JP2004334193A - 音声認識および自然言語理解のための複合統計／ルール・ベース文法モデルを有するシステム - Google Patents

Abstract

【課題】 ２パスのシステムに関連する効率の悪さを低減し、また、言語モデルにおける以前の知識を含んで、言語モデル・トレーニング・データの不足を補うこと。
【解決手段】 複合統計モデルおよびルール・ベース文法言語モデルを使用し、音声認識タスクおよび自然言語理解タスクの両方を実行をする。
【選択図】 図２Ａ

Description

本発明は音声認識（speech recognition）および自然言語理解（natural language understanding）に関する。より詳細には、本発明は、統計モデル部およびルール・ベース文法部から形成される複合モデルを、同時の音声認識および自然言語理解の実行において言語モデルとして、使用することに関する。

発話された人間の音声を認識および理解することは、将来のコンピューティング環境に不可欠であると考えられている。現在まで、発話音声を認識および理解するタスクは、２つの異なるシステムによって対処されてきた。第１のシステムは音声認識システムであり、第２のシステムは自然言語理解システムである。

従来の音声認識システムは、発話言語入力を示す音声信号を受信する。音響特徴が音声信号内で識別され、音声信号が、音響モデルおよび言語モデルを使用して復号化されて、入力音声信号によって表現された語（words）を指し示す出力が提供される。

また、話し言葉の使用可能なアプリケーションおよびサービス（speech enabled applications and services）の開発を容易にするために、意味ベースの頑強な理解システム（semantic-based robust understanding systems）が現在開発下にある。このようなシステムは、会話型であり、リサーチ・システムにおいて幅広く使用されている。しかし、これらは特に、会話システムの実装において従来の開発者による使用に対しては実用的ではない。大体において、このような実装は、領域特有の文法（domain-specific grammars）の手動の開発に依拠している。このタスクには時間がかかり、エラーを起こしやすく、領域内で著しい量の専門知識（技術）が必要となる。

話し言葉の使用可能なアプリケーションおよびサービスの開発を進めるために、用例ベース文法オーサリング・ツール（example- based grammar authoring tool）が導入されている。このツールはＳＧＳｔｕｄｉｏとして知られている（たとえば、非特許文献１および非特許文献２参照）。このツールは、以前の情報の多数の異なるソースを利用することによって、文法開発を大幅に容易にする。これは、言語知識をほとんど有していない通常の開発者が、発話言語理解のための意味文法を構築することを可能にする。このシステムは、少量のデータによる、比較的高品質な意味文法の半自動生成を容易にする。さらに、このツールは、文法開発に関係する労力を著しく削減するだけでなく、異なる領域に渡る理解の精度も向上させる。

しかし、ＮＬＵシステムにおける純粋にルール・ベースの文法は、なお頑強性に欠け、脆弱性を示す可能性がある。

加えて、全てではないが大部分の以前の手法は、理解を、別の問題として、音声認識とは無関係に扱う。２パスの手法がしばしば採用され、これにおいて、第１のパスとして、領域特有のｎ−グラム言語モデルが構築されて音声認識のために使用され、その語第２のパスとして、様々な学習アルゴリズムにより得られた理解モデルが音声認識装置からの出力を「理解」するために適用される。

Y. Wang, A. Acero, "GRAMMAR LEARNING FOR SPOKEN LANGUAGE UNDERSTANDING", IEEE Workshop on Automatic Speech Recognition and Understanding, Madonna D. Campiglio Italy, 2001 Y. Wang, A. Acero, "EVALUATION OF SPOKEN LANGUAGE GRAMMAR LEARNING IN ATIS DOMAIN", Proceedings of ICASSP, Orlando, FL 2002 Riccardi, G., et al., "STOCHASTIC AUTOMATA FOR LANGUAGE MODELING", Computer Speech and Language, 10: pages 265-293 (1996)

理解および音声認識を２つの別々の独立したタスクとして扱った以前のシステムは、いくつかの欠点を示すと考えられる。第１に、音声認識装置のためのｎ−グラム言語モデルを構築する際に最適化される目的関数は、テスト・データの混乱の低減であり、これは、音声認識語エラー率の低減に関係付けられる。これは必ずしも、全体の理解エラー率における低減につながるとは限らない。第２に、大量のトレーニング・データは、多数のスピーチ・アプリケーションの開発のためにめったに使用可能ではない。少量のデータでトレーニングされたｎ−グラムはしばしば、不十分な認識精度を生じる。

したがって、本発明は、複合統計モデルおよびルール・ベース文法言語モデルを使用し、音声認識タスクおよび自然言語理解タスクの両方を実行する。

本発明の一実施形態は、また、各未知語についてのループをあらゆるｎ−グラムに含むのではなく、バック−オフ状態上の共有分布を参照することによって、各ｎ−グラムについてのすべての未知語を処理することによって、コンパクトな方法で複合モデルに対応する状態マシンを構築することも含む。

本発明は、音声認識および自然言語理解システムを扱う。具体的には、本発明は、音声認識および自然言語理解を実行するために使用される複合ルール・ベース文法および統計モデルを扱う。しかし、本発明をより詳細に論じるより先に、本発明を使用することができる１つの例示的環境を論じる。

図１は、本発明を実装することができる、適切なコンピューティング・システム環境１００の一実施例を例示する。コンピューティング・システム環境１００は適切なコンピューティング環境の一実施例でしかなく、本発明の使用または機能性の範囲についてのいかなる限定をも示唆するように意図されない。コンピューティング環境１００は、例示的オペレーティング環境１００において例示したコンポーネントのいずれか１つまたは組合せに関係するいかなる依存性も要件も有するものとして解釈されるべきではない。

本発明は、多数の他の汎用または専用コンピューティング・システム環境または構成と共に動作可能である。本発明と共に使用するために適切である可能性のある周知のコンピューティング・システム、環境および／または構成の例には、それだけに限定されないが、パーソナル・コンピュータ、サーバ・コンピュータ、ハンドヘルドまたはラップトップ・デバイス、マルチ・プロセッサ・システム、マイクロ・プロセッサ・ベースのシステム、セットトップボックス、プログラマブルなコンシューマ・エレクトロニクス、ネットワークＰＣ、ミニ・コンピュータ、メインフレーム・コンピュータ、上記のシステムまたはデバイスのいずれかを含む分散コンピューティング環境などが含まれる。

本発明を一般に、プログラム・モジュールなど、コンピュータによって実行されるコンピュータ実行可能命令に関連して説明することができる。一般に、プログラム・モジュールには、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれ、これらは特定のタスクを実行するか、あるいは特定の抽象データ型を実施する。本発明をまた分散コンピューティング環境において実施することもでき、ここでは、通信ネットワークを通じてリンクされるリモート処理デバイスによってタスクが実行される。分散コンピューティング環境では、プログラム・モジュールは、メモリ・ストレージ・デバイスを含む、ローカルおよびリモートのコンピュータ・ストレージ・メディアに位置することができる。

図１を参照すると、本発明を実装するための例示的システムは、コンピュータ１１０の形態における汎用コンピューティング・デバイスを含む。コンピュータ１１０のコンポーネントは、それだけに限定されないが、処理装置１２０、システム・メモリ１３０、および、システム・メモリを含む様々なシステム・コンポーネントを処理装置１２０に結合するシステム・バス１２１を含むことができる。システム・バス１２１は、いくつかのタイプのバス構造のいずれかにすることができ、これには、様々なバス・アーキテクチャのいずれかを使用する、メモリ・バスまたはメモリ・コントローラ、周辺バスおよびローカル・バスが含まれる。例として、限定ではなく、このようなアーキテクチャには、業界標準アーキテクチャ（ＩＳＡ）バス、マイクロ・チャネル・アーキテクチャ（ＭＣＡ）バス、拡張ＩＳＡ（ＥＩＳＡ）バス、Ｖｉｄｅｏ Ｅｌｅｃｔｒｏｎｉｃｓ Ｓｔａｎｄａｒｄｓ Ａｓｓｏｃｉａｔｉｏｎ（ＶＥＳＡ）ローカル・バス、およびメザニン・バスとしても知られるＰｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ（ＰＣＩ）バスが含まれる。

コンピュータ１１０は通常、様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータ１１０によってアクセスすることができるいかなる使用可能なメディアにすることもでき、これには、揮発性および不揮発性のメディア、リムーバブルおよび非リムーバブルのメディアが含まれる。例として、限定ではなく、コンピュータ可読媒体は、コンピュータ・ストレージ・メディアおよび通信メディアを含むことができる。コンピュータ・ストレージ・メディアは、揮発性および不揮発性、リムーバブルおよび非リムーバブルのメディアを含み、これらはコンピュータ可読命令、データ構造、プログラム・モジュールまたは他のデータなど、情報の格納のためのいずれかの方法または技術において実施される。コンピュータ・ストレージ・メディアには、それだけに限定されないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリもしくは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）もしくは他の光ディスク・ストレージ、磁気カセット、磁気テープ、磁気ディスク・ストレージもしくは他の磁気ストレージ・デバイス、または、所望の情報を格納するために使用することができ、コンピュータ１１０によってアクセスすることができる他のいかなるメディアもが含まれる。通信メディアは、通常、コンピュータ可読命令、データ構造、プログラム・モジュールまたは他のデータを、搬送波ＷＡＶまたは他の移送メカニズムなどの変調データ信号において具現化し、任意の情報配信メディアをも含む。「変調データ信号」という用語は、信号における情報を符号化するような方法でその特性の１つまたは複数が設定または変更されている信号を意味する。例として、限定ではなく、通信メディアには、有線ネットワークまたは直接有線接続などの有線メディア、ならびに、音響、ＲＦ、赤外線および他の無線メディアなどの無線メディアが含まれる。上記のいずれの組合せも、コンピュータ可読媒体の範囲内に含まれるべきである。

システム・メモリ１３０は、揮発性および／または不揮発性メモリの形態におけるコンピュータ・ストレージ・メディアを含み、これは読み取り専用メモリ（ＲＯＭ）１３１およびランダム・アクセス・メモリ（ＲＡＭ）１３２などである。基本入出力システム１３３（ＢＩＯＳ）は、起動中など、コンピュータ１１０内の複数の要素の間で情報を転送する助けとなる基本ルーチンを含み、通常はＲＯＭ１３１に格納される。ＲＡＭ１３２は通常、処理装置１２０によって即時アクセス可能および／または現在動作中であるデータおよび／またはプログラム・モジュールを含む。例として、限定ではなく、図１は、オペレーティング・システム１３４、アプリケーション・プログラム１３５、他のプログラム・モジュール１３６およびプログラム・データ１３７を例示する。

コンピュータ１１０はまた、他のリムーバブル／非リムーバブル、揮発性／不揮発性のコンピュータ・ストレージ・メディアも含むことができる。例としてのみ、図１は、非リムーバブル、不揮発性の磁気メディアに対する読み書きを行うハードディスク・ドライブ１４１、リムーバブル、不揮発性磁気ディスク１５２に対する読み書きを行う磁気ディスク・ドライブ１５１、および、ＣＤ ＲＯＭまたは他の光メディアなど、リムーバブル、不揮発性の光ディスク１５６に対する読み書きを行う光ディスク・ドライブ１５５を例示する。例示的オペレーティング環境で使用することができる他のリムーバブル／非リムーバブル、揮発性／不揮発性のコンピュータ・ストレージ・メディアには、それだけに限定されないが、磁気テープ・カセット、フラッシュ・メモリ・カード、デジタル多用途ディスク、デジタル・ビデオ・テープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭなどが含まれる。ハードディスク・ドライブ１４１は通常システム・バス１２１に、インターフェース１４０などの非リムーバブル・メモリ・インターフェースを通じて接続され、磁気ディスク・ドライブ１５１および光ディスク・ドライブ１５５は通常システム・バス１２１に、インターフェース１５０などのリムーバブル・メモリ・インターフェースによって接続される。

