第2章 感知机

第2章 感知机

习题2.1

  Minsky 与 Papert 指出：感知机因为是线性模型，所以不能表示复杂的函数，如异或 (XOR)。验证感知机为什么不能表示异或。

解答：

解答思路：

1. 列出异或函数(XOR)的输入和输出；
2. 使用图例法证明异或问题是线性不可分的；
3. 使用反证法证明感知机无法表示异或。

解题步骤：

第1步：异或函数(XOR)的输入和输出

  对于异或函数(XOR)，全部的输入与对应的输出如下：

第2步：使用图例法证明异或问题是线性不可分的

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline

# 使用Dataframe表示异或的输入与输出数据
x1 = [0, 0, 1, 1]
x2 = [0, 1, 0, 1]
y = [-1, 1, 1, -1]
x1 = np.array(x1)
x2 = np.array(x2)
y = np.array(y)
data = np.c_[x1, x2, y]
data = pd.DataFrame(data, index=None, columns=['x1', 'x2', 'y'])
data.head()
​

.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
​

# 获取正类别（y=1）的数据
positive = data.loc[data['y'] == 1]
# 获取负类别（y=-1）的数据
negative = data.loc[data['y'] == -1]

# 绘制数据图
# 绘制坐标轴
plt.xlim(-0.5, 1.5)
plt.ylim(-0.5, 1.5)
plt.xticks([-0.5, 0, 1, 1.5])
plt.yticks([-0.5, 0, 1, 1.5])
# 添加坐标轴文字
plt.xlabel("x1")
plt.ylabel("x2")
# 绘制正、负样本点
plt.plot(positive['x1'], positive['x2'], "ro")
plt.plot(negative['x1'], negative['x2'], "bx")
# 添加图示
plt.legend(['Positive', 'Negative'])
plt.show()
​

  从上图可以看出，无法使用一条直线将两类样本分开，所以异或问题是线性不可分的

from sklearn.linear_model import Perceptron
import numpy as np

# 构造异或问题的训练数据集
X_train = np.array([[1, 1], [1, 0], [0, 1], [0, 0]])
y = np.array([-1, 1, 1, -1])

# 使用sklearn的Perceptron类构建感知机模型
perceptron_model = Perceptron()
# 进行模型训练
perceptron_model.fit(X_train, y)

# 打印模型参数
print("感知机模型的参数：w=", perceptron_model.coef_[
      0], "b=", perceptron_model.intercept_[0])
​

感知机模型的参数：w= [0. 0.] b= 0.0
​

  上述使用sklearn的Perceptron类构建感知机模型，从模型的参数上观察，感知机模型无法表示异或。

第3步：使用反证法证明感知机无法表示异或

  根据书中第2章感知机模型的定义2.1：

定义2.1（感知机） 假设输入空间（特征空间）是\mathcal{X} \subseteq R^n，输出空间是\mathcal{y}=\{+1,-1\}。输入x \in \mathcal{X}表示实例的特征向量，对应于输入空间（特征空间）的点；输出y \in \mathcal{Y}表示实例的类别。由输入空间到输出空间的如下函数：

f(x)=\text{sign}(w \cdot x + b)

\text{sign}(x)=\left { \begin{array}{ll}
+1, \quad x \geqslant 0 \
-1, \quad x < 0
\end{array}\right.

\begin{array}{ll}
w \leftarrow w + \eta y_i x_i \
b \leftarrow b + \eta y_i
\end{array}

\text{conv}(S) = \left{ x = \sum_{i=1}^k \lambda_i x_i \Big| \sum_{i=1}^k \lambda_i=1,\lambda_i \geqslant 0, i=1,2,\cdots, k \right}

T={(x_1,y_1), (x_2,y_2), \cdots, (x_n,y_n)}

w \cdot x + b = 0

w \cdot x + b = 0

w \cdot x_i + b = \varepsilon_i > 0, \quad i = 1,2,\cdots,|S_+|

\begin{aligned}
w \cdot s_+ + b &= w \cdot (\sum_{i=1}^{|S_+|} \lambda_i x_i) + b \
&= (\sum_{i=1}^{|S_+|} \lambda_i(\varepsilon_i - b)) + b \
&= \sum_{i=1}^{|S_+|} \lambda_i \varepsilon_i - (b\sum_{i=1}^{|S_+|} \lambda_i) + b \quad (\because \sum_{i=1}^{|S_+|} \lambda_i = 1) \
& = \sum_{i=1}^{|S_+|} \lambda_i \varepsilon_i
\end{aligned}

\text{dist}(x_1,x_2) = |x_1 - x_2|_2

\text{dist}(\text{conv}(S_+),\text{conv}(S_-)) = \min |s_+ - s_-|2 \quad s+ \in \text{conv}(S_+), s_- \in \text{conv}(S_-)

\text{dist}(\text{conv}(S_+),\text{conv}(S_-)) = \text{dist}(x_+, x_-) \quad x_+ \in \text{conv}(S_+), x_- \in \text{conv}(S_-)

\displaystyle f(x|w,b)=(x_+-x_-)^T(x - \frac{x_+ + x_-}{2})\
\left { \begin{array}{ll}
w = (x_+ - x_-)^T \
\displaystyle b = -\frac{1}{2}({|x_+|2}^2 - {|x-|_2}^2)
\end{array}\right .

\begin{aligned}
\displaystyle f(x)&=(x_+-x_-)^T(x - \frac{x_+ + x_-}{2}) \
&=(x_+-x_-)^T(x + x_+ - x_+ - \frac{x_+ + x_-}{2}) \
&=(x_+-x_-)^T(x - x_+ + \frac{x_+ - x_-}{2}) \
&=(x_+-x_-)^T(x - x_+) + \frac{{|x_+ - x_-|_2}^2}{2} \
\end{aligned}

(x_+-x_-)^T(x - x_+) < 0

\begin{aligned}
\displaystyle g(t)&={|u-x_-|_2}^2 \
&={|x_++t(x-x_+)-x_-|_2}^2 \
\end{aligned}

\begin{aligned}
\displaystyle g'(t)&=2(x_++t(x-x_+)-x_-)(x-x_+) \
&=2(x_+-x_-)^T(x-x_+)+t{|x-x_+|_2}^2 \
\end{aligned}