Systems and methods for sentence based interactive topic-based text summarization

• US 7,376,893 B2
• Filed: 12/16/2002
• Issued: 05/20/2008
• Est. Priority Date: 12/16/2002
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Zaenen, Annie E., Chen, Francine R., Brants, Thorsten H.
• Primary Examiner(s): Hong; Stephen
• Assistant Examiner(s): Patel; Manglesh M.
• Application Number:
  US10/319,544
• Publication Number:
  US 20040117725A1
• Time in Patent Office: 1,982 Days
• Field of Search: 715/530, 715/903, 715/531, 715/501.1, 715/254, 715/200, 715/255, 704/9, 704/257, 707/3, 707/100
• US Class Current: 715/254
• CPC Class Codes: G06F 16/345 Summarisation for human users
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

Techniques for determining sentence based interactive topic-based summarization are provided. A text to be summarized is segmented. Discrete keyword, key-phrase, n-gram, sentence and other sentence constituent based summaries are generated based on statistical measures for each text segment. Interactive topic-based summaries are displayed with human sensible omitted text indicators such as alternate colors, fonts, sounds, tactile elements or other human sensible display characteristics useful in indicating omitted text. Individual and/or combinations of discrete keyword, key-phrase, n-gram, sentence, noun phrase and sentence constituent based summaries are dynamically displayed to provide an overview of topic and subtopic development within a text. A hierarchical and interactive display of texts based on the use of discrete sentence constituent based summaries which associates expansible and contractible displayed text provides contextualized access to an interactive topic-based text summary and to an original text.

Claims

1. A method of determining sentence based interactive topic-based text summaries comprising the steps of:

dynamically determining a text to summarize;

dynamically determining at least one segment of the determined text to summarize;

dynamically determining at least one discrete sentence based interactive topic-based text summary based on a summary type and a determined segment based on a statistical measure of the segment characterization and segment differentiation;

dynamically determining a subtopic development by recursively repeating the step of determining at least one discrete sentence based interactive topic-based text summary, the subtopic development arranged as a hierarchy including at least one subtopic of the at least one discrete sentence based interactive topic-based text summary;

storing in an electronic memory storage at least one discrete sentence based interactive topic based text summary based on the at least one determined text segment based summary type; and

,

displaying the at least one discrete sentence based interactive topic based text summary.

2. The method of claim 1, wherein the statistical measure is a measure of determined segment characterization and other segment differentiation.

3. The method of claim 2, wherein determining the statistical measure comprises the steps of:

determining at least one candidate sentence within a determined segment;

for each at least one candidate sentence, determining the measure of determined segment characterization and other segment differentiation;

ranking the at least one candidate sentence based on the determined measure of current segment characterization and other segment differentiation.

4. The method of claim 3, wherein the at least one other segment is at least one of the n-preceding and m-following segments of the determined segment and where n+m>

0.

5. The method of claim 2, wherein the measure of determined segment characterization and other segment differentiation is at least one of mutual information, log odds ratio, Π

², G² distributions.

6. The method of claim 1, further comprising the steps of:

dynamically determining the at least one segment to summarize;

dynamically displaying at least one discrete interactive topic-based text summary based on the at least one dynamically determined segment and wherein a human sensible display characteristic indicates omitted text.

7. The method of claim 6, wherein the human sensible display characteristic is at least one of a visual, auditory, tactile, olfactory and taste characteristic.

8. The method of claim 7, wherein the at least one visual characteristic is at least one of a text font, color, italics, bolding and placement.

9. The method of claim 1, wherein the statistical measure is at least one of four components of mutual information based on presence in a segment and presence in other segments.

10. The method of claim 1, wherein the statistical measure is at least two of four components of mutual information based on presence in the determined segment and presence in other segments.

11. The method of claim 1, further comprising the step of normalizing probabilities based on sentence length.

12. The method of claim 2, wherein determining the statistical measure further comprises the steps of:

determining a function f_i on an indication of the presence of term w1, determining a pointwise mutual information score I(f_i,r) between the determined function f_i and the segment based on the formula;

$I<br><br>\left(f_i,r\right)=\log <br><br>\frac{P(f_i<br><br><br><br>r)}{P<br><br>\left(f_i\right)}=\log <br><br>\frac{P<br><br>\left(f_i,r\right)}{P<br><br>\left(f_i\right)<br><br>P<br><br>\left(r\right)};<br><br>$

determining an average score for each of the at least one candidate sentences based on an average of the pointwise mutual information scores in the at least one candidate sentences.

13. The method of claim 3, further comprising the steps of:

determining a relative importance score 8 for the presence or absence of a term in a region;

determining a term-region score based on presence (f_i=1) of a term in a determined segment r, and absence (f_i=0) of the term from other segments (r) based on the following formula

Score_wi=λ

P(ƒ

_i=1|r)I(ƒ

_i=1,r)+(1−

λ

)P(ƒ

_i=0|,r)I(ƒ

_i=0, r).

14. The method of claim 3, where determining candidate scores comprises the steps of:

determining a weighting of term w_i in each candidate sentence;

determining candidate sentence scores based on the formula

$\mathrm{Score}<br><br><br><br>\left(S\right)=\underset{w_i<br><br>\mathrm{\varepsilon <br><br>S}}{\sum <br><br>}<br><br>P<br><br>\left(w_i\right)<br><br>\mathrm{Score}<br><br><br><br>\left(w_i\right).$

15. The method of claim 3, further comprising the step of removing inessential elements from at least one of the candidate sentences and the determined summary sentences, based on at least one of syntactic analysis, semantic analysis and statistical filtering.

33. The method of claim 3, further comprising the step of modifying at least one word.

16. A system for determining sentence based interactive topic-based text summaries comprising:

