ICML 2007 - The 24th Annual International Conference on Machine Learning

Learning for Efficient Retrieval of Structured Data with Noisy Queries

author: Charles Parker, Oregon State University

Description

Increasingly large collections of structured data necessitate the development of efficient, noise-tolerant retrieval tools. In this work, we consider this issue and describe an approach to learn a similarity function that is not only accurate, but that also increases the effectiveness of retrieval data structures. We present an algorithm that uses functional gradient boosting to maximize both retrieval accuracy and the retrieval efficiency of vantage point trees. We demonstrate the effectiveness of our approach on two datasets, including a moderately sized real-world dataset of folk music.

You might be experiencing some problems with Your Video player.

*Slides*
0:00	Learning for Efficient Retrieval of Structured Data with Noisy Queries
0:00	Structured Data Retrieval: The Problem
0:58	Sequence Alignment: Introduction
1:57	Obligatory Overview Slide
2:35	Sequence Alignment: Basics
3:07	Sequence Alignment: Alignment Costs
3:42	The Dynamic Time Warping (Smith-Waterman) Algorithm
4:19	Gradient Boosting: Learning Distance Functions
5:51	Metric Access Methods: Overview
6:38	The Triangular Inequality
8:20	The Triangular Inequality: Concave Function Application
8:44	Vantage Point Trees: Overview
9:36	Vantage Point Trees: Demonstration - 1
9:45	Vantage Point Trees: Demonstration - 2
9:49	Vantage Point Trees: Demonstration - 3
9:55	Vantage Point Trees: Demonstration - 4
10:02	Vantage Point Trees: Demonstration - 5
10:06	Vantage Point Trees: Demonstration - 6
10:09	Vantage Point Trees: Demonstration - 7
10:13	Vantage Point Trees: Searching for Nearest Neighbors Within ‘t’ - 1
10:24	Vantage Point Trees: Searching for Nearest Neighbors Within ‘t’ - 2
10:35	Vantage Point Trees: Searching for Nearest Neighbors Within ‘t’ - 3
10:54	Vantage Point Trees: Searching for Nearest Neighbors Within ‘t’ - 4
11:04	Vantage Point Trees: Searching for Nearest Neighbors Within ‘t’ - 5
11:26	Vantage Point Trees: Searching for Nearest Neighbors Within ‘t’ - 6
11:40	Vantage Point Trees: Searching for Nearest Neighbors Within ‘t’ - 7
11:52	Vantage Point Trees: Searching for Nearest Neighbors Within ‘t’ - 8
12:15	Vantage Point Trees: Searching for Nearest Neighbors Within ‘t’ - 9
12:25	Vantage Point Trees: Optimizing
14:23	Boosting for Efficiency: Summary
14:56	Boosting for Efficiency: Vp-Tree-Based Loss Function
16:09	Boosting for Efficiency: Gradient Expression
16:51	Synthetic Domain: Summary
17:27	Query-by-Humming: Summary
17:52	Query-by-Humming: Basic Techniques for Query Processing
18:24	Application to Query-by-Humming: Our Data Set
18:54	Results: Experimental Setup
20:29	Results: Query-by-Humming Domain
21:07	Results: Synthetic Domain
21:54	Conclusion
22:44	Future Work
23:43	- Questions

Lecture rating

People found this lecture:
Worth seeing
because it is:
Valuable and informative
Well presented
Easily understandable
Acceptably recorded
You need to login to cast your vote.

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.