(57)【要約】【課題】推定モデルを構成する重み行列を更新する訓練事例であるレコード数がクラスによって偏っている場合でも重み行列を適切に更新する。【解決手段】推定モデル生成部４は、１つ以上のクラスを対象とし、各対象のクラス（ｃ）につき、対象以外のクラス（ｉ）に関する重みパラメータからなる重みベクトル（ｗｔ（ｉ））と訓練データＤＢの１つのレコード内の各特徴の数からなる特徴ベクトル（ｘ）の内積から、対象のクラス（ｃ）に関する重みパラメータ値からなる重みベクトル（ｗｔ（ｃ））と特徴ベクトルｘの内積を減算して得られる最大損失を最大とするようなレコードを訓練データＤＢ３から選択し、当該選択されたレコードを含む訓練事例集合を用いて重み行列を更新する。【選択図】図１
2014222434.tif 000002
【特許請求の範囲】
【請求項１】
複数の文書に関する複数の特徴ならびに、前記複数の文書を複数のカテゴリに分ける場合の各カテゴリに対応するクラスが特定され、各文書につき該文書における各特徴の数を有するレコードを備える訓練データＤＢが設けられている場合に、１つの特徴と１つのクラスからなる組のそれぞれについての重みパラメータを有する重み行列を訓練データＤＢを用いて更新する重み行列更新装置であって、
１つ以上のクラスを対象とし、各対象のクラス（ｃ）につき、対象以外のクラス（ｉ）に関する重みパラメータからなる重みベクトル（ｗｔ（ｉ））と訓練データＤＢの１つのレコード内の各特徴の数からなる特徴ベクトル（ｘ）の内積から、対象のクラス（ｃ）に関する重みパラメータ値からなる重みベクトル（ｗｔ（ｃ））と特徴ベクトルｘの内積を減算して得られる最大損失を最大とするようなレコードを前記訓練データＤＢから選択する手段と、
当該選択されたレコードを含む訓練事例集合を用いて前記重み行列を更新する手段と
を有することを特徴とする重み行列更新装置。
【請求項２】
前記選択する手段は、
前記最大損失に対し、クラス（ｃ）をクラス（ｉ）と誤る場合の追加コストを加算し、加算後の最大損失を最大とするようなレコードを選択する
ことを特徴とする請求項１記載の重み行列更新装置。
【請求項３】
前記選択する手段は、前記訓練データＤＢにおける１つのクラスについてのレコードを複数のブロックに分割し、各ブロックにおける最大損失を比較することで、当該クラスについて選択すべきレコードを検出する
ことを特徴とする請求項１または２記載の重み行列更新装置。
【請求項４】
複数の文書に関する複数の特徴ならびに、前記複数の文書を複数のカテゴリに分ける場合の各カテゴリに対応するクラスが特定され、各文書につき該文書における各特徴の数を有するレコードを備える訓練データＤＢが設けられている場合に、１つの特徴と１つのクラスからなる組のそれぞれについての重みパラメータを有する重み行列を訓練データＤＢを用いて更新する重み行列更新装置の動作方法であって、
前記重み行列更新装置が、１つ以上のクラスを対象とし、各対象のクラス（ｃ）につき、対象以外のクラス（ｉ）に関する重みパラメータからなる重みベクトル（ｗｔ（ｉ））と訓練データＤＢの１つのレコード内の各特徴の数からなる特徴ベクトル（ｘ）の内積から、対象のクラス（ｃ）に関する重みパラメータ値からなる重みベクトル（ｗｔ（ｃ））と特徴ベクトルｘの内積を減算して得られる最大損失を最大とするようなレコードを前記訓練データＤＢから選択し、
前記重み行列更新装置が、当該選択されたレコードを含む訓練事例集合を用いて前記重み行列を更新する
ことを特徴とする重み行列更新装置の動作方法。
【請求項５】
前記重み行列更新装置は、
前記最大損失に対し、クラス（ｃ）をクラス（ｉ）と誤る場合の追加コストを加算し、加算後の最大損失を最大とするようなレコードを選択する
ことを特徴とする請求項４記載の重み行列更新装置の動作方法。
【請求項６】
前記重み行列更新装置は、前記訓練データＤＢにおける１つのクラスについてのレコードを複数のブロックに分割し、各ブロックにおける最大損失を比較することで、当該クラスについて選択すべきレコードを検出する
ことを特徴とする請求項４または５記載の重み行列更新装置の動作方法。
【請求項７】
請求項１ないし３のいずれかに記載の重み行列更新装置としてコンピュータを機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、重み行列更新装置、その動作方法およびコンピュータプログラムに関するものである。
【背景技術】
【０００２】
テキスト情報を持つ文書を予め定められた複数のカテゴリの中からひとつのカテゴリに分類する場合、予め一定量の文書に対して人手によりカテゴリラベルを付与し、教師あり機械学習の枠組みを用いて推定モデルを学習することで、マルチクラス分類の推定モデルによって未知の文書に対してカテゴリ予測が可能である。この際、テキストに出現する単語頻度を特徴として利用し、たとえば非特許文献１の方法を利用するができる。以降、本稿においてはカテゴリとクラスを同義で用いる。
【０００３】
マルチクラス分類の枠組みでモデルを学習する場合、しばしばクラスの訓練事例数の偏りが発生し、訓練事例数が少ないクラスに比べて訓練事例数が多いクラスに対する損失が大きく算出されてしまう。このため、あるクラスの事例に対して、訓練事例数が多いクラスと予測される誤りが発生するモデルを生成する問題があった。これにより、訓練事例数に偏りがある場合には適切に推定モデルを構築することができず、予測精度が低下する課題があった。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Crammer, K., Dekel, O., Keshet, J., Shalev-Shwartz, S. and Singer,Y., "Online Passive-Aggressive Algorithm", Journal of Machine Learning, Vol.7, pp.551-585, 2006.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、上記の課題に鑑みてなされたものであり、その目的とするところは、推定モデルを構成する重み行列を更新する訓練事例であるレコード数がクラスによって偏っている場合でも重み行列を適切に更新できる重み行列更新装置、その動作方法およびコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【０００６】
上記の課題を解決するために、第１の本発明は、複数の文書に関する複数の特徴ならびに、前記複数の文書を複数のカテゴリに分ける場合の各カテゴリに対応するクラスが特定され、各文書につき該文書における各特徴の数を有するレコードを備える訓練データＤＢが設けられている場合に、１つの特徴と１つのクラスからなる組のそれぞれについての重みパラメータを有する重み行列を訓練データＤＢを用いて更新する重み行列更新装置であって、１つ以上のクラスを対象とし、各対象のクラス（ｃ）につき、対象以外のクラス（ｉ）に関する重みパラメータからなる重みベクトル（ｗｔ（ｉ））と訓練データＤＢの１つのレコード内の各特徴の数からなる特徴ベクトル（ｘ）の内積から、対象のクラス（ｃ）に関する重みパラメータ値からなる重みベクトル（ｗｔ（ｃ））と特徴ベクトルｘの内積を減算して得られる最大損失を最大とするようなレコードを前記訓練データＤＢから選択する手段と、当該選択されたレコードを含む訓練事例集合を用いて前記重み行列を更新する手段とを有することを特徴とする。
【０００７】
例えば、前記選択する手段は、前記最大損失に対し、クラス（ｃ）をクラス（ｉ）と誤る場合の追加コストを加算し、加算後の最大損失を最大とするようなレコードを選択する。
【０００８】
例えば、前記選択する手段は、前記訓練データＤＢにおける１つのクラスについてのレコードを複数のブロックに分割し、各ブロックにおける最大損失を比較することで、当該クラスについて選択すべきレコードを検出する。
【０００９】
例えば、前記選択する手段は、前記最大損失が上位からｋ（ｋは予め設定されたレコード数)番目までのレコードを選択する。
【００１０】
第２の本発明は、複数の文書に関する複数の特徴ならびに、前記複数の文書を複数のカテゴリに分ける場合の各カテゴリに対応するクラスが特定され、各文書につき該文書における各特徴の数を有するレコードを備える訓練データＤＢが設けられている場合に、１つの特徴と１つのクラスからなる組のそれぞれについての重みパラメータを有する重み行列を訓練データＤＢを用いて更新する重み行列更新装置の動作方法であって、前記重み行列更新装置が、１つ以上のクラスを対象とし、各対象のクラス（ｃ）につき、対象以外のクラス（ｉ）に関する重みパラメータからなる重みベクトル（ｗｔ（ｉ））と訓練データＤＢの１つのレコード内の各特徴の数からなる特徴ベクトル（ｘ）の内積から、対象のクラス（ｃ）に関する重みパラメータ値からなる重みベクトル（ｗｔ（ｃ））と特徴ベクトルｘの内積を減算して得られる最大損失を最大とするようなレコードを前記訓練データＤＢから選択し、前記重み行列更新装置が、当該選択されたレコードを含む訓練事例集合を用いて前記重み行列を更新することを特徴とする。
【００１１】
例えば、前記重み行列更新装置は、前記最大損失に対し、クラス（ｃ）をクラス（ｉ）と誤る場合の追加コストを加算し、加算後の最大損失を最大とするようなレコードを選択する。
【００１２】
例えば、前記重み行列更新装置は、前記訓練データＤＢにおける１つのクラスについてのレコードを複数のブロックに分割し、各ブロックにおける最大損失を比較することで、当該クラスについて選択すべきレコードを検出する。
【発明の効果】
【００１３】
本発明によれば、推定モデルを構成する重み行列を更新する訓練事例であるレコード数がクラスによって偏っている場合でも重み行列を適切に更新できる。
【図面の簡単な説明】
【００１４】
【図１】本実施の形態に係る重み行列更新装置を用いた推定モデル生成装置の構成を示す。
【図２】ラベル付きテキストＤＢ１のデータ構造の例を示す。
【図３】訓練データＤＢ３のデータ構造の例を示す。
【図４】訓練データ生成部２の処理の流れを示す。
【図５】推定モデルＤＢ５ののデータ構造の例を示す。
【図６】推定モデル生成部４の処理の流れを示す。
【図７】ステップＳ２−２におけるデータ分割と並列処理の概略を示す。
【発明を実施するための形態】
【００１５】
以下、本発明の実施の形態について図面を参照して説明する。
【００１６】
図１に示すように、本実施の形態に係る重み行列更新装置を用いた推定モデル生成装置は、ラベル付きテキストデータベース（以下、データベースをＤＢと略す）１と、訓練データ生成部２と、訓練データＤＢ３と、推定モデル生成部４と、推定モデルＤＢ５とを備える。推定モデル生成部４は、重み行列を更新するものであり、つまり、重み行列更新装置である。
【００１７】
（訓練データ生成部２）
訓練データ生成部２は、ラベル付きテキストＤＢ１を入力とし、訓練データＤＢ３を出力とする。
【００１８】
（ラベル付きテキストＤＢ１）
図２に示すように、ラベル付きテキストＤＢ１は、文書の本文（以下、テキスト情報）に対して、文書ＩＤと、文書のカテゴリを示すカテゴリＩＤなどを付与したレコードを予め格納したＤＢである。
【００１９】
（訓練データＤＢ３）
図３に示すように、訓練データＤＢ３は、複数のレコードを有し、レコードは、事例、訓練事例ともいう。各レコードは、文書の文書ＩＤ、カテゴリＩＤ、特徴ベクトルを含む。ここで文書ＩＤ、カテゴリＩＤは、ラベル付きテキストＤＢ１の文書ＩＤ、カテゴリＩＤに対応する。特徴ベクトルの次元数は語彙異なり数（種類数）である。たとえばx1が東京という単語に対応し、あるレコードにおいてx1の値が2ということは、当該文書のテキスト情報に東京という単語が2つ含まれているということを表している。特徴ベクトルの要素を素性値ともいう。
【００２０】
（訓練データ生成部２）
図４に示すように、
（S1-1）訓練データ生成部２は、ラベル付きテキストＤＢ１から未処理の文書ＩＤを選択する。以下、これをdという。
【００２１】
（S1-2）訓練データ生成部２は、（S1-1）で選択したｄ（文書ＩＤ）に対応する文書のテキスト情報を単語に分割する。テキスト情報の分割には、例えば参考文献１の技術を用いることができる。
【００２２】
訓練データ生成部２は、訓練データＤＢ３に文書ＩＤがdであるレコードがない場合は、その文書ＩＤと、該当のカテゴリＩＤと、全ての素性値を０とした特徴ベクトルを含むレコードを作成する。
【００２３】
訓練データ生成部２は、分割された各単語について、その数を、訓練データＤＢ３の文書ＩＤがdであるレコードの素性値に加算する。
【００２４】
ここで、該当する素性値に加算するとは、例えば「東京」という単語頻度をx1に加算する、というように単語に対応するxkの値に加算するという意味である。
【００２５】
（S1-3）訓練データ生成部２は、ラベル付きテキストＤＢ１に未処理の文書ＩＤがある場合には（S1-1）に戻り、未処理の文書ＩＤがない場合には処理を終了する。
【００２６】
（推定モデル生成部４）
推定モデル生成部４は、訓練データＤＢ３を入力とし、推定モデルＤＢ５を出力する。推定モデル生成部４が行う処理に使用する最大の試行回数Ｔは予め設定されているものとする。
【００２７】
（推定モデルＤＢ５）
図５に示すように、推定モデルＤＢ５は、上記のように複数のクラスと複数の特徴が定義され、よって、クラスと特徴の組がクラス数と特徴の数の積の数だけ定義されている状況において、各組に対する重みパラメータを保持した重み行列である。列数は訓練データＤＢ３に格納された特徴ベクトルと同じ次元数であり、すなわちＭは語彙異なり数（種類数）と一致する。一方、行数はクラス数と一致する。この例では、クラス数を47としている。
【００２８】
図６に示すように、
（S2-1）推定モデル生成部４は、まず、重み行列の全ての重みパラメータを０に初期化し、試行回数を表す変数tを１に初期化する。
【００２９】
Wtの添え字は試行回数を表しており、Wtは、試行回数tにおける重いパラメータを意味している。
【００３０】
ここで重み行列は、各クラスに対してＭ個の重みパラメータを保持しており、
【数１】
2014222434.tif 000003
【００３１】
であり、i行目がクラスiに対する重みパラメータからなる重みベクトルw(i)によって構成されている。ここでw(i)は、重み行列Wのi行目の重みベクトルを表すものとする。
【００３２】
（S2-2）推定モデル生成部４は、重み行列の更新に用いる訓練事例集合（図示せず、ここでは、Ｄ）を空集合として初期化し、訓練データＤＢ３から、現在の重み行列Wtで各クラスの最大損失に対応するレコードを選択する。すなわちクラス数が47の場合には、47個のレコードが選択される。ここでクラスcの最大損失のレコードxt(c)とは、
【数２】
2014222434.tif 000004
【００３３】
によって得られるレコードである。
【００３４】
ここで、「・」は内積を示すものであり、ｍａｘは、それ以降に記載された式の最大値（最大損失）を示すものであり、ａｒｇｍａｘは、それ以降に記載された式（ここでは最大損失）を最大とするような対象（ここでは、訓練データＤＢ３のレコード）を示すものである。
【００３５】
また、X(c)は訓練データＤＢ３のうち、カテゴリＩＤがcに等しいレコードの集合を表す。また、｜C｜は総クラス数を表し、たとえば47カテゴリ分類の場合には、47である。
【数３】
2014222434.tif 000005
【００３６】
は、クラスcをクラスiと誤る場合の追加コストで、予め設定されているものとする。なお、追加コストは、各クラスにつき、等しく0とし、つまり、特に設定しなくてもよい。
【００３７】
推定モデル生成部４は、得られたレコードxt(c)を、訓練事例集合Ｄに加える。
【００３８】
式（２）で計算される損失はクラスcをクラスc以外（ｉ）と誤判別する際の確信度の最大値と、正しい予測の確信度の差と解釈することができる。式（２）においては、クラスcにおいて最大損失を与える訓練データＤＢ３のレコードを選択している。このため、各クラスについて、全レコードと全クラスの組み合わせ分だけ損失を計算し、比較を行う必要がある。
【００３９】
この処理を高速に行うため、たとえばOpenMP（http://openmp.org/wp/を参照）などの並列化ライブラリを利用し、各クラスにおける最大損失の選択を並列に実行することで、並列化が可能である。しかしながら、本実施の形態においてはクラス毎に訓練データＤＢ３のレコードの偏りがあることを想定しており、その場合にはレコード数の多いクラスについては他のクラスに比べて最大損失選択の計算コストが高くなる問題がある。
【００４０】
そこで、図７に示すように、レコード数が多いクラスについては複数のブロックに分割し、各ブロックにおける最大損失の値を比較することで当該クラスにおける最大損失のレコードを検出、つまり効率的に発見するという方法を用いることができる。
【００４１】
本実施の形態においては最大損失レコードのみを選択する方法を記載したが、例えば、同様の方法を用い、最大損失が上位からk(kは予め設定されたレコード数)番目までのレコードを選択するという方法も考えられる。
【００４２】
また本実施の形態においては、全クラスの最大損失のレコードを訓練事例集合Ｄに追加した状態で本ステップを終了する方法を記載している。すなわち｜D｜=｜C｜
(ただし、｜D｜は訓練事例集合Ｄに含まれるレコード数)である。
【００４３】
しかしながら、全クラスの最大損失のレコードを選択する前に、予め定めたクラス数のクラスについて、訓練事例集合Ｄへのレコード追加が終わった段階で本ステップを終了する方法も考えられる。その場合には、たとえば｜D｜に対して閾値判定する方法。前回のイテレーションで処理されなかったクラスが訓練事例集合Ｄに含まれるように処理する方法などが考えられる。
【００４４】
（S2-3）推定モデル生成部４は、（S2-2）で得られた訓練事例集合Ｄ内のレコードを用いて、重み行列Wｔ内の重みパラメータを更新し、Wｔ+1とする。重みパラメータの更新には、例えば、参考文献２の技術を用いることができる。
【００４５】
（S2-4）ｔをｔ＋１とする。  
（S2-5）ｔ≦Ｔである場合には（S2-2）に戻り、そうでない場合には（S2-6）に進む。
【００４６】
（S2-6）推定モデル生成部４は、現在の重み行列Ｗを推定モデルＤＢ５に出力する。
【００４７】
以上のように、本実施の形態により、各クラスにつき最大損失を与える訓練データＤＢ３のレコードを選択し、パラメータ更新に用いることにより、レコード数の偏りによる損失計算の偏りの影響を排除することが可能となり、レコード数の偏りがある場合において、適切に推定モデルを構築することが可能となり、予測精度の低下を防ぐことが可能となる。
【００４８】
つまり、推定モデルを構成する重み行列を更新する訓練事例であるレコード数がクラスによって偏っている場合でも重み行列を適切に更新できる。
【００４９】
参考文献１：Takeshi Fuchi, Shinichiro Takagi: Japanese Morphological Analyzer
using Word Co-occurence - JTAG. COLING-ACL, pp.409-413, 1998.
参考文献２：Crammer, K. and Singer, Y., \Ultraconservative online algorithms
for multiclass problems", Journal of Machine Learning Research, vol.3, pp.951{991,
2003.
なお、重み行列更新装置（推定モデル生成部４）としてコンピュータを機能させるためのコンピュータプログラムは、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのコンピュータ読み取り可能な記録媒体に記録でき、また、インターネットなどの通信網を介して伝送させて、広く流通させることができる。
【符号の説明】
【００５０】
１…ラベル付きテキストＤＢ
２…訓練データ生成部
３…訓練データＤＢ
４…推定モデル生成部
５…推定モデルＤＢ
【図１】
2014222434.tif 000006
【図２】
2014222434.tif 000007
【図３】
2014222434.tif 000008
【図４】
2014222434.tif 000009
【図５】
2014222434.tif 000010
【図６】
2014222434.tif 000011
【図７】
2014222434.tif 000012