Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
Aprendizagem de Máquina
Aprendizagem Bayesiana
Alessandro L. Koerich
Mestrado/Doutorado em Informática (PPGIa)Pontifícia Universidade Católica do Paraná (PUCPR)
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 2Alessandro L. Koerich ([email protected])
Plano de Aula
IntroduçãoTeorema de Bayes e Aprendizagem ConceitualClassificador Ótimo de BayesAlgoritmo de GibbsClassificador Naïve BayesExemplosResumo
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 3Alessandro L. Koerich ([email protected])
Referências
Duda R., Hart P., Stork D. PatternClassification 2ed. Willey Interscience, 2002. Capítulos 2 & 3
Mitchell T. Machine Learning. WCB McGraw–Hill, 1997. Capítulo 6.
Theodoridis S., Koutroumbas K. PatternRecognition. Academic Press, 1999. Capítulo 2
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 4Alessandro L. Koerich ([email protected])
Introdução
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.
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 5Alessandro L. Koerich ([email protected])
Introdução
Decisões ótimas podem ser tomadas com base nestas probabilidades conjuntamente com os dados observados.
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.
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 6Alessandro L. Koerich ([email protected])
Introdução
Os métodos Bayesianos são relevantes por dois motivos:
1. Fornecem algoritmos de aprendizagem práticos:
Aprendizagem Naïve BayesAprendizagem de Redes BayesianasCombinam conhecimento a priori com os dados observadosRequerem probabilidades a priori
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 7Alessandro L. Koerich ([email protected])
Introdução
2. Fornecem uma estrutura conceitual útil:
Fornece “norma de ouro” para avaliar outros algoritmos de aprendizagem
Percepção adicional dentro do Occam’s razor
Norma de Ouro: menor erro possível
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 8Alessandro L. Koerich ([email protected])
Características da Aprendizagem Bayesiana
1.
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)
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 9Alessandro L. Koerich ([email protected])
Características da Aprendizagem Bayesiana
4.
Novas instâncias podem ser classificadas combinando a probabilidade de múltiplas hipóteses ponderadas pelas suas probabilidades.
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 10Alessandro L. Koerich ([email protected])
Dificuldades Práticas
Métodos Bayesianos requerem o conhecimento inicial de várias probabilidades.
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.
Custo computacional significativo para determinar a hipótese ótima de Bayes
É geralmente linear com o número de hipóteses
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 11Alessandro L. Koerich ([email protected])
Teorema de Bayes
)()()|(
)|(DP
hPhDPDhP =
P(h): probabilidade a priori da hipótese h
P(D|h): probabilidade de D dado h.
P(h|D): probabilidade de h dado D
P(D): probabilidade a priori dos dados de treinamento D
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 12Alessandro L. Koerich ([email protected])
Teorema de Bayes
P(h|D) é chamada de probabilidade a posterioride 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.
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 13Alessandro L. Koerich ([email protected])
Teorema de Bayes
Geralmente queremos encontrar a hipótese mais provável h ∈ H, sendo fornecidos os dados de treinamento D.
Ou seja, a hipótese com o máximo a posteriori (MAP)
)()|(maxarg )(
)()|(maxarg
)|(maxarg
hPhDPDP
hPhDP
DhPh
Hh
Hh
HhMAP
∈
∈
∈
=
=
≡
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 14Alessandro L. Koerich ([email protected])
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.
P(hi ) = P(hj ) ∀
hi e hj em H
Então, podemos simplificar mais e escolher a hipótese de máxima probabilidade condicional (maximum likelihood = ML).
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 15Alessandro 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.
)|(maxarg hDPhHh
ML∈
≡
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 16Alessandro L. Koerich ([email protected])
Teorema de Bayes: Exemplo
Considere um problema de diagnóstico médico onde existem duas hipóteses alternativas:
1.
O paciente tem câncer
2.
O paciente não tem câncer
Os dados disponíveis são de um exame de laboratório com dois resultados possíveis:
⊕: positivo: negativo
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 17Alessandro L. Koerich ([email protected])
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.
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 18Alessandro L. Koerich ([email protected])
Teorema de Bayes: Exemplo
P(câncer) =
P(¬câncer) =
P(⊕|câncer) =
P( |câncer) =
P(⊕|¬câncer) =
P( | ¬ câncer) =
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 19Alessandro 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 ?
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 20Alessandro L. Koerich ([email protected])
Aplicando o Teorema de Bayes
Calculando a hipótese com maior probabilidade a posteriori:
P(⊕|câncer) P(câncer) = 0.98 . 0.008 = 0.0078P(⊕|¬câncer) P(¬câncer) = 0.03 . 0.992 = 0.0298
Assim, hMAP = ¬câncer
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 21Alessandro L. Koerich ([email protected])
Formulação Básica de Probabilidades
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 22Alessandro L. Koerich ([email protected])
Aprendizagem Conceitual Força–Bruta
Qual a relação entre o teorema de Bayes e a aprendizagem de conceito?
Considere:um espaço finito de hipóteses H definido sobre um espaço de instâncias Xa 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>
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 23Alessandro 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.
Para cada hipótese h em H calcular a probabilidade a posteriori:
2.
Escolher a hipótese hMAP com probabilidade a posteriori mais alta:
)()()|()|(
DPhPhDPDhP =
)|(maxarg DhPhHh
MAP∈
=
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 24Alessandro L. Koerich ([email protected])
Aprendizagem Conceitual Força–Bruta
Escolher P(h) como sendo uma distribuição uniforme
Escolher P(D|h)
Agora podemos usar o teorema de Bayes para estimar P(h|D) para cada hipótese h dado os dados de treinamento D.
⎩⎨⎧
=contráriocaso
DcomeconsistentforhsehDP
0 1
)|(
HhH
hP ∈∀= 1)(
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 25Alessandro L. Koerich ([email protected])
Aprendizagem Conceitual Força–Bruta
Se h for inconsistente com os dados de treinamento D, temos:
Se h for consistente com D:
onde VSH,D é
o subconjunto de hipóteses de H que são consistentes com D (i.e Espaço Versão).
.
0)()(.0)|( ==
DPhPDhP
DHDH VSH
VSH
DPH
DhP,,
11.1
)(
1.1)|( ===
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 26Alessandro L. Koerich ([email protected])
Aprendizagem Conceitual Força–Bruta
Em resumo, o teorema Bayes implica que a probabilidade a posteriori P(h|D) para P(h) e P(D|h) assumidos seja:
⎪⎩
⎪⎨
⎧=
contráriocaso
DcomeconsistentforhseVSDhP DH
0
1
)|( ,
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 27Alessandro L. Koerich ([email protected])
Aprendizagem Conceitual Força–Bruta
Evolução das probabilidades a posteriori com o aumento dos dados de treinamento.
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 28Alessandro L. Koerich ([email protected])
Aprendizagem Conceitual
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 29Alessandro L. Koerich ([email protected])
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?”
A hipótese MAP (hMAP ) é
ou nãoa classificação mais provável?
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 30Alessandro 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:
P(h1 |D) = 0.4 P(h2 |D) = 0.3 P(h3 |D) = 0.3
Qual é a hipótese MAP?h1
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 31Alessandro L. Koerich ([email protected])
Classificador Ótimo de Bayes
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?
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 32Alessandro L. Koerich ([email protected])
Classificador Ótimo de Bayes
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 é:
∑∈
=Hh
iijji
DhPhvPDvP )|()|()|(
∑∈∈
=Hh
iijVv
jij
DhPhvPDvP )|()|(maxarg)|(
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 33Alessandro L. Koerich ([email protected])
Classificador Ótimo de Bayes
A classificação ótima para a nova instância é o valor vjpara o qual P(vj|D) é máxima, i.e.:
Qualquer sistema que classifique novas instâncias de acordo com a equação acima é chamada de um classificador ótimo de Bayes.
Importante: Nenhum outro classificador que utilize o mesmo espaço de hipóteses H e mesmo conhecimento a priori pode superar este método
∑∈∈ Hh
iijVv
ij
DhPhvP )|()|(maxarg
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 34Alessandro L. Koerich ([email protected])
Classificador Ótimo de Bayes
Exemplo:P(h1 |D) = 0.4, P(–|h1 ) = 0, P(+|h1 ) = 1P(h2 |D) = 0.3, P(–|h2 ) = 1, P(+|h2 ) = 0P(h3 |D) = 0.3, P(–|h3 ) = 1, P(+|h3 ) = 0
portanto
e
6.0)|()|(
4.0)|()|(
=−
=+
∑
∑
∈
∈
Hhii
Hhii
i
i
DhPhP
DhPhP
−=∑∈−+∈ Hh
iijv
ij
DhPhvP )|()|(maxarg},{
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 35Alessandro L. Koerich ([email protected])
Algoritmo de Gibbs
O classificador ótimo de Bayes fornece melhores resultados mas pode ser “dispendioso” se existirem muitas hipóteses.
Algoritmo de Gibbs:1. Escolha uma hipótese aleatoriamente de acordo com P(h|D)2. Use–a para classificar uma nova instância
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 ]
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 36Alessandro L. Koerich ([email protected])
Algoritmo de Gibbs
E[erroGibbs ] ≤
2E[erroBayesÓtimo ]
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.
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 37Alessandro L. Koerich ([email protected])
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.
Aplicações bem sucedidas:DiagnósticosClassificação de documentos de textuais
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 38Alessandro L. Koerich ([email protected])
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.
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 39Alessandro 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.
Mas podemos usar o teorema de Bayes para reescrever a expressão . . .
),...,,|(maxarg 21 njVv
MAP aaavPvj ∈
=
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 40Alessandro L. Koerich ([email protected])
Classificador Naïve Bayes
Devemos agora estimar os dois termos da equação acima baseando-se nos dados de treinamento.
P(vj) é fácil de estimar . . .Porém, P(a1,a2,...,an| vj) . . .
)()|,...,,(maxarg ),...,,(
)()|,...,,(maxarg
),...,,|(maxarg
21
21
21
21
jjnVv
n
jjn
VvMAP
njVv
MAP
vPvaaaPaaaP
vPvaaaPv
aaavPv
j
j
j
∈
∈
∈
=
=
=
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 41Alessandro L. Koerich ([email protected])
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.
Ou seja, a probabilidade de observar a conjunção a1, a2,..., an é somente o produto das probabilidades para os atributos individuais:
∏=i
jijn vaPvaaaP )|()|,...,,( 21
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 42Alessandro L. Koerich ([email protected])
Classificador Naïve Bayes
Temos assim o classificador Naïve Bayes:
onde vNB indica o valor alvo fornecido pelo Naïve Bayes.
∏∈
=i
jijVv
NB vaPvPvj
)|()(maxarg
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 43Alessandro L. Koerich ([email protected])
Classificador Naïve Bayes
Em resumo, o algoritmo Naïve Bayes envolve
Aprendizagem no qual os termos P(vj) e P(ai|vj) são estimados baseado nas suas freqüências no conjunto de treinamento.
O conjunto destas estimativas corresponde as hipóteses aprendidas
As hipóteses são então utilizadas para classificar cada nova instância aplicando a equação vista anteriormente (vNB)
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 44Alessandro L. Koerich ([email protected])
Classificador Naïve Bayes
Algoritmo 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)
∏∈∈
=xa
jijVv
NBij
vaPvPv )|(')('maxarg
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 45Alessandro L. Koerich ([email protected])
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:
<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.
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 46Alessandro L. Koerich ([email protected])
Classificador Naïve Bayes
Atributo alvo: PlayTennis (yes, no)
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 47Alessandro L. Koerich ([email protected])
Classificador Naïve Bayes
O valor alvo VNB será dado por:
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.
)|()|(
)|()|()(maxarg
)|()(maxarg
},{
},{
jj
jjjnoyesv
ijij
noyesvNB
vstrongWindPvhighHumidityP
vcooleTemperaturPvsunnyOutlookPvP
vaPvPv
j
j
==
===
=
∈
∈∏
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 48Alessandro L. Koerich ([email protected])
Classificador Naïve Bayes
Probabilidades a priori:P(PlayTennis = yes) = 9/14 = 0.64P(PlayTennis = no) = 5/14 = 0.36
Probabilidades condicionais:P(Wind=strong | PlayTennis = yes) = 3/9 = 0.33P(Wind=strong | PlayTennis = no) = 3/5 = 0.60. . .
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 49Alessandro L. Koerich ([email protected])
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) :P(yes)
P(sunny| yes) P(cool| yes) P(high| yes)
P(strong| yes) = 0.0053P(no)
P(sunny| no) P(cool| no) P(high| no) P(strong|
no) = 0.026
Então o classificador atribui o valor alvo PlayTennis = no para esta nova instância.
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 50Alessandro L. Koerich ([email protected])
Classificador Naïve Bayes
Sutilezas:1. Suposição de independência condicional é
muitas vezes
violada
. . . 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
Probabilidades Naïve Bayes a posteriori próximas de 0 e 1 são geralmente não realísticas
∏=i
jij vaPvaaP )|(),...,,( 21
)|,...,()(maxarg)|(')('maxarg 1 jnjVvi
jijVv
vaaPvPvaPvPjj ∈∈
=∏
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 51Alessandro L. Koerich ([email protected])
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,
e ...
A solução típica é
uma estimativa Bayesiana para P’(ai |vj )
.
0)|(' =ji vaP
mnmpnvaP c
ii ++
←)|('
0)|(')(' =∏i
jij vaPvP
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 52Alessandro L. Koerich ([email protected])
Classificador Naïve Bayes
onde:n é o número de exemplos de treinamento para os quais v = vj,nc é o número de exemplos para os quais v = vje a = ai
p é a estimativa a priori para P’(ai|vj)m é o peso dado as priori (i.e. número de exemplos “virtuais”).
mnmpnvaP c
ii ++
←)|('
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 53Alessandro L. Koerich ([email protected])
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?
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 54Alessandro L. Koerich ([email protected])
Exemplo: Classificando Texto
ContextoConsidere 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.
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 55Alessandro 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.
Considere a função alvo como sendo documentos interessantes e não interessantes.
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 56Alessandro L. Koerich ([email protected])
Exemplo: Classificando Texto
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.
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 57Alessandro L. Koerich ([email protected])
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.
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 58Alessandro L. Koerich ([email protected])
Exemplo: Classificando Texto
Dada a representação de documento de texto, podemos aplicar o Naïve Bayes.
Assumimosum conjunto de 700 documentos classificados por uma pessoa como não interessantesoutros 300 classificados como interessantes
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 59Alessandro L. Koerich ([email protected])
Exemplo: Classificando Texto
Conceito alvo interessante: documento → {+, –}
1. Representar cada documento por um vetor de palavras
Um atributo por posição da palavra no documento2. Aprendendo usar exemplos de treinamento
para estimar P (+)P (–)P (doc|+)P (doc|–)
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 60Alessandro L. Koerich ([email protected])
Exemplo: Classificando Texto
Suposição da independência condicional Naïve Bayes
onde P(ai = wk |vj ) é
a probabilidade que a palavra na posição i é
wk , dado vj .
Mais uma suposição
∏=
==)(
1
)|()|(doclength
ijkij vwaPvdocP
mivwaPvwaP jkmjki , )|()|( ∀===
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 61Alessandro L. Koerich ([email protected])
Exemplo: Classificando Texto
Learn_Naïve_Bayes_Text (Examples, V)
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 ) ...
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 62Alessandro L. Koerich ([email protected])
Exemplo: Classificando Texto
Para cada valor alvo vj em V façadocsj ← subconjunto de documento de Examples para o qual o valor alvo é vj
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 Vocabularynk ← número de vezes que a palavra wk ocorre em Textj
Examples
docsvP j
j =)(
VocabularynnvwP k
jk ++
←1
)|(
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 63Alessandro L. Koerich ([email protected])
Exemplo: Classificando Texto
Classify_Naïve_Bayes_Text (Doc)
positions ← todas as posições das palavras em Docque contém tokens encontrados em Vocabulary
retornar vNB onde
∏∈∈
=positionsi
jijVv
NB vaPvPvj
)|()(maxarg
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 64Alessandro L. Koerich ([email protected])
Exemplo: Classificando Texto
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 65Alessandro L. Koerich ([email protected])
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%
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 66Alessandro L. Koerich ([email protected])
Exemplo: Classificando Texto
Artigo de rec.sport.hockey
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 67Alessandro L. Koerich ([email protected])
Curva de Aprendizagem
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 68Alessandro L. Koerich ([email protected])
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.
Mestrado/Doutorado em Informática (PPGIa) Aprendizagem de Máquina 69Alessandro L. Koerich ([email protected])
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.