nips nips2009 nips2009-74 nips2009-74-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Lawrence Cayton
Abstract: We develop an algorithm for efficient range search when the notion of dissimilarity is given by a Bregman divergence. The range search task is to return all points in a potentially large database that are within some specified distance of a query. It arises in many learning algorithms such as locally-weighted regression, kernel density estimation, neighborhood graph-based algorithms, and in tasks like outlier detection and information retrieval. In metric spaces, efficient range search-like algorithms based on spatial data structures have been deployed on a variety of statistical tasks. Here we describe an algorithm for range search for an arbitrary Bregman divergence. This broad class of dissimilarity measures includes the relative entropy, Mahalanobis distance, Itakura-Saito divergence, and a variety of matrix divergences. Metric methods cannot be directly applied since Bregman divergences do not in general satisfy the triangle inequality. We derive geometric properties of Bregman divergences that yield an efficient algorithm for range search based on a recently proposed space decomposition for Bregman divergences. 1
[1] Marcel Ackermann and Johannes Bl¨ mer. Coresets and approximate clustering for bregman o divergences. In Proceedings of the Symposium on Discrete Algorithms (SODA), 2009.
[2] Pankaj K. Agarwal and Jeff Erickson. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry, pages 1–56. American Mathematical Society, 1999.
[3] Katy Azoury and Manfred Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine Learning, 43(3):211–246, 2001. 8
[4] Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, and Joydeep Ghosh. Clustering with bregman divergences. Journal of Machine Learning Research, Oct 2005.
[5] David Blei and John Lafferty. A correlated topic model of Science. Annals of Applied Statistics, 1(1):17–35, 2007.
[6] David Blei, Andrew Ng, and Michael Jordan. Latent dirichlet allocation. Journal of Machine Learning Research, 2003.
[7] L.M. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7(3):200–217, 1967.
[8] Lawrence Cayton. Fast nearest neighbor retrieval for bregman divergences. In Proceedings of the International Conference on Machine Learning, 2008.
[9] Lawrence Cayton. Bregman Proximity Search. PhD thesis, University of California, San Diego, 2009.
[10] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Symposium on Computational Geometry, 2004.
[11] Alexander Gray and Andrew Moore. ‘N-body’ problems in statistical learning. In Advances in Neural Information Processing Systems, 2000.
[12] Alexander Gray and Andrew Moore. Nonparametric density estimation: Toward computational tractability. In SIAM International Conference on Data Mining, 2003.
[13] Sudipto Guha, Piotr Indyk, and Andrew McGregor. Sketching information divergences. In Conference on Learning Theory, 2007.
[14] Michael P. Holmes, Alexander Gray, and Charles Lee Isbell. QUIC-SVD: Fast SVD using cosine trees. In Advances in Neural Information Processing Systems 21, 2008.
[15] Dongryeol Lee and Alexander Gray. Fast high-dimensional kernel summations using the monte carlo multipole method. In Advances in Neural Information Processing Systems 21, 2008.
[16] D. D. Lewis, Y. Yang, T. Rose, and F. Li. RCV1: A new benchmark collection for text categorization research. Journal of Machine Learning Research, 2004.
[17] Ting Liu, Andrew Moore, and Alexander Gray. New algorithms for efficient high-dimensional nonparametric classification. Journal of Machine Learning Research, 2006.
[18] Ting Liu, Andrew Moore, Alexander Gray, and Ke Yang. An investigation of practical approximate neighbor algorithms. In Advances in Neural Information Processing Systems, 2004.
[19] Frank Nielsen, Jean-Daniel Boissonnat, and Richard Nock. On bregman voronoi diagrams. In Symposium on Discrete Algorithms, pages 746–755, 2007.
[20] Frank Nielsen, Paolo Piro, and Michel Barlaud. Bregman vantage point trees for efficient nearest neighbor queries. In IEEE International Conference on Multimedia & Expo, 2009.
[21] Frank Nielsen, Paolo Piro, and Michel Barlaud. Tailored bregman ball trees for effective nearest neighbors. In European Workshop on Computational Geometry, 2009.
[22] Fernando Pereira, Naftali Tishby, and Lillian Lee. Distributional clustering of English words. In 31st Annual Meeting of the ACL, pages 183–190, 1993.
[23] Jan Puzicha, Joachim Buhmann, Yossi Rubner, and Carlo Tomasi. Empirical evaluation of dissimilarity measures for color and texture. In Proceedings of the Internation Conference on Computer Vision (ICCV), 1999.
[24] N. Rasiwasia, P. Moreno, and N. Vasconcelos. Bridging the gap: query by semantic example. IEEE Transactions on Multimedia, 2007.
[25] Yirong Shen, Andrew Ng, and Matthias Seeger. Fast gaussian process regression using kdtrees. In Advances in Neural Information Processing Systems, 2006.
[26] Zhenjie Zhang, Beng Chin Ooi, Srinivasan Parthasarathy, and Anthony Tung. Similarity search on bregman divergence: towards non-metric indexing. In International Conference on Very Large Databases (VLDB), 2009. 9