Derivando o algoritmo K-means como um limite de Maximização de Expectativas para Misturas Gaussianas

8

Christopher Bishop define o valor esperado da função de probabilidade do log de dados completos (ou seja, assumindo que recebemos os dados observáveis ​​X e os dados latentes Z) da seguinte maneira:

(1)EZ[lnp(X,Zμ,Σ,π)]=n=1Nk=1Kγ(znk){lnπk+lnN(xn μk,Σk)}

onde γ(znk) é definido como:

2)πkN(xn μk,Σk)j=1KπjN(xn μj,Σj)

A idéia, como descrita, é considerar um Modelo de Mistura Gaussiano no qual as matrizes de covariância dos componentes da mistura são dadas por ϵEu , em que ϵ é um parâmetro de variação compartilhado por todos os componentes, como aquele:

(3)p(xμk,Σk)=1(2πϵ)M2exp{-12ϵ__x-μk__2}

e assim, γ(znk) agora é definido como:

4)πkexp{-__xn-μk__2/2ϵ}j=1Kπjexp{-__xn-μj__2/2ϵ}

O argumento agora é o seguinte:

se considerarmos o limite , vemos que no denominador o termo para o qual é menor, passará a zero mais lentamente e, portanto, as responsabilidades para o ponto de dados vão para zero, exceto pelo termo j, pela qual a responsabilidade irá para a unidade. Assim, nesse limite, obtemos uma atribuição rígida de pontos de dados para clusters, assim como no algoritmo -eans, de modo queϵ0 0__xn-μj__2γ(znk)xnγ(znk)Kγ(znk)rnk

onde é definido como:rnk

(5)f(n)={1E se k=arg minj__xn-μj__20 0de outra forma

Minha pergunta é como o argumento acima se aplica? Ou seja, o que significa um termo ir para zero ? E como levar o limite na eqn resulta em uma responsabilidade binária?mais devagarϵ0 04

BitRiver
fonte
1
Quando a zero, vai para zero para todos os , mas em velocidades diferentes, dependendo de , o menor reúna todo o peso no limite. exp { - x n - μ k 2 / 2 ε } = exp { - δ n / ε } n δ n δ nϵexp{-__xn-μk__2/2ϵ}=exp{-δn/ϵ}nδnδn
Xi'an
1
(explicação adicional) Se você considerar como o menor , poderá reescrever todos os termos como , o que significa que todos os termos zerados com exceto um, aquele para o qual . δ n exp { ( δ - δ n ) / ϵ } ϵ δ - δ n = 0δδnexp{(δ-δn)/ϵ}ϵδ-δn=0 0
Xi'an
@ Xi'an Você gostaria de fornecer mais elaboração? O que você quer dizer com "o menor então reúne todo o peso no limite"? E como o termo para o qual = 0 é avaliado como unidade? Quero dizer, o numerador é 0, certo? δ - δ nδnδδn
BitRiver

Respostas:

8

Vamos escrever Então Se usarmos teremos where exceto em queπ k exp { - x n - μ k 2 / 2 ε }

__xn-μk__2=δk.
δ=minnδn
πkexp{-__xn-μk__2/2ϵ}j=1Kπjexp{-__xn-μj__2/2ϵ}=πkexp{-δk/2ϵ}j=1Kπjexp{-δj/2ϵ}
π k exp { - δ k / 2 ϵ }
δ=minnδn,
δ*-δk<0K=k*δ*-δk*=0kk*limε0πkexp{(δ-δk)/2ϵ
πkexp{-δk/2ϵ}j=1Kπjexp{-δj/2ϵ}=πkexp{(δ-δk)/2ϵ}j=1Kπjexp{(δ-δj)/2ϵ}
δ-δk<0 0k=kδ-δk=0 0 . Portanto, para todos os , , pois, para , enquanto kkum>0limε0exp{-um/ε}=0limε0π k * exp{(δ-δ k )/
limϵ0 0πkexp{(δ-δk)/2ϵ}j=1Kπjexp{(δ-δj)/2ϵ}=limϵ0 0πkexp{(δ-δk)/2ϵ}πk+jkπjexp{(δ-δj)/2ϵ}=0 0
uma>0 0
limϵ0 0exp{-uma/ϵ}=0 0
limϵ0 0πkexp{(δ-δk)/2ϵ}j=1Kπjexp{(δ-δj)/2ϵ}=limϵ0 0πk×1πk+jkπjexp{(δ-δj)/2ϵ}=1
Xi'an
fonte