【机器学习公式推导】SVM
本文旨在SVM相关公式推导
相关定义：
函数间隔
超平面和样本点 (x_i, y_i) 的函数间隔
\gamma_i = y_i (w \cdot x_i + b)
超平面关于训练数据集的函数间隔
\gamma = \min_{i=1,\dots,N} \gamma_i
几何间隔
超平面和样本点 (x_i, y_i) 的函数间隔
\gamma_i = y_i (\frac{w}{||w||} \cdot x_i + \frac{b}{||w||})
超平面关于训练数据集的函数间隔
\gamma = \min_{i=1,\dots,N} \gamma_i
支持向量
离超平面最近的点
间隔最大化
考虑如何求得几何间隔最大的分离超平面，得到如下约束最优化问题
\max_{w,b} \gamma \qquad(1.1)
s.t. \quad y_i(\frac{w}{||w||}\cdot x_i + \frac{b}{||w||}) \leq \gamma \qquad(1.2)
将几何间隔用函数间隔代替
\max_{w,b} \frac{\gamma'}{||w||}\qquad(1.3)
s.t. \quad y_i(w\cdot x_i + b) \leq \gamma' \qquad (1.4)
因为本身 \gamma' 的取值对对等式约束和优化没有影响，比如 \gamma' = \lambda \gamma' 时，取 w = \lambda w , b=\lambda b 目标函数(1.3)值未变，且约束函数满足，故不如将 \gamma' 设为1，且对\frac{1}{||w||}取最大值等价于对 \frac{1}{2} \cdot ||w||^2 取最小值，得到变换后的式子，然后约束改为对 w 的约束，使得对每个 w 的取值大于1，得到一个凸二次规划(有待学习)的问题
\min_{w, b} \frac{1}{2} \cdot ||w||^2 \qquad (1.5)
s.t. \quad y_i(w\cdot x_i + b) - 1 \geq 0 \qquad (1.6)
对最大间隔分离超平面存在唯一性的证明(暂时不写)
求解上述凸二次规划问题的对偶问题
构建拉格朗日函数，对每个不等式约束引入拉格朗日算子得到
L(w,b,\alpha) = \frac{1}{2}\cdot ||w||^2 - \sum_{i=1}^N \alpha_i y_i(w\cdot x_i + b) + \sum_{i=1}^{N}\alpha_i \quad (1.7)
因为根据对偶性，原始问题化为对偶问题，且满足KKT条件，原始问题的解等于对偶问题的解
\max_\alpha \min_{w, b} L(w, b,\alpha) \quad (1.8)
对于
开始(1.8)式求导
(1)\min_{w,b} L(w, b, \alpha)
\bigtriangledown_wL(w, b,\alpha) = w -\sum_{i=1}^N \alpha_iy_ix_i=0\\ \bigtriangledown_bL(w, b,\alpha) = - \sum_{i=1}^N\alpha_iy_i = 0
可得
w = \sum_{i=1}^N\alpha_iy_ix_i \quad (1.9)\\ \sum_{i=1}^N\alpha_iy_i = 0 \quad (1.10)
带入（1.7）可得
L(w,b,\alpha) = \frac{1}{2}\cdot \sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jx_ix_jy_iy_j-\sum_{i=1}^N\alpha_iy_i((\sum_{j=1}^N\alpha_jx_jy_j)\cdot x_i+b) + \sum_{i=1}^N\alpha_i \\ =-\frac{1}{2}\cdot \sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^N\alpha_i
得到新约束
\max_\alpha\quad-\frac{1}{2}\cdot \sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^N\alpha_i \\ s.t.\quad \sum_{i=1}^N\alpha_iy_i = 0,\alpha_i \geq0\quad (1.11)
(2)\max_{\alpha} L(w,b,\alpha)
转换（1.11）式 \min_\alpha\quad\frac{1}{2}\cdot \sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) -\sum_{i=1}^N\alpha_i \\ s.t.\quad \sum_{i=1}^N\alpha_iy_i = 0,\alpha_i \geq0\quad (1.11)
通过SMO算法(TODO)得到解 \alpha^* ，从而得到
w^* = \sum_{i=1}^N\alpha_i^*y_ix_i \quad (1.9)\\ b^* = y_i - \sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)
先写到这