(57)【要約】      （修正有）【課題】オブジェクトをより低次元のパラメータを用いて表現する。【解決手段】方法は、オブジェクトのクラスを表す。クラスのオブジェクトに対しサンプルの集合が取得され、各オブジェクトに対して１つのサンプルがあり、各サンプルは、オブジェクトの特性を表す複数のデータ値を含む。サンプルは、部分集合にグループ化され、各部分集合は、少なくとも１つの他の部分集合と交わる。各部分集合に対し、低次元パラメータ化が確定される。低次元パラメータ化の零空間が平均化され、オブジェクトのクラスの低次元表現を含む零空間を有する行列を取得する。【選択図】図１
2006079605.tif 000002
【特許請求の範囲】
【請求項１】
オブジェクトのクラスを表す方法であって、
各オブジェクトに対して１つのサンプルがあり、各サンプルは、前記オブジェクトの特性を表す複数のデータ値を含み、前記クラスの前記オブジェクトに対しサンプルの集合を取得することと、
各部分集合は少なくとも１つの他の部分集合と交わるように、前記サンプルを部分集合にグループ化することと、
各部分集合に対し、低次元部分集合パラメータ化を確定することと、
前記オブジェクトのクラスの低次元表現を含む零空間を有する行列を取得するために、前記低次元部分集合パラメータ化の零空間を平均化することと
を含むオブジェクトのクラスを表す方法。
【請求項２】
前記サンプルの集合と、前記オブジェクトのクラスの前記低次元表現を含む前記零空間との相違を確定することにより、前記サンプルの集合におけるノイズを低減することをさらに含む請求項１に記載の方法。
【請求項３】
前記オブジェクトのクラスの前記低次元表現を生成するために、前記行列の列零空間を前記部分集合パラメータ化に写像することをさらに含む請求項１に記載の方法。
【請求項４】
前記クラスにおける前記オブジェクトに対するサンプルの次の集合を取得することと、
前記次のサンプルを次の部分集合にグループ化することと、
各次の部分集合に対し、低次元部分集合パラメータ化を確定することと、
フィルタを取得するために、各次の部分集合と、次の部分集合と交わる各部分集合との前記低次元部分集合パラメータ化の零空間を平均化することと、
前記オブジェクトのクラスの前記表現を更新するために、前記サンプルの集合および前記サンプルの次の集合をフィルタリングすることと
をさらに含む請求項１に記載の方法。
【請求項５】
前記サンプルは、人間の顔の画像である請求項１に記載の方法。
【請求項６】
前記サンプルは、人間の顔のモデルである請求項１に記載の方法。
【請求項７】
前記表現を出力デバイスにおいてレンダリングすることをさらに含む請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはサンプリングされたデータをモデル化することに関し、特に、高次元データを低次元モデルで表現することに関する。
【背景技術】
【０００２】
非線形次元削減（nonlinear dimensionality reduction）（ＮＬＤＲ）は、高次元サンプルデータの低次元表現を生成する。データは、Ｄ＞ｄの場合に、周囲空間ＲＤに埋め込まれるｄ次元多様体Ｍをサンプリングするものと考えられる。目的は、埋込みの外的幾何形状（extrinsic geometry）、すなわち多様体Ｍが周囲空間ＲＤにおいていかに形成されるかを、その内的幾何形状（intrinsic geometry)、すなわち多様体Ｍの固有のｄ次元座標系から分離することである。
【０００３】
たとえば、人間の顔の多様体が顔の画像の空間にいかに埋め込まれているかが分かる場合、内的幾何形状を使用して顔の画像を編集し、比較し、かつ分類することができ、外的幾何形状を活用して画像における顔を検出し新たな顔の画像を合成することができる。
【０００４】
コンピュータビジョンでは、主成分分析（ＰＣＡ）を介して画像をサンプリングするように適合された線形部分空間により多様体を近似することが一般的である。これは、近似であるが、データ内挿、外挿、圧縮、ノイズ除去および視覚化にうまく適用されてきた。
【０００５】
ＮＬＤＲ「部分多様体」方法は、同じ機能を提供することができるが、演算の大部分が多様体Ｍの内的幾何形状または外的幾何形状に対して限定されているため、真のデータ分布に対してより忠実である。
【０００６】
ＰＣＡ方法は、多様体の大域構造、すなわちデータ平均に関する共分散を保存するが、ＮＬＤＲ方法は、多様体における局所構造を保存する。微分幾何形状により、データの無限小近傍における局所計量および近傍の連結性に関する情報が、多様体の内的幾何形状を完全に確定するということが分かる。
【０００７】
これは、データに対して近傍グラフを与え、グラフの部分集合における隣接する点の間の関係を測定することにより、有限データに対し近似される。
【０００８】
従来技術は、データに対して近傍グラフを与えること、および２点間の距離に対しグラフの部分集合の隣接する点の間の関係を測定することについて記載している。たとえば、Tenenbaum他著「A global geometric framework for nonlinear dimensionality reduction」、Science, 290:2319-2323, December 2000、Weinberger他著「Learning a kernel matrix for nonlinear dimensionality reduction」、Proc. 21st ICML, 2004およびBelkin他著「Laplacian eigenmaps for dimensionality reduction and data representation」、Advances in Neural Information Processing Systems, volume 14, 2002を参照願いたい。
【０００９】
グラフの部分集合における隣接する点の間の関係を測定することについては、局所接空間に射影された点の座標に対しても記載されている。Brand著「Charting a manifold」、Advances in Neural Information Processing Systems, volume 15, 2003、Donoho他著「Hessian eigenmaps」、Proceedings, National Academy of Sciences, 2003およびZhang他著「Nonlinear dimension reduction via local tangent space alignment」、Proceedings, Conf. on Intelligent Data Engineering and Automated Learning, number 2690 in Lecture Notes on Computer Science, Springer-Verlag, pages 477-481, 2003を参照願いたい。
【００１０】
グラフの部分集合における隣接する点の間の関係を測定することは、さらに、局所重心座標についても記載されている。Roweis他著「Nonlinear dimensionality reduction by locally linear embedding」、Science, 290:2323-2326, December 2000を参照願いたい。
【００１１】
従来技術における重要な仮定は、周囲空間における点の部分集合の局所線形構造が、多様体Ｍの対応する近傍における計量構造を近似することができる、すなわち、周囲空間ＲＤにおける距離が多様体Ｍ上の測地線の弧長を表すということである。そして、グラフは、すべての局所計量制約の組合せを二次形式に導き、そこでは、固有関数を最大化または最小化することで、目標空間Ｒｄに多様体を埋め込むための最小二乗誤差基底が提供される。
【００１２】
離散データに対し、二次形式は、多様体が線形に埋め込まれる未知の空間における点の間の内積として解釈することができるエントリを有するグラム行列であり、したがって、ＮＬＤＲは、未知のカーネル関数ではあるが、カーネル法である。Ham他著「A kernel view of the dimensionality reduction of manifolds」、Proc. ICML04, 2004を参照願いたい。
【００１３】
信号処理およびデータモデル化に対して特に重要なのは、多様体Ｍにおけるサンプリングされたパッチが、目標空間Ｒｄの連結されたパッチに対して局所的に等長である場合である。それは、無限サンプリングの連続極限において、固有関数を最適化することにより、多様体の局所データ密度および内的幾何形状を完全に再現する平面はめ込みがもたらされるためである。Donoho他著「Hessian eigenmaps」、Proceedings, National Academy of Sciences, 2003を参照願いたい。このため、ほとんどのＮＬＤＲ埋込み方法は、等長をめざす。
【００１４】
ＮＬＤＲは、グラフ埋込みから導出される。たとえば、Tutte著「Convex representations of graphs」、Proc. London Mathematical Society, 10:304-320, 1960、Tutte著「How to draw a graph」、Proc. London Mathematical Society, 13:743-768, 1963、Fiedler著「Algebraic connectivity of graphs」、Czechoslovak Mathematics Jounal, 23:298-305, 1973、およびChung著「Spectral graph theory」、CBMS Regional Conference Series in Mathmatics, volume 92, American Mathematical Society, 1997を参照願いたい。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
機械学習における最近の進歩は、編成されていない点のデータセットをカバーするようにグラフおよび局所計量制約を推定することにより、グラフ埋込みの枠組みに次元削減を適用することができるという洞察に基づく。上記Tenenbaum他、Roweis他、Brand、Belkin他、およびDonoho他を参照願いたい。グラフ埋込みの枠組みにＮＬＤＲを適用することにより、２つの問題が提示される。
１．外的に湾曲した多様体から引き出されるデータは、任意の有限スケールにおいて局所的に非線形であるため、局所計量制約は、系統的に歪んでいる。したがって、周囲空間ＲＤにおける距離は、多様体Ｍの測地線の弧長の偏った近似である。
２．局所的な推定された計量制約が任意の誤差を含む場合、大域的な解決法は、実際の経験的なデータ分布の代りに近傍系に関して最小平均二乗誤差（ＭＭＳＥ）を含む。
【００１６】
したがって、従来技術によるＮＬＤＲ法の結果は、特に連結グラフに対しわずかな変化がある場合、一貫せず安定しない。Balasubramanian他著「The IsoMap algorithm and topological stability」、Science, 295(5552):7, January 2002を参照願いたい。
【００１７】
したがって、従来技術に対して改善された高次元データの低次元表現を生成する方法を提供することが望まれる。
【課題を解決するための手段】
【００１８】
本発明は、高次元データの局所計量構造を、低次元目標空間における大域的に一貫した等長はめ込みに編成する。本発明は、これを、局所部分集合パラメータ化の収集された零空間を平均化する線形化作用素を生成することによって行う。作用素は、局所計量構造の非線形関数であるデータの成分、すなわち外的曲率およびノイズを隔離し、局所的なノイズ除去から大域的な次元削減までにおよぶデータ変換のスペクトルを定義する。この作用素により、部分集合によりデータが一様に包含されないことによるアーティファクトが低減するため、はめ込みは、誤差があったとしても、それがデータにわたって一様に分散されるというＭＭＳＥ特性を有する。
【００１９】
本発明を、データ削減、ノイズ除去、サンプル外の一般化および新たなデータ点による連続した更新に対して使用することができる。本発明は、また、従来技術によるＮＬＤＲ法と比較した場合、大幅に誤差が低減する。
【００２０】
より具体的には、本発明は、オブジェクトのクラスのオブジェクトに対しサンプルの集合を取得し、各オブジェクトに対して１つのサンプルがあり、各サンプルは、オブジェクトの特性を表す複数のデータ値を含む。サンプルは、部分集合にグループ化され、各部分集合は、少なくとも１つの他の部分集合と交わる。各部分集合に対し、低次元パラメータ化が確定され、低次元パラメータ化の零空間が平均化され、オブジェクトのクラスの低次元表現を含む零空間を有する行列を取得する。
【発明を実施するための最良の形態】
【００２１】
図１に示すように、本発明による方法１００は、オブジェクト１０１のクラス、たとえば、人間の顔を表す。クラスにおけるオブジェクトに対するサンプルのセット１１１を取得する（１１０）。たとえば、サンプルは、顔の画像である。各顔に対して、少なくとも１つの画像がある。各サンプルは、オブジェクトの特性、たとえば、画像における画素色および強度値を表すデータ値の集まりを含む。このため、各サンプルは、数百万ものデータ値を含む可能性がある。各サンプルに対するデータ値は、ベクトルとして編成される。画像に対し、これを、従来のスキャンライン変換によって行ってもよい。
【００２２】
Ｎ個のサンプルをＭ個の部分集合１２１にグループ化し（１２０）、各部分集合が少なくとも１つの他の部分集合と交わるようにする。サンプルの各部分集合１２１に対し、低次元パラメータ化１３１を確定する（１３０）。低次元パラメータ化の零空間を平均化して（１４０）、オブジェクトのクラスの低次元表現１４１を含む零空間を有する行列を取得する。
【００２３】
Ｄ＞ｄである場合、高次元周囲空間ＲＤにおけるクラスのオブジェクトを、周囲空間に埋め込まれたｄ次元多様体からサンプリングする。目的は、埋込みの外的幾何形状を分離することである。すなわち、多様体の内的幾何形状、すなわち多様体における固有のｄ次元座標系から、周囲空間ＲＤにおける多様体の形状を確定することが望まれる。
【００２４】
多様体は、目標空間Ｒｄの開部分集合に対して局所的に等長であり、未知の二次関数Ｃ２によって周囲ユークリッド空間ＲＤ＞ｄに埋め込まれる。多様体Ｍは、周囲空間ＲＤのリーマン部分多様体である。
【００２５】
多様体は、周囲空間ＲＤにおいて外的曲率を有するが、ゼロの内的曲率も有する。しかしながら、目標空間Ｒｄにおける多様体の等長はめ込みは、凹状境界を含む自明でない形状を有する場合がある。
【００２６】
Ｘ＝［ｘ１，…，ｘＮ］∈ＲＤ×Ｎによって表されるサンプルの集合は、周囲空間ＲＤにおける多様体のＮ個のサンプルの位置を記録する。
【００２７】
サンプルの集合Ｙｉｓｏ＝［ｙ１，…，ｙＮ］∈Ｒｄ×Ｎの等長はめ込みは、等長を目標空間Ｒｄにおける剛体運動にまで回復するために集合の外的曲率を除去する。
【００２８】
サンプルをグループ化して（１２０）部分集合にし、その際、各部分集合が少なくとも１つの他の部分集合とオーバラップするようにする。各部分集合は、ｋ個のサンプル（ｋは、変化する可能性がある）を有する。グループ化１２０は、ｎ番目の点がｍ番目の部分集合にある場合であり、かつ、その場合に限り、Ｍｎｍ＞０である隣接行列Ｍ＝［ｍ１，…，ｍＭ］∈ＲＮ×Ｍによって指定される。
【００２９】
各部分集合に対し、部分集合パラメータ化Ｘｍ∈Ｒｄ×ｋ１３１を確定する（１３０）。好ましい実施形態では、部分集合パラメータ化１３１は、ｍ番目の部分集合におけるｋ個のサンプルの局所的に等長なパラメータ化を含む。パラメータ化におけるユークリッド対距離は、多様体における測地線距離に等しい。
【００３０】
等長低次元パラメータ化の零空間を平均化して（１４０）、オブジェクト１０１のクラスの低次元表現１４１を含む零空間を有する行列を取得する。
【００３１】
零空間を介する大域的調整
平均化１４０により、変換後にカーネル行列をもたらすはめ込み誤差行列が生成される。カーネル行列の要素は、目標埋込みにおけるサンプル間の内積を近似する。
【００３２】
カーネル行列は、サンプルの集合に対する部分集合パラメータ化の零空間を併合する。
【００３３】
２つの基底が部分集合パラメータ化Ｘｍ１３０に関連付けられる。すなわち、下式Ｐｍは、部分集合パラメータ化Ｘｍの行空間およびその平行移動の直交基底である。
【００３４】
【数１】
2006079605.tif 000003
【００３５】
また、下式Ｑｍは、相補的な零空間に対する直交基底である。
【００３６】
【数２】
2006079605.tif 000004
【００３７】
共に２つの基底は、単位行列である下式の関係を満足する。
【００３８】
【数３】
2006079605.tif 000005
【００３９】
基底Ｐｍは、サンプルＸｍのアフィン（線形および平行移動）関数の範囲にわたり、基底Ｑｍは、Ｘｍの非アフィン関数、等価的には下式の非線形関数の範囲にわたる。
【００４０】
【数４】
2006079605.tif 000006
【００４１】
サンプルの集合の内的座標は、基底Ｐｍ上に排他的に射影する。サンプルの集合の外的曲率は、基底Ｑｍ上に排他的に射影する。このため、部分集合パラメータ化が等長性に一貫する場合、すなわち、パラメータ化をまとめて、部分集合に対する剛体変換のみを使用してサンプルの集合全体の大域的に一貫したパラメータ化Ｙｉｓｏにすることができる場合、パラメータ化Ｙｉｓｏから取得される任意の部分集合は、対応する局所零空間Ｑｍへのゼロ射影を有する。
【００４２】
等価的に、Ｙｉｓｏは、零空間の和集合のうちの零空間にあり、すなわち、
Ｙｉｓｏ［Ｆ１Ｑ１，…，ＦＭＱＭ］＝０
であり、ここでｉ番目のサンプルがｍ番目の部分集合のｊ番目の点によって表される場合、インジケータ行列Ｆｍ∈｛０，１｝Ｎ×（ｋ＋１）は（Ｆｍ）ｉｊ＝１を有する。
【００４３】
この零空間制約は、Brand著「Charting a manifold」、Advances in Neural Information Processing Systems, volume 15, 2003に記載されている誤差測定の基礎である。この零空間制約は、完全な局所パラメータ化が与えられる完全なはめ込みをもたらすことができる。しかしながら、局所パラメータ化誤差がある場合、零空間制約に関連する最小二乗問題は、グラフの適用範囲に従って誤差を分散する。
【００４４】
従来技術とは対照的に、本発明は、最小二乗誤差解決法に対して望ましいように、サンプル点の集合全体にわたり一様に誤差を分散する。
【００４５】
平均化ステップ１４０は、下式の線形化作用素Ｋを生成することにより、誤差の一様な分散を達成する。
【００４６】
【数５】
2006079605.tif 000007
【００４７】
そして、この線形化作用素は、以下に示す特性を有する。
【００４８】
スペクトル半径
作用素ＫおよびＩ−Ｋは、範囲［０，１］における固有値を有する半正値である。線形化作用素Ｋは、べき等直交射影子の重み付き平均であり、Ｉは単位行列である。
【００４９】
線形化
積ＹＫは、部分集合にわたって平均化された（１４０）、部分集合パラメータ化１３１に対してアフィン変換でない任意の大域パラメータ化Ｙの成分を分離する。下式の射影子は、部分集合パラメータ化Ｘｍに対してアフィン変換でないＹＦｍの成分、すなわちＹのｍ番目の部分集合における点を分離する。
【００５０】
【数６】
2006079605.tif 000008
【００５１】
各サンプルに対し、対角行列は、部分集合にわたって平均化されるこれらの誤差の重み付き平均をもたらす。
【００５２】
大域パラメータ化Ｙの誤差は、その非アフィン成分のユークリッドノルム、すなわち、下式として定義される。
【００５３】
【数７】
2006079605.tif 000009
【００５４】
変換Ｘ→Ｘ（Ｉ−Ｋ）は、サンプルの集合に対して局所的に直交するパラメータ化Ｘの成分、すなわちノイズと、部分集合スケールにおける外的曲率とを軽減する。
【００５５】
変換の繰返しＸ→Ｘ（Ｉ−Ｋ）ｎにより、サンプル点をますます広い近傍においてランクｄにますます近づけることにより、サンプル点を「平滑化」し「展開する」。
【００５６】
最終的に、パラメータ化は、最小特異値に関連する線形化作用素Ｋのｄ＋１左特異ベクトルを含む行を有する下式Ｙの誤差最小化アフィン部分空間にある。
【００５７】
【数８】
2006079605.tif 000010
【００５８】
完全な局所等長性に基づき、これは、作用素Ｋの正確な零空間である。線形化作用素Ｋは、はめ込みの大域的な平行移動に対して不変であるため、零空間は、定数ベクトル１を含み、したがって、下式の関係がある。
【００５９】
【数９】
2006079605.tif 000011
【００６０】
Ｙａｆｆを分離する１つの方法は、ＫＫＴのスペクトルを反転させた後、平行移動に関連する任意の分散を除去するというものである。下式の中心化行列Ｔを使用する。
【００６１】
【数１０】
2006079605.tif 000012
【００６２】
上式の中心化行列を使用すると、ＧＮＡカーネルは、下式となる。
【００６３】
【数１１】
2006079605.tif 000013
【００６４】
そして、そのＰＣＡであるＹａｆｆは、下式となる。
【００６５】
【数１２】
2006079605.tif 000014
【００６６】
パラメータ化Ｙａｆｆは、あらゆる場所においてサンプルの集合に対し最大限アフィン変換である。さらに、以下の条件に基づき、多様体Ｍに対するアフィン写像は、すべての部分集合に対して同じである。
【００６７】
調整
サンプルの集合が、部分集合が大域的に剛性であるＲｄにおける等長はめ込みＹｉｓｏを可能にし、すべての部分集合パラメータ化Ｘｍがそのｄ次元部分集合に対してアフィン変換である場合、パラメータ化Ｙｉｓｏは、Ｙａｆｆが張る部分空間にある。
【００６８】
明らかに、Ｙａｆｆの行空間から引き出される任意のはめ込みは、すべての部分集合パラメータ化｛Ｘｍ｝Ｍｍおよびサンプルの対応する部分集合に対して最小限に非アフィン変換であり、すべてのサンプルＸｍが等長はめ込みに一貫する場合は、完全にアフィン変換である。Ｙａｆｆが等長はめ込みを張ることを示すために、大域的剛性が、Ｙａｆｆにおける任意の２つの部分集合をＹｉｓｏにおけるそれらの対応する部分集合パラメータ化に対して写像するアフィン写像が互いに対して完全に制約されることを暗示するということを想起願いたい。
【００６９】
Ｙａｆｆにおける、点を共有する任意の２つの部分集合を考える。それらのＹｉｓｏに対するアフィン写像が異なる場合、カーネルＫＫＴは、はめ込みを可能にしなければならず、それは共有点の非線形関数であり、それは矛盾である。したがって、すべての部分集合は、ＹａｆｆからＹｉｓｏへの同じアフィン写像を共有しなければならず、ＹａｆｆをＹｉｓｏに対して大域的にアフィン変換であるようにする。
【００７０】
なお、Ｒｄに対して局所的に等長であるサンプルの多様体は、埋込み、すなわちＭからのトポロジー保存写像、または目標空間Ｒｄにおける局所的等長はめ込みを必ずしも有していない。それは、どちらかを有していても、いずれも有していなくても、両方を有していてもよい。たとえば、ランプシェイド、メビウスの帯および螺旋形ランプ等のオブジェクトは、Ｒ２に対して局所的に等長である境界付きＲ３部分多様体であるが、それらを、それぞれ歪み、折返しおよび自己交差なしに平坦化することはできない。
【００７１】
本発明は、ランプシェイドを、平滑な歪みを含んで埋め込み、メビウスの帯を、折返しを含んではめ込み、ランプを、自己交差を含んで等長的にはめ込む。ランプシェイド等の場合、零空間を平均化することにより、各点が、対応する部分集合において線形であるパラメータ化を有する部分集合から最小限に変位することが確実になる。
【００７２】
調整を行うのは、オーバラップする局所パラメータ化において、それらを一貫しないようにする誤差が原因である場合もある。しかしながら、本発明は、従来技術の場合のように部分集合にわたって制約を合計するのではなく、サンプルに対し制約を平均化するため、本発明によるはめ込みは、以下の意味でサンプルに対し忠実である。
【００７３】
ＭＭＳＥ
パラメータ化Ｙａｆｆは、各サンプルのその隣接するサンプルに対する平均局所パラメータ化に関して最小二乗誤差を有する。
【００７４】
要するに、カーネルＫＫＴは、部分集合または近似を採用する、ＬＬＥ、ＨＬＬＥおよびラプラシアン固有マップ等の他の局所方法で可能であるように、埋込みが局所パラメータ化の非線形関数でないようにし、部分集合において低度である点に対して優先的に歪み誤差を分散させないという点で優れている。
【００７５】
実際の等長性Ｙｉｓｏ＝ＡＹａｆｆは、すべての部分集合パラメータ化をそれらの対応する部分集合に対して等長であるようにする線形せん断変換Ａ∈Ｒｄ×ｄに対して解くことによって見つけられる。等長性は、回転および平行移動に対して不変であるため、Ａは、せん断変換である。
【００７６】
これらを抽出するために、Ｘ（バー）ｍを、サンプル１１１の集合における中心部分集合パラメータ化とし、Ｙ（バー）ｍを、Golub他により「Matrix Computations」、Johns Hopkins, third edition, 1996において記載されているようにプロクラステス（Procrustes）方法§１２．４．１を介して中心が置かれ、Ｘ（バー）ｍと位置合せされるように回転した、同じ部分集合に対するＹａｆｆからの座標の集合とする。ここで、（バー）は、その前の記号の上に￣が付されていることを意味する。そして、せん断変換の最小二乗推定は、下式である。
【００７７】
【数１３】
2006079605.tif 000015
【００７８】
ここで、Ｄｍは、下式で表され、カーネルの誤差平均化を繰り返す。
【００７９】
【数１４】
2006079605.tif 000016
【００８０】
Ｋの左特異ベクトルはまた、暗示的なグラフのラプラシアン作用素ＫＫＴの固有ベクトルでもある。この観点から、それらは、はめ込みの変形に対する調和基底を提供する。低周波数モードは、データの大規模曲率を考慮し、高周波数モードは、ノイズ等の局所歪みを考慮する。Ｋの左固有ベクトルは、本質的に同じ構造を有し、そのため、Ｉ−Ｋから０および１への固有値の閾値化により、サンプリングされた集合の周囲形状を保存しながらノイズ等の高周波数アーティファクトをフィルタリングする作用素が生成される。
【００８１】
一般化
ＮＬＤＲは、高次元周囲空間と低次元目標空間との間で新たなサンプルを写像することができる場合の信号処理に対して有用である。サンプル外拡張では、既知のサンプルによって制約される新しいサンプルのはめ込みは可能であるがその逆は可能でない。たとえば、Bengio他著「Out-of-sample extensions for LLE, Isomap, MDS, eigenmaps, and spectral clustering」、Advances in Neural Information Processing Systems, volume 15, 2003を参照願いたい。
【００８２】
基本的な概念は、新たなサンプルのすべての元のサンプルとのカーネル内積を含むベクトルを確定し、そのサンプルを元のはめ込みの固有ベクトルに射影することである。
【００８３】
本発明に対し、この概念を適用することにより、単純な解決法が得られる。
【００８４】
Ｋ’を、上述したように生成された線形化作用素であるが、部分集合行列［ｘ，ｘｉ，ｘｊ，…］に対するものであるとし、この場合、ｘ∈ＲＤは、新たなサンプルであり、｛ｘｉ，ｘｊ，…｝⊂Ｘは、新たなサンプルｘが参加する部分集合に属する元のサンプルである。作用素Ｋ’を、同じ部分集合パラメータ化関数ｆｍを使用して生成し、元の作用素Ｋに対して使用したようにＲＤ→Ｒｄとするが、これらの関数をまたｘにも適用する。ｘのはめ込みは、｛ｙｉ，ｙｊ，…｝⊂Ｙｉｓｏおよびｋ１’すなわちＫ’の最初の行に対し、下式である。
【００８５】
【数１５】
2006079605.tif 000017
【００８６】
新たなサンプルが１つの部分集合Ｘｍのみに割り当てられる場合、はめ込みはアフィン回帰になる。
【００８７】
同じ概念を、周囲空間におけるサンプルのノイズを除去するために使用することができ、ｆｍ（・）が、Ｍに接する面にサンプルをもたらすように擬似可逆であるとする。ノイズが除去されたサンプルｘ’からｆｍ−１（ｆｍ（ｘ））までの周囲ユークリッド距離は、下式である。
【００８８】
【数１６】
2006079605.tif 000018
【００８９】
ここで、ｑ’ｍ１は、Ｑ’ｍの最初の行であり、下式の直交基底である。
【００９０】
【数１７】
2006079605.tif 000019
【００９１】
Ｘ（Ｉ−Ｋ）が各サンプルに対する部分集合制約を平均化することによって元のデータのノイズを除去するように、ノイズが除去されたｘ’の最小二乗推定を取得するために、ｘを含むすべての部分集合にわたり逆射影ｆｍ−１（・）を平均化することができる。ｆｍ（ｍ）が直交射影である場合、この方式は、よく知られた下式の形式となる。
【００９２】
【数１８】
2006079605.tif 000020
【００９３】
これは、ノイズ除去およびはめ込みのためのサンプル集合外拡張が一次仮定の下で一貫していることを示す。この方式を使用して、目標空間から周囲空間にサンプルを写像することも可能である。
【００９４】
集合全体のはめ込みを変更することができるサンプルの集合に関する情報として新たなサンプルを処理することも可能である。Lanczosランク１更新等の固有値分解（ＥＶＤ）に対する略線形時間更新方式を利用することにより、最初に新たなサンプリング１１０で開始する必要なくサンプルおよび部分集合を追加し、または変更することができる。それは、ｋ個の点に対する制約を更新するには、ＥＶＤに対し、最大２ｋ個のランク１更新があればよいためである。
【００９５】
新たな誤差行列がＫ＋Ｊであり、Ｊは、影響を受けたサンプルに対応するｋ個の非ゼロ列を有する。Ｔ−ＫＫＴのＥＶＤが分かると、下式のＥＶＤが確定される。
【００９６】
【数１９】
2006079605.tif 000021
【００９７】
括弧に入れられた加数のスパンは、Ｊの非ゼロ列およびＫの対応する列の結合されたスパンである。したがって、加数は、最大ランク２ｋを有し、そのスパンにおいてＪＪＴを含む。更新を一連のランク１更新とするために、加数を分解して固有対にする。これを、部分空間基底を得るように［Ｊ，Ｋ］を直交させ、加数をこの部分空間内に射影し、結果としての２ｋ×２ｋ対称行列のＥＶＤを実行し、固有ベクトルを使用して基底を逆回転させることにより行うことができる。そして、はめ込みＥＶＤの連続したランク１更新に対して結果としての基底ベクトルおよび固有値を使用する。
【００９８】
サンプル集合複雑性
Ｋが、各局所零空間Ｑｍの部分空間を使用して生成される場合、Ｋは、局所歪みに対して不変であるため、はめ込みが完全に確定されない場合がある。これにより、零空間の次元を確定する、部分集合サイズに関する単純であるが有用な洞察に至る。ｄ次元はめ込みに対し、非空局所零空間を構成するために、少なくともｋ≧ｄ＋２個のサンプルが必要であり、合計で下式の個数のサンプル数が対象となる。
【００９９】
【数２０】
2006079605.tif 000022
【０１００】
そして上式のサンプルに対して、零空間のスパンに含まれる局所ヘッセ行列の推定量に対し、さらに下式の個数のサンプルが必要である。
【０１０１】
【数２１】
2006079605.tif 000023
【０１０２】
このため、非線形性を２次まで除去するために、予期されるはめ込みを局所パラメータ化と比較する任意の局所ＮＬＤＲ方法では、ｋ＝Ｏ（ｄ２）点の部分集合サイズが必要である。それは、より少ないサンプルまたは不完全な零空間制約を使用することにより、低歪みのはめ込みがもたらされる可能性を排除するものではない。それは、厳密にオーバラップする部分集合は、一般に、それらの制約の和集合に従うためである。本発明は、ｋ＝ｄ＋２の場合であっても、密度の高い部分集合の適用範囲を有するデータ多様体に対してうまく作用する。
【０１０３】
サンプル重み付け
はめ込みは、サンプリングノイズ、数値誤差および局所パラメータ化誤差のために誤差を有する可能性がある。本発明により、サンプルを乱すことに関連する誤差は、そのサンプルが含まれる各部分集合の中心からのそのサンプルの距離で二次方程式的に低減する。特に、ｍ番目の部分集合に関して大域パラメータ化Ｙの重み付きでない下式の零空間射影誤差を考える。
【０１０４】
【数２２】
2006079605.tif 000024
【０１０５】
はめ込み点ｙｉ∈Ｙが部分集合点ｘｉ∈Ｘｍに対応するものとする。いずれかの点を乱すことに関連する誤差は、Ｘｍ（バー）と示す部分集合中心からｘｉの距離で二次方程式的に低減する。
【０１０６】
ｙｉまたはｘｉの乱れにより、下式は変化する。
【０１０７】
【数２３】
2006079605.tif 000025
【０１０８】
上式は、ｉとは無関係の何らかの制約ａ，ｂ＞０に対し、下式として変化する。
【０１０９】
【数２４】
2006079605.tif 000026
【０１１０】
Ｐｍを、［１、ＸｍＴ］の列空間の直交基底であるとする。Ｐｍの第１の列は、一定であるとする。直交性により、他のすべての列は、合計するとゼロにならなければならず、そのため、中心のＸｍの線形変換である。したがって、Ｐｍのｉ番目の行の値は、（Ｘｉ−Ｘｍ（バー））において線形であり、射影子ＰｍＰｍＴの対角にあるｉ番目の要素は、下式において二次である。
【０１１１】
【数２５】
2006079605.tif 000027
【０１１２】
したがって、ＱｍＱｍＴ＝Ｉ−ＰｍＰｍＴであるＹの内積のノルムは、下式として線形に変化する。
【０１１３】
【数２６】
2006079605.tif 000028
【０１１４】
ｘｉのわずかな乱れ△ｘｉにより、ノルムは、下式で変化する。
【０１１５】
【数２７】
2006079605.tif 000029
【０１１６】
このように、零空間射影子は、本来、部分集合の周辺において誤差に対し、より耐性があり、周辺の点より中心の点によって、よりはめ込みが確定される。
【０１１７】
しかしながら、かかる耐性が十分ではない状態がある。たとえば、サンプルの集合が局所的に二次代数曲面、たとえば、放物線、双曲線または楕円形である場合、線形射影による推定接空間へのパラメータ化における誤差は、下式として増大する。
【０１１８】
【数２８】
2006079605.tif 000030
【０１１９】
上式の中に示された下式は、接空間における部分集合平均に対するｘｉの距離である。
【０１２０】
【数２９】
2006079605.tif 000031
【０１２１】
このように、局所的に線形のモデルに対し、部分集合重みＭｍｍを、周辺サンプルに関連する誤差をさらに割り引くように有利に調整することができる。
【０１２２】
局所等長パラメータ化
ＮＬＤＲは、多様体の測地線距離に対する代りとして、周囲空間におけるユークリッド距離を使用するが、それは、常に真の距離を少なく見積もる偏りのある近似である。サンプルの多様体がそれらの接空間から離れるように湾曲する場合はいつでも、多様体の局所的に線形な像は、「魚眼」歪みを引き起こし、それにより、大域パラメータ化が場所および方向において収縮し、多様体は、非常に外的な曲率を有する。有限データにより、歪みを除去する部分集合サイズを定義することは不可能であり、多くのＮＬＤＲ方法では、厳密さまたは安定性のために大きい部分集合が必要であり、それは歪み問題を悪化させる。
【０１２３】
二次関数を用いて部分集合の曲率をモデル化することにより、局所的な歪みを実質的に低減し、時に完全に除去することができる。本発明は、平面二次関数（ＰＰＱ）の積である二次多様体、すなわち放物線、楕円形、双曲線および直線状の平面曲線の積として定義される多様体の正確な等長パラメータ化をもたらすように部分集合の曲率をモデル化する。
【０１２４】
たとえば、一般化円筒およびd-toriiの最小等長はめ込みは、局所的に、サンプルの内的に平坦な多様体のＰＰＱ埋込みである。多様体が局所的にＰＰＱでない場合、ＰＰＱモデルは、本質的に混合一次および二次近似であり、二次項は、多様体が最大曲率を示す場所の方向において当てはめられる。ベンチマークＮＬＤＲ「スイスロール」問題は、アルキメデスの螺旋および線分の積多様体であり、二次に対し、螺旋ｆ（θ）＝（θｃｏｓθ，θｓｉｎθ）は、θ＜π／２の場合は楕円形であり、θ＝π／２の場合は放物線であり、θ＞π／２の場合は双曲線である。
【０１２５】
サンプルｐ∈Ｍ⊂ＲＤの周囲の局所近傍を考える。ここでは、サンプルのｄ次元集合の周囲埋込みは、局所的に二次であり、直行基底Ｔｐ∈ＲＤ×２ｄが張る２ｄ次元アフィン部分空間において範囲を有する。明らかに、かかる近傍は存在し、サンプルの集合がｐの周囲で局所的に線形である無限小近傍の上位集合となる。この近傍において、サンプルの集合を、対称的なＦｐに対する下式の行列式および下式の局所同次座標を有する次元２ｄ−１の二次超曲面Ｑｐ⊂ＲＤによって当てはめることができる。
【０１２６】
【数３０】
2006079605.tif 000032
【０１２７】
厳密に言えば、この近傍において、サンプルの集合は、Ｑｐの部分多様体である。実際に重要なのは、面Ｑｐが、任意の線形モデルよりはるかに広い領域にわたるサンプルの集合の優れた局所近似であるという事実である。主な結果は、サンプルの集合の局所ＰＰＱ分解および等長パラメータ化を後述するように確定することができるということである。
【０１２８】
ＰＰＱ
サンプルのｄ次元集合が局所的に平面二次関数の積である場合、ＦｐおよびそのＰＰＱ分解は、Ｔｐを張るＯ（ｄ２）のランダムサンプルから確率１で回復可能である。
【０１２９】
構成的証明の最重要点は、Ｆｐが次元の平面二次関数への対化を示す標準形を有するということである。そして、平面二次関数を、弧長に対して独立して統合することができ、真の測地線パラメータ化が得られる。
【０１３０】
経験的に、二次関数は、下式の縦座標の対の積すべての分散を含む行列Ｂを介して多変量データに当てはめられる。
【０１３１】
【数３１】
2006079605.tif 000033
【０１３２】
ここで、ｘ’ｐｉは、同次サンプルＸ’ｉのｐ番目の要素である。対称非負定値Ｂの固有ベクトルの最小化には、二次方程式係数行列Ｆｐの要素が含まれ、関連する固有値により、下式であるように、当てはめの二乗誤差の和を与えられる。
【０１３３】
【数３２】
2006079605.tif 000034
【０１３４】
これは、下式の個数の未知数の線形システムであるため、サンプル複雑度は、Ｏ（ｄ２）である。
【０１３５】
【数３３】
2006079605.tif 000035
【０１３６】
下式の部分的ＥＶＤ対角行列化により、Ｔｐ内の部分空間回転が得られる。
【０１３７】
【数３４】
2006079605.tif 000036
【０１３８】
それにより、Ｑは、各次元において１つ、二次関数ｑｊ（・）の合計として表される。すなわち、下式で表される。
【０１３９】
【数３５】
2006079605.tif 000037
【０１４０】
ここで、ａｊ∈ａおよびｂｊ∈ｂに対し、ｚは下式である。
【０１４１】
【数３６】
2006079605.tif 000038
【０１４２】
この対角行列化は、固有値ａｊ∈ａにおいてあり得る多重度まで一意的なものである。
【０１４３】
まず、すべての固有値が別個である場合を考える。サンプルの集合が局所的にＰＰＱである場合、その構成要素である平面曲線のうちの任意の１つを、Ｑの二次加数のうちの２つの線形組合せとして表さなければならず、たとえば、ｒｉ∈Ｒ＼０およびｃ∈Ｒに対してｒｉｑｉ（ｚｉ）＋ｑｊ（ｚｊ）＋ｃｊ＝０である。それは、ＥＶＤが、倍数的に増加して次元を結合するすべての対の積ｚｉｚｊを排除する単なる直交基底のみを与えるためである。次元のすべてが加法的に結合される。サンプルの集合が局所的にＰＰＱである場合、２ｄの二次加数を対にしてｄの直交独立二次関数を形成しなければならず、それらは各々、Ｖにおける固有ベクトルの対が張るＲ２部分空間において１Ｄ曲線を指定する。
【０１４４】
したがって、サンプルの集合は、局所的にＱの部分多様体である。すべてのサンプルにわたって繰り返される各加数ｑｉの値のベクトルが、その対にされた加数ｑｊの値のベクトルの１Ｄアフィン変換であるため、データから対化を確定することができる。満足する対を見つけるために、加数ベクトルがＲ２ｄにおいて線形に独立している場合に線形回帰が完全に確定され、それには少なくとも２ｄ個のサンプルが必要である。
【０１４５】
固有値多重度を扱うために、繰り返される固有値｛ａｉ＝ａｊ＝…｝⊂ａに関連付けられたｍ固有ベクトル｛ｖｉ，ｖｊ，…｝⊂Ｖは、Ｒｍ相互回転までのみに確定されるということを想起願いたい。サンプルの集合の局所ＰＰＱ構造は、関連する二次加数を互いにまたは他の固有値の加数と対にすることができるように、これらの固有ベクトルおよび線形係数｛ｂｉ，ｂｊ，…｝の回転があるということを暗示する。４つの原因および多重度の解決法がある。
１．各放物線は、その横座標に対してａｊ≠０、その縦座標に対してａｉ＝０をもたらし、そのため、すべての放物線の縦座標は、零空間において合わせて回転する。回転を、対応する加数値ベクトルを非ゼロａｊのベクトルに回帰することによって回復することができる。
２．各独立した線形次元は、ａｉ＝ｂｉ＝０である加数をもたらす。これらの次元は、放物線次元が対化を介して除去された後に零空間の残りを構成する。
３．各完全な円は、対ａｉ＝ａｊ≠０をもたらす。円であるため、対化は、多重度によって示され、関連する固有ベクトルの回転に対して不変である。
４．各平面対に対し二次形式Ｆで任意に重み付けすることができるため、ａｉ＝ａｋが２つの独立した平面曲線からのパラメータである偶発的な多重度があり得る。これは、散布図行列Ｂが等価なＦパラメータ化のｄ次元零空間を有することを暗示する。その空間では、偶発的な多重度を有するパラメータ化の部分集合は、次元＜ｄを有し、そのためゼロになる。したがって、対化は、確率１で完全に確定される。
【０１４６】
ＰＰＱ多様体は、簡単な等長パラメータ化を有する。局所的な積多様体は、その全体として測地線の部分多様体の積に対して局所的に等長であるため、ＰＰＱ多様体は、各二次関数の弧長パラメータ化の積空間に対して等長である。
【０１４７】
図２に示すように、サンプルの集合が大域的にＰＰＱである、たとえば、Ｒ３において開いた円筒２０１である場合、この手続きは、サンプルの集合全体をパラメータ化することができる（２０２）。放物線および円は、弧長パラメータ化に対し簡単な分析式を提供する。
【０１４８】
すべての内的に平坦な多様体が局所的にＰＰＱであるとは限らず、たとえば、Ｒ３における円錐は積多様体ではない。実際には、対角行列化されたＦｐから二次加数の３つの組すべてを考慮することにより、ＰＰＱ分解が円錐まで拡張されることは自明である。すなわち、円錐は、一定の経験的な合計およびさまざまな符号の二次係数を有する３つの加数として表される。円錐がいかなる追加の固有値多重度源を提示しないため、分解は依然として明確である。Ｒ３における可展面、すなわち空間曲線の接面の残りのクラスは、二次ではないが、産業上の利用に対して十分に正確である部分的円錐近似を有する。
【０１４９】
本発明を、好ましい実施形態の例によって説明したが、本発明の精神および範囲内で他のさまざまな適応および変更を行うことができるということを理解しなければならない。したがって、添付の特許請求の範囲の目的は、本発明の真の精神および範囲内にあるかかる変形および変更をすべて包含することである。
【図面の簡単な説明】
【０１５０】
【図１】本発明によるオブジェクトのクラスを表す方法のブロック図である。
【図２】本発明によるサンプルのマッピングの概略図である。
【図１】
2006079605.tif 000039
【図２】
2006079605.tif 000040
【外国語明細書】
2006079605.tif 000041
2006079605.tif 000042
2006079605.tif 000043
2006079605.tif 000044
2006079605.tif 000045
2006079605.tif 000046
2006079605.tif 000047
2006079605.tif 000048
2006079605.tif 000049
2006079605.tif 000050
2006079605.tif 000051
2006079605.tif 000052
2006079605.tif 000053
2006079605.tif 000054
2006079605.tif 000055
2006079605.tif 000056
2006079605.tif 000057
2006079605.tif 000058
2006079605.tif 000059
2006079605.tif 000060
2006079605.tif 000061
2006079605.tif 000062
2006079605.tif 000063
2006079605.tif 000064
2006079605.tif 000065
2006079605.tif 000066
2006079605.tif 000067
2006079605.tif 000068
2006079605.tif 000069