回顾 Review
在上一节课 Classification中，讨论了如何通过样本点的均值$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)}$计算得到新的样本点$x$属于class 1的概率，由于是二元分类，属于class 2的概率$P(C_2|x)=1-P(C_1|x)$。
然后推导了$P(C_1|x)=\sigma(z)=\frac{1}{1+e^{-z}}$，并且在Gaussian distribution下考虑class 1和class 2共用$\Sigma$，可以得到一个线性的z(其实很多其他的Probability model经过化简以后也都可以得到同样的结果)
从上式中我们可以看出，现在这个model(function set)是受$w$和$b$控制的，因此我们不必要再去像前面一样计算那些与概率相关的东西，而是直接计算$w$和$b$，用这个全新的由$w$和$b$决定的model——Logistic Regression逻辑回归。
1.Three Steps of Logistic Regression
现在来用机器学习的“三步走”分析一下逻辑回归。
Step 1: Function Set
由所有不同的$w$和$b$组成的函数的集合就是Logistic Regression的Function set。
$w_i$：weight，$b$：bias，$\sigma(z)$：sigmoid function，$x_i$：input
Step 2：Goodness of a function
现在我们有N笔Training data，每一笔data都要标注它是属于哪一个class。假设这些Training data是从我们定义的posterior Probability中产生的(后置概率，某种意义上就是概率密度函数)，而w和b就决定了这个posterior Probability，那么就可以去计算某一组w和b去产生这N笔Training data的概率，利用极大似然估计的思想，求出使得似然函数取最大值时的那组参数$w^$和$b^$。
似然函数只需要将每一个点产生的概率相乘即可，注意，这里假定是二元分类，class 2的概率为1减去class 1的概率。
由于$L(w,b)$是乘积项的形式，为了方便计算，我们将上式做个变换，求$L$的最大值相当于求$-\ln L$的最小值：
由于class 1和class 2的概率表达式不统一，上面的式子无法写成统一的形式，为了统一格式，这里将Logistic Regression里的所有Training data都打上0和1的标签，即output $\hat{y}=1$代表class 1，output $\hat{y}=0$代表class 2，于是上式进一步改写成：
现在已经有了统一的格式，我们就可以把要minimize的对象写成一个summation的形式：
这里$x^n$表示第n个样本点，$\hat{y}^n$表示第n个样本点的class标签(1表示class 1,0表示class 2)，最终这个summation的形式，里面其实是两个Bernouli distribution(两点分布)的cross entropy(交叉熵)。
假设有如上图所示的两个distribution $p$和$q$，它们的交叉熵就是$H(p,q)=-\sum\limits_{x} p(x) \ln (q(x))$，这也就是之前的推导中在$-\ln L(w,b)$前加一个负号的原因。
cross entropy 交叉熵的含义是表达这两个distribution有多接近，如果$p$和$q$这两个distribution一模一样的话，那它们算出来的cross entropy就是0，而这里$f(x^n)$表示function的output，$\hat{y}^n$表示预期 的target，因此交叉熵实际上表达的是希望这个function的output和它的target越接近越好
总之，我们要找的参数实际上就是：
step 3：Find the best function
实际上就是去找到使loss function即交叉熵之和最小的那组参数$w^,b^$，这里依然可以使用gradient descent的方法。
sigmoid function $\sigma(z)=\frac{1}{1+e^{-z}}$的微分可以直接作为公式记下来：$\frac{\partial \sigma(z)}{\partial z}=\sigma(z)(1-\sigma(z))$。
先计算$-\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只需要做：
那这个式子到底代表着什么意思呢？现在你的update取决于三件事：
- learning rate，是你自己设定的；
- $x_i$，来自于data；
- $\hat{y}^n-f_{w,b}(x^n)$，代表function的output跟理想target的差距有多大，如果离目标越远，update的步伐就要越大。
通过上面的分析，我们可以将Logistic Regression和Linear Regression的三个步骤作一个对比：
2.Logistic Regression + Square error？
这里可能会有一个疑惑，为什么Logistic Regression的loss function不能像linear Regression一样用square error来表示呢？我们试着用square error来定义Loss function重新写一下Logistic Regression的三个步骤：
这样就会遇到一个问题：如果第n个点的目标target是class 1，则$\hat{y}^n=1$，此时如果function的output $f_{w,b}(x^n)=1$的话，说明现在离target很接近了，$f_{w,b}(x)-\hat{y}$这一项是0，于是得到的微分$\frac{\partial L}{\partial w_i}$会变成0，这件事情是很合理的；但是当function的output $f_{w,b}(x^n)=0$的时候，说明离target还很遥远，但是由于在step3中求出来的update表达式中有一个$f_{w,b}(x^n)$，因此这个时候也会导致得到的微分$\frac{\partial L}{\partial w_i}$变成0，这样无论function的输出是1还是0，微分项都会是0，导致在做gradient descent时参数无法获得更新。如果举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更顺利。
3. Discriminative v.s. Generative
same model but different currency
Logistic Regression的方法，称之为Discriminative的方法；而上节课中用Gaussian来描述posterior Probability来建立Generative model的方法，称之为Generative的方法。
实际上它们用的model(function set)是一模一样的，都是$P(C_1|x)=\sigma(w\cdot x+b)$，如果是用Logistic Regression的话，可以用gradient descent的方法直接去把b和w找出来；如果是用Generative model的话，我们要先去算$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的方法表现得更好，这里举一个简单的例子来解释一下：
Testing data的两个feature都是1，凭直觉来说会认为它肯定是class 1。但是如果用naive bayes的方法(朴素贝叶斯假设所有的feature相互独立，方便计算)，却会得到相反的结果：
Discriminative model在data充足的情况下，它训练出来的model的准确率一般是比Generative model要来的高的。但是Generative的方法也有它自己的优势：它对data的依赖并没有像discriminative model那么严重，在data数量少或者data本身就存在noise的情况下受到的影响会更小，而它还可以做到Prior部分与class-dependent部分分开处理，如果可以借助其他方式提高Prior model的准确率，对整一个model是有所帮助的(比如前面提到的语音辨识)。
4.Multi-class Classification
之前讲的都是二元分类的情况，这里讨论一下多元分类问题，其原理的推导过程与二元分类基本一致
假设有三个class：$C_1,C_2,C_3$，每一个class都有自己的weight和bias，这里$w_1,w_2,w_3$分布代表三个vector，$b_1,b_2,b_3$分别代表三个const，input x也是一个vector
softmax的意思是对最大值做强化，因为在做第一步的时候，对$z$取exponential会使大的值和小的值之间的差距被拉得更开，也就是强化大的值。
我们把$z_1,z_2,z_3$丢进一个softmax的function，softmax做的事情是这样三步：
- 取exponential，得到$e^{z_1},e^{z_2},e^{z_3}$
- 把三个exponential累计求和，得到total sum=$\sum\limits_{j=1}^3 e^{z_j}$
- 将total sum分别除去这三项(归一化)，得到$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}}$
原来的output $z$可以是任何值，但是做完softmax之后，output $y_i$的值一定是介于0~1之间，并且其和一定是1，$\sum\limits_i y_i=1$。softmax的output，就是拿来当z的posterior probability。
假设我们用的是Gaussian distribution(共用covariance)，经过一般推导以后可以得到softmax的function，而从information theory也可以推导出softmax function，Maximum entropy本质内容和Logistic Regression是一样的，它是从另一个观点来切入为什么我们的classifier长这样子。
multi-class classification的过程：
如下图所示，input $x$经过三个式子分别生成$z_1,z_2,z_3$，经过softmax转化成output $y_1,y_2,y_3$，它们分别是这三个class的posterior probability，由于summation=1，因此做完softmax之后就可以把y的分布当做是一个probability contribution，我们在训练的时候还需要有一个target，因为是三个class，output是三维的，对应的target也是三维的，为了满足交叉熵的条件，target $\hat{y}$也必须是probability distribution，这里我们不能使用1,2,3作为class的区分，为了保证所有class之间的关系是一样的，这里使用类似于one-hot编码的方式，即:
这个时候就可以计算一下output $y$和 target $\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分隔开来。关于这种不可分问题，还有几个点最多可以分几类的问题的深入分析可以看林轩田老师的《机器学习基石》课程的Lecture 5和Lecture 6。
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(连接)起来，让一个input $x$的两个feature $x_1,x_2$经过两个Logistic Regression的transform，得到新的feature $x_1’,x_2’$，在这个新的feature space上，class 1和class 2是可以用一条直线分开的，那么最后只要再接另外一个Logistic Regression的model(对它来说，$x_1’,x_2’$才是每一个样本点的”feature”，而不是原先的$x_1,x_2$)，它根据新的feature，就可以把class 1和class 2分开。
因此着整个流程是，先用n个Logistic Regression做feature Transformation(n为每个样本点的feature数量)，生成n个新的feature，然后再用一个Logistic Regression作classifier
Logistic Regression的boundary一定是一条直线，它可以有任何的画法，但肯定是按照某个方向从高到低的等高线分布，具体的分布是由Logistic Regression的参数决定的，每一条直线都是由$z=b+\sum\limits_i^nw_ix_i$组成的(二维feature的直线画在二维平面上，多维feature的直线则是画在多维空间上)
下图是二维feature的例子，分别表示四个点经过transform之后的$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的效果(:3_ヽ)_，如果我们把每一个Logistic Regression叫做一个neuron(神经元)，把这些Logistic Regression串起来所形成的network，就叫做Neural Network 类神经网路，那我们已经开始接触到Deep Learning了∠(ᐛ」∠)＿。
