2020-02-08

サポートベクターマシン（ハードマージン）（２）

サポートベクターマシン

サポートベクターマシン（ハードマージン）（１）の続きです。先回、求める解は

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

を、

$t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b) \ge 1 \quad\quad (n=1,\cdots,N) \tag{2}$

という2次計画問題となることを確認しました。この問題を解きやすい形にするため、2次計画における双対問題の手順に沿って双対問題を導出します。手順は、

ラグランジュ関数を作る
$\displaystyle \frac{\partial L}{\partial \mathbf{w}}=0$ 、 $\displaystyle \frac{\partial L}{\partial b}=0$ を求める
求めた $\mathbf{w},b$ を使って、ラグランジュ関数から $\mathbf{w},b$ を消去する
双対問題が完成。もとのラグランジュ関数に比べ、制約条件が少なく、解くのが簡単になる。

です。まず手順１。不等式制約におけるラグランジュの未定乗数法（KKT条件）より、ラグランジュ乗数 $a_n$ を用いれば、ラグランジュ関数は

$\displaystyle L(\mathbf{w},b,\mathbf{a}) = \frac{1}{2} \| \mathbf{w} \|^{2} - \sum_{n=1}^{N} a_n ( t_n (\mathbf{w}^{T} \phi(\mathbf{x}_n)+b)-1) \,\,\,\,\,\,\,\, (a_n\ge0)\tag{3}$

と書けます。

次に手順２。 $\displaystyle \frac{\partial L}{\partial \mathbf{w}}=0$ 、 $\displaystyle \frac{\partial L}{\partial b}=0$ を計算すれば*1、

$\begin{eqnarray*} \displaystyle \frac{\partial L}{\partial \mathbf{w}}=\mathbf{w} - \sum_{n=1}^{N}a_n t_n \phi(\mathbf{x}_n) &=& 0 \tag{4} \\ \mathbf{w} &=& \sum_{n=1}^{N}a_n t_n \phi(\mathbf{x}_n) \tag{5} \end{eqnarray*}$

$\displaystyle \frac{\partial L}{\partial b} = \sum_{n=1}^{N}a_n t_n = 0 \tag{6}$

です。

次に手順３・４。式(5)、(6)を、式(3)のラグランジュ関数に代入して $\mathbf{w},b$ を消去して双対問題 $\tilde{L}$ を作ります。まずそのまま代入すれば、

$\begin{equation*} \begin{split} \displaystyle \tilde{L}(\mathbf{a})&= \frac{1}{2} \left( \sum_{n=1}^{N}a_n t_n \phi(\mathbf{x}_n) \right)^{T} \left( \sum_{n=1}^{N}a_n t_n \phi(\mathbf{x}_n)\right) \\ &- \sum_{n=1}^{N}a_n t_n \left( \sum_{m=1}^{N}a_m t_m \phi(\mathbf{x}_m) \right)^{T} \phi(\mathbf{x}_n) +\sum_{n=1}^{N}a_n \end{split} \end{equation*} \tag{7}$

です。式(7)右辺の１番目の項は、カーネル関数を用いて $k(\mathbf{x}_i,\mathbf{x}_j) = \phi^{T}(\mathbf{x}_i)\phi(\mathbf{x}_j)$ とすれば、

$\displaystyle \frac{1}{2} \sum_{n=1}^{N}\sum_{m=1}^{N} a_n t_n a_m t_m k(\mathbf{x}_n,\mathbf{x}_m) \tag{8}$

と書けます。同様に式(7)右辺の2番目の項も計算すれば、

$\displaystyle - \sum_{n=1}^{N}\sum_{m=1}^{N} a_n t_n a_m t_m k(\mathbf{x}_n,\mathbf{x}_m) \tag{9}$

です。したがって、双対問題は

$\displaystyle \tilde{L}(\mathbf{a}) = \sum_{n=1}^{N}a_n -\frac{1}{2} \sum_{n=1}^{N}\sum_{m=1}^{N} a_n t_n a_m t_m k(\mathbf{x}_n,\mathbf{x}_m) \tag{10}$

となります。なおここで、

$\displaystyle \sum_{n=1}^{N} a_n t_n =0 \tag{11}$

$a_n \ge 0 \tag{12}$

です。

最適解においては、不等式制約におけるラグランジュの未定乗数法（KKT条件）で示すKKT条件が成立します。今回の問題におけるKKT条件は以下です。

$a_n \ge 0 \tag{13}$

$t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b) -1 \ge 0 \tag{14}$

