模式识别课程总结提要

1 贝叶斯决策方法

1.1 贝叶斯决策

假设：

1. 分类数已知
2. 各类别类条件概率分布已知

先验概率：(Pleft(omega_1 ight),~Pleft(omega_2 ight))

后验概率：

[Pleft(omega_1|x ight)=frac{Pleft(omega_1,x ight)}{P(x)}=frac{Pleft(x|omega_1 ight)Pleft(omega_1 ight)}{sum_iPleft(x|omega_i ight)Pleft(omega_i ight)} ]

贝叶斯决策：后验概率大的类

[Pleft(omega_1|x ight)>Pleft(omega_2|x ight)Rightarrow xin omega_1 ]

等价形式：

[Pleft(omega_i|x ight)=max_jPleft(omega_j|x ight)Rightarrow xin omega_i ]

1.2 最小错误率贝叶斯决策

最小错误率决策：

[Pleft(omega_i|x ight)=max_jPleft(omega_j|x ight)Rightarrow xin omega_i ]

等价形式：

[Pleft(x|omega_i ight)Pleft(omega_i ight)=max_jPleft(x|omega_j ight)Pleft(omega_j ight)Rightarrow xin omega_i ]

似然比：

[l(x)=frac{Pleft(x|omega_1 ight)}{Pleft(x|omega_2 ight)} >frac{Pleft(omega_2 ight)}{Pleft(omega_1 ight)} Rightarrow xin omega_1 ]

负对数似然：

[h(x)=-ln left[l(x) ight] <ln frac{Pleft(omega_1 ight)}{Pleft(omega_2 ight)} Rightarrow xin omega_1 ]

错误率：

[Pleft(e ight) riangleq int_{-infty}^{infty}{pleft(e,x ight)mathrm{d}x}=int_{-infty}^{infty}{Pleft(e|x ight)p(x)mathrm{d}x} ]

其中错误后验概率为

[Pleft(e|x ight)=min left{ Pleft(omega_1|x ight), Pleft(omega_2|x ight) ight} ]

最小错误率导出决策：

[min Pleft(e ight)Rightarrow max Pleft(omega_i|x ight) ]

两类错误率：使用先验概率与类条件概率密度计算

[egin{aligned} Pleft(e ight)&=Pleft(xin mathcal{R}_1,omega_2 ight)+Pleft(xin mathcal{R}_2,omega_1 ight)\ &=Pleft(xin mathcal{R}_1|omega_2 ight)Pleft(omega_2 ight)+Pleft(xin mathcal{R}_2|omega_1 ight)Pleft(omega_1 ight)\ &=Pleft(omega_2 ight)int_{mathcal{R}_1}{pleft(x|omega_2 ight)}mathrm{d}x+Pleft(omega_1 ight)int_{mathcal{R}_2}{pleft(x|omega_1 ight)}mathrm{d}x\ &=Pleft(omega_2 ight)P_2left(e ight)+Pleft(omega_1 ight)P_1left(e ight) end{aligned} ]

多类错误率：通过平均正确率来计算平均错误率

[egin{aligned} Pleft(c ight) &=sum_{j=1}^c{Pleft(xin mathcal{R}_j|omega_j ight)Pleft(omega_j ight)}\ &=sum_{j=1}^c{int_{mathcal{R}_j}{pleft(x|omega_j ight)Pleft(omega_j ight)}}mathrm{d}x end{aligned} ]

[egin{aligned} Pleft(e ight) &=sum_{i=1}^c{sum_{j e i}{Pleft(xin mathcal{R}_j|omega_i ight)Pleft(omega_i ight)}}\ &=1-Pleft(c ight) end{aligned} ]

1.3 最小风险贝叶斯决策

基本思想：不同的决策错误所带来的损失可能不同

决策论表述：样本 (xinmathbb{R}^d) 看做随机向量

状态空间：(c) 个可能的状态 (类别)

[Omega =left{ omega_1,omega_2,dots ,omega_c ight} ]

决策空间：判定样本为某类或拒绝等

[mathcal{A} =left{ alpha_1,alpha_2,dots ,alpha_k ight} ]

一般 (kgeqslant c)，

[alpha_i=left{ xin omega_i ight} , i=1,dots ,c ]

(alpha_{c+1}=mathrm{reject}) 等

损失函数：实际为 (omega_j) 类判定为 (alpha_i) 的损失 (lambda left(alpha_i,omega_j ight)) →决策表

期望损失：

[egin{aligned} Rleft(alpha_i|x ight) &=mathbb{E} left[lambda left(alpha_i,omega_j ight)|x ight]\ &=sum_jlambda left(alpha_i,omega_j ight)Pleft(omega_j|x ight) end{aligned} ]

期望风险：

[Rleft(alpha ight)=int_{-infty}^{infty}{Rleft(alpha |x ight)p(x)}mathrm{d}x ]

最小风险决策：

[min Rleft(alpha ight)Rightarrow alpha =mathrm{argmin}_jRleft(alpha_j|x ight) ]

与最小错误率决策等价：0-1 决策表

[lambda left(alpha_i,omega_j ight)=1-delta_{ij} ]

则

[egin{aligned} Rleft(alpha_i|x ight) &=sum_jlambda left(alpha_i,omega_j ight)Pleft(omega_j|x ight)\ &=sum_{j e i}Pleft(omega_j|x ight)\ &=1-Pleft(omega_i|x ight) end{aligned} ]

因此

[egin{aligned} min Rleft(alpha ight) &Rightarrow min_jRleft(alpha_j|x ight)\ &Rightarrow alpha =mathrm{argmax}_jPleft(omega_j|x ight) end{aligned} ]

似然比：

[l(x)=frac{Pleft(x|omega_1 ight)}{Pleft(x|omega_2 ight)}>frac{Pleft(omega_2 ight)}{Pleft(omega_1 ight)}frac{lambda_{12}-lambda_{22}}{lambda_{21}-lambda_{11}}Rightarrow xin omega_1 ]

1.4 限定一类错误率条件下使另一类错误率最小

Neyman-Pearson 决策：优化问题

[min left{ P_1left(e ight)|P_2left(e ight)-epsilon_0=0 ight} ]

[egin{aligned} L &=P_1left(e ight)+lambda left(P_2left(e ight)-epsilon_0 ight)\ &=int_{mathcal{R}_2}{pleft(x|omega_1 ight)}mathrm{d}x+lambda left(int_{mathcal{R}_1}{pleft(x|omega_2 ight)}mathrm{d}x-epsilon_0 ight)\ &=1-lambda epsilon_o+int_{mathcal{R}_1}{left[lambda pleft(x|omega_2 ight)-pleft(x|omega_1 ight) ight]}mathrm{d}x end{aligned} ]

梯度条件：决策边界满足

[lambda =frac{pleft(x|omega_1 ight)}{pleft(x|omega_2 ight)},~P_2left(e ight)=epsilon_0 ]

决策规则：

[lambda pleft(x|omega_2 ight)-pleft(x|omega_1 ight)<0Rightarrow xin omega_1 ]

似然比：

[l(x)=frac{pleft(x|omega_1 ight)}{pleft(x|omega_2 ight)}>lambda Rightarrow xin omega_1 ]

对偶变量求解：通过 (l(x)) 的映射关系，可由 (p(x)) 求得 (pleft(l|omega_2 ight))，则由定义可知误差率为

[egin{aligned} P_2left(e ight) &=1-int_0^{lambda}{pleft(l|omega_2 ight)mathrm{d}l}\ &=epsilon_0Rightarrow lambda end{aligned} ]

1.5 朴素贝叶斯

随机向量分量独立：

[pleft(vec{x}|omega ight)=pleft(x_1,dots ,x_d|omega ight) riangleq prod_ipleft(x_i|omega ight) ]

1.6 判别函数与正态分布

判别函数：(g_i(x))，例如后验概率

[g_i(x)=Pleft(omega_i|x ight) ]

取分子

[g_i(x)=pleft(x|omega_i ight)Pleft(omega_i ight) ]

取对数

[g_i(x)=ln pleft(x|omega_i ight)+ln Pleft(omega_i ight) ]

决策面方程：(g_i(x)=g_j(x))

正态分布：

[p(x)=frac{1}{left(2pi ight)^{d/2}|Sigma |^{1/2}}exp left{ -frac{1}{2}left(x-mu ight)^{ op}Sigma ^{-1}left(x-mu ight) ight} ]

维数 (d)，均值 (mu =mathbb{E} left[x ight])，协方差

[Sigma =mathbb{E} left[left(x-mu ight)left(x-mu ight)^{ op} ight] ]

贝叶斯判别：各类分布

[pleft(x|omega_i ight)sim mathcal{N} left(mu_i,Sigma_i ight) ]

则判别函数为

[g_i(x)=-frac{d}{2}ln 2pi -frac{1}{2}ln |Sigma_i|+ln Pleft(omega_i ight)-frac{1}{2}left(x-mu_i ight)^{ op}Sigma_{i}^{-1}left(x-mu_i ight) ]

决策面方程：(g_i(x)=g_j(x))，即

[egin{aligned} &-0.5left[left(x-mu_i ight)^{ op}Sigma_{i}^{-1}left(x-mu_i ight)-left(x-mu_j ight)^{ op}Sigma_{j}^{-1}left(x-mu_j ight) ight]\ &+left[ln Pleft(omega_i ight)-ln Pleft(omega_j ight) ight] -0.5left(ln |Sigma_i|-ln |Sigma_j| ight)=0 end{aligned} ]

1.7 分类性能评价 ROC 与 AUC

ROC (Receiver Operating Characteristic)：FP-TP 曲线，越靠近曲线左上角的点对应的阈值参数性能越好

混淆矩阵：两类分类问题

	实际为正类	实际为负类
预测为正类	TP	FP
预测为负类	FN	TN

AUC (Area Under ROC Curves)：ROC 曲线下方面积越大越好

例：给定样本标签

[y = [1~0~1~1~1~0~0~0] ]

分类器输出结果为

[S = [0.5~0.3~0.6~0.22~0.4~0.51~0.2~0.33] ]

则 FP 与 TP 计算如下:

class	score	FP	TP
1	0.6	0	0.25
0	0.51	0.25	0.25
1	0.5	0.25	0.5
1	0.4	0.25	0.75
1	0.33	0.5	0.75
0	0.3	0.75	0.75
0	0.22	0.75	1
0	0.2	0.1	1

2 概率密度函数估计

统计量：样本的分布信息，如均值，方差等

参数空间：未知参数向量 ( heta) 全部可能取值的集合 (Theta)

点估计：构造估计量 (dleft(x_1,dots ,x_N ight)) 作为 ( heta) 的估计

区间估计：构造置信区间 (left(d_1,d_2 ight)) 作为 ( heta) 可能取值范围的估计

2.1 极大似然估计 (MLE, Maximum Likelihood Estimate)

假设：

