什么是感知机？

ChuanXin · 发表于 2021-12-1 18:50

1) 感知机的定义是什么？
感知机(perceptron)是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别。
2) 感知机的取值是什么？
取+1和-1二值。
3) 感知机对应于输入空间(特征空间)中的什么？
感知机对应于输入空间中将实例划分为正负两类的分离超平面，属于判别模型。
4) 感知机学习的目的是什么？
感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此，导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。
5) 感知机学习算法有什么特点？
感知机学习算法具有简单，并且易于实现的特点，分为原始形式和对偶形式。
6) 什么是感知机预测？
感知机预测是用学习得到的感知机模型对新的输入实例进行分类。它是神经网络与支持向量机的基础。
2.1感知机模型

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

$f(x) = sign(w\bullet x + b) \space\space\space\space\space\space\space(2.1)$
称为感知机。其中w和b为感知机模型参数， $w \in R^n$ 叫做权值(weight)或权值向量(weight vector)， $b \in R$ 叫作偏置(bias)， $w\bullet x$ 表示w 和 x的内积。sign是符号函数，即：

$sign(x) = \bigg \{_{-1, \space x<0}^{+1, \space x \geq 0} \space\space\space\space\space\space\space\space\space (2.2)$
2) 感知机是什么类型的模型？
感知机是一种线性分类模型，属于判别模型。
3) 感知机的几何解释？
感知机的几何解释是线性方程：

$w\bullet x + b = 0 \space \space\space\space\space (2.3)$
对应于特征空间  中的一个超平面S，其中w是从超平面的法向量，b是超平面的截距。
这个超平面将特征空间划分为两个部分。位于两部分的点(特征向量)分别被分为正、负两类。
因此，超平面S成为分离超平面(separating hyperplane),如图2.1所示。

感知机学习，由训练数据集(实例的特征向量及类别)

其中，求得感知机模型(2.1)，即求得模型参数w, b。感知机预测，通过学习得到的感知机模型，对于新的输入实例给出其对应的输出类别。
2.2 感知机的学习策略

2.2.1 数据集的线性可分性

1) 什么是感知机的线性可分性？
定义2.2 (数据集的线性可分性) 给定一个数据集

，
其中  ，如果存在某个超平面S

$w \bullet x + b = 0$
能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，即对所有的 $y_i = +1$ 的实例i，有  对所有  的实例 i，有  ，则称数据集T为线性可分数据集(linearly separable data set)；否则，成数据集T线性不可分。
2.2.2 感知机学习策略

1) 感知机的目的是什么？
假设训练数据集是线性可分的，感知机学习的目的是求得一个能够将训练集整实例点和负实例点完全正确分开的分离超平面。
为了找出这样的超平面，即确定感知机模型参数w 和 b, 需要确定一个学习策略，即定义(经验)损失函数并将损失函数极小化。
2) 损失函数的选择依据是什么？
损失函数的一个自然选择是误分类点的总数，但是这样损失函数不是参数w和b的连续可到函数，不易优化。
损失函数的另一个选择是误分类点到超平面S的总距离，这是感知机所采用的。为此，首先写出输入空间  中任一点 $x_0$ 到超平面S的距离：

$\frac{1}{||w||}|w \bullet x_0 + b|$
这里， $||w||$ 是w的 $L_2$ 范数。
其次，对于误分类的数据  来说， $-y_i(w \bullet x_i + b) > 0$ 成立。因为当  时，  ，而当  时， $y_i = \underline+ 1$ 。因此，误分类点 $x_i$ 到超平面S的距离是 $\frac{1}{||w||} y_i(w \bullet x_i + b)$
这样，假设超平面S的误分类点集合为M，那么所有误分类点到超平面S的总距离为 $\frac{1}{||w||} \sum_{x_i \in M} y_i (w \bullet x_i + b)$
不考虑 $\frac{1}{||w||}$ ,就得到感知机学习的损失函数。
3) 感知机学习的损失函数如何定义的？和经验风险函数有什么关系？
给定训练数据集 $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}, i = 1, 2,..., N$ 。感知机 $sign(w \bullet x + b)$ 学习的损失函数定义为

