"訓練データのセンシング行列に基づき未知データをスパース表現クラス分類するクラス分類装置であって、前記クラス分類の訓練データから分割されたセンシング行列候補データに含まれる各候補アイテムの正解分類への寄与率を算出する寄与率計算手段と、前記候補アイテムの寄与率の値に基づき選択された候補アイテムを成分とするセンシング行列を作成するセンシング行列作成手段とを備えたことを特徴とするクラス分類装置。前記寄与率計算手段は、前記センシング行列候補データと前記訓練データ由来の検証データとの線形的な制約を満たす解の係数を正規化することにより前記各候補アイテムの寄与率を算出することを特徴とする請求項1に記載のクラス分類装置。最新の訓練データのセンシング行列候補データと当該訓練データ由来の検証データとの線形的な制約を満たす解の係数に基づき従前のセンシング行列に含まれる各候補アイテムの寄与率を更新しこの更新した寄与率の値に基づき当該センシング行列を更新するセンシング行列更新手段をさらに備えたことを特徴とする請求項1に記載のクラス分類装置。訓練データのセンシング行列に基づき未知データをスパース表現クラス分類するクラス分類方法であって、寄与率計算手段が前記クラス分類の訓練データから分割されたセンシング行列候補データに含まれる各候補アイテムの正解分類への寄与率を算出するステップと、センシング行列作成手段が前記候補アイテムの寄与率の値に基づき選択された候補アイテムを成分とするセンシング行列を作成するステップとを有することを特徴とするクラス分類方法。前記寄与率を算出するステップでは、前記センシング行列候補データと前記訓練データ由来の検証データとの線形的な制約を満たす解の係数を正規化することにより前記各候補アイテムの寄与率を算出することを特徴とする請求項4に記載のクラス分類方法。センシング行列更新手段が最新の訓練データのセンシング行列候補データと当該訓練データ由来の検証データとの線形的な制約を満たす解の係数に基づき従前のセンシング行列に含まれる各候補アイテムの寄与率を更新しこの更新した寄与率の値に基づき当該センシング行列を更新するステップをさらに有することを特徴とする請求項4に記載のクラス分類方法。請求項1から3のいずれか1項に記載のクラス分類装置を構成する各手段としてコンピュータを機能させることを特徴とするクラス分類プログラム。SRC法ではクラス分類する際に毎回L1最適化を解く必要があるため、センシング行列の列数に比例した計算量を要することになる。センシング行列の列数が多ければ多いほど精度高くクラス分類できるので、クラス分類時間と精度の間にはトレードオフの関係がある。本発明は以上の事情に鑑みなされたものでスパース表現クラス分類に要する計算量を削減できる共に分類精度を低下させずに高速にクラス分類を行えるクラス分類技術の提供を目的とする。そこで、本発明はスパース表現クラス分類に供される訓練データ由来のセンシング行列に含まれるベクトル候補アイテムのうちで正解分類への寄与率の高いものだけを抽出して当該センシング行列を縮小する。これにより、スパース表現クラス分類の精度を低減させることなくクラス分類に要する計算量を削減させることができる。本発明のクラス分類装置の態様としては、訓練データのセンシング行列に基づき未知データをスパース表現クラス分類するクラス分類装置であって、前記クラス分類の訓練データから分割されたセンシング行列候補データに含まれる各候補アイテムの正解分類への寄与率を算出する寄与率計算手段と、前記候補アイテムの寄与率の値に基づき選択された候補アイテムを成分とするセンシング行列を作成するセンシング行列作成手段とを備える。本発明のクラス分類方法の態様としては、訓練データのセンシング行列に基づき未知データをスパース表現クラス分類するクラス分類方法であって、寄与率計算手段が前記訓練データから分割されたセンシング行列候補データに含まれる各候補アイテムの正解分類への寄与率を算出するステップと、センシング行列作成手段が前記候補アイテムの寄与率の値に基づき選択された候補アイテムを成分とするセンシング行列を作成するステップとを有する。前記クラス分類装置及びクラス分類方法において、前記寄与率計算手段の具体的な態様としては、例えば、前記センシング行列候補データと前記訓練データ由来の検証データとの線形的な制約を満たす解の係数を正規化することにより前記各候補アイテムの寄与率を算出する。また、前記クラス分類装置及びクラス分類方法においては、新しい分類を行う毎に、寄与率とセンシング行列をオンラインで更新することで、最新の分類結果の傾向を反映したセンシング行列による分類を行える。すなわち、前記クラス分類装置及びクラス分類方法において、センシング行列更新手段は最新の訓練データのセンシング行列候補データと当該訓練データ由来の検証データとの線形的な制約を満たす解の係数に基づき従前のセンシング行列に含まれる各候補アイテムの寄与率を更新しこの更新した寄与率の値に基づき当該センシング行列を更新する。尚、本発明は上記のクラス分類装置を構成する各手段としてコンピュータを機能させるクラス分類プログラムの態様とすることもできる。以上の発明によればスパース表現クラス分類に要する計算量を削減すると共に分類精度を低下させずに高速にクラス分類を行える。以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態に限定されるものではない。図1に示されクラス分類装置1は図6に示したようにSRC法の訓練データに由来するセンシング行列に含まれるアイテムの正解分類への寄与率を予め蓄積する。そして、図7に示したセンシング行列CAに含まれるアイテム集合から正解分類に対して寄与率の高いアイテム集合を選択することでセンシング行列CAをセンシング行列CBに縮小させる。これにより、クラス寄与率の高い少数の訓練データで精度低下を少なくさせながらSRC法によるクラス分類を高速に行える。また、図10に示したように新しいクラス分類を行う毎に寄与率とセンシング行列をオンラインで更新することにより最新の分類結果の傾向を反映したセンシング行列によるクラス分類が行える。本実施形態の説明で用いられる技術用語について説明する。スパースベクトル:空間を張る基底の線形結合でベクトルを表現したときに、ベクトル成分の係数の多くが0となるようなベクトルを意味する。kスパースネス:あるデータセットを表現した際の上記係数のうち、0でない係数の個数の最大値を意味する。計算量や圧縮センシングにおけるL1最適化問題とL0最適化問題の解が一致することを理論上証明するために必要な概念。圧縮センシング:スパース信号の再現理論である。センシング行列がある条件線形的な制約を満たすならば、L1最適化により高い確率でスパース信号が復元できる再現理論である非特許文献1。センシング行列をA、スパースベクトルをx、圧縮ベクトルをyで示すと、スパース信号を復元するためのL1最適化の線形的な制約は以下の式で表現できる。映像配信サービス等では、センシング行列Aを受信側で保持することにより、圧縮ベクトルyを配信するだけで、元々のベクトルxを復元できるため、データ転送量を削減することができる。線形計画問題:最適化問題において、目的関数が線型関数で、かつ線型関数の等式と不等式で制約条件が記述できる問題を意味する。この問題を解く手法を線形計画法と言う。一般に以下の形で記述できる。すなわち、圧縮センシングにおけるL1最適化は線形計画問題の1つと考えることができる。下記の式においてAは観測行列センシング行列、bは観測結果検証データ、xは未知ベクトルスパースベクトルを示す。[クラス分類装置1の構成]クラス分類装置1は図1に示されたようにクラス分類手段10、訓練データ分割手段11、L1最適化手段12、寄与率計算手段13、センシング行列作成手段14、センシング行列更新手段15を備える。クラス分類装置1の上記各機能手段はサーバコンピュータのハードウェアリソースによって実現される。すなわち、情報検索装置1は制御手段CPU100、記憶手段ハードディスク装置等101、通信インタフェース102、入力装置キーボード、ポインティングデバイス等103、出力装置モニタ104等のコンピュータに係るハードウェアリソースを備える。そして、これらのハードウェアリソースがソフトウェアリソースOS、アプリケーション等と協働することにより上記各機能手段が実装される。クラス分類装置1にはユーザ端末2からネットワーク3を介して検証データが供されるようになっている。検証データはクラス分類に供されるデータであり、例えばユーザ端末2のデータ処理手段20によって作成、編集された複数の画像からなる。データ処理手段20はユーザ端末2のハードウェアリソースCPU、記憶手段21、通信手段22、ユーザインタフェース23等とソフトウェアリソースとの協働により実装される。クラス分類手段10はユーザ端末2から供された検証データをSRC法によってクラス分類する多クラス分類器である。検証データの分類結果は訓練データとして保持される。訓練データ分割手段11はクラス分類手段10で得られた訓練データを図8に示したようにセンシング行列候補データと検証データとに分割する。L1最適化手段12は前記センシング行列候補データと前記検証データとの線形的な制約を満たす解を算出する。当該線形的な制約には線形計画問題として後述の式0で示したL1最適化問題が適用される。寄与率計算手段13は前記センシング行列候補データに含まれる各候補アイテムの正解分類への寄与率を算出する。寄与率計算手段13は具体的にはL1最適化手段12によって算出された解の係数を正規化することにより前記各候補アイテムの寄与率を算出する。センシング行列作成手段14は前記候補アイテムの寄与率の値に基づき選択された候補アイテムを成分とするセンシング行列を作成する。センシング行列更新手段15は最新の訓練データのセンシング行列候補データと当該訓練データ由来の検証データとの線形的な制約を満たす解の係数に基づき従前のセンシング行列に含まれる各候補アイテムの寄与率を更新する。そして、この更新した寄与率の値に基づき当該センシング行列を更新する。尚、本手段15による線形的な制約を満たす解の算出においても後述の式0で示したL1最適化問題の解法が適用される。[処理手順の説明]本実施形態の処理手順は図2に示すように訓練データの縮小されたセンシング行列を作成するオフライン処理S1~S5と最新の訓練データを得る毎に必要に応じて従前のセンシング行列を更新するオンライン処理S6とからなる。オフライン処理S1:クラス分類手段10はユーザ端末2から供された検証データをSRC法によってクラス分類する。検証データの分類結果は訓練データとして保持される。S2:訓練データ分割手段11はS1にて得られた訓練データを図8に例示されたようにセンシング行列候補データと検証データとに分割する。訓練データのアイテムには、それぞれクラスラベルが付与されている。それぞれのクラスに十分な数のアイテムがあり、図8に示したようにそれぞれのクラス内のアイテム集合はセンシング行列候補データと検証データに分割される。センシング行列候補データは、SRC法において検証データをスパース表現する際の基底ベクトルの候補集合となっており、候補アイテムをai1≦i≦nとした場合、センシング行列はA=[a1,a2,...,an]と表現される。但し、図9に示したように、先頭から順番にクラスC1,...,Ckの順で各クラスに属するアイテムa1~anが並ぶように配置される。訓練データの分割法には図8aに例示した等分割法や図8bに例示した1heldout法が適用される。最も単純な分割方法は等分割法でありクラス内のアイテム集合を等分割する。訓練データが十分にない場合は、1heldout法により、1つのアイテムを除いてそれ以外をセンシング行列データとする。S3:L1最適化手段12はS2にて分割されたセンシング行列候補データと検証データとの線形的な制約を満たす解を算出する。具体的には図3に示した手順S101~S103を実行する。S101S2で得られたセンシング行列候補データから成る行列A’と検証データを格納した集合Aの入力を受ける。S102検証データ中のアイテムyが集合Aに含まれていることy∈Aを確認する。S103行列A’とアイテムyとの線形制約y=A’xを条件とするL1最適化問題を解き、その解をx^とする。すなわち、行列A’が行列A=[a1,a2,...,an]で示される場合、SRC法では下記の線形制約で示されるL1最適化問題を解くことになる。但し、現実的にはノイズが含まれていることも多く上記の問題を厳密に解くことは困難なため、実質的には誤差を許容した以下の式0で示される最適化問題を解く。L1最適化問題の一般的な計算量は少なくともO要するがnはアイテム数、スパースベクトルの解xの算出にはほぼ線形で解けるアルゴリズムが提案されている。このアルゴリズムは前記の一般的な計算量よりも少ないのが特徴であり、その計算量はOだけで済む但し、kはk‐スパースネスの値、すなわち空間のスパース性を示す尺度であり、係数がゼロとならない最大値。以上の手順S102,S103はアイテムyの数だけ繰り返し実行される。S4:寄与率計算手段13はS3S101~S103にて算出された解x^に基づき前記センシング行列に含まれる各候補アイテムの正解分類への寄与率を算出する。具体的には図3に示した手順S104~S106を実行する。S104検証データ中のアイテムyの所属クラスと同じクラスに属するベクトル内の係数で解x^を正規化した値sを保存する。S105アイテムyの数だけS104の手順を繰返し実行する。S106行列A’に含まれる全ての候補アイテムaijに対して、以下の式による演算によってSCOREaij以下、スコアSaijと称するを計算し、出力する。上記の式において、sljはl番目の候補アイテムをyとして式0のL1最適化問題を解いた解x^のj番目の係数を正規化した値である。Saijのとり得る値の範囲は0以上1以下となり、候補アイテムaijの正解分類への寄与率の平均値を示している。S5:センシング行列作成手段14はS4S104~S106にて算出された候補アイテムaijの寄与率のスコアSaijに基づき選択された候補アイテムを成分とするセンシング行列を作成する。具体的には図4に示した手順S201~S205を実行する。S201センシング行列候補アイテム集合A’、S4にて算出された集合A’の全ての候補アイテムaijの寄与率のスコアSaij、クラス集合CSC1,...,Ckの入力を受ける。また、クラス毎のセンシング行列候補アイテムの所望選択数kが設定される。S202クラスCがクラス集合CSに含まれていることC∈CSを確認する。S203a∈Cかつa∈A’となるセンシング行列候補アイテムaの集合からスコアSaの値が上位k個の候補アイテムaをセンシング行列の成分として選択する。S204クラス集合CSの全てのクラスC1~kについてS203を実行する。S205クラス集合CS中の全てのクラスC1~kにおいて、S203で選択されたk個の候補アイテムaを成分とするセンシング行列を作成し、出力する。以上の手順S1~S5によって図7に例示された通常のセンシング行列CAよりも情報量が縮小され且つ訓練データに対して寄与率の高いアイテムを含んだセンシング行列CBが作成される。図7に示された行列CBは、クラスC1ではアイテムa12,a15が選択され、クラスC2ではアイテムa25,a27が選択され、クラスC3ではアイテムa34,a38が選択され、クラスC4ではアイテムa43,a49が選択されて情報量が縮小されている。尚、縮小されたセンシング行列CBはクラス分類装置1の記憶手段101に保存される。オンライン処理S6:新たな検証データがクラス分類手段10によってクラス分類されて最新の訓練データが取得されると、センシング行列更新手段15は必要に応じて従前のセンシング行列を更新する。すなわち、図10に示されたように、新たな訓練データ新たな検証データyのクラス分類によって得られたクラスCiに含まれるアイテムが取得される毎に、当該訓練データに基づき従前のセンシング行列Aに含まれるアイテムの寄与率のスコアSnを逐次的に更新する。次いで、この更新した寄与率のスコアSn1に基づきセンシング行列Aを更新すべきか判定する。すなわち、センシング行列A内のクラスCiにおいて更新された寄与率のスコアSn1が最小であり且つ閾値tよりも低いアイテムが含まれているか否かを判断する。この寄与率の低いアイテムが含まれていると判断された場合、当該アイテムを他の所望のアイテムに差し替える。このようにしてセンシング行列Aが更新される。図5を参照しながらセンシング行列更新手段15によって実行されるセンシング行列更新S6の具体的な手順S301~S305について説明する。S301:最新の訓練データの情報新たな検証データyが属するクラスラベルC、従前のセンシング行列A、センシング行列A中のアイテムaの寄与率のスコアSa、の入力を受ける。また、忘却係数f、最小寄与率の閾値t0<t<1が設定される。S302:アイテムaがセンシング行列A中のクラスCに含まれているかa∈Aかつa∈Cを確認する。S303:アイテムaと検証データyとの線形的な制約式0を満たす解の係数を正規化した値正規化スコアに基づきセンシング行列Aに含まれるアイテムaの寄与率のスコアSを更新する。具体的には式1を用いて0以上1以下の範囲に確率として正規化したスコアSを利用する。オンライン処理の開始前に訓練データを利用できるのであれば、オフライン処理によるスコアを求め、これを初期スコアS0とする。n回目のクラス分類結果の線形的制約式0を満たす解の係数を正規化した正規化スコアをCn、寄与率のスコアをSnとすると、下記の式3で示される漸化式によってSnを算出できる。但し、fは一種の忘却係数とも呼べる0<f<1の定数である。この式は直前のクラス分類時に得られた正規化スコアCnを1-fの重みで採用し、それ以前のスコアSn1をfの重みで採用するということであり、0≦Sn≦1が成り立つ。この式の意味するところは、再帰的にSnを展開すると理解できる。上記式を再帰的に展開すると下記の式になることが数学的帰納法にて証明できる。この式にて、Cn,Cn1,...,C1,S0のそれぞれのスコアの係数の総和をとると、下記の表に示したように、1になることが確認できる。漸化式3で示される寄与率のスコアSnは直前の分類結果の正規化スコアCnを1-fで重み付けし、さらにその以前のスコアSn1が古くなるほど係数fを乗じて指数的に小さくした重みで重み付けした混合スコアとなる。実際には、以前の全てのスコアを保持し続けるのは効率的では無いため、直前の寄与率のスコアSのみと混合すれば良い漸化式3を利用して寄与率のスコアSを更新する。S304:センシング行列AにおけるクラスCに含まれる全てのアイテムaの寄与率のスコアSaをS303によって更新する。S305:アイテムa∈センシング行列Aかつアイテムa∈クラスCとなるアイテムaのうち、S304で算出した寄与率のスコアSaが最小となるアイテムaで、Sa<閾値tとなる場合に、当該アイテムaを行列Aから除去する。そして、検証データyの所望のアイテムを挿入することで更新したセンシング行列Aを出力する。S305において前記所望のアイテムは例えば最新または過去の訓練データのセンシング行列に含まれるクラスCiに含まるアイテムの集合から適当に選ばれたものが挙げられる。例えば寄与率のスコアが最も高いものが選択される。以上の手順S301~S305により常に最新の情報を反映させたクラス分類を継続して行うことができる。[本実施形態の効果]以上のようにクラス分類装置1による圧縮センシングによればスパース表現されたベクトルのクラス分類サービスを提供する際に分類精度の低下を最小限に抑えながらセンシング行列の縮小が行える。これにより、センシング行列の膨大化による分類時間の遅延を回避でき、SRC法によるクラス分類を高速に行える。特に、オフライン処理においては、訓練データのセンシング行列Aに含まれるクラスCj毎に候補セットの中から、寄与率のスコアSaijの高いアイテムが選択される。これにより、候補セットの中から検証セットの分類に貢献した順に訓練データが選ばれることになり、図7に示されたように候補セット全てを利用した場合よりも小さいセンシング行列を作ることができる。また、オンライン処理では寄与率が必要に応じて逐次更新されるので、より最新の分類結果の傾向を反映したセンシング行列を構築し分類を行うことができる。さらに、センシング行列の候補アイテムはその寄与度の閾値に基づき選択されるので所望のセンシング行列を作成できる。例えば、CPUやメモリ性能と1秒以内で新規データにラベルを付与したいといったサービス上の要求の両方に応じて、選択する候補アイテムの個数が適宜選択され、任意に縮小されたセンシング行列を得ることができる。本実施形態のクラス分類装置1は例えば検索対象の画像データを一元的に管理する画像管理システムにおいて適用されると当該システムの画像管理機能をより一層最適化させることができる。[本発明のプログラムとしての態様]本発明は上記のクラス分類装置1の各機能手段の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータによって実行して本発明を実現することができる。また、コンピュータで前記機能手段を実現するためのプログラムをそのコンピュータが読み取り可能な記録媒体、例えば、FDFloppy登録商標Diskや、MOMagneto-Opticaldisk、ROMReadOnlyMemory、メモリカード、CDCompactDisk-ROM、DVDDigitalVersatileDisk-ROM、CD-R、CD-RW、HDD、SSD、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。"