めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

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

何の話かというと

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

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

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

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

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

  • 上記の例は、データの配置にあわせて、うまいこと z 軸方向の変形をしているのでうまくいっているのですが、カーネル法には、データの配置にあわせてうまいこと変形するような仕組みは組み込まれていません。なので、この説明だけでは、なぜ、カーネル法がうまく機能するかという本質が実はまったく見えないです。
  • カーネル法は、最適化問題を双対問題に置き換えて解くという解法に特徴があって、その結果として得られる解は、「学習データについての和を取る」という非常に特殊な形式をしています。そのため、学習データが多い場合は、予測時の計算量が大きくなるという課題を持っています。このあたりの特性を抜きにして、「高次元空間を使って解くのがカーネル法」とさらっと言われると、ものすごく気持ち悪いですよね。。。

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

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

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

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

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

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

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

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

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

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

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

\mathbf x =\{x_1,x_2,\cdots,x_K\}

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

\bf \phi =\{\phi_1(\mathbf x),\phi_2(\mathbf x),\cdots,\phi_M(\mathbf x)\}

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

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

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

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

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

K(\mathbf x, \mathbf y) =\sum_{m=1}^M\phi_m(\mathbf x)\phi_m(\mathbf y) ---- (1)

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

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

 f(\mathbf x) = \sum_{n=1}^N\alpha_nK(\mathbf x,\mathbf x_n) ---- (2)

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

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

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

カーネルの決定方法

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

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

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

えーーーーーーー。

っと思うでしょう。

ふふふふふふふふふ。

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

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

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

K(\mathbf x,\mathbf y)=\exp\left(-\frac{|\mathbf x - \mathbf y|^2}{2\sigma^2}\right) ---- (3)

の場合、後で説明するように、なんと、無限個の \phi_1(\mathbf x),\phi_2(\mathbf x),\cdots を用いて、K(\mathbf x,\mathbf y) が構成されることがわかります。

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

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

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

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

 \phi_{\mathbf r}(\mathbf x) = C\exp\left(-\frac{|\mathbf x-\mathbf r|^2}{2\sigma^2}\right) ---- (4)

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

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

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

・・・・・・? どういうこと?

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

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

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

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

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

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

はい。そういうことです。上記は2項分類の場合ですが、回帰問題であれば、\alpha_n をトレーニングデータ \mathbf x_n のラベル値 t_n に比例するようにして、適切な定数で割り算して正規化しておけば、近くのデータとなるべく同じ値をとるように予測することになります。前述の双対問題を解くと、結果として、そんな感じの \alpha_n が決まります。

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

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

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

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

PRML Figure 5.21 を再現するコード

何の話かというと

A Neural Representation of Sketch Drawings でスケッチの次のストロークを予測するモデルとして、混合ガウス分布が使われており、ガウス分布の混合係数、平均、分散を Latent Variable z を入力とする RNN で計算するという手法が用いられています。

上図のデコーダ部分の出力 y が混合係数、平均、分散にあたります。その後、この分布から次のストロークのサンプルを取得することで、非決定的に画像を生成します。

このモデルは、Bishop先生のMixture Density Networksが元ネタになっており、PRMLにも解説があります。そこで、勉強のためにPRMLで紹介されているサンプルをTensorFlowで実装してみました。

モデルの説明

座標 x に依存して、平均と分散が変化する正規分布 {\mathcal N}(t\mid \mu(x),\sigma^2(x)) を3つ混合したモデルを考えます。

\displaystyle p(t\mid x) = \sum_{k=1}^3 \pi_k(x){\mathcal N}(t\mid \mu_k(x),\sigma_k^2(x))
\displaystyle\sum_{k=1}^3 \pi_k(x)=1

ここで、混合係数 \pi_k(x) も座標に依存します。さらに、平均、分散、混合係数の x に対する依存性は、ニューラルネットワークで計算されます。ここでは、一例として、5ノードの隠れ層を1層だけ持つモデルを使用します。

このモデルを用いて、下記のデータセットを学習すると、3つのパートを個別の正規分布でフィッティングできるものと期待されます。

誤差関数には、対数尤度の符号違いを用います。

\displaystyle E(\theta) = -\sum_{n=1}^N\log\left\{\sum_{k=1}^3\pi_k(x_n,\theta){\mathcal N}(t_n\mid \mu_k(x_n,\theta),\sigma_k^2(x_n,\theta))\right\}

TensorFlowを用いて実装した結果が下記になります。

実際のコードはこちらです。


Mixture Density Network

DQN implementation for Open AI Gym CartPole-v0

References

github.com

Hands-On Machine Learning With Scikit-Learn and Tensorflow: Concepts, Tools, and Techniques to Build Intelligent Systems

Hands-On Machine Learning With Scikit-Learn and Tensorflow: Concepts, Tools, and Techniques to Build Intelligent Systems

Implementation