$L(w, b) = - \sum_{x_i \in M} y_i(w \bullet x_i + b) \space\space\space\space\space(2.4)$
其中M为误分类点的集合。这个损失函数就是感知机学习的经验风险函数。
4) 损失函数可以取到负值么？
显然，损失函数是非负的。
如果没有误分类点，损失函数值是0；
误分类点越少，误分类点距离超平面越近，损失函数值越小;
一个特定的样本点的损失函数，在误分类时是参数w, b的线性函数，在正确分类时是0。
因此，给定训练数据集T，损失函数L(w, b)是w, b的连续可导函数。
感知机学习的策略是在假设空间中选取使损失函数式(2.4)最小的模型参数w, b,即感知机模型。
2.3 感知机学习算法

感知机的学习问题转化为求解损失函数式(2.4)的最优化问题，最优化的方法是随机梯度下降法。
2.3.1 感知机学习算法的原始形式

感知机学习算法是对一下最优化问题的算法，给定一个训练数据集

$T = \{(x_1, y_1), (x_2, y_2),...,(x_N, y_N) \}$
其中， $x_i \in X = R^{n}, \space y_i \in Y = \{-1, 1\}, \space i = 1,2,...,N$ ,求参数w 和 b，使其为一下损失函数极小化问题的解：

$\min_{w, b} L(w, b) = - \sum_{xi \in M} y_i(w \bullet x_i + b) \space\space\space\space\space (2.5)$
其中M为误分类点的集合。
1) 感知机学习算法是正确分类驱动的么？
不是。感知机学习算法是误分类驱动的。具体采用随机梯度下降法。
首先，任意选取一个超平面  ，然后用梯度下降法不断地极小化目标函数(2.5)。极小化过程中不是一次使M中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。
2) 损失函数的梯度怎么取？
假设误分类点集合M是固定的，那么损失函数L(w, b)的梯度由

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

$\space\space\space\space\space \bigtriangledown_b L(w, b) = - \sum_{x_i \in M} y_i$
给出。
随机选取一个误分类点 $(x_i , y_i)$ ，对w, b进行更新：

$\space\space\space\space\space w <- w + \eta y_i x_i \space\space\space\space\space(2.6)$

$\space\space\space\space\space b <- b + \eta y_i \space\space\space\space\space (2.7)$
式中  是步长，在统计学习中又称为学习率(learning rate)。这样，通过迭代可以期待损失函数L(w, b)不断减小，直到为0。
3) 梯度下降算法的原始形式是什么？
算法 2.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}, \space i = 1, 2,..., N;\space 学习率 \eta (0 < \eta \leq 1);$
输出： w, b; 感知机模型 $f(x) = sign(w \bullet x + b)$
(1) 选取初值
(2) 在训练集中选取数据
(3) 如果 $y_i (w \bullet x_i + b) \leq 0$

$\qquad \qquad w <- w + \eta y_i x_i$

$\qquad \qquad b <- b + \eta y_i$
(4) 转至(2),直至训练集中没有误分类点。
这种学习算法直观上有如下解释：当一个实例点被误分类，及位于分离超平面的错误一侧时，则调整w, b的值，使分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面的距离，直至超平面越过该误分类点使其被正确分类。
算法2.1 是感知机学习的基本算法，对应于后面的对偶形式，成为原始形式，感知机学习算法简单且易于实现。
4) 例举一个感知机算法的例子
例2.1 如图2.2所示的训练数据集，其正实例点是 $x_1 = (3, 3)^ T, \space x_2 = (4, 3)^T,$ 负实例点是 $x_3 = (1, 1)^T,$ 试用感知机学习算法的原始形式求感知机模型 $f(x) = sign(w \bullet x + b).$ 这里， $w = (w^{(1)}, w^{(2)})^T, \space x = (x^{(1)}, x^{(2)})^T.$

解  构建最优化问题：

