因此取等号，必有$w_1^*=\pm 1(w_2^*)=w_2^*$，负号不是解，所以w解唯一。因此，两个最优解$(w,b_1^*)$，$(w,b_2^*)$,还有证明偏置相等，设$x_1^{\'}$,$x_2^{\'}$是集合$\{x_i|y_i=1\}$中分别满足$(w,b_1^*)$，$(w,b_2^*)$不等式成立两个点，而$x_1^{\'\'}$,$x_2^{\'\'}$是集合$\{x_i|y_i=-1\}$的两个点，那么有
\[(w^{\mathrm{T}}x_1^{\'}+b_1^*)-1=0\\
(w^{\mathrm{T}}x_2^{\'}+b_2^*)-1=0\]
\[-(w^{\mathrm{T}}x_1^{\'\'}+b_1^*)-1=0\\
-(w^{\mathrm{T}}x_2^{\'\'}+b_2^*)-1=0\]
因此得到
\[b_1^*=-\frac{1}{2}(w^{\mathrm{T}}x_1^{\'}+w^{\mathrm{T}}x_1^{\'\'})\\
b_2^*=-\frac{1}{2}(w^{\mathrm{T}}x_2^{\'}+w^{\mathrm{T}}x_2^{\'\'})\]
因此得到
\[b_1^*-b_2^*=-\frac{1}{2}[w^{\mathrm{T}}(x_1^{\'}-x_2^{\'})+w^{\mathrm{T}}(x_1^{\'\'}-x_2^{\'\'})]\]
又因为
\[(w^{\mathrm{T}}x_2^{\'}+b_1^*)\geq 1=w^{\mathrm{T}}x_1^{\'}+b_1^*\\
(w^{\mathrm{T}}x_1^{\'}+b_1^*)\geq 1=w^{\mathrm{T}}x_2^{\'}+b_1^*\]
因此$w^{\mathrm{T}}(x_1^{\'}-x_2^{\'})=0$，同理$w^{\mathrm{T}}(x_1^{\'\'}-x_2^{\'\'})=0$，所以$b_1^*=b_2^*$。
支持向量和间隔边界：
支持向量：训练数据集中样本点与分离超平面最近的样本点是支持向量，而支持向量是使得约束条件等号成立
\[y_i(w^{\mathrm{T}}x_i+b)-1=0\]
上图H1和H2两个平面上的点就是支持向量，二者距离称为间隔，二者平行，所以间隔大小等于$\frac{2}{||w||}$。
支持向量非常少，因此支持向量机由少数重要的训练样本组成的。改变支持向量以外的点不改变解，但是增减支持向量将会改变。
§12.3 线性支持向量机学习的对偶法
例子：如图所示的训练数据集，正样本点,$\{[3\quad 3]^{\mathrm{T}}|y_1=1\}$，$\{[4\quad 3]^{\mathrm{T}}|y_2=1\}$,负样本点$\{[1\quad 1]^{\mathrm{T}}|y_3=-1\}$。那么构成了如下优化问题
\[\underset{w,b}{min}\quad \frac{1}{2}||w||^2\\
s.t. \quad 3w_1+3w_2+b-1\geq 0\\
4w_1+3w_2+b-1\geq 0\\
-w_1-w_2-b-1\geq 0\]
求解得到超平面
\[\frac{1}{2}w_1+\frac{1}{2}w_2-2=0\]
下面引用对偶算法，一是对偶算法有时候比上面原优化问题好解决，二是可以自然引入核方法，推广到非线性分类问题。
对偶算法求
\[\underset{w,b}{min}\quad \frac{1}{2}||w||^2\\
s.t.\quad y_i(w^{\mathrm{T}}x_i+b)-1\geq 0,x=1,2,\cdots,N\]
首先构建Lagrange函数，对于每一个约束都引入一个Lagrange乘子
\[L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^N\alpha_iy_i(w^{\mathrm{T}}x_i+b)+\sum_{i=1}^N\alpha_i\]
根据对偶性，原始问题的对偶问题是
\[\underset{\alpha}{max}\underset{w,b}{min}\quad L(w,b,\alpha)\]
因此首先求最小
\[\bigtriangledown_wL(w,b,\alpha)=w-\sum_{i=1}^N\alpha_iy_ix_i=0\\
\bigtriangledown_bL(w,b,\alpha)=-\sum_{i=1}^N\alpha_iy_i=0\]
将$w=\sum_{i=1}^N\alpha_iy_ix_i$，且由于$\sum_{i=1}^N\alpha_iy_i=0$，得到
\[minL(w,b,\alpha)=\frac{1}{2}\sum_{i=1}^{N}\sum_{i=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_iy_i\left ( \sum_{i=1}^{N}\alpha_jy_jx_j\cdot x_i+b\right )+\sum_{i=1}^{N}\alpha_i\\
=-\frac{1}{2}\sum_{i=1}^{N}\sum_{i=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^{N}\alpha_i\]
其次对于Lagrange乘子求最大
\[\underset{\alpha}{max}-\frac{1}{2}\sum_{i=1}^{N}\sum_{i=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^{N}\alpha_i\\
s.t.\quad \sum_{i=1}^{N}\alpha_iy_j=0\\
\quad \quad \quad \alpha_i\geq 0\]
也等价于对偶问题
\[\underset{\alpha}{min}\frac{1}{2}\sum_{i=1}^{N}\sum_{i=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_i\\
s.t.\quad \sum_{i=1}^{N}\alpha_iy_j=0\\
\quad \quad \quad \alpha_i\geq 0\]
定理：设$\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_i)$为上面对偶问题的解，则存在下标
\[\alpha_j> 0\]
求得原始最优化问题的解，KKT条件
\[\bigtriangledown_wL(w,b,\alpha)=w^*-\sum_{i=1}^{N}\alpha_i^*y_ix_i=0\\
\bigtriangledown_bL(w,b,\alpha)=-\sum_{i=1}^{N}\alpha_i^*y_i=0\\
\alpha_i^*(y_i(w^{\mathrm{T}}x_i+b)-1)=0\\
y_i(w^{\mathrm{T}}x_i+b)-1\geq 0\\
\alpha_i^* >0\]
至少存在一个$\alpha_j >0$，对于此下标
\[y_j(w^*x_j+b^*)-1= 0\]
将$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$代入得到
\[y_j(\sum_{i=1}^{N}\alpha_i^*y_ix_i\cdot x_j+b^*)-1=0\\
y_jb^*=1-y_j(\sum_{i=1}^{N}\alpha_i^*y_ix_i\cdot x_j)\\
b^*=y_j-(\sum_{i=1}^{N}\alpha_i^*y_ix_i\cdot x_j)\]
因此超平面为
\[w^*x+b^*=0\\
\sum_{i=1}^{N}\alpha_i^*y_i(x\cdot x_i)+b^*=0\]
而且支持向量一定在间隔边界上，所以满足
\[w^*x_i+b^*\mp 1=0\\\]