Aprendizado Bayesiano

Marcelo K. Albertini

3 de Julho de 2014

Conteudo

I Aprendizado Naive Bayes

I Exemplo: classificacao de texto

I Redes Bayesiana

I Algoritmo EM

I Regressao probabilıstica

2/1

Classificador Maximum a Posteriori

Assumir que funcao alvo f : X → C , onde cada instancia x edescrita por atributos 〈a1, a2 . . . an〉Classe mais provavel, ou seja cMAP = f (x), e:

cMAP = arg maxcj∈C

P(cj |a1, a2, . . . , an)

cMAP = arg maxcj∈C

P(a1, a2, . . . , an|cj)P(cj)

P(a1, a2, . . . , an)

= arg maxcj∈C

P(a1, a2, . . . , an|cj)P(cj)

3/1

Premissa de Naive Bayes

Premissa simplificadora: atributos sao independentes.

P(a1, a2, . . . an|cj) =∏i

P(ai |cj)

o que resulta no classificador Naive Bayes

cNB = arg maxcj∈C

P(cj)∏i

P(ai |cj)

4/1

Algoritmo Naive Bayes

NaiveBayes(exemplos)

Para cada valor-alvo cj

I P(cj)← estimativa de P(cj)

I Para cada valor de atributo ai de cada atributo a

P(ai |cj)← estimativa de P(ai |cj)

ClassificarNovaInstancia(x)

cNB = arg maxcj∈C

P(cj)∏ai∈x

P(ai |cj)

5/1

Naive Bayes: exemplo

Considere exemplo JogarTenis e uma nova instancia:

〈Aparencia=Ensolarado, Temp.=frio, Umidade=alta, Vento = forte〉

Queremos computar

cNB = arg maxcj∈C

P(cj)∏i

P(ai |cj)

P(sim)P(ensol.|sim)P(frio|sim)P(alta|sim)P(forte|sim) = 0.005

P(nao)P(ensol.|nao)P(frio|nao)P(alta|nao)P(forte|nao) = 0.021

→ cNB = n

6/1

Naive Bayes: detalhes

Premissa de independencia condicional e frequentemente violada

P(a1, a2, . . . , an|cj) =∏i

P(ai |cj)

porem funciona bem, mesmo com P(cj |x) incorretas; necessitasomente que

arg maxcj∈C

P(cj)∏i

P(ai |cj) = arg maxcj∈C

P(cj)P(a1, . . . an|cj)

7/1

Naive Bayes: detalhes

E se nenhuma das instancias de treino com valor-alvo ci tem valorde atributo ai? Entao

P(ai |cj) = 0, e ...

P(cj)∏i

P(ai |cj) = 0

8/1

Solucao tıpica

Usar estimativa m

P(ai |cj)←nc + mp

n + m

onde

I n e numero de exemplos de treino em que v = cjI nc e numero de exemplos em que v = cj e a = ai

I p e estimativa a priori para P(ai |cj)I m e peso dado para a priori (numero de exemplos

“fantasmas”)I se m = 0, temos formulacao originalI quanto maior m, maior e a confianca no conhecimento previo

9/1

Aprendizado de classificacao de textos

I Aprender quais artigos de jornal sao do interesse de umapessoa

I Aprender a classificar paginas de acordo com topicos

Naive bayes e um dos algoritmos mais usados.

Quais atributos devemos usar para representar documentos detexto?

10/1

Aprendizado de classificacao de textos

Conceito-alvo Interessante? : Documento → {+,−}I Representar cada documento por um vetor de palavras: um

atributo por palavra no documentoI Aprendizado: usar exemplos de treino para estimar

I P(+)I P(−)I P(doc|+)I P(doc|−)

11/1

Classificador Naive Bayes em textos

Premissa de independencia condicional de Naive Bayes

P(doc|cj) =

tam(doc)∏i=1

P(ai = wk |cj)

onde P(ai = wk |cj) e a probabilidade que a palavra na posicao i ewk , assumindo que a classe e cj

Premissa adicionalA posicao da palavra nao muda a probabilidade:

P(ai = wk |cj) = P(am = wk |cj),∀i ,m

12/1

1 Tre inoNa iveBayes (Doc [ ] exemplos , C l a s s e s C) {2 // P : p r o b a b i l i d a d e s de cada c l a s s e3 doub l e [ ] P = new doub l e [C . s i z e ( ) ] ;4 // Pw: p r o b a b i l i d a d e s de cada p a l a v r a em cada c l a s s e5 Map<St r i ng , doub l e []> Pw = new HashMap ( ) ;67 S t r i n g vocab [ ] = exemplos . o b t e r P a l a v r a sD i s t i n t a s ( ) ;89 f o r ( C l a s s e c j : C) {

10 Doc [ ] d o c s c j = exemplos . comClasse ( c j )11 P [ c j ] = d o c s c j . s i z e ( ) / exemplos . s i z e ( ) ;12 i n t n = d o c s c j . numeroDePalavras ( ) ;1314 f o r ( S t r i n g a i : vocab ) {15 i n t n c = d o c s c j . numeroOcorrenc iasDe ( a i ) ;16 Pw. ge t ( a i ) [ c j ] = ( n c + 1) /( n + vocab . l e n g t h ) ;17 }18 }19 r e t u r n P , Pw;20 }

