Sentence realization model for a natural language generation system

BACKGROUND OF THE INVENTION

P-0001[0001] The present invention deals with natural language generation. More specifically, the present invention deals with sentence realization in a natural language generation system.

P-0002[0002] A natural language generation system generates a text from a linguistic representation of a sentence. Such systems typically include a text planner or content selection portion, a sentence planner portion and a sentence realization portion.

P-0003[0003] The text planner or content selection component obtains, as an input, content which is to form the basis of the realized text. The sentence planning portion determines how to organize the content into sentences, and the sentence realization component generates the actual output sentence.

P-0004[0004] For example, assume that the text planner provides content words such as “Little Red Riding Hood”, “walking”, and “grandmother's house”. The sentence planner determines that “Little Red Riding Hood” is the agent, the action is “walking”, and the destination is “grandmother's house”. The sentence planner provides this abstract linguistic representation as an input to the sentence realization component. The sentence realization component performs the complex task of mapping from the abstract linguistic representation to an actual sequence of words and punctuation corresponding to that abstract linguistic representation. The actual sequence of words and punctuation is the realized sentence (also referred to as the surface string) which is output by the system.

P-0005[0005] Prior systems which have attempted sentence realization have tended to be one of two different types of systems. The first type of system is a hand-coded, rule-based system that successively manipulates the linguistic representation to produce representations from which the surface string can simply be read. In such systems, computational linguists typically explicitly code strategies for stages ranging from planning texts and aggregating content into a single sentence, to choosing appropriate forms of referring expressions, performing morphological inflection and formatting an output. Such systems have typically included a very large volume of handwritten code which is extremely time consuming to produce. In addition, such hand-coded systems encounter great difficulty in adapting to new domains, and even more difficulty adapting to different languages.

P-0006[0006] The second type of sentence realization system which was typically used in the past attempted to generate candidate sentences directly from the input linguistic representation. For example, such systems have been used in highly domain specific applications (such as in flight reservations) in which there are a finite number of templates, and the content words are simply assigned to the various slots in the templates. The filled in templates are used to directly generate an output.

P-0007[0007] Other similar systems enumerate all possible candidate sentences which can be generated from the abstract linguistic representation of the sentence. In these cases, the candidate sentences are evaluated using statistical techniques that prefer the sentences in which combinations of words most closely match combinations observed in real text. However, for a given linguistic representation, the number of candidate sentences to be examined can be extremely large. This leads to slow computation times as each candidate must be evaluated. Furthermore the techniques used to evaluate the candidate sentences often perform poorly on long distance linguistic phenomena. This makes such systems ill-suited to genres of languages in which long distance phenomena are common.

P-0008[0008] Examples of systems discussed above are set out in Langkilde, I. and K. Knight, 1998, <i>The Practical Value of N</i>-<i>Grams in Generation</i>, Proceedings of the 9th International Workshop on Natural Language Generation, Niagara-on-the-Lake, Canada, pages 248-255; and Langkilde, I. and K. Knight, 1998, <i>Generation that Exploits Corpus</i>-<i>Based Statistical Knowledge</i>, Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics (COLING-ACL 1998), Montreal, Quebec, Canada, pages 704-710.

P-0009[0009] In the first of these systems, word bi-grams are used instead of deep symbolic knowledge to decide among alternative output sentences. Two sets of knowledge-engineered rules operate on the input specification to produce candidate output sentences. One set of rules performs one-to-many mappings from under-specified semantics to possible syntactic formulations, fleshing out information such as definiteness and number that might be missing in practical generation contexts such as Japanese-to-English machine translation systems. The second set of rules, which include sensitivity to the target domain, transforms the representations produced by the first module to yield still more candidate sentences that are represented as a word lattice. Word bi-grams are used to find the optimal traversal of the lattice, yielding the best-ranked output sentence. Morphological inflection is performed by simple table look up.

P-0010[0010] This system is one which generates a very large number of candidate sentences which must be processed. For example, in one of the work examples in Langkilde, I. and K. Knight, the input semantic form includes five lexical nodes in such relationships as AGENT, DESTINATION, and PATIENT. The word lattice that results from this semantic input contains more 11 million possible paths, with the top-ranked candidate being “Visitors who came in Japan admire Mount Fuji.” Another such example (for which the semantic input representation is not given) appears to contain only two content words that are transformed into a lattice containing more than 155,000 paths to yield the top-ranked candidate “I can not betray their trust.”

P-0011[0011] The use of bi-grams in this system also leads to other disadvantages. Bi-grams are unable to capture dependencies among non-contiguous words. Increasing the number of terms to tri-grams, or even higher order n-grams, raises the well-known problem of data sparsity.

P-0012[0012] Other prior work relevant to the parts of the present disclosure referred to below as the order model includes “generative” parsing models. Such models are employed in the parsing (i.e., syntactic analysis) process to assign probabilities to alternative syntactic trees. The name “generative” indicates that the model can also be sampled randomly to generate a sentence structure according to the distributions in the model. Such a model can assign a probability to possible constituent constructions, given relevant features during the generation process, as in the parsing process.

P-0013[0013] Examples of such parsing models are set out in the following publications. Eugene Charniak, “A Maximum-Entropy-Inspired Parser”, appearing in the Proceedings of NAACL-2000, Seattle, Wash., pp. 132-139. Also: Eugene Charniak, “Immediate-Head Parsing for Language Models” appearing in the Proceedings of the 39th Annual Meeting of the Association for Computational Linguistics (2001), Toulouse, France, pp. 116-123. In the work described in these papers, assessments of constituent probability are conditioned on contextual information such as the head of the constituent. One aspect of the order model in the present invention that sets the work to be disclosed here apart from the models of Charniak and from prior generative parsing models is the use of semantic relations available to the generation task.

SUMMARY OF THE INVENTION

P-0014[0014] The present invention is a sentence realization system that processes an abstract linguistic representation (ALR) of a sentence into a structure that can be fully realizable. The system includes a tree conversion component that receives the ALR and generates a basic syntax tree from the ALR. A global movement component then receives the basic syntax tree and hierarchically orders child nodes in that syntax tree relative to ancestor nodes. An intra-constituent ordering component then establishes a linear order among the nodes such that the syntax tree is fully ordered. A surface cleanup component receives the fully ordered tree and performs a number of realization operations to generate surface realizations for constituents that are still represented in an abstract way in the fully ordered syntax tree.

P-0015[0015] In one embodiment a punctuation insertion component then inserts punctuation into the syntax tree to obtain a fully ordered, punctuated syntax tree. This tree can simply be read off to obtain a realized sentence.

P-0016[0016] In various embodiments, the system also includes an inflection generation component that is placed in the pipeline after the punctuation insertion component. The inflection generation component modifies the syntax tree to reflect correct inflection based on attributes in the syntax tree.

P-0017[0017] In another embodiment, the ALR is an underspecified representation that needs to be fleshed-out prior to being converted into a basic syntax tree. In that embodiment, a flesh-out component adds syntactic labels to the nodes in the ALR. In other embodiments, the flesh-out component can also insert function words and assign probability of realization to logical subjects and logical objects in the ALR. Similarly, the flesh-out component can identify the case of noun phrases and can also assign verb position to verbs in the ALR.

