Timezone: »

 
Poster
Learning Nearest Neighbor Graphs from Noisy Distance Samples
Blake Mason · Ardhendu Tripathy · Robert Nowak

Thu Dec 12 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #7
in Algorithms -- Active Learning »

We consider the problem of learning the nearest neighbor graph of a dataset of n items. The metric is unknown, but we can query an oracle to obtain a noisy estimate of the distance between any pair of items. This framework applies to problem domains where one wants to learn people's preferences from responses commonly modeled as noisy distance judgments. In this paper, we propose an active algorithm to find the graph with high probability and analyze its query complexity. In contrast to existing work that forces Euclidean structure, our method is valid for general metrics, assuming only symmetry and the triangle inequality. Furthermore, we demonstrate efficiency of our method empirically and theoretically, needing only O(n\log(n)\Delta^{-2}) queries in favorable settings, where \Delta^{-2} accounts for the effect of noise. Using crowd-sourced data collected for a subset of the UT~Zappos50K dataset, we apply our algorithm to learn which shoes people believe are most similar and show that it beats both an active baseline and ordinal embedding.

Keywords: Active Learning · Algorithms · Algorithms -> Bandit Algorithms; Algorithms -> Online Learning; Algorithms -> Ranking and Preference Learning; Algorithms · Si
[ Paper]  [ Slides] 

Author Information

Blake Mason (University of Wisconsin - Madison)

Blake Mason is Doctoral Student at the University of Wisconsin-Madison studying Electrical and Computer Engineering under the advisement of Professor Robert Nowak. Prior to his graduate studies, he completed his bachelors in electrical engineering at the University of Southern California.

Ardhendu Tripathy (University of Wisconsin - Madison)
Robert Nowak (University of Wisconsion-Madison)

More from the Same Authors