浅谈线性回归、逻辑回归、感知机和SVM

分类和回归是机器学习可以解决两大主要问题，从预测值的类型上看，连续变量预测的定量输出称为回归；离散变量预测的定性输出称为分类。例如：预测明天多少度，是一个回归任务；预测明天阴、晴、雨，就是一个分类任务。

1.线性回归（Linear Regression）

线性回归

1.1 预测函数

在一维特征空间，线性回归是通过学习一条直线 $\scriptstyle h_\theta(x)=\theta_0+\theta_1x_1$ ，使得这条直线尽可能拟合所有已有的看到的点 $\scriptstyle y$ （观测数据），并希望未看到的数据（测试数据）也尽可能落在这条线上（泛化性能）， $\scriptstyle h_\theta$ 是预测值， $\scriptstyle y$ 是实际值。

在多维空间，线性回归表示为 $\scriptstyle h_\theta(x)=\theta_0+\theta_1x_1+\theta_2x_2+\cdots+\theta_nx_n$ ，简化形式为 $\scriptstyle h_\theta(x)=\sum_{i=0}^n\theta_ix_i=\theta^Tx$ ，我们的目的是要找一个参数 $\scriptstyle \theta$ 令 $\scriptstyle h_\theta(x)$ 对数据拟合得最好。

1.2 损失函数

那么怎样评价它对于观测到的数据点拟合得好坏呢？所以需要对我们做出的假设 $\scriptstyle h$ 进行评估，一般这个函数称为损失函数（loss function）

损失函数表示图

很直观的想法是希望预测值与实际值尽可能接近，即看预测值与实际值之间的均方误差是否最小，定义线性回归损失函数为:
$J(\theta)=\frac{1}{2m}\sum_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})^2$

所以现在变成了一个优化问题，即找到要找到令损失函数 $\scriptstyle J(θ)$ 最小的 $\scriptstyle θ$ 。定义均方误差有着非常好的几何含义，对应常用的欧式距离（Euclidean distance），基于均方误差最小化进行模型求解的方法称为“最小二乘法”（least square method）。
最小二乘法是一种完全数学描述的方法，用矩阵表示 $\scriptstyle J(\theta)=\frac{1}{2}(X\theta-Y)^2$ ，展开并对其求偏导，令偏导 $\scriptstyle \frac{\partial} {\partial\theta}J(\theta)=0$ 即可得到所求的 $\scriptstyle \theta$
$\theta=(X^TX)^{-1}X^TY$
然而现实任务中当特征数量大于样本数时， $\scriptstyle X^TX$ 不满秩，此时 $\scriptstyle \theta$ 有多个解；而且当数据量大时，求矩阵的逆非常耗时；对于不可逆矩阵（特征之间不相互独立），这种正规方程方法是不能用的。所以，还可以采用梯度下降法，利用迭代的方式求解 $\scriptstyle θ$ 。

1.3 梯度下降法

梯度下降法是按下面的流程进行的：

1）首先对 $\scriptstyle \theta$ 赋值，这个值可以是随机的，也可以让 $\scriptstyle \theta$ 是一个全零的向量。

2）改变 $\scriptstyle \theta$ 的值，使得 $\scriptstyle \theta$ 按梯度下降的方向进行减少。

对于只有二维属性的样本， $\scriptstyle J(\theta)$ 即 $\scriptstyle J(\theta_0,\theta_1)$ 的等高线图

利用梯度下降法，逐步最小化损失函数，找准梯度下降方向，即偏导数的反方向，每次前进一小步，直到收敛

方法：
(1)先确定向下一步的步伐大小，我们称为Learning rate；
(2)任意给定一个初始值 $\scriptstyle \theta_0,\theta_1$ ：
(3)确定一个向下的方向，并向下走预先规定的步伐，并更新 $\scriptstyle \theta_0,\theta_1$ ；
(4)当下降的高度小于某个定义的值，则停止下降；
$\theta_j:=\theta-\alpha\frac{\partial}{\partial\theta_j}J(\theta)=\theta_j-\alpha\frac{1}{m}\sum_{i-1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}$
特点：
(1)初始点不同，获得的最小值也不同，因此梯度下降求得的只是局部最小值；
(2)越接近最小值时，下降速度越慢；

如果取到一个正确的 $\scriptstyle \alpha$ 值，则 $\scriptstyle Cost Function$ 应该越来越小；
问题：怎么取 $\scriptstyle \alpha$ 值？
答：随时观察 $\scriptstyle \alpha$ 值，如果 $\scriptstyle Cost Function$ 变小了，则ok，反之，则再取一个更小的值；

