Pattern Recognition

绪论

模式识别

模：法也；式，法也。

模式：一种规律

Pattern：事物的模板或原型，或者表征事物特点的特征或性状的组合。

模式识别中的模式：

• 存在于时间、空间中可观察的事物，具有时间空间分布的信息。
• 对客体特征的描述。

样本：

• 一个具体的研究对象

模式类：

• 具有某些共同特性的模式的集合

模式识别：

• 确定一个样本的类别属性（模式类）的过程
• 把某一样本归属于多个类型中的某个类型

模式识别——用计算机实现人对各种事物或现象的分析、描述、判断、识别。

模式识别系统

典型构成

监督模式识别

回归：

• 反映样本数据集中样本的属性值的特性，通过函数表达样本映射的关系来发现属性值之间的依赖关系。

分类：

• 将样本数据集中的样本映射到某个给定的类别中。

一般步骤：

1. 分析问题
2. 原始特征获取
3. 特征提取与选择
4. 分类器设计
5. 分类决策

非监督模式识别

聚类：

• 将样本数据集中的样本分为几个类别，属于同一类别的样本相似性比较大。

一般步骤：

1. 分析问题
2. 原始特征获取
3. 特征提取与选择
4. 聚类分析
5. 结果解释

比较

有已知样本：监督模式识别

无已知样本：非监督模式识别

贝叶斯决策理论

基本符号与定义

决策：根据观测到的$x$，利用先验和类条件概率决定$x$属于哪一类。决策是从样本空间到决策空间的一个映射。

Bayes决策

两种常用的准则：

• 最小错误概率准则
• 最小风险准则

基于最小错误

贝叶斯概率：

决策规则

等价形式：

错误率：

条件错误率$p(e|x)$的计算：

• 以两类问题为例，当获得观测值$x$之后，有两种决策可能：决定$x\in \omega_1$或$x\in\omega_2$。则条件错误率为：

贝叶斯最小错误率决策：

• 选择后验概率$p(\omega_1|x)$，$p(\omega_2|x)$中大的$\omega$作为决策，使得在观测值$x$下的条件错误率最小：

条件错误率：

错误率：

同时可以证明，此决策保证了每个观测值下的条件错误率最小。Bayes决策是一致最优决策。

基于最小风险

引入风险函数（损失函数）$\lambda(x)$

风险损失：采用决策$a_i$时的风险

$x$是随机变量，采用$x$不同的观测值，产生的条件风险不同。决策$a$可以看成$x$的函数。定义期望风险：

条件风险对应的是$x$，期望风险对应的是$a(x)$。

在考虑错判带来的损失时，我们希望损失最小，如果在采取每个决策都使其条件风险最小，则对所有的$x$做出决策时，其期望风险也必然最小。这样的决策就是最小风险贝叶斯准则。

即：

如果有：

则有：$a=a_k$

计算步骤：

1. 计算后验概率
2. 根据决策风险表，计算采取$a_i$的条件风险
3. 对$a$个条件风险值进行比较，找出使条件风险最小的决策$a$。

多类情况贝叶斯决策规则

判别函数

$g_i(x)$，一般选取$g_i(x)=\max_jg_j(x)$，则将$x$归于$\omega_i$类。

决策面方程

正态分布统计决策

最小错误率贝叶斯判别函数：

带入正态分布：

决策面方程：

几个特殊情况：

1. $\Sigma_i=\sigma^2I$，则判别函数为：$-\frac{1}{2\sigma^2}(x-\mu_i)^T(x-\mu_i)+\ln p(\omega_i)$。若先验概率相等，直接等价于最小距离分类器。
2. 每一个协方差矩阵都相等，则判别函数为：$-\frac{1}{2\sigma^2}(x-\mu_i)^T(x-\mu_i)-\frac{d}{2}\ln 2\pi-0.5\ln \sigma^{2d}+\ln p(\omega_i)$式中$d$为维度。可简化为：$-\frac{1}{2\sigma^2}(x-\mu_i)^T\Sigma_i^{-1}(x-\mu_i)+\ln p(\omega_i)$
3. 若协方差矩阵各不相等：

