ニューラルネットワークって何かな〜って調べていたら普遍性定理(universal approximation theorem)という面白そうなものを見つけたのでCybenkoさんの有名な論文で証明を追ってみました。日本語でこの定理の証明まで書いてくれているところはざっと見た感じ無かったのでTeX打ちの練習も兼ねてQiitaに纏めてみようってことでこの記事を書きました。この記事ではCybenkoさんの論文を少し一般化した普遍性定理を述べます。証明はほとんどCybenkoさんによる証明に基づいています(一部修正しているくらい)。

この記事の目的は皆さんに普遍性定理の内容と証明を伝えることなのですが、証明に使う数学はそれなりに高級で誰でも読めるように書くのは難しかったので、以下に挙げる3つの分野すべてに少しでも触れたことがある人を読者として想定しています。

• 位相空間論
• 測度論・積分論
• 関数解析学

ただし、詳しく知っていなくても大丈夫なように書いたつもりです。

普遍性定理とは

まず定理の内容を記述するためにいくつかの記号と言葉を定義します。この記事を通して、X⊂Rn$X\subset {\mathbb{R}}^n$をコンパクト連結集合とし、X$X$上の実数値連続関数全体の集合をC(X)$C(X)$で表すことにします。

定義1(sigmoidal関数)
関数 σ:R→R$\sigma :\mathbb{R}\to \mathbb{R}$ が次の条件をみたすとき、sigmoidal関数と呼ぶことにします:

