13

I am reading about Bayesian inference and I came across the phrase "numerical integration of the marginal likelihood is too expensive"

I do not have a background in mathematics and I was wondering what exactly does expensive mean here? Is it just in terms of computation power or is there something more.

kjetil b halvorsen
  • 63,378
  • 26
  • 142
  • 467
discretetimeisnice
  • 427
  • 3
  • 12
  • 6
    It means it takes too much computational power, probably in terms of CPU time (since all computing resources are all essentially either memory or CPU). – Sycorax Oct 25 '16 at 13:57
  • 3
    Actually, communication bandwidth can become an issue sometimes (e.g. between cache/RAM/disk serially, or between compute nodes in parallel). – GeoMatt22 Oct 25 '16 at 14:57
  • It means that it takes too much time, for a single computer, our for a network of computers, to carry out the computation. – Jack Maddington Oct 25 '16 at 15:41
  • 2
    And if the marginal likelihood is needed inside of some loop, what counts as too expensive is much less. Eg. a 1 second integration routine sounds fast, but it may be "too expensive" if you need to do it 1 million times... – Matthew Gunn Oct 25 '16 at 17:22
  • Expensive in terms of computational effort, as in it takes more effort to compute it than you can afford, as in it takes too much time, or needs too many processors to do in a reasonable time. – user253751 Oct 26 '16 at 04:52
  • As others have already mentioned, it just means that it takes too long computationally. Some other expensive routines are solving $Ax=b$ by inverting $A$ and the Richardson method for solving $Ax=b$. – TheIncredibleZ1 Oct 26 '16 at 16:24

3 Answers3

16

In the context of computational problems, including numerical methods for Bayesian inference, the phrase "too expensive" generally could refer to two issues

  1. a particular problem is too "large" to compute for a particular "budget"
  2. a general approach scales badly, i.e. has high computational complexity

For either case, the computational resources comprising the "budget" may consist of things like CPU cycles (time complexity), memory (space complexity), or communication bandwidth (within or between compute nodes). In the second instance, "too expensive" would mean intractable.

In the context of Bayesian computation, the quote is likely referring to issues with marginalization over a large number of variables.

For example, the abstract of this recent paper begins

Integration is affected by the curse of dimensionality and quickly becomes intractable as the dimensionality of the problem grows.

and goes on to say

We propose a randomized algorithm that ... can in turn be used, for instance, for marginal computation or model selection.

(For comparison, this recent book chapter discusses methods considered "not too expensive".)

GeoMatt22
  • 11,997
  • 2
  • 34
  • 64
  • 4
    This is a great answer. I will just add, though, that "expensive" may increasingly also be taken quite literally. -- one can increase one's computational power and storage dramatically (to supercomputer levels, for as long as one needs), very easily these days (and quite cheaply) ... but for large problems it will still work out to be *too expensive* -- in that it will literally cost more actual money than you have available. – Glen_b Oct 25 '16 at 21:10
  • 1
    @Glen_b that is a good point! I imagine this meaning is less common in the *published* literature ... but more common in proposals (and their reviews!) – GeoMatt22 Oct 25 '16 at 21:14
  • @GeoMatt22 It's actually another way of stating the same meaning, if you think about it. – user253751 Oct 26 '16 at 04:54
  • @GeoMatt22 Thank you! I now perfectly understand what does expensive mean in a Bayesian context. – discretetimeisnice Oct 27 '16 at 09:24
9

I will give you an example on discrete case to show why integration / sum over is very expensive.

Suppose we have $100$ binary random variables, and we have the joint distribution $P(X_1, X_2, \cdots, X_{100})$. (In fact, it is impossible to store the joint distribution in a table, because there are $2^{100}$ values. Let us assume we have the it in table and in RAM now.)

To get a marginal distribution on $P(X_1)$, we need to sum over other random variables. (In continuous case, it is integrate over.)

$$P(X_1)=\sum_{X_2}\sum_{X_3}\cdots \sum_{X_{100}}P(X_1, X_2, \cdots, X_{100})$$

We are summing over $99$ variables, Therefore, there are exponentiation number of operations, in this case, it is $2^{99}$, which is a huge number that all the computers in earth will not able to do.

In probabilistic graphical models literature, such way of calculating marginal distribution is called "brute force" approach to perform "inference". By name, we may know it is expensive. And people use many other ways to perform the inference, e.g., getting the marginal distribution effectively. "Other ways" including approximate inference, etc.

Haitao Du
  • 32,885
  • 17
  • 118
  • 213
  • 3
    Maybe you could also comment on why Bayesian approach is helpful here, as the question raised in this context. – Tim Oct 25 '16 at 14:29
5

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

Lcol
  • 83
  • 6
  • 3
    This answer doesn't seem to address the OP's main question around the meaning of "expensive" in this context. Or at least not very clearly. – Shufflepants Oct 25 '16 at 15:19
  • The short explanation is to introduce the reader to the meaning of computational demand when performing specific analysis in Bayesian statistic, since it stated to be not a mathematician. Anyway hope it was clear to someone – Lcol Oct 25 '16 at 21:59