概率密度函数的估计

基于样本的两步贝叶斯决策

• 利用样本集估计$P(\omega_i)$和$P(x|\omega_i)$
• 得到$\hat P(\omega_i)$和$\hat P(x|\omega_i)$
• 将估计量带入贝叶斯决策规则
• 得到决策结果

首先通过训练样本估计概率密度函数

• 先验概率估计-训练样本分布情况/根据领域知识认定
• 但类条件概率密度估计难

统计决策进行类别判定

• 训练样本有限，难以涵盖所有情况
• 但当训练样本多，就可以趋近于理论贝叶斯决策

概率密度估计方法

由训练样本集估计总体概率密度的方法可分为：

• 监督参数估计
• 非监督参数估计
• 非参数估计

参数估计的基本概念

统计量、参数空间

点估计：构造一个统计量作为某参数的估计

估计量、估计值、区间估计

概率密度估计的评估

无偏性：$\mathbb E\theta = \hat \theta$

渐进无偏：$N$趋于无穷有无偏性

有效性：一种估计比另一种方差小

一致估计

则$\hat \theta$是$\theta$的一致估计

最大似然估计

基本假设

• $\theta$确定但未知
• 按类别把样本集分开，$\Re_j$类中每个样本都是对立从概率密度$p(x|\omega_i)$的总体中独立抽取出来的。每即个样本i.i.d
• $p(x|\omega_j)$为已知分布，参数向量未知，且每个不同类别参数在函数上独立

似然函数定义

在一类中独立抽取样本集来估计未知参数。

假设某类样本集中有$N$个样本

因样本独立抽取，样本出现在样本集中的概率

也可以取对数。

求解

由于每个训练样本独立，可对概率乘积取对数，再求导。

注意：方程有可能有多解，但只有一个解最大。

多维正态分布的最大似然估计

$\Sigma$已知，$\mu$未知，求$\mu$

$\Sigma,\mu$均未知

贝叶斯估计和贝叶斯学习

贝叶斯估计实质：贝叶斯决策来决策参数的取值。

与最大似然估计的区别：

• 最大似然估计把待估计的参数当作未知但固定的量
• 贝叶斯估计把待估计的参数也看为随机变量

贝叶斯学习：把贝叶斯估计的原理用于直接从数据对概率密度函数进行迭代估计。

可以回顾最小风险贝叶斯决策

贝叶斯估计量

$R(\hat\theta|x)$为给定$x$条件下估计量$\hat\theta$的期望损失，称为条件风险

定义：如果$\theta$的估计量$\hat \theta$使得条件风险最小，则为贝叶斯估计量。

损失函数

损失函数有多种，最常见为平方误差：

贝叶斯估计

定理：如果损失函数为二次函数，则贝叶斯估计量为给定$x$时$\theta$的条件期望：

估计基本步骤

1. 确定$\theta$的先验分布$p(\theta)$，待估参数为随机变量
2. 用第$i$类样本$X^i=(X_1,X_2,\dots，X_N)$求出样本的联合概率密度分布$p(X^i|\theta)$，是一个$\theta$的函数
3. 利用贝叶斯公式，求$\theta$的后验概率

4. 求贝叶斯估计

这两种参数估计方法，最终目的是估计总体分布

其实在第三步后可以直接通过联合密度求类条件概率密度

正态分布的均值估计

一维正态分布，已知$\sigma^2$，估计$\mu$。

假设概率密度服从正态分布，则$p(X|\mu)\sim N(\mu,\sigma^2),p(\mu)\sim N(\mu_0,\sigma^2)$

用第$i$类样本$X^i=(X_1,X_2,\dots,X_N)$，求出后验概率：

因为$N$个样本独立抽取，且$\int p(X^i|\mu)p(\mu)\mathrm d\mu$仅仅与$x$有关，则上式可改写为：

非监督参数估计

在未知样本类别的条件下的参数估计称为非监督参数估计

几个基本假设

• 样本来自类数为$c$的各类中，但不知道每个样本究竟来自于哪一类
• 每类的先验概率$p(\omega_j)$已知
• 类条件概率密度的形式$p(x|\omega_j,\theta_j)$已知
• 未知的只是$c$个参数向量$\theta_1,\theta_2,\dots,\theta_c$的值

