一、线性支撑向量机（找最大间隔分类面）

1.优化问题
原优化问题：$ma{x}_{w,b}margin(w,b)=mi{n}_{n=\mathrm{1..}N}\frac{1}{\Vert w\Vert }{y}_n(w^T{x}_n+b)$
约束条件：$y_n(w^T{x}_n+b)>0$（所有样本正确分类）
经过尺度缩放简化后的优化问题：$mi{n}_{w,b}\frac{1}{2}{w}^{T}w$ $s.t.y_n(w^T{x}_n+b)\ge 1$
2.支撑向量：满足 $y_n(w^T{x}_n+b)=1$

二、对偶与核支撑向量机

规避高维难题：将原问题求解维度从$\tilde{d}$转为样本数量N

（一）对偶支撑向量机：简化求解过程

1.对偶转化
原问题：$mi{n}_{w,b}ma{x}_{{\alpha }_n\ge 0}L(w,b,\alpha )$
对偶问题：$ma{x}_{{\alpha }_n\ge 0}mi{n}_{w,b}L(w,b,\alpha )$
带约束优化转化为无约束优化问题：$L(w,b,\alpha )=\frac{1}{2}{w}^{T}w+{\sum }_{n=1}^N{\alpha }_n[1-y_n(w^T{x}_n+b)]$
2.求解

• $\frac{\partial L}{\partial b}=-{\sum }_{n=1}^N{\alpha }_n{y}_n=0$ → 约束${\sum }_{n=1}^N{\alpha }_n{y}_n=0$。
• $\frac{\partial L}{\partial w}=w-{\sum }_{n=1}^N{\alpha }_n{y}_n{x}_n=0$ →$w={\sum }_{n=1}^N{\alpha }_n{y}_n{x}_n$（w是支撑向量的线性组合）
• 将$w$表达式代入$L$，得到最终对偶问题：$mi{n}_{\alpha }\frac{1}{2}{\sum }_{n=1}^N{\sum }_{m=1}^N{\alpha }_n{\alpha }_m{y}_n{y}_m(x_n^T{x}_m)-{\sum }_{n=1}^N{\alpha }_n$ 约束条件:${\sum }_{n=1}^N{\alpha }_n{y}_n=0$
• 通过互补松弛找支撑向量如${\alpha }_s>0$，再用支撑向量求b：$b=y_s-w^T{x}_s$

3.KKT条件：最优解充要条件

• $y_n(w^T{x}_n+b)\ge 1$(原问题可行，即所有样本满足约束条件)
• ${\alpha }_n\ge 0$（错分样本对函数贡献非正）
• ${\alpha }_n[1-y_n(w^T{x}_n+b)]=0$（互补松弛）
• ${\sum }_{n=1}^N{\alpha }_n{y}_n=0$且$w={\sum }_{n=1}^N{\alpha }_n{y}_n{x}_n$（梯度为0）

（二）核支撑向量机：解决非线性问题

核函数$K={\Phi }^T\Phi$对x做非线性变换

1.常用核函数

2.分类预测

• 求解$mi{n}_{\alpha }\frac{1}{2}{\sum }_{n=1}^N{\sum }_{m=1}^N{\alpha }_n{\alpha }_m{y}_n{y}_{m}K(x_n,x_m)-{\sum }_{n=1}^N{\alpha }_n$
• 求解后得：$g_{SVM}(x)=sign({\sum }_{SV}{\alpha }_n{y}_{n}K(x_n,x)+b)$,$b=y_s-{\sum }_{SV}{\alpha }_n{y}_{n}K(x_n,x)$

3.软间隔SVM：允许部分样本越界

• 松弛变量${\xi }_n\ge 0$：${\xi }_n>0$：样本越界；${\xi }_n>1$：样本分错 惩罚参数C：C越大惩罚越界越重
• 目标函数：$mi{n}_{w,b,\xi }\frac{1}{2}{w}^{T}w+C{\sum }_{n=1}^N{\xi }_n,s.t.y_n(w^T{x}_n+b)\ge 1-{\xi }_n（\xi n\ge 0）$
• 对偶问题的目标函数：$L(w,b,\xi ,\alpha ,\beta )=\frac{1}{2}{w}^{T}w+C{\sum }_{n=1}^N{\xi }_n+{\sum }_{n=1}^N{\alpha }_n[1-{\xi }_n-y_n(w^T{x}_n+b)]-{\sum }_{n=1}^N{\beta }_n{\xi }_n$
• 支撑向量分类：
  – 非支撑向量：$a_n=0,{\xi }_n=0$
  – 边界支撑向量：$0<a_n<C,\xi =0$
  – 越界向量：$a_n=C,{\xi }_n\ge 0$

附录：

1. Dual-SVM算法关键代码

# 构建二次规划问题
n_samples, n_features = X.shape
P = cvxopt.matrix(np.outer(y, y) * np.dot(X, X.T), tc='d')
q = cvxopt.matrix(-np.ones(n_samples), tc='d')
A = cvxopt.matrix(y.reshape(1, -1), tc='d')
b = cvxopt.matrix(np.zeros(1), tc='d')
G = cvxopt.matrix(-np.eye(n_samples), tc='d')
h = cvxopt.matrix(np.zeros(n_samples), tc='d')

# 求解二次规划
solution = cvxopt.solvers.qp(P, q, G, h, A, b)

# 提取结果
alpha = np.array(solution['x']).reshape(-1)
support_vectors = alpha > 1e-5
alpha_sv = alpha[support_vectors]
X_sv = X[support_vectors]
y_sv = y[support_vectors]
w = np.sum(alpha_sv.reshape(-1, 1) * y_sv.reshape(-1, 1) * X_sv, axis=0)
b = np.mean(y_sv - np.dot(X_sv, w))

2. Kernel-SVM算法关键代码

# 定义高斯核函数
def gaussian_kernel(x1, x2, gamma=1.0):
    return np.exp(-gamma * np.linalg.norm(x1 - x2)**2)

# 构建二次规划问题
n_samples, n_features = X.shape
P = cvxopt.matrix(np.outer(y, y) * np.array([[gaussian_kernel(xi, xj) for xj in X] for xi in X]), tc='d')
q = cvxopt.matrix(-np.ones(n_samples), tc='d')
A = cvxopt.matrix(y.reshape(1, -1), tc='d')
b = cvxopt.matrix(np.zeros(1), tc='d')
G = cvxopt.matrix(-np.eye(n_samples), tc='d')
h = cvxopt.matrix(np.zeros(n_samples), tc='d')

# 求解二次规划
solution = cvxopt.solvers.qp(P, q, G, h, A, b)

# 提取结果
alpha = np.array(solution['x']).reshape(-1)
support_vectors = alpha > 1e-5
alpha_sv = alpha[support_vectors]
X_sv = X[support_vectors]
y_sv = y[support_vectors]

# 计算 b
def predict(x):
    return np.sum(alpha_sv * y_sv * np.array([gaussian_kernel(x, xi) for xi in X_sv]))

b = np.mean(y_sv - np.array([predict(xi) for xi in X_sv]))