(57)【要約】【課題】計算量の増大を抑制して、逐次入力される入力文字列毎に精度良く自然言語解析処理を行う。【解決手段】極小部分問題生成部２２によって、一入力単位に対して言語解析処理を行う問題を、極小部分問題に分解して、極小部分問題の集合を生成し、グループ作成部２６によって、極小部分問題の全集合に対する部分集合で構成されるＳ個のグループを作成してＳ個の計算ノード３０に割り当てる。各計算ノード３０において、パラメータ更新部３２、部分解更新部３４、第１フラグ判定部３６、同期部３８、制約条件更新部４０、及び第２フラグ判定部４２の処理を、制約条件パラメータの値が最適値に収束したと判定されるまで繰り返し行う。【選択図】図３
2014149786.tif 000002
【特許請求の範囲】
【請求項１】
逐次入力される少なくとも１つの文字からなる文字列の各々を連結して得られる入力文字列に対して言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置であって、
前記入力文字列に対して前記言語解析処理を行う問題を、予め定義した文字単位又は文字列単位で前記言語解析処理を行う部分問題に分解したときの前記部分問題を、前記文字単位又は文字列単位の入力毎に、逐次生成する部分問題生成手段と、
前記部分問題生成手段により逐次生成された部分問題の集合を記憶する部分問題記憶手段と、
前記部分問題生成手段により前記部分問題が逐次生成される毎に、前記自然言語解析処理を行うＳ個（Ｓは２以上の自然数である）の計算ノードと、
前記部分問題生成手段により前記部分問題が逐次生成される毎に、前記部分問題記憶手段に記憶された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当てるグループ作成手段と、を含み、
前記Ｓ個の計算ノードの各々は、
前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各極小部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新する部分解更新手段と、
前記部分解更新手段によって更新された前記部分集合の各部分問題の解が、前回更新された前記部分集合の各部分問題の解と全て一致している場合に、前記計算ノードの前記部分更新手段による更新処理を行わないことを表すグループ非活性状態を設定するグループ非活性状態設定手段と、
各部分問題について、前記部分解更新手段によって更新された前記部分問題の解が、前回更新された前記部分問題の解と一致していない場合に、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータについて設定されている、前記制約条件パラメータの更新処理を行わないことを表す制約条件非活性状態を解除する制約条件活性状態設定手段と、
前記部分解更新手段によって更新された前記部分集合の各部分問題の解を、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記部分集合の各部分問題の解を取得する同期手段と、
前記同期手段によって取得した前記他の計算ノードの前記部分集合の各部分問題の解と、前記部分解更新手段によって更新された前記部分集合の各部分問題の解とに基づいて、各部分問題について、前記部分問題の前記制約条件パラメータを更新する制約条件更新手段と、
各部分問題について、前記制約条件更新手段により更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致しない場合には、前記部分問題が属するグループが割り当てられた前記計算ノードについて設定されている前記グループ非活性状態を解除するグループ活性状態設定手段と、
各部分問題について、前記制約条件更新手段によって更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致している場合に、前記部分問題の前記制約条件パラメータについて前記制約条件非活性状態を設定する制約条件非活性状態設定手段と、
前記制約条件パラメータの値が収束したか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、前記部分解更新手段による更新、前記グループ非活性状態設定手段による設定、前記制約条件活性状態設定手段による設定、前記同期手段による通知及び取得、前記制約条件更新手段による更新、前記グループ活性状態設定手段による設定、並びに前記制約条件非活性状態設定手段による設定を繰り返す収束判定手段と
を含む自然言語解析処理装置であって、
前記グループ非活性状態が設定されている前記計算ノードは、前記部分解更新手段による更新を行わず、
前記グループ非活性状態が設定されている前記計算ノードの前記同期手段は、前記部分解更新手段によって最後に更新された前記部分集合の各部分問題の解を、他の計算ノードに通知し、
前記制約条件更新手段は、前記制約条件非活性状態が設定されている前記制約条件パラメータを更新しない
自然言語解析処理装置。
【請求項２】
前記部分解更新手段は、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の部分集合について、前回更新されたラグランジュ未定乗数、前記部分集合の各部分問題の解、及び前記制約条件パラメータを用いて、予め定められた目的関数の値を最適化するように、前記ラグランジュ未定乗数を更新し、前記更新された前記ラグランジュ未定乗数を用いて、前記目的関数の値を最適化するように、前記部分集合の各部分問題の解を更新し、
前記同期手段は、前記部分解更新手段によって更新された前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解を、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記ラグランジュ未定乗数及び前記部分集合の各極小部分問題の解を取得し、
前記制約条件更新手段は、前記同期手段によって取得した前記他の計算ノードの前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解に基づいて、前記目的関数の値を最適化するように、各部分問題について、前記制約条件パラメータを更新する請求項１記載の自然言語解析処理装置。
【請求項３】
逐次入力される少なくとも１つの文字からなる文字列の各々を連結して得られる入力文字列に対して言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置であって、
前記入力文字列に対して前記言語解析処理を行う問題を、予め定義した文字単位又は文字列単位で前記言語解析処理を行う部分問題に分解したときの前記部分問題を、前記文字単位又は文字列単位の入力毎に、逐次生成する部分問題生成手段と、
前記部分問題生成手段により逐次生成された部分問題の集合を記憶する部分問題記憶手段と、
前記部分問題生成手段により前記部分問題が逐次生成される毎に、前記自然言語解析処理を行うＳ個（Ｓは２以上の自然数である）の計算ノードと、
前記部分問題生成手段により前記部分問題が逐次生成される毎に、前記部分問題記憶手段に記憶された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当てるグループ作成手段と、
制約条件更新手段と、グループ活性状態設定手段と、制約条件非活性状態設定手段と、収束判定手段と、を含み、
前記Ｓ個の計算ノードの各々は、
前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各極小部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新する部分解更新手段と、
前記部分解更新手段によって更新された前記部分集合の各部分問題の解が、前回更新された前記部分集合の各部分問題の解と全て一致している場合に、前記計算ノードの前記部分更新手段による更新処理を行わないことを表すグループ非活性状態を設定するグループ非活性状態設定手段と、
各部分問題について、前記部分解更新手段によって更新された前記部分問題の解が、前回更新された前記部分問題の解と一致していない場合に、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータについて設定されている、前記制約条件パラメータの更新処理を行わないことを表す制約条件非活性状態を解除する制約条件活性状態設定手段と、を含み
前記制約条件更新手段は、各計算ノードの前記部分集合の各部分問題の解と、前記部分解更新手段によって更新された前記部分集合の各部分問題の解とに基づいて、各部分問題について、前記部分問題の前記制約条件パラメータを更新し、
前記グループ活性状態フラグ付与手段は、各部分問題について、前記制約条件更新手段により更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致しない場合には、前記部分問題が属するグループが割り当てられた前記計算ノードについて設定されている前記グループ非活性状態を解除し、
前記制約条件非活性状態設定手段は、各部分問題について、前記制約条件更新手段によって更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致している場合に、前記部分問題の前記制約条件パラメータについて前記制約条件非活性状態を設定し、
前記収束判定手段は、前記制約条件パラメータの値が収束したか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、前記部分解更新手段による更新、前記グループ非活性状態設定手段による設定、前記制約条件活性状態設定手段による設定、前記同期手段による通知及び取得、前記制約条件更新手段による更新、前記グループ活性状態設定手段による設定、並びに前記制約条件非活性状態設定手段による設定を繰り返す
自然言語解析処理装置であって、
前記グループ非活性状態が設定されている前記計算ノードは、前記部分解更新手段による更新を行わず、
前記制約条件更新手段は、前記制約条件非活性状態が設定されている前記制約条件パラメータの更新を行わず、
前記グループ非活性状態が設定されている前記計算ノードにおける前記部分集合の各部分問題の解は、前記部分解更新手段によって最後に更新された前記部分集合の各部分問題の解とする
自然言語解析処理装置。
【請求項４】
前記部分解更新手段は、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の部分集合について、前回更新されたラグランジュ未定乗数、前記部分集合の各部分問題の解、及び前記制約条件パラメータを用いて予め定められた目的関数の値を最適化するように、前記ラグランジュ未定乗数を更新し、前記更新された前記ラグランジュ未定乗数を用いて、前記目的関数の値を最適化するように、前記部分集合の各部分問題の解を更新し、
前記制約条件更新手段は、各計算ノードの前記部分解更新手段によって更新された前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解に基づいて、前記目的関数の値を最適化するように、各部分問題について、前記制約条件パラメータを更新する請求項３記載の自然言語解析処理装置。
【請求項５】
部分問題生成手段、部分問題記憶手段、Ｓ個（Ｓは２以上の自然数である）の計算ノード、及びグループ作成手段を含み、逐次入力される少なくとも１つの文字からなる文字列の各々を連結して得られる入力文字列に対して言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置における自然言語解析処理方法であって、
前記部分問題生成手段によって、前記入力文字列に対して前記言語解析処理を行う問題を、予め定義した文字単位又は文字列単位で前記言語解析処理を行う部分問題に分解したときの前記部分問題を、前記文字単位又は文字列単位の入力毎に、逐次生成し、
前記部分問題記憶手段によって、前記部分問題生成手段により逐次生成された部分問題の集合を記憶し、
前記グループ作成手段によって、前記部分問題生成手段により前記部分問題が逐次生成される毎に、前記部分問題記憶手段に記憶された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当て、
前記Ｓ個の計算ノードによって、前記自然言語解析処理を行い、
前記Ｓ個の計算ノードの各々によって前記自然言語解析処理を行うことは、
部分解更新手段によって、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各極小部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新し、
グループ非活性状態設定手段によって、前記部分解更新手段によって更新された前記部分集合の各部分問題の解が、前回更新された前記部分集合の各部分問題の解と全て一致している場合に、前記計算ノードの前記部分更新手段による更新処理を行わないことを表すグループ非活性状態を設定し、
制約条件活性状態設定手段によって、各部分問題について、前記部分解更新手段によって更新された前記部分問題の解が、前回更新された前記部分問題の解と一致していない場合に、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータについて設定されている、前記制約条件パラメータの更新処理を行わないことを表す制約条件非活性状態を解除し、
同期手段によって、前記部分解更新手段によって更新された前記部分集合の各部分問題の解を、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記部分集合の各部分問題の解を取得し、
制約条件更新手段によって、前記同期手段によって取得した前記他の計算ノードの前記部分集合の各部分問題の解と、前記部分解更新手段によって更新された前記部分集合の各部分問題の解とに基づいて、各部分問題について、前記部分問題の前記制約条件パラメータを更新し、
グループ活性状態設定手段によって、各部分問題について、前記制約条件更新手段により更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致しない場合には、前記部分問題が属するグループが割り当てられた前記計算ノードについて設定されている前記グループ非活性状態を解除し、
制約条件非活性状態設定手段によって、各部分問題について、前記制約条件更新手段によって更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致している場合に、前記部分問題の前記制約条件パラメータについて前記制約条件非活性状態を設定し、
収束判定手段によって、前記制約条件パラメータの値が収束したか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、前記部分解更新手段による更新、前記グループ非活性状態設定手段による設定、前記制約条件活性状態設定手段による設定、前記同期手段による通知及び取得、前記制約条件更新手段による更新、前記グループ活性状態設定手段による設定、並びに前記制約条件非活性状態設定手段による設定を繰り返すことを含む
自然言語解析処理方法であって、
前記グループ非活性状態が設定されている前記計算ノードは、前記部分解更新手段による更新を行わず、
前記グループ非活性状態が設定されている前記計算ノードの前記同期手段は、前記部分解更新手段によって最後に更新された前記部分集合の各部分問題の解を、他の計算ノードに通知し、
前記制約条件更新手段は、前記制約条件非活性状態が設定されている前記制約条件パラメータを、更新しない
自然言語解析処理方法。
【請求項６】
前記部分解更新手段は、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の部分集合について、前回更新されたラグランジュ未定乗数、前記部分集合の各部分問題の解、及び前記制約条件パラメータを用いて、予め定められた目的関数の値を最適化するように、前記ラグランジュ未定乗数を更新し、前記更新された前記ラグランジュ未定乗数を用いて、前記目的関数の値を最適化するように、前記部分集合の各部分問題の解を更新し、
前記同期手段は、前記部分解更新手段によって更新された前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解を、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記ラグランジュ未定乗数及び前記部分集合の各極小部分問題の解を取得し、
前記制約条件更新手段は、前記同期手段によって取得した前記ほかの計算ノードの前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解に基づいて、前記目的関数の値を最適化するように、各部分問題について、前記制約条件パラメータを更新する請求項５記載の自然言語解析処理方法。
【請求項７】
部分問題生成手段、部分問題記憶手段、Ｓ個（Ｓは２以上の自然数である）の計算ノード、グループ作成手段、制約条件更新手段、グループ活性状態設定手段、制約条件非活性状態設定手段、及び収束判定手段を含み、逐次入力される少なくとも１つの文字からなる文字列の各々を連結して得られる入力文字列に対して言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置における自然言語解析処理方法であって、
前記部分問題生成手段によって、前記入力文字列に対して前記言語解析処理を行う問題を、予め定義した文字単位又は文字列単位で前記言語解析処理を行う部分問題に分解したときの前記部分問題を、前記文字単位又は文字列単位の入力毎に、逐次生成し、
前記部分問題記憶手段によって、前記部分問題生成手段により逐次生成された部分問題の集合を記憶し、
前記グループ作成手段によって、前記部分問題生成手段により前記部分問題が逐次生成される毎に、前記部分問題記憶手段に記憶された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当て、
前記Ｓ個の計算ノードによって、前記自然言語解析処理を行い、
前記制約条件更新手段によって更新し、
前記グループ活性状態設定手段によって設定し、
前記制約条件非活性状態設定手段によって設定し、
前記収束判定手段によって判定することを含み、
前記Ｓ個の計算ノードの各々によって前記自然言語解析処理を行うことは、
前記部分解更新手段によって、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各極小部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新し、
前記グループ非活性状態設定手段によって、前記部分解更新手段によって更新された前記部分集合の各部分問題の解が、前回更新された前記部分集合の各部分問題の解と全て一致している場合に、前記計算ノードの前記部分更新手段による更新処理を行わないことを表すグループ非活性状態を設定し、
前記制約条件活性状態設定手段によって、各部分問題について、前記部分解更新手段によって更新された前記部分問題の解が、前回更新された前記部分問題の解と一致していない場合に、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータについて設定されている、前記制約条件パラメータの更新処理を行わないことを表す制約条件非活性状態を解除することを含み、
前記制約条件更新手段は、各計算ノードの前記部分解更新手段によって更新された前記部分集合の各部分問題の解に基づいて、各部分問題について、前記部分問題の前記制約条件パラメータを更新し、
前記グループ活性状態設定手段は、各部分問題について、前記制約条件更新手段により更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致しない場合には、前記部分問題が属するグループが割り当てられた前記計算ノードについて設定されている前記グループ非活性状態を解除し、
制約条件非活性状態設定手段は、各部分問題について、前記制約条件更新手段によって更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致している場合に、前記部分問題の前記制約条件パラメータについて前記制約条件非活性状態を設定し、
前記収束判定手段は、前記制約条件パラメータの値が収束したか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、各計算ノードの前記部分解更新手段による更新、前記グループ非活性状態設定手段による設定、前記制約条件活性状態設定手段による設定、前記同期手段による通知及び取得、前記制約条件更新手段による更新、前記グループ活性状態設定手段による設定、並びに前記制約条件非活性状態設定手段による設定を繰り返すことを含む
自然言語解析処理方法であって、
前記グループ非活性状態が設定されている前記計算ノードは、前記部分解更新手段による更新を行わず、
前記制約条件更新手段は、前記制約条件非活性状態が設定されている前記制約条件パラメータの更新を行わず、
前記グループ非活性状態が設定されている前記計算ノードにおける前記部分集合の各部分問題の解は、前記部分解更新手段によって最後に更新された前記部分集合の各部分問題の解とする自然言語解析処理方法。
【請求項８】
コンピュータを、請求項１〜請求項４の何れか１項記載の自然言語解析処理装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自然言語解析処理装置、方法、及びプログラムに係り、特に、入力文書に対して自然言語解析処理を行う自然言語解析処理装置、方法、プログラムに関する。
【背景技術】
【０００２】
自然言語とは、日本語や英語など人間が通常使う言語のことである。自然言語で記述された文書を文法や意味的に解析する技術は、例えば、その言語の成り立ちや構造を理解するという言語学的な観点で学術的に重要な意義がある。また、近年では、人間が生成した文書を、文法・意味的に自動で解析し、その結果を利用して提供するさまざまなサービスが、主にｗｅｂ上で展開されるようになってきた。例えば、翻訳サイト、人や商品の評判分析サイト、ある特定の事象に対する要約サイトなどのサービスが、これに相当する。これらのサービスでは、人間が生成した電子化文書を、システム内部で文法、意味的に解析し、それらを利用する形で実際のサービスを提供する形になる。その意味で、自然言語を文法、意味的に解析する技術は、これらサービスの根幹の技術であり、情報処理分野でも非常に重要な位置を占めるようになった。
【０００３】
一概に、自然言語を解析するといっても、単語区切りや品詞推定といった表層的な解析から、語や節間の係り受け関係の推定といったより高度な解析を行うものまで含まれる。例えば、文書から文の区切りを推定する「文区切り」、単語の区切りを推定する「単語区切り」、単語の品詞を推定する品詞付与、単語や節間の関係を推定する係り受け解析などがある。これらの例を図９に示す。
【０００４】
品詞付与や係り受け解析といった言語解析問題は、「相互依存性」がある問題に分類される。これは、例えば、単語の品詞を決定する問題では、ある単語の品詞を決定する際には、前後や周辺の品詞によって対象とする単語に付与すべき品詞が決まる関係があり、また、その前後や周辺の品詞も、その前後や周辺の品詞に依存して決まる問題である。仮に、ある品詞Ａの後に、品詞Ｂは出現してはいけないという規則が存在する場合、個々の単語の品詞を独立に推定してしまうと、この規則を満たした結果が得られるという保証が無い。つまり、個々単語の品詞を独立に推定した場合はこういった全体としての整合性がとれるとは限らないため、文書全体として最も良い品詞列を探索する問題になってくる。特に、文区切り、単語区切り、品詞推定、係り受け解析といった問題を一括して解くことを考えると、とても複雑に絡み合った問題となっているため、最もよい出力を探索する問題は非常に難しい問題である。
【０００５】
これらの問題を解くために、履歴ベースの逐次解析法（いわゆる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 Identi_cation via a Linear Programming Formulation Introduction to Statistical Relational Learning, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
履歴ベースの逐次解析法は、直前までの推定結果を利用して次の推定を行う方法である（図１０参照）。独立に問題を解く方法に比べて、出力の整合性を保つことが可能である。ただし、直前までの解析結果を信じて次の解析結果を決定する方法であるため、直前の解析結果に誤りがあった場合には、その誤りに従った解析を続けてしまうため、間違いの伝播が起こるという問題がある。
【０００８】
その問題を解決する方法として、動的計画法に基づく方法（図１１参照）や整数計画法に基づく方法が使われるようになった。これは、全体として最もよい出力を選ぶ方法となっているため、履歴ベースの逐次解析法に比べて途中の解析誤りといった問題が発生しない。しかし、全体として最もよい出力を選ぶための計算量は、逐次解析法に比べると非常に大きくなるといった問題がある。
【０００９】
特にストリーミング入力のような逐次的にテキストが入力される状況に対して、入ってきた順に逐次処理をし、逐次的に結果を出力するシステムを想定する。例えば、自然言語解析を利用したアプリケーションには、機械翻訳、文書校正、オンライン違法有害情報監視などがある。この様なアプリケーションをオンラインで、かつリアルタイム処理する状況を想定すると、翻訳では、特に同時通訳システムがあり、文書校正では、非母国語文書作成時のオンライン文書校正といったアプリケーションがある。この様なサービスを実現する上では、テキストをリアルタイムかつ逐次処理が可能であることが重要な要件となる。
【００１０】
また、逐次入力に対応した逐次処理を必要とする状況では、履歴ベースの方法が最も適している。また、逆に整数計画問題法を用いて解析法で逐次処理を行う場合には、現状では入力が入る毎に最適化をやり直さなくてはいけない状況になり、計算量的な観点で非常に困難となる問題がある。
【００１１】
また、一般的に、整数計画法のような全体最適化を行う方法論のほうが、履歴ベースで解析を行う方法論よりも解析制度は高いが、上述のように、整数計画法のような全体最適化を行う方法論は、逐次処理には計算量的な観点で問題がある。
【００１２】
本発明では、上記問題点を解決するために成されたものであり、計算量の増大を抑制して、逐次入力される入力文字列に対して精度良く自然言語解析処理を行うことができる自然言語解析処理装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記目的を達成するために、第１の発明に係る自然言語解析処理装置は、逐次入力される少なくとも１つの文字からなる文字列の各々を連結して得られる入力文字列に対して言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置であって、前記入力文字列に対して前記言語解析処理を行う問題を、予め定義した文字単位又は文字列単位で前記言語解析処理を行う部分問題に分解したときの前記部分問題を、前記文字単位又は文字列単位の入力毎に、逐次生成する部分問題生成手段と、前記部分問題生成手段により逐次生成された部分問題の集合を記憶する部分問題記憶手段と、前記部分問題生成手段により前記部分問題が逐次生成される毎に、前記自然言語解析処理を行うＳ個（Ｓは２以上の自然数である）の計算ノードと、前記部分問題生成手段により前記部分問題が逐次生成される毎に、前記部分問題記憶手段に記憶された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当てるグループ作成手段と、を含み、前記Ｓ個の計算ノードの各々は、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各極小部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新する部分解更新手段と、前記部分解更新手段によって更新された前記部分集合の各部分問題の解が、前回更新された前記部分集合の各部分問題の解と全て一致している場合に、前記計算ノードの前記部分更新手段による更新処理を行わないことを表すグループ非活性状態を設定するグループ非活性状態設定手段と、各部分問題について、前記部分解更新手段によって更新された前記部分問題の解が、前回更新された前記部分問題の解と一致していない場合に、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータについて設定されている、前記制約条件パラメータの更新処理を行わないことを表す制約条件非活性状態を解除する制約条件活性状態設定手段と、前記部分解更新手段によって更新された前記部分集合の各部分問題の解を、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記部分集合の各部分問題の解を取得する同期手段と、前記同期手段によって取得した前記他の計算ノードの前記部分集合の各部分問題の解と、前記部分解更新手段によって更新された前記部分集合の各部分問題の解とに基づいて、各部分問題について、前記部分問題の前記制約条件パラメータを更新する制約条件更新手段と、各部分問題について、前記制約条件更新手段により更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致しない場合には、前記部分問題が属するグループが割り当てられた前記計算ノードについて設定されている前記グループ非活性状態を解除するグループ活性状態設定手段と、各部分問題について、前記制約条件更新手段によって更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致している場合に、前記部分問題の前記制約条件パラメータについて前記制約条件非活性状態を設定する制約条件非活性状態設定手段と、前記制約条件パラメータの値が収束したか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、前記部分解更新手段による更新、前記グループ非活性状態設定手段による設定、前記制約条件活性状態設定手段による設定、前記同期手段による通知及び取得、前記制約条件更新手段による更新、前記グループ活性状態設定手段による設定、並びに前記制約条件非活性状態設定手段による設定を繰り返す収束判定手段とを含む自然言語解析処理装置であって、前記グループ非活性状態が設定されている前記計算ノードは、前記部分解更新手段による更新を行わず、前記グループ非活性状態が設定されている前記計算ノードの前記同期手段は、前記部分解更新手段によって最後に更新された前記部分集合の各部分問題の解を、他の計算ノードに通知し、前記制約条件更新手段は、前記制約条件非活性状態が設定されている前記制約条件パラメータを更新しない自然言語解析処理装置として構成されている。
【００１４】
第２の発明に係る自然言語解析方法は、部分問題生成手段、部分問題記憶手段、Ｓ個（Ｓは２以上の自然数である）の計算ノード、及びグループ作成手段を含み、逐次入力される少なくとも１つの文字からなる文字列の各々を連結して得られる入力文字列に対して言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置における自然言語解析処理方法であって、前記部分問題生成手段によって、前記入力文字列に対して前記言語解析処理を行う問題を、予め定義した文字単位又は文字列単位で前記言語解析処理を行う部分問題に分解したときの前記部分問題を、前記文字単位又は文字列単位の入力毎に、逐次生成し、前記部分問題記憶手段によって、前記部分問題生成手段により逐次生成された部分問題の集合を記憶し、前記グループ作成手段によって、前記部分問題生成手段により前記部分問題が逐次生成される毎に、前記部分問題記憶手段に記憶された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当て、前記Ｓ個の計算ノードによって、前記自然言語解析処理を行い、前記Ｓ個の計算ノードの各々によって前記自然言語解析処理を行うことは、部分解更新手段によって、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各極小部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新し、グループ非活性状態設定手段によって、前記部分解更新手段によって更新された前記部分集合の各部分問題の解が、前回更新された前記部分集合の各部分問題の解と全て一致している場合に、前記計算ノードの前記部分更新手段による更新処理を行わないことを表すグループ非活性状態を設定し、制約条件活性状態設定手段によって、各部分問題について、前記部分解更新手段によって更新された前記部分問題の解が、前回更新された前記部分問題の解と一致していない場合に、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータについて設定されている、前記制約条件パラメータの更新処理を行わないことを表す制約条件非活性状態を解除し、同期手段によって、前記部分解更新手段によって更新された前記部分集合の各部分問題の解を、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記部分集合の各部分問題の解を取得し、制約条件更新手段によって、前記同期手段によって取得した前記他の計算ノードの前記部分集合の各部分問題の解と、前記部分解更新手段によって更新された前記部分集合の各部分問題の解とに基づいて、各部分問題について、前記部分問題の前記制約条件パラメータを更新し、グループ活性状態設定手段によって、各部分問題について、前記制約条件更新手段により更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致しない場合には、前記部分問題が属するグループが割り当てられた前記計算ノードについて設定されている前記グループ非活性状態を解除し、制約条件非活性状態設定手段によって、各部分問題について、前記制約条件更新手段によって更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致している場合に、前記部分問題の前記制約条件パラメータについて前記制約条件非活性状態を設定し、収束判定手段によって、前記制約条件パラメータの値が収束したか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、前記部分解更新手段による更新、前記グループ非活性状態設定手段による設定、前記制約条件活性状態設定手段による設定、前記同期手段による通知及び取得、前記制約条件更新手段による更新、前記グループ活性状態設定手段による設定、並びに前記制約条件非活性状態設定手段による設定を繰り返すことを含む自然言語解析処理方法であって、前記グループ非活性状態が設定されている前記計算ノードは、前記部分解更新手段による更新を行わず、前記グループ非活性状態が設定されている前記計算ノードの前記同期手段は、前記部分解更新手段によって最後に更新された前記部分集合の各部分問題の解を、他の計算ノードに通知し、前記制約条件更新手段は、前記制約条件非活性状態が設定されている前記制約条件パラメータを、更新しない。
【００１５】
第１の発明及び第２の発明によれば、逐次入力される入力文字列に対して自然言語解析処理を行う問題を部分問題の集合に分割してグループを作成し、２以上のグループに属する部分問題の解が一致する制約条件に基づいて、各計算ノードにおいて、計算ノードのグループに非活性状態が設定されているか否かに応じて、割り当てられた部分問題の部分集合について解を更新し、他の計算ノードから取得した部分問題の解を用いて、制約条件パラメータに非活性状態が設定されているか否かに応じて、制約条件パラメータを更新することを収束するまで繰り返すことにより、計算量の増大を抑制して、逐次入力される入力文字列に対して精度良く自然言語解析処理を行うことができる。
【００１６】
また、第１の発明及び第２の発明によれば、前記部分解更新手段は、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の部分集合について、前回更新されたラグランジュ未定乗数、前記部分集合の各部分問題の解、及び前記制約条件パラメータを用いて、予め定められた目的関数の値を最適化するように、前記ラグランジュ未定乗数を更新し、前記更新された前記ラグランジュ未定乗数を用いて、前記目的関数の値を最適化するように、前記部分集合の各部分問題の解を更新し、前記同期手段は、前記部分解更新手段によって更新された前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解を、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記ラグランジュ未定乗数及び前記部分集合の各極小部分問題の解を取得し、前記制約条件更新手段は、前記同期手段によって取得した前記ほかの計算ノードの前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解に基づいて、前記目的関数の値を最適化するように、各部分問題について、前記制約条件パラメータを更新するようにすることもできる。
【００１７】
第３の発明の自然言語解析処理装置は、  逐次入力される少なくとも１つの文字からなる文字列の各々を連結して得られる入力文字列に対して言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置であって、前記入力文字列に対して前記言語解析処理を行う問題を、予め定義した文字単位又は文字列単位で前記言語解析処理を行う部分問題に分解したときの前記部分問題を、前記文字単位又は文字列単位の入力毎に、逐次生成する部分問題生成手段と、前記部分問題生成手段により逐次生成された部分問題の集合を記憶する部分問題記憶手段と、前記部分問題生成手段により前記部分問題が逐次生成される毎に、前記自然言語解析処理を行うＳ個（Ｓは２以上の自然数である）の計算ノードと、前記部分問題生成手段により前記部分問題が逐次生成される毎に、前記部分問題記憶手段に記憶された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当てるグループ作成手段と、制約条件更新手段と、グループ活性状態設定手段と、制約条件非活性状態設定手段と、収束判定手段と、を含み、前記Ｓ個の計算ノードの各々は、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各極小部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新する部分解更新手段と、前記部分解更新手段によって更新された前記部分集合の各部分問題の解が、前回更新された前記部分集合の各部分問題の解と全て一致している場合に、前記計算ノードの前記部分更新手段による更新処理を行わないことを表すグループ非活性状態を設定するグループ非活性状態設定手段と、各部分問題について、前記部分解更新手段によって更新された前記部分問題の解が、前回更新された前記部分問題の解と一致していない場合に、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータについて設定されている、前記制約条件パラメータの更新処理を行わないことを表す制約条件非活性状態を解除する制約条件活性状態設定手段と、を含み前記制約条件更新手段は、各計算ノードの前記部分集合の各部分問題の解と、前記部分解更新手段によって更新された前記部分集合の各部分問題の解とに基づいて、各部分問題について、前記部分問題の前記制約条件パラメータを更新し、前記グループ活性状態フラグ付与手段は、各部分問題について、前記制約条件更新手段により更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致しない場合には、前記部分問題が属するグループが割り当てられた前記計算ノードについて設定されている前記グループ非活性状態を解除し、前記制約条件非活性状態設定手段は、各部分問題について、前記制約条件更新手段によって更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致している場合に、前記部分問題の前記制約条件パラメータについて前記制約条件非活性状態を設定し、前記収束判定手段は、前記制約条件パラメータの値が収束���たか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、前記部分解更新手段による更新、前記グループ非活性状態設定手段による設定、前記制約条件活性状態設定手段による設定、前記同期手段による通知及び取得、前記制約条件更新手段による更新、前記グループ活性状態設定手段による設定、並びに前記制約条件非活性状態設定手段による設定を繰り返す自然言語解析処理装置であって、前記グループ非活性状態が設定されている前記計算ノードは、前記部分解更新手段による更新を行わず、前記制約条件更新手段は、前記制約条件非活性状態が設定されている前記制約条件パラメータの更新を行わず、前記グループ非活性状態が設定されている前記計算ノードにおける前記部分集合の各部分問題の解は、前記部分解更新手段によって最後に更新された前記部分集合の各部分問題の解とする自然言語解析処理装置として構成されている。
【００１８】
第４の発明に係る自然言語解析方法は、部分問題生成手段、部分問題記憶手段、Ｓ個（Ｓは２以上の自然数である）の計算ノード、グループ作成手段、制約条件更新手段、グループ活性状態設定手段、制約条件非活性状態設定手段、及び収束判定手段を含み、逐次入力される少なくとも１つの文字からなる文字列の各々を連結して得られる入力文字列に対して言語解析処理を含む自然言語解析処理を行う自然言語解析処理装置における自然言語解析処理方法であって、前記部分問題生成手段によって、前記入力文字列に対して前記言語解析処理を行う問題を、予め定義した文字単位又は文字列単位で前記言語解析処理を行う部分問題に分解したときの前記部分問題を、前記文字単位又は文字列単位の入力毎に、逐次生成し、前記部分問題記憶手段によって、前記部分問題生成手段により逐次生成された部分問題の集合を記憶し、前記グループ作成手段によって、前記部分問題生成手段により前記部分問題が逐次生成される毎に、前記部分問題記憶手段に記憶された前記部分問題の集合について、各部分問題が少なくとも２以上のグループに属するように、前記部分問題の全集合に対する任意の部分集合で構成されるＳ個のグループを作成して前記Ｓ個の計算ノードに割り当て、前記Ｓ個の計算ノードによって、前記自然言語解析処理を行い、前記制約条件更新手段によって更新し、前記グループ活性状態設定手段によって設定し、前記制約条件非活性状態設定手段によって設定し、前記収束判定手段によって判定することを含み、前記Ｓ個の計算ノードの各々によって前記自然言語解析処理を行うことは、前記部分解更新手段によって、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の全集合に対する部分集合について、前記２以上のグループに属する各極小部分問題の解が一致する制約条件に基づいて、前記部分集合の各部分問題の解を更新し、前記グループ非活性状態設定手段によって、前記部分解更新手段によって更新された前記部分集合の各部分問題の解が、前回更新された前記部分集合の各部分問題の解と全て一致している場合に、前記計算ノードの前記部分更新手段による更新処理を行わないことを表すグループ非活性状態を設定し、前記制約条件活性状態設定手段によって、各部分問題について、前記部分解更新手段によって更新された前記部分問題の解が、前回更新された前記部分問題の解と一致していない場合に、前記制約条件に従って前記部分問題の解を一致させるときの解である制約条件パラメータについて設定されている、前記制約条件パラメータの更新処理を行わないことを表す制約条件非活性状態を解除することを含み、前記制約条件更新手段は、各計算ノードの前記部分解更新手段によって更新された前記部分集合の各部分問題の解に基づいて、各部分問題について、前記部分問題の前記制約条件パラメータを更新し、前記グループ活性状態設定手段は、各部分問題について、前記制約条件更新手段により更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致しない場合には、前記部分問題が属するグループが割り当てられた前記計算ノードについて設定されている前記グループ非活性状態を解除し、制約条件非活性状態設定手段は、各部分問題について、前記制約条件更新手段によって更新された前記制約条件パラメータが、前回更新された前記制約条件パラメータの値と一致している場合に、前記部分問題の前記制約条件パラメータについて前記制約条件非活性状態を設定し、前記収束判定手段は、前記制約条件パラメータの値が収束したか否かを判定し、前記制約条件パラメータの値が収束したと判定するまで、各計算ノードの前記部分解更新手段による更新、前記グループ非活性状態設定手段による設定、前記制約条件活性状態設定手段による設定、前記同期手段による通知及び取得、前記制約条件更新手段による更新、前記グループ活性状態設定手段による設定、並びに前記制約条件非活性状態設定手段による設定を繰り返すことを含む自然言語解析処理方法であって、前記グループ非活性状態が設定されている前記計算ノードは、前記部分解更新手段による更新を行わず、前記制約条件更新手段は、前記制約条件非活性状態が設定されている前記制約条件パラメータの更新を行わず、前記グループ非活性状態が設定されている前記計算ノードにおける前記部分集合の各部分問題の解は、前記部分解更新手段によって最後に更新された前記部分集合の各部分問題の解とする。
【００１９】
第３の発明及び第４の発明によれば、逐次入力される入力文字列に対して自然言語解析処理を行う問題を部分問題の集合に分割してグループを作成し、２以上のグループに属する部分問題の解が一致する制約条件に基づいて、各計算ノードにおいて、割り当てられた部分問題の部分集合について、グループに設定された活性状態又は非活性状態に基づいて、解を更新し、各計算ノードで更新された部分問題の解を用いて、制約条件パラメータに設定された活性状態又は非活性状態に基づいて、制約条件パラメータを更新することを収束するまで繰り返すことにより、計算量の増大を抑制して、逐次入力される入力文字列毎に精度良く自然言語解析処理を行うことができる。
【００２０】
また、第３の発明によれば、前記部分解更新手段は、前記グループ作成手段によって割り当てられた前記グループの前記部分問題の部分集合について、前回更新されたラグランジュ未定乗数、前記部分集合の各部分問題の解、及び前記制約条件パラメータを用いて予め定められた目的関数の値を最適化するように、前記ラグランジュ未定乗数を更新し、前記更新された前記ラグランジュ未定乗数を用いて、前記目的関数の値を最適化するように、前記部分集合の各部分問題の解を更新し、前記制約条件更新手段は、各計算ノードの前記部分解更新手段によって更新された前記ラグランジュ未定乗数及び前記部分集合の各部分問題の解に基づいて、前記目的関数の値を最適化するように、各部分問題について、前記制約条件パラメータを更新するようにすることもできる。
【００２１】
また、本発明のプログラムは、コンピュータを、請求項１〜請求項４に記載の自然言語解析処理装置を構成する各手段として機能させるためのプログラムである。
【発明の効果】
【００２２】
以上、説明したように、本発明の自然言語解析処理装置、方法、及びプログラムによれば、計算量の増大を抑制して、逐次入力される入力文字列に対して精度よく自然言語解析処理を行うことができる。
【図面の簡単な説明】
【００２３】
【図１】「逐次処理方式」と「一括処理方式」の違いの例を示す図である。
【図２】極小部分問題のグループを作成する方法を説明するための図である。
【図３】本発明の第１の実施の形態に係る自然言語解析処理装置の構成を示す概略図である。
【図４】本発明の第１の実施の形態に係る自然言語解析処理装置の計算ノードにおける自然言語解析処理ルーチンの内容を示すフローチャートである。
【図５】本発明の第１の実施の形態に係る自然言語解析処理装置の他の例を示す概略図である。
【図６】本発明の第２の実施の形態に係る自然言語解析処理装置の構成を示す概略図である。
【図７】本発明の第２の実施の形態に係る言語解析制御装置の構成を示す概略図である。
【図８】本発明の第２の実施の形態に係る言語解析装置の構成を示す概略図である。
【図９】単語区切り、品詞タグ付け、固有表現抽出、文節区切り、及び文節間の係り受けの例を示す図である。
【図１０】従来技術における履歴ベースの逐次解析法を示す図である。
【図１１】従来技術における動的計画法に基づく解析の例を示す図である。
【発明を実施するための形態】
【００２４】
以下、発明の概要について詳細に説明する。
【００２５】
＜発明の概要＞
本発明では、非特許文献４（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.）で提案されている整数計画問題を解くための一つの方法論である双対分解＋拡張ラグランジュ緩和（ＤＤ−ＡＤＭＭ）法を用いて、全体最適性を保持しつつ逐次解析を実現する。ＤＤ−ＡＤＭＭ法の大きな特徴としては、実際に解きたい問題を小さなグループに分割して解く方法である。また、この特徴により得られる重要な性質として、分割した個々のグループは、他のグループと独立に解くことが出来るという点であり、相対的に計算が容易になるといった利点がある。
【００２６】
また、独立に解くことが出来る性質から、個々のグループを解く際に、他のグループの解析結果には直接影響を与えられないため、将来入力されることで生成されるグループは事実上知らなくても、部分的に解析結果を得ることが可能である。
【００２７】
本発明では、逐次入力に対して前の処理結果を再利用することで計算コストの削減を図る。また、さらにグループの活性／非活性状態制御部を導入し、最適解の探索時に各グループを、計算コストを使って計算すべきか、計算不要であるかを制御する。
【００２８】
本発明の実施の形態として、オンライン・リアルタイム日本語文書校正システムで用いられる日本語形態素解析器において、人間が文書を入力するのに合わせて逐次解析結果を出力するシステムを想定する。
【００２９】
逐次入力で一回に入力されるものは、一回のかな漢字変換確定後の文字列とする。そのため、最小で一文字であり、最長は一文書となる。一般的には、逐次入力で一回に入力される文字列は、１から３単語程度や一文節程度である。一回に入力される文字列は可変長なので、ここでは、一回に入力される文字列を「一入力単位」とする。処理は以下のように行われる。
【００３０】
・開始状態：何も入力されていない状態（初期状態）
・処理１：ユーザが一入力単位をシステムに入力
・処理２：システムが一入力単位を受理し、それまでに入力されたテキストと合わせて解析を行う。
・処理３：得られた解析結果を出力
・処理４：次の入力を待機
・（以降処理１〜４の繰り返し）
・終了状態：ユーザの入力が終了（明示的な終了宣言が無くてもよい）
【００３１】
本発明は、上記処理２の逐次入力される一入力単位に対して逐次最適な自然言語解析結果を提示する処理部に相当する。以下、上記処理２に相当する処理方法を説明する。
【００３２】
まず、本発明が対象とする「逐次処理」による自然言語解析処理装置について定義する。ここでは、「逐次処理方式」との対比として、入力テキストが最後まですべて入力後に処理を開始する方式を「一括処理方式」とする。「逐次処理方式」と「一括処理方式」では、最終的に入力される文書は完全に同じものであるとする。処理方式の違いは、入力のされ方に依存して変わる。
【００３３】
逐次処理方式では、一入力単位がいくつかの時刻にわかれて各時刻毎に部分的に入力されるという状況を想定する。「逐次処理方式」と「一括処理方式」の違いを図１に示す。
【００３４】
一入力単位は、最終的に時刻Ｔまで入力がなされると仮定する（０≦ｔ≦Ｔ）。現在時刻をｔとし、その一時刻前をｔ−１とし、ｔ＝０を何も入力がされていない状態（初期状態）とする。
【００３５】
ここで、注意点として、仮にＴ＝１の場合には、入力全体が一時刻で入力されたことを意味するので、これは一括処理方式と同じ処理になることを意味する。つまり、逐次処理方式は間接的に一括処理方式を包含する処理の枠組みとなっている。逐次処理方式が可能であれば、一括処理方式の状況でも逐次処理方式で対応可能であるという方式としての利点がある。
【００３６】
逆に、一括処理方式で逐次処理に対応するのは、方法論としては困難である。ただし、実際にはナイーブな適用法として、逐次入力される一入力単位に対して入力毎に一括処理方式を繰り返し行うことを意味するので、一般的には計算量的な困難性が発生する。
【００３７】
ここまでの、逐次処理方式と一括処理方式との比較でわかるように、逐次処理方式としての要件は、前時刻の処理結果を有効に活用して、効率的に処理することが出来る方法である。例えば、従来の履歴ベースの方法であれば、前時刻までの解析結果は正しいと仮定して、その解析結果を利用して現時刻に新しく入ってきた一入力単位の処理を行う方法になっている。
【００３８】
本発明は、処理方式としては一括処理方式の解法をベースにするが、全体が入力されていない途中状態でも、その時点での最適解を得つつ、現時刻で新たに入力された一入力単位を、前時刻の処理結果をうまく利用して効率的に新しい解を得る処理方法に相当する。次に本発明のベースとなる一括処理方式について説明する。
【００３９】
本発明では、基本的な考え方として処理の最小単位を事前に決定する。処理の最小単位とは、形態素解析処理において、問題を定義する上で最も小さい問題として定義できるものに相当する。最小単位の問題は、解きたい問題の部分に相当することから、ここでは、最小単位の問題を「極小部分問題」と呼ぶ。そして、極小部分問題のインデックスをｒで表す。また、すべての極小部分問題のインデックスの集合をＲで表す事とする。よって、解きたい問題は、｜Ｒ｜個の極小部分問題で構成されている。なお部分問題の一例が極小部分問題である。
【００４０】
次に、一入力単位を一つの入力と考えると、形態素解析は、極小部分問題の集合により定義される。よって、これらの問題の解空間をベクトルの集合Ｙで表すとする。入力が与えられた時に得られる一つの出力をベクトルＹ∋ｚであらわす。ここでは、極小部分問題の解はベクトルの一つの要素ｚｉに相当する。
【００４１】
次に、本発明では、いくつかの極小部分問題でグループを構成し、グループの集合で問題を表現する。この時、各グループは極小部分問題を重複して含むことが可能である。グループの作り方は任意であるが、以下の２つの点を満たすようにする。１点目は、解きたい問題全域をカバーする形でグループを構成することであり、２点目は、各極小部分問題は複数のグループに属することである。ここでは、作成した一つのグループを全体の問題に対する一部分の問題と考える。よって、一つのグループで一つの最適化問題として解くことになる。
【００４２】
ここで、グループをＳ個作成したとする。ｓ番目のグループに含まれる解空間の部分空間をＹｓとする。つまりＹｓ⊆Ｙである。このとき、ｓ番目のグループに含まれるｒ番目の極小部分問題の解をｚｓ（ｒ）とする。グループを作成する例を図２に示す。
【００４３】
Ｒｓをｓ番目のグループに含まれる極小部分問題のインデックスの集合とする。次に、ＲｓをＲ⊆Ｕｓ＝１ＳＲ´ｓ、および、Ｒｓ＝Ｒ´ｓ∩Ｒとなる集合とする。これは、極小部分問題ではないが全体の問題を解くうえで有効な補助的な部分問題があるので、それらの部分問題を含めてグループを構成したい場合に対応するための拡張である。つまり、ここではＲ´ｓ＼Ｒに相当する集合に含まれるインデックスは、極小部分問題ではないが問題を解く上での有効な補助的な部分問題のインデックスに相当する。
【００４４】
ｓ番目のグループで得られる出力に対して、出力の良さを計算する関数をｆｓとする。ここでは、ｆｓ（zｓ）の値が大きいほど、出力として良いものであるという仮定のもとに計算される値とする。この時、自然言語解析処理を行う問題全体は下記（１）式に示す最適化問題として定式化できる。
【００４５】
【数１】
2014149786.tif 000003
【００４６】
ここで、ｚｓはグループｓに含まれる極小部分問題の解の集合とする。また、ｚは、０または１の値をとる極小部分問題の解を表すｚｓ（ｒ）の全集合とする。この最適化問題は、Ｓ個のグループが独立に、各グループが担当する極小部分問題に対する出力ｚｓ（ｒ）で最も良いと思われる部分解を選択する問題を、各グループの部分解はｕ（ｒ）のベクトルと一致することを制約条件として解いていることに相当する。この定式化のポイントは、制約条件ｚｓ（ｒ）＝ｕ（ｒ）の部分にあり、各グループｓで、ｒ番目の極小部分問題を含む場合、ｚｓ（ｒ）の値はすべてｕ（ｒ）と一致することを解の条件とするということを意味している。これは、つまり、個々のグループでは、解ｚｓ（ｒ）を独立に決定するが、制約条件ｚｓ（ｒ）＝ｕ（ｒ）により全体として整合性が取れる解に限定することができるということである。この制約条件の式とラグランジュ緩和とを用いて、最適化のための目的関数を得る。なお、上記（１）式は、任意のスコア関数ｆｓにより定義されるスコアが最大になる極小部分問題の解ｚｓ（ｒ）の集合を求めることを意味する。ただし、解きたい問題は、任意のＳ個のグループに分割できることが条件である。つまり、分割したＳ個のグループの線形和によって得られるスコアが最大になるものが解となることになる。
【００４７】
実際の形態素解析問題では、例えば、単語分割に関しては、文字間に分割候補点があるとして、その分割候補点で分割されるか（ｚｓ（ｒ）＝１）、または、されないか（ｚｓ（ｒ）＝０）を判定する整数計画問題とみなすことが出来る。また、品詞付与の場合は、各単語に事前に定義された品詞から一つを選択する問題であり、各品詞に一つの極小部分問題の解ｚｓ（ｒ）を割り当て、その中から一つが１でそれ以外がすべて０になるという制約を持った整数計画問題を解くことに相当する。また、品詞付与と同様に、読みや原形推定も、各単語の読みや原形候補の中から一つを選択する問題であり、各候補に一つの極小部分問題の解ｚｓ（ｒ）を割り当て、その中から一つが１でそれ以外がすべて０になるという制約を持った整数計画問題を解くことに相当する。このような分割や割り当て問題の全体が最も適している解が形態素解析の結果として選ばれる。
【００４８】
実際に整数計画問題を解く際には、（拡張）ラグランジュ緩和を用いて下記（２）式の最適化の目的関数を得る。
【００４９】
【数２】
2014149786.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の項ρ／２（ｚｓ（ｒ）―ｕ（ｒ））２を追加して問題を下記（３）式に示すように２次式の形に変形することで問題をより解きやすい形とする。
【００５１】
【数３】
2014149786.tif 000005
【００５２】
これは、最適値で元の問題と一致する。また、以降の式展開を簡単にするためにλｓ（ｒ）＝−ραｓ（ｒ）とし、下記（４）式を得る。
【００５３】
【数４】
2014149786.tif 000006
【００５４】
実際の解は、以下の反復処理により得る。
・初期化：繰り返しを管理する変数ｋ＝０
・処理１：ラグランジュ未定乗数αｋｓ（ｒ）を更新
・処理２：各極小部分問題の解ｚｋｓ（ｒ）を各極小部分問題毎に独立に推定
・処理３：制約条件パラメータ（各極小部分問題の解の平均）であるｕｋ（ｒ）を更新
・処理４：収束判定
収束していたらｕ＾（ｒ）＝ｕｋ（ｒ）とする。していない場合にはｋ＝ｋ＋１として処理１へ戻る。
・出力：ｕ＾を出力する。
【００５５】
以下、上記処理１〜４の処理を詳細に説明する。
【００５６】
まず、処理１について説明すると、処理１として、各計算ノードのラグランジュ未定乗数αｓ（ｒ）を更新する。ｚとｕを固定したとき個々のαｓ（ｒ）の最適値の方向は、目的関数Ｌ（ｚ、ｕ、α）のαｓ（ｒ）に関する偏微分方向である。
【００５７】
【数５】
2014149786.tif 000007
【００５８】
上記（５）式の関係から以下の更新式を得る。
【００５９】
【数６】
2014149786.tif 000008
【００６０】
この上記（６）式の更新式は、各極小部分問題毎に独立に計算可能である。
【００６１】
次に処理２について説明すると、処理２は、各極小部分問題の解ｚｋｓ（ｒ）を推定する処理であり、反復計算ｋの時点で、αとｕを固定した時、各ｚｓ（ｒ）の最適解は、目的関数Ｌ（ｚ、ｕ、α）を最大にするｚｓ（ｒ）を見つける問題である。
【００６２】
【数７】
2014149786.tif 000009
【００６３】
ここで、ｆｓは下記（８）式であると仮定する。
【００６４】
【数８】
2014149786.tif 000010
【００６５】
ここで、上記（８）式のθｓ（ｒ）は、グループｓでのｒに関するスコアを表わしており、この値は外部から与えられるものとする。つまり、この最適化の中では定数として扱われる。定義に従って、上記（４）式からｚに関係する項のみ取り出すと下記（９）式になる。
【００６６】
【数９】
2014149786.tif 000011
【００６７】
上記（７）式の計算も各グループｓ毎に計算することが可能である。つまり、各グループｓ毎に、下記（１１）式の最大化問題を解けばよい。
【００６８】
【数１０】
2014149786.tif 000012
【００６９】
次に、処理３について説明すると、処理３として、制約条件パラメータｕ（ｒ）を更新する。ｚとαを固定したときｕの最適解は、目的関数Ｌ（ｚ、ｕ、α）に対して、ｕ（ｒ）に関する偏微分の値が０になる点である。その関係から下記（１２）式の関係式が得られる。
【００７０】
【数１１】
2014149786.tif 000013
【００７１】
つまり、ｕはｚｓ（ｒ）の平均とαｓ（ｒ）の平均を足したものを意味し、制約条件パラメータｕ（ｒ）の更新には、すべてのαｓ（ｒ）とｚｓ（ｒ）が必要である。
【００７２】
次に、処理４について説明すると、処理４として、処理３で得られたｕが最適値になっているか（収束しているか）判定する。二つの小さな正の実数ε１、ε２を与え、下記（１３）式及び（１４）式を満たした際に収束したと判定する（非特許文献５を参照）。
【００７３】
【数１２】
2014149786.tif 000014
【００７４】
収束判定で、収束していなかった場合は、ｋ＝ｋ＋１として処理１に戻る。最適値に収束していると判定された場合は、繰り返し処理を終了し、解ｕを出力する。以上が一括処理の説明である。
【００７５】
次に、上述の言語解析問題を整数計画問題で定式化し、双対分解＋拡張ラグランジュ緩和により問題を解く方法で、逐次処理を実現する方法について説明する。
【００７６】
上述の一括処理では、最適化変数はすべて０などで初期化して最適化を開始するが、本発明では、基本的に、逐次入力に効率的に対応するために、前時刻の処理結果を初期値とする。概要として、前時刻までの処理結果に関しては、現時刻で新しく入力された一入力単位の解析に影響を受けない部分に関しては、解析結果は前時刻で得られたものと同じものが得られ、現時刻で新しく入力された一入力単位と依存関係のある部分の解析結果は、改めて解析結果が評価される、という処理になる。このような方法により、前時刻の最適化の結果を効率的に再利用できるので、毎入力毎に最適化を行う方法と比べて実際の処理時間を大幅に削減できる。
【００７７】
このような効率的な処理は、双対分解＋ラグランジュ緩和法の「個別の部分問題は独立に解くことができる」という性質によって効果的に導入できる。一方、整数計画法のソルバーなどでは、このような性質をもたないため、部分的、効率的かつ逐次的に解を修正していく処理には適さない。上記（１）式を逐次処理用に拡張すると下記（１５）式のように示せる。
【００７８】
【数１３】
2014149786.tif 000015
【００７９】
時刻ｔまでに入力されたテキストで生成されるグループの総数をＳｔと書く。また、最終時刻Ｔで最後まで入力がなされた場合に最終的に生成されるグループの総数をＳＴとする。ただし、これは、上記（１）式中のＳと等しい値Ｓ＝ＳＴであり、逐次処理をしない場合に一括して入力を与えた際に得られるグループの総数と一致することとする。
【００８０】
このとき、時刻ｔに新たに生成されたグループのスコアの総和
【数１４】
2014149786.tif 000016
の最大値（上記（１５）式の右辺第二項）を求めるだけの問題であれば、従来の履歴ベースの方法と等価である。つまり、履歴ベースの方法との差異は、時刻ｔ−１までに生成されたグループのスコアの最大値も同時に考慮しつつ、現在時刻ｔまでのすべてのグループのスコアの最大値を求めることである。ただし、特に工夫がなければ、これは一括処理方式を単に時刻毎に繰り返し実行することと等価になってしまう。そのため、本発明では、時刻ｔ−１までの処理結果をうまく利用することで、単に繰り返し実行するより大幅に計算量を少なくして逐次処理を可能とする。
【００８１】
まず、最も単純な方法としては、時刻ｔ−１の最適解を得た状態を時刻ｔの初期値にして利用する方法が考えられる。時刻ｔ−１と時刻ｔの最適解が近ければ、この方法は直感的にうまく働くと考えられる。ただし、時刻変化によって変数や制約が増減しているので、単純に前時刻の最終状態を初期状態としても効果があるかは必ずしも自明ではない。また、最適化アルゴリズムによっては、初期値があまり効果的に働かない場合もある。
【００８２】
しかし、本発明で利用する双対分解に基づく最適化アルゴリズムは、他の最適化アルゴリズムと比べ、各制約とその変数が他の制約やそこで扱われる変数と独立になるため、時刻ｔ−１から時刻ｔに変化した際に増減するグループの最適化変数ｚｓ（ｒ）は他の変数との整合性等を考慮せず容易に追加／削除できるという利点がある。また、最適解を求めるアルゴリズムも変数を固定しての反復計算なので、徐々に最適解に近づくアルゴリズムである点も時刻ｔ−１の状態を利用する効果が大きいと期待できる。
【００８３】
そのため、手続きとしては、時刻ｔ−１から時刻ｔに変化し、整数計画問題Ｐｔ−１から、整数計画問題Ｐｔに移行した際に、まずＰｔ−１との制約（部分問題）の観点での差分を取得する。このとき、追加に関しては、ｚｓ（ｒ）＝０、αｓ（ｒ）＝０とし、新たにｒが追加されたのであればｕ（ｒ）＝０として、新たな最適化変数を生成する。逆に、削除の時は、ｓに関するすべてのｚｓ（ｒ）、αｓ（ｒ）を削除し、削除したｚｓ（ｒ）が最後のｕ（ｒ）に関する要素であれば、ｕ（ｒ）も削除する。これらの増減したグループ以外のグループおよび等式制約の変数は、Ｐｔ−１の最終状態を引き継ぐものとする。
【００８４】
非特許文献６（Terry Koo, Alexander M. Rush, Michael Collins, Tommi Jaakkola, and David Sontag. Dual decomposition for parsing with non-projective head automata. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 1288−1298, Cambridge, MA, October 2010. Association for Computational Linguistics.）及び非特許文献７（Andre Martins, Noah Smith, Mario Figueiredo, and Pedro Aguiar. Dual decom-position with many overlapping components. In Proceedings of the 2011 Con-ference on Empirical Methods in Natural Language Processing, pages 238−249.Association for Computational Linguistics, July 2011.）では、最適化中に多くの最適化変数が一定の値で固定する状態が続く点に着目し、そういった変数を最適化から外すことにより最適化速度を向上させる方法を採用している。本発明では、こういった方法を更に発展させ、より緻密な最適化変数の状態制御の方法を提案する。結果として、提案する状態制御法は、本発明が取り上げる動的変化整数計画問題系列のような、最適化変数や制約が動的に変化する状況でその効果を発揮する方法である。
【００８５】
まず、最適化中の不要な計算を削減する仕組みとして、各グループｓと等式制約の変数ｕ（ｒ）毎に、それぞれ「活性」「非活性」の二値の状態を持つフラグＦｓとＦｒを付与する。「活性」状態（Ｆｓ＝１またはＦｒ＝１）とは、ｓまたはｒは、通常の最適化処理を行うことを意味し、「非活性」状態（Ｆｓ＝０またはＦｒ＝０）とは、ｓまたはｒは、最適化処理の計算から除外される事を意味する。
【００８６】
まず、上記（６）式〜（１４）式で表されるアルゴリズムは、上記（６）式〜（１１）式と、上記（１２）式〜（１４）式という二種類の計算ブロックで表現でき、それぞれ一つのｆоｒ文の形で書き直すことが出来る。また、上記（６）式〜（１１）式の処理では、ｕ（ｒ）を定数として計算するので、各グループｓ毎に独立な変数ｚｓ（ｒ）とαｓ（ｒ）のみが変数となる計算となり、グループｓの単位で計算することが出来る。一方、上記（１２）式〜（１４）式の処理では、ｚｓ（ｒ）は定数として計算するので、すべて等式制約に基づく変数ｕ（ｒ）の単位で計算することが出来る。Ｆｓ、Ｆｒのフラグは以下の条件で切り替わる。
【００８７】
・Ｆｓ＝１  →  Ｆｓ＝０
対応するグループｓに含まれるすべての変数ｚｓ（ｒ）がｚｋｓ（ｒ）＝ｚｋ−１ｓ（ｒ）となったとき、自身のグループｓは収束したと仮定。以降、Ｆｓ＝０が続く限り、グループｓに対する上記（６）式〜（１１）式で表される処理は行われない。
【００８８】
・Ｆｒ＝１  →  Ｆｒ＝０
対応するｒに対しｕｋ（ｒ）＝ｕｋ−１（ｒ）となったとき、自身の変数ｕ（ｒ）は収束したと仮定する。以降、Ｆｒ＝０が続く限り、ｕ（ｒ）に対する上記（１２）式〜（１４）式の処理は行わない。ただし、収束判定用の値はキャッシュしておき、非活性状態が続いても、キャッシュした値を用いることで適切に収束判定用の値を計算する。
【００８９】
上記２つの状態以降の条件は比較的緩めに設定してある。よって、かなりアグレッシブに本来収束していない場合も非活性状態へ移行する可能性がある。この問題を回避するために非活性状態から活性状態に戻す処理を下記に示す。
【００９０】
・Ｆｓ＝０  →  Ｆｓ＝１
Ｒｓ∋ｒとする。制約条件パラメータｕｋ−１（ｒ）≠ｕｋ（ｒ）のとき、つまりグループｓに含まれる極小部分問題の解ｚｓ（ｒ）と共有関係にある制約条件パラメータｕ（ｒ）が更新されたことを意味する。つまり、グループの解が制約条件パラメータｕ（ｒ）に一致していなかったことを示しているので、再度最適値を推定するためにグループｓを活性状態に戻す。
【００９１】
・Ｆｒ＝０  →  Ｆｒ＝１
あるグループｓの中のｚｓ（ｒ）がｚｋ−１ｓ（ｒ）≠ｚｋｓ（ｒ）のとき、すなわち、制約条件パラメータｕ（ｒ）の値が変化する可能性があるので、再度最適解を評価するために活性状態にする。
【００９２】
活性状態、非活性状態のポイントは、フラグを非活性化する際には、自分自身のフラグしか変更することができないという点、及び活性化する際には、自分とは別カテゴリのフラグしか変更することが出来ないという点である。これにより、状態制御がスタックすることがないように設計されている。
【００９３】
このように、非活性状態から活性状態へ変化させる処理を導入することで、動的変化整数計画問題系列の時刻変化による制約や最適化変数の増減に対応することが可能となる。つまり、容易に非活性状態から活性状態へ移行することが可能な枠組みを持つため、最適化変数の増減など周囲の状況が変化した場合でも、単純なフラグ管理で最小の計算で最適化を行うことができる。
【００９４】
＜第１の実施の形態＞
＜システム構成＞
本発明の第１の実施の形態に係る自然言語解析処理装置１００は、逐次与えられる自然言語解析処理の対象の一入力単位の文字列を逐次入力として受け取り、逐次入力された文字列を連結した入力文字列に対する自然言語解析処理の結果である日本語形態素解析の結果を逐次出力する。この自然言語解析処理装置１００は、ＣＰＵと、ＲＡＭと、後述する自然言語解析処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。図３に示すように、自然言語解析処理装置１００は、入力部１０と、演算部２０と、出力部５０とを備えている。
【００９５】
入力部１０は、逐次入力された一入力単位の文字列を逐次受け付ける。また、入力部１０は、人手により入力された計算ノード数Ｓとパラメータρを逐次受け付ける。
【００９６】
演算部２０は、極小部分問題生成部２２と、極小部分問題記憶部２４と、グループ作成部２６と、Ｓ個の計算ノード３０１〜３０ｓと、パラメータ記憶部４６と、を備えている。なお、計算ノード３０１〜３０ｓのうちの任意の計算ノードを示す場合には、計算ノード３０と称することとする。
【００９７】
極小部分問題生成部２２は、入力部１０により逐次入力された文字列を連結した入力文字列に対して言語解析処理を行う問題を分割して得られる予め定義された極小部分問題を、逐次入力された一入力単位の文字列毎に生成し、極小部分問題の集合を生成する。
【００９８】
極小部分問題記憶部２４は、極小部分問題生成部２２において逐次生成された極小部分問題の集合を記憶している。
【００９９】
グループ作成部２６は、極小部分問題生成部２２によって極小部分問題が逐次生成される毎に、極小部分問題記憶部２４に記憶されている極小部分問題の集合について、各極小部分問題が少なくとも２以上のグループに属するように、Ｓ個のグループを作成し、Ｓ個の計算ノード３０１〜３０ｓに割り当てる。また、グループ作成部２６は、入力されたパラメータρを、Ｓ個の計算ノード３０１〜３０Ｓの各々に通知する。なお、極小部分問題記憶部２４に記憶されている各極小部分問題の各々については、前回割り当てられたグループと同様のグループに所属するようにグループを作成する。
【０１００】
Ｓ個の計算ノード３０１〜３０ｓの各々は、パラメータ更新部３２と、部分解更新部３４と、第１フラグ判定部３６と、同期部３８と、制約条件更新部４０と、第２フラグ判定部４２と、収束判定部４４と、を備えている。各Ｓ個のパラメータ更新部３２と、部分解更新部３４と、第１フラグ判定部３６と、同期部３８と、制約条件更新部４０と、第２フラグ判定部４２と、収束判定部４４と、が存在することになるが、同様の機能を有する処理部は同じ番号で表している。また、Ｓ個の計算ノード３０１〜３０ｓの各々は、極小部分問題生成部２２によって極小部分問題が逐次生成される毎に、パラメータ更新部３２、部分解更新部３４、第１フラグ判定部３６、同期部３８、制約条件更新部４０、第２フラグ判定部４２、及び収束判定部４４による各処理を行う。なお、第１フラグ判定部３６は、グループ非活性状態設定手段と、制約条件活性状態設定手段の一例であり、第２フラグ判定部４２は、グループ活性状態設定手段と、制約条件非活性状態設定手段の一例である。
【０１０１】
パラメータ更新部３２は、グループ作成部２６によって割り当てられた自グループｓに含まれる各極小部分問題ｒに対するラグランジュ未定乗数αｓ（ｒ）を更新する。具体的には、各極小部分問題ｒに対して、上記（６）式に従って、ラグランジュ未定乗数αｓ（ｒ）を更新する。上記（６）式の更新式は、各計算ノード３０で独立に計算できるため、他の計算のノード３０と通信などを行う必要がない。なお、ラグランジュ未定乗数αｓ（ｒ）の初期値は、パラメータ記憶部４６に記憶されている前回の自然言語解析処理ルーチンの実行の結果により得られたラグランジュ未定乗数αｓ（ｒ）の値とする。自然言語解析処理ルーチンが一度も実行されていない場合には、ラグランジュ未定乗数αｓ（ｒ）の初期値は０とする。また、自グループｓのグループフラグＦｓ＝０の場合、パラメータ更新部３２は、各極小部分問題ｒに対するラグランジュ未定乗数αｓ（ｒ）の更新を行わず、初期値、又は前回更新された値をラグランジュ未定乗数αｓ（ｒ）として保持する。        
【０１０２】
部分解更新部３４は、グループ作成部２６によって割り当てられた自グループｓに含まれる極小部分問題ｒの部分集合について、当該計算ノード３０ｓにおける各極小部分問題の解ｚｓ（ｒ）を更新する。具体的には、上記（１１）式に示す最大化問題を解くことにより各極小部分問題の解を更新する。なお、各極小部分問題の解ｚｓ（ｒ）の初期値は、パラメータ記憶部４６に記憶されている前回の自然言語解析処理ルーチンの実行の結果により得られた各極小部分問題の解ｚｓ（ｒ）の値とする。自然言語解析処理ルーチンが一度も実行されていない場合には、各極小部分問題の解ｚｓ（ｒ）の初期値は０とする。また、自グループｓのグループフラグＦｓ＝０の場合、部分解更新部３４は、各極小部分問題の解ｚｓ（ｒ）の解の更新を行わず、初期値、又は前回更新された値を各極小部分問題の解ｚｓ（ｒ）の値として保持する。
【０１０３】
第１フラグ判定部３６は、部分解更新部３４により得られた自グループｓに含まれる各極小部分問題の解ｚｋｓ（ｒ）が、前回得られた解ｚｋ−１ｓ（ｒ）と一致するか否かを判定する。自グループｓに含まれる全極小部分問題についてｚｋｓ（ｒ）＝ｚｋ−１ｓ（ｒ）の場合、計算ノード３０ｓに割り当てられたグループｓは収束したとして、自グループｓのグループフラグＦｓに非活性化を表す０の値を付与する。また、自グループｓに含まれる各極小部分問題ｒについて、ｚｋｓ（ｒ）≠ｚｋ−１ｓ（ｒ）となる極小部分問題ｒが存在する場合、当該極小部分問題ｒの制約条件パラメータｕ（ｒ）の値が変化する可能性があるとして、ｕ（ｒ）に対する制約フラグＦｒに活性化を表す１の値を付与する。
【０１０４】
同期部３８は、当該計算ノード３０で今回更新され、又は保持されたラグランジュ未定乗数αｓ（ｒ）及び各極小部分問題の解ｚｓ（ｒ）を、自分以外のすべての計算ノード３０ｉへ通知する。また、同期部３８は、他の計算ノード３０ｉすべてから通知された、今回更新され、または保持されたラグランジュ未定乗数αｓ（ｒ）及び各極小部分問題の解ｚｓ（ｒ）を受け取る。この処理によって、個々の計算ノード３０はすべての計算ノード３０ｓの持つラグランジュ未定乗数αｓ（ｒ）と各極小部分問題の解ｚｓ（ｒ）の値を取得することができる。
【０１０５】
制約条件更新部４０は、他の計算ノード３０ｓすべてから受け取ったラグランジュ未定乗数αｓ（ｒ）と各極小部分問題の解ｚｓ（ｒ）を用いて、上記（１２）式により、制約条件に従って極小部分問題の解を一致させるときの解を示す制約条件パラメータｕ（ｒ）を、全ての極小部分問題ｒの各々について更新する。なお、ｕ（ｒ）の初期値は、パラメータ記憶部４６に記憶されている前回の自然言語解析処理ルーチンの実行の結果により得られたｕ（ｒ）の値とする。自然言語解析処理ルーチンが一度も実行されていない場合には、制約条件パラメータｕ（ｒ）の初期値は０とする。また、制約フラグＦｒ＝０の場合、制約条件更新部４０は、ｕ（ｒ）の更新を行わず、初期値、又は前回更新された値をｕ（ｒ）の値として保持する。
【０１０６】
また、個々の計算ノード３０で独立にｕ（ｒ）を求めているが、得られるｕ（ｒ）はすべての計算ノード３０で一致する。処理方法としては、任意のひとつの計算ノード３０でｕ（ｒ）を計算し、そのあとに各計算ノード３０に通知するといった処理を行うようにしてもよい。ただし、その場合には、選択された計算ノード３０の計算が終了し、結果が通知されるまで、それ以外の計算ノードは待機する必要がある。本実施の形態では、個々の計算ノード３０で同じ計算を行う方式をとった場合を例に説明する。
【０１０７】
第２フラグ判定部４２は、全ての極小部分問題ｒの各々について、制約条件更新部４０により得られたｕ（ｒ）がｕｋ−１（ｒ）と一致するか否かを判定する。ｕｋ（ｒ）＝ｕｋ−１（ｒ）の場合、自身の変数ｕ（ｒ）は収束したとして、制約フラグＦｒに非活性化を表す０の値を付与する。また、ｕｋ（ｒ）≠ｕｋ−１（ｒ）の場合、制約式ｕ（ｒ）の値が更新されたとして、当該極小部分問題ｒを含むグループの解が制約条件パラメータｕ（ｒ）と一致しないことになるので、当該極小部分問題ｒを含むグループｓのグループフラグＦｓに活性化を示す１の値を付与する。
【０１０８】
収束判定部４４は、上記（１３）式、及び（１４）式を用いて、制約条件更新部４０で得られたパラメータｕが収束して最適値になっているか判定する。具体的には、二つの小さな性の実数ε１、ε２を与え、上記（１３）式、及び（１４）式を満たした場合に、ｕが最適値に収束したと判定する。
【０１０９】
収束判定で、最適値に収束していない場合は、ｋ＝ｋ＋１として、パラメータ更新部３２による処理に戻る。最適値に収束していると判定された場合は、繰り返し処理を終了する。
【０１１０】
この収束判定の処理もｕ（ｒ）と同様に任意のひとつの計算ノード３０で行い、その結果を全体に通知するようにしてもよい。しかし、同期処理が必要となるため、本実施の形態では、収束判定もすべて計算ノード３０で個別に行い、収束と判定されれば処理を終了する場合を例に説明する。この収束判定も、すべての計算ノードで結果が必ず一致するため、ここに判定を行っても結果は同じになる。
【０１１１】
収束判定部４４は、ｕ（ｒ）が最適値に収束したと判定された場合、その時点で得られた各極小部分問題ｒの解ｕ（ｒ）を組み合わせて、形態素解析の結果を生成し、自然言語解析処理の結果として出力部５０により出力する。また、その時点で得られた各極小部分問題ｒの解ｕ（ｒ）、各計算ノード３０において更新されたグループｓに含まれる各極小部分問題ｒの解ｚｓ（ｒ）、各計算ノード３０において更新されたグループｓのラグランジュ未定乗数αｓ（ｒ）の各々の値をパラメータ記憶部４６に記憶する。なお、本実施の形態では、任意の一つの計算ノード３０から、自然言語解析処理の結果が出力される場合を例に説明したが、全ての計算ノード３０から、自然言語解析処理の結果が出力されてもよい。
【０１１２】
パラメータ記憶部４６は、計算ノード３０において得られた各極小部分問題ｒの解ｕ（ｒ）、更新されたグループｓに含まれる各極小部分問題ｒの解ｚｓ（ｒ）、更新されたグループｓのラグランジュ未定乗数αｓ（ｒ）の値を記憶している。
【０１１３】
＜自然言語解析処理装置の作用＞
次に、本発明の第１の実施の形態に係る自然言語解析処理装置１００の作用について説明する。まず、自然言語解析処理の対象となる一入力単位の文字列が自然言語解析処理装置１００に入力される毎に、自然言語解析処理装置１００において、極小部分問題生成部２２によって、入力された一入力単位の文字列に対する自然言語解析処理を行う極小部分問題を生成し、極小部分問題記憶部２４に記憶されている極小部分問題の集合に追加する。そして、極小部分問題が生成される毎に、グループ作成部２６によって、極小部分問題記憶部２４に記憶されている極小部分問題の集合について、Ｓ個のグループを作成し、Ｓ個の計算ノード３０１〜３０ｓに割り当てる。
【０１１４】
そして、逐次極小部分問題が生成される毎に、制約条件パラメータｕ０（ｒ）の各々に、初期値として、パラメータ記憶部４６に記憶されている前回の自然言語解析処理ルーチンの実行の結果で得られた値を各々設定する。なお、自然言語解析処理ルーチンが一度も実行されていない場合には、制約条件パラメータｕ０（ｒ）の各々に、初期値として０を設定する。また、新たに生成された極小部分問題ｒに対する制約条件パラメータｕ０（ｒ）に、初期値として０を設定する。また、各グループｓのグループフラグＦ-ｓの値を、活性化状態を表す１に設定する共に、各極小部分問題ｒについての制約条件パラメータｕ（ｒ）の制約フラグＦｒの値を、活性化状態を表す１の値に設定する。そして、自然言語解析処理装置１００の各計算ノード３０によって、図４に示す自然言語解析処理ルーチンが実行される。なお、以下では、計算ノード３０ｓによって実行した場合について説明する。
【０１１５】
まず、ステップＳ１００において、割り当てられた自グループｓの極小部分問題ｒの部分集合に対する各ラグランジュ未定乗数α０ｓ（ｒ）及び各極小部分問題の解ｚ０ｓ（ｒ）の各々に、初期値として、パラメータ記憶部４６に記憶されている前回の自然言語解析処理ルーチンの実行の結果で得られた値を各々設定する。なお、自然言語解析処理ルーチンが一度も実行されていない場合には、各ラグランジュ未定乗数α０ｓ（ｒ）及び各極小部分問題の解ｚ０ｓ（ｒ）の各々に、初期値として０を設定する。また、新たに生成された極小部分問題ｒに対するラグランジュ未定乗数α０ｓ（ｒ）及び極小部分問題の解ｚ０ｓ（ｒ）の各々に、初期値として０を設定する。
【０１１６】
次に、ステップＳ１０２において、繰り返し回数を示す変数ｋに初期値１を設定する。
【０１１７】
次に、ステップＳ１０４において、自グループｓのグループフラグＦ-ｓの値が０か否かを判定する。自グループｓのグループフラグＦｓの値が０である場合、ステップＳ１１８へ移行し、グループフラグＦｓの値が０でない場合（１の場合）、ステップＳ１０６へ移行する。
【０１１８】
次に、ステップＳ１０６において、パラメータ更新部３２によって、上記ステップＳ１００で設定されたラグランジュ未定乗数α０ｓ（ｒ）、各極小部分問題の解ｚ０ｓ（ｒ）、及び制約条件パラメータｕ０（ｒ）、又は前回更新されたラグランジュ未定乗数αｋ−１ｓ（ｒ）各極小部分問題の解ｚｋ−１ｓ（ｒ）、及び制約条件パラメータｕｋ−１（ｒ）に基づいて、上記（６）式に従って、自グループｓ内の極小部分問題ｒの各々に対するラグランジュ未定乗数αｋｓ（ｒ）を更新する。
【０１１９】
次に、ステップＳ１０８において、部分解更新部３４によって、上記ステップＳ１０６で更新されたラグランジュ未定乗数αｋｓ（ｒ）と、上記ステップＳ１００で設定された各極小部分問題の解ｚ０ｓ（ｒ）、または前回更新された各極小部分問題の解ｚｋ−１ｓ（ｒ）に基づいて、上記（１１）式に従って、自グループｓ内の極小部分問題ｒの各々に対する解ｚｋｓ（ｒ）を更新する。
【０１２０】
次に、ステップＳ１１０において、第１フラグ判定部３６によって、上記ステップＳ１０８で更新された自グループｓの各極小部分問題の解ｚｋｓ（ｒ）に基づいて、自グループｓに含まれる全ての極小部分問題ｒの解ｚｋｓ（ｒ）が前回更新されたｚｋ−１ｓ（ｒ）の値と同じ値であるか否かを判定する。同じ値である場合には、ステップＳ１１２に移行し、同じ値でない場合には、ステップＳ１１４に移行する。
【０１２１】
次に、ステップＳ１１２において、自グループｓに対するグループフラグＦｓに非活性化状態を表す０の値を付与する。
【０１２２】
次に、ステップＳ１１４において、第１フラグ判定部３６によって、上記ステップＳ１０８で更新された自グループｓの各極小部分問題の解ｚｋｓ（ｒ）に基づいて、自グループｓの各極小部分問題ｒの解ｚｋｓ（ｒ）が前回更新されたｚｋ−１ｓ（ｒ）の値と同じ値でない極小部分問題ｒの解ｚｋｓ（ｒ）があるか否かを判定する。同じ値でない極小部分問題ｒの解ｚｋｓ（ｒ）が存在する場合は、ステップＳ１１６に移行し、それ以外の場合には、ステップＳ１１８に移行する。
【０１２３】
次に、ステップＳ１１６において、ステップＳ１１４において前回更新された解と同じ値でない自グループｓの極小部分問題ｒの解ｚｋｓ（ｒ）の極小部分問題ｒについての制約条件パラメータｕ（ｒ）に対する制約フラグＦｒに、活性化状態を表す１の値を付与する。
【０１２４】
次に、ステップＳ１１８において、同期部３８によって、上記ステップＳ１０６で更新された自グループｓのラグランジュ未定乗数αｋｓ（ｒ）、及び上記ステップＳ１０８において更新された自グループｓの各極小部分問題の解ｚｋｓ（ｒ）を他の計算ノード３０に通知すると共に、他の計算ノード３０ｉ全てから、更新されたラグランジュ未定乗数αｋｉ（ｒ）、及び各極小部分問題の解ｚｋｉ（ｒ）を取得する（ｉ＝１、・・・、ｓ−１、ｓ＋１、・・・Ｓ）。なお、自グループｓが非活性化状態となっていることにより、ステップＳ１０６、及びステップＳ１０８の処理を省略している場合には、その時点で保持している自グループｓのラグランジュ未定乗数αｋ−１ｓ（ｒ）、及び各極小部分問題の解ｚｋ−１ｓ（ｒ）の値をｋ回目のラグランジュ未定乗数αｋｓ（ｒ）、及び各極小部分問題の解ｚｋｓ（ｒ）の値として他の計算ノード３０に通知する。
【０１２５】
次に、ステップＳ１２０において、制約条件更新部４０によって、自グループｓの上記ステップＳ１０６で更新されたラグランジュ未定乗数αｋｓ（ｒ）又は、ステップＳ１１８において他の計算ノード３０に通知したラグランジュ未定乗数αｋｓ（ｒ）と、自グループｓの上記ステップＳ１０８において更新された各極小部分問題の解ｚｋｓ（ｒ）又は、ステップＳ１１８において他の計算ノード３０に通知した各極小部分問題の解ｚｋｓ（ｒ）と、上記ステップＳ１１８において他の計算ノード３０ｉ全てから取得したラグランジュ未定乗数αｋｉ（ｒ）、及び各極小部分問題の解ｚｋｉ（ｒ）とに基づいて、制約フラグＦｒの値が１となっている制約条件パラメータｕｋ（ｒ）の各々のみを、上記（１２）式に従ってを更新する。なお、制約フラグＦｒの値が０となっている、制約条件パラメータｕ（ｒ）については、その時点で保持しているｕｋ−１（ｒ）の値をｋ回目の制約条件パラメータｕｋ（ｒ）とする。
【０１２６】
次に、ステップＳ１２２において、第２フラグ判定部４２によって、全ての極小部分問題ｒの各々について、制約条件パラメータｕｋ（ｒ）が前回更新された制約条件パラメータｕｋ−１（ｒ）と同じ値であるか否かを判定する。同じ値である極小部分問題ｒについてのｕｋ（ｒ）については、後述するステップＳ１２４における処理が実行され、同じ値をもたない極小部分問題ｒについてのｕｋ（ｒ）については、後述するステップＳ１２６における処理が実行される。
【０１２７】
次に、ステップＳ１２４において、前回更新された制約条件パラメータｕｋ−１（ｒ）と同じ値である制約条件パラメータｕｋ（ｒ）に対する制約フラグＦｒ各々に非活性状態を表す０の値を付与する。
【０１２８】
次に、ステップＳ１２６において、第２フラグ判定部４２によって、前回更新された制約条件パラメータｕｋ−１（ｒ）と同じ値でない制約条件パラメータｕｋ（ｒ）に関する極小部分問題ｒを少なくとも１つ含むグループｓに対するグループフラグＦｓの各々に、活性化状態を表す１の値を付与する。
【０１２９】
次に、ステップＳ１２８において、更新又は通知された全ての極小部分問題ｒの各々の解ｚｋｓ（ｒ）と、更新又は保持されている全ての制約条件パラメータｕｋ（ｒ）とに基づいて、上記（１３）式、及び（１４）式に従って、制約条件パラメータｕｋ（ｒ）の全てが最適値に収束したか否かを判定する。上記（１３）式、及び（１４）式を満たさない場合には、収束していないと判断し、ステップＳ１３２へ移行し変数ｋを１インクリメントして、上記ステップＳ１０４へ戻る。一方、上記（１３）式、及び（１４）式を満たした場合には、収束したと判断し、上記ステップＳ１３２へ移行する。
【０１３０】
次に、ステップＳ１３２において、自グループｓの上記ステップＳ１１８で通知及び取得したラグランジュ未定乗数αｋｓ（ｒ）と、極小部分問題ｒの解ｚｋｓ（ｒ）と、上記ステップＳ１２０で最終的に更新又は保持している全ての制約条件パラメータｕｋ（ｒ）をパラメータ記憶部４６に記憶する。また、上記ステップＳ１２０で最終的に更新又は保持している制約条件のパラメータｕｋ（ｒ）を用いて、自然言語解析処理の結果を生成し、出力部５０より出力して、自然言語解析処理ルーチンを終了する。
【０１３１】
以上、説明したように、第１の実施の形態に係る自然言語解析処理装置によれば、逐次入力される入力文字列に対して自然言語解析処理を行う問題を部分問題の集合に分割してグループを作成し、２以上のグループに属する部分問題の解が一致する制約条件に基づいて、各計算ノードにおいて、計算ノードのグループに非活性状態が設定されているか否かに応じて、割り当てられた部分問題の部分集合について解を更新し、他の計算ノードから取得した部分問題の解を用いて、制約条件パラメータに非活性状態が設定されているか否かに応じて、制約条件パラメータを更新することを収束するまで繰り返すことにより、計算量の増大を抑制して、逐次入力される入力文字列に対して精度良く自然言語解析処理を行うことができる。
【０１３２】
また、自然言語解析は、一般的に離散最適化問題として定式化され、その最適解を得ることが自然言語の解析結果を得ることと等価という事を前提として、自然言語解析問題を双対分解＋拡張ラグランジュ緩和法を利用して整数計画問題として解くことにより、自然言語解析問題を部分問題に分解して独立に解くことができ、自然言語解析問題を部分問題に分解して独立に解くことができるという性質を利用することで、活性／非活性制御を実現することができる。
【０１３３】
また、活性状態から非活性状態に変化させる処理を行うことで、値が変わらないグループの処理をスキップして最適化を行うことが可能となり、計算量を大幅に削減できる。また、逆に非活性状態から活性状態へ変化させる処理を導入することで、例えば、時刻が変わって新しい入力がされることにより前時刻の最適解から最適解が変化する場合に、これまで非活性状態で値の更新をしていなかったものに対して、活性状態にすることで、値を更新することが可能となる。つまり、この活性／非活性状態の制御によって、必要最小限の計算で最適解を見つけることが可能となり、また、時刻変化による最適解の変化に対しても、最小限の計算コストで対応することが可能となる。
【０１３４】
また、ストリーミング入力のように、逐次的に入力が渡される環境でも、現時点まで入ってきた入力の最適解を提示しつつ処理を継続することが可能であることから、同時通訳のようなリアルタイム情報処理システムを実現するための基盤技術を提供することが可能となる。また、履歴ベースの方法を用いるよりも解析精度は大きく向上することから、自然言語処理を用いたアプリケーションの性能を底上げすることが可能である。また、前の処理結果の再利用と、活性／非活性制御とにより、逐次処理において冗長となる計算コストを削減し、効率的な逐次処理が可能となる。また、得られる解は、入力されているテキストの最適解であるため、その時点での最も良い解析結果が逐次得られることになる。
【０１３５】
また、逐次的に解析を行うことで、実際に解く問題の最適化変数の一部しかわからない状況でも最適化を行い、その部分的な変数だけの状況での最適解を得ることができる。また、実際に解く整数計画問題の最適化変数が時刻変化により徐々に利用できるようになるような問題設定で、一時刻前の最適解を再利用して、効率的に次の時刻の最適解を得ることができる。そのため、最終的に問題全体として得られる最適解は、逐次、最適化変数が増えていく状況と、一括して通常通りに最適化問題を解く状況で基本的に一致するため、解析精度は一括処理と同等となる。
【０１３６】
なお、上記の実施の形態では、各計算ノード３０が制約条件更新部４０、第２フラグ判定部４２、及び収束判定部４４を備えている場合を例に説明したが、これに限定されるものではない。例えば、図５に示すように、各計算ノード３０は、パラメータ更新部３２、部分解更新部３４、及び第１フラグ判定部３６を備え、演算部２０が、制約条件更新部４０、第２フラグ判定部４２、及び収束判定部４４を１つずつ備えるように構成してもよい。この場合には、制約条件更新部４０は、全ての計算ノード３０ｓで得られたラグランジュ未定乗数αｋｓ（ｒ）と各極小部分問題の解ｚｋｓ（ｒ）を用いて、制約条件パラメータｕｋ（ｒ）を更新し、第２フラグ判定部４２は、得られたｕｋ（ｒ）の値が前回更新又は保持されたｕｋ−１（ｒ）の値と同じであるかに基づいて、対象となるＦｒ及びＦｓに活性状態又は非活性状態を表す値を付与し、収束判定部は、得られた制約条件パラメータｕｋ（ｒ）が最適値に収束しているか判定するようにする。収束判定で、収束していなかった場合には、各計算ノード３０に得られた制約条件パラメータｕｋ（ｒ）を通知してパラメータ更新部３２による処理に戻るようにする。
【０１３７】
＜第２の実施の形態＞
次に、第２の実施の形態について説明する。なお、第１の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。
【０１３８】
第２の実施の形態では、ネットワークで接続された複数の言語解析装置を備えた分散並列計算環境において、複数の言語解析装置による分散並列計算で、パラメータ更新を行っている点が、第１の実施の形態と異なっている。
【０１３９】
図６に示すように、第２の実施の形態に係る自然言語解析処理システム２００は、言語解析制御装置２０１、及びＳ個の言語解析装置２０２１〜２０２Ｓを備えている。言語解析制御装置２０１及びＳ個の言語解析装置２０２１〜２０２Ｓは、ネットワーク２０３を介して接続されている。なお、言語解析装置２０２１〜２０２Ｓのうちの任意の言語解析装置を示す場合には、言語解析装置２０２と称することとする。
【０１４０】
図７に示すように、言語解析制御装置２０１は、入力部１０、演算部２２０、及び出力部２３０を備えている。
【０１４１】
演算部２２０は、極小部分問題生成部２２、極小部分問題記憶部２４、及びグループ作成部２６を備えている。
【０１４２】
グループ作成部２６は、極小部分問題生成部２２によって極小部分問題が逐次生成される毎に、極小部分問題記憶部２４に記憶されている極小部分問題の集合について、各極小部分問題が少なくとも２以上のグループに属するように、Ｓ個のグループを作成し、ネットワーク２０３を介してＳ個の言語解析装置２０２１〜２０２Ｓに送信する。また、グループ作成部２６は、入力されたパラメータρを、ネットワーク２０３を介してＳ個の言語解析装置２０２１〜２０２Ｓの各々に送信する。なお、極小部分問題記憶部２４に記憶されている各極小部分問題の各々については、前回割り当てられたグループと同様のグループ構成となるようにグループを作成する。
【０１４３】
Ｓ個の言語解析装置２０２１〜２０２Ｓの各々は、図８に示すように、入力部２４０、演算部２５０、及び出力部２６０を備えている。
【０１４４】
入力部２４０は、言語解析制御装置２０１から送信された自グループｓに含まれる極小部分問題の部分集合を受け付ける。また、入力部２４０は、他の言語解析装置２０２からネットワーク２０３を介して送信された情報を受け付ける。
【０１４５】
演算部２５０は、パラメータ更新部３２、部分解更新部３４、第１フラグ判定部３６、同期部３８、制約条件更新部４０、第２フラグ判定部４２、収束判定部４４、及びパラメータ記憶部４６を備えている。
【０１４６】
パラメータ更新部３２は、言語解析装置２０２に送信された自グループｓに含まれる各極小部分問題ｒに対するラグランジュ未定乗数αｓ（ｒ）を更新する。なお、自グループｓのグループフラグＦｓ＝０の場合、パラメータ更新部３２は、各極小部分問題ｒに対するラグランジュ未定乗数αｓ（ｒ）の更新を行わず、初期値、又は前回更新された値をラグランジュ未定乗数αｓ（ｒ）として保持する。
【０１４７】
部分解更新部３４は、言語解析装置２０２に送信された自グループｓに含まれる極小部分問題ｒの部分集合について、各極小部分問題の解ｚｓ（ｒ）を更新する。なお、自グループｓのグループフラグＦｓ＝０の場合、部分解更新部３４は、各極小部分問題の解ｚｓ（ｒ）の解の更新を行わず、初期値、又は前回更新された値を各極小部分問題の解ｚｓ（ｒ）の値として保持する。
【０１４８】
同期部３８は、当該言語解析装置２０２ｓで今回更新され、又は保持されたαｓ（ｒ）及び、ｚｓ（ｒ）を、自分以外の全ての言語解析装置２０２へネットワーク２０３を介して送信する。また、同期部３８は、他の言語解析装置２０２ｉ全てから送信された、今回更新され、又は保持されたラグランジュ未定乗数αｉ（ｒ）及び、各極小部分問題の解ｚｉ（ｒ）を受け取る。この処理によって、個々の言語解析装置２０２は全ての言語解析装置２０２ｓの持つαｓ（ｒ）とｚｓ（ｒ）の値を取得することができる。
【０１４９】
制約条件更新部４０は、他の言語解析装置２０２ｉ全てから受け取ったラグランジュ未定乗数αｉ（ｒ）と極小部分問題の解ｚｉ（ｒ）を使って、上記（１２）式に従って、各極小部分問題ｒに対する制約条件パラメータｕ（ｒ）を更新する。
【０１５０】
収束判定部４４は、得られた制約条件パラメータｕ（ｒ）が収束して最適値になっているか判定し、収束したと判定されたときに得られた制約条件パラメータｕ（ｒ）を組み合わせて、自然言語解析処理の結果を生成し、出力部２６０により言語解析制御装置２０１へ送信する。また、その時点で得られた全ての極小部分問題ｒの解ｕ（ｒ）、自グループｓの各極小部分問題ｒの解ｚｓ（ｒ）、自グループｓのラグランジュ未定乗数αｓ（ｒ）の各々の値をパラメータ記憶部４６に記憶する。
【０１５１】
＜自然言語解析処理システムの作用＞
次に、第２の実施の形態に係る自然言語解析処理システム２００の作用について説明する。まず、自然言語解析処理の対象となる一入力単位の文字列が言語解析制御装置２０１に入力されると、言語解析制御装置２０１において、自然言語解析処理を行う問題を、極小部分問題に分解して、極小部分問題の集合を生成する。そして、グループ作成部２６によって、生成された極小部分問題の集合と、極小部分問題記憶部２４に記憶されている極小部分問題の集合とを合わせた集合について、Ｓ個のグループを作成し、ネットワーク２０３を介してＳ個の言語解析装置２０２へ送信して、Ｓ個の言語解析装置２０２に割り当てる。
【０１５２】
そして、各言語解析装置２０２によって、上記図４に示す自然言語解析処理ルーチンが実行される。
【０１５３】
少なくとも１つの言語解析装置２０２によって、最終的に更新された制約条件パラメータｕ（ｒ）を組み合わせて生成された自然言語解析処理の結果が、ネットワーク２０３を介して言語解析制御装置２０１へ送信される。言語解析制御装置２０１は、言語解析装置２０２により受信した自然言語解析処理の結果を出力部２３０により出力する。
【０１５４】
以上説明したように、第２の実施の形態に係る自然言語解析処理システムによれば、ネットワークを介して接続された複数の言語解析装置によって、分散並列処理による自然言語解析処理を行うため、処理を高速化できる。
【０１５５】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１５６】
上記の実施の形態では、一入力単位の文字列が入力される毎に、問題を新たに逐次生成し、既存の極小部分問題に追加していく場合について説明したが、これに限定されるものではない。新たに入力された一入力単位の文字列を用いて、直前に作成した極小部分問題を変更することによって、新たな極小部分問題を作成するようにしてもよい。
【０１５７】
また、上記の実施の形態では、グループフラグの活性化及び制約フラグの非活性化の設定を、各計算ノード毎に全てのグループ及び制約条件パラメータについて設定を行っている場合について説明したが、これに限定されるものではない。各計算ノード毎に、自グループのグループフラグのみの活性化の設定、及び自グループに属している極小部分問題に関わる制約条件パラメータについてのみの非活性化の設定を行ってもよい。
【０１５８】
また、上記の実施の形態では、制約条件パラメータの更新を各計算ノード毎に全ての制約条件パラメータについて更新を行っている場合について説明したが、これに限定されるものではない。各計算ノード毎に、自グループに属する極小部分問題に関わる制約条件パラメータのみの更新を行ってもよい。
【０１５９】
また、上述の自然言語解析処理装置１００及び２００は内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）を含むものとする。
【０１６０】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能であるし、ネットワークを介して提供することも可能である。また、本実施の形態の自然言語解析処理装置１００の各部をハードウエアにより構成してもよい。
【符号の説明】
【０１６１】
１０   入力部
２０   演算部
２２   極小部分問題生成部
２４   極小部分問題記憶部
２６   グループ作成部
３０   計算ノード
３２   パラメータ更新部
３４   部分解更新部
３６   第１フラグ判定部
３８   同期部
４０   制約条件更新部
４２   第２フラグ判定部
４４   収束判定部
４６   パラメータ記憶部
５０   出力部
１００ 自然言語解析処理装置
２００ 自然言語解析処理システム
２０１ 言語解析制御装置
２０２ 言語解析装置
２０３ ネットワーク
２２０ 演算部
２３０ 出力部
２４０ 入力部
２５０ 演算部
２６０ 出力部
【図１】
2014149786.tif 000017
【図２】
2014149786.tif 000018
【図３】
2014149786.tif 000019
【図４】
2014149786.tif 000020
【図５】
2014149786.tif 000021
【図６】
2014149786.tif 000022
【図７】
2014149786.tif 000023
【図８】
2014149786.tif 000024
【図９】
2014149786.tif 000025
【図１０】
2014149786.tif 000026
【図１１】
2014149786.tif 000027