第7章 支持向量机
习题7.1
比较感知机的对偶形式与线性可分支持向量机的对偶形式。
解答：
解答思路：
- 列出感知机的原始形式；
- 写出感知机的对偶形式；
- 列出线性可分支持向量机的原始形式；
- 写出线性可分支持向量机的对偶形式；
- 比较感知机和线性可分支持向量机的对偶形式。
解答步骤：
第1步：感知机的原始形式
根据书中第2.3.1节的感知机学习算法的原始形式：
给定一个训练数据集
>
> 其中，$x_i \in \mathcal{X} = R^n, y_i \in \mathcal{Y}=\{-1,1\}, i=1,2,\cdots,N$，求参数$w,b$，使其为以下损失函数极小化问题的解
>
> $$ \min \limits_{w,b} L(w,b)=-\sum_{x_i \in M} y_i(w \cdot x_i + b)
其中M为误分类点的集合。
根据书中第2章的算法2.1：
算法2.1（感知机学习算法的原始形式）
输入：训练数据集T={(x1,y1),(x2,y2),⋯,(xN,yN)}，其中xi∈X=Rn,yi∈Y={−1,+1},i=1,2,⋯,N；学习率η（0<η⩽1）；
输出：w,b；感知机模型f(x)=sign(w⋅x+b)
（1）选取初值w0,b0；
（2）在训练集中选取数据(xi,yi)；
（3）如果yi(w⋅xi+b)⩽0，
b \leftarrow b + \eta y_i
>（4）转至步骤（2），直至训练集中没有误分类点。
**第2步：感知机的对偶形式**
  根据书中第2章的算法2.2：
> **算法2.2（感知机学习算法的对偶形式）**
> 输入：线性可分的数据集$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$，其中$x_i \in R^n, y_i \in \{-1, +1\}, i=1,2,\cdots,N$；学习率$\eta$（$0 < \eta \leqslant 1$）；
输出：$a,b$；感知机模型$\displaystyle f(x)=\text{sign} \left( \sum_{j=1}^N \alpha_j y_j x_j \cdot x + b \right)$，其中$\alpha = (\alpha_1, \alpha_2,\cdots, \alpha_N)^T$
（1）$\alpha \leftarrow 0,b \leftarrow 0$；
（2）在训练集中选取数据$(x_i, y_i)$；
（3）如果$\displaystyle y_i\left( \sum_{j=1}^N \alpha_j y_j x_j \cdot x + b \right) \leqslant 0$，
> $$ \alpha_i \leftarrow \alpha_i + \eta \\
b \leftarrow b + \eta y_i
（4）转至（2），直至训练集中没有误分类数据。
根据书中第2.3.3节对偶形式的基本思想
从学习过程不难看出，最后学习到的w,b可以分别表示为
b=\sum_{i=1}^N \alpha_i y_i
> 这里，$\alpha_i \geqslant 0, i=1,2,\cdots,N$
  综上所述：
1. 感知机的原始形式中的损失函数：
\min_{w,b} L(w,b)=-\sum_{x_i \in M} y_i(w \cdot x_i + b)
2. 感知机的对偶形式中的损失函数：可知$w,b$表示为$\langle x_i,y_i \rangle$的线性组合形式，则
\min_{w,b} L(w,b) = \min_{\alpha} L(\alpha) = - \sum \limits_{x_i \in M} ( y_i ( \sum_{j=1}^N \alpha_j y_j x_j \cdot x_i + \sum_{j=1}^N \alpha_j y_j ) )
其中，$\alpha = (\alpha_1, \alpha_2,\cdots, \alpha_N)^T$
**第3步：线性可分支持向量机的原始形式**
  根据书中第7.1.3节的线性可分支持向量机学习的最优化问题，可作为原始最优化问题(7.13)~(7.14)：
