模式识别笔记-第三章(2)

2018-11-19 本文已影响1人 Xavier_NZX

3.6 感知器算法

感知器算法是一种分类算法，需要了解一些前置知识。
（1）训练
我们有一些“正确答案”或者说是“标准答案”，我们需要让学习机对这些样本进行处理，使其分类规则不断修改知道可以按照和标准答案一样的结果进行分类。
这里需要训练集，训练集样本过少会欠拟合，过量会过拟合，但是过拟合的避免不是通过减少训练集样本数而是通过算法的改进来避免。通常我们需要尽可能大的训练集。
（2）学习
有监督学习：训练，对应机器学习中的分类。
无监督学习：没有“标准答案”，对应机器学习中的聚类。
（3）确定性分类器
处理确定可分情况的分类器。通过几何方法将特征空间分解为对应不同类的子空间，又称为几何分类器。
（4）感知器算法
一种早期神经网络分类学习模型，属于有关机器学习的仿生学领域中的问题，由于无法实现非线性分类而下马（Minsky and Papert）。但“赏罚概念（ reward-punishment ）”得到广泛应用。

算法

两类线性可分的模式类： $\omega_1,\omega_2$ ，设 $d(X)=W^TX$ 。
其中 $W=[w_1,w_2,w_3,w_4]^T$ ， $X=[x_1,x_2,…,x_n,1]^T$
应具有性质： $d(x)=W^TX\begin{cases} >0, &若x∈\omega_1\\ <0, &若x∈\omega_2 \end{cases}$ 。
因为是两类线性可分，所以我们对其规范化：对所有 $x∈\omega_2$ 乘以-1，即具有 $d(x)=W^TX>0$ 。
算法步骤：
（1）选择N个分属于ω1和ω2类的模式样本构成训练样本集，并将其编号为 $X_1,X_2,…,X_N$ 。
（2）设定初始权值W(0)。一般将每个分量设置为0。
（3）进行一轮迭代，对于每个样本计算 $W^TX$ ，若 $W^TX>0$ ，权值不改变， $W^TX<=0$ ，权值校正为 $W=W+cX$ ，c是校正增量系数。
假设这是第k轮迭代的第i个样本：
i. 若 $W^T(k+i)X_i<=0$ ，说明分类错误，则令 $W^T(k+i+1)=W(k+i)+cX_i$
ii.若 $W^T(k+i)X_i>0$ ，说明分类正确，令
$W^T(k+i+1)=W(k+i)$
（4）若一轮迭代没有出现权值修改，则完成分类；反之继续进行（3）

用于多类情况

对于多类情况1和多类情况2，需要多个判别函数，而每个判别函数相当于一个两类情况，多次使用感知器算法。
对于多类情况3，需要对上述算法进行改变：
依据的判别性质改变为：若 $X\in\omega_i$ ，需要 $d_i(X)>d_j(X),\forall j\neq i;j=1,2,…,M$ ，简而言之， $d_i(X)$ 是最大的。
（1）选择N个分属于 $ω_1,ω_2,…,ω_n$ 类的模式样本构成训练样本集，并将其编号为 $X_1,X_2,…,X_N$ 。
（2）设定N个初始权值 $W_i(0),i=1,2,…,N$ 。一般将每个分量设置为0。
（3）进行一轮迭代，对于每个样本 $X_i$ 计算计算 $W_j^T(k+i)X_i,j=1,2,…,N$ ，假设X_i属于类 $ω_m$ ,
i.若 $W_m^T(k+i)X_i$ 是最大的，则分类正确
ii.若 $W_m^T(k+i)X_i$ 不是最大的
$\begin{cases} W_n(k+i+1)=W_n(k)-cX_i\\ W_m(k+i+1)=W_m(k)+cX_i\\ W_o(k+i+1)=W_o(k) \end{cases}$
简而言之，比 $W_m^T(k+i)X_i$ 大的使其变小，比 $W_m^T(k+i)X_i$ 小的不变， $W_m$ 本身增长。
（4）若一轮迭代没有出现权值修改，则完成分类；反之继续进行（3）

3.7 梯度算法

3.7.1 梯度法基本原理

1.梯度概念
设函数 $f(Y)$ 是向量 $Y=(y_1,y_2,…,y_n)^T$ 的一个标量函数，则 $f(Y)$ 的梯度定义为：
$\triangledown f(Y)=\frac{d}{dY}f(Y)=(\frac{\partial f}{\partial y_1},\frac{\partial f}{\partial y_2},…,\frac{\partial f}{\partial y_n})^T$ ，类似于多维向量的导数。
梯度方向是自变量增加时 $f(Y)$ 增长最快的方向，负梯度方向反之。
2.梯度算法
定一个对错误分类敏感的准则函数 $J(W,X)$ （损失函数），在 $J$ 的负梯度方向上修改向量W。损失函数的确定需要损失函数的极小值发生在 $W^TX_i>0$ 时。
（1）将分属于 $\omega_1和\omega_2$ 的样本规范化并写成增广向量。
（2）进行一轮迭代，求出 $\triangledown J(k)$ ，权值校正为 $W=W-c\triangledown J$ ，c是校正增量系数。
假设这是第k轮迭代的第i个样本：令 $W^T(k+i+1)=W(k+i)-c\triangledown J(k)$
（3）若一轮迭代中有一次 $\triangledown J\neq0$ ，则再次进行（2），反之算法结束。