考点
- 贝叶斯
- SVM 对偶形式
- K-L 变换/PCA
- Logistic Regression
- AdaBoost
- 概率图模型、HMM
- BP/CNN
No Free Lunch: 没有最好的算法/学习器,不存在一个与具体应用无关的、普遍适用的“最优分类器/回归器”！仅在学习算法与问题align或match的情况下才有所谓“更优”！Ugly Duckling Theorem: **没有最优的特征: 世界上不存在分类的客观标准，一切分类标准都是主观的。**分类结果取决于选择什么特征作为分类标准，而特征的选择又依存于人的目的或价值观。丑小鸭是白天鹅的幼雏，在画家眼里，丑小鸭和白天鹅的区别大于两只白天鹅的区别；但在遗传学家眼里，丑小鸭与其父亲或母亲的差别小于父母之间的差别。Occam’s Razor: 越简单越好，如无必要，勿增实体。为了防止过拟合，尽量选择简单的模型、剪枝、正则化、惩罚机制、最小化描述长度(MDL)。Bias and Variance Dilemma- Bagging/Boosting
- Bagging: 通过有放回地采样得到 $m$ 个独立同分布的数据集，分别训练得到 $m$ 个模型，最后再模型融合；
- Boosting: 基分类器串行训练；样本点加权表示，且权重依赖于之前的分类器的性能，之前分类器分类错误的样本点在下个分类器中有更大的权重、决策采用加权多数表决方案合并；
概念题
模式的概念、直观特性以及模式分类的方法
答：模式是从事物获取的信息(特征)集合。模式往往表现为具有时间和空间分布的信息。
模式的直观特性：可观察性、可区分性、相似性；
根据样本数据的特性，模式分类问题可以分成监督学习方法、无监督学习方法、半监督学习方法；
模式分类的主要方法：数据聚类、统计分类、结构模式识别、神经网络等；
线性判别函数的基本概念、为何需要有非线性判别函数？
答：线性判别函数是对模式进行分类的线性的准则函数，用于判别各个模式所属的类别。
引入非线性判别函数的原因是线性判别要求模式线性可分，而现实世界中的特征往往是高度非线性的。
简述偏差方差分解及其推导过程，并说明偏差、方差、噪声三部分的内在含义
答：
$$\begin{align*}
E[L] &= \iint \left(f(\mathrm x)-y\right)^2p(\mathrm x,y) \mathrm{dx}\mathrm{d}y\
&= \iint \left(f(\mathrm x)-h(\mathrm x)+h(\mathrm x)-y\right)^2p(\mathrm x,y) \mathrm{dx}\mathrm{d}y, \color{blue}{\quad h(\mathrm x)=E[y|\mathrm x]=\int yp(y|\mathrm x)\mathrm{d} y}\
&= E\left[\left(f(\mathrm x)-h(\mathrm x)\right)^2\right] + \color{red}{E\left[\left(h(\mathrm x)-y\right)^2\right]} + 2\color{blue}{\iint \left(f(\mathrm x)-h(\mathrm x)\right)\left(h(\mathrm x)-y\right)p(\mathrm x, y) \mathrm{dx}\mathrm{d}y}\\
\end{align*}$$
$$\begin{align*}
\color{blue}{\iint \left(f(\mathrm x)-h(\mathrm x)\right)\left(y-h(\mathrm x)\right) p(\mathrm x, y)\mathrm{dx}\mathrm{d}y}&=\iint y\left(f(\mathrm x)-h(\mathrm x)\right)p(\mathrm x, y)-h(\mathrm x)\left(f(\mathrm x)-h(\mathrm x)\right)p(\mathrm x, y)\mathrm{dx}\mathrm{d}y\
&= \iint \left(f(\mathrm x)-h(\mathrm x)\right)p(\mathrm x)\color{blue}{p(y|\mathrm x)y}-h(\mathrm x)\left(f(\mathrm x)-h(\mathrm x)\right)p(\mathrm x, y)\mathrm{dx}\mathrm{d}y\
&= 0\\
E\left[\left(f(\mathrm x)-h(\mathrm x)\right)^2\right]&=\left[E[f(\mathrm x)]-h(x)\right]^2+E\left[(f(x)-E[f(\mathrm x)])^2\right]+\color{blue}{0}\\
\end{align*}$$
$$\begin{align*}
\mathrm{bias}&=E[f(\mathrm x)]-h(x)\
\mathrm{variance}&=E\left[(f(x)-E[f(\mathrm x)])^2\right]\
与模型无关的固有误差, \mathrm{\color{red}{noise}}&=\color{red}{E\left[\left(h(\mathrm x)-y\right)^2\right]}\\
E[L] &= \mathrm{bias}^2 + \mathrm{variance} + \mathrm{noise}\
\end{align*}$$
EM 算法求解 高斯混合模型(GMM) 的思想和过程，并分析 K-Means 和 高斯混合模型 在求解聚类问题中的异同
答：
详细描述 AdaBoost 算法，解释为什么 Adaboost 经常可以在训练误差为0后继续训练还可能带来测试误差的继续下降。
答：当训练误差为0后，AdaBoost 会继续增大分类间距，提升模型泛化能力，减小测试误差。
描述 Perception 模型，并给出其权值学习算法。
答：
以仅有一个隐含层的3层神经网络为例，形式化描述 Back-Propagation 算法中是如何对隐含神经元与输出层神经元之间的连接权值进行调整的。
答：
随机猜作为一个分类算法是否一定比 SVM 差？借此阐述你对 “No Free Lunch Theorem” 的理解。
答：
举例阐述你对 “Occam’s razor” 的理解
答：
Part I
概率论基础
先验概率、后验概率
协方差矩阵
贝叶斯判别
最小错误率判别、最小风险判别
正态概率贝叶斯判别
在多元正态概率的假设下，多变量正态类密度函数为:
$$
P(\mathrm x|\omega_i)=\frac{1}{(2\pi){D/2}|C_i|{1/2}}\exp\left{-\frac{1}{2}(\mathrm x-\mathrm m_i)TC_i{-1}(\mathrm x-\mathrm m_i)\right},\quad |C_i|=\det(C_i)
$$
贝叶斯判别，指的是给定一个模式样本，在 $M$ 个类别中找到最大的后验概率对应的类别做为分类结果，即 $\mathop{\arg\max}\limits_{\omega_i}P(\omega_i|\mathrm{x})$。
根据贝叶斯定理，有：
$$
\begin{align*}
P(\omega_i|\mathrm{x}) &=\frac{P(\omega_i)P(\mathrm{x}|\omega_i)}{P({\mathrm{x}})}\
&=\frac{P(\omega_i)}{P({\mathrm{x}})}\frac{1}{(2\pi){D/2}|C_i|{1/2}}\exp\left{-\frac{1}{2}(\mathrm x-\mathrm m_i)TC_i{-1}(\mathrm x-\mathrm m_i)\right},\quad |C_i|=\det(C_i)
\end{align*}
$$
对于正态概率判别来说，就是:
$$
\mathop{\arg\max}_{\omega_i}\frac{P(\omega_i)}{|C_i|^{1/2}}\exp\left{-\frac{1}{2}(\mathrm x-\mathrm m_i)TC_i{-1}(\mathrm x-\mathrm m_i)\right},\quad |C_i|=\det(C_i)
$$
对数表示, 令:
$$
\begin{align*}
d_i(\mathrm x)&=\ln P(\omega_i)-\frac{1}{2}\ln |C_i| -\frac{1}{2}(\mathrm x-\mathrm m_i)TC_i{-1}(\mathrm x-\mathrm m_i),\quad |C_i|=\det(C_i)\
&= \ln P(\omega_i)-\frac{1}{2}\ln |C_i| -\frac{1}{2}\mathrm xTC_i{-1}\mathrm x-\frac{1}{2}\mathrm m_iTC_i{-1}\mathrm m_i+\mathrm m_iTC_i{-1}\mathrm x
\end{align*}
$$
如果是两类问题判别，且$C_1=C_2=C$，那么有, 判别界面为：
$$
d_1(\mathrm x)-d_2(\mathrm x) = \ln \frac{P(\omega_1)}{P(\omega_2)}+(\mathrm m_1-\mathrm m_2)TC{-1}\mathrm x-\frac{1}{2}\mathrm m_1TC{-1}\mathrm m_1+\frac{1}{2}\mathrm m_2TC{-1}\mathrm m_2 = 0
$$
线性判别
- 两类问题
- 多类($M$类)问题：
- 多类情况 1 ($\omega_i/\bar{\omega}_i$ 两分法/One vs. Rest): $M$ 个判别函数, $x\in \omega_i$ 当且仅当 $d_i\gt 0, d_j\lt 0, \mbox{ for all }j\neq i$
- 多类情况 2 ($\omega_i/\omega_j$ 两分法/One vs. One): $\frac{M(M-1)}{2}$ 个判别函数, $x\in \omega_i$ 当且仅当 $d_{ij}\gt 0, \mbox{ for all }j\neq i$
- 多类情况 3 (无不确定区域的 $\omega_i/\omega_j$ 两分法): $M$ 个判别函数/估值函数, $x\in \omega_i$ 当且仅当 $d_i\gt d_j, \mbox{ for all }j\neq i$, 把 $M$ 类情况分成 $M-1$ 个两类问题
- 多类情况 1 和多类情况 2 的比较
- 对于M类模式的分类，多类情况1需要M个判别函数，而多类情况2需要M*(M-1)/2个判别函数，当M较大时，后者需要更多的判别式（这是多类情况2的一个缺点）。
- 采用多类情况1时，每一个判别函数都要把一种类别的模式与其余M-1种类别的模式分开，而不是将一种类别的模式仅与另一种类别的模式分开。
- 由于一种模式的分布要比M-1种模式的分布更为聚集，因此多类情况2对模式是线性可分的可能性比多类情况1更大一些（这是多类情况2的一个优点）。
广义线性判别
对模式 $x$ 进行非线性变换，得到维度更高的模式 $x^*$，然后再用线性判别函数来进行分类。
模式空间和权空间
Fisher 准则函数
$$
\begin{align*}
J_F(\mathrm w) &= \frac{(\tilde{\mathrm m}_1-\tilde{\mathrm{m}}_2)^2}{\tilde {\mathrm S}1^2 + \tilde{\mathrm S}2^2}\
&= \mathrm{\frac{wTS_bw}{wTS_ww}}
\end{align*}
$$
其中，$\mathrm{S_b}$ 为样本类间离散度矩阵，$\mathrm{S_w}$ 为总样本类内离散度矩阵。
$$
\begin{align*}
\tilde {\mathrm m}i &= \frac{1}{N_i}\sum{\mathrm y\in \Gamma_i’}\mathrm y=\frac{1}{N_i}\sum{\mathrm x\in \Gamma_i}\mathrm w^T\mathrm x=\mathrm w\left(\frac{1}{N_i}\sum{\mathrm x\in \Gamma_i}\mathrm x\right)=\mathrm w^T\mathrm m_i\
(\tilde {\mathrm m}_1-\tilde {\mathrm m}2)^2 &= (\mathrm w^T\mathrm m_1-\mathrm w^T\mathrm m_2)^2\
&=\mathrm w^T(\mathrm m_1-\mathrm m_2)(\mathrm m_1-\mathrm m_2)^T\mathrm w=\mathrm w^T\mathrm {S_b}\mathrm w\
\mathrm{\tilde S_i}^2&=\sum{\mathrm y\in \Gamma_i’}(\mathrm y-\tilde{\mathrm m}_i)^2=\mathrm {w^TS_iw}\
\mathrm{\tilde S_1}^2+\mathrm{\tilde S_2}^2 &= \mathrm{wT(S_1+S_2)w=wTS_ww}
\end{align*}
$$
最佳变换向量 $\mathrm{w*=S_w{-1}(m_1-m_2)}$
感知器算法
最小平方误差(LMSE)
- Ho-Kashyap(H-K)算法： 求解 $\mathrm{Xw=b}$，式中$\mathrm{b=(b_1, b_2,\cdots, b_n)^T}$，$\mathrm b$的所有分量都是正值。
利用平方误差做为损失函数$\mathrm{J(w,x,b)=\frac{1}{2}(Xw-b)^T(Xw-b)}$, 然后对$w$ 求偏导，令偏导数为0，得：
$$
\mathrm{w=(XTX){-1}XTb}=X#b
$$
这里$X^# =(XTX){-1}X^T$称为X的伪逆，X是N*(n+1)阶的长方阵。
然后对 $\mathrm b$ 求偏导数…
令 $\mathrm{e(k)=Xw(k)-b(k)}$，得到迭代式：
$$
\begin{align*}
\mathrm{w(1)} &= \mathrm{X^#b(1)}\
\mathrm{e(k)} &= \mathrm{Xw(k)-b(k)}\
\mathrm{w(k+1)} &= \mathrm{w(k)+CX^#|e(k)|}\
\mathrm{b(k+1)} &= \mathrm{b(k)+CX^#[e(k)+|e(k)|]}
\end{align*}
$$ - 模式类别可分性的判别
势函数法
- Hermite 多项式
Hermite Poly
特征选择
假设 $n$ 维空间中同一类样本各个模式样本点集 ${a^{(i)}}{i=1,2,\cdots,K}$，那么有:
$$
\begin{align*}
类内距离:&\
类内散布矩阵:& \mathrm{S=\sum{i=1}K{(a{(i)}-m)(a{(i)}-m)T}}, &\mathrm{m=\frac{1}{K}\sum_{i=1}Ka{(i)}}\
\end{align*}
$$
在两类/多类情况下，有：
$$
\begin{align*}
两类类间距离: &\mathrm{D2=\sum_{k=1}n(m_{1_k}-m_{2_k})^2}\
两类类间散布矩阵: & \mathrm{S_{b2}=(m_1-m_2)(m_1-m_2)^T}\
\color{red}{多类类间散布矩阵}: & \mathrm{S_{b}=\sum_{i=1}^c P(\omega_i) (m_i-m_0)(m_i-m_0)^T}, & \mathrm{m_0=\sum_{i=1}^cP(\omega_i)m_i}\
\color{red}{多类类内散布矩阵}: & \mathrm{S_w=\sum_{i=1}cP(\omega_i)E{(x-m_i)(x-m_i)T|\omega_i}=\sum_{i=1}^cP(\omega_i)C_i}\
多类总体分布的散布矩阵: & \mathrm{S_t=E{(x-m_0)(x-m_0)^T}=S_w+S_b}
\end{align*}
$$
总体散布矩阵是各类类内散布矩阵与类间散布矩阵之和
离散K-L变换(PCA)
对自相关矩阵/协方差矩阵 做特征分解
K-L 变换步骤：
- 计算各个类别的均值向量 $m_c$
- 计算各类协方差矩阵 $R_c$
- 计算总协方差矩阵 $R=\sum_c P(x\in c)R_c$
- 对 $R$ 进行特征分解：
$$
\begin{align*}
Rv=\lambda v ,\lambda\neq 0
&\quad \Rightarrow \quad (R-\lambda I) v=\mathbf 0 \
&\quad \Rightarrow \quad \mathrm{det}(R-\lambda I)=0\
&\quad \Rightarrow \quad 高斯消元求 \lambda\
&\quad \Rightarrow \quad 根据 Rv=\lambda v 高斯消元求 v\
\end{align*}
$$ - 取前 $k$ 大特征向量对应的特征向量组 $\Phi_{c\times k}$，线性变换（即逐样本 $y_i=\Phi^T x_i$）。
Part II
正则化
Lasso 回归: $\lvert \mathrm w \rvert=\sum_{j=1}^D\lvert w_j\rvert$
Ridge 回归: $\lVert \mathrm w \rVert2=\sum_{j=1}D\lvert w_j\rvert^2$
Lasso Regression (Least Absolute Shrinkage and Selection Operator):
$$
\begin{align*}
\hat{w}{Lasso} &= \mathop{\arg\min}\limits{w} J(x,w)\
&= \mathop{\arg\min}\limits_{w}\frac{1}{2}\lVert {wTx-y}\rVert2+\frac{1}{2}\lambda \lvert w\rvert \
\end{align*}
$$
Lasso 有特征选择的功能，得到的解是稀疏的，且解不一定是稳定的
Lasso 选择的变量个数受限于观测样本数 $N$Ridge Regression:
$$
\begin{align*}
\hat{w}{Ridge} &= \mathop{\arg\min}\limits{w} J(x,w)\
&= \mathop{\arg\min}\limits_{w}\frac{1}{2}\lVert {wTx-y}\rVert2+\frac{1}{2}\lambda w^Tw\
&= (XX^T+\lambda I)^{-1}XY\
\end{align*}
$$Ridge Regression:
Standard Least Square Regression:
$$
\begin{align*}
\hat{w} &= \mathop{\arg\min}\limits_{w} J(x,w)\
&= \mathop{\arg\min}\limits_{w}\frac{1}{2}\lVert {wTx-y}\rVert2\
&= (XXT){-1}XY\
\end{align*}
$$
当$(XX^T)$ 为奇异矩阵时：
- 可以对该矩阵进行PCA 降维/SVD 分解；
- 可以用Ridge 回归方法(因此Ridge 回归也称为 Soft-PCA)
Ridge Regression 允许维度$D$ 大于 样本数 $N$，
- 鲁棒性好，$XX^T+\lambda I$总是可逆的;
- 是一种隐式的降维方法
Elastic Net[2]
VC Dimension
Logistic Regression
Logistic Regression 是一个分类模型，基于假设的先验概率模型。
$$
f(w, x)=\frac{1}{1+\exp (w^Tx)}
$$
多元高斯混合模型
$$
\mathbf x\sim\mathcal N (\mu,\Sigma)\
p(\mathbf x) = \frac{1}{(2\pi){D/2}|\Sigma|{1/2}}\exp\left{ -\frac{1}{2}(\mathbf x - \mu)T\Sigma{-1}(\mathbf x - \mu) \right}
$$
马氏距离(Mahalanobis distance): 马氏距离等价于先对所有的输入x做线性变换后用欧式距离
$$
(x-\mu)T\Sigma{-1}(x-\mu)
$$
Part III
K-Means 聚类
GMM 聚类
EM 算法求解
维数灾难
随着空间维度的增长，数据点越来越分散，以至于距离和密度的概念变得越来越模糊
没有一种距离函数或相似性函数能避免高维带来的问题
降维主要思想
- 最小化重建误差
- 最大化投影后数据的方差
矩阵分解
特征分解
$$
A=V\Sigma V^{-1}
$$
$V$ 是矩阵的特征向量，$\Sigma$ 是特征值组成的对角矩阵
应用：MDS(Multiple Dimensional Scaling)
SVD 分解
$$
A=U\Sigma V^T
$$
$U$ 和 $V$ 是正交矩阵，$\Sigma$ 是奇异值矩阵
特征值和奇异值的物理意义：
- 从统计的角度:方差
- 从物理的角度:能量
特征向量/奇异值向量的物理意义：
- 按照特征值/奇异值降序排列，最大特征值/奇异值 $\lambda_1$ 对应的特征向量/奇异值向量 $u_1$ 为最大能量/方差的方向、次大的特征值/奇异值 $\lambda_2$ 对应的特征向量/奇异值向量 $u_2$ 为与 $u_1$ 正交最大能量/方差的方向、$\cdots\cdots$
PCA
求解算法
- 最大化方差/特征分解：寻找一个方向向量，使得数据投影到其上后方差最大(假设样本已经中心化)
- SVD 分解
在原始数据维度较高时，特征分解比较低效，且协方差矩阵 $\Sigma$ 比较大
PCA 总结
- 优点
- 特征向量方法
- 无超参
- 无迭代
- 没有局部最小值
- 缺点
- 只用了二阶统计量，不能处理高阶依赖
- 受限于线性投影
非线性方法
KPCA(Kernel Method + PCA)
通过 Kernel Method 来定义两个输入样本点的相似度。
算法步骤
- 计算由核函数计算核矩阵 $K$;
- 对核矩阵 $K$ 进行中心化，得到 $\bar K$;
- 对 $\bar K$ 进行特征分解;
- 取前 $d’$ 大的特征值对应的特征向量;
- 对原始数据进行核变换之后，乘以选出的特征向量矩阵.
流形学习
测地距离(最短路径)
ISOMAP算法
- 构建邻接图
- 计算最短路径 (算法瓶颈 1)
- 构建低维嵌入 (算法瓶颈 2: 特征分解)
- 对于新数据点, 我们可以训练一个回归模型给定原数据点去预测新的数据点
全局嵌入/局部嵌入
全局嵌入：保持所有样本点对之间的(欧式)距离或者测地距离来计算嵌入表达。如: MDS、ISOMAP。
局部潜入：试图通过保持局部的几何特性来恢复全局的非线性结构。如: 局部线性嵌入 (LLE) 和拉普拉斯特征映射(Laplacian eigenmap)
拉普拉斯特征映射(Laplacian Eigenmap)
- 根据𝜀邻域/K近邻来建边, 常见边权 $D_{ij}$计算方式有热核(Heat kernel)、二值化权重;
- 然后，对每个连通分量单独做图嵌入。构造连通分量的图 Laplace 矩阵 $L$;
- 转化为最优化问题：
$$\mathop{\arg\min}\mathbf{Tr}(Z^TLZ)\
\mbox{s.t. }ZTDZ=I,ZTDI=0$$ - 对 $L$ 矩阵进行特征分解，取前 $d’$ 个最小特征向量对应的特征向量;
- 然后对这些特征向量进行归一化。
自编码器
深度非线性自编码器学习如何投影数据到一个非线性流形，而不是一个子空间
概率图模型
节点表示随机变量/状态，边表示概率关系
类型
- 有向概率图模型 或 贝叶斯网络: 因果关系
- 无向图模型 或 马尔科夫随机场: 关联关系
HMM
$\lambda=(A_{N\times N}, B_{N\times M}, \pi)$ 分别表示状态转移概率矩阵、观测概率矩阵、初始状态概率向量。
- 概率计算: 求观测序列的概率 $P(O|\lambda)$
- 学习问题: 极大似然 $\mathop{\arg\max}\limits_\lambda P(O|\lambda)$
- 预测问题: 求最有可能的状态序列 $\mathop{\arg\max}\limits_{I=(i_1,i_2,\cdots,i_T)}P(I|\lambda)$
HMM 概率计算问题
前向概率
- 定义前向概率 $\alpha_t(i)$ 为给定HMM $\lambda$ 时，到时刻 $t$ 部分观测序列为 $o_1,o_2,\cdots,o_t$ 且状态为 $q_i$ 的概率;
$$\alpha_t(i)=P(o_1,o_2,\cdots,o_t,i_t=q_i | \lambda)$$ - 初始化 $\alpha_1(i)=\pi(i) b_i(o_1), \mbox{ for all } i=1,2,\cdots,N$;
- 递推方程：对 $t=1,2,\cdots,T$,
$$\alpha_{t+1}(i)=\sum_{j=1}^N \alpha_t(j)A_{ji}b_{i}(o_{t}),\quad b_i(o_t)=B_{io_t}, \mbox{ for all } i=1,2,\cdots,N$$ - 终止： $$P(O|\lambda)=\sum_{i=1}^N\alpha_T(i)$$
后向概率
- 定义后向概率 $\beta_t(i)$ 为给定HMM $\lambda$ 且 时刻 $t$ 状态为 $q_i $时，从时刻 $t+1$ 到 $T$ 的部分观测序列为 $o_{t+1},o_{t+2},\cdots,o_T$ 的概率;
- 初始化 $\beta_T(i)=1,\mbox{ for all } i = 1,2,\cdots,N$;
- 递推方程：对 $t=T-1,T-2,\cdots,1$,
$$\beta_{t}(i)=\sum_{j=1}^N A_{ij}\beta_{t+1}(j)b_j(o_{t+1}),\quad b_i(o_{t+1})=B_{io_{t+1}}, \mbox{ for all } i=1,2,\cdots,N$$ - 终止：$$P(O|\lambda)=\sum_{i=1}^N\pi(i)\beta_1(i)b_1(o_1)$$
Part IV
目标检测
目标检测
BP 算法
利用输出误差来估计输出层的直接前导层的误差，再用这个误差估计更前一层的误差，如此一层一层的反传下去，就获得了所有其他各层的误差估计，利用此误差更新权重
CNN
- 卷积层:局部连接(卷积，滤波器…)
- 非线性激活
- Pooling层:下采样，降维
References
- 1.Qingming Huang, Hong Chang, JiaFeng Guo, Shiguang Shan. PRML Course Slides, 2018. ↩
- 2.Xingwang Xiong. Notes on Elastic Net ↩
