Coursera MachineLearning 7週目 まとめ

MachineLearning


機械学習界隈で評判高いCourseraのMachineLearningを受講したので、講義内容を個人的にまとめてみたいと思います。
7週目は、サポートベクターマシン(Support Vector Machine)とカーネル(kernel)についてです。


 

Support Vector Machine

例のごとく、ある細胞がガンで「ある」か「ない」かを、発現している遺伝子の状態から判断する2値分類を行いたいとします。

既にはっきりと分かれていますが、二つのカテゴリーに分ける決定境界はどのように引くことができるでしょうか?
Support Vector Machine は、両側にマージンを残しつつ決定境界を引くことで最適な分類を目指します。

このマージンはどのようにして与えられるのか?について見ていきましょう。
Support Vector Machine でもいつものように目的関数を求める必要がありますが、まずはロジスティック回帰の目的関数から見ていき、それをちょちょいと変形していきます。

具体的には、目的関数に含まれる以下の2つの項に変更を加えていくことになります。


ロジスティック回帰では、以下のような場合分けを行っていました。

  • (i) \(y=1\)(悪性腫瘍) を予測したい場合 … \(y=1\)を示す時に、\(z >> 0\) で目的関数Jが最小になる。(\(y=0\)を示す時は、\(z << 0\) で最大(∞)になる)
  • (ii) \(y=0\)(良性腫瘍) を予測したい場合 … \(y=0\)を示す時に、\(z << 0\) で目的関数Jが最小になる。(\(y=1\)を示す時は、\(z >> 0\) で最大(∞)になる)

このような場合分けを行うと、以下の2種類のグラフが得られます。
(\(y=1\) の時は \(z >> 0\) で最小の値を示し、\(y=0\) の時は \(z << 0\) で最小の値を示すようなパラメーター\(θ\)を求めていました)

Support Vector Machines では、上記の2項を以下のように解釈します。

場合分けも以下のように変更します。

  • (i) \(y=1\)(悪性腫瘍) を予測したい場合 … \(y=1\) を示す時に、\(z ≧ 1\) で \(cost_1{(z)}\)が 0 になる。(\(y=0\)を示す時は、\(z << 1\) で最大(∞)になる)
  • (ii) \(y=0\) (良性腫瘍) を予測したい場合 … \(y=0\) を示す時に、\(z ≦ -1\) で \(cost_0{(z)}\)が 0 になる。(\(y=1\)を示す時は、\(z >> -1\) で最大(∞)になる)

曲線だった各項のグラフを直線で表し、\(y = 1\) の時は \(z ≧ 1\) で目的関数が 0 になる!
\(y = 0\) の時は \(z ≦ -1\) で目的関数Jが 0 になる!と条件を大きく変更してしまいます。

変更に伴って各項を\(cost(z)\)で置き換えた Support Vector Machine の目的関数は、以下のようになります。

\(\frac{1}{m}\) は取り除かれています。(最小になる時の値は\(m\)に依存しないので、ここは取り除いても問題ないようです)
また、正則化パラメーター \(λ\) が 新規のパラメーター \(C\) に置き変わっています。
ロジスティック回帰では正則化に\(λ\)というパラメーターを使用しましたが、Support Vector Machine では\(C\)というパラメーターを用います。
目的関数を最小化するために、ロジスティック回帰では、第2項に負荷をかけて第1項を最適化しました。 Support Vector Machineでは、第1項が小さくなるように\(C\)をかけることで、第2項に間接的に負荷をかけていきます。

つまり、ロジステック回帰の目的関数に\(\frac{m}{λ}\)をかけたものが、Support Vector Machineの目的関数となります。(パラメーター \(C = \frac{1}{λ}\)とみなすことができます)

これで、Support Vector Machineの目的関数を得ることができました!となりそうなのですが、もう少し続きがあります。

Support Vector Machineでは 、\(cost(z)\)が 0 になるような場合分けを行いました。これはつまり、Support Vector Machineの目的関数の第1項は 0 になりうるということです。以下のような場合には、第1項が 0 になりますね。

ということは、目的関数が最小になる際には必ず、第1項は0になっているはずです。
これらのことからSupport Vector Machineでは、目的関数の第2項を最小にすることを目指します。

次に、これらがどのようにマージンの幅に繋がるか?についてみていきます。

Mathematics Behind Large Margin Classification

いくつかの性質を復習しましょう。


