IIIIIIIB!~I
`U.S. PAT£NT A'>PLICATION
`-------------+-----..-,-- --------•--,----------t
`
`GROUP ART UNIT
`
`~":'.'ti.... NUMBER
`
`F"ILING DA TE
`
`C\.ASS
`
`08/674,dO
`
`06/28/96
`
`395
`
`2412
`
`GIORGI HIIDORJf, ttZLLIVUB, WA7 llRZN JENSIN, BILLIVUI, WA.
`
`••CONTINUING DATA•••••••••••••••••••••
`VSRIFISD
`
`REC'D 1 2 AUG 1997
`WIPO
`-----__:_PC~T~J
`
`**PORIICN/PCT APPLICATIONS************
`VSRIFIID
`
`S, \TE OR
`COVIITRY
`
`SHEETS
`DRAWING
`
`FILING FEE
`RECEIVED
`
`ATTORNEY DOCKET NO.
`
`WA
`
`69
`
`36
`
`7
`
`$1,544.00
`
`661005.447
`
`IHD AND :..:RRY
`6300 COLUMBIA CINTIR
`11.ATTLI WA 98104-7092
`
`METHOD AND IYSTIUt FOR COMPUTING SEMANTIC !.OGICAL PORKS FROM SYNTAX
`TRIii
`
`Thi1 ii to certify that ennHed hereto i1 1 true copy from the record, of the United Stain
`Patent and Trademark Office of the application which i1 identified above.
`Iv eurhonry cl the
`COMMISSIONER Of l"ATfNTS AHO TIIAOEMAIIKS
`
`Page 1 of 113
`
`GOOGLE EXHIBIT 1021
`
`

`

`.,. .. ,, .... 10
`I·
`11~, "- , ~o
`
`Description
`
`METHOD AND SYSTEM FOR COMPUTING SEMANTIC·
`--~-- -- ----------·----
`""---·--
`LOGICAL FORMS FROM SYNTAX TREES
`
`TN:hnical Field
`
`The present invention relates to the field of natural language
`processing ("NLP"), and more particularly, to a method and system for
`generating a logical fonn graph from a syntax tree.
`
`5
`
`JO
`
`Background of the Invention
`Computer systems for automatic natural language processing use a
`variety of subsystems, roughly corresponding to the linguistic fields of
`morphological, syntactic, and semantic analysis to analyze input text and achieve
`1 S a level of machine understanding of natural language. Having understood the
`input text to some level, a computer system can, for example, suggest
`grammatical and stylistic changes to the input text, answer questions posed in the
`input text, or effectively store information represented by the input text.
`Morphological analysis identifies input words and provides
`inf onnation for each word that a human speaker of the natural language could
`determine by using II dictionary. Such inf onnation might include the syntactic
`roles that a word can play (t.g., noun or verb) and ways that the word can be
`modified by adding prefixes or suffixes to generate different, related words. For
`example, in addition to the word '"fish." the dictionary might also list a variety of
`-
`25 words related to, and derived from, the word 04fish." including "fishes,., "fished,.,
`
`-~►
`
`20
`
`Page 2 of 113
`
`

`

`2
`
`"fishing,"
`
`"fisher,"
`
`"fisherman."
`
`"fishable,"
`
`.. fishability,"
`
`.. fishbowl,"
`
`"fisherwoman." "fishery," "fishhook." "fishnet," and "fishy."
`
`Syntactic analysis analyzes each input sentence, using, u a starting
`
`point,
`
`the information provided by the morphological analysis of input words_
`
`s
`
`and the set of syntax rules that define the grammar of the language in which the
`
`input sentence was written. The. following are sample syntax rules:
`
`sentence
`
`=
`
`noun phrase + verb phrase
`
`noun phrase
`
`=
`
`adjective + noun
`
`verb phrase
`
`=
`
`adverb + verb
`
`Syntactic analysis attempts to find an ordered subset of syntax rules that. when
`
`applied to the words of the input sentence, combine groups of words into
`
`phrases, and then combine phrases into a complete sentence. For example,
`
`IO
`
`consider the input sentence: "Big dogs fiercely bite." Using the three simple
`
`rules listed above, syntactic analysis would identify the words "Big .. and .. dogs"
`
`as an adjective and noun, respectively, and apply the second rule to generate the
`
`noun phrase .. Big dogs." Syntactic analysis would identify the words "fiercely"
`
`and "bite" as an adverb and verb, respectively, and apply the third rule to
`
`15
`
`generate the verb phrase .. fier:ely bite." Finally, syntactic analysis would apply
`
`the_ first rule to fonn a complete sentence from the previously generated noun
`
`phrase and verb phrase. The result of syntactic analysis, often represented as an
`
`acyclic downward branching
`
`tree with nodes representing
`
`input words,
`
`punctuation symbols, phrases, and a root node representing an entire sentence, is
`
`20
`
`called a parse .
`
`. -61'
`
`Page 3 of 113
`
`

`

