Domain dictionary creation by detection of new topic words using divergence value comparison

• US 8,386,240 B2
• Filed: 06/10/2011
• Issued: 02/26/2013
• Est. Priority Date: 08/23/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wu, Jun, Liu, Tang Xi, Hong, Feng, Wang, Yong-Gang, Yang, Bo, Zhang, Lei
• Primary Examiner(s): PULLIAS, JESSE SCOTT
• Application Number:
  US13/158,125
• Publication Number:
  US 20110238413A1
• Time in Patent Office: 627 Days
• Field of Search: None
• US Class Current: 704/10
• CPC Class Codes: G06F 40/258 Heading extraction; Automatic titling; Numbering

Abstract

Methods, systems, and apparatus, including computer program products, to identify topic words in a collection of documents that includes topic documents related to a topic are disclosed. A reference topic word divergence value based on a document collection and the topic document collection is determined. A candidate topic word divergence value for a candidate topic word is determined based on the document collection and the topic document collection. The candidate topic word is determined to be a topic word if the candidate topic word divergence value is greater than the reference topic word divergence value.

Claims

1. A computer-implemented method, comprising:

determining a topic divergence value, the topic divergence value proportional to a ratio of a first topic word distribution in a first collection of documents to a second topic word distribution in a second collection of documents, wherein the first collection of documents is a collection of topic documents related to a particular topic, and the second collection of documents is a collection of documents that includes other documents related to other topics;

determining a candidate topic word divergence value for a candidate topic word, the candidate topic word divergence value proportional to a ratio of a first distribution of the candidate topic word in the first collection of documents to a second distribution of the candidate topic word in the second collection of documents, wherein the candidate topic word is a candidate for being identified as a new topic word for the particular topic and is not a word in a topic dictionary for the particular topic; and

determining whether the candidate topic word is a new topic word for the particular topic based on the candidate topic word divergence value and the topic divergence value.

2. The method of claim 1, further comprising selecting an existing word in the topic dictionary for the particular topic as a topic word from which the topic divergence value is determined.

3. The method of claim 1, wherein determining a topic divergence value comprises:

selecting topic words for the particular topic;

determining a topic word divergence value for each of the topic words, each topic word divergence value proportional to a ratio of a first distribution of each topic word in the first collection of documents to a second distribution of each topic word in the second collection of documents; and

determining the topic divergence value based on a central tendency of the topic word divergence values.

4. The method of claim 1, wherein the first distribution of the candidate topic word in the first collection of documents is proportional to a ratio of a distribution of the candidate topic word in the first collection of documents to a value based on a logarithm of the distribution.

5. The method of claim 1, wherein determining whether the candidate topic word is a new topic word comprises determining the candidate topic word is a new topic word if the candidate topic word divergence value is greater than the topic divergence value.

6. The method of claim 1, further comprising storing the candidate topic word in the topic dictionary if the candidate topic word is determined to be a new topic word.

7. The method of claim 1, further comprising:

identifying documents in the second collection of documents related to topics;

generating document clusters related to the topics;

identifying words in each of the document clusters; and

selecting candidate topic words from the identified words in each of the document clusters.

8. The method of claim 1, further comprising:

determining first word frequencies for existing words and a candidate word in a training collection of documents, the candidate word defined by a sequence of constituent words, each constituent word being an existing word in a dictionary, and the training collection of documents comprising a first subset of the second collection of documents;

determining second word frequencies for the constituent words and the candidate word in a development collection of documents, the development collection of documents comprising a second subset of the second collection of documents;

determining a candidate word entropy measure based on the second word frequency of the candidate word and the first word frequencies of the constituent words and the candidate word;

determining an existing word entropy measure based on the second word frequencies of the constituent words and the first word frequencies of the constituent words and the candidate word; and

determining that the candidate word is a candidate topic word if the candidate word entropy measure exceeds the existing word entropy measure.

9. The method of claim 8, wherein:

determining first word frequencies for existing words and a candidate word in a training collection of documents comprises training a language model for probabilities of the existing words and the candidate words in the training collection of documents; and

wherein determining second word frequencies for the constituent words and the candidate word in a development collection of documents comprises determining a word count value for each of the constituent words and the candidate word in the development collection of documents.

