Functional/Geometric Margin
两者区别在于 \(w\) 是否被标准化。效用边际会受到参数scale的影响。如果标准化了则两者等效。
Optimal Margin Classifier (Primal)
经过转换，问题变为一个QP问题，可以用一般优化器优化。
Primal:
\[\min_{w,b} \frac12 \|w\|^2 \\ \text{s.t.\quad} y^{(i)}(w^Tx^{(i)}+b) \geq 1\]
关于代码实现，感谢小胖子的建议，如果使用 scipy.optimize.minimize，
- 首先，最值必然位于某顶点处，这是凸优化的性质，因而必然有至少一个 \(x^{(j)}\) 使得约束条件tight，即取等号。即至少有一个点到平面的向量是支持向量
- 则b与w的关系构成等式，b可以用w线性表示
- 假设任意点是支持向量，该优化问题必然有最优解
- 那么遍历 N 个数据点，取
min和argmin即可
具体来说，假设
\[y^{(j)}(w^Tx^{(j)}+b) = 1\]
\[b = y^{(j)} - w^Tx^{(j)}\]
对于剩余的 \(N-1\) 个数据点，
\[ y^{(i)}(w^Tx^{(i)}+ y^{(j)} - w^Tx^{(j)}) \geq 1\]
\[\to y^{(i)}w^T(x^{(i)}-x^{(j)}) + y^{(i)}y^{(j)} \geq 1\]
可以写作线性的约束。
Dual
使用拉格朗日对偶，需要注意如果使用软间隔（见CS229-Notes3 Part8），在存在 regularization C 时，b的表达式变化，不再是式 (25) 的形式。因而在代码实现时，偷懒不考虑C了。
Kernel SVM
有以下注意点： 1. 要对输入数据 X 一开始就做标准化。否则用 softmax 这种核函数量级直接爆炸。比如本数据中 \(\|x\| \approx27\)， 想象一下\(e^{x^Ty}有多大\) 2. 相当于把线性的所有self.x替换为self.phi_x。K的存在确实替代了 featuremap 的显示表达，然而 b 的表达式里仍然是 \(\phi(x)\)，所以还是不得不给出 featuremap 的表达式。