$\qquad \min_{w, b} L(w, b) = - \sum_{x_i \in M} y_i(w \bullet x + b)$
按照算法2.1求解w, b ,  .
(1) 取初值 $w_0 = 0, \quad b_0 = 0$
(2) 对 $x_1 = (3, 3)^T, \space y_1(w_0 \bullet x_1 + b_0) = 0,$ 未能被正确分类，更新w, b

$\qquad w_1 = w_0 + y_1x_1 = (3, 3)^T,\space b_1 = b_0 + y_1 = 1$
得到线性模型

$\qquad w_1 \bullet x + b_1 = 3x^{(1)} + 3x^{(2)} + 1$
(3) 对于 $x_1, x_2，$ 显然， $y_1(w_1 \bullet x_1 + b_1) > 0,$ 被正确分类，不修改w, b;
对 $x_3 = (1, 1)^T, y_3(w_1 \bullet x_3 + b_1) < 0,被误分类，更新w, b$ .

$\qquad w_2 = w_1 + y_3x_3 = (2, 2)^T, \space b_2 = b_1 + y_3 = 0$
得到线性模型

$\qquad w_2 \bullet x + b_2 = 2x^{(1)} + 2x^{(2)}$
如此继续下去，直到

$\qquad w_7=(1, 1)^T, \space b_7 = -3$

$\qquad w_7 \bullet x + b_7 = x^{(1)} + x^{(2)} -3$
对所有数据点 $y_i(w_7 \bullet x_i + b_7) > 0,$ 没有误分类点，损失函数达到极小。
   分离超平面为          $x^{(1)} + x^{(2)} -3 = 0$
   感知机模型为          $f(x) = sign(x^{(1)} + x^{(2)} -3)$
   迭代过程见表2.1

这是在计算中误分类点先后取 $x_1, x_3, x_3, x_3, x_1, x_3, x_3$ 得到的分离超平面和感知机模型。如果在计算中误分类点依次取 $x_1, x_3, x_3, x_3, x_2, x_3, x_3, x_3, x_1, x_3, x_3,$ 那么得到的分离超平面是 $2x^{(1)} + x^{(2)} -5 =0$ 。
5) 感知机学习算法的初值和解有什么规律？
感知机学习算法由于采用不同的初值或选取不同的误分类点，解可以不同。
2.3.2 算法的收敛性

1) 感知机算法原始形式收敛么？
对于线性可分数据集，感知机学习算法原始形式收敛，即经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型。
2) 证明感知机原始形式的收敛性
为了便于叙述与推到，将偏置b并入权重向量w，记作 $\hat w = (w^T, b)^T$ ，同样也将输入向量加以扩充，加进常数1，记作 $\hat x = (x^T, 1)^T.$ 这样， $\hat x \in R^{(n+1)}, \space \hat w \in R^{(n+1)}$ ,显然， $\hat w \bullet \hat x = w \bullet x + b.$
定理 2.1(Novikoff)  设训练数据集 $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}, \space i = 1, 2,...,N,$
则
(1) 存在满足条件 $||\hat w_{opt}|| = 1$ 的超平面 $\hat w_{opt} \bullet \hat x = w_{opt} \bullet x + b_{opt} = 0$ 将训练数据集完全分开；且存在 $\gamma >0,对所有i = 1, 2,..., N$

$\qquad y_i(\hat w_{opt} \bullet \hat x_i) = y_i(w_{opt} \bullet x_i + b_{opt} ) \geq \gamma \qquad (2.8)$
(2) 令 $R = \max_{1 \leq i \leq N} ||\hat x_i||,$ 则感知机算法2.1在训训练数据集上的误分类次数k 满足不等式

$\qquad \qquad \qquad k \leq \bigg( \frac{R}{\gamma} \bigg)^2 \qquad(2.9)$
证明 (1) 由于训练数据集是线性可分的，按照定义2.2存在超平面将训练数据集完全正确分开，取次超平面为 $\hat w_{opt} \bullet \hat x = w_{opt} \bullet x + b_{opt} = 0,使||\hat w_{opt}|| = 1$ 。由于对有限的 $i = 1,2,...N,$ 均有