とすると、以下のように表すことができます。



 

  • \(||u||\) (ノルム): ベクトル\(u\)の長さ(実数)
  • \(p\) : ベクトル\(v\)のベクトル\(u\)への射影の長さ(実数。ベクトルによってはプラスにもマイナスにもなる(\(u\) と \(v\) のなす角が90°以上になる))

目的関数の第二項は以下のように書き換えることができます。

つまり、Support Vector Machines の目的関数の最小値を求めるということは、 パラメータ\(θ\)のノルム\(||θ||\)(ベクトル\(θ\)の長さ)の二乗を最小化しようと試みるということになります。

この時の条件は、以下のように表すことができます。(\(p\)はベクトル\(x\)のベクトル\(θ\)への射影の長さ)

目的関数の第1項が0になる条件を書き換えています。
\(||θ||\) は2乗するので、\(||θ||\)を大きくしてしまうと、目的関数の値も一気に大きくなってしまいます。
すなわち、以上の2条件を満たしつつ目的関数を小さくしようと思うと、「射影の長さ\(p\)」を大きくする必要があります。

\(||θ||\)を最小の値にするべく、\(1\)~ \(i\)番目の\(p\)がそれぞれ大きな値となるようにみていきます。
この「射影の長さ\(p\)」が、SVMのマージンの正体です。

パラメーター\(C\) は\(\frac{1}{λ}\) に対応していて、、、
\(C\)が大きすぎなければ(正則化パラメーター\(λ\)が大きければ)、より良い決定境界を引くことができます。(マージンが広がる)
\(C\)をとても大きい値になると(正則化パラメーター\(λ\)が小さくなると)、一つの外れ値に敏感になります。(マージンが狭くなる)

この章で説明したものは、線形回帰のような直線の分類器を与えるSVMでした。主に、特徴量の数 \(n\) が多く、サンプル数 \(m\) が少ない場合などに用いられます。(非線形の分類だと、十分なサンプル数がなければ、オーバーフィットのリスクがあります)

kernel 1


Support Vector Machinesで以下のような非線形分類をしたい場合、どうすればよいのでしょうか?
ここでは、カーネル法と呼ばれる方法を用いて分類を行なっていきます。

上の例のようなSVMによる線形分類では、うまく分類が行えなさそうです。そこでカーネル法と呼ばれる方法を用います。
同一平面乗に、周りのある一定の範囲を判定する点「ランドマーク」を複数設置することで、非線形分類を行います。

はじめに、カーネルは新しい特徴量\(f\)を定義します。

\(x\):手持ちのデータ                             
\(l\):ランドマーク(\(x\)と同次元上にある点)

この\(similarity\)関数は、カーネル関数とも呼ばれます。今回の講義で示されるのはガウシアンカーネル(gaussian kernel)と呼ばれ、\(x\) と \(l^{(i)}\)(ランドマーク)がどれほど類似しているか?を示します。(\(k_{(x,l^{(i)})}\)と記述することもあるみたいです)

\(x\) と \(l^{(i)}\)(ランドマーク)の一つ \(l^{(1)}\) が 近い場合、上記式の分子は近似的に0(\(e\)の0乗)になるので、\(f_{1} = 1\)となります。
反対に、それらの距離が遠い場合、上記式の分子は大きな数字になるので、
\(e^{-\frac{(LargeNumber)^{2}}{2σ^{2}}}\) となり、\(f_{1} = 0\)となります。

以上のようにして、カーネルはxと\(l^{(i)}\)がどれだけ近いか(類似しているか)を示しています。
実際には多くのランドマーク\(l^{(1)}\),\(l^{(2)}\),\(l^{(3)}\),\(l^{(4)}\),\(l^{(5)}\)… を取り、それぞれのランドマークに対し、新しい特徴量として\(f_{1}\),\(f_{2}\),\(f_{3}\),\(f_{4}\),\(f_{5}\)… と定義していきます。手持ちのとあるデータ\(x\)に対して、設定したランドマークの数だけ特徴量の数も増えていくことになります。

また\(σ^{2}\)はガウシアンカーネルのパラメータで、
\(σ^{2}\)を小さくすれば、\(x\)とランドマーク\(l^{(i)}\)が離れた時の\(f_{i}\)の変化量は大きくなり、\(σ^{2}\)を大きくすれば、\(x\)とランドマーク\(l^{(i)}\)が離れた時の\(f_{i}\)の変化量は小さくなります。

●カーネル関数が類似性を示すことは分かったけど、これらを利用してどんな仮説が得られるのか?

