機械学習におけるカーネル法について

何の話かというと

機械学習におけるカーネル法の説明で、よく登場するのがこちらの図です。

左側の (x, y) 平面上の点を分類する場合、このままだと線形分類器（直線で分類するアルゴリズム）ではうまく分類できないのが、右図のように z 軸を追加してデータを変形すると、平面できれいに分割できるようになって、線形分類器による分類がうまくいくというものです。このように、高次元空間にデータを埋め込むことでうまいこと分類するのがカーネル法の仕組みだというわけです。

なのですが・・・・・・・・・・・・・・・・・・・・

これ、本当にカーネル法の原理を知っている方には、ちょっと気持ち悪くないですか？

※ 以下はカーネル法を知っている方向けのつぶやきです。

• 上記の例は、データの配置にあわせて、うまいこと z 軸方向の変形をしているのでうまくいっているのですが、カーネル法には、データの配置にあわせてうまいこと変形するような仕組みは組み込まれていません。なので、この説明だけでは、なぜ、カーネル法がうまく機能するかという本質が実はまったく見えないです。

• カーネル法は、最適化問題を双対問題に置き換えて解くという解法に特徴があって、その結果として得られる解は、「学習データについての和を取る」という非常に特殊な形式をしています。そのため、学習データが多い場合は、予測時の計算量が大きくなるという課題を持っています。このあたりの特性を抜きにして、「高次元空間を使って解くのがカーネル法」とさらっと言われると、ものすごく気持ち悪いですよね。。。

というわけで、実際の所、カーネル法が何をやっているのかをできるかぎり正確に説明した上で、なぜ、カーネル法がうまく機能するのかをがんばって説明しようというのがこのエントリーです。

なお、以下の説明では、特徴量はすべて数値型データだとします。カテゴリーデータは取り扱い対象外とします。

特徴量エンジニアリングについて

現実の機械学習モデルを作る場合、ナマの学習データ x1,x2,⋯$x_1,x_2,\cdots$ をそのまますべてモデルに入力するということは、それほど多くはありません。予測したい内容やデータに対する既知の知見を活用して、予測に影響を与えるデータを選択したり、複数のデータを組み合わせて事前に計算した結果を入力値に使うということをします。このような作業を一般に「特徴量エンジニアリング」と言います。冒頭の例であれば、x,y をモデルに入力する代わりに、z=x2+y2$z=x^2+y^2$ を入力すれば、z のある値を境にして2種類のデータがきれい分類できるということになります。

特徴量エンジニアリングの自動化問題

冒頭の例であれば、元のグラフをじーーーーーっと眺めれば、数学の心得がある人であれば、z=x2+y2$z=x^2+y^2$ を使えばいいじゃん！というのはすぐに分かります。しかしながら、現実のデータセットでは、グラフをじーーーーっと眺めただけで思いつくようなことはほとんどありえません。というか、そもそもグラフを描くこと自体がつらいです。従って、データが本来的にもっているであろう性質やら、過去の試行錯誤の経験を元に、手探りで特徴量エンジニアリングを進めていくことになります。

だったら、いっその事、考えられる計算式を全部自動で構成して、うまくいくやつを自動的に発見するような仕組みをつくってしまえば・・・という気にもなります。たとえば、scikit-learn には、sklearn.preprocessing.PolynomialFeatures という関数が用意されており、これを用いると、学習データに対して、指定した次数までの積を自動で構成することができます。（x, y に対して、2次を指定すると、x2,y2,xy$x^2,y^2,xy$ の3種類の特徴量が出てきます。）さらに、Feature selection の機能を使うと、ここからデータの特性をよりよく反映するであろう特徴量を自動で選択するということもできます。

とはいえ・・・・・・・・・・・・

これもまた容易に想像できることですが、もともとの変数の数が多くなると、考えられる組み合わせの数は爆発的に増加します。さらに、先ほどの sklearn.preprocessing.PolynomialFeatures は、単純な変数同士の積をとるだけですが、それ以外のより複雑な関数まで考え出すときりがありません。

特徴量空間とカーネルトリック

というような問題は、一旦、横においておき、ここで一度、「多数の特徴量を用意して、それらをモデルに入力する」という操作をもう少し正確に定義しておきましょう。今、ナマの変数が K 個あるとして、これらを

x={x1,x2,⋯,xK}$\mathbf{x}=\{x_1,x_2,\cdots ,x_K\}$

