第4章カーネル法とサポートベクターマシン（機械学習の数理）

この章の目標

マージン最大化をハードマージン・ソフトマージン SVM として定式化し、KKT 条件から双対問題を導ける

相補性条件からサポートベクトルの意味を説明し、小さいデータで SVM の解を確かめられる

正定値カーネルの構成法を証明し、ガウスカーネルが正定値であることを示せる

再生核ヒルベルト空間を説明し、表現定理を証明できる

カーネルリッジ回帰の閉形式を導き、計算量とハイパーパラメータの注意を説明できる

前提：23-optimization 第4章（KKT 条件・ラグランジュ双対）、02-linear-algebra 第8章（正定値行列）、第2章（リッジ回帰）。4.5 節以降では 02-linear-algebra 第7章の実対称行列の対角化と直交分解を使う（ヒルベルト空間の一般論は 10-functional-analysis 第2章）。

製品の測定値から良品か不良品かを判定したい。訓練データを分ける超平面が無数にあるとき、どれを選ぶべきか。サポートベクトルマシン (support vector machine, SVM) の答えは「両側のデータから最も離れたもの」である。これは凸二次計画で、双対問題を導くと、解が少数のデータ（サポートベクトル）だけで決まり、データが内積を通してしか現れないことがわかる。

後者を使うと、内積をカーネルに取り替えるだけで、高次元（無限次元でもよい）の特徴空間での線形な方法を、その座標を計算せずに実行できる。どんな関数がカーネルになるか（正定値性）、背後の関数空間（再生核ヒルベルト空間）、無限次元の最適化が有限次元に帰着する理由（表現定理）を順に見る。

訓練データを $(x_1, y_1), \dots, (x_n, y_n)$ （ $x_i \in \mathbb{R}^d$ ）とし、2 値分類のラベルは $y_i \in \lbrace +1, -1 \rbrace$ とする（第2章のロジスティック回帰の $\lbrace 0, 1 \rbrace$ とは異なる）。 $f(x) = w^{\top}x + b$ の符号で予測する。転置は $A^{\top}$ と書く（02-linear-algebra の ${}^tA$ ）。

4.1 マージン最大化

補題 4.1（点と超平面の距離） $w \neq 0$ のとき、点 $x$ と超平面 $H = \lbrace z \mid w^{\top}z + b = 0 \rbrace$ の距離は $\lvert w^{\top}x + b \rvert/\lVert w \rVert$ である。

証明. $z_0 = x - \frac{w^{\top}x + b}{\lVert w \rVert^2}w \in H$ で、 $z \in H$ なら $w^{\top}(z_0 - z) = 0$ 、 $x - z_0$ は $w$ の定数倍なので、ピタゴラスの定理より $\lVert x - z \rVert^2 = \lVert x - z_0 \rVert^2 + \lVert z_0 - z \rVert^2 \geq \lVert x - z_0 \rVert^2 = (w^{\top}x + b)^2/\lVert w \rVert^2$ 。 $\square$

定義 4.2（線形分離可能・マージン）すべての $i$ で $y_i(w^{\top}x_i + b) > 0$ となる $(w, b)$ があるとき、データは線形分離可能 (linearly separable) であるという。 $w \neq 0$ に対し $\gamma(w, b) = \min_i y_i(w^{\top}x_i + b)/\lVert w \rVert$ を $(w, b)$ のマージン (margin) という。

$(w, b)$ がデータを分離していれば、 $\gamma(w, b)$ は超平面と最も近いデータ点の距離である（補題 4.1）。マージンが大きいほど、小さな揺れで判定が変わりにくい。 $(w, b)$ を正の定数倍しても $\gamma$ は変わらないので、 $\min_i y_i(w^{\top}x_i + b) = 1$ と正規化すれば $\gamma = 1/\lVert w \rVert$ で、マージン最大化は次の問題になる。

命題 4.3（ハードマージン SVM）データは線形分離可能で、両方のラベルを含むとする。制約 $y_i(w^{\top}x_i + b) \geq 1$ （ $i = 1, \dots, n$ ）のもとで $\frac{1}{2}\lVert w \rVert^2$ を最小化する問題 (P) をハードマージン SVM という。(P) はただ一つの最適解 $(w^{\ast}, b^{\ast})$ をもち、 $w^{\ast} \neq 0$ で、 $\gamma(w^{\ast}, b^{\ast}) = 1/\lVert w^{\ast} \rVert$ は $w \neq 0$ であるすべての $(w, b)$ のマージンの最大値である。マージンを最大にする $(w, b)$ は $(w^{\ast}, b^{\ast})$ の正の定数倍に限る。

証明. 分離する $(w, b)$ を $m = \min_i y_i(w^{\top}x_i + b) > 0$ で割れば実行可能で、実行可能なら $w \neq 0$ （ $w = 0$ なら両方のラベルで $y_ib \geq 1$ となる）。最適解の存在は 23-optimization 第4章 4.7 節の応用例「サポートベクターマシンの双対問題」で示した。一意性：最適解の $w_1 \neq w_2$ があれば、中点は実行可能で $\lVert (w_1 + w_2)/2 \rVert^2 = (\lVert w_1 \rVert^2 + \lVert w_2 \rVert^2)/2 - \lVert w_1 - w_2 \rVert^2/4$ が最適値より小さい。 $w = w^{\ast}$ で実行可能な $b$ が 2 つあれば、その間の $b$ ではすべての制約が狭義で、 $m = \min_i y_i(w^{\ast\top}x_i + b) > 1$ として $(w^{\ast}/m, b/m)$ がより小さい値を与える。同じ理由で $\min_i y_i(w^{\ast\top}x_i + b^{\ast}) = 1$ 。最後に $\gamma(w, b) > 0$ なら、 $m = \gamma(w, b)\lVert w \rVert$ として $(w/m, b/m)$ が実行可能なので $\lVert w^{\ast} \rVert \leq \lVert w \rVert/m$ 、すなわち $\gamma(w, b) \leq 1/\lVert w^{\ast} \rVert$ 。等号なら $\lVert w/m \rVert = \lVert w^{\ast} \rVert$ で $(w/m, b/m)$ も最適解なので、一意性より $(w, b) = m(w^{\ast}, b^{\ast})$ 。 $\square$

