Ontology-based parser for natural language processing Number:7,027,974 from the United States Patent and Trademark Office (PTO) owispatent 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.<H processing, language, Ontology, based, , 7027974.html, Patent, pto, 7027974

Title: Ontology-based parser for natural language processing

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.

Patent Number: 7,027,974 Issued on 04/11/2006 to Busch, et al.

Inventors: Busch; Justin Eliot (Irvine, CA); Lin; Albert Deirchow (San Diego, CA); Graydon; Patrick John (Windsor, CA); Caudill; Maureen (San Diego, CA)
Assignee: Science Applications International Corporation (San Diego, CA)

Appl. No.: 697676

Filed: October 27, 2000

Current U.S. Class: 704/4 ; 704/9; 707/4

Current International Class: G10L 13/08 (20060101)

Field of Search: 704/4,9 707/4

References Cited [Referenced By]

U.S. Patent Documents


4270182	May 1981	Asija
4864502	September 1989	Kucera et al.
4887212	December 1989	Zamora et al.
4914590	April 1990	Loatman et al.
4984178	January 1991	Hemphill et al.
5056021	October 1991	Ausborn
5101349	March 1992	Tokuume et al.
5146406	September 1992	Jensen
5237502	August 1993	White et al.
5297039	March 1994	Kanaegami et al.
5309359	May 1994	Katz et al.
5317507	May 1994	Gallant
5321833	June 1994	Chang et al.
5331556	July 1994	Black, Jr. et al.
5386556	January 1995	Hedin et al.
5404295	April 1995	Katz et al.
5418948	May 1995	Turtle
5446891	August 1995	Kaplan et al.
5475588	December 1995	Schabes et al.
5535382	July 1996	Ogawa
5576954	November 1996	Driscoll
5619709	April 1997	Caid et al.
5675710	October 1997	Lewis
5680627	October 1997	Anglea et al.
5687384	November 1997	Nagase
5694523	December 1997	Wical
5694592	December 1997	Driscoll
5706497	January 1998	Takahashi et al.
5721902	February 1998	Schultz
5721938	February 1998	Stuckey
5761389	June 1998	Maeda et al.
5790754	August 1998	Mozer et al.
5794050	August 1998	Dahlgren et al.
5802515	September 1998	Adar et al.
5835087	November 1998	Herz et al.
5864855	January 1999	Ruocco et al.
5870701	February 1999	Wachtel
5870740	February 1999	Rose et al.
5873056	February 1999	Liddy et al.
5893092	April 1999	Driscoll
5915249	June 1999	Spencer
5920854	July 1999	Kirsch et al.
5930746	July 1999	Ting
5933822	August 1999	Braden-Harder et al.
5940821	August 1999	Wical
5953718	September 1999	Wical
5960384	September 1999	Brash
5963940	October 1999	Liddy et al.
5974412	October 1999	Hazlehurst et al.
5974455	October 1999	Monier
6006221	December 1999	Liddy et al.
6012053	January 2000	Pant et al.
6021387	February 2000	Mozer et al.
6021409	February 2000	Burrows
6026388	February 2000	Liddy et al.
6038560	March 2000	Wical
6047277	April 2000	Parry et al.
6049799	April 2000	Mangat et al.
6055531	April 2000	Bennett et al.
6076051	June 2000	Messerly et al.
6233575	May 2001	Agrawal et al.
6778979	August 2004	Grefenstette et al.
2002/0143755	October 2002	Wynblatt et al.

Foreign Patent Documents


0413132	Feb., 1991	EP
WO 0049517	Aug., 2000	WO

Other References

