ソフトウェアエンジニアが Cousera の機械学習コーシ（7週目）に参加して学んだことをメモ代わりに共有します。今週は分類問題の大詰めで、おそらく分類問題の基礎は大体学べたような気がします。
6週目の記事もあるので良かったら読んでみてください。
Large Margin Classification
この章では SVM（Support Vector Machines）のアルゴリズムについて説明します。SVM は Large Margin Classification とも呼ばれます。その名の通り、分類問題で使われるアルゴリズムです。複雑な非線形の関数を学習する方法として利用されます。
Optimization Objective
ロジスティック回帰を例に SVM のコスト関数を説明します。まず、下記がロジスティック回帰のコスト関数です。
また、h(x) は具体的に下記の数式です。
コスト関数を少し式変形すると、 -log(h(x)) と -log(1-h(x)) が得られます。これを、 z を横軸にプロットすると下記のようなグラフになります。
ロジスティック回帰では、このグラフで得られる値をなるべく小さくするように θ を選んでいました。しかし、SVM では、このグラフを下記のように書き換えます。
重なっていてい見にくいですが、紫の2つの直線です。具体的には、1と-1を境に0と傾きのある直線に分かれています。1と-1が分岐点あるのは、後の計算上の都合です。傾きは何になろうと問題はありません。そして、y=1 の時のグラフを cost1(z) 、y=0 の時のグラフを cost0(z) と書き表すと、ロジスティック回帰のコスト関数を下記のように書き換えることができます。
ロジスティック回帰のコスト関数では全項に 1/m がかけてありましたが、これは θ へ影響を与えないので、省略されます。一方で、正則化パラメーターの λ は、全項を 1/λ で割ることで、SVM で慣例的に使われる C へと変換されます。よって、上記の数式が SVM で用いるコスト関数です。
Large Margin Intuition
SVM（Large Margin Classification）が直感的に何を行っているか説明します。
上記の緑の境界線は、誤ってはいませんが質の良い境界線だとは言えません。
一方で、上記の黒の線の境界線は、質の良い境界線だと言えることができます。何故なら、緑や紫の境界線では、簡単に分類誤差が出てしまいますが、黒の境界線ではそう簡単には分類誤差が出てこないからです。この黒の境界線を引くのに使っているアルゴリズムが、SVM（Large Margin Classification）です。
具体的にどのようなアルゴリズムかと言うと、各データから境界線のマージン（距離）が最大になるように境界線を求めいています。これによって、分類誤差を少なくなるようにしています。
また、上記のグラフを使って、SVM のコスト関数の C との相関を説明します。C が大きくなると、コスト関数に対して、外れ値による影響が大きくなるのでより厳密な境界線になります。一方、C をそれほど大きい値にすると、外れ値の影響が弱まるので、外れ値をある程度許容する境界線になります。
Mathematics Behind Large Margin Classification
この節では、前々節で導出したコスト関数が、なぜマージンを最大化しているのかを数学的に説明します。が、かなり数学的に複雑なので、簡単に説明します。
ざっくり説明すると、ベクトルの内積を使っています。ベクトルの内積とは、片方のベクトルの長さと、そのベクトルにもう片方を射影したベクトルの長さをかけ合わせます。ここで言うベクトルは、θ と各データセットのベクトルです。θ のベクトルは境界線と直角に交わるベクトルになります。それに対して、射影した各データセットのベクトルが最大になると、下記のコスト関数の2項目が最小になります。
このことから、各データセットから境界線のマージンが大きくなればなるほど、射影したベクトルが最大化されます。そして、コスト関数の2項目が最小になります。
正直、かなり端折っています。証明は理解できていますが、ここで表現するのに限界があったので、詳しく知りたい人は下記の記事を読むことを進めます。
Kernels
この章では、複雑な非線形の分類器を構築する為に SVM をどのように用いるかというのかを説明します。そして、その主な方法はカーネル（Kernel）と呼ばれる手法を用います。
Kernels I
この節では、カーネルがどういうものなのかを説明します。下記の分類を例に説明します。
上記の分類の境界線を正確に引こうとすると、高次の多項式になることが予想されます。しかし、これらの高次の多項式は、自分の欲しい物かいまいち分からないという問題があります。また、そこでは高次の多項式を用いるのは 計算量的にとても高くつくことも長い目で見れば問題になります。そこで、その問題を解決するためにカーネルという手法があります。
カーネルとは、上記の図のように、まず任意に l1, l2, l3 の目印（ランドマーク）をグラフ上に取ります。そして、学習の際にデータセットを使うのではなく、各データセットに対応した f1, f2, f3… を用います。この f は下記の similarity 関数を用いて各データセットから変換します。
この数式は数学用語では、カーネル関数と呼ばます。特に今回の数式は、ガウスカーネルと呼ばれるものです。それでは、この数式がどうのような役割を果たしているのかを説明します。
上記の図は、この数式で表される値をグラフにプロットしました。ご覧の通り、目印（ランドマーク）に近づけば近づくほど、f の値は1に近づきます。一方で、離れると0に近づきます。また、σ の値を大きくすればするほど、グラフの等高線の感覚が大きくなります。これを使って、機械学習の計算を行うと、下記のような直感を得ることができると思います。
上記の図は、各目印（ランドマーク）に近ければ各 f が1となり、遠ければ0となります。θ の値次第ではありますが、今回は θ0=-0.5, θ1=1, θ2=1, θ3=0 とします。すると、l1, l2 に近ければ f1, f2 が1となり、y=1を導出します。逆に、l3 に近くても、θ3=0 なので、結果に影響を与えません。このことから、上図のような非線形の境界線を得ることができると予想ができます。
Kernels I
この節では、ランドマークの選び方と SVM のパラメーターについて説明します。
まず、ランドマークは各データセットをそのまま使います。つまり、m個のデータセットがあったら、m個のランドマークが設定されます。
そして、各ランドマークに対して、カーネル関数を用いて、x を f に変換します。データセット数 m が5で、特徴量数 n が2だったとしたら、f の特徴量数が、5 になります。つまり、x の特徴量数は関係なく、f はデータセット数 m で、特徴量数が m のデータセットへ変換されます。
そして、上記の画像のように SVM のコスト関数で、x と f を入れ替えたコスト関数を使います。ここで、カーネル関数をロジスティック回帰で使う場合も十分に考えられると思います。ただ、カーネルの手法は、SVM と相性が良くロジスティック回帰では計算が遅くなるだけだそうです。数学的な証明は省かれましたが、ロジスティック回帰ではカーネルは使わず、SVM でカーネルを使うと考えておけば良いそうです。また、SVM を独自実装せずに既存のライブラリーを使うことを強く推奨されました。これは、行列計算をライブラリーに依存するべき理由と同じで、既存のライブラリーの方が計算量やスピードを最適化してあるからです。
最後に、SVM の各パラメータの選定方法を説明します。SVM の C が大きくなると高分散でオーバーフィッティングしやすくなります。逆に C を小さくすると高バイアスでアンダーフィッティングしやすくなります。これは、ロジスティック回帰で、正則化パラメーターの λ の対応と一緒です。一方、σ を小さくすると、ランドマークに近い値を高く評価するようになるので、高分散でオーバーフィッティングしやすくなります。逆に σを大きくすると、ランドマークから多少離れていても高く評価されるので、高バイアスでアンダーフィッティングしやすくなります。
SVMs in Practice
この章では、SVM を使う際の注意点をまとめておきます。
Using An SVM
前節で説明しましたが、SVM を独自で実装することは避けるべきです。世の中には十分に使われているライブラリーが存在するのでそれに依存するべきです。ただ、分類問題で開発者が考慮すべきなのは、どのアルゴリズムを使うかです。今まで、ロジスティック回帰、ニューラルネットワーク、SVM を学びました。この節では、どのアルゴリズムを使うべきかを説明します。
上記の表は、特徴量とデータセット数に対してどのアルゴリズムを使うべきかの対応表です。表を見て分かる通り、ロジスティック回帰とカーネルなし SVM はセットになっているます。この2つのアルゴリズムが似ているためほぼ同じような振る舞いをし、ほぼ同じパフォーマンスになるらしいです。
また、カーネルを使った SVM を用いる場合は、必ずフューチャースケーリングを行います。なぜなら、特徴量のスケールの違いで各特徴量の結果への影響度が変わってくるからです。例えば、家の価格の分類問題の場合、特徴量に部屋数と平米数があったとします。部屋数は概ね1〜5の数値になり、平米数は1000付近の数値をとると考えられます。そうなった場合、下記のカーネル関数は特徴量の数値が大きくなればなるほど0に近づいてしまい、特徴量の影響度が落ちてしまいます。
なので、フューチャースケーリングをして、各特徴量の影響度を均一にします。第二週目の記事にフューチャースケーリングのことを説明しているので、興味ある人は読んでみてください。
そして、ニューラルネットワークが対応表に存在ませんが、ニューラルネットワークはなるべく使うのを避けます。何故なら、欠点としては、 ニューラルネットワークは訓練するのに時間がかかるという問題があります。 なので、もし良い SVM 実装パッケージがあるなら、そちらの方が速く訓練が終わり、早く実行されます。なので、ニューラルネットワークは最終的な手段と思っておくと良いかもしれません。
最後に SVM で複数分類問題を解くことに触れておきます。大体の SVM のライブラリーには複数分類問題を解くための機能が実装されている場合がほとんどです。ただ、万が一実装がなかったとしても、ロジスティック回帰の場合と同様に、one vs all の考え方で同様に解くことができます。第二週目の記事に one vs all のことを説明しているので、興味ある人は読んでみてください。
最後に今週の分の宿題のコードを載せておきます。今週は SVM の実装などをする必要がなかったので、既存の数学的知識だけで解けました。
8週目の記事もあるので良かったら読んでみてください。