Y-J'.#
`
`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
`
`
`
`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
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
