Learning algorithm for ranking on graph data

• US 8,332,333 B2
• Filed: 10/19/2007
• Issued: 12/11/2012
• Est. Priority Date: 10/19/2006
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Agarwal, Shivani
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Hill, Stanley K
• Application Number:
  US11/975,697
• Publication Number:
  US 20080097941A1
• Time in Patent Office: 1,880 Days
• Field of Search: None
• 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 identifying a pair of objects of the portion, the pair of objects indicating a ranking preference of a first object of the pair with respect to the second object of the pair, said each example indicating that the first object of the pair is ranked higher than the second object of the pair, wherein penalty values are specified for said examples, one of said penalty values being specified for each of said examples wherein the one of the penalty values for said each example indicates a penalty value for improperly ordering the pair of objects of said each example, a first of the penalty values for a first of said examples specifying a first value that is different than a second value specified as a second of the penalty values for a second of said examples, wherein an allowable value for each of the penalty values includes any real value;

determining, using inputs including said examples and the penalty values specified for 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, wherein at least one of said providing a graph, said providing examples, said determining a function and said determining a ranking are performed using a processor.

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:

lh(f;

vi,vj)=(1−

(f(vi)−

f(vj)))₊

where, if (1−

(f(vi)−

f(vj)))>

0, then lh (f;

vi, vj)=(1−

(f(vi)−

f(vj))), and otherwise, lh (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. The method of claim 1, wherein a different one of the penalty values is specified for each of the examples.

18. 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 identifying a pair of objects of the portion, the pair of objects indicating a ranking preference of a first object of the pair with respect to a second object of the pair, wherein penalty values are specified for said examples, one of said penalty values being specified for each of said examples wherein the one of the penalty values for said each example indicates a penalty value for improperly ordering the pair of objects of said each example, a first of the penalty values for a first of said examples specifying a first value that is different than a second value specified as a second of the penalty values for a second of said examples, wherein an allowable value for each of the penalty values includes any real value;

determining, using inputs including said examples and the penalty values specified for 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, wherein at least one of said providing a graph, said providing examples, said determining a function and said outputting a ranking are performed using a processor.

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

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

21. The method of claim 19, 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.

22. The method of claim 19, 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.

23. The method of claim 18, 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.

24. The method of claim 18, 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.

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

26. A non-transitory 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 identifying a pair of objects of the portion, the pair of objects indicating a ranking preference of a first object of the pair with respect to a second object of the pair, wherein penalty values are specified for said examples, one of said penalty values being specified for each of said examples wherein the one of the penalty values for said each example indicates a penalty value for improperly ordering the pair of objects of said each example, a first of the penalty values for a first of said examples specifying a first value that is different than a second value specified as a second of the penalty values for a second of said examples, wherein an allowable value for each of the penalty values includes any real value;

determining, using inputs including said examples and the penalty values specified for 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 the 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.

27. A nontransitory computer readable medium comprising code for ranking a data set of objects, the nontransitory computer readable medium comprising code for:

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 identifying a pair of objects of the portion, the pair of objects indicating a ranking preference of a first object of the pair with respect to the second object of the pair, said each example indicating that the first object of the pair is ranked higher than the second object of the pair, wherein penalty values are specified for said examples, one of said penalty values being specified for each of said examples wherein the one of the penalty values for said each example indicates a penalty value for improperly ordering the pair of objects of said each example, a first of the penalty values for a first of said examples specifying a first value that is different than a second value specified as a second of the penalty values for a second of said examples, wherein an allowable value for each of the penalty values includes any real value;

determining, using inputs including said examples and the penalty values specified for 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, wherein at least one of said providing a graph, said providing examples, said determining a function and said determining a ranking are performed using a processor.