10. The method of claim 9, wherein:

determining a candidate word entropy measure based on the second word frequency of the candidate word and the first word frequencies of the constituent words and the candidate word comprises;

determining a first logarithmic value based on the probabilities of the candidate word and the constituent words; and

determining the candidate word entropy measure based on the word count value of the candidate word and the first logarithmic value; and

determining an existing word entropy measure based on the second word frequencies of the constituent words and the first word frequencies of the constituent words and the candidate word comprises;

determining second logarithmic values based on the probabilities of the candidate word and the constituent words; and

determining the existing word entropy measure based on the word counts of the constituent words and the second logarithmic values.

11. The method of claim 1, wherein the candidate topic word comprises one or more Hanzi characters.

12. The method of claim 1, wherein the second collection of documents also includes documents related to the particular topic.

13. A computer-implemented method, comprising:

selecting a topic dictionary comprising topic words related to a particular topic;

determining a topic word divergence value based on a topic word, a second collection of documents and a first collection of documents, wherein the first collection of documents is a collection of topic documents related to the particular topic, and the second collection of documents is a collection of documents that includes documents related to a plurality of topics, and the topic word is a word that is related to the topic;

determining a candidate topic word divergence value for a candidate topic word based on the second collection of documents and the first collection of documents, wherein the candidate topic word is a candidate for being identified as a new topic word for the particular topic and is not a word in the topic dictionary for the particular topic; and

determining whether the candidate topic word is a new topic word for the particular topic based on the candidate topic word divergence value and the topic word divergence value.

14. The method of claim 13, further comprising storing the candidate topic word in the topic dictionary if the candidate topic word is determined to be a new topic word for the particular topic.

15. The method of claim 13, wherein determining a topic word divergence value comprises:

selecting existing topic words in the topic dictionary;

determining an existing topic word divergence values for each of the topic words based on the second collection of documents and the first collection of documents; and

determining the topic word divergence value based on a central tendency of the existing topic word divergence values.

16. The method of claim 13, wherein determining a candidate topic word divergence value for the candidate topic word based on the second collection of documents and the first collection of documents comprises:

determining a first probability associated with the candidate topic word in the first collection of documents;

determining a second probability associated with the candidate topic word in the second collection of documents; and

calculating the candidate topic word divergence value based on a ratio of the first probability to the product of the second probability and value based on a logarithm on the first probability.

17. The method of claim 13, wherein the candidate topic word comprises one or more Hanzi characters.

18. An apparatus comprising software stored in a non-transitory computer readable medium, the software comprising computer readable instructions executable by a computer processing device and that upon such execution cause the computer processing device to:

determine a topic word divergence value based on a topic word, a second collection of documents and a first collection of documents, wherein the first collection of documents is a collection of topic documents related to a particular topic, and the second collection of documents is a collection of documents that includes the topic documents and other documents that are related to a plurality of topics, and the topic word is a word that is in a topic dictionary that is related to the particular topic;

determine a candidate topic word divergence value for a candidate topic word based on the second collection of documents and the first collection of documents, wherein the candidate topic word is a candidate for being identified as a new topic word for the particular topic and is not a word in the topic dictionary for the particular topic;

determine whether the candidate topic word is a topic word for the particular topic based on the candidate topic word divergence value and the topic word divergence value; and

store the candidate topic word in the topic dictionary if the candidate topic word is determined to be a topic word.

19. A system, comprising:

a data store storing a topic dictionary comprising topic words related to a topic;

a topic word processing module configured to;

determine a topic word divergence value based on a topic word, a second collection of documents and a first collection of documents, wherein the first collection of documents is a collection of topic documents related to a topic, the second collection of documents is a collection of documents that includes documents related to a plurality of topics, and the topic word is a word in a topic dictionary that is related to the topic;

select a candidate topic word that is not a word in the topic dictionary;

determine a candidate topic word divergence value for the candidate topic word based on the second collection of documents and the first collection of documents; and

determine whether the candidate topic word is a topic word for the particular topic based on the candidate topic word divergence value and the topic word divergence value; and

a dictionary updater module configured to store the candidate topic word in the topic dictionary if the candidate topic word is determined to be a topic word.