13/1

1 C l a s s e C l a s s i f i c a rNB (Doc d , C l a s s e s C ,2 doub l e [ ] P ,3 Map<St r i ng , doub l e []> Pw) {45 S t r i n g [ ] p a l a v r a s = d . o b t e rP a l a v r a s ( ) ;6 C l a s s e c NB = argmax (C , P , Pw, p a l a v r a s ) ;7 r e t u r n c NB ;8 }

Funcao: argmax(C, P, Pw, palavras)

cNB = arg maxcj∈C

logP(cj) +∑

ai∈palavraslogP(ai |cj)

14/1

Exemplo: 20 newsgroups

Dados 1000 documentos de treino de cada classe (1 lista = 1classe).Aprender a classificar novos documentos entre as listas:

I comp.graphicsI comp.os.ms-windows.miscI comp.sys.ibm.pc.hardwareI alt.atheismI talk.religion.miscI talk.politics.miscI sci.spaceI sci.cryptI sci.medI rec.autosI misc.forsaleI ...

http://qwone.com/~jason/20Newsgroups/15/1

Redes Bayesianas

Interessante porque:

I Premissa de Naive Bayes de independencia condicional emuito restritiva

I Redes Bayesiana permite melhorar premissa, mantendo atratabilidade

I Combina conhecimento previo de (in)dependencias entrevariaveis com dados observados

16/1

Independencia condicional

Definicao

X e condicionalmente independente de Y , considerando Z se

(∀xi , yj , zk)P(X = xi |Y = yj ,Z = zk) = P(X = xi |Z = zk)

De maneira mais compacta

P(X |Y ,Z ) = P(X |Z )

17/1

Exemplo

Trov~ao e condicionalmente independente de chuva, considerandoraio.

P(trovao|chuva, raio) = P(trovao|raio)

Naive Bayes usa independencia condicional para justificar suapremissa:

P(X ,Y |Z ) = P(X |Y ,Z )P(Y |Z )

= P(X |Z )P(Y |Z )

18/1

Rede Bayesiana

Tempestade Turistas

Raio

Trovao

Fogueira

Incendio

A =Tempestade, B =Turistas,C =Fogueira

A,B A,¬B ¬A,B ¬A,¬BC 0.4 0.1 0.8 0.2¬C 0.6 0.9 0.2 0.8

Rede representa um conjunto de afirmacoes sobre independenciacondicional.Cada vertice e condicionalmente independente de seusnao-descendentes, considerando seus pais.

19/1

Rede Bayesiana

Rederepresenta distribuicao de probabilidade conjunta sobre todas asvariaveis

I Exemplo P(tempestade, turistas . . . incendio)

I Em geral

P(y1, . . . , yn) =n∏

i=1

P(yi |Pais(Yi ))

onde Pais(Yi ) denota predecessores imediatos de Yi no grafo

I Entao distribuicao conjunta e completamente definida pelografo, mais P(yi |Pais(Yi ))

20/1

Inferencia em Redes Bayesianas

Como inferir as probabilidades de variaveis da rede,considerando os valores de outras?

I Rede Bayesiana contem toda a informacao necessaria para ainferencia

I No caso geral, problema e NP-hard

Na pratica, pode ser bem sucedido

I Metodos de inferencia exatos funcionam para algumasestruturas simplificadas

I Metodos de Monte Carlo “simulam” a rede aleatoriamentepara calcular solucoes aproximadas

21/1

Aprendizado de Redes Bayesianas

Muitas variantes para esta tarefa de aprendizado

I Estrutura da rede pode ser conhecida ou nao

I Exemplos de treino podem prover valores para todas asvariaveis da rede, ou apenas algumas

Estrutura conhecida e sem valores faltandotreino similar ao classificador de Naive Bayes.

22/1

Algoritmo EM

EM : Expectativa/Esperanca e Maximizacao

Supor estrutura conhecida, variaveis parcialmente observaveis.

Exemplo

Possıvel saber Incendio, Tempestade, Turistas, Trov~ao, masnao Raio, Fogueira ...

Inicializar parametros ignorando informacao faltante.

Repetir ate convergencia:

I Passo E: computar valores esperados de variaveis naoobservadas assumindo valores de parametros atuais

I Passo M: computar novos valores de parametros paramaximizar probabilidade dos dados (observados & estimados)

23/1

Exemplo EM

A B C

Exemplos

A B C0 1 11 0 01 1 11 ? 0

Inicializacao

P(B|A) = P(C |B) =P(A) = P(B|¬A) = P(C |¬B) =

Passo EP(? = 1) = P(B|A,¬C ) = P(A,B,¬C)

P(A,¬C) = . . . =

Passo MP(B|A) = P(C |B) =P(A) = P(B|¬A) = P(C |¬B) =

Passo EP(? = 1) =

24/1

Estrutura desconhecida

Busca

I Estado inicial: rede vazia ou rede de conhecimento previo

I Operadores: adicionar aresta, remover aresta, inverter aresta

I Avaliacao: probabilidade a posteriori

25/1