下图就详细的说明了梯度下降的过程：

从上面的图可以看出：初始点不同，获得的最小值也不同，因此梯度下降求得的只是局部最小值；
注意：下降的步伐大小非常重要，因为如果太小，则找到函数最小值的速度就很慢，如果太大，则可能会出现overshoot the minimum的现象；

下图就是overshoot minimum现象：

image.png

如果Learning rate取值后发现 $\scriptstyle J function$ 增长了，则需要减小Learning rate的值

迭代更新的方式有多种

批量梯度下降（batch gradient descent），也就是是梯度下降法最原始的形式，对全部的训练数据求得误差后再对 $\scriptstyle \theta$ 进行更新，优点是每步都趋向全局最优解；缺点是对于大量数据，由于每步要计算整体数据，训练过程慢；

随机梯度下降（stochastic gradient descent），每一步随机选择一个样本对 $\scriptstyle \theta$ 进行更新，优点是训练速度快；缺点是每次的前进方向不好确定，容易陷入局部最优；

微型批量梯度下降（mini-batch gradient descent），每步选择一小批数据进行批量梯度下降更新 $\scriptstyle \theta$ ，属于批量梯度下降和随机梯度下降的一种折中，非常适合并行处理。

2.逻辑回归（Logistic Regression）

逻辑回归由于存在易于实现、解释性好以及容易扩展等优点，被广泛应用于点击率预估（CTR）、计算广告（CA）以及推荐系统（RS）等任务中。逻辑回归虽然名字叫做回归，但实际上却是一种分类学习方法。
线性回归完成的是回归拟合任务，而对于分类任务，我们同样需要一条线，但不是去拟合每个数据点，而是把不同类别的样本区分开来。

2.1 预测函数

对于二分类问题， $\scriptstyle y\in\{0,1\}$ ,1表示正例，0表示负例。逻辑回归是线性函数 $\scriptstyle \theta^Tx$ 输出预测实际值的基础上，寻找一个假设函数，函数 $\scriptstyle h_\theta(x)=g(\theta^Tx)$ ，将实际值映射到0,1之间，如果 $\scriptstyle h_\theta(x)\geqq0.5$ ，则预测 $\scriptstyle y=1$ ，及 $\scriptstyle y$ 属于正例；如果 $\scriptstyle h_\theta(x)<0.5$ ，则预测 $\scriptstyle y=0$ ，即 $\scriptstyle y=0$ ，即 $\scriptstyle y$ 属于负例。

逻辑回归中选择对数几率函数（logistic function）作为激活函数，对数几率函数是Sigmoid函数（形状为S的函数）的重要代表
$g(z)=\frac{1} {1+e^{-z}}$

Sigmoid函数

则逻辑回归输出的预测函数数学表达式为
$h_\theta(x)=g(\theta^Tx)=\frac{1}{1+e^{-\theta^Tx}}$
其中 $\scriptstyle \theta$ 是参数向量。对于 $\scriptstyle h_\theta(x)$ 的直观解释是：对于给定的输入 $\scriptstyle x$ ， $\scriptstyle h_\theta(x)$ 表示其对应类标 $\scriptstyle y=1$ 即属于正例的概率。

问：为什么逻辑回归又叫对数几率回归？
答：上式可以变化为
$ln\frac{h_\theta(x)}{1-h_\theta(x)}=\theta^Tx$
$\scriptstyle h_\theta(x)$ 是 $\scriptstyle x$ 属于正例得概率， $\scriptstyle 1-h_\theta(x)$ 是 $\scriptstyle x$ 属于反例的概率俩者比值 $\scriptstyle \frac{h_\theta(x)} {1-h_\theta(x)}$ 叫做几率（odds），表示了 $\scriptstyle x$ 作为正例的相对可能性。取对数就叫做对数几率（log odds，或logit） $\scriptstyle ln\frac{h_\theta(x)}{1-h_\theta(x)}$

如果说线性回归是对于特征的线性组合来拟合真实标记的话 $\scriptstyle (y=wx+b)$ ，逻辑回归是对于特征的线性组合来拟合真实标记为正例的概率的对数几率 $\scriptstyle (ln\frac{y}{1-y}=wx+b)$
对于输入 $\scriptstyle x$ 分类结果为类别1和类别0的概率分别为：
$P(y=1|x;\theta)=h_\theta(x)\\P(y=0|x;\theta)=1-h_\theta(x)$
例如，如果对于给定的 $\scriptstyle x$ ，通过已经确定的参数计算得出 $\scriptstyle h_\theta(x)=0.7$ ，则表示有 $\scriptstyle 70\%$ 的几率 $\scriptstyle y$ 为正例，相应的 $\scriptstyle y$ 为负例的几率为 $\scriptstyle 0.3$