$\qquad \qquad y_i(\hat w_{opt} \bullet \hat x_i) = y_i(w_{opt} \bullet x_i + b_{opt}) > 0$
所以存在

$\qquad \qquad \gamma = \min_i \{y_i (w_{opt} \bullet x_i + b_{opt})\}$
使

$\qquad \qquad y_i(\hat w_{opt} \bullet \hat x_i) = y_i(w_{opt} \bullet x_i + b_{opt}) \geq \gamma$
(2) 感知机算法从 $\hat w_0 = 0$ 开始，如果实例被误分类，则更新权重。令 $\hat w_{k-1}$ 是第k个误分类实例之前的扩充权重向量，即

$\qquad \qquad \hat w_{k-1} = (w_{k-1}^T, b_{k-1})^T$
则第k个误分类实例的条件是

$\qquad \qquad y_i(\hat w_{k-1}, \hat x_i) = y_i(w_{k-1} \bullet x_i + b_{k-1}) \leq 0 \qquad (2.10)$
若 $(x_i, y_i)是被\hat w_{k-1} = (w_{k-1}^T, b_{k-1})^T$ 误分类的数据，则w 和b的更新是

$\qquad \qquad w_k \leftarrow \space w_{k-1} + \eta y_i x_i$

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

$\qquad \qquad \hat w_{k} = \hat w_{k-1} + \eta y_i \hat x_i \qquad (2.11)$
下面推导两个不等式：
(1) $\qquad \qquad \hat w_k \bullet \hat w_{opt} \geq k \eta \gamma \qquad (2.12)$
由式(2.11)及式(2.8)得

$\hat w_k \bullet \hat w_{opt} = \hat w_{k-1} \bullet \hat w_{opt} + \eta y_i \hat w_{opt} \bullet \hat x_i \geq \hat w_{k-1} \bullet \hat w_{opt} + \eta\gamma$
由此递推即得不等式(2.12)

$\hat w_k \bullet \hat w_{opt} \geq \hat w_{k-1} \bullet \hat w_{opt} + \eta\gamma \geq \hat w_{k-2} \bullet \hat w_{opt} + 2\eta\gamma \geq ... \geq k\eta\gamma$
(2)

$\qquad \qquad ||\hat w_k||^2 \leq k \eta^2 R^2 \qquad\qquad (2.13)$
由式(2.11)及(2.10)得

$\qquad \qquad ||\hat w_k||^2 = ||\hat w_{k-1}||^2 + 2\eta y_i \hat w_{k-1} \bullet \hat x_i + \eta^2 ||\hat x_i||^2$

$\qquad \qquad \qquad \leq ||\hat w_{k-1}||^2 + \eta^2 ||\hat x_i||^2$

$\qquad \qquad \qquad \leq ||\hat w_{k-1}||^2 + \eta^2 R^2$

$\qquad \qquad \qquad \leq ||\hat w_{k-2}||^2 + 2\eta^2R^2 \leq ...$

$\qquad \qquad \qquad \leq k \eta^2 R^2$
结合不等式(2.12)及式(2.13)即得

$\qquad \qquad k\eta\gamma \leq \hat w_k \bullet \hat w_{opt} \leq ||\hat w_k||\space||\hat w_{opt}|| \leq \sqrt k \eta R$

$\qquad \qquad k^2 \gamma^2 \leq k R^2$
于是 $\qquad \qquad \qquad k \leq \bigg (\frac{R}{\gamma} \bigg )^2$
定理表明，误分类的次数k是有上界的，经过有限次搜索可以找到将训练数据完全分开的分离超平面，也就是说，当训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的。
不过例2.1说明，感知机学习算法存在很多解，而为了得到唯一的超平面，需要对分离超平面增加约束条件，这就是之后会讲解的线性支持向量机的想法，当训练集线性不可分时，感知机学习算法不收敛，迭代结果会发生震荡。
2.3.3 感知机学习算法的对偶形式

