感知机

感知机

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

感知机有如下几何解释：线性方使用方程

$$w\cdot x+b=0$$

对应于特征空间 $\mathbb{R}^n$ 中的一个超平面 $S$。其中，$w$ 是超平面的法向量，$b$ 是超平面的截距。

线性可分

给定数据集

$$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$$

若存在某个超平面 $S:w\cdot x+b=0$, 能够将数据集的正负实例点完全正确地划分到超平面两侧，即

$$\begin{cases}
y_i=+1, & \text{则 } w\cdot x_i+b>0,\\
y_i=-1, & \text{则 } w\cdot x_i+b<0,
\end{cases}$$

那么，称 $T$ 为线性可分数据集；否则，称 $T$ 为线性不可分数据集。

线性可分的充要条件

设集合 $S \subset \mathbf{R}^n$ 是由 $\mathbf{R}^n$ 中的 $k$ 个点所组成的集合，即 $S = \{x_1,x_2,\cdots,x_k\}$。定义 $S$ 的凸壳 $\text{conv}(S)$ 为

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

凸壳是凸集

$$\text{样本集线性可分}
\iff
\operatorname{conv}(P)\cap\operatorname{conv}(N)=\varnothing$$

$$\text{样本集线性可分}
\implies
\operatorname{conv}(P)\cap\operatorname{conv}(N)=\varnothing.$$

$$\begin{aligned}
w^\top u+b
&=w^\top\left(\sum_{i=1}^{m}\lambda_i x_i\right)+b\\
&=\sum_{i=1}^{m}\lambda_i w^\top x_i+b\\
&=\sum_{i=1}^{m}\lambda_i(w^\top x_i+b).
\end{aligned}$$

$$w^\top u+b>0$$

$$\operatorname{conv}(P)\cap\operatorname{conv}(N)=\varnothing
\implies
\text{样本集线性可分}.$$

$$u^*\in\operatorname{conv}(P),
\qquad
v^*\in\operatorname{conv}(N).$$

$$(1-t)u^*+tu\in\operatorname{conv}(P),
\qquad 0\leq t\leq1$$

$$\left\|v^*-\big[u^*+t(u-u^*)\big]\right\|^2$$

$$-2(v^*-u^*)^\top(u-u^*)\geq0.\quad i.e.\quad d^\top(u-u^*)\leq0$$

$$d^\top u\leq d^\top u^*
<
d^\top v^*
\leq d^\top v.$$

$$\begin{aligned}
d^\top v^*-d^\top u^*
&=d^\top(v^*-u^*)\\
&=d^\top d\\
&=\|d\|^2\\
&>0.
\end{aligned}$$

$$w=d,\qquad b=-\frac{d^\top u^*+d^\top v^*}{2}.$$

$$\boxed{ d^\top x-\frac{d^\top u^*+d^\top v^*}{2}=0 }.$$

$$c=\frac{d^\top u^*+d^\top v^*}{2}.$$

$$d^\top u^*<c<d^\top v^*,$$

$$d^\top x\leq d^\top u^*<c,$$

$$d^\top x-c<0.$$

$$d^\top z\geq d^\top v^*>c,$$

$$d^\top z-c>0.$$

用Python验证线性可分

import numpy as np
from scipy.optimize import linprog


