System and method for identifying query-relevant keywords in documents with latent semantic analysis

• US 20060106767A1
• Filed: 11/12/2004
• Published: 05/18/2006
• Est. Priority Date: 11/12/2004
• Status: Active Grant

• Current Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation)
• Original Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation)
• Inventors: Girgensohn, Andreas, Cooper, Matthew, Wilcox, Lynn D., Adcock, John E.
• Granted Patent: US 7,440,947 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A system and method for identifying query-related keywords in documents found in a search using latent semantic analysis. The documents are represented as a document term matrix M containing one or more document term-weight vectors d, which may be term-frequency (tf) vectors or term-frequency inverse-document-frequency (tf-idf) vectors. This matrix is subjected to a truncated singular value decomposition. The resulting transform matrix U can be used to project a query term-weight vector q into the reduced N-dimensional space, followed by its expansion back into the full vector space using the inverse of U.

To perform a search, the similarity of q_expanded is measured relative to each candidate document vector in this space. Exemplary similarity functions are dot product and cosine similarity. Keywords are selected with the highest values in q_expanded that are also comprised in at least one document. Matching keywords from the query may be highlighted in the search results.

Claims

1. A method for identifying a set of query-relevant keywords comprised in one or more documents obtained from a query, wherein the query need not comprise the keywords, comprising:

a) creating a term-weight matrix M comprising one or more document term-weight vectors d, wherein each document term-weight vector d comprises information on the frequency in one of the one or more documents obtained from the terms in the query;

b) creating an expanded query term-weight vector q_expanded from the query term-weight vector q and the term-weight matrix M; and

c) using the expanded query term-weight vector q_expanded and the document term-weight vectors d, locating a set of keywords identified as terms related to the query and also comprised in at least one of the documents, wherein the query need not comprise the keywords.

2. The method of claim 1, wherein the document term-weight vectors d are term-frequency vectors.

3. The method of claim 1, wherein the document term-weight vectors d are term-frequency inverse-document frequency (tf-idf) vectors, whose nth component is computed as a function of a) the term-frequency in document d of the nth term and b) the fraction of the documents that comprise the nth term.

4. The method of claim 3, wherein the function is computed according to the equation tf-idf=(1.0+log(tf))*log(1/df), where tf is a term-frequency for the nth term in document d, and df is the fraction of the documents that comprises the nth term.

5. The method of claim 1, wherein the step of locating a set of keywords comprises selecting keywords comprised in at least one of the documents and having the highest values in the expanded query term-weight vector q_expanded.

6. The method of claim 1, wherein the step of locating a set of keywords comprises:

c1) computing for each document a term-by-term product of the expanded query term-weight vector q_expanded and the corresponding document term-weight vector d; and

c2) selecting keywords having the highest values in the computed product.

7. The method of claim 1, wherein creating the expanded query term-weight vector q_expanded comprises the following steps:

b1) projecting a query term-weight vector q corresponding to the query terms into latent semantic space, creating a reduced query term-weight vector q_reduced; and

b2) expanding the query term-weight vector back out of latent semantic space, creating the expanded query term-weight vector q_expanded.

8. The method of claim 7, wherein the step of projecting comprises:

b11) approximating the term-weight matrix M as a product of three matrices U S V′

, wherein S is a square diagonal matrix, U is a unitary transform matrix, and V is a unitary matrix.

9. The method of claim 8, wherein the step of projecting further comprises:

b12) creating a reduced query term-weight vector q_reduced=q′

*U.

10. The method of claim 8, wherein the step of expanding the query term-weight vector q comprises:

b21) creating the expanded query term-weight vector q_expanded according to the equation q_expanded=q_reduced*U′

=(q′

*U)*U′

.

11. The method of claim 7, wherein the step of expanding the query term-weight vector q comprises:

b21) computing each of n terms of q_expanded by computing a similarity function between a reduced query term-weight vector q_reduced and row n of the unitary transform matrix U.

12. The method of claim 11, wherein the similarity function is a cosine similarity function.

13. The method of claim 1, wherein creating an expanded query term-weight vector q_expanded comprises:

b1) approximating the term-weight matrix M as a product of three matrices U S V′

, wherein S is a square diagonal matrix, U is a unitary transform matrix, and V is a unitary matrix.

14. The method of claim 13, wherein creating an expanded query term-weight vector q_expanded further comprises:

b2) creating the expanded query term-weight vector q_expanded using a query term-weight vector q according to the equation q_expanded=U′

Uq.

15. The method of claim 1, further comprising the following step:

d) highlighting the keywords.

16. The method of claim 1, wherein the document is a text document.

17. The method of claim 1, wherein the document is text associated with a video segment.

18. A method for identifying a set of query-relevant keywords comprised in one or more documents obtained from a query, wherein the query need not comprise the keywords, comprising:

a) creating a term-weight matrix M comprising one or more document term-weight vectors d, wherein each document term-weight vector d comprises information on the frequency in one of the one or more documents obtained from the terms in the query;

b) projecting a query term-weight vector q corresponding to the query terms into latent semantic space, creating a reduced query term-weight vector q_reduced;

