表現者の定理の証明 📂機械学習

表現者の定理の証明

定理

インプット集合^{input set} $X \ne \emptyset$ と正定値カーネル $k: X \times X \to \mathbb{R}$ が与えられているとする。学習データセット^{training Dataset}を $$ D := \left\{ \left( x_{i} , y_{i} \right) \right\}_{i=1}^{m} \subset X \times \mathbb{R} $$ とし、再生カーネルヒルベルト空間 $H_{k}$ のクラス $$ \mathcal{F} := \left\{ f \in \mathbb{R}^{X} : f \left( \cdot \right) = \sum_{i=1}^{\infty} \beta_{i} k \left( \cdot , z_{i} \right) \land \beta_{i} \in \mathbb{R} \land z_{i} \in X \land \left\| f \right\| < \infty \right\} \subset H_{k} $$ を上記のように設定する。任意の目的関数 $c : \left( D \times \mathbb{R} \right) ^{m} \to \overline{\mathbb{R}}$ と単調増加関数であるレギュライザー^regulizer $g : \mathbb{R} \to [0,\infty)$ に対して、以下のように正則化された目的汎関数^{regulized Objective Functional} $L : \mathcal{F} \to \overline{\mathbb{R}}$ が定義されているとする。 $$ L (f) := c \left( \left( x_{1}, y_{1}, f \left( x_{1} \right) \right), \cdots , \left( x_{m}, y_{m}, f \left( x_{m} \right) \right) \right) + g \left( \left\| f \right\| \right) $$ ここで、$H_{k}$ のノルム $\left\| \cdot \right\|$ は、$k$ の正定値性^{positive Definiteness}によって次のように与えられる。 $$ \left\| \sum_{i=1}^{\infty} \beta_{i} k \left( \cdot , z_{i} \right) \right\|^{2} := \sum_{i=1}^{\infty} \sum_{j=1}^{\infty} \beta_{i} \beta_{j} k \left( z_{i} , z_{j} \right) \ge 0 $$

$\mathbb{R}$ は実数の集合であり、$\overline{\mathbb{R}}$ は無限大 $\infty$ を含む拡張実数である。
$\mathbb{R}^{X}$ は定義域が $X$ で値域が $\mathbb{R}$ である関数を集めた関数空間である。
レギュライザーとは、データに対する過学習を防ぐためのペナルティ^penalty関数である。
汎関数とは、ざっくり言えば関数自体をインプットとして受け取る関数のことである。

ノンパラメトリック^{nonparametric}

$L (f)$ を最小化する関数 $f \in \mathcal{F}$ は、ある $\left\{ \alpha_{i} \right\}_{i=1}^{m} \subset \mathbb{R}$ に対して次のような形で表される。 $$ f (\cdot) = \sum_{i=1}^{m} \alpha_{i} k \left( \cdot , x_{i} \right) $$

セミパラメトリック^{semiparametric}

$X$ で定義された実関数の集合が $\left\{ \psi_{p} : X \to \mathbb{R} \right\}_{p=1}^{M}$ に対して行列 $\left( \psi_{p} \left( x_{i} \right) \right)_{ip}$ のランクが $M$ であるとする。すると、$f \in \mathcal{F}$ と $h \in \span \left\{ \psi_{p} \right\}$ に対して $$ c \left( \left( x_{1}, y_{1}, \tilde{f} \left( x_{1} \right) \right) , \cdots , \left( x_{m}, y_{m}, \tilde{f} \left( x_{m} \right) \right) \right) + g \left( \left\| f \right\| \right) $$ を最小化する $\tilde{f} = f + h$ は、ある $\left\{ \alpha_{i} \right\}_{i=1}^{m}, \left\{ \beta_{p} \right\}_{p=1}^{M} \subset \mathbb{R}$ に対して次のような形で表される。 $$ \tilde{f} (\cdot) = \sum_{i=1}^{m} \alpha_{i} k \left( \cdot , x_{i} \right) + \sum_{p=1}^{M} \beta_{p} \psi_{p} (\cdot) $$

説明

可能であれば、以下の二つのポストを先に読むことをお勧めする:

表現者

