学習理論の学習

統計的学習理論を学習してるときに思ったこととか

macOS にフォントを追加する

Mac その他

プログラミング言語 Rust の勉強をしていて，そのフォントを使いたかったのでメモ． 今回は Source-code-pro というフォントを手に入れる．

以下の３ステップでできる．

  1. フォントをダウンロード．今回は，URL 先に行って右上にある「Download family」をクリックすれば良い．
  2. 「Font Book」というアプリを開く．
  3. アプリの上側にあるプラスのマーク「+」をクリックし，先ほどダウンロードした Source_Code_Pro 内の .ttf で終わっているファイルを全て選択し，「開く」をクリック．設定を何もいじっていなければ，ダウンロードした Source_Code_Pro は Downloads に入っているはず．

これが終われば，フォントの設定画面で選択できるようになっているはず．

CUI を使ってダウンロードする記事は他にあるので，気になる方はそちらを参照．

SVM（Support Vector Machine，サポートベクターマシーン）その２

機械学習 最適化 統計的学習理論 SVM

　前回の記事の続きです． 前回導出した SVM の双対問題を導出します．

導入

　前回の記事では，ハードマージンSVMが解く最適化問題を求めました．

\displaystyle{ \min _ {w \in \mathbb R ^ d, b \in \mathbb R} \frac 1 2 \| w \| _ 2 ^ 2 \quad \text{subject to} \quad y_i(w \cdot x_i + b) \geq 1, \; \forall i \in \{ 1, \ldots, m \} }

これは d 変数，制約は m 個の最適化問題です． 今回はこの問題の双対問題を考えてみようと思います．

双対形の導出

　まずは，ラグランジュ乗数 \alpha \in \mathbb R ^ m _ + を導入してラグランジュ関数 L( w, b ; \alpha ) を定義します （w，b は主問題の変数， \alpha は双対問題の変数なのでセミコロンで区切りました）．

\displaystyle{ L( w, b; \alpha ) = \frac 1 2 \| w \| _ 2 ^ 2 + \sum_{i = 1} ^ m \left\{ 1 - y_i(w \cdot x_i + b) \right \} }

この関数を主問題の変数 w， b について最小化します．

\displaystyle{ \begin{align} &\min_{w, b} L( w, b; \alpha ) \\ =& \min_{w, b} \frac 1 2 \| w \| _ 2 ^ 2 + \sum_{i = 1} ^ m \alpha _ i \left\{ 1 - y_i(w \cdot x_i + b) \right \} \\ =& \min _ w \frac 1 2 \| w \| _ 2 ^ 2 - w \cdot \left( \sum_{i=1} ^ m y_i \alpha _ i x_i \right) + \min _ b b \sum_{i = 1} ^ m \alpha _ i y_i + \sum _ {i=1} ^ m \alpha _ i \end{align} }

明らかに L は凸関数ですので，最小値が存在します．主問題の変数で偏微分すると

\displaystyle{ \begin{align} \nabla _ w L( w, b; \alpha ) &= w - \sum_{i=1} ^ m \alpha _ i y_i x_i = 0 & & \Leftrightarrow w = \sum_{i=1} ^ m \alpha _ i y_i x_i \\ \nabla _ b L( w, b; \alpha ) &= \sum_{i = 1} ^ m \alpha _ i y_i = 0 & & \Leftrightarrow \sum_{i = 1} ^ m \alpha _ i y_i = 0 \end{align} }

となるので，これらを L に代入すると

\displaystyle{ \begin{align} &\min_{w, b} L( w, b; \alpha ) \\ =& \frac 1 2 \left\| \sum_{i=1} ^ m \alpha _ i y_i x_i \right\| ^ 2 - \sum _ {i=1} ^ m \sum _ {j=1} ^ m \alpha _ i \alpha _ j y _ i y _ j (x _ i \cdot x _ j) - b \sum _{i=1}^m \alpha _ i y _ i + \sum_{i=1} ^ m \alpha _ i \\ =& \sum_{i=1} ^ m \alpha _ i - \frac 1 2 \left\| \sum_{i=1} ^ m \alpha _ i y_i x_i \right\| ^ 2 \end{align} }

となり，双対形の目的関数が得られます．

　以上より，SVM の双対問題は

\displaystyle{ \begin{align} \max _ {\alpha} \sum_{i=1} ^ m \alpha _ i & - \frac 1 2 \left\| \sum_{i=1} ^ m \alpha _ i y_i x_i \right\| ^ 2 \\ \text{subject to} & \sum _ {i=1} ^ m \alpha _ i y _ i = 0 \\ & \alpha _ i \geq 0, \quad \forall i \in \{ 1, \ldots, m \} \end{align} }

となります．双対問題は m 変数，制約は 1 個です．

　ここで，

\displaystyle{ Q := \sum _ {i=1} ^ m (y _ i x _ i) (y _ i x _ i) ^ \top }

とすれば Q はグラム行列と呼ばれる半正定値行列ですので， 目的関数

\displaystyle{ \sum _ {i=1} ^ m \alpha _ i - \frac 1 2 \alpha ^ \top Q \alpha }

は上に凸な二次関数（Quadratic function）であることがわかりやすくなります．

主問題と双対問題の関係

　また，KKT条件から主問題の最適解 w ^ \ast と双対問題の最適解 \alpha ^ \ast に対して

