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

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

コメント

このブログの人気の投稿

MAP estimation

Introduction 日本語 ver Today, I will explain MAP estimation(maximum a posteriori estimation). MAP estimation is used Bayes' thorem. If sample data is few, we can not belive value by Maximum likelihood estimation. Then, MAP estimation is enable to include our sense.  Overveiw Bayes' theorem MAP estimation Conjugate distribution Bayes' theorem  Bayes' theorem is $$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$ $P(A|B)$ is Probability when B occur. Please go on  http://takutori.blogspot.com/2018/04/bayes-theorem.html to know detail of Bayes' theorem. Map estimation Map estimation is used Bayes' theorem. Map estimation estimate parameter of population by maximuzing posterior probability. Now, suppoce we get data $x_1,x_2,...,x_n$ from population which have parameter $\theta$. Then, we want to $P(\theta|x_1,x_2,...,x_n)$. Here, we use Bayes' theorem. $$P(\theta|x_1,x_2,...,x_n) = \frac{P(x_1,x_2,...,x_n | \theta ) P(\theta)}{P(x_1,x_2,...,x_n)}...

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...

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...