Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (Hardcover)

Gregory Shakhnarovich, Trevor Darrell, Piotr Indyk

  • 出版商: MIT
  • 出版日期: 2006-03-24
  • 售價: $1,350
  • 語言: 英文
  • 頁數: 280
  • 裝訂: Hardcover
  • ISBN: 026219547X
  • ISBN-13: 9780262195478
  • 相關分類: Machine Learning
  • 立即出貨(限量) (庫存=3)

買這商品的人也買了...

商品描述

Description

Regression and classification methods based on similarity of the input to stored examples have not been widely used in applications involving very large sets of high-dimensional data. Recent advances in computational geometry and machine learning, however, may alleviate the problems in using these methods on large data sets. This volume presents theoretical and practical discussions of nearest-neighbor (NN) methods in machine learning and examines computer vision as an application domain in which the benefit of these advanced methods is often dramatic. It brings together contributions from researchers in theory of computation, machine learning, and computer vision with the goals of bridging the gaps between disciplines and presenting state-of-the-art methods for emerging applications.

The contributors focus on the importance of designing algorithms for NN search, and for the related classification, regression, and retrieval tasks, that remain efficient even as the number of points or the dimensionality of the data grows very large. The book begins with two theoretical chapters on computational geometry and then explores ways to make the NN approach practicable in machine learning applications where the dimensionality of the data and the size of the data sets make the naïve methods for NN search prohibitively expensive. The final chapters describe successful applications of an NN algorithm, locality-sensitive hashing (LSH), to vision tasks.

Gregory Shakhnarovich is a Postdoctoral Research Associate in the Computer Science Department at Brown University

Trevor Darrell is Associate Professor and Head of the Vision Interface Group in the Computer Science and Artificial Intelligence Lab (CSAIL) at MIT.

Piotr Indyk is Associate Professor in the Theory of Computation Group in the Computer Science and Artificial Intelligence Lab (CSAIL) at MIT.

 

Table of Contents

Series Foreword
  
Preface
  
1 Introduction
Gregory Shakhnarovich, Piotr Indyk and Trevor Darrell
   
I Theory 13
 
2 Nearest-Neighbor Searching and Metric Space Dimensions
Kenneth L. Clarkson 15
 
3 Locality-Sensitive Hashing Using Stable Distributions
Aleksandr Andoni, Mayur Datar, Nicole Immorlica, Piotr Indyk and Vahab Mirrokni 61
 
II Applications: Learning 73
 
4 New Algorithms for Efficient High-Dimensional Nonparametric Classification
Ting Liu, Andrew W. Moore and Alexander Gray 75
 
5 Approximate Nearest Neighbor Regression in Very High Dimensions
Sethu Vijayakumar, Aaron D'Souza and Stefan Schaal 103
 
6 Learning Embeddings for Fast Approximate Nearest Neighbor Retrieval
Vassilis Athitsos, Jonathan Alon, Stan Sclaroff and George Kollios 143
 
III Applications: Vision 163
 
7 Parameter-Sensitive Hashing for Fast Pose Estimation
Gregory Shakhnarovich, Paul Viola and Trevor Darrell 165
 
8 Contour Matching Using Approximate Earth Mover's Distance
Kristen Grauman and Trevor Darrell 181
 
9 Adaptive Mean Shift Based Clustering in High Dimensions
Ilan Shimshoni, Bogdan Georgescu and Peter Meer 203
 
10 Object Recognition using Locality Sensitive Hashing of Shape Contexts
Andrea Frome and Jitendra Malik 221 
 
Contributors
   
Index
 

商品描述(中文翻譯)

描述

基於輸入與存儲範例的相似性的回歸和分類方法在涉及非常大的高維數據集的應用中並不常用。然而,最近在計算幾何和機器學習方面的進展可能會緩解在大數據集上使用這些方法時的問題。本書介紹了機器學習中最近鄰居(NN)方法的理論和實踐討論,並將計算機視覺作為一個應用領域,其中這些先進方法的好處通常是顯著的。它匯集了計算理論、機器學習和計算機視覺領域的研究人員的貢獻,旨在彌合學科之間的差距,並提供新興應用的最新方法。

貢獻者們專注於設計NN搜索算法的重要性,以及相關的分類、回歸和檢索任務,即使數據點的數量或數據的維度變得非常大,這些算法仍然保持高效。本書首先介紹了兩個關於計算幾何的理論章節,然後探討了如何使NN方法在機器學習應用中變得實用,其中數據的維度和數據集的大小使得對NN搜索的天真方法變得代價高昂。最後幾章描述了一種NN算法——局部敏感哈希(LSH)在視覺任務中的成功應用。

Gregory Shakhnarovich是布朗大學計算機科學系的博士後研究員。

Trevor Darrell是麻省理工學院計算機科學和人工智能實驗室(CSAIL)視覺界面組的副教授和負責人。

Piotr Indyk是麻省理工學院計算機科學和人工智能實驗室(CSAIL)計算理論組的副教授。

目錄

系列前言
前言
1. 簡介
Gregory Shakhnarovich,Piotr Indyk和Trevor Darrell

第一部分 理論
2. 最近鄰居搜索和度量空間維度
Kenneth L. Clarkson

3. 使用穩定分佈的局部敏感哈希
Aleksandr Andoni,Mayur Datar,Nicole Immorlica,Piotr Indyk和Vahab Mirrokni

第二部分 應用:學習
4. 高維非參數分類的新算法
Ting Liu,Andrew W. Moore和Alexander Gray

5. 非常高維度的近似最近鄰居回歸
Sethu Vijayakumar,Aaron D'Souza和Stefan Schaal

6. 學習嵌入以實現快速應用