LR & SVM

classification & regression

逻辑回归处理的是分类问题（损失是交叉墒），线性回归处理的是回归问题（损失是mse），这是两者的最本质的区别。

SVM解决的是分类问题，损失是合页损失（hinge loss）。

线性回归

$y = w x + b$ 假设因变量和自变量之间是线性关系。

最常用的是参数估计方法是最小二乘法（Least Square Method）, 最小二乘法试图找到一条直线，使得样本点和直线的欧氏距离之和最小。这个寻找的过程简单描述就是：根据凸函数的性质，求其关于$w$和$b$的二阶导的零点。

svm

hard margin

找到一个分类平面，使得两类之间完全可分。任何一个分类面都可以表示为$W^Tx+b = 0$，加一个间隔，变成了$W^Tx+b = 1$和$W^Tx+b = -1$。两个加了间隔的分类面之间的距离就叫做间隔，为$\gamma = \frac{2}{||W||}$。在满足分类正确的约束条件下，最大化这个间隔，就是svm的基本型。

\begin{aligned} &\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2} \\ &\text { s.t. } y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m \end{aligned}

soft margin

在数据线性不可分的情况下，不存在hard margin的解，此时在满足尽可能正确的解，就是soft margin。

损失用hinge loss，即max(0,1-z).即不满足约束的样本给一个损失，那么最小化间隔就变最小化间隔加上不满足约束的损失尽可能的小，如下：

\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \ell_{0 / 1}\left(y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)-1\right)

对偶问题

对偶问题指的就是用拉格朗日乘子法将SVM问题进行转换。

基本的拉格朗日乘子法主要是针对等式约束下的非线性方程最优化问题，但事实上，很多时候等式约束很难覆盖我们显示的问题，计算成本时候，通常说不能超过多少资金，不能超多多少时间，都是一个范围内，通常面对更多的是不等式条件约束的情况，面对这种情况，可以通过增加KKT条件后，通过拉格朗日乘子求解不等式约束的优化问题。

Karush-Kuhn-Tucker (KKT)条件是非线性规划(nonlinear programming)最佳解的必要条件。KKT条件将Lagrange乘数法(Lagrange multipliers)所处理涉及等式的约束优化问题推广至不等式。

考虑标准约束优化问题(或称非线性规划)：

\begin{array}{ll} \min & f(\mathbf{x}) \\ \text { s.t. } & g_{j}(\mathbf{x})=0, \quad j=1, \ldots, m \\ & h_{k}(\mathbf{x}) \leq 0, \quad k=1, \ldots, p \end{array}

定义Lagrangian 函数

L\left(\mathbf{x},\left\{\lambda_{j}\right\},\left\{\mu_{k}\right\}\right)=f(\mathbf{x})+\sum_{j=1}^{m} \lambda_{j} g_{j}(\mathbf{x})+\sum_{k=1}^{p} \mu_{k} h_{k}(\mathbf{x})

KKT条件包括

\begin{aligned} \nabla_{\mathbf{x}} L &=\mathbf{0} \\ g_{j}(\mathbf{x}) &=0, \quad j=1, \ldots, m \\ h_{k}(\mathbf{x}) & \leq 0 \\ \mu_{k} & \geq 0, \\ \mu_{k} h_{k}(\mathbf{x}) &=0, \quad k=1, \ldots, p \end{aligned}

根据KKT条件可以求解，分情况讨论得到最终结果。

为什么要将求解 SVM 的原始问题转换为其对偶问题? 一是对偶问题往往更易求解，当我们寻找约束存在时的最优点的时候，约束的存在虽然减小了需要搜寻的范围，但是却使问题变得更加复杂。为了使问题变得易于处理，我们的方法是把目标函数和约束全部融入一个新的函数，即拉格朗日函数，再通过这个函数来寻找最优点。二是可以自然引入核函数，进而推广到非线性分类问题。