Aprendizado de Máquinas
Aprendendo de Observações
Critica
Sensores
Feedback
Performance
Aprendizado
Objetivos de aprendizado
Gerador
Efectores
Modelo de Aprendizado
A
M
B
I
E
N
T
E
Aprendizado
"
"
A percepção pode ser usada para atuar e para
melhorar a habilidade do agente no futuro.
O aprendizado ocorre como resultado da
interação do agente e o mundo, e das
observações deste agente.
Pesquisas em Aprendizado
"
"
Que componentes do elemento de
performance devem ser melhorados.
Que representação é usada para estes
componentes.
"
Que feedback esta disponivel.
"
Que informação a priori esta disponivel.
Componentes de Performance
"
Mapeamento do estado corrente para ações.
"
Um meio de inferir propriedades do mundo.
"
Informações de como o meio evolue
"
Informações das consequências das ações do
agente
"
Estados desejaveis do mundo
"
Objetivos para atingir determinados estados.
Representação do componente
• Diferentes formas de representar
conhecimento levam a diferentes métodos de
aprendizado.
• Ex: redes neurais, algoritmos géneticos,
formulas lógicas....
Feedback Disponivel
• E, S ; aprendizado supervisionado
• E, ~S ; aprendizado reforçado
• E ;
aprendizado não supervisionado
Aprendizado Inductivo
F(x)
X
F(X)
Aprendizado Inductivo
• Assumindo que o sistema é modelado por um
uma função f, desconhecida;
• Dado uma coleção de exemplos de f, retornar
a função h que se aproxima a f, a função h é
denominada hipoteses.
Bias
Tarefa de Classificação
Árvores de Decisão
País
Alemanha
Não
Inglaterra
França
Sim
Idade
< 25
Sim
> 25
Não
Árvores de Decisão
• Classificação; baseado num conjunto de
atributos
• Cada nó interno corresponde a um teste sobre
os valores dos atributos;
• Os arcos são rotulados com os valores
possiveis do teste;
• Cada folha na árvore especifica a
classificação.
Esperar por uma mesa num
restaurante
• Decidir que propriedades ou atributos estão
disponiveis para descrever os exemplos do
dominio;
• Existem alternativas?, existe um bar no
local?, dia da semana, estado da fome, estado
do restaurante, preço, chuva, reserva, tipo de
comida, tempo de espera....
Esperar por uma mesa?
Estado rest.
Cheio
Medio
Vazio
Não
Sim
Não
30-60
Alternati
va
Reservas
Não
Não
Não
Sim
Sim
Sim
Sim
Não
0-10
Sim
Fome
Sim
Não
Sim
Dia
Sim Semana
Bar
Não
Esper
a
>60 10-30
Final
Sim
Alternat.
Não
Sim
Sim
Não
Não
Chove
Sim
Sim
Expressividade das Árvores de
decisão
• Conjunto de implicações: da raiz até uma folha
• ex:
r Estado(r,cheio) Espera(r,0-10) 
fome(r,não) => Esperar.
• As árvores de decisão estão limitadas a falar de um
objeto único.
• Linguagem proposicional, cada teste num atributo é
uma proposição
  rr, Perto(rr,r),Preço(r,p),Preço(rr,pp),Menor(pp,p)
Inducindo Árvores a partir de
Exemplos
• Um exemplo é descrito pelo valor dos atributos e o
valor do predicado objetivo (classificação).
• Solução trivial; uma folha para cada exemplo;
• memorização das observações sem extrair padrão
• Extrair padrões significa descrever um grande
número de casos de uma maneira concisa.
• Ockham Razor: A melhor hipoteses é a mais
simples consistente com todas as observações.
Indução de Árvores
• Encontrar a árvore de decisão menor é um problema
intratavel;
• Solução: Heuristicas simples, boas árvores
• Ideia básica
• Testar o atributo mais importante primeiro
• Separar o maior número de casos, a cada vez.
• Classificação correta com o menor número de teste.
Indução de Árvores
• Uma árvore de decisão é construída de forma
"top-down", usando o princípio de dividirpara-conquistar.
• Inicialmente, todas as tuplas são alocadas à
raiz da árvore.
• Selecione um atributo e divida o conjunto.
• Objetivo- separar as classes
• Repita esse processo, recursivamente.
Conjunto de Treinamento
Seleção do Atributo
+ 1 3 4 6 8 12
- 2 5 7 9 10 11
Vazio
Medi
+ 1 3o
68
+
- 7 11
-
+1 3 4 6 8 12
-2 5 7 9 10 11
F
+1
-5
I
+6
- 10
Estad
o
Cheio
+ 4 12
- 2 5 9 10
Tipo
B
T
+48
- 2 11
+ 3 12
-79
+ 1 3 4 6 8 12
- 2 5 7 9 10 11
Vazio
+
- 7 11
Estado
Medio
+1368
-
Cheio
+ 4 12
Fome
- 2 5 9 10
Sim
+ 4 12
- 2 10
Não
+
- 59
Algoritmo
Árvore Gerada
Estado
Vazio
Medio
Não
Sim
Cheio
Fome
Sim
Não
Não
Tipo
F
I
Sim
Não
B
T
Sim
sex/sab
Não
Não
Sim
Sim
Árvore
• Os dados do exemplo foram gerados com a
árvore inicial;
• A árvore gerada é diferente da original;
• O algoritmo olha os exemplos!!!;
• Performance do algoritmo: é bom se produz
uma hipoteses que é boa para predizer a
classificação de exemplos não vistos
anteriormente. Conjunto de teste.
Métodologia de Aprendizado
• Colecione um conjunto grande de exemplos;
• Divida em 2 conjuntos disjunto:
– conjunto de treinamento
– conjunto de teste
• Use o algoritmo de aprendizado com o conj.
treinamento para gerar a hipoteses H.
• Calcule a percentagem de exemplos no conjunto de
teste que estão corretamente classificados por H.
• Repita os passos 2 a 4 para diferentes conjuntos
Conjunto de treinamento
• O resultado é um conjunto de dados que pode
ser processado para dar a media da qualidade
da predição.
Curva de Aprendizado
% de corretos no conjunto de teste
100
Tamanho do conjunto de treinamento
Uso pratico de Árvores
• Lógica proposicional
• Tomada de decisões, classificação de objetos
• Planos de vôos
• Equipamentos para separação de gasolina e
oleo.
Teoria da Informação
• Escolha do melhor atributo?
• Árvore de profundidade mínima
• Atributo perfeito divide os exemplos em
conjuntos que são + e -.
– ex: estado do restaurante x tipo de restaurante
• Quantidade de informação esperada de cada
atributo (Shanon & Weaver, 1949).
Teoria da Informação
• Dada uma situação na qual há N resultados
alternativos desconhecidos, quanta informação você
adquire quando você sabe o resultado?
– Resultados equiprováveis:
– Lançar uma moeda, 2 resultados, 1 bit de informação
– 1 ficha dentre 8, 8 resultados, 3 bits de informação
– 1 ficha dentre 32, 32 resultados, 5 bits de informação
– N resultados equiprováveis: Info = log2N bits
Teoria da Informação
• Probabilidade de cada resultado p=1/N,
– Info = - log2 p bits
• Resultados não equiprováveis:
– ex: 128 fichas, 127 pretas e 2 branca. É quase certo que o
resultado de extrair uma ficha será uma ficha preta.
• Existe menos incerteza removida, porque há menos
dúvida sobre o resultado.
Função de Shannon
• Info = - i=1,N pi log2pi bits
• Em vários algoritmos de árvore de decisão, a
seleção de atributos é baseada nesta teoria.
– Ex: ID3, C4.5, C5.0 [Quinlan93],
[Quinlan96].
Árvores e Teoria da Informação
• Para um dado exemplo qual é a classificação
correta?
– Uma estimação das probabilidades das possiveis
respostas antes de qualquer atributo ser testado é:
– Proporção de exemplos + e - no conjunto de
treinamento.
– I(p/(p+n),n/(p+n))=
-p/(p+n)log2p/(p+n)- n/(p+n)log2n/(p+n)
Árvores e Teoria da Informação
• Testar atributo
– Qualquer atributo A divide o conjunto E em
subconjuntos E1,...,Ev de acordo com seus
valores (v valores distintos).
– Cada subconjunto Ei possui pi exemplos (+ ) e ni
exemplos (-),
– I (pi/(pi+ni),ni/(pi+ni)) bits de informação
adicional para responder.
Ganho de Informação
• Um exemplo randomico possui valor i para o
atributo com probabilidade (pi+ni)/(p+n)
• Em media depois de testar o atributo A
necessitamos
• Resta(A)=i=1,v
(pi+ni)/(p+n)I(pi/(pi+ni),ni/(pi+ni))
• Ganho(A)= I(p/(p+n),n/(p+n))- Resta(A)
Exemplo
• Estado do restaurante
• Valores possiveis (vazio, medio, cheio)
– Ganho(Estado) = 1-[2/12 I(0,1)+4/12I(1,0)+6/12I(2/6,4/6)] =
0,541 bits
– Ganho(tipo)= 1[2/12I(1/2,1/2)+1/12I(1/2,1/2)+4/12I(2/4,2/4)+4/12
I(2/4,2/4)] = 0 bits
Outros Criterios
• Há vários outros critérios que podem ser
usados para selecionar atributos quando
construindo uma árvore de decisão
• Nenhum critério é superior em todas as
aplicações. A eficácia de cada critério
depende dos dados sendo minerados.
Ruido e Overfitting
• Ex: 2 ou mais exemplos com a mesma descrição e
diferentes classificações.
– Classificação segundo a maioria
– Reportar a estimação das probabilidades de cada
classificação.
• Classificar considerando atributos irrelevantes
– ex: jogo de dados, considerar como atributo dia,cor..
Overfitting
• Quando existe um conjunto grande de
hipoteses possiveis, devemos ser cuidadosos
para não usar a liberdade resultante para
encontrar regularidades nos dados.
• Sugere-se podar a árvore, prevenindo testar
atributos que não são claramente relevantes.
– Ganho de informação perto de zero
– Teste de Significância Estatistica.
Teste de Significância
• Assumir que não existe um padrão nos dados,
hipoteses nula.
• Os dados são analizados para calcular quanto eles
desviam-se da ausência perfeita de padrão.
• Se o grau de desviação é estatisticamente
insignificante (5%)
• Existe uma boa evidência da presença de um padrão
nos dados.
Teste de Significância
• As probabilidades são calculadas de uma
distribuição estandard da quantidade de
desviação que se espera ver devido a uma
amostra randomica.
• Neste caso, a hipoteses nula é que o atributo
é irrelevante, e o ganho de informação de
uma amostra infinitamente grande seria zero.
Probabilidade de Hipotese Nula
• Uma amostra de tamanho v exiba a desviação
observada da distribuição esperada de exemplos + e
-.
• Comparar o número de casos p, n dos esperados ^pi
e ^ni
• ^pi = p(pi+ni)/(p+n);
• ^ni=n(pi+ni)/(p+n);
• D =  (pi-^pi)2/^pi+(ni-^ni)2/^ni
• baixo a hipóteses nula, D é distribuído de acordo a
X2 com v-1 graus de liberdade.
Cross-Validação
• A ideia é tentar estimar como a hipoteses
atual predizirá.
• Manter dados de teste, testar performance da
predição.
Árvores de decisão
• Falta de dados
• Atributos multivalorados
• Atributos continuos