スキップしてメイン コンテンツに移動

ロジスティック回帰 理論編

Introduction


今日はロジスティック回帰について書こうと思います。ロジスティック回帰は機械学習の中でも基本とされています。ロジスティック回帰は二値を分類するためのアルゴリズム、モデルです。

概要

この記事はPRMLを参考に書かせていただいています。
最適化には反復再重みづけ最小二乗法を用いています。
  • シグモイド関数
  • 分類のための確率を定義
  • 交差エントロピー誤差関数
  • 反復再重みづけ最小二乗法

シグモイド関数

初めにシグモイド関数を定義します。
以下のような関数です。
\[\sigma(a) = \frac{1}{1+\exp(a)}\]
後に扱うので、シグモイド関数の微分を計算しておきます。きれいな形をしています。
\begin{eqnarray*} \frac{d}{d a} \frac{1}{1+\exp(a)} &=& \frac{\exp(-a)}{(1+\exp(-a))^2} \\ &=& \frac{1}{1+\exp(-a)} \frac{\exp(-a)}{1+\exp(-a)}\\ &=& \frac{1}{1+\exp(-a)} \{ \frac{1+\exp(-a)}{1+\exp(-a)} - \frac{1}{1+\exp(-a)} \} \\ &=& \sigma(a)(1-\sigma(a)) \end{eqnarray*}
シグモイド関数は機械学習において大事な役割を果たしています。
シグモイド関数は以下のような形をしています。
enter image description here
これを見てわかる通り、シグモイド関数は次のような性質を持っています。
  • シグモイド関数は 定義域は\((-\infty,\infty)\)で定義され、値域は\((0,1)\)で定義されています
  • シグモイド関数は単調増加関数です
  • シグモイド関数は(0,0.5)で点対称です
シグモイド関数の値を確率として考えることができるようになります。

分類のための確率の定義

初めにデータが正しく分類されたかの確率を考えてみる。
enter image description here
この直線は超平面だと思ってください。
超平面は以下のように表されます。
\[w^T x= 0\]
wは超平面に対する法線ベクトルになります。
  • \(w^T x > 0\)の時\(x\)は赤い領域にいる
  • \(w^T x < 0\)の時\(x\)は青い領域にいる
もし、データ点が赤い領域に属しているのならそのデータ点のクラスは\(C_1\).
また、データ点が青い領域に属しているのならそのデータ点のクラスは\(C_2\)
\(C_1\) は1を \(C_2\)は0をそれぞれラベルとして持っています。
私たちは、超平面から遠いデータ点ほど分類の結果に確信を持てます。
しかし、超平面に近いデータ点は必ずしもそうではないですよね。
超平面に近いデータ点に割り当てられたクラスはそんなに信用できない。
よって、シグモイド関数の性質を使う時が来た。超平面からデータポイントまでの距離を確率としてみましょう。
  • 確率が0.5を超えているとき\((C_1)\)のクラスに属しているとみなす。
  • 確率が0.5の時、どちらのクラスに属しているかはわからない。(データ点が超平面上にあることをさす。)
  • 確率が0.5を超えないとき、\((C_2)\) のクラスに属しているとみなす。
これをシグモイド関数を用いることで実現します。
シグモイド関数はこれらの性質をうまく実現してくれます。
よって、距離をシグモイド関数にいれた値を確率として扱います。

交差エントロピー誤差関数

データ集合が \(\{\phi_n,t_n\}\)で与えられているとき、 確率を次のように考えます。
\[\sigma(w^T \phi_n)\]
この確率に対する尤度関数を考えます。
\[p(t|w) = \Pi_{n=1}^{N} y_{n}^{t_n} \{1-y_n\}^{1-t_n}\]
ただし、
\[y_n = \sigma(w^T \phi_n) \]
\[t = (t_1,t_2,,,t_n)^T\]
y_n は\(\phi_n\) が\(C_1\) に属している確率です。
この尤度関数の負の対数をとると、対数の性質から次のようになります。
\[E(w) = -\log p(t|w) = - \sum_{n=1}^{N} \{t_n \log(y_n) + (1-t_n ) \log(1-y_n)\}\]
尤度関数の最大化は、この\(E(w)\)の最小化と同値になります。(対数は単調増加関数のため、最適解が変わらない)
\(E(w)\) は交差エントロピー誤差関数とゆわれています。

IRLS

