SVM和Kernel

这一章的前半部分主要讲SVM，SVM的具体推导过程我就不赘述了，网上一堆一堆的。简单提一句，对偶问题的转换，是对\(\beta, \xi\)求Lagrange函数的下界，转换为\(\alpha, \mu, C\)的优化问题，这个问题就是原问题的对偶问题，相应的就是要最大化这个对偶问题了。由于这是个凸问题，且满足Slater条件，对偶问题的解就是原问题的解了（对偶间隙为0）。

原问题：

\[\min \frac{1}{2} \| \boldsymbol{\beta} \|^2 + C \sum_{i=1}^N \xi_i \\ s.t. \xi_i \le 0, y_i(\boldsymbol{x}_i^T \boldsymbol{\beta}) \le 1-\xi_i, \forall i\]

对偶问题：

\[\max L_D = \sum_{i=1}^N \alpha_i - \frac{1}{2}\sum_{i=1}^N\sum_{i^\prime=1}^N \alpha_i \alpha_{i^\prime} y_i y_{i^\prime}\boldsymbol{x}_i^T \boldsymbol{x}_{i^\prime} \\ s.t. 0 \le \alpha_i \le C, \sum_{i=1}^N \alpha_i y_i = 0, \forall i\]

书上提到说这个对偶问题相比原问题更简单(“simpler convex quadratic programming problem”)，这点我并不能理解（诚意请教）。我觉得两个问题是一样难的，只是后者的优势在于\(L_D\)中\(\boldsymbol{x}\)的点积，可以自然而然地引入Kernel。

TODO