UCAS模式识别与机器学习

国科大模式识别与机器学习笔记

期末答疑

选择题 8 题
大题 8-9 道
选择题用贝叶斯或者全贝叶斯都行，只要答案正确就行
作业题选做不算分
svm 要知道最基本的形式，优化，软间隔之类的分析，C 怎么变化
考试不会比给的计算题难
大题目过程怎么算都行只要答案对就可以
势函数不考了
SMO 不考
KKT 只要了解下

习题总结

朴素贝叶斯，算后验概率比一下
Fisher 线性判别
1. 准则函数:
2. 类间离散度矩阵：
3. 类内离散度矩阵：
4. 最佳变换向量：
5. 如果两类有概率权重，计算的时候要加上权重。
6. 计算的时候，是把进行行变换，变成，其中是单位阵。
7. 最后投影计算：
K-L 变换
1. 判断所有样本均值是否为 0，如果有类别概率，就加上这个概率权重
2. 计算协方差矩阵
3. 求矩阵的特征值和特征向量。使用计算出特征值，然后用得到特征向量。
4. 最后进行降维：
感知机
1. 记得先把所有的负样本乘以（-1），同时变成增广矩阵的形式，就是在最后添加一个类别特征，1 或者-1
2. 初始化权重最好是全 0。
3. 迭代的终止条件是所有的样本都被分对。
4. 迭代的过程，对每个样本进行计算：，其中是步骤数，如果结果大于 0，就进行梯度下降，，其中 C 是步长，就是学习率。如果不大于 0，就不改变权重。
广义线性判别
1. 。
2. 定义和，使得，，的各个分量为，且。
拉普拉斯平滑
1. 分子+1，分母+类别数
2. ，
带高斯噪声的模型计算对数似然
1. 高斯函数：
2. 令，然后带入到高斯函数里，就可以得到
3. 然后累乘可以得到似然函数，再 log 得到对数似然。
正则化项
1. 正则化项越大，模型越简单，越小，模型越复杂
2. 越大，训练误差增大，测试误差先降后升
SVM
1. 决策边界的问题
  1. hard margin 最小化的只是，会让 margin 最大化
  2. 如果是 sorft margin，松弛因子 C 越大，误差占的比例越大。越不会存在分错的点。
  3. C 趋向于 0 的时候，损失函数近似 hard margin，决策边界 margin 会很宽，而且不会在意部分样本错分类，因为就算错分了，C=0 也不会有惩罚。
  4. margin
  5. margin 越大，泛化能力越强。
  6. 当 C 很大的时候，噪声点可能会影响决策边界。因为支持向量就是决策边界上的点，如果新噪声点出现在决策边界里面，就会改变决策边界。
2. 注意对偶问题的损失函数是：。有个负号的。
3. 计算题，把所有样本点要带入，然后算出所有的，观察两类中最近的两个点，就是支持向量，然后计算。注意算的时候要除以支持向量个数。
4. 注意几个常见的核函数：
  1. 核函数是有效的，和核函数矩阵是半正定的，是充要条件。
  3. RBF 核/高斯核：
  4. 多项式核函数：
  5. sigmoidal 核：
k-means 慢慢算
k-means 是按照欧氏距离来的，所以两个类别之间能看到明显的分界线，在两个簇头连线的中垂线那里。GMM 会形成圆圆的簇，同时会有一定的去噪声的作用，对噪声不敏感。
半监督学习的假设：
1. 平滑假设：如果高密度空间中两个点相似，则对应的输出也相似
2. 聚类假设：如果点在同一个簇，则很有可能是同一类
3. 流形假设：高维数据大体满足一个低维的流形分布；邻近样本拥有相似输出；邻近的程度常用相似程度刻画。
贝叶斯球
1. 球能从 A 跑到 B，就表示 A 和 B 不条件独立
HMM的推断，使用前向算法和维特比解码，应该只会考推断
1. 初始化概率
2. 计算转移概率矩阵A，
3. 计算发射概率矩阵B，
4. 两种考法，一种用前向算法计算算未知X序列出现的概率，一种用维特比解码计算已知X最可能的状态序列。
5. 计算未知X序列出现概率：
  1. 表示产生部分输出序列并结束于的概率
6. 计算已知序列X最有可能的状态序列：
  1. 表示结尾状态时，最可能状态序列的概率
  3. 初始化：，其他都为0
  4. 计算每个时刻：，k是所有的状态的数目，也就是说要计算这个时刻，每个状态以它结尾的概率。
  5. 每个步骤记录的最有可能的状态就是max得到前一个状态值。哪个最大就是哪个
