线性可分 SVM
数据 $D={x_i,y_i}$, 学习目标为分类超平面 $w x+b=0$ 也即 $w,b$.
\[\begin{align*} & \max_{w, b} \lambda \\ & \text{ s.t. } \frac 1 {\| w\|} y_i (w x_i + b) \geq \lambda \end{align*}\]直接求解这个问题则 $w, b$ 有一个多余自由度（模长）。利用该自由度将 $w \cdot \lambda$ 设定为定值，于是可以将问题改写为：
\[\begin{align*} & \min_{w, b} \frac 1 2 \| w \| ^ 2 \\ & \text{ s.t. } y_i(w x_i + b) - 1 \geq 0 \end{align*}\]上式中 $1/2$ 是为了后续推导简洁，当前无意义。
线性软间隔 SVM
软间隔最大化问题适用于非严格线性可分问题。为了应对非严格线性可分数据，引入松弛变量 $\xi$ 将上式变更为：
\[\begin{align*} & \min_{w, b, \xi} \frac 1 2 \| w \| ^ 2 + C \sum_i \xi_i \\ & \text{ s.t. } \left\{\begin{array}{l} y_i(wx_i + b) \geq 1 - \xi_i \\ \xi_i \geq 0 \end{array}\right. \end{align*}\]式中 $C$ 为惩罚参数。上式可以被整理为：
\[\begin{align*} \min_{w, b} \frac 1 2 \| w \|^ 2 + C \sum_i \max \left[ 0, 1 - y_i(w x_i + b) \right] \end{align*}\]函数 $\max(0,\cdot)$ 被称为合叶损失函数（也即 ReLU 激活函数），于是可以认为软间隔 SVM 的损失函数是带二次正则项的合叶损失函数。当 $C\to\infty$ 软间隔过渡为硬间隔.
SVM 对偶问题
对软间隔 SVM 使用拉格朗日乘子法求其对偶问题。定义拉格朗日函数：
\[\begin{align*} L = \frac 1 2 \| w \|^2 + C \sum_i \xi_i - \sum_i \alpha_i \left[ y_i(w x_i+b) - 1 + \xi_i \right] - \sum_i \mu_i \xi_i \end{align*}\]关于 $w,b,\xi$ 求导并令导数等于零的到：
\[\begin{align*} & w = \sum_i \alpha_i y_i x_i \\ & \sum_i \alpha_i y_i = 0 \\ & C - \alpha_i -\mu_i = 0 \end{align*}\]于是将最优化问题整理为：
\[\begin{align*} &\min_\alpha \frac 1 2 \sum_{i=1}^N \sum_{j=1}^N \alpha_i\alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^N \alpha_i \\ &\text{ s.t. } \left\{ \begin{array}{l} \sum_{i=1}^N \alpha_i y_i = 0 \\ 0 \leq \alpha_i \leq C \end{array}\right. \end{align*}\]由于拉格朗日乘子法的 KKT 条件，有
\[\begin{align*} \alpha_i \left[ y_i(w x_i+b) - 1 + \xi_i \right] = 0 \end{align*}\]也即只有满足约束条件边界的样本才会有 $a_i\neq 0$, 这些向量就是支持向量，此即支持向量机名字的来源。
核函数
课程中核函数是在本节引入的，讨论对偶问题只是为了讨论核函数。这里跳出 SVM 的限制，较为一般的介绍核函数。
有以下两个事实：
- 有时在低维空间不好处理的问题，在高维空间可能变得简单。如低维空间非线性可分数据在高维空间可能变得线性可分。因此使用映射 $\phi(\cdot)$ 将数据集映射到一个高维空间有助于问题解决。
- 很多学习算法在计算过程中并不需要计算 $\phi(x)$，而是要计算 $\phi(x)\cdot\phi(y)$，也即高维空间中的内积，如感知机模型。
这种情况下，定义 $k(x,y)=\phi(x)\cdot\phi(y)$ 即为核函数。核函数的优势在于，有时候核函数的计算比直接计算 $\phi$ 容易，甚至 $\phi$ 不可计算时核函数仍然可计算核函数。
核函数的选取依赖于经验。常用的核函数：
多项式核函数：
\[K(\vec x, \vec z)=(\vec x \cdot \vec y + 1)^p\]高斯核函数： $$ K(\vec x, \vec z) = \exp\left(
- \frac{|\vec x - \vec z| ^ 2}{2 \sigma^2} \right) $$
使用核函数的软间隔 SVM 对偶问题整理为（略去 KKT 约束条件）：
\[\begin{align*} &\min_\alpha \frac 1 2 \sum_{i=1}^N \sum_{j=1}^N \alpha_i\alpha_j y_i y_j K(x_i, x_j) - \sum_{i=1}^N \alpha_i \\ &\text{ s.t. } \left\{ \begin{array}{l} \sum_{i=1}^N \alpha_i y_i = 0 \\ 0 \leq \alpha_i \leq C \end{array}\right. \end{align*}\]习题
1.1 比较感知机的对偶形式和支持向量机的对偶形式。
【解】支持向量机：
\[\begin{align*} &\min_\alpha \frac 1 2 \sum_{i=1}^N \sum_{j=1}^N \alpha_i\alpha_j y_i y_j K(x_i, x_j) - \sum_{i=1}^N \alpha_i \\ &\text{ s.t. } \left\{ \begin{array}{l} \sum_{i=1}^N \alpha_i y_i = 0 \\ 0 \leq \alpha_i \leq C \end{array}\right. \end{align*}\]感知机：
\[\begin{align*} &\min_\alpha \frac 1 2 \sum_{y_i \neq \hat y_i} \sum_{j=1}^N \alpha_j y_i y_j K(x_i, x_j) - \sum_{i=1}^N \alpha_i \\ \end{align*}\]感知机的损失函数没有约束条件，也没有最优解。感知机使用梯度下降法求解，SVM 理论上可以求解析解。
1.3
\[\begin{align*} & L = \frac 1 2 \| w \|^2 + C \sum_i \xi_i^2 - \sum_i \alpha_i \left[ y_i(w \cdot x_i + b) - (1 - \xi_i) \right] - \sum_i \beta_i \xi_i \\ & \alpha, \beta \geq 0 \end{align*}\]关于 $w, b, \xi_i$ 求偏导数并令偏导数为零的到整理的到：
\[\begin{align*} & L = \frac 1 2 \sum_{i, j} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \frac {\sum_i(\alpha_i+\beta_i)^2} {4C} \\ & \alpha, \beta \geq 0 \end{align*}\]1.4 证明内积的正整数幂函数：
\[\begin{align*} K(x, z) = (x \cdot z) ^ p \end{align*}\]是正定核函数，$p$ 为正整数，$x, y\in R_n$.
【解】恰好该核函数对应的映射容易找到。
\[\begin{align*} K(x,z) &= (x \cdot z) ^ p \\ &= (x_1z_1 + x_2z_2 + \cdots x_Dz_D)^p \\ &= \sum_{i_1+i_2+\cdots+i_D=p} A_{i_1+i_2+\cdots+i_D=p} (x_1z_1)^{i_1}(x_2z_2)^{i_2} \cdots (x_D z_D)^{i_D} \end{align*}\]注意到该和式中，$x_i, z_i$ 总是有相同的次数，可以构造映射：
\[\begin{align*} \phi(x) &= \left[\sqrt{A_{i_1i_2\cdots i_D}} \cdot x_1^{i_1}x_2^{i_2} \cdots x_D^{i_D} \right] \end{align*}\]也即对满足 $i_i+i_2+\cdots+i_D=p$ 的每一种下标组合构造一个维度。