2.2 决策面

在逻辑回归中，我们预测：

当 $\scriptstyle h_\theta$ 大于等于0.5时，预测 $\scriptstyle y=1$ ；

当 $\scriptstyle h_\theta$ 小于0.5时，预测 $\scriptstyle y=0$ 。
根据上面绘制出的S形函数图像，我们知道：

$\scriptstyle z=0$ 时 $\scriptstyle g(z)=0.5$ ，

$\scriptstyle z>0$ 时 $\scriptstyle g(z)>0.5$ ，

$\scriptstyle z<0$ 时 $\scriptstyle g(z)<0.5$ 。
又 $\scriptstyle z=\theta^Tx$ ，所以

$\scriptstyle \theta^Tx$ 大于等于0时，预测 $\scriptstyle y=1$ ；

$\scriptstyle \theta^Tx$ 小于0时，预测 $\scriptstyle y=0$ 。

假设我们有一个模型： $\scriptstyle h_\theta(x)=g(\theta_0+\theta_1x_1+\theta_2x_2)$ 并且参数 $\scriptstyle \theta$ 是向量[-3 1 1]。则当 $\scriptstyle -3+x_1+x_2$ 大于等于0，即 $\scriptstyle x_1+x_2$ 大于3时，模型将预测 $\scriptstyle y=1$ 。绘制直线 $\scriptstyle x_1+x_2=3$ ，便是我们模型的分界线，将预测为1的区域和预测为0的区域分隔开。

2.3 损失函数

如何求分类任务的最优解呢？第一个直接的想法是仍然沿用上述的均方误差来表示真实样本与预测值之间的差距 $J(\theta)=\frac{1}{2m}\sum_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})^2=\frac{1}{2m}\sum_{i=1}^{m}(\frac{1}{1+e^{-\theta ^Tx^{(i)}-b}}-y^{(i)})^2$
但这个函数不是凸函数，很难进行优化。

于是我们接着转换思路，既然是分类任务，那么我们可以对于每个类别分别取计算它们各自的损失呀。对于真实标记是1的样本，我们希望预测值越接近于1，损失越小；对于真实标记是0的样本，我们希望预测值越接近于0时损失越小，-log函数正好满足以上情况

image.png

用交叉熵损失 $\scriptstyle Cost$ 函数来衡量 $\scriptstyle h_\theta(x)$ 函数预测：
$Cost(h_\theta(x),y)=\begin{cases}-log(h_\theta(x))， &&if&y=1\\ -log(1-h_\theta(x)),&&if&y=0\end{cases}$

