DSC/CCT/UFCG

Inteligência Artificial IInteligência Artificial I

Aprendizagem Aprendizagem (Parte II)(Parte II)

Prof.Prof.aa Joseana Macêdo Fechine Joseana Macêdo Fechine joseana@dsc.ufcg.edu.brjoseana@dsc.ufcg.edu.br

Carga Horária: 60 horas

Universidade Federal de Campina GrandeUniversidade Federal de Campina GrandeDepartamento de Sistemas e Computação Departamento de Sistemas e Computação

Curso de Bacharelado em Ciência da Curso de Bacharelado em Ciência da ComputaçãoComputação

2

DSC/CCT/UFCG

Aprendizagem

Tópicos

Aprendizagem Árvores de decisão

3

DSC/CCT/UFCG

INDUÇÃO por ÁRVORES de DECISÃO Indução mediante árvores de decisão - uma das

formas mais simples de algoritmos de aprendizagem e também de muito sucesso.

Entrada: um objeto ou situação descrito por um conjunto de propriedades ou atributos;

Saída: uma decisão.

Árvore de decisão: formada por um conjunto de nós de decisão, perguntas, que permitem a classificação de cada caso.

4

DSC/CCT/UFCG

INDUÇÃO por ÁRVORES de DECISÃO

Aprendizagem de uma árvore de decisão com exemplos:

Situações em que se têm exemplos previamente classificados com regras desconhecidas que se pretendem aprender (descobrir).

Essas classificações podem ter sido feitas por um especialista que queremos imitar ou traduzir em medidas difíceis ou caras de obter (por exemplo, medidas realizadas por testes destrutivos).

Pode-se substituir o especialista por uma árvore de decisão.

Aprendizagem, Estimação, Treinamento: Partindo de exemplos, "adivinhar" a árvore.

Árvore de Decisão: Conjunto de “nós de decisão” e “folhas” que implementam um modelo de classificação.

5

DSC/CCT/UFCG

INDUÇÃO por ÁRVORES de DECISÃO

A partir de um conjunto de propriedades, decide sim ou não.

Representação de árvores de decisão Cada nó interno testa um atributo Cada ramo corresponde a um valor do atributo Cada folha atribui uma classificação

6

DSC/CCT/UFCG

INDUÇÃO por ÁRVORES de DECISÃO Exemplo - descrito pelos valores dos atributos e o

valor do predicado meta.

Valor do predicado meta - chamado classificação do exemplo.

Se o predicado meta é verdadeiro para algum exemplo, tem-se o exemplo positivo, caso contrário exemplo negativo.

O conjunto completo de exemplos é chamado conjunto de treinamento.

7

DSC/CCT/UFCG

Expressividade de árvores de decisão Qualquer função booleana pode ser escrita como

uma árvore de decisão.

8

DSC/CCT/UFCG

O problema com a Ad trivial Algoritmo de aprendizagem em árvore de decisão

(Ad):

A idéia é testar o atributo mais importante – aquele que faz a maior diferença para a classificação de um exemplo.

Obter a classificação correta com pequeno nº de testes = caminhos curtos e árvore pequena.

Limitação: A árvore memoriza as observações. Ela não extrai qualquer padrão dos exemplos e, assim, não podemos esperar que ela esteja apta a extrapolar para exemplos não vistos antes.

9

DSC/CCT/UFCG

Expressividade de árvores de decisão

Árvores de decisão servem para alguns tipos de funções e não são boas para outros.

Infelizmente, não existe uma espécie de representação que seja eficiente para todos os tipos de funções.

10

DSC/CCT/UFCG

INDUÇÃO por ÁRVORES de DECISÃO

EXEMPLO no domínio do restaurante: O objetivo é aprender uma definição para o predicado

meta Esperará, em que a definição é expressa como uma árvore de decisão.

Clientes?

Bar?

Sex/Sab?Reserva?

Faminto?Alternativa?

EsperaEstimada?

Chovendo?

NãoNão

Não

Não

Não

SimSimSim

Sim

Sim

Sim

Alternativa?

SimSim

Nenhum alguns cheio

>60 30-60 10-30 0-10

Não Sim Não Sim

Não Sim Não Sim Não Sim

Não Sim Não Sim

Clientes?

Bar?

Sex/Sab?Reserva?

Faminto?Alternativa?

EsperaEstimada?

Chovendo?

NãoNão

Não

Não

Não

SimSimSim

