机器学习与计算机视觉：最近邻方法全文解析

需积分: 10 14 浏览量更新于2024-07-17 1 收藏 28.43MB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

"《Nearest-Neighbor Methods in Learning and Vision》是关于机器学习与计算机视觉领域中最近邻方法的一本详尽的理论与实践指南，由Gregory Shakhnarovich, Trevor Darrell和Piotr Indyk编辑。本书是神经信息处理系列的一部分，探讨了近似最近邻、最近邻查找以及局部敏感哈希等关键技术。全书包含263页的英文原文，深入浅出地阐述了这些方法的理论基础和实际应用。" 《Nearest-Neighbor Methods in Learning and Vision》一书是机器学习和计算机视觉研究者的重要参考资料，它详细介绍了最近邻方法在这些领域的核心概念和实用技巧。近似最近邻算法是大数据时代下解决高维空间搜索问题的有效手段，它能够在保持一定精度的同时减少计算复杂性，适用于大规模数据集的分类和检索。书中可能涵盖了K-d树、球树、多层感知器等近似搜索结构，以及如何优化这些结构以提高查询效率。最近邻查找是机器学习中常用的一种策略，尤其在分类和回归任务中，它基于实例学习的理念，即新样本最有可能被归类到与其最相似的训练样本所属的类别。书中可能详细讨论了不同的距离度量（如欧氏距离、曼哈顿距离、余弦相似度）以及如何处理非线性可分数据。局部敏感哈希（LSH）是一种用于近似最近邻搜索的随机化技术，它通过将高维数据投影到低维空间来降低计算复杂性。LSH能够高效地检测数据集中的相似项，对于大数据集的相似性搜索和聚类具有重要意义。书中可能会介绍LSH的基本原理、构造方法以及参数选择策略。此外，这本书还可能涉及了其他相关主题，比如集成学习中的最近邻方法、半监督学习中的局部一致性、在计算机视觉中的应用，如图像分类、目标识别、图像检索等。作者们可能会讨论如何结合深度学习和最近邻方法来提升模型性能，以及在处理高维和复杂数据时面临的挑战和解决方案。作为神经信息处理系列的一部分，本书不仅关注理论，也强调实践，提供了丰富的案例研究和实验结果，帮助读者理解和应用这些方法。这使得《Nearest-Neighbor Methods in Learning and Vision》成为学术界和工业界研究人员不可多得的资源，有助于推动机器学习和计算机视觉领域的发展。

资源详情

资源推荐

Introduction 5

Deﬁnition 1.3 (Randomized c-approximate near-neighbor) Given

asetP of points in a d-dimensional space 

,andparametersR>0,

δ>0, construct a data structure which, given any query point q,doesthe

following with probability 1 − δ:ifthereisanR-near neighbor of q in P ,it

reports a cR-near neighbor of q in P .

Deﬁnition 1.4 (Randomized near-neighbor reporting) Given a set

P of points in a d-dimensional space 

,andparametersR>0, δ>0,

construct a data structure which, given any query point q, reports each

R-near neighbor of q in P with probability 1 − δ.

Note that, in the second deﬁnition, the probabilities of reporting diﬀerent

R-near neighbors might not be independent. Also note that, in both prob-

lems, the value R is known during the preprocessing time. Therefore, by

scaling the coordinates of all points, we can assume that R =1.

Among the algorithms discussed in [23], the LSH algorithm is probably

the one that has received most attention in the practical context. Its main

idea is to hash the data points using several hash functions so as to ensure

that, for each function, the probability of collision is much higher for points

which are close to each other than for those which are far apart. Then, one

can determine near neighbors by hashing the query point and retrieving

elements stored in buckets containing that point.

The LSH algorithm can be used to solve either the approximate or the

exact near-neighbor problem. It relies on the existence of LSH functions,

deﬁned in the following manner. Consider a family H of hash functions

mapping 

to some universe U.

Deﬁnition 1.5 (Locality-sensitive hashing) AfamilyH is called

