感知机

《统计学习方法》笔记 第2章

Posted by Cheereus on January 16, 2020

第2章 感知机

2.1 感知机模型

感知机的定义:

假设输入空间(特征空间)是 $\mathcal X \subseteq \mathcal{R}^n$,输出空间是 $\mathcal Y=\{+1,-1\}$。输入 $x \in \mathcal X$ 表示实例的特征向量,对应于输入空间(特征空间)的点;输出 $\mathcal{Y}$ 表示实例的类别。由输入空间到输出空间的如下函数:

称为感知机。其中,$\omega$ 和 $b$ 为感知机模型参数,$\omega \in \mathcal{R}^n$ 叫作权值(weight)或权值向量(weight vector),$b \in \mathcal{R}$ 叫作偏置(bias),$\omega \cdot x$ 表示 $\omega$ 和 $x$ 的内积。$sign$ 是符号函数,即

感知机是一种线性分类模型,属于判别模型。感知机模型的假设空间是定义在特征空间中的所有线性分类模型(linear classification model)或线性分类器(linear classifier),即函数集合 $\{f \vert f(x)=\omega \cdot x + b\}$。

2.2 感知机学习策略

2.2.1 数据集的线性可分性

给定一个数据集:

其中,$x_i \in \mathcal X = \mathcal{R}^n,\ y_i \in \mathcal{Y} = \{+1,-1\},\ i=1,2,\cdots,N$,如果存在某个超平面 $S$:

能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧,即对所有 $y_i=+1$ 的实例 $i$,有 $\omega \cdot x_i + b > 0$,对所有 $y_i=-1$ 的实例,有 $\omega \cdot x_i + b < 0$,则称数据集 $T$ 为现行可分数据集(linearly separable data set);否则,称数据集 $T$ 线性不可分。

2.2.2 感知机学习策略

损失函数的一个自然选择是误分类点的总数。但是,这样的损失函数不是参数 $\omega , b$ 的连续可导函数,不易优化。损失函数的另一个选择是误分类点到超平面 $S$ 的总距离,这是感知机所采用的。

输入空间 $\mathcal R^n$ 中任一点 $x_0$ 到超平面 $S$ 的距离:

这里 $\lVert \omega \lVert$ 是 $\omega$ 的 $L_2$ 范数。

对于误分类的数据 $(x_i,y_i)$ 来说,

成立。因为当 $\omega \cdot x_i + b > 0$ 时,$y_i=-1$;而当 $\omega \cdot x_i + b < 0$ 时,$y_i=+1$。因此,误分类点 $x_i$ 到超平面 $S$ 的距离是

这样,假设超平面 $S$ 的误分类点集合为 $M$,那么所有误分类点到超平面 $S$ 的总距离为:

不考虑 ,就得到感知机学习的损失函数。

感知机 $sign(\omega \cdot x + b)$ 学习的损失函数定义为:

这个损失函数是感知机学习的经验风险函数,显然损失函数 $L(\omega,b)$ 是非负的,是 $\omega,b$ 的连续可导函数。

感知机的学习策略是在假设空间中选取使损失函数式最小的模型参数,即感知机模型。

2.3 感知机学习算法

2.3.1 感知机学习算法的原始形式

输入:训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$,其中 $x_i \in \mathcal{X} = \mathcal{R}^n,y \in \mathcal{Y} = \{+1,-1\},i=1,2,\cdots,N$;学习率 $\eta(0 < \eta \leq 1)$;

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

(1) 选取初值 $\omega_0,b_0$;

(2) 在训练集中选取数据 $(x_i,y_i)$;

(3) 如果 $y_i(\omega \cdot x_i + b) \leq 0$,

(4) 转至(2),直至训练集中没有误分类点。

2.3.2 算法的收敛性

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

$\text{Novikoff}$ 定理:设训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$ 是线性可分的,其中 $x_i \in \mathcal{X} = \mathcal{R}^n,y \in \mathcal{Y} = \{+1,-1\},i=1,2,\cdots,N$,则

(1) 存在满足条件 $\lVert \hat\omega_{opt} \lVert = 1$ 的超平面 $\hat\omega_{opt}\cdot\hat x = \omega_{opt}\cdot x + b_{opt}=0$ 将训练数据集完全正确分开;且存在 $\gamma > 0$,对所有 $i=1,2,\cdots,N$ 都有

(2) 令 $R=\underset{1 \leq i \leq N}{\max}\ \lVert \hat x_i \lVert$,则感知机算法在训练集上的误分类次数 $k$ 满足不等式:

定理表明,误分类的次数 $k$ 是有上界的,经过有限次搜索可以找到将训练数据完全正确分开的分离超平面。

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

输入:线性可分的数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$,其中 $x_i \in \mathcal{R}^n,y \in \{+1,-1\},i=1,2,\cdots,N$;学习率 $\eta(0 < \eta \leq 1)$;

输出:$\alpha,b$;感知机模型 $f(x)=sign(\displaystyle\sum_{j=1}^N{\alpha_j y_j x_j \cdot x + b})$,其中 $\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)$。

(1) $\alpha \leftarrow 0,\ b \leftarrow 0$;

(2) 在训练集中选取数据 $(x_i,y_i)$;

(3) 如果 $y_i(\displaystyle\sum_{j=1}^N{\alpha_j y_j x_j \cdot x_i + b}) \leq 0$,

(4) 转至(2)直到没有误分类数据。

对偶形式中训练实例仅以内积的形式出现。为了方便,可以预先将训练集中实例间的内积计算出来并以矩阵的形式存储,这个矩阵就是所谓的 $\text{Gram}$ 矩阵(Gram matrix)

第2章完结