模式识别复习

一、绪论

1.什么是模式识别

人类智能：感知、学习、思维、语言理解与对话、行为

人工智能研究内容：机器感知（模式识别）、机器学习、机器思维（问题求解）、自然语言处理、只能行为
模式识别：使计算机模仿人的感知能力，从感知数据中提取信息的过程。

非结构化数据—>结构化知识
模式识别相关问题：数据预处理、模式分割、运动分析、模式描述与分类（特征提取/选择、模式分类、聚类、机器学习）、模式识别应用研究

2.模式识别发展简史

80年代：多层神经网络，BP算法；卷积神经网络
90年代：SVM；多分类器系统（Ensemble）；半监督学习；多标签学习；多任务学习
21世纪初：概率图模型（马尔可夫随机场、隐马尔可夫模型、条件随机场）；迁移学习；深度学习
ML/PR/DM主要方法：分类/聚类/特征提取
- ML：从数据、经验中获取知识、规则、模型、参数的过程，主要研究通用理论算法，大部分针对分类
- DM：针对各种数据中的信息提取和知识发现
- PR：主要研究分类识别方法，面向感知应用
- CV：模仿人类视觉系统，实现视觉信息高层理解

3.模式识别形式化

模式的两个层次：样本&类别
模式识别核心技术：模式分类
模式的计算机表示：
- 识别对象的表示（特征）：特征矢量、特征空间
- 分类器表示：类别模型、判别函数、决策面

4.模式识别系统流程

训练/测试过程中的模式预处理和特征提取必须完全一致

5.模式分类器设计

数据划分的两个层次
- 性能评价：Training+Test
- 模型选择：Estimation+Validation
泛化性能（Bias-Variance Tradeoff图）

6.模式识别方法分类

按模式/模型表示方法分类
- 统计方法：需要大量数据训练，解释性差，与人类认知的相关性低
- 结构方法：小样本情况下性能良好，大样本训练困难，对outlier鲁棒
学习方法分类
- 监督学习
- 无监督学习
- 半监督学习
- 强化学习
- 领域自适应（迁移学习）：测试样本分布发生变化，分类器参数自适应
- 增量学习、在线学习：数据顺序出现（且过去数据不能保存），学新不忘旧
生成/判别（都属于统计模式识别方法？）
- 生成模型Generative：表示各个类别内部结构或特征分布，不同类别分别学习。
- 判别模型Discriminative：表示不同类别之间的区别，一般为判别函数、边界函数或后验概率。所有类别样本同时学习
- 混合模型的几种方式
  - 生成模型+判别学习
  - 混合模型 $f_1(x,\theta_1)+f_2(x,\theta_2)$
  - 混合学习准则 $l_1(x,\theta_1)+l_2(x,\theta_2)$

二、贝叶斯决策(生成模型)

1.分类问题的表示

类别： $\omega_i,i=1,...,c$
特征矢量： $x=[x_1,...,x_d] \in R^d$
先验概率： $P(\omega_i)\quad\textstyle\sum_{i=1}^c P(\omega_i)=1$
概率密度函数（条件概率）：$p(x|\omega_i)$
后验概率：$P(\omega_i|x)=\frac{p(x|\omega_i)P(\omega_i)}{p(x)}=\frac{p(x|\omega_i)P(\omega_i)}{\sum^{c}_{j=1}p(x|\omega_j)P(\omega_j)} \quad \sum^c_{i=1}P(w_i|x)=1$

3.最小风险决策（贝叶斯决策的一般形式）

风险函数 $\lambda(\alpha_i|\omega_j)$ 描述类别状态为$\omega_j$ 时采取行动$\alpha_i$ 的风险
条件风险$R(\alpha_i|x)=\sum_{j=1}^c \lambda(\alpha_i|\omega_j)P(\omega_j|x)$
为了最小化总风险$R=\int R(\alpha(x)|x)p(x)dx$ ，

对所有$i=1,...,a$ 计算条件风险$R(\alpha_i|x)=\sum_{j=1}^c \lambda(\alpha_i|\omega_j)P(\omega_j|x)$ ，

并且选择行为$_i $使$R(_i|x)$ 最小化。
两类分类问题
- 简化 $\lambda_{ij}=\lambda(\alpha_i|\omega_j)$ 表示当实际类别为$\omega_j$ 却误判为$\omega_i$ 所引起的损失。
  
  $R(\alpha_1|x)=\lambda_{11}P(\omega_1|x)+\lambda_{12}P(\omega_2|x)$
  
  $R(\alpha_2|x)=\lambda_{21}P(\omega_1|x)+\lambda_{22}P(\omega_2|x)$
- 最小风险决策基本规则（表示1）：
  
  如果$R(\alpha_1|x)<R(\alpha_2|x)$ ，则判为$\omega_1$
- 用后验概率形式表述为（表示2）：
  
  如果$(\lambda_{21}-\lambda_{11})P(\omega_1|x)>(\lambda_{12}-\lambda_{22})P(\omega_2|x)$ ，则判为$\omega_1$
- 利用贝叶斯公式，用先验概率和条件密度来表示后验概率，等价规则为（表示3）：
  
  如果$(\lambda_{21}-\lambda_{11})p(x|\omega_1)P(\omega_1)>(\lambda_{12}-\lambda_{22})p(x|\omega_2)P(\omega_2)$ ，则判为$\omega_1$
- 通常，一次错误判决所造成的损失比正确判决要大，所以可以合理假设$\lambda_{21}-\lambda_{11}$ 和$\lambda_{12}-\lambda_{22}$ 都是正的，等价规则为（表示4）：
  
  如果$\frac{p(x|\omega_1)}{p(x|\omega_2)}>\frac{\lambda_{12}-\lambda_{22}}{\lambda_{21}-\lambda_{11}} \frac{P(\omega_2)}{P(\omega_1}$ ，则判为$\omega_1$
  
  考虑$p(x|\omega_j)$ 作为$_j $的函数（似然函数），等式左边的式子构成似然比。因此贝叶斯决策规则可以解释成如果似然比超过某个不依赖观测值$x$的阈值，那么可判决为$_1$。

3.最小误差率分类（最大后验概率决策）

损失函数（“对称损失”或“0-1损失”函数）：

\[ \lambda(\alpha_i|\omega_j)= \begin{cases} 0, \quad i=j \\ 1, \quad i\neq j \end{cases} \qquad i,j=1,...,c \]

这个损失函数对应的风险（平均误差概率）：

\[ R(\alpha_i|x) &=\sum_{j=1}^c \lambda_{ij}P(\omega_j|x) \\ &=\sum_{j \neq i} P(\omega_j|x) \\ &= 1- P(\omega_i|x) \]

最小化平均误差概率条件下的贝叶斯决策规则：（后验概率最大）

对任给$j \neq i$，如果$P(\omega_i|x)\gt P(\omega_j|x)$ ，则判决为$_i $

3.5. 带拒识的决策（c+1 classes)

损失函数

\[ \lambda(\alpha_i|\omega_j)= \begin{cases} 0, & i=j \\ \lambda_s, & i\neq j \\ \lambda_r, & reject \end{cases} \]
风险函数

\[ R(\alpha_i|x) =\sum_{j=1}^c \lambda_{ij}P(\omega_j|x) \]

\[ R_i(x)= \begin{cases} \lambda_s[1-P(\omega_i|x)],&i=1,...,c \\ \lambda_r,&reject \end{cases} \]
决策规则

\[ \arg\min_i R_i(x)= \begin{cases} \arg\max_i P(\omega_i|x), &if \max_i P(\omega_i|x) \gt 1-\lambda_r/\lambda_s \\ reject, &otherwise \end{cases} \]

最大后验概率小于阈值$1-\lambda_r/\lambda_s$时，拒识。

4.判别函数和决策面

判别函数：

表征模式属于每一类的广义似然度$g_i(x),i=1,...,c$

分类决策 $\arg\max_i g_i(x)$

例如：
- 条件风险：$g_i(x)=-R(\alpha_i|x)$
- 后验概率：$g_i(x)=P(\omega_i|x)$
- 似然函数：$g_i(x)=\log p (x|\omega_i)+\log P(\omega_i)$
决策面：特征空间中两类判别函数相等的点的集合

5.0. 贝叶斯决策用于模式分类

贝叶斯决策的关键：
- 类条件概率密度估计
- 先验概率：从训练样本估计或假设等概率
- 决策代价$[\lambda_{ij}]$ ，一般为0-1代价

5.高斯概率密度

单变量高斯密度函数（正态分布）

\[ p(x)=\frac{1}{\sqrt{2\pi}\sigma}\exp[-\frac{1}{2}(\frac{x-\mu}{\sigma})^2] \\ \mu \equiv \varepsilon[x] = \int_{-\infty}^{\infty} xp(x)dx \\ \sigma^2 \equiv \varepsilon[(x-\mu)^2]= \int_{-\infty}^{\infty} (x-\mu)^2p(x)dx \]