IRLS は反復再重みづけ最小二乗のことです。最適化のためのこのアルゴリズムではニュートン法が用いられています。
E(w)を\(w\)について微分しましょう。
\begin{eqnarray*} \nabla E(w) &=& \nabla - \sum_{n=1}^{N} \{t_n \log(y_n) + (1-t_n ) \log(1-y_n)\}\\ &=& \nabla - \sum_{n=1}^{N} \{t_n \log(\sigma(w^T \phi_n) + (1-t_n ) \log(1-\sigma(w^T \phi_n)\}\\ &=&-\sum_{n=1}^{N} \{ \frac{t_n \sigma(w^T \phi_n)(1-\sigma(w^T \phi_n))}{\sigma(w^T \phi_n)}\phi_n - \frac{(1-t_n) \sigma(w^T \phi_n)(1-\sigma(w^T \phi_n))}{1-\sigma(w^T \phi_n)}\phi_n \}\\ &=& -\sum_{n=1}^{N} \frac{t_n (1-\sigma(w^T \phi_n))-(1-t_n)\sigma(w^T \phi_n)}{\sigma(w^T \phi_n) (1-\sigma(w^T \phi_n))} \{\sigma(w^T \phi_n) (1-\sigma(w^T \phi_n))\} \phi_n \\ &=& -\sum_{n=1}^{N} \{t_n (1-\sigma(w^T \phi_n))-(1-t_n)\sigma(w^T \phi_n)\} \phi_n \\ &=& -\sum_{n=1}^{N} \{t_n - t_n \sigma(w^T \phi_n) - \sigma(w^T \phi_n) - \sigma(w^T \phi_n) + t_n \sigma(w^T \phi)\} \phi_n\\ &=&\sum_{n=1}^{N} \{\sigma(w^T \phi_n) - t_n \} \phi_n\\ &=& \sum_{n=1}^{N} (y_n - t_n) \phi_n\\ &=& \phi^T (y - t)\\ \end{eqnarray*}
次に、E(w)のヘッセ行列を求めましょう。
\begin{eqnarray*} H &=& \nabla \nabla E(w) \\ &=& \nabla \phi^T(y-t) \\ &=& \nabla \sum_{n=1}^{N} \phi_{n}^T (y_n-t_n) \\ &=& \nabla\sum_{n=1}^{N} (y_n-t_n) \phi_{n}^T \\ &=&\sum_{n=1}^{N} y_n(1-y_n) \phi_n \phi^T = \phi^T R \phi \end{eqnarray*}
ここでRは対角成分に\(y_n(1-y_n)\) を持つ対角行列です。
これらの式を使うとwの更新は次のようになります。
\begin{eqnarray*} w_{new} &=& w_{old} - \{ \phi^ T R \phi \}^ {-1} \phi^T (y-t) \\ &=& \{ \phi^ T R \phi \}^ T \{ \phi^ T R \phi w_{old} - \phi^T(y-t)\} \\ &=& \{ \phi^ T R \phi \} ^ {-1} \phi^ T Rz \end{eqnarray*}
ただし、
$$z=\phi w_{old} - R^{-1}(y-t)$$

この記事ではロジスティック回帰の理論的な部分を扱いました。
次はロジスティック回帰の実装の記事を書こうと思います。
次の記事も見ていただけると嬉しいです。

*実装の記事も書きました。
Implementation of Logistic Regression


コメント

このブログの人気の投稿

Implementation of Robbins monro

Robbins monro の実装 sorry, this page is Japanese only.   今回はRobbins monro の実装をしてみました。 Robbins monroは確率勾配降下法の学習率を入りテーション回数の逆数で割っていくものです。 使っているprogram言語はpython 3です。osはwindowsです。(macほしい...) アルゴリズム 確率勾配降下方とは目的関数の最適解を求めるアルゴリズムです。目的関数をf(X)とすると、手順は以下のようになっています。 初期学習率$n_0$を決めます。訓練データDを用意します。この訓練データは複数の初期値の集まりです。 訓練データから一つ初期値をランダムに取り出し、これを$x_0$とし、最初の予測値とします。 次の式に現在の予測値$x_0$を代入し、新たな予測値$x_{n+1}$を得ます。$$x_{n+1} = x_{n} - \frac{n_0}{n} grad f(X_n)$$ 収束して入れば4へ、収束していなければ2で得られた値$x{n+1}$を新たに$x_n$としてもう一度2を行う。 訓練データを一周していなければ2へ、一周していれば各初期値から得られた解の中から目的関数を最も小さくするものを選ぶ。   実装例 以下の目的関数を最小化させてみましょう。 $$f(x,y) = (x-2)^2 + (y-3)^2 $$ コマンドラインでpythonを実行していきます。 予想通り、(2,3)という解を導き出してくれました。目的関数が簡単だったので、初期値をどの値でとってもばっちり正解にたどり着いてくれました。 CODE 以下にRobbins monroの関数だけ置いておきます。 こちら にすべてのコードを載せています。 def Robbins_monro(function,grad,number_variable_gradient): init_learning_rate = 1.5 stepsize = 1000 init_value = np.array([range(-1000,1020,20) for i in range(number_v...

ダイクストラ法

Introduction English ver 今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this page を見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。 この スライド はダイクストラ法を説明したスライドです。 Overview アルゴリズム 実装 アルゴリズム このアルゴリズムは スタート始点のノードを決める。そして、それをAと名付ける。 各ノードに$d=\infty$を割り当てる。ただし、スタート地点はd=0 Aの隣接ノードのリストをadj_listと名付ける。  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj. グラフnetworkからAを取り除く グラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。 となっています。 このアルゴリズムを図を用いて説明します。  このグラフを使って説明します。  初めに、スタート地点を決めます。そして、各ノードに$d=\infty$を割り当てます。  Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。 次にAを取り除きます。  次はBから始まります。Aと同じことをやります。 このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。 実装 このアルゴリズムでは$O(log(|V|^2))$という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。 しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点での...

dijkstra method

Introduction 日本語 ver Today, I will write about the dijkstra method. This method is algorithm which find the shortest distance. The map is expressed by graph. If you never see  this page , look at its page. This page explain the heap structure and definition of graph. The dijkstra method used heap structure, Because heap structure reduce the amout of calculation of dijkstra method. I use  this slide  to explain dijkstra. Overview Algorithm Implementation Algorithm This algorithm is  Decide start node, and this node named A. Allocate $d=\infty$ for each node, but d=0 for start node. Adjacent node of A named adj_list.  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj. Remove A from graph network. Find node which have the smallest d and it named A, and if network have node, back to 4. I explain this algorithm by drawing.  I explain algorithm by using this graph.  Fis...