支持向量机
基本思想
支持向量机的基本思想就是用一个超平面来划分一群点，达到二分类效果。寻找超平面过程中。我们使用最小化间隔的思想，使得svm具有鲁棒性。
硬间隔SVM
欲分类点记为(xi, yi)i = 1N共N个，预测结果yi取值为0，1 我们的判别模型可以表示为 f(w) = sign(wTx + b) 其中wTx + b = 0就是1划分所用的超平面，因此约束条件可以表示为 yi(wTx + b) > 0
由上图可以看到，对称地，总能找到连两个点距离超平面最近，我们的目的就是最大化这个”最小距离”，优化任务记为 $$\begin{cases}\max_{w,b}\min\frac{1}{||w||}|w^{T}x_{i}+b|\\\\s.t.\quad y_{i}(w^{T}x_{i}+b)>0\end{cases}$$ 化简为 $$\begin{cases}\max_{w,b}\min\frac{1}{||w||}y_i(w^{T}x_{i}+b)\\\\s.t.\quad y_{i}(w^{T}x_{i}+b)>0\end{cases}$$ 超平面方程为wTx + b = 0,可以任意缩放倍数，因此不妨规定min yi(wTx + b) = 1 原问题化为 $$\begin{cases}min\, \frac{1}{2}w^Tw\\\\s.t.\quad y_{i}(w^{T}x_{i}+b)\geq1\end{cases}$$
由于其约束都是仿射的，因此符合放松的slater条件，问题变为一个纯粹的N个约束的凸优化问题。
对偶问题
但是，如果样本数量或维度非常高，直接求解困难甚至不可解，于是需要对这个问题进一步处理。引入 Lagrange 函数：
$$L(w,b,\lambda)=\frac12w^Tw+\sum_{i=1}^N\lambda_i(1-y_i(w^Tx_i+b))$$
原问题为
$$\begin{cases}min\, \frac12 w^Tw\\\\s.t.\quad 1-y_{i}(w^{T}x_{i}+b)\leq0\end{cases}$$
可以证明，原问题的等价问题为
$$\begin{cases}min_{w,b}\max_{\lambda}L(w,b,\lambda_i)\mathrm{~}\\\\\mathrm{~}\lambda_i\geq0\end{cases}$$
交换最小和最大值的符号得到对偶问题：
maxλiminw, bL(w, b, λi) s.t. λi ≥ 0
由于不等式约束是仿射函数，对偶问题和原问题等价
>引入:原问题和对偶问题满足强对偶关系的充要条件为其满足 KKT
条件：
>$$\begin{aligned}
&\frac{\partial L}{\partial w}=0,\frac{\partial L}{\partial b}=0 \\
&\large\lambda_k(1-y_k(w^Tx_k+b))=0(slackness complementary) \\
&\lambda_{i}\geq0 \\
&1-y_i(w^Tx_i+b)\leq0
\end{aligned}$$
利用KKT条件将上述优化问题变为只和λ有关的优化问题
$$\frac\partial{\partial b}L=0\Rightarrow\sum_{i=1}^N\lambda_iy_i=0$$
$$\frac\partial{\partial w}L=0\Rightarrow w=\sum_{i=1}^N\lambda_iy_ix_i$$
带入原始拉格朗日函数得到
$$L(w,b,\lambda_i)=-\frac12\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^N\lambda_i$$
问题转化为了对λ的优化问题
$$\max_\lambda\boldsymbol{-}\frac12\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^N\lambda_i,\mathrm{~}s.t.\mathrm{~}\lambda_i\geq0$$
使用优化手段求解得到λi，进而求解w, b ,
$$\hat{w}=\sum_{i=1}^N\lambda_iy_ix_i\\\hat{b}=y_k-w^Tx_k=y_k-\sum_{i=1}^N\lambda_iy_ix_i^Tx_k,\exists k,1-y_k(w^Tx_k+b)=0$$
容易看出上面的xk就是距离超平面最近的点(向量)，我们把它称之为支持向量，这也是支持向量机名字的由来。而这里也可以看出，互补松弛条件就是说只有支持向量对应的λi为0.
软间隔SVM
Hard-margin 的 SVM 只对可分数据可解，如果不可分的情况，我们的基本想法是在损失函数中加入错误分类的可能性。为此我们考虑修正想要min的函数
$$\begin{cases}min\, \frac12 w^Tw+loss \\\\s.t.\quad 1-y_{i}(w^{T}x_{i}+b)\leq0\end{cases}$$
loss应当允许错误分类同时使得错误分类最小，为了尽量保持loss可导，直观地想法是
当yi(wTxi + b) > = 1,此时为正确分类的情况，那么loss = 0
当yi(wTxi + b) < 1,此时为错误分类的情况，不妨直接取距离作为loss，也即取loss = 1 − yi(wTxi + b)
因此loss表示为
$$loss=\sum_{i=1}^N\max\{0,1-y_i(w^Tx_i+b)\}$$
求和符号中的式子又叫做 Hinge Function。
优化问题进一步修正为
$$\begin{cases}min\, \frac12w^Tw+C\sum_{i=1}^N\max\{0,1-y_i(w^Tx_i+b)\} \\\\s.t.\quad 1-y_{i}(w^{T}x_{i}+b)\leq0\end{cases}$$
这个式子中，常数C可以看作允许的错误水平，同时上式为了进一步消除 max 符号，对数据集中的每一个观测，我们可以认为其大部分满足约束，但是其 中部分违反约束，因此这部分约束变成yi(wTx + b) ≥ 1 − ξi ,其中 ξi = 1 − yi(wTxi + b) ,进一步的修正为：
$$\begin{cases}min_{w,b}\frac12w^Tw+C\sum_{i=1}^N\xi_i \\\\ s.t.\quad y_i(w^Tx_i+b)\geq1-loss_i,loss_i\geq0\end{cases}$$
对于正确分类的点，lossi = 0,约束变为yi(wTxi + b) ≥ 1 − 0
对于错误分类的点，lossi = 1 − yi(wTxi + b)，约束恒成立，相当于没有约束。
一些凸分析杂谈与核方法
latex有空再敲，太多了太多了
主要就是在讲一些十分凸分析的内容，比如
- 凸优化+slater条件是强对偶关系的充要条件
- slater条件有放松版本，就是对于仿射形式的约束条件的放松
- 从几何上可以直观感受到强弱对偶关系之间对的联系
- 从几何上可以简单的感受到KKT条件