Manifold-adaptive Dimension Estimation

Manifold-adaptive Dimension Estimation. Farahmand, A., Szepesvári, C., & Audibert, J. In ICML, pages 265–272, 2007.

Manifold-adaptive Dimension Estimation [pdf]

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.

@inproceedings{farahmand2007,
	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.},
	acceptrate = {29\%},
	author = {Farahmand, A.m. and Szepesv{\'a}ri, Cs. and Audibert, J.-Y.},
	bibsource = {DBLP, http://dblp.uni-trier.de},
	booktitle = {ICML},
	ee = {http://doi.acm.org/10.1145/1273496.1273530},
	keywords = {unsupervised learning, dimension estimation, theory, manifold learning},
	pages = {265--272},
	title = {Manifold-adaptive Dimension Estimation},
	url_paper = {dimicml.pdf},
	year = {2007}}

Downloads: 0