多項回帰にて、\(x_{1}\), \(x_{2}\), \(x_{1}x_{2}\), \(x_{2}^{2}\) などの \(x\) で表現していた説明変数を、\(f\)に変換します。
例として、ランドマークを3点取った場合の仮説(hypothesis function)は以下のようになります。

training set の\(x^{(1)}\)はランドマーク\(l^{(1)}\)から近いか、遠いか? \(l^{(2)}\)は? \(l^{(3)}\)は? … と見ていき、そこで得られた\(f_{1}\), \(f_{2}\), \(f_{3}\) の値から上記の仮説を計算し、\(x^{(1)}\)の分類 \((y^{(1)} = 1 or 0)\) を行ないます。
これを、 \(x^{(2)}\)では?\(x^{(3)}\)では?…と training set の数だけ行なっていきます。

ランドマークとカーネル関数を定義し、以上のことを行なっていくことで、非線形の決定境界を学習させることができるというわけです。

kernel 2

実際にカーネルというアイディアを使うには、どうしたら良いのかについてみていきます。(バイアス分散のトレードオフにはどのように関係するか?なども併せて確認します)

ランドマークはどのように取ったらいいのか?

先ほどの例では3点を手動で取りましたが、複雑な学習問題になってくると更に多くのランドマークが必要になってくるはずです。そういった場合はどうすればよいのでしょうか?

講義では「training example と全く同じ場所にランドマークをとる」という方法が挙げられています。
\(x^{(1)}\)の場所には \(l^{(1)}\)、\(x^{(2)}\) の場所には \(l^{(2)}\) …、 \(x^{(m)}\) の場所には \(l^{(m)}\) という風においていきます。

\(x^{(i)}\)に対し\(f_{1}^{(i)}\),\(f_{2}^{(i)}\),\(f_{3}^{(i)}\),\(f_{4}^{(i)}\),\(f_{5}^{(i)}\), …, \(f_{m}^{(i)}\)と、\(m\)個の近似値が得られるということですね。
これは、training exampleをカーネルに当てはめていった時に、\(f\)の中の1つが必ず1になることを保証しています。

どのようにパラメーターθを得るか?

SVMの目的関数で、\(θ^{T}*x^{(i)}\) としていたところを、\(θ^{T}*f^{(i)}\)とする。正則化に関わる第2項目についても、繰り返しの数を特徴量の数\(n\)から、\(f\)の個数\(m\)に変更します。

《注意点》
サンプル数が、\(m = 10,000\) のようにとても大きい場合、計算量が膨大になります。
目的関数の最小化問題を解かなければならないときには、目的関数の第2項の \(θ^{2}\)を \(||θ||^{2}\)に変更してあげると良いそうです。また、最小値を求めるための計算は、自ら実装するのではなく、既存の高度に最適化されたソフトウェアライブラリ(liblinear や libsvm など)を使うべきとのことです。

SVMのパラメーターCにおいて、bias / variance はトレードオフの関係にある。

\(C\) は\(\frac{1}{λ} に対応していて…

  • 正則化パラメーター\(λ\) が大きいほど\(C\)は小さくなります。
                              ⇨ Higher bias, Lower variance(アンダーフィット方向へ)
  • 反対に正則化パラメーター\(λ\)が小さいほど\(C\)は大きくなります。
                              ⇨Lower bias, Higher variance(オーバーフィット方向へ )

また\(σ^{2}\)はガウスカーネルのパラメータで…

  • \(σ^{2}\)を大きくすれば、\(x\)とランドマーク\(l\)が離れた時の\(f\)の変化量は小さくなります。
              ⇨ Higher bias / Lower variance (アンダーフィット方向へ)
  • \(σ^{2}\)を小さくすれば、\(x\)とランドマーク\(l\)が離れた時の\(f\)の変化量は大きくなります。
              ⇨ Lower bias / Higher variance (オーバーフィット方向へ)

Gaussian kernel は、\(n\) = number of features が少なく、\(m\) = number of training examples が多い場合などに用いられます。講義内では具体的な数字が挙げられていて、\(n\) = 1-1000 , \(m\) = 10 – 10000(50000くらいまでなら問題なし)の場合には有効のようです。
\(m\) がさらに多く50000以上になってくる場合は、\(n\) を増やすか、ロジスティック回帰またはカーネルを使用しないSVMを使用した方が良いとのこと。


 

左のような平面のグラフを、右のグラフのようにして分類するようなカーネル法もあるそうなのですが、今回は違うみたいですね。
8週目は、教師なし学習「クラスタリング」「主成分解析(PCA)」について学習していきます。

コメント

タイトルとURLをコピーしました