• 1. 支持向量机
  • 1.1. 机器学习的过程
  • 1.2. 优化问题（凸优化问题、二次规划问题）
    • 1.2.1. 二次规划问题
  • 1.3. SVM处理非线性问题
  • 1.4. 低维到高维映射φ(x)
  • 1.5. SVM精髓
  • 1.6. 原问题与对偶问题
  • 1.7. 凸函数
  • 1.8. 将支持向量机的原问题转为对偶问题
  • 1.9. 核函数
  • 1.10. 交叉验证的好处
  • 1.11. ROC曲线
  • 1.12. SVM处理多类问题

1. 支持向量机

支持向量机（苏联Vapnik发明）问题

1. 如何在线性可分样本集上画一条直线将其分开（找到最好的直线）。
2. 如何将非线性可分样本集分开。

线性可分样本集就是一条直线能分开的集合，二者有明显界限。

• 首先要找到一个性能指标，然后根据这个性能指标指出某一条线比其他线指标高。

• 将一条线平行地向一侧移动，直到叉到某一个样本为止，然后平行地向另一侧移动，也是叉到某一个样本为止。这个性能指标就是两条平行线的距离。这个距离最大的一条线就是最佳的。同时两条平行线的最中间是唯一的。

• 将平行线间的距离称为d(margin)，支持向量机是最大化平行线距离d(margin)的方法。

• 将平行线叉到的向量称为支持向量，画出这条线的方法只跟支持向量有关系，跟其他向量没关系，这也是为什么支持向量能够用在小样本集上。

1. 定义训练数据和标签：(X1,y1)、(X2, y2)...(Xn, yn)，其中X = [x1, x2 ..]，是多维向量，y是+1或-1的标签。
2. 线性模型 (W, b) => W^TX+ b = 0，描述超平面的线性方程。W是一个向量，如果X是n维的，那么W也是n维的。b是一个常数。W^TX 一个列向量转置然后乘以一个行向量，也是一个数。
3. 线性可分的定义。存在(W，b)，使 y_i =+1 时，W^TX + b >= 0；y_i = -1时，W^TX + b < 0。即 y_i[W^TX_i + b] >= 0（公式一）

1.1. 机器学习的过程

1. 确定一个方程；
2. 确定一些要求取的参数，比如这里的W和B；
3. 训练模型，求出参数

1.2. 优化问题（凸优化问题、二次规划问题）

1. 最小化minimize： ||W||², 即 W 模的平方。
2. 限制条件Subject to：y_i[W^TX_i+ b] >= 1，其中 i = 1~N

如何从最大化margin转化到上面的两个问题？

事实1. W^TX + b = 0 与 aW^TX + ab = 0 是同一个平面，其中 a 是一个正实数。也就是若(W, b)满足公式一，那么（aW, ab）也满足公式一，a是负数的话符号就相反了。 事实2. 点 (x₀, y₀) 到平面（w₁x + w₂y + b = 0）的最短距离：d = |w₁x₀ + w₂y₀ + b| / √(w₁² + w₂²)

那么高维上，向量 X₀ 到超平面 W^TX + b = 0的距离，就是：|W^TX₀+ b|/ || W ||，其中分母 W 的模就是 √(w₁² + w₂² + w₃² ...)

那么，

1. 我们可以用 a 缩放（W，b）得到（aW, ab），最终使所有支持向量 X₀ 上，有 |W^TX₀ + b| = 1 ，那么非支持向量上，|W^TX₀+ b| >1，从而得证限制条件；
2. 此时支持向量与平面的距离 d = 1/|| W ||，从而最小化 || W || 可以使 d 最大，得证最小化条件

注意：

1. 限制条件最后的1可以是2、3、4...等任意整数，它们的区别只是一个常数a。
2. 只要线性可分，一定存在 W 和 b，反之如果线性不可分，找不到 W 和 b 满足限制条件

1.2.1. 二次规划问题

1. 目标函数是二次项，限制条件是一次项。
2. 要么无解，要么只有一个极值。

支持向量机效果好，是因为数学理论漂亮，漂亮在转化为了一个凸优化问题，这类问题在全局上有一个最优解。

1.3. SVM处理非线性问题

优化问题：

1. 最小化 ||W||² / 2 + C∑ε_i
2. 限制条件
   • y_i[W^TX_i + b] >= 1 - ε_i
   • ε_i >= 0 ，其中 i = 1~N

理解：

1. 有上面知道非线性情况下，找不到满足 y_i[W^TX_i + b] >= 1 的（W，b）；
2. 因此，放宽条件，当 ε_i 很大的时候，1-ε_i 很小，就能满足限制条件；
3. 同时又不能让 ε_i 很大，否则问题会很发散，所以把它又放在最小化里面。
4. ε_i 称为松弛变量，slack variable.

所以，已知条件有X_i、Y_i，即训练样本，要求的有 W、b、ε_i

• C∑ε_i被称为正则项，regulation term，C 的作用是平衡每一项 ε_i，使它们都不要太大。
• C 是事先设定的参数，起到平衡前后两项的作用。通常没有固定的值，一般根据经验在某个范围内去一个个试。

为什么要加正则项？

1. 以前没有解，要使其有解，就需要加正则项。
2. 目标函数有解，但其解并不想要的，比如目标函数凹凸不平，也需要加正则项。

1.4. 低维到高维映射φ(x)

问题：之前的解都是求解直线，但如果最优解其实是圆形怎么办？比如一堆1包围了0。

vapnik一个创意的想法是，不在低维的空间找圆形、椭圆等其他形状，而是在高维的空间还是找直线。x => φ(x)

举例：x1(0, 0)和x2(1,1)属于第一类，x3(1, 0)和x4(0, 1)属于第二类。一个映射方案是[a,b] =>[a², b², a, b, ab]

那么 x1: [0, 0] => [0, 0, 0, 0, 0] x2: [1, 1] => [1, 1, 1, 1, 1] x3: [1, 0] => [1, 0, 1, 0, 0] x4: [0, 1] => [0, 1, 0, 1, 0] (转置)

如何求解 W 和 b ？ 一个解是：W = [-1，-1，-1，-1, 6]，b = 1

维度越高，被线性分开的可能性越高，如果是无限维，被线性分开的概率为1。

1.5. SVM精髓

我们可以不知道无限维映射 φ(x) 的显式表达，我们只要知道一个核函数 kernal function，K(x1, x2) = φ(x1)^Tφ(x2)，那么 ||W||²/2 + C∑ε_i 这个优化式仍然可解。

φ(x1)^Tφ(x2) 是两个无限维向量的内积，就是一个数，也就是不需要 φ(x) 的具体表达式，只要知道核函数就行了。

常见的核函数有高斯核和多项式核函数等，具体公式见下文。

核函数 K(x1, x2) 能写成 φ(x1)^Tφ(x2)的充要条件是（Mercer's Theorem）：

1. 满足交换律 K(x1, x2) = K(x2, x1)
2. 半正定性，对于所有的 C_i 和 X_i， 有 ∑_i∑_jC_iC_jK(X_i, Y_i) >= 0。其中 C_i 是常数，X_i 是向量。

1.6. 原问题与对偶问题

原问题Prime Problem：

1. 最小化 f(ω)
2. 限制条件
   • g_i(ω) <= 0，其中 i = 1~K；
   • h_i(ω) = 0，其中 i = 1~M

原问题非常普适，最小化可以转为最大化问题，限制条件大于等于可以转为小于等于，后面的 h(ω) = 0 可以转为 h(ω) - C = 0。

对偶问题Dual Problem：

先定义函数：L(ω, α, β) = f(ω) + ∑_iα_ig_i(ω) + ∑_iβ_ih_i(ω) = f(ω) + α^Tg(ω) + β^Th(ω)，其中后面的形式是向量的形式。

对偶问题定义：

1. 最大化 θ(α, β) = inf_所有ω( L(ω, α, β) )，
2. α_i >= 0，其中 i = 1~K

inf 指求括号内的最小值，即在限定了 α 和 β ，去遍历所有的 ω，求 L 的最小值。所以每确定一个 α 和 β，都能算出一个最小值，θ(α, β)只和 α, β 有关。然后再针对所有的 α, β，再求 θ 的最大值。里面求最小，外面求最大。

定理：如果ω*是原问题的解，而α*, β*是对偶问题的解，则有f(ω*) >= θ(α*, β*)

证明：θ(α*, β*) = inf_所有ω( L(ω, α*, β*) ) <= L(ω*, α*, β*) = f(ω*) + ∑_iα*_ig_i(ω*) + ∑_iβ*_ih_i(ω*) . 其中 h_i(ω*) = 0，g_i(ω*) <= 0，α*_i >= 0，得证。

定义：G = f(ω*) - θ(α*, β*) >= 0，G叫做原问题与对偶问题的间距（Duality Gap）。对于某些特定的优化问题，可以证明 G 等于0。