Koller, D., and Sahami, M. Hierarchically classifying documents using very few words. ICML-97; Proceedings of the Fourteenth International Conference on Machine Learning, 1997. cited by other .
Susan T. Dumais, John Platt, David Hecherman, Mehran Sahami: Inductive Learning Algorithms and Representations for Text Categorization. CIKM pp. 148-155, 1998. cited by other .
Andrew McCallum, Kamal Nigam, Jason Rennie and Kristie Seymore. Building Domain-Specific Search Engines with Machine Learning Techniques. AAAI-99 Spring Symposium, 1999. cited by other .
M. Sahami, S. Dumais, D. Heckerman, and E. Horvitz. A Bayesian approach to filtering junk e-mail. AAAI Workshop on Learning for Text Categorization, Jul. 1998, Madison, Wisconsin. cited by other .
Larkey, Leah S. (1999) A Patent Search and Classification System In Digital Libraries 99--The Fourth ACM Conference on Digital Libraries (Berkeley, CA, Aug. 11-14 1999) ACM Press, pp. 79-87. cited by other .
Teuvo Kohonen, Self Organization and Associative memory, 3.sup.rd Edition, Table of Contents, Springer-Verlag, New York, NY 1989. cited by other .
Dunja Mladinic, Turning Yahoo into an Automatic Web Page Classifier, ECAI 98:13.sup.th European Conference on Artificial Intelligence, Brighton, UK, Aug. 23 to Aug. 28, 1998, pp. 473-474, John Wiley & Sons, Ltd. cited by other .
Tom M. Mitchell, "Machine Learning", WCB/McGraw-Hill 1997. cited by other .
Choon Yang Quek, "Classification of World Wide Web Documents", Senior Honors Thesis, CMU. cited by other .
Bresnan, Joan (ed.). 1982. The Mental Representation of Grammatical Relations. Cambridge, MA: MIT Press. cited by other .
Charniak, Eugene. 1993. Statistical Language Learning. Cambridge, MA: MIT Press. cited by other .
Domingos, Pedro and Michael Pazzani. 1997. "On the Optimality of the Simple Bayesian Classifier Under Zero-One Loss." Machine Learning 29:103-130. cited by other .
Duda, Richard and Peter Hart. 1973. Pattern Classification and Scene Analysis. New York, NY: Wiley. cited by other .
Gold, Mark. 1967. "Language Identification in the Limit." Information and Control 10:447-474. cited by other .
Horning, James. 1969. A Study of Grammatical Inference. Ph.D. thesis, Stanford. cited by other .
Magerman, David and Mitchell Marcus. 1991. "Pearl: A Probabilistic Chart Parser." Proceedings of the 2.sup.nd International Workshop for Parsing Technologies. cited by other .
Manning, Christopher and Hinrich Schutze. 1999. Foundations of Statistical Natural Language Processing. Cambridge, MA: MIT Press. cited by other .
McCallum, A., K. Nigam, S. Thrun, and T. Mitchell. 1988. "Learning to Classify Text from Labeled and Unlabeled Documents." Proceedings of the 1998 National Conference on Artificial Intelligence, Jul. 1998. cited by other .
McCallum, A., R. Rosenfeld., T. Mitchell and A. Ng. 1998. "Improving Text Classification by Shrinkage in a Hierarchy of Classes," Proceedings of the 1998 International Conference on Machine Learning. cited by other .
Pollard, Carl and Ivan Sag. 1994. Head-Driven Phrase Structure Grammar. Chicago, IL: University of Chicago Press. cited by other .
Dirk van Eylen, "Ranking of search results using AltaVista", http://ping4.ping.be/.about.ping0658/avrank.html. cited by other .
Avrim Blum, Tom Mitchell, "Combining Labeled and Unlabeled Data with Co-Training", Proceedings of the 1998 conference on Computational Learning Theory. cited by other.

Primary Examiner: Abebe; Daniel
Attorney, Agent or Firm: Banner & Witcoff, Ltd.

Parent Case Text

Applicants hereby incorporate by reference co-pending application Ser. No. 09/627,295 filed in the U.S. Patent and Trademark Office on Jul. 27, 2000, entitled "Concept-Based Search and Retrieval System."

Claims

What is claimed is:

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.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to an ontological parser for natural language processing. More particularly, the present invention relates to a system and method for ontological parsing of natural language that provides a simple knowledge-base-style representation format for the manipulation of natural-language documents. The system utilizes unstructured text as input and produces a set of data structures representing the conceptual content of the document as output. The data is transformed using a syntactic parser and ontology. The ontology is used as a lexical resource. The output that results is also an ontological entity with a structure that matches the organization of concepts in natural language. The resulting ontological entities are predicate-argument structures designed in accordance with the best practices of artificial intelligence and knowledge-base research.