def check_linear_separable(X, y):
    """
    根据正负样本凸壳是否相交，判断数据集是否线性可分。

    参数
    ----
    X : shape (n_samples, n_features)
        样本特征矩阵
    y : shape (n_samples,)
        标签，必须为 -1 或 +1

    返回
    ----
    bool
        True 表示线性可分，False 表示线性不可分
    """
    X = np.asarray(X, dtype=float)
    y = np.asarray(y)

    P = X[y == 1]    # 正类样本
    N = X[y == -1]   # 负类样本

    if len(P) == 0 or len(N) == 0:
        raise ValueError("数据集必须同时包含正类和负类样本")

    # 设 z = [lambda, mu]
    m, n = len(P), len(N)
    d = X.shape[1]

    # P.T @ lambda - N.T @ mu = 0
    A_eq = np.block([
        [P.T, -N.T],
        [np.ones((1, m)), np.zeros((1, n))],
        [np.zeros((1, m)), np.ones((1, n))]
    ])

    b_eq = np.r_[np.zeros(d), 1.0, 1.0]

    # 目标函数为 0，只需判断是否存在可行解
    result = linprog(
        c=np.zeros(m + n),
        A_eq=A_eq,
        b_eq=b_eq,
        bounds=(0, None),
        method="highs"
    )

    if result.status == 0:
        # 存在两个凸壳的公共点
        return False
    elif result.status == 2:
        # 约束不可行，凸壳不相交
        return True
    else:
        # 求解器未能明确判断，不能擅自归类
        raise RuntimeError(
            f"无法确定线性可分性：{result.message}"
        )

损失函数

对于任意 $x_0\in\mathbb{R}^n$，其到超平面 $S$ 的距离为

$$\frac{\left|w\cdot x_0+b\right|}{\|w\|}$$

• 若 $x_0$ 是正确分类点，则

  $$\frac{\left|w\cdot x_0+b\right|}{\|w\|}
  =
  \begin{cases}
  \dfrac{w\cdot x_0+b}{\|w\|}, & y_0=+1,\\
  -\dfrac{w\cdot x_0+b}{\|w\|}, & y_0=-1.
  \end{cases}$$

• 若 $x_0$ 是错误分类点，则

  $$\frac{\left|w\cdot x_0+b\right|}{\|w\|}=
  \begin {cases}
  -\dfrac {w\cdot x_0+b} {\|w\|}, & y_0=+1,\\
  \dfrac {w\cdot x_0+b} {\|w\|}, & y_0=-1.
  \end {cases}
  =
  -\frac{y_0(w\cdot x_0+b)}{\|w\|}$$

误分类点 $x_i$ 到 $S$ 的距离：

$$-\frac{1}{\|w\|}y_i(w\cdot x_i+b)$$

所有误分类点到 $S$ 的距离：

$$-\frac{1}{\|w\|}\sum_{x_i\in M}y_i(w\cdot x_i+b)$$

其中，$M$ 代表所有误分类点的集合。

损失函数：

$$L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)$$

模型参数估计：

$$\arg\min_{w,b} L(w,b)$$

梯度：

$$\nabla_w L(w,b)=-\sum_{x_i\in M}y_i x_i,
\qquad
\nabla_b L(w,b)=-\sum_{x_i\in M}y_i$$

参数更新：

• 批量梯度下降法（Batch Gradient Descent）：每次迭代时使用所有误分类点来进行参数更新。

$$w\leftarrow w+\eta\sum_{x_i\in M}y_i x_i,
    \qquad
    b\leftarrow b+\eta\sum_{x_i\in M}y_i$$

其中，$0< \eta \leq 1$ 代表步长。

• 随机梯度下降法（Stochastic Gradient Descent）：每次随机选取一个误分类点。

$$w\leftarrow w+\eta y_i x_i,
    \qquad
    b\leftarrow b+\eta y_i$$

学习算法的原始形式

原始算法的Python实现

import numpy as np

class Perceptron:
    def __init__(self, eta=0.1, max_iter=10000):
        self.eta = eta
        self.max_iter = max_iter
        self.w = None
        self.b = None
        self.n_iter_ = 0
        self.converged_ = False

    def fit(self, X, y):
        X = np.asarray(X, dtype=float)
        y = np.asarray(y)

        n_samples, n_features = X.shape

        # 1. 初始化参数
        self.w = np.zeros(n_features)
        self.b = 0.0

        # 2. 反复遍历训练集
        for epoch in range(self.max_iter):
            errors = 0

            for i in range(n_samples):
                x_i, y_i = X[i], y[i]

                # 3. 判断是否误分类
                if y_i * (self.w @ x_i + self.b) <= 0:
                    self.w += self.eta * y_i * x_i
                    self.b += self.eta * y_i
                    errors += 1

            self.n_iter_ = epoch + 1

            # 4. 没有误分类点，训练结束
            if errors == 0:
                self.converged_ = True
                break

        return self

    def predict_one(self, x):
        return 1 if self.w @ x + self.b >= 0 else -1

    def predict(self, X):
        X = np.asarray(X, dtype=float)
        return np.where(X @ self.w + self.b >= 0, 1, -1)