多元密度函数

\[ p(x)=\frac{1}{(2\pi)^{d/2}\abs{\Sigma}^{1/2}}\exp[-\frac{1}{2}(x-\mu)^t\Sigma^{-1}(x-\mu)] \\ \mu \equiv \varepsilon[x] = \int xp(x)dx \quad \mu_i=\varepsilon[x_i] \\ \Sigma \equiv \varepsilon[(x-\mu)(x-\mu)^t]= \int (x-\mu)(x-\mu)^t p(x)dx \quad \\ \sigma_{ij}=\varepsilon[(x_i-\mu_i)(x_j-\mu_j)] \quad 若x_i与x_j独立，则\sigma_{ij}=0 \]

协方差矩阵$\Sigma$ 的性质
- 实对称
- 特征值分解，特征向量构成的矩阵$\Phi$是正交的
- 可对角化 $\Phi^T \Sigma \Phi =\Lambda$
- 应用：PCA
- 服从正态分布的随机变量的线性组合（独立或非独立的都可以）也是一个正态分布。定义白化变换$A_w=\Phi\Lambda^{-t1/2}$ ，可以产生一个圆轴对称的高斯分布。
  
  \[ \begin{align*} A^t_w\Sigma A_w&=\Lambda^{-1/2}\Phi^t\Sigma\Phi\Lambda^{-1/2}\\ &=\Lambda^{-1/2}\Lambda\Lambda^{1/2}\\ &=I \end{align*} \]

6.高斯密度下的判别函数（LDF&QDF）

二、4中由类似然函数相等得到的判别函数：$g_i(x)=\log p (x|\omega_i)+\log P(\omega_i)$

如果密度函数$p(x|\omega_i)$ 是多元正态分布，则可得到判别函数：

\[ g_i(x)=-\frac{1}{2}(x-\mu_i)^t\Sigma_i^{-1}(x-\mu_i)-\frac{d}{2}\ln{2\pi}-\frac{1}{2}\ln{\abs{\Sigma_i}}+\ln{P(\omega_i)} \]

特殊情况讨论：
- $\Sigma_i=\sigma^2I$
  - 各特征统计独立，且每个特征具有相同的$\sigma^2$
  - 等价的线性判别函数：
    
    \[ g_i(x)=w_i^tx+w_{i0}\\ w_i=\frac{1}{\sigma^2}\mu_i\\ w_{i0}=-\frac{1}{2\sigma^2}\mu_i^t\mu_i+\ln{P(\omega_i)} \]
  - 决策面：
    
    $$
    
    $$
    
    \[ x_0=\frac{1}{2}(\mu_i+\mu_j)-\frac{\sigma^2}{\norm{\mu_i-\mu_j}^2}\ln{\frac{P(\omega_i)}{P(\omega_j)}}(\mu_i-\mu_j) \]
$\Sigma_i=\Sigma$ （LDF）
- 所有类的协方差矩阵都相等，但各自的均值向量是任意的
- 等价的线性判别函数：
  
  \[ g_i(x)=w_i^tx+w_{i0}\\ w_i=\Sigma^{-1}\mu_i\\ w_{i0}=-\frac{1}{2}\mu_i^t\Sigma^{-1}\mu_i+\ln{P(\omega_i)} \]
  - 决策面：
    
    \[ x_0=\frac{1}{2}(\mu_i+\mu_j)-\frac{1}{(\mu_i-\mu_j)^t\Sigma^{-1}(\mu_i-\mu_j)}\ln{\frac{P(\omega_i)}{P(\omega_j)}}(\mu_i-\mu_j) \]
$\Sigma_i=任意$ （QDF）
- 每一类的协方差矩阵是不同的
- 等价的线性判别函数：
  
  \[ g_i(x)=x^tW_ix+w_i^tx+w_{i0}\\ W_i=-\frac{1}{2}\Sigma_i^{-1}\\ w_i=\Sigma_i^{-1}\mu_i\\ w_{i0}=-\frac{1}{2}\mu_i^t\Sigma_i^{-1}\mu_i-\frac{1}{2}\ln{\abs{\Sigma_i}}+\ln{P(\omega_i)} \]

7.分类错误率

2类的情况

\[ \begin{align*} P(error)&=P(x \in \mathcal{R}_2,\omega_1)+P(x \in \mathcal{R}_1,\omega_2)\\ &=P(x \in \mathcal{R}_2|\omega_1)P(\omega_1)+P(x \in \mathcal{R}_1|\omega_2)P(\omega_2)\\ &=\int\limits_{\mathcal{R}_2}p(x|\omega_1)P(\omega_1)dx+\int\limits_{\mathcal{R}_1}p(x|\omega_2)P(\omega_2)dx \end{align*} \]

一般情况

\[ \begin{align*} P(correct)&=\sum_{i=1}^c P(x\in \mathcal{R}_i,\omega_i)\\ &=\sum_{i=1}^cP(x\in\mathcal{R}_i|\omega_i)P(\omega_i)\\ &=\sum_{i=1}^c\int\limits_{\mathcal{R}_i}p(x|\omega_i)P(\omega_i)dx \end{align*} \]
最大后验概率决策（MAP）的情况

\[ \begin{align*} P(correct)&=\int\limits_x \max_i P(x|\omega_i)P(\omega_i)dx\\ &=\int\limits_x \max_i P(\omega_i|x)P(x)dx\\ \end{align*} \]

\[ P(error)=\int\limits_x[1-\max_i P(\omega_i|x)]P(x)dx \]

8.离散变量的贝叶斯决策

9.复合模式分类

10.往年试题

2018年
- 贝叶斯最小风险决策和最小错误率决策的决策规则（6分）
- d维空间，c类分类，每一类条件概率密度为高斯分布
  - 写出最小错误率决策的判别函数，并说明在什么条件下判别函数为线性判别函数（5分）
  - c=2，高斯密度条件下线性判别的决策面函数，说明类先验概率如何影响决策面的位置，并说明在什么情况下决策面与两个类中心差向量$\mu_1-\mu_2$ 垂直（举例说明两种情况即可）（6分）
2017年
- 贝叶斯最小风险决策和最小错误率决策的决策规则（5分）
- 引入拒识，最小损失决策的决策规则（5分）
- 2维空间，2类，概率密度为高斯分布，给出均值、协方差和先验概率
  - 分类误差最小的贝叶斯决策的决策面函数，并写出贝叶斯错误率（积分形式）（6分）
  - 当$\lambda_{11}=\lambda_{22}=0,\lambda_{12}=2\lambda_{21}$ ，请给出损失最小的贝叶斯决策的决策面函数（4分）
2016年
- 贝叶斯最小风险决策和最小错误率决策的决策规则（8分）
- d维空间，c类分类，假设各类先验概率相等，每一类条件概率密度为高斯分布
  - 类协方差矩阵不等和相等两种情况下的最小错误率决策判别函数（6分）
  - c=2，$P(\omega_1)=P(\omega_2)$ ，两类概率密度均为高斯分布且协方差矩阵相等，写出贝叶斯分类决策面和贝叶斯错误率的公式（6分）

三、参数估计

给定分类器结构/函数形式，从训练样本估计参数
统计生成模型的参数估计（概率密度）
- 1.最大似然估计
  
  假设参数为确定值，最优估计：似然度最大MLE
- 2.贝叶斯估计
  
  假设参数为随机变量，估计其后验分布MAP
统计判别模型的参数估计（判别函数）

1.最大似然估计

假设概率密度函数$p(x|\omega_i,\theta_i)$，估计$\theta_i$
样本数据$D_1,...,D_c$
- $D_i$ 中的样本独立同分布
- $D_i$ 用来估计$\theta_i$
估计一类模型的参数
- 似然函数：$p(\mathcal{D}|\theta)=\prod_{k=1}^np(x_k|\theta)$
- 最大化似然函数：$\max_\theta p(D|\theta)\leftrightarrow \gradient_\theta p(D|\theta)=0$
- p维参数空间上的梯度向量：
  
  \[ \gradient_\theta \equiv \begin{bmatrix} \frac{\partial}{\partial\theta_1} \\ \vdots\\ \frac{\partial}{\partial\theta_p} \end{bmatrix} \]
- $\gradient_\theta p(D|\theta)=0$ 的解可能有解析解，也可能需要迭代求解（如梯度下降）
- 对数似然函数：$l(\theta)\equiv\ln{p(\mathcal{D}|\theta)} \quad l(\theta)=\sum_{k=1}^n\ln{p(x_k|\theta)}$
  
  最大似然估计：$\hat{\theta}=\arg\max_\theta l(\theta)$
  
  $\gradient_\theta l =\sum_{k=1}^n\gradient_\theta\ln{p(x_k|\theta)}=0$
  
  $\frac{\partial l}{\partial \theta_j}=0,\quad j=1,..,p$
