Regularized latent semantic indexing for topic modeling

• US 8,533,195 B2
• Filed: 06/27/2011
• Issued: 09/10/2013
• Est. Priority Date: 06/27/2011
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Xu, Jun, Li, Hang, Craswell, Nicholas
• Primary Examiner(s): NGUYEN, PHONG H
• Application Number:
  US13/169,808
• Publication Number:
  US 20120330958A1
• Time in Patent Office: 806 Days
• Field of Search: 707/738, 707/739, 707/750, 707/776, 706/55
• US Class Current: 707/738
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 18/2136 based on sparsity criteria, e.g. with an overcomplete basis
• CPC Class Codes: G06F 2212/454 Vector or matrix data
• CPC Class Codes: G06V 10/95 structured as a network, e.g. client-server architectures

Abstract

Electronic documents are retrieved from a database and/or from a network of servers. The documents are topic modeled in accordance with a Regularized Latent Semantic Indexing approach. The Regularized Latent Semantic Indexing approach may allow an equation involving an approximation of a term-document matrix to be solved in parallel by multiple calculating units. The equation may include terms that are regularized via either l₁ norm and/or via l₂ norm. The Regularized Latent Semantic Indexing approach may be applied to a set, or a fixed number, of documents such that the set of documents is topic modeled. Alternatively, the Regularized Latent Semantic Indexing approach may be applied to a variable number of documents such that, over time, the variable of number of documents is topic modeled.

Claims

1. A topic modeling system, comprising:

at least one calculating unit; and

at least one computer readable medium in communication with the at least one calculating unit and having instructions and a first equation stored therein, the first equation having terms including a term-document matrix D, a term-topic matrix U, a topic-document matrix V, a regularization of vectors of the term-topic matrix U and a regularization of vectors of the topic-document matrix V, the term-document matrix D having N columns, N>

1, each column of the term-document matrix D representing a respective document and having M (M>

1) members in which each member represents a respective term of the respective document, the term-topic matrix U and the topic-document matrix V are related such that the term-document matrix D is approximated by a matrix multiplication of the term-topic matrix U and the topic-document matrix V, when executed by the at least one calculating unit, cause the at least one calculating unit to perform acts comprising;

for a number of iterations,

minimizing the first equation while holding the topic-document matrix V fixed;

updating the term-topic matrix U based at least on values of the topic-document matrix V calculated in a most recent minimization of the first equation;

minimizing the first equation while holding the term-topic matrix U fixed; and

updating the topic-document matrix V based at least on values of the term-topic matrix U calculated in a most recent minimization of the first equation.

2. The topic modeling system as recited in claim 1, wherein the at least one calculating unit comprises multiple calculating units, and the acts further comprise:

providing each calculating unit of a first plurality of calculating units with at least a respective vector of the term-document matrix D and at least a respective vector of the term-topic matrix U, most recently updated, the multiple calculating units including the first plurality of calculating units; and

wherein the minimizing the first equation while holding the topic-document matrix V fixed includes;

independently solving a respective vector of the term-topic matrix U at a respective calculating unit of the first plurality of calculating units based at least in part on the respective calculating unit minimizing a respective second equation that is a decomposition of the first equation.

3. The topic modeling system as recited in claim 2, the acts further comprising:

providing each calculating unit of a second plurality of calculating units with at least a respective vector of the term-document matrix D and at least a respective vector of the topic-document matrix V, most recently updated, the multiple calculating units including the second plurality of calculating units; and

wherein the minimizing the first equation while holding term-topic matrix U fixed includes;

independently solving a respective vector of the topic-document matrix V at a respective calculating unit of the second plurality of calculating units based at least in part on the respective calculating unit minimizing a respective third equation that is a decomposition of the first equation.

4. The topic modeling system as recited in claim 3, wherein the multiple calculating units include multiple processors of a single computer.

5. The topic modeling system as recited in claim 3, wherein the multiple calculating units include computing systems coupled together over a communication network.

6. The topic modeling system as recited in claim 1, wherein the minimizing the first equation while holding the topic-document matrix V fixed includes the regularization of vectors of the term-topic matrix U, and the minimizing the first equation while holding the term-topic matrix U fixed includes the regularization of vectors of the topic-document matrix V.

7. The topic modeling system as recited in claim 6, wherein the regularization of vectors of the term-topic matrix U is based on either an l1 norm or an l2 norm and the regularization of vectors of the topic-document matrix V is based on either an l1 norm or an l2 norm.

8. The topic modeling system as recited in claim 7, wherein the regularization of vectors of the term-topic matrix U is based on the l1 norm and the regularization of vectors of the topic-document matrix V is based on the l2 norm.

9. The topic modeling system as recited in claim 1, the acts further comprising:

retrieving a number (N) of electronic documents;

generating the term-document matrix D based at least on the retrieved documents; and

