Ontology-based parser for natural language processing

• US 7,027,974 B1
• Filed: 10/27/2000
• Issued: 04/11/2006
• Est. Priority Date: 10/27/2000
• Status: Expired due to Term

• Current Assignee: Leidos, Inc. (Leidos Holdings, Inc.)
• Original Assignee: Science Applications International Corporation
• Inventors: Caudill, Maureen, Busch, Justin Eliot, Graydon, Patrick John, Lin, Albert Deirchow
• Primary Examiner(s): ABEBE, DANIEL DEMELASH
• Application Number:
  US09/697,676
• Time in Patent Office: 1,992 Days
• Field of Search: 704/4, 704/9, 707/4
• US Class Current: 704/4
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

An ontology-based parser incorporates both a system and method for converting natural-language text into predicate-argument format that can be easily used by a variety of applications, including search engines, summarization applications, categorization applications, and word processors. The ontology-based parser contains functional components for receiving documents in a plurality of formats, tokenizing them into instances of concepts from an ontology, and assembling the resulting concepts into predicates. The ontological parser has two major functional elements, a sentence lexer and a parser. The sentence lexer takes a sentence and converts it into a sequence of ontological entities that are tagged with part-of-speech information. The parser converts the sequence of ontological entities into predicate structures using a two-stage process that analyzes the grammatical structure of the sentence, and then applies rules to it that bind arguments into predicates.

Claims

1. A system for ontological parsing that converts natural-language text into predicate-argument format comprising:

a sentence lexer for converting a natural language sentence into a sequence of ontological entities that are tagged with part-of-speech information; and

a parser for converting the sequence of ontological entities into predicate structures using a two-stage process that analyzes the grammatical structure of the natural language sentence and binds arguments into predicates.

2. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 1, wherein said sentence lexer comprises:

a document iterator that receives text input and outputs individual sentences;

a lexer that receives said individual sentences from said document iterator and outputs individual words; and

an ontology that receives said individual words from said lexer and returns ontological entities or words tagged with default assumptions about an ontological status of said individual words to said lexer.

3. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 2, wherein said ontology is a parameterized ontology that assigns numbers to concepts.

4. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 3, wherein said numbers can be subtracted to determine if features are in agreement, wherein a non-negative number indicates agreement.

5. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 3, wherein said numbers can be subtracted to determine if features are in agreement, wherein a negative number indicates feature incompatibility.

6. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 3, wherein in said parameterized ontology, each data structure includes at least one integer value, where groups of digits of said integer value correspond to specific branches taken at corresponding levels in a parse tree.

7. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 6, wherein said parameterized ontology is encoded in two ways:

a base of said integer value bounds a number of branches extending from a root node of said ontology, while a number of digits in the integer value bounds a potential depths of said parse tree.

8. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 6, wherein a first digit difference between two nodes provides a measure of the degree of ontological proximity of two concepts.

9. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 6, wherein said predicates and arguments are represented by encodings comprising at least one digit separated into multiple groups to provide multiple ontological levels and a branching factor at each node.

10. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 2, further comprising lexer filters for modifying said individual sentences based on word meanings.

11. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 10, wherein said lexer filters comprise at least one of:

a noun filter, an adjective filter, an adverb filter, a modal verb filter, a stop word filter, a pseudo-predicate filter, and a pseudo-concept filter.

12. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 11, wherein said stop word filter removes stop words from said individual sentences.

13. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 11, wherein said adjective filter removes lexemes representing adjectives from said individual sentences.

14. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 11, wherein said noun filter groups proper nouns into single lexical nouns.

15. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 11, wherein said modal verb filter removes modal verbs from objects of said individual sentences.

16. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 11, wherein said adverb filter removes lexemes containing adverb concepts from said individual sentences.

17. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 11, wherein said pseudo-predicate filter removes verbs from queries.

18. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 11, wherein said pseudo-concept filter removes concepts from queries.

19. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 1, wherein said parser comprises:

a sentence receiver that receives sentences including ontological entities from said sentence lexer;

a parser component that parses said sentences, received by said sentence receiver, into parse trees representing concepts in a respective sentence received by said sentence receiver; and

a parse tree converter that receives the output of said parser component and converts said parse trees into predicates.

20. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 19, wherein said parser component further comprises:

parser filters operating on said predicates to remove erroneous predicates.

21. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 19, wherein said parser component looks ahead at least one word, scans input from left-to-right, and constructs said parse tree.

22. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 20, wherein said parser filters remove parse trees that violate one of statistical and ontological criteria for well-formedness.

23. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 22, wherein said parser filters include a selectional restriction filter and a parse probability filter.

24. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 23, wherein said selectional restriction filter vetoes parse trees having conflicts between selectional features of concepts serving as arguments to a second concept and restrictions of said second concept.

25. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 23, wherein said parse probability filter vetoes parse trees that fall below a minimum probability for semantic interpretation.

26. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 1, wherein said system is modular to permit the use of any part-of-speech-tagged ontology.

27. A system for ontological parsing that converts natural-language text into predicate-argument format as recited in claim 6, wherein said parse trees is represented by modified hexadecimal digits that have an octet of hexadecimal pairs to provide eight ontological levels and a branching factor at each node of 256.

28. A method of ontological parsing that converts natural-language text into predicate-argument format comprising the steps of:

converting a natural language sentence into a sequence of ontological entities that are tagged with part-of-speech information; and

converting said sequence of ontological entities into predicate structures using a two-stage process that analyzes the grammatical structure of the natural language sentence and binds arguments into predicates.

29. A method of ontological parsing that converts natural-language text into predicate-argument format as recited in claim 28, further comprising the step of modifying said natural language sentence based on word meanings.

30. A method of ontological parsing that converts natural-language text into predicate-argument format as recited in claim 28, further comprising the steps of:

receiving sentences including ontological entities;

parsing said sentences including ontological entities into parse trees representing concepts in the corresponding sentence including ontological entities; and

converting said parse trees into predicates.

31. A method of ontological parsing that converts natural-language text into predicate-argument format as recited in claim 28, wherein the step of parsing comprises the step of looking ahead one word, scanning input from left-to-right, and constructing said parse tree.

32. A method of ontological parsing that converts natural-language text into predicate-argument format as recited in claim 28, further comprising the step of removing parse trees that violate one of statistical and ontological criteria for well-formedness.

33. A method of ontological parsing that converts natural-language text into predicate-argument format as recited in claim 28, further comprising the step of vetoing parse trees having conflicts between selectional features of concepts serving as arguments to a second concept and restrictions of said second concept.

34. A method of ontological parsing that converts natural-language text into predicate-argument format as recited in claim 30, further comprising the step of assigning numbers to said concepts.

35. A method of ontological parsing that converts natural-language text into predicate-argument format as recited in claim 34, further comprising the step of subtracting said numbers to determine if features are in agreement, wherein a negative number indicates feature incompatibility.

36. A method of ontological parsing that converts natural-language text into predicate-argument format as recited in claim 34, further comprising the step of subtracting said numbers to determine if features are in agreement, wherein a non-negative number indicates agreement.

37. A method of ontological parsing that converts natural-language text into predicate-argument format as recited in claim 28, further comprising the step of vetoing parse trees that fall below a minimum probability for semantic interpretation.

38. A method of ontological parsing that converts natural-language text into predicate-argument format as recited in claim 28, wherein the step of converting the natural language sentence into the sequence of ontological entities includes data structures, wherein each data structure includes an integer value, where each digit of said integer value corresponds to a specific branch taken at a corresponding level in a parse tree.

39. A method of ontological parsing that converts natural-language text into predicate-argument format as recited in claim 38, further comprising the step of encoding in two ways:

a number of grouped digits and their numerical base bounds a number of branches extending from a root node of an ontology, while at least one of said groups of digits in said integer value bounds a potential depth of said parse tree.

40. A method of ontological parsing that converts natural-language text into predicate-argument format as recited in claim 39, wherein a most significant digit difference between two nodes provides a measure of the degree of ontological proximity of two concepts.

41. A method of ontological parsing that converts natural-language text into predicate-argument format as recited in claim 38, further comprising the step of representing said parse trees by modified hexadecimal numbers that have an octet of hexadecimal pairs to provide eight ontological levels and a branching factor at each node of 256.

42. A method of ontological parsing that converts natural-language text into predicate-argument format as recited in claim 28, further comprising the step of representing said predicates and arguments by encodings comprising at least one digit separated into groups to provide multiple ontological levels and a branching factor at each node.