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

• US 7,747,618 B2
• Filed: 09/08/2005
• Issued: 06/29/2010
• Est. Priority Date: 09/08/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Huan, Ma, Wei-Ying, Chen, Zheng, Sun, Jian-Tao, Zhang, Benyu, Zeng, Hua-Jun
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Gebresenbet; Dinku W
• Application Number:
  US11/222,243
• Publication Number:
  US 20070055646A1
• Time in Patent Office: 1,755 Days
• Field of Search: None
• US Class Current: 707/732
• 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 performed by a computer system with a processor and a memory for augmenting user, query, and document triplets, the method comprising:

providing in the memory 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 by the processor a three-order singular value decomposition of the three-dimensional matrix by

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; and

generating by the processor 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 generating of the augmented three-dimensional matrix includes combining the three-dimensional core singular value matrix with the non-reduced left singular matrices.

3. 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.

4. The method of claim 3 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.

5. 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.

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

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

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

9. 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.

10. 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.

11. A computer-readable storage medium containing instructions for controlling a computer system with a processor and a memory 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 by the processor a three-order singular value decomposition of the three-dimensional matrix by

performing a two-order singular value decomposition for unfolded two-dimensional matrices for users, queries, and documents, each unfolded matrix generated 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; and

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

12. The computer-readable storage medium of claim 11 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.

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

14. The computer-readable storage medium of claim 11 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.

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

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

a memory storing

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

computer-executable instructions implementing

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 generated 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; 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; and

a processor for executing the computer-executable instructions stored in the memory.

17. The computer system of claim 16 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.