实例

数据点为

X = np.array([[3,3], [4,3], [1,1]])
y = np.array([1, 1, -1])

构建最优化问题：

$$\min_{w,b} L(w,b) = -\sum_{x_i\in M} y_i(w \cdot x_i + b)$$

按照原始算法求解 $w,b$。$\eta = 1$。

（1）取初值 $w_0 = 0,\ b_0 = 0$

（2）对 $x_1 = (3,3)^\mathrm{T}$，$y_1(w_0 \cdot x_1 + b_0) = 0$，未能被正确分类，更新 $w,\ b$

$$w_1 = w_0 + y_1 x_1 = (3,3)^\mathrm{T},\ b_1 = b_0 + y_1 = 1$$

得到线性模型

$$w_1 \cdot x + b_1 = 3x^{(1)} + 3x^{(2)} + 1$$

（3）对 $x_1,x_2$，显然，$y_i(w_1 \cdot x_i + b_1) > 0$，被正确分类，不修改 $w,\ b$； 对 $x_3 = (1,1)^\mathrm{T}$，$y_3(w_1 \cdot x_3 + b_1) < 0$，被误分类，更新 $w,\ b$。

$$w_2 = w_1 + y_3 x_3 = (2,2)^\mathrm{T},\ b_2 = b_1 + y_3 = 0$$

得到线性模型

$$w_2 \cdot x + b_2 = 2x^{(1)} + 2x^{(2)}$$

如此继续下去，直到

$$w_7 = (1,1)^\mathrm{T},\ b_7 = -3$$

$$w_7 \cdot x + b_7 = x^{(1)} + x^{(2)} - 3$$

对所有数据点 $y_i(w_7 \cdot x_i + b_7) > 0$，没有误分类点，损失函数达到极小。

分离超平面为：$x^{(1)} + x^{(2)} - 3 = 0$

感知机模型为：$f(x) = \operatorname{sign}(x^{(1)} + x^{(2)} - 3)$

import numpy as np
import matplotlib.pyplot as plt
import math

# ==================== 1. 输入数据 ====================
X = np.array([[3, 3], [4, 3], [1, 1]])
y = np.array([1, 1, -1])

eta = 1                 # 学习率
max_updates = 100        # 最大更新次数

# LaTeX 公式设置（需要本机安装 LaTeX）
plt.rcParams['text.usetex'] = True
plt.rcParams['text.latex.preamble'] = r'\usepackage{amsmath}'

# ==================== 2. 感知机迭代 ====================
w = np.zeros(X.shape[1], dtype=float)
b = 0.0

# 保存初始状态
history = [(w.copy(), b, None)]

for _ in range(max_updates):
    updated = False

    # 按输入顺序寻找第一个误分类点
    for i in range(len(X)):
        if y[i] * (np.dot(w, X[i]) + b) <= 0:
            w += eta * y[i] * X[i]
            b += eta * y[i]

            # 保存更新后的参数和本次误分类点
            history.append((w.copy(), b, i))
            updated = True
            break

    # 一轮扫描没有误分类点，算法收敛
    if not updated:
        break
else:
    print(f"达到最大更新次数 {max_updates}，算法可能尚未收敛。")

# ==================== 3. 绘制迭代过程 ====================
n = len(history)
cols = min(3, n)
rows = math.ceil(n / cols)

fig, axes = plt.subplots(
    rows, cols,
    figsize=(5 * cols, 4 * rows),
    squeeze=False
)

# 统一坐标范围，方便比较, 实际使用可能需要微调
xmin, ymin = X.min(axis=0) - 5
xmax, ymax = X.max(axis=0) + 5
x1 = np.linspace(xmin, xmax, 300)

for step, (w, b, error_idx) in enumerate(history):
    ax = axes.flat[step]

    # 绘制两类样本
    ax.scatter(
        X[y == 1, 0], X[y == 1, 1],
        marker='o', facecolors='none',
        edgecolors='black', s=60, label=r'$+1$'
    )
    ax.scatter(
        X[y == -1, 0], X[y == -1, 1],
        marker='x', color='black',
        s=60, label=r'$-1$'
    )

    # 高亮本次更新所使用的误分类点
    if error_idx is not None:
        ax.scatter(
            X[error_idx, 0], X[error_idx, 1],
            s=180, facecolors='none',
            edgecolors='red', linewidths=1.8,
            label='Misclassified'
        )

    # 绘制 w·x + b = 0
    if np.allclose(w, 0):
        message = 'All points on boundary' if np.isclose(b, 0) \
                  else 'No decision boundary'
        ax.text(
            0.5, 0.5, message,
            transform=ax.transAxes,
            ha='center', va='center'
        )
    elif not np.isclose(w[1], 0):
        x2 = -(w[0] * x1 + b) / w[1]
        ax.plot(x1, x2, color='tab:red', lw=1.8)
    else:
        ax.axvline(-b / w[0], color='tab:red', lw=1.8)

    ax.set_title(
        rf'Iteration {step}: '
        rf'$w=({w[0]:g},{w[1]:g})^T,\ b={b:g}$'
    )
    ax.set_xlim(xmin, xmax)
    ax.set_ylim(ymin, ymax)
    ax.set_xlabel(r'$x^{(1)}$')
    ax.set_ylabel(r'$x^{(2)}$')
    ax.tick_params(direction='in')
    ax.grid(alpha=0.2)

    # 只在第一张图中显示图例
    if step == 0:
        ax.legend(frameon=False, fontsize=9)

# 隐藏多余子图
for ax in axes.flat[n:]:
    ax.set_visible(False)

fig.suptitle('Perceptron Learning Process', fontsize=15)
plt.tight_layout()
plt.show()

print(f"总更新次数：{len(history) - 1}")
print(f"最终 w = {w}, b = {b}")

算法的收敛性

记 $\hat{w}=(w^T,b)^T$，$\hat{x}=(x^T,1)^T$，则分离超平面可以写为

$$\hat{w}\cdot\hat{x}=0$$

若训练集

$$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$$

线性可分，其中，$x_i\in\mathcal{X}\subseteq\mathbb{R}^n$，$y_i\in\mathcal{Y}=\{+1,-1\}$，则

1. 存在满足条件 $\|\hat{w}_{opt}\|=1$ 的超平面 $\hat{w}_{opt}\cdot\hat{x}=0$ 可将 $T$ 完全正确分开；且 $\exists\gamma>0$，对所有 $i=1,2,\cdots,N$，

$$y_i(\hat{w}_{opt}\cdot\hat{x}_i)\geq\gamma$$

2. 令 $R=\max_{1\leq i\leq N}\|\hat{x}_i\|$，则感知机算法在 $T$ 上的误分类次数 $k$ 满足不等式

$$k\leq\left(\frac{R}{\gamma}\right)^2$$

证明

1.由于 $T$ 是线性可分的，由定义，存在超平面可将训练数据集完全正确分开，取此超平面为

$$\hat{w}_{opt}\cdot\hat{x}=w_{opt}\cdot x+b_{opt}=0 ,\quad\|\hat{w}_{opt}\|=1$$

由于对有限的 $i=1,2,\cdots,N$，均有

$$y_i(\hat{w}_{opt}\cdot\hat{x}_i)
=y_i(w_{opt}\cdot x_i+b_{opt})>0$$

记 $\gamma=\min_i\left\{y_i(w_{opt}\cdot x_i+b_{opt})\right\}$ , 则有

