o que se quer dizer com integração numérica é muito caro?

Estou lendo sobre a inferência bayesiana e me deparei com a frase "a integração numérica da probabilidade marginal é muito cara"

Eu não tenho formação em matemática e queria saber o que exatamente significa caro aqui? É apenas em termos de poder computacional ou há algo mais.

No contexto de problemas computacionais, incluindo métodos numéricos para inferência bayesiana, a frase "muito caro" geralmente pode se referir a duas questões

1. um problema específico é "grande" demais para calcular um " orçamento " específico
2. uma abordagem geral escala mal, ou seja, possui alta complexidade computacional

Nos dois casos, os recursos computacionais que compõem o "orçamento" podem consistir em itens como ciclos de CPU ( complexidade de tempo ), memória ( complexidade de espaço ) ou largura de banda de comunicação ( dentro ou entre nós de computação). Na segunda instância, "muito caro" significaria intratável .

No contexto da computação bayesiana, a cotação provavelmente se refere a problemas de marginalização de um grande número de variáveis .

Por exemplo, o resumo deste artigo recente começa

A integração é afetada pela maldição da dimensionalidade e rapidamente se torna intratável à medida que a dimensionalidade do problema aumenta.

e continua dizendo

Propomos um algoritmo aleatório que ... por sua vez, pode ser usado, por exemplo, para computação marginal ou seleção de modelo.

(Para comparação, este capítulo recente do livro discute métodos considerados "não muito caros".)

Vou dar um exemplo em caso discreto para mostrar por que a integração / soma total é muito cara.

Suponha que tenhamos $100$ variáveis ​​aleatórias binárias e temos a distribuição conjunta $P(X_1, X_2, \cdots, X_{100})$. (De fato, é impossível armazenar a distribuição conjunta em uma tabela, porque existem$2^{100}$valores. Vamos supor que temos isso na tabela e na RAM agora.)

Para obter uma distribuição marginal em $P(X_1)$, precisamos somar outras variáveis ​​aleatórias. (No caso contínuo, ele é integrado ao longo.)

Estamos resumindo $99$ variáveis, portanto, há número de exponenciação de operações, neste caso, é $2^{99}$, que é um número enorme que todos os computadores do mundo não conseguirão fazer.

Na literatura de modelos gráficos probabilísticos , essa maneira de calcular a distribuição marginal é chamada de abordagem de "força bruta" para realizar "inferência". Pelo nome, podemos saber que é caro. E as pessoas usam muitas outras maneiras de realizar a inferência, por exemplo, obtendo a distribuição marginal de forma eficaz. "Outras formas", incluindo inferência aproximada , etc.

Usually when performing Bayesian inference it's easy to encounter heavy integration over nuisance variables for instance. Another example can be a numerical sampling as in this case from a likelihood function, meaning to perform a random sampling from a given distribution. As the number of model parameters increases, this sampling becomes extremely heavy and various computational methods have been developed to speed up the procedure and allow very fast implementations, keeping of course a high level of accuracy. These tecniques are for instance MC, MCMC, Metropolis ecc. Take a look in Bayesian data analysis by Gelman et. al it should give you a broad introduction! good luck