4.2 双対問題とサポートベクトル

(P) のラグランジュ関数は、乗数 $\alpha_i \geq 0$ について

L(w, b, \alpha) = \frac{1}{2}\lVert w \rVert^2 - \sum_{i=1}^n \alpha_i\bigl(y_i(w^{\top}x_i + b) - 1\bigr)

である。双対関数 $g(\alpha) = \inf_{w, b} L$ は、 $\sum_i \alpha_iy_i \neq 0$ なら $b$ を動かして $-\infty$ になり、 $\sum_i \alpha_iy_i = 0$ なら $L$ は $w$ の狭義凸な二次関数で $w = \sum_i \alpha_iy_ix_i$ で最小になるので

g(\alpha) = \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n \alpha_i\alpha_jy_iy_jx_i^{\top}x_j

である。 $\alpha_i \geq 0$ , $\sum_i \alpha_iy_i = 0$ のもとで $g(\alpha)$ を最大化する問題を (D) とする。

定理 4.4（ハードマージン SVM の双対性）命題 4.3 の仮定のもとで、次が成り立つ。

(D) は最適解をもち、(P) と (D) の最適値は一致する。

(D) の任意の最適解 $\alpha^{\ast}$ について $w^{\ast} = \sum_i \alpha_i^{\ast}y_ix_i$ であり、相補性条件 $\alpha_i^{\ast}\bigl(y_i(w^{\ast\top}x_i + b^{\ast}) - 1\bigr) = 0$ （すべての $i$ ）が成り立つ。 $\alpha_j^{\ast} > 0$ となる $j$ が存在し、 $b^{\ast} = y_j - w^{\ast\top}x_j$ である。

逆に、(P) の実行可能解 $(w, b)$ と $\alpha \geq 0$ が $w = \sum_i \alpha_iy_ix_i$ , $\sum_i \alpha_iy_i = 0$ と相補性条件を満たせば、 $(w, b)$ は (P) の、 $\alpha$ は (D) の最適解である。

証明. 3：(P) の実行可能解 $(w', b')$ について、 $\alpha_i \geq 0$ と制約から

\frac{1}{2}\lVert w' \rVert^2 \geq L(w', b', \alpha) \geq g(\alpha) = L(w, b, \alpha) = \frac{1}{2}\lVert w \rVert^2

（ $w$ が $L(\cdot, b, \alpha)$ の最小点であることと相補性条件による）。よって $(w, b)$ は最適で、(D) の実行可能解 $\alpha'$ も同様に $g(\alpha') \leq \frac{1}{2}\lVert w \rVert^2 = g(\alpha)$ （弱双対性）を満たすので $\alpha$ も最適である。

1：(P) の制約は 1 次式なので、最適解 $(w^{\ast}, b^{\ast})$ で KKT 条件を満たす乗数 $\alpha^{\ast} \geq 0$ が存在する（23-optimization 第4章命題 4.5）。KKT 条件は 3 の条件そのものなので、3 より $\alpha^{\ast}$ は (D) の最適解で、最適値は一致する。

2：(D) の任意の最適解 $\alpha$ について、1 より

\frac{1}{2}\lVert w^{\ast} \rVert^2 = g(\alpha) \leq L(w^{\ast}, b^{\ast}, \alpha) = \frac{1}{2}\lVert w^{\ast} \rVert^2 - \sum_i \alpha_i\bigl(y_i(w^{\ast\top}x_i + b^{\ast}) - 1\bigr) \leq \frac{1}{2}\lVert w^{\ast} \rVert^2

で等号が成り立つ。和の各項は $0$ 以上なので相補性条件が従い、 $(w^{\ast}, b^{\ast})$ は $L(\cdot, \cdot, \alpha)$ の最小点なので $w^{\ast} = \sum_i \alpha_iy_ix_i$ 。 $w^{\ast} \neq 0$ より $\alpha_j > 0$ の $j$ があり、 $y_j(w^{\ast\top}x_j + b^{\ast}) = 1$ に $y_j$ を掛ければよい。 $\square$

定義 4.5（サポートベクトル）(D) の最適解 $\alpha^{\ast}$ について、 $\alpha_i^{\ast} > 0$ となるデータ点 $x_i$ をサポートベクトル (support vector) という。

相補性条件より、サポートベクトルはマージンの境界 $y_if(x_i) = 1$ 上にあり、分類器 $f(x) = \sum_i \alpha_i^{\ast}y_ix_i^{\top}x + b^{\ast}$ はそれだけで決まる。境界上でも $\alpha_i^{\ast} = 0$ の点はありうる（どの点がサポートベクトルかは $\alpha^{\ast}$ によりうる）。

命題 4.6 (D) の最適解 $\alpha^{\ast}$ について $\alpha_i^{\ast} = 0$ となるデータをいくつ取り除いても、(P) の最適解は変わらない。

証明. 残ったデータの (P) について $(w^{\ast}, b^{\ast})$ は実行可能で、残った $\alpha_i^{\ast}$ は定理 4.4 の 3 の条件を満たす（取り除いた項は $0$ ）。残ったデータは $\sum_i \alpha_i^{\ast}y_i = 0$ , $\alpha^{\ast} \neq 0$ より両方のラベルを含むので、定理 4.4 の 3 と命題 4.3 の一意性から従う。 $\square$

例 4.7 ラベル $+1$ の $(1, 3), (3, 1), (3, 3)$ とラベル $-1$ の $(1, 1), (0, 0), (1, -1)$ を順に $x_1, \dots, x_6$ とする。 $w = (1, 1)$ , $b = -3$ , $\alpha = (1/2, 1/2, 0, 1, 0, 0)$ は $\sum_i \alpha_iy_i = 0$ , $\sum_i \alpha_iy_ix_i = \frac{1}{2}(1, 3) + \frac{1}{2}(3, 1) - (1, 1) = (1, 1)$ を満たし、 $y_if(x_i)$ は順に $1, 1, 3, 1, 3, 3$ なので実行可能で相補性条件も成り立つ。定理 4.4 の 3 よりこれが最適解である（双対問題を数値的に解いても同じ解を得る）。決定境界は $z_1 + z_2 = 3$ 、マージンは $1/\sqrt{2}$ 、サポートベクトルは $x_1, x_2, x_4$ 、最適値は $\frac{1}{2}\lVert w \rVert^2 = 1 = g(\alpha)$ である。