- 讨论当训练样本服从多元正态分布时的情况
  - $\mu$ 未知
    
    $\hat{\mu}=\frac{1}{n}\sum_{k=1}^n x_k$
  - $\mu$ 和$\Sigma$ 均未知
    
    $\hat{\mu}=\frac{1}{n}\sum_{k=1}^n x_k$ $\hat{\Sigma}=\frac{1}{n}\sum_{k=1}^n(x_k-\hat{\mu})(x_k-\hat{\mu})^t$

2.贝叶斯估计

*2.5最大似然估计和贝叶斯估计对比

当训练样本量趋近于无穷时，ML和BL的效果是一样的
计算复杂度：
- ML计算简单，只涉及一些微分运算或梯度搜索技术
- BL可能要求计算非常复杂的多重积分
可理解性：
- ML易理解，得到的结果是基于样本的最佳解答
- BL难于直观理解，得到的结果是许多可行解答的加权平均值，反映出对各种可行解答的不确定程度
对初始先验知识的信任程度：
- ML得到的结果$p(x|\hat{\theta})$ 的形式与初始假设的形式一致
- BL得到的结果$p(x|\hat{\theta})$ 的形式与初始假设的形式不一定相同
- 通过使用全部$p(\theta|\mathcal{D})$ 中的信息，BL比ML能够利用更多有用的信息
- 如果没有特别的先验知识（$\theta$ 均匀分布），BL和ML是相似的。
样本点很少的情况下，ML的效果并不好
ML估计的是$\theta$ 空间中的一个点，而BL估计的则是一个概率分布

3.特征维数问题

4.期望最大法

数据缺失情况下的参数估计

5.隐马尔可夫模型

6.往年试题

2018年
- 2维空间，2个类别分别4个样本，两类都服从高斯分布，求最大似然估计参数值。进一步假设两个类别先验概率相等，写出分类决策面公式（6分）
2016年
- 2维空间，2个类别分别4个样本，两类都服从高斯分布，求最大似然估计参数值。进一步假设两个类别先验概率相等，写出分类决策面公式（8分）

四、非参数方法

1.密度估计

2.Parzen窗方法

*2.5.Parzen窗估计和k-近邻估计的区别

3.K近邻估计

4.最近邻规则

5.距离度量

6.Approximation by Series Expansion

7.往年试题

2018年
- 说明Parzen窗估计和k-近邻估计的区别（4分）
- 给定2维空间三个样本点，写出概率密度函数$p(x)$ 的最近邻(1-NN)估计密度公式（这种情况下V为圆形面积）（4分）
- 对于c个类别，基于k-NN密度估计进行贝叶斯分类，写出各个类别的后验概率并证明（4分）
2017年
- 说明Parzen窗估计和k-近邻估计的区别（5分）
- 已知$\varphi(u)$ 写出概率密度函数的Parzen窗估计$p_n(x)$ （5分）
- 给定2维空间三个样本点，写出概率密度函数$p(x)$ 的最近邻(1-NN)估计并画出概率密度函数曲线图（5分）
2016年
- 说明Parzen窗估计和k-近邻估计的区别（5分）
- 对于c个类别，基于k-NN密度估计进行贝叶斯分类，写出各个类别的后验概率并证明（5分）

五、线性判别函数

假定用于分类的判别函数的形式已知，直接从样本来估计判别函数的参数
模式分类的途径：
- 估计类条件概率密度函数：
  - 利用贝叶斯公式求出后验概率
  - 核心步骤：概率密度估计（参数估计和非参数估计）
- 直接估计后验概率（K近邻）
- 直接计算判别函数
利用样本直接设计分类器的方法分类：
- 线性判别函数、SVM、Fisher线性判别函数
- 广义线性判别函数、非线性判别函数、核学习机

1.线性判别函数与决策面

基本形式：$g(x)=w^Tx+w_0$
两类情形的决策规则：

\[ \begin{cases} x \in \omega_1, & if\quad g(x) \gt 0\\ x \in \omega_2, & if \quad g(x) \lt 0\\ uncertain, & if\quad g(x) = 0 \end{cases} \]
两类情形的决策面：

超平面$H：g(x)=0$ ，位于该平面的任意向量与$w$ 垂直。
多类情形：

2.广义线性判别函数

3.感知准则函数

4.松弛方法

5.最小平方误差（MSE）准则函数

6.Ho-Kashyap方法

7.往年试题

