(57)【特許請求の範囲】
【請求項１】
訓練データのセンシング行列に基づき未知データをスパース表現クラス分類するクラス分類装置であって、
前記クラス分類の訓練データから分割されたセンシング行列候補データに含まれる各候補アイテムの正解分類への寄与率を算出する寄与率計算手段と、
前記候補アイテムの寄与率の値に基づき選択された候補アイテムを成分とするセンシング行列を作成するセンシング行列作成手段と
を備えたこと
を特徴とするクラス分類装置。
【請求項２】
前記寄与率計算手段は、前記センシング行列候補データと前記訓練データ由来の検証データとの線形的な制約を満たす解の係数を正規化することにより前記各候補アイテムの寄与率を算出すること
を特徴とする請求項１に記載のクラス分類装置。
【請求項３】
最新の訓練データのセンシング行列候補データと当該訓練データ由来の検証データとの線形的な制約を満たす解の係数に基づき従前のセンシング行列に含まれる各候補アイテムの寄与率を更新しこの更新した寄与率の値に基づき当該センシング行列を更新するセンシング行列更新手段を
さらに備えたこと
を特徴とする請求項１に記載のクラス分類装置。
【請求項４】
訓練データのセンシング行列に基づき未知データをスパース表現クラス分類するクラス分類装置が実行するクラス分類方法であって、
前記クラス分類装置の寄与率計算手段が前記クラス分類の訓練データから分割されたセンシング行列候補データに含まれる各候補アイテムの正解分類への寄与率を算出するステップと、
前記クラス分類装置のセンシング行列作成手段が前記候補アイテムの寄与率の値に基づき選択された候補アイテムを成分とするセンシング行列を作成するステップと
を有すること
を特徴とするクラス分類方法。
【請求項５】
前記寄与率を算出するステップでは、前記センシング行列候補データと前記訓練データ由来の検証データとの線形的な制約を満たす解の係数を正規化することにより前記各候補アイテムの寄与率を算出すること
を特徴とする請求項４に記載のクラス分類方法。
【請求項６】
前記クラス分類装置のセンシング行列更新手段が最新の訓練データのセンシング行列候補データと当該訓練データ由来の検証データとの線形的な制約を満たす解の係数に基づき従前のセンシング行列に含まれる各候補アイテムの寄与率を更新しこの更新した寄与率の値に基づき当該センシング行列を更新するステップ
をさらに有すること
を特徴とする請求項４に記載のクラス分類方法。
【請求項７】
請求項１から３のいずれか１項に記載のクラス分類装置を構成する各手段としてコンピュータを機能させることを特徴とするクラス分類プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は入力されたベクトルが所属するクラスラベルを予測する技術に関する。特に、スパース表現されたベクトルのクラス分類を行う際に有効であるとされるスパース表現分類法（Sparse Representation-based Classification  以下、ＳＲＣ法と称する）を最適化させる技術に関する。
【背景技術】
【０００２】
近年、写真中の人認識やテキスト分類、音声認識といった応用のために、クラス分類技術が注目されている。クラス分類は入力されるベクトルに対して予め決められた有限個のクラスラベルを割り当てる分類手法である。分類手法には線形識別モデルやロジスティック回帰モデル、ＳＶＭ（Support Vector machine）等の手法がよく適用されている。
【０００３】
上記の様々なクラス分類技術の中で圧縮センシング理論に基づいたＳＲＣ法が近年注目を浴びている（非特許文献１）。
【０００４】
ＳＲＣ法では図１１に示したように未知データは訓練データ中の全てのアイテムの線形結合で表現されると考える。その表現がスパース性を満たすという仮定のもと、圧縮センシング理論に基づき未知データのスパース信号を効率的に復元し、復元信号が所属するクラスを求めることによって、クラス分類を行う。
【０００５】
すなわち、分類画像は訓練データの線形結合で表され、所属クラスの訓練データの係数以外はほとんどゼロであるという仮説のもとに、L１最適化にてテストデータを表現するスパース信号すなわち基底の係数を算出する。その後、スパース信号の係数を各クラスに射影したベクトルをもう一度センシング行列で写像し、テストデータとのL2距離が最も小さくなるクラスを予測クラスラベルとする。ＳＲＣ法の分類アルゴリズムを以下に示す。
【０００６】
【表１】
0005491430.tif 000002
【０００７】
ダウンサンプリングした画像に適用したＳＲＣ法は、固有顔（Eigenfaces）、FisherfacesやLaplacianfacesといった、顔に特化した特徴量と高度な学習を行う分類器であるＳＶＭと組み合わせた場合と同程度の精度を達成することが確認されている（非特許文献１）。また、オクルージョンや表情などにもロバストに人を検出出来ることが確認されており、現在有望視されているクラス分類技術の一つである言える。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】J.Wright,A.Y.Yang,A.Ganesh,S.S.Sastry,and Yi Ma,"Robust Face Recognitionvia Sparse Representation.",In PAMI 2009,VOL.31,No.2,FEBRUARY 2009, pp. 210-227.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ＳＲＣ法ではクラス分類する際に毎回L1最適化を解く必要があるため、センシング行列の列数に比例した計算量を要することになる。センシング行列の列数が多ければ多いほど精度高くクラス分類できるので、クラス分類時間と精度の間にはトレードオフの関係がある。
【００１０】
本発明は以上の事情に鑑みなされたものでスパース表現クラス分類に要する計算量を削減できる共に分類精度を低下させずに高速にクラス分類を行えるクラス分類技術の提供を目的とする。
【課題を解決するための手段】
【００１１】
そこで、本発明はスパース表現クラス分類に供される訓練データ由来のセンシング行列に含まれるベクトル（候補アイテム）のうちで正解分類への寄与率の高いものだけを抽出して当該センシング行列を縮小する。これにより、スパース表現クラス分類の精度を低減させることなくクラス分類に要する計算量を削減させることができる。
【００１２】
本発明のクラス分類装置の態様としては、訓練データのセンシング行列に基づき未知データをスパース表現クラス分類するクラス分類装置であって、前記クラス分類の訓練データから分割されたセンシング行列候補データに含まれる各候補アイテムの正解分類への寄与率を算出する寄与率計算手段と、前記候補アイテムの寄与率の値に基づき選択された候補アイテムを成分とするセンシング行列を作成するセンシング行列作成手段とを備える。
【００１３】
本発明のクラス分類方法の態様としては、訓練データのセンシング行列に基づき未知データをスパース表現クラス分類するクラス分類装置が実行するクラス分類方法であって、前記クラス分類装置の寄与率計算手段が前記クラス分類の訓練データから分割されたセンシング行列候補データに含まれる各候補アイテムの正解分類への寄与率を算出するステップと、前記クラス分類装置のセンシング行列作成手段が前記候補アイテムの寄与率の値に基づき選択された候補アイテムを成分とするセンシング行列を作成するステップとを有する。
【００１４】
前記クラス分類装置及びクラス分類方法において、前記寄与率計算手段の具体的な態様としては、例えば、前記センシング行列候補データと前記訓練データ由来の検証データとの線形的な制約を満たす解の係数を正規化することにより前記各候補アイテムの寄与率を算出する。
【００１５】
また、前記クラス分類装置及びクラス分類方法においては、新しい分類を行う毎に、寄与率とセンシング行列をオンラインで更新することで、最新の分類結果の傾向を反映したセンシング行列による分類を行える。
【００１６】
すなわち、前記クラス分類装置及びクラス分類方法において、当該クラス分類装置のセンシング行列更新手段は最新の訓練データのセンシング行列候補データと当該訓練データ由来の検証データとの線形的な制約を満たす解の係数に基づき従前のセンシング行列に含まれる各候補アイテムの寄与率を更新しこの更新した寄与率の値に基づき当該センシング行列を更新する。
【００１７】
尚、本発明は上記のクラス分類装置を構成する各手段としてコンピュータを機能させるクラス分類プログラムの態様とすることもできる。
【発明の効果】
【００１８】
以上の発明によればスパース表現クラス分類に要する計算量を削減すると共に分類精度を低下させずに高速にクラス分類を行える。
【図面の簡単な説明】
【００１９】
【図１】発明の実施形態に係るクラス分類装置のブロック構成図。
【図２】クラス分類の処理手順を説明したフロー図。
【図３】寄与率の算出手順を説明したフロー図。
【図４】センシング行列の作成手順を説明したフロー図。
【図５】センシング行列の更新手順を説明したフロー図。
【図６】候補アイテムの寄与率の説明図。
【図７】発明によるセンシング行列の縮小の説明図。
【図８】（ａ）等分割法によって得られたデータ構造を示した図，（ｂ）1Held-out法によって得られたデータ構造を示した図。
【図９】ＳＲＣ法におけるセンシング行列の構成例を示した図。
【図１０】センシング行列の更新処理の説明図。
【図１１】ＳＲＣ法におけるスパース性の説明図。
【発明を実施するための形態】
【００２０】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態に限定されるものではない。
【００２１】
図１に示されクラス分類装置１は図６に示したようにＳＲＣ法の訓練データに由来するセンシング行列に含まれるアイテムの正解分類への寄与率を予め蓄積する。そして、図７に示したセンシング行列ＣＡに含まれるアイテム集合から正解分類に対して寄与率の高いアイテム集合を選択することでセンシング行列ＣＡをセンシング行列ＣＢに縮小させる。これにより、クラス寄与率の高い少数の訓練データで精度低下を少なくさせながらＳＲＣ法によるクラス分類を高速に行える。また、図１０に示したように新しいクラス分類を行う毎に寄与率とセンシング行列をオンラインで更新することにより最新の分類結果の傾向を反映したセンシング行列によるクラス分類が行える。
【００２２】
本実施形態の説明で用いられる技術用語について説明する。
【００２３】
スパースベクトル：空間を張る基底の線形結合でベクトルを表現したときに、ベクトル成分の係数の多くが０となるようなベクトルを意味する。
【００２４】
ｋ-スパースネス：あるデータセットを表現した際の上記係数のうち、０でない係数の個数の最大値を意味する。計算量や圧縮センシングにおけるL1最適化問題とL0最適化問題の解が一致することを理論上証明するために必要な概念。
【００２５】
圧縮センシング(Compressed Sensing)：スパース信号の再現理論である。センシング行列がある条件（線形的な制約）を満たすならば、L1最適化により高い確率でスパース信号が復元できる再現理論である（非特許文献１）。センシング行列をＡ、スパースベクトル(信号)をｘ、圧縮ベクトルをｙで示すと、スパース信号を復元するためのL1最適化の線形的な制約は以下の式で表現できる。映像配信サービス等では、センシング行列Ａを受信側で保持することにより、圧縮ベクトルｙを配信するだけで、元々のベクトルｘを復元できるため、データ転送量を削減することができる。
【００２６】
【数１】
0005491430.tif 000003
【００２７】
線形計画問題(Linear Programming Problem)：最適化問題において、目的関数が線型関数で、かつ線型関数の等式と不等式で制約条件が記述できる問題を意味する。この問題を解く手法を線形計画法と言う。一般に以下の形で記述できる。すなわち、圧縮センシングにおけるL1最適化は線形計画問題の１つと考えることができる。下記の式においてＡは観測行列（センシング行列）、ｂは観測結果（検証データ）、ｘは未知ベクトル（スパースベクトル）を示す。
【００２８】
【数２】
0005491430.tif 000004
【００２９】
［クラス分類装置１の構成］
クラス分類装置１は図１に示されたようにクラス分類手段１０、訓練データ分割手段１１、L1最適化手段１２、寄与率計算手段１３、センシング行列作成手段１４、センシング行列更新手段１５を備える。
【００３０】
クラス分類装置１の上記各機能手段はサーバ（コンピュータ）のハードウェアリソースによって実現される。すなわち、情報検索装置１は制御手段（ＣＰＵ）１００、記憶手段（ハードディスク装置等）１０１、通信インタフェース１０２、入力装置（キーボード、ポインティングデバイス等）１０３、出力装置（モニタ）１０４等のコンピュータに係るハードウェアリソースを備える。そして、これらのハードウェアリソースがソフトウェアリソース（ＯＳ、アプリケーション等）と協働することにより上記各機能手段が実装される。
【００３１】
クラス分類装置１にはユーザ端末２からネットワーク３を介して検証データが供されるようになっている。検証データはクラス分類に供されるデータであり、例えばユーザ端末２のデータ処理手段２０によって作成、編集された複数の画像からなる。データ処理手段２０はユーザ端末２のハードウェアリソース（ＣＰＵ、記憶手段２１、通信手段２２、ユーザインタフェース２３等）とソフトウェアリソースとの協働により実装される。
【００３２】
クラス分類手段１０はユーザ端末２から供された検証データをＳＲＣ法によってクラス分類する多クラス分類器である。検証データの分類結果は訓練データとして保持される。
【００３３】
訓練データ分割手段１１はクラス分類手段１０で得られた訓練データを図８に示したようにセンシング行列候補データと検証データとに分割する。
【００３４】
L1最適化手段１２は前記センシング行列候補データと前記検証データとの線形的な制約を満たす解を算出する。当該線形的な制約には線形計画問題として後述の式（０）で示したL1最適化問題が適用される。
【００３５】
寄与率計算手段１３は前記センシング行列候補データに含まれる各候補アイテムの正解分類への寄与率を算出する。寄与率計算手段１３は具体的にはL1最適化手段１２によって算出された解の係数を正規化することにより前記各候補アイテムの寄与率を算出する。
【００３６】
センシング行列作成手段１４は前記候補アイテムの寄与率の値に基づき選択された候補アイテムを成分とするセンシング行列を作成する。
【００３７】
センシング行列更新手段１５は最新の訓練データのセンシング行列候補データと当該訓練データ由来の検証データとの線形的な制約を満たす解の係数に基づき従前のセンシング行列に含まれる各候補アイテムの寄与率を更新する。そして、この更新した寄与率の値に基づき当該センシング行列を更新する。尚、本手段１５による線形的な制約を満たす解の算出においても後述の式（０）で示したL1最適化問題の解法が適用される。
【００３８】
［処理手順の説明］
本実施形態の処理手順は図２に示すように訓練データの縮小されたセンシング行列を作成するオフライン処理（Ｓ１〜Ｓ５）と最新の訓練データを得る毎に必要に応じて従前のセンシング行列を更新するオンライン処理（Ｓ６）とからなる。
【００３９】
（オフライン処理）
Ｓ１：クラス分類手段１０はユーザ端末２から供された検証データをＳＲＣ法によってクラス分類する。検証データの分類結果は訓練データとして保持される。
【００４０】
Ｓ２：訓練データ分割手段１１はＳ１にて得られた訓練データを図８に例示されたようにセンシング行列候補データと検証データとに分割する。
【００４１】
訓練データのアイテムには、それぞれクラスラベルが付与されている。それぞれのクラスに十分な数のアイテムがあり、図８に示したようにそれぞれのクラス内のアイテム集合はセンシング行列候補データと検証データに分割される。
【００４２】
センシング行列候補データは、ＳＲＣ法において検証データをスパース表現する際の基底ベクトルの候補集合となっており、候補アイテムをａi（１≦ｉ≦ｎ）とした場合、センシング行列はＡ＝［ａ1，ａ2，…，ａn］と表現される。但し、図９に示したように、先頭から順番にクラスＣ1，…，Ｃkの順で各クラスに属するアイテムａ1〜ａnが並ぶように配置される。
【００４３】
訓練データの分割法には図８（ａ）に例示した等分割法や図８（ｂ）に例示した1held-out法が適用される。最も単純な分割方法は等分割法でありクラス内のアイテム集合を等分割する。訓練データが十分にない場合は、1held-out法により、１つのアイテムを除いてそれ以外をセンシング行列データとする。
【００４４】
Ｓ３：L1最適化手段１２はＳ２にて分割されたセンシング行列候補データと検証データとの線形的な制約を満たす解を算出する。具体的には図３に示した手順Ｓ１０１〜Ｓ１０３を実行する。
【００４５】
（Ｓ１０１）Ｓ２で得られたセンシング行列候補データから成る行列Ａ’と検証データを格納した集合Ａ”の入力を受ける。
【００４６】
（Ｓ１０２）検証データ中のアイテムｙが集合Ａ”に含まれていること（ｙ∈Ａ”）を確認する。
【００４７】
（Ｓ１０３）行列Ａ’とアイテムｙとの線形制約（ｙ＝Ａ’ｘ）を条件とするＬ１最適化問題を解き、その解をｘ＾とする。
【００４８】
すなわち、行列Ａ’が行列Ａ＝［ａ1，ａ2，…，ａn］で示される場合、ＳＲＣ法では下記の線形制約で示されるL1最適化問題を解くことになる。
【００４９】
【数１】
0005491430.tif 000005
【００５０】
但し、現実的にはノイズが含まれていることも多く上記の問題を厳密に解くことは困難なため、実質的には誤差を許容した以下の式（０）で示される最適化問題を解く。
【００５１】
【数３】
0005491430.tif 000006
【００５２】
L1最適化問題の一般的な計算量は少なくともO(|n3|)要するが（ｎはアイテム数）、スパースベクトルの解ｘの算出にはほぼ線形で解けるアルゴリズムが提案されている。このアルゴリズムは前記の一般的な計算量よりも少ないのが特徴であり、その計算量はＯ(|n+k3|)だけで済む（但し、ｋはｋ‐スパースネスの値、すなわち空間のスパース性を示す尺度であり、係数がゼロとならない最大値）。
【００５３】
以上の手順Ｓ１０２，Ｓ１０３はアイテムｙの数だけ繰り返し実行される。
【００５４】
Ｓ４：寄与率計算手段１３はＳ３（Ｓ１０１〜Ｓ１０３）にて算出された解ｘ＾に基づき前記センシング行列に含まれる各候補アイテムの正解分類への寄与率を算出する。具体的には図３に示した手順Ｓ１０４〜Ｓ１０６を実行する。
【００５５】
（Ｓ１０４）検証データ中のアイテムｙの所属クラスと同じクラスに属するベクトル内の係数で解ｘ＾を正規化した値ｓを保存する。
【００５６】
（Ｓ１０５）アイテムｙの数だけＳ１０４の手順を繰返し実行する。
【００５７】
（Ｓ１０６）行列Ａ’に含まれる全ての候補アイテムａijに対して、以下の式による演算によってＳＣＯＲＥ（ａij）（以下、スコアＳ（ａij）と称する）を計算し、出力する。
【００５８】
【数４】
0005491430.tif 000007
【００５９】
上記の式において、ｓljはｌ番目の候補アイテムをｙとして式（０）のL1最適化問題を解いた解ｘ＾のｊ番目の係数を正規化した値である。Ｓ（ａij）のとり得る値の範囲は０以上１以下となり、候補アイテムａijの正解分類への寄与率の平均値を示している。
【００６０】
Ｓ５：センシング行列作成手段１４はＳ４（Ｓ１０４〜Ｓ１０６）にて算出された候補アイテムａijの寄与率のスコアＳ（ａij）に基づき選択された候補アイテムを成分とするセンシング行列を作成する。具体的には図４に示した手順Ｓ２０１〜Ｓ２０５を実行する。
【００６１】
（Ｓ２０１）センシング行列候補アイテム集合Ａ’、Ｓ４にて算出された集合Ａ’の全ての候補アイテムａijの寄与率のスコアＳ（ａij）、クラス集合ＣＳ（Ｃ1，…，Ｃk）の入力を受ける。また、クラス毎のセンシング行列候補アイテムの所望選択数ｋが設定される。
【００６２】
（Ｓ２０２）クラスＣがクラス集合ＣＳに含まれていること（Ｃ∈ＣＳ）を確認する。
【００６３】
（Ｓ２０３）ａ∈Ｃかつａ∈Ａ’となるセンシング行列候補アイテムａの集合からスコアＳ（ａ）の値が上位ｋ個の候補アイテムａをセンシング行列の成分として選択する。
【００６４】
（Ｓ２０４）クラス集合ＣＳの全てのクラスＣ1〜kについてＳ２０３を実行する。
【００６５】
（Ｓ２０５）クラス集合ＣＳ中の全てのクラスＣ1〜kにおいて、Ｓ２０３で選択されたｋ個の候補アイテムａを成分とするセンシング行列を作成し、出力する。
【００６６】
以上の手順Ｓ１〜Ｓ５によって図７に例示された通常のセンシング行列ＣＡよりも情報量が縮小され且つ訓練データに対して寄与率の高いアイテムを含んだセンシング行列ＣＢが作成される。図７に示された行列ＣＢは、クラスＣ1ではアイテムａ12，ａ15が選択され、クラスＣ2ではアイテムａ25，ａ27が選択され、クラスＣ3ではアイテムａ34，ａ38が選択され、クラスＣ4ではアイテムａ43，ａ49が選択されて情報量が縮小されている。尚、縮小されたセンシング行列ＣＢはクラス分類装置１の記憶手段１０１に保存される。
【００６７】
（オンライン処理）
Ｓ６：新たな検証データがクラス分類手段１０によってクラス分類されて最新の訓練データが取得されると、センシング行列更新手段１５は必要に応じて従前のセンシング行列を更新する。
【００６８】
すなわち、図１０に示されたように、新たな訓練データ（新たな検証データｙのクラス分類によって得られたクラスＣiに含まれるアイテム）が取得される毎に、当該訓練データに基づき従前のセンシング行列Ａに含まれるアイテムの寄与率のスコアＳnを逐次的に更新する。
【００６９】
次いで、この更新した寄与率のスコアＳn+1に基づきセンシング行列Ａを更新すべきか判定する。すなわち、センシング行列Ａ内のクラスＣiにおいて更新された寄与率のスコアＳn+1が最小であり且つ閾値ｔよりも低いアイテムが含まれているか否かを判断する。この寄与率の低いアイテムが含まれていると判断された場合、当該アイテムを他の所望のアイテムに差し替える。このようにしてセンシング行列Ａが更新される。
【００７０】
図５を参照しながらセンシング行列更新手段１５によって実行されるセンシング行列更新Ｓ６の具体的な手順Ｓ３０１〜Ｓ３０５について説明する。
【００７１】
Ｓ３０１：最新の訓練データの情報（新たな検証データｙが属するクラスラベルＣ）、従前のセンシング行列Ａ、センシング行列Ａ中のアイテムａの寄与率のスコアＳ（ａ）、の入力を受ける。また、忘却係数ｆ、最小寄与率の閾値ｔ（０＜ｔ＜１）が設定される。
【００７２】
Ｓ３０２：アイテムａがセンシング行列Ａ中のクラスＣに含まれているか（ａ∈Ａかつａ∈Ｃ）を確認する。
【００７３】
Ｓ３０３：アイテムａと検証データｙとの線形的な制約（式（０））を満たす解の係数を正規化した値（正規化スコア）に基づきセンシング行列Ａに含まれるアイテムａの寄与率のスコアＳを更新する。
【００７４】
具体的には式（１）を用いて０以上１以下の範囲に確率として正規化したスコアＳを利用する。オンライン処理の開始前に訓練データを利用できるのであれば、オフライン処理によるスコアを求め、これを初期スコアＳ0とする。
【００７５】
ｎ回目のクラス分類結果の線形的制約（式（０））を満たす解の係数を正規化した正規化スコアをＣn、寄与率のスコアをＳnとすると、下記の式（３）で示される漸化式によってＳnを算出できる。
【００７６】
【数５】
0005491430.tif 000008
【００７７】
但し、ｆは一種の忘却係数とも呼べる０＜ｆ＜１の定数である。この式は直前のクラス分類時に得られた正規化スコアＣnを１−ｆの重みで採用し、それ以前のスコアＳn-1をｆの重みで採用するということであり、０≦Ｓn≦１が成り立つ。
【００７８】
この式の意味するところは、再帰的にＳnを展開すると理解できる。上記式を再帰的に展開すると下記の式になることが数学的帰納法にて証明できる。
【００７９】
【数６】
0005491430.tif 000009
【００８０】
この式にて、Ｃn，Ｃn-1，…，Ｃ1，Ｓ0のそれぞれのスコアの係数の総和をとると、下記の表に示したように、１になることが確認できる。
【００８１】
【表２】
0005491430.tif 000010
【００８２】
漸化式（３）で示される寄与率のスコアＳnは直前の分類結果の正規化スコアＣnを（１−ｆ）で重み付けし、さらにその以前のスコアＳn-1が古くなるほど係数ｆを乗じて指数的に小さくした重みで重み付けした混合スコアとなる。実際には、以前の全てのスコアを保持し続けるのは効率的では無いため、直前の寄与率のスコアＳのみと混合すれば良い漸化式（３）を利用して寄与率のスコアＳを更新する。
【００８３】
Ｓ３０４：センシング行列ＡにおけるクラスＣに含まれる全てのアイテムａの寄与率のスコアＳ（ａ）をＳ３０３によって更新する。
【００８４】
Ｓ３０５：アイテムａ∈センシング行列Ａかつアイテムａ∈クラスＣとなるアイテムａのうち、Ｓ３０４で算出した寄与率のスコアＳ（ａ）が最小となるアイテムａで、Ｓ（ａ）＜閾値ｔとなる場合に、当該アイテムａを行列Ａから除去する。そして、検証データｙの所望のアイテムを挿入することで更新したセンシング行列Ａを出力する。
【００８５】
Ｓ３０５において前記所望のアイテムは例えば最新または過去の訓練データのセンシング行列に含まれるクラスＣiに含まるアイテムの集合から適当に選ばれたものが挙げられる。例えば寄与率のスコアが最も高いものが選択される。
【００８６】
以上の手順Ｓ３０１〜Ｓ３０５により常に最新の情報を反映させたクラス分類を継続して行うことができる。
【００８７】
［本実施形態の効果］
以上のようにクラス分類装置１による圧縮センシングによればスパース表現されたベクトルのクラス分類サービスを提供する際に分類精度の低下を最小限に抑えながらセンシング行列の縮小が行える。これにより、センシング行列の膨大化による分類時間の遅延を回避でき、ＳＲＣ法によるクラス分類を高速に行える。
【００８８】
特に、オフライン処理においては、訓練データのセンシング行列Ａに含まれるクラスＣj毎に候補セットの中から、寄与率のスコアＳ（ａij）の高いアイテムが選択される。これにより、候補セットの中から検証セットの分類に貢献した順に訓練データが選ばれることになり、図７に示されたように候補セット全てを利用した場合よりも小さいセンシング行列を作ることができる。
【００８９】
また、オンライン処理では寄与率が必要に応じて逐次更新されるので、より最新の分類結果の傾向を反映したセンシング行列を構築し分類を行うことができる。
【００９０】
さらに、センシング行列の候補アイテムはその寄与度の閾値に基づき選択されるので所望のセンシング行列を作成できる。例えば、ＣＰＵやメモリ性能と「１秒以内で新規データにラベルを付与したい」といったサービス上の要求の両方に応じて、選択する候補アイテムの個数が適宜選択され、任意に縮小されたセンシング行列を得ることができる。
【００９１】
本実施形態のクラス分類装置１は例えば検索対象の画像データを一元的に管理する画像管理システムにおいて適用されると当該システムの画像管理機能をより一層最適化させることができる。
【００９２】
［本発明のプログラムとしての態様］
本発明は上記のクラス分類装置１の各機能手段の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータによって実行して本発明を実現することができる。また、コンピュータで前記機能手段を実現するためのプログラムをそのコンピュータが読み取り可能な記録媒体、例えば、ＦＤ（Ｆｌｏｐｐｙ（登録商標） Ｄｉｓｋ）や、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ ｄｉｓｋ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、メモリカード、ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｋ）−ＲＯＭ、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＨＤＤ、ＳＳＤ、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【符号の説明】
【００９３】
１…クラス分類装置
１０…クラス分類手段
１１…訓練データ分割手段
１２…L1最適化手段
１３…寄与率計算手段
１４…センシング行列作成手段
１５…センシング行列更新手段
【図１】
0005491430.tif 000011
【図２】
0005491430.tif 000012
【図３】
0005491430.tif 000013
【図４】
0005491430.tif 000014
【図５】
0005491430.tif 000015
【図６】
0005491430.tif 000016
【図７】
0005491430.tif 000017
【図８】
0005491430.tif 000018
【図９】
0005491430.tif 000019
【図１０】
0005491430.tif 000020
【図１１】
0005491430.tif 000021