Extracting data from semi-structured information utilizing a discriminative context free grammar

• US 20060245641A1
• Filed: 04/29/2005
• Published: 11/02/2006
• Est. Priority Date: 04/29/2005
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shilman, Michael, Viola, Paul A., Narasimhan, Mukund
• Application Number:
  US11/119,467
• Publication Number:
  US 20060245641A1
• Time in Patent Office: Days
• US Class Current: 382/155
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/295 Named entity recognition
• CPC Class Codes: G06V 30/416 Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors

Abstract

A discriminative grammar framework utilizing a machine learning algorithm is employed to facilitate in learning scoring functions for parsing of unstructured information. The framework includes a discriminative context free grammar that is trained based on features of an example input. The flexibility of the framework allows information features and/or features output by arbitrary processes to be utilized as the example input as well. Myopic inside scoring is circumvented in the parsing process because contextual information is utilized to facilitate scoring function training.

Claims

1. A system that facilitates recognition, comprising:

a receiving component that receives an input of semi-structured information; and

a parsing component that parses the semi-structured information utilizing a discriminatively trained context free grammar.

2. The system of claim 1, the parsing component employs a perceptron-based learning rule to facilitate in learning a parse scoring function.

3. The system of claim 2, the parsing component trains the scoring function based on N-best parses, where N is an integer from one to infinity.

4. The system of claim 2, the parsing component trains the scoring function based on at least one subparse.

5. The system of claim 2, the parsing component interacts with a user to facilitate in parsing the semi-structured information.

6. The system of claim 1, the semi-structured information comprising semi-structured text, semi-structured information derived from images, and/or semi-structured information derived from audio.

7. The system of claim 6, the semi-structured text comprising text from an email, text from a document, text from a bibliography, and/or text from a resume.

20. A database system employing the method of claim 8. 1

8. A method for facilitating recognition, comprising:

receiving an input of semi-structured information; and

parsing the semi-structured information utilizing a discriminatively trained context free grammar.

9. The method of claim 8 further comprising:

constructing a discriminatively trained context free grammar.

10. The method of claim 9, the construction of the discriminatively trained context free grammar comprising:

performing a grammar induction process to generate a set of grammar rules to construct a context free grammar;

selecting a set of features that facilitate to disambiguate a set of semi-structured information;

generating label data automatically from a set of training data for the semi-structured information set; and

training the context free grammar discriminatively utilizing, at least in part, the label data.

11. The method of claim 8 further comprising:

utilizing correction propagation to facilitate in parsing the semi-structured information.

12. The method of claim 8 further comprising:

interfacing with a user to obtain at least one correction associated with the parsing of the semi-structured information.

13. The method of claim 8 further comprising:

parsing the input based on a grammatical scoring function;

the grammatical scoring function derived, at least in part, via a machine learning technique that facilitates in determining an optimal parse.

14. The method of claim 13, the machine learning technique comprising a perceptron-based learning technique.

15. The method of claim 14, the perceptron-based learning technique comprising:

setting parameters λ

(R) for each rule R in the grammar to obtain a maximized resulting score for a correct parse of Tⁱ of wⁱ for 0≦

i≦

m;

where T is a collection of training data {(wⁱ, l^a, T^a)|1≦

i≦

m}, wⁱ=w₁ⁱw₂ⁱ . . . w_niⁱ is a collection of components, lⁱ=l₁ⁱl₂ⁱ . . . l_niⁱ is a set of corresponding labels, and Tⁱ is a parse tree.

16. The method of claim 13 further comprising:

training a scoring function based on N-best parses, where N is an integer from one to infinity.

17. The method of claim 13 further comprising:

training a scoring function based on at least one subparse.

18. A system that facilitates recognition, comprising:

means for receiving an input of semi-structured information; and

means for parsing the semi-structured information utilizing a discriminatively trained context free grammar.

19. The system of claim 18 further comprising:

means for parsing the semi-structured information utilizing at least one classifier trained via a machine learning technique.