Method and apparatus for generating summary information for hierarchically related information

• US 7,031,970 B2
• Filed: 12/16/2002
• Issued: 04/18/2006
• Est. Priority Date: 12/16/2002
• Status: Expired due to Fees

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Blitzer, John C.
• Primary Examiner(s): Rimell, Sam
• Assistant Examiner(s): ABEL JALIL, NEVEEN
• Application Number:
  US10/321,203
• Publication Number:
  US 20040117340A1
• Time in Patent Office: 1,219 Days
• Field of Search: 707 1-1041, 715/532, 704/251
• US Class Current: 1/1
• CPC Class Codes: G06F 16/345 Summarisation for human users
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method is provided for digesting the content of hierarchically related information. The method chooses a set of extracted sentences representing a proportion of the text associated with a subtopic, by a combination of features resting on inherent properties of the sentences, and on the content of a developing summary.

Claims

1. A method of forming a summary for hierarchically related information, where the information can be represented as a set of nodes wherein each node is associated with a portion of the information and that portion of the information contains at least one sentence, and wherein the nodes are connected by directed edges such that each node has at most one incoming edge, a parent node is the source of an incoming edge, and a child node is the target of an outgoing edge, the method comprising:

a) determining a sentence vector for each sentence associated with each node,

b) determining a centroid vector of the sentence vectors,

c) determining an intrinsic score for each sentence using the centroid vector,

d) selecting the sentence with the highest intrinsic score as a summary sentence to form a summary,

e) determining an extract score for each of the remaining sentences using the intrinsic score for the remaining sentence and at least one summary sentence included in the summary,

f) selecting the sentence having the highest extract score as a summary sentence and adding the summary sentence to the summary, and

g) repeating steps e) and f) until a desired number of sentences from the remaining sentences are selected as summary sentences for inclusion in the summary.

2. The method of claim 1 wherein the centroid vector of the sentence vectors comprises a vector where each position, p, in the vector contains the average of all values in position p in all of the sentence vectors.

3. The method of claim 1 wherein determining an intrinsic score for each sentence comprises:

a) determining a sentence position of the sentence in the information, a hierarchy position of the node associated with the sentence in the hierarchy, and using the centroid vector, determining a lexical centrality of the sentence to the information, and

b) determining the intrinsic score for the sentence using the sentence position, the hierarchy position and the lexical centrality determined for the sentence.

4. The method of claim 1 wherein determining an extract score far each of the remaining sentences comprises:

a) selecting one of the remaining sentences,

b) determining the number of non-quoting sentences in the summary which are adjacent to the selected remaining sentence, the number of sentences in the summary whose associated nodes are either a parent node or a child node of the node associated with the selected remaining sentence, the number of sentences in the summary which are quoted immediately before the selected remaining sentence, and the number of sentences in the summary that appear immediately after a quote of the selected remaining sentence, and

c) responsive to the determinations in step b and the intrinsic score of the selected remaining sentence, determining an extract score, and

d) repeating steps a–

c until each of the remaining sentences has an extract score.

5. The method of claim 1 wherein the desired number of sentences selected as summary sentences for inclusion in the summary equals a percentage of a total number of sentences associated with all of the nodes representing the hierarchically-related information.

6. The method of claim 1 wherein the desired number of sentences selected as summary sentences for inclusion in the summary equals a percentage of a total number of the nodes representing the hierarchically-related information.

7. The method of claim 1 further including formatting the summary for display and displaying the summary using a display processor.

8. A method of forming a summary for hierarchically related information represented as a set of nodes wherein each node is associated with a portion of the information containing at least one sentence, and wherein the nodes are connected by directed edges such that each node has at most one incoming edge, a parent node is the source of an incoming edge, and a child node is the target of an outgoing edge, the method comprising:

selecting a sentence from all of the sentences associated with all of the nodes as a first summary sentence to form a summary;

the first summary sentence being selected by computing an intrinsic score indicating a lexical centrality of the sentence to the information represented by the set of nodes;

the first summary sentence having the highest intrinsic score of all of the sentences associated with all of the nodes; and

for each additional summary sentence to be added to the summary until a desired summary length is reached, selecting a remaining sentence from the plurality of remaining sentences associated with all of the nodes;

the selected remaining sentence having the highest extract score of all extract scores computed for the remaining sentences;

computing the extract score including

determining the number of non-quoting sentences in the summary which are adjacent to the selected remaining sentence;

determining the number of sentences in the summary whose associated nodes are either a parent node or a child node of the node associated with the selected remaining sentence;

determining the number of sentences in the summary which are quoted immediately before the selected remaining sentence; and

determining the number of sentences in the summary that appear immediately after a quote of the selected remaining sentence.

9. The method of claim 8 wherein computing the extract score further includes combining the extract score with the intrinsic score computed for the selected remaining sentence.

10. The method of claim 8 wherein computing the extract score further includes computing a sentence similarity quantity produced by adding a similarity quantity indicating a similarity of the selected remaining sentence to each summary sentence included in the summary the sentence similarity quantity being subtracted from the extract score and indicating that the selected remaining sentence includes information redundant to the summary.

11. The method of claim 8 further including formatting the summary for display and displaying the summary using a display processor.