1 模式识别

1. 简述模式的概念和他的直观特性
   • 模式：是抽取自物体的信息集合，既包含空间部分，又包含时间部分。
   • 直观特性：可观察性，可区分性，相似性
   • 主要方法：
     • 监督学习：概念驱动，归纳假说
     • 无监督学习：数据驱动，演绎假说
   • 模式分类的主要方法：
     • 数据聚类：用某种相似性度量的方法将原始数据组织成有意义的和有用的各种数据集。是一种非监督学习的方法，解决方案是数据驱动的。
     • 统计分类：基于概率统计模型得到各类别的特征向量的分布，以取得分类的方法。特征向量分布的获得是基于一个类别已知的训练样本集。是一种监督分类的方法，分类器是概念驱动的。
     • 结构模式识别：该方法通过考虑识别对象的各部分之间的联系来达到识别分类的目的。（句法模式识别）
     • 神经网络：由一系列互相联系的、相同的单元（神经元）组成。相互间的联系可以在不同的神经元之间传递增强或抑制信号。增强或抑制是通过调整神经元相互间联系的权重系数来（weight）实现。神经网络可以实现监督和非监督学习条件下的分类。

过拟合欠拟合

2. 某研究者在会议上使用SVM，在如下情况下，如何才能使效果更好：
   • 训练5%，验证误差10%，测试误差10%
     • 欠拟合：换用复杂度高的模型
   • 训练1%，验证误差10%，测试误差10%
     • 过拟合：换复杂度低的模型
   • 训练1%，验证误差3%，测试误差10%
     • 测试数据与训练数据不是独立同分布的，更换测试数据集

概率图

概率图-独立性

* P(x1,x2,x3,x4,x5,x6)=p(x1)p(x6)P(x2|x1)p(x3|x1,x6)P(x4|x3)p(x5|x2,x4)
* $$\begin{gathered} p(x1,x2,x3,x6)={\Sigma }_{x4}{\Sigma }_{x5}P(x1,x2,x3,x4,x5,x6) \\ =p(x1)p(x6)P(x2|x1)p(x3|x1,x6){\Sigma }_{x4}P(x4|x3){\Sigma }_{x5}p(x5|x2,x4) \\ =p(x1)p(x6)P(x2|x1)p(x3|x1,x6) \end{gathered}$$
* ${\Sigma }_{x5}p(x5|x2,x4)=1$
* $$\begin{gathered} P(x1,x2,x3,x4,x6)={\Sigma }_{x5}P(x1,x2,x3,x4,x5,x6) \\ =p(x1)p(x6)P(x2|x1)p(x3|x1,x6)P(x4|x3) \end{gathered}$$
* $P(x4|x1,x2,x3,x6)=p(x4|x3)---所以给定x3,x4和x6独立，和x1/x2/x6均独立$

HMM

• A:aij:i->j
• 前向计算
  • 时间1：
    • $$\begin{gathered} \alpha (y_1=1)=P(x_1|y_1=1){\pi }_{y_1=1}=0.5\ast 0.2=0.1 \\ （x1=红）\alpha (y_1=2)=P(x_1|y_1=2){\pi }_{y_1=2}=0.4\ast 0.4=0.16\alpha (y_1=3)=P(x_1|y_1=3){\pi }_{y_1=3}=0.7\ast 0.4=0.28 \end{gathered}$$
  • 时间2:x2=白
    • $$\begin{gathered} \alpha (y_2=1)=({\Sigma }_{y_1}\alpha (y_1)P(y_2=1|y_1))P(x_2|y_2)=(0.1\ast 0.5+0.16\ast 0.3+0.28\ast 0.2)\ast 0.5=0.077 \\ \alpha (y_2=2)=(\alpha (y_1=1)P(y_2=2|y_1=1)+\alpha (y_1=2)P(y_2=2|y_1=2)+\alpha (y_1=3)P(y_2=2|y_1=3))\ast P(x_2|y_2=2)=(0.1\ast 0.2+0.16\ast 0.5+0.28\ast 0.3)\ast 0.6=0.1104 \\ \alpha (y_2=3)=(0.1\ast 0.3+0.16\ast 0.2+0.28\ast 0.5)\ast 0.3=0.0606 \end{gathered}$$
  • 时间3：x3=红
    • $$\begin{gathered} \alpha (y_3=1)=(0.077\ast 0.5+0.1104\ast 0.3+0.0606\ast 0.2)\ast 0.5=0.4187 \\ \alpha (y_3=2)=(0.077\ast 0.2+0.1104\ast 0.5+0.0606\ast 0.3)\ast 0.4=0.03551 \\ \alpha (y_3=3)=(0.077\ast 0.3+0.1104\ast 0.2+0.0606\ast 0.5)\ast 0.7=0.05284 \\ p(x)={\Sigma }_i\alpha (y_T^i)=\alpha (y_3=1)+\alpha (y_3=2)+\alpha (y_3=3)=0.13022 \end{gathered}$$
• 后向计算：
  • $\beta (y_3=1)=1，\beta (y_3=2)=1，\beta (y_3=3)=1$
  • 时间2
    • $$\begin{gathered} \beta (y_2)={\Sigma }_{y_3}\beta (y_3)a_{y_3,y_2}P(x_3|y_3) \\ =\beta (y_3=1)a_{y_3=1,y_2}P(x_3|y_3=1)+\beta (y_3=2)a_{y_3=2,y_2}P(x_3|y_3=2)+\beta (y_3=3)a_{y_3,y_2}P(x_3|y_3=3) \end{gathered}$$
    • $\beta (y_2=1)=1\ast 0.5\ast 0.5+1\ast 0.2\ast 0.4+1\ast 0.2\ast 0.7=0.47$
    • $\beta (y_2=2)=1\ast 0.3\ast 0.5+1\ast 0.5\ast 0.4+1\ast 0.2\ast 0.7=0.49$
    • $\beta (y_2=3)=1\ast 0.2\ast 0.5+1\ast 0.3\ast 0.4+1\ast 0.5\ast 0.7=0.57$
  • 时间1
    • $\beta (y_2=1)=0.47\ast 0.5\ast 0.5+0.49\ast 0.2\ast 0.6+0.57\ast 0.2\ast 0.3=0.2105$
    • $\beta (y_2=2)=0.47\ast 0.3\ast 0.5+0.49\ast 0.5\ast 0.6+0.57\ast 0.2\ast 0.3=0.2517$
    • $\beta (y_2=3)=0.47\ast 0.2\ast 0.5+0.49\ast 0.3\ast 0.6+0.57\ast 0.5\ast 0.3=0.2207$
      