似然函数：

线性判别函数

引言

基于样本的Bayes分类器：通过估计类条件概率密度，设计相应判别函数

如果可以估计概率密度函数，则可以使用贝叶斯决策来最优的实现分类

从样本数据中直接估计参数->根据对样本/问题的理解直接设定判别函数形式，直接求解！

参数方法

概率密度函数已知，训练样本去估计参数

线性判别方法

与非参数方法类似，与参数没有直接关系。次优方法。

基于样本的直接确定判别函数的方法

1. 针对不同情况，使用不同准则函数，设计出满足这些不同准则要求的分类器。
2. 这些准则的“最优”并不一定与错误率最小相一致：次优分类器。

线性判别函数的基本概念

d维空间中线性判别函数的一般形式：

其中：$x$是样本向量-样本在$d$维特征空间中的描述，$w$是权向量，$w_0$是一个常数。

令$g(x) = g(x_1)-g(x_2)$，$g(x) = 0$定义了一个决策面，分开了两类。

判别函数$g(x)$也可以看作是特征空间中某个点$x$到超平面距离的一种代数度量。可定义：

其中$x_p$是$x$到$H$的投影向量，$r$是$x$到$H$的垂直距离。

则

特殊情况：x为原点，则$g(x)=w_0$。

设计分类器的主要步骤

1. 有一组具有类别标志的样本集
2. 根据实际情况确定一个准则函数 $J$,满足：$J$是样本集和$w,wo ,a$的函数；$J$的值能反映分类器的性能，它的极值解对应于 “最好”的决策
3. 利用最优化方法求出准则函数的极值解和$w,wo ,a$，进而得到$g(x)$

Fisher线性判别分析

基本思想

希望投影后的一维数据满足：

1. 两类之间尽可能远
2. 每一类自身尽可能紧凑

即：用投影后数据的统计性质（均值和离散度）的函数作为判别优劣的标准

定义符号

$m_1,m_2$两类数据均值向量

$S_1,S_2$两类数据离散度矩阵

$\mu_1,\mu_2$两类数据投影后一维数据均值

$\sigma_1,\sigma_2$两类数据投影后一维数据离散度

则有：

Fisher准则函数

称$S_b=(m_1-m_2)(m_1-m_2)^T$类间离散度矩阵

称$S_t=S_1+S_2$类内总离散度矩阵

则：

Fisher准则合理性

$J_F(w)$只与投影方向有关，与$||w||$无关，若$w$是最优解，则$\lambda w$也是最优解。

Fisher最佳投影方向求解

需要$S_t=S_1+S_2$正定，否则存在$w$使得$w^TS_tw=0$，导致$J_F(w)$无极大值。

又因为有界性，则$J_F(w)\le\frac{\max \lambda(S_b)}{\min \lambda(S_t)}$

$\lambda(S)$表示$S$的特征根。

又因为$S_t$正定，则存在最优的$w$，使得$w^TS_tw=1$

本来是无约束优化$\max\frac{w^TS_bw}{w^TS_tw}$，等价为带约束最优化：

由定义：

记$c=(m_1-m_2)^Tw_{opt}$，则：

而我们只关心投影方向，所以：

映射就此完成，现在确定分类阈值$w_0$，即两个样本投影后的加权平均值（权为样本个数）的负数

感知准则函数

为讨论方便，将$x$增加一维：$y=[1,x_1,x_2,\dots,x_d]^T$，增广的权向量为：$a=[w_0,w_1,w_2,\dots,w_d]^T$ ，线性判别函数为：$g(y)=a^Ty$

基本概念

线性可分性

训练样本集中的两类样本在特征空间可以用一个线性分界面正确无误的分开。

规范化样本向量

将第二类样本取其反向向量。

感知准则函数

式中$Y_M$是被$a$错误分类的实例集合，由于全部反向，导致所有错误分类的实例有$a^Ty<0$，因此$J_P(a)$非负。

定义梯度：

梯度衰减更新法则为：

