2018年中科院自动化所模式识别考博真题解答

点击这里下载题目,提取码: wbs4

1、解

(1) 令$g_{i}(x)=\ln p(w_i|x)=\ln(p(x|w_i)p(w_i))$$=\ln p(x|w_i)+\ln p(w_i)$,则$g_{i}$可以作为$w_i$类的判别函数. 此时,决策规则为:

  • 如果$g_{i}(x)=\max g_k(x)\ (k=1,2\dots,c)$,则$x\in w_i$.

(2) 将$p(x|w_i)\sim N(\mu_i,\Sigma_i)$带入$g_{i}(x)$,有

$$ \begin{aligned} g_{i}(x)= & \ln p(x|w_i)+\ln p(w_i) \\ = & \ln\{\frac{1}{(2\pi)^\frac{d}{2}|\Sigma_i|^\frac{1}{2}}\exp(-\frac{1}{2}(x-u_i)^T\Sigma_i^{-1}(x-u_i))\}+\ln p(w_i) \\ = & -\frac{1}{2}\{(x-u_i)^T\Sigma_i^{-1}(x-u_i)\} - \frac{1}{2}\ln |\Sigma_i| - \frac{d}{2}\ln(2\pi) + \ln p(w_i)\\ = & -\frac{1}{2}(x^T\Sigma_i^{-1}x) + (u_i^T(\Sigma_i^{-1}+{\Sigma_i^{-1}}^T))x - \frac{1}{2}u_i^T\Sigma_i^{-1}u_i \\ & -\frac{1}{2}\ln |\Sigma_i|-\frac{d}{2}\ln(2\pi)+\ln p(w_i) \\ \end{aligned} $$
显然,当$-\frac{1}{2}(x^T\Sigma_i^{-1}x)$与$i$无关时,即$\Sigma_i=\Sigma_j\ (i, j=1,2,\dots,c)$时,判别函数$g_i(x)$为线性函数。

2、解

(1) Parzen窗概率密度估计函数为 $$p(x)=\frac{1}{N}\sum_{i=1}^N\frac{1}{\sqrt{2\pi}\sigma}\exp(-\frac{(x-x_i)^2}{2\sigma^2})$$ 当$\sigma=0.5$时 $$p(x)=\frac{1}{N}\sum_{i=1}^N\sqrt{\frac{2}{\pi}}\exp(-2(x-x_i)^2)$$ 其中$N=4$为样本个数。

(2) 概率密度函数为

