ニューラルネットワークって何かな〜って調べていたら普遍性定理(universal approximation theorem)という面白そうなものを見つけたのでCybenkoさんの有名な論文で証明を追ってみました。日本語でこの定理の証明まで書いてくれているところはざっと見た感じ無かったのでTeX打ちの練習も兼ねてQiitaに纏めてみようってことでこの記事を書きました。この記事ではCybenkoさんの論文を少し一般化した普遍性定理を述べます。証明はほとんどCybenkoさんによる証明に基づいています(一部修正しているくらい)。
この記事の目的は皆さんに普遍性定理の内容と証明を伝えることなのですが、証明に使う数学はそれなりに高級で誰でも読めるように書くのは難しかったので、以下に挙げる3つの分野すべてに少しでも触れたことがある人を読者として想定しています。
- 位相空間論
- 測度論・積分論
- 関数解析学
ただし、詳しく知っていなくても大丈夫なように書いたつもりです。
2022/5/21追記
私の修士論文( Universal Approximation Theorem for Neural Networks ) で、この記事の内容をさらに深めた、下表の結果の証明をまとめています。ReLUなど非有界な活性化関数を含む関数のクラスで万能近似定理が成り立つことも詳細に解説しています。また、ニューラルネットワークの万能近似定理だけでなく、その近似レート(中間ユニット数と近似誤差の関係)やBarron Spaceについても記述しています。なお、タイトルは英語ですが本文は日本語です。ぜひご覧ください！
普遍性定理とは
まず定理の内容を記述するためにいくつかの記号と言葉を定義します。この記事を通して、$X \subset \mathbb{R}^n$をコンパクト連結集合とし、$X$上の実数値連続関数全体の集合を$C(X)$で表すことにします。
定義1(sigmoidal関数)
関数 $\sigma : \mathbb{R} \rightarrow \mathbb{R}$ が次の条件をみたすとき、sigmoidal関数と呼ぶことにします:
$$
\sigma(t) \rightarrow
\begin{cases}
1 &\quad (t \rightarrow +\infty) \\
0 &\quad (t \rightarrow -\infty)
\end{cases}
$$
以下が普遍性定理のステートメントです。
普遍性定理
$\sigma : \mathbb{R} \rightarrow \mathbb{R}$ を連続なsigmoidal関数とすると、$$G(x) = \sum_{j = 1}^{N}{\alpha_j \sigma(\left< x, y_j \right> + \theta_j)} $$という形をした$X$上の関数全体の集合は$C(X)$で稠密になる。すなわち、任意の $f \in C(X)$と任意の正数$\varepsilon$に対して、上の形をした関数$G$を適当に持ってくれば$$\displaystyle{\forall x \in X,\left|f(x) - G(x) \right| < \varepsilon}$$が成立する。ただし$\alpha_j \in \mathbb{R},y_j \in \mathbb{R}^n$であり、$\left< x, y \right>$は内積である。
つまり、与えられた連続関数を所望の精度で近似できる入力層、隠れ層1層、出力層の合計3層のニューラルネットワークが必ず存在するよということです(ただし隠れ層のノード数は大きく取らないといけないかもしれない)。この定理の感覚的な理解のためには cfikenさんの記事(ニューラルネットワークにおけるUniversal Approximation Theorem(普遍性定理)について)の「イメージの理解」の節も参考になると思います。この普遍性定理は初めに挙げた分野における基本的かつ重要な定理である、優収束定理、Hahn-Banachの拡張定理、Riesz-Markov-角谷の表現定理、Stone-Weierstrassの定理を使って証明されます。そこで、これらの定理の主張を理解できるようになることを目標にして、以下で定義からそのステートメントまでを見ていくことにしましょう。また、これらの定理の系で、普遍性定理の証明の中で使われるものについても見ていきましょう。十分知ってるよという人は普遍性定理の証明の節に一気に飛んでもらって大丈夫です。なお、これらの定理の証明は『関数解析』(横浜図書、宮島静雄)に大体載っています(定義やステートメントはこの本を参考にしています)。ただし、定理の系のうちこの本に載っていないものなどの証明については後日まとめるつもりです。
優収束定理
ルベーグ式の積分の定義は既に知っているものとします。
優収束定理
$(\Omega,\mathscr{F},\mu)$を測度空間とする。$(f_n)$が$(\Omega,\mathscr{F},\mu)$上の可測関数列で、関数 $f$に各点収束し、かつある$(\Omega,\mathscr{F},\mu)$上の可積分関数$g$が存在して任意の$n,x$に対して$\left|f_n(x)\right| \leq g(x)$が成り立つならば、$f$は可積分で、$$\lim_{n \rightarrow \infty}{\int_{\Omega}{f_n}{d\mu}} = \int_{\Omega}{f}{d\mu}$$が成り立つ。
次の系の成立は明らかでしょう。
系(有界収束定理)
$(\Omega,\mathscr{F},\mu)$を有限測度空間とする。$(f_n)$が$(\Omega,\mathscr{F},\mu)$上の可測関数列で、関数 $f$に各点収束し、かつある正数$M$が存在して任意の$n,x$に対して$\left|f_n(x)\right| \leq M$が成り立つならば、$f$は可積分で、$$\lim_{n \rightarrow \infty}{\int_{\Omega}{f_n}{d\mu}} = \int_{\Omega}{f}{d\mu}$$が成り立つ。
Hahn-Banachの拡張定理
定義2(劣線形汎関数)
$V$を$\mathbb{R}$上のベクトル空間とする。写像$p : V \rightarrow \mathbb{R}$が劣線形であるとは、以下の2つの条件が成り立つことを言います:
$(1)\forall \lambda > 0,\forall x \in V, \ p(\lambda x) = \lambda p(x)$
$(2)\forall x,y \in V, \ p(x+y) \leq p(x)+p(y)$
例えば、ノルム空間においてノルムは劣線形汎関数です。Hahn-Banachの定理は線形部分空間上の線形汎関数は劣線形汎関数に支配されているのであればいい感じに拡張できるよって主張です。正確には以下の通りです。
Hahn-Banachの拡張定理
$V$を$\mathbb{R}$上のベクトル空間、$W \subset V$を線形部分空間、$p : V \rightarrow \mathbb{R}$を劣線形汎関数とするとき、線形汎関数$f : W \rightarrow \mathbb{R}$が$\forall x \in W,\ f(x) \leq p(x)$ をみたすならば、線形汎関数$F : V \rightarrow \mathbb{R}$であって、$W$上で$F = f$となり、$V$上で$F \leq p$となるものが存在する。
優収束定理もそうですが、有限の広がりしか持ち得ないときには都合の良い性質が成り立つことが多いのですね。Hahn-Banachの拡張定理の応用例を1つ見てみましょう(普遍性定理の証明に使います)。
定義3
$V,W$をノルム空間とするとき、写像$f : V \rightarrow W$が有界であるとは、ある$M > 0$ が存在して、$\forall x \in V, \ \|f(x) \|_W \leq M \|x\|_V $が成り立つことを言います。
系
$V$を$\mathbb{R}$上のノルム空間、$W \subset V$を線形部分空間とする。もし$W$の$V$における閉包$\overline{W} \ $が$V$と一致しなければ、$V$上の有界線形汎関数$f \neq 0$で、$f = 0 \ (\mathrm{on} \ \ \overline{W})$ なるものが存在する。
Riesz-Markov-角谷の表現定理
この節ではまず符号付き測度及びそれによる積分の定義を非負値の測度の知識を前提にして述べます。その後、符号付きBorel測度の定義を述べ、Riesz-Markov-角谷の表現定理の主張を述べます。
定義4(符号付き測度)
$(\Omega,\mathscr{F})$を可測空間とします。写像$\varphi : \mathscr{F} \rightarrow \mathbb{R}$ が次の条件をみたすときを$\varphi$を$(\Omega,\mathscr{F})$上の符号付き測度と呼ぶことにします:
$\mathscr{F}$の元の列$(A_n)$が互いに素であるならば$\varphi(\bigcup_{n=1}^{\infty}{A_n}) = \sum_{n=1}^{\infty}{\varphi(A_n)}$となる。
以下の事実に基づき符号付き測度による積分を定義します(Hahn分解などを知っている方は「ん？」となるかもですがちゃんと一致します)。
事実
$\varphi$を可測空間$(\Omega,\mathscr{F})$上の符号付き測度とするとき、$A \in \mathscr{F}$に対して、
$$
\varphi^{+}(A) = \sup \{\varphi(B) \mid B \in \mathscr{F},B \subset A\},\
\varphi^{-}(A) = -\inf \{\varphi(B) \mid B \in \mathscr{F},B \subset A\}
$$とおくと、$\varphi^{+},\varphi^{-}$は$(\Omega,\mathscr{F})$上の有限測度となり、$\varphi = \varphi^{+} - \varphi^{-}$ が成立する。
定義5
$\varphi$を可測空間$(\Omega,\mathscr{F})$上の符号付き測度とするとき、$f \in L^1(\Omega,\mathscr{F},\varphi^{+}) \cap L^1(\Omega,\mathscr{F},\varphi^{-})$に対して、$\varphi$に関する$f$の積分を以下で定めます。 $$\int_{\Omega}{f}{d\varphi} := \int_{\Omega}{f}{d\varphi^{+}} - \int_{\Omega}{f}{d\varphi^{-}}$$
Borel測度の定義から正則符号付きBorel測度の定義まで一気に述べてしまいましょう。
定義6(Borel測度)
$(\Omega,\mathscr{O})$を位相空間とし、$\mathscr{F}$を$\mathscr{O}$を含む最小の$\Omega$上の完全加法族とします。このとき可測空間$(\Omega,\mathscr{F})$上の測度を$(\Omega,\mathscr{O})$上のBorel測度と呼ぶことにします。
定義7(正則Borel測度)
定義6と同じ設定とします。位相空間$(\Omega,\mathscr{O})$上のBorel測度$\mu$は以下の条件をみたすとき正則であると言われます:
$$\forall A \in \mathscr{F},\ \mu(A) = \inf \{\mu(U) \mid U \supset A,\mathrm{open}\} = \sup \{\mu(K) \mid K \subset A,\mathrm{cpt.}\}.$$
定義8(正則符号付きBorel測度)
定義6と同じ設定とします。$(\Omega,\mathscr{F})$上の符号付き測度$\varphi : \mathscr{F} \rightarrow \mathbb{R}$ は$\varphi^{+},\varphi^{-}$がともに$(\Omega,\mathscr{F})$上の正則Borel測度になるとき、$(\Omega,\mathscr{F})$上の正則符号付き測度と呼ばれます。
なお、文脈によっては$S$に入っている位相を明示せず単に$S$上の正則符号付き測度と呼ぶこともあります。以上の定義のもと以下が成り立ちます。個人的にはかなり好きな定理です。
Riesz-Markov-角谷の表現定理
$S$をコンパクトHausdorff空間とし、$C(S)$を$S$上の実数値連続関数全体の集合とするとき、任意の有界線形汎関数$\varphi : C(S) \rightarrow \mathbb{R}$に対して、$S$上の正則符号付きBorel測度$\mu$であって、$$\forall f \in C(S),\ \varphi(f) = \int_{S}{f}{d\mu}$$をみたすものが一意的に存在する。
Stone-Weierstrassの定理
この節では$S$をコンパクトHausdorff空間とし、$C(S)$を$S$上の実数値連続関数全体の集合とします。$C(S)$は$\|f\| = \sup \{ f(x) \mid x \in S\}$によりノルム空間になります。
定義($C(S)$の部分代数)
$A \subset C(S)$が部分代数であるとは、$A$が$C(S)$の線形部分空間であり、かつ任意の$ f,g \in A$について積$ fg $が$A$の元になることを言います。
$C(S)$の部分集合$A$が与えられたとき、$A$を含む最小の部分代数が存在します($A$を含む部分代数全体の共通部分を取ればよい)。それを$A$で生成された部分代数と呼ぶことにしましょう。Stone-Weierstrassの定理は生成された部分代数の稠密性について述べたものです。
Stone-Weierstrassの定理
$A \subset C(S)$が次の2つの条件をみたしているとする。
(1)恒等的に1を取る関数$\mathbf{1}$は$A$に属する
(2)任意の相異なる$x,y \in S$に対して、$f(x) \neq f(y)$なる$f \in A$が存在する
このとき$A$が生成する部分代数の閉包は$C(S)$と一致する。すなわち、任意の$f \in C(S)$と$\varepsilon > 0$に対して、$A$が生成する部分代数の元$g$で、$\|f-g\| < \varepsilon$をみたすものが取れる。
1つ具体例を見てみましょう。
例
$S \subset \mathbb{R}$をコンパクト集合とするとき、(1変数)多項式関数を$S$上に制限したもの全体の集合を$A$とおくと、明らかに$A$は上の2条件をみたすのでStone-Weierstrassの定理から$A$が生成する部分代数の閉包は$C(S)$と一致します。ところが$A$は部分代数なので$A$が生成する部分代数は$A$になります。よって、S上の連続関数は多項式により一様近似できます。
次に系と言うには些かギャップがありますがStone-Weierstrassの定理から以下がわかります(Fourier変換の一般論から示すこともできます)。
系
$S \subset \mathbb{R}^n$とするとき、$\mu$を部分空間$S$上の正則符号付きBorel測度とすると、$$\left(\forall y \in \mathbb{R}^n,\int_{S}{\exp(i \left<x,y\right >)}{d\mu(x)} = 0 \right) \Rightarrow \mu = 0$$が成り立つ。
普遍性定理の証明
普遍性定理を2つの補題に分けて証明します。まず補題の主張を述べるために言葉と記号の定義をしましょう。位相空間$(X,\mathscr{O})$を$\mathbb{R}^n$の部分空間、すなわち$\mathscr{O} = \{X \cap U \mid U \subset \mathbb{R}^n,\mathrm{open}\}$とし、$(X,\mathscr{O})$上の正則符号付きBorel測度全体の集合を$M(X)$で表すことにします。
定義5(discriminatory関数)
関数 $\sigma : \mathbb{R} \rightarrow \mathbb{R}$ が次の条件をみたすとき、discriminatory関数と呼ぶことにします:
$$\forall \mu \in M(X),\left(\forall y \in \mathbb{R}^n,\theta \in \mathbb{R},\int_{X}{\sigma \left(\left< x, y \right> + \theta \right)}{d\mu(x)} = 0 \right) \Rightarrow \mu = 0.$$
この定義のもとで以下の2つの命題が成り立ちます。
補題1
$\sigma : \mathbb{R} \rightarrow \mathbb{R}$ を連続なdiscriminatory関数とすると、$$G(x) = \sum_{j = 1}^{N}{\alpha_j \sigma \left(\left< x, y_j \right> + \theta_j \right)} \tag{1}$$という形をした$X$上の関数全体の集合は$C(X)$で稠密になる。すなわち、任意の $f \in C(X)$と任意の正数$\epsilon$に対して、上の形の関数$G$を適当に持ってくれば$$\displaystyle{\forall x \in X,\left|f(x) - G(x) \right| < \epsilon}$$が成立する。
補題2
有界で可測なsigmoidal関数$\sigma$はdiscriminatory関数である。特に連続なsigmoidal関数はdiscriminatory関数である。
2つの補題から普遍性定理が導かれることは明らかでしょう。以下でこれらの補題の証明をしていきます。
補題1の証明
$S$を(1)の形をした$X$上の関数全体の集合とします。明らかに$S$は $C(X)$ の部分空間です。補題1の主張は$\overline{S} = C(X)$が成り立つというものです。そこで、$\overline{S} \neq C(X)$を仮定してみましょう。すると、Hahn-Banachの拡張定理(の系)により、$C(X)$上の有界線形汎関数$L \neq 0$で、$L = 0 \ (\mathrm{on} \ \ \overline{S})$ なるものが取れます。$X$はコンパクトHausdorff空間ですので、Riesz-Markov-角谷の表現定理から、$\mu \in M(X)$で、$$\forall f \in C(X),\ L(f) = \int_{X}{f}{d\mu}$$をみたすものが取れます。任意の$y \in \mathbb{R}^n,\theta \in \mathbb{R}$に対して、$\mathbb{R}^n \ni x \mapsto \sigma(\left< x, y \right> + \theta) \in \mathbb{R}$は$S$に属するので、$$\int_{X}{\sigma(\left< x, y \right> + \theta)}{d\mu} = 0$$となります。ゆえに、$\sigma$がdiscriminatory関数であることから$\mu = 0$となり、したがって$L = 0$となりますが、これは$L \neq 0$に反します。よって、$\overline{S} = C(X)$でなければなりません。
補題2の証明
後半については連続性から可測性が、sigmoidal関数であることと連続性から有界性が出てくるので成立します。前半を証明していきましょう。
$\mu \in M(X)$を任意にとり固定します。そして、$$\forall y \in \mathbb{R}^n,\theta \in \mathbb{R},\int_{X}{\sigma \left(\left< x, y \right> + \theta \right)}{d\mu(x)} = 0 \tag{2}$$が成り立つと仮定しましょう。このとき、$\mu = 0$を示すのが目標となります。さて、いま、$\sigma$はsigmoidalなので、任意の$x,y \in \mathbb{R}^n,\varphi,\theta \in \mathbb{R}$に対して、$\lambda \rightarrow +\infty$のとき、
$$\sigma(\lambda (\left< x, y \right> + \theta) + \varphi) \rightarrow
\begin{cases}
1 &\quad \mathrm{for} \ \left< x, y \right>+ \theta >0 \\
0 &\quad \mathrm{for} \ \left< x, y \right>+ \theta <0 \\
\sigma(\varphi) &\quad \mathrm{otherwise}
\end{cases}$$ となります($ \left< x, y \right>+ \theta = 0 $のときは任意の$\lambda \in \mathbb{R}$に対して$\sigma(\lambda (\left< x, y \right> + \theta) + \varphi) = \sigma(\varphi)$です)。そこで、
$$
\Pi_{y,\theta} = \left \{ x \in X \mid \left< x, y \right>+ \theta = 0 \right \}, \\
H_{y,\theta} = \left \{ x \in X \mid \left< x, y \right>+ \theta > 0 \right \}
$$
とおき、
$$\gamma(x) =
\begin{cases}
1 &\quad x \in H_{y,\theta} \\
\sigma(\varphi) &\quad x \in \Pi_{y,\theta} \\
0 &\quad \mathrm{otherwise}
\end{cases}$$
とおくと、(2)と$\sigma$の有界性及び$\mu$の有限性により、
$$\begin{align}
0 &= \lim_{\lambda \rightarrow +\infty}{\int_{X}{\sigma(\lambda (\left< x, y \right> + \theta) + \varphi)}{d\mu(x)}} \\
&= \int_{X}{\lim_{\lambda \rightarrow +\infty}\sigma(\lambda (\left< x, y \right> + \theta) + \varphi)}{d\mu(x)} \\
&= \int_{X}{\gamma(x)}{d\mu(x)}\\
&= \sigma(\varphi)\mu\left( \Pi_{y,\theta} \right)+\mu\left( H_{y,\theta} \right)
\end{align} \tag{3}$$となります(2つ目の等号は有界収束定理による)。ここで、$\mathbb{R}$上の有界な可測関数$h$に対して、線形汎関数$F$を$$F(h) = \int_{X}{h(\left< x, y \right>)}{d\mu(x)}$$により定めます。$h = \chi_{[\theta,\infty)}$(定義関数)と取ると、$$F(h) = \int_{X}{h(\left< x, y \right>)}{d\mu(x)} = \mu\left( \Pi_{y,-\theta} \right)+\mu\left( H_{y,-\theta} \right)$$となりますが、(3)において$\varphi \rightarrow +\infty$とすると$\mu\left( \Pi_{y,-\theta} \right)+\mu\left( H_{y,-\theta} \right) = 0$を得るので$F(h) = 0$となります。同様に$\varphi \rightarrow -\infty$とすると$\mu\left( H_{y,-\theta} \right) = 0$を得るので$F(\chi_{(\theta},\infty)) = 0$となります。このことと$F$の線形性から任意の$\mathbb{R}$の区間$J$について$F(\chi_{J}) = 0$となり、したがって有限個の$\mathbb{R}$の区間の定義関数の線形結合を$F$で写すと$0$になります。以下、一旦$y \in \mathbb{R}^n$を固定します。このとき$A = \\{\left< x, y \right> \mid x \in X\\}$は$\mathbb{R}$のコンパクト連結集合となります。何故なら$A$はコンパクト連結集合$X$の連続写像による像だからです。したがって$A$は有界閉区間になるので$A$上の任意の連続$g$は$\mathbb{R}$の区間の定義関数たちの線形結合$\sum_{k=1}^{N}{a_k \chi_{J_k}}$により一様近似できます。すなわち任意の正数$\varepsilon$に対して、適当に$a_k,J_k$を取れば、$$\forall x \in A, \\ \left\| g(x) - \sum_{k=1}^{N}{a_k \chi_{J_k}(x)} \right\| < \varepsilon$$とできます。何故なら、コンパクト集合上の連続関数は一様連続なので、任意の$\varepsilon > 0$に対して、$\delta>0$を適当に取れば、$$\forall x,y \in A, |x-y|<\delta \Rightarrow |g(x)-g(y)|<\varepsilon$$が成り立ちます。そこで、一つの区間の幅が$\delta$に収まるような分割$A = \sum_{k=1}^{N}{J_k}$を取り、各$k$に対して$x_k \in J_k$を取ってくれば、$$\forall x \in A, \ \left| g(x) - \sum_{k=1}^{N}{g(x_k) \chi_{J_k}(x)} \right| < \varepsilon$$となります。したがって、このことから、
$$\begin{align}
\left|F(g)\right| &= \left | \int_{X}{g(\left< x, y \right>)}{d\mu(x)} \right | \\
&= \left | \int_{X}{g(\left< x, y \right>)}{d\mu(x)} - \int_{X}{\sum_{k=1}^{N}{a_k \chi_{J_k}(\left< x, y \right>)}}{d\mu(x)}) \right | \\
&\leq \int_{X}{\left | g(\left< x, y \right>) - \sum_{k=1}^{N}{a_k \chi_{J_k}(\left< x, y \right>)}\right |}{d\left|\mu\right|(x)} \\
&\leq \int_{X}{\varepsilon}{d\mu(x)} = \varepsilon \left|\mu \right|(I_n)
\end{align} $$とできます。ただし$\left|\mu\right| = \mu^{+}+\mu^{-}$です。よって、$\left|\mu\right|(I_n)$が$\varepsilon$に依存しない定数(有限値)であることと$\varepsilon$の任意性から、$F(g) = 0$がわかります。特に$\cos(x),\sin(x)$についてもこれが成立するので、$$0 = \int_{X}{\cos(\left< x, y \right>)+i\sin(\left< x, y \right>)}{d\mu(x)} = \int_{X}{\exp(i\left< x, y \right>)}{d\mu(x)}$$がわかります。よって、$y \in \mathbb{R}$は任意だったのでStone-Weierstrassの定理(の系)から$\mu = 0$となります。これが示したいことでした。
おわりに
関数解析の基本的な定理からこういった面白い定理が導かれる様は痛快でしたね！
普通にStone-Weierstrass使って多項式近似でよくない？とか肝心の近似アルゴリズムがない(普遍性定理はあくまで近似可能性を保証しているだけである)から実務的には何の役にも立たんなとか色々な感想があると思いますが、あの形の関数で任意の連続関数が一様近似可能できるのは個人的に面白いなと思いました。なお、$\sigma$が違う性質を持つ場合にも同様のことが成り立つことも現在は知られているようです。
Cybenkoさんの論文ではこの記事で紹介した普遍性定理を証明したあと、分類問題への応用を述べている(そして、その中にもLusinの定理という測度論の定理を用いている)ので興味を持たれた方は是非読んでみてください。幸せな気持ちになれること間違いなしです。
そういえば、ニューラルネットワークには積分表現理論なるものもあって、そこでも関数解析が力を発揮しているそうです。いつか勉強したいな〜。