机器学习算法实践-Platt SMO和遗传算法优化SVM

rustum · 发表于 2021-12-23 11:57

前言

之前实现了简单的SMO算法来优化SVM的对偶问题，其中在选取的时候使用的是两重循环通过完全随机的方式选取，具体的实现参考《机器学习算法实践-SVM中的SMO算法》。
本文在之前简化版SMO算法的基础上实现了使用启发式选取对的方式的Platt SMO算法来优化SVM。另外由于最近自己也实现了一个遗传算法框架GAFT，便也尝试使用遗传算法对于SVM的原始形式进行了优化。

对于本文算法的相应实现，参考:https://github.com/PytLab/MLBox/tree/master/svm
遗传算法框架GAFT项目地址: https://github.com/PytLab/gaft

正文

SMO中启发式选择变量

在SMO算法中，我们每次需要选取一对  来进行优化，通过启发式的选取我们可以更高效的选取待优化的变量使得目标函数下降的最快。
针对第一个  和第二个 Platt SMO采取不同的启发式手段。
第一个变量的选择

第一个变量的选择为外循环，与之前便利整个  列表不同，在这里我们在整个样本集和非边界样本集间进行交替:

首先我们对整个训练集进行遍历, 检查是否违反KKT条件，如果改点的 $\alpha_i$ 和 $x_1$ , $y_i$ 违反了KKT条件则说明改点需要进行优化。
Karush-Kuhn-Tucker(KKT)条件是正定二次规划问题最优点的充分必要条件。针对SVM对偶问题，KKT条件非常简单: $\begin{cases} \alpha_i = 0 \Longleftrightarrow y_i(w^{T}x_i + b) \ge 1 \\ \alpha_i = C \Longleftrightarrow y_i(w^{T}x_i + b) \le 1 \\ 0 < \alpha_i < C \Longleftrightarrow y_i(w^{T}x_i + b) = 1 \end{cases}$
在遍历了整个训练集并优化了相应的αα后第二轮迭代我们仅仅需要遍历其中的非边界αα. 所谓的非边界就是指那些不等于边界0或者C的值。同样这些点仍然需要检查是否违反KKT条件并进行优化.

之后就是不断地在两个数据集中来回交替，最终所有的  都满足KKT条件的时候，算法中止。
为了能够快速选取有最大步长的  ，我们需要对所有数据对应的误差进行缓存，因此特地写了个SVMUtil类来保存svm中重要的变量以及一些辅助方法:
class SVMUtil(object):
&#39;&#39;&#39;
Struct to save all important values in SVM.
&#39;&#39;&#39;
def __init__(self, dataset, labels, C, tolerance=0.001):
      self.dataset, self.labels, self.C = dataset, labels, C
      self.m, self.n = np.array(dataset).shape
      self.alphas = np.zeros(self.m)
      self.b = 0
      self.tolerance = tolerance
      # Cached errors ,f(x_i) - y_i
      self.errors = [self.get_error(i) for i in range(self.m)]