The ontology-based parser is designed around the idea that predicate structures represent a convenient approach to searching through text. Predicate structures constitute the most compact possible representation for the relations between grammatical entities. Most of the information required to construct predicates does not need to be stored, and once the predicates have been derived from a document, the predicates may be stored as literal text strings, to be used in the same way. The system and method of ontology-based parsing of the present invention is directed towards techniques for deriving predicate structures with minimal computational effort.

In addition, the ontology-based parser is designed to permit the use of arithmetic operations instead of string operations in text-processing programs, which employ the ontology-based parser. The output predicate structures contain numeric tags that represent the location of each concept within the ontology. The tags are defined in terms of an absolute coordinate system that allows calculation of conceptual similarity according to the distance within a tree structure. All applications making use of the fact that the output of the ontology-based parser is an ontological entity may realize enormous speed benefits from the parameterized ontology that the parser utilizes.

2. Background of the Invention

Numerous techniques have been developed to process natural language input. These techniques tend to be complicated and cumbersome. Often numerous passes through the input sentence(s) are required to fully parse the input, thereby adding to the time required to parse the input. Often the previous techniques do not have very robust feature checking capabilities. In particular, the techniques do not check for both syntactic and semantic compatibility. Often these techniques expend significant time trying to parse words that can be pruned or filtered according to their information.

The previous techniques of natural language processing are often limited to the performance of a particular purpose and cannot be used for other purposes. Conventional parsing techniques may be designed to function as part of a grammar checking system, but cannot function as part of a search engine, summarization application, or categorization application.

Furthermore, conventional parsing techniques do not take full advantage of an ontology as a lexical resource. This limits the versatility of the techniques.

U.S. Pat. No. 4,864,502 to Kucera et al. discloses a device that tags and parses natural-language sentences, and provides interactive facilities for grammar correction by an end user. The system taught by Kucera et al. has a complicated analysis, and cannot afford semantic status to each word relative to all the other words within the dictionary. The Kucera et al. system uses three parsing stages, each of which needs more than one pass through the sentence to complete its analysis.

U.S. Pat. No. 4,887,212 to Zamora et al. discloses a parser for syntactic analysis of text using a fast and compact technique. After part-of-speech tagging and disambiguation, syntactic analysis occurs in four steps. The grammar of Zamora et al. operates by making multiple passes to guess at noun phrases and verb phrases and then attempts to reconcile the results. Furthermore, the grammar violation checking technique of the Zamora et al. system checks only for syntactic correctness.

U.S. Pat. No. 4,914,590 to Loatman et al. discloses a natural language understanding system. The goal of the Loatman et al. system is to provide a formal representation of the context of a sentence, not merely the sentence itself. Case frames used in Loatman et al. require substantial hard-coded information to be programmed about each word, and a large number of case frames must be provided to obtain reasonable coverage.

Tokuume et al., U.S. Pat. No. 5,101,349, discloses a natural language processing system that makes provisions for validating grammar from the standpoint of syntactic well-formedness, but does not provide facilities for validating the semantic well-formedness of feature structures.

U.S. Pat. No. 5,146,496 to Jensen discloses a technique for identifying predicate-argument relationships in natural language text. The Jensen system must create intermediate feature structures to store semantic roles, which are then used to fill in predicates whose deep structures have missing arguments. Post-parsing analysis is needed and the parsing time is impacted by the maintenance of these variables. Additionally, semantic feature compatibility checking is not possible with Jensen's system.

U.S. Pat. No. 5,721,938 to Stuckey discloses a parsing technique, which organizes natural language into symbolic complexes, which treat all words as either nouns or verbs. The Stuckey system is oriented towards grammar-checker-style applications, and does not produce output suitable for a wide range of natural-language processing applications. The parser of the Stuckey system is only suitable for grammar-checking applications.

U.S. Pat. No. 5,960,384 to Brash discloses a parsing method and apparatus for symbolic expressions of thought such as English-language sentences. The parser of the Brash system assumes a strict compositional semantics, where a sentence's interpretation is the sum of the lexical meanings of nearby constituents. The Brash system cannot accommodate predicates with different numbers of arguments, and makes an arbitrary assumption that all relationships are transitive. The Brash system makes no provisions for the possibility that immediate relationships are not in fact the correct expression of sentence-level concepts, because it assumes that syntactic constituency is always defined by immediate relationships. The Brash system does not incorporate ontologies as the basis for its lexical resource, and therefore does not permit the output of the parser to be easily modified by other applications. Furthermore, the Brash system requires target languages to have a natural word order that already largely corresponds to the style of its syntactic analysis. Languages such as Japanese or Russian, which permit free ordering of words, but mark intended usage by morphological changes, would be difficult to parse using the Brash system.

