Fundamentos de IA: Árvores, Redes Neurais e Algoritmos Genéticos

Fundamentos de Inteligência Artificial

Árvores de Decisão

Vantagens

• Fáceis de implementar
• Permitem extrair regras claras
• Não incrementais (mais eficientes e práticas, sem backtracking)

Desvantagens

• Função objetivo deve ser discreta
• Principalmente para problemas de classificação

Critérios de Parada

• Todos os exemplos pertencem à mesma classe
• Todos os exemplos têm o mesmo valor dos atributos
• O ganho em cada partição for insignificante
• O número de exemplos atingiu um certo limite

Problema de Overfitting

Se o número de nós for muito grande, as decisões são tomadas com base em partições muito pequenas dos exemplos, o que diminui a generalização.

Fórmulas

• Entropia (Ent(S)): Ent(S) = -(p+ * log2p+) - (p- * log2p-), onde S é o conjunto de exemplos para aquele nó, p+ é a probabilidade de saídas positivas e p- é a probabilidade de saídas negativas.
• Informação (Info(A)): Info(atributo A) = Σ(p(vi) * Ent(vi)), onde p(vi) é a probabilidade do valor i (número de exemplos com valor i / número total de exemplos).
• Ganho de Informação (Ganho-info(S, A)): Ganho-info(S, A) = Ent(S) - Info(A).

Algoritmo

1. Escolha o atributo que melhor divide os exemplos.
2. Expanda a árvore criando um novo ramo para cada valor do atributo escolhido.
3. Passe os exemplos para cada nó de acordo com o valor do atributo.
4. Repita para cada folha até alcançar o critério de parada:
   1. Se todos os exemplos pertencem à mesma classe, atribua o nó à classe.
   2. Senão, repita os passos 1 a 4.

Função Recursiva geraArvore(Exs)

1. Se Exs atende a algum critério de parada, retorne uma folha.
2. Senão, escolha o melhor atributo para dividir Exs e crie um nó associado ao atributo.
3. Para cada valor i do atributo escolhido, faça arvore_i = geraArvore(Exs_i).
4. Retorne a subárvore gerada tendo como descendentes arvores_i.
5. Fim.

Redes Neurais

Principais Características (Vantagens)

• Capacidade de se adaptar e aprender
• Capacidade de generalizar
• Capacidade de classificar
• Usadas principalmente em problemas de classificação, categorização, otimização e aproximação
• Implementação rápida e simples

Perceptron

Fórmulas

• Erro: Erro = (saída desejada - saída da rede)
• Ajuste de Peso: Δw = η * xi * Erroi
• Atualização de Peso: Wij(t + 1) = wij(t) + Δw

MLP (Multi-Layer Perceptron)

Fórmulas

• Erro (Quadrático): Erro = 1/2 Σ(saída desejada - saída da rede)2
• Ajuste de Peso: Δwij = η * xi * δ, onde δ é:
  • (saída desejada - saída da rede) * f'(net) se for nó de saída
  • (Σδda camada seguinte * w(peso entre o neurônio atual e o da camada seguinte)) * f'(net) para nós ocultos

Critérios de Parada

• Número máximo de iterações
• Erro em treinamento < mínimo escolhido
• Erro aumenta por k vezes consecutivas na etapa de validação

Algoritmos Genéticos

Fórmula de Normalização do Vetor de Entrada

X = min + (Max - min) * valor_base_10 / (2número_de_bits - 1)

Critérios de Parada

• Não houve melhoria na aptidão
• A melhor solução foi encontrada (se conhecida)
• Perda de diversidade
• Número máximo de gerações alcançado