Logistic Regression

Review

$u$ $\Sigma$ $P(C_1),P(C_2),P(x|C_1),P(x|C_2)$ $P(C_1|x)=\frac{P(C_1)P(x|C_1)}{P(C_1)P(x|C_1)+P(C_2)P(x|C_2)}$ $P(C_2|x)=1-P(C_1|x)$

$P(C_1|x)=\sigma(z)=\frac{1}{1+e^{-z}}$ $\Sigma$ ，可以得到一个线性的z(其实很多其他的Probability model经过化简以后也都可以得到同样的结果)

P_{w,b}(C_1|x)=\sigma(z)=\frac{1}{1+e^{-z}} \\ z=w\cdot x+b=\sum\limits_i w_ix_i+b \\

这里的w和x都是vector，两者的乘积是inner product，从上式中我们可以看出，现在这个model(function set)是受w和b控制的，因此我们不必要再去像前面一样计算一大堆东西，而是用这个全新的由w和b决定的model——Logistic Regression(逻辑回归)

Three Steps of machine learning

Step 1：function set

这里的function set就是Logistic Regression——逻辑回归

$w_i$ $b$ $\sigma(z)$ $x_i$ ：input

Step 2：Goodness of a function

现在我们有N笔Training data，每一笔data都要标注它是属于哪一个class

$w^*$ $b^*$

似然函数只需要将每一个点产生的概率相乘即可，注意，这里假定是二元分类，class 2的概率为1减去class 1的概率

$L(w,b)$ 是乘积项的形式，为了方便计算，我们将上式做个变换：

\begin{split} &w^*,b^*=\arg \max\limits_{w,b} L(w,b)=\arg\min\limits_{w,b}(-\ln L(w,b)) \\ &\begin{equation} \begin{split} -\ln L(w,b)=&-\ln f_{w,b}(x^1)\\ &-\ln f_{w,b}(x^2)\\ &-\ln(1-f_{w,b}(x^3))\\ &\ -... \end{split} \end{equation} \end{split}

$\hat{y}=1$ $\hat{y}=0$ 代表class 2，于是上式进一步改写成：

\begin{split} -\ln L(w,b)=&-[\hat{y}^1 \ln f_{w,b}(x^1)+(1-\hat{y}^1)ln(1-f_{w,b}(x^1))]\\ &-[\hat{y}^2 \ln f_{w,b}(x^2)+(1-\hat{y}^2)ln(1-f_{w,b}(x^2))]\\ &-[\hat{y}^3 \ln f_{w,b}(x^3)+(1-\hat{y}^3)ln(1-f_{w,b}(x^3))]\\ &\ -... \end{split}

现在已经有了统一的格式，我们就可以把要minimize的对象写成一个summation的形式：

-\ln L(w,b)=\sum\limits_n -[\hat{y}^n \ln f_{w,b}(x^n)+(1-\hat{y}^n) \ln(1-f_{w,b}(x^n))]

$x^n$ $\hat{y}^n$ 表示第n个样本点的class标签(1表示class 1,0表示class 2)，最终这个summation的形式，里面其实是两个Bernouli distribution(两点分布)的cross entropy(交叉熵)

$H(p,q)=-\sum\limits_{x} p(x) \ln (q(x))$ $-\ln L(w,b)$ 前加一个负号的原因

$f(x^n)$ $\hat{y}^n$ 表示预期的target，因此交叉熵实际上表达的是希望这个function的output和它的target越接近越好

总之，我们要找的参数实际上就是：

