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

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

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


Labels:

コメント

コメントを投稿

このブログの人気の投稿

カーネルK-means 理論編

Introduction English ver 今日は、カーネルK-meansの理論について書きます。カーネルK-meansは通常のK-meansの欠点を補うことができます。通常のK-meansの欠点とカーネルK-meansの強みも説明します。もし、まだ御覧になられていなければ、通常の K-means 理論編 の記事を見ていただけるとよいのではないかと思います。 カーネルK-meansの実装編 も併せてご覧ください。 概要 K-meansの弱点 カーネルトリック カーネルK-means アルゴリズム K-meansの弱点 例えば、次のようなデータを用意します。 このデータはK-meansによってうまく分類することはできません。なぜなら通常のK-meansでは、データとプロトタイプのユークリッド距離に依存しているからです。そのため、このような円状に分布しているデータはうまく分類することができません。 プロトタイプとはそれぞれのクラスにあり、そのクラスを代表するようなもののことです。K-meansでは各クラスの平均ベクトルとなります。それゆえ、以下のような分類になってしまいます。 このようなデータではK-meansはうまくいきません。 K-meansで分類できるデータセットは次のように各クラスで固まっている必要があります。 カーネルK-meansはK-meansの弱点を補います。 カーネルトリック 初めに、カーネルトリックを説明します。 線形分離できないようなデータ$X$を例えば次のように線形分離できるように$\phi(x)$に送る写像$\phi$を考えます。 カーネルは次のように定義されます。 $$K(x,y) = \phi(x)^T \phi(y)$$ $\phi$を具体的に計算することは難しいですが、$K(x,y)$を計算することなら簡単です。 この手法をカーネルトリックと呼ばれます。 カーネルK means K-meansの目的関数を復習しておきます。 $$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$$ ここで、 プロトタイプは$\mu_i ~\forall k \in K$としま...
コメントを投稿
続きを読む

Kullback-Leibler divergence

Introduction sorry, this page is Japanese only.   今日がダイバージェンスについて書いていきます。 ちなみにエントロピーの知識を使うのでエントロピーの記事も見てあげてください。 エントロピーの記事はこちら Kullback-Leibler Divergence 二つの確率分布の平均エントロピーの差を表す値をKLダイバージェンスといいます。 式では次のように定義されます。 $$KL(P||Q) = \int_{-\infty}^{\infty} P(X) log \frac{P(X)}{Q(X)}$$ 離散の場合は $$KL(P||Q) = \sum_{i} P(X_i) log \frac{P(X_i)}{Q(X)}$$ なぜ二つの分布間の距離をこのように定義できるのでしょうか。 式の解釈 真の分布P(X)が存在するとします。しかし、有限のデータから真の分布P(X)を求めるのは難しいです。そこで、有限のデータから推定して得られた確率分布をQ(X）とします。では真の分布P(X）と推定した分布Q(X)はどれだけ違っているのでしょうか。 ここで登場するのがエントロピーです。エントロピーはその分布の不確実性を示す値でした。 エントロピーが高いほど不確かなことが起こるとゆうことです。 P(X)のエントロピーとは$-\int_{-\infty}^{\infty} logP(X)$でした。 では推定した確率分布Q(X）は確率分布P(X)に対してどれだけ不確実性を持っているのでしょうか。エントロピーとは情報量の期待値でした。確率分布Q(X）が持つ情報量は$-logQ(X)$です。この情報量を確率P(X)で期待値をとります。 式は以下のようになります。 $$-\int_{-\infty}^{\infty} P(X) logQ(X)$$ この値と真の分布のエントロピーとの差を二つの分布間の差として定義します。式では以下のようになります。 $$-\int_{-\infty}^{\infty} P(X) logQ(X) - (--\int_{-\infty}^{\infty} P(X) logP(X)))$$ これを式変形すると $$-\int_{-\infty}^...
コメントを投稿
続きを読む

ダイクストラ法

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))に減らせます。ヒープ構造で現時点での...
コメントを投稿
続きを読む