表現者定理^{representer theorem}は、古典的な機械学習、特にサポートベクターマシンの文脈で最も重要な定理の一つとして、与えられたデータに対して私たちが近似しようとしている目的関数 $f$ が適切なカーネル $k$ に対して $$ f (\cdot) = \sum_{i=1}^{m} \alpha_{i} k \left( \cdot , x_{i} \right) $$ のような形で表されるという強力な定理である。ここでカーネルのインプットの一つが $x_{i}$ で固定された関数 $$ k \left( \cdot , x_{i} \right) = \phi \left( x_{i} \right) (\cdot)\in H_{k} $$ を表現者^representerと呼ぶ。これにより、表現者定理は「再生カーネルヒルベルト空間で学習データに適合した^fitted任意の関数は、表現者たちの有限な線形結合で表すことができる」と要約することができる。特に、非線形回帰のためのサポートベクターマシンのカーネルトリックは、これに正確に合致している。

これはディープラーニングとシーベンコの定理の関係に似ている。

データサイエンスの文脈では、表現者 $\phi \left( x_{i} \right) (\cdot)$ はフィーチャーマップ^{feature Map}とも呼ばれ、任意のデータ $X$ を私たちがその特徴^featureを知ることができるヒルベルト空間に移し、その有限な和で私たちが求める関数を表現できるということは、これまで私たちが学んできた多くの機械学習技術がなぜ機能してきたのかを正当化する。もちろん、数学的な保証がなく

てもそれらの技術はそれ自体で有効であるが、表現者定理があることで、それらの技術が理論的な基盤を築くことになるという点で非常に重要である。

目的関数とレギュライザー

定理のステートメントでは、目的関数 $c$ とレギュライザー $g$ を非常に一般的に定義しているが、実際には多くの場合、$c$ はデータと $f$ の適合度を測る平均残差二乗、つまり $$ c = {{ 1 } \over { m }} \sum_{i=1}^{n} \left( y_{i} - f \left( x_{i} \right) \right)^{2} $$ と見なし、$g$ は二乗セミノルムペナルティ $g \left( \left\| f \right\| \right) = \lambda \left\| f \right\|^{2}$ と見なしても問題ない¹。

注意すべき点は、この式の形や単語の意味だけを見て目的関数とレギュライザーを区別してはいけないということである。表現者定理の最も代表的な応用がサポートベクターマシンであるが、ソフトマージンを許容するソフトマージンSVMで扱う最小化問題は次のようである。 $$ \begin{matrix} \text{Minimize} & {{ 1 } \over { 2 }} \left\| \mathbf{w} \right\|_{2}^{2} + \lambda \sum_{k=1}^{n} \xi_{k} \\ \text{subject to} & \left| f \left( \mathbf{x}_{k} \right) \right| \ge 1 - \xi_{k} \\ & \xi_{k} \ge 0 \end{matrix} \\ k = 1, \cdots , n $$

ここで、最適化自体だけを考えた場合、目的関数は実際には $$ {{ 1 } \over { 2 \lambda }} \left\| \mathbf{w} \right\|_{2}^{2} + \sum_{k=1}^{n} \xi_{k} $$ と変わらず、この場合はデータとの乖離を考える $\sum_{k=1}^{n} \xi_{k}$ が $c$ であり、サポートベクターマシンの超平面 $f (\mathbf{x}) = \mathbf{w}^{T} + b$ から導かれる ${{ 1 } \over { 2 \lambda }} \left\| \mathbf{w} \right\|_{2}^{2}$ が $g$ として読まれるべきである。この最適化の意味を数学に置くか機械学習に置くかによって混乱することがあるが、

数学の色が強い人はSVMを「まず線形回帰を終えてから例外を設けるもの」と見なし、$\left\| \mathbf{w} \right\|_{2}^{2}$ を最初に最小化しようとする一方で、
データサイエンスの色が強い人はSVMを「まずデータをうまく分類し、その中で最もマージンの大きな超平面を見つけるもの」と見なし、$\sum_{k=1}^{n} \xi_{k}$ を最初に最小化しようとするためである。

どちらの視点も十分に共感できるものであり、表現者定理の応用がSVMだけでないことを考えると、ここでは暗記術のようなものを探そうとせず、問題に応じて能動的に考え受け入れる必要がある。

証明 ²

参考文献にあるように、ノンパラメトリック表現者定理のみを証明する。

Part 1. $f = \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) + v$