w^*,b^*=\arg \max\limits_{w,b} L(w,b)=\arg\min\limits_{w,b}(-\ln L(w,b)=\sum\limits_n -[\hat{y}^n \ln f_{w,b}(x^n)+(1-\hat{y}^n) \ln(1-f_{w,b}(x^n))]

step 3：Find the best function

$w^*,b^*$ 就行了，这里用gradient descent的方法进行运算就ok

$\frac{\partial \sigma(z)}{\partial z}=\sigma(z)(1-\sigma(z))$ ，sigmoid和它的微分的图像如下：

$-\ln L(w,b)=\sum\limits_n -[\hat{y}^n \ln f_{w,b}(x^n)+(1-\hat{y}^n) \ln(1-f_{w,b}(x^n))]$ $w_i$ $\hat{y}^n$ $1-\hat{y}^n$ $\ln f_{w,b}(x^n)$ $\ln (1-f_{w,b}(x^n))$ $w_i$ 的偏微分即可，整体推导过程如下：

将得到的式子进行进一步化简，可得：

我们发现最终的结果竟然异常的简洁，gradient descent每次update只需要做：

w_i=w_i-\eta \sum\limits_{n}-(\hat{y}^n-f_{w,b}(x^n))x_i^n

那这个式子到底代表着什么意思呢？现在你的update取决于三件事：

learning rate，是你自己设定的
$x_i$ ，来自于data
$\hat{y}^n-f_{w,b}(x^n)$ ，代表function的output跟理想target的差距有多大，如果离目标越远，update的步伐就要越大

Logistic Regression V.s. Linear Regression

我们可以把逻辑回归和之前将的线性回归做一个比较

compare in step1

$x_i$ 加权求和，加上bias，再通过sigmoid function，当做function的output

因为Logistic Regression的output是通过sigmoid function产生的，因此一定是介于0~1之间；而linear Regression的output并没有通过sigmoid function，所以它可以是任何值

compare in step2

$f(x^n)$ $\hat{y}^n$ )在Bernoulli distribution(两点分布)下的cross entropy(交叉熵)总和

交叉熵 $f(x^n)$ $\hat{y}^n$ 各自看做Bernoulli distribution(两点分布) $l(f(x^n),\hat{y}^n)=-[\hat{y}^n \ln f(x^n)+(1-\hat{y}^n) \ln (1-f(x^n))]$ 之和，就是我们要去minimize的对象，直观来讲，就是 $f(x^n)$ $\hat{y}^n$ 越接近越好

注：这里的“看做”只是为了方便理解和计算，并不是真的做出它们是两点分布的假设

$f(x^n)$ $\hat{y}^n$ )在数值上的平方和的均值

这里可能会有一个疑惑，为什么Logistic Regression的loss function不能像linear Regression一样用square error来表示呢？后面会有进一步的解释

compare in step3

$w_i$ $\hat{y}^n$ $f(x^n)$ 都必须是在0和1之间的，而linear Regression的target和output的范围可以是任意值

Logistic Regression + Square error？

之前提到了，为什么Logistic Regression的loss function不能用square error来描述呢？我们现在来试一下这件事情，重新做一下machine learning的三个step

$\hat{y}^n=1$ $f_{w,b}(x^n)=1$ $f_{w,b}(x)-\hat{y}$ $\frac{\partial L}{\partial w_i}$ $f_{w,b}(x^n)=0$ $f_{w,b}(x^n)$ $\frac{\partial L}{\partial w_i}$ 变成0

如果举class 2的例子，得到的结果与class 1是一样的

如果我们把参数的变化对total loss作图的话，loss function选择cross entropy或square error，参数的变化跟loss的变化情况可视化出来如下所示：(黑色的是cross entropy，红色的是square error)

假设中心点就是距离目标很近的地方，如果是cross entropy的话，距离目标越远，微分值就越大，参数update的时候变化量就越大，迈出去的步伐也就越大

但当你选择square error的时候，过程就会很卡，因为距离目标远的时候，微分也是非常小的，移动的速度是非常慢的，我们之前提到过，实际操作的时候，当gradient接近于0的时候，其实就很有可能会停下来，因此使用square error很有可能在一开始的时候就卡住不动了，而且这里也不能随意地增大learning rate，因为在做gradient descent的时候，你的gradient接近于0，有可能离target很近也有可能很远，因此不知道learning rate应该设大还是设小

综上，尽管square error可以使用，但是会出现update十分缓慢的现象，而使用cross entropy可以让你的Training更顺利

Discriminative v.s. Generative

same model but different currency

Logistic Regression的方法，我们把它称之为discriminative的方法；而我们用Gaussian来描述posterior Probability这件事，我们称之为Generative的方法

$P(C_1|x)=\sigma(w\cdot x+b)$ $u_1,u_2,\Sigma^{-1}$ ，然后算出b和w

你会发现用这两种方法得到的b和w是不同的，尽管我们的function set是同一个，但是由于做了不同的假设，最终从同样的Training data里找出来的参数会是不一样的

在Logistic Regression里面，我们没有做任何实质性的假设，没有对Probability distribution有任何的描述，我们就是单纯地去找b和w(推导过程中的假设只是便于理解和计算，对实际结果没有影响)

而在Generative model里面，我们对Probability distribution是有实质性的假设的，之前我们假设的是Gaussian(高斯分布)，甚至假设在相互独立的前提下是否可以是naive bayes(朴素贝叶斯)，根据这些假设我们才找到最终的b和w

