线性可分与凸壳

描述

题目出自《统计学习方法》 P36：设集合$S\subset R^n$ 是由$R^n$中的$k$个点所组成的集合，即$S=\{x_1,x_2,\cdots,x_k\}$，定义$S$的凸壳$conv(S)$为：

$$conv(S)=\{x=\sum_{i=1}^{k}\lambda_ix_i \Bigg | \sum_{i=1}^k\lambda_i=1,\lambda_i\ge0,i=1,2,\cdots,k \}$$

证明以下定理：样本集线性可分的充分必要条件是正实例点集所构成的凸壳与负实例点集所构成的凸壳互不相交。

上网查了一遍，只找到半份比较好的证明：http://blog.csdn.net/y954877035/article/details/52210734 对充分性证明起了很大作用（其实是本菜鸡整理补充了一下他的证明过程）。

必要性

必要性： 若样本集线性可分，则正实例点集所构成的凸壳与负实例点集所构成的凸壳互不相交。

采用反证法，假设超平面$f(\hat{x})=\hat{w}\cdot\hat{x}$能完全分开正负样本，即$f(x_+)>0$，$f(x_-)<0$。

假设正类凸壳和负类凸壳相交部分样本点为$z$ ，有定义可知：

$$z=\sum_{i=1}^{k_1}\lambda_ix_{+i}$$

其中$ \sum_{i=1}^k\lambda_i=1,\lambda_i\ge0,i=1,2,\cdots,k_1 $
即样本$z$分别可由正样本和负样本按线性加权表示。现考虑$f(z)$:

$$\begin{align*} f(z)&=f(\sum_{i=1}^{k_1}\lambda_ix_{+i})\\ &=\hat{w}\cdot\sum_{i=1}^{k_1}\lambda_ix_{+i}\\ &=\sum_{i=1}^{k_1}\lambda_ix_{+i}\cdot\hat{w}\\ &=\sum_{i=1}^{k_1}\lambda_if(x_{+i})>0 \end{align*}$$

同理可得，$f(z)<0$,矛盾，故必要性得证。

充分性

（该部分主要来源于http://blog.csdn.net/y954877035/article/details/52210734 特别感谢该CSDN博主！）

再证充分性：若正实例点集所构成的凸壳与负实例点集所构成的凸壳互不相交，则样本集线性可分。

从距离入手。定义两点间的距离为 $dist(x_1,x_2)=\sqrt{(x_1-x_2)\cdot(x_1-x_2)}=\Vert x_1-x_2\Vert _2$ ，也就是二范数。

定义凸壳间的距离为$dist(conv(S_+),conv(S_-))=min\{dist(x_+,x_-) \quad \big| \quad x_+\in conv(S_+),x_-\in conv(S_-) \}$ ，也就是两个凸壳上最接近的点之间的距离。下文记该点对为$x_{+0}$ 和$x_{-0}$ 。

那么显然：对任意$x_+\in conv(S_+),x_-\in conv(S_-)$ , $dist(x_+,x_-)\ge dist(conv(S_+),conv(S_-))=dist(x_{+0},x_{-0}) \tag{3.1}$

引理1：$dist(x_+,x_{-0})>dist(x_+,x_{+0})$ ,即正类凸壳上的任意点到负类凸壳的距离一定比该点到$x_{+0}$ 的距离大。

其实很显然。想象成过河的情景，你到对面岸的距离显然比你到自己这个岸边的距离要更远。然而证明起来还有点 非常费劲。。

反证法，假设$dist(x_+,x_{-0}) \le dist(x_+,x_{+0})$ ，又有式(2): $dist(x_+,x_{-0})d \ge dist(x_{+0},x_{-0})$ .

即$dist(x_{+0},x_{-0}) \le dist(x_+,x_{-0}) \le dist(x_+,x_{+0}) \tag{3.2}$

取

$$t=\frac{(x_{-0}-x_{+0})\cdot(x_+-x_{+0})}{\Vert x_+-x_{+0}\Vert _2^2}=\frac{\Vert x_{-0}-x_{+0}\Vert _2cos\theta}{\Vert x_+-x_{+0}\Vert _2}$$

由式(3.2)可知$t<1$ 。$\theta$="" 表示向量$\overrightarrow{="" x_{+0}="" x_{-0}}$="" 与向量$\overrightarrow{="" x_{+}}$="" 间的夹角。$\theta$="" 所对的边是$\overline{x_+x_{-0}}$="" ，由式(3.2)可知该边为最短的边，故$\theta$="" 小于$90^\circ$="" ,="" 故$t="">0$ 。

取 $z=tx_++(1-t)x_{+0}$ ，故点$z\in conv(S_+)$ 且在线段$\overline{x_{+0} x_+}$ 上。显然$dist(z,x_{-0})<dist(x_{+0},x_{-0})$ ,这与式(3.1)矛盾，引理得证。

下面开始正式证明。直接以线段$\overline{x_{+0}+x_{-0}}$ 的中垂超平面作为判决函数：

$$w=x_{+0}-x_{-0} \\b=\frac{x_{-0}\cdot x_{-0}-x_{+0}\cdot x_{+0}}{2}$$

考虑对任意正样本$x_+$：

$$\begin{align} w\cdot x_+ +b &=(x_{+0}-x_{-0})\cdot x_+ +\frac{x_{-0}\cdot x_{-0}-x_{+0}\cdot x_{+0}}{2}\\ &=\frac{2x_{+0}\cdot x_{+}-2x_{-0}\cdot x_{+}+x_{-0}\cdot x_{-0}-x_{+0}\cdot x_{+0}}{2}\\ &=\frac{dist(x_+,x_{-0})^2-dist(x_+,x_{+0})^2}{2}>0 \end{align}$$

同理，对任意负样本有$w\cdot x_-+b <0$ ，该数据集线性可分。

其实有个凸集分离定理知 直接就证完了，有兴趣的同学可以自行了解。。