今天人工智能课考试，果不其然跪在了支持向量机上。
题也不难，但我真的是啥都不会。
究其原因，其一我是从神经网络开始听说机器学习的，所以就戴上了鄙视SVM的有色眼镜，一直不情愿去学；其二学起来确实也感觉有点费劲，不像线性回归、随机森林这些模型简单直观；其三课上讲支持向量机一节我因为一些个人原因大部没听；其四因为后来还算自己补了一些支持向量机的知识，自我感觉很良好没有认真复习，只是考前随便看了看，结果随便一看看得心里拔凉，但也没时间继续复习了。
找了这么多理由，没有怒跪一波管用。花点时间亡羊补牢吧。
先看题:
有三个点，(0,0)是正样例，(-1,-1),(1,1)是两个负样例，核函数\(K=(1+\vec x\cdot \vec y)^2\)，求支持向量机参数，以及(0,1)的分类。
核心考点是一个对偶问题的公式：
$$\min_\alpha \frac{1}{2}\Sigma_{i=1}^{N}\Sigma_{j=1}^{N}\alpha_i\alpha_j y_i y_j K(\vec x_i, \vec x_j) - \Sigma_{i=1}^{N}\alpha_i
$$同时满足：
$$
\begin{align}
& \Sigma_{i=1}^{N}\alpha_i y_i = 0
& \alpha_i \geq 0, i = 1,2,\cdots, N
\end{align}
$$求出三个\(\alpha\)很简单，把三个点带进去，然后求\(\alpha\)的极值方程就行了，但我掌握不牢的第一个体现是忘了公式里后面到底是\(\Sigma_{i=1}^{N}\alpha_i\)还是\(\Sigma_{i=1}^{N}\alpha_i^2\)（可能是被正则化影响…）。当时隐约记得应该是前者，但有点分不清，这个问题其实不算大。
但接着往下看，还要判断(0,1)的分类，这就一下击穿了我纸糊的SVM知识。用主问题的\(\vec w\)和\(b\)来判断还好，变成核空间了咋整？我毫无头绪。我第一反应是利用\(\alpha\)把\(\vec w\)和\(b\)求出来，但因为我一点都不懂SVM，并不知道怎么用\(\alpha\)求出\(\vec w\)和\(b\)，所以这就等于是要我推对偶问题公式。考虑到我本来就不太确定这个公式的形式，我就在考场上推了起来。由主问题：
$$\min_{w,b} | \vec w |^2
$$同时满足：
$$
y_i(\vec w \cdot \vec x_i+b) \geq 1, i = 1,2,\cdots, N
$$使用拉格朗日乘子法，为每个约束条件添加拉格朗日乘子\(\alpha\)，得拉格朗日函数：
$$
L(\vec w,b,\alpha) = \frac{1}{2} | \vec w |^2 + \Sigma_{i=1}^N\alpha_i\left (1-y_i(\vec w \cdot \vec x_i+b)\right )
$$关于拉格朗日乘子法，这里多说两句，因为考场上开始怀疑拉格朗日函数极值问题和主问题极值问题的等价性了（微积分都还给了老师，惭愧惭愧！）。拉格朗日函数对\(\alpha\)的偏导为0可以得到约束条件，这一部分的等价性不难发现。而拉格朗日函数对\(\vec w\)和\(b\)的偏导为0，则意味着主函数和约束条件对某个变量的偏导数方向共线。如果不共线，总能通过调整某个变量使主函数变得更大（针对max优化）或者更小（针对min优化）。
这里按照传统的条件极值的解法，应该分别对\(\vec w\)、\(b\)和\(\alpha\)求偏导为0然后解联立方程组。但这样的话数学上就没什么大事了，剩下的就是暴力解方程组，可能很困难。SVM使用了SMO的trick，这里只对\(\vec w\)和\(b\)求偏导为0，\(\alpha\)用SMO迭代解决。这还是我在考场上琢磨出来的。但我还是出了错，只求了\(\vec w\)的偏导，忘了还有\(b\)这样一个参数，于是半天没有推出来，卒。
对\(w\)求偏导得：
$$
\vec w=\Sigma_{i=1}^N\alpha_i y_i \vec x_i
$$对\(b\)求偏导得：
$$
0=\Sigma_{i=1}^N\alpha_i y_i
$$这两个式子代入到拉格朗日函数中消去\(\vec w\)和\(b\)。\(w\)直接代入消去即可，\(b\)则用到了\(0=\Sigma_{i=1}^N\alpha_i y_i\)。这就得到了最开始给出的对偶问题公式。
这么一推，虽然得到了优化出\(\alpha\)后，\(\vec w\)应该怎么求的线索，但其实没什么卵用，因为通过核函数已经隐式地把\(\vec x\)映射到特征空间得到\(\phi(\vec x)\)了，而\(\phi(\vec x)\)形式未知。这个公式其实也不难，但在考场上进一步推出来超出了我的能力……
通过特征空间映射，决策函数的形式从\(f(\vec x)=\vec w \cdot \vec x+b\)变成了：
$$
f(\vec x)=\vec w \cdot \phi(\vec x)+b
$$将\(\vec w=\Sigma_{i=1}^N\alpha_i y_i \phi(\vec x_i)\)代入：
$$
f(\vec x)=\Sigma_{i=1}^N\alpha_i y_i \phi(\vec x_i)\cdot \phi(\vec x)+b
$$按照核函数的定义：
$$
f(\vec x)=\Sigma_{i=1}^N\alpha_i y_i K(\vec x_i, \vec x)+b
$$这样决策函数中就不显含特征映射函数\(\phi(\vec x)\)了，(0,1)的分类可以由\(\alpha\)和\(b\)给出。在这个只有三个样本的例子中，可以利用二次函数极值求出\(\alpha\)，但偏移量\(b\)我肯定是不知道怎么求的。
首先，由KKT条件知，若\(\alpha_i \geq 0 \)，则必有\(y_i f(\vec x_i) - 1 = 0\)，即\(x_i\)为支持向量。依据这个判据可以找到所有的支持向量，然后根据这些支持向量\(\vec x_s \)都满足：
$$
[\Sigma_{i=1}^N\alpha_i y_i K(\vec x_i, \vec x_s)+b]y_i=1
$$把不等式变成等式，求出这些支持向量的\(b\)。最后对这些\(b\)取平均作为最终的\(b\)。
这并不是什么技术博文，而是对自己的吐槽。即便“亡羊补牢”了一把，我依然一点都不懂SVM。
BTW
为了写这篇blog，还折腾了一下hexo的\(\LaTeX\)写法。Google了一下发现了一个Github项目hexo-math，看起来好像挺对口，用起来真是难用，比如默认设置的MathJax的js链接已经失效，要自己custom一个，这么简单的事，issue提了半年没人管，感觉是年久失修。索性自己直接编辑了Hacker模板在header中引入了MathJax的js然后渲染。效果还可以，需要注意的两个坑是：
- 直接用
$E=mc^2$并不能获得行内公式环境，要用奇怪的括号括起来，如\\(E=mc^2\\)，在数学环境外需要用两个反斜杠，环境内一个即可。 - 下划线貌似会和Markdown的语法冲突，所以也要用反斜杠转义