The patent to Hemphill et al. (U.S. Pat. No. 4,984,178) discloses a chart parser designed to implement a probabilistic version of a unification-based grammar. The decision-making process occurs at intermediate parsing stages, and parse probabilities are considered before all parse paths have been pursued. Intermediate parse probability calculations have to be stored, and the system has to check for intermediate feature clashes.

U.S. Pat. No. 5,386,406 to Hedin et al. discloses a system for converting natural-language expressions into a language-independent conceptual schema. The output of the Hedin et al. system is not suitable for use in a wide variety of applications (e.g. machine translation, document summarization, categorization). The Hedin et al. system depends on the application in which it is used.

SUMMARY OF THE INVENTION

The foregoing and other deficiencies are addressed by the present invention, which is directed to an ontology-based parser for natural language processing. More particularly, the present invention relates to a system that provides a simple knowledge-base-style representation format for the manipulation of natural-language documents. The system utilizes unstructured text as input and produces a set of data structures representing the conceptual content of the document as output. The data is transformed using a syntactic parser and ontology. The ontology is used as a lexical resource. The output that results is also an ontological entity with a structure that matches the organization of concepts in natural language. The resulting ontological entities are predicate-argument structures designed in accordance with the best practices of artificial intelligences and knowledge-base research.

The design of the ontology-based parser is based on the premise that predicate structures represent a convenient approach to searching through text. Predicate structures constitute the most compact possible representation for the relations between grammatical entities. Most of the information required to construct predicates does not need to be stored, and once the predicates have been derived from a document, the predicates may be stored as literal text strings, to be used in the same way. The ontology-based parser of the present invention is directed towards techniques for deriving predicate structures with minimal computational effort.

In addition, the ontology-based parser is designed to permit the use of arithmetic operations instead of string operations in text-processing programs, which employ the ontology-based parser. The output predicate structures contain numeric tags that represent the location of each concept within the ontology. The tags are defined in terms of an absolute coordinate system that allows calculation of conceptual similarity according to the distance within a tree structure. All applications making use of the fact that the output of the ontology-based parser is an ontological entity may realize enormous speed benefits from the parameterized ontology that the parser utilizes.

The present system imposes a logical structure on text, and a semantic representation is the form used for storage. The present system further provides logical representations for all content in documents. The advantages of the present system are the provision of a semantic representation of comparable utility with significantly reduced processing requirements, and no need to train the system to produce semantic representations of text content.

The system and method for ontological parsing of natural language according to the present invention has a far simpler analysis process than conventional parsing techniques, and utilizes a dictionary containing tags with syntactic information. The preferred implementation of the present system and method affords semantic status to each word relative to all the other words within the dictionary, and uses a single-pass context-free grammar to provide complete predicate structures containing subject and object relationships. The system and method of the present invention also provides a robust feature-checking system that accounts for semantic compatibility as well as syntactic compatibility.

The ontology of the present invention converts all inflected words to their canonical forms. Additionally, the system and method can filter lexical items according to their information content. For example, in an information retrieval application, it is capable of pulling out stopwords and unintended query words (as in the pseudo-concept and pseudo-predicate filters). In one embodiment, the grammar of the system and method of the present invention operates in a single pass to produce predicate structure analyses, and groups noun phrases and verb phrases as they occur, not by making multiple passes to guess at them and then attempting to reconcile the results. In the embodiment discussed above, the grammar violation checking of the system and method of the present invention filters both by the probability of a syntactically successful parse and the compatibility of the lexical semantics of words in the ontology. The compatibility referred to here is the self-consistent compatibility of words within the ontology; no particular requirement is imposed to force the ontology to be consistent with anything outside the present system.

In the predicate representation scheme of the present invention, there are only a few distinct frames for predicate structures, as many as needed to cover the different numbers of arguments taken by different verbs. Predicates may be enhanced with selectional restriction information, which can be coded automatically for entire semantic classes of words, rather than on an individual basis, because of the ontological scheme.

