(57)【要約】【課題】  順序付けられていない構文木を受け取り、順序付けられていない構文木から順序付けられた代替構文木のランク付けされたリストを生成する文章実現化システム内の木順序付け構成要素を提供すること。【解決手段】  本発明は、順序付けられた代替木を採点するのに木順序付け構成要素が使用する構成素構造の統計的モデルも含む。【選択図】  図２
2004295884.tif 000002
【特許請求の範囲】
【請求項１】
順序付けられていない構文木を受け取り、前記順序付けられていない構文木から順序付けられた代替構文木の採点かつランク付けされたリストを生成する文章実現化システム内の木順序付け構成要素であって、
形式構造を有し、統計的評価技術を使用してそのパラメータが推定される、素性を条件とする構成素構造の統計的モデルと、
前記順序付けられていない構文木を受け取り、可能な順序付けられた代替構文木の組を検討し、前記構成素構造の統計的モデルに従って前記順序付けられた代替構文木のどれが最も高い確率を有しているかを識別する検索構成要素と
を含むことを特徴とする木順序付け構成要素。
【請求項２】
前記構成素構造の統計的モデルにおいて、前記素性は自動素性選択技術によって選択されていることを特徴とする請求項１に記載の木順序付け構成要素。
【請求項３】
前記構成素構造の統計的モデルにおいて、前記モデルの前記パラメータは言語モデリング技術によって推定されることを特徴とする請求項１に記載の木順序付け構成要素。
【請求項４】
前記構成素構造の統計的モデルにおいて、前記モデルの前記パラメータは最大エントロピ技術によって推定されることを特徴とする請求項１に記載の木順序付け構成要素。
【請求項５】
前記構成素構造の統計的モデルにおいて、前記モデルの前記パラメータは決定木学習技術によって推定されることを特徴とする請求項１に記載の木順序付け構成要素。
【請求項６】
前記構成素構造の統計的モデルにおいて、前記モデルの前記形式構造は特定の向きを有するマルコフ法であることを特徴とする請求項１に記載の木順序付け構成要素。
【請求項７】
前記構成素構造の統計的モデルにおいて、マルコフ法構造を有する前記モデルは構成素構造の結合モデルであることを特徴とする請求項６に記載の木順序付け構成要素。
【請求項８】
前記構成素構造の統計的モデルにおいて、マルコフ法構造を有する前記モデルは右から左へのマルコフ法による構成素構造の条件付きモデルであることを特徴とする請求項６に記載の木順序付け構成要素。
【請求項９】
前記構成素構造の統計的モデルにおいて、前記モデルの前記形式構造はバイナリ条件付きモデルであることを特徴とする請求項１に記載の木順序付け構成要素。
【請求項１０】
前記構成素構造の統計的モデルにおいて、前記モデルの素性の組は前記順序付けられていない木の構成素の１つまたは複数の語彙素性を含むことを特徴とする請求項１に記載の木順序付け構成要素。
【請求項１１】
前記構成素構造の統計的モデルにおいて、前記モデルの素性の組は前記順序付けられていない木の構成素の１つまたは複数の統語素性を含むことを特徴とする請求項１に記載の木順序付け構成要素。
【請求項１２】
前記構成素構造の統計的モデルにおいて、前記モデルの素性の組は前記順序付けられていない木の構成素の１つまたは複数の意味素性を含むことを特徴とする請求項１に記載の木順序付け構成要素。
【請求項１３】
前記構成素構造の統計的モデルにおいて、前記モデルの素性の組は前記順序付けられていない木の所与の構成素の主辞とその構成素の娘の間の意味関係を含むことを特徴とする請求項１２に記載の木順序付け構成要素。
【請求項１４】
前記構成素構造の統計的モデルにおいて、前記モデルの素性の組は前記順序付けられていない木の特定の構成素の単語の長さを含むことを特徴とする請求項１に記載の木順序付け構成要素。
【請求項１５】
前記構成素構造の統計的モデルにおいて、前記モデルの素性の組は、前記順序付けられていない木の特定の構成素につき、前記順序付け検索中、１つの順序付け仮説に関連する、すでに順序付けられている前記構成素の前記娘として定義された構成素の組の素性を含むことを特徴とする請求項１に記載の木順序付け構成要素。
【請求項１６】
前記構成素構造の統計的モデルにおいて、対象の前記構成素の組の前記素性はその組のサイズを含むことを特徴とする請求項１５に記載の木順序付け構成要素。
【請求項１７】
前記構成素構造の統計的モデルにおいて、対象の前記構成素の組の前記素性はその組での各統語範疇の出現の総数を含むことを特徴とする請求項１５に記載の木順序付け構成要素。
【請求項１８】
前記構成素構造の統計的モデルにおいて、前記モデルの素性の組は、前記順序付けられていない木の特定の構成素につき、前記順序付け検索中、１つの順序付け仮説に関連する、順序付けすべく残っている前記構成素の前記娘として定義された構成素の組の素性を含むことを特徴とする請求項８に記載の木順序付け構成要素。
【請求項１９】
前記構成素構造の統計的モデルにおいて、対象の前記構成素の組の前記素性はその組のサイズを含むことを特徴とする請求項１８に記載の木順序付け構成要素。
【請求項２０】
前記構成素構造の統計的モデルにおいて、対象の前記構成素の組の前記素性はその組での各統語範疇の出現の総数を含むことを特徴とする請求項１８に記載の木順序付け構成要素。
【請求項２１】
前記構成素構造の統計的モデルにおいて、前記モデルの素性の組は、前記順序付けられていない木の特定の構成素につき、前記順序付け検索中、１つの順序付け仮説に関連する、順序付けすべく残っている前記構成素の前記娘として定義された構成素の組の素性を含むことを特徴とする請求項９に記載の木順序付け構成要素。
【請求項２２】
前記構成素構造の統計的モデルにおいて、対象の前記構成素の組の前記素性はその組のサイズを含むことを特徴とする請求項２１に記載の木順序付け構成要素。
【請求項２３】
前記構成素構造の統計的モデルにおいて、対象の前記構成素の組の前記素性はその組での各統語範疇の出現の総数を含むことを特徴とする請求項２１に記載の木順序付け構成要素。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は自然言語生成を扱う。より詳細には、本発明は自然言語生成システムにおける文章実現を扱う。
【背景技術】
【０００２】
自然言語生成システムは、１文の言語表現からテキストを生成する。こうしたシステムは一般に、テキストプランナまたは内容選択構成要素（ｃｏｎｔｅｎｔ  ｓｅｌｅｃｔｉｏｎ  ｃｏｍｐｏｎｅｎｔ）、文章プランナ構成要素（ｓｅｎｔｅｎｃｅ  ｐｌａｎｎｅｒ  ｃｏｍｐｏｎｅｎｔ）、および文章実現化構成要素（ｓｅｎｔｅｎｃｅ  ｒｅａｌｉｚａｔｉｏｎ  ｃｏｍｐｏｎｅｎｔ）を含む。
【０００３】
テキストプランナまたは内容選択構成要素は、実現されるテキストの基礎を形成する内容を入力として取得する。文章プランニング部分は、その内容をどのように文章にまとめるかを決定し、文章実現化構成要素は、実際の出力文章をどのように構築するかを決定する。
【０００４】
例えば、テキストプランナは「Ｌｉｔｔｌｅ  Ｒｅｄ  Ｒｉｄｉｎｇ  Ｈｏｏｄ」、「ｗａｌｋｉｎｇ」、「ｇｒａｎｄｍｏｔｈｅｒ’ｓ  ｈｏｕｓｅ」などの内容語を提供すると仮定する。文章プランナは、「Ｌｉｔｔｌｅ  Ｒｅｄ  Ｒｉｄｉｎｇ  Ｈｏｏｄ」が動作主であり、動作が「ｗａｌｋｉｎｇ」、行き先が「ｇｒａｎｄｍｏｔｈｅｒ’ｓ  ｈｏｕｓｅ」であると判断する。文章プランナは、この抽象的な言語表現を入力として文章実現化構成要素に提供する。文章実現化構成要素は、抽象的な言語表現から、その抽象的な言語表現に対応する実際の単語および句読点のシーケンスにマッピングする複雑なタスクを実行する。実際の単語および句読点のシーケンスは、実現された文（表層文字列（ｓｕｒｆａｃｅ  ｓｔｒｉｎｇ）とも呼ぶ）であり、これがシステムによって出力される。
【０００５】
以前の文章実現化システムは、異なる２つの範疇に分類される傾向があった。第１のタイプのシステムは、言語表現を連続的に処理して、単に表層文字列をそこから読み取ることができる表現を生成するハンドコードによるルールベースのシステムである。こうしたシステムでは、コンピュータ言語学者は一般に、テキストのプランニング、内容の単一の文への統合から、指示表現の適切な形の選択、形態素の語形変化の実行、出力のフォーマットに至る諸段階に対する戦略を明示的にコード化する。こうしたシステムは一般に、生成に極めて時間がかかる手書きコードを大量に含んでいた。さらに、こうしたハンドコードによるシステムでは、新しい分野への適応がかなり難しく、異なる言語への適用はよりいっそう難しい。
【０００６】
一般に従来使用されていた第２のタイプの文章実現化システムは、入力言語表現から直接候補文を生成しようと試みる。例えば、こうしたシステムは、ある分野に極めて特化したアプリケーション（フライト予約など）で使用されていた。それには限られた数のテンプレートがあり、内容語が単にテンプレートの様々なスロットに割り当てられるだけである。書込みテンプレートを使用して直接出力を生成する。
【０００７】
別のタイプの文章実現化システムは、文の抽象的な言語表現から生成できる可能性のあるすべての候補文を列挙する。こうした場合、候補文は、単語の組合せが実際のテキストに見られる組合せに最も近い文を選ぶ統計的技術を使用して評価される。しかし、所与の言語表現では、検査すべき候補文の数が極端に多い可能性がある。これによって計算時間が遅くなる。さらに、候補文の評価に使用する技術は、長距離の言語現象の対応に劣る。そのため、こうしたシステムは、長距離現象が一般的なジャンルおよび言語には不適当である。
【０００８】
この３番目の範疇のシステムの例には、Ｎｉｔｒｏｇｅｎシステムがある（例えば、非特許文献１および２参照）。
【０００９】
これらのシステムの第１のものでは、深い言語知識の代わりに、単語２−ｇｒａｍ法（ｗｏｒｄ ｂｉ−ｇｒａｍｓ）を使用して代替出力文間での決定を行う。知識工学による２組のルールが入力の仕様に対して作用して、出力される候補文を生成する。１組のルールは、指定が十分ではない意味から可能性のある統語形式への１対多のマッピングを行い、定性、数など、日本語／英語機械翻訳システムなどの実践上の生成状況において欠落し得る情報を肉付けする。対象領域への感度を含む第２の組のルールによって、第１のモジュールによって生成された表現が変換されて、単語ラティスとして表される候補文がさらに取得される。簡単なテーブル検索によって行われる形態素の語形変化によって、さらにラティスが拡張される。単語２−ｇｒａｍ法は、ラティスの最適な道（ｔｒａｖｅｒｓａｌ）を見つけるために使用され、それによって最上位の出力文が得られる。このシステムでは、候補文が非常に大量に生成され、採点され、ランク付けされる。例えば、Ｌａｎｇｋｉｌｄｅ，Ｉ．およびＫ．Ｋｎｉｇｈｔで示した例の１つでは、入力意味形式（ｓｅｍａｎｔｉｃ  ｆｏｒｍ）は、動作主、行き先、および受動者などの関係に５つの語彙節点を含む。この意味入力に起因する単語ラティスは、可能性のあるパスを１１００万以上含み、最上位の候補は、「Visitors who came in Japan admire Mount Fuji.」である。こうした別の例（意味入力表現が与えられていない場合）では、内容語を２つのみしか含んでいないように思われるが、これらは１５５，０００を超えるパスを含むラティスに変換され、最上位候補「Ｉ  ｃａｎ  ｎｏｔ  ｂｅｔｒａｙ  ｔｈｅｉｒ  ｔｒｕｓｔ．」が得られる。
【００１０】
このシステムで使用する単語２−ｇｒａｍ法の言語モデルは、連続していない単語間の依存関係を捕捉することができないという問題を来す。言語モデルの次数を３−ｇｒａｍ法またはより高いｎ−ｇｒａｍ法に増やすことは可能であるが、こうしたモデルでは依然として一般的な長距離の依存関係を捕捉できない。さらに、次数が増えるにつれてデータが乏しくなることが問題である。
【００１１】
また、以下で順序モデル（ｏｒｄｅｒ  ｍｏｄｅｌ）とも呼ぶ本開示の一部分に関連する従来の他の研究についても言及する。１つの関連分野は、「生成」解析モデルを含む。こうしたモデルは、解析（すなわち統語解析）プロセスで、確率を代替構文木に割り当てるために使用される。「生成」という名称は、モデルをランダムにサンプリングして、モデルにおける分布に応じて文の構造を生成できることを示す。構文解析プロセスと同様、こうしたモデルは、生成プロセス中に関連する素性が与えられると、確率を可能性のある構成素構造に割り当てることができる。
【００１２】
こうした解析モデルの例は、出版物に詳述されている（例えば、非特許文献３および４参照）。これらの論文に記載されている研究では、構成素の確率評価は、構成素の主辞などの文脈的情報を条件としている。ここに開示された研究をＣｈａｒｎｉａｋのモデルおよび以前の生成解析モデルと区別する本発明における順序モデルの一態様は、生成タスクから使用可能である意味関係および他の機能を解析中以外に使用することである。
【００１３】
別の基準点は、Ｄａｖｉｄ  Ｍａｇｅｒｍａｎの解析研究である。これは、決定木を使用して解析の対象の分布を評価する（例えば、非特許文献５参照）。この研究と本発明の間の主な相違は、解析における使用対生成における使用、および各モデルから使用可能な素性の違いである。さらにＭａｇｅｒｍａｎのモデルは生成的なものではなかった。
【００１４】
単語および構成素の順序は、文の流暢さおよび明瞭さの確立において極めて重要な役割を果たす。自然言語生成の文章実現段階における順序の設定は、一般に、過去において手動で生成された文法によって達成されていた（例えば、非特許文献６および７を参照）。  最近では、統計的手法の探求が行われている。上記のＮｉｔｒｏｇｅｎシステム、およびＦｅｒｇｕｓシステム（例えば、非特許文献８参照）は、単語ｎ−ｇｒａｍ法言語モデルを使用して、構成素の順序、単語の順序、語彙選択、および形態素の語形変化が異なる大量の単語シーケンス候補の組の中から選択を行っていた。ＮｉｔｒｏｇｅｎシステムおよびＦｅｒｇｕｓシステムでは、構成素の順序は単語ｎ−ｇｒａｍ法を介して表層文字列に間接的にモデル化されているにすぎない。すなわち、順序は、適切な形態素の変種の選択、および指定が十分ではない入力の解明から個別の現象として分離されない。またこれらは、実現中に使用可能な重要な言語特性を使用しない。
【００１５】
Ｈａｌｏｇｅｎシステム（例えば非特許文献９および１０参照）は、Ｎｉｔｒｏｇｅｎと同様、単語ｎ−ｇｒａｍ法のモデルを使用するが、検索を最初に各構成素の範囲内に制約することによって、最高得点の表層実現を（ラティスではなく）フォレストから効率的に抽出する。
【００１６】
Ａｍａｌｇａｍシステム（例えば、非特許文献１１参照）は、その単語を直接的にではなく、構成素およびその娘の順序を決定する明示的な順序付け段階を有する。Ａｍａｌｇａｍは、木構成素構造およびこうした構成素の素性を使用する。構成素内の順序を確立することによって、Ａｍａｌｇａｍは、可能性のある文章実現を単語レベルに制約する。
【００１７】
【特許文献１】米国特許第５，９６６，６８６号明細書
【非特許文献１】Langkilde, I. and K. Knight, 1998, "The Practical Value of N-Grams in Generation," Proceedings of the 9th International Workshop on Natural Languae Generation, Niagara-on-the-Lake, Canada, pages 248-255
【非特許文献２】Langkilde, I. and K. Knight, 1998, "Generation that Exploits Corpus-Based Statistical Knowledge," 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
【非特許文献３】Eugene Charniak, "A Maximum-Entropy-Inspired Parser", appearing in The Proceedings of NAACL-2000, Seattle, Washington, pp. 132-139
【非特許文献４】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
【非特許文献５】Magerman M. 1995, "Statistical Decision-Tree Models for Parsing," in Proc. of ACL, pp. 276-283
【非特許文献６】Aikawa T. et al., 2001, "Multilingual sentence generation," in Proceedings of the 8th European Workshop on Natural Language Generation, Toulouse, France pp. 57-63
【非特許文献７】Reiter E. et al., 2000, "Building natural language generation systems," Cambridge University Press
【非特許文献８】Bangalore S. and Rambow 0., 2000, "Exploiting a probabilistic hierarchical model for generation," in Proceedings of COLING 2000, Saarbrucken, Germany, pp. 42-48
【非特許文献９】Langkilde I., 2000, "Forest-Based Statistical Sentence generation," in Proceedings of NAACL 2000, pp. 170-177
【非特許文献１０】Langkilde-Geary I., 2002, "An Empirical Verification of Coverage and Correctness for a General-Purpose Sentence Generator," in Proceedings of the International Language Generation Conference 2002, New York, pp.17-24
【非特許文献１１】Corston-Oliver et al., 2002, "An overview of Amalgam: a machine-learned generation module," in Proceedings of the International Language Generation Conference 2002, New York, pp.33-40
【発明の開示】
【発明が解決しようとする課題】
【００１８】
しかし、Ａｍａｌｇａｍモデルにおける、自然言語生成における構成素の順序を確立するために使用される構成素構造の向上によって、結果の向上をもたらすことができる。これらの機能強化が本開示の焦点である。
【課題を解決するための手段】
【００１９】
本発明は、文章実現において正しい単語の順序が確立されるように、構文木構造において構成素を順序付けする構成要素である。生成物は、順序付けされた構文木、または代替の順序付けされた構文木の得点付き、ランク付きリストである。システムのこの木順序付け構成要素（または構成要素群）は、順序付けされていない構文木を受け取り、構成素構造の統計的モデル（決定木モデルを含む）に基づいてその構文木の代替の順序付けの確率を評価する。決定木モデルを使用して構成素構造のモデルにおける確率分布を評価することも、本発明の寄与するところである。この技術によって、自動素性選択を含む大きい素性空間が可能になる。
【００２０】
別の実施形態では、決定木学習以外の技術、例えば最大エントロピトレーニング（ｍａｘｉｍｕｍ  ｅｎｔｒｏｐｙ  ｔｒａｉｎｉｎｇ）、言語モデリングなどを使用して、構成素構造のモデル（本明細書では「順序モデル」とも呼ぶ）のパラメータを推定することができる。
【００２１】
一部の実施形態では、木順序付け構成要素は、条件付き構成素順序モデルを使用する。これは、順序付けられていない構文木が与えられると、複数の代替の順序付けされた構文木のうちのどれが順序付けされていない構文木が与えられたときに最高の条件付き確率を有するかを識別する。一部のより詳細な実施形態では、条件付き構成素順序モデルは、バイナリ条件付き構成素順序モデル（binary conditional constituent order model）である。
【００２２】
順序モデルが条件付き構成素順序モデルである一部の実施形態では、モデルはマルコフ法（Ｍａｒｋｏｖ  ｇｒａｍｍａｒ）である。一部のより詳細な実施形態は、マルコフ法は、左から右へのマルコフ法、または主辞駆動型のマルコフ法である。この定義は、上記の向きに限定されるものではなく、右から左、または左と右の交互など、他の向きを含むことができる。
【００２３】
一部の実施形態では、木順序付け構成要素は、所与の順序付けされていない構文木とともに複数の代替の順序付けられた構文木のそれぞれに得点を割り当てる結合構成素順序モデル（ｊｏｉｎｔ  ｃｏｎｓｔｉｔｕｅｎｔ  ｏｒｄｅｒ  ｍｏｄｅｌ）を使用する。こうした結合モデルはマルコフ法である。結合モデルの場合も、左から右へ、または主辞駆動型などの向きによるより具体的な実施形態がある。
【００２４】
一部の実施形態では、順序モデルは、構成素の娘の素性を条件とすることによって構成素の順序の確率を評価する。例えば、モデルは、主辞の娘と当該の娘の間の意味関係を条件とすることができる。別の実施形態では、文脈素性は、すでに順序付けされている構成素の娘の数、または順序付けすべく残っている構成素の娘の数である。さらに別の実施形態では、素性は、特定の構成素ラベルを有するすでに順序付けられた（または順序付けすべく残っている）構成素の娘の数である。
【００２５】
一部の実施形態では、順序モデルは、少なくとも１つの語彙素性を順序付けられた構文木の確率の条件とする。可能性のある語彙素性には、例えば他動性、節の補語との互換性などがある。
【００２６】
別の実施形態では、順序モデルは、意味関係や量化演算子の存在など少なくとも１つの意味素性を順序付けられた構文木の確率の条件とする。別の実施形態でさらに別の素性を使用することもできる。
【発明を実施するための最良の形態】
【００２７】
本発明は、文章実現化システムに関して説明する。本発明は、文章実現化システム全体の木順序付け構成要素、およびその構成要素に関連する方法を含む。
【００２８】
本発明は、決定木を使用して、構成素構造のモデルにおける確率分布を評価して自然言語生成における構成素の順序を確立する。この手法は、手動による素性の選択なしに、大きい素性空間を扱うことができる。本明細書ではこの技術をフランス語およびドイツ語における広範にわたる文章実現に適用するものとして説明し、この手法がこれらの言語における単語の順序の一般化をどのように扱うかを示す。この教示は、どんな言語にも適用可能である。
【００２９】
図１は、本発明の実施に適したコンピューティングシステム環境１００の例を示している。コンピューティングシステム環境１００は、適したコンピューティング環境の一例にすぎず、本発明の使用または機能の範囲に関する限定を示唆するものではない。また、コンピューティング環境１００を、動作環境１００の例に示した構成要素のいずれか１つ、またはその組合せに関連する依存性または必要条件を有しているものと解釈すべきではない。
【００３０】
本発明は、他の多くの汎用または専用コンピューティングシステム環境または構成で動作可能である。本発明との使用に適したよく知られているコンピューティングシステム、環境、および／または構成の例には、それだけには限定されないが、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップ装置、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラム可能家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記の任意のシステムまたは装置を含む分散コンピューティング環境などがある。
【００３１】
本発明は、コンピュータによって実行されるプログラムモジュールなどのコンピュータ実行可能命令の一般的な文脈で説明することができる。一般にプログラムモジュールは、特定のタスクを実行する、または特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、構成要素、データ構造などを含む。また、本発明は、タスクが通信ネットワークによってリンクされているリモート処理装置によって実行される分散コンピューティング環境で実施することもできる。分散コンピューティング環境では、プログラムモジュールを、メモリ記憶装置を含むローカルおよびリモートのコンピュータ記憶媒体に置くことができる。
【００３２】
図１を参照すると、本発明を実施するシステムの例は、コンピュータ１１０の形の汎用コンピューティング装置を含む。コンピュータ１１０の構成要素は、それだけには限定されないが、処理ユニット１２０、システムメモリ１３０、およびシステムメモリを含む様々なシステム構成要素を処理ユニット１２０に結合するシステムバス１２１を含む。システムバス１２１は、様々なバスアーキテクチャのうちの任意のものを使用するメモリバスまたはメモリコントローラ、周辺バス、およびローカルバスを含むいくつかのタイプのバス構造のうちどんなものでもよい。こうしたアーキテクチャには、それだけには限定されないが一例として、業界標準アーキテクチャ（ＩＳＡ）バス、マイクロチャネルアーキテクチャ（ＭＣＡ）バス、拡張ＩＳＡ（ＥＩＳＡ）バス、ビデオ電子装置規格化協会（ＶＥＳＡ）ローカルバス、およびメザニンバスとしても知られている周辺部品相互接続（ＰＣＩ）バスなどがある。
【００３３】
コンピュータ１１０は、一般に様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータ１１０からアクセスできる使用可能な任意の媒体とすることができ、揮発性および不揮発性媒体、リムーバブルおよび非リムーバブル媒体を含む。コンピュータ可読媒体は、それだけには限定されないが一例として、コンピュータ記憶媒体および通信媒体を含み得る。コンピュータ記憶媒体には、コンピュータ可読命令、データ構造、プログラムモジュール、他のデータなど、情報を記憶するための任意の方法または技術で実施される揮発性および不揮発性のリムーバブルおよび非リムーバブル媒体がある。コンピュータ記憶媒体には、それだけには限定されないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）または他の光ディスク記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置または他の磁気記憶装置、または所望の情報の格納に使用でき、コンピュータ１１０からアクセスできる他の任意の媒体などがある。通信媒体は一般に、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータを搬送波または他の移送機構などの変調されたデータ信号に組み込む。これには任意の情報配送媒体がある。「変調されたデータ信号」という用語は、信号内の情報を符号化するように設定または変更された１つまたは複数のその特徴を有する信号を意味する。通信媒体には、それだけには限定されないが一例として、有線ネットワーク、直接配線された接続などの有線媒体、および音響、ＲＦ、赤外線、その他の無線媒体などの無線媒体がある。また、上記のどんな組合せでもコンピュータ可読媒体の範囲内に含まれるものとする。
【００３４】
システムメモリ１３０は、読取り専用メモリ（ＲＯＭ）１３１やランダムアクセスメモリ（ＲＡＭ）１３２など、揮発性および／または不揮発性メモリの形態のコンピュータ記憶媒体を含む。基本入出力システム１３３（ＢＩＯＳ）は、例えば起動中など、コンピュータ１１０内の要素間での情報の転送を助ける基本ルーチンを含み、一般にＲＯＭ１３１に格納されている。ＲＡＭ１３２は一般に、処理ユニット１２０から直接アクセス可能な、かつ／または処理ユニット１２０が現在処理しているデータおよび／またはプログラムモジュールを含む。図１は、それだけには限定されないが一例として、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７を示している。
【００３５】
コンピュータ１１０は、他のリムーバブル／非リムーバブル、揮発性／不揮発性コンピュータ記憶媒体を含むこともできる。一例にすぎないが、図１は、非リムーバブル不揮発性磁気媒体から読み取り、あるいはそこに書き込むハードディスクドライブ１４１、リムーバブル不揮発性磁気ディスク１５２から読み取り、あるいはそこに書き込む磁気ディスクドライブ１５１、およびＣＤ−ＲＯＭや他の光媒体など、リムーバブル不揮発性光ディスク１５６から読み取り、あるいはそこに書き込む光ディスクドライブ１５５を示している。動作環境の例で使用できる他のリムーバブル／非リムーバブル、揮発性／不揮発性コンピュータ記憶媒体には、それだけには限定されないが、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、半導体ＲＡＭ、半導体ＲＯＭなどがある。ハードディスクドライブ１４１は一般に、インターフェース１４０などの非リムーバブルメモリインターフェースを介してシステムバス１２１に接続され、磁気ディスクドライブ１５１および光ディスクドライブ１５５は一般に、インターフェース１５０などのリムーバブルメモリインターフェースによってシステムバス１２１に接続される。
【００３６】
上述し、図１に示したドライブおよびその関連のコンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、およびコンピュータ１１０の他のデータの記憶を提供する。図１では例えば、ハードディスクドライブ１４１は、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７を記憶するものとして示されている。これらの構成要素は、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７と同じであっても、異なっていてもよいことに注意されたい。オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７は少なくとも異なるコピーであることを示すために、ここではそれらに異なる番号を付している。
【００３７】
ユーザは、キーボード１６２、マイクロフォン１６３、および一般にマウス、トラックボール、タッチパッドなどのポインティングデバイス１６１などの入力装置を介してコマンドおよび情報をコンピュータ１１０に入力することができる。他の入力装置（図示せず）には、ジョイスティック、ゲームパッド、衛星パラボラアンテナ、スキャナなどがある。これらおよび他の入力装置は、しばしばシステムバスに結合されているユーザ入力インターフェース１６０を介して処理ユニット１２０に接続されるが、パラレルポート、ゲームポート、ユニバーサルシリアルバス（ＵＳＢ）など他のインターフェースおよびバス構造で接続してもよい。モニタ１９１または他のタイプの表示装置もまた、ビデオインターフェース１９０などのインターフェースを介してシステムバス１２１に接続される。モニタに加えて、コンピュータは、出力周辺インターフェース１９５などを介して接続できるスピーカー１９７、プリンタ１９６などの他の周辺出力装置を含むこともできる。
【００３８】
コンピュータ１１０は、リモートコンピュータ１８０など１つまたは複数のリモートコンピュータへの論理接続を使用してネットワーク式環境で操作することができる。リモートコンピュータ１８０は、パーソナルコンピュータ、ハンドヘルド装置、サーバ、ルータ、ネットワークＰＣ、ピア装置、または他の一般のネットワークノードでよく、一般にコンピュータ１１０に関連して上述した多くまたはすべての要素を含む。図１に示した論理接続は、ローカルエリアネットワーク（ＬＡＮ）１７１およびワイドエリアネットワーク（ＷＡＮ）１７３を含むが、他のネットワークを含んでいてもよい。こうしたネットワーキング環境は、オフィス、全社規模のコンピュータネットワーク、イントラネット、およびインターネットではごく一般的である。
【００３９】
ＬＡＮネットワーキング環境で使用する場合、コンピュータ１１０は、ネットワークインターフェースまたはアダプタ１７０を介してＬＡＮ１７１に接続される。ＷＡＮネットワーキング環境で使用する場合、コンピュータ１１０は一般に、モデム１７２、またはインターネットなどＷＡＮ１７３にわたって通信を確立する他の手段を含む。モデム１７２は、内蔵のものでも外付けのものでもよく、ユーザ入力インターフェース１６０または他の適切な機構を介してシステムバス１２１に接続することができる。ネットワーク式環境では、コンピュータ１１０に関連して示したプログラムモジュール、またはその一部をリモートメモリ記憶装置に格納することができる。図１は、それだけには限定されないが一例として、リモートアプリケーションプログラム１８５をメモリコンピュータ１８０上に存在するものとして示している。図示したネットワーク接続は例であり、コンピュータ間の通信リンクを確立する他の手段を使用してもよいことは理解されよう。
【００４０】
図２は、本発明をそこで使用する文章実現化構成要素２００を示すブロック図（データフローも示す）である。文章実現化構成要素２００は、前処理構成要素２０２、具体化構成要素（ｆｌｅｓｈ−ｏｕｔ  ｃｏｍｐｏｎｅｎｔ）２０４、基本木変換構成要素２０６、全体的移動構成要素（ｇｌｏｂａｌ  ｍｏｖｅｍｅｎｔ  ｃｏｍｐｏｎｅｎｔ）２０８、構成素内順序付け構成要素２１０、表層クリーンアップ構成要素２１２、句読点挿入構成要素２１４、語形変化生成構成要素２１６、および木リーダ構成要素２１８を含む。次に、システム２００の全体的な動作について説明する。
【００４１】
システム２００は、入力文の抽象的な言語表現を入力として受け取る。本明細書で説明する実施形態では、入力は論理形式である。しかし、実質的に文の他のどんな統語表現または意味表現でも入力として受け取ることができることは理解されよう。論理形式構造は、特許文献１により詳しく記載されている。
【００４２】
前処理構成要素２０２は、入力をデグラフ（ｄｅｇｒａｐｈ）することによって抽象的な言語表現を処理する。例えば、入力は、論理形式の場合、木構造ではなくグラフ構造である。したがって、入力構造はデグラフされ、より木のような構造に変換される。また、前処理構成要素２０２は、例えば辞書検索操作によって語彙情報を入力構造に追加する。前処理構成要素２０２は、合成語の簡略化を行うこともできる。前処理構成要素２０２の出力は、追加情報がそこに追加されているデグラフされた構造２２０である。
【００４３】
具体化構成要素２０４は、データ構造２２０を受け取り、統語情報をそのデータ構造に追加する。具体化構成要素２０４は、限定詞、助動詞、意味的に空の前置詞、関係代名詞など機能語も挿入する。また、構成要素２０４は、格の素性および動詞位置の素性、主語または目的語の位置に名詞句をスペルアウトする確率を割り当てる。具体化構成要素２０４は、統語情報および他の情報がそこに追加されているデグラフされた構造である構造２２２を出力として提供する。
【００４４】
基本木変換構成要素２０６は、データ構造２２２を受け取り、そのデータ構造を基本構文木に変換する。構成要素２０６は、デグラフされたデータ構造２２２から統語木構造を読み取り、語幹から分離可能な接頭語を分ける。また、構成要素２０６は、同等の統語表現を挿入し、一部の統語の支配関係を逆転させる。構成要素２０６は、順序付けられていない基本構文木２２４を出力として提供する。
【００４５】
全体的移動構成要素２０８は、構造２２４を受け取り、全体的移動または全体的順序付けを行う。全体的移動には、疑問詞（Ｗｈ語）、関係代名詞、および言語理論で繰り上げとして知られているプロセスの移動がかかわる。また、構成要素２０８は、外置変形処理も行う。構成要素２０８は、その中の構成素は順序付けられていないが、各構成素が正しい親を有している構造２２６を出力として提供する。
【００４６】
構成素内順序付け構成要素２１０は、構造２２６を入力として受け取り、構文木のノードを完全に順序付けて、その出力で、完全に順序付けられた構文木２２８を提供する。
【００４７】
表層クリーンアップ構成要素２１２は、構造２２８を受け取り、限定詞、関係代名詞、および再帰代名詞の表層実現などの表層クリーンアップ操作を行う。また、構成要素２１２は、重複する同等のものを削除する。構成要素２１２は、不要なものが取り除かれた完全に順序付けられた構文木２３０を出力として提供する。
【００４８】
句読点構成要素２１４は、構造２３０を受け取り、句読点を構文木に挿入する。構成要素２１４は、数字２３２で示すように、句読点が挿入された状態で、不要なものが取り除かれた完全に順序付けられた構文木をその出力として提供する。
【００４９】
語形変化生成構成要素２１６は、構造２３２を受け取り、最終的な語形変化を生成し、最終の語形変化済みの木２３４を出力する。木読取り構成要素２１８は、単に木２３４を読み取り、最終の語形変化済みの木２３４の葉で単語を出すことによって表層文字列２３６（または実現された文２３６）をその出力として提供する。これが図２に示す経路の終点である。
【００５０】
上記のシステムを使用して、特定の言語的操作の適用のために文脈を決定するマシンで習得された様々なモジュールの使用によって、文の文字列が意味依存グラフから生成される。これらの操作によって、その意味表現が統語木および流暢な文字列に変換される。
【００５１】
すべての構文ノードが作成され、すべての階層関係が確立されると、順序付けられていない構文木の構成素間で順序が決定されて、順序付けられた構文木が生成される。
【００５２】
図３にこの概略を示しており、順序付けられていない構文木が順序付け構成要素２１０によって順序付けられて、その結果順序付けられた構文木（または順序付けられた木のリスト）が得られる。順序付けられていない構文木は、例えば図２の２２６で示したもの、順序付けられた構文木は、図２の２２８で示したものとすることができる。例えば、図５に示した順序付けられていない構文木の例を考察する。この順序付けられていない構文木は、図４に示すドイツ語の文の「In der folgenden Tabelle werden die Optionen sowie deren Funktionen aufgelistet.」の意味依存グラフから導出されている。この文の英語に相当するのは「The options and their functions are listed in the following table.」である。図５で、修飾語と主辞の間の意味関係を葉のところの括弧内に示している。この順序付けられていない統語木の順序付けられた構文木が、図６に示す木となる。
【００５３】
本発明の一実施形態では、構成素の順序を確立するために決定木を使用して構成素構造のモデルでの確率分布を評価することによって文章実現プロセスがさらに向上する。この手法は、手動による素性の選択なしに大きい素性空間を扱うことができる。他の実施形態では、他の技術（対数線形モデルの最大エントロピトレーニングなど）を使用して確率分布を評価する。
【００５４】
文章実現中の構成素の順序決定の問題の以前の研究のほとんどは、英語、つまり単語および構成素のかなり厳格な順序を有する言語に集中していた。本開示では、新たな問題を提起するフランス語およびドイツ語に焦点を当てている。本発明の目的は、類型論的に様々な言語にわたって統一された簡潔な方法ですべての順序付け現象を扱うモデルを提示することである。本開示では、可能なモデルの空間を記載し、その一部を詳細に考察する。モデルを詳しく説明する前に、フランス語およびドイツ語の単語および構成素の順序の決定における問題を概説する。
【００５５】
単語および構成素の順序
構成素の順序の任意のモデルについての問題は、流暢な文を生成するために、構成素のタイプおよび文脈に依存する好ましい順序付けの制約を学ぶことである。
【００５６】
ドイツ語の文章実現における問題は、厳格な動詞位置と他の構成素のかなり自由な位置付けの組合せである。平叙文主節（ｄｅｃｌａｒａｔｉｖｅ  ｍａｉｎ  ｃｌａｕｓｅ）と、従属節のほんの一部分では、定形動詞は、任意の種類の構成素の後ろの第２位置になければならない（「動詞第２位（ｖｅｒｂ−ｓｅｃｏｎｄ）」節）。ほとんどの従属節の定形動詞、およびすべての非定形動詞は、節の末尾に配置される（図６のような「動詞末尾（ｖｅｒｂ−ｆｉｎａｌ）」節）。動詞の配置の間違いによって、明瞭さに欠けるテキストになってしまう。
【００５７】
動詞の項および追加の修飾語は、この厳格な動詞の枠によって定義されるテンプレート内の様々な位置に配置することができる。こうした流動的な構成素の位置を決定する構造上の語用論的、意味論的制約は、完全には理解されない。
【００５８】
フランス語は、表面的な構文と文法関係の間の関係がやや直接的という点で英語と似ている。フランス語は、順序付けのタスクの複雑さにおいて英語とドイツ語の間に位置する。フランス語は、英語のように、構成素の順序付けはかなり厳格であるが、単語の順序については、フランス語は英語ほど厳格ではない。フランス語は、英語のようにＳＶＯ言語であるが、補語の順序付けはかなり自由であり、ＰＰ補語は、単一の単語より大きい目的補語より前にくることが多く、文の先頭に置くことができる。関係詞節では、非節語主語（ｎｏｎ−ｃｌｉｔｉｃ  ｓｕｂｊｅｃｔ）の倒置はよく起きる。形容詞の位置も英語ほど厳格ではなく、多くの形容詞は、それが修飾する名詞の前または後ろに置くことができ、他の形容詞は名詞の前または後ろにしか置くことができない。
【００５９】
一方、主語と動詞の間の構成素の順序付けは、非常に厳格である。接語代名詞および接語否定詞（ｃｌｉｔｉｃ  ｎｅｇａｔｏｒ）は、正書法的にはフランス語では自立語として表され、接語のタイプ（目的語、与格、または位置）、および一致素性（ａｇｒｅｅｍｅｎｔ  ｆｅａｔｕｒｅ）によって決定される厳格な順序で主語と動詞の間に置かれる。
【００６０】
構成素の順序のモデル
重要な順序現象を捕捉する構成素構造のモデルを説明するために、可能な結合モデルおよび条件付きモデルの空間について考察する。モデルにおける独立性の仮定、モデルで使用される素性の組、および自動素性選択はすべて、有用なモデルの生成に重要な役割を果たす。多くの組合せが可能であり、本発明は、有用と考えられる組合せを包含する。
【００６１】
我々のモデルは、入力素性の範囲において以前の統計的手法とは異なる。知識工学の手法と同様、ここで示したモデルは、語彙素性、品詞、構成素タイプ、構成素境界、長距離依存関係、および主辞とその修飾語の間の意味関係を組み込む。
【００６２】
説明したモデルは可能なモデルの全空間をカバーしてはいないが、その空間のうちの重要な点を選択している。
【００６３】
結合モデル
まず、順序付けられた構文木πおよび順序付けられていない構文木ρについて構成素構造の形式がＰ（π，ρ）の結合モデルを検討する。順序付けられた木πは、非終端の構成素Ｃを含み、そのそれぞれは順序付けられている娘のシーケンス（Ｄ１，．．．，Ｄｎ）の親であり、娘の１つが主辞構成素Ｈである（大文字のラテン文字は構成素を指し、対応する小文字のラテン文字はそのラベル、すなわち統語範疇を指す）。順序付けられた木πが与えられた場合、関数ｕｎｏｒｄｅｒｅｄ＿ｔｒｅｅ（π）の値は、Ｂ＝ｕｎｏｒｄｅｒｅｄ＿ｓｅｔ（Ｃ）＝｛Ｄ１，．．．，Ｄｎ｝となるようにπ中のＣごとに構成素Ｂを含むπに対応する順序付けられていない木ρである。この場合もまたＨ＝Ｄｉで、ｉは（１．．ｎ）である。ρの階層構造は、πと同一である。
【００６４】
次のように、結合モデルを使用して順序付けられた代替木に得点を付ける。順序付けられていない構文木ρが与えられた場合、同時確率（ｊｏｉｎｔ  ｐｒｏｂａｂｉｌｉｔｙ）を最大にする順序付けられた構文木
【００６５】
【数１】
2004295884.tif 000003
【００６６】
が必要である。つまり、
【００６７】
【数２】
2004295884.tif 000004
【００６８】
を求める。数式１が示すように、与えられた木ρの代替の順序である木πに検索を限定することができる。
【００６９】
考察中の可能なモデルタイプを制約するために、任意の構成素の順序が、その娘を含むその木の他の構成素内の順序とは無関係であると仮定する。したがって各構成素は、独立して順序付けを行うことができる。したがって
【００７０】
【数３】
2004295884.tif 000005
【００７１】
となる。特に
【００７２】
【数４】
2004295884.tif 000006
【００７３】
の場合は
【００７４】
【数５】
2004295884.tif 000007
【００７５】
となる。最後に、Ｂ∈ｃｏｎｓｔｉｔｓ（ρ）ごとに
【００７６】
【数６】
2004295884.tif 000008
【００７７】
となる。したがって、問題は、順序付けられていない木の各構成素の最適な順序を見つけることまで低減された。
【００７８】
実際に、Ｃ’の主辞はＢ’の主辞に一致しなければならないため、さらにＢの主辞に従って検索を制約することができる。
【００７９】
【数７】
2004295884.tif 000009
【００８０】
唯一可能な順序付けられた木は、上記の断定を満たす構成素で構築された木である。Ｐ（π）がこれを反映するようにＰ（Ｃ）を正規化する必要がある。Ｚが正規化定数であるとすると、
【００８１】
【数８】
2004295884.tif 000010
【００８２】
となる。次いで
【００８３】
【数９】
2004295884.tif 000011
【００８４】
となる。当然、Ｂが与えられている場合、Ｚは定数であり、したがってａｒｇｍａｘの値に影響を与えないため、実際にはそれを算出する必要がない。
【００８５】
次にある素性ｘ＝ｆ（ρ）を条件としたい場合、まずそれを予測する必要がある。
【００８６】
【数１０】
2004295884.tif 000012
【００８７】
ｘが本当にρの素性であり、ρと一致するどのＣを考慮するかに依存しない場合、Ｐ（ｘ）は定数であり、実際にはそれを算出する必要がない。したがって、結合モデルＰ（Ｃ）の場合でさえ、数式９のように、与えられた順序付けられていない木ρにおいて固定されている条件付けの素性を、最初に予測することなく、追加することができる。
【００８８】
【数１１】
2004295884.tif 000013
【００８９】
ここで説明した結合モデルは、この形式のものである。このため、分布Ｐ（Ｃ｜ｘ）を説明する場合、特に明記しない限り、実際に対象となる結合モデルの一部を説明している。上記で正当であることを示したように、Ｐ（ｘ）を算出する必要はなく、単にＰ（Ｃ｜ｘ）の代替形式を提示するだけである。
【００９０】
連鎖法則を使用して異なる多くの方法で分布Ｐ（Ｃ）（またはＰ（Ｃ｜ｘ））を因数分解することができる。開始点としてマルコフ法と呼ばれるモデルのクラスを採用する。「マルコフ法」とは、木の根から開始し、非終端の拡張に、確率を、全体的な生産物としてではなく、一度に娘１つずつ割り当てる構成素構造のモデルである（Charniak, E., 1997, "Statistical Techniques for Natural Language Parsing," In AI Magazine (1997)およびCharniak, E., 2000, "A Maximum-Entropy-Inspired Parser," in Proceedings of ACL 2000, pp.132-139を参照）。
【００９１】
左から右
引き続き結合モデルに焦点を置いて、まず、数式１１
【００９２】
【数１２】
2004295884.tif 000014
【００９３】
での分布に従って、図７に示すように、その娘Ｄ１，．．．，Ｄｎを１回に一度左から右に予測することによってＣを拡張する順序ｊの左から右へのマルコフ法について考察する。
【００９４】
主辞構成素Ｈとのその意味関係Ψｉなど、各娘Ｄｉの別の素性を条件とするために、連鎖法則に従って最初にそれも予測する。その結果は、数式１２
【００９５】
【数１３】
2004295884.tif 000015
【００９６】
となる。したがってモデルは、意味関係Ψｉを予測し、次いでその意味関係との関連でラベルｄｉを予測する。
【００９７】
上記のモデルの拡張として、すでに順序付けられているＣの娘の組αｉに対して以下の関数によって算出された素性を含む。  
・すでに順序付けられている娘の数（αｉのサイズ）
・可能な構成素ラベル｛ＮＰ、ＡＵＸＰ、ＶＰなど｝ごとに特定のラベルを有するαｉ内の娘の数（ドイツ語では２４、フランス語では２３）
このように、マルコフ次数（Ｍａｒｋｏｖ  ｏｒｄｅｒ）ｊのモデルは、ｊより大きい真の次数を有する可能性がある。この点で、「マルコフ法」という用語の使用は、その句の従来の解釈とは異なる。素性の組を簡略的にｆ（αｉ）と示す。
【００９８】
【数１４】
2004295884.tif 000016
【００９９】
主辞駆動型
左から右への拡張の代替として、順序付けられた木πの各構成要素Ｃを、図８に示すように、主辞の娘Ｈ、順序付けられた（Ｈの）前置修飾語（Ｌ１，．．．，Ｌｍ）、および順序付けられた後置修飾語（Ｒ１，．．．，Ｒｎ）と特徴付けることができる。これを「主辞駆動型マルコフ法」と呼ぶ。条件付けの文脈が主辞で止まる場合、この拡張は、一般性を失わずに、まず前置修飾語で開始し、後置修飾語が続く。分布には２部分あり、第１部分は前置修飾語の拡張、および第２部分は後置修飾語の拡張である。
【０１００】
【数１５】
2004295884.tif 000017
【０１０１】
左から右への場合と同様、主辞構成素Ｈとの娘の意味関係を条件とする。モデルがより豊富な場合、すでに順序付けられている娘の全組αｉを条件とする（したがって主辞にわたる素性を条件とする）。
【０１０２】
次に、追加の素性、つまりＣの主辞Ｈ、Ｃに対応する順序付けられていない構成素Ｂ、その親ＰＢ、およびその祖父（母）ＧＢを使用するより複雑なモデルについて考察する。数式１３の状況として、Ｂ、ＰＢ、およびＧＢはそれぞれ、こうしたそれぞれの構成素に対する１組の言語特性を表す。
Ｐ（Ｃ｜ρ）＝Ｐ（Ｃ｜ｈ，Ｂ，ＰＢ，ＧＢ）                  数式１５
【０１０３】
したがって、左から右への向きの複雑なモデルは、次のように構築される。
【０１０４】
【数１６】
2004295884.tif 000018
【０１０５】
ここで、Ｐ（Ｃ｜ｈ，Ｂ，ＰＢ，ＧＢ）のすべてのモデルは、Ｂの任意の素性を照会することができる。すでに順序付けられているＣの娘の組αｉに対する関数である素性も含める。
【０１０６】
最後に、結合モデルの領域を離れ、順序付けるべきＣの娘の組βｉに対する関数である素性を含めることによる真の条件付きモデルを紹介する。例えば、
・順序付けすべく残っている娘の数（βｉのサイズ）
・特定のラベルを有するβｉ内の娘の数
これらの素性の組を簡略的にｆ（αｉ）およびｆ（βｉ）と示す。
【０１０７】
【数１７】
2004295884.tif 000019
【０１０８】
簡単なモデルと同様、再度同じ形式の複雑な主辞駆動型マルコフ法について考察する。
【０１０９】
バイナリ条件付きモデル
バイナリ条件付きモデルと呼ぶ第３のタイプのモデルを紹介する。これは、「次にソート」と呼ばれる｛ｙｅｓ，ｎｏ｝の値を有するバイナリ変数σの分布を評価する。これは、図９に示すように、まだ順序付けられていないβｉ（上で定義したように、親Ｃのまだ順序付けられていない娘の組）のメンバＤを次に「ソート」すべきイベントを表す。条件付けの素性は、条件付けの文脈に現れるＤおよびΨ（Ｄと主辞Ｈとの意味関係）は決して予測されないことを除いて、上記の左から右への条件付きモデルで使用したものとほぼ同じである。その簡単な形式で、モデルは、次の分布を評価する。
【０１１０】
【数１８】
2004295884.tif 000020
【０１１１】
検索のセクションで左から右への「ソート」検索においてこのモデルを直接適用する方法について後述する。
【０１１２】
評価
異なるいくつかの技術を使用してモデルの分布を評価することができる。本開示では、補間言語モデリング技術（interpolated langage modeling technique）（以下ＬＭと略す）および確率的決定木（probabilistic decision tree）（ＤＴ）を使用する。本開示では詳しく説明しないが、素性選択および分布評価への他の手法も使用できることを当業者であれば理解されよう。
【０１１３】
この実験で使用する両方のタイプのモデルについて説明する。本開示のすべてのモデルは、上で定義した追加の素性関数ｆ（αｉ）およびｆ（βｉ）を除いてマルコフ次数２である。
【０１１４】
言語モデリング
ＬＭモデルは、平滑化技術として補間Ｋｎｅｓｅｒ−Ｎｅｙを使用する。Kneser R. and Ney H., 1995, "Improved backing-off for m-gram language modeling," in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, Vol. 1, pp. 181-184およびGoodman J. T., 2001, "A Bit of Progress in Language Modeling: Extended Version," Microsoft technical report MSRTR-2001-72を参照されたい。
【０１１５】
この手法（および使用するツール）の１つの欠点は、手動による素性の選択、および手動で指定した逆方向の順序を必要とすることであり、その実際の効果は、比較的少数の素性を有効に使用できることである。この実験ではこのタイプの単一の結合主辞駆動型モデルを使用する。
【０１１６】
決定木
ＷｉｎＭｉｎｅツールキット（Chickering D. M., 2002, "The WinMine Toolkit," Microsoft Technical Report 2002-103参照）を使用して決定木を構築する。ＷｉｎＭｉｎｅで習得した決定木は、トレーニングにおいて使用可能なすべての素性が与えられた場合、各葉は対象の素性の値にわたる条件付き確率分布になるため、単なる分類器ではなく、木自体が同じ条件付き分布の評価であることを明らかにしておくだけの価値はある。決定木、および特に確率的ＤＴを使用する主な利点は、大きい素性のプールからの素性の自動選択である。このタイプの６つのモデルを、豊富な素性の組とともに使用する。２つのモデルは結合であり、２つはすでに順序付けられている娘の組に対する素性（ｆ（αｉ）で示す）を有する結合であり、２つは条件付きである。各タイプの一方は主辞駆動型であり、もう一方は左から右である。さらに、正規化ありおよびなしによる左から右へのバイナリ条件付きＤＴモデルを使用する。
【０１１７】
素性および素性の選択
異なる決定木モデルごとに広範にわたる言語特性が抽出される。ドイツ語の場合、選択された素性の数は、結合モデルでは（８のうち）６から８、ｆ（αｉ）を有する結合モデルでは（３３のうち）７から１６、条件付きモデルでは（４８７（主辞駆動型）、４９４（左から右）のうち）２１から１０７に及び、バイナリ条件付きモデルでは（６５１のうち）２８０に達する。フランス語の場合、選択された素性の数は、結合モデルでは（８のうち）６から８、ｆ（αｉ）を有する結合モデルでは（３２のうち）７から１１、条件付きモデルでは（４０４（主辞駆動型）、４２９（左から右）のうち）２２から９１に及び、バイナリ条件付きモデルでは（５５０のうち）２１８に達し、それらはすべて、ドイツ語モデルにかなり類似している。複雑モデルおよびバイナリ条件付きモデルは、使用可能な素性の全範囲から以下を得ることができる。  
・他動性や節の補語との互換性などの語彙の下位範疇化素性
・見出し語（または語幹）
・意味関係や量化演算子の存在などの意味素性
・単語内の構成素の長さ
・ラベルや統語修飾語（ｓｙｎｔａｃｔｉｃ  ｍｏｄｉｆｉｅｒ）の存在などの統語情報
【０１１８】
言語学上の見地から、ドイツ語およびフランス語の文法の特色の詳細な言語的知識をもってしても、この特徴の選択を手動で行うことは不可能であったことは特に興味深い。有生性、定性など、２、３の顕著な基本的意味素性は、明らかに順序付けに関連している。しかし現在、これらの素性の相互作用の理解が乏しすぎて、順序付けにおけるそれらの役割を断定的に指定することができない。
【０１１９】
検索−網羅的検索（Ｅｘｈａｕｓｔｉｖｅ  ｓｅａｒｃｈ）
順序付けられていない木ρおよび構成素構造Ｏのモデルが与えられた場合、文脈がモデルの複雑さに応じて変動する、ＰＯ（π｜ρ）を最大にする最適に順序付けられた木πを検索する。（バイナリ条件付きモデルを除く）モデルのそれぞれは、π中の他の構成素内部の順序付けとは関係なく、πの中の任意の構成素Ｃの順序付けの確率を評価する。完全な検索は、モデルに応じて、Ｃの娘における左から右、または主辞駆動型のダイナミックプログラミングアルゴリズムである。検索は、１つの非統計的制約を維持し、これは、調整された構成素が「順序付けられていない」木に現れる通りの順序を守る。
【０１２０】
検索−バイナリ条件付きモデルの盲目的検索（ｇｒｅｅｄｙ  ｓｅａｒｃｈ）
バイナリ条件付きモデルは、左から右への「ソート」モード時に適用される。図９のプロセスの図を参照されたい。βｉ内の順序付けられていない娘Ｄｊごとに、モデルでσｊ＝ｙｅｓの確率、つまりそのＤｊがすでに順序付けられている姉（妹）の構成素αｉの右に配置されている確率を調べる。最も高い確率を有するβｉ内の娘は、βｉから取り除かれ、αｉを右に延長する。順序付けられていない構成素のリスト内のすべての構成素がこの盲目的なやり方で順序付けられるまで、順序付けられていない残りの構成素について検索が続けられる。
【０１２１】
網羅的ＤＰ検索にこのモデルを適用するために、検索のすべての段階においてモデルを正規化し、それによってモデルがβｉ内の残りの娘にわたる確率分布になるようにする。数式１８を簡略的にＰ（σ｜ｄ，Ψ，Γｉ）とする。この場合Γｉは、検索段階ｉでの所与の検索仮説での文脈素性を表す。したがって、段階ｉで正規化された分布は、数式１９によって得られる。自由変数ｊは、βｉ内の順序付けられていない娘のインデックスを表し、ｋも同様である。
【０１２２】
【数１９】
2004295884.tif 000021
【０１２３】
実験−トレーニング
ここでは、上記の様々なモデルを比較し、対比する１組の実験を説明する。トレーニングには、フランス語およびドイツ語の２０，０００文のトレーニングセットを使用した。データは、コンピュータ分野の技術マニュアルからのものである。トレーニングセット内のある文が与えられた場合、その文は、最初に、ＮＬＰＷｉｎシステム（例えば、特許文献１参照）を使用して構文木、および意味依存グラフとして分析される。意味依存グラフおよび構文木を調べることによって、これらのトレーニング木は適切に順序付けられるという１つの例外を除いて、木は、生成実行時にＡｍａｌｇａｍ順序付け段階によって見られる木のすべての特性を含んで生成される。この木は、主辞およびその修飾語の間の意味関係を含めて、対象のすべての素性を含む。使用した順序モデルは、これらの木の構成素を基に訓練される。
【０１２４】
実験−評価
モデルを評価するために、Ａｍａｌｇａｍ文章実現プロセスの残りとは関係なく、順序付けプロセスが独立して評価される。１，０００文のテストセットが使用される。これらもまた各言語の技術マニュアルからのものである。順序を切り離すために、テスト文が与えられると、トレーニングの場合と同様、文が処理されて、順序付けられた木π（評価のための基準）が生成され、それから順序付けられていない木ρ文が生成される。ρが与えられると、当該のモデルを使用して最適に順序付けられた木の仮説
【０１２５】
【数２０】
2004295884.tif 000022
【０１２６】
の検索が行われる。次いでπと
【０１２７】
【数２１】
2004295884.tif 000023
【０１２８】
の比較が行われる。構成素の順序付けのみが行われているため、対応するそれぞれの構成素の順序を比較することによってπおよび
【０１２９】
【数２２】
2004295884.tif 000024
【０１３０】
を比較することができる。この場合の２つの構成要素の比較に使用される測定値は、編集距離であり、移動に関与するすべての娘の割合として測定される。仮説木
【０１３１】
【数２３】
2004295884.tif 000025
【０１３２】
の総得点は、構成素ごとの加重平均編集距離である。
【０１３３】
また、構成素ごとの平均編集距離測定値（average per-consistuent edit distance metrics）は、エラー分析、および対象の言語文脈に対する所与のモデルの影響を決定するために、非終端タイプごとに算出される。
【０１３４】
図１０の表に、所与の言語のテストセットにわたる平均点をモデルごとに示している。ドイツ語およびフランス語で、左から右へのバイナリ条件付きＤＴモデル（盲目的検索に適用）は、他のすべてのモデルより優れている。バイナリ条件付きモデルを正規化し、それを網羅的検索に適用することは役に立たない。事実、精度のわずかな低下は、ラベルバイアス問題によるものであり得る。Lafferty et al., 2001, "Conditional Random Fields: Probabilistic models for segmenting and labeling sequence data", in Proc. Of 18th ICML, pp. 282-289を参照されたい。
【０１３５】
補間言語モデルは、フランス語およびドイツ語の両方で、２番目によく働く。このモデルは、最も簡単な構造を有するが、最も高度な平滑化を使用する。
【０１３６】
ドイツ語およびフランス語の両方で、左から右への結合モデル（ｆ（αｉ）素性なし）が主辞駆動型の結合モデルより優れていることは興味深い。左から右および主辞駆動型の場合にｆ（αｉ）素性を含めることによって、フランス語の場合は状況が逆転するが、ドイツ語の場合は逆転しない。
【０１３７】
ドイツ語の場合も、左から右への条件付きモデルは、主辞駆動型の条件付きモデルより優れている。フランス語の場合はわずかの差である。条件付きモデル対結合モデルの問題については、簡単なモデル（ｆ（αｉ）素性あり）は、もう一方の複雑なモデルより常に優れている。これは、十分なトレーニングデータの欠如によるものである。現時点では、複雑なモデルのトレーニング時間が制限要因となっている。
【０１３８】
ドイツ語のモデルのパフォーマンスとフランス語のモデルのパフォーマンスの間には明らかな相違がある。ドイツ語の最適なモデルは、フランス語の最適なモデルの１／２である。
【０１３９】
個々の統語範疇に関して、バイナリ条件付きモデルの強さは、主に動詞構成素内の構成素順序の適切な設定にある。ドイツ語の場合、バイナリ条件付きモデルは、動詞構成素では９．８９２％を得点する。他の任意のモデルによる最高得点は、１３．６１％である（左から右への結合、ｆ（αｉ）あり）。フランス語の場合、バイナリ条件付きモデルは、動詞構成要素では３．６０２％を得点する。他の任意のモデルによる最高得点は、５．８９１％である（ＬＭ主辞駆動型結合）。
【０１４０】
ドイツ語での動詞構成素の順序の設定における特定の問題は、動詞の位置付け、および動詞の文脈での修飾語のより緩やかな順序の問題に起因する可能性が最も高い。動詞の順序の問題に対処するために、順序付けられていない木に追加の素性を含めて実験を行った。動詞の位置には、関連するすべての構成素に注釈を付けた。図１１の表に示すように、条件付きモデルにこの素性を追加することによって、モデルの精度においてかなりの飛躍が認められた。
【０１４１】
繰り返すが、最適なモデルはバイナリ条件付きモデルである。上述したように、正規化は役立たない。動詞位置の素性の使用可能性によってもたらされた向上によって、全体的な順序付け誤り率が相対的に１３％低下する。動詞構成素については、得点は、動詞位置の素性によって８．４６８％まで向上する。次に最適な動詞位置を用いたモデルは、１２．５９％の左から右への条件付モデルである。
【０１４２】
本発明は、特定の実施形態に関連して説明してきたが、本発明の意図および範囲から逸脱することなく形態および詳細に変更を加えることができることが当分野の技術者には理解できよう。
【図面の簡単な説明】
【０１４３】
【図１】本発明を使用できる環境の一例を示すブロック図である。
【図２】本発明を表し、データフローを示す、順序付けするためのボックスを含む文章実現化システムの一実施形態を示すブロック図である。
【図３】特定の順序付けられていない構文木が与えられた場合、順序付けられた構文木を識別するために本発明で使用されるタイプの順序付け構成要素を示すブロック図である。
【図４】本発明への入力として使用する、論理形式として組み込まれる文の意味表現の例を示す図である。
【図５】図４の論理形式に対応し、順序付け構成要素の入力の一種の例である順序付けられていない構文木の一例を示す図である。
【図６】図５の順序付けられていない木に対応する、木順序付け構成要素からの出力の一例である順序付けられた構文木の一例を示す図である。
【図７】構成素の左から右への拡張を示すブロック図である。
【図８】構成素の主辞駆動型の拡張を示すブロック図である。
【図９】バイナリ条件付きモデルを使用した構成素の左から右への拡張を示すブロック図である。
【図１０】ドイツ語およびフランス語の様々な順序モデルを比較した結果を示す表である。
【図１１】動詞の位置特性の有無による順序モデルのサブセットを比較した結果を示す表である。
【符号の説明】
【０１４４】
１００  コンピューティングシステム環境
１１０  コンピュータ
１２０  処理ユニット
１２１  システムバス
１３０  システムメモリ
１３１  読取り専用メモリ（ＲＯＭ）
１３２  ランダムアクセスメモリ（ＲＡＭ）
１３３  基本入出力システム（ＢＩＯＳ）
１３４  オペレーティングシステム
１３５  アプリケーションプログラム
１３６  他のプログラムモジュール
１３７  プログラムデータ
１４０  インターフェース
１４１  ハードディスクドライブ
１４４  オペレーティングシステム
１４５  アプリケーションプログラム
１４６  他のプログラムモジュール
１４７  プログラムデータ
１５０  インターフェース
１５１  磁気ディスクドライブ
１５２  リムーバブル不揮発性磁気ディスク
１５５  光ディスクドライブ
１５６  リムーバブル不揮発性光ディスク
１６０  ユーザ入力インターフェース
１６１  ポインティングデバイス
１６２  キーボード
１６３  マイクロフォン
１７０  ネットワークインターフェースまたはアダプタ
１７１  ローカルエリアネットワーク（ＬＡＮ）
１７２  モデム
１７３  ワイドエリアネットワーク（ＷＡＮ）
１８０  リモートコンピュータ
１８５  リモートアプリケーションプログラム
１９０  ビデオインターフェース
１９１  モニタ
１９５  出力周辺インターフェース
１９６  プリンタ
１９７  スピーカー
２００  文章実現化構成要素
２０２  前処理構成要素
２０４  具体化構成要素
２０６  基本木変換構成要素
２０８  全体的移動構成要素
２１０  構成素内順序付け構成要素
２１２  表層クリーンアップ構成要素
２１４  句読点挿入構成要素
２１６  語形変化生成構成要素
２１８  木リーダ構成要素
２２０  デグラフされた構造
２２２  データ構造
２２４  順序付けられていない基本構文木
２２６  構造
２２８  完全に順序付けられた構文木
２３０  不要なものが取り除かれた完全に順序付けされた構文木
２３４  最終の語形変化済みの木
２３６  表層文字列
【図１】
2004295884.tif 000026
【図２】
2004295884.tif 000027
【図３】
2004295884.tif 000028
【図４】
2004295884.tif 000029
【図５】
2004295884.tif 000030
【図６】
2004295884.tif 000031
【図７】
2004295884.tif 000032
【図８】
2004295884.tif 000033
【図９】
2004295884.tif 000034
【図１０】
2004295884.tif 000035
【図１１】
2004295884.tif 000036
【外国語明細書】
2004295884000001.pdf