`•
`~
`~t!
`
`I ~
`~ ~ ~ .
`
`.
`
`I-,'
`
`~ .
`~ .:.;_.,,
`.,..,.
`.,. ... ,,
`-~ ... .,
`•;..,;
`~ ·- ..,
`~ .-,;,
`.,,. .. ,
`,.:~
`·,/'!;
`
`~
`
`-~
`~~
`
`~ .
`~
`···1
`.......
`"',->.
`"',->,
`.,.,,.
`
`.1-..,.J-.
`
`~
`
`ij
`
`~ ~
`~~ ,.,;..,.
`,., .
`\,•:·~
`.... ~ ..
`v',
`~
`
`:--.
`
`I
`I
`
`3
`
`S
`
`10
`
`20
`
`Some sentences, however, can have several different panes. A
`classic example sentence for such multiple parses is: "Time flies like III arrow."
`There arc at least three possible parses corresponding to three possible meanings
`of this sentence. In the first parse, "time" is the subject of the sentence, "flies" is
`the verb, and "like an arrow" is a prepositional phrase modifying the verb "flies."
`However, there are at least two unexpected parses as well. In the second parse,
`"time" is an adjective modifying "flies," "like" is the verb, and "an arrow" is the
`object of the verb. This parse corresponds to the meaning that flies of a certain
`type, "time flies," like or are attracted to an arrow. In the third parse, "time" is
`an imperative verb, "flies" is the .-,bject, and "like an arrow" is a prepositional
`phrase modifying "time." This parse corresponds to a command to time flies as
`one would time an arrow, perhaps with a stopwatch.
`Syntactic analysis is often accomplished by constructing one or
`more hierarchical trees called syntax parse trees. Each leaf 11ode of the syntax
`1 S parse tree generally represents one word or punctuation symbol of the input
`sentence. The application of a syntax rule generates an intermediate-level node
`linked from below to one, two, or occasionally more existing nodes. Tnc
`existing nodes initially comprise only leaf nodes, but, as syntactic analysis
`applies syntax rules, the existing nodes comprise both leaf nodes as well as
`intermediate-level nodes. A single root node of a complete syntax parse tree
`represents an entire sentence.
`Semantic analy:,is generates a logical form graph that describes the
`meaning of input text in a deeper way than can be described by a syntax parse
`tree alone. The logical form graph is a first attempt tc, understand the input text
`at a level analogous to that achieved by a human speaker of the language.
`
`• -11/o
`
`2S
`
`-
`
`Page 4 of 113
`
`

`

`4
`
`The logical form graph has nodes and links, but. 1m1ike the syntax
`
`parse tree described above, is not hierarchically ordered. The links of the logical
`
`fonn graph are labeled to indicate the relationship between a pair of nodes. For
`
`example, semantic analysis may identify a certain noun in a sentence as the deep
`
`S subject or deep object of a verb. The deep subject of a verb is the doer of the
`
`action and the deep object of a verb is the object of the ~tion specified by the
`
`verb. The deep subject of an active voice verb may be the syntactic subject of
`
`the sentence, and the deep object of an &ctive voice verb may be the syntactic
`
`object of the verb. However, the deep subject of a passive voice verb may be
`
`10
`
`expressed in an agentive-by phrase, 11nd the c!eep object of a passive voice verb
`
`may be the syntactic subject of the sentence. For example, consider the two
`
`sentences: (1) "Dogs bite people" and (2) "People arc bitten ·oy dogs." The first
`
`sentence has an active voice verb, and the second sentence has a passive voice
`
`verb. The syntactic subject of the first sentence is "Dogs" and the syntactic
`
`IS
`
`object of the verb "bite" is .. people." By contrast. the syntactic subject of the
`
`second sentence is "People" and the verb phrase "arc bitten~ is modified by the
`
`agentive-by phrase "by dogs." For both sentences, "dogs" is the deep subject,
`
`and "peoi,lc" is the deep object of the verb or verb phrase of the sentence.
`
`Although the syntax parse trees generated by syntactic analysis for sentences I
`
`20
`
`and 2, above, will be different. the logical form graphs generated by semantic
`
`analysis will be the same, \M-causc the underlying meaning vf the two sentences
`
`is t.'ic same.
`
`Further semantic processing after generation of the logical form
`
`graph may draw on knowledge databases to relate analyzed text to real world
`
`25
`
`coifd'epts in order to achieve still de!per levels of understanding. An exaanplc
`
`I
`i
`f
`'
`a,.;..ii._i.;;..&;;~, t
`r
`t
`
`Page 5 of 113
`
`

