Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Quick Search
My eDoc
Session History
Support Wiki
Direct access to
document ID:

          Institute: MPI für biologische Kybernetik     Collection: Biologische Kybernetik     Display Documents

ID: 548486.0, MPI für biologische Kybernetik / Biologische Kybernetik
Efficient Bregman Range Search
Authors:Cayton, L.
Editors:Bengio, Y.; Schuurmans, D.; Lafferty, J.; Williams, C.; Culotta, A.
Date of Publication (YYYY-MM-DD):2010-04
Title of Proceedings:Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009
Start Page:243
End Page:251
Physical Description:9
Audience:Not Specified
Intended Educational Use:No
Abstract / Description: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.
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Holger Fischer
Affiliations:MPI für biologische Kybernetik/Empirical Inference (Dept. Schölkopf)
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.