Propagating relevance from labeled documents to unlabeled documents

• US 20070203940A1
• Filed: 02/27/2006
• Published: 08/30/2007
• Est. Priority Date: 02/27/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Li, Mingjing, Li, Zhiwei, Wang, Jue
• Granted Patent: US 8,019,763 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A method and system for propagating the relevance of labeled documents to a query to unlabeled documents is provided. The propagation system provides training data that includes queries, documents labeled with their relevance to the queries, and unlabeled documents. The propagation system then calculates the similarity between pairs of documents in the training data. The propagation system then propagates the relevance of the labeled documents to similar, but unlabeled, documents. The propagation system may iteratively propagate labels of the documents until the labels converge on a solution. The training data with the propagated relevances can then be used to train a ranking function.

Claims

1. A system for propagating relevance of labeled documents to unlabeled documents, comprising:

a document store that contains representations of documents, some of the documents being labeled with relevance to a query and others of the documents not being labeled with relevance to the query;

a graph component that creates a graph of the documents with the documents represented as nodes being connected by edges representing similarity between documents; and

a propagate relevance component that propagates relevance of the labeled documents to the unlabeled documents based on the similarity between documents as indicated by the similarity represented by the edges of the graph.

2. The system of claim 1 wherein the graph component includes:

a build graph component that builds a graph in which nodes representing similar documents are connected via edges;

a generate weights component that generates weights for the edges based on similarity of the documents represented by the connected nodes; and

a normalize weights component that normalizes the weights of the graph.

3. The system of claim 2 wherein the build graph component establishes edges between nodes using a nearest neighbor algorithm.

4. The system of claim 3 wherein the nearest neighbor algorithm uses a Euclidean distance metric.

5. The system of claim 3 wherein the build graph component connects a node to its 10 nearest neighbors.

6. The system of claim 2 wherein the build graph component establishes edges between each pair of nodes.

7. The system of claim 2 wherein the build graph component establishes edges between nodes to create a minimum spanning tree.

8. The system of claim 1 wherein the relevance of the labeled documents is generated by searching for documents related to the query in a corpus of documents and the unlabeled documents are not included in the corpus of documents.

9. The system of claim 1 wherein the propagate relevance component propagates relevance using a manifold ranking based algorithm.

10. The system of claim 1 wherein the propagate relevance component propagates relevance according to the following equation:

ƒ

*=(1−

α

)(I−

α

S)<sup>−

1</sup>y

where ƒ

* represents a propagated relevance vector, S is a similarity matrix, y represents an initial relevance vector, and α

represents a decay rate.

11. The system of claim 1 wherein the propagate relevance component propagates relevance according to the following equation:

ƒ

*=(I+α

S+α

²S²+ . . . +α

^NS^N)_y

where ƒ

* represents a propagated relevance vector, S is a similarity matrix, y represents an initial relevance vector, and α

represents a decay rate, and where n represents an exponent for which ƒ

* converges on a solution.

12. A system for propagating relevance of labeled pages to a query to unlabeled pages to the query, comprising:

a page store that contains representations of pages, some of the pages being labeled with relevance to a query and others of the pages not being labeled with relevance to the query;

a graph component that creates a graph of the pages with the pages represented as nodes connected by edges representing similarity between the pages, including;

a build graph component that builds a graph in which nodes representing similar pages are connected via edges; and

a generate weights component that generates weights for the edges based on similarity of the pages represented by the connected nodes; and

a propagate relevance component that propagates relevance of the labeled pages to the unlabeled pages based on the similarity between pages as indicated by the similarity represented by the edges of the graph and based on a manifold ranking algorithm.

13. The system of claim 12 wherein the build graph component establishes edges between nodes using a nearest neighbor algorithm.

14. The system of claim 13 wherein the nearest neighbor algorithm uses a Euclidean distance metric.

15. The system of claim 13 wherein the build graph component connects a node to its 10 nearest neighbors.

16. The system of claim 12 wherein the generate weights component uses a Manhattan distance metric for representing the similarity between pages.

17. The system of claim 12 wherein each page is represented by a feature vector and the similarity between pages is represented by distance in feature vector space.

18. A computer-readable medium containing instructions for controlling a computer system to propagate relevance of documents to a query to other documents, by a method comprising:

creating a graph of the documents represented as nodes connected by edges having weights representing similarity between documents; and

propagating the relevance of the labeled documents to the unlabeled documents based on the weights of the edges between nodes using a manifold ranking based algorithm.

19. The computer-readable medium of claim 18 wherein the propagating of the relevance of the labeled documents includes using a Taylor expansion to iteratively solve the following equation:

ƒ

*=(1−

α

)(I−

α

S)<sup>−

1</sup>y

20. The computer-readable medium of claim 18 wherein the creating of the graph includes connecting edges using a nearest neighbor algorithm and establishing the weight of an edge based on distance between documents represented by the nodes connected by the edge.