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

Theorem of Logistic regression.

Introduction


Today, I will write about Logistic regression. Logistic regression is the basis of Machine Learning. Logistic regression is the model to classify two value

Overview

This post is written by using PRML for reference.
Optimization is used for Iterative reweighted least squares method.

  • First, I will introduce the sigmoid function
  • Second, I will define probability to classify
  • Third, I will write cross-entropy error function
  • Fourth, I will explain IRLS
Firstly, We define Sigmoid function.
sigmoid function is following.

\[\sigma(a) = \frac{1}{1+\exp(a)}\]

I will compute differential of this function.

\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*}

This function is very important in terms in terms of Machine Learning.
Because Sigmoid function has the following form.
enter image description here
The sigmoid function has the following characteristic.
  • Sigmoid function is defined on \((-\infty,\infty)\)
  • and, range of y is (0,1).
  • The sigmoid function is monotonic increase function.
  • Sigmoid function is point-symmetry in (0,0.5)
We regard the value of the sigmoid function as the probability.

Probability of classifying

First, We think of probability that data is properly classified.
enter image description here

This line is a hyperplane.
a hyperplane is expressed as follows.

\[w^T x= 0\]

w is a normal vector of the hyperplane.
  • Data point exist red domain when \(w^T x > 0\)
  • Data point exist blue domain when \(w^T x < 0\)
If data is exists in red domain, the data is belong \(C_1\).
If data exists in the blue domain, the data is belonging \(C_2\)
\(C_1\) have 1 as a label. \(C_2\) have 0 as a label.

We can have confidence that I know the class of data exist far from the hyperplane, but we do not know the class of data when data point exists near hyperplane.

We want not to believe the class of data predicted near hyper plane.

Therefore!!, I use disposition of Sigmoid function. I change the distance from
the hyperplane to data point into probability.
  • I handle that data point exist red domain\((C_1)\) when the probability is higher than 0.5.
  • When probability has just 0.5, I do not know the class of data. (The data exist on the hyperplane)
  • I handle that data point exist blue domain \((C_2)\) when the probability is lower than 0.5.
I summarize this paragraph. I want to handle as follows.
  • The farther the distance between a data point and the hyperplane is the farther keep probability away from 0.5.
  • The nearer the distance between a data point and the hyperplane is, the nearer probability is 0.5.
  • When the probability is near 1, I have confidence that class of the data is \(C_1\)
  • When the probability is near 0, I have confidence that class of the data is \(C_2\)
I implement this way of thinking by using the sigmoid function.
Sigmoid function fulfill these way of thinking.

Thus, I handle probability value which output of sigmoid function by input distance between datapoint and hyperplane.

Cross-entropy error function

when Data set is \(\{\phi_n,t_n\}\), I define probability by using Sigmoid function.
here, \(t_n \in {0,1}\)
I define likelihood function as follows.
\[p(t|w) = \Pi_{n=1}^{N} y_{n}^{t_n} \{1-y_n\}^{1-t_n}\]
here,\[y_n = \sigma(w^T \phi_n) \]
\[t = (t_1,t_2,,,t_n)^T\]
\(w^T x\)is distance between \(\phi\) and hyper plane.
y_n is probability that \(\phi_n\) is \(C_1\)
I get negative logarithm about likelihood function.
\[E(w) = -\log p(t|w) = - \sum_{n=1}^{N} \{t_n \log(y_n) + (1-t_n ) \log(1-y_n)\}\]

\(E(w)\) is called Cross-entropy error function

IRLS

IRLS is iterative reweighted least squares method. This method estimate w by using the Newton-Raphson method.

I get gradient of E(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*}
I get Hessian matrix of 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*}
here, R is daiagonal matrix and have \(y_n(1-y_n)\) element of (n,n)
I use These form to estimate by Newton-Raphson method.
\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*}

Thus, w is updated by this form.
This post is Theory ed of Logistic Regression.
Next, I implement Logistic Regression.
I am glad to see my next post.

*I wrote the implementation of Logistic Regression.
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...