`

`:...;.
`Si
`i!
`~
`~~
`~ ~;;
`
`~<
`~:-~
`
`}'",.
`
`,,
`?;
`
`¥,•
`
`.... _
`
`;,:
`~
`~
`~ ,, f
`
`"
`
`'~ ~,I>. I
`
`~ •.~ ...
`..... , .. -... ~
`.......
`. . . ·
`, . .,.
`·'~~
`
`~ . -' I ~ ... '.\;
`~
`
`. .,,,., .
`. . ·,; .
`. ..., .. .,
`►,, • .,
`
`,~;
`~
`I
`~~
`~-~--
`~
`I •
`
`knowledge base would be an on-line encyclopedia. from which more elaborate
`
`definitions and contextual infonnation for particular words can be obtained.
`
`In the following, the three NLP subsystems - morph<,logical,
`
`syntactic, and seff\antic - are described in the context of processing the sample
`
`5
`
`input text: "The !)Ct'SOn whom I met was my friend." Figure I is_ a block
`
`diagram ilJustrating the flow of infonnation between the NLP subsystems. The
`
`morphologicaJ subsystem
`
`IO 1 receives
`
`the
`
`input
`
`text and out1".'Uts
`
`111
`
`identification of the words and senses for each of the various parts of speech in
`
`which each word can be used. The syntactic subsystem l 02 receives this
`
`l O
`
`information and generates a syntax parse tree by applying syntax rules. The
`
`semantic subsystem 103 receives the syntax parse tree and generates a logical
`
`fonn graph.
`
`Figures 2-S display the dictionary infonnation stored on an
`
`electronic storage medium that is retrieved for the input words of the sample
`
`15
`
`input text during morphological analysis. Figure 2 displays the dictionary entries
`
`for the input words "the" 201 and "person" 202. Enay 201 comprises the key
`
`"the"' 203 and a list of attribute/value pairs. The first attr.'>ute "Adf' 204 has, as
`
`its value, the symbols contained within the braces 205 and 206. These symbols
`
`comprise two further attribute/value pairs: (I) "Lemma"/ "the" and (2) .. Bits"/
`
`20
`
`.. Sing Plur Wa6 Det Art BO Def." A lemma is the basic, uninflc:cted fonn of a
`
`word. The attribute "Lemma" therefore indicates that "the" is the basic,
`
`uninflected form of the word represented by this enay in the dictionary. The
`
`attribute
`
`.. Bits" comprises a set of abbreviations representing certain
`
`morphological and syntactic information about a word. This infonnation
`
`25
`
`indftates that "the" is: (I) singular; (2) plural; (3) not inflectable; (4) a
`
`'
`
`'
`
`.-
`
`.-
`
`.
`
`..,. Y. . . • • • -
`
`Page 6 of 113
`
`

`