σ(t)→{10(t→+∞)(t→−∞)$$\sigma (t)\to \{\begin{array}{ll}1& (t\to +\mathrm{\infty })\\ 0& (t\to -\mathrm{\infty })\end{array}$$

以下が普遍性定理のステートメントです。

普遍性定理
σ:R→R$\sigma :\mathbb{R}\to \mathbb{R}$ を連続なsigmoidal関数とすると、

G(x)=∑j=1Nαjσ(⟨x,yj⟩+θj)$$G(x)=\sum _{j=1}^N{\alpha }_j\sigma (⟨x,y_j⟩+{\theta }_j)$$

という形をしたX$X$上の関数全体の集合はC(X)$C(X)$で稠密になる。すなわち、任意の f∈C(X)$f\in C(X)$と任意の正数ε$\epsilon$に対して、上の形をした関数G$G$を適当に持ってくれば

∀x∈X,|f(x)−G(x)|<ε$${\displaystyle \mathrm{\forall }x\in X,|f(x)-G(x)|<\epsilon }$$

が成立する。ただしαj∈R,yj∈Rn${\alpha }_j\in \mathbb{R},y_j\in {\mathbb{R}}^n$であり、⟨x,y⟩$⟨x,y⟩$は内積である。

つまり、与えられた連続関数を所望の精度で近似できる入力層、隠れ層1層、出力層の合計3層のニューラルネットワークが必ず存在するよということです(ただし隠れ層のノード数は大きく取らないといけないかもしれない)。この定理の感覚的な理解のためには cfikenさんの記事(ニューラルネットワークにおけるUniversal Approximation Theorem(普遍性定理)について)の「イメージの理解」の節も参考になると思います。この普遍性定理は初めに挙げた分野における基本的かつ重要な定理である、優収束定理、Hahn-Banachの拡張定理、Riesz-Markov-角谷の表現定理、Stone-Weierstrassの定理を使って証明されます。そこで、これらの定理の主張を理解できるようになることを目標にして、以下で定義からそのステートメントまでを見ていくことにしましょう。また、これらの定理の系で、普遍性定理の証明の中で使われるものについても見ていきましょう。十分知ってるよという人は普遍性定理の証明の節に一気に飛んでもらって大丈夫です。なお、これらの定理の証明は『関数解析』(横浜図書、宮島静雄)に大体載っています(定義やステートメントはこの本を参考にしています)。ただし、定理の系のうちこの本に載っていないものなどの証明については後日まとめるつもりです。

優収束定理

ルベーグ式の積分の定義は既に知っているものとします。

優収束定理
(Ω,F,μ)$(\mathrm{\Omega },\mathcal{F},\mu )$を測度空間とする。(fn)$(f_n)$が(Ω,F,μ)$(\mathrm{\Omega },\mathcal{F},\mu )$上の可測関数列で、関数 f$f$に各点収束し、かつある(Ω,F,μ)$(\mathrm{\Omega },\mathcal{F},\mu )$上の可積分関数g$g$が存在して任意のn,x$n,x$に対して|fn(x)|≤g(x)$|f_n(x)|\le g(x)$が成り立つならば、f$f$は可積分で、

limn→∞∫Ωfndμ=∫Ωfdμ$$\underset{n\to \mathrm{\infty }}{lim}{\int }_{\mathrm{\Omega }}{f}_{n}d\mu ={\int }_{\mathrm{\Omega }}fd\mu$$

が成り立つ。

次の系の成立は明らかでしょう。

系(有界収束定理)
(Ω,F,μ)$(\mathrm{\Omega },\mathcal{F},\mu )$を有限測度空間とする。(fn)$(f_n)$が(Ω,F,μ)$(\mathrm{\Omega },\mathcal{F},\mu )$上の可測関数列で、関数 f$f$に各点収束し、かつある正数M$M$が存在して任意のn,x$n,x$に対して|fn(x)|≤M$|f_n(x)|\le M$が成り立つならば、f$f$は可積分で、

limn→∞∫Ωfndμ=∫Ωfdμ$$\underset{n\to \mathrm{\infty }}{lim}{\int }_{\mathrm{\Omega }}{f}_{n}d\mu ={\int }_{\mathrm{\Omega }}fd\mu$$

が成り立つ。

Hahn-Banachの拡張定理

定義2(劣線形汎関数)
V$V$をR$\mathbb{R}$上のベクトル空間とする。写像p:V→R$p:V\to \mathbb{R}$が劣線形であるとは、以下の2つの条件が成り立つことを言います:
(1)∀λ>0,∀x∈V, p(λx)=λp(x)$(1)\mathrm{\forall }\lambda >0,\mathrm{\forall }x\in V,p(\lambda x)=\lambda p(x)$
(2)∀x,y∈V, p(x+y)≤p(x)+p(y)$(2)\mathrm{\forall }x,y\in V,p(x+y)\le p(x)+p(y)$

例えば、ノルム空間においてノルムは劣線形汎関数です。Hahn-Banachの定理は線形部分空間上の線形汎関数は劣線形汎関数に支配されているのであればいい感じに拡張できるよって主張です。正確には以下の通りです。

Hahn-Banachの拡張定理
V$V$をR$\mathbb{R}$上のベクトル空間、W⊂V$W\subset V$を線形部分空間、p:V→R$p:V\to \mathbb{R}$を劣線形汎関数とするとき、線形汎関数f:W→R$f:W\to \mathbb{R}$が∀x∈W, f(x)≤p(x)$\mathrm{\forall }x\in W,f(x)\le p(x)$ をみたすならば、線形汎関数F:V→R$F:V\to \mathbb{R}$であって、W$W$上でF=f$F=f$となり、V$V$上でF≤p$F\le p$となるものが存在する。

優収束定理もそうですが、有限の広がりしか持ち得ないときには都合の良い性質が成り立つことが多いのですね。Hahn-Banachの拡張定理の応用例を1つ見てみましょう(普遍性定理の証明に使います)。

定義3
V,W$V,W$をノルム空間とするとき、写像f:V→W$f:V\to W$が有界であるとは、あるM>0$M>0$ が存在して、∀x∈V, ∥f(x)∥W≤M∥x∥V$\mathrm{\forall }x\in V,\parallel f(x){\parallel }_W\le M\parallel x{\parallel }_V$が成り立つことを言います。

系
V$V$をR$\mathbb{R}$上のノルム空間、W⊂V$W\subset V$を線形部分空間とする。もしW$W$のV$V$における閉包W¯¯¯¯¯ $\overline{W}$がV$V$と一致しなければ、V$V$上の有界線形汎関数f≠0$f\ne 0$で、f=0 (on  W¯¯¯¯¯)$f=0(\mathrm{o}\mathrm{n}\overline{W})$　なるものが存在する。

Riesz-Markov-角谷の表現定理

この節ではまず符号付き測度及びそれによる積分の定義を非負値の測度の知識を前提にして述べます。その後、符号付きBorel測度の定義を述べ、Riesz-Markov-角谷の表現定理の主張を述べます。

定義4(符号付き測度)
(Ω,F)$(\mathrm{\Omega },\mathcal{F})$を可測空間とします。写像φ:F→R$\phi :\mathcal{F}\to \mathbb{R}$ が次の条件をみたすときをφ$\phi$を(Ω,F)$(\mathrm{\Omega },\mathcal{F})$上の符号付き測度と呼ぶことにします:
F$\mathcal{F}$の元の列(An)$(A_n)$が互いに素であるならばφ(⋃∞n=1An)=∑∞n=1φ(An)$\phi (\bigcup _{n=1}^{\mathrm{\infty }}{A}_n)=\sum _{n=1}^{\mathrm{\infty }}\phi (A_n)$となる。

以下の事実に基づき符号付き測度による積分を定義します(Hahn分解などを知っている方は「ん？」となるかもですがちゃんと一致します)。

事実
φ$\phi$を可測空間(Ω,F)$(\mathrm{\Omega },\mathcal{F})$上の符号付き測度とするとき、A∈F$A\in \mathcal{F}$に対して、

φ+(A)=sup{φ(B)∣B∈F,B⊂A}, φ−(A)=−inf{φ(B)∣B∈F,B⊂A}$${\phi }^{+}(A)=sup\{\phi (B)\mid B\in \mathcal{F},B\subset A\},{\phi }^{-}(A)=-inf\{\phi (B)\mid B\in \mathcal{F},B\subset A\}$$

とおくと、φ+,φ−${\phi }^{+},{\phi }^{-}$は(Ω,F)$(\mathrm{\Omega },\mathcal{F})$上の有限測度となり、φ=φ+−φ−$\phi ={\phi }^{+}-{\phi }^{-}$ が成立する。

定義5
φ$\phi$を可測空間(Ω,F)$(\mathrm{\Omega },\mathcal{F})$上の符号付き測度とするとき、f∈L1(Ω,F,φ+)∩L1(Ω,F,φ−)$f\in L^1(\mathrm{\Omega },\mathcal{F},{\phi }^{+})\cap L^1(\mathrm{\Omega },\mathcal{F},{\phi }^{-})$に対して、φ$\phi$に関するf$f$の積分を以下で定めます。

∫Ωfdφ:=∫Ωfdφ+−∫Ωfdφ−$${\int }_{\mathrm{\Omega }}fd\phi :={\int }_{\mathrm{\Omega }}fd{\phi }^{+}-{\int }_{\mathrm{\Omega }}fd{\phi }^{-}$$

Borel測度の定義から正則符号付きBorel測度の定義まで一気に述べてしまいましょう。

定義6(Borel測度)
(Ω,O)$(\mathrm{\Omega },\mathcal{O})$を位相空間とし、F$\mathcal{F}$をO$\mathcal{O}$を含む最小のΩ$\mathrm{\Omega }$上の完全加法族とします。このとき可測空間(Ω,F)$(\mathrm{\Omega },\mathcal{F})$上の測度を(Ω,O)$(\mathrm{\Omega },\mathcal{O})$上のBorel測度と呼ぶことにします。

定義7(正則Borel測度)
定義6と同じ設定とします。位相空間(Ω,O)$(\mathrm{\Omega },\mathcal{O})$上のBorel測度μ$\mu$は以下の条件をみたすとき正則であると言われます:

∀A∈F, μ(A)=inf{μ(U)∣U⊃A,open}=sup{μ(K)∣K⊂A,cpt.}.$$\mathrm{\forall }A\in \mathcal{F},\mu (A)=inf\{\mu (U)\mid U\supset A,\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{n}\}=sup\{\mu (K)\mid K\subset A,\mathrm{c}\mathrm{p}\mathrm{t}.\}.$$

定義8(正則符号付きBorel測度)
定義6と同じ設定とします。(Ω,F)$(\mathrm{\Omega },\mathcal{F})$上の符号付き測度φ:F→R$\phi :\mathcal{F}\to \mathbb{R}$ はφ+,φ−${\phi }^{+},{\phi }^{-}$がともに(Ω,F)$(\mathrm{\Omega },\mathcal{F})$上の正則Borel測度になるとき、(Ω,F)$(\mathrm{\Omega },\mathcal{F})$上の正則符号付き測度と呼ばれます。

なお、文脈によってはS$S$に入っている位相を明示せず単にS$S$上の正則符号付き測度と呼ぶこともあります。以上の定義のもと以下が成り立ちます。個人的にはかなり好きな定理です。

Riesz-Markov-角谷の表現定理
S$S$をコンパクトHausdorff空間とし、C(S)$C(S)$をS$S$上の実数値連続関数全体の集合とするとき、任意の有界線形汎関数φ:C(S)→R$\phi :C(S)\to \mathbb{R}$に対して、S$S$上の正則符号付きBorel測度μ$\mu$であって、

∀f∈C(S), φ(f)=∫Sfdμ$$\mathrm{\forall }f\in C(S),\phi (f)={\int }_{S}fd\mu$$

をみたすものが一意的に存在する。

Stone-Weierstrassの定理

この節ではS$S$をコンパクトHausdorff空間とし、C(S)$C(S)$をS$S$上の実数値連続関数全体の集合とします。C(S)$C(S)$は∥f∥=sup{f(x)∣x∈S}$\parallel f\parallel =sup\{f(x)\mid x\in S\}$によりノルム空間になります。

定義(C(S)$C(S)$の部分代数)
A⊂C(S)$A\subset C(S)$が部分代数であるとは、A$A$がC(S)$C(S)$の線形部分空間であり、かつ任意のf,g∈A$f,g\in A$について積fg$fg$がA$A$の元になることを言います。

C(S)$C(S)$の部分集合A$A$が与えられたとき、A$A$を含む最小の部分代数が存在します(A$A$を含む部分代数全体の共通部分を取ればよい)。それをA$A$で生成された部分代数と呼ぶことにしましょう。Stone-Weierstrassの定理は生成された部分代数の稠密性について述べたものです。

Stone-Weierstrassの定理
A⊂C(S)$A\subset C(S)$が次の2つの条件をみたしているとする。
(1)恒等的に1を取る関数1$\mathbf{1}$はA$A$に属する
(2)任意の相異なるx,y∈S$x,y\in S$に対して、f(x)≠f(y)$f(x)\ne f(y)$なるf∈A$f\in A$が存在する
このときA$A$が生成する部分代数の閉包はC(S)$C(S)$と一致する。すなわち、任意のf∈C(S)$f\in C(S)$とε>0$\epsilon >0$に対して、A$A$が生成する部分代数の元g$g$で、∥f−g∥<ε$\parallel f-g\parallel <\epsilon$をみたすものが取れる。

1つ具体例を見てみましょう。

例
S⊂R$S\subset \mathbb{R}$をコンパクト集合とするとき、(1変数)多項式関数をS$S$上に制限したもの全体の集合をA$A$とおくと、明らかにA$A$は上の2条件をみたすのでStone-Weierstrassの定理からA$A$が生成する部分代数の閉包はC(S)$C(S)$と一致します。ところがA$A$は部分代数なのでA$A$が生成する部分代数はA$A$になります。よって、S上の連続関数は多項式により一様近似できます。

次に系と言うには些かギャップがありますがStone-Weierstrassの定理から以下がわかります(Fourier変換の一般論から示すこともできます)。

系
S⊂Rn$S\subset {\mathbb{R}}^n$とするとき、μ$\mu$を部分空間S$S$上の正則符号付きBorel測度とすると、

(∀y∈Rn,∫Sexp(i⟨x,y⟩)dμ(x)=0)⇒μ=0$$(\mathrm{\forall }y\in {\mathbb{R}}^n,{\int }_S\exp (i⟨x,y⟩)d\mu (x)=0)\Rightarrow \mu =0$$

が成り立つ。

普遍性定理の証明

普遍性定理を2つの補題に分けて証明します。まず補題の主張を述べるために言葉と記号の定義をしましょう。位相空間(X,O)$(X,\mathcal{O})$をRn${\mathbb{R}}^n$の部分空間、すなわちO={X∩U∣U⊂Rn,open}$\mathcal{O}=\{X\cap U\mid U\subset {\mathbb{R}}^n,\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{n}\}$とし、(X,O)$(X,\mathcal{O})$上の正則符号付きBorel測度全体の集合をM(X)$M(X)$で表すことにします。

定義5(discriminatory関数)
関数 σ:R→R$\sigma :\mathbb{R}\to \mathbb{R}$ が次の条件をみたすとき、discriminatory関数と呼ぶことにします:

∀μ∈M(X),(∀y∈Rn,θ∈R,∫Xσ(⟨x,y⟩+θ)dμ(x)=0)⇒μ=0.$$\mathrm{\forall }\mu \in M(X),(\mathrm{\forall }y\in {\mathbb{R}}^n,\theta \in \mathbb{R},{\int }_X\sigma (⟨x,y⟩+\theta )d\mu (x)=0)\Rightarrow \mu =0.$$

この定義のもとで以下の2つの命題が成り立ちます。

補題1
σ:R→R$\sigma :\mathbb{R}\to \mathbb{R}$ を連続なdiscriminatory関数とすると、

G(x)=∑j=1Nαjσ(⟨x,yj⟩+θj)(1)$$\begin{array}{}\text{(1)}& G(x)=\sum _{j=1}^N{\alpha }_j\sigma (⟨x,y_j⟩+{\theta }_j)\end{array}$$

という形をしたX$X$上の関数全体の集合はC(X)$C(X)$で稠密になる。すなわち、任意の f∈C(X)$f\in C(X)$と任意の正数ϵ$ϵ$に対して、上の形の関数G$G$を適当に持ってくれば

∀x∈X,|f(x)−G(x)|<ϵ$${\displaystyle \mathrm{\forall }x\in X,|f(x)-G(x)|<ϵ}$$

が成立する。

補題2
有界で可測なsigmoidal関数σ$\sigma$はdiscriminatory関数である。特に連続なsigmoidal関数はdiscriminatory関数である。

2つの補題から普遍性定理が導かれることは明らかでしょう。以下でこれらの補題の証明をしていきます。

補題1の証明

S$S$を(1)の形をしたX$X$上の関数全体の集合とします。明らかにS$S$は C(X)$C(X)$ の部分空間です。補題1の主張はS¯¯¯=C(X)$\overline{S}=C(X)$が成り立つというものです。そこで、S¯¯¯≠C(X)$\overline{S}\ne C(X)$を仮定してみましょう。すると、Hahn-Banachの拡張定理(の系)により、C(X)$C(X)$上の有界線形汎関数L≠0$L\ne 0$で、L=0 (on  S¯¯¯)$L=0(\mathrm{o}\mathrm{n}\overline{S})$　なるものが取れます。X$X$はコンパクトHausdorff空間ですので、Riesz-Markov-角谷の表現定理から、μ∈M(X)$\mu \in M(X)$で、

をみたすものが取れます。任意のy∈Rn,θ∈R$y\in {\mathbb{R}}^n,\theta \in \mathbb{R}$に対して、Rn∋x↦σ(⟨x,y⟩+θ)∈R${\mathbb{R}}^n\ni x\mapsto \sigma (⟨x,y⟩+\theta )\in \mathbb{R}$はS$S$に属するので、となります。ゆえに、σ$\sigma$がdiscriminatory関数であることからμ=0$\mu =0$となり、したがってL=0$L=0$となりますが、これはL≠0$L\ne 0$に反します。よって、S¯¯¯=C(X)$\overline{S}=C(X)$でなければなりません。

補題2の証明

後半については連続性から可測性が、sigmoidal関数であることと連続性から有界性が出てくるので成立します。前半を証明していきましょう。
μ∈M(X)$\mu \in M(X)$を任意にとり固定します。そして、

が成り立つと仮定しましょう。このとき、μ=0$\mu =0$を示すのが目標となります。さて、いま、σ$\sigma$はsigmoidalなので、任意のx,y∈Rn,φ,θ∈R$x,y\in {\mathbb{R}}^n,\phi ,\theta \in \mathbb{R}$に対して、λ→+∞$\lambda \to +\mathrm{\infty }$のとき、
となります(⟨x,y⟩+θ=0$⟨x,y⟩+\theta =0$のときは任意のλ∈R$\lambda \in \mathbb{R}$に対してσ(λ(⟨x,y⟩+θ)+φ)=σ(φ)$\sigma (\lambda (⟨x,y⟩+\theta )+\phi )=\sigma (\phi )$です)。そこで、とおき、

とおくと、(2)とσ$\sigma$の有界性及びμ$\mu$の有限性により、
となります(2つ目の等号は有界収束定理による)。ここで、R$\mathbb{R}$上の有界な可測関数h$h$に対して、線形汎関数F$F$をにより定めます。h=χ[θ,∞)$h={\chi }_{[\theta ,\mathrm{\infty })}$(定義関数)と取ると、となりますが、(3)においてφ→+∞$\phi \to +\mathrm{\infty }$とするとμ(Πy,−θ)+μ(Hy,−θ)=0$\mu \left({\mathrm{\Pi }}_{y,-\theta }\right)+\mu \left(H_{y,-\theta }\right)=0$を得るのでF(h)=0$F(h)=0$となります。同様にφ→−∞$\phi \to -\mathrm{\infty }$とするとμ(Hy,−θ)=0$\mu \left(H_{y,-\theta }\right)=0$を得るのでF(χ(θ,∞))=0$F({\chi }_{(\theta },\mathrm{\infty }))=0$となります。このこととF$F$の線形性から任意のR$\mathbb{R}$の区間J$J$についてF(χJ)=0$F({\chi }_J)=0$となり、したがって有限個のR$\mathbb{R}$の区間の定義関数の線形結合をF$F$で写すと0$0$になります。以下、一旦y∈Rn$y\in {\mathbb{R}}^n$を固定します。このときA={⟨x,y⟩∣x∈X}$A=\{⟨x,y⟩\mid x\in X\}$はR$\mathbb{R}$のコンパクト連結集合となります。何故ならA$A$はコンパクト連結集合X$X$の連続写像による像だからです。したがってA$A$は有界閉区間になるのでA$A$上の任意の連続g$g$はR$\mathbb{R}$の区間の定義関数たちの線形結合∑Nk=1akχJk$\sum _{k=1}^N{a}_k{\chi }_{J_k}$により一様近似できます。すなわち任意の正数ε$\epsilon$に対して、適当にak,Jk$a_k,J_k$を取れば、とできます。何故なら、コンパクト集合上の連続関数は一様連続なので、任意のε>0$\epsilon >0$に対して、δ>0$\delta >0$を適当に取れば、が成り立ちます。そこで、一つの区間の幅がδ$\delta$に収まるような分割A=∑Nk=1Jk$A=\sum _{k=1}^N{J}_k$を取り、各k$k$に対してxk∈Jk$x_k\in J_k$を取ってくれば、となります。したがって、このことから、
とできます。ただし|μ|=μ++μ−$\left|\mu \right|={\mu }^{+}+{\mu }^{-}$です。よって、|μ|(In)$\left|\mu \right|(I_n)$がε$\epsilon$に依存しない定数(有限値)であることとε$\epsilon$の任意性から、F(g)=0$F(g)=0$がわかります。特にcos(x),sin(x)$\cos (x),\sin (x)$についてもこれが成立するので、がわかります。よって、y∈R$y\in \mathbb{R}$は任意だったのでStone-Weierstrassの定理(の系)からμ=0$\mu =0$となります。これが示したいことでした。

おわりに

関数解析の基本的な定理からこういった面白い定理が導かれる様は痛快でしたね！
普通にStone-Weierstrass使って多項式近似でよくない？とか肝心の近似アルゴリズムがない(普遍性定理はあくまで近似可能性を保証しているだけである)から実務的には何の役にも立たんなとか色々な感想があると思いますが、あの形の関数で任意の連続関数が一様近似可能できるのは個人的に面白いなと思いました。なお、σ$\sigma$が違う性質を持つ場合にも同様のことが成り立つことも現在は知られているようです。
Cybenkoさんの論文ではこの記事で紹介した普遍性定理を証明したあと、分類問題への応用を述べている(そして、その中にもLusinの定理という測度論の定理を用いている)ので興味を持たれた方は是非読んでみてください。幸せな気持ちになれること間違いなしです。
そういえば、ニューラルネットワークには積分表現理論なるものもあって、そこでも関数解析が力を発揮しているそうです。いつか勉強したいな〜。