Domain Dictionary Creation

• US 20090055381A1
• Filed: 08/23/2007
• Published: 02/26/2009
• Est. Priority Date: 08/23/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wang, Yonggang, Liu, Tang Xi, Yang, Bo, Wu, Jun, Zhang, Lei, Hong, Feng
• Granted Patent: US 7,983,902 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 document corpus that includes topic documents related to a topic are disclosed. A reference topic word divergence value based on the document corpus and the topic document corpus is determined. A candidate topic word divergence value for a candidate topic word is determined based on the document corpus and the topic document corpus. 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 substantially proportional to a ratio of a first topic word distribution in a topic document corpus to a second topic word distribution in a document corpus, wherein the topic document corpus is a corpus of topic documents related to a topic, and the document corpus is a corpus of documents that includes the topic documents and other documents;

determining a candidate topic word divergence value for a candidate topic word, the candidate topic word divergence value substantially proportional to a ratio of a first distribution of the candidate topic Word in the topic document corpus to a second distribution of the candidate topic word in the document corpus; and

determining whether the candidate topic word is a new topic word 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 a topic dictionary related to the topic as the topic word.

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

selecting topic words;

determining a topic word divergence value for each of the topic words, each topic word divergence value substantially proportional to a ratio of a first distribution of each topic word in the topic document corpus to a second distribution of each topic word in the document corpus; 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 topic document corpus is proportional to a ratio of a distribution of the candidate topic word in the topic document corpus 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 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 a 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 document corpus 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 corpus, the candidate word defined by a sequence of constituent words, each constituent word being an existing word in a dictionary, and the training corpus comprising a first subset of the document corpus;

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

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 corpus comprises training a language model for probabilities of the existing words and the candidate words in the training corpus; and

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

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. A computer-implemented method, comprising:

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

determining a topic word divergence value based on a topic word, a document corpus and a topic document corpus, wherein the topic document corpus is a corpus of topic documents related to a topic, and the document corpus is a corpus of documents that includes the topic documents and other documents, 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 document corpus and the topic document corpus; and

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

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

14. The method of claim 12, 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 document corpus and the topic document corpus; and

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

15. The method of claim 12, wherein determining a candidate topic word divergence value for the candidate topic word based on the document corpus and the topic document corpus comprises:

determining a first probability associated with the candidate topic word in the topic document corpus;

determining a second probability associated with the candidate topic word in the document corpus; 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.

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

17. An apparatus comprising software stored in a 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 document corpus and a topic document corpus, wherein the topic document corpus is a corpus of topic documents related to a topic, and the document corpus is a corpus of documents that includes the topic documents and other documents, and the topic word is a word that in a topic dictionary that is related to the topic;

determine a candidate topic word divergence value for a candidate topic word based on the document corpus and the topic document corpus;

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

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

18. 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 document corpus and a topic document corpus, wherein the topic document corpus is a corpus of topic documents related to a topic, the document corpus is a corpus of documents that includes the topic documents and other documents, and the topic word is a word in a topic dictionary that is related to the topic;

select a candidate topic word;

determine a candidate topic word divergence value for the candidate topic word based on the document corpus and the topic document corpus; and

determine whether the candidate topic word is a topic word 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

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

determine a first probability associated with the candidate topic word in the topic document corpus;

determine a second probability associated with the candidate topic word in the document corpus; 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.

20. A method, comprising:

determining a divergence threshold for a topic document corpus, the divergence threshold proportional to the ratio of a first topic word probability for a topic word in the topic document corpus to a second topic word probability for the topic word in the document corpus, wherein the topic document corpus is a corpus of topic documents related to a topic, the topic word is a word in a topic dictionary related to the topic, and the document corpus is a corpus of documents that includes the topic documents and other documents;

determining a candidate word divergence value for a candidate word, the candidate word divergence value proportional to the ratio of a first candidate word probability for the candidate word with reference to the topic document corpus to a second candidate word probability for the candidate word with reference to the document corpus; and

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

21. A system, comprising:

means for determining a topic divergence value, the topic divergence value substantially proportional to a ratio of a first topic word distribution in a topic document corpus to a second topic word distribution in a document corpus, wherein the topic document corpus is a corpus of topic documents related to a topic, and the document corpus is a corpus of documents that includes the topic documents and other documents;

means for determining a candidate topic word divergence value for a candidate topic word, the candidate topic word divergence value substantially proportional to a ratio of a first distribution of the candidate topic word in the topic document corpus to a second distribution of the candidate topic word in the document corpus; and

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

22. 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 document corpus and a topic document corpus, wherein the topic document corpus is a corpus of topic documents related to a topic, and the document corpus is a corpus of documents that includes the topic documents and other documents, and the topic word is a word that is related to the topic;

means for determining a candidate topic word divergence value for a candidate topic word based on the document corpus and the topic document corpus; and

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

23. An computer processing device comprising:

means for determining a topic word divergence value based on a topic word, a document corpus and a topic document corpus, wherein the topic document corpus is a corpus of topic documents related to a topic, and the document corpus is a corpus of documents that includes the topic documents and other documents, and the topic word is a word that 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 document corpus and the topic document corpus;

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 a topic dictionary if the candidate topic word is determined to be a topic word.

24. A system, comprising:

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

means for determining a candidate word divergence value for a candidate word, the candidate word divergence value proportional to the ratio of a first candidate word probability for the candidate word with reference to the topic document corpus to a second candidate word probability for the candidate word with reference to the document corpus; 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.