(57)【要約】【課題】下位問題を少ない計算量で厳密に解くことができるモデルパラメータを推定することができる。【解決手段】選択部４０により、正解データに含まれるペアを選択し、パラメータ更新部４２により、選択されたペアに基づいて、各カテゴリに対するペアのコンテンツの双対変数からなるベクトルを推定するための下位問題が置換される、シンプレックス射影問題を解くために、ベクトル及びパラメータを計算し、計算されたベクトル及びパラメータに基づいて、シンプレックス射影問題を解くことにより、ベクトルを計算し、計算されたベクトルに基づいて、各カテゴリに対するパラメータからなるベクトルを計算し、計算されたベクトルに基づいて、各カテゴリに対する双対変数からなるベクトル及び各カテゴリに対するモデルパラメータを更新し、繰り返し判定部４４により、予め定められた収束条件を満たすまで繰り返す。【選択図】図７
2016024502.tif 000002
【特許請求の範囲】
【請求項１】
コンテンツと前記コンテンツが所属するカテゴリとの複数のペアからなる正解データに含まれる前記ペアを選択する選択部と、
前記選択されたｉ番目のペアに基づいて、コンテンツが所属するカテゴリを分類するための各カテゴリｍに対するモデルパラメータを学習する際に用いる、各カテゴリｍに対するｉ番目のペアのコンテンツの双対変数αｉmからなるベクトルα＾iを推定するための以下（１）式に示す下位問題が置換される、以下（２）式に示すシンプレックス射影問題を解くために、以下（３）式に従ってベクトルμ＾及びパラメータｚを計算し、前記計算されたベクトルμ＾及びパラメータｚに基づいて、前記シンプレックス射影問題を解くことにより、ベクトルβ＾を計算し、前記計算されたベクトルβ＾に基づいて、以下（４）式に従って、各カテゴリｍに対するパラメータδｉmからなるベクトルδ＾ｉを計算し、前記計算されたベクトルδ＾ｉに基づいて、各カテゴリｍに対する前記双対変数αｉmからなるベクトルα＾i及び各カテゴリｍに対する前記モデルパラメータを更新するパラメータ更新部と、
前記選択部による前記ペアの選択と、前記パラメータ更新部による更新と、を予め定められた収束条件を満たすまで繰り返す繰り返し判定部と、
を含む、モデルパラメータ推定装置。
【数１】
2016024502.tif 000015
ただし、ｘ＾ｉは、前記正解データに含まれるｉ番目のペアのコンテンツの特徴ベクトルであり、Ｃ＾ｉは、各ペアｉ及び各カテゴリｍの組み合わせに対する正則化パラメータＣｉｍからなり、Ｃｉｍは、各ペアｉ及び各カテゴリｍの組み合わせに対する前記正則化パラメータであり、カテゴリｍが前記ペアのカテゴリと同一のとき、予め定められた正の値Ｃとなり、それ以外のときは０となり、ｇ＾ｉは、各カテゴリｍに対するｇｉmからなり、ｇｉmは、各ペアｉ及び各カテゴリｍの組み合わせに対する前記双対変数αｉmからなる行列α＾を推定するための目的関数の双対変数αｉmについての偏微分である。
【請求項２】
前記パラメータ更新部は、以下（５）式に示す関数φ（θ）についてφ（θ）＝０を満たすθを求める求根アルゴリズム、各カテゴリｍに対応するパラメータμｍを降順に並べ替えて、パラメータμｍの部分和を求めるＳｏｒｔ法、又は各カテゴリｍに対応するパラメータμｍの並べ替えを行わずに各カテゴリｍに対応するパラメータμｍの分割する位置を決定する値を選択し、前記パラメータμｍの各々の和を繰り返し計算するＰｉｖｏｔ法を用いて、前記シンプレックス射影問題を解く請求項１記載のモデルパラメータ推定装置。
【数２】
2016024502.tif 000016
ただし、ｋはカテゴリ数、μｍはカテゴリｍに対するパラメータμを表す。
【請求項３】
選択部と、パラメータ更新部と、繰り返し判定部と、を含むモデルパラメータ推定装置における、モデルパラメータ推定方法であって、
前記選択部は、コンテンツと前記コンテンツが所属するカテゴリとの複数のペアからなる正解データに含まれる前記ペアを選択し、
前記パラメータ更新部は、前記選択されたｉ番目のペアに基づいて、コンテンツが所属するカテゴリを分類するための各カテゴリｍに対するモデルパラメータを学習する際に用いる、各カテゴリｍに対するｉ番目のペアのコンテンツの双対変数αｉmからなるベクトルα＾iを推定するための以下（６）式に示す下位問題が置換される、以下（７）式に示すシンプレックス射影問題を解くために、以下（８）式に従ってベクトルμ＾及びパラメータｚを計算し、前記計算されたベクトルμ＾及びパラメータｚに基づいて、前記シンプレックス射影問題を解くことにより、ベクトルβ＾を計算し、前記計算されたベクトルβ＾に基づいて、以下（９）式に従って、各カテゴリｍに対するパラメータδｉmからなるベクトルδ＾ｉを計算し、前記計算されたベクトルδ＾ｉに基づいて、各カテゴリｍに対する前記双対変数αｉmからなるベクトルα＾i及び各カテゴリｍに対する前記モデルパラメータを更新し、
前記繰り返し判定部は、前記選択部による前記ペアの選択と、前記パラメータ更新部による更新と、を予め定められた収束条件を満たすまで繰り返す
モデルパラメータ推定方法。
【数３】
2016024502.tif 000017
ただし、ｘ＾ｉは、前記正解データに含まれるｉ番目のペアのコンテンツの特徴ベクトルであり、Ｃ＾ｉは、各ペアｉ及び各カテゴリｍの組み合わせに対する正則化パラメータＣｉｍからなり、Ｃｉｍは、各ペアｉ及び各カテゴリｍの組み合わせに対する前記正則化パラメータであり、カテゴリｍが前記ペアのカテゴリと同一のとき、予め定められた正の値Ｃとなり、それ以外のときは０となり、ｇ＾ｉは、各カテゴリｍに対するｇｉmからなり、ｇｉmは、各ペアｉ及び各カテゴリｍの組み合わせに対する前記双対変数αｉmからなる行列α＾を推定するための目的関数の双対変数αｉmについての偏微分である。
【請求項４】
前記パラメータ更新部が前記シンプレックス射影問題を解くことは、以下（１０）式に示す関数φ（θ）についてφ（θ）＝０を満たすθを求める求根アルゴリズム、各カテゴリｍに対応するパラメータμｍを降順に並べ替えて、パラメータμｍの部分和を求めるＳｏｒｔ法、又は各カテゴリｍに対応するパラメータμｍの並べ替えを行わずに各カテゴリｍに対応するパラメータμｍの分割する位置を決定する値を選択し、前記パラメータμｍの各々の和を繰り返し計算するＰｉｖｏｔ法を用いて、前記シンプレックス射影問題を解く請求項３記載のモデルパラメータ推定方法。
【数４】
2016024502.tif 000018
ただし、ｋはカテゴリ数、μｍはｍ番目のカテゴリのμを表す。
【請求項５】
コンピュータを、請求項１又は請求項２記載のモデルパラメータ推定装置を構成する各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、モデルパラメータ推定装置、方法、及びプログラムに係り、特に、自動分類に用いるパラメータを推定するモデルパラメータ推定装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
統計的手法に基づくコンテンツの自動分類技術では、コンテンツとカテゴリの依存関係の強さを表す識別関数を特徴ベクトルとモデルパラメータの関数として与え、最も強い依存関係のあるカテゴリを識別関数をもとに推定することでコンテンツの自動分類を行う。モデルパラメータの値は、一般的に、カテゴリが判明しているコンテンツを用いて求める。多カテゴリ分類を行うための識別関数の例として下記（１）式の関数がある。
【０００３】
【数１】
2016024502.tif 000003
【０００４】
ここで＊ｙはモデルパラメータベクトルにより予測されたカテゴリを表し、ｘ＾はコンテンツの特徴ベクトルを表す。ｗ＾ｍはｘ＾と同じ次元性を持つｍ番目のカテゴリのモデルパラメータベクトルを表し、ｋはカテゴリ数を表す。また、Τはベクトル転置を示す。
【０００５】
従来、多カテゴリサポートベクトルマシン（以下、ＭＣＳＶＭ）のモデルパラメータを効率的に計算する手法が提案されており（非特許文献１）、ｗ＾ｍを下記（２）式のように定義している。なお、記号に付された「＾」は、当該記号が行列、多次元配列、又はベクトルであることを表している。また、記号の前に付された「＊」は、当該記号が推定された値であることを表している。
【０００６】
【数２】
2016024502.tif 000004
【０００７】
ここで、ｘ＾ｉはカテゴリが判明しているｉ番目のコンテンツの特徴ベクトル、αｉｍはｍ番目のカテゴリに対するｉ番目のコンテンツの双対変数、ｎはカテゴリが判明しているコンテンツの数である。反復計算を行うことにより双対変数の値を推定する（非特許文献１）。各反復において、ｉ番目のコンテンツをランダムで選択し、αｉ１，．．．，αｉｋのみを推定するための下位問題を解く。双対変数のランダム選択と下位問題の計算を繰り返すことで、すべての双対変数の推定値を求め、上記（２）式を用いてモデルパラメータを得る。下位問題の解法として、様々な手法が提案されており、例えば、下位問題をｆｉｘｅｄ  ｐｏｉｎｔ法で解く方法（非特許文献１）、下位問題をソートによる手法で解く方法（非特許文献２）、下位問題をａｃｔｉｖｅ  ｓｅｔ法で解く方法（非特許文献３）、下位問題をＳｅｑｕｅｎｔｉａｌ  Ｍｉｎｉｍａｌ  Ｏｐｔｉｍｉｚａｔｉｏｎ（ＳＭＯ）法で解く方法（非特許文献４）、下位問題をＦｒａｎｋ−Ｗｏｌｆｅ法で解く方法（非特許文献５）が知られている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】K. Crammer and Y. Singer (2002), On the algorithmic implementation of multiclass kernel-based vector machines, Journal of Machine Learning Research, vol. 2, pp. 265-292.
【非特許文献２】K. Crammer and Y. Singer (2002), On the learnability and design of output codes for multiclass problems, Machine Learning, vol.47, no. 2-3, pp. 201-233.
【非特許文献３】S. S. Keerthi, S. Sundararajan, K.-W. Chang, C.-J. Hsieh, and C.-J. Lin (2008), A sequential dual method for large scale multi-class linear SVMs, Proceedings of KDD conference 2008, pp. 408-416.
【非特許文献４】A. Bordes, L. Bottou, P. Gallinari, and J. Weston (2007),Solving multiclass support vector machines with LaRank, Proceedings of ICML conference 2007, pp. 89-96.
【非特許文献５】S. Lacoste-Julien, M. Jaggi, M. Schmidt, and P. Pletscher,Block- coordinate frank-wolfe optimization for structural SVMs, Proceedings of ICML conference 2013.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ＭＣＳＶＭでは、下位問題を少ない計算量で厳密に解ければ、高い分類精度を与えるモデルパラメータ値を短い計算時間で得ることが期待できる。非特許文献１、４、及び５によるｆｉｘｅｄ  ｐｏｉｎｔ法、ＳＭＯ法、Ｆｒａｎｋ−Ｗｏｌｆｅ法は、下位問題を解くのに必要な計算量のオーダーはＯ（ｋ）であり、短い時間の計算によりパラメータ値を得ることができるが、下位問題を近似的に解くため、正しい双対変数の推定値を得られる保証がないという問題がある。このため、高い分類精度を与えるモデルパラメータ値を得るために、下位問題の反復計算を多数回行う必要が生じる。
【００１０】
一方、非特許文献２及び３によるソート法とａｃｔｉｖｅ  ｓｅｔ法は、下位問題を厳密に解くが、計算量のオーダーはＯ（ｋｌｏｇｋ）であり、また、すべてのｎ個のコンテンツに対して下位問題を解かなければならないため、ｎとｋが大きければ大きいほど、モデルパラメータの推定に必要な計算量が多くなるという問題がある。
【００１１】
本発明では、上記問題を解決するために成されたものであり、下位問題を少ない計算量で厳密に解いてモデルパラメータを推定することができるモデルパラメータ推定装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するために、第１の発明に係るモデルパラメータ推定装置は、コンテンツと前記コンテンツが所属するカテゴリとの複数のペアからなる正解データに含まれる前記ペアを選択する選択部と、前記選択されたｉ番目のペアに基づいて、コンテンツが所属するカテゴリを分類するための各カテゴリｍに対するモデルパラメータを学習する際に用いる、各カテゴリｍに対するｉ番目のペアのコンテンツの双対変数αｉmからなるベクトルα＾iを推定するための下位問題が置換される、シンプレックス射影問題を解くために、ベクトルμ＾及びパラメータｚを計算し、前記計算されたベクトルμ＾及びパラメータｚに基づいて、前記シンプレックス射影問題を解くことにより、ベクトルβ＾を計算し、前記計算されたベクトルβ＾に基づいて、各カテゴリｍに対するパラメータδｉmからなるベクトルδ＾ｉを計算し、前記計算されたベクトルδ＾ｉに基づいて、各カテゴリｍに対する前記双対変数αｉmからなるベクトルα＾i及び各カテゴリｍに対する前記モデルパラメータを更新するパラメータ更新部と、前記選択部による前記ペアの選択と、前記パラメータ更新部による更新と、を予め定められた収束条件を満たすまで繰り返す繰り返し判定部と、を含んで構成されている。
【００１３】
第２の発明に係るモデルパラメータ推定方法は、選択部と、パラメータ更新部と、繰り返し判定部と、を含むモデルパラメータ推定装置における、モデルパラメータ推定方法であって、前記選択部は、コンテンツと前記コンテンツが所属するカテゴリとの複数のペアからなる正解データに含まれる前記ペアを選択し、前記パラメータ更新部は、前記選択されたｉ番目のペアに基づいて、コンテンツが所属するカテゴリを分類するための各カテゴリｍに対するモデルパラメータを学習する際に用いる、各カテゴリｍに対するｉ番目のペアのコンテンツの双対変数αｉmからなるベクトルα＾iを推定するための下位問題が置換される、シンプレックス射影問題を解くために、ベクトルμ＾及びパラメータｚを計算し、前記計算されたベクトルμ＾及びパラメータｚに基づいて、前記シンプレックス射影問題を解くことにより、ベクトルβ＾を計算し、前記計算されたベクトルβ＾に基づいて、各カテゴリｍに対するパラメータδｉmからなるベクトルδ＾ｉを計算し、前記計算されたベクトルδ＾ｉに基づいて、各カテゴリｍに対する前記双対変数αｉmからなるベクトルα＾i及び各カテゴリｍに対する前記モデルパラメータを更新し、前記繰り返し判定部は、前記選択部による前記ペアの選択と、前記パラメータ更新部による更新と、を予め定められた収束条件を満たすまで繰り返す。
【００１４】
第１及び第２の発明によれば、選択部により、コンテンツとコンテンツが所属するカテゴリとの複数のペアからなる正解データに含まれるペアを選択し、パラメータ更新部により、選択されたｉ番目のペアに基づいて、コンテンツが所属するカテゴリを分類するための各カテゴリｍに対するモデルパラメータを学習する際に用いる、各カテゴリｍに対するｉ番目のペアのコンテンツの双対変数αｉmからなるベクトルα＾iを推定するための下位問題が置換される、シンプレックス射影問題を解くために、ベクトルμ＾及びパラメータｚを計算し、計算されたベクトルμ＾及びパラメータｚに基づいて、シンプレックス射影問題を解くことにより、ベクトルβ＾を計算し、計算されたベクトルβ＾に基づいて、各カテゴリｍに対するパラメータδｉmからなるベクトルδ＾ｉを計算し、計算されたベクトルδ＾ｉに基づいて、各カテゴリｍに対する双対変数αｉmからなるベクトルα＾i及び各カテゴリｍに対するモデルパラメータを更新し、繰り返し判定部により、選択部によるペアの選択と、パラメータ更新部による更新と、を予め定められた収束条件を満たすまで繰り返す。
【００１５】
このように、正解データに含まれるペアを選択し、選択されたｉ番目のペアに基づいて、各カテゴリｍに対するｉ番目のペアのコンテンツの双対変数αｉmからなるベクトルα＾iを推定するための下位問題が置換される、シンプレックス射影問題を解くために、ベクトルμ＾及びパラメータｚを計算し、計算されたベクトルμ＾及びパラメータｚに基づいて、シンプレックス射影問題を解くことにより、ベクトルβ＾を計算し、計算されたベクトルβ＾に基づいて、各カテゴリｍに対するパラメータδｉmからなるベクトルδ＾ｉを計算し、計算されたベクトルδ＾ｉに基づいて、各カテゴリｍに対する双対変数αｉmからなるベクトルα＾i及び各カテゴリｍに対するモデルパラメータを更新し、ペアの選択と、更新と、を予め定められた収束条件を満たすまで繰り返すことにより、下位問題を少ない計算量で厳密に解くことができるモデルパラメータを推定することができる。
【００１６】
また、第１及び第２の発明において、前記パラメータ更新部は、関数φ（θ）についてφ（θ）＝０を満たすθを求める求根アルゴリズム、各カテゴリｍに対応するパラメータμｍを降順に並べ替えて、パラメータμｍの部分和を求めるＳｏｒｔ法、又は各カテゴリｍに対応するパラメータμｍの並べ替えを行わずに各カテゴリｍに対応するパラメータμｍの分割する位置を決定する値を選択し、前記パラメータμｍの各々の和を繰り返し計算するＰｉｖｏｔ法を用いて、前記シンプレックス射影問題を解いてもよい。
【００１７】
また、本発明のプログラムは、コンピュータを、上記のモデルパラメータ推定装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１８】
以上説明したように、本発明のモデルパラメータ推定装置、方法、及びプログラムによれば、正解データに含まれるペアを選択し、選択されたｉ番目のペアに基づいて、下位問題が置換される、シンプレックス射影問題を解くために、ベクトルμ＾及びパラメータｚを計算し、計算されたベクトルμ＾及びパラメータｚに基づいて、シンプレックス射影問題を解くことにより、ベクトルβ＾を計算し、計算されたベクトルβ＾に基づいて、各カテゴリｍに対するパラメータδｉmからなるベクトルδ＾ｉを計算し、計算されたベクトルδ＾ｉに基づいて、各カテゴリｍに対する双対変数αｉmからなるベクトルα＾i及び各カテゴリｍに対するモデルパラメータを更新することを、予め定められた収束条件を満たすまで繰り返すことにより、下位問題を少ない計算量で厳密に解いてモデルパラメータを推定することができる。
【図面の簡単な説明】
【００１９】
【図１】モデルパラメータ推定装置の構成の例について示す図である。
【図２】本実施の形態において用いるアルゴリズムの例を示す図である。
【図３】Ｂｉｓｅｃｔｉоｎ法の詳細を示す図である。
【図４】Ｓｏｒｔ法の詳細を示す図である。
【図５】Ｐｉｖｏｔ法の詳細を示す図である。
【図６】本発明の第１の実施の形態に係るモデルパラメータ推定装置の機能的構成を示すブロック図である。
【図７】本発明の第１の実施の形態に係るモデルパラメータ推定装置のパラメータ推定部の機能的構成を示すブロック図である。
【図８】本実施の第１の形態に係るモデルパラメータ推定装置におけるモデルパラメータ推定処理ルーチンを示すフローチャート図である。
【図９】本実施の第１の形態に係るモデルパラメータ推定装置におけるカテゴリ分類処理ルーチンを示すフローチャート図である。
【図１０】実験例の結果を示す図である。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２１】
＜本実施の形態の原理＞
まず、本実施の形態における原理について説明する。本実施の形態においては、下位問題をシンプレックスへの射影問題に置き換え、射影問題を解き、双対変数、及びモデルパラメータを更新する。図１に示すように、本実施の形態に係るモデルパラメータ推定装置による処理は、「モデルパラメータの推定」と「新規のコンテンツに対するカテゴリ予測」との２つにより構成されている。
【００２２】
次に、本実施の形態における、「モデルパラメータの推定」について説明すると、モデルパラメータの推定では、所属するカテゴリが判明しているコンテンツの特徴ベクトル（ｘ＾１，ｙ１），．．．，（ｘ＾ｎ，ｙｎ）から、モデルパラメータベクトルｗ＾１，．．．，ｗ＾ｋを推定する。ここで、ｎはカテゴリが判明しているコンテンツの数を表し、ｋはカテゴリの数を表し、ｘ＾ｉは、ｉ番目のコンテンツの特徴ベクトルを表す。また、ｙｉは、ｉ番目のコンテンツの正解カテゴリであり、カテゴリ１からカテゴリｋまでの間の何れかの値である。また、ｗ＾１，．．．，ｗ＾ｋは、各カテゴリのモデルパラメータベクトルを表し、各コンテンツの特徴ベクトルｘ＾ｉと同じ次元数である。
【００２３】
また、本実施の形態における、「新規のコンテンツに対するカテゴリ予測」について説明すると、新規のコンテンツに対するカテゴリ予測では、カテゴリが判明していないコンテンツの特徴ベクトルｘ＾とモデルパラメータベクトルｗ＾１，．．．，ｗ＾ｋを用いて、上記（１）式に従って、当該コンテンツｘのカテゴリを予測する。
【００２４】
次に、モデルパラメータを推定する際に用いる双対変数からなる行列α＾の求め方について説明する。非特許文献１〜非特許文献５の方法を用いる場合、ＭＣＳＶＭの双対変数からなる行列α＾の推定値を、下記（３）式に示す二次計画問題を解くことで得ることができる。
【００２５】
【数３】
2016024502.tif 000005
【００２６】
ここで、ｎはカテゴリが判明しているコンテンツの数であり、ｋはカテゴリの総数、ｆは目的関数、α＾は双対変数をまとめたｎ×ｋの行列、αｉｍはｍ番目のカテゴリに対するｉ番目のコンテンツの双対変数である。また、ｍ＝ｙｉのとき、Ｃｉｍ＝Ｃ、Δｉｍ＝０、それ以外のとき、Ｃｉｍ＝０、Δｉｍ＝１と定義する。Ｃはユーザの任意に設定した正則化のパラメータ（Ｃ＞０）である。行列α＾の推定値を計算した後に、上記（２）式に従って、モデルパラメータベクトルｗ＾１，．．．，ｗ＾ｋの推定値を得る。
【００２７】
上記（３）式の二次計画問題を解くために、下位問題の反復計算を行う。各反復計算では、コンテンツの特徴ベクトルとカテゴリのｉ番目のペア（ｘ＾ｉ，ｙｉ）をランダムで選択し、選択したｉ番目のペア（ｘ＾ｉ，ｙｉ）について、下記（４）式の下位問題を解く。
【００２８】
【数４】
2016024502.tif 000006
【００２９】
ここで、α＾ｉ＝［αｉ１，．．．，αｉｋ］Τ、Ｃ＾ｉ＝［Ｃｉ１，．．．，Ｃｉｋ］Τ、ｇ＾ｉ＝［ｇｉ１，．．．，ｇｉｋ］Τと定義する。ｇｉｍはｆのαｉｍについての偏微分であり、ｇｉｍ＝ｗ＾ｍΤ＋ｘ＾ｉ＋Δｉｍで計算する。上記（４）式を最小化するベクトルδ＾ｉは、ベクトルα＾ｉをα＾ｉ←α＾ｉ＋δ＾ｉで更新した場合に、上記（３）式を最小化するベクトルδ＾ｉとなる。
【００３０】
本実施の形態においては、上記（４）式の下位問題を、下記（５）式に示すシンプレックス射影問題に置き換えて解く。
【００３１】
【数５】
2016024502.tif 000007
【００３２】
ここで、ベクトルμ＾とパラメータｚを下記（６）式のように定義する。
【００３３】
【数６】
2016024502.tif 000008
【００３４】
また、上記（４）式による最適な解のベクトルδ＾ｉと、上記（５）式による最適な解のベクトルβ＾には、下記（７）式に示す関係がある。
【００３５】
【数７】
2016024502.tif 000009
【００３６】
本実施の形態においては、まず、上記（５）式の問題を解き、次に、上記（７）式に従って、ベクトルδ＾ｉを取得する。そして、ベクトルδ＾ｉを取得したら、ベクトルα＾ｉとモデルパラメータベクトルｗ＾１，．．．，ｗ＾ｋとを下記（８）式に従って更新する。
【００３７】
【数８】
2016024502.tif 000010
【００３８】
ここで、δｉｍは、ベクトルδ＾ｉのｍ番目の要素である。すなわち、δ＾ｉ＝［δｉ１，．．．，δｉｋ］となる。そして、上記（５）式の問題を解き、上記（７）式に従ってベクトルδ＾ｉを取得し、上記（８）式に従って、ベクトルα＾ｉ及びモデルパラメータベクトルｗ＾１，．．．，ｗ＾ｋを更新する処理を、アルゴリズムが収束するまで繰り返す。なお、アルゴリズムが収束したか否かの判定は、例えば、更新されたベクトルα＾ｉに基づいて、最小化問題の最適条件であるＫａｒｕｓｈ−Ｋｕｈｎ−Ｔｕｃｋｅｒ（ＫＫＴ）条件を一定基準の下で満たしているか否かにより判定する。また、本実施の形態で用いるアルゴリズムの詳細を図２に示す。
【００３９】
上記（５）式を解く方法について説明する。本実施の形態においては、求根アルゴリズムの１つであるＢｉｓｅｃｔｉоｎ法、Ｓｏｒｔ法、又はＰｉｖｏｔ法の何れか１つを用いて上記（５）式を解く。
【００４０】
まず、求根アルゴリズムについて説明する。本実施の形態における求根アルゴリズムは、任意の求根アルゴリズムを用いて、下記（９）式に示す関数の根を求める。すなわち、下記（９）式の、φ（θ）＝０を満たすθを求める。図３に、本実施の形態において用いる求根アルゴリズムの一つであるＢｉｓｅｃｔｉоｎ法の詳細を示す。なお、Ｂｉｓｅｃｔｉоｎ法は、近似的な解をＯ（ｋ）時間で得ることができる。また、Ｂｉｓｅｃｔｉｏｎ法で用いる、パラメータτは、任意の正の値が予め定められているものとする。
【００４１】
【数９】
2016024502.tif 000011
【００４２】
ここで、パラメータμｍは、ベクトルμ＾の要素であり、上記（９）式によりθを取得した後、下記（１０）式に従って、ベクトルβ＾を計算する。
【００４３】
【数１０】
2016024502.tif 000012
【００４４】
次に、Ｓｏｒｔ法（非特許文献６：J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra(2008), Efficient projections onto the l1-ball for learning in high dimensions,Proceedings of the ICML conference 2008, pp. 272-279.）について説明する。本実施の形態において用いるＳｏｒｔ法の詳細を図４に示す。Ｓｏｒｔ法は、カテゴリｊに対応する入力パラメータμｊを大きい順（降順）に並べ替えて、上位ｍ個の入力パラメータの部分和
【００４５】
【数１１】
2016024502.tif 000013
【００４６】
を求めることで、カテゴリ数ｋに対してＯ（ｋｌоｇｋ）のオーダーの計算量でシンプレックスへの射影問題を厳密に解く。
【００４７】
次に、Ｐｉｖｏｔ法（非特許文献６）について説明する。本実施の形態において用いるＰｉｖｏｔ法の詳細を図５に示す。Ｐｉｖｏｔ法は、各カテゴリｊに対応するパラメータμｊを分割する位置を決定するＰｉｖｏｔ値を選択してパラメータの部分和を繰り返し計算することで、パラメータの並べ替えをせずに、Ｓｏｒｔ法で求めるパラメータの部分和
【００４８】
【数１２】
2016024502.tif 000014
【００４９】
を計算する。このＰｉｖｏｔ法を用いることにより、カテゴリ数ｋに対してＯ（ｋ）のオーダーの計算量でシンプレックスへの射影問題を厳密に解くことができる。
【００５０】
＜本発明の第１の実施の形態に係るモデルパラメータ推定装置の構成＞
次に、本発明の第１の実施の形態に係るモデルパラメータ推定装置の構成について説明する。図６に示すように、本発明の第１の実施の形態に係るモデルパラメータ推定装置１００は、入力部１０と、演算部２０と、出力部９０と、を含んで構成されている。
【００５１】
入力部１０は、所属するカテゴリが判明しているコンテンツに関する特徴ベクトルとカテゴリとの複数のペア（ｘ＾１，ｙ１），．．．，（ｘ＾ｎ，ｙｎ）からなる正解データを受け付け、正解データ記憶部３２に記憶する。また、入力部１０は、分類対象となるコンテンツの特徴ベクトルｘ＾を受け付ける。
【００５２】
演算部２０は、モデルパラメータ推定部３０と、カテゴリ予測部６０とを含んで構成されている。
【００５３】
モデルパラメータ推定部３０は、入力部１０において受け付けた正解データから、各カテゴリのモデルパラメータベクトルｗ＾１，．．．ｗ＾ｋを推定する。また、モデルパラメータ推定部３０は、正解データ記憶部３２と、初期化部３４と、パラメータ推定部３６と、モデルパラメータ記憶部５０とを含んで構成されている。
【００５４】
正解データ記憶部３２には、入力部１０において受け付けた正解データが記憶されている。
【００５５】
初期化部３４は、行列α＾とモデルパラメータベクトルｗ＾ｍの各々とを０に初期化する。
【００５６】
パラメータ推定部３６は、正解データ記憶部３２に記憶されている正解データと、初期化部３４において初期化された各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍ又は、前回更新された各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍとに基づいて、上記（５）式〜（１０）式に従って、各カテゴリｍのモデルパラメータベクトルｗ＾ｍを推定（学習）し、推定されたモデルパラメータを、モデルパラメータ記憶部５０に記憶する。また、パラメータ推定部３６は、図７に示すように、選択部４０と、パラメータ更新部４２と、繰り返し判定部４４とを備えている。
【００５７】
選択部４０は、正解データ記憶部３２に記憶されている正解データに含まれるコンテンツとカテゴリとのペアから、ランダムに１つのペアを選択する。
【００５８】
パラメータ更新部４２は、まず、選択部４０において選択されたｉ番目のペアについて、選択されたペアのコンテンツの特徴ベクトルｘ＾ｉ及びカテゴリｙｉと、予め任意の正の値が設定された正則化パラメータＣと、初期化された各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍ又は、前回更新された各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍとに基づいて、上記（６）式に従って、ベクトルμ＾及びパラメータｚを取得する。次に、取得されたベクトルμ＾及びパラメータｚと、予め任意の正の値が設定されたパラメータτとに基づいて、上記（５）式で示されるシンプレックス射影問題を、求根アルゴリズムであるＢｉｓｅｃｔｉｏｎ法を用いて解き、ベクトルβ＾を取得する。次に、選択部４０において選択されたペアのコンテンツの特徴ベクトルｘ＾ｉ及びカテゴリｙｉと、予め任意の正の値が設定された正則化パラメータＣと、初期化された各カテゴリｍの双対変数αｉｍ又は、前回更新された各カテゴリｍの双対変数αｉｍと、取得されたベクトルβ＾とに基づいて、上記（７）式に従って、ベクトルδ＾ｉを取得する。そして、取得されたベクトルδ＾ｉと、初期化された各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍ又は、前回更新された各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍとに基づいて、上記（８）式に従って、各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍを更新する。
【００５９】
繰り返し判定部４４は、パラメータ更新部４２において更新された各カテゴリｍの双対変数αｉｍに基づいて、最小化問題の最適条件であるＫａｒｕｓｈ−Ｋｕｈｎ−Ｔｕｃｋｅｒ（ＫＫＴ）条件を一定基準の下で満たしているか否かを判定し、満たしている場合には、双対変数からなる行列α＾及びモデルパラメータベクトルｗ＾ｍの各々を確定し、各カテゴリｍのモデルパラメータベクトルｗ＾ｍを、モデルパラメータ記憶部５０に記憶する。満たしていない場合には、選択部４０におけるペアの選択、パラメータ更新部４２におけるパラメータの更新、繰り返し判定部４４による判定の処理を繰り返す。
【００６０】
モデルパラメータ記憶部５０には、パラメータ更新部４２において更新された各カテゴリｍのモデルパラメータベクトルｗ＾ｍが記憶されている。
【００６１】
カテゴリ予測部６０は、入力部１０において受け付けたコンテンツの特徴ベクトルｘ＾と、モデルパラメータ記憶部５０に記憶されている各カテゴリｍのモデルパラメータベクトルｗ＾ｍとに基づいて、上記（１）に従って、カテゴリを予測し、予測したカテゴリを分類結果として出力部９０に出力する。
【００６２】
＜本発明の第１の実施の形態に係るモデルパラメータ推定装置のモデルパラメータ推定の作用＞
次に、本発明の第１の実施の形態に係るモデルパラメータ推定装置１００の作用について説明する。まず、正解データを受け付け、正解データ記憶部３２に記憶する。そして、正解データ記憶部３２から正解データを読み出すと、モデルパラメータ推定装置１００は、図８に示すモデルパラメータ推定処理ルーチンを実行する。また、モデルパラメータ推定処理ルーチンが終了すると、モデルパラメータ推定装置１００は、入力部１０から分類対象となるコンテンツの特徴ベクトルｘ＾を受け付け、図９に示すカテゴリ分類処理ルーチンを実行する。
【００６３】
まず、図８に示すモデルパラメータ推定処理ルーチンについて説明する。
【００６４】
ステップＳ１００では、行列α＾とモデルパラメータベクトルｗ＾ｍの各々との初期値を０に設定する。
【００６５】
次に、ステップＳ１０２では、読み込んだ正解データに含まれるコンテンツの特徴ベクトルとカテゴリとのペア（ｘ＾ｉ、ｙｉ）をランダムに選択する。
【００６６】
次に、ステップＳ１０４では、上記ステップＳ１０２で選択されたｉ番目のペアについて、ステップＳ１００において取得した各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍ、又は、ステップＳ１０８において前回更新された各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍと、ステップＳ１０２において取得したペアのコンテンツの特徴ベクトルｘ＾ｉ及びカテゴリｙｉと、予め設定されているパラメータＣと、に基づいて、上記（６）式に従って、ベクトルμ＾及びパラメータｚを計算する。
【００６７】
次に、ステップＳ１０６では、ステップＳ１０４において取得したベクトルμ＾及びパラメータｚと、予め設定されているパラメータτと、に基づいて、上記（５）式に示すシンプレックス射影問題を、求根アルゴリズムであるＢｉｓｅｃｔｉｏｎ法を用いて解き、ベクトルβ＾を取得する。
【００６８】
次に、ステップＳ１０８では、ステップＳ１００において取得した各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍ、又は、ステップＳ１０８において前回更新された各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍと、ステップＳ１０２において取得したペアのコンテンツの特徴ベクトルｘ＾ｉ及びカテゴリｙｉと、ステップＳ１０６において取得したベクトルβ＾と、予め設定されているパラメータＣとに基づいて、上記（７）式に従って、ベクトルδ＾ｉを計算し、取得したベクトルδ＾ｉに基づいて、上記（８）式に従って、各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍを更新する。
【００６９】
ステップＳ１１０では、ステップＳ１０８において取得した各カテゴリｍの双対変数αｉｍに基づいて、予め定められた収束条件を満たしているか否かを判定する。収束条件を満たしている場合には、ステップＳ１１２へ移行し、収束条件を満たしていない場合には、ステップＳ１０２へ移行し、ステップＳ１０２〜ステップＳ１１０の処理を繰り返す。
【００７０】
ステップＳ１１２では、ステップＳ１０８において取得した各カテゴリｍのモデルパラメータベクトルｗ＾ｍを、モデルパラメータ記憶部５０に記憶して、モデルパラメータ推定処理ルーチンを終了する。
【００７１】
次に、図９に示すカテゴリ分類処理ルーチンについて説明する。
【００７２】
まず、ステップＳ２００では、モデルパラメータ記憶部５０に記憶されている各カテゴリｍのモデルパラメータベクトルｗ＾ｍを読み込む。
【００７３】
次に、ステップＳ２０２では、入力部１０において受け付けた分類対象となるコンテンツの特徴ベクトルｘ＾と、ステップＳ２００において取得した各カテゴリｍのモデルパラメータベクトルｗ＾ｍとに基づいて、上記（１）に従って、当該コンテンツのカテゴリを取得し、出力部９０に取得したカテゴリを出力して、カテゴリ分類処理ルーチンを終了する。
【００７４】
以上説明したように、本発明の第１の実施の形態に係るモデルパラメータ推定装置によれば、正解データに含まれるペアを選択し、選択されたｉ番目のペアに基づいて、下位問題が置換される、シンプレックス射影問題を解くために、ベクトルμ＾及びパラメータｚを計算し、計算されたベクトルμ＾及びパラメータｚに基づいて、求根アルゴリズムに従って、シンプレックス射影問題を解くことにより、ベクトルβ＾を計算し、計算されたベクトルβ＾に基づいて、各カテゴリｍに対するパラメータδｉmからなるベクトルδ＾ｉを計算し、計算されたベクトルδ＾ｉに基づいて、各カテゴリｍに対する双対変数αｉmからなるベクトルα＾i及び各カテゴリｍに対するモデルパラメータを更新することを、予め定められた収束条件を満たすまで繰り返すことにより、下位問題を少ない計算量で厳密に解いてモデルパラメータを推定することができる。
【００７５】
また、カテゴリ数ｋに対して下位問題を厳密にＯ（ｋ）の計算量で解くことができる。下位問題を厳密に解くことで、双対変数の推定値の収束に要する反復計算の回数が少なく、従来手法より短い計算時間で高い分類精度を与えるモデルパラメータ値を得ることが期待できる。特に、カテゴリが判明しているコンテンツ数とカテゴリ数とが大きい大規模データに対して効果がある。
【００７６】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００７７】
例えば、本実施の形態においては、アルゴリズムの収束条件を満たしているか否かを判定するために、ＫＫＴ条件を一定基準の下で満たしているか否かにより判定する場合について説明したが、これに限定されるものではなく、全てのα＾ｉが更新された場合であって、かつ、行列α＾と前回更新された各カテゴリｍの双対変数αｉｍの値を反映した行列α＾との差分が、予め定められた一定の以下になる場合に、アルゴリズムの収束条件を満たしていると判定してもよい。
【００７８】
また、本実施の形態においては、入力される正解データはコンテンツの特徴ベクトルｘ＾ｉを含む場合を例に説明したがこれに限定されるものではない。例えば、入力される正解データは、コンテンツのデータを含み、モデルパラメータ推定装置１００において当該コンテンツの特徴ベクトルを抽出するようにしてもよい。
【００７９】
次に、第２の実施の形態に係るモデルパラメータ推定装置について説明する。
【００８０】
第２の実施の形態においては、モデルパラメータ推定装置１００の、パラメータ推定部３６のパラメータ更新部４２において、上記（５）式に示すシンプレックス射影問題を、Ｓｏｒｔ法を用いて解いている点が第１の実施の形態と異なる。なお、第１の実施の形態に係るモデルパラメータ推定装置１００と同様の構成及び作用については、同一の符号を付して説明を省略する。
【００８１】
パラメータ更新部４２は、まず、選択部４０において選択されたｉ番目のペアについて、選択されたペアのコンテンツの特徴ベクトルｘ＾ｉ及びカテゴリｙｉと、予め任意の正の値が設定された正則化パラメータＣと、初期化された各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍ又は、前回更新された各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍとに基づいて、上記（６）式に従って、ベクトルμ＾及びパラメータｚを取得する。次に、取得されたベクトルμ＾及びパラメータｚと、に基づいて、上記（５）式に示すシンプレックス射影問題を、Ｓｏｒｔ法を用いて解き、ベクトルβ＾を取得する。次に、上記（７）式に従って、δ＾ｉを取得する。そして、上記（８）式に従って、各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍを更新する。
【００８２】
なお、第２の実施の形態に係るモデルパラメータ推定装置の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【００８３】
以上説明したように、本発明の第２の実施の形態に係るモデルパラメータ推定装置によれば、正解データに含まれるペアを選択し、選択されたｉ番目のペアに基づいて、下位問題が置換される、シンプレックス射影問題を解くために、ベクトルμ＾及びパラメータｚを計算し、計算されたベクトルμ＾及びパラメータｚに基づいて、Ｓｏｒｔ法に従って、シンプレックス射影問題を解くことにより、ベクトルβ＾を計算し、計算されたベクトルβ＾に基づいて、各カテゴリｍに対するパラメータδｉmからなるベクトルδ＾ｉを計算し、計算されたベクトルδ＾ｉに基づいて、各カテゴリｍに対する双対変数αｉmからなるベクトルα＾i及び各カテゴリｍに対するモデルパラメータを更新することを、予め定められた収束条件を満たすまで繰り返すことにより、下位問題を少ない計算量で厳密に解いてモデルパラメータを推定することができる。
【００８４】
また、カテゴリ数ｋに対して下位問題を厳密にＯ（ｋｌｏｇｋ）の計算量で解くことができる。下位問題を厳密に解くことで、双対変数の推定値の収束に要する反復計算の回数が少なく、従来手法より短い計算時間で高い分類精度を与えるモデルパラメータ値を得ることが期待できる。
【００８５】
次に、第３の実施の形態に係るモデルパラメータ推定装置について説明する。
【００８６】
第３の実施の形態においては、モデルパラメータ推定装置１００の、パラメータ推定部３６のパラメータ更新部４２において、上記（５）式に示すシンプレックス射影問題を、Ｐｉｖｏｔ法を用いて解いている点が第１の実施の形態と異なる。なお、第１の実施の形態に係るモデルパラメータ推定装置１００と同様の構成及び作用については、同一の符号を付して説明を省略する。
【００８７】
パラメータ更新部４２は、まず、選択部４０において選択されたｉ番目のペアについて、選択されたペアのコンテンツの特徴ベクトルｘ＾ｉ及びカテゴリｙｉと、予め任意の正の値が設定された正則化パラメータＣと、初期化された各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍ又は、前回更新された各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍとに基づいて、上記（６）式に従って、ベクトルμ＾及びパラメータｚを取得する。次に、取得されたベクトルμ＾及びパラメータｚと、に基づいて、上記（５）式に示すシンプレックス射影問題を、Ｐｉｖｏｔ法を用いて解き、ベクトルβ＾を取得する。次に、上記（７）式に従って、ベクトルδ＾ｉを取得する。そして、上記（８）式に従って、各カテゴリｍの双対変数αｉｍ及びモデルパラメータベクトルｗ＾ｍを更新する。
【００８８】
なお、第３の実施の形態に係るモデルパラメータ推定装置の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【００８９】
＜実験例＞
本実施の形態におけるモデルパラメータ推定装置に、２種類の公開データを用いた実験例を図１０に示す。図１０のＮｅｗｓ２０は、２０のカテゴリに属する１８，８４６個の文書のデータである。各文書は、１３０，０８８次元の特徴ベクトルとして表現されている。図１０のＳｅｃｔｏｒは１０５のカテゴリに属する９，６１９個の文書のデータである。各文書は５５，１９７次元の特徴ベクトルとして表現されている。文書の７５％をモデルパラメータの値の推定に用い、残りの２５％の文書をカテゴリ予測の精度評価に用いている。図１０の右の２つのグラフより、本実施の形態に用いるＰｉｖоｔ法では、目的関数値を小さくする最適な双対変数の推定値に短い計算時間で近づくことができる。また、左の２つのグラフより、Ｐｉｖоｔ法を用いることにより、高い分類精度を与えるパラメータ値に短い計算時間で近づく傾向があるといえる。なお、図１０の左は、評価データに対する性能であり、高いほうが良く、一方図１０の右は、目的関数（双対問題）に対する目的値であり、低いほうが良い。
【００９０】
以上説明したように、本発明の第３の実施の形態に係るモデルパラメータ推定装置によれば、正解データに含まれるペアを選択し、選択されたｉ番目のペアに基づいて、下位問題が置換される、シンプレックス射影問題を解くために、ベクトルμ＾及びパラメータｚを計算し、計算されたベクトルμ＾及びパラメータｚに基づいて、Ｐｉｖｏｔ法に従って、シンプレックス射影問題を解くことにより、ベクトルβ＾を計算し、計算されたベクトルβ＾に基づいて、各カテゴリｍに対するパラメータδｉmからなるベクトルδ＾ｉを計算し、計算されたベクトルδ＾ｉに基づいて、各カテゴリｍに対する双対変数αｉmからなるベクトルα＾i及び各カテゴリｍに対するモデルパラメータを更新することを、予め定められた収束条件を満たすまで繰り返すことにより、下位問題を少ない計算量で厳密に解いてモデルパラメータを推定することができる。
【００９１】
また、上記（４）式を、上記（５）式に置き換えることにより、下位問題をＯ（ｋ）時間で解くことができるＰｉｖｏｔ法を適用することができる。
【００９２】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００９３】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能であるし、ネットワークを介して提供することも可能である。
【符号の説明】
【００９４】
１０   入力部
２０   演算部
３０   モデルパラメータ推定部
３２   正解データ記憶部
３４   初期化部
３６   パラメータ推定部
４０   選択部
４２   パラメータ更新部
４４   判定部
５０   モデルパラメータ記憶部
６０   カテゴリ予測部
９０   出力部
１００ モデルパラメータ推定装置
【図６】
2016024502.tif 000019
【図７】
2016024502.tif 000020
【図８】
2016024502.tif 000021
【図９】
2016024502.tif 000022
【図１】
2016024502.tif 000023
【図２】
2016024502.tif 000024
【図３】
2016024502.tif 000025
【図４】
2016024502.tif 000026
【図５】
2016024502.tif 000027
【図１０】
2016024502.tif 000028