P-0018[0018] In yet another embodiment, the ALR is received as a logical form graph, or another type of graph structure. The ALR is first be degraphed into a tree-like structure for further processing. Thus, a preprocessing component is included which degraphs the ALR.

BRIEF DESCRIPTION OF THE DRAWINGS

P-0019[0019]FIG. 1 is a block diagram of one exemplary environment in which the present invention can be used.

P-0020[0020]FIG. 2 is a block diagram of one embodiment of the present invention, illustrating data flow.

P-0021[0021]FIG. 3 is an exemplary semantic representation of a sentence used as an input to the present invention, and is embodied as a logical form.

P-0022[0022]FIG. 4 is a flow diagram better illustrating preprocessing of the input.

P-0023[0023]FIG. 5 illustrates a data structure representative of the output of the preprocessing component.

P-0024[0024]FIG. 6 is a flow diagram better illustrating the operation of the fleshing out component.

P-0025[0025]FIG. 7 illustrates the output of the fleshing out component.

P-0026[0026]FIG. 8 is a flow diagram illustrating the operation of the basic tree conversion component.

P-0027[0027]FIG. 9 illustrates a basic tree output by the basic tree conversion component.

P-0028[0028]FIG. 10 is a flow diagram better illustrating the global movement component.

P-0029[0029]FIG. 11 illustrates the output of the global movement component.

P-0030[0030]FIG. 12 is a flow diagram better illustrating the operation of the intra-constituent ordering component.

P-0031[0031]FIGS. 12A and 12B illustrate operation of the intra-constituent ordering component.

P-0032[0032]FIG. 12C further illustrates operation of the intra-constituent ordering component.

P-0033[0033]FIG. 13 illustrates the output of the intra-constituent ordering component.

P-0034[0034]FIG. 14 is a flow diagram illustrating the operation of a surface clean-up component.

P-0035[0035]FIG. 15 illustrates the output of the surface clean-up component.

P-0036[0036]FIG. 16 is a flow diagram illustrating the operation of the punctuation insertion component and the inflectional generation component.

P-0037[0037]FIGS. 17 and 19 illustrate the output of the punctuation insertion component and the inflectional generation component, respectively.

P-0038[0038]FIG. 18 is one illustrative embodiment of a record for a node that is input to the inflectional generation component.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

P-0039[0039] The present invention is described with respect to a sentence realization system. The present invention includes the overall sentence realization system and methods involved in that system. The present invention also, however, includes the individual sub-components or modules of the overall sentence realization system, in and of themselves. However, those modules or sub-components are described in the context of sentence realization, for better understanding.

P-0040[0040] It should also be noted that the description of the present invention set out below uses, as an example, a sentence in the German language. The German language presents a rather large number of hurdles which must be overcome by a sentence realization system and is thus used to exhibit the versatility of the present system in handling such situations. However, the present invention can be used with substantially any other language as well, and is not to be limited to the German language.

P-0041[0041] Of course, a number of the components or modules described herein are specific to the German language and can simply be removed or disabled when processing in other languages. Similarly, a number of modules specific to other languages can easily be added to the overall system of the present invention, to accommodate certain irregularities or phenomena in a given target language.

P-0042[0042]FIG. 1 illustrates an example of a suitable computing system environment <b>100</b> on which the invention may be implemented. The computing system environment <b>100</b> is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Neither should the computing environment <b>100</b> be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment <b>100</b>.

P-0043[0043] The invention is operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well known computing systems, environments, and/or configurations that may be suitable for use with the invention include, but are not limited to, personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

P-0044[0044] The invention may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices.

P-0045[0045] With reference to FIG. 1, an exemplary system for implementing the invention includes a general purpose computing device in the form of a computer <b>110</b>. Components of computer <b>110</b> may include, but are not limited to, a processing unit <b>120</b>, a system memory <b>130</b>, and a system bus <b>121</b> that couples various system components including the system memory to the processing unit <b>120</b>. The system bus <b>121</b> may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus also known as Mezzanine bus.

P-0046[0046] Computer <b>110</b> typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by computer <b>110</b> and includes both volatile and nonvolatile media, removable and non-removable media. By way of example, and not limitation, computer readable media may comprise computer storage media and communication media. Computer storage media includes both volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by computer <b>110</b>. Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Combinations of any of the above should also be included within the scope of computer readable media.

P-0047[0047] The system memory <b>130</b> includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM) <b>131</b> and random access memory (RAM) <b>132</b>. A basic input/output system <b>133</b> (BIOS), containing the basic routines that help to transfer information between elements within computer <b>110</b>, such as during start-up, is typically stored in ROM <b>131</b>. RAM <b>132</b> typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit <b>120</b>. By way of example, and not limitation, FIG. 1 illustrates operating system <b>134</b>, application programs <b>135</b>, other program modules <b>136</b>, and program data <b>137</b>.

P-0048[0048] The computer <b>110</b> may also include other removable/non-removable volatile/nonvolatile computer storage media. By way of example only, FIG. 1 illustrates a hard disk drive <b>141</b> that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive <b>151</b> that reads from or writes to a removable, nonvolatile magnetic disk <b>152</b>, and an optical disk drive <b>155</b> that reads from or writes to a removable, nonvolatile optical disk <b>156</b> such as a CD ROM or other optical media. Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive <b>141</b> is typically connected to the system bus <b>121</b> through a non-removable memory interface such as interface <b>140</b>, and magnetic disk drive <b>151</b> and optical disk drive <b>155</b> are typically connected to the system bus <b>121</b> by a removable memory interface, such as interface <b>150</b>.

P-0049[0049] The drives and their associated computer storage media discussed above and illustrated in FIG. <b>1</b>, provide storage of computer readable instructions, data structures, program modules and other data for the computer <b>110</b>. In FIG. 1, for example, hard disk drive <b>141</b> is illustrated as storing operating system <b>144</b>, application programs <b>145</b>, other program modules <b>146</b>, and program data <b>147</b>. Note that these components can either be the same as or different from operating system <b>134</b>, application programs <b>135</b>, other program modules <b>136</b>, and program data <b>137</b>. Operating system <b>144</b>, application programs <b>145</b>, other program modules <b>146</b>, and program data <b>147</b> are given different numbers here to illustrate that, at a minimum, they are different copies.

P-0050[0050] A user may enter commands and information into the computer <b>110</b> through input devices such as a keyboard <b>162</b>, a microphone <b>163</b>, and a pointing device <b>161</b>, such as a mouse, trackball or touch pad. Other input devices (not shown) may include a joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit <b>120</b> through a user input interface <b>160</b> that is coupled to the system bus, but may be connected by other interface and bus structures, such as a parallel port, game port or a universal serial bus (USB). A monitor <b>191</b> or other type of display device is also connected to the system bus <b>121</b> via an interface, such as a video interface <b>190</b>. In addition to the monitor, computers may also include other peripheral output devices such as speakers <b>197</b> and printer <b>196</b>, which may be connected through an output peripheral interface <b>195</b>.