问：为什么定义这样的损失函数？
答：实际上 $\scriptstyle J(θ)$ 是通过极大似然估计推导得到的
由于 $\scriptstyle y$ 只能取0或1，服从伯努利分布， $\scriptstyle h_\theta(x)$ 是 $\scriptstyle y=1$ 即事件发生概率，则概率质量函数为
$p(y|x;\theta)=(h_\theta(x)^y)(1-h_\theta(x))^{1-y}$
对于 $\scriptstyle m$ 个独立同分布的训练本 $\scriptstyle x$ ，其似然函数写作
$L(\theta)=\prod_{i=1}^mp(y|x;\theta)=\prod_{i=1}^mh_\theta(x_i)^{y_i}(1-h_\theta(x_i))^{1-y_i}$
为了方便操作，取对数，则对数似然函数为
$l(\theta)=logL(\theta)=\sum_{i=1}^my_ilogh_\theta(x_i)+(1-y_i)log(1-h_\theta(x_i))$
根据“最大似然估计”，求 $\scriptstyle l(\theta)$ 取最大值是的 $\scriptstyle \theta$ ，定义损失函数 $\scriptstyle J(\theta)$ 为
$J(\theta)=-\frac{1}{m}l(\theta)$
所以最后目标变成取 $\scriptstyle J(\theta)$ 最小值时的 $\scriptstyle \theta$ 为最佳参数。与线性回归类似，利用梯度下降法更新 $\scriptstyle \theta$
$\theta_j:=\theta_j-\alpha\frac{\partial}{\partial_{\theta_j}}J(\theta)=\theta_j-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)}-y^{i})x_j^{(i)})$
$\begin{aligned} \frac{\partial}{\partial \theta_{j}} J(\theta) &=-\frac{1}{m} \sum_{i=1}^{m}\left(y^{(i)} \frac{1}{h_{\theta}\left(\mathrm{x}^{(1)}\right)} \frac{\partial}{\partial \theta_{j}} h_{\theta}\left(\mathrm{x}^{(i)}\right)-\left(1-y^{(i)}\right) \frac{1}{1-h_{\theta}\left(\mathrm{x}^{(1)}\right)} \frac{\partial}{\partial \theta_{j}} h_{\theta}\left(\mathrm{x}^{(i)}\right)\right) \\ &=-\frac{1}{m} \sum_{i=1}^{m}\left(y^{(i)} \frac{1}{g\left(\theta^{T} x^{(0)}\right)}-\left(1-y^{(i)}\right) \frac{1}{1-g\left(\theta^{T} x^{(i)}\right)}\right) \frac{\partial}{\partial \theta_{j}} g\left(\theta^{T} x^{(i)}\right) \\ &=-\frac{1}{m} \sum_{i=1}^{m}\left(y^{(i)} \frac{1}{g\left(\theta^{T} x^{(0)}\right)}-\left(1-y^{(i)}\right) \frac{1}{1-g\left(\theta^{T} x^{(0)}\right)}\right) g\left(\theta^{T} x^{(i)}\right)\left(1-g\left(\theta^{T} x^{(i)}\right)\right) \frac{\partial}{\partial \theta_{j}} \theta^{T} x^{(i)} \\ &=-\frac{1}{m} \sum_{i=1}^{m}\left(y^{(i)}\left(1-g\left(\theta^{T} x^{(i)}\right)\right)-\left(1-y^{(i)}\right) g\left(\theta^{T} x^{(i)}\right)\right) x_{j}^{(0)} \\ &=-\frac{1}{m} \sum_{i=1}^{m}\left(y^{i}-g\left(\theta^{T} x^{(0)}\right)\right) x_{j}^{(0)} \\ &=-\frac{1}{m} \sum_{i=1}^{m}\left(y^{(i)}-h_{\theta}\left(\mathrm{x}^{(i)}\right)\right) x_{j}^{(0)} \\ &=\frac{1}{m} \sum_{i=1}^{m}\left(h_{\theta}\left(\mathrm{x}^{(i)}\right)-y^{(i)}\right) x_{j}^{(i)} \end{aligned}$

虽然逻辑回归得到的梯度下降更新迭代公式与线性回归的梯度下降算法一样，但是这里的 $\scriptstyle h_\theta(x)=g(\theta^Tx)$ 与线性回归不同，所以实际上是不一样的。除了梯度下降法，还有其他的一些用来求代价函数最小时参数 $\scriptstyle\theta$ 的方法，如牛顿法、共轭梯度法Conjugate Gradietn）、局部优化法（BFGS）和有限内存局部优化法（LBFGS）等。

3.正则化（Regularization）

3.1 欠拟合和过拟合

以线性回归预测房价为例

欠拟合（unerfitting），高偏差（bias），没有很好地拟合训练数据，存在较大偏差，不是一个好模型；
过拟合（overfitting），高方差（variance），对训练数据拟合过于好，泛化性能差，上下波动厉害，也不是一个好模型。
上述情况对于LR也存在

过拟合问题通常发生在变量（特征）过多的时候。这种情况下训练出的方程总是能很好的拟合训练数据，也就是说，我们的代价函数可能非常接近于0或者就为0，使其拟合只局限于训练样本中，无法很好预测其他新的样本。

解决过拟合问题的方法主要有两种：
1.减少特征数量，通过人工或者算法选择哪些特征有用保留，哪些特征没用删除，但会丢失信息。
2.正则化，保留特征，但减少特征对应参数的大小，让每个特征都对预测产生一点影响。

假设我们在损失函数上加上一些项，对 $\scriptstyle \theta_3$ 和 $\scriptstyle \theta_4$ 进行惩罚，变成
$\min _{\theta} \frac{1}{2 m} \sum_{i=1}^{m}\left(h_{\theta}\left(x^{(i)}\right)-y^{(i)}\right)^{2}+1000 \theta_{3}^{2}+1000 \theta_{4}^{2}$

