模式识别

模式识别复习

一、绪论

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)\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 _{j=1}^{c}p(x|{\omega }_j)P({\omega }_j)}\sum _{i=1}^{c}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 $\mathrm{使}$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 $\mathrm{的}\mathrm{函}\mathrm{数}（\mathrm{似}\mathrm{然}\mathrm{函}\mathrm{数}），\mathrm{等}\mathrm{式}\mathrm{左}\mathrm{边}\mathrm{的}\mathrm{式}\mathrm{子}\mathrm{构}\mathrm{成}\mathrm{似}\mathrm{然}\mathrm{比}。\mathrm{因}\mathrm{此}\mathrm{贝}\mathrm{叶}\mathrm{斯}\mathrm{决}\mathrm{策}\mathrm{规}\mathrm{则}\mathrm{可}\mathrm{以}\mathrm{解}\mathrm{释}\mathrm{成}\mathrm{如}\mathrm{果}\mathrm{似}\mathrm{然}\mathrm{比}\mathrm{超}\mathrm{过}\mathrm{某}\mathrm{个}\mathrm{不}\mathrm{依}\mathrm{赖}\mathrm{观}\mathrm{测}\mathrm{值}$x$\mathrm{的}\mathrm{阈}\mathrm{值}，\mathrm{那}\mathrm{么}\mathrm{可}\mathrm{判}\mathrm{决}\mathrm{为}$_1$。

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

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

