aprendizado IA

Inteligncia Artificial

Prof. Paulo Martins Engel

Aprendizagem de mquinarvores de deciso

Informtica UFRGS Prof. Paulo Martins Engel

2

Aprendizagem de mquina A soluo de um problema se d por mtodos indutivos. No necessrio extrair conhecimento de especialistas no

domnio, mas precisa de dados que representem instncias vlidas da soluo do problema (conjunto de treinamento).

Em geral, um modelo capaz de resolver uma tarefa especfica gerado por induo a partir de um conjunto de treinamento.

A soluo bastante flexvel. A variabilidade do domnio deve estar representada no

conjunto de treinamento.


3

Exemplos de tarefas solucionadas por aprendizado

Identificar mensagens como spam: no existe um algoritmo especfico, mas podemos coletar exemplos de mensagens que consideramos como spam, e gerarmos um modelo de classificao para identificar automaticamente novas mensagens como spam.

Identificar potenciais consumidores para um produto: coletar dados de transaes efetuadas e descobrir perfis de consumo.

Anlise de crdito: dados histricos de clientes tomadores de crdito permitem gerar um modelo para prever se um novo cliente potencial ser um bom ou mau pagador.

Agrupar documentos por assunto: criar um modelo para classificar textos por assunto, com base em palavras compartilhadas.


4

Tipos de Aprendizado Aprendizado supervisionado:

existe um conjunto de treinamento contendo pares de valores de atributos medidos para cada instncia do problema e valores de atributos correspondentes soluo do problema, fornecidos por um especialista (aprendizado por imitao).

Aprende mapeamentos entre valores de entrada e sada. Aprendizado no-supervisionado:

ocorre apenas das observaes dos valores medidos para cada instncia do problema, sem conhecimento sobre a sua soluo.

Detecta regularidade nos dados, formando conceitos. Aprendizado por reforo:

Aprende um comportamento, por tentativa e erro, a partir de um sinal de reforo, relacionado com o sucesso de uma ao realizada,


5

O problema da aprendizagem por reforo

Agente

Ambiente

aoat

recompensart

estadost rt+1

st+1

Os sistemas de aprendizagem e de tomada de deciso so denominados de agente. O objeto com o qual o agente interage chamado de ambiente. A interao se d com o agente selecionando aes e o ambiente respondendo a estas

aes apresentando novas situaes para o agente. O ambiente tambm fornece as recompensas - valores numricos que o agente tenta

maximizar ao longo do tempo. O problema representado como um processo de deciso de Markov (PDM), sendo os

estados, aes e a recompensa modelados por variveis aleatrias. Existem algoritmos que encontram a soluo tima baseados em explorao do ambiente.


6

Definio de um problema de aprendizagem Dizemos que um sistema computacional aprende da experincia E,

em relao a uma classe de tarefas T e a uma medida de desempenho P, se seu desempenho nas tarefas em T, medido por P, melhora com a experincia E.

Portanto, num problema de aprendizagem bem formulado identificamos 3 fatores:

a classe das tarefas T tipo de problema de aprendizado o que aprender; soluo; funo alvo; hiptese

a fonte de experincia E especificao do treinamento conjunto de treinamento; procedimento de treinamento

a medida de desempenho a ser melhorada P como avaliar o desempenho

funo de avaliao; funo de valor


7

Projeto de um sistema de aprendizagem O projeto de um sistema de aprendizagem para solucionar uma

determinada tarefa pode ser compreendido como uma srie de escolhas envolvendo os componentes da soluo:

O treinamento: Direto (supervisionado): em cada estado do domnio se conhece a

soluo desejada. A soluo depende de uma nica deciso instantnea (funo ou mapeamento

esttico) Indireto (por reforo): apenas em estados finais, de uma sequncia de

estados, se recebe a informao de sucesso ou insucesso. A soluo depende do encadeamento de decises (funo ou mapeamento

dinmico) Neste caso, o sistema enfrenta o problema de atribuio de crdito para os

estados intermedirios.


8

Medida de desempenho: a funo de valor

Muitas tarefas de aprendizagem podem ser representadas como problemas de otimizao.

Neste caso, o desempenho de uma soluo pode ser medido atravs de uma funo de valor V, de utilidade a ser maximizada pelo treinamento, ou alternativamente, de custo a ser minimizada.

