Method and apparatus for learning information extraction patterns from examples

• US 5,796,926 A
• Filed: 06/06/1995
• Issued: 08/18/1998
• Est. Priority Date: 06/06/1995
• Status: Expired due to Fees

• Current Assignee: Price Waterhouse Company Limited (Price Waterhouse Hong Kong Services Limited)
• Original Assignee: Price Waterhouse Company Limited (Price Waterhouse Hong Kong Services Limited)
• Inventors: Huffman, Scott B.
• Primary Examiner(s): Horabik, Michael
• Assistant Examiner(s): WONG, ALBERT KANG
• Application Number:
  US08/469,981
• Time in Patent Office: 1,169 Days
• Field of Search: 364/419.19, 364/419.08, 395/22, 395/23, 395/75, 395/77, 395/50, 395/54
• US Class Current: 706/45
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A system is provided for learning extraction patterns (grammar) for use in connection with an information extraction system. The learning system learns extraction patterns from examples of texts and events. The patterns can then be used to recognize similar events in other input texts. The learning system builds new extraction patterns by recognizing local syntactic relationships between the sets of constituents within individual sentences that participate in events to be extracted. The learning system generalizes extraction patterns it has learned previously through simple inductive learning of sets of words that can be treated synonymously within the patterns. Sets of patterns for a sample extraction task perform nearly at the level of a hand-built dictionary of patterns.

Claims

1. In a computer-based information extraction system having text as input and events as output, a method for learning information extraction patterns for use in logging events, said learning method comprising the steps of:

a) presenting an example sentence to a pattern learning engine;

b) identifying to said pattern learning engine a valid event, said valid event comprising a set of syntactic constituents from within said example sentence; and

c) determining whether said example sentence and its corresponding valid event is not already matched by any known pattern, wherein said determining step comprises;

segmenting said example sentence into in a series of syntactic constituents, each said syntactic constituent containing a head word/head entity characterizing said syntactic constituent; and

matching each said head word/entity and selected other syntactic properties of said series of syntactic constituents against said known patterns in order to verify plausibility of specific syntactic relationships between said syntactic constituents of the event under test;

and, if the example sentence and its valid event are not matched by any of said known patterns,

d) attempting to generalize one of said known patterns to match the example sentence with its corresponding valid event; and

, if no acceptable resultant pattern is produced,

e) building, in said learning engine, a new grammar pattern based on said example sentence and its corresponding valid event, for use in constructing subsequent valid events from subsequent input sentences which are input to said information extraction system.

2. In the computer-based system according to claim 1, wherein said new pattern building step (e) includes:

producing potential patterns from the example by;

searching for sets of plausible syntactic relationships that relate all role-filling constituents in the example to one another, the role-filling constituents being syntactic constituents in the input example sentence that are referenced in the output event of the example.

3. In the computer-based system according to claim 2, wherein said searching step comprises:

finding a path of said plausible syntactic relationships between each pair of said role-filling constituents, a path being a chain of syntactic relations from a beginning to an end of said role-filling constituents; and

merging said paths to create a single set of said plausible syntactic relationships relating all said role-filling constituents.

4. In the computer-based system according to claim 3, wherein said finding step comprises:

locating direct relationships in order to produce said paths; and

locating indirect relationships through intermediate constituents in absence of direct relationships to produce said paths.

5. In a computer-based information extraction system having text as input and events as output, a method for learning information extraction patterns for use in logging events, said method comprising the steps of:

presenting a plurality of example sentences to a pattern learning engine;

identifying to said pattern learning engine valid events that consist of sets of constituents from within said example sentences; and

building, in said learning engine, grammar patterns based on said identified valid events for use in constructing subsequent valid events from subsequent input sentences which are input to said information extraction system;

wherein said identifying step allows a user to interactively identify events and roles in texts, said step comprising;

flagging, by said learning engine in each potential training sentence, entities of interest;

presenting by said learning engine to the user a choice of combinations of the entities which signify potential valid events; and

receiving by said learning engine indications by the user that selected entities constitute valid events and indications that specific entities of interest fill specific roles in order to establish a positive example of an actual training sentence identifying said selected entities, selected syntactic constituents, and an event that occurs in said actual training sentence;

wherein said grammar pattern building step comprises;

determining whether a new example is not already matched by any known pattern;

attempting to generalize one of said known patterns to cover the example; and

if no acceptable pattern is produced

building a new pattern based on the new example;

wherein said determining step comprises testing head entities and word group properties to verify plausibility of specific syntactic relationships between pairs of constituents;

wherein said new pattern building step includes;

producing potential patterns from the example by;

searching for sets of plausible syntactic relationships that relate all role-filling constituents in the example to one another, the role-filling constituents being syntactic constituents in the input example sentence that are referenced in the output event of the example;

wherein said searching step comprises;

finding a path of said plausible syntactic relationships between each pair of said role-filling constituents a path being a chain of syntactic relations from a beginning to an end of said role-filling constituents; and

merging said paths to create a set of said plausible syntactic relationships relating all said role-filling constituents;

wherein said finding step comprises;

locating direct relationships to produce said paths; and

locating indirect relationships through intermediate constituents in absence of direct relationships to produce said paths; and

wherein said new pattern building step further comprises;

producing potential patterns from the example; and

selecting from said potential patterns a best pattern for addition to a pattern dictionary, said best pattern being selected by;

measuring, on a set of valid examples consisting of input sentences and output events to be extracted, output event extraction accuracy of each said potential pattern, said output events being extracted from said input sentences, and by

choosing the most accurate of the potential patterns.