サポートベクトルマシンとは

/機械学習

サポートベクトルマシンとは、複数のサンプルデータを2つのクラスに分類する手法です。

空間内の点の分類

$D$ 次元空間の $N$ 個の点(${\bf x}_n$)を2つのクラスに分類する問題を考えます。$D$ 次元空間を仕切るためには、次の超平面を求める必要があります。

$$a_1x_1+a_2x_2+\cdots+a_Dx_D+b=0$$

ここで、次の関数を定義し、

$$y({\bf x})=a_1x_1+a_2x_2+\cdots+a_Dx_D+b={\bf a}\cdot{\bf x}+b$$

全ての点が、超平面のどちらかの側に分類された場合、目的変数 $t_n$ を次のように定義すると、

  • クラス1:$y({\bf x}_n)\gt0$ ならば $t_n=1$
  • クラス2:$y({\bf x}_n)\lt0$ ならば $t_n=-1$

常に、$t_ny({\bf x}_n)\gt0$ であることが分かります。このことを利用すると、点 ${\bf x}_n$ と超平面との距離は以下で求められるため、

$$\frac{|{\bf a}\cdot{\bf x}_n+b|}{|{\bf a}|}=\frac{t_n({\bf a}\cdot{\bf x}_n+b)}{|{\bf a}|}  -①$$

超平面に最近接の点(${\bf x}_n$)に対し、その距離(マージン)が最大になるような超平面(${\bf a},b$)を求める問題に帰着します。これを式で表すと以下になります。

$$\max_{{\bf a},b}\Big(\frac{1}{|{\bf a}|}\min_n[t_n({\bf a}\cdot{\bf x}_n+b)]\Big)    -②$$

問題の簡略化

②の解くことは複雑であるため、ラグランジュ未定乗数法を利用して、問題の簡略化を図ります。距離①は、超平面の係数(${\bf a},b$)を定数倍しても変わらないため、

$$t_n({\bf a}\cdot{\bf x}_n+b)=1  -③$$

とういう条件を置けば、この条件のもとで、以下の関数を最大にすればよいことになります。

$$\max_{{\bf a},b}\frac{1}{|{\bf a}|}$$

さらに、これを最大ということは、$|{\bf a}|^2$ を最小化することなので、③の条件の下で、以下の関数を最小化する問題と等価になります。

$$\min_{{\bf a},b}\frac{1}{2}|{\bf a}|^2$$

ここで、ラグランジュ未定乗数法を利用すると、次のラグランジュ関数($\lambda_n\ge0$)が、

$$L({\bf a},b,\lambda_n)=\frac{1}{2}|{\bf a}|^2-\sum_{n=1}^N\lambda_n[t_n({\bf a}\cdot{\bf x}_n+b)-1]  -④$$

停留値を取る(${\bf a},b$)を求めればよいことになります。この停留値を取る条件は以下で表されます。

$$\frac{\partial L}{\partial{\bf a}}={\bf a}-\sum_{n=1}^N\lambda_nt_n{\bf x}_n=0  -⑤$$

$$\frac{\partial L}{\partial b}=-\sum_{n=1}^N\lambda_nt_n=0$$

双対表現

双対表現とは、⑤を④に代入して得られる次のラグランジュ関数のことです。

$$\tilde{L}(\lambda_n)=\sum_{n=1}^N\lambda_n-\frac{1}{2}\sum_{n,m=1}^N\lambda_n\lambda_mt_nt_mk({\bf x}_n,{\bf x}_m)$$

ここで、$k$ はカーネル関数と呼ばれており、以下で一般に定義されます。

$$k({\bf x}_n,{\bf x}_m)\equiv\phi({\bf x})^t\phi({\bf x})={\bf x}_n\cdot{\bf x}_m$$

尚、制約条件は以下になります。

$$\frac{\partial L}{\partial b}=-\sum_{n=1}^N\lambda_nt_n=0$$

$$\lambda_n\ge0$$

 

数学
解析学、代数学、幾何学、統計分析、数学基礎、高校数学
散策路TOP
古典物理、量子力学、物性論、数学、応用数学、力学、電磁気学、相対論、熱・統計力学、解析学、代数学、幾何学、統計分析、情報

Wikipedia

 

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