2018年
- 简述感知器（感知准则函数）算法的基本思想，并给出一种感知器学习算法（5分）
2017年
- one-vs-all技巧，3类，3个判别函数，画出分类决策面（6分）
- 简述感知器（感知准则函数）算法的基本思想，并给出一种感知器学习算法（5分）
2016年
- 四个样本，两个类别，二维空间，批处理感知器算法求权向量（10分）

六、神经网络

1.人工神经元

2.拓扑结构

3.网络训练

Hebb训练方法（经验方法）：两结点的连接权重按它们的输出值之积来改变
$\delta$ 训练方法（分析方法）：梯度下降法
随机训练方法：随机改变一个权重，计算改变后产生的最终能量，并按如下准则来确定是否接受此改变，模拟退火算法
Kohonen训练方法（无监督）：自组织竞争型神经网络

4.单层前馈神经网络（单层感知机）

单样本随机更新算法：适用于超大规模数据

批量更新算法：所有样本完成之后再更新

5.多层感知器

6.BP算法

经典问题：

完全难以训练
- 网络的麻痹现象：$f'(net)\rightarrow 0$ 时，$\delta \rightarrow 0$ ，从而$\delta w_{ij} \rightarrow 0$ ，相当于调节过程几乎停顿下来。梯度更新将在S型函数的饱和区域进行，即处在其导数$f'(net)$ 非常小的区域内(平坦区域)。
- 梯度消失
- 局部最小
训练时间过长
- 复杂问题需要很长时间训练
- 可能选取了不恰当的训练速率$\eta$

7.径向基函数网络

8.反馈神经网络

9.自组织映射

10.卷积神经网络CNN

11.自编码器

12.Recurrent NN

权重是共享的，因此简单地采用现有BP方法显得效率不高。

Back Propagation Through Time（BPTT）算法

13.LSTM

14.往年试题

2018（15分）

d维空间，n个样本，c个类别，三层前向神经网络（输入层、隐含层、输出层），平方损失函数作为目标函数，写出权重$w_{ih}$ 和权重$w_{hj}$ 的更新公式，并简明扼要地给出其推导过程。
2017（15分）

d维空间，n个样本，c个类别，三层前向神经网络（输入层、隐含层、输出层），交叉熵损失函数作为目标函数，推导误差反向传播算法，并写出具体的推导过程。
2016（15分）
- 针对多层前馈神经网络，请给出误差反向传播算法（即BP算法）的原理；结合三层网络给出有关权重更新的公式，并用文字描述所述公式的含义。（9）
- 请描述自组织映射网络的构造原理；针对网络训练，请给出自组织算法的主要计算步骤。（6）

七、特征提取与选择

线性特征变换通常维度更低：PCA、LDA、ICA

非线性特征变换通常性能更好：KPCA、KLDA、Isomap、LLE、HLLE、LSTA

1.特征提取

特征提取的最终形式都是使用向量来表示数据样本，便于分析

语音特征提取
- 技术路线：预处理、分帧、加窗处理、特定数学运算得到低维向量作为提取的特征
- MFCCs特征（Mel Frequency Cepstral Coefficients梅尔倒谱系数）
文本特征提取
- 词频-逆向文档频率（TF-IDF）
- Word2Vec（主要模型：连续词袋模型CBOW，跳字模型Skip Gram）
视觉特征提取
- 局部二值模式（LBP）：应用于人脸识别
- Gabor特征提取
- 尺度不变特征变化（SIFT）：
  - 局部方法：对图像中的局部区域进行分析
  - 特征点检测+特征点描述
  - 技术路线：高斯尺度空间构建GSS，高斯差分尺度空间构建DoGSS，极值点检测，特征点精细定位，特征点主方向计算，特征描述子生成
  - 基于SIFT的图像匹配算法
- 视觉词袋（Bag of Visual Words）
  - 技术路线：提取特征，学习视觉词汇，用视觉词汇量化特征，用视觉单词的频率表达图像
- 哈尔特征（Haar）：应用于人脸识别
  - 一个Haar特征由一组方形滤波器组成，响应值为白色滤波器相应值-灰色滤波器相应值
  - 通过比较Haar特征值是否超过某个阈值来判断是否为人脸，需要集成大量haar特征的判定结果来判断（Adaboost）
  - 积分图快速计算
- 梯度方向直方图（HoG）：最早用于行人检测，后来发展成面向一般物体检测
  - 技术路线：预处理（颜色转换、Gamma校正），计算图像梯度信息，划分图像区域成若干个cell，统计每个cell的梯度方向直方图，将相邻区域内的cell组成block串联起来进行归一化得到block特征，将block特征串联起来组成图像HoG特征
  - 特征维度比较高，通常结合线性SVM进行分类