# 其他方法...
...下面为第一个变量选择交替遍历的大致代码，相应完整的Python实现(完整实现见https://github.com/PytLab/MLBox/blob/master/svm/svm_platt_smo.py):
while (it < max_iter):
pair_changed = 0
if entire:
      for i in range(svm_util.m):
         pair_changed += examine_example(i, svm_util)
         print(&#39;Full set - iter: {}, pair changed: {}&#39;.format(i, pair_changed))
else:
      alphas = svm_util.alphas
      non_bound_indices = [i for i in range(svm_util.m)
                           if alphas > 0 and alphas < C]
      for i in non_bound_indices:
         pair_changed += examine_example(i, svm_util)
...
...第二个变量的选择

SMO中的第二个变量的选择过程为内循环，当我们已经选取第一个  之后，我们希望我们选取的第二个变量  优化后能有较大的变化。根据我们之前推导的式子 $\alpha_{2}^{new, unclipped} = \alpha_{2}^{old} + \frac{y_{2}(E_{1} - E_{2})}{\eta}$ 可以知道，新的  的变化依赖于  , 当 $E_1$ 为正时，那么选择最小的  作为 $E_2$ ，通常将每个样本的  缓存到一个列表中，通过在列表中选择具有  的  来近似最大化步长。
有时候按照上述的启发式方式仍不能够是的函数值有足够的下降，这是按下述步骤进行选择:

在非边界数据集上选择能够使函数值足够下降的样本作为第二个变量

如果非边界数据集上没有，则在整个数据仅上进行第二个变量的选择

如果仍然没有则重新选择第一个

第二个变量选取的Python实现:
def select_j(i, svm_util):
&#39;&#39;&#39; 通过最大化步长的方式来获取第二个alpha值的索引.
&#39;&#39;&#39;
errors = svm_util.errors
valid_indices = [i for i, a in enumerate(svm_util.alphas) if 0 < a < svm_util.C]
if len(valid_indices) > 1:
      j = -1
      max_delta = 0
      for k in valid_indices:
         if k == i:
            continue
         delta = abs(errors - errors[j])
         if delta > max_delta:
            j = k
            max_delta = delta
else:
      j = select_j_rand(i, svm_util.m)
return jKKT条件允许一定的误差

在Platt论文中的KKT条件的判断中有一个tolerance允许一定的误差，相应的Python实现：
r = E_i*y_i
# 是否违反KKT条件
if (r < -tolerance and alpha < C) or (r > tolerance and alpha > 0):
...关于Platt SMO的完整实现详见:
https://github.com/PytLab/MLBox/blob/master/support_vector_machine/svm_platt_smo.py
针对之前的数据集我们使用Platt SMO进行优化可以得到：
w = [0.8289668843516077, -0.26578914269411114]
b = -3.9292583040559448将分割线和支持向量可视化：

可见通过Platt SMO优化出来的支持向量与简化版的SMO算法有些许不同。
使用遗传算法优化SVM

由于最近自己写了个遗传算法框架，遗传算法作为一个启发式无导型的搜索算法非常易用，于是我就尝试使用遗传算法来优化SVM。
使用遗传算法优化，我们就可以直接优化SVM的最初形式了也就是最直观的形式:

$arg \max \limits_{w, b} \{ \min \limits_{n} (y_{i} \cdot (w^{T}x + b)) \cdot \frac{1}{\lVert w \rVert} \}$
顺便再安利下自己的遗传算法框架，在此框架的帮助下，优化SVM算法我们只需要写几十行的Python代码即可。其中最主要的就是编写适应度函数，根据上面的公式我们需要计算数据集中每个点到分割线的距离并返回最小的距离即可，然后放到遗传算法中进行进化迭代。
遗传算法框架GAFT项目地址: https://github.com/PytLab/gaft , 使用方法详见README。
Ok，我们开始构建种群用于进化迭代。
创建个体与种群

对于二维数据点，我们需要优化的参数只有三个也就是 $[w_1, w_2]$ 和 $b$ , 个体的定义如下:
indv_template = GAIndividual(ranges=[(-2, 2), (-2, 2), (-5, 5)],
                           encoding=&#39;binary&#39;,
                           eps=[0.001, 0.001, 0.005])种群大小这里取600，创建种群
population = GAPopulation(indv_template=indv_template, size=600).init()创建遗传算子和GA引擎

这里没有什么特别的，直接使用框架中内置的算子就好了。
selection = RouletteWheelSelection()
crossover = UniformCrossover(pc=0.8, pe=0.5)
mutation = FlipBitBigMutation(pm=0.1, pbm=0.55, alpha=0.6)
engine = GAEngine(population=population, selection=selection,
               crossover=crossover, mutation=mutation,
               analysis=[ConsoleOutput, FitnessStore])适应度函数

这一部分只要把上面svm初始形式描述出来就好了，只需要三行代码:
@engine.fitness_register
def fitness(indv):
w, b = indv.variants[: -1], indv.variants[-1]
min_dis = min([y*(np.dot(w, x) + b) for x, y in zip(dataset, labels)])
return float(min_dis)开始迭代

这里迭代300代种群
if &#39;__main__&#39; == __name__:
engine.run(300)绘制遗传算法优化的分割线

variants = engine.population.best_indv(engine.fitness).variants
w = variants[: -1]
b = variants[-1]
# 分类数据点
classified_pts = {&#39;+1&#39;: [], &#39;-1&#39;: []}
for point, label in zip(dataset, labels):
if label == 1.0:
      classified_pts[&#39;+1&#39;].append(point)
else:
      classified_pts[&#39;-1&#39;].append(point)
fig = plt.figure()
ax = fig.add_subplot(111)
# 绘制数据点
for label, pts in classified_pts.items():
pts = np.array(pts)
ax.scatter(pts[:, 0], pts[:, 1], label=label)
# 绘制分割线
x1, _ = max(dataset, key=lambda x: x[0])
x2, _ = min(dataset, key=lambda x: x[0])
a1, a2 = w
y1, y2 = (-b - a1*x1)/a2, (-b - a1*x2)/a2
ax.plot([x1, x2], [y1, y2])
plt.show()得到的分割曲线如下图：

完整的代码详见: https://github.com/PytLab/MLBox/blob/master/support_vector_machine/svm_ga.py
总结

本文对SVM的优化进行了介绍，主要实现了Platt SMO算法优化SVM模型，并尝试使用遗传算法框架GAFT对初始SVM进行了优化。
参考

Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines

zifa2003293 · 发表于 2021-12-23 12:07

这些都是博主从零开始手动写的吗，还是会参考一些其他代码？

jquave · 发表于 2021-12-23 12:07

代码都是自己写的，但是参考过其他书上的代码

RhinoFreak · 发表于 2021-12-23 12:12

dalao，关于文中提到的那些优化理论你是怎么学的？有没有什么推荐？

super1 · 发表于 2021-12-23 12:12

优化理论之前在学校上过一些基础课程，后面好久不用也会忘，再拿出来看一下很快就能回忆起来了

super1 · 发表于 2021-12-23 12:15

你好，请问效果如何？之前我把smo换成pso效率低了好多，特别是训练样例多了以后，感觉ga可能也有这种问题？还有想请问下优化问题中的约束是如何怎么处理的？感觉直接用ga约束不太好处理

franciscochonge · 发表于 2021-12-23 12:25

我是直接用GA优化SVM的初始形式的，关于非支持向量的约束条件直接包含在里面然后丢到GA里面直接跑的，可能是我做测试的数据集很小，效率的差别并不明显。

RecursiveFrog · 发表于 2021-12-23 12:28

这样啊，那这样的话不就不能用核函数了嘛…用最原始的形式的，线性不可分和非线性都不能处理了嘛

rustum · 发表于 2021-12-23 12:33

这个线性可分的简单数据我是这样处理的，我也是只是尝试使用自己的遗传算法框架啦。如果是线性不可分的我觉得可以尝试在适应度函数里面对违反约束的解进行处理惩罚，使其被淘汰掉也可以。种群大小可以取大一些。

FeastSC · 发表于 2021-12-23 12:39

线性不可分挺容易扩展的，可是非线性问题就不好处理了，约束在优化算法中好难表示…

		自动登录	找回密码
密码			立即注册

机器学习算法实践-Platt SMO和遗传算法优化SVM

本帖子中包含更多资源