`
`P,ATENIDAif ---.
`OCT 121ssg
`
`Form PTO-436A
`(Rev. 8/92)
`
`\
`
`$--rfr FfrF il&r r$ilffi
`
`a;q**"
`
`.'1,,,
`
`5e6ms
`iltililww
`
`.!
`
`,,1
`i l.*, i
`r irlJ
`\ "\{
`
`.'t'
`
`Page 1 of 535
`
`GOOGLE EXHIBIT 1023
`
`
`
`[t/6?4
`
`610
`
`..t',,.
`
`--'-FAfenr APPt;gxrFn
`-:,-- --'
`
`Date
`Entered
`or
`Gounted
`
`llllllllllllllllllllllilillilllililillillillfil
`08674510
`
`-
`coNrENr!
`
`l,,Appti,cation +
`
`i
`
`:k;.,
`.i',
`
`:
`'! -"(;,
`
`r
`z-
`
`1
`
`.
`.
`' /\-
`
`:
`
`j.r.(--
`';
`
`lapers.
`
`APPRovEDFoR.EtcENSe | -l_,-
`AUs 14 gS sF-
`
`INITIALS
`
`Date
`
`Receivedor'
`Mailed
`
`-?-
`
`i
`
`1
`
`,-
`
`r
`
`\
`
`'1
`
`)
`
`{\ L -'
`
`\\h-"1
`
`tL'L 3
`
`pL)
`
`6.
`
`7.
`
`8.
`
`9.
`
`10.
`
`11.
`
`12.
`
`13.
`_14.
`" f{.
`-a ,./
`_ 16.
`17.
`
`18.
`
`19.
`
`21.
`2t
`
`27.
`
`4-27
`
`1'"13
`q li5 lat r
`iz /4 7,r
`t8 "3y -7 g
`
`4-+?fi
`
`x_
`
`Page 2 of 535
`
`
`
`, ,ir, '; *rlji ,.
`
`'.
`
`. ,..t,
`
`.S. PATENT APPLICATION
`
`ti,l".::'
`'t:it. .",i
`
`, U
`
`BAR
`
`.is,l.,--w.
`
`ttt' ..
`
`iltilil ilililil ilililil1ililililil ilililililtil
`
`SERIAL NUMBER
`
`oBf674,Gto
`
`FILING DATE
`
`CLASS
`
`GBOUP ART UNIT
`
`06 /28 /e6
`
`39s
`
`24L2
`
`Z GEORGE HEIDORN, BELLEVUE, WA' KAREN JEN'EN, BELLE'UE, WA.
`
`* *CONTINUING DATATI t( rr tr * * t( tr tr tr * * * * * * * * * * *
`VERIFIED
`
`t'*FOREIGN/PCT APPLICATIONS******** *:t* :k
`VERIFIED
`
`FoRErcN FrrrNG LrcENsE GRANTED u,/zo/95
`IU IAL
`ITATE OR
`CLAIMS
`]OUNTRY
`
`SHEETS
`DRAWING
`
`NDEPENDENT
`3LAIMS
`
`FILING FEE
`RECEIVED
`
`ATTORNEY DOCKET NO.
`
`WA
`
`69
`
`36
`
`n
`
`$1,544.00
`
`56100s.447
`
`SEED AND BERRY
`6300 COLUMBIA CENTER
`SEATTLE WA 98L04-7092
`
`METHOD AND SYSTEM FOR COMPUTING SEMANT]C LOGICAL FORMS FROM SYNTAX
`TREES
`
`LlJ
`
`aa
`oo
`
`H
`F
`
`This is to certifv that annexed hereto is a true copv from the records of the United States
`Patent and Trademark Office of the application which is identified above.
`By authority of the
`COMMISSIONER OF PATENTS AND TRADEMARKS
`
`Certifying Officer
`
`Page 3 of 535
`
`
`
`1::..-.
`
`FORMPTO.IOS2
`
`ih
`
`.ee*er
`on98104-7092
`
`0ur'6'7;$'S3.CI
`
`Fax (206) 682-603 1
`Express Mail Certificate No.: Pffiyf}J5r544
`DocketNo.: 'ffttOOS.Uf
`' Juna7[Jgge
`Date:
`
`BOX PATENT APPLICATION
`ASSISTANT COMMIS$ONER FOR PATENTS
`WASHINGTONDC 20231
`
`Sir:
`
`Inventors:
`
`For:
`
`is the patent application of:
`Karen Jensen
`METHOD AND SYSTEM FOR COMPUTING SEMANTIC
`LOGICAL FORMS FROM SYNTAX TREES
`Enclosed arrc:
`
`69 sheets of informal drawings (Figs. l-59).
`An assignment of the invention to: Miorosoft Corporation, a oorporation of the State of V/ashington.
`A Declaration and Power of Attorney.
`A verified staterrrcnt to establish small entity status rmder 37 C.F.R. 1.9 and 37 C.F.R. 1.21.
`A certified oopy of Application No. , filed , from whioh priority is claimed, .
`This application claims the benefit of U.S. Provisional ApplicationNo. , filed . IDELETD IF NOT APPLICABLE]
`The filing fee has been calculated as shownbelow.
`Filed without fee or formal papers.
`
`Xt
`
`Xt
`
`For:
`
`Utilitv Fee
`
`Total Claims
`
`Indenendent Clalms
`( ) Multiple Dependent
`Clairn Presented
`
`,4,SSIGNMEIYT
`
`No. Filed
`
`No. Extra
`
`SmaII Entitv
`Rate
`
`Fee
`
`$
`
`$
`
`$
`
`$
`
`s
`
`xll
`
`x39
`
`+ 125
`
`+40
`
`TOTAL $
`
`Other Than A
`Small Entitv
`Rate
`
`Fee
`
`$
`
`$
`
`$
`
`$
`
`$
`
`x22
`
`x7t
`
`+ 250
`
`+40
`
`TOTAL $
`
`or
`or
`
`or
`
`or
`
`or
`
`or
`
`or
`
`or
`
`Please charge my Deposit Account No. I 9- 1090 in the amount of $-. A duplicate copy of this sheet is enclosed.
`A check in the amount of $_is enclosed.
`The Assistant Commissioner is hereby authorized to charge payment of the following fees associated with this
`communication or credit any overpa),rnent to Deposit Acoount No. l9-1090. A duplioate copy of this sheet is enclosed.
`t I Any additional filing fees required under 37 C.F.R. 1.16.
`[ ] Any patent applioation processing fees under 37 C.F.R. L 17.
`
`Respectfully submitted,
`SEED and BERRYIIP
`
`Registration No. 39,906
`
`Page 4 of 535
`
`
`
`[Jfri'ui''.-St0
`PATENT
`
`IN TIIE UNITED STATES PATENT AND TRADEMARK OFFICE
`
`: George Heidorn and Karen Jensen
`:
`June 28,1996
`: METHOD AI{D SYSTEM FOR COMPUTING SEMANTIC
`LOGICAL FORMS FROM SYNTAX TREES
`
`Docket No.
`
`6610a5.447
`
`Date
`
`Iune 28, 1996
`
`Box Patent Application
`Assistant Commissioner for Patents
`Washington, DC zAnl
`
`CERTIFICATE OF MAILING BY "E)GRESS MAIL'
`
`Sir:
`
`I hereby certify that tfre enclosures listed below are being deposited with the
`United States Postal Service "EXPRESS MAIL Post Office to Addressee" service under 37
`C.F.R. $ 1.10, Mailing Label Certificate No. EM417213544, on June 28, 1996, addressed to:
`Box Patent Application, Assistant Commissioner for Patents, Washington, DC 20231.
`
`Respectfully submitted,
`
`SEED and BERRY LrP
`
`RWB jlc
`
`Enclosures:
`Postcard
`Form PTO-1082 (+ copy)
`Specification, claims, abstract
`Informal Drawings (Figures 1-59)
`
`c:kwb\0188
`
`Page 5 of 535
`
`
`
`frf
`
`#
`
`ErGREssrvr,/ Yo.EM4r,2E&/cl
`/ I FzK-
`i,ti'67461S
`
`Description
`
`METHOD AND SYSTEM FOR COMPUTING SEMANTIC,
`
`LOGICAL FORMS FROM SYNTAX TREES
`
`Technical Field
`
`The present invention relates to the field of
`processing ("I{LP"), and more particularly, to a method
`
`natural language
`
`and system for
`
`generating a logical form graph from a syntax fiee.
`
`10
`
`Backeround of the Invention
`
`Computer systems for automatic natural language processing use a
`variety of subsystems, roughly corresponding to the linguistic fields of
`
`morphological, slmtactic, and semantic analysis to analyze input text and achieve
`
`15
`
`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 tex! answer questions posed in the
`
`input text, or effectively store information represented by the input text.
`
`Morphological analysis identifies input words and provides
`
`information for each word that a human speaker of the natural language could
`
`determine by using a dictionary. Such information might include the syntactic
`
`roles that a word can play (e.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
`
`words related to, and derived from, the word "fish," including "fishes," "fished,"
`
`,t1
`
`Page 6 of 535
`
`
`
`2
`
`"fishing," "fishefo" "fisherman," "fishable," "fishability," "fishbowl,"
`
`"fi sherwomar.," "fishery," "fi shhook," "fi shnet," and "fi shy."
`
`Syntactic analysis analyzes each input sentence, using, as a starting
`
`point, the information provided by the morphological analysis of input words
`
`and the set of syntax rules that define the grammar of the language in which the
`
`input sentence was written. The following are sample syntur rules:
`sentence = noun phrase + verb phrase
`noun phrase : adjective + noun
`
`verb phrase = adverb * verb
`
`f
`
`Syntactic analysis affempts to find an ordered subset of syntax rules that, when
`:---z-
`applied to the words of the input sentence, combine groups of words into
`
`phrases, and then combine phrases into a complete sentence. For example,
`
`10
`
`consider the input sentence: "Big dogs fiercely bite." Using the three simple
`rules listed above, syntactic analysis would identiff 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 identiff the words "fiercely"
`
`and "bite" as an adverb and verb, respectively, and apply the third rule to
`
`15
`
`generate the verb phrase "fiercely bite." Finally, syritactic analysis would apply
`
`the first rule to form a complete sentence from the previously generated noun
`
`phrase and verb phrase. The result of syntactic analysis, often represented as an
`
`acyclic downward branching fiee with nodes representing input words,
`
`punctuation symbols, phrases, and a root node representing an entire sentence, is
`
`2A
`
`called a parse.
`
`a1
`
`Page 7 of 535
`
`
`
`Some sentences, however, can have several different parses. A
`
`classic example sentence for such multiple parses is: "Time flies like an arrow."
`
`There are at least three possible parses corresponding to three possible meanings
`
`of this sentence. In the first parse, "time" is the subject of the sentenceo "flies" is
`the verb, and "like an arrof is a prepositional phrase modiffing the verb "flies."
`
`However, there are at least two unexpected parses as well. ln the second parse,
`
`"fime" is an adjective modi$ing "flies," "like" is the verb, and "an alTow" is the
`
`object of the verb. This parse corresponds to the meaning that flies of a certain
`
`10
`
`t5rye, "time flies," like or are attracted to an arrow. In the third parse, "time" is
`an imperative verb, "flies" f the object, and "like an arow'' is a prepositional
`phrase modi$ing "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 node of the syntax
`
`15
`
`parse free 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. The
`
`existing nodes initially comprise only leaf nodes, but, as syntactic analysis
`
`applies syntax rules, the existing nodes comprise both leaf nodes as well as
`
`20
`
`intermediate-level nodes. A single root node of a complete syntax parse free
`
`represents an entire sentence.
`
`Semantic analysis generates a logical form graph that describes the
`
`meaning of input text in a deeper way than can be described by a syntax parse
`free alone. The logical f rm graph is a first attempt to understand the input text
`
`25
`
`at a level analogous to that achieved by a human speaker of the language.
`
`if,
`-Li
`\./ I
`i
`
`Page 8 of 535
`
`
`
`4
`
`The logical form graph has nodes and links, but, unlike the syntax
`
`parse tee described above, is not hierarchically ordered. The links of the logical
`
`form graph are labeled to indicate the relationship between a pair of nodes. For
`
`example, semantic analysis may identiff a certain noun in a sentence as the deep
`
`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 action 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 active 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, and the deep object of a passive voice verb
`
`may be the slmtactic subject of the sentence. For example, consider the two
`
`sentences: (1) "Dogs bite people" and (2) "People are bitten by dogs." The frst
`
`sentence has an active voice verb, and the second sentence has a passive voice
`
`verb. The syntactic subject of the fust sentence is 'oDogs" and the syntactic
`object of the verb "bite" is "people." By contras! the syntactic subject of the
`
`15
`
`second sentence is "People" and the verb phrase "are bitten" is modified by the
`
`agentive-by phrase "by dogs." For both sentences, "dogs" is the deep subjec!
`
`and "people'o is the deep object of the verb or verb phrase of the sentence.
`
`Although the syntax parse trees generated by syntactic analysis for sentences 1
`
`20
`
`and 2, above, will be different, the logical form graphs generated by semantic
`
`analysis will be the same, because the underlying meaning of the two sentences
`
`is the same.
`
`Further semantic processing after generation of the logical form
`
`graph may draw on knowledge databases to relate analyzed text to real world
`
`25
`
`concepts in order to achieve still deeper levels of understanding. An example
`
`'-)
`
`Page 9 of 535
`
`
`
`knowledge base would be an on-line encyclopedia, from which more elaborate
`
`definitions and contextual information for particular words can be obtained.
`In the following, the three NLP subsystems - morphological,
`syntactic, and semantic -- are described in the context of processing the sample
`input texf "The person whom I met was my friend." Figure 1 is tr block
`diagram illustrating the flow of information between the NLP subsystems. The
`
`morphological subsystem 101 ieceives the input text and outputs an
`
`identification of the words and senses for each of the various parts of speech in
`
`which each word can be used. The syntactic subsystem 102 receives this
`
`10
`
`information and generates d synto( parse tree by applying syntax rules. The
`
`semantic subsystem 103 receives the syntax parse ffee and generates a logical
`
`form graph.
`
`Figures 2-S display the dictionary information stored on an
`
`elecfronic storage medium that is retieved for the input words of the sample
`
`15
`
`input text during morphological analysis. Figure 2 displays the dictionary enfiies
`
`for the input words 'othe" 201 and "person" 202. Enbry 201 comprises the key
`"the" 203 and a list of atffibute/value pairs. The first attribute *Adj' 204 has, as
`
`its value, the symbols contained within the braces 205 and 206. These symbols
`
`comprise two frrther atfribute/value pairs: (1) "Lemmt' | "the" and (2) "Bits" /
`
`20
`
`"Sing Plur Wa6 Det Art B0 Def." A lemma is the basic, uninflected form of a
`word. The attribute o'Lemma" therefore indicates that "the" is the basic,
`
`uninflected form of the word represented by this enty in the dictionary. The
`atfibute "Bits" comprises a set of abbreviations representing certain
`morphological and syntactic information about a word. This information
`indicates that "the" is: (1) singular; (2) plural; (3) not inflectable; (4) a
`
`25
`
`Il. r'r
`
`Page 10 of 535
`
`
`
`6
`
`determiner; (5) an article; (6) an ordinary adjective; and (7) definite. Attribute
`
`204 indicates that the word "the" can serve as an 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
`
`examples, a portion of which are included in the list of atfribute/value pairs
`
`between braces 208-2Og and between braces 2L}-ZLI. Additional meanings
`
`actually contained in the enty for "the" have been omitted in Figure 2, indicated
`
`by the parenthesized expression "(more sense records)" 213.
`
`In the frst step of natural language processing, the morphological
`
`10
`
`subsystem recognizes each yord and punctuation symbol of the input text as a
`
`separate token and constructs an atfribute/value record for each part of speech of
`
`each token using the dictionary information. Attributes are fields within the
`
`records that can have one of various values defined for the particular attribute.
`
`These attribute/value records are then passed to the syntactic subsystem for
`
`15
`
`further processing, where they are used as the leaf nodes of the syntax parse ffee
`
`that the syntactic subsystem constructs. All of the nodes of the syntax parse tee
`
`and the logical form. graph constructed by subsequent NLP subsystems are
`
`atfibute/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 synta,x parse tree that represents the sample
`
`input text. A complete syntax parse ffee includes a root node, intermediate-level
`
`nodeso and leaf nodes. The root node represents the syntactic construct (e.g.,
`
`declarative sentence) for the sample input text. The intermediate-level nodes
`
`$
`
`Page 11 of 535
`
`
`
`7
`
`represent intermediate syntactic constructs (e.g., verb, noun, or prepositional
`
`phrases). The leaf nodes represent the initial set of atffibute/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
`
`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 nodes to
`pairs of leaf nodes, ffid, occasionally, to larger groups of leaf nodes. If the
`
`syntactic rule requires two leaf nodes upon which to operate, and a par of leaf
`
`nodes both contain auributes that match the requirements specified in the rule,
`
`10
`
`then the rule is applied to them to create a higher-level syntactic consffuct. 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
`the two leaf nodes representing "my'' and "friend" to the newly created
`
`15
`
`intermediate-level node. As each new intermediate-level node is created, it is
`
`linked to already-existing leaf nodes and intermediate-level nodes, and becomes
`
`part of the total set of nodes to which the syntax rules are applied. The process
`
`of applying symtax rules to the growing set of nodes continues until either a
`
`20
`
`complete syntax parse fiee is generated or until no more syntax rules can be
`
`applied. A complete syntax 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,
`
`JJI*in
`.t
`
`Page 12 of 535
`
`
`
`8
`
`complete syntax parse tree. Moreover, this method of parsing can
`
`simultaneously generate more than one complete syntax parse ffee.
`
`The syntactic subsystem can conduct an exhaustive search for all
`
`possible complete syntax parse trees by continuously applying the rules until no
`
`additional rules can be applied. The syntactic subsystem can also fiy various
`
`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
`syntax parse fees. If no pomplete syntax parse fiees are generated after a
`
`10
`
`reasonable search, then a fitted parse can be achieved by combining the most
`
`promising sub-ffees together into a single tree using a root node that is generated
`
`by the application of a special aggregation rule.
`
`Figure 6 illusfiates the initial leaf nodes created by the syntactic
`
`15
`
`subsystem for the dictionary entries initialty displayed in Figures 2-5. The leaf
`
`nodes include two special nodes, 601 and 6L4,that represent the beginning of
`
`the sentence and the period terminating the sentence, respectively. Each of the
`
`nodes 602-613 represent a single part of speech that an input word can represerf
`
`in a sentence. These parts of speech are found as atfribute/value pairs in the
`
`dictionary entries. For example, leaf nodes 602 and 603 represent the two
`
`possible parts of speech for the word "The," that are found as attributes 204 and
`
`2l2nFigure 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
`
`25
`
`application of a single syntax rule to generate an intermediate-level node that
`
`il*\
`
`\
`
`Page 13 of 535
`
`
`
`9
`
`represents a syntactic structure. Only the rules that produce the intermediate-
`
`level nodes that comprise the final syntax fiee are illustrated. The syntactic
`
`subsystem generates many intermediate-level nodes which do not end up
`
`included in the final synta:< parse fiee.
`
`In Figures 7-14, the syntactic subsystem applies unary syntax ru1es
`
`that create intermediate-level nodes that represent simple verb, noun, and
`
`adjective phrases. Starting with Figure 15, the syntactic subsystem begins to
`
`apply bioaty syntax rules that combine simple verb, noun, and adjective phrases
`
`into multiple-word syntactic constructs. The syntactic subsystem orders the
`
`10
`
`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
`
`existing nodes. 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 phrase. The rule specifies the characteristics
`
`15
`
`required of the adjective and noun phrases. In this example, the adjective phrase
`
`must be a determiner. By following the pointer from node 1501 back to node
`
`1503, and then accessing morphological information included in node 1503, the
`
`syntactic subsystem determines that node 1501 does represent a determiner.
`
`Having located the two nodes 1501 and 1502 that meet the characteristics
`
`20
`
`required by the rule, the syntactic subsystem then applies the rule to create from
`
`the two simple phrases 1501 and 1502 an intermediateJevel node that represents
`
`the noun phrase "my friend." ln Figure 22, the syntactic subsystem generates the
`
`final, complete syntax parse fiee representing the input sentence by applying a
`
`trinary rule that combines the special Beginl leaf node 22A\ the verb phrase
`"The person whom I met was my friend" 2202, and the leaf node 2203 that
`
`.. /i
`L"*-'
`
`Page 14 of 535
`
`
`
`10
`
`represents the final terminating period to form node 2204 representing the
`
`declarative sentence.
`
`The semantic subsystem generates a logical form Saph from a
`complete syntax parse fiee. In some NLP systems, the logical form graph is
`
`constucted from the nodes of a syntax parse tree, adding to them atffibutes and
`
`new bi-directional links. The logical form 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 ftee from within nodes of the logical fonn
`gaph. Both the directions'and labels of the links of the logical form graph
`
`10
`
`represent semantic information, including the functional roles for the nodes of
`
`the logical form graph. During its analysis, the semantic subsystem adds links
`
`and nodes to represent (1) omitted, but implied, words; (2) missing or unclear
`arguments and adjuncts for verb phrases; and (3) the objects to which
`
`15
`
`prepositional phrases refer.
`
`Figure 23 illustrates the complete logical form graph generated by
`
`the semantic subsystem for the example input sentence. Meaningful labels have
`
`been assigned to links 2301 -2306 by the semantic subsystem as a product of the
`
`successful application of semantic rules. The six nodes 2307-2312, along with
`
`the links between them, represent the essential components of the semantic
`
`meaning of the sentence. ln general, the logical form nodes roughly correspond
`
`to input words, but certain words that are unnecessary for conveying semantic
`
`meaning, such as "The" and "whom" do not appear in the logical form graph,
`
`and the input verbs "met" and "was" appear as their infinitive forms "meef' and
`
`'obe." The trodes are represented in the computer system as records, and contain
`
`il
`\1
`i\
`
`Page 15 of 535
`
`
`
`11
`
`additional information not shown in Figure 23. The fact that the verbs were
`
`input in singular past tense form is indicated by additional information within the
`
`logical form nodes coresponding to the meaning of the verbs, 2307 and23l0.
`
`The differences between the syntax parse tee and the logical form
`
`graph are readily apparent from a comparison of Figrre 23 to Figare 22. The
`synta:< parse free displayed in Figure 22 includes 10 leaf nodes and 16
`
`intermediateJevel nodes linked together in a strict hierarchy, whereas the logical
`
`form graph displayed in Figwe 23 contains only 6 nodes. Unlike the syntax
`
`parse free, the logical form graph is not hierarchically ordered, obvious from the
`
`10
`
`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, analyzrng groups of sentences, and
`generally attempting to assemble around each logical form graph a rich
`
`contextual environment approximating that in which humans process natural
`
`language.
`
`Prior art methods for generating lolical form graphs involve
`
`computationally complex adjustments to, and manipulations of the syntax parse
`
`tree. As a resulg it becomes increasingly difficult to add new semantic rules to a
`
`NLP system. Addition of a new rule involves new procedural logic that may
`
`conllict with the procedural logic already programmed into the semantic
`
`subsystem. Furthermore, because nodes of the syntax parse free are extended
`
`25
`
`and reused as nodes for the logical form graph, prior art semantic subsystems
`
`\
`
`Page 16 of 535
`
`
`
`12
`
`produce large, cumbersome, and complicated data sfuctures. The size and
`
`complexity of a logical form graph overlayed onto a syntax parse free makes
`firrther use of the combined data structure error-prone and inefficient.
`Accordingly, it would be desirable to have a more easily extended and
`manageable semantic subsystem so that simple logical form gaph data structures
`
`can be produced.
`
`Summary of the Invention
`
`The present invention is directed to a method and system for
`
`10
`
`performing semantic analysip of an input sentence within a NLP system. The
`semantic analysis subsystem receives a syntax parse tee generated by the
`
`morphological and syntactic subsystems. The semantic analysis subsystem
`
`applies two sets of semantic rules to make adjustrnents to the received syntax
`
`parse tree. The semantic analysis subsystem then applies a third set of semantic
`
`15
`
`rules to create a skeletal logical form graph from the syntax parse tree. The
`
`semantic analysis subsystem 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 uni$/ redundant logical forrn guph nodes. The final
`
`logical fonugaph generated by the semantic analysis subsystem represents the
`
`complete semantic analysis of an input sentence.
`
`Brief Description of the Drawings
`
`Figure 1 is a block diagram illustrating the flow of information
`25 between the subsystems of a NLP system.
`
`ii -
`\l1 .,/
`
`Page 17 of 535
`
`
`
`13
`
`Figures 2-5 display the dictionary information stored on an
`
`elecfionic storage medium that is retrieved for each word of the example input
`sentence: o'The person whom I met was my friend."
`Figure 6 displays the leaf nodes generated by the syntactic
`subsystem as the frst step in parsing the input sentence.
`
`Figures 7-72 display the successive application of syntax rules by
`
`the syntactic subsystem to parse of the input sentence and produce a syntax parse
`
`tree.
`
`Figure 23 illustrates the logical form graph generated by the
`
`10
`
`semantic subsystem to repre$ent the meaning of the input sentence.
`
`Figure 24 shows a block diagram illustrating a preferred computer
`
`system for natural language processing.
`Figure 25 illusfrates the three phases of the preferred new
`
`semantical subsystem.
`
`15
`
`Figure 26 is a flow diagram for the new semantic subsystem
`
`cNSs).
`
`Figure 27 displays the first set of semantic rules.
`
`Figure 28A displays a detailed description of the semantic rule
`PrLF-You from the first set of semantic rules.
`Figure 288 displays an example application of the semantic rule
`
`\
`
`PrLF_You frortr the fust set of semantic rules.
`
`Figure 29 displays the second set of semantic rules.
`
`Figures 304.-308 display a detailed description of the semantic
`
`rule TrLF_MoveProp from the second set of semantic rules.
`
`1L{
`tt
`
`I
`
`Page 18 of 535
`
`
`
`t4
`
`Figure 30C displays an example application of the semantic rule
`
`TrLF_MoveProp from the second set of semantic rules.
`
`Figure 31 displays a flow diagram for appll'_rules.
`
`Figure 32 displays a flow diagram for phase one of the NSS.
`
`Figure 33 displays the third set of semantic rules.
`-grta
`Figures 34A-F, display a detailed description of the semantic rule
`
`Jfr'S
`
`SynToSeml from the third set of semantic rules.
`
`Figure 34D displays an example application of the semantic rule
`
`SynToSeml from the third set of semantic rules.
`
`10
`
`Figure 35 dispiays a flow diagram for phase two of the NSS.
`
`Figotes 36-38 display the fourth set of semantic rules.
`
`Figure 39A displays a detailed description of the semantic rule
`
`LF*pobj2 from the fourth set of semantic rules.
`
`Figure 39B displays an example application of the semantic rule
`
`15
`
`LF_Dobj2 from the fourttr set of semantic rules.
`
`{;u
`
`Figure 40 displays the fifth set of semantic rules.
`4tp
`Figures 4IA-p display a detailed description of the semantic rule
`
`PslF_PronAnaphora from the fifth set of semantic rules.
`
`Figure 41D displays an example application of the semantic rule
`
`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-59 display each successful rule application by the NSS
`
`as it processes the syntax parse free generated for the example input sentence.
`
`riI".att
`
`II
`
`Page 19 of 535
`
`
`
`15
`
`Detailed Description of the Invention
`
`The present invention provides a new semantic method and system
`for generating a logical form graph from a synta:r tee. In a preferred
`embodiment, a new semantic subsystem (NSS) performs the semantic analysis in
`
`three phases: (1) fr[ing in and adjusting the syntax parse tee, (2) generating an
`
`initial logical form graph, ffid (3) generating meaningful labels for links of the
`
`logical 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 synta>< tree
`
`10
`
`nodes or to a set of logical form Saph nodes.
`The NSS addresses the recognized deficiencies in prior art
`semantic subsystems described above in the background section. Each phase of
`
`the NSS is a simple and extensible rule-based method. As additional linguistic
`
`phenomena are recogmzed, rules to handle them can be easily included into one
`
`15
`
`of the rule sets employed by the NSS. In addition, the second phase of the NSS
`
`generates an entirely separate logical form graph, rather than overlaying the
`
`logical form 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 form graph data structures.
`
`20
`
`Figure 24 ts a block diagram illusfiating a preferred computer
`system for a NLP system. The computer system 240L contains a cenfral
`
`processing unit, a memory, a storage device, and input and output devices. The
`
`NLP subsystems 2406-2409 are typically loaded into memory 24A4 from a
`
`computer-readable storage device such as a disk. An application program 2405
`
`that uses the services provided by the NLP system is also typically loaded into
`
`(i!
`
`i
`llatlt
`v
`
`Page 20 of 535
`
`
`
`t6
`
`memory. The elecfronic dictionary 2411 is stored on a storage device, such as a
`
`disk 2410, ffid entries are read into memory for use by the morphological
`
`subsystem. In one embodiment, a user typically responds to a prompt displayed
`
`on the output device 2403 by entering one or more natrral language sentences on
`
`an input device 2404. The natural iaoguuge sentences are received.by the
`application, processed, and then passed to the NLP system by way of the
`
`morphological subsystem 2406. The morphological subsystem uses information
`
`from the elecfionic dictionary to construct records describing each input word,
`
`and passes those records to the syntactic subsystem 2407. The syntactic
`
`10
`
`subsystem parses the input *.ords to consffuct a syntax parse free and passes the
`
`syntax parse tee to the semantic subsystem 2408. The semantic subsystem
`
`generates a logical form graph from the received syntax parse ffee and passes
`
`that logical form graph to other NLP subsystems 2409. The application program
`then can send and receive information to the natural language subsystem 24Og n
`
`15
`
`order to make use of the machine understanding of the input text 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 semantic
`
`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 250I, 25A3, 2505,
`
`and2507. The NSS receives a syntax parse tree 2501 generated by the syntactic
`
`subsystem. The first phase of the NSS 2502 com