$$p(x)=\left\{ \begin{aligned} \frac{1}{8|x-8|} & , & x>6 \\ \frac{1}{8|x-4|} & , & 2< x\le6 \\ \frac{1}{8|x|} & , & -1< x\le2 \\ \frac{1}{8|x+2|} & , & x\le-1 \end{aligned} \right. $$
曲线图为

3、解

(1) 算法步骤:

  1. 确定聚类个数$c$,随机选择$c$个聚类中心;

  2. 对每个样本点,选择与其欧式距离最近的聚类中心作为其类别代表,将具有相同类别代表的样本归为一类,划分为$c$个类,计算每个类的样本均值$m_i$,以$m_i$作为每类新的聚类中心,$i=1,\dots,c$;

  3. 对于第$i$类的一个样本$x'$,计算将其放入$j$类之后,总的平方误差的减少量$I_{ij}$ $$I_{ij}=\frac{n_i}{n_i-1}||x’-m_i||^2-\frac{n_j}{n_j+1}||x’-m_j||^2$$ 令$I_{ik}=\mathop{max}\limits_j{I_{ij}}$,如果$I_{ik}>0$,则将$x'$从第$i$个类别移动到第$k$个类别,更新$i$类和$k$类均值 $$m_i \leftarrow m_i-\frac{1}{n_i-1}(x’-m_i)$$ $$m_k \leftarrow m_k+\frac{1}{n_k+1}(x’-m_k)$$ 否则不移动$x'$;

  4. 重复2.和3.过程,如果移动任何样本都不会减少总的平方误差,则算法结束。

(2) 假设将$x'$移动到$D_j$聚类之后,$D_j$聚类新的均值为

$$m_j^*=m_j+\frac{1}{n_j+1}(x'-m_j)$$
$D_j$聚类新的平方误差为 $$ \begin{aligned} J_j^* =& \sum_{x\in D_j\cup {x'}}||x-m_j^*||^2 \\ =& \sum_{x\in D_j}||x-m_j^*||^2+||x'-m_j^*||^2 \\ =& \sum_{x\in D_j}||x-m_j-\frac{1}{n_j+1}(x'-m_j)||^2+||x'-m_j-\frac{1}{n_j+1}(x'-m_j)||^2 \\ =& \sum_{x\in D_j}\left\{||x-m_j||^2 + ||\frac{1}{n_j+1}(x'-m_j)||^2-\frac{2(x-m_j)^T(x'-m_j)}{n_j+1}\right\} \\ & +\frac{n_j^2}{(n_j+1)^2}||x'-m_j||^2 \\ =& J_j + \frac{n_j}{(n_j+1)^2}||x'-m_j||^2+\frac{n_j^2}{(n_j+1)^2}||x'-m_j||^2 \\ =& J_j + \frac{n_j}{n_j+1}||x'-m_j||^2 \end{aligned} $$

4、解

(1) Adaboost算法步骤:

  1. 选择m个弱分类器$f_j(x)\in {-1, 1}$, 如果$x$为第一类样本,则结果为$1$,否则结果为$-1$, $j=1,\dots,m$;
  2. 初始化样本权重$w_i=\frac{1}{n}$, $i=1,\dots,n$;
  3. 令$j=1\to m$,作如下操作:
    1. 使用$n$个由$w_i$加权的样本$x_i$构造分类器$f_j$,$i=1,\dots,n$;
    2. 计算$f_j$在训练样本上的分类错误率$e_j$,令$c_j=log\frac{1-e_j}{e_j}$. 如果$f_j$对$x_i$样本分类正确,则权重$w_i$不变,否则$w_i=w_i\cdot exp(c_j)$,$i=1,\dots,n$;
    3. 将$w_i$归一化,$i=1,\dots,n$.
  4. 构造最终分类器$f(x)=\mathrm{sgn}\left[\sum_{j=1}^m c_jf_j(x)\right]$.

(2) 训练误差为0后,Adaboost会继续增大分类间距,提升模型的泛化能力,减少测试误差

5、解

(1) K-L变换矩阵为

$$ \begin{aligned} \Sigma =& E[x\cdot x^T] \\ =& \frac{1}{8}\{(-4, 1)^T (-4, 1) + (-2, 1)^T (-2, 1) \\ =& (-4, -1)^T (-4, -1) + (-2, -1)^T (-2, -1) \\ =& (4, 1)^T (4, 1) + (2, 1)^T (2, 1) \\ =& (4, -1)^T (4, -1) + (2, -1)^T (2, -1)\} \\ =& \begin{gathered} \begin{pmatrix} 10 & 0 \\ 0 & 1 \end{pmatrix} \end{gathered} \end{aligned} $$
显然,$\Sigma$的特征值为$10$和$1$,对应的特征向量分别为$(1, 0)^T$和$(0, 1)^T$.

(2) 令两类集合分别为$w_1$和$w_2$, 各类样本均值分别为$m_1$和$m_2$,总的样本均值为$m$,两类样本概率分别为$P_1$和$P_2$,则 $$ \begin{aligned} & S_b=\sum_{i=1}^2P_i(m_i-m)(m_i-m)^T \
& S_w=\sum_{i=1}^2P_i\mathrm{E_{x\in w_i}}[(x-m_i)(x-m_i)^T] \end{aligned} $$ 对第一个特征计算样本的$S_b$和$S_w$得 $$S_b=9, S_w=1$$ 因此$J_5=10$. 对第二个特征计算样本的$S_b$和$S_w$得 $$S_b=0, S_w=1$$ 因此$J_5=1$. 由于$10>1$,所以应选择第一个特征进行分类任务。

6、解

(1) 原优化问题:

$$ \begin{aligned} & \min_{W,b} & \frac{1}{2}||W||^2+C\sum_{i=1}^n \xi_i\\ & s.t. & y_i(W^Tx_i+b)\ge1-\xi_i, \\ & & \xi_i\ge0, i=1,\dots,n. \end{aligned} $$
对偶优化问题:
$$ \begin{aligned} & \max_{\alpha} & \sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^na_ia_jy_iy_jx_i^Tx_j\\ & s.t. & \sum_{i=1}^na_iy_i=0, \\ & & 0\le\alpha_i\le C, i=1,\dots,n. \end{aligned} $$

(2) 当$C$很大时,分类超平面对错分样本比较敏感,因此要保证不错分的情况下,最大化最小间隔

(3) 当$C$很小时,分类超平面对错分样本不敏感,而对$W$的长度比较敏感

7、解

(1) 假设输入层神经元个数为$d$个,每个神经元的输入为$x_i$,$i=1,\dots,d$;隐藏层的神经元个数为$d_1$个,激活值分别为$h’_j$,输出分别为$h_j=\sigma_1(h’_i)$,其中$\sigma_1$为隐藏层的激活函数,$j=1,\dots,d_1$;输出层的神经元个数为$c$个,激活值分别为$y’_k$,输出为$y_k=\sigma_2(y’_k)$,其中$\sigma_2$为输出层的激活函数,$k=1,\dots,c$.

输入层与隐藏层之间的参数为$w^{(1)}_{ij}$和$b^{(1)}_j$,满足:

$$h'_j=\sum_{i=1}^dw^{(1)}_{ij}x_i+b^{(1)}_j$$

输入层与隐藏层之间的参数为$w^{(2)}_{jk}$和$b^{(2)}_k$,满足:

$$y'_k=\sum_{j=1}^dw^{(2)}_{jk}h_j+b^{(2)}_k$$

令$L$为网络的损失函数,则有:

$$\left\{ \begin{aligned} & \nabla_{w^{(2)}_{jk}}=\sum_{k=1}^c\frac{\partial L}{\partial y_k}\frac{\partial y_k}{\partial y'_k}\frac{\partial y'_k}{\partial w^{(2)}_{jk}} = \sum_{k=1}^c\frac{\partial L}{\partial y_k}\sigma'_2(y'_k)h_j \\ & \nabla_{b^{(2)}_k}=\sum_{k=1}^c\frac{\partial L}{\partial y_k}\frac{\partial y_k}{\partial y'_k}\frac{\partial y'_k}{\partial b^{(2)}_k} = \sum_{k=1}^c\frac{\partial L}{\partial y_k}\sigma'_2(y'_k) \\ & \nabla_{w^{(1)}_{ij}}=\sum_{k=1}^c\sum_{j=1}^{d_1}\frac{\partial L}{\partial y_k}\frac{\partial y_k}{\partial y'_k}\frac{\partial y'_k}{\partial h_j}\frac{\partial h_j}{\partial h'_j}\frac{\partial h'_j}{\partial w^{(1)}_{ij}} = \sum_{k=1}^c\sum_{j=1}^{d_1}\frac{\partial L}{\partial y_k}\sigma'_2(y'_k)w^{(2)}_{jk}\sigma'_1(h'_j)x_i\\ & \nabla_{b^{(1)}_j}=\sum_{k=1}^c\sum_{j=1}^{d_1}\frac{\partial L}{\partial y_k}\frac{\partial y_k}{\partial y'_k}\frac{\partial y'_k}{\partial h_j}\frac{\partial h_j}{\partial h'_j}\frac{\partial h'_j}{\partial b^{(1)}_j} = \sum_{k=1}^c\sum_{j=1}^{d_1}\frac{\partial L}{\partial y_k}\sigma'_2(y'_k)w^{(2)}_{jk}\sigma'_1(h'_j) \end{aligned} \right. $$

网络经过前向传播之后,得到了计算梯度$\nabla_{w^{(2)}_{jk}}$, $\nabla_{b^{(2)}_k}$, $\nabla_{w^{(1)}_{ij}}$, $\nabla_{b^{(1)}_j}$所需的各个变量的值,因此可以利用反向传播依次求出它们的值,然后利用梯度下降对参数$w^{(2)}_{jk}$, $b^{(2)}_k$, $w^{(1)}_{ij}$, $b^{(1)}_j$进行更新:

$$\left\{ \begin{aligned} & w^{(2)}_{jk}\gets w^{(2)}_{jk} - \eta\nabla_{w^{(2)}_{jk}} \\ & b^{(2)}_k\gets b^{(2)}_k - \eta\nabla_{b^{(2)}_k} \\ & w^{(1)}_{ij}\gets w^{(1)}_{ij} - \eta\nabla_{w^{(1)}_{ij}} \\ & b^{(1)}_j\gets b^{(1)}_j - \eta\nabla_{b^{(1)}_j} \end{aligned} \right. $$
其中$\eta$为学习率。
(2) 沿用(1)中的假设,计算步骤为:
  1. 初始化参数$w^{(2)}_{jk}$,$b^{(2)}_k$,$w^{(1)}_{ij}$, $b^{(1)}_j$;
  2. 利用前向传播过程得到输出,从输入$x_i$,得到$h_j$和$y_k$,$i=1,\dots,d$,$j=1,\dots,d_1$,$k=1,\dots,c$;
  3. 计算样本标签和输出$y_k$之间的差异,即损失函数$L$;
  4. 参数更新,如果模型损失函数小于阈值,则结束。否则,利用(1)中公式更新参数$w^{(2)}_{jk}$, $b^{(2)}_k$, $w^{(1)}_{ij}$, $b^{(1)}_j$的值;
  5. 重复1,2,3,4,直至结束。
(3) 如果神经网络中的激活函数为Sigmoid函数,以$\sigma_1$为例,即 $$ \sigma_1(x)=\frac{1}{1+\exp(-x)} $$ 则
$$ \sigma'_1(x)=\frac{\exp(-x)}{(1+\exp(-x))^2}=\sigma_1(x)(1-\sigma_1(x)) $$
当x远离$0$时,$\sigma'_1(x)\to 0$,从而$\nabla_{w^{(1)}_{ij}}\to 0$, $\nabla_{b^{(1)}_j}\to 0$,这样参数$w^{(1)}_{ij}$, $b^{(1)}_j$在训练过程中得不到有效更新,因此出现麻痹现象。

8、解

(1) 深度学习定义:深度学习是机器学习算法的一种,通过创建多层神经网络模型,使其能够自动提取样本中的特征,并对样本进行分类或回归,采用反向传播算法对参数进行更新,从而得到对样本有效分类或回归的模型。

(2)

  1. 卷积神经网络(CNN):图像分类、目标检测;
  2. 循环神经网络(RNN):机器翻译、人机对话;
  3. 全卷积神经网路(FCN):语义分割;
  4. 全连接神经网络:邮件分类;
  5. 图神经网络(GNN):知识图谱,推荐系统。