$a_n \{ t_n ( \mathbf{w}^{T}\phi(\mathbf{x}_n)+b) -1 \} = 0 \tag{15}$

続きは次回。

*1:参考：ベクトルの微分

2020-02-04

2次計画における双対問題

最適化

$f(\mathbf{x})$ の最大値を、

${\displaystyle \begin{eqnarray} \left\{ \begin{array}{l} g_1(\mathbf{x})\le0 \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\vdots \\ g_m(\mathbf{x})\le0 \tag{1} \end{array} \right. \end{eqnarray} }$

${\displaystyle \begin{eqnarray} \left\{ \begin{array}{l} h_1(\mathbf{x})=0 \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\vdots \\ h_l(\mathbf{x})=0 \tag{2} \end{array} \right. \end{eqnarray} }$

の制約条件下で求めることを考えます。この問題において、 $f(\mathbf{x})$ が上に凸の2次関数で、制約条件が線形制約の場合、2次計画と呼びます。2次計画の問題を解くには、双対定理がよく使われるようです。この双対定理の背景にある理論は僕にとっては難解でなかなか理解が難しかったので、とりあえず解き方の手順だけを整理してみました。

まず、ラグランジュ関数を作ります。*1

$\displaystyle L(\mathbf{x},\boldsymbol \lambda ,\boldsymbol \mu) = f(\mathbf{x}) - \sum_{i=1}^{m} \lambda_{i} g_i(\mathbf{x}) - \sum_{i=1}^{l} \mu_{i} h_{i}(\mathbf{x}) \tag{3}$

解においては、不等式制約におけるラグランジュの未定乗数法（KKT条件）より、KKT条件

$\lambda_i g_i(\mathbf{x}) = 0 \tag{4}$ $\lambda_i \ge 0 \tag{5}$ $g_i(\mathbf{x}) \leq 0 \tag{6}$

が成り立ちます。ここで、 $L(\mathbf{x},\boldsymbol \lambda ,\boldsymbol \mu)$ は凸関数ですから、最大値においては $\displaystyle \frac{\partial L}{\partial \mathbf{x}}=\mathbf{0}$ が成り立ちます。 $\displaystyle \frac{\partial L}{\partial \mathbf{x}}=\mathbf{0}$ を用いてラグランジュ関数から $\mathbf{x}$ を消去すると、双対問題

$l(\boldsymbol \lambda ,\boldsymbol \mu) \tag{7}$

が得られます（KKT条件より $\lambda_i \ge0$ ）。これを最小にする $\boldsymbol \lambda ,\boldsymbol \mu$ を求めます。すると、式(3)、(7)に解が存在するなら、その最大値と最小値は一致し、この性質を双対定理と呼びます。もとのラグランジュ関数よりも双対問題のほうが解きやすいために、2次計画問題ではこの手法がよく用いられるようです。

*1:参考：ラグランジュの未定乗数法、不等式制約におけるラグランジュの未定乗数法（KKT条件）

2020-02-02

20年1月の振り返り

不労所得

正月休みのボーナス期間でWeb収入は好調。が、月末にかけて急激に尻すぼみ状態で、2月はこのブログに記録を残して以来の最低額を更新するかもしれない。

投信のほうはいろいろ事情があって、いったんNISAを除いて全て処分することに。1月上旬に処分したあと、相場は急落。全く予見していたわけではないのですが、結果的にはベストなタイミングで処分できた。あくまでも短期的にはですけど。まあいずれ再開するつもりです。でもいったん処分しちゃうと、再開するなら大きな下落相場を迎えてからがいいなあと思ってしまいます。

20年1月の実績

Web収入	投信前月比評価損益	計
880,615円	117,835円	998,450円

2020-01-22

サポートベクターマシン（ハードマージン）（１）

サポートベクターマシン

サポートベクターマシンにはハードマージン/ソフトマージンという分類があります。訓練データが線形分離可能であるという前提をおいたものをハードマージン、そうでないものをソフトマージンと呼びます。まずはハードマージンを見ていきます。下図はサポートベクターマシンで分類問題を解いた結果例です。緑色で強調した点がサポートベクトルと呼ばれる点です。分類境界を作っているのはこのサポートベクトルのみであり、その他の点は境界に一切影響しないのが特徴です。

f:id:opabinia2:20200122224207p:plain

分類境界が $y(\mathbf{x})=\mathbf{w}^{T}\phi(\mathbf{x})+b$ で与えられるとすれば、訓練データ点 $\mathbf{x}_n$ と境界までの距離 $d_n$ は、直線と点の距離より、

$\displaystyle | d_n | = \frac{|y(\mathbf{x}_n)|}{\|\mathbf{w}\|} = \frac{|\mathbf{w}^{T}\phi(\mathbf{x}_n)+b|}{\|\mathbf{w}\|}\tag{1}$

です。

問題の前提をハードマージン、つまり訓練データが線形分離可能としていますから、データのラベルを $t_n \in \{-1,1\}$ とすれば常に $t_n y(\mathbf{x}_n) \gt 0$ となります。また、 $t_n$ をかけても大きさは変わりませんから、

$\displaystyle d_n = \frac{t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b)}{\|\mathbf{w}\|} \tag{2}$

のように絶対値を外すことができます。

最大マージン分類器で書いた通り、サポートベクターマシンは、分類境界と最も近い点との距離（マージン）を最大にするような分類境界を求めることが目標です。マージンが最大となる $\mathbf{w},b$ は、

$\newcommand{\argmax}{\mathop{\rm arg~max}\limits} \newcommand{\min}{\mathop{\rm min}\limits} \displaystyle \argmax_{\mathbf{w},b} \left( \min_{n} \frac{t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b)}{\|\mathbf{w}\|} \right) \tag{3}$

