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

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

20年3月の振り返り

相場はひどいですね。先月と同じことを言ってしまいますが、売っておいて本当によかった。なんかもうこの辺だったら何を買っても利益が出るような気がする。と思いながらもまだ何にも手を出していない。

20年3月の実績
Web収入 投信 前月比評価損益
759,282円 - 759,282円
20年の累積
Web収入 投信評価損益
2,337,090円 117,835円 2,454,925‬円

2020年2月の振り返り

なんだかんだで2月のWeb収入はそこそこに落ち着いた。

投信は先月売っておいて本当に良かった。今月もすごい勢いで下落していて、仮に持ち続けていたら200万くらいはマイナスでした。下落の勢いがすごいぶん、戻るスピードも速いかもしれません。また買い始めるのをいつにするか難しい。結局、戻ったところで買い始めたら、持ち続けてたのと同じというかむしろ安いところで買わなかった分、損じゃんって話なんですよね。全処分してダメージを避けたので、積立自体はすぐに再開するのが良いような気もする。

20年2月の実績
Web収入 投信 前月比評価損益
697,193円 - 697,193円
20年の累積
Web収入 投信評価損益
1,577,808‬円 117,835円 1,695,643‬円

サポートベクターマシン(ハードマージン)(2)

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


\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次計画における双対問題の手順に沿って双対問題を導出します。手順は、

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

です。まず手順1。不等式制約におけるラグランジュの未定乗数法(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}

と書けます。

次に手順2。\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}

です。

次に手順3・4。式(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)右辺の1番目の項は、カーネル関数を用いて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}

続きは次回。

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次計画問題ではこの手法がよく用いられるようです。

20年1月の振り返り

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

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

20年1月の実績
Web収入 投信 前月比評価損益
880,615円 117,835円 998,450円

サポートベクターマシン(ハードマージン)(1)

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

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次計画と呼ぶようです。

続き:サポートベクターマシン(ハードマージン)(2)

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

直線と点の距離

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

f:id:opabinia2:20200114225421p:plain


直線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}

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