Exemplos: A contagem de erros de previso de um classificador, por exemplo,

constitui uma de funo de custo. A configurao do tabuleiro em um determinado estado de um jogo

poderia ser avaliada por uma funo de utilidade, que mede o quo distante est este estado, do estado final (de vitria).


9

Representao do Domnio

Na maioria dos mtodos de aprendizado de mquina, o domnio representado por trincas : (objeto, atributo, valor).

objeto

atributo_1 atributo_i atributo_n

val11 val12 vali1 vali3vali2 valn1 valn2


10

Um conceito a ser aprendido um padro que descreve um subconjunto dos dados e que depende do estilo de aprendizado (tarefa).

Estilos de aprendizado: Aprendizado classificatrio: prever uma classe discreta Aprendizado associativo: detectar associaes entre caractersticas Aprendizado aglomerativo: agrupar amostras similares Previso numrica: prever uma quantidade numrica

Descrio de conceito: sada do esquema de aprendizado Exemplo: uma regra de classificao descreve um conceito como uma

conjuno de valores de atributos que indicam uma determinada classe do domnio:

R1: val12 val33 classe1

Aprendizado de conceitos


11

Um modelo a ser aprendido descreve todo o conjunto de dados e formado por um conjunto de conceitos.

Descrio do modelo: sada do esquema de aprendizado

Exemplo: um conjunto de regras de classificao descreve a partio do domnio, induzida a partir do conjunto de dados:

R1: val12 val33 classe1R2: val41 classe1R3: val22 classe2R4: val21 val31 classe2

Aprendizado de modelos


12

Instncia de treinamento: um exemplo especfico do problema Objeto a ser classificado, associado ou agrupado Exemplo individual e independente do conceito alvo Caracterizado por um conjunto predeterminado de atributos

Entrada para o esquema de aprendizagem: conjunto de instncias/ dados Representado como uma nica relao (arquivo plano)

uma forma restrita de entrada No pode haver relacionamentos entre objetos

Exemplos de treinamento


13

Cada amostra descrita por um conjunto pr-definido de caractersticas, os seus atributos

Mas: na prtica, nmero de atributos pode variar Soluo possvel: flag valor irrelevante (p. ex. ?)

Problema relacionado: existncia de um atributo pode depender de valor de um outro atributo

Tipos possveis de atributos (nveis de medidas): Nominal, ordinal, intervalar e racional

O que um atributo?


14

Exemplo de representao e tarefa de aprendizagem

Problema de previso (classificao): dadas as condies climticas de um determinado dia, prever se uma pessoa vai jogar (tnis) ou no.

Representao grfica do conhecimento a priori do domnio do tempo.

Dia

Tempo Umidade Joga

ensolarado chuvoso normal alta sim nonublado

Ventoso

verdadeiro falso

Temperatura

quente friaamena

Os conceitos de interesse so as classes: joga, no joga. Amostras dos conceitos so quinas com valores dos atributos:

< val-tempo, val-temperatura, val-umidade, val-ventoso, val-joga >


15

Tempo Temperatura Umidade Ventoso Jogaensolarado quente normal verdadeiro noensolarado quente normal falso noensolarado quente alta verdadeiro noensolarado quente alta falso noensolarado amena normal verdadeiro noensolarado amena normal falso noensolarado amena alta verdadeiro noensolarado amena alta falso noensolarado fria normal verdadeiro noensolarado fria normal falso noensolarado fria alta verdadeiro noensolarado fria alta falso no

nublado quente normal verdadeiro nonublado quente normal falso nonublado quente alta verdadeiro nonublado quente alta falso nonublado amena normal verdadeiro nonublado amena normal falso nonublado amena alta verdadeiro nonublado amena alta falso nonublado fria normal verdadeiro nonublado fria normal falso nonublado fria alta verdadeiro nonublado fria alta falso nochuvoso quente normal verdadeiro nochuvoso quente normal falso nochuvoso quente alta verdadeiro nochuvoso quente alta falso nochuvoso amena normal verdadeiro nochuvoso amena normal falso nochuvoso amena alta verdadeiro nochuvoso amena alta falso nochuvoso fria normal verdadeiro nochuvoso fria normal falso nochuvoso fria alta verdadeiro nochuvoso fria alta falso no

