3.2.近傍グラフに基づく教師なし、半教師ありアルゴリズム――Learning Deep Architectures for AI
Learning Deep Architectures for AIの翻訳です。
3.2.近傍グラフに基づく教師なし、半教師ありアルゴリズム
ローカル評価子は、上で議論したアルゴリズムのような教師あり学習アルゴリズムだけでなく、これから我々が検討する、教師なしと半教師あり学習アルゴリズムにもみられるものである。ここでもやはり我々は、学習対象の関数の多くの可能な変化をカバーするために、カバーすべき変化の数に比例した数の例が必要になることを、見いだす。
教師なし学習アルゴリズムは、入力分布の特徴をとらえようとする。例えば、多様体学習アルゴリズムは、密度がそこに集中している、より低い次元の領域を発見しようとする。サポート・ベクター・マシンやガウシアン・プロセスのようなカーネル・マシンと多くの教師なし、あるいは、半教師あり学習アルゴリズムの間には関連がある。これらの教師なし、あるいは、半教師ありアルゴリズムの多くは、特定のカーネルを、ことによるとデータ依存のカーネルを、持つカーネル・マシンとして表現出来る (Bengio, Delalleau, Le Roux, Paiement, Vincent, & Ouimet, 2004)。この分析に含まれる以下の教師なし学習アルゴリズムは、形のローカルな変化をとらえることによりデータの多様体構造をとらえようとする。局所的線形埋め込み (RoweisとSaul, 2000)、アイソマップ (Tenenbaum、de Silva、Langford, 2000)、カーネル主要要素分析 (Schölkopf、Smola、Müller, 1998) （あるいはカーネルPCA）、ラプラシアン固有地図(Eigenmaps) (BelkinとNiyogi, 2003)、多様体図解 (Brand, 2003)、スペクトラル・クラスタリング・アルゴリズム (Weiss (1999)の概説を参照)。いくつかのノンパラメトリック半教師あり学習アルゴリズムは、カーネルを用いた類似の概念に基づいている。（Zhu、Ghahramani、Lafferty, 2003。Zhou、Bousquet、Navin Lal、Weston、Schölkopf, 2004。Belkin、Matveeva、Niyogi、2004。Delalleau、Bengio,、Le Roux、2005）。
これらの教師なしと半教師ありのアルゴリズムの大部分は、近傍グラフに基づいている。近傍グラフは、例毎に１つのノードを持ち、隣接するものとの間に線を持つグラフである。ここで我々が検討したい疑問は、上述のノンパラメトリック・アルゴリズムが、前のセクションで、分類や回帰のためのローカル・カーネル・マシンについてすでに議論したのと同じ制限に苦しみそうであるかどうか、ということである。これらのアルゴリズムは、それが何をしているかについての幾何学的な直感を提供出来るが、同様に、ローカル評価子であることが学習を妨げ得るかということも示す。これは、多様体学習の場合について図４に例を挙げて示した。問題は、次元ののろい、と関係している。局所的な線形パッチ（つぎあて）で全ての変化をカバーするために、多くのパッチが必要であろうし、その形を特徴付けるのに十分な例、つまりパッチ場所での接平面、が個々のパッチに必要である。
図４：同じオブジェクト・クラスに関係する画像の集合は多様体、つまり画像の元々の空間よりも低い次元の領域、を形成する。画像、例えば数字の４、を回転、平行移動、縮小することにより、同じクラスの、つまり同じ多様体の別の画像を得る。多様体は局所的には滑らかなので、多様体に接する線形のパッチで原理的には局所的に近似出来る。あいにく、もし多様体が高度に曲がっているならば、パッチは小さくなければならず、多様体の次元に関して指数関数的に多くのパッチが必要になるだる。
近傍グラフに基づいた半教師あり学習アルゴリズムの大きなクラスについて、同様の制限が証明されてきた（Zhu他、2003。Zhou他、2004。Belkin他、2004。Delalleau他、2005）。これらのアルゴリズムは近傍グラフを一定のラベルの領域に分割する。一定のラベルを持つ領域の数は、ラベル付けされた例の数より大きくはなり得ないことを示すことが出来る（Bengio他、2006）。よって分類のために興味のある変化の数と少なくとも同じ数の、ラベル付けされた例が必要である。これは、もし興味のある判断面が非常に多量の変化を持つならば、禁止的な効果を持つだろう。
