Method and system for extracting information from unstructured text using symbolic machine learning

• US 8,140,323 B2
• Filed: 07/23/2009
• Issued: 03/20/2012
• Est. Priority Date: 07/12/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Johnson, David E., Oles, Frank J.
• Primary Examiner(s): Shah, Paras
• Application Number:
  US12/507,866
• Publication Number:
  US 20090287476A1
• Time in Patent Office: 971 Days
• Field of Search: 715/256, 704/1, 704/9, 704/10, 706/45, 706/55
• US Class Current: 704/9
• CPC Class Codes: G06F 40/205 Parsing

Abstract

A method (and structure) of extracting information from text, includes parsing an input sample of text to form a parse tree and using user inputs to define a machine-labeled learning pattern from the parse tree.

Claims

1. A method of preparing a learning pattern for extracting information from text, said method comprising:

receiving an input sample of text as an input into a computer tool executed by a processor on a computer;

receiving inputs from a user to name entities within said sample of text;

parsing said input sample of text to form a parse tree, using a processor on a computer executing a parser that respects named entities of a Named Entity (NE) Annotator, meaning that the parser treats a named entity as a single token;

presenting said parse tree to a user; and

receiving user inputs to;

specify relation arguments and names of components of said parse tree;

define a machine-labeled learning pattern from said parse tree and its associated user inputs, said machine-labeled learning pattern comprising a precedence inclusion pattern wherein elements in said learning pattern are defined in a precedence relation and in an inclusion relation (PI pattern), based on said user'"'"'s inputs; and

store said machine-labeled learning pattern in a memory, said stored learning pattern being available as a query for searching for relation instances in unseen text that matches said PI pattern wherein said user interfaces with said computer tool using;

a first menu to permit the user to input a sample text, to select and designate argument names for linguistic elements from a selected sample text, and to construct a relation instance of said linguistic elements;

a second menu to permit the user to generate a PI pattern from one or more relation instances generated using said first menu; and

a third menu to permit the user to use a PI pattern generated by said second menu to search for undiscovered instances of a relation instance.

2. The method of claim 1, further comprising:

calculating a generalization of said learning pattern.

3. The method of claim 1, wherein said machine-labeled learning pattern comprises a precedence inclusion pattern wherein elements in said learning pattern are defined in at least one of a precedence relation and an inclusion relation, said data structure comprising an ordered tuple Σ

=(O, A, L), wherein;

O comprises an order symbol set of Σ

, a strictly partially ordered set of binary relation symbols, each of which is interpreted as a strict partial order on the set,

A comprises an argument name set of Σ

, a set whose elements name arguments for A-ary relations of interest, instances of which may be found in patterns, and

L comprises a property poset (partially ordered set) of Σ

, a bounded complete poset of labels that may be attached to elements of structures.

4. The method of claim 1, wherein said input sample comprises a first input sample, said parse tree comprises a first parse tree, and said learning pattern comprises a first learning pattern, said method further comprising:

receiving user inputs for receiving and parsing at least one more input sample of text to form therefrom a parse tree, for each said at least one more input sample parse tree, defining therefrom a learning pattern; and

calculating a generalization of said first learning pattern and at least some of learning patterns defined from said at least one more input sample of text.

5. The method of claim 4, wherein said generalization also comprises a precedence inclusion pattern.

6. The method of claim 5, wherein said precedence inclusion pattern of said generalization comprises a most specific generalization (MSG).

7. The method of claim 6, further comprising:

calculating a Minimal Most Specific Generalization (MMSG) of all of said learning samples used to define said learning pattern.

8. The method of claim 2, further comprising:

comparing said learning pattern with an unknown text.

9. The method of claim 7, further comprising:

comparing said learning patterns with an unknown text

10. The method of claim 9, wherein said comparing comprises:

parsing each said unknown text to form a parse tree;

calculating a generalization of said parse tree, said generalization forming a precedence inclusion pattern;

calculating an MMSG for said generalization; and

using said MMSG to calculate a similarity of said unknown text to said learning pattern.

11. The method of claim 8, wherein said comparing comprises:

parsing each said unknown text to form a parse tree;

calculating a generalization of said parse tree, said generalization forming a precedence inclusion pattern; and

calculating a similarity of said generalization of said parse tree of said unknown text with said generalization of said learning pattern.

12. An apparatus for relational learning, said apparatus comprising:

a generator for developing a precedence inclusion (PI) pattern of a learning sample, as executed by a processor on said apparatus, wherein elements in said learning sample are machine-labeled to define a precedence relation and an inclusion relation, based on user inputs, said PI pattern comprising a set equipped with two strict partial orders for said precedence and inclusion that interact with one another through laws of interactive transitivity and interactive irreflexivity; and

a graphical user interface (GUI) to permit a user to provide inputs used for said developing said PI pattern, wherein said user inputs are used to define a learning pattern wherein said GUI comprises;

a first menu to permit a user to input a sample text, to select and designate argument names for linguistic elements from a selected sample text, and to construct a relation instance of said linguistic elements;

a second menu to permit a user to generate a PI pattern from one or more relation instances generated using said first menu; and

a third menu to permit a user to use a PI pattern generated by said second menu to search for undiscovered instances of a relation instance.

13. The apparatus of claim 12, further comprising:

a comparison module for applying said PI pattern to unseen text and determining a similarity therebetween.

14. The apparatus of claim 13, wherein said generator further calculates a Minimal Most Specific Generalization (MMSG) of all learning samples entered and said comparison is based on said MMSG.

15. A non-transitory, signal-bearing storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of relational learning, said machine-readable instructions comprising:

a precedence inclusion (PI) pattern learning module for generating a PI pattern of a learning sample wherein elements in said learning sample are machine-labeled to define a precedence relation and an inclusion relation; and

a graphical user interface (GUI) to permit a user to provide inputs to define said PI pattern for each said learning sample;

wherein said GUI comprises;

a first menu to permit the user to input a sample text, to select and designate argument names for linguistic elements from a selected sample text, and to construct a relation instance of said linguistic elements;

a second menu to permit the user to generate a PI pattern from one or more relation instances generated using said first menu; and

a third menu to permit the user to use a PI pattern generated by said second menu to search for undiscovered instances of a relation instance.

16. The storage medium of claim 15, wherein said PI pattern learning module further calculates a Minimal Most Specific Generalization (MMSG) of all learning samples entered, said machine-readable instructions further comprising:

a PI application module for comparing unseen text with said learning samples, said comparing based on said MMSG.