Scalable probabilistic latent semantic analysis

• US 7,844,449 B2
• Filed: 03/30/2006
• Issued: 11/30/2010
• Est. Priority Date: 03/30/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Han, Jie, Xue, Guirong, Chen, Zheng, Zhang, Benyu, Wang, Jian, Zeng, Hua-Jun, Lin, Chenxi
• Primary Examiner(s): Hudspeth; David R
• Assistant Examiner(s): Spooner; Lamont M
• Application Number:
  US11/392,763
• Publication Number:
  US 20070239431A1
• Time in Patent Office: 1,706 Days
• Field of Search: 704/1, 704/9, 704/10, 707 2- 6, 707706-708
• US Class Current: 704/9
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

A scalable two-pass scalable probabilistic latent semantic analysis (PLSA) methodology is disclosed that may perform more efficiently, and in some cases more accurately, than traditional PLSA, especially where large and/or sparse data sets are provided for analysis. The improved methodology can greatly reduce the storage and/or computational costs of training a PLSA model. In the first pass of the two-pass methodology, objects are clustered into groups, and PLSA is performed on the groups instead of the original individual objects. In the second pass, the conditional probability of a latent class, given an object, is obtained. This may be done by extending the training results of the first pass. During the second pass, the most likely latent classes for each object are identified.

Claims

1. A computer-readable medium storing computer-executable instructions for performing operations comprising:

clustering a set of data objects into a plurality of groups;

performing a first pass of performing probabilistic latent semantic analysis on the groups;

identifying a plurality of latent classes of the set of data objects;

calculating a first conditional probability of a data object of the set of data objects given a latent class of the plurality of latent classes;

estimating a ranking of each latent class;

eliminating low probability links between the set of data objects and the latent classes based on the rankings, the low probability links being determined based on a predetermined probability threshold;

determining remaining links between the set of data objects and the latent classes;

performing a second pass of probabilistic latent semantic analysis on a result of the first pass based on the remaining links between the set of data objects and the latent classes; and

calculating a second conditional probability of a data object of the set of data objects given the remaining links between the set of data objects and the latent classes.

2. The computer-readable medium of claim 1, wherein the set of data objects is a set of words in a plurality of documents.

3. The computer-readable medium of claim 2, wherein the clustering includes clustering the set of words into a plurality of groups of words and clustering the set of documents into a plurality of groups of documents.

4. The computer-readable medium of claim 1, further comprising determining probabilistic latent semantic analysis model parameters from results of the second pass.

5. The computer-readable medium of claim 1, wherein the estimating includes determining, for each of the latent classes, the ranking of that latent class given a respective one of the objects, according to the following calculation:

P(z|d)=P(d)<sup>−

1</sup>P(d|z)P(z)∝

P(d|z)P(z),

wherein z is the latent class and d is the respective given object.

6. A method of performing two-pass probabilistic latent semantic analysis, the method comprising:

receiving a set of data objects at an input of a computing device;

clustering the set of data objects into a plurality of groups;

performing a first pass of performing probabilistic latent semantic analysis on the groups;

estimating a ranking of each latent class;

eliminating low probability links between the set of data objects and the latent classes based on the rankings, the low probability links being determined based on a predetermined probability threshold;

determining remaining links between the set of data objects and the latent classes; and

performing a second pass of probabilistic latent semantic analysis, using a processor of the computing device, on a result of the first pass based on the remaining links between the set of data objects and the latent classes.

7. The method of claim 6, wherein the set of data objects is a set of words in a plurality of documents.

8. The method of claim 7, wherein the clustering includes clustering the set of words into a plurality of groups of words and clustering the set of documents into a plurality of groups of documents.

9. The method of claim 6, further including determining probabilistic latent semantic analysis model parameters from results of the second pass.

10. The method of claim 6, wherein the estimating the ranking includes determining, for each of the latent classes, the ranking of that latent class given a respective one of the objects, according to the following calculation:

P(z|d)=P(d)<sup>−

1</sup>P(d|z)P(z)∝

P(d|z)P(z),

wherein z is the latent class and d is the respective given object.