です。ややこしいですが、内側の $\min$ は、分類境界と最も近い $n$ 番目のベクトルを指し、このようなベクトルが境界から最も遠くなる $\mathbf{w},b$ を選ぶというのが式(3)の意味です。まあ要するにマージンを最大化するということです。

ここで、 $\mathbf{w} \rightarrow \kappa\mathbf{w}$ 、 $b \rightarrow \kappa b$ とすると、式(2)の右辺は

$\begin{eqnarray*} \displaystyle \frac{t_n(\kappa \mathbf{w}^{T}\phi(\mathbf{x}_n)+\kappa b)}{\kappa \|\mathbf{w}\|} &=&\frac{t_n\kappa (\mathbf{w}^{T}\phi(\mathbf{x}_n)+ b)}{\kappa \|\mathbf{w}\|} \tag{4}\\ &=& \frac{t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b)}{\|\mathbf{w}\|} \tag{5}\\ &=&d_n \tag{6} \end{eqnarray*}$

となり、結局距離 $d_n$ は変わりません。 $\kappa$ によって任意に $\mathbf{w},b$ をスケーリングできるわけですから、境界に最も近い点に対して、

$t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b) = 1 \tag{7}$

となるように $\mathbf{w},b$ を選ぶことができます。これを式(3)に代入すれば、

$\newcommand{\argmax}{\mathop{\rm arg~max}\limits} \displaystyle \argmax_{\mathbf{w},b} \frac{1}{\|\mathbf{w}\|} \tag{8}$

となります。式(8)を最大にする $\mathbf{w},b$ は、 $\|\mathbf{w}\|^{2}$ を最小にする $\mathbf{w},b$ と同じです。したがって求める $\mathbf{w},b$ は

$\newcommand{\argmin}{\mathop{\rm arg~min}\limits} \displaystyle \argmin_{\mathbf{w},b} \frac{1}{2}\|\mathbf{w}\|^{2} \tag{9}$

と書けます。 $\frac{1}{2}$ をかけているのは、微分したときにきれいな形にするためのもので、あってもなくても求められる解は同じです。また、わざわざ2乗しているのは、後で書くように2次計画問題にもっていきたいからです*1。なお $b$ は式(7)の制約がありますから、消えているわけではありません。

式(7)は、分類境界から最も近い点までの距離が1であるということですから、その他の点までの距離は1より大きいといえます。

以上より、

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

を、

$t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b) \ge 1 \quad\quad (n=1,\cdots,N) \tag{11}$

という不等式制約条件下での2次関数の最小問題を解けば良いことになります。制約条件が線形で、目的関数が凸の2次形式であるこのような問題を2次計画と呼ぶようです。

続き：サポートベクターマシン（ハードマージン）（２）

*1:詳しく調べていないのですが、そうしないと解を求めるのが大変、、、なのだと思います。

2020-01-14

直線と点の距離

線形代数・ベクトル

下図に示すような点 $\mathbf{a}$ から、直線 $y(\mathbf{x})=\mathbf{w}^{T}\mathbf{x}+b=0$ におろした垂線との交点 $\mathbf{h}$ との距離を考えます。

直線 $y(\mathbf{x})$ の法線ベクトルは $\nabla y=\mathbf{w}$ （参考：法線ベクトルと勾配）ですから、

