Problemas de generalização

Nesta seção, discute-se os problemas de generalização de classificadores. Tais problemas são muito relevantes no projeto de sistemas de reconhecimento estatístico de padrões, mas que também podem ser comuns a sistemas não estatísticos, como redes neurais. Não importando qual o classificador utilizado, ele deve ser treinado usando os exemplos de treinamento. Como resultado, o desempenho do classificador depende tanto do número de exemplos de treinamento como dos valores específicos dos exemplos, ou seja, da qualidade desses exemplos. Ao mesmo tempo, o objetivo do projeto de um sistema de reconhecimento é classificar futuros exemplos de teste que, preferencialmente, não sejam os mesmos que os de treinamento. Porém, a otimização de um classificador para maximizar seu desempenho no conjunto de treinamento nem sempre produz um bom resultado para o conjunto de testes. A habilidade de generalização de classificadores se refere a seu desempenho ao classificar padrões de teste que não foram utilizados durante o treinamento. Deficiências na capacidade de generalização de um classificador podem ser atribuídas aos seguintes fatores: sobre-ajuste (overfitting), sobre-treinamento (overtraining) e ``maldição da dimensionalidade'' (curse of dimensionality). A seguir encontram-se alguns detalhes a respeito desses fatores.

Sobre-ajuste (ovefitting) Basicamente, há dois problemas que ocorrem se um classificador gerar superfícies de decisão mais complexas do que o requisitado pelo problema que esse aborda. O primeiro, e mais óbvio, é que o custo computacional dos processos de classificação é proporcional à complexidade do sistema classificador utilizado. Assim, se o classificador for mais complexo que o necessário, haverá desperdício de esforço computacional. O outro problema é que um classificador muito complexo possui menos poder de generalização. A complexidade da superfície de decisão de um classificador é proporcional ao número de parâmetros livres que ele possui, ou seja, o número de parâmetros utilizados para a determinação das superfícies de decisão. Intuitivamente pode parecer lógico que, para que um classificador seja poderoso, esse deve construir fronteiras de decisão detalhadas. Mas quando o número de parâmetros livres é grande, o classificador tende a se adaptar a detalhes específicos da base de treinamento, o que pode causar uma redução da taxa de acerto. Esse fenômeno é conhecido como overfitting (sobre-ajuste). Para evitá-lo, é desejável que o classificador seja o mais simples possível, pois assim será dada mais importância às maiores regularidades nos dados e as menores serão ignoradas, pois essas podem ser resultantes de ruídos. Também é possível evitar esse problema aumentando o número de padrões de treinamento do classificador, utilizando padrões que representem o máximo de variações possíveis dos dados. Mas obviamente isso não reduzirá o custo computacional do classificador. Maiores detalhes sobre overfiting podem ser encontrados em [12].

Sobre-treinamento (Overtraining) O problema de sobre-treinamento (overtraining) pode ser observado principalmente em sistemas de redes neurais, mas, de certa forma, também ocorre em sistemas estatísticos. Uma característica em comum com sobre-ajuste é o fato de ambos serem causados pela adaptação do classificador às peculiaridades específicas do conjunto de treinamento. Mas no caso de sobre-treinamento, o problema ocorre quando o classificador é treinado com um conjunto muito grande de exemplos de padrões com pequena variação intra-classe (no caso de classificadores estatísticos) ou com muitas iterações de treinamento (no caso de classificadores neurais). A conseqüência desse fato é que a capacidade de generalização do classificador é reduzida, proporcionando muitas falhas quando esse é utilizado para classificar padrões não pertencentes ao conjunto de treinamento. No caso de redes neurais, esse problema ocorre quando são realizadas muitas iterações de treinamento com pares de entrada e saída. A figura 2 ilustra esse fato.

Figura 2: Curvas ilustrando o efeito de sobre-treinamento (baseada em [12]).

Ainda no caso de redes neurais, uma maneira de evitar overtraining determinar qual é o número ideal do iterações de treinamento. Para isso, pode-se criar um gráfico como o da figura 2 e identificar o ponto de mínimo da curva de erro do conjunto de testes. Mas isso só é possível quando o tamanho do conjunto de treinamento for grande o suficiente. No caso de sistemas estatísticos, uma solução é utilizar, para treinamento, dados que realmente representem todas as possíveis variações entre padrões de mesma classe.

Maldição da dimensionalidade (Curse of dimensionality) e o fenômeno do pico (peaking phenomena) 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 exponencial da dimensão do espaço de características. Um caso ilustrativo em que esse fenômeno ocorre é 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 é segmementada em intervalos regulares. A intercecçã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. Esse é um exemplo de sistema de classificação em que é bastante intuitivo verificar que, para que não sobrem 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. Esse fenômeno é bem conhecido pela comunidade de reconhecimento de padrões. Maiores detalhes podem ser encontrados em [13]. Nos casos em que o número de elementos de treinamento é arbitrariamente grande ou a distribuição estatística das classes é completamente conhecida, a probabilidade de erro de classificação de uma regra de decisão não aumenta com o aumento do número de características consideradas. Porém, nos problemas práticos, observa-se que a adição de características pode prejudicar o desempenho de um classificador se o número de exemplos de treinamento não for 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 da maldição da dimensionalidade e também foi amplamente estudado (por exemplo: [18,19]). Todos os classificadores amplamente utilizados, inclusive redes neurais multi-camadas com retro-alimentação (feed-forward) sofrem da maldição da dimensionalidade.