Pythonと機械学習

Pythonも機械学習も初心者ですが、頑張ってこのブログで勉強してこうと思います。

サポートベクターマシン

名前だけ聞くとなんか凄そうなマシンに聞こえますね。

サポートベクターとはベクトルの事です。トレーニングサンプルを特徴量空間の位置ベクトルとしてみています。

決定境界に一番近いトレーニングサンプルの事をサポートベクトルといいます。サポートベクトルを使ったマシンラーニングという意味でしょうかね?

サポートベクトルと決定境界の距離をマージンと言い、サポートベクターマシンではこのマージンを最大化してあげることで決定境界を求めます。

ベクトル空間上の超平面

一般的に、あるベクトル空間{\mathbf{x}}上の超平面を表す式は以下のようにあらわすことができます。({\mathbf{x}}は横ベクトルで{\mathbf{w}}は縦ベクトルです。)

超平面という表現は、一般的なベクトル空間は3次元とは限らないので、n次元空間上の平面という意味です。

{\displaystyle
\mathbf{x}\mathbf{w}+w_0=0 \tag{1}
}

{\mathbf{w}}は超平面の法線方向ベクトルを表し、{w_0}は適当な実数です。

この時、ベクトル空間上の適当な点{\mathbf{x}_0}とこの超平面の距離は以下の式であらわされます。

{\displaystyle
\frac{|\mathbf{x}_0\mathbf{w}+w_0|}{||\mathbf{w}||} \tag{2}
}

(1)式で表される超平面を適当な定数{\alpha}倍しても、点と超平面の距離は変化しません。

{\displaystyle
\frac{|\alpha \mathbf{x}_0\mathbf{w}+\alpha w_0|}{||\alpha \mathbf{w}||} = \frac{|\mathbf{x}_0\mathbf{w}+w_0|}{||\mathbf{w}||}   \tag{3}
}

こう考えてみると、コスト関数の最小値を与える重みと、特徴量ベクトルとの積の和は決定境界を表していたんですね。一つ賢くなりました。

また、このベクトル空間上の平行な2平面{\displaystyle\mathbf{x}\mathbf{w}+w_a=0}{\displaystyle\mathbf{x}\mathbf{w}+w_b=0}間の距離は以下のように表すことができます。

{\displaystyle
\frac{|w_b - w_a|}{||\mathbf{w}||} \tag{4}
}

サポートベクトルと決定境界の距離

クラスラベルを1と-1としたときに、決定境界からクラスラベルが1(+側)にあるサポートベクトルを{\mathbf{x}_p}と書いてあげます。

このとき決定境界{\mathbf{x}\mathbf{w}+w_0=0}とサポートベクトルの距離は以下のように表されます。

{\displaystyle
\frac{|\mathbf{x}_p\mathbf{w}+w_0|}{||\mathbf{w}||} \tag{5}
}

また決定境界からクラスラベルが-1(-側)にあるサポートベクトルを{\mathbf{x}_m}と書いてあげます。同様に決定境界とサポートベクトルの距離は以下になります。

{\displaystyle
\frac{|\mathbf{x}_m\mathbf{w}+w_0|}{||\mathbf{w}||} \tag{6}
}

ここがポイントです。決定境界は以下の式を満たすように重み{\mathbf{w}}を調整して無理やり決定してやります。

{\displaystyle
\mathbf{x}_p\mathbf{w}+w_0=1 \tag{7}
}

{\displaystyle
\mathbf{x}_m\mathbf{w}+w_0=-1 \tag{8}
}

(3)式を考慮すると、重みを定数倍しても点と平面の距離は変化しないので、適当に定数倍してやることで、(7)、(8)式を満たす{\mathbf{w}}を見つけることができるわけです。

(7)、(8)式を(5)、(6)式に代入してやると、

{\displaystyle
\frac{|\mathbf{x}_p\mathbf{w}+w_0|}{||\mathbf{w}||} = \frac{|\mathbf{x}_m\mathbf{w}+w_0|}{||\mathbf{w}||} = \frac{1}{||\mathbf{w}||}   \tag{9}
}

(9)式はサポートベクトルと決定境界との距離を表しており、これが最大化すべきマージンになります。

{\displaystyle
 \frac{1}{||\mathbf{w}||}   \tag{10}
}

実際は(10)式の逆数をとって2乗し、{\frac{1}{2}}をかけた値を最小化してやります。計算しやすいようにしているだけです。

{\displaystyle
 \frac{1}{2}||\mathbf{w}||^2  \tag{11}
}

式だけ見ると、重みベクトルの内積を最小化するだけなので簡単すぎるように思えますが、他に制約条件を考慮する必要があります。

マージン最大化における制約条件

(7)式で表される超平面よりクラスラベルが1側にある、トレーニングサンプル{\mathbf{x}_i}は、以下の式を満たす必要があります。

{\displaystyle
\mathbf{x}_i\mathbf{w}+w_0 \geqq 1 ~~~~~(y_i=1) \tag{11}
}

また、同様に(8)式で表される超平面よりクラスラベルが-1側にある、トレーニングサンプル{\mathbf{x}_i}は、以下の式を満たす必要があります。

{\displaystyle
\mathbf{x}_i\mathbf{w}+w_0 \leqq -1 ~~~~~(y_i=-1) \tag{12}
}

(11)、(12)式をまとめて以下のように書けます。

{\displaystyle
y_i(\mathbf{x}_i\mathbf{w}+w_0) \geqq 1 \tag{13}
}

これがマージン最大化における満たすべき制約条件になります。

ADALINEやロジスティック回帰の時とは異なり、最適化するべきマージンに制約が付いています。

この場合はマージンの最適化に勾配効果法を使うことはできず、2次計画法という手法を使います。

次は2次計画法について考察してみたいと思います。

参考にさせて頂いたサイト