P-0051[0051] The computer <b>110</b> may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer <b>180</b>. The remote computer <b>180</b> may be a personal computer, a hand-held device, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer <b>110</b>. The logical connections depicted in FIG. 1 include a local area network (LAN) <b>171</b> and a wide area network (WAN) <b>173</b>, but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.

P-0052[0052] When used in a LAN networking environment, the computer <b>110</b> is connected to the LAN <b>171</b> through a network interface or adapter <b>170</b>. When used in a WAN networking environment, the computer <b>110</b> typically includes a modem <b>172</b> or other means for establishing communications over the WAN <b>173</b>, such as the Internet. The modem <b>172</b>, which may be internal or external, may be connected to the system bus <b>121</b> via the user input interface <b>160</b>, or other appropriate mechanism. In a networked environment, program modules depicted relative to the computer <b>110</b>, or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation, FIG. 1 illustrates remote application programs <b>185</b> as residing on remote computer <b>180</b>. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.

P-0053[0053]FIG. 2 is a block diagram (also illustrating data flow) of sentence realization component <b>200</b> in accordance with one embodiment of the present invention. Sentence realization component <b>200</b> includes preprocessing component <b>202</b>, flesh-out component <b>204</b>, basic tree conversion component <b>206</b>, global movement component <b>208</b>, intra-constituent ordering component <b>210</b>, surface cleanup component <b>212</b>, punctuation insertion component <b>214</b>, inflectional generation component <b>216</b> and tree reader component <b>218</b>. The overall operation of system <b>200</b> is now described with a detailed discussion of the components of system <b>200</b> reserved for later Figures.

P-0054[0054] System <b>200</b> receives as an input an abstract linguistic representation of an input sentence. In the embodiment discussed herein, the input is a logical form. However, it will be appreciated that substantially any other syntactic or semantic representation of a sentence can be received as an input as well. A logical form structure is set out in greater detail in U.S. Pat. No. 5,966,686 issued Oct. 12, 1999 to Heidorn et al. entitled METHOD AND SYSTEM FOR COMPUTING SEMANTIC LOGICAL FORMS FROM SYNTAX TREES.

P-0055[0055] Preprocessing component <b>202</b> processes the abstract linguistic representation by degraphing the input. For example, where the input is a logical form, it is a graph structure, rather than a tree structure. Thus, the input structure is degraphed and converted into a more tree-like structure. Preprocessing component <b>202</b> also adds lexical information to the input structure, such as through a dictionary lookup operation. Preprocessing component <b>202</b> can also perform simplification of compounds. The output of preprocessing component <b>202</b> is a degraphed structure <b>220</b> which has additional information added thereto.

P-0056[0056] Flesh-out component <b>204</b> receives data structure <b>220</b> and adds syntactic information to that data structure. Flesh-out component <b>204</b> also inserts function words such as determiners, auxiliaries, semantically empty prepositions, relative pronouns, etc. Component <b>204</b> also assigns case features and verb-position features, as well as spell-out probabilities for noun phrases in subject or object positions. Flesh-out component <b>204</b> provides, as an output, structure <b>222</b> which is a degraphed structure with syntactic and other information added thereto.

P-0057[0057] Basic tree conversion component <b>206</b> receives data structure <b>222</b> and converts that data structure into a basic syntax tree. Component <b>206</b> reads off a syntactic tree structure from the degraphed data structure <b>222</b> and splits separable prefixes from their stem. Component <b>206</b> can also introduce a syntactic representation of coordination, and reverse certain syntactic dominance relations. Component <b>206</b> provides, as an output, a basic unordered syntax tree <b>224</b>.

P-0058[0058] Global movement component <b>208</b> receives structure <b>224</b> and performs global movement or global ordering. Global movement involves the movement of question words (Wh words), relative pronouns, and a process known in linguistic theory as raising. Component <b>208</b> also performs extraposition processing. Component <b>208</b> provides, as an output, structure <b>226</b> in which each constituent has the correct parent, although the constituents in <b>226</b> are unordered.

P-0059[0059] Intra-constituent ordering component <b>210</b> receives structure <b>226</b> as an input and fully orders the nodes in the syntax tree to provide a fully ordered syntax tree <b>228</b> at its output.

P-0060[0060] Surface cleanup component <b>212</b> receives structure <b>228</b> and performs surface cleanup operations, such as surface realization of determiners, relative pronouns and reflexive pronouns. Component <b>212</b> also deletes duplicated material in coordination. Component <b>212</b> provides, as an output, a clean, fully ordered syntax tree <b>230</b>.

P-0061[0061] Punctuation component <b>214</b> receives structure <b>230</b> and inserts punctuation marks into the syntax tree. Component <b>214</b> provides as its output the clean, fully ordered syntax tree, with punctuation inserted as indicated by numeral <b>232</b>.

P-0062[0062] Inflectional generation component <b>216</b> receives structure <b>232</b> and generates final inflection and outputs a final inflected tree <b>234</b>. Tree reading component <b>218</b> simply reads tree <b>234</b> and provides, as its output, surface string <b>236</b> (or realized sentence <b>236</b>) by simply applying all of the information in final inflected tree <b>234</b>.

P-0063[0063] Each of the components shown in FIG. 2 will now be discussed in greater detail with respect to an example. The example sentence discussed herein is in the German language and is as follows:

P-0064[0064] “Hans isst die Kartoffeln auf, die er gestern geernet hat”

P-0065[0065] This sentence translates as “Hans eats up the potatoes which he has harvested yesterday.” After the operation of the present system, this sentence is the surface string <b>236</b> which will be produced based on a linguistic representation of this sentence input to the system. It should also be noted that this example sentence will not illustrate each and every operation performable by the present invention, but has been chosen as an illustrative example only.

P-0066[0066]FIG. 3 illustrates the abstract linguistic representation input to system <b>200</b>. FIG. 3 shows that the abstract linguistic representation is embodied as a logical form in the present example, but could be substantially any other abstract linguistic representation which includes content words and syntactic or semantic information that represents the sentence to be generated.

P-0067[0067] Preprocessing component <b>202</b> receives the linguistic representation shown in FIG. 3 and performs a number of operations. FIG. 4 is a flow diagram better illustrating the operation of preprocessing component <b>204</b>. FIG. 4 illustrates that the logical form is first degraphed as illustrated by block <b>280</b>. In other words, a structure is created such that each node has at most one parent node. This operation creates a tree structure that facilities conversion into a syntactic tree in the following stages. Some nodes need to be duplicated in order to create the tree structure from the graph. If the nodes are created, indices are added which link them to their counterparts, thus preserving the information that the nodes were originally a single node in the graph. Such indices are referred to as “CoIndices”.

P-0068[0068] During the degraphing operation, certain logical form attributes are ignored. Such attributes include:

P-0069[0069] 1. System-internal bookkeeping attributes of no linguistic interest;

