２．浅いアーキテクチャの理論的限界――Learning Deep Architectures for AI

Learning Deep Architectures for AIの翻訳です。

目次はこちら

２．浅いアーキテクチャの理論的限界

このセクションでは、不十分な深さのアーキテクチャの制限を明らかにする理論的結果によってディープ・アーキテクチャに賛成する議論を提示する。論文のこのパート（このセクションと次のセクション）はそののちのセクションで説明するアルゴリズムを動機づけし、後半を追いづらくすることなくスキップすることが出来る。このセクションの主な結論は深さ $k$ アーキテクチャによってコンパクトに表現出来る関数は、深さ $k-1$ アーキテクチャによって表現するためには指数関数的な数の計算要素が必要である、ということである。人が利用可能な計算要素の数はそれらを訓練し、あるいは選択することが出来る訓練例の数に依存するので、この結論は計算的だけではなく統計的である。ある関数を表現するために不十分な深さのアーキテクチャを用いる場合、汎化は貧弱になることが予想されるだろう。

次元が固定された入力の場合を考察しよう。そこでは機械が遂行する計算は、方向があり戻りのないグラフによって表すことが出来、そのグラフでは個々のノードが計算を遂行する。その計算はある関数のその入力についての適用であり、各々の入力はグラフ内の別のノードの出力であるか、グラフへの外部入力のひとつである。そのグラフ全体は、外部入力に適用された関数を計算するひとつの回路とみなすことが出来る。計算ノードに許される関数の集合が{ AND, OR, NOT }のような論理ゲートに限定される場合、これはブーリアン回路、つまり論理回路である。

異なる深さのアーキテクチャのさらなる例とともに、深さの観念に戻ろう。関数 $f(x)=x\ast\sin(a\ast{x}+b)$ を考えよう。これは図２に示すように、加算、減算、積算、sin演算、といった単純な演算の組み合わせとして表現できる。この例では、積算 $a\ast{x}$ のためにと、 $x$ による最後の積算のために、別のノードが存在するだろう。グラフ内の個々のノードは、グラフの他のノードの出力である入力値にある関数を適用することによって得られる出力値と関係付けられる。例えば論理回路では個々のノードは、論理関数の小さな集合から取られた論理関数を計算出来る。全体としてのグラフは入力ノードと出力ノードを持ち、入力から出力への関数を計算する。アーキテクチャの深さはグラフの任意の入力からグラフの任意の出力への道のりの最大の長さである。つまり図２の $x\ast\sin(a\ast{x}+b)$ の場合は３である。

