Learning algorithm for ranking on graph data

• US 20080097941A1
• Filed: 10/19/2007
• Published: 04/24/2008
• Est. Priority Date: 10/19/2006
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Agarwal, Shivani
• Granted Patent: US 8,332,333 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Described are techniques for ranking a data set of objects. A graph representing the data set is provided. Examples of ranking preferences are provided for a portion of objects in the data set. Each of the examples indicates a ranking of a first object of the portion with respect to a second object of the portion. In accordance with the examples, a function, f, is determined that ranks the objects of the data set. A ranking of the objects of the data set is determined using the function f.

Claims

1. A method for ranking a data set of objects comprising:

providing a graph representing the data set;

providing examples of ranking preferences for a portion of objects in the data set, each of said examples indicating a ranking of a first object of the portion with respect to a second object of the portion;

determining, in accordance with said examples, a function, f, that ranks the objects of the data set; and

determining a ranking of the objects of the data set using said function, f.

2. The method of claim 1, wherein said function, f, minimizes an objective function.

3. The method of claim 2, wherein said objective function is formed using an error term and a regularization term.

4. The method of claim 3, wherein said error term includes a loss function and is determined using penalty values associated with the examples.

5. The method of claim 3, wherein said regularization term is formed using a regularizer determined from the graph of the input data set and regularization parameter value used to weight the regularization term in accordance with said error term.

6. The method of claim 2, wherein said graph includes a set of vertices corresponding to the objects, a set of edges where each of said edges represents a similarity between two vertices connected by said each edge, and a set of weights where each of said weights is associated with one of said edges and represents a degree of similarity between two vertices connected by said one edge.

7. The method of claim 6, wherein said graph is an undirected graph and said objective function includes a regularizer formed using a Laplacian matrix of the graph representing the data set of objects.

8. The method of claim 7, wherein said objective function includes an error term formed using penalty values associated with said examples and using a convex upper bound of a step-loss function, l(f:

vi, vj), wherein, for one of said examples indicating that a vertex vi of the graph is ranked higher than vertex vj, the step-loss function l(f;

vi, vj), for the pair of vertices, vi, vj, is 1 if f(vi)<

f(vj), ½

if f(vi)=f(vj), or 0 if f(vi)>

f(vj).

9. The method of claim 8, wherein, said objective function uses a convex upper bound on the step-loss function of the error term represented as:

l_h(f;

vi,vj)=(1−

(f(vi)−

f(vj)))₊

where, if (1−

(f(vi)−

f(vj)))>

0, then l_h (f;

vi, vj)=(1−

(f(vi)−

f(vj))), and otherwise, l_h (f;

vi, vj)=0.

10. The method of claim 6, wherein said graph is a directed graph and said objective function includes a regularization term formed using a Laplacian of the graph determined using a transitional probability matrix.

11. The method of claim 1, wherein said data set is a set of documents.

12. The method of claim 11, wherein the documents are ranked in accordance with one or more query terms.

13. The method of claim 11, wherein the documents include multimedia documents.

14. The method of claim 1, wherein said data set is a set of molecules ranked according to biological activity with respect to a particular target.

15. The method of claim 14, wherein the molecules include chemical structures.

16. The method of claim 6, wherein said graph of the data set is a data graph, and said examples are represented as an order graph, said order graph being a directed graph formed from a subset of vertices of said data graph, edges and weights, each of said edges from a first vertex of said subset to a second vertex of said subset indicating that said first vertex is ranked higher than said second vertex, each of said weights corresponding to one of said edges and indicating a penalty value for improperly ordering said first vertex and said second vertex of said one edge.

17. A method for ranking a data set of objects comprising:

providing a graph representing similarity between pairs of the objects of the data set, said graph including vertices corresponding to the objects, said graph including edges, each of said edges between a pair of vertices having a weight corresponding to a similarity measurement between objects that correspond to the pair of vertices;

providing examples of ranking preferences for a portion of objects in the data set, each of said examples indicating a ranking of a first object included in the portion with respect to a second object included in the portion;

determining, in accordance with said examples, a function, f, that minimizes an objective function, said objective function including an error term and a regularization term, said error term being formed from a loss function and penalty values associated with improperly ranking pairs of objects included in said examples, said regularization term formed using a weighting factor and a regularizer that provides a measurement of how smooth the function f is with respect to ranking a pair of objects in accordance with their respective similarity; and

outputting a ranking of said objects in the data set using said function, f.

18. The method of claim 17, wherein said regularizer is formed using a Laplacian matrix of the graph.

19. The method of claim 18, wherein said graph is a directed graph and the Laplacian matrix is formed using a transition probability matrix.

20. The method of claim 18, wherein said graph is an undirected graph and the Laplacian matrix, L, is represented as:

L=D<sup>−

1/2</sup>(D−

W)D<sup>−

1/2</sup>

where D is a diagonal matrix and W is an “

n×

n”

matrix, n=a number of vertices in the graph, with entry Wij=w(vi, vj) for all edges {vi, vj} of the graph, Wij=0 otherwise, w(vi, vj) representing a weight associated with an edge between vertex vi and vertex vj in the graph, and D is a diagonal matrix with entry Dii=d(vi), w(vi, vj) being the weight of the edge between vertices vi and vj of the graph.

21. The method of claim 18, wherein said regularization term include a regularizer S(f) represented as:

S(f)=F^TLF

where L represents the Laplacian matrix of the graph, F is a column vector of ranking function values for each of the vertices in the graph, and F^T is a transpose of the column vector F.

22. The method of claim 17, wherein the examples of ranking preferences are specified using one of a real value assigned to each object in the portion or a partitioning of the objects in the portion into a first partition of relevant objects and a second partition of objects which are not relevant.

23. The method of claim 17, further comprising:

preprocessing a first form of the examples of ranking preferences to convert the first form into a second form including pairs of vertices and an associated one of said penalty values with each of said pairs, said penalty value indicating a penalty incurred for misordering vertices of said each pair.

24. The method of claim 17, wherein said data set is a set formed from webpages, products, or genes.

25. A computer readable medium comprising code stored thereon for ranking a data set of objects, the computer readable medium comprising code for:

providing a graph representing similarity between pairs of the objects of the data set, said graph including vertices corresponding to the objects, said graph including edges, each of said edges between a pair of vertices having a weight corresponding to a similarity measurement between objects that correspond to the pair of vertices;

providing examples of ranking preferences for a portion of objects in the data set, each of said examples indicating a ranking of a first object included in the portion with respect to a second object included in the portion;

determining, in accordance with said examples, a function, f, that minimizes an objective function, said objective function including an error term and a regularization term, said error term being formed from a loss function and penalty values associated with improperly ranking pairs of objects included in said examples, said regularization term formed using a weighting factor and a regularizer that provides a measurement of how smooth the function f is with respect to ranking a pair of objects in accordance with their respective similarity; and

outputting a ranking of said objects in the data set using said function, f.