45
Aprendizado de Máquinas

Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Embed Size (px)

Citation preview

Page 1: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Aprendizado de Máquinas

Page 2: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Aprendendo de Observações

AMBIENTE

Sensores

Efectores

Critica

Aprendizado

Gerador

PerformanceFeedback

Objetivos de aprendizado

Modelo de Aprendizado

Page 3: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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.

Page 4: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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.

Page 5: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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.

Page 6: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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....

Page 7: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Feedback Disponivel

• E, S ; aprendizado supervisionado

• E, ~S ; aprendizado reforçado

• E ; aprendizado não supervisionado

Page 8: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Aprendizado Inductivo

F(x)

X F(X)

Page 9: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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.

Page 10: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Bias

Page 11: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Tarefa de Classificação

Page 12: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Árvores de Decisão

Alemanha Inglaterra

França

País

Não Sim

Sim Não

Idade

> 25< 25

Page 13: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Á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.

Page 14: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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....

Page 15: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Esperar por uma mesa?

Alternativa Fome

Reservas DiaAlternat.

BarChove

Não SimNão Sim

Vazio Medio

CheioEstado rest.

Espera

Não Não

Não

Sim

Sim Sim

Sim

Sim

Sim

0-1030-60>60 10-30

Não Sim

Não Sim

Não Sim

Não Sim

Não Sim

Não Sim

Semana Final

Page 16: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Expressividade das Árvores de decisão

• Conjunto de implicações: da raiz até uma folha

• ex: r Estado(r,cheio)spera(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)

Page 17: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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.

Page 18: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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.

Page 19: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Indução de Árvores

• Uma árvore de decisão é construída de forma "top-down", usando o princípio de dividir-para-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.

Page 20: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Conjunto de Treinamento

Page 21: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Seleção do Atributo

+1 3 4 6 8 12-2 5 7 9 10 11

+ 1- 5

+ 6- 10

+ 4 8- 2 11

+ 3 12- 7 9

+ 1 3 4 6 8 12- 2 5 7 9 10 11

+- 7 11

+ 1 3 6 8-

+ 4 12- 2 5 9 10

EstadoVazi

oMedio

Cheio

F I T B

Tipo

Page 22: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

+ 1 3 4 6 8 12- 2 5 7 9 10 11

+- 7 11

+ 1 3 6 8-

+ 4 12- 2 5 9 10

Estado

Vazio Medio Cheio

Fome

+ 4 12- 2 10

+ - 5 9

Sim Não

Page 23: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Algoritmo

Page 24: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Árvore GeradaEstado

Não SimFome

Tipo

sex/sab

Não

Não

NãoSim

Sim

Sim

Vazio Medio Cheio

Não Sim

Não Sim

F I T

B

Page 25: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Á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.

Page 26: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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

Page 27: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Conjunto de treinamento

• O resultado é um conjunto de dados que pode ser processado para dar a media da qualidade da predição.

Page 28: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Curva de Aprendizado

Tamanho do conjunto de treinamento

% de corretos no conjunto de teste

100

Page 29: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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.

Page 30: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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).

Page 31: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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

Page 32: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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.

Page 33: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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].

Page 34: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Á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)

Page 35: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Á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.

Page 36: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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)

Page 37: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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

Page 38: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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.

Page 39: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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..

Page 40: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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.

Page 41: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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.

Page 42: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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.

Page 43: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

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.

Page 44: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Cross-Validação

• A ideia é tentar estimar como a hipoteses atual predizirá.

• Manter dados de teste, testar performance da predição.

Page 45: Aprendizado de Máquinas. Aprendendo de Observações AMBIENTEAMBIENTE Sensores Efectores Critica Aprendizado Gerador Performance Feedback Objetivos de aprendizado

Árvores de decisão

• Falta de dados

• Atributos multivalorados

• Atributos continuos