3.3.デシジョン・ツリーは新しい変化に対して汎化出来ない――Learning Deep Architectures for AI

Learning Deep Architectures for AIの翻訳です。

目次はこちら

3.3.デシジョン・ツリーは新しい変化に対して汎化出来ない

デシジョン・ツリーは、最もよく研究された学習アルゴリズムのひとつである。それらは入力変数の特定の部分集合に注目することが出来るので、一見、非ローカルに見える。しかし、入力空間の分割に基づき、個々の領域に個別のパラメータ群を用いる点で、それらもまたローカル評価子である（Bengio、Delalleau、Simard、2007）。ここで議論するように、これは、それらもまた、前のセクションで他のノンパラメトリック学習アルゴリズムについて検討した制限に苦しむことを、意味する。それらは少なくとも、対象関数の興味のある変化の数と同じ数の訓練例を必要とし、それらは、訓練集合がカバーしていない新しい変化に対応して汎化することが出来ない。

図５：デシジョン・ツリーは再帰的に入力空間を分割する。バイナリ・ツリーでは、根ノードはそれを２分割する。個々のノードは領域と関連する。出力値は個々の葉ノード領域について学習される。

図５に示すように、デシジョン・ツリーは再帰的に入力空間を分割し、その分割の入力領域の各々に出力値を割り付ける。デシジョン・ツリーの学習アルゴリズム(Breiman, Friedman, Olshen, & Stone, 1984)はノンパラメトリックで、木の構造と、ノードと葉に関係するパラメータを選ぶのに非凸最適を含む。幸いなことに、木を追加的に構築する貪欲ヒューリスティクスがうまくいくことが分かっている。木の個々のノードは入力空間の領域と対応し、根は入力空間全体と対応している。区間が内部デシジョン・ツリーによって定義された区間一定関数に、木全体が対応するような（普通のタイプの）デシジョン・ツリーを我々は一定葉デシジョン・ツリーと呼ぶ。個々の葉は、関係する領域の出力への定数とともに、ひとつの区間に関係する。根からひとつの葉への道筋上のデシジョン・ノードは、デシジョン・ツリーが形成する相互に排他的な領域のひとつを定義する。選言標準形回路やガウシアン・カーネル・マシンにおけるように、デシジョン・ノードの出力は掛け合わされ、積を形成する。例は、ある葉領域に属する全ての条件を満たさなければならない。デシジョン・ノードは、アーキテクチャの第１レベルを形成する。葉とそのパラメータ群と関連する予測は、アーキテクチャの第２レベルを形成する。Bengio他(2007)は、訓練集合に見られない変化に対してデシジョン・ツリーが汎化出来ないことについての根本的な制限を研究した。基本的な要旨は、デシジョン・ツリーはそのような変化の各々を正しくモデル化するのに別の葉ノードを必要として、少なくとも個々の葉ノードについて１つの訓練例が必要である、というものである。その理論的分析は、以前、計算複雑性の文献で利用されたアイディアに類似した線にそって構築された(Cucker & Grigoriev, 1999)。これらの結果は、対象関数の変化の数が増加する時デシジョン・ツリーの汎化性能は低下することを示した、以前の実験結果(Pérez & Rendell, 1996; Vilalta, Blix, & Rendell, 1997)とも合致している。

以下の結果はBengio他(2007)からとられた。

定理 3.3.　 $\mathcal{F}$ が区間一定関数の集合であるとする。対象関数 $h\,:\,\mathbb{R}^d\rightar\mathbb{R}$ を考慮する。与えられた表現誤差レベル $\epsilon$ について、対象関数 $h$ を $\epsilon$ より小さな誤差で、 $\mathcal{F}$ 内の関数で近似するのに必要な、一定区間の数の最小値を $N$ とする。すると、一定差デシジョン・ツリーを $\epsilon$ 未満の誤差で訓練するのに、少なくとも $N$ 個の訓練例が必要になる。

必要な例の数は、希望する誤差レベルを達成するのに必要な領域の数について線形に増加することを、上記の定理は述べている。以下の定理は、必要な領域の数が入力のサイズについて指数関数的に増加するような関数族の場合について、より特殊な結果を述べている。

定理 3.4.　 $d$ ビットのパリティ関数を学習する課題について、座標軸に平行なデシジョン・ノードを持つ一定葉デシジョン・ツリーは、 $\epsilon$ 以下の汎化誤差を達成するのに少なくとも $2^d(1-2\epsilon)$ 個の例を必要とする。

（ブーステッド・ツリー(Freund & Schapire, 1996)や森(Ho, 1995; Breiman, 2001)のような）木の集合は１つの木より強力である。それらは３番目のレベルをアーキテクチャに加えることによって、モデルがパラメータの数について指数関数的な、数の領域を判別するのを可能にしている(Bengio et al., 2007)。図６で示すように、それらは、暗黙のうちに森の中の全ての木の出力で（セクション４でさらに検討する概念である）分散表現を形成している。集合内の個々の木は、入力例がその木で落ち着く先の葉／領域を特定する、個別の記号に関係づけることが出来る。木の葉ノードの識別子による入力パターンの記述は非常に豊かである。それは非常に多くの可能なパターンを表現出来る。というのは、 $n$ 本の木に関連する葉領域の交点の数は $n$ について指数関数的であり得るからである。深さ $k-1$ アーキテクチャは、深さ $k$ 関数を表現するには非常に不十分なので、アーキテクチャの深さが木の集合における深さよりさらに大きいようなデシジョン・ツリーに基づく学習アルゴリズムを調査することは興味深い事だろう。

図６：１本の木はパラメータ（差）の数に線形な数の領域を区別出来る一方で、木の集合は（少なくとも木の数が入力の数以下である限り）木の数について指数関数的な数、つまり、パラメータの総数に指数関数的な数、の領域を区別出来る。個々の区別可能な領域は、個々の木の葉のひとつと関連する（ここでは全部で７つの領域について、３本の木があり、各々が２つの領域を定義している）。これはマルチクラスタリングと等価であり、ここでは３つのクラスタリングの各々が２つの領域と関連している。２項RBMは、（その各々は１つの隠れたユニットに関連している）分割毎に２つの直線的に分けられた領域を持つ、マルチクラスタリングである。よってマルチクラスタリングは、入力パターンの分散表現である。