• 求最优路径(维特比，贪心）
  • $\delta (y_1)=\alpha (y_1)=P(x_1|y_1){\pi }_{y_1}$
  • $\delta (y_{t+1})=ma{x}_{y_1}\delta (y_1)P(y_2=1|y_1))P(x_2|y_2)=max(\delta (y_1=1)P(y_2=2|y_1=1),\delta (y_1=2)P(y_2=2|y_1=2),\delta (y_1=3)P(y_2=2|y_1=3))\ast P(x_2|y_2=1)$
• HMM(x–O)
  • 则联合概率$P(x,y)=p(y_1){\Pi }_{t=1}^{T-1}P(y_{t+1}^j|y_t^i){\Pi }_{t=1}^{T}P(x_t|y_t)$
    • 参数化$P(x,y)={\pi }_{y_1}{\Pi }_{t=1}^{T-1}{a}_{y_{t+1},y_t}{\Pi }_{t=1}^{T}P(x_t|y_t)$
  • $$\begin{gathered} P(x)={\Sigma }_{y_1,y_2,...,y_T}P(x,y)={\Sigma }_{y_1,y_2,...,y_T}{\pi }_{y_1}{\Pi }_{t=1}^{T-1}{a}_{y_{t+1},y_t}{\Pi }_{t=1}^{T}P(x_t|y_t) \\ ={\Sigma }_{y}P(x|y)p(y) \\ ={\Sigma }_{y_1}{\Sigma }_{y_2}...{\Sigma }_{y_T}{\pi }_{y_1}{\Pi }_{t=1}^{T-1}{a}_{y_{t+1},y_t}{\Pi }_{t=1}^{T}P(x_t|y_t) \end{gathered}$$
  • $P(y_t|x)=\gamma (y_t)=\frac{P(x1,...,x_t,y_t)P(x_{t+1},...,x_n|y_t)}{P(x)}=\frac{\alpha (y_t)\beta (y_t)}{P(x)}$
  • 递归的计算
    • $\alpha (y_{t+1})={\Sigma }_{y_t}\alpha (y_t)a_{y_{t+1},y_t}P(x_{t+1}|y_{t+1})$
      • 初始化$\alpha (y_0)=P(x_0,y_0)=p(x_0|y_0)P(y_0)=P(x_0|y_0){\pi }_{y_0}$
    • $\beta (y_t)={\Sigma }_{y_{t+1}}\beta (y_{t+1})a_{y_{t+1},y_t}P(x_{t+1}|y_{t+1})$
      • 初始化$\beta (y_T)=1就行了$
        • $假定\beta (y_T)为单位向量，我们可以准确计算出{\beta }_{y_{T-1}}$
          • $P(x)={\Sigma }_i\alpha (y_T^i)\beta (y_T^i)={\Sigma }_i\alpha (y_T^i)=P(x)$

哲学理论

4. （1）随便猜测作为一个分类算法是否一定比SVM差？借此阐述你对“no free lunch theorem”的理解（2）举例阐述你对“Occam’s razor"的理解
   • （1）：不一定，在没有先验的情况下，无法得知一个算法是否比另一个算法更好。
   • （2）简单的就是最好的：训练数据来自添加高斯噪声的$y=sinx(x\in [0,2\pi ])$,使用不同的多项式拟合，三次的效果最佳，在同等训练错误率的条件下，简单模型具有更小的方差，又有更好的泛化能力。（复杂模型方差大，偏差小）

