K-means como um caso limite do algoritmo EM para misturas de Gauss com covariâncias indo para

8

Meu objetivo é ver que o algoritmo K-means é de fato o algoritmo de Expectativa-Maximização para misturas Gaussianas, em que todos os componentes têm covariância no limite como .σ2Ilimσ0

Suponha que temos um conjunto de dados {x1,,xN} de observações de variável aleatória X .
A função objetivo para médias M é dada por:

J=n=1Nk=1Krnk||xnμk||2
em que rnk é uma variável de indicador binário de uma designação definitiva de x_nxn para o cluster k .
(ponto de dados se xn é atribuído a agrupar k , então rnk=1 e rnj=0 para j k).
O algoritmo K-means minimiza J através da iteração até a convergência, o que envolve duas etapas sucessivas:
(E) minimizaJ com relação a {rnk}n,k mantendo todos μk fixos
(M) minimize J com relação a {μk}k mantendo todos os rnk fixos

Em geral, denotando todos os dados observados por X , todas as variáveis ​​latentes por Z e o conjunto de todos os parâmetros do modelo por θ , o algoritmo EM maximiza a distribuição posterior p(θ|X) através da iteração até a convergência, de duas etapas alternadas:
(E ) calcule a expectativa Q(θ,θold):=Zp(Z|X,θold)logp(Z,X|θ)
(M) encontre θnew=argmaxθQ(θ,θold)

Agora, considere a distribuição gaussiana mistura: Introduzindo um latente -dimensional binário variável aleatória por , vemos que: AssimK z p ( z k = 1 ) = π k p ( X , Z ) = N n = 1 K μ k , Σ k ) z n k γ ( z k

p(x)=k=1KπkN(x|μk,Σk)
Kzp(zk=1)=πk
p(X,Z)=n=1Nk=1KπkznkN(xn|μk,Σk)znk
logp(X,Z|μ,Σ,π)=N n=1K k=1znk)E(znk)=γ(znk)Q((
γ(zk):=p(zk=1|x)=πkN(x|μk,Σk)j=1KπjN(x|μj,Σj)
logp(X,Z|μ,Σ,π)=n=1Nk=1Kznk(logπk+logN(xn|μk,Σk))
E(znk)=γ(znk)
Q((π,μ,Σ),(π,μ,Σ)old)=n=1Nk=1Kγ(znk)(logπk+logN(xn|μk,Σk))

Se agora todos os gaussianos no modelo de mistura têm covariância , considerando o limite , posso mostrar facilmente que onde é definido acima. Portanto, a etapa (E) atualiza como no algoritmo K-means.σ 0 γ ( z n k ) σ2Iσ0 r n k r n kγ(znk)rnkrnkrnk

No entanto, tenho problemas com a maximização de nesse contexto, como para . É verdade que até alguma multiplicação constante e escalar: ?Q((π,μ,Σ),(π,μ,Σ)old)xμ limσ0log(N(x|μ,σ2))=
limσ0Q((π,μ,Σ),(π,μ,Σ)old)=J

Talvez esteja faltando alguma coisa. Algum conselho?

Andrzej Neugebauer
fonte
2
Bem-vindo ao site, @Andrzej. Poste a pergunta completa - não espere que as pessoas pesquisem seu livro.
StasK 04/10
1
Caro StasK, Acabei de publicar a pergunta completa e espero que esteja clara agora.
Andrzej Neugebauer

Respostas:

3

É verdade que até alguma multiplicação constante e escalar: ?limσ0Q((π,μ,Σ),(π,μ,Σ)old)=J

Não é esse o caso, pois - como você se observou - o limite diverge.

No entanto, se primeiro transformarmos e depois tomarmos o limite, convergiremos para o objetivo de k-mean. Para e , temosQΣk=σ2Iπk=1/K

Q=n,kγnk(logπk+logN(xnμk,Σk))=Nlog1K1σ2n,kγnk||xnμk||2ND2log2πσ2.

Multiplicando por (que não afeta o algoritmo EM, pois não é otimizado, mas constante) e coletando todos os termos constantes em , vemos que Observe que maximizar essa função com relação a para qualquer e dá o mesmo resultar como a função objetivo acima, ou seja, é uma formulação equivalente da etapa M. Mas tomar o limite agora produz .σ2σC

Qn,kγnk||xnμk||2+σ2C.
μγσJ

Como um aparte, na minha opinião, uma formulação um pouco mais elegante do EM é usar a função objetivo Usando essa função de objetivo, o algoritmo EM equivale a alternância entre otimizar com relação a (etapa M) e (etapa E). Tomando o limite, vemos que o passo M e o passo E convergem para o algoritmo k-means.Fμγ

F(μ,γ)=n,kγnklogπkN(xnμk,Σk)/γnkn,kn,kγnk||xnμk||2σ2n,kγnklogγnk+σ2C.
Fμγ

Veja também uma visão alternativa do EM .

Lucas
fonte