Uma Implementaç ˜ao Concorrente de Redes Neurais PCA para

Uma Implementação Concorrente de Redes Neurais PCA para
Compressão de Imagens
Willian Y. Honda1 , Patrı́cia R. Oliveira1 ,
Luciano A. Digiampietri1 , Marcone C. Pereira1
1
Escola de Artes, Ciências e Humanidades da USP
Av. Arlindo Bettio, 1000 – 03828-000 – São Paulo – SP
{kio,proliveira,digiampietri,marcone}@usp.br
Abstract. Principal Component Analysis (PCA) is a statistical method that can
be applied for reducing data dimensionality. Focusing on a neural network
which approximates the results obtained by classical PCA, the main contribution
of this work consists in presenting a concurrent implementation model for such
network. A comparative study shows that the proposal, which was applied to
compress images, presents promissing results when more than one computer
processor are available.
Resumo. A Análise de Componentes Principais (PCA) é um método estatı́stico
que pode ser aplicado para reduzir a dimensionalidade de conjuntos de dados.
Considerando uma rede neural que aproxima os resultados da PCA clássica,
a principal contribuição deste trabalho consiste em apresentar um modelo de
implementação concorrente para essa rede. Um estudo comparativo mostra que
a proposta, aplicada à tarefa de compressão de imagens, apresenta resultados
promissores quando executada em computadores com mais de um processador.
1. Introdução
Ao comprimir uma imagem, esta passa a ser representada por uma quantidade
menor de dados, podendo, ou não, haver perdas na qualidade da sua versão recuperada. Neste contexto, a técnica estatı́stica de Análise de Componentes Principais
(PCA1 ) [Johnson and Wichern 1998] pode ser usada como um método de compressão
de imagens digitais, já que permite reduzir a dimensionalidade de um conjunto de dados preservando suas caracterı́sticas mais relevantes [Ziyad et al. 1998, Fang et al. 2003,
Rizk and Koosha 2006].
Além da abordagem estatı́stica tradicional para a PCA, implementada em vários
software comerciais, como MinitabT M , MatlabT M e SAST M , uma abordagem computacional alternativa baseia-se na utilização de redes neurais artificiais. Dessa forma, é
possı́vel aplicar redes neurais PCA no processo de compressão de imagens digitais, uma
vez que esses modelos conseguem aproximar os resultados gerados pela técnica PCA
clássica e superar o JPEG no que diz respeito ao erro quadrático médio entre as imagens
originais e as versões recuperadas [Oliveira et al. 2000].
A rede neural explorada neste trabalho é conhecida como Rede Neural PCA Adaptativa e foi proposta por Rubner e Tavan em 1989 [Rubner and Tavan 1989]. No trabalho
1
Do original, em inglês, Principal Component Analysis.
desenvolvido em [Oliveira et al. 2000], uma implementação sequencial desse modelo
mostrou-se eficiente no cálculo das componentes principais usadas como base para compressão de imagens. A proposta apresentada no presente artigo consiste na elaboração de
um modelo de implementação concorrente para a Rede Neural PCA Adaptativa também
aplicado à compressão de imagens. A principal motivação por trás dessa ideia original é a
obtenção de melhorias no desempenho do aplicativo graças à popularização de computadores pessoais e estações de trabalho com mais um processador. A avaliação da proposta
é realizada por meio de um estudo comparativo entre o desempenho da implementação
concorrente e outras duas implementação sequenciais. Além disso, as componentes principais obtidas por este modelo são comparadas com as geradas pelo software MinitabT M .
O restante deste trabalho está dividido como segue. A seção 2 apresenta a técnica
PCA como um método estatı́stico clássico; a seção 3 apresenta implementações de Redes
Neurais PCA Adaptativa que aproximam os resultados da técnica PCA estatı́stica; a seção
4 discute os resultados experimentais e a seção 5 apresenta as conclusões e trabalhos
futuros.
2. Análise de Componentes Principais
A PCA é uma técnica estatı́stica para análise de dados e sinais, utilizada para seleção e
extração de caracterı́sticas [Mao and Jain 1995]. Esta técnica realiza uma transformação
linear dos dados originais, permitindo uma redução de dimensionalidade, de modo que
a escolha dos elementos a serem eliminados seja ótima com respeito ao erro quadrático
médio [Haykin 2001].
Basicamente, a PCA baseia-se no pressuposto de que é possı́vel definir m
variáveis estatisticamente não correlacionadas, denominadas componentes principais, a
partir de combinações lineares das p variáveis do conjunto de dados original, em que
m ≤ p [Johnson and Wichern 1998]. Geralmente, como há mais informação concentrada nestas m componentes do que nas p variáveis originais, as m componentes podem
substituir as p variáveis originais no conjunto de dados.
2.1. Cálculo das componentes principais
Na abordagem clássica, primeiramente a PCA resolve o Problema do Autovalor:
Cx aj = λj aj , para j = 1, 2, ..., p
(1)
em que Cx é a matriz de covariância dos dados originais, λj é um dos autovalores de Cx e
aj é o autovetor associado ao autovalor λj . Após esta etapa, os autovalores são ordenados
em ordem decrescente:
λ1 ≥ λ2 ≥ ... ≥ λp
(2)
As componentes principais são calculadas de acordo com a equação:
Zj = aTj X = X T aj , para j = 1, 2, ..., p
(3)
em que Zj é a j-ésima componente principal, aj é o autovetor associado ao autovalor λj
e X representa o conjunto de dados original. Uma vez que o conjunto de dados X é
composto por p variáveis, a Equação (3) está sujeita à seguinte restrição:
a2j1 + a2j1 + ... + a2jp = 1, para j = 1, 2, ..., p
Além disso, as componentes principais possuem as seguintes propriedades:
(4)
1. As componentes principais Zj , j
correlacionadas entre si;
2. V ar(Zj ) = λj , para j = 1, 2, ..., p;
3.
p
X
j=1
V ar(Zj ) =
p
X
= 1, 2, ..., p são estatisticamente não-
V ar(Xj ).
j=1
A Propriedade 2 indica que os autovalores correspondem às variâncias das respectivas componentes principais. A Propriedade 3 mostra que a variância do conjunto
original é preservada pelas componentes principais.
2.2. Reconstrução dos dados originais e Redução de dimensionalidade
O conjunto original pode ser reconstruı́do a partir das componentes principais Z, reescrevendo a Equação (3):
X=
p
X
Z j aj .
(5)
i=1
Como os autovalores representam a variância das componentes principais, é adequado eliminar as componentes com os menores autovalores. Para que haja uma redução
de dimensionalidade, consideram-se apenas os autovetores associados aos m autovalores
mais significativos no processo de reconstrução dos dados originais:
X̂ =
m
X
Zj aj , para m < p,
(6)
i=1
em que X̂ representa uma aproximação do conjunto de dados original.
2.3. Limitações da técnica PCA
O método apresentado para encontrar as componentes principais enfrenta algumas
limitações que o tornam aplicável somente a exemplos mais simples. Primeiramente,
a resolução do problema do autovalor depende do cálculo de um determinante, um processo demorado quando se trata de matrizes grandes [Poole 2004]. Como a matriz de
covariância cresce proporcionalmente ao número de atributos do conjunto sendo analisado, este método se torna inadequado. Além disso, todos os autovalores precisam ser
calculados, mesmo que poucos autovetores venham a serem utilizados no processo.
Neste caso, métodos de aproximação podem ser utilizados para estimar os autovetores e, consequentemente, as componentes principais. Dentre os métodos de
aproximação, modelos de redes neurais artificiais têm se mostrado como um método eficiente para o cálculo dos principais autovetores sem a necessidade do cálculo da matriz
de covariância dos dados.
3. Rede Neural PCA Adaptativa
A Rede Neural PCA Adaptativa utiliza um tipo de aprendizado não-supervisionado para
ajuste dos pesos de suas conexões e sua arquitetura consiste de p unidades de entrada
e m neurônios de saı́da (ver Figura 1). Cada unidade de entrada i está conectada a cada
neurônio de saı́da j com um peso wij . Além disso, existem conexões laterais com peso uij
que ligam um neurônio de saı́da i a um neurônio de saı́da j somente se i < j. Um neurônio
Figura 1. Arquitetura da rede neural PCA Adaptativa
de saı́da j produz, no tempo n, uma saı́da yj (n) , que é gerada em resposta ao conjunto
de entrada xi , para i = 1, 2, ..., p, calculada pela seguinte equação [Mao and Jain 1995]:
yj (n) =
p
X
i=1
wij (n)xi (n) +
j
X
ukj yk (n).
(7)
k=1
A atualização dos pesos sinápticos wij no tempo n segue a regra de aprendizado hebbiano [Mao and Jain 1995], com a inclusão de um termo para acelerar a convergência, de
acordo com a equação:
∆wij (n + 1) = ηxi yi + β∆wij (n), para i = 1, 2, ..., p e j = 1, 2, ..., m,
(8)
em que η é uma constante de aprendizado e β é o momentum. Já os pesos das conexões
laterais são ajustados de acordo com a regra de aprendizado anti-hebbiana:
∆ukj (n + 1) = µyk yj + β∆ukj (n), para k < j e j = 1, 2, ..., m,
(9)
em que µ é outro parâmetro de aprendizado positivo. De acordo com o critério de convergência da rede apresentada em [Haykin 2001], a tendência das conexões laterais é
diminuir assintoticamente, devido ao efeito da regra anti-hebbiana. Quando estes pesos
atingirem valores suficientemente pequenos, os pesos das conexões internas da rede terão
convergido para os autovetores da matriz de correlação dos dados. Isto é,
limn→∞ uj (n) = 0, para j = 1, 2, ..., m ;
(10)
limn→∞ wj (n) = aj , para j = 1, 2, ..., m .
(11)
O algoritmo da Rede Neural PCA Adaptativa é apresentado na Figura 2. A seguir são
apresentados aspectos de uma implementação individual e de uma implementação concorrente da Rede Neural PCA Adaptativa.
3.1. Implementação individual
Em [Haykin 2001], prova-se que os pesos das conexões internas de um neurônio j só irão
convergir se os dos neurônios de 1 a j − 1 já tiverem convergido. Assim sendo, observa-se
que o processamento da rede pode ser focado em cada neurônio de maneira individual e
sequencial, conservando a interdependência entre os mesmos.
Para esquematizar essas execuções individuais, a arquitetura original da Rede
Neural PCA Adaptativa pode ser subdividida em estruturas menores, cada uma orientada
por um neurônio de saı́da, como pode ser visto na Figura 3, para o primeiro neurônio.
Figura 2. Algoritmo da Rede Neural PCA Adaptativa.
Figura 3. Estrutura da primeira sub-arquitetura da rede neural PCA Adaptativa.
Este modelo é implementado pelo algoritmo da Rede Neural PCA Adaptativa,
considerando apenas os pesos relacionados ao primeiro neurônio, como mostrado pela
Equação (12). A atualização dos pesos das conexões internas é feita de acordo com a
Equação (8), observando-se a não existência de pesos de conexões laterais.
y1 (n) =
p
X
wi1 (n)xi (n).
(12)
i=1
A segunda sub-arquitetura da rede neural é orientada pelo neurônio de saı́da relativo à segunda componente principal, como mostrado na Figura 4. Este segundo modelo também
Figura 4. Estrutura da segunda sub-arquitetura da rede neural PCA Adaptativa.
é implementado pelo algoritmo da Rede Neural PCA Adaptativa, considerando-se apenas os pesos relacionados ao segundo neurônio. Assim como a primeira sub-arquitetura,
a atualização dos pesos das conexões internas é feita de acordo com a Equação (8) e a
atualização do peso da conexão lateral com o primeiro neurônio é feita de acordo com
a Equação (9). Como este modelo possui uma dependência com o primeiro neurônio, já
que utiliza a sua saı́da, ele deve convergir depois que a primeira sub-arquitetura já tiver
convergido. A saı́da do neurônio da segunda sub-arquitetura da rede será:
y2 (n) =
p
X
(wi2 (n)xi (n) + u12 y1 (n)) .
(13)
i=1
De forma geral, a estrutura da j-ésima sub-arquitetura da rede neural é mostrada na
Figura 5. O neurônio de saı́da considera os pesos da sinapse com as unidades de en-
Figura 5. Estrutura da j-ésima sub-arquitetura da rede neural
trada, os pesos das sinapses laterais com os neurônios de saı́da das j − 1 redes neurais
anteriores e suas saı́das. O ajuste dos pesos são calculados de acordo com o algoritmo da
Rede Neural PCA Adaptativa, assim como a saı́da da rede.
3.2. Implementação concorrente
Uma RNA pode ser considerada como um processador distribuı́do densamente paralelo
que tem uma propensão natural para armazenar conhecimento experimental e disponibilizá-lo para uso [Haykin 2001]. Portanto, considera-se, no presente trabalho, a utilização
de princı́pios computacionais de programação concorrente para otimizar o desempenho
da Rede Neural PCA Adaptativa.
Pode-se implementar a programação concorrente na Rede Neural PCA Adaptativa
através do uso de threads. A proposta apresentada neste trabalho considera uma thread
diferente para cada sub-arquitetura, cada uma delas executada de forma concorrente.
Neste caso, cada sub-arquitetura seria responsável por gerar os autovetores necessários
para o cálculo de cada uma das componentes principais.
Entretanto, observa-se, pela Figura 5, que há uma interdependência entre os
neurônios da rede. Na implementação individual este fator não é critico, já que, com
exceção do primeiro neurônio, um determinado neurônio j só iniciará sua execução
quando o neurônio j − 1 terminar seu processamento. Na implementação concorrente, há
a necessidade da utilização de mecanismos de sincronização para que um neurônio j não
encerre antes dos j − 1 neurônios anteriores e também não inicie sua execução antes do
neurônio j − 1.
Para sincronizar o processamento das threads na implementação concorrente, foi
utilizado o conceito de semáforo. Fundamentalmente, um semáforo é uma variável inteira que tem duas operações atômicas (aquisição e liberação). Isso significa que quando
uma thread modifica o valor do semáforo, nenhuma outra thread pode fazê-lo de modo
concorrente [Silberschatz et al. 2004]. Os semáforos foram utilizados neste trabalho para
sincronizar o inı́cio e término de cada thread.
Também foi estabelecida uma porcentagem mı́nima de ciclos que um neurônio
deve executar após o encerramento do neurônio da sub-arquitetura anterior. Desta forma,
se restar apenas esse limiar de ciclos para um dado neurônio executar e o neurônio antecessor não tiver concluı́do sua execução, o contador de ciclos do neurônio atual será
congelado até que o neurônio anterior encerre sua execução.
4. Resultados experimentais
Os testes foram realizados em um computador com as seguintes configurações: processador Intel Core 2 CPU 6320 1,86GHz, memória RAM 3,24GB e sistema operacional Microsoft Windows XP Professional 2002 Service Pack 3. As implementações
utilizaram como entrada imagens de dimensões 640 x 480 pixels, selecionadas do conjunto de domı́nio público da Microsoft Research Cambridge Object Recognition Image
Database [Microsoft 2005].
O pré-processamento da imagem foi dividido em duas etapas. Na primeira, a imagem colorida foi convertida em uma imagem em tons de cinza e reduzida para 160 x 120
pixels. Essas operações foram feitas apenas para facilitar a visualização dos resultados
produzidos pelos algoritmos. A técnica aqui apresentada pode ser aplicada a imagens
maiores e coloridas. A segunda etapa consiste da escolha arbitrária do número de autovetores desejados e da divisão da imagem em blocos com tamanho correspondente a esse
número de autovetores. Para os experimentos aqui apresentados, o número de autovetores
escolhido foi 10. A imagem de 160 x 120 pixels foi dividida em 1920 blocos de 2 x 5
pixels, originando uma matriz de 1920 linhas por 10 colunas. Esta matriz foi normalizada
através da divisão do valor de cada célula por 255. Por fim, o valor de cada célula da
matriz foi subtraı́do pela média dos valores da matriz.
Para cada implementação da Rede Neural PCA Adaptativa foram obtidos os autovetores para geração das componentes principais e o tempo de execução do treinamento.
Cada treinamento foi executado com diferentes quantidades de ciclos: de 1.000 a 10.000,
variando de 1.000 em 1.000 ciclos e de 20.000 a 100.000, variando de 10.000 em 10.000
ciclos. Além disso, para a implementação concorrente, estabeleceu-se margens de 20%
e 70% da quantidade total de ciclos para que um neurônio aguarde o neurônio da subarquitetura anterior encerrar sua execução. Feito isso, calculou-se o erro quadrático médio
entre a imagem restaurada e a imagem original.
A Figura 6 apresenta um gráfico do erro quadrático médio em função do número
de ciclos para cada uma das execuções. Analisando esta figura, nota-se que as melhores aproximações, tanto utilizando as 10 componentes principais quanto apenas 7
componentes, foram obtidas pela implementação concorrente com a utilização de uma
margem de 70% da quantidade de ciclos. Mesmo com a utilização de poucos ciclos,
esta implementação alcançou melhores aproximações em relação às demais, isto é, sua
convergência foi relativamente mais rápida. Por outro lado, a abordagem sequencial apresentou erros mais elevados, o que indica que a rede não alcançou a convergência de todos
seus autovetores e necessitaria de mais ciclos para tal.
O próximo passo consistiu em aplicar o software MinitabT M na imagem selecionada com o objetivo de gerar os autovetores e, assim, calcular o erro quadrático médio
com a imagem reconstruı́da. Os resultados foram comparados com as implementações da
Rede Neural PCA Adaptativa e são apresentados na Figura 7, onde os erros são conside-
Figura 6. Erro Quadrático Médio para 10 e 7 componentes principais
rados após 100.000 ciclos de treinamento. Para poucas componentes, observa-se que os
erros das redes neurais são similares aos obtidos pelo MinitabT M . A diferença aumenta
quando mais componentes são consideradas. Isso acontece pois os pesos das conexões
internas das redes relativos a essas componentes ainda não convergiram totalmente.
Figura 7. Erro Quadrático Médio: Comparação com MinitabT M .
Os tempos de execução do treinamento das implementações da rede podem ser
vistos na Figura 8. A implementação concorrente com 20% de margem de execução
apresentou-se mais rápida em todas situações. Por outro lado, a abordagem concorrente
com 70% de margem de execução mostrou um tempo maior do que todas as outras.
Figura 8. Tempo de execução dos algoritmos até 10.000 ciclos e até 100.000
A Figura 9 apresenta o tempo de execução dos algoritmos até a convergência de
um dado neurônio. Neste caso, são analisados os tempos até que os neurônios 5 e 6 tenham convergido. Para isto, considerou-se que um neurônio convergiu quando a diferença
entre seus autovetores e os valores dos autovetores calculados através de abordagens estatı́sticas fosse inferior a 0,000001. Observa-se nesta figura que a abordagem concorrente
com 70% de margem de execução é a que converge mais rápido, enquanto que a sequencial é a abordagem que demora mais tempo para convergir.
Figura 9. Tempo de execução dos algoritmos até convergência.
A Figura 10 apresenta as imagens reconstruı́das utilizando-se de 1 a 10 componentes principais resultantes da execução da abordagem concorrente com 70% de margem
de execução e 100.000 ciclos. Abaixo de cada imagem encontra-se o número de componentes principais utilizadas (entre parênteses) e o erro quadrático médio em relação a
imagem original. É importante destacar que a imagem que utiliza apenas uma componente principal ocupa 10% do espaço da imagem original, a que utiliza duas componente,
20% e assim por diante. Nota-se também que o erro associado a imagem que utilizou 10
componentes é maior do que o erro da imagem com 9 componentes, o que indica que a
décima componente ainda não convergiu.
Figura 10. Imagem reconstruı́da utilizando de 1 a 10 Componentes Principais
Pelos resultados apresentados, a abordagem concorrente com 70% de margem de
execução apresenta maior estabilidade ao aproximar a imagem reconstruı́da em termos do
erro quadrático médio e o melhor custo benefı́cio considerando o tempo de convergência.
Já a abordagem concorrente com 20% de margem de execução apresenta-se mais rápida
em tempo de execução, porém necessita de mais ciclos para convergir.
A abordagem individual apresenta uma vantagem em relação à sequencial, pois
possui uma convergência mais rápida, entretanto somente consegue uma aproximação
parecida à implementação concorrente com um grande número de ciclos de treinamento.
É importante ressaltar que apenas a abordagem concorrente utiliza mais de um processador. Desta forma, havendo apenas um processador disponı́vel, a abordagem individual
é a recomendada.
5. Conclusões e trabalhos futuros
Diferentes modelos de implementação da Rede Neural PCA Adaptativa foram apresentados e discutidos neste trabalho, tendo como foco a aplicação dessa abordagem à tarefa
de compressão de imagens. Em especial, foi proposta a incorporação de princı́pios de
programação concorrente a um modelo que considera a rede neural em questão como
composta de sub-arquiteturas interdependentes.
Os resultados experimentais apontaram que, dentre os quatro modelos de
implementação que foram desenvolvidos, o que apresentou a melhor relação
custo/benefı́cio entre tempo de execução e precisão de resultados foi a abordagem concorrente que prevê, para cada neurônio, uma margem de execução de 70% de ciclos apó
o encerramento do neurônio da sub-arquitetura anterior.
Como continuação do trabalho, estão sendo avaliados critérios mais flexı́veis para
a convergência dos modelos, como o estabelecimento de limiares para os ajustes e valores dos pesos das conexões da rede. No contexto da aplicação, a pesquisa envolverá
compressão de grandes volumes de imagens, tais como sequências e dados de vı́deo.
Referências
Fang, T., Lu, J., Wang, Z., and Sun, Y. (2003). An Image Compressing Algorithm based
on PCA/SOFM Hybrid Neural Network. In The 29th Annual Conference of the IEEE
Industrial Electronics Society, 2003 (IECON’03), pages 2103–2107.
Haykin, S. (2001). Redes Neurais: Princı́pios e prática. Bookman, 2nd edition.
Johnson, R. A. and Wichern, D. W. (1998). Applied Multivariate Statistical Analysis.
Prentice-Hall, Inc., Englewood Cliffs, NJ, 4th edition.
Mao, J. and Jain, A. K. (1995). Artificial neural networks for feature extraction and
multivariate data projection. IEEE Transactions on Neural Networks, 6(2):296–317.
Microsoft (2005).
Microsoft research cambridge object recognition image
database. http://research.microsoft.com/research/downloads/Details/b94de342-60dc45d0-830b-9f6eff91b301/Details.aspx (acessado em 2009-01-22).
Oliveira, P. R., Romero, R. F., Nonato, L. G., and Mazucheli., J. (2000). Techniques
for Image Compression: a Comparative Analysis. In Proceedings of VIth Brazilian
Symposium on Neural Networks (SBRN’2000), pages 249–254.
Poole, D. (2004). Álgebra Linear. Pioneira Thompson Learning, São Paulo.
Rizk, M. and Koosha, E. (2006). A comparison of principal component analysis and generalized hebbian algorithm for image compression and face recognition. In Proceedings of The 2006 International Conference on Computer Engineering, pages 214–219.
Rubner, J. and Tavan, P. (1989). A self-organizing network for principal component
analysis. Europhysics Letters, 10(7):693–698.
Silberschatz, A., Gagne, G., and Galvin, P. B. (2004). Sistemas Operacionais com Java:
Conceitos e Aplicaçp̃es. Elservier, Rio de Janeiro, 6th edition.
Ziyad, N., Gilmore, E., and Chouikha, M. (1998). Improvements for image compression
using adaptive principal component extraction (APEX). In The Thirty-Second Asilomar Conference on Signals, Systems & Computers, pages 969–973.