上述し、図１に例示したドライブおよびそれらの関連付けられたコンピュータ・ストレージ・メディアは、コンピュータ１１０用のコンピュータ可読命令、データ構造、プログラム・モジュールおよび他のデータのストレージを提供する。図１では、たとえば、ハードディスク・ドライブ１４１が、オペレーティング・システム１４４、アプリケーション・プログラム１４５、他のプログラム・モジュール１４６およびプログラム・データ１４７を格納するものとして例示される。これらのコンポーネントを、オペレーティング・システム１３４、アプリケーション・プログラム１３５、他のプログラム・モジュール１３６およびプログラム・データ１３７と同じものにも異なるものにもすることができることに留意されたい。オペレーティング・システム１４４、アプリケーション・プログラム１４５、他のプログラム・モジュール１４６およびプログラム・データ１４７にはここで異なる番号が与えられて、最低でも、それらが異なるコピーであることが例示される。

ユーザはコマンドおよび情報をコンピュータ１１０へ、キーボード１６２、マイクロフォン１６３、および、マウス、トラック・ボールまたはタッチ・パッドなどのポインティング・デバイス１６１などの入力デバイスを通じて、入力することができる。他の入力デバイス（図示せず）には、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、スキャナなどが含まれる可能性がある。これらおよび他の入力デバイスがしばしば処理装置１２０へ、システム・バスに結合されるユーザ入力インターフェース１６０を通じて接続されるが、これを、パラレル・ポート、ゲームポートまたはユニバーサル・シリアル・バス（ＵＳＢ）など、他のインターフェースおよびバス構造によって接続することができる。モニタ１９１または他のタイプの表示デバイスもまたシステム・バス１２１へ、ビデオ・インターフェース１９０などのインターフェースを介して接続される。モニタに加えて、コンピュータはまた、スピーカ１９７およびプリンタ１９６など、出力周辺インターフェース１９５を通じて接続することができる他の周辺出力デバイスを含むこともできる。

コンピュータ１１０はネットワーク環境において、リモート・コンピュータ１８０など、１つまたは複数のリモート・コンピュータへの論理接続を使用して動作することができる。リモート・コンピュータ１８０は、パーソナル・コンピュータ、ハンドヘルド・デバイス、サーバ、ルーター、ネットワークＰＣ、ピア・デバイスまたは他の共通ネットワーク・ノードにすることができ、通常は、コンピュータ１１０に関連して上述した要素の多数またはすべてを含む。図１に示す論理接続は、ローカル・エリア・ネットワーク（ＬＡＮ）１７１およびワイド・エリア・ネットワーク（ＷＡＮ）１７３を含むが、他のネットワークも含むことができる。このようなネットワーキング環境は、オフィス、企業全体のコンピュータ・ネットワーク、イントラネットおよびインターネットにおいて一般的である。

ＬＡＮネットワーキング環境において使用するとき、コンピュータ１１０がＬＡＮ１７１へ、ネットワーク・インターフェースまたはアダプタ１７０を通じて接続される。ＷＡＮネットワーキング環境において使用するとき、コンピュータ１１０は通常、モデム１７２、またはインターネットなどのＷＡＮ１７３を介して通信を確立するための他の手段を含む。モデム１７２を内部または外部にすることができ、システム・バス１２１へ、ユーザ入力インターフェース１６０または他の適切なメカニズムを介して接続することができる。ネットワーク環境では、コンピュータ１１０に関連して示したプログラム・モジュールまたはその一部を、リモート・メモリ・ストレージ・デバイスに格納することができる。例として、限定ではなく、図１はリモート・アプリケーション・プログラム１８５をリモート・コンピュータ１８０上に存在するものとして例示する。図示のネットワーク接続は例示的であり、複数のコンピュータの間で通信リンクを確立する他の手段を使用できることは理解されよう。

本発明を、図１に関して説明したものなど、コンピュータ・システム上で実行することができることに留意されたい。しかし、本発明を、サーバ、メッセージ・ハンドリング専用コンピュータ、または、本発明の異なる部分が分散コンピューティング・システムの異なる部分上で実行される分散システム上で実行することができる。

図２Ａは、本発明の一実施形態によるモデル・オーサリング・システム２００のブロック図である。モデル・オーサリング・システム２００は、モデル・オーサリング・コンポーネント２０２およびオプショナルのユーザ・インターフェース２０４を含む。図２Ａはまた、モデル・オーサリング・コンポーネント２０２が入力として、スキーマ２０６、トレーニング用例テキスト文字列のセット２０８、オプショナルの文法ライブラリ２０９を受信し、ルール・ベース文法（文脈自由文法またはＣＦＧ）２１０を出力することも示す。オプショナルの文法ライブラリ２０９は、日付および時間など、領域に依存しない概念、ならびに、都市名、航空路など、領域依存の概念についての定義を含み、これをアプリケーション・データベースから得ることができる。

システム２００の詳細なオペレーションを以下でより詳細に説明する。しかし、簡単に言えば、ユーザはモデル・オーサリング・コンポーネント２０２に、スキーマ２０６およびトレーニング用例テキスト文字列２０８を提供する。これを、オプショナルのユーザ・インターフェース２０４を通じて、あるいはある他のユーザ入力メカニズムを通じて、あるいは自動手段を通じて行うことができる。モデル・オーサリング・コンポーネント２０２は入力を受信し、ルール・ベース文法２１０をこの入力に基づいて生成する。ルール・ベース文法の一実施例は、コンピュータが入力をテキストの意味表現にマップすることができるようにする文脈自由文法（またはＣＦＧ）である。

スキーマ２０６は、例示的には、モデリングされる領域の意味記述である。スキーマの１つの例示を図２Ｂに示す。図２Ｂは、開発者によってシステム２００へ入力することができる、大幅に簡易化されたスキーマ２１２を例示する。スキーマ２１２は、異なる都市から出発して異なる都市に到着し、異なる出発および到着時間を有するフライトを示す、ユーザからの入力用の様々なテキスト文字列の意味を表現するスキーマである。スキーマ２１２は、フライト表示コマンド（ＳｈｏｗＦｌｉｇｈｔ）がフライトのための意味クラスをスロットとして含むことを示す。スキーマ２１２はまた、フライトのための意味クラスを、４つのスロットを有し、それぞれが、出発時間、到着時間、出発都市、到着都市に対応することを、より詳細に示している。

スキーマ２１２から、モデル・オーサリング・コンポーネント２０２は、図２Ｃに例示するルールのセットを生成することができる。ルール１は、ＳｈｏｗＦｌｉｇｈｔ文は、常に、プロパティ部ＳｈｏｗＦｌｉｇｈｔＰｒｏｐｅｒｔｉｅｓを後続するコマンド部ＳｈｏｗＦｌｉｇｈｔＣｍｄを有することを示す。

ルール２は、ＳｈｏｗＦｌｉｇｈｔＰｒｏｐｅｒｔｉｅｓ部が１つまたは複数のプロパティをその中に有することができることを指し示す。たとえば、ルール２は、ＳｈｏｗＦｌｉｇｈｔＰｒｏｐｅｒｔｉｅｓ部が、オプショナルのＳｈｏｗＦｌｉｇｈｔＰｒｏｐｅｒｔｉｅｓ部を後続することができる少なくとも１つのＳｈｏｗＦｌｉｇｈｔＰｒｏｐｅｒｔｙを含むことを指し示す。ＳｈｏｗＦｌｉｇｈｔＰｒｏｐｅｒｔｉｅｓのこの再帰的定義は、その表現を簡易化し、これが１つまたは複数のプロパティを有することを可能にする。

ルール３は、ＳｈｏｗＦｌｉｇｈｔＰｒｏｐｅｒｔｙ部が、ＳｈｏｗＦｌｉｇｈｔＰｒｅＦｌｉｇｈｔ部、Ｆｌｉｇｈｔ部、およびＳｈｏｗＦｌｉｇｈｔＰｏｓｔＦｌｉｇｈｔ部を含むことを示す。これは、スキーマ内のスロットＦｌｉｇｈｔがプレアンブルおよびポストアンブルを有することができることを指し示す。

第４のルールは、スキーマ内のオブジェクトＦｌｉｇｈｔが、コマンド部を有していないけれども、ｐｒｏｐｅｒｔｉｅｓ部（ＦｌｉｇｈｔＰｒｏｐｅｒｔｉｅｓ）を有するのみであることを示し、これは、Ｆｌｉｇｈｔはスキーマ内のオブジェクトであるが、ＳｈｏｗＦｌｉｇｈｔはコマンドであるからである。ルール５は、ＦｌｉｇｈｔＰｒｏｐｅｒｔｉｅｓ部が再度再帰的に、オプショナルのＦｌｉｇｈｔＰｒｏｐｅｒｔｉｅｓを後続する少なくとも１つのＦｌｉｇｈｔＰｒｏｐｅｒｔｙを含むように定義されることを示す。

ルール６〜９は、図２Ｂに示すスキーマ２１２の４つのスロットに対応する。ルール６は、第１のプロパティを、プリアンブル（ＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙ）が前に来て、後にポストアンブル（ＦｌｉｇｈｔＰｏｓｔＤｅｐａｒｔｕｒｅＣｉｔｙ）が続く、出発都市スロットを有する、として定義する。ルール７は到着都市を同じ方法で定義し、ルール８および９は、出発時間および到着時間を類似の方法でそれぞれ定義する。

図２Ｃで識別されたルールのすべてをスキーマ２１２から、モデル・オーサリング・コンポーネント２０２によって自動的に生成することができるという事実が与えられても、なお、何の特定の語が実際に特定のプレターミナル（コマンド意味クラスについてのコマンド、ならびに、スロットについてのプレアンブルおよびポストアンブル）にマップされるかを示す、書き換えルールはない。たとえば、「ｐｌｅａｓｅ ｓｈｏｗ ｍｅ ｔｈｅ ｆｌｉｇｈｔｓ …」という句がＳｈｏｗＦｌｉｇｈｔＣｍｄにマップされることを示すであろうルールはない。同様に、どの語が、具体的に、たとえば、ＦｌｉｇｈｔＰｒｅＡｒｒｉｖａｌＣｉｔｙプレアンブルにマップするかなどを示す書き換えルールはない。したがって、開発者は、また、モデル・オーサリング・コンポーネント２０２がこれらの書き換えルールも学習できるように、トレーニング用例テキスト文字列および注釈２０８も入力する。

図２Ｄは、用例テキスト文字列２１３の一実施例「Ｆｌｉｇｈｔ ｆｒｏｍ Ｓｅａｔｔｌｅ ｔｏ Ｂｏｓｔｏｎ」を、テキスト文字列２１３に対応する意味注釈２１４と共に例示する。意味注釈２１４は開発者によって提供され、文字列２１３の意味論的な意味を指し示す。意味注釈２１４はたとえば、入力テキスト文字列２１３がＳｈｏｗＦｌｉｇｈｔコマンドに対応し、これはスロットＦｌｉｇｈｔを有し、スロットＦｌｉｇｈｔ自体が２つのスロットを有し、その両方が都市であることを示す。Ｆｌｉｇｈｔスロット内の２つのスロットの間の区別は、スロットの名前によってのみ行われる。一方は「Ａｒｒｉｖａｌ」都市と呼ばれ、他方は「Ｄｅｐａｒｔｕｒｅ」都市と呼ばれる。意味注釈２１４はまた、語「Ｂｏｓｔｏｎ」を「Ａｒｒｉｖａｌ」都市スロットにマップし、語「Ｓｅａｔｔｌｅ」を「Ｄｅｐａｒｔｕｒｅ」都市スロットにマップする。したがって、注釈２１４に基づいて、モデル・オーサリング・コンポーネント２０２は、どのスロットが語「Ｓｅａｔｔｌｅ」および「Ｂｏｓｔｏｎ」にマップするかを知るようになる。

