3 ms·

Because probability has to sum to one. The higher you go in dimension that unit probability is distributed across more and more "boxes" until any single box, i

Because probability has to sum to one. The higher you go in dimension that unit probability is distributed across more and more "boxes" until any single box, including the one around the mode becomes irrelevant. When you are computing expectations you need to focus on those boxes that dominate contributions to the integrals, which are all in the typical set. The typical set is a vaguely defined notation as you cannot define an explicit neighborhood without defining some explicit probability threshold which is often done in information theory of discrete systems. The point here, however, is not to define an explicit neighborhood but rather to motivate that the whichever neighborhood of high-probability mass you would define would not near the mode and instead extend out into a compact neighborhood around the mode. You are welcome to define a neighborhood as the convex hull of the typical set, which would then include the mode (subject to some technical conditions). That wouldn't add any appreciable probability mass, however, but would introduce a whole bunch of space that your statistical algorithm would have to explore at additional computational cost.

kgwgk 10y ago
How would that add a whole bunch of space if the only reason why the probability mass is not appreciable is that the volume is minuscule?
- betanalpha 10y ago
  Yes, "a whole bunch" is not a technical term. :-p You are correct that including the entire convex hull would not itself be absurdly costly. A naive search (say grid search) would still spend most of its time evaluating points at the boundary of the hypersphere, although the additional evaluations near the mode would strictly add more cost. Similarly, any algorithm targeting probability mass (like MCMC) would avoid the interior of the hypersphere altogether. In practice you don't exclude the mode explicitly, you build an algorithm that targets mass and it ends up inherently avoiding the mode. The important conceptual take aways are that, for example, algorithms that try to utilize information just in the neighborhood around the mode (for example so-called MAP estimators) will never be able to accurately quantify a probability distribution and that algorithms that explore neighborhoods of high probability mass will behave in seemingly-counterintuitive ways.
  - kgwgk 10y ago
    > although the additional evaluations near the mode would strictly add more cost. No, one evaluation near the mode is more efficient than one evaluation at the boundary (because the density is higher). I agree that the region immediately around the mode is naturally "avoided" (because the volume is small). But your paper makes it look like we increase efficiency by explicitely avoiding it and concentrating somewhere else. That's what I found confusing.
    - betanalpha 10y ago
      "No, one evaluation near the mode is more efficient than one evaluation at the boundary (because the density is higher)." Incorrect in general. Firstly, one evaluation anywhere does not yield any reasonably accurate estimate of expectations. We'll always need an ensemble of evaluations, in which case the relevant question really is "how should I distribute these evaluations". And for any scalable algorithm none of them will be near the mode. This is often hard to grok because people implicit fall back to the example of a gaussian density where the mode and the Hessian at the mode fully characterize the density which can then be used to compute analytic integrals. But for a general target distribution we do not have any of that structure and instead have to consider general computational strategies. "I agree that the region immediately around the mode is naturally "avoided" (because the volume is small). But your paper makes it look like we increase efficiency by explicitely avoiding it and concentrating somewhere else. That's what I found confusing." In high-dimensions the probability mass of any well-behaved probability distribution concentrates in (or _around_ if you want to acknowledge the fuzziness) the typical set. Hence accurate estimation of expectations requires quantifying the typical set. Any evaluation outside of the typical set is wasted because it offers increasingly negligible contributions to the integrals -- a few additional evaluations may not drive the cost up appreciably but they will still be wasted. So it's not that the only thing that matters is avoiding the mode. Rather what matters is that, contrary to many's intuitions, the neighborhood around the mode does inform expectation values and so exploring that neighborhood is insufficient for estimating expectations. That then motivates the question of what neighborhoods do matter, which is answered by concentration of measure and the existence of the typical set. And in practice, we don't actually do any of this explicitly. Instead we construct algorithms that somehow quantify probability mass (MCMC, VB, etc) and they will implicitly avoiding the mode and end up working with the typical set.
deleted 10y ago
[deleted]

kgwgk 10y ago

How would that add a whole bunch of space if the only reason why the probability mass is not appreciable is that the volume is minuscule?

betanalpha 10y ago
Yes, "a whole bunch" is not a technical term. :-p You are correct that including the entire convex hull would not itself be absurdly costly. A naive search (say grid search) would still spend most of its time evaluating points at the boundary of the hypersphere, although the additional evaluations near the mode would strictly add more cost. Similarly, any algorithm targeting probability mass (like MCMC) would avoid the interior of the hypersphere altogether. In practice you don't exclude the mode explicitly, you build an algorithm that targets mass and it ends up inherently avoiding the mode. The important conceptual take aways are that, for example, algorithms that try to utilize information just in the neighborhood around the mode (for example so-called MAP estimators) will never be able to accurately quantify a probability distribution and that algorithms that explore neighborhoods of high probability mass will behave in seemingly-counterintuitive ways.
- kgwgk 10y ago
  > although the additional evaluations near the mode would strictly add more cost. No, one evaluation near the mode is more efficient than one evaluation at the boundary (because the density is higher). I agree that the region immediately around the mode is naturally "avoided" (because the volume is small). But your paper makes it look like we increase efficiency by explicitely avoiding it and concentrating somewhere else. That's what I found confusing.
  - betanalpha 10y ago
    "No, one evaluation near the mode is more efficient than one evaluation at the boundary (because the density is higher)." Incorrect in general. Firstly, one evaluation anywhere does not yield any reasonably accurate estimate of expectations. We'll always need an ensemble of evaluations, in which case the relevant question really is "how should I distribute these evaluations". And for any scalable algorithm none of them will be near the mode. This is often hard to grok because people implicit fall back to the example of a gaussian density where the mode and the Hessian at the mode fully characterize the density which can then be used to compute analytic integrals. But for a general target distribution we do not have any of that structure and instead have to consider general computational strategies. "I agree that the region immediately around the mode is naturally "avoided" (because the volume is small). But your paper makes it look like we increase efficiency by explicitely avoiding it and concentrating somewhere else. That's what I found confusing." In high-dimensions the probability mass of any well-behaved probability distribution concentrates in (or _around_ if you want to acknowledge the fuzziness) the typical set. Hence accurate estimation of expectations requires quantifying the typical set. Any evaluation outside of the typical set is wasted because it offers increasingly negligible contributions to the integrals -- a few additional evaluations may not drive the cost up appreciably but they will still be wasted. So it's not that the only thing that matters is avoiding the mode. Rather what matters is that, contrary to many's intuitions, the neighborhood around the mode does inform expectation values and so exploring that neighborhood is insufficient for estimating expectations. That then motivates the question of what neighborhoods do matter, which is answered by concentration of measure and the existence of the typical set. And in practice, we don't actually do any of this explicitly. Instead we construct algorithms that somehow quantify probability mass (MCMC, VB, etc) and they will implicitly avoiding the mode and end up working with the typical set.

deleted 10y ago

[deleted]