Is there an accepted method to determine an approximate dimension for manifold learning

Question

Apologies for the rather vague title, I had difficulty explaining the question without making the title obnoxiously long.

The manifold hypothesis suggests that natural data exists on or close to a lower dimensional manifold. There are plenty of real-world and theoretical examples of cases where this is shown to pan out, and I'm not questioning that.

How, though, does one determine what the dimension of that manifold might be? In PCA, one can specify how much variance to retain and use the eigenspace that accounts for that much variance, but more complex methods non-linear methods don't generally allow for such convenient rules. A naïve approach might be laid out treating the lower dimension as a hyperparameter:

1. Assume I have data $\left( (\mathbf{x_1,y_1}) \ldots (\mathbf{x_n,y_n})) \right)$ with $x_i \in \mathbb{R}^p$. Split data into a standard train/test split
2. Determine some function $f: \mathbb{R}^p \rightarrow \mathbb{R}^d$ that maps the data to a lower dimensional space
3. Perform your favorite predictive algorithm on the new low-dimensional $x^* \in \mathbb{R}^d$ to find a $\hat{y}$
4. Measure $\mathcal{L}(y,\hat{y})$
5. Repeat, dropping d by some prescribed amount
6. Plot $d$ against $\mathcal{L}$ and hope for some insight (maybe a clear kink, or some such).

But that method seems so unsatisfactory. Surely someone has come up with a better way, or has given a reason why there is no better way.

I guess it could also be framed as a regularization problem, but that doesn't avoid the use of a hyperparameter.

This is strongly related to the solution in (What is the manifold assumption in semi-supervised learning?) but I thought it sufficiently different to warrant being its own question.

Answer 1

I am not quite sure if I understood your confusion correctly, if you accept the embedding principle (i.e. the "manifold assumption") the only way you can "decide" your dimension is to construct a projector to low-dimensional manifold. [Levina&Bickel] pointed out that eigenvalue(spectral projector) and projection are two mainstream methods at their time.

The method you pointed out ("dimension expansion") is one way to construct projector (approximately). It is widely used in statistics and biostatistics (say [Sampson&Guttorp]) not only because of its performance but also due to its relatively easy idea and control of error rate for general observations. And not surprisingly, in most applications, favorite predictive algorithm will be a spline regression/thin-plate spline since its performance can be dominated by a Taylor-like term.

Since [Levina&Bickel] is published, it has never overcome this dimension expansion method in practice since MLE is based on conditionality evidence functional (due to Birnbaum's theorem) which most people will argue that it is not reasonable to use when the inference is on the design (the dimension of the observation is usually part of design of the experiment, not observation of the experiment).

I do not know what do you mean by unsatisfactory. If you think there is one way of figuring out the projector exactly(in closed form) for a general manifold(which is the case for most observations embedded in an infinite-dimensional space), that is an unsolved mathematical problem. If you mean the result does not come out in expected successful rate, then you will probably be disappointed in most "machine learning" publications.

Reference

[Sampson&Guttorp]Sampson, Paul D., and Peter Guttorp. "Nonparametric estimation of nonstationary spatial covariance structure." Journal of the American Statistical Association 87.417 (1992): 108-119.

[Perrin&Wendy]Perrin, Olivier, and Wendy Meiring. "Nonstationarity in Rn is second-order stationarity in R2n." Journal of applied probability (2003): 815-820.

[Levina&Bickel]Levina, Elizaveta, and Peter J. Bickel. "Maximum likelihood estimation of intrinsic dimension." Ann Arbor MI 48109 (2004): 1092.