这样求出的 $\scriptstyle θ_3$ 和 $\scriptstyle θ_4$ 就会非常小，接近0，得到一个近似的二次函数。
一般来说，正规化背后的思路就是，如果我们的参数值对应一个较小值的话（参数值比较小），那么往往我们会得到一个形式更简单的假设。但更一般地说，如果我们像惩 $\scriptstyle θ_3$ 和 $\scriptstyle θ_4$ 这样惩罚其它参数，那么我们往往可以得到一个相对较为简单的假设。
实际上，这些参数的值越小，通常对应于越光滑的函数，也就是更加简单的函数。因此就不易发生过拟合的问题。
假如我们有非常多的特征，我们并不知道其中哪些特征我们要惩罚，我们将对所有的特征进行惩罚，并且让代价函数最优化算法来选择这些惩罚的程度。我们需要修改代价函数，在后面添加一个正则项，收缩每个参数。

3.2 正则化线性回归

对于正则化线性回归，损失函数变成
$J(\theta)=\frac{1}{2 m}\left[\sum_{i=1}^{m}\left(h_{\theta}\left(x^{(i)}\right)-y^{(i)}\right)^{2}+\lambda \sum_{j=1}^{n} \theta_{j}^{2}\right]$
注：根据惯例，不对 $\scriptstyle θ$ 进行惩罚。
其中 $\scriptstyle \lambda$ 叫做正则化参数，用于平衡拟合训练数据和保持参数值较小避免过拟合之间的关系。
如果 $\scriptstyle \lambda$ 过大，则用梯度下降法迭代求 $\scriptstyle θ$ ，由于不对 $\scriptstyle \theta_0$ 进行惩罚，所以重复梯度下降算法计算直到收敛：

$\theta_{j}:=\theta_{j}\left(1-\alpha \frac{\lambda}{m}\right)-\alpha \frac{1}{m} \sum_{i=1}^{m}\left(\left(h_{\theta}\left(x^{(i)}\right)-y^{(i)}\right) x_{j}^{(i)}\right.$

3.3 正则化逻辑回归

对于逻辑回归损失函数加入正则项得：
$J(\theta)=-\frac{1}{m} \sum_{i=1}^{m}\left[y^{(i)} \log h_{\theta}\left(x^{(i)}\right)+\left(1-y^{(i)}\right) \log \left(1-h_{\theta}\left(x^{(i)}\right)\right)\right]+\frac{\lambda}{2 m} \sum_{j=1}^{n} \theta_{j}^{2}$
通过求导用梯度下降法更新 $\scriptstyle θ$
形式跟正则化线性回归一样，但其中 $\scriptstyle h_\theta(x)=g(\theta^Tx)$ ，所以与正则化线性回归不同。

3.4 多类分类

LR是一个传统的二分类模型，它也可以用于多分类任务，其基本思想是：将多分类任务拆分成若干个二分类任务，然后对每个二分类任务训练一个模型，最后将多个模型的结果进行集成以获得最终的分类结果。一般来说，可以采取的拆分策略有：

one vs one策略
假设我们有N个类别，该策略基本思想就是不同类别两两之间训练一个分类器，这时我们一共会训练出 $\scriptstyle C_{N}^2$ 种不同的分类器。在预测时，我们将样本提交给所有的分类器，一共会获得N(N−1)个结果，最终结果通过投票产生。
one vs all策略
该策略基本思想就是将第iii种类型的所有样本作为正例，将剩下的所有样本作为负例，进行训练得到一个分类器。这样我们就一共可以得到N个分类器。在预测时，我们将样本提交给所有的分类器，一共会获得N个结果，我们选择其中概率值最大的那个作为最终分类结果。

3.5 LR特点以及适用场景

LR实现简单高效易解释，计算速度快，易并行，在大规模数据情况下非常适用，更适合于应对数值型和标称型数据，主要适合解决线性可分的问题，但容易欠拟合，大多数情况下需要手动进行特征工程，构建组合特征，分类精度不高。

LR直接对分类可能性进行建模，无需事先假设数据分布，这样就避免了假设分布不准确所带来的问题。
LR能以概率的形式输出，而非知识0，1判定，对许多利用概率辅助决策的任务很有用。
对率函数任意阶可导，具有很好的数学性质，许多现有的数值优化算法都可以用来求最优解，训练速度快

适用情景：LR是很多分类算法的基础组件，它的好处是输出值自然地落在0到1之间，并且有概率意义。因为它本质上是一个线性的分类器，所以处理不好特征之间相关的情况。虽然效果一般，却胜在模型清晰，背后的概率学经得住推敲。它拟合出来的参数就代表了每一个特征(feature)对结果的影响。也是一个理解数据的好工具。

应用上：
CTR预估，推荐系统的learning to rank，各种分类场景
某搜索引擎厂的广告CTR预估基线版是LR
某电商搜索排序基线版是LR
某新闻app排序基线版是LR
大规模工业实时数据，需要可解释性的金融数据，需要快速部署低耗时数据
LR就是简单，可解释，速度快，消耗资源少，分布式性能好

ADMM-LR:用ADMM求解LogisticRegression的优化方法称作ADMM_LR。ADMM算法是一种求解约束问题的最优化方法，它适用广泛。相比于SGD，ADMM在精度要求不高的情况下，在少数迭代轮数时就达到一个合理的精度，但是收敛到很精确的解则需要很多次迭代。

4.感知机

4.1 感知机简述

感知机（perceptron）是二分类的线性分类模型，属于监督学习算法。输入为实例的特征向量，输出为实例的类别（取+1和-1）。感知机旨在求出将输入空间中的实例划分为两类的分离超平面。为求得超平面，感知机导入了基于误分类的损失函数，利用梯度下降法对损失函数进行最优化求解。
如果训练数据集是线性可分的，则感知机一定能求得分离超平面。如果是非线性可分的数据，则无法获得超平面。

线性可分数据集

线性不可分数据集

感知机具有简单而易于实现的优点，分为原始形式和对偶形式。对偶形式中训练实例仅以内积的形式出现，所以速度要比原始形式要忧。感知机预测是用学习得到的感知机模型对新的实例进行预测的，因此属于判别模型。感知机是神经网络和支持向量机的基础。

4.2 感知机模型

感知机从输入空间到输出空间的模型如下：
$\begin{aligned} &f(x)=\operatorname{sign}(w \cdot x+b)\\ &\operatorname{sign}(x)=\left\{\begin{array}{ll} -1 & x<0 \\ 1 & x \geq 0 \end{array}\right. \end{aligned}$

4.3 感知机的损失函数

我们首先定义对于样本 $\scriptstyle (x_i,y_i)$ ，如果 $\scriptstyle \frac{w \cdot x_{i}+b}{\|w\|}>0$ ，则记为 $\scriptstyle y_i=+1$ ，如果 $\scriptstyle \frac{w \cdot x_{i}+b}{\|w\|}<0$ ，则记为 $\scriptstyle y_i=-1$ 。
这样取 $\scriptstyle y$ 的值有一个好处，就是方便定义损失函数。因为正确分类的样本满足 $\scriptstyle \frac{w \cdot x_{i}+b}{\|w\|}>0$ ，而错误分类的样本满足 $\scriptstyle \frac{w \cdot x_{i}+b}{\|w\|}<0$ 。我们损失函数的优化目标，就是期望使误分类的所有样本，到超平面的距离之和最小。
所以损失函数定义如下：
$L(w, b)=-\frac{1}{\|w\|} \sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right)$
其中 $\scriptstyle M$ 集合是误分类点的集合。
不考虑 $\scriptstyle \frac{1}{||w||}$ ，就得到感知机模型的损失函数：
$L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right)$

