(57)【要約】  いくつかの実施形態は、次元削減技法を使用してデータ判別を実行するためのシステムおよび方法に関する。具体的には、所与のデータセットについて、より効率的にフィッシャー判別ベクトルを判定するために、スパース行列変換（ＳＭＴ）を適用する。ＳＭＴの調整は、様々なリソース制約の観点から、フィッシャー判別ベクトルのよりロバストな識別を可能にする。
2014501965.tif 000002
【特許請求の範囲】
【請求項１】
電子デバイス上で実施される、物理的センサデータ分類子を生成するための方法であって、
複数の物理的センサデータを受信することと、
メトリック関数を備える検索アルゴリズムを使用して、前記物理的センサデータに基づいて投影ベクトルを識別することと、ここにおいて、投影ベクトルを識別することが、スパース行列変換を使用して前記メトリック関数に関連した１つまたは複数の固有値を計算することを備え、
前記物理的センサデータの少なくとも一部を前記投影ベクトルに投影することによって、物理的センサデータ分類子を生成することとを備える、方法。
【請求項２】
前記物理的センサデータが顔画像データ、音声オーディオデータ、ワイヤレス通信信号またはレーザーレンジファインダーデータのうちの１つを備える、請求項１に記載の方法。
【請求項３】
前記検索アルゴリズムが反復して計算される、請求項１に記載の方法。
【請求項４】
前記メトリック関数がフィッシャー判別を備える、請求項１に記載の方法。
【請求項５】
前記検索アルゴリズムが二分法検索を備える、請求項１に記載の方法。
【請求項６】
物理的センサデータを備えるデータセットを記憶するように構成されたメモリと、
プロセッサとを備え、前記プロセッサが、
複数の物理的センサデータを受信することと、
メトリック関数を備える検索アルゴリズムを使用して、前記物理的センサデータに基づいて投影ベクトルを識別することと、ここにおいて、投影ベクトルを識別することが、スパース行列変換を使用してメトリック関数に関連した１つまたは複数の固有値を計算することを備え、
前記物理的センサデータの少なくとも一部を前記投影ベクトルに投影することによって、物理的センサデータ分類子を生成することとを行うように構成される、モバイル電子デバイス。
【請求項７】
前記物理的センサデータが顔画像データ、音声オーディオデータ、ワイヤレス通信信号またはレーザーレンジファインダーデータのうちの１つを備える、請求項６に記載のモバイル電子デバイス。
【請求項８】
前記検索アルゴリズムが反復して計算される、請求項６に記載のモバイル電子デバイス。
【請求項９】
前記メトリック関数がフィッシャー判別を備える、請求項６に記載のモバイル電子デバイス。
【請求項１０】
前記検索アルゴリズムが二分法検索を備える、請求項６に記載のモバイル電子デバイス。
【請求項１１】
物理的センサデータを分類するための方法をプロセッサに実施させるように構成された命令を備える非一時的コンピュータ可読媒体であって、前記方法が、
複数の物理的センサデータを受信することと、
メトリック関数を備える検索アルゴリズムを使用して、前記物理的センサデータに基づいて投影ベクトルを識別することと、ここにおいて、投影ベクトルを識別することが、スパース行列変換を使用して前記メトリック関数に関連した１つまたは複数の固有値を計算することを備え、
前記物理的センサデータの少なくとも一部を前記投影ベクトルに投影することによって、物理的センサデータ分類子を生成することとを備える、非一時的コンピュータ可読媒体。
【請求項１２】
前記物理的センサデータが顔画像データ、音声オーディオデータ、ワイヤレス通信信号またはレーザーレンジファインダーデータのうちの１つを備える、請求項１１に記載の非一時的コンピュータ可読媒体。
【請求項１３】
前記検索アルゴリズムが反復して計算される、請求項１１に記載の非一時的コンピュータ可読媒体。
【請求項１４】
前記メトリックがフィッシャー判別を備える、請求項１１に記載の非一時的コンピュータ可読媒体。
【請求項１５】
前記アルゴリズムが二分法検索を備える、請求項１１に記載の非一時的コンピュータ可読媒体。
【請求項１６】
複数の物理的センサデータを受信するための手段と、
メトリック関数を備える検索アルゴリズムを使用して、前記物理的センサデータに基づいて投影ベクトルを識別するための手段と、ここにおいて、投影ベクトルを識別することが、スパース行列変換を使用して前記メトリック関数に関連した１つまたは複数の固有値を計算することを備え、
前記物理的センサデータの少なくとも一部を前記投影ベクトルに投影することによって、物理的センサデータ分類子を生成するための手段とを備える、モバイル電子デバイス。
【請求項１７】
前記受信する手段がプロセッサ実行ソフトウェアを備え、前記識別する手段がプロセッサ実行ソフトウェアを備え、前記生成する手段がプロセッサ実行ソフトウェアを備える、請求項１６に記載のモバイル電子デバイス。
【請求項１８】
前記物理的センサデータが顔画像データ、音声オーディオデータ、ワイヤレス通信信号またはレーザーレンジファインダーデータのうちの１つを備える、請求項１６に記載のモバイル電子デバイス。
【請求項１９】
前記検索アルゴリズムが反復して計算される、請求項１６に記載のモバイル電子デバイス。
【請求項２０】
前記メトリック関数がフィッシャー判別を備える、請求項１６に記載のモバイル電子デバイス。
【請求項２１】
前記検索アルゴリズムが二分法検索を備える、請求項１６に記載のモバイル電子デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、本出願の譲受人に譲渡された、２０１１年１０月１７日に出願した「ＳＹＳＴＥＭＳ  ＡＮＤ  ＭＥＴＨＯＤＳ  ＦＯＲ  ＲＯＢＵＳＴ  ＰＡＴＴＥＲＮ  ＣＬＡＳＳＩＦＩＣＡＴＩＯＮ」と題する米国特許出願第１３／２７５，２４８号、および２０１０年１１月１８日に出願した「ＳＰＡＲＳＥ  ＦＩＳＨＥＲ  ＬＩＮＥＡＲ  ＤＩＳＣＲＩＭＩＮＡＮＴ  ＡＮＡＬＹＳＩＳ」と題する米国仮特許出願第６１／４１５，２２８号の優先権を主張するものである。先願の開示は、本開示の一部と見なされ、参照により本開示に組み込まれる。
【０００２】
本明細書で開示するシステムおよび方法は、一般に、物理的センサデータの複数の異なる形式のためのより効率的なデータ分類に関する。
【背景技術】
【０００３】
現代のコンピュータシステムは、迅速なトレーニング、ならびにデータセットの正確な識別および分類のためのデータ処理技法にますます依存している。これらのデータセットは、スパースであり、過制約（over-constrained）であり得る。たとえば、無線通信受信機は、様々な次元のデータを備えたほんのわずかなメッセージだけを受信する場合がある。システムがほんのわずかしかない、複雑なサンプルに基づいて一般的な特性を推定しなければならないため、そのような状況は「過制約」であると呼ばれる。この困難さにもかかわらず、受信機は本物のメッセージからエラーを正確に区別するために、メッセージパターンを分類しなければならない。
【０００４】
分析およびデータ分類のためにより適用できる形式にデータを再構築するために、様々なツールを使用することができる。フィッシャー線形判別分析（ＬＤＡ：linear discriminant analysis）は、データセット内のデータのクラスを区別するための１つの方法である。従来ＬＤＡは、分類の前に、２つ以上のクラスからの高次元の観測値を低次元の特徴空間に線形的に投影するために、統計およびパターン認識において使用され得る。データをより低次元の特徴空間に投影することによって、分類がより高い次元空間で試みられた場合よりも、簡単に入来データを分類することができる。さらに、より低い次元の特徴空間で動作することによって、本来の空間におけるよりも効率的な分類を可能にすることができる。
【０００５】
フィッシャー法の開発
図１は、２つのデータ分類子１０１ａおよび１０１ｂを示す。これらの分類子内に含まれるデータは、オーディオデータ、ビデオデータ、画像データ、または分類が実行され得る任意のデータセットを備えてもよい。分類子は、システムに入れられた複数の「トレーニング」データポイント、すなわち、すでに与えられている、対応する分類を備えたデータから生成することができる。値が分類子１０１ａ内に含まれる新しいデータポイント、すなわち「テスト」データポイントまたは「ライブ」データポイントは、分類子２０１ａに対応するタイプのデータとして分類される。同様に、値が分類子１０１ｂ内に含まれる新しいデータポイントは、分類子１０１ｂに対応するタイプのデータとして分類される。ここでは、説明を簡単にするために、データは２つの次元１０２ａと１０２ｂだけを備えるが、データは通常、より多くの次元の中で表されてもよいことが容易に認識されよう。
【０００６】
１０２ａ、１０２ｂのデフォルトの座標を参照することによって、新しいデータポイントのセットのための適切な分類を簡単に識別することができるが、通常の場合、これらのデフォルト座標は、必ずしも分類を実行するためのデータを表す最良の座標であるとは限らない。代わりに、別の未識別の座標系が迅速な分類のためにより適用可能であり得る。さらに、いくつかのデフォルトの次元１０２ａ、１０２ｂは他のデフォルトの次元よりも分類のために有用ではない場合があるので（上述のように、画像の１６００ピクセルのすべてが顔の分類のために等しく有用であるとは限らない）、分類を実行する際により少ない次元を使用するのが好ましい場合がある。分類を行うためのより少数の次元を識別することは、「次元削減」と呼ばれることがある。
【０００７】
一旦新しい座標セット（１０３ａ，１０３ｂ）が識別されると、次いで分類子およびこれらの入来データポイントは、データ分類を可能にするためにこれらの新しい座標に投影されてもよい。図１の例では、２つの次元１０２ａと１０２ｂを考えるのではなく、代わりに分類子と新しい入来データをベクトル１０３ｂに投影することができる。次いで、新しいデータポイントのベクトル１０３ｂ上への投影位置に留意することによって、分類を実行することができる。この例では、分類子２０１ａと２０１ｂの分布はそれぞれ、ベクトルφ２０３ｂに沿って投影された場合、平均μ1とμ2とを備える。
【０００８】
ベクトル１０３ｂを識別するための１つの方法は、フィッシャー判別基準によるフィッシャー判別法である。フィッシャー判別基準は、クラス間変動（Ｓb）を、候補ベクトル１０３ｂ上に投影されるものとして、分類子のクラス内変動（Ｓw）に関連付ける。また、総散乱Ｓtは、Ｓw＋Ｓbと呼ぶこともできる。クラス間散乱Ｓbは次のように定義することができる：
【数１】
2014501965.tif 000003
【０００９】
この例では、クラス内散乱は次のように定義することができる。
【数２】
2014501965.tif 000004
【００１０】
また、総散乱は次のように定義することができる。
【数３】
2014501965.tif 000005
【００１１】
直感的に、高いクラス間変動と低いクラス内変動とを備えた投影分類子は、その逆よりもよいデータポイントの分離を可能にする。これは、次のように定義されるフィッシャー基準に反映される。
【数４】
2014501965.tif 000006
【００１２】
高いクラス間変動（Ｓb）と低いクラス内変動（Ｓw）とはより高いフィッシャー基準を有し、よりよい分類を可能にする。この基準は、座標１０２ａ、１０２ｂの空間の中のすべての可能なベクトルの中で、最もよく分類子１０１ａおよび１０１ｂを分離するベクトルφ１０３ｂを識別するために使用することができる。いくつかの方法は、最初にベクトル転置φ0１０３ａを識別するが、全体的な概念は当業者によって認識されるものと同じである。図１の簡略化された例の中では、ベクトルφ２０３ｂが最もよく分類子１０１ａおよび１０１ｂを分類することを容易に判断できるが、複雑な分類子を備えた多次元のシステムの中では、適切なベクトルを判断することは遥かに困難な場合がある。したがって、フィッシャー基準は、分類を改善するための候補ベクトルのメリットを評価するための有益なメトリックを提供する。
【００１３】
ベクトルφ１０３ａは、１０２ａ、１０２ｂの空間の中の可能なベクトルを反復し、分類子のためのフィッシャー基準を最大化するベクトルを発見することによって識別することができる。この「最大ベクトル」
【数５】
2014501965.tif 000007
【００１４】
は次のように表すことができる。
【数６】
2014501965.tif 000008
【００１５】
代替として、同等の基準λFの最大化を計算することによって、
【数７】
2014501965.tif 000009
【００１６】
を判断することができる。
【数８】
2014501965.tif 000010
【００１７】
簡潔のために、総散乱Ｓtが使用されるので、λFの値は０〜１の範囲内に含まれる。λFは、フィッシャー線形判別基準（ＦＬＤＣ：Fisher's Linear Discrimination Criterion）と呼ばれる。
【００１８】
ある定数λのために、ＦＬＤＣを最大化するベクトルφが
【数９】
2014501965.tif 000011
【００１９】
を満たさなければならないということを示すことができる（添付の付録において証明が示されている）。これは、一般化された固有値分解問題である。
【００２０】
ＳbとＳtが両方ともＮ×Ｎの対称行列である場合、（７）を満たす固有値と固有ベクトルのＮ個のペアが存在する：（λ0，φ0），・・・，（λN-1，φN-1）固有値λ0，・・・，λN-1はすべて実数であり、このときＳbおよびＳtは０〜１の範囲に入る散乱行列である。一般性を失わずに、λ0≧・・・≧λN-1と仮定する。Ｓbはランク１の行列であるため、Ｎ個の固有値λfのうちの１つだけが非ゼロであると推測することができる。
【数１０】
2014501965.tif 000012
【００２１】
したがって、フィッシャー線形判別ベクトルは一般化固有ベクトルφ0であり、ＳbおよびＳtの唯一の非ゼロの一般化固有値λ０に対応する：
【数１１】
2014501965.tif 000013
【数１２】
2014501965.tif 000014
【００２２】
以下は、λ0を識別するための１つの提案する方法である。（７）から、固定されたλのために、（Ｓb−λＳt）の典型的な固有値分解を実行すると考える。
【数１３】
2014501965.tif 000015
【００２３】
および
【数１４】
2014501965.tif 000016
【００２４】
として、それぞれ（Ｓb−λＳt）の固有ベクトル行列と固有値行列を示す。固有値分解は、次のように書くことができる。
【数１５】
2014501965.tif 000017
【００２５】
固有値
【数１６】
2014501965.tif 000018
【００２６】
は、
【数１７】
2014501965.tif 000019
【００２７】
によって、その固有ベクトル
【数１８】
2014501965.tif 000020
【００２８】
に関連する。一般性を失わずに、
【数１９】
2014501965.tif 000021
【００２９】
と仮定する。
【００３０】
したがって、フィッシャー判別基準の最適値は、（Ｓb−λＳt）を半負定値（semi-negative definite）にする０＜λ＜１の値として計算することができる。上の条件を満たす範囲[０，１]の中にλの唯一の固有の値が存在すことを示すことができる（添付の付録において証明が示されている）。したがって、ｆ（λ）：[０,１]−＞Ｒがλの関数として（Ｓb−λＳt）の最大固有値を表すとすると、すなわち次のようになる。
【数２０】
2014501965.tif 000022
【数２１】
2014501965.tif 000023
【数２２】
2014501965.tif 000024
【００３１】
次いで、フィッシャー基準の最適値である
【数２３】
2014501965.tif 000025
【００３２】
は、次のように計算することができる。
【数２４】
2014501965.tif 000026
【００３３】
フィッシャー判別ベクトル
【数２５】
2014501965.tif 000027
【００３４】
は、以下の式によって与えられ得る。
【数２６】
2014501965.tif 000028
【００３５】
関数ｆ（λ）：は[０，１]で有界であり、閉区間上で次の特性を満たす。
【数２７】
2014501965.tif 000029
【数２８】
2014501965.tif 000030
【数２９】
2014501965.tif 000031
【００３６】
フィッシャー判別分析の一般化された概要
前述の節および付属の添付書類は、いくつかの実施形態の中で使用されるフィッシャー判別分析法の完全な処理を示すことを意図しているが、図２は、理解を容易にするために、この推論のより一般化された概要を示す。特に、図２は、関数ｆ（λ）を作り出す分析、および以下でより詳細に論じるいくつかの実施形態によって改善される対応する検索アルゴリズムを要約する。
【００３７】
上記で説明したように、適切な投影ベクトル
【数３０】
2014501965.tif 000032
【００３８】
を判定するために、フィッシャー基準を使用しようとすることを認識する（２０２）ことによって、分析が開始する（２０１）。
【数３１】
2014501965.tif 000033
【００３９】
を判定するには、
【数３２】
2014501965.tif 000034
【００４０】
の最大引数を見つけ出す必要がある。
【００４１】
これは、固有値分解問題２０３として書き直すことができる。付録Ｂの中で示される証明によって、フィッシャー判別基準の最適値が（Ｓb−λＳt）を半負定値にする０と１の間の値を見つけ出すことによって計算できることを示すことができる。偶然に、（Ｓb−λＳt）を半負定値にする範囲の中には、唯一の値が存在する。これらの条件から、関数３０４を定義することができる。
【数３３】
2014501965.tif 000035
【数３４】
2014501965.tif 000036
【００４２】
この関数は、様々な特性２０５を有する。これらの特性を考慮して、０のｆ（λ）を作り出す値λを識別するまで、λの可能な値を反復し、それらを方程式２０４に代入することによって、λ*を見つけ出すことができることを認識する。このλはλ*となり、これを、元来求めていた投影ベクトル
【数３５】
2014501965.tif 000037
【００４３】
を判定するために、方程式（２１）とともに使用することができる。
【００４４】
以下の節では、方程式ｆ（λ）２０４からλ*を見つけ出すための１つの可能なアルゴリズムについて論じる。
【００４５】
関数ｆ（λ）を使用したλ*を求めるアルゴリズム検索
図２の条件２０５を参照すると、λ*であるλは二分法検索アルゴリズムによって見つけ出すことができる。すなわち、λがあまりにも低い場合（条件＃１）、ｆ（λ）は高すぎることになる。したがって、より大きなλの値を選択しなければならない。しかしながら、大きすぎるλの値が選択される場合、ｆ（λ）は負となる（条件＃２）。十分に低いｆ（λ）の値が達成されるまで、順により粒度の細かいデルタを選択することを反復することができる。このようにすると、必要に応じてλをλ*に近づけることができる。
【００４６】
図３は、（Ｓb−λＳt）の最大固有値をλの関数として表す関数ｆ（λ）のプロットである。図示のように、この関数は０から１までの範囲に沿ってλ３０１の値をとる。この特定の例では、この関数は０．３５の値で０を通過する。上述のように、このゼロ値を作り出すλは、求めているλ*３０５である。したがって、この例においては、λ*は０．３５である。関数ｆの形状は知られているのでｆ（λ）をゼロに設定する値を反復して検索することが可能である。たとえば、方程式２０４を解くことによって、０．５で開始してｆ（λ）の値を計算することができる。（この例での０．５の場合のように）ｆ（λ）３０２がゼロ未満である場合、たとえば０．２５など、前に選択した値よりも小さな値を選択することができる。λ＝０．２５でｆ（λ）を計算すると正のｆ（λ）３０２が生じるので、最初に選択した値０．５の前に、前の値０．２５の右側の値を選択することができる。したがってλ＝０．３７５を選択することができ、それによってわずかに負のｆ（λ）が生じる。このプロセスは無限に、または所望のレベルの精度に達するまで続いてもよい。
【００４７】
図４は、このプロセス、すなわち二分法を使用して（Ｓb−λＳt）の最大固有値を反復的に分割してゼロにすることの一般化されたアルゴリズムである。ライン４０１は、それぞれ考慮されるべきλの範囲の最小値と最大値を表す変数ａとｂを初期化する。所望の回数Ｋの反復４０２にわたって、システムはλ*の検索を反復する。候補のλは、値４０３を平均化することによって判断される。対応する固有値４０４がわかる。次いでシステムはｆ（λ）４０５を計算することができる。上述のように、この計算を実行するためにかなりの計算リソースを必要とし得る。反復してｆ（λ）を計算することは、いくつかのシステムに対してあまりにも大きな負担を課す場合がある。ｆ（λ）がゼロよりも大きい場合（４０６）、システムは、反復を続ける前に、選択されたλを考慮すべき範囲の中の最小値として割り当てる（４０７）。ｆ（λ）が負である場合（４０８）、代わりに、候補の値を考慮されるべき範囲の中の最大値として割り当てること（４０９）によって、範囲は更新される。Ｋ回の反復に達する場合、システムは出力のために第Ｋの固有値および固有ベクトルを割り当てる（４１２）。当技術分野には、この例に対する多くの変更形態が存在することが容易に認識されよう。
【００４８】
フィッシャー判別の実施形態に関係する図４の二分法検索などの検索アルゴリズムは、多くの分類問題に共通している。これらの問題の多くでは、ｆ（λ）などのメトリック関数は反復して計算されなければならない。このメトリック関数は、迅速に計算されなければならない固有ベクトルと固有値とを備える場合があり、それ以外の場合、反復は完了するのにあまりにも長い時間がかかる。
【００４９】
残念ながら、線形特徴抽出の計算の複雑さは観測サンプルの次元数とともに線形的に増加し、操作がリアルタイムで実行されるべき場合には特に、高次元データに対しての計算が難しくなる可能性がある。モバイルデバイスおよびポータブルコンピュータが一層普及するにつれて、より効率的でロバストな分類システムに対する必要性が高まっている。特に、上記で説明したλ*のための検索アルゴリズムの一部としてメトリックｆ（λ）を計算することは計算集約的であり、より効率的なトレーニングに対する障壁を表している。
【発明の概要】
【００５０】
いくつかの実施形態は、電子デバイス上で実施される、物理的センサデータ分類子を生成するための方法であって、複数の物理的センサデータを受信することと、メトリック関数を備える検索アルゴリズムを使用して、前記物理的センサデータに基づいて投影ベクトルを識別することであって、スパース行列変換を使用して前記メトリック関数に関連した１つまたは複数の固有値を計算することを備える、識別することと、物理的センサデータの少なくとも一部を投影ベクトルに投影することによって、物理的センサデータ分類子を生成することとを備える方法を企図する。
【００５１】
いくつかの実施形態では、物理的センサデータは顔画像データ、音声オーディオデータ、ワイヤレス通信信号またはレーザーレンジファインダーデータのうちの１つを備える。いくつかの実施形態では、検索アルゴリズムは反復して計算される。いくつかの実施形態では、メトリック関数はフィッシャー判別を備える。いくつかの実施形態では、検索アルゴリズムは全単射検索を備える。
【００５２】
いくつかの実施形態は、物理的センサデータを備えるデータセットを記憶するように構成されたメモリと、プロセッサとを備えるモバイル電子デバイスであって、プロセッサが、複数の物理的センサデータを受信することと、メトリック関数を備える検索アルゴリズムを使用して、物理的センサデータに基づいて投影ベクトルを識別することであって、スパース行列変換を使用してメトリック関数に関連した１つまたは複数の固有値を計算することを備える、識別することと、物理的センサデータの少なくとも一部を投影ベクトルに投影することによって、物理的センサデータ分類子を生成することとを行うように構成された、モバイル電子デバイスを企図する。
【００５３】
いくつかの実施形態では、物理的センサデータは顔画像データ、音声オーディオデータ、ワイヤレス通信信号またはレーザーレンジファインダーデータのうちの１つを備える。いくつかの実施形態では、検索アルゴリズムは反復して計算される。いくつかの実施形態では、メトリック関数はフィッシャー判別を備える。いくつかの実施形態では、検索アルゴリズムは全単射検索を備える。
【００５４】
いくつかの実施形態は、物理的センサデータを分類するための方法をプロセッサに実施させるように構成された命令を備える非一時的コンピュータ可読媒体であって、その方法が、複数の物理的センサデータを受信することと、メトリック関数を備える検索アルゴリズムを使用して、物理的センサデータに基づいて投影ベクトルを識別することであって、スパース行列変換を使用してメトリック関数に関連した１つまたは複数の固有値を計算することを備える、識別することと、物理的センサデータの少なくとも一部を投影ベクトルに投影することによって、物理的センサデータ分類子を生成することとを備える、非一時的コンピュータ可読媒体を企図する。
【００５５】
いくつかの実施形態では、物理的センサデータは顔画像データ、音声オーディオデータ、ワイヤレス通信信号またはレーザーレンジファインダーデータのうちの１つを備える。いくつかの実施形態では、検索アルゴリズムは反復して計算される。いくつかの実施形態では、メトリックはフィッシャー判別を備える。いくつかの実施形態では、検索アルゴリズムは全単射検索を備える。
【００５６】
いくつかの実施形態は、複数の物理的センサデータを受信するための手段と、メトリック関数を備える検索アルゴリズムを使用して、物理的センサデータに基づいて投影ベクトルを識別するための手段であって、投影ベクトルを識別することが、スパース行列変換を使用してメトリック関数に関連した１つまたは複数の固有値を計算することを備える、手段と、物理的センサデータの少なくとも一部を投影ベクトルに投影することによって、物理的センサデータ分類子を生成するための手段とを備えるモバイル電子デバイスを企図する。
【００５７】
いくつかの実施形態では、受信手段はプロセッサ実行ソフトウェアを備え、識別手段はプロセッサ実行ソフトウェアを備え、生成手段はプロセッサ実行ソフトウェアを備える。いくつかの実施形態では、物理的センサデータは顔画像データ、音声オーディオデータ、ワイヤレス通信信号またはレーザーレンジファインダーデータのうちの１つを備える。いくつかの実施形態では、検索アルゴリズムは反復して計算される。いくつかの実施形態では、メトリック関数はフィッシャー判別を備える。いくつかの実施形態では、検索アルゴリズムは全単射検索を備える。
【図面の簡単な説明】
【００５８】
【図１】従来技術による、分類子間のフィッシャー判別基準を最大化するベクトルへの２つのデータ分類子の投影を示す図。
【図２】フィッシャー判別基準を最大化するベクトルを識別するために遂行される分析を示す従来技術の一般化された論理フロー図。
【図３】（Ｓb−λＳt）の最大固有値をλの関数として表す関数ｆ（λ）の従来技術のプロット。
【図４】二分法によって（Ｓb−λＳt）の最大固有値をゼロへと反復的に分割するための１つの可能な従来技術の一般化されたアルゴリズム。
【図５】ＳＭＴ変換を適用して対称行列の固有値および固有ベクトルを推定するための１つの可能なアルゴリズムを示す従来技術の一般化された図。
【図６】従来技術の対称ギブンス回転行列の図。
【図７】モバイルデバイスが複数の顔の中から１つまたは複数の顔を認識するようにトレーニングされる、いくつかの実施形態を実装するモバイルデバイスの図。
【図８】いくつかの実施形態で企図されるスパースマトリックス変換（ＳＭＴ：Sparse Matrix Transform）法を組み込んだ二分法によって（Ｓb−λＳt）の最大固有値をゼロへと反復的に分割するための一般化されたアルゴリズム。
【図９Ａ】最適なフィッシャー線形判別ための顔対非顔の分類および対応する線形判別の結果を示す図。
【図９Ｂ】しきい値処理されたフィッシャー判別のための顔対非顔の分類および対応する線形判別の結果を示す図。
【図９Ｃ】ＳＭＴ最適化フィッシャー判別のための顔対非顔の分類および対応する線形判別の結果を示す図。
【図１０】図５のアルゴリズムを使用した顔対非顔の分類問題のため、およびｒが２６０で固定されている図８のアルゴリズムのためのλ(k)対ｋの反復、および｜ｆr（λ(k)）｜対ｋの反復のプロット。
【図１１】顔データと非顔データ（すなわち、人間の顔を含む画像と人間の顔を含まない画像）の間で区別するための従来のフィッシャーＬＤＡ対ＳＭＴ−ＬＤＡのパフォーマンスの比較プロット。
【図１２】それぞれｒ＝２０、４０、１００、１２０、２００、２６０、３２０、３５０および４００のために取得されたスパースフィッシャー判別投影のプロット。
【図１３】特定の実施形態を使用した分類の精度対スパース性のプロット。
【発明を実施するための形態】
【００５９】
一実施形態は、電子デバイスにおけるセンサによって受信されたデータを分類するためのシステムおよび方法である。この実施形態では、電子デバイスは、センサデータをキャプチャし、適切な分類子を生成し、データを１つまたは複数の分類に分類する迅速なデータ分類プロセスを含む。たとえば、センサは画像センサであってもよく、したがって迅速な分類プロセスは、センサによってキャプチャされた画像を分類するように構成されてもよい。１つの特定の実施形態では、キャプチャされた画像は１つまたは複数の顔を含んでもよく、迅速な分類プロセスは、顔を含むキャプチャされた画像の一部を識別するために使用されてもよい。関係する実施形態では、キャプチャされた画像は１つまたは複数の顔を含んでもよく、迅速な分類プロセスは、データストレージから同じ人の他の画像を取り出すために、画像センサによってキャプチャされた顔を、他のあらかじめ記憶された画像に対して照合するために使用されてもよい。顔だけでなく、いかなる物体にも、この実施形態の分類方法を用いてもよいことが容易に認識されよう。
【００６０】
これらの実施形態のいくつかで、迅速な分類システムおよびシステムは、本明細書では「スパース行列ＬＤＡ」と呼ぶＬＤＡの変更バージョンを使用することができ、スパース行列変換は、従来のＬＤＡプロセスのために上記で説明したより典型的な行列変換に置き換わる。この実施形態ではＬＤＡは最適化されているが、最適化は同様に、以下でより詳細に説明する他の分類子の検索アルゴリズムに適用することができる。この実施形態では、スパースＬＤＡの中の判別ベクトルは、制約付き最適化問題に対する解として計算することができる。この実施形態は、この制約付き最適化問題に関連するメトリック関数の計算を最適化することを企図する。特に、メトリック関数は、スパース行列変換（ＳＭＴ：Sparse Matrix Transform）を用いて変更されてもよい。ＳＭＴは、固有値および固有ベクトルの計算など、メトリック関数の副計算を実行するために使用されてもよい。ＳＭＴは、この計算の精度を制御するために、複数の制約を与える。特に、これらの制約は、最適化された判別ベクトルの中で非ゼロのエントリの数を制御するために、緩和されたり、またはより厳しくされたりすることができる。最適化された判別ベクトルの中で非ゼロエントリが多くなると、次元数および計算複雑性はより高くなり、一方で非ゼロエントリが少なくなると、分析されるべきデータの中で次元数および複雑性はより低くなる。制約を緩和したり、より厳しくしたりすることを可能にすることによって、所望の計算精度のレベルを達成することができる。本出願全体を通して、ＳＭＴをメトリック関数の一部として組み込むＬＤＡのことを、スパース行列ＬＤＡと呼ぶ。典型的なフィッシャーＬＤＡは、最適化問題における制約が完全に緩和された場合、提案するスパース行列ＬＤＡフレームワークの特殊なケースとなる。
【００６１】
制約を厳しくすることはスパースな特徴につながり、分類の精度を低くする可能性があるが、計算的には遥かに効率が高くなる。スパース行列特徴の計算のために最適化されたメトリックは、典型的なフィッシャーＬＤＡにおいて使用されたものと同じである。しかしながら、検索空間は、異なるクラスからデータを判別するために、ＲＮにおいてスパースである潜在的に有益なベクトルのセットだけを含むように制約される。したがって、スパース行列ＬＤＡは、顔認識などのターゲットの目的のために最も有益なベクトルに焦点を当て、一方で、最終的な分類の精度を高めるために大いに役立つベクトルを無視している。
【００６２】
一実施形態では、候補のスパース判別方向のプールを生成するために、スパース行列変換は、高次元信号の共分散推定値の正則化のために使用されてもよい。ＳＭＴモデルは、ギブンス回転として知られる一連の対の座標回転の積として直交変換を推定する。固有分解のスパーシティは、ＳＭＴモデルにおけるギブンス回転の数を制限または増加することによって制御することができる。実験結果によって、提案するアルゴリズムを使用して検索されるスパース判別方向は、２つのクラスのデータセットにおいて、所望の数の非ゼロ要素だけを保持するようにハードしきい値処理された典型的なフィッシャー判別方向よりも優れた判別能力を示すということが明らかである。したがって、新しい判別分析のフレームワークは、分類の精度と計算複雑性との間の有利な妥協点を提供する。
【００６３】
これらの実施形態のうちのいくつかは、詳細にはＬＤＡを用いて実施される顔認識を特に参照しながら論じられているが、これらの実施形態の中で開示される改善されたスパース行列方法は、様々なリソース制約（時間、計算能力など）の下で、連続した固有値または固有ベクトルの計算を必要とするメトリック関数を備える任意の検索アルゴリズムに適用することができる。たとえば、開示する実施形態は、主成分分析（ＰＣＡ：Principal Component Analysis）およびフーリエ変換の組成変更など、他の検索メトリック関数計算の固有値に容易に適合させることができる。
【００６４】
従来、スパース行列変換（ＳＭＴ）は、典型的な固有値問題（またはＰＣＡ）に対するスパース正則化された解を見つけ出すという意図とともに使用される。そのような問題は、ＳＭＴが単一の行列に適用され得るという期待とともにアプローチされる。代わりに、出願人は、ＳＭＴフレームワークが、１つではなく２つの対称行列を備える一般化された固有値問題に対するスパース正則化された解を見つけ出すために拡張され得るということを認識した（たとえば、図２の２０４、ならびに図８の８０４および８０５の行列ＳbおよびＳtを参照されたい）。出願人は、さらに、この拡張が、より迅速にデータを分類するためにデータセット分類の状況でさらに適用され得るということを認識した。従来のＳＭＴシステムアプローチは、個々にＳbとＳtのうちの１つに回転を適用するので、この問題には適さない。代わりに、出願人は、２つの行列（Ｓb−λＳt）の線形結合に反復してＳＭＴを適用するための方法を判断した。以下で説明するように、出願人の反復方法によって、主要な固有値および固有ベクトルを判断するために、行列Ｓb、Ｓtに個別にＳＭＴを適用する必要がなくなる。提案する最適化を使用して生成されるスパース固有ベクトルは、以下でさらに説明するように、データ分類アルゴリズムにおける高速次元削減のために、または高次元線形回帰問題における変数の収縮／選択のために使用することができる。出願人の方法は、回帰問題などの様々なアルゴリズムを解くために使用することができる。たとえば、ＬＤＡを参照すると、固有値のスパース行列計算は、工場トレーニングセットを使用して投影ベクトルを判断するために、以下で説明する方法を使用して実行することができる。工場トレーニングセットは、エンドユーザによるフィールドでの使用を見越して生成することができる。本実施形態は、工場トレーニングセットに基づいて、以前に可能であったよりも速い、および／またはより正確なデバイスのトレーニングを可能にする。これらの方法はまた、フィールドで動作するモバイルデバイスのためのさらに速いその場での分類、トレーニングおよび再トレーニングを可能にする。
【００６５】
本実施形態によって改善された、いくつかの検索アルゴリズムは、ＬＤＡなど、分類子を投影する投影ベクトルを求めることができ、一方で他のものは、線形プログラミングを使用することなど、他の知られている方法を通じてパラメータを最適化しようとすることができる。概して、固有値と固有ベクトルのセットの計算を多数必要とする任意の分類アルゴリズムは、以下で説明する改善点を用いることができる。
【００６６】
本開示では、物理的センサデータは広義の用語であって、当業者にその通常および慣習的な意味を与えられるべきであり（すなわち、特殊な、またはカスタマイズされた意味に限定されるものではない）、限定されないが、顔画像データ、音声オーディオデータ、ワイヤレス通信信号、レーザーレンジファインダーデータ、またはカメラ、マイク、圧力センサなどから派生した任意のデータセットを含む。同様に、本開示では、投影ベクトルは広義の用語であって、当業者にその通常および慣習的な意味を与えられるべきであり（すなわち、特殊な、またはカスタマイズされた意味に限定されるものではない）、限定されないが、データが投影される、すなわちデータが以前に示された次元と異なる次元のセットで記述されるように変換されるコンピュータシステム内の任意のデータ構造を含む。本開示では、検索アルゴリズムは広義の用語であって、当業者にその通常および慣習的な意味を与えられるべきであり（すなわち、特殊な、またはカスタマイズされた意味に限定されるものではない）、限定されないが、関係するベクトルまたは値を識別するために使用される任意のアルゴリズムを含む。たとえば、図４に示すアルゴリズムは、所望の程度の精度まで最適値λ*に近づく値λを識別しようとする検索アルゴリズムを備える。本開示では、メトリック関数は広義の用語であって、当業者にその通常および慣習的な意味を与えられるべきであり（すなわち、特殊な、またはカスタマイズされた意味に限定されるものではない）、限定されないが、それによって所望の精度または完成のレベルが評価される計算プログラム内の任意の関数を含む。たとえば、図３に示すλの関数として（Ｓb−λＳt）の最大固有値を表す関数ｆ（λ）は、メトリック関数を備える。メトリック関数はそれ自体複数のコンポーネントメトリックを備えてもよく、「メトリック関数」という用語は、所望の精度または完成のレベルが達成される程度を評価するために使用される範囲で、これらのコンポーネントメトリックのうちの任意のものに等しく適用できるということが容易に認識されよう。本開示では、スパース行列変換は広義の用語であって、当業者にその通常および慣習的な意味を与えられるべきであり（すなわち、特殊な、またはカスタマイズされた意味に限定されるものではない）、限定されないが、図５に示す動作を含む。しかしながら、図５は任意の境界線に沿ってＳＭＴの動作を中断させており、ＳＭＴの副動作の任意の表現を描いていることが容易に認識されよう。たとえば、ｆｏｒループ５０２はｗｈｉｌｅループと置き換えられてもよく、個々の動作は、同じ側の動作効果を達成しながら、並べ替えられ、再特徴付けされてもよいことが、当業者には容易に認識されよう。したがって、本開示でのＳＭＴへの参照は、図５に示すアルゴリズムと同じ動作効果を達成する任意のアルゴリズムに関する。本開示では、分類子は広義の用語であって、当業者にその通常および慣習的な意味を与えられるべきであり（すなわち、特殊な、またはカスタマイズされた意味に限定されるものではない）、限定されないが、注釈付きのデータのセットから派生した分類子１０１ａおよび１０１ｂなどの境界または領域を含む。分類子とは生の��ンポートされた注釈付きデータのことを指してもよいが、また、分類子１０１ａおよび１０１ｂが投影ベクトル１０３ｂに投影される場合など、異なる表現のデータのことを指してもよい。
【００６７】
図７は、開示される実施形態のうちのいくつかを実装するモバイルデバイス７００を示す。モバイルデバイスは、デバイス上で操作されるデータの中のパターンを認識するように構成された複数のソフトウェアおよびハードウェアを備えてもよい。たとえば、デバイスはカメラ７０３を備えてもよく、モバイルデバイスは様々な分類技法を使用して、複数の顔から１つまたは複数の顔７０４を認識するようにトレーニングされてもよい。ユーザがトレーニング画像のコーパスに新しいデータを組み込むと、システムは、同じ顔の特徴を様々な採光条件および環境の下でより容易に認識できるように、システム自体を再トレーニングすることができる。明快のために、本開示ではカメラシステムを、特に顔の分類に関して説明しているが、データ分類技法を実装する多数の他のデバイスコンポーネントが容易に認識されよう。たとえば、モバイルデバイス７００上に位置するワイヤレス受信システム、音声認識システムおよびオーディオ送信システムもまた、ワイヤレス送信信号、音声入力および諧調パターンをそれぞれ分類するために、データ分類技法を各々用いることができる。
【００６８】
これらのシステムの各々は、それらの入力を多数の次元を備えるデータセットとして取得することができる。たとえば、画像データの１つの解釈によって、画像内の各画像ピクセルは、所定の次元に関連する値に対応するピクセル強度で、データの個別のデータの次元を備えてもよい。この例によって、４０×４０ピクセルの画像では、それに応じて１６００次元となる。
【００６９】
フィッシャー線形判別分析（ＬＤＡ）は、２つ以上のデータのクラス間で適切な分離子を識別するための知られている方法である。次に、この分離子は、新しいデータセットを素早く分類するために使用することができる。画像コンテンツの中など、多くの次元が存在する場合、ＬＤＡは次元削減を可能にするので有用である。すなわち、上記の例における４０×４０ピクセルの画像のうちの１６００ピクセルすべてが、たとえば顔の認識のためにすべて等しく重要である可能性は低い。最初に、分類された画像の「トレーニング」データセットがあるとすれば、顔画像を特徴付けるのに最も適した次元（すなわちピクセル）を識別するために、ＬＤＡを実行することができる。その後、識別される必要のある顔画像から新しいデータセットが与えられる場合、新しいデータのための適切なカテゴリー分類（すなわち、「顔」または「非顔」または特定の個人の顔を含むものなど）を迅速に判断するために、これらの適した次元だけを考慮する必要がある。
【００７０】
スパース行列変換
スパース行列変換（ＳＭＴ）のための疑似コードを図５に示す。いくつかの実施形態は、より効率的な二分検索を可能にするために、ＳＭＴをｆ（λ）の計算に組み込むことを企図する。ＳＭＴアルゴリズムは最初に、Ｓ(0)を行列Ｓの初期値に初期設定する（５０１）。次いで、システムは、ＳＭＴモデル次数ｒまでの値の間を反復する（５０２）。各反復のために、システムは比率のためのａｒｇＭａｘ５０３を識別する。次いでシステムは、５０４のために、Ｓ(m)内の副行列
【数３６】
2014501965.tif 000038
【００７１】
の非対角要素に対する対角要素のアークタンジェント最大比率を判断する。各反復でギブンス回転Ｔ(m)（５０５）が判断され、次の中間スパース行列Ｓ(m+1)を取得するために、保留のスパース行列Ｓに適用される。図６は、対称ギブンス回転行列の図である。一旦反復がＳＭＴモデル次数まで実行されると、その後、固有値Ｅｒはギブンス回転の乗算によって割り当てられてもよい（５０８）。同様に、固有値は対角を取り込むことによって判断することができる（５０９）。図８に関するこれらのステップのより徹底的な説明を以下に示す。
【００７２】
当業者が認識するように、典型的な固有値分解問題はＳＥ＝ＥＤと書くことができ、式中Ｓは実数および対称行列であり、Ｅは固有ベクトルの正規直交行列であり、Ｄは固有値の対角行列である。典型的な固有値問題を解くために、ヤコビ固有値アルゴリズムを使用することができる。ヤコビ固有値アルゴリズムは、一連の正規直交変換を通じて反復してＳを対角行列に変換する（６０６）。
【数３７】
2014501965.tif 000039
【００７３】
Ｓ(0)＝ＳでありＴ(m)：＝Ｔ（ｉm，ｊm，θm）である場合は、４つの要素の中だけにある単一性行列とは異なる対のギブンス回転である：
【数３８】
2014501965.tif 000040
【００７４】
および
【数３９】
2014501965.tif 000041
【００７５】
ヤコビアルゴリズムのｒ回の反復を実行した後で推定される固有ベクトル行列６０８および固有値行列６０９は、次のように書くことができる：
【数４０】
2014501965.tif 000042
【００７６】
式中、ｒ→∞、Ｄr→Ｄである場合、
【数４１】
2014501965.tif 000043
【００７７】
は限界にある。
【００７８】
スパース行列変換（ＳＭＴ）は、早期に終了するヤコビ固有分解であり、すなわちヤコビ固有分解におけるギブンス回転の数は小さく保たれる：ｒ＜＜Ｎ（Ｎ−１）／２。上述のように、変数ｒはしばしばＳＭＴモデル次数と呼ばれる。
【００７９】
固有分解のスパーシティは、ＳＭＴモデル次数ｒを変えることによって、増加または減少させることができる。ＳＭＴの各反復での適切なギブンス回転Ｔ（ｍ）＝Ｔ（ｉm，ｊm，θm）の選択は、スパース固有分解の精度を判断する。最適な座標ペア（ｉm，ｊm）を判断するために、ＳＭＴアルゴリズムは、対角要素に対する非対角要素の最大比率（図６のステップ６０３）のために、Ｓ(m)内の２×２の副行列
【数４２】
2014501965.tif 000044
【００８０】
を検査する（図６のステップ６０３）。
【数４３】
2014501965.tif 000045
【００８１】
次いで、（ｉm，ｊm）および（ｊm，ｉm）での非対角要素がＳ(m+1)でゼロになるように、回転角θmが選択される（図５のステップ５０４）。
【数４４】
2014501965.tif 000046
【００８２】
次数の数ｒに従って、所望の数の反復が実行された後 、次いでスパース固有分解は、（それぞれ図５のステップ５０８およびステップ５０９）によって、（２４）に基づいて判断されてもよい。
【数４５】
2014501965.tif 000047
【００８３】
スパース行列変換を組み込んだフィッシャー判別方法
上述のように、ＳＭＴは、ｒを変えることによって推定される固有ベクトルのスパーシティを増加または減少させることを可能にする。次の節では、図４の二分法検索アルゴリズムへＳＭＴを組み込むことについて詳述する。一般性を失わずに、対応する固有ベクトルによって、
【数４６】
2014501965.tif 000048
【００８４】
を（Ｓb−λＳt）および
【数４７】
2014501965.tif 000049
【００８５】
の最大固有値とする。
【００８６】
集合
【数４８】
2014501965.tif 000050
【００８７】
が、固定のｒのため、および［０，１］の範囲のλのために、すべてのＳＭＴ推定固有ベクトルの集合
【数４９】
2014501965.tif 000051
【００８８】
を示すものとする。以下の制約付き最適化問題に対する解として、スパースフィッシャー線形判別ベクトル
【数５０】
2014501965.tif 000052
【００８９】
を計算することを提案する：
【数５１】
2014501965.tif 000053
【００９０】
典型的に、ＳＭＴモデル次数ｒのより小さな値は、判別ベクトルのよりスパースな推定値をもたらし、その逆も同様である。ｒが大きい場合、集合
【数５２】
2014501965.tif 000054
【００９１】
に対するスパーシティ制約は緩和され、スパースフィッシャーＬＤＡは典型的なフィッシャーＬＤＡに縮小する。
【００９２】
（２９）に従って、最適なスパース判別投影
【数５３】
2014501965.tif 000055
【００９３】
は、範囲[０，１]のλのために、（Ｓb−λＳt）の固有ベクトル
【数５４】
2014501965.tif 000056
【００９４】
として計算される。上記の説明と類似した方法で、判別基準を最大化するλの値
【数５５】
2014501965.tif 000057
【００９５】
はまた、固有値
【数５６】
2014501965.tif 000058
【００９６】
がゼロに等しくなる値でもあるということを示すことができる（付録Ａを参照されたい）。
【００９７】
このように、ｆr（λ）：[０，１]→Ｒが（Ｓb−λＳt）の最大固有ベクトルを表すものとすると、λの関数として、次数ｒのＳＭＴモデルを使用して以下が推定される。すなわち、
【数５７】
2014501965.tif 000059
【００９８】
（２１）の制約付き最適化問題は、同等に次のように解くことができる：
【数５８】
2014501965.tif 000060
【００９９】
ｒ→∞、ｆr（λ）→ｆ（λ）、したがって
【数５９】
2014501965.tif 000061
【０１００】
である場合、限度にある。
【０１０１】
いくつかの実施形態では、関数ｆr（λ）は、検索アルゴリズムＬＤＡのための「メトリック関数」と呼ぶことができる。この場合も、上記で説明したものと類似の方法で、関数ｆr（λ）：は[０，１]で有界であり、閉区間上で次の特性を満たす（付録Ｂを参照されたい）：
【数６０】
2014501965.tif 000062
【数６１】
2014501965.tif 000063
【数６２】
2014501965.tif 000064
【０１０２】
したがって、非線形方程式ｆr（λ）＝０の解は、先に説明したように、二分法を使用することによって計算することができる。二分法に基づいて
【数６３】
2014501965.tif 000065
【０１０３】
および
【数６４】
2014501965.tif 000066
【０１０４】
を推定するための反復方式は、図８のアルゴリズムの中に示す。
【０１０５】
図８は、ＳＭＴ変換方法を組み込んだ細分によって、反復して（Ｓb−λＳt）の最大固有値をゼロにするための一般化されたアルゴリズムである。このアルゴリズムを、ＬＤＡのための「検索アルゴリズム」、および「メトリック」としての関数ｆ（λ）と呼ぶことができる。たとえば、ＰＣＡを用いる別の分類問題は、多数の「メトリック」の反復を使用して固有値を識別した「検索アルゴリズム」ＰＣＡを同様に備える。両方の場合、および同様の場合、固有値の計算を最適化するためにＳＭＴを使用することができる。図８のステップ８０１〜８０３、８０６〜８１２は、図４のステップ４０１〜４０３、４０６〜４１２に対応する。しかしながら、８０４および８０５のために必要なｆ（λ）の計算は、ここではスパース行列変換の使用とともに最適化される。
【０１０６】
したがって、アルゴリズムは、非線形方程式ｆr（λ）＝０のルートとして、スパースフィッシャー判別基準の最適値
【数６５】
2014501965.tif 000067
【０１０７】
を推定する。このルートは閉区間[ａ，ｂ]の中間点と推定され、ここでａとｂの初期値はそれぞれ０と１であり、次いでａとｂの間のギャップが２-Kに減少するまで反復して更新される。次いで
【数６６】
2014501965.tif 000068
【０１０８】
および
【数６７】
2014501965.tif 000069
【０１０９】
の最終値が
【数６８】
2014501965.tif 000070
【０１１０】
および
【数６９】
2014501965.tif 000071
【０１１１】
として計算され、式中λ(k)はｋ番目の反復におけるａとｂの間の中間点を示し、Ｋは、ルート発見アルゴリズムが実行される反復の総数を示す。λ(k)が更新されるたびに、ｆr（λ(K)）＝０は、λ(k)の新しい値のために（Ｓb−λ(k)Ｓt）のＳＭＴ分解を実行することによって計算される。ここでも、この特定の二分法アルゴリズムを例示のために示しているが、この特定の例に対する多数の変形形態が容易に認識されよう。たとえば、パラメータａおよびｂは、より洗練された中間検索変数と置き換えられてもよく、実行される反復は、単なるＫではない追加の要因に基づいて判断されてもよい。同様に、次数ｒは反復ごとに異なってもよく、たとえばユーザがモバイルデバイス上で顔認識トレーニングを試みている状態など、アルゴリズムが実行される領域に関係する複数の不特定のパラメータによって決まってもよい。
【０１１２】
実証となる適用
以下の表および図面は、上記のアルゴリズムのいくつかの実験的実証について様々な結果を示す。これらの例のために、顔と非顔を表す複数の２０×２０のパッチが使用されている（顔を備えるクラスω1と非顔を備えるクラスω2）。簡単のために、クラスω1を「正」のクラスと呼び、ω2を「負」のクラスと呼ぶことができる。２０×２０のパッチは平均値除去（de-meaned）され、分散正規化され、４００次元のベクトルとして構成される。トレーニングのために、ω１からの２０００サンプルとω２からの５１０００サンプルが使用されている。テストのために、ω１から使用されるサンプル数は１４００であり、ω２から使用されるサンプル数は３４０００である。それぞれクラス間散乱行列Ｓbとクラス内散乱行列Ｓtを計算するために、顔からのトレーニングデータベクトルと非顔からのトレーニングベクトルが使用される。最適なフィッシャー判別基準
【数７０】
2014501965.tif 000072
【０１１３】
および判別ベクトル
【数７１】
2014501965.tif 000073
【０１１４】
は、図４のアルゴリズムを使用して計算されている。同様に、
【数７２】
2014501965.tif 000074
【０１１５】
および
【数７３】
2014501965.tif 000075
【０１１６】
は、図８のアルゴリズムを使用して計算されている。これら実験において使用した顔は、正面、直立の顔を備える。すなわち、頭の回転と面外の横向きの回転との両方のための許容可能な範囲は、−１５から１５度程度である。
【０１１７】
図９Ａ〜図９Ｃは、それぞれ最適なフィッシャー線形判別図９Ａ、しきい値処理されたフィッシャー判別図９Ｂ、およびＳＭＴ最適化フィッシャー判別図９Ｃのための顔対非顔の分類９０２ａ-ｃおよび対応する線形判別９０１ａ-ｃの結果を示す。線形判別９０１ａおよび９０１ｂと比較すると、ＳＭＴ最適化判別のための線形判別９０１ｃはより少ない次元を備える。
【０１１８】
図９Ａに関して、９０１ａによって表される最適化判別ベクトル
【数７４】
2014501965.tif 000076
【０１１９】
は、次のルールに従って、上記で説明したクラスｗ1またはクラスｗ2のいずれかからテストベクトルｘを分類するために使用されている。
【数７５】
2014501965.tif 000077
【０１２０】
式中しきい値Ｔは、所望の分類率を与えるように調整される。
【０１２１】
図９Ｂに関して、テストのしきい値処理バージョンが実行されている。Ｎ次元のデータのために、フィッシャー投影の計算は、Ｎの乗算およびＮ−１の加算を必要とする。Ｎが大きい場合、必要とされる計算はかなりの量になる場合があり、分類方式のソフトウェア実施を遅くし、同方式のハードウェア実装を高価なものにする。分類精度と計算との間のトレードオフを制御できるようにする単純な方策は、
【数７６】
2014501965.tif 000078
【０１２２】
の構成要素をハードしきい値処理することであり、しきい値よりも大きい、またはしきい値と等しい振幅を有するものだけを残す。これらのテストの結果は図９Ｂの中で示され、次のルールを使用している：
【数７７】
2014501965.tif 000079
【０１２３】
式中θcはハードしきい値処理関数を示し、定数ｃはしきい値処理された判別ベクトルのスパーシティ
【数７８】
2014501965.tif 000080
【０１２４】
を制御する。
【０１２５】
下位の計算の分類制度をトレードオフするために、図３（ａ）に示すように、１０個だけの非ゼロコンポーネントとともに、ｃの値を選択して、しきい値判別ベクトル
【数７９】
2014501965.tif 000081
【０１２６】
を取得する。ここで、ドット積
【数８０】
2014501965.tif 000082
【０１２７】
の計算は、１０個の乗算と９個の加算だけを必要とする。しかしながら、計算の縮小は、１１０２ｂに示すように、分類パフォーマンスの大幅な劣化という犠牲を払う。９９％の固定の肯定検出率のために、スパース投影ベクトル
【数８１】
2014501965.tif 000083
【０１２８】
との誤検出率は４０．７％まで上昇する。
【０１２９】
顔および非顔の分類は、ルールを使用してテストサンプリングする。図面１１Ａ〜１１Ｃの各々における青い破線は、（３５）におけるＴの値を表す。
【表１】
2014501965.tif 000084
【０１３０】
表１は、しきい値処理された判別のスパーシティの関数
【数８２】
2014501965.tif 000085
【０１３１】
として、分類の精度を示す。肯定検出は９９％で固定されている。
【０１３２】
図９Ｃに関して、テストもまた、上記のフィッシャー判別方法のスパース行列変換実装を使用して実行されている。２つのクラスｗ1、ｗ2からのトレーニングデータのベクトルは、散乱行列ＳbおよびＳtを計算するために使用されている。スパース判別方向
【数８３】
2014501965.tif 000086
【０１３３】
およびスパース判別基準の最適値
【数８４】
2014501965.tif 000087
【０１３４】
は、非線形方程式８０５を解くことによって推定されている。スパースフィッシャー線形判別分析を実行するために、ＳＭＴモデルの中のギブンス回転の数ｒは固定されている。ルート発見二分法が実行される反復の最大数Ｋもまた固定されており、具体的にはＫ＝２０が使用されている。ｒが２６０に固定されている場合の、アルゴリズムの反復数ｋの関数としてのλ(k)および｜ｆr（λ(k)）｜の推定値は、以下に、それぞれ１００２Ｃおよび１００２Ｄのプロットの中で示されている。スパース判別基準の最適値は、
【数８５】
2014501965.tif 000088
【０１３５】
と推定されており、これは、従来のＦＤＡのために推定された典型的なフィッシャー判別基準λ＊F＝０．９０６の最適値よりも小さい。対応するスパース判別ベクトルは、
【数８６】
2014501965.tif 000089
【０１３６】
と判断されている。スパース投影ベクトル
【数８７】
2014501965.tif 000090
【０１３７】
は、２０×２０のマスク９０１ｃとして構成されている。
【０１３８】
投影ベクトルは１１個だけの非ゼロコンポーネントを有するので、
【数８８】
2014501965.tif 000091
【０１３９】
のテストベクトルｘを空間に投影するのに関与する計算は、１１個の乗算と１０個の加算だけである。判別方向として
【数８９】
2014501965.tif 000092
【０１４０】
を用いるデータ分類パフォーマンスを９０２ｃに示す。しきい値Ｔは９９％の肯定検出率を与えるように調整されており、達成された誤検出率は１６．７％であった。比較のために、同様の計算負荷と肯定検出率について、ハードしきい値処理されたフィッシャー特徴
【数９０】
2014501965.tif 000093
【０１４１】
９０２ｂは、４２．０％の誤検出率をもたらす。
【０１４２】
図１０は、ｒが２６０に固定されている、図５のアルゴリズムを使用した、また図８のアルゴリズムのための、顔対非顔の分類問題のためのλ(k)対ｋの反復および｜ｆr（λ(k)）｜対ｋの反復のプロットを示す。特に、プロット１００２ａとプロット１００２ｂとのペア１０００Ａは、それぞれ、図５のアルゴリズムを使用するｋの連続反復のためのλ(k)１００３ａおよび｜ｆr（λ(k)）｜１００３ｂの予想値を示す。同様に、プロット１００２ｃとプロット１００２ｄとのペア１０００Ｂは、それぞれ、図８のアルゴリズムを使用するｋの連続反復のためのλ(k)１００３ｃおよび｜ｆr（λ(k)）｜１００３ｄの予想値を示す。より大きい反復については、図５のアルゴリズムのλの値はλF*のために０．９０６に収束し、一方図８のアルゴリズムのλの値はλF*rのために０．８５に収束する。
【０１４３】
概して、λの値が大きいほど、優れたクラス分離可能性を意味する。λF*に対応する固有ベクトルは密、すなわち計算的に非効率的であり得るが、より高い分類精度を与えることができる。一方で、λF*に対応する固有ベクトルはスパース、すなわち計算的に効率的であるが、より低い分類精度を与える。したがって、このアルゴリズムの実施形態は、分類精度と計算効率との間のトレードオフを可能にする。スパーシティは一般により低いｒの値についてはより大きく、したがって出願人は、適切なｒの値の識別を可能にするためのテスト（本明細書に記載）を実行した。
【０１４４】
図１１は、顔対非顔のテストデータのための従来のフィッシャーＬＤＡ１１０３ｂ対ＳＭＴ−ＬＤＡ１１０３ａの相対的な分類パフォーマンスを示す。ここでも、両方の方法のための誤検出率は９９％に固定される。水平軸は、判別機能ベクトルのスパーシティ
【数９１】
2014501965.tif 000094
【０１４５】
または
【数９２】
2014501965.tif 000095
【０１４６】
を示す。図示のように、ＳＭＴ実装は、非ゼロコンポーネント１１０２の各数について、従来のＦＤＡアプローチよりも著しく小さい数の誤検出１１０１を示している。
【０１４７】
図１２は、具体的にはｒ＝２０、４０、１００、１２０、２００、２６０、３２０、３５０および４００が選択されている（それぞれ図１２００Ａ〜Ｉ）、提案するスパース行列ＬＤＡフレームワークの中で異なるｒの値を使用して最適化された判別投影
【数９３】
2014501965.tif 000096
【０１４８】
を示す。各判別ベクトル
【数９４】
2014501965.tif 000097
【０１４９】
における非ゼロコンポーネントの数および対応する判別基準の値
【数９５】
2014501965.tif 000098
【０１５０】
を以下の表２の中で示す。ＳＭＴモデル次数ｒの増加に伴い、投影のスパーシティＦは減少し、同時に
【数９６】
2014501965.tif 000099
【０１５１】
の値は（一般に）増加し、クラス分離可能性の改善を示す。
【表２】
2014501965.tif 000100
【０１５２】
表２は、顔対非顔の認識データの特定のセットに適用されるＳＭＴモデル次数ｒの関数として、スパース判別基準の最適値
【数９７】
2014501965.tif 000101
【０１５３】
および判別投影のスパーシティ
【数９８】
2014501965.tif 000102
【０１５４】
を示す。
【表３】
2014501965.tif 000103
【０１５５】
表３は、顔／非顔データセット上の従来のフィッシャーＬＤＡ対ＳＭＴ−ＬＤＡの分類パフォーマンスの比較を示す。顔検出率は９９％で一定に保たれている。一般に、肯定検出率と誤検出の間にはトレードオフが存在する。より高い肯定検出率を作り出すパラメータはまた、より高い誤検出を作り出す傾向があり、逆もまた同じである。最適な顔検出アルゴリズムパラメータは、非顔の領域が顔領域とラベル付されることを防止しながら、所与の画像シーケンスの中で、９５％以上で顔を見つけ出す。方程式（３５）、すなわち
【数９９】
2014501965.tif 000104
【０１５６】
においてドット積を計算するために必要な乗算の数は、判別特徴ベクトル
【数１００】
2014501965.tif 000105
【０１５７】
または
【数１０１】
2014501965.tif 000106
【０１５８】
における非ゼロコンポーネントの数と等しい。
【０１５９】
これらの実験結果は、提案するスパース行列変換の適用が、分類の精度と分類アルゴリズムの計算複雑性との間のトレードオフを制御するための優れたフレームワークを提供することを示している。
【０１６０】
本明細書で開示する実施形態に関して説明する方法またはアルゴリズムのステップは、ハードウェア、プロセッサによって実行されるソフトウェアモジュール、またはこの２つの組合せにおいて直接具体化されてもよい。ソフトウェアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、リムーバブルディスク、ＣＤ−ＲＯＭ、または当技術分野で知られている任意の他の形態の記憶媒体中に常駐することができる。例示的な記憶媒体は、プロセッサが記憶媒体から情報を読み取り、記憶媒体に情報を書き込むことができるようにプロセッサに結合することができる。代替として、記憶媒体はプロセッサに一体化することができる。プロセッサおよび記憶媒体はＡＳＩＣ中に常駐することができる。ＡＳＩＣは、ユーザ端末内に常駐することができる。代替として、プロセッサおよび記憶媒体は、ユーザ端末内に個別構成要素として常駐することもできる。
【０１６１】
上述のプロセスのすべては、１つまたは複数の汎用または専用のコンピュータまたはプロセッサによって実行されるソフトウェアコードモジュールにおいて具体化されてもよく、そのソフトウェアコードモジュールを介して完全に自動化されてもよい。コードモジュールは、任意の種類のコンピュータ可読媒体、または他のコンピュータ記憶デバイスもしくは記憶デバイスの集合に記憶することができる。方法の一部または全部は、代替として、専用のコンピュータハードウェアにおいて具体化されてもよい。
【０１６２】
本明細書で説明する方法およびタスクの全部は、コンピュータシステムによって実行され、完全に自動化されてもよい。コンピュータシステムは、ある場合には、説明した機能を実行するためにネットワーク上で通信し、相互運用する複数の別個のコンピュータまたはコンピューティングデバイス（たとえば、物理的サーバ、ワークステーション、ストレージアレイなど）を含むことができる。そのようなコンピューティングデバイスの各々は、典型的に、メモリまたは他の非一時的コンピュータ可読記憶媒体に記憶されたプログラム命令またはモジュールを実行するプロセッサ（または複数のプロセッサ、または、たとえばモジュールなどの回路もしくは回路の集合）を含む。本明細書で開示する様々な機能は、そのようなプログラム命令において具体化されてもよいが、開示する機能の一部または全部は、代替的に、コンピュータシステムの特定用途向け回路（たとえばＡＳＩＣまたはＦＰＧＡなど）において実装されてもよい。コンピューティングシステムが複数のコンピューティングデバイスを含む場合、これらのデバイスは、必要ではないが、共同設置されてもよい。開示する方法およびタスクの結果は、固体メモリチップおよび／または磁気ディスクなどの物理的記憶デバイスを異なる状態に変換することによって、永続的に記憶することができる。
【０１６３】
付録Ａ
この付録は、（２９）の制約付き最適化問題に対する解が（３１）の問題を解くことによって同等に得られるという上記で行った主張を証明するものである。
【０１６４】
（２９）から、
【数１０２】
2014501965.tif 000107
【０１６５】
となる。
【０１６６】
したがって、次のようになる。
【数１０３】
2014501965.tif 000108
【０１６７】
任意に、ベクトル
【数１０４】
2014501965.tif 000109
【０１６８】
を選択する場合、またＳtは正定値であるため、次のようになる：
【数１０５】
2014501965.tif 000110
【０１６９】
また、Ｓtは正定値であるため、次のようになる：
【数１０６】
2014501965.tif 000111
【０１７０】
（３６）と（３８）とを結合すると、以下が得られる。
【数１０７】
2014501965.tif 000112
【０１７１】
したがって、以下が得られる。
【数１０８】
2014501965.tif 000113
【０１７２】
反対に、以下のために、λ0が[０，１]の区間で何らかの定数であると仮定する。
【数１０９】
2014501965.tif 000114
【数１１０】
2014501965.tif 000115
【数１１１】
2014501965.tif 000116
【数１１２】
2014501965.tif 000117
【０１７３】
また、任意の
【数１１３】
2014501965.tif 000118
【０１７４】
のために、以下が得られる。
【数１１４】
2014501965.tif 000119
【数１１５】
2014501965.tif 000120
【０１７５】
（４４）と（４６）とを結合する。
【数１１６】
2014501965.tif 000121
【０１７６】
したがって、以下が得られる。
【数１１７】
2014501965.tif 000122
【０１７７】
付録Ｂ
この付録では、λ∋[０，１]での関数ｆr（λ）の上記で行った主張を証明する。
【数１１８】
2014501965.tif 000123
【数１１９】
2014501965.tif 000124
【０１７８】
この付録では、（４９）だけを証明する。（５０）の証明も同様である。最初に、固定されたｒで、閉区間[０，１]の任意のλのために、以下を仮定する。
【数１２０】
2014501965.tif 000125
【数１２１】
2014501965.tif 000126
【０１７９】
Ｓtは正定値であるため、したがって次のようになる。
【数１２２】
2014501965.tif 000127
【０１８０】
以上、次のように結論付ける。
【数１２３】
2014501965.tif 000128
【０１８１】
ここで、反対に
【数１２４】
2014501965.tif 000129
【０１８２】
のようなλ∈[０，１]を選択すると仮定する。
【数１２５】
2014501965.tif 000130
【数１２６】
2014501965.tif 000131
【数１２７】
2014501965.tif 000132
【０１８３】
であるため、したがって次のようになる。
【数１２８】
2014501965.tif 000133
【数１２９】
2014501965.tif 000134
【０１８４】
以上、次のように結論付ける。
【数１３０】
2014501965.tif 000135
【図１】
2014501965.tif 000136
【図２】
2014501965.tif 000137
【図３】
2014501965.tif 000138
【図４】
2014501965.tif 000139
【図５】
2014501965.tif 000140
【図６】
2014501965.tif 000141
【図７】
2014501965.tif 000142
【図８】
2014501965.tif 000143
【図９Ａ】
2014501965.tif 000144
【図９Ｂ】
2014501965.tif 000145
【図９Ｃ】
2014501965.tif 000146
【図１０】
2014501965.tif 000147
【図１１】
2014501965.tif 000148
【図１２】
2014501965.tif 000149
【図１３】
2014501965.tif 000150
【国際調査報告】
2014501965.tif 000151
2014501965.tif 000152
2014501965.tif 000153