Real time detection of topical changes and topic identification via likelihood based methods

• US 6,104,989 A
• Filed: 07/29/1998
• Issued: 08/15/2000
• Est. Priority Date: 07/29/1998
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Kanevsky, Dimitri, Yashchin, Emmanuel
• Primary Examiner(s): Thomas, Joseph
• Application Number:
  US09/124,075
• Time in Patent Office: 748 Days
• Field of Search: 704/1, 704/9, 704/10, 704/2, 704/8, 704/4, 704/5, 704/7, 704/257, 704/277, 707/530, 707/531, 707/532, 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/100, 707/101, 707/102, 707/103, 707/104, 707/500, 707/501, 434/156, 434/167, 434/169
• US Class Current: 704/9
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A method is disclosed for detecting topical changes and topic identification in texts in real time using likelihood ratio based methods. In accordance with the method, topic identification is achieved by evaluating text probabilities under each topic, and then selecting a new topic when one of those probabilities becomes significantly larger than the others. The method is usable to improve real time machine translation.

Claims

1. A method for real time identification of topics in text, comprising the steps of:

forming a battery of topics from training data;

detecting topic changes in said text, using said battery and a first threshold ratio;

identifying topics in said text, using said battery and a second threshold ratio;

wherein said detecting and identifying steps are applied to said text in real time, wherein said first and second threshold ratios compare a metric having a likelihood measure, and wherein a topic can be identified for a current segment of said text prior to detecting a topic change in said segment.

2. The method of claim 1, wherein said first and second threshold ratios are determined from said training data.

3. The method of claim 1, wherein said first and second threshold ratios are estimated theoretically.

4. The method of claim 1 wherein said identifying step performs translation of segmented text using topic labeling of each segment.

5. The method of claim 1, wherein said detecting step further comprises the steps of:

successively looking backward from a current word to a prior word, beginning where said prior word is said current word, determining for each step in said succession whether a comparative topic metric is greater than said first threshold ratio, said metric including some likelihood measure that a word string from said current word to said prior word will be found in a context of a topic in said battery, not including a neutral topic;

if said determination is YES, declaring said prior word an onset point of a new topic different from a current topic;

if said determination is NO, moving said prior word back one word and repeating said succession until said prior word is a regeneration point;

if all said successive determinations are less than one, declaring said current word a new regeneration point, otherwise advancing said current word by one word and repeating said successive determinations.

6. The method of claim 5, wherein said likelihood measure for said word string is calculated for the most likely and next most likely topics of said battery, and said comparative topic metric is the ratio of said next most likely measure to said most likely measure.

7. The method of claim 5, wherein said comparative topic metric is ##EQU14## where T_j is said current topic in said battery, where k is the length of said word string, where said current word is m+1 (at i=0), where said prior word is m-k+2 (at i=k-l), where P^T.sbsp.j.sup.)_m-i+1 is said likelihood measure for the single word located i words prior to said current word, and where ##EQU15##

8. The method of claim 5, wherein said identification step further comprises the steps of:

verifying whether said new topic associated with said word string beginning with said onset point is in said battery;

if said new topic is not in said battery, switching to said neutral topic;

otherwise, determining whether a second comparative topic metric is greater than said second threshold ratio for a topic in said battery other than said current topic;

if said determination is YES, declaring said topic to be the new topic;

if said determination is NO, adding a word to said word string and repeating said identification step.

9. The method of claim 8, wherein said verifying step further comprises the steps of:

computing for said word string and for every topic in said battery ##EQU16## where T_j is the j-th topic in said battery, where k is the number of words in said word string, where said current word is m+1 (at i=0), where said prior word is m-k+2 (at i=k-1), where P^T.sbsp.j.sup.)_m-i+1 is said likelihood measure for the single word located i words prior to said current word, and where ##EQU17## determining whether S.sub.(j) is greater than said first threshold ratio for every topic j in said battery.

10. The method of claim 8, wherein said identification determining step further comprises the steps of

computing for said word string ##EQU18## where l=m+1, m, . . . , m-k+2;

determining whether for some topic T_i in said battery, other than said current topic, R_i is greater than said second threshold ratio.

11. The method of claim 8, wherein said second comparative topic metric is ##EQU19## where T_j is the j-th topic in said battery, where k is the number of words in said word string, where said current word is w_m+1, where said prior word is w_m-k+2, where P([ . . . ]|T_i) is said likelihood measure for a string of words [ . . . ] in a context of topic T_i, where max_j≠

