3 ms·
I also like Neal's introduction. I find the discussion about the typical set in the paper linked in the submission more confusing than illuminating. Why wouldn'
by kgwgk 10y ago
I also like Neal's introduction. I find the discussion about the typical set in the paper linked in the submission more confusing than illuminating. Why wouldn't the typical set include the mode of the distribution given that its contribution is higher than for any other region of the same volume. Of course the "outside half" of a hypersphere (say 0.5<R<1) will contribute more than the "inside half" (R<0.5) as N grows but it will also be exponentially larger. It's not clear to me how that defines a neighbourhood (or what does one gain from doing so, it seems the neighbourhood could be defined to be the full hypersphere without any loss).
- soVeryTired 10y agoThe only illustration that I know of a "typical set" is as follows: Take a sample from an N-dimensional standard Gaussian. The square of its Its distance from the origin is x_1^2 + x_2^2 + ... + x_N^2. Each component of this sum has mean 1, so the law of large numbers says for large N, the sum will be about equal to N. On other words, I take a sample from a high-dimensional Gaussian and with very high probability, it will live a distance sqrt(N) from the origin. Which is counterintuitive as you point out, since the most likely value is the 0 vector.
- kgwgk 10y agoYes, the typical point is far from the origin (but unless there is spherical symmetry the only thing those points have in common is being far from the origin). What do you gain by excluding the origin from the typical set? Edit: I'm not sure if your comment contradicts or complements what I wrote. As I said, taking a hypersphere of radius 1 the "inner" hypersphere of radius 0.5 accounts for just 1/2^n of the hypervolume. Would you say that the "outer" shell is a neighbourhood? How is that defined? What is the advantage of doing so instead of using the whole (only marginally bigger) hypersphere?
- soVeryTired 10y agoThere's some information theory that goes over my head, but I think the point is that you can approximate E[f(x)] with an integral over the typical set and expect good results, for non-pathological functions f. Defined in this way, you could of course leave the origin in the typical set. But then there would be another, smaller, typical set that would do the job just as well.
- kgwgk 10y agoThanks. I'm sure the formalism makes sense if properly developed and can lead to useful approximations. It's just that the "conceptual introduction" in that paper makes no sense to me... I understand it's just a simplification, but simplifying too much removes the essence of things. > A grid of length N distributed uniformly in a D-dimensional parameter space requires N^D points and hence N^D evaluations of the integrand. Unless N is incredibly large, however, it is unlikely that any of these points will intersect the narrow typical set, and the exponentially-growing cost of averaging over the grid yields worse and worse approximations to expectations. In fact any point within the hypersphere is as good (or better) as any point in that narrow typical set not including the mode. The problem is not missing the "narrow typical set", is missing the whole hypersphere (because the volume of the hypersphere is small). I fail to see where in that introduction the fact that the typical set excludes the mode of the distribution makes any difference.
- betanalpha 10y agoBecause 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 agoHow 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 agoYes, "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.