2014年11月24日月曜日

1次元ロジスティック回帰と確率的勾配降下法


はじめに


 ここでは、1次元ロジスティック回帰と、これを解く際に用いられる確率的勾配降下法についてまとめる。

1次元ロジスティック回帰


 2分類問題を考える。$N$ 個の観測値 $\vec{x}^{\;i},i=1,\cdots,N$ が与えられ、それぞれ0か1のラベルを持つとする。このとき、観測値が従う確率分布モデル $p(c=0,1\;|\;\vec{x}\;;\;\vec{\omega},b)$ を求めたい。ここで、$\vec{\omega},b$ はモデルを調節するパラメータである。各観測値が他の観測値の影響を受けないと仮定すれば、全ての観測値の確率は 次式で与えられる。 \begin{equation} L(\vec{\omega},b)=\prod_{i=1}^{N}\;p(c^{i}\;|\;\vec{x}^{\;i}\;;\;\vec{\omega},b) \label{likelihood} \end{equation} これが最大となるように $(\vec{\omega},b)$ を調節すればよい。計算を容易にするため次式の最小化を考える。 \begin{equation} L(\vec{\omega},b)=-\sum_{i=1}^{N}\;\ln{p(c^{i}\;|\;\vec{x}^{\;i}\;;\;\vec{\omega},b)} \label{nll} \end{equation} 上式を負の対数尤度(Negative Log Likelihood:NLL)関数と呼ぶ。ところで、観測値のラベル $c$ を0か1に制限したので、確率 $p$ は以下のように書くことができる。 \begin{equation} p(c\;|\;\vec{x}\;;\;\vec{\omega},b)=s(1\;|\;\vec{x}\;;\;\vec{\omega},b)^c\;\left\{1-s(1\;|\;\vec{x}\;;\;\vec{\omega},b)\right\}^{1-c} \end{equation} ここで、$s$ は $c=1$ となる確率である。$s$ と $\vec{x}$ を結びつけるモデルが必要である。1次元ロジスティック回帰では次のモデルを考える。 \begin{eqnarray} s(1\;|\;\vec{x}\;;\;\vec{\omega},b) &=& \sigma\left(f(\vec{x}\;;\;\vec{\omega},b)\right)\nonumber \\ \sigma(a) &=& \frac{1}{1+\exp{(-a)}}\label{sigmoid}\\ f(\vec{x}\;;\;\vec{\omega},b) &=& \vec{\omega}^{\;T}\cdot\vec{x}+b \label{projection} \end{eqnarray} 関数 $\sigma$ はシグモイド関数と呼ばれ、以下のような形をしている。
ベクトル $\vec{x}$ を式(\ref{projection})により1次元に射影し、その結果を式(\ref{sigmoid})を使って区間(0,1)に射影し、これを確率とみなすわけである。式(\ref{nll})をパラメータ $(\vec{\omega},b)$ で微分するのであるが、その前に少しだけ式を一般化する。いま、$\vec{x}$ に1次元加えたベクトルを導入する。 \begin{equation} \vec{X}=(\vec{x},1) \end{equation} 最後の次元の値は常に1である。さらに、$\vec{\Omega}$ を次式で定義する。 \begin{equation} \vec{\Omega}=(\vec{\omega},b) \end{equation} このとき関数 $f$ は \begin{equation} f(\vec{X}\;;\;\vec{\Omega}) = \vec{\Omega}^{\;T}\cdot\vec{X} \label{new_projection} \end{equation} と書くことができる。この表式を使うと $L$ は \begin{equation} L(\vec{\Omega})=-\sum_{i=1}^{N} \left\{ c^{i}\ln{s(1\;|\;\vec{X}^{\;i}\;;\;\vec{\Omega})} + (1-c^{i}) \ln{ \left( 1-s(1\;|\;\vec{X}^{\;i}\;;\;\vec{\Omega}) \right) } \right\} \end{equation} となる。ただし、 \begin{eqnarray} s(1\;|\;\vec{X}\;;\;\vec{\Omega}) &=& \sigma\left(f(\vec{X}\;;\;\vec{\Omega})\right)\nonumber \\ \sigma(a) &=& \frac{1}{1+\exp{(-a)}}\label{new_sigmoid}\\ f(\vec{X}\;;\;\vec{\Omega}) &=& \vec{\Omega}^{\;T}\cdot\vec{X} \label{new_new_projection} \end{eqnarray} である。この式を $\vec{\Omega}$ で微分する。シグモイド関数なので計算は容易である。 \begin{equation} \frac{\partial L(\vec{\Omega})}{\partial \vec{\Omega}}=-\sum_{i=1}^{N}\;\vec{X}^{\;i} \left(c^{i}-s(1\;|\;\vec{X}^{\;i}\;;\;\vec{\Omega})\right) \label{gradient} \end{equation} これを0と置いたときの解が求める $\vec{\Omega}$ であるが、これ以上の解析計算は不可能である。そこで、勾配降下法を使って数値計算を行なう。手順は以下の通りである。
  1. $\vec{\Omega}$に適当な初期値を与える。
  2. 次式で $\vec{\Omega}$ を更新する。 \begin{equation} \vec{\Omega}\leftarrow \vec{\Omega} - \eta \frac{\partial L(\vec{\Omega})}{\partial \vec{\Omega}} \end{equation} ここで $\eta$ は学習率と呼ばれる正の量である。収束速度を調節するパラメータである。
  3. $L$ の変化量がしきい値以下となるまで上記を繰り返す。あるいは、エラー $E$ \begin{equation} E=\sum_{i=1}^{N}\;\left|c^{i}-s(1\;|\;\vec{X}^{\;i}\;;\;\vec{\Omega})\right| \end{equation} の変化量がしきい値以下となるまで繰り返しても良い。この量は理想的には0になって欲しい量である。

