22 ms·

That's true in the asymptotic, but the dimension find a way to rear its head in the constant to the big O through the variance of your estimator. It's still bet

That's true in the asymptotic, but the dimension find a way to rear its head in the constant to the big O through the variance of your estimator. It's still better than Riemann integration, but it sucks nonetheless. For instance, integrate the function f(x1,x2,...xd) = 6^d * x1 * (1-x1) * ... * xd * (1-xd) on the d-dimensional unit cub (the answer is 1, for all d). the expected variance for a single point estimator is -1+(6/5)^d, which increases exponentially in the number of dimensions. That's the multiplicative constant to your big O. For a probabilistic example let x_i ~ N(0,1) for i in 1..d and let s = Sum x_i. Try estimating the probability that -0.1 < s < 0.1 by Monte-Carlo sampling. If most of the probability distribution mass is located near a manifold of lower dimensions, as tends to be the case for natural data, your variance will be huge. MCMC, HMC both improve this state of affair by letting you walk or "glide" on the manifold, but you still have to contend with curvature, with multiple modes etc.

yummyfajitas 10y ago
How does MCMC improve this state of affairs? From what I can see, MCMC only worsens things since you can't be sure you are sampling the entire manifold.
- murbard2 10y ago
  That's a good question. If your distribution isn't multimodal but still suffers from having its mass concentrated in one place, and if the variable you're integrating isn't fat-tailed, then MCMC will help you by sticking around the right area once it finds it.
  - yummyfajitas 10y ago
    I don't even think that's true. Consider a distribution in R^2 that is concentrated on [0,1] x [0,100]. If you have an O(1) jump size it'll take time O(100^2) for the MCMC to fully sample the support of this distribution. If you had a jump size of O(100), then you'll be rejecting 99% of your jumps due to the narrowness in the x-direction. This is hardly an uncommon scenario.
    - murbard2 10y ago
      It's easy to design examples that trip MCMC, but they also trip straight Monte Carlo integration even more. You can, of course, construct examples where MCMC will do worse than simple Monte Carlo integration, but these are uncommon. They mostly illustrate the difficulty of picking an appropriate jump size.
      - yummyfajitas 10y ago
        If you directly draw samples from the underlying distribution, you don't have to worry at all about whether the markov chain or other process (e.g. HMC) is fully sampling the distribution. MC has no rejections and always samples the entire distribution. You simply don't need to worry about trajectories not going everywhere they should.
    - deleted 10y ago
      [deleted]
zump 10y ago
What course did you study to get this knowledge?
- AlexCoventry 10y ago
  Any course on the mathematics of Bayesian inference will introduce you to the necessary tools.
- murbard2 10y ago
  AlexCoventry is right, these are "the mathematics of Bayesian inference", to unpack a bit my recommendation is: - Get a strong grip on linear algebra and euclidean spaces. You should be able to have an intuitive feel for the key theorems (e.g. Cayley-Hamilton, the Spectral theorem) and should be comfortable proving them (at least once). The point isn't that you need to check that they're correct (they are), but if you can prove them, it means you've learned a certain amount of prerequisite knowledge and gained enough familiarity with the topic. They aren't just theorems you apply, they make sense and you understand the intuition behind them. - Get the same feel for multivariate calculus. The intuition there is generally easier to acquire than for linear algebra, but you need to be comfortable with the mechanics of it. Learn to prove your results rigorously, but also to quickly derive formulas by treating infinitesimals as variables, like a physicist. - Study integration, measures, distributions and the fundamentals of probability. If the course talks about sigma-algebras, you're in the right place. Finally study Baseyian statistics, Monte-Carlo Integration, Markov-Chain Monte-Carlo, some information theory You don't need that level of rigor and that level of fundamentals to do machine learning. Some linear algebra, some calculus and some probability theory that you pick along the way will generally do. However, I think if you're interested in ML it is worth the effort because it will make most of the math seamless. This is a lot of math to learn, but it's not particularly "advanced" math. The underlying intuitions are relatively concrete and a lot of the procedures are relatively mechanical.
  - zump 10y ago
    Thanks for the wonderful reply. How long do you estimate it took for you to get to the level you are now?

yummyfajitas 10y ago

How does MCMC improve this state of affairs? From what I can see, MCMC only worsens things since you can't be sure you are sampling the entire manifold.

murbard2 10y ago
That's a good question. If your distribution isn't multimodal but still suffers from having its mass concentrated in one place, and if the variable you're integrating isn't fat-tailed, then MCMC will help you by sticking around the right area once it finds it.
- yummyfajitas 10y ago
  I don't even think that's true. Consider a distribution in R^2 that is concentrated on [0,1] x [0,100]. If you have an O(1) jump size it'll take time O(100^2) for the MCMC to fully sample the support of this distribution. If you had a jump size of O(100), then you'll be rejecting 99% of your jumps due to the narrowness in the x-direction. This is hardly an uncommon scenario.
  - murbard2 10y ago
    It's easy to design examples that trip MCMC, but they also trip straight Monte Carlo integration even more. You can, of course, construct examples where MCMC will do worse than simple Monte Carlo integration, but these are uncommon. They mostly illustrate the difficulty of picking an appropriate jump size.
    - yummyfajitas 10y ago
      If you directly draw samples from the underlying distribution, you don't have to worry at all about whether the markov chain or other process (e.g. HMC) is fully sampling the distribution. MC has no rejections and always samples the entire distribution. You simply don't need to worry about trajectories not going everywhere they should.
  - deleted 10y ago
    [deleted]

zump 10y ago

What course did you study to get this knowledge?

AlexCoventry 10y ago
Any course on the mathematics of Bayesian inference will introduce you to the necessary tools.
murbard2 10y ago
AlexCoventry is right, these are "the mathematics of Bayesian inference", to unpack a bit my recommendation is: - Get a strong grip on linear algebra and euclidean spaces. You should be able to have an intuitive feel for the key theorems (e.g. Cayley-Hamilton, the Spectral theorem) and should be comfortable proving them (at least once). The point isn't that you need to check that they're correct (they are), but if you can prove them, it means you've learned a certain amount of prerequisite knowledge and gained enough familiarity with the topic. They aren't just theorems you apply, they make sense and you understand the intuition behind them. - Get the same feel for multivariate calculus. The intuition there is generally easier to acquire than for linear algebra, but you need to be comfortable with the mechanics of it. Learn to prove your results rigorously, but also to quickly derive formulas by treating infinitesimals as variables, like a physicist. - Study integration, measures, distributions and the fundamentals of probability. If the course talks about sigma-algebras, you're in the right place. Finally study Baseyian statistics, Monte-Carlo Integration, Markov-Chain Monte-Carlo, some information theory You don't need that level of rigor and that level of fundamentals to do machine learning. Some linear algebra, some calculus and some probability theory that you pick along the way will generally do. However, I think if you're interested in ML it is worth the effort because it will make most of the math seamless. This is a lot of math to learn, but it's not particularly "advanced" math. The underlying intuitions are relatively concrete and a lot of the procedures are relatively mechanical.
- zump 10y ago
  Thanks for the wonderful reply. How long do you estimate it took for you to get to the level you are now?