$$y_i(\hat{w}_{opt}\cdot\hat{x}_i)
=y_i(w_{opt}\cdot x_i+b_{opt})\geq\gamma$$

2.假设 $\hat w_0 = 0$，若实例被误分类，则更新权重。令 $\hat w_{k-1}$ 为第 $k$ 个误分类实例之前的扩充权重向量，即

$$`\hat w_{k-1} = (w_{k-1}^T,\ b_{k-1})`$$

若

$$y_i(\hat w_{k-1} \cdot \hat x_i) = y_i(w_{k-1} \cdot x_i + b_{k-1}) \le 0$$

则，$(x_i,y_i)$ 为第 $k$ 个误分类实例，更新参数，

$$\begin{cases}
w_k \leftarrow w_{k-1} + \eta y_i x_i \\
b_k \leftarrow b_{k-1} + \eta y_i
\end{cases}
\quad i.e.\quad\hat w_k = \hat w_{k-1} + \eta y_i \hat x_i$$

下面推导两个不等式

$$\begin{cases}
\hat w_k \cdot \hat w_{opt} \ge k\eta\gamma \\
\|\hat w_k\|^2 \le k\eta^2 R^2
\end{cases}$$

$\hat w_k \cdot \hat w_{opt} \ge k\eta\gamma$：

$$\begin{aligned}
\hat w_k \cdot \hat w_{opt} &= (\hat w_{k-1} + \eta y_i \hat x_i) \cdot \hat w_{opt} \\
&= \hat w_{k-1} \cdot \hat w_{opt} + \eta y_i \hat w_{opt} \cdot \hat x_i \\
&\ge \hat w_{k-1} \cdot \hat w_{opt} + \eta\gamma \\
&\ge \hat w_{k-2} \cdot \hat w_{opt} + 2\eta\gamma \\
&\quad \vdots \\
&\ge \hat w_1 \cdot \hat w_{opt} + (k-1)\eta\gamma \\
&\ge \hat w_0 \cdot \hat w_{opt} + k\eta\gamma \\
&= k\eta\gamma
\end{aligned}$$

$\|\hat w_k\|^2 \le k\eta^2 R^2$：

$$\begin{aligned}
\|\hat w_k\|^2 &= \|\hat w_{k-1} + \eta y_i \hat x_i\|^2 \\
&= \|\hat w_{k-1}\|^2 + 2\eta y_i \hat w_{k-1} \cdot \hat x_i + \eta^2 \|\hat x_i\|^2 \\
&\le \|\hat w_{k-1}\|^2 + \eta^2 \|\hat x_i\|^2 \\
&\le \|\hat w_{k-1}\|^2 + \eta^2 R^2 \\
&\le \|\hat w_{k-2}\|^2 + 2\eta^2 R^2 \\
&\quad \vdots \\
&\le \|\hat w_1\|^2 + (k-1)\eta^2 R^2 \\
&\le \|\hat w_0\|^2 + k\eta^2 R^2 \\
&= k\eta^2 R^2
\end{aligned}$$

结合所得两个不等式，

$$\begin{cases}
\hat w_k \cdot \hat w_{opt} \ge k\eta\gamma \\
\|\hat w_k\|^2 \le k\eta^2 R^2
\end{cases}
\implies k\eta\gamma \le \hat w_k \cdot \hat w_{opt} \le \|\hat w_k\| \|\hat w_{opt}\| \le \sqrt{k}\eta R$$

得到：

$$k\eta\gamma \le \sqrt{k}\eta R \implies k^2\gamma^2 \le kR^2$$

于是，有

$$k \le \left(\frac{R}{\gamma}\right)^2$$

• 收敛性：对于线性可分的 $T$，经过有限次搜索，可得将 $T$ 完全正确分开的分离超平面。
• 依赖性：不同的初值选择，或者迭代过程中不同的误分类点选择顺序，可能会得到不同的分离超平面。
• 对于线性不可分的 $T$，算法不收敛，迭代结果会发生震荡。
• 为得到唯一分离超平面，需增加约束条件。