$\displaystyle \mathbf{a} - \mathbf{h} = d \frac{\mathbf{w}}{\| \mathbf{w} \|} \tag{1}$

となる実数 $d$ が存在します。式(1)において $\displaystyle \frac{\mathbf{w}}{\| \mathbf{w} \|}$ は $\mathbf{w}$ 方向への単位ベクトルです。したがって $|d|$ は点 $\mathbf{a}$ から $\mathbf{h}$ までの距離を表します。使っている文字が1次関数 $y=ax+b$ と似ててややこしいですが、 $y(\mathbf{x})=w_1 x_1+w_2 x_2+b=0$ を想定しています。

式(1)より

$\displaystyle \mathbf{h} =\mathbf{a}- d \frac{\mathbf{w}}{\| \mathbf{w} \|} \tag{2}$

です。ここで $\mathbf{h}$ は直線 $y(\mathbf{x})=0$ 上の点ですから、

$\begin{eqnarray*} \displaystyle \mathbf{w}^{T} \left( \mathbf{a} - d \frac{\mathbf{w}}{\|\mathbf{w}\|} \right) + b &=& 0 \tag{2} \\ \displaystyle \mathbf{w}^{T}\mathbf{a} - d \frac{\mathbf{w}^{T}\mathbf{w}}{\|\mathbf{w}\|} + b &=& 0 \tag{3} \end{eqnarray*}$

です。ベクトルのノルムの式(5)より $\mathbf{w}^{T}\mathbf{w} = \| \mathbf{w} \|^{2}$ ですから、

$\begin{eqnarray*} \mathbf{w}^{T}\mathbf{a} - d \| \mathbf{w}\| + b &=& 0 \tag{4} \\ \displaystyle d &=& \frac{\mathbf{w}^{T}\mathbf{a}+b}{ \|\mathbf{w}\| } \tag{5} \\ &=& \frac{y(\mathbf{a})}{\|\mathbf{w}\|} \tag{6} \end{eqnarray*}$

です。したがって、点 $\mathbf{a}$ から直線 $y(\mathbf{x})$ におろした垂線の距離 $d$ は、

$\displaystyle |d| = \frac{|y(\mathbf{a})|}{\|\mathbf{w}\|} \tag{6}$

です。直線でなくとも、曲線でも平面でも同じ式で距離が求められます。

2020-01-12

最大マージン分類器

サポートベクターマシン

2クラスの分類問題を

$y(\mathbf{x}) = \mathbf{w}^{T}\phi(\mathbf{x})+b \tag{1}$

で識別することを考えます。*1　このとき、分離できる解は複数存在します。例えばパーセプトロンの場合、係数の初期値によって下図のように複数の解が求まります。

f:id:opabinia2:20200112121236p:plain

最大マージン分類器では、分離境界から最も近くの訓練データまでの距離をマージンと定義し、このマージンが最大となるような解を求めます。そして、分離境界からマージンだけ離れた点をサポートベクトルと呼びます。下図のようなイメージです。

このように、マージンを最大化するという考えのもとに分類する手法をサポートベクターマシンと呼ぶようです。サポートベクトルマシンとも呼ぶようですが、ベクターのほうがかっこいい。次回以降、解の求め方を確認していきますが、識別モデルはカーネル関数を使って表されます。つまりサポートベクターマシンはカーネル法と同様、無限次元を扱うことができるモデルです。（参考：ガウスカーネル）　そして、カーネル法では新たな入力に対する結果を求めるのに、全ての訓練データを用いる必要がありましたが、サポートベクターマシンでは、計算に使われるのはサポートベクトルのみです。メモリ上に多くのデータを持つ必要がないなどのメリットがあるのかな。この特性を、疎な解を持つ、あるいはスパースな解、と呼ぶようです。

*1:参考：線形識別の概要

2020-01-04

カーネル法の目次

カーネル法

機械学習に詳しくなりたいブログ

機械学習や数学について勉強した内容を中心に書きます。100％趣味です。記事は数学的に厳密でなかったり誤りを含んでいるかもしれません。ご指摘頂ければ幸いです。

サポートベクターマシン（ハードマージン）（２）

2次計画における双対問題

20年1月の振り返り

20年1月の実績

サポートベクターマシン（ハードマージン）（１）

直線と点の距離

最大マージン分類器

カーネル法の目次

カーネル法の概要

カーネル回帰分析

ガウス過程

ガウス過程による回帰

ガウス過程による分類

必要な数学知識

関連