II. LITERATURE REVIEW
2.4 T HE NEED FOR STANDARDIZATION
Esta seção descreve detalhadamente o algoritmo EvSOM. Embora o arcabouço geral do algoritmo seja típico de um AE, sua aplicação ao problema de formação de MTOs requer a definição de operadores específicos para o problema em mãos.
3.2.1 A função de aptidão proposta
Conforme analisado no Capítulo 1, a formação do MTO busca atingir dois objetivos: baixo erro de quantização e elevado ordenamento topológico. Assim, em princípio, combinações diversas de índices de qualidade destes dois critérios podem ser utilizadas como função de aptidão para avaliar soluções em uma população de soluções potenciais. A função de aptidão tem um efeito significativo sobre a qualidade do mapa e sobre a demanda computacional por parte do AE.
Por outro lado, a importância relativa dos índices que medem a qualidade da quantização vetorial e do ordenamento topológico no mapa final depende da aplicação e é praticamente impossível de ser avaliada e/ou controlada usando o algoritmo SOM original. É desejável, portanto, ter algum grau de controle desses índices durante a formação do MTO, de forma que o usuário possa escolher qual deles é o mais importante para uma dada aplicação. A abordagem baseada em AE provê tal flexibilidade pela escolha adequada da função de aptidão.
Kirk & Zurada (2002), trabalhando com mapas unidimensionais, usaram como índice de avaliação da preservação de topologia o erro topográfico ponderado (ETP), definido na notação original como ET P= 1 L L
∑
l=1 |i1(l) − i2(l)| − 1 N− 1 , (3.1)em que i1(l) e i2(l) são os índices dos neurônios cujos vetores de pesos são, respectivamente, o
primeiro e o segundo mais próximos do l-ésimo padrão de entrada, e |x| denota o valor absoluto de x. Os autores comparam os valores de ET P obtidos pela abordagem evolucionária (AG) por eles proposta com aqueles obtidos pelo algoritmo SOM original, mostrando vantagens claras para o AG.
Curry & Morgan (2004) usam como função de aptidão a distorção localmente ponderada (DLP), já definida na Equação (2.9) e repetida aqui por conveniência:
DLP(W) = E "
∑
∀ j hi j xi− wj 2 # , (3.2)em que E[·] denota o operador valor esperado tomado sobre todo o conjunto dos padrões de entrada, indexados por i, segundo a distribuição p(x). Uma comparação, em termos dos valores obtidos da DLP, entre a abordagem genética proposta por Curry e Morgan e o algoritmo SOM original favorece a primeira.
3.2 Proposição de um Mapa Auto-Organizável Evolucionário (EvSOM) 46
simples do erro de quantização (EQ) e do coeficiente de correlação de pearson (CCP) é tão boa quanto ETP e DLP para o propósito de formação de MTOs. Isso posto, a função de aptidão do EvSOM é dada por
Aptidão(W) =α·CCP(W) −β· EQ(W), (3.3)
em que os parâmetrosα,β ≥ 0 ponderam a importância relativa entre os índices. A escala ou a normalização deαeβ dependem do domínio da aplicação. No contexto de formação de MTOs, o índice CCP é a correlação cruzada entre todos os pares de distâncias [d(rm, rn) , d (wm, wn)],
sendo que (rm, rn) são as coordenadas dos pares de neurônios no arranjo de saída e (wm, wn)
são os correspondentes pares de vetores de pesos. O índice CCP é calculado como: CCP= ∑m∑n[d(rm, rn) d (wm, wn)]
(N − 1)SrSw
, (3.4)
em que d(rm, rn) =krm− rnk e d(wm, wn) =kwm− wnk sendo k.k a norma euclidiana. Além
disso, Sr = N−11 ∑Nl=1krl− ¯rk
1/2
é o desvio-padrão das distâncias entre os neurônios no arranjo de saída e Sw = N−11 ∑Nl=1kwl− ¯wk
1/2
é o desvio-padrão das distâncias entre os vetores de pesos. Aqui ¯w e ¯r são os valores médios dos vetores de pesos e das coordenadas no arranjo de saída, respectivamente. As grandezas Sr e Swnormalizam as distâncias nos espaços
de saída e entrada, respectivamente, tornando os valores de CCP independentes de escala e situados no intervalo [0, +1].
Por sua vez, o erro de quantização EQ é calculado como: EQ(W) = 1 L L
∑
i=1 N∑
j=1 xi− wj 2. (3.5)Ou seja, EQ é o valor médio do erro cometido pela reconstrução de cada amostra de dado pelo correspondente vetor protótipo.
É importante frisar que CCP é um índice do tipo “quanto maior, melhor”, enquanto EQ é do tipo “quanto menor, melhor”. A maximização da função de aptidão mostrada na Equação (3.3) via AE é o núcleo do algoritmo aqui proposto. A abordagem proposta é comparada com o algoritmo SOM, com um AE utilizando DLP como função de aptidão como em Curry & Morgan (2004) e com um algoritmo subida da encosta com a mesma função de aptidão, Equação 3.3, em termos dos valores de EQ, ETP, DLP e CCP para um dado mapa formado.
As referências Curry & Morgan (2004) e Kirk & Zurada (2002) são representativas da abordagem adotada neste trabalho no sentido de que ambas aplicam otimização evolucionária de uma função de aptidão para a formação do MTO. No entanto, deve-se destacar uma diferença fundamental entre os algoritmos ali utilizados e aquele aqui proposto, qual seja: as funções de aptidão de ambos os trabalhos incorporam direta ou indiretamente o conceito de uma função de vizinhança que varia durante o processamento do algoritmo, inserido heuristicamente por Kohonen para induzir o ordenamento topológico entre os espaços de entrada e de saída. Já foi notado por Bishop et al. (1998) e Heskes (1999) que, embora não exista uma função objetivo ou função de energia a qual é minimizada pelo algoritmo SOM de Kohonen, funções de energia existem, tais que, quando minimizadas resultam no ordenamento topográfico do mapa de neurônios (Veja Seção 2.5). Uma dessas funções, proposta em Heskes (1999), é precisamente
3.2 Proposição de um Mapa Auto-Organizável Evolucionário (EvSOM) 47
o índice DLP utilizado por Curry & Morgan (2004). Para essa função de energia uma regra de busca estocástica baseada em gradiente descendente foi derivada em Heskes (1999), o que torna o experimento de Curry & Morgan (2004) um exercício de AG. Por outro lado, o índice ETP, utilizado em Kirk & Zurada (2002), também faz uso do conceito de vizinhança no arranjo de saída, na medida em que não apenas conta (acumula) as inversões de ordem entre os primeiros e segundos vencedores de cada amostra, mas pondera essas inversões pela distância entre eles na grade de saída.
Já a combinação de EQ e CCP como função de aptidão, aqui proposta, não incorpora um mecanismo explícito do tipo função de vizinhança (ponderação pelas distâncias no espaço de saída) como indutor do ordenamento topológico, tornando este um algoritmo de natureza qualitativamente diferente daqueles. De fato, no cálculo da correlação, cada distância tem peso igual.
3.2.2 Operadores Genéticos
Operadores genéticos atuam sobre indivíduos da população chamados de cromossomos. A estrutura de dados escolhida para codificar os cromossomos costuma ter papel decisivo no desempenho do AE e na definição dos operadores genéticos. No AE aqui considerado a codificação dos MTOs em indivíduos foi realizada de maneira muito direta. No que segue NP
denota o tamanho da população.
Cada indivíduo vk, k = 1, . . . , NPé representado por uma matriz de números reais. Na forma
mais geral, cada linha dessa matriz é um vetor ui, i = 1, . . . , N composto pela concatenação do
vetor de pesos com dois conjuntos de parâmetros da estratégia evolucionária utilizada [Castro 2006]. Para um arranjo de saída com N neurônios, vk = {ui, i = 1, . . . , N} com cada linha