P-0070[0070] 2. Attributes which receive special handling elsewhere in the degraphing code (such as ParentAttrs (storing labels on arcs to parent nodes), Parents (storing pointers to parent nodes, and CoIndex)); and

P-0071[0071] 3. Attributes used only for advanced semantic processing, but not yet considered reliable or useful for generation.

P-0072[0072] Tables A, B and C set out in Appendix 1 hereto illustrate the pseudocode for the degraphing algorithm used in this example. It should be noted that this is but one example of a degraphing algorithm and substantially any other degraphing algorithm which changes the structure from a graph to a tree-like structure can be used. Table A is the pseudocode for a function referred to as DeepDegraphLF. This function calls the DeepDegraphLFsubgraph function set out in Table B. In that function, the logical form is traversed an nodes with more than one parent are duplicated. The indices are assigned so that subsequent processing can determine identity of nodes. The function shown in Table B makes reference to a list of Func_LF_Attrs, which is a list of attributes which lie outside of the argument structure of a predicate. These attributes CleftFOC (the focus of a left construction), Ltopic and L_top (topics), and CoCoords (a coordinated sibling node). The function shown in Table B, in turn, calls the CopyLFStruct function, which performs a deep copy or shallow copy operation, as appropriate, and maintains the CoIndex attribute. The pseudocode for the CopyLFStruct function is set out in Table C.

P-0073[0073] Once the logical form has been degraphed, the nodes are lexicalized as indicated by block <b>282</b>. In other words, a lexical look up is performed in a lexical database (such as an electronic dictionary) on each of the lexical items present in the graph. The dictionary information is stored in an attribute in the records in the graph. Finally, for the present example in the German language, compound nouns are simplified as indicated by block <b>284</b>.

P-0074[0074]FIG. 5 is a diagram of the degraphed, lexicalized structure <b>220</b> that is output by preprocessing component <b>202</b>. That structure is input to flesh-out component <b>204</b>. FIG. 6 is a flow diagram better illustrating the operation of flesh-out component <b>204</b>.

P-0075[0075] During the flesh-out processing, information is added to the degraphed structure shown in FIG. 5. Typically, this information relates to syntactic realization details that have been normalized at the more abstract logical form level of representation. As shown in FIG. 6, syntactic labels are first assigned to the nodes in the degraphed logical form shown in FIG. 5. This is indicated by block <b>290</b> in FIG. 6 and is illustratively performed by a decision tree classifier. The syntactic labels are added as attributes on the nodes. A more complete description of each of the decision tree classifiers referenced herein is set out in Appendix <b>2</b> to the present specification, and the reader is referred there for further details.

P-0076[0076] Once the syntactic labels are added to the nodes, function words are inserted in the degraphed structure. Since function words carry little semantic information, they are not in the logical form graph input to the system and thus must be added. The insertion of function words includes, in the example discussed herein, the insertion of determiners, auxiliaries, prepositions, infinitival markers, negators, subordinating conjunctions, and expletive subjects. Each of these function words is illustratively inserted by a decision tree classifier and the insertion of these function words is illustrated by numerals <b>292</b>-<b>304</b> in FIG. 6.

P-0077[0077] Again, reference is made to Appendix <b>2</b> herein for discussion of the appropriate decision tree classifiers. Briefly, however, abstract determiners, for example, include definite determiners (DefDet), indefinite determiners (InDefDet), WhDeterminers (WhDet), and demonstrative determiners (ProxlDet and DistlDet). The surface form of these determiners is fixed at a later stage in the processing (in the surface cleanup component <b>212</b>).

P-0078[0078] The insertion of prepositions includes insertion of prepositions which have a purely syntactic function. For example, in the German language, the prepositions “von” and “durch” used in the passive construction have a purely syntactic function and are inserted.

P-0079[0079] The insertion of infinitival markers includes insertion of, for example, “zu”. Subordinating conjunctions that are inserted include those such as “dass” and “ob”. Expletive subjects include those such as the semantically empty grammatical subject “es”.

P-0080[0080] After the function words are inserted, logical subjects and objects are assigned a probability for “spell-out”, illustratively by a decision tree classifier. This is indicated by block <b>306</b> in FIG. 6. More specifically, a probability of the logical subjects or objects being realized in the surface string is assigned. Logical subjects of infinitival clauses, for example, should not be overtly represented in the surface string.

P-0081[0081] Next, logical form nodes of prepositional proforms such as “dadurch” and “damit” etc., are contracted to their surface string. This is performed by a simple rule-based function and is indicated by block <b>308</b> in FIG. 6. This module is substantially related only to some Germanic languages. In the German language, such forms contain a preposition, “mit” or “für” in this example) and a pronominal element “da”. In the logical form, these words are decomposed into a representation similar to that of a full prepositional phrase, such as the prepositional phrase “mit das” (with that) and, “für das” (for that).

P-0082[0082] Abstract relative pronouns (RelPro) are next inserted. This is indicated by block <b>310</b>. Relative pronouns are later spelled out in the surface realization, during the surface cleanup process illustrated by block <b>212</b> in FIG. 2. For example, in the logical form, relative pronouns are replaced by a copy of the semantic node they are referring to. Thus, to obtain the surface realization, this copy must be replaced by the relative pronoun. The information necessary to do this is contained in the fleshed-out logical form and this operation is performed by a simple rule-based function.

P-0083[0083] Next, reflexive pronouns are inserted. This is indicated by block <b>312</b> and is again performed by a rule-based function. Reflexive pronouns are typically used in two contexts in the German language: there are inherently reflexive verbs, where the reflexive does not carry any semantic role, and there are normal transitive verbs used reflexively. In the first context, the reflexive does not appear in the logical form at all (but the verb is marked with a special feature ReflexSens) In the second context, it appears as a copy of the node that it refers to. Insertion of reflexive pronouns identifies these two different contexts and inserts a reflexive pronoun in the first context, and replaces the copy with the reflexive pronoun in the second context.

P-0084[0084] The Wh adverbial “wie” is then inserted as indicated by block <b>314</b>. “Wie” is a Wh adverb, like its English counterpart “How”. It is not represented as a node in the logical form of the present example, since its only function is to carry the Wh feature. Insertion of “wie” is a simple operation that is triggered if there is a “Wh” feature on a node, but no other Wh-carrying element has yet been inserted.

P-0085[0085] Case features and verb position features are then assigned by decision tree classifiers. This is indicated by blocks <b>316</b> and <b>318</b> in FIG. 6. Again, reference is made to Appendix <b>2</b> hereto for a more complete discussion of these decision tree classifiers. Briefly, however, case is an important feature in the German grammar. Constituent order is relatively free in the German language, and often only the case-marking on a noun phrase indicates whether it is to be interpreted as the subject, object, or indirect object of a sentence. During sentence realization, case serves as a proxy for grammatical subjecthood, etc. For surface realization it is therefore desirable to identify the case of a given noun phrase properly, in order to produce intelligible output.

