(57)【要約】【課題】サポートベクターマシンの計算コストを低減させる。【解決手段】パラメータ計算部１３は、行列に含まれるデータポイントごとに、サポートベクターマシンで用いられるマージンパラメータに基づく所定のパラメータについて、該パラメータの上限値および下限値を計算する。集合設定部１４は、データポイントのうち、所定のパラメータが、上限値以下かつ下限値以上であるデータポイントの集合を設定する。超平面計算部１５は、集合に含まれるデータポイントおよびマージンパラメータを基に、サポートベクターマシンの超平面を計算する。【選択図】図１
2019185198.tif 000002
【特許請求の範囲】
【請求項１】
行列に含まれるデータポイントごとに、サポートベクターマシンで用いられるマージンパラメータに基づく所定のパラメータについて、該パラメータの上限値および下限値を計算するパラメータ計算部と、
前記データポイントのうち、前記所定のパラメータが、前記上限値以下かつ前記下限値以上であるデータポイントの集合を設定する集合設定部と、
前記集合に含まれるデータポイントおよび前記マージンパラメータを基に、サポートベクターマシンの超平面を計算する超平面計算部と、
を有することを特徴とする計算装置。
【請求項２】
前記集合設定部は、前記データポイントのうち、前記下限値および前記上限値が第１の条件を満たすデータポイントを、前記集合に含めることを特徴とする請求項１に記載の計算装置。
【請求項３】
前記行列に含まれるデータポイントであって、前記集合に含まれないデータポイントが、前記超平面計算部によって計算された超平面を基に設定された第２の条件を満たすか否かを確認する確認部をさらに有し、
前記集合設定部は、前記確認部によって前記第２の条件を満たすことが確認されたデータポイントを前記集合に追加することを特徴とする請求項１または２に記載の計算装置。
【請求項４】
前記行列の要素の値のスケーリングおよびシフトを行うことによって、疎行列を計算する疎行列計算部をさらに有し、
前記パラメータ計算部は、前記疎行列のデータポイントごとに前記上限値および前記下限値を計算し、
前記集合設定部は、前記疎行列のデータポイントを基に前記集合を設定することを特徴とする請求項１から３のいずれか１項に記載の計算装置。
【請求項５】
前記疎行列計算部は、前記行列の最頻値に基づく重みを計算し、前記行列の要素のうち値が前記最頻値と等しい要素の値が０になるように、前記行列の要素の値を前記重みでスケーリングし、所定の定数でシフトすることを特徴とする請求項４に記載の計算装置。
【請求項６】
コンピュータが実行する計算方法であって、
行列に含まれるデータポイントごとに、サポートベクターマシンで用いられるマージンパラメータに基づく所定のパラメータについて、該パラメータの上限値および下限値を計算するパラメータ計算工程と、
前記データポイントのうち、前記所定のパラメータが、前記上限値以下かつ前記下限値以上であるデータポイントの集合を設定する集合設定工程と、
前記集合に含まれるデータポイントおよび前記マージンパラメータを基に、サポートベクターマシンの超平面を計算する超平面計算工程と、
を含むことを特徴とする計算方法。
【請求項７】
コンピュータを、請求項１から５のいずれか１項に記載の計算装置として機能させるための計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算装置、計算方法および計算プログラムに関する。
【背景技術】
【０００２】
従来、機械学習による識別器として、サポートベクターマシン（ＳＶＭ：Support  Vector  Machine）が知られている。サポートベクターマシンは、データポイントから超平面を学習し、超平面を基にデータポイントを２つのクラスに分類するものである。また、超平面を求めるための高速なソルバとしてＳＭＯ（Sequential  Minimal  Optimization）が提案されている（例えば、非特許文献１を参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】John  Platt,  Sequential  Minimal  Optimization:  A  Fast  Algorithm  for  Training  Support  Vector  Machines,  1998.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来のサポートベクターマシンには、計算コストが高いという問題がある。例えば、ＳＭＯでは、データポイントの数がＮである場合、超平面を求めるためにＮ個の制約を持つ２次計画問題を解く必要がある。このとき、ＳＭＯの計算量は、データポイントの数の２乗に比例して増加する。さらに、サポートベクターマシンには、マージンの幅を決定するマージンパラメータなど複数のパラメータがあるため、パラメータを決定するためのグリッドサーチにも多くの計算コストが必要となる。
【課題を解決するための手段】
【０００５】
本発明の計算装置は、行列に含まれるデータポイントごとに、サポートベクターマシンで用いられるマージンパラメータに基づく所定のパラメータについて、該パラメータの上限値および下限値を計算するパラメータ計算部と、前記データポイントのうち、前記所定のパラメータが、前記上限値以下かつ前記下限値以上であるデータポイントの集合を設定する集合設定部と、前記集合に含まれるデータポイントおよび前記マージンパラメータを基に、サポートベクターマシンの超平面を計算する超平面計算部と、を有することを特徴とする。
【発明の効果】
【０００６】
本発明によれば、サポートベクターマシンの計算コストを低減させることができる。
【図面の簡単な説明】
【０００７】
【図１】図１は、第１の実施形態に係る計算装置の構成の一例を示す図である。
【図２】図２は、第１の実施形態に係る疎行列計算部の構成の一例を示す図である。
【図３】図３は、第１の実施形態に係る集合設定部の構成の一例を示す図である。
【図４】図４は、第１の実施形態に係る確認部の構成の一例を示す図である。
【図５】図５は、定義１を示す図である。
【図６】図６は、補題１を示す図である。
【図７】図７は、補題２を示す図である。
【図８】図８は、補題３を示す図である。
【図９】図９は、補題４を示す図である。
【図１０】図１０は、定義２を示す図である。
【図１１】図１１は、補題５を示す図である。
【図１２】図１２は、補題６を示す図である。
【図１３】図１３は、補題７を示す図である。
【図１４】図１４は、定理１および定理２を示す図である。
【図１５】図１５は、補題８を示す図である。
【図１６】図１６は、第１の実施形態に係る計算処理のアルゴリズムの一例を示す図である。
【図１７】図１７は、第１の実施形態に係る計算処理のアルゴリズムの一例を示す図である。
【図１８】図１８は、第１の実施形態に係る計算処理のアルゴリズムの一例を示す図である。
【図１９】図１９は、第１の実施形態に係る計算処理のアルゴリズムの一例を示す図である。
【図２０】図２０は、第１の実施形態に係る計算処理の流れを示すフローチャートである。
【図２１】図２１は、第１の実施形態に係る計算処理の流れを示すフローチャートである。
【図２２】図２２は、第１の実施形態に係る計算処理の流れを示すフローチャートである。
【図２３】図２３は、第１の実施形態に係る計算処理の流れを示すフローチャートである。
【図２４】図２４は、実施形態に係る計算プログラムを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【０００８】
以下に、本願に係る計算装置、計算方法および計算プログラムの実施形態を図面に基づいて詳細に説明する。なお、本発明は、以下に説明する実施形態により限定されるものではない。
【０００９】
［従来のＳＶＭ］
まず、従来のＳＶＭについて説明する。ここで、Ｎをデータポイントの数としたとき、ＳＶＭには、データセット｛（ｘｉ，ｙ［ｉ］）：ｉ＝１，２，・・・，Ｎ｝が与えられるとする。ベクトルｘｉは、Ｍ次元空間におけるｉ番目のデータポイントとし、行列Ｘのｉ番目の行ベクトルとする。スカラｙ［ｉ］∈｛＋１，−１｝は、データポイントｘｉのラベルである。また、特徴量空間における超平面は、式（１）となる。
【００１０】
【数１】
2019185198.tif 000003
【００１１】
ここで、ｗはＭ次元のベクトルであり、ｂはスカラである。最適な超平面は、以下の式（２）および（３）の最適化問題を解くことで求められる。
【００１２】
【数２】
2019185198.tif 000004
【００１３】
ここで、｜｜・｜｜はベクトルのＬ２ノルムであり、ξ［ｉ］はスラック変数であり、Ｃはマージンパラメータである。スラック変数ξ［ｉ］≧０は、データポイントと超平面の距離であり、データポイントが超平面の間違った方にあると正の値を取る。マージンパラメータＣ＞０は、マージン誤差とマージン最大化のトレードオフをコントロールするパラメータである。この最適化問題は、ＫＫＴ（Karush-Kuhn-Tucker）条件から双対問題にすることができる。α［ｉ］とβ［ｉ］をラグランジュ乗数としたとき、最適解は以下の式（４）のラグランジュ関数を最小化することで求められる。
【００１４】
【数３】
2019185198.tif 000005
【００１５】
ここで、ξ、α、βは、それぞれξ［ｉ］、α［ｉ］、β［ｉ］のベクトルとする。式（２）が極値をとったとき、以下の式（５）から（７）に示す条件が成り立つ。
【００１６】
【数４】
2019185198.tif 000006
【００１７】
式（５）から（７）を、式（２）および（３）へ代入することにより、以下の式（８）および（９）が得られる。
【００１８】
【数５】
2019185198.tif 000007
【００１９】
ここで、α≠０となるようなデータポイントは、サポートベクトルと呼ばれる。サポートベクトルは、サポートベクターマシンにおける超平面の形に影響を与える。
【００２０】
ここで、データポイントを高次元空間へ変換した場合であっても、超平面を計算することができる。φを、データポイントを高次元空間へマッピングする関数とすると、カーネル関数はＫ（ｘｉ，ｘｊ）＝＜φ（ｘｉ），φ（ｘｊ）＞となる。ここで、＜・，・＞は、ベクトルの内積である。すなわち、カーネル関数は、２つのベクトルφ（ｘｉ）とφ（ｘｊ）の内積である。カーネル関数としてはＲＢＦカーネルが知られており、以下の式（１０）ように与えられる。
【００２１】
【数６】
2019185198.tif 000008
【００２２】
カーネル関数を用いることで、双対問題は以下の式（１１）および（１２）のようになる。
【００２３】
【数７】
2019185198.tif 000009
【００２４】
ｚ＝（ｘ，α，β）＝Σｉ＝１ｎα［ｉ］ｙ［ｉ］Ｋ（ｘ，ｘｉ）＋ｂとすると、サポートベクターマシンによる分類器は以下の式（１３）のように与えられる。
【００２５】
【数８】
2019185198.tif 000010
【００２６】
式（１１）および（１２）は、Ｎ個の制約を持つ２次計画問題である。ここで、式（１３）から、サポートベクターマシンにより分類を行うには、ラグランジュ乗数とｂが必要となることがわかる。ベクトルαの最適解は、ソルバを適用することで求めることができ、ｂは、ベクトルαと０＜α［ｉ］＜Ｃを満たすデータポイントから、ｂ＝ｙ［ｉ］−Σｘｊ∈Ｘα［ｉ］ｙ［ｉ］Ｋ（ｘｉ，ｘｊ）として求めることができる。式（１３）において、データポイントｘｉが正しく分類できているとき、ｙ［ｉ］ｆ（ｘｉ）≧１となり、そうでないとき、ｙ［ｉ］ｆ（ｘｉ）＜１となる。
【００２７】
［第１の実施形態］
マージンパラメータＣは、マージン最大化と誤差に対する許容度のトレードオフを調整する働きがあるため、精度に大きな影響を与える。一般的に、マージンパラメータＣは、グリッドリサーチによって求められる。グリッドリサーチでは、マージンパラメータを少しずつ変えながら学習を行い。最適な値を求める。しかし、グリッドサーチでは計算コストが増大し、さらに、ソルバの計算量はデータポイントの２乗に比例して大きくなるため、大規模なデータに対しサポートベクターマシンを行うことは困難である。
【００２８】
そこで、本実施形態の計算装置は、ＳＶＭの計算コストを低減させるため、データポイントの枝狩りを行う。具体的には、計算装置は、枝狩りされたデータポイントに対し、α［ｉ］＝０、またはα［ｉ］＝Ｃとし、その他のデータポイントに対してソルバを適用することで、ラグランジュ乗数を計算する。データポイントを枝狩りするためにパラメータＺ（ｘ，α，ｂ）の上限値および下限値を計算する。計算装置は、特異値分解を利用することで、上限値と下限値を高速に計算することができる。さらに、計算装置は、高速に計算を行うために、与えられたデータ行列から疎な行列を求める。疎な行列の次元数は、元のデータ行列と同じであるが、非零要素の数が少ないため、高速な処理が可能となる。
【００２９】
図１を用いて、第１の実施形態の構成について説明する。図１は、第１の実施形態に係る計算装置の構成の一例を示す図である。図１に示すように、計算装置１０は、ＳＶＤ計算部１１、疎行列計算部１２、パラメータ計算部１３、集合設定部１４、超平面計算部１５、スコア更新部１６および確認部１７を有する。
【００３０】
ＳＶＤ計算部１１は、与えられたデータの特異値分解を行う。疎行列計算部１２は、行列の要素の値のスケーリングおよびシフトを行うことによって、疎行列を計算する。また、疎行列計算部１２は、行列の最頻値に基づく重みを計算し、行列の要素のうち値が最頻値と等しい要素の値が０になるように、行列の要素の値を重みでスケーリングし、所定の定数でシフトすることができる。
【００３１】
パラメータ計算部１３は、行列に含まれるデータポイントごとに、サポートベクターマシンで用いられるマージンパラメータに基づく所定のパラメータ（以降、パラメータｚ）について、該パラメータの上限値および下限値を計算する。また、パラメータ計算部１３は、疎行列のデータポイントごとに上限値および下限値を計算することができる。
【００３２】
集合設定部１４は、データポイントのうち、所定のパラメータが、上限値以下かつ下限値以上であるデータポイントの集合を設定する。また、集合設定部１４は、データポイントのうち、下限値および上限値が第１の条件を満たすデータポイントを、集合に含めることができる。また、集合設定部１４は、確認部１７によって第２の条件を満たすことが確認されたデータポイントを集合に追加することができる。また、集合設定部１４は、疎行列のデータポイントを基に集合を設定することができる。
【００３３】
超平面計算部１５は、集合に含まれるデータポイントおよびマージンパラメータを基に、サポートベクターマシンの超平面を計算する。スコア更新部１６は、パラメータ計算部１３によって用いられるデータポイントに対するスコアの更新を行う。
【００３４】
確認部１７は、行列に含まれるデータポイントであって、集合に含まれないデータポイントが、超平面計算部１５によって計算された超平面を基に設定された第２の条件を満たすか否かを確認する。
【００３５】
また、図２に示すように、疎行列計算部１２は、並び替え部１２１、最頻要素計算部１２２、重み計算部１２３および要素計算部１２４を有する。図２は、第１の実施形態に係る疎行列計算部の構成の一例を示す図である。並び替え部１２１は、行列Ｘのｉ番目のベクトルの要素をソートする。最頻要素計算部１２２は、ソートされた要素から最頻値を計算する。重み計算部１２３は、最頻値を基にスケーリングのための重みを計算する。
【００３６】
また、図３に示すように、集合設定部１４は、初期化部１４１、上下限計算部１４２およびデータポイント追加部１４３を有する。図３は、第１の実施形態に係る集合設定部の構成の一例を示す図である。初期化部１４１は、集合を初期化する。上下限計算部１４２は、パラメータｚの上限値および下限値を計算する。データポイント追加部１４３は、上限値および下限値に関する所定の条件を満たすデータポイントを集合に追加する。
【００３７】
また、図４に示すように、確認部１７は、初期化部１７１、集合Ｓ確認部１７２および集合Ｎ確認部１７３を有する。図４は、第１の実施形態に係る確認部の構成の一例を示す図である。初期化部１７１は、集合を初期化する。集合Ｓ確認部１７２は、集合Ｓのデータポイントのうち、所定の条件を満たすものを集合Ｃに移行させる。集合Ｎ確認部１７３は、集合Ｎのデータポイントのうち、所定の条件を満たすものを集合Ｃに移行させる。集合Ｃ、集合Ｓおよび集合Ｎについては後述する。
【００３８】
最適なラグランジュ乗数α＊とスカラｂ＊によるパラメータｚ（ｘ，α＊，ｂ＊）から与えられる最適な超平面をｆ＊（ｘ）としたとき、パラメータ計算部１３は、パラメータｚ（ｘ，α＊，ｂ＊）を、すべてのデータポイントの集合Ｘに対してソルバを適用することで計算することができる。計算コストを下げるため、集合設定部１４は、集合Ｃ⊆集合Ｘであるような集合Ｃを設定する。
【００３９】
もし、データポイントｘｉが集合Ｃに含まれていれば、当該データポイントのラグランジュ乗数は、α［ｉ］＝０またはα［ｉ］＝Ｃになる。集合Ｃを求めるために、ラグランジュ乗数α´とスカラｂ´から求められるパラメータｚ（ｘ，α´，ｂ´）で与えられる準最適な超平面ｆ´（ｘ）が用いられる。
【００４０】
ｚ￣（ｘ，α´，ｂ´）およびｚ＿（ｘ，α´，ｂ´）を、それぞれパラメータｚ（ｘ，α´，ｂ´）の上限値および下限値とすると、集合Ｃは、ソルバを適用する前に、図５の定義１のように初期化される。図５は、定義１を示す図である。なお、ｚ￣は、ｚの直上に￣があることを示す。また、ｚ＿は、ｚの直下に＿があることを示す。なお、定義１の条件は、第１の条件の一例である。
【００４１】
集合設定部１４が集合Ｃを設定する場合、パラメータ計算部１３は、まずｚ￣（ｘ，α´，ｂ´）およびｚ＿（ｘ，α´，ｂ´）を計算する。そして、データポイントｘｉが定義１の条件を満たす場合にｚ（ｘ，α´，ｂ´）を計算する。ここで、集合Ｃは、図６の補題１および図７の補題２に示す性質を持つ。図６は、補題１を示す図である。また、図７は、補題２を示す図である。
【００４２】
補題１と補題２は、データポイントｘｉに対してα［ｉ］＝０またはα［ｉ］＝Ｃが成り立つため、ソルバを適用する前に上限値および下限値を用いてラグランジュ乗数が分かることを示している。つまり、そのようなデータポイントに対しては、ソルバを適用する必要がない。このことは、図１４に示す定理１および定理２から導出される、図８の補題３に示す集合Ｃの性質に基づいている。図１４は、定理１および定理２を示す図である。また、図８は、補題３を示す図である。
【００４３】
補題３より、集合設定部１４は、集合Ｃに含まれるデータポイントにソルバを適用し、補題１および補題２によって求められるデータポイントに対しては、α［ｉ］＝０またはα［ｉ］＝Ｃとする。集合設定部１４は、集合Ｃを定義１により初期化し、学習の処理において逐次的に更新していく。
【００４４】
確認部１７は、計算された超平面の最適性を確認する。ここで、集合Ｓを、ソルバ適用前のラグランジュ乗数α［ｉ］＝０であったデータポイントの集合とする。また、集合Ｎを、ソルバ適用前のラグランジュ乗数α［ｉ］＝Ｃであったデータポイントの集合とする。このとき、確認部１７は、図９の補題４に示す方法で最適性を確認する。なお、補題４の条件は、第２の条件の一例である。
【００４５】
確認部１７は、補題４により最適性を確認するために、まずｚ￣（ｘ，α，ｂ）およびｚ＿（ｘ，α，ｂ）を計算する。そして、そして、データポイントｘｉがｚ￣（ｘ，α，ｂ）−１＜０またはｚ＿（ｘ，α，ｂ）−１＞０を満たす場合にｚ（ｘ，α，ｂ）を計算する。
【００４６】
パラメータ計算部１３によるパラメータｚの上限値および下限値の計算方法について説明する。本実施形態では、パラメータ計算部１３は、ＲＢＦカーネルに対して上限値および下限値を計算する場合について説明するが、パラメータ計算部１３は、他のカーネルに対して上限値および下限値を計算してもよい。
【００４７】
なお、ＳＶＤ計算部１１によって、入力された行列のＳＶＤ近似が行われているため、パラメータ計算部１３は、高速に上限値および下限値を計算することができる。ここで、ｍをＳＶＤのランクとすると、ＳＶＤ計算部１１は、学習処理の開始時に１度だけＯ（ＮＭｌｏｇｍ）のコストでＳＶＤを計算する（参考文献：Nathan  Halko,  Per-Gunnar  Martinsson,  and  Joel  A.  Tropp,  Finding  Structure  with  Randomness:Probabilistic  Algorithms  for  Constructing  Approximate  Matrix  Decompositions,  2011.）。
【００４８】
行列Ｖをユニタリ行列とし、Ｘ〜を行列Ｘの変換行列とする。なお、Ｘ〜は、Ｘの直上に〜があることを示す。行列Ｘは、ＳＶＤによりＸ≒Ｘ〜Ｖと表される。さらに、上限値と下限値を計算するために、集合Ｄと集合ＵをＤ＝｛ｘｉ：α［ｉ］＝Ｃ｝、Ｕ＝｛ｘｉ：０＜α［ｉ］＜Ｃ｝と定義する。ここで、集合Ｄおよび集合Ｕは、ラグランジュ乗数を計算する過程で逐次的に計算できることは明らかである。ベクトルｒｉ＝（ｒｉ［１］，ｒｉ［２］，・・・，ｒｉ［Ｍ−ｍ］）のそれぞれがｒｉ［ｊ］＝ｘｉ〜［ｍ＋ｊ］として与えられたとすると、上限値および下限値の定義は、図１０の定義２で表される。図１０は、定義２を示す図である。
【００４９】
定義２において、パラメータ計算部１３は、スコアＦ（ｘｉ）を逐次的に計算することができる。これは、学習処理において集合Ｄを逐次的に計算できるからである。さらに、ピタゴラスの定理より、｜｜ｒｉ｜｜２＝｜｜ｘｉ｜｜２＋｜｜ｘｊ〜｜｜２が成り立つため、｜｜ｒｉ｜｜２は、Ｏ（Ｍ＋ｍ）の計算コストで学習の前に求めることができる。上限値と下限値の性質を図１１の補題５に示す。図１１は、補題５を示す図である。
【００５０】
パラメータ計算部１３は、上限値と下限値の計算において、スコアＦ（ｘｉ）を、集合Ｄから逐次的に計算することはできるが、集合Ｄにデータポイントを追加または削除するたびに、Ｏ（Ｍ）の計算コストが必要になってしまう。そのため、本実施形態では、パラメータ計算部１３は、疎行列計算部１２によって計算された疎行列を用いて計算を行うことで、計算コストを低減させている。
【００５１】
Ｘ＾を行列Ｘから計算された疎行列であるとする。なお、Ｘ＾は、Ｘの直上に＾があることを示す。疎行列計算部１２は、行列Ｘの要素をスケーリング、またはシフトすることでＸ＾の非零要素を少なくする。ｘｉ＾［ｊ］を変換行列の（ｉ，ｊ）要素とすると、疎行列計算部１２は、行列Ｘ＾の要素ｘｉ＾［ｊ］を、式（３３）のように計算する。
【００５２】
【数９】
2019185198.tif 000011
【００５３】
Ｄ＝ｄｉａｇ（ω１，ω２，・・・，ωＭ）を重みの対角行列とし、Ｄ−１を行列Ｄの逆行列とすると、疎行列計算部１２は、行列Ｘ＾の要素ｘｉ＾［ｊ］を利用するときに、行列Ｄ−１を利用する。行列Ｄ−１のサイズは、Ｍ×Ｍであるが、行列Ｄは対角行列であるため、疎行列計算部１２は、行列Ｄ−１を行列ＤからＯ（Ｍ３）のコストで求めることができる。ｘｉ＾＝（ｘｉ＾［１］，ｘｉ＾［２］，・・・，ｘｉ＾［Ｍ］）を行列Ｘ＾のｉ番目の行ベクトルとすると、図１２の補題６に示す性質が成り立つ。
【００５４】
補題６は、式（２５）および（３４）から、Ｆ（ｘｉ）＝Σｘｊ∈Ｄｙ［ｊ］ｅＡ（ただし、Ａ＝−γ｜｜（ｘ＾ｉ−ｘ＾ｊ）Ｄ−１｜｜２）となるため、疎行列計算部１２は、｜｜（ｘ＾ｉ−ｘ＾ｊ）Ｄ−１｜｜２を計算することにより行列Ｘの代わりに行列Ｘ＾からスコアＦ（ｘｉ）を計算することができる。
【００５５】
［第１の実施形態のアルゴリズム］
図１６から図１９は、第１の実施形態に係る計算処理のアルゴリズムの一例を示す図である。図１６に示すように、Algorithm１では、計算装置１０は、まず行列ＸのＳＶＤを計算し、疎行列Ｘ＾をAlgorithm２を用いて計算する（１−２行目）。
【００５６】
そして、計算装置１０は、マージンパラメータＣｔに対して超平面を計算する（３−８行目）。この処理ではデータポイントｘｉにおいて、もしα［ｉ］≠Ｃｔ−１がマージンパラメータに対して成り立てば、α［ｉ］≠ＣｔがマージンパラメータＣｔに対してなるという知見に基づいている。この知見から、もしｔ≠１であれば、計算装置１０は、ラグランジュ乗数α［ｉ］を以前のマージンパラメータＣｔ−１におけるラグランジュ乗数を参考にすることで初期化する（９−１１行目）。なお、スカラｂはベクトルから求めることができる。
【００５７】
計算装置１０は、以前のマージンパラメータＣｔ−１における超平面を参考にすることにより、マージンパラメータＣｔに対する準最適な超平面を求めることができる。計算装置１０は、ソルバを用いる前にAlgorithm３から集合Ｃ、集合Ｓ、集合Ｎを計算する（１２行目）。
【００５８】
計算装置１０は、求めた超平面が最適であるという条件を満たすまで、逐次的に集合Ｃを更新しながらソルバを適用する（１３−１８行目）。計算装置１０は、Algorithm４を用いて超平面の最適性を確認する。Algorithm４は、求めた超平面が最適であればｏｐｔをｔｒｕｅに設定し、そうでなければｏｐｔをｆａｌｓｅに設定するものである。また、ここで説明する各アルゴリズムはソルバとは独立であるため、様々なソルバを用いることができる。
【００５９】
図１７に示すように、Algorithm２では、計算装置１０は、νｉを行列Ｘのｉ番目の列において最頻の要素とすると、ｉ番目の列の要素を並び替えることでνｉを求めることができ、ｉ番目の列ベクトルに対する重みωｉを、ωｉ＝μ／νｉとして計算する（２−４行目）。そして、計算装置１０は、行列Ｘにおいて値μを増やすように重みωｉを用い、その後に値μをすべての要素から引く（５−６行目）。
【００６０】
図１８に示すように、Algorithm３では、計算装置１０は、まず定義２から上限値ｚ￣（ｘｉ，α，ｂ）およびｚ＿（ｘｉ，α，ｂ）を計算する。もし、データポイントｘｉが（ｚ￣（ｘｉ，α，ｂ）−１）（ｚ＿（ｘｉ，α，ｂ）−１）＜０を満たせば、計算装置１０は、正確にパラメータｚ（ｘｉ，α，ｂ）を計算する（４−５行目）。
【００６１】
もし、データポイントｘｉが、集合Ｃの条件（定義１）を満たせば、計算装置１０は、集合Ｃにデータポイントｘｉを追加する（６−７行目）。そうでなければ、計算装置１０は、集合Ｓまたは集合Ｎにデータポイントｘｉを追加する（８−１３行目）。
【００６２】
これは、もしｙ［ｉ］ｚ（ｘｉ，α，ｂ）＜１またはｙ［ｉ］ｚ（ｘｉ，α，ｂ）＞１が成り立てば、それぞれα［ｉ］＝０およびα［ｉ］＝Ｃとなるためである。さらに、もしデータポイントｘｉが補題１または補題２の条件を満たせば、計算装置１０は、そのデータポイントを集合Ｓまたは集合Ｎに追加する（１４−１９行目）。もし、この処理においてラグランジュ乗数α［ｉ］がα［ｉ］＝Ｃまたはα［ｉ］＝０と決定されれば、計算装置１０は、高速に上限値と下限値を計算するためにスコアＦ（ｘｉ）を更新することができる（２０−２２行目）。
【００６３】
図１９に示すように、Algorithm４では、計算装置１０は、ラベルがｙ［ｉ］＝１であり、ｘｉ∈Ｓであるデータポイントに対して、もしｚ￣（ｘｉ，α，ｂ）−１≧０かつｙ［ｉ］ｚ（ｘｉ，α，ｂ）≧１であれば、ｏｐｔをｆａｌｓｅに設定し、当該データポイントを集合Ｓから集合Ｃへ式（１９）を用いて追加する（２−１０行目）。同様に、計算装置１０は、式（２０）から（２２）の条件が満たされていなければ、ｏｐｔをｆａｌｓｅに設定し、データポイントの追加を行う（１１−３５）行目）。
【００６４】
Algorithm４に見られるように、計算装置１０は、まず条件ｚ￣（ｘｉ，α，ｂ）−１＜０またはｚ＿（ｘｉ，α，ｂ）−１＞０を確認するために、上限値ｚ￣（ｘｉ，α，ｂ）および下限値ｚ＿（ｘｉ，α，ｂ）を計算する。そして、もしデータポイントが条件を満たせば、計算装置１０は、パラメータｚ（ｘｉ，α，ｂ）を計算する。
【００６５】
また、Algorithm４に見られるように、マージンパラメータＣｔに対して学習を行うとき、集合Ｃは単調増加であり、集合Ｓおよび集合Ｎは単調減少である。
【００６６】
ここで、Algorithm３は、図１３の補題７に示す性質を示す。図１３は、補題７を示す図である。補題７は、Algorithm３がすべてのデータポイントを集合Ｃ、集合Ｓ、集合Ｎのいずれかに割り当てることを示している。
【００６７】
これはもし（ｚ￣（ｘｉ，α，ｂ）−１）（ｚ＿（ｘｉ，α，ｂ）−１）≦０があるデータポイントに対して成り立てば、Algorithm３の４−１３行目から、そのデータポイントは集合Ｃ、集合Ｓ、集合Ｎのいずれかに割り当てられるからである。補題７から、図１４の定理１が成り立つ。
【００６８】
また、これまでＲＢＦカーネルを用いてマージンパラメータに対してグリッドサーチを行うことを前提にしてきたが、ここではこれらの制限を拡張する手法について述べる。カーネル関数としてはＲＢＦカーネル以外に代表的なものとして線形カーネル、多項式カーネル、シグモイドカーネルがある。ＲＢＦカーネルに対しては、スコアｄ￣とスコアｄ＿を計算して上限値および下限値を求めるが、その他のカーネルについては、図１５の補題８に示す性質を用いて上限値と下限値を計算することができる。
【００６９】
線形カーネル、多項式カーネル、シグモイドカーネルはｘｉＴｘｊを用いて計算できるため、補題８を用いることで、上限値および下限値を計算することができる。また、マージンパラメータＣの他に、サポートベクターマシンにはカーネル関数のγ、ｒ、ｐなどのパラメータが存在する。マージンパラメータＣと同様に、これらのパラメータに対してもグリッドサーチを用いて適切な値を求めることができる。
【００７０】
実施形態では、これまでマージンパラメータＣに対するグリッドサーチを前提にしてきたが、これらのカーネルのパラメータのグリッドサーチにも提案手法は有効である。具体的には、カーネルのパラメータを固定しながらマージンパラメータＣに対するグリッドサーチを実行し、その後にカーネルのパラメータの変更を行うことができる。
【００７１】
［第１の実施形態の処理の流れ］
図２０から２４は、第１の実施形態に係る計算処理の流れを示すフローチャートである。図２０に示すように、まず、計算装置１０には、行列Ｘ、ベクトルｙ、パラメータＣ１，，Ｃ２，・・・，ＣＴ、ランクｍ、値μが入力される（ステップＳ１０１）。そして、計算装置１０は、行列ＸのＳＶＤを計算する（ステップＳ１０２）。
【００７２】
そして、計算装置１０は、疎行列を計算し（ステップＳ１０３）、α［ｉ］を初期化する（ステップＳ１０４−Ｓ１１３）。また、計算装置１０は、初期集合を設定し（ステップＳ１１４）、集合Ｃに対してソルバを適用する（ステップＳ１１５）。さらに、計算装置１０は、Ｆ（ｘｉ）を更新する（ステップＳ１１６−Ｓ１１８）。
【００７３】
また、計算装置１０は、最適性の確認を行い（ステップＳ１１９）、ｏｐｔ＝ｔｒｕｅとなるまで（ステップＳ１２０、Ｎｏ）ソルバの適用を行う。そして、ｏｐｔ＝ｔｒｕｅとなった場合（ステップＳ１２０、Ｙｅｓ）、計算装置１０は、ラグランジュ乗数およびスカラを出力する（ステップＳ１２１）。
【００７４】
図２１を用いて、疎行列の計算処理の流れを説明する。図２１に示すように、疎行列の計算処理には、行列Ｘおよび値μが入力される（ステップＳ２０１）。そして、計算装置１０は、行列Ｘの各行の要素をソートしつつ、最頻値を計算する（ステップＳ２０２−Ｓ２０９）。その際、計算装置１０は、ωｉおよびμで各要素のスケーリングおよびシフトを行う（ステップＳ２０６−Ｓ２０８）。
【００７５】
図２２を用いて、初期集合の設定処理の流れを説明する。図２２に示すように、初期集合の設定処理には、パラメータＣ、ラグランジュ乗数α、スカラｂ、行列Ｘが入力される（ステップＳ３０１）。計算装置１０は、各集合を初期化し（ステップＳ３０２）、各データポイントの上限値および下限値を計算する（ステップＳ３０３、Ｓ３０４）。
【００７６】
上限値および下限値が条件を満たす場合（ステップＳ３０５、Ｙｅｓ）、計算装置１０は、パラメータｚを計算する（ステップＳ３０６）。上限値および下限値が条件を満たさない場合（ステップＳ３０５、Ｎｏ）、計算装置１０は、処理をステップＳ３１４へ進める。
【００７７】
パラメータｚが集合Ｃへ追加されるための条件を満たす場合（ステップＳ３０７、Ｙｅｓ）、計算装置１０は、集合Ｃにデータポイントを追加する（ステップＳ３０８）。
【００７８】
パラメータｚが集合Ｓへ追加されるための条件を満たす場合（ステップＳ３０９、Ｙｅｓ）、計算装置１０は、集合Ｓにデータポイントを追加し（ステップＳ３１０）、ラグランジュ乗数にＣを設定し（ステップＳ３１１）、処理をステップＳ３２０へ進める。
【００７９】
パラメータｚが集合Ｓへ追加されるための条件を満たさない場合（ステップＳ３０９、Ｎｏ）、計算装置１０は、集合Ｎにデータポイントを追加し（ステップＳ３１２）、ラグランジュ乗数に０を設定し（ステップＳ３１１）、処理をステップＳ３２０へ進める。
【００８０】
上限値および下限値が集合Ｓへ追加されるための条件を満たす場合（ステップＳ３１４、Ｙｅｓ）、計算装置１０は、集合Ｓにデータポイントを追加し（ステップＳ３１５）、ラグランジュ乗数にＣを設定し（ステップＳ３１６）、処理をステップＳ３２０へ進める。
【００８１】
上限値および下限値が集合Ｓへ追加されるための条件を満たさず（ステップＳ３０９、Ｎｏ）、集合Ｎへ追加されるための条件を満たす場合（ステップＳ３１７、Ｙｅｓ）、計算装置１０は、集合Ｎにデータポイントを追加し（ステップＳ３１８）、ラグランジュ乗数に０を設定し（ステップＳ３１９）、処理をステップＳ３２０へ進める。
【００８２】
ラグランジュ乗数が０またはＣである場合（ステップＳ３２０、Ｙｅｓ）、計算装置１０は、スコアを更新する（ステップＳ３２１−Ｓ３２４）。そして、計算装置１０は、各集合、ラグランジュ乗数およびスコアを出力する（ステップＳ３２５）。
【００８３】
図２３を用いて、最適性の確認処理の流れを説明する。図２３に示すように、最適性の確認処理には、ラグランジュ乗数α、スカラｂおよび行列Ｘが入力される（ステップＳ４０１）。
【００８４】
まず、計算装置１０は、ｏｐｔ＝ｔｒｕｅを設定する（ステップＳ４０２）。そして、計算装置１０は、集合Ｓに含まれるデータポイントについて（ステップＳ４０３）、ラベルが１である場合（ステップＳ４０４、Ｙｅｓ）、上限値を計算し（ステップＳ４０５）、さらに上限値が所定の条件を満たす場合（ステップＳ４０６、Ｙｅｓ）、パラメータｚを計算し（ステップＳ４０７）、さらにパラメータｚが所定の条件を満たす場合（ステップＳ４０８、Ｙｅｓ）、ｏｐｔ＝ｆａｌｓｅを設定し（ステップＳ４０９）、当該データポイントを集合Ｓから集合Ｃに移動させ（ステップＳ４１０）、処理をＳ４１７へ進める。また、上限値またはパラメータｚに関する条件が満たされない場合（ステップＳ４０６、ステップＳ４０８のいずれかがＮｏ）、計算装置１０は、処理をステップＳ４１７へ進める。
【００８５】
また、計算装置１０は、集合Ｓに含まれるデータポイントについて（ステップＳ４０３）、ラベルが１でない場合（ステップＳ４０４、Ｎｏ）、下限値を計算し（ステップＳ４１１）、さらに下限値が所定の条件を満たす場合（ステップＳ４１２、Ｙｅｓ）、パラメータｚを計算し（ステップＳ４１３）、さらにパラメータｚが所定の条件を満たす場合（ステップＳ４１４、Ｙｅｓ）、ｏｐｔ＝ｆａｌｓｅを設定し（ステップＳ４１５）、当該データポイントを集合Ｓから集合Ｃに移動させ（ステップＳ４１６）、処理をＳ４１７へ進める。また、下限値またはパラメータｚに関する条件が満たされない場合（ステップＳ４１２、ステップＳ４１４のいずれかがＮｏ）、計算装置１０は、処理をステップＳ４１７へ進める。
【００８６】
また、計算装置１０は、集合Ｎに含まれるデータポイントについて（ステップＳ４１８）、ラベルが１である場合（ステップＳ４１９、Ｙｅｓ）、下限値を計算し（ステップＳ４２０）、さらに下限値が所定の条件を満たす場合（ステップＳ４２１、Ｙｅｓ）、パラメータｚを計算し（ステップＳ４２２）、さらにパラメータｚが所定の条件を満たす場合（ステップＳ４２３、Ｙｅｓ）、ｏｐｔ＝ｆａｌｓｅを設定し（ステップＳ４２４）、当該データポイントを集合Ｎから集合Ｃに移動させ（ステップＳ４２５）、処理をＳ４３２へ進める。また、下限値またはパラメータｚに関する条件が満たされない場合（ステップＳ４２１、ステップＳ４２３のいずれかがＮｏ）、計算装置１０は、処理をステップＳ４３２へ進める。
【００８７】
また、計算装置１０は、集合Ｎに含まれるデータポイントについて（ステップＳ４１８）、ラベルが１でない場合（ステップＳ４１９、Ｎｏ）、上限値を計算し（ステップＳ４２６）、さらに上限値が所定の条件を満たす場合（ステップＳ４２７、Ｙｅｓ）、パラメータｚを計算し（ステップＳ４２８）、さらにパラメータｚが所定の条件を満たす場合（ステップＳ４２９、Ｙｅｓ）、ｏｐｔ＝ｆａｌｓｅを設定し（ステップＳ４３０）、当該データポイントを集合Ｎから集合Ｃに移動させ（ステップＳ４３１）、処理をＳ４３２へ進める。また、上限値またはパラメータｚに関する条件が満たされない場合（ステップＳ４２７、ステップＳ４２９のいずれかがＮｏ）、計算装置１０は、処理をステップＳ４３２へ進める。
【００８８】
そして、計算装置１０は、各集合および最適化否かを示すｏｐｔの値を出力する（ステップＳ４３３）。
【００８９】
［第１の実施形態の効果］
パラメータ計算部１３は、行列に含まれるデータポイントごとに、サポートベクターマシンで用いられるマージンパラメータに基づく所定のパラメータについて、該パラメータの上限値および下限値を計算する。集合設定部１４は、データポイントのうち、所定のパラメータが、上限値以下かつ下限値以上であるデータポイントの集合を設定する。超平面計算部１５は、集合に含まれるデータポイントおよびマージンパラメータを基に、サポートベクターマシンの超平面を計算する。このように、本実施形態の計算装置１０は、超平面を計算する前にデータポイントの枝狩りを行うため、サポートベクターマシンの計算コストを低減させることができる。
【００９０】
集合設定部１４は、データポイントのうち、下限値および上限値が第１の条件を満たすデータポイントを、集合に含める。このように、計算装置１０は、パラメータｚを計算することなく、パラメータｚの上限値および下限値から枝狩りをするか否かを判断できるため、さらに計算コストを低減させることができる。
【００９１】
確認部１７は、行列に含まれるデータポイントであって、集合に含まれないデータポイントが、超平面計算部１５によって計算された超平面を基に設定された第２の条件を満たすか否かを確認する。集合設定部１４は、確認部１７によって第２の条件を満たすことが確認されたデータポイントを集合に追加する。これにより、枝狩りを行った後の集合を使って計算した超平面の最適性が保証されるため、本実施形態によれば、計算コストの低減とＳＶＭの分類精度とを両立させることができる。
【００９２】
疎行列計算部１２は、行列の要素の値のスケーリングおよびシフトを行うことによって、疎行列を計算する。パラメータ計算部１３は、疎行列のデータポイントごとに上限値および下限値を計算する。集合設定部１４は、疎行列のデータポイントを基に集合を設定する。このように、計算装置１０は、行列をあらかじめ疎行列化しておくことで、さらに計算コストを低減させることができる。
【００９３】
疎行列計算部１２は、行列の最頻値に基づく重みを計算し、行列の要素のうち値が最頻値と等しい要素の値が０になるように、行列の要素の値を重みでスケーリングし、所定の定数でシフトする。これにより、出現頻度が高い要素の値を零にすることができる。
【００９４】
［システム構成等］
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況等に応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行われる各処理機能は、その全部または任意の一部が、ＣＰＵ（Central  Processing  Unit）および当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【００９５】
また、本実施形態において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００９６】
［プログラム］
一実施形態として、計算装置１０は、パッケージソフトウェアやオンラインソフトウェアとして上記の計算を実行する計算プログラムを所望のコンピュータにインストールさせることによって実装できる。例えば、上記の計算プログラムを情報処理装置に実行させることにより、情報処理装置を計算装置１０として機能させることができる。ここで言う情報処理装置には、デスクトップ型またはノート型のパーソナルコンピュータが含まれる。また、その他にも、情報処理装置にはスマートフォン、携帯電話機やＰＨＳ（Personal  Handyphone  System）等の移動体通信端末、さらには、ＰＤＡ（Personal  Digital  Assistant）等のスレート端末等がその範疇に含まれる。
【００９７】
また、計算装置１０は、ユーザが使用する端末装置をクライアントとし、当該クライアントに上記の計算に関するサービスを提供する計算サーバ装置として実装することもできる。例えば、計算サーバ装置は、多次元行列を入力とし、次元削減した行列を出力とする計算サービスを提供するサーバ装置として実装される。この場合、計算サーバ装置は、Ｗｅｂサーバとして実装することとしてもよいし、アウトソーシングによって上記の計算に関するサービスを提供するクラウドとして実装することとしてもかまわない。
【００９８】
図２４は、計算プログラムを実行するコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらの各部は、バス１０８０によって接続される。
【００９９】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ（Random  Access  Memory）１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１１００に挿入される。シリアルポートインタフェース１０５０は、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、例えばディスプレイ１１３０に接続される。
【０１００】
ハードディスクドライブ１０９０は、例えば、ＯＳ（Operating  System）１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、計算装置１０の各処理を規定するプログラムは、コンピュータにより実行可能なコードが記述されたプログラムモジュール１０９３として実装される。プログラムモジュール１０９３は、例えばハードディスクドライブ１０９０に記憶される。例えば、計算装置１０における機能構成と同様の処理を実行するためのプログラムモジュール１０９３が、ハードディスクドライブ１０９０に記憶される。なお、ハードディスクドライブ１０９０は、ＳＳＤにより代替されてもよい。
【０１０１】
また、上述した実施形態の処理で用いられる設定データは、プログラムデータ１０９４として、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して実行する。
【０１０２】
なお、プログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限らず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、プログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶されてもよい。そして、プログラムモジュール１０９３およびプログラムデータ１０９４は、他のコンピュータから、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【０１０３】
１０  計算装置
１１  ＳＶＤ計算部
１２  疎行列計算部
１３  パラメータ計算部
１４  集合設定部
１５  超平面計算部
１６  スコア更新部
１７  確認部
【図１】
2019185198.tif 000012
【図２】
2019185198.tif 000013
【図３】
2019185198.tif 000014
【図４】
2019185198.tif 000015
【図５】
2019185198.tif 000016
【図６】
2019185198.tif 000017
【図７】
2019185198.tif 000018
【図８】
2019185198.tif 000019
【図９】
2019185198.tif 000020
【図１０】
2019185198.tif 000021
【図１１】
2019185198.tif 000022
【図１２】
2019185198.tif 000023
【図１３】
2019185198.tif 000024
【図１４】
2019185198.tif 000025
【図１５】
2019185198.tif 000026
【図１６】
2019185198.tif 000027
【図１７】
2019185198.tif 000028
【図１８】
2019185198.tif 000029
【図１９】
2019185198.tif 000030
【図２０】
2019185198.tif 000031
【図２１】
2019185198.tif 000032
【図２２】
2019185198.tif 000033
【図２３】
2019185198.tif 000034
【図２４】
2019185198.tif 000035