对偶形式

在原始形式中，若$(x_i,y_i)$为误分类点，可如下更新参数：

$$w \leftarrow w + \eta y_i x_i; \qquad b \leftarrow b + \eta y_i$$

假设初始值 $w_0 = \boldsymbol{0},\ b_0 = 0$，对误分类点 $(x_i,y_i)$ 通过上述公式更新参数，修改 $n_i$ 次之后，$w,b$ 的增量分别为 $\alpha_i y_i x_i$ 和 $\alpha_i y_i$，其中 $\alpha_i = n_i \eta$。

最后学习到的参数为，

$$w = \sum_{i=1}^{N} \alpha_i y_i x_i; \qquad b = \sum_{i=1}^{N} \alpha_i y_i$$

算法 （感知机学习算法的对偶形式）

$$\begin{aligned}
\alpha_i &\leftarrow \alpha_i + \eta \\
b &\leftarrow b + \eta y_i
\end{aligned}$$

(3) 若 $y_i\left(\sum_{j=1}^{N}\alpha_j y_j x_j \cdot x_i + b\right) \le 0$，

$$\alpha_i \leftarrow \alpha_i + \eta; \qquad b \leftarrow b + \eta y_i$$

迭代条件：

$$\begin{aligned}
y_i\left(\sum_{j=1}^{N}\alpha_j y_j x_j \cdot x_i + b\right)
&= y_i\left[(\alpha_1 y_1 x_1 + \alpha_2 y_2 x_2 + \cdots + \alpha_N y_N x_N)\cdot x_i + b\right] \\
&= y_i\left(\alpha_1 y_1 x_1\cdot x_i + \alpha_2 y_2 x_2\cdot x_i + \cdots + \alpha_N y_N x_N\cdot x_i + b\right) \\
&\le 0
\end{aligned}$$

Gram 矩阵：

$$G = [x_i \cdot x_j]_{N\times N} =
\begin{bmatrix}
x_1\cdot x_1 & x_1\cdot x_2 & \cdots & x_1\cdot x_N \\
x_2\cdot x_1 & x_2\cdot x_2 & \cdots & x_2\cdot x_N \\
\vdots & \vdots & & \vdots \\
x_N\cdot x_1 & x_N\cdot x_2 & \cdots & x_N\cdot x_N
\end{bmatrix}$$

对偶形式的Python实现

import numpy as np


class Perceptron:
    def __init__(self, eta=0.1, max_iter=10000):
        self.eta = eta
        self.max_iter = max_iter
        self.alpha = None
        self.b = 0.0
        self.X_train = None
        self.y_train = None
        self.converged_ = False
        self.n_iter_ = 0

    def fit(self, X, y):
        X = np.asarray(X, dtype=float)
        y = np.asarray(y, dtype=int)

        n_samples = len(X)
        self.X_train = X
        self.y_train = y

        # (1) 初始化 alpha 和 b
        self.alpha = np.zeros(n_samples)
        self.b = 0.0
        self.converged_ = False

        # 预先计算训练样本之间的内积
        gram = X @ X.T

        # (2) 反复选取训练样本
        for epoch in range(self.max_iter):
            errors = 0

            for i in range(n_samples):
                # sum(alpha_j * y_j * x_j · x_i) + b
                score = np.sum(
                    self.alpha * self.y_train * gram[:, i]
                ) + self.b

                # (3) 如果误分类，更新 alpha_i 和 b
                if y[i] * score <= 0:
                    self.alpha[i] += self.eta
                    self.b += self.eta * y[i]
                    errors += 1

            self.n_iter_ = epoch + 1

            # (4) 没有误分类点，训练结束
            if errors == 0:
                self.converged_ = True
                break

        return self

    def decision_function(self, X):
        X = np.asarray(X, dtype=float)
        gram = X @ self.X_train.T
        return gram @ (self.alpha * self.y_train) + self.b

    def predict(self, X):
        return np.where(self.decision_function(X) >= 0, 1, -1)