と表します。そして、ここから、M 個の特徴量を計算したとします。

ϕ={ϕ1(x),ϕ2(x),⋯,ϕM(x)}$\varphi \mathbf{=}\{{\varphi }_{\mathbf{1}}\mathbf{(}\mathbf{x}\mathbf{)}\mathbf{,}{\varphi }_{\mathbf{2}}\mathbf{(}\mathbf{x}\mathbf{)}\mathbf{,}\cdots \mathbf{,}{\varphi }_{\mathbf{M}}\mathbf{(}\mathbf{x}\mathbf{)}\}$

記号で書くと抽象的ですが、ϕ1(x)=x21${\varphi }_1(\mathbf{x})=x_1^2$ とか、ϕ2(x)=x1x2${\varphi }_2(\mathbf{x})=x_1{x}_2$ のように、それぞれの ϕ$\varphi$ は、ナマの変数を組み合わせた計算式に過ぎません。ただし、ここでは、M は K に比べて膨大に大きな数であるとします。つまり、膨大な数の組み合わせ計算を用意しているのです。

次に、これまで、x={x1,x2,⋯,xK}$\mathbf{x}=\{x_1,x_2,\cdots ,x_K\}$ を用いて計算していた、素朴な線形モデルを１つ用意します。冒頭のような２項分類問題であれば、SVM（サポートベクターマシン）などでもよいでしょう。そして、これまで、x={x1,x2,⋯,xK}$\mathbf{x}=\{x_1,x_2,\cdots ,x_K\}$ を代入していたところをすべて ϕ={ϕ1(x),ϕ2(x),⋯,ϕM(x)}$\varphi =\{{\varphi }_1(\mathbf{x}),{\varphi }_2(\mathbf{x}),\cdots ,{\varphi }_M(\mathbf{x})\}$ に置き換えて計算します。ただこれだけです。何も特別なことはしていません。

ただし。。。。従来の素朴な線形モデルの解法に、そのまま ϕ={ϕ1(x),ϕ2(x),⋯,ϕM(x)}$\varphi =\{{\varphi }_1(\mathbf{x}),{\varphi }_2(\mathbf{x}),\cdots ,{\varphi }_M(\mathbf{x})\}$ を入れると、M がとても大きな数であることから、計算量が膨大になり、大変なことになります。

ここで登場するのが、「カーネルトリック」と呼ばれる解法です。細かいところは適用対象の問題によって変わるのですが、大雑把には、この手法を用いると、次のような特徴を持った「別解」が得られます。

• 特徴量に関する計算は、すべて、次の形で計算に含まれる。（この関数をカーネル関数と呼びます。）

K(x,y)=∑Mm=1ϕm(x)ϕm(y)$K(\mathbf{x},\mathbf{y})=\sum _{m=1}^M{\varphi }_m(\mathbf{x}){\varphi }_m(\mathbf{y})$ ---- (1)

• 計算量は M ではなく、トレーニングセットのデータ数 N に依存する。（従って、M が大きくても、N が小さければ計算量は問題にならない。）

たとえば、前述の SVM であれば、大雑把には、次のような形の解が得られます。

f(x)=∑Nn=1αnK(x,xn)$f(\mathbf{x})=\sum _{n=1}^N{\alpha }_{n}K(\mathbf{x},{\mathbf{x}}_n)$ ---- (2)

ここでは、関数 f(x)$f(\mathbf{x})$ の符号によって、点 x$\mathbf{x}$ にある新しいデータのラベル t=±1$t=\pm 1$ が予測できると考えてください。また、係数 αn${\alpha }_n$ は、事前に、ある最適化問題（双対問題と呼ばれます）の解として、値が決まります。

これで、無事に M が膨大な場合でも適用できる解法が見つかりました。めでたしめでたし・・・・・・。

な、わけがありませんね。

カーネルの決定方法

上記の説明だけをさらっと読むと、めでたく問題が解決された気になりますが、実は、そんなことはありません。まず (1) をどうやって計算するのかという問題が残っています。M が膨大という前提なので、この計算は大変です。また、そもそも、ϕ={ϕ1(x),ϕ2(x),⋯,ϕM(x)}$\varphi \mathbf{=}\{{\varphi }_{\mathbf{1}}\mathbf{(}\mathbf{x}\mathbf{)}\mathbf{,}{\varphi }_{\mathbf{2}}\mathbf{(}\mathbf{x}\mathbf{)}\mathbf{,}\cdots \mathbf{,}{\varphi }_{\mathbf{M}}\mathbf{(}\mathbf{x}\mathbf{)}\}$ を具体的にどう設定するかという、特徴量エンジニアリングに関する根本の問題が残っています。大量の組み合わせを使えると言っても、実際、どういう関数を持っているのがよいのか、何か指針が必要です。

