(57)【要約】【課題】同一の依存構造へ到達する行動系列が複数存在しないように依存構造解析を行うことができるようにする。【解決手段】特徴抽出部２４２が、依存関係が付与されていない単語のペアの各々に対して依存関係を付与する行動のうち、行動選択部２４４によって選択された行動とは異なる行動の各々について、当該行動を受理する場合の特徴、及び当該行動を受理しない場合の特徴を抽出する。行動選択部２４４が、抽出された特徴に基づいて、行動を受理する場合の特徴、及び行動を受理しない場合の特徴の差分が最大となる行動を選択する。行動判別部２４６が、行動選択部２４４によって選択された行動を受理するか否かを判別する。状態遷移部２４８が、行動判別部２４６によって選択された行動を受理すると判別された場合、選択された行動に対応する単語のペアに付与される依存関係を追加した状態に遷移させる。【選択図】図２
2015170044.tif 000002
【特許請求の範囲】
【請求項１】
特徴抽出部、行動選択部、行動判別部、状態遷移部、及び終了判定部を含む依存構造解析装置における依存構造解析方法であって、
前記特徴抽出部が、解析対象文の形態素解析結果に基づいて、初期状態、又は前記解析対象文に含まれる単語のペアの少なくとも１つに対し前記ペアの一方から他方への依存関係を付与した状態において、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動の各々について、前記行動を受理する場合の特徴、及び前記行動を受理しない場合の特徴を抽出するステップと、
前記行動選択部が、前記特徴抽出部によって抽出された前記特徴に基づいて、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動のうち、前記行動を受理する場合の特徴に基づくスコア、及び前記行動を受理しない場合の特徴に基づくスコアの差分が最大となる行動を選択するステップと、
前記行動判別部が、前記行動選択部によって選択された前記行動を受理する場合の特徴に基づくスコア、及び前記行動を受理しない場合の特徴に基づくスコアに基づいて、前記行動選択部によって選択された前記行動を受理するか否かを判別するステップと、
前記状態遷移部が、前記行動判別部によって前記選択された前記行動を受理すると判別された場合、前記選択された前記行動に対応する前記単語のペアに付与される前記依存関係を追加した状態に遷移させるステップと、
前記終了判定部が、予め定められた終了条件を満たすまで、前記行動選択部による選択、前記行動判別部による判別、及び前記状態遷移部による遷移を繰り返すステップと、
を含む依存構造解析方法であって、
前記特徴抽出部が特徴を抽出するステップは、初期状態、又は前記状態において、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動のうち、前記行動選択部によって選択された行動とは異なる行動の各々について、前記行動を受理する場合の特徴、及び前記行動を受理しない場合の特徴を抽出し、
前記行動選択部が行動を選択するステップは、前記特徴抽出部によって抽出された前記特徴に基づいて、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動のうち、前記行動選択部によって選択された行動とは異なる行動から、前記行動を受理する場合の特徴に基づくスコア、及び前記行動を受理しない場合の特徴に基づくスコアの差分が最大となる行動を選択する
依存構造解析方法。
【請求項２】
前記特徴抽出部が特徴を抽出するステップは、前記依存関係の主要素となる単語に関する特徴、及び前記依存関係の従要素となる単語に関する特徴を抽出する
請求項１記載の依存構造解析方法。
【請求項３】
前記特徴抽出部が特徴を抽出するステップは、更に、前記依存関係の主要素となる単語の前後の単語に関する特徴、及び前記依存関係の従要素となる単語の前後の単語に関する特徴を抽出する
請求項１又は請求項２記載の依存構造解析方法。
【請求項４】
解析対象文の形態素解析結果に基づいて、初期状態、又は前記解析対象文に含まれる単語のペアの少なくとも１つに対し前記ペアの一方から他方への依存関係を付与した状態において、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動の各々について、前記行動を受理する場合の特徴、及び前記行動を受理しない場合の特徴を抽出する特徴抽出部と、
前記特徴抽出部によって抽出された前記特徴に基づいて、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動のうち、前記行動を受理する場合の特徴に基づくスコア、及び前記行動を受理しない場合の特徴に基づくスコアの差分が最大となる行動を選択する行動選択部と、
前記行動選択部によって選択された前記行動を受理する場合の特徴に基づくスコア、及び前記行動を受理しない場合の特徴に基づくスコアに基づいて、前記行動選択部によって選択された前記行動を受理するか否かを判別する行動判別部と、
前記行動判別部によって前記選択された前記行動を受理すると判別された場合、前記選択された前記行動に対応する前記単語のペアに付与される前記依存関係を追加した状態に遷移させる状態遷移部と、
予め定められた終了条件を満たすまで、前記行動選択部による選択、前記行動判別部による判別、及び前記状態遷移部による遷移を繰り返す終了判定部と、
を含む依存構造解析装置であって、
前記特徴抽出部は、初期状態、又は前記状態において、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動のうち、前記行動選択部によって選択された行動とは異なる行動の各々について、前記行動を受理する場合の特徴、及び前記行動を受理しない場合の特徴を抽出し、
前記行動選択部は、前記特徴抽出部によって抽出された前記特徴に基づいて、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動のうち、前記行動選択部によって選択された行動とは異なる行動から、前記行動を受理する場合の特徴に基づくスコア、及び前記行動を受理しない場合の特徴に基づくスコアの差分が最大となる行動を選択する
依存構造解析装置。
【請求項５】
コンピュータに、請求項１〜請求項３の何れか１項記載の依存構造解析方法の各ステップを実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、依存構造解析方法、装置、及びプログラムに係り、特に、依存関係を付与する依存構造解析方法、装置、及びプログラムに関する。
【背景技術】
【０００２】
自然言語の依存構造解析とは、英語や日本語などの文に対して、文中の各単語（または各文節）間における依存関係の情報を、計算機によって自動的に付与する処理である。図５（Ａ）に入力となる文の例を示し、図５（Ｂ）に、依存構造解析を行った出力の例を示す。図５（Ｂ）において、単語と単語をつなぐ矢印は単語間の依存関係を表しており、矢印の向きは、依存関係の主従関係を表している。例えば、図５（Ｂ）において、“I”と“saw”との間には依存関係があり、主要素は“saw”、従要素は“I”である。一般的に、主語と述語では、述語が主要素、主語が従要素となり、修飾語と被修飾語では、被修飾語が主要素、修飾語が従要素となる。
【０００３】
現在の依存構造解析には、大きく分けると二種類の方法がある。一つは、グラフ型依存構造解析と呼ばれるもので、動的計画法に基づいて最適な依存構造全体を一度に推定する方法である。グラフ型依存構造解析の方法は、例えば非特許文献１に開示されている。もう一つは、遷移型依存構造解析と呼ばれるもので、入力から出力までをいくつかの連続した状態遷移と捉えて、最終的な状態（依存構造）へ至る最適な行動（アクション）系列を推定する方法である。図６（Ａ）に、遷移型依存構造解析の状態遷移の例を示す。遷移型依存構造解析における状態とは、部分的に依存構造が付与された文のことであり、行動とは、まだ依存関係の情報が付与されていない任意の単語間に、依存関係の情報を付与することである。このように、遷移型依存構造解析では、段階的に依存関係の情報を付与しながら最終的な依存構造を推定する。遷移型依存構造解析の方法は、例えば非特許文献２に開示されている。
【０００４】
遷移型依存構造解析における「擬似曖昧性」とは、図６（Ａ）のような状態遷移系列において、同一の最終状態（依存構造）へ到達する遷移過程が複数存在する性質のことをいう。図６（Ａ）と図６（Ｂ）に、擬似曖昧性の例を示す。
【０００５】
図６（Ａ）と図６（Ｂ）は、どちらも同一の依存構造へ到達する遷移過程であるが、途中の状態は異なっている。
【０００６】
一般的に、遷移型依存構造解析を行う場合には、ビーム探索などの方法を援用して、複数の依存構造の可能性（仮説）を同時に探索し、与えられた文に対して最もスコアの高い依存構造を決定する。このとき、擬似曖昧性の高い遷移型依存構造解析の方法では、同一の依存構造へ到達する行動系列が多数存在する。そのため、たとえ複数の仮説を考慮したとしても、それらが最終的に同一の依存構造へ到達する可能性が高くなり、複数の仮説を考慮しても解析性能が向上しないという問題がある。実際に、非特許文献３では、擬似曖昧性のある遷移型依存構造解析の方法は、擬似曖昧性が存在しない方法と比較して、解析性能が劣ることを報告している。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】R. McDonald, F. Pereira, K. Ribarov, and J. Haji.c.，“Non-Projective Dependency Parsing using Spanning Tree Algorithms.”，2005，In Proceedings of HLT-EMNLP，p.523-530
【非特許文献２】Joakim Nivre.，“Algorithms for deterministic incremental dependency parsing.”，Computational Linguistics，2008，34(4):513.553
【非特許文献３】Katsuhiko Hayashi, Shuhei Kondo and Yuji Matsumoto.，“Efficient Stacked Dependency Parsing by Forest Reranking.”，Transactions of the Association of Computational Linguistics，2013，p.139-150
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記の非特許文献２〜３に開示されている、擬似曖昧性が存在する遷移型依存構造構文解析の方法は、同一の依存構造へ到達する行動系列が複数存在するため、複数の仮説を同時に探索しても解析性能が向上しないという問題がある。
【０００９】
本発明は、上記問題点を解決するために成されたものであり、同一の依存構造へ到達する行動系列が複数存在しないように依存構造解析を行うことができる依存構造解析方法、装置、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、本発明の依存構造解析方法は、特徴抽出部、行動選択部、行動判別部、状態遷移部、及び終了判定部を含む依存構造解析装置における依存構造解析方法であって、前記特徴抽出部が、解析対象文の形態素解析結果に基づいて、初期状態、又は前記解析対象文に含まれる単語のペアの少なくとも１つに対し前記ペアの一方から他方への依存関係を付与した状態において、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動の各々について、前記行動を受理する場合の特徴、及び前記行動を受理しない場合の特徴を抽出するステップと、前記行動選択部が、前記特徴抽出部によって抽出された前記特徴に基づいて、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動のうち、前記行動を受理する場合の特徴に基づくスコア、及び前記行動を受理しない場合の特徴に基づくスコアの差分が最大となる行動を選択するステップと、前記行動判別部が、前記行動選択部によって選択された前記行動を受理する場合の特徴に基づくスコア、及び前記行動を受理しない場合の特徴に基づくスコアに基づいて、前記行動選択部によって選択された前記行動を受理するか否かを判別するステップと、前記状態遷移部が、前記行動判別部によって前記選択された前記行動を受理すると判別された場合、前記選択された前記行動に対応する前記単語のペアに付与される前記依存関係を追加した状態に遷移させるステップと、前記終了判定部が、予め定められた終了条件を満たすまで、前記行動選択部による選択、前記行動判別部による判別、及び前記状態遷移部による遷移を繰り返すステップと、を含む依存構造解析方法であって、前記特徴抽出部が特徴を抽出するステップは、初期状態、又は前記状態において、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動のうち、前記行動選択部によって選択された行動とは異なる行動の各々について、前記行動を受理する場合の特徴、及び前記行動を受理しない場合の特徴を抽出し、前記行動選択部が行動を選択するステップは、前記特徴抽出部によって抽出された前記特徴に基づいて、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動のうち、前記行動選択部によって選択された行動とは異なる行動から、前記行動を受理する場合の特徴に基づくスコア、及び前記行動を受理しない場合の特徴に基づくスコアの差分が最大となる行動を選択する。
【００１１】
本発明に係る依存構造解析装置は、解析対象文の形態素解析結果に基づいて、初期状態、又は前記解析対象文に含まれる単語のペアの少なくとも１つに対し前記ペアの一方から他方への依存関係を付与した状態において、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動の各々について、前記行動を受理する場合の特徴、及び前記行動を受理しない場合の特徴を抽出する特徴抽出部と、前記特徴抽出部によって抽出された前記特徴に基づいて、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動のうち、前記行動を受理する場合の特徴に基づくスコア、及び前記行動を受理しない場合の特徴に基づくスコアの差分が最大となる行動を選択する行動選択部と、前記行動選択部によって選択された前記行動を受理する場合の特徴に基づくスコア、及び前記行動を受理しない場合の特徴に基づくスコアに基づいて、前記行動選択部によって選択された前記行動を受理するか否かを判別する行動判別部と、前記行動判別部によって前記選択された前記行動を受理すると判別された場合、前記選択された前記行動に対応する前記単語のペアに付与される前記依存関係を追加した状態に遷移させる状態遷移部と、予め定められた終了条件を満たすまで、前記行動選択部による選択、前記行動判別部による判別、及び前記状態遷移部による遷移を繰り返す終了判定部と、を含む依存構造解析装置であって、前記特徴抽出部は、初期状態、又は前記状態において、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動のうち、前記行動選択部によって選択された行動とは異なる行動の各々について、前記行動を受理する場合の特徴、及び前記行動を受理しない場合の特徴を抽出し、前記行動選択部は、前記特徴抽出部によって抽出された前記特徴に基づいて、前記依存関係が付与されていない単語のペアの各々に対して前記依存関係を付与する行動のうち、前記行動選択部によって選択された行動とは異なる行動から、前記行動を受理する場合の特徴に基づくスコア、及び前記行動を受理しない場合の特徴に基づくスコアの差分が最大となる行動を選択する。
【００１２】
本発明の前記特徴抽出部は、前記依存関係の主要素となる単語に関する特徴、及び前記依存関係の従要素となる単語に関する特徴を抽出するようにすることができる。
【００１３】
本発明の前記特徴抽出部は、更に、前記依存関係の主要素となる単語の前後の単語に関する特徴、及び前記依存関係の従要素となる単語の前後の単語に関する特徴を抽出するようにすることができる。
【００１４】
また、本発明のプログラムは、コンピュータに、上記の依存構造解析方法の各ステップを実行させるためのプログラムである。
【発明の効果】
【００１５】
以上説明したように、本発明の依存構造解析方法、装置、及びプログラムによれば、解析対象文の形態素解析結果に基づいて、依存関係が付与されていない単語のペアの各々に対して依存関係を付与する行動のうち、選択された行動とは異なる行動の各々について、当該行動を受理する場合の特徴、及び当該行動を受理しない場合の特徴を抽出し、抽出された特徴に基づいて、行動を受理する場合の特徴に基づくスコア、及び行動を受理しない場合の特徴に基づくスコアの差分が最大となる行動を選択し、選択された行動を受理する場合の特徴に基づくスコア、及び当該行動を受理しない場合の特徴に基づくスコアに基づいて、選択された行動を受理するか否かを判別し、選択された行動を受理すると判別された場合、選択された行動に対応する単語のペアに付与される依存関係を追加した状態に遷移させることを繰り返すことにより、同一の依存構造へ到達する行動系列が複数存在しないように依存構造解析を行うことができる、という効果が得られる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施の形態の依存構造解析装置の機能構成を示すブロック図である。
【図２】本発明の実施の形態の依存構造解析装置の遷移型依存構造解析部の機能構成を示すブロック図である。
【図３】本発明の実施の形態の依存構造解析装置における解析処理ルーチンの内容を示すフローチャートである。
【図４】本発明の実施の形態の依存構造解析装置における依存構造解析処理ルーチンの内容を示すフローチャートである。
【図５】依存構造解析の一例を示す図である。
【図６】遷移型依存構造解析の状態遷移の一例を示す図である。
【発明を実施するための形態】
【００１７】
＜概要＞
まず、本発明の実施の形態の概要について説明する。
【００１８】
本発明の実施の形態では、従来の遷移型依存構造構文解析に、擬似曖昧性を取り除く処理を導入する。この擬似曖昧性を取り除く処理は、遷移型依存構造構文解析の各状態遷移において、従来のように、複数の行動の候補から最適な行動の選択を行う多値分類アルゴリズムを構成するのではなく、受理するかしないかを最も判定しやすい行動を一つ選択し、選択された行動を受理するかしないかを決定する二値分類アルゴリズムを構成することによって実現される。受理しないと判定された行動は、それ以降の状態遷移において、二度と選択することができないため、擬似曖昧性の問題を解消することができる。
【００１９】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２０】
＜依存構造解析装置の構成＞
【００２１】
本実施の形態の依存構造解析装置１００は、ＣＰＵと、ＲＡＭと、後述する解析処理ルーチン、及び依存構造解析処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することができる。この依存構造解析装置１００は、機能的には、図１に示すように、入力部１０と、演算部２０と、出力部３０とを備えている。依存構造解析装置１００は、重みベクトルＷ、特徴抽出関数Ｆ、依存構造の解析対象文Ｘを入力とし、解析対象文Ｘの依存構造解析結果Ｔを出力する装置である。
【００２２】
入力部１０は、解析対象文Ｘと、重みベクトルＷと、特徴抽出関数Ｆとを受け付ける。重みベクトルＷは、後述する遷移型依存構造解析部２４においてスコアを計算するために用いられる。また、特徴抽出関数Ｆは、後述する特徴抽出部２４２において用いられる。
【００２３】
演算部２０は、入力部１０によって受け付けた解析対象文Ｘについて、依存関係の状態遷移を繰り返して、Ｘの最適な依存構造解析結果Ｔを出力する。演算部２０は、メモリ２２と、遷移型依存構造解析部２４とを備えている。
【００２４】
メモリ２２には、入力部１０によって受け付けた重みベクトルＷと、特徴抽出関数Ｆとが格納される。
【００２５】
遷移型依存構造解析部２４は、入力部１０によって受け付けた解析対象文Ｘと、メモリ２２に格納された重みベクトルＷ、及び特徴抽出関数Ｆとに基づいて、解析対象文Ｘに含まれる単語のペアに対し、当該ペアの一方から他方への依存関係を付与した状態の遷移（依存状態遷移）を繰り返し行い、解析対象文Ｘの最適な依存構造解析結果Ｔを出力する。遷移型依存構造解析部２４は、図２に示すように、形態素解析部２４０と、特徴抽出部２４２と、行動選択部２４４と、行動判別部２４６と、状態遷移部２４８と、終了判定部２５０とを備えている。
【００２６】
形態素解析部２４０は、入力部１０によって受け付けた解析対象文Ｘについて、形態素解析を行って、解析対象文Ｘを単語に分割し、各単語に対して品詞を付与する。
【００２７】
特徴抽出部２４２は、メモリ２２に格納された特徴抽出関数Ｆと、形態素解析部２４０によって出力された解析対象文Ｘの形態素解析結果とに基づいて、依存関係が付与されていない単語のペアの各々に対して依存関係を付与する行動のうち、後述する行動選択部２４４によって選択された行動を除いた行動の各々について、当該行動を受理する場合の特徴、及び当該行動を受理しない場合の特徴を抽出する。
【００２８】
特徴抽出部２４２における特徴の抽出処理は、後述する終了判定部２５０の判定により繰り返し行われるため、解析対象文Ｘに含まれる単語のペアに依存関係が付与されていない状態（初期状態）、又は解析対象文Ｘに含まれる単語のペアの少なくとも１つに対し当該ペアの一方から他方への依存関係を付与した状態において、取りうる行動の各々に対して行われる。
【００２９】
特徴抽出関数Ｆは、ある状態ｓ（初期状態、又は依存関係を付与した状態）と行動ａとの組み合わせからｄ次元の実数ベクトルへ変換する関数であり、Ｆ：（ｓ，ａ）→ｆ∈Ｒｄと表記される。ただし、ｄはあらかじめ定められた定数であり、ｆは特徴ベクトルと呼ばれる。状態ｓは、解析対象文Ｘに対して、単語間の依存関係が部分的に付与された状態を指し、行動ａは、状態ｓにおいて、未だ依存関係が付与されていない単語間の中で、次に依存関係を付与する単語のペア、及び当該ペアのどちらが主要素でどちらが従要素であるか、という情報を表す。ある状態ｓにおいて、次に取る行動ａが決まると、次の状態ｓ’が一意に決定される。例えば、上記図６（Ａ）の二番目の状態では、状態ｓは、“I saw a man”の“I”が従要素、“saw”が主要素、それ以外の単語には依存関係の情報が付与されていない状態であり、行動ａは、“a”を従要素、“man”を主要素とする依存関係を新たに付与することを表している。
【００３０】
特徴抽出関数Ｆは、依存関係の主要素となる単語に関する特徴、及び依存関係の従要素となる単語に関する特徴を抽出したり、依存関係の主要素となる単語の前後の単語に関する特徴、及び依存関係の従要素となる単語の前後の単語に関する特徴を抽出する。例えば、特徴抽出関数Ｆは、上記非特許文献２に示されているように、行動ａに含まれる主要素および従要素となる単語や、その周囲の単語や品詞を０／１のバイナリベクトルで表現したものを用いることができる。
【００３１】
具体的には、特徴抽出部２４２は、まず、解析対象文Ｘを初期状態ｓ０とする。すなわち、ステップｔ＝０のとき、ｓｔ←Ｘとする。そして、特徴抽出部２４２は、状態ｓｔと、状態ｓｔから取り得る全ての行動ａと、それを受理するかしないかという情報ｂに対して、特徴抽出関数Ｆを用いて特徴ベクトルｆを計算する。ただし、ｂは、ｔｒｕｅかｆａｌｓｅの二値を取り、ｔｒｕｅのときは行動ａを受理する、ｆａｌｓｅのときは受理しないことを意味する。特徴ベクトルの計算結果を（ｓｔ，｛ｆａ，ｂ｝）と表記する。ただし、｛ｆａ，ｂ｝は各行動ａと受理フラグｂに関連付けられた特徴ベクトルｆａ，ｂの集合である。
【００３２】
また、状態ｓｔから取り得る全ての行動ａとは、状態ｓｔに依存関係が付与されていない単語間の依存関係で、かつ、過去のステップ１，２，．．．，ｔ−１において、後述する行動選択部２４４で選択されたことがない行動の集合である。
【００３３】
行動選択部２４４は、特徴抽出部２４２によって抽出された特徴に基づいて、依存関係が付与されていない単語のペアの各々に対して依存関係を付与する行動のうち、行動選択部２４４によって選択された行動を除いた行動から、当該行動を受理する場合の特徴に基づくスコア、及び当該行動を受理しない場合の特徴に基づくスコアの差分が最大となる行動を選択する。
【００３４】
具体的には、行動選択部２４４は、まず、特徴抽出部２４２によって抽出された｛ｆａ，ｂ｝から、各行動ａおよび受理フラグｂに関するスコアｖａ，ｂを計算する。スコアの計算式として、例えば、非特許文献２に示されているように、重みベクトルと特徴ベクトルの内積を用いれば良い。重みベクトルＷと特徴ベクトルｆとの内積をスコアと定義する場合、具体的な計算式は以下の式（１）に示すようになる。
【００３５】
【数１】
2015170044.tif 000003
【００３６】
ただし、ｆｉはｆのｉ次元目の値を表し、ｗｉは、重みベクトルＷのｉ次元目の値を表す。重みベクトルＷ∈Ｒｄは、特徴ベクトルｆと同じくｄ次元の実数ベクトルであり、状態ｓと行動ａから抽出された特徴ベクトルｆ∈Ｒｄに対して、実数のスコアｖ∈Ｒを計算するために用いられる。
【００３７】
スコアｖの値が高ければ、その状態ｓにおいて行動ａが起こりやすいことを表し、逆にスコアの値が小さければ、状態ｓにおいて行動ａが起こりにくいことを表す。
【００３８】
そして、行動選択部２４４は、受理するかしないかを最も判定しやすい行動ａ＾を選択する。これは、例えば、以下のようにｖａ，ｂ＝ｔｒｕｅとｖａ，ｂ＝ｆａｌｓｅの差の絶対値が最大となる行動を選択すれば良い。
【００３９】
【数２】
2015170044.tif 000004
【００４０】
従って、従来法のように「最も起こりうる」行動を選択するだけではなく、「この行動は起こりえない」という行動を選択することができる。
【００４１】
行動判別部２４６は、行動選択部２４４によって選択された行動を受理する場合の特徴に基づくスコア、及び行動を受理しない場合の特徴に基づくスコアに基づいて、行動選択部２４４によって選択された行動を受理するか否かを判別する。
【００４２】
具体的には、行動判別部２４６は、行動を受理する場合の特徴に基づいて算出されたスコアｖａ，ｂ＝ｔｒｕｅと、行動を受理しない場合の特徴に基づいて算出されたスコアｖａ，ｂ＝ｆａｌｓｅとを比較し、スコアの高い方：（ａ＾，ｂ＾）を選択する。ｂ＝ｔｒｕｅであれば、a＾を受理するということになり、ｂ＝ｆａｌｓｅであれば、ａ＾を受理しないことになる。
【００４３】
状態遷移部２４８は、現在の状態ｓｔと、行動判別部２４６で決定された（ａ＾，ｂ＾）に基づいて状態遷移を行い、次の状態ｓｔ＋１を決定する。具体的には、状態遷移部２４８は、ｂ＾＝ｔｒｕｅである場合、行動判別部２４６によって選択された当該行動を受理すると判別されているため、選択された行動ａ＾に含まれる単語のペアに付与される依存関係を状態ｓｔに追加する。ｂ＾＝ｆａｌｓｅである場合、状態は変更しない。ただし、特徴抽出部２４２の部分で説明したように、一度、行動選択部２４４で選択された行動ａ＾は、その後の行動選択過程において再び選択されることはなく、そのため、ｂ＾＝ｆａｌｓｅとなった場合には、その後のステップでも行動ａ＾を実行することは二度とない。したがって、この行動選択部２４４及び行動判別部２４６によって、本実施の形態では、擬似曖昧性が存在しないことが保証される。
【００４４】
終了判定部２５０は、予め定められた終了条件を満たすまで、行動選択部２４４による選択、行動判別部２４６による判別、及び状態遷移部２４８による遷移を繰り返す。
【００４５】
具体的には、終了判定部２５０は、状態遷移部２４８による状態遷移処理によって得られた状態ｓｔ＋１が完全な依存構造であるかを確認し、完全である場合には、状態遷移過程は終了し、解析結果Ｔ←ｓｔ＋１を出力する。完全でない場合には、ｔ←ｔ＋１として、特徴抽出部２４２へ戻る。ただし、依存構造が完全であるとは、文のいずれか一つの単語が主要素を持たず、かつ、それ以外の全ての単語が必ず一つの主要素を持つ状態を指す。例えば、上記図６（Ａ）の最終状態では、“saw”が主要素を持たない唯一の単語で、それ以外の全ての単語はただ一つの主要素を持つので、完全な依存構造である。
【００４６】
＜依存構造解析装置の作用＞
次に、本実施の形態に係る依存構造解析装置１００の作用について説明する。まず、解析対象文Ｘと、重みベクトルＷと、特徴抽出関数Ｆとが依存構造解析装置１００に入力されると、依存構造解析装置１００において、ＲＯＭに記憶されたプログラムをＣＰＵが実行することにより、図３に示す解析処理ルーチンが実行される。
【００４７】
まず、ステップＳ１００において、入力部１０によって、解析対象文Ｘと、重みベクトルＷと、特徴抽出関数Ｆとを受け付ける。そして、入力部１０によって、重みベクトルＷと、特徴抽出関数Ｆとをメモリ２２に格納する。
【００４８】
そして、ステップＳ１０２において、遷移型依存構造解析部２４によって、上記ステップＳ１００で受け付けた解析対象文Ｘと、重みベクトルＷと、特徴抽出関数Ｆとに基づいて、解析対象文Ｘの解析が行われる。ステップＳ１０２は、図４に示す依存構造解析処理ルーチンによって実現される。
【００４９】
まず、ステップＳ２００において、形態素解析部２４０によって、上記ステップＳ１００で受け付けた解析対象文Ｘについて、形態素解析を行って、解析対象文Ｘを単語に分割し、各単語に対して品詞を付与する。
【００５０】
ステップＳ２０１において、初期状態を設定し、現在の状態とする。
【００５１】
ステップＳ２０２において、特徴抽出部２４２によって、メモリ２２に格納された特徴抽出関数Ｆと、上記ステップＳ２００で得られた解析対象文Ｘの形態素解析結果とに基づいて、現在の状態において、依存関係が付与されていない単語のペアの各々に対して依存関係を付与する行動のうち、前回までのステップＳ２０６で選択された行動を除いた行動の各々について、当該行動を受理する場合の特徴、及び当該行動を受理しない場合の特徴を抽出する。
【００５２】
ステップＳ２０４において、行動選択部２４４によって、メモリ２２に格納された重みベクトルＷと、上記ステップＳ２０２で抽出された特徴に基づいて、依存関係が付与されていない単語のペアの各々に対して依存関係を付与する行動のうち、前回までのステップＳ２０６で選択された行動を除いた行動の各々について、上記式（１）に従って、当該行動を受理する場合の特徴に基づくスコアｖａ，ｂ＝ｔｒｕｅと、当該行動を受理しない場合の特徴に基づくスコアｖａ，ｂ＝ｆａｌｓｅとを計算する。
【００５３】
ステップＳ２０６において、行動選択部２４４によって、上記ステップＳ２０４で計算された当該行動を受理する場合の特徴に基づくスコアｖａ，ｂ＝ｔｒｕｅと、当該行動を受理しない場合の特徴に基づくスコアｖａ，ｂ＝ｆａｌｓｅとに基づいて、依存関係が付与されていない単語のペアの各々に対して依存関係を付与する行動のうち、前回までのステップＳ２０６で選択された行動を除いた行動から、上記式（２）に従って、スコアｖａ，ｂ＝ｔｒｕｅと、スコアｖａ，ｂ＝ｆａｌｓｅとの差分が最大となる行動を選択する。
【００５４】
ステップＳ２０８において、行動判別部２４６によって、上記ステップＳ２０６で選択された行動について、上記ステップＳ２０４で計算された、当該行動を受理する場合の特徴に基づくスコアｖａ，ｂ＝ｔｒｕｅと、当該行動を受理しない場合の特徴に基づくスコアｖａ，ｂ＝ｆａｌｓｅとに基づいて、上記ステップＳ２０６で選択された行動を受理するか否かを判別する。
【００５５】
ステップＳ２１０において、状態遷移部２４８は、上記ステップＳ２０８で選択された当該行動を受理すると判別された場合、選択された当該行動に対応する単語のペアに付与される依存関係を追加した状態に遷移させる。一方、上記ステップＳ２０８で選択された当該行動を受理しないと判別された場合、現在の状態を変更せずに、ステップ２０２へ移行する。
【００５６】
ステップＳ２１２において、終了判定部２５０によって、上記ステップＳ２１０で得られた状態が完全な依存構造であるか否かを判定する。上記ステップＳ２１０で得られた状態が完全な依存構造である場合には、ステップＳ２１４へ進む。一方、上記ステップＳ２１０で得られた状態が完全な依存構造でない場合には、ステップＳ２０２へ戻り、完全な依存構造が得られるまで、上記ステップＳ２０２〜Ｓ２１０の処理を繰り返す。
【００５７】
ステップＳ２１４において、最終的な状態に含まれる依存関係を依存構造解析結果Ｔとして出力して、依存構造解析処理ルーチンを終了する。
【００５８】
以上説明したように、本実施の形態の依存構造解析装置によれば、解析対象文の形態素解析結果に基づいて、依存関係が付与されていない単語のペアの各々に対して依存関係を付与する行動のうち、既に選択された行動を除いた行動の各々について、当該行動を受理する場合の特徴、及び当該行動を受理しない場合の特徴を抽出し、抽出された特徴に基づいて、行動を受理する場合の特徴、及び行動を受理しない場合の特徴の差分が最大となる行動を選択し、選択された行動を受理する場合の特徴、及び当該行動を受理しない場合の特徴に基づいて、選択された行動を受理するか否かを判別し、選択された行動を受理すると判別された場合、選択された行動に対応する単語のペアに付与される依存関係を追加した状態に遷移させることを繰り返すことにより、同一の依存構造へ到達する行動系列が複数存在しないように依存構造解析を行うことができる。
【００５９】
また、行動選択と行動判別の二種類の手続きによって、擬似曖昧性のない遷移型依存構造解析を行うことができる。したがって、複数の仮説を同時に考慮した場合に、それらが同じ依存構造へ到達することがなく、依存構造解析の性能が向上するという効果がある。
【００６０】
また、擬似曖昧性を取り除く処理が導入されることによって、複数の仮説を同時に考慮した場合に、それらが同じ依存構造へ到達することがないことが保証される。したがって、複数の仮説を同時に考慮した場合に、依存構造解析の解析性能が向上するという効果がある。
【００６１】
また、擬似曖昧性を取り除く処理が導入されるため、依存構造解析を高速に行うことができる。
【００６２】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００６３】
例えば、本実施の形態の依存構造解析装置１００は、メモリ２２を備えている場合について説明したが、例えばメモリ２２が依存構造解析装置１００の外部装置に設けられ、依存構造解析装置１００は、外部装置と通信手段を用いて通信することにより、メモリ２２を参照するようにしてもよい。
【００６４】
例えば、上述の依存構造解析装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【００６５】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【００６６】
１０   入力部
２０   演算部
２２   メモリ
２４   遷移型依存構造解析部
３０   出力部
１００ 依存構造解析装置
２４０ 形態素解析部
２４２ 特徴抽出部
２４４ 行動選択部
２４６ 行動判別部
２４８ 状態遷移部
２５０ 終了判定部
【図１】
2015170044.tif 000005
【図２】
2015170044.tif 000006
【図３】
2015170044.tif 000007
【図４】
2015170044.tif 000008
【図５】
2015170044.tif 000009
【図６】
2015170044.tif 000010