感知机学习算法是对上述损失函数进行极小化，求得 $w$ 和 $b$ 。但是用普通的基于所有样本的梯度和的均值的批量梯度下降法（BGD）是行不通的，原因在于我们的损失函数里面有限定，只有误分类的M集合里面的样本才能参与损失函数的优化。所以我们不能用最普通的批量梯度下降,只能采用随机梯度下降（SGD）

4.4 训练过程

我们大概从下图看下感知机的训练过程。

线性可分的过程：

线性可分

线性可分的过程：

线性不可分

5.支持向量机（SVM）

5.1 什么是SVM？

SVM（Support Vector Machine）是一种可监督的机器学习算法，可用于分类或回归问题。它使用一种称为核技巧的技术来转换数据，然后根据这些转换在可能的输出之间找到最佳边界。简而言之，它进行了一些极其复杂的数据转换，然后指出了如何根据您定义的标签或输出来分离数据。支持向量机算法的目标是在N维空间（N —特征数）中找到一个具有最大间隔的超平面，即两个类别的数据点之间的最大距离，该超平面对数据点进行明显分类。

Possible hyperplanes

5.2 为什么SVM受欢迎？

它能够进行分类和回归。SVM可以处理线性和非线性问题，非线性SVM意味着算法计算的边界不必是直线。好处是我们可以捕获数据点之间更复杂的关系，而不必自己执行困难的转换。缺点是训练时间更长，因为它的计算量更大。
如下图：通过使用几种不同类型的分类器，我们发现SVM在将牛与狼群分开方面做得很好。我认为这些图也很好地说明了使用非线性分类器的好处。我们可以看到逻辑模型和决策树模型都仅使用直线。