也被称为感知机批次更新法则。

感知准则函数修正法：

1. 单样本修正法：样本集视为不断重复出现的序列，逐个样本检查，修正权向量
2. 批量样本修正法：样本成批或全部检查后，修正权向量。

小结

感知准则函数方法思路：

1. 找初始向量$a_1$，用训练样本集中每个样本计算
2. 若发现某个$y$有$a^Ty<0$，则只要$a_{k+1} = a_k+\eta_ky$，则必有$a_{k+1}^Ty = a_k^Ty+\eta_ky^Ty$，有趋势使得$a_{k+1}^Ty>0$

当然，修正后的$a$也有可能使某些$y$出现$a_{k+1}^Ty<0$，但只要训练样本集线性可分，无论初值为什么，有限次迭代都能收敛。

最小平方误差准则函数

规范化增广样本向量$y_i$，增广权向量$a$，正确分类要求：$a^Ty_i>0$

本质就是求一组$N$个线性不等式的解。

样本集增广矩阵$Y$及一组$N$个线性不等式可由矩阵表示

引入余量$b=[b_1,b_2,\dots,b_N]^T$，$b_i$为任意给定正常数，$a^Ty_i=b_i>0$，则可表示为：

定义误差向量$e=Ya-b$，定义平方误差准则函数：

求解

则：

与其他方法的关系

与Fisher：当$b=[N/N_1,N/N_1,\dots,N/N_1(N_1个),N/N_2,N/N_2,\dots,N/N_2(N_2个)]^T$

MSE等价于Fisher

与Bayes：当$N\to \infin,b=u_N$时，则它以最小均方误差逼近Bayes判别函数$g(x)=P(\omega_1|x)-P(\omega_2|x)$

MSE方法的迭代解

伪逆解计算量大，实际使用的梯度下降法

满足一定条件时梯度下降结束。

也可以使用单样本修正调整权向量：Widrow-Hoff/最小均方根/LMS算法

其中$y_i$是使得$a_K^Ty_i\ne b_i$的样本。

多类问题

三种方法：

c-1 二类问题

分离符合与不符合$\omega_1$的点

c(c-1)/2 二类问题

分离每一对

定义c个线性离散函数

将$x$归于$w_j$类如果$g_i(x)>g_j(x),\forall j\ne i$

非线性判别函数

引言

线性判别函数：简单实用，但线性不可分时错误率大。

1. 使用新的特征
2. 非线性变换
3. 非线性分类器

分段线性判别函数

• 决策面由若干超平面段组成，计算相对比较简单
• 能够逼近各种形状的超平面，适应性强
• 多类情况下的线性判别函数分类
• 树状分类

如果两类可划分为线性可分的若干子类，则可以设计多个线性分类器，实现分段线性分类器。

基于距离的分段线性判别函数

分段线性距离分类器：将各类别划分为相对密集的子类，每个子类以它们的均值作为代表点，然后按最小距离分类。

判别函数：$\omega_i$有$l_i$个子类，将$\omega_i$的决策域$R_i$分成$l_i$个子域$R_i^1,R_i^2,\dots,R_i^{l_i}$，每个区域用均值$m_i^k$代表：

判别规则：

如果$g_j(x)=\arg\min_{i=1,\dots,c}g_i(x)$，则$x$属于$\omega_j$。

一般的分段线性判别函数

将每个大类分成若干子类，针对每个子类定义一个线性判别函数。

一般形式：$g_i^k(x)$表示第$i$类第$k$段线性判别函数，$l_i$是第$i$类所具有的判别函数个数，$w_i^k.w_{i_0}^k$扽别是第$k$段的权向量和阈值权：

第$i$类判别函数：

判别规则：如果$g_j(x)=\arg\min_{i=1,\dots,c}g_i(x)$，则$x$属于$\omega_j$。

决策面：$g_i^n(x)=g_j^m(x)$

问题：如何确定子类数目？如何求得各子类的线性判别函数？

分段线性判别函数的设计

已知子类划分

直接使用多类线性分类方法

如何知道子类划分？先验、聚类分析

只知道子类数目，不知道子类划分