実は、実際にカーネル法を利用する場合は、この点について、おどろくべき斬新な解決策を持ち出します。

関数 K(x,y)$K(\mathbf{x},\mathbf{y})$ を適当に手で決めるのです。

えーーーーーーー。

っと思うでしょう。

ふふふふふふふふふ。

大部分のカーネル法の解説では、このとんでもない飛躍があまりにもさらっと流されるので、みなさん、意味がわからなくなるのではないでしょうか？

順を追って説明しましょう。

まず、関数 K(x,y)$K(\mathbf{x},\mathbf{y})$ を適当に決めた時、これがある一定の条件を満たしていれば、何らかの ϕ={ϕ1(x),ϕ2(x),⋯,ϕM(x)}$\varphi \mathbf{=}\{{\varphi }_{\mathbf{1}}\mathbf{(}\mathbf{x}\mathbf{)}\mathbf{,}{\varphi }_{\mathbf{2}}\mathbf{(}\mathbf{x}\mathbf{)}\mathbf{,}\cdots \mathbf{,}{\varphi }_{\mathbf{M}}\mathbf{(}\mathbf{x}\mathbf{)}\}$ を用いて、(1) の形でその関数が書き表せることが数学的に証明されています。たとえば、よく使われるガウスカーネル

K(x,y)=exp(−|x−y|22σ2)$K(\mathbf{x},\mathbf{y})=\exp (-\frac{|\mathbf{x}-\mathbf{y}{|}^2}{2{\sigma }^2})$ ---- (3)

の場合、後で説明するように、なんと、無限個の ϕ1(x),ϕ2(x),⋯${\varphi }_1(\mathbf{x}),{\varphi }_2(\mathbf{x}),\cdots$ を用いて、K(x,y)$K(\mathbf{x},\mathbf{y})$ が構成されることがわかります。

従って、とりあえず、(3) のカーネルを用いて、先ほどの解法を適用すれば、謎の無限個の特徴量を用いて SVM を実行した場合と同等の結果が得られます。「無限個の特徴量」の正体が気になりますが、思い切り割り切って考えるならば、「無限個の特徴量があれば、きっと有用な特徴量もいっぱい含まれているに違いない」と期待することができます。つまり、あまり深く考えずに、とりあえずガウスカーネルを突っ込んでおけば、ナマの変数を用いた線形 SVM よりはずっとよい結果が期待できるというわけです。

ガウスカーネルに対応する特徴変数

・・・と、ここで終わると、「そんな適当なことでいいんかい？」とモヤモヤする人もいると思うので、先ほどのガウスカーネルの正体を説明します。

先に答えを言うと、無限個の ϕ(x)$\varphi (\mathbf{x})$ は、ナマのパラメーター空間 x$\mathbf{x}$ 上の点 r$\mathbf{r}$ をパラメーターとして、

ϕr(x)=Cexp(−|x−r|22σ2)${\varphi }_{\mathbf{r}}(\mathbf{x})=C\exp (-\frac{|\mathbf{x}-\mathbf{r}{|}^2}{2{\sigma }^2})$ ---- (4)

で与えられます。C$C$ は適当な定数値です。1次元の場合の証明が、こちらにあるので参考にしてください。多次元の場合も計算方法は同じです。

(4) は、点 r$\mathbf{r}$ を頂点とする山形の関数です。冒頭のシンプルな例で登場した z=x2+y2$z=x^2+y^2$ は原点を頂点とした（上下逆さまの）山形ですが、これと同様の山形の値を持った新しい座標をすべての点について用意していることになります。

ここで、すべての点を z 軸方向に持ち上げているわけではない点に注意してください。ϕ1,ϕ2,⋯${\varphi }_1,{\varphi }_2,\cdots$ はすべて異なる座標軸ですので、これはつまり、すべての点 x=r$\mathbf{x}=\mathbf{r}$ をそれぞれに別の次元方向に引き伸ばしているのです。

