"電子デバイス上で実施される、物理的センサデータ分類子を生成するための方法であって、複数の物理的センサデータを受信することと、メトリック関数を備える検索アルゴリズムを使用して、前記物理的センサデータに基づいて投影ベクトルを識別することと、ここにおいて、投影ベクトルを識別することが、スパース行列変換を使用して前記メトリック関数に関連した1つまたは複数の固有値を計算することを備え、前記物理的センサデータの少なくとも一部を前記投影ベクトルに投影することによって、物理的センサデータ分類子を生成することとを備える、方法。前記物理的センサデータが顔画像データ、音声オーディオデータ、ワイヤレス通信信号またはレーザーレンジファインダーデータのうちの1つを備える、請求項1に記載の方法。前記検索アルゴリズムが反復して計算される、請求項1に記載の方法。前記メトリック関数がフィッシャー判別を備える、請求項1に記載の方法。前記検索アルゴリズムが二分法検索を備える、請求項1に記載の方法。物理的センサデータを備えるデータセットを記憶するように構成されたメモリと、プロセッサとを備え、前記プロセッサが、複数の物理的センサデータを受信することと、メトリック関数を備える検索アルゴリズムを使用して、前記物理的センサデータに基づいて投影ベクトルを識別することと、ここにおいて、投影ベクトルを識別することが、スパース行列変換を使用してメトリック関数に関連した1つまたは複数の固有値を計算することを備え、前記物理的センサデータの少なくとも一部を前記投影ベクトルに投影することによって、物理的センサデータ分類子を生成することとを行うように構成される、モバイル電子デバイス。前記物理的センサデータが顔画像データ、音声オーディオデータ、ワイヤレス通信信号またはレーザーレンジファインダーデータのうちの1つを備える、請求項6に記載のモバイル電子デバイス。前記検索アルゴリズムが反復して計算される、請求項6に記載のモバイル電子デバイス。前記メトリック関数がフィッシャー判別を備える、請求項6に記載のモバイル電子デバイス。前記検索アルゴリズムが二分法検索を備える、請求項6に記載のモバイル電子デバイス。物理的センサデータを分類するための方法をプロセッサに実施させるように構成された命令を備える非一時的コンピュータ可読媒体であって、前記方法が、複数の物理的センサデータを受信することと、メトリック関数を備える検索アルゴリズムを使用して、前記物理的センサデータに基づいて投影ベクトルを識別することと、ここにおいて、投影ベクトルを識別することが、スパース行列変換を使用して前記メトリック関数に関連した1つまたは複数の固有値を計算することを備え、前記物理的センサデータの少なくとも一部を前記投影ベクトルに投影することによって、物理的センサデータ分類子を生成することとを備える、非一時的コンピュータ可読媒体。前記物理的センサデータが顔画像データ、音声オーディオデータ、ワイヤレス通信信号またはレーザーレンジファインダーデータのうちの1つを備える、請求項11に記載の非一時的コンピュータ可読媒体。前記検索アルゴリズムが反復して計算される、請求項11に記載の非一時的コンピュータ可読媒体。前記メトリックがフィッシャー判別を備える、請求項11に記載の非一時的コンピュータ可読媒体。前記アルゴリズムが二分法検索を備える、請求項11に記載の非一時的コンピュータ可読媒体。複数の物理的センサデータを受信するための手段と、メトリック関数を備える検索アルゴリズムを使用して、前記物理的センサデータに基づいて投影ベクトルを識別するための手段と、ここにおいて、投影ベクトルを識別することが、スパース行列変換を使用して前記メトリック関数に関連した1つまたは複数の固有値を計算することを備え、前記物理的センサデータの少なくとも一部を前記投影ベクトルに投影することによって、物理的センサデータ分類子を生成するための手段とを備える、モバイル電子デバイス。前記受信する手段がプロセッサ実行ソフトウェアを備え、前記識別する手段がプロセッサ実行ソフトウェアを備え、前記生成する手段がプロセッサ実行ソフトウェアを備える、請求項16に記載のモバイル電子デバイス。前記物理的センサデータが顔画像データ、音声オーディオデータ、ワイヤレス通信信号またはレーザーレンジファインダーデータのうちの1つを備える、請求項16に記載のモバイル電子デバイス。前記検索アルゴリズムが反復して計算される、請求項16に記載のモバイル電子デバイス。前記メトリック関数がフィッシャー判別を備える、請求項16に記載のモバイル電子デバイス。前記検索アルゴリズムが二分法検索を備える、請求項16に記載のモバイル電子デバイス。一実施形態は、電子デバイスにおけるセンサによって受信されたデータを分類するためのシステムおよび方法である。この実施形態では、電子デバイスは、センサデータをキャプチャし、適切な分類子を生成し、データを1つまたは複数の分類に分類する迅速なデータ分類プロセスを含む。たとえば、センサは画像センサであってもよく、したがって迅速な分類プロセスは、センサによってキャプチャされた画像を分類するように構成されてもよい。1つの特定の実施形態では、キャプチャされた画像は1つまたは複数の顔を含んでもよく、迅速な分類プロセスは、顔を含むキャプチャされた画像の一部を識別するために使用されてもよい。関係する実施形態では、キャプチャされた画像は1つまたは複数の顔を含んでもよく、迅速な分類プロセスは、データストレージから同じ人の他の画像を取り出すために、画像センサによってキャプチャされた顔を、他のあらかじめ記憶された画像に対して照合するために使用されてもよい。顔だけでなく、いかなる物体にも、この実施形態の分類方法を用いてもよいことが容易に認識されよう。これらの実施形態のいくつかで、迅速な分類システムおよびシステムは、本明細書ではスパース行列LDAと呼ぶLDAの変更バージョンを使用することができ、スパース行列変換は、従来のLDAプロセスのために上記で説明したより典型的な行列変換に置き換わる。この実施形態ではLDAは最適化されているが、最適化は同様に、以下でより詳細に説明する他の分類子の検索アルゴリズムに適用することができる。この実施形態では、スパースLDAの中の判別ベクトルは、制約付き最適化問題に対する解として計算することができる。この実施形態は、この制約付き最適化問題に関連するメトリック関数の計算を最適化することを企図する。特に、メトリック関数は、スパース行列変換SMT:SparseMatrixTransformを用いて変更されてもよい。SMTは、固有値および固有ベクトルの計算など、メトリック関数の副計算を実行するために使用されてもよい。SMTは、この計算の精度を制御するために、複数の制約を与える。特に、これらの制約は、最適化された判別ベクトルの中で非ゼロのエントリの数を制御するために、緩和されたり、またはより厳しくされたりすることができる。最適化された判別ベクトルの中で非ゼロエントリが多くなると、次元数および計算複雑性はより高くなり、一方で非ゼロエントリが少なくなると、分析されるべきデータの中で次元数および複雑性はより低くなる。制約を緩和したり、より厳しくしたりすることを可能にすることによって、所望の計算精度のレベルを達成することができる。本出願全体を通して、SMTをメトリック関数の一部として組み込むLDAのことを、スパース行列LDAと呼ぶ。典型的なフィッシャーLDAは、最適化問題における制約が完全に緩和された場合、提案するスパース行列LDAフレームワークの特殊なケースとなる。制約を厳しくすることはスパースな特徴につながり、分類の精度を低くする可能性があるが、計算的には遥かに効率が高くなる。スパース行列特徴の計算のために最適化されたメトリックは、典型的なフィッシャーLDAにおいて使用されたものと同じである。しかしながら、検索空間は、異なるクラスからデータを判別するために、RNにおいてスパースである潜在的に有益なベクトルのセットだけを含むように制約される。したがって、スパース行列LDAは、顔認識などのターゲットの目的のために最も有益なベクトルに焦点を当て、一方で、最終的な分類の精度を高めるために大いに役立つベクトルを無視している。一実施形態では、候補のスパース判別方向のプールを生成するために、スパース行列変換は、高次元信号の共分散推定値の正則化のために使用されてもよい。SMTモデルは、ギブンス回転として知られる一連の対の座標回転の積として直交変換を推定する。固有分解のスパーシティは、SMTモデルにおけるギブンス回転の数を制限または増加することによって制御することができる。実験結果によって、提案するアルゴリズムを使用して検索されるスパース判別方向は、2つのクラスのデータセットにおいて、所望の数の非ゼロ要素だけを保持するようにハードしきい値処理された典型的なフィッシャー判別方向よりも優れた判別能力を示すということが明らかである。したがって、新しい判別分析のフレームワークは、分類の精度と計算複雑性との間の有利な妥協点を提供する。これらの実施形態のうちのいくつかは、詳細にはLDAを用いて実施される顔認識を特に参照しながら論じられているが、これらの実施形態の中で開示される改善されたスパース行列方法は、様々なリソース制約時間、計算能力などの下で、連続した固有値または固有ベクトルの計算を必要とするメトリック関数を備える任意の検索アルゴリズムに適用することができる。たとえば、開示する実施形態は、主成分分析PCA:PrincipalComponentAnalysisおよびフーリエ変換の組成変更など、他の検索メトリック関数計算の固有値に容易に適合させることができる。従来、スパース行列変換SMTは、典型的な固有値問題またはPCAに対するスパース正則化された解を見つけ出すという意図とともに使用される。そのような問題は、SMTが単一の行列に適用され得るという期待とともにアプローチされる。代わりに、出願人は、SMTフレームワークが、1つではなく2つの対称行列を備える一般化された固有値問題に対するスパース正則化された解を見つけ出すために拡張され得るということを認識したたとえば、図2の204、ならびに図8の804および805の行列SbおよびStを参照されたい。出願人は、さらに、この拡張が、より迅速にデータを分類するためにデータセット分類の状況でさらに適用され得るということを認識した。従来のSMTシステムアプローチは、個々にSbとStのうちの1つに回転を適用するので、この問題には適さない。代わりに、出願人は、2つの行列Sb-λStの線形結合に反復してSMTを適用するための方法を判断した。以下で説明するように、出願人の反復方法によって、主要な固有値および固有ベクトルを判断するために、行列Sb、Stに個別にSMTを適用する必要がなくなる。提案する最適化を使用して生成されるスパース固有ベクトルは、以下でさらに説明するように、データ分類アルゴリズムにおける高速次元削減のために、または高次元線形回帰問題における変数の収縮/選択のために使用することができる。出願人の方法は、回帰問題などの様々なアルゴリズムを解くために使用することができる。たとえば、LDAを参照すると、固有値のスパース行列計算は、工場トレーニングセットを使用して投影ベクトルを判断するために、以下で説明する方法を使用して実行することができる。工場トレーニングセットは、エンドユーザによるフィールドでの使用を見越して生成することができる。本実施形態は、工場トレーニングセットに基づいて、以前に可能であったよりも速い、および/またはより正確なデバイスのトレーニングを可能にする。これらの方法はまた、フィールドで動作するモバイルデバイスのためのさらに速いその場での分類、トレーニングおよび再トレーニングを可能にする。本実施形態によって改善された、いくつかの検索アルゴリズムは、LDAなど、分類子を投影する投影ベクトルを求めることができ、一方で他のものは、線形プログラミングを使用することなど、他の知られている方法を通じてパラメータを最適化しようとすることができる。概して、固有値と固有ベクトルのセットの計算を多数必要とする任意の分類アルゴリズムは、以下で説明する改善点を用いることができる。本開示では、物理的センサデータは広義の用語であって、当業者にその通常および慣習的な意味を与えられるべきでありすなわち、特殊な、またはカスタマイズされた意味に限定されるものではない、限定されないが、顔画像データ、音声オーディオデータ、ワイヤレス通信信号、レーザーレンジファインダーデータ、またはカメラ、マイク、圧力センサなどから派生した任意のデータセットを含む。同様に、本開示では、投影ベクトルは広義の用語であって、当業者にその通常および慣習的な意味を与えられるべきでありすなわち、特殊な、またはカスタマイズされた意味に限定されるものではない、限定されないが、データが投影される、すなわちデータが以前に示された次元と異なる次元のセットで記述されるように変換されるコンピュータシステム内の任意のデータ構造を含む。本開示では、検索アルゴリズムは広義の用語であって、当業者にその通常および慣習的な意味を与えられるべきでありすなわち、特殊な、またはカスタマイズされた意味に限定されるものではない、限定されないが、関係するベクトルまたは値を識別するために使用される任意のアルゴリズムを含む。たとえば、図4に示すアルゴリズムは、所望の程度の精度まで最適値λに近づく値λを識別しようとする検索アルゴリズムを備える。本開示では、メトリック関数は広義の用語であって、当業者にその通常および慣習的な意味を与えられるべきでありすなわち、特殊な、またはカスタマイズされた意味に限定されるものではない、限定されないが、それによって所望の精度または完成のレベルが評価される計算プログラム内の任意の関数を含む。たとえば、図3に示すλの関数としてSb-λStの最大固有値を表す関数fλは、メトリック関数を備える。メトリック関数はそれ自体複数のコンポーネントメトリックを備えてもよく、メトリック関数という用語は、所望の精度または完成のレベルが達成される程度を評価するために使用される範囲で、これらのコンポーネントメトリックのうちの任意のものに等しく適用できるということが容易に認識されよう。本開示では、スパース行列変換は広義の用語であって、当業者にその通常および慣習的な意味を与えられるべきでありすなわち、特殊な、またはカスタマイズされた意味に限定されるものではない、限定されないが、図5に示す動作を含む。しかしながら、図5は任意の境界線に沿ってSMTの動作を中断させており、SMTの副動作の任意の表現を描いていることが容易に認識されよう。たとえば、forループ502はwhileループと置き換えられてもよく、個々の動作は、同じ側の動作効果を達成しながら、並べ替えられ、再特徴付けされてもよいことが、当業者には容易に認識されよう。したがって、本開示でのSMTへの参照は、図5に示すアルゴリズムと同じ動作効果を達成する任意のアルゴリズムに関する。本開示では、分類子は広義の用語であって、当業者にその通常および慣習的な意味を与えられるべきでありすなわち、特殊な、またはカスタマイズされた意味に限定されるものではない、限定されないが、注釈付きのデータのセットから派生した分類子101aおよび101bなどの境界または領域を含む。分類子とは生のインポートされた注釈付きデータのことを指してもよいが、また、分類子101aおよび101bが投影ベクトル103bに投影される場合など、異なる表現のデータのことを指してもよい。図7は、開示される実施形態のうちのいくつかを実装するモバイルデバイス700を示す。モバイルデバイスは、デバイス上で操作されるデータの中のパターンを認識するように構成された複数のソフトウェアおよびハードウェアを備えてもよい。たとえば、デバイスはカメラ703を備えてもよく、モバイルデバイスは様々な分類技法を使用して、複数の顔から1つまたは複数の顔704を認識するようにトレーニングされてもよい。ユーザがトレーニング画像のコーパスに新しいデータを組み込むと、システムは、同じ顔の特徴を様々な採光条件および環境の下でより容易に認識できるように、システム自体を再トレーニングすることができる。明快のために、本開示ではカメラシステムを、特に顔の分類に関して説明しているが、データ分類技法を実装する多数の他のデバイスコンポーネントが容易に認識されよう。たとえば、モバイルデバイス700上に位置するワイヤレス受信システム、音声認識システムおよびオーディオ送信システムもまた、ワイヤレス送信信号、音声入力および諧調パターンをそれぞれ分類するために、データ分類技法を各々用いることができる。これらのシステムの各々は、それらの入力を多数の次元を備えるデータセットとして取得することができる。たとえば、画像データの1つの解釈によって、画像内の各画像ピクセルは、所定の次元に関連する値に対応するピクセル強度で、データの個別のデータの次元を備えてもよい。この例によって、40×40ピクセルの画像では、それに応じて1600次元となる。フィッシャー線形判別分析LDAは、2つ以上のデータのクラス間で適切な分離子を識別するための知られている方法である。次に、この分離子は、新しいデータセットを素早く分類するために使用することができる。画像コンテンツの中など、多くの次元が存在する場合、LDAは次元削減を可能にするので有用である。すなわち、上記の例における40×40ピクセルの画像のうちの1600ピクセルすべてが、たとえば顔の認識のためにすべて等しく重要である可能性は低い。最初に、分類された画像のトレーニングデータセットがあるとすれば、顔画像を特徴付けるのに最も適した次元すなわちピクセルを識別するために、LDAを実行することができる。その後、識別される必要のある顔画像から新しいデータセットが与えられる場合、新しいデータのための適切なカテゴリー分類すなわち、顔または非顔または特定の個人の顔を含むものなどを迅速に判断するために、これらの適した次元だけを考慮する必要がある。スパース行列変換スパース行列変換SMTのための疑似コードを図5に示す。いくつかの実施形態は、より効率的な二分検索を可能にするために、SMTをfλの計算に組み込むことを企図する。SMTアルゴリズムは最初に、Sを行列Sの初期値に初期設定する501。次いで、システムは、SMTモデル次数rまでの値の間を反復する502。各反復のために、システムは比率のためのargMax503を識別する。次いでシステムは、504のために、S内の副行列の非対角要素に対する対角要素のアークタンジェント最大比率を判断する。各反復でギブンス回転T505が判断され、次の中間スパース行列Sを取得するために、保留のスパース行列Sに適用される。図6は、対称ギブンス回転行列の図である。一旦反復がSMTモデル次数まで実行されると、その後、固有値Erはギブンス回転の乗算によって割り当てられてもよい508。同様に、固有値は対角を取り込むことによって判断することができる509。図8に関するこれらのステップのより徹底的な説明を以下に示す。当業者が認識するように、典型的な固有値分解問題はSE=EDと書くことができ、式中Sは実数および対称行列であり、Eは固有ベクトルの正規直交行列であり、Dは固有値の対角行列である。典型的な固有値問題を解くために、ヤコビ固有値アルゴリズムを使用することができる。ヤコビ固有値アルゴリズムは、一連の正規直交変換を通じて反復してSを対角行列に変換する606。S=SでありT:=Tim,jm,θmである場合は、4つの要素の中だけにある単一性行列とは異なる対のギブンス回転である:およびヤコビアルゴリズムのr回の反復を実行した後で推定される固有ベクトル行列608および固有値行列609は、次のように書くことができる:式中、r→∞、Dr→Dである場合、は限界にある。スパース行列変換SMTは、早期に終了するヤコビ固有分解であり、すなわちヤコビ固有分解におけるギブンス回転の数は小さく保たれる:r<<NN-1/2。上述のように、変数rはしばしばSMTモデル次数と呼ばれる。固有分解のスパーシティは、SMTモデル次数rを変えることによって、増加または減少させることができる。SMTの各反復での適切なギブンス回転Tm=Tim,jm,θmの選択は、スパース固有分解の精度を判断する。最適な座標ペアim,jmを判断するために、SMTアルゴリズムは、対角要素に対する非対角要素の最大比率図6のステップ603のために、S内の2×2の副行列を検査する図6のステップ603。次いで、im,jmおよびjm,imでの非対角要素がSでゼロになるように、回転角θmが選択される図5のステップ504。次数の数rに従って、所望の数の反復が実行された後、次いでスパース固有分解は、それぞれ図5のステップ508およびステップ509によって、24に基づいて判断されてもよい。スパース行列変換を組み込んだフィッシャー判別方法上述のように、SMTは、rを変えることによって推定される固有ベクトルのスパーシティを増加または減少させることを可能にする。次の節では、図4の二分法検索アルゴリズムへSMTを組み込むことについて詳述する。一般性を失わずに、対応する固有ベクトルによって、をSb-λStおよびの最大固有値とする。集合が、固定のrのため、および[0,1]の範囲のλのために、すべてのSMT推定固有ベクトルの集合を示すものとする。以下の制約付き最適化問題に対する解として、スパースフィッシャー線形判別ベクトルを計算することを提案する:典型的に、SMTモデル次数rのより小さな値は、判別ベクトルのよりスパースな推定値をもたらし、その逆も同様である。rが大きい場合、集合に対するスパーシティ制約は緩和され、スパースフィッシャーLDAは典型的なフィッシャーLDAに縮小する。29に従って、最適なスパース判別投影は、範囲0,1のλのために、Sb-λStの固有ベクトルとして計算される。上記の説明と類似した方法で、判別基準を最大化するλの値はまた、固有値がゼロに等しくなる値でもあるということを示すことができる付録Aを参照されたい。このように、frλ:0,1→RがSb-λStの最大固有ベクトルを表すものとすると、λの関数として、次数rのSMTモデルを使用して以下が推定される。すなわち、21の制約付き最適化問題は、同等に次のように解くことができる:r→∞、frλ→fλ、したがってである場合、限度にある。いくつかの実施形態では、関数frλは、検索アルゴリズムLDAのためのメトリック関数と呼ぶことができる。この場合も、上記で説明したものと類似の方法で、関数frλ:は0,1で有界であり、閉区間上で次の特性を満たす付録Bを参照されたい:したがって、非線形方程式frλ=0の解は、先に説明したように、二分法を使用することによって計算することができる。二分法に基づいておよびを推定するための反復方式は、図8のアルゴリズムの中に示す。図8は、SMT変換方法を組み込んだ細分によって、反復してSb-λStの最大固有値をゼロにするための一般化されたアルゴリズムである。このアルゴリズムを、LDAのための検索アルゴリズム、およびメトリックとしての関数fλと呼ぶことができる。たとえば、PCAを用いる別の分類問題は、多数のメトリックの反復を使用して固有値を識別した検索アルゴリズムPCAを同様に備える。両方の場合、および同様の場合、固有値の計算を最適化するためにSMTを使用することができる。図8のステップ801~803、806~812は、図4のステップ401~403、406~412に対応する。しかしながら、804および805のために必要なfλの計算は、ここではスパース行列変換の使用とともに最適化される。したがって、アルゴリズムは、非線形方程式frλ=0のルートとして、スパースフィッシャー判別基準の最適値を推定する。このルートは閉区間a,bの中間点と推定され、ここでaとbの初期値はそれぞれ0と1であり、次いでaとbの間のギャップが2Kに減少するまで反復して更新される。次いでおよびの最終値がおよびとして計算され、式中λはk番目の反復におけるaとbの間の中間点を示し、Kは、ルート発見アルゴリズムが実行される反復の総数を示す。λが更新されるたびに、frλ=0は、λの新しい値のためにSb-λStのSMT分解を実行することによって計算される。ここでも、この特定の二分法アルゴリズムを例示のために示しているが、この特定の例に対する多数の変形形態が容易に認識されよう。たとえば、パラメータaおよびbは、より洗練された中間検索変数と置き換えられてもよく、実行される反復は、単なるKではない追加の要因に基づいて判断されてもよい。同様に、次数rは反復ごとに異なってもよく、たとえばユーザがモバイルデバイス上で顔認識トレーニングを試みている状態など、アルゴリズムが実行される領域に関係する複数の不特定のパラメータによって決まってもよい。実証となる適用以下の表および図面は、上記のアルゴリズムのいくつかの実験的実証について様々な結果を示す。これらの例のために、顔と非顔を表す複数の20×20のパッチが使用されている顔を備えるクラスω1と非顔を備えるクラスω2。簡単のために、クラスω1を正のクラスと呼び、ω2を負のクラスと呼ぶことができる。20×20のパッチは平均値除去demeanedされ、分散正規化され、400次元のベクトルとして構成される。トレーニングのために、ω1からの2000サンプルとω2からの51000サンプルが使用されている。テストのために、ω1から使用されるサンプル数は1400であり、ω2から使用されるサンプル数は34000である。それぞれクラス間散乱行列Sbとクラス内散乱行列Stを計算するために、顔からのトレーニングデータベクトルと非顔からのトレーニングベクトルが使用される。最適なフィッシャー判別基準および判別ベクトルは、図4のアルゴリズムを使用して計算されている。同様に、およびは、図8のアルゴリズムを使用して計算されている。これら実験において使用した顔は、正面、直立の顔を備える。すなわち、頭の回転と面外の横向きの回転との両方のための許容可能な範囲は、-15から15度程度である。図9A~図9Cは、それぞれ最適なフィッシャー線形判別図9A、しきい値処理されたフィッシャー判別図9B、およびSMT最適化フィッシャー判別図9Cのための顔対非顔の分類902acおよび対応する線形判別901acの結果を示す。線形判別901aおよび901bと比較すると、SMT最適化判別のための線形判別901cはより少ない次元を備える。図9Aに関して、901aによって表される最適化判別ベクトルは、次のルールに従って、上記で説明したクラスw1またはクラスw2のいずれかからテストベクトルxを分類するために使用されている。式中しきい値Tは、所望の分類率を与えるように調整される。図9Bに関して、テストのしきい値処理バージョンが実行されている。N次元のデータのために、フィッシャー投影の計算は、Nの乗算およびN-1の加算を必要とする。Nが大きい場合、必要とされる計算はかなりの量になる場合があり、分類方式のソフトウェア実施を遅くし、同方式のハードウェア実装を高価なものにする。分類精度と計算との間のトレードオフを制御できるようにする単純な方策は、の構成要素をハードしきい値処理することであり、しきい値よりも大きい、またはしきい値と等しい振幅を有するものだけを残す。これらのテストの結果は図9Bの中で示され、次のルールを使用している:式中θcはハードしきい値処理関数を示し、定数cはしきい値処理された判別ベクトルのスパーシティを制御する。下位の計算の分類制度をトレードオフするために、図3aに示すように、10個だけの非ゼロコンポーネントとともに、cの値を選択して、しきい値判別ベクトルを取得する。ここで、ドット積の計算は、10個の乗算と9個の加算だけを必要とする。しかしながら、計算の縮小は、1102bに示すように、分類パフォーマンスの大幅な劣化という犠牲を払う。99の固定の肯定検出率のために、スパース投影ベクトルとの誤検出率は40.7まで上昇する。顔および非顔の分類は、ルールを使用してテストサンプリングする。図面11A~11Cの各々における青い破線は、35におけるTの値を表す。表1は、しきい値処理された判別のスパーシティの関数として、分類の精度を示す。肯定検出は99で固定されている。図9Cに関して、テストもまた、上記のフィッシャー判別方法のスパース行列変換実装を使用して実行されている。2つのクラスw1、w2からのトレーニングデータのベクトルは、散乱行列SbおよびStを計算するために使用されている。スパース判別方向およびスパース判別基準の最適値は、非線形方程式805を解くことによって推定されている。スパースフィッシャー線形判別分析を実行するために、SMTモデルの中のギブンス回転の数rは固定されている。ルート発見二分法が実行される反復の最大数Kもまた固定されており、具体的にはK=20が使用されている。rが260に固定されている場合の、アルゴリズムの反復数kの関数としてのλおよび|frλ|の推定値は、以下に、それぞれ1002Cおよび1002Dのプロットの中で示されている。スパース判別基準の最適値は、と推定されており、これは、従来のFDAのために推定された典型的なフィッシャー判別基準λF=0.906の最適値よりも小さい。対応するスパース判別ベクトルは、と判断されている。スパース投影ベクトルは、20×20のマスク901cとして構成されている。投影ベクトルは11個だけの非ゼロコンポーネントを有するので、のテストベクトルxを空間に投影するのに関与する計算は、11個の乗算と10個の加算だけである。判別方向としてを用いるデータ分類パフォーマンスを902cに示す。しきい値Tは99の肯定検出率を与えるように調整されており、達成された誤検出率は16.7であった。比較のために、同様の計算負荷と肯定検出率について、ハードしきい値処理されたフィッシャー特徴902bは、42.0の誤検出率をもたらす。図10は、rが260に固定されている、図5のアルゴリズムを使用した、また図8のアルゴリズムのための、顔対非顔の分類問題のためのλ対kの反復および|frλ|対kの反復のプロットを示す。特に、プロット1002aとプロット1002bとのペア1000Aは、それぞれ、図5のアルゴリズムを使用するkの連続反復のためのλ1003aおよび|frλ|1003bの予想値を示す。同様に、プロット1002cとプロット1002dとのペア1000Bは、それぞれ、図8のアルゴリズムを使用するkの連続反復のためのλ1003cおよび|frλ|1003dの予想値を示す。より大きい反復については、図5のアルゴリズムのλの値はλFのために0.906に収束し、一方図8のアルゴリズムのλの値はλFrのために0.85に収束する。概して、λの値が大きいほど、優れたクラス分離可能性を意味する。λFに対応する固有ベクトルは密、すなわち計算的に非効率的であり得るが、より高い分類精度を与えることができる。一方で、λFに対応する固有ベクトルはスパース、すなわち計算的に効率的であるが、より低い分類精度を与える。したがって、このアルゴリズムの実施形態は、分類精度と計算効率との間のトレードオフを可能にする。スパーシティは一般により低いrの値についてはより大きく、したがって出願人は、適切なrの値の識別を可能にするためのテスト本明細書に記載を実行した。図11は、顔対非顔のテストデータのための従来のフィッシャーLDA1103b対SMT-LDA1103aの相対的な分類パフォーマンスを示す。ここでも、両方の方法のための誤検出率は99に固定される。水平軸は、判別機能ベクトルのスパーシティまたはを示す。図示のように、SMT実装は、非ゼロコンポーネント1102の各数について、従来のFDAアプローチよりも著しく小さい数の誤検出1101を示している。図12は、具体的にはr=20、40、100、120、200、260、320、350および400が選択されているそれぞれ図1200A~I、提案するスパース行列LDAフレームワークの中で異なるrの値を使用して最適化された判別投影を示す。各判別ベクトルにおける非ゼロコンポーネントの数および対応する判別基準の値を以下の表2の中で示す。SMTモデル次数rの増加に伴い、投影のスパーシティFは減少し、同時にの値は一般に増加し、クラス分離可能性の改善を示す。表2は、顔対非顔の認識データの特定のセットに適用されるSMTモデル次数rの関数として、スパース判別基準の最適値および判別投影のスパーシティを示す。表3は、顔/非顔データセット上の従来のフィッシャーLDA対SMT-LDAの分類パフォーマンスの比較を示す。顔検出率は99で一定に保たれている。一般に、肯定検出率と誤検出の間にはトレードオフが存在する。より高い肯定検出率を作り出すパラメータはまた、より高い誤検出を作り出す傾向があり、逆もまた同じである。最適な顔検出アルゴリズムパラメータは、非顔の領域が顔領域とラベル付されることを防止しながら、所与の画像シーケンスの中で、95以上で顔を見つけ出す。方程式35、すなわちにおいてドット積を計算するために必要な乗算の数は、判別特徴ベクトルまたはにおける非ゼロコンポーネントの数と等しい。これらの実験結果は、提案するスパース行列変換の適用が、分類の精度と分類アルゴリズムの計算複雑性との間のトレードオフを制御するための優れたフレームワークを提供することを示している。本明細書で開示する実施形態に関して説明する方法またはアルゴリズムのステップは、ハードウェア、プロセッサによって実行されるソフトウェアモジュール、またはこの2つの組合せにおいて直接具体化されてもよい。ソフトウェアモジュールは、RAMメモリ、フラッシュメモリ、ROMメモリ、EPROMメモリ、EEPROMメモリ、レジスタ、ハードディスク、リムーバブルディスク、CD-ROM、または当技術分野で知られている任意の他の形態の記憶媒体中に常駐することができる。例示的な記憶媒体は、プロセッサが記憶媒体から情報を読み取り、記憶媒体に情報を書き込むことができるようにプロセッサに結合することができる。代替として、記憶媒体はプロセッサに一体化することができる。プロセッサおよび記憶媒体はASIC中に常駐することができる。ASICは、ユーザ端末内に常駐することができる。代替として、プロセッサおよび記憶媒体は、ユーザ端末内に個別構成要素として常駐することもできる。上述のプロセスのすべては、1つまたは複数の汎用または専用のコンピュータまたはプロセッサによって実行されるソフトウェアコードモジュールにおいて具体化されてもよく、そのソフトウェアコードモジュールを介して完全に自動化されてもよい。コードモジュールは、任意の種類のコンピュータ可読媒体、または他のコンピュータ記憶デバイスもしくは記憶デバイスの集合に記憶することができる。方法の一部または全部は、代替として、専用のコンピュータハードウェアにおいて具体化されてもよい。本明細書で説明する方法およびタスクの全部は、コンピュータシステムによって実行され、完全に自動化されてもよい。コンピュータシステムは、ある場合には、説明した機能を実行するためにネットワーク上で通信し、相互運用する複数の別個のコンピュータまたはコンピューティングデバイスたとえば、物理的サーバ、ワークステーション、ストレージアレイなどを含むことができる。そのようなコンピューティングデバイスの各々は、典型的に、メモリまたは他の非一時的コンピュータ可読記憶媒体に記憶されたプログラム命令またはモジュールを実行するプロセッサまたは複数のプロセッサ、または、たとえばモジュールなどの回路もしくは回路の集合を含む。本明細書で開示する様々な機能は、そのようなプログラム命令において具体化されてもよいが、開示する機能の一部または全部は、代替的に、コンピュータシステムの特定用途向け回路たとえばASICまたはFPGAなどにおいて実装されてもよい。コンピューティングシステムが複数のコンピューティングデバイスを含む場合、これらのデバイスは、必要ではないが、共同設置されてもよい。開示する方法およびタスクの結果は、固体メモリチップおよび/または磁気ディスクなどの物理的記憶デバイスを異なる状態に変換することによって、永続的に記憶することができる。付録Aこの付録は、29の制約付き最適化問題に対する解が31の問題を解くことによって同等に得られるという上記で行った主張を証明するものである。29から、となる。したがって、次のようになる。任意に、ベクトルを選択する場合、またStは正定値であるため、次のようになる:また、Stは正定値であるため、次のようになる:36と38とを結合すると、以下が得られる。したがって、以下が得られる。反対に、以下のために、λ0が0,1の区間で何らかの定数であると仮定する。また、任意ののために、以下が得られる。44と46とを結合する。したがって、以下が得られる。付録Bこの付録では、λ∋0,1での関数frλの上記で行った主張を証明する。この付録では、49だけを証明する。50の証明も同様である。最初に、固定されたrで、閉区間0,1の任意のλのために、以下を仮定する。Stは正定値であるため、したがって次のようになる。以上、次のように結論付ける。ここで、反対にのようなλ∈0,1を選択すると仮定する。であるため、したがって次のようになる。以上、次のように結論付ける。"