Book Notes on Pattern Recognition and Machine Learning (PRML)
在之前的线性模型中，有时我们可以找到很多个模型都可以正确地进行分类。那么此时我们就需要选一个“最好”的模型。也就是说，我们不仅希望模型能正确分类，还希望它能尽可能地把不同类数据分得更开。
假设是 \(\{+1,-1\}\) 的二分类问题。为了衡量模型这种分类的信心，我们定义
\[r_i = y_i(w^Tx_i+b)\]此时，\(r_i\) 的值越大，表示模型对数据 \(x_i\) 的分类信心越大。然而，我们发现如果同时扩大 w 和 b 相同的倍数，会导致 \(r_i\) 同样变大，但分类结果不会有改变。所以我们还需要归一化，修改后的定义为
\[r_i = \frac{y_i(w^Tx_i+b)}{||w||_2}\]这里的 \(r_i\) 可以理解为数据点 i 到分类平面的距离。我们关注的是分类信心最小的那些点，即需要提升 \(r\) 的下界。（在教材中，这些最小的分类信心被称为margin，优化问题为最大化margin），可以写出对应的数学形式
\[max_{w,b}(min_{i=1,...,n} (r_i))\]改写一下，用 \(\tau=min(r_i)\) 来表示margin，此时的优化目标为
\[max_{\tau,w,b} \tau \qquad s.t.\ \forall i\ \ y_i(w^Tx_i+b)\geq\tau, \quad ||w||=1\]为了简便表示，将约束条件中的归一化挪到优化目标里，我们得到
\[max_{\tau,w,b} \frac{\tau}{||w||} \qquad s.t.\ \forall i\ \ y_i(w^Tx_i+b)\geq\tau\]我们可以发现，此时margin的具体值对最终得到的解没有影响，所以我们设为1，得到最终的 SVM 优化问题
\[min_{w,b} \frac{1}{2}||w||^2 \qquad s.t.\ \forall i\ \ y_i(w^Tx_i+b)\geq 1\]我们之所以加上 1/2 的系数是为了后续求解的方便。现在我们已经得到了 SVM 对应的优化问题，下一步就是求解。
因为原问题很难求解，我们使用拉格朗日乘子法将其转化为对偶问题求解。这里首先介绍拉格朗日乘子法。我们假设原优化问题为
\[min_w f(w) \quad s.t.\ g_k(w)\leq 0, k=1,...,K;\ h_{l}(w)=0,l=1,...,L\]对应的对偶问题为
\[L(w,\alpha,\beta) =f(w)+\sum_{i=1}^K\alpha_ig_i(w)+\sum_{i=1}^L\beta_ih_i(w)\]此时的约束条件也被称为 KKT condition，即
\[\forall k\ \alpha_kg_k(w) = 0, \quad \forall k \ g_k(w)\leq 0, \quad \forall k\ \alpha_k\geq 0\]回到 SVM 的求解中，我们现在的优化问题为
\[min_{w,b} \frac{1}{2}||w||^2 \qquad s.t.\ \forall i\ \ 1-y_i(w^Tx_i+b)\leq 0\]我们写出对偶问题
\[min_{w,b} max_{\alpha:\alpha\geq 0} L(w,b,\alpha)\] \[where\quad L(w,b,\alpha)=\frac{1}{2}||w||^2 + \sum_{i=1}^n \alpha_i[1-y_i(w^Tx_i+b)]\]我们分别对 w 和 b 求偏导，以消除 L 中的这两个变量只剩下 \(\alpha\)，可以得到
\[\frac{\partial L}{\partial w} = 0 \Rightarrow w = \sum_{i=1}^n\alpha_iy_ix_i\] \[\frac{\partial L}{\partial b} = 0 \Rightarrow \sum_{i=1}^n\alpha_iy_i = 0\]将这两个式子代入到 \(L(w,b,\alpha)\) 中消除变量后，我们可以得到只关于 \(\alpha\) 的优化目标，即
\[max_{\alpha} L(\alpha) = \sum_{i=1}^n\alpha_i - \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^ny_iy_j\alpha_i\alpha_jx_i^Tx_j\] \[s.t. \quad \forall i \ \alpha_i\geq 0, \sum_{i=1}^n\alpha_iy_i = 0\]这个优化问题就可以更容易地求解，最常用的一种求解方式称为 sequential minimal optimization（SMO）。在求解得到 \(\alpha\) 后，我们代回到 w 和 b 的式子中，可以得到
\[w = \sum_{i:\alpha_i > 0}\alpha_iy_ix_i\] \[b = \frac{1}{|S|}\sum_{s\in S}(y_s-\sum_{i\in S}\alpha_iy_ix_i^Tx_s),\quad where\ S = \{j\vert \alpha_j >0\}\]自此我们就求解得到了模型（w 和 b），接下来我们对这个结果进行一下分析。
正如之前提到的，我们在使用拉格朗日乘子转换为对偶问题时，需要满足 KKT 条件，即
这意味着，对于每一个数据 \(x_i\) ，要么对应的 \(\alpha_i=0\) ，要么 \(y_i(w^Tx_i+b)=1\) 。前者表明该数据很容易被分类，对最后的模型没有影响。后者表明该数据处于离分类平面最近的位置，是最难分类的。所有满足后者的数据构成了 Support Vector 支撑向量。我们也只用到了支持向量有关的数据作为模型的一部分。
所以当模型训练结束后，大部分训练数据都可以丢弃，只保留构成支持向量的数据。这些数据对应最难分类的一系列样本，正是这样一些数据把单个分类平面支撑起来，所以被称为支持向量机
在之前的介绍中，我们假设训练数据是完全可分类的，而这是一种很强的假设。在这一节，我们通过引入误差项，允许一些样本的分类信心没有那么强，允许一些样本被分错类。我们记误差项为 \(\xi\) ，正则化系数为常数 \(C\) ，此时的优化问题可写为
\[min_{\xi,w,b}\frac{1}{2}||w||^2 + C\sum_{i=1}^n\xi_i\quad s.t. \forall i, \ \ y_i(w^Tx_i+b)\geq 1-\xi_i,\ \xi_i\geq 0\]等价于
\[min_{\xi,w,b}\frac{1}{2}||w||^2 + C\sum_{i=1}^n max(0,1-y_i(w^Tx_i+b))\]和上面一样的变化方法，这里直接写出对偶问题中的优化函数
\[L(w,b,\xi,\alpha,\beta) = \frac{1}{2}||w||^2 + C\sum_{i=1}^n\xi_i + \sum_{i=1}^n\alpha_i[1-\xi_i-y_i(w^Tx_i+b)] - \sum_{i=1}^n \beta_i\xi_i\]和上面的流程一样，接着我们对 w b 和 \(\xi\) 求偏导消除变量，w 和 b 的偏导结果和标准SVM一样，对 \(\xi\) 求偏导则可得到
\[\frac{\partial L}{\partial \xi_i} = 0 \Rightarrow \alpha_i + \beta_i = C\]代入原函数后，我们得到变换后的优化问题
\[max_{\alpha} L(\alpha) = \sum_{i=1}^n\alpha_i - \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^ny_iy_j\alpha_i\alpha_jx_i^Tx_j\] \[s.t. \quad \forall i \ 0\leq \alpha_i \leq C, \sum_{i=1}^n\alpha_iy_i = 0\]最后我们对结果进行分析。这里因为引入了误差项 \(\xi\) 不等式，KKT条件变为
\[\forall i,\quad \alpha_i \geq 0,\quad y_i(w^Tx_i+b)-1+\xi_i\geq 0,\quad a_i(y_i(w^Tx_i+b)-1+\xi_i)=0\] \[\forall i,\quad \beta_i \geq 0,\quad \xi_i\geq 0,\quad \beta_i\xi_i=0\]可以看出，这样增加误差项的处理方式防止了过拟合，提升了对训练数据的泛化能力
对于非线性的分类问题，有时需要用核函数 \(\phi(X)\) 代替 X 。此时的SVM可表示为 \(Y = w^T\phi(X)+b\)
求解可以得到 \(w=\sum_{i=1}^n\alpha_iy_i^*\phi(x_i)\) ，代入原模型可得
\[y_j = (\sum_{i=1}^n\alpha_iy_i^*\phi(x_i))^T\phi(x_j)+b = \sum_{i:\alpha>0} \alpha_iy_i^*k(x_i,x_j) + b\]我们可以发现，SVM并不能提供概率输出，即每个数据属于某个类的概率。为了解决这个问题，其中一种方式再拟合，即
\[p(y^*=1\vert x) = \sigma(Ay(x)+B)\]这里 \(\sigma(\cdot)\) 是logistic sigmoid函数，\(y(x)\) 为SVM的输出值，A和B为通过交叉熵loss学习的参数。我们需要另一套数据集来训练这个 logistic 模型，必须与之前训练 SVM 的数据集相互独立，否则会有严重的过拟合现象。即使这样，效果仍然很差
最后我们来看下 SVM 和 Logistic regression 的联系。
首先是 SVM，在软间隔的SVM中，优化目标为
把它写成Loss的形式可以得到
\[L = \sum_{i=1}^n max(0,1-y_i^*y_i) + \lambda ||w||^2,\quad where\ \ \lambda = \frac{1}{2C}\]我们再来看 logistics regression，之前我们针对的是 \(\{0,1\}\) 标签。为了保持和 SVM 标签一致，我们假设为 \(\{+1,-1\}\) 标签，则有
\[p(y^*_i=1\vert x) = \frac{1}{1+e^{-x_i^T\beta}}, \quad p(y^*_i=-1\vert x)= 1- p(1) = \frac{1}{1+e^{x_i^T\beta}}\]因此可以得到通式
\[p(y_i^*\vert y_i) = \frac{1}{1+e^{-y_i^*y_i}}\] \[L = \sum_{i=1}^n \ln(1+e^{-y_i^*y_i}) + \lambda ||w||^2\]可以看出两者 Loss 函数的相似与不同。
之前的SVM存在一些缺陷，比如它直接输出分类决策而不是后验概率，主要用来处理二分类问题等。因此又提出了RVM，在保留SVM特点的同时避免了SVM的局限性。
RVM类似与之前的贝叶斯线性回归，给定输入数据 x 后，ground-truth 的分布为 \(y^*\vert x,w \sim N(y(x),\sigma^2)\) ，这里的 \(y(x)\) 写成基函数的形式，即
\[y(x) = \sum_{i=1}^{n+1} w_i\phi_i(x) = w^T\phi(x)\]我们用矩阵表示，写出似然函数
\[p(Y^*\vert X,w) = \prod_{i=1}^np(y^*_i\vert x_i,w) \Rightarrow Y^*\vert X,w \sim N(\phi w,\sigma^2 I)\]这里 \(\phi\) 是一个 n*(n+1) 的矩阵，\(\phi_{ij} = \phi_j({x_i})\) 。和之前不同的一点是，RVM关键区别是为每个权参数 \(w_i\) 都引入一个单独的超参数 \(\alpha_i\) ，而不是像之前一样共享一个超参数 \(\Sigma\) ，所以此时的模型先验分布为
\[p(w\vert \alpha) = \prod_{i=1}^{n+1}N(0,\alpha_i) \Rightarrow w\vert \alpha \sim N(0,\alpha)\]至此结合以上表达式，我们可以写出模型的后验概率 \(p(w\vert X,Y)\) ，即
\[w\vert X,Y \sim N(\mu,\Sigma)\] \[where \quad \mu = \sigma^{-2}\Sigma \phi^TY, \quad \Sigma = ((\alpha I)^{-1}+\sigma^{-2}\phi^{T}\phi)^{-1}\]如果我们再知道超参 \(\alpha\) 和 \(\sigma\) 的值，就可以对新数据进行预测了。所以接下来的一步是求这两个超参。我们通过对权向量积分最大化边缘似然函数，即
\[p(Y^*\vert X) = \int p(Y^*\vert X,w)p(w\vert\alpha)dw = \int N(Y^*\vert \phi w,\sigma^2I)N(w\vert 0,\alpha)dw\]令上式导数为零，可以得到估计方程
\[\alpha_i^{new} = \frac{1-\alpha_i \Sigma_{ii}}{\mu_i^2},\qquad (\sigma^2)^{new} = \frac{||Y^*-\phi\mu||^2}{n-\sum_i(1-\alpha_i \Sigma_{ii})}\]所以超参 \(\alpha\) 和 \(\sigma\) 的整个学习流程为
我们观察收敛后的超参，可以发现一部分 \(\alpha_i\) 趋于无穷大。那么对应的模型权值 \(w_i\) 的均值和方差都趋近零，也就意味着这些权值及对应的基函数对模型没有贡献。这就和之前的SVM相似了，剩下的非零权值输入 \(x_n\) 称为相关向量，类似与SVM中的支持向量。
我们用 \(\alpha^\star\) 和 \(\sigma^\star\) 来表示最后学到的超参。在预测阶段，我们假设输入数据为 \(x_0\)，那么此时可以写出预测输出的概率分布
\[p(y_{pred}\vert x_0) = \int p(y_{pred}\vert x_0,w)p(w\vert X,Y)dw = \int N(y_{pred}\vert \phi(x_0)^Tw,(\sigma^*)^2)N(w\vert\mu,\Sigma)dw\] \[y_{pred}\vert x_0 \sim N(\mu^T\phi(x_0),(\sigma^*)^2+\phi(x_0)^T\Sigma\phi(x_0))\]我们就可以根据上式得到我们最后的预测输出 \(y_{pred}\)
以上是 RVM 在回归任务中的应用，接下来我们简要介绍一下 RVM 在分类任务的应用。
在分类任务中，我们还是保持模型 \(w\) 的高斯先验分布，同样为每个权参数 \(w_i\) 都引入一个单独的超参数控制精度。只是此时的输出变为 \(y(x) = sigmoid(w^T\phi(x))\) (在多分类问题中则变为 softmax)
和回归问题不同的是，这里不再对模型 \(w\) 解析求积分来求得最大化边缘似然函数，而是使用了拉普拉斯近似的方法求解。
最后总结下 RVM 的优劣