2.特征变换

线性降维

不同方法的差异：对低维子空间的性质有不同的要求，即对变换矩阵$W \in R^{d\times m}$施加不同的约束
- PCA
  - 目标：寻找一组方差较大的方向，将样本在该方向进行投影
  - 求解过程：
  - 算法步骤：
- LDA
  - 目标：寻找一组投影方向，使样本在投影之后类内样本点尽可能靠近，类间样本点尽可能互相远离，提升样本表示的分类鉴别能力
  - 求解过程：
  - 算法步骤：
  - 局部线性判别分析（Neighborhood constraints/Locally weighting）
- 多维缩放MDS
  - 目标：降维后的样本仍保持两两之间的距离
- 其他维数缩减方法
  - 经典方法：独立成分分析ICA，典型关联分析CCA，2DPCA，2DLAD，KPCA
  - 流形学习方法：LLE，Isomap，LE，LTSA
  - 深度学习方法：PCANet，RBM，DBN，DBM，AutoEncoder，Deep CCA
流形学习
- 在数学上，流形用于描述一个几何体，他在局部具有欧式空间的性质
- 基本思想：高维空间相似的数据点映射到低维空间距离也是相似的
- 方法：对于给定数据集，通过最近邻等方式构造一个数据图。然后在每一个局部区域，高维空间中的某种相似度/距离在低维空间中得以保持
- 几乎所有的流形学习方法都需要首先构建一个关于数据的图
- 经典算法：
  - LLE局部线性嵌入：保持样本线性重构关系
    
    最优线性表示系数：
    
    全局嵌入学习模型：
    
    计算流程：1.线性表示，2.保持表示，3.全局误差，4.低维嵌入
    
    算法步骤：
  - Isomap等距映射：保持样本对之间的测地距离
    
    算法步骤：
  - LE拉普拉斯特征映射：保持样本对之间的亲合度
    
    学习模型：
    
    算法步骤：
  - LTSA局部切空间对齐
  - LSE局部样条嵌入
  - LPP局部保持投影
    
    学习模型：
- 统一的学习模型：
  - 目标：通过非线性变换寻找给定高维数据的低维表示

3.特征选择

最优特征选择方法
- 穷举法
- 分支定界法
特征选择的次优方法（贪心策略）
- 过滤式特征选择方法：“选择”与“学习”独立
  - 单独特征选择法
  - 顺序前进特征选择法
  - 顺序后退特征选择法
  - 增l减r特征选择法
  - 启发式选择方法：Relief方法
- 包裹式特征选择方法：“选择”依赖“学习”
- 嵌入式特征选择方法：“选择”与“学习”同时进行

4.往年试题

2018（8分）
- 简述并比较PCA、CCA、LDA、ICA的区别和适用场景
- 详细阐述一种实现非线性数据降维的方式
2017（12分）
- 简述PCA（主成分分析）的主要思想及其求解过程
- 比较PCA、CCA、LDA、ICA的区别和适用场景
- 解释LDA（线性判别分析）所基于的数据分布假设，并阐述其不足之处
2016（12分）
- 简述LDA（线性判别分析）的主要思想
- 基于上述思想，给出两类问题的LDA目标函数
- 最优化上述目标函数，得到LDA结果

八、模型选择

1.引言

机器学习
- 学习=表示+评价+优化
  - 表示：为学习器选择一种表示就以为选择一个特定的分类器集合。该集合被称为学习器的假设空间

2.模型选择原则

3.模型评价标准

训练样本的划分
- 刀切法（留一法）：每次从样本集中删除一个或者多个样本
- 自助法（Bootstrap）：每次有放回地随机抽取n个样本
- 保持方法（Holdout）：一部分用于训练，一部分用于测试
- 交叉验证（cross-validation）：将数据平分为k个子集，用k-1个子集进行训练，余下的部分用于验证，并计算验证误差。重复这一过程k次，得到k次结果的平均。（常用于模型参数选择）

4.分类器集成

集成学习的有效条件：
- 每个单一的学习器错误率都应当低于0.5
- 进行集成学习的每个分类器应当各不相同
集成学习的常用技术手段：
- 通过处理训练数据（bagging，boosting）：对训练样本进行随机分组，对错分样本进行加权
- 通过处理特征：每次只选择一部分特征来训练
- 通过处理类别标号：对多类问题，一对一策略、一对多策略
- 通过改进学习方法：变更学习参数、模型结构
算法分类（按训练数据处理方式）
- Bagging
- Random subspace
- Boosting/adaboost
- 随机森林

