はじめまして！ @tsum_tsum です！
某会社でエンジニアをしており、ソフトウェア開発会社の AI 系の部門に勤めて約 3 年になりました。
そろそろ勉強だけでなく、アウトプットもしていこうと Qiita に記事を書きたいと思います！
初心者なので、何かミスがありましたらお手柔らかくご指摘いただければと思います…。
一番最初の記事はカーネルトリックについてです！生成 AI やらディープラーニングが世の中に出回っているなか、今更感がありますが…。個人的には統計を勉強していた時、一番最初に感動した概念なんですよね。ということで、自己紹介も程々に実際にカーネルトリックについて話していければと思います～
はじめに
-
カーネルトリックについてわかりやすく解説したつもりの記事ですが、認識の違いや誤った理解をしている可能性があります。間違いを発見された方は、お手数ではございますがコメント欄にてご指摘いただければと思います。
-
既にカーネルトリックをご存じの方向けではありますが、今回のカーネルトリックの解説はリッジ回帰にカーネルトリックを適用した場合について解説いたします。下記に記載されている内容については紹介しませんので、あらかじめご了承ください。
- カーネルトリックに関する厳密な理論
- カーネルトリックのPCAへの適用など、別機械学習手法への適用
- 本記事に登場する諸数式の証明
-
また、こちらの本、記事を参考にしております。ご興味のある方はこちらも合わせてご覧いただければ幸いです。
上記の資料はカーネルトリックを理解する上で非常に助けになりましたので、この場をお借りし執筆者に感謝を申し上げたいと思います。少し数学的で難しい部分もあるかもしれませんが、カーネルトリックのより理論的な部分について知りたい方はぜひご一読ください！
（オーソドックスな）線形回帰
まずは、線形回帰から紹介していきます。この記事を読んでくれている方には簡単すぎるかもしれません。順を追って色々と定義していきたいと思います。
データ集合を
{\mathcal X} = \{ \text{x}_1, \cdots ,\text{x}_N \} \subset {\mathbb R}^d,
予測値を
{\mathcal Y} = \{ y_1, \cdots, y_N \}\subset {\mathbb R}
とします。$ \text{x}_i =(x_{i1}, \cdots, x_{id}) \in {\mathcal X}$ に対し、一般的な線形回帰を考えてみます。
y = w_0 + w_1 x_1 + \cdots + w_d x_d \ (w_0, \cdots, w_d \in {\mathbb R})
を仮定し、実際に代入します。
{\tilde y}_i = w_0 + w_1 x_{i1} + \cdots + w_d x_{id} \ (i = 1, \cdots,N)
から、残差平方和
\begin{eqnarray}
L(w_0, \cdots, w_d) &=& \sum_{i=1}^N (y_i - {\tilde y}_i)^2 \\
&=& \sum_{i=1}^N (y_i - (w_0 + w_1 x_{i1} + \cdots + w_d x_{id}))^2
\end{eqnarray}
が最小になるような $w_0, \cdots, w_d$ を求めることで回帰式を求める…という計算方法が一般的かと思います。さて、
\begin{eqnarray}
\phi(\text{x}) &=& (1, x_1, \cdots, x_d)^T, \\
\text{w} &=& (w_0, \cdots, w_d)^T
\end{eqnarray}
とおいてみましょう。（定義を列ベクトルにしたくて、転置を付けていることに注意してください。筆者が途中間違えて書き直してます。）すると、
y = \text{w}^{T} \cdot \phi(\text{x})
と表せます。
さて、この式を見ると、多変数のベクトル値関数 $\phi$ と、係数ベクトル $\text{w}$ で構成されていることが分かります。こうなると「$\phi$ ってもっと複雑な関数にしてもいいじゃね？」ってなるのが数学屋の感覚ですよね…？（知らんがな）
非線形回帰
さきほど、「$\phi$ ってもっと複雑な関数にしてもいいんじゃね？」と述べました。では、
\begin{eqnarray}
\phi(\text{x}) &=& (\phi_0(\text{x}), \phi_1(\text{x}), \cdots , \phi_H(\text{x}))^T \\
\text{w} &=& (w_0, \cdots, w_H)^T
\end{eqnarray}
とします。ただし、$\phi_0, \cdots, \phi_H$ はスカラー値を取る多変数関数です。
ここで注意なのは、$d$ ではなく $H$ を用いている点です。$\phi = (1, x_1, \cdots, x_d)^T$ としていた先の例と違い、$\phi$ がデータの次元と一致する必要性はありません。例えば、$\phi = (1, x_1, x_2)^T$ とすれば、$\text{w} = (w_0, w_1, w_2)$ となりますが、今回の例では、$\phi = (\sin (x_1+x_2), \cos(x_1x_2))^T$ としても問題ないです。この場合は当然 $\text{w} = (w_0, w_1)$ で考える必要がありますね。
さて本題に戻りましょう。上記のような場合でも、
y = \text{w}^{T} \cdot \phi(\text{x})
のように、同じ式で表すことが可能です。
では、この式に実際にデータを入れてみましょう。データ$ \text{x}_i $に対して、
\tilde{y}_i = \text{w}^{T} \cdot \phi (\text{x}_i) \ (i=1,\cdots,N)
とおくと、
\tilde{\text{y}} =
\begin{pmatrix}
\tilde{y}_1 \\
\vdots \\
\tilde{y}_N \\
\end{pmatrix}
=
\begin{pmatrix}
\phi_0(\text{x}_1) & \cdots & \phi_H(\text{x}_1) \\
\phi_0(\text{x}_2) & \cdots & \phi_H(\text{x}_2) \\
\vdots & \ddots & \vdots \\
\phi_0(\text{x}_N) & \cdots & \phi_H(\text{x}_N) \\
\end{pmatrix}
\begin{pmatrix}
w_0 \\
w_1 \\
\cdots \\
w_H
\end{pmatrix}
=\Phi(\text{x}) \text{w}
となりました。
リッジ回帰
リッジ回帰は、先ほど紹介した残差平方和に少し工夫を凝らしたものです。もとの残差平方和は下記のような式でした。
\begin{eqnarray}
L(w_0, \cdots, w_d) &=& \sum_{i=1}^N (y_i - {\tilde y}_i)^2 \\
&=& \sum_{i=1}^N (y_i - (w_0 + w_1 x_{i1} + \cdots + w_d x_{id}))^2.
\end{eqnarray}
一方、リッジ回帰は残差平方和に $c \text{w} \cdot \text{w}^T \ (c > 0)$ を足したもので表されます。
\begin{eqnarray}
L(w_0, \cdots, w_d) &=&
c \text{w} \cdot \text{w}^T + \sum_{i=1}^N (y_i - {\tilde y}_i)^2 \\
&=&
c (w_0^2 + \cdots + w_d^2) + \sum_{i=1}^N (y_i - (w_0 + w_1 x_{i1} + \cdots + w_d x_{id}))^2.
\end{eqnarray}
何のために $\text{w} \cdot \text{w}^T$ を足すのかという話ですが、一般の線形回帰の場合、取得されるデータのわずかな違いに $w_i$ の値が大きく影響されてしまうという問題点があったりします。リッジ回帰の式をあらためて見てみると、$w_0^2 + \cdots + w_d^2$ は常に正の値ですね。$L$ を最小にするには、$w_0, \cdots , w_d$ が極力小さな値になる必要があります。この調整によって、$w_i$ の値が影響を受けにくくなるというメリットがあるんですね。
ちなみに、リッジ回帰は $w_i$ に正規分布（かつそれぞれの $w_i$ は独立である）を事前分布として仮定した線形回帰と等価になります。
w_i \overset{i.i.d.}{\sim} \mathcal{N}(0, \sigma^2) .
この辺りはカーネルトリックの趣旨とはずれてしまうので、詳細は割愛します。
カーネルトリックの入口へ…
いよいよカーネルトリックの入口へと向かっていきます。ここから少しずつ面白いと思っているところに進んでいくので、諦めずに読んでいただければと思います…！
まず、非線形回帰は下記のような式で表されるのでした。
y = \text{w}^{T} \cdot \phi(\text{x}) .
ただし、
\begin{eqnarray}
w &=& (w_0, \cdots, w_H)^T \\
\phi(\text{x}) &=& (\phi_0(\text{x}), \phi_1(\text{x}), \cdots , \phi_H(\text{x}))^T
\end{eqnarray}
です。そして、$\text{x} \in \mathcal{X} $ と $y \in \mathcal{Y}$ にデータと特徴を全て代入すると、
\tilde{\text{y}} = \Phi(\text{x}) \text{w}
と表せるのでした。さて、先のリッジ回帰で紹介したように、
w_i \overset{i.i.d.}{\sim} \mathcal{N}(0, \sigma^2) \ (i = 0, \cdots, H)
を仮定します。このとき、$\text{w}$ は $H+1$ 次元の多変数正規分布に従います。
\text{w} \sim \mathcal{N}(\mathbf{0}, \sigma^2 \mathbf{I}).
ただし、$\mathbf{I}$ は 単位行列です。このとき、$\text{y} = \Phi(\text{x}) \text{w}$ も同じように多変数正規分布に従います。では、どのような正規分布に従うか実際に計算してみましょう。期待値（ベクトル）、共分散（行列）はそれぞれ、
\begin{eqnarray}
\mathbb{E}[ \text{y} ] &=& \mathbb{E}[ \Phi(\text{x})\text{w}] \\
&=& \Phi(\text{x}) \mathbb{E}[\text{w}] \\
&=& 0, \\
\mathbb{V}[ \text{y} ] &=& \mathbb{E}[\text{y} \text{y}^T] - \mathbb{E}[\text{y}] \mathbb{E}[\text{y}]^T \\
&=& \mathbb{E}[\Phi(\text{x})\text{w} (\Phi(\text{x})\text{w})^T] - \mathbb{E}[\Phi(\text{x})\text{w}] \mathbb{E}[\Phi(\text{x})\text{w}]^T \\
&=& \mathbb{E}[\Phi(\text{x})\text{w}\text{w}^T \Phi(\text{x})^T] - \Phi(\text{x}) \mathbb{E}[\text{w}]\mathbb{E}[\text{w}]^T \Phi(\text{x})^T \\
&=& \Phi(\text{x})\mathbb{E}[\text{w}\text{w}^T]\Phi(\text{x})^T - \Phi(\text{x}) \mathbb{E}[\text{w}]\mathbb{E}[\text{w}]^T \Phi(\text{x})^T \\
&=& \Phi(\text{x})\mathbb{E}[\text{w}\text{w}^T]\Phi(\text{x})^T \\
&=& \sigma^2 \Phi(\text{x})\Phi(\text{x})^T
\end{eqnarray}
となります。ここで、$\mathbb{E}[\text{w}] = \mathbf{0}, \mathbb{V}[\text{w}] = \sigma^2 \mathbf{I}$ および、
\begin{eqnarray}
\mathbb{V}[\text{w}] &=& \mathbb{E}[\text{w}\text{w}^T] - \mathbb{E}[\text{w}]\mathbb{E} [\text{w}^T] \\
\mathbb{E}[\text{w}\text{w}^T] &=& \sigma^2 \mathbf{I}
\end{eqnarray}
となることに注意してください。さて、ここで重要なことが分かってきます。まず先の計算から、$\text{y} \sim \mathcal{N}(\mathbf{0}, \sigma^2 \Phi(\text{x})\Phi(\text{x})^T)$ であることが分かります。そして、期待値を取ったことにより、$\text{w}$ が消えていますね。このことから、非線形回帰＋リッジ回帰を組み合わせたモデルでは $\text{w}$ の値は（モデリングをする上で）必要ないということが分かります。（まぁ $\text{w}$ の事前分布を設定してるんだから当たり前でしょ）
この部分が機械学習を始めて勉強した時の最初の感動ポイントだったことを覚えています。教師あり機械学習を勉強し始めると、学習データにもっとも当てはまりのいい係数を求めたりすることがあると思います。しかし、 係数を求めないけど予測値（実際には予測値の取る分布）を求められるよ！ って何か感動しません？（私だけかも…）
ちょっと話が横道に逸れてしまいました…。ここからはいよいよカーネルトリックを紹介していきたいと思います！
カーネルトリックとは？
さきほど、$\text{y}$ の分布が下記であることを求めました。
\text{y} \sim \mathcal{N}(\mathbf{0}, \sigma^2 \Phi(\text{x})\Phi(\text{x})^T).
この共分散行列を
\text{K} = (k(\text{x}_i, \text{x}_j))_{1\le i,j \le N} = \sigma^2 \Phi(\text{x})\Phi(\text{x})^T
とおくと、
\Phi(\text{x})\Phi(\text{x})^T =
\begin{pmatrix}
\phi_0(\text{x}_1) & \cdots & \phi_H(\text{x}_1) \\
\phi_0(\text{x}_2) & \cdots & \phi_H(\text{x}_2) \\
\vdots & \ddots & \vdots \\
\phi_0(\text{x}_N) & \cdots & \phi_H(\text{x}_N) \\
\end{pmatrix}
\begin{pmatrix}
\phi_0(\text{x}_1) & \cdots & \phi_0(\text{x}_N) \\
\phi_1(\text{x}_1) & \cdots & \phi_1(\text{x}_N) \\
\vdots & \ddots & \vdots \\
\phi_H(\text{x}_N) & \cdots & \phi_H(\text{x}_N) \\
\end{pmatrix}
より、$k(\text{x}_i, \text{x}_j) = \sigma^2 \phi(\text{x}_i)^T \phi(\text{x}_j)$ が分かります。さて、ここから計算をさらに進めていこうとします。普通に考えると、
- $\phi$ を決定する
- $k(\text{x}_i, \text{x}_j)$ が計算できる
という順番になるはずです。しかし、カーネルトリックでは違います。 $k$ が簡単に計算できるような "都合のいい" $k$ を選べばいい のです。ではどんな $k$ を選べば、都合よく計算できるでしょうか？
正定値カーネル
先の章では、 $k$ が簡単に計算できるような "都合のいい" $\phi$ を選ぶ といいました。ここでは、その関数の満たす条件を考えましょう。
$\text{K}$ は正規分布の共分散行列であることを思い出してください。ということはどんな行列でもいいというわけではないですね。この条件を満たすには、$k$ が 正定値カーネル という特徴を有している必要があります。正定値カーネルとは、下記の条件$1, 2$を満たすような関数（写像）です。
- 任意の $\alpha, \beta \in \mathcal{X}$ に対し、
が成り立つ。
k(\alpha, \beta) = k(\beta, \alpha) - 任意の $\alpha_1, \cdots, \alpha_n \in \mathcal{X}, \text{c} = (c_1, \cdots, c_n)^T \in \mathbb{R}^n$ に対し、
が成り立つ。
\sum_{i=1}^n \sum_{j=1}^n c_i c_j k(\alpha_i, \alpha_j) = \text{c}^T \mathbf{K} \text{c} \ge 0
そして、$k$ が正定値カーネルのとき、$\mathbf{K}$ をグラム行列といいます。
定義だけでは分かりにくいところがあると思いますので、具体的な正定値カーネルについて紹介していきましょう。
正定値カーネルの具体例
カーネルトリックの"トリック"部分を分かりやすくするために、具体的に正定値カーネルを例示したいと思います。
$\alpha = (\alpha_1, \alpha_2)^T, \beta = (\beta_1, \beta_2)^T$ とします。このとき、
k(\alpha, \beta) = (\alpha_1 \beta_1 + \alpha_2 \beta_2 + 1)^2
とおきます。この $k$ は実は正定値カーネルの条件を満たし、多項式カーネルといいます。一方で、
\begin{eqnarray}
(\alpha_1 \beta_1 + \alpha_2 \beta_2 + 1)^2 &=&
\alpha_1^2 \beta_1^2 + \alpha_2^2 \beta_2^2 + 1 + 2 \alpha_1 \alpha_2 \beta_1 \beta_2
+ 2 \alpha_1 \beta_1 + 2 \alpha_2 \beta_2 \\
&=& (\alpha_1^2, \alpha_2^2, 1, \sqrt{2}\alpha_1\alpha_2, \sqrt{2}\alpha_1, \sqrt{2}\alpha_2)^T \cdot (\beta_1^2, \beta_2^2, 1, \sqrt{2}\beta_1\beta_2, \sqrt{2}\beta_1, \sqrt{2}\beta_2) \\
&=& \phi(\alpha_1, \alpha_2)^T \phi(\beta_1, \beta_2)
\end{eqnarray}
より、$\phi(x_1, x_2) = (x_1^2, x_2^2, 1, \sqrt{2}x_1x_2, \sqrt{2}x_1, \sqrt{2}x_2)$ とすれば、$k(\alpha, \beta) = \phi(\alpha)^T \phi(\beta)$ であることが分かります。
トリックの正体
散々話を引っ張ってきましたが、いよいよ"トリック"の正体を説明していきましょう。
先の例で、
\begin{eqnarray}
\phi(x_1, x_2) &=& (x_1^2, x_2^2, 1, \sqrt{2}x_1x_2, \sqrt{2}x_1, \sqrt{2}x_2)^T \\
k(\alpha, \beta) &=& (\alpha_1\beta_1 + \alpha_2\beta_2 +1)^2
\end{eqnarray}
とおくことで、$k(\alpha, \beta) = \phi(\alpha)^T \phi(\beta)$ が成り立つことを見ました。
さて、この式に注目してほしいのですが、今求めたかったのは、$\text{y}$ の分布でした。$\text{y}$ がどんな正規分布に従うのかな～？と調べていたはずです。先の例では、説明のために $\phi$ を具体的に計算したのですが、そもそも知りたいのは $k$ であって $\phi$ の情報は不要ですよね。つまり、$\text{y}$ の分布は
\text{y} \sim \mathcal{N}(\mathbf{0}, \sigma^2 \Phi(\text{x})^T\Phi(\text{x}))
= \mathcal{N}(\mathbf{0}, \mathbf{K})
だったので、$\phi$ でさえ求める必要がない ということが分かります。トリックの正体とは、$k$ を定義するだけで分布を計算できる！という計算の工夫だったのです！！！
このトリックを初めて学んだ時に、機械学習すごいなと感心してしまいました。純粋数学を学んでた立場からすると、 機械学習の理論に対して甘く見てた 部分があったんですね。しかし、機械学習のことを知らないが故に自分の認識が甘かったな… となった記憶があります。
またまた話が脱線してしまいましたが、カーネルトリックの正体が分かったことなので、カーネルトリックの威力について説明していきましょう。
カーネルトリックの威力
カーネルトリックは都合のいい $k$ を選ぶことで、$\text{w}$ や $\phi$ を求めることなく、$\text{y}$ の分布を求めることができる計算手法のことでした。この計算手法を少し別の角度から見直してみます。
先の多項式カーネルを考えます。
\begin{eqnarray}
\phi(x_1, x_2) &=& (x_1^2, x_2^2, 1, \sqrt{2}x_1x_2, \sqrt{2}x_1, \sqrt{2}x_2)^T, \\
k(\alpha, \beta) &=& (\alpha_1\beta_1 + \alpha_2\beta_2 +1)^2 \\
&=& \phi(\alpha)^T \phi(\beta).
\end{eqnarray}
さて、$ k(\alpha, \beta) = \phi(\alpha)^T \phi(\beta)$ より、
- $k$ は $\phi(\alpha)$ と $\phi(\beta)$ の内積を求めている
と考えることができます。$\phi$ は $6$ 次元のベクトル だったので、
- $6$ 次元同士のベクトルの内積を $k$ の計算のみで求めることができる
とも考えられますね。$2$ 次元のベクトル $(x_1, x_2)$ を一旦 $6$ 次元のベクトル $(x_1^2, x_2^2, 1, \sqrt{2}x_1x_2, \sqrt{2}x_1, \sqrt{2}x_2)$ に変換してから内積を計算するより、簡単な掛け算足し算で内積を一気に計算できるので、計算資源をそれだけ節約できることが分かるかと思います。
このようにカーネルトリックは、$\phi$ という変換をしてから、内積を計算する という方法ではなく、あらかじめ都合のいい $k$ を設定することで、楽に内積を計算できる というメリットを持っています。いくら現代の計算資源が豊富になってきた時代とはいえ、計算量がこのようにして減らせるのは分析する上でも非常にありがたいですね。
まとめ
ということで、カーネルトリックについて紹介していきました！
カーネルトリック自体は高次元ベクトルの内積を簡単に計算できる計算手法のことを指しますので、カーネルトリックは機械学習の分析手法とセットで使われます。機械学習は、ベクトルの次元、つまり
- 特徴量の数は多ければ多いほど、データの豊かな情報を利用できる
という長所を持っています。一方で、
- 特徴量の数は多ければ多いほど、計算量が多くなってしまう
という欠点も抱えています。それらの問題点を同時に解消する計算テクニックとして、現在でも利用されています。
今回はカーネルトリックの"トリック"についてお話していきましたが、あくまでも非線形回帰＋リッジ回帰と組み合わせたお話にすぎません。最初にも言及しましたが、カーネルトリックは PCA（主成分分析）、SVM などの機械学習手法と組み合わせて利用されています。カーネルトリックそのものの理論についても Moore-Aronszajn の定理など、好きな定理があったりするんですが、今回は割愛いたします。いつか記事にしたいですね。
初回の投稿ということもあり、拙い文章である部分もあるかと思いますが、最後までお読みいただきありがとうございました！！！
また次回お会いしましょう！