注釈付き用例、および、図２Ｃのテンプレート文法ルールから、モデル・オーサリング・コンポーネント２０２は、図２Ｅに例示した解析木２１６などのルール・ベース文法（またはＣＦＧ）解析木を生成することができる。解析木２１６の第１のレベル２１８（ＳｈｏｗＦｌｉｇｈｔがＳｈｏｗＦｌｉｇｈｔＣｍｄとその後に続くＳｈｏｗＦｌｉｇｈｔＰｒｏｐｅｒｔｉｅｓから形成されることを示す部分）は、図２Ｃのルール１から形成される。

第２のレベル２２０（ＳｈｏｗＦｌｉｇｈｔＰｒｏｐｅｒｔｉｅｓがＳｈｏｗＦｌｉｇｈｔＰｒｏｐｅｒｔｙから形成されることを示す部分）はルール２から生成され、ここで、オプショナルのＳｈｏｗＦｌｉｇｈｔＰｒｏｐｅｒｔｉｅｓ部は使用されない。

次のレベル２２２（ＳｈｏｗＦｌｉｇｈｔＰｒｏｐｅｒｔｙがＳｈｏｗＦｌｉｇｈｔＰｒｅＦｌｉｇｈｔとその後に続くＳｈｏｗＦｌｉｇｈｔＰｏｓｔＦｌｉｇｈｔから形成されることを示す部分）は、図２Ｃのルール３から生成される。

次のレベル２２４（ＦｌｉｇｈｔオブジェクトがＦｌｉｇｈｔＰｒｏｐｅｒｔｉｅｓセクションから形成されることを示す）は、図２Ｃのルール４から生成される。

次のレベル２２６（ＦｌｉｇｈｔＰｒｏｐｅｒｔｉｅｓ部がＦｌｉｇｈｔＰｒｏｐｅｒｔｙ部とその後に続くＦｌｉｇｈｔＰｒｏｐｅｒｔｉｅｓ部から形成されることを示す部分）は、図２Ｃのルール５から生成される。

次のレベル２２８（ＦｌｉｇｈｔＰｒｏｐｅｒｔｙ部がＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙ部とその後に続くＣｉｔｙスロットとその後に続くＦｌｉｇｈｔＰｏｓｔＤｅｐａｒｔｕｒｅＣｉｔｙポストアンブルから形成されることを示すレベル）は、ルール６から生成され、次のレベル２３０（ＦｌｉｇｈｔＰｒｏｐｅｒｔｉｅｓがＦｌｉｇｈｔＰｒｅＡｒｒｉｖａｌＣｉｔｙプレアンブル、ＣｉｔｙスロットおよびＦｌｉｇｈｔＰｏｓｔＡｒｒｉｖａｌＣｉｔｙポストアンブルから形成されることを示すレベル）は、ルール７から生成される。

最後に、語「Ｓｅａｔｔｌｅ」がＣｉｔｙスロットへレベル２２８の下でマップされること、語「Ｂｏｓｔｏｎ」がＣｉｔｙスロットへレベル２３０の下でマップされることを示すレベルは、意味注釈２１４から生成され、これもまたユーザによって入力される。したがって、モデル・オーサリング・コンポーネント２０２は、入力シーケンスにおける語「Ｓｅａｔｔｌｅ」および「Ｂｏｓｔｏｎ」からＣＦＧ解析木へ、また、図２Ｃにおいて生成されたルールへマップする方法を学習することができる。都市ルールもまた、注釈付きデータからではなくライブラリ文法（これは、データを領域特有のデータベースから取ることによって構築することができる）から得ることができることに留意されたい。

しかし、なお、まだツリーにマップされないいくつかの語が入力文において存在する。これらの語には、「Ｆｌｉｇｈｔ」、「ｆｒｏｍ」および「ｔｏ」が含まれる。語「Ｆｌｉｇｈｔ」および「ｆｒｏｍ」は語「Ｓｅａｔｔｌｅ」の前に来るので、これらの語は解析木２１６において様々なプレターミナルにマップすることができ、これには、ＦｌｉｇｈｔＣｍｄ、ＳｈｏｗＦｌｉｇｈｔＰｒｅＦｌｉｇｈｔおよびＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙが含まれる。同様に、語「ｔｏ」は入力テキスト文字列２１３における語「Ｓｅａｔｔｌｅ」と「Ｂｏｓｔｏｎ」の間に存在するので、語「ｔｏ」はＦｌｉｇｈｔＰｏｓｔＤｅｐａｒｔｕｒｅＣｉｔｙにもＦｌｉｇｈｔＰｒｅＡｒｒｉｖａｌＣｉｔｙにもマップすることができる。

語「ｔｏ」は前置詞であることが知られているので、これは、その後に来るものを修飾しなければならない。したがって、語「ｔｏ」は解析木２１６においてＦｌｉｇｈｔＰｒｅＡｒｒｉｖａｌＣｉｔｙプレターミナルにマップすると決定することができる。

しかし、語「Ｆｌｉｇｈｔ」および「ｆｒｏｍ」が解析木２１６においてどこに存在するべきであるかはなお知られていない。また、この２つの語のための特定の文節化は知られていない。たとえば、１つの代替方法では、語「Ｆｌｉｇｈｔ」をＳｈｏｗＦｌｉｇｈｔＣｍｄにマップすることができ、語「ｆｒｏｍ」はＳｈｏｗＦｌｉｇｈｔＰｒｅＦｌｉｇｈｔにマップされる。その場合、プレターミナルＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙは空のセットにマップされる。

もう１つの代替方法によれば、語「Ｆｌｉｇｈｔ」および「ｆｒｏｍ」はＳｈｏｗＦｌｉｇｈｔＣｍｄにマップされ、他のプレターミナルＳｈｏｗＦｌｉｇｈｔＰｒｅＦｌｉｇｈｔおよびＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙは共に空のセットにマップされる。

さらにもう１つの代替方法では、「Ｆｌｉｇｈｔ」はＳｈｏｗＦｌｉｇｈｔＣｍｄにマップされ、「ｆｒｏｍ」はＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙにマップされ、その間に残りのプレターミナルＳｈｏｗＦｌｉｇｈｔＰｒｅＦｌｉｇｈｔは空のセットにマップされる。

これは文節化の曖昧性を表し、これは伝統的に、開発者からの追加の情報がなければ解決されていなかった。いくつかの以前のシステムでは、可能な文節化の各々が単にユーザに表示され、ユーザはこれらの文節化の１つを選択することを許可された。

しかし、このことは、結果としていくつかの問題を生じてきた。最初に、ユーザとのこのタイプの対話は、押しつけがましく、時間がかかる。また、より可能性のあるプレターミナルがあり、より多くの位置合わせされていない語が入力テキスト文字列内にあるとき、ユーザに提示されなければならない可能性の数は劇的に増す。すべてのこのような文節化の候補をユーザによる選択のために有効に表示することは、不可能でないけれども、非常に困難である。加えて、文節化がユーザによる選択のために適切に表示されたときでさえ、ユーザは、文節化において、しばしば、エラーを起こしたり、また、類似テキスト文字列を一貫性がなく、文節化したりする。

一実施形態によれば、期待値最大化（ＥＭ）アルゴリズムが、文節化の選択の曖昧性をなくすために、モデル・コンポーネント２０２における文節化の曖昧性に適用される。ＥＭアルゴリズムは一般に、モデルが観測不可能な隠れ変数を含むとき、最尤推定量を有するモデル・パラメータを推定するためのアルゴリズムである。

図３Ａは、モデル・オーサリング・コンポーネント２０２をより詳細に例示するブロック図である。図３Ａは、モデル・オーサリング・コンポーネント２０２が例示的に、テンプレート文法ジェネレータ３００、文節化ＥＭ適用コンポーネント３０２およびプルーニング(pruning：剪定)・コンポーネント３０４を含むことを示す。テンプレート文法ジェネレータ３００は、スキーマ２０６、および、スキーマ２０６内の意味クラスによって（適切なタイプの単一化を通じて）参照されたオプショナルの文法ライブラリ２０９内のいかなるルールをも受信し、スキーマ２０６およびオプショナルの文法ライブラリ２０９から学習または収集することができるすべてのルールを含むテンプレート文法を生成する。次いで、テンプレート文法がＥＭ文節化コンポーネントによって入力として、トレーニング用例（テキスト文字列およびそれらの注釈）と共に、取られる。ＥＭ文節化コンポーネント３０２はテンプレート文法を使用して、トレーニング用例内の文節化の曖昧性を発見する。次いで、コンポーネント３０２はいかなる文節化の曖昧性をもなくすように動作する。その曖昧性をなくすことに基づいて、文法から書き換えルールを、プルーニング・コンポーネント３０４を使用してプルーニング（剪定）して、ルール・ベース文法２１０を提供することができる。

ＥＭ文節化コンポーネント３０２のオペレーションをさらに例示するため、図２Ｆおよび２Ｇは例示的表を提供する。図２Ｆは、用例のセットを含む表である。そのうちの最初のものは、語「ｆｒｏｍ」が場合によってはプレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄにもプレターミナルＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙにもマップすることができることを示す。この用例をコンポーネント３０２によって「ｆｒｏｍ Ｓｅａｔｔｌｅ ｔｏ Ｂｏｓｔｏｎ」のような用例文から取り入れることができる。第２の用例は、語「Ｆｌｉｇｈｔ ｆｒｏｍ」をプレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄおよびＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙにマップすることができることを示す。この用例を、コンポーネント３０２によって「Ｆｌｉｇｈｔ ｆｒｏｍ Ｓｅａｔｔｌｅ ｔｏ Ｂｏｓｔｏｎ」のような用例文から、取り入れることができる。第３の用例は、語「Ｆｌｉｇｈｔ ｔｏ」をプレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄおよびＦｌｉｇｈｔＰｒｅＡｒｒｉｖａｌＣｉｔｙにマップすることができることを例示し、これを同様にコンポーネント３０２によって「Ｆｌｉｇｈｔ ｔｏ Ｂｏｓｔｏｎ ｏｎ Ｔｕｅｓｄａｙ」のような用例から得ることができる。しかし、用例の文節化は曖昧である。すなわち、第１の用例における語「ｆｒｏｍ」がプレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄにマップされるべきであるか、プレターミナルＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙにマップされるべきであるかは、まだ知られていない。同様に、語「Ｆｌｉｇｈｔ ｆｒｏｍ」がプレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄとＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙの間でどのようにマップされるべきであるかは、知られていない。加えて、言うまでもなく、「Ｆｌｉｇｈｔ ｔｏ」が可能なプレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄとＦｌｉｇｈｔＰｒｅＡｒｒｉｖａｌＣｉｔｙでどのようにマップされるべきであるかは、知られていない。

図２Ｇは、ＥＭアルゴリズム適用コンポーネント２０２のオペレーションをさらに例示する表である。図３Ｂは、コンポーネント２０２のオペレーションを例示する流れ図であり、これを図２Ｆおよび２Ｇと共に説明する。

最初に、コンポーネント３０２はすべての可能な文節化を列挙する。これを図２Ｇの左の列の、「可能な書き換えルール」というラベルが付けられた所に示す。図２Ｇに示す書き換えルールでは、プレターミナル名を形成する複数の語のいくつかが短縮される。したがって、例として、書き換えルールＳＦＣｍｄ→εは、ＳｈｏｗＦｌｉｇｈｔＣｍｄ（ＳＦＣｍｄに短縮）プレターミナルが空のセットにマップされることを示す。同様に、書き換えルールＳＦＣｍｄ→ｆｒｏｍは、語「ｆｒｏｍ」がプレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄにマップされる文節化を表現する。さらに、ＦＰＤＣｉｔｙ→εは、プレターミナルＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙ（ＦＰＤＣｉｔｙに短縮）が空のセットにマップされる文節化を表現し、ＦＰＡＣｉｔｙ→εは、プレターミナルＦｌｉｇｈｔＰｒｅＡｒｒｉｖａｌＣｉｔｙ（ＦＰＡＣｉｔｙに短縮）が空のセットにマップされる文節化を表現する。これらの例から、図２Ｇに示す表の書き換えルール部における他の表意法は自明である。図２Ｆに示す用例についての各可能な文節化が列挙されると言えば十分であろう。

