(57)【要約】本発明は、弱く注釈付けされた文のトレーニングコーパス内の句に意味標識をマッピングし、それにより言語理解の目的のために未知の文に適用できる文法を生成するための方法、システムおよびコンピュータプログラムプロダクトに関する。本方法は、所与の句が候補となる意味標識の集合のうちのある意味標識にマッピングされる確率的推定に基づいている。マッピングおよび文法生成は、所与の句と候補となる意味標識の集合とのマッピング確率の集合の最大マッピング確率に従って実行される。特に、マッピング確率の決定は期待値最大化アルゴリズムを利用する。
2007513407.tif 000002
【特許請求の範囲】
【請求項１】
句に対して候補となる意味標識の集合のうちのある意味標識が割り当てられるマッピング確率を計算する方法であって、マッピング確率の前記計算が文のコーパスをなす句の集合に基づく統計的手順によって実行され、それぞれの句が候補となる意味標識の集合を割り当てられていることを特徴とする方法。
【請求項２】
それぞれの句について、マッピング確率の集合を計算し、その句に割り当てられている前記候補となる意味標識の集合の各意味標識についての確率を与えることをさらに有することを特徴とする、請求項１記載の方法。
【請求項３】
前記候補となる意味標識の集合のうち、マッピング確率の集合のうちで最高のマッピング確率をもつ一つの意味標識を決定し、その一つの意味標識を前記の句にマッピングすることをさらに有することを特徴とする、請求項２記載の方法。
【請求項４】
前記統計的手順が期待値最大化アルゴリズムを含むことを特徴とする、請求項１ないし３のうちいずれか一項記載の方法。
【請求項５】
未知の文または未知の句に適用可能な文法を導出するために、候補となる意味標識と句との間の実行されたマッピングをマッピングテーブルの形で保存することをさらに有することを特徴とする、請求項３または４記載の方法。
【請求項６】
句に対して候補となる意味標識の集合のうちのある意味標識が割り当てられるマッピング確率を計算するためのコンピュータプログラムであって、マッピング確率の前記計算が文のコーパスをなす句の集合に基づく統計的手順によって実行され、それぞれの句が候補となる意味標識の集合を割り当てられていることを特徴とするコンピュータプログラム。
【請求項７】
それぞれの句について、マッピング確率の集合を計算し、その句に割り当てられている前記候補となる意味標識の集合の各意味標識についての確率を与えるためのプログラム手段をさらに有することを特徴とする、請求項６記載のコンピュータプログラム。
【請求項８】
前記候補となる意味標識の集合のうち、マッピング確率の集合のうちで最高のマッピング確率をもつ一つの意味標識を決定し、その一つの意味標識を前記の句にマッピングするためのプログラム手段をさらに有することを特徴とする、請求項７記載のコンピュータプログラム。
【請求項９】
前記統計的手順が期待値最大化アルゴリズムを含むことを特徴とする、請求項６ないし８のうちいずれか一項記載のコンピュータプログラム。
【請求項１０】
未知の文または未知の句または未知の句のシーケンスに適用可能な文法を導出するために、意味標識と句または句のシーケンスとの間の実行されたマッピングをマッピングテーブルの形で保存するためのプログラム手段をさらに有することを特徴とする、請求項８または９記載のコンピュータプログラム。
【請求項１１】
句に意味標識をマッピングするためのシステムであって、句に対して候補となる意味標識の集合のうちのある意味標識が割り当てられるマッピング確率を計算するための手段を有しており、マッピング確率の前記計算が文のコーパスをなす句の集合に基づく統計的手順によって実行され、それぞれの句が候補となる意味標識の集合を割り当てられていることを特徴とするシステム。
【請求項１２】
それぞれの句について、マッピング確率の集合を計算し、その句に割り当てられている前記候補となる意味標識の集合の各意味標識についての確率を与える手段をさらに有することを特徴とする、請求項１１記載のシステム。
【請求項１３】
前記候補となる意味標識の集合のうち、マッピング確率の集合のうちで最高のマッピング確率をもつ一つの意味標識を決定し、その一つの意味標識を前記の句にマッピングする手段をさらに有することを特徴とする、請求項１１記載のシステム。
【請求項１４】
前記統計的手順が期待値最大化アルゴリズムを含むことを特徴とする、請求項１１ないし１３のうちいずれか一項記載のシステム。
【請求項１５】
未知の文または未知の句または未知の句のシーケンスに適用可能な文法を導出するために、意味標識と句または句のシーケンスとの間の実行されたマッピングをマッピングテーブルの形で保存するための手段をさらに有することを特徴とする、請求項１３または１４記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は対話アプリケーションのための自動化された言語理解の分野に関する。
【背景技術】
【０００２】
自動対話システムおよび電話ベースの機械質問システムは、今日、列車や飛行機の時刻表などのような情報を提供したり、あるいは銀行取引もしくは旅行予約などのようなユーザーからの問い合わせを受けたりするために幅広く広まっている。自動対話システムの決定的な務めは、典型的には発話によって提供されるユーザー入力から、当該対話システムにとって必要な情報を抽出することにある。
【０００３】
発話からの情報抽出は、一方での音声認識と、他方での認識された音声の意味論的な意味へのマッピングという二つのステップに分割できる。音声認識ステップはユーザーから受け取った発話の機械処理できる形への変換を提供する。その際、認識された発話が自動対話システムによって正しい仕方で解釈されることが本質的に重要である。したがって、自動対話システムは認識された発話の意味論的な意味への割り当てまたはマッピングを実行する必要がある。たとえば、列車時刻表対話システムにとっては、「ハンブルクからミュンヘンまでの接続便を必要としています」という問い合わせにおける二つの都市「ハンブルク」および「ミュンヘン」が、その列車の旅の出発地と目的地であると正しく同定することが必要である。
【０００４】
自動対話システムは、上記の文の本質的な断片「ハンブルクから」や「ミュンヘンまで」を抽出し、句「ハンブルクから」が出発地の意味標識にマッピングされ、一方で句「ミュンヘンまで」が目的地の意味標識にマッピングされる程度に理解しなければならない。出発地、目的地、時刻、日付またはその他の旅の細目がユーザーの問い合わせの句にマッピングされたとき、対話システムは要求される動作を実行することができる。
【０００５】
認識された句の意味標識へのマッピングの割り当ては典型的には何らかの種類の文法によって提供される。文法は意味標識の句へのマッピングを定義する規則を含んでいる。そのような規則をベースとした文法は自然言語理解の分野において最も調査がされている研究テーマであり続けてきたもので、しばしば実際の対話システムに組み込まれる。自動対話システムの例は自動対話システムの一般的な説明とともに、論文H.  Aust,  M.  Oerder,  F.  Seide,  V.  Steinbiss  “the  Philips  Automatic  Train  Timetable  Information  System”,  Speech  Communication  17  (1995)  249-262で与えられている。
【０００６】
自動対話システムは典型的には、時刻表情報または問い合わせ処理システムなどのような明確に区別された目的に指定されるので、基礎となる文法はそれら明確に区別される目的のために個別に設計される。従来技術において知られている文法のほとんどは、該文法を構成する規則が、対話に現れうる句および句のさまざまな組み合わせの膨大な集合をカバーするという意味において、手作業で書かれたものである。
【０００７】
句と意味標識との間のマッピングを実行するためには、前記の句または句の組み合わせが手作業で書かれた文法の規則の少なくとも一つに一致しなければならない。句のあらゆる可能な組み合わせまたは対話の変形を個別の規則によって明示的に取り入れなければならないため、そのような手作業で書かれた文法の生成はきわめて時間がかかり、リソースを浪費するプロセスである。さらに、基礎となる規則の集合は自動対話システムの運用の間に典型的に生じるあらゆる対話の種類および句の種類をカバーしていない可能性があるので、手作業で作成された文法は常にメンテナンスの対象である。
【０００８】
一般に、自動対話システムのための文法は用途に関係している。これはすなわち、自動対話システムのある明確に区別される種類には常に、明確に区別される文法が指定されるということを意味している。したがって、自動対話システムの各種類について、特別な文法が手作業で構築されなければならない。多数の異なる文法のそのような生成が、最小限にすべきコストのかなりの要因を表していることは明らかである。
【０００９】
文法の生成、メンテナンスおよび適応のためのかなり高価な手作業の努力の量を減らすべく、近年、文法の自動生成または文法の自動学習のための方法が導入された。文法の自動構築は典型的には弱く注釈付けされたトレーニング文のコーパスに基づいている。そのようなトレーニングコーパスはたとえば、既存のアプリケーションの対話のログを取ることによって導出できる。しかし、自動学習はさらに、トレーニングコーパスのどの句がどの既知の標識に割り当てられるかを示す注釈の集合を必要とする。典型的には、この注釈付けは手作業で実行しなければならないが、一般には文法全体を生成するよりは時間がかからない。
【００１０】
論文K.  Macherey,  F.  J.  Och  and  H.  Ney;  “Natural  Language  Understanding  using  Statistical  Machine  Translation”,  presented  at  the  7th  European  Conference  on  Speech  Communication  and  Technology,  Aalborg,  Denmark,  September  2001はURL“http://wasserstoff.informatik.rwth-aachen.de/Colleagues/och/eurospeech2001.ps”からも入手可能であるが、この論文が文法の自動学習を記載している。
【００１１】
実は前記文書は自然言語理解へのアプローチを開示しているが、これは統計的機械翻訳の分野から導かれるものである。自然言語理解の問題は、起点文から形式言語の目標文への翻訳として記述される。したがって、この方法は文法の利用を減らし、単語とその意味との間の依存関係を自動的に学習することに重きを置くことをねらいとしている。この限りにおいて、前述した方法が扱っているのは、文法の自動生成というよりは翻訳の問題である。
【００１２】
これに対し、米国特許出願US2003/0061024A1は明示的に文法の学習に集中している。この方法は、文のトレーニングコーパスにおいてある文法の、非終端記号に結び付けられた、終端記号または終端記号とワイルドカードのシーケンスを決定することに基づいている。終端記号または終端記号とワイルドカードのシーケンスが決定されたのち、それらは分類手順によってある非終端記号に割り当てられるか、あるいはどの非終端記号にも割り当てられないかする。この分類は今度は交換アルゴリズムに基づく交換手順を使う。交換アルゴリズムは、目標関数の効率的な最適化を保証する。これは、正しくないすべての分類を考慮に入れ、終端記号または終端記号とワイルドカードのシーケンスの分類において逐次的に最適化される。したがって、トレーニング文における非終端記号の順序は手作業で注釈付けする必要がない。目標関数が使うのは、トレーニング文の中に、終端記号または終端記号とワイルドカードのシーケンスのどれが、および非終端記号のどれが存在するかについての情報だけだからである。さらに、前記交換手順は目標関数の効率的な（局所的）最適化を保証する。交換実行に際して目標関数における変化を計算するためには若干の演算しか必要でないからである。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明は、意味標識を句にマッピングするための別の方法を提供し、それにより自動対話システムのための文法の生成を提供することをねらいとする。
【課題を解決するための手段】
【００１４】
本発明は、弱く注釈付けされたコーパスの文からの意味論的に有用な語句の自動学習を提供する。それにより語句と意味論的概念または意味標識との間の確率的な依存関係が推定される。確率的依存関係は、所与の句がある明確に区別される意味標識にマッピングされる、または割り当てられる尤度を記述する。このコンテキストでは、句というのは、文の断片、語のシーケンスあるいは最小の場合には単一の語を表す一般的な用語として使われている。
【００１５】
句と標識との間の確率的依存関係はさらにマッピング確率として表され、その決定はトレーニング文のコーパスに基づいて行われる。最初は、当該方法は標識とトレーニングコーパスの句との間の注釈について何らの情報ももっていない。マッピング確率の計算を実行するためには、句と意味標識との間の弱い注釈をどうにかして提供してやる必要がある。そのような弱い注釈はたとえば、一つの句にいくつかの候補となる意味標識を割り当てることによって実現できる。代替的に、IEL（inclusion/exclusion  list［包含／除外リスト］）を使うこともできる。IELというのは、ある句にマッピングできる、あるいはマッピングしてはならないさまざまな意味標識を含めたり、除外したりするリストを表す。
【００１６】
本発明のある好ましい実施形態によれば、トレーニングコーパスのそれぞれの句について、句とそれに対応する候補となる意味標識の集合との間のマッピング確率の全体集合が決定される。このようにして、所与の句がある意味標識に割り当てられる確率が、前記の句と候補となる意味標識の前記全体集合との間の可能な各組み合わせについて計算され、これが文法の自動学習または自動生成を与える。
【００１７】
本発明のあるさらなる好ましい実施形態によれば、トレーニングコーパスの句へのある意味標識のマッピングが、マッピング確率の集合の最高のマッピング確率に基づいて行われる。これは、トレーニングコーパスの所与の句へのある標識のマッピングまたは割り当てが前記所与の句についてのマッピング確率の集合の最高確率によって決定されるということを意味している。
【００１８】
句に意味標識をマッピングするための前記方法は、したがって、マッピング確率の決定を明示的に利用する。そのようなマッピング確率はたとえば、トレーニングコーパスの句と意味標識との間の前記所与の弱い注釈から決定できる。一般に、そのようなマッピング確率を生成するための複数の確率的手段が存在する。
【００１９】
本発明のあるさらなる好ましい実施形態によれば、統計的手順、よってマッピング確率の計算は、期待値最大化（expectation  maximization）（EMアルゴリズム）によって実行される。EMアルゴリズムは一般に、隠れマルコフモデル（HMM:  Hidden  Markov  Models）についての前向き・後ろ向きトレーニング（forward  backward  training）から知られる。マッピング確率の計算のためのEMアルゴリズムの具体的な実装は数学的補遺で与えてある。
【００２０】
本発明のあるさらなる好ましい実施形態によれば、文法は、候補となる意味標識と句との間の実行されたマッピングから導き出すことができる。好ましくは、計算上の努力を定レベルに保つため、計算され、実行されたマッピングは何らかの種類の保存手段によって保存される。最後に、導き出された文法は新規の未知の文に適応されることができる。
【００２１】
本発明の方法の全体としてのパフォーマンスは、EMアルゴリズムが反復的に適用されるときに向上させられる。この場合、EMアルゴリズムのある反復工程の結果は次の反復工程のための入力として使われる。たとえば、ある句がある標識にマッピングされる推定確率が何らかの種類の保存手段によって保存され、次いでEMアルゴリズムの次の適用において再利用されうる。同様な仕方で、句と標識との間の弱い注釈の形の、あるいはIELの形の初期条件は、EMアルゴリズムに基づいて以前に実行されたマッピング手順に従って修正されうる。
【００２２】
文法学習のためのEMベースのアルゴリズムの効率および信頼性を試験するため、EMベースのアルゴリズムを、いわゆるボストンレストランガイド・コーパスを使って実装した。この実装に基づく実験により、EMベースの手順が米国特許第2003/0061024A1号において示されているような交換アルゴリズムに基づく手順よりも良好な結果に導くことが立証された。特に、大きなトレーニングコーパスを使った場合はそうである。さらに、EMベースの手順の反復適用は、生成される文法の連続的な改善につながることが立証された。誤ってマッピングされた標識と標識総数の比として定義される標識誤り率は、反復回数に対する関数として記述したとき単調減少を示す。標識誤り率の主要な改善は、反復工程２回、あるいは１回後でさえすでに到達されている。
【００２３】
以下では、図面を参照しながら本発明の好ましい実施形態についてより詳細に述べる。
【発明を実施するための最良の形態】
【００２４】
図１は、EMアルゴリズムに基づいて意味標識を句にマッピングするためのフローチャートを示している。第一のステップ１００では、トレーニングコーパスの文から句￣wが抽出される。続くステップ１０２は、無順序の標識リストκからの各標識kについて確率p(k,w)をマッピングするステップである。
【００２５】
ひとたび句￣wについてマッピング確率の集合が計算されたら、マッピング確率p(k,w)の集合の最高確率が次のステップ１０４で決定される。次のステップ１０６では、句￣wと意味標識kとの間のマッピングが実行される。句￣wは、ステップ１０４で決定されたマッピング確率の集合の最高確率p(k,w)に従って単一の標識kにマッピングされる。このようにして、意味標識kと句￣wとの間のマッピングが、トレーニングコーパスに基づく確率的推定を使用することによって実行される。確率的推定は、意味標識kがトレーニングコーパス中の句￣wにマッピングされる尤度を決定する。ステップ１０６でマッピングが実行されたとき、該実行されたマッピングを当該アルゴリズムのその後の適用に提供するため、ステップ１０８で何らかの種類の保存手段によって実行されたマッピングが保存される。このようにして、当該手順は反復的に実行でき、標識誤り率の低下に、したがって文法学習手順全体の信頼性および効率の向上につながる。
【００２６】
ステップ１０２で実行されるマッピング確率の計算はEMアルゴリズムに基づいている。これは数学的補遺において図２および図３を参照することによって明示的に説明される。
【００２７】
EMアルゴリズムによるマッピング確率の計算は、L(i,κ′)およびR(i,κ′)と記される二つの追加的な確率に基づいている。これはそれぞれあるトレーニングコーパス文の、左の部分文にわたる長さi−1の無順序の標識部分リストκ′と、位置i＋1からの右の部分文にわたる相補的な無順序の標識部分リストとのあらゆる順列についての確率を表している。
【００２８】
図２は、確率L(i,κ′)を計算するためのフローチャートを示している。
【００２９】
第一のステップ２００では、i＝0についての初期確率は1にセットされ、それから次のステップ２０２で標識部分リストの添え字iがi＝1に初期化される。続くステップ２０４では、長さiの各部分リストが無順序の標識部分リストκ′から選択される。各部分リストを選択したのち、計算手順はステップ２０６に続き、ここである順列についての確率がL(i,κ′)＝0と0にセットされる。次いで、ステップ２０８では、無順序の部分リストからの各標識kがステップ２０８で選択され、逐次的にステップ２１０に与えられる。そこで順列確率が次式に従って計算される。
【００３０】
L(i,κ′)＝L(i,κ′)＋L(i−1，κ′＼{k})・p(k|￣wi)
L(i,κ′)の計算後、ステップ２１２で添え字iが句￣W中の語数と比較される。iが|￣W|以下であれば、手順はiを1インクリメントしてステップ２０４に戻る。その他の場合、iが|￣W|より大きい場合には、順列確率を計算するための手順はステップ２１４で終了する。
【００３１】
ひとたび図２に記載されている手順によって順列確率が計算されたら、右の部分文の相補的な部分リストについての順列確率Rを得るために類似の計算が実行される。
【００３２】
最後に図３が、上記した順列確率を使うことによってマッピング確率~p(k,￣w)を計算するためのEMアルゴリズムの実装を示している。
【００３３】
第一のステップ３００では、すべての標識kおよび句wについて確率p(k|￣w)が、~q＝0とセットし、~q(k,￣w)＝0とセットすることによって初期化される。それからステップ３０２においてトレーニングコーパスの文の一つが選択される。トレーニングコーパスのあらゆる文が文法学習のために考慮に入れられるので、続くステップ３０４はトレーニングコーパスのすべての文に適用されなければならない。
【００３４】
トレーニングコーパスの文がステップ３０２で選択されたのち、それはステップ３０４でさらに処理される。ステップ３０４の中ではステップ３０６、３０８、３１０、３１２が逐次的に実行される。ステップ３０６では無順序の標識リストκ′が順序付けられた句リスト￣Wとともに選択される。次のステップ３０８では、前記テーブルLの動的プログラミング（dynamic  programming）構築が図２で記載されたように実行される。その後、ステップ３１０で反転したテーブルRを用いて同様の手順が実行される。
【００３５】
計算されたテーブルLおよびRならびに初期化された確率はさらにステップ３１２において処理される。ステップ３１２は、添え字i＝1、i≦|W|についてのネストされたループとして解釈できる。各iについてステップ３１４が実行され、長さi−1の無順序の部分リストκのそれぞれについて別のループを初期化する。無順序の各部分リストについてステップ３１６が実行され、κ′の要素でない各標識kを選択し、ステップ３１８で次の計算を実行する：
【００３６】
【数１】
2007513407.tif 000003
ここで、左辺はステップ３２０でさらに次式によって処理される：
【００３７】
【数２】
2007513407.tif 000004
ステップ３１６においてステップ３１８と３２０がκ′の要素でない各標識kについて実行されたときで、ステップ３１４において長さi−1の無順序の各部分リストについてステップ３１６が実行されたときで、ステップ３１２において各添え字i≦|￣W|についてステップ３１４が実行されたときで、最後にトレーニングコーパスのそれぞれの文についてステップ３１２によって与えられる手順全体が実行されたとき、ステップ３２２においてマッピング確率が次式に従って決定される。
【００３８】
【数３】
2007513407.tif 000005
ひとたびマッピング確率が決定されたら、それは好ましくは何らかの保存手段によって保存される。文法学習の目的のため、および所与の句に標識をマッピングするため、句および候補となる意味標識のあらゆる可能な組み合わせのあらゆる確率が計算され、保存される。最後に、所与の句への意味標識のマッピングが、該所与の句についてのあらゆる計算された確率の最大確率に従って実行される。
【００３９】
前記の複数の実行されたマッピングに基づき、文法が最終的に演繹され、自動化された対話システムの枠組みにおいて生起しうる他の、よって未知の文に適用されることができる。
【００４０】
EMアルゴリズムが反復して文のトレーニングコーパスに適用されるときには特に、文法学習手順の全体としての効率は上昇し、標識誤り率は低下する。
数学的補遺
本発明の好ましい実施形態によれば、所与の句￣wが意味標識kにマッピングされるマッピング確率~p(k,￣w)は期待値最大化（EM）アルゴリズムによって計算される。このセクションではEMアルゴリズムの実装および適応について述べる。
【００４１】
ここで、HMMの前向き・後ろ向きトレーニングと同様のアプローチがとられる。EMに基づく文法学習のための一般的な式は次式によって与えられる：
【００４２】
【数４】
2007513407.tif 000006
ここで、Wは句のシーケンス、Kは標識のシーケンス、￣w〔バー付きのw〕は句、kは意味標識、NK(k,￣w)は所与のWおよびKについてkと￣wとが生起する生起数であり、p(K|W)は句のシーケンスWが標識のシーケンスKにマッピングされる確率を与える。
【００４３】
このアプローチは、標識の数sが句の数に等しいことを前提としている。式（１）の分子
【００４４】
【数５】
2007513407.tif 000007
は、標識シーケンスKそれぞれについて、該標識シーケンス中の句￣wに標識kがマッピングされるのと同じ回数だけ確率p(K|W)を加算するものである。これは次のように書き直すことができる：
【００４５】
【数６】
2007513407.tif 000008
ここで、δ(x,y)は通常のデルタ関数で、
δ(x,y)＝1      x＝yの場合
δ(x,y)＝0      その他の場合
であり、p(ki＝k|W)は句のシーケンスWの中で位置iにある句￣wが標識kにマッピングされる全体としての確率である。同様に、式（１）の分母については、次式が成り立つ：
【００４６】
【数７】
2007513407.tif 000009
この結果、次の推定公式が得られる。
【００４７】
【数８】
2007513407.tif 000010
コーパス全体にわたる推定のため、分子と分母は別々に計算され、各コーパス文について合計される。
【００４８】
式（１）の中心である確率p(ki＝k|W)は、位置iの句に対して標識kをもつあらゆる標識シーケンスの確率を計算する。位置iの前および後では、残りのあらゆる標識の順列が可能である。κが無順序の標識のリストであり、π(κ)がκ上でのあらゆる可能な順列の集合であるとすると、次のようになる：
【００４９】
【数９】
2007513407.tif 000011
L(i−1,κ′)は、位置i−1までの左の部分文にわたる長さi−1の無順序の標識部分リストκ′のあらゆる順列の確率であり、R(i＋1，(κ＼κ′)＼{k})は、位置i＋1からの右の部分文にわたる長さs−iの無順序の相補的な標識部分リスト(κ＼κ′)＼{k}のあらゆる順列の確率である。これらの値は再帰的に計算できる：
【００５０】
【数１０】
2007513407.tif 000012
同様に、
【００５１】
【数１１】
2007513407.tif 000013
式（３）および（４）の値L(i,κ′)およびR(i,κ′)を保存して再利用することにより計算コストが削減される。所与のiについて、無順序の標識リストκ′は|κ|Ci通りあり、よって、テーブルLを完全に計算するには実行すべき演算はΣ|κ|Ci・i〔和はi＝1から|κ|−1まで〕回である（同じことがテーブルRについても成り立つ）。しかし、これについての閉じた形またはよい推定は見つかっておらず、そのためこの計算が、多項式計算時間であるという意味で効率的でないかどうかははっきりしない。
【００５２】
前記EMアルゴリズムの実装は、上述した表式からの直接の帰結である。その実装について、図２および図３によって１反復工程についてさらに説明する。その実装についていくつかの注記がある。
【００５３】
技術的な理由で、無順序の標識リストκの各要素は1から|κ|の範囲の一意的な添え字を与えられる。長さiの無順序の部分リストκ′はi次元ベクトルとして表現されるが、そのスカラー要素はκ′を構成するκの要素の添え字である。このベクトルは、長さiの無順序の部分リストκ′のすべてを順次得るために、次のようにインクリメントされる。
【００５４】
【数１２】
2007513407.tif 000014
長さiの何らかの無順序の部分リストκ′についてのL(i,  κ′)を取り出すのは、L(i,  κ′)＝L(α)となる添え字αをκ′のベクトル表現から
【００５５】
【数１３】
2007513407.tif 000015
によって計算することによって実現される。ここで、ajはκ′のベクトル表現のj番目の要素である。κ′への標識の追加やκ′からの標識の除去はその標識の添え字に反映される。R(i，(κ＼κ′)＼{k})＝R(β)を取り出すために必要とされる相補的な無順序の標識リストの添え字βは
【００５６】
【数１４】
2007513407.tif 000016
によって容易に計算される。
【００５７】
より高速な計算のため、j番目の項目が2jの値を含んでいるテーブルがある。
【００５８】
リストRの動的プログラミング計算は、リストLを計算するための動的プログラミングを使ったサブルーチンを、句の順序を反転させた、すなわち
【００５９】
【数１５】
2007513407.tif 000017
となる句のシーケンス￣W′を用いて呼び出すことによって実行される。
【００６０】
標識と句の数が等しくない文は破棄される。
【００６１】
初期確率p(k,￣w)はファイルから読み込まれ、p(￣w)はp(k|￣w)についての境界値として計算される。前記ファイルは単にk、￣w、p(k,￣w)をアスキー行１行にリストするだけのものである。推定された確率~p(k,￣w)は同じフォーマットで書き込まれ、こうして次の反復工程のための入力としてはたらくことになる。
【００６２】
図２は、位置iまでの左の部分文にわたる長さiの無順序の標識部分リストκ′のあらゆる順列について確率L(i−1,κ′)を逐次的に計算するためのフローチャートを示している。
【００６３】
最初に、ステップ２００で確率L(0,{})が1にセットされ、それからステップ２０２で添え字iがi＝1にセットされる。
【００６４】
ステップ２０４では、ループが開始され、長さiの無順序の各部分リストκ′が選択される。続くステップ２０６では、選択された無順序の各部分リストについての確率がL(i,κ′)＝0と0にセットされる。それから次のステップ２０８では、前記無順序の部分リストの要素である各標識kが選択される。ステップ２１０で最終的に、確率L(i,κ′)が次式に従って計算される。
【００６５】
L(i,κ′)＝L(i,κ′)＋L(i−1，κ′＼{k})・p(k|￣wi)
ステップ２１２では、添え字iが句の中の語数以下であるかどうかが調べられる。ステップ２１２でi≦|￣W|であれば、iを1インクリメントして手順はステップ２０４に戻る。これに対し、i＞|￣W|であれば、手順はステップ２１４で停止する。
【００６６】
位置i＋1からの右の部分文の無順序の相補的な部分リストのあらゆる順列についての確率も、同様にして計算が実行される。
【００６７】
図３は、EMアルゴリズムに基づいてマッピング確率~p(k,￣w)を計算するためのフローチャートを示している。ステップ３００では、すべての標識kおよび句wについて確率p(k|￣w)が、~q＝0とセットし、~q(k,￣w)＝0とセットすることによって初期化される。それからステップ３０２においてトレーニングコーパスの文の一つが選択される。トレーニングコーパスのあらゆる文が文法学習のために考慮に入れられるので、続くステップ３０４はトレーニングコーパスのすべての文に適用されなければならない。
【００６８】
トレーニングコーパスの文がステップ３０２で選択されたのち、それはステップ３０４でさらに処理される。ステップ３０４の中ではステップ３０６、３０８、３１０、３１２が逐次的に適用される。ステップ３０６では無順序の標識リストκ′が順序付けられた句リスト￣Wとともに選択される。次のステップ３０８では、前記テーブルLの動的プログラミング（dynamic  programming）構築が図２で記載されたように実行される。その後、ステップ３１０で反転したテーブルRを用いて同様の手順が実行される。
【００６９】
計算されたテーブルおよび初期化された確率はさらにステップ３１２において処理される。ステップ３１２は、添え字i＝1、i≦|W|についてのネストされたループとして解釈できる。各iについてステップ３１４が実行され、長さi−1の無順序の部分リストκ′のそれぞれについて別のループを初期化する。無順序の各部分リストについてステップ３１６が実行され、κ′の要素でない各標識kを選択し、ステップ３１８で次の計算を実行する：
【００７０】
【数１６】
2007513407.tif 000018
ここで、左辺はステップ３２０でさらに次式によって処理される：
【００７１】
【数１７】
2007513407.tif 000019
ステップ３１６においてステップ３１８と３２０がκ′の要素でない各標識kについて実行されたときで、ステップ３１４において長さi−1の無順序の各部分リストについてステップ３１６が実行されたときで、ステップ３１２において各添え字i≦|￣W|についてステップ３１４が実行されたときで、最後にトレーニングコーパスのそれぞれの文についてステップ３１２によって与えられる手順全体が実行されたとき、ステップ３２２においてマッピング確率が次式に従って決定される。
【００７２】
【数１８】
2007513407.tif 000020
【図面の簡単な説明】
【００７３】
【図１】EMに基づくアルゴリズムによる句と標識のマッピングのためのフローチャートを示す図である。
【図２】EMアルゴリズムのためのサブルーチンであるテーブルLの動的プログラミング構築を示すフローチャートを示す図である。
【図３】EMアルゴリズムの実装を記述するフローチャートを示す図である。
【図１】
2007513407.tif 000021
【図２】
2007513407.tif 000022
【図３】
2007513407.tif 000023
【国際調査報告】
2007513407.tif 000024
2007513407.tif 000025
2007513407.tif 000026