・・・・・・？　どういうこと？

と思った方は・・・すいません。。。。無限次元空間が脳内に想像できないタイプの方のようなので、次の一節はこらえて読み飛ばしてください。。。。

無限次元空間が脳内に想像できる方は、もう、お分かりかと思います。すべての点を別の次元方向に伸ばしているということは、この無限次元空間であれば、すべての点を完璧に区別できてしまうのです。これなら、どれほど複雑なデータ配置であっても、線形関数で完璧に分離することができることになります。無限次元ってすごいなぁ。。。

もう少し違う見方をしてみましょう。

いま、ある点 x=x0$\mathbf{x}={\mathbf{x}}_0$ の周りに、トレーニングセットのデータ x1,x2,⋯${\mathbf{x}}_1,{\mathbf{x}}_2,\cdots$ がばら撒かれていたとします。この時、先ほどの無限次元空間の座標を用いて、どのデータが一番近いかを判別することができます。ϕx0(x1),ϕx0(x2),⋯${\varphi }_{{\mathbf{x}}_0}({\mathbf{x}}_1),{\varphi }_{{\mathbf{x}}_0}({\mathbf{x}}_2),\cdots$ の中で、値が一番大きいものを見つければよいのです。つまり、この無限次元空間の座標を利用すると、実質的にk近傍法が実装できるのです。

実際、先に紹介した (2) の解は、k近傍法とほぼ同等になっています。K(x,xn)$K(\mathbf{x},{\mathbf{x}}_n)$ は2点 x,xn$\mathbf{x},{\mathbf{x}}_n$ の距離が近いほど大きな値をとります。従って、係数 αn${\alpha }_n$ をトレーニングデータ xn${\mathbf{x}}_n$ のラベル値 tn=±1$t_n=\pm 1$ と同じ符号にしておけば、各トレーニングデータに対して、近くにあるもののラベルをより大きな重みで参照して、点 x0${\mathbf{x}}_0$ のラベル値を予測しているということになります。また、カーネル関数に含まれるパラメーター σ$\sigma$ を大きくすると、より遠くのデータまで参照することになるので、これは、k近傍法における、kの値を大きくすることと同等の効果になります。

なーーーーんだ。そういうことなのか。。。。。

はい。そういうことです。ただ、ガウスカーネルの場合は特に極端で、先の σ$\sigma$ を思い切り小さくすれば、k 近傍法で k=1$k=1$ とした場合と同じで、いくらでもオーバーフィットさせることができてしまいます。なので、実際には、オーバーフィットしないように、σ$\sigma$ を適度に調整する必要があります。いわゆるハイパーパラメーターチューニングです。

あるいは、データの特性に応じて、ガウスカーネルとは異なる関数をカーネルに用いた方が、より汎化性能が高い結果が得られる可能性も十分にあります。結局、この部分に関しては、絶対的な解法はなくて、問題領域ごとに、適切なカーネルを見つけていくという人手の作業は残るということになります。ただ、(2) の形が本質的にk近傍法と同等なのは変わりなく、トレーニングデータとの「距離」K(x,xn)$K(\mathbf{x},{\mathbf{x}}_n)$ によって、点 x$\mathbf{x}$ のラベルを判断しているという事実は変わりません。ガウスカーネルの場合は、2点のユークリッド距離が近ければ、データのラベルも同じ可能性が高いと判断するわけですが、この仮説は常に正しいとは限りません。データの類似度が高くなる場所について、K(x,xn)$K(\mathbf{x},{\mathbf{x}}_n)$ の値が大きくなるような関数をうまく選べば・・・・って、それがどんな場所だか分からない苦労しているわけなんですが。ぐぬぬぬぬ(*)。

(*) 時系列データで24時間周期の周期性があるとかが、事前知識として分かっている場合は、時間軸方向に24時間周期の関数を用いるとか、そんなテクニックは考えられます。こういうドメインナレッジをいかにしてカーネル関数に注入するかが、現実的には、カーネル法の肝になります。もしくは、こういうドメインナレッジをカーネル関数を通して、うまく注入できるところが、カーネル法のメリットと言えるかも知れません。

あと、ちなみに、(2) はトレーニングデータの和になっているので、当然ながら、トレーニングデータが膨大にある場合は、予測処理そのものの計算量が膨大になってしまいます。これもk近傍法と同じ課題ですね。