Generalized latent semantic analysis

• US 20070067281A1
• Filed: 09/16/2005
• Published: 03/22/2007
• Est. Priority Date: 09/16/2005
• Status: Active Grant

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Matveeva, Irina, Farahat, Aymann
• Granted Patent: US 8,312,021 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 40/216 using statistical methods

Abstract

One embodiment of the present invention provides a system that builds an association tensor (such as a matrix) to facilitate document and word-level processing operations. During operation, the system uses terms from a collection of documents to build an association tensor, which contains values representing pair-wise similarities between terms in the collection of documents. During this process, if a given value in the association tensor is calculated based on an insufficient number of samples, the system determines a corresponding value from a reference document collection, and then substitutes the corresponding value for the given value in the association tensor. After the association tensor is obtained, a dimensionality reduction method is applied to compute a low-dimensional vector space representation for the vocabulary terms. Document vectors are computed as linear combinations of term vectors.

Claims

1. A method for building an association tensor to facilitate document and word-level processing operations, comprising:

receiving a collection of documents containing textual information;

using terms from the collection of documents to build the association tensor, which contains values representing pair-wise similarities between terms in the collection of documents; and

wherein if a given value for a pair-wise similarity is calculated based on an insufficient number of samples, the method further comprises,

determining a corresponding value for the pair-wise similarity from a reference document collection, and

substituting the corresponding value for the given value into the association tensor.

2. The method of claim 1, wherein building the association tensor involves using statistical association measures or corpus-derived measures of association to represent similarities between terms.

3. The method of claim 1,

wherein building the association tensor involves computing confidence values for each value in the association tensor;

and

wherein the method further comprises retaining values in the association tensor if corresponding confidence values are greater than a pre-determined threshold.

4. The method of claim 1, further comprising performing a dimensionality-reduction operation on the association tensor to reduce the dimensionality of the association tensor.

5. The method of claim 1, wherein performing the dimensionality-reduction operation can involve using:

the isometric mapping (ISOMAP) method;

the local linear embedding (LLE) method;

the Laplacian Eigenmaps embedding method;

multidimensional scaling techniques;

or

singular-value decomposition techniques.

6. The method of claim 1, wherein after the association tensor is computed, the association tensor is used to compute a vector-space representation for the documents and/or queries by:

computing a vector-space representation for individual terms in the documents and/or queries; and

computing a weighted linear combination of the vectors for the individual terms to form vectors which represent the documents and/or queries.

7. The method of claim 6, wherein the method further comprises using the computed vectors for the documents and/or queries to perform:

a clustering operation;

an information-retrieval operation;

a text segmentation operation;

a text-translation operation;

a cognitive-modeling operation;

a synonym-detection operation;

or

a related-term-identification operation.

8. The method of claim 1,

wherein the reference document collection is the World Wide Web (or a proprietary document collection);

and

wherein determining the corresponding value for the pair-wise similarity in the reference document collection involves using a search engine to query the World Wide Web (or the proprietary document collection) to determine the corresponding value for the pair-wise similarity.

9. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for building an association tensor to facilitate document and word-level processing operations, the method comprising:

receiving a collection of documents containing textual information;

using terms from the collection of documents to build the association tensor, which contains values representing pair-wise similarities between terms in the collection of documents; and

wherein if a given value for a pair-wise similarity is calculated based on an insufficient number of samples, the method further comprises,

determining a corresponding value for the pair-wise similarity from a reference document collection, and

substituting the corresponding value for the given value into the association tensor.

10. The computer-readable storage medium of claim 9, wherein building the association tensor involves using statistical association measures or corpus-derived measures of association to represent similarities between terms.

11. The computer-readable storage medium of claim 9,

wherein building the association tensor involves computing confidence values for each value in the association tensor;

and

wherein the method further comprises retaining values in the association tensor if corresponding confidence values are greater than a pre-determined threshold.

