I Classi cador otimo: necess ario conhecer de antem~aofatc/AM/Estimacao-Parametros.pdf · Estima˘c~ao de Par^ametros1 I Classi cador otimo: necess ario conhecer de antem~ao I as

Estimação de Parâmetros1

I Classificador ótimo: necessário conhecerde antemão

I as probabilidades a prioriI as densidades condicionais das classes

I Caso real t́ıpico:I conhecimento muito geral da situaçãoI amostra dos exemplos a serem classificados

I Como usar de alguma maneira essa

informação para construir o classificador

1Aprendizagem de Máquina, CIn/UFPE, Prof. Francisco de A.T. de Carvalho


I Abordagem posśıvel: usar os exemplospara estimar

I as probabilidades a prioriI as densidades condicionais das classes

I usar essas estimativas como se fossem os

verdadeiros valores



I Dificuldades dessa abordagem: estimaçãoda funções densidades das classes

I O número de exemplos (pre-classificados)em geral é pequeno

I dificuldades são grandes quando adimensionalidade do vetor de atributos égrande



I Simplificação do Problema:I supor que p(x|ωi) ∼ N(µi ,Σi)I os parâmetros µi ,Σi são desconhecidos

I Em vez de precisar estimarI uma função desconhecida p(x|ωi)I é necessário estimar os parâmetros µi ,Σi

I Abordagens para a estimação deparâmetros:

I máxima verossimilhançaI estimação Bayesiana


Estimação com Máximo de Verossimilhana5

I Prinćıpio Geral: c amostras D1, . . . ,DcI Cada amostra corresponde a uma das c

classes

I Os exemplos da amostra Dj são

constrúıdos independentemente segundo a

função p(x|ωi)I Esses exemplos são resultados de variáveis

aleatórias independentes e identicamente

distribud́as5Aprendizagem de Máquina, CIn/UFPE, Prof. Francisco de A.T. de Carvalho


I Problema: usar as informações fornecidas

pelas amostras para estimar θ1, . . ., θcI Suposição: os parâmetros das diferentes

classes são independentes

I As amostras Di não são informativos para

θj



I c problemas independentes da seguinte

forma:

I usar o conjunto de treinamento D cujos

exemplos são constrúıdos

independentemente a partir da função

densidade de probabilidade p(x|ωi) paraestimar θ



I D = {x1, . . . , xn}: amostra de nexemplos independentes

I Então P(D|θ) =n∏

k=1

p(xk |θ)

I P(D|θ) verossimilhança de θ em relaçãoao conjunto de exemplos

I A estimativa de máxima verossimilhança

de θ é o valor θ̂ que maximiza P(D|θ)I θ̂ é o valor de θ mais compat́ıvel com os

exemplos observados9Aprendizagem de Máquina, CIn/UFPE, Prof. Francisco de A.T. de Carvalho


I Observação: é mais fácil trabalhar com o

logaritmo da verossimilhança do que com

a própria verossimilhança

I Como o logaritmo é monotonicamente

crescente, o θ que maximiza a

log-verossimilhança tambm maximiza a

verossimilhança



I Seja θ=

θ1. . .θd

e seja ∇θ o operadorgradiente ∇θ =

∂∂θ1

. . .∂∂θd

I Função log-verossimilhança:

l(θ) = lnP(D|θ)



I Estimativa de máxima verossimilhança de

θ: θ̂= arg maxθ

l(θ)

I l(θ) = lnP(D|θ) = ln∏k=1

p(xk |θ) =

n∑k=1

ln p(xk |θ)⇒



I ∇θl(θ) =n∑

k=1

∇θ ln p(xk |θ)

I A estimativa de máxima verossimilhança

de θ é obtida do conjunto de d equações

∇θl(θ) = 0


Distribuição normal univariada15

I Distribuição normal univariada

p(x ,θ) =1√

2πσ2exp

[−1

2

(x − µσ

)2]θ=

(µ

σ2

)



I D = {x1, . . . , xn}: conjunto deaprendizagem

I ln (p(xk |θ)) =

ln

(1√

2πσ2exp

[−1

2

(x − µσ

)2])=

−12

ln (2πσ2)− 12σ2

(xk − µ)2