4.3 ソフトマージン SVM

実際のデータは線形分離できないことが多く、分離できても 1 点の外れ値でマージンが大きく変わる。そこで制約の違反 $\xi_i \geq 0$ を許し、その総量に罰則をつける。

定義 4.8（ソフトマージン SVM） $C > 0$ について、制約 $y_i(w^{\top}x_i + b) \geq 1 - \xi_i$ , $\xi_i \geq 0$ （ $i = 1, \dots, n$ ）のもとで $\frac{1}{2}\lVert w \rVert^2 + C\sum_i \xi_i$ を最小化する問題 $(\mathrm{P}_C)$ をソフトマージン SVM という。

$(w, b)$ を固定すると最適な $\xi_i$ は $\max(0, 1 - y_if(x_i))$ なので、 $(\mathrm{P}_C)$ は次と同値である。

\min_{w, b}\ \frac{1}{2}\lVert w \rVert^2 + C\sum_{i=1}^n \ell_{\mathrm{hinge}}\bigl(y_i(w^{\top}x_i + b)\bigr), \qquad \ell_{\mathrm{hinge}}(t) = \max(0, 1 - t)

$\ell_{\mathrm{hinge}}$ をヒンジ損失 (hinge loss) という。全体を $Cn$ で割れば、ヒンジ損失の経験リスクに正則化項 $\frac{1}{2Cn}\lVert w \rVert^2$ を加えた正則化つき経験リスク最小化（第1章定義 1.20）であり、 $C$ が大きいほど正則化は弱い（ $C \to \infty$ でハードマージンに近づき、外れ値に引きずられやすくなる。正則化の強さ $\lambda \propto 1/C$ で指定するソフトウェアもあるので向きに注意）。ヒンジ損失は凸で、0-1 損失 $\mathbf{1}\lbrace t \leq 0 \rbrace$ 以上である。

定理 4.9（ソフトマージン SVM の双対問題）両方のラベルがあるとする。 $(\mathrm{P}_C)$ は最適解をもち、 $w^{\ast}$ は一意である。双対問題は、 $0 \leq \alpha_i \leq C$ , $\sum_i \alpha_iy_i = 0$ のもとで (D) と同じ $g(\alpha)$ を最大化する問題で、最適値は一致する。双対問題の任意の最適解 $\alpha^{\ast}$ について $w^{\ast} = \sum_i \alpha_i^{\ast}y_ix_i$ であり、主問題の任意の最適解について $m_i = y_i(w^{\ast\top}x_i + b^{\ast})$ とおくと

$\alpha_i^{\ast} = 0$ なら $m_i \geq 1$ 、 $0 < \alpha_i^{\ast} < C$ なら $m_i = 1$ 、 $\alpha_i^{\ast} = C$ なら $m_i \leq 1$ である。

したがって $m_i > 1$ なら $\alpha_i^{\ast} = 0$ 、 $m_i < 1$ なら $\alpha_i^{\ast} = C$ 。 $0 < \alpha_j^{\ast} < C$ の $j$ があれば $b^{\ast} = y_j - w^{\ast\top}x_j$ 。

証明. ヒンジ損失の形の目的関数は連続かつ強圧的（ $\lVert w \rVert \to \infty$ なら $\frac{1}{2}\lVert w \rVert^2$ が、 $w$ が有界で $\lvert b \rvert \to \infty$ なら一方のラベルのヒンジ損失が発散する）なので最小値をもち（23-optimization 第1章定理 1.11）、 $w^{\ast}$ の一意性は命題 4.3 と同じ。 $\xi_i \geq 0$ の乗数を $\mu_i \geq 0$ とすると、ラグランジュ関数の $\xi_i$ の係数 $C - \alpha_i - \mu_i$ が $0$ でなければ下限は $-\infty$ なので、双対関数が有限なのは $\mu_i = C - \alpha_i \geq 0$ のときで、値は $g(\alpha)$ 。残りは定理 4.4 と同様で、主・双対の最適解の組は相補性条件 $\alpha_i^{\ast}(m_i - 1 + \xi_i^{\ast}) = 0$ , $(C - \alpha_i^{\ast})\xi_i^{\ast} = 0$ を満たす（逆に KKT 条件を満たす組は最適）。 $\alpha_i^{\ast} < C$ なら $\xi_i^{\ast} = 0$ で $m_i \geq 1$ 、さらに $\alpha_i^{\ast} > 0$ なら $m_i = 1$ 。 $\alpha_i^{\ast} = C$ なら $m_i = 1 - \xi_i^{\ast} \leq 1$ 。2 番目の項目の前半はこの対偶で、 $b^{\ast}$ の式は $m_j = 1$ から従う。 $\square$

例 4.10（外れ値）例 4.7 のデータにラベル $-1$ の点 $x_7 = (2, 2)$ を加える。 $x_7$ は $x_1, x_2$ の中点なので、 $f(x_1), f(x_2) > 0$ となる 1 次式では $f(x_7) > 0$ で、線形分離できない。 $C = 2$ では $\alpha^{\ast} = (3/2, 3/2, 0, 1, 0, 0, 2)$ , $w^{\ast} = (1, 1)$ , $b^{\ast} = -3$ が最適で（ $m_i = 1, 1, 3, 1, 3, 3, -1$ から KKT 条件を確かめられる）、例 4.7 と同じ分類器になり、外れ値は $\alpha_7^{\ast} = C$ で誤分類される。 $C = 1/4$ では $w^{\ast} = (1/3, 1/3)$ , $b^{\ast} = -1$ , $\alpha^{\ast} = (1/4, 1/4, 1/36, 1/4, 1/36, 0, 1/4)$ で、マージンは 3 倍の $3/\sqrt{2}$ に広がり、 $x_1, x_2, x_4, x_7$ がマージンの内側（ $\alpha_i^{\ast} = C$ ）、 $x_3, x_5$ が境界上（ $0 < \alpha_i^{\ast} < C$ ）になる（ $x_6$ も境界上だが $\alpha_6^{\ast} = 0$ ）。 $C = 1/2$ では $\alpha_i^{\ast}$ がすべて $0$ か $C$ で、 $b^{\ast}$ が一意に定まらない（問題 4.3）。