\displaystyle{ w ^ * = \sum _ {i=1} ^ m \alpha ^ * _ i y _ i x _ i }

が成り立つので，双対問題の最適解 \alpha ^ \astから主問題の最適解 w ^ \ast を構築できます． 主問題の最適解 b に関しては，次の考察からわかります．

サポートベクター

　さて，相補正条件から得られる主問題の最適解 w ^ \ast と双対問題の最適解 \alpha ^ * の関係式

\displaystyle{ \forall i \in \{ 1, \ldots, m\}, \quad \alpha ^ * _ i \left( 1 - y _ i ( w ^ * \cdot x _ i + b ) \right) = 0 }

より，各 i \in \{ 1, \ldots, m \} に対して次が成り立ちます．

\displaystyle{ \left( \alpha ^ * _ i = 0 \right) \vee \left( y _ i (w ^ * \cdot x _ i + b ) = 1 \right) }

L を w で偏微分して得られた関係式

\displaystyle{ w ^ * = \sum _ {i=1} ^ m \alpha ^ * _ i y _ i x _ i }

が主問題の最適解 w ^ * と双対問題の最適解 \alpha ^ * について成り立つことを思い出すと， 最適解 w ^ * は \alpha ^ * _ i \neq 0 となるような y _ i x _ i を組み合わせて構成されることがわかります． \alpha ^ * _ i \neq 0 のとき，相補正条件の式から y _ i ( w \cdot x _ i + b ) = 1 が成り立つので，

  • y _ i = + 1 のとき．
    　 w \cdot x _ i + b = 1 となるので，訓練例 x _ i は 超平面の正例側で， 超平面との距離が最小（ = 1）となるような例であることがわかります．
  • y _ i = - 1 のとき．
    　 w \cdot x _ i + b = -1 となるので，訓練例 x _ i は 超平面の負例側で， 超平面との距離が最小（ = 1）となるような例であることがわかります．

　このような， \alpha _ i \neq 0 となる x _ i のことをサポートベクター（Support Vector）と呼びます．

f:id:OCELOT:20200607145153p:plain
サポートベクター
w は一意に定まりますが， w を構成する (x _ i, y _ i) の組み合わせは必ずしも一意には定まりませんので注意が必要です．

　また，各サポートベクター x _ i に関しては，相補性条件より w \cdot x _ i + b = 1 が成り立つので

\displaystyle{ \begin{align} b &= 1 - w \cdot x _ i \\ &= 1 - \left( \sum _ {j=1} ^ m \alpha _ j y _ j x _ j \right) \cdot x _ i \end{align} }

得られます．従って最適な \alpha ^ \ast が求まれば，最適な w ^ \ast が求まり， それから b も双対問題の最適解を使って構築できることがわかります．

　以上より，主問題の代わりに双対問題を解けば良いこともわかります．

おわりに

　さて，これまでの式変形でハードマージンSVM で扱う最適化問題と，その双対問題を求めました． しかし，一般にはデータは超平面でラベルが+1のデータと-1のデータを分離できません（言い換えると，線形分離可能でないということです）． そういう場合には，これまで展開してきた話の仮定が崩れることになりますので，定式化をやり直す必要があります． こうして新たに定式化し直されたSVMを ソフトマージンSVM と呼びます．

　次の記事では，ソフトマージンSVMについて話をし， 余力があればハードマージンSVM，ソフトマージンSVMの汎化誤差の保証について話をしたいと思います．

多項式カーネル

機械学習 統計的学習理論

証明を考えながら一気書きしたので文章が拙いのは見逃してください（そうでなくとも拙いですが）．

多項式カーネル

　正の実数 c > 0 に対して， d \in \mathbb N 次の多項式カーネル K : \mathbb R ^ N \times \mathbb R ^ N \to \mathbb R は 次式で定義されます．