I Assim: ∇θ ln (p(xk |θ)) =[∂∂µ

(−12 ln (2πσ

2)− 12σ2

(xk − µ)2)

∂∂(σ2)

(−12 ln (2πσ

2)− 12σ2

(xk − µ)2) ] =[

1σ2

(xk − µ)− 1

2σ2+ (xk−µ)

2

2(σ2)2

]I Estimativa de máxima verossimilhança de

θ deve satisfazer:

∇θl(θ) =n∑

k=1

∇θ ln p(xk |θ) = 0



I Então:n∑

k=1

1σ̂2(xk − µ̂)− 1

2σ̂2+ (xk−µ̂)

2

2(σ̂2)2

= 0I

∑nk=1 1σ̂2(xk − µ̂)∑nk=1− 12σ̂2 +

(xk−µ̂)2

2(σ̂2)2

= [ 00

]

I

[µ̂

σ̂2

]=

[1n

∑nk=1 xk

1n

∑nk=1(xk − µ̂)2

]



I µ̂ =1

n

n∑k=1

xk

I σ̂2 =1

n

n∑k=1

(xk − µ̂)2


Distribuição normal multivariada20

I D = {x1, . . . , xn}: conjunto deaprendizagem

I p(xk |θ) =1

(2π)d2 |Σ|

12

exp[−12(xk − µ)

′Σ−1(xk − µ)

]I θ=

(µ

Σ

)I |Σ−1| = 1

|Σ|20Aprendizagem de Máquina, CIn/UFPE, Prof. Francisco de A.T. de Carvalho


I ln p(xk |θ) = −12 ln(

(2π)d

|Σ−1|

)−