`I I
`
`6
`
`detenniner; (5) an article; (6) an ordinary adjective: and (7) definite. Attribute
`
`204 indicates that the word "the" can serve as III adjective. Attribute 212
`
`indicates that the word "the" can serve as an adverb. Attribute '"Senses" 207
`
`represents the various meanings of the word as separate definitions and
`
`S examples, a portion of which are included in the list of attribute/valu,e pain
`
`between braces 208-209 and between braces 210-211. Additional meanings
`
`actually contained in the entry for "the" have been omitted in Figure 2, indicated
`
`by the parenthesized expressi_on "(more sense records)" 213.
`
`In the first step of natural language processing, the morphological
`
`10
`
`subsystem recognizes each word and punctuation symbol of the input text as a
`
`separate token and constructs an attribute/value record for each part of speech of
`
`each token using the dictionary infonnation. Attributes arc fields within the
`
`records that can have one of various values defined for the particular attribute.
`
`These attribute/value records arc then passed to the syntactic subsystem for
`
`l S
`
`further processing, where they arc used as the leaf nodes of the syntax parse tree
`
`that the syntactic subsystem construct. All of the nodes of the syntax parse tree
`
`and the logical fonn graph C')nstructed by subsequent NLP subsystems arc
`
`attribute/value records.
`
`The syntactic subsystem applies syntax rules to the leaf nodes
`
`20
`
`passed to the syntactic subsystem from the morphological subsystem to construct
`
`higher-level nodes of a possible syntax parse tree that represents the sample
`
`input text. A complete syntax parse tree includes a root node, intcnnediatc-level
`
`nodes, and leaf nodes. The root node represents the syntactic construct (e.g.,
`
`declarative sentence) for the sample input text. The intennediatc-leve.l nodes
`
`·"~~~?:::::-
`·. <- .. ~
`
`Page 7 of 113
`
`

`

`....
`
`177
`
`n
`
`7
`
`represent intennediate syntactic constructs (e.g., verb, noun, or prepositional
`
`phrases). The leaf nodes represent the initial set of attribute/value records.
`
`In some NLP systems, syntax rules are applied in a top-down
`
`manner. The syntactic subsystem of the NLP system herein described applies
`
`5
`
`syntax rules to the leaf nodes in a bottom-up manner. That is, the syntactic ,
`
`subsystem attempts to apply syntax rules one-at-a-time to single leaf no&s to
`
`pairs of leaf nodes, and, occasionally, to larger groups of leaf nodes.
`
`If the
`
`syntactic rule requires two leaf nodes upon which to operate, and a pair of leaf
`
`nodes both contain attributes that match the requirements specified in the rule,
`
`10
`
`then the rule is applied to them to create a higher-level syntactic construct. For
`
`example, the words "my friend" could represent an adjective and a noun,
`
`respectively, which can be combined into the higher-level syntactic construct of
`
`a noun phrase. A syntax rule corresponding to the grammar rule, "noun phrase=
`
`adjective + noun," would create an intermediate-level noun phrase node, and link
`
`15
`
`the two leaf nodes representing "my" and "friend" to the newly created
`
`intermediate-level node. As each new intermediate-level node is created, it is
`
`linked to already-existing leaf nodes and intennediate-le· .. el nodes, and becomes
`
`part of the total set of nodes to which the syntax rules arc applied. The process
`
`of applying syntax rules to the growing set of nodes continues until either a
`
`20
`
`complete syntax parse tree is generated or until no more syntax rules can be
`
`applied. A complete ~-yntax parse tree includes all of the words of the input
`
`sentence as leaf nodes and represents one possible parse of the sentence.
`
`This bottom-up method of syntax parsing creates many
`
`intermediate-level nodes and sub-trees that may never be included in a final,
`
`.. -~ .....
`
`~rJ~tK~~~~~t~~~~~~~~~~ru~'"<~~~::~~-=~--~~::.:·~-c"~{~\~~-=~·{·
`
`Page 8 of 113
`
`

`

`!
`
`i •
`
`8
`
`s
`
`this method of parsing can
`tree. Moreover,
`complete syntax parse
`simultaneously generate more than one complete syntax parse tree.
`The syntactic subsystem can conduct an exhaustive search for all
`possible complete syntax parse trees by continuously applying the rules 1D1til no
`additional rules can be applied. The syntactic subsystem can also try vari~us
`heuristic approaches to first generate the most probable nodes. After one or a
`few complete syntax parse trees are generated. the syntactic subsystem typically
`can terminate the search because the syntax parse tree most likely to be chosen
`as best representing the input sentence is probably one of the first generated
`If no complete syntax parse trees are generated after a
`syntax parse trees.
`reasonable search. then a fined parse can be achieved by combining the most
`promising sub-trees together into a single tree using a root node that is generated
`by the application of a special aggregation rule.
`Figure 6 illustrates the initial leaf nodes created by the syntactic
`subsystem for the dictionary entries initially displayed in Figures 2-S. The leaf
`nodes include two special nodes, 601 and 614, that represent the beginning of
`the sentence and the period terminating the sentet, -:c, respectively. Each of the
`nodes 602-613 represent a single part of speech that an input word can represent
`in a sentence. These parts of speech are found as attribute/value pairs in the
`20 dictionary entries. For example, leaf nodes 602 and 603 represent the two
`possible parts of speech for the word .. The, .. that arc found as attributes 204 and
`
`IO
`
`IS
`
`212 in Figure 2.
`Figure 7-22 show the rule-by-rule construction of the final syntax
`parse tree by the syntactic subsystem. Each of the figures illustrates the
`application of a single syntax rule to generate an intennediate-level node that
`
`25
`
`.;.
`
`i
`
`!
`
`t
`
`) -I l
`' ' • • I •
`I I . • •
`
`~,,.-,.~:~•·.•-,.:_, ~--.:-r .-, -~ ·-".:•· .• ,;.,-.,,. . .,.-,..~ ............... ·.·.:-·.: • • . •
`... • ·. -:~-: ~--' ·:-.
`•
`•
`
`........ .,, ....... , . .,
`
`..... "··'"" .. '-' .. • ..... • ........ •' .. •--:.r .... _., ........... ~. ~:t-""·
`
`Page 9 of 113
`
`

`