4.4 カーネルトリック

双対問題と分類器 $f(x) = \sum_i \alpha_i^{\ast}y_ix_i^{\top}x + b^{\ast}$ には、データが内積 $x_i^{\top}x_j$ , $x_i^{\top}x$ を通してしか現れない。そこで写像 $\varphi$ で内積空間 $\mathcal{H}$ （特徴空間, feature space）へ写してから SVM を使えば、必要なのは $k(x, z) = \langle \varphi(x), \varphi(z) \rangle$ だけで、 $\varphi(x)$ 自体は計算しなくてよい。双対問題の $x_i^{\top}x_j$ を $k(x_i, x_j)$ に、分類器を $f(x) = \sum_i \alpha_i^{\ast}y_ik(x_i, x) + b^{\ast}$ に置き換えればよい。これをカーネルトリック (kernel trick)、 $k$ をカーネル (kernel) という。

例 4.11（多項式カーネル） $d = 2$ 、 $x = (s, t)$ で $\varphi(x) = (s^2, \sqrt{2}st, t^2, \sqrt{2c}s, \sqrt{2c}t, c)$ （ $c \geq 0$ ）なら $\langle \varphi(x), \varphi(x') \rangle = (x^{\top}x' + c)^2$ 。一般に $(x^{\top}z + c)^m$ （ $c > 0$ ）は次数 $m$ 以下の単項式による $\binom{d + m}{m}$ 次元の特徴写像に対応し（ $d = 100$ , $m = 3$ で $176851$ 次元）、計算は内積 1 回分ですむ。