使用错误修正法（此法介绍使用增广的判别函数形式表示$g_i^k(y)={a_i^{(k)}}^Ty$）

假设$\omega_i$，$\omega_i$类中有$l_i$个子类，每一类均存在一定数量训练样本：

1. 初始化：任意给定各类各子类权值${a_i^{(k)}}^T(0)$，通常使用小随机数
2. 在时刻$t$：当前权值为${a_i^{(k)}}^T(t)$，考虑某个训练样本$y_v\in\omega_j$，找出$\omega_j$类的子类中最大的判别函数${a_i^{(m)}}^T(t)y_v=\max_k{a_j^{(k)}}^T(t)y_v$
3. 考察当前权值对$y_v$的分类情况，若${a_j^{(m)}}^T(t)y_v>{a_i^{(k)}}^T(t)y_v,\forall i\ne j$，则${a_i^{(k)}}^T(t)$不变。若$\exist i\ne j,k=n,s.t.{a_j^{(m)}}^T(t)y_v\le{a_i^{(n)}}^T(t)y_v$，则$y_v$被错分，对其中最大者记为$(i^{'},n^{'})$修正：

重复迭代，直至收敛。式中$\rho$为自取步长

未知子类数目

使用树状分段线性分类器。

用凹函数的并来表示分段线性函数

设$l_i$为线性判别函数，则：

1. $l_1,l_2,\dots,l_r$都是分段线性判别函数
2. 若$A,B$都是分段线性判别函数，则：$A\wedge B,A\vee B$也是分段线性判别函数。
3. 对任何分段线性函数都可以表示为析取范式或合取范式。

析取范式中最小项$(L_{11}\wedge L_{22}\wedge\dots\wedge L_{1m})$称为凹函数。

对于多峰二类问题：设第一类有$q$个峰，则有$q$个凹函数，即：

每个凹函数$P_i$由$m$个线性判别函数来构成：

假设对于每个子类的线性判别函数$L_{ij}$都设计成：

最终判别规则：

例：

$\omega_1$分三个峰，$q=3$。

判别函数：

所以共有十三个分段判别函数

若$P>0$则$x\in\omega_1$，否则$x\in \omega_2$

用交遇区的样本设计分段线性函数

思想：寻找两类中最靠近的样本子集，用他们设计分类器。

步骤：

1. 用聚类分析等方法把每类样本分为若干子类
2. 考察子类间的距离$d(v_i^m,v_j^n)$
3. 寻找紧互对原型对$d(v_i^m,v_j^n)=\min_l(d(v_i^l,v_j^n))=\min_l(d(v_i^m,v_j^l))$
4. 用紧互对原型对设计分类面
5. 决策规则（可能有错分）：设最后得到$m$个超平面$H_i:\alpha _i^Ty=0$，记$z_i(x)=if\ \alpha _i^Ty>0: 1,\ else\ 0$，得$z(x)=[z_1(x),z_2(x),\dots,z_m(x)]$，对$z(x)$的每一种可能取值$z_j$，统计其在$\chi_1,\chi_2$两类样本中出现的次数$N_1(z_j),N_2(z_j)$，定义$\Omega(z_j)$：若$N_1(z_j),N_2(z_j)$很小，则$\Omega(z_j)=\delta$，否则若$L=\frac {N_1(z_j)}{N_1(z_j)+N_2(z_j)}>1$，则$\Omega(z_j)=1$，否则若$L<2$，$\Omega(z_j)=0$。
6. 最终决策规则：对输入$x$，若$\Omega(z_j)=1$则$x\in \omega_1$；若$\Omega(z_j)=0$，则$x\in\omega_2$；若$\Omega(z_j)=\delta$则拒绝。

二次判别函数

二次判别函数一般表示为：

其中：$\bar W$是$n\times n$维权向量，$W$为$n$维权向量，系数共有$l=\frac 1 2n(n+3)+1$（很大）

二次决策面为超二次曲面。

已知样本$\omega_1$集中，而$\omega_2$分散

定义$\omega_1$判别函数：

$k$决定超平面大小，$\mu$为$\omega_1$均值，$\Sigma$为$\omega_1$协方差。

