カーネル法の理論（カーネルトリック）を導出して理解する | 機械学習と情報技術

カーネル法の理論（カーネルトリック）を導出して理解する | 機械学習と情報技術 カーネル法の理論（カーネルトリック）を導出して理解する – 機械学習と情報技術 カーネル法の理論（カーネルトリック）を導出して理解する 2026/2/25 カーネル法 線形モデルはシンプルで解釈しやすい一方、現実のデータは線形では捉えきれない複雑な構造を持つことが多くあります。カーネル法（Kernel Methods）は、データを高次元（場合によっては無限次元）の特徴空間に写像しつつ、実際には高次元空間での計算を一切行わずに内積だけで処理するという巧妙なアイデアです。 この魔法のような仕組みが「カーネルトリック」です。本記事では、線形モデルの限界から出発し、特徴写像とカーネル関数の定義、具体的なカーネルの特徴写像の明示、正定値カーネルとマーサーの定理、再生核ヒルベルト空間（RKHS）の導入まで丁寧に解説し、カーネルリッジ回帰の双対形式を導出・実装します。 本記事の内容 線形モデルの限界と特徴写像 $\phi(\bm{x})$ の導入 カーネル関数 $k(\bm{x}, \bm{x}’) = \langle \phi(\bm{x}), \phi(\bm{x}’) \rangle$ の定義 カーネルトリックの威力 多項式カーネルの特徴写像の明示的展開 RBF カーネルが無限次元特徴空間に対応することの説明 正定値カーネルの定義とマーサーの定理 再生核ヒルベルト空間（RKHS）への導入 カーネルリッジ回帰の双対形式の導出 Python での実装と可視化 前提知識 この記事を読む前に、以下の記事を読んでおくと理解が深まります。 線形回帰 正則化 ガウス過程回帰 線形モデルの限界 線形分類器の問題 線形モデル $f(\bm{x}) = \bm{w}^T \bm{x} + b$ は、データが線形分離可能な場合には有効ですが、XOR パターンや円形の決定境界のような非線形構造を持つデータには対応できません。 例えば、2次元データ $\bm{x} = (x_1, x_2)^T$ に対して、$x_1^2 + x_2^2 < r^2$ の内側と外側でクラスが分かれるような場合、どのような超平面 $w_1 x_1 + w_2 x_2 + b = 0$ を引いても完全な分類はできません。 特徴写像による解決 この問題を解決する直接的なアプローチは、元の入力空間から高次元の特徴空間への写像 $\phi: \mathbb{R}^d \to \mathcal{H}$ を導入することです。 上記の例では $$ \phi(\bm{x}) = \phi(x_1, x_2) = (x_1^2, x_2^2, \sqrt{2} x_1 x_2, \sqrt{2} x_1, \sqrt{2} x_2, 1)^T $$ のように写像すれば、高次元空間 $\mathcal{H} = \mathbb{R}^6$ で線形分離可能になります。 しかし、この直接的なアプローチには問題があります。 特徴空間の次元が非常に高くなり得る（次数 $d$ の多項式で $\binom{n+d}{d}$ 次元） $\phi(\bm{x})$ を明示的に計算するコストが高い 無限次元の特徴空間は直接扱えない カーネルトリックは、これらの問題を全て解決します。 カーネル関数の定義 定義 カーネル関数 $k: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ は、ある特徴空間 $\mathcal{H}$ への写像 $\phi: \mathcal{X} \to \mathcal{H}$ が存在して $$ k(\bm{x}, \bm{x}’) = \langle \phi(\bm{x}), \phi(\bm{x}’) \rangle_{\mathcal{H}} $$ と表される関数です。ここで $\langle \cdot, \cdot \rangle_{\mathcal{H}}$ は $\mathcal{H}$ の内積です。 カーネルトリックの威力 カーネルトリックの核心は、$\phi(\bm{x})$ を明示的に計算しなくても、$k(\bm{x}, \bm{x}’)$ の計算だけで高次元特徴空間での内積が得られるという点です。 多くの機械学習アルゴリズム（リッジ回帰、SVM、主成分分析など）は、データを内積 $\langle \bm{x}_i, \bm{x}_j \rangle$ を通じてのみ参照するように書き換えることができます。この内積を $k(\bm{x}_i, \bm{x}_j)$ に置き換えるだけで、暗黙的に高次元特徴空間での学習が実現されます。 多項式カーネルの特徴写像の展開 2次多項式カーネル 2次元入力 $\bm{x} = (x_1, x_2)^T$、$\bm{x}’ = (x_1′, x_2′)^T$ に対する2次多項式カーネル $$ k(\bm{x}, \bm{x}’) = (1 + \bm{x}^T \bm{x}’)^2 $$ の特徴写像を明示的に求めましょう。まず内積を展開します。 $$ \bm{x}^T \bm{x}’ = x_1 x_1′ + x_2 x_2′ $$ よって $$ \begin{align} k(\bm{x}, \bm{x}’) &= (1 + x_1 x_1′ + x_2 x_2′)^2 \\ &= 1 + x_1^2 {x_1′}^2 + x_2^2 {x_2′}^2 + 2x_1 x_1′ x_2 x_2′ + 2x_1 x_1′ + 2x_2 x_2′ \\ &= 1 \cdot 1 + x_1^2 \cdot {x_1′}^2 + x_2^2 \cdot {x_2′}^2 \\ &\quad + (\sqrt{2} x_1 x_2)(\sqrt{2} x_1′ x_2′) + (\sqrt{2} x_1)(\sqrt{2} x_1′) + (\sqrt{2} x_2)(\sqrt{2} x_2′) \end{align} $$ これは以下の特徴写像の内積に一致します。 $$ \phi(\bm{x}) = (1, \, x_1^2, \, x_2^2, \, \sqrt{2}x_1 x_2, \, \sqrt{2}x_1, \, \sqrt{2}x_2)^T $$ 確認すると $$ \langle \phi(\bm{x}), \phi(\bm{x}’) \rangle = 1 + x_1^2 {x_1′}^2 + x_2^2 {x_2′}^2 + 2x_1 x_2 x_1′ x_2′ + 2x_1 x_1′ + 2x_2 x_2′ = (1 + \bm{x}^T \bm{x}’)^2 $$ となり、確かに一致しています。 一般の多項式カーネル 一般の $d$ 次多項式カーネル $$ k(\bm{x}, \bm{x}’) = (c + \bm{x}^T \bm{x}’)^d, \quad c \geq 0 $$ は、入力空間 $\mathbb{R}^n$ に対して $\binom{n+d}{d}$ 次元の特徴空間に対応します。例えば $n = 100, d = 5$ では特徴空間の次元は約 $9.6 \times 10^7$ になりますが、カーネルの計算は元の入力空間での内積 $\bm{x}^T\bm{x}’$（$O(n)$）と冪乗（$O(1)$）だけで済みます。 RBF カーネルと無限次元特徴空間 RBF（ガウス）カーネルの定義 RBF カーネル（ガウスカーネル）は $$ k(\bm{x}, \bm{x}’) = \exp\left(-\frac{\|\bm{x} – \bm{x}’\|^2}{2\sigma^2}\right) $$ と定義されます。ここで $\sigma > 0$ はバンド幅パラメータです。$\gamma = 1/(2\sigma^2)$ と置いて $$ k(\bm{x}, \bm{x}’) = \exp(-\gamma \|\bm{x} – \bm{x}’\|^2) $$ と書くこともあります。 無限次元特徴空間への対応 RBF カーネルが無限次元の特徴空間に対応することを示しましょう。簡単のため1次元の場合（$x, x’ \in \mathbb{R}$）で $\sigma^2 = 1$ とします。 $$ \begin{align} k(x, x’) &= \exp\left(-\frac{(x – x’)^2}{2}\right) \\ &= \exp\left(-\frac{x^2}{2}\right) \exp(xx’) \exp\left(-\frac{x’^2}{2}\right) \end{align} $$ ここで $\exp(xx’)$ をテイラー展開します。 $$ \exp(xx’) = \sum_{n=0}^{\infty} \frac{(xx’)^n}{n!} = \sum_{n=0}^{\infty} \frac{x^n {x’}^n}{n!} $$ よって $$ k(x, x’) = \sum_{n=0}^{\infty} \underbrace{\left(\frac{e^{-x^2/2} x^n}{\sqrt{n!}}\right)}_{\phi_n(x)} \underbrace{\left(\frac{e^{-x’^2/2} {x’}^n}{\sqrt{n!}}\right)}_{\phi_n(x’)} $$ 特徴写像は $$ \phi(x) = e^{-x^2/2} \left(1, \, \frac{x}{\sqrt{1!}}, \, \frac{x^2}{\sqrt{2!}}, \, \frac{x^3}{\sqrt{3!}}, \, \dots \right)^T $$ これは無限次元ベクトルであり、RBF カーネルは無限次元の特徴空間 $\ell^2$（二乗可算なスペースの列空間）での内積を計算していることがわかります。 有限の多項式カーネルでは表現できないような複雑な非線形関数も、RBF カーネルならば表現できるのは、この無限次元性に由来します。しかし、カーネルの計算自体は $\|\bm{x} – \bm{x}’\|^2$ の計算（$O(d)$）と指数関数（$O(1)$）だけで済み、無限次元空間を明示的に扱う必要はありません。 正定値カーネルとマーサーの定理 正定値カーネルの定義 関数 $k: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ が 正定値カーネル （positive definite kernel）であるとは、任意の $N \geq 1$、任意の $\bm{x}_1, \dots, \bm{x}_N \in \mathcal{X}$、任意の $c_1, \dots, c_N \in \mathbb{R}$ に対して $$ \sum_{i=1}^{N} \sum_{j=1}^{N} c_i c_j k(\bm{x}_i, \bm{x}_j) \geq 0 $$ が成り立つことをいいます。これは、グラム行列 $$ \bm{K} = \begin{pmatrix} k(\bm{x}_1, \bm{x}_1) & \cdots & k(\bm{x}_1, \bm{x}_N) \\ \vdots & \ddots & \vdots \\ k(\bm{x}_N, \bm{x}_1) & \cdots & k(\bm{x}_N, \bm{x}_N) \end{pmatrix} $$ が半正定値（全ての固有値が非負）であることと同値です。 正定値性の意味 正定値カーネルの重要性は、以下の同値性にあります。 $k$ が正定値カーネルである $\iff$ ある特徴空間 $\mathcal{H}$ と写像 $\phi: \mathcal{X} \to \mathcal{H}$ が存在して $k(\bm{x}, \bm{x}’) = \langle \phi(\bm{x}), \phi(\bm{x}’) \rangle_{\mathcal{H}}$ つまり、正定値性は「カーネル関数が何らかの特徴空間での内積として解釈できる」ための必要十分条件です。 マーサーの定理（概要） マーサーの定理（Mercer’s theorem）は、正定値カーネルの特徴写像表現をより具体的に与えます。 定理（マーサー） : $\mathcal{X}$ がコンパクト集合で、$k: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ が連続な正定値カーネルであるとき、固有値 $\lambda_1 \geq \lambda_2 \geq \dots \geq 0$ と正規直交固有関数 $\{\psi_n\}$ が存在して $$ k(\bm{x}, \bm{x}’) = \sum_{n=1}^{\infty} \lambda_n \psi_n(\bm{x}) \psi_n(\bm{x}’) $$ と展開できます（$L^2$ ノルムで一様収束）。 このとき、特徴写像は $$ \phi(\bm{x}) = (\sqrt{\lambda_1} \psi_1(\bm{x}), \, \sqrt{\lambda_2} \psi_2(\bm{x}), \, \dots)^T $$ と構成できます。 よく使われるカーネルの正定値性 カーネル 定義 正定値性 線形カーネル $k(\bm{x}, \bm{x}’) = \bm{x}^T \bm{x}’$ 半正定値 多項式カーネル $k(\bm{x}, \bm{x}’) = (c + \bm{x}^T \bm{x}’)^d$ $c \geq 0, d \in \mathbb{N}$ で正定値 RBF カーネル $k(\bm{x}, \bm{x}’) = \exp(-\gamma\|\bm{x}-\bm{x}’\|^2)$ $\gamma > 0$ で正定値 ラプラスカーネル $k(\bm{x}, \bm{x}’) = \exp(-\gamma\|\bm{x}-\bm{x}’\|_1)$ $\gamma > 0$ で正定値 再生核ヒルベルト空間（RKHS） RKHS の定義 再生核ヒルベルト空間（Reproducing Kernel Hilbert Space, RKHS）$\mathcal{H}_k$ は、正定値カーネル $k$ に対応するヒルベルト空間で、以下の2つの性質を持ちます。 包含性 : 任意の $\bm{x} \in \mathcal{X}$ に対して、$k(\bm{x}, \cdot) \in \mathcal{H}_k$（カーネル関数は $\mathcal{H}_k$ の要素） 再生性 : 任意の $f \in \mathcal{H}_k$ と任意の $\bm{x} \in \mathcal{X}$ に対して $$ f(\bm{x}) = \langle f, k(\bm{x}, \cdot) \rangle_{\mathcal{H}_k} $$ 再生性の意味は、「関数 $f$ の点 $\bm{x}$ での値を、$\mathcal{H}_k$ の内積で取り出せる」ということです。 RKHS の直感 RKHS $\mathcal{H}_k$ は、カーネル $k$ によって「滑らかさ」が定義される関数空間です。 RBF カーネル $\to$ 無限回微分可能な滑らかな関数の空間 マテルンカーネル $\to$ 微分可能性を制御できる関数の空間 線形カーネル $\to$ 線形関数の空間 RKHS のノルム $\|f\|_{\mathcal{H}_k}$ は関数の「複雑さ」を測る尺度であり、小さいほどカーネルの意味で「滑らか」な関数を意味します。 特徴写像との関係 特徴写像 $\phi(\bm{x}) = k(\bm{x}, \cdot)$ と定義すると $$ \langle \phi(\bm{x}), \phi(\bm{x}’) \rangle_{\mathcal{H}_k} = \langle k(\bm{x}, \cdot), k(\bm{x}’, \cdot) \rangle_{\mathcal{H}_k} = k(\bm{x}, \bm{x}’) $$ 最後の等号は再生性から従います。これにより、カーネル関数は「RKHS への特徴写像の内積」として自然に解釈できます。 カーネルリッジ回帰の双対形式の導出 主問題（原始形式） 特徴空間でのリッジ回帰は $$ \min_{\bm{w}} \frac{1}{2} \sum_{i=1}^{N} (y_i – \bm{w}^T \phi(\bm{x}_i))^2 + \frac{\lambda}{2} \|\bm{w}\|^2 $$ 行列形式で書くと（$\bm{\Phi} = [\phi(\bm{x}_1), \dots, \phi(\bm{x}_N)]^T$） $$ \min_{\bm{w}} \frac{1}{2} \|\bm{y} – \bm{\Phi}\bm{w}\|^2 + \frac{\lambda}{2} \|\bm{w}\|^2 $$ 解は $$ \bm{w}^* = (\bm{\Phi}^T \bm{\Phi} + \lambda \bm{I})^{-1} \bm{\Phi}^T \bm{y} $$ ですが、$\phi(\bm{x})$ が高次元（あるいは無限次元）の場合、$\bm{\Phi}^T \bm{\Phi}$ は巨大（あるいは無限次元）で直接計算できません。 双対形式への変換 主問題の最適性条件（勾配を0とおく）から $$ \bm{\Phi}^T(\bm{\Phi}\bm{w} – \bm{y}) + \lambda \bm{w} = \bm{0} $$ $$ \bm{w} = \frac{1}{\lambda} \bm{\Phi}^T (\bm{y} – \bm{\Phi}\bm{w}) $$ ここで $\bm{\alpha} = \frac{1}{\lambda}(\bm{y} – \bm{\Phi}\bm{w})$ とおくと $$ \bm{w} = \bm{\Phi}^T \bm{\alpha} = \sum_{i=1}^{N} \alpha_i \phi(\bm{x}_i) $$ これは、最適な $\bm{w}$ がデータ点の特徴ベクトルの線形結合で表せることを意味します（リプレゼンター定理の特殊な場合）。 $\bm{w} = \bm{\Phi}^T \bm{\alpha}$ を主問題に代入します。予測値は $$ \bm{\Phi}\bm{w} = \bm{\Phi}\bm{\Phi}^T \bm{\alpha} = \bm{K}\bm{\alpha} $$ ここで $\bm{K} = \bm{\Phi}\bm{\Phi}^T$ はグラム行列で、$K_{ij} = \langle \phi(\bm{x}_i), \phi(\bm{x}_j) \rangle = k(\bm{x}_i, \bm{x}_j)$ です。 正則化項は $$ \|\bm{w}\|^2 = \bm{w}^T\bm{w} = \bm{\alpha}^T \bm{\Phi} \bm{\Phi}^T \bm{\alpha} = \bm{\alpha}^T \bm{K} \bm{\alpha} $$ 双対問題は $$ \min_{\bm{\alpha}} \frac{1}{2} \|\bm{y} – \bm{K}\bm{\alpha}\|^2 + \frac{\lambda}{2} \bm{\alpha}^T \bm{K} \bm{\alpha} $$ $\bm{\alpha}$ で微分して 0 とおくと $$ -\bm{K}(\bm{y} – \bm{K}\bm{\alpha}) + \lambda \bm{K} \bm{\alpha} = \bm{0} $$ $\bm{K}$ が正則であれば（$\bm{K} + \lambda \bm{I}$ は常に正則） $$ \bm{K}\bm{\alpha} + \lambda \bm{\alpha} = \bm{y} $$ $$ \bm{\alpha}^* = (\bm{K} + \lambda \bm{I})^{-1} \bm{y} $$ 新しいデータ点での予測 新しいデータ点 $\bm{x}_*$ での予測は $$ f(\bm{x}_*) = \bm{w}^{*T} \phi(\bm{x}_*) = \sum_{i=1}^{N} \alpha_i^* k(\bm{x}_i, \bm{x}_*)= \bm{k}_*^T \bm{\alpha}^* = \bm{k}_*^T (\bm{K} + \lambda \bm{I})^{-1} \bm{y} $$ ここで $\bm{k}_* = (k(\bm{x}_1, \bm{x}_*), \dots, k(\bm{x}_N, \bm{x}_*))^T$ です。 この式は $\phi(\bm{x})$ を一度も明示的に計算しておらず、カーネル関数 $k(\cdot, \cdot)$ のみで計算が完結しています。これがカーネルトリックの真髄です。 計算量の比較 形式 逆行列サイズ 計算量 有利な場合 主問題 $(\bm{\Phi}^T\bm{\Phi} + \lambda\bm{I})$: $D \times D$ $O(D^3)$ $D \ll N$ 双対問題 $(\bm{K} + \lambda\bm{I})$: $N \times N$ $O(N^3)$ $N \ll D$ or $D = \infty$ 特徴空間の次元 $D$ が非常に大きい（あるいは無限の）場合、双対形式が唯一の実行可能なアプローチとなります。 Python での実装と可視化 各種カーネルの可視化 import numpy as np import matplotlib.pyplot as plt def linear_kernel(X1, X2): """線形カーネル""" return X1 @ X2.T def polynomial_kernel(X1, X2, degree=3, c=1.0): """多項式カーネル""" return (c + X1 @ X2.T) ** degree def rbf_kernel(X1, X2, gamma=1.0): """RBFカーネル（ガウスカーネル）""" sq_dists = np.sum(X1**2, axis=1, keepdims=True) - 2 * X1 @ X2.T + np.sum(X2**2, axis=1, keepdims=True).T return np.exp(-gamma * sq_dists) def laplacian_kernel(X1, X2, gamma=1.0): """ラプラスカーネル""" # L1距離の計算 dists = np.sum(np.abs(X1[:, None, :] - X2[None, :, :]), axis=2) return np.exp(-gamma * dists) # 1次元データでカーネル関数の形状を可視化 x_fixed = np.array([[0.0]]) # 固定点 x_range = np.linspace(-3, 3, 200).reshape(-1, 1) fig, axes = plt.subplots(2, 2, figsize=(12, 10)) # 線形カーネル k_linear = linear_ker