例 4.12（XOR）ラベル $+1$ の $(1, 1), (-1, -1)$ とラベル $-1$ の $(1, -1), (-1, 1)$ は（どちらも中点が原点なので）線形分離できない。カーネル $(1 + x^{\top}x')^2$ のハードマージン SVM では、グラム行列は対角成分 $9$ 、他の成分 $1$ で、すべての $\alpha_i$ を $a$ とすると双対の目的関数は $4a - 16a^2$ 、最大は $a = 1/8$ 。 $x = (s, t)$ について $\frac{1}{8}\sum_i y_i(1 + x_i^{\top}x)^2 = st$ なので、 $b = 0$ とすれば $f(x) = st$ で全点が境界上にあり、特徴空間で定理 4.4 の 3 の条件が成り立つ。分類器は座標の積の符号である。

4.5 正定値カーネル

どんな関数でもカーネルになるわけではない。双対問題の目的関数が凹であるには、 $(y_iy_jk(x_i, x_j))$ が半正定値でなければならない。

定義 4.13（正定値カーネル）集合 $\mathcal{X}$ 上の対称な関数 $k\colon \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ が、任意の $n$ 、 $x_1, \dots, x_n \in \mathcal{X}$ 、 $c \in \mathbb{R}^n$ について $\sum_{i, j} c_ic_jk(x_i, x_j) \geq 0$ を満たすとき、正定値カーネル (positive definite kernel) という。つまり、どの有限個の点でもグラム行列 $K = (k(x_i, x_j))_{i, j}$ が半正定値である。

行列の用語では「半正定値」にあたるが、カーネルでは「正定値」と呼ぶのが標準である。相異なる点のグラム行列が常に正定値なら狭義正定値という。

命題 4.14 (1) 内積空間 $\mathcal{H}$ への写像 $\varphi$ について、 $k(x, z) = \langle \varphi(x), \varphi(z) \rangle$ は正定値カーネルである。(2) 正定値カーネルは $k(x, x) \geq 0$ , $k(x, z)^2 \leq k(x, x)k(z, z)$ を満たす。

証明. (1) $\sum_{i, j} c_ic_j\langle \varphi(x_i), \varphi(x_j) \rangle = \lVert \sum_i c_i\varphi(x_i) \rVert^2 \geq 0$ 。(2) 1 点と 2 点のグラム行列が半正定値で、後者の行列式（固有値の積）が $0$ 以上であることによる。 $\square$

定理 4.15（正定値カーネルの構成） $k_1, k_2$ を $\mathcal{X}$ 上の正定値カーネルとする。次も正定値カーネルである。

$ak_1 + bk_2$ （ $a, b \geq 0$ ）と、定数 $c_0 \geq 0$ 。

積 $k_1(x, z)k_2(x, z)$ 。

正定値カーネルの列 $k^{(m)}$ がすべての $(x, z)$ で収束するときの極限 $\lim_m k^{(m)}(x, z)$ 。

任意の関数 $g\colon \mathcal{X} \to \mathbb{R}$ について $g(x)k_1(x, z)g(z)$ 。

$a_m \geq 0$ で $\sum_{m \geq 0} a_mk_1(x, z)^m$ がすべての $(x, z)$ で収束するときの和。特に $\exp(k_1(x, z))$ 。

証明. 点 $x_1, \dots, x_n$ と $c \in \mathbb{R}^n$ を固定し、 $k_1, k_2$ のグラム行列を $K_1, K_2$ とする。1： $c^{\top}(aK_1 + bK_2)c \geq 0$ 。定数のグラム行列は $c_0\mathbf{1}\mathbf{1}^{\top}$ で、 $c_0(\sum_i c_i)^2 \geq 0$ 。2（シューアの積定理）：積のグラム行列は成分ごとの積 $K_1 \circ K_2$ である。 $K_2 = \sum_l \lambda_lv_lv_l^{\top}$ （ $\lambda_l \geq 0$ 、02-linear-algebra 第7章定理 7.32）と書き、 $u_l = (c_i(v_l)_i)_i$ とおくと

c^{\top}(K_1 \circ K_2)c = \sum_{i, j} c_ic_j(K_1)_{ij}\sum_l \lambda_l(v_l)_i(v_l)_j = \sum_l \lambda_lu_l^{\top}K_1u_l \geq 0

3：有限和 $\sum_{i, j} c_ic_jk^{(m)}(x_i, x_j) \geq 0$ の極限も $0$ 以上。4： $c_i' = c_ig(x_i)$ とおけば $k_1$ の 2 次形式。5：1 と 2 より部分和 $\sum_{m \leq M} a_mk_1^m$ は正定値（ $k_1^0 = 1$ ）で、3 より和も正定値。 $\exp$ は $a_m = 1/m!$ の場合。 $\square$

系 4.16（ガウスカーネル） $\sigma > 0$ について、 $\mathbb{R}^d$ 上のガウスカーネル $k(x, z) = \exp(-\lVert x - z \rVert^2/(2\sigma^2))$ は正定値である。多項式カーネル $(x^{\top}z + c)^m$ （ $c \geq 0$ , $m \in \mathbb{N}$ ）も正定値である。

証明. $\lVert x - z \rVert^2 = \lVert x \rVert^2 - 2x^{\top}z + \lVert z \rVert^2$ より $k(x, z) = g(x)\exp(x^{\top}z/\sigma^2)g(z)$ （ $g(x) = \exp(-\lVert x \rVert^2/(2\sigma^2))$ ）。 $x^{\top}z/\sigma^2$ は命題 4.14 (1)、その指数は定理 4.15 の 5、全体は 4 により正定値。多項式カーネルは 1 と 2 による。 $\square$

ガウスカーネルは狭義正定値でもあり（問題 4.7）、相異なる点の $\varphi(x_1), \dots, \varphi(x_n)$ はどんな特徴写像でも一次独立になる（ $\lVert \sum_i c_i\varphi(x_i) \rVert^2 = c^{\top}Kc$ ）ので、特徴空間は無限次元である。

例 4.17（正定値でない例） $k(x, z) = \lVert x - z \rVert^2$ では、相異なる 2 点のグラム行列は対角成分 $0$ 、非対角成分 $a > 0$ で、固有値 $-a$ をもつ。 $k(x, z) = \tanh(x^{\top}z - 1)$ は $k(0, 0) = \tanh(-1) < 0$ で命題 4.14 (2) に反する（ $\tanh(\kappa x^{\top}z + \theta)$ の形の「シグモイドカーネル」は一般に正定値でない）。数値で調べるときはグラム行列の最小固有値を見るが、半正定値でも丸め誤差で小さい負の値が出るので、最大固有値に比べて十分小さい負の値は $0$ とみなす。

4.6 再生核ヒルベルト空間

正定値カーネルには、それを内積として実現する標準的な関数空間が付随する。

定義 4.18（再生核ヒルベルト空間） $\mathcal{X}$ 上の実数値関数からなるヒルベルト空間（完備な内積空間） $\mathcal{H}$ と $k\colon \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ が、(i) すべての $x$ で $k(\cdot, x) \in \mathcal{H}$ 、(ii) すべての $f \in \mathcal{H}$ , $x$ で $f(x) = \langle f, k(\cdot, x) \rangle_{\mathcal{H}}$ （再生性, reproducing property）を満たすとき、 $k$ を $\mathcal{H}$ の再生核 (reproducing kernel)、 $\mathcal{H}$ を再生核ヒルベルト空間 (reproducing kernel Hilbert space, RKHS) という。

(ii) で $f = k(\cdot, z)$ とすると $k(x, z) = \langle k(\cdot, z), k(\cdot, x) \rangle_{\mathcal{H}}$ なので、再生核は特徴写像 $\varphi(x) = k(\cdot, x)$ の内積で、正定値である（命題 4.14）。逆も成り立つ。

定理 4.19（ムーア–アロンシャインの定理, Moore–Aronszajn theorem） $\mathcal{X}$ 上の任意の正定値カーネル $k$ に対し、 $k$ を再生核とする再生核ヒルベルト空間 $\mathcal{H}_k$ がただ一つ存在する。 $\sum_{i=1}^m a_ik(\cdot, x_i)$ の形の関数全体は $\mathcal{H}_k$ で稠密で、その内積は $\bigl\langle \sum_i a_ik(\cdot, x_i), \sum_j b_jk(\cdot, z_j) \bigr\rangle = \sum_{i, j} a_ib_jk(x_i, z_j)$ で与えられる。

証明は省略する（福水『カーネル法入門』を参照）。再生性とコーシー–シュワルツの不等式から $\lvert f(x) - f(z) \rvert \leq \lVert f \rVert_{\mathcal{H}_k}\lVert k(\cdot, x) - k(\cdot, z) \rVert_{\mathcal{H}_k}$ で、ガウスカーネルでは $1 - e^{-u} \leq u$ より右辺は $\lVert f \rVert_{\mathcal{H}_k}\lVert x - z \rVert/\sigma$ 以下になる。ノルムの小さい関数はゆるやかにしか変化せず、正則化項 $\lVert f \rVert_{\mathcal{H}_k}^2$ はなめらかさを測る。

例 4.20（線形カーネル） $k(x, z) = x^{\top}z$ の RKHS は、1 次関数 $f_w(x) = w^{\top}x$ 全体に内積 $\langle f_w, f_v \rangle = w^{\top}v$ を入れたものである（ $k(\cdot, x) = f_x$ で $\langle f_w, f_x \rangle = f_w(x)$ ）。 $\lVert f_w \rVert = \lVert w \rVert$ なので、一般のカーネルの SVM は $\frac{1}{2}\lVert f \rVert_{\mathcal{H}_k}^2 + C\sum_i \ell_{\mathrm{hinge}}(y_i(f(x_i) + b))$ を $f \in \mathcal{H}_k$ , $b \in \mathbb{R}$ について最小にする問題である。

4.7 表現定理

$\mathcal{H}_k$ は一般に無限次元だが、解は訓練データでのカーネルの 1 次結合から探せばよい。

定理 4.21（表現定理, representer theorem） $k$ を正定値カーネル、 $\mathcal{H}$ をその RKHS、 $x_1, \dots, x_n \in \mathcal{X}$ とし、 $V = \operatorname{span}(k(\cdot, x_1), \dots, k(\cdot, x_n))$ とする。関数 $L\colon \mathbb{R}^n \to \mathbb{R}$ と単調非減少な関数 $\Omega\colon [0, \infty) \to \mathbb{R}$ について
$J(f) = L\bigl(f(x_1), \dots, f(x_n)\bigr) + \Omega(\lVert f \rVert_{\mathcal{H}}) \qquad (f \in \mathcal{H})$
とする。任意の $f \in \mathcal{H}$ に対し $J(f_V) \leq J(f)$ となる $f_V \in V$ がある。特に $J$ が最小点をもてば $V$ の中にも最小点があり、 $\Omega$ が狭義単調増加なら最小点はすべて $V$ に属する。 $L$ が実数のパラメータ $b$ （SVM の切片）にも依存してよい。

証明. $V$ は有限次元なので $f = f_V + f_{\perp}$ （ $f_V \in V$ , $f_{\perp} \perp V$ ）と分解できる（02-linear-algebra 第7章定理 7.15。 $\mathcal{H}$ が無限次元でも有限次元部分空間への分解は成り立つ）。再生性より $f(x_i) = \langle f, k(\cdot, x_i) \rangle = \langle f_V, k(\cdot, x_i) \rangle = f_V(x_i)$ で、ピタゴラスの定理より $\lVert f_V \rVert^2 = \lVert f \rVert^2 - \lVert f_{\perp} \rVert^2 \leq \lVert f \rVert^2$ 。よって $L$ の値は変わらず $\Omega$ の値は増えない。 $\Omega$ が狭義単調増加で $f_{\perp} \neq 0$ なら $J(f_V) < J(f)$ なので、 $f$ は最小点でない。 $\square$

SVM の双対から得た $f = \sum_i \alpha_i^{\ast}y_ik(\cdot, x_i)$ と整合する。損失が訓練点での値だけに、正則化がノルムだけに依存することが本質である。

4.8 カーネルリッジ回帰

第2章のリッジ回帰を RKHS の中で行う。

定理 4.22（カーネルリッジ回帰） $\lambda > 0$ 、 $K = (k(x_i, x_j))_{i, j}$ 、 $y = (y_1, \dots, y_n)^{\top} \in \mathbb{R}^n$ とする。 $J(f) = \sum_{i=1}^n (y_i - f(x_i))^2 + \lambda\lVert f \rVert_{\mathcal{H}}^2$ の $\mathcal{H}$ での最小点 $\hat{f}$ はただ一つで、
$\hat{f} = \sum_{i=1}^n \hat{\alpha}_ik(\cdot, x_i), \qquad \hat{\alpha} = (K + \lambda I_n)^{-1}y, \qquad \hat{f}(x) = k_x^{\top}(K + \lambda I_n)^{-1}y$
である。ここで $k_x = (k(x_1, x), \dots, k(x_n, x))^{\top}$ 。

証明. $K + \lambda I_n$ は正定値なので正則。 $f = \sum_i \alpha_ik(\cdot, x_i)$ なら再生性より $f(x_j) = (K\alpha)_j$ , $\lVert f \rVert^2 = \alpha^{\top}K\alpha$ で、 $J(f) = \Phi(\alpha) := \lVert y - K\alpha \rVert^2 + \lambda\alpha^{\top}K\alpha$ 。 $\Phi$ は凸な二次関数で $\nabla\Phi(\alpha) = 2K\bigl((K + \lambda I_n)\alpha - y\bigr)$ は $\hat{\alpha}$ で $0$ なので、 $\hat{\alpha}$ は $\Phi$ の最小点である（23-optimization 第2章定理 2.19）。表現定理より任意の $f$ で $J(f) \geq J(f_V) \geq \Phi(\hat{\alpha}) = J(\hat{f})$ 。一意性：中線定理（02-linear-algebra 第7章命題 7.4）より $f \neq g$ なら $\lVert (f + g)/2 \rVert^2 < (\lVert f \rVert^2 + \lVert g \rVert^2)/2$ で、二乗誤差は凸なので $J((f + g)/2) < (J(f) + J(g))/2$ 。よって最小点は 1 つである（ $K$ が特異なら係数は一意でないが、関数 $\hat{f}$ は一意）。 $\square$

注意 4.23（線形カーネルとリッジ回帰）線形カーネルでは $K = XX^{\top}$ （ $X$ はデータ行列）で $\hat{f}(x) = x^{\top}X^{\top}(XX^{\top} + \lambda I_n)^{-1}y$ 。 $X^{\top}(XX^{\top} + \lambda I_n) = (X^{\top}X + \lambda I_d)X^{\top}$ より、これは第2章定理 2.5 のリッジ回帰の解 $(X^{\top}X + \lambda I_d)^{-1}X^{\top}y$ と一致する。前者は $n$ 次、後者は $d$ 次の連立方程式で、 $n < d$ なら前者が速い。特徴空間が無限次元なら前者しかない。

ガウスカーネルの幅 $\sigma$ の影響を見る。 $\sigma \to 0$ では（訓練点が相異なれば） $K \to I_n$ で、 $\hat{f}(x_i) \to y_i/(1 + \lambda)$ 、離れた点では $\hat{f} \to 0$ （暗記）。 $\sigma \to \infty$ では $K$ の成分がすべて $1$ に近づき、 $\hat{f}$ はほぼ定数になる。

import numpy as np

rng = np.random.default_rng(0)
x = rng.uniform(0, 6, 30)
y = np.sin(x) + 0.3 * rng.standard_normal(30)    # 訓練データ
xt = np.linspace(0, 6, 601)                      # 真の関数 sin と比べる点
K = lambda a, b, s: np.exp(-(a[:, None] - b[None, :])**2 / (2 * s**2))
for s in [0.03, 0.5, 5.0]:
    alpha = np.linalg.solve(K(x, x, s) + 0.1 * np.eye(30), y)    # lambda = 0.1
    tr = np.mean((K(x, x, s) @ alpha - y)**2)
    te = np.mean((K(xt, x, s) @ alpha - np.sin(xt))**2)
    print(f"sigma={s:4.2f}: 訓練誤差 {tr:.4f}  真の関数との誤差 {te:.4f}")

sigma=0.03: 訓練誤差 0.0053  真の関数との誤差 0.3721
sigma=0.50: 訓練誤差 0.0303  真の関数との誤差 0.0638
sigma=5.00: 訓練誤差 0.2749  真の関数との誤差 0.1683

$\sigma = 0.03$ は訓練誤差が最小だが真の関数から最も遠く（過学習）、 $\sigma = 5$ は両方大きい（未学習）。

ヒント

実務では (1) ガウスカーネルは距離を使うので、特徴量を標準化してから使う。(2) $C$ （または $\lambda$ ）と $\sigma$ は対数スケールの格子で、訓練データ内の交差検証で選ぶ（ $\sigma$ の目安に訓練点どうしの距離の中央値を使う経験則もある）。テストデータで選ぶと評価が楽観的になる（第1章 1.7 節）。(3) SVM の $f(x)$ は確率ではない。必要なら検証データで $f(x)$ にロジスティック関数を当てはめて較正する。(4) カーネル行列は $n^2$ 個の成分をもち（ $n = 10^5$ なら倍精度で 80 GB）、カーネルリッジ回帰を直接解くと $O(n^3)$ かかる。大きなデータでは線形モデルや近似（ランダム特徴など）を使う。

まとめ

マージン最大化はハードマージン SVM（凸二次計画）で、解は一意である。双対問題では $w^{\ast} = \sum_i \alpha_i^{\ast}y_ix_i$ となり、データは内積だけを通して現れる。
相補性条件より、サポートベクトル（ $\alpha_i^{\ast} > 0$ ）は境界上にあり、分類器はそれだけで決まる。
ソフトマージン SVM はヒンジ損失の正則化つき経験リスク最小化で、双対は $0 \leq \alpha_i \leq C$ の箱型制約になる。 $C$ が大きいほど正則化は弱い。
カーネルトリック：内積を正定値カーネルに置き換えると、特徴空間の座標を計算せずに非線形な分類ができる。
正定値カーネルは和・積・極限・指数で閉じ、ガウスカーネルは正定値である。距離の 2 乗や $\tanh(x^{\top}z - 1)$ は正定値でない。
正定値カーネルには再生核ヒルベルト空間がただ一つ対応し（ムーア–アロンシャイン）、そのノルムはなめらかさを測る。
表現定理により解は $\sum_i \alpha_ik(\cdot, x_i)$ の形でよく、カーネルリッジ回帰の解は $k_x^{\top}(K + \lambda I)^{-1}y$ である。計算量は $n$ の 3 乗で増える。

演習問題

問題 4.1 ★ ラベル $+1$ の点 $(2, 3), (4, 0)$ とラベル $-1$ の点 $(1, 1)$ がある。(1) $w = (3, 4)$ , $b = -10$ のマージンを求めよ。(2) $w = (6/7, 4/7)$ , $b = -17/7$ , $\alpha = (18/49, 8/49, 26/49)$ が定理 4.4 の 3 の条件を満たすことを確かめ、最大のマージンを求めよ。

解答

(1) $y_i(w^{\top}x_i + b)$ は順に $8, 2, 3$ 、 $\lVert w \rVert = 5$ なので $\gamma = 2/5$ 。(2) $\sum_i \alpha_iy_i = (18 + 8 - 26)/49 = 0$ 、 $\sum_i \alpha_iy_ix_i = \frac{1}{49}(36 + 32 - 26, 54 - 26) = w$ 。 $y_if(x_i)$ はすべて $1$ （ $(12 + 12 - 17)/7$ など）で、実行可能かつ相補性条件も成り立つので最適。最大のマージンは $1/\lVert w \rVert = 7/(2\sqrt{13}) \approx 0.971$ 。

問題 4.2 ★★ 線形分離可能で両方のラベルを含むデータで、各 $i$ について $(x_i, y_i)$ を除いて学習したハードマージン SVM で $x_i$ を分類する（一つ抜き交差検証）。サポートベクトルが $s$ 個なら誤分類率は $s/n$ 以下であることを示せ。

解答

$\alpha_i^{\ast} = 0$ の点を除いても、命題 4.6 より解は $(w^{\ast}, b^{\ast})$ のままで、その点は $y_i(w^{\ast\top}x_i + b^{\ast}) \geq 1 > 0$ より正しく分類される。よって誤分類は $\alpha_i^{\ast} > 0$ の $s$ 点でしか起こらない。

問題 4.3 ★★ (1) 線形分離可能なデータで、(D) の最適解 $\alpha^{h}$ が $\max_i \alpha_i^{h} \leq C$ を満たせば、ハードマージン SVM の解（と $\xi = 0$ ）は $(\mathrm{P}_C)$ の最適解でもあることを示せ。例 4.7 ではどの $C$ で成り立つか。(2) 例 4.10 のデータで $C = 1/2$ とする。 $\alpha = (1/2, 1/2, 0, 1/2, 0, 0, 1/2)$ と、 $w = (1/2, 1/2)$ , $b \in [-2, -1]$ の値を比べ、 $b$ が一意に定まらないことを示せ。

解答

(1) $\alpha^{h}$ は $(\mathrm{P}_C)$ の双対の実行可能解で値は $g(\alpha^{h}) = \frac{1}{2}\lVert w^{\ast} \rVert^2$ 、 $(w^{\ast}, b^{\ast}, 0)$ は $(\mathrm{P}_C)$ の実行可能解で値は同じなので、弱双対性より両者は最適。例 4.7 では $\max_i \alpha_i^{h} = 1$ なので $C \geq 1$ （ $C = 1/2$ では $w^{\ast} = (1/2, 1/2)$ , $b^{\ast} = -1$ になる）。(2) $\alpha$ は双対の実行可能解で、 $\sum_i \alpha_iy_ix_i = \frac{1}{2}\bigl((1, 3) + (3, 1) - (1, 1) - (2, 2)\bigr) = (1/2, 1/2)$ 、値は $2 - \frac{1}{4} = \frac{7}{4}$ 。 $b \in [-2, -1]$ のヒンジ損失は $x_1, x_2$ で $-1 - b$ 、 $x_4$ で $2 + b$ 、 $x_7$ で $3 + b$ 、他は $0$ で和は $3$ 、主問題の値は $\frac{1}{4} + \frac{3}{2} = \frac{7}{4}$ 。値が等しいので、すべての $b \in [-2, -1]$ が最適である（ $0 < \alpha_j < C$ の点がない）。

問題 4.4 ★★ 次は正定値カーネルか。(1) $[0, \infty)$ 上の $\min(x, z)$ (2) $\mathbb{R}$ 上の $\cos(x - z)$ (3) $(-1, 1)$ 上の $1/(1 - xz)$ (4) $\mathbb{R}^d$ 上の $\lVert x - z \rVert$

解答

(1) 正定値。点の正の値を $t_1 < \cdots < t_m$ 、 $t_0 = 0$ とし $\varphi_l(x) = \sqrt{t_l - t_{l-1}}\ \mathbf{1}\lbrace x \geq t_l \rbrace$ とおくと、点 $x, z$ で $\sum_l \varphi_l(x)\varphi_l(z) = \min(x, z)$ なので、グラム行列は $\Phi\Phi^{\top}$ の形。(2) 正定値。 $\cos x\cos z + \sin x\sin z$ は $\varphi(x) = (\cos x, \sin x)$ の内積。(3) 正定値。 $\sum_{m \geq 0} (xz)^m$ が収束するので定理 4.15 の 5 による。(4) 正定値でない。相異なる 2 点のグラム行列は対角成分 $0$ 、非対角成分が正で、負の固有値をもつ。

問題 4.5 ★★ 2 点 $x_1 = 0$ , $x_2 = 1$ （ $y = (1, -1)$ ）に、 $\sigma = 1$ のガウスカーネルと $\lambda = 0.1$ でカーネルリッジ回帰を行う。 $\rho = e^{-1/2}$ として $\hat{f}(x)$ を求め、 $\hat{f}(0)$ , $\hat{f}(2)$ と $\lvert x \rvert \to \infty$ での値を調べよ。実務上どんな注意につながるか。

解答

$K(1, -1)^{\top} = (1 - \rho)(1, -1)^{\top}$ なので $\hat{\alpha} = y/(1.1 - \rho)$ 、 $\hat{f}(x) = (e^{-x^2/2} - e^{-(x - 1)^2/2})/(1.1 - \rho)$ 。 $\hat{f}(0) \approx 0.797$ 、 $\hat{f}(2) \approx -0.955$ 、 $\lvert x \rvert \to \infty$ で $\hat{f}(x) \to 0$ 。データから離れると予測は $0$ に戻るので、 $y$ を中心化する（または定数項を加える）必要があり、外挿は信用できない。

問題 4.6 ★★ 次の分析の問題点を指摘せよ。「年収（円）と年齢（歳）から購入の有無を予測するため、特徴量をそのまま使って $\sigma = 1$ のガウスカーネル SVM を学習した。テストデータの正解率が最大になるように $C$ と $\sigma$ を選び直し、その正解率 93% を報告した。 $f(x)$ の値は購入確率として営業部門に渡した。」

解答

(1) 標準化していない。顧客どうしの年収の差は数十万円以上になるのがふつうなので、 $\sigma = 1$ では異なる顧客のカーネルの値がほぼ $0$ でグラム行列はほぼ単位行列になり、訓練データを暗記するだけになる。(2) テストデータでハイパーパラメータを選ぶと正解率が楽観的になる（第1章 1.7 節）。訓練データ内の交差検証で選ぶ。(3) $f(x)$ は確率ではない（ $[0, 1]$ に入らず、較正されていない）。

問題 4.7 ★★★ ガウスカーネル（ $\sigma = 1$ ）が狭義正定値であること、すなわち相異なる $x_1, \dots, x_n \in \mathbb{R}^d$ と $c \neq 0$ について $\sum_{j, l} c_jc_l\exp(-\lVert x_j - x_l \rVert^2/2) > 0$ を示せ。ヒント： $Z \sim N(0, I_d)$ について $E[e^{\mathrm{i}t^{\top}Z}] = e^{-\lVert t \rVert^2/2}$ （ $\mathrm{i}$ は虚数単位。11-probability 第3章例 3.15 の正規分布の特性関数と成分の独立性から）。

解答

ヒントより

\sum_{j, l} c_jc_le^{-\lVert x_j - x_l \rVert^2/2} = \sum_{j, l} c_jc_lE\bigl[e^{\mathrm{i}(x_j - x_l)^{\top}Z}\bigr] = E\Bigl[\Bigl\lvert \sum_j c_je^{\mathrm{i}x_j^{\top}Z} \Bigr\rvert^2\Bigr] \geq 0

これが $0$ なら、非負の連続関数 $h(z) = \lvert \sum_j c_je^{\mathrm{i}x_j^{\top}z} \rvert^2$ と正の密度の積の積分が $0$ なので $h \equiv 0$ 。 $a_j = u^{\top}x_j$ が相異なる $u$ をとり（ $u^{\top}(x_j - x_l) = 0$ となる $u$ は有限個の超平面上にしかない）、 $z = su$ とすると $\sum_j c_je^{\mathrm{i}a_js} = 0$ （すべての $s$ ）。 $s = 0$ で $m$ 回微分して $\sum_j c_ja_j^m = 0$ （ $m = 0, \dots, n - 1$ ）で、ファンデルモンド行列は正則なので $c = 0$ 、矛盾。