> $$ \begin{align}
\displaystyle \min_{w,b} \quad & \displaystyle \frac{1}{2} \|w\|^2 \tag{7.13} \\
\text{s.t.} \quad & y_i(w \cdot x_i + b) -1 \geqslant 0, \quad i=1, 2,\cdots, N \tag{7.14} \\
\end{align}
第4步：线性可分支持向量机的对偶形式
根据书中第7章的算法7.2：
算法7.2（线性可分支持向量机学习算法）
输入：线性可分训练集T={(x1,y1),(x2,y2),⋯,(xN,yN)}，其中xi∈X=Rn，yi∈Y={−1,+1}，i=1,2,⋯,N；
输出：分离超平面和分类决策函数。
（1）构造并求解约束最优化问题
\displaystyle \min_{\alpha} & \displaystyle \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^N
\alpha_i \
\text{s.t.} & \displaystyle \sum_{i=1}^N \alpha_i y_i = 0 \
& \alpha_i \geqslant 0, \quad i=1,2,\cdots,N
\end{array}
> 求得最优解$\alpha^*=(\alpha_1^*, \alpha_2^*, \cdots, \alpha_N^*)^T$。
>（2）计算
> $$ w^* = \sum_{i=1}^N \alpha_i^* y_j x_i
并选择α∗的一个正分量αj∗>0，计算
>（3）求得分离超平面
> $$ w^* \cdot x + b^* = 0
分类决策函数：
f(x)=sign(w∗⋅x+b∗)
综上所述：
- 线性可分支持向量机的原始形式中的损失函数：
w,bminL(w,b)=21∥w∥2
- 线性可分支持向量机的对偶形式中的损失函数：根据定理7.2，可知w,b表示为⟨xi,yi⟩的线性组合形式，则
w,bminL(w,b)=αminL(α)=21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)−i=1∑Nαi
其中，α=(α1,α2,⋯,αN)T
第5步：感知机和线性可分支持向量机对偶形式的比较
- 在两者的对偶形式中，w,b都可以表示为⟨xi,yi⟩的线性组合形式；
- 在两者的对偶形式中，都可以通过求解α=(α1,α2,⋯,αN)T，最后代入由xi,yi,αi表示的w和b公式中，从而求解最优化问题的解w∗和b∗；
- 感知机学习得到一个分隔超平面，而线性可分支持向量机学习得到所有分隔超平面中的间隔最大分隔超平面。
习题7.2
已知正例点x1=(1,2)T,x2=(2,3)T,x3=(3,3)T，负例点x4=(2,1)T,x5=(3,2)T，试求最大间隔分离平面和分类决策函数，并在图中画出分离超平面、间隔边界及支持向量。
解答：
解答思路：
- 通过调用sklearn.svm的SVC类构建模型，根据题目中的数据训练模型，得到w、b和支持向量；
- 调用matplotlib库，画出分离超平面、间隔边界和支持向量。
解答步骤：
第1步：训练模型，得到w、b和支持向量
%matplotlib inline
from sklearn.svm import SVC
X = [[1, 2], [2, 3], [3, 3], [2, 1], [3, 2]]
y = [1, 1, 1, -1, -1]
clf = SVC(kernel='linear', C=10000)
clf.fit(X, y)
print("w =", clf.coef_)
print("b =", clf.intercept_)
print("support vectors =", clf.support_vectors_)
w =
b = [-2.]
support vectors = [[3. 2.]
[1. 2.]
[3. 3.]]
可得：
- 最大间隔分离超平面：−x(1)+2x(2)−2=0
- 分类决策函数：f(x)=sign(−x(1)+2x(2)−2)
- 支持向量：x1=(3,2)T,x2=(1,2)T,x3=(3,3)T
第2步：在图中画出分离超平面、间隔边界和支持向量
import matplotlib.pyplot as plt
import numpy as np
color_seq = ['red' if v==1 else 'blue' for v in y]
plt.scatter([i[0] for i in X], [i[1] for i in X], c=color_seq)
xaxis = np.linspace(0, 3.5)
w = clf.coef_[0]
a = -w[0] / w[1]
y_sep = a * xaxis - (clf.intercept_[0]) / w[1]
b = clf.support_vectors_[0]
yy_down = a * xaxis + (b[1] - a * b[0])
b = clf.support_vectors_[-1]
yy_up = a * xaxis + (b[1] - a * b[0])
plt.plot(xaxis, y_sep, 'k-')
plt.plot(xaxis, yy_down, 'k--')
plt.plot(xaxis, yy_up, 'k--')
plt.xlabel('$x^{(1)}$')
plt.ylabel('$x^{(2)}$')
plt.scatter(clf.support_vectors_[:, 0], clf.support_vectors_[:, 1],
s=150, facecolors='none', edgecolors='k')
plt.show()
习题7.3
线性支持向量机还可以定义为以下形式：
w,b,ξmins.t.21∥w∥2+Ci=1∑Nξi2yi(w⋅xi+b)⩾1−ξi,i=1,2,⋯,Nξi⩾0,i=1,2,⋯,N
试求其对偶形式。
解答：
解答思路：
参考书中第7.2.2节“学习的对偶算法”内容`
- 根据附录C 拉格朗日对偶性，写出拉格朗日函数；
- 对 L(w,b,ξ,α,μ) 求 w,b,ξ 的极小；
- 对 w,b,ξminL(w,b,ξ,α,μ) 求 α 的极大；
- 整理得到对偶形式。
解答步骤：
第1步：原始问题的拉格朗日函数
根据书中附录C 拉格朗日对偶性：
假设f(x),ci(x),hj(x)是定义在Rn上的连续可微函数。考虑约束最优化问题
\displaystyle \min \limits_{x \in R^n} \quad & f(x) \tag{C.1} \
\text{s.t.} \quad & c_i(x) \leqslant 0, \quad i=1,2,\cdots, k \tag{C.2} \
\quad & h_j(x) = 0, \quad j=1,2,\cdots, l \tag{C.3}
\end{align}
> 称此约束最优化问题为原始最优化问题，或原始问题。
>
> 引入广义拉格朗日函数
> $$ L(x,\alpha, \beta) = f(x) + \sum_{i=1}^k \alpha_i c_i(x) + \sum_{j=1}^l \beta_j h_j(x) \tag{C.4}
这里，x=(x(1),x(2),⋯,x(n))T∈Rn，αi,βj是拉格朗日乘子，αi⩾0。考虑x的函数：
> 这里，下标$P$表示原始问题。
  根据书中附录C的原始问题极小化：
> 如果考虑极小化问题
> $$ \min \limits_{x} \theta_P(x) = \min \limits_{x} \max \limits_{\alpha,\beta:\alpha_i \geqslant 0} L(x, \alpha, \beta)
它是与原始最优化问题(C.1)~(C.3)等价的，即它们有相同的解。问题 xminα,β:αi⩾0maxL(x,α,β) 称为广义拉格朗日函数的极小极大问题。
根据题意，原始问题为
w,b,ξmins.t.21∥w∥2+Ci=1∑Nξi2yi(w⋅xi+b)⩾1−ξi,i=1,2,⋯,Nξi⩾0,i=1,2,⋯,N
根据最优化函数的对应关系，可得
⎩⎨⎧f(x)=21∥w∥2+Ci=1∑Nξi2ci(1)(x)=1−ξi−yi(w⋅xi+b),i=1,2,⋯,Nci(2)(x)=−ξi,i=1,2,⋯,N
根据拉格朗日函数的定义，可得原始问题的拉格朗日函数为
L(w,b,ξ,α,μ)=21∥w∥2+Ci=1∑Nξi2−i=1∑Nαi(yi(w⋅xi+b)−1+ξi)−i=1∑Nμiξi
其中，αi⩾0,μi⩾0
第2步：对L(w,b,ξ,α,μ)求w,b,ξ的极小
根据拉格朗日对偶性，对偶问题是拉格朗日函数的极大极小问题，先对L(w,b,ξ,α,μ)求w,b,ξ的极小，分别对w,b,ξ求偏导，并令导数等于0，由
∇wL(w,b,ξ,α,μ)=w−i=1∑Nαiyixi=0∇bL(w,b,ξ,α,μ)=−i=1∑Nαiyi=0∇ξiL(w,b,ξ,α,μ)=2Cξi−αi−μi=0
可得：
w=i=1∑Nαiyixii=1∑Nαiyi=02Cξi−αi−μi=0
将上式代入到原始问题的拉格朗日函数中，可得
L(w,b,ξ,α,μ)=21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)+Ci=1∑Nξi2−i=1∑Nαiyi((j=1∑Nαjyjxj)⋅xi+b)+i=1∑Nαi−i=1∑Nαiξi−i=1∑Nμiξi=−21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)+i=1∑Nαi+Ci=1∑Nξi2−i=1∑Nαiξi−i=1∑Nμiξi=−21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)+i=1∑Nαi+Ci=1∑Nξi2−i=1∑N(αi+μi)ξi=−21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)+i=1∑Nαi+Ci=1∑Nξi2−i=1∑N(2Cξi)ξi=−21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)+i=1∑Nαi+Ci=1∑Nξi2−2Ci=1∑Nξi2=−21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)+i=1∑Nαi−Ci=1∑Nξi2=−21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)+i=1∑Nαi−Ci=1∑N(4C21(αi+μi)2)=−21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)+i=1∑Nαi−4C1i=1∑N(αi+μi)2
第3步：对w,b,ξminL(w,b,ξ,α,μ)求α的极大
根据第2步，对w,b,ξminL(w,b,ξ,α,μ)求α的极大，可得到对偶问题：
αmaxs.t.−21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)+i=1∑Nαi−4C1i=1∑N(αi+μi)2i=1∑Nαiyi=02Cξi−αi−μi=0αi⩾0,μi⩾0,ξi⩾0,i=1,2,⋯,N
第4步：进行公式变换，得到对偶形式
再将对目标函数求极大转换为求极小，于是得到原始问题的对偶形式
αmins.t.21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)−i=1∑Nαi+4C1i=1∑N(αi+μi)2i=1∑Nαiyi=02Cξi−αi−μi=0αi⩾0,μi⩾0,ξi⩾0,i=1,2,⋯,N
习题7.4
证明内积的正整数幂函数：K(x,z)=(x∙z)p是正定核函数，这里p是正整数，x,z∈Rn。
解答：
解答思路：
- 写出正定核函数的判定依据
- 使用数学归纳法，证明
- 当p=1时，根据定理7.5，证明K(x,z)=x∙z是正定核函数
- 假设当p=k且k>1时，K(x,z)=(x∙z)k是正定核函数
- 证明当p=k+1时，K(x,z)=(x∙z)k+1是正定核函数
解答步骤：
第1步：列出正定核函数的判定依据
根据书中第7章的定理7.5（正定核的充要条件）：
定理7.5（正定核的充要条件） 设K:X×X→R是对称函数，则K(x,z)为正定核函数的充要条件是对任意xi∈X,i=1,2,⋯,m，K(x,z)对应的Gram矩阵：
> 是半正定矩阵。
**第2步：使用数学归纳法，证明$K(x, z)=(x \bullet z)^p$是正定核函数**
1. 当$p=1$时，$K(x, z)=x \bullet z$，对任意$c_1,c_2,\cdots,c_n \in \mathbf{R}$，有
\begin{aligned}
\sum_{i,j=1}^n c_i c_j K(x_i,x_j)
&= \sum_{i,j=1}^n c_i c_j (x_i \bullet x_j) \
&= \left(\sum_{i=1}^m c_i x_i \right) \bullet \left(\sum_{j=1}^m c_j x_j \right) \
&= \Bigg|\left( \sum_{i=1}^m c_i x_i \right)\Bigg|^2 \geqslant 0
\end{aligned}
可得，当$p=1$时，$K(x, z)=x \bullet z$对应的Gram矩阵是半正定的，根据定理7.5，可知$K(x,z)=x \bullet z$是正定核函数。
2. 假设$p=k$且$k$是大于1的正整数时，$K(x, z)=(x \bullet z)^k$是正定核函数
根据书中第7章的定义7.6的（核函数）：
> **定义7.6（核函数）** 设$\mathcal{X}$是输入空间（欧式空间$R^n$的子集或离散集合），又设$\mathcal{H}$为特征空间（希尔伯特空间），如果存在一个从$\mathcal{X}$到$\mathcal{H}$的映射
> $$ \phi(x):\mathcal{X} \rightarrow \mathcal{H}
使得对所有x,z∈X，函数K(x,z)满足条件
> 则称$K(x,z)$为核函数，$\phi(x)$为映射函数，式中$\phi(x) \bullet \phi(z)$为$\phi(x)$和$\phi(z)$的内积。
故存在一个输入空间为$R^n$，$R^n$到$\mathcal{H}$的映射
\phi(x):R^n \rightarrow \mathcal{H}
使得对所有$x,z \in R^n$，函数$K(x,z)=(x \bullet z)^k$满足条件
K(x,z) = \phi(x) \bullet \phi(z)
可假设$\phi(x)=(f_1(x), f_2(x), \cdots, f_m(x))^T$，其中$x=(x^{(1)}, x^{(2)}, \cdots, x^{(n)})^T$
3. 当$p=k+1$时
\begin{aligned}
K(x,z)
&= (x \bullet z)^{k+1} \
&= (x \bullet z)^k (x \bullet z) \
&= (\phi(x) \bullet \phi(z))(x \bullet z) \
&= (f_1(x)f_1(z) + f_2(x)f_2(z) + \cdots + f_m(x)f_m(z))(x^{(1)}z^{(1)} + x^{(2)}z^{(2)} + \cdots + x^{(n)}z^{(n)}) \
&= f_1(x)f_1(z)(x^{(1)}z^{(1)} + x^{(2)}z^{(2)} + \cdots + x^{(n)}z^{(n)}) \
& \quad + f_2(x)f_2(z)(x^{(1)}z^{(1)} + x^{(2)}z^{(2)} + \cdots + x^{(n)}z^{(n)}) + \cdots \
& \quad + f_m(x)f_m(z)(x^{(1)}z^{(1)} + x^{(2)}z^{(2)} + \cdots + x^{(n)}z^{(n)}) \
&= (f_1(x)x^{(1)})(f_1(z)z^{(1)}) + (f_1(x)x^{(2)})(f_1(z)z^{(2)}) + \cdots \
& \quad + (f_1(x)x^{(n)})(f_1(z)z^{(n)}) \
& \quad + (f_2(x)x^{(1)})(f_2(z)z^{(1)}) + (f_2(x)x^{(2)})(f_2(z)z^{(2)}) + \cdots \
& \quad + (f_2(x)x^{(n)})(f_2(z)z^{(n)}) + \cdots \
& \quad + (f_m(x)x^{(1)})(f_m(z)z^{(1)}) + (f_m(x)x^{(2)})(f_m(z)z^{(2)}) + \cdots \
& \quad + (f_m(x)x^{(n)})(f_m(z)z^{(n)})
\end{aligned}
  可得
\begin{aligned}
\phi'(x) &= (f_1(x)x^{(1)}, f_1(x)x^{(2)}, \cdots, f_1(x)x^{(n)}, \
& \quad f_2(x)x^{(1)}, f_2(x)x^{(2)}, \cdots, f_2(x)x^{(n)}, \
& \quad f_m(x)x^{(1)}, \cdots, f_m(x)x^{(n)})^T
\end{aligned}
  故存在从$R^n$到希尔伯特空间$\mathcal{H}$的映射$\phi'(x)$，使得
K(x,z) = (x \bullet z)^{k+1} = \phi'(x) \bullet \phi'(z)
  根据《矩阵分析》书中定理7.5.3：
> **7.5.3定理** 如果$A,B \in M_n$是半正定矩阵，则$A \bullet B$也是半正定矩阵，此外如果$A$和$B$都是正定矩阵，则$A \bullet B$也是正定矩阵。
> 其中，$A \bullet B$称为$A$和$B$的Hadamard乘积。
  由根据书中定理7.5，可得$K(x,z)=(x \bullet z)^{k+1}$是正定核函数。
  根据数学归纳法可得：
  当$p$是正整数，$x,z\in R^n$时，内积的正整数幂函数：$$K(x,z)=(x \bullet z)^p$$是正定核函数。
## 参考文献
【1】Roger A.Horn, Charles R.Johnson, 杨奇(译). 矩阵分析[M]. 2005(1):324