AI 科技谈论按,本文为韦易笑在知乎问题怎样学习SVM(支撑向量机)以及改善完结SVM算法程序下面的回复,AI 科技谈论获其授权转载。

韦易笑知乎网址:

https://www.zhihu.com/people/skywind3000/activities

知乎问题:

https://www.zhihu.com/question/31211585/answer/640501555

以下为正文:

学习 SVM 的最好办法是完结一个 SVM,可讲理论的许多,讲完结的太少了。

假定你现已读懂了 SVM 的原理,并了解公式怎样推导出来的,比方到这儿:

SVM 的问题就变成:求解一系列满意束缚的 alpha 值,使得上面那个函数能够取到最小值。然后记录下这些非零的 alpha 值和对应样本中的 x 值和 y 值,就完结学习了,然后猜测的时分用:

上面的公式核算出 f(x) ,假如返回值 > 0 那么是 +1 类别,否则是 -1 类别,先把这一步怎样来的,为什么这么来找篇文章读懂,否则你会做的一头雾水。

那么剩余的 SVM 完结问题便是怎样求解这个函数的极值。办法有许多,咱们先找个起点,比方 Platt 的SMO算法(https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-98-14.pdf),它后边有伪代码描绘怎样快速求解 SVM 的各个系数。

第一步:完结传统的 SMO 算法

现在大部分的 SVM 开源完结,源头都是 platt 的 smo 算法,读完他的文章和推导,然后照着伪代码写就行了,中心代码没几行:

target = desired output vector

point = training point matrix

procedure takeStep(i1,i2)

if (i1 == i2) return 0

alph1 = Lagrange multiplier for i1

y1 = target[i1]

E1 = SVM output on point[i1] – y1 (check in error cache)

s = y1*y2

Compute L, H via equations (13) and (14)

if (L == H)

return 0

k11 = kernel(point[i1],point[i1])

k12 = kernel(point[i1],point[i2])

k22 = kernel(point[i2],point[i2])

eta = k11+k22-2*k12

if (eta > 0)

{

a2 = alph2 + y2*(E1-E2)/eta

if (a2 < L) a2 = L

else if (a2 > H) a2 = H

}

else

{

Lobj = objective function at a2=L

Hobj = objective function at a2=H

if (Lobj < Hobj-eps)

a2 = L

else if (Lobj > Hobj+eps)

a2 = H

else

a2 = alph2

}

if (|a2-alph2| < eps*(a2+alph2+eps))

return 0

a1 = alph1+s*(alph2-a2)

Update threshold to reflect change in Lagrange multipliers

Update weight vector to reflect change in a1 & a2, if SVM is linear

Update error cache using new Lagrange multipliers

Store a1 in the alpha array

Store a2 in the alpha array

return 1

endprocedure

中心代码很紧凑,便是给定两个 ai, aj,然后迭代出新的 ai, aj 出来,还有一层循环会不断的挑选最需求被优化的系数 ai, aj,然后调用这个函数。怎样更新权重和 b 变量(threshold)文章里边都有说,再多调试一下,能够用 python 先调试,再换成 C/C++,确保得到一个正确可用的 SVM 程序,这是后边的根底。

第二步:完结核函数缓存

调查下上面的伪代码,开支最大的便是核算核函数 K(xi, xj),有些核算又重复用到,一个 100 个样本的数据集求解,假定总共要调用核函数 20 万次,可是 xi, xj 的组和只要 100x100=1 万种,有缓存的话你的功率能够进步 20 倍。

样本太大时,假如你想存储一切核函数的组和,需求 N*N * sizeof(double) 的空间,假如练习集有 10 万个样本,那么需求 76 GB 的内存,显然是不或许完结的,所以核函数缓存是一个有限空间的 LRU 缓存,SVM 的 SMO 求解过程中其实会重复用到特定的几个有限的核函数求解,所以命中率不必忧虑。

有了这个核函数缓存,你的 SVM 求解程序能瞬间快几十倍。

第三步:优化差错值求解

留意看上面的伪代码,里边需求核算一个估计值和实在值的差错 Ei 和 Ej,他们的求解办法是:

E(i) = f(xi) - yi

这便是目前为止 SMO 这段为代码里价值最高的函数,因为回忆下上面的公式,核算一遍 f(x) 需求 for 循环做乘法加法。

platt 的文章主张是做一个 E 函数的缓存,便利后边挑选 i, j 时比较,我看到许多入门版别 SVM 完结都是这么做。其实这是有问题的,后边咱们会说到。最好的办法是界说一个 g(x) 令其等于:

也便是 f(x) 公式除了 b 以外前面的最费时的核算,那么咱们随时能够核算差错:

E(j) = g(xj) + b - yj

所以最好的办法是对 g(x) 进行缓存,platt 的办法里因为一切 alpha 值初始化成了 0,所以 g(x) 一开始就能够悉数设置成 0,略微调查一下 g(x) 的公式,你就会发现,因为去掉了 b 的搅扰,而每次 SMO 迭代更新 ai, aj 参数时,这两个值都是线性改变的,所以咱们能够给 g(x) 求关于 a 的偏导,假定 ai,aj 改变了步长 delta,那么一切样本对应的 g(x) 加上 delta 乘以针对 ai, aj 的偏导数就行了,详细代码相似:

double Kik = kernel(i, k);

double Kjk = kernel(j, k);

G[k] += delta_alpha_i * Kik * y[i] + delta_alpha_j * Kjk * y[j];

把这段代码放在 takeStep 后边,每次成功更新一对 ai, aj 今后,更新一切样本对应的 g(x) 缓存,这样经过每次迭代更新 g(x) 避免了许多的重复核算。

这其实是很直白的一种优化办法,我查了一下,有人专门发论文就讲了个相似的办法。

第四步:完结冷热数据别离

Platt 的文章里也证明过一旦某个 alpha 出于鸿沟(0 或许 C)的时分,就很不容易变化,而且伪代码也是优先在作业集里寻觅 > 0 and < C 的 alpha 值进行优化,找不到了,再对作业集全体的 alpha 值进行迭代。

那么咱们必然就能够把作业集分红两个部分,热数据在前(大于 0 小于 C 的 alpha 值),冷数据在后(小于等于 0 或许大于等于 C 的 alpha)。

跟着迭代加深,会发现大部分时分只需求在热数据里求解,而且热数据的大小会逐渐不断的缩短,所以区分了冷热今后 SVM 大部分都在针对有限的热数据迭代,偶然不行了,再悉数迭代一次,然后又回到冷热迭代,功能又能进步不少。

第五步:支撑 Ensemble

咱们都知道,经过 Ensemble 能够让多个不同的弱模型组和成一个强模型,而传统 SVM 完结并不能习惯一些相似 AdaBoost 的集成办法,所以咱们需求做一些改动。能够让外面针对某一个分类传入一个“权重”过来,批改 SVM 的辨认成果。

最传统的修正办法便是将不等式束缚 C 分为 Cp 和 Cn 两个针对 +1 分类的 C 及针对 -1 分类的 C。修正办法是直接用原始的 C 乘以各自分类的权重,得到 Cp 和 Cn,然后迭代时,不同的样本依据它的 y 值符号,用不同的 C 值带入核算。

这样 SVM 就能用各种集成办法同其他模型一同组成更为强壮精准的模型了。

完结到这一步你就得到了功能上和功能上同 libsvm 相似的东西,接下来咱们持续优化。

第六步:持续优化核函数核算

核函数缓存十分耗费内存,libsvm 数学上现已没得挑了,可是工程方面还有很大改善地步,比方它的核缓存完结。

因为规范 SVM 核函数用的是两个高维矢量的内积,依据内积的几个条件,SVM 的核函数又是一个正定核,即 K(xi, xj) = K(xj, xi),那么咱们相同的内存还能再多存一倍的核函数,功能又能有所进步。

针对核函数的核算和存储有许多优化办法,比方有人对 NxN 的核函数矩阵进行采样,只核算有限的几个核函数,然后经过插值的办法求解出中心的值。还有人用 float 存储核函数值,又降低了一倍空间需求。

第七步:支撑稀少向量和非稀少向量

关于高维样本,比方文字这些,或许有上千维,每个样本的非零特征或许就那么几个,所以稀少向量会比较高效,libsvm 也是用的稀少向量。

可是还有许多时分样本是密布向量,比方总共 200 个特征,大部分样本都有 100个以上的非零特征,用稀少向量存储的话就十分低效了,openCV 的 SVM 完结便对错稀少向量。

非稀少向量直接是用数组保存样本每个特征的值,在工程方面就有许多优化办法了,比方用的最多的求核函数的时分,直接上 SIMD 指令或许 CUDA,就能取得更好的核算功能。

所以最好的办法是一起支撑稀少和非稀少,统筹时刻和空间功率,对不同的数据挑选最合适的办法。

第八步:针对线性核进行优化

传统的 SMO 办法,是 SVM 的通用求解办法,可是针对线性核,便是:

K(xi, xj) = xi . xj

还有许多更高效的求解思路,比方 Pegasos 算法就用了一种相似随机梯度下降的办法,快速求 SVM 的解权重 w,假如你的样本合适线性核,运用一些针对性的非 SMO 算法能够极大的优化 SVM 求解,而且能处理愈加巨大的数据集,LIBLINEAR 便是做这件工作的。

一起这类算法也合适 online 练习和并行练习,能够逐渐更新增量练习新的样本,还能够用到多核和分布式核算来练习模型,这是 SMO 算法做不到的当地。

可是假如碰到非线性核,权重 w 处于高维核空间里(有或许无限维),你无法梯度下降迭代 w,而且 pegasos 的 pdf 里边也没有说到怎样用到非线性核上,LIBLINEAR 也没有办法处理非线性核。

或许哪天出个数学家又找到一种更好的办法,能够用相似 pegasos 的办法求解非线性核,那么 SVM 就能有比较大的发展了。

后话

上面八条,你假如完结前三条,根本就能深化了解 SVM 的原理了,假如完结一大半,就能够得到一个相似 libsvm 的东西,悉数完结,你就能得到一个比 libsvm 更好用的 SVM 库了。

上面便是怎样完结一个相对老练的 SVM 模型的思路,以及配套优化办法,再往后还有爱好,能够接着完结支撑向量回归,也是一个很有用的东西。

声明:该文观念仅代表作者自己,搜狐号系信息发布渠道,搜狐仅供给信息存储空间服务。

推荐阅读