《统计学习方法》-习题2.3

2020-05-04 本文已影响0人 LuckilyHaveYou

题目：

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

必要性：
如果样本集是线性可分的，即存在一个分离平面 $wx+b = 0$
对于所有的正实例点 $x_+$ 有 $wx_++b>0$
对于所有的负实例点 $x_-$ 有 $wx_-+b<0$
设正实例点集合 $S_+$ ，其凸壳为 $conv(S)=\{x=\sum_{i=1}^k\lambda_ix_{+i}|\sum_{i=1}^k\lambda_i=1,\lambda_i\ge0,i=1,2...k\}$
将x带入平面,得到
$wx+b=w\sum_{i=1}^k\lambda_ix_{+i}+b=w\sum_{i=1}^k\lambda_ix_{+i}+\sum_{i=1}^k\lambda_i b$
$=\sum_{i=1}^k\lambda_i(wx_{+i}+b)$
因为 $\lambda_i\ge0$ 并且 $\sum_{i=1}^k\lambda_i=1$ 所以上式 $>0$
同理可以得到对于所有的负实例点，在平面 $wx+b<0$
分离平面也是正负实例点凸壳的分离平面。
充分性：
如果正负实例点构成的凸壳是互不相交的，则存在分离平面将正负实例点分离。即存在平面 $wx+b=0$ 可以将所有的凸壳构成的点进行分离。
分别取 $\lambda_i=1,\lambda_j=0,j\neq i$ ，分别得到了点 $x_i$ ，即对于所有的 $x_i$ ， $wx+b=0$ 也可以将其分离，所以样本集线性可分。