Universidade Federal de Campina Grande
Departamento de Sistemas e Computação
Curso de Bacharelado em Ciência da Computação
Inteligência Artificial I
Aprendizagem
(Parte II)
Prof.a Joseana Macêdo Fechine
[email protected]
Carga Horária: 60 horas
DSC/CCT/UFC
G
Aprendizagem
Tópicos

Aprendizagem

Árvores de decisão
2
DSC/CCT/UFCG
INDUÇÃO por
ÁRVORES de DECISÃO
DSC/CCT/UFCG

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.
3
INDUÇÃO por
ÁRVORES de DECISÃO

Aprendizagem de uma árvore de decisão com
exemplos:



DSC/CCT/UFCG
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.
4
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
5
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.
6
DSC/CCT/UFCG
Expressividade de árvores de
decisão

Qualquer função booleana pode ser escrita como
uma árvore de decisão.
7
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.
8
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.
9
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?
Nenhum
Não
alguns
Sim
cheio
EsperaEstimada?
>60
30-60
Não
Alternativa?
Não
Reserva?
Não
Sim
Bar?
Não
Não
Sim
Sim
Sim
Sex/Sab?
Não
0-10
Sim
Faminto?
Sim
Não
10-30
Não
Sim
Sim
Alternativa?
Sim
Não
Sim
Sim
Sim
Chovendo?
Não
Sim
Não
Sim
10
DSC/CCT/UFCG
Exemplo
Restaurante ...

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
11
DSC/CCT/UFCG
Exemplo
Restaurante ...
Clientes?
Nenhum
Não
alguns
Sim
cheio
EsperaEstimada?
>60
30-60
Não
Alternativa?
Não
Reserva?
Não
Sim
Bar?
Não
Não
DSC/CCT/UFCG
Sim
Sim
Sim
Sex/Sab?
Não
0-10
Sim
Faminto?
Sim
Não
10-30
Não
Sim
Sim
Alternativa?
Sim
Não
Sim
Sim
Sim
Chovendo?
Não
Sim
Não
Sim
12
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.
13
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)
14
DSC/CCT/UFCG
Conjunto de treinamento para o exemplo do restaurante
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
Sim15
DSC/CCT/UFCG
Aplicação do algoritmo de
aprendizagem
DSC/CCT/UFCG
alternativa?
Ex Alt
Bar
Sex
Meta
X1
Sim
Não
Não
Sim
1 3 4 6 8 12
sim
X2
Sim
Não
Não
Não
2 5 7 9 10 11
X3
Não
Sim
Não
1 4 12
3 6 8
X4
Sim
Não
Sim
2 5 10
7 9 11
X5
Sim
Não
Sim
X6
Não
Sim
Não
X7
Não
Sim
Não
X8
Não
Não
Não
sim
X9
Não
Sim
Sim
X10 Sim
Sim
Sim
X11 Não
Não
Não
X12 Sim
Sim
Sim
não
Bar?
Sex/Sab?
não
sim
não
4 12
1 3 6 8
3 6 12
1 4 8
5 9 10
2 7 11
7 9 10
2 5 11
16
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.
17
DSC/CCT/UFCG
Árvore resultante da
aplicação do algoritmo
Clientes?
Nenhum
Não
alguns
cheio
Sim
Faminto?
Não
Sim
Não
Tipo?
Fra
Sim
O algoritmo poderia
encontrar uma Ad diferente
para o mesmo conjunto de
treinamento?
Ita
Não
Qual seria?
Tai
Ham
Sex/sab?
Sim
Não
Sim
Não
Sim
19
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.
20
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”
21
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
22
DSC/CCT/UFCG
Metodologia para avaliação de
desempenho de um algoritmo
1. 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
23
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.
24
DSC/CCT/UFCG
Curva de aprendizagem
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.
Observação: É um bom sinal de que existe realmente algum padrão nos
dados e de que o algoritmo de aprendizagem o está incorporando.
DSC/CCT/UFCG
25
Problemas gerais: overfitting

Overfitting (hiper-especialização):


Evitar encontrar uma “regularidade” muito restrita nos dados
Soluções:


validação cruzada
poda
26
DSC/CCT/UFCG
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 TR
3) Mede percentagem de erro de H aplicada à TE
4) Repete passos 1-3 com diferentes tamanhos de TE e TR, e
tendo elemento escolhidos aleatoriamente
Treinamento
Teste
27
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.

28
DSC/CCT/UFCG