$$\lambda ({\alpha }_i|{\omega }_j)=\{\begin{array}{l}0,i=j\\ 1,i\ne j\end{array}i,j=1,...,c$$

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

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

  对任给$j\ne i$， 如果$P({\omega }_i|x)>P({\omega }_j|x)$ ，则判决为${}_i$

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

• 损失函数

  $$\lambda ({\alpha }_i|{\omega }_j)=\{\begin{array}{ll}0,& i=j\\ {\lambda }_s,& i\ne j\\ {\lambda }_r,& reject\end{array}$$

• 风险函数

  $$R({\alpha }_i|x)=\sum _{j=1}^c{\lambda }_{ij}P({\omega }_j|x)$$
  $$R_i(x)=\{\begin{array}{ll}{\lambda }_s[1-P({\omega }_i|x)],& i=1,...,c\\ {\lambda }_r,& reject\end{array}$$

• 决策规则

  $$\arg \underset{i}{min}{R}_i(x)=\{\begin{array}{ll}\arg \underset{i}{max}P({\omega }_i|x),& if\underset{i}{max}P({\omega }_i|x)>1-{\lambda }_r/{\lambda }_s\\ reject,& otherwise\end{array}$$

  最大后验概率小于阈值$1-{\lambda }_r/{\lambda }_s$时，拒识。

4.判别函数和决策面

• 判别函数：

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

  分类决策 $\arg \underset{i}{max}{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.高斯概率密度

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

$$\begin{gathered} p(x)=\frac{1}{\sqrt{2\pi }\sigma }\exp [-\frac{1}{2}(\frac{x-\mu }{\sigma }{)}^2] \\ \mu \equiv \epsilon [x]={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}xp(x)dx \\ {\sigma }^2\equiv \epsilon [(x-\mu {)}^2]={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}(x-\mu {)}^{2}p(x)dx \end{gathered}$$

• 多元密度函数

$$\begin{gathered} p(x)=\frac{1}{(2\pi {)}^{d/2}\text{abs}{\mathrm{\Sigma }}^{1/2}}\exp [-\frac{1}{2}(x-\mu {)}^t{\mathrm{\Sigma }}^{-1}(x-\mu )] \\ \mu \equiv \epsilon [x]=\int xp(x)dx{\mu }_i=\epsilon [x_i] \\ \mathrm{\Sigma }\equiv \epsilon [(x-\mu )(x-\mu {)}^t]=\int (x-\mu )(x-\mu {)}^{t}p(x)dx \\ {\sigma }_{ij}=\epsilon [(x_i-{\mu }_i)(x_j-{\mu }_j)]\mathrm{若}{x}_i\mathrm{与}{x}_j\mathrm{独}\mathrm{立}，\mathrm{则}{\sigma }_{ij}=0 \end{gathered}$$

• 协方差矩阵$\mathrm{\Sigma }$ 的性质

  • 实对称

  • 特征值分解，特征向量构成的矩阵$\mathrm{\Phi }$是正交的

  • 可对角化 ${\mathrm{\Phi }}^T\mathrm{\Sigma }\mathrm{\Phi }=\mathrm{\Lambda }$

  • 应用：PCA

  • 服从正态分布的随机变量的线性组合（独立或非独立的都可以）也是一个正态分布。定义白化变换$A_w=\mathrm{\Phi }{\mathrm{\Lambda }}^{-t1/2}$ ，可以产生一个圆轴对称的高斯分布。

    $$\begin{array}{rl}{A}_w^t\mathrm{\Sigma }{A}_w& ={\mathrm{\Lambda }}^{-1/2}{\mathrm{\Phi }}^t\mathrm{\Sigma }\mathrm{\Phi }{\mathrm{\Lambda }}^{-1/2}\\ & ={\mathrm{\Lambda }}^{-1/2}\mathrm{\Lambda }{\mathrm{\Lambda }}^{1/2}\\ & =I\end{array}$$

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{\mathrm{\Sigma }}_i^{-1}(x-{\mu }_i)-\frac{d}{2}\ln 2\pi -\frac{1}{2}\ln \text{abs}{\mathrm{\Sigma }}_i+\ln P({\omega }_i)$$

• 特殊情况讨论：

  • ${\mathrm{\Sigma }}_i={\sigma }^{2}I$

    • 各特征统计独立，且每个特征具有相同的${\sigma }^2$

    • 等价的线性判别函数：

      $$\begin{gathered} g_i(x)=w_i^{t}x+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) \end{gathered}$$

    • 决策面：

      $$

      $$

      $$x_0=\frac{1}{2}({\mu }_i+{\mu }_j)-\frac{{\sigma }^2}{\text{norm}{{\mu }_i-{\mu }_j}^2}\ln \frac{P({\omega }_i)}{P({\omega }_j)}({\mu }_i-{\mu }_j)$$

• ${\mathrm{\Sigma }}_i=\mathrm{\Sigma }$ （LDF）

  • 所有类的协方差矩阵都相等，但各自的均值向量是任意的

  • 等价的线性判别函数：

    $$\begin{gathered} g_i(x)=w_i^{t}x+w_{i0} \\ {w}_i={\mathrm{\Sigma }}^{-1}{\mu }_i \\ {w}_{i0}=-\frac{1}{2}{\mu }_i^t{\mathrm{\Sigma }}^{-1}{\mu }_i+\ln P({\omega }_i) \end{gathered}$$

    • 决策面：

      $$x_0=\frac{1}{2}({\mu }_i+{\mu }_j)-\frac{1}{({\mu }_i-{\mu }_j{)}^t{\mathrm{\Sigma }}^{-1}({\mu }_i-{\mu }_j)}\ln \frac{P({\omega }_i)}{P({\omega }_j)}({\mu }_i-{\mu }_j)$$

• ${\mathrm{\Sigma }}_i=\mathrm{任}\mathrm{意}$ （QDF）

  • 每一类的协方差矩阵是不同的

  • 等价的线性判别函数：

    $$\begin{gathered} g_i(x)=x^t{W}_{i}x+w_i^{t}x+w_{i0} \\ {W}_i=-\frac{1}{2}{\mathrm{\Sigma }}_i^{-1} \\ {w}_i={\mathrm{\Sigma }}_i^{-1}{\mu }_i \\ {w}_{i0}=-\frac{1}{2}{\mu }_i^t{\mathrm{\Sigma }}_i^{-1}{\mu }_i-\frac{1}{2}\ln \text{abs}{\mathrm{\Sigma }}_i+\ln P({\omega }_i) \end{gathered}$$

7.分类错误率

• 2类的情况

$$\begin{array}{rl}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)\\ & =\underset{{\mathcal{R}}_2}{\int }p(x|{\omega }_1)P({\omega }_1)dx+\underset{{\mathcal{R}}_1}{\int }p(x|{\omega }_2)P({\omega }_2)dx\end{array}$$

• 一般情况

  $$\begin{array}{rl}P(correct)& =\sum _{i=1}^{c}P(x\in {\mathcal{R}}_i,{\omega }_i)\\ & =\sum _{i=1}^{c}P(x\in {\mathcal{R}}_i|{\omega }_i)P({\omega }_i)\\ & =\sum _{i=1}^c\underset{{\mathcal{R}}_i}{\int }p(x|{\omega }_i)P({\omega }_i)dx\end{array}$$

• 最大后验概率决策（MAP）的情况

  $$\begin{array}{rl}P(correct)& =\underset{x}{\int }\underset{i}{max}P(x|{\omega }_i)P({\omega }_i)dx\\ & =\underset{x}{\int }\underset{i}{max}P({\omega }_i|x)P(x)dx\end{array}$$
  $$P(error)=\underset{x}{\int }[1-\underset{i}{max}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}^{n}p(x_k|\theta )$

  • 最大化似然函数：$\underset{\theta }{max}p(D|\theta )\leftrightarrow {\text{gradient}}_{\theta }p(D|\theta )=0$

  • p维参数空间上的梯度向量：

    $${\text{gradient}}_{\theta }\equiv \left[\begin{array}{c}\frac{\partial }{\partial {\theta }_1}\\ ⋮\\ \frac{\partial }{\partial {\theta }_p}\end{array}\right]$$

  • ${\text{gradient}}_{\theta }p(D|\theta )=0$ 的解可能有解析解，也可能需要迭代求解（如梯度下降）

  • 对数似然函数：$l(\theta )\equiv \ln p(\mathcal{D}|\theta )l(\theta )=\sum _{k=1}^n\ln p(x_k|\theta )$

    最大似然估计：$\hat{\theta }=\arg \underset{\theta }{max}l(\theta )$

    ​ ${\text{gradient}}_{\theta }l=\sum _{k=1}^n{\text{gradient}}_{\theta }\ln p(x_k|\theta )=0$

    ​ $\frac{\partial l}{\partial {\theta }_j}=0,j=1,..,p$

  • 讨论当训练样本服从多元正态分布时的情况

    • $\mu$ 未知

      $\hat{\mu }=\frac{1}{n}\sum _{k=1}^n{x}_k$

    • $\mu$ 和$\mathrm{\Sigma }$ 均未知

      $\hat{\mu }=\frac{1}{n}\sum _{k=1}^n{x}_k$ $\hat{\mathrm{\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分）
  • 已知$\phi (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^{T}x+w_0$

• 两类情形的决策规则：

  $$\{\begin{array}{ll}x\in {\omega }_1,& ifg(x)>0\\ x\in {\omega }_2,& ifg(x)<0\\ uncertain,& ifg(x)=0\end{array}$$

• 两类情形的决策面：

  超平面$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^{\prime }(net)\to 0$ 时，$\delta \to 0$ ，从而$\delta w_{ij}\to 0$ ，相当于调节过程几乎停顿下来。梯度更新将在S型函数的饱和区域进行，即处在其导数$f^{\prime }(net)$ 非常小的区域内(平坦区域)。

    

    image-20220102170556841

  • 梯度消失

    

  • 局部最小

    

• 训练时间过长

  • 复杂问题需要很长时间训练
  • 可能选取了不恰当的训练速率$\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分）