`9
`
`represents a synta-:::tic structure. Only the rules that produce the intennediate(cid:173)
`level nodes that comprise the final syntax tree are iUustrate-3. The syntactic
`subsystem generates many intennediate-level nodes which do not end up .
`included in the final syntax parse tn.t.
`In Figures 7-14, the syntactic subsystem applies unary ~yntax rules
`that create intennediate-level nodes that repres...-nt simple verb, noun, - and
`adjective phrases. Starting with Figure IS, the syntactic subsystem begins to
`apply binary syntax rules that combine simple verb, noun, and adjective phrases
`into multiple-word syntactic constructs. The syntactic subsystem orders the
`rules by their likelihood of successful application, and then attempts to apply
`them one-by-one until it finds a rule that can be successfully applied to the
`e.csting norles. For example,. as shown in Figure 15, the syntactic subsystem
`successfully applies a rule that creates a node representing a noun phrase from an
`adjective phrase and a noun phr'be. The rule specifics the characteristics
`required of the adjective and noun phrases. In this example, .he adjective phrase
`must be a detcnniner. By following the !)()inter from node 1501 back to node
`1503, and then accessing morphological information included in node 1503, the
`syntactic subsystem determines that node 1501 docs represent a dete,miner.
`Having located the two nodes I 501 and I 502 that meet the characteristics
`required by the rule, the synt11ctic subsystem then applies the rule to create from
`the two simple phrases I SC' I and I 502 an intcnnediatc-levcl node that represents
`the noun phrase "my friend." In Figure 22, the syntactic subsystem generates the
`final, complete syntax parse tree representing the input sentence by applying a
`trinary rule that combines the special Begin I leaf node 2201, the verb phrase
`.. The person whom I met was my friend" 2202, and the leaf node 2203-that
`
`s
`
`10
`
`15
`
`20
`
`25
`
`i
`V. •.•
`
`·!
`
`, .. ..-,-,., .. ,
`
`,• ~-.•
`
`,~._w:,;.~•"'•.~-';\.#.tl',..-. .,.,1\.J'.,"'V_-_. ..
`
`•
`
`. •
`
`•
`
`•
`
`"
`
`•
`
`•
`
`•
`
`~ .. .,
`
`•· •.· ., . • -.,:•
`
`Page 10 of 113
`
`

