【机器学习 课后习题 系列教程】第 7 章 习题解答（上）

习题 7.1 详解

「习题 7.1」 比较感知机的对偶形式与线性可分支持向量机的对偶形式。

「由于感知机模型和线性可分支持向量机均以数据集线性可分作为前提条件，因此本习题将通过对比两者的对偶形式，深入分析它们在理论上的联系与差异。」

感知机的对偶形式

感知机对偶形式的学习问题并未在《统计学习方法（第 2 版）》中直接给出。为此，我们从原始形式的学习问题出发，结合对偶问题中引入的参数  ，推导对偶形式。

感知机模型以最小化误分类点到分离超平面的总距离和来学习模型参数。学习问题为

其中   是训练集中误分类点集合。 在感知机对偶形式的算法中，

将式中参数   的表达式代入原始形式的学习问题中，得到

因此，感知机对偶形式的学习问题为

其中  。

若求解出的最优参数为  ，则可以得到模型参数  。

线性可分支持向量机的对偶形式

线性可分支持向量机以最大化几何间隔学习模型参数，其对偶形式的学习问题为

其中拉格朗日乘子向量  。

若求解出的最优参数为  ，则模型最优参数为

感知机与线性可分支持向量机对偶形式的异同

「相同之处」

• 两者都需要假设数据集是线性可分的。

• 两者的模型参数   关于   的表达式是相同的。

• 两者都是先求得   的最优解，然后以   将模型参数   表示出来。

• 两者都涉及到样本点之间的内积运算，可以采用 Gram 矩阵

存储内积信息，提高运算速度。

「差异之处」

• 两者的「基本原理不同」：感知机侧重于减少误分类点的数量；线性可分支持向量机不只是侧重减少误分类，同时还侧重于增强分类的确信度。

• 两者「学习问题的目标函数不同」：感知机的目标函数定义在误分类点集合   上，线性可分支持向量机的目标函数定义在整个训练集上；而且感知机和线性可分支持向量机的目标函数表达式不同。

• 两者「学习问题的约束条件不同」：线性可分支持向量机比感知机多了一个约束条件  ，这个约束条件保证了线性可分支持向量机最终得到的分离超平面是间隔最大的。

• 两者的「最优解不同」：感知机的最优解不是唯一的；线性可分支持向量机的最优解具有唯一性。

习题 7.2 详解

「习题 7.2」 已知正例点~  ，负例点~  ，  ，试求最大间隔分离超平面和分类决策函数，并在图上画出分离超平面，间隔边界及支持向量。

数据可视化

为更好地理解数据情况，先将这些实例点在二维平面上绘制出来

仔细观察，可以发现正例点主要分布在左上区域，负例点分布在右下区域，这表明数据集是线性可分，肯定存在一个分离超平面完全将这两类实例点分开。

尝试推导计算解析解

先求出 Gram 矩阵，存储样本点的内积

记  ，则优化问题为

其中拉格朗日乘子向量  。

引用费马引理，对目标函数    求偏导数，并令其为零，得到

记

采用消元法对矩阵   进行变换

可见，「矩阵   的行列式为 0，意味着矩阵   是奇异的，很难通过直接推导得到解析解。」

采用 Python 中的 svm 求数值解

线性可分支持向量机的硬间隔算法要求所有的样本点都能完全分开，不需要任何松弛变量。在 python 的 sklearn 中，svm 的函数 SVC 默认使用的是带有惩罚项的软间隔算法，为此我们可以「将函数 SVC 中的惩罚参数   设置为一个非常大的数值，比如令  ，使得模型强制要求尽可能地完全分离数据，从而模拟硬间隔算法的行为」。以下是求解的 Python 代码。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm

# 输入数据
X = np.array([[1, 2], [2, 3], [3, 3], [2, 1], [3, 2]])  # 特征向量
y = np.array([1, 1, 1, -1, -1])  # 标签

# 创建支持向量机分类器
hard_svm = svm.SVC(kernel='linear', C=1e10) # 选择线性核
hard_svm.fit(X, y)

# 获取分离超平面的参数
w = hard_svm.coef_[0]  # `{\color{gray} 法向量}`
b = hard_svm.intercept_[0]  # `{\color{gray} 截距}`
print(f"Final model: w = {w}, b = {b}")


# 获取支持向量
support_vectors = hard_svm.support_vectors_
print("support vectors:", support_vectors)

运行代码，可以得到分离超平面的最优参数以及支持向量

Final model: w = [[-1.  2.]], b = [-2.]
support vectors: [[3. 2.]
 [1. 2.]
 [3. 3.]]

于是，通过线性可分支持向量机的硬间隔算法得到最优分离超平面

分类决策函数为

支持向量为

写出结果可视化的 Python 代码

写出绘制分离超平面、间隔边界及支持向量的 Python 代码。

# 设置图像大小和分辨率
plt.figure(figsize=(6, 6), dpi=500)

# 绘制数据点
plt.scatter(X[y == 1][:, 0], X[y == 1][:, 1], color='red', label='正例点', marker='o')  
plt.scatter(X[y == -1][:, 0], X[y == -1][:, 1], color='green', label='负例点', marker='x')   

# 绘制支持向量
plt.scatter(support_vectors[:, 0], support_vectors[:, 1], s=100, facecolors='none', edgecolors='gray', label='支持向量', marker='s')

# 绘制分离超平面和间隔边界
xx, yy = np.meshgrid(np.linspace(0, 4, 30), np.linspace(0, 4, 30))
Z = np.dot(np.c_[xx.ravel(), yy.ravel()], w) + b
Z = Z.reshape(xx.shape)

# 绘制分离超平面
plt.contour(xx, yy, Z, levels=[0], linewidths=2, colors='black', label='Decision boundary')

# 绘制间隔边界
plt.contour(xx, yy, Z, levels=[1], linewidths=1, colors='blue', linestyles='dashed')
plt.contour(xx, yy, Z, levels=[-1], linewidths=1, colors='blue', linestyles='dashed')

# 设置图形参数
plt.xlabel('$x^{(1)}$')   
plt.ylabel('$x^{(2)}$')  
plt.legend(loc='upper left')
plt.show()

运行后的结果如图所示。