5.3 SVM结构

支持向量（Support Vector） -最接近超平面的数据点称为支持向量。将在这些数据点的帮助下定义分隔线。

超平面（Hyperplane） -如下图所示，它是一个决策平面或空间，该平面或空间把数据集划分成不同的类别。

间隔（Margin） -可以定义为不同类别里最近的数据点上两条线之间的间隙。可以将其计算为从线到支持向量的垂直距离。大间隔被认为是好间隔，小间隔被认为是不好的间隔。

函数间隔：是人为定义的一个间隔度量
几何间隔：才是直观上的点到超平面的距离。
几何间隔就是函数间隔除以||w||,其中||w||为w的二阶范数（范数是一个类似于模的表示长度的概念）

SVM示意图

从上面我们得知：SVM的主要目标是将数据集划分为类以找到最大间隔超平面（maximum marginal hyperplane -MMH)，可以通过以下两个步骤完成:

首先，SVM将迭代多次生成超平面，以最佳方式隔离分类。

然后，它将选择能正确分隔类的超平面。

5.4 SVM 核函数（Kernel）

核函数：通过两个向量点积来度量向量间相似度的函数
使用核技巧的原因：通过使用核技巧，我们可以在原始特征空间中计算两个高维特征空间中向量的相似度。

线性核函数（Linear Kernel）
它可以用作任意两个观测值之间的点积。线性核的公式如下
$K\left(x, x_{i}\right)=\operatorname{sum}\left(x * x_{i}\right)$
从上面的公式，我们可以看到两个向量之间的乘积𝑥和𝑥𝑖是每对输入值的乘积之和。

多项式核函数（Polynomial Kernel）
它是线性核的更广义形式，可以区分弯曲或非线性输入空间。以下是多项式内核的公式
$k(X, X i)=1+\operatorname{sum}\left(X * X_{i}\right) \cdot d$
这里d是多项式的阶数，我们需要在学习算法中手动指定它

径向基函数（Radial Basis Function-RBF）核函数--（高斯核函数）
RBF内核（主要用于SVM分类）将输入空间映射到不确定的维空间中。以下公式在数学上对其进行了解释
$\mathrm{k}\left(x^{(i)}, x^{(j)}\right)=\exp \left(-\gamma\left\|x^{(i)}-x^{(j)}\right\|^{2}\right)$
此处， $\gamma$ 的范围是0到1。我们需要在学习算法中手动指定它。好的 $\gamma$ 默认值为0.1。
在为线性可分离数据可用SVM，我们可以在Python中为不可线性分离的数据实现SVM，就可以通过使用核函数来完成。

提问：为什么要用核函数呢？
回答：从输入空间到某个特征空间的映射，这意味着建立非线性学习器分为两步：
1.首先使用一个非线性映射将数据变换到一个特征空间，
2.然后在特征空间使用线性学习器分类。
简单来讲：拿到非线性数据，就找一个映射，然后一股脑把原来的数据映射到新空间中，再做线性 SVM 即可。不过事实上好像并没有这么简单。
思索之后：如果遇到多维数据，出现维度爆炸，那么计算就非常困难了。这个时候，可能就需要核函数出马了

5.5 使用松弛变量处理 outliers 方法

当处理数据是线性可分的时候，我们可以找到一个可行的超平面将数据完全分开。后来为了处理非线性数据，使用 Kernel 方法对原来的线性 SVM 进行了推广，使得非线性的的情况也能处理。虽然通过映射将原始数据映射到高维空间之后，能够线性分隔的概率大大增加，但是对于某些情况还是很难处理。

例如可能并不是因为数据本身是非线性结构的，而只是因为数据有噪音。对于这种偏离正常位置很远的数据点，我们称之为 outlier ，在我们原来的 SVM 模型里，outlier 的存在有可能造成很大的影响，因为超平面本身就是只有少数几个 support vector 组成的，如果这些 support vector 里又存在 outlier 的话，其影响就很大了。例如下图：

image.png

用黑圈圈起来的那个蓝点是一个 outlier ，它偏离了自己原本所应该在的那个半空间，如果直接忽略掉它的话，原来的分隔超平面还是挺好的，但是由于这个 outlier 的出现，导致分隔超平面不得不被挤歪了，变成途中黑色虚线所示（这只是一个示意图，并没有严格计算精确坐标），同时 margin 也相应变小了。当然，更严重的情况是，如果这个 outlier 再往右上移动一些距离的话，我们将无法构造出能将数据分开的超平面来。

