読者です 読者をやめる 読者になる 読者になる

しまてく

学んだ技術を書きためるブログ

ITエンジニアのための機械学習理論入門 4-1

機械学習 数学

第4章 パーセプトロン : 分類アルゴリズムの基礎

  • 複数の観測値があるときに、$ t=\pm 1 $ に分類するような直線を発見する問題。
  • 最小二乗法に類似の「誤差関数」を使って解く。
  • ただし「紙と鉛筆による計算」では解けない。
  • 数値計算をしてパラメータの修正を繰り返す「確立的勾配降下法」を利用する。

4.1 確率的勾配降下法アルゴリズム

パラメトリックモデルの3つのステップ(再掲)

  1. パラメーターを含むモデル(数式)を設定する
  2. パラメーターを評価する基準を定める
  3. 最良の評価を与えるパラメーターを決定する

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$)というベクトル微分演算記号を覚えた!