P-0086[0086] One striking property of the German language is the pattern in which verbs are distributed in main and subordinate clauses. Most descriptive accounts of German syntax are based on a topology of a German sentence that treats the position of the verb as the fixed frame around which other syntactic constituents are organized in a relatively free order.

P-0087[0087] As is known, the general form of German sentences includes left and right bracket verbal positions which separate three fields, a pre-field, a middle field, and a post-field. The pre-field typically contains at most one constituent. The left bracket verb position contains the finite verb, a subordinating conjunction, or a relative pronoun/relative expression. The middle field can contain any number of constituents and the right verbal bracket contains all of the verbal material that is not present in the left bracket. The post-field typically contains clausal complements, subordinate clauses, extraposed material (e.g., relative clauses extraposed from the middle field) or other constituents.

P-0088[0088] Depending on the position of the finite verb, German sentences and verb phrases are often classified as being “verb-initial” “verb-second” or “verb-final”. In verb-initial clauses, the finite verb is in the initial position. Verb-second sentences contain material in the pre-field, and the finite verb in the left bracket position, and verb-final sentences contain no verbal element in the left bracket. This usually occurs because the left bracket is occupied by a subordinating conjunction or a relative pronoun.

P-0089[0089] In accordance with one embodiment of the present invention, a decision tree classifier is used to assign features that indicate the verb-positioning pattern in the constituent. Downstream components and functions then utilize the information present in these features.

P-0090[0090] After verb positioning features have been assigned, the fleshing out operation is complete and the degraphed structure with the added syntactic and other information is provided as output <b>222</b> in FIG. 2. FIG. 7 illustrates the degraphed logical form in accordance with the example under discussion, after it has been fleshed-out.

P-0091[0091] The fleshed-out and degraphed logical form <b>222</b> is then provided to basic tree conversion component <b>206</b> (shown in FIG. 2) where it is converted into a basic syntax tree structure. FIG. 8 is a flow diagram better illustrating the operation of basic tree conversion component <b>206</b>. The conversion is performed by conducting a recursive read-off of the degraphed logical form into a tree structure. In doing this conversion, the first operation is to remove the logical subjects and objects which have a low probability of overt realization, as indicated by block <b>350</b>. Recall that this probability was assigned by a decision tree classifier during the flesh-out operation.

P-0092[0092] Next, the degraphed logical form is mapped or copied to a tree structure as indicated by block <b>352</b> in FIG. 8. In doing this, the labels on non-terminal nodes of the tree are copied over from the nodes in the degraphed logical form (recall that the labels have been assigned during flesh-out). This is indicated by block <b>354</b> in FIG. 8.

P-0093[0093] Next, and specifically for the German language, separable prefixes are split from their stem, based on verb-position features assigned in the flesh-out stage, and based on lexical information (such as from the dictionary, inserted during preprocessing) about the boundary between the prefix and the stem. Splitting separable prefixes is indicated by block <b>356</b> in FIG. 8.

P-0094[0094] Splitting the verb into a stem and separable prefix is triggered under the following conditions:

P-0095[0095] 1. The verb is actually a separable prefix verb (as indicated by a lexical feature); and

P-0096[0096] 2. The verb occurs in a context where the stem should be separated (either in a verb-initial or in a verb-second structure, with no auxiliary or modal verb present that would carry the finiteness features).

P-0097[0097] If these conditions hold, lexical information on the verb determines where the split between stem and prefix should be made. The node is split into a STEM and a PREFIX node, and verb inflectional features are copied over to the stem.

P-0098[0098] The Parents attribute for each node is then updated based on the previous steps in FIG. 8. This is indicated by block <b>358</b> in FIG. 8.

P-0099[0099] In the next two steps <b>360</b> and <b>362</b>, the representation of coordination is mapped from the way it is handled in the abstract input (in the logical form) to a more surface-oriented structure. Coordination is a difficult aspect of natural language and is represented in different ways at the logical form level (at the abstract representation level) and during syntactic analysis. Syntactically, a conjunction can be treated as the head of a coordinated construction, with the coordinated phrases and additional conjunctions in the pre- and post-modifiers of that head. Semantically, there may be no single node for the coordinated phrase. Rather, each of the coordinated phrases has its own node, and enters into semantic relations by itself. In addition, each of the coordinated nodes maintains pointers to the semantic nodes of the other phrases that it is coordinated with in an attribute referred to herein as “CoCoords”. This idiosyncratic logical form representation is simplified by the two functions illustrated in steps <b>360</b> and <b>362</b>.

P-0100[0100] Step <b>360</b> introduces coordination non-roots, while step <b>362</b> introduces coordination roots. These two functions simplify the representation by adapting the tree structure that has been built directly from the degraphed logical form representation to the syntactic representation strategy. In essence, the functions convert the CoCoords attribute into coordinated syntactic nodes, with the conjunction as the head.

P-0101[0101] The final step <b>364</b> in FIG. 8 is referred to as the “Switch Heads” operation and is illustratively performed by a decision tree classifier. This step embodies the conversion to the basic tree, and the decision tree classifier reverses syntactic dominance relations in those contexts where syntactic and semantic dominance relations are at odds. Typically in German this occurs in quantificational examples of the kind “viele der Leute” where “viele” is the syntactic head but “Leute” is the semantic one.

P-0102[0102]FIG. 9 illustrates a basic tree structure for the example sentence, after processing by basic tree conversion component <b>206</b>. This structure is then provided to global movement component <b>208</b>. FIG. 10 is a flow diagram better illustrating the operation of global movement component <b>208</b> shown in FIG. 2.

P-0103[0103] During global movement, non-local movement operations are performed. Non-local, in this context, means movement beyond the limits of the immediate parent. All “local” movement in accordance with one embodiment of the present invention is treated as an ordering phenomenon within one constituent, instead of as a genuine movement. While raising, Wh-movement and the movement of relative pronouns/relative expressions are handled in the present example by simple rule-based functions, they could also be dealt with by a machine-learned system, such as a decision tree classifier.

P-0104[0104] In any case, once global movement component <b>208</b> receives structure <b>224</b>, it first performs raising movement as indicated by block <b>366</b> in FIG. 10. In accordance with one embodiment, two different raising functions are performed. One function raises nodes from adjective phrases (AJPs) and noun phrases (NPs) to the level of the copular verb in the predicative context. The other function raises subjects of raising verbs.

P-0105[0105] After the raising functions are performed, the Wh movement function is performed as illustrated by block <b>368</b> in FIG. 10. Wh movement is triggered if the structure contains a phrase marked by the “Wh” feature that is not dominated by another “Wh” or “WhQ” phrase (a direct or indirect Wh question) and if that phrase has an ancestor higher up in the tree that is marked as “WhQ”. Once this context is detected, the Wh phrases is moved up to the WhQ node.

P-0106[0106] Movement of relative pronouns or expressions is illustrated by block <b>370</b> in FIG. 10 and operates in a similar fashion to Wh movement, except that the triggering context is the presence of a relative pronoun that is not dominated by a relative clause. In this context, the relative pronoun is moved up to the first relative clause in its parent chain.