为了处理这种情况，SVM 允许数据点在一定程度上偏离一下超平面。例如上图中，黑色实线所对应的距离，就是该 outlier 偏离的距离，如果把它移动回来，就刚好落在原来的超平面蓝色间隔边界上，而不会使得超平面发生变形了。

换言之，在有松弛的情况下outline点也属于支持向量SV，同时，对于不同的支持向量，拉格朗日参数的值也不同，如此篇论文《Large Scale Machine Learning》中的下图所示：

对于远离分类平面的点值为0；对于边缘上的点值在[0, 1/L]之间，其中，L为训练数据集个数，即数据集大小；对于outline数据和内部的数据值为1/L

6.小结

6.1 逻辑回归和感知机的异同

两类都是线性分类器；
损失函数两者不同：逻辑回归使用极大似然（对数损失函数），感知机使用的是均方损失函数（即错误点到分离平面的距离，最小化这个值）
逻辑回归比感知机的优点在于对于激活函数的改进。
前者为sigmoid function，后者为阶跃函数。这就导致LR是连续可导，而阶跃函数则没有这个性质。
LR使得最终结果有了概率解释的能力（将结果限制在0-1之间），sigmoid为平滑函数，能够得到更好的分类结果，而step function为分段函数，对于分类的结果处理比较粗糙，非0即1，而不是返回一个分类的概率。

6.2 感知机和SVM的区别

相同点
都是属于监督学习的一种分类器（决策函数）。
不同点
感知机追求最大程度正确划分，最小化错误，很容易造成过拟合。
支持向量机追求大致正确分类的同时，一定程度上避免过拟合。
感知机使用的学习策略是梯度下降法，而SVM采用的是由约束条件构造拉格朗日函数，然后求偏导令其为0求得极值点。这里特别说明下一般我们的拉格朗日函数是符合凸函数的，因此对于凸函数一定存在极值点，也是唯一的最优解。而一般的非凸函数，只好采用梯度下降法一步一步的求得极值点，如果非凸函数还是采用求导令为0，可能找不到极值点！因为鞍点也是导数为，但却不是极值点的特例，如y = x^3函数。导数为0是函数极值点的必要条件。

6.3 逻辑回归与SVM的区别

它们的区别就在于逻辑回归采用的是 log loss（对数损失函数），svm采用的是hinge loss

其实，这两个损失函数的目的都是增加对分类影响较大的数据点的权重，减少与分类关系较小的数据点的权重。SVM的处理方法是只考虑 support vectors，也就是和分类最相关的少数点，去学习分类器。而逻辑回归通过非线性映射，大大减小了离分类平面较远的点的权重，相对提升了与分类最相关的数据点的权重,两者的根本目的都是一样的。

svm考虑局部（支持向量），而logistic回归考虑全局，就像大学里的辅导员和教师间的区别

辅导员关心的是挂科边缘的人，常常找他们谈话，告诫他们一定得好好学习，不要浪费大好青春，挂科了会拿不到毕业证、学位证等等，相反，对于那些相对优秀或者良好的学生，他们却很少去问，因为辅导员相信他们一定会按部就班的做好分内的事；而大学里的教师却不是这样的，他们关心的是班里的整体情况，大家是不是基本都理解了，平均分怎么样，至于某个人的分数是59还是61，他们倒不是很在意。

逻辑回归和SVM都可以用于分类问题的解决，其主要区别就在于映射函数选择上的不同，逻辑回归常用于处理大数据，而SVM则正好相反。

参考链接：

支持向量机通俗导论（理解SVM的三层境界）
逻辑回归（Logistic Regression, LR）简介
 机器学习入门：线性回归及梯度下降
 感知机原理
 【机器学习】感知机原理详解
 What is a Support Vector Machine, and Why Would I Use it?
Support Vector Machine — Introduction to Machine Learning Algorithms
ML - Support Vector Machine(SVM)
【机器学习】数据降维—核主成分分析(Kernel PCA)
逻辑回归感知机异同，损失函数思考
 感知机和SVM的区别
 Machine learning: lecture 7
Logistic Regression and SVM
逻辑回归和SVM的区别是什么？各适用于解决什么问题？

最后编辑于：2020.09.14 16:55:22

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,294评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,493评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,790评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,595评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,718评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,906评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,053评论 3赞 410
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,797评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,250评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,570评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,711评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,388评论 4赞 332
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,018评论 3赞 316
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,796评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,023评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,461评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,595评论 2赞 350