非参数化模型，当数据集规模增大时，其参数量也相应变多
希望从这无数个可以分隔两个点集的超平面中，挑选出与任意一点间隔（margin）的最小值最大的平面
支持向量机的数学描述
对上式来说，当w和b的大小同时变为λ倍时，式中的分母||w||也变为λ倍，这时划分超平面完全不变
定义γ = yi(wx+b)为函数间隔，γi = γ / ||w||为几何间隔。我们希望所有样本到平面的几何间隔 γi 的最小值最大
于是，支持向量机的优化目标可以写为：
上面已经提到，函数间隔γ关于w和b的大小并不影响实际的几何间隔γi，因为其变化总会被||w||所抵消。因此，不妨令γ=1。这样上面的优化目标就变为：
为了求解方便，我们选择凸的单调递增函数，进一步将优化目标等价地写为：
如果数据线性不可分，我们可以适当放低上面的约束要求，引入松弛变量ξi，将约束问题改写为：
凸优化的原始问题：
定义其拉格朗日函数（Lagrangian function）为：
当约束条件满足时，拉格朗日函数的最大值恰好就等于原问题的目标函数f(w)，从而原问题可以写为：
将上面优化问题中计算min和max的顺序交换，定义其对偶问题为：
所以求解拉格朗日函数得到w和b，代入对偶函数得到：
序列最小优化
每次选取两个不同的参数αi和αj，而固定其他的参数，只优化这两个参数从而保证等式约束一直成立
核函数
去拟合非线性
alpha, b = SMO(x, y, kernels[i], C=C, max_iter=max_iter)
sup_idx = alpha > 1e-6 # 支持向量的系数不为零
sup_x = x[sup_idx] # 支持向量
sup_y = y[sup_idx]
sup_alpha = alpha[sup_idx]
# 用支持向量计算 w^T*x
def wx(x_new):
s = 0
for xi, yi, ai in zip(sup_x, sup_y, sup_alpha):
s += yi * ai * kernels[i](xi, x_new)
return s调用SMO算法求解SVM的对偶问题，得到最优的拉格朗日乘子alpha和截距b
alpha值通常会有一些非常接近于零的值，这些对应于不重要的样本点，而对于支持向量来说，其对应的alpha值通常远大于零
contou
G = np.linspace(-1.5, 1.5, 100)
G = np.meshgrid(G, G)
X = np.array([G[0].flatten(), G[1].flatten()]).T # 转换为每行一个向量的形式
Y = np.array([wx(xi) + b for xi in X])
Y[Y < 0] = -1
Y[Y >= 0] = 1
Y = Y.reshape(G[0].shape)
axs[i].contourf(G[0], G[1], Y, cmap=cmap, alpha=0.5)
# 绘制原数据集的点
axs[i].scatter(x[y == -1, 0], x[y == -1, 1], color='red', label='y=-1')
axs[i].scatter(x[y == 1, 0], x[y == 1, 1], marker='x', color='blue', label='y=1')
axs[i].set_title(ker_names[i])
axs[i].set_xlabel(r'$x_1$')
axs[i].set_ylabel(r'$x_2$')
axs[i].legend()contourf 函数在二维平面上画出决策边界，其中 G[0] 和 G[1] 是网格的横纵坐标，Y 是每个网格点的预测结果，根据预测结果的正负来填充不同的颜色
Sklearn中的SVM工具
model = SVC(kernel='rbf', gamma=50, tol=1e-6)对于RBF核函数，其参数为γ =1/(2σ^2)。上一节我们设置σ=0.1，因此这里对应的参数为γ=50
tol=1e-6表示训练算法停止的容差值。当模型在两次迭代中的优化结果之间的差异小于 tol 时，算法将停止迭代
习题
1.B。
2.D。大大降低了时间复杂度倒未必
3.逻辑斯谛回归使用梯度下降等优化算法来找到最优参数，而这些优化算法可能会涉及复杂度很高的矩阵乘法和求逆运算
支持向量机则可以通过拉格朗日对偶性得到解析解，不包含这类复杂运算
4.左边是支持向量机，右边是逻辑回归
from sklearn.linear_model import LogisticRegression
log_reg = LogisticRegression(max_iter=10000)
log_reg.fit(x, y)
w_log_reg = log_reg.coef_[0]
b_log_reg = log_reg.intercept_
Y_log_reg = -(w_log_reg[0] * X + b_log_reg) / (w_log_reg[1] + 1e-5)
plt.figure()
plt.scatter(x[y == -1, 0], x[y == -1, 1], color='red', label='y=-1')
plt.scatter(x[y == 1, 0], x[y == 1, 1], marker='x', color='blue', label='y=1')
plt.plot(X, Y_log_reg, color='green', label='Logistic Regression')
plt.xlabel(r'$x_1$')
plt.ylabel(r'$x_2$')
plt.legend()
plt.show()
加点前：
加点后：
x = np.vstack((x, [[3, 3], [4, 4]]))
y = np.hstack((y, [-1, 1]))
左边SVM右边逻辑回归
5.RBF核函数对应的Φ(·)函数是将输入空间映射到无穷维空间的高斯函数，而输出为无穷维的特征映射Φ(·)的意义在于将原始数据映射到一个更高维度的空间，以便找到更好的数据分隔边界。
6.
# 访问支持向量的索引
support_vector_indices = model.support_
# 获取支持向量
support_vectors = x[support_vector_indices]
# 绘制结果
fig = plt.figure(figsize=(6,6))
G = np.linspace(-1.5, 1.5, 100)
G = np.meshgrid(G, G)
X = np.array([G[0].flatten(), G[1].flatten()]).T # 转换为每行一个向量的形式
Y = model.predict(X)
Y = Y.reshape(G[0].shape)
plt.contourf(G[0], G[1], Y, cmap=cmap, alpha=0.5)
# 绘制支持向量
plt.scatter(support_vectors[:, 0], support_vectors[:, 1], marker='o', color='none',
edgecolor='purple', s=150, label='Support Vectors')
# 绘制原数据集的点
plt.scatter(x[y == -1, 0], x[y == -1, 1], color='red', label='y=-1')
plt.scatter(x[y == 1, 0], x[y == 1, 1], marker='x', color='blue', label='y=1')
plt.xlabel(r'$x_1$')
plt.ylabel(r'$x_2$')
plt.legend()
plt.show()
7.
原问题：
原问题是指SVM的原始优化问题，它直接处理数据点和模型参数。SVM的原问题涉及一个带有约束的优化问题，即在满足所有数据点到分隔超平面距离至少为某个固定值（即间隔）的条件下，最大化这个间隔。
在数学上，原问题可以表示为关于支持向量和模型参数（例如，权重向量和偏置项）的问题。如果数据集很大，那么相应的参数也会很多，因此，从这个角度看，原问题似乎是一个参数化模型。然而，由于解仅由一小部分称为支持向量的数据点决定，所以实际上并不需要存储整个数据集。
对偶问题：
通过引入拉格朗日乘子将原问题的约束优化转换为无约束优化问题，我们得到了所谓的对偶问题。在这个过程中，数据点以拉格朗日乘子的形式出现，并且最终决策函数仅依赖于数据点之间的内积，而不是数据点的显式表示。这意味着在对偶形式下，我们不需要直接处理原始数据点，而是关注数据点之间的关系。
从参数更新方式来看，对偶问题通常只涉及拉格朗日乘子（alpha），而与原始问题中的参数（如权重和偏置）无关。这使得对偶问题看起来更像一个非参数化模型，因为它没有直接使用原始参数空间的大小作为其复杂性的度量。此外，对偶问题通常具有更少的变量（拉格朗日乘子的数量等于数据点的数量），这使得求解过程更加高效，尤其是在处理大规模数据集时。