强对偶定理：若 f(ω) 为凸函数， g(ω) = aω+b，h(ω）=cω+d，则此优化问题的原问题与对偶问题间距为0。即 f(ω*) = θ(α*, β*) => 对于所有的 i = 1 - K，α*_i = 0 或者 g_i(ω*) = 0

1.7. 凸函数

凸函数：如果在函数图像上任取两点，函数图像在这两点之间的部分都在两点线段的下边，那么就成为凸函数，否则称为凹函数。凸函数只有一个极小值，比如 x²，而 sinx 有多个极值。

对于任意（0,1）中有理数 λ，有

如果 f 连续，那么 λ 可以改变成区间（0,1）中的任意实数。

几何意义只是一维的，而代数的定义可以是向量，即任意维。

1.8. 将支持向量机的原问题转为对偶问题

注意转化后的对偶问题中的 β_i 和 α_i 对应着原来对偶问题的一个 α_i，因为 g_i(ω) <= 0，而支持向量机的不等式的限制条件有两个，所以都写上了。

对向量求偏导，就是对其每个分量求偏导。

W^TW，蹦出来个 α_j，只是个符号，因为写 α_i 不合适了

对于上面的推倒后的式子，已知的是所有的 y，和 kernal 函数，未知的是所有的 α。怎么把求 α 转化为求 W 和 b？根据上面 W 的公式就可以。

KKT条件对应到SVM上：

SVM算法流程分为训练流程和测试流程，训练时，先求出所有的α，再算b

可见所有的 φ(x) 都转成了 kernel 函数

1.9. 核函数

线性核等于没用，解原问题和解对偶问题的复杂度一样。多项式核函数d是几维，就对应到几维。高斯核是低维映射到高维。

每个核函数都要调参数，多项式核函数要调的参数是d，高斯核要调的是方差。

SVM训练时的一个经验是，必须归一化，一般用高斯归一化，即减掉均值，然后除以平均值，而不是最小最大归一化。

SVM 用高斯核的话，只有两个参数要调，一个是 C 平衡前面的 W 和后面的 ε_i，另一个是高斯核中的方差。

C范围：2^-5~15，方差范围：2^-15~23，组合有21*19种

1.10. 交叉验证的好处

• 不使用训练样本进行测试，因为无法验出真实水平。
• 尽可能地充分利用训练样本，比如只有5000个样本，分成abcde五组，每次取出4份进行训练，另一份进行测试，保证每一次训练时，样本足够的多。

折数越多，训练模型越多，10折就是10个模型，5折就是训练5次。5000个样本，最多5000折，每次取4999个进行训练，1个进行测试。这种称为leave-one-out cross validation

支持向量20%左右正常，如果特别多，说明没有训练好，或者数据本身就没有规律。

1.11. ROC曲线

为什么同一个系统中TP增加，FP也增加？小平同志说，改革开放了，好的东西进来了，蚊子苍蝇也进来了。因为自身性能不变，把更多的正例识别成正例，那么一定也会将更多的反例识别为正例。同理FN增加=>TN增加。

ROC (Receiver Operating Character)曲线， 是一条横坐标 FP，纵坐标 TP 的曲线

给定一个模型，怎么画出ROC曲线？从小到大变换下面的阈值，每次变换一个阈值，测出 TP 和 FP。FP 等于0时，表示把所有的样本判为负例，此时 TP 也为0，FP 等于1表示把所有的样本判为正例。

等错误率 (Equal Error Rate, EER)是两类错误 FP 和 FN 相等时候的错误率，可以直观的表示系统性能。

对于不同的应用，判别模型好坏的标准不同。对于人脸开锁的应用而言，容忍错误低，即要 FP 最小，或者是0情况下，FP 的最大值。

ROC 下的面积称为 AUC，面积越大，一般性能越好。

可以用 ROC 曲线、EER、AUC，但不要单纯用识别率来判断，识别率高不代表性能就好（这是机器学习领域懂和不懂的人的一个区别）。

1.12. SVM处理多类问题

1. 改造优化的目标函数和限制条件，使之能处理多类。论文 SVM-Multiclass Multi-class Support Vector Machine
2. 一类 VS 其他类
3. 一类 VS 另一类

一类 VS 其他类：

如果一个样本被判为 C1 或 C2，那就看哪一个负的多，因为 y = -1，说明...是负的，看更偏向于谁。

一类 VS 另一类：

根据经验，改造公式的方法并不好用，因为SVM适合在两类中寻找最大间隔。

如果有 N 类，一类VS其他类的方法要做 N 个 SVM 模型，一类VS另一类要做 (N*(N-1))/2 个SVM模型。根据经验，后者更佳。