Evaluating distinctiveness of document

• US 20040006736A1
• Filed: 06/13/2003
• Published: 01/08/2004
• Est. Priority Date: 07/04/2002
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Kawatani, Takahiko
• Granted Patent: US 7,200,802 B2
• Time in Patent Office: Days
• US Class Current: 715/500
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 18/2132 based on discrimination criteria, e.g. discriminant analysis

Abstract

Two document sets are compared in natural language processing and the distinctiveness of each constituent element (such as a sentence, term or phrase) of one document set is evaluated by dividing both the target and comparison documents into document segments, constructing the sentence vector of each document segment whose components are the occurring frequencies of terms occurring in the document segment, and projecting all the sentence vectors of both the documents on a projection axis to find a projection axis which maximizes a ratio equal to: (squared sum of projected values originating from the target document)/(squared sum of projected values originating from the comparison document). Projected values are obtained by projecting the sentence vectors on the projection axis, and the degrees of distinctiveness of the individual sentences of the target document are calculated on the basis of the projected values.

Claims

1. A method of evaluating a degree of distinctiveness of each document segment contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, and identifying a distinctive document segment, the method comprising:

(a) identifying a respective document segment vector for each document segment contained in the comparison document and the target document, each document segment vector having component values associated with occurring frequencies of terms occurring in its respective document segment;

(b) computing squared sum matrices respectively corresponding to the comparison document and the target document, from said document segment vectors;

(c) computing a predetermined number of orders of topic difference factor vectors of the target document from said squared sum matrices corresponding to the comparison document and the target document;

(d) computing respective degrees of distinctiveness of said respective orders and a total degree of distinctiveness for each document segment of the target document, from said corresponding document segment vector and said topic difference factor vectors of said respective orders; and

(e) identifying a distinctive document segment in the target document, on the basis of the degrees of distinctiveness of said respective orders or on the basis of the total degree of distinctiveness thereof.

2. The method of claim 1, further comprising:

computing the squared sum matrix of the target document by defining J as a larger one of the numbers of types of terms occurring in the target document and the comparison document, and defining M as the number of document segments in the target document, and defining a kth document segment vector to be d_k=(d_kl, . . . , d_kj)^T (k=1, . . . , M) where T denotes a transposition of the vector, and d_kj denotes a value associated with the occurring frequency of a jth term occurring in said document segment, and computing the squared sum matrix of the target document in accordance with the following equation;

$S_D=\underset{k=1}{\overset{M}{\sum <br><br>}}<br><br>d_k<br><br>d_k^T,\mathrm{and}$

computing the squared sum matrix of the comparison document by defining N as the number of document segments in the comparison document, and defining an nth document segment vector to be t_k=(t_kl, . . . , t_kJ)^T (k=1, . . . , N) where T denotes a transposition of the vector, and t_kj denotes the value associated with the occurring frequency of a jth term occurring in said document segment, and computing the squared sum matrix of the comparison document in accordance with the following equation;

