(57)【特許請求の範囲】
【請求項１】
少なくとも一文を含む入力文書に対して複数種類の自然言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置であって、
前記複数種類の自然言語解析処理の各々について、前記入力文書に対して前記自然言語解析処理を行う問題を、前記自然言語解析処理について予め定義した文字単位以上の単位の問題である部分問題に分解して、前記部分問題の集合を生成する部分問題生成手段と、
前記自然言語解析処理を行うＳ個（Ｓは２以上の自然数である）の計算ノードと、
前記部分問題生成手段によって生成された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当てるグループ作成手段と、を含み、
前記Ｓ個の計算ノードの各々は、
前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新する部分解更新手段と、
前記部分解更新手段によって更新された前記部分集合の各部分問題の解を、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記部分集合の各部分問題の解を取得する同期手段と、
前記同期手段によって取得した前記他の計算ノードの前記部分集合の各部分問題の解と、前記部分解更新手段によって更新された前記部分集合の各部分問題の解とに基づいて、各部分問題について、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータを更新する制約条件更新手段と、
前記制約条件パラメータの値が収束したか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、前記部分解更新手段による更新、前記同期手段による通知及び取得、並びに前記制約条件更新手段による更新を繰り返す収束判定手段と
を含む自然言語解析処理装置。
【請求項２】
前記部分解更新手段は、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の部分集合について、前回更新されたラグランジュ未定乗数、前記部分集合の各部分問題の解、及び前記制約条件パラメータを用いて、予め定められた目的関数の値を最適化するように、前記ラグランジュ未定乗数を更新し、前記更新された前記ラグランジュ未定乗数を用いて、前記目的関数の値を最適化するように、前記部分集合の各部分問題の解を更新し、
前記同期手段は、前記部分解更新手段によって更新された前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解を、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解を取得し、
前記制約条件更新手段は、前記同期手段によって取得した前記他の計算ノードの前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解、並びに前記部分解更新手段によって更新された前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解に基づいて、前記目的関数の値を最適化するように、各部分問題について、前記制約条件パラメータを更新する請求項１記載の自然言語解析処理装置。
【請求項３】
少なくとも一文を含む入力文書に対して複数種類の自然言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置であって、
前記複数種類の自然言語解析処理の各々について、前記入力文書に対して前記自然言語解析処理を行う問題を、前記自然言語解析処理について予め定義した文字単位以上の単位の問題である部分問題に分解して、前記部分問題の集合を生成する部分問題生成手段と、
前記自然言語解析処理を行うＳ個（Ｓは２以上の自然数である）の計算ノードと、
前記部分問題生成手段によって生成された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当てるグループ作成手段と、
制約条件更新手段と、収束判定手段と、を含み、
前記Ｓ個の計算ノードの各々は、
前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新する部分解更新手段と、を含み、
前記制約条件更新手段は、各計算ノードの前記部分解更新手段によって更新された前記部分集合の各部分問題の解に基づいて、各部分問題について、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータを更新し、
前記収束判定手段は、前記制約条件パラメータの値が収束したか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、各計算ノードの前記部分解更新手段による更新、及び前記制約条件更新手段による更新を繰り返す
自然言語解析処理装置。
【請求項４】
前記部分解更新手段は、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の部分集合について、前回更新されたラグランジュ未定乗数、前記部分集合の各部分問題の解、及び前記制約条件パラメータを用いて、予め定められた目的関数の値を最適化するように、前記ラグランジュ未定乗数を更新し、前記更新された前記ラグランジュ未定乗数を用いて、前記目的関数の値を最適化するように、前記部分集合の各部分問題の解を更新し、
前記制約条件更新手段は、各計算ノードの前記部分解更新手段によって更新された前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解に基づいて、前記目的関数の値を最適化するように、各部分問題について、前記制約条件パラメータを更新する請求項３記載の自然言語解析処理装置。
【請求項５】
部分問題生成手段、Ｓ個（Ｓは２以上の自然数である）の計算ノード、及びグループ作成手段を含み、少なくとも一文を含む入力文書に対して複数種類の自然言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置における自然言語解析処理方法であって、
前記部分問題生成手段によって、前記複数種類の自然言語解析処理の各々について、前記入力文書に対して前記自然言語解析処理を行う問題を、前記自然言語解析処理について予め定義した文字単位以上の単位の問題である部分問題に分解して、前記部分問題の集合を生成し、
前記グループ作成手段によって、前記部分問題生成手段によって生成された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当て、
前記Ｓ個の計算ノードによって、前記自然言語解析処理を行い、
前記Ｓ個の計算ノードの各々によって前記自然言語解析処理を行うことは、
部分解更新手段によって、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新し、
同期手段によって、前記部分解更新手段によって更新された前記部分集合の各部分問題の解を、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記部分集合の各部分問題の解を取得し、
制約条件更新手段によって、前記同期手段によって取得した前記他の計算ノードの前記部分集合の各部分問題の解と、前記部分解更新手段によって更新された前記部分集合の各部分問題の解とに基づいて、各部分問題について、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータを更新し、
収束判定手段によって、前記制約条件パラメータの値が収束したか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、前記部分解更新手段による更新、前記同期手段による通知及び取得、並びに前記制約条件更新手段による更新を繰り返すことを含む
自然言語解析処理方法。
【請求項６】
前記部分解更新手段は、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の部分集合について、前回更新されたラグランジュ未定乗数、前記部分集合の各部分問題の解、及び前記制約条件パラメータを用いて、予め定められた目的関数の値を最適化するように、前記ラグランジュ未定乗数を更新し、前記更新された前記ラグランジュ未定乗数を用いて、前記目的関数の値を最適化するように、前記部分集合の各部分問題の解を更新し、
前記同期手段は、前記部分解更新手段によって更新された前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解を、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解を取得し、
前記制約条件更新手段は、前記同期手段によって取得した前記他の計算ノードの前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解、並びに前記部分解更新手段によって更新された前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解に基づいて、前記目的関数の値を最適化するように、各部分問題について、前記制約条件パラメータを更新する請求項５記載の自然言語解析処理方法。
【請求項７】
部分問題生成手段、Ｓ個（Ｓは２以上の自然数である）の計算ノード、グループ作成手段、制約条件更新手段、及び収束判定手段を含み、少なくとも一文を含む入力文書に対して複数種類の自然言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置における自然言語解析処理方法であって、
前記部分問題生成手段によって、前記複数種類の自然言語解析処理の各々について、前記入力文書に対して前記自然言語解析処理を行う問題を、前記自然言語解析処理について予め定義した文字単位以上の単位の問題である部分問題に分解して、前記部分問題の集合を生成し、
前記グループ作成手段によって、前記部分問題生成手段によって生成された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当て、
前記Ｓ個の計算ノードによって、前記自然言語解析処理を行い、
前記制約条件更新手段によって更新し、
前記収束判定手段によって判定することを含み、
前記Ｓ個の計算ノードの各々によって前記自然言語解析処理を行うことは、
部分解更新手段によって、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新することを含み、
前記制約条件更新手段は、各計算ノードの前記部分解更新手段によって更新された前記部分集合の各部分問題の解に基づいて、各部分問題について、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータを更新し、
前記収束判定手段は、前記制約条件パラメータの値が収束したか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、各計算ノードの前記部分解更新手段による更新、及び前記制約条件更新手段による更新を繰り返す
自然言語解析処理方法。
【請求項８】
コンピュータを、請求項１〜請求項４の何れか１項記載の自然言語解析処理装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自然言語解析処理装置、方法、及びプログラムに係り、特に、入力文書に対して複数段階の言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
自然言語とは、日本語や英語など人間が通常使う言語のことである。自然言語で記述された文書を文法や意味的に解析する技術は、例えば、その言語の成り立ちや構造を理解するという言語学的な観点で学術的に重要な意義がある。また近年では、人間が生成した文書を、文法・意味的に自動で解析し、その結果を利用して提供する様々なサービスが、主にweb上で展開されるようになってきた。例えば、翻訳サイト、人や商品の評判分析サイト、ある特定の事象に対する要約サイトなどのサービスが、これに相当する。これらのサービスでは、人間が生成した電子化文書を、システム内部で文法、意味的に解析し、それらを利用する形で実際のサービスを提供する形になる。その意味で、自然言語を文法、意味的に解析する技術は、これらサービスの根幹の技術であり、情報処理分野でも非常に重要な位置を占めるようになった。
【０００３】
一概に自然言語を解析するといっても、単語区切りや品詞推定といった表層的な解析から、語や節間の係り受け関係の推定といったより高度な解析を行うものまで含まれる。例えば、文書から文の区切りを推定する「文区切り」、単語の区切りを推定する「単語区切り」、単語の品詞を推定する品詞付与、単語や節間の関係を推定する係り受け解析などがある。これらの例を図８に示す。
【０００４】
品詞付与や係り受け解析といった言語解析問題は、「相互依存性」がある問題に分類される。これは、例えば、単語の品詞を決定する問題では、ある単語の品詞を決定する際には、前後や周辺の品詞によって対象とする単語に付与すべき品詞が決まる関係があり、また、その前後や周辺の品詞も、その前後や周辺の品詞に依存して決まる問題である。仮に、ある品詞Aの後に、品詞Bは出現してはいけないという規則が存在する場合、個々の単語の品詞を独立に推定してしまうと、この規則を満たした結果が得られる保証が無い。つまり、個々単語の品詞を独立に推定した場合はこういった全体としての整合性がとれるとは限らないため、文書全体として最も良い品詞列を探索する問題になっている。特に、文区切り、単語区切り、品詞推定、係り受け解析といった問題を一括して解くことを考えると、とても複雑に絡みあった問題となっているため、最もよい出力を探索する問題は非常に難しい問題であると言える。
【０００５】
これらの問題を解くために、履歴ベースの逐次解析法(いわゆるstack decoding)、動的計画法、整数計画法などのアルゴリズムを使って出力を推定する方法が広く使われている（非特許文献１〜非特許文献３）。
【０００６】
履歴ベースの逐次解析法は、直前までの推定結果を利用して次の推定を行う方法である（図９参照）。独立に問題を解く方法に比べて、出力の整合性を保つことが可能である。ただし、直前までの解析結果を信じて次の解析結果を決定する方法であるため、直前の解析結果に誤りがあった場合には、その誤りに従った解析を続けてしまい、間違いの伝播が起こる、という問題が知られている。
【０００７】
その問題を解決する方法として、動的計画法に基づく方法（図１０参照）や整数計画法に基づく方法が使われるようになった。これは、全体として最もよい出力を選ぶ方法となっているため、履歴ベースの逐次解析法に比べて途中の解析誤りといった問題が発生しない。一方で、全体として最もよい出力を選ぶための計算量は、逐次解析法に比べると非常に大きくなるといった欠点もある。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Joakim Nivre. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 2008.
【非特許文献２】F. Sha and F. Pereira. Shallow Parsing with Conditional Random Fields. Proc. of HLT/NAACL, 2003.
【非特許文献３】Dan Roth, Wen-tau Yih Global Inference for Entity and Relation Identification via a Linear Programming Formulation Introduction to Statistical Relational Learning, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
例えば、日本語の文書に対して、単語区切り、文節区切り、文区切り、品詞付与（辞書引き）、文節間係り受け関係付与を一括して行うシステムを想定する。こういった文書の文法・意味的な解析結果を使ったサービスとして、web上での人物や商品の評判を分析するサイトや、翻訳サイトなどが考えられる。
【００１０】
こういったシステムでは、通常全ての処理を一括で行うのは複雑であるため、従来は、1、文区切り、2、単語区切り+品詞付与(一般に形態素解析と呼ばれる)、3、文節区切り、4、係り受け解析、というような順番で処理を段階的に適用して処理を行う。つまり、各段階の処理は、前段階の処理結果を入力として受け取り処理を行う。こういった逐次的に処理を行う方法を一般的に「パイプライン方式」とよぶ。よって、ここでも各段階の処理を次の段階の処理の入力として扱う従来法を「パイプライン方式」と呼ぶ。パイプライン方式は、前段階の処理結果に誤りがあった場合、その誤りを修正する枠組みは存在しないため、その誤りにより後の解析を間違えるという誤りの伝播が発生しやすい、という問題がある。また、各処理の段階にまたがって利用できる情報を考慮して解析システムを運用することは困難である。実際にこういった複合的な情報を利用することで、解析精度を向上させることが可能であることが多いため、パイプライン方式の欠点と考えられる。これらは、一つの段階において履歴ベースの逐次解析法で見られる欠点と同じ原因である。
【００１１】
つまり、個々の段階の処理に動的計画法や整数計画法のような全体最適化法を利用していたとしても、結局のところパイプライン処理による部分で履歴ベースの逐次解析法と同じ欠点が発生してしまう。
【００１２】
もちろん動的計画法や整数計画法のような全体最適化を行う方法を、このような複数の解析を同時に行うシステムに適用することは可能である。ただし、あまりにも計算量が大きくなりすぎて、実用上はそのまま適用するのは困難となる。
【００１３】
本発明は、上記の事情を鑑みてなされたもので、計算量の増大を抑制して、精度よく自然言語解析処理を行うことができる自然言語解析処理装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記の目的を達成するために第１の発明に係る自然言語解析処理装置は、少なくとも一文を含む入力文書に対して複数種類の自然言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置であって、前記複数種類の自然言語解析処理の各々について、前記入力文書に対して前記自然言語解析処理を行う問題を、前記自然言語解析処理について予め定義した文字単位以上の単位の問題である部分問題に分解して、前記部分問題の集合を生成する部分問題生成手段と、前記自然言語解析処理を行うＳ個（Ｓは２以上の自然数である）の計算ノードと、前記部分問題生成手段によって生成された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当てるグループ作成手段と、を含み、前記Ｓ個の計算ノードの各々は、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新する部分解更新手段と、前記部分解更新手段によって更新された前記部分集合の各部分問題の解を、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記部分集合の各部分問題の解を取得する同期手段と、前記同期手段によって取得した前記他の計算ノードの前記部分集合の各部分問題の解と、前記部分解更新手段によって更新された前記部分集合の各部分問題の解とに基づいて、各部分問題について、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータを更新する制約条件更新手段と、前記制約条件パラメータの値が収束したか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、前記部分解更新手段による更新、前記同期手段による通知及び取得、並びに前記制約条件更新手段による更新を繰り返す収束判定手段とを含んで構成されている。
【００１５】
第２の発明に係る自然言語解析処理方法は、部分問題生成手段、Ｓ個（Ｓは２以上の自然数である）の計算ノード、及びグループ作成手段を含み、少なくとも一文を含む入力文書に対して複数種類の自然言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置における自然言語解析処理方法であって、前記部分問題生成手段によって、前記複数種類の自然言語解析処理の各々について、前記入力文書に対して前記自然言語解析処理を行う問題を、前記自然言語解析処理について予め定義した文字単位以上の単位の問題である部分問題に分解して、前記部分問題の集合を生成し、前記グループ作成手段によって、前記部分問題生成手段によって生成された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当て、前記Ｓ個の計算ノードによって、前記自然言語解析処理を行い、前記Ｓ個の計算ノードの各々によって前記自然言語解析処理を行うことは、部分解更新手段によって、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新し、同期手段によって、前記部分解更新手段によって更新された前記部分集合の各部分問題の解を、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記部分集合の各部分問題の解を取得し、制約条件更新手段によって、前記同期手段によって取得した前記他の計算ノードの前記部分集合の各部分問題の解と、前記部分解更新手段によって更新された前記部分集合の各部分問題の解とに基づいて、各部分問題について、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータを更新し、収束判定手段によって、前記制約条件パラメータの値が収束したか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、前記部分解更新手段による更新、前記同期手段による通知及び取得、並びに前記制約条件更新手段による更新を繰り返すことを含む。
【００１６】
このように、第１の発明及び第２の発明によれば、複数種類の自然言語解析処理を行う問題を部分問題の集合に分解してグループを作成し、２以上のグループに属する部分問題の解が一致する制約条件に基づいて、各計算ノードにおいて、割り当てられた部分問題の部分集合について解を更新し、他の計算ノードから取得した部分問題の解を用いて、制約条件パラメータを更新することを収束するまで繰り返すことにより、計算量の増大を抑制して、精度よく自然言語解析処理を行うことができる。
【００１７】
第３の発明に係る自然言語解析処理装置は、少なくとも一文を含む入力文書に対して複数種類の自然言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置であって、前記複数種類の自然言語解析処理の各々について、前記入力文書に対して前記自然言語解析処理を行う問題を、前記自然言語解析処理について予め定義した文字単位以上の単位の問題である部分問題に分解して、前記部分問題の集合を生成する部分問題生成手段と、前記自然言語解析処理を行うＳ個（Ｓは２以上の自然数である）の計算ノードと、前記部分問題生成手段によって生成された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当てるグループ作成手段と、制約条件更新手段と、収束判定手段とを含み、前記Ｓ個の計算ノードの各々は、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新する部分解更新手段と、を含み、前記制約条件更新手段は、各計算ノードの前記部分解更新手段によって更新された前記部分集合の各部分問題の解に基づいて、各部分問題について、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータを更新し、前記収束判定手段は、前記制約条件パラメータの値が収束したか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、各計算ノードの前記部分解更新手段による更新、及び前記制約条件更新手段による更新を繰り返す。
【００１８】
第４の発明に係る自然言語解析処理方法は、部分問題生成手段、Ｓ個（Ｓは２以上の自然数である）の計算ノード、グループ作成手段、制約条件更新手段、及び収束判定手段を含み、少なくとも一文を含む入力文書に対して複数種類の自然言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置における自然言語解析処理方法であって、前記部分問題生成手段によって、前記複数種類の自然言語解析処理の各々について、前記入力文書に対して前記自然言語解析処理を行う問題を、前記自然言語解析処理について予め定義した文字単位以上の単位の問題である部分問題に分解して、前記部分問題の集合を生成し、前記グループ作成手段によって、前記部分問題生成手段によって生成された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当て、前記Ｓ個の計算ノードによって、前記自然言語解析処理を行い、前記制約条件更新手段によって更新し、前記収束判定手段によって判定することを含み、前記Ｓ個の計算ノードの各々によって前記自然言語解析処理を行うことは、部分解更新手段によって、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新することを含み、前記制約条件更新手段は、各計算ノードの前記部分解更新手段によって更新された前記部分集合の各部分問題の解に基づいて、各部分問題について、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータを更新し、前記収束判定手段は、前記制約条件パラメータの値が収束したか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、各計算ノードの前記部分解更新手段による更新、及び前記制約条件更新手段による更新を繰り返す。
【００１９】
このように、第３の発明及び第４の発明によれば、複数種類の自然言語解析処理を行う問題を部分問題の集合に分解してグループを作成し、２以上のグループに属する部分問題の解が一致する制約条件に基づいて、各計算ノードにおいて、割り当てられた部分問題の部分集合について解を更新し、各計算ノードで更新された部分問題の解を用いて、制約条件パラメータを更新することを収束するまで繰り返すことにより、計算量の増大を抑制して、精度よく自然言語解析処理を行うことができる。
【００２０】
第５の発明に係るプログラムは、コンピュータを、上記の自然言語解析処理装置の各手段として機能させるためのプログラムである。
【発明の効果】
【００２１】
以上説明したように、本発明の自然言語解析処理装置、方法、及びプログラムによれば、計算量の増大を抑制して、精度よく自然言語解析処理を行うことができる、という効果が得られる。
【図面の簡単な説明】
【００２２】
【図１】極小部分問題のグループを作成する方法を説明するための図である。
【図２】本発明の第１の実施の形態に係る自然言語解析処理装置の構成を示す概略図である。
【図３】本発明の第１の実施の形態に係る自然言語解析処理装置の計算ノードにおける自然言語解析処理ルーチンの内容を示すフローチャートである。
【図４】本発明の第１の実施の形態に係る自然言語解析処理装置の構成の他の例を示す概略図である。
【図５】本発明の第３の実施の形態に係る自然言語解析処理システムの構成を示す概略図である。
【図６】本発明の第３の実施の形態に係る言語解析制御装置の構成を示す概略図である。
【図７】本発明の第３の実施の形態に係る言語解析装置の構成を示す概略図である。
【図８】単語区切り、品詞タグ付け、固有表現抽出、文節区切り、及び文節間の係り受けの例を示す図である。
【図９】従来技術における履歴ベースの逐次解析法を示す図である。
【図１０】従来技術における動的計画法に基づく解析の例を示す図である。
【発明を実施するための形態】
【００２３】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２４】
〔第１の実施の形態〕
＜発明の概要＞
本発明では、非特許文献４（Andre F. T. Martins, Mario A. T. Figueiredo, Pedro M. Q. Aguiar, Noah A. Smith, Eric P. Xing An Augmented Lagrangian Approach to Constrained MAP Inference Proc. of ICML, 2011.）で提案されているDD-ADMM法を用いて、全体最適化の課題に対処する。DD-ADMMでは、実際に解きたい大きな問題を小さな部分問題に分割して解く方法である。ポイントは、分割した個々の問題は、他と独立に解くことができる点であり、相対的に計算が容易になるといった利点がある。このとき、問題を分割する際に各問題で重複する部分を作っておき、その重複部分の解析結果は全て一致しなくてはいけないという制約を付与することで全体の整合性を保つ。これによって、分割した小さな部分問題の集合を解くことで、実際に解きたい大きな問題の解を得ることが可能となる。
【００２５】
実施例として、入力文書（日本語）に対して、単語区切り、文節区切り、文区切り、品詞付与（辞書引き）、文節間係り受け関係付与を行うシステムを想定する。従来は、1,文区切り、2,単語区切り+品詞付与(一般に形態素解析と呼ばれる)、3,文節区切り、4,係り受け解析、というように、各段階の処理は、前段階の処理結果を入力として受け取り処理を行う。つまり、処理は以下のように行われる。
【００２６】
・入力:システムに文書が入力される
・処理1[入力]:システムに入力された文書を受け取る
・処理1:入力文書に対して文区切りを推定する
・処理1[出力]:入力文書に対して文区切りを付与した文書を出力する
・処理2[入力]:処理1の出力した文書を受け取る
・処理2:単語区切りと同時に品詞を推定する
・処理2[出力]:入力文書に対して文区切り、単語区切り、品詞を付与した文書を出力する
・処理3[入力]:処理2の出力した文書を受け取る
・処理3:文節区切りを推定する
・処理3[出力]:入力文書に対して文区切り、単語区切り、文節区切り、品詞を付与した文書を出力する
・処理4[入力]: 処理3の出力した文書を受け取る
・処理4:文節間の係り受け関係を推定する
・処理4[出力]: 入力文書に対して文区切り、単語区切り、文節区切り、品詞、文節間係り受け関係を付与した文書を出力する
・出力:入力文書に対して文区切り、単語区切り、文節区切り、品詞、文節間係り受け関係を付与した文書を出力する。
【００２７】
それに対し、本発明では、上記の例における5種類の処理を一括して一つの枠組みで処理を行う。
【００２８】
・入力:システムに文書が入力される
・処理[入力]:システムに入力された文書を受け取る
・処理:文区切り、単語区切り、文節区切り、品詞、文節間係り受け関係を一括して推定する
・処理[出力]:入力文書に対して文区切り、単語区切り、文節区切り、品詞、文節間係り受け関係を付与した文書を出力する
・出力:入力文書に対して文区切り、単語区切り、文節区切り、品詞、文節間係り受け関係を付与した文書を出力する
【００２９】
本発明の特徴として、事前に定義された極小部分問題に対し、いくつかの極小部分問題をひとまとめにしたグループを作成する処理があること、各グループで「独立」に、担当する極小部分問題の解を決定する処理のくり返しにより全体の処理を行うこと、各グループで独立に処理された結果の整合性を保持するような処理があること、最終的な解を各グループの解が一致した時に得る処理があること、などが挙げられる。これらの特徴を以下で説明する。
【００３０】
まず、従来のパイプライン方式では、以下の（１）式で表される最適化問題をくり返し解くことになる。
【００３１】
【数１】
0005530469.tif 000002
【００３２】
上記（１）式は、自然言語解析処理に例えばI個の段階があるとした時のi∈{1,...,I}番目の言語解析処理に関する最適化問題を表している。このとき、Xiをi番目の言語解析処理の問題の入力、Yiをi番目の言語解析処理の問題の出力とする。パイプライン方式の場合は、i−1番目の言語解析処理で得られたyi-1を、i番目の言語解析処理の入力xiの一部として利用する方式と言える。
【００３３】
本発明では、基本的な考え方として処理の最小単位を事前に決定する。処理の最小単位とは、それぞれの段階の処理において、問題を定義する上で最も小さい問題として定義できるものに相当し、各段階によってそれぞれ異なり、文字単位以上の単位である。例えば、単語区切りであれば、各文字間が区切れるか区切れないかと推定する問題が問題の最小単位となる。同様に、文節区切りや文区切りも、各文字間が文節、または、文の区切りになるかどうかを推定する問題が問題の最小単位と考えることができる。また、品詞付与の問題であれば、一つの文字に適した品詞を選択する問題が最小単位となる。最小単位の問題は、解きたい問題の部分に相当することから、ここでは、最小単位の問題を「極小部分問題」と呼ぶ。ここでは、極小部分問題のインデックスをrで表す。また、全ての極小部分問題のインデックスの集合をRで表す事とする。よって、解きたい問題は｜R｜個の極小部分問題で構成されている。
【００３４】
次に、一つの文書を一つの入力と考えると、単語区切りや品詞タグ付けは、極小部分問題の集合により定義される。よって、これらの問題の解空間をベクトルの集合Yで表すとする。入力が与えられた時に得られる一つの出力をベクトルz∈Yで表す。ここでは、極小部分問題の解はベクトルの一つの要素ziに相当する。
【００３５】
次に、本発明では、いくつかの極小部分問題でグループを構成し、グループの集合で問題を表現する。この時、各グループは極小部分問題を重複して含むことが可能である。グループの作り方は任意であるが、以下の2つの点を満たすようにする。１点目は、解きたい問題全域をカバーする形でグループを構成することであり、２点目は、各極小部分問題は複数のグループに属することである。ここでは、作成した一つのグループを全体の問題に対する一つの部分問題と考える。よって、一つのグループで一つの最適化問題として解くことになる。なお、グループに属する極小部分問題の部分集合は、複数段階の言語解析処理に関するものを含むことが可能である。
【００３６】
ここで、グループをS個作成したとする。s番目のグループに含まれる解空間の部分空間をYsとする。つまりYs⊆Yである。このとき、ｓ番目のグループに含まれるr番目の極小部分問題の解をzs(r)とする。
【００３７】
グループを作成する例を図１に示す。
【００３８】
Rsをs番目のグループに含まれる極小部分問題のインデックスの集合とする。次に、RsをR⊆∪s=1S  R′s、および、Rs=R′s∩Rとなる集合とする。これは、極小部分問題ではないが全体の問題を解く上で有効な補助的な部分問題があるので、それらの部分問題を含めてグループを構成したい場合に対応するための拡張である。つまり、ここではR′s＼Rに相当する集合に含まれるインデックスは、極小部分問題ではないが問題を解く上での有効な補助的な部分問題のインデックスに相当する。
【００３９】
s番目のグループで得られる出力に対して、出力の良さを計算する関数をfsとする。ここでは、fs(zs)の値が大きいほど、出力として良いものであるという仮定のもとに計算される値とする。このとき、自然言語解析処理を行う問題全体は以下の（２）式に示す最適化問題として定式化できる。
【００４０】
【数２】
0005530469.tif 000003
【００４１】
ここで、zsはグループsに含まれる極小部分問題の解の集合とする。また、zは、zs(r)の全集合とする。この最適化問題は、S個のグループが独立に、各グループが担当する極小部分問題に対する出力zs(r)で最も良いと思われる部分解を選択する問題を、各グループの部分解はu(r)のベクトルと一致することを制約条件として解いていることに相当する。この定式化のポイントは、制約条件zs(r)=u(r)の部分にあり、各グループsで、r番目の極小部分問題を含む場合、zs(r)の値は全てu(r)と一致することを解の条件とする、ということを意味している。これは、つまり、個々のグループでは、解zs(r)を独立に決定するが、制約条件zs(r)=u(r)により全体として整合性が取れる解に限定することができる。この制約条件の式とラグランジュ緩和とを用いて、最適化のための以下の（３）式に示す目的関数を得る。
【００４２】
【数３】
0005530469.tif 000004
【００４３】
次に、非特許文献５（Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 2011.）に記載されているように、augmented Lagrangianの項P/2(zs(r)−u(r))2を追加して、以下の（４）式のように、問題を2次式の形に変形することで問題をより解きやすい形とする。
【００４４】
【数４】
0005530469.tif 000005
【００４５】
これは、最適値でもとの問題と一致する。また、以降の式展開を簡単にするためにλs(r)=−ραs(r)とし、以下の（５）式を得る。
【００４６】
【数５】
0005530469.tif 000006
【００４７】
＜システム構成＞
本発明の第１の実施の形態に係る自然言語解析処理装置１００は、自然言語解析処理の対象として与えられた文書を入力として受け取り、複数段階の言語解析処理を含む自然言語解析処理の結果を出力する。この自然言語解析処理装置１００は、ＣＰＵと、ＲＡＭと、後述する自然言語解析処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。図２に示すように、自然言語解析処理装置１００は、入力部１０と、演算部２０と、出力部３０とを備えている。
【００４８】
入力部１０は、入力された文書を受け付ける。また、入力部１０は、人手により入力された計算ノード数Sとパラメータρを受け付ける。
【００４９】
演算部２０は、極小部分問題生成部２１、グループ作成部２２、及びS個の計算ノード２３1〜２３Sを備えている。なお、計算ノード２３1〜２３Sのうちの任意の計算ノードを示す場合には、計算ノード２３と称することとする。
【００５０】
極小部分問題生成部２１は、言語解析処理の段階毎に、入力部１０により入力された入力文書に対して当該段階の言語解析処理を行う問題を、当該段階の言語解析処理について予め定義された極小部分問題に分解し、全段階における極小部分問題の集合を生成する。
【００５１】
グループ作成部２２は、極小部分問題生成部２１によって生成された極小部分問題の集合について、各極小部分問題が少なくとも２以上のグループに属するように、部分問題の部分集合からなるＳ個のグループを作成し、S個の計算ノード２３1〜２３Sに割り当てる。また、グループ作成部２２は、入力されたパラメータρを、S個の計算ノード２３1〜２３Sの各々に通知する。
【００５２】
S個の計算ノード２３1〜２３Sの各々は、パラメータ更新部３１、部分解更新部３２、同期部３３、制約条件更新部３４、及び収束判定部３５を備えている。各S個のパラメータ更新部３１、部分解更新部３２、同期部３３、制約条件更新部３４、及び収束判定部３５が存在することになるが、同様の機能を有す処理部は同じ番号で表わしている。
【００５３】
パラメータ更新部３１は、グループ作成部２２によって割り当てられたグループに含まれる極小部分問題の部分集合について、以下に説明するように、ラグランジュ未定乗数αs（ｒ）を更新する。
【００５４】
（ラグランジュ未定乗数αs（ｒ）の更新）
最初の処理として、パラメータ更新部３１は、当該計算ノード２３sに割り当てられたグループに含まれる各極小部分問題ｒに対するラグランジュ未定乗数αs（ｒ）を更新する。
【００５５】
ｚとｕを固定したときαs（ｒ）の最適値の方向は、以下の（６）式に示すように、上記（５）式に示す目的関数Lρ(ｚ,ｕ,α)のαs（ｒ）に関する勾配方向である。
【００５６】
【数６】
0005530469.tif 000007
【００５７】
上記（６）式の関係から、以下の（７)式に示す更新式を得る。
【００５８】
【数７】
0005530469.tif 000008
【００５９】
パラメータ更新部３１は、各極小部分問題ｒに対して、上記（７）式に従って、ラグランジュ未定乗数αs（ｒ）を更新する。上記（７）式の更新式は、各計算ノード２３で独立に計算できるため、他の計算ノード２３と通信などを行う必要がない。
【００６０】
部分解更新部３２は、グループ作成部２２によって割り当てられたグループに含まれる極小部分問題ｒの部分集合について、以下に説明するように、当該計算ノード２３sにおける各極小部分問題の解ｚs（ｒ）を更新する。
【００６１】
（各極小部分問題の解ｚs（ｒ）の更新）
【００６２】
反復計算k（kは繰り返し回数を管理する変数）の時点で、αとｕを固定したとき各ｚs（ｒ）の最適解は、以下の（８)式に示すように、上記（５）式に示す目的関数L(ｚ,ｕ,α)を最大にするｚs（ｒ）を見つける問題である。
【００６３】
【数８】
0005530469.tif 000009
【００６４】
ここで、fsは以下の（９）式で表されると仮定する。
【００６５】
【数９】
0005530469.tif 000010
【００６６】
ここでθs(r)は、グループsでのrに関するスコアを表しており、この値は外部から与えられるものとする。つまり、この最適化の中では定数として扱われる。
【００６７】
定義に従って、上記（５）式から解ｚに関係する項のみを取り出すと、以下の（１０）式が得られる。
【００６８】
【数１０】
0005530469.tif 000011
【００６９】
上記（８）式の計算も各グループs毎に計算することが可能である。つまり、計算ノード２３毎に、部分解更新部３２は、割り当てられたグループに含まれる各極小部分問題ｒについて、以下の（１２）式に示す最大化問題を解けばよい。
【００７０】
【数１１】
0005530469.tif 000012
【００７１】
同期部３３は、当該計算ノード２３で今回更新されたαs（ｒ）とｚs（ｒ）を、自分以外の全ての計算ノード２３iへ通知する。また、同期部３３は、他の計算ノード２３i全てから通知された、今回更新されたαs（ｒ）とｚs（ｒ）を受け取る。この処理によって、個々の計算ノード２３は全ての計算ノード２３sの持つαs（ｒ）とｚs（ｒ）の値を取得することができる。
【００７２】
制約条件更新部３４は、他の計算ノード２３s全てから受け取ったαs（ｒ）とｚs（ｒ）を使って、以下のように、制約条件に従って極小部分問題の解を一致させるときの解を示すパラメータｕ（ｒ）を更新する。
【００７３】
ｚとαを固定したときｕの最適解は、上記（５）式に示す目的関数L(ｚ,ｕ,α)に対してus(r)に関する偏微分の値が0になる点である。その関係から以下の（１３）式、（１４）式に示す関係式が得られる。
【００７４】
【数１２】
0005530469.tif 000013
【００７５】
つまり、uはzs(r)の平均とαs(r)の平均を足したものを意味し、パラメータｕ（ｒ）の更新には、全てのαs（ｒ）とｚs（ｒ）が必要である。
【００７６】
そこで、制約条件更新部３４は、取得した全ての計算ノード２３sの持つαs（ｒ）とｚs（ｒ）の値を用いて、上記（１４）式に従って、全ての極小部分問題ｒの各々に対するパラメータｕ（ｒ）を更新する。
【００７７】
個々の計算ノード２３で独立にｕ（ｒ）を求める。ここでの注意点として、個々の計算ノード２３は独立でｕ（ｒ）を求めるが、得られるｕ（ｒ）は全ての計算ノード２３で一致する。処理方法としては、任意のひとつの計算ノード２３でｕ（ｒ）を計算し、その後に各計算ノード２３に通知するといった処理を行うようにしてもよい。ただし、その場合には、選択された計算ノード２３の計算が終了し、結果が通知されるまで、それ以外の計算ノードは待機する必要がある。本実施の形態では、個々の計算ノード２３で同じ計算を行う方式をとった場合を例に説明する。
【００７８】
収束判定部３５は、得られた制約条件のパラメータｕが収束して最適値になっているか判定する。
【００７９】
二つの小さな正の実数ε1、ε2をあたえ、以下の（１５)式、（１６）式を満たした際に最適値に収束したと判定する（非特許文献５を参照）。
【００８０】
【数１３】
0005530469.tif 000014
【００８１】
収束判定で、最適値に収束していなかった場合は、ｋ=ｋ+1として、パラメータ更新部３１による処理に戻る。最適値に収束していると判定された場合は、繰り返し処理を終了する。
【００８２】
この収束判定の処理もｕ（ｒ）と同様に任意のひとつの計算ノード２３で行い、その結果を全体に通知するようにしてもよい。しかし、同期処理が必要となるため、本実施の形態では、収束判定も全ての計算ノード２３で個別に行い、収束と判定されれば処理を終了する場合を例に説明する。この収束判定も、全ての計算ノードで結果が必ず一致するため、個々に判定をおこなっても結果は同じになる。
【００８３】
収束判定部３５は、最適値に収束したと判定されたときに得られた各極小部分問題ｒの解ｕ（ｒ）を組み合わせて、複数段階の言語解析処理の結果を生成し、自然言語解析処理の結果として出力部３０により出力する。なお、本実施の形態では、任意の一つの計算ノード２３から、自然言語解析処理の結果が出力される場合を例に説明したが、全ての計算ノード２３から、自然言語解析処理の結果が出力されてもよい。また、実際のランキングを生成する際には、従来法と同様に上記（２）式を用いて検索スコアを計算する。
【００８４】
＜自然言語解析処理装置の作用＞
次に、本実施の形態に係る自然言語解析処理装置１００の作用について説明する。まず、自然言語解析処理の対象となる入力文書が自然言語解析処理装置１００に入力されると、自然言語解析処理装置１００において、極小部分問題生成部２１によって、入力文書に対する自然言語解析処理を行う問題を、言語解析処理の段階毎の極小部分問題に分解して、全段階における極小部分問題の集合を生成する。そして、グループ作成部２２によって、生成された極小部分問題の集合について、S個のグループを作成し、S個の計算ノード２３1〜２３Sに割り当てる。
【００８５】
そして、自然言語解析処理装置１００の各計算ノード２３によって、図３に示す自然言語解析処理ルーチンが実行される。なお、以下では、計算ノード２３sによって実行した場合について説明する。
【００８６】
まず、ステップＳ１０１において、繰り返し回数を示す変数ｋに初期値１を設定すると共に、割り当てられたグループｓの極小部分問題ｒの部分集合に対する各ラグランジュ未定乗数αs0（ｒ）、各極小部分問題の解ｚs0（ｒ）、及び制約条件のパラメータｕs0（ｒ）の各々に、適当な値（例えば、０）を与えて初期化する。
【００８７】
そして、ステップＳ１０２において、パラメータ更新部３１によって、上記ステップＳ１０１で初期化されたラグランジュ未定乗数αs0（ｒ）、各極小部分問題の解ｚs0（ｒ）、及び制約条件のパラメータｕs0（ｒ）、又は前回更新されたラグランジュ未定乗数αsk-1（ｒ）、各極小部分問題の解ｚsk-1（ｒ）、及び制約条件のパラメータｕsk-1（ｒ）に基づいて、上記（７)式に従って、グループｓ内の極小部分問題ｒの各々に対するラグランジュ未定乗数αsk（ｒ）を更新する。
【００８８】
次のステップＳ１０３では、部分解更新部３２によって、上記ステップＳ１０２で更新されたラグランジュ未定乗数αsk（ｒ）と、上記ステップＳ１０１で初期化された各極小部分問題の解ｚs0（ｒ）、又は前回更新された各極小部分問題の解ｚsk-1（ｒ）に基づいて、上記（１２）式に従って、グループｓ内の極小部分問題ｒの各々に対する解ｚsk（ｒ）を更新する。
【００８９】
そして、ステップＳ１０４では、同期部３３によって、上記ステップＳ１０２で更新されたラグランジュ未定乗数αsk（ｒ）及び上記ステップＳ１０３で更新された各極小部分問題の解ｚsk（ｒ）を他の計算ノード２３に通知すると共に、他の計算ノード２３i全てから、更新されたラグランジュ未定乗数αik（ｒ）及び各極小部分問題の解ｚik（ｒ）を取得する（ｉ＝１,・・・,s−１，s＋１，・・・,S）。
【００９０】
ステップＳ１０５では、制約条件更新部３４によって、上記ステップＳ１０２で更新されたラグランジュ未定乗数αsk（ｒ）及び上記ステップＳ１０３で更新された各極小部分問題の解ｚsk（ｒ）と、上記ステップＳ１０４で他の計算ノード２３i全てから取得したラグランジュ未定乗数αik（ｒ）及び各極小部分問題の解ｚik（ｒ）とに基づいて、上記（１４）式に従って、全ての極小部分問題ｒの各々に対する制約条件のパラメータｕk（ｒ）を更新する。
【００９１】
次のステップＳ１０６では、更新された全てのグループｓ内の極小部分問題ｒの各々の解ｚsk（ｒ）と、更新された制約条件のパラメータｕk（ｒ）とに基づいて、上記（１５）式、(１６)式に従って、制約条件のパラメータｕk（ｒ）の全てが最適値に収束したか否かを判定する。上記（１５）式および(１６)式を満たさない場合には、収束していないと判断し、変数ｋを１インクリメントして、上記ステップＳ１０２へ戻る。一方、上記（１５）式及び(１６）式を満たした場合には、収束したと判断し、上記ステップＳ１０７へ移行する。
【００９２】
ステップＳ１０７では、上記ステップＳ１０５で最終的に更新された制約条件のパラメータｕk（ｒ）を用いて、各段階の言語解析処理の結果を生成し、自然言語解析処理の結果として出力部３０により出力して、自然言語解析処理ルーチンを終了する。
【００９３】
以上説明したように、第１の実施の形態に係る自然言語解析処理装置によれば、複数段階の言語解析処理を行う問題を極小部分問題の集合に分解してグループを作成し、２以上のグループに属する極小部分問題の解が一致する制約条件に基づいて、各計算ノードにおいて、割り当てられた極小部分問題の部分集合についてラグランジュ未定乗数及び極小部分問題の解を更新し、他の計算ノードから取得したラグランジュ未定乗数及び極小部分問題の解を用いて、全ての極小部分問題に対する制約条件パラメータを更新することを収束するまで繰り返すことにより、複数段階の言語解析処理を一括して行うことができ、計算量の増大を抑制して、精度よく自然言語解析処理を行うことができる。
【００９４】
また、本発明を用いることにより、複数の段階で構成される言語解析処理を統合して一括して行うことができるようになる。これによって、従来のカスケード方式で解析するよりも、前の段階の解析結果の間違いの影響をその後の段階の解析に出にくくすることが可能となり、結果的に、全体の解析精度を向上させることが可能となる。また、複雑な言語解析問題を各段階に分割せずに全体最適化を少ない計算量で実現できる。
【００９５】
また、様々な観点を統合して解析を行うことができる。例えば、辞書などの既存の情報や、部分的に解析済みのデータなども容易に統合して利用することが可能である。また、大域的な特徴も容易に統合可能である。また、問題を小さい単位に分割して問題を処理するため、並列処理による高速化が容易である。
【００９６】
なお、上記の実施の形態では、各計算ノード２３が、制約条件更新部３４及び収束判定部３５を備えている場合を例に説明したが、これに限定されるものではない。例えば、図４に示すように、各計算ノード２３は、パラメータ更新部３１及び部分解更新部３２を備え、演算部２０が、制約条件更新部３４、及び収束判定部３５を１つずつ備えるように構成してもよい。この場合には、制約条件更新部３４は、全ての計算ノード２３sで得られたラグランジュ未定乗数αsk（ｒ）と各極小部分問題の解ｚsk（ｒ）を使って、制約条件のパラメータｕk（ｒ）を更新し、収束判定部３５は、得られた制約条件のパラメータｕk（ｒ）が最適値に収束しているか判定するようにする。収束判定で、収束していなかった場合は、各計算ノード２３に得られた制約条件のパラメータｕk（ｒ）を通知してパラメータ更新部３１による処理に戻るようにする。
【００９７】
〔第２の実施の形態〕
次に、第２の実施の形態について説明する。なお、第１の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。
【００９８】
第２の実施の形態では、ネットワークで接続された複数の言語解析装置を備えた分散並列計算環境において、複数の言語解析装置による分散並列計算で、パラメータ更新を行っている点が、第１の実施の形態と異なっている。
【００９９】
＜システム構成＞
図５に示すように、第２の実施の形態に係る自然言語解析処理システム２００は、言語解析制御装置２０１、及びS個の言語解析装置２０２1〜２０２Sを備えている。言語解析制御装置２０１及びS個の言語解析装置２０２1〜２０２Sは、ネットワーク２０３を介して接続されている。なお、言語解析装置２０２1〜２０２Sのうちの任意の言語解析装置を示す場合には、言語解析装置２０２と称することとする。
【０１００】
図６に示すように、言語解析制御装置２０１は、入力部１０、演算部２２０、及び出力部２３０を備えている。
【０１０１】
演算部２２０は、極小部分問題生成部２１及びグループ作成部２２を備えている。
【０１０２】
グループ作成部２２は、極小部分問題生成部２１によって生成された極小部分問題の集合について、極小部分集合の部分集合からなるＳ個のグループを作成し、ネットワーク２０３を介してS個の言語解析装置２０２1〜２０２Sに送信する。また、グループ作成部２２は、入力されたパラメータρを、ネットワーク２０３を介してS個の言語解析装置２０２1〜２０２Sの各々に送信する。
【０１０３】
S個の言語解析装置２０２1〜２０２Sの各々は、図７に示すように、入力部２４０、演算部２５０、及び出力部２６０を備えている。
【０１０４】
入力部２４０は、言語解析制御装置２０１から送信されたグループｓに含まれる極小部分問題の部分集合を受け付ける。また、入力部２４０は、他の言語解析装置２０２からネットワーク２０３を介して送信された情報を受け付ける。
【０１０５】
演算部２５０は、パラメータ更新部３１、部分解更新部３２、同期部３３、制約条件更新部３４、及び収束判定部３５を備えている。
【０１０６】
パラメータ更新部３１は、言語解析装置２０２に送信されたグループｓの極小部分問題の部分集合について、各極小部分問題ｒに対するラグランジュ未定乗数αs（ｒ）を更新する。
【０１０７】
同期部３３は、当該言語解析装置２０２sで今回更新されたαs（ｒ）とｚs（ｒ）を、自分以外の全ての言語解析装置２０２へネットワーク２０３を介して送信する。また、同期部３３は、他の言語解析装置２０２i全てから送信された、今回更新されたαi（ｒ）とｚi（ｒ）を受け取る。この処理によって、個々の言語解析装置２０２は全ての言語解析装置２０２sの持つαs（ｒ）とｚs（ｒ）の値を取得することができる。
【０１０８】
制約条件更新部３４は、他の言語解析装置２０２i全てから受け取ったαi（ｒ）とｚi（ｒ）を使って、上記（１４）式に従って、各極小部分問題ｒに対する制約条件のパラメータｕ（ｒ）を更新する。
【０１０９】
収束判定部３５は、得られた制約条件のパラメータｕ（ｒ）が収束して最適値になっているか判定し、収束したと判定されたときに得られた制約条件のパラメータｕ（ｒ）を組み合わせて、複数段階の言語解析処理の結果を生成し、自然言語解析処理の結果として、出力部２６０により言語解析制御装置２０１へ送信する。
【０１１０】
＜自然言語解析処理システムの作用＞
次に、本実施の形態に係る自然言語解析処理システム２００の作用について説明する。まず、自然言語解析処理の対象となる文書が言語解析制御装置２０１に入力されると、言語解析制御装置２０１において、極小部分問題生成部２１によって、入力文書に対する自然言語解析処理を行う問題を、言語解析処理の段階毎の極小部分問題に分解して、極小部分問題の集合を生成する。そして、グループ作成部２２によって、生成された極小部分問題の集合について、S個のグループを作成し、ネットワーク２０３を介してS個の言語解析装置２０２へ送信して、S個の言語解析装置２０２に割り当てる。
【０１１１】
そして、各言語解析装置２０２によって、上記図３に示す自然言語解析処理ルーチンが実行される。
【０１１２】
少なくとも１つの言語解析装置２０２によって、最終的に更新された制約条件のパラメータｕ（ｒ）を組み合わせて生成された自然言語解析処理の結果が、ネットワーク２０３を介して言語解析制御装置２０１へ送信される。言語解析制御装置２０１は、言語解析装置２０２により受信した自然言語解析処理の結果を出力部２３０により出力する。
【０１１３】
以上説明したように、第２の実施の形態に係る自然言語解析処理システムによれば、ネットワークを介して接続された複数の言語解析装置によって、分散並列処理による自然言語解析処理を行うため、処理を高速化できる。
【０１１４】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１１５】
例えば、複数段階の言語解析処理を含む自然言語解析処理を行う問題を、段階毎に予め定義された最小の単位である極小部分問題に分解する場合を例に説明したが、これに限定されるものではなく、最小の単位より大きい単位の部分問題を定義して、当該部分問題に分解するようにしてもよい。例えば、最小の単位である極小部分問題を複数組み合わせた部分問題に分解するようにしてもよい。
【０１１６】
また、上述の自然言語解析処理装置、言語解析制御装置、言語解析装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【０１１７】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【０１１８】
１０   入力部
２０   演算部
２１   極小部分問題生成部
２２   グループ作成部
２３   計算ノード
３１   パラメータ更新部
３２   部分解更新部
３３   同期部
３４   制約条件更新部
３５   収束判定部
１００ 自然言語解析処理装置
２００ 自然言語解析処理システム
２０１ 言語解析制御装置
２０２ 言語解析装置
【図２】
0005530469.tif 000015
【図３】
0005530469.tif 000016
【図４】
0005530469.tif 000017
【図５】
0005530469.tif 000018
【図６】
0005530469.tif 000019
【図７】
0005530469.tif 000020
【図８】
0005530469.tif 000021
【図９】
0005530469.tif 000022
【図１】
0005530469.tif 000023
【図１０】
0005530469.tif 000024