哪一个假设的结果是比较好的呢？Generative model和discriminative model的预测结果比较如下：

实际上Discriminative的方法常常会比Generative的方法表现得更好，这里举一个简单的例子来解释一下

toy example

假设总共有两个class，有这样的Training data：每一笔data有两个feature，总共有1+4+4+4=13笔data

如果我们的testing data的两个feature都是1，凭直觉来说会认为它肯定是class 1，但是如果用naive bayes的方法(朴素贝叶斯假设所有的feature相互独立，方便计算)，得到的结果又是怎样的呢？

通过Naive bayes得到的结果竟然是这个测试点属于class 2的可能性更大，这跟我们的直觉比起来是相反的，实际上我们直觉认为两个feature都是1的测试点属于class 1的可能性更大是因为我们潜意识里认为这两个feature之间是存在某种联系的，但是对Naive bayes来说，它是不考虑不同dimension之间的correlation，Naive bayes认为在dimension相互独立的前提下，class 2没有sample出都是1的data，是因为sample的数量不够多，如果sample够多，它认为class 2观察到都是1的data的可能性会比class 1要大

$P(x|C_2)=P(x_1=1|C_2)\cdot P(x_2=1|C_2)$ $P(x|C_2)$ 不能够那么轻易地被拆分成两个独立的概率乘积，也就是说Naive bayes自作聪明地多假设了一些条件

所以，Generative model和discriminative model的差别就在于，Generative的model它有做了某些假设，假设你的data来自于某个概率模型；而Discriminative的model是完全不作任何假设的

Generative model做的事情就是脑补，它会自己去想象一些事情，于是会做出一个和我们人类直觉想法不太一样的判断结果，就像toy example里，我们做了naive bayes这样一个假设(事实上我们并不知道这两个feature是否相互独立)，于是Naive bayes会在class 2里并没有出现过两个feature都是1的样本点的前提下，自己去脑补有这样的点

通常脑补不是一件好的事情，因为你给你的data强加了一些它并没有告诉你的属性，但是在data很少的情况下，脑补也是有用的，discriminative model并不是在所有的情况下都可以赢过Generative model，discriminative model是十分依赖于data的，当data数量不足或是data本身的label就有一些问题，那Generative model做一些脑补和假设，反而可以把data的不足或是有问题部分的影响给降到最低

在Generative model中，priors probabilities和class-dependent probabilities是可以拆开来考虑的，以语音辨识为例，现在用的都是neural network，是一个discriminative的方法，但事实上整个语音辨识的系统是一个Generative的system，它的prior probability是某一句话被说出来的几率，而想要estimate某一句话被说出来的几率并不需要有声音的data，可以去互联网上爬取大量文字，就可以计算出某一段文字出现的几率，并不需要声音的data，这个就是language model，而class-dependent的部分才需要声音和文字的配合，这样的处理可以把prior预测地更精确

Conclusion

对于分类的问题(主要是二元分类)，我们一般有两种方法去处理问题，一种是Generative的方法，另一种是Discriminative的方法，注意到分类问题的model都是从贝叶斯方程出发的，即

\begin{split} P(C_i|x)&=\frac{P(C_i)P(x|C_i)}{\sum\limits_{j=1}^nP(C_j)P(x|C_j)} \ \ (1) \\ &=\sigma(z)=\frac{1}{1+e^{-z}}=\frac{1}{1+e^{-(b+\sum\limits_k w_k x_k)}} \ \ (2) \end{split}

其中分子表示属于第i类的可能性，分母表示遍历从1到n所有的类的可能性，两种方法的区别在于：

$P(x|C_i)$ $P(x|C_j)$ ，结合极大似然估计法最终得到最优的参数以确定这个model的具体形式

$P(x|C_i)$ 的表达式，因此它使用的是(2)，直接去利用交叉熵和gradient descent结合极大似然估计法得到最优的b和w，以确定model的具体形式

$P(C_i|x)$ 与0.5相比较来判断它属于那个class的可能性更大

Generative model的好处是，它对data的依赖并没有像discriminative model那么严重，在data数量少或者data本身就存在noise的情况下受到的影响会更小，而它还可以做到Prior部分与class-dependent部分分开处理，如果可以借助其他方式提高Prior model的准确率，对整一个model是有所帮助的(比如前面提到的语音辨识)

而Discriminative model的好处是，在data充足的情况下，它训练出来的model的准确率一般是比Generative model要来的高的

Multi-class Classification

softmax

之前讲的都是二元分类的情况，这里讨论一下多元分类问题，其原理的推导过程与二元分类基本一致