\displaystyle{ \forall \boldsymbol x, \boldsymbol x' \in \mathbb R ^ N, \quad K(\boldsymbol x, \boldsymbol x') = (\boldsymbol x \cdot \boldsymbol x' + c)^d }

　多項式カーネルは \mathbb R ^ N から \mathbb R ^ H へと写していると考えられるそうです． ただし，ここで H は

\displaystyle{ H = \begin{pmatrix} N+d \\ d \end{pmatrix} }

のことです．

　本記事ではこの証明，つまり

\displaystyle{ K(\boldsymbol x, \boldsymbol x') = \phi (\boldsymbol x) \cdot \phi (\boldsymbol x') }

を満たす写像 \phi : \mathbb R ^ N \to \mathbb R ^ H が存在することを示します．

証明

　まず， z = \boldsymbol x \cdot \boldsymbol x' とおくと，二項定理より

\displaystyle{ K(\boldsymbol x, \boldsymbol x') = \sum _ {s = 0} ^ d \begin{pmatrix} d \\ s \end{pmatrix} z ^ s c ^ {d - s} }

と展開できます．

　さて，ベクトル \boldsymbol x, \boldsymbol x ' \in \mathbb R ^ N の各成分を

\displaystyle{ \boldsymbol x = \begin{pmatrix} x _ 1 & x _ 2 & \cdots & x _ N \end{pmatrix} ^ \top, \quad \boldsymbol x' = \begin{pmatrix} x' _ 1 & x' _ 2 & \cdots & x' _ N \end{pmatrix} ^ \top }

と書くことにします． こうすると， z ^ s は次のように展開できます．

\displaystyle{ \begin{align} z ^ s &= (\boldsymbol x \cdot \boldsymbol x') ^ s \\ &= ( x _ 1 x' _ 1 + x _ 2 x' _ 2 + \cdots + x _ N x' _ N) ^ s \end{align} }

ここで，多項定理の公式

\displaystyle{ ( z _ 1 + \cdots + z _ N) ^ d = \sum _ { r _ 1 , \ldots, r _ N : r _ 1 + r _ 2 + \cdots + r _ N = d } \begin{pmatrix} d \\ r _1 , \ldots , r _ N \end{pmatrix} z _ 1 ^ {r_1} z _ 2 ^ {r _ 2} \cdots z _ N ^ {r _ N} }

を使うと，

\displaystyle{ \begin{align} z ^ s &= ( x _ 1 x' _ 1 + x _ 2 x' _ 2 + \cdots + x _ N x' _ N + c) ^ s \\ &= \sum _ {\boldsymbol r : r _ 1 + r _ 2 + \cdots + r _ N + r _ N = s } \begin{pmatrix} s \\ \boldsymbol r \end{pmatrix} (x _ 1 x' _ 1) ^ {r_1} (x _ 2 x' _ 2) ^ {r _ 2} \cdots (x _ N x' _ N) ^ {r _ N} \end{align} }

と書き直すことができます． ただし，表記を簡単にするために

\displaystyle{ \begin{align} \boldsymbol r &= \begin{pmatrix} r _ 1 & \ldots & r _ {N+1} \end{pmatrix}, \\ \begin{pmatrix} s \\ \boldsymbol r \end{pmatrix} &= \frac { s! } { r _ 1 ! \cdots r _ N ! } \end{align} }

としました． ある s に対して， \boldsymbol r を \sum _ {i=1} ^ N r _ i = s となるようにひとつ決めると， 和の中身はの積の部分（二項係数を除いた部分）は，

\displaystyle{ \begin{align} &(x _ 1 x' _ 1) ^ {r_1} (x _ 2 x' _ 2) ^ {r _ 2} \cdots (x _ N x' _ N) ^ {r _ N} \\ =& \left( x ^ {r _ 1} _ 1 \cdots x ^ {r _ N} _ N \right) \left( x' ^ {r _ 1} _ 1 \cdots x' ^ {r _ N} _ N \right) &=: \phi _ { \boldsymbol r } (\boldsymbol x) \phi _ { \boldsymbol r } (\boldsymbol x') \end{align} }

と， \boldsymbol x に関する項と \boldsymbol x' に関する項の積の形に書き直せます． ただし，

\displaystyle{ \begin{align} \phi _ { \boldsymbol r } (\boldsymbol x) &= \left( x ^ {r _ 1} _ 1 \cdots x ^ {r _ N} _ N \right) \in \mathbb R, \\ \phi _ { \boldsymbol r } (\boldsymbol x') &= \left( x' ^ {r _ 1} _ 1 \cdots x' ^ {r _ N} _ N \right) \in \mathbb R \end{align} }

と定義しました．このように書くことで， \phi _ {\boldsymbol r} (\boldsymbol x) \phi _ {\boldsymbol r} (\boldsymbol x') は 内積 \phi (\boldsymbol x) \cdot \phi (\boldsymbol x') の第 \boldsymbol r 成分と考えることができます． z ^ s は \phi _ {\boldsymbol r} (\boldsymbol x) \phi _ {\boldsymbol r} (\boldsymbol x') を \sum _ {i=1} ^ N r _ i = s を満たすすべての \boldsymbol r について足し合わせているので

\displaystyle{ \begin{align} z ^ s &= \sum _ {\boldsymbol r : r _ 1 + r _ 2 + \cdots + r _ N + r _ N = s } \begin{pmatrix} s \\ \boldsymbol r \end{pmatrix} (x _ 1 x' _ 1) ^ {r_1} (x _ 2 x' _ 2) ^ {r _ 2} \cdots (x _ N x' _ N) ^ {r _ N} \\ &= \phi _ { \boldsymbol r _ 1 } (\boldsymbol x) \phi _ { \boldsymbol r _ 1 } (\boldsymbol x') + \phi _ { \boldsymbol r _ 2 } (\boldsymbol x) \phi _ { \boldsymbol r _ 2 } (\boldsymbol x') + \cdots \\ &= \begin{pmatrix} \phi _ { \boldsymbol r _ 1 } (\boldsymbol x) \\ \phi _ { \boldsymbol r _ 2 } (\boldsymbol x) \\ \vdots \end{pmatrix} \cdot \begin{pmatrix} \phi _ { \boldsymbol r _ 1 } (\boldsymbol x') \\ \phi _ { \boldsymbol r _ 2 } (\boldsymbol x') \\ \vdots \end{pmatrix} &=: \phi _ s (\boldsymbol x) \cdot \phi _ s (\boldsymbol x') \end{align} }

と書くことができます．ただし， \sum _ {i=1} ^ N r _ i = s を満たす \boldsymbol r をそれぞれ \boldsymbol r _ 1, \boldsymbol r _ 2, \ldots のように書きました．

以上の議論から，各 s について z ^ s はベクトルの内積の形で書くことができるということがわかりました． 本記事の目的は K (\boldsymbol x, \boldsymbol x') が \mathbb R ^ H 上で内積を取った値を返す関数であることを示すことでしたので， これからすべきことは

  1. 各 s について \phi _ s (\boldsymbol x) が何次元ベクトルなのかを求める．
    1. で求めた次元数を s=0 から s=d まで足し合わせる．

の2つです．

1. 各 s について \phi _ s (\boldsymbol x) が何次元ベクトルなのかを求める．

　この問題は，今回の場合は次の問題と等価です．

\displaystyle{ (z _ 1 + z _ 2 + \cdots + z _ N) ^ s }

を展開したとき，項数はいくつか．

　この問題は，高校数学で習った組み合わせの問題ですね．要は， N 種類のものから重複を許して s 個選ぶ問題 です．従って，簡単な計算から各 s における (z _ 1 + z _ 2 + \cdots + z _ N) ^ s の項数は

\displaystyle{ \begin{pmatrix} N + s - 1 \\ s \end{pmatrix} = \frac {(N+s-1)!} {s ! (N-1)!} }

となることがわかります．

2. 1. で求めた次元数を s=0 から s=d まで足し合わせる．

　次の量を求めたいです．

\displaystyle{ \sum _ {s=0} ^ d \begin{pmatrix} N + s - 1 \\ s \end{pmatrix} }

次の補題から直ちに求まります．

補題

N \in \mathbb N とします．このとき，

\displaystyle{ \forall d \in \mathbb N, \quad \sum _ {s=0} ^ d \begin{pmatrix} N + s - 1 \\ s \end{pmatrix} = \begin{pmatrix} N + d \\ d \end{pmatrix} }

補題の証明

数学的帰納法で示します．

  • d = 1 のとき．
\displaystyle{ \begin{align} \sum _ {s=0} ^ 1 \begin{pmatrix} N \\ s \end{pmatrix} &= \begin{pmatrix} N \\ 0 \end{pmatrix} + \begin{pmatrix} N \\ 1 \end{pmatrix} \\ &= 1 + N \\ \begin{pmatrix} N + 1 \\ 1 \end{pmatrix} &= N+1 \end{align} }

よって， d=1 のときは成り立ちます．

  • d \geq 1 のときに成り立つと仮定します．
    このとき， d+1 のときにも成り立つことを示します．
\displaystyle{ \begin{align} \sum _ {s=0} ^ {d+1} \begin{pmatrix} N+s-1 \\ s \end{pmatrix} &= \sum _ {s=0} ^ {d} \begin{pmatrix} N+s-1 \\ s \end{pmatrix} + \begin{pmatrix} N+d \\ d+1 \end{pmatrix} \\ &= \begin{pmatrix} N+d \\ d \end{pmatrix} + \begin{pmatrix} N+d \\ d+1 \end{pmatrix} \\ &= \begin{pmatrix} N+d+1 \\ d+1 \end{pmatrix} \end{align} }

したがって， d+1 のときも成り立ちます．

以上より，任意の d \in \mathbb N に対して

\displaystyle{ \forall d \in \mathbb N, \quad \sum _ {s=0} ^ d \begin{pmatrix} N + s - 1 \\ s \end{pmatrix} = \begin{pmatrix} N + d \\ d \end{pmatrix} }

が成り立つことが示せました．

　上記の補題を使うことで，

\displaystyle{ \sum _ {s=0} ^ d \begin{pmatrix} N + s - 1 \\ s \end{pmatrix} = \begin{pmatrix} N + d \\ d \end{pmatrix} }

が成り立つことが直ちに言えるので， 多項式カーネルは \mathbb R ^ N から \mathbb R ^ H に写した後に内積を取ったものと考えられることが示せました．

余談

これは Foundation of Machine Learning の第 6 章の演習問題の一つ（しかもその半分）でした． 証明が間違っていないといいな，と願ってます．

SVM（Support Vector Machine，サポートベクターマシーン）その１

機械学習 最適化 SVM

はじめに

　本記事は，Mohriさんの教科書を参考にしています． 非常に面白い教科書ですのでぜひ読んでみてください．

Foundations of Machine Learning (Adaptive Computation and Machine Learning series)

Foundations of Machine Learning (Adaptive Computation and Machine Learning series)

　本記事では，機械学習に入門した人が必ずと言っていいほど聞いたことがある SVM（Support Vector Machine）の問題設定，定式化について解説をしていきます．

　次の記事では，サポートベクターマシーンのサポートベクター（Support Vector）とは何かという話や， SVM で得られた分類器はどれぐらい誤差が抑えられるかという保証の話， そして実装（Python か C++ か Haskell を候補として考えています）などをしてみようと考えています．

　また，いつになるかはわかりませんがハードマージン SVM だけでなく，ソフトマージン SVM についての記事も書きたいと考えています．

注意点

　この記事では，ベクトルを太字で書いておりません．文脈から，これはベクトル，これはスカラーと判断してください． 一応この記事では w， x _ 1, \ldots, x _ m をベクトル， \alpha， d， i， m， b， y _ 1, \ldots, y _ m をスカラーとして扱っています．

問題設定

　入力として m 個の訓練例 \left\{ (x_i, y_i) \right\}_{i=1}^m \subseteq \mathbb{R}^d \times \{ -1, +1 \} が与えられます （各訓練例 (x_i, y_i) は d 次元ベクトルとラベルの組）．

　ただし，訓練例の各 x_i はどのように取ってきても良いというわけではなく， 何らかの分布（どのような分布かはわからないですが）に独立に従って得られるものとします．

　機械学習では訓練例から学習した規則で未知のデータがやってきたときになるべく高い精度で予測をしたい，つまり汎化誤差（後述）を小さくしたい という目標があります． 「SVMでは汎化誤差はある値以下になる」という主張をするためにこの仮定は必須なのです．

　例えば，各 x_i が身長（ d=1）の場合を考えます． このとき，無作為に n=100 人のとってくるのが自然です（そうでなければ，偏ったデータになってしまい予測も悪くなってしまうからです）． 無作為に抽出した身長のデータは何らかの分布に従いますので，先ほどの未知の分布に従うという仮定はそれほど強い仮定ではないと思います （おそらく，身長のデータは正規分布に従います）．

　次の図は，ある分布に従って取ってきた訓練例の図です．

f:id:OCELOT:20200318221403p:plain
訓練例

　このとき，入力として与えられた訓練例をうまく分類するような超平面を求めたい，というのが直感的なSVMの直感的な理解です． ここで訓練例をうまく分類するというのは「超平面の片側には +1 のラベルがついた訓練例が，もう一方には -1 のラベルがついた訓練例が集まっている」 という状態を指しています．もちろん，必ずしも綺麗に（完全に）分類できるというわけではありません． しかし，今回は訓練例集合をうまく分類する超平面 h(x) = w \cdot x + b が存在すると仮定します （関数は f(x) と書くのが一般的ですが，統計的学習理論の分野ではラベルや値を予測する関数を仮説（hypothesis）と呼ぶので， その頭文字をとって h(x) と書いていると思われます）． この仮定は非常に強いと思われますが，後に「訓練例をうまく分類する超平面が存在しない」場合を考えますので安心してください．

　また，超平面が存在するといっても一意に定まることはなく多くの場合は無数に存在します． 次の図は訓練例をうまく分類する超平面をいくつか引いてみたものです． ２次元なので直線といったほうが正しいでしょうか．

f:id:OCELOT:20200318222209p:plain
①，②，③はそれぞれデータを分類する超平面（直線）

　この図では，①，②，③のいずれの超平面もうまくデータを分離しています． それでは，分類できればどの超平面でも良いのでしょうか．たまたま入力点が分類しやすかっただけではないのでしょうか． 機械学習では，データが従う分布と分類器から定まる「汎化誤差」と呼ばれる量を最小化することを目標としますので， 汎化誤差が大きくならないという保証ができるように超平面を引くのが良さそうです．

汎化誤差

　それでは，先ほどから何度か出ている「汎化誤差」とは一体なんでしょうか．定義は，次のようになります．

　各データ x は未知の分布 D に従うと仮定します． このとき，関数 h : \mathbb R ^ d \to \{ -1, +1 \} の汎化誤差 R(h) を次のように定義します．

\displaystyle{ R(h) = \mathbb E _ {x \sim D} \left[ \mathbb I _ {h(x) \neq c(x)} \right] }

ただし， c(x) はデータ x のラベル， \mathbb I _ {\omega} は \omega が真なら 1，偽なら 0 を返す関数（指示関数と呼ばれる）です．

　汎化誤差は，「ある分布に従って取ってきたデータを予測しようと思ったとき，平均してどれくらい間違えるか」という量です． 未知のデータが与えられたとき，そのデータが「予測器を学習するときに使った訓練例」と同じ分布に従っているならば， 高い確率で予測が成功する，すなわち「平均して間違える量」が小さいことが望ましいです．その「平均して間違える量」を表すものが 汎化誤差のことです．

　さて，ここで「汎化誤差を小さくしたいならば，汎化誤差を最小にするように学習をすれば良いのでは？」という疑問が浮かぶわけですが， これは一般にとても難しいことなのです．なぜなら，データが従う分布 D は未知である上に，仮に分布を知っていたとしても データは一般に無数に存在しており，汎化誤差はその全てのデータ上で期待値を取るので， 計算が非常に困難だからです．

　このような問題もあり，統計的学習理論では「汎化誤差の上界を求める」といったアプローチをとる場合が多く見受けられます （Rademacher Complexity，Growth function，VC次元など非常に面白い概念が出てきます）．

　それでは，どのような場合に汎化誤差が大きくならないのでしょうか． SVMの場合，マージン，すなわち最も超平面と近いデータの距離を最大にする超平面が良いとされています． 上の図では，②の超平面がそれに相当します（概念図ですので少しずれているとは思いますが）．

（ハード）マージン

　超平面 h(x) = w \cdot x + b とデータ x との距離を \rho_h (x) と書くことにします． 一般の d 次元空間における点と直線の距離の公式は高校生の時に習った 2 次元空間のものを拡張したもので，次のようにかけます．

\displaystyle{ \rho_h (x) = \frac{|w \cdot x + b|}{\| w \|_2} }

　超平面との距離が最小となるデータの距離を最小（ハード）マージンと呼びます． 式で書くと，

\displaystyle{ \min_{i \in \{ 1, \ldots, m \}} \frac{|w \cdot x_i + b|}{\| w \|_2} = \min_{i \in \{ 1, \ldots, m \}} \rho_h (x_i) }

となります．

　下図はある超平面（直線）を弾いた時の，最小（ハード）マージンを表しています．

f:id:OCELOT:20200318222726p:plain
最小（ハード）マージン

ハードマージンSVM（hard margin SVM）

　訓練例をうまく分類する超平面が存在するという仮定のもとでのSVMをハードマージンSVM（hard margin SVM）と呼びます． 汎化誤差が大きくならないという保証をするためにマージンを最大化するとのことだったので， ハードマージン最大化SVMは次のような最適化問題で定式化されます．

\displaystyle{ \max _ {w \in \mathbb R ^ d, b \in \mathbb R} \min_{i \in \{ 1, \ldots, m \}} \rho_h (x_i) = \max _ {w \in \mathbb R ^ d, b \in \mathbb R} \min_{i \in \{ 1, \ldots, m \}} \frac{|w \cdot x_i + b|}{\| w \|_2} }

　ただ，今回は訓練例をうまく分類できる場合（ハードマージン SVM）を考えていますので， ラベル y_i と予測 w \cdot x_i + b の符号が一致します． ですので，次のように書き直すことができます．

\displaystyle{ \max _ {w \in \mathbb R ^ d, b \in \mathbb R} \min_{i \in \{ 1, \ldots, m \}} \frac{y_i(w \cdot x_i + b)}{\| w \|_2} }

　ただ，このままでは最適な (w, b) が一意に定まりません． なぜなら， (w ^ *, b ^ *) が最適解のとき，それを \alpha > 0 倍した (\alpha w ^ *, \alpha b ^ *) も最適解になってしまうからです （分子と分母で \alpha が打ち消し合うので，最適値が一緒になってしまうんですね）．

　この問題を避けるために， \min _ {i \in \{1, \ldots, m \} } y_i(w \cdot x_i + b) = 1 と制約を加えてしまいます． そうすると，先ほどの最適化問題の分子の部分はこの制約より 1 になるので，次のような最適化問題が得られます．

\displaystyle{ \max _ {w \in \mathbb R ^ d, b \in \mathbb R} \frac{1}{\| w \|_2} \quad \text{subject to} \quad \min _ {i \in \{1, \ldots, m \} } y_i(w \cdot x_i + b) = 1 }

　この制約は y_i(w \cdot x_i + b) が最も小さくなる i に対して成り立つようにしてくださいと言っています．

　最も小さくなる i に対して y_i(w \cdot x_i + b) = 1 が成り立つということは，全ての i に対して y_i(w \cdot x_i + b) \geq 1 が成り立つということです．従って，次のように書き直せます．

\displaystyle{ \max _ {w \in \mathbb R ^ d, b \in \mathbb R} \frac{1}{\| w \|_2} \quad \text{subject to} \quad y_i(w \cdot x_i + b) \geq 1, \; \forall i \in \{ 1, \ldots, m \} }

　目的関数は w のノルムの逆数になっているので，これを最小化問題に書き直してしまいます．

\displaystyle{ \min _ {w \in \mathbb R ^ d, b \in \mathbb R} \frac 1 2 \| w \|_2 \quad \text{subject to} \quad y_i(w \cdot x_i + b) \geq 1, \; \forall i \in \{ 1, \ldots, m \} }

　ここで，目的関数が 1/2 倍されていますが，今求めたいのは最適値ではなく最適解 (w, b) ですので， 目的関数を定数倍したところで最適解は変わらないので問題ありません（最適値が欲しい場合は， 2 倍すれば良いです）．

　さらに，目的関数が \| w \|_2 = \sqrt { \sum _ {i=1} ^ d w _ i ^ 2 } のままでは解析がし辛いので，2乗してしまいます．

\displaystyle{ \min _ {w \in \mathbb R ^ d, b \in \mathbb R} \frac 1 2 \| w \| _ 2 ^ 2 \quad \text{subject to} \quad y_i(w \cdot x_i + b) \geq 1, \; \forall i \in \{ 1, \ldots, m \} }

　こうすると，目的関数が凸関数となって（これは次の記事で詳しく見ていきます）解析がしやすくなります． そして，得られた最適化問題がハードマージン SVM で解く最適化問題の式です．

目的関数を少しいじった理由は，今後の解析を綺麗にするためです．

ここまでのまとめ

　この記事では，SVMの問題設定と定式化について説明をしました．

f:id:OCELOT:20200603003214p:plain
SVM の問題設定

　定式化だけでも十分面白いですが，今回の記事では最も大事な解析が全くできていません． その上，サポートベクターマシンのサポートベクター（Support Vector）とは何かということもわからないままです．

次の記事でそのあたりをしっかり書こうと考えています（やる気が出ればの話ですが）．

ubuntu 20.04 にihaskell を導入したけど動かない．

Haskell IHaskell

基本的に公式に従って導入したんですけど，kernelが死んだまま動きませんでした． 対処法を忘れないようにここに書いておきます．

前提として，Haskellはstackを使って導入しているものとします． 導入していなくとも次のコマンドを打つだけで導入することができるので大丈夫です．

$ curl -sSL https://get.haskellstack.org/ | sh
$ stack setup
$ stack upgrade

また，エイリアスをいくつか作っておくと便利かと思います．

alias ghc="stack ghc"
alias ghci="stack ghci"
alias runghc="stack runghc"

さて，本題のIHaskellのkernelが死んだままになる解決法に入ります． まず，ダウンロードした（clone した）IHaskell のディレクトリにいって，stack.yamlというファイルを覗いてみます．

$ cd ~/Downloads/IHaskell
$ head stack.yaml -n 1

すると，

resolver: lts-14.27

のように，なにかよくわからない数字が出てきます（たぶんhaskellのバージョン？）．

これをメモしておきます．
次は，以下のコマンドを打ちます．

$ cd ~/.stack/global-project/

ここでlsコマンドを打つと，stack.yamlというファイルがあると思います． このファイルを覗いてみます．

$ cat stack.yaml

すると，前と同じように，

resolver: lts-15.10

というものが書いてある行があります．ここの数字が違うのがkernel が死んでる原因っぽいです．コメントアウトして数字を合わせます．

# resolver: lts-15.10
resolver: lts-14.27

これで解決しました．

Gurobiの使い方（python3）

最適化ソルバの一つである Gurobi の使い方について．

はじめに

これは私が頻繁に最適化ソルバを使うので，方法を忘れないための記事です． 多少わかりにくいところ，もしくは使い方を間違っているところがあればぜひ教えてください．

注意書き

本記事を書いた時点で，私のダウンロードしている Gurobi のバージョンは 9.0.1. なので， この記事を参考にしてプログラムを書こうという方は適宜自分のバージョンに置き換えて読んでください． また，jupyter notebookで実行しようとしてmodule import errorが出るときは，次のコマンドを打てば解決すると思います．

$ conda config --add channels http://conda.anaconda.org/gurobi
$ conda install gurobi

解きたい問題

前に書いたGurobiの使い方（C++） で解いた問題と同じ問題を解いてみようと思います． ocelot.hatenadiary.com 次式で定義される行列 A \in \mathbb{R}^{2 \times 2}，ベクトル b \in \mathbb{R}^{2}

A = \begin{pmatrix} -1 & 2 \\ 0 & 1 \\ \end{pmatrix}, \quad b = \begin{pmatrix} 0 \\ 6 \end{pmatrix}

を用いて，次のような最適化問題を考えます．

\min \left\{ (x _ 1- 3)^2 + (x _ 2 - 4)^2 \mid A x \leq b, x _ 1 \geq 0, x _ 2 \geq 0 \right\}

この問題の最適値は 5で， 最適解は

x = \begin{pmatrix} x _ 1 \\ x _ 2 \end{pmatrix} = \begin{pmatrix} 4 \\ 2 \end{pmatrix}

です． これらを求めるプログラムを書いてみようと思います．

プログラム

例えば，次のように書けます．

# -*- coding: utf-8 -*-
import gurobipy as gp
from gurobipy import GRB

# モデルの宣言
model = gp.Model(name="Test")

# 変数の宣言，初期化，モデルに追加．
x1 = model.addVar(lb=0, ub=GRB.INFINITY, vtype=GRB.CONTINUOUS, name='x')
x2 = model.addVar(lb=0, ub=GRB.INFINITY, vtype=GRB.CONTINUOUS, name='y')

# 制約をモデルに追加
constraint_1 = model.addConstr(-x1 + 2*x2 <= 0, name="constraint_1")
constraint_2 = model.addConstr(x1 <= 6, name="constraint_2")

# 目的関数の設定
objective = (x1 - 3)*(x1 - 3) + (x2 - 4)*(x2 - 4)
model.setObjective(objective, GRB.MINIMIZE)

# コンソールへの出力をなくす．
model.params.LogToConsole = False

# ソルバに解いてもらう．
model.optimize()

# 最適値の出力
print("Optimal Value: ".format(objective.getValue()))

# 最適解の出力
print("Optimal Solutions")
print("\t{} = {}".format(x1.varName, x1.x))
print("\t{} = {}".format(x2.varName, x2.x))

解きたい問題が最大化問題である場合，model.setObjective( objective, GRB.MAXIMIZE ) と書きます．

実行

普通のpythonのプログラムと同様に実行できます．

$ python main.py
Academic license - for non-commercial use only
Optimal Value: 
Optimal Solutions
    x = 4.000000000023386
    y = 1.9999999999694231

双対変数について

解いた問題の双対問題の解が欲しい場合，つぎのように書くと得られます．

for constr in model.getConstrs():
    print("The dual value of {} is {}.".format(constr.constrName, constr.pi))

終わりに

なんでC++で解いた時の出力とpython3で解いた時の出力に違いがあるのかな，出力の形式の違いなのかな，というのが地味に気になっています．

汎化誤差とか経験誤差とか

機械学習 統計的学習理論

はじめに

機械学習ではよく経験誤差を小さくするような関数(パラメータ)を学習することを目標にしますが， 実際のところなぜ経験誤差を小さくしたいのかわかっていなかったり， そもそも経験誤差の定義を知らない人も多いかと思われます． 実際，僕もその一人でした．

本記事はそんな僕が経験誤差や汎化誤差について理解するためのもので， 経験誤差を小さくする気持ちについて書いています． 誤り等ありましたら早急に連絡をよろしくお願いいたします．

注意

この記事は，Foundations of Machine Learning（聖書）を 参考に書いています（ほとんど中身は同じです）． pdf版が無料で公開されているのでぜひそちらを参照してください．

Foundations of Machine Learning, second edition (Adaptive Computation and Machine Learning series)

Foundations of Machine Learning, second edition (Adaptive Computation and Machine Learning series)

記号の定義

本題に入る前に，本記事で扱う記法をここで導入しておきます．

  • \mathcal{X} ... データの空間．
    \mathcal{X} はユークリッド空間の部分集合である必要はありません．例えば画像データの場合は \mathcal{X} が \mathbb{R}^2 や \{0, 1, \ldots, 255\} であったり，テキストデータの場合は文字列全体の集合だったりします．

  • \mathcal{Y} ... ラベルの空間．
    例えば，本記事で挙げる分類問題においては， \mathcal{Y} = \{0, 1, 2\} だったり， \mathcal{Y} = \{\text{犬}, \text{猫}\} だったりと カテゴリを表すものだったりします．

  • \mathcal{D} ... データとラベルの組の背後にある分布（ \mathcal{X} \times \mathcal{Y} 上の分布）．
    訓練データ，テストデータは独立に分布 \mathcal{D} に従って得られると仮定します．

  • \mathcal{H} ... 仮説集合， \mathcal{H} \subseteq \left\{ h : \mathcal{X} \to \mathcal{Y} \right\} ．
    言葉で表すと，データからラベルを予測する関数全体の集合の部分集合，と言えば伝わるでしょうか．

一般には，分布 \mathcal D に従って得られた (\boldsymbol{x}, y) を「データ」や「例」と呼ぶので， 本記事でも特に断りがない限りはそう呼ぶことにします． また，「サンプル」という言葉は分布 \mathcal D に独立に従って得られた訓練例の列を指すことにも注意してください （訓練例の「集合」ではなく訓練例の「列」と表現したのはランダムにとってきた結果同じものが得られた場合，「集合」だと重複を一つと見做すからです）．

機械学習では，「訓練データに対してのみ誤差（訓練誤差）を小さくすること」を目標にするのではなく， 「未知のデータが来た場合にも間違える確率（汎化誤差）を小さくすること」を目標にします．

汎化誤差とは

仮説 h \in \mathcal{H} とデータの背後にある分布 \mathcal{D} が与えられたとき， h の汎化誤差を次式で定義します．

\displaystyle{ R(h) = \Pr\limits_{(\boldsymbol{x}, y) \sim \mathcal{D}} \left[ h(\boldsymbol{x}) \neq y \right] = \mathbb{E}_{(\boldsymbol{x}, y) \sim \mathcal{D}} \left[ 1_{h(\boldsymbol{x}) \neq y } \right] }

ただし，

\displaystyle{ 1_{\omega} = \begin{cases} 1 & \omega \text{ is True} \\ 0 & \omega \text{ is False} \end{cases} }

としました． 汎化誤差を言葉で説明すると， 「分布 \mathcal D に従ってデータを取ってきたときに間違える確率」となります．

機械学習では，多くの場合この汎化誤差を最小にする仮説を求めることを目標にします． しかし，現実にはデータの背後にある分布など得られるはずもありません． そこで代わりに 経験誤差 というものを考えます．

経験誤差とは

仮説 h \in \mathcal{H} と 訓練例の列 S = ( x_1, \ldots, x_m ) \subseteq \mathcal{X} \times \mathcal{Y} が与えられたとき， h の経験誤差を次式で定義します．

\displaystyle{ \hat{R}_{S} (h) = \frac{1}{m} \sum_{i=1}^m 1_{h (\boldsymbol{x} _ i) \neq y_i} }

経験誤差は汎化誤差の不偏推定量

示したいことは，以下の等式です．

\displaystyle{ \mathbb{E}_{S \sim \mathcal{D}^m} \left[ \hat{R}_{S} (h) \right] = R(h) }

期待値の線形性と，各訓練例は独立に分布 \mathcal{D} に従って取ってくるという仮定から，

\displaystyle{ \begin{eqnarray} \mathbb{E}_{S \sim \mathcal{D}^m} \left[ \hat{R}_{S} (h) \right] & = & \frac{1}{m} \sum_{i=1}^m \mathbb{E}_{S \sim \mathcal{D}^{m}} \left[ 1_{h (\boldsymbol{x} _ i) \neq y_i} \right] \\ & = & \frac{1}{m} \sum_{i=1}^m \mathbb{E}_{S \sim \mathcal{D}^{m}} \left[ 1_{h (\boldsymbol{x} _ i) \neq y_i} \right] \\ & = & \mathbb{E}_{S \sim \mathcal{D}^{m}} \left[ 1_{h (\boldsymbol{x}) \neq y} \right] \\ & = & \mathbb{E}_{(\boldsymbol{x}, y) \sim \mathcal{D}} \left[ 1_{h (\boldsymbol{x}) \neq y} \right] \\ & = & R(h) \end{eqnarray} }

となって，求めたい等式が得られました．

おわりに

以上より， 汎化誤差を計算するのは大変だから， 汎化誤差を小さくする代わりに，その不偏推定量である経験誤差を小さくすることで汎化誤差を小さくできないか ということになります． なるほど，妥当な感じがしますね． しかし，経験誤差を最小にする仮説が汎化誤差を最小にするとは限りません． この辺については追って書こうと思います．

次はPAC学習の記事かSVMの汎化誤差の記事を書きたいなと思っています．

Foundations of Machine Learning, second edition (Adaptive Computation and Machine Learning series)

Foundations of Machine Learning, second edition (Adaptive Computation and Machine Learning series)