縮約素性生成装置、方法、プログラム、モデル構築装置及び方法
【課題】一般的な教師あり学習に用いられる素性よりも、コンパクトかつ高精度の縮約素性を生成する。
【解決手段】原素性重要度計算部141で、ベースモデル構築部12により正解データから学習して構築されたベースモデル22と未解析データ24とを用いて、未解析データ24の入力に対するベースモデル22の最尤出力に対して、未解析データから抽出された原素性各々が与える影響を示す重要度を、複数の原素性各々について計算する。原素性選択部142で、重要度が0の原素性を排除して、残りの原素性を選択する。原素性融合部143で、選択した原素性集合から、同じ重要度となる原素性を一つの縮約素性としてまとめ上げて、縮約素性集合を生成する。原素性重要度追加部144で、原素性の重要度に関する素性を生成して、縮約素性集合に追加する。
【解決手段】原素性重要度計算部141で、ベースモデル構築部12により正解データから学習して構築されたベースモデル22と未解析データ24とを用いて、未解析データ24の入力に対するベースモデル22の最尤出力に対して、未解析データから抽出された原素性各々が与える影響を示す重要度を、複数の原素性各々について計算する。原素性選択部142で、重要度が0の原素性を排除して、残りの原素性を選択する。原素性融合部143で、選択した原素性集合から、同じ重要度となる原素性を一つの縮約素性としてまとめ上げて、縮約素性集合を生成する。原素性重要度追加部144で、原素性の重要度に関する素性を生成して、縮約素性集合に追加する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、縮約素性生成装置、方法、プログラム、モデル構築装置及び方法に係り、特に、教師あり学習に用いるための縮約素性集合を生成するための縮約素性生成装置、方法、及びプログラム、並びに、生成された縮約素性集合を用いてモデルを構築するモデル構築装置及び方法に関する。
【背景技術】
【0002】
自然言語処理やバイオインフォマティクスの研究分野の分類問題に属する問題は、近年では、正解データから統計的な機械学習を行う手法である教師あり学習により、分類器のモデルを構築する方法が主流であり、多くの研究で良い精度が得られることが知られている。教師あり学習を行う際には、図16に示すように、対象とする問題に有用と思われる判別規則、または、判別規則を構成する要素と雛形とを人手で事前に定義する方法が一般的である。ここで定義される判別規則を一般的に「素性」と呼ぶ。正解データを用いた学習により構築されたモデルを用いることで、図17に示すように、正解が分かっていないデータ(未解析データ)を解析し、解析結果を得ることができる。なお、図16及び17中の矢印は、定義の依存関係を示す。
【0003】
素性は、入力されるデータに対して解きたい問題を特徴付けるものであり、人間の持つ知識や直感等に基づいて定義される場合が多い。自然言語処理の問題では、単語や単語の連接等が素性として用いられることが多い。これは、文書を構成する要素が単語であること、及び、それぞれの単語が問題を説明する主要な要因となることが多いためである。また、意味や高次の情報を外部のリソース(例えば辞書)等を参照して利用することも行われている。この素性の設計により、教師あり学習によるモデル学習の精度が大きく影響を受ける。
【0004】
一般論として、機械学習を行う際に素性数が多いと学習データに過適応してしまい相対的に汎化性能が悪くなる。この問題は、「次元の呪い」といわれる良く知られた問題として説明できる。つまり、機械学習では、素性数がそのまま素性空間の次元数に相当することから、素性を一つ増やす毎に、十分な汎化性能を得るために必要なデータ量は指数関数的に増大し、現実的にデータ量を準備することが不可能となる、という問題である。
【0005】
ただし、自然言語処理やバイオインフォマティクスの問題を対象とする場合には、解きたい問題をうまく特徴付けるものは、テキスト中の単語であるとか、遺伝子配列の記号系列などといった離散シンボルである。また、解きたい問題に対して、個々の離散シンボルにより説明できる問題の事象の範囲はごく少数のデータに対してのみである場合がほとんどである。それ故に、解きたい問題全体をうまく説明するのに必要な素性数は、非常に多くなることが一般的である。さらに、同一のシンボルであっても状況によって多くの例外が発生する場合が多いため、複数のシンボルの組み合わせなどを考慮して対応する必要が生じる。このような状況では、結果的に、多くの離散シンボルまたはその組み合わせによる素性の集合を用いて問題を特徴付けることが必然となる。すると、個々の素性がデータ上に出現する割合は非常に小さくなる傾向となり、データx素性の行列を考えた場合、要素の多くが0となる疎行列となる。要素が0とは、情報が無いことと等価であり、各素性が出現する割合が大きく密行列となる場合と比較して、「次元の呪い」問題が示すように、より多くのデータを必要とすることを意味する。このように、自然言語処理やバイオインフォマティクスの問題では、そもそも「次元の呪い」問題が頻出しやすい問題設定となっているという背景がある。
【0006】
理論的には、「次元の呪い」問題は、学習データが無限に存在すれば回避できると考えられる。しかし、正解データを用いた教師あり学習の枠組みでは、正解データは人手で作成するのが最も一般的であるため、作成コストが高く、高次元素性空間を統計的に十分満たす量を作成するのは非常に困難である。そのため、正解データ量を増やしてこの問題に対処するという方案は、現実的ではない。結果的に、教師あり学習の枠組みでは、限定された正解データ量で学習すると、十分な汎化性能が得られない可能性がある。
【0007】
このように、素性設計の観点では、多くの素性を利用する方が解きたい問題をうまく表現できるため適していると考えられるが、機械学習の観点では、素性数は極力少なくするべきであるというジレンマがある。
【0008】
このような問題を解決するための方法として、例えば、素性空間の次元圧縮や次元削減等と呼ばれる、高次元素性空間を低次元空間に写像する方法が提案されている(例えば、非特許文献1参照)。同様に、任意のクラスタリング法等を用いて素性をクラスタリングして新たな素性とする方法も提案されている(例えば、非特許文献2参照)。
【先行技術文献】
【非特許文献】
【0009】
【非特許文献1】Joseph Turian, Lev-Arie Ratinov, and Yoshua Bengio. 2010. Word representations: A simple and general method for semi-supervised learning. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 384−394.
【非特許文献2】Terry Koo, Xavier Carreras, and Michael Collins. 2008. Simple Semi-supervised Dependency Parsing. In Proceedings of ACL-08: HLT, pages 595−603.
【発明の概要】
【発明が解決しようとする課題】
【0010】
しかしながら、非特許文献1及び2の方法は、特定の問題では効果を発揮する場合も考えられるが、実際に現在これらの方法が、ほとんど用いられていないことを考慮すると、一般的にはそれほど効果は期待できない。また、自然言語処理やバイオインフォマティクスの問題では、前述のようにデータx素性の行列が疎行列になるという観点から、行列分解による方法や、最近傍法に基づくクラスタリング法等は、効果が得られないことが一般的に知られている。つまり、高次元かつ疎な素性空間であるが故に、統計や機械学習の観点でうまく素性を縮約することが困難であり、また、精度向上という効果を得ることが困難である、という問題がある。これは、非特許文献1及び2のような方法の枠組みは、素性数を削減して、全素性を用いる場合と同等の精度を達成するためのものだからである。
【0011】
前述のクラスタリングや素性の次元削減法以外にも、素性選択という観点で様々な取り組みがなされている。ただし、これらの方法は、本来不要な素性をうまく選択して削除することにより、素性集合を縮小することを目的としている。つまり、仮に、不要な素性が存在しなければ、素性の削減には結びつかない方法と言える。これら素性選択の技術も、基本的には、素性数を減らして元と同じ精度を達成することを目的としているため、精度を向上させることは困難な枠組みである、という問題がある。
【0012】
本発明は、上記問題を解決するためになされたもので、一般的な教師あり学習に用いられる素性よりも、コンパクトかつ高精度の縮約素性を生成することができる縮約素性生成装置、方法、及びプログラムを提供することを目的とする。また、学習時の過適合を低減することができるモデル構築装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【0013】
上記目的を達成するために、第1の発明の縮約素性生成装置は、入力に対する正解が既知の正解データから学習して構築されたベースモデルに、入力に対する正解が未知の複数の未解析データを入力した際の該ベースモデルの最尤出力に対して、前記複数の未解析データから抽出された該未解決データの特徴を表す複数の原素性各々が与える影響を示す重要度を、前記複数の原素性各々について計算する計算手段と、前記計算手段により計算された複数の原素性各々の重要度に基づいて、前記複数の未解析データから抽出された複数の原素性から、前記ベースモデルの最尤出力に対して影響を与える原素性を選択する選択手段と、前記原素性各々の重要度に基づいて、前記選択手段により選択された原素性の集合から、1つ以上の原素性をまとめた縮約素性の集合を生成する生成手段と、を含んで構成されている。
【0014】
第1の発明の縮約素性生成装置は、計算手段が、入力に対する正解が既知の正解データから学習して構築されたベースモデルに、入力に対する正解が未知の複数の未解析データを入力した際の該ベースモデルの最尤出力に対して、複数の未解析データから抽出された該未解決データの特徴を表す複数の原素性各々が与える影響を示す重要度を、複数の原素性各々について計算する。そして、選択手段が、計算手段により計算された複数の原素性各々の重要度に基づいて、複数の未解析データから抽出された複数の原素性から、ベースモデルの最尤出力に対して影響を与える原素性を選択し、生成手段が、原素性各々の重要度に基づいて、選択手段により選択された原素性の集合から、1つ以上の原素性をまとめた縮約素性の集合を生成する。
【0015】
このように、原素性がベースモデルの最尤出力に与える影響を示す重要度を原素性毎に計算し、この重要度に基づいて選択された原素性から縮約素性を生成するため、コンパクトかつ精度良く縮約された縮約素性を生成することができる。
【0016】
また、前記計算手段は、前記複数の未解析データを複数の部分集合に分割し、分割した複数の部分集合毎に前記重要度を計算するためのパラメータを算出し、該部分集合各々から抽出された複数の原素性各々と前記パラメータとのペアを生成し、前記ペアに基づいて、前記原素性毎に前記パラメータの値を集計して求めて、前記重要度を計算することができる。これにより、未解決データの量が多い場合でも、効率的に重要度を計算することができる。
【0017】
また、前記生成手段は、前記縮約素性各々に含まれる原素性の重要度に関する素性を生成し、前記縮約素性の集合に追加することができる。原素性自体のみならず、原素性の重要度に関する情報も非常に有用な情報であるため、縮約素性の集合に追加することで、縮約素性の集合の精度がより向上する。
【0018】
また、第2の発明のモデル構築装置は、第1の発明の縮約素性生成装置と、前記正解データから学習して前記ベースモデルを構築する構築手段と、前記縮約素性生成装置により生成された縮約素性の集合から学習して最終モデルを再構築する再構築手段と、を含んで構成されている。このように、コンパクトかつ高精度に生成された縮約素性を用いて最終モデルを再構築することにより、学習時の過適合を低減することができる。
【0019】
また、第3の発明の縮約素性生成方法は、計算手段と、選択手段と、生成手段とを含む縮約素性生成装置における縮約素性生成方法であって、前記計算手段は、入力に対する正解が既知の正解データから学習して構築されたベースモデルに、入力に対する正解が未知の複数の未解析データを入力した際の該ベースモデルの最尤出力に対して、前記複数の未解析データから抽出された該未解決データの特徴を表す複数の原素性各々が与える影響を示す重要度を、前記複数の原素性各々について計算し、前記選択手段は、前記計算手段により計算された複数の原素性各々の重要度に基づいて、前記複数の未解析データから抽出された複数の原素性から、前記ベースモデルの最尤出力に対して影響を与える原素性を選択し、前記生成手段は、前記原素性各々の重要度に基づいて、前記選択手段により選択された原素性の集合から、1つ以上の原素性をまとめた縮約素性の集合を生成する方法である。
【0020】
また、第4の発明のモデル構築方法は、第1の発明の縮約素性生成装置と、構築手段と、再構築手段とを含むモデル構築装置におけるモデル構築方法であって、前記構築手段は、入力に対する正解が既知の正解データから学習してベースモデルを構築し、前記縮約素性生成装置は、前記縮約素性の集合を生成し、前記再構築手段は、前記縮約素性生成装置により生成された縮約素性の集合から学習して最終モデルを再構築する方法である。
【0021】
また、第5の発明の縮約素性生成プログラムは、コンピュータを、第1の発明の縮約素性生成装置を構成する各手段として機能させるためのプログラムである。
【発明の効果】
【0022】
以上説明したように、本発明の縮約素性生成装置、方法、及びプログラムによれば、原素性がベースモデルの最尤出力に与える影響を示す重要度を原素性毎に計算し、この重要度に基づいて選択された原素性から縮約素性を生成するため、一般的な教師あり学習に用いられる素性よりも、コンパクトかつ高精度の縮約素性を生成することができる、という効果が得られる。
【0023】
また、本発明のモデル構築装置及び方法によれば、コンパクトかつ高精度に生成された縮約素性を用いて最終モデルを再構築することにより、学習時の過適合を低減することができる、という効果が得られる。
【図面の簡単な説明】
【0024】
【図1】(a)一般的なモデルを示す概念図、及び(b)本実施の形態の概要を示す概念図である。
【図2】原素性集合と縮約素性集合との関係を示すイメージ図である。
【図3】本実施の形態のモデル構築装置の機能的構成を示すブロック図である。
【図4】縮約素性関数集合生成部の機能的構成を示すブロック図である。
【図5】原素性重要度計算部の機能的構成を示すブロック図である。
【図6】本実施の形態のモデル構築装置におけるモデル構築処理ルーチンの内容を示すフローチャートである。
【図7】本実施の形態のモデル構築装置の縮約素性関数集合生成部における縮約素性関数集合生成処理ルーチンの内容を示すフローチャートである。
【図8】縮約素性関数集合生成処理を示す概念図である。
【図9】MapReduceによる原素性の重要度の計算処理を説明するための図である。
【図10】本実施の形態のモデル構築装置を固有表現抽出に適用した場合の効果を示す図である。
【図11】本実施の形態のモデル構築装置を係り受け解析に適用した場合の効果を示す図である。
【図12】文書分類問題への適用例の概要を示す図である。
【図13】固有表現抽出問題への適用例の概要を示す図である。
【図14】文書分類問題へ本発明を適用した実施例の参考例として、原素性関数を用いた場合の処理を示す概略図である。
【図15】文書分類問題へ本発明を適用した実施例の処理を示す概略図である。
【図16】従来の教師あり学習でのモデル構築の概要を示す概念図である。
【図17】従来の教師あり学習で構築されたモデルを用いた未解析データの解析の概要を示す概念図である。
【発明を実施するための形態】
【0025】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
<概要>
まず、本実施の形態の概要について説明する。
【0026】
ここでは、正解の解析結果が付与されていないデータを、正解の解析結果が付与されている正解データと対比した呼び方で、未解析データと呼ぶ。本実施の形態は、大規模な未解析データを利用することを前提とした技術である。
【0027】
自然言語処理やバイオインフォマティクスといった分野の問題では、大規模な未解析データを比較的容易に獲得することができる。例えば、自然言語処理の場合は、近年では、電子化された文書をweb等から容易に獲得することができる。
【0028】
本実施の形態の概要としては、まず、大規模未解析データ上で各素性の重要度を計算する。これは、素性の重要度を計算するという観点では、解きたい問題の正解は不要であるため、限定された量の正解データではなく、比較的容易に獲得可能な大規模な未解析データを用いることで、「次元の呪い」の影響が軽減された状態で統計量(重要度)を推定できる。次に、大規模なデータから得られた比較的信頼性の高い統計量(重要度)を用いて素性空間を再構築する。具体的には、重要度に基づいて素性のクラスタリング及び削除を行い、更に、重要度の値自身を素性の値として活用する。このように再構築された素性空間は、大規模なデータから導出されているため、解きたい問題全体をコンパクトにかつ精度良く表現できている可能性が高い。最後に、再構築した素性空間を使って、通常の正解データを使った教師あり学習によりモデルを学習する。これにより、図1(a)に示す従来のモデルよりもコンパクトなモデル(同図(b))を構築することができる。
<本実施の形態の原理>
次に、本実施の形態の原理について説明する。
【0029】
まず、以下の説明で用いる記号について、下記のように定義する。
【0030】
X:可能な全ての入力の集合
Y:可能な全ての出力の集合
x:任意の一つの入力、つまり、x∈Xの関係が成り立つ。
【0031】
y:任意の一つの出力、つまり、y∈Yの関係が成り立つ。
【0032】
Y(x):ある一つのxが与えられた際に得られる可能性のある出力の集合、ただし、Y(x)⊆Yの関係が成り立つ。
【0033】
fn(x、y):学習用素性定義で定義されたn番目の原素性関数。戻り値は実数(スカラー)である。
【0034】
N:学習用素性定義で定義された原素性または原素性関数の総数
wn:n番目のパラメータ。線形モデルの場合には基本的にn番目の素性関数に対する重みに相当する。よってn∈{1,・・・,N}である。
【0035】
hn(x、y):m番目の縮約素性関数。戻り値は実数(スカラー)である。
【0036】
hm(x、y)=Σfn∈Smfn(x、y)
M:生成される縮約素性または縮約素性関数の総数
なお、本実施の形態では、大規模な未解析データ上で各素性の重要度を計算し、重要度に基づいて素性のクラスタリング及び削除を行うことにより、解きたい問題全体をコンパクトにかつ精度良く表現できる素性空間を再構築する。この再構築された素性空間を構成する素性を縮約素性と呼ぶ。
【0037】
ここで、本実施の形態で用いる縮約素性を以下のように定義する。まず、説明を簡単にするため、従来一般的に教師あり学習で用いる素性を、原素性と呼ぶ。学習に利用する際には、複数の素性を利用することから、学習に利用する全ての縮約素性をまとめて縮約素性集合と呼び、また、学習に利用する全ての原素性をまとめて原素性集合と呼ぶ。このとき、縮約素性とは、「原素性集合内の一つ以上の原素性で構成される素性」とする。
【0038】
形式的には以下のような定義となる。縮約素性集合をH、原素性集合をFとする。また、縮約素性集合内の素性数をM、原素性集合内の素性数をNとする。この時、定義からM≦Nが成り立ち、多くの場合M≪Nとなるように構成する。
【0039】
次に、縮約素性集合内の任意の一つの縮約素性hm∈Hは、原素性集合F内の一つ以上の集合で構成されるとする。つまり、hm=Sm、ただし、Sm⊆Fの関係が成り立つ。
【0040】
ここで、原素性集合内の任意の一つの原素性fn∈Fは、高々一つの縮約素性hmの構成要素にしかならないと仮定する。この仮定は、任意の二つの縮約素性の構成要素に同じ原素性が存在することは決してない事を保証し、かつ、いくつかの原素性はどの縮約素性の構成要素にもならない場合があることを意味している。つまり、任意のmとm’、ただし、m≠m’の時に、Sm∩Sm’=O(空集合)、及び∪m=1MSm⊆Fが成り立つことを意味する。図2に原素性と縮約素性との関係を示す。
【0041】
次に、縮約素性を利用して生成される縮約素性関数を定義する。一般的に素性関数とは、定義した素性に基づいて定義される関数であり、入力xと出力yとにより値が決定する関数である。素性関数は、一般的にf(x,y)のような形で表される。この素性関数f(x,y)の戻り値はスカラー(実数)である。
【0042】
ここで、原素性に従って定義される素性関数を原素性関数と呼ぶ。また、入力xと出力yとにより値が決定するn番目の原素性に対する原素性関数をfn(x,y)とする。fn(x,y)は、入力xと出力yとが与えられたとき、n番目の原素性の値(または、n番目の原素性が成立するか否かを表す値)を返す関数である。ただし、原素性は全部でN 個であるので、n∈{1,・・・,N}である。同様に、入力xと出力yとにより値が決定するm番目の縮約素性に対する縮約素性関数をhm(x,y)とする。ただし、縮約素性は全部でM個であるので、m∈{1,・・・,M}である。このとき、縮約素性関数の戻り値は、対象となる縮約素性の構成要素となった全ての原素性関数の戻り値の総和と定義する。従って、縮約素性関数hm(x,y)は、下記(1)式で表すことができる。
【0043】
【数1】
【0044】
このことから、縮約素性関数の値は、原素性関数の値に従って自動的に定義されることを意味し、縮約素性関数用に新たに計算式を定義する必要はないことを意味する。
【0045】
次に、ベースモデルについて定義する。本実施の形態では、学習に用いるモデルは(対数)線形モデルであると仮定する。線形モデルの判別関数g(入力xに対する出力yの尤もらしさを返す関数)は、下記(2)式で定義することができる。
【0046】
【数2】
【0047】
ここで、wnはn番目の原素性関数fn(x,y)に対するモデルパラメータ(重み)である。つまり、線形モデルでは、入力xが与えられた場合に、出力yの尤もらしさは、全ての原素性関数fn(x,y)の重み付き和によって評価されることを意味している。
【0048】
また、入力xが与えられた際の最尤出力^yを決定する方法は、判別関数gを用いて、下記(3)式で表される最大化問題を解くことに帰着する。
【0049】
【数3】
【0050】
線形モデルは、分類問題等で用いられる最も簡潔なモデルである一方、多くの実問題で十分な精度が得られることが多く、多くの場面で利用されているモデルである。また、計算が単純な加算及び乗算で行えることから、速度面でも複雑なモデルに対して優位性がある場合が多い。
【0051】
本実施の形態では、ある縮約素性関数を自動的に生成するために、後述する原素性の重要度を計算する。この原素性の重要度の計算に際して、事前に通常の教師あり学習により構築されたモデルを利用する。このモデルを、ここではベースモデルと呼ぶ。ここで述べたように、ベースモデルも(対数)線形モデルであると仮定する。
【0052】
次に、本実施の形態において、ある縮約素性関数を自動構築する際に計算する原素性の重要度の定義を述べる。
【0053】
まず、関数r(x,y)を定義する。ある入力xが与えられたときのベースモデルによる最尤出力を^yとする。このとき、関数r(x,y)は、与られたyがベースモデルによる最尤出力^yと同じ場合、つまり、y=^yの場合には1を返し、それ以外の場合には−1を返す関数とする。つまり、関数r(x,y)は、ベースモデルに従って戻り値が決定される関数である。
【0054】
次に、−r(x)を、関数r(x,y)のxにおける平均とする(下記(4)式)。
【0055】
【数4】
【0056】
また、rd(x,y)を、平均−r(x)からの実際の値r(x,y)の偏りを表すとする(下記(5)式)。
【0057】
【数5】
【0058】
次に、下記(6)式及び(7)式に示すように、VD+(fn)及びVD−(fn)を定義する。
【0059】
【数6】
【0060】
また、Dを未解析データの集合とする。このとき、各原素性関数fnの重要度を下記(9)式で定義する。
【0061】
【数7】
【0062】
ここで、VD+(fn)は、ある入力xが与えられた際にベースモデルが選択した最尤出力^yに対し原素性関数fn(x,y)の値がどの程度貢献しているかを未解析データD 内の全ての入力データで評価した値を意味する。同様に、VD−(fn)はベースモデルが選択しなかった出力に対して原素性関数fn(x,y)の値がどの程度貢献しているかを未解析データD内の全ての入力データで評価した値を意味する。つまり、原素性重要度VD(fn)の意味は、以下のように解釈できる。|VD(fn)|が相対的に大きい値の場合には、原素性関数fn(x,y)は、ベースモデルの最尤出力の決定の際に大きな影響を与えているとみなすことができる。よって、原素性fnは、重要な素性であると推定できる。逆に、|VD(fn)|が相対的に小さい値の場合には、原素性関数fn(x,y)は、ベースモデルが最尤出力を決定する際にほとんど影響を与えないとみなすことができる。よって、原素性fnは、ほぼ意味のない素性であると推定できる。このような視点から、VD(fn)は原素性の重要度を表現していると言える。
【0063】
次に、精度の良い縮約素性を生成するために、原素性重要度を計算する際に、信頼性の低い値の正則化、及び、重要度の離散化という二つの要素を取り入れる。
【0064】
まず一つ目の正則化に関しては、下記(10)式に示すように、VD(fn)をVD'(fn)に変更することで実施する。
【0065】
【数8】
【0066】
ここで、Cは正の実数であり、正則化パラメータとする。この時の注意点として、VD(fn)=VD+(fn)−VD−(fn)=Rn/Fnが成り立つ点である。つまり、VD(fn)との違いは、単にCを導入しただけであり、C=0のときVD(fn)=VD’(fn) となる。正則化パラメータにより、Rnが小さいときには大きく値が0方向に圧縮される操作となる。特に、|Rn|≦Cの時、VD’(fn)=0となる。
【0067】
次に、原素性重要度の離散化について述べる。まず、下記(12)式に示す補助関数を定義する。
【0068】
【数9】
【0069】
次に、整数空間をN(N={・・・,−2,−1,0,1,2,・・・}を考える。また、δを正の実数とし、整数空間Nに対して、各整数をスケーリングする値として導入する。ここでは、離散空間N/δを、整数空間の各整数をδによってスケーリングした離散空間として定義する。つまり、N/δ={・・・,−2/δ,−1/δ,0,1/δ,2/δ,・・・}である。このとき、実数値VD’(fn)の離散空間N/δ内で最も近い上限及び下限の値を、下記(14)式に示すように定義する。
【0070】
【数10】
【0071】
そして、最終的に下記(15)式を用いて原素性の重要度を離散化する。
【0072】
【数11】
【0073】
つまり、最終的にun*がn番目の原素性の重要度の値となる。
【0074】
なお、本実施の形態の原素性重要度計算は、下記(16)式に示す最適化問題を解くことと等価である。
【0075】
【数12】
【0076】
ここで、nは、(16)式に対するunの最適解を表す。また、u*={un*}n=1Nとする。
【0077】
この式から、解空間がN/δで定義される離散空間であるという条件下で、各素性毎に、未解析データD上でのrdとunとの間の最小二乗誤差を最小化する問題と解釈できる。
【0078】
ここで、制約である各パラメータの制約であるun∈N/δを考えない場合は、(16)式 は、凸最適化問題となる。凸最適化問題では、勾配が0になる点が大域的最適解となることが保証される。ここでは、下記(17)式に示す最小化したい目的関数に対して、un の偏微分は下記(18)式となる。
【0079】
【数13】
【0080】
ここで、∂U(u|D)/∂un=0とおけば、VD’(fn)が解となることがわかる。また、離散化制約を満たす解は、(10)式により得られる。つまり(16)式の解は、(15)式により得ることができる。
<システム構成>
次に、本発明の縮約組成生成装置を適用したモデル構築装置を例にして、本実施の形態を説明する。
【0081】
本実施の形態のモデル構築装置10は、CPU(Central Processing Unit)と、RAM(Random Access Memory)と、後述する縮約組成関数集合生成処理ルーチンを含むモデル構築処理ルーチンを実行するためのプログラムを記憶したROM(Read Only Memory)とを備えたコンピュータで構成されている。
【0082】
このコンピュータは、機能的には、図3に示すように、ベースモデル構築部12と、縮約素性関数集合生成部14と、モデル再構築部16とを含んだ構成で表すことができる。
【0083】
ベースモデル構築部12は、正解データ20を入力として、周知の教師あり学習により対象とする問題のベースモデル22を構築(学習)する。ここで、入力される正解データ20は、対象とする問題に応じて人手により定義した「モデル定義」及び「原素性関数集合定義」である。
【0084】
具体的には、ベースモデル構築部12は、従来の教師あり学習によるモデル構築処理を実施する。教師あり学習の方法としては、解きたい問題に合わせて様々な方法を用いることができる。例えば、スパムフィルタのように、スパムかそうでないかという二つのクラスに分類したいような問題では、Support Vector Machine(参考文献:V.Vapnik. The Nature of Statistical Learning Theory. Spring-Verlag, New York, 1995.参照)等の二クラス分類器用の学習法を用いることができる。また、分類したいクラスの種類が二つ以上の場合は、多クラスロジスティック回帰モデル等を用いて教師あり学習が行われる。自然言語処理分野の係り受け解析等では、条件付確率場(参考文献:J. Lafferty, A. McCallum, and F. Pereira. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. In Proc. of ICML-2001, pages 282−289, 2001.)といった構造予測器用のモデルを用いて学習することができる。
【0085】
ベースモデル構築部12により学習されたベースモデル22は、モデル定義及び原素性関数集合定義を含む。
【0086】
縮約素性関数集合生成部14は、大量の未解析データ24と、ベースモデル構築部12の出力であるベースモデル22とを用いて、縮約素性関数集合の定義(縮約素性関数集合定義26)を生成する。この縮約素性関数集合生成部14が、本発明の縮約素性生成装置の一例である。
【0087】
モデル再構築部16は、正解データ20と、縮約素性関数集合生成部14で生成した縮約素性関数集合定義26とを用いて、周知の教師あり学習アルゴリズムを用いた教師あり学習により、対象とする問題のモデルを再構築する。なお、ここで再構築されるモデルを、ベースモデルと区別して、「最終モデル」と呼ぶ。
【0088】
ここで、縮約素性関数集合生成部14で得られる縮約素性関数集合定義26は、原素性関数群定義から無駄を省いた縮約形を自動で生成したものに相当するため、性質としては、原素性関数集合定義と同じとなる。よってモデル再構築部16の処理は、本質的にベースモデル構築部12と同様に、従来の教師あり学習によるモデル構築の処理に相当する。つまり、ベースモデル構築部12及びモデル再構築部16の処理は、従来技術をそのまま用いることができる。
【0089】
すなわち、本実施の形態の主要部は、本発明の縮約素性生成装置を適用した縮約素性関数集合生成部14にある。つまり、縮約素性関数集合生成部14は、教師あり学習で一般的に用いる原素性集合から、教師あり学習に適した縮約素性関数集合定義26を生成する。
【0090】
以下、縮約素性関数集合生成部14について、より具体的に説明する。図4に示すように、縮約素性関数集合生成部14は、原素性重要度計算部141と、原素性選択部142と、原素性融合部143と、原素性重要度追加部144とを含んだ構成で表すことができる。なお、原素性融合部143及び原素性重要度追加部144が、本発明の生成手段の一例である。
【0091】
原素性重要度計算部141は、入力されたベースモデル22に含まれる各原素性関数について、原素性重要度un*を計算する。未解析データ24の量が少ない場合には、各未解析データ24毎に(15)式により、原素性重要度un*を直接計算することができる。ただし、一般的に未解析データ24の量は非常に多くなることから、本実施の形態では、分散並列計算モデルによる効率的な計算方法について説明する。ここでは、MapReduceモデル(参考文献:J. Dean and S. Ghemawat. 2008. MapReduce: Simplified Data Processing on Large Clusters. Commun. ACM, 51(1):107−113.)を応用した計算方法を示す。
【0092】
原素性重要度計算部141は、図5に示すように、未解析データ分割部141aと、Key−valueペア生成部141b−1〜Pと、Key−valueペア集計部141c−1〜Rと、原素性重要度出力部141dとを含んだ構成で表すことができる。なお、Key−valueペア生成部141b−1〜Pの各々、及びKey−valueペア集計部141c−1〜Rの各々をそれぞれ区別することなく説明する場合には、単に、Key−valueペア生成部141b、及びKey−valueペア集計部141cと表記する。
【0093】
未解析データ分割部141aは、未解析データ24をP個の部分集合に分割し、分割した未解析データ24の部分集合を、P個のKey−valueペア生成部141b−1〜Pへそれぞれ出力する。
【0094】
Key−valueペア生成部141bは、受け取った未解析データ24の部分集合に対し、ベースモデル22を用いて、(Tn,Rn,Fn)を計算する。ここで、Tnは(13)式に示す値であり、(12)式に用いられている原素性重要度を離散化する際に計算する補助関数の値である。また、Rnは(11)式、Fnは(8)式に示す値であり、(10)式で用いられている原素性重要度そのものを計算するための値である。そして、各原素性をkey、各未解析データの部分集合により計算された(Tn,Rn,Fn)をvalueとするkey−valueペアの系列を生成し、生成したkey−valueペアの系列を、R個のKey−valueペア集計部141c−1〜Rへ出力する。
【0095】
Key−valueペア集計部141cは、P個のKey−valueペア生成部141bから取得したkey−valueペアを用いて、原素性(key)毎にvalueの値を集計し、原素性毎の(Tn,Rn,Fn)値を求める。そして、(15)式を用いて、原素性fnに対する離散化かつ正則化された原素性重要度un*を計算する。ここで、C及びδの値は、予め設定しておくものとする。
【0096】
原素性重要度出力部141dは、Key−valueペア集計部141cで計算された原素性重要度un*を出力する。
【0097】
原素性選択部142は、原素性重要度計算部141で計算された原素性重要度un*に基づいて、不必要と考えられる原素性を排除する。具体的には、(15)式により重要度を離散化した値un*に対して、un*=0を除いた重要度を離散化した値の集合を出力する。これは、un*=0となった原素性fnを不必要と判定し、原素性の集合から排除することに相当する。原素性選択部142の処理は、原素性の重要度が0ということは、その原素性はモデルの出力決定に影響を与えないであろうと推定されたことを意味するので、これらの素性を縮約素性に含めないための処理である。
【0098】
原素性融合部143は、原素性選択部142で求めた不必要な原素性を排除した原素性の重要度を離散化した値un*の集合を用いて、複数の原素性を一つの縮約素性として融合する。簡単な処理の例として、計算した重要度un*に基づき、同じ重要度となった原素性を一つの縮約素性としてまとめ上げることができる。
【0099】
各un*は離散値であるため、いくつか同じ値である場合が想定される。よって、値の集合の要素数は必ずN以下となる。ここでは、値の集合の要素数をMとする。次に、Sm を、m番目の原素性重要度の値となった原素性fnの集合とする。このとき、m番目の縮約素性関数hm(x,y)を、Sm内の原素性関数fn(x,y)の総和、すなわち、(1)式により計算する。
【0100】
原素性重要度追加部144は、原素性融合部143で求めた縮約素性に素性重要度un*に関する情報を追加する。計算した素性重要度un*の値自体も非常に有効な情報源であるため、縮約素性に利用するものである。ここでは、M+1番目の縮約素性として、下記(20)式で定義される素性φ(x,y)を追加する。
【0101】
ただし、umは、m番目に対応つけられた原素性重要度である。ここでは、原素性融合部143において、原素性重要度が同じ値の原素性を融合して縮約素性としているため、必然的にm番目に対応つけられた原素性重要度は一つの値となる。
【0102】
【数14】
【0103】
これは、全ての縮約素性を重要度の重み付きで総和を取ったものである。よって、縮約素性関数の集合は、{h1(x,y),・・・,hM(x,y),φ(x,y)}となる。
【0104】
ただし、φ(x,y)の計算量は無視できる。φ(x,y)を一つの素性として線形モデルで用いる際には、線形モデルの判別関数g(x,y)は、下記(21)式で計算することができる。
【0105】
【数15】
【0106】
ここで、学習が終わった後には、{wm}m=1M+1は固定した値となるため、wm‘は事前に計算することができる。この結果、(22)式に示すように、φが消えて、hmのみに依存した線形モデルと同じ形式で表現することができる。つまり、φを取り入れても、取り入れなくても、変数の数はMとして計算できるため、φを導入しても計算時間は増大しない。
<モデル構築装置の作用>
次に、本実施の形態に係るモデル構築装置10の作用について説明する。正解データとして、対象とする問題に応じて人手により定義した「モデル定義」及び「原素性関数集合定義」が所定の記憶領域に記憶され、モデル構築装置10において、図6に示すモデル学習処理ルーチンが実行される。
【0107】
ステップ100で、正解データ20を入力として、周知の教師あり学習により対象とする問題のベースモデル22を構築(学習)する。
【0108】
次に、ステップ200で、後述する縮約素性関数集合生成処理ルーチンを実行して、縮約素性関数集合定義26を生成する。
【0109】
次に、ステップ300で、正解データ20と、上記ステップ200で生成した縮約素性関数集合定義26とを用いて、周知の教師あり学習アルゴリズムを用いた教師あり学習により、対象とする問題の最終モデル28を再構築して、処理を終了する。
【0110】
次に、図7及び図8を参照して、縮約素性関数生成処理ルーチンについて説明する。
【0111】
ステップ202で、MapReduceモデルを用いて、入力されたベースモデル22に含まれる各原素性関数について、原素性重要度un*を計算する。
具体的には、図9に示すように、未解析データ24をP個の部分集合に分割し、分割した未解析データ24の部分集合に対し、ベースモデル22を用いて、(13)式、(11)式、及び(8)式により、(Tn,Rn,Fn)を計算する。そして、各原素性をkey、各未解析データの部分集合により計算された(Tn,Rn,Fn)をvalueとするkey−valueペアの系列を生成する。そして、生成したkey−valueペアを用いて、原素性(key)毎にvalueの値を集計し、原素性毎の(Tn,Rn,Fn)値を求め、(15)式を用いて、原素性fnに対する離散化かつ正則化された原素性重要度un*を計算する。
【0112】
次に、ステップ204で、上記ステップ202で計算された原素性重要度un*に基づいて、un*=0となった原素性fnを不必要と判定し、原素性の集合から排除し、un*≠0となった原素性fnを、縮約素性に含める原素性として選択する。
【0113】
次に、ステップ206で、上記ステップ204で選択した原素性の重要度を離散化した値un*の集合を用いて、計算した重要度un*に基づき、同じ重要度となった原素性を一つの縮約素性として融合し、縮約素性の集合のm番目の縮約素性関数hm(x,y)を(1)式により計算する。
【0114】
次に、ステップ208で、上記ステップ206で計算した縮約素性に、(20)式に示す原素性重要度un*に関する素性φ(x,y)を、M+1番目の縮約素性として追加し、縮約素性関数の集合{h1(x,y),・・・,hM(x,y),φ(x,y)}を出力して、リターンする。
【0115】
以上の処理により、原素性の定義から、縮約素性関数の定義が自動的に構築される。縮約素性関数の定義とは、原素性関数の定義からどのようにして縮約素性を構成するかの情報全てを意味し、縮約素性の個数、各縮約素性を構成する原素性集合Smの定義、及び各縮約素性(対応する原素性)の重要度um*となる。
【0116】
以上説明したように、本実施の形態のモデル構築装置によれば、原素性がベースモデルの最尤出力に与える影響に基づいて、原素性毎の重要度を計算し、この重要度に基づいて選択された原素性を融合して縮約素性を生成するため、正解データを用いて教師あり学習する際に一般的に用いる素性集合よりもコンパクトかつ高精度の縮約素性集合を生成することができる。これにより、教師あり学習時に、過適合の起こる可能性を大幅に削減することができる。
【0117】
また、構築するモデルとして線形分類器を用いる場合には、パラメータ数は素性数と一致するため、パラメータ数も大幅に削減することができ、結果として必要な主記憶(メモリ)量も大幅に削減することができる。更に、メモリ量が削減できるということは、実行速度も向上可能である。
【0118】
また、大規模未解析データ上でしか観測されない素性を間接的に利用することが可能となり、汎化性能も大幅に向上させることができる。
【0119】
このように、一般的には、トレードオフの関係にある、速度−精度や、速度−メモリ量といった要素を同時に向上させることができる。
【0120】
実際に、自然言語処理分野の固有表現抽出及び係り受け解析に本実施の形態のモデル構築装置を適用した場合の効果を図10及び図11に示す。
また、本発明は、自然言語処理やバイオインフォマティクスの研究分野の分類問題に属する問題で教師あり学習を行うような設定で特に高い効果が得られることを意図して考案された発明である。具体的な利用例として、文書を分類する文書分類問題、文(文書)に対して言語的な構造を解析する問題、DNA 塩基配列に遺伝子領域とアミノ酸対応を示すラベルを付与する問題、たんぱく質の2次構造予測問題等が考えられる(図12及び図13)。
【0121】
また、上述のモデル構築装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、WWWシステムを利用している場合であれば、ホームページ提供環境(あるいは表示環境)も含むものとする。
【0122】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【実施例】
【0123】
本発明を自然言語処理分野での文書分類問題に適用した実施例について説明する。
【0124】
まず、計算機による自動文書分類システムを想定する。自動文書分類システムでは、入力が文書、出力が文書に付与すべきクラスとなる。出力である「文書に付与すべきクラス」とは、例えば、カテゴリへの分類問題を想定すると、書籍の体系のように「科学」「経済」「政治」「スポーツ」といったものがクラスとなる。また、スパム分類のような文書分類問題を想定すると、出力クラスは、「スパム文書」か「通常の文書」の二クラスになる。それ以外にも、任意の商品に対するアンケートからの評判分析をするような文書分類問題を想定する場合には、例えば、出力クラスは5 段階の「非常に良い」「良い」「普通」「悪い」「非常に悪い」のようなものになる。図14に典型的な自動文書分類システムの例を示す。
【0125】
次に、このような文書分類システムを構築する方法について述べる。近年では、このような問題は正解データを準備し、そこから教師あり学習により分類モデルを構築する方法が主流である。このとき、正解データとは、構築したい自動文書分類システムの入力と出力とのペアに相当するデータである。教師あり学習とは、この正解データから、演繹的に自動分類モデルを学習する方法である。
【0126】
次に、文書分類問題を教師あり学習によりモデル構築する際に用いる素性関数について述べる。文書分類問題の例では、文書中に出現する単語を原素性として用いる方法が一般的である。これは、文書を構成する要素が単語であること、及びそれぞれの単語が問題を説明する大きな要素となるからである。ただし、この場合、原素性の数は、単語数となるため、例えば、数万や数百万といった非常に大きな数となる。ここで、単語が{F1,・・・,FN}とN個存在する場合、n番目の素性関数、例えば、下記(24)式に示すようなものが考えられる。
【0127】
【数16】
【0128】
また、下記(25)式に示すように、単純に単語が出現したか否かを0と1とで表現する二値素性関数としてもよい。
【0129】
【数17】
【0130】
ここでは、この素性関数を例として以下の説明を述べる。
【0131】
文書分類システムとしては、入力としてある文書xが与えられた場合に、推定した出力クラスyを選択する。ここでは、自動文書分類システムのモデルとして、(2)式で示した線形分類モデルを用いる。つまり、定義した素性関数及びその重みの線形和が最も大きくなるクラスが出力として選択される。
【0132】
線形モデルを教師あり学習により構築することは、線形モデルのモデルパラメータであるwnの値を決定することに相当する。これには、正解データを利用する教師あり学習により値を決定する。また、学習法としては、例えば、確率モデル(対数線形モデル)による尤度最大化や、線形モデルによるマージン最大化に基づくモデルパラメータ推定法を用いる。
【0133】
学習が終わり、モデルパラメータが決定したあと、縮約素性関数の定義を生成する。文書分類で、素性に単語を利用している場合には、単語のクラスタリングをすることに近い処理になる。つまり、重要度が同じぐらいになる単語を一つに融合する処理である。図14及び15に原素性関数と縮約素性関数とを用いた際の処理の違いを示す。
【0134】
最後に、生成された縮約素性関数定義に従って素性関数を生成し、それを用いて通常の教師あり学習アルゴリズムを用いてモデルパラメータを再推定する。
【符号の説明】
【0135】
10 モデル構築装置
12 ベースモデル構築部
14 縮約素性関数集合生成部
16 モデル再構築部
20 正解データ
22 ベースモデル
24 未解析データ
26 縮約素性関数集合定義
28 最終モデル
141 原素性重要度計算部
142 原素性選択部
143 原素性融合部
144 原素性重要度追加部
【技術分野】
【0001】
本発明は、縮約素性生成装置、方法、プログラム、モデル構築装置及び方法に係り、特に、教師あり学習に用いるための縮約素性集合を生成するための縮約素性生成装置、方法、及びプログラム、並びに、生成された縮約素性集合を用いてモデルを構築するモデル構築装置及び方法に関する。
【背景技術】
【0002】
自然言語処理やバイオインフォマティクスの研究分野の分類問題に属する問題は、近年では、正解データから統計的な機械学習を行う手法である教師あり学習により、分類器のモデルを構築する方法が主流であり、多くの研究で良い精度が得られることが知られている。教師あり学習を行う際には、図16に示すように、対象とする問題に有用と思われる判別規則、または、判別規則を構成する要素と雛形とを人手で事前に定義する方法が一般的である。ここで定義される判別規則を一般的に「素性」と呼ぶ。正解データを用いた学習により構築されたモデルを用いることで、図17に示すように、正解が分かっていないデータ(未解析データ)を解析し、解析結果を得ることができる。なお、図16及び17中の矢印は、定義の依存関係を示す。
【0003】
素性は、入力されるデータに対して解きたい問題を特徴付けるものであり、人間の持つ知識や直感等に基づいて定義される場合が多い。自然言語処理の問題では、単語や単語の連接等が素性として用いられることが多い。これは、文書を構成する要素が単語であること、及び、それぞれの単語が問題を説明する主要な要因となることが多いためである。また、意味や高次の情報を外部のリソース(例えば辞書)等を参照して利用することも行われている。この素性の設計により、教師あり学習によるモデル学習の精度が大きく影響を受ける。
【0004】
一般論として、機械学習を行う際に素性数が多いと学習データに過適応してしまい相対的に汎化性能が悪くなる。この問題は、「次元の呪い」といわれる良く知られた問題として説明できる。つまり、機械学習では、素性数がそのまま素性空間の次元数に相当することから、素性を一つ増やす毎に、十分な汎化性能を得るために必要なデータ量は指数関数的に増大し、現実的にデータ量を準備することが不可能となる、という問題である。
【0005】
ただし、自然言語処理やバイオインフォマティクスの問題を対象とする場合には、解きたい問題をうまく特徴付けるものは、テキスト中の単語であるとか、遺伝子配列の記号系列などといった離散シンボルである。また、解きたい問題に対して、個々の離散シンボルにより説明できる問題の事象の範囲はごく少数のデータに対してのみである場合がほとんどである。それ故に、解きたい問題全体をうまく説明するのに必要な素性数は、非常に多くなることが一般的である。さらに、同一のシンボルであっても状況によって多くの例外が発生する場合が多いため、複数のシンボルの組み合わせなどを考慮して対応する必要が生じる。このような状況では、結果的に、多くの離散シンボルまたはその組み合わせによる素性の集合を用いて問題を特徴付けることが必然となる。すると、個々の素性がデータ上に出現する割合は非常に小さくなる傾向となり、データx素性の行列を考えた場合、要素の多くが0となる疎行列となる。要素が0とは、情報が無いことと等価であり、各素性が出現する割合が大きく密行列となる場合と比較して、「次元の呪い」問題が示すように、より多くのデータを必要とすることを意味する。このように、自然言語処理やバイオインフォマティクスの問題では、そもそも「次元の呪い」問題が頻出しやすい問題設定となっているという背景がある。
【0006】
理論的には、「次元の呪い」問題は、学習データが無限に存在すれば回避できると考えられる。しかし、正解データを用いた教師あり学習の枠組みでは、正解データは人手で作成するのが最も一般的であるため、作成コストが高く、高次元素性空間を統計的に十分満たす量を作成するのは非常に困難である。そのため、正解データ量を増やしてこの問題に対処するという方案は、現実的ではない。結果的に、教師あり学習の枠組みでは、限定された正解データ量で学習すると、十分な汎化性能が得られない可能性がある。
【0007】
このように、素性設計の観点では、多くの素性を利用する方が解きたい問題をうまく表現できるため適していると考えられるが、機械学習の観点では、素性数は極力少なくするべきであるというジレンマがある。
【0008】
このような問題を解決するための方法として、例えば、素性空間の次元圧縮や次元削減等と呼ばれる、高次元素性空間を低次元空間に写像する方法が提案されている(例えば、非特許文献1参照)。同様に、任意のクラスタリング法等を用いて素性をクラスタリングして新たな素性とする方法も提案されている(例えば、非特許文献2参照)。
【先行技術文献】
【非特許文献】
【0009】
【非特許文献1】Joseph Turian, Lev-Arie Ratinov, and Yoshua Bengio. 2010. Word representations: A simple and general method for semi-supervised learning. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 384−394.
【非特許文献2】Terry Koo, Xavier Carreras, and Michael Collins. 2008. Simple Semi-supervised Dependency Parsing. In Proceedings of ACL-08: HLT, pages 595−603.
【発明の概要】
【発明が解決しようとする課題】
【0010】
しかしながら、非特許文献1及び2の方法は、特定の問題では効果を発揮する場合も考えられるが、実際に現在これらの方法が、ほとんど用いられていないことを考慮すると、一般的にはそれほど効果は期待できない。また、自然言語処理やバイオインフォマティクスの問題では、前述のようにデータx素性の行列が疎行列になるという観点から、行列分解による方法や、最近傍法に基づくクラスタリング法等は、効果が得られないことが一般的に知られている。つまり、高次元かつ疎な素性空間であるが故に、統計や機械学習の観点でうまく素性を縮約することが困難であり、また、精度向上という効果を得ることが困難である、という問題がある。これは、非特許文献1及び2のような方法の枠組みは、素性数を削減して、全素性を用いる場合と同等の精度を達成するためのものだからである。
【0011】
前述のクラスタリングや素性の次元削減法以外にも、素性選択という観点で様々な取り組みがなされている。ただし、これらの方法は、本来不要な素性をうまく選択して削除することにより、素性集合を縮小することを目的としている。つまり、仮に、不要な素性が存在しなければ、素性の削減には結びつかない方法と言える。これら素性選択の技術も、基本的には、素性数を減らして元と同じ精度を達成することを目的としているため、精度を向上させることは困難な枠組みである、という問題がある。
【0012】
本発明は、上記問題を解決するためになされたもので、一般的な教師あり学習に用いられる素性よりも、コンパクトかつ高精度の縮約素性を生成することができる縮約素性生成装置、方法、及びプログラムを提供することを目的とする。また、学習時の過適合を低減することができるモデル構築装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【0013】
上記目的を達成するために、第1の発明の縮約素性生成装置は、入力に対する正解が既知の正解データから学習して構築されたベースモデルに、入力に対する正解が未知の複数の未解析データを入力した際の該ベースモデルの最尤出力に対して、前記複数の未解析データから抽出された該未解決データの特徴を表す複数の原素性各々が与える影響を示す重要度を、前記複数の原素性各々について計算する計算手段と、前記計算手段により計算された複数の原素性各々の重要度に基づいて、前記複数の未解析データから抽出された複数の原素性から、前記ベースモデルの最尤出力に対して影響を与える原素性を選択する選択手段と、前記原素性各々の重要度に基づいて、前記選択手段により選択された原素性の集合から、1つ以上の原素性をまとめた縮約素性の集合を生成する生成手段と、を含んで構成されている。
【0014】
第1の発明の縮約素性生成装置は、計算手段が、入力に対する正解が既知の正解データから学習して構築されたベースモデルに、入力に対する正解が未知の複数の未解析データを入力した際の該ベースモデルの最尤出力に対して、複数の未解析データから抽出された該未解決データの特徴を表す複数の原素性各々が与える影響を示す重要度を、複数の原素性各々について計算する。そして、選択手段が、計算手段により計算された複数の原素性各々の重要度に基づいて、複数の未解析データから抽出された複数の原素性から、ベースモデルの最尤出力に対して影響を与える原素性を選択し、生成手段が、原素性各々の重要度に基づいて、選択手段により選択された原素性の集合から、1つ以上の原素性をまとめた縮約素性の集合を生成する。
【0015】
このように、原素性がベースモデルの最尤出力に与える影響を示す重要度を原素性毎に計算し、この重要度に基づいて選択された原素性から縮約素性を生成するため、コンパクトかつ精度良く縮約された縮約素性を生成することができる。
【0016】
また、前記計算手段は、前記複数の未解析データを複数の部分集合に分割し、分割した複数の部分集合毎に前記重要度を計算するためのパラメータを算出し、該部分集合各々から抽出された複数の原素性各々と前記パラメータとのペアを生成し、前記ペアに基づいて、前記原素性毎に前記パラメータの値を集計して求めて、前記重要度を計算することができる。これにより、未解決データの量が多い場合でも、効率的に重要度を計算することができる。
【0017】
また、前記生成手段は、前記縮約素性各々に含まれる原素性の重要度に関する素性を生成し、前記縮約素性の集合に追加することができる。原素性自体のみならず、原素性の重要度に関する情報も非常に有用な情報であるため、縮約素性の集合に追加することで、縮約素性の集合の精度がより向上する。
【0018】
また、第2の発明のモデル構築装置は、第1の発明の縮約素性生成装置と、前記正解データから学習して前記ベースモデルを構築する構築手段と、前記縮約素性生成装置により生成された縮約素性の集合から学習して最終モデルを再構築する再構築手段と、を含んで構成されている。このように、コンパクトかつ高精度に生成された縮約素性を用いて最終モデルを再構築することにより、学習時の過適合を低減することができる。
【0019】
また、第3の発明の縮約素性生成方法は、計算手段と、選択手段と、生成手段とを含む縮約素性生成装置における縮約素性生成方法であって、前記計算手段は、入力に対する正解が既知の正解データから学習して構築されたベースモデルに、入力に対する正解が未知の複数の未解析データを入力した際の該ベースモデルの最尤出力に対して、前記複数の未解析データから抽出された該未解決データの特徴を表す複数の原素性各々が与える影響を示す重要度を、前記複数の原素性各々について計算し、前記選択手段は、前記計算手段により計算された複数の原素性各々の重要度に基づいて、前記複数の未解析データから抽出された複数の原素性から、前記ベースモデルの最尤出力に対して影響を与える原素性を選択し、前記生成手段は、前記原素性各々の重要度に基づいて、前記選択手段により選択された原素性の集合から、1つ以上の原素性をまとめた縮約素性の集合を生成する方法である。
【0020】
また、第4の発明のモデル構築方法は、第1の発明の縮約素性生成装置と、構築手段と、再構築手段とを含むモデル構築装置におけるモデル構築方法であって、前記構築手段は、入力に対する正解が既知の正解データから学習してベースモデルを構築し、前記縮約素性生成装置は、前記縮約素性の集合を生成し、前記再構築手段は、前記縮約素性生成装置により生成された縮約素性の集合から学習して最終モデルを再構築する方法である。
【0021】
また、第5の発明の縮約素性生成プログラムは、コンピュータを、第1の発明の縮約素性生成装置を構成する各手段として機能させるためのプログラムである。
【発明の効果】
【0022】
以上説明したように、本発明の縮約素性生成装置、方法、及びプログラムによれば、原素性がベースモデルの最尤出力に与える影響を示す重要度を原素性毎に計算し、この重要度に基づいて選択された原素性から縮約素性を生成するため、一般的な教師あり学習に用いられる素性よりも、コンパクトかつ高精度の縮約素性を生成することができる、という効果が得られる。
【0023】
また、本発明のモデル構築装置及び方法によれば、コンパクトかつ高精度に生成された縮約素性を用いて最終モデルを再構築することにより、学習時の過適合を低減することができる、という効果が得られる。
【図面の簡単な説明】
【0024】
【図1】(a)一般的なモデルを示す概念図、及び(b)本実施の形態の概要を示す概念図である。
【図2】原素性集合と縮約素性集合との関係を示すイメージ図である。
【図3】本実施の形態のモデル構築装置の機能的構成を示すブロック図である。
【図4】縮約素性関数集合生成部の機能的構成を示すブロック図である。
【図5】原素性重要度計算部の機能的構成を示すブロック図である。
【図6】本実施の形態のモデル構築装置におけるモデル構築処理ルーチンの内容を示すフローチャートである。
【図7】本実施の形態のモデル構築装置の縮約素性関数集合生成部における縮約素性関数集合生成処理ルーチンの内容を示すフローチャートである。
【図8】縮約素性関数集合生成処理を示す概念図である。
【図9】MapReduceによる原素性の重要度の計算処理を説明するための図である。
【図10】本実施の形態のモデル構築装置を固有表現抽出に適用した場合の効果を示す図である。
【図11】本実施の形態のモデル構築装置を係り受け解析に適用した場合の効果を示す図である。
【図12】文書分類問題への適用例の概要を示す図である。
【図13】固有表現抽出問題への適用例の概要を示す図である。
【図14】文書分類問題へ本発明を適用した実施例の参考例として、原素性関数を用いた場合の処理を示す概略図である。
【図15】文書分類問題へ本発明を適用した実施例の処理を示す概略図である。
【図16】従来の教師あり学習でのモデル構築の概要を示す概念図である。
【図17】従来の教師あり学習で構築されたモデルを用いた未解析データの解析の概要を示す概念図である。
【発明を実施するための形態】
【0025】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
<概要>
まず、本実施の形態の概要について説明する。
【0026】
ここでは、正解の解析結果が付与されていないデータを、正解の解析結果が付与されている正解データと対比した呼び方で、未解析データと呼ぶ。本実施の形態は、大規模な未解析データを利用することを前提とした技術である。
【0027】
自然言語処理やバイオインフォマティクスといった分野の問題では、大規模な未解析データを比較的容易に獲得することができる。例えば、自然言語処理の場合は、近年では、電子化された文書をweb等から容易に獲得することができる。
【0028】
本実施の形態の概要としては、まず、大規模未解析データ上で各素性の重要度を計算する。これは、素性の重要度を計算するという観点では、解きたい問題の正解は不要であるため、限定された量の正解データではなく、比較的容易に獲得可能な大規模な未解析データを用いることで、「次元の呪い」の影響が軽減された状態で統計量(重要度)を推定できる。次に、大規模なデータから得られた比較的信頼性の高い統計量(重要度)を用いて素性空間を再構築する。具体的には、重要度に基づいて素性のクラスタリング及び削除を行い、更に、重要度の値自身を素性の値として活用する。このように再構築された素性空間は、大規模なデータから導出されているため、解きたい問題全体をコンパクトにかつ精度良く表現できている可能性が高い。最後に、再構築した素性空間を使って、通常の正解データを使った教師あり学習によりモデルを学習する。これにより、図1(a)に示す従来のモデルよりもコンパクトなモデル(同図(b))を構築することができる。
<本実施の形態の原理>
次に、本実施の形態の原理について説明する。
【0029】
まず、以下の説明で用いる記号について、下記のように定義する。
【0030】
X:可能な全ての入力の集合
Y:可能な全ての出力の集合
x:任意の一つの入力、つまり、x∈Xの関係が成り立つ。
【0031】
y:任意の一つの出力、つまり、y∈Yの関係が成り立つ。
【0032】
Y(x):ある一つのxが与えられた際に得られる可能性のある出力の集合、ただし、Y(x)⊆Yの関係が成り立つ。
【0033】
fn(x、y):学習用素性定義で定義されたn番目の原素性関数。戻り値は実数(スカラー)である。
【0034】
N:学習用素性定義で定義された原素性または原素性関数の総数
wn:n番目のパラメータ。線形モデルの場合には基本的にn番目の素性関数に対する重みに相当する。よってn∈{1,・・・,N}である。
【0035】
hn(x、y):m番目の縮約素性関数。戻り値は実数(スカラー)である。
【0036】
hm(x、y)=Σfn∈Smfn(x、y)
M:生成される縮約素性または縮約素性関数の総数
なお、本実施の形態では、大規模な未解析データ上で各素性の重要度を計算し、重要度に基づいて素性のクラスタリング及び削除を行うことにより、解きたい問題全体をコンパクトにかつ精度良く表現できる素性空間を再構築する。この再構築された素性空間を構成する素性を縮約素性と呼ぶ。
【0037】
ここで、本実施の形態で用いる縮約素性を以下のように定義する。まず、説明を簡単にするため、従来一般的に教師あり学習で用いる素性を、原素性と呼ぶ。学習に利用する際には、複数の素性を利用することから、学習に利用する全ての縮約素性をまとめて縮約素性集合と呼び、また、学習に利用する全ての原素性をまとめて原素性集合と呼ぶ。このとき、縮約素性とは、「原素性集合内の一つ以上の原素性で構成される素性」とする。
【0038】
形式的には以下のような定義となる。縮約素性集合をH、原素性集合をFとする。また、縮約素性集合内の素性数をM、原素性集合内の素性数をNとする。この時、定義からM≦Nが成り立ち、多くの場合M≪Nとなるように構成する。
【0039】
次に、縮約素性集合内の任意の一つの縮約素性hm∈Hは、原素性集合F内の一つ以上の集合で構成されるとする。つまり、hm=Sm、ただし、Sm⊆Fの関係が成り立つ。
【0040】
ここで、原素性集合内の任意の一つの原素性fn∈Fは、高々一つの縮約素性hmの構成要素にしかならないと仮定する。この仮定は、任意の二つの縮約素性の構成要素に同じ原素性が存在することは決してない事を保証し、かつ、いくつかの原素性はどの縮約素性の構成要素にもならない場合があることを意味している。つまり、任意のmとm’、ただし、m≠m’の時に、Sm∩Sm’=O(空集合)、及び∪m=1MSm⊆Fが成り立つことを意味する。図2に原素性と縮約素性との関係を示す。
【0041】
次に、縮約素性を利用して生成される縮約素性関数を定義する。一般的に素性関数とは、定義した素性に基づいて定義される関数であり、入力xと出力yとにより値が決定する関数である。素性関数は、一般的にf(x,y)のような形で表される。この素性関数f(x,y)の戻り値はスカラー(実数)である。
【0042】
ここで、原素性に従って定義される素性関数を原素性関数と呼ぶ。また、入力xと出力yとにより値が決定するn番目の原素性に対する原素性関数をfn(x,y)とする。fn(x,y)は、入力xと出力yとが与えられたとき、n番目の原素性の値(または、n番目の原素性が成立するか否かを表す値)を返す関数である。ただし、原素性は全部でN 個であるので、n∈{1,・・・,N}である。同様に、入力xと出力yとにより値が決定するm番目の縮約素性に対する縮約素性関数をhm(x,y)とする。ただし、縮約素性は全部でM個であるので、m∈{1,・・・,M}である。このとき、縮約素性関数の戻り値は、対象となる縮約素性の構成要素となった全ての原素性関数の戻り値の総和と定義する。従って、縮約素性関数hm(x,y)は、下記(1)式で表すことができる。
【0043】
【数1】
【0044】
このことから、縮約素性関数の値は、原素性関数の値に従って自動的に定義されることを意味し、縮約素性関数用に新たに計算式を定義する必要はないことを意味する。
【0045】
次に、ベースモデルについて定義する。本実施の形態では、学習に用いるモデルは(対数)線形モデルであると仮定する。線形モデルの判別関数g(入力xに対する出力yの尤もらしさを返す関数)は、下記(2)式で定義することができる。
【0046】
【数2】
【0047】
ここで、wnはn番目の原素性関数fn(x,y)に対するモデルパラメータ(重み)である。つまり、線形モデルでは、入力xが与えられた場合に、出力yの尤もらしさは、全ての原素性関数fn(x,y)の重み付き和によって評価されることを意味している。
【0048】
また、入力xが与えられた際の最尤出力^yを決定する方法は、判別関数gを用いて、下記(3)式で表される最大化問題を解くことに帰着する。
【0049】
【数3】
【0050】
線形モデルは、分類問題等で用いられる最も簡潔なモデルである一方、多くの実問題で十分な精度が得られることが多く、多くの場面で利用されているモデルである。また、計算が単純な加算及び乗算で行えることから、速度面でも複雑なモデルに対して優位性がある場合が多い。
【0051】
本実施の形態では、ある縮約素性関数を自動的に生成するために、後述する原素性の重要度を計算する。この原素性の重要度の計算に際して、事前に通常の教師あり学習により構築されたモデルを利用する。このモデルを、ここではベースモデルと呼ぶ。ここで述べたように、ベースモデルも(対数)線形モデルであると仮定する。
【0052】
次に、本実施の形態において、ある縮約素性関数を自動構築する際に計算する原素性の重要度の定義を述べる。
【0053】
まず、関数r(x,y)を定義する。ある入力xが与えられたときのベースモデルによる最尤出力を^yとする。このとき、関数r(x,y)は、与られたyがベースモデルによる最尤出力^yと同じ場合、つまり、y=^yの場合には1を返し、それ以外の場合には−1を返す関数とする。つまり、関数r(x,y)は、ベースモデルに従って戻り値が決定される関数である。
【0054】
次に、−r(x)を、関数r(x,y)のxにおける平均とする(下記(4)式)。
【0055】
【数4】
【0056】
また、rd(x,y)を、平均−r(x)からの実際の値r(x,y)の偏りを表すとする(下記(5)式)。
【0057】
【数5】
【0058】
次に、下記(6)式及び(7)式に示すように、VD+(fn)及びVD−(fn)を定義する。
【0059】
【数6】
【0060】
また、Dを未解析データの集合とする。このとき、各原素性関数fnの重要度を下記(9)式で定義する。
【0061】
【数7】
【0062】
ここで、VD+(fn)は、ある入力xが与えられた際にベースモデルが選択した最尤出力^yに対し原素性関数fn(x,y)の値がどの程度貢献しているかを未解析データD 内の全ての入力データで評価した値を意味する。同様に、VD−(fn)はベースモデルが選択しなかった出力に対して原素性関数fn(x,y)の値がどの程度貢献しているかを未解析データD内の全ての入力データで評価した値を意味する。つまり、原素性重要度VD(fn)の意味は、以下のように解釈できる。|VD(fn)|が相対的に大きい値の場合には、原素性関数fn(x,y)は、ベースモデルの最尤出力の決定の際に大きな影響を与えているとみなすことができる。よって、原素性fnは、重要な素性であると推定できる。逆に、|VD(fn)|が相対的に小さい値の場合には、原素性関数fn(x,y)は、ベースモデルが最尤出力を決定する際にほとんど影響を与えないとみなすことができる。よって、原素性fnは、ほぼ意味のない素性であると推定できる。このような視点から、VD(fn)は原素性の重要度を表現していると言える。
【0063】
次に、精度の良い縮約素性を生成するために、原素性重要度を計算する際に、信頼性の低い値の正則化、及び、重要度の離散化という二つの要素を取り入れる。
【0064】
まず一つ目の正則化に関しては、下記(10)式に示すように、VD(fn)をVD'(fn)に変更することで実施する。
【0065】
【数8】
【0066】
ここで、Cは正の実数であり、正則化パラメータとする。この時の注意点として、VD(fn)=VD+(fn)−VD−(fn)=Rn/Fnが成り立つ点である。つまり、VD(fn)との違いは、単にCを導入しただけであり、C=0のときVD(fn)=VD’(fn) となる。正則化パラメータにより、Rnが小さいときには大きく値が0方向に圧縮される操作となる。特に、|Rn|≦Cの時、VD’(fn)=0となる。
【0067】
次に、原素性重要度の離散化について述べる。まず、下記(12)式に示す補助関数を定義する。
【0068】
【数9】
【0069】
次に、整数空間をN(N={・・・,−2,−1,0,1,2,・・・}を考える。また、δを正の実数とし、整数空間Nに対して、各整数をスケーリングする値として導入する。ここでは、離散空間N/δを、整数空間の各整数をδによってスケーリングした離散空間として定義する。つまり、N/δ={・・・,−2/δ,−1/δ,0,1/δ,2/δ,・・・}である。このとき、実数値VD’(fn)の離散空間N/δ内で最も近い上限及び下限の値を、下記(14)式に示すように定義する。
【0070】
【数10】
【0071】
そして、最終的に下記(15)式を用いて原素性の重要度を離散化する。
【0072】
【数11】
【0073】
つまり、最終的にun*がn番目の原素性の重要度の値となる。
【0074】
なお、本実施の形態の原素性重要度計算は、下記(16)式に示す最適化問題を解くことと等価である。
【0075】
【数12】
【0076】
ここで、nは、(16)式に対するunの最適解を表す。また、u*={un*}n=1Nとする。
【0077】
この式から、解空間がN/δで定義される離散空間であるという条件下で、各素性毎に、未解析データD上でのrdとunとの間の最小二乗誤差を最小化する問題と解釈できる。
【0078】
ここで、制約である各パラメータの制約であるun∈N/δを考えない場合は、(16)式 は、凸最適化問題となる。凸最適化問題では、勾配が0になる点が大域的最適解となることが保証される。ここでは、下記(17)式に示す最小化したい目的関数に対して、un の偏微分は下記(18)式となる。
【0079】
【数13】
【0080】
ここで、∂U(u|D)/∂un=0とおけば、VD’(fn)が解となることがわかる。また、離散化制約を満たす解は、(10)式により得られる。つまり(16)式の解は、(15)式により得ることができる。
<システム構成>
次に、本発明の縮約組成生成装置を適用したモデル構築装置を例にして、本実施の形態を説明する。
【0081】
本実施の形態のモデル構築装置10は、CPU(Central Processing Unit)と、RAM(Random Access Memory)と、後述する縮約組成関数集合生成処理ルーチンを含むモデル構築処理ルーチンを実行するためのプログラムを記憶したROM(Read Only Memory)とを備えたコンピュータで構成されている。
【0082】
このコンピュータは、機能的には、図3に示すように、ベースモデル構築部12と、縮約素性関数集合生成部14と、モデル再構築部16とを含んだ構成で表すことができる。
【0083】
ベースモデル構築部12は、正解データ20を入力として、周知の教師あり学習により対象とする問題のベースモデル22を構築(学習)する。ここで、入力される正解データ20は、対象とする問題に応じて人手により定義した「モデル定義」及び「原素性関数集合定義」である。
【0084】
具体的には、ベースモデル構築部12は、従来の教師あり学習によるモデル構築処理を実施する。教師あり学習の方法としては、解きたい問題に合わせて様々な方法を用いることができる。例えば、スパムフィルタのように、スパムかそうでないかという二つのクラスに分類したいような問題では、Support Vector Machine(参考文献:V.Vapnik. The Nature of Statistical Learning Theory. Spring-Verlag, New York, 1995.参照)等の二クラス分類器用の学習法を用いることができる。また、分類したいクラスの種類が二つ以上の場合は、多クラスロジスティック回帰モデル等を用いて教師あり学習が行われる。自然言語処理分野の係り受け解析等では、条件付確率場(参考文献:J. Lafferty, A. McCallum, and F. Pereira. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. In Proc. of ICML-2001, pages 282−289, 2001.)といった構造予測器用のモデルを用いて学習することができる。
【0085】
ベースモデル構築部12により学習されたベースモデル22は、モデル定義及び原素性関数集合定義を含む。
【0086】
縮約素性関数集合生成部14は、大量の未解析データ24と、ベースモデル構築部12の出力であるベースモデル22とを用いて、縮約素性関数集合の定義(縮約素性関数集合定義26)を生成する。この縮約素性関数集合生成部14が、本発明の縮約素性生成装置の一例である。
【0087】
モデル再構築部16は、正解データ20と、縮約素性関数集合生成部14で生成した縮約素性関数集合定義26とを用いて、周知の教師あり学習アルゴリズムを用いた教師あり学習により、対象とする問題のモデルを再構築する。なお、ここで再構築されるモデルを、ベースモデルと区別して、「最終モデル」と呼ぶ。
【0088】
ここで、縮約素性関数集合生成部14で得られる縮約素性関数集合定義26は、原素性関数群定義から無駄を省いた縮約形を自動で生成したものに相当するため、性質としては、原素性関数集合定義と同じとなる。よってモデル再構築部16の処理は、本質的にベースモデル構築部12と同様に、従来の教師あり学習によるモデル構築の処理に相当する。つまり、ベースモデル構築部12及びモデル再構築部16の処理は、従来技術をそのまま用いることができる。
【0089】
すなわち、本実施の形態の主要部は、本発明の縮約素性生成装置を適用した縮約素性関数集合生成部14にある。つまり、縮約素性関数集合生成部14は、教師あり学習で一般的に用いる原素性集合から、教師あり学習に適した縮約素性関数集合定義26を生成する。
【0090】
以下、縮約素性関数集合生成部14について、より具体的に説明する。図4に示すように、縮約素性関数集合生成部14は、原素性重要度計算部141と、原素性選択部142と、原素性融合部143と、原素性重要度追加部144とを含んだ構成で表すことができる。なお、原素性融合部143及び原素性重要度追加部144が、本発明の生成手段の一例である。
【0091】
原素性重要度計算部141は、入力されたベースモデル22に含まれる各原素性関数について、原素性重要度un*を計算する。未解析データ24の量が少ない場合には、各未解析データ24毎に(15)式により、原素性重要度un*を直接計算することができる。ただし、一般的に未解析データ24の量は非常に多くなることから、本実施の形態では、分散並列計算モデルによる効率的な計算方法について説明する。ここでは、MapReduceモデル(参考文献:J. Dean and S. Ghemawat. 2008. MapReduce: Simplified Data Processing on Large Clusters. Commun. ACM, 51(1):107−113.)を応用した計算方法を示す。
【0092】
原素性重要度計算部141は、図5に示すように、未解析データ分割部141aと、Key−valueペア生成部141b−1〜Pと、Key−valueペア集計部141c−1〜Rと、原素性重要度出力部141dとを含んだ構成で表すことができる。なお、Key−valueペア生成部141b−1〜Pの各々、及びKey−valueペア集計部141c−1〜Rの各々をそれぞれ区別することなく説明する場合には、単に、Key−valueペア生成部141b、及びKey−valueペア集計部141cと表記する。
【0093】
未解析データ分割部141aは、未解析データ24をP個の部分集合に分割し、分割した未解析データ24の部分集合を、P個のKey−valueペア生成部141b−1〜Pへそれぞれ出力する。
【0094】
Key−valueペア生成部141bは、受け取った未解析データ24の部分集合に対し、ベースモデル22を用いて、(Tn,Rn,Fn)を計算する。ここで、Tnは(13)式に示す値であり、(12)式に用いられている原素性重要度を離散化する際に計算する補助関数の値である。また、Rnは(11)式、Fnは(8)式に示す値であり、(10)式で用いられている原素性重要度そのものを計算するための値である。そして、各原素性をkey、各未解析データの部分集合により計算された(Tn,Rn,Fn)をvalueとするkey−valueペアの系列を生成し、生成したkey−valueペアの系列を、R個のKey−valueペア集計部141c−1〜Rへ出力する。
【0095】
Key−valueペア集計部141cは、P個のKey−valueペア生成部141bから取得したkey−valueペアを用いて、原素性(key)毎にvalueの値を集計し、原素性毎の(Tn,Rn,Fn)値を求める。そして、(15)式を用いて、原素性fnに対する離散化かつ正則化された原素性重要度un*を計算する。ここで、C及びδの値は、予め設定しておくものとする。
【0096】
原素性重要度出力部141dは、Key−valueペア集計部141cで計算された原素性重要度un*を出力する。
【0097】
原素性選択部142は、原素性重要度計算部141で計算された原素性重要度un*に基づいて、不必要と考えられる原素性を排除する。具体的には、(15)式により重要度を離散化した値un*に対して、un*=0を除いた重要度を離散化した値の集合を出力する。これは、un*=0となった原素性fnを不必要と判定し、原素性の集合から排除することに相当する。原素性選択部142の処理は、原素性の重要度が0ということは、その原素性はモデルの出力決定に影響を与えないであろうと推定されたことを意味するので、これらの素性を縮約素性に含めないための処理である。
【0098】
原素性融合部143は、原素性選択部142で求めた不必要な原素性を排除した原素性の重要度を離散化した値un*の集合を用いて、複数の原素性を一つの縮約素性として融合する。簡単な処理の例として、計算した重要度un*に基づき、同じ重要度となった原素性を一つの縮約素性としてまとめ上げることができる。
【0099】
各un*は離散値であるため、いくつか同じ値である場合が想定される。よって、値の集合の要素数は必ずN以下となる。ここでは、値の集合の要素数をMとする。次に、Sm を、m番目の原素性重要度の値となった原素性fnの集合とする。このとき、m番目の縮約素性関数hm(x,y)を、Sm内の原素性関数fn(x,y)の総和、すなわち、(1)式により計算する。
【0100】
原素性重要度追加部144は、原素性融合部143で求めた縮約素性に素性重要度un*に関する情報を追加する。計算した素性重要度un*の値自体も非常に有効な情報源であるため、縮約素性に利用するものである。ここでは、M+1番目の縮約素性として、下記(20)式で定義される素性φ(x,y)を追加する。
【0101】
ただし、umは、m番目に対応つけられた原素性重要度である。ここでは、原素性融合部143において、原素性重要度が同じ値の原素性を融合して縮約素性としているため、必然的にm番目に対応つけられた原素性重要度は一つの値となる。
【0102】
【数14】
【0103】
これは、全ての縮約素性を重要度の重み付きで総和を取ったものである。よって、縮約素性関数の集合は、{h1(x,y),・・・,hM(x,y),φ(x,y)}となる。
【0104】
ただし、φ(x,y)の計算量は無視できる。φ(x,y)を一つの素性として線形モデルで用いる際には、線形モデルの判別関数g(x,y)は、下記(21)式で計算することができる。
【0105】
【数15】
【0106】
ここで、学習が終わった後には、{wm}m=1M+1は固定した値となるため、wm‘は事前に計算することができる。この結果、(22)式に示すように、φが消えて、hmのみに依存した線形モデルと同じ形式で表現することができる。つまり、φを取り入れても、取り入れなくても、変数の数はMとして計算できるため、φを導入しても計算時間は増大しない。
<モデル構築装置の作用>
次に、本実施の形態に係るモデル構築装置10の作用について説明する。正解データとして、対象とする問題に応じて人手により定義した「モデル定義」及び「原素性関数集合定義」が所定の記憶領域に記憶され、モデル構築装置10において、図6に示すモデル学習処理ルーチンが実行される。
【0107】
ステップ100で、正解データ20を入力として、周知の教師あり学習により対象とする問題のベースモデル22を構築(学習)する。
【0108】
次に、ステップ200で、後述する縮約素性関数集合生成処理ルーチンを実行して、縮約素性関数集合定義26を生成する。
【0109】
次に、ステップ300で、正解データ20と、上記ステップ200で生成した縮約素性関数集合定義26とを用いて、周知の教師あり学習アルゴリズムを用いた教師あり学習により、対象とする問題の最終モデル28を再構築して、処理を終了する。
【0110】
次に、図7及び図8を参照して、縮約素性関数生成処理ルーチンについて説明する。
【0111】
ステップ202で、MapReduceモデルを用いて、入力されたベースモデル22に含まれる各原素性関数について、原素性重要度un*を計算する。
具体的には、図9に示すように、未解析データ24をP個の部分集合に分割し、分割した未解析データ24の部分集合に対し、ベースモデル22を用いて、(13)式、(11)式、及び(8)式により、(Tn,Rn,Fn)を計算する。そして、各原素性をkey、各未解析データの部分集合により計算された(Tn,Rn,Fn)をvalueとするkey−valueペアの系列を生成する。そして、生成したkey−valueペアを用いて、原素性(key)毎にvalueの値を集計し、原素性毎の(Tn,Rn,Fn)値を求め、(15)式を用いて、原素性fnに対する離散化かつ正則化された原素性重要度un*を計算する。
【0112】
次に、ステップ204で、上記ステップ202で計算された原素性重要度un*に基づいて、un*=0となった原素性fnを不必要と判定し、原素性の集合から排除し、un*≠0となった原素性fnを、縮約素性に含める原素性として選択する。
【0113】
次に、ステップ206で、上記ステップ204で選択した原素性の重要度を離散化した値un*の集合を用いて、計算した重要度un*に基づき、同じ重要度となった原素性を一つの縮約素性として融合し、縮約素性の集合のm番目の縮約素性関数hm(x,y)を(1)式により計算する。
【0114】
次に、ステップ208で、上記ステップ206で計算した縮約素性に、(20)式に示す原素性重要度un*に関する素性φ(x,y)を、M+1番目の縮約素性として追加し、縮約素性関数の集合{h1(x,y),・・・,hM(x,y),φ(x,y)}を出力して、リターンする。
【0115】
以上の処理により、原素性の定義から、縮約素性関数の定義が自動的に構築される。縮約素性関数の定義とは、原素性関数の定義からどのようにして縮約素性を構成するかの情報全てを意味し、縮約素性の個数、各縮約素性を構成する原素性集合Smの定義、及び各縮約素性(対応する原素性)の重要度um*となる。
【0116】
以上説明したように、本実施の形態のモデル構築装置によれば、原素性がベースモデルの最尤出力に与える影響に基づいて、原素性毎の重要度を計算し、この重要度に基づいて選択された原素性を融合して縮約素性を生成するため、正解データを用いて教師あり学習する際に一般的に用いる素性集合よりもコンパクトかつ高精度の縮約素性集合を生成することができる。これにより、教師あり学習時に、過適合の起こる可能性を大幅に削減することができる。
【0117】
また、構築するモデルとして線形分類器を用いる場合には、パラメータ数は素性数と一致するため、パラメータ数も大幅に削減することができ、結果として必要な主記憶(メモリ)量も大幅に削減することができる。更に、メモリ量が削減できるということは、実行速度も向上可能である。
【0118】
また、大規模未解析データ上でしか観測されない素性を間接的に利用することが可能となり、汎化性能も大幅に向上させることができる。
【0119】
このように、一般的には、トレードオフの関係にある、速度−精度や、速度−メモリ量といった要素を同時に向上させることができる。
【0120】
実際に、自然言語処理分野の固有表現抽出及び係り受け解析に本実施の形態のモデル構築装置を適用した場合の効果を図10及び図11に示す。
また、本発明は、自然言語処理やバイオインフォマティクスの研究分野の分類問題に属する問題で教師あり学習を行うような設定で特に高い効果が得られることを意図して考案された発明である。具体的な利用例として、文書を分類する文書分類問題、文(文書)に対して言語的な構造を解析する問題、DNA 塩基配列に遺伝子領域とアミノ酸対応を示すラベルを付与する問題、たんぱく質の2次構造予測問題等が考えられる(図12及び図13)。
【0121】
また、上述のモデル構築装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、WWWシステムを利用している場合であれば、ホームページ提供環境(あるいは表示環境)も含むものとする。
【0122】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【実施例】
【0123】
本発明を自然言語処理分野での文書分類問題に適用した実施例について説明する。
【0124】
まず、計算機による自動文書分類システムを想定する。自動文書分類システムでは、入力が文書、出力が文書に付与すべきクラスとなる。出力である「文書に付与すべきクラス」とは、例えば、カテゴリへの分類問題を想定すると、書籍の体系のように「科学」「経済」「政治」「スポーツ」といったものがクラスとなる。また、スパム分類のような文書分類問題を想定すると、出力クラスは、「スパム文書」か「通常の文書」の二クラスになる。それ以外にも、任意の商品に対するアンケートからの評判分析をするような文書分類問題を想定する場合には、例えば、出力クラスは5 段階の「非常に良い」「良い」「普通」「悪い」「非常に悪い」のようなものになる。図14に典型的な自動文書分類システムの例を示す。
【0125】
次に、このような文書分類システムを構築する方法について述べる。近年では、このような問題は正解データを準備し、そこから教師あり学習により分類モデルを構築する方法が主流である。このとき、正解データとは、構築したい自動文書分類システムの入力と出力とのペアに相当するデータである。教師あり学習とは、この正解データから、演繹的に自動分類モデルを学習する方法である。
【0126】
次に、文書分類問題を教師あり学習によりモデル構築する際に用いる素性関数について述べる。文書分類問題の例では、文書中に出現する単語を原素性として用いる方法が一般的である。これは、文書を構成する要素が単語であること、及びそれぞれの単語が問題を説明する大きな要素となるからである。ただし、この場合、原素性の数は、単語数となるため、例えば、数万や数百万といった非常に大きな数となる。ここで、単語が{F1,・・・,FN}とN個存在する場合、n番目の素性関数、例えば、下記(24)式に示すようなものが考えられる。
【0127】
【数16】
【0128】
また、下記(25)式に示すように、単純に単語が出現したか否かを0と1とで表現する二値素性関数としてもよい。
【0129】
【数17】
【0130】
ここでは、この素性関数を例として以下の説明を述べる。
【0131】
文書分類システムとしては、入力としてある文書xが与えられた場合に、推定した出力クラスyを選択する。ここでは、自動文書分類システムのモデルとして、(2)式で示した線形分類モデルを用いる。つまり、定義した素性関数及びその重みの線形和が最も大きくなるクラスが出力として選択される。
【0132】
線形モデルを教師あり学習により構築することは、線形モデルのモデルパラメータであるwnの値を決定することに相当する。これには、正解データを利用する教師あり学習により値を決定する。また、学習法としては、例えば、確率モデル(対数線形モデル)による尤度最大化や、線形モデルによるマージン最大化に基づくモデルパラメータ推定法を用いる。
【0133】
学習が終わり、モデルパラメータが決定したあと、縮約素性関数の定義を生成する。文書分類で、素性に単語を利用している場合には、単語のクラスタリングをすることに近い処理になる。つまり、重要度が同じぐらいになる単語を一つに融合する処理である。図14及び15に原素性関数と縮約素性関数とを用いた際の処理の違いを示す。
【0134】
最後に、生成された縮約素性関数定義に従って素性関数を生成し、それを用いて通常の教師あり学習アルゴリズムを用いてモデルパラメータを再推定する。
【符号の説明】
【0135】
10 モデル構築装置
12 ベースモデル構築部
14 縮約素性関数集合生成部
16 モデル再構築部
20 正解データ
22 ベースモデル
24 未解析データ
26 縮約素性関数集合定義
28 最終モデル
141 原素性重要度計算部
142 原素性選択部
143 原素性融合部
144 原素性重要度追加部
【特許請求の範囲】
【請求項1】
入力に対する正解が既知の正解データから学習して構築されたベースモデルに、入力に対する正解が未知の複数の未解析データを入力した際の該ベースモデルの最尤出力に対して、前記複数の未解析データから抽出された該未解決データの特徴を表す複数の原素性各々が与える影響を示す重要度を、前記複数の原素性各々について計算する計算手段と、
前記計算手段により計算された複数の原素性各々の重要度に基づいて、前記複数の未解析データから抽出された複数の原素性から、前記ベースモデルの最尤出力に対して影響を与える原素性を選択する選択手段と、
前記原素性各々の重要度に基づいて、前記選択手段により選択された原素性の集合から、1つ以上の原素性をまとめた縮約素性の集合を生成する生成手段と、
を含む縮約素性生成装置。
【請求項2】
前記計算手段は、前記複数の未解析データを複数の部分集合に分割し、分割した複数の部分集合毎に前記重要度を計算するためのパラメータを算出し、該部分集合各々から抽出された複数の原素性各々と前記パラメータとのペアを生成し、前記ペアに基づいて、前記原素性毎に前記パラメータの値を集計して求めて、前記重要度を計算する請求項1記載の縮約素性生成装置。
【請求項3】
前記生成手段は、前記縮約素性各々に含まれる原素性の重要度に関する素性を生成し、前記縮約素性の集合に追加する請求項1または請求項2記載の縮約素性生成装置。
【請求項4】
請求項1〜請求項3のいずれか1項記載の縮約素性生成装置と、
前記正解データから学習して前記ベースモデルを構築する構築手段と、
前記縮約素性生成装置により生成された縮約素性の集合から学習して最終モデルを再構築する再構築手段と、
を含むモデル構築装置。
【請求項5】
計算手段と、選択手段と、生成手段とを含む縮約素性生成装置における縮約素性生成方法であって、
前記計算手段は、入力に対する正解が既知の正解データから学習して構築されたベースモデルに、入力に対する正解が未知の複数の未解析データを入力した際の該ベースモデルの最尤出力に対して、前記複数の未解析データから抽出された該未解決データの特徴を表す複数の原素性各々が与える影響を示す重要度を、前記複数の原素性各々について計算し、
前記選択手段は、前記計算手段により計算された複数の原素性各々の重要度に基づいて、前記複数の未解析データから抽出された複数の原素性から、前記ベースモデルの最尤出力に対して影響を与える原素性を選択し、
前記生成手段は、前記原素性各々の重要度に基づいて、前記選択手段により選択された原素性の集合から、1つ以上の原素性をまとめた縮約素性の集合を生成する
縮約素性生成方法。
【請求項6】
請求項1〜請求項3のいずれか1項記載の縮約素性生成装置と、構築手段と、再構築手段とを含むモデル構築装置におけるモデル構築方法であって、
前記構築手段は、入力に対する正解が既知の正解データから学習してベースモデルを構築し、
前記縮約素性生成装置は、前記縮約素性の集合を生成し、
前記再構築手段は、前記縮約素性生成装置により生成された縮約素性の集合から学習して最終モデルを再構築する
モデル構築方法。
【請求項7】
コンピュータを、請求項1〜請求項3のいずれか1項記載の縮約素性生成装置を構成する各手段として機能させるための縮約素性生成プログラム。
【請求項1】
入力に対する正解が既知の正解データから学習して構築されたベースモデルに、入力に対する正解が未知の複数の未解析データを入力した際の該ベースモデルの最尤出力に対して、前記複数の未解析データから抽出された該未解決データの特徴を表す複数の原素性各々が与える影響を示す重要度を、前記複数の原素性各々について計算する計算手段と、
前記計算手段により計算された複数の原素性各々の重要度に基づいて、前記複数の未解析データから抽出された複数の原素性から、前記ベースモデルの最尤出力に対して影響を与える原素性を選択する選択手段と、
前記原素性各々の重要度に基づいて、前記選択手段により選択された原素性の集合から、1つ以上の原素性をまとめた縮約素性の集合を生成する生成手段と、
を含む縮約素性生成装置。
【請求項2】
前記計算手段は、前記複数の未解析データを複数の部分集合に分割し、分割した複数の部分集合毎に前記重要度を計算するためのパラメータを算出し、該部分集合各々から抽出された複数の原素性各々と前記パラメータとのペアを生成し、前記ペアに基づいて、前記原素性毎に前記パラメータの値を集計して求めて、前記重要度を計算する請求項1記載の縮約素性生成装置。
【請求項3】
前記生成手段は、前記縮約素性各々に含まれる原素性の重要度に関する素性を生成し、前記縮約素性の集合に追加する請求項1または請求項2記載の縮約素性生成装置。
【請求項4】
請求項1〜請求項3のいずれか1項記載の縮約素性生成装置と、
前記正解データから学習して前記ベースモデルを構築する構築手段と、
前記縮約素性生成装置により生成された縮約素性の集合から学習して最終モデルを再構築する再構築手段と、
を含むモデル構築装置。
【請求項5】
計算手段と、選択手段と、生成手段とを含む縮約素性生成装置における縮約素性生成方法であって、
前記計算手段は、入力に対する正解が既知の正解データから学習して構築されたベースモデルに、入力に対する正解が未知の複数の未解析データを入力した際の該ベースモデルの最尤出力に対して、前記複数の未解析データから抽出された該未解決データの特徴を表す複数の原素性各々が与える影響を示す重要度を、前記複数の原素性各々について計算し、
前記選択手段は、前記計算手段により計算された複数の原素性各々の重要度に基づいて、前記複数の未解析データから抽出された複数の原素性から、前記ベースモデルの最尤出力に対して影響を与える原素性を選択し、
前記生成手段は、前記原素性各々の重要度に基づいて、前記選択手段により選択された原素性の集合から、1つ以上の原素性をまとめた縮約素性の集合を生成する
縮約素性生成方法。
【請求項6】
請求項1〜請求項3のいずれか1項記載の縮約素性生成装置と、構築手段と、再構築手段とを含むモデル構築装置におけるモデル構築方法であって、
前記構築手段は、入力に対する正解が既知の正解データから学習してベースモデルを構築し、
前記縮約素性生成装置は、前記縮約素性の集合を生成し、
前記再構築手段は、前記縮約素性生成装置により生成された縮約素性の集合から学習して最終モデルを再構築する
モデル構築方法。
【請求項7】
コンピュータを、請求項1〜請求項3のいずれか1項記載の縮約素性生成装置を構成する各手段として機能させるための縮約素性生成プログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【公開番号】特開2012−256198(P2012−256198A)
【公開日】平成24年12月27日(2012.12.27)
【国際特許分類】
【出願番号】特願2011−128741(P2011−128741)
【出願日】平成23年6月8日(2011.6.8)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
【公開日】平成24年12月27日(2012.12.27)
【国際特許分類】
【出願日】平成23年6月8日(2011.6.8)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
[ Back to top ]