Plano de Aula
Introdução
“ Teorema de Bayes e Aprendizagem Conceitual
“ Classificador Ótimo de Bayes
“ Algoritmo de Gibbs
“ Classificador Naïve Bayes
“ Exemplos
“ Resumo
Aprendizagem de Máquina
“
Aprendizagem Bayesiana
Aula 4
Alessandro L. Koerich
Mestrado em Informática Aplicada
Pontifícia Universidade Católica do Paraná (PUCPR)
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Referências
“
Mitchell T. Machine Learning. WCB McGraw–
Hill, 1997. Capítulo 6.
“
Theodoridis S., Koutroumbas K. Pattern
Recognition. Academic Press, 1999. Capítulo 2
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
2
Introdução
Duda R., Hart P., Stork D. Pattern
Classification 2ed. Willey Interscience, 2002.
Capítulos 2 & 3
“
Aprendizagem de Máquina
3
“
O pensamento Bayesiano fornece uma
abordagem probabilística para aprendizagem
“
Está baseado na suposição de que as
quantidades de interesse são reguladas por
distribuições de probabilidade.
“
Distribuições de probabilidade: Ver documento
em anexo.
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
4
Introdução
“
“
Introdução
Decisões ótimas podem ser tomadas com base
nestas probabilidades conjuntamente com os
dados observados.
“
Os métodos Bayesianos são relevantes por dois
motivos:
1. Fornecem algoritmos de aprendizagem
práticos:
Fornece uma solução quantitativa ponderando
a evidência suportando hipóteses alternativas.
“
“
“
Fornece a base para algoritmos de
aprendizagem que manipulam probabilidades
bem como outros algoritmos que não
manipulam probabilidades explicitamente.
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
“
“
5
Alessandro L. Koerich ([email protected])
2. Fornecem uma estrutura conceitual útil:
“
“
Cada exemplo de treinamento pode decrementar ou
incrementar incrementalmente a probabilidade de
uma hipótese ser correta.
2.
Conhecimento a priori pode ser combinado com os
dados observados para determinar a probabilidade de
uma hipótese.
3.
Métodos Bayesianos podem acomodar hipóteses que
fazem predições probabilísticas (Ex: Este paciente tem
uma chance de 93% de se recuperar)
Percepção adicional dentro do Occam’s razor
Norma de Ouro: menor erro possível
Mestrado em Informática Aplicada
Aprendizagem de Máquina
Aprendizagem de Máquina
1.
Fornece “norma de ouro” para avaliar outros
algoritmos de aprendizagem
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
6
Características da Aprendizagem
Bayesiana
Introdução
“
Aprendizagem Naïve Bayes
Aprendizagem de Redes Bayesianas
Combinam conhecimento a priori com os dados
observados
Requerem probabilidades a priori
7
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
8
Características da Aprendizagem
Bayesiana
4.
Dificuldades Práticas
Novas instâncias podem ser classificadas
combinando a probabilidade de múltiplas
hipóteses ponderadas pelas suas
probabilidades.
“
Métodos Bayesianos requerem o conhecimento
inicial de várias probabilidades.
“
“
Custo computacional significativo para
determinar a hipótese ótima de Bayes
“
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
9
Quando não conhecidas, podem ser estimadas a
partir de conhecimento prévio, dados previamente
disponíveis e suposições a respeito da forma da
distribuição.
É geralmente linear com o número de hipóteses
Alessandro L. Koerich ([email protected])
Teorema de Bayes
P(h|D): probabilidade de h dado D
P(D): probabilidade a priori dos dados de treinamento D
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
11
10
“
P(h|D) é chamada de probabilidade a posteriori
de h porque ela reflete nossa confiança que h se
mantenha após termos observado o dado de
treinamento D.
“
P(h|D) reflete a influência do dado de
treinamento D.
“
Em contraste, a probabilidade a priori P(h) é
independente de D.
P(h): probabilidade a priori da hipótese h
P ( D | h )P (h )
P(D)
Aprendizagem de Máquina
Teorema de Bayes
P(D|h): probabilidade de D dado h.
P (h | D ) =
Mestrado em Informática Aplicada
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
12
Teorema de Bayes
“
“
Geralmente queremos encontrar a hipótese
mais provável h ∈ H, sendo fornecidos os dados
de treinamento D.
Teorema de Bayes
“
Desprezamos o termo P(D) porque ele é uma
constante independente de h.
“
Se assumirmos que cada hipótese em H é
igualmente provável a priori, i.e.
Ou seja, a hipótese com o máximo a posteriori
(MAP)
h MAP ≡ arg max P ( h | D )
P(hi) = P(hj) ∀ hi e hj em H
h∈H
P ( D | h ) P (h )
P(D)
h∈H
= arg max P ( D | h ) P ( h )
= arg max
“
h∈H
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
13
Então, podemos simplificar mais e escolher a
hipótese de máxima probabilidade condicional
(maximum likelihood = ML).
Alessandro L. Koerich ([email protected])
Teorema de Bayes
“
O termo P(D|h) é chamado de probabilidade
condicional (ou likelihood) de D
“
Sendo fornecido h, qualquer hipótese que
maximiza P(D|h) é chamada de uma hipótese
ML.
2.
“
Mestrado em Informática Aplicada
“
Aprendizagem de Máquina
15
O paciente tem câncer
O paciente não tem câncer
Os dados disponíveis são de um exame de
laboratório com dois resultados possíveis:
“
Alessandro L. Koerich ([email protected])
14
Considere um problema de diagnóstico
médico onde existem duas hipóteses
alternativas:
1.
h∈H
Aprendizagem de Máquina
Teorema de Bayes: Exemplo
“
hML ≡ arg max P ( D | h )
Mestrado em Informática Aplicada
⊕: positivo
\: negativo
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
16
Teorema de Bayes: Exemplo
“
Temos o conhecimento prévio que na população
inteira somente 0.008 tem esta doença.
“
O teste retorna um resultado positivo correto
somente em 98% dos casos nos quais a doença está
atualmente presente.
“
O teste retorna um resultado negativo correto
somente em 97% dos casos nos quais a doença não
esteja presente.
“
Nos outros casos, o teste retorna o resultado oposto.
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
17
Teorema de Bayes: Exemplo
P(câncer) =
P(¬câncer) =
P(⊕|câncer) =
P(\|câncer) =
P(⊕|¬câncer) =
P(\| ¬ câncer) =
Alessandro L. Koerich ([email protected])
Teorema de Bayes: Exemplo
“
Supondo que um paciente fez um teste de
laboratório e o resultado deu positivo.
“
O paciente tem câncer ou não ?
“
Aprendizagem de Máquina
19
18
Calculando a hipótese com maior
probabilidade a posteriori:
“
“
Mestrado em Informática Aplicada
Aprendizagem de Máquina
Aplicando o Teorema de Bayes
“
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
P(⊕|câncer) P(câncer) = 0.98 . 0.008 = 0.0078
P(⊕|¬câncer) P(¬câncer) = 0.03 . 0.992 = 0.0298
Assim, hMAP = ¬câncer
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
20
Formulação Básica de Probabilidades
Aprendizagem Conceitual Força–Bruta
“
Qual a relação entre o teorema de Bayes e a
aprendizagem de conceito?
“
Considere:
“
“
“
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
21
Alessandro L. Koerich ([email protected])
Aprendizagem Conceitual Força–Bruta
“
Podemos projetar um algoritmo de
aprendizagem de conceito que fornece na
saída a hipótese de máxima probabilidade a
posteriori:
1.
2.
Mestrado em Informática Aplicada
Aprendizagem de Máquina
22
Aprendizagem Conceitual Força–Bruta
“
Escolher P(h) como sendo uma distribuição uniforme
P (h) =
Para cada hipótese h em H calcular a probabilidade
a posteriori:
P (h | D ) =
um espaço finito de hipóteses H definido sobre um
espaço de instâncias X
a tarefa é aprender algum conceito alvo c: X → {0,1)
Assumindo que é fornecida uma seqüência de
exemplos de treinamento <x1...xm> e valores alvos
correspondentes <d1...dm>
“
1
H
∀ h∈ H
Escolher P(D|h)
⎧1 se h for consistent e com D
P ( D | h) = ⎨
⎩0 caso contrário
P ( D | h) P (h)
P( D)
Escolher a hipótese hMAP com probabilidade a
posteriori mais alta:
“
hMAP = arg max P ( h | D )
Agora podemos usar o teorema de Bayes para estimar
P(h|D) para cada hipótese h dado os dados de
treinamento D.
h∈H
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
23
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
24
Aprendizagem Conceitual Força–Bruta
“
Se h for inconsistente com os dados de
treinamento D, temos:
P (h | D ) =
“
“
0 .P ( h )
=0
P( D)
P (h | D ) =
P(D)
=
1
1.
H
VS H , D
=
Em resumo, o teorema Bayes implica que a
probabilidade a posteriori P(h|D) para P(h) e
P(D|h) assumidos seja:
⎧ 1
⎪
P ( h | D ) = ⎨ VS H , D
⎪ 0
⎩
Se h for consistente com D:
1
1.
H
Aprendizagem Conceitual Força–Bruta
1
VS H , D
se h for consistent e com D
caso contrário
H
onde VSH,D é o subconjunto de hipóteses de H
que são consistentes com D (i.e Espaço Versão).
.
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
25
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
26
Aprendizagem Conceitual
Aprendizagem Conceitual Força–Bruta
Evolução das probabilidades a posteriori com o
aumento dos dados de treinamento.
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
27
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
28
Classificador Ótimo de Bayes
“
Até agora consideramos a questão “Qual a
hipótese mais provável (i.e. hMAP) dado os
exemplos de treinamento (D)?”
“
De fato, a questão mais significativa é na
verdade “Qual é a classificação mais provável
de uma nova instância dado os dados de
treinamento?”
Classificador Ótimo de Bayes
“
P(h1|D) = 0.4 P(h2|D) = 0.3 P(h3|D) = 0.3
“
A hipótese MAP (hMAP ) é ou não
a classificação mais provável?
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
29
Exemplo: Dada uma nova instâncias x que é
classificada da seguinte forma:
h1(x) = + h2(x) = – h3(x) = –
“
Qual será a classificação mais provável de x?
Qual é a hipótese MAP?
h1
Alessandro L. Koerich ([email protected])
Classificador Ótimo de Bayes
“
Considere três hipóteses possíveis h1, h2 e h3 e
suponha as seguintes probabilidades a
posteriori destas hipóteses dado o conjunto de
treinamento D:
Mestrado em Informática Aplicada
“
A classificação mais provável da nova instância
x é obtida através da combinação das predições
de todas as hipóteses ponderadas pelas suas
probabilidades a posteriori.
“
Assim, a P(vj|D) que a correta classificação para
a instancia seja vj é:
∑ P (v
hi ∈ H
P ( v j | D ) = arg max
v j ∈V
Mestrado em Informática Aplicada
Aprendizagem de Máquina
31
30
Classificador Ótimo de Bayes
P (v j | D ) =
Alessandro L. Koerich ([email protected])
Aprendizagem de Máquina
Alessandro L. Koerich ([email protected])
j
| hi ) P ( hi | D )
∑ P (v
hi ∈ H
Mestrado em Informática Aplicada
j
| hi ) P ( hi | D )
Aprendizagem de Máquina
32
Classificador Ótimo de Bayes
“
A classificação ótima para a nova instância é o valor vj
para o qual P(vj|D) é máxima, i.e.:
arg max
v j ∈V
“
“
∑ P (v
hi ∈ H
j
Classificador Ótimo de Bayes
“
P(h1|D) = 0.4, P(–|h1) = 0, P(+|h1) = 1
P(h2|D) = 0.3, P(–|h2) = 1, P(+|h2) = 0
P(h3|D) = 0.3, P(–|h3) = 1, P(+|h3) = 0
| hi ) P ( hi | D )
Qualquer sistema que classifique novas instâncias de
acordo com a equação acima é chamada de um
classificador ótimo de Bayes.
portanto
Mestrado em Informática Aplicada
Aprendizagem de Máquina
“
33
Alessandro L. Koerich ([email protected])
| D ) = 0 .6
i
∑ P (v
hi ∈ H
j
| hi ) P ( hi | D ) = −
Mestrado em Informática Aplicada
Aprendizagem de Máquina
34
Algoritmo de Gibbs
E[erroGibbs] ≤ 2E[erroBayesÓtimo]
“
Fato surpreendente: Assumindo que os conceitos alvo
são tirados aleatoriamente de H segundo “a priori” em
H, então:
E[erroGibbs] ≤ 2E[erroBayesÓtimo]
Aprendizagem de Máquina
i
v j ∈{ + , − }
Algoritmo de Gibbs:
Mestrado em Informática Aplicada
∑ P (− | h )P (h
arg max
O classificador ótimo de Bayes fornece melhores
resultados mas pode ser “dispendioso” se existirem
muitas hipóteses.
Alessandro L. Koerich ([email protected])
| D ) = 0 .4
e
1. Escolha uma hipótese aleatoriamente de acordo com P(h|D)
2. Use–a para classificar uma nova instância
“
i
i
hi ∈H
Algoritmo de Gibbs
“
∑ P (+ | h )P (h
hi ∈H
Importante: Nenhum outro classificador que utilize o
mesmo espaço de hipóteses H e mesmo conhecimento a
priori pode superar este método
Alessandro L. Koerich ([email protected])
Exemplo:
35
Supondo que temos uma distribuição uniforme
de probabilidades a priori sobre H, então:
“
Pegue qualquer hipótese de VS, com probabilidade
uniforme.
“
Seu erro esperado não será pior do que o dobro do
erro de uma classificador Bayes ótimo.
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
36
Classificador Naïve Bayes
“
Junto com árvores de decisão, redes neurais e k–NN,
Naïve Bayes é um dos métodos de aprendizagem mais
práticos.
“
Quando usar ?
“
“
“
houver disponibilidade de um conjunto de treinamento grande
ou moderado.
os atributos que descrevem as instâncias forem
condicionalmente independentes dada a classificação.
Classificador Naïve Bayes
“
Se aplica a tarefas de aprendizagem onde cada
instância x é descrita por um conjunção de
valores de atributos e onde a função alvo, f(x)
pode assumir qualquer valor de um conjunto V.
“
Um conjunto de exemplos de treinamento da
função alvo é fornecido a uma nova instância é
apresentada, descrita pela tupla de valores de
atributos <a1, a2, ..., an>.
“
A tarefa é predizer o valor alvo (ou
classificação) para esta nova instância.
Aplicações bem sucedidas:
“
“
Diagnósticos
Classificação de documentos de textuais
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
37
Alessandro L. Koerich ([email protected])
Classificador Naïve Bayes
“
A solução Bayesiana para classificar a nova
instância consiste em atribuir o valor alvo mais
provável (vMAP) dados os valores dos atributos
<a1, a2, ..., an> que descrevem a instância.
v j ∈V
v MAP = arg max
v j ∈V
P ( a1 , a 2 ,..., a n )
v j ∈V
Mas podemos usar o teorema de Bayes para
reescrever a expressão . . .
Aprendizagem de Máquina
P ( a1 , a 2 ,..., a n | v j ) P ( v j )
= arg max P ( a1 , a 2 ,..., a n | v j ) P ( v j )
“
Mestrado em Informática Aplicada
38
v MAP = arg max P ( v j | a1 , a 2 ,..., a n )
v j ∈V
Alessandro L. Koerich ([email protected])
Aprendizagem de Máquina
Classificador Naïve Bayes
v MAP = arg max P ( v j | a1 , a 2 ,..., a n )
“
Mestrado em Informática Aplicada
Devemos agora estimar os dois termos da
equação acima baseando-se nos dados de
treinamento.
“
“
39
P(vj) é fácil de estimar . . .
Porém, P(a1,a2,...,an| vj) . . .
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
40
Classificador Naïve Bayes
“
“
O classificador Naïve Bayes é baseado na
suposição simplificadora de que os valores dos
atributos são condicionalmente independentes
dado o valor alvo.
Classificador Naïve Bayes
“
Temos assim o classificador Naïve Bayes:
v NB = arg max P ( v j ) ∏ P ( a i | v j )
v j ∈V
i
onde vNB indica o valor alvo fornecido pelo
Naïve Bayes.
Ou seja, a probabilidade de observar a
conjunção a1, a2,..., an é somente o produto das
probabilidades para os atributos individuais:
P ( a1 , a 2 ,..., a n | v j ) = ∏ P ( a i | v j )
i
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
41
Alessandro L. Koerich ([email protected])
Classificador Naïve Bayes
“
Em resumo, o algoritmo Naïve Bayes envolve
“
“
As hipóteses são então utilizadas para classificar
cada nova instância aplicando a equação vista
anteriormente (vNB)
Mestrado em Informática Aplicada
Aprendizagem de Máquina
42
Classificador Naïve Bayes
Naïve_Bayes_Learn (examplos)
Para cada valor alvo vj
P’ (vj) ³ estimar P (vj)
Para cada valor de atributo ai de cada atributo a
P’ (ai|vj) ³ estimar P (ai| vj)
Classify_New_Instances (x)
O conjunto destas estimativas corresponde as hipóteses
aprendidas
Alessandro L. Koerich ([email protected])
Aprendizagem de Máquina
Algoritmo Naïve Bayes
Aprendizagem no qual os termos P(vj) e P(ai|vj) são
estimados baseado nas suas freqüências no conjunto
de treinamento.
“
Mestrado em Informática Aplicada
v NB = arg max P ' ( v j )∏ P ' ( a i | v j )
v j ∈V
43
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
ai ∈ x
Aprendizagem de Máquina
44
Classificador Naïve Bayes
“
Exemplo: Considere os 14 exemplos de
treinamento de PlayTennis e uma nova
instância que o Naïve Bayes deve classificar:
Classificador Naïve Bayes
“
Atributo alvo: PlayTennis (yes, no)
<Outlook=sunny, Temperature=cool, Humidity=high, Wind=strong>
“
Nossa tarefa é predizer o valor alvo (yes ou no)
do conceito PlayTennis para esta nova
instância.
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
45
Alessandro L. Koerich ([email protected])
Classificador Naïve Bayes
“
O valor alvo VNB será dado por:
Aprendizagem de Máquina
46
Classificador Naïve Bayes
“
Probabilidades a priori:
P(PlayTennis = yes) = 9/14 = 0.64
P(PlayTennis = no) = 5/14 = 0.36
v NB = arg max P ( v j ) ∏ P ( a i | v j )
v j ∈{ yes , no }
Mestrado em Informática Aplicada
i
= arg max P ( v j ) P (Outlook = sunny | v j ) P (Temperatur e = cool | v j )
v j ∈{ yes , no }
P ( Humidity = high | v j ) P (Wind = strong | v j )
“
Note que ai foi instanciado utilizando os valores
particulares de atributo da nova instância.
“
Para calcular VNB são necessárias 1o probabilidades que
podem ser estimadas a partir dos exemplos de
treinamento.
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
“
Probabilidades condicionais:
P(Wind=strong | PlayTennis = yes) = 3/9 = 0.33
P(Wind=strong | PlayTennis = no) = 3/5 = 0.60
...
47
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
48
Classificador Naïve Bayes
“
Classificador Naïve Bayes
Usando estas estimativas de probabilidade e
estimativas similares para os valores restantes
dos atributos, calculamos vNB de acordo com a
equação anterior (omitindo nome dos
atributos) :
Sutilezas:
1. Suposição de independência condicional é muitas vezes
violada
P(yes) P(sunny| yes) P(cool| yes) P(high| yes)
P(strong| yes) = 0.0053
P(no) P(sunny| no) P(cool| no) P(high| no) P(strong|
no) = 0.026
. . . mas, de qualquer maneira, ele funciona bem. Note que
não é necessário estimar probabilidades a posteriori
P’(vj|x) para ser correta. Necessita somente que
P ( a1 , a 2 ,..., v j ) = ∏ P ( a i | v j )
i
arg max P ' ( v j )∏ P ' ( a i | v j ) = arg max P ( v j ) P ( a1 ,..., a n | v j )
v j ∈V
“
Então o classificador atribui o valor alvo
PlayTennis = no para esta nova instância.
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
“
49
Alessandro L. Koerich ([email protected])
i
A solução típica é uma estimativa Bayesiana para P’(ai|vj)
.
Alessandro L. Koerich ([email protected])
n c + mp
n+m
Mestrado em Informática Aplicada
Aprendizagem de Máquina
Aprendizagem de Máquina
50
Classificador Naïve Bayes
n c + mp
n+m
onde:
“ n é o número de exemplos de treinamento para
os quais v = vj,
“ nc é o número de exemplos para os quais v = vj
e a = ai
“ p é a estimativa a priori para P’(ai|vj)
“ m é o peso dado as priori (i.e. número de
exemplos “virtuais”).
P ' ( v j )∏ P ' ( a i | v j ) = 0
P ' ( a i | vi ) ←
Mestrado em Informática Aplicada
P ' ( a i | vi ) ←
P ' ( ai | v j ) = 0
e ...
v j ∈V
Probabilidades Naïve Bayes a posteriori próximas de 0
e 1 são geralmente não realísticas
Classificador Naïve Bayes
Sutilezas:
2. E se nenhuma das instâncias de treinamento com valor
alvo vj tiver uma atributo de valor ai? Então,
i
51
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
52
Exemplo: Classificando Texto
Por que ?
“ Aprender quais notícias são interessantes
“
“
Aprender a classificar páginas WEB por assunto
“
Naïve Bayes é um dos algoritmos mais
eficientes
“
Quais atributos devemos usar para representar
documentos de texto?
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
Exemplo: Classificando Texto
53
Contexto
“
Considere um espaço de instâncias X consistindo de
todos os documentos de texto possíveis.
“
Dados exemplos de treinamento, de alguma função
alvo f(x) que pode assumir valores de um conjunto
finito V.
Alessandro L. Koerich ([email protected])
Exemplo: Classificando Texto
“
“
A tarefa de aprendizagem é aprender, a partir dos
exemplos de treinamento, a predizer o valor alvo
para os documento de texto subseqüentes.
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
55
Aprendizagem de Máquina
54
Exemplo: Classificando Texto
“
Considere a função alvo como sendo documentos
interessantes e não interessantes.
Mestrado em Informática Aplicada
Projeto do Naïve Bayes:
“
Como representar um documento de texto arbitrário
em termos de valores de atributos
“
Decidir como estimar as probabilidades necessárias
para o Naïve Bayes.
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
56
Exemplo: Classificando Texto
“
Representação de texto arbitrário
“
Dado um documento de texto, este parágrafo, por
exemplo, definimos um atributo para cada posição
de palavra no documento e definimos o valor do
atributo como sendo a palavra em português
encontrada nesta posição.
“
O parágrafo anterior pode ser descrito por 34 valores
de atributos correspondendo as 34 posições de
palavras.
“
O valor do primeiro atributo é a palavra “Dado” e do
segundo é a palavra “um” e assim por diante.
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
Exemplo: Classificando Texto
“
Dada a representação de documento de texto,
podemos aplicar o Naïve Bayes.
“
Assumimos
“
“
57
Alessandro L. Koerich ([email protected])
Exemplo: Classificando Texto
“
Conceito alvo interessante: documento → {+, –
}
“
“
“
“
length ( doc )
∏ P (a
i
= wk | v j )
onde P(ai = wk|vj) é a probabilidade que a
palavra na posição i é wk, dado vj.
P (+)
P (–)
P (doc|+)
P (doc|–)
“
Mais uma suposição
P (ai = w k | v j ) = P (am = w k | v j )
Mestrado em Informática Aplicada
Aprendizagem de Máquina
58
i =1
Um atributo por posição da palavra no documento
Alessandro L. Koerich ([email protected])
Aprendizagem de Máquina
Suposição da independência condicional Naïve
Bayes
P ( doc | v j ) =
2. Aprendendo usar exemplos de treinamento
para estimar
“
Mestrado em Informática Aplicada
Exemplo: Classificando Texto
1. Representar cada documento por um vetor de
palavras
“
um conjunto de 700 documentos classificados por
uma pessoa como não interessantes
outros 300 classificados como interessantes
59
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
∀i, m
Aprendizagem de Máquina
60
Exemplo: Classificando Texto
Learn_Naïve_Bayes_Text (Examples, V)
Exemplo: Classificando Texto
“
Para cada valor alvo vj em V faça
“
1. Colecionar todas palavras, pontuação e outros
tokens que ocorrem em Examples
“
“
Vocabulary ← todas as palavras distintas e outros
tokens que ocorrem em Examples
“
“
“
2. Calcular as probabilidade necessárias P (vj) e P
(wk|vj) ...
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
docsj ← subconjunto de documento de Examples para o
qual o valor alvo é vj
P (v j ) =
z
Exemplo: Classificando Texto
j
Textj ← um documento único criado pela concatenação de
todos os membros de docsj
n ← número total de posições distintas de palavras em Textj
Para cada palavra wk em Vocabulary
z
61
docs
Examples
nk ← número de vezes que a palavra wk ocorre em Textj
P (wk | v j ) ←
Alessandro L. Koerich ([email protected])
nk + 1
n + Vocabulary
Mestrado em Informática Aplicada
Aprendizagem de Máquina
62
Exemplo: Classificando Texto
Classify_Naïve_Bayes_Text (Doc)
“
“
positions ← todas as posições das palavras em Doc
que contém tokens encontrados em Vocabulary
retornar vNB onde
v NB = arg max P ( v j )
v j ∈V
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
∏ P (a
i
|vj)
i∈ positions
Aprendizagem de Máquina
63
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
64
Exemplo: Classificando Texto
“
Dados 1000 documentos de treinamento de cada grupo,
aprenda a classificar novos documentos de acordo com
o newsgroup de origem.
“
Naïve Bayes: precisão de classificação: 89%
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
Exemplo: Classificando Texto
“
65
Artigo de rec.sport.hockey
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Curva de Aprendizagem
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
67
Aprendizagem de Máquina
66
Resumo
“
Métodos Bayesianos: acomodam conhecimento
prévio e e dados observáveis; atribuem probabilidade
a posteriori para cada hipótese candidata, baseando–
se na priori e dados.
“
Métodos Bayesianos: podem determinar a hipótese
mais provável (MAP), tendo os dados.
“
Bayes Ótimo: combina predições de todas hipóteses
alternativas, ponderadas pela probabilidade a
posteriori, para calcular a classificação mais provável
de cada nova instância.
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
68
Resumo
“ Naïve
Bayes: é chamado de naïve (simples,
não sofisticado), porque assume que os
valores dos atributos são condicionalmente
independentes.
“ Naïve
Bayes: se a condição é encontrada, ele
fornece a classificação MAP, caso contrário,
pode fornecer também bons resultados.
Alessandro L. Koerich ([email protected])
Mestrado em Informática Aplicada
Aprendizagem de Máquina
69