In general, a computer is a digital machine that uses precise languages with absolute values, such as “on”, “off”, “1”, “0”, “3+4”, “AND”, and “XOR”. In contrast, a human is an analog, biological machine that inherently uses imprecise languages with few or no absolute values. Since computers are tools for human use, input devices and input processing system are needed for human to use the computer tools.
Since it is generally easier to train humans to conform to the digital requirements of computers than vice versa, humans have used precise input interfaces such as a keyboard and a mouse. In addition, the computer is often only required to receive the input and not to process it for syntax and semantics.
In the past, this has been the situation because of limited processing capabilities of typical computers and because of the inherent difficulties of modeling imprecise human language within a digital computer. However, as typical computing power increases, natural language processing systems are being used by computers to “understand” imprecise human language.
Natural Language Processing
A natural language processing (NLP) system is typically a computer-implemented software system, which intelligently derives meaning and context from an input string of natural language text. “Natural languages” are the imprecise languages that are spoken by humans (e.g., English, French, Japanese). Without specialized assistance, computers cannot distinguish linguistic characteristics of natural language text. For instance, a sentence in a natural language text read as follows:Betty saw a bird.
A student of English understands that, within the context of this sentence, the word “Betty” is a noun, the word “saw” is a verb, the word “a” is an adjective, and the word “bird” is a noun. However, in the context of other sentences, the same words might assume different parts of speech. Consider the following sentence:Use a saw.
The English student recognizes that the word “use” is a verb, the word “a” is an adjective, and the word “saw” is a noun. Notice that the word “saw” is used in the two sentences as different parts of speech—a verb and a noun—which an English speaking person realizes. To a computer, however, the word “saw” is represented by the same bit stream and hence can be identical for both sentences. The computer is equally likely to consider the word “saw” as a noun as it is a verb, in either sentence.
A NLP system assists the computer in distinguishing how words are used in different contexts and in applying rules to construct syntactical and meaning representations. A NLP system has many different applications where a computer derives meaning and information from the natural language of a human. Such applications include speech recognition, handwriting recognition, grammar checking, spell checking, formulating database searches, and language translation.
The core of a NLP system is its parser. Generally, a parser breaks an utterance (such as a phrase or sentence) down into its component parts with an explanation of the form, function, and syntactical relationship of each part.
NLP Parser
The NLP parser takes a phrase and builds for the computer a representation of the syntax of the phrase that the computer can understand. A parser may produce multiple different representations for a given phrase. The representation makes explicit the role each word plays and the relationships between the words, much in the same way as grade school children diagram sentences. In addition to “diagramming” a sentence, the parser ranks the multiple diagrams in order of most likely meaning to least likely.
Herein, an utterance is equivalent to a phrase. A phase is a sequence of words intended to have meaning. In addition, a sentence is understood to be one or more phrases. In addition, references herein to a human speaker include a writer and speech includes writing.
FIG. 1 shows a NLP parser 20 of a typical NLP system. The parser 20 has four key components:                Tokenizer 28;        Grammar Rules Interpreter 26;        Searcher 30; and        Parse Ranker 34.        
The parser 20 receives a textual string 22. Typically, this is a sentence or a phrase. The parser also receives grammar rules 24. These rules attempt to codify and interpret the actual grammar rules of a particular natural language, such as English. Alternatively, these rules may be stored in memory within the parser.
The grammar rules interpreter 26 interprets the codified grammar rules. The tokenizer 28 identifies the words in the textual string 22, looks them up in a dictionary, makes records for the parts of speech (POS) of a word, and passes these to the searcher.
The searcher 30 in cooperation with the grammar rules interpreter generates multiple grammatically correct parses of the textual string. The searcher sends it results to the parse ranker 34.
The parse ranker 34 mathematically measures the “goodness” of each parse and ranks them. “Goodness” is a measure of the likelihood that such a parse represents the intended meaning of the human speaker (or writer). The ranked output of the parser ranker is the output of the ranker. This output is one or more of parses 38 ranked from most to least goodness.
Foundational Concepts
Three concepts form the foundation for understanding the invention described herein: statistics, linguistics, and computational linguistics.
Statistics is the branch of mathematics that deals with the relationships among and between groups of measurements, and with the relevance of similarities and differences in those relationships.
Linguistics is the analytic study of human natural language.
Computational linguistics is the analytic study of human natural language within computer science to mathematically represent language rules such as grammar, syntax, and semantics.
Statistics
Probability. The expression “Prob(x)” is the probability of event x occurring. The result of Prob(x) is a number between zero (0) and one (1), where zero means that the event never occurs and one means that it always occurs. For example, using a six-sided fair die with the sides labeled 1-6, the probability of rolling a three is ⅙. Similarly, using a randomly shuffled deck of cards (All examples using a deck of cards are based upon a standard American deck of cards having four suits (spades, hearts, diamonds, clubs) and thirteen cards per suit:Prob(top card is an Ace)= 1/13Prob(top card is a club)=¼Prob(top card is 3 of diamonds)= 1/52
Estimating Probabilities using Training Data. The probability of events using a randomly shuffled deck or fair die can be mathematically derived. However, in many cases, there is no mathematical formula for a probability of a given event. For example, assume that one wished to determine the probability of rolling a three given a weighted die. The probability may be ⅙ (as it would be with a fair die), but it is likely to be more or less than that depending upon how the die is weighted.
How would one estimate the probability? The answer is to run an experiment. The die is thrown many times and the number of rolls where “3” is rolled is counted. This data is called the “training data”. It is sometimes called the “training corpus.” To determine the probability of rolling a three in the future, it is assumed that the behavior of the die in the future will be the same as it was during our experiment and thus:             Prob      ⁡              (        event        )              =                  Count        ⁡                  (          event          )                            Total        ⁢                                   ⁢        number        ⁢                                   ⁢        of        ⁢                                   ⁢        events                        Prob      ⁡              (                  roll          ⁢                                           ⁢          is          ⁢                                           ⁢          a          ⁢                                           ⁢          3                )              =                  Count        ⁡                  (                      number            ⁢                                                   ⁢            of            ⁢                                                   ⁢            3            ⁢                                                   ⁢            rolls            ⁢                                                   ⁢            in            ⁢                                                   ⁢            the            ⁢                                                   ⁢            experiment                    )                            Total        ⁢                                   ⁢        #        ⁢                                   ⁢        of        ⁢                                   ⁢        rolls        ⁢                                   ⁢        in        ⁢                                   ⁢        the        ⁢                                   ⁢        experiment            
In general, the accuracy of the estimate increases as the amount of training data increases. Theoretically, the estimates increase in accuracy as the amount of training data increases.
Conditional Probability. Conditional probabilities are used when there is additional information known about an event that affects the likelihood of the outcome. The notation used is Prob(x|y) meaning. “What is the probability of an unknown event x occurring given that known event y occurred.”
Conditional probability is defined to be:                               Prob          (                      x            |            y                    )                =                ⁢                              Prob            ⁡                          (                                                x                  &                                ⁢                                                                   ⁢                y                            )                                            Prob            ⁡                          (              y              )                                                              =                ⁢                                            Count              ⁡                              (                                                      x                    &                                    ⁢                                                                           ⁢                  y                                )                                                    Total              ⁢                                                           ⁢              #              ⁢                                                           ⁢              of              ⁢                                                           ⁢              events                                                          Count              ⁡                              (                y                )                                                    Total              ⁢                                                           ⁢              #              ⁢                                                           ⁢              of              ⁢                                                           ⁢              events                                                              =                ⁢                              Count            ⁡                          (                                                x                  &                                ⁢                                                                   ⁢                y                            )                                            Count            ⁡                          (              y              )                                          
When the known event is predicative of the outcome, knowing the conditional probabilities is better than knowing just the unconditional probability. For example, assume that a man is in a casino playing the following game. The man then can bet $1 or pass. The House rolls a pair of dice. If the man bets and if the dice sum to 12, the man gets $35, otherwise the man loses his bet. Since the probability of rolling two die that sum to 12 is 1/36, the man should expect to lose money playing this game. On average, the man will make only $35 for every $36 that he bets.
Now suppose that the man had a fairy godmother that could whisper in his ear and tell him whether one of the die rolled was going to be a six. Knowing this, the probabilities of rolling a twelve are:Prob(two die summing to 12|one die is a 6)=⅙Prob(two die summing to 12|neither die is a 6)=0
With the fairy godmother's help, the man can make money on the game. The strategy is to only bet when the fairy godmother says that one of the die is a six. On average, the man should expect to make $35 for every $6 that he bets.
As another example, consider the problem of predicting what the next word in a stream of text will be. E.g., is the next word after “home” more likely to be “table” or “run.”? Wordi represents the ith word in the lexicon and Prob(wordi) is the probability that wordi will be the next word in the stream. The standard approach (using unconditional probability) for computing Prob(wordi) is to take a training corpus and count up the number of times the word appears. This formula represents this approach:       Prob    ⁡          (              word        i            )        =            Count      ⁡              (                  word          i                )                    Total      ⁢                           ⁢      #      ⁢                           ⁢      of      ⁢                           ⁢      words      ⁢                           ⁢      in      ⁢                           ⁢      the      ⁢                           ⁢      training      ⁢                           ⁢      corpus      
Better results are achieved by using conditional probabilities. In English, words don't appear in a random order. For example, “Table red the is” is highly unlikely but “The table is red” is common. Put another way, the last word in a stream is predicative of the next word that will follow. For example, if the last word in a stream is “the” or “a”, then the next word is usually either an adjective or noun, but is rarely a verb. If the last word in a stream is “clever”, then the next word is likely to be an animate noun like “boy” or “dog” and not likely to be an inanimate noun like “stone.”
By making use of this information, the next word that will appear in a stream of text may be better predicted. If every pair of words in our lexicon is considered and a record of how often that pairs appear is kept, the probability of a specific word pairing is:       Prob    (                  word        i            |                        word          k                ⁢                                   ⁢        appears        ⁢                                   ⁢        before        ⁢                                   ⁢                  word          i                      )    =            Count      ⁢                           ⁢              (                              word            i                    ⁢                                           ⁢          and          ⁢                                           ⁢                      (                                          word                k                            ⁢                                                           ⁢              before              ⁢                                                           ⁢                              word                i                                      )                          )                    Count      ⁢                           ⁢              (                  word          k                )            
This conditional probability is much more accurate than Prob(wordi). This technique is commonly used by conventionally speech recognizers to predict what words are likely to follow a given speech fragment.
Sparse Data Problem. The sparse data problem occurs when there is not enough data in a training corpus to distinguish between events that never occur versus events that are possible but just didn't happen to occur in the training corpus. For example, Prob(wordi+1|wordi) is being computed by counting how often pairs of words occur in the corpus. If in the training corpus the pair of words “gigantic” and “car” never appears, it would be wrong to conclude that it is impossible in the English language to have the words “gigantic” and “car” together.
In general, natural languages have nearly an infinite number of possible word, phrase, and sentence combinations. The training corpus used to determine conditional probabilities must necessarily be a subset of this set of infinite combinations. Thus, the sparse data problem results in poor probabilities with a given combination when the training corpus did not include that given combination.
Chain Rule.Prob(a, b|c)=Prob(a|c) Prob(b|a, c)Linguistics
Linguistics is the scientific study of language. It endeavors to answer the question—what is language and how it is represented in the mind? Linguistics focuses on describing and explaining language.
Linguistics focuses on languages' syntax (sentence and phrase structures), morphology (word formation), and semantics (meaning). Before a computer representation model of a natural language can be generated and effectively used, the natural language must be analyzed. This is the role of linguistics.
Part of Speech. Linguists group words of a language into classes, which show similar syntactic behavior, and often a typical semantic type. These word classes are otherwise called “syntactic” or “grammatical categories”, but more commonly still by the traditional names “part of speech” (POS). For example, common POS categories for English include noun, verb, adjective, preposition, and adverb.
Word Order and Phrases. Words do not occur in just any order. Languages have constraints on the word order. Generally, words are organized into phrases, which are groupings of words that are clumped as a unit. Syntax is the study of the regularities and constraints of word order and phrase structure. Among the major phrase types are noun phrases, verb phrases, prepositional phrases, and adjective phrases.
Headword. The headword is the key word in a phrase. This is because it determines the syntactic character of a phrase. In a noun phrase, the headword is the noun. In a verb phrase, it is the main verb. For example, in the noun phrase “red book”, the headword is “book.” Similarly, for the verb phrase “going to the big store”, the headword is “going.”
Modifying Headword. A modifying headword is the headword of a sub-phrase within a phrase where the sub-phrase modifies the main headword of the main phrase. Assume a phrase (P) has a headword (hwP) and a modifying sub-phrase (M) within the P that modifies hwP. The modifying headword (hwM) is the headword of the modifying subphrase (M).
For example, if the phrase is “The red bear growled at me”, the headword is “growled,” the modifying phrase is “the red bear,” and the modifying headword is “bear.” If the phrase is “running to the store”, then the headword is “running”, the modifying phrase is “to the store”, and the modifying headword is “to.”
Syntactic Features. Syntactic features are distinctive properties of a word relating to how the word is used syntactically. For example, the syntactic features of a noun include whether it is singular (e.g. cat) or plural (e.g. cats) and whether it is countable (e.g. five forks) or uncountable (e.g. air). The syntactic feature of a verb includes whether or not it takes an object:                Intransitive verbs do not take an object. For example, “John laughed,” and “Bill walked,”        Mono-transitive verbs take a single direct object. For example, “I hit the ball”,        Di-transitive verbs take a direct and an indirect object. For example, “I gave Bill the ball,” and “I promised Bill the money”        
Lemma of Headwords. The syntactic and semantic behavior of a headword is often independent of its inflectional morphology. For example, the verbs “walks”, “walking”, and “walked” are derived from the verb “walk”. The transitivity of a verb is independent of such inflection.
Computational Linguistics
Transitions (i.e., Rewrite Rules). The regularities of a natural language's word order and grammar are often captured by a set of rules called “transitions” or “rewrite rules.” The rewrite rules are a computer representation of rules of grammar. These transitions are used to parse a phrase.
A rewrite rules has the notation form: “symbolA→symbolB symbolC . . . ”. This indicates that symbol (symbolA) on the left side of the rule may be rewritten as one or more symbols (symbolB, symbolC, etc.) on the right side of the rule.
For example, symbolA may be “s” to indicated the “start” of the sentence analysis. SymbolB may be “np” for noun phrase and symbolC may be “vp” for verb phrase. The “np” and “vp” symbols may be further broken down until the actual words in the sentence are represented by symbolB, symbolC, etc.
For convenience, transitions can be named so that the entire rule need not be recited each time a particular transition is referenced. In Table 1 below the name of the transitions are provided under the “Name” heading. The actual transitions are provided under the “Transition” heading. Table 1 provides an example of transitions being used to parse a sentence like “Swat flies like ants”.
TABLE 1NameTransition (i.e., rewrite rule)s_npvps →  np vps_vps →    vpnp_nounnp →    nounnp_nounppnp →    noun ppnp_nounnpnp →    noun npvp_verbvp →    verbvp_verbnpvp →    verb npvp_verbppvp →    verb ppvp_verbnpppvp →    verb np pppp_prepnppp →    prep nppref_likeprep →    likeverb_swatverb →    swatverb_fliesverb →    fliesverb_likeverb →    likenoun_swatnoun →    swatnoun_fliesnoun →    fliesnoun_antsnoun →    ants
In Table 1 above, the transition names (on the left-hand column) represent and identify the transition rule (on the right-hand column). For example, “np_nounpp” is the name for “np→noun pp” rule, which means that “noun phrase” may be rewritten as “noun” and “prepositional phrase.”
Context Free Grammar (CFG). The nature of the rewrite rules is that a certain syntactic category (e.g., noun, np, vp, pp) can be rewritten as one or more other syntactic categories or words. The possibilities for rewriting depend solely on the category, and not on any surrounding context, so such phrase structure grammars are commonly referred to as context-free grammars (CFG).
FIG. 2 illustrates a CFG parse tree 50 of a phrase (or sentence). This tree-like representation of the sentence “flies like ants” is deconstructed using a CFG set of rewrite rules (i.e., transitions). The tree 50 has leaf nodes (such as 52a-52c and 54a-54g.)
The tree 50 includes a set of terminal nodes 52a-52c. These nodes are at the end of each branch of the tree and cannot be further expanded. For example, “like” 52b cannot be expanded any further because it is the word itself.
The tree 50 also includes a set of non-terminal nodes 54a-54g. These nodes are internal and may be further expanded. Each non-terminal node has immediate children, which form a branch (i.e., “local tree”). Each branch corresponds to the application of a transition. For example, “np” 54b can be further expanded into a “noun” by application of the “np_noun” transition.
Each non-terminal node in the parse tree is created via the application of some rewrite rule. For example, in FIG. 2, the root node 54a was created by the “s→np vp” rule. The “VP” node 54d by the “s→verb np” rule.
The tree 50 has a non-terminal node 54a designated as the starting node and it is labeled “s.”
In general, the order of the children in each branch generates the word order of the sentence, and the tree has a single root node (in FIG. 2 it is node 54a), which is the start of the parse tree.
Segtypes. A non-terminal node has a type that is called its “segtype.” In FIG. 2, each non-terminal node 54a-g is labeled with its segtype. A node's segtype identifies the rule that was used to create the node (working up from the terminal nodes). In Table 1 above, the segtypes are shown under the “transition” heading and to the left of the “→” symbol. For example, the segtype of node 54b in FIG. 2 is “np” because the rule “np→noun” was used to create the node.
In given grammar, a segtype can be many different values including, for example: NOUN, NP (noun phrase), VERB, VP (verb phrase), ADJ (adjective), ADJP (adjective phrase), ADV (adverb), PREP (preposition), PP (prepositional phrase), INFCL (infinitive clauses), PRPRT (present participial clause) PTPRT (past participial clause), RELCL (relative clauses), and AVPVP (a verb phrase that has a verb phrase as its head).
Node-Associated Functional Notation. In this document, a functional notation is used to refer to the information associated with a node. For example, if a variable “n” represents a node in the tree, then “hw(n)” is the headword of node “n.”
The following functions are used throughout this document:                hw(n) is the headword of node n        segtype(n) is the segtype of node n        trans(n) is the transition (rewrite rule) associated with node n (e.g., the rules under the heading “Transition” in Table 1)        trn(n) is the name of the transition (e.g., the names under the heading “Names” in Table 1)        modhw(n) is the modifying headword of node n        
Annotated Parse Tree. A parse tree can be annotated with information computed during the parsing process. A common form of this is the lexicalized parse tree where each node is annotated with its headword. One can annotate a parse tree with additional linguistic information (e.g. syntactic features).
FIG. 3 shows an example of such a lexicalized parse tree 60. (For the purposes of this example, directional path 66 with circled reference points is ignored.) FIG. 3 is a parse tree of one of many parses of the sentence, “swat flies like ants.” Terminal nodes 62a-d, which are the words of the sentence, are not annotated. Non-terminal nodes 64a-i are annotated. For example, node 64h has a segtype of “noun” and is annotated with “hw=ants”. This means that its headword is “ants.”
The parse tree 60 in FIG. 3 is also annotated with the names of the transitions between nodes. For example, the transition name “vp_verbvp” is listed between node 64f and node 64h. 
Probabilistic Context Free Grammar (PCFG). A PCFG is a context free grammar where every transition is assigned a probability from zero to one. PCFGs have commonly been used to define a parser's “goodness” function. “Goodness” is a calculated measurement of the likelihood that a parse represents the intended meaning of the human speaker. In a PCFG, trees containing transitions that are more probable are preferred over trees that contain less probable transitions.
Since the probability of a transition occurring cannot be mathematically derived, the standard approach is to estimate the probabilities based upon a training corpus. A training corpus is a body of sentences and phrases that are intended to represent “typical” human speech in a natural language. The speech may be intended to be “typical” for general applications, specific applications, and/or customized applications. This “training corpus” may also be called “training data.”
Thus, the probabilities are empirically derived from analyzing a training corpus. Various approaches exist for doing this. One of the simplest approaches is to use an unconditional probability formula like this:             Prob      ⁡              (        event        )              =                  Count        ⁡                  (          event          )                            Total        ⁢                                   ⁢        number        ⁢                                   ⁢        of        ⁢                                   ⁢        events                        Prob      ⁡              (                  trans          i                )              =                  Count        ⁡                  (                      times            ⁢                                                   ⁢                          trans              i                        ⁢                                                   ⁢            appears                    )                            Total        ⁢                                   ⁢        #        ⁢                                   ⁢        of        ⁢                                   ⁢        transitions        ⁢                                   ⁢        in        ⁢                                   ⁢        the        ⁢                                   ⁢        training        ⁢                                   ⁢        corpus            
However, this approach, by itself, produces inaccurate results because the likelihood that a transition will apply is highly dependent upon the current linguistic context, but this approach does not consider the current linguistic context. This approach simply considers occurrences of specific transitions (transi).
Depth First Tree Walk. In order to analyze each node of a parse tree to rank parse trees, a parser must have a method of “visiting” each node. In other words, the nodes are examined in a particular order.
A “depth first tree walk” is a typical method of visiting all the nodes in a parse tree. In such a walk, all of a node's children are visited before any of the node's siblings. The visitation is typically from top of the tree (i.e., the start node) to the bottom of the tree (i.e., terminal nodes). Such visitation is typically done from left-to-right to correspond to the order of reading/writing in English, but may be done from right-to-left.
The directional path 66 of FIG. 3 shows a depth first tree walk of the parse tree. The sequence of the walk is shown by the directional path 66 with circled reference points. The order of the stops along the path is numbered from 1 to 14 by the circled reference points.
Generative model of syntax. Each sentence-tree pair in a language has an associated top-down derivation consisting of a sequence of rule applications (transitions) of a grammar.
This is an example of how this model may work: Start at the top node. There is a rule that produces the constituents below. Record this rule. Pick the leftmost of the children. If this node does not have children, then visit its sibling to the right. If there is no sibling go up to the parent and visit the parents right sibling. Keep going up and to the right until an unvisited node is found. If all nodes have been visited then we are done. For any node not visited, record the rule and recurse. (This is much easier to describe using code.) This is what is meant by top-down and left to right. This produces a unique representation of the tree.
Augmented Phrase Structured Grammar (APSG). An APSG is a CFG that gives multiple names to each rule, thereby limiting the application of each “named” rule. Thus, for each given rewrite rule there are more than one name and the name limits its use to specific and narrower situations. For example, the structure “VP→NP VP” may have these limiting labels: “SubjPQuant” and “VPwNPl.”
SubjPQuant specifies subject post-quantifiers on a verb phrase. For example, in ”we all found useful the guidelines” “all” is a subject post-qualifier The structure of “all found useful the guidelines” is [NP all][VP found useful the guidelines]. VPwNPl specifies a subject to a verb phrase. For example, in “John hit the ball” [NP John][VP hit the ball] where John is the subject.
An APSG is similar to a CFG in that there are rules that look like CFG rules. But an APSG rule can examine the pieces to decide if it is going to put them together, and it determines and labels the syntactic relation between the children. Because of this, one can have multiple rules that represent VP−>NP VP. This multiple rules can build different syntactic relationships.
The Problem
Given the ambiguity that exists in natural languages, many sentences have multiple syntactic interpretations. The different syntactic interpretations generally have different semantic interpretations. In other words, a sentence has more than one grammatically valid structure (“syntactic interpretation”) and as a result, may have more than one reasonable meaning (“semantic interpretation”). A classic example of this is the sentence, “times flies like an arrow.” There are generally considered to be seven valid syntactic parse trees.
FIGS. 4a and 4b show examples of two of the seven valid parses of this sentence. For the parse tree 70 of FIG. 4a, the object “time” 74 moves in a way that is similar to an arrow. For the parse tree 80 of FIG. 4b, the insects called “time files” 84 enjoy the arrow object; just as one would say “Fruit flies like a meal.”
Either parse could be what the speaker intended. In addition, five other syntactically valid parses may represent the meaning that the speaker intended.
How does a NLP system determine which parse is the “correct” one. It is better to say the most “correct” one. How does a NLP parser judge amongst the multiple grammatically valid parses and select the most “correct” parse?
Previous Approaches
Generally. A parser needs a way to accurately and efficiently rank these parse trees. In other words, the parser needs to compute which parse tree is the most likely interpretation for a sentence, such as “time flies like an arrow.”
Since human language is inherently imprecise, rarely is one parse one hundred percent (100%) correct and the others never correct. Therefore, a parser typically ranks the parser from most likely to be correct to least likely to be correct. Correctness in this situation is a measure of what a human most likely means by a particular utterance.
A conventional approach is to use a “goodness” function to calculate a “goodness measure” of each valid parse. Existing parsers differ in the extent to which they rely on a goodness function, but most parsers utilize one.
A simple parser may generate all possible trees without regard to any linguistic knowledge and then allow the goodness function to do all the work in selecting the desired parse. Alternatively, a parser generates reasonable trees based on linguistic knowledge and then uses the goodness function to choose between the reasonable trees. In either case, the problem is to implement an efficient goodness function that accurately reflects and measures the most likely meaning of an utterance.
Straw Man Approach. The most straightforward approach is the “straw man approach.” The goodness function of this approach computes the probability of a given parse tree based upon how often identical trees appeared in a training corpus. This approach is theoretical and is rarely (if ever) used in practice. This is because it is inaccurate without an impractically huge training corpus that accurately represents nearly all-possible syntactic and semantic constructions within a given language.
Using the straw man approach, the probability of a parse tree is defined to be:       Prob    ⁡          (      parse      )        =            Count      ⁡              (        parse        )                    Total      ⁢                           ⁢      #      ⁢                           ⁢      of      ⁢                           ⁢      trees      ⁢                           ⁢      in      ⁢                           ⁢      the      ⁢                           ⁢      training      ⁢                           ⁢      corpus      
For example, assume in the training corpus the sentence, “time flies like an arrow” appears ten times. The parse represented by the parse tree 70 of FIG. 4a appears in nine of those times. In addition, the parse represented by the parse tree 80 of FIG. 4b appears only once. Thus, the probability of the parse tree 70 of FIG. 4a would be ninety percent.
If the parse of parse tree 70 is the correct parse, then this example provide good results. Note that, the exact sentence had to occur multiple times within the corpus to provide such good results.
Theoretically, given enough training data, the straw man approach can be highly accurate. However, the amount of training data required is astronomical. First, it requires that the tagged training corpus contain all the sentences that the parser is likely to even encounter. Second, the sentences must appear in the correct ratios corresponding to their appearance within the normal usage of the natural language. In other words, common sentences occurring more often than uncommon sentences and in the right proportion.
Creating such a hug training corpus is infeasible. However, working from a smaller corpus creates sparse data problems.
Statistical Hodgepodge Approach. Using this approach, the goodness of a parse may be determined by a collection of mostly unrelated statistical calculations based upon parts of speech, syntactic features, word probabilities, and selected heuristic rules.
A goodness function using such an approach is utilized by the grammar checker in “Office 97” by the Microsoft Corporation. Parser were assigned a score based upon statistical information and heuristic rules. These scores were often called “POD” scores.
Since this hodgepodge approach employs heuristics and does not use a unifying methodology for calculating the goodness measure of parses, there are unpredictable and unanticipated results that incorrectly rank the parses.
Syntactic Bigrams Approach. This approach uses collocations to compute a goodness function. A collocation is two or more words in some adjacent ordering or syntactic relationship. Examples of such include: “strong tea”, “weapons of mass destruction”, “make up”, “the rich and powerful”, “stiff breeze”, and “broad daylight.”
Specifically, syntactic bigrams are two-word collocation. The basic idea is to find the probability of two words of being in a syntactic relationship to each other, regardless of where those words appear in the sentence. The words may be adjacent (e.g., “I drink coffe”), but need not be (e.g., “I love to drink hot black coffee.”). For example, the object of the verb “drink” is more likely to be “coffee” or “beer” than “table”. This can be used to create a goodness function based on “syntactic bigrams.”
If the following four sentences appeared in the training corpus, all four would provide evidence that “coffee” is often the object of the verb “to drink”:I drink coffee.I drink black coffee.I love to drink hot black coffee.I drink on most days of the week, coffee in the morning.
Because of the huge potential number of word combinations, this approach requires a hefty training corpus.
Transition Probability Approach (TPA). A goodness function may be calculated using a generative grammar approach. Each sentence has a top-down derivation consisting of a sequence of rule applications (transitions). The probability of the parse tree is defined to be the product of the probabilities of the transitions.
There are a number of different ways to assign probabilities to the transitions. For this example, the transition probabilities are conditioned on segtype:                               Prob          ⁡                      (            parse            )                          =                ⁢                              Π            i                    ⁢                                           ⁢                      Prob            ⁡                          (                              n                i                            )                                                              =                ⁢                              Π            i                    ⁢                                           ⁢                      Prob            ⁡                          (                                                trans                  ⁡                                      (                                          n                      i                                        )                                                  |                                  segtype                  ⁡                                      (                                          n                      i                                        )                                                              )                                                              =                ⁢                              Π            i                    ⁢                                           ⁢                                    Count              ⁢                                                           ⁢                              (                                                                            trans                      ⁡                                              (                                                  n                          i                                                )                                                              ⁢                                                                                   &                                    ⁢                                                                           ⁢                                      segtype                    ⁡                                          (                                              n                        i                                            )                                                                      )                                                    Count              ⁢                                                           ⁢                              (                                  segtype                  ⁡                                      (                                          n                      i                                        )                                                  )                                                        Where                ni: is the ith node        trans(ni): is the transition out of ni of the form X→Y Z        segtype(ni): is the segtype of ni         Πi is the notation to combine (e.g., multiply) over all nodes i in the parse tree        
For example, suppose that probabilities are assigned to each transition shown in Table 1 above and those probabilities are based upon some training corpus. The training corpus would contain parsed sentences such that the system can count the number of times each transition occurred. In other words, the system counts the number of times each particular grammar rule was used to generate the parse. The result might be:
TABLE 2TransitionCountProb (trans|segtype)s →  np vp80.8Sum = 1.0s →    vp20.2np →    noun80.4Sum = 1.0np →    noun pp100.5np →    noun np20.1vp →    verb40.4Sum = 1.0vp →    verb np20.2vp →    verb pp20.2vp → verb np pp20.2pp →    prep np101Sum = 1.0prep →    like101Sum = 1.0verb →    swat10.1Sum = 1.0verb →    flies50.5verb →    like40.4noun →    swat100.5Sum = 1.0noun →    flies50.25noun →    ants50.25
Using the PCFG represented by Table 2 above, the probability of a parse tree can be computed below as follows:Prob(S)=Prob(s→np vp)*Prob(np→noun np)*Prob(noun→wat)*Prob(np→noun)*Prob(noun→flies)*Prob(vp→verb np)*Prob(verb→like)*Prob(np→noun)*Prob(noun→ants)=0.8*0.04*0.05*0.4*0.4*0.45*0.3*0.4*0.4*0.5=0.000027648
However, this approach does not define a very accurate goodness function. Alone, a PCFG is generally poor at ranking parses correctly. A PCFG prefers common constructions in a language over less common ones.
Ancestor Dependency-Based Generative Approach (ADBGA). This approach assumes a top-down, generative grammar approach. It defines a formulism for computing the probability of a transition given an arbitrary set of linguistic features. Features might include headword, segtype, and grammatical number, though the formulism is independent of the actual features used. This approach does not attempt to define a particular set of features.
A transition is assumed to have the form:(a1, a2, . . . ag)→(b1, b2, . . . bg) (c1, c2, . . . cg)where                a1, a2, . . . ag are the features of a parent node        b1, b2, . . . bg are the features of a left child        c1, c2, . . . cg are the features of a right child        
The probability of a transition isProb(b1, b2, . . . bg, c1, c2, . . . cg|a1, a2, . . . ag)
Using the chain rule, this approach then conditions each feature on the parent feature and all features earlier in the sequence:Prob(b1, b2, . . . bg, c1, c2, . . . cg|a1, a2, . . . ag)=Prob(b1|a1, . . .ag)*Prob(b2|a1, . . . ag, b1)*Prob(b3|a1, . . . , ag, b1, b2)*. . . *Prob(bg|a1, . . . , ag, b1, . . . , bg-1)*Prob(c1|a1, . . . , ag, b1, . . . , bg)*Prob(c2|a1, . . . , ag, b1, . . . , bg, c1)* Prob(cg|a1, . . . , ag, b1, . . . , bg, c1, . . . , cg-1)
USPTO Backgrounds
USPTO Backgrounds