Exemplos possveis para o problema do tempo (33222 = 72)Tempo Temperatura Umidade Ventoso Joga

ensolarado quente normal verdadeiro simensolarado quente normal falso simensolarado quente alta verdadeiro simensolarado quente alta falso simensolarado amena normal verdadeiro simensolarado amena normal falso simensolarado amena alta verdadeiro simensolarado amena alta falso simensolarado fria normal verdadeiro simensolarado fria normal falso simensolarado fria alta verdadeiro simensolarado fria alta falso sim

nublado quente normal verdadeiro simnublado quente normal falso simnublado quente alta verdadeiro simnublado quente alta falso simnublado amena normal verdadeiro simnublado amena normal falso simnublado amena alta verdadeiro simnublado amena alta falso simnublado fria normal verdadeiro simnublado fria normal falso simnublado fria alta verdadeiro simnublado fria alta falso simchuvoso quente normal verdadeiro simchuvoso quente normal falso simchuvoso quente alta verdadeiro simchuvoso quente alta falso simchuvoso amena normal verdadeiro simchuvoso amena normal falso simchuvoso amena alta verdadeiro simchuvoso amena alta falso simchuvoso fria normal verdadeiro simchuvoso fria normal falso simchuvoso fria alta verdadeiro simchuvoso fria alta falso sim

Atributos previsores Atributo meta


16

Dados reais de um problema do tempo com incertezas

Situao muito comum: as combinaes podem no ser exaustivas e ser contraditrias. O domnio no determinstico (tem rudo): para um certo conjunto de valores de atributos,

existe uma chance (probabilidade) de ocorrer o valor previsto.

Tempo Temperatura Umidade Ventoso Jogaensolarado quente alta falso noensolarado quente alta verdadeiro no

nublado quente alta falso simchuvoso amena alta falso simchuvoso fria normal falso simchuvoso fria normal verdadeiro nonublado fria normal verdadeiro sim

ensolarado amena alta falso noensolarado fria normal falso sim

chuvoso amena normal falso simensolarado amena normal verdadeiro sim

nublado amena alta verdadeiro simnublado quente normal falso simchuvoso amena alta verdadeiro no

Lista de dias, apresentando as condies climticas e se o jogador foi jogar ou no. Arquivo lista apenas as combinaes dos valores dos atributos que realmente apareceram no

domnio (Tem apenas 14 das 72 combinaes possveis).


17

Num domnio com valores discretos (abordagem simblica), os conceitos possveis de se encontrar pertencem a um espao limitado (mas normalmente muito grande!) dado pela combinao (de todas as ordens) de todos os valores possveis: o espao de conceitos ou espao de busca.

Exemplo: o espao de conceitos para o problema do tempo, considerando que os conceitos so regras de classificao (condio climtica joga ou no)

4 x 4 x 3 x 3 x 2 = 288 possibilidades por regra (pois um atributo previsor pode no estar presente numa regra, representado por ?)

Exemplo: < nublado, ?, ?, ?, sim > Se tempo = nublado Ento joga = sim Restringindo um modelo de classificao a no mais que 14 regras: 2,7x1034

conjuntos (modelos) diferentes de regras possveis (28814) Outros problemas prticos de usar busca para descobrir conceitos:

Pode restar mais que uma descrio Pode no restar nenhuma descrio

A linguagem pode no ser capaz de descrever o conceito alvo Os dados podem conter rudo

Enumerao do espao de conceitos

Informtica UFRGS 18

rvores de Deciso As rvores de deciso (AD) so ferramentas poderosas para

classificao cuja maior vantagem a sua expressividade, j que elas representam um conjunto consistente de regras de classificao.

Uma AD representa uma srie de testes encadeados acerca de atributos de um objeto do domnio.

Um dado entra na rvore pelo n raiz, tradicionalmente colocado no topo da representao grfica, e a rvore se desenvolve para baixo, at chegar a um n folha, representando uma classe.

A partir de um n (pai), feito um teste para decidir qual n filho deve ser pesquisado a seguir.

Existe apenas um caminho da raiz at cada folha. Este caminho uma expresso da regra usada para classificar os dados.

Informtica UFRGS 19

y < 0.33?

: 0 : 3

: 4 : 0

y < 0.47?

: 4 : 0

: 0 : 4

x < 0.43?

Yes

Yes

No

No Yes No

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

x

yExemplo de AD

N2 N3

N4 N5 N6 N7

N2N3

N3

N1

N4

N5

N6

N7

Na verso usual, testa um atributo por vez produzindo fronteiras de deciso paralelas aos eixos.

Produz um modelo de classificao consistente: baseado em partio, sem superposio de regras

N4: Se x < 0.43 E y < 0.47 Ento Classe = tringulo (4/0)N5: Se x < 0.43 E y 0.47 Ento Classe = crculo (4/0)N6: Se x 0.43 E y < 0.33 Ento Classe = crculo (3/0)N7: Se x 0.43 E y 0.33 Ento Classe = tringulo (4/0)

N2

N1N1

Informtica UFRGS 20

Exemplo: Problema do tempo

Tempo Temperatura Umidade Ventoso Jogaensolarado quente alta falso noensolarado quente alta verdadeiro no





Assumindo que as condies meteorolgicas influenciam a deciso de um jogador de jogar ou no (tnis, golfe, ....), determine, a partir de um conjunto de observaes passadas, um modelo capaz de prever se o jogador vai ou no jogar num determinado dia, dadas as condies meteorolgicas.

Tempoensolarado

nublado

chuvoso

Temperaturaquente

amena

fria

Umidade

alta normal

Ventoso

falso verdadeiro

Joga

sim no

Atributos previsores: Atributo alvo:(classe)

Modelo

TempoTemperatura

UmidadeVentoso

Joga

Informtica UFRGS 21

Exemplo de rvore de deciso

Se Tempo = ensolaradoE Umidade = altaEnto Classe = no

Ventoso

falso verdadeiro

Tempoensolarado

nubladochuvoso

Umidadealta

normal

no sim

sim

sim no

Se Tempo = ensolaradoE Umidade = normalEnto Classe = sim

Se Tempo = nubladoEnto Classe = sim

Se Tempo = chuvosoE Ventoso = falsoEnto Classe = sim

Se Tempo = chuvosoE Ventoso = verdadeiroEnto Classe = no

O algoritmo de gerao da AD descobre quais atributos previsores so realmente importantes para a classificao, descartando os demais (temperatura, no exemplo do tempo).

ADTempo

Umidade

Ventoso

Joga

Informtica UFRGS 22

Procedimento padro: de cima para baixo, usando recursivamente dividir e conquistar (algoritmo de Hunt). Primeiro: seleciona-se o atributo do n raiz e cria-se um ramo para cada valor

possvel do atributo. Ento: os exemplos so divididos em subconjuntos (um para cada ramo que sai do

n), conforme o resultado do teste. Finalmente: o procedimento repetido recursivamente para cada ramo, usando

apenas os exemplos que chegam no ramo considerado.

O processo termina quando todos os exemplos do subconjunto do ramo tm a mesma classe, ou ...... todos os exemplos tm valores de atributos similares nmero de instncias menor que um limiar estabelecido o critrio de expanso de ns no satisfeito (mtrica de escolha do teste) .....

Construo de rvores de deciso

Informtica UFRGS 23

Seleo do teste a ser aplicado em um determinado n

conjunto de entrada: 9/5 (9 sim, 5 no)

Tempo

simsimnonono

ensolaradonublado

chuvoso

simsimsimsim

simsimsimnono

conjuntos resultantes do teste

sim sim sim sim sim sim sim sim simno no no no noT

T1 T2 T3

Tempo Temperatura Umidade Ventoso Joga

ensolarado quente alta falso noensolarado quente alta verdadeiro no





Estratgia gulosa: o atributo testado produz uma partio das instncias que chegam no n que otimiza um determinado critrio.

Base: mtrica para seleo de atributos.

2/3 3/24/0

Informtica UFRGS 24

Qual o melhor atributo para testar num n? Aquele que produz a menor rvore (implica gerar todas as

possibilidades!!). Heurstica: escolher o atributo que produz os ns mais puros

(homogneos em relao classe majoritria). Critrio popular para impureza: quantidade de informao, ou

entropia de um subconjunto. O ganho de informao representa o quanto (em mdia) se ganha em

pureza ao se dividir um conjunto segundo um atributo. Estratgia: escolher o atributo que produz o maior ganho de

informao.

Critrio para seleo de atributo

Informtica UFRGS 25

A quantidade de informao medida em bits.

Dada uma distribuio (de classes), calcula-se a quantidade de informao necessria para prever um evento (uma classe).

equivalente entropia da distribuio

A entropia representa a informao necessria em bits (ou frao de bits!)

Frmula para calcular a entropia de um conjunto:

entropia(p1, p2, ..., pn) = p1logp1 p2logp2 ... pnlogpnonde p1, p2, ..., pn so as probabilidades (taxa de ocorrncia) das classes 1, 2, ..., n, neste conjunto.

Obs: o logaritmo na base 2 para a medida em bits!

Clculo da informao

Informtica UFRGS 26

O algoritmo C4.5

O algoritmo C4.5 (Quinlan 93) produz rvores com nmero de ramos varivel.

Cada valor de um dado categrico gera um ramo.

A entropia ou ganho de informao utilizada como fator de escolha do atributo a ser testado num n.

A partio do espao de caractersticas comea pelo n raiz e continua para os ns filhos da mesma maneira, ou seja, escolhendo-se em cada n o melhor atributo para a partio, at que um atributo assuma um nico valor.

Neste caso, ns rotulamos este n como folha.

Informtica UFRGS 27

Avaliao dos atributos do tempo

Tempo Temperatura Umidade Ventoso Joga

ensolarado quente alta falso no

ensolarado quente alta verdadeiro no

nublado quente alta falso sim

chuvoso amena alta falso sim

chuvoso fria normal falso sim

chuvoso fria normal verdadeiro no

nublado fria normal verdadeiro sim

ensolarado amena alta falso no

ensolarado fria normal falso sim

chuvoso amena normal falso sim

ensolarado amena normal verdadeiro sim

nublado amena alta verdadeiro sim

nublado quente normal falso sim

chuvoso amena alta verdadeiro no

Qual o ganho de informao do teste para o atributo Tempo?

Informtica UFRGS 28

entropia(p1,..., pn) = p1logp1 p2logp2 ... pnlogpnEntropia do conjunto original:entropia(9/14, 5/14) = 9/14log(9/14) 5/14log(5/14) = 0,940 bitsEntropia dos conjuntos resultantes do teste:Tempo = ensolarado:entropia(2/5, 3/5) = 2/5log(2/5) 3/5log(3/5) == 0,971 bitsTempo = nublado:entropia(4/4, 0/4) = 1log(1) 0log(0) = 0 bitsTempo = chuvoso:entropia(3/5, 2/5) = 3/5log(3/5) 2/5log(2/5) == 0,971 bits

Entropia mdia dos conjuntos resultantes:(5/14)0,971 + (4/14)0 + (5/14)0,971 = 0,693 bits

Exemplo: atributo Tempo

conjunto original: 9 sim, 5 no

Tempo

simsimnonono

ensolaradonublado

chuvoso

simsimsimsim

simsimsimnono

conjuntos resultantes do teste

sim sim sim sim sim sim sim sim simno no no no no

Ganho de informao do testepara o atributo Tempo:

0,940 0,693 = 0,247 bits

T

T1 T2 T3

Informtica UFRGS 29

Qual atributo deve ser selecionado?Temperatura

simsimnono

quenteamena

fria

simsimsimsimnono

simsimsimno

Umidade

simsimsimnononono

alta normal

simsimsimsimsimsimno

Ventoso

simsimsimsimsimsimnono

falso verdadeiro

simsimsimnonono

Tempo

simsimnonono

ensolaradonublado

chuvoso

simsimsimsim

simsimsimnono

Ganho = 0,247 bits Ganho = 0,029 bits

Ganho = 0,152 bits Ganho = 0,048 bits

Informtica UFRGS 30

Continuar a dividir

Temperatura

nono

quenteamena

fria

simno sim

Umidade

nonono

alta normal

simsim

Ventoso

simnono

falso verdadeiro

simno

Temposim simno no no

ensolarado nubladochuvoso





Ganho = 0,971 bits

Ganho = 0,020 bits

Ganho = 0,571 bits

Informtica UFRGS 31

rvore de deciso final

simsimsim

nono

simsimsimsim

nonono

simsim

Ventoso

falso verdadeiro

Tempoensolarado

nubladochuvoso

Umidade

alta normal

no sim

sim

sim no

Distribuio das classes dos exemplos que chegam nas folhas

Documents

aprendizado IA