event thumbnail image
NIPS ´08 Workshop: Algebraic and combinatorial methods in machine learning

Graph Helmholtzian and rank learning

author: Lek-Heng Lim, UC Berkeley, University of California

Description

The graph Helmholtzian is the graph theoretic analogue of the Helmholtz operator or vector Laplacian, in much the same way the graph Laplacian is the analogue of the Laplace operator or scalar Laplacian. We will see that a decomposition associated with the graph Helmholtzian provides a way to learn ranking information from incomplete, imbalanced, and cardinal score-based data. In this framework, an edge flow representing pairwise ranking is orthogonally resolved into a gradient flow (acyclic) that represents the L2-optimal global ranking and a divergence-free flow (cyclic) that quantifies the inconsistencies. If the latter is large, then the data does not admit a statistically meaningful global ranking. A further decomposition of the inconsistent component into a curl flow (locally cyclic) and a harmonic flow (locally acyclic) provides information on the validity of small- and large-scale comparisons of alternatives. This is joint work with Xiaoye Jiang, Yuan Yao, and Yinyu Ye.

You might be experiencing some problems with Your Video player.
Slides
0:00 Graph Helmholtzian and Rank Learning
1:00 Modern ranking data
3:00 Old problems with ranking
4:41 New problems with ranking
6:50 Example: Netflix customer-product rating
8:05 Objective
9:24 Local inconsistencies
10:42 Basic model for rank learning
12:23 Rank aggregation
13:14 Pairwise rank aggregation
14:57 More second order statistics
15:12 Functions on graph
17:35 Hilbert space of forms
19:03 Operators
20:48 Properties
22:45 Helmholtz decomposition
23:37 Hodge theory: matrix theoretic
24:10 Hodge theory: graph theoretic
24:36 Rank aggregation problem revisited
25:20 Answer: not always
26:27 Boundary of a boundary is empty
27:25 Illustration
28:24 Harmonic rankings: locally consistent but globally inconsistent
28:52 - Questions
29:15 - Questions
29:24 - Questions
29:52 - Questions
31:27 - Questions
32:08 - 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.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: