Por que o problema de desordem é intratável para amostras de grandes tamanhos?

13

Suponha que tenhamos um conjunto de pontos . Cada ponto é gerado usando a distribuição Para obter posterior para , escrevemos p (x | \ mathbf {y}) \ propto p (\ mathbf {y} | x) p (x) = p (x) \ prod_ {i = 1} ^ N p (y_i x) De acordo com o artigo de Minka na expectativa de propagação precisamos 2 ^ N cálculos para se obter posterior p (x | \ mathbf {y}) e, assim, torna-se intratável problema para a grande amostra tamanhos N . No entanto, não consigo descobrir por que precisamos dessa quantidade de cálculos nesse caso, porque, para um único y_iy={y1,y2,,yN}yi

p(yi|x)=12N(x,1)+12N(0,10).
x
p(x|y)p(y|x)p(x)=p(x)i=1Np(yi|x).
2Np(x|y)Nyia probabilidade tem o formato
p(yi|x)=122π(exp{12(yix)2}+110exp{120yi2}).

Usando esta fórmula, obtemos posterior pela multiplicação simples de p(yi|x) , portanto, precisamos apenas de N operações e, portanto, podemos resolver esse problema exatamente para tamanhos grandes de amostra.

Faço experimentos numéricos para comparar se realmente obtenho o mesmo posterior no caso de calcular cada termo separadamente e no caso de usar produto de densidades para cada . Os posteriores são os mesmos. Veja onde estou errado? Alguém pode me esclarecer por que precisamos de operações para calcular posteriormente o dado e a amostra ?2 N x yyiinsira a descrição da imagem aqui2Nxy

Alexey Zaytsev
fonte
Uma operação por termo e termos, por isso precisamos de operações . Além disso, olho o artigo de Minka e o capítulo de Bishop sobre inferência aproximada novamente. Ambos sugerem que queremos estimar e obter posterior para . O ( N ) xNO(N)x
Alexey Zaytsev
Estou entendendo corretamente que seus são univariados? Se assim for, você pode resolver isso em , que é considerado tratável independentemente de O ( n log ( n ) ) nyiO(nlog(n))n
user603
1
@ Alexey Depois de reler este parágrafo, acho que o autor não menciona operações. Ele apenas aponta que "o estado de crença para é uma mistura de gaussianos" . x 2 N2Nx2N
1
@ Procrastinator De acordo com o artigo, queremos usar a propagação de crenças, mas não podemos usá-los porque precisamos prosseguir com a mistura de gaussianos. Então a questão é por que queremos usar a BP? Outra questão surge no caso de lermos o capítulo 10.7.1 no PRML de Bishop ou assistirmos à videoconferência de Minka . Depois disso, a resposta não é clara. 2N
Alexey Zaytsev
1
@ Alexey Eu acho que a lógica por trás disso é diferente. O autor descreve o que acontece se você usar a propagação de crenças, a fim de enfatizar algumas dificuldades quando é grande e, em seguida, promover sua "propagação de expectativa". Ele menciona que a propagação de crenças requer o uso de uma mistura de Gaussianos para o estado de crença para que se torna complicado quando é grande. Não há menção ao número de operações necessárias, mas à complexidade do estado de crença para . 2 N x N xN2NxNx

Respostas:

4

Você está certo que o jornal está dizendo a coisa errada. Você certamente pode avaliar a distribuição posterior de em um local conhecido usando operações . O problema é quando você deseja calcular momentos do posterior. Para calcular exatamente a média posterior de , você precisaria de operações. Esse é o problema que o jornal está tentando resolver.O ( n ) x 2 NxO(n)x2N

Tom Minka
fonte
2

Você perdeu o ponto de que a distribuição é uma mistura de gaussianos: cada amostra é distribuída conforme com probabilidade e como (distribuição de desordem para , independente de ) com probabilidade .yip(yi|x)1wpc(y)yxw

Seja a variável indicadora indicando que a amostra foi extraída da distribuição de desordem; portanto, se for , indica que a amostra foi retirada de . Obviamente, se a amostra foi retirada da distribuição de desordem, seu valor é irrelevante para a estimativa de .cii0p(y|x)x

É a presença dos possíveis estados conjuntos para essas variáveis ​​indicadoras que causam o problema.2N

Dave
fonte
No entanto, podemos descartar variáveis adicionais , pois precisamos obter uma solução posterior máxima do problema. Posterior para tem uma forma clara, portanto não somos obrigados a levar em consideração todos os estados presentes. Portanto, a pergunta é "Por que precisamos dessa quantidade de cálculos, caso desejemos encontrar uma solução posterior máxima?" x 2 Ncix2N
Alexey Zaytsev
A maximização precisa ser tomada sobre os estados das variáveis . c
8603 Dave
Não sabemos , então nós integramos out (resumir over) c i . Isso pode ser feito de maneira direta, não é? cici
Alexey Zaytsev
Dirija sim, mas o número de estados (termos) cresce como , o que pode ser computacionalmente problemático. 2N
Dave
Podemos fazer isso para cada observação de maneira independente, portanto temos complexidade , não O ( 2 n ) . O(n)O(2n)
Alexey Zaytsev