Aprendizado de Conceitos
(aprendizado de regras)
Introdução
• Aprender uma definição de uma categoria
• Dado um conjunto de treinamento positivos e negativos
• Problema de busca através de um espaço
predefinido de hipóteses potenciais.
• Ordenação do espaço de busca
Exemplo
Qual é o conceito ???
Céu
Temp
Humed Vento
Água
Prev
Esporte
Sol
Temp
Normal Forte
Temp
Igual
S
Sol
Temp
Alta
Forte
Temp
Igual
S
Chuva
Frio
Alta
Forte
Temp
Muda
N
Sol
Temp
Alta
Forte
Fria
Muda
S
Aprendizado de Descrições Lógicas
• Aprendizado inductivo pode ser visto como um
processo de busca de uma boa hipoteses num
grande espaço.
• O espaço de hipoteses, definido pela linguagem de
representação escolhida para a tarefa.
• No termo lógico a relação entre hipoteses, objetivos e
exemplos.
Representação da Hipóteses
• Muitas possibilidades de representações
• Aqui h é uma conjunção de restrições sobre os
atributos
• Cada restrição pode ser
• Um valor especifico (Água = Temp)
• Não interessa (Água = ?)
• Nenhum valor é permitido (Agua = #)
• Exemplo
• (Sol, ?, ?, Forte, ?, Igual)
Tarefa de Aprendizado de Conceitos
• Dado
• Instâncias X: Dias, descritos por seus atributos, Céu....
• Função Alvo c: Esporte : X -> {0,1}
• Hipóteses H: Conjunção de literais, ex
:(?,Frio,Forte,?,?,?)
• Exemplos de treinamento D
• (x1,c(x1)), (x2,c(x2)), (x3,c(x3)),... (xn,c(xn)),
• Determine: A Hipótese h em H tal que
• h(x) = c(x) para todo x em D
Extensão de uma hipoteses
• Cada hipoteses prediz um certo conjunto de
exemplos. Os que satisfacem sua definição
• Duas hipoteses são diferentes => suas extensões
são inconsistentes.
• Logicamente falando, um exemplo é um objeto ao
qual o conceito objetivo se aplica ou não. Ele tem
uma descrição lógica.
Consistência
• Hi é consistente com todos os exemplos de
treinamento => consistente com cada exemplo
• Um exemplo pode ser falso - para a hipótese
• Se a hipótese afirma ser negativo mais de fato é +
• Um exemplo pode ser um falso positivo para a
hipótese, se a hipótese diz que é positivo mais o
exemplo é negativo.
Busca pela melhor hipoteses
• Manter uma hipoteses única e ajustar ela a novos
exemplos de maneira a manter consistência.
--- - -
--- - -
- +++ - - +++ - +++ - - +++ - +++ - - +++ -
+
------
Espaço
consistente
------
Falso
negativo
--- - -
--- - -
- +++ - +++ - +++ +
- +++ - -++ - +++ +
------
------
Hipoteses
Falso
generalizada positivo
--- - -
+++ -- + + +++ -
+
------
Hipoteses
especializada
Espaço de Classes conceituais
• Parcialmente ordenado
T, a mais
geral
(#,#,#,#,#)
F, a mais
especifica
(?,?,?,?,?)
Instâncias, Hipótese e mais Geral que
Instâncias
Hipótese
Especifico
Genérico
X1 = <sol,temp,alto,forte,fria,igual>
X2= <sol,temp,alto,suave,temp,igual>
h2 é mais geral que h3
h1 = <sol,?,?,forte,?,?>
h2= <sol,?,?,?,?,?>
h3= <sol,?,?,?,fria,?>
Indução não incremental de CL
• Bredth-first search (EGS, G->S)
• a cada nivel EGS considera todas as especializações de
uma H, com + 1 condição.
• Para cada especialização gerada H
• H cobre todos os exemplos + , cc ela é retirada.
• Se H ainda cobre algum exemplo negativo, será
novamente especializada no proximo ciclo, se não H é
consistente.
Algoritmo: EGS
+
-
+
-
Problemas
• Complexidade computacional
• Ruído nos dados
FIND-S
• Começar com a hipótese mais especifica possível
em H, então generalizar esta hipótese cada vez que
falhe em cobrir um exemplo positivo.
• Algoritmo
• Inicializar h, hipótese mais especifica em H
• Para cada restrição num atributo ai em h
• Se ai em h é satisfeita por x não faça nada
• CC substitua ai em h por a próxima restrição mais geral
satisfeita por x
• Saída hipótese h
FIND-S
Instâncias
Hipótese
Especifico
Geral
X1 = <sol,temp,normal,forte,temp,igual>,+
X2= <sol,temp,alto ,forte,temp,igual>,+
X3 = <chove,frio,alto,forte,temp,muda>,X4= <sol,temp,alto ,forte,frio,muda>,+
h0 =<#,#,#,#,#,#>
h1 = <sol,temp,normal,forte,temp,igual>
h2 = <sol,temp,?
,forte,temp,igual>
h3 = <sol,temp,?
,forte,temp,igual>
h4 = <sol,temp,?
,forte,?
,? >
Problemas
• Uma hipótese única, a mais especifica
• Ruído nos dados
• Memória para manter todos o conjunto de
treinamento
Indução Incremental IGS
• Um caso de treinamento por vez, guarda-se Hs
consistentes com exemplos.
• Inicializa com T
• encontra e-, abandona as hi tal que hi->e-, substituindo
por uma variante
• Abandona qualquer hi tal que hi ~->e+.
• Obs: guarda e reprocessa explicitamente a lista de
exemplos +, fazendo uma aproximação incremental
somente com respecto a exemplos -.
Algoritmo: IGS
+
-
+
-
Algoritmo ISG
• Estrutura básica similar a IGS
• Esta tecnica retem um conjunto de descrições que são
consistentes com as instâncias observadas
• Inicializa o conjunto de Hs a 1a instância positiva do conjunto
de treinamento
• frente a uma instância + , verfica as Hs, substituindo as
inconsistentes por "minimas"mais gerais
• ISG abandona as Hs que cobrem instâncias negativas, e Hs
mais especificas que outras.
• O ciclo ISG usa e+ para gerar Hs e e- para abandonar Hs
Tecnicas Bidirecionais
• Combinação de S->G e G->S
• Neste caso, ou G ou S atua como operador
primario, sendo que o outro efetua backtracking
Tecnicas Bidirecionais
• Outra alternativa, espaço de versão, que IGS e ISG
• 2 conjuntos de descrições (S,G)
• ISG atualiza S, quando encontra e+
• IGS atualiza G, quando encontra e• não é necessário reter as instâncias + nem • IGS apaga os membros de G que são mais especificos
que todos os membros de S, similar ISG com S.
Problemas dos Métodos I. Exaustivos
• ISG, IGS, Bidireccionais guardam em memoria
todas as descrições consistentes com os dados
• Em alguns dominios o tamanho do conjunto pode
crecer exponencialmente
• Problemas com ruído e com conceitos que não são
uma conjunção lógica
HGS(G->S)
• Manipula dois conjuntos
• Closed (H, sem melhora)
• Open (H, podem ser melhoradas)
• A cada estagio HGS considera todas as
especializações de Hset com + 1 condição (S)
• S -> f(S)
• Se f(S) > f(H), Open-set = Open-set +S
• Se " S f(S) < f(H) , H -> Closed-set
HGS
 Depois de considerar todas as especializações das
descrições em Hset
Se existem H em Open-set continua,
Se não retorna H com maior score.
 Avaliação heuristica
ex: Pc + Nnc/(P+N) (0,1)
Problemas de HGS
• HGS ou HSG
• custo de memoria fixo
• busca sobre controle, mais não sempre gera a descrição
otima para um conjunto de dados
• relativamente robusta com respeito a ruido, e a hipoteses
que são aproximadamente conjuntivas
• em HSG deve-se cuidar o exemplo inicial usado.
Método Hill Climbing
• Minimizar o processamento para cada nova
instância, reduzir memoria requerida
• Ideia: Guardar uma hipoteses
• Hill Climbing
• metodo de busca clássico de IA
• se aplicam todos os possiveis operadores
• comparam os resultados, função de avaliação
• seleciona-se o melhor, iterar até não obter progressos
Algoritmo IHC
• Para cada instância I, o método verifica se H classifica
corretamente
• Se correto, IHC não atua
• Se errado, IHC gera todas as revisões de H que corrigem
o erro
• usa f para ordenar as candidatas, nos últimos K casos
• A melhor é comparada com H pai, fica a melhor
• O caso mais antigo é substituido pelo novo
• O processo continua ate que existam instâncias
Algoritmo IHC
• O algoritmo responde diferente se e+ ou e• e-, IHC diz e+, H é geral demais, -> S
• e+, IHC diz e-, H é muito especifica, -> G
• Formas de inicialização
• a mais geral
• o primeiro exemplo
IHC +em operação
-
(1+1)/2=1
(1+2)/3=1
-
+
(1+1)/2=1
(1+2)/3=1
(1+1)/3=2/3
-
(1+2)/3=1
(0+1)/2=0.5
(0+2)/3=2/3
(0+1)/3=1/3
(0+2)/3=2/3
(0+1)/2=0.5
(0+2)/3=2/3
Comentarios IHC
• Baixos requisitos de memória e processamento
• Uma hipótese
• Sensibilidade a ordem no treinamento, maior
quantidade de instâncias de treinamento para
convergência
• Menos sensitivo a ruído
Exercicios
Construção de listas de decisão
• Os tópicos anteriores tratam de indução de
conceitos que podem ser descritos usando uma
única região de decisão
• Neste tópico se tratará da indução de descrições
disjuntivas (v)
Múltiplas regiões
Peso
+ +
-
+ + +
+
+
Altura
Construção de listas de decisão
Construção de listas de decisão
• Forma normal disjuntiva FND
• combina um conjunto de descrições D1,D2,..Dn em uma
disjunção {D1vD2v..Dn }
• as vezes mais de uma classe "match"uma instância
• criar descrições mutualmente exclusivas
• precedência, lista ordenada
A tarefa de indução disjuntiva
• Dado: Um conjunto de instâncias de treinamento,
cada uma com sua classe associada
• Encontrar: Uma descrição disjuntiva que,
corretamente classifique instâncias não
observadas
• Ao menos para algumas representações, o espaço
de FND é parcialmente ordenado (G->S), mas o
fator de ramificação é muito grande
Aprendizado não-incremental
Dividir e Conquistar (NDC)
• Tarefa de discriminar entre duas classes
• construir a FND de uma classe e usar a outra como
default. Tecnicamente o resultado é uma lista de decisão.
NDC usando HSG
Peso
Pes
o
+
+
+
+
-
-
+
+
Altura
-
+
+
Altura
-
NDC
• Entrada:
• Pset, conjunto de instâncias +
• Nset, conjunto de instâncias • FND uma disjunção de uma descrição de uma única região
• Saída: Uma disjunção de uma única região
• Nivel-Top chamada: NDC(Pset,Nset,{})
• Procedimento NDC(Pset,Nset,FND)
• Se Pset esta vazio Então retorne FND
• CC Encontre uma região D que cobra algumas instâncias em
Pset e não em Nset, FND=FND+D, Pset=Pset-{D->}
• Retorne NDC(Pset,Nset,DNF)
MDC
• NDC é projetado para inducir expressões para
uma única classe
• MDC utiliza NDC como bloco de construção para
mais de duas classes
MDC
• Entrada: Cset é conjunto dos nomes das classes, Iset é o
conjunto das instâncias de treinamento.
• Saída: uma lista de decisão
• Procedimento MDC(Cset,Iset)
• Rule-set = {}
• Para cada Classe em Cset,
• Pset = {i Iset e i  Classe}, Nset = {i Iset e i 
Classe}, FND = NDC(Pset,Nset,{}).
• Para cada termo D em FND, Rule-set =Rule-set + Se D
então Classe
• Elimine possiveis conflitos entre descrições de classe,
retorne Rule-set
Indução Incremental usando
Dividir para conquistar (IDC)
• Utiliza ideias de Hill Climbing
• Guarda uma única hipoteses em memoria (um
conjunto de termos lógicos disjuntivo)
• Guarda as k últimas instâncias de treinamento,
para avaliar as hipoteses
• Revisa suas hipoteses somente quando realiza um
erro de classificação
• IDC utiliza a função de avaliação para escolher
Revisões em IDC
 Erro de classificação de uma instância positiva,
generalizar a hipoteses
• modificar um termo da FND; remover um teste
booleano, nominal ou características numericas,
Aumentar o tamanho do retangulo ou mudanças nos
pesos
• Como a hipoteses pode ter multiples termos, IDC pode
aplicar generalização a cada um deles
• Outra alternativa envolve em adicionar um termo novo
(a descrição da instância ou a descrição mais geral que
não case com os exemplos negativos)
Revisões em IDC
• Erro de classificação de uma instância negativa,
especializar a hipoteses
• modificar cada termo da FND que case com a
instância; adicionar um teste booleano, nominal
ou características numericas, diminuir o tamanho
do retangulo ou mudanças nos pesos
• Outra alternativa envolve em eliminar um termo
Função de Avaliação
• Incluir uma medida da simplicidade da expresão e
de precisão
• simplicidade 1/t , t número de termos
• precisão a = (Pc + N~c)/k
• F = a + 1/t ou F = (1-w)a + w 1/t , w entre 0 e 1
Comportamento de IDC
+
+
1/1+1/1=2
2/2+1/1=2
1/2+2/2=1,5
v
-
2/3+1/1=5/3
1/1+2/3=5/3
+
3/4+1/1=7/4
+
4/4+1/2=3/2
V
+
4/4+1/2=3/2
V
Problemas
• Métodos que utilizam "Hill Climbing" possuem
baixos requisitos de memoria e processamento
• Eles consideram somente uma hipoteses
• Sensibilidade a ordem das instâncias de
treinamento, maior número de casos para
convergência
• Pode não converger e em ambiente com ruido
podem abandonar sua boas hipoteses