an input/output circuit for receiving, a selected sentence constituent based summary type, a selected text and a dynamically determined portion of text to summarize;

a processor that retrieves the selected text based on the summary type from the input/output circuit, segments the text and determines a text segment to summarize;

a statistical measure determining circuit for determining a statistical measure of segment characterization and segment differentiation of the at least one determined segment; and

wherein the processor segments the text into at least one segment and determines and prepares for display a discrete sentence based interactive topic-based text summary for at least one determined segment based on the statistical measure of the segment;

dynamically determining a subtype development by recursively repeating the step of determining and preparing for display a discrete sentence based interactive topic-based text summary, the subtopic development arranged as a hierarchy including at least one subtopic of the at least one discrete sentence based interactive topic-based text summary.

17. The system of claim 16, wherein the statistical measure is a measure of determined segment characterization and other segment differentiation.

18. The system of claim 17, wherein at least one candidate sentence is determined within a determined segment, and a measure of segment characterization and other segment differentiation is determined for each candidate sentence.

19. The system of claim 18, wherein other segments are at least one of n-preceding text segments of a determined text segment and in-following text segments and where n+m>

0.

20. The system of claim 17, wherein the measure of text segment characterization and other segment differentiation is at least one of mutual information, log odds ratio, Π

², G² distributions.

21. The system of claim 16, further comprising a display circuit that displays at least one discrete interactive topic-based text summary based on a dynamic selection of the selected text segment and which display a human sensible display characteristic to indicate omitted text.

22. The system of claim 21, wherein the human sensible display characteristic is at least one of a visual, auditory, tactile, olfactory and taste characteristic.

23. The system of claim 22, wherein the visual characteristic is at least one of text font, text color, text italics, text bolding and placement.

24. The system of claim 16, wherein the statistical measure determining circuit determines at least one of four components of mutual information based on presence in a segment and presence in other segments.

25. The system of claim 16, wherein the statistical measure determining circuit determines at least two of four components of mutual information based on presence in a segment and presence in other segments.

26. The system of claim 16, further comprising a probability normalization circuit that normalizes probabilities based on sentence length.

27. The system of claim 17, wherein the statistical measure determining circuit determines

a function f_i based on an indication of the presence of term w_i;

a pointwise mutual information score I(f_i,r) between the determined function f_i, and the segment based on the formula;

$I<br><br>\left(f_i,r\right)=\log <br><br>\frac{P(f_i<br><br><br><br>r)}{P<br><br>\left(f_i\right)}=\log <br><br>\frac{P<br><br>\left(f_i,r\right)}{P<br><br>\left(f_i\right)<br><br>P<br><br>\left(r\right)};<br><br>$

an average score for ranking the at least one candidate sentences based on an average of the pointwise mutual information scores in the at least one candidate sentences.

28. The system of claim 18, wherein the statistical measure determining circuit determines;

a relative importance score 8 for the presence or absence of a term in a region;

a term-region score for ranking candidate sentences based on presence (f_i1) of a term in a determined segment r, and absence (f_i=0) of the term from other segments (Γ

r) based on the following formula

Score_wi=λ

P(ƒ

_i=1|r)I(ƒ

_i=1,r)+(1−

λ

)P(ƒ

_i=0|,r)I(ƒ

_i=0, r).

29. The system of claim 18, wherein the statistical measure determining circuit determines;

a relative frequency of each of the terms w_i in each candidate sentence;

scores for the candidate sentence based on the formula

$\mathrm{Score}<br><br><br><br>\left(S\right)=\underset{w_i<br><br>\mathrm{\varepsilon <br><br>S}}{\sum <br><br>}<br><br>P<br><br>\left(w_i\right)<br><br>\mathrm{Score}<br><br><br><br>\left(w_i\right).$

30. The system of claim 18, wherein the inessential elements are removed from at least one of the candidate sentences and the determined summary sentences, based on at least one of syntactic analysis, semantic analysis and statistical filtering.

34. The system of claim 18, wherein at least one word is modified.

31. Computer readable storage medium comprising:

computer readable program code embodied on the computer readable storage medium, the computer readable program code usable to program a computer to determine sentence based interactive topic-based text summaries comprising the steps of;

dynamically determining a text to summarize;

determining at least one segment of the determined text to summarize;

dynamically determining at least one discrete sentence based interactive topic-based text summary based on a summary type and a determined segment based on a statistical measure of the segment characterization and segment differentiation;

dynamically determining a subtopic development by recursively repeating the step of determining at least one discrete sentence based interactive topic-based text summary, the subtopic development arranged as a hierarchy including at least one subtopic of the at least one discrete sentence based interactive topic-based text summary;

preparing for dynamic display of the at least one discrete sentence based interactive topic based text summary based on the at least one text segment of the determined text and the at least one discrete sentence based interactive topic based text summary type.

32. Computer readable storage medium comprising computer readable program code embodied on the computer readable storage medium, the computer readable program code usable to program a computer to determine sentence based interactive topic-based text summaries comprising the steps of:

instructions for dynamically determining a text to summarize;

instructions for dynamically determining at least one segment of the determined text to summarize;

instructions for dynamically determining at least one discrete sentence based interactive topic-based text summary based on a summary type and a determined segment based on a statistical measure of the segment characterization and segment differentiation;

instructions for dynamically determining a subtopic development by recursively repeating the step of determining at least one discrete sentence based interactive topic-based text summary, the subtopic development arranged as a hierarchy including at least one subtopic of the at least one discrete sentence based interactive topic-based text summary;

instructions for preparing for dynamic display of the at least one discrete sentence based interactive topic based text summary based on the at least one text segment of the determined text and the at least one discrete sentence based interactive topic based text summary type.