Pourquoi le problème d'encombrement est-il insoluble pour les grands échantillons?

13

Supposons que nous ayons un ensemble de points . Chaque point est généré en utilisant la distribution Pour obtenir postérieur pour nous écrivons Selon le document de Minka sur Expectation propagation nous avons besoin calculs pour obtenir a posteriori p (x | \ mathbf {y}) et, donc, problème devient intraitable pour échantillons de grande taille N . Cependant, je ne peux pas comprendre pourquoi avons-nous besoin d'une telle quantité de calculs dans ce cas, car pour un seul 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)Nyila vraisemblance a la forme
p(yi|x)=122π(exp{12(yix)2}+110exp{120yi2}).

En utilisant cette formule, nous obtenons a posteriori par simple multiplication de p(yi|x) , nous n'avons donc besoin que de N opérations, et nous pouvons donc résoudre exactement ce problème pour des échantillons de grande taille.

Je fais une expérience numérique pour comparer est-ce que j'obtiens vraiment le même postérieur dans le cas où je calcule chaque terme séparément et dans le cas où j'utilise un produit de densités pour chaque . Les postérieurs sont les mêmes. Voir Où je me trompe? Quelqu'un peut-il me dire clairement pourquoi avons-nous besoin de opérations pour calculer a posteriori pour donné et échantillon ?2 N x yyienter image description here2Nxy

Alexey Zaytsev
la source
Une opération par terme et termes, nous avons donc besoin d'opérations . De plus, je regarde à nouveau l'article de Minka et le chapitre de Bishop sur l'inférence approximative. Les deux suggèrent que nous voulons estimer et obtenir a posteriori pour . O ( N ) xNO(N)x
Alexey Zaytsev
Est-ce que je comprends bien que vos sont univariés? Si oui, vous pouvez résoudre ce problème dans qui est considéré comme traitable indépendamment de O ( n log ( n ) ) nyiO(nlog(n))n
user603
1
@Alexey Après avoir relu ce paragraphe, je pense que l'auteur ne mentionne pas les opérationsIl souligne simplement que "l'état de croyance pour est un mélange de gaussiens" . x 2 N2Nx2N
1
@Procrastinator selon l'article, nous voulons utiliser la propagation des croyances, mais nous ne pouvons pas l'utiliser car nous devons procéder à un mélange de gaussiens. Alors la question est pourquoi voulons-nous utiliser BP? Une autre question se pose au cas où nous lirions le chapitre 10.7.1 dans Bishop's PRML ou regarder videolecture par Minka . Après cela, la réponse n'est pas aussi claire. 2N
Alexey Zaytsev
1
@Alexey Je pense que la logique derrière cela est différente. L'auteur décrit ce qui se passe si vous utilisez la propagation de croyances, afin de souligner certaines difficultés lorsque est grand, puis de promouvoir sa "propagation d'attentes". Il mentionne que la propagation des croyances nécessite l'utilisation d'un mélange de gaussiens pour l'état de croyance pour qui se complique lorsque est grand. Il n'y a aucune mention du nombre d'opérations requises mais de la complexité de l'état de croyance pour . N2NxNx

Réponses:

4

Vous avez raison de dire que le journal dit la mauvaise chose. Vous pouvez certainement évaluer la distribution postérieure de à un emplacement connu en utilisant des opérations . Le problème est lorsque vous voulez calculer des moments de la partie postérieure. Pour calculer exactement la moyenne postérieure de , vous auriez besoin de opérations. C'est le problème que le document tente de résoudre.xO(n)x2N

Tom Minka
la source
2

Vous avez manqué le point que la distribution est un mélange de gaussiens: chaque échantillon est soit distribué selon avec probabilité et comme (distribution d'encombrement pour , indépendante de ) avec probabilité .yip(yi|x)1wpc(y)yxw

Soit la variable indicatrice indiquant que l'échantillon été tiré de la distribution du fouillis; ainsi, s'il vaut cela indique que l'échantillon a été tiré de . De toute évidence, si l'échantillon a été tiré de la distribution de fouillis, sa valeur n'est pas pertinente pour l'estimation de .cii0p(y|x)x

C'est la présence des états conjoints possibles pour ces variables indicatrices qui cause le problème.2N

Dave
la source
Cependant, nous pouvons supprimer des variables supplémentaires , car nous devons obtenir une solution postérieure maximale du problème. Postérieur pour a une forme claire, nous ne sommes donc pas obligés de prendre en compte tous les états présents. Donc, la question est "Pourquoi avons-nous besoin de cette quantité de calculs au cas où nous voudrions trouver une solution postérieure maximale?" cix2N
Alexey Zaytsev
La maximisation doit être prise sur les états pour les variables . c
Dave
Nous ne connaissons pas , nous intégrons donc (résumons) c i . Cela peut se faire de manière directe, n'est-ce pas? cici
Alexey Zaytsev
Direct oui, mais le nombre d'états (termes) croît comme , ce qui peut être problématique en termes de calcul. 2N
Dave
Nous pouvons le faire pour chaque observation de manière indépendante, nous avons donc une complexité et non O ( 2 n ) . O(n)O(2n)
Alexey Zaytsev