5.层叠泛化Stacked Generalization

采用多层结构，第一层的学习器配置不同的学习算法$L_1,L_2,..,L_T$，第一层的输出作为第二层的输入，第二层学习层称为元学习器L

6.样本装袋Bagging

训练一组基分类器，每个基分类器通过一个bootstrap训练样本集（通过有放回地随机抽样）来训练
获得基本分类器之后，通过投票进行统计

7.随机子空间Random Subspace

通常也被称为属性装袋（attribute bagging）
基分类器通常由线性分类器、支持向量机等组成

8.Adaboost

9.对Adaboost的理论解释

10.基于Adaboost的人脸检测

11.往年试题

2018年

针对两类分类问题简述Adaboost算法的基本计算过程（5分）

九、聚类

1.引言

2.距离与相似性度量

3.K-means

4.Gaussian Mixture Models

5.Hierachical Clustring

6.Spectral Clustering

7.Kernel Clustering

8.Deep Clustering

9.往年试题

2018年
- 简述谱聚类算法的基本思想，并指出可能影响谱聚类性能的因素（5分）
- 按最小距离准则对六个样本进行分级聚类，并画出聚类系统树图（10分）
2017年
- 从混合高斯密度函数估计的角度，简述K-Means聚类算法的原理（4分）
- 按最小距离准则对六个样本进行分级聚类，并画出聚类系统树图（8分）
2016年
- K-menas对八个二维空间样本聚类的计算过程和结果（6分）
- 对GMM进行参数估计的过程中，哪些条件下可以导出K-means聚类算法（4分）

十、支持向量机与核方法

1.结构风险最小化

2.VC维

3.Hard-Margin SVM

4.Soft-Margin SVM

5.Dual Problem

6.Kernel Methods

7.模型选择

8.往年试题

2018年
2017年
2016年

十一、决策树方法

1.信息增益算法

2.ID3

3.C4.5

4.CART

5.过拟合

6.随机森林

7.往年试题

2018年
- 描述ID3、C4.5、CART三种决策树方法的区别（4分）
- 阐述随机森林（Random Forests）的核心思想（4分）

模式识别复习

一、绪论

1.什么是模式识别

2.模式识别发展简史

3.模式识别形式化

4.模式识别系统流程

5.模式分类器设计

6.模式识别方法分类

二、贝叶斯决策(生成模型)

1.分类问题的表示

3.最小风险决策（贝叶斯决策的一般形式）

3.最小误差率分类（最大后验概率决策）

3.5. 带拒识的决策（c+1 classes)

决策规则

4.判别函数和决策面

5.0. 贝叶斯决策用于模式分类

5.高斯概率密度

6.高斯密度下的判别函数（LDF&QDF）

7.分类错误率

8.离散变量的贝叶斯决策

9.复合模式分类

10.往年试题

三、参数估计

1.最大似然估计

2.贝叶斯估计

*2.5最大似然估计和贝叶斯估计对比

3.特征维数问题

4.期望最大法

5.隐马尔可夫模型

6.往年试题

四、非参数方法

1.密度估计

2.Parzen窗方法

*2.5.Parzen窗估计和k-近邻估计的区别

3.K近邻估计

4.最近邻规则

5.距离度量

6.Approximation by Series Expansion

7.往年试题

五、线性判别函数

1.线性判别函数与决策面

2.广义线性判别函数

3.感知准则函数

4.松弛方法

5.最小平方误差（MSE）准则函数

6.Ho-Kashyap方法

7.往年试题

六、神经网络

1.人工神经元

2.拓扑结构

3.网络训练

4.单层前馈神经网络（单层感知机）

5.多层感知器

6.BP算法

7.径向基函数网络

8.反馈神经网络

9.自组织映射

10.卷积神经网络CNN

11.自编码器

12.Recurrent NN

13.LSTM

14.往年试题

七、特征提取与选择

1.特征提取

2.特征变换

3.特征选择

4.往年试题

八、模型选择

1.引言

2.模型选择原则

3.模型评价标准

4.分类器集成

5.层叠泛化Stacked Generalization

6.样本装袋Bagging

7.随机子空间Random Subspace

8.Adaboost

9.对Adaboost的理论解释

10.基于Adaboost的人脸检测

11.往年试题

九、聚类