図２Ｆの第１の用例から、ある文節化は、語「ｆｒｏｍ」がＳｈｏｗＦｌｉｇｈｔＣｍｄにマップされることを示し、別の文節化は、語「ｆｒｏｍ」がＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙにマップされることを示す。

図２Ｆの第２の用例は、いくつかの異なる代替文節化もサポートする。たとえば、１つの代替文節化によれば、２語「Ｆｌｉｇｈｔ ｆｒｏｍ」は両方ともプレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄにマップされ、プレターミナルＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙはεにマップされる。もう１つの代替文節化では、語「Ｆｌｉｇｈｔ ｆｒｏｍ」は両方ともプレターミナルＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙにマップされ、プレターミナル「ＳｈｏｗＦｌｉｇｈｔＣｍｄ」はεにマップされる。さらにもう１つの代替文節化では、語「Ｆｌｉｇｈｔ」および語「ｆｒｏｍ」に分割され、語「Ｆｌｉｇｈｔ」はプレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄにマップされ、語「ｆｒｏｍ」はプレターミナルＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙにマップされるようになる。これらの文節化の各々もまた、図２Ｇにおいて列挙された書き換えルールに示される。

第３の用例を、第２の用例に類似の方法で文節化することができ、これにおいて語「Ｆｌｉｇｈｔ ｔｏ」をプレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄにもプレターミナルＦｌｉｇｈｔＰｒｅＡｒｒｉｖａｌＣｉｔｙにもマップすることができ、他のプレターミナルはεにマップされるか、あるいは２語「Ｆｌｉｇｈｔ ｔｏ」をプレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄおよびＦｌｉｇｈｔＰｒｅＡｒｒｉｖａｌＣｉｔｙの間で分割することができる。再度、これらの文節化の各々は、図２Ｇに示す書き換えルールにおいて表現される。

すべての可能な文節化の列挙を、図３Ｂの流れ図におけるブロック３０６によって示す。

文節化をサポートする書き換えルールが列挙された後、これらにはそれぞれ確率が割り当てられる。最初に、図２Ｇに例示したすべての文節化には同じ確率が割り当てられる。これを図３Ｂのブロック３０８によって示す。

次に、コンポーネント３０２が、新たに期待カウントを、列挙された書き換えルールに、図２Ｆの用例におけるこれらのカウントの可能な生起（occurrences）に基づいて、割り当る。これをブロック３１０によって示す。たとえば、第１の用例から、２つの可能な文節化があり、一方は語「ｆｒｏｍ」をＳｈｏｗＦｌｉｇｈｔＣｍｄにマップし、プレターミナルＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙをεにマップし、その他方はＳｈｏｗＦｌｉｇｈｔＣｍｄをεにマップし、語「ｆｒｏｍ」をプレターミナルＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙにマップする。第１の書き換えルールは、ＳｈｏｗＦｌｉｇｈｔＣｍｄプレターミナルがε（空のセット）にマップすることを示す。したがって、用例１における文節化の半分は、図２Ｇの表に示す第１の書き換えルールをサポートする。したがって、第１の用例から、第１の書き換えルール（ＳｈｏｗＦｌｉｇｈｔＣｍｄ→ε）に２分の１のカウントが割り当てられる。

上述のように、第２の用例は３つの異なる文節化をサポートし、その１つは両方の語「Ｆｌｉｇｈｔ ｆｒｏｍ」をプレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄに割り当て、プレターミナルＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙをεに割り当て、もう１つの文節化は、語「Ｆｌｉｇｈｔ」をプレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄにマップし、語「ｆｒｏｍ」をプレターミナルＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙにマップし、最後の文節化は、プレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄをεにマップし、両方の語「Ｆｌｉｇｈｔ ｆｒｏｍ」をプレターミナルＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙにマップする。これらの３つの文節化のうち、１つは第１の書き換えルール（ＳＦＣｍｄ→ε）をサポートする。したがって、第２の用例から、第１の書き換えルールに３分の１のカウントが割り当てられる。

同様に、第３の用例は３つの可能な文節化を有し、その１つはプレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄをεにマップする。したがって、第３の用例から、図２Ｇに示す第１の書き換えルールに再度３分の１のカウントが割り当てられる。

このタイプの解析を使用すると、第２の書き換えルール（ＳＦＣｍｄ→ｆｒｏｍ）が第１の用例によってサポートされるだけであることがわかる。したがって、第１の用例についての２つの可能な文節化があり、その一方は第２の書き換えルールをサポートしているので、第２の書き換えルール（ＳＦＣｍｄ→ｆｒｏｍ）に２分の１が割り当てられる。

第３の書き換えルール（ＳＦＣｍｄ→Ｆｌｉｇｈｔ）は、図２Ｆに示す第２および第３の用例の各々からの文節化の１つによってサポートされる。したがって、これらの各用例は３つの可能な文節化を有するので、第３の書き換えルール（ＳＦＣｍｄ→Ｆｌｉｇｈｔ）に、各用例から３分の１のカウントが割り当てられる。

コンポーネント３０２は、図２において列挙された各書き換えルールに対してカウントをこのような方法で割り当て、これらのカウントを図２Ｇに示す表の第２の列に例示する。これらのカウントはすべて、共通の分母を有するように変換され、次いでこれらが各プレターミナルについて正規化されて、確率が得られる。すなわち、ＳｈｏｗＦｌｉｇｈｔＣｍｄプレターミナルについての合計の確率量は合計で１にならなければならない。したがって、各書き換えルールについてのカウントが正規化係数によって乗算され、その書き換えルールに関連付けられた確率を得る。

たとえば、プレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄについてのカウントの総数が３であることがわかる。したがって、第１の書き換えルール（ＳＦＣｍｄ→ε）の確率は７／１８である。同様に、第２の書き換えルール（ＳＦＣｍｄ→ｆｒｏｍ）についての確率は３／１８である、などとなる。コンポーネント３０２は、この確率を得るために、各書き換えルールおよび各プレターミナルについてのカウントを処理する。

このように、プレターミナルＦＰＤＣｉｔｙでは、すべての異なるルールに渡るカウントの合計は２であり、したがって正規化係数は１／２である。最後のプレターミナルＦＰＡＣｉｔｙでは、１のカウント（３＊１／３＝１）しかなく、したがって正規化係数は１である。このように、コンポーネント３０２は、各書き換えルールに関連付けられた確率を１に再設定し、これは、用例によってサポートされた書き換えルールの生起をより正確に反映することがわかる。カウントを正規化して新しい確率を得ることを、図３Ｂのブロック３１２によって示す。

コンポーネント３０２はこのプロセス（各カウントを推定し、新しい確率を得ること）において、カウントおよび確率が収束するまで繰り返す。これをブロック３１４によって示す。たとえば、第１の書き換えルールについての新しいカウント

を得るために、コンポーネント３０２は式１を実装し、これは最初に、以下のようにノンターミナル・シーケンスＳｈｏｗＦｌｉｇｈｔＣｍｄおよびＦＰＤＣｉｔｙが与えられると、語「ｆｒｏｍ」を観測する合計の尤度を発見する。
式１
Ｐ（ｆｒｏｍ｜ＳｈｏｗＦｌｉｇｈｔＣｍｄ ＦＰＤＣｉｔｙ）
＝Ｐ（ε｜ＳｈｏｗＦｌｉｇｈｔＣｍｄ）＊Ｐ（ｆｒｏｍ｜ＦＰＤＣｉｔｙ）
＋Ｐ（ｆｒｏｍ｜ＳｈｏｗＦｌｉｇｈｔＣｍｄ）＊Ｐ（ε｜ＦＰＤＣｉｔｙ）
＝［（７／１８）×（５／１２）］＋［（３／１８）×（５／１２）］＝５０／２１６
この量から、空の文字列をＳｈｏｗＦｌｉｇｈｔＣｍｄに位置合わせし、「ｆｒｏｍ」をＦＰＤＣｉｔｙに位置合わせする文節化についての比率は、以下のように新しい期待カウント

になる。

同様に、第２の書き換えルール（ＳＦＣｍｄ→ｆｒｏｍ）についての新しいカウント

は、以下のように計算される。

このプロセスが各書き換えルールについて継続されて、各用例からのカウント

が収集される。次いで、新しいカウントが正規化係数によって乗算されて、新しい確率が得られる。図３Ｂに示すように、コンポーネント３０２はこのプロセスにおいて繰り返し、新しいカウントおよび新しい確率を、確率が収束するまで再推定する。

この繰り返しが完了した後、コンポーネント３０２は、算出された、列挙された各書き換えルールに関連付けられた、新しいカウントおよび新しい確率を有することになる。このことは、それ自体、トレーニング中に得られた異なる文節化に対応するルールに、各文節化への確率を割り当てているので、大変有用であるが、このことは、所望する最終結果ではない可能性がある。たとえば、いくつかのパーサーは確率を利用することができない。また、いくつかの構文解析コンポーネントでは、多数のルールがパーサーをそれほど有効でなくする。

したがって、１つの例示的実施形態によれば、コンポーネント３０２は、ルールおよび関連付けられた確率をプルーニング・コンポーネント３０４に提供し、ここでルールをプルーニング（剪定：）することができる。これを、図３Ｂのブロック３１６および３１８によって示す。プルーニング・コンポーネント３０４はルールを、いくつかの異なる方法の１つでプルーニングすることができる（ブロック３２０によって示す）。たとえば、プルーニング・コンポーネント３０４は単に、所望のしきい値レベルより下の確率を有するルールをプルーニングして除くことができる。次いで、コンポーネント３０４は残りのルールをルール・ベース文法２１０に導入する。

もう１つの例示的実施形態によれば、プルーニング・コンポーネント３０４は、各用例に対応する高い尤度を有する所定の数の文節化を除くすべてを取り除き、残りの文節化に従って文法に書き換えルールを提供するだけである。たとえば、コンポーネント３０４は、最高の確率を有するものを除く、各用例に対応するすべての文節化を取り除くことができる。このように、用例１では、語「ｆｒｏｍ」をプレターミナルＦｌｉｇｈｔＰｒｅＤｅｐａｒｔｕｒｅＣｉｔｙにマップした文節化が、語「ｆｒｏｍ」をプレターミナルＳｈｏｗＦｌｉｇｈｔＣｍｄに割り当てた文節化よりも高い確率を有したと仮定する。その場合、２番目の文節化（「ｆｒｏｍ」をＳｈｏｗＦｌｉｇｈｔＣｍｄにマップしたもの）が取り除かれる。その場合、選択された文節化をサポートする２つの書き換えルールが文法に追加される。したがって、書き換えルール「ＳＦＣｍｄ→ε」および書き換えルール「ＦＰＤＣｉｔｙ→ｆｒｏｍ」が両方とも文法に追加される。

同様に、すべての用例のうちの最良の文節化によってもはやサポートされないルールを、図２Ｇに示された列挙されたルールから除去することができる。したがって、ルール「ＳＦＣｍｄ→ｆｒｏｍ」は、それが、除去されている用例１についての文節化によってサポートされているだけであるので、除去することができる。

この方法におけるＥＭアルゴリズムの適用を、より形式的な数学的表現で、これより説明する。文節化の曖昧性の解決は、各ブロックがシーケンスＮ＝ＮＴ_１，ＮＴ_２，…，ＮＴ_ｍにおけるプレターミナルに位置合わせするように、語のシーケンスｗ＝ｗ_１，，ｗ_２，…，ｗ_ｎについて、ｍブロック・パーティションπ＝α_１，α_２，…，α_ｍを発見する問題として公式化することができる。ブロックは、ｗからの０個またはそれ以上の語を含むことができる。

π、Ｎおよびｗの結合確率をモデリングする場合、以下のようになる。

次いで、Ｎおよびｗが与えられると、最も可能性の高い文節化を以下のように得ることができる。

このようなパーティションをビタビ探索により発見することができる。したがって、残された唯一の問題は、モデル・パラメータＰ（ＮＴ→α）を、あらゆるプレターミナル（または概念）ＮＴおよび語のシーケンスα、について推定することである。トレーニング・データが、各プレターミナルについての語のシーケンスとペアにされたプレターミナルのリストである場合、このことを最尤（ＭＬ）推定により行うことができる。しかし、ユーザからオーサリング・ツールを介して得られたトレーニング用例は例示的に、プレターミナル・シーケンスおよびターミナル・シーケンスのペアである。パーティションまたは文節化は隠れ変数であり、ツールにとっては未知である。

ＥＭアルゴリズムは最初に、モデルについてパラメータＰ_Φを設定し、次いで、観測Ｄの尤度が増すように反復的にパラメータをＰ_Φ’に修正する。
このようなＰ_Φ’を発見するため、補助関数Ｑを式６に定義する。

これは、Ｌ（Ｄ｜Ｐ_Φ’）−Ｌ（Ｄ｜Ｐ_Φ）の下限であり、２つのモデル・パラメータ化の間のトレーニング・データの対数尤度差である。ＥＭアルゴリズムは、プレターミナルについてのすべての可能な書き換えルールの確率が合計で１にならなければならないという制約を受け、新しいパラメータ化によるトレーニング・サンプル尤度の増大を最大にするように、Ｑを最大化することにより、パラメータＰ_Φ’を意欲的に再設定する。したがって、各ルールＮＴ→αについて、その新しい確率を、以下の式を解くことによって得ることができる。

なので、以下のようになる。

したがって、確率は、期待カウントに正規化係数−１／λを掛けたものに再設定されるべきである。

期待カウントを計算するため、以下に留意されたい。

よって、以下の通りである。

が、プレターミナル・シーケンスＮを語シーケンスｗに書き換えるプロセスにおいて、ルールＮＴ→αがＮにおけるｋ番目のプレターミナルについて使用されてサブ・シーケンスα＝ｗ_ｉ，…，ｗ_ｊを生成するイベントであるとし、および

が、シーケンスＮにおける位置ｓからｔへのプレターミナルが、ターミナル語ｗ_Ｐ，…，ｗ_ｑ＝１を包含する確率であるとする。そうすると、以下のようになる。

したがって、仮に、

を計算することができる場合、式（９）、（１１）および（１３）を結合して、期待カウントを得て、モデル・パラメータを再設定することができる。実際には、

は、式１４に従うダイナミック・プログラミングにより計算することができ、ただしεはヌル文字列である。

式１１において、

を使用できることに留意されたい。

図４は、本発明の異なる態様によるモデル・オーサリング・コンポーネント３５０のもう１つの実施形態３５０を例示する。ルール・ベース文法２１０は、まだ、望まれるよりも頑強ではなく、より脆弱である可能性がある。たとえば、トレーニング中に、以下のルールが生成されて以下のプレターミナルがモデリングされると仮定する。
ＦｌｉｇｈｔＰｒｅＡｒｒｉｖａｌＣｉｔｙ→ｔｏ
ＳｈｏｗＦｌｉｇｈｔＣｍｄ→Ｓｈｏｗ ｍｅ ｔｈｅ ｆｌｉｇｈｔ
さらに、ランタイム中に、入力された文が「Ｓｈｏｗ ｆｌｉｇｈｔ ｔｏ Ｂｏｓｔｏｎ」であると仮定する。この入力文は、「Ｓｈｏｗ ｆｌｉｇｈｔ」がＳｈｏｗＦｌｉｇｈｔＣｍｄであることを示すルールがないので、理解されないことになる。

ＣＦＧは、高分解理解（high resolution understanding）について十分に機能する。高分解理解は、文を多数のスロットに分解する文法を表現する。スロットの数が多くなるほど、より高い分解理解が文法によって示される。ＣＦＧは、高分解の状況において十分に一般化する。

しかし、満たされるべき多数のスロットがない場合、多くの適用は、低い分解理解を必要とする。１つのこのような適用は、コマンドおよびコントロールである。たとえば、コマンドおよびコントロール適用では、認識されなければならないいくつかのコマンドには、「ＣｈａｎｇｅＰａｓｓｗｏｒｄ」、「ＣｈａｎｇｅＢａｃｋｇｒｏｕｎｄ」および「ＣｈａｎｇｅＬｏｇｉｎＰｉｃｔｕｒｅ」が含まれる。これらの場合では、満たされるべきスロットはなく、文全体がコマンドとして認識されなければならない。トレーニング中に、これは十分に結果として以下のようなルールを生じることができる。
ＣｈａｎｇｅＬｏｇｉｎＰｉｃｔｕｒｅＣｍｄ→Ｐｌｅａｓｅ ｃｈａｎｇｅ ｍｙ ｌｏｇｉｎ ｉｃｏｎ
「ＣｈａｎｇｅＬｏｇｉｎＰｉｃｔｕｒｅ」はコマンドであるので、ルールへのプロパティ部はない。したがって、文法学習者は単に、それが獲得したルールにおいて全文を「記憶する」。ユーザが発行したコマンドを認識し、呼び出すために、このコマンドはトレーニング・データ内の全文にマッチしなければならない。汎用化はまったくない。

テンプレート文法内のルールによりプレターミナル（コマンド、プレアンブル、ポストアンブルなど）をモデリングする代わりに、本発明の一実施形態が引き出され、統計モデル（ｎ−グラムなど）がプレターミナルをモデリングするために使用される。一実施形態では、テンプレート文法におけるプレターミナルに対応する、列挙された文節化について生成されたテキストが、ｎ−グラム（または他の統計モデル）についてのトレーニング・データとして使用される。したがって、上記の用例では、プレターミナルについて列挙された文節化に対応するテキスト文字列が、ＥＭアルゴリズムの期待ステップにおいて収集されたその期待カウントと共に、プレターミナルについてのｎ−グラムをトレーニングするために使用される。このように、テキスト「Ｓｈｏｗ ｍｅ ｔｈｅ ｆｌｉｇｈｔ」がトレーニング・データとして使用されて、ＳｈｏｗＦｌｉｇｈｔＣｍｄプレターミナルをモデリングするためのｎ−グラムがトレーニングされる。したがって、それにおける「Ｓｈｏｗ ｆｌｉｇｈｔ」を有する文がＳｈｏｗＦｌｉｇｈｔＣｍｄとして認識されるであろう確率を、以下のように計算することができる。

式１５
Ｐｒ（＜ｓ＞ＳｈｏｗＦｌｉｇｈｔ＜／ｓ＞｜ＳｈｏｗＦｌｉｇｈｔＣｍｄ）＝
Ｐｒ（ｓｈｏｗ｜＜ｓ＞； ＳｈｏｗＦｌｉｇｈｔＣｍｄ）＊
Ｐｒ（ｆｌｉｇｈｔ｜ｓｈｏｗ；ＳｈｏｗＦｌｉｇｈｔＣｍｄ）＊
Ｐｒ（＜／ｓ＞｜ｆｌｉｇｈｔ； ＳｈｏｗＦｌｉｇｈｔＣｍｄ）

このルールは、ＳｈｏｗＦｌｉｇｈｔＣｍｄとして認識された「ｓｈｏｗ ｆｌｉｇｈｔ」を有しないけれども、式１５における上記のｎ−グラム確率はゼロにならない。式１５における第１の係数および第３の係数は、これらの係数が、実際にトレーニング・データ内に存在するバイグラムに対応するので、ゼロではない（たとえば、［＜ｓ＞ ｓｈｏｗ］および［ｆｌｉｇｈｔ ＜／ｓ＞］）。第２の係数は、トレーニング・データにおいて現れたバイグラムに対応しないが、バック−オフのような平滑化技術（後述）があるため、これもまたゼロでない確率を有するようになり、以下のように表現することができる。

式１６
Ｐｒ（ｆｌｉｇｈｔ｜ｓｈｏｗ；ＳｈｏｗＦｌｉｇｈｔＣｍｄ）＝
ｂａｃｋｏｆｆ＿ｗｅｉｇｈｔ＊Ｐｒ（ｆｌｉｇｈｔ｜ＳｈｏｗＦｌｉｇｈｔＣｍｄ）
バック−オフ重みを経験的に、あるいはそうでない場合は望むように設定することができ、ユニグラム確率Ｐｒ（ｆｌｉｇｈｔ｜ＳｈｏｗＦｌｉｇｈｔＣｍｄ）は、「ｆｌｉｇｈｔ」がトレーニング・データ内の語であるので、ゼロではない。

パーサーは、Ｐｒ（ｓｈｏｗ ｆｌｉｇｈｔ＜／ｓ＞｜ＳｈｏｗＦｌｉｇｈｔＣｍｄ）＞０なので、入力文をＳｈｏｗＦｌｉｇｈｔ候補として見なすようになる。入力文の最終的な解釈は、他の解釈候補との比較によって決まるようになる。

したがって、図４は、スロットおよび統計モデル部３２６（ｎ−グラムなど）をモデリングするためのルールを含み、プレターミナル（コマンド、プレアンブルおよびポストアンブルなど）を識別する、文法部２１０（ＣＦＧなど）を含む複合モデル３５１を作成するモデル・オーサリング・コンポーネントのもう１つの実施形態３５０を示す。したがって、ランタイム中に、入力文は、統計モデル部３２６を使用して評価されてプレターミナルが識別され、ルール・ベース文法部２１０を使用して評価されてスロットが満たされる。

コンポーネント３５０は複合モデル３５１を、部分的には、上述のＥＭアルゴリズム技術を使用してトレーニングする。たとえば、図５が、異なるサンプル文節化に従ってＳｈｏｗＦｌｉｇｈｔＣｍｄについて列挙されたすべてのルールを示すと仮定する。

図２〜３Ｂに関して上述したモデルでは、ＥＭアルゴリズムのＥ−ステップ中に、期待カウントが、図５に示す列挙された各ルールについて収集される。Ｍ−ステップ中に、カウントが正規化される。しかし、複合モデル３５１では、アルゴリズムのＭ−ステップ中にカウントを正規化する代わりに、列挙されたルールの右側におけるテキスト文字列、および、これらのルールに対応する、関連する期待カウントがトレーニング・データとして使用されて、ＳｈｏｗＦｌｉｇｈｔＣｍｄプレターミナルについてのｎ−グラムがトレーニングおよび平滑化される。

言い換えれば、ｎ−グラムのトレーニングにおいて、フル・カウントが語シーケンスの各生起について追加される必要はない。その代わりに、トレーニング・シーケンスに関連付けられたルールについての期待カウントに対応する部分データ（図３Ａで例示したＥＭ適用コンポーネント３０２によって生成されたもの）が、語シーケンスの各生起について追加される。

図２〜３Ｂに関して文節化の曖昧性をなくすことについて説明した実施形態とのもう１つの違いは、ＥＭアルゴリズムのＥ−ステップに関連する。確率を、列挙された各ルールに関連付けるのではなく、ルールの確率はルール内のすべてのｎ−グラムの積である。

