Processing math: 2%
スキップしてメイン コンテンツに移動

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

コメント

このブログの人気の投稿

カーネル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としま...

ダイクストラ法

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))に減らせます。ヒープ構造で現時点での...

Visualization of Variational method

Introduction Today, I will implement visualization of Variational method. Variational method is used when we want to minimize functional. functional is function of function. Please look at  [1] , [2] , [3] , [5]  and  [6] . Overview formula  Implementation Visualization Formula I used following formula. F(x) = \sqrt{1+(\frac{du}{dx}(x))^2} l(u) = \int_{0}^{1} \sqrt{1+(\frac{du}{dx}(x))^2} dx l(u) is the length of the u(x).  I want to minimize l(u) subject to u(0)=a and u(1)=b. u minimizing I(u) is  u(x) = (b-a)x+a This u is line from (0,a) to (1,b). Because l(u) is the length of the u(x), We found out that u minimizing l(u) is line. Please look  [5]  to calculate of variational method. Implementation I implement visualization of variational method to check difference of optimize curve and other curve.  Let u_A is  u_A = (b-a)x+a + A sin(8t) A sin(8t) increase the di...