(57)【要約】  高次元空間におけるデータ点の多様体に関する、一部学習済の学習の方法及びシステムのための局所的近傍点ラプラス固有マップ（ＬＮＬＥ）アルゴリズムが提供される。一実施形態において、ＬＮＬＥに基づく方法は、分類済点及び未分類点のデータセットにわたって近接グラフを生成するステップを含む。近接グラフは、分類すべき未分類点に関する局所的近傍点のセットを求めるために用いられる。局所的部分グラフの固有分解は、部分グラフにわたって滑らかな関数を提供する。滑らかな関数は評価され、未分類データは、関数評価に基づいて分類される。一実施形態において、転動的推論（ＴＩ）アルゴリズムアプローチが提供される。他の実施形態において、一部学習済の帰納的推論（ＳＳＩＩ）アルゴリズムアプローチが、次のデータ点の分類のために提供される。信頼性決定が、局所的近傍点内における分類済データ点の数に基づいて提供される。ＬＮＬＥアプローチ及びＬＥアプローチを比較する実験結果が表される。【選択図】図２【特許請求の範囲】
【請求項１】
複数のデータ点から未分類データ点の分類を学習する、コンピュータに基づく方法であって、
複数のデータ点における全てのデータ点間の相対距離を決定するステップと、
未分類データ点に関する近傍データ点のセットを決定するステップと、
前記近傍データ点のセット間の距離の行列の固有分解を実行することによって、関数を決定するステップと、
前記未分類データ点に関する前記関数を評価した結果に基づいて、前記未分類データ点を分類するステップと、
を含むことを特徴とする方法。
【請求項２】
追加的な未分類データ点を受信するステップと、
前記追加的な未分類データ点と前記複数のデータ点との間の相対距離を決定するステップと、
前記追加的な未分類データ点に関する近傍データ点の第二のセットを決定するステップと、
前記近傍データ点の第二のセット間の距離の行列の固有分解を実行することによって、第二の関数を決定するステップと、
前記追加的な未分類データ点に関する前記第二の関数を評価した結果に基づいて、前記追加的な未分類データ点を分類するステップと、
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記近傍データ点のセット内において決定された分類済データ点の数に基づいて、信頼値を提供するステップ
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記固有分解は、分類済データ点が前記近傍データ点のセット内に存在しない場合と、未分類データ点の分類が誤差条件となる場合と、には実行されない
ことを特徴とする請求項１に記載の方法。
【請求項５】
分類済データ点が前記未分類データ点に関する前記近傍データ点のセット内に存在しないと決定するステップと、
前記近傍データ点のセットを決定するために近傍データ点の数を増やすステップと、
増やされた前記近傍データ点の数に基づいて、未分類データ点に関する近傍データ点の第二のセットを決定するステップと、
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記全てのデータ点間の相対距離を決定するステップは、
近接行列を計算するステップ
を含むことを特徴とする請求項１に記載の方法。
【請求項７】
複数のデータ点から未分類データ点の分類を学習する、コンピュータに基づくシステムであって、
複数のデータ点における全てのデータ点間の相対距離を決定する手段と、
未分類データ点に関する近傍データ点のセットを決定する手段と、
前記近傍データ点のセット間の距離の行列の固有分解を実行することによって、関数を決定する手段と、
前記未分類データ点に関する前記関数を評価した結果に基づいて、前記未分類データ点を分類する手段と、
を備えることを特徴とするシステム。
【請求項８】
追加的な未分類データ点を受信する手段と、
前記追加的な未分類データ点と前記複数のデータ点との間の相対距離を決定する手段と、
前記追加的な未分類データ点に関する近傍データ点の第二のセットを決定する手段と、
前記近傍データ点の第二のセット間の距離の行列の固有分解を実行することによって、第二の関数を決定する手段と、
前記追加的な未分類データ点に関する前記第二の関数を評価した結果に基づいて、前記追加的な未分類データ点を分類する手段と、
をさらに備えることを特徴とする請求項７に記載のシステム。
【請求項９】
前記近傍データ点のセット内において決定された分類済データ点の数に基づいて、信頼値を提供するステップ
をさらに備えることを特徴とする請求項７に記載のシステム。
【請求項１０】
前記固有分解を実行する手段は、前記近接データ点のセットを決定する手段からの受信結果に応じて、分類済データ点が前記近傍データ点のセット内に存在しない場合と、未分類データ点の分類が誤差条件となる場合と、には前記固有分解を実行しない
ことを特徴とする請求項７に記載のシステム。
【請求項１１】
分類済データ点が前記未分類データ点に関する前記近傍データ点のセット内に存在しないと決定する手段と、
前記近傍データ点のセットを決定するために近傍データ点の数を増やす手段と、
増やされた前記近傍データ点の数に基づいて、未分類データ点に関する近傍データ点の第二のセットを決定する手段と、
をさらに備えることを特徴とする請求項７に記載のシステム。
【請求項１２】
前記全てのデータ点間の相対距離を決定する手段は、
近接行列を計算する手段
を備えることを特徴とする請求項７に記載のシステム。
【請求項１３】
複数のデータ点から未分類データ点の分類を学習する、コンピュータに基づくシステムであって、
未分類データ点に関する近傍データ点のセットを決定し、前記近傍データ点のセット間の距離の行列の固有分解を実行することによって、関数を決定する局所的近傍点ラプラス固有マップ（ＬＮＬＥ）分類モジュール
を備えることを特徴とするシステム。
【請求項１４】
複数のデータ点から未分類データ点の分類を学習するコンピュータ読み取り可能な記録媒体であって、
複数のデータ点における全てのデータ点間の相対距離を決定するステップと、
未分類データ点に関する近傍データ点のセットを決定するステップと、
前記近傍データ点のセット間の距離の行列の固有分解を実行することによって、関数を決定するステップと、
前記未分類データ点に関する前記関数を評価した結果に基づいて、前記未分類データ点を分類するステップと、
を含む方法をコンピュータシステムに実行させるコンピュータプロセッサにおいて実行されるソフトウェア命令を備えることを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１５】
前記方法は、
追加的な未分類データ点を受信するステップと、
前記追加的な未分類データ点と前記複数のデータ点との間の相対距離を決定するステップと、
前記追加的な未分類データ点に関する近傍データ点の第二のセットを決定するステップと、
前記近傍データ点の第二のセット間の距離の行列の固有分解を実行することによって、第二の関数を決定するステップと、
前記追加的な未分類データ点に関する前記第二の関数を評価した結果に基づいて、前記追加的な未分類データ点を分類するステップと、
をさらに含むことを特徴とする請求項１４に記載のコンピュータ読み取り可能な記録媒体。
【請求項１６】
前記方法は、
前記近傍データ点のセット内において決定された分類済データ点の数に基づいて、信頼値を提供するステップ
をさらに含むことを特徴とする請求項１４に記載のコンピュータ読み取り可能な記録媒体。
【請求項１７】
前記固有分解は、分類済データ点が前記近傍データ点のセット内に存在しない場合と、未分類データ点の分類が誤差条件となる場合と、には実行されない
ことを特徴とする請求項１４に記載のコンピュータ読み取り可能な記録媒体。
【請求項１８】
前記方法は、
分類済データ点が前記未分類データ点に関する前記近傍データ点のセット内に存在しないと決定するステップと、
前記近傍データ点のセットを決定するために近傍データ点の数を増やすステップと、
増やされた前記近傍データ点の数に基づいて、未分類データ点に関する近傍データ点の第二のセットを決定するステップと、
をさらに含むことを特徴とする請求項１４に記載のコンピュータ読み取り可能な記録媒体。
【請求項１９】
前記全てのデータ点間の相対距離を決定するステップは、
近接行列を計算するステップ
を含むことを特徴とする請求項１４に記載のコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には学習機械に関し、より詳細には、機械に基づく、一部学習済の、未分類データの分類に関する。
【背景技術】
【０００２】
一部学習済学習機械は、分類済サンプルデータ点と未分類サンプルデータ点との両方のセットの分類又は回帰機能を学習する機械の能力を備える。例えば、画像、音声、テキスト文書等といった多くの領域において、未分類データは、分類済データよりも容易かつ安価に収集することが可能であるので、このことは重要な問題である。しかし、データが何であるか、何に関連しているかを我々が決定しない場合には、大量のデータはあまり有用ではない。このように、未分類データを分類する機械の能力は、有用な目的で大量のデータを処理することに関して大きな利点を提供する。例えば、機械に基づく画像の分類は、例えば、顔認識、動作検出等といった無数の用途において用いられている。
【０００３】
一部学習済学習機械の基本概念は、分類済データ点と未分類データ点との間に存在する密度関数を（しばしば暗黙のうちに）学習又は推定することによって、未分類データ点を分類することである。一般的に、実用的な用途のほとんどにおいて、データ点は、多くの変数すなわち次元を含んでおり、すなわち、データ点は、高次元空間に属する。例えば、デジタル画像は、画像におけるピクセルと同じ次元（例えば、五百万次元）を有する。このような高次元空間における密度関数の推定は、空間の次元（「ｄ」）よりも指数関数的に多い例を必要とする。それゆえ、一般的には、データセットにおけるデータ点間の関係性に関する仮定が行われる。一般的な仮定としては、データセットにおけるデータ点が、データ点間の関係性により、低次元構造すなわち高次元空間における多様体を形成することが挙げられる。
【０００４】
一般的には、転導的推論（ＴＩ：Transductive Inference）アプローチ及び一部学習済の帰納的推論（ＳＳＩＩ：Semi-Supervised Inductive Inference）アプローチといった、機械に基づく未分類データの分類に関する二つの異なるアプローチが存在する。ＴＩアプローチに基づいて、機械は、分類済データ点及び未分類データ点からなる所与のデータセットから未分類データ点を分類する。全てのデータ点が、学習開始前にシステムに提供される。逆に、ＳＳＩＩアプローチは、分類済例及び未分類例の両方からなるトレーニングセットに依存し、分類のためだけに未分類データ点を含むセットを分離する。ＳＳＩＩアプローチによると、トレーニングセットは、最初に関数を構成又は学習するために用いられ、続いて次のセットにおける未分類データ点を分類するために用いられる。
【０００５】
ＴＩアプローチとＳＳＩＩアプローチとの間の重要な違いとして、これらの具現化に必要な計算資源の量が挙げられる。無制限の資源によると、ＳＳＩＩの問題は、データ点がシステムに提供されてリアルタイムで分類されるＴＩアルゴリズムをリアルタイムで実行することによって解決可能である。しかし、計算資源には限りがあるので、最初にトレーニングセットを処理することによって、新たな例を分類することは、次第にリアルタイムでＴＩアルゴリズムを実行するよりも計算コストが低くなる。一般的には、全てのＳＳＩＩアルゴリズムがＴＩアルゴリズムとしてみなされることは自明であるので、ＳＳＩＩアルゴリズムは、ＴＩアルゴリズムよりも正確ではない。すなわち、学習開始前に未分類データ点を知ることによって、分類がより困難なものとなることを防ぐことができる。それゆえ、一般的には、ＳＳＩＩアルゴリズムは、「対応する」ＴＩアルゴリズムと同程度に振舞う。
正確性がより望まれる場合には、ＴＩアルゴリズムが好ましく、ＴＩアルゴリズムが十分に早い場合には、ＴＩアルゴリズムは、対応するＳＳＩＩアルゴリズムに取って代わる。しかし、ＴＩアルゴリズムはデータ点の閉集合にわたって演算される。このように、サンプル外の新たな未分類データ点を導入する柔軟性が望まれる場合には、ＳＳＩＩアルゴリズムは、新たなデータ点のそれぞれの密度関数の再学習の計算コストを避けることができるので望ましい。
【０００６】
多様体に関する一部学習済の学習のためのアルゴリズムが多数存在する。多様体学習アルゴリズムのいくつかは、実に似ている：work of Bengio et al. (2003) places multi-dimensional scaling (Cox & Cox, 1994), spectral clustering (Ng et al., 2002), Laplacian Eigenmaps (Belkin & Niyogi, 2004), isomap (Tenenbaum et al., 2000), and locally linear embedding (Roweis & Saul, 2000) in a single framework (これらの文献は、全てが参照によって本明細書に一体的に組み込まれるものとする。)
【０００７】
一部学習済学習機械に関する効率的なアプローチの一つとして、ラプラス固有マップ（ＬＥ：Laplacian Eigenmap）アルゴリズムが挙げられる。ＬＥアルゴリズムを具現化するＭＡＴＬＡＢコードは、http://people.cs.uchicago.edu/~misha/ManifoldLearning/MATLAB/laplacian.tar で入手可能であり、参照によって本明細書に組み込まれるものとする。ＬＥアルゴリズムは、（http://yann.lecun.com/exdb/mnist/index.htmlで入手可能な）ＭＮＩＳＴの手書き数字のデータセットに基づいて実行される。図１には、ＭＮＩＳＴデータベースからのサンプルデータセット１００が記載されている。未分類点１０２の第一のセットが提供され、未分類点１０４の第二のセットが分類される。ＬＥアルゴリズムは、（後記する）数少ない分類済例を用いて、（他の複数のタスクに加えて）数字分類タスクを実行するために用いられ、適度に良い正確性を示した。
【０００８】
しかし、ＬＥアルゴリズムにはいくつかの欠点が存在する。ＬＥアルゴリズムは、計算コストが非常に高い。例えば、ＬＥが必要とする資源集約的な計算の一つが、近接グラフの計算である。直接的なアプローチを用いて、データ点の全てのペア間の距離が計算され、各点に関して、最近傍点が追われる。大きいデータセットに関して、全ての距離を計算するためのＯ（ｎ２ｄ）時間が、最近傍点の軌道を追うのに必要な時間を小さくする。このステップは、線形メモリを用いるためのみに具現化されるが、Ｏ（ｎ２ｄ）時間は、非常に大きい問題のせいで禁止されている。
【０００９】
計算的により要求の厳しいステップが、固有値問題の解決法である。ＬＥアルゴリズムは、データセットにわたって形成された近接グラフの固有分解の計算を必要とする。このグラフは、非常に疎であり、内部固有ベクトルが必要とされ、固有分解を非常にコストが高いものとする。大きい疎行列に関して、固有問題は、暗黙のうちに再開されるアーノルド法、すなわち、ＡＲＰＡＣＫによって提供される反復法を用いたＭＡＴＬＡＢコードに基づいて解決される（Lehoucq & Sorensen, 1996; Lehoucq et al., 1998）。当該文献は、参照によって本明細書に組み込まれるものとする。疎行列の最大の固有値（及びそれに対応する固有ベクトル）は、疎行列−ベクトル乗算のみを用いて素早く求められる（Golub & Loan, 1996, 参照によって本明細書に組み込まれるものとする。）。しかし、ラプラスグラフ行列（Ｌ：Laplacian graph matrix）の最小の固有値に対応する固有ベクトルが必要とされており、ＡＲＰＡＣＫは、実行するためのアルゴリズムの内部ループにおいてＬを因数分解する必要がある。この因数分解は、Ｌ自身よりも十分に疎となるであろう。因数分解は、Ｏ（ｎ３）の時間とＯ（ｎ２）のメモリを必要とする。実際には、２ギガバイトのＲＡＭを備えた機械は、メモリ不足のせいで、ＬＥアルゴリズムを有する６０，０００点のＭＮＩＳＴデータセットを処理することができなかった。このことは、非常に大きいデータセットに関して全体的な固有分解を実行することは、従来システムの多くにおいて当然実行不可能であることを示す。
【００１０】
他の欠点としては、ＬＥアルゴリズムが、ＳＳＩＩアルゴリズムに変換する明白で計算効率が良い手法が無い転動的推論ＴＩアルゴリズムであることが挙げられる。資源集約的な全体的固有値問題を解くこと無しにＬＥアプローチを新たなサンプル外のデータ点に適用する明白な手法は存在しない。このように、ＬＥアルゴリズムは、初期のデータセットの一部ではない新たなデータ点を分類するのに非効率である。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
したがって、（１）既存の手法よりも計算コストが低く、（２）データセット全体にわたる再計算の必要無しに新たな点の分類を提供することが可能な、一部学習済学習機械システム及び方法が必要とされている。
【課題を解決するための手段】
【００１２】
本発明は、局所的近傍点ラプラス固有マップ（ＬＮＬＥ：local-Neighborhood Laplacian Eigenmap）アプローチに基づく一部学習済学習機械のための方法、コンピュータ読み取り可能な記録媒体及びシステムを含む。ＬＮＬＥは、ＳＳＩＩアルゴリズムに容易に拡張される高速のＴＩアルゴリズムを提供する。ＬＮＬＥは、分類すべきデータ点の局所的近傍点におけるデータ点のみからなる全体的なデータセットを考慮することによって、未分類データ点の機械分類を可能とする。局所的多様体構造の概念が、全体的なデータセットのグローバルな多様体よりも、未分類データ点の分類のためにより関連する情報を提供するために用いられる。
【００１３】
本発明の一態様によると、分類がデータセットの局所的なバージョンに集中するので、ＬＮＬＥは、全体的なデータセットにわたる固有分解の計算を回避し、それによって、システムがより大きいデータセットを処理することができるようになる。したがって、新たな点が、近接グラフに追加して局所的近傍点に関して処理することによって容易に分類される。
【００１４】
本発明の他の態様によると、ＬＮＬＥは、システムが未分類データの分類を「高信頼性」分類と「低信頼性」分類とに区分することが可能とする。
【００１５】
本発明の一実施例に従って、未分類データ点の分類を学習するコンピュータに基づく方法、コンピュータ読み取り可能な記録媒体、及びシステムが提供される。一実施形態において、本方法は、データセットにおける全てのデータ点間の相対距離を決定するステップを含む。また、本方法は、未分類データ点に関する近傍データ点のセットを決定するステップを含む。近傍データ点のセット間の距離の行列の固有分解が実行されることによって、関数を決定する。最後に、未分類データ点は、未分類データ点に関する関数の評価から取得された結果に基づいて分類される。
【００１６】
他の実施形態において、本方法は、初期データセットの一部ではない追加的な未分類データ点を分類するステップも含む。追加的な未分類データ点は受信され、元のデータセットにおけるデータ点に関するその相対距離が決定される。続いて、追加的なデータ点に関する近傍データ点の第二のセットが決定される。本方法は、近傍データ点の第二のセット間の距離の行列の固有分解を決定することによって、他の関数を決定するステップも含む。続いて、関数の評価に基づいて、追加的な未分類データ点が分類される。
【００１７】
他の実施形態において、近傍データ点のセット内であると決定される分類済データ点の数に基づいて、信頼値が提供される。
【００１８】
本明細書に記載される特徴及び利点は、全てを包括するものではなく、詳細には、図面、明細書及び特許請求の範囲を見た当業者にとって、多くの追加的な特徴及び利点が自明である。さらに、本明細書で用いられる言語は、原則として読みやすさ及び説明を目的として選択されており、本発明の構成要件を線引き又は制限するために選択されたものではないことに留意すべきである。
【００１９】
図面及び以下の記述は、説明のみを目的として本発明の好ましい実施形態に関連するものである。以下の議論から、本明細書に開示された構造及び方法の他の実施形態が、本発明の特許請求の範囲の原理から逸脱しない範囲で利用される実行可能な例として容易に認識されることに留意すべきである。
【発明を実施するための最良の形態】
【００２０】
以下の記述を通じて、分類済データ点はｎＬと呼ばれ、未分類データ点はｎＵと呼ばれる。データセットｎは、ｎＬ＋ｎＵとして定義される。文字ｙは、分類済データ点ｎＬの分類を示すために用いられる。固有ペア項は、固有値λ及びそれに対応する固有ベクトルｖに言及するために用いられ、固有ペアの大きさは、｜（λ，ｖ）｜＝｜λ｜として定義される。
【００２１】
ここで図２を参照すると、学習機械システムの見本の実施形態を説明するシステムブロック図が示されている。学習機械システム２００は、データ記憶ユニット２０２からデータユニット（例えば、データ点ｎＬ及びデータ点ｎＵ）を受信する。データユニットは、既存のデータセットｎ、例えばＭＮＩＳＴデータセットに属していてもよく、データ供給源２０４から受信されてデータ記憶ユニット２０２に記憶されていてもよい。例えば、データ供給源２０４としては、デジタル撮像装置（例えば、カメラ、画像センサ等）、デジタル音声記録装置、他のデジタルデータ取得装置等が挙げられる。あるいは、データ供給源２０４は、有線又は無線ネットワーク、例えば音声又は映像放送システムを介してデータを伝送する遠隔データ伝送システムであってもよい。一実施形態において、データ供給源２０４及びデータ記憶ユニット２０２は、データに関する学習機械の機能を実行するために、機械２０６に外付けされる。他の実施形態において、データ供給源２０４は、機械２０６内に設けられる。例えば、機械２０６としては、データユニットを取得する装置、例えば、カメラを備えた自走車両が挙げられる。さらに他の実施形態において、データ供給源２０４は、データ記憶ユニット２０２と連結されていて機械２０６に内付け又は外付けされており、例えば、ＣＤがデータ供給源２０４であってもよく、データ記憶ユニット２０２はＣＤプレーヤを備えたコンピュータ内に設けられてもよい。
【００２２】
一実施形態において、機械２０６は、例えば、インテル（登録商標）プロセッサに基づくパソコン等といった従来の汎用コンピュータである。しかし、機械２０６は、本明細書に記述されたアルゴリズムを具現化することが可能な計算資源を備えた任意の機械であり、例えば、機械２０６は、知的車両、ヒト型ロボット又は他の計算可能なシステムとして具現化される。
【００２３】
一実施形態において、機械２０６は、外付けのデータ記憶ユニット２０２等といった外部装置とインターフェースで接続する入力／出力（「Ｉ／Ｏ」）モジュール２０８を備える。Ｉ／Ｏモジュール２０８は、機械２０６に内付けされたメモリ２１４にデータを取り込む。例えば、一実施形態において、２ＧＢのＲＡＭを備えた汎用コンピュータが、後記するように用いられる。他の実施形態は、オンチップのキャッシュメモリ、フラッシュメモリ等といった他のメモリ２１４構成を備える。
【００２４】
また、機械２０６は、処理部２１０を備える。一実施形態において、処理部２１０は、カリフォルニア州サンタクララのインテル社から市販されているペンティアム（登録商標）プロセッサ、カリフォルニア州サニーベイルのアドバンスドマイクロデバイス社から市販されているアスロン（登録商標）プロセッサ、カリフォルニア州クパチーノのアップルコンピュータ社のＧ５プロセッサ等といった従来のコンピュータマイクロプロセッサである。他の実施形態において、処理部２１０は、組み込みプロセッサ、カスタムプロセッサ、マイクロコントローラ、プログラム化されたＡＳＩＣ等といった一以上の他の論理処理装置であってもよい。
【００２５】
また、機械２０６は、局所的近傍点ラプラス固有マップ（ＬＮＬＥ：local-Neighborhood Laplacian Eigenmap）分類モジュール２１２を備える。一実施形態において、ＬＮＬＥ分類モジュール２１２は、処理部２１０によって実行された際に後記する一以上の手法を具現化する命令を備えるソフトウェアに具現化される。ＬＮＬＥ分類モジュール２１２は、データ記憶ユニット２０２に記憶され、処理部２１０によって実行されるためにＲＡＭ２１４に読み込まれる。他の実施形態において、ＬＮＬＥ分類モジュール２１２は、一部学習済学習機械（semi-supervised machine learning）のためのＡＳＩＣとしてハードウェアに具現化される。さらに他の実施形態において、ＬＮＬＥ分類モジュール２１２は、カスタムされたコントローラプロセッサとともに動作するように構成された内付けのフラッシュメモリ装置内のファームウェアとして具現化される。ＬＮＬＥ分類モジュール２１０のためのソフトウェア及びハードウェアの様々な結合を備えた他の実施形態が可能であり、本発明の請求の範囲の範囲に含まれる。
【００２６】
一実施形態において、学習機械システム２００は、一以上のユーザインターフェース装置２１６も備える。例えば、ユーザインターフェース装置２１６としては、画像表示装置（例えば、モニタ、平面パネル表示装置等）、キーボード、ポインティングデバイス、及び他の同様なユーザ入力／出力装置が挙げられる。ユーザインターフェース装置２１６は、一以上のＩ／Ｏモジュール２０８を介して機械２０６に連結される。一実施形態において、ユーザインターフェース装置２１６は通常動作中には表れないが、機械２０６は、例えば、データ点ｎＬのトレーニングセットの分類、プログラム化、故障修理、モニタリング等のために、一以上のユーザインターフェース装置２１６に対する（有線又は無線）接続を提供するように構成されたＩ／Ｏモジュール２０８を備える。このような実施形態の機械２０６としては、知的車両、ロボット等が挙げられる。
【００２７】
ここで図３を参照すると、一部学習済学習機械のＬＮＬＥ分類モジュールの一実施形態を説明する機能ブロック図が示されている。一実施形態において、ＬＮＬＥ分類モジュール２１２は、マップモジュール３０２を備える。マップモジュール３０２は、近接マップとも呼ばれる近接グラフ又は近接行列を構築するために、データセットｎにアクセスすることができる。一般的に、近接マップは、他のモジュールにとってアクセス可能なメモリ２１４内に記憶されている。また、ＬＮＬＥ分類モジュール２１２は、近傍点モジュール３０４を備える。近傍点モジュール３０４は、例えばメモリ２１４の近接マップにアクセスすることによって、所与のデータ点ｎＵに対する近傍データ点のセット又はクラスタを決定する。さらに、ＬＮＬＥ分類モジュール２１２は、近傍データ点のセット又はクラスタに対する密度関数を推定するために近傍点モジュール３０４に連結された固有分解（「ＥＤ」）モジュール３０６を備える。評価モジュール３０８は、未分類データ点ｎＵに関してＥＤモジュール３０６によって推定された密度関数を評価し、関連した信頼値を有する結果を提供する。分類部３１０は、評価モジュール３０８に連結されており、評価結果を受信して評価結果に係るデータ点ｎＵを分類する。
【００２８】
ここで図４を参照すると、ＴＩアルゴリズムを具現化するＬＮＬＥ手法の一実施形態を説明するフローチャートが示される。この実施形態において、初期のデータセットｎが入力される（ステップＳ４０２）。データセットｎは、少量の分類済サンプルデータ点ｎＬ及び分類のための未分類サンプルデータ点ｎＵを含む。データセットｎに基づいて、全体的な近接グラフ又は近接行列が、例えば、疎な対称近接行列Ｗとして生成される（ステップＳ４０４）。近接行列Ｗを生成する（ステップＳ４０４）ために、各データ点に対して、データ点ｉがデータ点ｊの最近傍点ｋの一つであるか、ｊがデータ点ｉの最近傍点である場合には、行列要素ｗｉｊ＝１であり、それ以外の場合には、ｗｉｊ＝０である。全体的な近接行列Ｗの構成に関して、ｋは、各点の最近傍点の数を例えば八個と定義するためのプログラム可能なパラメータである。単純な１，０に加えて、他の値、例えば、データ点間の相対距離等が、近接行列（例えば、重み付けされた近接行列）を構成するために利用可能である。
例えば、一実施形態において、「熱核（heat kernel）」距離（「ｄ」）によって重み付けされた点距離、すなわち、ｄ（ｘ１，ｘ２）＝ｅｘｐ（‖ｘ１−ｘ２‖２／ｃ）が用いられる。この実施形態において、ｃは、距離値を正規化するプログラム可能なパラメータに相当し、例えば、一実施形態において、ｃは、データ点間の所望の距離の平方根に設定される。他の実施形態において、「熱核」距離を用いる代わりに、高次元空間におけるデータ点間の実際の距離、例えばピクセル数で測定された距離が用いられる。
【００２９】
続いて、一実施形態において、未分類点ｘが分類のために選択される（ステップＳ４０６）。選択（ステップＳ４０６）は、ユーザ、ランダムな選択によって、又は他の要因に基づいて提供される。選択された点ｘ（ｎＵ＝ｘ）に関して、局所的な近傍点又はクラスタが決定される（ステップＳ４０８）。一実施形態において、横型探索が、ｘまわりの決定された局所的近傍点からなる全体近接グラフＷの部分グラフ又は局所的近接行列Ｗｘを構成するために用いられる。局所的近接行列Ｗｘを生成する（ステップＳ４０８）ために、データ点ｘの最近傍点の数ｋｘが求められる。例えば、一実施形態において、２０００個の最近傍点が用いられる。近接グラフＷにおけるｘに対するｋｘ個の最近傍データ点が選択され、ここで、ｋｘは、プログラム可能な他のパラメータであり、計算資源及び必要な正確性、例えば、実験においては２０００から４０００の間で変化するｋｘの値が用いられた、によって調整される。ｋｘ個の局所的近傍点を用いて、グラフ局所的ラプラス演算子Ｌｘ（Ｌｘ＝Ｗｘ−Ｂｘ）が構成される。Ｂｘは、要素がＷｘの行の合計（すなわち、ｂｉｉ＝Σｊｗｉｊ）である対角行列である。
【００３０】
この実施形態において、続いて、局所的固有分解（local eigen decomposition）が実行される（ステップＳ４１０）。局所的ラプラス演算子（local Laplacian）Ｌｘは、対称かつ半正値である。スペクトルグラフ理論によると、近接グラフのベクトルで定義された関数は、そのラプラス演算子の固有関数の和に分解可能であることがわかる。さらに、ラプラス演算子の最小の固有値に対応する固有関数は、滑らかであることが知られている。それゆえ、局所的ラプラス演算子Ｌｘの局所的固有分解を実行する（ステップＳ４１０）ために、Ｌｘのｐ個の最小固有ペア（λ，ｖ）が導出される（ここで、ｐはアルゴリズムのプログラム可能な他のパラメータである）。一実施形態において、固有値（λ）自身は無視される。ｐ個の固有ベクトル行列Ｅごとのｎは、分類済点及び未分類点に対応して、ｐ個の行列ＥＬごとのｎＬとｐ個の行列ＥＵごとのｎＵとに区分される。ｐがデータ点ｄの次元よりも十分に小さい場合には、この固有関数空間への変換は、次元の減少とみなされる。しかし、一般的には、より良く選択されたｐは、ｄよりも大きい。固有分解の完了後、局所的グラフＷｘにおける滑らかな関数ａｘが決定される。一実施形態において、線形最小二乗適合が実行されることによって、局所的部分グラフＷｘにおける滑らかな関数ａｘを求めることができる。
【００３１】
続いて、関数ａｘが、選択されたデータ点ｘに関して評価される（ステップＳ４１２）。一実施形態において、単純線形最小二乗回帰が、局所的部分グラフＷｘに関して解かれる。問題はバイナリである（すなわち、分類のための分類済セットにおいて二つの分類のみが提供される）と仮定すると、ｐ次元の超平面が、
【数１】
2008538041.tif 000002
を解くことによって構成される。
【００３２】
ａｘが与えられると、未分類点での出力は、
【数２】
2008538041.tif 000003
によって与えられる。
【００３３】
一実施形態において、分類作業がマルチクラスである（すなわち、サンプル分類済セットが二つよりも多いクラスを含む）場合には、一対全（one-vs-all）の超平面ａｃは、右辺をｙｃとした前記式を解くことによって、各クラスｃに関して構成され、ここで、ｉ番目の分類済データ点ｎＬｉがクラスｃに属する場合には、ｙｉｃ＝１であり、それ以外の場合には、ｙｉｃ＝０である。
【００３４】
関数ｙが一旦評価されると、選択されたデータ点ｘが、分類を未分類データ点に適用することによって分類される（ステップＳ４１４）。一実施形態において、二つの分類のうちの一つが、関数の結果に基づいて選択される。例えば、第一の分類が正の結果（ｙＵ＞０）に対応し、第二の分類が負の結果（ｙＵ＜０）に対応する。マルチクラスの実施形態において、最後の分類は、ａｃのそれぞれを未分類点ｎＵに提供し、最大のクラスｃを選択することによって実行される。固有ベクトル行列ＥＬはクラスｃに依存しないことに留意すべきである。したがって、前記二番目の式は、各クラスｃに関して解かれるが、固有分解は一回のみ実行される。
【００３５】
データセットｎにおける追加的な未分類データ点ｎＵは、ステップＳ４０６〜Ｓ４１４を繰り返すことによって簡単に処理される。どの時点においても、一以上のデータ点の分類が出力される（ステップＳ４１８）。一実施形態において、出力は、データセット構造へのアクセスと各データ点に関する所定のフィールドにおけるクラス分類の書き込みとを含む。他の実施形態において、出力（ステップＳ４１８）は、データ点、例えば、認識作業の結果としての画像、顔認識アプリケーションに基づく画像の表示を含む。他の多くの出力手法が可能であり、本発明の範囲内であるとみなされる。
【００３６】
ＬＮＬＥアルゴリズムは、いくつかの利点を有する。例えば、利点の一つとしては、全体的近接グラフＷの全体的固有分解が不要であることが挙げられる。従来のアプローチにおいて、全体的固有分解は、最も時間を消費し計算的に集約されたステップである。さらに、処理のために大きいメモリを必要とするため、非常に大きいデータセットの全体的固有分解は、従来のコンピュータシステムでは不可能であった。ＬＮＬＥアルゴリズムは、アルゴリズムをより大きいデータセットに拡張することができる局所的固有分解を実行することによって、この問題を緩和する。他の利点としては、ＬＮＬＥの局所特性が与えられると、図５に説明されるアルゴリズムのＳＳＩＩ改良型を構成することが容易であることが挙げられる。
【００３７】
図５を参照すると、ＳＳＩＩアルゴリズムを具現化するＬＮＬＥ方法の一実施形態を説明するフローチャートが示される。この実施形態において、図４に関して記述されたステップが、（コネクタＡによって説明されるように、）初期のデータセットｎに関して実行されているものと仮定する。新たなサンプル外の未分類データ点ｘ’が受信される（ステップＳ５０２）。サンプル外のデータ点ｘ’は、ステップＳ４０２で入力された元のデータセットｎの一部ではない。例えば、サンプル外のデータ点ｘ’は、データ供給源２０４によって取得された新たな画像であってもよい。新たなデータ点ｘ’は、ｋ個、例えば８個の局所的近傍点を決定し、対応する値、例えば距離０／１等を近接行列に追加することによって、拡大した近接グラフＷ’を形成する近接グラフＷに追加される。続いて、新たなデータ点ｘ’まわりのｋｘ個（例えば、４０００個）の局所的近傍点の大きいグループが求められ、拡大した近接グラフＷ’における局所的近傍点部分グラフＷｘ’が形成される（ステップＳ５０８）。続いて、ステップＳ５１０〜Ｓ５１８は、本質的には、新たなデータ点ｘ’に関するステップＳ４１０〜Ｓ４１８の繰り返しである。このように、サンプル外の点とサンプル内の点との扱いは同様である。したがって、本アルゴリズムは、サンプル外の点とサンプル内の点に関してほぼ同様に機能する。
【００３８】
本発明の一実施形態に係る他の態様は、分類結果に関する信頼性決定を含む。一実施形態によると、ＬＮＬＥアルゴリズムは、局所的近傍点部分グラフＷｘを構成し、局所的固有分解を実行し、分類すべき各未分類データ点ｎＵに関して最小二乗問題を解く。ある状況の下で、初期のデータセットｎは、非常に少ないサンプル分類済データ点ｎＬを含むことがある。これらの状況の下では、未分類データ点ｎＵまわりの局所的近傍点は、その内部に分類済データ点ｎＬを含まない可能性が十分にある。
【００３９】
この潜在的な問題を解決するために、一実施形態において、ＬＮＬＥ分類手法に関する二つのアプローチが提供される。第一のアプローチであるＬＮＬＥ（Ｇ）は、分類のランダムな推定に基づいて動作する。ＬＮＬＥ（Ｇ）アプローチを用いて、所与のデータ点ｘ（ｎＵ＝ｘ）に関する局所的近傍点Ｗｘが分類済データ点ｎＬを含まない場合には、データ点ｘに与えるためのクラス分類に関するランダムな推定が実行される。結果としてのデータ点の分類ｃは、「低い信頼性」の兆候を含む。逆に、一実施形態において、分類済データ点ｎＬが局所的近傍点Ｗｘ内に存在する場合には、「高い信頼性」の兆候が提供される。さらに他の実施形態において、信頼性決定は、分類すべきデータ点ｘからなる局所的近傍点Ｗｘ内における分類済データ点ｎＬの数に応じた尺度（例えば、二つよりも大きい値を有する）に基づいている。
【００４０】
低分類済サンプル問題を解決するための他のアプローチとしては、ＬＮＬＥ（Ｒ）拒否アプローチが挙げられる。ＬＮＬＥ（Ｒ）アプローチを用いて、未分類点ｘが分類のために選択されて局所的近傍点Ｗｘ内に分類済データ点ｎＬが存在しない場合には、分類拒否が実行されて分類結果は得られない。あるいは、一実施形態において、拒否条件が決定される場合には、拒否条件が発生しなくなるまで、すなわち分類済データ点ｎＬの一つが局所的近傍点Ｗｘの一部となるまで、又は、近傍点Ｗｘの個数が極度に大きくなるまで（例えば、ｋｘが最大値に達するまで）、近傍点の個数ｋｘが、因子Δによって増加される（ｋｘ＝ｋｘ＋Δ）。
【００４１】
＜実験例による実験結果＞
このセクションにおいて、ＬＥアルゴリズム及びＬＮＬＥアルゴリズムを比較することを意図した実験結果に関する報告が提供される。二つの基本的な問題が解決される。第一の問題は、ＬＮＬＥはＬＥと同じくらい正確であるかということである。第二は、ＬＮＬＥはＬＥよりも計算的に要求が厳しくないかということである。
【００４２】
一実験例に関して、ＭＩＮＳＴデータベースのデータセットが、主成分分析（ＰＣＡ）を用いて２８×２８画像のそれぞれを１００次元ベクトルとして表現することによって予め処理された。２ＧＢのＲＡＭを備えた従来の汎用コンピュータが、本発明の様々な実施形態に係るＬＮＬＥアルゴリズムを具現化するために用いられた。
【００４３】
既に刊行された実験において、ＬＥアルゴリズムは、未分類データ点ｎＵを無視するベースラインｋ最近傍点アルゴリズム（baseline k-nearest neighbor algorithm）を超える著しい改善が示された。実験の準備段階において、ｋ−ＮＮの結果が複製され、非常に似た結果が、よく調整されたサポートベクトルマシン（ＳＶＭ）をベースライン分類部として用いて取得された。
【００４４】
ＬＥアルゴリズムアプローチの著者であるBelkin and Niyogi は、「近接行列は非常に疎であり、６００００×６００００行列の固有ベクトル問題を解くことを可能にする」と述べているが、２ＧＢのＲＡＭを備えた機械上で、著者によって提供されたコードを用いて６０，０００点のデータセットに関してＬＥアルゴリズムを実行することは不可能であった。問題の原因の研究後、機械は、６０，０００点のデータセットに関して固有問題を解こうとしている間、メモリ外で実行していることが見出された。少なくとも４ＧＢのＲＡＭが６０，０００個の問題を解くのに必要であり、ＲＡＭの容量は、市販の計算システムにおいて従来入手不可能であるものと判断された。
【００４５】
２ＧＢの機械を用いて、データセットの大きさは、ＬＥアルゴリズム技術の適用のために３０，０００点までに減らされた。ＭＮＩＳＴの３０，０００点のサブセットが、ＬＥに関連する実験において用いられた。ＬＮＬＥアルゴリズムに関しては、全体の６０，０００点のデータセットが用いられた。分類済データ点ｎＬの定数に関して、２０回の反復が実行され、各回は、分類すべきデータ点の異なるランダムなサブセットを選択するものであった。各アルゴリズムに関して用いられる分類済データ点ｎＬのセットは同一であった。各実験に関して、誤差率の平均及び標準偏差が記録された。結果の分布が正規分布であると仮定すると、９０％の「信頼区間」が平均を中心とした標準偏差区間四個分として報告される。
【００４６】
Belkin and Niyogi による従来の実験は、２０から５，０００といった分類済データ点ｎＬの様々な数を用いて実行された。本発明の実施形態に関して実行された実験は、２０から５００個の分類済データ点を備えたデータセットに焦点を当てて実行されたが、これは、未分類データを用いることによって提供される利点がこの範囲で最も著しいためである。
【００４７】
これらの研究において、Belkin and Niyogi は、固有ベクトルの個数ｐの様々な選択をテストし、分類済データ点ｎＬの個数と固有ベクトルｖの個数ｐとを変化させるために二次元テーブルを与えた。同様の実験が本明細書に記述され、各実験の最適な結果のみを報告する。分類済データ点ｎＬの定数に関して、ｐよりも少ない又は多い数を用いて劣化する性能によって、固有ベクトルｖの最適個数ｐが決定された。さらに、固有ベクトルｖの最適個数ｐは、分類済データ点ｎＬの個数に伴って増加した。ＬＮＬＥアルゴリズムに関して、固有ベクトルの最適個数は、一般的には、全体的なＬＥアルゴリズムに関してよりも十分に小さくなり、ＬＮＬＥ（Ｒ）及びＬＮＬＥ（Ｇ）は同一の最適選択を有していた。表１は、各アルゴリズムに関する固有ベクトルの最適個数ｐを、分類済データ点ｎＬの個数の関数として報告する。
【００４８】
前記表に関して、表記は、用いられたデータセットｎのサイズ及び局所的近傍点の個数を示すために用いられていることに留意すべきである。ＬＥアルゴリズムに関して、（Ａ）は、Ａの点のデータセットに言及するものである（例えば、（３０）は、データセットにおける３０，０００個のデータ点を示す）。同様に、ＬＮＬＥアルゴリズムに関して、（Ａ，ｋ）は、前記したｋｘとも呼ばれるｋ個の点の局所的近傍点（例えば、２，０００又は４，０００点）を有するＡの点のデータセットに言及するものである（例えば、Ａは３０，０００、６０，０００又は同様の量）。
【００４９】
表１は、ＬＥアルゴリズム及びＬＮＬＥアルゴリズムに関する固有ベクトルの最適個数ｐを分類済データ点ｎＬの関数として示す。最適個数は、（２０回よりも多い反復で平均された）平均誤差率が最小となる固有ベクトルの個数として選択された。
【表１】
2008538041.tif 000004
【００５０】
＜正確性結果＞
表２及び表３は、ＬＥアルゴリズムとＬＮＬＥアルゴリズムとを比較した基本的な結果を含み、表４は、表３における実験に関する拒否の可能性を与える。
【００５１】
表２は、ＬＥアルゴリズム及びＬＮＬＥ（Ｇ）アルゴリズムの正確性比較を示す。正確性の全てが、誤差率上における９０％の信頼性区間として報告される。
【表２】
2008538041.tif 000005
【００５２】
正確性の標準偏差については、アルゴリズム間の観測された正確性の差に対応して大きくなることが観測された。研究された全てのケースにおいて、全てのアルゴリズムの信頼区間が実質的に重複してテストされた。厳密な観測点を採用して実験は独立していると仮定すると、テストされた全てのアルゴリズムの性能は一致するという仮説は拒絶されない。しかし、実験は、異なるアルゴリズムに関して同じ分類済データ点ｎＬを用いて繰り返される。このように、分散の量が、アルゴリズムよりもむしろ分類済データ点ｎＬのランダムな選択に依存することが予想される。したがって、重複するが実質的には異なる信頼区間が、異なる性能の指標として解釈される。
【００５３】
表３は、ＬＥアルゴリズム及びＬＮＬＥ（Ｒ）アルゴリズムの正確性の比較を示す。正確性の全てが、誤差率上における９０％の信頼区間として報告される。
【表３】
2008538041.tif 000006
【００５４】
表４は、ＬＮＬＥ（Ｒ）に関する拒否率を、全ての実験にわたって平均された近傍点の個数ｋとデータ点の個数との関数として示す。一般的には、ＬＮＬＥ（Ｒ）アルゴリズムの性能を記述する場合には、拒否されないデータ点の性能に関して言及されている。
【表４】
2008538041.tif 000007
【００５５】
これらの実験は若干予備的であるが、いくつかの観測がなされた。３０，０００個のデータ点に関するＬＥアルゴリズム及びＬＮＬＥアルゴリズムを比較すると、少ない数の分類済データ点ｎＬ（例えば、２０から５０）に関して、ＬＥはＬＮＬＥ（Ｇ）よりも優れているが、ＬＮＬＥ（Ｒ）はＬＥよりも優れていることがわかる。大きい数の分類済データ点ｎＬ（例えば、１００から５００）に関して、ＬＮＬＥ（Ｒ）及びＬＮＬＥ（Ｇ）はほぼ同一に機能し（ほとんどの点が拒否されず）、性能はＬＥの性能に非常に近い。
【００５６】
一般的に、３０，０００個よりもむしろ６０，０００個の点を用いてＬＮＬＥを実行することは、近傍点の個数ｋが２，０００個のデータ点に固定される場合には、誤差を増大させる。しかし、近傍点の個数ｋが、例えば４，０００個のデータ点まで比例して増加させることが可能な場合には、誤差は減少する。増えた性能は、６０，０００個の点全てで全体的なＬＥアルゴリズムを用いて報告された性能に十分に匹敵するものと思われる。２０個の分類済点と６０，０００個の点全てを用いたＬＮＬＥ（Ｒ）アルゴリズムに関する少ない近傍点を用いて得られた誤差率の明らかな減少は、２，０００個の近傍点の利用が、４０００個の近傍点と比較してデータの０．２５足された誤差率を提供するので、若干誤解を招くおそれがある（図４参照）。概略すると、最小のデータセットに関して、元のＬＥアルゴリズムはＬＮＬＥ（Ｇ）よりも優れており、ここで、全ての未分類データ点ｎＵが分類される。しかし、ＬＮＬＥ（Ｒ）は、分類がＬＥアルゴリズムよりも正確であるデータの大きいサブセットを識別することが可能である。大きいデータセットに関して、全てのアルゴリズムの性能は非常に類似しているが、ＬＮＬＥアルゴリズムの計算上の要求は非常に小さい。
【００５７】
続いて、（図５に関して前記した）サンプル外の点を分類するＳＳＩＩアルゴリズムにおけるＬＮＬＥアルゴリズムアプローチの利用が検討される。この実験において、ＭＮＩＳＴデータのサブセットの３０，０００個の点が、トレーニングセットとして用いられ、残りの３０，０００個の点が、テストセットとして用いられる。各テスト点ｘは、近接グラフＷｘを増やし、２，０００個の局所的近傍点を求め、結果として得られた固有問題を解き、最小二乗分類を実行することによって分類される。ＬＮＬＥ（Ｇ）及びＬＮＬＥ（Ｒ）の両方の結果が、表５に示される。
【００５８】
表５は、ＬＮＬＥ（Ｇ）アルゴリズム及びＬＮＬＥ（Ｒ）アルゴリズムに関するサンプル外の誤差率を示す。３０，０００個のサンプル外のデータ点ｘ’のそれぞれに関して、近接グラフＷは、データ点ｘ’を追加し、局所的近傍点Ｗｘ’を求め、前記したようにデータ点ｘ’を分類することによって、（Ｗ’に）増える。追加的なサンプル外のデータ点ｘ’は、グラフＷから除去され、続いて、サンプル外のデータ点ｘ’’が同様に処理される。
【表５】
2008538041.tif 000008
【００５９】
結果は、表２及び表３において与えられたＬＮＬＥ（Ｇ）及びＬＮＬＥ（Ｒ）に関するサンプル内の結果と非常に似ており、それによって、ＬＮＬＥのサンプル外の点への自然な拡張がサンプル内の点に関するＬＮＬＥと同様に正確である所望の結果を確認することができる。
【００６０】
＜時間結果＞
アルゴリズムの様々な態様に関する時間要求が本明細書に記載される。測定の全ては、２ＧＢのＲＡＭを備えた２．４ＧＨｚインテル（登録商標）プロセッサを有する単一マシン上で実行される。
【００６１】
表６は、ＬＮＬＥアルゴリズムの実験例に基づいて、３０，０００個から６０，０００個にわたる８個の近傍点（すなわち、ｋ＝８）の近接グラフＷを計算するのに必要な時間（秒単位）を示す。６０，０００点に必要な時間は、３０，０００点に必要な時間のほぼ正確に４倍であり、このことは、アルゴリズムのこの部分の時間がデータ点のｎ２個の距離を計算するのに費やされていることから十分に予想される。
【表６】
2008538041.tif 000009
【００６２】
表７は、ＬＥアルゴリズム及びＬＮＬＥアルゴリズムにおいて生じるデータセットのサイズと所望の固有ベクトルの個数とを変化させることによって内部固有問題を解くのに必要な時間（秒単位）を報告する。サイズ２，０００及び４，０００の固有問題に関して、報告された時間は、１００回にわたる試行の平均である。サイズ３，０００では１回のみの試行が実行された。データセットの固定されたサイズに関して、固有値の個数の関数として必要な時間が、ほぼ線形的に増えることがわかった。他方、データセットのサイズへの依存は、より大きなものとなる。測定値は、時間要求は、Ｏ（ｎ３）よりもＯ（ｎ２）に近づくが、Ｏ（ｎ２）よりも早く増えることを示す。
【表７】
2008538041.tif 000010
【００６３】
ＬＮＬＥアルゴリズムにおいて、各未分類点ｘに関して、我々は、横型探索を用いて近接グラフの部分グラフを求める。表８は、１００回の試行にわたって平均された、近傍点の個数ｋｘ＝２，０００，ｋｘ＝４，０００に関する近接グラフの必要な部分グラフを求めるのに必要な時間を示す。
【表８】
2008538041.tif 000011
【００６４】
固有ベクトル行列Ｅを求めるのに加えて、我々は、ＥＴＬＥＬａｘ＝ＥＴＬｙの形態の半正値な線形系を解き、超平面ａを用いることによって未分類データを分類しなければならない。固有ベクトルの個数ｐはデータ点ｎの個数よりも非常に小さいので、この演算を実行するための時間は、近接グラフ又は固有分解処理の構成と比べて重要ではない。例えば、１００×１００の正定値な行列のCholesky 因数分解は、約２ミリ秒を必要とするが、２０×２０系のCholesky 因数分解は、１ミリ秒未満で済む。それゆえ、これらの時間は、本明細書に記載される解析の残り部分において無視される。
【００６５】
様々な表の時間を足し合わせて、表９は、３０，０００個のサイズのトレーニングセット（ＬＥ及びＬＮＬＥの両方）及び６０，０００個のサイズ（ＬＮＬＥのみ）に関して、未分類データ点ｎＵを分類するために、点ごとに必要な時間を示す。分類時間は秒単位で示され、全体データセットにわたってならされる。ならすために、データセットｎ全体が分類されていないものと仮定する。この表において、ＬＥに関して、（ｎ，ｐ）は、未分類データ点ｎＵの個数ｎと、用いられた固有ベクトルｖの個数ｐとに言及するものである。ＬＮＬＥ（ｎ，ｋ，ｐ）は、ｎ千個のデータ点、ｋ千個のデータ点（ｋｘ）の局所的近傍点及びｐ個の固有ベクトルｖを用いたＬＮＬＥアルゴリズムに言及するものである。
【表９】
2008538041.tif 000012
【００６６】
未分類データセットの全体を分類するために用いられる場合には、ＬＮＬＥアルゴリズムは、ＬＥよりも約二桁遅い。しかし、追加的な考察がいくつか存在する。例えば、大きいサイズのデータセットに関して、ＬＥアルゴリズムは、極度に大きいＲＡＭの容量を必要とするので、実験システムにおいて全く利用不可能である。このように、ＬＮＬＥは、全ての環境下で速いわけではないが、より少ないメモリ要求でＬＥよりも大きい問題を解くことができる能力を提供する。さらに、ＬＮＬＥは、実質的にそれ以上に、容易に拡大可能である。その上、その局所的性質のために、ＬＮＬＥは、セット全体よりもむしろ所望のサブセットの点の分類を可能とし、サブセットの計算効率の悪さのみを受ける。例えば、単一のデータ点のみが３０，０００個のデータ点から分類される必要がある場合には、ＬＥ（３０，５０）は１，５５０秒を要するが、ＬＮＬＥ（３０，２，２０）はたったの８６９秒で済む。
【００６７】
おそらく最も重要なのは、ＬＥはＴＩアルゴリズムのみであるのに対して、ＬＮＬＥはＳＳＩＩアルゴリズム及びＴＩアルゴリズムの両方によって具現化可能であることである。ＬＥによると、例えばｎ＝３０，０００及びｎＬ＝１００と仮定すると、後の時刻で与えられた単一の追加的なサンプル外データ点ｘ’を分類するためのコストは、約４２９秒である。ＬＥによると、近接グラフＷは再利用されるが、サンプル外データ点ｘ’の次の追加のそれぞれに関する全体的固有分解の計算を必要とする。他方、ＬＮＬＥによると、例えば２，０００個の近傍点（ｋｘ）を用いて、近傍点を計算し、追加的なサンプル外データ点ｘ’に関する局所的固有分解計算を実行するためには、たったの約２．４５秒が必要である。このことは、単一のテストデータ点が即時分類のために提供される際、すなわち、バッチ処理が不可能な場合に、ＬＮＬＥを特に便利にする。
【００６８】
さらに、計算効率がさらに必要な場合には、ＬＮＬＥアルゴリズムに対する簡単な拡張が利用可能である。例えば、一実施形態において、ｋｃ個の非常に近いデータ点からなる小さい「中心」が形成され、近傍点がその中心まわりに生成される。単一の固有問題は、（ｋｘ個の近傍点全てではない）中心におけるデータ点全てを同時に分類するために用いられる。この実施形態において、ＬＮＬＥアプローチは、他のＬＮＬＥアプローチと実質的に同じ正確性を提供し、より少ない計算資源で済むＬＥに基づくアプローチと同様に早い性能を提供する。
【００６９】
他の実施形態において、データセット全体にわたって近接グラフを生成する代わりに、ｋｄツリー（kd-trees）、ボールツリー（ball trees）等といったデータ構造がアルゴリズムを速くするために用いられる。さらに、「中心」アプローチを用いると、近接グラフを計算するための時間は、分類を処理するための時間全体の一部よりも大きいので、これらの技術は、「中心」アプローチとともに用いられる。
【００７０】
本発明の特定の実施形態及び用途が本明細書で説明及び記述されたが、本発明は本明細書に開示された正確な構成及び成分に限定されず、添付の特許請求の範囲において定義された本発明の精神及び範囲を逸脱しない範囲で、本発明の方法及び装置の配列、動作及び詳細において、様々な修正、変形及び改変が可能であると理解されるべきである。
【図面の簡単な説明】
【００７１】
【図１】手書き数字のＭＮＩＳＴから得られるサンプルデータセットである。
【図２】学習機械システムの見本の実施形態を説明するシステムブロック図である。
【図３】一部学習済学習機械のＬＮＬＥ分類モジュールの一実施形態を説明する機能ブロック図である。
【図４】ＴＩアルゴリズムを具現化するＬＮＬＥ方法の一実施形態を説明するフローチャートである。
【図５】ＳＳＩＩアルゴリズムを具現化するＬＮＬＥ方法の一実施形態を説明するフローチャートである。
【図１】
2008538041.tif 000013
【図２】
2008538041.tif 000014
【図３】
2008538041.tif 000015
【図４】
2008538041.tif 000016
【図５】
2008538041.tif 000017