# 支持向量机

## 第6章 支持向量机

* Page121: 划分超平面

  超平面是将N维空间分成两个闭半空间的N-1维的仿射空间。划分超平面则是把两类数据集样本划分开来的超平面。
* Page122: 支持向量

  支持平面上把两类划分开来的超平面的向量点，即距离超平面最近的几个训练样本点。
* Page122: 间隔

  两个异类支持向量到超平面的距离之和为间隔，$$\gamma = \frac{2}{\parallel \omega \parallel }$$.
* Page123: SVM

  $$\min\_{\omega,b} \frac{1}{2}\parallel \omega \parallel ^{2}$$ s.t. $$y\_i(\omega ^{T}x\_i+b)\geqslant 1, i=1,2,...,m$$
* Page123: 对偶问题(405)(dual problem)

  在求最小值的原问题里，其对偶问题提供了一个下界(lower bound)。
* Page124: KKT条件(124,132,135)(Karush-Kuhn-Tucker)
  * $$\alpha \_i\geqslant 1$$
  * $$y\_i f(x\_i)-1\geqslant 0$$
  * $$\alpha \_i(y\_if(x\_i)-1)=0$$ - Page126: 核函数

    可以看成是一种映射，不仅可以是点对点的映射，还可以是一个分布对点的映射。
* Page127: 核技巧(kernel trick)

  $$x\_i$$与$$x\_j$$在特征空间的内积等于它们在原始样本空间中通过函数κ(·,·)计算的结果。
* Page127: 支持向量展式

  模型最优解课通过训练样本的核函数展开。
* Page128: 核矩阵(138,233)

  $$K=\begin{bmatrix}\kappa(x\_1,y\_1) & \cdots\ & \kappa(x\_1,y\_j) & \cdots\ &\kappa(x\_1,y\_m)\ \vdots & \ddots & \vdots & \ddots & \vdots \ \kappa(x\_i,y\_1) & \cdots\ & \kappa(x\_i,y\_j) & \cdots\ & \kappa(x\_i,y\_m)\ \vdots & \ddots & \vdots & \ddots & \vdots \ \kappa(x\_m,y\_1) & \cdots\ & \kappa(x\_m,y\_j) & \cdots\ & \kappa(x\_m,y\_m)\ \end{bmatrix}$$ 形为这样的核函数，可以将低维空间映射为高维空间，将原来线性不可分的分布转化为线性可分的分布。核函数可以表示高维空间的内积。 此外，核函数必须满足对称性和矩阵半正定。
* Page128: RKHS

  非线性映射ϕ，它将原始特征空间中的数据点映射到另一个高维空间中，这个高维空间称为再生核希尔伯特空间(Reproducing Kernel Hilbert Space)，简称RKHS。
* Page128: 高斯核

  高斯核函数是最常用的径向基函数。
* Page128: 线性核

  线性核函数是$$\kappa(x\_i,y\_i)=x\_i^Tx\_j$$；多项式核是$$\kappa(x\_i,y\_i)=(x\_i^Tx\_j)^d$$，即d为1时退化为线性核。
* Page129: 软间隔

  允许支持向量机在一些样本上出错，即允许某些样本不满足约束。
* Page129: 硬间隔

  要求所有样本均满足约束，即所有样本都划分正确。
* Page130: 0/1损失函数(page147)

  $$ l\_{0/1}(z) = \left{ \begin{array}{rl} 1, &\mbox{ if $z<0$} \ 0, &\mbox{ otherwise} \end{array} \right. $$
* Page130: 替代损失

  0/1损失函数不易直接求解（非连续，不是convex），所以通常会用其他函数来替代求解，也叫替代损失。
* Page130: hinge损失

  $$l\_{hinge}(z)=\max(0,1-z)$$，采用hinge损失函数，则优化目标变成$$\min\_{w,b}\frac{1}{2}||w||^2+C\sum\_{i=1}^{m}max(0,1-y\_i(w^Tx\_i+b))$$
* Page130: 指数损失(173)

  $$l\_{exp}(z)=\exp(-z)$$
* Page130: 对率损失

  $$l\_{log}(z)=\log(1+\exp(-z))$$
* Page130: 松弛变量

  松弛变量，即slack variables$$\xi\_i$$
* Page131: 软间隔支持向量机

  引入了松弛变量$$\xi\_i$$，式子可重写为：

  $$\begin{align\*}& \min\_{w,b}\frac{1}{2}||w||^2+C\sum\_{i=1}^{m}max(0,1-y\_i(w^Tx\_i+b))\\& \begin{array}{r@{\quad}r@{}l@{\quad}l}s.t.\&yi(w^Tx\_i+b)\geq1-\xi\_i\ &\xi\_i\geq0, i=1,2\ldots,m \\\end{array} .\end{align\*}$$
* Page133: 结构风险

  描述模型f的性质，$$\Omega(f)$$.
* Page133: 经验风险

  描述模型和训练数据的契合程度，可以理解为误差。
* Page133: 罚函数法

  正则化。对不希望得到的结果施以惩罚，从而使得优化过程趋向于希望目标。
* Page133: 支持向量回归

  Support Vector Regression(SVR)其实是对误差的计算加了一个误差容忍值epsilon（即$$\epsilon$$），即落入这个$$\epsilon$$误差范围内的不计入误差和中。
* Page137: 核方法

  这一系列基于核函数的学习方法统称为核方法。最常见的是将线性学习器拓展为非线性学习器。如把线性不可分的低维分布通过方法转成线性可分的高维分布。
* Page137: Mercer定理

  任何半正定的函数都可以作为核函数。
* Page137: 表示定理

  优化问题的解总可用核函数表示。
* Page137: 核化(232)

  引入核函数来解决问题。
* Page137: 核线性判别分析

  Kernelized Linear Discriminant Analysis(KLDA)是指引入核函数进行线性判别分析。
* Page139: 割平面法

  Cutting plane algorithm是求全整数规划的一种方法，先松弛求得最优解，再逐步把不符合整数可行解的那一部分可行域通过平面（不等式分割）划分掉。
* Page140: 多核学习

  使用多个核函数，学习后获得最优凸组合。
* Page140: 一致性

  相合性。即考虑通过求解替代损失函数得到的解释是否是原问题的解。