$C_1,C_2,C_3$ $w_1,w_2,w_3$ $b_1,b_2,b_3$ 分别代表三个const，input x也是一个vector

$z$ 取exponential会使大的值和小的值之间的差距被拉得更开，也就是强化大的值

$z_1,z_2,z_3$ 丢进一个softmax的function，softmax做的事情是这样三步：

$e^{z_1},e^{z_2},e^{z_3}$
$\sum\limits_{j=1}^3 e^{z_j}$
$y_1=\frac{e^{z_1}}{\sum\limits_{j=1}^3 e^{z_j}}$ $y_2=\frac{e^{z_2}}{\sum\limits_{j=1}^3 e^{z_j}}$ $y_3=\frac{e^{z_3}}{\sum\limits_{j=1}^3 e^{z_j}}$

$y_i$ $\sum\limits_i y_i=1$ $y_i$ $y_1=0.88$ $y_2=0.12$ $y_3=0$

而softmax的output，就是拿来当z的posterior probability

假设我们用的是Gaussian distribution(共用covariance)，经过一般推导以后可以得到softmax的function，而从information theory也可以推导出softmax function，Maximum entropy本质内容和Logistic Regression是一样的，它是从另一个观点来切入为什么我们的classifier长这样子

multi-class classification的过程：

$z_1,z_2,z_3$ $y_1,y_2,y_3$ $\hat{y}$ 也必须是probability distribution，这里我们不能使用1,2,3作为class的区分，为了保证所有class之间的关系是一样的，这里使用类似于one-hot编码的方式，即

\hat{y}= \begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix}_{x \ ∈ \ class 1} \hat{y}= \begin{bmatrix} 0\\ 1\\ 0 \end{bmatrix}_{x \ ∈ \ class 2} \hat{y}= \begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix}_{x \ ∈ \ class 3}

$y$ $\hat{y}$ $-\sum\limits_{i=1}^3 \hat{y}_i \ln y_i$ ，同二元分类一样，多元分类问题也是通过极大似然估计法得到最终的交叉熵表达式的，这里不再赘述

Limitation of Logistic Regression

Logistic Regression其实有很强的限制，给出下图的例子中的Training data，想要用Logistic Regression对它进行分类，其实是做不到的

因为Logistic Regression在两个class之间的boundary就是一条直线，但是在这个平面上无论怎么画直线都不可能把图中的两个class分隔开来

Feature Transformation

如果坚持要用Logistic Regression的话，有一招叫做Feature Transformation，原来的feature分布不好划分，那我们可以将之转化以后，找一个比较好的feature space，让Logistic Regression能够处理

$x_1'$ $\begin{bmatrix}0\\0 \end{bmatrix}$ $x_2'$ $\begin{bmatrix}1\\ 1 \end{bmatrix}$ 之间的距离，重新映射之后如下图右侧(红色两个点重合)，此时Logistic Regression就可以把它们划分开来

但麻烦的是，我们并不知道怎么做feature Transformation，如果在这上面花费太多的时间就得不偿失了，于是我们会希望这个Transformation是机器自己产生的，怎么让机器自己产生呢？我们可以让很多Logistic Regression cascade(连接)起来

$x_1,x_2$ $x_1',x_2'$ $x_1',x_2'$ $x_1,x_2$ )，它根据新的feature，就可以把class 1和class 2分开

因此着整个流程是，先用n个Logistic Regression做feature Transformation(n为每个样本点的feature数量)，生成n个新的feature，然后再用一个Logistic Regression作classifier

$z=b+\sum\limits_i^nw_ix_i$ 组成的(二维feature的直线画在二维平面上，多维feature的直线则是画在多维空间上)

$x_1'$ $x_2'$ ，在新的feature space中可以通过最后的Logistic Regression划分开来

注意，这里的Logistic Regression只是一条直线，它指的是“属于这个类”或“不属于这个类”这两种情况，因此最后的这个Logistic Regression是跟要检测的目标类相关的，当只是二元分类的时候，最后只需要一个Logistic Regression即可，当面对多元分类问题，需要用到多个Logistic Regression来画出多条直线划分所有的类，每一个Logistic Regression对应它要检测的那个类

Powerful Cascading Logistic Regression

通过上面的例子，我们发现，多个Logistic Regression连接起来会产生powerful的效果，我们把每一个Logistic Regression叫做一个neuron(神经元)，把这些Logistic Regression串起来所形成的network，就叫做Neural Network，就是类神经网路，这个东西就是Deep Learning！