nips nips2005 nips2005-71 nips2005-71-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nando D. Freitas, Yang Wang, Maryam Mahdaviani, Dustin Lang
Abstract: This paper addresses the issue of numerical computation in machine learning domains based on similarity metrics, such as kernel methods, spectral techniques and Gaussian processes. It presents a general solution strategy based on Krylov subspace iteration and fast N-body learning methods. The experiments show significant gains in computation and storage on datasets arising in image segmentation, object detection and dimensionality reduction. The paper also presents theoretical bounds on the stability of these methods.
[1] A Y Ng, M I Jordan, and Y Weiss. On spectral clustering: Analysis and algorithm. In Advances in Neural Information Processing Systems, pages 849–856, 2001.
[2] D Zhou, J Weston, A Gretton, O Bousquet, and B Scholkopf. Ranking on data manifolds. In Advances on Neural Information Processing Systems, 2004.
[3] X Zhu, J Lafferty, and Z Ghahramani. Semi-supervised learning using Gaussian fields and harmonic functions. In International Conference on Machine Learning, pages 912–919, 2003.
[4] M N Gibbs. Bayesian Gaussian processes for regression and classification. In PhD Thesis, University of Cambridge, 1997.
[5] M Belkin and P Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373–1396, 2003.
[6] G Hinton and S Roweis. Stochastic neighbor embedding. In Advances in Neural Information Processing Systems, pages 833–840, 2002.
[7] A Smola and R Kondor. Kernels and regularization of graphs. In Computational Learning Theory, pages 144–158, 2003. True manifold Sampled data Embedding of SNE Embedding of SNE withIFGT S−curve 4 Running time(seconds) Running time(seconds) 10 SNE SNE with IFGT 3 10 2 10 1 10 Swissroll 4 10 SNE SNE with IFGT 3 10 2 10 1 0 1000 2000 3000 N 4000 5000 10 0 1000 2000 3000 4000 5000 N Figure 4: Examples of embedding on S-curve and Swiss-roll datasets.
[8] M Mahdaviani, N de Freitas, B Fraser, and F Hamze. Fast computational methods for visually guided robots. In IEEE International Conference on Robotics and Automation, 2004.
[9] L Greengard and V Rokhlin. A fast algorithm for particle simulations. Journal of Computational Physics, 73:325–348, 1987.
[10] C Yang, R Duraiswami, N A Gumerov, and L S Davis. Improved fast Gauss transform and efficient kernel density estimation. In International Conference on Computer Vision, Nice, 2003.
[11] A Gray and A Moore. Rapid evaluation of multiple density models. In Artificial Iintelligence and Statistics, 2003.
[12] J Shi and J Malik. Normalized cuts and image segmentation. In IEEE Conference on Computer Vision and Pattern Recognition, pages 731–737, 1997.
[13] R K Beatson, J B Cherrie, and C T Mouat. Fast fitting of radial basis functions: Methods based on preconditioned GMRES iteration. Advances in Computational Mathematics, 11:253–270, 1999.
[14] J W Demmel. Applied Numerical Linear Algebra. SIAM, 1997.
[15] Y Saad. Iterative Methods for Sparse Linear Systems. The PWS Publishing Company, 1996.
[16] L Greengard and J Strain. The fast Gauss transform. SIAM Journal of Scientific Statistical Computing, 12(1):79–94, 1991.
[17] B J C Baxter and G Roussos. A new error estimate of the fast Gauss transform. SIAM Journal of Scientific Computing, 24(1):257–259, 2002.
[18] D Lang, M Klaas, and N de Freitas. Empirical testing of fast kernel density estimation algorithms. Technical Report TR-2005-03, Department of Computer Science, UBC, 2005.
[19] G H Golub and Q Ye. Inexact preconditioned conjugate gradient method with inner-outer iteration. SIAM Journal of Scientific Computing, 21:1305–1320, 1999.
[20] G W Stewart. Backward error bounds for approximate Krylov subspaces. Linear Algebra and Applications, 340:81–86, 2002.
[21] V Simoncini and D B Szyld. Theory of inexact Krylov subspace methods and applications to scientific computing. SIAM Journal on Scientific Computing, 25:454–477, 2003.
[22] D G Lowe. Object recognition from local scale-invariant features. In ICCV, 1999.