Automated feature selection based on rankboost for ranking

• US 8,301,638 B2
• Filed: 09/25/2008
• Issued: 10/30/2012
• Est. Priority Date: 09/25/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Xu, Ning-Yi, Hsu, Feng-Hsiung, Gao, Rui, Cai, Xiong-Fei, Chen, Junyan
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Burke, Jeff A.
• Application Number:
  US12/238,012
• Publication Number:
  US 20100076911A1
• Time in Patent Office: 1,496 Days
• Field of Search: 707/48, 706/12, 706 14- 15, 706/20
• US Class Current: 707/748
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A method using a RankBoost-based algorithm to automatically select features for further ranking model training is provided. The method reiteratively applies a set of ranking candidates to a training data set comprising a plurality of ranking objects having a known pairwise ranking order. Each round of iteration applies a weight distribution of ranking object pairs, yields a ranking result by each ranking candidate, identifies a favored ranking candidate for the round based on the ranking results, and updates the weight distribution to be used in next iteration round by increasing weights of ranking object pairs that are poorly ranked by the favored ranking candidate. The method then infers a target feature set from the favored ranking candidates identified in the iterations.

Claims

1. A computer implemented method used in a ranking algorithm, the method comprising:

reiteratively applying a set of ranking candidates to a training data set comprising a plurality of ranking objects having a known pairwise ranking order, wherein each iteration applies a weight distribution of ranking object pairs, yields a ranking result by each ranking candidate, identifies a favored ranking candidate based on the ranking results, and updates the weight distribution to be used in a next iteration by increasing weights of ranking object pairs that are poorly ranked by the favored ranking candidate, wherein the ranking result is determined based in part on building a histogram and determining an integral histogram associated with the histogram; and

inferring a target feature set from the favored ranking candidates identified in a plurality of iterations.

2. The method as recited in claim 1, wherein the set of ranking candidates are derived from an initial set of ranking features.

3. The method as recited in claim 2, wherein each ranking candidate is associated with one or more ranking features, and inferring a target feature set from the favored ranking candidates comprises:

selecting at least some ranking features associated with the favored ranking candidates and including them in the target feature set.

4. The method as recited in claim 2, wherein each ranking candidate is associated with one or more ranking features, and is derived from the associated one or more ranking features based on a linear ranker scheme or based on a threshold ranker scheme.

5. The method as recited in claim 2, wherein each ranking candidate is associated with at least one ranking feature, and inferring a target feature set from the favored ranking candidates comprises:

selecting the ranking features associated with the favored ranking candidates and including them in the target feature set.

6. The method as recited in claim 1, wherein the set of ranking candidates comprises at least one subset of ranking candidates, and the ranking candidates of each subset are derived from a common single ranking feature and differ from one another by each having a different threshold parameter.

7. The method as recited in claim 1, wherein the favored ranking candidate of each iteration round is identified by selecting a best performing ranking candidate of the iteration round.

8. The method as recited in claim 1, wherein the ranking objects that are poorly ranked by the favored ranking candidate are identified by comparing the ranking result with the known pairwise ranking order of the training data.

9. The method as recited in claim 1, further comprising:

constructing an output ranking model using a linear combination of the selected favored ranking candidates.

10. The method as recited in claim 9, wherein the target feature set is inferred from the output ranking model.

11. The method as recited in claim 1, wherein the ranking candidates are weak rankers.

12. The method as recited in claim 1, further comprising:

stopping iteration at a user chosen stop point.

13. The method as recited in claim 1, further comprising:

inputting the selected target feature set to a training engine; and

training the selected target feature set using the training engine to obtain a final ranking model.

14. The method as recited in claim 13, wherein the training engine comprises a RankNet or a RankBoost training procedure.

15. The method as recited in claim 1, wherein reiteratively applying a set of candidate rankers to a training data set is performed using an FPGA-based accelerator.

16. A method for selecting the feature set for a ranking algorithm, the method comprising:

constructing a set of ranking candidates using an initial set of features;

applying each ranking candidate to a training data set comprising a plurality of ranking objects having a known pairwise ranking order and a weight distribution of ranking object pairs, each ranking candidate yielding a ranking result, wherein the ranking result is determined based in part on building a histogram and determining an integral histogram associated with the histogram;

comparing the ranking results of the set of ranking candidates to identify a favored ranking candidate;

analyzing the ranking result of the favored ranking candidate to identify ranking object pairs poorly ranked by the favored ranking candidate;

adjusting the weight distribution by increasing the weights of the ranking object pairs poorly ranked by the favored ranking candidate;

reiterating the above applying, comparing, analyzing, and adjusting, each iteration identifying a favored ranking candidate; and

inferring a target feature set from the favored ranking candidates identified in previous iterations.

17. The method as recited in claim 16, wherein each ranking candidate is associated with one or more ranking features, and inferring a target feature set from the favored ranking candidates comprises:

selecting at least some ranking features associated with the favored ranking candidates and including them in the target feature set.

18. One or more computer readable tangible physical memory devices having stored thereupon a plurality of instructions that, when executed by a processor, causes the processor to:

reiteratively apply a set of ranking candidates to a training data set comprising a plurality of ranking objects having a known pairwise ranking order, wherein each iteration applies a weight distribution of ranking object pairs, yields a ranking result by each ranking candidate based in part on building a histogram and determining an integral histogram associated with the histogram, identifies a favored ranking candidate based on the ranking results, and updates the weight distribution to be used in next iteration by increasing weights of ranking object pairs that are poorly ranked by the favored ranking candidate; and

prepare the favored ranking candidates identified in a plurality of iterations for inferring a target feature set therefrom.