(57)【要約】      （修正有）【課題】高次元のサンプリングされたデータから導出されるオブジェクトクラスの低次元モデルの集合から、特定の低次元モデルを選択する。【解決手段】オブジェクトのクラスの低次元モデルの集合からクラスのモデルが選択され、モデルはグラフであり、各グラフは、クラスのオブジェクトを表す複数の頂点と、それら頂点を接続する辺とを含む。クラスのオブジェクトの高次元サンプルの部分集合間の第１の距離が測定される。第１の距離は、クラスの低次元モデルの集合と結合されて、第１の距離によって制約されるモデルの部分集合が生成され、頂点が最大限に分散された特定のモデルが、モデルの部分集合から選択される。【選択図】図３
2007102771.tif 000002
【特許請求の範囲】
【請求項１】
オブジェクトのクラスの低次元モデルの集合から該クラスの特定のモデルを選択する方法であって、前記モデルはグラフであり、各グラフは、前記クラスのオブジェクトを表す複数の頂点と、該頂点を接続する辺とを含む、方法であり、
前記クラスの前記オブジェクトの高次元サンプルの部分集合間の距離を測定すること、
前記第１の距離を前記クラスの前記低次元モデルの集合と結合して、前記第１の距離によって制約されるモデルの部分集合を生成すること、及び
前記モデルの部分集合から、頂点が最大限に分散された特定のモデルを選択すること
を備えた、オブジェクトのクラスの低次元モデルの集合から該クラスの特定のモデルを選択する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはサンプリングされたデータをモデル化することに関し、特に、高次元データを低次元モデルで表現することに関する。
【背景技術】
【０００２】
［発明の背景］
図１に示すように、非線形次元削減（nonlinear dimensionality reduction）（ＮＬＤＲ）は、高次元のサンプリングされたデータ１０１から低次元表現１２０を生成する。データ１０１は、Ｄ＞ｄの場合に、周囲空間（ambient space）ＲＤ１１０に埋め込まれるｄ次元多様体Ｍ１０５をサンプリングする。目的は、埋込みの外的幾何形状（extrinsic geometry）、すなわち多様体Ｍ１０５が周囲空間ＲＤにおいていかに形成されるかを、その内的幾何形状（instrinsic geometry）、すなわち多様体Ｍのｄ次元座標系１２０から分離する（１１５）ことである。多様体を、グラフ理論の分野において一般に理解されるように、辺１３０によって接続される複数の頂点１２５を有するグラフとして表現する（１０４）ことができる。頂点１２５は、高次元座標系において多様体上のサンプリングされたデータ点１０１を表し、辺１３０は、頂点１２５を接続する線又は弧である。このため、グラフは多様体に埋め込まれる。グラフという用語を、解析幾何学におけるような関数のグラフ、すなわちプロットと混乱させるべきではない。
【０００３】
たとえば、人間の顔等のオブジェクトの多様体が顔の画像の周囲空間にいかに埋め込まれているかが分かる場合、モデルの内的幾何形状を使用して顔の画像を編集し、比較し、且つ分類することができ、外的幾何形状を活用して画像における顔を検出し新たな顔の画像を合成することができる。
【０００４】
別の例として、言語音の空間に埋め込まれた母音オブジェクトの多様体を使用して、母音における音響変化の空間をモデル化することができ、それを使用して母音のクラスを分離することができる。
【０００５】
低次元空間にグラフを埋め込み、且つデータ多様体をはめ込む（immerse）ことにより高次元データの低次元モデルを生成する既知のスペクトル方法は、制約集合が不十分であり且つ／又は数値的に悪条件（ill-conditioned）であるために不安定である。
【０００６】
計量制約下でグラフを埋め込むことは、ＮＬＤＲ、アドホック無線ネットワークマッピング及びリレーショナルデータの可視化において頻繁に行われる操作である。スペクトル埋込み方法の進歩にも関わらず、従来技術によるＮＬＤＲ方法は実際的でなく且つ信頼性が低い。ＮＬＤＲに関連する１つの問題点は、問題を、良設定であり、良条件であり、且つ実際的な時間で可解であるようにする埋込み制約を自動的に生成することである。良設定制約は、一意の解を保証する。良条件制約により、解は、次善解から数値的に分離可能となる。
【０００７】
両問題は、埋込み制約のスペクトルにおける小さいか又はゼロの固有ギャップ（eigengap）として現われ、それは、グラフ、すなわちモデルが事実上非剛性（non-rigid）であり、最適解が他の解から識別不可能である解の固有空間があることを示す。小さい固有ギャップにより、解をその変形のモードから分離することが困難になり又はさらには不可能になる。
【０００８】
グラフ埋込み
ラプラシアンのような局所から大域への（local-to-global）グラフ埋込みでは、各グラフ頂点の埋込みは、頂点の直近傍、すなわちグラフ理論術語では頂点の１リング（1-ring）の埋込みによって制約される。次元削減の場合、頂点は、周囲高次元サンプル空間において何らかの形で「巻き上げられる（rolled-up）」多様体からサンプリングされるデータ点であり、グラフ埋込み制約は、より低次元の目標空間において多様体を「展開し（unroll）」ながらその多様体の局所アフィン構造を再現するように設計される。
【０００９】
局所から大域へのグラフ埋込みの従来技術による例には、Tutteの方法（W. T. Tutte著、「How to draw a graph」（Proc. London Mathematical Society, 13:743-768, 1963）参照）と、ラプラシアン固有マップ（Belkin他著、「Laplacian eigenmaps for dimensionality reduction and data represantation」（volume 14 of Advances in Neural Information Processing Systems, 2002）参照）と、局所線形埋込み（locally linear embedding）（ＬＬＥ）（Roweis他著、「Nonlinear dimensionality reduction by locally linear embedding」（Science, 290:2323-2326, December 22 2000）参照）と、ヘッセ（Hessian）ＬＬＥ（Donoho他著、「Hessian eigenmaps」（Proceedings, National Academy of Sciences, 2003）参照）と、チャート化（Brand著、「Charting a manifold」（Advances in Neural Information Processing Systems, volume 15, 2003）参照）と、線形接空間位置合せ（linear tangent-space alignment）（ＬＴＳＡ）（Zhang他著、「Nonlinear dimension reduction via local tangent space alignment」（Proc., Conf. on Intelligent Data Engineering and Automated Learning, number 2690 in Lecture Notes on Computer Science, pages 477-481, Springer-Verlag, 2003）参照）と、測地線零空間解析（geodesic nullspace analysis）（ＧＮＡ）（Brand著、「From subspaces to submanifolds」（Proceedings, British Machine Vision Conference, 2004）参照）とがある。
【００１０】
上述した最後の３つの方法は、最大のあり得るランクの局所アフィン制約を構成し、実質的に安定した解に導く。
【００１１】
ＬＴＳＡ及びＧＮＡは、頂点位置Ｘ＝［ｘ１，…，ｘＮ］∈ＲＤ×Ｎを用いて周囲空間ＲＤに埋め込まれるＮ頂点グラフをとり、新たな頂点位置Ｙ＝［ｙ１，…，ｙＮ］∈Ｒｄ×Ｎをを用いてより低次元の空間Ｒｄにグラフを再度埋め込み、局所アフィン構造を保存する。通常、グラフは、ｋ最近傍等、何らかの発見的手法によって点データから構成される。
【００１２】
埋め込みは以下のように作用する。ｋ個の点のうち１つのこうした近傍を取得し、たとえば局所主成分分析（ＰＣＡ）を使用して局所ｄ次元座標系Ｘｍ＝［ｘｉ，ｘｊ，…］∈Ｒｄ×ｋを構成する。ＰＣＡは、座標系Ｘｍの行に対して、且つ定数ベクトル１に対して直交する直交列を有する零空間行列Ｑｍ∈Ｒｋ×（ｋ−ｄ−１）を生成する。この零空間はまた、局所座標系の任意のアフィン変換Ａ（Ｘｍ）に対して直交し、それにより局所座標系において平行線を保存する任意の平行移動、回転又は伸縮はＡ（Ｘｍ）Ｑｍ＝０を満足する。そして、任意の他の変換Ｔ（Ｘｍ）を、アフィン成分Ａ（Ｘｍ）に非線形歪みＮ（Ｘｍ）＝Ｔ（Ｘｍ）ＱｍＱｍＴを足したものに分離することができる。
【００１３】
ＬＴＳＡ法及びＧＮＡ法は、零空間射影子ＱｍＱｍＴ（ｍ＝１，２，…）を集めて、グラフのすべての近傍にわたって非線形歪みを合計するか（ＬＴＳＡ）又は重みを用いて平均化する（ＧＮＡ）疎行列Ｋ∈ＲＮ×Ｎにする。
【００１４】
埋込み基底Ｖ∈Ｒｄ×Ｎは、正規直交であり［Ｋ，１］の列零空間に張る行ベクトル、すなわちＶＶＴ＝Ｉ及びＶ［Ｋ，１］＝０を有する。したがって、埋込み基底Ｖが存在しＲｄにグラフを埋め込むための基底として提供される場合、その埋込みにおける各近傍は、その元の局所座標系に対しゼロ非線形歪みを有することになる。上記Zhang他を参照されたい。
【００１５】
さらに、近傍が、グラフをＲｄにおいてアフィン的に剛性にするために十分オーバラップする場合、元のデータＸから埋込み基底Ｖへの変換により、グラフのすべての近傍が同様に「伸縮する」。そして、線形変換Ｔ∈Ｒｄ×ｄは、より低次元の頂点位置Ｙ＝ＴＶを与えて伸縮を除去し、より高次元データＸからより低次元データＹへの変換が局所近傍の剛性変換のみを含む、すなわち埋込みＹが等長であるようにする。プロセスに任意の種類の雑音又は測定誤差がある場合、Ｋ∈ＲＮ×Ｎの薄い（thin）特異値分解（ＳＶＤ）か又はＫの零空間すなわちＫＫＴの薄い固有値分解（ＥＶＤ）を介して、最小二乗最適近似埋込み基底（least-squares optimal approximate embedding basis）Ｖを取得することができる。行列Ｋは、Ｏ（Ｎ）個の非ゼロ値を含み非常に疎であるため、反復的部分空間推定量(iterative subspace estimators)は、通常、Ｏ（Ｎ）の時間スケーリングを呈する。疎行列ＫがＧＮＡを用いて構成される場合、対応する特異値ｓＮ−１，ｓＮ−２，…は、次元毎の点別平均歪みを示す。
【００１６】
従来技術によるグラフ埋込みの中心問題のうちの１つは、ＫＫＴの固有値、及び局所ＮＬＤＲにおける任意の制約行列の固有値は、埋込み基底Ｖをもたらすスペクトルの端であるλ０＝０近くで二次的に（quadratically）増大するということである。これについては、ＫＫＴの固有値の二次的増大の証明についての付録を参照されたい。二次的増大とは、固有値曲線がスペクトルの下端
【００１７】
【数１】
2007102771.tif 000003
【００１８】
において略平坦であり、それにより埋込み基底を他の固有ベクトルから分離する固有ギャップがわずかであることを意味する。同様の結果は、単純なグラフラプラシアンのスペクトルに見られ、それらもまたゼロ近くの二次的増大を伴いシグモイド状である。
【００１９】
グラフ埋込みにおいて、制約行列は、有限要素法における剛性行列（stiffness matrix）に類似する役割を果たし、両方の場合において、略ゼロの固有値に関連する固有ベクトルは、最適なパラメータ化、すなわち解と、「振動（vibration）」としても知られる解のそれほど最適ではない歪んだモードとを指定する。固有値ソルバ（eigensolver）又は零空間の他の任意の推定量に直面する問題は、収束速度が、所望の固有値と残りの原理（principle）固有値との相対的な固有ギャップ
【００２０】
【数２】
2007102771.tif 000004
【００２１】
又は固有率
【００２２】
【数３】
2007102771.tif 000005
【００２３】
の線形関数である、ということである。これについては、Knyazev著、「Toward the optimal preconditioned eigensolver」（SIAM Journal on Scientific Computing, 23(2):517-541, 2001）を参照されたい。固有ベクトルの数値安定性は、同様に固有ギャップによって決まる。上述したように、局所から大域へのＮＬＤＲの場合、固有ギャップ及び固有率は共に非常に小さく、解、すなわち高次元データの最良の低次元モデルを解の歪んだモード、すなわち振動から分離することが困難となる。
【発明の開示】
【発明が解決しようとする課題】
【００２４】
直観的に、低周波数振動により、グラフに非常に平滑な湾曲がもたらされ、それは、局所制約レベルにおいて被る変形ペナルティが非常に小さい。グラフの固有値はそれらのペナルティを合計するため、変形の低周波数モードに関連する固有値は非常に小さい値を有し、数値調節が不十分になり、固有値ソルバの収束が低速となる。この問題は、緻密な近傍構造により固有値が狭い間隔で配置される場合のより大きい問題に対して規模が大きくなり、反復固有値ソルバが、振動が最も少ないか又は振動のない最適な最良解、すなわち最良モデルを表す最小固有値及びベクトルを正確に確定することが不可能となる。
【００２５】
したがって、高次元のサンプリングされたデータから導出されるオブジェクトのクラスの低次元モデルの集合から、特定の低次元モデルを選択する方法が必要である。
【課題を解決するための手段】
【００２６】
［発明の概要］
本発明は、オブジェクトのクラスの低次元モデルの集合からクラスの特定のモデルを選択し、モデルはグラフであり、各グラフは、クラスのオブジェクトを表す複数の頂点と、それら頂点を接続する辺とを含む。クラスのオブジェクトの高次元サンプルの部分集合間の第１の距離が測定される。第１の距離は、クラスの低次元モデルの集合と結合されて、第１の距離によって制約されるモデルの部分集合が生成され、頂点が最大限に分散された特定のモデルが、モデルの部分集合から選択される。
【発明を実施するための最良の形態】
【００２７】
［好ましい実施形態の詳細な説明］
ＮＬＤＲを使用する入力クラスのモデルの生成
本発明は、後にさらに詳細に説明する、オブジェクトの低次元モデルの集合、すなわちオブジェクトのクラスを表す局所から大域への埋込みの集合のうちの１つを入力とする。モデルの集合は、非線形次元削減（ＮＬＤＲ）を使用して生成される。好ましい実施形態では、モデルの集合は、測地線零空間解析（ＧＮＡ）、又は任意に線形接空間位置合せ（ＬＴＳＡ）を使用して生成される。それは、他の既知の局所から大域への埋込み方法はすべて、ＬＴＳＡ及びＧＮＡのアフィン制約の部分集合を採用するためである。
【００２８】
図２は、２００４年９月２日に出願され本出願の譲受人によって所有され且つその内容がすべて参照により本明細書に援用される米国特許出願第１０／９３２，７９１号、「Method for Generating a Low-Dimensional Representation of High-Dimensional Data」に記載されている測地線零空間解析（ＧＮＡ）を使用してモデルの集合３０１を生成する従来技術による方法を示す。ＧＮＡを使用してモデルの入力集合を生成するために、高次元周囲空間ＲＤに存在するクラスにおけるオブジェクト２０１を、Ｄ＞ｄの場合に、周囲空間に埋め込まれたｄ次元多様体からサンプリングする（２１０）ことにより、サンプルの集合２１１を生成する。たとえば、サンプル２１１は顔の画像である。各顔に対して、少なくとも１つの画像（サンプル）がある。各サンプルは、オブジェクトの特性、たとえば、画像における画素強度値、恐らくは色の強度値を表す複数のデータ値を含む。このため、各サンプルは、数百万ものデータ値を含む可能性がある。各サンプルに対するデータ値は、ベクトルとして編成される。画像に対し、これを、従来のスキャンライン変換によって行ってもよい。ＮＬＤＲの目的は、埋込みの外的幾何形状を分離することである。すなわち、周囲空間ＲＤにおける多様体の形状を、多様体の内的幾何形状、すなわち多様体における固有のｄ次元座標系から確定することが望まれる。
【００２９】
多様体は、目標空間Ｒｄの開部分集合に対して局所的に等長であり、未知の二次関数Ｃ２によって周囲ユークリッド空間ＲＤ＞ｄに埋め込まれる。多様体Ｍは、周囲空間ＲＤのリーマン部分多様体である。
【００３０】
多様体は、周囲空間ＲＤにおいて外的曲率を有するが、ゼロの内的曲率も有する。しかしながら、目標空間Ｒｄにおける多様体の等長はめ込みは、凹状境界を含む自明でない形状を有する場合がある。
【００３１】
Ｘ＝［ｘ１，…，ｘＮ］∈ＲＤ×Ｎによって表されるサンプルの集合２１１は、周囲空間ＲＤにおける多様体のＮ個のサンプルの位置を記録する。
【００３２】
サンプルの集合Ｙｉｓｏ＝［ｙ１，…，ｙＮ］∈Ｒｄ×Ｎの等長はめ込みは、等長を目標空間Ｒｄにおける剛体運動にまで回復するために集合の外的曲率を除去する。
【００３３】
サンプル２１１をグループ化して（２２０）サンプルの部分集合２２１、すなわち近傍にし、その際、各部分集合が少なくとも１つの他の部分集合とオーバラップするようにする。サンプルの各部分集合はｋ個のサンプル（ｋは変化する可能性がある）を有する。グループ化２２０は、ｎ番目の点がｍ番目の部分集合にある場合であり、且つ、その場合に限り、Ｍｎｍ＞０である隣接行列Ｍ＝［ｍ１，…，ｍＭ］∈ＲＮ×Ｍによって指定される。
【００３４】
各サンプル部分集合２２１に対し、部分集合パラメータ化Ｘｍ∈Ｒｄ×ｋ２３１を確定する（２３０）。部分集合パラメータ化２３１は、ｍ番目の部分集合におけるｋ個のサンプルの局所的に等長なパラメータ化を含む場合がある。パラメータ化におけるユークリッド対距離は、多様体における測地線距離に等しい。
【００３５】
測地線零空間解析を適用する場合、等長低次元パラメータ化の零空間を平均化して（２４０）、オブジェクトのクラスの低次元モデルの集合３０１を含む零空間を有する行列を取得する。本発明の１つの目的は、モデルの集合３０１から特定のモデル３３１を選択する方法を提供することである。集合３０１における各モデルを、より低次元の目標空間Ｒｄにおけるオブジェクトのグラフによって表すことができる、ということが理解されるべきである。本発明は、集合３０１から特定のモデルを選択する従来技術による方法に対する改良である。
【００３６】
近傍拡張（neighborhood expansion）
本発明は、周囲空間ＲＤに埋め込まれたｄ次元多様体のグラフにおいて頂点及び辺の拡張された部分集合に対しより距離の長い制約を適用して、より低次元の目標空間Ｒｄにおいてオブジェクトのグラフ、すなわちモデルの頂点及び辺のメッシュを有効に強化する。
【００３７】
図３に示すように、本発明による方法３００は、モデルの集合３０１から選択されたモデルのサンプル部分集合３０２をグループ化する（３１０）ことによりサブグラフ３１１を生成する。サブグラフ３１１は、選択されたモデル３０２の頂点及び辺のオーバラップした近傍の集合、すなわち周囲空間ＲＤに埋め込まれたｄ次元多様体を表すグラフを含む。サブグラフから選択されたアンカー頂点３１２〜３１５の集合に対し、サブグラフパラメータ化３２１を確定する（３２０）。好ましい実施形態では、アンカー頂点はサブグラフの周縁部における頂点であるが、アンカー頂点の位置は周縁部に限定されない。サブグラフパラメータ化３２１をモデルの入力集合３０１と結合する（３３０）ことにより、特定のモデル３３１を特定する。
【００３８】
図２に関して上述したように、元のサンプルの集合２１０にＧＮＡを適用する場合、等長低次元パラメータ化の零空間を平均化して、オブジェクトのクラスの低次元モデル３０１の集合を含む零空間を有する行列を取得する。図３に戻ると、本発明の一実施形態による結合３３０により、サブグラフパラメータ化３２１の零空間とモデルの入力集合３０１の零空間とを平均化する。サブグラフパラメータ化３２１が、元のサンプル部分集合２２１より長い距離によって分離されるサンプル間で確定されるため、零空間にない固有値は、結合３３０の後、より大きい値を有し、それにより特定のモデル３３１と残りのモデルの集合３０１との間の固有ギャップが増大する。
【００３９】
図４に示すように、選択されたモデル３０２をおよそ又は全体としてカバーする４０１が、すべての頂点の小さい部分集合、たとえばアンカー頂点のみに対して制約を追加する、複数のサブグラフ３１１に対してパラメータ化を確定することにより、選択されたクラスのモデル３０２全体に対して本発明を適用することができる。複数のサブグラフに対するパラメータ化を、図３に示す方法と同様に結合する（３３０）。サイズが大きいさらなるサブグラフパラメータ化４０２を、選択されたモデル３０２に対して反復的に適用してもよい。よりサイズの大きいサブグラフに対するアンカー頂点は、先の反復からのアンカー頂点のみから選択する。
【００４０】
好ましい実施形態では、各サブグラフサイズに対して、頂点の一定の一部をアンカー頂点として選択し、たとえば、サブグラフのサイズとは無関係に各反復に対し頂点の１／４を選択する。
【００４１】
各反復においてサブグラフ及びアンカー頂点の数が半分になる場合、Ｋ行列における非ゼロの数を倍にするのみで、Ｏ（Ｎ）時間でマルチスケール強化を実行することができる。
【００４２】
辺長制約を使用する低次元クラスのモデルの規則化
モデル、すなわちグラフが強化されても、グラフが内的に非剛性である場合もある。それは、一般に、グラフがｋ最近傍等の発見的手法によって生成される場合に発生する。こうした場合、埋込み基底Ｖ∈Ｒｃ×Ｎは、目標空間Ｒｄより高い次元ｃ（ｃ＞ｄ）を有する。たとえば、図５に示すように、ｄ＝２を有するモデル５１０の頂点及び辺の部分集合５０１が同一線上にある場合、それらは軸５０２を生成し、それにより、Ｒｄにおける多様体の種々の折畳み（fold）、たとえばグラフにおける折畳み５０３が可能になる。その場合、モデルの集合は、すべてのあり得る折畳み構成５０４を張る。このため、埋込みは不良設定であり、モデルの集合から最も折り畳まれていないモデルを選択するために規則化が必要である。
【００４３】
図６は、モデルの集合６０２から、頂点が最大限に分散されたモデル６３１、すなわち最も折り畳まれていないグラフを選択する方法６００を示す。高次元サンプル６０１の部分集合間の第１の距離６１１を測定する（６１０）。高次元サンプルは低次元モデルにおける頂点に対応することが理解されるべきである。第１の距離をモデルの集合と結合する（６２０）。結合６２０により、高次元サンプルの部分集合に対応する、第１の距離によって制約される頂点間の距離を有するモデルの部分集合が特定される。好ましい実施形態では、第１の距離は、第１の距離によって制約される辺長を有するモデルの部分集合を特定する。モデルの部分集合から、すべての頂点間の距離が最大である特定のモデル６３１が選択される（６３０）。好ましい実施形態では、特定のモデルにおける各頂点と各頂点のすべての４ホップ（hop）近傍との間の距離を最大化する。このように、モデルとして選択される最も折り畳まれていないグラフは、行列Ｋにおいて符号化されるアフィン制約を満足し、頂点の相互に反発する部分集合間の距離を最大化し、辺のいくつかの部分集合に対して正確な距離の制約を満足する。
【００４４】
任意に、高次元サンプル６０１の第２の部分集合間の距離の第２の集合６１２を、特定のモデル６３１における対応する距離、たとえば辺長と比較（６４０）してもよい。高次元サンプルの第２の部分集合に対応する頂点間の距離が、第２の距離によって制約される場合、特定のモデルの選択６３０が正しいことを確認する一致６５０がある。一致がない場合、方法を繰り返し６５１、第２の距離６１２をモデルの集合及び第１の距離と結合する６２０。
【００４５】
形式上、混合行列Ｕ∈Ｒｃ×ｄは、任意の非ゼロノルムの直交列を有する。誤差ベクトルσ＝［σ１，…，σｃ］Ｔは、その左特異ベクトルに関連する行列Ｋの特異値、すなわち埋込み基底Ｖの行を含む。混合行列Ｕは、埋込み基底Ｖの行が張るあり得る解の空間から計量的に正しい埋込みを選択する。
【００４６】
目標埋込み
【００４７】
【数４】
2007102771.tif 000006
【００４８】
は、全歪み
【００４９】
【数５】
2007102771.tif 000007
【００５０】
と、任意の２つの頂点の間の距離
【００５１】
【数６】
2007102771.tif 000008
【００５２】
（ｖｉは埋込み基底Ｖのｉ番目の列である）とを有する。最適化問題は、Ｒｄにおける非ゼロボリュームの単体を形成する少なくともｄ個の辺に対し距離
【００５３】
【数７】
2007102771.tif 000009
【００５４】
を保存して、重みｒｐｑ≧０のいくつかの選択に対し、分散
【００５５】
【数８】
2007102771.tif 000010
【００５６】
を最大化しながら、歪みを最小化する、ということであり、そうでなければ、埋込みはいくつかの次元において崩壊する可能性がある。直線距離として測定される辺距離Ｄｉｊは、多様体における測地線ではなく周囲空間ＲＤにおける弦であるため、辺長は一様でない可能性があり、そのため、低次元埋込みと一貫していなくてもよい。
【００５７】
非一様性により、より分散し、且つそのためより平坦な低次元埋込みのために、いくつかの辺をわずかに短くすることができる。グラフにおける辺のすべてのサンプル又はランダムなサンプルに対応する距離制約が実施される。距離制約は、接続されたグラフを形成する必要はない。
【００５８】
式１〜２に適用される恒等式
【００５９】
【数９】
2007102771.tif 000011
【００６０】
は、目標
【００６１】
【数１０】
2007102771.tif 000012
【００６２】
に対して次のように半正定値計画（ＳＤＰ）をもたらす。
【００６３】
【数１１】
2007102771.tif 000013
【００６４】
特に、すべての頂点が等しく反発する
【００６５】
【数１２】
2007102771.tif 000014
【００６６】
場合、Ｃ＝ＶＶＴ＝Ｉであり、
【００６７】
【数１３】
2007102771.tif 000015
【００６８】
である。
【００６９】
【数１４】
2007102771.tif 000016
【００７０】
であるため、埋込みは中心化する。
【００７１】
ｃ＝ｄの極値において、Ｕ＝Ｔが等長性に対する向上である場合、ＳＤＰは不要である。ｃ＝Ｄ−１において、半正定値グラフ埋込みが適用され、そこでは、範囲
【００７２】
【数１５】
2007102771.tif 000017
【００７３】
が中心化制約に取って代わり、そのためＬＴＳＡ／ＧＮＡは不要である。中間に、非剛性位置合せ（Non-rigid Alignment）（ＮＡ）と呼ばれる混合がある。反復的固有値解析を用いる場合、ＬＴＳＡ／ＧＮＡはＯ（Ｎ）時間かかるが、制約の大域的に剛性な集合が必要である。半正定値グラフ埋込みは、剛性制約は不要であるが、Ｏ（Ｎ６）の時間スケーリングを有する。
【００７４】
非剛性位置合せ
非剛性位置合せ（ＮＡ）は、ＬＴＳＡ／ＧＮＡを使用して、半正定値計画を実質的に低減する埋込み基底を構成する。さらに、近傍の不完全な集合を辺長制約の不完全な集合と結合するオプションが可能であり、それにより両問題がさらに低減する。この方法は、初期ＬＴＳＡ／ＧＮＡに対する局所次元の推定を必要とするが、半正定値グラフ埋込みから、より高次元のデータＸのスペクトルが大域的埋込み次元の明確な推定値を与えるという性質を受け継ぐ。それは、埋込み基底Ｖが埋込みを張るためである。局所次元を過大推定する（over-estimate）場合があり、それにより局所零空間次元が低減し、そのため大域的剛性が低減するが、それによりＳＤＰ問題においてさらなる自由度を定めることができる。
【００７５】
ＳＤＰ制約の低減
ＳＤＰ等式制約を、行列ベクトル形式でＡＴｓｖｅｃ（Ｇ）＝ｂとして書き直すことができ、この場合、ｓｖｅｃ（Ｇ）は、非対角要素が√２によって乗算されるＸの上三角行列から列ベクトルを形成する。ここでは、制約行列Ａの各列は、何らかの辺
【００７６】
【数１６】
2007102771.tif 000018
【００７７】
に対しベクトル化辺長制約（たとえば、等式制約に対し、ｓｖｅｃ（（ｖｉ−ｖｊ）（ｖｉ−ｖｊ）Ｔ）を含み、ベクトルｂの対応する要素は値Ｄ２ｉｊを含む。ＳＤＰソルバの主なコストは、多数の線形に冗長な列を有する可能性のある、行列Ａ∈Ｒｃ２×ｅに対する演算にある。
【００７８】
問題が正確な解を有する（式５が等式として実行可能である）場合、このコストを射影によって低減することができる。Ｆ∈Ｒｅ×ｆであり、ｆ＜＜ｅは、制約行列Ａの主行・部分空間に対する列・直交基底であるとし、これは、薄いＳＶＤを介してＯ（ｅｆ２ｃ２）時間で推定することができる。Ｍｉｒｓｋｙ−Ｅｃｋａｒｔの定理から、ｆ等式制約
【００７９】
【数１７】
2007102771.tif 000019
【００８０】
は、元の等式制約に等価であるか又はその最小二乗最適近似である。大きく、正確に解決可能な問題の場合、情報の喪失なしに制約集合の濃度を９７％低減することは例外的なことではない。
【００８１】
問題が正確な解を有していない場合、すなわち、式５が不等式としてしか実行可能でない場合、ＳＤＰ問題を、ランダムに選択された辺長不等式制約の小さい部分集合を用いて解くことができる。部分空間Ｖによって課されるアフィン制約と結合して、これは残りの強制されない長さ制約の大部分を満足させるために十分である。違反される制約を有効集合に追加し、すべてが満足するまで繰り返して、ＳＤＰを再度解くことができる。
【００８２】
音声データに対する適用
ＴＩＭＩＴ音声データベースは、６００＋の話者によって発せられる２０００＋の文に対する音声波形及び音声表記の広く利用可能な集まりである。本発明の１つの適用は、母音において音響変動の空間をモデル化する。標準的な表現で開始して、表記において母音としてラベル付けされた１０ミリ秒フレーム毎に、Ｄ＝１３メルケプストラム特性のベクトルを確定する。
【００８３】
表記誤差及び調音結合現象の影響を低減するために、データを、各母音節の中間半分まで狭くして、Ｒ１３においておよそＮ＝２４０，０００のサンプルを生成する。ランダムなデータの近傍に対しＰＣＡを複数回適用することにより、データが局所的に５次元であることが示唆された。５次元近傍及び２５次元基底を有する７個の略最近傍グラフのＮＡ埋込みは、確定するためにかかった時間はわずかに１１分未満であった。スペクトルは鮮鋭であり、７次元では分散は＞９９％であり、５次元では＞９５％であり、２次元では＞７５％である。
【００８４】
生データのＰＣＡ循環は、１３次元、９次元及び４次元それぞれにおいてこれらの割合と一致する。推定された局所次元と大域的埋込み次元との間の不一致に留意すると、ペナルティが低いスラック変数がもたされることにより、グラフが完全に折り畳まれていなかった可能性が探索される。
【００８５】
音声認識における長年の経験則は、全共分散ガウスが３又は４対角共分散ガウスの混合と競合する、ということである［ＬＲＳ８３］。重要な経験的問題は、ＮＡ表現が、ＰＣＡより優れたクラスの分離を提供するか否かである。これを、ガウスを各音素クラスに当てはめ、クラス間の対称化ＫＬダイバージェンス（KL-divergence）を計算することにより（いかなるダウンストリーム音声処理とも無関係に）定量化することができる。
【００８６】
ダイバージェンスが高くなることは、（ガウス）二次分類子によってもたらされる分類誤差を記述するために必要なビットが少なくなることを意味する。ｄ＝５ＮＡ表現におけるクラス間のダイバージェンスは、平均して、ｄ＝５ＰＣＡ表現におけるクラス間のダイバージェンスのおよそ２．２倍であり、その際ＮＡ表現の方が劣っている場合はなかった。同様の利点は、ｄの他の値、ｄ＝１及びｄ＝Ｄに対してさえも観測された。
【００８７】
本発明を好ましい実施形態の例を用いて説明したが、本発明の精神及び範囲内においてさまざまな他の適応及び変更を行ってもよい、ということが理解されなければならない。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内にあるこうした変更及び変更を包含することである。
【００８８】
付録Ａ（Appendix  Ａ）
本発明では、制約行列Ｋを、フィルタによる候補埋込みＺの畳込みに対する離散近似として見ることができる。Ｋの列をプロットする場合、このフィルタは、逆ラプラシアンに似ている。分析により、これは実際にそうであることが分かった。
【００８９】
命題４
ｚｉ＝ｚ（ｙｉ）が、内的座標（intrinsic coordinate）ｙｉにおける何らかのＣ２多値写像
【数１８】
2007102771.tif 000020
によって与えられるデータパラメータ化である場合、
【数１９】
2007102771.tif 000021
とする。
【００９０】
【数２０】
2007102771.tif 000022
とし、ここで２値インデックス行列（indexing matrix）Ｓｍ∈｛０，１｝Ｎ×ｋは、ｍ番目の近傍を形成するｋ個の点を選択し、近傍重みベクトル
【数２１】
2007102771.tif 000023
は、点重みをそれらの近傍中心からの距離に従って割り当てる：
【数２２】
2007102771.tif 000024
【００９１】
そして、Ｋの各列は、‖ｚ−Ｇ＊ｚ−▽２Ｇ＊Ｚ‖２、すなわち、ｚとそれ自体を平滑化したものとの差からラプラシアンガウシアンオペレータ（Laplacian-of-Gaussian operator）によるその畳込みを減算したものに近似するパラメータ化誤差‖ＺＫ‖２Ｆを含むガウシアンオペレータの離散差分である。
【００９２】
証明（命題４）
簡略化のために、まず、規則的な間隔でサンプリングされた１Ｄ多様体の場合を考える。Ｋが、
【数２３】
2007102771.tif 000025
が中心化局所座標
【数２４】
2007102771.tif 000026
の直交基底である場合、形式の各々がＮｍ＝ＱｍＱＴｍ＝Ｉ−１／ｋ・１１Ｔ−ＰｍＰＴｍである近傍零空間射影子（neighborhood nullspace projector)の平均であることを想起されたい。直交化は線形演算であるため、１／ｋ−｛Ｎｍ｝ｉ≠ｊは、
【数２５】
2007102771.tif 000027
すなわち、点ｉ及び点ｊのクリーク重心(clique centroid)からの距離の積に比例する。
【００９３】
行列ＰｍＰＴｍの要素を表面高さとして見ると、左上角及び右下角が最大に正であり、右上角及び左下角が最大に負である、二次鞍面(quadratic saddle surface)が得られる。もっとも簡略化した場合では、ｋ＝２ｊ＋１が各近傍のサイズである場合、Ｐｍ＝ｋ−１／２・［−ｊ，１−ｊ，…，ｊ−１，ｊ］Ｔであり、Ｋの各列の要素は、Ｎｍの対角線に沿ったガウス重み付き合計である。正確には、ｐ番目の非境界近傍に対し、Ｋの列のｎ番目の非ゼロ副対角要素は、
【数２６】
2007102771.tif 000028
である。
【００９４】
なお、
【数２７】
2007102771.tif 000029
はラプラシアンガウシアンであるということ、及びｉ＝ｎを保持しｎ（Ｋの列の要素）にわたって繰り返す場合、各々有限サポートを有する、ガウス及びＬｏＧの差分が得られ、ｉにわたって合計することにより、各々異なるサポートを有するこれらの曲線の重畳が得られる、ということに留意されたい。非規則的なサンプリングを一般化するために、ｉを近傍点間の差分だけ単に増分する。多次元多様体まで一般化するために、上記証明は、Ｍの上に測地線を形成する点の任意の部分集合に対し適用され、Ｋ及びラプラシアンオペレータの線形性により、異なる測地線を形成する点の異なる部分集合の任意の線形結合に対して適用される、ということに留意されたい。
【００９５】
命題５
Ｉ−Ｇ−∇２Ｇのゼロ近傍固有値は二次的に増大する。
【００９６】
証明（命題５）
グラフがその埋込みに対して垂直な空間においていかに振動するかを記述する調和方程式、すなわち、Ｙ（ｘ，ｔ）が時刻ｔ及び位置ｘ（多様体・内的座標における）における変位である場合、−（Ｉ−Ｇ−∇２Ｇ）Ｙ（ｘ，ｔ）＝ｄ２Ｙ（ｘ，ｔ）／ｄ２ｔについて考える。周期的な動きに対し、Ｙ（ｘ）が振動モードである場合、Ｙ（ｘ，ｔ）＝ｓｉｎ（ωｔ）・Ｙ（ｘ）と設定する。代入及び約分の後、調和方程式は、（Ｉ−Ｇ−∇２Ｇ）Ｙ（ｘ）＝ω２・Ｙ（ｘ）まで簡略化され、モードＹ（ｘ）が演算子Ｉ−Ｇ−∇２Ｇの固有関数であることが確認される。代入により、ａ∈｛１，２，…，Ｎ｝、
【数２８】
2007102771.tif 000030
に対するＹ（ｘ）＝ｓｉｎ（ａｘ＋ｂ）がＳ字形曲線
【数２９】
2007102771.tif 000031
上の固有値を含む解（固有ベクトル）に対する直交基底であることを証明することができる。ａ＝０の周囲の級数展開により、先頭項が二次であることが明らかとなる。
【００９７】
証明（命題１）
展開により、新たな近傍、すなわちそのパラメータ化がその構成要素である近傍に対してアフィンであり、そのためその零空間がＫに対して直交する、新たな近傍が生成される。
【００９８】
証明（命題２）
半分にするため、いかなるスケールにおいても、各近傍拡張における頂点の数は、平均して、元の局所近傍の内的次元（intrinsic dimensionality）及び平均サイズのみによって確定される定数ｖ≪Ｎである。また、半分にすることにより、近傍展開の総数がΣｉ（１／２）ｉＮ＜Ｎであることも保証される。合せてこれらは、Ｏ（Ｎ）時間を確立する。Ｎを下回る近傍拡張の各々において、点は、新たな近傍から平均してｄ個の制約を受け取り、それは、点がＮ個の元の近傍の各々において受け取るものと同じか又はそれを下回る。
【００９９】
証明（例題３）
Ｆは制約の分散を保存する循環であるため、常に、∀ｉｆＴｉｂ＞０であるようにＦ＝［ｆ１，…，ｆｆ］のｆ次元行空間を循環することができる。そして、任意の実行不可能な解
【数３０】
2007102771.tif 000032
を、非負のスラック変数によってもたらされる任意の差分により、
【数３１】
2007102771.tif 000033
であるように、ｚ＞０によってスケーリングすることができる。
【図面の簡単な説明】
【０１００】
【図１】非線形次元削減の基本ステップのブロック図である。
【図２】オブジェクトのクラスの低次元モデルの集合を生成する従来技術による方法のブロック図である。
【図３】本発明によるオブジェクトのクラスを表すモデルの集合から特定のモデルを選択する方法のブロック図である。
【図４】本発明による反復的近傍拡張のブロック図である。
【図５】オブジェクトのクラスを表す非剛性グラフのブロック図である。
【図６】本発明による高次元データに基づいてオブジェクトのクラスを表す低次元モデルの集合から特定のモデルを選択する方法のブロック図である。
【図１】
2007102771.tif 000034
【図２】
2007102771.tif 000035
【図３】
2007102771.tif 000036
【図４】
2007102771.tif 000037
【図５】
2007102771.tif 000038
【図６】
2007102771.tif 000039
【外国語明細書】
2007102771.tif 000040
2007102771.tif 000041
2007102771.tif 000042
2007102771.tif 000043
2007102771.tif 000044
2007102771.tif 000045
2007102771.tif 000046
2007102771.tif 000047
2007102771.tif 000048
2007102771.tif 000049
2007102771.tif 000050
2007102771.tif 000051
2007102771.tif 000052
2007102771.tif 000053
2007102771.tif 000054
2007102771.tif 000055
2007102771.tif 000056
2007102771.tif 000057
2007102771.tif 000058
2007102771.tif 000059
2007102771.tif 000060
2007102771.tif 000061
2007102771.tif 000062
2007102771.tif 000063
2007102771.tif 000064
2007102771.tif 000065
2007102771.tif 000066
2007102771.tif 000067
2007102771.tif 000068
2007102771.tif 000069
2007102771.tif 000070
2007102771.tif 000071