たとえば、上述のルール・ベース文法では、ルール、ＳｈｏｗＦｌｉｇｈｔＣｍｄ→Ｓｈｏｗ ｍｅ ｔｈｅ ｆｌｉｇｈｔは、それに関連付けられたアトミック確率を有する。しかし、複合モデル３５１では、ルールについての確率を以下のように計算することができる。
式１７
Ｐｒ（ＳｈｏｗＦｌｉｇｈｔＣｍｄ→Ｓｈｏｗ ｍｅ ｔｈｅ ｆｌｉｇｈｔ）＝
Ｐｒ（ｓｈｏｗ｜＜ｓ＞； ＳｈｏｗＦｌｉｇｈｔＣｍｄ）＊
Ｐｒ（ｍｅ｜ｓｈｏｗ； ＳｈｏｗＦｌｉｇｈｔＣｍｄ）＊
Ｐｒ（ｔｈｅ｜ｍｅ； ＳｈｏｗＦｌｉｇｈｔＣｍｄ）＊
Ｐｒ（ｆｌｉｇｈｔ｜ｔｈｅ； ＳｈｏｗＦｌｉｇｈｔＣｍｄ）＊
Ｐｒ（＜／ｓ＞｜ｆｌｉｇｈｔ； ＳｈｏｗＦｌｉｇｈｔＣｍｄ）

また、本発明の一実施形態によれば、プレターミナルについての統計モデルのトレーニングには、平滑化アルゴリズムを適用することが含まれる。たとえば、プレターミナルについての統計モデルをトレーニングするためのトレーニング・データは比較的疎（sparse）である可能性があり、これは、このトレーニング・データが、所与のプレターミナルに関連付けられた文節化について列挙されたテキスト文字列を含むだけであるからである。このことは、統計モデルによって対象とされない（カバーされない）比較的大量の言語表現を残し、したがって、統計モデルを比較的脆弱にさせる。このように、モデル確率は、より低いレベルのｎ−グラムを使用して、一様分布状態に平滑化される。すなわち、統計モデルがバイグラムを含む場合、これは、文脈（context）に関係なくモデリングされた語についての確率を提供するユニグラムにより平滑化される。加えて、統計モデルは、同じ確率を語彙内の各語に割り当てる一様分布により平滑化される。したがって、語が語彙内にある場合、これは統計モデルによって、ゼロ確率によりモデリングされないようになる。削除された補間が使用されて、平滑化のオペレーションにおいて各モデルについての重みが求められ、異なる次数のモデルが線形補間される。

コンポーネント３５０はまた、本発明の異なる実施形態による追加の統計モデル・コンポーネントをトレーニングすることもできる。これをより詳細に、図６に示すブロック図に例示する。たとえば、そのブロック図で、統計モデル部３２６を、プレターミナルについての統計モデル・コンポーネント３４０を含むだけでなく、複数の他の統計モデルも含むものとして示す。たとえば、統計モデル３２６は、一実施形態では、コンポーネント３４２および３４４を含み、これらは、タスクの事前確率をモデリングする統計モデル、および、スロット遷移についての統計モデルを含む。

たとえば、ランタイム入力文が「Ｓｈｏｗ ｆｌｉｇｈｔｓ ｔｏ Ｂｏｓｔｏｎ ａｒｒｉｖｉｎｇ ｏｎ Ｔｕｅｓｄａｙ， １１：００ ａ．ｍ．」である場合、語「ａｒｒｉｖｉｎｇ ｏｎ」は、「Ｔｕｅｓｄａｙ」が到着日に対応することを示すものとして解析されるようになる。しかし、「１１：００ ａ．ｍ．」の前に、それが出発時間であるのか到着時間であるのかを示すための語はない。「到着時間」スロットが「到着日」スロットの後に続く確率は、「出発時間」スロットが「到着日」スロットの後に続く確率より高い可能性が高くなる。このようなスロット遷移がモデリングされる場合、スロット遷移モデルは、「１１：００ ａ．ｍ．」が「ａｒｒｉｖａｌ ｔｉｍｅ」スロットにマッチされる方を選ぶようになる。また、統計モデル（ｎ−グラム・モデルなど）をトレーニングしてスロット遷移をモデリングすることは、統計モデル（ｎ−グラムモデルなど）をトレーニングしてスロットの事前確率をモデリングすることと、ｎの次数が異なることを除いて同じであることにも留意されたい。スロットの事前確率では、ユニグラム・モデルがトレーニングされ、２つのスロットの間のスロット遷移をモデリングするために、バイグラム・モデルがトレーニングされるなどとなる。

さらに、いくつかのコマンドは、トレーニング・データにおいて他のものより頻繁に発生する。したがって、コマンドの事前確率はモデル３４２においてモデリングされる。

本発明を、これから、もう１つの実施例に関して、より詳細に説明する。図７は、アポイントメント・スケジューリング・コマンドＮｅｗＡｐｐｔについてのセマンティクスを定義する、スキーマにおける意味クラスの１つの例示的な簡易化された実施例を示す。

図８は、意味クラスＮｅｗＡｐｐｔについて自動的に生成することができるテンプレート・ルールを例示し、ただし中括弧（braces）内のシンボルはオプショナルである。図９は、注釈付き文の一実施形態「Ｎｅｗ ｍｅｅｔｉｎｇ ｗｉｔｈ Ｐｅｔｅｒ ａｔ ５：００」を例示する。図１０は、文節化の曖昧性をなくすことが前述のように実行された後に追加することができる、２つのルールを例示する。

しかし、前述のように、純粋なルール・ベースの文法は頑強性に欠け、脆弱性を示す可能性がある。したがって、本発明の一態様は、ＣＦＧルールをｎ−グラムで置き換えて、テンプレート文法におけるコマンド、プレアンブルおよびポストアンブルの各々をモデリングし、スロット遷移をモデリングする。スロットｎ−グラムは、プレアンブルおよびポストアンブルを欠くスロットの解釈を制約する。結果として生じるモデルは、統計モデル（またはＨＭＭ）およびＣＦＧの複合である。ＨＭＭはテンプレート・ルールおよびｎ−グラムプレターミナルをモデリングし、ＣＦＧはライブラリ文法をモデリングする。

このようなモデルの一実施例を図１１に示す。語「Ａｔｔ」は、「Ａｔｔｅｎｄｅｅ」の省略形であり、「ＳＴ」は「ＳｔａｒｔＴｉｍｅ」の省略形である。出力確率（emission probabilities）ｂはプレターミナル依存ｎ−グラムであり（この図では、これらをユニグラムとして示すが、高位出力分布は結果として高位ＨＭＭを生じるようになる）、遷移確率ａはスロット遷移バイグラムである。スロット・ノードからの出力τは、ライブラリＣＦＧノンターミナルである。語はこれらから、ＣＦＧモデルＰ_ＣＦＧに従って生成される。

図１１に示すモデルでは、入力文ｓの意味を、以下（式１８）を満たすビタビ意味クラスｃおよび状態シーケンスσを発見することによって得ることができる。

新しいモデルはＣＦＧモデルの制限を克服する。低分解理解（タスク分類）では、プロパティ・プレターミナルがテンプレート文法に導入されない。したがって、すべてのトレーニング・データが使用されて、コマンド・プレターミナルについてのｎ−グラムがトレーニングおよび平滑化される。このモデルは、式１９によって表現されるｎ−グラム分類子に縮小する。

ｎ−グラム・モデルは厳密なルールマッチを必要としない。ルール適用可能性について二分決定（binary decisions）を行うのではなく、これは観測された語シーケンスが状態（プレターミナル）シーケンスから生成される確率を比較して、最も可能性の高い解釈を発見する。したがって、モデル自体は頑強であり、頑強なパーサーの必要性がない。

これより、トレーニングをより詳細に、図７〜１１に示す実施例に関して説明する。モデルをトレーニングするため、ＥＭアルゴリズムは自動的に語シーケンスを文節化し、各文節αを、対応するペアのプレターミナル・シーケンスにおいて対応するプレターミナルＮＴに位置合わせする。ＥＭアルゴリズムは、ＮＴから生成する語の文字列に対して確率を割り当てるモデルＰ（ＮＴ→α）を構築し、これを初期一様分布によりパラメータ化する。次いで、これは、パラメータ化を反復的にリファインする。各反復において、これは、ルールＮＴ→αについての期待カウントを、前の反復におけるモデルのパラメータ化に従って計算し（Ｅステップ）、次いで、確率Ｐ（ＮＴ→α）を、期待カウントを正規化することによって再推定する（Ｍステップ）。プレターミナルをｎ−グラムでモデリングする新しいモデルをトレーニングするため、Ｅ−ステップにおいて収集された期待カウントが使用されて、Ｍ−ステップにおいてｎ−グラムがトレーニングおよび平滑化され、このｎ−グラムはＥＭアルゴリズムによって使用されて、文節化についての期待カウントが収集される。このことは、結果として、図１２に例示するトレーニング・アルゴリズムを生じる。

１つの例示的実施形態では、図１２の最後の行において例示されたしきい値は０．０１に設定される。言うまでもなく、他のしきい値も使用することができる。

本発明のもう１つのオプショナルの態様にも留意されたい。オプショナルの文法ライブラリ２０９（図２Ａ、４および１３に示す）をトレーニング・データ２０８に統計的に適合させることができる。たとえば、文法ライブラリ２０９が、大小の国内外の都市を含む、比較的大きい都市リストを含むと仮定する。しかし、さらに、モデルがトレーニングされている特定の適用（application）は国内の都市のみを参照する傾向があり、さらに、ニューヨークおよびロサンゼルスなどの国内の大都市は、より小さい都市よりも参照される可能性が高いと仮定する。コンポーネント２０２または３５０は、文法２０９を備えることができる確率文脈自由文法（ＰＣＦＧ）に関連付けられた確率を、注釈付きトレーニング・データ２０８から学習する。たとえば、ルールＣｉｔｙｎａｍｅ→Ｎｅｗ Ｙｏｒｋについての確率は、ルールＣｉｔｙｎａｍｅ→Ｔｏｋｙｏについての確率より大きいことを学習することができる。このことは、上述の他の確率が学習されるのと同じ方法で行うことができる。

図１３は、スロットについてのルール・ベース文法部およびプレターミナルについての統計モデル部を共に使用したランタイム・システムを例示する。このシステムは入力を受信し、文法部およびｎ−グラム部を使用し、出力４０２を出力する。

復号化をより詳細に、図１４に関して説明する。図１４は、入力「ｎｅｗ ｍｅｅｔｉｎｇ ｗｉｔｈ Ｐｅｔｅｒ ａｔ ｆｉｖｅ」についてのダイナミック・プログラミング・デコーダを表しているダイナミック・プログラミング・トレリス構造を例示している。

ダイナミック・プログラミング・デコーダは、上記の式１８によって表現されたビタビ経路を発見する。入力を受信すると、デコーダは最初にボトムアップのチャート・パーサーを使用して、いくつかの入力スパンを包含するライブラリ文法ノン・ターミナルを発見する。この実施例では、これは「Ｐｅｔｅｒ」を＜Ｐｅｒｓｏｎ＞、「ｆｉｖｅ」を＜ｔｉｍｅ＞または＜ｎｕｍ＞と識別する。次いで、デコーダは第１の列の意味クラスノード（この実施例は意味クラスＮｅｗＡｐｐｔのみを示す）から開始して、トレリス中を探索する。各ノードで、これは、同じ列における他のノードへの遷移（異なるノン・ターミナルへの切り替え）、または同じ行における次のノードへの遷移（ノン・ターミナルによる入力語の消費）を行う。探索は左から右へ、これが一番右の列に達するまで継続する。これが遷移を行うとき、適切な対数確率を開始ノードのスコアに追加することによって、スコアが得られる。次いでこのスコアが、宛先ノードのスコアと比較され、新しいスコアの方が高い場合、スコアを置き換える。トレリスより下は、チャート・パーサーによって識別されたノン・ターミナルである。太い経路４１０は、ビタビ解釈を表現する。高い方の細い経路４１２は正しいタスクを識別するが、いずれのスロットも識別しない。低い方の細い経路４１４（ビタビ経路４１０の部分を共有する）は、出席者を識別するが開始タイム・スロットを識別しない。これは「ａｔ ｆｉｖｅ」を出席者についてのポストアンブルとして扱う。図１４に示す最初の９個の各遷移についての対数確率を以下にビタビ経路４１０についてリストする。

