备份一下之前的笔记
第三章 判别域代数界面方程
3.1 用判别域界面方程分类的概念
1.分类的基本原理
不用模式对应特征点在不同区域中散布。运用已知类别的训练样本进行学习，产生若干个代数界面$d(\vec x)=0$，将特征空间划分成一些互不重叠的子区域。
2.判别函数
表示划分界面的函数。
3.线性可分的定义
对于来自两类的一组模式$\vec x_1,\vec x_2,\dots,\vec x_N$，如果能用一个线性判别函数正确分类，则称他们是线性可分的。
4.分类方法的基本技术思路
- 利用训练样本求出分类器/判别函数
- 利用判别函数对未知类别样本分类
3.2 线性判别函数
一般形式是$d(\vec x)=w_1x_1+w_2x_2+\dots+w_nx_n+w_{n+1}$
$\vec w$称为权矢量或系数矢量
简化为$d(\vec x)=\vec w'\vec x$
其中$\vec x=(x_1,x_2,\dots,x_n,1),\vec w=(w_1,w_2,\dots,w_n,w_{n+1})$
$\vec x$和$\vec w$分别称为增广特征矢量和增广权矢量。
两类问题
对于两类问题
$d(\vec x)=\vec w'\vec x\begin{cases} >0\Rightarrow\vec x\in\omega_1\\ <0\Rightarrow\vec x\in\omega_2\\ =0\Rightarrow\vec x\in\omega_i或拒判\\ \end{cases}$
多类问题
1.$\omega_i/\bar\omega_i$两分法（第一种情况）
判别规则为：如果$\begin{cases} d_i(\vec x)>0\\ d_j(\vec x)\leqslant0&\forall j\ne i \end{cases}$则判$\vec x\in\omega_i$
注意这种方法存在不确定区域
2.$\omega_i/\omega_j$两分法（第二种情况）
对于任意两类之间分别建立判别函数
判别规则为：如果$d_{ij}(x)>0,\forall j\ne i$则判$\vec x\in\omega_i$
注意这种方法也存在不确定区域
3.没有不确定区域的$\omega_i/\omega_j$两分法（第三种情况）
令方法2中的判别函数为$d_{ij}(\vec x)=d_i(\vec x)-d_j(\vec x)=(\vec\omega_i-\vec\omega_j)'\vec x$
判别规则为：如果$d_i(\vec x)>d_j(\vec x),\forall j\ne i$则判$\vec x\in\omega_i$
或者：如果$d_i(\vec x)=\max_j[d_j(\vec x)]$则判$\vec x\in\omega_i$
小结
- 当$c>3$时，$\omega_i/\omega_j$法比$\omega_i/\bar\omega_i$法需要更多的判别函数式。
- $\omega_i/\omega_j$法使模式更容易线性可分
- 方法3判别函数数目与方法1相同，但没有不确定区，分析简单，是最常用的方法
3.3 判别函数值的鉴别意义、权空间及解空间
数学意义
- 系数矢量$\vec w=(w_1,w_2,\dots,w_n)$是该平面的法矢量。
- 判别函数$d(\vec x)$的绝对值正比于$\vec x$到超平面$d(\vec x)=0$的距离。
- 判别函数的正负表示出特征点位于哪个半空间中
权空间、解矢量、解空间
- 将权系数视为变量，则由其组成的增广权矢量的全体构成增广权空间。
- 系数矢量$\vec w$指向判别函数的正侧。
- 解矢量是能够正确分类的权矢量。
- 满足上面各不等式的$\vec w$必在该锥体中，即锥中每一点都是上面不等式组的解，解矢量不是唯一的，上述的凸多面锥包含了解的全体，称其为解区、解空间或解锥。
3.4 Fisher线性判别
思想：通过Fisher变换转换为利于分类的一维问题
方法：求权矢量$\vec w\Rightarrow$求满足上述目标的投影轴方向$\vec w_0$和在一维空间中确定判别规则。
希望经过投影后，类内离差度越小越好，类间离差度越大越好，根据这个目标作准则函数（即Fisher准则函数），并使其最大。
算法过于硬核，告辞
3.5 感知器算法
感知器算法
算法原理步骤
- 置步数$k=1$，令增量$\rho=\rho_0$，分别赋给初始增广权矢量$\vec w(1)$的各分量较小的任意值。
- 输入训练模式$\vec x_k$，计算判别函数值$\vec w'(k)\vec x_k$
- 调整增广权矢量
如果$\vec x_k\in\omega_1$和$\vec w'(k)\leqslant 0$，则$\vec w(k+1)=\vec w(k)+\rho\vec x_k$
如果$\vec x_k\in\omega_2$和$\vec w'(k)\geqslant 0$，则$\vec w(k+1)=\vec w(k)-\rho\vec x_k$
如果$\vec x_k\in\omega_1$和$\vec w'(k)>0$，或$\vec x_k\in\omega_2$和$\vec w'(k)<0$，则$\vec w(k+1)=\vec w(k)$ - 如果$k<N$，令$k=k+1$，返回2。如果$k=N$，检验判别函数是否都能正确分类，如果是，结束，否则令$k=1$，返回2。
收敛定理
如果训练模式是线性可分的，感知器算法在有限次迭代后便可以收敛到正确的解矢量。
一次准则函数和梯度下降法
- 当$\rho_k$为常数时，梯度下降法的迭代公式和感知器算法是一致的。
- 当$\rho_k$取常数时，$\rho_k$小收敛慢，$\rho_k$大震荡。
- 改进方法时$\rho_k$随$k$变化，称为可变增量法。
感知器算法在多类问题中的应用
不做要求
3.6 一般情况下的判别函数权矢量算法
（下面三个了解即可） 最小错分模式数目准则 分段二次准则函数 最小方差准则及W-H算法
3.7 广义线性判别函数
作非线性变换，将原来一维特征空间映射为二维特征空间，使其为线性可分的。
3.8 二次判别函数
$d(\vec x)=\vec x'W\vec x+\vec w'\vec x+w_{n+1}$
3.9 支持向量机
支持向量机以训练误差作为优化问题的约束条件，以置信范围值最优化作为优化目标，即SVM是一种基于结构风险最小化准则的学习方法，其推广能力明显优于一些传统的学习方法。
由于SVM的求解最后转化为二次规划问题求解，因此SVM的解是全局唯一的最优解。
SVM在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等许多机器学习问题中。
SVM方法的特点
- 非线性映射是SVM方法的理论基础，SVM利用内积核函数代替向高维空间的非线性映射。
- 对特征空间划分的最优超平面是SVM的目标，最大化分类边际的思想是SVM方法和核心。
- 支持向量是SVM的训练结果，在SVM分类决策中起决定作用的是支持向量。
- SVM的最终决策只由少数支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数。
- SVM的最终决策只由少数支持向量所确定，注定了该方法具有较好的鲁棒性
- 增删非支持向量样本对模型没有影响
- 支持向量样本集具有一定的鲁棒性
- 有些成功的应用中，SVM对核的选区不敏感
第四章 统计判别
4.0 前提条件
- 各类别总体概率密度是已知的
- 要判决的类别数是一定的
4.1 最小误判概率判决
判决规则：
如果：$l_{12}(\vec x)=\dfrac{p(\vec x|\omega_1)}{p(\vec x|\omega_2)}\gtrless\dfrac{P(\omega_2)}{P(\omega_1)}$，则判$\vec x\in\begin{cases} \omega_1\\ \omega_2\\ \end{cases}$
称$l_{12}(\vec x)$为似然比，称$\theta_{12}$为似然比阈值，记为$\dfrac{P(\omega_2)}{P(\omega_1)}$。
对于多类问题，若$P(\omega_i|\vec x)>P(\omega_j|\vec x),\forall j\ne i$，则判$\vec x\in\omega_i$
或者，若$P(\omega_i|\vec x)=\max_j[P(\omega_j|\vec x)]$，则判$\vec x\in\omega_i$
例题：对一批人进行癌症普查，患癌症者定为属$\omega_1$类，正常者定为属$\omega_2$类。统计资料表明人们患癌的概率$P(\omega_1)=0.005$，从而$P(\omega_2)=0.995$。设有一种诊断此病的试验，其结果有阳性反应和阴性反应之分，依其作诊断。化验结果是一维离散模式特征。统计资料表明：癌症者有阳性反映的概率为0.95即$P(x=阳|\omega_1)=0.95$，从而可知$P(x=阴|\omega_1)=0.05$，正常人阳性反映的概率为0.01即$P(x=阳|\omega_2)=0.01$, 可知$P(x=阴|\omega_2)=0.99$。
问有阳性反映的人患癌症的概率有多大？按照最小误判概率准则，阳性反映者应判为哪一类？
解：
$\begin{aligned} P(\omega_1|x=阳)&=\dfrac{P(x=阳|\omega_1)P(\omega_1)}{P(x=阳)}\\ &=\dfrac{P(x=阳|\omega_1)P(\omega_1)}{P(x=阳|\omega_1)P(\omega_1)+P(x=阳|\omega_2)P(\omega_2)}\\ &=\dfrac{0.95\times0.005}{0.95\times0.005+0.01\times0.995}\\ &=0.323 \end{aligned}$
$P(\omega_2|x=阳)=1-P(\omega_1|x=阳)=0.677$
所以$\vec x\in\omega_2$
或者似然比形式
$l_{12}(x)=\dfrac{P(x=阳|\omega_1)}{P(x=阳|\omega_2)}=\dfrac{0.95}{0.01}=95$
$\theta_{12}=\dfrac{P(\omega_2)}{P(\omega_1)}=\dfrac{0.995}{0.005}=197$
$\because l_{12}(x)<\theta_{12} \therefore x\in\omega_2$
例题：鱼类加工厂对鱼进行自动分类，$\omega_1$：鲈鱼；$\omega_2$：鲑鱼。模式特征$x=$长度。
已知：先验概率$P(\omega_1)=1/3,P(\omega_2)=1-P(\omega_1)=2/3$
$P(x=10|\omega_1=0.05),P(x=10|\omega_2=0.5)$
求：后验概率$P(\omega|x=10)$
解法1：利用Bayes公式
$\begin{aligned} P(\omega_1|x=10)&=\dfrac{P(x=10|\omega_1)P(\omega_1)}{P(x=10)}\\ &=\dfrac{P(x=10|\omega_1)P(\omega_1)}{P(x=10|\omega_1)P(\omega_1)+P(x=10|\omega_2)P(\omega_2)}\\ &=\dfrac{0.05\times1/3}{0.05\times1/3+0.5\times2/3}\\ &=0.048 \end{aligned}$
$P(\omega_2|x=10)=1-P(\omega_1|x=10)=0.952$
所以$\vec x\in\omega_2$，是鲑鱼
解法2：似然比形式
$l_{12}(x=10)=\dfrac{P(x=10|\omega_1)}{P(x=10|\omega_2)}=\dfrac{0.05}{0.5}=0.1$
判决阈值$\theta_{12}=\dfrac{P(\omega_2)}{P(\omega_1)}=\dfrac{2/3}{1/3}=2$
$l_{12}(x=10)<\theta_{12}$，所以$\vec x\in\omega_2$，是鲑鱼
4.2 最小损失准则判决
似然比形式
如果$\dfrac{P(\vec x|\omega_1)}{P(\vec x|\omega_2)}\gtrless\dfrac{P(\omega_2)(\lambda_{21}-\lambda_{22})}{P(\omega_1)(\lambda_{12}-\lambda_{11})}$，则判$\vec x\in\begin{cases} \omega_1\\ \omega_2\\ \end{cases}$
记似然比阈值$\theta_{12}=\dfrac{P(\omega_2)(\lambda_{21}-\lambda_{22})}{P(\omega_1)(\lambda_{12}-\lambda_{11})}$
则判决规则为：如果$l_{12}(\vec x)\gtrless\theta_{12}$，则判$\vec x\in\begin{cases} \omega_1\\ \omega_2\\ \end{cases}$
如果相等，称任判或拒判。
定理
使条件损失最小必然使总的平均损失最小、
当损失函数取0-1时最小损失准则等价于最小误判准则。
第五章 决策树与随机森林
5.1 决策树
概念和特点
- 决策树是一种树形结构，其中每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。
- 决策树学习时以实例为基础的归纳学习。
- 决策树采用的是自顶而下的递归方法。
- 决策树学习算法的最大优点是，他可以自学习，在学习的过程中不需要使用者了解过多背景知识，只需要对训练实例进行标注，就能进行学习。
- 属于有监督学习。从一类无序、无规则的十五中推理出决策树表示的分类规则。
- 建立决策树的关键，是在当前状态下选择哪些属性作为分类依据。
- 三种算法：ID3、C4.5、CART
对熵的理解
熵是随机变量不确定性的度量，不确定性越大，熵值越大。若随机变量退化成定值，熵为0。同理，均匀分布是最不确定的分布。
熵定义了一个概率分布函数到一个值的映射。
信息增益
当熵和条件熵中的概率由数据估计得到时，所对应的熵和条件熵分别为经验熵和经验条件熵。 信息增益表示得到特征A的信息而使得类X的信息的不确定性减少的程度。
特点
决策树对训练数据有很好的分类能力，但对未知的测试数据未必有好的分类能力，泛化能力弱，即可能发生过拟合现象。
bootstrap有放回抽样方法
随机森林
随机森林在bagging基础上做了修改。
从样本集中用Bootstrap采样选出n个样本；
从所有属性中随机选择k个属性，选择最佳分割属性作为节点建立CART决策树；
重复以上两步m次，即建立了m棵CART决策树
这m个CART形成随机森林，通过投票表决结果，决定数据属于哪一类
第六章 人工神经网络
人工神经网络的分类
从信息传递形式上
- 前向型：信息传递由后层神经元向前层神经元传递，从一层内的神经元之间没有信息交流。
- 反馈型：神经元之间不但互相作用，而且自身也有信息内耗。
按照神经元的学习过程
- 有指导学习网络
- 无指导学习网络
人工神经元模型的三个要素
- 一组连接，连接强度由各连接上的权值表示，权值为正表示激活，权值为负表示抑制，另有一个偏置值。
- 一个求和单元，用于求取个输入信号的加权和。
- 一个非线性的激活函数，起非线性映射的作用，并将神经元的输出幅度限制在一定范围内。
常用的激活函数
硬极限函数、线性函数、对数S形函数、双曲正切S形函数
特点
当分类效果不好时，调整神经元数目等其他参数。函数非线性程度越高，对于BP网络要求越高，则相同的网络逼近效果要差一些，因曾神经元数目对于网络逼近效果也有一定影响，一般来说，隐层神经元数目越多，则BP网络逼近非线性函数的能力越强。
第七章 深度学习
自动提取特征，学习特征
机器学习中，获得好的特征是识别成功的关键
- 高层的特征是低层特征的组合，从低层到高层的特征表示越来越抽象，越来越能表现语义或者意图
- 抽象层面越高，存在的可能猜测就越少，就越利于分类
浅层学习的局限
人工神经网络(BP算法)：—虽被称作多层感知机，但实际是种只含有一层隐层节点的浅层模型
SVM、Boosting、最大熵方法（如LR，Logistic Regression）:带有一层隐层节点（如SVM、Boosting），或没有隐层节点（如LR）的浅层模型
局限性：有限样本和计算单元情况下对复杂函数的表示能力有限，针对复杂分类问题其泛化能力受限。
深度学习好处
可通过学习一种深层非线性网络结构，实现复杂函数逼近，表征输入数据分布式表示。
深度学习VS神经网络
相同点：二者均采用分层结构，系统包括输入层、隐层（多层）、输出层组成的多层网络
不同点：
- 神经网络：采用BP算法调整参数，即采用迭代算法来训练整个网络。
- 深度学习：采用逐层训练机制。采用该机制的原因在于如果采用BP机制，对于一个deep network（7层以上），残差传播到最前面的层将变得很小，出现所谓的gradient diffusion（梯度扩散）。
神经网络的局限性：
- 比较容易过拟合，参数比较难调整，而且需要不少技巧；
- 训练速度比较慢，在层次比较少（小于等于3）的情况下效果并不比其它方法更优
不采用BP算法的原因
- 反馈调整时，梯度越来越稀疏，从顶层越往下，误差校正信号越来越小；
- 收敛易至局部最小，
- BP算法需要有标签数据来训练，但大部分数据是无标签的；
深度学习训练过程
第一步：采用自下而上的无监督学习
- 逐层构建单层神经元。
- 每层采用wake-sleep算法逐层调整。
这个过程可以看作是一个feature learning的过程，是和传统神经网络区别最大的部分。
第二步：自顶向下的监督学习
这一步是在第一步学习获得各层参数进的基础上，利用梯度下降法去微调整个网络参数。
深度学习的第一步实质上是一个网络参数初始化过程。深度学习模型是通过无监督学习输入数据的结构得到的，因而这个初值更接近全局最优，从而能够取得更好的效果。
深度学习具体方法模型
- 自动编码器（ AutoEncoder ）
- 稀疏自动编码器(Sparse AutoEncoder)
- 降噪自动编码器(Denoising AutoEncoders)
- 深度信念网络（Deep Belief Net)
- 卷积神经网络（CNN）
卷积神经网络
CNN的关键技术
局部感受野、权值共享、时间或空间子采样
CNN的优点
- 隐式特征抽取
- 降低了网络的复杂性；
- 采用时间或空间子采样，有一定鲁棒性；
- 语音识别和图像处理方面有着独特优势。
CNN的缺点：
构建CNN模型需要大规模有标签数据；处理大尺寸图像耗时较长
第八章 特征提取与选择
模式识别三大核心问题
- 特征数据采集
- 分类识别
- 特征提取与选择
特征提取的任务
在得到实际对象的若干具体特征之后，再由这些原始特征产生出对分类识别最有效、数目最少的特征，
特征提取的目的是使在最小维数特征空间中类间距离较大，类内距离较小。
选取特征的要求
- 具有很好的可分性。
- 具有可靠性。
- 尽可能强的独立性。
- 数量尽量少，同时损失的信息尽量小。
特征提取与特征选择的区别
- 特征选择：从L个度量值集合中按一定准则选出供分类用的子集，作为降维（m维，m<L）的分类特征。
- 特征提取：使一组度量值L通过某种变换产生新的m个特征作为降维的分类特征，
特征提取与选择的方法
直接选择法，变换法
变换法里的离散K-L变换(DKLT)主成分分析
有限离散K-L变换（DKLT）,是一种基于目标统计特性的最佳正交变换。
DKLT的性质
- 使变换后产生的新的分量正交或不相关
- 以部分新分量表示原矢量均方误差最小
- 使变换矢量更趋确定、能量更趋集中
取x的自相关阵Rx或协方差阵Cx的特征矢量矩阵的转置作为变换矩阵的变换称为离散K-L变换。
$$\vec x=T'^{-1}\vec y=T\vec y=\sum_{i=1}^{n}y_i\vec t_i$$离散K-L展开式
$\lambda_i(R_{\vec x})\geqslant\lambda_i(C_{\vec x})$
这表明对于相同的m，第一种估计式比第二种估计式的均方差大。
步骤：
- 求样本集{X}的总体自相关矩阵R或协方差矩阵C。
- 求$R$或$C$的特征值$\lambda_j,j=1,2,\dots,n$。对特征值从大到小排序，选择前$d$个较大的特征值。
- 计算$d$个特征值对应的特征向量$\vec u_j,j=1,2,\dots,d$，构成变换矩阵$U$。
- 对$\{X\}$中的每个$X$进行K-L变换，得到变换后的向量$X^*$，$X^*=U^{\rm T}X$
第九章 句法模式识别
汉字、字符、语言、图像、生物的识别
定义
以结构基元为基础，利用模式的结构信息完成分类的过程。也称为句法模式识别。
基元
指构成模式结构信息的基本单元，本身不包含有意义的结构信息。
理论基础形式
语言
模式描述方法
符号串，树，图
模式判定
用一个文法表示一个类，m类就有m个文法，然后判定未知模式遵循哪一个文法。
在学习过程中，确定基元与基元之间的关系，推断出生成景物的方法。
判决过程中，提取基元，基元连接关系，句法分析。判断类型。
句法模式识别的特点
- 结构模式识别是与统计模式识，一个基于结构信息，一个基于特征值
- 结构模式识别可以得到每个模式的结构性质
- 结构模式识别的依据是模式间结构上的“相似性”
- 结构模式识别用小而简单的基元与语法规则描述和识别
- 大而复杂的模式，通过对基元的识别，进而识别子模式，最终识别复杂模式。
与自然语言对比
模式$\leftrightarrow$句子
子模式$\leftrightarrow$词组
基元$\leftrightarrow$单词
组合关系$\leftrightarrow$自然语言的文法
符合某个文法的所有句子的集合$\leftrightarrow$一个模式类
句法
- 句法是指由字（词）构成句子的方式，也就是一个句子组成的规则。
- 句法具有递归性
- 用句法来表达基元间的结构关系。
文法(类)
- 文法是指一类相似的句子的共同句法规则。
- 可以用文法来表示一类样本的共同特点。
- 对某个具体的句子进行句法分析，判别与某类的文法是否相似，可以实现模式识别。
文法推断
用已知类别的模式样本集训练类别文法的过程
句法分析
利用文法对未知类别的句法模式进行识别或分类的过程。
字母表，句子，语言，文法
- $V^*$：V中符号组成的所有句子的集合，包括空句；
- $V^+$：不包含空句的句子集合。
- 语言：由字母表中的符号组成的句子集合，用L表示
- 文法：构成一种语言的句子所必须遵守的规则。是一个四元式，由四个参数构成：
- $V_N$：非终止符的有限集，子模式的集合，大写字母表示。
- $V_T$：终止符有限集，基元的集合，字母表起始部分的小写字母表示 。
- P：产生式的有限集。用文法产生句子时的重写规则。
- S：起始符，代表模式本身，特殊的非终止符。用产生式构成句子时，必须由左边是S的产生式开始。
文法分类
0型文法、1型文法、2型文法和3型文法。