(r, cr, P

)-sensitive if for any p, q ∈

–ifp − q≤R then P

[h(q)=h(p)] ≥ P

–ifp − q≥cR then P

[h(q)=h(p)] ≤ P

In order for a LSH family to be useful, it has to satisfy P

An LSH family can be utilized as follows. Given a family H of hash

functions with parameters (r, cr, P

) as in the above deﬁnition, we

amplify the gap between the “high” probability P

and the “low” probability

by concatenating several functions. In particular, for k and L speciﬁed

later, we choose L functions g

(q)=(h

1,j

(q),...,h

k,j

(q)), where h

t,j

(1 ≤ t ≤

k, 1 ≤ j ≤ L) are chosen independently and uniformly at random from H.

During preprocessing, we store each p ∈ P (input point set) in the bucket

(p), for j =1,...,L. Since the total number of buckets may be large, we

retain only the nonempty buckets by resorting to hashing the values g

(p).

To process a query q, we search through the buckets g

(q),...,g

(q). Two

concrete strategies are possible:

6Introduction

1. Interrupt search after ﬁnding the ﬁrst L



points (including duplicates).

2. Continue search until all points from the buckets are retrieved.

It is shown in [24] that the ﬁrst strategy, with L



=3L, enables solving the

randomized c-approximate near-neighbor problem, with parameters R and

δ,forsomeconstantδ<1. To obtain that guarantee, it suﬃces to set L to

Θ(n

), where ρ =

ln 1/P

. Note that this implies that the algorithm runs in

time proportional to n

, which is sublinear in n if P

On the other hand, in practice, the second strategy appears to be more

popular, presumably since it avoids the need to specify the additional

parameter L



. Also, there is no need to specify c, since the algorithm can

solve the exact near neighbor problem, as described in the remainder of this

paragraph. The analysis in [24] can be used to show that the second strategy

enables solving the randomized exact near-neighbor reporting problem for a

given parameter R.Thevalueofδ depends on the choice of the parameters k

and L; alternatively, for each δ one can provide parameters k and L so that

the error probability is smaller than δ. The query time is also dependent

on k and L: it could be as high as Θ(n) in the worst case, but for many

data sets a proper choice of parameters results in a sublinear query time.

See more details in chapter 3.

The quality of LSH functions is characterized by the parameter ρ.Itwas

shown in [24, 19] that if the distance is measured according to the l

norm,

then there exists a (R, cR, P

)-sensitive family of functions with ρ =1/c.

In chapter 3 another family of functions is described which works if the

distances are measured according to the l

norm for s ∈ (0, 2].

1.2 Nearest-Neighbor Methods in Learning and Vision

In the context of machine learning, nearest-neighbor methods are applied to

supervised problems. Suppose one is given a reference set –a set of examples

for which the target concept (a class label, function value, etc.) is known,

and a query, for which such a value is unknown and is to be recovered. The

nearest-neighbor approach consists of ﬁnding one or more examples most

similar to the query, and using the labels of those examples to produce the

desired estimate of the query’s label.

This broad description leaves two important questions:

1. What are the criteria of similarity? The answer depends on the under-

lying distance measure as well as on the selection criteria, e.g., the k ex-

amples closest to the query for a ﬁxed k, or the examples closer than a

ﬁxed threshold r. The choices of these criteria are known to have a very

signiﬁcant inﬂuence on the performance on the algorithm.

2. How are the labels from the neighbors to be combined? The simplest

way is to take the majority vote, in classiﬁcation setup, or the average,

Introduction 7

in regression setup. However, more sophisticated methods, such as locally

weighted regression, have been shown to produce sometimes dramatically

better results.

The following fundamental property of nearest-neighbor classiﬁcation

has been shown by Cover and Hart in [15]. Let R(n) be the expected

probability of error of the M-category nearest-neighbor classiﬁer for a

training set of n examples. Then the limit R = lim

n→∞

R(n) is bounded

by R

∗

≤ R ≤ R

∗