梯度提升
1. 用上次的函数计算残差，当前的基学习器就来拟合这个残差数据集：
2. 当前基学习器的权重是使得整体模型误差最小的权重：
Adaboost
1. 其实是一个不断更新样本权重的过程，用新的样本权重计算新的基分类器的权重
模式的概念：
1. ⼴义地说，存在于时间和空间中可观察的物体，如果我们可以区别它们是否相同或是否相似，都可以称之为模式。
2. 模式所指的不是事物本身，⽽是从事物获得的信息，因此，模式往往表现为具有时间和空间分布的信息。
3. 模式的直观特性:
  - 可观察性
  - 可区分性
  - 相似性
卷积：提取局部特征的手段，部分特征与filter滤波器相乘的操作。
池化：将局部特征进行压缩，逐步扩大卷积范围的有效手段，从而在计算量不显著上升的情况下获得更加全局的特征。
CNN和传统特征提取方法的异同：
1. 不同的特征之间权值共享
2. CNN的权重是学到的，Gabor的权重是预设的

贝叶斯系列

贝叶斯法则

朴素贝叶斯

朴素贝叶斯属于是生成式模型，要计算联合概率分布，再得到后验概率。

使用后验概率判别

使用似然比判别

似然比：
判别阈值：
若使用似然比来判断，则为：

其实把似然比的分式去掉，就是原始的贝叶斯判别

朴素贝叶斯和逻辑回归

贝叶斯最小风险判别

M 类的条件平均风险

，
其中，是本来应该属于类的模式被判别成类的是非代价。
- ，则，这时候表示不失分。
- ，则，分类错误，这时候相当于是失分
越小，越有可能是那个类别

同原始贝叶斯判别相同，也可以分为使用条件平均风险判别，和似然比判别。

两类下条件平均风险判别

两类下似然比判别

当分错的时候的时，形式就和原始的贝叶斯判别一样了。

多类情况贝叶斯最小风险判别

这里还是用原始的计算条件平均风险的方法计算，然后风险越小，就是那类。

特殊情况，当时，条件平均风险

正态分布模式的贝叶斯分类

M 类的多变量正态类密度函数

此时判别函数是一个超二次曲面
两个模式类别之间用一个二次判别界面分开，就可以求得最优的分类效果
这里说的多变量正态类密度，其实就是每个类别下，有多个特征，然后服从正态分布

知道了似然之后，就可计算后验概率，然后得到判别函数。这里因为是有指数，所以取对数。

判别函数记不住的话，可以记正态密度函数，然后推一下。

两类的特殊情况

分两种情况

- 判别界面是二次型方程，两类模式可以用二次判别界面分开
- x 是二维的时候，判别界面是二次曲线
- 判别界面是 x 的线性函数，为一超平面
- x 是二维的时候，判别界面是一条直线

只是多类情况的特殊情况，一样算，最后的判别函数用两个后验概率相减得到。

参数估计

贝叶斯分类从公式里就能看出，需要先验和似然才能算出后验。

如果知道分布，那就只要知道分布的参数，比如正态分布就只要知道均值和协方差矩阵。

两种方式：

将参数当做非随机变量处理，比如矩估计
将参数当成随机变量，比如贝叶斯参数估计

看成非随机变量

迭代运算形式（这里考到了就炸了）

看成随机变量

感觉看的有点头大。。

贝叶斯网络

线性判别系列

这一类是判别式模型，通过直接建模后验概率，得到判别函数，而不去管每一类是什么情况，不考虑联合概率分布。

线性判别

简单的两类问题下的线性判别，就是一条直线。

权向量，增广模式向量，增广权向量

多类情况的线性判别

二类情况就直接一个就可以，多类情况可以有三种划分的方法。

分为属于类和不属于类。M 类分成 M 个两类问题。因此有 M 个判别函数。有时候会遇到分不开的情况，比如其中一类被一个环包围了，这就需要用其他划分方法。
每两个类就弄一个判别函数，只把这两个类分开。因此 M 类就需要个判别函数。除了参数多的缺点，还存在不确定区域，即这个区域，对所有的都找不到一个的情况。
是第二种方法的特例，第二种方法是直接写出了两两之间判别的判别函数，而这里是分成每个类有一个自己的判别函数，但这个又不是情况一那样直接按照大于0还是小于0分。这里是比较各自判别函数的大小。如果某个类的判别函数值比所有其他类都大，那就分到这个类。
划分方法 1 和方法 2 的比较
- 对于 M 类模式的分类，多类情况 1 需要 M 个判别函数，而多类情况 2 需要 M*(M-1)/2 个判别函数，当 M 较大时，后者需要更多的判别式（这是多类情况 2 的一个缺点）。
- 采用多类情况 1 时，每一个判别函数都要把一种类别的模式与其余 M-1 种类别的模式分开，而不是将一种类别的模式仅与另一种类别的模式分开。有时候情况 1 分不开
- 由于一种模式的分布要比 M-1 种模式的分布更为聚集，因此多类情况 2 对模式是线性可分的可能性比多类情况 1 更大一些（这是多类情况 2 的一个优点）。