c) expanding the query term-weight vector back out of latent semantic space, creating the expanded query term-weight vector q_expanded; and

d) using the expanded query term-weight vector q_expanded and the document term-weight vectors d, locating a set of keywords identified as terms related to the query and also comprised in at least one of the documents, wherein the query need not comprise the keywords.

19. A method for identifying a set of query-relevant keywords comprised in one or more documents obtained from a query, wherein the query need not comprise the keywords, comprising:

a) creating a term-weight matrix M comprising one or more document term-weight vectors d, wherein each document term-weight vector d comprises information on the frequency in one of the one or more documents obtained from the terms in the query;

b) approximating the term-weight matrix M as a product of three matrices U S V′

, wherein S is a square diagonal matrix, U is a unitary transform matrix, and V is a unitary matrix;

c) expanding the query term-weight vector back out of latent semantic space, creating the expanded query term-weight vector q_expanded; and

d) using the expanded query term-weight vector q_expanded and the document term-weight vectors d, locating a set of keywords identified as terms related to the query and also comprised in at least one of the documents, wherein the query need not comprise the keywords.

20. In a computer, a method for identifying a set of query-relevant keywords comprised in one or more documents obtained from a query, wherein the query need not comprise the keywords, comprising:

a) receiving by the user a term-weight matrix M created by the computer and comprising one or more document term-weight vectors d, wherein each document term-weight vector d comprises information on the frequency in one of the one or more documents obtained from the terms in the query;

b) receiving by the user an expanded query term-weight vector q_expanded created by the computer from the from the query term-weight vector q and the term-weight matrix M; and

c) receiving by the user a set of keywords identified by the computer, using the expanded query term-weight vector q_expanded and the document term-weight vectors d, as terms related to the query and also comprised in at least one of the documents, wherein the query need not comprise the keywords.

21. In a computer, a method for identifying a set of query-relevant keywords comprised in one or more documents, wherein the query need not comprise the keywords, comprising:

a) receiving by the user a term-weight matrix M comprising information on the frequency in the one or more documents of terms in the selected query and approximated by the computer as a product of three matrices U S V′

, wherein S is a square diagonal matrix, U is a unitary transform matrix, and V is a unitary matrix;

b) receiving by the user an expanded query term-weight vector q_expanded created by the computer using a query term-weight vector q according to the equation q_expanded=U′

Uq; and

c) receiving by the user a set of keywords identified by the computer, using the expanded query term-weight vector q_expanded and the document term-weight vectors d, as terms related to the query and also comprised in at least one of the documents, wherein the query need not comprise the keywords.

22. A system for identifying a set of query-relevant keywords comprised in one or more selected documents, wherein the query need not comprise the keywords, comprising:

a) one or more processors capable of creating a term-weight matrix M comprising one or more document term-weight vectors d, wherein each document term-weight vector d comprises information on the frequency in one of the one or more documents obtained from the terms in the query;

capable of creating an expanded query term-weight vector q_expanded from the query term-weight vector q and the term-weight matrix M; and

capable of, using the expanded query term-weight vector q_expanded and the document term-weight vectors d, locating a set of keywords identified as terms related to the query and also comprised in at least one of the documents, wherein the query need not comprise the keywords; and

b) a machine readable medium including operations stored thereon that when processed by the one or more processors cause a system to perform the steps of creating a term-weight matrix M comprising one or more document term-weight vectors d, wherein each document term-weight vector d comprises information on the frequency in one of the one or more documents obtained from the terms in the query;

creating an expanded query term-weight vector q_expanded from the query term-weight vector q and the term-weight matrix M; and

, using the expanded query term-weight vector q_expanded and the document term-weight vectors d, locating a set of keywords identified as terms related to the query and also comprised in at least one of the documents, wherein the query need not comprise the keywords.

23. A program of instructions executable by a computer to perform a method for identifying a set of query-relevant keywords comprised in one or more selected documents, wherein the query need not comprise the keywords, comprising the steps of:

a) creating a term-weight matrix M comprising one or more document term-weight vectors d, wherein each document term-weight vector d comprises information on the frequency in one of the one or more documents obtained from the terms in the query;

b) creating an expanded query term-weight vector q_expanded from the query term-weight vector q and the term-weight matrix M; and

c) using the expanded query term-weight vector q_expanded and the document term-weight vectors d, locating a set of keywords identified as terms related to the query and also comprised in at least one of the documents, wherein the query need not comprise the keywords.

24. A system or apparatus for identifying a set of query-relevant keywords comprised in one or more selected documents, wherein the query need not comprise the keywords, comprising:

a) means for creating a term-weight matrix M comprising one or more document term-weight vectors d, wherein each document term-weight vector d comprises information on the frequency in the one or more documents of terms in the selected query;

b) means for creating an expanded query term-weight vector q_expanded from the query term-weight vector q and the term-weight matrix M; and

c) means for locating, using the expanded query term-weight vector q_expanded and the term-weight matrix M, a set of keywords identified as terms related to the query and also comprised in at least one of the documents, wherein the query need not comprise the keywords.