• • 丑小鸭定理：
    • 丑小鸭与白天鹅之间的区别和两只白天鹅之间的区别一样大
    • 世界上不存在分类的客观标准，一切分类的标准都是主观的
    • (有假设的）
    • (无假设的前提下）没有最优的特征

adaboost

5. Adaboost的原理并给出算法，并解释为什么adaboost经常可以在训练误差为0后继续训练还能带来测试误差的继续下降？
   • adaboost原理：通过多个弱学习器的组合，得到一个强分类器，每次训练弱分类器后，对分类错误的样本增加权重使得后续分类器更加”关注“分类错误的样本，以提升分类效果。
   • 算法：{xi,yi}i=1nDi1=1/nforitoT：对每个分类器训练弱分类器，给各样本加权重Dit+1=Dit∗e−αtyiht(xi)ht(x)为第t个分类器;αt=12ln1−ϵtϵt>0;错误率ϵ=P(h(x)≠y)<0.5Hfinal(x)=sign(Σt=1nαtht(x))\{x_i,y_i\}_{i=1}^n\\D^1_i=1/n\\for i to T：对每个分类器\\训练弱分类器，给各样本加权重\\D_i^{t+1}=D_i^{t}*e^{-\alpha_ty_ih_t(x_i)}\\h_t(x)为第t个分类器;\alpha_t=\frac{1}{2}ln\frac{1-\epsilon_t}{\epsilon_t}>0;错误率\epsilon=P(h(x)\neq y)<0.5\\H_{final}(x)=sign(\Sigma_{t=1}^n\alpha_th_t(x)){xi​,yi​}i=1n​Di1​=1/nforitoT：对每个分类器训练弱分类器，给各样本加权重Dit+1​=Dit​∗e−αt​yi​ht​(xi​)ht​(x)为第t个分类器;αt​=21​lnϵt​1−ϵt​​>0;错误率ϵ=P(h(x)​=y)<0.5Hfinal​(x)=sign(Σt=1n​αt​ht​(x))
   • 训练误差为0后，adaboost会继续增大分类间距，提升模型的泛化能力，减少测试误差
     

贝叶斯

贝叶斯判别

贝叶斯判别-正态分布

• 贝叶斯判别：$p(wi|x)=\frac{p(x|w1)p(w1)}{{\Sigma }_{i=1}^{2}p(x|wi)p(wi)},哪个大属于哪一类$
• 模式类别具有正态概率密度函数 p(x∣wi)=1(2π)n/2∣Ci∣1/2exp{−12(x−mi)TCi−1(x−mi)}p(x|w_i) ={{1} \over {(2\pi)^{n/2}|C_i|^{1/2}}} exp\{ -{{1} \over {2}}(x-m_i)^TC_i^{-1}(x-m_i)\}p(x∣wi​)=(2π)n/2∣Ci​∣1/21​exp{−21​(x−mi​)TCi−1​(x−mi​)}—一个类别一个,n-n维度
  • $C_i=(x-m_i)(x-m_i{)}^T$–>x是一列一个样本的，C最终是个33的，m是31的列向量
  • 均值就用均值求，方差就用协方差矩阵求（由贝叶斯估计、极大似然估计都可以得到）
• 判别面：第i类的$$\begin{gathered} f(x)常数，g_i(x)=lnp(x|w_i)+lnp(w_i) \\ =lnp(w_i)-\frac{1}{2}log|C_i|-\frac{1}{2}(x-m_i{)}^T{C}_i^{-1}(x-m_i) \end{gathered}$$
• 二分类的界面：$g_1(x)-g_2(x)=lnp(w_1)+lnp(w_2)-\frac{1}{2}log|C_1|-\frac{1}{2}(x-m_1{)}^T{C}_1^{-1}(x-m_1)+\frac{1}{2}log|C_2|+\frac{1}{2}(x-m_2{)}^T{C}_2^{-1}(x-m_2)$
• 二分类的界面(C1=C2=C)：$$\begin{gathered} g_1(x)-g_2(x)=lnp(w_1)-lnp(w_2)-\frac{1}{2}(x-m_1{)}^T{C}_1^{-1}(x-m_1)+\frac{1}{2}(x-m_2{)}^T{C}_2^{-1}(x-m_2) \\ =lnp(w_1)-lnp(w_2)+(m_1-m_2{)}^T{C}^{-1}x-\frac{1}{2}{m}_1^T{C}^{-1}{m}_1+\frac{1}{2}{m}_2^T{C}^{-1}{m}_2=0 \end{gathered}$$
• $X1=\left[\begin{array}{ccccc}0& 1& 1& 1& \\ 0& 0& 0& 1& \\ 0& 0& 1& 0& \end{array}\right]$–一列一个样本，一行一个维度
• $X2=\left[\begin{array}{ccccc}0& 0& 0& 1& \\ 1& 1& 0& 1& \\ 0& 1& 1& 1& \end{array}\right]$
• $m1=\frac{1}{4}(3,1,1{)}^T,m_2=\frac{1}{4}(1,3,3{)}^T$
• $$\begin{gathered} C_1=(X1-m1)(X1-m1{)}^T=\frac{1}{16}\left[\begin{array}{ccc}12& 4& 4\\ 4& 12& -4\\ 4& -4& 12\end{array}\right] \\ C2=(X2-m2)(X2-m2{)}^T=\frac{1}{16}\left[\begin{array}{ccc}12& 4& 4\\ 4& 12& -4\\ 4& -4& 12\end{array}\right] \\ C=C1=C2 \end{gathered}$$

贝叶斯估计

• $图中\sigma ->{\sigma }^2$
• $p(\beta |y)=\frac{p(y|\beta )p(\beta )}{p(y)}$
• p(y∣β)=1(2π)n/2∣σ2I∣1/2exp{−12(y−Xβ)T(σ2I)−1(y−Xβ)}p(β)=1(2π)n/2∣τI∣1/2exp{−12(β)T(τI)−1(β)}p(y|\beta)={{1} \over {(2\pi)^{n/2}|\sigma^2I|^{1/2}}} exp\{ -{{1} \over {2}}(y-X\beta)^T(\sigma^2I)^{-1}(y-X\beta)\}\\ p(\beta)={{1} \over {(2\pi)^{n/2}|\tau I|^{1/2}}} exp\{ -{{1} \over {2}}(\beta)^T(\tau I)^{-1}(\beta)\}p(y∣β)=(2π)n/2∣σ2I∣1/21​exp{−21​(y−Xβ)T(σ2I)−1(y−Xβ)}p(β)=(2π)n/2∣τI∣1/21​exp{−21​(β)T(τI)−1(β)}
• $$\begin{gathered} logp(\beta |y)=log(p(y|\beta )+logp(\beta )+C \\ =-\frac{1}{2{\sigma }^2}(y-X\beta {)}^2-\frac{1}{2\tau }||\beta |{|}^2+C^{\prime } \\ =-\frac{1}{2{\sigma }^2}((y-X\beta {)}^2+\frac{{\sigma }^2}{\tau }||\beta |{|}^2) \end{gathered}$$

贝叶斯决策

• 最小错误率就是最普通的贝叶斯决策$I_{12}=\frac{p(x\Vert w1)}{p(x\Vert w2)}>\frac{p(w2)}{p(w1)}，分界面为d(x)=\frac{p(x\Vert w1)}{p(x\Vert w2)}-\frac{p(w2)}{p(w1)}$
• 最小风险的贝叶斯决策$$\begin{gathered} r_1={\lambda }_{11}p(x|w_1)p(w_1)+{\lambda }_{12}p(x|w_2)p(w_2) \\ {r}_2={\lambda }_{21}p(x|w_1)p(w_1)+{\lambda }_{22}p(x|w_2)p(w_2) \\ {r}_1>r_2=>({\lambda }_{11}-{\lambda }_{21})p(x|w_1)p(w_1)+({\lambda }_{12}-{\lambda }_{22})p(x|w_2)p(w_2)>0 \\ \frac{p(x|w_1)}{p(x|w_2)}>\frac{({\lambda }_{12}-{\lambda }_{22})p(w_2)}{({\lambda }_{11}-{\lambda }_{21})p(w_1)} \\ 分界面：d(x)=r1-r2 \end{gathered}$$

	w1	w2	------------阈值------------
p(wi|x)(max)	p(w1|x)>p(w2|x)	p(w1|x)>p(w2|x)	1
p(x|wi)p(wi)(max)	p(x|w1)p(w1) > p(x|w2)p(w2)	p(x|w1)p(w1) < p(x|w2)p(w2)	1
最小错误率$I_{12}$似然比(分割)	$I_{12}=\frac{p(x\Vert w1)}{p(x\Vert w2)}>\frac{p(w2)}{p(w1)}$	$I_{21}=\frac{p(x\Vert w1)}{p(x\Vert w2)}<\frac{p(w2)}{p(w1)}$	${\theta }_{21}=\frac{p(w2)}{p(w1)}$
条件平均风险(min)	r1(x)<r2(x)	r1(x)>r2(x)	${\theta }_{21}=\frac{p(w2)}{p(w1)}\frac{L_{21}-L_{22}}{L_{12}-L_{11}}$(L的定义和上面相反）
正态模式（ max）	d1(x)>d2(x)	d2(x)>d1(x)	$d_i(x)=lnp(w_i)-\frac{1}{2}ln\Vert C_i\Vert -\frac{1}{2}(x-m_i{)}^T{C}_i^{-1}(x-m_i)，d_1(x)-d_2(x)=0为判别界面$

朴素贝叶斯

• $$\begin{gathered} p(wi|x)=\frac{p(x|w1)p(w1)}{{\Sigma }_{i=1}^{2}p(x|wi)p(wi)} \\ p(x|w_1)={\Pi }_{i}p(x_i|w_1)--统计得到 \end{gathered}$$
  

半监督无监督

聚类

	k-均值聚类	GMM	层次聚类	基于密度的聚类
算法	随机中心，迭代更新簇中心	EM求解;E步是软划分的k-means;M步不仅估计了均值还有协方差；属于所有簇概率均等时一样	树；凝聚式，分列式	连接性，最大性的点属于簇
局限性	不同尺寸、密度、非球形不可用；扰动影响大	-	贪心（拆分和合并不可逆）；没有全局目标函数；对噪声和离群点敏感；难处理不同尺寸的簇和凸的簇；成链，误把大簇分裂	参数确定困难 ，不适合密度差异大的数据集；对变化的维度和高维数据不友好
损失函数	最小平方距离和	最小化负对数似然	没有优化一个全局的目标函数
划分	点到簇的硬划分	从属关系的软划分	层次划分,拆分合并不可逆
优点	-	-	不需要确定k,聚类结果可能对应着有意义的分类体系	不需要确定簇的数量；任意形状；对离群点稳定
超参数确定	间隔统计；交叉检验；簇的稳定性；非参数方法			eps;minPts=k:同一个簇的点，到他们k最近邻的距离相同（画出来找）
预处理	归一化；消除离群点
后处理	删除小簇；分裂远；合并近的
收敛	收敛（J单调下降）	收敛
最优	局部极小	局部极小
假设	簇是球的且每个簇的概率相等（欧式距离、质心）	簇是高斯分布，属于每个簇的概率不同，但每个簇都有可能，球或椭球形

GMM+EM+极大似然估计

• 目标函数： $L=logp(X_l,Y_l,X_u|\theta )={\Sigma }_{i=1}^{l}logp(y_i|\theta )p(x_i|y_i,\theta )+{\Sigma }_{i=l+1}^{m}log({\Sigma }_{k=1}^{N}p(y_i=k|\theta )p(x_i|y_i=k,\theta )),{\theta }_i={\alpha }_i,{\mu }_i,{\Sigma }_i$
• =Σi=1llogαyiN(xi∣θyi)+Σi=lmlogΣk=1NαkN(xi∣θk)=Σi=1l(logαyi−n2log(2π)−12log(∣Σyi∣)−(xi−μyi)TΣyi−1(xi−μyi)+Σi=lmlog(Σk=1N(αk1(2π)n/2∣Σk∣1/2exp{−12(xi−μk)TΣk−1(xi−μk)}))=\Sigma_{i=1}^llog \alpha_{y_i}N(x_i|\theta_{y_i})+\Sigma_{i=l}^mlog\Sigma_{k=1}^N\alpha_kN(x_i|\theta_k) \\=\Sigma_{i=1}^l(log\alpha_{y_i}-\frac{n}{2}log(2\pi)-\frac{1}{2}log(|\Sigma_{y_i}|)-(x_i-\mu_{y_i})^T\Sigma_{y_i}^{-1}(x_i-\mu_{y_i})+\Sigma_{i=l}^mlog(\Sigma_{k=1}^N(\alpha_k{{1} \over {(2\pi)^{n/2}|\Sigma_k|^{1/2}}} exp\{ -{{1} \over {2}}(x_i-\mu_k)^T{\Sigma_k}^{-1}(x_i-\mu_k)\}))=Σi=1l​logαyi​​N(xi​∣θyi​​)+Σi=lm​logΣk=1N​αk​N(xi​∣θk​)=Σi=1l​(logαyi​​−2n​log(2π)−21​log(∣Σyi​​∣)−(xi​−μyi​​)TΣyi​−1​(xi​−μyi​​)+Σi=lm​log(Σk=1N​(αk​(2π)n/2∣Σk​∣1/21​exp{−21​(xi​−μk​)TΣk​−1(xi​−μk​)}))
• E：$求{\gamma }_{ik}=p(y_i=k|x_i)=\frac{{\alpha }_{k}N(x_i|{\theta }_k)}{{\Sigma }_{k=1}^N{\alpha }_{k}N(x_i|{\theta }_k)}$
• M：$$\begin{gathered} {\mu }_k=\frac{1}{{\Sigma }_{i=l}^m{\gamma }_{ik}+l_k}({\Sigma }_{i\in D_l,y_i=k}{x}_i+{\Sigma }_{i=l}^m{\gamma }_{ik}{x}_i) \\ {\Sigma }_i=\frac{1}{{\Sigma }_{i=l}^m{\gamma }_{ik}+l_k}({\Sigma }_{i\in D_l,y_i=k}(x_i-{\mu }_k)(x_i-{\mu }_k{)}^T+{\Sigma }_{i=l}^m{\gamma }_{ik}(x_i-{\mu }_k)(x_i-{\mu }_k{)}^T) \\ {\alpha }_k=\frac{{\Sigma }_{i=l}^m{\gamma }_{ik}+l_k}{m} \end{gathered}$$

	有监督	无监督	半监督
目标函数	$$\begin{gathered} L=logp(X_l,Y_l\Vert \theta )={\Sigma }_{i=1}^{l}logp(y_i\Vert \theta )p(x_i\Vert y_i,\theta ) \\ ={\Sigma }_{i=1}^{l}log{\alpha }_{y_i}N(x_i\Vert {\theta }_{y_i}) \end{gathered}$$	$p(x;\theta )={\Pi }_i^N{\Sigma }_{k=1}^K{\pi }_{k}N(x_i\Vert {\mu }_k,{\Sigma }_k)$	$P(x_l,y_l,x_u\Vert \theta )={\Sigma }_{i=1}^{l}log{\alpha }_{y_i}N(x_i\Vert {\theta }_{y_i})+{\Sigma }_{i=l}^{m}log{\Sigma }_{k=1}^N{\alpha }_{k}N(x_i\Vert {\theta }_k)$
E	求导解决	$求{\gamma }_{ik}=p(y_i=k\Vert x_i)=\frac{{\alpha }_{k}N(x_i\Vert {\theta }_k)}{{\Sigma }_{k=1}^N{\alpha }_{k}N(x_i\Vert {\theta }_k)}$	$求{\gamma }_{ik}=p(y_i=k\Vert x_i)=\frac{{\alpha }_{k}N(x_i\Vert {\theta }_k)}{{\Sigma }_{k=1}^N{\alpha }_{k}N(x_i\Vert {\theta }_k)}$
M	$$\begin{gathered} {\mu }_k=\frac{1}{l_k}({\Sigma }_{i\in D_l,y_i=k}{x}_i) \\ {\Sigma }_i=\frac{1}{l_k}({\Sigma }_{i\in D_l,y_i=k}(x_i-{\mu }_k)(x_i-{\mu }_k{)}^T) \\ {\alpha }_k=\frac{l_k}{m} \end{gathered}$$	$$\begin{gathered} {\mu }_k=\frac{{\Sigma }_i\gamma (z_{ik})x_i}{\gamma (z_{ik})} \\ {\pi }_k=\frac{{\Sigma }_i\gamma (z_{ik})}{N} \\ {\Sigma }_k=\frac{{\Sigma }_i\gamma (z_{ik})(x_i-{\mu }_k)(x_i-{\mu }_k{)}^T}{\gamma (z_{ik})} \end{gathered}$$	$$\begin{gathered} {\mu }_k=\frac{1}{{\Sigma }_{i=l}^m{\gamma }_{ik}+l_k}({\Sigma }_{i\in D_l,y_i=k}{x}_i+{\Sigma }_{i=l}^m{\gamma }_{ik}{x}_i) \\ {\Sigma }_i=\frac{1}{{\Sigma }_{i=l}^m{\gamma }_{ik}+l_k}({\Sigma }_{i\in D_l,y_i=k}(x_i-{\mu }_k)(x_i-{\mu }_k{)}^T+{\Sigma }_{i=l}^m{\gamma }_{ik}(x_i-{\mu }_k)(x_i-{\mu }_k{)}^T) \\ {\alpha }_k=\frac{{\Sigma }_{i=l}^m{\gamma }_{ik}+l_k}{m} \end{gathered}$$
			半监督=无监督+有监督

• 分析高斯混合模型和k-means的异同
  • ;E步是软划分的k-means;M步不仅估计了均值还有协方差；属于所有簇概率均等时两者等价

判别函数

线性判别和非线性判别

• 试阐述线性判别和非线性判别的基本概念，并说明为何有了线性判别还要有非线性判别？假设有两类模式，每类模式有5个3维特征的样本，且良好分布，问线性可分情况下权重需要多少系数分量？假如需要建立二次多项式判别函数，需要多少系数分量？
  • 线性判别：以线性函数为判别函数的模式分类
  • 非线性判别：使用非线性函数作为判别函数的模式分类
  • 因为存在线性不可分的模式，无法用线性判别函数进行模式分类
  • $C_{n+r}^r:n维数据，采用r次多项式的参数个数$
  • $$\begin{gathered} 线性可分：C_4^1=4 \\ 二次：C_{3+2}^2=10 \end{gathered}$$

线性判别函数的数量（M分类

• 情况1：分为自己和其他所有：M个判别函数
• 情况2：分为i和j类：M(M-1)/2个判别函数
• 情况3：M个

	想法	…判别函数…	…判别…	优点	缺点
二分类	区分为${\omega }_1和{\omega }_2$（不是1就是2）	$$\begin{gathered} d(x)=w_1{x}_1+w_2{x}_2+w_3=0， \\ 1个 \end{gathered}$$	$$\begin{gathered} d(x)>0x\in {\omega }_1; \\ d(x)<0x\in {\omega }_2 \end{gathered}$$	—	—
M分类1	区分为${\omega }_1和非{\omega }_1$	$$\begin{gathered} d_i(x)=w_1{x}_1+w_2{x}_2+w_3{x}_3+...+w_n{x}_n+w_{n+1}=w^{T}x+w_{n+1}=0， \\ M个 \end{gathered}$$	$$\begin{gathered} d_i(x)>0 \\ 且d_j(x)<0, \\ i\ne j, \\ ifx\in {\omega }_i \end{gathered}$$	简单	线性可分性差，IR区域最大
M分类2	区分为${\omega }_i和{\omega }_j$,一对一对的分	$$\begin{gathered} d_{ij}(x)=w_1{x}_1+w_2{x}_2+w_3{x}_3+...+w_n{x}_n+w_{n+1}=w^{T}x+w_{n+1}=0， \\ {d}_{ij}(x)=-d_{ji}(x); \\ M(M-1)/2个 \end{gathered}$$	$$\begin{gathered} d_{ij}(x)>0 \\ 且i\ne j,,任意j, \\ ifx\in {\omega }_i \end{gathered}$$	简单	线性可分性差，IR区域小，判别函数太多
M分类3_1	区分为${\omega }_i和{\omega }_j$,一对一对的分	$$\begin{gathered} d_{ij}(x)=d_i(x)-d_j(x)， \\ {d}_{ij}(x)=-d_{ji}(x); \\ M个d_i(x),M(M-1)/2个判别面 \end{gathered}$$	$$\begin{gathered} d_{ij}(x)>0 \\ 且i\ne j,,任意j, \\ ifx\in {\omega }_i \end{gathered}$$	无IR	线性可分性差，IR区域无
M分类3_2	区分为${\omega }_i和{\omega }_j$,一对一对的分	$$\begin{gathered} d_{ij}(x)=d_i(x)-d_j(x)， \\ {d}_{ij}(x)=-d_{ji}(x); \\ M个d_i(x),M(M-1)/2个判别面 \end{gathered}$$	$$\begin{gathered} d_i(x)>d_j(x) \\ 且i\ne j,任意j, \\ ifx\in {\omega }_i \end{gathered}$$	无IR	线性可分性差，IR区域无
非线性f(x)	核函数：非线性x–>线性的x*=f(x)	-	-	从非线性变成了线性	|x|<|x*|
非线性分段判别函数	分段函数逼近曲线	-	-	从非线性变成了线性	-
最小距离分类	分段函数逼近曲线	$$\begin{gathered} d(x)=\Vert x-{\mu }_1{\Vert }^2-\Vert x-{\mu }_2{\Vert }^2， \\ \mu 为各类中心 \end{gathered}$$	$$\begin{gathered} d(x)>0x\in {\omega }_1; \\ d(x)<0x\in {\omega }_2 \end{gathered}$$	从非线性变成了线性	-
模式空间与权空间	模式空间w为面/线的法向量； 权空间x为法向量	$d(x)=w^{T}x=0$	$$\begin{gathered} 法向量方向为正的方向，d(x)>0x\in {\omega }_1; \\ d(x)<0x\in {\omega }_2 \end{gathered}$$	-	-
Fisher准则函数（降维,找$J_F(w)=\frac{(m_1(y)-m_2(y){)}^2}{S_1^2(y)+S_1^2(y)}$最大的w）	d维空间–>1维且仍可分，$y_n=w^T{x}_n$;找类间距离大，类内距离小的最佳投影方向；	$d(y_n)=T(阈值)$	$d(y_n)>Tx\in {\omega }_1;d(y_n)<Tx\in {\omega }_2$	降维	-
决策树	二叉树，每个特征分一次	符合特征就专项分支	到哪个叶子，就是哪一类	概念简单、直观、便于解释，可用先验知识	不易得到最优

感知机

• 描述感知机模型，并给出权值学习算法。在此基础上，以仅有一个隐含层的三层神将网络为例，形式化描述BP算法中是如何对隐含层和神经元之间的连接权重调整的。
  • 感知机模型：$y=W^{T}x,>0分为w1类，<0分为w2类；分错：W_{t+1}=W_t+y_i\ast x_i，分对了：W_{t+1}=W_t$
    

势函数法

9.势函数法（非线性）

• 一个样本一个势函数
• 计算积累位势函数K(x)
  • $x_{k+1}\in {\omega }_1：K_k(x_{k+1})<0$则分错了：修改K(x)
  • $x_{k+1}\in {\omega }_1：K_k(x_{k+1})>0$正确，不变
• 初始化$K_1(x)=$
  • $K(x,x_1),x_1\in {\omega }_1$
  • $-K(x,x_1),x_1\in {\omega }_2$
• 迭代
  • 分错：
    • $K_{k+1}(x)=K_k(x)+K(x,x_{k+1}),x_{k+1}\in {\omega }_1$
    • $K_{k+1}(x)=K_k(x)-K(x,x_{k+1}),x_{k+1}\in {\omega }_2$
  • 正确：
    • 不变
• $x=(x_1,x_2{)}^T,x_k=(x_{k_1}，x_{k_2}{)}^T$
• 如何选择势函数
  1. K(x,xk)=K(xk,x)<==>当且仅当x=xk时最大
  2. x距离xk越远越小，无穷远则趋于0
  3. 光滑的，x距离xk越远越小

9.1Hermite

• Hermite多项式
  • $H_0(x)=1$
  • $H_1(x)=2x$——一次多项式的K取到这里
  • $H_2(x)=4x^2-2$————二次多项式的K取到这里
• 建立二维正交函数集：（一次的，前两项排列组合
  • ${\varphi }_1(x)={\varphi }_1(x_1,x_2)=H_0(x_1)H_0(x_2)=1$
  • ${\varphi }_2(x)={\varphi }_2(x_1,x_2)=H_1(x_1)H_0(x_2)=2x_1$
  • ${\varphi }_3(x)={\varphi }_3(x_1,x_2)=H_0(x_1)H_1(x_2)=2x_2$
  • ${\varphi }_4(x)={\varphi }_4(x_1,x_2)=H_1(x_1)H_1(x_2)=4x_1{x}_2$
• $K(x,x_k)={\Sigma }_{i=1}^4{\varphi }_i(x){\varphi }_i(x_k)=1+4x_1{x}_{k_1}+4x_2{x}_{k_2}+16x_1{x}_{k_1}{x}_2{x}_{k_2}$
  • 对样本$x_1=(1,0{)}^T:K_1(x)=K_1(x,x_1)=1+4x_1$——xk=x1
  • $x_2=(0,-1{)}^T{K}_1(x_2,x_1)=1>0,分对了，所以K_2(x)=K_1(x)$——看是否分对的时候x=x2
  • 二次hermit
    

9.2z第二种：指数势函数

• $K(x,x_k)=exp(-\alpha \Vert x-x_k{\Vert }^2)$
  • 二维$\alpha =1,K(x,x_k)=exp(-((x_1-x_{k_1}{)}^2+(x_2-x_{k_2}{)}^2))$

偏差方差分解过程

• 偏差-方差分解
  • $expectedloss=bia{s}^2+variance+noise$
  • expectedloss=E(fD)=∫∫(fD(x)−y)2p(x,y)dxdy={∫(fD(x)−h(x))2p(x)dx+∫∫(h(x)−y)2p(x,y)dxdy}=(ED(fD(x))−h(x))2+ED(fD(x)−ED(fD(x)))2+∫∫(h(x)−y)2p(x,y)dxdyexpected loss=E(f_D)= \int \int (f_D(x)-y)^2p(x,y)dxdy\\=\{\int (f_D(x)-h(x))^2p(x)dx+\int \int (h(x)-y)^2p(x,y)dxdy\}\\=(E_D(f_D(x))-h(x))^2+E_D(f_D(x)-E_D(f_D(x)))^2+\int \int (h(x)-y)^2p(x,y)dxdyexpectedloss=E(fD​)=∫∫(fD​(x)−y)2p(x,y)dxdy={∫(fD​(x)−h(x))2p(x)dx+∫∫(h(x)−y)2p(x,y)dxdy}=(ED​(fD​(x))−h(x))2+ED​(fD​(x)−ED​(fD​(x)))2+∫∫(h(x)−y)2p(x,y)dxdy
  • $bias=E_D(f_D(x))-h(x)，预测结果的均值和最优解的差别$
    • 模型越复杂，偏差越小
  • $variance=E_D(f_D(x)-E_D(f_D(x)){)}^2,预测的结果自己和自己均值的差别$
    • 模型越复杂，方差越大
  • $noise=\int \int (h(x)-y{)}^{2}p(x,y)dxdy$ --不论如何也解决不了的部分，不用管了
  • $E_D(f_D(x))={\bar{f}}_D(x)$
    

降维PCA

• $$\begin{gathered} X1=\left(\begin{array}{ccccc}-5& -5& -4& -5& -6\\ -5& -4& -5& -6& -5\end{array}\right) \\ X2=\left(\begin{array}{ccccc}5& 5& 6& 5& 4\\ 5& 6& 5& 4& 5\end{array}\right) \\ M1=(-5,-5{)}^T;M2=(5,5{)}^T;M1+M2=0不用变化 \\ C=P(w_1)X1X{1}^T/5+P(w_2)X2X{2}^T/5=0.5\left(\begin{array}{cc}25.4& 25\\ 25& 25.4\end{array}\right)+0.5\left(\begin{array}{cc}25.4& 25\\ 25& 25.4\end{array}\right)=\left(\begin{array}{cc}25.4& 25\\ 25& 25.4\end{array}\right) \\ C=W\Sigma W^T=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}-1& 1\\ 1& 1\end{array}\right)\left(\begin{array}{cc}0.4& 0\\ 0& 50.4\end{array}\right)\frac{1}{\sqrt{2}}{\left(\begin{array}{cc}-1& 1\\ 1& 1\end{array}\right)}^T \\ W=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}-1& 1\\ 1& 1\end{array}\right) \\ 取W^{\prime }=\frac{1}{\sqrt{2}}(1,1{)}^T \\ Z1=W^{T}X1=\frac{1}{\sqrt{2}}(1,1)\left(\begin{array}{ccccc}-5& -5& -4& -5& -6\\ -5& -4& -5& -6& -5\end{array}\right)=\frac{1}{\sqrt{2}}\left(\begin{array}{ccccc}-10& --9& -9& -11& -11\end{array}\right) \\ Z1=W^{T}X1=\frac{1}{\sqrt{2}}(1,1)\left(\begin{array}{ccccc}5& 5& 6& 5& 4\\ 5& 6& 5& 4& 5\end{array}\right)=\frac{1}{\sqrt{2}}\left(\begin{array}{ccccc}10& 11& 11& 9& 9\end{array}\right) \end{gathered}$$

• 思想：最小化重构误差

• 算法：(不区分类别）

  1. 均值化为0：$x_i=x_i-\frac{1}{m}{\Sigma }_{j=1}^m{x}_j---这是所有样本的均值，若有多类，则是多类样本均值之和$
  2. 计算$X{X}^T$
  3. 对$C=E(X{X}^T)$特征分解(SVD取U)(C-协方差）
  4. 取前d‘个特征向量：$W=(w_1,w_2,...,w_{d^{\prime }})$
  5. $z=W^{T}x$

• 算法：(区分类别）

  1. 均值化为0：$x_i=x_i-m,m=m_1+m_2---这是所有样本的均值，若有多类，则是多类样本均值之和，$
  2. 计算$X{X}^T$
  3. 对$C=p(w_1)E(X_1{X}_1^T)+p(w_2)E(X_2{X}_2^T)=V\Sigma V^T,V的列向量为特征向量W=V，V^{T}CV=\Sigma$特征分解(SVD取U)(C-协方差）
  4. 取前d‘个特征向量：$W=(w_1,w_2,...,w_{d^{\prime }}),w_i为列向量-特征向量$
  5. $z=W^{T}x,x是均值归0后的$

• PCA优化目标

  • 最小化重构误差
  • PCA能够获取互不相关的新特征。采用较大特征值对应的特征向量变换，则能保留元模式中方差最大的特征部分，所以K-L变换起到了减小相关性，突出差异性的效果==KL变换

SVM

	原问题	拉格朗日	对偶问题	分界面	最终参数
hard margin	$mi{n}_w\frac{1}{2}\Vert w{\Vert }^2$约束$y^i(w^T{x}^i)>=1,对任意i$	$L({\lambda }_i,w,b)={\Sigma }_{i=1}^N{\lambda }_i(1-y^i(w^T{x}^i+b){)}_{+}+\frac{1}{2}\Vert w{\Vert }^2$	$ma{x}_{\lambda }{\theta }_D(\lambda )={\Sigma }_{i=1}^n{\lambda }_i-\frac{1}{2}{\Sigma }_{i,j=1}^n{y}^i{y}^j{\lambda }_i{\lambda }_j(x^i{)}^T{x}^j$约束：${\lambda }_i>=0;{\Sigma }_{i=1}^n{\lambda }_i{y}^i=0$	$b\ast +{\Sigma }_{i=1}^n{\lambda }_i\ast y^i(x^i{)}^T{x}^j=0$	$w\ast ={\Sigma }_{i=1}^n{\lambda }_i\ast y^i{x}^i;b\ast =y^j-{\Sigma }_{i=1}^n{\lambda }_i\ast y^i(x^i{)}^T{x}^j$
soft	$mi{n}_w\frac{1}{2}\Vert w{\Vert }^2+C{\Sigma }_{i=1}^n{\xi }_i$约束$y^i(w^T{x}^i)>=1-{\xi }_i,{\xi }_i\ge 0,对任意i$	$L({\lambda }_i,{\eta }_i,\xi ,w,b)={\Sigma }_{i=1}^N{\lambda }_i(1-y^i(w^T{x}^i+b)-{\xi }_i)-{\Sigma }_{i=1}^n{\eta }_i{\xi }_i+\frac{1}{2}\Vert w{\Vert }^2$	$ma{x}_{\lambda }{\theta }_D(\lambda )={\Sigma }_{i=1}^n{\lambda }_i-\frac{1}{2}{\Sigma }_{i,j=1}^n{y}^i{y}^j{\lambda }_i{\lambda }_j(x^i{)}^T{x}^j$ 约束：$0\le {\lambda }_i\le C={\lambda }_i+{\eta }_i({\eta }_i>=0);{\Sigma }_{i=1}^n{\lambda }_i{y}^i=0$	$b\ast +{\Sigma }_{i=1}^n{\lambda }_i\ast y^i(x^i{)}^T{x}^j=0$	$w\ast ={\Sigma }_{i=1}^n{\lambda }_i\ast y^i{x}^i;b\ast =y^j-{\Sigma }_{i=1}^n{\lambda }_i\ast y^i(x^i{)}^T{x}^j$
kernel	-	-	${\theta }_D(\lambda )={\Sigma }_{i=1}^n{\lambda }_i-\frac{1}{2}{\Sigma }_{i,j=1}^n{y}^i{y}^j{\lambda }_i{\lambda }_{j}K(x^i,x^j)$约束：${\lambda }_i>=0;{\Sigma }_{i=1}^n{\lambda }_i{y}^i=0$	$$\begin{gathered} w\ast ={\Sigma }_{i=1}^n{\lambda }_i\ast y^i{x}^i \\ b\ast =y^j-{\Sigma }_{i=1}^n{\lambda }_i\ast y^{i}K(x^i,x^j) \end{gathered}$$

• SMO
  • 每次对一对，其他n-2个固定：${\lambda }_1{y}^1+{\lambda }_2{y}^2=-{\Sigma }_{i=3}^N{\alpha }_i{y}^i=C$
    • ${\lambda }_1=(C-{\lambda }_2{y}^2)y^1$
    • $L((C-{\lambda }_2{y}^2)y^1,{\lambda }_2,...,{\lambda }_N），先忽略约束求导，得到{\lambda }_2^{new,unclipped}，再加上约束$
    • $用{\lambda }_2更新{\lambda }_1:{\lambda }_1^{new}={\lambda }_1^{old}({\lambda }_2^{old}-{\lambda }_2^{new})y^2{y}^1$
  • 从那一对开始呢？

神经网络

人工神经网络

1. 定义
   所谓人工神经网络就是基于模仿生物大脑的结构和功能而构成的一种信息处理系统（计算机）。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。由于我们建立的信息处理系统实际上是模仿生理神经网络，因此称它为人工神经网络。
2. 特点
   • 固有的并行结构和并行处理；
   • 知识的分布存储；
   • 容错性；
   • 自适应性；

• 人工神经网络也有其局限性（
  • 不适于高精度的计算、
  • 不适于类似顺序计数的工作、
  • 学习和训练是一个艰难的过程、
  • 必须克服时间域顺序处理方面的困难、
  • 硬件限制、
  • 正确的训练数据的收集）。

3. 考虑因素
   要基于应用的要求和人工神经网络模型的能力间的匹配，主要考虑因素包括：
   网络大小、所需输出类型、联想记忆类型、训练方法、时间的限定。

why deep

1. 深层结构能够有效地表达
   1. 对相同函数需要更少的计算单元
   2. 高层可以综合利用低层信息
2. 深层结构产生层次化的特征表达
   1. 可解释性，更有语义化信息
3. 多层隐变量允许统计上的组合共享
4. 有效

BP：

CNN

• CNN基本操作的含义
• 卷积层： 检测某种特异性特征，不同的权值组合检测不同的特征，通过局部连接，参数共享降低参数数量
• 池化层：平移不变性和旋转不变性（下采样+降维）
• 激活函数（RELU）层： 非线性。
• 多层：层级性

特征提取方式的变更（目标检测）