1. 概率分布函数形式已知
2. 样本独立同分布采样得到

似然函数：

[egin{aligned} lleft( heta ight) &=pleft(X| heta ight)\ &=pleft(x_1,dots ,x_N| heta ight)\ &=prod_kpleft(x_k| heta ight) end{aligned} ]

对数似然函数：

[egin{aligned} Hleft( heta ight) &=ln lleft( heta ight)\ &=sum_kln pleft(x_k| heta ight) end{aligned} ]

极大似然估计：

[egin{aligned} heta &=mathrm{argmax}_{ heta in Theta}lleft( heta ight)\ &=mathrm{argmax}_{ heta in Theta}Hleft( heta ight) end{aligned} ]

正态分布：待估计参数为 ( heta =left[mu ,sigma ^2 ight]), 数据点

[X=left{ x_1,dots ,x_N ight} ]

估计量为 (hat{ heta}=left[hat{mu},hat{sigma}^2 ight])

概率密度函数为

[pleft(x_k| heta ight)=frac{1}{sqrt{2pi}sigma}exp left[-frac{left(x_k-mu ight)^2}{2sigma ^2} ight] ]

取对数得

[ln pleft(x_k| heta ight)=-frac{1}{2}ln left(2pi heta_2 ight)-frac{left(x_k- heta_1 ight)^2}{2 heta_2} ]

对 ( heta) 求梯度有

[ abla_{ heta}ln pleft(x_k| heta ight) =egin{bmatrix} dfrac{x_k- heta_1}{ heta_2}\ -dfrac{1}{2 heta_2}+dfrac{left(x_k- heta_1 ight)^2}{2 heta_{2}^{2}}\ end{bmatrix} ]

又

[sum_{k=1}^N{ abla_{ heta}ln pleft(x_k| heta ight)}=0 ]

因此，估计量为

[egin{aligned} hat{mu}&=frac{1}{N}sum_{k=1}^N{x_k} \ hat{sigma}^2&=frac{1}{N}sum_{k=1}^N{left(x_k-hat{mu} ight)^2} end{aligned} ]

多元正态分布：

[egin{aligned} hat{mu}&=frac{1}{N}sum_{k=1}^N{x_k}\ hat{Sigma}&=frac{1}{N}sum_{k=1}^N{left(x_k-hat{mu} ight)left(x_k-hat{mu} ight)^{ op}} end{aligned} ]

无偏估计：

[mathbb{E} left[hat{mu} ight] =mu ]

[mathbb{E} left[frac{N}{N-1}hat{Sigma} ight] =Sigma ]

渐进无偏估计：

[lim_{n ightarrow infty} mathbb{E} left[hat{Sigma} ight] =Sigma ]