`

`10
`
`represents the final tenninating period to form node 2204 representing the
`
`declarative sentence.
`
`The semantic subsystem generates a logical form graph from a
`
`complete syntax parse tn:e. In some NLP systems. me logical form graph is
`
`S constructed from the nodes of a syntax parse ·tree, adding to them attributes and
`
`new bi~tional links. The logical fonn graph is a labeled, directed graph, It
`
`is a semantic representation of an input sentence. The information obtained for
`
`each word by the morphological subsystem is still available through references
`
`to the leaf nodes of the syntax parse tree from within nodes of the logical fonn
`
`•
`
`IO graph. Both the directions and labels of the links of the logical fonn graph
`
`represent semantic infonnation, including the functional roles for the nodes of
`
`the logical fonn graph. During its analysis, the semantic subsystem adds links
`
`and nodes to represent (I) omitted, but implied, words; (2) missing or unclear
`
`arguments and adjuncts for verb phrases; and
`
`(3) the objects to which
`
`15 prepositional phrases refer.
`
`Fi~ure 23 illustrates tht complete logical fonn graph generated by
`
`the semantic subsystem for the example input sentence. Meaningful labels have
`
`been assigned to links 2301-2306 by the ~a.,tic subsystem as a product of the
`
`successful application of semantic rules. The six nodes 2307-2312, along with
`
`•
`
`20
`
`the links between them. represent the essential components of the semantic
`
`meaning of the sentence. In general, the logical fonn nodes roughly correspond
`
`to input "1ords, but ccnain wortls that are unnecessary for conveying semantic
`
`meaning. such as .. The .. and .. whom .. do not ai>pcar in the logical form graph,
`
`and the input verbs .. met" and .. was" appear as their infinitive forms .. meet" and
`
`25
`
`.. be." The nodes arc represented in the computer system as records, and contain
`
`! -;
`I
`' I
`l
`i
`f
`
`Page 11 of 113
`
`

`

`I'~
`
`-·
`
`;:; ,'.,\
`
`....
`
`t
`
`' i
`I ,, I ,'if
`f 1•
`
`••
`
`•
`
`•
`
`•
`
`•
`
`•
`
`11
`
`additional information not shown in Figure 23. The fact that the verbs were
`
`input in singular past tense fonn is indicated by additional inf onnation within the
`
`logical fonn nodes corresponding to the meaning of the verbs. 2307 and 2310.
`-
`The differences between the syntax parse tree and the logical fonn
`
`5
`
`graph are readily apparent from a comparison of Figure 23 to Figure 22. The
`
`syntax parse tree dispfayed in Figw-e 22 includes 10 leaf nodes and 16
`
`intennediate-level nodes linked together in a strict hierarchy. whereas the logical
`
`fonn graph displayed in Figure 23 contains only 6 nodes. Unlike the syntax
`
`parse tree, the logical fonn graph is not hierarchically ordered. obvious from the
`
`IO
`
`two links having opposite directions between nodes 2307 and 2308. In addition.
`
`as noted above, the nodes no longer represent the exact form of the input words.
`
`but instead represent their meanings.
`
`Further natural language processing steps occur after .semantic
`
`analysis. They involve combining the logical form graph with additional
`
`15
`
`information obtained from knowledge bases, analyzing groups of sentences, and
`
`generally attempting to assemble around each logical form graph a rich
`
`contextual environment approximating that in which humnns process natural
`
`language.
`
`Prior an methods for generating logical form graphs involve
`
`20 computationally complex adjustments to, and manipulations of the syntax parse
`
`tree. As a result, it hecomes increasingly difficult to add new semantic rules to a
`
`NLP system. Addition of a new rule involves new procedural logic that may
`
`conflict with the procedural logic . already programmed into the semantic
`
`subsystem. Furthermore, because nodes of the syntax parse tree are extended
`
`25
`
`and reused as nodes for the logical form graph, prior art semantic subsystems
`
`Page 12 of 113
`
`

`

`12
`
`produce large, cmnbersome, and complicated data structures. The size and
`
`complexity of a logical form graph overlayed onto a syntax parse tree makes
`
`further use of the combined data structure ~-prone · and inefficient
`
`Accordingly, it would be desirable to have a more easily ex:ended and
`
`S manageable semantic subsystem so that simple logical form graph data structures
`
`can be produced.
`
`Swrumuy of the Invention
`
`The present invention is directed to a method and system for
`
`10 performing semantic analysis of an input sentence within a NLP system. The
`
`semantic analysis subsystem receives a syntax parse tree generated by the
`
`morphological and syntactic subsystems. The semantic analysis subsystem
`
`applies two sets of semantic rules to make adjustments to the received syntax
`
`parse tree. The semantic analysis subsystem then applies a third set of semantic
`
`IS
`
`rules to create II skeletal logical form graph from the syntax parse tree. The
`
`semantic analysis subsy!ltcm finally applies two additional sets of semantic rules
`
`to the skeletal logical form graph to provide semantically meaningful labels for
`
`the links of the logical form graph. to create additional logical form graph nodes
`
`for missing nodes, and to unify redundant logical form graph nodes. The final
`
`20
`
`logical form graph generated by the semantic analysis subsystem represents the
`
`complete semantic analysis of an input sentence.
`
`Brief Qescrjprion of the Ora" iogs
`Figure I is a block '11iagram illustrating the flow of information
`
`· . ~.,.
`
`25
`
`between the subsystems of a NLP system.
`
`ti~
`~ ._,
`._~...,
`,,..
`
`~\®.
`. .,,,,..,;,:~
`'-•~ ... ---... ~
`
`Page 13 of 113
`
`

`

