感知机

作者: 冷寒香 | 来源:发表于2020-04-05 20:17 被阅读0次

感知机
1、深度学习入门-感知机
深度学习入门(1)感知机
神经网络概述
动手学深度学习(三) 多层感知机
多层感知机 2020-02-18
多层感知机
神经网络
动手学深度学习笔记（二）
人工智能入门

1.前言

感知机1957年由Rosenblatt提出，是神经网络与支持向量机（Support Vector Machine, SVM）的基础。

2.基础知识

2.1.超平面

超平面是指n维线性空间中维度为n-1的子空间。它可以把线性空间分割成不相交的两部分。

例如：一维直线可以通过零维点分割成两部分。二维平面可以通过一维直线分割成两部分。三维空间中通过二维平面分割成两部分。

法向量是垂直于超平面的向量

在 $n$ 维空间中，超平面的方程:
$\omega_1x_1+\omega_2x_2+...+\omega_nx_n=b$
其中超平面内任意一点记为 $x=(x_1,x_2,...,x_n)$

现在任意选择超平面内的两个点 $x,x'$ ，向量 $\boldsymbol{xx'}=(x_1-x'_1,x_2-x'_2,...,x_n-x'_n)$

由于 $x,x'$ 在超平面内，所以满足：
$\omega_1x_1+\omega_2x_2+...+\omega_nx_n=b$

$\omega_1x'_1+\omega_2x'_2+...+\omega_nx'_n=b$

两式相减得：
$\omega_1(x_1-x'_1)+\omega_2(x_2-x'_2)+...+\omega_n(x_n-x'_n)=0$
即：
$\boldsymbol{\omega} \cdot \boldsymbol{xx'} = 0$
其中
$\boldsymbol{\omega}=(\omega_1,\omega_2,...,\omega_n)$
由于 $\boldsymbol{xx'}$ 是超平面内任意一个向量，所以 $\boldsymbol{\omega}$ 是超平面的法向量，超平面可写成：
$\boldsymbol{\omega} \cdot \boldsymbol{x} + b = 0$

2.2.点到超平面的距离

现需要求超平面外某一点 $\boldsymbol{x}$ 离超平面的距离 $d$

距离 $d$ 为红色部分，取平面任意一点 $\boldsymbol{x'}$ ，由三角函数可知：
$cos(\theta)= \frac {d} { || \boldsymbol{x} - \boldsymbol{x'} || }$
而且 $\boldsymbol{xx'}$ 与 $\boldsymbol{\omega}$ 所成夹角正好就是 $\theta$ ，所以两向量点积为：
$|(\boldsymbol{x} - \boldsymbol{x'} ) \cdot \boldsymbol{\omega}|=||\boldsymbol{x} - \boldsymbol{x'} || \cdot ||\boldsymbol{\omega}|| \cdot cos(\theta)$
由于法向量可能反向，所以给左边加上绝对值，联立可得:
$d=|| \boldsymbol{x} - \boldsymbol{x'} ||cos(\theta) =\frac {|(\boldsymbol{x} - \boldsymbol{x'} ) \cdot \boldsymbol{\omega}|}{|| \boldsymbol{\omega} ||} = \frac {|\boldsymbol{x} \cdot \boldsymbol{\omega} - \boldsymbol{x'} \cdot \boldsymbol{\omega}|}{|| \boldsymbol{\omega} ||}$
由于 $\boldsymbol{x'}$ 在平面内，满足 $\boldsymbol{\omega} \cdot \boldsymbol{x'} + b = 0$ ，带入上式得任意一点到超平面距离公式：
$d=\frac {|\boldsymbol{\omega} \cdot \boldsymbol{x} + b|}{|| \boldsymbol{\omega} ||}$

3.感知机模型

假设输入空间（特征空间）是 $X \subseteq R^n$ ，输出空间是 $Y={-1,+1}$ 。输出 $x \in X$ 表示实例的特征向量，对应于输入空间的点，输出实例的类别。由输出空间到输出空间的函数为：
$f(x)=sign(\boldsymbol\omega \cdot \boldsymbol x + b)$
称为感知机。其中 $\boldsymbol \omega$ 和 $\boldsymbol x$ 称为感知机模型参数， $\boldsymbol \omega \in R^n$ 叫做权值或者权值向量， $b \in R$ 称为偏置。

$sign$ 函数为符号函数，即:
$sign(x) = \left \{ \begin {matrix} +1 & x \ge 0\\ -1 & x < 0 \end {matrix} \right.$
感知机是一种线性分类模型，属于判别模型。感知机模型的假设空间是定义在特征空间中的所有线性分类模型或线性分类器，即函数集合 $f|f(x) = \omega \cdot x + b$ 。

如图，这个超平面将两类不同的点分成正、负两类，因此也被称之为分离超平面。对于感知机而言，目的就是求出该超平面，之后对于给定的输入，就可以判断该点到底是属于哪一个类别。

4.感知机学习策略

4.1.线性可分

数据集的线性可分性：给定数据集 $T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$ ，其中 $x_i \in X = R^n,y_i \in Y = {-1,1}$ ，如果存在某个超平面 $S$ ，能够将数据集的正实例点和负实例点完全正确划分到超平面的两侧，即对于所有 $y_i=+1$ 的点满足 $\omega \cdot x + b > 0$ ，对于所有 $y_i = -1$ 的点满足 $\omega \cdot x + b < 0$ ，则称数据集 $T$ 为线性可分数据集，否则称之为线性不可分。

4.2.感知机学习策略

目标：找到超平面，也就是确定参数 $\omega,b$ ，我们需要定义学习策略，即定义经验损失函数，并将损失函数极小化。

损失函数：误分类点到超平面S的总距离。也就是误分类点的距离越小，损失函数就越小，分类效果就越好。

由之前可知任意一点 $x_0$ 到超平面距离
$d=\frac{|\boldsymbol{\omega} \cdot \boldsymbol{x_0} + b|}{|| \boldsymbol{\omega} ||}$
对于分类正确的点满足 $y(\omega \cdot x + b) > 0$ ，因此对于误分类点 $(x_i,y_i)$
$-y_i(\omega \cdot x + b) > 0(y_i = 1 \ or \ y_i = -1)$
所以对于误分类点的距离可以写成
$-\frac{y_i(\omega \cdot x_i + b)}{|| \omega ||}$
那么所有的误分类点到超平面 $S$ 的距离是：
$-\frac{1}{|| \omega ||} \sum_{x_i \in M}y_i(\omega \cdot x_i + b)$
其中 $M$ 是误分类点的集合。

然后忽略 $-\frac{1}{|| \omega ||}$ ，定义感知机学习损失函数：
$L(\omega, b) =-\sum_{x_i \in M}y_i(\omega \cdot x_i + b)$
由函数可知，损失函数非负，当正确分类时，损失函数为0。

4.3.为什么可以忽略 $-\frac{1}{|| \omega ||}$

本答案综合网上回答

不忽略的话计算的是几何间隔，忽略的话计算的是函数间隔。（具体概念此处不展开）

1、由于我们只需要进行分类即可，忽略之后不会影响误分类点的判定。

2、因为最终损失函数变成了0，所以与 $-\frac{1}{|| \omega ||}$ 大小是无关的，加上反而计算麻烦。

5.感知机学习算法

5.1.感知机学习算法原始形式

感知机学习算法是对以下最优化问题的算法。给定一个训练数据集
$T = \{ (x_1,y_1),(x_2,y_2), ... ,(x_N,y_N)\}$
其中 $x_i \in X = R^n , y_i = Y = \{ -1, +1 \}$ ，求参数 $\omega, b$ ，使其为以下损失函数极小化问题的解
$\underset{ \omega, b }{min} L(\omega, b) = -\sum_{x_i \in M}y_i(\omega \cdot x_i + b)$
其中 $M$ 是误分类点的集合。

感知机学习算法是误分类驱动的，具体采用随机梯度下降法。首先任意选择一个超平面 $\omega_0, b_0$ ，然后用梯度下降法不断极小化目标函数。极小化过程不是一次使 $M$ 中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。

假设误分类点集合 $M$ 是固定的，那么损失函数 $L(\omega, b)$ 的梯度由
$\bigtriangledown _\omega L(\omega, b) = -\sum_{x_i \in M}y_ix_i$

$\bigtriangledown _b L(\omega, b) = -\sum_{x_i \in M}y_i$

随机选取一个误分类点 $(x_i,y_i)$ ，对 $\omega, b$ 进行更新：
$\omega \leftarrow \omega + \eta y_i x_i$

$b \leftarrow b + \eta y_i$

其中 $\eta \in (0,1]$ 是步长，也叫学习率。通过迭代可以使得损失函数不断减少，直到为0。

算法流程：

输入：线性可分的训练数据集 $T = \{ (x_1,y_1), (x_2,y_2), ... , (x_N,y_N) \}$ ，其中 $x_i \in X = R^n ,$ $y_i = Y = \{ -1, +1 \}$ ，学习率 $\eta ( \eta \in (0,1] )$

输出： $\omega, b$ ；感知机模型 $f(x) = sign(\omega \cdot x + b)$

选取初值 $\omega_0, b_0$
在训练集中选取数据 $(x_i, y_i)$
如果 $y_i(\omega \cdot x + b) \le 0$ ，即该点误分类，则更新 $\omega, b$ ：
$\omega \leftarrow \omega + \eta y_i x_i$

$b \leftarrow b + \eta y_i$
转到2，直到不存在误分类点。

5.2.算法的收敛性

为了便于推导，将偏置 $b$ 并入权重向量 $\omega$ ，记作 $\hat{\omega}=(\omega^T, b)^T$ ，同样的也将输入向量进行扩充，加入常数1，记作 $\hat{x} = (x^T, 1)^T$ ，这样 $\hat{x} \in R^{n+1}, \hat{\omega} \in R^{n+1}$ ，显然：
$\hat{\omega} \cdot \hat{x}=\omega \cdot x + b = 0$

设训练数据集 $T = \{ (x_1,y_1), (x_2,y_2), ... , (x_N,y_N) \}$ 是线性可分的，其中 $x_i \in X = R^n ,$ $y_i = Y = \{ -1, +1 \}$ ，则

（1）存在满足条件 $|| \hat{\omega}_{opt} ||=1$ 的超平面 $\hat{\omega}_{opt} \cdot \hat{x}=\omega_{opt} \cdot x + b_{opt} = 0$ 将训练数据集完全正确分开；且存在 $\gamma > 0$ ，对所有 $i=1,2,...,N$ 都满足：
$y_i(\hat{\omega}_{opt} \cdot \hat{x}_i) = y_i(\omega_{opt} \cdot x_i + b_{opt}) \ge \gamma$
（2）令 $R=\underset{1 \le i \le N}{ max }|| \hat{x}_i ||$ ，则感知机算法5.1在训练数据集上的误分类次数 $k$ 满足不等式
$k \le ( \frac {R} { \gamma} )^2$
证明：

（1）由于训练数据集是线性可分的，按照定义可知存在超平面可将训练数据集完全分开，取此超平面为 $\hat{\omega}_{opt} \cdot \hat{x}=\omega_{opt} \cdot x + b_{opt} = 0$ ，使 $|| \hat{\omega}_{opt} ||=1$ 。由于对 $i=1,2,...,N$ 均有：
$y_i(\hat{\omega}_{opt} \cdot \hat{x}_i) = y_i(\omega_{opt} \cdot x_i + b_{opt}) > 0$
所以存在
$\gamma = \underset{i}{min} \{ y_i (\omega_{opt} \cdot x_i + b_{opt} ) \}$
使得
$y_i(\hat{\omega}_{opt} \cdot \hat{x}_i) = y_i(\omega_{opt} \cdot x_i + b_{opt}) \ge \gamma$
（2）感知机算法从 $\hat{\omega}_{0} = 0$ 开始，如果实例被误分类，则更新权重。令 $\hat{\omega}_{k-1}$ 是第 $k$ 个误分类实力之前的扩充权重向量，即
$\hat{\omega}_{k-1} = (\omega_{k-1}^T,b_{k-1})^T$
则第 $k$ 个误分类实例的条件是：
$y_i(\hat{\omega}_{k-1} \cdot \hat{x}_{i}) = y_i(\omega_{k-1} \cdot x_i + b_{k-1}) \le 0$
如果 $(x_i,y_i)$ 是被 $\hat{\omega}_{k-1} = (\omega_{k-1}^T,b_{k-1})^T$ 误分类的数据，则 $\omega$ 和 $b$ 的更新是:
$\omega _k \leftarrow \omega_{k-1} + \eta y_ix_i$

$b_k \leftarrow b_{k-1} + \eta y_i$

即
$\hat \omega _k = \hat {\omega} _{k-1} + \eta y_i \hat{x}_i$
然后推导两个不等式：
$\hat \omega _k \cdot \hat{\omega}_{opt} \ge k \eta \gamma$

$|| \hat{\omega} _k ||^2 \le k \eta ^2 R^2$

首先推导 $\hat \omega _k \cdot \hat{\omega}_{opt} \ge k \eta \gamma$ ：

由于 $\hat \omega _k = \hat {\omega} _{k-1} + \eta y_i \hat{x}_i$ ，所以
$\hat \omega _k \cdot \hat{\omega}_{opt} = \hat {\omega} _{k-1} \cdot \hat{\omega}_{opt} + \eta y_i\hat{\omega}_{opt} \cdot \hat{x}_i \ge \hat {\omega} _{k-1} \cdot \hat{\omega}_{opt} + \eta \gamma$
根据这个递推式可知：
$\hat \omega _k \cdot \hat{\omega}_{opt} \ge \hat {\omega} _{k-1} \cdot \hat{\omega}_{opt} + \eta \gamma \ge \hat {\omega} _{k-2} \cdot \hat{\omega}_{opt} + 2\eta \gamma \ge ... \ge k \eta \gamma$
然后推导 $|| \hat{\omega} _k ||^2 \le k \eta ^2 R^2$ ：

由于 $\hat \omega _k = \hat {\omega} _{k-1} + \eta y_i \hat{x}_i$ ，所以
$|| \hat \omega _k ||^2 = || \hat {\omega} _{k-1} + \eta y_i \hat{x}_i ||^2 =|| \hat \omega _{k-1} ||^2 + 2 \eta y_i \hat {\omega} _{k-1} \cdot \hat{x}_i + \eta^2 ||\hat x_i||^2 \\ \le || \hat \omega _{k-1} ||^2 + \eta^2 ||\hat x_i||^2 \\ \le || \hat \omega _{k-1} ||^2 + \eta^2 R^2$
根据这个递推式可知
$|| \hat \omega _k ||^2 \le || \hat \omega _{k-1} ||^2 + \eta^2 R^2 \le || \hat \omega _{k-2} ||^2 + 2\eta^2 R^2 \le ... \le k\eta^2 R^2$
最后：
$k \eta \gamma \le \hat \omega _k \cdot \hat{\omega}_{opt} \le ||\hat \omega _k|| \ ||\hat{\omega}_{opt}||$
由于前提条件 $||\hat{\omega}_{opt}|| = 1$ ，所以：
$k \eta \gamma \le ||\hat \omega _k|| \le \sqrt{k} \eta R$
所以
$k \le ( \frac {R} {\gamma} ) ^2$
最终得证。

由上述可知，误分类的次数 $k$ 是存在上界的，经过有限次搜索可以找到将训练数据完全正确分开的分离超平面。

5.3.感知机学习算法对偶形式

对偶形式的基本想法是，将 $\omega$ 和 $b$ 表示为实例 $x_i$ 和标记 $y_i$ 的线性组合的形式，通过求解其系数而求得 $\omega$ 和 $b$ 。

原始形式是设置初始值 $\omega_0$ 和 $b_0$ 均为0，对于误分类点 $(x_i,y_i)$ 进行更新：
$\omega \leftarrow \omega + \eta y_i x_i$

$b \leftarrow b + \eta y_i$

逐步修改 $\omega,b$ ，这样可以发现对于 $\omega$ 来说，就是 $y_ix_i$ 的线性组合，那么我们假设点 $(x_i,y_i)$ 误分类的次数记为 $n_i$ ，那么记 $\alpha_i = \eta n_i$ ，这样最后的 $\omega,b$ 为：
$\omega = \sum_{i=1}^N \alpha_i y_i x_i$

$b = \sum_{i=1}^N \alpha_i y_i$

这里 $\alpha_i \ge 0,i=1,2,...,N$ 。

算法流程：

输入：线性可分的训练数据集 $T = \{ (x_1,y_1), (x_2,y_2), ... , (x_N,y_N) \}$ ，其中 $x_i \in X = R^n ,$ $y_i = Y = \{ -1, +1 \}$ ，学习率 $\eta ( \eta \in (0,1] )$

输出： $\alpha,b$ ；感知机模型
$f(x)=sign(\sum_{j=1}^N \alpha_j y_j x_j \cdot x + b)$
其中 $\alpha = (\alpha_1, \alpha_2, ..., \alpha_N) ^ T$

$\alpha \leftarrow 0, b \leftarrow 0$
在训练集中选取数据 $(x_i, y_i)$
如果
$y_i (\sum_{j=1}^N \alpha_j y_j x_j \cdot x_i + b) \le 0$
更新
$\alpha_i \leftarrow \alpha_i + \eta$

$b \leftarrow b + \eta y_i$
转至2直到不存在误分类点

对偶形式中训练实例以内积的形式出现，为了方便，可以预先将训练集中两两内积结果计算出来，也就是Gram矩阵。
$G=[x_i \cdot x_j]_{N \times N}$
两种形式的比较

原始形式，对于误分类点的判定是：
$y_i(\omega \cdot x + b) \le 0$
时间复杂度是 $O(n)$ ， $n$ 为向量维度，之后更新 $\omega,b$ 时间复杂度是 $O(1)$ ，所以一次迭代的时间复杂度是 $O(n)$

对偶形式，对于误分类点的判定是：
$y_i (\sum_{j=1}^N \alpha_j y_j x_j \cdot x_i + b) \le 0$
由于提前求出两两点积，也就是 $x_i \cdot x_j$ 的时间复杂度是 $O(1)$ 查表可知，更新 $\alpha ,b$ 时间复杂度是 $O(1)$ ，所以一次迭代的时间复杂度是 $O(N)$ ， $N$ 是样本个数。

如果特征空间维度 $n$ 大于训练集样本数量 $N$ 时，使用对偶形式是更优的。

6.代码实践

6.1.例2.1

给定正例点 $x_1=(3,3)^T,x_2=(4,3)^T$ ，负例点 $x_3=(1,1)^T$ ，利用感知机学习算法的原始形式求感知机模型 $f(x)=sign(\omega \cdot x + b)$ 。这里 $\omega=(\omega^{(1)} , \omega^{(2)} )^T , x=(x^{(1)}, x^{(2)})^T$ 。

感知机示例

计算过程可以参考《统计学习方法》P40-41

代码

附加文件2_1.csv

x1,x2,y
3,3,1
4,3,1
1,1,-1

导入库，读取文件

import numpy as np
import pandas as pd
##读取文件
df = pd.read_csv('2_1.csv', encoding='utf-8')
print(df)
'''
输出:
   x1  x2  y
0   3   3  1
1   4   3  1
2   1   1 -1
'''

点的分布图

import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
%matplotlib inline
plt.figure('点分布')
#绘制Positive的点
plt.scatter(df[df.y==1]['x1'].values, df[df.y==1]['x2'].values,color='red',marker='o',label='Positive')
#绘制Negative的点
plt.scatter(df[df.y==-1]['x1'].values, df[df.y==-1]['x2'].values,color='blue',marker='x',label='Negative')
plt.xlabel('x1')
plt.ylabel('x2')
plt.legend(loc = 'upper left')
plt.show()

点的分布图

当前样本的 $x,y$

x = df.values[::,:-1:]
y = df.values[::,-1::]
n = df.shape[1] - 1#获取特征数量
m = df.shape[0]#样本数量
print(x)
print(y)
'''
输出:
[[3 3]
 [4 3]
 [1 1]]
[[ 1]
 [ 1]
 [-1]]
'''

开始训练

#初始化w,b
w = np.zeros(n, dtype=int)
b = 0
eta = 1#学习率
#print(n,m)
#不断迭代
Time = 0
while True:
    update = False
    for i in range(m):
        Time
        #满足则说明分类错误，进行梯度下降
        if y[i] * (w.dot(x[i])+b) <= 0:
            w = w + eta * y[i] * x[i]
            b = b + eta * y[i]
            update = True
            print(w, b)
            
    
    #如果没有更新，说明全部分类正确，直接
    if Time > 10**9 or update == False:
        break
'''
输出:
[3 3] [1]
[2 2] [0]
[1 1] [-1]
[0 0] [-2]
[3 3] [-1]
[2 2] [-2]
[1 1] [-3]
'''

绘制结果

def predict(all):
    return np.sign(all.dot(w.T) + b)
    ans = np.array([], dtype = int)
    for every in all:
        if w.dot(every)+b < 0:
            ans = np.append(ans, -1)
        else:
            ans = np.append(ans, 1)
    return ans

def plot_decision_regions(x, y):
    x1_min,x2_min = x.min(axis = 0)-1
    x1_max,x2_max = x.max(axis = 0)+1
    x1 = np.linspace(x1_min, x1_max, 500)
    x2 = np.linspace(x2_min, x2_max, 500)
    x1, x2=np.meshgrid(x1, x2) # 生成网格采样点
    x_show = np.stack((x1.flat, x2.flat), axis=1)  # 测试点
    y_predict=predict(x_show)##将所有点求出正确的y
    colors = ('lightgreen', 'LightPink', 'red', 'gray', 'cyan')
    cmap = ListedColormap(colors[:len(np.unique(y))])

    plt.pcolormesh(x1, x2, y_predict.reshape(x1.shape), cmap=cmap)
    plt.xlim(x1.min(), x1.max())
    plt.ylim(x2.min(), x2.max())
    #绘制Positive的点
    plt.scatter(df[df.y==1]['x1'].values, df[df.y==1]['x2'].values,color='red',marker='o',label='Positive')
    #绘制Negative的点
    plt.scatter(df[df.y==-1]['x1'].values, df[df.y==-1]['x2'].values,color='green',marker='x',label='Negative')

    plt.xlabel('x1')
    plt.ylabel('x2')
    plt.legend(loc = 'upper left')
    plt.show()
    
    
predict(x)
plot_decision_regions(x,y)

分类结果

6.2.例2.2

计算过程可以参考《统计学习方法》P45

6.3.鸢尾花

数据下载

链接：https://pan.baidu.com/s/1icV0yZmyIp0cCZHZhNM3tQ 提取码：bc0m

导入库，读取文件

import numpy as np
import pandas as pd
df = pd.read_csv('iris2.data')

点的分布图

import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
%matplotlib inline

#绘制Iris-setosa的点
plt.scatter(df[df.Class=='Iris-setosa']['sepal_len'].values, df[df.Class=='Iris-setosa']['petal_len'].values,color='green',marker='o',label='Iris-setosa')
#绘制Iris-versicolor的点
plt.scatter(df[df.Class=='Iris-versicolor']['sepal_len'].values, df[df.Class=='Iris-versicolor']['petal_len'].values,color='red',marker='x',label='Iris-versicolor')

plt.xlabel('sepal_len')
plt.ylabel('petal_len')
plt.legend(loc = 'upper left')
plt.show()

点的分布图

当前样本的 $x,y$

x = df.values[::,0:-1:2] ##此处只取第0列和第3列
y = df.values[::,-1::]
y[y=='Iris-setosa'] = -1
y[y=='Iris-versicolor'] = 1
x = np.array(x, dtype=float)
y = np.array(y, dtype=float)

n = 2#获取特征数量
m = df.shape[0]#样本数量

#初始化w,b
w = np.random.random(n)
b = 0
eta = 1#学习率

开始训练

#不断迭代
Time = 0
while True:
    update = False
    for i in range(m):
        Time
        #满足则说明分类错误，进行梯度下降
        if y[i] * (w.dot(x[i])+b) <= 0:
            w = w + eta * y[i] * x[i]
            b = b + eta * y[i]
            update = True
            print(w, b)
            
    
    #如果没有更新，说明全部分类正确，直接
    if Time > 10**9 or update == False:
        break
'''
输出:
[-4.31809634 -0.81533251] [-1.]
[2.68190366 3.88466749] [0.]
[-2.41809634  2.48466749] [-1.]
[4.58190366 7.18466749] [0.]
[-0.51809634  5.78466749] [-1.]
[-5.41809634  4.38466749] [-2.]
[1.58190366 9.08466749] [-1.]
[-3.51809634  7.68466749] [-2.]
'''

绘制结果

def predict(all):
    return np.sign(all.dot(w.T) + b)
    ans = np.array([], dtype = int)
    for every in all:
        if w.dot(every)+b < 0:
            ans = np.append(ans, -1)
        else:
            ans = np.append(ans, 1)
    return ans

def plot_decision_regions(x, y):
    x1_min,x2_min = x.min(axis = 0)-1
    x1_max,x2_max = x.max(axis = 0)+1
    x1 = np.linspace(x1_min, x1_max, 500)
    x2 = np.linspace(x2_min, x2_max, 500)
    x1, x2=np.meshgrid(x1, x2) # 生成网格采样点
    x_show = np.stack((x1.flat, x2.flat), axis=1)  # 测试点
    y_predict=predict(x_show)##将所有点求出正确的y
    colors = ('lightgreen', 'LightPink', 'red', 'gray', 'cyan')
    cmap = ListedColormap(colors[:len(np.unique(y))])
    
    plt.pcolormesh(x1, x2, y_predict.reshape(x1.shape), cmap=cmap)
    plt.xlim(x1.min(), x1.max())
    plt.ylim(x2.min(), x2.max())
    #绘制Iris-setosa的点
    plt.scatter(df[df.Class=='Iris-setosa']['sepal_len'].values, df[df.Class=='Iris-setosa']['petal_len'].values,color='green',marker='o',label='Iris-setosa')
    #绘制Iris-versicolor的点
    plt.scatter(df[df.Class=='Iris-versicolor']['sepal_len'].values, df[df.Class=='Iris-versicolor']['petal_len'].values,color='red',marker='x',label='Iris-versicolor')

    plt.xlabel('sepal_len')
    plt.ylabel('petal_len')
    plt.legend(loc = 'upper left')
    plt.show()

plot_decision_regions(x,y)

分类结果图

7.思考题

7.1.习题2.1

问：感知机为什么不能表示异或？

答：因为异或线性不可分。

$x_1$	$x_2$	$x_1 \otimes x_2$
0	0	0
0	1	1
1	0	1
1	1	0

感知机模型：
$f(x)=sign(\omega \cdot x + b)$
在本题中可以定义 $sign(0)=-1$

异或运算

可以将异或的四种情况绘制成上图，可发现线性不可分。

7.2.习题2.2

问：模仿例题2.1，构建从训练数据集求解感知机模型的例子。

略，直接可以参考第6节代码实践。

7.3.习题2.3

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

凸壳

设集合 $S \in R^n$ ，是由 $R^n$ 中的 $k$ 个点所组成的集合，即 $S = {x_1, x_2, ..., x_n}$ 。定义 $S$ 的凸壳 $conv(S)$ 为：
$conv(S) = \{x = \sum_{i=1}^k \lambda_i x_i | \sum_{ i=1 }^k \lambda_i = 1, \lambda_i \ge 0 \}$
凸壳是一个集合，包含最外层的“壳”，还包括所有在“壳”内的所有元素。

凸壳

线性可分

概念见4.1

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

设数据集 $T$ 中的正实例点为 $S_+$ ， $S_+$ 的凸壳为 $conv(S_+)$ ，负实例点为 $S_-$ ， $S_-$ 的凸壳为 $conv(S_-)$ 。

若数据集线性可分，则一定存在超平面：
$\omega \cdot x + b = 0$
能够将 $S_+,S_-$ 分离。

假设对所有正实例点 $x^+_i$ 有：
$\omega \cdot x^+_i + b = \xi_i$
显然 $\xi_i > 0$ 。

假设对所有负实例点 $x_i$ 有：
$\omega \cdot x^-_i + b = \eta_i$
显然 $\eta_i < 0$ 。

对于凸壳中的点 $s$ 而言：
$\omega \cdot s = \omega \cdot \sum_{i=1}^k \lambda_i x_i = \sum_{i=1}^k \lambda_i \omega \cdot x_i$
对于 $S_+$ 凸壳中的所有点 $s^+ \in conv(S_+)$ 有：
$\omega \cdot s^+ = \sum_{i=1}^k \lambda_i (\xi_i - b) = \sum_{i=1}^k \lambda_i \xi_i -b\sum_{i=1}^k \lambda_i = \sum_{i=1}^k \lambda_i \xi_i -b$
因此：
$\omega \cdot s^+ + b = \sum_{i=1}^k \lambda_i \xi_i > 0$
对于 $S_-$ 凸壳中所有点 $s^- \in conv(S_-)$ 有：
$\omega \cdot s^- + b = \sum_{i=1}^k \lambda_i \eta_i < 0$
假设 $S_+,S_-$ 的凸壳相交，等价于存在一点 $s$ 同时满足 $s \in conv(S_+), s \in conv(S_-)$ ，所以：
$\omega \cdot s + b = \sum_{i=1}^k \lambda_i \xi_i > 0$ $\omega \cdot s + b = \sum_{i=1}^k \lambda_i \eta_i < 0$
产生矛盾，所以凸壳一定不相交。

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

设数据集 $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_+,x_-$ 这两个点的距离就是两个凸壳之间的距离。

则对于任意的 $x \in conv(S_+)$ 有 $dist(x,x_-) \ge dist(x_+,x_-)$ 。

则对于任意的 $x \in conv(S_-)$ 有 $dist(x,x_+) \ge dist(x_+,x_-)$ 。

存在超平面 $\omega \cdot x + b = 0$ ，其中
$\omega = x_+ - x_-$

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

对于任意的正例点 $x$
$\omega \cdot x + b = (x_+ - x_-) \cdot x - \frac{x_+ \cdot x_+ - x_- \cdot x_-}{2} \\ =\frac{2x_+ \cdot x - x_+ \cdot x_+ - 2x_- \cdot x + x_- \cdot x_-}{2} \\ =\frac{-x \cdot x + 2x_+ \cdot x - x_+ \cdot x_+ + x \cdot x - 2x_- \cdot x + x_- \cdot x_-}{2} \\ =\frac{||x_- - x||^2 - ||x_+ - x||^2}{2} \\ =\frac{dist(x, x_-) - dist(x, x_+)}{2}$
只需要证明 $\omega \cdot x + b > 0$ 即可，也就是证明 $dist(x, x_-) > dist(x, x_+)$ ：

利用反证法，假设 $dist(x, x_-) \le dist(x, x_+)$ ，由上文可知 $dist(x, x_-) \ge dist(x_+, x_-)$ ，就有 $dist(x, x_+) \ge dist(x, x_-) \ge dist(x_+, x_-)$ 。

为了更好理解，绘制出二维平面的三个点 $x_+,x_-,x$ ，其中 $x_+,x \in conv(S_+),x_- \in conv(S_-)$

二维情况

由边的比例大小关系，在 $x_+x$ 之间存在一点 $x'$ 满足 $(x_- -x') \cdot (x_+ - x) = 0$ 。由于 $x_+,x \in conv(S_+)$ ，所以 $x' \in conv(S_+)$ ，但是显然 $dist(x',x_-) < dist(x_+, x_-)$ 。