$S_T=\underset{k=1}{\overset{N}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>t_k<br><br>t_k^T.$

3. The method of claim 2, further comprising computing an ith-order topic difference factor vector of the target document in accordance with an ith-order eigenvector α

_i of a generalized eigenvalue problem in accordance with the following equation;

S_Dα

=λ

S_Tα

.

4. The method of claim 1, further comprising computing the degree of distinctiveness of each order for each document segment of the target document by one of an absolute value or a squared value of an inner product between the corresponding document segment vector and the topic difference factor vector of each order, or by normalizing said degree of distinctiveness of each order for each document segment by a norm of said document segment vector, and computing said total degree of distinctiveness by adding a predetermined number of degrees of distinctiveness of the respective orders.

5. The method of claim 2, further comprising computing the degree of distinctiveness of each order for each document segment of the target document by one of an absolute value or a squared value of an inner product between the corresponding document segment vector and the topic difference factor vector of each order, or by normalizing said degree of distinctiveness of each order for each document segment by a norm of said document segment vector, and computing said total degree of distinctiveness by adding a predetermined number of the degrees of distinctiveness of the respective orders.

6. The method of claim 3, further comprising computing the degree of distinctiveness of each order for each document segment of the target document by one of an absolute value or a squared value of an inner product between the corresponding document segment vector and the topic difference factor vector of each order, or by normalizing said degree of distinctiveness of each order for each document segment by a norm of said document segment vector, and computing said total degree of distinctiveness by adding a predetermined number of degrees of distinctiveness of the respective orders.

7. A method of evaluating a degree of distinctiveness of each combination of terms contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, and identifying a distinctive combination of terms, the method comprising:

(a) identifying a respective document segment vector for each document segment contained in the comparison document and the target document, each document segment vector having component values associated with occurring frequencies of terms occurring in the document segment;

(b) computing squared sum matrices respectively corresponding to the comparison document and the target document, from the document segment vectors;

(c) computing a predetermined number of orders of topic difference factor vectors of the target document from the squared sum matrices corresponding to the comparison document and the target document;

(d) computing a term combination vector for each combinations of terms in the target document, each term combination vector having components corresponding to the terms contained in the combination of terms being given values determined by occurring numbers of said terms in said combination of terms, and having other components equal to “

0”

;

(e) computing degrees of distinctiveness of the respective orders and a total degree of distinctiveness for each combination of terms of the target document, from the corresponding term combination vector and the topic difference factor vectors of said respective orders; and

(f) identifying a combination of terms in the target document as being distinctive, on the basis of the degrees of distinctiveness of said respective orders or the total degree of distinctiveness thereof.

8. The method of claim 7, further comprising computing the degree of distinctiveness of each order for each combination of terms of said target document by one of an absolute value or a squared value of the inner product between the corresponding term combination vector and the topic difference factor vector of each order, or by normalizing said degree of distinctiveness of each order for each combination of terms by a norm of said term combination vector, and computing said total degree of distinctiveness by adding a predetermined number of degrees of distinctiveness of the respective orders.

9. A method of evaluating a degree of distinctiveness of each term contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, and identifying a distinctive term, the method comprising:

(a) identifying a respective document segment vector for each document segment contained in the comparison document and the target document, each document segment vector having component values associated with occurring frequencies of terms occurring in the document segment;

(b) computing squared sum matrices respectively corresponding to the comparison document and the target document, from the document segment vectors;

(c) computing a predetermined number of orders of topic difference factor vectors of the target document from the squared sum matrices respectively corresponding to the comparison document and the target document;

(d) computing values of inner products for each of said document segments of the target document and the comparison document, the values of inner products being calculated between the corresponding document segment vector and the topic difference factor vectors of the respective orders;

(e) computing degrees of distinctiveness of said respective orders and a total degree of distinctiveness for each term contained in the target document, on the basis of correlation coefficients between frequencies of each term in the respective document segments and the values of the inner products; and

(f) identifying a distinctive combination of terms in the target document, on the basis of the degrees of distinctiveness of said respective orders or the total degree of distinctiveness thereof.

10. The method of claim 9, further comprising:

computing the squared sum matrix of the target document by defining J as a larger one of the numbers of types of terms occurring in the target document and the comparison document, defining M as the number of document segments in the target document, and defining a kth document segment vector to be d_k=(d_kl, . . . , d_kJ)^T (k=1, . . . , M) where T denotes a transposition of the vector, and d_kj denotes the value associated with the occurring frequency of a jth term occurring in the document segment, and computing the squared sum matrix of the target document by the following equation;

$S_D=\underset{k=1}{\overset{M}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>d_k<br><br>d_k^T,\mathrm{and}$

computing the squared sum matrix of the comparison document by defining N as the number of document segments in said comparison document, and defining an nth document segment vector to be t_k=(t_kl, . . . , t_kJ)^T (k=1, . . . , N) where T denotes a transposition of the vector, and t_kj denotes the value associated with the occurring frequency of a jth term occurring in said document segment, and then computing the squared sum matrix of the comparison document by the following equation;

$S_T=\underset{k=1}{\overset{N}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>t_k<br><br>t_k^T.$

11. The method of claim 9, further comprising computing an ith-order topic difference factor vector of the target document in accordance with an ith-order eigenvector α

_i of a generalized eigenvalue in accordance with the following equation;

S_Dα

=λ

S_Tα

.

12. The method of claim 9, further comprising computing the degree of distinctiveness of each order for each term contained in the target document by one of an absolute value or a squared value of the correlation coefficients between the frequencies of each term in the respective document segments and the inner product values of the corresponding document segment vector and the topic difference factor vectors of the respective orders, and computing said total degree of distinctiveness by adding a predetermined number of degrees of distinctiveness of the respective orders.

13. The method of claim 10, further comprising computing the degree of distinctiveness of each order for each term contained in the target document by one of an absolute value or a squared value of the correlation coefficients between the frequencies of each term in the respective document segments and the inner product values of the corresponding document segment vector and the topic difference factor vectors of the respective orders, and computing said total degree of distinctiveness by adding a predetermined number of degrees of distinctiveness of the respective orders.

14. The method of claim 11, further comprising computing the degree of distinctiveness of each order for each term contained in the target document by one of an absolute value or a squared value of the correlation coefficients between the frequencies of each term in the respective document segments and the inner product values of the corresponding document segment vector and the topic difference factor vectors of the respective orders, and computing said total degree of distinctiveness by adding a predetermined number of degrees of distinctiveness of the respective orders.

15. A method of evaluating a degree of distinctiveness of each combination of terms contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, and identifying a distinctive combination of terms, the method comprising:

(a) identifying a respective document segment vector for each document segment contained in the comparison document and the target document, each document segment having component values associated with occurring frequencies of terms occurring in the document segment;

(b) computing squared sum matrices respectively corresponding to the comparison document and the target document, from the document segment vectors;

(c) computing a predetermined number of orders of topic difference factor vectors of the target document from the squared sum matrices respectively corresponding to the comparison document and the target document;

(d) computing values of inner products for each of said document segments of the target document and the comparison document, said values of inner products being calculated between the corresponding document segment vector and the topic difference factor vectors of the respective orders;

(e) computing degrees of distinctiveness of said respective orders and a total degree of distinctiveness for each combination of terms contained in the target document, on the basis of correlation coefficients between frequencies of each combination of terms in the respective document segments and the values of the inner products; and

(f) identifying a distinctive combination of terms in the target document, on the basis of the degrees of distinctiveness of said respective orders or the total degree of distinctiveness thereof.

16. The method of claim 15, further comprising computing the squared sum matrix of the target document by defining J as a larger one of the numbers of types of terms occurring in the target document and the comparison document, defining M as the number of document segments in the target document, and defining a kth document segment vector to be d_k=(d_kl, . . . , d_kl)^T (k=1, . . . , M) where T denotes a transposition of the vector, and d_kj denotes the value associated with the occurring frequency of a jth term occurring in said document segment, and then computing the squared sum matrix of the target document by the following equation:

17. The method of claim 16, further comprising computing an ith-order topic difference factor vector of the target document in accordance with an ith-order eigenvector α

_i of a generalized eigenvalue in accordance with the following equation;

S_Dα

=λ

S_Tα

.

18. The method of claim 15, further comprising computing the degree of distinctiveness of each order for each combination of terms contained in the target document by one of an absolute value or a squared value of the correlation coefficients between the frequencies of each combination of terms in the respective document segments and values of the inner products, and computing said total degree of distinctiveness by adding a predetermined number of degrees of distinctiveness of the respective orders.

19. The method of claim 16, further comprising computing the degree of distinctiveness of each order for each combination of terms contained in the target document by one of an absolute value or a squared value of the correlation coefficients between the frequencies of each combination of terms in the respective document segments and values of the inner products, and computing said total degree of distinctiveness by adding a predetermined number of degrees of distinctiveness of the respective orders.

20. The method of claim 17, further comprising computing the degree of distinctiveness of each order for each combination of terms contained in the target document by one of an absolute value or a squared value of the correlation coefficients between the frequencies of each combination of terms in the respective document segments and values of the inner products, and computing said total degree of distinctiveness by adding a predetermined number of degrees of distinctiveness of the respective orders.

21. A method of evaluating a degree of distinctiveness of each document segment contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, and identifying a distinctive document segment, the method comprising:

(a) identifying a respective document segment vector for each segment of the comparison document and the target document, each document segment vector having component values associated with occurring frequencies of terms occurring in the document segment;

(b) computing similarities of the document segment vector for each document segment of the target document, the similarities of the document segment vectors corresponding to the target document and the comparison document;

(c) computing a total degree of distinctiveness for each document segment of the target document, by using the similarities to the target document and the comparison document; and

(d) identifying a distinctive document segment in the target document, on the basis of the total degree of distinctiveness thereof.

22. The method of claim 21, further comprising computing the similarity between the document segment vector and the target document on the basis of a squared sum of inner products between said document segment vector and the respective segment vectors of the target document, and computing the similarity between said document segment vector and the comparison document on the basis of a squared sum of inner products between said document segment vector and the respective segment vectors of the comparison document.

23. The method of claim 21, further comprising computing the similarity between the document segment vector and the target document on the basis of inner products between said document segment vector and an average segment vector of the target document, and computing the similarity between said document segment vector and the comparison document on the basis of inner products between said document segment vector and an average segment vector of the comparison document.

24. The method of claim 21, further comprising computing the total degree of distinctiveness of the document segment by a ratio between the similarity to the target document and the similarity to the comparison document.

25. A method of evaluating a degree of distinctiveness of each term contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, and identifying a distinctive term, the method comprising:

(a) identifying a respective document segment vector for each document segment of the comparison document and the target document, the document segment vectors having component values associated with occurring frequencies of terms occurring in the document segment;

(b) computing similarities of the corresponding document segment vector for each document segment of the target document, the similarities of the corresponding document segment vectors corresponding to the target document and the comparison document;

(c) computing a total degree of distinctiveness for each document segment of the target document, by using the similarities to the target document and the comparison document;

(d) computing a total degree of distinctiveness for each document segment of the comparison document, by using said similarities to the target document and the comparison document;

(e) computing a total degree of distinctiveness for each of the terms contained in the target document, on the basis of correlation coefficients between frequencies of each term in the respective document segments of the target document and the comparison document and values of the total degrees of distinctiveness of the respective document segment vectors; and

(f) identifying a distinctive term in the target document, on the basis of the total degree of distinctiveness thereof.

26. A method of evaluating a degree of distinctiveness of each combination of terms contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, and identifying a distinctive combination of terms, the method comprising

(a) identifying a respective document segment vector for each document segment of the comparison document and the target document, said document segment vectors having component values associated with occurring frequencies of terms occurring in the document segment;

(b) computing similarities of the corresponding document segment vector for each of the document segments of the target document, the similarities of the corresponding document segment vectors corresponding to the target document and the comparison document;

(c) computing a total degree of distinctiveness for each document segment of the target document, by using the similarities to the target document and the comparison document;

(d) computing a degree of distinctiveness for each combination of terms contained in the target document, on the basis of correlation coefficients between frequencies of each combination of terms in the respective document segments and values of total degrees of distinctiveness of said respective document segments; and

(e) identifying a distinctive combination of terms in the target document, on the basis of the total degree of distinctiveness thereof.

27. The method of claim 26, further comprising computing the similarity between the document segment vector and the target document on the basis of a squared sum of inner products between said document segment vector and the respective segment vectors of the target document, and computing the similarity between said document segment vector and the comparison document on the basis of a squared sum of inner products between said document segment vector and the respective segment vectors of the comparison document.

28. The method of claim 26, further comprising, computing the similarity between the document segment vector and the target document on the basis of inner products between said document segment vector and an average segment vector of the target document, and computing the similarity between said document segment vector and the comparison document on the basis of inner products between said document segment vector and an average segment vector of the comparison document.

29. The method of claim 26, further comprising computing the total degree of distinctiveness of the document segment in accordance with a ratio of the similarity to the target document to the similarity to the comparison document.

30. A method of evaluating a degree of distinctiveness of each combination of terms contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, and identifying a distinctive combination of terms, the method comprising:

(a) identifying a respective document segment vector for each document segment of the comparison document and the target document, said document segment vectors having component values associated with occurring frequencies of terms occurring in the document segment;

(b) computing a term combination vector for each combination of terms in said target document, said term combination vectors having components corresponding to the terms contained in the combination of terms being given values determined by occurring numbers of said terms in said combination of terms, and having other components equal to “

0”

;

(c) computing similarities of the corresponding combination vector of terms for each combination of terms in the target document, the similarities of the corresponding combination vectors corresponding to the target document and the comparison document;

(d) computing a total degree of distinctiveness for each combination of terms in the target document, by using the similarities to the target document and the comparison document; and

(e) identifying a distinctive combination of terms in the target document, on the basis of the total degree of distinctiveness thereof.

31. The method of claim 30, further comprising computing the similarity between the term combination vector and the target document on the basis of a squared sum of inner products between said term combination vector and the respective segment vectors of the target document, and computing the similarity between said term combination vector and the comparison document on the basis of a squared sum of inner products between said term combination vector and the respective segment vectors of the comparison document.

32. The method of claim 30, further comprising computing the similarity between the term combination vector and the target document on the basis of inner products between said term combination vector and an average segment vector of the target document, and computing the similarity between said term combination vector and the comparison document on the basis of inner products between said term combination vector and an average segment vector of the comparison document.

33. The method of claim 30, further comprising computing the total degree of distinctiveness of the combination of terms by a ratio of the similarity to the target document to the similarity to the comparison document.

34. A method of evaluating a degree of distinctiveness of each document segment contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, the method comprising:

(a) identifying a respective document segment vector for each document segment contained in the comparison document and the target document, each document segment vector having component values associated with occurring frequencies of terms occurring in its respective document segment;

(b) computing squared sum matrices respectively corresponding to the comparison document and the target document, from said document segment vectors;

(c) computing a predetermined number of orders of topic difference factor vectors of the target document from said squared sum matrices corresponding to the comparison document and the target document; and

(d) computing respective degrees of distinctiveness of said respective orders and a total degree of distinctiveness for each document segment of the target document, from said corresponding document segment vector and said topic difference factor vectors of said respective orders.

35. A method of evaluating a degree of distinctiveness of each combination of terms contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, and identifying a distinctive combination of terms, the method comprising:

(a) identifying a respective document segment vector for each document segment contained in the comparison document and the target document, each document segment vector having component values associated with occurring frequencies of terms occurring in the document segment;

(b) computing squared sum matrices respectively corresponding to the comparison document and the target document, from the document segment vectors;

(c) computing a predetermined number of orders of topic difference factor vectors of the target document from the squared sum matrices corresponding to the comparison document and the target document;

(d) computing a term combination vector for each combinations of terms in the target document, each term combination vector having components corresponding to the terms contained in the combination of terms being given values determined by occurring numbers of said terms in said combination of terms, and having other components equal to “

0”

; and

(e) computing degrees of distinctiveness of the respective orders and a total degree of distinctiveness for each combination of terms of the target document, from the corresponding term combination vector and the topic difference factor vectors of said respective orders.

36. A method of evaluating a degree of distinctiveness of each term contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, the method comprising:

(a) identifying a respective document segment vector for each document segment contained in the comparison document and the target document, each document segment vector having component values associated with occurring frequencies of terms occurring in the document segment;

(b) computing squared sum matrices respectively corresponding to the comparison document and the target document, from the document segment vectors;

(c) computing a predetermined number of orders of topic difference factor vectors of the target document from the squared sum matrices respectively corresponding to the comparison document and the target document;

(d) computing values of inner products for each of said document segments of the target document and the comparison document, the values of inner products being calculated between the corresponding document segment vector and the topic difference factor vectors of the respective orders; and

(e) computing degrees of distinctiveness of said respective orders and a total degree of distinctiveness for each term contained in the target document, on the basis of correlation coefficients between frequencies of each term in the respective document segments and the values of the inner products.

37. A method of evaluating a degree of distinctiveness of each combination of terms contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, the method comprising:

(a) identifying a respective document segment vector for each document segment contained in the comparison document and the target document, each document segment having component values associated with occurring frequencies of terms occurring in the document segment;

(b) computing squared sum matrices respectively corresponding to the comparison document and the target document, from the document segment vectors;

(c) computing a predetermined number of orders of topic difference factor vectors of the target document from the squared sum matrices respectively corresponding to the comparison document and the target document;

(d) computing values of inner products for each of said document segments of the target document and the comparison document, said values of inner products being calculated between the corresponding document segment vector and the topic difference factor vectors of the respective orders; and

(e) computing degrees of distinctiveness of said respective orders and a total degree of distinctiveness for each combination of terms contained in the target document, on the basis of correlation coefficients between frequencies of each combination of terms in the respective document segments and the values of the inner products.

38. A method of evaluating a degree of distinctiveness of each document segment contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, the method comprising:

(a) identifying a respective document segment vector for each segment of the comparison document and the target document, each document segment vector having component values associated with occurring frequencies of terms occurring in the document segment;

(b) computing similarities of the document segment vector for each document segment of the target document, the similarities of the document segment vectors corresponding to the target document and the comparison document; and

(c) computing a total degree of distinctiveness for each document segment of the target document, by using the similarities to the target document and the comparison document.

39. A method of evaluating a degree of distinctiveness of each term contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, the method comprising:

(a) identifying a respective document segment vector for each document segment of the comparison document and the target document, the document segment vectors having component values associated with occurring frequencies of terms occurring in the document segment;

(b) computing similarities of the corresponding document segment vector for each document segment of the target document, the similarities of the corresponding document segment vectors corresponding to the target document and the comparison document;

(c) computing a total degree of distinctiveness for each document segment of the target document, by using the similarities to the target document and the comparison document;

(d) computing a total degree of distinctiveness for each document segment of the comparison document, by using said similarities to the target document and the comparison document; and

(e) computing a total degree of distinctiveness for each of the terms contained in the target document, on the basis of correlation coefficients between frequencies of each term in the respective document segments of the target document and the comparison document and values of the total degrees of distinctiveness of the respective document segment vectors.

40. A method of evaluating a degree of distinctiveness of each combination of terms contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, the method comprising:

(a) identifying a respective document segment vector for each document segment of the comparison document and the target document, said document segment vectors having component values associated with occurring frequencies of terms occurring in the document segment;

(b) computing similarities of the corresponding document segment vector for each of the document segments of the target document, the similarities of the corresponding document segment vectors corresponding to the target document and the comparison document;

(c) computing a total degree of distinctiveness for each document segment of the target document, by using the similarities to the target document and the comparison document; and

(d) computing a degree of distinctiveness for each combination of terms contained in the target document, on the basis of correlation coefficients between frequencies of each combination of terms in the respective document segments and values of total degrees of distinctiveness of said respective document segments.

41. A method of evaluating a degree of distinctiveness of each combination of terms contained in a target document including at least one document segment with respect to a comparison document including at least one document segment, the method comprising:

(a) identifying a respective document segment vector for each document segment of the comparison document and the target document, said document segment vectors having component values associated with occurring frequencies of terms occurring in the document segment;

(b) computing a term combination vector for each combination of terms in said target document, said term combination vectors having components corresponding to the terms contained in the combination of terms being given values determined by occurring numbers of said terms in said combination of terms, and having other components equal to “

0”

;

(c) computing similarities of the corresponding combination vector of terms for each combination of terms in the target document, the similarities of the corresponding combination vectors corresponding to the target document and the comparison document; and

(d) computing a total degree of distinctiveness for each combination of terms in the target document, by using the similarities to the target document and the comparison document.