已知样本$\omega_1,\omega_2$都集中

可以定义两个判别函数：

$\mu_i$为$\omega_i$均值，$\Sigma_i$为$\omega_i$协方差。

判别面方程：

神经网络综述

简介

神经网是一种模拟动物神经网络行为特征，进行分布式并行信息处理的算法。

这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。

基础：

1. 构成：大量简单的基本元件——神经元
2. 工作原理：模拟生物神经处理信息
3. 功能：进行信息的并行处理和非线性转换

特点：

1. 比较轻松地实现非线性映射
2. 具有大规模的计算能力

发展

1. MP模型
2. Hebb学习规则
3. 感知机模型
4. 感知器，局限性
5. 能量函数
6. 反向传播，解决多层前向神经网络学习问题

优劣势

优势：

1. 很强的自适应学习能力
2. 实现特征空间较复杂的划分
3. 能用高速并行处理系统实现

劣势：

1. 需要更多训练数据
2. 在普通计算机模拟运行速度较慢
3. 无法解释

本质

利用计算机语言模拟人脑做决定

神经元结构模型

几种代表性的网络模型

1. 单层前向神经网络——线性网络
2. 阶跃网络
3. 多层前向神经网络（反推学习规则，即BP神经网络）
4. Elman、Hopfield、双向联想记忆网络、自组织竞争网络

神经网络能干什么

函数逼近、数据聚类、模式分类、优化计算等。

BP神经网络

