O Problema da Dimensionalidade

O problema da dimensionalidade, também conhecido como curse of dimensionality e como comportamento de curva em U, é um fator muito relevante para decidir-se a dimensionalidade ideal a ser adotada em um problema de reconhecimento de padrões. Trata-se do seguinte fenômeno: o número de elementos de treinamento requeridos para que um classificador tenha um bom desempenho é uma função monotonicamente crescente da dimensão do espaço de características. Em alguns casos (mas não necessariamente em todos), pode-se mostrar que essa função é exponencial, ou seja, $\vert T\vert \Leftrightarrow O(e^N)$ [Jain et al., 2000]. Um exemplo é o da técnica de particionamento do espaço de características para classificação baseada em árvores de decisão. Nessa técnica, cada reta suporte dos vetores da base do espaço de características é segmentada em intervalos regulares. A interseção entre esses intervalos forma células no espaço. O reconhecimento de padrões é feito através da associação de uma classe a cada célula, de acordo com a classe majoritária nas células. Esse é um exemplo de sistema de classificação em que é bastante intuitivo verificar que, para que não hajam células com classificação indefinida, é necessário que o número de elementos de treinamento seja uma função exponencial da dimensão do espaço de características. Isso ocorre devido ao fato de que, em reconhecimento estatístico de padrões, o volume do espaço de característica cresce exponencialmente com a dimensionalidade [Perlovsky, 1998]. Esse fenômeno é bem conhecido pela comunidade de reconhecimento de padrões (ver também [Jain et al., 2000] para um exemplo mais formal). Quando é utilizado um classificador Bayesiano, nos casos em que o número de elementos de treinamento é arbitrariamente grande ou a função densidade de probabilidade das classes ( $p({\bf x}\vert\omega_i), i=1, \cdots, c$) for completamente conhecida, a probabilidade de erro de classificação de uma regra de decisão não aumenta com o número de características consideradas. Porém, nos problemas práticos, para um conjunto de treinamento finito, observa-se que a adição de características pode prejudicar o desempenho de um classificador (se não forem adicionados exemplos de treinamento). Isso ocorre quando o número de exemplos de treinamento não é grande o suficiente em relação ao número de características. Esse fenômeno, chamado fenômeno do pico (peaking phenomena), é uma conseqüência do problema da dimensionalidade, tendo também sido amplamente estudado (por exemplo, [Campos et al., 2000d,Belhumeur et al., 1997]). Todos os classificadores comumente utilizados podem sofrer de problema da dimensionalidade. Apesar de ser teoricamente clara a relação entre a dimensionalidade e o tamanho do conjunto de treinamento ( $\vert T\vert \Leftrightarrow e^N$), há outros fatores que, quando considerados, ofuscam a exatidão dessa relação, tais como a complexidade do classificador e o número de classes. Segundo [Jain et al., 2000], resultados empíricos fazem com que, geralmente, seja aceita a seguinte relação: $\vert T_i\vert \Leftrightarrow 10 \cdot N$, $i = 1, \cdots, c$, sendo $\vert T_i\vert$ o número de exemplos de treinamento da classe $i$. Ou seja, no mínimo deve-se utilizar um número de exemplos de treinamento por classe dez vezes maior que a dimensionalidade.

.8problema_dist_prot.eps Exemplo de problema em que o uso de uma dimensão é melhor que o uso de duas.

Para mostrar que o problema da dimensionalidade não depende exclusivamente do número de padrões utilizados no processo de treinamento, criamos a figura 2.2. Nesta figura há um problema de classificação com duas classes cujas distribuições estão mostradas através das formas que circundam as letras que identificam tais classes. Esse espaço de características possui dimensão 2 e os vetores de sua base estão indicados por $F_1$ e $F_2$. Supomos que a distribuição dessas classes faz com que o protótipo de cada classe fique nas posições indicadas por $p_A$ e $p_B$. Assim, caso seja utilizado um classificador de mínima distância ao protótipo, a fronteira de decisão criada divide o espaço de características no lugar geométrico indicado pela linha tracejada. Podemos notar que a taxa de erro desse classificador não será pequena. Por outro lado, se for utilizada somente a característica $F_1$, podemos notar que a projeção dos padrões e do protótipo nessa característica fará com que a taxa de erro seja praticamente nula, pois a fronteira de decisão será o ponto $0$. Esse problema ocorre mesmo que sejam utilizados conjuntos de treinamento grandes, pois ele decorre de uma deficiência do classificador, e não do número de padrões de treinamento. Essa deficiência decorre do fato de que o classificador de mínima distância ao protótipo com distância Euclidiana não estima a fronteira de decisão com precisão quando a distribuição das classes não é circular.

.25curse_of_dimensionality.ps Efeito do problema da dimensionalidade.

A curva apresentada a figura 2.3, a qual ilustra o problema da dimensionalidade, apresenta três regiões no eixo da dimensionalidade com significados diferentes:

1. Na primeira região, compreendida entre $0$ e $m_1$, ocorre o comportamento mais esperado intuitivamente, pois a adição de características promove redução na taxa de erro. Isso deve-se ao fato de espaços com dimensões muito pequenas não possuírem informações suficientes para distinguir-se as classes de padrões. Com isso, a adição de novas características melhora os resultados de classificação.
2. A segunda região é aquela em que é atingida uma estabilidade na taxa de acerto. Nessa região, a adição ou eliminação de características não altera (ou altera muito sutilmente) essa taxa. Para um problema de classificação, a melhor solução está na adoção da dimensionalidade $m_1$, pois esse é o menor valor em que a taxa de acerto é máxima. A estabilização na taxa de acerto se deve ao fato de que as características importantes para se distinguir os padrões já foram inseridas na região anterior, e as características extras não são nem ruidosas nem relevantes para a classificação.
3. A última região é a região em que de fato ocorre o problema da dimensionalidade. Note que o aumento no número de características provoca aumento na taxa de erro.

Assim, para obter-se o desempenho máximo de um classificador, é necessário investigar qual é a dimensionalidade ideal para um determinado problema de reconhecimento de padrões. Para isso, pode ser aplicada uma estratégia simples de tentativa e erro em relação à dimensionalidade, usando um método de redução de dimensionalidade (incluindo extração e seleção de características) até que o ponto de máximo desempenho de um classificador seja atingido. Nessa estratégia, são realizados testes de redução de dimensionalidade para a obtenção de sub-espaços de características de vários tamanhos diferentes, até que seja obtida a dimensionalidade que minimiza o erro de classificação. O próximo capítulo apresenta mais detalhes sobre métodos de redução de dimensionalidade. Outros detalhes sobre os problemas de generalização podem ser encontrados em [Theodoridis and Koutroumbas, 1999,Jain et al., 2000].