P-0107[0107] Extraposition processing is then performed. This is indicated by block <b>372</b> in FIG. 10. In a variety of languages, it is possible to extrapose clausal material to the right periphery of the sentence. For example, in German and English, this can be done with relative clauses. One example of these clauses is as follows:

P-0108[0108] “The man entered the room who usually causes trouble right away.”

P-0109[0109] “Der Mann hat den Raum betreten, der üblicherweise immer Ärger macht.”

P-0110[0110] A relative clause modifying “the man” has been shifted to the right edge of the sentence. This is particularly prevalent in languages such as German where it has been observed that nearly one-third of relative clauses are extraposed in technical writing.

P-0111[0111] The same is true, for example, with infinitival clauses:

P-0112[0112] “The possibility was considered to leave the country.”

P-0113[0113] “Man hat die Moglichkeit erwogen, das Land zu verlassen.”

P-0114[0114] The same can be observed with complement clauses such as:

P-0115[0115] “A rumor has been circulating that he is ill.”

P-0116[0116] “Ein Gerucht ging um, dass er krank ist.”

P-0117[0117] In this embodiment of the present invention, it is determined for each extraposable node (Infcl, Compcl, Relcl) whether the node should move up one step from its current attachment (i.e., from its parent node) to the next higher node (i.e., to its grandparent node). From the new position, another assessment is made for the next possible movement step, etc. Each movement is evaluated until a position is found where the probability of further movement is less than a predetermined threshold, such as 0.5. A trace is left behind in the original position with a pointer to the extraposed clause. In addition, a pointer is provided in the extraposed clause back to its original position.

P-0118[0118] The final two steps shown in FIG. 10 and represented by numerals <b>374</b> and <b>376</b> are functions that assign morphological features for verbs based on the information present in the tree nodes. The first function (Distribution of Verb-form Features) identifies the finite verb (which can be an inserted auxiliary, or modal) and shifts the tense, mood, and finiteness features to that verb. This function also marks the non-auxiliary verb as past participle if the construction is marked as perfective or passive, and it marks verbs as infinitives if a modal verb is present and there is no passive or perfective context.

P-0119[0119] The second function (Set Agreement Bits) identifies the grammatical subject as a nominative noun phrase that is in the domain of the verb. It then copies person and number features of that noun phrase onto the finite verb. If no grammatical subject is found, a default assignment of third person singular is made.

P-0120[0120]FIG. 11 illustrates the output of global movement component <b>208</b>. It can specifically be seen that in the example shown, extraposition of the relative clause has taken place.

P-0121[0121] The output illustrated in FIG. 11 is then input to intra-constituent ordering component <b>210</b> (shown in FIG. 2). FIG. 12 is a flow diagram better illustrating the operation of intra-constituent ordering component <b>210</b>.

P-0122[0122] The ordering of words and constituents varies across languages, as does the rigidity with which the canonical order has to be obeyed. The present examples will be discussed with respect to the English and German languages, since neither English nor German show examples where individual words can be ordered freely, outside of the immediate constituent that they belong to.

P-0123[0123] English has a relatively rigid constituent order, although a number of preposing and extraposing operations can alter that order. Thus, it is overly-simplistic to describe English as having “fixed” constituent order.

P-0124[0124] German, on the other hand, allows many major constituents to be rather freely distributed among the pre-field and middle-field, and to a somewhat lesser extent, to the post-field. At the same time, the position of the verb is fixed to the two bracket positions discussed above. Thus, it can be seen that word order plays a crucial role in establishing the fluency and intelligibility of a sentence.

P-0125[0125] Given a syntactic tree with unordered constituents for a sentence, one aspect of the present invention establishes linear order within each constituent, so that each modifier is placed in its proper position. Intra-constituent ordering component <b>210</b> can thus handle each constituent independently and in isolation, but the net effect is to establish linear order among all leaves of the tree.

P-0126[0126]FIG. 12A shows one node from a hierarchically ordered tree for purposes of illustration. The node is a noun phrase (NP) and has three child nodes, a determiner phrase (DetP), a noun (Noun) which is the head indicated by the asterisk, and an adjective phrase (AJP). Furthermore, the Noun is linked to each of its modifiers by a semantic relation as follows:

P-0127[0127] Noun→˜DefDet→DetP

P-0128[0128] And

P-0129[0129] Noun→˜Attrib→AJP

P-0130[0130] The intra-constituent ordering component orders each of the child nodes relative to one another. Thus, it can be seen that there are six possible orderings for the three nodes as indicated below:

P-0131[0131] DetP AJP Noun*

P-0132[0132] AJP Noun* DetP

P-0133[0133] Noun* AJP DetP

P-0134[0134] Noun* DetP AJP

P-0135[0135] DetP Noun* AJP

P-0136[0136] AJP DetP Noun*

P-0137[0137] In order to determine the proper ordering of the three child nodes (i.e., in order to select the best possibility or possibilities indicated above) intra-constituent ordering component <b>210</b> begins with the head node (in this case the Noun) and performs a staged search though all of the possibilities. If there are M child nodes, then the number of stages in the search is M-<b>1</b>.

P-0138[0138]FIG. 12B illustrates this search with respect to the example shown in FIG. 12A. Since there are three child nodes, there are two stages in the search. In stage <b>1</b>, component <b>210</b> begins with the head node (the noun) and enumerates all possibilities with respect to the remaining child nodes relative to the head node. Thus, it can be seen that there are four possibilities with respect to the ordering of the head node and the remaining child nodes. Each of these hypothesized orderings are scored using a language model (in one embodiment, with a bi-gram language model on nodetype and semantic relation) and are placed in ranked order.

P-0139[0139] Assume for the sake of example that the four possibilities shown in FIG. 12B are in ranked order according to their score. In the next stage, component <b>210</b> extends each hypothesis from the preceding stage in all possible ways by introducing an additional child node from the set of remaining nodes. In the present example, it can be seen that hypothesis one from stage one will spawn three different hypotheses in stage two, and hypothesis two from stage one will also spawn three different hypotheses in stage two. All of the hypotheses in stage two that would be spawned from hypotheses three and four in stage one are duplicates of those developed by extending hypotheses one and two from stage one into stage two. In an illustrative embodiment, the per-stage lists are maintained in priority queues containing only unique items. Thus, lists of unique orderings are maintained in rank order and without duplicates.

P-0140[0140] For each of the hypotheses spawned in stage two, component <b>210</b> computes the score by applying the language model to the extended sequence. The scored hypotheses are again placed in rank order, and those with scores above a threshold level (above a beam) are carried forward to the next stage, if any. Component <b>210</b> illustratively applies the language model from the head node outward in each direction, one constituent at a time. It can be seen that since the hypotheses from a previous stage spawn multiple additional hypotheses in a subsequent stage, the search space can grow quite quickly. However, using this beam search technique, the best hypotheses can be explored while maintaining the search space at a desirably low level.

P-0141[0141] In one illustrative embodiment, component <b>210</b> employs a generative statistical language model to score possible orders among a head and its modifiers as illustrated above.

