ITエンジニアのための機械学習理論入門 4-1
第4章 パーセプトロン : 分類アルゴリズムの基礎
- 複数の観測値があるときに、$ t=\pm 1 $ に分類するような直線を発見する問題。
- 最小二乗法に類似の「誤差関数」を使って解く。
- ただし「紙と鉛筆による計算」では解けない。
- 数値計算をしてパラメータの修正を繰り返す「確立的勾配降下法」を利用する。
4.1 確率的勾配降下法のアルゴリズム
パラメトリックモデルの３つのステップ（再掲）
- パラメーターを含むモデル（数式）を設定する
- パラメーターを評価する基準を定める
- 最良の評価を与えるパラメーターを決定する
4.1.1 平面を分割する直線の方程式
- まずステップ1として「パラメーターを含むモデル」を設定する。
- 今回は($x$, $y$)平面上のデータを分類する直線を求めることが目的。
- 直線の式と言えば $ y = ax + b$ だが、ここでは$x$と$y$を対等に扱うため、以下の関数を設定する。
$$ f(x, y) = \omega_0 + \omega_1x + \omega_2y \tag{4.1} $$
- この時、($x$, $y$)平面を分割する直線は以下の式で表せる。
$$ f(x, y) = 0 \tag{4.2} $$
(4.2)の直線(境界線)から離れれば離れるほど$f$($x$, $y$)の絶対値は大きくなる。
($x$, $y$)平面をこのように分割するのは、$ t=\pm 1 $ の2種類の属性を持つデータを分類すること。
- ここでは次のルールでデータを分類するものとする。
$$ f(x, y) > 0 \Rightarrow t = +1 \tag{4.3} $$
$$ f(x, y) < 0 \Rightarrow t = -1 \tag{4.4} $$
- この時、トレーニングデータとして与えられたデータ $ {( x_n, y_n, t_n )}_{n=1}^N $ について、正しく分類されているかは以下で判定する。
$$ f(x_n, y_n) \times t_n > 0 : 正解 \tag{4.5} $$
$$ f(x_n, y_n) \times t_n \le 0 : 不正解 \tag{4.6} $$
- $ t=\pm 1 $ のどちらの場合においても、同じルールで正誤判定ができるのがポイント。
- すべての $( x_n, y_n, t_n )$ について、(4.5)が成り立つような直線、すなわち(4.1)の係数($\omega_0, \omega_1, \omega_2$)を見つけることがゴール。
- ということで、ステップ2としてパラメーター($\omega_0, \omega_1, \omega_2$)の評価基準を定める。
4.1.2 誤差関数による分類結果の評価
- パラメータの誤差として、正しく分類できない点、すなわち(4.6)が成り立つ点があった場合に、それを誤差として計算する。
- ここで言う誤差は、誤判定に対するペナルティと考えてもいい。
- この誤差が小さいほど正しい分類に近いと言える。
- 具体的な誤差の値としては、「境界線から離れるほど $f(x, y)$ の絶対値が大きくなる」という特徴を利用して次の値を採用する。
$$ ある点の誤差 E_n = \mid f(x_n, y_n) \mid \tag{4.7} $$
- (4.7)は、正しく分類できなかった点についてのみ計算することに注意。
- 誤って分類された点の誤差を合計したものを、分類の誤差 $E$ とする。
$$ E = \sum_{n}{E_n} = \sum_{n} \mid f(x_n, y_n) \mid \tag {4.8} $$
- (4.8)は誤分類された点の誤差の合計を表している。
- このような点は(4.6)を満たすので、次の関係式が成り立つ。
$$ \mid f(x_n, y_n) \mid = - f(x_n, y_n) \times t_n \tag {4.9} $$
- (4.9)および $ f(x, y) $ の定義 (4.1)を用いると、(4.8)は次のように表せる。
$$ E = - \sum_{n}{(\omega_0 + \omega_1x_n + \omega_2y_n ) t_n} \tag {4.10} $$
- あるいは、ベクトルを用いて次のように表すこともできる。
$$ E = - \sum_{n}{t_n w^T \phi_n} \tag {4.11} $$
- ここで、$w$と$\phi_n$は次で定義されるベクトルになる。
$$ w = \left( \begin{array}{r} \omega_0 \\ \omega_1 \\ \omega_2 \end{array} \right) \tag{4.12} \ $$
$$ \phi_n = \left( \begin{array}{r} 1 \ \\ x_n \\ y_n \end{array} \right) \begin{array}{r} \longleftarrow バイアス項 \\ \\ \ \end{array} \tag{4.13} $$
- $w$は求めるべき係数をならべたベクトル。
- $\phi_n$はトレーニングセットに含まれるデータの座標$(x_n, y_n)$を並べたもの。
- ただし、係数$w_0$に対応する成分として、第1成分に定数1を入れてある。
- これはやや技巧的ではあるが、(4.10)をベクトル形式で書き直すために導入した。
- このような形で追加する定数項を「バイアス項」と呼ぶ。
- (4.11)で計算される誤差$E$が小さくなるほど、トレーニングセットは適切に分類されていると言える。
- すべてのデータが完全に正しく分類できれば、$E=0$になる。
- 最後のステップ3は、(4.11)の誤差$E$を最小にするパラメーター$w$を求めること。
- ただこれが難しく、本節のテーマである「確率的勾配降下法」を用いて解く。
4.1.3 勾配ベクトルによるパラメーターの修正
- 最小二乗法ではパラメーターによる偏微分係数が0になるという条件から、二乗誤差$E_D$を最小にする係数$w$を決定することができた。
- これと同様に、(4.10)の誤差$E$の偏微分係数を0と置いてみる。
$$ \dfrac{\partial \ E}{\partial \ \omega_m} = 0 \ \ \ (m = 0, 1, 2) \tag {4.14} $$
- あるいは、ベクトル形式で、勾配ベクトルが0になるとしても同じ。
$$ \nabla E(w) = - \sum_{n}{t_n \phi_n} = 0 \tag {4.15} $$
- 一般に、勾配ベクトルは次式で定義されるベクトルになる。
$$ \nabla E(w) = \left( \begin{array}{r} \dfrac{\partial \ E}{\partial \ \omega_0} \\ \dfrac{\partial \ E}{\partial \ \omega_1} \\ \dfrac{\partial \ E}{\partial \ \omega_2} \end{array} \right) \tag{4.16} $$
- しかし、(4.14)や(4.15)を変形して係数$w$を表す式を得ることは不可能。
- (4.15)を見るとわかるように、この式の中にはそもそも$w$が含まれていない。
- そこで、純粋な式変形で$w$を求めることはやめ、数値計算を用いて$w$の値を修正しながら、誤差$E$がなるべく小さくなるものを求めることにする。
- ここでヒントになるのが、勾配ベクトルの幾何学的な性質になる。
- 例えば、$(x, y)$平面上に、原点(0, 0)を谷底とするようなすり鉢状の形状をした2変数関数$h(x, y)$があったとする。
$$ 例: h(x, y) = \dfrac{3}{4}(x^2 + y^2) \tag{4.17} $$
- この場合、勾配ベクトルは次のように計算される。
$$ \nabla h = \left( \begin{array}{r} \dfrac{\partial \ h}{\partial \ x} \\ \dfrac{\partial \ h}{\partial \ y} \end{array} \right) = \left( \begin{array}{r} \dfrac{3}{2}x \\ \dfrac{3}{2}y \end{array} \right) \tag{4.18} $$
- この時、任意の点$(x, y)$において、どちらかの方向に少し移動すると、hの値が増減するが、勾配ベクトル$\nabla h$は、$h$の値が最も増加する方向、すなわち「斜面をまっすぐに這い上がる方向」を表す。
- また、勾配ベクトルの大きさは、その点における斜面(接平面)の傾きを表す。
- つまり、各点における勾配ベクトルの方向に移動していけば$h(x, y)$の値はどんどん大きくなる。
- 逆に、勾配ベクトルの反対方向に進めば、$h(x, y)$の値は小さくなる。
- 現在点を$x{old}$とし、次の点$x{new}$を次の式で決定するアルゴリズムとして表現できる。
$$ x_{new} = x_{old} - \nabla h \tag{4.19} $$
- 座標$x$を(4.19)に従って何度も更新していくと、次第に原点に近づき、原点にたどり着いた(勾配ベクトルが0になった)時に停止する。
- 途中で$\nabla h$が大きすぎて原点を超えることがあるが、何度も行ったり来たりしながら次第に収束する。
$$ - \nabla E(w) = \sum_{n}{t_n \phi_n} \tag{4.20} $$
- 「確率的勾配降下法」という名前の「勾配降下」というのは、勾配ベクトルの反対方向にパラメーターを修正して、「誤差の谷」を降りていく、という考えから。
- では「確率的」というのはなにか？
- (4.20)を見ると、右辺は「正しく分類されなかった点」についての和になる。
- 点が100個ある場合は100個分の ${t_n \phi_n}$ を合計して、その値を$w$に加えるという計算が必要。
- しかしデータ数が膨大になると、事前に${t_n \phi_n}$を計算するのは難しいので、サンプリングを行う。
- サンプリングは、正しく分類されていない点をどれか一つ選んで、とりあえずその分だけのパラメーターを修正する。
$$ w_{new} = w_{old} + t_n\phi_n \tag{4.21} $$
- さらに、修正された新しい$w$の下で、正しく分類されていない点を一つ選び、繰り返し(4.21)の修正を行う。
- このように「正しく分類されていない点」をランダムに選びながら、パラメーターを修正していくことこそが「確率的勾配降下法」となる。
- ただし、今回の例では「ランダムに選ぶ」のも面倒なので、かたっぱしから計算していく。
- n = 1～Nについて、処理が終わったらさらにもう一度n=1～Nについて同じ処理を行う。
- これを何度も繰り返し、すべての点を正しく分類する直線にたどり着くと、「$(x_n, y_n)$が正しく分類されていない」という条件を満たさなくなるので、これ以上パラメーター$w$は変化しなくなるためアルゴリズムは終了。
- すべての点を正しく分類できるかはトレーニングセット次第。
- 仮にすべての点を正しく分類できる直線が存在する場合は、この処理でいつかその直線にたどり着くことができる。(Novikovの定理として数学的に証明されている)
- しかしそのような直線が存在しない場合は、いつまでも$w$の値は変化し続ける。
- 従って一定回数で打ち切るように処理をする必要がある。
おしまい
今回は計算式すくなめ。 ナブラ($\nabla$)というベクトル微分演算記号を覚えた！
