Generalized latent semantic analysis

• US 8,312,021 B2
• Filed: 09/16/2005
• Issued: 11/13/2012
• Est. Priority Date: 09/16/2005
• Status: Expired due to Fees

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Matveeva, Irina, Farahart, Ayman
• Primary Examiner(s): TIMBLIN, ROBERT M
• Application Number:
  US11/228,924
• Publication Number:
  US 20070067281A1
• Time in Patent Office: 2,615 Days
• Field of Search: 707 1- 5, 707/739, 707999001-999005
• US Class Current: 707/739
• 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 computer-implemented method for building an association tensor to facilitate document and word-level processing operations, the method comprising:

receiving, at a computer, a collection of reference documents containing textual information;

building, at the computer, the association tensor representing pair-wise similarities corresponding to a co-occurrence of term pairs in the collection of reference documents;

computing a lower-dimensional vector-space representation of terms that preserves the pair-wise similarities in the association tensor based on a singular value decomposition of the association tensor;

deriving a lower-dimensional vector-space representation of a document based on a weighted linear combination of computed term vectors in the lower-dimensional vector-space representation of the terms in the collection of reference documents; and

performing semantic analysis upon the collection of reference documents using the lower-dimensional vector-space representation of the document.

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

3. The method of claim 1, wherein the method further comprises using the lower-dimensional vector-space representation of the terms in the reference documents and a query 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.

4. The method of claim 1,

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

and

wherein building the association tensor involves using a search engine to query the collection of the reference documents to determine the pair-wise similarities.

5. A non-transitory 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 reference documents containing textual information;

building the association tensor representing pair-wise similarities corresponding to a co-occurrence of term pairs in the collection of reference documents;

computing a lower-dimensional vector-space representation of terms that preserves the pair-wise similarities in the association tensor based on a singular value decomposition of the association tensor;

deriving a lower-dimensional vector-space representation of a document based on a weighted linear combination of computed term vectors in the lower-dimensional vector-space representation of the terms in the collection of reference documents; and

performing semantic analysis upon the collection of reference documents using the lower-dimensional vector-space representation of the document.

6. The non-transitory computer-readable storage medium of claim 5,

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.

7. The non-transitory computer-readable storage device of claim 5, wherein the method further comprises using the lower-dimensional vector-space representation of the terms in the reference documents and a query 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 non-transitory computer-readable storage medium of claim 5,

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

and

wherein building the association tensor involves using a search engine to query the reference document collection to determine the pair-wise similarities.

9. An apparatus, implemented on a computer system, that builds an association tensor to facilitate document and word-level processing operations, comprising:

a processor;

a memory;

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

an association-tensor-building mechanism configured to build the association tensor representing pair-wise similarities corresponding to a co-occurrence of term pairs in the collection of reference documents;

a lower-dimensionality-association-tensor computing mechanism configured to compute a lower-dimensional vector-space representation of terms that preserves the pair-wise similarities in the association tensor based on a singular value decomposition of the association tensor;

a lower-dimensionality-matrix-deriving mechanism configured to derive a lower-dimensional vector-space representation of a document based on a weighted linear combination of computed term vectors in the lower-dimensional vector-space representation of the terms in the collection of reference documents; and

a performing mechanism configured to perform semantic analysis upon the collection of reference documents using the lower-dimensional vector-space representation of the document.

10. The apparatus of claim 9,

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

and

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

11. The apparatus of claim 9, wherein the apparatus is further configured to use the lower-dimensional vector-space representation of the terms in the reference documents and a query 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.

12. The apparatus of claim 9,

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

and

wherein while building the association tensor, the tensor-building mechanism is configured to use a search engine to query the collection of the reference documents to determine the pair-wise similarities.