Page 1
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Introdução à
APRENDIZAGEM SIMBÓLICA AUTOMÁTICA
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
APRENDIZAGEM SIMBÓLICA AUTOMÁTICA
Herbert Simon (pioneiro da IA): “Aprender implica mudanças adaptativas de um sistema no sentido de lhe permitir realizar, da próxima vez, a(s) mesma(s) tarefa(s), em circunstâncias análogas, de um modo mais eficiente e efetivo “
Page 2
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Aprendizagem humana:
aquisição de conhecimento (Knowledge acquisition)
Consiste na aquisição estruturada de nova informação simbólica assim como da capacidade de a aplicar a situações novas. Exemplo: aprender teoremas da Matemática.
refinamento de habilidade (skill refinement)
Processo, eminentemente não simbólico caraterizado por refinar um procedimento através de tentativas sucessivas até atingir uma proximidade desejada com o objetivo.
Exemplo: aprender a andar de bicicleta, nadar,...
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Taxonomia dos Métodos de Aprendizagem Simbólica
- classificação quanto à estratégia, à representação e ao domínio.
Classificação quanto à estratégia usada:
- “rote learning” (by being programmed)
- aprendizagem por conselho ou por instrução (by being told or by instruction) - aprendizagem por analogia - aprendizagem por exemplos - aprendizagem por observação ou descoberta - aprendizagem por Reforço
Page 3
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
- “rote learning”
Consiste na implantação directa de novo conhecimento,
- aprender por ser programado (by being programmed) -aprender por memorização de novos factos ou dados. O termo rote learning deriva precisamente daí.
O conselho é fornecido pelo agente exterior numa forma ou linguagem não directamente utilizável pelo sistema. Uma transformação de representação e/ou alguma inferência deve ser feita pelo sistema de aprendizagem por forma a operacionalizar o novo conhecimento e compatibilizá-lo com o pré-existente.
- aprendizagem por conselho ou por instrução (by being told or by instruction)
Consiste na aquisição de novos conceitos ou factos ou planos por transformação ou ampliação de conceitos já adquiridos pelo sistema.
Ex: CBR (Raciocínio Baseado em Casos); Generalização de Planos em robótica
- aprendizagem por analogia
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
aprendizagem por exemplos Dado um conjunto de exemplos e contra-exemplos, o sistema de aprendizagem deve induzir um conceito geral que verifique todos os exemplos (ou exemplos positivos) e não contemple nenhum dos contra-exemplos (ou exemplos negativos).
aprendizagem por observação ou descoberta (não supervisionada)
É um método bastante geral de aprendizagem indutiva que inclui os chamados sistemas de descoberta, tarefas de formação de teorias, criação de critérios de classificação para formação de hierarquias taxonómicas ( conceptual clustering ) sem a intervenção ou auxílio de um agente exterior.
aprendizagem por Reforço
O sistema aprende a adaptar o seu comportamento às novas situações depois de receber reforços quer positivos quer negativos vindos do ambiente.
Page 4
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Classificação quanto à representação do conhecimento adquirido
- Parâmetros em expressões algébricas
Elementos lógicos de limiar . Funções que modelam o desempenho do sistema e cujos coeficientes são ajustados.
- árvores de decisão Nós ordenados ligados por arcos representando os valores possíveis dos atributos a testar (nos nós).
- Expressões baseadas em lógica formal e formalismos semelhantes. Lógica de Predicados de Primeira Ordem. Cálculo de predicados anotado (Michalski). Lógicas Modais - Grafos e redes
- Gramáticas formais São tipicamente representadas por expressões regulares, autómatos finitos, regras de uma gramática independente do contexto ou regras de tranformação.
- Regras de produção (ou Produções) Pares antecedentes - consequente que seleccionam acções a serem executadas.
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Aprendizagem Híbrida: Dedutiva/Indutiva por
Métodos Baseados em Explicações EBL
definição correcta de um conceito a partir de exemplos
Estratégia que inclui "aprendizagem por exemplos":
-Problema: Como identificar uma positivos, tais que o conceito seja uma especialização de um conceito-genérico (target) definido pela " Teoria do Domínio “ dada.
3 Versões do método (para a Especilaização de Conceitos baseados na Teoria): - Generalização Baseada nas Explicação ( EBG ) - EBG de exemplos multiplos ( mEBG) - uma versão diversa: Indução Sobre as Explicações ( IOE )
Os dois primeiros tem desvantagens : - raramente identificam a definição correcta e o sucesso depende grandemente da codificação das regras da teoria do domínio.
Page 5
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Generalização Baseada em Explicações (EBG)
O Resolvedor de Problemas começa com uma teoria correcta do domínio que define o conceito-genérico CG (target-concept). A teoria, embora correcta pode ser ineficiente.
É claro que se pode aprender
neste caso mais conhecimento se as WP forem condição necessária e suficiente para a definição de um conceito C mais específico.
WP(E) = C(E)
* Dados Exemplos treino E
* aplicar a teoria do domínio para provar que cada E é uma instância do conceito-genérico.
* Extraír as pré-condições mais fracas (WP) da prova para formar uma regra eficiente
* O conceito-genérico dá origem a uma nova "forma operacional".
- Processo:
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Exemplo prático:
* Sistema de Pazzani (OCCAM) onde a teoria do domínio define o conceito-genérico "coerção" (fazer executar um objetivo pela ameaça). Ao aplicar a teoria numa situação em que “um país ameaça não vender petróleo" e ao achar a pré-condição mais fraca, o sistema deriva o conceito de “sanção económica” que é depois aprendido.
Como explorar o domínio do conhecimento para guiar uma aprendizagem indutiva?
Dados : TD Uma teoria do Domínio que define um conceito genérico (CG) . Um conjunto de exemplos E positivos de treino envolvendo um conceito C que é uma especialização de CG
Encontrar:
Uma definição correta de C
Page 6
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Método EBG
1º Construir a árvore de explicação que prova que um (único) exemplo é uma instância do conceito genérico.
2º Coligir as Pré-condições mais fracas (WP) tais que a uma explicação é ainda verdadeira. Para árvores simples WP é a conjunção dos literais das folhas .
3º Devem generalizar-se os termos Argumentos desses literais, i.e. devem ficar independentes do exemplo, (eis a generalização).
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Consideremos as três versões referidas do método para especializar conceitos baseados na Teoria do domínio (TD), no conceito genérico (CG) e nos exemplos de treino (E) -Teoria do domínio que define o conceito objeto chávena:
regra C chavena(Obj):- conter_liquido(Obj), estavel(Obj), eleva(Obj), acessivel(Obj). regra CL conter_liquido(Obj):- superficie(Obj,S), feito_de(S,Ms), não-poroso(Ms), fundo(Obj,F), feito_de(F,Mf), não_poroso(Mf). não_poroso(plastico). não_poroso(porcelana). não_poroso(aluminio).
Regra Es estavel(Obj):- fundo(Obj,F), plano(F). Regra El eleva(Obj):- leve(Obj), apanhavel(Obj).
Page 7
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
regra Lv leve(Obj):- pequeno(Obj), superficie(Obj,S), feito_de(S,Ms), material_leve(Ms), fundo(Obj,F), feito_de (F,Mf), material_leve(Mf). material_leve(plastico). material_leve(porcelana). material_leve(aluminio). material_leve(papel).
regra Ap_1 apanhavel(Obj):- pequeno(Obj), superficie(Obj,S), cilindrico(S), feito_de(S,M), isolante_termico(M). regra Ap_2 apanhavel(Obj):- pequeno(Obj), tem(Obj,P), asa(P). isolante_termico(plastico). isolante_termico(porcelana).
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Descrição dos objetos Ci (exemplos treino-positivos):
superficie(c1, s1) superficie (c2,s2) superficie(c3, s3)
feito-de(s1, plastico) feito-de(s2, plástico) feito-de(s3, porcelana).
fundo(c1, f1). fundo(c2, f2). fundo(c3, f3)
feito-de(f1, plástico) feito-de(f2, alumínio) feito-de(f3, porcelana).
plano(f1). plano(f2). plano(f3).
tem(c1, p1). tem(c2, p2). tem(c3, p3).
concavidade(p1). concavidade(p2). concavidade(p3).
para-cima(p1). para-cima(p2). para-cima(p3).
pequeno(c1). pequeno(c2). pequeno(c3).
cilindrico(s1). tem(c2, p21). tem(c23, p31).
asa(p21). asa(p31).
Page 8
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
As árvores de explicação construídas para provar cada exemplo a partir da Teoria do Domínio
são:
As folhas das árvores (não representadas) são os factos que descrevem os Exemplos C1”apanhável” porque pequeno, cilindrico, isolante_térmico; C2 e C3 pequenos e tem_asa
C
CL Es El Ac
Lv Ap
Ap2
Factos Factos
Factos
Factos
Factos
C
CL Es El Ac
Lv Ap
Ap2
Factos Factos
Factos
Factos
Factos
Factos
C
CL Es El Ac
Factos
sup(c1,s1)
feito_de(s1,plas)
n_poroso(plas)
fundo(c1,f1)
feito_de(f1,plas)
n_poroso(plas)
Factos
Lv Ap
Ap1
Factos
Factos
c1 c2 c3
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Método EBG
Para o exemplo Chávena C1 as pré-condições mais fracas são: superficie(c1,s1), feito_de(s1,plástico), não_poroso(plástico), fundo(c1,f1), feito_de(f1,plástico), não_poroso(plástico), plano(f1), pequeno(c1), material_leve(plástico), cilindrico(s1), isolante_termico(plástico), tem(c1,p1), concavidade(p1), para_cima(p1). Estas são as pré-condições mais fracas wp. São condições suficientes para sêr Chávena
Generalizando para o exemplo Chávena 1 as pré-condições mais fracas: superficie(O,S), feito_de(S,Ms), não_poroso(Ms), fundo(O,F), feito_de(F,Mf), não_poroso(Mf), plano(F), pequeno(O), material_leve(Ms), material_leve(Mf), cilindrico(S), isolante_termico(Ms), tem(O,P), concavidade(P), para_cima(P).
Estas wp formam o novo conceito Ca que é uma especialização do conceito chávena depois de generalizar os argumentos. Ca - (superfície cilindrica feita de material leve e isolante térmico) Chávena-copo
Page 9
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Se em vez de chávena1 construíssemos a árvore de explicação para chávena 2 um novo conceito Cb seria criado para chávenas com asa removendo a restrição do material isolante-térmico.
Logo o número de conceitos derivados é igual ao número de árvores de explicação completas diferentes que se podem derivar. (no caso visto, só 2).
superficie(O,S), feito_de(S,Ms), não_poroso(Ms), fundo(O,F), feito_de(F,Mf), não_poroso(Mf), plano(F), pequeno(O), material_leve(Ms), material_leve(Mf), cilindrico(S), tem(O,P), concavidade(P), para_cima(P), tem(O,P1), asa(P1).
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
m E B G : G e n e r a l i z a ç ã o B a s e a d a n a s E x p l i c a ç õ e s p o r m ú l t i p l o s e x e m p l o s .
1: Para cada exemplo construir a árvore de explicação provando que o exemplo é uma instância do conceito geral (CG).
2: Comparar as árvores de explicação para encontrar a maior sub-árvore partilhada por todos os exemplos.
3: Aplicar as técnicas de generalização do EBG a esta sub-árvore e extraír a WP tal que a árvore permaneça uma prova válida.
Page 10
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
WP: superficie(O,S), feito_de(S,Ms), não_poroso(Ms), fundo(O,F), feito_de(F,Mf), não_poroso(Mf) plano(F), pequeno(O), material_leve(Ms), material_leve(Mf) tem(O,P), concavidade(P), para_cima(P), apanhável(O).
As condições específicas de "apanhável" foram apagadas. Mas continua a ser Chávena !
C
CL Es El Ac
Lv Ap
Ap2
Factos Factos
Factos
Factos
Factos
Factos
C
CL Es El Ac
Factos
sup(c1,s1)
feito_de(s1,plas)
n_poroso(plas)
fundo(c1,f1)
feito_de(f1,plas)
n_poroso(plas)
Factos
Lv Ap
Ap1
Factos
Factos
Se tivéssemos usado os exemplos da chávena 1 e 2
C
CL Es El Ac
Lv Ap
mEBG(C1, C2)
Factos Factos
Factos
Factos
A máxima sub-árvore seria:
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
IOE Indução Sobre as Explicações
Como em mEBG, também IOE aprende a partir de múltiplos exemplos.
A diferença está na estratégia de derivar a máxima sub- -árvore comum de explicações.
Consideremos 2 exemplos de treino :
1: Aplicar mEBG aos dois exemplos, produzindo a definição
de novos conceitos e retendo as árvores originais.
2: Fazer o "matching" do conceito C com cada uma das árvores de prova dos exemplos de treino para produzir uma substituição Qi de pares Vj=cj.
Vj é cada variável em C e cj a respetiva constante ou termo do exemplo ou Teoria do Domínio. (substituições Q1 e Q2 de C)
3: Derive Q, uma nova substituição para NC da seguinte forma:
Page 11
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
3.2.1 atente nos valores que substituem Vj em q1, (c1j), e em q2 (c2j) 3.2.2 cj = gen(c1j,c2j) onde gen(c1j,c2j) é definido por:
SE c1j=c2j ENTÃO gen(c1j,c2j)=c1j SENÃO
3.1 q F
3.2 para cada Vj em NC faça Vj=cj em q, onde cj é computado como segue:
SE c1j=f(t11, t21,…tk1) e c2j=f(t12,t22,…,tk2) (i.e. termos com o mesmo functor) ENTÃO gen(c1j,c2j)= f(gen(t11,t12), …, gen(tk1,tk2)) SENÃO
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
(SENÃO)
gen(c1j,c2j)=V onde V é seleccionado como segue:
SE gen(c1j,c2j) nunca anteriormente chamada
ENTÃO V é uma variável ainda não usada em q1, q2 ou q
guardar gen(c1j,c2j)=V numa tabela
SENÃO (i.e. já houve pelo menos uma chamada a gen(c1,c2))
consultar tabela e usar variável já considerada
4º Computar e retornar a descrição do conceito NC com a substituição q
IOE computa portanto a definição do novo conceito NC tal como em mEBG, mas depois especializa-a introduzindo restrições às variáveis usando a substituição q
Page 12
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Primeiro tipo de restrição : Uma constante é introduzida na definição do conceito quando uma variável V aparecendo na definição C de mEBG fica ligada à mesma constante em cada exemplo de treino.
Suponhamos que aplicavámos mEBG às chávenas 1 e 2 :
Na definição do conceito especializado aparece feito_de(S, Ms) onde Ms é o material da superficie lateral da chávena. c 1 e c 2 tem superficies laterais de plástico o que implicará que a definição final do conceito exija que a superficie lateral seja de plástico.
Segundo tipo de restrição : é uma restrição de igualdade forçando 2 ou mais variáveis da definição de C a serem iguais.
Tal acontece quando IOE encontra 2 ou mais variáveis diferentes V 1 , V 2 na definição do conceito mEBG ligadas ao mesmo termo em cada exemplo. Isto é, o termo C i pode diferir de um exemplo para outro mas em cada um deles V 1 e V 2 estão ligados a um mesmo C i .
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Suponhamos que aplicamos IOE aos exemplos c 1 e c 3 . Em c 1 quer a superficie quer o fundo são de plástico e em c 3 são ambos de porcelana. A definição do conceito C por mEBG leva a :
feito_de(S, Ms) e feito_de(F, Mf).
No primeiro caso (c 1 ), Ms = Mf = plástico e em c 2 Ms = Mf = porcelana.
Então IOE encontra uma nova variável M e a definição final do conceito inclui : feito_de (S, M) e feito_de(F,M). O novo conceito define chávena homogéneas.
Consideremos a seguinte tabela onde a 1ª coluna mostra as 6 variáveis aparecendo na definição do conceito C de mEBG.
As 2ª, 3ª e 4ª colunas apresentam as substituições Q , para c 1 , c 2 e c 3 . As duas colunas finais mostram os resultados da aplicação de IOE aos exemplos c 1 , c 2 e c 1 , c 3 respectivamente.
Page 13
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Variáv el
V
exemplos treino resultados da aprendizagem
IOE(C1, C2) IOE(C1, C3)
Ms plás tico p lástic o porcelana plástico M
Mf plás tico alumínio porc elana
Ma M
C1 C2 C3
Obj c1 c2 c3 O O
S s1 s2 s3 Sup Sup
F f1 f2 f3 Fundo Fundo
Parte p1 p2 p3 P P
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Consideremos a última coluna da tabela mostrando os resultados do algoritmo IOE para c 1 e c 3 . No passo 3 do algoritmo IOE o procedimento gen será aplicado a cada linha. gen (c 1 , c 3 ) Como as constantes são diferentes cria uma variável, seja Q = {Obj = O}
gen(s 1 , s 3 ) = Sup Q = {Obj = O, S=Sup}
gen(plástico, porcelana) cria uma restrição de igualdade gerando a variável M
Q = {Obj = O, S=Sup, Ms=M}
A informação gen(plástico,porcelana)=M também é guardada para posterior utilização.
Quando se chega à 5ª linha, o algoritmo consulta a tabela e verifica que gen já foi chamado com aqueles argumentos, logo dá à variável Mf a mesma substituição, isto é, M.
Q = {Obj=O, S=Sup, Ms=M, F=Fundo, Mf=M}
Page 14
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Este método (chamado das "não-coincidências" ) é simples mas poderoso. Ao contrário de outros métodos indutivos não procura encontrar padrões nos exemplos de treino tal como eles são apresentados originalmente. Aplica a Teoria do Domínio e o conceito genérico para identificar caraterísticas úteis para a generalização indutiva.
O espaço das definições de conceitos possíveis de serem construídas por esta técnica é superior a mEBG pois IOE pega em cada um dos conceitos mEBG e gera substituições restringindo a definição pelas igualdades.
No domínio considerado das chávenas IOE gera 58 diferentes definições de chávenas (incluindo as de asa de plástico e as homogéneas).
Baseado em : "A study of Explanation-based methods for inductive learning" - Nocholas Flann; Thomas Diettrich; Machin Learning, Nov-89
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
O programa para usar o Algoritmo IOE (versão de EBG) teria de ter as seguintes funcionalidades:
• Importar / Editar Regras para a Teoria do Domínio (TD);
•Motor de Inferência com produção de Explicações para: • provar que os exemplos satisfazem a TD e • derivar e guardar as árvores de prova
•Comparação das substituições das árvores de prova e produção da nova substituição Q
Page 15
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
EBL é do tipo Aprendizagem Analítica e tem a vantagem de bastar 1 ou poucos exemplo(s) de treino para aprender AA: “processa Conhecimento pre-existente e requer poucos exemplos providenciados exteriormente à Teoria conhecida
Alguns investigadores em EBL foram motivados pela observação de as pessoas são muitas vezes capazes de aprender uma regra ou conceito geral depois de observarem uma simples instancia desse conceito.
O método EBL está enviezado (inclinado para) fazer generalizações que possam ser explicadas em termos de um modelo do domínio do conhecimento.
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
OBJETIVO: Simplificar ( 1*(0+X) ) Background Knowledge: Reescreve(u,v) simplifica (v,w) simplifica(u,w). Primitiva(u) simplifica(u,u). Express_aritm_desconhecida(u) Primititiva(u). Numero(u) Primitiva(u). Reescreve(1*u,u). Reescreve(0+u,u).
Page 16
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Simplifica( 1*(0+X),w ) Reescreve(1*(0+X),v) Simplifica(0+X,w) {v/0+X}
Reescreve((0+X),v’) Simplifica(X,w) {v’/X} {w/X}
Primitiva(X) Express_aritm_desconhecida(X) Verdade w=X, {}
Generalizando: Qualquer que seja a variável z: Reescreve(1*(0+z),0+z) Reescreve((0+z),z) Express_aritm_desconhecida(z) Simplifica( 1*(0+z),z )
Reescreve(u,v) simplifica (v,w) simplifica(u,w). Primitiva(u) simplifica(u,u). Express_aritm_desconhecida(u) Primititiva(u). Numero(u) Primitiva(u). Reescreve(1*u,u). Reescreve(0+u,u).
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Generalizando: Reescreve(1*(0+z),0+z) Reescreve((0+z),z) Express_aritm_desconhecida(z) Simplifica( 1*(0+z),z )
As duas primeiras condições da regra são verdadeiras independentemente do valor de z A regra final aprendida foi: Express_aritm_desconhecida(z) Simplifica( 1*(0+z),z ) Casos em que não é verdade Express_aritm_desconhecida(z) já não simplifica: Se z=2*3 então Simplifica(1*(0+(2*3), (2*3)) não seria a melhor simplificação mas sim Simplifica(1*(0+(2*3), 6)
Page 17
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Algoritmos criando Árvores de Decisão (Algoritmos da família do ID3- Quinlan) O objetivo desta abordagem é a aquisição de Conhecimento através da construção automática de novas Regras de Conhecimento.
APRENDIZAGEM INDUTIVA
Identificados os atributos significativos (e respectivos valores possíveis) dos objetos do domínio considerado, é possível construir Árvores de Decisão (classificação desses Objetos).
Dessas Árvores obtêm-se Regras (conjuntos de nós que são passos entre a raíz da Árvore e as folhas). Várias Árvores (logo, vários conjuntos de Regras) se podem obter, dependendo da ordem em que foram considerados os nós (incluindo qual nó ficará na raíz).
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Ex. reconhecimento do tipo de aviões
TIPO de AVIÃO-----------------------------------------------------
atributo C130 C141 C5A B747motor prop jato jato jatopos-asa alto alto alto baixoforma-asa convenc. aguda aguda agudacauda convenc. forma T forma T convencionalsaliencias sob-asas sobre-asas não sobre-cockpit----------------------------------------------------------------------
Page 18
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
5 testes foram necessários Para esta classificação!
motor
jato prop.
forma-asa C130
pos-asas ?
B747 cauda
conv.
saliencias
C5A
C141
? ?
Ex. reconhecimento do tipo de aviões
TIPO de AVIÃO-----------------------------------------------------
atributo C130 C141 C5A B747motor prop jato jato jatopos-asa alto alto alto baixoforma-asa convenc. aguda aguda agudacauda convenc. forma T forma T convencionalsaliencias sob-asas sobre-asas não sobre-cockpit----------------------------------------------------------------------
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Reordenando:
motor
jact
o
prop.
pos-asa C130
bai
xa
alta
B747 saliencias
nao
sobre-asas
C5A C141
Aqui só 3 testes são necessários!!
Ex. reconhecimento do tipo de aviões
TIPO de AVIÃO-----------------------------------------------------
atributo C130 C141 C5A B747motor prop jato jato jatopos-asa alto alto alto baixoforma-asa convenc. aguda aguda agudacauda convenc. forma T forma T convencionalsaliencias sob-asas sobre-asas não sobre-cockpit----------------------------------------------------------------------
Page 19
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Melhor ainda:
Um Teste só!! saliencias
C5A C141 B747 C130
Ex. reconhecimento do tipo de aviões
TIPO de AVIÃO-----------------------------------------------------
atributo C130 C141 C5A B747motor prop jato jato jatopos-asa alto alto alto baixoforma-asa convenc. aguda aguda agudacauda convenc. forma T forma T convencionalsaliencias sob-asas sobre-asas não sobre-cockpit----------------------------------------------------------------------
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
REGRAS Derivadas de uma Árvore de Decisão do anterior Quadro
R1 - Se motor prop então C130 R2 - Se motor jato e pos-asa baixa então B747 R3 - Se motor jato e pos-asa alta e não saliencias então C5A R4 - Se motor jato e pos-asa alta e saliencias sobre-asa então C141
Page 20
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
O Algoritmo de Quinlan proporciona uma forma sistemática de desenvolver regras (Produções) relativamente eficientes e que se pode encontrar em alguns programas já comercializados.
Ex. Geração de um conjunto de Regras para um cenário simplificado sobre possibilidades de Investimento :
Oportunidades de Investimento :
- fundos de investimento em Circuitos Integrados - fundos de investimento em Minas de Ouro - fundos de investimento relacionados com construção de habitação
Objetivo : Para cada situação, determinar onde investir todas as economias.
Suposição : Valores esperados dos fundos de investimento numa de 3 classes: altos, médios, baixos.
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
O primeiro problema é como seleccionar os atributos descrevendo a situação (ainda uma arte). No exemplo considerado, Fatores de impacto no valor dos fundos: - taxas de juro - disponibilidade monetária na Europa, Estados Unidos e Japão
- grau de tensão internacional (operações militares, incidentes terroristas em perspectiva,…)
O algoritmo vai fazer um tratamento da informação previamente coligida (histórico). Considera-se uma tabela em que cada linha é um exemplo. A última coluna (resultado do valor dos Fundos) é o que as Regras induzidas deverão saber concluir para novos exemplos. Em terminologia dos algoritmos da família ID3, é a Classificação ou a Classe
Page 21
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
de Investimento
A abordagem deste algoritmo usa a medida da Entropia de cada atributo. Quanto mais alta a Entropia do atributo, mais incerteza há a respeito do interesse dos seus valores para a classificação. A selecção da ordem de consideração dos atributos na árvore de decisão será feita por ordem crescente das Entropias dos atributos
Tipo do Taxa de Disponib. Tensão Valor do Fundo Juro Monetar. Fundo _______________________________________________________________________________________
Circ. Int. alta alta média médio Circ. Int. baixa alta média alto Circ. Int. média baixa alta baixo Mina ouro alta alta média alto Mina ouro baixa alta média médio Mina ouro média baixa alta médio Construção alta alta média baixo Construção baixa alta média alto Construção média baixa alta baixo ___________________________________________________________________
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
A entropia da propriedade de classificação do Atributo a k é: H ( C / a k) = S( j =1,Mk)
p ( a k,j ) * [ - S (i =1,N) p ( C
i / a k,j ) * log 2 p ( C i / a k,j ) ]
p (a k,j ) é a probabilidade do atributo a k ter o valor j.
p ( C i / a k,j ) é a probabilidade do valor da classe sêr Ci quando atributo ak tem o valor j.
M k número total de valores do atributo a k N número total de classes diferentes (i=1..n) K número total de atributos (k varia de 1 a K)
Page 22
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
No exemplo dado: 4 atributos (K=4):
A1Tipo de Fundo(C.I., Ouro, Constr.) M1 = 3 A2Taxa_Juros (alto, médio, baixo) M2 = 3 A3DispMassa Monet. (alta, baixa) M3 = 2 A4Tensão_int (alta, média) M4 = 2
3 classes: Retorno (alto, médio, baixo) N=3
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Deve calcular-se a Entropia para cada atributo
H(C/A3)= H ( Classificação / disponib. monetaria) =
p ( d.m = alta ) * * [- (( p(alto, d.m. = alta ) . log
2 p (alto, dm = alta) ) +
( p(medio, d.m. = alta ) . log 2 p (medio, dm = alta) ) +
( p(baixo, d.m. = alta ) . log 2
p (baixo, dm = alta) ) )] + p ( d.m = baixa ) *
* [- (( p(alto, d.m. = baixa ) . log 2
p (alto, dm = baixa) ) + ( p(medio, d.m. = baixa ) . log 2 p (medio, dm = baixa) ) + ( p(baixo, d.m. = baixa ) . log
2 p (baixo, dm = baixa) ) )]
Tipo do Taxa de Disponib. Tensão Valor do Fundo Juro Monetar. Fundo _______________________________________________________________________________________
Circ. Int. alta alta média médio Circ. Int. baixa alta média alto Circ. Int. média baixa alta baixo Mina ouro alta alta média alto Mina ouro baixa alta média médio Mina ouro média baixa alta médio Construção alta alta média baixo Construção baixa alta média alto Construção média baixa alta baixo ___________________________________________________________________
Page 23
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
p(a 3,1 ) = 6 / 9 dm alta p(a 3,2 ) = 3 / 9 dm baixa
p(alto/alta) = 3 / 6 p(medio/alta) = 2 / 6 p(baixo/alta) = 1 / 6
p(alto/baixa) = 0 / 3 p(medio/baixa) = 1 / 3 p(baixo/baixa) = 2 / 3
H(C/dm) = 6 / 9 *[- 3 / 6 * log ( 3 / 6 ) - 2 / 6 * log ( 2 / 6 ) - 1 / 6 .log ( 1 / 6 ) ] +
3 / 9 * [ - 0 / 3 *log ( 0 / 3 ) - 1 / 3 * log ( 1 / 3 ) - 2 / 3 *log ( 2 / 3 ) ] = 1.2787
H ( C/ disponib. monetaria) = ? ( a partir da tabela)
Tipo do Taxa de Disponib. Tensão Valor do Fundo Juro Monetar. Fundo _______________________________________________________________________________________
Circ. Int. alta alta média médio Circ. Int. baixa alta média alto Circ. Int. média baixa alta baixo Mina ouro alta alta média alto Mina ouro baixa alta média médio Mina ouro média baixa alta médio Construção alta alta média baixo Construção baixa alta média alto Construção média baixa alta baixo ___________________________________________________________________
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Analogamente :
H(C/t_juros)= 1.14033 H(C/tensão)= 1.2787 H(C/tipo_fundo)= 1.14033
Podemos escolher como raíz da árvore quer t_juros quer tipo_fundo ( mínima entropia)
t_juros
se alta se média se baixa
classes: medio baixo alto
alto medio baixo
baixo alto baixo
Page 24
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Consideramos agora as sub-tabelas para cada valor da t_ juros (alta, média, baixa)
Ex: sub-tabela para t_juros=alta __________________________________________________________ tipo de fundo Disp. Monet. Tensão Valor do fundo __________________________________________________________ Circ. Int. alta média médio Minas ouro alta média alto construção alta média baixo __________________________________________________________
Calculemos de novo, agora para esta tabela, a entropia para cada atributo (disp_monet, tipo_fundo, tensão)
Tipo do Taxa de Disponib. Tensão Valor do Fundo Juro Monetar. Fundo _______________________________________________________________________________________
Circ. Int. alta alta média médio Circ. Int. baixa alta média alto Circ. Int. média baixa alta baixo Mina ouro alta alta média alto Mina ouro baixa alta média médio Mina ouro média baixa alta médio Construção alta alta média baixo Construção baixa alta média alto Construção média baixa alta baixo ___________________________________________________________________
t_juros
se alta se média se baixa
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
H ( classificação / tipo_fundo) = p ( tipo_fundo = constr. ) *
* [- (( p(alto, constr) . log 2 p (alto, constr) ) + ( p(medio, constr ) . log 2 p (medio, constr) ) + ( p(baixo, constr ) . log 2 p (baixo, constr) ) ) ] + p ( tipo_fundo = ouro ) *
* [- (( p(alto, ouro ) . log 2 p (alto, ouro) ) + ( p(medio, ouro ) . log 2 p (medio, ouro) ) + ( p(baixo, ouro ) . log 2 p (baixo, ouro) )) ] + p ( tipo_fundo = circ int ) *
* [- (( p(alto, circ int ) . log 2 p (alto,circ int ) ) + ( p(medio, circ int ) . log 2 p (medio, circ int ) ) + ( p(baixo, circ int ) . log 2 p (baixo, circ int ) )) ] =
= 1 / 3 * [ -( 0 + 0 + ( 1 * log 1) )] + 1 / 3 * [ -( 1 * log 1 + 0 + 0)] + 1 / 3 * [ -( 0 + 1 * log 1 + 0 )] = 1/3 * (-1*log 1 – 1*log 1 – 1* log 1) = 0
Ex: sub-tabela para t_juros alta __________________________________________________________ tipo de fundo Disp. Monet. Tensão Valor do fundo __________________________________________________________ Circ. Int. alta média médio Minas ouro alta média alto construção alta média baixo __________________________________________________________
Entropia do atributo tipo fundo é a mínima!
Page 25
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
H ( C/ak ) = S (j=1,Mk) p ( ak,j ) * [ - S (i=1,N) p ( Ci / a k,j ) * log2 p ( Ci / a k,j ) ] Quando a probabilidade é =1, o log2 é =0, logo temos a entropia mínima. Ou seja o contrário do caos (tudo ordenado).
Quando a probabilidade p=0 então o log2 tende para – infinito
0 * -infinito é uma indeterminação que se deve levantar lim p0 log2 p * p = lim p0 (log2 p * 1/(1/p)) Aplicando a Regra de l’Hôpital para levantar a indeterminação: lim p0 (d/dp (log2 p) ) / lim p0 (d/dp (1/p)) = lim p0 (c*1/p) / lim p0 ((1-0)/p2) =c* p2 /p lim p0 c*p=0
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Ex: sub-tabela para t_juros alta __________________________________________________________ tipo de fundo Disp. Monet. Tensão Valor do fundo __________________________________________________________ Circ. Int. alta média médio Minas ouro alta média alto construção alta média baixo __________________________________________________________
H (classificação/disponibilidade monetária) = p ( disp_mon= alta. ) *
* [- ( p(alto, dm=alta) . log 2 p (alto, dm=alta) ) +
( p(medio, dm=alta) . log 2 p (medio, dm=alta) ) +
( p(baixo, dm=alta) . log 2 p (baixo, dm=alta) ) ]
=1* [ -(1/3 *log(1/3) -(1/3 *log(1/3) - (1/3 *log(1/3)]
= - log(1/3) * (1/3+1/3+1/3)= - ( log(1) –log(3) )=log(3)>0
Page 26
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
seguiam- se cálculos idênticos para os outros atributos (tensão). (?) idem para as outras sub-tabelas (t_juros média, t_juros baixa). "deveria concluir-se" que em qualquer dos casos o atributo seguinte com entropia mínima (0), era o tipo de fundo de investimento! Daí que a árvore agora se ramifique de acordo com o atributo "tipo de fundo".
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
t_Juros
alta media baixa
tipo fundo
tipo fundo
tipo fundo
baixo medio alto baixo baixo medio alto alto medio
Page 27
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Bastaram 2 atributos (taxa de juros e tipo de fundos) para a classificação O conjunto de regras resultante é:
R1: SE t_juros=alta E tipo=const ENTÃO valor fundo=baixo R2: SE t_juros=alta E tipo=c. int. ENTÃO valor fundo=medio R3: SE t_juros=alta E tipo=ouro ENTÃO valor fundo=alto R4: SE t_juros=media E tipo= const ENTÃO valor fundo=baixo R5: SE t_juros=media E tipo= c.int ENTÃO valor fundo=baixo R6: SE t_juros=media E tipo=ouro ENTÃO valor fundo=medio R7: SE t_juros=baixa E tipo=const ENTÃO valor fundo=alto R8: SE t_juros=baixa E tipo=c.int ENTÃO valor fundo=alto R9: SE t_juros=baixa E tipo=ouro ENTÃO valor fundo=medio
Por exemplo as regras R6 e R9 podem combinar-se: R 6/9 = SE tipo=ouro E ( t_juros=media OU t_juros=baixa) ENTÃO Valor fundo=medio R 1/4 = SE tipo=const E (t_juros=alta OU t_juros=media) ENTÂO Valor fundo=baixo
t_Juros
alta media baixa
tipo fundo
tipo fundo
tipo fundo
baixo medio alto baixo baixo medio alto alto medio
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
O facto de em um nível da árvore aparecer o mesmo atributo (2º nível, tipo de fundo) foi apenas uma COINCIDÊNCIA derivada da tabela de exemplos simples. De notar também que usamos sempre valores discretos (logo de variação não contínua). Este algoritmo, ID3, pode levar a enormes árvores que por sua vez não levam necessariamente a melhores Bases de Regras.
Page 28
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Para “podar” as árvores, Quinlan desenvolveu outros algoritmos como o C4.5. Não só diminuiu assim o número de testes necessários como aumentou a proporção de classificações corretas. ID3 tem vários problemas (só trata valores discretos, produz árvores frondosas) e só é válido para problemas de diagnóstico.
Ao tentar minimizar o número de atributos na árvore de decisão pode estar a perder-se informação. É preciso pesar, em cada caso, vantagens e desvantagens da “poda”. As regras induzidas não são hierárquicas mas planas. Resultam todas numa conclusão final. Um especialista tiraria antes conclusões intermédias e só depois as finais.
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Agoritmos de Aprendizagem Indutiva
C4.5
Bibliografia: C4.5 Programs for Machine Learning, Ross Quinlan, Morgan Kaufmann, 1998
Page 29
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
C4.5 Consideremos exemplos relacionados com doentes da Tiroide. Os casos são expressos por vários indicadores cujos valores são (Verdadeiro ou Falso) mais seis testes laboratoriais representados por reais ou inequações (<0.1 ou >200). Foram considerados 15 diagnósticos.
Exemplo de um caso:
Indicadores: idade ---------------------- 27 sexo ----------------------- Fem tyroxina ------------------- V medicação anti-tiroide ---- F cirurgia-tiroide ------------ F Hipotiroide ---------------- F Hipertiroide --------------- F grávida -------------------- V doente --------------------- F tumor ---------------------- F litio ------------------------ F inchaço -------------------- F
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Testes:
TSH (thyrotropin) ------------------- 30 T3 (tri-iodotyronina) ---------------- 33 TT4 (total tyroxina) ----------------- 70 T4U (tyroxina "uptake") ------------ 1.71 FTI (free tyroxina fundex) ---------- 41 TBG (tyroxina binding globulina) --- não perguntado
Interpretação:
T3 e T4U elevados consistente com gravidez. TSH elevado e FTI baixo sugerem "fraca substituição" (under-replacement)
Diagnóstico:
TBG elevado, grávida, efeito de estrogéneo, baixa substituição de tiroxina.
Page 30
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Começa-se por descrever os items (exemplos) através de um conjunto de atributos. Esses Atributos são aqui de dois tipos diferentes: • Atributos com valores num pequeno conjunto discreto (exs:cirurgia-tiróide, sexo) • Atributos com valores no conjunto dos Reais (ex:T4U) • Os Atributos poderão ainda ter valores desconhecidos.
A descrição do caso chama-se “item”. A sua classificação é em uma Classe. Supomos que a Classificação de cada item é mutuamente exclusiva. Só pertence a uma Classe
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
O problema agora é: Dado um conjunto de itens cuja Classe é conhecida, usá-lo no treino do algoritmo para encontrar Regras de Classificação aplicáveis a outros itens.
As Regras devem poder aplicar-se não só aos itens (objetos, exemplos) do conjunto de treino mas também a futuros itens (objetos, exemplos). Isto é, as Regras devem ser mais gerais que as descrições disponíveis. C4.5 expressa essas Regras na forma de Árvore de Decisão (AD)
Page 31
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
C4.5
Seleccionar a Árvore podada mais promissora
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
O coração do algorítmo é "Formar Àrvore" que constrói de maneira recursiva a Árvore de Decisão (AD).
Seja C uma colecção de itens: Se " c C forem da mesma classe, a AD é uma folha. Senão
seja T um teste de valor de um atributo cujos valores possíveis são {O1, O2,..., On} (se o atributo A for continuo, consideramos testes da forma A<K, A>K, Se o atributo A for discreto, os testes são da forma A=Oi ( i=1,2,....,n)
Então T parte C em subconjuntos {C1,...,Cn} cada um correspondendo a um possível valor (ou conjº de valores) do atributo
O1 : C1 O2 : C2 ....... ...... On : Cn
Page 32
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Cada sub-conjunto é substituído por uma (sub) Árvore de Decisão. Quando há ruído não é necessário continuar a divisão da árvore até que todos os membros do conjunto C das folhas fiquem na mesma classe. Usa-se um “Critério de Paragem ”. No caso de faltarem valores para o atributo a ser testado, também a partição de C resulta mais complexa.
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
A escolha do teste T é crucial para que a árvore seja simples. O critério de selecção do C4 .5 : “Critério da Razão do Ganho” (Gain Ratio Criterion) baseia-se, para cada teste T, no Ganho de Informação de classificação. O algoritmo C4.5 escolhe sempre um teste T que maximize esta “Razão”
Page 33
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
No Algorítmo C4.5, o sub-algoritmo “Formar Árvore” aplica-se inicialmente a subconjuntos (10 a 15% do conjunto de treino). Uma primeira Árvore de Decisão é formada e usada para classificar os restantes elementos. Depois vão-se adicionando alguns exemplos mal classificados e nova árvore é construída. Quando nenhuma melhoria é conseguida com algumas iterações sucessivas, o processo para.
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Devido à existência de ruído, a árvore torna-se complicada e pode levar a erros. Deve-se podar várias sub-árvores mais complexas reduzindo-as a folhas.
C4.5 poda a árvore usando informação do conjunto de treino. Seja S uma sub-árvore da Árvore de Decisão: C4.5 repetidamente calcula, para cada sub-árvore S, a sua razão entre aumento de erro (se podada) e a complexidade (se mantida) e, sendo a razão inferior à da média das outras sub-árvores, substitui-a por uma folha.
Page 34
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Outro processo de “podar” árvores de decisão diferente do proposto por Breiman (Cost Complex Prunning) é o da poda pessimista
Seja uma folha de uma Árvore de Decisão que está a classificar n elementos de um conjunto e seja e o numero de erros de classificação, isto é, e é o nº de elementos dos n que pertencem realmente a outra classe que não a representada por aquela folha. e/n daria uma razão de erro da folha. Mas, por exemplo, para n=1 e e=0 pareceria uma boa folha (razão e/n=0) e, no entanto, não será razoável esperar que, nos casos futuros, estes vão ser todos bem classificados.
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
A confiança na folha pode também ser dada por: (e+1)/(n+2) Exemplos usando a razão do erro e/n : a) Folha classificando 1 caso com zero erros: 0/1=0 b) Folha classificando 10 casos com 1 erro: 1/10 A primeira folha (caso a) ) parece melhor e provavelmente não é!
Exemplos usando (e+1)/(n+2) : a) Folha classificando 1 caso com zero erros: 0+1/1+2=1/3 b) Folha classificando 10 casos com 1 erro: 1+1/10+2=1/6 A segunda folha parece melhor (razão do erro, inferior) e provavelmente é!
Page 35
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
É portanto melhor calcular a confiança na folha por: (e+1)/(n+2) Então a razão de erro “pessimista” de uma sub-árvore é a média das razões de erro das suas folhas, pesadas pela frequência relativa do número de casos do conjunto de treino que elas cobrem. O processo de poda substitui então todas as sub-árvores que não aumentam significativamente o previsível erro da árvore. O ciclo exterior do algorimo C4.5 repete um certo número de vezes (usualmente 10 vezes) os procedimentos “crescimento da árvore” e “poda”.
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Melhoria do Critério de escolha do Atributo para Teste de Separação Critério do GANHO DE INFORMAÇÃO pelo Teste T (Atributo Ai ) =
info(C) -info(C/Ai) onde: info(C) Informação média para identificar Classes Ck no Conjunto C de itens (independente do Atributo) Info(C) = Sk=1..n p(Ck) * (-log2 p(Ck)) (a informação é medida em bits) info(C/Ai) Entropia do Atributo Ai em relação à Classificação no Conjunto de Treino C
Page 36
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Melhoria do Critério de escolha do Atributo para Teste de Separação Critério do GANHO DE INFORMAÇÃO pelo Teste T (Atributo Ai ) = info(C) -info(C/Ai)
Ex:(jogar golf…) Atributo “estado do céu” para classes “Joga” e “Não Joga” Valores das Classes: Classes(J e NJ) 9 J 5NJ Total 14 itens Valores do Atributo (e_d_c) Valores das Classes Sol J (2) NJ (3) Nublado J (4) NJ (0) Chuva J (3) NJ (2) info(C)= -9/14*log2(9/14) -5/14*log2(5/14) = 0.940 bits
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Info (C/Ai)= (S (j=1 a n) |Cj|/|C| * Info(Cj) Cj são os sub-conjuntos do Conjunto de Treino C, resultantes de aplicar um Teste (qual estado do céu?) ao atributo Ai (Céu) ( Csol, Cnublado, Cchuva )
Info(C/Ai) = 5/14 * [-2/5*log2(2/5) -3/5*log2(3/5)] + Info(C/céu) 4/14 * [-4/4*log2(4/4)-0*log2 0] + 5/14 * [-3/5*log2(3/5) -2/5*log2(2/5) = 0.694 bits info(C/Ai) = 0.694 bits
Ganho de Informação pelo Teste Ti (do Atributo Ai=céu) = info(C) - info(C/Ai) = = 0.940 - 0.694 = 0.246bits
Page 37
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Dá bons resultados mas sobrevaloriza testes com muitos valores possíveis.
Para normalizar de acordo com os resultados do teste do atributo usa-
-se a Informação de Separação (informação obtida dos resultados de um teste Ti com j=1 a n valores, independentemente de serem ou não da mesma classe):
A medida do Ganho :
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Então temos o Critério da Razão do Ganho = Ganho / Info de Separação
onde Info de Separação= - S (i=1 a n) |Ci| / |C| * log2(|Ci| / |C|) = 1.577 bits
Sendo n o número de Valores possíveis do atributo relativa ao teste
Teste T (Atributo Ai) é escolhido de forma a maximizar a Razão do Ganho
Info de Separação = -( 5/14 * log(5/14) + 4/14*log(4/14) + 5/14*log(5/14) )= 1.577
Não confundir com Info (C/Ai)= (S (j=1 a n) |Cj|/|C| * Info(Cj)
Razão do Ganho (Atributo Ai=céu) = 0.246 / 1.577 = 0.156
Page 38
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
ex: Se para um dos itens do atributo “estado do céu” de valor antes considerado nublado agora é desconhecido: de 14 passamos a 13 valores conhecidos do atributo para os 14 exemplos: Sol : 5 (2J + 3NJ) Nublado: 3 (3J) Chuva: 5 (3J + 2NJ) J=8 e NJ=5 13 valores conhecidos
Existindo Valores desconhecidos para o Atributo Ai: Aumenta a informação necessária para a discriminação e Diminui o Ganho devido ao teste por Ai
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Sol : 5 (2J + 3NJ) Nublado: 3 (3J) Chuva: 5 (3J + 2NJ) J=8 e NJ=5
Info(C) = - 8/13*log(8/13) - 5/13*log(5/13) = 0.961 bits (antes era 0.940)
Info(C/Ai) = 0.747 bits
( a entropia aumentou devido à falta de um valor. Antes era 0.694)
Ganho(Ai) = Frequência dos conhecidos * Ganho = 13/14*(0.961-0.747)=0.199
(antes era 0.246)
Existindo Valores desconhecidos para o Atributo Ai:
Page 39
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Info separação (consideram-se os 14 casos incluindo “?”, j=4) = 1.809 bits
Razão do Ganho= 0.199/ 1.809 = 0.110 ou seja Baixou!! (antes era 0.156)
Então deve-se distribuir os valores desconhecidos probabilisticamente pelos valores conhecidos de acordo com as respectivas frequências:
O valor desconhecido (“?” para o estado do céu) será considerado:
Sol com prob 5/13
Nublado com prob 3/13
Chuva com prob 5/13
Nas expressões anteriores consideravam-se agora as frequências de
Sol=(5+5/13)/14,
Nublado=(3+3/13)/14
Chuva=(5+5/13)/14
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
TESTE PARA ATRIBUTOS COM VALORES CONTÍNUOS
Dados: Atributos Ai com m Valores no conjunto de treino em análise, ordenados {v1, v2, ..., vm} há m-1 possíveis divisões (entre v1 e v2 ou entre v2 e v3 ...)
Escolhem-se para análise todos os pontos intermédios vt=(vi + vi+1 ) / 2
No C4.5 considera-se o maior valor existente na totalidade do conj. de treino ainda menor que esse(s) ponto(s) intermédio(s) para pontos de corte
Procedimento para atributos de valores contínuos:
1º Ordenar os m valores do atributo do conjunto
2º Considerar todos os valores de teste (pontos de corte) possíveis
3º Calcular o Ganho (e a Razão do Ganho) do atributo Ai para cada teste do atributo
4º escolher o valor de corte que der o maior Ganho (ou Razão de Ganho)
5º O Teste do valor do atributo faz-se em relação ao valor escolhido em 4º
Page 40
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
Em Conclusão: C4.5 é um algoritmo poderoso de inferência indutiva para a construção de Árvores de Decisão a partir de objetos descritos por um conjunto fixo de atributos. Esses atributos podem ter valores num domínio contínuo ou discreto, podem incluir ou não ruído e pode acontecer que alguns valores estejam em falta . O critério de escolha dos atributos para nós da Árvore de Decisão é o da Razão do Ganho
Eugénio Oliveira / FEUP
Aprendizagem Simbólica Automática
MIEIC/Aprendizagem Simbólica
IA
Est Lóg 1ªO LNM LMo
M.Fracos M.Informados Pesq Adv.
pl
pp
bb s.a. AG sc A* Mm ab
Mist
EBG
IOE
Ind
ID3
C4.5
Por Ref.
Q
sarsa
RN
Repr. Conh. Mét.Resol.Prob. Aquis. Conh.
SP
SBC Ag SMA Outras
Arquitecturas
Conh.
Simb Inf.
Sub-Simb
APLICAÇÕES id
Rac.Inc.
RB DS FC FS