View
8
Download
0
Category
Preview:
Citation preview
Tópico 7 – Seleção de Atributos
IA004 – Redes Neurais II – Prof. Romis Attux Página 1
Tópico 7 – Seleção de Atributos
O projeto de um modelo de regressão ou classificação, como tivemos a chance de ver
anteriormente no curso, tem por base a utilização de um conjunto de dados para definição
de parâmetros livres de uma estrutura escolhida. Até este momento, abordamos esse
problema de uma perspectiva voltada, prioritariamente, ao processo de construção da
máquina em si. Neste tópico, abordaremos outro ponto: como definir, a partir do conjunto
de dados, um bom repertório de atributos?
Pode-se pensar, a princípio, que se trata de uma etapa “supérflua” – bastaria passar todos os
atributos à máquina e ela, com seu poder de aproximação, se encarregaria de realizar a
seleção necessária. No entanto, do ponto de vista prático, essa noção pode ser inadequada
por uma série de razões [Guyon e Elisseeff, 2003]:
o Pode ser mais simples compreender os dados e as necessidades de projeto se o espaço
de entrada for relativamente pequeno.
o Utilizar um conjunto compacto de atributos pode ser relevante para permitir que o
treinamento e a operação da máquina ocorram num período de tempo compatível com
a aplicação.
Tópico 7 – Seleção de Atributos
IA004 – Redes Neurais II – Prof. Romis Attux Página 2
o Realizar uma escolha de “bons atributos” permite, em muitos casos, que se evite o
problema de “maldição de dimensionalidade”.
o Uma vez que o conjunto de dados disponíveis é limitado, a eventual eliminação de
“atributos pobres ou ruidosos” pode tornar o processo de aprendizado mais efetivo em
termos de capacidade de generalização.
De antemão, podemos imaginar duas formas básicas de realizar a seleção de atributos:
o Lançar mão de medidas estatísticas gerais para quantificar a relevância de cada
atributo.
o Utilizar o treinamento do modelo que se pretende usar na avaliação.
A primeira forma dá origem ao conceito de filtro, e a segunda ao conceito de wrapper.
Teremos a chance de discutir exemplos de ambas as estratégias a seguir.
7.1 – Avaliação Estatística Geral – o Conceito de Filtro
Conforme delineado acima, o conceito de filtro, em seleção de variáveis, diz respeito a
métodos que utilizam apenas uma análise estatística geral, ou seja, que não geram máquinas
Tópico 7 – Seleção de Atributos
IA004 – Redes Neurais II – Prof. Romis Attux Página 3
treinadas para avaliação de desempenho. Há, de certa forma, uma “filtragem” a priori de
atributos [Holschuh, 2008]. Para que possamos compreender a idéia, vamos analisar, seguindo o raciocínio exposto em
[Guyon e Elisseeff, 2003] a geração de uma medida de ordenação (ranking) baseada em
correlação / covariância. Para tanto, suponhamos que se disponha de um conjunto de dados
do tipo (xi, di), i = 1, ..., N. Para o caso de classificação, consideraremos que os rótulos são
valores numéricos (e.g. +1 e -1).
Intuitivamente, adaptamos o modelo para aproximar o valor de di para cada padrão de
entrada xi. Portanto, poderíamos pensar em avaliar a correlação de cada um dos M atributos
xj,i, j = 1, ..., M, relativamente ao valor desejado di. Para tanto, analisaremos o coeficiente
de correlação de Pearson:
𝑅(𝑗) =𝑐𝑜𝑣(𝑥𝑗 , 𝑑)
√𝑣𝑎𝑟(𝑥𝑗)𝑣𝑎𝑟(𝑑)
onde cov(.) representa a covariância e var(.) a variância. O coeficiente pode ser estimado da
seguinte forma:
Tópico 7 – Seleção de Atributos
IA004 – Redes Neurais II – Prof. Romis Attux Página 4
𝑅(𝑗) =∑ (𝑥𝑗,𝑖 − 𝑥�̅�)(𝑑𝑖 − �̅�)𝑁
𝑖=1
√∑ (𝑥𝑗,𝑖 − 𝑥�̅�)2𝑁
𝑖=1 ∑ (𝑑𝑖 − �̅�)2𝑁
𝑖=1
Pode-se então imaginar que, após avaliar R(j), j = 1, ..., M, far-se-ia uma escolha dos K
“melhores” atributos. Uma crítica imediata que pode ser feita, e não sem razão, é que a
correlação, por ser uma estatística de segunda ordem, captura apenas uma dependência
linear entre os atributos e o sinal de interesse. Portanto, caso se tenha um modelo não-linear
em mãos, haverá uma limitação naquilo que se poderá aprender das variáveis utilizando o
coeficiente de Pearson.
Outra possibilidade interessante é utilizar como métrica uma espécie de “relação sinal-
ruído” que evoca a metodologia do discriminante de Fisher. Para tanto, inicialmente, dá-se
aos valores do i-ésimo atributo xi que se associam a padrões da classe +1 o nome de xi+ e,
aos valores da classe -1, o nome de xi-. Com isso, pode-se escrever [Duch, 2006]:
𝑅𝐹𝑖𝑠ℎ𝑒𝑟(𝑖) =|𝜇𝑖
+ − 𝜇𝑖−|
𝑣𝑎𝑟𝑖+ + 𝑣𝑎𝑟𝑖
−
Tópico 7 – Seleção de Atributos
IA004 – Redes Neurais II – Prof. Romis Attux Página 5
onde i+ é a média dos valores xi
+ e vari+ é a variância associada, e i
- é a média dos valores
xi-, sendo vari
- a variância associada.
Para contornar as limitações estatísticas advindas do uso de estatísticas de segunda ordem, é
possível utilizar a informação mútua para avaliar a relação entre cada atributo e os valores
desejados. Teremos a chance, no futuro, de discutir em mais detalhe as origens e as
peculiaridades da medida de informação mútua, mas, por ora, basta expor o seguinte:
o A informação mútua é uma medida de dependência estatística entre variáveis, já que
I(X, Y) ≥ 0 e I(X, Y) = 0 se e somente se X e Y são estatisticamente independentes.
o O fato de a informação mútua lidar diretamente com o conceito de dependência
estatística faz com que essa medida seja capaz de captar “correlações não-lineares”
gerais entre as variáveis.
Caso se trabalhe com valores contínuos, define-se a informação mútua como:
𝐼(𝑋, 𝑌) = ∫ 𝑝(𝒙, 𝒚)𝑙𝑜𝑔 (𝑝(𝒙, 𝒚)
𝑝(𝒙)𝑝(𝒚)) 𝑑𝒙𝑑𝒚
Tópico 7 – Seleção de Atributos
IA004 – Redes Neurais II – Prof. Romis Attux Página 6
que é, basicamente, a divergência de Kullback-Leibler entre a densidade de probabilidade
conjunta p(x,y) e p(x)p(y). Se lembrarmos que a condição de independência é dada por
p(x,y) = p(x)p(y), percebemos que a informação mútua mede, intuitivamente, uma
“distância” entre a densidade conjunta e a densidade que vigoraria em caso de
independência.
Para o caso de valores discretos, tem-se uma definição análoga:
𝐼(𝑋, 𝑌) = ∑ ∑ 𝑃(𝑋, 𝑌)𝑙𝑜𝑔 (𝑃(𝑋, 𝑌)
𝑃(𝑋)𝑃(𝑌))
A partir dessas definições, pode-se definir de maneira direta uma medida de ordenação
como:
RIM(j) = I(xj, d), j = 1, ..., M
Apesar das inegáveis vantagens conceituais, o uso da informação mútua traz dificuldades –
a principal delas é a necessidade de estimar, implícita ou explicitamente, a estrutura de
probabilidade das variáveis envolvidas. No caso de variáveis discretas, o problema é
Tópico 7 – Seleção de Atributos
IA004 – Redes Neurais II – Prof. Romis Attux Página 7
relativamente bem comportado – podem-se contar frequências de um repertório finito de
possibilidades – mas, no caso contínuo, a coisa é mais complicada – é preciso contar
frequências num “grid”, ou utilizar outros estimadores, como o de Parzen [Guyon e
Elisseeff, 2003].
Uma limitação dessa metodologia de ordenação em separado dos atributos é a possibilidade
de que uma variável que, sozinha, não é particularmente relevante leve a ganhos de
desempenho em conjunto com outras variáveis. Pode mesmo acontecer que duas variáveis
“ruins” sejam “boas” em conjunto. Naturalmente, essa limitação pode ser, até certo ponto
contornada, sem necessidade de abandonar o arcabouço de filtragem, caso se analisem
dependências entre múltiplas variáveis. No entanto, isso levanta dificuldades combinatórias,
o que pode ter um impacto “explosivo” com o aumento do número de atributos.
7.2 - Wrappers
Como delineado anteriormente, a principal diferença entre filtros e wrappers é que a
segunda classe de métodos de seleção faz uso da máquina treinada na avaliação
comparativa dos atributos.
Tópico 7 – Seleção de Atributos
IA004 – Redes Neurais II – Prof. Romis Attux Página 8
Basicamente, é preciso ter um conjunto de atributos, uma metodologia de busca nesse
conjunto, um critério de avaliação de desempenho e um modelo de máquina [Guyon e
Elisseeff, 2003].
O problema de realizar uma busca no espaço de atributos é bastante complicado por seu
caráter explosivo. Por exemplo, se tivermos 3 atributos, x1, x2 e x3, podemos formar
combinações como {x1}, {x2}, {x3}, {x1, x2}, {x1, x3}, {x2, x3} e {x1, x2, x3}. Nota-se que,
para um número de atributos maior, a complexidade pode “sair de controle”. Para contornar
essa dificuldade, podem ser utilizados métodos de busca como algoritmos genéticos e
simulated annealing, ou podem ser utilizadas heurísticas construtivas gulosas, como
veremos mais adiante.
Para avaliar o desempenho da máquina junto a determinada configuração de atributos,
pode-se recorrer a um processo de validação cruzada. Por fim, a escolha da máquina a ser
usada depende da natureza do problema em mãos.
Duas heurísticas gulosas interessantes para a construção de wrappers são a seleção adiante e
e a retro-eliminação (forward selection e backward selection) [Holschuh, 2008]. No caso da
seleção adiante, parte-se do conjunto vazio de atributos e se faz uma avaliação do
Tópico 7 – Seleção de Atributos
IA004 – Redes Neurais II – Prof. Romis Attux Página 9
desempenho individual de cada atributo em termos da métrica de avaliação (e.g. validação
cruzada). Seleciona-se então o melhor atributo para fazer parte do conjunto. Fixado esse
atributo, faz-se uma nova análise de desempenho com a inclusão de cada um dos atributos
restantes – o que tiver melhor desempenho passa a fazer parte do conjunto. Pode-se
interromper o processo quando a inclusão de um novo atributo não levar a uma melhora de
desempenho frente ao estado anterior.
Na retro-eliminação, tem-se a perspectiva oposta. Considera-se o estado inicial como sendo
composto de todos os atributos. Em seguida, faz-se uma análise de desempenho com a
retirada de um atributo, gerando o estado seguinte. O processo se repete até que não haja
melhoria de desempenho.
Conforme exposto em [Holschuh, 2008], o processo de seleção adiante é interessante por
ser “mais leve” computacionalmente – parte-se de modelos pequenos. Por outro lado, o
processo de retro-eliminação, por utilizar, desde o início, um conjunto amplo de atributos,
pode ser mais sensível a conjunções desejáveis de variáveis. Um exemplo simples está na
Fig. 1.
Tópico 7 – Seleção de Atributos
IA004 – Redes Neurais II – Prof. Romis Attux Página 10
Figura 1 – Exemplo de Aplicação das Heurísticas Gulosas [Holschuh, 2008]
É importante frisar que o tipo de critério de parada apresentado (em caso de não haver
melhoria, interrompa o algoritmo) pode fazer com que o método de seleção fique preso
num ótimo local. Para evitar essa limitação, podem ser usados critérios de parada mais
elaborados (k > 1 passos sem melhoria, por exemplo) e operadores mais complexos de
geração de configurações (estados) [Holschuh, 2008].
Tópico 7 – Seleção de Atributos
IA004 – Redes Neurais II – Prof. Romis Attux Página 11
Conforme já discutido, a principal estratégia de avaliação de desempenho é recorrer a um
conjunto de validação ou a uma estratégia de validação cruzada. Podem ainda ser criados
elementos que penalizem um número relativamente alto de atributos caso se deseje
enfatizar a busca por configurações parcimoniosas [Holschuh, 2008].
Uma abordagem não-gulosa poderia ser baseada em metaheurísticas populacionais como
algoritmos evolutivos [de Castro, 2006]. Cada configuração de variáveis seria representada
por um cromossomo com alelos binários – a existência de um “1” corresponderia ao uso do
respectivo atributo, e a existência de um “0” corresponderia ao contrário. Usando um
algoritmo genético clássico [de Castro, 2006], ter-se-ia, então, uma população de soluções
que, a cada geração, estaria sujeita a uma dinâmica de aplicação de operadores genéticos e
seleção. O processo de seleção natural seria simulado com o auxílio de uma função de
fitness, que, no caso de problemas de maximização, poderia ser equivalente à função custo
que se deseja otimizar.
Para analisarmos um pouco mais a fundo essa dinâmica, consideremos a Fig. 2 [de Castro e
Von Zuben, 2002]. Nela, temos uma população de indivíduos (cromossomos) que
corresponde ao conjunto de soluções para o problema abordado numa certa geração.
Tópico 7 – Seleção de Atributos
IA004 – Redes Neurais II – Prof. Romis Attux Página 12
A partir desse conjunto, geram-se, com a ajuda de um método de seleção estocástico
denominado “método da roleta” (roulette wheel)1, pares de indivíduos para serem
combinados, com determinada probabilidade, por meio de um operador de crossover. A
aplicação desse operador parte da definição de um “ponto de corte” aleatório – após a
definição desse ponto, faz-se a recombinação dos vetores de bits por meio do intercâmbio
de toda a informação após o ponto.
A seguir, realiza-se uma etapa de mutação, na qual, com uma probabilidade pré-definida,
modificam-se posições aleatoriamente escolhidas dos cromossomos da população. Após a
aplicação dos operadores, passa-se à geração seguinte, repetindo-se o processo até que um
critério de parada seja atingido. A Fig. 2 ilustra os operadores de crossover e mutação em
mais detalhe.
1 No método da roleta, a probabilidade seleção de um indivíduo é diretamente proporcional ao valor de custo (fitness) a ele associado – supondo, como é praxe, que o problema a ser resolvido é de maximização. Portanto, pode-se imaginar o processo de sorteio como sendo realizado por uma roleta com áreas distintas, cada qual proporcional ao fitness do respectivo indivíduo.
Tópico 7 – Seleção de Atributos
IA004 – Redes Neurais II – Prof. Romis Attux Página 13
Figura 2 – Dinâmica de um Algoritmo Genético Clássico [de Castro e Von Zuben, 2002]
Tópico 7 – Seleção de Atributos
IA004 – Redes Neurais II – Prof. Romis Attux Página 14
Referências
[de Castro, 2006] L. N. de Castro, Fundamentals of Natural Computing, CRC Press, 2006.
[de Castro e Von Zuben, 2002] L. N. de Castro, F. J. Von Zuben, Notas de Aula do Curso IA707
– Computação Evolutiva, UNICAMP, 2002.
[Duch, 2006] W. Duch, “Filter Methods”, in I. Guyon et al. (eds.), Feature Extraction:
Foundations and Applications, Springer, 2006.
[Guyon e Elisseeff, 2003] I. Guyon, A. Elisseeff, “An Introduction to Variable and Feature
Selection”, Journal of Machine Learning Research, Vol. 3, pp. 1157 – 1182, 2003.
[Holschuh, 2008] L. M. Holschuh, Contribuições para o Aprendizado por Busca de Projeção,
Dissertação de Mestrado, UNICAMP, 2008.
Recommended