广义线性判别

在原本的模式空间中线性不可分，但是映射到高维空间后，变得线性可分。只要对原来的模式 x 做非线性变换就可以，之后再进行线性判别就可以。

这里的有多种情况，可以分为一次函数、二次多项式函数、r 次多项式函数

为一次函数
为二次多项式函数
为高次函数
1. 判别函数各项的一般化表达：，其中，且
例题

分段线性判别

在线性不可分的情况下，如果使用广义线性判别，会增加维数。维数的大量增加会使得在低维空间里解析和计算熵行得通的方法在高位空间遇到困难，增加计算复杂性。所以有时候要用分段线性判别。

分段线性判别函数设计上，采用最小距离分类的方法。

对于各类交错分布的情况，如果再用每类一个均值代表点来产生最小距离分类器，那么就会产生很明显的错误率。在这种情况下，可以先用聚类方法把一些类分解成若干个子类，再用最小距离分类。

模式空间和权空间

模式空间

模式空间是在模式 X 的空间中。

对线性方程，系数，把 w 作为该方程在三维空间中平面的法线向量，则该平面过原点且与 w 垂直。

权空间

权空间是在权重 W 的空间中。

Fisher 线性判别

考虑到高维空间比较复杂的问题，Fisher 线性判别对其进行了降维，把原本的 d 维空间压缩到一条直线上，就是投影在一条线上。然而，即使样本在 d 维空间里形成若干紧凑的互相分得开的集群，当把它们投影到一条直线上时，也可能会是几类样本混在一起而变得无法识别。但是，在一般情况下，总可以找到某个方向，使在这个方向的直线上，样本的投影能分得开。

所以，关键就是怎么找到一条最好的，最能把样本分开的投影线。

结论

Fisher 准则函数为：
其中，类间离散度矩阵
总样本类内离散度矩阵
各类的样本均值向量
最佳变换向量
是 Fisher 准则函数取得最大值时的解，就是 d 维 X 空间到 1 维 Y 空间的最佳投影方向。是一种降维的映射。
降维之和，只要确定一个阈值 T 就可以将投影点和 T 比较，进行分类判别。

推导过程

感知机模型

两类

对负例样本的模式乘以(-1)，统一得到：

如果，则。否则。C 是一个校正增量，和对应分错的样本相乘。

多类

要训练一个判别性能好的线性分类器，训练样本需要多少？如果 k 是模式的维数，令则训练样本需要 C 的 10-20 倍。

距离和散布矩阵

K-L 变换

原理不讲了，证明也不记了

PCA 总结

其实就是 PCA。

要使得 KL 变换后的误差最小，那么就需要将整体模式进行 K-L 变换之前，应先将其均值作为新坐标轴的原点，采用协方差矩阵 C 或自相关矩阵 R 来计算特征值。

误差的均方误差，其中，m 是降维时选择的最大特征值的数量，也就是说，均方误差等于没有选择的特征值的和。

协方差矩阵

自相关矩阵，当样本是 0 均值的时候，和协方差矩阵相同。

K-L 变换是在均方误差最小的意义下获得数据压缩（降维）的最佳变换，且不受模式分布的限制。对于一种类别的模式特征提取，它不存在特征分类问题，只是实现用低维的 m 个特征来表示原来高维的 n 个特征，使其误差最小，亦即使其整个模式分布结构尽可能保持不变
通过 K-L 变换能获得互不相关的新特征。若采用较大特征值对应的特征向量组成变换矩阵，则能对应地保留原模式中方差最大的特征成分，所以 K-L 变换起到了减小相关性、突出差异性的效果。在此情况下，K-L 变换也称为主成分变换（PCA 变换）。
需要指出的是，采用 K-L 变换作为模式分类的特征提取时，要特别注意保留不同类别的模式分类鉴别信息，仅单纯考虑尽可能代表原来模式的主成分，有时并不一定有利于分类的鉴别。