Method and apparatus for generating summary information for hierarchically related information

• US 20040117340A1
• Filed: 12/16/2002
• Published: 06/17/2004
• Est. Priority Date: 12/16/2002
• Status: Active Grant

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Blitzer, John C.
• Granted Patent: US 7,031,970 B2
• Time in Patent Office: Days
• US Class Current: 707/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, the nodes are connected by directed edges wherein each node has at most one incoming edge, a parent node is the source of an incoming edge, a child node is the target of an outgoing edge

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,

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

e) determining an extract score for each of the remaining sentences from the intrinsic score and the summary,

f) selecting the sentence with the highest extract score and adding it to the summary, and

g) repeating steps e) and f) until a desired number of sentences are selected.

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

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

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

b) responsive to the determinations in step a determining an intrinsic score for the sentence.

4. ) The method of claim 1 wherein modifying the intrinsic score to determine an extract score for 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 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 sentence, the number of sentences in the summary which are quoted immediately before the selected sentence, and the number of sentences in the summary that appear immediately after a quote of the selected sentence, and

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

d) repeating steps a-c until each of the remaining sentences has an extract score.