1) 什么是感知机学习算法的对偶形式？
对偶形式的基本想法是，将w 和 b表示为实例 $x_i和标记y_i$ 的线性组合的形式，通过求解其系数而求得 w 和 b 。
在算法2.1中可假设初始值  均为0，对误分类点  通过

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

逐步修改w 和 b，设修改n 次，则w , b 关于  的增量分别是 $\alpha_i y_i x_i和\alpha_i y_i$ ，这里 $\alpha_i = n_i \eta$ 。这样，从学习过程不难看出，最后学习到的w , b 可以分别表示为

$\qquad \qquad \qquad w = \sum_{i=1}^{N} \alpha y_i x_i \qquad \qquad (2.14)$

$\qquad \qquad \qquad b = \sum_{i=1}^{N} \alpha_i y_i \qquad \qquad (2.15)$
这里， $\alpha_i \geq 0,\space i = 1,2,...,N,$ 当  时，表示第 $i$ 个实例点由于误分而进行更新的次数，实例点更新次数越多，意味着它距离分离超平面越近，也就越难正确分类。换句话说，这样的实例对学习结果影响最大。
2) 请对照原始形式来叙述对偶形式
算法 2.2 (感知机学习算法的对偶形式)
输入：线性可分的数据集 $T = \{ (x_1, y_1), (x_2, y_2),...,(x_N, y_N)\}, 其中x_i \in R,\space y_i \in \{-1, +1\}, \space i = 1,2,...,N;$ 学习率  ;
输出： $\alpha, b;$ 感知机模型 $f(x) = sign\bigg(\sum_{j = 1}^{N} \alpha_j y_j x_j \bullet x + b\bigg)$
其中 $\alpha = (\alpha_1, \alpha_2,...,\alpha_N)^T.$
(1) $\alpha \leftarrow 0, b \leftarrow 0$
(2) 在训练集中选取数据
(3) 如果 $y_i \bigg(\sum_{j=1}^{N} \alpha_j y_j x_j \bullet x_i + b \bigg) \leq 0$

$\qquad \qquad \qquad \alpha_i \leftarrow \alpha_i + \eta$

(4) 转至(2)直到没有误分类数据。
对偶形式中训练实例仅以内积的形式出现，为了方便，可以预先将训练集中实例间的内积计算出来并以矩阵形式存储，这个矩阵就是所谓的Gram矩阵(Gram matrix)

$\qquad \qquad \qquad G = [x_i \bullet x_j]_{M \times N}$

pc8888888 · 发表于 2021-12-1 18:57

emmmmmm简单总结+copy了一下统计学习方法的内容

zt3ff3n · 发表于 2021-12-1 19:00

对偶形式的基本想法是，将w 和 b表示为实例的线性组合的形式。此处我个人理解成w=Axi+Byi这种形式，但下文中w=alpha×yi×xi，求解答！

DungDaj · 发表于 2021-12-1 19:01

此处损失函数，最好加上个max(0, -yi(w*xi+b))，不然当选择到一个样本，将其正确分类后，原有的损失函数会小于0

IT圈老男孩1 · 发表于 2021-12-1 19:03

的确是这样 2333

LiteralliJeff · 发表于 2021-12-1 19:07

你好，想问下loss函数为什么将1/||w||拿掉

redhat9i · 发表于 2021-12-1 19:16

损失函数存在的作用对象是误分类的点。有了1/||w||、没有1/||w||，只要数据集线性可分（前提条件），那么loss的值最终都会收敛到0，因此拿掉也没关系。此外，重要的一点是感知机没有要求最终得到的线性模型唯一，只要最终loss为0即可。如果要求唯一的话，参考SVM的间隔最大化思想。

maltadirk · 发表于 2021-12-1 19:20

谢谢了[微笑]

rustum · 发表于 2021-12-1 19:21

站在李航老师的肩膀上，更加简洁清晰
[欢呼]

RhinoFreak · 发表于 2021-12-1 19:28

请问，这个上界与学习率无关了，难道学习率再小学习次数也不会超过此上界吗，怎么理解这一点？

		自动登录	找回密码
密码			立即注册

什么是感知机？

本帖子中包含更多资源