(2 − MR

∗

/(M − 1)), where R

∗

stands for the Bayes risk–

the probability of error of the optimal classiﬁer given the distribution of the

data. A similar result can be shown for the nearest-neighbor regression [13].

Unfortunately, these asymptotic results do not necessarily translate into

similar bounds in practice when training sets of ﬁnite size are used. As

has been shown by Cover in [14], the rate of convergence to this limit may

be arbitrarily slow. A signiﬁcant body of work has been devoted to analy-

sis of nearest-neighbor performance on samples of ﬁnite size. Although no

“distribution-free” bounds have been found, it is possible to characterize the

ﬁnite sample risk of the nearest-neighbor classiﬁer based on various proper-

ties of the input space and the data distribution (see [18, 35, 37] for some

interesting results). Moreover, despite the lack of theoretical guarantees, it

has often been observed that the nearest-neighbor classiﬁers perform very

well in practice, and achieve accuracy equivalent to or even better than that

of signiﬁcantly more complicated methods; see, e.g., the extensive compar-

ative study reported in [16].

Similar success has been seen in the application of nearest-neighbor meth-

ods to a variety of vision tasks, such as shape matching [22, 7] and object

recognition [33, 30, 28]. However, in computer vision the limitations of some

nearest-neighbor search methods have particularly high impact, since the

data here is typically high-dimensional, and in many cases the databases

required to suﬃciently represent the visual phenomena are large. On the

other hand, appropriate similarity measures in vision applications are often

more expensive than the Euclidean distance. Furthermore, these measures

may not even be metrics. All this poses a challenge for a practitioner inter-

ested in using an example-based technique in a computer vision problem.

Possible solutions include randomized approximate algorithms, embedding

techniques, and machine learning algorithms for adapting the data struc-

tures for the properties of the data in the given domain. The book describes

some of the recent advances in these directions.

8Introduction

1.3 Contributions to this book

Theory

The book opens with two contributions from computational geometry.

Chapter 2, by Clarkson, focuses on the formulation of exact nearest-neighbor

search, and studies this problem in metric spaces. In particular, it investi-

gates the various dimensionality properties that make the problem tractable

in practice, and presents theoretical results. Chapter 3, by Andoni, Datar,

Immorlica, Indyk, and Mirrokni, is devoted to a randomized algorithm that

allows approximate as well as exact similarity search in very high dimensions

in time sublinear in the size of the database. The algorithm is an extension

of LSH, described in 1.1.3, to a family of distance metrics beyond the l

norm.

Learning

The unifying theme of the three chapters in the second part of the book

is exploring the ways to make the nearest-neighbor approach practicable in

machine learning application where the dimensionality of the data, and

the size of the data sets, make the naive methods for nearest-neighbor

search prohibitively expensive. In chapter 4, Liu, Moore, and Gray notice

that in nearest-neighbor classiﬁcation, what matters for the decision is the

distribution of labels of the query’s neighbors, rather than the neighbors

themselves. They use this observation to develop new algorithms, using

previously introduced balltree data structures, that aﬀord a signiﬁcant

speedup while maintaining the accuracy of the exact k-nearest-neighbor

classiﬁcation.

Chapter 5, by Vijayakumar, D’Souza, and Schaal, is devoted to methods

that build a local model of the target function in the vicinity of the query by

ﬁnding its neighbors in the reference set. The chapter proposes an approach

that extends such local learning methods to very high-dimensional spaces by

exploiting the low intrinsic dimensionality within a neighborhood. Another

contribution is a new Bayesian regression algorithm. The proposed frame-

work has been shown to be fast and accurate in a number of applications,

including real-time motor control tasks for robots.

Chapter 6, by Athitsos, Alon, Sclaroﬀ, and Kollios addresses the issue that

arises in the context of many applications of nearest-neighbor methods in

learning, be they for classiﬁcation, regression, or database retrieval. When

computing the distance of interest is expensive, a signiﬁcant reduction in

