前言：仅个人小记。https://blog.csdn.net/qq_25847123/article/details/108055404给出了原问题的解法。这里给出支持向量机中凸二次规划问题的对偶解法。不论是对偶还是原问题形式，都是转成二次规划问题，编程角度上来看没太大差别。但从理论角度来看，对偶性形式能够直接凸显出“内积”形式，进而可以很好地引入“核”概念。
对偶形式 min ? α 1 2 ∑ i = 1 N ∑ i = 1 N α i α j y i y j ( x i x j ) ? ∑ i = 1 N α i s . t . ∑ i = 1 N α i y i = 1 α i ≥ 0 , i = 1 , 2 , . . . , N \min_{\alpha}\frac{1}{2}\sum_{i=1}^{N}\sum_{i=1}^{N}\alpha_i\alpha_jy_iy_j({\color{red}\boldsymbol{x}_i\boldsymbol{x}_j})-\sum_{i=1}^N\alpha_i\\ \mathsf{s.t.} \sum_{i=1}^N \alpha_iy_i=1\\ \alpha_i\geq 0,i=1,2,...,N αmin?21?i=1∑N?i=1∑N?αi?αj?yi?yj?(xi?xj?)?i=1∑N?αi?s.t.i=1∑N?αi?yi?=1αi?≥0,i=1,2,...,N
求解出 α ? \alpha^* α?，进而根据下面结论可以得到原始问题的解
w ? = ∑ i = 1 N α i ? y i x i b ? = y j ? ∑ i = 1 N α i ? y i ( x i x j ) w^*=\sum_{i=1}^N\alpha_i^*y_i\boldsymbol{x}_i\\ b^* = y_j-\sum_{i=1}^N \alpha_i^*y_i(\boldsymbol{x}_i\boldsymbol{x}_j) w?=i=1∑N?αi??yi?xi?b?=yj??i=1∑N?αi??yi?(xi?xj?)其中 j j j式对应于某一个大于 0 0 0的 α j \alpha_j αj?即可。进而求出了原始问题的解，进而线性可分支持向量机训练完毕。
注意到在对偶最优化问题中，完全可以把内积 x i ? y j , i , j ∈ [ 1 , N ] {\color{red}\boldsymbol{x}_i\cdot \boldsymbol{y}_j,i,j\in [1,N]} xi??yj?,i,j∈[1,N]提前计算出来。同时观察到，使用对偶形式训练支持向量机的过程中，对于数据集，只是使用到了求内积运算，而不再有任何其他运算。故而，在后面可以将内积概念广义化，进而推出非线性的支持向量机。
【ML|线性可分支持向量机 对偶性形式求解】也注意到，对偶形式中目标函数的二次部分可以直接提取出二次型矩阵，并将目标函数写作矩阵形式为
[ α 1 α 2 . α N ] ( 1 2 [ y 1 y 1 ( x 1 ? x 1 ) y 1 y 2 ( x 1 ? x 2 ) . . . y 1 y 3 ( x 1 ? x 3 ) y 2 y 1 ( x 2 ? x 1 ) y 2 y 2 ( x 2 ? x 2 ) . . . y 2 y N ( x 2 ? x N ) . . . . . . y N y 1 ( x N ? x 1 ) y N y 2 ( x N ? x 2 ) . . . y N y N ( x N ? x N ) ] [ α 1 α 2 . α N ] ? [ 1 1 . 1 ] ) \begin{bmatrix} \alpha_1&\alpha_2&.&\alpha_N\end{bmatrix} (\frac{1}{2}\begin{bmatrix} y_1y_1(\boldsymbol{x}_1\cdot \boldsymbol{x}_1) & y_1y_2(\boldsymbol{x}_1\cdot \boldsymbol{x}_2) & ... & y_1y_3(\boldsymbol{x}_1\cdot \boldsymbol{x}_3)\\ y_2y_1(\boldsymbol{x}_2\cdot \boldsymbol{x}_1) & y_2y_2(\boldsymbol{x}_2\cdot \boldsymbol{x}_2) & ... & y_2y_N(\boldsymbol{x}_2\cdot \boldsymbol{x}_N)\\ .&.&...&.\\ y_Ny_1(\boldsymbol{x}_N\cdot \boldsymbol{x}_1) & y_Ny_2(\boldsymbol{x}_N\cdot \boldsymbol{x}_2) & ... & y_Ny_N(\boldsymbol{x}_N\cdot \boldsymbol{x}_N)\\ \end{bmatrix} \begin{bmatrix} \alpha_1\\\alpha_2\\.\\\alpha_N\end{bmatrix}-\begin{bmatrix} 1\\1\\.\\1\end{bmatrix}) [α1??α2??.?αN??](21??????y1?y1?(x1??x1?)y2?y1?(x2??x1?).yN?y1?(xN??x1?)?y1?y2?(x1??x2?)y2?y2?(x2??x2?).yN?y2?(xN??x2?)?............?y1?y3?(x1??x3?)y2?yN?(x2??xN?).yN?yN?(xN??xN?)???????????α1?α2?.αN?????????????11.1??????)
记为 α T ( 1 2 P α ? [ 1 , 1 , . . . , 1 ] T ) \boldsymbol{\alpha}^T(\frac{1}{2}P\boldsymbol{\alpha}-[1,1,...,1]^T) αT(21?Pα?[1,1,...,1]T)
这个式子给出了非常简洁的对偶最优化目标函数的形式。容易看出，整个函数的核心就是那个 P P P。
对偶实现
# 使用对偶形式求解#因为用到所有的数据之间的内积，故而可以将内积计算部分单独提出来
# 所有的内积写作矩阵形式，成为核矩阵
dataset = np.array([[3,3],[4,3],[1,1]])
labels = np.array([1,1,-1])
#T = [(3,3,1),(4,3,1),(1,1,-1)] # 数据集，格式为 (x1,x2,y)，其中y 为标签，取值-1，+1
n = len(dataset)
P = np.zeros((n,n))for i in range(n):
for j in range(i+1):
P[i][j] = labels[i]*labels[j]*np.dot(dataset[i],dataset[j])
P[j][i] = P[i][j]P = cvxopt.matrix(P)q = cvxopt.matrix([-1.0]*n)G = -np.identity(n)
G = cvxopt.matrix(G)h = cvxopt.matrix([0.0]*n)A = cvxopt.matrix([label*1.0 for label in labels],(1,3))
b = cvxopt.matrix([0.0],(1,1))sol = cvxopt.solvers.qp(P,q,G,h,A,b)alpha = sol['x']print(sol['x'])# 计算分离超平面
w = np.array([0.0,0.0])
for i in range(n):
w += alpha[i]*labels[i]*dataset[i]alphaPos = 0
for i in range(n):
if alpha[i] > 0:
alphaPos =i
break
t = 0
for i in range(n):
t += alpha[i]*labels[i]*np.dot(dataset[i],dataset[alphaPos])b = labels[alphaPos]- tprint(w,b)
drawScatterPointsAndLine(dataset,labels,w,b)
推荐阅读
- AI|Seq2Seq中的Attention和self-attention
- 机器学习|SVM学习笔记
- bert-modeling代码学习
- 机器学习-推荐系统中基于深度学习的混合协同过滤模型
- bert-create_pretraining_data代码学习
- 机器学习常见评价指标 -- 混淆矩阵 & Precision(精确度) & Recall(召回率) & Accuracy(准确度)
- 使用Amazon SageMaker部署CVAT AI自动图像标注系统
- 基于Amazon Machine Learning Bot 的 Named-entity Recognition 快速解决方案
- 在亚马逊云科技Marketplace上的SaaS架构设计——如何支持多产品使用单一账户中心
- Amazon DeepRacer训练日志分析范例与强化学习Reward Function设计