BP 神经网络是一种按**误差逆传播算法(反向传播）**训练的多层前馈网络，是应用广泛的神经网络模型之一。

BP网络能学习和存贮大量的输入-输出模式映射关系，而无需事前揭示描述这种映射关系的数学方程。

学习规则是使用最速下降法，通过反向传播来不断调整网络的权值和阈值，使网络的误差平方和最小。

BP神经网络模型拓扑结构包括输入层(input layer)隐层(hidden layer)和输出层(output layer)

特点

多层前馈神经网络，信号向前传播，误差向后传播。

工作原理

基本BP算法包括两个方面：信号的前向传播和误差的反向传播。即计算实际输出时按从输入到输出的方向进行，而权值和阈值的修正从输出到输入的方向进行。利用输出后的误差来估计输出层的直接前一层的误差，再 用这个误差估计更前一层的误差，如此反传下去，就获得了所有其他各层的误差估计。

工作流程

1. 网络初始化：根据训练数据确定网络输入神经元、隐含神经元、输出神经元数目，初始化各层神经元间的连接权值，初始化隐含层、输出层的阈值，给定学习率和神经元传递函数。
2. 隐含层输出计算：根据输入向量、输入层和隐含层连接权值、阈值，计算隐含层输出
3. 输出层输出计算：根据隐含层输出、连接权值、阈值，计算BP神经网络预测输出
4. 误差计算：根据预测输出和期望输出计算网络预测误差
5. 权值更新：根据网络误差更新网络权值
6. 阈值更新：根据网络误差更新
7. 判断是否结束

学习过程

正向传播：

输入样本$\to$输入层$\to$隐含层$\to$输出层

判断是否转入反向传播阶段：若输出层的实际输出与期望的输出不符。

误差反传：误差以某种形式在各层表示——修正各层单元的权值。

缺陷与改进

缺陷：

1. 学习效率低，收敛速度慢
2. 易陷入局部极小状态

改进：

隐含层层数：过少则误差大，过多则会过拟合，学习时间增长。

隐含层神经元数量一般使用经验判断，$m$为隐含层神经元数，$n$为输入层神经元数。$I$为输出层神经元数，$\alpha$为$1-10$间的常数，则：$m = \sqrt{n+l}+a,m=\log_2 n,m=\sqrt{nl}$ 等。

其它常用传统神经网络模型

径向基函数网络

特点：只有一个隐层，隐层单元采用径向基函数作为输出函数，输入层到隐层的权值固定为1，输出节点为线性求和单元，隐层到输出节点间权值可调。

径向基函数

某种沿径向对称的标量函数。通常定义为空间中任一点$x$到某一中心$x_c$之间欧氏距离的单调函数，可记作$k(||x-x_c||)$。

最常用的是高斯核函数：$k(||x-x_c||)=\exp\left\{-\frac{||x-x_c||^2}{2\delta^2}\right\}$

作用

把网络看作对未知函数的逼近器，输入层到隐层的基函数是非线性的，而输出是线性的，可看作先对原始非线性可分特征空间变换到另一空间，通过这一变换使得在新空间线性可分，再用线性单元解决问题。

可调参数

隐层基函数中心、方差，输出单元权值。

Hopfield 网络

Hopfield网络是一种反馈网络。反馈网络具有一般非线性系统的许多性质，如稳定性问题、各种类型的吸引子以及混沌现象等。它比前馈网络的内容复杂。

Hopfield还满足：

1. 权值对称：权矩阵为对称阵
2. 无自反馈：权矩阵对角线元素为0

自适应共振理论神经网络ART

自适应共振理论神经网络既能模拟人脑的可塑性，可以学习知识，又能模拟人脑的稳定性，学习新的知识但不破坏原有知识，即这种网络不仅能记忆新的知识，而且还保留已记忆的内容。

自组织特征映射神经网络SOM

人脑的记忆不是神经元与记忆模式的一一对应，而是一群神经元对应一个模式。

支持向量机

回顾：

• 线性判别函数
• Fisher线性判别函数
• 感知准则函数
• 最小平方误差准则函数
• 多类问题

线性支持向量机

SVM从线性可分情况下的最优分类面发展而来。

最优分类面就是要求分类线不仅能将两类正确分开，并且分类间隔最大。

SVM考虑找到一个超平面，并且使训练集中的点距离分类面尽可能远，也就是使其两侧的空白区域（margin）尽可能大。

样本集：$\{x_n.t_n\},n=1,2,\dots,N,x_n\in\mathbb R^d;t_n\in\{-1,1\}$

分类器：$y(x) = w^{T}x+b$

其中：

即：

样本集任意一点$x_n$到分类面的距离：

优化$w,b$使得margin最大。

求解很复杂，可以令超平面最近的点有：$t_n(w^{T}x_n+b) = 1$，则所有点都有：$t_n(w^{T}x_n+b) \ge 1$

这时只需要最大化$||w||^{-1}$，等价于：

转化为二次规划问题。

拉格朗日乘子法求解即可。

非线性支持向量机

对于非线性可分的数据样本，可通过适当的函数变换，将其在高维空间中转化为线性可分。

例如异或问题：

二维样本集：$x = (x_1.x_2)$

第一类$(0,0),(1,1)$，第二类$(1,0),(0,1)$

映射函数$\phi(x) = (x_1,x_2,x_1x_2)$

则：$(0,0)\to (0,0,0),(1,1)\to (1,1,1)$,$(1,0)\to (1,0,0),(0,1)\to (0,1,0)$

线性可分了。即将$y(x)=w^Tx+b$转化为$y(x)=w^T\phi(x)+b$。

核函数

决策时：原本为

转化为

其中：

核函数在特征空间中直接计算数据映射后的内积，简化了计算过程。

基于泛函理论，我们只需要知道核函数，没必要知道非线性变换的表达形式。

核函数需要满足Mercer定理：

$\mathbb R ^ n\times \mathbb R ^ n\to \mathbb R$上的映射$k$是一个有效核函数，当且仅当对于训练样本其相应的核函数矩阵是对称半正定的。即对于任何平方可积函数$g(x)$，有$\iint k(x,y)g(x)g(y)\mathrm dx\mathrm dy\ge 0$。

根据问题和数据不同，选择不同的核函数，如：

• 线性核：$k(x_1,x_2)=x_1^Tx_2$
• 多项式核：$k(x_1,x_2)=(<x_1,x_2>+R)^d$
• 高斯核：$k(x_1,x_2)=\exp\left\{-\frac{||x_1-x_2||^2}{2\sigma^2}\right\}$
• sigmoid核：$k(x_1,x_2) = \tanh(\beta_0x_1^Tx_2+\beta_1)$