Learning algorithm for ranking on graph data
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
27 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
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. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25)
-
-
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.
Specification