任意の所望のプルーニング・メカニズムも使用することができる。たとえば、あるプルーニング・メカニズムは、トレリスの各列で、ノードのスコアが同じ列における最大スコアより低いしきい値（５．０など）より小さい場合、そのノードから遷移が行われないことを規定する。すなわち、経路が同じ列におけるノードに通じる別の経路よりおそらく１０^５倍低い場合、その経路は延長されない。デコーダは、プルーニングの後、頑強なパーサーより１桁速く実行する。

本発明の一実施形態によれば、複合モデル３５１は自然言語理解システムにおいて使用されるだけでなく、音声認識システムにおいても使用することができる。このような実施形態では、音声認識システムは音声認識および自然言語理解を単一のパスにおいて実行することができる。

図１５は、複合モデル３５１が使用される１つの例示的音声認識システム５００のブロック図を例示する。言うまでもなく、複合モデル３５１が、図１５に示す音声認識システムにおいて実装されるので、システム５００は、音声認識に加えて、自然言語理解も実行することができる。これをより詳細に説明する前に、システム５００の全体のオペレーションの簡単な考察を提供する。

図１５で、話者５０１はマイクロフォン５０４に向かって話す。マイクロフォン５０４によって検出されたオーディオ信号は電気信号に変換され、これがアナログ−デジタル（Ａ−Ｄ）コンバータ５０６に提供される。

Ａ−Ｄコンバータ５０６は、マイクロフォン５０４からのアナログ信号を一連のデジタル値に変換する。いくつかの実施形態では、Ａ−Ｄコンバータ５０６はアナログ信号を１６ｋＨｚおよびサンプル当たりに１６ビットでサンプリングし、それにより毎秒３２キロバイトの音声データを作成する。これらのデジタル値はフレーム・コンストラクタ５０７に提供され、これは一実施形態では、これらの値を１０ミリ秒間隔で開始する２５ミリ秒フレームにグループ化する。

フレーム・コンストラクタ５０７によって作成されたデータのフレームは、特徴抽出器（feature extractor）５０８に提供され、これが特徴を各フレームから抽出する。特徴抽出モジュールの例には、線形予測符号化（ＬＰＣ）、ＬＰＣ導出ケプストラム、知覚線形予想（ＰＬＰ）、聴覚モデル特徴抽出、およびメル周波数ケプストラム係数（Mel-Frequency Cepstrum Coefficients：ＭＦＣＣ）特徴抽出を実行するためのモジュールが含まれる。本発明はこれらの特徴抽出モジュールに限定されず、本発明とのコンテクスト内で他のモジュールを使用できることに留意されたい。

特徴抽出モジュール５０８は、それぞれが音声信号のフレームに関連付けられている特徴ベクトルのストリームを生じる。この特徴ベクトルのストリームは、デコーダ５１２に提供され、そこで、最も可能性の高い語のシーケンスが、特徴ベクトルのストリーム、レキシコン５１４、言語モデル３５１および音響モデル５１８に基づいて、識別される。復号化のために使用される特定の方法は、本発明には重要ではない。

仮説語の最も確からしいシーケンスを、オプショナルの信頼性測定モジュール５２０に提供することができる。信頼測定モジュール５２０は、どの語が音声認識装置によって不適切に識別されている可能性が最も高いかを識別する。これを、部分的には２次音響モデル（図示せず）に基づかせることができる。次いで、信頼測定モジュール５２０は仮説語のシーケンスを出力モジュール５２２へ、どの語が不適切に識別されている可能性があるかを示す識別子と共に、提供する。信頼測定モジュール５２０は本発明の実施のために必要ではないことは、当業者には理解されよう。

トレーニング中に、トレーニング・テキスト５２６に対応する音声信号がトレーナ５２４_{［ＹＷ１］}に、トレーニング・テキスト５２６の語彙表記（lexical transcription）と共に入力される。トレーナ５２４は音響モデル５１８を、トレーニング入力に基づいてトレーニングする。複合言語モデル３５１のトレーニングについては上述した。

同じく上述したように、モデル３５１は、（たとえば、隠れマルコフ・モデル技術を使用して実装される）統計部を使用して適用スキーマの構造情報を符号化し、（たとえば、ＣＦＧ技術を使用して実装される）ルール・ベース部を使用して、いくつかのＨＭＭ状態の出力（emissions）をモデリングする。図１６〜１７Ｂは、モデルのトポロジを、それが未知語を説明するとしても、どのようにこのモデルを有限状態表現において、コンパクトな方法で、表現することができるかの考察を容易にするような方法で例示する。

図１６は、もう１つの適用スキーマ６００の１つの例示的実施形態である。スキーマ６００は単に、この適用が２つのタイプの情報クエリ、すなわち、フライト情報についてのもの（ＳｈｏｗＦｌｉｇｈｔタスク）、および、陸上輸送情報についてのもの（ＧｒｏｕｎｄＴｒａｎｓｐｏｒｔタスク）をサポートすることを示す。フライト情報を得るために、ユーザは到着都市（ＡＣｉｔｙ）および／または出発都市（ＤＣｉｔｙ）スロットについての情報を提供して、システムがユーザの仕様に従って情報を探索することができるようにしなければならない。スロットのタイプは、その「フィラー」についての要件を指定する。ＡＣｉｔｙおよびＤＣｉｔｙスロットの両方について、フィラーは、タイプ「Ｃｉｔｙ」のオブジェクトを参照する文法ライブラリにおいてモデリングされた表現でなければならない。

図１７Ａおよび１７Ｂは、スキーマ６００の意味制約を自然言語理解ルール・ベース文法（ＣＦＧなど）に組み込む統計モデル部（ＨＭＭ）を示す。図１７Ａは、最上位構造６０２を例示し、これは２つのブランチを有し、一方はＳｈｏｗＦｌｉｇｈｔサブ・ネットワーク６０４につながり、他方はＧｒｏｕｎｄＴｒａｎｓｐｏｒｔネットワーク６０６につながる。各ブランチにおける遷移重みは、２つのタスクについての確率である。したがって、Ｓ−ノードからＳｈｏｗＦｌｉｇｈｔサブ・ネットワーク６０４への遷移重みは、ＳｈｏｗＦｌｉｇｈｔタスク（またはコマンド）の確率に対応し、ＧｒｏｕｎｄＴｒａｎｓｐｏｒｔサブ・ネットワーク６０６への遷移重みは、ＧｒｏｕｎｄＴｒａｎｓｐｏｒｔタスクの確率に対応する。

図１７Ｂは、ＳｈｏｗＦｌｉｇｈｔサブ・ネットワーク６０４モデルをより詳細に例示し、このサブ・ネットワーク・モデルの使用を図１７Ｃによって例示する。図１７Ｂに示すＳｈｏｗＦｌｉｇｈｔサブ・ネットワーク・モデルは、ユーザがＳｈｏｗＦｌｉｇｈｔコマンドを発行するために使用することができる言語表現をモデリングする。このサブ・ネットワーク・モデルはコマンド部（「Ｓｈｏｗ ｍｅ ｔｈｅ ｆｌｉｇｈｔ」など）により開始し、その後にスロットについての表現が続く。各スロットは、プレアンブルおよびポストアンブルによって一まとめに扱われ、プレアンブルおよびポストアンブルはスロットについての言語的文脈としての機能を果たす。たとえば、語「ｆｒｏｍ」はＤＣｉｔｙスロットについてのプレアンブルである。これは、その後に続くＣｉｔｙが出発都市である可能性が高いことを示唆する。これらのスロットは相互接続され、これらの接続はスロット遷移についてのバイグラム確率により重み付けされ、これはトレーニング・データから推定される。

サブ・ネットワーク・モデル６０４では、コマンド、プレアンブルおよびポストアンブルが統計ｎ−グラム・モデルによりモデリングされる。これらをサブ・ネットワーク・モデル６０４における長円形の部分によって例示する。スロット・フィラーは、文法ライブラリからの確率的ＣＦＧルールによりモデリングされる。これらをサブ・ネットワーク・モデル６０４における長方形によって例示する。文法ライブラリにおけるルールについての確率は例示的に、領域特有のデータを使用して調節され、平滑化される。モデル６０４におけるｎ−グラムは、部分的にラベル付きのトレーニング・データによりトレーニングされる。上述のように、ＥＭアルゴリズムを使用してネットワーク内のｎ−グラムをトレーニングすることができ、これらのアラインメントは隠れ変数として扱われる。

頑強なパーサーに依拠して、文法によって包含されない語をスキップした、以前の頑強な理解技術とは異なり、文法におけるプレターミナルについてのｎ−グラム・モデルの使用は、モデルをそれ自体で頑強にする。このことは、本発明の１つの特徴を可能とし、これは複合モデル３５１（図１７Ａおよび１７Ｂに示す一実施形態）を自然言語理解のみにおいて使用するのではなく、音声認識においても使用する、ことを可能にする。このことは、以前のシステムにおいて音声認識および自然言語理解を実施するために使用された、最適状態とは言えない、２パスの手法に勝り、さらに、それは、以前のシステムよりよく例示的に汎用化することができるように、以前の知識を使用する。

しかし、音声認識システムにおけるモデル３５１（図１５に示す言語モデルなど）を使用するために、このモデルは最初に、デコーダ５１２がその言語モデルとして受け入れることができるフォーマットに変換される。したがって、コマンド、プレアンブルおよびポストアンブルをモデリングするために使用された統計ｎ−グラム・モデル（すなわち、ＣＦＧ内のこれらのｎ−グラム）が、確率有限状態オートマトン（automata）に変換される。変換されたｎ−グラムおよび最上位のＨＭＭ構造（図１７Ａに示す６０２など）は、ライブラリ文法におけるルールと共に、確率文脈自由文法（ＰＣＦＧ）言語モデルを形成する。この変換は、周知の変換アルゴリズム（たとえば、非特許文献３参照。）に基づいて、実行することができる。

しかしながら、従来のアルゴリズムに対して、モデルのサイズを著しく縮小するために、１つの著しい修正が行われる。これを、図１８の（ａ）、（ｂ）および（ｃ）によって例示する。図１８の（ａ）および（ｃ）は、２つのプレターミナルについてのバイグラム言語モデルの有限状態表現を例示し、各々は２つの観測語（それぞれａ、ｂおよびｃ、ｄと示す）によりトレーニングされている。モデル内の各円弧におけるラベルは、重みおよび出力シンボルを例示する。文字Ｉは初期状態を表現し、文字Ｏはバック−オフ状態を表現し、文字Ｆは最終状態を表現する。図１８の（ｂ）は共有一様分布の有限状態表現であり、これが使用されて、バック−オフ確率が未知語（すなわち、図１８の（ａ）に示すような特定のｎ−グラム・モデルについてのトレーニング・データにおいて見られなかった語）に割り当てられる。

図１８の（ａ）に示すモデルのオペレーションを例示するため、語「ａ」の発声とその後に続く語「ｂ」の発声に関連付けられた確率を考察する。これは、以下の確率の組合せに対応する。
Ｐ（ａ｜＜ｓ＞）：ａ
Ｐ（ｂ｜ａ）：ｂ
Ｐｒ（＜／ｓ＞｜ｂ）

第１の確率は、語「ａ」が文開始シンボルの後に続くｎ−グラム確率である。これは、初期状態Ｉから状態ａへの遷移に対応する。第２の確率は、語「ｂ」が語「ａ」の後に続く確率であり、これは状態ａから状態ｂへの遷移においてラベル付けされる。第３の確率は、文終了シンボルが語「ｂ」の後に続く確率であり、これは状態ｂから有限状態Ｆへの遷移においてラベル付けされる。この一連の遷移は、有限状態マシンにおいて、発声「ａ ｂ」を受け入れる経路を形成し、この発声の確率を、この経路における遷移の確率を乗算することによって計算する。

