本文最后更新于：2023年2月28日下午

相关概念

术语	释义	推导
超平面	n维空间中的n-1维的子空间，即平面中的直线、空间中的平面之推广	$\vec w \cdot \vec x + b = 0$ $(\vec w, b)$
点到超平面的距离	$d = \frac{	\vec w \cdot \vec {x_0} + b
线性可分性	给定一个数据集： $T = \lbrace (x_1,y_1),(x_2,y_2), ..., (x_n,y_n)\rbrace$ ，其中$ x_i \subseteq \mathbb R^n $，$ \gamma = \lbrace+1,-1\rbrace$， $i=1,2,...,n$ 如果存在某个超平面 $\vec w \cdot \vec x + b = 0$ 能将数据集中的正实例点和负实例点完全正确地划分到超平面两侧，即对所有 $y_i = +1$ 的正实例 $i$ ，有$$\vec w \cdot \vec x + b > 0$$；对所有 $y_i = -1$ 的正实例 $i$ ，有$$\vec w \cdot \vec x + b < 0$$。则称数据集 $T$ 线性可分；否则，数据集 $T$ 线性不可分。

原理

感知机是一个线性分类器，只适用于线性可分问题。

感知机通过训练集数据最小化损失函数的学习，得到能够将正实例点和负实例点完全分离的分离超平面 (确定 $w, b$ )。

单个神经元/处理单元

输入空间：$ x \subseteq \mathbb R^n $，输入$ n$维特征向量

输出空间： $y_i \in \gamma, \gamma = \lbrace+1,-1\rbrace$ ，实现二分类

感知机： $\sum_{i=1}^{n}w_ix_i+b$ ， $w_1, ..., w_n$ 为各维输入分量连接到感知机的权重， $b$ 为偏置

激活函数：将结果映射至输出空间

函数	表达式	图像
符号函数： $sign(x)$	$f(x) = \begin{cases}1 , x>0\\0 , x=0\\-1 , x<0\end{cases}$

损失函数的自然选择

由于误分类的数据满足 (异号)：

$-y_i(w \cdot x_i + b) \geq 0$

因此，误分类点 $(x_i,y_i)$ 到超平面的距离是：

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

误分类点集合 $M$ 中的点到超平面的总距离是：

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

忽略 $\frac{1}{\|w\|}$ ，得到感知机学习的损失函数：

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

采用随机梯度下降算法 (stochastic gradient descent，SGD)，解决最小化损失函数的优化问题。

目标：

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

损失函数 $L(w,b)$ 的梯度为：

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

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

误分类点 $(x_i,y_i)$ 更新 $w,b$ ：

$w \gets w+ \alpha \cdot \nabla_w L(w,b) = w + \alpha y_ix_i$

$b \gets b+ \alpha \cdot \nabla_b L(w,b) = b + \alpha y_i$

学习算法的原始形式

选取初值 $w_0,b_0,\alpha$
选取训练集中点 $(x_i,y_i)$
将数据输入感知机，若激活函数得到的结果 $y_i(w \cdot x_i + b) \leq 0$ ，则为误分类点，更新 $w,b$

$w \gets w + \alpha y_ix_i$

$b \gets b + \alpha y_i$
转至2. ，直到训练集中无误分类点