initializing the topic-document matrix V based at least on random values assigned to members of the topic-document matrix V.

10. The topic modeling system as recited in claim 1, wherein the minimizing the first equation while holding the topic-document matrix V fixed includes the regularization of column vectors of the term-topic matrix U, and the minimizing the first equation while holding the term-topic matrix U fixed includes the regularization of column vectors of the topic-document matrix V.

11. The topic modeling system as recited in claim 10, wherein the regularization of column vectors of the term-topic matrix U is based on an l₁ norm and the regularization column vectors of the topic-document matrix V is based on an l₂ norm.

12. A computer-implemented method for topic modeling, comprising:

defining a first equation having terms including a term-document matrix D, a term-topic matrix U, a topic-document matrix V, a regularization of vectors of the term-topic matrix U and a regularization of vectors of the topic-document matrix V, the term-document matrix D having N columns, N>

1, each column of the term-document matrix D representing a respective document and having M (M>

1) members in which each member represents a respective term of the respective document, the term-topic matrix U and the topic-document matrix V are related such that a matrix multiplication of the term-topic matrix U and the topic-document matrix V is approximated as the term-document matrix D;

retrieving a number (N) of electronic documents;

representing each retrieved document as a respective vector of the term-document matrix D; and

for a number of iterations,

minimizing the first equation while holding the topic-document matrix V fixed,

updating the term-topic matrix U based at least on values of the topic-document matrix V calculated in a most recent minimization of the first equation,

minimizing the first equation while holding the term-topic matrix U fixed, and

updating the topic-document matrix V based at least on values of the term-topic matrix U calculated in a most recent minimization of the first equation; and

storing, at a computer readable storage medium, at least one of the most recently updated term-topic matrix U and the topic-document matrix V.

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

providing each calculating unit of a first plurality of calculating units with at least a respective vector of the term-document matrix D and at least a respective vector of the term-topic matrix U, most recently updated, the multiple calculating units including the first plurality of calculating units; and

wherein the minimizing the first equation while holding the topic-document matrix V fixed includes;

independently solving a respective vector of the term-topic matrix U at a respective calculating unit of the first plurality of calculating units based at least in part on the respective calculating unit minimizing a respective second equation that is a decomposition of the first equation.

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

providing each calculating unit of a second plurality of calculating units with at least a respective vector of the term-document matrix D and at least a respective vector of the topic-document matrix V, most recently updated, the multiple calculating units including the second plurality of calculating units; and

wherein the minimizing the first equation while holding term-topic matrix U fixed includes;

independently solving a respective vector of the topic-document matrix V at a respective calculating unit of the second plurality of calculating units based at least in part on the respective calculating unit minimizing a respective third equation that is a decomposition of the first equation.

15. The method as recited in claim 12, wherein the minimizing the first equation while holding the topic-document matrix V fixed includes regularizing vectors of the term-topic matrix U, and the minimizing the first equation while holding the term-topic matrix U fixed includes regularizing vectors of the topic-document matrix V.

16. The method as recited in claim 15, wherein the regularizing vectors of the term-topic matrix U is based on either an l₁ norm or an l₂ norm and the regularizing vectors of the topic-document matrix V is based on either an l₁ norm or an l₂ norm.

17. The topic modeling system as recited in claim 16, wherein the regularizing vectors of the term-topic matrix U is based on an l₁ norm and the regularizing vectors of the topic-document matrix V is based on an l₂ norm.

18. One or more computer-readable storage media storing computer-executable instructions that, when executed on one or more processors, causes the one or more processors to perform acts comprising:

retrieving a number (N) of electronic documents;

representing each retrieved document as a respective vector of a term-document matrix D;

defining a first equation having terms including the term-document matrix D, a term-topic matrix U, a topic-document matrix V, the term-topic matrix U and the topic-document matrix V are related such that a matrix multiplication of the term-topic matrix U and the topic-document matrix V is approximated as the term-document matrix D;

independently solving in parallel for vectors of the topic-document matrix V and the term-topic matrix U; and

updating the topic-document matrix V and the term-topic matrix U based at least in part of the solved vectors of the document matrix V and the term-topic matrix U; and

storing at least one of the document matrix V and the term-topic matrix U.

19. The one or more computer-readable storage media as recited in claim 18, wherein the independently solving in parallel for vectors of the topic-document matrix V and the term-topic matrix U includes regularizing vectors of the term-topic matrix U based on either an l₁ norm or an l₂ norm and regularizing vectors of the topic-document matrix V based on either an l₁ norm or an l₂ norm.

20. The one or more computer-readable storage media as recited in claim 18, wherein the independently solving in parallel for vectors of the topic-document matrix V and the term-topic matrix U comprises:

holding the topic-document matrix V fixed while solving in parallel for the vectors of the term-topic matrix U; and

holding the term-topic matrix U fixed while solving in parallel for the vectors of the topic-document matrix V.