(57)【要約】【課題】パラメタベクトルを推定する際に、セグメント単位の誤り推定関数を厳密に求め、従来法で用いる近似的な計算法と同じ計算量で実現可能な手段を提供すること。【解決手段】学習データ１４４に分類タグの種類を示す出力ラベル候補を対応付けた出力候補グラフと、パラメタベクトル１４５の初期値とを記憶した記憶部と、学習データ１４４の所定の評価単位の出現確率を、パラメタベクトル１４５を変数として周辺確率により表す決定関数を用いて、学習データ１４４の正解の要素の出現確率と、正解の要素以外で最も出力されやすい要素の出現確率との差分を誤り推定関数として計算し、この推定関数を用いて設定される目的関数を最適化するパラメタベクトル１４５を算出するパラメタ学習部１４１３とを備える言語モデル学習装置とした。【選択図】図１８
2008217592.tif 000002
【特許請求の範囲】
【請求項１】
テキストデータに所定の分類タグを付与するために使用するパラメタベクトルを、予め前記分類タグが付与されたテキストデータである学習データから算出する言語解析モデル学習装置であって、
前記学習データに前記分類タグの種類を示す出力ラベル候補を対応付けた出力候補グラフと、前記パラメタベクトルの初期値とを記憶した記憶部と、
前記学習データの所定の評価単位の出現確率を、前記パラメタベクトルを変数として周辺確率により表す決定関数を用いて、前記学習データの正解の要素の出現確率と、前記正解の要素以外で最も出力されやすい要素の出現確率との差分を誤り推定関数として計算し、前記誤り推定関数を用いて設定される目的関数を最適化するパラメタベクトルを算出するパラメタ学習部とを備える
ことを特徴とする言語解析モデル学習装置。
【請求項２】
前記目的関数は、すべての最小評価単位についての前記誤り推定関数の出力の総和であり、前記目的関数を最適化するパラメタベクトルは、前記目的関数の出力を最小にする前記パラメタベクトルである
ことを特徴とする請求項１に記載の言語解析モデル学習装置。
【請求項３】
前記目的関数は、前記誤り推定関数を用いて設定される、次の式（１）に示すＦ値の分母であり、前記目的関数を最適化するパラメタベクトルは、前記目的関数の出力を最小にする前記パラメタベクトルである
ことを特徴とする請求項１に記載の言語解析モデル学習装置。
【数１】
2008217592.tif 000048
ただし、γは再現率と適合率とのトレードオフの度合いを示す定数、Ｍは正例セグメント数、ＦＰｌは負例の正例への間違い数の推定量、ＦＮｌは正例の負例への間違い数の推定量をそれぞれ示す。
【請求項４】
前記パラメタ学習部は、
Forward-Backwardアルゴリズムを用いて前記決定関数の出力を計算する
ことを特徴とする請求項１ないし請求項３のいずれか１項に記載の言語解析モデル学習装置。
【請求項５】
前記パラメタ学習部は、
前記目的関数の勾配を計算し、前記勾配が所定値以下になるまで、その時点のパラメタベクトルを用いて、前記目的関数を最適化するパラメタベクトルを再度算出する
ことを特徴とする請求項１ないし請求項４のいずれか１項に記載の言語解析モデル学習装置。
【請求項６】
テキストデータに所定の分類タグを付与するために使用するパラメタベクトルを、予め前記分類タグが付与されたテキストデータである学習データから算出する言語解析モデル学習装置における言語解析モデル学習方法であって、
前記言語解析モデル学習装置の記憶部には、前記学習データに前記分類タグの種類を示す出力ラベル候補を対応付けた出力候補グラフと、前記パラメタベクトルの初期値とが記憶され、
前記言語解析モデル学習装置のパラメタ学習部は、
前記学習データの所定の評価単位の出現確率を、前記パラメタベクトルを変数として周辺確率により表す決定関数を用いて、前記学習データの正解の要素の出現確率を計算し、
前記決定関数を用いて、前記正解の要素以外で最も出力されやすい要素の出現確率を計算し、
前記正解の要素の出現確率と、前記正解の要素以外で最も出力されやすい要素の出現確率との差分を誤り推定関数として計算し、
前記誤り推定関数を用いて設定される目的関数を最適化するパラメタベクトルを算出する
ことを特徴とする言語解析モデル学習方法。
【請求項７】
前記目的関数は、すべての最小評価単位についての前記誤り推定関数の出力の総和であり、前記目的関数を最適化するパラメタベクトルは、前記目的関数の出力を最小にする前記パラメタベクトルである
ことを特徴とする請求項６に記載の言語解析モデル学習方法。
【請求項８】
前記目的関数は、前記誤り推定関数を用いて設定される、次の式（１）に示すＦ値の分母であり、前記目的関数を最適化するパラメタベクトルは、前記目的関数の出力を最小にする前記パラメタベクトルである
ことを特徴とする請求項６に記載の言語解析モデル学習方法。
【数１】
2008217592.tif 000049
ただし、γは再現率と適合率とのトレードオフの度合いを示す定数、Ｍは正例セグメント数、ＦＰｌは負例の正例への間違い数の推定量、ＦＮｌは正例の負例への間違い数の推定量をそれぞれ示す。
【請求項９】
前記パラメタ学習部は、
Forward-Backwardアルゴリズムを用いて前記決定関数の出力を計算する
ことを特徴とする請求項６ないし請求項８のいずれか１項に記載の言語解析モデル学習方法。
【請求項１０】
前記パラメタ学習部は、
前記パラメタベクトルを算出後に、前記目的関数の勾配を計算し、前記勾配が所定値以下になるまで、その時点のパラメタベクトルを用いて、前記目的関数を最適化するパラメタベクトルを再度算出する
ことを特徴とする請求項６ないし請求項９のいずれか１項に記載の言語解析モデル学習方法。
【請求項１１】
請求項１ないし請求項５のいずれか１項に記載の言語解析モデル学習装置として、コンピュータを機能させる
ことを特徴とする言語解析モデル学習プログラム。
【請求項１２】
請求項９に記載の言語解析モデル学習プログラムを記録した
ことを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は言語解析処理の技術に関し、特に対象テキストに文法的又は意味的なラベルを付与するために用いる特徴パラメタベクトルを学習データ（コーパス）から作成する技術に関する。
【背景技術】
【０００２】
主に対象テキスト（以下、生テキスト）に対して、品詞の付与（専門用語でタギンク又はラベリングと呼ぶ）や、単語・文節区切り又は意味のある単語の連続の抽出（専門用語でチャンキング又はセグメンテーションと呼ぶ）を行う技術がある。
計算機上では、生テキストは、文章の先頭から末尾までの一本のストリーム(一次元上の記号列)とみなして処理されることから、テキストのラベリング及びセグメンテーションは、自然言語処理／機械学習分野の用語で系列ラベリングまたは、系列セグメンテーションという問題の種類に分類される。
【０００３】
このような、系列セグメンテーション及び系列ラベリングの例を図１に示す。
図１に示すように、系列ラベリングとは、入力される系列に対して、ラベルを付与する問題と定義される（ただし、系列（Sequence）とは記号の列を意味し、生テキストの場合は文字列や単語列等に相当）。また、自然言語処理分野では、単語列に対して品詞タグを付与する問題等がこれに含まれる。
また、同じく図１に示すように、系列セグメンテーションとは、入力系列に対して、部分系列単位の区分（セグメント）を求める問題と定義される。ただし、セグメントとは、一つ以上の記号の連続から成る（部分）記号列である。自然言語処理分野では、単語列に対して文節区切りを付与する問題等がこれに含まれる。
【０００４】
前記の系列セグメンテーションは、容易に系列ラベリングに帰着させることが可能であり、かつ、系列セグメンテーション問題を直接解くモデルを扱うよりも、系列ラベリング問題として解く方が簡単であるため、一般的には、系列ラベリングのモデルを用いて問題を解き、その後にセグメントに変換する方法が用いられる。
【０００５】
この系列セグメンテーションから系列ラベリングを解く方法として、「ＩＯＢラベリング法」が提案されている。このＩＯＢラベリング法では、セグメントの開始（Ｂ）と続き（Ｉ）、及びセグメント外（Ｏ）を現すラベルＢ，Ｉ，Ｏを用いてセグメントを個々のラベルに分割・変換をおこなう。
ここで、図２はＩＯＢラベリング法を説明する図面である。図２に示すように、セグメントの開始を示すラベルＢに注目することで、容易にかつ一意にラベルからセグメントに、又はセグメントからラベルに変換することが可能となる。
【０００６】
このように、系列セグメンテーションの問題は、ＩＯＢラベリング法により系列ラベリングと同じ問題とみなすことが可能であるため、系列ラベリングの問題として同一のモデルを用いて解くことができる。
【０００７】
ここで、系列ラベリング問題で、入力系列（観測データ）をｘ＝｛ｘ１，…，ｘｎ｝、出力系列をｙ＝｛ｙ１，…，ｙｎ｝と表すこととする。例えば、品詞タグ付けの場合は、ｘは生テキストに相当し、ｘｉはｉ番目の単語になる。また、ｙは、ｘの生テキストに対応する品詞タグ列であり、ｙｉはｉ番目の単語に付与される品詞となる。ここで、図３は、品詞タグ付けの例を示す図面である。図３に示すように、「山田 太郎 は 日本 の 首相 です 。」という生テキストｘに対して、各単語ｘｉについてその品詞を付与することを考える。
【０００８】
このとき、系列ラベリング問題では、任意の一つの出力ラベルｙｉはその周囲のラベル（例えば、ｙｉ−１やｙｉ＋１）に依存して決定される。つまり、個々のラベルｙｉは、入力系列ｘのみではなく出力系列ｙ自身に依存して決定される変数であると言える。よって、部分的に入力系列がまったく同じであっても、周囲の推定された出力ラベルによってはまったく別のラベルが付与される可能性がある。このように出力系列ｙ自身に相互依存性（または、相互依存構造）があるような問題を機械学習の研究分野では「構造学習問題」とよび、大まかには、局所最適解を組み合わせて解を得る古典的なモデルと、出力全体の大域的な最適解を直接学習／推定するモデルに分類することができる。それぞれの代表的なモデルとして、カスケードモデルと条件付き確率場がある。
【０００９】
カスケードモデルは、構造学習問題を解く古典的な方法である。従来、相互依存構造を持つ問題の大域的最適解を求めるためには、計算量が非常に大きくなるため、大域的最適解を求めることは現実的な解法ではなかった。そこで、局所最適解を組み合わせて全体の解を得る方法として、カスケードモデルが提案された。
ここで、図４は、カスケードモデルを適用した系列ラベリングの例を示す説明図である。局所最適解としては、図４に示すように、個々のラベルｙｉを独立に学習／推定する。この個々のラベルの学習／推定は、単純な分類問題とみなすことができるので、一般的に用いられる分類問題用の機械学習手法を用いることができる。つまり、カスケードモデルでは、個々のラベルごとに問題を分割して（多クラス）分類問題として一般的な学習手法を用いて解くことができる。
【００１０】
一方、条件付き確率場は、従来困難とされた大域的な最適解を求めるために考案されたモデルの一つである。機械学習の分野では、カスケードモデルが示すように、従来、データ中の個々のインスタンスは独立であるという仮定で学習を行ってきた。しかし、現実のデータでは、個々のインスタンス間に複雑な依存関係がある場合が多いことが知られている。
例えば、Ｗｅｂのホームページのカテゴリ分類の場合は、個々のインスタンス（ホームページ）を独立に扱って分類することができるが、文中の単語に対する品詞分類では、前後の文脈の情報によって与えられるラベルは異なるという特徴を持っている。
【００１１】
このように依存関係がある構造の学習を行う一つの方法として、マルコフ確率場(markov random field)という方法がある。ただし、マルコフ確率場は、もともと入力と出力の同時確率（ｐ（ｙ，ｘ））を求める方法として用いられるモデルであり、テキストのように、入力ｘが既知の場合には同時確率ではなく、条件付き確率（ｐ（ｘ｜ｙ））を求める方が、テキストの解析モデルを直接モデル化することになるので、解析性能が高くなることが推察できる。そこで、マルコフ確率場の枠組で、同時確率ではなく条件付き確率でも問題を解けるように改良した方法として、非特許文献１及び非特許文献２には、条件付き確率場（Conditiona1 Random Fields）が提案されている。これらの方法は、周辺の文脈に依存して出力を学習／推定するためのモデルである。
【００１２】
数多くの実験から、条件付き確率場のように大域的な情報を用いて最適化した方が、局所的な情報を組み上げて問題を解くカスケードモデルよりも性能がよいことが示されている。
ここで、図５は、条件付き確率場を適用した系列ラベリングの例を示す説明図である。図５に示すように、系列ラベリング問題を条件付き確率場(マルコフ確率場でも同じ)でモデル化する場合には、取り得る出力ラベル系列をあらわしたラティス状の出力候補グラフに含まれるパス中から、始端ノードから終端ノードヘの最適パス（最も確率の高いパス）を求める問題に帰着される。
なお、条件付き確率場を用いてモデルを「学習（パラメタ推定とも言う）」するとは、特徴抽出により抽出された特徴に対応したパラメタベクトルの重みを決定する作業である。
【００１３】
また、特徴抽出とは、一般的な機械学習問題で同じ処理であるが、入力ｘと出力ｙの関係を特徴付けるような情報を抽出する処理である。基本的に、入力ｘから特徴を抽出する特徴抽出関数は、対象とする問題に依存して人手で決定するのが一般的である。
ここで、図６は特徴抽出の例を示す説明図である。図６に示した例では、推定したいラベル（ｉ＝４）の前後２単語と、推定したいラベルとの組み合わせで特徴を特徴ベクトルとして抽出する。このように、系列ラベリング問題の場合は、入力ｘと出力ｙとの組合せで特徴を抽出することが一般的である。図６に示した例では、任意のラベルｙｉを推定する際に利用する特徴（関数）として、ｘｉ−２，ｘｉ−１，ｘｉ，ｘｉ＋１，ｘｉ＋２とｙｉの組合せを抽出する。
【００１４】
パラメタベクトルの重みを決定する学習は、特徴抽出関数により抽出された個々の特徴に対応するパラメタ（ベクトル）λの値を推定する問題となる。ここで「対応する」とは、個々の特徴とパラメタベクトルの要素が一対一に対応することを意味し、特徴ベクトルとパラメタベクトルの次元数は同じとなり、またｉ番目の特徴はｉ番目のパラメタベクトルの要素で重みが決定される。
【００１５】
条件付き確率場は以下のように定義される。入力(観測データ)に対する確率変数をｘ、出力に対する確率変数をｙ＝｛ｙ１，…，ｙｎ｝とする。ここで、確率変数ｙがマルコフ性を満たすとき、すなわち、ｐ（ｙｉ｜ｘ，ｙ１，…，ｙｉ−１，ｙｉ＋１，…，ｙｎ）＝ｐ（ｙｉ｜ｘ，Ｎ（ｙｉ））の条件を満たすとき、（ｘ，ｙ）は条件付き確率場である。ただし、Ｎ（ｙｉ）は、個々確率変数ｙｉ間の依存関係をグラフで表した際に接続する確率変数の集合を表す。つまり、確率変数ｙｉは、接続する確率変数Ｎ（ｙｉ）およびｘに依存して決まる変数である。一般的に、確率変数ｙｉ間の接続を表すグラフ内のクリーク集合をｃとすると、条件付き確率場は、個々のクリークのポテンシャル関数の対数線形モデルになる。
【００１６】
ここでは、系列ラベリング問題に特化した記述なので、系列ラベリングの場合のクリークのみを議論する。系列ラベリングの場合は、図５に示したようなラティス状の出力候補グラフを用いるので、クリークはｙｉ−１，ｙｉのラベルペアで構成されることになる。
ここで、図７は、条件付き確率場におけるクリークを説明する図面である。クリークとは、グラフ中の部分グラフのうち、完全グラフとなるノードの集合である。図７に示すように、ラティス状の出力候補グラフにおいて、隣り合う二つのノードのみが、クリークとなる。このため、リンクで結合された全ての隣り合うノードがクリークとなる。
なお、完全グラフとは、グラフ中のノードが自身以外の全てのノードとのリンクを持つ場合をいう。
【００１７】
図７からもわかるように、系列ラベリングでは、一つのパス中のクリーク数は系列の長さｎ＋１(ＢＯＳ（開始）ノード，ＥＯＳ（終端）ノードを含むため)となる。
このとき、条件付き確率場において、任意のクリークｃｉでの局所的な特徴をｆ（ｙ，ｘ，ｉ）と表し、λを特徴に対応したパラメタベクトルとする。ここで、図８は条件付き確率場におけるクリーク毎の特徴の例を示す図面である。このとき、条件付き確率場上の任意の出力ｙに対する条件付き確率は以下のように表すことができる。
【００１８】
【数１】
2008217592.tif 000003
【数２】
2008217592.tif 000004
【００１９】
数式（２）において、Ｚλ（ｘ）は正規化項を意味し、全ての出力の可能性の総和である。つまり条件付き確率場での条件付き確率分布ｐ（ｘ｜ｙ）は、出力系列ｙの各地点ｉでの局所的な特徴ｆ（ｙ，ｘ，ｉ）の重みを指数とした値の総積を、全ての可能性の出力系列の総和で割ったものとなる。
このとき、数式（１）は、次のように書き直すことができる。
【００２０】
【数３】
2008217592.tif 000005
【００２１】
前記の数式（３）から、一つのパス全体に対する大域的な特徴はＦを用いて次のように書き表すことができる。
【００２２】
【数４】
2008217592.tif 000006
【００２３】
つまり、系列の大域的な特徴は、各地点での局所的な特徴の総和で表されることを意味する。この大域的特徴Ｆに従うと、数式（１）の条件付き確率場による条件付き確率は以下のように書き直すことができる。
【００２４】
【数５】
2008217592.tif 000007
【数６】
2008217592.tif 000008
【００２５】
任意の出力系列ｙの確率は、出力候補グラフ中の出力系列が表すパス上のクリークから抽出される特徴とパラメタベクトルとの内積を、指数関数を用いて変換した値を、可能な全ての出力系列全体の値で割ったものとなる。
条件付き確率場上で、入力系列ｘに対して最も確率の高い出力系列
2008217592.tif 000009
は、次式により推定できる。
【００２６】
【数７】
2008217592.tif 000010
【００２７】
ここで、ｙは入力系列ｘに対する出力系列の候補の集合を表す。また、数式（５）中の正規化項Ｚλ（ｘ）はｙに依存しない値なので、最尤出力（argmax）を得る際には影響を及ぼさないので用いる必要はない。このように、数式（７）を用いて入力系列ｘを条件付き確率場に与えたときに、最も確率の高い出力系列ｙを得ることができる。
【００２８】
条件付き確率場の学習では、最尤推定に基づいて学習データ
2008217592.tif 000011
からの学習をおこなう。
【００２９】
【数８】
2008217592.tif 000012
【００３０】
ここで、ｙ＊は正解を表す。
【００３１】
一般的に、確率モデルでは実用上の観点から、確率の対数（対数尤度）を最大にするように学習を行う。これは、対数をとっても、最大値をとるパラメタの値は同じになる（確率と対数尤度は比例関係にある）ため、このような変換が可能である。これを一般的に、尤度最大化（Maximum Likelihood）学習と呼び、条件付き確率場上の学習では、以下の目的関数を最大化することになる。
【００３２】
【数９】
2008217592.tif 000013
【００３３】
目的関数である数式（９）の最適解は、目的関数のパラメタλによる微分が０になる点を探せばよい。
【００３４】
【数１０】
2008217592.tif 000014
【００３５】
ただし、
2008217592.tif 000015
は、大域的特徴Ｆの期待値を意味する。ここで用いる目的関数、数式（９）は、凸関数であるので唯一の最適解を持つ。実際の最適化には、最急降下法やニュートン法などの一般的な数値最適化アルゴリズムを用いて効率的に解くことができる。
【非特許文献１】J.Lafferty, A. MaCallum, and F.Pereira. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. In Proc. of ICML-2001, pages 282-289, 2001.
【非特許文献２】F. Sha and F. Pereira. Shallow Parsing with Conditiona1 Random Fields. In Proc. of HLT/NACCL-2003, pages 213-220, 2003.
【非特許文献３】Jun Suzuki， Erik McDermott, and Hideki Isozaki. Training Conditiona1 Random Fields with Multivariate Evaluation Measures. In Association for Computational Linguistics(ACL), pages 217-224, 2006.
【非特許文献４】磯崎秀樹 鈴木潤，誤り最小化に基づく条件付き確率場の学習:言語解析への適用，言語処理学会第１２回年次大会，2006年
【発明の開示】
【発明が解決しようとする課題】
【００３６】
前記のように、一般的には、条件付き確率場では、尤度最大化学習を用いて学習(パラメタベクトルλの推定)をおこなう。しかし、非特許文献３及び非特許文献４において、条件付き確率場を尤度最大化による学習(パラメタ推定)ではなく、実際に解きたいタスクの評価指標を基準として最大化(或は最小化)する学習手法が提案されている。
【００３７】
条件付き確率場によって学習したモデルを実問題に用いる際の性能評価は、対象とする問題に特化した評価指標を用いて性能を評価する場合がほとんどである。しかし、尤度最大化学習は、あくまで尤度(出力確率の対数)を最大化する学習であって、学習後の対象タスクの性能を最大化することは保証していない。つまり、非特許文献３及び非特許文献４で提案されている「評価指標最大化学習」は、この学習時に最適化する目的関数と、実際にタスク評価に用いる評価指標との不整合を解消することを可能としている。
【００３８】
具体的な例をあげる。系列セグメンテーションでは、各セグメント単位でのＦ値という指標を用いて系列セグメンテーションの性能を評価する。
【００３９】
【数１１】
2008217592.tif 000016
【００４０】
数式（１１）において、ＴＰ，ＦＰ，ＦＮは、それぞれtrue positive（正例の正解数），false positive（負例の正例への間違い数），false negative（正例の負例への間違い数）のセグメント数を表す。また、γは、Ｆ値を計算する上で、再現率と適合率とのトレードオフの度合いを決定するハイパーパラメータであり、目的とするタスクに合わせて人手により設定する値である。一般的には、γ＝１を用いてＦ値を計算する。
【００４１】
Ｆ値とは、主に正例・負例のように２種類の出力を前提に考えられた評価指標であり、「正例（positive）」を評価対象としたい出力のクラスとし、「負例（negative）」はそれ以外（評価対象としない）の出力のクラスとする。系列セグメンテーションの場合は、ＩＯＢラベリングのＯが付与されている場合を負例と考え、それ以外のラベルを全て正例として扱う。つまり、ＴＰやＦＮの最大数は正例セグメント数となり、ＦＰは全セグメント数が最大数となる。
【００４２】
数式（１１）と数式（９）とを比べてもわかるように、Ｆ値と系列の尤度にはある程度の相関関係はあるにせよ、比例関係のような密接な関係にあるような指標ではない。具体的な対比としては、数式（９）の右辺は、サンプル毎の尤度の総和（線形）をもちいるが、数式（１１）の右辺では、単純な総和ではなく正例・負例を考慮した分数の形（非線形）の式になっている。また、数式（９）は、系列全体を一単位として評価を行っているが、数式（１１）では、セグメントを一単位として評価を行っている。
このように、系列セグメンテーション問題において、尤度最大化学習によって学習を行ったとしても、解決したい問題の性能を最大にする学習をしているとは限らない。非特許文献３及び非特許文献４においては、通常の尤度最大化学習をおこなうよりも解決したい問題の評価指標を最大化する学習をおこなうことによって、さらに性能が向上することが示されている。
【００４３】
また、この枠組を用いることで、対象とする実問題の評価関数が「正解（又は誤り）の数」を基準として計算するような評価関数であれば、どのような評価関数であっても、条件付き確率場の学習に用いる目的関数として導入することが可能となる。つまり、一般的に用いられるような実問題の評価指標は基本的に正解（又は誤り）の数を基準として計算されるため、この枠組を用いることで、現在用いられているほとんどの評価指標を用いて条件付き確率場を学習することが可能となる。
【００４４】
「評価指標最大化学習」では、扱いたい評価指標によって学習時の最適化法を考案しなくてはいけない。評価指標最大化学習で、ある評価指標についての最適化法（アルゴリズムを含む）を考えるにあたり、評価指標が利用する（最小）評価単位をはじめに定義する必要がある。ここでは、系列ラベリング又はセグメンテーションを対象にしているので、評価単位としては主に（１）系列全体，（２）セグメント，（３）ラベル単体という３種類が考えられる。
【００４５】
基本的な手段として、評価指標最大化学習では、評価単位毎の正解出力ｙ＊と正解以外の出力候補ｙ（ｙ≠ｙ＊）の差分を用いる。そして、この評価単位毎の差分を対象とする評価指標に基づいて最大化するように学習をおこなう。つまり、最も間違えやすい出力候補と正解出力との差を扱う評価指標に基づいて、その差分を大きくするということは、最終的な評価指標を最大化することになる。
【００４６】
条件付き確率場で系列全体としての出力ｙの決定関数ｇ（）は、特徴ベクトルとパラメタベクトルの内積として次のように与えられる。
【００４７】
【数１２】
2008217592.tif 000017
【００４８】
決定関数とは、入力ｘとパラメタベクトルλを与えたときに、ある出力ｙが出力される尤度(またはスコア)を表す関数である。ただし、ここでの出力ｙは、評価の単位が系列全体の場合を表している。また、右辺の総和ｉは単一のクリーク単位での特徴ベクトルの総和を表している。このとき誤り推定関数は、決定関数を用いて次のように定義できる。
【００４９】
【数１３】
2008217592.tif 000018
【００５０】
誤り推定関数とは、学習データに付けられた正解と正解以外の出力と比較してどの程度、間違えやすいかという推定量を出力する関数である。ここでは、正解と正解以外の出力候補との差分で表す。つまり、最も間違えやすい出力候補と正解との決定関数の差分が大きければ大きい程、間違えにくいということを意味する推定量である。
【００５１】
最終的には、この誤り推定関数ｄ（）を用いて利用したい評価指標に基づいた目的関数を構成する。つまり、評価時の評価指標の計算を、学習時には、誤り推定関数の返す値を利用して評価指標を計算するという手順になる。ただし、数式（１３）を用いる場合、誤り推定関数は［-∞，∞］の値域をとるが、実際の評価指標では［０，１］の値域のみを利用したい場合が考えられる。例えば、正解率で評価する場合は、誤りの数で評価指標が構成されているので、正解を１，誤りを０として計算したい。そこで、一般的には平滑化関数を用いて値域を変換する。平滑化関数の例として、シグモイド関数等がある。ここで、図９は、平滑化関数の例を示す図面である。図９には、平滑化関数の例として、ステップ関数、シグモイド関数及びロジステック関数をあげる。
ただし、平滑化関数は計算不能等を引き起こさないための一つの手段であり、評価指標最大化学習に必須の手法や条件というわけではない。
【００５２】
評価単位が系列全体に対する評価指標を扱う場合には、数式（１３）のような誤り推定関数ｄ（）を用いればよい。系列全体を扱う時と同様に、セグメント単位での誤り推定関数ｄ［ｉ，ｊ］（）（位置ｉ〜ｊまでの区間の場合）を定義すればよい。
ここで、図１０は、非特許文献３及び非特許文献４に記載の誤り推定計算方法を説明する図面である。図１０に記載の方法では、正解パスと正解パス以外で最も出力されやすいパスとの差分を計算し、このセグメント単位での誤り推定関数を系列全体の誤り推定関数を用いて、近似的に計算をおこなっている。
ただし、正解パス以外で最も出力されやすいパスとは、対象セグメントｙ２ｙ４間で、正解パスと一致しないパスの中から選択される。
【００５３】
【数１４】
2008217592.tif 000019
【００５４】
このように、系列全体の誤り推定関数を利用してセグメントの誤り推定関数を構成しているのは、条件付き確率場が、元来系列全体に対する尤度最大化学習という枠組を提供していることから、系列全体に対する決定関数ｇ（）や誤り推定関数ｄ（）に対する効率的な計算法が確立されていたという背景がある。また逆に、評価指標最大化学習の枠組での系列ラベリング／セグメンテーションでは、セグメント単位での誤り推定関数を厳密に計算する方法・アルゴリズムがこれまで発明されていなかったため、近似的な方法を用いていたという背景もある。つまり、非特許文献３及び非特許文献４では、条件付き確率場の学習時に用いる計算アルゴリズムとほぼ同じアルゴリズムを用いることで、セグメント単位の誤り推定関数の計算を近似的に実現していた。
【００５５】
しかし、一方で、従来技術のように、系列全体に対する誤り推定関数を近似的に用いると、本来最適化したいセグメント単位の評価指標を真に最大化しているという保証はない。
このことを、従来技術の問題点を説明する図面である図１１を参照しつつ説明する。図１１に示した出力候補グラフの対象区間［ｉ＝２，ｊ＝２］において、パス単位の値を用いた場合には、ｃ−ｌ−ｏ：３．８であるＣノードが出力されるが、セグメント単位の値を用いた場合には、セグメント尤度が８．８のＢノードが出力されてしまう。
【００５６】
セグメント単位で見た場合、セグメントの出力確率と系列の出力確率に基づくセグメントの出力確率には、相関はあるが一致はしないから起こる不整合である。つまり、厳密な意味で、本来の目的である評価指標を最大化していない可能性がある。
【００５７】
以上の問題を解決するため、本発明は、パラメタベクトルを推定する際に、評価単位（セグメント単位、ラベル単位や系列全体の場合も含む)の誤り推定関数を厳密に求め、従来法で用いる近似的な計算法と同じ計算量で実現可能な手段を提供することを目的とする。
【課題を解決するための手段】
【００５８】
前記の課題を解決するためになされた本発明に係る言語解析モデル学習装置は、テキストデータに所定の分類タグを付与するために使用するパラメタベクトルを、予め分類タグが付与されたテキストデータである学習データから算出するものであって、学習データに分類タグの種類を示す出力ラベル候補を対応付けた出力候補グラフと、パラメタベクトルの初期値とを記憶した記憶部と、学習データの所定の評価単位の出現確率を、パラメタベクトルを変数として周辺確率により表す決定関数を用いて、学習データの正解の要素の出現確率と、正解の要素以外で最も出力されやすい要素の出現確率との差分を誤り推定関数として計算し、推定関数を用いて設定される目的関数を最適化するパラメタベクトルを算出するパラメタ学習部とを備えることを特徴としている。
本発明に係る言語解析モデル学習装置によると、学習データの評価単位の要素の厳密な出現確率に基づく評価指標最大化学習を行うことができる。
【００５９】
なお、本発明のその他の態様については、後記する最良の形態において詳しく説明する。
【発明の効果】
【００６０】
本発明によると、従来技術と比較して様々な点が改善される。
厳密な出現確率に基づく評価指標最適化学習を行うことが可能となるため、最適化したい評価指標の意味で最良の学習結果を得ることが可能となる。従来技術は、目的関数を評価指標に置き換えるための方法論を示したが、実際に評価単位での出力確率を求める際には、従来から用いられてきた計算アルゴリズムを流用して近似値を用いていた。このため、枠組としては、評価指標最大化を行う学習法であったが、実際には評価指標を最大化していない可能性を含んでいた。一方、本発明はその問題点を改善し、厳密な出力確率に基づいて評価指標を最適化することを可能とする。
【００６１】
また、評価単位の出力確率を求めることができるため、この出力結果を用いてさらに処理を行う際に、出力値を確率として扱うことが可能となる。例えば、本発明を用いた固有表現抽出を行って、それを情報検索に用いる場合、出力された固有表現がどのくらい信頼性があるかといった指標として用いることができたり、確率論に基づいた情報検索システムであれば、本発明を用いた固有表現システムをそのまま情報検索システムと結合することが可能となる。従来法では、出力値が確率の定義を満たさない可能性があるため、このような状況で、そのまま出力値を扱うことができなかった。
【発明を実施するための最良の形態】
【００６２】
以下、本発明の方式を説明し、その後、その方式を適用した発明を実施するための最良の形態（以下、実施形態）について説明する。
【００６３】
（言語モデルの学習方法の概略）
ここで、図１２は、あるセグメントの出力確率を説明する図面である。
図１２に示す出力候補グラフにおいて、出力系列ｙ中の位置ｉから位置ｊまでの間のセグメントの（部分）出力系列ｙ［ｉ，ｊ］の出力確率は、周辺確率を用いて以下のように定義することができる。
【００６４】
【数１５】
2008217592.tif 000020
【００６５】
数式（１５）において、
2008217592.tif 000021
は、セグメント［ｉ，ｊ］間のパスを通る全てのパスの重みの総和を表している。また、α［０，ｉ］（ｙｉ）及びβ［ｊ，ｎ］（ｙｊ）は、それぞれ、前側確率及び後側確率であり、［ｉ，ｊ］間の周辺確率を表している。図１２に示した例では、α［０，ｉ］（ｙｉ）は、セグメント［０，２］の確率を、β［ｊ，ｎ］（ｙｊ）は、セグメント［４，６］の確率をそれぞれ表す。そして、前側確率は、次に示す数式（１６）のように定義される。
【００６６】
【数１６】
2008217592.tif 000022
【００６７】
ただし、ｉ＝０のときは、α［０，０］（ｙ０）＝1とする。また、Ｙを単一のラベルの(とりうる全てのラベル)集合とする。同様に後側確率も、次に示す数式（１７）のように定義される。
【００６８】
【数１７】
2008217592.tif 000023
【００６９】
ただし、ｊ＝ｎのときは、β［ｎ，ｎ］（ｙｎ）＝１とする。
数式（１５）の分母は、ｙに依存しないので、最終的にセグメント単位の出現確率を基準にしたセグメント単位の決定関数は次のように表せる。
【００７０】
【数１８】
2008217592.tif 000024
【００７１】
よって、このセグメント出現確率に基づいた決定関数を用いると、誤り推定関数ｄ（）は次のように表せる。
【００７２】
【数１９】
2008217592.tif 000025
【００７３】
ここで、図１３は、図１２に示す出力候補グラフにおける数式（１９）の意味を説明する図面である。図１３に示しように、数式（１９）における−ｇ［ｉ，ｊ］（ｙ＊，ｘ，λ）の項は、正解セグメントの出現確率を示し、それ以下の項は、正解以外で最も出力されやすいセグメントの出現確率を示している。ただし、正解以外で最も出力されやすいセグメントとは、対象区間［２，４］間で正解セグメントと一致しないセグメントの中から選択される。
【００７４】
周辺確率を用いることで、系列中から対象セグメントが選択される確率を厳密に求めることが可能となる。これにより、誤り推定関数は、正解セグメントが出力される確率とそれ以外のセグメントが出力される確率との差分を利用して学習を行うことになる。
【００７５】
誤り推定関数として、従来技術の数式（１３）と数式（１９）とを比較すると、表層的には従来技術でセグメント単位の決定関数を系列全体の値で近似していたものを、セグメント単位で正確に計算した値に置き換えた形になる。ただし、決定関数として、従来技術の数式（１２）と数式（１８）とを比較すると、従来技術では系列の重みを用いていたのに対して、本発明では周辺確率用いたセグメントの出現確率に基づいた重みを用いているという違いがわかる。
【００７６】
実際の計算アルゴリズムとしては、α０，ｋ（ｙｋ）やβｌ，ｎ（ｙｌ）は、forward-backwardアルゴリズムを用いることにより効率的に計算することが可能である。つまり、従来技術では、Viterbiアルゴリズムを前からと後ろからの２パスで計算することで、系列全体の出力確率から対象セグメントの決定関数と誤り推定関数とを近似していたが、本発明では、その代わりにforward-backwardアルゴリズムを用いて、セグメント単位の決定関数や誤り推定関数を計算する。また、従来技術に係る２パスViterbiアルゴリズムと、本発明に係るforward-backwardアルゴリズムの計算量は全く同じになることから、本発明によると、従来技術と同じ計算量で厳密なセグメント単位の出力確率に基づいた最適化が可能となる。
【００７７】
（テキスト解析装置）
次に、前記の方式を適用した本発明の実施形態に係るテキスト解析装置について説明する。図１４は本実施形態のテキスト解析装置のブロック構成図である。図１４に示すように、テキスト解析装置１は、演算装置であるＣＰＵ（Central Processing Unit）１１、後記するプログラムが展開され、一時記憶されるデータが保持されるＲＡＭ（Random Access Memory）１２、外部との入出力インタフェースである入出力部１３及びハードディスクドライブ等からなるストレージ１４とを相互に接続して構成され、パーソナルコンピュータ等を用いて具現される。
【００７８】
また、テキスト解析装置１のストレージ１４には、ＣＰＵ１１が実行することで、それぞれ学習器１４１、推定器１４２及びタグ／セグメント変換器１４３として動作するプログラムと、各プログラムが使用又は生成する学習データ１４４、パラメタベクトル１４５、生テキスト１４６、タグ付きテキスト１４７及びセグメント別タグ付きテキスト１４８とが記憶されている。
なお、各プログラムの動作及び各データの内容については後記する。また、ストレージ１４に記憶された各プログラム及び各データは、コンピュータで読み取り可能な各種の記録媒体（ＣＤ−ＲＯＭ等）に記憶することができる。
【００７９】
（テキスト解析装置の動作の概略）
次に、図１５は、前記の構成を有するテキスト解析装置１の処理動作の概略を説明する説明図である。図１５を参照しつつ、テキスト解析装置１の処理動作を説明する。
【００８０】
テキスト解析装置１の動作は、タグ付きコーパスである学習データに基づいて、パラメタベクトルを計算する学習フェーズと、計算されたパラメタベクトルを用いて生テキストにタギンク又はチャンキングを行う評価フェーズとに大きく分けられる。
【００８１】
図１５に示すように、学習フェーズでは、学習器１４１が、タグ付きコーパスである学習データ１４４の入力を受けて、パラメタベクトル１４５を出力する。
そして、評価フェーズに移って、推定器１４２が、この出力されたパラメタベクトル１４５を用いて、生テキスト１４６に対してタギングを実行し、タグ付きテキスト１４７を出力する。そして、タグ／セグメント変換器１４３が、推定器１４２が出力したタグ付きテキスト１４７に対して、チャンキングを実行し、セグメント別タグ付きテキスト１４８を出力する。ここで、参考として、図１６に、学習器１４１に入力される学習データ１４４及び出力されるパラメタベクトル１４５の例を、図１７に、推定器１４２に入力される生テキスト１４６及び出力されるタグ付きテキスト１４７の例をそれぞれ示す。
【００８２】
なお、推定器１４２における処理は、学習器１４１における処理において、学習データ１４４の代わりに生テキスト１４６を入力し、パラメタベクトル１４５の初期値の代わりに学習器１４１の計算したパラメタベクトル１４５を入力したものであるため、その詳細な説明は省略する。また、タグ／セグメント変換器１４３における処理は、前記のように公知のアルゴリズムを適用することができるため、同じくその詳細な説明を省略する。
また、図１５に示した動作例では、推定器１４２は、タギングを実行してタグ付きテキスト１４７を出力することとしたが、チャンキングを実行してセグメント付きテキストを出力して、タグ／セグメント変換器１４３において、タギングを実行してセグメント別タグ付きテキスト１４８を出力することにしてもよい。
【００８３】
（学習器の構成・動作）
次に、テキスト解析装置１の構成要素のうち、学習器１４１について詳しく説明する。なお、学習器１４１は、特許請求の範囲の言語解析モデル学習装置に相当し、学習器１４１における処理手順は、言語解析モデル学習方法に相当している。
【００８４】
ここで、図１８は、学習器１４１の詳細ブロックを示す図面である。図１８に示すように、学習器１４１は、出力候補グラフ生成部１４１１、特徴抽出部１４１２及びパラメタ学習部１４１３を備えている。
出力候補グラフ生成部１４１１は、学習データ１４４及び入出力部１３から入力された出力ラベル候補に基づいて出力候補グラフを生成する。特徴抽出部１４１２は、入出力部１３から入力された特徴抽出テンプレートを取得し、出力候補グラフ生成部１４１１が生成した出力候補グラフ上のクリーク単位に特徴を抽出し、パラメタベクトル１４５の次元数を計算し、その初期値を設定する。パラメタ学習部１４１３は、出力候補グラフ及び特徴抽出部１４１２が設定したパラメタベクトル１４５の初期値に基づいて、学習基準アルゴリズムにより、パラメタベクトル１４５を学習する。
【００８５】
次に、図１９は、学習器１４１の処理手順を示すフローチャートである。図１９を参照しつつ、学習器１４１における処理手順を詳しく説明する。なお、以下の手順において、各構成要素が生成又は計算した情報は、ＲＡＭに一時記憶されるものとし、その記載は省略する。
【００８６】
まず、学習器１４１を動作させる準備として、学習に用いる評価指標を決定（主に対象とする問題の評価指標を利用）し、この決定した評価指標に基づいて評価の（最小）単位を決定する。そして、決定した評価指標及び評価の単位に基づいて、学習に用いる目的関数を決定しておく。
【００８７】
そして、学習器１４１の動作が開始され、学習器１４１の出力候補グラフ生成部１４１１は、ストレージ１４から学習データ１４４
2008217592.tif 000026
を所得して（ステップＳ１０１）、ＲＡＭ１２に記憶する。
【００８８】
次に、出力候補グラフ生成部１４１１は、入出力部１３を介して対象とする問題に依存した出力ラベル候補集合を取得し（ステップＳ１０２）、ＲＡＭ１２に記憶する。そして、ＲＡＭ１２に記憶した学習データ及び出力ラベル候補集合に基づいて、出力候補グラフを生成する（ステップＳ１０３）。
【００８９】
次に、出力候補グラフ生成部１４１１は、特徴抽出部１４１２に処理を受け渡し、特徴抽出部１４１２は、入出力部１３を介して特徴抽出テンプレートを取得し（ステップＳ１０４）、ＲＡＭ１２に記憶する。そして、出力候補グラフ生成部１４１１が生成した出力候補グラフ上のクリーク単位に特徴ベクトルを抽出し、パラメタベクトル１４５の次元数を計算する（ステップＳ１０５）。さらに、特徴抽出部１４１２は、パラメタベクトル１４５の初期値を設定する。なお、このパラメタベクトル１４５の初期値とは、例えば、パラメタベクトル１４５の各要素を、０と設定したものである。
【００９０】
次に、特徴抽出部１４１２は、パラメタ学習部１４１３に処理を受け渡し、パラメタ学習部１４１３は、出力候補グラフ生成部１４１１が生成した出力候補グラフ及び特徴抽出部１４１２が計算した次元数を有するパラメタベクトル１４５の初期値に基づいて、学習基準アルゴリズムにより、パラメタベクトル１４５を学習し（ステップＳ１０６）、ストレージ１４に学習結果を記憶する。
【００９１】
（パラメタ学習部における処理の詳細）
次に、図２０は、パラメタ学習部１４１３の詳細な処理手順を示すフローチャートである。図２０を参照しつつ、ステップＳ１０６におけるパラメタ学習部１４１３の処理をさらに詳細に説明する。
【００９２】
図１９に示したフローチャートのステップＳ１０７に処理が移ると、パラメタ学習部１４１３は、その時点のパラメタベクトル１４５を用いて、各評価単位に対して正解出力のスコア（重み）を計算する（ステップＳ２０１）。そして、その時点のパラメタベクトル１４５を用いて、各評価単位に対して正解以外の出力候補（最尤出力候補）のスコアを計算する（ステップＳ２０２）。
【００９３】
次に、パラメタ学習部１４１３は、各評価単位に対して、ステップＳ２０１で計算した正解出力のスコアと、ステップＳ２０２で計算した最尤出力候補のスコアとの差分を計算する（ステップＳ２０３）。そして、事前に決定された評価指標に基づいて目的関数Ｌを計算する（ステップＳ２０４）。
【００９４】
次に、パラメタ学習部１４１３は、ステップＳ２０４で計算した目的関数Ｌの勾配∇Ｌλを計算して（ステップＳ２０５）、目的関数Ｌが収束したか否かを判定する（ステップＳ２０６）。この判定は、例えば、勾配∇Ｌλが所定値以下か否かで判定することができる。ここで、目的関数Ｌが収束してなければ（ステップＳ２０６で‘Ｎｏ’）、勾配∇Ｌλの値を用いてスコアを更新しステップＳ２０１に戻る。一方、目的関数Ｌが収束した場合は（ステップＳ２０６で‘Ｙｅｓ’）、その時点のパラメタベクトル１４５をストレージ１４に記憶して処理を終了する（図１９のステップＳ１０６に戻る）。
【００９５】
次に、学習器１４１の動作（学習フェーズ）として、系列セグメンテーションを行う２つの具体的な例を示しつつ、さらに詳しく説明する（適宜、図１８〜２０参照）。
【００９６】
（具体例１:正解率を評価指数とする系列セグメンテーション）
具体例１では、系列セグメンテーション問題で、「評価単位」を「セグメント」とし、「評価指標」を「セグメント単位の正解率」とした場合の具体例を示す。この評価単位及び評価指標の決定は、図２０に示したステップＳ２０４において適用する評価指標（学習基準）を決定することに相当し、学習器１４１の処理の前準備として事前に決定される。
系列セグメンテーション問題で、前記のように「評価単位」を「セグメント」とし、「評価指標」を「セグメント単位の正解率」とした場合の目的関数は以下のようになる。
【００９７】
【数２０】
2008217592.tif 000027
【００９８】
ただし、正解率は、エラー率の反比例の関係にあり、数式（１９）の誤り推定関数は正解のスコアが大きいときには大きなマイナスの値をとるように定義されているので(一般的に機械学習分野では誤り最小化で定義するため)、実際にはエラー率最小化を行う。
【００９９】
【数２１】
2008217592.tif 000028
【０１００】
ゆえに、目的関数を次のように定義する。
【０１０１】
【数２２】
2008217592.tif 000029
【０１０２】
なお、総セグメント数は定数になるので、目的関数には含めない。
その後、図１９に示したフローチャートしたがって、学習器１４１の出力候補グラフ生成部１４１１は、学習データ（タグ付きコーパス）を取得する（ステップＳ１０１）。また、同時に出力ラベル候補集合を取得する（ステップＳ１０２）。
【０１０３】
ここで、図２１は、出力候補グラフ生成部１４１１が取得した学習データ等の例を示す図面である。図２１（ａ）は、学習データの例を示し、「田中・一郎・は・陸上・連盟・の・会長・です」（形態素区切りは事前にあるという設定）といったテキストにラベルが付与されているものが入力される。また、このときの出力ラベル候補は図２１（ｂ）に示すように、「Ｂ−人名，Ｉ−人名，Ｂ−組織名，Ｉ−組織名，Ｏ」の５種類のラベルが出力ラベル候補集合となる。
【０１０４】
次に、取得した学習データに基づいて、出力候補グラフ生成部１４１１は出力候補グラフを生成する（ステップＳ１０３）。ここで、図２１（ｃ）は、出力候補グラフ生成部１４１１が、図２１（ａ）の学習データ及び図２１（ｂ）の出力ラベル集合に基づいて生成した出力候補グラフの例である。図２１（ｃ）に示した出力候補グラフは、可能性のある全ての出力候補をパスで接続したラティス形式をとる。つまり、出力候補グラフ中のＢＯＳノードからＥＯＳノード間の一つのパスが一つの出力に対応し、出力候補グラフは、とり得る全ての出力の候補を包含したグラフになっている。
【０１０５】
さらに、出力候補グラフと特徴抽出テンプレートとを用いて、出力候補グラフの各ノード(またはリンク)に特徴ベクトルを付与する。
特徴抽出テンプレートは、図６に示したような形式であり、ここでは、前後２単語の特徴を用いて対象とする位置のノードの特徴ベクトルを作成する。このとき、前後２単語とノードが属する出力ラベルの組合せで特徴を生成するため、同じ位置で出力ラベルの違うノード間の特徴ベクトルは、お互い直行する（内積０になる）関係になる。
【０１０６】
具体的な例として、図２１（ｃ）に示した出力候補グラフに対して、図２２に示したような特徴ベクトルが各ノードに付与される。
以上の前処理を経て、特徴ベクトル付き出力候補グラフと、初期化されたパラメタベクトル（全ての要素が０のベクトル）とをパラメタ学習部１４１３に入力して、学習が開始される。
【０１０７】
次に、パラメタ学習部１４１３の動作について説明する（図２０参照）。例えば、図２３に示した「田中 一郎 は 陸上 連盟 の 会長 です」というテキストと、正解出力が「Ｂ−人名，Ｉ−人名，Ｏ，Ｂ−組織名，Ｉ−組織名，Ｏ，Ｏ，Ｏ」の場合で、区間［４，５］を評価する場合を示す。
この区間での正解は、「Ｂ−組織名，Ｉ−組織名」なので、この二つのノードを通過する全てのパスのスコアを用いて、区間［４，５］で「Ｂ−組織名，Ｉ−組織名」が出力される周辺確率に基づいた決定関数を求める。この処理は、正解出力のスコアを計算する処理（ステップＳ２０１）に相当する。
【０１０８】
このときの計算式には、数式（１９）を用いる。前側確率のα［０，ｉ］（ｙｉ）は、ｉ＝４及びｙ４＝Ｂ−組織名となる。つまり、位置４のＢ−組織名のノードに接続する前側のパス全てのスコアを表している。これは、forwardアルゴリズムで求められる。
また、同様に後側確率のβ［ｊ，ｎ］（ｙｊ）は、ｊ＝５及びｙ５＝Ｉ−組織名であり、位置５のＩ−組織名のノードに接続する後側のパスのスコアである。これも、backwardアルゴリズムにより求められる。
【０１０９】
次に、正解セグメントを除いて最もスコアの高いセグメントを求める。この処理は、最尤出力候補のスコアを計算する処理（ステップＳ２０２）に相当する。
これは、計算方法自体は正解セグメントの計算と同じであり、同一区間内で正解以外のとり得る全てのセグメントの計算を行い、最大値のセグメントを選出すればよい。
【０１１０】
ここで得られた正解セグメントと最尤出力候補セグメントのスコアを用いて、数式（１９）を計算する。この処理は、差分を計算する処理（ステップＳ２０３）に相当する。
これで、区間［４，５］に対する誤り推定を行うことができた。ここでは、セグメント単位の正解率を用いるので、平滑化関数として1ogistic関数を用いることを考える（図９参照）。これにより、誤り推定関数の値は［０，∞］の値域をとり、正解セグメントの決定関数の値が大きければ大きいほど値が０に近い値を返す。
【０１１１】
数式（２２）のセグメントエラー率は、単なるセグメント単位の誤り推定関数の総和で計算できるので、以上の処理を各セグメントに対しておこなう。この処理は、評価指標に基づいて目的関数Ｌを計算する処理（ステップＳ２０４）に相当する。
【０１１２】
そして、最終的に求めたいものは目的関数を最小化するパラメタベクトルλである。そこで、微分して０になるパラメタベクトルを求める。次に、パラメタ更新をおこなうために、目的関数（式（２２））の勾配を求める。この処理は、目的関数の勾配を計算する処理（ステップＳ２０５）に相当する。
数式（２２）の微分は、chain ruleを用いて以下のように分解して考えることができる。
【０１１３】
【数２３】
2008217592.tif 000030
【０１１４】
目的関数を平滑化関数ｌで微分したものは、1ogistic関数の定義にしたがって以下のようになる。
【０１１５】
【数２４】
2008217592.tif 000031
【０１１６】
ここで、誤り推定関数ｄ（）のパラメタに対する偏微分を示す。
【０１１７】
【数２５】
2008217592.tif 000032
【数２６】
2008217592.tif 000033
【数２７】
2008217592.tif 000034
【０１１８】
誤り推定関数ｄ（）のパラメタの偏微分は、対象セグメントを通るパス上の各ノード（リンク）が出力される期待値となることがわかる。ゆえに、Forward-Backwardアルゴリズムを利用することで各パラメタの勾配を効率的に計算することができる。
【０１１９】
ここで計算した勾配を元に、一般的に用いられる数値最適化法を利用してパラメタを更新する。その際にパラメタの更新量が収束していたら学習は終了となり（ステップＳ２０６で‘Ｙｅｓ’）、パラメタベクトル１４５をストレージ１４に出力して（ステップＳ２０７）処理を終了する。
一方、収束していない場合は（ステップＳ２０６で‘Ｎｏ’）、パラメタ学習の最初に戻る。この収束判定は、例えば、パラメタベクトルの変化量が十分小さい場合（所定の閾値以下となった場合）に収束したとみなす。
【０１２０】
この具体例によると、目的関数として、正解セグメントの出現確率と正解セグメント以外で最も出力されやすいセグメントの出現確率との差分を用いるため、全確率を学習に用い、目的関数が連続凸関数となる。従来技術では、目的関数が非連続(凸)関数になる可能性があるため、通常の数値最適化法を単に適用するということはできなかった。つまり、非連続点に対応した数値最適化法を用いる必要があった。しかし、本具体例により、制約無しの一般的な数値最適化法を用いることが可能となり、計算効率を向上させることが可能となる。
【０１２１】
（具体例２：Ｆ値を評価指標とする系列セグメンテーション）
次に、系列セグメンテーションで「評価単位」を「セグメント」とし、「評価指標」を「Ｆ値」とした場合の具体例を示す。ここでは、数式（１１）に示したＦ値を最大化する場合を示す。これには、以下の式を最小化することと等価である。
【０１２２】
【数２８】
2008217592.tif 000035
【０１２３】
ただし、Ｍは正例セグメント数とする。また、ＦＰｌ，ＦＮｌは学習時のＦＰ（false positive）とＦＮ（false negative）の推定値を表す。これは、数式（１１）を、次のように変形した際の分母であり、分母を最小化することが全体の最大化になるということから導出される。
【０１２４】
【数２９】
2008217592.tif 000036
【０１２５】
数式（２９）から、ＦＰ，ＦＮの推定量ＦＰｌ，ＦＮｌを計算することができれば、Ｆ値の最大化が可能となる。よって、正解率ではなく、系列セグメンテーションで数式（１１）に示されたＦ値を最大化したい場合は、数式（２８）を目的関数として学習をおこなう。以下、ＦＰｌ，ＦＮｌの導出手順を説明する。
【０１２６】
まず、ＦＮｌについて説明する。前記のようにＦＮ（false negative）、つまり、正例を間違える推定量であるＦＮｌは、誤り推定関数を用いて次のように定義できる。
【０１２７】
【数３０】
2008217592.tif 000037
【０１２８】
ただし、ＦＮｌは正例を間違える推定量なので、正例に関してのみ計算を行えばよいため、２番目の総和は正例の正解セグメントに対してのみ計算する。
【０１２９】
次に、ＦＰｌについて示す。ＦＰｌは、正例へ間違える推定量なので、負例への間違いは考慮されない。よって、誤り推定関数を計算する際に、負例への誤りは計算に含めないように式を変形する必要がある。
【０１３０】
【数３１】
2008217592.tif 000038
ただし、正解セグメントがＯであった場合は、負例への間違いというのは存在しないので、数式（１９）の計算と等価となる。よって、正例へ間違える推定量であるＦＰｌは、数式（３１）の誤り推定関数を用いて以下のように定義できる。
【０１３１】
【数３２】
2008217592.tif 000039
【０１３２】
ＦＮｌに対してＦＰｌは、とりうる全てのセグメントに対して計算を行う。
以下、パラメタ学習部で勾配を求める際の式は以下のようになる。
【０１３３】
【数３３】
2008217592.tif 000040
【０１３４】
以下、それぞれのコンポーネント毎に示す。
まず、目的関数をＦＮｌとＦＰｌで偏微分したものは以下のようになる。
【０１３５】
【数３４】
2008217592.tif 000041
【数３５】
2008217592.tif 000042
【０１３６】
ただし、ＺＮとＺＤはそれぞれ数式（２８）の分子と分母の値を示す。
次に、ＦＮｌとＦＰｌとを平滑化関数lで偏微分したものは、ＦＮｌとＦＰｌとがlの単なる線形和で表されるため定数となる。
平滑化関数l（ここではシグモイド関数を適用)の偏微分は定義にしたがって、次のようになる。
【０１３７】
【数３６】
2008217592.tif 000043
【０１３８】
最後に、誤り推定関数ｄ（）とｄ’（）のパラメタに対する偏微分を示す。
【０１３９】
【数３７】
2008217592.tif 000044
【数３８】
2008217592.tif 000045
【数３９】
2008217592.tif 000046
【数４０】
2008217592.tif 000047
【０１４０】
以下、評価単位と目的関数の定義、及び目的関数と目的関数の勾配の計算以外の処理は、セグメント正解率を用いて学習する場合と全く同じ処理になるためここでは省略する。
【０１４１】
以上、本発明の実施形態を説明したが、前記の説明において用いた数式等は、例示しものにすぎず、適用する言語モデルに応じて適宜変更可能である。よって、本発明の範囲は、特許請求の範囲に記載された技術的思想により定められる。
【図面の簡単な説明】
【０１４２】
【図１】系列セグメンテーション及び系列ラベリングの例を示す図面である。
【図２】ＩＯＢラベリング法を説明する図面である。
【図３】品詞タグ付けの例を示す図面である。
【図４】カスケードモデルを適用した系列ラベリングの例を示す図面である。
【図５】条件付き確率場を適用した系列ラベリングの例を示す図面である。
【図６】特徴抽出の例を示す図面である。
【図７】条件付き確率場におけるクリークを説明する図面である。
【図８】条件付き確率場におけるクリーク毎の特徴の例を示す図面である。
【図９】平滑化関数の例を示す図面である。
【図１０】従来技術の誤り推定計算方法を説明する図面である。
【図１１】従来技術の問題点を説明する図面である。
【図１２】セグメントの出力確率の例を説明する図面である。
【図１３】出力候補グラフにおける数式（１９）の意味を説明する図面である。
【図１４】テキスト解析装置のブロック構成図である。
【図１５】テキスト解析装置の処理動作の概略を説明する説明図である。
【図１６】学習器の入力・出力例を示す図面である。
【図１７】推定器の入力・出力例を示す図面である。
【図１８】学習器の詳細ブロックを示す図面である。
【図１９】学習器の処理手順を示すフローチャートである。
【図２０】パラメタ学習部の詳細な処理手順を示すフローチャートである。
【図２１】（ａ）は入力される学習データの例を示し、（ｂ）抽出される主力ラベル候補集合を示し、（ｃ）は生成される出力候補グラフの例を示す図面である。
【図２２】出力候補グラフの各ノードに特徴ベクトルを付与した例を示す図面である。
【図２３】学習データの例において、区間［４，５］を評価する場合を説明する図面である。
【符号の説明】
【０１４３】
１１    ＣＰＵ
１２    ＲＡＭ
１３    入手力部
１４    ストレージ
１４１  学習器
１４４  学習データ
１４５  パラメタベクトル
１４１１  出力候補グラフ生成部
１４１２  特徴抽出部
１４１３  パラメタ学習部
【図１】
2008217592.tif 000050
【図２】
2008217592.tif 000051
【図３】
2008217592.tif 000052
【図４】
2008217592.tif 000053
【図５】
2008217592.tif 000054
【図６】
2008217592.tif 000055
【図７】
2008217592.tif 000056
【図８】
2008217592.tif 000057
【図９】
2008217592.tif 000058
【図１０】
2008217592.tif 000059
【図１１】
2008217592.tif 000060
【図１２】
2008217592.tif 000061
【図１３】
2008217592.tif 000062
【図１４】
2008217592.tif 000063
【図１５】
2008217592.tif 000064
【図１６】
2008217592.tif 000065
【図１７】
2008217592.tif 000066
【図１８】
2008217592.tif 000067
【図１９】
2008217592.tif 000068
【図２０】
2008217592.tif 000069
【図２１】
2008217592.tif 000070
【図２２】
2008217592.tif 000071
【図２３】
2008217592.tif 000072
【手続補正書】
【提出日】平成20年5月16日(2008.5.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
テキストデータに所定の分類タグを付与するために使用するパラメタベクトルを、予め前記分類タグが付与されたテキストデータである学習データから算出する言語解析モデル学習装置であって、
前記学習データに前記分類タグの種類を示す出力ラベル候補を対応付けた出力候補グラフと、前記パラメタベクトルの初期値とを記憶した記憶部と、
前記学習データの一つ以上の記号の連続から成る部分記号列であるセグメントを評価単位とするセグメント単位の出現確率を、前記パラメタベクトルを変数として、対象セグメントの前側確率及び後側確率である当該セグメント間の周辺確率により表す決定関数を用いて、前記学習データの正解の要素の出現確率と、前記正解の要素以外で最も出力されやすい要素の出現確率との差分を誤り推定関数として計算し、前記誤り推定関数を用いて設定される目的関数を最適化するパラメタベクトルを算出するパラメタ学習部とを備える
ことを特徴とする言語解析モデル学習装置。
【請求項２】
前記目的関数は、すべての最小評価単位についての前記誤り推定関数の出力の総和であり、前記目的関数を最適化するパラメタベクトルは、前記目的関数の出力を最小にする前記パラメタベクトルである
ことを特徴とする請求項１に記載の言語解析モデル学習装置。
【請求項３】
前記パラメタ学習部は、
前記出力候補グラフにおいて、出力系列ｙ中の位置ｉから位置ｊまでの間のセグメントの部分出力系列ｙ［ｉ，ｊ］の前記前側確率αを次の式（１）により計算し、前記後側確率βを次の式（２）により計算し、当該セグメント間の出現確率を前記前側確率と前記後側確率である周辺確率として、前記決定関数ｇを次の式（３）により計算し、同一区間内で正解以外のとり得る全てのセグメントの計算を行い、最大値のセグメントを選出して、これを最尤出力候補セグメントとし、正例の負例への間違い数を推定する場合には前記誤り推定関数ｄを次の式（４）により計算し、負例の正例への間違い数を推定する場合には前記誤り推定関数ｄを次の式（５）により計算し、
前記目的関数は、前記式（４）および式（５）でそれぞれ計算される誤り推定関数を用いて設定される、次の式（６）に示すＦ値の分母であり、前記目的関数を最適化するパラメタベクトルλは、前記目的関数の出力を最小にする前記パラメタベクトルである
ことを特徴とする請求項１に記載の言語解析モデル学習装置。
【数１】
2008217592.tif 000073
ただし、ｘは入力系列、ｆは特徴ベクトル、ｎはセグメント数、ｌは単一のクリーク単位での特徴ベクトルの識別子、ｙiはｉ番目の出力ラベル、ｙjはｊ番目の出力ラベル、Ｙは単一のラベルのとりうる全てのラベル集合、ｙ*は正解セグメント、ＢはＩＯＢラべリング法の開始セグメントをそれぞれ示す。また、γは再現率と適合率とのトレードオフの度合いを示す定数、Ｍは正例セグメント数、ＦＰｌは負例の正例への間違い数の推定量、ＦＮｌは正例の負例への間違い数の推定量をそれぞれ示す。
【請求項４】
前記パラメタ学習部は、
前記決定関数を用いて前記学習データの正解の要素の出現確率と、前記正解の要素以外で最も出力されやすい要素の出現確率とを計算する際に、
Forward-Backwardアルゴリズムを用いて前記決定関数の出力として前記各要素の出現確率を計算する
ことを特徴とする請求項１ないし請求項３のいずれか１項に記載の言語解析モデル学習装置。
【請求項５】
前記パラメタ学習部は、
前記パラメタベクトルの初期値の入力を受け付け、
前記パラメタベクトルの初期値からその時点で前記目的関数を最適化するパラメタベクトルを算出後に、前記目的関数の勾配を計算し、前記勾配が所定値以下になるまで、その時点のパラメタベクトルを用いて、前記目的関数を最適化するパラメタベクトルを再度算出し、
前記勾配が所定値以下になった場合に、その時点のパラメタベクトルを、前記目的関数を最適化するパラメタベクトルとして出力する
ことを特徴とする請求項１ないし請求項４のいずれか１項に記載の言語解析モデル学習装置。
【請求項６】
予め所定の分類タグが付与されたテキストデータである学習データに前記分類タグの種類を示す出力ラベル候補を対応付けた出力候補グラフと、テキストデータに前記分類タグを付与するために使用するパラメタベクトルの初期値とが記憶された記憶部と、パラメタ学習部とを有する言語解析モデル学習装置において、前記学習データおよび前記パラメタベクトルの初期値から最適なパラメタベクトルを算出する言語解析モデル学習方法であって、
前記言語解析モデル学習装置のパラメタ学習部は、
前記学習データの一つ以上の記号の連続から成る部分記号列であるセグメントを評価単位とするセグメント単位の出現確率を、前記パラメタベクトルを変数として、対象セグメントの前側確率及び後側確率である当該セグメント間の周辺確率により表す決定関数を用いて、前記学習データの正解の要素の出現確率を計算するステップと、
前記決定関数を用いて、前記正解の要素以外で最も出力されやすい要素の出現確率を計算するステップと、
前記正解の要素の出現確率と、前記正解の要素以外で最も出力されやすい要素の出現確率との差分を誤り推定関数として計算するステップと、
前記誤り推定関数を用いて設定される目的関数を最適化するパラメタベクトルを算出するステップと、を実行する
ことを特徴とする言語解析モデル学習方法。
【請求項７】
前記目的関数は、すべての最小評価単位についての前記誤り推定関数の出力の総和であり、前記目的関数を最適化するパラメタベクトルは、前記目的関数の出力を最小にする前記パラメタベクトルである
ことを特徴とする請求項６に記載の言語解析モデル学習方法。
【請求項８】
前記パラメタ学習部は、
前記出力候補グラフにおいて、出力系列ｙ中の位置ｉから位置ｊまでの間のセグメントの部分出力系列ｙ［ｉ，ｊ］の前記前側確率αを次の式（１）により計算するステップと、
前記後側確率βを次の式（２）により計算するステップと、
当該セグメント間の出現確率を前記前側確率と前記後側確率である周辺確率として、前記決定関数ｇを次の式（３）により計算するステップと、
同一区間内で正解以外のとり得る全てのセグメントの計算を行い、最大値のセグメントを選出して、これを最尤出力候補セグメントとするステップと、
正例の負例への間違い数を推定する場合に前記誤り推定関数ｄを次の式（４）により計算するステップと、
負例の正例への間違い数を推定する場合に前記誤り推定関数ｄを次の式（５）により計算するステップと、を実行し、
前記目的関数は、前記式（４）および式（５）でそれぞれ計算される誤り推定関数を用いて設定される、次の式（６）に示すＦ値の分母であり、前記目的関数を最適化するパラメタベクトルλは、前記目的関数の出力を最小にする前記パラメタベクトルである
ことを特徴とする請求項６に記載の言語解析モデル学習方法。
【数１】
2008217592.tif 000074
ただし、ｘは入力系列、ｆは特徴ベクトル、ｎはセグメント数、ｌは単一のクリーク単位での特徴ベクトルの識別子、ｙiはｉ番目の出力ラベル、ｙjはｊ番目の出力ラベル、Ｙは単一のラベルのとりうる全てのラベル集合、ｙ*は正解セグメント、ＢはＩＯＢラべリング法の開始セグメントをそれぞれ示す。また、γは再現率と適合率とのトレードオフの度合いを示す定数、Ｍは正例セグメント数、ＦＰｌは負例の正例への間違い数の推定量、ＦＮｌは正例の負例への間違い数の推定量をそれぞれ示す。
【請求項９】
前記パラメタ学習部は、
前記決定関数を用いて前記学習データの正解の要素の出現確率を計算するステップおよび、前記決定関数を用いて前記正解の要素以外で最も出力されやすい要素の出現確率を計算するステップにおいて、
Forward-Backwardアルゴリズムを用いて前記決定関数の出力として前記各要素の出現確率を計算する
ことを特徴とする請求項６ないし請求項８のいずれか１項に記載の言語解析モデル学習方法。
【請求項１０】
前記パラメタ学習部は、
前記パラメタベクトルの初期値の入力を受け付けるステップと、
前記パラメタベクトルの初期値からその時点で前記目的関数を最適化するパラメタベクトルを算出後に、前記目的関数の勾配を計算するステップと、
前記勾配が所定値以下になるまで、その時点のパラメタベクトルを用いて、前記目的関数を最適化するパラメタベクトルを再度算出するステップと、
前記勾配が所定値以下になった場合に、その時点のパラメタベクトルを、前記目的関数を最適化するパラメタベクトルとして出力するステップと、を実行する
ことを特徴とする請求項６ないし請求項９のいずれか１項に記載の言語解析モデル学習方法。
【請求項１１】
請求項１ないし請求項５のいずれか１項に記載の言語解析モデル学習装置を構成する各部として、コンピュータを機能させるための言語解析モデル学習プログラム。
【請求項１２】
請求項１１に記載の言語解析モデル学習プログラムを記録した
ことを特徴とする記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００６８
【補正方法】変更
【補正の内容】
【００６８】
【数１７】
2008217592.tif 000075
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００７０
【補正方法】変更
【補正の内容】
【００７０】
【数１８】
2008217592.tif 000076