The manner in which the present invention constructs parse trees, from which predicate structures and their arguments can be read directly, uses context-free grammars, which result in faster execution. The system of the present invention maintains arguments as variables during the parsing process, and automatically fills in long-distance dependencies as part of the parsing process. No post-parsing analysis is needed to obtain this benefit, and the parsing time is not impacted by the maintenance of these variables, thus resulting in faster parsing execution. Additionally, the ontologies used permit semantic feature compatibility checking.

The system and method of the present invention isolates predicate-argument relationships into a consistent format regardless of text types. The predicate-argument relationships can be used in search, grammar-checking, summarization, and categorization applications, among others.

The system and method of the present invention can accommodate predicates with different numbers of arguments, and does not make arbitrary assumptions about predicate transitivity or intransitivity. Instead the system and method of the present invention incorporates a sophisticated syntactic analysis component, which allows facts about parts-of-speech to determine the correct syntactic analysis. Additionally, by incorporating ontologies as the basis for the lexical resource, the present invention permits the output of the parser to be easily modified by other applications. For example, a search engine incorporating our parser can easily substitute words corresponding to different levels of abstraction into the arguments of a predicate, thus broadening the search. As long as grammatical roles can be identified, the present system and method can be easily adapted to any language. For example, certain case-marked languages, such as Japanese or German, can be parsed through a grammar which simply records the grammatical relationships encoded by particular markers, and the resulting output is still compatible with the parsing results achieved for other languages.

From the foregoing, it is an object of the present invention to provide a system and method for parsing natural language input that provides a simple knowledge-base-style representation format for the manipulation of natural-language documents.

Another object of the present invention is to provide a system and method for parsing natural language input that utilizes unstructured text as an input and produces a set of data structures representing the conceptual content of the document as output, where the output is an ontological entity with a structure that matches the organization of concepts in natural language.

Still another object of the present invention is to provide a system and method for parsing natural language input that transforms data using a syntactic parser and ontology, where the ontology is used as a lexical resource.

Yet another object of the present invention is to provide a system and method for parsing natural language input that provides ontological entities as output that are predicate-argument structures.

Another object of the present invention is to provide a system and method for parsing natural language input that derives predicate structures with minimal computational effort.

Still another object of the present invention is to provide a system and method for parsing natural language input that permits the use of arithmetic operations in text-processing programs, where the output predicate structures contain numeric tags that represent the location of each concept within the ontology, and the tags are defined in terms of an absolute coordinate system that allows calculation of conceptual similarity according to the distance within a tree structure.

Another object of the present invention is to provide a system and method for parsing natural language input that realizes enormous speed benefits from the parameterized ontology that the parser utilizes.

BRIEF DESCRIPTION OF THE DRAWINGS

These and other attributes of the present invention will be described with respect to the following drawings in which:

FIG. 1 is a block diagram of the sentence lexer according to the present invention;

FIG. 2 is a block diagram of the parser according to the present invention;

FIG. 3 is a diagram showing two complete parse trees produced according to the present invention;

FIG. 4 is an example parse tree according to the present invention;

FIG. 5 is another example parse tree according to the present invention;

FIG. 6 is another example parse tree according to the present invention; and

FIG. 7 is another example parse tree incorporating real words according to the present invention.

DETAILED DESCRIPTION OF THE INVENTION

In the following detailed discussion of the present invention, numerous terms, specific to the subject matter of a system and method for concept-based searching, are used. In order to provide complete understanding of the present invention, the meaning of these terms is set forth below as follows:

The term concept as used herein means an abstract formal representation of meaning, which corresponds to multiple generic or specific words in multiple languages. Concepts may represent the meanings of individual words or phrases, or the meanings of entire sentences. The term predicate means a concept that defines an n-ary relationship between other concepts. A predicate structure is a data type that includes a predicate and multiple additional concepts; as a grouping of concepts, it is itself a concept. An ontology is a hierarchically organized complex data structure that provides a context for the lexical meaning of concepts. An ontology may contain both individual concepts and predicates.

The 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 predicate structures.

The ontological parser is designed to be modular, so that improvements and language-specific changes can be made to individual components without reengineering the other components. The components are discussed in detail below.

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.