12. The computer-readable storage medium of claim 9, wherein the method further comprises performing a dimensionality-reduction operation on the association tensor to reduce the dimensionality of the association tensor.

13. The computer-readable storage medium of claim 9, wherein performing the dimensionality-reduction operation can involve using:

the isometric mapping (ISOMAP) method;

the local linear embedding (LLE) method;

the Laplacian Eigenmaps embedding method;

multidimensional scaling techniques;

or

singular-value decomposition techniques.

14. The computer-readable storage medium of claim 9, wherein after the association tensor is computed, the association tensor is used to compute a vector-space representation for the documents and/or queries by:

computing a vector-space representation for individual terms in the documents and/or queries; and

computing a weighted linear combination of the vectors for the individual terms to form vectors which represent the documents and/or queries.

15. The computer-readable storage medium of claim 14, wherein the method further comprises using the computed vectors for the documents and/or queries to perform:

a clustering operation;

an information-retrieval operation;

a text segmentation operation;

a text-translation operation;

a cognitive-modeling operation;

a synonym-detection operation;

or

a related-term-identification operation.

16. The computer-readable storage medium of claim 9,

wherein the reference document collection is the World Wide Web (or a proprietary document collection);

and

wherein determining the corresponding value for the pair-wise similarity in the reference document collection involves using a search engine to query the World Wide Web (or the proprietary document collection) to determine the corresponding value for the pair-wise similarity.

17. An apparatus that builds an association tensor to facilitate document and word-level processing operations, comprising:

an receiving mechanism configured to receive a collection of documents containing textual information;

an tensor-building mechanism configured to use terms from the collection of documents to build the association tensor, which contains values representing pair-wise similarities between terms in the collection of documents; and

wherein if a given value for a pair-wise similarity is calculated based on an insufficient number of samples, the tensor-building mechanism is configured to,

determine a corresponding value for the pair-wise similarity from a reference document collection, and to

substitute the corresponding value for the given value into the association tensor.

18. The apparatus of claim 17, wherein while building the association tensor, the tensor-building mechanism is configured to use statistical association measures or corpus-derived measures of association to represent similarities between terms.

19. The apparatus of claim 17,

wherein while building the association tensor, the tensor-building mechanism is configured to compute confidence values for each value in the association tensor;

and

wherein the tensor-building mechanism is further configured to retain values in the association tensor if corresponding confidence values are greater than a pre-determined threshold.

20. The apparatus of claim 17, wherein the tensor-building mechanism is further configured to perform a dimensionality-reduction operation on the association tensor to reduce the dimensionality of the association tensor.

21. The apparatus of claim 17, wherein while performing the dimensionality-reduction operation, the tensor-building mechanism is configured to use:

the isometric mapping (ISOMAP) method;

the local linear embedding (LLE) method;

the Laplacian Eigenmaps embedding method;

multidimensional scaling techniques;

or

singular-value decomposition techniques.

22. The apparatus of claim 17, wherein after the association tensor is computed, the apparatus is further configured to use the association tensor to compute a vector-space representation for the documents and/or queries by:

computing a vector-space representation for individual terms in the documents and/or queries; and

computing a weighted linear combination of the vectors for the individual terms to form vectors which represent the documents and/or queries.

23. The apparatus of claim 22, wherein the apparatus is further configured to use the computed vectors for the documents and/or queries to perform:

a clustering operation;

an information-retrieval operation;

a text segmentation operation;

a text-translation operation;

a cognitive-modeling operation;

a synonym-detection operation;

or

a related-term-identification operation.

24. The apparatus of claim 17,

wherein the reference document collection is the World Wide Web (or a proprietary document collection);

and

wherein while determining the corresponding value for the pair-wise similarity in the reference document collection, the tensor-building mechanism is configured to use a search engine to query the World Wide Web (or the proprietary document collection) to determine the corresponding value for the pair-wise similarity.