20. The system of claim 19, wherein the topic word processing module is configured to:

determine a first probability associated with the candidate topic word in the first collection of documents;

determine a second probability associated with the candidate topic word in the second collection of documents; and

calculate the candidate topic word divergence value based on a ratio of the first probability to the product of the second probability and a logarithmic value based on the first probability.

21. A method, comprising:

determining a divergence threshold for a first collection of documents, the divergence threshold proportional to the ratio of a first topic word probability for a topic word in the first collection of documents to a second topic word probability for the topic word in the second collection of documents, wherein the first collection of documents is a first collection of topic documents related to a topic, the topic word is a word in a topic dictionary related to the topic, and the second collection of documents is a collection of documents related to a plurality of topics;

determining a candidate word divergence value for a candidate word that is not a word in the topic dictionary, the candidate word divergence value proportional to the ratio of a first candidate word probability for the candidate word with reference to the first collection of documents to a second candidate word probability for the candidate word with reference to the second collection of documents; and

determining that the candidate word is a topic word for the topic if the candidate word divergence value exceeds the divergence threshold.

22. A system, comprising:

means for determining a topic divergence value, the topic divergence value proportional to a ratio of a first topic word distribution in a first collection of documents to a second topic word distribution in a second collection of documents, wherein the first collection of documents is a collection of topic documents related to a particular topic, and the second collection of documents is a collection of documents that includes documents related to a plurality of topics;

means for determining a candidate topic word divergence value for a candidate topic word, the candidate topic word divergence value proportional to a ratio of a first distribution of the candidate topic word in the first collection of documents to a second distribution of the candidate topic word in the second collection of documents, wherein the candidate top word is a candidate for being identified as a new topic word for the particular topic and is not a word in a topic dictionary for the particular topic; and

means for determining whether the candidate topic word is a new topic word for the topic based on the candidate topic word divergence value and the topic divergence value.

23. A system, comprising:

means for selecting a topic dictionary comprising topic words related to a topic;

means for determining a topic word divergence value based on a topic word, a second collection of documents and a first collection of documents, wherein the first collection of documents is a collection of topic documents related to a particular topic, and the second collection of documents is a collection of documents that includes documents related to a plurality of topics, and the topic word is a word that is in the topic dictionary;

means for determining a candidate topic word divergence value for a candidate topic word based on the second collection of documents and the first collection of documents, wherein the candidate topic word is a candidate for being identified as a new topic word for the particular topic and is not a word in a topic dictionary for the topic; and

means for determining whether the candidate topic word is a new topic word for the topic based on the candidate topic word divergence value and the topic word divergence value.

24. A computer processing device comprising:

means for determining a topic word divergence value based on a topic word, a second collection of documents and a first collection of documents, wherein the first collection of documents is a collection of topic documents related to a topic, and the second collection of documents is a collection of documents that includes documents related to a plurality of topics, and the topic word is a word that is in a topic dictionary that is related to the topic;

means for determining a candidate topic word divergence value for a candidate topic word based on the second collection of documents and the first collection of documents, wherein the candidate topic word is not a word in the topic dictionary;

means for determining whether the candidate topic word is a topic word based on the candidate topic word divergence value and the topic word divergence value; and

means for storing the candidate topic word in the topic dictionary if the candidate topic word is determined to be a topic word.

25. A system, comprising:

means for determining a divergence threshold for a first collection of documents, the divergence threshold proportional to the ratio of a first topic word probability for a topic word in the first collection of documents to a second topic word probability for the topic word in the second collection of documents, wherein the first collection of documents is a collection of topic documents related to a topic, the topic word is a word in a topic dictionary related to the topic, and the second collection of documents is a collection of documents that includes documents related to a plurality of topics;

means for determining a candidate word divergence value for a candidate word that is a candidate for being identified as a new topic word for the particular topic and that is not a word in the topic dictionary for the topic, the candidate word divergence value proportional to the ratio of a first candidate word probability for the candidate word with reference to the first collection of documents to a second candidate word probability for the candidate word with reference to the second collection of documents; and

means for determining that the candidate word is a topic word for the topic if the candidate word divergence value exceeds the divergence threshold.