内容提要
《机器学习》第三课主要讲解以下5方面内容：
Locally weighted regression（局部加权回归）
probabilistic interpretation（线性回归的概率解释）
logistic regression（logistic回归）
二元分类
sigmoid函数
梯度上升
digression：perceptron（感知器算法）
Newton's method（牛顿方法）
本篇为lecture 3-3，包括逻辑回归、感知器算法。牛顿方法将在lecture 4中介绍。
先回顾lecture 3-1、3-2讲过的内容：
局部加权回归（LWR）：
如果特征数目选择过少会出现欠拟合情况，如果特征数目选择过多会出现过拟合情况，为使数据刚好达到拟合状态，引入局部加权回归解决这个问题。仅考虑与查询点x周围权重较高的邻近点，作为数据子集拟合直线，建立线性回归模型预测结果。使用局部加权回归算法无需担心特征选择问题。另外，该算法是非参数学习算法，其特点是参数数量随训练集呈线性增加。
线性回归的概率解释：
为什么线性回归要选择最小二乘法使代价函数J(θ)最小值？通过假设相互独立的误差项满足高斯分布，给定x、以θ为参数、输出结果y的概率满足高斯分布，将求数据y的分布转移为求参数θ的似然值。为了使数据结果y出现的概率尽可能大，因此需要求参数θ的极大似然值。而似然函数通常通过其对数进行求解，将极大似然值转移为求对数似然函数的极大值。通过公式推导从而证明最小二乘法求代价函数最小值是非常自然的方法。
CS229 lecture 3 课程内容
以下是监督学习的全新章节：分类问题。本节将介绍解决分类问题所用的logistic回归模型，以及简单介绍感知器（perceptron）学习算法。
二元分类（binary classification）
什么是分类问题？
如果尝试预测的目标变量x是连续的，比如根据房屋面积预测房屋价格，那么这个学习问题称为回归问题（regression）。 如果输出结果y为少量的离散值（如0、1），例如垃圾邮件分类器，只需要通过算法给出此邮件是1（表示垃圾邮件），还是0（表示不是垃圾邮件）即可，那么该类学习问题称为分类问题(classification)。
在分类问题中最常见的是二元分类或二分类（binary classification），如0、1。
其中，0也称为negative class（负类、负例、阴性结果），用符号“-”负号表示；1也称为positive class（正类、正例、阳性结果），用符号“+”加号表示。
另外对于给定的x(i)，其相应的y(i)也称为训练样本的标签（label）。(x(i), y(i))表示 ith training example，即第i个训练样本。
基于二分类问题，可以拓展为多元分类问题（multi-class）。其解决方法的核心是分解为二分类进行求解。多分类问题也称为one-vs-all（一对多）或one-vs-rest（一对余）。
多元分类问题分解为二分类问题
（图片截图自网易云课堂《吴恩达机器学习》）
如上图所示，将训练样本分为三类。建立模型的时候，可以将所有样本分为三角形样本和非三角形样本，以此类推。
另外，上图中的紫罗兰色直线表示决策边界（decision boundary）。位于直线左侧的数据点判断为三角形，即y=1；直线右侧的数据点判断为非三角形，即y=0。决策边界可以是直线、非线性等任何形状。下图展示非线性决策边界：
非线性决策边界
问题：为什么分类问题不能用线性回归模型？
以二元分类问题为例，由于要求输出结果是0至1之间，而线性回归的结果可能出现大于1或小于0的情况。另外，如果将线性回归作为分类模型会出现分类不准确的情况。
举例说明，根据肿瘤体积大小判断该肿瘤是良性肿瘤（用0表示）还是恶性肿瘤（用1表示），通过下图说明。
对于分类问题线性回归是个糟糕的模型
图中位于x轴的红色叉号表示良性肿瘤，即y=0；y=1的红色叉号表示恶性肿瘤。以线性回归为模型，可以看到y<0.5的点（紫罗兰色直线左侧）为良性肿瘤，y>=0.5的点（紫罗兰色直线右侧）为恶性肿瘤。
但随着训练输入的恶性肿瘤样本越来越多、x坐标轴足够长的时候，发现原先的线性回归函数已经不能满足需求，更新函数后发现y<0.5的点（蓝色直线左侧），本该是良性肿瘤的数据点中包含有恶性肿瘤样本，因此分类问题用线性回归模型是个很糟糕的决定。
假设模型：sigmoid函数
为了解决上述问题，将假设函数h(x)定义如下：
其中，g(z)函数定义如下：
线性回归中假设函数h(x)=θTx，为了将线性回归的输出结果限制在0~1之间，将其输出结果θTx整体作为自变量，放入g(z)函数中。线性回归中h(x)的假设如下：
g(z)函数称为logistic函数或sigmoid函数，它的函数图像如下：
sigmoid函数图像
（关于绘制图像的python代码请参考下篇文章）
从图中我们可以看出，当g(z)趋近于1时，z趋近于无穷大（z→∞）；当g(z)趋近于0时，z趋近于无穷大（z→-∞）。因为g(z)的结果在0-1之间，所以根据h(x)=g(θTx)，因此h(x)的输出结果很自然地限制在0-1之间。
同样的根据惯例，令x0=1，θTx的结果整理为
因此选择logistic函数为分类模型，其求导结果在后面的推导中用到，即
g’(z)=g(z)(1-g(z))。
g(z)具体求导过程如下：
g(z)具体求导过程
拟合参数θ
确定合适的模型（即logistic回归模型）后，参考线性回归的分析方法，接下来是确定参数θ。
那么参考线性回归的概率解释，将分类模型赋予一系列概率假设，通过极大似然估计拟合参数。
step1：概率表达式
假设
说明：上式表示给定x，以θ作为参数，y=1的概率为hθ(x)；y=0的概率为1-hθ(x)。因为y的输出结果要么是1，要么是0，所以两者出现的概率之和为1。
将上述假设合二为一，写成简洁的形式如下：
说明：当y=1时，1-y=0，任何数的零次方结果是1，则第二项1-hθ(x)的结果为1，表达式为p(y|x;θ)=(hθ(x))y；当y=0时，第一项(hθ(x))0=1，所以概率表达式为p(y|x;θ)=(1-hθ(x))1-y。是不是很巧妙~
step2：参数θ的似然函数
假设m个训练样本是独立生成的（样本间相互独立），因此参数θ的似然函数等于m个样本的数据向量y出现的概率，等于第i个样本数据y概率的连乘积结果，将上式代入，整理结果如下。
step3：参数θ的对数似然函数
参考线性回归的概率解释，求参数θ的极大似然估计，等同于求其对数似然函数ℓ(θ)的极大值，所以对似然函数L(θ)取对数进行处理，得到如下表达式。
ℓ(θ)表达式的整理过程如下：
对数似然函数ℓ(θ)表达式的整理过程
梯度上升
其实从ℓ(θ)的表达式中不能直接得出极大似然值结果，所以为了拟合参数θ，参考线性回归求参数θ的方法。
在线性回归中，为了得到代价函数J(θ)最小值，采用梯度下降法。而分类问题（logistic回归）想要得到极大似然值，则采用梯度上升算法（gradient ascent），将对数似然函数ℓ(θ)求导。
梯度上升算法：
梯度上升算法：不断将新生成的θ替换原来的θ，加上学习率α，乘以代价函数（这里是对数似然函数）的梯度。注意：梯度上升采用“+”加号。（梯度下降采用“-”减号）
step4：极大似然估计（梯度上升求导ℓ(θ)）
以一例训练样本(x,y)为例，利用随机梯度上升法对ℓ(θ)求导。因为随机梯度上升法每次更新参数只需迭代一个样本，速度快。关于随机梯度下降算法的介绍参见文章：从入门到放弃：监督学习之梯度下降（吴恩达《机器学习》监督学习笔记）。
ℓ(θ)求导结果如下：
在求导过程中，应用了g’(z)=g(z)(1-g(z))的这一结论。ℓ(θ)具体求导过程如下，供参考。
ℓ(θ)具体求导过程
将ℓ(θ)求导结果代入梯度上升表达式，得到如下结果，即为拟合θ的表达式。
虽然上述表达式从形式上看起来很像梯度下降使用的LMS更新法则（least mean square update rules），但它们之间没有任何关系，因为假设函数h(x)不同。
表 梯度上升与梯度下降的比
虽然表面上结论相似，但这是个完全不同的算法。这并不是巧合，可以推广为广义的学习算法。
如果强制logistic回归精准输出0或1，那么需要修改g(z)函数为阈值函数（threshold function），如下所示：
与logistic回归不同的是，这里的g(z)称为阶跃函数（step function），即数值直接从0跳跃到1。阶跃函数图像为：
阶跃函数图像
根据前面logistic回归提到的假设hθ(x)=g(θTx)，以及上述g(z)函数，结合更新学习规则：
得到感知器学习算法。
感知器这个名词最初来自于建立人脑神经元工作的模型。
虽然感知器学习规则与logistic回归中的梯度上升出奇的相似，但与其他算法相比，这是一类非常不同的学习规则。在以后的算法学习中，会利用其简单性作为基本构造步骤。
另外，感知器算法的风格和之前的最小二乘回归以及logistic回归相比，十分不同。因为它生成的值要么是1，要么是0。实际上，为感知器赋予概率意义非常困难。
关于logistic回归：
1、给出分类问题不能用线性回归解决的原因
因为分类问题要求输出结果y∈{0,1}，而线性回归存在y<0或y>1的情况，加之线性回归模型对结果分类不准确，所以线性回归不合适解决分类问题。
2、提出假设，寻找合适的模型
利用sigmoid函数（也称为logistic函数）输出结果在0-1之间的特性，将线性回归结果限制在0-1之间，因此将logistic回归作为解决分类问题的模型。
其实，logistic回归与“回归”一点关系也没有，因为历史原因写成regression，其实logistic回归是classification分类问题。
3、拟合参数θ
我将求解θ的套路称之为神奇四步走：
step1：概率表达式
step2：参数θ的似然函数
step3：参数θ的对数似然函数
step4：极大似然估计（利用梯度上升对ℓ(θ)求导）
虽然logistic回归与线性回归在最后求参数θ的表达式（学习规则）相同，但由于二者所用的h(x)假设不同，所以是不同的算法。
关于感知器算法，将线性回归结果套用在阶跃函数上，强制其输出结果要么是0要么是1。该算法也是与线性回归、logistic回归完全不同的算法。
补充：
Binary classification 二元分类
gradient ascent 梯度上升
step function 阶跃函数（阶梯函数）
参考视频
https://open.163.com/movie/2008/1/E/B/M6SGF6VB4_M6SGHM4EB.html
参考讲义
http://cs229.stanford.edu/notes/cs229-notes1.pdf
相关文章
笔记 | 线性回归的概率解释（吴恩达CS229《机器学习》lecture 3-2）
机器学习笔记 | 局部加权回归（吴恩达《机器学习》lecture 3-1）
从入门到放弃：监督学习之梯度下降（吴恩达《机器学习》监督学习笔记）lecture 2-2
用探索八卦的好奇心学习线性回归（吴恩达《机器学习》监督学习整理笔记）lecture 2-1
吴恩达《机器学习》课程入门介绍的整理笔记 lecture 1
版权声明：公号千万篇，版权第一条。转载不规范，博主两行泪。
联系客服