確率的勾配降下法(Stochastic Gradient Descent:SGD)


 式(\ref{gradient})を見て分る通り、通常の勾配降下法では $\vec{\Omega}$ の更新ごとに全観測値についての和を取る必要がある。大規模データの場合、これでは大変時間がかかる。そこで、$\vec{\Omega}$ の更新に使うデータをランダムに取り出すことを考える。この手法を確率的勾配降下法と呼ぶ。 手順は以下の通りである。
  1. データをシャッフルしたあと、複数のグループに分割する。たとえば、1000個のデータを10個のデータのグループに分割する。各グループはミニバッチ(minibatch)と呼ばれる。
  2. $\vec{\Omega}$に適当な初期値を与える。
  3. 次式で $\vec{\Omega}$ を更新する。
    • $\mbox{for}\;\;\;\;k = 1, \cdots,$ \begin{equation} \vec{\Omega}\leftarrow \vec{\Omega} - \eta \left\{ -\frac{1}{|\Lambda^{k}|} \sum_{i\;\in\;\Lambda^k}\;\vec{X}^{\;i} \left(c^{i}-s(1\;|\;\vec{X}^{\;i}\;;\;\vec{\Omega})\right) \right\} \label{grad} \end{equation}
    ここで $\Lambda^{k}$ は $k$ 番目のミニバッチを、$|\Lambda^{k}|$ はそこに含まれるデータの数を表す。
  4. 先の勾配法と同じように何らかの量がしきい値以下となるまで上記を繰り返す。

実装


 2次元平面に、(5,5)と(0,0)を中心にした2つの正規分布を使って1000個ずつ点を生成し、2分類問題を行なった。ミニバッチのサイズを10、学習率を0.1とした。Theanoを使って実装を行なった。
  • 45,46行目:行列とベクトルのシンボルを作成する。前者は座標を後者はラベルを格納する。
  • 49行目:パラメータ $\vec{\Omega}$ を表す共有変数である。
  • 55行目:$f$ を表すTheano Expression Graphである。
  • 58行目:$\sigma$ を表すTheano Expression Graphである。
  • 61行目:Negative Log Likelihood(NLL) を表すTheano Expression Graphである。
  • 64行目:ミニバッチ内でのNLLの平均値である。
  • 67行目:$\vec{\Omega}$についての微分を表すTheano Expression Graphである。
  • 70行目:学習率 $\eta$ を表す共有変数である。
  • 71行目:$\vec{\Omega}$ の更新を表現するTheano Functionである。
  • 76行目:$\eta$ の更新を表現するTheano Functionである。
  • 79行目:サンプルを作成する。
  • 84〜92行目:勾配降下法を実行する
  • 下図における青線が、識別関数 $f(\vec{X}\;;\;\vec{\Omega}) = \vec{\Omega}^{\;T}\cdot\vec{X}=0$ である。
    このときのエラー $E$(プログラム中のリストerrors)を下に示す。合計2000個のデータを200個のミニバッチに分割し、これを10回繰り返したので横軸の最大値は2000である。 振動しながら小さくなっていく様子が分かる。

    0 件のコメント:

    コメントを投稿