P-0142[0142] For a given constituent the model assigns a probability to modifier n-grams in the context of several relevant features. Many features can be used as relevant context, such as the node type of the parent of the head (i.e., the constituent type), the node type of the head (i.e. part of speech), verb position bits on the parent of the head, the lemma of the head, and the node type of the grandparent of the head, among other possibilities. Furthermore, many features of the constituents to be ordered can be used, including node type (part of speech), semantic relation to the head constituent, lemma, and other lexical, syntactic, and semantic features.

P-0143[0143] In one illustrative embodiment, the model first predicts the semantic relation (from the logical form) of each modifier. This is done in the constituent contexts and in the context of the preceding n−1 neighbors. The model then predicts the node type (syntactic category) of the modifier.

P-0144[0144]FIG. 12C is another illustration showing the operation of the model. The model is split into a model of head pre-modifier order (pre-modifiers lie to the left of the Head in FIG. 12C) and post-modifier order (post-modifiers lie to the right of the Head in FIG. 12C). Included in the notion of neighbor are explicit pseudo-modifiers for marking the beginning and the end of the pre-modifiers (<Pr>and </Pr>, respectively) and for marking the end points of the post-modifiers (<Ps>and </Ps>). Hence, for any Parent/Head context, the model includes an n-gram distribution for pre-modifiers and an n-gram distribution for post-modifiers.

P-0145[0145] To elaborate on the previous example, consider the hypothesis Hi consisting of the sequence “DetP AJP Noun*”. It is scored by working out from the head (in this case, there are only pre-modifiers). As mentioned above, for the benefit of the model, we mark the beginning of the pre-modifers (with <Pr>) and the end of the pre-modifiers (with </Pr>). We do the same for the post-modifiers (with <Ps>and </Ps>). The resulting sequence is (<Pr>DetP AJP </Pr>Noun* <Ps> </Ps>). Note that an empty post-modifier sequence is significant and does contribute to the overall score for the hypothesis. The score P(H1) is computed as follows:

P-0146[0146] P(H1)=

P-0147[0147] P(</Pr>|Noun, NP)

P-0148[0148] ×P(</Pr>|</Pr>, Noun, NP)

P-0149[0149] ×P(Attrib|</Pr>, </Pr>, Noun, NP)

P-0150[0150] ×P(AJP|Attrib, </Pr>, </Pr>, Noun, NP)

P-0151[0151] ×P(˜DefDet|AJP, Attrib, </Pr>, </Pr>, Noun, NP)

P-0152[0152] ×P(DetP|˜DefDet, AJP, Attrib, </Pr>, </Pr>, Noun, NP)

P-0153[0153] ×P(<Pr>|DetP, ˜DefDet, AJP, Attrib, </Pr>, </Pr>, Noun, NP)

P-0154[0154] ×P(<Pr>|<Pr>, DetP, ˜DefDet, AJP, Attrib, </Pr>, </Pr>, Noun, NP)

P-0155[0155] ×P(<Ps>|Noun, NP)

P-0156[0156] ×P(<Ps>|<Ps>, Noun, NP)

P-0157[0157] ×P(</Ps>|<Ps>, <Ps>, Noun, NP)

P-0158[0158] ×P(</Ps>|</Ps>, <Ps>, <Ps>, Noun, NP)

P-0159[0159] Each of these probabilities can be estimated by looking at a limited number of predecessor nodes to the right (for pre-modifier sequences) or to the left (for post-modifier sequences). In an illustrative embodiment, this number can be restricted to one, yielding a bi-gram model, or two, yielding a tri-gram model. Furthermore, these probability distributions can be smoothed using any of the available approaches to smoothing known to those skilled in the art.

P-0160[0160] The ordering stage searches among all possible orders or at least among the most promising orders. As discussed above, the search proceeds by considering all possible incomplete orderings of length one, then those of length two, and so on, up to all possible complete orderings of length n. Each step in the search can be pruned to consider only those incomplete ordering hypotheses for which the model assigns a sufficiently high score. This search produces as many scored order hypotheses as desired. If the number of members in the constituent (counting the head and its modifiers) equals n, then there are n! possible orderings. Thus, for a relatively large constituent, the search space can be overwhelming. The beam search thus puts a practical limit on the complexity of the complete search.

P-0161[0161] This intra-constituent ordering model is represented by block <b>380</b> in FIG. 12. There are some additional linguistic constraints that can be used to modify the output of the ordering stage in step <b>380</b>, if needed. One constraint involves ordering in coordination, which ensures that conjunctions and coordinated phrases are in alternating order. This is indicated by block <b>382</b> in FIG. 12. In a second constraint, verb positioning is adjusted according to the verb position features that have been assigned by a decision tree classifier in the flesh-out stage. The verb positioning function shifts the finite verb to the left bracket position in verb-second and verb-initial structures and ensures that all non-finite verbs are aligned in the right bracket position. Fixing verb order is indicated by block <b>384</b> in FIG. 12. In a third constraint, the order of relative pronouns is adjusted as indicated by block <b>386</b>. This function moves relative pronouns to the beginning of the relative clause. Finally, the order of Wh phrases can be determined. This is indicated by block <b>388</b> in FIG. 12.

P-0162[0162] For the sentence used as the example herein, FIG. 13 illustrates the ordered tree output by the intra-constituent ordering component <b>210</b>. The structure illustrated in FIG. 13 is then provided to the surface cleanup component <b>212</b>.

P-0163[0163]FIG. 14 is a flow diagram which better illustrates the operation of surface cleanup component <b>212</b>. It can be seen from the structure in FIG. 13 that a number of things must still be done in order to arrive at a correct surface string. For example, there must be a surface realization of determiners. This is accomplished by a decision tree classifier (in the embodiment discussed herein) as illustrated by block <b>400</b> in FIG. 14. There are 55 different determiner forms which have been observed in the German training data. While the realization of the determiners can be specified by rule, it can also be determined by a decision tree classifier as discussed in Appendix 2 hereto. Thus, in the example currently under consideration, the abstract determiner “Defdet” is converted to its surface realization, namely “die”.

P-0164[0164] In addition, the relative pronoun “RelPro” must be converted to its surface realization as well. While this is also done, in one embodiment, using a decision tree classifier, it could be done using a hand-crafted selection process as well. Surface realization of relative pronouns is indicated by block <b>410</b> in FIG. 14.

P-0165[0165] Reflexive pronouns which also received an abstract form during insertion in flesh-out, are converted into their surface form by a rule-based function. This is indicated by block <b>412</b> in FIG. 14. The results of these operations for the present example sentence are illustrated in FIG. 15 which is indicative of a clean, fully ordered syntax tree <b>230</b>.

P-0166[0166]FIG. 14 shows that surface clean-up of stage <b>212</b> can contain additional functions which are not illustrated by the example currently being discussed. Such functions can include, for example, the reduction of duplication in coordinated constituents as indicated by block <b>414</b> in FIG. 14. To illustrate this function, consider a sentence such as:

P-0167[0167] “Hans hat die Kartoffeln gekocht und gegessen.” (Hans has cooked and eaten the potatoes.) The logical form for this sentence correctly establishes semantic relations between each of the verbs “kochen” (cook) and “essen” (eat) and the subject “Hans” and object “die Kartoffeln” (the potatoes). However, mapped to a tree structure through the present invention, the surface string will encode all of the relations that were present in the input logical form, resulting in duplication as follows:

P-0168[0168] “Hans hat die Kartoffeln gekocht und Hans hat die Kartoffeln gegessen.” (Hans has cooked the potatoes and Hans has eaten the potatoes).

P-0169[0169] While this is a perfectly grammatical German sentence, it is not a desired fluent output. Therefore, surface cleanup component <b>212</b> illustratively includes two operations that deal with the elimination of duplicates in coordination. The first operation indicated by numeral <b>414</b> in FIG. 14 is based on a decision tree classifier that establishes a probability of being overtly realized for each of the duplicated nodes in a coordination structure. The second operation illustrated by block <b>416</b> eliminates duplicated function words (such as prepositions and auxiliaries). These operations can be accomplished using machine-learned techniques or using rule-based procedures.

P-0170[0170] For example, in one embodiment, the first object and the second subject, and their associated function words, are deleted. This results in deletion of the first occurrence of “die Kartoffeln” (the potatoes) and the second occurrence of “Hans hat” (Hans has). Thus, the sentence reads “Hans hat gekocht und die Kartoffeln gegessen.” (Hans has cooked and eaten the potatoes).

P-0171[0171] Once the ordered syntax tree has undergone surface cleanup at component <b>212</b>, it is provided to punctuation insertion component <b>214</b> in FIG. 2. After punctuation is inserted, the tree is provided to inflectional generation component <b>216</b>. FIG. 16 is a flow diagram better illustrating the operation of punctuation insertion component <b>214</b> and inflectional generation component <b>216</b>.

P-0172[0172] Punctuation rules are difficult in German, and although more simplification has been achieved in the spelling reform, there are still <b>26</b> different rules for the correct positioning of the comma alone. Since punctuation conventions are typically in the form “insert punctuation x after y” or “insert punctuation x before y” two different decision tree classifiers are used for preceding and for following punctuation. In one illustrative embodiment, these models are only applied for sentence internal punctuation since sentence final punctuation can be inserted with a relatively simple rule-based function.

P-0173[0173] In one embodiment, at each terminal node in the tree <b>230</b> provided to punctuation insertion component <b>214</b>, the left edge of the terminal node, and the right edge of the preceding node are passed into the classifier for preceding and following punctuation, respectively. The verdicts from both classifiers are collected and if there is a strong prediction (such as, for example, greater than 0.5) for the insertion of punctuation, the strongest such prediction wins and the predicted punctuation mark is inserted into the tree. Punctuation labeling is indicated by block <b>420</b> in FIG. 16, and the fully punctuated syntax tree <b>232</b> for the present example is shown in FIG. 17.

P-0174[0174] A final stage prior to obtaining the final inflected tree <b>234</b> (shown in FIG. 2) is inflectional generation processing by inflectional generation component <b>216</b>. German has a very rich system of inflectional morphology. Particularly important for sentence realization as well as parsing in German is case marking on noun phrases. There are four cases in German: nominative, accusative, dative and genitive. Depending on a number of factors such as the morphological class of the lexical items, the choice of determiner, number and gender, case can be morphologically realized on various elements of the noun phrase: the noun itself, the determiners and adjectives (if present). The importance of case marking in German sentence realization stems from the fact that because of its relatively free constituent order, case is often an important tool in determining the semantic role of a noun phrase in the clause. If an (e.g., active) clause contains a nominative and accusative noun phrase, the nominative phrase can safely be assumed to be the subject, and the accusative to be the object, independently of their linear order in the sentence string.

P-0175[0175] The records in the tree structure at this point in the pipeline (just prior to inflectional generation component <b>216</b>) contain all necessary information to be passed into component <b>216</b>. Features that are passed into the inflectional generation component <b>216</b> for German include case, gender, number, person, etc. As an example, the record of the node STEM<b>1</b> in the tree shown in FIG. 17 is illustrated in FIG. 18. Based on the features Pers<b>2</b> SingPres Indicat, the verb for “isst” can be generated from the lemma “essen”. The terminal nodes in the syntactic tree, along with their inflectional bits and case information on nouns are passed into the generation function.

P-0176[0176] In one embodiment, the inflectional generation function is that which has been developed for the grammar checker in the “MICROSOFT®” Office products offered by the Microsoft Corporation of Redmond, Wash. This is but one example, and any others could be used for performing this type of morphological generation. This inflectional generation function utilizes a finite-state morphology. Performing inflectional generation is indicated by block <b>422</b> in FIG. 16. The final inflected syntax tree <b>234</b> provided by component <b>216</b> for the example under discussion is illustrated in FIG. 19.

P-0177[0177] Finally, tree reader component <b>218</b> simply reads the string off of the final inflected tree <b>234</b> to provide the surface string <b>236</b>. In accordance with the present invention, the surface string corresponds exactly to the sentence represented by the abstract linguistic input and is:

P-0178[0178] “Hans isst die Kartoffeln auf, die er gestern geerntet hat.” (Hans eats up the potatoes which he has harvested yesterday.) It can thus be seen that one embodiment of the present invention decomposes the entire process of sentence realization into a number of decision points. For some of these decision points, machine learned methods are used, while in others rule-based methods are used. Of course, most decision points can be implemented by either machine-learned components or rule-based components.

P-0179[0179] In one illustrative embodiment, at each decision point along the pipeline, only a threshold number of hypotheses are carried along to the next decision point. Thus, the present system does not enumerate every possible realization of a sentence. Instead, the hypotheses are ranked at each stage, and each stage passes on rank-ordered hypotheses that meet a predetermined threshold.

P-0180[0180] Each of the hypotheses passed on to a next stage can spawn multiple additional hypotheses in the next stage. Therefore, even in the present staged process, the search space could grow undesirably large. However, using the beam search technique, the present invention maintains the search space at a manageable size.

P-0181[0181] Of course, it should also be noted that the individual processing stages of the present overall system <b>200</b> are, in and of themselves, features of the present invention which can stand by themselves.

P-0182[0182] Similarly, a sentence realization system may not take as its abstract linguistic input a logical form but may take some other graph or dependency structure. In that case, the structure may enter the process illustrated in FIG. 2 at varying points along the pipeline. Thus, inventive concepts of the present invention can be used even where all processing stages are not used.

P-0183[0183] Similarly, it will certainly be noted that a number of the functions and processing stages discussed with respect to the present invention are specific to either English or German. In those cases, where different languages are being processed, the modules specific to English or German can simply be disabled or need not be present at all. Similarly, other modules or processing stages or functions specific to other desired languages can be added in the pipeline in accordance with the present invention without departing from the inventive concepts discussed herein.

P-0184[0184] Although the present invention has been described with reference to particular embodiments, workers skilled in the art will recognize that changes may be made in form and detail without departing from the spirit and scope of the invention.