Neighbor search with global geometry: a minimax message passing algorithm
Neighbor search with global geometry: a minimax message passing algorithm
复制标题
DOI：
10.1145/1273496.1273547
复制
发表时间：
2007-06
期刊：
影响因子：
--
通讯作者：
Kye-Hyeon Kim;Seungjin Choi
中科院分区：
文献类型：
--
作者：
Kye-Hyeon Kim;Seungjin Choi
邻域搜索是机器学习中的一项基本任务，特别是在分类和检索中。高效的最近邻搜索方法已经得到了广泛的研究，其重点是数据结构，但大多数都没有考虑数据集的底层全局几何。最近的基于图的半监督学习方法捕捉全局几何，但遭受可扩展性和参数调整问题。在本文中，我们提出了一个（最近）邻居搜索方法，其中底层的全球几何被纳入和参数调整是不需要的。为此，我们引入了确定性的散步作为一个确定性的马尔可夫随机游动，导致我们使用的极大极小距离作为一个全球性的相异性措施。然后，我们开发了一个有效的极大极小距离计算的消息传递算法，它在时间和空间上都是线性的。实验结果表明，该方法在图像检索和半监督学习中具有良好的性能。
Neighbor search is a fundamental task in machine learning, especially in classification and retrieval. Efficient nearest neighbor search methods have been widely studied, with their emphasis on data structures but most of them did not consider the underlying global geometry of a data set. Recent graph-based semi-supervised learning methods capture the global geometry, but suffer from scalability and parameter tuning problems. In this paper we present a (nearest) neighbor search method where the underlying global geometry is incorporated and the parameter tuning is not required. To this end, we introduce deterministic walks as a deterministic counterpart of Markov random walks, leading us to use the minimax distance as a global dissimilarity measure. Then we develop a message passing algorithm for efficient minimax distance calculation, which scales linearly in both time and space. Empirical study reveals the useful behavior of the method in image retrieval and semi-supervised learning.