逻辑回归可以用于二类或多类分类，它是源自逻辑斯谛分布，使用极大似然估计法估计模型参数。支持向量机是一种二类分类模型。
逻辑回归
首先，逻辑回归模型的分布函数是S型曲线（sigmoid函数）：
$$h_w(x)=g(w^Tx)=\frac{1}{1+e^{-w^Tx}}$$即：
$$g(z)=\frac{1}{1+e^{-z}}$$
![S函数曲线][1]
逻辑回归模型
假定条件概率分布：
$$P(Y=1|x)=h_w(x) \\
P(Y=0|x)=1-h_w(x)$$
模型参数估计：
使用极大似然估计法估计模型参数，则似然函数为：
$$\prod_{i=1}^N[h_w(x_i)]^{y_i}[1-h_w(x_i)]^{1-y_i}$$
对数似然函数为
$$
L(w)=\sum_{i=1}^N[{y_i}logh_w(x_i)+(1-y_i)log(1-h_w(x_i))] \\
=\sum_{i=1}^N[y_ilog\frac{h_w(x_i)}{(1-h_w(x_i))}+log((1-h_w(x_i)))] \\
=\sum_{i=1}^N[y_i(w^Tx_i)-log(1+e^{w^Tx_i})]
$$
对L（w）求极大值，得到w的估计值：
$$
\frac{\partial L(w)}{\partial w_i}=\sum_{i=1}^N (y_ix_i-h_w(x_i)x_i)
$$
学习中通常采用梯度下降法以及拟牛顿法。
则最后求得逻辑回归模型：
$$
y_i=\begin{cases}
h_w(x_i), y_i=1\\
1-h_w(x_i), y_i=0
\end{cases}
$$
多分类逻辑回归
对于多分类来说，将逻辑回归模型推广到多项逻辑回归模型
$$P(Y=k|x)=\frac{e^{w_k^Tx}}{1+\sum_{k=1}^{K-1} e^{w_k^Tx}}, k=1,2,…,K-1 \\
P(Y=K|x)=\frac{1}{1+\sum_{k=1}^{K-1}e^{w_k^Tx}}
$$
支持向量机
支持向量机基础是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机。此外，它还包括核方法，这使得它成为非线性分类器。它的学习算法是求解凸二次规划的最优化算法。
- 线性可分支持向量机：训练数据集是线性可分的，通过硬间隔最大化，学习线性分类器；
- 线性支持向量机：训练数据集是线性近似可分的，通过软间隔最大化，学习线性分类器；
- 非线性支持向量机：训练数据集是非线性可分的，通过核技巧和软间隔最大化，学习非线性分类器。
输入都由输入空间转换到特征空间，支持向量机的学习是在特征空间进行的。
注：当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开。感知机利用误分类最小的策略，求得分离超平面，不过这时的解有无穷多个。线性可分支持向量机利用间隔最大化求最优分离超平面，解是唯一的。
线性可分支持向量机
函数间隔
一个点距离分离超平面的远近表示分类的确信度。$w^Tx+b$的符号与类y的符号是否一致表示分类的正确性，所以函数间隔来表示两者,超平面对一个样本点来说的函数间隔：
$$\hat\gamma_i=y_i(w^Tx_i+b)$$
只有函数间隔选择分离超平面不够，因为当$w,b$成倍增加时，函数间隔也成倍增加，超平面虽然没有变，但是点到面距离大了，所以要引入几何间隔（对$w$加上某些约束）。
几何间隔
也就是函数间隔除以$||w||$,即：
$$\gamma_i=y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||})$$
所以当$||w||=1$时，函数间隔等于几何间隔，当$w,b$成倍增加时（超平面没改变），函数间隔改变了，但几何间隔没改变。
间隔最大化
约束最优化问题：
$$\max_{w,b} \frac{\hat\gamma}{||w||} \\
s.t. y_i(w \cdot x_i+b)\geq \hat\gamma, i=1,2,…,N
$$
表示样本点的几何间隔至少为$\hat\gamma/||w||$。函数间隔的取值并不影响最优化问题的解，函数间隔的改变对上面的最优化问题不等式约束没有影响，对目标函数优化也没有影响，所以取$\hat\gamma=1$，等价的最小化问题(凸二次规划问题)：
$$\min_{w,b} \frac{1}{2}||w||^2\\
s.t. y_i(w \cdot x_i+b)-1 \geq 0, i=1,2,…,N
$$
支持向量和间隔边界
支持向量在超平面上，也就是间隔边界上，两个间隔边界的距离等于$2/||w||$,在决定分离超平面时只有支持向量起作用，而其他实例点不起作用。由于支持向量（重要的训练样本点）在确定分离超平面时起决定性作用，所以称为支持向量机。
学习算法
为了求解原问题的凸二次规划问题，需要借助拉格朗日对偶性转化为对偶问题进行求解。
对偶问题优点：
- 更容易求解；
- 自然引入核函数，推广到非线性分类问题。
1、构建拉格朗日函数：
$$
L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^N \alpha_iy_i(w \cdot x_i+b)+\sum_{i=1}^N \alpha_i
$$
2、转化为对偶问题,先对$w,b$求极小，再对$\alpha$求极大：
$$\max_\alpha \min_{w,b}L(w,b,\alpha)$$
对$w,b$求极小：
$$\nabla_wL(w,b,\alpha)=w-\sum_{i=1}^N \alpha_iy_ix_i=0 \\
\nabla_bL(w,b,\alpha)=\sum_{i=1}^N\alpha_iy_i=0 \\
w=\sum_{i=1}^N\alpha_iy_ix_i \\
\sum_{i=1}^N\alpha_iy_i=0
$$
代入$L(w,b,\alpha)$：
$$L(w,b,\alpha)=\frac{1}{2}w^Tw-w^T\sum_{i=1}^N \alpha_iy_ix_i-\sum_{i=1}^N \alpha_iy_ib+\sum_{i=1}^N\alpha_i \\
=\frac{1}{2}w^T\sum_{i=1}^N \alpha_iy_ix_i-w^T\sum_{i=1}^N \alpha_iy_ix_i-\sum_{i=1}^N \alpha_iy_ib+\sum_{i=1}^N\alpha_i \\
=-\frac{1}{2}w^T\sum_{i=1}^N \alpha_iy_ix_i-\sum_{i=1}^N \alpha_iy_ib+\sum_{i=1}^N\alpha_i \\
=-\frac{1}{2}\sum_{i=1}^N\alpha_iy_ix_i^T\sum_{i=1}^N \alpha_iy_ix_i+\sum_{i=1}^N\alpha_i \\
=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_jx_i^T x_j+\sum_{i=1}^N\alpha_i
$$
3、对$\alpha$求极大，相当于对以下求极小：
$$\min_\alpha \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_jx_i^T x_j-\sum_{i=1}^N\alpha_i \\
s.t. \sum_{i=1}^N\alpha_iy_i=0 \\
\alpha_i \geq 0, i=1,2,…,N
$$
通过SMO算法求解$\alpha$，之后求出$w,b$，最后求出分离超平面和分类决策函数。
[1]: https://raw.githubusercontent.com/GaoJianchao/learngit/master/img/S.png
