Aprendizado com Árvores de Decisão
Árvore de Decisão é um dos modelos mais versáteis e populares para aprendizado de máquina em dados tabulares.
Uma Árvore de Decisão é uma representação hierárquica onde cada nó interno representa um teste sobre um atributo e as folhas representam decisões. Ao ser utilizada para classificar um exemplo, inicia-se na raíz e percorre-se um caminho na árvore até chegar em uma folha com a classe. Abaixo está um exemplo de uma árvore de decisão para ajudar a decidir por um tipo de carro.
O exemplo acima é uma aplicação de uma árvore de decisão a um problema de classificação, e é o tipo de aplicação mais comum. Há, porém, adaptações para utilização em problemas de regressão. Também no exemplo mostra-se uma árvore binária, mas árvores de decisão podem ter qualquer número de filhos e número diferente de filhos entre nós internos.
Uma das principais vantagens deste modelo é sua interpretabilidade. Ao contrário, por exemplo, de um classificador linear, a sintaxe do modelo em si existe no mesmo domínio do problema e é facilmente legível e utilizável por leigos e mesmo sem computador. O modelo também é computacionalmente eficiente, realizando inferências rápidas mesmo para um grande número de atributos.
O treinamento de uma árvore de decisão envolve encontrar uma árvore que seja consistente com os exemplos de treinamento. Essencialmente todos algoritmos de treinamento constróem a árvore de cima para baixo, escolhendo um atributo para colocar na raíz e descendo por cada caminho e decidindo por novos atributos a serem testados. Porém, construir uma árvore que classifica os exemplos de forma ótima é um problema NP-Difícil, o que significa que é muito custoso computacionalmente.
Para acelerar o processo de encontrar uma árvore adequada, algoritmos práticos de treinamento fazem uso de suposições sobre o que é uma boa árvore. A suposição mais comum é a de que árvores mais curtas são melhores do que longas. Esta é uma versão da Navalha de Ockham (Occam?), o princípio costumeiramente parafraseado como "a explicação mais simples é a mais provável de ser a correta". Este princípio é costumaz em Aprendizado de Máquina, uma vez que descrever padrões em dados exige menos informação do que descrever os dados em si e, quanto mais compacto, mais forte é o padrão.
Para guiar o processo de construção da árvore em direção a uma árvore curta, os algoritmos de treinamento utilizam diferentes heurísticas. Uma heurística é uma informação utilizada pelo algoritmo para decidir que atributo deve ser testado em cada nó interno.
Para ganhar uma intuição da origem destas heurísticas e de como os algoritmos procedem com a construção das árvores a partir dos dados, vamos desenvolver uma estratégia vencedora para o jogo Cara-a-Cara.
Nesse jogo, dois jogadores escolhem aleatoriamente uma carta com um rosto e nome. O objetivo é adivinhar a carta do jogador oponente fazendo apenas perguntas cujas respostas são sim/não. Por exemplo, pode-se perguntar "a pessoa na sua carta tem bigode?". Para auxiliar, cada jogador tem acesso a um tabuleiro com todos possíveis rostos e nomes. Inicia-se com todos rostos levantados e vai-se abaixando quando se descarta os "suspeitos". Assim, se a resposta a pergunta sobre bigode for "não", se abaixaria todos rostos de pessoas com bigodes. Ao restar apenas um, sabe-se qual é a carta. Ganha quem descobrir primeiro.
Claramente uma boa estratégia é uma que faz o menor número de perguntas possíveis. Por um lado, podemos perguntar algo como "A pessoa na sua carta é a Susan?". Se a resposta for sim, descartamos todos suspeitos de uma única vez. Porém, a probabilidade de ser a Susan é muito baixa (~4%) e o mais provável é que com a resposta descartaremos apenas um suspeito. Se seguirmos esta estratégia, podemos acabar tendo que fazer 24 perguntas no total.
Assim, perguntas devem ser feitas de forma a descartar um grande número de suspeitos a cada pergunta, independente da resposta. Isso é feito fazendo perguntas que dividem os suspeitos aproximadamente pela metade. Olhe o tabuleiro e pense em qual deve ser a primeira pergunta a ser feita.
Uma possibilidade é que, dos 24 rostos, 13 possuem uma boca grande e 11 uma boca pequena. Esta é uma boa candidata a ser a primeira pergunta; descartaremos 13 ou 11 suspeitos dependendo da resposta.
A segunda pergunta, porém, depende da resposta da primeira. Se a pessoa possuir boca grande, a melhor próxima pergunta talvez seja se ela possui cabelo preto (estou chutando). Mas para pessoas de boca pequena, a próxima melhor pergunta pode ser se os olhos são azuis. A cada pergunta tentamos encontrar a característica que divide os suspeitos restantes em dois grupos aproximadamente de mesmo tamanho. Com esta estratégia, nos aproximaremos de log2(24) perguntas, o que resulta em uma média de 4,6 perguntas. No jogo real é necessário ser criativo com a forma das perguntas, porém.
A estratégia desenvolvida para o Cara-a-Cara pode ser adaptada como uma estratégia para construir uma árvore de decisão a partir de dados. O problema é quase idêntico na sua concepção. No problema de aprendizado de máquina, iniciamos com uma tabela com vários exemplos (rostos); cada exemplo possui atributos (características faciais) e um rótulo (nome). A principal diferença é o número de rótulos, que é muito menor do que o número de exemplo em problemas de aprendizado de máquina, enquanto no jogo a relação é um para um.
A construção da árvore procede exatamente como a construção da estratégia para o jogo. Iniciamos na raíz e para cada nó interno nos perguntamos qual é o atributo mais informativo neste momento? Um atributo informativo é o que permite que, se tiveres que chutar um rótulo, tenhas a maior chance de acertar. Um atributo maximamente informativo seria um que divide os rótulos perfeitamente — todos exemplos positivos de um lado, todos negativos do outro (em problemas binários).
Há múltiplas formas para determinar estes atributos. Um dos primeiros algoritmos de aprendizado para árvores de decisão é o ID3 (Iterative Dichotomiser 3), de 1986. Ele utiliza o conceito de ganho de informação para determinar o atributo em cada nó da árvore. Sua operação em alto nível é como segue:
- Iniciando pela raíz, determine o atributo com maior ganho de informação a partir da totalidade dos exemplos
- Para cada valor possível do atributo selecionado, crie um nó filho;
- Para cada filho criado, determine o atributo com o maior ganho de informação para os exemplos que satisfazem as condições até aquele nó;
- Repita a partir de (2) até que todos exemplos restantes tenham o mesmo rótulo ou que todos atributos tenham sido testados;
- Inclua um nó folha ao final de cada caminho contendo o rótulo restante ou o rótulo majoritário nos exemplos restantes.
Importante destacar que no passo 3 os exemplos restantes serão diferentes para cada caminho. Assim como no jogo, dependendo da resposta, removeremos suspeitos diferentes e a próxima pergunta é sempre baseada nos suspeitos restantes. O efeito é que, como no jogo, conforme descemos na árvore, temos incrementalmente menos exemplos disponíveis.
O conceito de ganho de informação é construído matematicamente sobre a definição de entropia. Considerando um problema com apenas dois rótulos (e.g. 0 e 1) e um conjunto de exemplo S, podemos definir p₀ como sendo a fração de exemplos em S com rótulo=0 e p₁ a fração de exemplos em S com rótulo=1 (p₀ + p₁=1). A entropia E do conjunto S é dada então por:
Podemos plotar a entropia variando p₀ de 0.0 a 1.0:
O que observamos é que a entropia é máxima quando p₀ = 0,5 (e, portanto, p₁=0,5 também). Isto é, a entropia é máxima quando a divisão entre as duas classes é perfeita. Por outro lado, a entropia é mínima nos extremos, quando todos exemplos são da mesma classe.
O ganho de informação de um atributo A (com valores possíveis V) sobre um conjunto de exemplos S é a diferença observada na entropia de S ao usarmos A para separar os exemplos. Ele é dado, para um problema binário, por:
Onde p(v) é a proporção de exemplos com valor v no atributo A entre os exemplos disponíveis, e E(v) é a entropia do subconjunto de exemplos que tem o atributo A com valor v.
Assim, para cada nó interno calculamos o ganho de informação para todos atributos possíveis sobre os dados restantes e escolhemos aquele com o maior ganho ou, se a entropia for zero, tomamos uma decisão.
Para ver como entropia e ganho de informação funcionam na prática, acompanhe este notebook.
Ganho de informação e entropia não são as únicas heurísticas para construir árvores de decisão. Por exemplo, o modelo CART utiliza o coeficiente Gini, uma medida também utilizada na Economia para medir desigualdade econômica.
O ID3 apenas lida com atributos e classes categóricas — i.e. apenas se aplica em problemas de classificação com dados categóricos. Porém, ambas restrições podem ser relaxadas com aplicação de diversas técnicas, permitindo que árvores de decisão se apliquem a atributos numéricos e a problemas de regressão.
Por exemplo, o algoritmo C4.5 (e sua versão open source J48) permite a utilização de atributos categóricos, numéricos ou uma mistura dos dois. Para isso, os atributos numéricos são automaticamente particionados em faixas finitas por operadores de comparação (e.g. “X ≤ 3” e “X > 3”). Quando isto é feito, o mesmo atributo pode aparecer mais de uma vez no mesmo caminho da árvore, pois particionamentos com diferentes granularidades podem ser realizadas (o que ocorre no exemplo que segue).
Como para o classificador linear, podemos plotar a superfície de decisão de uma árvore de decisão — isto é, as regiões no espaço de atributos atribuídas para cada classe. Abaixo está um exemplo com dois atributos numéricos e uma árvore limitada a 3 níveis.
Cada nó da árvore cria um separador linear no espaço restrito pelos nós anteriores. Estes separadores são sempre paralelos aos eixos, mesmo para atributos numéricos. Apesar de cada nó ser um separador linear simples, a árvore como um todo cria uma separação não-linear do espaço. Permitindo uma árvore com mais níveis, temos algo como o abaixo.
Quanto mais alta a árvore, mais complexa é a superfície de decisão. Assim, ao contrário do classificador linear, a árvore de decisão tem expressividade variável, podendo se tornar mais expressiva para acomodar problemas mais complexos. Ainda que isto seja algo desejável em geral, sabemos que excessiva expressividade pode trazer um problema: o sobreajuste aos dados.
O sobreajuste (overfitting) ocorre quando o modelo se ajusta excessivamente aos dados de treinamento, perdendo a capacidade de generalizar adequadamente para novos exemplos. Isto ocorre pois os exemplos de treinamento são uma amostra finita e imperfeita do problema e podem conter padrões (ou falta de padrões) espúrios devido a amostragem ou ruído.
Por outro lado, subajuste (underfitting) ocorre quando o modelo não é expressivo o suficiente para capturar as nuances necessárias do problema.
Sobreajuste é um problema tão grande quanto subajuste e encontrar um balanço entre os dois é um dos principais desafios em qualquer tarefa de aprendizado de máquina.
Considere uma tarefa onde os exemplos de treinamento contém um nível de ruído baixo — talvez alguns poucos exemplos possuem rótulo errado. Adotando um algoritmo como ID3 para construir uma árvore de decisão, vemos que os nós mais próximos da raíz utilizam uma grande quantidade de exemplos para escolher os atributos. Neste caso, alguns poucos exemplos ruidosos praticamente não terão efeito pois há muito mais exemplos "corretos". Porém, ao descermos na árvore temos menos exemplos e os ruidosos começam a ter um efeito maior. Uma conclusão dessa linha de pensamento é que exemplos ruidosos afetam primariamente os nós mais próximos das folhas.
Isto leva a uma abordagem para reduzir o sobreajuste de uma árvore treinada: a poda da árvore. Na sua forma mais simples, elencamos um conjunto de validação contendo exemplos que não fazem parte do conjunto de treinamento. Então, construímos a árvore usando os exempos de treinamento e, com a árvore completa, iniciamos o processo de poda.
Começando por algum nó interno mais baixo (próximo das folhas), removemos o nó e substituímos por uma decisão dada pela classe majoritária nos exemplos disponíveis naquele nó. Então, testamos esta nova árvore no conjunto de validação e, se o resultado for superior ao da árvore original, mantemos a alteração e fazemos o mesmo para outro nó até que todos nós tenham sido considerados. Do contrário, se o resultado for inferior, restauramos o nó removido e consideramos outro nó.
Este método simples de poda é também conhecido por substituição de subárvore, pois toda a subárvore é substituída por uma folha. Diversas outras alternativas existem. O C4.5, por exemplo, utiliza o conceito de elevação de subárvore, ou enxerto de subárvore. Nele, um nó interno é substituído por toda uma subárvore que ocorre mais para baixo deste nó. Outra alternativa é realizar pré-poda, onde paramos o crescimento da árvore segundo algum critério.
Todos métodos de poda são instâncias de regularização de modelo. Métodos de regularização são técnicas aplicadas para introduzir informação adicional sobre parâmetros desejáveis, com a intenção de reduzir o sobreajuste do modelo. Usualmente são técnicas que visam reduzir a complexidade do modelo, o que acontece na poda de árvores de decisão, mas nem sempre é o caso.
Enquanto a escolha do modelo faz suposições sobre a natureza do problema e o que deve ser representado (e.g. o classificador linear supõe que o problema é linearmente separável), a regularização faz suposições sobre que hipóteses devem ser avaliadas. Isto é, ela opera no algoritmo de treinamento do modelo.
Regularização é frequentemente utilizada para diferentes modelos e é uma parte integral do pipeline de aprendizado de máquina. É importante para modelos expressivos e tem ganho especial atenção nos últimos anos devido a redes neurais profundas, que podem ser muito expressivas.
