(57)【要約】【課題】メモリの使用量を抑制すること。【解決手段】学習装置２０は、正例または負例のラベル付きのテキストを取得する処理と、取得されたテキストに含まれる素性を展開する処理と、テキストに含まれる素性の組合せまたは複数のテキストの間で生成される部分構造データと確信度とが対応付けられたモデルを参照して、展開された素性ごとにモデル内の素性の組合せまたは部分構造データと照合する処理と、ラベルに反する分類が行われた場合、当該テキストに対する分類のエラー回数に応じてモデルの更新に用いる素性のサイズを設定する処理と、設定されたサイズにしたがって展開された素性の組合せまたは部分構造データのうちモデルと一致しない素性の組合せまたは部分構造データをモデルに追加する更新を行う処理とを実行する。【選択図】図９
2018045524.tif 000002
【特許請求の範囲】
【請求項１】
正例または負例のラベル付きのテキストを取得する処理と、
前記取得する処理で取得されたテキストに含まれる素性を展開する処理と、
テキストに含まれる素性の組合せまたは複数のテキストの間で生成される部分構造データと確信度とが対応付けられたモデルを参照して、前記展開する処理で展開された素性ごとに前記モデル内の前記素性の組合せまたは前記部分構造データと照合する処理と、
前記照合する処理により前記ラベルに反する分類が行われた場合、当該テキストに対する分類のエラー回数に応じて前記モデルの更新に用いる素性のサイズを設定する処理と、
前記設定する処理で設定されたサイズにしたがって展開された素性の組合せまたは部分構造データのうち前記モデルと一致しない素性の組合せまたは部分構造データをモデルに追加する更新を行う処理と
をコンピュータに実行させることを特徴とする学習プログラム。
【請求項２】
前記更新を行う処理は、前記設定する処理で設定されたサイズにしたがって展開された素性の組合せまたは部分構造データのうち前記モデルと一致する素性の組合せまたは部分構造データに対応付ける確信度を前記ラベルに基づいて更新することを特徴とする請求項１に記載の学習プログラム。
【請求項３】
前記部分構造データは、配列構造、木構造またはグラフ構造のいずかにより表されるデータであることを特徴とする請求項１または２に記載の学習プログラム。
【請求項４】
前記部分構造データは、前記複数のテキストの間で共通する部分文字列であることを特徴とする請求項３に記載の学習プログラム。
【請求項５】
正例または負例のラベル付きのテキストを取得する処理と、
前記取得する処理で取得されたテキストに含まれる素性を展開する処理と、
テキストに含まれる素性の組合せまたは複数のテキストの間で生成される部分構造データと確信度とが対応付けられたモデルを参照して、前記展開する処理で展開された素性ごとに前記モデル内の前記素性の組合せまたは前記部分構造データと照合する処理と、
前記照合する処理により前記ラベルに反する分類が行われた場合、当該テキストに対する分類のエラー回数に応じて前記モデルの更新に用いる素性のサイズを設定する処理と、
前記設定する処理で設定されたサイズにしたがって展開された素性の組合せまたは部分構造データのうち前記モデルと一致しない素性の組合せまたは部分構造データをモデルに追加する更新を行う処理と
をコンピュータが実行することを特徴とする学習方法。
【請求項６】
正例または負例のラベル付きのテキストを取得する取得部と、
前記取得部により取得されたテキストに含まれる素性を展開する展開部と、
テキストに含まれる素性の組合せまたは複数のテキストの間で生成される部分構造データと確信度とが対応付けられたモデルを参照して、前記展開部により展開された素性ごとに前記モデル内の前記素性の組合せまたは前記部分構造データと照合する照合部と、
前記照合部により前記ラベルに反する分類が行われた場合、当該テキストに対する分類のエラー回数に応じて前記モデルの更新に用いる素性のサイズを設定する設定部と、
前記設定部により設定されたサイズにしたがって展開された素性の組合せまたは部分構造データのうち前記モデルと一致しない素性の組合せまたは部分構造データをモデルに追加する更新を行う更新部と
を有することを特徴とする学習装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、学習プログラム、学習方法及び学習装置に関する。
【背景技術】
【０００２】
自然言語処理には、一例として、ｐｅｒｃｅｐｔｒｏｎ、ＳＶＭｓ（Support  Vector  Machines）、ＰＡ（Passive-Aggressive）やＡＲＯＷ（Adaptive  Regularization  of  Weight  Vectors）などいった各種の機械学習が用いられる。
【０００３】
例えば、テキストデータを扱かう場合、テキストから単語を切り出して、単語をベクトルの各次元に対応付けて、テキスト内での各単語の出現頻度を対応する次元の値とすることにより、ベクトルが作成されることがある。この例であれば、単語は素性と呼ばれ、ベクトルは素性ベクトルと呼ばれる。
【０００４】
自然言語処理では、素性の組合せが精度に影響を与える場合がある。しかし、自然言語処理の素性の種類は数万規模になることもあり、素性の組合せを考慮するとその種類数はさらに膨大なものとなる。また、自然言語処理では、文字列は配列で表現できる。また、係り受け解析されたテキストは解析木として表現されるため、ベクトルで表現されたデータを扱かう学習手法に加えて、Ｓｔｒｉｎｇ（配列）、Ｔｒｅｅ（木）、Ｇｒａｐｈ（グラフ）など、構造化データを扱う学習手法がある。
【０００５】
素性の組合せの学習並びにＳｔｒｉｎｇ、Ｔｒｅｅ、Ｇｒａｐｈを対象とする学習手法の一つとして、Ｋｅｒｎｅｌ法という手法がある。Ｋｅｒｎｅｌ法では、データ間の類似度を計算した後に、学習が行われる。
【０００６】
Ｋｅｒｎａｌ法では、暗黙的に素性を展開しながら、学習事例間の内積を計算することで、素性の組合せの学習やＳｔｒｉｎｇ、Ｔｒｅｅ、Ｇｒａｐｈなどの半構造データの扱いにおいて、効率的な計算を実現することができる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Koby  Crammer,  Ofer  Dekel,  Joseph  Keshet,  Shai  Shalev-Shwartz,  and  Yoram  Singer著  「Online  passive-aggressive  algorithms.  Journal  of  Machine  Learning  Research」  7:551｛585,  2006.
【非特許文献２】Jun  Suzuki,  Hideki  Isozaki,  and  Eisaku  Maeda著  「Convolution  kernels  with  feature  selection  for  natural  language  processing  tasks.  In  Proceedings  of  the  42nd  Annual  Meeting  of  the  Association  for  Computational  Linguistics」  21-26  July,  2004,  Barcelona,  Spain.,  pages  119｛126,  2004.
【非特許文献３】X.Yan  and  J.Han著  「gspan:Graph-based  substructure  pattern  mining」  2002.
【非特許文献４】Naoki  Yoshinaga  and  Masaru  Kitsuregawa著  「Kernel  slicing:  Scalable  online  training  with  conjunctive  features.  In  COLING  2010,  23rd  International  Conference  on  Computational  Linguistics,  Proceedings  of  the  Conference」  23-27  August  2010,  Beijing,  China,  pages  1245｛1253,  2010.
【非特許文献５】Mohammed  Zaki著  「Efficiently  mining  frequent  trees  in  a  forest」  In  Proc.  of  SIGKDD'02,  pages  71｛80,  2002.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記の技術では、処理速度の低下やメモリの使用量が増大につながる場合がある。
【０００９】
Ｋｅｒｎａｌ法を利用する場合は、学習事例との内積を取る必要があり、学習データ数が増えると処理速度が低下する。また、ＡＲＯＷを始めとするConfidence-Weighted-Learningでは、各素性の確信度も学習する必要があるので、ｐｅｒｃｅｐｔｒｏｎやＰＡのように、カーネル関数を用いて各学習事例との内積を取る方法で暗黙的に素性を拡張する手法を用いることができない。
【００１０】
これらのことから、素性の組合せを事前に陽に展開することが考えられる。しかし、組合せ数が増大し、メモリ消費量が増大する。例えば、素性の確信度を学習するConfidence-Weighted-Learningに、内積計算に基づくＫｅｒｎｅｌ法を組み込む代わりに、事前に、全ての素性を陽に展開する対応も方法論の一つとして考えられる。ところが、事前に全ての素性を陽に展開すると、下記の通り、膨大な数の素性の展開が発生するので、メモリの使用量が増大する。例えば、ｎ種類の素性のｄ種類の素性の組合せまで考慮する場合、下記の式（１）に示す通りの素性が事前に展開される必要がある。また、上記の半構造データのうちＳｔｒｉｎｇの場合を例に挙げると、長さｎのＳｔｒｉｎｇで連続するｋ文字までを全て列挙するとなると、下記の式（２）に示す数の部分文字列の列挙が必要となる。
【００１１】
【数１】
2018045524.tif 000003
【数２】
2018045524.tif 000004
【００１２】
１つの側面では、本発明は、メモリの使用量を抑制することができる学習プログラム、学習方法及び学習装置を提供することを目的とする。
【課題を解決するための手段】
【００１３】
一態様では、学習プログラムは、正例または負例のラベル付きのテキストを取得する処理と、前記取得する処理で取得されたテキストに含まれる素性を展開する処理と、テキストに含まれる素性の組合せまたは複数のテキストの間で生成される部分構造データと確信度とが対応付けられたモデルを参照して、前記展開する処理で展開された素性ごとに前記モデル内の前記素性の組合せまたは前記部分構造データと照合する処理と、前記照合する処理により前記ラベルに反する分類が行われた場合、当該テキストに対する分類のエラー回数に応じて前記モデルの更新に用いる素性のサイズを設定する処理と、前記設定する処理で設定されたサイズにしたがって展開された素性の組合せまたは部分構造データのうち前記モデルと一致しない素性の組合せまたは部分構造データをモデルに追加する更新を行う処理とをコンピュータに実行させる。
【発明の効果】
【００１４】
メモリの使用量を抑制することができる。
【図面の簡単な説明】
【００１５】
【図１】図１は、実施例１に係る学習装置の機能的構成を示すブロック図である。
【図２】図２は、素性の動的展開に基づくｐｅｒｃｅｐｔｒｏｎの擬似アルゴリズムの一例を示す図である。
【図３】図３は、学習データの一例を示す図である。
【図４】図４は、素性の展開の一例を示す図である。
【図５】図５は、素性の動的展開およびモデルの更新の一例を示す図である。
【図６】図６は、素性の動的展開およびモデルの更新の一例を示す図である。
【図７】図７は、素性の動的展開およびモデルの更新の一例を示す図である。
【図８】図８は、実施例１に係る学習処理の手順を示すフローチャートである。
【図９】図９は、実施例２に係る学習装置の機能的構成を示すブロック図である。
【図１０】図１０は、エラーに基づくｐｅｒｃｅｐｔｒｏｎの擬似アルゴリズムの一例を示す図である。
【図１１】図１１は、学習サンプルとモデルの照合の一例を示す図である。
【図１２】図１２は、学習サンプルとモデルの照合の一例を示す図である。
【図１３】図１３は、学習サンプルとモデルの照合の一例を示す図である。
【図１４】図１４は、学習サンプルとモデルの照合の一例を示す図である。
【図１５】図１５は、学習サンプルとモデルの照合の一例を示す図である。
【図１６】図１６は、学習サンプルとモデルの照合の一例を示す図である。
【図１７】図１７は、学習サンプルとモデルの照合の一例を示す図である。
【図１８】図１８は、学習サンプルとモデルの照合の一例を示す図である。
【図１９】図１９は、実施例２に係る学習処理の手順を示すフローチャートである。
【図２０】図２０は、素性の動的展開に基づくＡＲＯＷの擬似アルゴリズムの一例を示す図である。
【図２１】図２１は、モデル内の部分構造を用いる照合の一例を示す図である。
【図２２】図２２は、エラーに基づくＡＲＯＷの擬似アルゴリズムの一例を示す図である。
【図２３】図２３は、実施例１〜実施例３に係る学習プログラムを実行するコンピュータのハードウェア構成例を示す図である。
【発明を実施するための形態】
【００１６】
以下に添付図面を参照して本願に係る学習プログラム、学習方法及び学習装置について説明する。なお、この実施例は開示の技術を限定するものではない。そして、各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【実施例１】
【００１７】
図１は、実施例１に係る学習装置の機能的構成を示すブロック図である。図１に示す学習装置１０は、自然言語処理における素性を学習する学習処理を行うものであり、一側面として、各素性の確信度を学習に用いるｐｅｒｃｅｐｔｒｏｎにおいて、Ｋｅｒｎｅｌ法を使わずに、素性の組合せを考慮する場合にメモリの使用量が増大するのを抑制する。
【００１８】
すなわち、学習装置１０は、事前に素性を展開するのではなく、動的に展開しながら、学習する方法を用いる。図２は、素性の動的展開に基づくｐｅｒｃｅｐｔｒｏｎの擬似アルゴリズムの一例を示す図である。図２に示す「ｘ」は、文字列を指し、φ（ｘ）は、文字列ｘに含まれる素性の組合せまたは文字列ｘの部分文字列、例えば２つの構造データ間で共通する部分文字列を取り出してベクトルにマッピングする関数を指す。図２に示す「ｗ」は、重みベクトルを指し、例えば、ｄ次元のベクトル空間が対象である場合、ｔラウンド目のｄ次元の重みベクトルは「ｗｔ」で表される。なお、ここでは、書面の制約上、「ｗ」の表記に斜体でない表記を用いるが、実際には、重みベクトルに関する「ｗ」は斜体で表記される。
【００１９】
図２に示すように、学習装置１０は、（１）分類時は、モデルに含まれる素性だけが必要である点、（２）更新時は、誤った事例から生成される素性だけが必要である点の２点に着目し、動的に素性を展開しながら、学習データから重みベクトルを学習する。すなわち、学習装置１０は、分類時には、モデルに含まれる素性だけを展開し、モデルとのスコアを計算し、分類が誤っている場合には、誤った事例から生成される素性だけを展開し、モデルを更新する。これにより、全ての素性の組合せや全ての部分構造ではなく、分類に必要な素性の組合せや部分構造だけを展開するだけで学習が可能となり、事前に素性の組合せや全ての部分素性を展開する場合と比較し、メモリの使用量の削減を実現できる。
【００２０】
図１に示す学習装置１０は、上記の学習処理を実現するコンピュータである。
【００２１】
一実施形態として、学習装置１０は、パッケージソフトウェアやオンラインソフトウェアとして上記の学習処理を実行する学習プログラムを所望のコンピュータにインストールさせることによって実装できる。例えば、上記の学習プログラムを情報処理装置に実行させることにより、情報処理装置を学習装置１０として機能させることができる。ここで言う情報処理装置には、デスクトップ型またはノート型のパーソナルコンピュータの他、スマートフォン、携帯電話機やＰＨＳ（Personal  Handyphone  System）などの移動体通信端末、さらには、ＰＤＡ（Personal  Digital  Assistants）などのスレート端末などがその範疇に含まれる。また、ユーザが使用する端末装置をクライアントとし、当該クライアントに上記の学習処理に関するサービスを提供するサーバ装置として実装することもできる。例えば、学習装置１０は、正例または負例のラベル付きの学習データ、または、学習データをネットワークもしくは記憶メディアを介して呼び出すことができる識別情報を入力とし、当該学習データに対する上記の学習処理の実行結果、すなわち分類器が用いるモデルを出力する学習サービスを提供するサーバ装置として実装される。この場合、学習装置１０は、Ｗｅｂサーバとして実装することとしてもよいし、アウトソーシングによって上記の学習処理に関するサービスを提供するクラウドとして実装することとしてもかまわない。
【００２２】
図１に示すように、学習装置１０は、取得部１１と、展開部１２と、モデル記憶部１３と、照合部１４と、更新部１５とを有する。なお、学習装置１０は、図１に示した機能部以外にも既知のコンピュータが有する各種の機能部、例えば各種の入力デバイスや音声出力デバイスなどの機能部を有することとしてもかまわない。
【００２３】
取得部１１は、正例または負例のラベル付きの学習データを取得する処理部である。
【００２４】
一実施形態として、取得部１１は、ハードディスクや光ディスクなどの補助記憶装置またはメモリカードやＵＳＢ（Universal  Serial  Bus）メモリなどのリムーバブルメディアに保存された学習データを読み出すことにより取得することもできる。この他、取得部１１は、外部装置からネットワークを介して受信することによって学習データを取得することもできる。
【００２５】
ここで、以下では、一例として、図３に示す学習データが取得される場合を想定し、入力されるテキストをスパムまたは通常のいずれかのクラスに分類するのに用いるモデルをｐｅｒｃｅｐｔｒｏｎという手法にしたがって学習する場合を想定する。なお、ここでは、あくまで一例として、素性の組合せを学習する場合を例示するが、後述する通り、Ｓｔｒｉｎｇ、Ｔｒｅｅ、Ｇｒａｐｈなどの半構造データの学習を行う場合にも上記の学習処理を適用できる旨をここで予め付言しておく。
【００２６】
図３は、学習データの一例を示す図である。図３の上段に示す通り、取得部１１は、「スパム」または「通常」のラベルが付与されたテキストを学習データとして取得する。このように学習データが取得されると、取得部１１は、一例として、テキストに形態素解析を実行することにより形態素に分解し、テキストに含まれる名詞を抽出する。これにより、図３の下段に示す通り、ラベルと素性の対応関係が抽出される。例えば、１行目のテキスト「簡単な速度改善を考えてください」の場合、素性として「簡単」、「速度」、「改善」が抽出される。また、２行目のテキスト「売り上げは１００万円以上」の場合、素性として「売り上げ」、「１００万円」、「以上」が抽出される。また、３行目のテキスト「簡単な売り上げ１００万円改善」の場合、素性として「簡単」、「売り上げ」、「１００万円」、「改善」が抽出される。
【００２７】
この図３の下段に示す例では、ラベル「スパム」が付与されたテキストに含まれる単語は、全てラベル「通常」が付与されたテキストに含まれる単語にも含まれるので、両者の分類が困難である。
【００２８】
これに対し、既存の技術の場合、図４に示すように、素性の組合せを事前に展開して学習する対応が取られる。図４は、素性の展開の一例を示す図である。図４には、図３に示された単語のうち２つを組み合わせる場合が示されている。図４に示す通り、ラベルごとに２つの単語が組み合わせられた場合、素性の組合せの総数は、図３に示した１０個の素性から２２個まで増加する。このように、素性の組合せを事前に展開すると、メモリの使用量は増大する。以下では、メモリの使用量の増大を抑制するために、いかにして動的な素性の展開を実現するかについて説明を行う。
【００２９】
展開部１２は、学習データに含まれる素性を動的に展開する処理部である。
【００３０】
一実施形態として、展開部１２は、取得部１１により取得された学習データＴのうち未処理の学習データｔを１つ選択する。続いて、展開部１２は、先に選択された学習データｔの素性を指定のアルゴリズムにしたがって動的に展開する。例えば、展開する素性の組合せのサイズとして「２」が設定される場合、学習データｔから２単語の組合せまで抽出される。すなわち、展開部１２は、学習データｔに含まれる単語を展開する共に、各単語が２つ組み合わせられた組合せを展開する。以下では、展開する素性の組合せのサイズのことを「素性サイズ」と記載する場合がある。
【００３１】
図５〜図７は、素性の動的展開およびモデルの更新の一例を示す図である。図５には、図３に示した３つの学習データのうち１行目の学習データが処理される場合を示し、図６には、２行目の学習データが処理される場合を示し、図７には、３行目の学習データが処理される場合を示し、１行目の学習データ、２行目の学習データ、３行目の学習データの順に処理が実行される場合を想定する。また、図５〜図７には、各学習データに付与されたラベルにしがって学習データにスパム「１」または通常「−１」のスコアが付与される。
【００３２】
例えば、図５のＳ５１に示す通り、図３に示した学習データの素性「簡単」、「速度」、「改善」が展開される場合、「簡単」、「速度」、「改善」、「簡単＆速度」、「簡単＆改善」、「速度＆改善」の６つの素性の組合せが展開される。また、図６のＳ６１に示す通り、図３に示した学習データの素性「売り上げ」、「１００万円」、「以上」が展開される場合、「売り上げ」、「１００万円」、「以上」、「売り上げ＆１００万円」、「売り上げ＆以上」、「１００万円＆以上」の６つの素性の組合せが展開される。また、図７のＳ７１に示す通り、図３に示した学習データの素性「簡単」、「売り上げ」、「１００万円」、「改善」が展開される場合、「簡単」、「売り上げ」、「１００万円」、「改善」、「簡単＆売り上げ」、「簡単＆１００万円」、「簡単＆改善」、「売り上げ＆１００万円」、「売り上げ＆改善」、「１００万円＆改善」の１０通りの素性の組合せが展開される。
【００３３】
照合部１４は、モデル記憶部１３に記憶されたモデルを参照して、展開部１２により展開された素性ごとにモデル内の素性の組合せと照合する処理部である。
【００３４】
ここで、モデル記憶部１３には、テキストに含まれる素性の組合せと確信度とが対応付けられたモデルが記憶される。このモデルは、学習処理が開始された段階には空の状態であり、後述の更新部１５により素性の組合せやその確信度が新規登録されたり、あるいは素性の組合せに対応付けられた確信度が更新される。ここで言う「確信度」は、スパムである確からしさを指すので、以下では、あくまで一側面として「スパムスコア」と記載する。
【００３５】
一実施形態として、照合部１４は、展開部１２により展開された学習データｔの素性の組合せと、モデル記憶部１３に記憶されたモデルに含まれる素性の組合せとを照合する。例えば、照合部１４は、展開部１２により展開された素性の組合せのうち１つ選択する。その上で、照合部１４は、上記のモデルに含まれる素性の組合せの中に、先に選択された学習データｔの素性の組合せと一致するものが存在するか否かを判定する。このとき、照合部１４は、互いが一致する素性の組合せが存在する場合、当該モデルの素性の組合せに対応付けられたスパムスコアを、図示しない内部メモリのワークエリアに保存されたスパムスコアの累積値にさらに加算する。このように、照合部１４は、展開部１２により展開された全ての素性の組合せに関し、スパムスコアが合計されるまで、上記の照合を繰り返し実行する。
【００３６】
更新部１５は、モデル記憶部１３に記憶されたモデルを更新する処理部である。
【００３７】
一実施形態として、更新部１５は、照合部１４による処理の結果がラベルに反する場合、すなわち分類が誤りである場合、モデルの更新を実施する。例えば、上述の通り、学習データＴにスパム「１」または通常「−１」のラベルが付与される場合、スパムスコアの累積値の符号がラベルの符号と異なる場合、あるいはスパムスコアの累積値がゼロになる場合、分類が不正解となる。この場合、更新部１５は、展開部１２により展開された素性の組合せのうちモデルと一致しない素性の組合せをモデルへ追加する更新を行うと共に、モデルに含まれる確信度のうち学習データｔから展開された素性の組合せと一致する素性の組合せに対応付けられた確信度をラベルに基づいて更新する。
【００３８】
例えば、図５に示す例の場合、Ｓ５１で展開された６つの素性の組合せ、すなわち「簡単」、「速度」、「改善」、「簡単＆速度」、「簡単＆改善」及び「速度＆改善」がモデルと照合される（Ｓ５２）。この段階では、モデルには素性の組合せの登録がないので、展開部１２により展開された素性の組合せと一致する素性の組合せもモデルに存在せず、スパムスコアの合計もゼロになる。この場合、Ｓ５１で展開された６つの素性の組合せ、すなわち「簡単」、「速度」、「改善」、「簡単＆速度」、「簡単＆改善」及び「速度＆改善」がモデル記憶部１３へ追加される。このとき、素性の各組合せには、当該学習データｔのラベル「負例」に付与されたスパムスコア「−１」が対応付けられる（Ｓ５３）。
【００３９】
さらに、図６に示す例の場合、Ｓ６１で展開された６つの素性の組合せ、すなわち「売り上げ」、「１００万円」、「以上」、「売り上げ＆１００万円」、「売り上げ＆以上」、「１００万円＆以上」がモデルと照合される（Ｓ６２）。この段階では、モデルには素性の組合せの登録があるものの、Ｓ６１で展開された素性の組合せと一致するものがないので、スパムスコアの合計もゼロになる。この場合、Ｓ６１で展開された６つの素性の組合せ、すなわち「売り上げ」、「１００万円」、「以上」、「売り上げ＆１００万円」、「売り上げ＆以上」、「１００万円＆以上」がモデル記憶部１３へ追加される。このとき、素性の各組合せには、当該学習データｔのラベル「負例」に付与されたスパムスコア「−１」が対応付けられる（Ｓ６３）。
【００４０】
さらに、図７に示す例の場合、Ｓ７１で展開された１０通りの素性の組合せ、すなわち「簡単」、「売り上げ」、「１００万円」、「改善」、「簡単＆売り上げ」、「簡単＆１００万円」、「簡単＆改善」、「売り上げ＆１００万円」、「売り上げ＆改善」、「１００万円＆改善」がモデルと照合される（Ｓ７２）。この段階では、図７に示す反転表示のハッチングに対応するモデルの素性の組合せと、Ｓ７１で展開された学習データｔの素性の組合せとが一致する。すなわち、素性の組合せ「簡単」、「改善」、「簡単＆改善」、「売り上げ」、「１００万円」及び「売り上げ＆１００万円」が学習データ及びモデルの間で一致する。
【００４１】
この場合、Ｓ７１で展開された学習データｔの素性の組合せと一致するモデルの素性の組合せに対応付けられたスパムスコアの合計値は「−６」となる。この例では、学習データｔのラベルが正例であり、スパムスコアの合計値の符号「負」と学習データｔのラベルの符号「正」が異なるので、分類は不正解となる。この場合、下記の通り、モデルの更新が実行される（Ｓ７３）。具体的には、モデルに含まれる素性の組合せのうちＳ７１で展開された学習データｔの素性の組合せと一致するものを対象に、モデルに含まれる素性の組合せに対応付けられた現在のスパムスコアに学習データｔのラベル「正例」に付与されたスパムスコア「＋１」が加算される。すなわち、モデル内の素性の組合せ「簡単」、「改善」、「簡単＆改善」、「売り上げ」、「１００万円」及び「売り上げ＆１００万円」にスパムスコア「＋１」が加算される。この結果、素性の組合せ「簡単」、「改善」、「簡単＆改善」、「売り上げ」、「１００万円」及び「売り上げ＆１００万円」に対応付けられたスパムスコアは「０」になる。さらに、Ｓ７１で展開された学習データｔの素性の組合せに含まれる素性の組合せのうちモデルに含まれる素性の組合せと一致しない素性の組合せがモデルに追加される。すなわち、Ｓ７１で展開された１０通りの素性の組合せのうちモデル内の素性の組合せと一致しない素性の組合せ、すなわち「簡単＆売り上げ」、「簡単＆１００万円」、「売り上げ＆改善」、「１００万円＆改善」がモデル記憶部１３へ追加される。このとき、素性の各組合せには、当該学習データｔのラベル「正例」に付与されたスパムスコア「＋１」が対応付けられる。
【００４２】
以上の展開および更新により、図７に示したモデル１３ｅが得られる。この図７に示したモデル１３ｅと図３に示す１行目の学習データと照合した場合、スパムスコアの合計は「−３」となる。また、図７に示したモデル１３ｅと図３に示す２行目の学習データと照合した場合、スパムスコアの合計は「−３」となる。さらに、図７に示したモデル１３ｅと図３に示す３行目の学習データと照合した場合、スパムスコアの合計は「４」となる。このように、図７に示したモデル１３ｅにしたがえば、ラベル通りの分類結果を導出することが可能になる。さらに、図３に示した３つの学習データにおいて２単語の全ての組合せを展開する場合には、２２通りの素性の組合せが求められるのに対し、図５〜図７に示した通り、展開および更新を行うことにより、１６通りの素性の組合せにまでその数を低減できる。したがって、メモリの使用量も抑制できる。
【００４３】
図８は、実施例１に係る学習処理の手順を示すフローチャートである。この学習処理では、入力部等の指示入力により学習が指示された場合に処理を起動したり、あるいは学習データが取得された場合に処理を自動的に起動することができる。
【００４４】
図８に示すように、取得部１１は、学習データＴを取得すると共に、学習の繰り返し回数Ｍの設定を取得する（ステップＳ１０１及びステップＳ１０２）。この繰り返し回数Ｍには、モデルに求める精度に応じて任意の回数を予め設定しておくことができる。なお、ステップＳ１０１及び１０２の処理は、実行される順序が順不同であってよく、並列して実行されることも妨げない。
【００４５】
続いて、取得部１１は、ステップＳ１０１で取得された学習データＴの全てのサンプルに関するステータス、例えばフラグ等を未処理に設定する（ステップＳ１０３）。そして、学習データＴの中に未処理の学習データのサンプルが存在する限り（ステップＳ１０４Ｙｅｓ）、ステップＳ１０５以降の処理を実行する。
【００４６】
すなわち、展開部１２は、ステップＳ１０１で取得された学習データＴのうち未処理の学習データｔを１つ選択する（ステップＳ１０５）。続いて、展開部１２は、ステップＳ１０５で選択された学習データｔの素性を指定のアルゴリズムにしたがって動的に展開する（ステップＳ１０６）。例えば、２単語の組合せまでを抽出する場合、学習データｔに含まれる単語が展開されると共に、各単語が２つ組み合わせられた組合せが展開される。その上で、照合部１４は、展開部１２により展開された学習データｔの素性の組合せと、モデル記憶部１３に記憶されたモデルに含まれる素性の組合せとを照合する（ステップＳ１０７）。
【００４７】
そして、ステップＳ１０７の照合により得られたスパムスコアの合計による学習データｔの分類が誤りである場合（ステップＳ１０８Ｙｅｓ）、更新部１５は、ステップＳ１０６で展開された素性の組合せと一致する素性の組合せがモデルの中に存在するか否かを判定する（ステップＳ１０９）。なお、学習データｔの分類が誤りではない場合（ステップＳ１０８Ｎｏ）、モデルの更新は実行されず、ステップＳ１０４の処理へ移行する。
【００４８】
ここで、ステップＳ１０６で展開された素性の組合せと一致する素性の組合せがモデルの中に存在する場合（ステップＳ１０９Ｙｅｓ）、更新部１５は、モデルに含まれる素性の組合せのうちステップＳ１０６で展開された学習データｔの素性の組合せと一致するものを対象に、モデルに含まれる素性の組合せに対応付けられた現在のスパムスコアに学習データｔのラベルに付与されたスパムスコアを加算する更新を行う（ステップＳ１１０）。なお、ステップＳ１０９Ｎｏの場合、ステップＳ１１０の処理はスキップされる。
【００４９】
また、ステップＳ１０６で展開された素性の組合せの中にモデルに含まれる素性の組合せと一致しない素性の組合せが存在する場合（ステップＳ１１１Ｙｅｓ）、更新部１５は、モデルに含まれる素性の組合せと一致しない素性の組合せをモデル記憶部１３へ追加する（ステップＳ１１２）。このとき、モデルに追加される素性の組合せに対応する確信度は、学習データｔのラベルに従う。なお、ステップＳ１１１Ｎｏである場合、ステップＳ１１２の処理はスキップされる。その後、処理ステップは、ステップＳ１０４へ移行する。
【００５０】
その後、学習データＴの中に未処理の学習データのサンプルが存在しない場合（ステップＳ１０４Ｎｏ）、図示しないレジスタ等に保持される繰り返し試行回数ｉをインクリメントする（ステップＳ１１３）。
【００５１】
そして、繰り返し試行回数ｉがステップＳ１０２で取得された繰り返し回数Ｍ未満である場合（ステップＳ１１４Ｙｅｓ）、処理ステップは、上記のステップＳ１０３へ移行し、ステップＳ１０３〜ステップＳ１１３までの処理が繰り返し実行される。
【００５２】
一方、繰り返し試行回数ｉがステップＳ１０２で取得された繰り返し回数Ｍになった場合（ステップＳ１１４Ｎｏ）、更新部１５は、モデル記憶部１３に記憶されたモデルを所定の出力先へ出力し（ステップＳ１１５）、処理を終了する。なお、モデルの出力先には、一例として、メールのフィルタリング処理を実行するアプリケーションプログラムなどが挙げられる。また、外部の装置からモデルの生成を依頼された場合には、その依頼元へ返信することができる。
【００５３】
［効果の一側面］
上述してきたように、本実施例に係る学習装置１０は、分類時には、モデルに含まれる素性だけを展開し、モデルとのスコアを計算し、分類が誤っている場合には、誤った事例から生成される素性だけを展開し、モデルを更新する。これにより、全ての素性の組合せではなく、分類に必要な素性の組合せを展開するだけで学習が可能となり、事前に素性の組合せを陽に展開せずともよくなる。したがって、本実施例に係る学習装置１０によれば、メモリの使用量を抑制することができる。
【実施例２】
【００５４】
さて、上記の実施例１では、指定の素性サイズまで展開された素性の組合せをモデルの更新に用いる場合を例示したが、必ずしも最初の段階からモデルの更新に用いる素性サイズを指定の素性サイズまで拡張とせずともよく、素性サイズを段階的に変更することとしてもかまわない。そこで、本実施例では、一例として、学習データごとに当該学習データに関する分類のエラー頻度、例えばエラー回数に応じてモデルの更新に用いる素性サイズを段階的に変更する場合の例を説明する。
【００５５】
図９は、実施例２に係る学習装置の機能的構成を示すブロック図である。図９に示す学習装置２０は、図１０に示すアルゴリズムにしたがって学習処理を実行する。図１０は、エラーに基づくｐｅｒｃｅｐｔｒｏｎの擬似アルゴリズムの一例を示す図である。図１０に示す「ｘ」は、文字列を指し、φ（ｘ）は、文字列ｘに含まれる素性の組合せを取り出してベクトルにマッピングする関数を指す。図１０に示す「ｗ」は、重みベクトルを指し、例えば、ｄ次元のベクトル空間が対象である場合、ｔラウンド目のｄ次元の重みベクトルは「ｗｔ」で表される。なお、図１０においても、図２の説明と同様、書面の制約上、「ｗ」の表記に斜体でない表記を用いるが、実際には、重みベクトルに関する「ｗ」は斜体で表記される。
【００５６】
図１０に示すアルゴリズムは、学習装置２０が動的に素性を展開する点は図２に示すアルゴリズムと共通するが、モデル更新に用いる素性サイズを段階的に変更する点が異なる。具体的には、学習装置２０は、学習データのサンプルｘｔの分類が誤りであるからといってモデルの更新に用いる素性サイズを画一的に最大とはしない。すなわち、学習装置２０は、学習データのサンプルｘｔに関する分類が誤りである場合、モデルへの更新を認める最大の素性サイズＬと、当該学習データのサンプルｘｔに関する分類のエラー回数Ｅ［ｘｔ］とを比較する。以下では、モデルへの更新を認める最大の素性サイズのことを「最大素性サイズ」と記載する場合がある。このとき、学習装置２０は、最大素性サイズＬおよびエラー回数Ｅ［ｘｔ］のうち最小値を今回のモデル更新に用いる素性サイズｌとして設定する。以下では、今回のモデル更新に用いる素性サイズのことを「更新素性サイズ」と記載する場合がある。このような更新素性サイズｌにしたがって学習データのサンプルｘｔに含まれる素性の組合せを展開し、展開された素性の組合せをモデル更新に用いる。
【００５７】
このように図１０に示すアルゴリズムを用いる場合、エラー回数Ｅ［ｘｔ］が最大素性サイズＬに達するまではモデル更新に用いられる更新素性サイズｌはエラー回数Ｅ［ｘｔ］となる。加えて、エラー回数Ｅ［ｘｔ］が最大素性サイズＬに達するまでのモデルの更新により、学習データのサンプルｘに関する分類が成功した場合、学習データのサンプルｘに対する学習で更新素性サイズｌを最大素性サイズＬまで拡張せずともよくなる。つまり、更新素性サイズｌを最大素性サイズＬとする場合よりもモデルのサイズを小さくできる。一方、エラー回数Ｅ［ｘｔ］が最大素性サイズＬに達するまでに学習データのサンプルｘに関する分類が成功しない学習データのサンプルの場合、更新素性サイズｌを最大素性サイズＬまで拡張できる。それ故、学習精度が低下することも抑制できる。以上のことから、図１０に示すアルゴリズムによれば、学習精度の低下を抑制しつつ、モデルのサイズを低減できる。
【００５８】
図９に示す学習装置２０は、図１に示す学習装置１０に比べて、上記のエラー回数に関する判定を実施する判定部２１をさらに有する点が相違する。なお、図９には、図１に示す学習装置１０と同一の機能を発揮する機能部には同一の符号を付し、その説明を省略することとする。なお、判定部２１は設定部の一例である。
【００５９】
一実施形態として、判定部２１は、判定部２１が参照する内部メモリのワークエリアに学習データのサンプルごとに当該サンプルに関する分類のエラー回数が対応付けられたエラーデータを保持する。このようなエラーデータの管理の下、判定部２１は、照合部１４による処理の結果がラベルに反する場合、すなわちスパムスコアの累積値の符号がラベルの符号と異なる場合、あるいはスパムスコアの累積値がゼロになる場合、次のような処理を行う。すなわち、判定部２１は、エラーデータのうち分類を誤った学習データのサンプルに対応付けられたエラー回数の更新、例えば回数のインクリメントを実施する。その上で、判定部２１は、更新が行われたエラー回数が最大素性サイズよりも小さいか否か、すなわちエラー回数＜最大素性サイズＬを判定する。
【００６０】
ここで、エラー回数＜最大素性サイズＬである場合、判定部２１は、更新素性サイズｌをエラー回数に設定する。一方、エラー回数＜最大素性サイズＬでない場合、判定部２１は、更新素性サイズｌを最大素性サイズＬに設定する。このように設定された更新素性サイズｌにしたがって、判定部２１は、学習データのサンプルに含まれる素性の組合せを展開する。
【００６１】
その後、更新部１５は、判定部２１により展開された素性の組合せのうちモデルと一致しない素性の組合せをモデルへ追加する更新を行うと共に、モデルに含まれる確信度のうち判定部２１により展開された素性の組合せと一致する素性の組合せに対応付けられた確信度をラベルに基づいて更新する。
【００６２】
［具体例］
次に、上記の実施例１に示すモデル更新および本実施例に係るモデル更新により生じるモデルサイズの違いを具体例を示して説明する。
【００６３】
（１）実施例１に係るモデル更新
図１１〜図１４は、学習サンプルとモデルの照合の一例を示す図である。これら図１１〜図１４には、実施例１に係るモデル更新が行われる例が示されている。図１１には、図中の学習データＴのうち１行目のサンプルと初期のモデルとが比較される１ラウンド目における１サンプル目の照合を示し、図１２には、２行目のサンプルと図１１に示す更新後のモデルとが比較される１ラウンド目における２サンプル目の照合を示す。さらに、図１３には、図中の学習データＴのうち１行目のサンプルと図１２に示した更新後のモデルとが比較される２ラウンド目における１サンプル目の照合を示し、図１４には、２行目のサンプルと図１３に示す照合後のモデルとが比較される２ラウンド目における２サンプル目の照合を示す。
【００６４】
例えば、１ラウンド目における１サンプル目には、図１１に示すように、１サンプル目から「簡単」、「速度」、「簡単＆速度」の３つの素性の組合せが展開部１２により展開される（ステップＳ１１０１）。このようにステップＳ１１０１で展開された３つの素性の組合せ、すなわち「簡単」、「速度」、「簡単＆速度」がモデルと照合される（ステップＳ１１０２）。この初期の段階では、モデルは空の状態であり、素性の登録がないので、展開部１２により展開された素性の組合せと一致する素性の組合せもモデルに存在せず、スパムスコアの合計もゼロになる。このため、ステップＳ１１０１で展開された３つの素性の組合せ、すなわち「簡単」、「速度」、「簡単＆速度」がモデル記憶部１３へ追加される。このとき、素性の各組合せには、１つ目のサンプルに付与されたラベル「負例」にしたがってスパムスコア「−１」が対応付けられる（ステップＳ１１０３）。
【００６５】
続いて、１ラウンド目における２サンプル目には、図１２に示すように、２サンプル目から「簡単」、「売り上げ」、「簡単＆売り上げ」の３つの素性の組合せが展開部１２により展開される（ステップＳ１２０１）。このようにステップＳ１２０１で展開された３つの素性の組合せ、すなわち「簡単」、「売り上げ」、「簡単＆売り上げ」がモデルと照合される（ステップＳ１２０２）。この段階では、図１１に示す反転表示のハッチングに対応するモデルの素性の組合せと、ステップＳ１２０１で展開された２つ目のサンプルの素性の組合せとが一致する。すなわち、素性の組合せ「簡単」が学習データのサンプル及びモデルの間で一致する。この場合、素性の組合せ「簡単」以外に学習データのサンプル及びモデルの間で一致する素性の組合せが存在しないので、スパムスコアの合計値は「−１」となる。この２サンプル目のラベルは正例であり、スパムスコアの合計値の符号「負」と２つ目のサンプルのラベルの符号「正」が異なるので、分類は誤りとなる。
【００６６】
この場合、下記の通り、モデルの更新が実行される（ステップＳ１２０３）。具体的には、モデルに含まれる素性の組合せのうちステップＳ１２０１で展開された２つ目のサンプルの素性の組合せと一致するものを対象に、モデルに含まれる素性の組合せに対応付けられた現在のスパムスコアに２つ目のサンプルに付与されたラベル「正例」にしたがってスパムスコア「＋１」が加算される。すなわち、モデル内の素性の組合せ「簡単」にスパムスコア「＋１」が加算される。この結果、素性の組合せ「簡単」に対応付けられたスパムスコアは「０」になる。さらに、ステップＳ１２０１で展開された２つ目のサンプルに含まれる素性の組合せのうちモデルに含まれる素性の組合せと一致しない素性の組合せがモデルに追加される。すなわち、ステップＳ１２０１で展開された３つの素性の組合せのうち「売り上げ」及び「簡単＆売り上げ」がモデル記憶部１３へ追加される。このとき、素性の各組合せには、当該学習データＴの２つ目のサンプルに付与されたラベル「正例」にしたがってスパムスコア「＋１」が対応付けられる。このような１ラウンド目の照合および更新により、モデル１３ｅ２が得られる。
【００６７】
次に、２ラウンド目における１サンプル目には、図１３に示すように、１サンプル目から「簡単」、「速度」、「簡単＆速度」の３つの素性の組合せが展開部１２により展開される（ステップＳ１３０１）。このようにステップＳ１３０１で展開された３つの素性の組合せ、すなわち「簡単」、「速度」、「簡単＆速度」がモデルと照合される（ステップＳ１３０２）。この２ラウンド目では、モデル１３ｅ２のうち図１３に示す反転表示のハッチングに対応するモデルの素性の組合せ「簡単」、「速度」及び「簡単＆速度」と、Ｓ１３０１で展開された１つ目のサンプルの素性の組合せ「簡単」、「速度」及び「簡単＆速度」とが一致する。この場合、スパムスコアの合計値は「−２（＝０−１−１）」となる。この１つ目のサンプルのラベルは負例であり、スパムスコアの合計値の符号「負」と１サンプル目のラベルの符号「負」が同一であるので、分類は正解となる。この結果、モデル記憶部１３に記憶されたモデル１３ｅ２の更新は実施されない。
【００６８】
また、２ラウンド目における２サンプル目には、図１４に示すように、２サンプル目から「簡単」、「売り上げ」、「簡単＆売り上げ」の３つの素性の組合せが展開部１２により展開される（ステップＳ１４０１）。このようにステップＳ１４０１で展開された３つの素性の組合せ、すなわち「簡単」、「売り上げ」、「簡単＆売り上げ」がモデルと照合される（ステップＳ１４０２）。この２ラウンド目では、モデル１３ｅ２のうち図１４に示す反転表示のハッチングに対応するモデルの素性の組合せ「簡単」、「売り上げ」、「簡単＆売り上げ」と、ステップＳ１４０１で展開された２つ目のサンプルの素性の組合せ「簡単」、「売り上げ」、「簡単＆売り上げ」とが一致する。この場合、スパムスコアの合計値は「＋２（＝０＋１＋１）」となる。この２つ目のサンプルのラベルは正例であり、スパムスコアの合計値の符号「正」と２サンプル目のラベルの符号「正」が同一であるので、分類は正解となる。よって、２つ目のサンプルでもモデル記憶部１３に記憶されたモデル１３ｅ２の更新は実施されない。
【００６９】
このようなモデル１３ｅ２を用いて照合を行うことにより、１つ目及び２つ目の各サンプルの間でラベル通りの分類結果を導出することが可能になる。
【００７０】
（２）実施例２に係るモデル更新
図１５〜図１８は、学習サンプルとモデルの照合の一例を示す図である。これら図１５〜図１８には、実施例２に係るモデル更新が行われる例が示されている。図１５には、図中の学習データＴのうち１行目のサンプルと初期のモデルとが比較される１ラウンド目における１サンプル目の照合を示し、図１６には、２行目のサンプルと図１５に示す更新後のモデルとが比較される１ラウンド目における２サンプル目の照合を示す。さらに、図１７には、図中の学習データＴのうち１行目のサンプルと図１６に示した更新後のモデルとが比較される２ラウンド目における１サンプル目の照合を示し、図１８には、２行目のサンプルと図１７に示す照合後のモデルとが比較される２ラウンド目における２サンプル目の照合を示す。なお、図１５〜図１８には、学習データＴの各サンプルに内部メモリのワークエリアに保存されるエラー回数が付された状態で図示されている。
【００７１】
例えば、１ラウンド目における１サンプル目には、図１５に示すように、１サンプル目から「簡単」、「速度」、「簡単＆速度」の３つの素性の組合せが展開部１２により展開される（ステップＳ１５０１）。このようにモデルとの照合時に展開される素性サイズは、上記の実施例１における場合と同様に、モデル更新に用いる更新素性サイズｌとは異なり、最大素性サイズＬと同じサイズで固定される。続いて、ステップＳ１５０１で展開された３つの素性の組合せ、すなわち「簡単」、「速度」、「簡単＆速度」がモデルと照合される（ステップＳ１５０２）。この１ラウンド目における１サンプル目のように、初期の段階では、モデルは空の状態であり、素性の登録がないので、展開部１２により展開された素性の組合せと一致する素性の組合せもモデルに存在せず、スパムスコアの合計もゼロになる。
【００７２】
このように、スパムスコアの合計がゼロである場合、分類は不正解となる。この結果、１サンプル目のエラー回数が判定部２１により１つインクリメントされる。その後、エラー回数Ｅ［ｘｔ］と最大素性サイズｌとを比較し（ステップＳ１５０３）、エラー回数「１」＜最大素性サイズ「２」との判定結果が得られるので、更新素性サイズｌがエラー回数「１」に設定される。この更新素性サイズｌ「１」にしたがって、１つ目のサンプルから素性の組合せ「簡単」および「速度」が１ラウンド目の１つ目のサンプルでモデル更新に用いる素性の組合せとして展開される。この結果、２つの素性の組合せ「簡単」および「速度」がモデル記憶部１３へ追加される。このとき、素性の各組合せには、１つ目のサンプルのラベル「負例」に付与されたスパムスコア「−１」が対応付けられる（ステップＳ１５０４）。
【００７３】
続いて、１ラウンド目における２サンプル目には、図１６に示すように、２つ目のサンプルから「簡単」、「売り上げ」、「簡単＆売り上げ」の３つの素性の組合せが展開部１２により展開される（ステップＳ１６０１）。このようにステップＳ１６０１で展開された３つの素性の組合せ、すなわち「簡単」、「売り上げ」、「簡単＆売り上げ」がモデルと照合される（ステップＳ１６０２）。この段階では、図１６に示す反転表示のハッチングに対応するモデルの素性の組合せと、ステップＳ１６０１で展開された２つ目のサンプルの素性の組合せとが一致する。すなわち、素性の組合せ「簡単」が学習データのサンプル及びモデルの間で一致する。この場合、素性の組合せ「簡単」以外に学習データのサンプル及びモデルの間で一致する素性の組合せが存在しないので、スパムスコアの合計値は「−１」となる。この２つ目のサンプルのラベルは正例であり、スパムスコアの合計値の符号「負」と２つ目のサンプルのラベルの符号「正」が異なるので、分類は誤りとなる。
【００７４】
このように、１ラウンド目における２サンプル目でも、分類は不正解となる。この結果、２つ目のサンプルのエラー回数が判定部２１により１つインクリメントされる。その後、エラー回数Ｅ［ｘｔ］と最大素性サイズｌとを比較し（ステップＳ１６０３）、エラー回数「１」＜最大素性サイズ「２」との判定結果が得られるので、更新素性サイズｌがエラー回数「１」に設定される。この更新素性サイズｌ「１」にしたがって、２つ目のサンプルから素性の組合せ「簡単」および「売り上げ」が１ラウンド目の２つ目のサンプルでモデル更新に用いる素性の組合せとして展開される。
【００７５】
この結果、下記の通り、モデルの更新が実行される（ステップＳ１６０４）。具体的には、モデルに含まれる素性の組合せのうち更新素性サイズｌ「１」にしたがって展開された素性の組合せ「簡単」および「売り上げ」と一致するものを対象に、モデルに含まれる素性の組合せに対応付けられた現在のスパムスコアに２つ目のサンプルのラベル「正例」に付与されたスパムスコア「＋１」が加算される。すなわち、モデル内の素性の組合せ「簡単」にスパムスコア「＋１」が加算される。この結果、素性の組合せ「簡単」に対応付けられたスパムスコアは「０」になる。さらに、更新素性サイズｌ「１」にしたがって展開された素性の組合せ「簡単」および「売り上げ」のうちモデルに含まれる素性の組合せと一致しない素性の組合せがモデルに追加される。すなわち、ステップＳ１６０１で展開された３つの素性の組合せのうち「売り上げ」がモデル記憶部１３へ追加される。このとき、素性の組合せ「売り上げ」には、当該学習データＴの２つ目のサンプルに付与されたラベル「正例」にしたがってスパムスコア「＋１」が対応付けられる。このような１ラウンド目の照合および更新により、モデル１３ｅ３が得られる。
【００７６】
次に、２ラウンド目における１サンプル目には、図１７に示すように、１つ目のサンプルから「簡単」、「速度」、「簡単＆速度」の３つの素性の組合せが展開部１２により展開される（ステップＳ１７０１）。このようにステップＳ１７０１で展開された３つの素性の組合せ、すなわち「簡単」、「速度」、「簡単＆速度」がモデルと照合される（ステップＳ１７０２）。この２ラウンド目では、モデル１３ｅ３のうち図１７に示す反転表示のハッチングに対応するモデルの素性の組合せ「簡単」及び「速度」と、ステップＳ１７０１で展開された１つ目のサンプルの素性の組合せ「簡単」及び「速度」とが一致する。この場合、スパムスコアの合計値は「−１（＝０−１）」となる。この１つ目のサンプルのラベルは負例であり、スパムスコアの合計値の符号「負」と１つ目のサンプルのラベルの符号「負」が同一であるので、分類は正解となる。この結果、モデル記憶部１３に記憶されたモデル１３ｅ３の更新は実施されない。
【００７７】
また、２ラウンド目における２サンプル目には、図１８に示すように、２つ目のサンプルから「簡単」、「売り上げ」、「簡単＆売り上げ」の３つの素性の組合せが展開部１２により展開される（ステップＳ１８０１）。このようにステップＳ１８０１で展開された３つの素性の組合せ、すなわち「簡単」及び「売り上げ」がモデルと照合される（ステップＳ１８０２）。この２ラウンド目では、モデル１３ｅ３のうち図１８に示す反転表示のハッチングに対応するモデルの素性の組合せ「簡単」及び「売り上げ」と、ステップＳ１８０１で展開された２つ目のサンプルの素性の組合せ「簡単」及び「売り上げ」とが一致する。この場合、スパムスコアの合計値は「＋１（＝０＋１）」となる。この２つ目のサンプルのラベルは正例であり、スパムスコアの合計値の符号「正」と２サンプル目のラベルの符号「正」が同一であるので、分類は正解となる。よって、２サンプル目でもモデル記憶部１３に記憶されたモデル１３ｅ３の更新は実施されない。
【００７８】
このようなモデル１３ｅ３を用いて照合を行うことにより、１つ目及び２つ目の各サンプルの間でラベル通りの分類結果を導出することが可能になる。
【００７９】
［モデルサイズの比較］
上述の通り、実施例１に係るモデル更新では、モデル更新が最大素性サイズで実施される。このため、ステップＳ１１０３で素性サイズが「２」である素性の組合せ「簡単＆速度」がモデルに追加されると共に、ステップＳ１２０３で素性サイズが「２」である素性の組合せ「簡単＆売り上げ」が追加されたモデル１３ｅ２が得られる。一方、本実施例に係るモデル更新では、エラー回数が最大素性サイズに達しない限り、エラー回数に対応する更新素性サイズでモデル更新が実施される。それ故、素性の組合せ「簡単＆速度」及び「簡単＆売り上げ」の追加が不要であることをエラー回数及び最大素性サイズの比較により判断した上で、モデルに対する素性の組合せ「簡単＆速度」及び「簡単＆売り上げ」の追加を見送ってモデル１３ｅ３を学習できる。このため、モデル１３ｅ３では、モデル１３ｅ２と同等の学習精度を有しつつ、モデルから素性の組合せ「簡単＆速度」及び「簡単＆売り上げ」を削減できる。したがって、本実施例に係るモデル更新によれば、上記の実施例１に係るモデル更新に比べてモデルサイズの低減を実現できる。
【００８０】
図１９は、実施例２に係る学習処理の手順を示すフローチャートである。この学習処理は、図８に示した処理と同様、入力部等の指示入力により学習が指示された場合に処理を起動したり、あるいは学習データが取得された場合に処理を自動的に起動したりすることができる。
【００８１】
ここで、図１９に示す学習処理は、図８に示した学習処理に比べて、ステップＳ１０８の分岐でＹｅｓと判定された場合に、ステップＳ２０１〜ステップＳ２０５の処理が挿入されている点が異なる。なお、図１９には、図８に示されたステップと同様の処理が実行されるステップには図８に示したステップと同一のステップ番号が付与されている。
【００８２】
図１９に示すように、取得部１１は、学習データＴを取得すると共に、学習の繰り返し回数Ｍの設定を取得する（ステップＳ１０１及びステップＳ１０２）。この繰り返し回数Ｍには、モデルに求める精度に応じて任意の回数を予め設定しておくことができる。なお、ステップＳ１０１及び１０２の処理は、実行される順序が順不同であってよく、並列して実行されることも妨げない。
【００８３】
続いて、取得部１１は、ステップＳ１０１で取得された学習データＴの全てのサンプルに関するステータス、例えばフラグ等を未処理に設定する（ステップＳ１０３）。そして、学習データＴの中に未処理の学習データのサンプルが存在する限り（ステップＳ１０４Ｙｅｓ）、ステップＳ１０５以降の処理を実行する。
【００８４】
すなわち、展開部１２は、ステップＳ１０１で取得された学習データＴのうち未処理の学習データｔを１つ選択する（ステップＳ１０５）。続いて、展開部１２は、ステップＳ１０５で選択された学習データｔの素性を指定のアルゴリズムにしたがって動的に展開する（ステップＳ１０６）。例えば、２単語の組合せまでを抽出する場合、学習データｔに含まれる単語と展開されると共に、各単語が２つ組み合わせられた組合せが展開される。その上で、照合部１４は、展開部１２により展開された学習データｔの素性の組合せと、モデル記憶部１３に記憶されたモデルに含まれる素性の組合せとを照合する（ステップＳ１０７）。
【００８５】
そして、ステップＳ１０７の照合の結果がラベルに反する場合、すなわちスパムスコアの累積値の符号がラベルの符号と異なる場合、あるいはスパムスコアの累積値がゼロになる場合（ステップＳ１０８Ｙｅｓ）、判定部２１は、次のような処理を行う。すなわち、判定部２１は、内部メモリに保存されたエラーデータのうち分類を誤った学習データのサンプルに対応付けられたエラー回数の更新、例えば回数のインクリメントを実施する（ステップＳ２０１）。
【００８６】
その上で、判定部２１は、ステップＳ２０１で更新が行われたエラー回数が最大素性サイズよりも小さいか否か、すなわちエラー回数＜最大素性サイズＬを判定する（ステップＳ２０２）。
【００８７】
ここで、エラー回数＜最大素性サイズＬである場合（ステップＳ２０２Ｙｅｓ）、判定部２１は、更新素性サイズｌをエラー回数に設定する（ステップＳ２０３）。一方、エラー回数＜最大素性サイズＬでない場合（ステップＳ２０２Ｎｏ）、判定部２１は、更新素性サイズｌを最大素性サイズＬに設定する（ステップＳ２０４）。このようにステップＳ２０３またはステップＳ２０４で設定された更新素性サイズｌにしたがって、判定部２１は、学習データのサンプルに含まれる素性の組合せを展開する（ステップＳ２０５）。
【００８８】
その後、更新部１５は、ステップＳ２０５で展開された素性の組合せと一致する素性の組合せがモデルの中に存在するか否かを判定する（ステップＳ１０９）。なお、学習データｔの分類が誤りではない場合（ステップＳ１０８Ｎｏ）、モデルの更新は実行されず、ステップＳ１０４の処理へ移行する。
【００８９】
ここで、ステップＳ２０５で展開された素性の組合せと一致する素性の組合せがモデルの中に存在する場合（ステップＳ１０９Ｙｅｓ）、更新部１５は、モデルに含まれる素性の組合せのうちステップＳ２０５で展開された学習データｔの素性の組合せと一致するものを対象に、モデルに含まれる素性の組合せに対応付けられた現在のスパムスコアに学習データｔのラベルに付与されたスパムスコアを加算する更新を行う（ステップＳ１１０）。なお、ステップＳ１０９Ｎｏの場合、ステップＳ１１０の処理はスキップされる。
【００９０】
また、ステップＳ２０５で展開された素性の組合せの中にモデルに含まれる素性の組合せと一致しない素性の組合せが存在する場合（ステップＳ１１１Ｙｅｓ）、更新部１５は、モデルに含まれる素性の組合せと一致しない素性の組合せをモデル記憶部１３へ追加する（ステップＳ１１２）。このとき、モデルに追加される素性の組合せに対応する確信度は、学習データｔのラベルに従う。なお、ステップＳ１１１Ｎｏである場合、ステップＳ１１２の処理はスキップされる。その後、処理ステップは、ステップＳ１０４へ移行する。
【００９１】
その後、学習データＴの中に未処理の学習データのサンプルが存在しない場合（ステップＳ１０４Ｎｏ）、図示しないレジスタ等に保持される繰り返し試行回数ｉをインクリメントする（ステップＳ１１３）。
【００９２】
そして、繰り返し試行回数ｉがステップＳ１０２で取得された繰り返し回数Ｍ未満である場合（ステップＳ１１４Ｙｅｓ）、処理ステップは、上記のステップＳ１０３へ移行し、ステップＳ１０３〜ステップＳ１１３までの処理が繰り返し実行される。
【００９３】
一方、繰り返し試行回数ｉがステップＳ１０２で取得された繰り返し回数Ｍになった場合（ステップＳ１１４Ｎｏ）、更新部１５は、モデル記憶部１３に記憶されたモデルを所定の出力先へ出力し（ステップＳ１１５）、処理を終了する。なお、モデルの出力先には、一例として、メールのフィルタリング処理を実行するアプリケーションプログラムなどが挙げられる。また、外部の装置からモデルの生成を依頼された場合には、その依頼元へ返信することができる。
【００９４】
［効果の一側面］
上述してきたように、本実施例に係る学習装置２０は、ラベル付きの学習サンプルとモデルの照合の結果がラベルに反する場合、学習サンプルに関するエラー回数に応じてモデル更新に用いる素性のサイズを変更してモデルを更新する。したがって、本実施例に係る学習装置２０によれば、モデルのサイズを低減できる。
【実施例３】
【００９５】
さて、これまで開示の装置に関する実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では、本発明に含まれる他の実施例を説明する。
【００９６】
［部分構造データへの適用］
上記の実施例１では、ｐｅｒｃｅｐｔｒｏｎの素性の組合せを学習する場合を例示したが、Ｓｔｒｉｎｇ、Ｔｒｅｅ、Ｇｒａｐｈなどの半構造データの学習を行う場合や、ＡＲＯＷといったConfidence-Weighted-Learningにも上記の学習処理を適用できる。図２０は、素性の動的展開に基づくＡＲＯＷの擬似アルゴリズムの一例を示す図である。図２０に示す「ｘ」は、単語列を指し、φ（ｘ）は、単語列ｘに含まれる素性の組合せまたは単語列ｘの部分文字列、例えば２つの構造データ間で共通する部分文字列を取り出してベクトルにマッピングする関数を指す。図２０に示す「μ」は、重みベクトルを指し、例えば、ｄ次元のベクトル空間が対象である場合、ｔラウンド目のｄ次元の重みベクトルは「μｔ」で表される。また、図２０に示す「Σ」は、素性の確信度を指し、例えば、ｔラウンド目の素性の確信度を保持するｄ×ｄ行列が「Σｔ」で表される。この場合、学習装置１０では、入力の単語列ｘに対し、関数φ（ｘ）にてベクトルに陽に展開し、更新時に重みベクトルμｔだけでなく、素性の確信度を保持するΣｔも更新する。
【００９７】
すなわち、学習装置１０は、分類時の展開に、既存の手法と同じく、モデルμｔ中の部分構造にマッチした場合にだけ処理を行なうことで、処理時間を軽減する。さらに、学習装置１０は、マッチング時にモデルに部分マッチした場合にだけ部分構造の列挙を続けるという方法を用いる。
【００９８】
具体的には、更新時は、更新対象の入力を指定されたサイズまでの単語列を展開する。図２１は、モデル内の部分構造をトライ構造に格納して照合する一例を示す図である。図２１には、“ｅａｔ”、“ｃｏｒｎ”、“ｓｏｕｐ”という３つの単語列が与えられた場合に、“ｃｏｒａｌ”、“ｃｏｒｉｎｇ”、“ｃｏｒｎ”、“ｃｏｒｎ  ｓｏｕｐ”（連続する単語列）がトライ構造で登録されているモデルに対し、“ｃｏｒｎ”と“ｓｏｕｐ”の組合せのマッチングを取っている状況を示す。図２１に示すように、最初に先頭からマッチする単語である“ｃｏｒｎ”を見つけた後、続いて、組合せのデリミタ、図２１では空白の丸があるので、続きにマッチする“ｓｏｕｐ”とマッチングを取って、終端記号の“♯”まで辿りつく。このように、モデルをトライ構造で保持し、入力とする学習データの素性の組合せがモデル内にある場合に、続いて学習データ内の残りの素性を含めて、モデルとのマッチングを取るという手順を行うことにより、全ての組合せを展開することなく、部分的にマッチした場合に、組合せを拡張する。
【００９９】
また、登録時には、一時的に、全ての組合せを展開する。例えば、“ｃｏｒｎ”、“ｅａｔ”、“ｓｏｕｐ”という３つの単語に対し、最大２つまでの連続する単語の組合せをモデルに組み込む場合に、“ｅａｔ”、“ｃｏｒｎ”、“ｓｏｕｐ”、“ｅａｔ  ｃｏｒｎ”、“ｃｏｒｎ  ｓｏｕｐ”を展開して、既存のＡＲＯＷと同じく、それぞれの素性の、分類用の素性の重みおよび、更新用の素性の確信度を計算し、トライ構造にて表現されたモデルに登録する。これにより、最初から、全ての事例の素性の組合せを展開せずとも、素性の組合せを学習することができる。
【０１００】
また、上記の実施例２に係る学習装置２０にも、Ｓｔｒｉｎｇ、Ｔｒｅｅ、Ｇｒａｐｈなどの半構造データの学習を行う場合や、ＡＲＯＷといったConfidence-Weighted-Learningにも上記の学習処理を適用できる。図２２は、エラーに基づくＡＲＯＷの擬似アルゴリズムの一例を示す図である。図２２に示す「ｘ」、「φ（ｘ）」、「μ」及び「Σ」は、図２０と同様である。図２２に示すアルゴリズム及び図２０に示したアルゴリズムの差分は、図２と図１０に示したアルゴリズムの差分と同様である。すなわち、図２２に示すアルゴリズムが学習装置２０に適用される場合、図２０に示すアルゴリズムにしたがって学習装置１０を動作させる場合に比べて、学習データのサンプルｘｔに関する分類が誤りである場合、最大素性サイズＬおよびエラー回数Ｅ［ｘｔ］のうち最小値を今回のモデル更新に用いる素性サイズｌとして設定する点が異なる。
【０１０１】
［エラー回数］
上記の実施例２では、最大素性サイズＬおよびエラー回数Ｅ［ｘｔ］のうち最小値を更新素性サイズｌとして設定する場合を例示したが、必ずしもエラー回数をそのまま最大素性サイズＬと比較せずともかまわない。例えば、最大素性サイズＬおよびエラー回数Ｅ［ｘｔ］／定数Ｎのうち最小値を更新素性サイズｌとして設定することもできる。この場合、エラー回数Ｅ［ｘｔ］／定数Ｎが整数でない場合、四捨五入等の条件によりエラー回数Ｅ［ｘｔ］／定数Ｎを整数に変換することにより、実施例２と同様の処理を実現できる。この場合、定数Ｎの値を大きく設定するほどモデルサイズを低減できる。
【０１０２】
［系列ラベリングへの適用］
上記の学習処理は、系列ラベリングにも同様に適用できる。すなわち、stochastic  gradient  decent  に基づくＣＲＦの学習や構造化パーセプトロンにおいても、素性ベクトルの場合と同様に動的に素性を展開しながら学習可能である。
【０１０３】
［他の半構造データへの適用］
また、上記の学習処理は、これまでに説明した以外の半構造データ、例えばＳｔｒｉｎｇやＴｒｅｅなどにも同様に適用できる。すなわち、Mohammed  Zaki著の文献、すなわち上記の非特許文献５に記載の方法にて、指定サイズまでの部分木を素性とする素性ベクトルを生成し更新を行う。ここで言う「指定サイズ」とは、含まれるノードの数である。Ｓｔｒｉｎｇは、Ｔｒｅｅのうち子供が一つしかない場合であるので、ＳｔｒｉｎｇとＴｒｅｅは同様のデータとして扱うことができる。また、上記の非特許文献５にあるよう、木構造は文字列にて表現できるため、上記ベクトルの例のようにトライ構造にて管理して、部分マッチした場合に、動的に展開しながら処理を行うことができる。
【０１０４】
また、X.YanやJ.Hanらの文献、すなわち上記の非特許文献３に記載の方法にて、モデルの要素は、ＤＦＳ（Depth-First  Search）  ｃｏｄｅにて保持しておき、ＤＦＳ  ｃｏｄｅの部分にマッチしたら次をチェックするために展開するという方法にて、マッチングを行うことができる。そして、モデルの更新時には、重複がないように、指定サイズまでの部分グラフを列挙し、それぞれの部分グラフを素性とする、素性ベクトルを生成し、モデルの更新を行う。ここで言う「指定サイズ」には、含まれるノードの数あるいは、エッジの数が該当する。
【０１０５】
［分散および統合］
また、図示した各装置の各構成要素は、必ずしも物理的に図示の如く構成されておらずともよい。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、取得部１１、展開部１２、照合部１４または更新部１５を学習装置１０の外部装置としてネットワーク経由で接続するようにしてもよい。また、取得部１１、展開部１２、照合部１４または更新部１５を別の装置がそれぞれ有し、ネットワーク接続されて協働することで、上記の学習装置１０の機能を実現するようにしてもよい。
【０１０６】
［学習プログラム］
また、上記の実施例で説明した各種の処理は、予め用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図２３を用いて、上記の実施例と同様の機能を有する学習プログラムを実行するコンピュータの一例について説明する。
【０１０７】
図２３は、実施例１〜実施例３に係る学習プログラムを実行するコンピュータのハードウェア構成例を示す図である。図２３に示すように、コンピュータ１００は、操作部１１０ａと、スピーカ１１０ｂと、カメラ１１０ｃと、ディスプレイ１２０と、通信部１３０とを有する。さらに、このコンピュータ１００は、ＣＰＵ１５０と、ＲＯＭ１６０と、ＨＤＤ１７０と、ＲＡＭ１８０とを有する。これら１１０〜１８０の各部はバス１４０を介して接続される。
【０１０８】
ＨＤＤ１７０には、図２３に示すように、上記の実施例１で示した取得部１１、展開部１２、照合部１４及び更新部１５と同様の機能を発揮する学習プログラム１７０ａが記憶される。また、ＨＤＤ１７０には、上記の実施例２で示した取得部１１、展開部１２、照合部１４、更新部１５及び判定部２１と同様の機能を発揮する学習プログラム１７０ａが記憶されることとしてもよい。この学習プログラム１７０ａは、図１に示した取得部１１、展開部１２、照合部１４及び更新部１５の各構成要素と同様、統合又は分離してもかまわない。また、学習プログラム１７０ａは、図９に示した取得部１１、展開部１２、照合部１４、更新部１５及び判定部２１の各構成要素と同様、統合又は分離してもかまわない。すなわち、ＨＤＤ１７０には、必ずしも上記の実施例１または上記の実施例２で示した全てのデータが格納されずともよく、処理に用いるデータがＨＤＤ１７０に格納されればよい。
【０１０９】
このような環境の下、ＣＰＵ１５０は、ＨＤＤ１７０から学習プログラム１７０ａを読み出した上でＲＡＭ１８０へ展開する。この結果、学習プログラム１７０ａは、図２３に示すように、学習プロセス１８０ａとして機能する。この学習プロセス１８０ａは、ＲＡＭ１８０が有する記憶領域のうち学習プロセス１８０ａに割り当てられた領域にＨＤＤ１７０から読み出した各種データを展開し、この展開した各種データを用いて各種の処理を実行する。例えば、学習プロセス１８０ａが実行する処理の一例として、図８や図１９に示す処理などが含まれる。なお、ＣＰＵ１５０では、必ずしも上記の実施例１で示した全ての処理部が動作せずともよく、実行対象とする処理に対応する処理部が仮想的に実現されればよい。
【０１１０】
なお、上記の学習プログラム１７０ａは、必ずしも最初からＨＤＤ１７０やＲＯＭ１６０に記憶されておらずともかまわない。例えば、コンピュータ１００に挿入されるフレキシブルディスク、いわゆるＦＤ、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に学習プログラム１７０ａを記憶させる。そして、コンピュータ１００がこれらの可搬用の物理媒体から学習プログラム１７０ａを取得して実行するようにしてもよい。また、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ１００に接続される他のコンピュータまたはサーバ装置などに学習プログラム１７０ａを記憶させておき、コンピュータ１００がこれらから学習プログラム１７０ａを取得して実行するようにしてもよい。
【符号の説明】
【０１１１】
１０    学習装置
１１    取得部
１２    展開部
１３    モデル記憶部
１４    照合部
１５    更新部
【図１】
2018045524.tif 000005
【図２】
2018045524.tif 000006
【図３】
2018045524.tif 000007
【図４】
2018045524.tif 000008
【図５】
2018045524.tif 000009
【図６】
2018045524.tif 000010
【図７】
2018045524.tif 000011
【図８】
2018045524.tif 000012
【図９】
2018045524.tif 000013
【図１０】
2018045524.tif 000014
【図１１】
2018045524.tif 000015
【図１２】
2018045524.tif 000016
【図１３】
2018045524.tif 000017
【図１４】
2018045524.tif 000018
【図１５】
2018045524.tif 000019
【図１６】
2018045524.tif 000020
【図１７】
2018045524.tif 000021
【図１８】
2018045524.tif 000022
【図１９】
2018045524.tif 000023
【図２０】
2018045524.tif 000024
【図２１】
2018045524.tif 000025
【図２２】
2018045524.tif 000026
【図２３】
2018045524.tif 000027