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

Suponha que tenhamos um conjunto de pontos . Cada ponto é gerado usando a distribuição Para obter posterior para , escrevemos De acordo com o artigo de Minka na expectativa de propagação precisamos cálculos para se obter posterior e, assim, torna-se intratável problema para a grande amostra tamanhos . No entanto, não consigo descobrir por que precisamos dessa quantidade de cálculos nesse caso, porque, para um único $\mathbf{y} = \{y_1, y_2, \ldots, y_N \}$ $y_i$

p (y_{i} | x) = \frac{1}{2} N (x, 1) + \frac{1}{2} N (0, 10) .

$p(y_i| x) = \frac12 \mathcal{N}(x, 1) + \frac12 \mathcal{N}(0, 10).$

x

$x$

p (x | y) \propto p (y | x) p (x) = p (x) \prod_{i = 1}^{N} p (y_{i} | x) .

$p(x| \mathbf{y}) \propto p(\mathbf{y}| x) p(x) = p(x) \prod_{i = 1}^N p(y_i | x).$

2^{N}

$2^N$

p (x | y)

$p(x| \mathbf{y})$

N

$N$

y_{i}

$y_i$ a probabilidade tem o formato

p (y_{i} | x) = \frac{1}{2 \sqrt{2 π}} (\exp {- \frac{1}{2} (y_{i} - x)^{2}} + \frac{1}{\sqrt{10}} \exp {- \frac{1}{20} y_{i}^{2}}) .

$p(y_i| x) = \frac{1}{2 \sqrt{2 \pi}} \left( \exp \left\{-\frac12 (y_i - x)^2\right\} + \frac{1}{\sqrt{10}} \exp \left\{-\frac1{20} y_i^2\right\} \right).$

Usando esta fórmula, obtemos posterior pela multiplicação simples de $p(y_i| 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 ? $y_i$ insira a descrição da imagem aqui $2^N$ $x$ $\mathbf{y}$

bayesian mixture posterior 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 .

N

$N$

O (N)

$O(N)$

x

$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

y_{i}

$y_i$

O (n \log (n))

$O(n\log(n))$

n

$n$

user603

@ 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" .

2^{N}

$2^N$ $x$ $2^N$

@ 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.

2^{N}

$2^N$

Alexey Zaytsev

@ 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 .

N

$N$

2^{N}

$2^N$

x

$x$

N

$N$

x

$x$

Respostas:

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. $x$ $O(n)$ $x$ $2^N$

Tom Minka
fonte

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 . $y_i$ $p(y_i | x)$ $1-w$ $p_c(y)$ $y$ $x$ $w$

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 . $c_i$ $i$ $0$ $p(y|x)$ $x$

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

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?"

c_{i}

$c_i$

x

$x$

2^{N}

$2^N$

Alexey Zaytsev

A maximização precisa ser tomada sobre os estados das variáveis .

c

$c$

8603 Dave

Não sabemos

, então nós integramos out (resumir over)

. Isso pode ser feito de maneira direta, não é?

c_{i}

$c_i$

c_{i}

$c_i$

Alexey Zaytsev

Dirija sim, mas o número de estados (termos) cresce como

, o que pode ser computacionalmente problemático.

2^{N}

$2^N$

Dave

Podemos fazer isso para cada observação de maneira independente, portanto temos complexidade

, não

O (n)

$O(n)$

O (2^{n})

$O(2^n)$

Alexey Zaytsev