统计学习方法-第二章课后习题答案整理

2.1Minsky和Papert指出：
感知机因为是线性模型，
所以不能表示复杂的函数，如异或。
验证感知机为什么不能表示异或
参考链接：
https://blog.****.net/yangfeisc/article/details/45486067

2.2，换下数据即可，具体代码实现参考：
https://blog.****.net/appleyuchi/article/details/82928881

2.3
样本集线性可分的充分必要条件是：
正实例点集构成的凸壳与负实例点集所构成的凸壳互不相交

首先是概念：
这里的凸壳≠凸集。
“相交”的意思是：一个样本点，既属于凸壳A，也属于凸壳B，
也就是说，某个样本点同时满足两个集合的约束条件。

统计学习方法-第二章课后习题答案整理
凸壳到底是一个什么鬼？？？？？
看下面的初中数学课件回顾一下：

证明如下：

必要性：线性可分->凸壳不相交

设数据集T中的正例点集为 $S_{+}$ ，
$S_{+}$ 的凸壳为 $conv(S_{+})$ ，
负实例点集为 $S_{-}$ ，
$S_{-}$ 的凸壳为 $conv(S_{-})$ ，
若T是线性可分的，则存在一个超平面: $w\cdot x +b =0$ 能够将 $S_{+}$ 和 $S_{-}$
完全分离。
假设对于所有的正例点 $x_{i}$ ，有:
$w\cdot x_{i}+b=\varepsilon_{i}$ 易知 $\varepsilon_{i}>0,i=1,2,\cdots,|S_{+}|$ 。
若 $conv(S_{+})$ 和 $conv(S_{-})$ 相交，即存在某个元素s，
同时满足 $s\in{conv(S_{+})}和s\in{conv(S_{-})}$ 。
对于 $conv(S_{+})$ 中的元素 $s^{+}$
有 $w\cdot s^{+}=w\cdot \sum^{k}_{i=1}\lambda_{i}x_{i}=\sum^{k}_{i=1}\lambda_{i}(\varepsilon_{i}-b)=\sum^{k}_{i=1}(\lambda_{i}\varepsilon_{i}-b\lambda_{i})$
注意，这里因为凸壳（convex hull）的性质，有：
$\sum_{i=1}^{k}\lambda_{i}=1$
所以上面的结果是：
$\sum^{k}_{i=1}(\lambda_{i}\varepsilon_{i})-b$

因此 $w\cdot s^{+}+b=\sum^{k}_{i=1}\lambda_{i}\varepsilon_{i}>0$ ，
同理对于 $S_{-}$ 中的元素 $s^{-}$ 有
$w\cdot s^{-}+b=\sum^{k}_{i=1}\lambda_{i}\varepsilon_{i}<0$ ，

线性可分条件下，假设两个凸壳相交，那么存在样本点s同时满足
$s\in{conv(S_{+})}$ 且 $s\in{conv(S_{-})}$
则 $w\cdot s^{+}+b=w\cdot s+b=\sum^{k}_{i=1}\lambda_{i}\varepsilon_{i}>0①$
且 $w\cdot s^{-}+b=w\cdot s+b=\sum^{k}_{i=1}\lambda_{i}\varepsilon_{i}>0②$
②违反了假设的前提：线性可分。
因为线性可分时，必须有②＜0
所以假设不成立，因此 $conv(S_{+})$ 和 $conv(S_{-})$ 必不相交
从而推出必要性：线性可分->凸壳不相交

充分性：凸壳不相交->线性可分

设数据集T中的正例点集为 $S_{+}，S_{+}$ 的凸壳为 $conv(S_{+})$ ，负实例点集为 $S_{-}，S_{-}$ 的凸壳为 $conv(S_{-})，且conv(S_{+})与conv(S_{-})$ 不相交，
定义两个点 $x_{1},x_{2}$ 的距离为
$dist(x_{1},x_{2})=||x_{1}-x_{2}||_{2}=\sqrt {(x_{1}-x_{2})\cdot (x_{1}-x_{2})}$
定义 $conv(S_{+})与conv(S_{-})$ 的距离为，
$dist(conv(S_{+}),conv(S_{-}))= \min||s_{+}-s_{-}||， s_{+}\in conv(S_{+}),s_{-}\in conv(S_{-})$

设 $x_{+}\in conv(S_{+})，x_{-}\in conv(S_{-})$ 且 $dist(x_{+},x_{-})=dist(conv(S_{+}),conv(S_{-}))$ 。
则对于任意正例点x有 $dist(x,x_{-})\geq dist(x_{+},x_{-})$ 。
注意，这里的 $(x_{+},x_{-})$ 是用来代表 $S_{+}$ 和 $S_{-}$ 最近距离的两个点。
同理，对于所有的负例点x有 $dist(x,x_{+})\geq dist(x,x_{-})$ 。
存在超平面 $w\cdot x+b=0$ 其中

$w=x_{+}-x_{-}$
$b=-\frac{x_{+}\cdot x_{+} - x_{-}\cdot x_{-}}{2}$
（以上就是两个技巧）

则对于所有的正例点x(易知 $w·x_{+} +b>0$ ，因此若 $x_{+}$ 属于正例点，则令 $x_{+}\neq x$ )，

$w\cdot x +b$
$=(x_{+}-x_{-})\cdot x-\frac{x_{+}\cdot x_{+} - x_{-}\cdot x_{-}}{2}$

$=x_{+}\cdot x -x_{-}\cdot x - \frac{x_{+}\cdot x_{+}-x_{-}\cdot x_{-}}{2}$

$=\frac{||x_{-}-x||_{2}^{2}-||x_{+}-x||_{2}^{2}}{2}$

$=\frac{dist(x,x_{-})^2-dist(x,x_{+})^2}{2}$
（这里我觉得不用搞得跟下面一样麻烦，只要分别在两个凸壳中各自取一个点，就能说明上面的式子的符号想相反的了，然后就得证了。）
若 $dist(x,x_{-})\leq dist(x,x_{+})$ ，
则 $dist(x,x_{-})\leq dist(x,x_{+}) \leq dist(x_{-},x_{+})$ ，
那么 $dist(S_{+},S_{-})< dist(x_{+},x_{-})$ (注：证明过程见下方)，
推出矛盾。
因此对所有的正例点， $w·x +b >0$ 成立。
同理，对所有的负例点， $w·x +b <0$ 成立。
至此，充分性：凸壳不相交->线性可分

补充：用反正法证明 $dist(x,x_{-})> dist(x,x_{+})$
证明：若 $dist(x,x_{-})\leq dist(x,x_{+})$ ，
则存在 $t=\frac{(x_{-}-x_{+})\cdot (x-x_{+})}{||x-x_{+}||_{2}^{2}}$ ，
令 $x^{'}=tx+(1-t)x_{+}$ ，则 $(x_{-}-x^{'})· (x_{+}-x)=0$ 。

易知 $t\leq 1$ 先证明0<t，我们可以将x,x_{+},x_{-}看作是空间中三个不同的点，三条边的长度分别为 $dist(x,x_{+}),dist(x,x_{-}),dist(x_{-},x_{+})$
由上文知 $dist(x,x_{+})\geq dist(x,x_{-})\geq dist(x_{-},x_{+})$
根据三角形的大边对应大角这一特性，很容易可以看出
$x_{+}-x与x_{+}-x_{-}之间的夹角小于90度，
因此t>0。
那么
$dist(x^{'},x_{-})<dist(x_{+},x_{-})$ ，
又因为 $x^{'}$ 必在 $conv(S_{+})$ 内部，
所以推出矛盾。

本文来自蓝色骨头零号的**** 博客，全文地址请点击：https://blog.****.net/y954877035/article/details/52210734?utm_source=copy

统计学习方法-第二章课后习题答案整理

证明如下：

相关推荐