search time may be gained if a cheap way exists to evaluate the relative dis-

tances from the query and eliminate the majority of the reference examples

from contention, thus requiring the distance to be explicitly computed only

on a small subset of the database. The approach proposed in this chapter

Introduction 9

is to learn an embedding of the original distance into a Euclidean space, in

which the ranking with respect to the Manhattan metric reﬂects the ranking

under the original distance. Connecting this chapter to the following ones,

the approach is evaluated on two computer vision tasks: estimating the

articulated pose of human hands and classifying sign language utterances.

Vision

The chapters in the third part of the book describe successful applications

of LSH to vision tasks. Moreover, as some of the chapters show, the basic

LSH framework may be adapted to better ﬁt the properties of the data

space and the task at hand.

In chapter 7, Shakhnarovich, Viola, and Darrell deal with a regression

task: estimating articulated body pose from images of people. The basic

idea here is to learn, using pairs of images with known poses, hash func-

tions sensitive to the distance in the pose space. The resulting method,

parameter-sensitive hashing, allows very fast example-based estimation of

pose using a very large set of labeled examples. Chapter 8, by Grauman

and Darrell, is concerned with database retrieval scenarios where the dis-

tance is known but very expensive to compute: the earth mover’s distance

(EMD) between contours. The authors propose a technique, based on mul-

tiresolution histograms, that embeds the contours into a Euclidean space

of very high dimensions, and replaces EMD with the Manhattan distances

between sparse points in that space, thus allowing application of very fast

approximate search algorithms such as LSH. The experiments on data sets

of handwritten digits and human body contours show that with this embed-

ding, neighbor-based methods remain very accurate while gaining dramatic

speedup.

In contrast to the previous chapters, the task of interest in chapter 9,

by Shimshoni, Georgescu, and Meer, is an unsupervised one: clustering.

Speciﬁcally, the authors show how LSH can be used to reduce the complex-

ity of mean-shift clustering, and apply the resulting algorithm to the tasks

of visual texture classiﬁcation and image segmentation. They also propose

signiﬁcant modiﬁcations in the algorithms for constructing the data struc-

ture used to index the examples: the partitions in the hash tables are data

driven.

Finally, in chapter 10 Frome and Malik present an application of LSH

to another vision task: automatic classiﬁcation of vehicles from their three-

dimensional range scans. The approach proposed by the authors relies on

LSH to perform fast search in a set of reference objects represented using

shape context–a representation that has been shown to be useful but also

to make distance calculations very costly. This chapter, too, presents a

modiﬁcation of the basic LSH algorithm: Associative LSH. In this algorithm,

the results returned by LSH for a query are further reﬁned by local search,

剩余262页未读，继续阅读

chantsky

粉丝: 4
资源: 3

机器学习与计算机视觉：最近邻方法全文解析

KK---Nearest-Neighbor.zip_K.

2006Practical Construction of k-Nearest Neighbor Graphs in Metric Spaces.pdf

Metric Learning A Survey

e2lsh.rar_ E2LSH_ E2LSH-0.1_E2L_Red on Red_lsh

numexpr-2.8.3-cp38-cp38-win_amd64.whl

ujson-5.3.0-cp311-cp311-win_amd64.whl

基于MATLAB车牌识别程序技术实现面板GUI.zip

RJFireWall-maste赛资源

msgpack-1.0.4-cp39-cp39-win_amd64.whl

基于 YOLOv11 的混凝土缺陷检测系统（包含详细的完整的程序和数据）

用 Python 实现简单网页爬虫并保存为CSV教程.txt

chompack-2.3.3-cp35-cp35m-win_amd64.whl

sparsesvd-0.2.2-cp38-cp38-win_amd64.whl

pendulum-2.0.5-cp35-cp35m-win_amd64.whl

RH358: 系统服务自动化与网络配置管理

led-tcp-maste资源

Qt直接打印日志，不使用第三方库

基于YOLOv11的肉鸡健康状态检测系统（包含详细的完整的程序和数据）

最新资源