図２：計算のグラフが表す関数の例。ここでは個々のノードは許された計算のある集合から取られている。左：要素は $\{\ast,+,\sin\}\cup\mathbb{R}$ である。このアーキテクチャは $x\ast\sin(a\ast{x}+b)$ を計算し、深さ４を持つ。右：要素は $f(x)=\tanh(b+w'x)$ を計算する人工ニューロンである。集合何の各要素はさまざまな $(w,b)$ パラメータを持つ。このアーキテクチャは深さ３の複数層ニューラル・ネットワークである。

もし計算要素の集合に、アフィン演算とシグモイドを含むならば、線形回帰とロジスティクス回帰は深さ１を持つ。つまり１つのレベルを持つ。

アフィン演算と一緒に、固定のカーネル計算 $K(u, v)$ を許された演算の集合の中に加える場合、固定のカーネルを持つカーネル・マシン(Schölkopf, Burges, & Smola, 1999a)は２レベルを持つと考えられる。最初のレベルは、個々のプロトタイプ $x_i$ （選択された代表訓練例）について $K(x,x_i)$ を計算するひとつの要素を持ち、入力ベクトル $x$ をプロトタイプ $x_i$ に照合する。２番目のレベルは、照合プロトタイプ $x_i$ を期待する応答に関係づけるために線形結合 $\Bigsum_i\alpha_iK(x,x_i)$ を遂行する。

要素の集合に人工ニューロン（非線型性に従われたアフィン変換）を入れる場合、通常の複数層ニューラル・ネットワークが得られる(Rumelhart et al., 1986a)。１つの隠れた層の最も普通な選択によって、それらも深さ２を持つ（隠れた層と出力層）。

デシジョン・ツリーもまた、セクション3.3で検討するように、２つの層を持つと見なすことが出来る。

ブースティング(Freund & Schapire, 1996)は通常、その基礎の学習機構に１レベル加える。このレベルは、基礎学習機構の出力の投票、つまり線形結合を計算する。

積上げ(Wolpert, 1992)は、１レベルを加えるもうひとつのメタ学習アルゴリズムである。

脳の組織の現在の知識(Serre, Kreiman, Kouh, Cadieu, Knoblich, & Poggio, 2007)に基づけば、大脳皮質はディープ・アーキテクチャであると見なすことが出来る。例えば、視覚系の多くのいわゆる層を考慮せよ。

深さは、個々の要素に許された計算の集合の選択に依存するが、理論的結果は、大切なのはレベルの絶対的な数ではなく、対象の関数を（計算要素の集合のある選択で）効率的に表現するのにどれだけ必要かに関係するレベルの数である。のちに説明するように、関数が計算要素の集合の特定の選択を用いて $k$ レベルでコンパクトに表現出来るならば、それは $k-1$ レベルかそれ以下で（同じ計算要素集合を用いて）それを表現する計算要素を非常に多く必要とする。

ディープ・アーキテクチャの力に関する最も型通りの議論は、回路の計算複雑性についての調査に由来している。これらの結果が示唆する基本的な結論は、ある関数がディープ・アーキテクチャによってコンパクトに表現出来る場合、それは不完全な深さのネットワークによって表現するには非常に大きなアーキテクチャを必要とする、ということである。

論理ゲートの２層回路は任意のブーリアン関数を表現できる(Mendelson, 1997)。任意のブーリアン関数は積の和の形（選言標準形：最初の層にオプションで入力の否定を伴ったANDゲート、２番目の層にORゲート）かあるいは合計の積の形（結合標準形：最初の層にオプションで入力の否定を伴ったORゲート、２番目の層にANDゲート）で書くことが出来る。浅いアーキテキクチャの制約を理解するために、考察すべき最初に重要な結果は、深さ２の論理回路では、大部分のブーリアン関数は、それを表現するために（入力サイズに関して）指数関数的な数の論理ゲートを必要とする(Wegener, 1987)ということである。

さらに、深さ $k-1$ に制限された時に指数関数的なサイズを必要とする、深さ $k$ の多項式サイズの論理ゲート回路で計算可能な関数がある(Hastad, 1986)。この理論の証明は、深さ２のdビット・パリティ回路は指数関数的サイズを持つことを示す、それ以前の結果(Yao, 1985)を元にしている。dビットパリティ関数は通常、以下のように定義される。
パリティ：

$( b_1,...,b_d)\in\{0,1\}^d$

$=1$ 　もし $\Bigsum_i^db_i$ が偶数ならば

$=-1$ 　さもなければ

人は、これらのブーリアン回路についての計算複雑性の結果が機械学習に関係があるのかどうか疑問に思うかもしれない。学習アルゴリズムに関連する計算複雑性における理論的結果の初期のサーベイについてはOrponen (1994)を参照のこと。興味深いことに、ブーリアン回路についての結果の多くは、その計算要素がパラメータ $w$ と $b$ を持ち、以下のように計算する線形しきい値ユニット（人工ニューロンとしても知られている(McCulloch & Pitts, 1943)）であるアーキテクチャに汎化出来る。

$f(x)=\mathbb{1}_{w'x+b{\ge}0}$ 　　　　　　　　　　　　　　　　(1)

回路のファン・インは、特定の要素の入力の最大数である。回路はしばしば、複数層ニューラル・ネットワークのように、層になっている。そこではある層の要素はその入力を、１つ前の層にある要素からのみ得、最初の層はニューラル・ネットワークの入力である。回路のサイズは、その計算要素の数である（入力要素は除外する。入力要素は計算を実行しない）。

人は論理ゲートの制限が機械学習のアルゴリズムで見出されたようなアーキテクチャには適用出来ないと異議を唱えるかもしれない。それを心にとめると、類似の論理が線形しきい値のユニットによる回路について証明されたことに注意するのは興味深い。そのようなユニットは若干の複数層のニューラル・ネットワークの計算要素である。特に興味深いのは、以下の定理である。これは、深さ $k$ の回路でコンパクトに表現可能なある関数を表現しようとする時に、単調重みしきい値回路（つまり、線形しきい値と正の重みを持つ複数層ニューラル・ネットワーク）に適用される、以下の定理である。

定理2.1.　関数 $f_k\in\mathcal{F}_{k,N}$ を計算する深さ $k-1$ の単調重みしきい値回路は、若干の定数 $c>0$ と $N>N_0$ について少なくとも $2^{cN}$ のサイズを持つ(Hastad & Goldmann, 1991)。

関数 $\mathcal{F}_{k,N}$ のクラスは以下のように定義される。ツリーである深さ $k$ の回路によって定義された $n^{2k-2}$ 個の変数の関数を、それは含む。ツリーの葉には、否定演算をほどこされていない(?　unnegate)入力変数が存在し、関数の値はその根に存在する。下から $i$ 番目のレベルは、 $i$ が偶数の時ANDゲートから成り、 $i$ が奇数の時ORゲートから成る。頂点と底辺レベルのファン・インは $N$ であり、他の全てのレベルでは $N^2$ である。

上の結果は、（AI課題を遂行するために我々が学習したい関数のような）他のクラスの関数がディープ・アーキテクチャを必要とすることも、これらの証明された制限が他のタイプの回路に当てはまるとも、証明してない。しかし、これらの理論的結果は次のような問題を提起する。（大部分の機械学習アルゴリズムに典型的に見られる）深さ1, 2, 3のアーキテクチャは、より複雑な関数を効率的に表現するには浅すぎるだろうか？　上記の定理のような結果はまた、普遍的に正しい深さは存在しないだろうということも示唆する。個々の関数（つまり、個々の課題）は（与えられた計算要素の集合について）特定の最小深さを要求するのであろう。よって我々は最終アーキテクチャの深さを決定するためのデータを用いる学習アルゴリズムを開発するよう努力しなければならない。

アーキテクチャの深さは高度に変化する関数の観念と関係している。一般に、ディープ・アーキテクチャは、不適切なアーキテクチャではそれを表現するのに非常に大きなサイズを必要とするような高度に変化する関数を、コンパクトに表現できる、と我々は主張する。ある関数の区分近似（例えば、区分一定、とか、区分線形）が多くの区分を必要とする時に、その関数は高度に変化する、と我々は言う。ディープ・アーキテクチャは多くの演算の組合せであり、どのような場合でも、それは非常に大きい深さ２アーキテクチャで潜在的に表現可能である。小さいが深い回路の中の計算ユニットの組合せは、大きいが浅い回路の効率的な因数分解であると実際にみなすことが出来る。計算ユニットが組み合わされる仕方を再組織化することは表現サイズの効率に劇的な効果を持ち得る。例えば、多項式 $\prod_{i=1}^n\Bigsum_{j=1}^ma_{ij}x_j$ は、和の積として、 $O(mn)$ 個の計算要素のみで効率的に表現出来るが、積の和のアーキテクチャでは、 $O(n^m)$ 個の計算要素を必要とし、非常に非効率である。

ディープ・アーキテクチャのより大きな表現力と、それのAIと機械学習についての潜在力を示唆するさらなる例が、Bengio and Le Cun (2007)でも議論されている。より深いアーキテクチャの期待する利点についての、より認知論的観点からの早期の議論は、Utgoff and Stracuzzi (2002)に見られる。学習ディープ・アーキテクチャの必要性を正当化する若干の理論的土台を確立するために、我々は次に関連する疑問に向かう。ディープ・アーキテクチャは、表現される関数における変化より少ない計算要素で、高度に変化する関数をコンパクトに表現出来るが、多くの最先端の機械学習アルゴリズムはその特徴を持っていない。

結論を言えば、多くの計算複雑性の結果は、深さ $k$ でコンパクトに表現出来る関数を浅いアーキテクチャで表現するためには、非常に多くの要素を必要とする。アーキテクチャの個々の要素を選ばなければならないので、つまり例を用いて学習しなければならないので、これらの結果は、統計的効率の観点からは、アーキテクチャの深さが非常に重要であることを意味する。