（不手打公式了，太费时间，也没啥收益。直接截图……）
第六章的核方法必须要对所有的训练数据点进行求值。这一章介绍具有稀疏解的基于核的方法，从而只依赖于训练数据点的一个子集。
arg min w , b 1 2 ∥ w ∥ 2 s.t. t n ( w T ϕ ( x n ) + b ) ⩾ 1 n = 1 , … , N \argmin_{\bm w,b}\frac{1}{2}\|\bm w\|^2 \\ \text{s.t.\quad } t_n(\bm w^T\bm \phi(\bm x_n)+b)\geqslant 1 \qquad n=1,\dots,N w,bargmin21∥w∥2s.t.tn(wTϕ(xn)+b)⩾1n=1,…,N 这是二次规划问题。约束中等式满足的称之为激活activate，其他的称之为未激活inactive 引入拉格朗日乘子 L ( w , b , a ) = 1 2 ∥ w ∥ 2 − ∑ n = 1 N a n { t n ( w T ϕ ( x n ) + b ) − 1 } L(\bm w, b,\bm a) = \frac{1}{2}\|\bm w\|^2-\sum_{n=1}^N a_n\{ t_n(\bm w^T\bm \phi(\bm x_n)+b)-1 \} L(w,b,a)=21∥w∥2−n=1∑Nan{tn(wTϕ(xn)+b)−1} 使用KKT条件，令 ∂ L ∂ w = 0 , ∂ L ∂ b = 0 \frac{\partial L}{\partial \bm w}=0,\frac{\partial L}{\partial b}=0 ∂w∂L=0,∂b∂L=0，得到 w = ∑ n = 1 N a n t n ϕ ( x n ) 0 = ∑ n = 1 N a n t n \begin{aligned} \bm w&=\sum_{n=1}^N a_nt_n\bm \phi(\bm x_n) \\ 0 &=\sum_{n=1}^N a_n t_n \end{aligned} w0=n=1∑Nantnϕ(xn)=n=1∑Nantn
消除 w , b \bm w,b w,b得到对偶形式 L ~ ( a ) = ∑ n = 1 N a n − 1 2 ∑ n = 1 N ∑ m = 1 N a n a m t n t m k ( x n , x m ) s.t. a n ⩾ 0 n = 1 , … , N ∑ n = 1 N a n t n = 0 \begin{aligned} \tilde L(\bm a)=\sum_{n=1}^N a_n - \frac{1}{2}\sum_{n=1}^N \sum_{m=1}^N &a_n a_m t_n t_m k(\bm x_n,\bm x_m) \\ \text{s.t. \qquad\qquad} a_n &\geqslant 0 \quad n=1,\dots,N \\ \sum_{n=1}^N a_nt_n &= 0 \end{aligned} L~(a)=n=1∑Nan−21n=1∑Nm=1∑Ns.t. ann=1∑Nantnanamtntmk(xn,xm)⩾0n=1,…,N=0 这里还需要满足其他KKT条件。 对偶形式的缺点是计算复杂度大，二次规划问题的复杂度从特征相关的 O ( M 3 ) \mathcal O(M^3) O(M3)变成了样本数量相关的 O ( N 3 ) \mathcal O(N^3) O(N3)。但对偶形式可以直接定义核函数，实现无限维特征。从上式也能看出，核函数的Gram矩阵要正定，否则 L ~ \tilde L L~没有上界。 推断时，判别函数为 y ( x ) = ∑ n = 1 N a n t n k ( x , x n ) + b (1) y(\bm x)=\sum_{n=1}^Na_n t_n k(\bm x,\bm x_n)+b \tag{1} y(x)=n=1∑Nantnk(x,xn)+b(1) 其中大部分 a n = 0 a_n=0 an=0是未激活的，剩下激活的对应数据点称之为支持向量support vectors，这些点满足 t n y ( x n ) = 1 t_ny(\bm x_n)=1 tny(xn)=1. 由此稀疏性产生了！ 可以证明最大超平面半间隔为 1 ∥ w ∥ = ∑ n = 1 N a n \frac{1}{\|\bm w\|} = \sqrt{\sum_{n=1}^N a_n} ∥w∥1=n=1∑Nan
上式 b b b可以通过任意一条支持向量有关的约束产生 t n ( ∑ m ∈ S a m t m k ( x n , x m ) + b ) = 1 t_n \left(\sum_{m\in \mathcal S}a_mt_m k(\bm x_n, \bm x_m)+b \right)=1 tn(m∈S∑amtmk(xn,xm)+b)=1 其中 S \mathcal S S是支持向量集合。也可以通过数值计算上更稳定的方法得到 b = 1 ∣ S ∣ ∑ n ∈ S ( t n − ∑ m ∈ S a m t m k ( x n , x m ) ) b = \frac{1}{|{\mathcal S}|} \sum_{n\in \mathcal S} \left ( t_n - \sum_{m \in \mathcal S} a_m t_mk(\bm x_n, \bm x_m)\right ) b=∣S∣1n∈S∑(tn−m∈S∑amtmk(xn,xm)) SVM目标函数的等价形式为 ∑ n = 1 N E ∞ ( y n ( x n ) t n − 1 ) + λ ∥ w ∥ 2 (2) \sum_{n=1}^N E_{\infty} (y_n(\bm x_n) t_n - 1)+\lambda \|\bm w\|^2 \tag{2} n=1∑NE∞(yn(xn)tn−1)+λ∥w∥2(2) 其中对于 E ∞ ( z ) E_{\infty}(z) E∞(z)，当 z ⩾ 0 z\geqslant 0 z⩾0时，为0，否则为 + ∞ +\infty +∞. λ > 0 \lambda>0 λ>0
引入松弛变量 ξ \xi ξ
拉格朗日乘子变为 L ( w , b , a ) = 1 2 ∥ w ∥ 2 + C ∑ n = 1 N ξ n − ∑ n = 1 N a n { t n ( w T ϕ ( x n ) + b ) − 1 + ξ n } − ∑ n = 1 N μ n ξ n s.t. a n ⩾ 0 t n y ( x n ) − 1 + ξ n ⩾ 0 a n ( t n y ( x n ) − 1 + ξ n ) = 0 μ n ⩾ 0 ξ n ⩾ 0 μ n ξ n = 0 \begin{aligned} L(\bm w, b,\bm a) = \frac{1}{2}\|\bm w\|^2 + C\sum_{n=1}^N \xi_n-&\sum_{n=1}^N a_n\{ t_n(\bm w^T\bm \phi(\bm x_n)+b)-1+\xi_n \}-\sum_{n=1}^N \mu_n\xi_n \\ \text{s.t. \qquad \qquad\qquad\qquad\qquad} a_n &\geqslant 0 \\ t_ny(\bm x_n)-1+\xi_n &\geqslant 0 \\ a_n(t_ny(\bm x_n)-1+\xi_n ) &=0 \\ \mu_n &\geqslant 0 \\ \xi_n&\geqslant 0 \\ \mu_n \xi_n &= 0 \end{aligned} L(w,b,a)=21∥w∥2+Cn=1∑Nξn−s.t. antny(xn)−1+ξnan(tny(xn)−1+ξn)μnξnμnξnn=1∑Nan{tn(wTϕ(xn)+b)−1+ξn}−n=1∑Nμnξn⩾0⩾0=0⩾0⩾0=0 其中 n = 1 , … , N n=1,\dots,N n=1,…,N 上式对 w , b \bm w,b w,b结果同上，对 ξ \xi ξ求偏导得到 a n = C − μ n a_n=C-\mu_n an=C−μn，进而得到 L ~ ( a ) = ∑ n = 1 N a n − 1 2 ∑ n = 1 N ∑ m = 1 N a n a m t n t m k ( x n , x m ) s.t. C ⩾ a n ⩾ 0 n = 1 , … , N ∑ n = 1 N a n t n = 0 \begin{aligned} \tilde L(\bm a)=\sum_{n=1}^N a_n - \frac{1}{2}\sum_{n=1}^N \sum_{m=1}^N &a_n a_m t_n t_m k(\bm x_n,\bm x_m) \\ \text{s.t. \qquad\qquad} C\geqslant a_n &\geqslant 0 \quad n=1,\dots,N \\ \sum_{n=1}^N a_nt_n &= 0 \end{aligned} L~(a)=n=1∑Nan−21n=1∑Nm=1∑Ns.t. C⩾ann=1∑Nantnanamtntmk(xn,xm)⩾0n=1,…,N=0 推断时，仍然是式（1） 解释：
a n = 0 a_n=0 an=0，不是支持向量 C > a n > 0 C>a_n>0 C>an>0，得到 μ n > 0 \mu_n>0 μn>0，即 ξ n = 0 \xi_n=0 ξn=0，在间隔上 a n = C a_n=C an=C，在间隔内。如果 ξ ⩽ 1 \xi\leqslant1 ξ⩽1，则分对，否则分错计算 b b b时，用 0 < a n < C 0<a_n <C 0<an<C的样本点集合计算 参数的优化过程还是用SMO算法多。SMO和训练数据点数量的关系位于一次和二次之间，取决于具体应用。
L ~ ( a ) = − 1 2 ∑ n = 1 N ∑ m = 1 N a n a m t n t m k ( x n , x m ) s.t. 1 / N ⩾ a n ⩾ 0 n = 1 , … , N ∑ n = 1 N a n t n = 0 ∑ n = 1 N a n ⩾ ν \begin{aligned} \tilde L(\bm a)= - \frac{1}{2}\sum_{n=1}^N \sum_{m=1}^N &a_n a_m t_n t_m k(\bm x_n,\bm x_m) \\ \text{s.t. \qquad\qquad} 1/N\geqslant a_n &\geqslant 0 \quad n=1,\dots,N \\ \sum_{n=1}^N a_nt_n &= 0 \\ \sum_{n=1}^N a_n &\geqslant \nu \end{aligned} L~(a)=−21n=1∑Nm=1∑Ns.t. 1/N⩾ann=1∑Nantnn=1∑Nananamtntmk(xn,xm)⩾0n=1,…,N=0⩾ν ν \nu ν可以被解释为边缘错误margin errors（即 ξ n > 0 \xi_n>0 ξn>0）的上界，也是支持向量比例的下界。（后半句能理解，前半句不能）。如图，用高斯核
从贝叶斯的角度看，SVM有一个缺点是，参数 C , ν C,\nu C,ν之类的需要手动用cross-validation之类的方法选择。后文的RVM似乎是解决了这个问题。软间隔SVM可以看作是对hinge loss的优化 ∑ n = 1 N E S V ( y n t n ) + λ ∥ w ∥ 2 \sum_{n=1}^N E_{SV}(y_n t_n)+\lambda\|\bm w\|^2 n=1∑NESV(yntn)+λ∥w∥2 其中 λ = ( 2 C ) − 1 , E S V ( y n t n ) = [ 1 − y n t n ] + \lambda = (2C)^{-1},E_{SV}(y_nt_n)=[1-y_nt_n]_{+} λ=(2C)−1,ESV(yntn)=[1−yntn]+ 逻辑回归中，如果用 t n ∈ { − 1 , + 1 } t_n\in \{-1,+1\} tn∈{−1,+1}表示，则MAP损失函数为 ∑ n = 1 N E L R ( y n t n ) + λ ∥ w ∥ 2 \sum_{n=1}^N E_{LR} (y_nt_n)+\lambda \| \bm w\|^2 n=1∑NELR(yntn)+λ∥w∥2 其中 E L R ( y t ) = ln ( 1 + exp ( − y t ) ) E_{LR}(yt)=\ln(1+\exp(-yt)) ELR(yt)=ln(1+exp(−yt)) E L R E_{LR} ELR和 E S V E_{SV} ESV如图所示，注意 E S V E_{SV} ESV会带来稀疏解，正如SVM中见到的
把SVM用于回归，目标函数为 C ∑ n = 1 N E ϵ ( y ( x n ) − t n ) + 1 2 ∥ w ∥ 2 C\sum_{n=1}^N E_{\epsilon}(y(\bm x_n)-t_n)+\frac{1}{2}\|\bm w\|^2 Cn=1∑NEϵ(y(xn)−tn)+21∥w∥2 其中 E ϵ ( y ( x ) − t ) = max ( ∣ y ( x ) − t ∣ − ϵ , 0 ) E_{\epsilon}(y(\bm x)-t )= \max(|y(\bm x)-t|-\epsilon, 0) Eϵ(y(x)−t)=max(∣y(x)−t∣−ϵ,0) 这样相比于SVM，能产生对于数据的稀疏解。引入松弛变量 ξ , ξ ^ \xi,\hat \xi ξ,ξ^，如图分别对应正负两侧的惩罚，得到 引入拉格朗日乘子，得到
对 w , b , ξ , ξ ′ \bm w, b, \bm \xi, \bm \xi' w,b,ξ,ξ′求偏导，并置为0，得到 代入得到
需要满足 推断时，为 对 a n a_n an讨论（对 a n ′ a_n' an′的讨论类似）
0 < a n ⩽ C 0<a_n\leqslant C 0<an⩽C，对应 ϵ + ξ n + y n − t n = 0 \epsilon+\xi_n+y_n-t_n=0 ϵ+ξn+yn−tn=0，当数据在边界时， ξ n = 0 \xi_n=0 ξn=0；或者在边界之上， ξ n > 0 \xi_n>0 ξn>0，此时 a n = C a_n=C an=C. 以上这些都是支持向量 a n = 0 a_n=0 an=0，边界内b b b的求解方法与上文类似
最多只有 ν N \nu N νN个点落在边界外，同时至少有 ν N \nu N νN个点在边界上或边界外（虽然不理解为啥）
这一块内容西瓜书第12章写的更丰富，当然钥匙书更更丰富。 PAC（Probably approximately correct）学习框架，旨在给出需要多大的数据集，才能有比较好的泛化性能，即以大于等于 1 − δ 1-\delta 1−δ的概率满足 同时给出了计算代价的界。
PAC框架推到的界通常是最坏情况，因为要考虑任意分布 p ( x , t ) p(\bm x,\bm t) p(x,t)，任意假设空间 F \mathcal F F。而现实任务中，我们处理的分布通常有很强的规律性，例如输入空间中大片区域有相同的类别标签。由于缺少关于分布形式的任何假设，所以PAC界非常保守，严格高估了给定泛化性能所需数据集的规模。所以PAC界实际中少用。（那Rademacher复杂度呢，有没有考虑数据分布？）RVM试图模仿SVM的推断方式，即 这和对偶回归是一样的，参考之前的博客：对偶回归（Dual Regression）——CVMLI Prince读书随笔第8、9章 对于 N N N个样本点， M M M维输入特征 和线性回归不同的是，对每个参数，引入不同的先验 α i \alpha_i αi 权重的后验分布满足 均值和方差分别为 其中 Φ ∈ R N × M , A = diag ( α i ) \bm \Phi \in \mathbb R^{N\times M}, \bm A=\text{diag}(\alpha_i) Φ∈RN×M,A=diag(αi) （如果把 k ( x , x n ) k(\bm x,\bm x_n) k(x,xn)看作是关于 x x x的第 n n n个特征，则 Φ = K \bm \Phi=\bm K Φ=K，其中 K \bm K K是核矩阵
α , β \bm \alpha, \beta α,β可以通过类似第三章求线性回归的证据近似得到 线性高斯模型求解后取对数 类似第三章，求导令梯度为0得到（没有验证，第三章的那个我就求不出来。。） 其中 对 α , β \bm \alpha, \beta α,β的优化过程是先初始化，然后计算后验均值和方差，再重新估计 α , β \bm \alpha, \beta α,β，如此迭代进行。EM算法形式上和该方法等价。
优化结束后，许多 α i \alpha_i αi很大，对应参数方差很小，这些参数就可以去掉。这也是RVM的核心思想 。对应的基函数 ϕ i \phi_i ϕi也可以去掉。式子（7.78）中剩下的非零权值就叫做相关向量relevance vectors。
注意这些向量是通过自动相关确定ARD（回顾第六章）得到，类似SVM的支持向量。不过这种方法有一般性，可用于任何表示成基函数的可调线性组合形式的模型。可以在 α , β \bm \alpha,\beta α,β上给两个Gamma先验分布，这样就从求 α \bm \alpha α的MLE变成了MAP。（如果不给Gamma先验，是否可以认为Gamma分布的先验参数 a = b → 0 a=b\to 0 a=b→0. 从而Gamma分布的方差贼大。CVMLI里介绍相关向量是带上先验的，把 w \bm w w的先验搞成了t分布）RVM中模型会对远离基函数的区域，方差变小，这个性质不好（应该是由于很多 ϕ \phi ϕ都变成0了）。高斯过程不会这样，但是高斯过程计算代价大很多RVM的训练复杂度很高，达到了 O ( M 3 ) \mathcal O(M^3) O(M3)，而SVM则不超过 O ( M 2 ) \mathcal O(M^2) O(M2)。但是SVM要手动选超参数，RVM则自动选超参数，ARD选相关feature实践中，RVM生成的模型通常比SVM要简洁一个数量级。并且泛化误差几乎没有减小 贴一张CVMLI的图这里设计了一种更快的计算RVM的方法。在公式（7.85）中考虑单独优化某一个 α i \alpha_i αi，方差 C \bm C C可拆成 利用Woodbury恒等式和行列式的一个性质 从而 其中 L ( α − i ) L(\alpha_{-i}) L(α−i)是剔除 α i \alpha_i αi后剩下的 这里 s i s_i si称之为稀疏度sparisity， q i q_i qi称为 ϕ i \phi_i ϕi的质量quality 稀疏度度量了基函数 ϕ i \phi_i ϕi和其他基函数的重叠程度；质量度量了基函数 ϕ i \phi_i ϕi与误差向量之间的对齐程度，其中误差向量是 t \bm t t和去掉 ϕ i \phi_i ϕi之后预测的 y − 1 \bm y_{-1} y−1之间的差异。 求导得到 如果 q i 2 < s q_i^2<s qi2<s，那么 α i → + ∞ \alpha_i\to +\infty αi→+∞；如果 q i 2 > s q_i^2>s qi2>s，那么 α i = s i 2 q i 2 − s i \alpha_i=\frac{s_i^2}{q_i^2-s_i} αi=qi2−sisi2. 如图所示 可以看出稀疏度和质量共同决定了一个基函数是否要删去。该方法居然能给出解析解。这样可以在不同的候选基函数集合上进行迭代循环。最终算法如下：（这弄得跟自动选特征一样……）
类似回归RVM，不同维度的先验参数 w \bm w w的精确度超参数分开。整个过程是先初始化 α \alpha α，然后用高斯近似后验，从而获得边缘似然的近似，优化 α \alpha α来最大化边缘似然。这个过程迭代至收敛。和第四章相同，后验分布 其中 A = diag ( α i ) \bm A=\text{diag}(\alpha_i) A=diag(αi). 求梯度得到 其中 B = diag ( y n ( 1 − y n ) ) \bm B=\text{diag}(y_n(1-y_n)) B=diag(yn(1−yn)). 则拉普拉斯近似的高斯函数均值和方差为 进一步对归一化常数 p ( t ∣ α ) p(\textbf t|\alpha) p(t∣α)近似（参考第四章），得到（这近似了一个什么分布啊。。。是伯努利分布吗） 上式取对数，对 α i \alpha_i αi求偏导，得到 定义 γ i = 1 − α i ∑ i i \gamma_i=1-\alpha_i\sum_{ii} γi=1−αi∑ii，得到更新式 定义（后三行我没验证了） 则得到 其中 这与回归（7.85）形式相同，可以用同样的稀疏性分析方法快速优化。 结果如图 再给一张CVMLI的图
注意相关向量倾向于不在决策边界，因为决策边界附近的基函数与训练向量 t \bm t t的对齐较差RVM相比于SVM的一个潜在优势是它是概率形式的预测分类RVM可以用softmax的方式扩展到多分类，整体做法类似二分类。但SVM做多分类仍然是一个问题总的来说：RVM的训练时间偏长，但是不像SVM需要手工调超参；另外RVM的解更稀疏参考文献： [1] Christopher M. Bishop. Pattern Recognition and Machine Learning. 2006