トレーニング・データにおいて観測されない語シーケンスの発声では、有限状態マシンは０の確率をそれに割り当てない。その代わりに、経路は、バック−オフ状態を通じて、バック−オフ重みおよびユニグラム確率の積を、未知イベントのバイグラム確率として使用し、トラバースする。たとえば、発声「ａ ａ」の確率は、図１８の（ａ）において以下の経路を介して計算される。
Ｉ→ａ Ｐ（ａ｜＜ｓ＞）：ａ
ａ→Ｏ Ｂ（ａ）：ε
Ｏ→ａ Ｐ（ａ）：ａ
ａ→Ｆ Ｐ（＜／ｓ＞｜ａ）
ここで、バイグラム「ａ ａ」がトレーニング・データにおいて観測されないとしても、Ｐ（ａ｜ａ）＝Ｂ（ａ）＊Ｐ（ａ）＞０である。

モデリング中の特定のｎ−グラムについてのトレーニング・データにおいて未知である語の発声では、その語が語彙内にある場合、その語には、一様確率への確率バック−オフ１／｜Ｖ｜が割り当てられ、ただし｜Ｖ｜は語彙サイズである。以前のシステムでは、これは結果として、あらゆる未知語についてのバック−オフ状態Ｏ上の自己ループとなる。複合モデル内の各ｎ−グラムについてのトレーニング・データは比較的疎である可能性があるので、モデルに関連付けられた語彙における多数の語が、各ｎ−グラムについてのトレーニング・データにおいて未知となる。モデル３５１は例示的に、多数の語（例示的には数百）を有する語彙をサポートするようになるので、また、モデルも多数のｎ−グラム（これも例示的には数百）を有するようになるので、複合モデル全体におけるバック−オフ状態Ｏを通じた自己ループの数は非常に大きくなる。

したがって、本発明の１つの例示的実施形態によれば、各未知語についてのループを追加するのではなく、複合モデル３５１におけるｎ−グラム・モデル（図１８の（ａ）に示すものなど）は、バック−オフ状態Ｏを通じた単一のループ６２０［ＹＷ２］を含む。単一のループ６２０は、図１８の（ｂ）に示すような共有一様分布モデルを参照する。

図１８の（ｂ）に示す一様分布モデルでは、文字ｎは語彙内の語の数を指し、ただしｗ１は最初の語「ａ」を指し、ｗ２は第２の語「ｂ」を指すなどとなる。したがって、各未知語について、バック−オフ状態上をループするのではなく、モデルは、バック−オフ状態Ｏ上の一様分布によりラベルが付けられた自己ループによりほぼ平滑化される。図１８の（ｂ）に示す一様分布モデルは、複合モデル３５１におけるｎ−グラムのすべてについて共有される。各ｎ−グラムは単に、図１８の（ａ）に示すループ６２０に類似のループを有し、これは図１８の（ｂ）に示す一様分布モデルを参照する。これを図１８の（ｃ）に例示する。これは、モデル３５１における空間の相当の量を節約し、これを以前のシステムよりはるかにコンパクトにする。

このように、本発明の様々な実施形態は、プレターミナルについての統計モデル部を含むだけでなく、スロットを満たすためのルール・ベース文法部をも含み、この複合モデルは音声認識、または、音声認識および自然言語理解システムの組合せにおいて使用されることは理解されよう。これは実質的に、最適状態とは言えない２パスのシステムに関連する効率の悪さを低減し、また、言語モデルにおける以前の知識を含んで、言語モデル・トレーニング・データの不足を補う（すなわち、データの疎性に対処する）。この組み合わせた手法はまた、全体の理解エラー率も低減する。本発明のもう１つの実施形態はまた、ｎ−グラム・モデルを平滑化することであって、これを、ｎ−グラム・モデルにおいてバック−オフ状態に渡って自己ループを使用するのではなく、別のバック−オフ・モデル（一様分布モデルなど）を参照することによって行うことも含む。これはモデルのサイズを縮小し、よりコンパクトにする。

本発明を特定の実施形態を参照して説明したが、本発明の精神および範囲から逸脱することなく、形態および詳細において変更を行うことができることは、当業者には理解されよう。

本発明を使用することができる１つの例示的環境のブロック図である。 本発明の一実施形態によるモデル・オーサリング・コンポーネントの一実施形態のブロック図である。 スキーマの一実施例を例示する図である。 スキーマの実施例について生成されたルールのセットの一実施例を例示する図である。 注釈付き文の一実施例を例示する図である。 解析木の一実施例を例示する図である。 用例における語についての可能なプレターミナルの表を例示する図である。 関連付けられたカウントおよび確率を有する書き換えルールの表の図である。 文法オーサリング・コンポーネントをより詳細に示すブロック図である。 図３Ａに示す文法オーサリング・コンポーネントのオペレーションを例示する流れ図である。 本発明のもう１つの実施形態によるモデル・オーサリング・コンポーネントを例示する図である。 列挙された分節化の一実施例を示す図である。 本発明の一実施形態による統計モデルをより詳細に例示する図である。 簡易スキーマの一実施例の図である。 図７のスキーマから生成されたルールのセットの一実施例の図である。 注釈付き文の一実施例の図である。 生成されたルールを示す図である。 複合モデルのための状態図を例示する図である。 トレーニング技術を記述する擬似コードを示す図である。 本発明により生成されたモデルを使用するためのランタイム・システムを例示するブロック図である。 デコーダトレリスの一実施例を例示する図である。 音声認識システムの簡易ブロック図である。 図１７Ａ〜図１８に示す実施例において使用される、もう１つの簡易適用スキーマを例示する図である。 図１６に示すスキーマから生成された最上位文法に対応する隠れマルコフ・モデル（ＨＭＭ）構造を例示する図である。 図１７Ａからの「ＳｈｏｗＦｌｉｇｈｔ」モデルについてのＨＭＭ構造をより詳細に例示する図である。 図１７Ｂに示すＨＭＭ構造の使用を例示する図である。 （ａ）は、２つの観測語（ａ、ｂ）を有するバイグラム言語モデルの有限状態表現を例示し、（ｂ）は、（ａ）に示すバック−オフ状態上の一様分布をモデリングするモデルの有限状態表現を例示し、（ｃ）は、２つの観測語（ｃ、ｄ）を有するバイグラム言語モデルの有限状態表現を例示する図である。

符号の説明

２００ モデル・オーサリング・システム
２０２ モデル・オーサリング・コンポーネント
２０４ ユーザ・インターフェース
２０６ スキーマ
２０８ トレーニング用例テキスト文字列のセット
２０９ 文法ライブラリ
２１０ ルール・ベース文法
３００ テンプレート文法ジェネレータ
３０２ 文節化ＥＭ適用コンポーネント
３０４ プルーニング・コンポーネント
３２５ スロットについてのルール・ベース文法部
３２６ 統計モデル部
３４０ プレターミナルについての統計モデル・コンポーネント
３４２ コンポーネント
３４４ コンポーネント
３５０ モデル・オーサリング・コンポーネント
３５１ 複合モデル
４００ 自然言語入力文字列
４０２ 出力
５００ 音声認識システム
５０１ 話者
５０４ マイクロフォン
５０６ アナログ−デジタル（Ａ−Ｄ）コンバータ
５０７ フレーム・コンストラクタ
５０８ 特徴抽出器
５１２ デコーダ
５１４ レキシコン
５１８ 音響モデル
５２０ 信頼測定モジュール
５２２ 出力モジュール
５２４ トレーナ
５２６ トレーニング・テキスト

Claims (16)

1. 音声処理システムであって、
   音響モデルと、
   ルール・ベース・モデル部および統計モデル部を含む複合言語モデルと、
   前記音響モデルおよび前記複合言語モデルに結合され、自然言語音声入力の部分を、スキーマから導出されたプレターミナルおよびスロットに、前記音響モデルおよび前記複合言語モデルに基づいてマップするように構成されたデコーダと
   を備えることを特徴とする音声処理システム。
2. 前記デコーダは、前記自然言語音声入力の部分を前記スロットに、前記複合言語モデルの前記ルール・ベース・モデル部に基づいてマップするように構成されることを特徴とする請求項１に記載の音声処理システム。
3. 前記デコーダは、前記自然言語音声入力の部分を前記プレターミナルに、前記複合言語モデルの前記統計モデル部に基づいてマップするように構成されることを特徴とする請求項１に記載の音声処理システム。
4. 前記複合言語モデルの前記統計モデル部は、複数の統計ｎ−グラム・モデルを備え、１つの統計ｎ−グラム・モデルは各プレターミナルに対応することを特徴とする請求項１に記載の音声処理システム。
5. 前記複合言語モデルは語の語彙をサポートし、前記統計ｎ−グラム・モデルはトレーニング・データに基づいてトレーニングされ、前記語彙において、特定の統計ｎ−グラム・モデルをトレーニングするために使用されない語は、前記特定の統計ｎ−グラム・モデルについての未知語を備えることを特徴とする請求項４に記載の音声処理システム。
6. 前記複合言語モデルの前記統計モデル部は、バック−オフ・モデル部をさらに備え、これはアクセスされるとき、バック−オフ・スコアを前記語彙における語に割り当てるように構成されることを特徴とする請求項５に記載の音声処理システム。
7. 各統計ｎ−グラム・モデルは、すべての未知語についての前記バック−オフ・モデル部への参照を含むことを特徴とする請求項６に記載の音声処理システム。
8. 前記バック−オフ・モデル部は、一様スコアを前記語彙におけるあらゆる語に割り当てる、一様分布ｎ−グラムを備えることを特徴とする請求項７に記載の音声処理システム。
9. 前記ルール・ベース・モデル部は、文脈自由文法（ＣＦＧ）を備えることを特徴とする請求項１に記載の音声処理システム。
10. 音声処理中に確率を語仮説に割り当てる方法であって、
    語仮説を受信すること、
    複数の統計モデルおよび複数のルール・ベース・モデルを有する複合言語モデルにアクセスすること、
    前記語仮説が、前記ｎ−グラム・モデルのトレーニング中に知られた語に対応する場合、ｎ−グラム確率を、ｎ−グラム・モデルにより、前記語仮説に割り当てること、
    前記語仮説が、前記ｎ−グラム・モデルのトレーニング中に知られなかった語に対応する場合、前記語仮説のための別のバック−オフ・モデルを参照すること、および
    バック−オフ確率を、未知語に対応する各語仮説に、前記バック−オフ・モデルにより割り当てること
    を備えることを特徴とする方法。
11. 前記語仮説を、入力スキーマから導出されたスロットに、前記複合言語モデル内の前記ルール・ベース・モデルに基づいて、マップすることをさらに備えることを特徴とする請求項１０に記載の方法。
12. 前記語仮説を、前記入力スキーマから導出されたプレターミナルに、前記複合言語モデル内の前記ｎ−グラム・モデルおよび前記バック−オフ・モデルによって割り当てられた確率に基づいて、マップすることをさらに備えることを特徴とする請求項１１に記載の方法。
13. 前記別のバック−オフ・モデルを参照することは、一様分布ｎ−グラムを参照することを備えることを特徴とする請求項１２に記載の方法。
14. 前記バック−オフ確率を割り当てることは、一様分布スコアを前記語彙におけるあらゆる語に割り当てることを備えることを特徴とする請求項１３に記載の方法。
15. 音声認識システムにおいて使用するための複合言語モデルであって、
    入力音声信号の部分をスキーマから導出されたスロットにマップするためにアクセスされるルール・ベース・モデル部と、
    前記入力音声信号の部分を前記スキーマから導出されたプレターミナルにマップするためにアクセスされる統計モデル部と
    を備えることを特徴とする複合言語モデル。
16. 前記統計モデル部は、複数の統計ｎ−グラム・モデルを備え、１つの統計ｎ−グラム・モデルは各プレターミナルに対応することを特徴とする請求項１５に記載の複合言語モデル。
    

Images