再生カーネルの定義: 関数 $k : X \times X \to \mathbb{C}$ が以下の二つの条件を満たす場合、$H$ の再生カーネル^{reproducing Kernel}と言う。
(i): 表現者^representer: すべての $x \in X$ に対して $$ k \left( \cdot , x \right) \in H $$
(ii) 再生性質^{reproducing Property}: すべての $x \in X$ とすべての $f \in H$ に対して $$ \left< f , k \left( \cdot , x \right) \right> = f(x) = \delta_{x} (f) $$ 特に、すべての $x_{1} , x_{2} \in X$ に対して以下が成り立つ。 $$ k \left( x_{1} , x_{2} \right) = \left< k \left( \cdot , x_{2} \right), k \left( \cdot , x_{1} \right) \right> $$

再生カーネル $k : X \times X \to \mathbb{R}$ に対して $x \mapsto k (\cdot ,x)$ である(表現者)関数 $\phi : X \to \mathbb{R}^{X}$ を定義する。$k$ は再生カーネルであるため、$x' \in X$ で関数 $\left( \phi (x) \right) (\cdot)$ の関数値はすべての $x, x' \in X$ に対して $$ \left( \phi (x) \right) (x ') = k \left( x' , x \right) = \left< \phi \left( x ' \right) , \phi (x) \right> $$ である。ここで $\left< \cdot , \cdot \right>$ は $H_{k}$ の内積である。与えられた $\left\{ x_{i} \right\}_{i=1}^{m}$ に対して、任意の関数 $f \in \mathcal{F}$ は $\span \left\{ \phi \left( x_{i} \right) \right\}_{i=1}^{m}$ の部分とそれに直交するすべての $j$ に対して $$ \left< v , \phi \left( x_{j} \right) \right> = 0 $$ を満たす $v \in \mathcal{F}$ とある $\left( \alpha_{1} , \cdots , \alpha_{m} \right) \subset \mathbb{R}^{m}$ に対して次のように表現できる。 $$ f = \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) + v $$ ここで、 $$ \begin{align*} L (f) :=& c \left( \left( x_{1}, y_{1}, f \left( x_{1} \right) \right), \cdots , \left( x_{m}, y_{m}, f \left( x_{m} \right) \right) \right) + g \left( \left\| f \right\| \right) \\ =& c + g \end{align*} $$ で、$c$ は $v$ に依存しないこと、$v = 0$ のとき $f$ が $L(f)$ を最小化することを議論する。

Part 2. $c$ と $v$ は独立である

関数 $f = f(\cdot)$ と再生カーネル $k \left( \cdot , x_{j} \right)$ の内積は再生性質により $$ \begin{align*} =& \left< f , k \left( \cdot , x_{j} \right) \right> \\ f \left( x_{j} \right) =& \left< \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) + v , \phi \left( x_{j} \right) \right> \\ =& \sum_{i=1}^{m} \alpha_{i} \left< \phi \left( x_{i} \right) , \phi \left( x_{j} \right) \right> + 0 \end{align*} $$ である。これは $v$ に独立であるため、$L (f) = c + g$ で学習データ $D$ と $f$ にのみ依存する $$ c = c \left( \left( x_{1}, y_{1}, f \left( x_{1} \right) \right), \cdots , \left( x_{m}, y_{m}, f \left( x_{m} \right) \right) \right) $$ も $v$ に独立であることがわかる。

Part 3. $g$ は $v = 0$ のとき最小化される

(1): $v$ は $\sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right)$ に直交し、
(2): $g$ が単調関数であると仮定したため、

$$ \begin{align*} & g \left( \left\| f \right\| \right) \\ =& g \left( \left\| \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) + v \right\| \right) \\ =& g \left( \sqrt{\left\| \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) + v \right\|^{2} + \left\| v \right\|^{2}} \right) & \because (1) \\ \ge& g \left( \left\| \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) \right\| \right) & \because (2) \end{align*} $$ を得る。明らかに $v = 0$ のとき等式が成立し、$g$ が最小化されるためには $v=0$ でなければならない。一方、Part 2で $v$ は $c$ に影響を与えることができないことが確認されたため、$v = 0$ としても問題なく、$L = c + g$ を最小化する関数 $f$ は次のような形で表現できる。 $$ f (\cdot) = \sum_{i=1}^{m} \alpha_{i} k \left( \cdot , x_{i} \right) $$

■

Wahba. (2019). Representer Theorem. https://pages.stat.wisc.edu/~wahba/ftp1/wahba.wang.2019submit.pdf ↩︎
Schölkopf. (2001). A Generalized Representer Theorem. https://link.springer.com/chapter/10.1007/3-540-44581-1_27 ↩︎