que veut-on dire par intégration numérique est trop cher?

Je lis sur l'inférence bayésienne et je suis tombé sur l'expression "l'intégration numérique de la probabilité marginale est trop chère"

Je n'ai pas de formation en mathématiques et je me demandais ce que signifie exactement cher ici? Est-ce juste en termes de puissance de calcul ou y a-t-il quelque chose de plus.

Dans le contexte des problèmes de calcul, y compris les méthodes numériques pour l'inférence bayésienne, l'expression "trop ​​cher" pourrait généralement se référer à deux questions

1. un problème particulier est trop "grand" pour être calculé pour un " budget " particulier
2. une approche générale évolue mal, c'est-à-dire a une grande complexité de calcul

Dans les deux cas, les ressources de calcul constituant le «budget» peuvent être constituées de choses comme des cycles CPU ( complexité temporelle ), de la mémoire ( complexité spatiale ) ou de la bande passante de communication (à l' intérieur ou entre les nœuds de calcul). Dans le deuxième cas, «trop cher» signifierait insoluble .

Dans le contexte du calcul bayésien, la citation fait probablement référence à des problèmes de marginalisation sur un grand nombre de variables .

Par exemple, le résumé de ce récent article commence

L'intégration est affectée par la malédiction de la dimensionnalité et devient rapidement insoluble à mesure que la dimensionnalité du problème augmente.

et continue en disant

Nous proposons un algorithme randomisé qui ... peut à son tour être utilisé, par exemple, pour le calcul marginal ou la sélection de modèle.

(À titre de comparaison, ce récent chapitre de livre traite des méthodes considérées comme "pas trop chères".)

Je vais vous donner un exemple sur cas discret pour montrer pourquoi l'intégration / la somme est très chère.

Supposons que nous ayons variables aléatoires binaires et que nous ayons la distribution conjointe . (En fait, il est impossible de stocker la distribution conjointe dans une table, car il y a valeurs. Supposons que nous l'avons maintenant dans la table et dans la RAM.)P ( X 1 , X 2 , ⋯ , X 100 ) 2 $100$$P(X_1, X_2, \cdots, X_{100})$$2^{100}$

Pour obtenir une distribution marginale sur , nous devons additionner d'autres variables aléatoires. (Dans le cas continu, il est terminé.)$P(X_1)$

Nous sommons plus de variables. Par conséquent, il y a un nombre d'exponentiation d'opérations, dans ce cas, c'est , ce qui est un nombre énorme que tous les ordinateurs de la terre ne pourront pas faire.2 $99$$2^{99}$

Dans la littérature sur les modèles graphiques probabilistes , une telle façon de calculer la distribution marginale est appelée approche de «force brute» pour effectuer une «inférence». Par son nom, nous savons peut-être que cela coûte cher. Et les gens utilisent de nombreuses autres façons d'effectuer l'inférence, par exemple, en obtenant efficacement la distribution marginale. "Autres moyens", y compris l' inférence approximative , etc.

Habituellement, lors de l'inférence bayésienne, il est facile de rencontrer une forte intégration sur des variables nuisibles, par exemple. Un autre exemple peut être un échantillonnage numérique comme dans ce cas à partir d'une fonction de vraisemblance, ce qui signifie effectuer un échantillonnage aléatoire à partir d'une distribution donnée. À mesure que le nombre de paramètres du modèle augmente, cet échantillonnage devient extrêmement lourd et diverses méthodes de calcul ont été développées pour accélérer la procédure et permettre des implémentations très rapides, en gardant bien sûr un haut niveau de précision. Ces techniques sont par exemple MC, MCMC, Metropolis ecc. Jetez un coup d'œil à l'analyse des données bayésiennes par Gelman et. il devrait vous donner une large introduction! bonne chance