i P([ . . . ]|T_j) is a maximum value of said likelihood measure over all topics T_j in said battery except topic T_i, and where R_i is computed for all values l=m+1, m, . . . , m-k+2.

12. The method of claim 11 wherein said likelihood measure is computed using t-gram language models.

13. An apparatus for real time identification of topics in text, comprising:

means for forming a battery of topics from training data;

means for detecting topic changes in said text, using said battery and a first threshold ratio;

means for identifying topics in said text, using said battery and a second threshold ratio;

wherein said detecting and identifying means are applied to said text in real time, wherein said first and second threshold ratios compare a metric having a likelihood measure, and wherein a topic can be identified for a current segment of said text prior to detecting a topic change in said segment.

14. The apparatus of claim 13, wherein said first and second threshold ratios are determined from said training data.

15. The apparatus of claim 13, wherein said first and second threshold ratios are estimated theoretically.

16. The apparatus of claim 13 wherein said identifying step performs translation of segmented text using topic labeling of each segment.

17. The apparatus of claim 13, wherein said detecting means further comprises:

means for successively looking backward from a current word to a prior word, beginning where said prior word is said current word, wherein for each step in said succession a determination is made whether a comparative topic metric is greater than said first threshold ratio, said metric including some likelihood measure that a word string from said current word to said prior word will be found in a context of a topic in said battery, not including a neutral topic;

wherein if said determination is YES, said prior word is declared an onset point of a new topic different from a current topic;

wherein if said determination is NO, said prior word is moved back one word and said succession is repeated until said prior word is a regeneration point;

wherein if all said successive determinations are less than one, said current word is declared a new regeneration point, and otherwise said current word is advanced by one word and said successive determinations are repeated.

18. The apparatus of claim 17, wherein said likelihood measure for said word string is calculated for the most likely and next most likely topics of said battery, and said comparative topic metric is the ratio of said next most likely measure to said most likely measure.

19. The apparatus of claim 17, wherein said comparative topic metric is ##EQU20## where T_j is said current topic in said battery, where k is the length of said word string, where said current word is m+1 (at i=0), where said prior word is m-k+2 (at i=k-1), where P.sup.(T.sbsp.j.sup.)_m-i+1 is said likelihood measure for the single word located i words prior to said current word, and where ##EQU21##20.

20. The apparatus of claim 17, wherein said identifying means further comprises:

means for verifying whether said new topic associated with said word string beginning with said onset point is in said battery;

means for either switching to said neutral topic if said new topic is not in said battery, or determining whether a second comparative topic metric is greater than said second threshold ratio for a topic in said battery other than said current topic;

wherein if said determination is YES, said topic is declared to be the new topic, and wherein if said determination is NO, a word is added to said word string and said identification step is repeated.

21. The apparatus of claim 20, wherein said verifying means further comprises:

means for computing for said word string and for every topic in said battery ##EQU22## where T_j is the j-th topic in said battery, where k is the number of words in said word string, where said current word is m+1 (at i=0), where said prior word is m-k+2 (at i=k-1), where P.sup.(T.sbsp.j.sup.)_m-i+1 is said likelihood measure for the single word located i words prior to said current word, and where ##EQU23## means for determining whether S.sub.(j) is greater than said first threshold ratio for every topic j in said battery.

22. The apparatus of claim 20, wherein said identification determining means farther comprises:

means for computing for said word string ##EQU24## where l=m+1, m, . . . , m-k+2;

means for determining whether for some topic T_i in said battery, other than said current topic, R_i is greater than said second threshold ratio.

23. The apparatus of claim 20, wherein said second comparative topic metric is ##EQU25## where T_j is the j-th topic in said battery, where k is the number of words in said word string, where said current word is w_m+1, where said prior word is w_m-k+2, where P([ . . . ]|T_i) is said likelihood measure for a string of words [ . . . ] in a context of topic T_i, where max_j≠

i P([ . . . ]|T_j) is a maximum value of said likelihood measure over all topics T_j in said battery except topic T_i, and where R_i is computed for all values l=m+1, m, . . . , m-k+2.

24. The apparatus of claim 23 wherein said likelihood measure is computed using t-gram language models.