Sim

Sim

Sim

Alternativa?

SimSim

Nenhum alguns cheio

>60 30-60 10-30 0-10

Não Sim Não Sim

Não Sim Não Sim Não Sim

Não Sim Não Sim

11

DSC/CCT/UFCG

Exemplo: Esperar ou não uma mesa em um restaurante?

Atributos disponíveis: Alternativa: há um outro restaurante apropriado por perto? Bar: o restaurante tem uma área de bar confortável para

esperar? Sex/Sab: verdadeiro às sextas e sábados Faminto: Estamos com fome? Clientes: Quantas pessoas estão no restaurante? Preço: A faixa de preços do restaurante Chovendo: Está chovendo do lado de fora? Reserva: Fizemos uma reserva? Tipo: Qual o tipo do restaurante? Espera estimada: A espera estimada pelo gerente

Exemplo Restaurante ...

12

DSC/CCT/UFCG

Exemplo Restaurante ...

Clientes?

Bar?

Sex/Sab?

Reserva?

Faminto?

Alternativa?

EsperaEstimada?

Chovendo?

Não

Não

Não

Não

Não

SimSimSim

Sim

Sim

Sim

Alternativa?

SimSim

Nenhum alguns cheio

>60 30-60 10-30 0-10

Não Sim Não Sim

Não Sim Não Sim Não Sim

Não Sim Não Sim

13

DSC/CCT/UFCG

Expressividade de árvores de decisão Qualquer hipótese de árvore de decisão específica para o

predicado meta VaiEsperar pode ser vista como uma asserção da forma:

∀s VaiEsperar(s) (P1(s) v P2(s) v ... v Pn(s))

Cada condição Pi(s) é uma conjunção de testes que pode corresponder a um caminho da raiz até uma folha da árvore com resultado positivo.

A árvore pode ser representada por uma conjunção de implicações individuais que correspondem aos caminhos que vão da raiz até o nó folha Sim.

14

DSC/CCT/UFCG

Expressividade de árvores de decisão

Não é possível utilizar árvores de decisão para representar testes que se referem a dois ou mais objetos diferentes

∃ r2 Perto(r2, r) ^ Preço(r, p) ^ Preço(r2, p2) ^ MaisBarato(p2, p)

15

DSC/CCT/UFCG

Ex Alt Bar Sex Fam Cli Pre Chu Res Tipo Tem Meta

X1 Sim Não Não Sim Alg $$$ Não Sim Fra 0-10 Sim

X2 Sim Não Não Sim Che $ Não Não Tai 30-60 Não

X3 Não Sim Não Não Alg $ Não Não Ham 0-10 Sim

X4 Sim Não Sim Sim Che $ Sim Não Tai 10-30 Sim

X5 Sim Não Sim Não Che $$$ Não Sim Fra >60 Não

X6 Não Sim Não Sim Alg $$ Sim Sim Ita 0-10 Sim

X7 Não Sim Não Não Ne $ Sim Não Ham 0-10 Não

X8 Não Não Não Sim Alg $$ Sim Sim Tai 0-10 Sim

X9 Não Sim Sim Não Che $ Sim Não Ham >60 Não

X10 Sim Sim Sim Sim Che $$$ Não Sim Ita 10-30 Não

X11 Não Não Não Não Ne $ Não Não Tai 0-10 Não

X12 Sim Sim Sim Sim Che $ Não Não Ham 30-60 Sim

Conjunto de treinamento para o exemplo do restaurante

16

DSC/CCT/UFCG

Aplicação do algoritmo de aprendizagem

Meta Sim 1 3 4 6 8 12Não 2 5 7 9 10 11

alternativa?

1 4 122 5 10

3 6 87 9 11

sim não

Ex Alt Bar SexX1 Sim Não Não

X2 Sim Não Não

X3 Não Sim Não

X4 Sim Não Sim

X5 Sim Não Sim

X6 Não Sim Não

X7 Não Sim Não

X8 Não Não Não

X9 Não Sim Sim

X10 Sim Sim Sim

X11 Não Não Não

X12 Sim Sim Sim

Bar?

3 6 127 9 10

1 4 82 5 11

sim não

Sex/Sab?

4 125 9 10

1 3 6 82 7 11

sim não

17

DSC/CCT/UFCG

Casos a considerar na escolha de um novo atributo Se existem alguns exemplos positivos e alguns negativos,

escolha o melhor atributo para dividi-los;