12tr(

Σ−1(xk − µ)′(xk − µ)

)I (algebra matricial:

(xk − µ)′Σ−1(xk − µ) =

tr(

(xk − µ)′Σ−1(xk − µ)

)=

tr(

Σ−1(xk − µ)′(xk − µ)

)I (algebra matricial:

tr(ABC ) = tr(CAB) = tr(BCA)22Aprendizagem de Máquina, CIn/UFPE, Prof. Francisco de A.T. de Carvalho


I∂

∂Σ−1 lnP(xk |θ) =−12(|Σ−1|(2π)d× 0×|Σ

−1|−(2π)d |Σ−1|Σ|Σ−1|2

+(xk − µ)(xk − µ)′)

=

−Σ2 +12(xk − µ)(xk − µ)

′

I (algebra matricial:

tr(ABC ) = tr(CAB) = tr(BCA)

I (calculo matricial: ∂∂B tr(ABC ) =∂∂B tr(BCA) = (CA)

′= A

′C′)



I ∇θ ln (P(xk |θ)) =[Σ−1(xk − µ)

−Σ2 +12(xk − µ)(xk − µ)

′

]I Estimativa de máxima verossimilhança de

θ deve satisfazer:

∇θl(θ) =n∑

k=1

∇θ ln p(xk |θ) = 0



I

n∑k=1

[Σ̂−1(xk − µ̂)

−Σ̂2 +12(xk − µ̂)(xk − µ̂)

′

]=[

00

]

I

[µ̂)

Σ̂

]=

1

n

n∑k=1

xk

1

n

n∑k=1

(xk − µ̂)(xk − µ̂)′



I µ̂=1

n

n∑k=1

xk

I Σ̂ =1

n

n∑k=1

(xk − µ̂)(xk − µ̂)′


Distribuição de Bernoulli multivariada27

I Seja D = {x1, . . . , xn} n exemplos da

classe ω onde xk =

xk1

...

xki...

xkd

, xki ∈ {0, 1},θi = P [xki = 1|ω], e1− θi = P [xki = 0|ω]



I Probabilidade condicional

P(xk |θ) =d∏i=1

θxkii (1− θi)

1−xki

θ=

θ1...

θi...

θd



I lnP(xk |θ) = lnd∏i=1

θxkii (1− θi)

1−xki =

d∑i=1

[xki ln θi + (1− xki) ln (1− θi)]


∂∂θ1

lnP(xk |θ)...

∂∂θi

lnP(xk |θ)...

∂∂θd

lnP(xk |θ)




xk1θ1− 1−xk11−θ1...

xkiθi− 1−xki1−θi...

xkdθd− 1−xkd1−θd

I Estimativa de máxima verossimilhança de

θ deve satisfazer:

∇θl(θ) =n∑

k=1

∇θ ln p(xk |θ) = 0



I Entãon∑

k=1

xk1θ̂1− 1−xk1

1−θ̂1...xkiθ̂i− 1−xki

1−θ̂i...xkdθ̂d− 1−xkd

1−θ̂d

= 0

I

∑nk=1(

xk1θ̂1− 1−xk1

1−θ̂1)

...∑nk=1(

xkiθ̂i− 1−xki

1−θ̂i)

...∑nk=1(

xkdθ̂d− 1−xkd

1−θ̂d)

= 031Aprendizagem de Máquina, CIn/UFPE, Prof. Francisco de A.T. de Carvalho


I

∑nk=1 xk1θ̂1

− n−∑n

k=1 xk11−θ̂1

...∑nk=1 xkiθ̂i− n−

∑nk=1 xki

1−θ̂i...∑n

k=1 xkdθ̂d

− n−∑n

k=1 xkd1−θ̂d

= 0

I

∑nk=1 xk1 − θ̂1

∑nk=1 xk1 − nθ̂1 + θ̂1

∑nk=1 xk1

...∑nk=1 xki − θ̂i

∑nk=1 xki − nθ̂i + θ̂i

∑nk=1 xki

...∑nk=1 xkd − θ̂d

∑nk=1 xkd − nθ̂d + θ̂d

∑nk=1 xkd

= 0



I

θ̂1...

θ̂i...

θ̂d

=

1n

∑nk=1 xk1...

1n

∑nk=1 xki...

1n

∑nk=1 xkd

I θ̂ =

1

n

n∑k=1

xk


Funções discriminantes - densidade normal34

I Funções discriminantes populacionais:

gi(x) = ln p(x|ωi) + lnP(ωi)I Se p(x|ωi) ∼ N(µ,Σi)

I gi(x) = −1

2(x− µi)

′Σ−1i (x− µi)−

d

2ln 2π − 1

2ln |Σi | + lnP(ωi)



I Σi arbitrário: somente o termod2 ln 2π

pode ser ignorado

I gi(x) = x′Wix + w

′ix + wi0

I onde Wi = −12Σ−1i , wi = Σ

−1i µi ,

wi0 = −12µ′iΣ−1i µi − 12 ln |Σi | + lnP(ωi)

I Regra de classificação: classificar x comoda classe r se r = arg max

i=1,...,cgi(x)


Funções discriminantes amostrais36

I Vetor de médias amostral: x̄i =1

ni

ni∑k=1

xik

I Matriz de covariâncias amostral:

Si =1

ni − 1

ni∑k=1

(xik − x̄i)(xik − x̄i)′



I Funções discriminantes amostrais:

ĝi(x) = x′Ŵix + ŵ

′ix + ŵi0

I onde Ŵi = −12S−1i , ŵi = S

−1i x̄i ,

ŵi0 = −12x̄′iS−1i x̄i − 12 ln |Si | + lnP(ωi)


i=1,...,cĝi(x)



I Σi = Σ: as matrizes de covariâncias detodas as classes so idênticas

I |Σi | e d2 ln 2π podem ser ignoradosI Funções discriminantes populacionais

gi(x) = w′ix + wi0

I onde wi = Σ−1i µi ,

wi0 = −12µ′iΣ−1i µi + lnP(ωi)


i=1,...,cgi(x)



I Vetor de médias amostral: x̄i =1

ni

ni∑k=1

xik

I Matriz de covariâncias amostral:

Si =1

ni − 1

ni∑k=1

(xik − x̄i)(xik − x̄i)′

I Matriz de covariâncias amostrais

combinadas:

SCom =(n1 − 1)S1 + . . . + (nc − 1)Sc

n1 + . . . + nc − c39Aprendizagem de Máquina, CIn/UFPE, Prof. Francisco de A.T. de Carvalho


I Funções discriminantes amostrais

ĝi(x) = ŵ′ix + ŵi0

I onde ŵi = S−1Comµi ,

wi0 = −12µ′iS−1Comµi + lnP(ωi)


i=1,...,cĝi(x)


Documents

I Classi cador otimo: necess ario conhecer de antem~aofatc/AM/Estimacao-Parametros.pdf · Estima˘c~ao de Par^ametros1 I Classi cador otimo: necess ario conhecer de antem~ao I as