Manifold-adaptive dimension estimation

ABSTRACT

Intuitively, learning should be easier when the data points lie on a low-dimensional submanifold of the input space. Recently there has been a growing interest in algorithms that aim to exploit such geometrical properties of the data. Oftentimes these algorithms require estimating the dimension of the manifold first. In this paper we propose an algorithm for dimension estimation and study its finite-sample behaviour. The algorithm estimates the dimension locally around the data points using nearest neighbor techniques and then combines these local estimates. We show that the rate of convergence of the resulting estimate is independent of the dimension of the input space and hence the algorithm is "manifold-adaptive". Thus, when the manifold supporting the data is low dimensional, the algorithm can be exponentially more efficient than its counterparts that are not exploiting this property. Our computer experiments confirm the obtained theoretical results.

REFERENCES

• 1: Azuma, K. (1967). Weighted sums of certain dependent random variables. Tohoku Math. J., 19(2):357--367.
• 2: Gine, E. and Koltchinskii, V. (2007). Empirical graph Laplacian approximation of Laplace-Beltrami operators: Large sample results. In Proc. of the 4th Int. Conf. on High Dimensional Probability. to appear.
• 3: Grassberger, P. and Procaccia, I. (1983). Measuring the strangeness of strange attractors. Physica D, 9:189--208.
• 4: Hein, M. (2006). Uniform convergence of adaptive graph-based regularization. In COLT-2006, pages 50--64.
• 5: Matthias Hein , Jean-Yves Audibert, Intrinsic dimensionality estimation of submanifolds in R^d, Proceedings of the 22nd international conference on Machine learning, p.289-296, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102388]
• 6: Hein, M., Audibert, J.-Y., and von Luxburg, U. (2006). From graphs to manifolds - weak and strong pointwise consistency of graph Laplacians. submitted.
• 7: Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13--30.
• 8: Kegl, B. (2002). Intrinsic dimension estimation using packing numbers. In NIPS-15, pages 681--688.
• 9: Levina, E. and Bickel, P. J. (2005). Maximum likelihood estimation of intrinsic dimension. In NIPS-17, pages 777--784.
• 10: McDiarmid, C. (1989). On the method of bounded differences. Surveys in Combinatorics, pages 148--188.
• 11: Pettis, K. W., Bailey, T. A., Jain, A. K., and Dubes, R. C. (1979). An intrinsic dimensionality estimator from near-neighbor information. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1:25--37.
• 12: Stone, C. (1977). Consistent nonparametric regression. Annals of Statistics, 5(4):595--620.
• 13: Tenenbaum, J. B., de Silva, V., and Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290: 2319--2323.