Augmenting user, query, and document triplets using singular value decomposition

• US 20070055646A1
• Filed: 09/08/2005
• Published: 03/08/2007
• Est. Priority Date: 09/08/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Chen, Zheng, Sun, Jian-Tao, Zhang, Benyu, Zeng, Hua-Jun
• Granted Patent: US 7,747,618 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A system for augmenting click-through data with latent information present in the click-through data for use in generating search results that are better tailored to the information needs of a user submitting a query is provided. The augmentation system creates a three-dimensional matrix with the dimensions of users, queries, and documents. The augmentation system then performs a three-order singular value decomposition of the three-dimensional matrix to generate a three-dimensional core singular value matrix and a left singular matrix for each dimension. The augmentation system finally multiplies the three-dimensional core singular value matrix by the left singular matrices to generate an augmented three-dimensional matrix that explicitly contains the information that was latent in the un-augmented three-dimensional matrix.

Claims

1. A method in a computer system for augmenting user, query, and document triplets, the method comprising:

providing triplets comprising a user, a query, and a document, a triplet indicating that the user submitted the query and then selected the document from a result of the query;

creating a three-dimensional matrix with values of the matrix based on whether the corresponding user, query, and document is in a provided triplet;

performing a three-order singular value decomposition of the three-dimensional matrix; and

generating an augmented three-dimensional matrix from the three-order singular value decomposition to represent augmented user, query, and document triplets.

2. The method of claim 1 wherein the performing of the three-order singular value decomposition includes:

generating unfolded two-dimensional matrices for users, queries, and documents;

performing a two-order singular value decomposition for each unfolded two-dimensional matrix, wherein a left singular matrix is generated;

selecting a reduced dimension for each left singular matrix; and

generating a three-dimensional core singular value matrix by combining the left singular matrices with reduced dimensions with the three-dimensional matrix.

3. The method of claim 2 wherein the generating of the augmented three-dimensional matrix includes combining the three-dimensional core singular value matrix with the non-reduced left singular matrices.

4. The method of claim 1 including before performing the three-order singular value decomposition, applying a weighting policy to the values of the three-dimensional matrix.

5. The method of claim 4 wherein the weighting policy is selected from the group consisting of a Boolean policy, a log frequency policy, and a log inverse document frequency policy.

6. The method of claim 1 including before performing the three-order singular value decomposition, applying a smoothing policy to the values of the three-dimensional matrix.

7. The method of claim 6 wherein the smoothing policy is selected from the group consisting of a constant policy and a document similarity policy.

8. The method of claim 1 including before performing the three-order singular value decomposition, applying a normalization policy to the three-dimensional matrix.

9. The method of claim 8 wherein the normalization policy normalizes along the query dimension.

10. The method of claim 1 including before performing the three-order singular value decomposition, applying a weighting policy followed by a smoothing policy followed by a normalization policy to the three-dimensional matrix.

11. The method of claim 1 including when a user submits a query, identifying documents relevant to the query based on the values in the augmented three-dimensional matrix for that user and query.

12. A computer-readable medium containing instructions for controlling a computer system to augment user, query, and document triplets, by a method comprising:

providing a three-dimensional matrix of users, queries, and documents with values of the three-dimensional matrix indicating whether the corresponding user would find the corresponding document relevant to the corresponding query;

performing a three-order singular value decomposition of the three-dimensional matrix; and

generating an augmented three-dimensional matrix from the three-order singular value decomposition to represent the augmented user, query, and document triplets.

13. The computer-readable medium of claim 12 wherein the performing of the three-order singular value decomposition includes:

performing a two-order singular value decomposition for unfolded two-dimensional matrices for users, queries, and documents, each unfolded matrix generating from unfolding the three-dimensional matrix in the other dimensions; and

generating a three-dimensional core singular value matrix by combining the three-dimensional matrix with left singular matrices with reduced dimensions derived from a two-order singular value decomposition of the unfolded matrices.

14. The computer-readable medium of claim 13 wherein the generating of the augmented three-dimensional matrix includes combining the three-dimensional core singular value matrix with the left singular matrices with non-reduced dimensions.

15. The computer-readable medium of claim 12 including before performing the three-order singular value decomposition, adjusting values of the three-dimensional matrix to account for variations in frequencies.

16. The computer-readable medium of claim 12 including before performing the three-order singular value decomposition, adjusting values based on similarity between a document that the user did visit from the query and a document that the user did not visit from the query.

17. The computer-readable medium of claim 12 including before performing the three-order singular value decomposition, normalizing the values in a dimension.

18. A system for augmenting user, query, and document triplets, comprising:

a three-dimensional matrix of users, queries, and documents with values of the three-dimensional matrix indicating whether the corresponding user would find the corresponding document relevant to the corresponding query; and

a component that generates an augmented three-dimensional matrix from a three-order singular value decomposition of the three-dimensional matrix to represent the augmented user, query, and document triplets.

19. The computer system of claim 18 including a component that performs the three-order singular value decomposition by:

performing a two-order singular value decomposition for unfolded two-dimensional matrices for users, queries, and documents, each unfolded matrix generating from unfolding the three-dimensional matrix in the other dimensions; and

generating a three-dimensional core singular value matrix by combining the three-dimensional matrix with left singular matrices with reduced dimensions derived from the two-order singular value decomposition.

20. The computer system of claim 19 wherein the generating of the augmented three-dimensional matrix includes combining the three-dimensional core singular value matrix with the left singular matrices with non-reduced dimensions.