`13
`
`Figures 2-5 display the dictionary information stored on 111
`electronic storage mediwn that is retrieved for each word of the example input
`sentence: "The person whom I met was my friend."
`Figure 6 displays the leaf nodes generated by the syntacti(;
`subsystem as the first step in parsing the input sentence.
`Figures 7-22 display the successive application of syntax rules by
`the syntactic subsystem to parse of the input sentence and produce a syntax pu,e
`
`tree.
`
`Figure 23 illustrates the logical foma graph generated by the
`semantic subsystem to represent the meaning of the input sentence.
`Figure 24 shows a block diagram illustrating a preferred computer
`system for natural language processing.
`illustrates the
`
`three phases of the preferred new
`
`Figure 25
`
`J.
`
`S
`
`10
`
`... .,.
`.;,
`.,.--?·
`.,.,... .. ~
`>-:t~ ~
`
`'
`
`semantical subsystem.
`Figure 26 is a flow diagram for the new semantic subsystem
`
`15
`
`(NSS) .
`
`20
`
`Figure 27 .£splays the first set of semantic rules.
`Figure 28A displays a detailed des,; :iption of the semantic rule
`Prl F _You from the first set of semantic rules.
`Figure 288 displays an example application of the semantic rule
`PrLF _You from the first set of semantic rules.
`Figure 29 displays the scamd set of semantic rules.
`Figures J0A-308 display a detailed description of the s~tic
`· "fllle TrLF _MoveProp from the seoond set of semantic rules.
`
`j,
`>
`
`Pi
`~ . II
`I ; r ~ t·
`•
`fl
`,t~----~
`. ..
`I-
`
`.
`
`•
`
`Page 14 of 113
`
`

`

`14
`
`Figure 30C o. .. plays an example appli~tion of the semantic rule
`
`TrLF _MoveProp from the second set of semantic rules.
`
`Figure 31 displays a flow diagram for apply _rules.
`Figure 32 displays a flow diagram for phase one of the NSS.
`Figure 33 displays the third set of semantic rules.
`
`Figures 34A-C display a detailed description of the semantic rule
`
`SynToSem I from the third set of semantic rules.
`
`Figure 340 displays an example application of the sen!antic rule
`
`SynToSem 1 from the third set of semantic rules.
`
`10
`
`Figure 35 displays a flow diagram for phase two of the NSS.
`
`Figures 36-38 display the fourth set of ~antic ruk:-.
`
`Figure 39A displays a de:ailed description of the semantic rule
`
`LF _Dobj2 from the fourth ... t of semantic rules.
`
`Figure 39B displays an example application of the sema,ttic rule
`
`15 LF _ Dobj2 from the fourth set of semantic rules.
`
`Figure 40 displays the f:fth set of semantic rules.
`
`Figures 41A-C display a detailed -iescription of the semantic rule
`
`PsLF _PronAnaphora from the fifth set of semantic rules.
`
`Figure 41 D displays an example application of the semantic rule
`
`20
`
`PsLF _PronAnaphora from the fifth set of semantic rules.
`
`Figure 42 displays a flow diagram for phase three of the NSS.
`
`Figure 43 is a block diagram of a computer system for the NSS.
`
`Figures 44-S9 display each sucet.ssful rule application by the NSS
`
`as it processes the syntax parse tree generated for the example input sentence .
`
`. -l!f.
`
`....
`
`Page 15 of 113
`
`

`

`15
`
`Detailed Description of the Invention
`
`The present invention provides a r.:w semantic method and system
`
`for generating a logical form graph from a syntax . tree.
`
`In a prefened
`
`S embodiment, a new semantic subsystem (NSS) perfonns the semantic analysis in
`
`three phases: (I> filling in and adjusting the syntax parse tree. (2) generating an
`
`initial logical form graph. and (3) generating meaningful labels for links •Of the
`
`iogical form graph and constructing a complete logical form graph. Each phase
`
`constitutes the application of one or two sets of rules to either a set of syntax tree
`
`1 0 nodes or to a set of logical form graph nodes.
`
`The NSS addresses the r~ognized di:ficiencies in prior art
`
`semantic subsystems described above in the backgr01md section. Each phase of
`
`the NSS is a simple and extensible rule-based method. As additional linguistic
`
`phenomena are recognized. rlles to handle them can be easily included into one
`
`JS of the rule sets employed by the NSS. In addition, the second phase of the NSS
`
`generates an entirely separate logical fonn graph. rather than overlaying the
`
`logical fonn graph onto an existing syntax parse tree. The logical form graph
`
`data structure generated by the NSS is therefore simple and space efficient by
`
`comparison with prior art logical fonn graph data structures.
`
`20
`
`Figure 24 is a block diagram illustrating a preferred computer
`
`system for a NLP system. The computer system 2401 contains a central
`
`processing unit, a memory, a storage device, and input and output devices. The
`
`NLP subsystems 2406-2409 are typically loaded into memory 2404 from a
`
`computer-readable storage device such as a disk. An application program 2405
`
`2S
`
`that uses the services provided by the NLP system is also typically loaded into
`
`. . . ..:... ..
`
`.. .
`
`Page 16 of 113
`
`

`

`16
`
`memo1 y. Tht: electronic dictionary 24 J J is stored on a storage device. such as a
`
`disk 24 J 0, and entries arc rCMl into memory for use by the morphological
`
`subsystem. In o:1e embodiment. a user typically responds to a prompt displayed
`
`on the output device 2403 by entering one or more natural language sentences on
`
`S an input device 2404. The natural language sentences are received by the
`
`application. processed, and then passed to the NLP system by way of dk~
`
`morphological subsystem 2406. The morphological subsystem uses information
`
`from the electronic dictionary to construct records describing each input word,
`
`and passes those records to the syntactic subsystem 2407. The syntactic
`
`10
`
`subsystem parses the input words to construct a syntax parse tree and passes the
`
`syntax parse tree to the semantic subsystem 2408. The semantic subsystem
`
`generates a logical fonn graph from the received syntax parse tree and passes
`
`that logical fonn graph to other NLP subsystems 2409. The application program
`
`then can send and receive information to the natural language subsystem 2409 in
`
`15 order to make use of the machine understanding of the input tm achieved by the
`
`NLP system. and then finally output a response to the user on an output device
`
`2403.
`
`Figure 25 illustrates the three phases of the preferred new sei..antic
`
`subsystem. Phases 1-3 of the NSS are shown as 2502, 2504, and 2506,
`
`20
`
`respectively. The states of the relevant data structures input and output from
`
`each phase of the NSS are displayed in Figure 25 as labels 2501, 2503, 2505,
`
`and 2507. The NSS receives a syntax parse tree 2501 generated i>y the syntactic
`
`subsystem. The first phase of the NSS 2502 completes the synbaX parse tree
`
`using semantic rules. and passes the completed syntax parse tree 2303 to :he
`
`25
`
`·srcond phase of the NSS 2504. Tft'!"sccond phase of the NSS generates an imtial
`
`Page 17 of 113
`
`

`

`17
`
`logical fonn graph 2.S0.S and passes that initial logical form graph to the third
`
`phase of the NSS 2.S06. The third phase of the NSS applies semantic rules to the
`
`initial logical f onn graph in order to add meaningful semantic labels to the linb
`
`of the logical fonn graph, to add new links and nodes to fill out the semantic
`
`5
`
`representation · of the input sentence, and oc:casiona!ly to remove redundant
`
`nodes. The complete logical fonn graph 2507 is then passed to other NLP
`
`subsystems for use in further interpreting the input sentence represented by the
`
`logir.al fonn graph or in answering questions or preparir,g data based on the input
`
`sentence.
`
`10
`
`A flow diagram for the NSS is displayed in Figw-e 26. The flow
`
`diagram shows successive invocation of the three phases of the NSS, 2601, 2602,
`
`and 2603. ln the following, each phase of the NSS will be described in detail.
`
`NSS Phase One - Completing ·Syntactic Roles of the Syntax Tree
`
`15
`
`In phase one of the NSS, the NSS modifies a syntax parse tree
`
`received from the syntactic subsystem by applying two different sets of semantic
`
`rules to the nodes of the syntax parse tree. These semantic rules can alter the
`
`linkage structure of the syntax tree