Ontological parsing is a grammatical analysis technique built on the proposition that the most useful information that can be extracted from a sentence is the set of concepts within it, as well as their formal relations to each other. Ontological parsing derives its power from the use of ontologies to situate words within the context of their meaning, and from the fact that it does not need to find the correct purely syntactic analysis of the structure of a sentence in order to produce the correct analysis of the meaning of a sentence.

An ontological parser is a tool that transforms natural-language sentences into predicate structures. Predicate structures are representations of logical relationships between the words in a sentence. Every predicate structure contains a predicate, which is either a verb or a preposition, and a set of arguments, which may be any part of speech. Predicates are words which not only have intrinsic meaning of their own, but which also provide logical relations between other concepts in a sentence. Those other concepts are the arguments of the predicate, and are generally nouns, because predicate relationships are usually between entities.

As stated previously, the ontological parser has two major components, a sentence lexer 100 and a parser 200. The sentence lexer 100 is a tool for transforming text strings into ontological entities. The parser is a tool for analyzing syntactic relationships between entities.

Referring to FIG. 1, the sentence lexer 100 is shown. Document iterator 120 receives documents or text input 110, and outputs individual sentences to the lexer 130. As the lexer 130 receives each sentence, it passes each individual word to the ontology 140. If the word exists within the ontology 140, it is returned as an ontological entity; if not, it is returned as a word tagged with default assumptions about its ontological status. In one embodiment, words are automatically assumed to be nouns; however, the words may be other parts of speech.

After the lexer 130 has checked the last word in a sentence against the contents of the ontology 140, the unparsed sentence is passed to a series of lexer filters 150. Lexer filters 150 are modular plug-ins, which modify sentences based on knowledge about word meanings. The preferred embodiment contains several filters 150, although more may be developed, and existing filters may be removed from future versions, without altering the scope of the invention. For example, in an information retrieval application, an ontological parser may employ the following filters: proper noun filter, adjective filter, adverb filter, modal verb filter, and stop word filter. Similarly, for information retrieval purposes, an embodiment of the ontological parser optimized for queries may make use of all these filters, but add a pseudo-predicate filter and a pseudo-concept filter.

The stop word filter removes stop words from sentences. Stop words are words that serve only as placeholders in English-language sentences. The stop word filter will contain a set of words accepted as stop words; any lexeme whose text is in that set is considered to be a stop word.

An adjective filter serves to remove lexemes representing adjective concepts from sentences. Adjective filter checks each adjective for a noun following the adjective. The noun must follow either immediately after the adjective, or have only adjective and conjunction words appearing between the noun and the adjective. If no such noun or conjunction is found, the adjective filter will veto the sentence. The noun must also meet the selectional restrictions required by the adjective; if not, the adjective filter will veto the sentence. If a noun is found and it satisfies the restrictions of the adjective, the adjective filter will apply the selectional features of the adjective to the noun by adding all of the adjective's selectional features to the noun's set of selectional features.

The proper noun filter groups proper nouns in a sentence into single lexical nouns, rather than allowing them to pass as multiple-word sequences, which may be unparsable. A proper noun is any word or phrase representing a non-generic noun concept. Although a number of proper nouns are already present in the lexicon, they are already properly treated as regular lexical items. Since proper nouns behave syntactically as regular nouns, there is no need to distinguish proper nouns and nouns already in the lexicon. The purpose of the proper noun filter is to ensure that sequences not already in the lexicon are treated as single words where appropriate.

The modal verb filter removes modal verbs from sentence objects. Modal verbs are verbs such as "should", "could", and "would". Such verbs alter the conditions under which a sentence is true, but do not affect the basic meaning of the sentence. Since truth conditions do not need to be addressed by the ontological parser 120 or 140, such words can be eliminated to reduce parsing complexity. The modal verb filter will contain a set of modal verbs similar to the stop word list contained in stop word filter. Any Lexeme whose text is in that set and whose concept is a verb is identified as a modal verb, and will be removed.

The adverb filter removes Lexemes containing adverb concepts from sentences. Adverbs detail the meaning of the verbs they accompany, but do not change them. Since the meaning of the sentence remains the same, adverbs can be removed to simplify parsing.

The pseudo-predicate filter operates in one embodiment, as a query ontological parser.