可识别性：对 ( heta e heta '),

[exists~xRightarrow pleft(x| heta ight) e pleft(x| heta ' ight) ]

离散随机变量的混合密度函数往往不可识别，连续的则一般可以识别

2.2 贝叶斯估计

假设：参数 ( heta) 是随机变量，且已知其先验分布 (pleft( heta ight))

贝叶斯估计：后验概率

[pleft( heta |X ight)=pleft(X| heta ight)pleft( heta ight)/p(x) ]

贝叶斯学习：

[egin{aligned} pleft(x|X ight) &=int{pleft(x, heta |X ight)mathrm{d} heta}\ &=int{pleft(x| heta ight)pleft( heta |X ight)mathrm{d} heta} end{aligned} ]

贝叶斯学习性质：

[lim_{N ightarrow infty} pleft(x|X^N ight)=pleft(x|hat{ heta}= heta ight)=p(x) ]

正态分布：

[pleft(X|mu ight)sim mathcal{N} left(mu ,sigma ^2 ight) ]

[pleft(mu ight)sim mathcal{N} left(mu_o,sigma_{0}^{2} ight) ]

其中 (sigma ^2) 已知，则有

[egin{aligned} pleft(mu |X ight) &=frac{pleft(X|mu ight)pleft(mu ight)}{p(x)}\ &=alpha prod_kpleft(x_k|mu ight)pleft(mu ight)\ &=alpha 'cdot exp left{ -frac{1}{2}left[sum_{k=1}^N{frac{left(mu -x_k ight)^2}{sigma ^2}}+frac{left(mu -mu_0 ight)^2}{sigma_{0}^{2}} ight] ight} \ & riangleq frac{1}{sqrt{2pi}sigma_N}exp left[-frac{left(mu -mu_N ight)^2}{2sigma_{N}^{2}} ight] end{aligned} ]

其中

[sigma_{N}^{2}=frac{sigma_{0}^{2}sigma ^2}{Nsigma_{0}^{2}+sigma ^2} ]

[mu_N=frac{Nsigma_{0}^{2}}{Nsigma_{0}^{2}+sigma ^2}m_N+frac{sigma ^2}{Nsigma_{0}^{2}+sigma ^2}mu_0 ]

其中

[m_N=frac{1}{N}sum_{k=1}^N{x_k} ]

因此

[egin{aligned} pleft(x|X ight) &=int{pleft(x|mu ight)pleft(mu |X ight)mathrm{d}mu}\ &sim mathcal{N} left(mu_N,sigma ^2+sigma_{N}^{2} ight) end{aligned} ]

参数变化：

[sigma_0=0Rightarrow mu_N=mu_0 ]

[Nuparrow Rightarrow mu_N ightarrow m_N,~sigma_{N}^{2} ightarrow 0 ]

最大似然估计与贝叶斯估计对比：

1. 训练样本无穷多时，最大似然估计与贝叶斯估计结果相同
2. 贝叶斯估计使用先验概率利用了更多信息，若信息可靠则贝叶斯估计更准确，但有时先验概率很难设计，无信息先验
3. 最大似然估计计算简单，贝叶斯通常计算复杂的积分
4. 最大似然估计易于理解，给出的是参数的最佳估计结果

2.3 非参数估计

假设：

1. 概率分布函数形式未知
2. 样本独立同分布

直方图估计：

[hat{p}_N(x) =frac{k_N}{NV_N} ightarrow p(x) ]

估计收敛条件：

[V_N ightarrow 0,~k_N ightarrow infty ,~k_N/N ightarrow 0 ]

2.4 Parzen 窗估计 (Kernel Density Estimation)

思想：固定小舱体积，滑动小舱估计每个点的概率密度

区域：(R_N) 是 (d) 维超立方体，棱长 (h_N)，体积 (V_N=h_{N}^{d})

窗函数条件：(displaystylephi left(u ight)geqslant 0,~int{phi left(u ight)mathrm{d}u}=1)

1. 方窗：

[phi left(u ight)= egin{cases} 1, &mathrm{if}~left| u ight|_{infty}leqslant 1/2\ 0, &mathrm{otherwise} end{cases} ]

2. 正态窗：

[phi left(u ight)=frac{1}{sqrt{2pi}}exp left(-frac{1}{2}u^2 ight),~uinmathbb{R} ]

3. 指数窗：

[phi left(u ight)=frac{1}{2}exp left(-|u| ight),~uinmathbb{R} ]

落入以 (x) 为中心的区域的样本数：

[k_N=sum_{i=1}^N{phi left(frac{x-x_i}{h_N} ight)} ]

概率密度函数估计：

[hat{p}_N(x)=frac{1}{N}sum_{i=1}^N{frac{1}{V_N}phi left(frac{x-x_i}{h_N} ight)} ]

窗宽选取：(h_N=h_1/sqrt{N})，其中 (h_1) 可调且一般存在最优值

估计量性质：一维正态窗

[egin{aligned} ar{p}_N &=mathbb{E} left[hat{p}_N(x) ight] \ &sim mathcal{N} left(mu ,sigma ^2+h_{N}^{2} ight) end{aligned} ]

2.5 (k_N) 近邻估计

思想：固定小舱内数据点个数，滑动可变大小的小舱对每个采样点 (而不是数据点) 进行概率密度估计

数据点个数：(k_N=k_1sqrt{N})，其中 (k_1) 可调且一般存在最优值

2.6 估计准确性、维数问题与过拟合

估计准确性：

1. 贝叶斯误差：不同的类条件概率分布函数之间的相互重叠
2. 模型误差：选择了错误的概率密度函数模型
3. 估计误差：采用有限样本进行估计所带来的误差

维数问题：维数为 (d)，需要样本 (100^d) →维数灾难

过拟合避免方法：

1. 贝叶斯方法
2. 增加样本数
3. 正则化
4. 减少模型参数

3 EM 算法与高斯混合模型 GMM

3.1 EM 算法

思想：用隐变量对缺失数据建模，迭代实现最大似然估计

数据：(X=left{ x_1,dots ,x_N ight})，隐变量 (Y)，完整数据 (Z=left(X,Y ight))

似然函数：

[egin{aligned} lleft( heta ight) &=pleft(X| heta ight)\ &=sum_{yin Y}pleft(X,y| heta ight) end{aligned} ]

对数似然函数：

[egin{aligned} Lleft( heta ight) &=ln lleft( heta ight)\ &=ln sum_{yin Y}pleft(X,y| heta ight) end{aligned} ]

对数似然函数的下界：应用 Jensen 不等式于对数函数可得

[egin{aligned} Lleft( heta ight) &=ln sum_ypleft(X,y| heta ight)\ &=ln sum_yfrac{q(y)pleft(X,y| heta ight)}{q(y)}\ &geqslant sum_yq(y)lnfrac{pleft(X,y| heta ight)}{q(y)} \ &=sum_yq(y)ln pleft(X,y| heta ight)-sum_yq(y)ln q(y)\ & riangleq Fleft(q, heta ight) end{aligned} ]

迭代优化下界：初始化 (q_{left[0 ight]},~ heta_{left[0 ight]}) 后反复迭代

[egin{aligned} q_{left[k+1 ight]}&gets mathrm{argmax}_qFleft(q, heta_{left[k ight]} ight)\ heta_{left[k+1 ight]}&gets mathrm{argmax}_{ heta}Fleft(q_{left[k+1 ight]}, heta ight) end{aligned} ]

期望：当 (q=pleft(y|X, heta_{left[k ight]} ight)) 为后验概率时，(Fleft(q, heta_{left[k ight]} ight)) 达到最大

[egin{aligned} Fleft(q, heta ight) &=sum_yq(y)lnfrac{pleft(X,y| heta ight)}{q(y)}\ &=sum_ypleft(y|X, heta ight)lnfrac{pleft(y|X, heta ight)pleft(X| heta ight)}{pleft(y|X, heta ight)} \ &=sum_ypleft(y|X, heta ight)ln pleft(X| heta ight)\ &=ln pleft(X| heta ight)\ &=Lleft( heta ight) end{aligned} ]

[egin{aligned} Fleft(q_{left[k+1 ight]}, heta ight)=sum_yq_{left[k+1 ight]}(y)ln pleft(X,y| heta ight)-sum_yq_{left[k+1 ight]}(y)ln q_{left[k+1 ight]}(y) end{aligned} ]

第二项不包含优化变量 ( heta) 可忽略，代入 (q_{left[k+1 ight]}(y)) 并定义

[egin{aligned} Qleft( heta_{left[k ight]}, heta ight)& riangleq sum_ypleft(y|X, heta_{left[k ight]} ight)ln pleft(X,y| heta ight)\ &=mathbb{E} left[ln pleft(X,y| heta ight)|X, heta_{left[ k ight]} ight] end{aligned} ]

最大化：

[ heta_{left[k+1 ight]}gets mathrm{argmax}_{ heta}Qleft( heta_{left[k ight]}, heta ight) ]

广义最大化：

[ heta_{left[k+1 ight]}in left{ heta_{left[k+1 ight]}|Qleft( heta_{left[k ight]}, heta_{left[k+1 ight]} ight)>Qleft( heta_{left[k ight]}, heta_{left[k ight]} ight) ight} ]

3.2 高斯混合模型 GMM

隐变量：(Y=left{ yin mathbb{R} ^N ight}) 表示样本 (x_i) 由第 (y_i) 个高斯分布产生

混合模型：

[pleft(X|Theta ight)=Sigma_jalpha_jp_jleft(X| heta_j ight) ]

其中

[Theta =left{ alpha_j, heta_j ight},~sum_jalpha_j=1 ]

由独立同分布可得

[egin{aligned} pleft(X|Theta ight) &=prod_ipleft(x_i|Theta ight)\ &=prod_isum_jalpha_jp_jleft(x_i| heta_j ight) end{aligned} ]

对数似然函数：

[ln pleft(X|Theta ight)=sum_iln sum_jalpha_jp_jleft(x_i| heta_j ight) ]

极大似然估计：

[ abla_{Theta}ln pleft(X|Theta ight)=0Rightarrow Theta ]

结果与EM相同

EM 算法：

[pleft(X,y|Theta ight)=prod_ipleft(x_i|y_i ight)pleft(y_i ight) ]

[egin{aligned} ln pleft(X,y|Theta ight) &=sum_iln pleft(x_i|y_i ight)pleft(y_i ight)\ &=sum_iln alpha_{y_i}p_{y_i}left(x_i| heta_{y_i} ight) end{aligned} ]

[egin{aligned} pleft(y|X,Theta ^g ight) &=prod_ipleft(y_i|x_i,Theta ^g ight)\ &=prod_ialpha_{y_i}^{g}frac{p_{y_i}left(x_i| heta_{y_i}^{g} ight)}{pleft(x_i|Theta ^g ight)} end{aligned} ]

[egin{aligned} Qleft(Theta ^g,Theta ight) &=sum_ypleft(y|X,Theta ^g ight)ln pleft(X,y|Theta ight)\ &=sum_jsum_iln left(alpha_jp_jleft(x_i| heta_j ight) ight)pleft(j|x_i,Theta ^g ight)\ &=sum_jsum_ipleft(j|x_i,Theta ^g ight)left[ln alpha_j+ln p_jleft(x_i| heta_j ight) ight] end{aligned} ]

(alpha_j) 与 ( heta_j) 解耦可分别优化，由 (sum_ialpha_i=1) 及梯度条件解得

[egin{aligned} alpha_{j}^{mathrm{new}}&=frac{1}{N}sum_ipleft(j|x_i,Theta ^g ight)\ mu_{j}^{mathrm{new}}&=frac{1}{Nalpha_{j}^{mathrm{new}}}sum_ix_ipleft(j|x_i,Theta ^g ight)\ Sigma_{j}^{mathrm{new}}&=frac{1}{Nalpha_{j}^{mathrm{new}}}sum_ipleft(j|x_i,Theta ^g ight)left(x_i-mu_{j}^{mathrm{new}} ight)left(x_i-mu_{j}^{mathrm{new}} ight)^{ op} end{aligned} ]

若限制各成分的协方差矩阵均相同，则 M 步需要修改为

[Sigma ^{mathrm{new}}=sum_{j}sum_ifrac{pleft(j|x_i,Theta ^g ight)left(x_i-mu_{j}^{mathrm{new}} ight)left(x_i-mu_{j}^{mathrm{new}} ight)^{ op}}{Nsum_jalpha_{j}^{mathrm{new}}} ]

例题：三维数据点，偶数点的第3维数据缺失，令 (x_{i3},~iin E) 为隐变量，

[x_i=left[x_{i1},x_{i2},x_{i3} ight] ^{ op} ]

则对数似然函数为

[egin{aligned} Lleft( heta ight) &=sum_{iin O}ln pleft(x_{i1},x_{i2},x_{i3}| heta ight)+sum_{iin E}ln pleft(x_{i1},x_{i2}| heta ight)\ &=sim +sum_{iin E}ln int_{-infty}^{+infty}pleft(x_{i1},x_{i2},x_{i3}| heta ight)mathrm{d}x_{i3}\ &=sim +sum_{iin E}ln int_{-infty}^{+infty}frac{qleft(x_{i3} ight)pleft(x_{i1},x_{i2},x_{i3}| heta ight)}{qleft(x_{i3} ight)}mathrm{d}x_{i3}\ &geqslant sim +sum_{iin E}int_{-infty}^{+infty}qleft(x_{i3} ight)lnfrac{pleft(x_{i1},x_{i2},x_{i3}| heta ight)}{qleft(x_{i3} ight)} mathrm{d}x_{i3} end{aligned} ]

[Qleft( heta_{left[k ight]}, heta ight)=sim +sum_{iin E}int_{-infty}^{+infty}pleft(x_{i3}|x_{i1},x_{i2}, heta_{left[k ight]} ight)ln pleft(vec{x}_i| heta ight)mathrm{d}x_{i3} ]

4 线性判别函数

思想：

1. 不恢复类条件概率密度，利用样本直接设计分类器
2. 线性判别函数形式简单易分析，但往往不是最优分类器

线性判别函数：(g(x)=w^{ op}x+w_0)

两类问题：(g(x)=g_1(x)-g_2(x))，分类决策为

[egin{cases} xin omega_1, &mathrm{if}~g(x)>0\ xin omega_2, &mathrm{if}~g(x)<0\ mathrm{either}~mathrm{or}~mathrm{reject}, &mathrm{otherwise} end{cases} ]

点到直线距离：

[r=frac{g(x)}{left| w ight|} ]

广义线性判别：

[g(x)=w^{ op}x+w_0 riangleq a^{ op}y ]

其中增广样本向量为

[y=egin{bmatrix} 1\ x end{bmatrix} ]

增广权向量为

[a=egin{bmatrix} w_0\ w end{bmatrix} ]

样本规范化：

[y_{i}'= egin{cases} y_i, & mathrm{if}~y_iin omega_1\ -y_i, & mathrm{if}~y_iin omega_2 end{cases} ]

解区：解向量集合 (left{ a|a^{ op}y_{i}'>0,~forall~i ight})

解区限制：(a^{ op}y_igeqslant b>0,~forall~i)

感知准则函数：

[min J_pleft(a ight)=sum_{yin Y^k}left(-a^{ op}y ight) ]

最小化错分样本 (yin Y^k) 到分界面距离之和，梯度为

[ abla J_pleft(a ight)=sum_{yin Y^k}left(-y ight) ]

迭代公式为

[aleft(k+1 ight)=aleft(k ight)+ ho_ksum_{yin Y^k}y ]

直到 (a) 不变

单样本感知器算法：循环处理每个样本，若 (a^{ op}y^kleqslant gamma)，其中 (gamma geqslant 0)，则

[aleft(k+1 ight)=aleft(k ight)+y^k ]

直到所有样本满足条件

多类问题：

1. (c-1) 个非己：(omega_1) 与非 (omega_1)，(omega_2) 与非 (omega_2)，双非为 (omega_3)
2. (cleft(c-1 ight)/2) 个两类：(omega_1-omega_2), (omega_1-omega_3), (omega_2-omega_3) 三条线
3. 直接设计判别函数：

[mathcal{R}_i=left{ x|g_i(x)>g_j(x),~forall~j e i ight} ]

5 支持向量机SVM

判别式模型：直接利用样本计算判别函数

5.1 线性可分情形

样本集合：

[T=left{ left(x_i,y_i ight) ight}_{i=1}^{N} ]

其中

[y_i= egin{cases} 1, &mathrm{if}~x_iin omega_1\ -1, &mathrm{if}~x_iin omega_2\ end{cases} ]

线性判别函数：

[y_ileft(w^{ op}x_i+b ight)geqslant 1,~forall~i ]

margin

[ ho=frac{2}{|w|} ]

优化问题：

[min left{frac{1}{2}w^{ op}w|y_ileft(w^{ op}x_i+b ight)geqslant 1, i=1,dots ,N ight} ]

Lagrange 函数为

[Lleft(w,b,alpha ight)=frac{1}{2}w^{ op}w-sum_{i=1}^{N}alpha_ileft[y_ileft(w^{ op}x_i+b ight)-1 ight] ]

梯度条件：

[w=sum_{i=1}^{N}alpha_iy_ix_i,~sum_{i=1}^{N}alpha_iy_i=0 ]

对偶函数：

[Qleft(alpha ight)=sum_{i=1}^{N}alpha_i-frac{1}{2}sum_{i=1}^{N}sum_{j=1}^{N}alpha_ialpha_jy_iy_jx_{i}^{ op}x_j ]

对偶问题：

[max left{ Qleft(alpha ight)|sum_{i=1}^{N}alpha_iy_i=0,~alpha geqslant 0 ight} ]

支持向量：互补松弛

[alpha_{i}^{*}left[y_ileft(left< w^*,x_i ight> +b ight)-1 ight] =0,~alpha_{i}^{*} e 0 ]

支持向量机：

[f(x)=mathrm{sgn} left(sum_ialpha_{i}^{*}y_ix_{i}^{ op}x+b^* ight)in left{ -1,+1 ight} ]

5.2 线性不可分情形

Soft margin：(y_ileft(w^{ op}x_i+b ight)geqslant 1-xi_i,~forall~i)

松弛变量：

[egin{cases} 0leqslant xi_ileqslant 1, &mathrm{if}~mathrm{violated}\ xi_i>1, &mathrm{if}~mathrm{misclassified} end{cases} ]

优化问题：错分率上界 (sum_ixi_i)，tradeoff (C)

[egin{aligned} min~~&frac{1}{2}w^{ op}w+Csum_ixi_i\ mathrm{s.t.}~~& y_ileft(w^{ op}x_i+b ight)geqslant 1-xi_i,~forall~i\ &xi_igeqslant 0,~forall~i end{aligned} ]

无约束形式：

[min~frac{1}{2}w^{ op}w+Csum_iLleft(w,b;x_i,y_i ight) ]

其中 Hinge 损失函数为

[Lleft(w,b;x_i,y_i ight)=max left{ 1-y_ileft(w^{ op}x_i+b ight),0 ight} ]

对偶问题：

[max left{ Qleft(alpha ight)|sum_{i=1}^{N}alpha_iy_i=0,~0leqslant alpha leqslant C ight} ]

5.3 非线性情形 Kernel SVM

广义线性可分：低维空间 (L) 升到高维空间 (H) 使样本线性可分

升维原因：输入空间 (L) 一般不是正常的特征空间

核函数：

[Kleft(x_i,x_j ight)=left< Phi left(x_i ight),Phi left(x_j ight) ight> ]

其中 (Phi :L ightarrow H)

多项式核函数：

[Kleft(x,y ight)=left(gamma left< x,y ight> +r ight)^p, gamma >0 ]

径向基 RBF 核函数：

[Kleft(x,y ight)=exp left(-frac{left| x-y ight| ^2}{2sigma ^2} ight) ]

Sigmiod 核函数：

[Kleft(x,y ight)= anh left(kappa left< x,y ight> -delta ight) ]

对偶函数：

[Qleft(alpha ight)=sum_{i=1}^{N}alpha_i-frac{1}{2}sum_{i=1}^{N}sum_{j=1}^{N}alpha_ialpha_jy_iy_jKleft(x_i,x_j ight) ]

对偶问题：

[max left{ Qleft(alpha ight)|sum_{i=1}^{N}alpha_iy_i=0,~0leqslant alpha leqslant C ight} ]

非线性支持向量机：

[f(x)=mathrm{sgn} left(sum_ialpha_{i}^{*}y_iKleft(x_i,x ight)+b^* ight) ]

5.4 SVM 几点改进

可微损失函数：

[Lleft(w,b;x_i,y_i ight)=left(max left{ 1-y_ileft(w^{ op}x_i+b ight),0 ight} ight)^2 ]

L1 正则化：稀疏性

[min left| w ight|_1+Csum_iLleft(w,b;x_i,y_i ight) ]

多核学习：

[Kleft(x,y ight)=sum_{i=1}^{m}eta_iK_ileft(x,y ight) ]

其中

[eta_igeqslant 0,~sum_ieta_i=1 ]

6 近邻法与距离度量

6.1 最近邻法 (Nearest Neighbor)

思想：测试样本与距离它最近的样本属于同类

数据：(c) 类 (left{ omega_1,dots ,omega_c ight})，每类 (N_i) 个样本

[left{ x_{i}^{left(1 ight)},x_{i}^{left(2 ight)},dots ,x_{i}^{left(N_i ight)} ight} ]

判别函数：

[g_i(x)=min_kleft| x-x_{i}^{left(k ight)} ight| , k=1,2,dots ,N_i ]

决策规则：

[g_j(x)=min_ig_i(x)Rightarrow xin omega_j ]

Voronoi 区域：L2 范数为凸，L1 范数非凸

证明：由余弦定理

[a^{ op}b=frac{left| a ight| ^2+left| b ight| ^2-left| a-b ight| ^2}{2} ]

可知对 (xi_1,xi_2in V_i)，

[xi =lambda xi_1+left(1-lambda ight)xi_2,~lambda in left[0,1 ight] ]

有

[egin{aligned} left| xi -x_i ight| ^2 &=lambda left| xi_1-x_i ight| ^2-lambda left(1-lambda ight)left| xi_1-xi_2 ight| ^2 +left(1-lambda ight)left| xi_2-x_i ight| ^2\ &leqslant left| xi -x_j ight| ^2,~forall~j e i end{aligned} ]

平均错误率：

[P_Nleft(e ight)=iint{P_Nleft(e|x,x' ight)pleft(x'|x ight)mathrm{d}x'p(x)mathrm{d}x} ]

渐进平均错误率：

[P=lim_{N ightarrow infty} P_Nleft(e ight) ]

记 Bayes 错误率为 (P^*), 则渐进平均错误率的范围

[P^*leqslant Pleqslant P^*left(2-frac{c}{c-1}P^* ight) ]

6.2 (k)-近邻法 ((k) Nearest Neighbors)

思想：测试样本与距离它最近的 (k) 个样本中占优的类同类

算法：最近邻法寻找 (k) 个近邻，(k_i) 表示属于 (omega_i) 的样本数，判别函数 (g_i(x)=k_i)，决策规则

[g_j(x)=max_ik_iRightarrow xin omega_j ]

6.3 近邻法快速算法

思想：样本集分级分解成多个子集 (树状结构) ，每个子集 (结点) 可用较少几个量代表，通过将新样本与各结点比较排除大量候选样本，只与最终结点 (子集) 中逐个样本比较

6.4 压缩近邻法 (Condensing)

算法：关注两类边界附近的样本，初始 Grabbag 为全部样本

1. 从 Grabbag 中选择一个样本放入 Store 中
2. 用 Store 中样本以近邻法测试 Grabbag 中样本，若分错则将该样本放入 Store
3. 重复 2) 直到 Grabbag 中没有样本再转到 Store 中，或 Grabbag 为空则停止
4. 用 Store 中样本作为近邻法设计集

6.5 距离度量

距离定义：二元函数 (Dleft(cdot ,cdot ight))

1. 自反性：(Dleft(x,y ight)=0Leftrightarrow x=y)
2. 对称性：(Dleft(x,y ight)=Dleft(y,x ight))
3. 三角不等式：(Dleft(x,y ight)+Dleft(y,z ight)geqslant Dleft(x,z ight))

注释：非负性 (Dleft(x,y ight)geqslant 0) 可由定义三条性质导出

Minkowski 距离度量：

[Dleft(x,y ight)=left(sum_{j=1}^{d}|x_j-y_j|^s ight)^{1/s},~sgeqslant 1 ]

欧氏距离：

[Dleft(x,y ight)=left| x-y ight|_2=sqrt{left(x-y ight)^{ op}left(x-y ight)} ]

Chebychev 距离：

[Dleft(x,y ight)=left| x-y ight|_{infty}=max_j|x_j-y_j| ]

马氏距离：可以表示样本距离对样本分布 (主要是方差) 的依赖性

[Dleft(x,y ight)=left(x-y ight)^{ op}Sigma ^{-1}left(x-y ight),~Sigma =AA^{ op} ]

且变换后等价于欧氏距离平方：

[A^{-1}:xmapsto x'Rightarrow Dleft(x,y ight)=left| x'-y' ight|_{2}^{2} ]

概率分布相似性判据：基于类条件概率密度函数

1. Bhattacharyya 距离：

[J_B=-ln int left[pleft(x|omega_1 ight)pleft(x|omega_2 ight) ight] ^{1/2}mathrm{d}x ]

2. Chernoff 界限：

[J_C=-ln int p^sleft(x|omega_1 ight)p^{1-s}left(x|omega_2 ight)mathrm{d}x ]

3. 散度：

[J_D=int left[pleft(x|omega_1 ight)-pleft(x|omega_2 ight) ight] lnfrac{pleft(x|omega_1 ight)}{pleft(x|omega_2 ight)} mathrm{d}x ]

散度定义来源：

[Dleft(f_1,f_2 ight)=int f_1(x)lnfrac{f_1(x)}{f_2(x)} mathrm{d}x ]

[J_D=Dleft(f_1,f_2 ight)+Dleft(f_2,f_1 ight) ]

切距离：记 (y) 所处流形的切空间基矩阵为 (T), 则切距离为

[Dleft(x,y ight)=min_aleft| left(y+aT ight)-x ight| ]

Holder 不等式：

[sum_{k=1}^{n}a_kb_kleqslant left| a ight|_pleft| b ight|_q,~frac{1}{p}+frac{1}{q}=1 ]

Minkowski 不等式：

[left| a+b ight|_pleqslant left| a ight|_p+left| b ight|_p,~pgeqslant 1 ]

7 特征提取与选择

模式识别系统构成：

1. 数据获取→特征提取与选择→分类器设计
2. 数据获取→特征提取与选择→测试

7.1 Fisher 线性判别

思想：把 (d) 维空间的样本投影到分开得最好的一条直线上

样本：

[X=left{ x_1,dots ,x_N ight} =X_1+X_2 ]

其中

[|X_1|=N_1,~|X_2|=N_2 ]

降维：(y_n=w^{ op}x_n)，寻找最好的投影方向即寻找 (w)

样本均值：

[m_i=frac{1}{N_i}sum_{xin X_i}x ]

类内离散度矩阵：

[S_i=sum_{xin X_i}left(x-m_i ight)left(x-m_i ight)^{ op} ]

总类内 (within-class) 离散度：(S_w=sum_iS_i)，一般可逆

类间 (between-class) 离散度：

[S_b=left(m_1-m_2 ight)left(m_1-m_2 ight)^{ op} ]

一维投影空间：样本均值

[ ilde{m}_i=frac{1}{N_i}sum_{yin Y_i}y ]

类内离散度

[ ilde{S}_{i}^{2}=sum_{yin Y_i}left(y- ilde{m}_i ight)^2 ]

总类内离散度

[ ilde{S}_w= ilde{S}_{1}^{2}+ ilde{S}_{2}^{2} ]

Fisher 准则函数：

[J_Fleft(w ight)=frac{left( ilde{m}_1- ilde{m}_2 ight)^2}{ ilde{S}_{1}^{2}+ ilde{S}_{2}^{2}} ]

优化问题：广义 Rayleigh 商

[max~J_Fleft(w ight)=frac{w^{ op}S_bw}{w^{ op}S_ww} ]

令分母为非零常数 (w^{ op}S_ww=c e 0)，可定义 Lagrange 函数

[Lleft(w,lambda ight)=w^{ op}S_bw-lambda left(w^{ op}S_ww-c ight) ]

由梯度条件可得

[S_bw^*=lambda S_ww^* ]

即

[egin{aligned} lambda w^* &=S_{w}^{-1}S_bw^*\ &=S_{w}^{-1}left(m_1-m_2 ight)R end{aligned} ]

其中

[R=left(m_1-m_2 ight)^{ op}w ]

忽略比例因子 (R/lambda) 有

[w^*=S_{w}^{-1}left(m_1-m_2 ight) ]

一维分类：估计类条件概率密度函数，采用 Bayes 决策，或取决策边界

[egin{aligned} y_{0}^{left(1 ight)}&=frac{ ilde{m}_1+ ilde{m}_2}{2}\ y_{0}^{left(2 ight)}&=frac{N_2 ilde{m}_1+N_1 ilde{m}_2}{N} end{aligned} ]

注释：Fisher 适合正态分布数据，若投影到平面则可把两类切割开组成多类，(S_w) 不可逆则数据有冗余，降维到可逆

多类 Fisher 线性判别：(K) 类则最多可选取 (K-1) 个特征

7.2 类别可分性判据

基于类内类间距离：

[egin{aligned} J_2&=mathrm{Tr}left(S_{w}^{-1}S_b ight)\ J_3&=lnfrac{|S_b|}{|S_w|}\ J_4&=frac{mathrm{Tr}left(S_b ight)}{mathrm{Tr}left(S_w ight)}\ J_5&=frac{|S_w+S_b|}{|S_w|}\ end{aligned} ]

基于概率分布：(J_B,~J_C,~J_D)

基于熵函数：

[J_{c}^{alpha}=left(2^{1-alpha}-1 ight)^{-1}left[sum_{i=1}^{c}P^{alpha}left(omega_i|x ight)-1 ight] ]

其中参数 (alpha ightarrow 1)：Shannon 熵，(alpha =2)：平方熵

7.3 特征提取

降维：(xin mathbb{R} ^Dmapsto yin mathbb{R} ^d)，

[y=W^{ op}x,~Win mathbb{R} ^{D imes d} ]

优化问题：(S_{w}^{-1}S_b) 前 (d) 个特征值对应的特征向量组成 (W)

7.4 特征选择

问题：单独最好的 (d) 个特征组合起来不一定是最好的

最优搜索算法：穷举法，分枝定界法

次优搜索算法：单独最优特征组合

1. 单独最优特征组合：

[J(x)=sum_iJleft(x_i ight)~mathrm{or}~ prod_iJleft(x_i ight) ]

2. 顺序前进法：单独最好+合作最好+合作最好
3. 顺序后退法：全部-合作最不好-合作次不好
4. 增 (l) 减 (r) 法：增加合作最好的，删除合作最不好的
5. 智能算法：模拟退火，遗传算法，Tabu 搜索

Relief 算法：

输入：训练集 (X=left{ x_iin mathbb{R} ^d ight}_{i=1}^{N})

随机选择样本数 (n)

设定 (d) 维权重向量

[w=[w_1,w_2,…,w_D]^{ op}=0 ]

for (i=1) to (n)：

从 (X) 中随机选择一个样本 (x)

计算 (X) 中离 (x) 最近的同类样本 (h)，不同类的样本 (m)

for (j=1) to (d)：

[w_j=w_j-frac{mathrm{diff}(j,x,h)}{n}+frac{mathrm{diff}(j,x,m)}{n} ]

return (w)

输出：权重 (w) 最大的前 (k) 个特征

差异计算：(mathrm{diff(}j,x,h)) 表示 (x) 与 (h) 在第 (j) 维上绝对值的差异

1. 离散变量：

[mathrm{diff}(j,x,h)=1-left[x_j=h_j ight] ]

2. 连续变量：

[mathrm{diff}(j,x,h)=frac{|x_j-h_j|}{x_{jmax}-x_{jmin}} ]

8 深度学习

8.1 Multi-Layer Perception, MLP

Perceptron：单个神经元→感知器

(x=left[x_1,dots ,x_p ight] ^{ op}, w=left[w_1,dots ,w_p ight] ^{ op})

神经元输入 (v=w^{ op}x- heta)

[y=mathrm{sgn}(v)= egin{cases} +1, &mathrm{if}~vgeqslant 0\ -1, &mathrm{if}~v< 0\ end{cases} ]

激活函数：

1. 符号函数：

[phi(x)=mathrm{sgn}(x) ]

2. Sigmoid：

[phi(x)=frac{1}{1+exp(-x)} ]

3. 分段线性函数
4. ReLU：

[phi (x)= egin{cases} x, &mathrm{if}~xgeqslant0\ 0, &mathrm{if}~x<0\ end{cases} ]

5. Leaky ReLU：

[phi (x)= egin{cases} x, &mathrm{if}~xgeqslant 0\ ax, &mathrm{if}~x<0\ end{cases} ]

6. Softmax：

[phi(x)=frac{exp(x)}{1^{ op}exp(x)} ]

7. 双曲正切：

[phi (x)= anh (x)=frac{mathrm{e}^x-mathrm{e}^{-x}}{mathrm{e}^x+mathrm{e}^{-x}} ]

Multi-Layer Perceptron：多层感知机网络

逼近能力：(forall fin C^{left[0,1 ight] ^p}, epsilon >0, exists~M,alpha , heta ,w)

[F(x)=sum_{i=1}^{M}alpha_iphi left(sum_{j=1}^{p}w_{ij}x_j- heta_i ight) ]

使得

[|F(x)-f(x)|<epsilon ]

标签：one-hot vector

[y=left[0,dots ,0,1,0,dots ,0 ight] ]

交叉熵损失：(L=-y^{ op}ln hat{y})，(hat{y}) 为网络输出判别结果

均方误差损失：样本集 (X=left{ x_n ight}_{n=1}^{N})，标签为 (left{ dleft(n ight) ight})

输出端第 (j) 个单元对第 (n) 个样本的输出：(y_jleft(n ight))

第 (j) 个单元的误差信号：

[e_jleft(n ight)=d_jleft(n ight)-y_jleft(n ight) ]

输出端对第 (n) 个样本的平方误差：

[Eleft(n ight)=frac{1}{2}sum_{j=1}^{c}e_{j}^{2}left(n ight) ]

全部 (N) 个样本的平方误差均值：

[E_{mathrm{av}}=frac{1}{N}sum_{n=1}^{N}Eleft(n ight) ]

逐个样本学习的 BP 算法：

1. 误差对输出单元 (j) 的权重 (left{ w_{ji},~forall~i ight}) 求梯度

由

[v_jleft(n ight)=sum_{i=0}^{p}w_{ji}left(n ight)y_ileft(n ight) ]

[y_jleft(n ight)=phi_jleft(v_jleft(n ight) ight) ]

可得

[egin{aligned} frac{partial Eleft(n ight)}{partial w_{ji}left(n ight)} &=frac{partial Eleft(n ight)}{partial e_jleft(n ight)}frac{partial e_jleft(n ight)}{partial y_jleft(n ight)}frac{partial y_jleft(n ight)}{partial v_jleft(n ight)}frac{partial v_jleft(n ight)}{partial w_{ji}left(n ight)}\ &=-e_jleft(n ight)phi_{j}^{'}left(v_jleft(n ight) ight)y_ileft(n ight)\ & riangleq delta_jleft(n ight)y_ileft(n ight) end{aligned} ]

权重修正：

[w_{ji}=w_{ji}+eta delta_jleft(n ight)y_ileft(n ight) ]

其中 (delta_jleft(n ight)) 称为局部梯度

2. 误差对内部隐单元 (j) 的权重 (left{ w_{ji},~forall~i ight}) 求梯度

局部梯度为

[egin{aligned} delta_jleft(n ight) &=-frac{partial Eleft(n ight)}{partial y_jleft(n ight)}frac{partial y_jleft(n ight)}{partial v_jleft(n ight)}\ &=-frac{partial Eleft(n ight)}{partial y_jleft(n ight)}phi_{j}^{'}left(v_jleft(n ight) ight) end{aligned} ]

其中

[egin{aligned} frac{partial Eleft(n ight)}{partial y_jleft(n ight)} &=sum_k{frac{partial Eleft(n ight)}{partial e_kleft(n ight)}frac{partial e_kleft(n ight)}{partial y_kleft(n ight)}frac{partial y_kleft(n ight)}{partial v_kleft(n ight)}frac{partial v_kleft(n ight)}{partial y_jleft(n ight)}}\ &=-sum_ke_kphi 'left(v_kleft(n ight) ight)w_{kj}left(n ight)\ &=-sum_kdelta_kleft(n ight)w_{kj}left(n ight) end{aligned} ]

因此

[delta_jleft(n ight)=phi_{j}^{'}left(v_jleft(n ight) ight)sum_kdelta_kleft(n ight)w_{kj}left(n ight) ]

权重修正：

[w_{ji}=w_{ji}+eta delta_jleft(n ight)y_ileft(n ight) ]

BP 问题：局部极值且收敛缓慢，需大量数据已知网络结构

深度问题：更深的深度可以具有更好的表示性但优化更困难

例题：(k) 类，输入 (xin mathbb{R} ^d)，one-hot 标签 (yin mathbb{R} ^k)，交叉熵损失网络为

[egin{aligned} hat{y}&=fleft(x;W_1,b_1,W_2,b_2 ight)\ h_1&=W_{1}^{ op}x+b_1 \ a_1&=mathrm{ReLU}left(h_1 ight)\ h_2&=egin{bmatrix} a_1\ x end{bmatrix} \ a_2&=h_2odot m \ h_3&=W_{2}^{ op}a_2+b_2 \ hat{y}&=mathrm{Softmax}left(h_3 ight) end{aligned} ]

则损失函数对各个变量的梯度为

[egin{aligned} ar{hat{y}}&=-yhat{y} \ ar{h}_3&=hat{y}-y \ ar{W}_2&=a_2ar{h}_{3}^{ op} \ ar{b}_2&=ar{h}_3 \ ar{a}_2&=W_2ar{h}_3\ ar{h}_2&=modot ar{a}_2 \ ar{a}_1&=left[I~~0 ight] ar{h}_2 \ ar{h}_1&=mathrm{diag}left[frac{1+mathrm{sgn} left(h_1 ight)}{2} ight]ar{a}_1\ ar{W}_1&=xar{h}_{1}^{ op} \ ar{b}_1&=ar{h}_1 \ ar{x}&=W_1ar{h}_1+left[0~~I ight] ar{h}_2 end{aligned} ]

8.2 Convolutional Neural Networks (CNN)

Dropout：随机删除某个节点的连接，以重点关注其余节点

例题：输入 (xin mathbb{R} ^{C_{mathrm{in}} imes H imes W}),

[egin{aligned} u_1&=mathrm{Conv}2mathrm{d}left(C_{mathrm{in}},C_{mathrm{out}},k ight)(x)\ h_1&=mathrm{MaxPoil}2mathrm{d}left(N ight)left(u_1 ight) \ a_1&=mathrm{ReLU}left(h_1 ight) \ u_2&=mathrm{Flatten}left(a_1 ight)\ h_2&=W_{2}^{ op}u_2+b_2 \ hat{y}&=mathrm{Softmax} left(h_2 ight)\ end{aligned} ]

则损失函数对各个变量的梯度为

[egin{aligned} ar{h}_2&=hat{y}-y \ ar{W}_2&=a_2ar{h}_{2}^{ op}\ ar{b}_2&=ar{h}_2 \ ar{u}_2&=W_2ar{h}_2 \ ar{a}_{1}^{left(i,j,k ight)}&=W_{2}^{left(nleft(i,j,k ight),: ight)}ar{h}_2 end{aligned} ]

其中

[nleft(i,j,k ight)=left(i-1 ight)H_{mathrm{mp}}W_{mathrm{mp}}+left(j-1 ight)W_{mathrm{mp}}+k ]

[ar{h}_{1}^{(r,s,t)}=frac{1+mathrm{sgn} left(h_{1}^{(r,s,t)} ight)}{2} ar{a}_{1}^{(r,s,t)} ]

卷积：

[u_{1}^{left(j,:,: ight)}=b_{1}^{left(j,:,: ight)}+sum_{k=1}^{C_{mathrm{in}}}W_{1}^{left(j,k,:,: ight)}star x^{left(k,:,: ight)} ]

其中 (star) 符号表示二维互相关

例题：

[a_i=mathrm{Sigmoid}left(W_{i}^{ op}a_{i-1}+b_i ight),~i=1,dots ,l ]

且

[a_0=x, a_l=hat{y} ]

令

[sigma left(z ight) riangleq mathrm{Sigmoid}left(z ight) ]

则

[sigma 'left(z ight)=mathrm{diag}left(sigma left(z ight)odot left[1-sigma left(z ight) ight] ight) ]

因此

[ar{W}_1=xleft[left(prod_{i=2}^{l}W_i ight)left(prod_{j=1}^{l}sigma 'left(a_j ight) ight)ar{hat{y}} ight] ^{ op} ]

其中

[sigma 'left(a_j ight)leqslant frac{1}{4} ]

则会出现梯度消失的问题

ReLU：

[ar{W}_1=xleft[left(prod_{i=2}^{l}W_i ight)left(prod_{j=1}^{l}mathrm{diag}left[frac{1+mathrm{sgn} left(a_j ight)}{2} ight] ight)ar{hat{y}} ight] ^{ op} ]

若行列式 (mathrm{det}(W_i)) 过小，则其连乘部分会消失，整体的梯度仍然会消失

ResNet：

[a_i=mathrm{Sigmoid}left(W_{i}^{ op}a_{i-1}+b_i ight)+a_{i-1},i=1,dots ,l ]

则梯度为

[ar{W}_1=xleft[sigma 'left(a_1 ight)left(prod_{i=2}^{l}left[ W_isigma 'left(a_i ight)+I ight] ight)ar{hat{y}} ight] ^{ op} ]

连乘的每一项都包含单位矩阵 (I)，有效缓解了梯度消失的问题

8.3 Recurrent Neural Networks (RNN)

目的：处理序列数据，如语言，轨迹，金融数据等

网络结构及展开：

更新方程：

[egin{aligned} h^{left(t ight)}&=phi left(Wh^{left(t-1 ight)}+Ux^{left(t ight)}+b ight)\ hat{y}^{left(t ight)}&=sigma left(Vh^{left(t ight)}+c ight) end{aligned} ]

BP 算法：换个符号，并考虑 (E_t=d_t-y_t)

(y_t=phi left(v_t ight), v_t=sigma left(w_vy_{t-1}+w_xx_t ight))，这里 (sigma (x) riangleq x)

[egin{aligned} frac{partial E}{partial w_v}&=sum_{t=1}^s{frac{partial E_t}{partial w_v}} \ frac{partial E_t}{partial w_v}&=sum_{k=1}^t{frac{partial E_t}{partial y_t}frac{partial y_t}{partial v_t}frac{partial v_t}{partial v_k}frac{partial v_k}{partial w_v}}\ frac{partial E_t}{partial y_t}&=frac{partial left(d_t-y_t ight)}{partial y_t}=-1 \ frac{partial y_t}{partial v_t}&=phi 'left(v_t ight) \ frac{partial v_t}{partial v_k} &=prod_{i=k+1}^t{frac{partial v_i}{partial v_{i-1}}}\ &=prod_{i=k+1}^t{frac{partial v_i}{partial y_{i-1}}frac{partial y_{i-1}}{partial v_{i-1}}}\ &=prod_{i=k+1}^t{w_vphi 'left(v_{i-1} ight)}\ frac{partial v_k}{partial w_v}&=y_{k-1} end{aligned} ]

8.4 Long Short Term Memory (LSTM)

网络结构：对 RNN 的输入输出和展开过程均加入门控

更新过程：(sigma left(cdot ight) riangleq mathrm{sigmoid}left(cdot ight))

Input gate：(i_t=sigma left(w_{xi}x_t+w_{hi}h_{t-1}+b_i ight))

Forget gate：(f_t=sigma left(w_{xf}x_t+w_{hf}h_{t-1}+b_f ight))

Output gate：(o_t=sigma left(w_{xo}x_t+w_{ho}h_{t-1}+b_o ight))

External input gate：

[g_t= anh left(w_{xg}x_t+w_{hg}h_{t-1}+b_g ight) ]

输出：

[egin{aligned} c_t&=f_todot c_{t-1}+i_todot g_t\ h_t&=o_todot anh left(c_t ight) end{aligned} ]

梯度：

[egin{aligned} ar{c}_t&=ar{h}_to_tleft[1- anh ^2left(c_t ight) ight] \ ar{w}_{ix}&=sum_tar{i}_ti_tleft(1-i_t ight)x_t end{aligned} ]

8.5 Attention

注意力机制：加权平均，权重表示不同的重视程度

网络参数：键值对 (left{ k_i,v_i ight})，查询向量 (q)

注意力：

[egin{aligned} cleft(left{ k_i,v_i ight} ,q ight)&=sum_imathrm{similarity}left(q,k_i ight)cdot v_i\ &=sum_ialpha_iv_i end{aligned} ]

相似性度量：(alpha_i) 的计算可使用内积，余弦相似度，MLP，softmax：

[alpha_i=frac{exp left(k_{i}^{ op}q ight)}{sum_iexp left(k_{i}^{ op}q ight)} ]

8.6 Graph Convolutional Neural Networks (GNN)

邻接矩阵：(A=left[a_{ij} ight],~a_{ij}=left[i ightarrow j ight])

度矩阵：(D=mathrm{diag}left(d_i ight))，出度 (d_i=sum_ja_{ij})，入度 (d_j=sum_ia_{ij})

简单 Propagation：

[H^{i+1}=sigma left(D^{-1}AH^iW^i ight) ]

9 非监督学习：降维

降维：给定一组高维样本，寻找一个低维空间表示这些样本

9.1 主成分分析 (PCA, Principal Component Analysis)

理论推导：最小均方误差的角度

向量 (xin mathbb{R} ^n) 视为随机变量，完备正交归一向量基：(left{ u_i ight}_{i=1}^{infty})，则

[x=sum_{i=1}^{infty}c_iu_i ]

若用 (dll n) 维来表示有

[hat{x}=sum_{i=1}^{d}c_iu_i ]

误差为

[epsilon =mathbb{E} left[left(x-hat{x} ight)^{ op}left(x-hat{x} ight) ight] =mathbb{E} left[sum_{i=d+1}^{infty}c_{i}^{2} ight] ]

又 (c_i=x^{ op}u_i)，则

[egin{aligned} epsilon &=mathbb{E} left[sum_{i=d+1}^{infty}u_{i}^{ op}xx^{ op}u_i ight] \ &=sum_{i=d+1}^{infty}u_{i}^{ op}mathbb{E} left[xx^{ op} ight] u_i\ &=sum_{i=d+1}^{infty}u_{i}^{ op}Psi u_i\ end{aligned} ]

其中

[Psi riangleq mathbb{E} left[xx^{ op} ight] ]

零均值化：须保证 (mathbb{E} left[x ight] =0)，则 (Psi) 为协方差矩阵

优化问题：(min epsilon)，其 Lagrange 函数为

[L=sum_{i=d+1}^{infty}u_{i}^{ op}Psi u_i-sum_{i=d+1}^{infty}lambda_ileft(u_{i}^{ op}u_i-1 ight) ]

梯度条件：

[frac{partial L}{partial u_j}=2left(Psi u_j-lambda_ju_j ight)=0 ]

即

[Psi u_j=lambda_ju_j ]

K-L 变换坐标系：(Psi) 前 (d) 个最大特征值对应的特征向量

K-L 变换：(x) 在 (u_1,u_2,dots ,u_d) 上展开系数

[x'=left[c_1,c_2,dots ,c_d ight] ^{ op} ]

性质：视展开系数 (x') 为随机向量，

[mathbb{E} left[c_ic_j ight] =lambda_iu_{i}^{ op}u_j=lambda_idelta_{ij} ]

[lambda_i=mathbb{E} left[c_{i}^{2} ight] =mathbb{E} left[left(c_i-mathbb{E} left(c_i ight) ight)^2 ight] =sigma_{i}^{2} ]

即特征值 (lambda_i) 表示数据降维投影在一维特征向量 (u_i) 方向上的方差，所以 K-L 变换就是把数据投影到 (d) 个正交的序贯最大方差方向上去

降维维度确定：根据精度要求与计算、存储能力确定

9.2 多维尺度变换 (MDS, Multi-Dimensional Scaling)

理论推导：数据点 (x_rin mathbb{R} ^p, r=1,2,dots ,n)，假定零均值

内积 (b_{rs}=x_{r}^{ op}x_s)，(X=left[x_1,dots ,x_n ight] ^{ op})，内积矩阵为 (B=XX^{ op})，平方距离

[egin{aligned} d_{rs}^{2} &=left(x_r-x_s ight)^{ op}left(x_r-x_s ight)\ &=x_{r}^{ op}x_r+x_{s}^{ op}x_s-2x_{r}^{ op}x_s end{aligned} ]

平方距离矩阵

[D=c1^{ op}+1c^{ op}-2B ]

其中

[c=left[x_{1}^{ op}x_1,dots ,x_{n}^{ op}x_n ight] ]

中心化矩阵：

[J=I-frac{1}{n}11^{ op} ]

易知

[left(c1^{ op} ight)J=Jleft(1c^{ op} ight)=0 ]

且由 (sum_rx_r=0) 可得

[JX=X-frac{1}{n}11^{ op}X=X ]

因此

[JBJ=JXX^{ op}J^{ op}=B ]

又

[egin{aligned} JDJ&=Jleft(c1^{ op} ight)J+Jleft(1c^{ op} ight)J-2JBJ\ &=-2B \ end{aligned} ]

所以

[B=-frac{1}{2}JDJ ]

SVD：(B=VLambda V^{ op})，其中 (V=left[v_1,dots ,v_p ight])，(Lambda =mathrm{diag}left(lambda_1,dots ,lambda_p ight))，则 (X=VLambda ^{1/2})，若降维 (k < p) 则取前 (k) 个特征值与特征向量

降维维度确定：

[egin{aligned} frac{1}{2}sum_rsum_sd_{rs}^{2} &=nsum_rx_{r}^{ op}x_r\ &=nmathrm{Tr}left(B ight)\ &=nsum_rlambda_r\ end{aligned} ]

可知为保持总体距离降低较少需取较大的特征值，总体距离降低比例为

[ ho=frac{displaystylesum_{i=1}^{p}lambda_i}{displaystylesum_{i=1}^{n-1}lambda_i} ]

可通过固定比例为 ( ho=95\%) 选取 (p)

9.3 等距特征映射 (ISOMAP, Isometric Feature Mapping)

基本思想：利用测地距离代替欧氏距离，保留样本分布信息

算法：

1. 找到 (k) 近邻 (或欧氏距离小于 (epsilon)) 点并计算欧式距离 (d_Xleft(i,j ight))，定义图 (G)，若样本点为 (k) 近邻则连线，连线长度为 (d_Xleft(i,j ight))
2. 计算图上任意两点间最短距离 (D_G=left[d_Gleft(i,j ight) ight])
3. 通过 MDS 多维尺度变换降维到 (d) 维空间

9.4 局部线性嵌入 (LLE, Locally Linear Embedding)

基本思想：高维数据集中分布在潜在的低维的平滑流形上，每个样本点及其近邻分布在流形上的一个局部线性区域

1. 寻找每个样本点的近邻

2. 解优化问题

   [min epsilon left(W ight)=sum_ileft|x_i-sum_jW_{ij}x_j ight|^2 ]

   求得 (W)

3. 固定 (W)，求降维向量

[y_iLeftarrow min epsilon left(W ight)=sum_ileft|x_i-sum_jW_{ij}x_j ight|^2 ]

10 非监督学习：聚类

10.1 (C) 均值方法 (K-means)

基于样本的方法：根据样本间相似性，使准则函数 (J_e) 取最值

思路：

1. 把样本分成一些不同的类别
2. 不断调整样本使得相似的样本聚集在一起
3. GMM 的 EM 算法取极限的特例

算法：

[min J_e=sum_{i=1}^c{sum_{yin Gamma_i}^{}{left| y-m_i ight| ^2}} ]

1. 把样本初始划分成 (C) 类，计算各类均值 (m_1,dots ,m_C) 和 (J_e)
2. 选任意一个样本 (y)，设 (yin Gamma_i)
3. 若 (N_i=1)，则该类只有1个元素则无需移出，转 2)
4. 计算当 (y) 被调整到其它各类时 (J_e) 的变化量：

[ ho_j= egin{cases} dfrac{N_j}{N_j+1}left| y-m_j ight| ^2, &mathrm{if}~j e i\ dfrac{N_i}{N_i-1}left| y-m_j ight| ^2, &mathrm{o}.mathrm{w}. end{cases} ]

5. 如果 ( ho_kleqslant ho_j, forall j)，则移动 (y:Gamma_i ightarrow Gamma_k)
6. 更新均值 (m_i, m_k) 和均方误差 (J_e)
7. 若连续迭代 (N) 次不变则算法终止，否则转 2)

问题：

• (C) 的确定：(J_e-C) 曲线肘点
• 初始划分：先选择一些代表点作为聚类的核心，然后把其余的点按某种方法分到各类中去，初始划分不当可能会使得问题陷入局部最优解

10.2 多级聚类方法 (Hierarchical Clustering)

算法：

1. 每个样本为一类
2. 最近的两类合并，直到只剩一类

两类之间的距离度量：

• 最近距离：

  [Delta left(Gamma_i,Gamma_j ight)=min_{yin Gamma_i, ilde{y}in Gamma_j}delta left(y, ilde{y} ight) ]

  不适合两类之间距离较近且中间有个别离群点，适合带状分布的数据

• 最远距离：

  [Delta left(Gamma_i,Gamma_j ight)=max_{yin Gamma_i, ilde{y}in Gamma_j}delta left(y, ilde{y} ight) ]

  与最近距离效果相反

• 均值距离：

  [Delta left(Gamma_i,Gamma_j ight)=delta left(m_i,m_j ight) ]

  效果介于以上两者之间

分类数量：根据聚类树判断，最长或次长跳跃前的水平

10.3 谱聚类 (Spectral Clustering)

样本点集：(x_1,dots ,x_n)

相似性度量：(s_{ij}=sleft(x_i,x_j ight)geqslant 0)

相似性图：加权无向图 (G=left(V,E ight))

加权邻接矩阵：(W=left(w_{ij} ight))

边权重：(w_{ij}=s_{ij})

度矩阵：(D=mathrm{diag}left(d_1,dots ,d_n ight))，其中度：

[d_i=sum_{j=1}^{n}w_{ij} ]

Graph Laplacian：未归一化 (L=D-W)，归一化 (L_{rw}=D^{-1}L)

性质：对称，半正定，最小特征值0，对应特征向量为1

构造相似性图：

1. (epsilon)-近邻图：任意两个距离小于 (epsilon) 的点之间存在一条边

2. (k)-近邻图：若 (v_i) 是 (v_j) 的 (k) 近邻，则存在一条边 (无向化)

3. 对称 (k)-近邻图：若两个点互为 (k) 近邻，则存在一条边

4. 全连接图：相似性大于 0 的两个点之间存在一条边

算法：

1. 输入相似性矩阵 (Sin mathbb{R} ^{n imes n})，聚类类别数 (k)
2. 构造相似性图，设加权邻接矩阵为

[W=[w_{ij}]=[s_{ij}] ]

3. 计算未归一化 (归一化) Graph Laplacian (Lleft(L_{rw} ight))
4. 计算 (Lleft(Lu=lambda Du ight)) 的前 (k) 个最小特征值对应的特征向量 (u_1,dots ,u_k)，并记

[U riangleq left[u_1,dots ,u_k ight] ]

5. 设 (y_iin mathbb{R} ^k) 为 (U) 的第 (i) 行构成的向量，称为谱嵌入向量
6. 使用 (C) 均值聚类方法将点 (left{ y_i ight}) 聚为 (k) 类

[C_1,dots ,C_k ]

7. 输出最终聚类为 (A_1,dots ,A_k)，其中

[A_i=left{ j:y_jin C_i ight} ]

推导：寻找图的划分，使得不同点集间边权重较小，同一点集内边权重较大，

[min mathrm{cut}left(A_1,dots ,A_k ight) =frac{1}{2}sum_{i=1}^{k}Wleft(A_i,ar{A}_i ight) ]

其中 (|A|) 表示 (A) 中顶点的个数，(mathrm{vol}left(A ight)) 表示 (A) 中顶点度的和

[egin{aligned} mathrm{RatioCut}left(A_1,dots ,A_k ight) &=frac{1}{2}sum_{i=1}^k{frac{Wleft(A_i,ar{A}_i ight)}{|A_i|}}\ &=frac{1}{2}sum_{i=1}^k{frac{mathrm{cut}left(A_i,ar{A}_i ight)}{|A_i|}} end{aligned} ]

[egin{aligned} mathrm{NCut}left(A_1,dots ,A_k ight) &=frac{1}{2}sum_{i=1}^k{frac{Wleft(A_i,ar{A}_i ight)}{mathrm{vol}left(A_i ight)}}\ &=frac{1}{2}sum_{i=1}^k{frac{mathrm{cut}left(A_i,ar{A}_i ight)}{mathrm{vol}left(A_i ight)}} end{aligned} ]

松弛离散约束后，RatioCut 对应归一化 Graph Laplacian，Ncut 对应未归一化 Graph Laplacian

注记：

• 谱聚类往往对相似性图及参数选择比较敏感，且存在尺度问题，一般 (k) 近邻图可以比较好的连接不同尺度下的数据，通常作为首选
• 参数选择应该使相似性图是连通的或连通分量数量较少
• 尽量选择归一化的 Graph Laplacian，理由：考虑聚类的原则，最小化 RatioCut 只考虑了使得不同点集间的边的权重较小，而最小化 Ncut 在某种程度上考虑了同一点集内的边权重较大

聚类方法的选择：

• 根据样本的分布特性和数量综合考虑
• 若样本点近似成球状分布或者样本数很大时，则用 K-means 算法能取得较好效果，且速度快
• 当样本数量较少时，可以选择基于最近邻图的谱聚类方法，其聚类的效果较好，而且不像分级聚类那样受距离度量选择的影响大

11 决策树

11.1 决策树概览

11.2 CART (Classification And Repression Trees)

分类和回归树算法 CART：一种通用的树生长算法

分枝数目：与属性有关，但决策树都等价于二叉树

构造决策树原则：简单性，获得的决策树简单、紧凑

节点不纯度 Impurity：(ileft(N ight)) 表示节点 (N) 的不纯度

• 熵不纯度：
  [ileft(N ight)=-sum_jPleft(w_j ight)log_2Pleft(w_j ight) ]
  其中 (Pleft(w_j ight)) 表示节点 (N) 处属于 (w_j) 类样本占节点总样本数的比例
• Gini 不纯度：
  [egin{aligned} ileft(N ight) &=sum_{i e j}Pleft(w_i ight)Pleft(w_j ight)\ &=1-sum_jP^2left(w_j ight) end{aligned} ]

• 错分不纯度：被错分的最小概率
  [ileft(N ight)=1-max_jPleft(w_j ight) ]

特征选择：选择能够使不纯度下降最多的特征做查询，不纯度下降

[Delta ileft(N ight)=ileft(N ight)-P_Lileft(N_L ight)-left(1-P_L ight)ileft(N_R ight) ]

其中 (P_L) 是分配到 (N_L) 节点样本数量占 (N) 节点样本数量比例

局部贪婪算法：只考虑了单一特征带来的不纯度下降

多重分枝：

[Delta ileft(N ight)=ileft(N ight)-sum_{k=1}^{B}P_kileft(N_k ight) ]

其中 (B) 为分枝数目，(P_k) 是节点 (N_k) 处样本占 (N) 处样本比例，但

[Buparrow Rightarrow Delta ileft(N ight)uparrow ]

故调整

[Delta i_Bleft(N ight)= frac{Delta ileft(N ight)}{-displaystylesum_{k=1}^{B}P_klog_2P_k} ]

分枝停止准则：

• 传统方法，验证或交叉验证
• 阈值方法，当所有候选分支的不纯度下降量都小于这个阈值，则停止分支

阈值方法优点：

• 全部样本都可用来训练
• 树的各个深度上都可能存在叶节点，这是一棵非平衡树

阈值方法缺点：

• 很难预先设定一个合适的阈值，因为树的分类准确性与阈值大小通常不是简单的函数关系

后剪枝：使用全部训练集数据，但计算量会增加

1. 树充分生长，直到叶节点都有最小的不纯度值
2. 对所有相邻的成对叶节点，如果消去它们能引起不纯度增长，则消去它们，并令其公共父节点成为新的叶节点

叶节点标号：用叶节点样本中大多数样本的类别来标号

不稳定性：树的生长对训练样本的微小位置变动很敏感，很大程度上是由离散性和节点选择时的贪婪性所导致的

特征选择：选择特征使得决策面简单，可尝试线性组合

多元决策树：当实值数据样本分布复杂时，平行于特征轴分界面的效率和推广性都可能很差，可采用一般的线性分类器

属性缺失：对主分支外的属性做替代分枝并根据相似性排序

11.3 ID3 (Interactive Dichotomizer-3)

算法：实值变量按区间离散化，节点分支数等于其属性的离散取值个数，决策树生长到所有叶节点都为纯，无剪枝

11.4 C4.5

算法概述：对于实值变量的处理和 CART 相同，对名义属性采用多重分支，不纯度的计算采用 (Delta i_Bleft(N ight))

与 CART 区别：对属性缺失数据的处理，所有 (B) 个分支进行判别，最终分类结果是 (M) 个叶节点加权决策的结果

基于规则的剪枝：尝试删除规则任意一个前件，取性能提高最大的子规则，重复删除直到无法修剪，按性能降序排序

优点：

• 允许在特定节点处考虑上下文信息
• 靠近根节点处的节点也可能被剪枝，根节点与叶节点等价，比叶节点合并剪枝方法更加通用
• 简化的规则可用于更好的类别表达

12 多分类器方法 (Ensemble)

12.1 Bagging (Bootstrap Aggregating)

算法：基于训练样本的分类器构造

1. 从训练集 (N) 个样本中随机抽取 (Bootstrap) 出 (n) 个样本
2. 用这 (n) 个样本训练一个分类器 (h)，然后放回这些样本
3. 重复步骤 1) 与 2) (L) 次，得到分类器
   [h_1, h_2,dots ,h_L ]

4. 使用 (L) 个分类器进行判别，决策层投票得到最终结果

基分类器：选择不稳定的分类器，决策树，神经网络等

12.2 AdaBoost (Adaptive Boosting)

算法：基于训练样本的分类器构造

输入：(X=left{ left(x_1,y_1 ight),dots ,left(x_N,y_N ight) ight})，基分类器 (C)，循环次数 (L)

初始化：样本 (x_i) 权重

[w_1(i)=frac{1}{N} ]

for (l=1) to (L)：

权重归一化

[p_l(i)=frac{w_l(i)}{displaystylesum_iw_l(i)},~forall~i=1,2,dots ,N ]

根据 (p_l(i)) 采样生成样本集合 (s_l)，训练分类器 (h_l)

计算 (h_l) 分类错误率

[epsilon_l=sum_ip_l(i)ar{delta}_{iy} ]

其中

[ar{delta}_{iy} riangleq left[h_lleft(x_i ight) e y_i ight] ]

计算权重系数的参数

[a_l=frac{1}{2}lnfrac{1-epsilon_l}{epsilon_l} ]

更新权重

[w_{l+1}(i)=w_l(i)mathrm{e}^{-a_l}delta_{iy}+w_l(i)mathrm{e}^{a_l}(1-delta_{iy}) ]

输出：加权投票

[h(x)=mathrm{argmax}_{yin Y}sum_{l=1}^{L}a_l[h_l(x)=y] ]

特性：随着算法进行，聚焦于容易分错而富含信息的样本

错误率：二分类 (Y=left{ 1,-1 ight})，(T) 轮迭代后样本概率分布为

[egin{aligned} p_{T+1}(i) &=p_T(i)frac{mathrm{e}^{-alpha_Ty_ih_T(i)}}{Z_T}\ &=p_1(i)frac{mathrm{e}^{-y_ileft< alpha ,h(i) ight>}}{displaystyleprod_{j=1}^{T}Z_j}\ &=frac{mathrm{e}^{-y_ileft< alpha ,h(i) ight>}}{Ndisplaystyleprod_{j=1}^{T}Z_j} end{aligned} ]

又

[sum_ip_{T+1}(i)=1 ]

则

[prod_{j=1}^{T}Z_j=frac{1}{N}sum_{i=1}^Nmathrm{e}^{-y_ileft< alpha ,h(i) ight>} ]

第 (i) 个样本错误标志

[egin{aligned} epsilon_i &=1-left[h_Tleft(x_i ight)=y_i ight] \ &leqslant mathrm{e}^{-y_ileft< alpha ,h(i) ight>} end{aligned} ]

则总错误率是分类错误率的一个上界

[egin{aligned} epsilon &=frac{1}{N}sum_{i=1}^Nepsilon_i\ &leqslantfrac{1}{N}sum_{i=1}^Nmathrm{e}^{-y_ileft< alpha ,h(i) ight>}\ &=prod_{j=1}^{T}Z_j end{aligned} ]

优化问题

[min~prod_{j=1}^{T}Z_j ]

可解得

[a_l=frac{1}{2}lnfrac{1-epsilon_l}{epsilon_l} ]

且由

[egin{aligned} Z_l &=sum_ip_l(i)mathrm{e}^{-alpha_ly_ih_l(i)}\ &=sum_{iin A}p_l(i)mathrm{e}^{-alpha_l}+sum_{iin ar{A}}p_l(i)mathrm{e}^{+alpha_l}\ &=left(1-epsilon_l ight)mathrm{e}^{-alpha_l}+epsilon_lmathrm{e}^{alpha_l}\ &=2sqrt{epsilon_lleft(1-epsilon_l ight)}\ &=sqrt{1-4gamma_{l}^{2}} end{aligned} ]

可得

[egin{aligned} prod_{l=1}^{T}Z_l &=prod_{l=1}^{T}sqrt{1-4gamma_{l}^{2}}\ &leqslant exp left(-2sum_{l=1}^{T}gamma_{l}^{2} ight)\ &leqslant mathrm{e}^{-2Tgamma_{min}^{2}} end{aligned} ]

因此，错误率可以随着迭代次数的增加而指数级下降

与 Bagging 对比：基分类器以序贯方式使用加权数据集进行训练，其中每个数据点权重依赖前一个分类器的性能

12.3 基于样本特征的分类器构造

随机子空间算法：随机抽取 (也可对特征加权) 特征子集 (S_l)，利用在 (S_l) 上的训练样本训练分类器 (h_l)，重复 (L) 次得到 (L) 个分类器，最后进行投票

[h(x)=mathrm{argmin}_{yin Y}sum_{l=1}^{L}left[h_l(x)=y ight] ]

12.4 分类器输出融合

1. 决策层输出：对于待测试的样本，用每一个基分类器的分类结果投票，得票最多的类别号就是待测试样本的类别
2. 排序层输出：分类器输出为输入样本可能属于的类别列表，并依据可能性大小进行排序，之后采用 Borda 计数：对名次赋分，计算每个类别总得分并排序
3. 度量层输出：分类器输出为样本归属于各个类别的一种相似性度量，对于每一类的所有的相似性度量值求和，和值最大的类别就是未知样本的类别标号

12.5 多分类器方法有效的原因

1. 统计方面：避免单分类器分类时的不稳定性
2. 计算方面：脱离单分类器陷入的局部最优解
3. 表示方面：拓展原简单假设空间的表达能力

13 统计学习理论

13.1 PAC (Probably Approximately Correct) 可学习

若函数集 VC 维是有限值，则任意概率分布均 PAC 可学习

13.2 VC (Vapnic-Chervonenkis) 维

期望风险：

[Rleft(omega ight)=int Lleft(y,fleft(x,omega ight) ight)mathrm{d}Fleft(x,y ight) ]

经验风险：

[R_{mathrm{emp}}left(omega ight)=frac{1}{N}sum_{i=1}^{N}Lleft(y,fleft(x,omega ight) ight) ]

VC 维：描述学习机器的复杂性

推广性界定理：

[Rleft(omega ight)leqslant R_{mathrm{emp}}left(omega ight)+Phi left(frac{n}{mathrm{VC}} ight) ]

其中函数 (Phi searrow)

13.3 没有免费的午餐

• 不存在一种模式分类算法具有天然的优越性，甚至不比随机猜测更好
• 如果某种算法对某个特定的问题看上去比另一种算法更好，其原因仅仅是它更适合这一特定的模式分类任务

13.4 丑小鸭定理

不存在与问题无关的最好的特征集合或属性集合

14 算法优缺点

14.1 贝叶斯分类器

优点：

• 理论上可以满足分类错误率最小
• 对于服从特定模型的样本有较好的分类结果
• 是其他分类算法的理论基础

缺点：

• 依赖模型 (类先验概率，类条件概率分布的形式和具体参数) ，因此模型可能选错
• 模型的参数可能过拟合
• 实际样本独立同分布难以满足

14.2 SVM

优点：

• 将低位空间线性不可分问题变换到高维空间，使其线性可分，由于只需要进内积计算，并没有增加多少计算复杂度
• 推广能力与变换空间维数无关，具有较好的推广能力
• 相对于传统方法，对模型具有一定的不敏感性

缺点：

• 对大规模训练样本难以实施
• 解决多分类问题存在困难
• 对缺失数据敏感，对参数和核函数的选择敏感

14.3 近邻法

优点：

• 错误率在贝叶斯错误率及其两倍之间
• 算法直观容易理解易于实现
• 可以适用任何分布的样本，算法适用性强

缺点：

• 需将所有样本存入计算机中，每次决策都要计算待识别样本与全部训练样本的距离并进行比较，存储和计算开销大
• 当错误的代价很大时，会产生较大风险
• 错误率的分析是渐进的，这要求样本为无穷，实际中这一条件很难达到

15 矩阵求导

15.1 迹 Trace

[frac{partial mathrm{Tr}left(W^{ op}Sigma W ight)}{partial W}=2Sigma W ]

[frac{partial mathrm{Tr}left(AB ight)}{partial A}=B+B^{ op}-mathrm{diag}left(B ight) ]

15.2 行列式

[frac{partial ln |A|}{partial A}=2A^{-1}-mathrm{diag}left(A^{-1} ight) ]

16 补充内容

• 感知准则函数：

  [min J_pleft(a ight)=sum_{yin Y^k}left(-a^{ op}y ight)geqslant 0 ]

  以使错分样本到分界面距离之和最小为原则

• 分类器错误率：分类结果中与样本实际类别不同的样本在总体中的比例

• 错误率估计方法：理论计算，计算错误率的上界，实验估计

• Fisher 与 Perceptron：Fisher 线性判别是把线性分类器的设计分为两步，一是确定最优方向，二是在这个方向上确定分类阈值；感知机则是通过不断迭代直接得到线性判别函数

• K-means 与 EM (GMM)：K 均值算法对数据点的聚类进行了硬分配，即每个数据点只属于唯一的聚类，而 EM 算法基于后验概率分布，进行了一个软分配。实际上，可以把 K 均值算法看成 GMM 的 EM 算法的一个特殊的极限情况。考虑高斯混合模型协方差矩阵均为 (epsilon I)，从而

  [Pleft(x|mu_k,Sigma_k ight)=frac{1}{left(2pi epsilon ight)^{d/2}}exp left(-frac{left| x-mu_k ight|^2}{2epsilon} ight) ]

  令 (epsilon ightarrow 0) 则可得到 K 均值算法的硬分配

参考文献

• 张长水, 赵虹. 模式识别课程讲义与作业. 清华大学, 2021.
• 张学工. 模式识别第3版. 清华大学出版社, 2010.
• Richard O. Duda, Peter E. Hart, David G. Stork. Pattern classification, 2nd Edition. Hoboken: Wiley, 2000.