Se todos os exemplos restantes forem positivos (ou negativos), terminamos;

Se não resta nenhum exemplo, nenhum exemplo deste tipo foi observado, retornamos a maioria do nó pai;

Não resta nenhum atributo mas há exemplos positivos e negativos – descrições iguais com classificações diferentes = ruído nos dados.

19

DSC/CCT/UFCG

Árvore resultante da aplicação do algoritmo

Clientes?

Faminto?

Não

Sim

Tipo?

Nenhum alguns cheio

Não

Sim Não

SimSex/sab?

Não

Sim

Não Sim

Fra Ita Tai Ham

Não Sim

O algoritmo poderia encontrar uma Ad diferente para o mesmo conjunto de treinamento?

Qual seria?

20

DSC/CCT/UFCG

A árvore resultante É diferente da árvore original.

Mas a hipótese concorda com todos os exemplos.

E é consideravelmente mais simples do que a árvore original.

Chovendo e Reserva ficaram de fora porque a árvore não necessita destes para classificar os exemplos.

Mas nunca viu um caso de espera de 0-10 min e o restaurante cheio Para um caso no qual faminto é falso a Ad informa que não

devemos esperar.

21

DSC/CCT/UFCG

Escolha de testes de atributos Esquema de aprendizagem da Ad

Projetado para minimizar a profundidade da árvore final

Idéia: escolher o atributo que melhor fornece uma classificação exata dos exemplos

Atributo perfeito: divide os exemplos em conjuntos que são todos positivos ou todos negativos Clientes não é perfeito, mas é “bastante bom”

Atributo inútil: deixa os conjuntos de exemplos com a mesma proporção do conjunto original Tipo é um atributo “realmente inútil”

22

DSC/CCT/UFCG

O algoritmo de aprendizagem É um bom algoritmo se ele produz hipóteses que

classificam (predizem) bem exemplos ainda não vistos

A predição é boa se ela se torna verdadeira

Como avaliar a qualidade de uma hipótese? Podemos checar sua previsão com uma

classificação correta que já conhecemos Conjunto de exemplos conhecidos = conjunto de

testes

23

DSC/CCT/UFCG

Metodologia para avaliação de desempenho de um algoritmo1. Coletar um grande conjunto de exemplos

2. Dividi-lo em dois conjuntos disjuntos Conjunto de treinamento e conjunto de teste

3. Aplicar o algoritmo ao conjunto de treinamento, gerando uma hipótese h

4. Medir a quantidade de exemplos do conjunto de teste classificados corretamente por h

5. Repetir as etapas 2 a 4 para Diferentes tamanhos de conjuntos de treinamento Diferentes conjuntos de treinamento de cada tamanho

24

DSC/CCT/UFCG

Curva de aprendizagem

É traçada com o conjunto de dados obtidos da metodologia anterior.

Conjunto de treinamento aumenta => qualidade da previsão aumenta.

Bom sinal de que existe um padrão nos dados e o algoritmo está capturando este padrão.

25

DSC/CCT/UFCG

Curva de aprendizagem

Observação: É um bom sinal de que existe realmente algum padrão nos dados e de que o algoritmo de aprendizagem o está incorporando.

Curva de aprendizagem para o algoritmo de árvore de decisão sobre 100 exemplos gerados aleatoriamente no domínio do restaurante. O gráfico resume 20 testes.

26

DSC/CCT/UFCG

Problemas gerais: overfitting Overfitting (hiper-especialização):

Evitar encontrar uma “regularidade” muito restrita nos dados

Soluções: validação cruzada poda

27

DSC/CCT/UFCG

Treinamento Teste

Validação Cruzada Serve para evitar overfitting e para averiguar robustez dos

resultados Algoritmo

1) Divide o conjunto de exemplos em dois sub-conjuntos: conjuntos de treinamento (TR) e de teste (TE)

2) Usa indução para gerar hipótese H sobre TR3) Mede percentagem de erro de H aplicada à TE4) Repete passos 1-3 com diferentes tamanhos de TE e TR, e

tendo elemento escolhidos aleatoriamente

28

DSC/CCT/UFCG

Exemplos Práticos Exemplos:

Diagnóstico médico e de equipamentos Análise de crédito Recuperação de Informação GASOIL

Sistema de separação de gás-óleo em plataformas de petróleo.

Piloto automático de um Cessna Treinado por três pilotos; Obteve um desempenho melhor do que os três.