(57)【要約】【課題】  ルート単語の検出と、前置詞等の係り先決定の精度を向上させる言語依存構造解析方法、言語依存構造解析装置、言語依存構造解析プログラム、及びその記録媒体を提供する。【解決手段】  文章の単語に品詞タグを付ける品詞タグ付け手段２０と、基本名詞句にタグを付ける基本名詞句タグ付け手段３０と、全ての単語の係り先の決定を行う簡約化手段６０とを備え、文章における依存構造を解析する言語依存構造解析装置において、文章中のどの単語がどの単語も修飾しないかを数値的に算出すると共に前置詞の係り先を数値的に算出する優先度関数学習手段９０と、前記優先度関数学習手段９０の算出結果が優先度関数適用手段１００によって、ルート単語を検出するルート単語検出手段４０に適用され、前記優先度関数学習手段９０の算出結果が、優先度関数適用手段１００によって、前置詞の係り先を決定する前置詞係り先決定手段５０に適用される。【選択図】      図１
2005316639.tif 000002
【特許請求の範囲】
【請求項１】
文入力手段と、入力された文の単語に品詞タグを付ける品詞タグ付け手段と、基本名詞句にタグを付ける基本名詞句タグ付け手段と、全ての単語の係り先の決定を行う簡約化手段と、結果出力手段とを備え、該文における依存構造を解析する言語依存構造解析装置において、
文中のどの単語がどの単語も修飾しないかを数値的に算出すると共に、前置詞の係り先を数値的に算出する優先度関数学習手段と、
前記優先度関数学習手段の算出結果が優先度関数適用手段により適用され、ルート単語を検出するルート単語検出手段と、
前記優先度関数学習手段の算出結果が前記優先度関数適用手段により適用され、前置詞の係り先を決定する前置詞係り先決定手段とを備えた
ことを特徴とする言語依存構造解析装置。
【請求項２】
演算手段を備えたコンピュータに入力された文の単語に品詞タグを付けると共に、基本名詞句にタグを付け、全ての単語の係り先の決定を行い、結果を出力する、文における依存構造を解析する言語依存構造解析方法において、
前記演算手段は、
文中のどの単語がどの単語も修飾しないかを数値的に算出すると共に、前置詞の係り先を数値的に算出する手順と、
前記算出結果から、ルート単語を検出する手順と、
前記算出結果から、前置詞の係り先を決定する手順とを備えた
ことを特徴とする言語依存構造解析方法。
【請求項３】
コンピュータに、入力された文の単語に品詞タグを付けると共に、基本名詞句にタグを付け、全ての単語の係り先の決定を行い、結果を出力する動作を実行させる文における依存構造を解析する言語依存構造解析プログラムにおいて、
コンピュータに、
文中のどの単語がどの単語も修飾しないかを数値的に算出すると共に、前置詞の係り先を数値的に算出する手順と、
前記算出結果から、ルート単語を検出する手順と、
前記算出結果から、前置詞の係り先を決定する手順とを実行させる
ことを特徴とする言語依存構造解析プログラム。
【請求項４】
請求項３に記載の言語依存構造解析プログラムを記憶した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、機械翻訳、情報抽出、質問応答等の自然言語処理において、各単語がどの単語を修飾するのかの単語間の係り受け関係を明らかにする言語依存構造解析方法、言語依存構造解析装置、言語依存構造解析プログラム、及びその記録媒体に関する。
【背景技術】
【０００２】
各単語がどの単語を修飾するかの単語間の係り受けを明らかにする技術を、言語係り受け解析技術、又は言語依存構造解析技術と呼ぶ。
【０００３】
言語依存構造解析技術（以下、単に依存構造解析と呼ぶ）では、各単語が一文中のどの単語を修飾しているかを推定する。英語を例に取れば、図３に示すように、文に含まれる各単語は、他の単語を修飾している。ここでは、「Ｈｅ」が「ｂｅｌｉｅｖｅｓ」を修飾し、「ｈｅ」が「ｐｌａｙｓ」を、「ｐｌａｙｓ」が「ｗｈａｔ」を修飾しており、全体として「ｗｈａｔ  Ｈｅ  ｐｌａｙｓ」が「ｉｎ」を、「ｉｎ」が「ｂｅｌｉｅｖｅｓ」を修飾している。
【０００４】
また、例えば、「Ｈｅ  ｓａｗ  ａ  ｇｉｒｌ  ｗｉｔｈ  ａ  ｔｅｌｅｓｃｏｐｅ．」という文を考えると、「ｗｉｔｈ」が「ｓａｗ」を修飾するという解釈（Ｈｅが望遠鏡を持っている）と「ｇｉｒｌ」を修飾するという解釈（ｇｉｒｌが望遠鏡を持っている）があり得る。そこで、選択肢となる候補がいくつかある中から、最適と思われる候補を選び出すという処理が重要となる。
【０００５】
英語依存構造解析については、非特許文献１に記載されているような、依存構造を用いて構造解析する方法が知られている。この方法は、句構造を基にした構造解析に比べて、多少、精度は低いが、句構造は複雑で学習データを用意するのには文法に関する高度な専門知識が必要である一方、依存構造は単純なので、学習データの作成が容易であるという点で優れたものであると言える。従って、依存構造解析の精度を向上させることが望まれる。
【０００６】
その一つの鍵となるのは、「一番相応しい依存構造の候補を選択する」という処理の精度を向上させることである。各依存構造の候補が正解か不正解かを判断できる装置があるとして、依存構造の候補毎に別々に正解か否かを何らかの基準で判断したとしても、正解と判断される依存構造の候補がちょうど一つだけになるという保障はない。正解と判断される依存構造の候補が全くなかったり、複数が正解と判断される可能性もある。従って、これは本質的に、正解か不正解かの分類の問題ではなく、依存構造の候補を比較して、優先度が最も高い候補を選ぶという問題、つまり順序付けの問題である。
【０００７】
従来、順序付けを行う技術については、以下のような方法がとられてきた。
（１）それぞれの選択肢の確率を計算し、確率が最大になるものを求める方法。
（２）サポート・ベクトル・マシン（ＳＶＭ）等の教師あり機械学習方法を用いて、正解      候補を正例、正解でない候補を負例として学習し、決定関数の出力値が最大になる      ものを求める方法。
（３）正解候補と不正解候補の特徴とを比較したデータを入力データとして与え、そのど      ちらがより良いかを教師信号ｙiとして、通常の教師あり機械学習方法により判定      する方法。
【非特許文献１】Hiroyasu Yamada, Yuji Matsumoto: Statistical Dependency Analysis, Proceedings of the international Workshop on Parsing Technologies, p.195-206, 2003
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、何れの方法にも問題がある。
【０００９】
（３）の方法では、推移律が保障されない。つまり、ＡよりＢが良く、ＢよりＣが良いと判定しているのに、ＣよりＡが良いという矛盾した判定を出力することがある。これは、通常の教師あり機械学習方法がデータを分類することだけを目的としており、推移律が考慮されていないからである。
【００１０】
（２）のＳＶＭ等の分類学習においても、出力値はほとんどの場合に実数値なので、出力結果の推移律は保障されている。しかしながら、分類のための方法なので、どれが一番良いかの判断に用いるには問題がある。
【００１１】
例えば、学習用の事例が、
・候補｛Ａ、Ｂ｝、正解Ｂ
・候補｛Ｂ、Ｃ｝、正解Ｃ
・候補｛Ｃ、Ｄ｝、正解Ｄ
・候補｛Ｄ、Ｅ｝、正解Ｅ
・候補｛Ｄ、Ｆ｝、正解Ｆ
であったとする。これを、良し悪しの順序として考えれば、Ａ＜Ｂ＜Ｃ＜Ｄ＜Ｅ、Ｆが成り立っていると推定できる。
【００１２】
しかし、良い方を正例○、悪い方を負例×とした分類問題として扱うと、以下のようになる。
・Ａ：○０回、×１回
・Ｂ：○１回、×１回
・Ｃ：○１回、×１回
・Ｄ：○１回、×２回
・Ｅ：○１回、×０回
・Ｆ：○１回、×０回
【００１３】
これによると、ＢとＣは同じ条件になり、その間の順序関係が、決定関数の出力値の差として正しく学習されることは望めない。また、学習方法にもよるが、Ｄは×が２回なので、×が１回のＢやＣより、不利に扱われる可能性が高い。このようになるのは、各場合における競合する他の候補を無視して、○と×の回数だけを数えているからである。
【００１４】
（１）の確率による方法も、単に○×の回数を数えるだけの方法であれば、順序関係の学習はできない。順序関係を学習するために、比較された候補のペアの数を数えるという方法を使えば、Ｂ＜Ｃのような判定は可能になる。しかし、Ａ＜Ｆのように、学習データに直接現れていない順序を判定するためには、順序を考慮した処理が必要となる。実際の学習データには間違いが含まれているので、順序が一貫していないことがある。また、学習データと同じデータが現れることは稀であり、何らかの一般化が必要である。
【００１５】
本発明は、この問題を順序付けに適した学習を用いることで解決するのであるが、順序付けを目的とする学習方法として、類似の方法にＲａｎｋｉｎｇ  ＳＶＭがある。しかし、この方法は、ＳＶＭの計算方法を転用しており、最適な解が得られない。
【課題を解決するための手段】
【００１６】
前記課題を解決するため、文入力手段と、入力された文の単語に品詞タグを付ける品詞タグ付け手段と、基本名詞句にタグを付ける基本名詞句タグ付け手段と、全ての単語の係り先の決定を行う簡約化手段と、結果出力手段とを備え、該文における依存構造を解析する言語依存構造解析装置において、文中のどの単語がどの単語も修飾しないかを数値的に算出すると共に、前置詞の係り先を数値的に算出する優先度関数学習手段と、前記優先度関数学習手段の算出結果を、ルート単語を検出するルート単語検出手段に適用する優先度関数適用手段と、前記優先度関数学習手段の算出結果が、優先度関数適用手段により適用され、前置詞の係り先を決定する前置詞係り先決定手段とを備えたことを特徴とする。
【発明の効果】
【００１７】
本発明によれば、優先度関数学習手段、優先度関数適用手段、ルート単語検出手段、及び前置詞係り先決定手段を用いることによって、従来の方法に比べて、ルート単語の検出と、前置詞等の係り先決定の精度を向上させることができる。
【発明を実施するための最良の形態】
【００１８】
図１及び図２は本発明の一実施形態を示すもので、図１は言語依存構造解析装置のブロック図である。
【００１９】
この言語依存構造解析装置は、文を入力する文入力手段１０と、入力された文の各単語に品詞タグを付ける品詞タグ付け手段２０と、基本名詞句にタグを付ける基本名詞句タグ付け手段３０と、他の単語を修飾しない単語であるルート単語を検出するルート単語検出手段４０と、前置詞の係り先を決定する前置詞係り先決定手段５０と、実際に全ての単語の係り先の決定を行う簡約化手段６０と、簡約化を再開する簡約化再開手段７０と、依存構造解析の結果を出力する結果出力手段８０と、後に詳細を説明する優先度関数学習手段９０と、優先度関数適用手段１００とから構成されている。
【００２０】
文入力手段１０としては、キーボード等がある。
【００２１】
品詞タグ付け手段２０は、文入力手段１０により読み込まれたタグの付いていない文の各単語の品詞を推定する。既に様々な手法が提案されており、何れか高精度なものを利用すればよい。例えば、ｈｅにはＰＲＰ（人称代名詞）、ｂｅｌｉｅｖｅｓやｐｌａｙｓにはＶＢＺ（３人称単数に対応する動詞）、という様に品詞のタグが付けられる。
【００２２】
簡約化手段６０は、実際に全ての単語の係り先の決定を行う。文全体を単語リストＬに記録する。Ｌを文頭又は文末から単語を一つずつ調べていき、単語ｗiが直前の単語ｗi-1を修飾するか、直後の単語ｗi+1を修飾するか、それともどちらでもないかを判断する。ただし、単語ｗiが他の単語から修飾されている場合は、たとえ隣の単語を修飾していても、「どちらでもない」と判断する。
【００２３】
もし、単語ｗiが隣接する単語ｗjを修飾していることがわかったら、ｗiを単語リストから削除して、ｗjの中に「ｗiが修飾している」という情報を残す。
【００２４】
この簡約化を繰り返し、単語リストに残る単語が全て「どちらでもない」と判断されるか、最後の１語になったら終了する。
【００２５】
この学習は、ＳＶＭ等の通常の分類学習器を利用する。
【００２６】
簡約化手段６０として、ＳＶＭを用いる場合、「前の単語を修飾（Ｌｅｆｔ）」「左の単語を修飾（Ｒｉｇｈｔ）」「どちらでもない（Ｓｈｉｆｔ）」の３つのクラスに分類するためには、与えられたベクトルが、それぞれのクラスに属するか、そうでないかの分類学習器を３つ用意する。そして、各分類学習器の出力であるベクトルｘの関数、ｆLeft（ｘ）、ｆRight（ｘ）、ｆShift（ｘ）を比較し（以下、ベクトルをアンダーラインで表す）、出力値が一番大きいクラスに属するものを判断する。この判断を行うＳＶＭを利用するにあたり、各単語ｗiをベクトルｘiに変換しなければならない。このベクトルは、単語ｗi、その品詞タグｐi、基本名詞タグｂi、括弧の中か外かのタグＰi、引用符の中か外かのタグＱi、ルート単語のどちら側にあるかのタグｌi、前置詞係り先決定手段５０による係り先までの距離、単語ｗiの直前の単語ｗi-kL，・・・，ｗi-1(ＫＬは３前後のごく小さな非負整数)、単語ｗiの直後の単語ｗi+1，・・・，ｗi+KR (ＫＲは３前後のごく小さな非負整数)、単語ｗi+1，・・・，ｗi+KO (ＫＯは３前後のごく小さな非負整数)に対する判断結果（Ｌｅｆｔ、Ｒｉｇｈｔ、Ｓｈｉｆｔ）と言ったような特徴を数値化することで作成できる。
【００２７】
カーネルとしては、２次の多項式カーネル（ｘi・ｘj+１）2が良い成績を与える。尚、これらの素性は一般に、単語が削除されると変化するので、分類の度にベクトル化をやり直す必要がある。単語が削除されると、例えば、2つ右の単語がすぐ右の単語になるなどの変化があるため、単語を調べ直してベクトルを作り直す必要があるのである。
【００２８】
しかし、簡約化手段６０だけでは精度が十分ではないので、本発明では、さらに精度を向上させるため、以下に述べる手段の出力を利用する。
【００２９】
簡約化手段６０は、単語ｗiの近傍の単語しか見ていないので、判断を誤りやすい。そこで、基本名詞句タグ付け手段３０を利用する。係り受けを判断する上で、長い名詞句は近傍の単語の情報を遠ざけてしまうので、誤りの原因になる。名詞句は一般的に入れ子構造になっており、複雑な構造を持つものであるが、基本名詞句はその中で一番単純な、それ以上分割できない名詞句である。例えば、「ｔｈｅ  ｂｅａｕｔｉｆｕｌ  ｐｉｃｔｕｒｅ」であれば、ｔｈｅが基本名詞句の先頭単語であり、Ｂ-ＮＰと言うタグが付けられる。ｂｅａｕｔｉｆｕｌとｐｉｃｔｕｒｅは、基本名詞句に含まれるが、先頭ではなく，Ｉ-ＮＰと言うタグが付けられる。
【００３０】
簡約化手段６０において、単語リストに２語以上残っているにも拘わらず、全ての単語が「どちらでもない」と判断されると、それ以上、依存構造解析が進まない。そこで、簡約化再開手段７０は、この場合に何か単語を一つ強制的に削除して、簡約化を再開させる手段である。
【００３１】
簡約化再開手段７０では、以下のような方法が利用できる。単語リストの全ての単語ｗiに対して、ｆShift（ｘi）-ｆLeft（ｘi）とｆShift（ｘi）-ｆRight（ｘi）を計算する。その中で、ｆShift（ｘk）-ｆLeft（ｘk）が最も小さい時には、単語ｗkをＬｅｆｔと判断して削除する。一方、その中でｆShift（ｘk）-ｆRight（ｘk）が最も小さい時には、単語ｗkをＲｉｇｈｔと判断して削除する。何れの場合にも、単語が一つ減るので、単語ｗkの所から簡約化手段６０を再開できる。
【００３２】
一文の中には、必ず一つ、他の単語を修飾しない単語があり、これは係り受け木のルート（根）である。このルート単語を見つけ出すのが、ルート単語検出手段４０である。図３で言えば、ｂｅｌｉｅｖｅｓがルート単語である。ルート単語は、文中の他の単語と比較して、ルートとして優先度が一番高い単語と言える。従って、文中の全ての単語をルート候補として、後記する本当のルートを正解とする優先度関数適用手段１００により、ルート単語を検出することができる。
【００３３】
ルート単語検出手段４０では、各単語ｗiをベクトルｘiに変換するのに、単語ｗi、その品詞タグｐi、基本名詞タグｂi、括弧の中か外かのタグＰi、引用符の中か外かのタグＱi、単語ｗiの直前の単語ｗi-kL，・・・，ｗi-1(ＫＬは１前後のごく小さな非負整数)とそのタグ、単語ｗiの直後の単語ｗi+1，・・・，ｗi+KR (ＫＲは１前後のごく小さな非負整数)とそのタグ、単語ｗiの左にある全ての単語の集合｛ｗ0，・・・，ｗi-1｝とそのタグの集合、単語ｗiの右にある全ての単語の集合｛ｗ0，・・・，ｗi-1｝とそのタグの集合、文の先頭かどうか、文中に動詞や助動詞が一つでも含まれているか、左右で一番近いコンマまでの距離のような素性を利用する。やはり２次の多項式カーネルが良い成績を与える。
【００３４】
ここで、例えば、「Ｈｅ  ｓａｗ  ａ  ｇｉｒｌ  ｗｉｔｈ  ａ  ｔｅｌｅｓｃｏｐｅ．」を考えると、この文のｗｉｔｈは、動詞ｓａｗを修飾する可能性と、名詞ｇｉｒｌを修飾している可能性があることが分かる。このように、前置詞は動詞に係ることも名詞に係ることもあり、どこに係っているかの判断が特に難しい。そこで、前置詞係り先決定手段５０は、前置詞の係り先だけを決定し、後記する同一文に現れる名詞や動詞の候補から前置詞の係り先を選び出す優先度関数適用手段１００により、係り先を決定することができる。
【００３５】
前置詞係り先決定手段５０におけるベクトル化では、前置詞ｗiと係り先候補の単語とそのタグ、前置詞ｗiから係り先候補までの距離、前後の単語とそのタグのような素性を利用する。
【００３６】
前記の通り、依存構造解析においては、複数の候補の中から最も優先度の高い候補を選ぶという処理が中心的になる。その学習データは、係り先候補のリストＬi＝｛ａ１，ａ２，・・・｝と、その中で選ばれるべき正解候補ｂiの組のリスト｛（Ｌi，ｂi）｝になる。ここから、ｂi≠ａjの場合、ｂi＞ａjという順序関係が得られる。各候補ａiを文脈の特徴と組み合わせて数値ベクトルｘiにしたものが、実際の学習データになる。例えば、ａ4＞ａ3ならば、これを（+１，ｘ4，ｘ3）というベクトル対データとして表す。最初の+１は、第１ベクトルの方が第２ベクトルより優先度が高いことを表す。逆の場合は-１とする。以下では、このようなベクトル対データを
【００３７】
【数１】
2005316639.tif 000003
で表し、
【００３８】
【数２】
2005316639.tif 000004
で第１のベクトルｘ4を、
【００３９】
【数３】
2005316639.tif 000005
で第２のベクトルｘ3を指す。
【００４０】
本発明は、このような順序関係のデータから、各候補の良さを表す優先度関数
【００４１】
【数４】
2005316639.tif 000006
を学習する。この学習を行うのが、前記の優先度関数学習手段９０である。即ち、優先度関数学習手段９０は、与えられた任意のベクトルｘに対して、前記ｇ（ｘ）を求める。ここで、Ｋ（ｘi，ｘj）はＳＶＭ等で用いられるカーネル関数であり、具体的には、内積ｘi・ｘjや内積の多項式関数（ｘi・ｘj+１）2等が用いられる。αiは学習によって定まる係数である。
【００４２】
この学習は以下の関数を最小化する問題に対応する。
【００４３】
【数５】
2005316639.tif 000007
ただし、０≦αi≦Ｃかつ
【００４４】
【数６】
2005316639.tif 000008
である。このαiは、優先度関数学習手段９０が求める。すなわち、優先度関数学習手段９０はベクトル対データ｛（ｙi，ｘi・1，ｘi・2）｝から最適なαiを求める。そして優先度関数適用手段１００が、優先度関数学習手段９０の算出結果から、ルート単語をルート単語検出手段４０に適用し、前置詞の係り先を前置詞係り先決定手段５０に適用する。
【００４５】
これに対して、ＳＶＭの場合は、
【００４６】
【数７】
2005316639.tif 000009
という関数を求める。このときの定数ｂの最適な値を決めるために
【００４７】
【数８】
2005316639.tif 000010
という制約条件が必要となる。
【００４８】
また、Ｒａｎｋｉｎｇ  ＳＶＭはαiが独立に変更できることを考慮しておらず、単純にＳＶＭの解法を適用しているので、前記の制約条件つきの最適化問題を解いており、最適な解が求まらない。しかし、順序付けの問題では、この制約条件が不要なので、各αiを他のαjの値に関係なく、変更することができる。そのため、学習は通常のＳＶＭに比べて簡単になり、様々な最適化方法を利用することができる。
【００４９】
図２は本発明の言語依存構造解析プログラムをコンピュータに実行させた時の、コンピュータの動作のフローチャートである。
【００５０】
まず、キーボード等から文が入力されると（Ｓ１）、品詞タグ付け手段２０がそれぞれの単語に品詞タグを付ける（Ｓ２）。次に、基本名詞句タグ付け手段３０が名詞句にタグを付ける（Ｓ３）。Ｓ２と同時に、数値ベクトルｘi化された全ての単語ｗiについてαiを求め、ｇ（ｘi）を求める（Ｓ４）。このＳ４で求められたｇ（ｘi）を基に、ルート単語検出手段４０がルート単語を求める（Ｓ５）と同時に、ｇ（ｘi）を基に、前置詞係り先決定手段５０が前置詞の係り先を決定する（Ｓ６）。続いて、簡約化を行い（Ｓ７）、全て終了すれば解析結果をディスプレイ等に出力する（Ｓ８）。
【００５１】
尚、本装置、方法、プログラム等は英語に限ったものではなく、ドイツ語やフランス語等のアルファベット言語にも適用可能である。
【００５２】
また、前記のプログラムは記録媒体に記録することにより、持ち運び等が可能である。
【図面の簡単な説明】
【００５３】
【図１】本発明の一実施形態に係る各手段のブロック図である。
【図２】本発明の一実施形態に係るコンピュータの動作のフローチャートである。
【図３】英語の文章の依存構造を示した図である。
【符号の説明】
【００５４】
１０    文入力手段
２０    品詞タグ付け手段
３０    基本名詞句タグ付け手段
４０    ルート単語検出手段
５０    前置詞係り先決定手段
６０    簡約化手段
７０    簡約化再開手段
８０    結果出力手段
９０    優先度関数学習手段
１００  優先度関数適用手段
【図１】
2005316639.tif 000011
【図２】
2005316639.tif 000012
【図３】
2005316639.tif 000013