Learning Latent Semantic Space for Ranking

• US 20100161596A1
• Filed: 12/24/2008
• Published: 06/24/2010
• Est. Priority Date: 12/24/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yan, Jun, Liu, Ning, Chen, Zheng, Ji, Lei
• Granted Patent: US 8,239,334 B2
• Time in Patent Office: Days
• US Class Current: 707/723
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A tool facilitating learning latent semantics for ranking (LLSR) tailored to the ranking task via leveraging relevance information of query-document pairs to learn a tailored latent semantic space such that other documents are better ranked for the queries in the subspace. The tool applying a learning latent semantics for ranking algorithm integrating LLSR, thereby enabling learning an optimal latent semantic space (LSS) for ranking by utilizing relevance information in the training process of subspace learning. The tool enabling an optimization of the LSS as a closed form solution and facilitating reporting the learned LSS.

Claims

1. A computer-implemented method of subspace learning for ranking, the method comprising:

learning from a plurality of labeled queries;

applying the learning from the labeled queries for ranking unranked documents;

obtaining, via the applying, a learned latent semantic space (LSS) for ranking unranked documents;

providing ranking for unranked documents in the learned LSS;

reporting the learned LSS including the unranked documents based at least in part on the ranking.

2. The method as recited in claim 1 further comprising:

maximizing an average of pair-wise labeled information of a query such that

$\frac{1}{<br><br>d_i;<br><br>-d_j;<br><br>q_i<br><br>}<br><br>\underset{d_j-d_i;<br><br>q_k}{\sum <br><br>}<br><br>\mathrm{tr}<br><br>\left\{W^T<br><br>\left(\left(2<br><br>q_i-d_j-d_i\right)<br><br>{\left(d_i-d_j\right)}^T\right)<br><br>W\right\}<br><br>{\mathrm{\xi <br><br>}}_{q_k}$

represents the pair-wise ranked data for the query represented as q_k, wherein;

|d_id_j;

q_k| represents the number of the pair-wise labeled data, and

ξ

_kij represents a weight characterizing importance of a ranked pair for a given query.

3. The method as recited in claim 2 wherein optimizing

$\frac{1}{}$

d i ;

- d j ;

q i 



∑

d j - d i ;

q k 

tr 

{ W T 

( ( 2 

q i - d j - d i ) 

( d i - d j ) T ) 

W } 

ξ

q k

embodies a closed form solution.

4. The method as recited in claim 1 further comprising calculating relevance between a document and a query based on a similarity measurement or a dissimilarity measurement.

5. The method as recited in claim 1 further comprising calculating relevance between a document and a query using Euclidean distance.

6. The method as recited in claim 1 wherein a labeled query denotes relevance to at least one document.

7. The method as recited in claim 1 wherein at least one labeled query has been manually labeled.

8. One or more computer readable media storing instructions for implementing the method of claim 1.

9. A computer readable media having computer-executable instructions embodied thereon, the computer-executable instructions to configure a computer to perform acts comprising:

subspace learning for ranking; and

returning a search based at least in part on the subspace learning for ranking.

10. The computer readable media as recited in claim 9 wherein the subspace learning for ranking is tailored for ranking based at least in part on labeled relevance information obtained during the training process of subspace learning.

11. The computer readable media as recited in claim 9 wherein the subspace learning for ranking further comprises:

learning from a plurality of labeled queries; and

applying the learning from the labeled queries for ranking unranked documents.

12. The computer readable media as recited in claim 9 wherein the acts further comprise:

obtaining a training query and documents to be processed as ranked query-document pairs;

indexing the training query and documents as training data in a vector space model having a dimension;

producing a training database via the indexing;

applying a learning latent semantic space for ranking algorithm;

receiving ordinal information of indexed documents;

integrating the ordinal information of the indexed documents into ranking in a learned subspace for ranking;

projecting data from the learned subspace for ranking to a document database; and

reporting the learned subspace including unranked documents.

13. The computer readable media as recited in claim 12 wherein the reporting comprises ranked text retrieval.

14. The computer readable media as recited in claim 12 wherein the reporting the learned subspace including unranked documents is based at least in part on the ranking.

15. The computer readable media as recited in claim 12 wherein applying the learning latent semantic space for ranking algorithm transforms the training data to a lower-dimensional feature subspace.

16. A computing device comprising:

a memory comprising the computer readable media as recited in claim 9; and

a processor operably coupled to the memory that upon executing the computer-executable instructions configures the computing device as the computer to perform the subspace learning for ranking.

17. A method comprising:

receiving as a training set, a set of ranked query-document pairs;

summarizing global text information from documents in the training set by computing a first matrix;

summarizing rank information from the training data by computing a second matrix;

applying the first matrix to the second matrix to smooth the second matrix to obtain a third matrix;

computing eigenvectors of the third matrix as column vectors of a subspace; and

reporting the subspace as a latent semantic space for ranking.

18. The method of claim 17 wherein smoothing the second matrix alleviates overfitting.

19. The method of claim 17 wherein the latent semantic space satisfies

∥

q_k′

−

d_j′

∥

²−

∥

q_k′

−

d_i∥

²>

0.

20. The method of claim 17 wherein the latent semantic space for ranking is defined as Ω

_p(W*|D) where

$W^{*}=\underset{W\in <br><br>R^{m\times <br><br>p}}{\arg <br><br><br><br>\max }<br><br>\mathrm{tr}<br><br>\left\{W^T<br><br>\left(\mathrm{\beta <br><br>\delta <br><br>}<br><br><br><br>C_1+\left(1-\mathrm{\beta <br><br>}\right)<br><br>C_2\right)<br><br>W\right\}$

such that W^TW=I.