Category-sensitive ranking for text

• US 9,092,422 B2
• Filed: 12/30/2009
• Issued: 07/28/2015
• Est. Priority Date: 12/30/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wang, Yi, Tao, Bo, Liu, Zhiyuan
• Primary Examiner(s): BOWEN, RICHARD L
• Application Number:
  US13/520,012
• Publication Number:
  US 20120278332A1
• Time in Patent Office: 2,036 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/345 Summarisation for human users
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

Provided are methods, systems and apparatus which include computer program products, for generating topic models for text summarization In one aspect, a method includes receiving a first document of text that is associated with one or more category labels and that includes one or more sequences of one or more words, determining a category label that represents a first category associated with the first document, sampling the one or more sequences to determine a topic and a co-occurrence relationship between the topic and the category label, where a topic represents a subdivision within a category, sampling the one or more sequences to determine a co-occurrence relationship between a sequence in the first document and the topic, and generating a category-topic model that represents the co-occurrence relationships.

Claims

1. A method comprising:

receiving a plurality of documents of text, wherein each document is associated with one or more category labels and includes one or more sequences of one or more words;

determining a plurality of topics from the plurality of documents, wherein each topic represents a subdivision of a respective category label;

performing a plurality of sampling iterations to generate a category-topic model that represents co-occurrence relationships between sequences and topics and co-occurrence relationships between topics and categories, wherein performing each of the plurality of sampling iterations comprises, for each sequence in each of the plurality of documents;

sampling a category label for the sequence from the category labels associated with the document that includes the sequence;

sampling a topic for the sequence; and

updating current values of representations of the co-occurrence relationships based on the category label and the topic sampled for the sequence.

2. The method of claim 1, where generating a category-topic model further includes:

determining, from the co-occurrence relationship between the topic and the category label, a first probability of the topic being associated with a document given that the category label is associated with the document; and

determining, from a co-occurrence relationship between the sequence and the topic, a second probability of the sequence occurring in the document given that the topic is associated with the document.

3. The method of claim 2, where sampling the category label and the topic comprises sampling the category label and the topic from a distribution that satisfies:

4. The method of claim 3, wherein performing the plurality of sampling iterations comprises performing a respective portion of the sampling independently on each of multiple processors, and wherein each processor p calculates an update Δ

C_|p^WT and an update Δ

C_|p^TC, and C_k,c ^TC and C_v,k^WT are updated according to the expressions

5. The method of claim 3, where the determining the first and second probabilities includes:

calculating the conditional probabilities that the topic is k given that the category label is c, the sequence is v given that the topic is k, the category label is c given that the topic is k, and the topic is k given that the sequence is v.

6. The method of claim 5, where the conditional probabilities satisfy the expressions:

7. The method of claim 1, further comprising:

receiving a textual input;

determining in the textual input one or more sequences of one or more words that are each associated with a respective category;

ranking each of the sequences using the category-topic model;

identifying one or more of the determined sequences that have a ranking greater than a threshold ranking value; and

generating a summary of the textual input that includes the identified sequences.

8. The method of claim 7, where the ranking includes calculating a probabilistic characteristic value for each sequence of one or more words, where the probabilistic characteristic value is expressed as:

9. The method of claim 1, where the category labels are human-readable.

10. The method of claim 1, where at least one of the topics is not human-readable.

11. The method of claim 1, where a sequence of one or more words is a phrase, sentence, or paragraph.

12. The method of claim 1, further comprising:

determining that a first document of the plurality of documents is not associated with any category labels; and

assigning a unique label to the first document.

13. A system comprising:

one or more computer-readable storage devices including computer program instructions; and

one or more computers operable to execute to execute the instructions to perform operations comprising;

receiving a plurality of documents of text, wherein each document is associated with one or more category labels and includes one or more sequences of one or more words;

determining a plurality of topics from the plurality of documents, wherein each topic represents a subdivision of a respective category label;

performing a plurality of sampling iterations to generate a category-topic model that represents co-occurrence relationships between sequences and topics and co-occurrence relationships between topics and categories, wherein performing each of the plurality of sampling iterations comprises, for each sequence in each of the plurality of documents;

sampling a category label for the sequence from the category labels associated with the document that includes the sequence;

sampling a topic for the sequence; and

updating current values of representations of the co-occurrence relationships based on the category label and the topic sampled for the sequence.

14. The system of claim 13, where sampling the category label and the topic comprises sampling the category label and the topic from a distribution that satisfies:

15. The system of claim 14, wherein performing the plurality of sampling iterations comprises performing a respective portion of the sampling independently on each of multiple processors, and wherein each processor p calculates an update Δ

C_|p^WT and an update Δ

C_|p^TC , and C_TC^k,c and C_v,k^WT are updated according to the expressions

16. The system of claim 15, where conditional probabilities satisfy the expressions:

17. One or more non-transitory computer-readable storage media encoded with instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:

receiving a plurality of documents of text, wherein each document is associated with one or more category labels and includes one or more sequences of one or more words;

determining a plurality of topics from the plurality of documents, wherein each topic represents a subdivision of a respective category label;

performing a plurality of sampling iterations to generate a category-topic model that represents co-occurrence relationships between sequences and topics and co-occurrence relationships between topics and categories, wherein performing each of the plurality of sampling iterations comprises, for each sequence in each of the plurality of documents;

sampling a category label for the sequence from the category labels associated with the document that includes the sequence;

sampling a topic for the sequence; and

updating current values of representations of the co-occurrence relationships based on the category label and the topic sampled for the sequence.

18. The computer-readable storage media of claim 17, where sampling the category label and the topic comprises sampling the category label and the topic from a distribution that satisfies:

19. The computer-readable storage media of claim 18, wherein performing the plurality of sampling iterations comprises performing a respective portion of the sampling independently on each of multiple processors, and wherein each processor p calculates an update Δ

C_|p^WT and an update Δ

C_|p^TC, and C_k,c^TC and C_v,k^WT are updated according to the expressions

20. The computer-readable storage media of claim 19, where conditional probabilities satisfy the expressions: