Estimating manifold dimension by inversion error

ABSTRACT

Video and image datasets can often be described by a small number of parameters, even though each image usually consists of hundreds or thousands of pixels. This observation is often exploited in computer vision and pattern recognition by the application of dimensionality reduction techniques. In particular, there has been recent interest in the application of a class of nonlinear dimensionality reduction algorithms which assume that an image dataset has been sampled from a manifold.From this assumption, it follows that estimating the dimension of the manifold is the first step in analyzing an image dataset. Typically, this estimate is obtained either by using a priori knowledge, or by applying one of the various statistical and geometrical methods available. Once an estimate is obtained, it is used as a parameter for the nonlinear dimensionality reduction algorithm.In this paper, we consider reversing this approach. Instead of estimating the dimension of the manifold in order to obtain a low dimensional representation, we consider producing low dimensional representations in order to estimate of the dimensionality of the manifold. By varying the dimensionality parameter, we obtain different low dimensional representations of the original dataset. The dimension of the best representation should then correspond to the actual dimension of the manifold.In order to determine the best representation, we propose a metric based on inversion. In particular, we propose that a good representation should be invertible, in that we should be able to reverse the reduction algorithm's transformation to obtain the original dataset. By coupling this metric with any reduction algorithm, we can estimate the dimensionality of an image manifold. We apply our method in the context of locally linear embedding (LLE) and Isomap to six frequently used examples and two image datasets.

REFERENCES

• 1: D. Banks and R. Olszewski. Estimating local dimensionality. In Proceedings of the Statistical Computing Section of the American Statistical Assocation. ASA, 1997.
• 2: Mikhail Belkin , Partha Niyogi, Laplacian Eigenmaps for dimensionality reduction and data representation, Neural Computation, v.15 n.6, p.1373-1396, June 2003 [doi>10.1162/089976603321780317]
• 3: D. Beymer and T. Poggio. Image representation for visual learning. Science, 272:1905--1909, 1996.
• 4: M. Brand. Charting a manifold. In Advances in Neural Information Processing Systems, volume 15, pages 961--968. MIT Press, 2003.
• 5: J. Bruske , G. Sommer, Intrinsic Dimensionality Estimation With Optimally Topology Preserving Maps, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.5, p.572-575, May 1998 [doi>10.1109/34.682189]
• 6: Francesco Camastra , Alessandro Vinciarelli, Estimating the Intrinsic Dimension of Data with a Fractal-Based Method, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.10, p.1404-1407, October 2002 [doi>10.1109/TPAMI.2002.1039212]
• 7: D. Donoho and C. Grimes. Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data. Proceedings of the National Academy of Science, 100:5591--5596, 2003.
• 8: K. Fukunaga and D. Olsen. An algorithm for finding intrinsic dimensionality of data. IEEE Transactions on Computers, 20(2):176--183, 1971.
• 9: J. J. Hull, A Database for Handwritten Text Recognition Research, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.5, p.550-554, May 1994 [doi>10.1109/34.291440]
• 10: D. Hundley and M. Kirby. Estimation of topological dimension. In SIAM International Conference on Data Mining, pages 194--202, 2003.
• 11: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 12: B. Kegl. Intrinsic dimension estimation using packing numbers. In Advances in Neural Information Processing Systems, volume 15. MIT Press, 2002.
• 13: M. Kirby , L. Sirovich, Application of the Karhunen-Loeve Procedure for the Characterization of Human Faces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.1, p.103-108, January 1990 [doi>10.1109/34.41390]
• 14: H. Lu, Y. Fainman, and R. Hecht-Nielsen. Image manifolds. In Applications of Artificial Neural Networks in Image Processing III, Proceedings of SPIE, volume 3307, pages 52--63, 1998.
• 15: K. Pettis, T. Bailey, A. Jain, and R. Dubes. An intrinsic dimensionality estimator from near-neighbor information. IEEE Transacations on Pattern Analysis and Machine Intelligence, 1:25--37, 1979.
• 16: Robert Pless, Image Spaces and Video Trajectories: Using Isomap to Explore Video Sequences, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.1433, October 13-16, 2003
• 17: M. Polito and P. Perona. Grouping and dimensionality reduction by locally linear embedding. In Advances in Neural Information Processing Systems, volume 14. MIT Press, 2002.
• 18: S. Roweis. http://www.cs.toronto.edu/~roweis/data.html.
• 19: S. Roweis and L. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323--2326, 2000.
• 20: Lawrence K. Saul , Sam T. Roweis, Think globally, fit locally: unsupervised learning of low dimensional manifolds, The Journal of Machine Learning Research, 4, p.119-155, 12/1/2003 [doi>10.1162/153244304322972667]
• 21: Bernhard Schölkopf , Alexander Smola , Klaus-Robert Müller, Nonlinear component analysis as a kernel eigenvalue problem, Neural Computation, v.10 n.5, p.1299-1319, July 1, 1998 [doi>10.1162/089976698300017467]
• 22: H. Seung and D. Lee. The manifold ways of perception. Science, 290:2268--2269, 2000.
• 23: A. Smola and B. Scholkopf. A tutorial on support vector regression. Technical Report NC2-TR-1998-030, NeuroCOLT2, 1998.
• 24: J. Tenenbaum, V. de Silva, and J. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319--2323, 2000.
• 25: M. Turk and A. Pentland. Eigenfaces for recognition. Journal of Cognitive Neuroscience, 3(1):71--86, 1991.
• 26: Peter J. Verveer , Robert P. W. Duin, An Evaluation of Intrinsic Dimensionality Estimators, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.1, p.81-86, January 1995 [doi>10.1109/34.368147]
• 27: K. Weinberger. http://www.seas.upenn.edu/~kilianw/sde/datasets.htm
• 28: K. Weinberger and L. Saul. Unsupervised learning of image manifolds by semidefinite programming. In Proceeding of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2004.