首页 机器学习

模式识别复习总结

# 前情提要：

本篇只适合与考试复习用，并不深入讲解每个算法的具体内容，详细知识点请移步本分类的其他文章

模式识别思维导图

# 一、距离分类器

  • 模板匹配

    • dd 是向量xx 和平均值μi\mu_i 的距离

    • j=arg⁡min⁡1≤i≤cd(x,μi)j=\arg\min_{1\le i\le c}d(\boldsymbol{x},\boldsymbol{\mu}_i)

  • 最近邻分类器

    • 计算每个类别训练样本的均值作为匹配模板

  • K - 近邻分类器

    • 如果j=arg⁡max⁡1≤i≤cki，则判别:x∈wj如果j=\arg\max_{1\le i\le c}k_i，则判别:x\in w_j

  • 距离和相似度度量：

    • 什么样的函数可以作为距离度量

      • 非负性、对称性、自反性、三角不等式

    • 常用函数

      • EuclideanEuclidean DistanceDistance:\sqrt
      • ManhattanManhattan DistanceDistance:∣x1−x2∣+∣y1−y2∣|x_1-x_2|+|y_1-y_2|
      • ChebyshevDistanceChebyshev Distance:max(∣x1−x2∣,∣y1−y2∣)max(|x_1-x_2|,|y_1-y_2|)

    • 相似性度量

      • 角度相似性：

        s(x,y)=cosθxy=xty∥x∥⋅∥y∥s(\boldsymbol{x},\boldsymbol{y})=cos\theta_{xy}=\dfrac{x^ty}{\lVert x\rVert\cdot\lVert y\rVert}

      • 相关系数：

        s(x,y)=(x−μx)t(y−μy)∥x−μx∥⋅∥y−μy∥s(\boldsymbol{x},\boldsymbol{y})=\dfrac{(x-\mu_x)^t(y-\mu_y)}{\lVert x-\mu_x\rVert\cdot\lVert y-\mu_y\rVert}

    • 特征归一化、标准化

      • 均匀缩放：xij′=xij−xjminxjmax−xjmin,i=1,...,n,j=1,...,dx^\prime_{ij}=\dfrac{x_{ij}-x_{jmin}}{x_{jmax}-x_{jmin}},i=1,...,n,j=1,...,d

      • 高斯缩放：xij′=xij−μjsj,i=1,...,n,j=1,...,dx^\prime_{ij}=\dfrac{x_{ij}-\mu_j}{s_j},i=1,...,n,j=1,...,d

      • 缩放的理由：使样本每一维特征都分布在相同或相似的范围内，计算距离度量时每一维特征上的差异都会得到相同的体现

  • 分类器性能评价：

    • 常用评价指标

      • 准确率：Acc=(TP+TN)/(TP+FN+FP+TN)Acc=(TP+TN)/(TP+FN+FP+TN)

      • 错误率：Err=1−AccErr=1-Acc

      • 查准率：P=TP/(TP+FP)P=TP/(TP+FP)

      • 查全率 (召回率)：R=TP/(TP+FN)R=TP/(TP+FN)

      • F1:F1=(2∗P∗R)/(P+R)F_1:F_1=(2*P*R)/(P+R)

        真实类别 \ 预测结果正例反例
        正例TP (真正例)FN (假反例)
        反例FP (假正例)TN (真反例)

    • 常用评价方法：

      • 留出法 (hold-out)
      • 交叉验证法 (cross validation)
      • 自助法 (bootstrap)

    • 偏差 (Bias) 和方差 (Variance)

    • 过拟合与欠拟合 (Over- and Under-Fitting)

      • 如何解决欠拟合:

        1、增加模型复杂数学公式度，即选择更复杂数学公式的模型

        2、特征工程，即选择更好的有助于模型预测的特征

        3、调整超参数

      • 如何解决过拟合：

        1、增加训练数据量

        2、降低模型复杂数学公式度

        3、通过正则化的方法，限制模型参数大小

        4、数据增强，通过对训练数据旋转、翻转，增加样本多样性

# 二、线性判别函数

线性判别函数：g(x)=wtx+w0=0g(x)=\boldsymbol{w}^t\boldsymbol{x}+w_0=0

  • 线性判别函数的几何意义

    • 分类超平面HH 将空间分成属于不同类别的两部分R1R_1 和R2R_2
    • 权矢量w\boldsymbol{w} 垂直与分类面HH，指向g(x)>0g(x)>0 的区域
    • 坐标原点到分类界面HH 的距离：r0=w0∥w∥r_0=\dfrac{w_0}{\lVert\boldsymbol{w}\rVert}

  • 线性判别函数的增广形式：

    • 增广权矢量：a=[wt,w0]t\boldsymbol{a}=[\boldsymbol{w}^t,\boldsymbol{w_0}]^t

    • 样本规范化：

      {y=[xt,1]t,∀x∈ω1y=[−xt,−1]t,∀x∈ω2\begin{cases} \boldsymbol{y}=[ \boldsymbol{x}^t,1]^t,& \forall \boldsymbol{x} \in \boldsymbol{\omega_1} \\ \boldsymbol{y}=[ \boldsymbol{-x}^t,-1]^t,& \forall \boldsymbol{x} \in \boldsymbol{\omega_2} \end{cases}

    • 统一形式：atyi>0,i=1,...,n\boldsymbol{a}^t\boldsymbol{y_i}>0,i=1,...,n

  • 优化方法 - 梯度下降法：α(k+1)=α(k)−η(k)∇J(a(k))\alpha(k+1)=\alpha(k)-\eta(k)\nabla J(a(k))

  • 感知器算法：

    JP(α)=∑y∈y−g(y)=∑y∈y−αtyJ_P(\alpha)=\sum_{y\in\mathcal{y}}-g(y)=\sum_{y\in\mathcal{y}}-\alpha^ty

    ∇JP(α)=∑y∈y−y\nabla J_P(\alpha)=\sum_{y\in\mathcal{y}}-y

  • 最小平方误差算法：

    JS(α)=∥Ya−b∥2J_S(\alpha)=\lVert Ya-b\rVert^2 ∇JS(a)=2Yt(Ya−b)\nabla J_S(a)=2Y^t(Ya-b)

    伪逆法：Y+=(YtY)−1YtY^+=(Y^tY)^{-1}Y^t((YtY)(Y^tY) 可能为奇异阵，且计算量巨大)

    迭代求解法：α(k+1)=α(k)+η(k)∑i=1n(bi−atyi)yi\alpha(k+1)=\alpha(k)+\eta(k)\sum\limits_{i=1}^n(b_i-a^ty_i)y_i

多类别线性分类：

  • 方法：一对多、一对一
  • 判别准则：
    • 若存在ii，使得gi(x)>0,gi(x)<0,j≠ig_i(x)>0,g_i(x)<0,j\neq i，则判别xx 属于ωi\omega_i 类
    • 如果对任意j≠ij\neq i，有gij(x)>0g_{ij}(x)>0，则判别xx 属于ωi\omega_i 类

支持向量机：

min⁡w,w012∥w∥2subjectto:zi(wtxi+w0)≥1,i=1,...n\min_{\boldsymbol{w},w_0}\frac{1}{2}\lVert w\rVert^2\\subject\ to:\qquad z_i(\boldsymbol{w}^t\boldsymbol{x}_i+w_0)\ge1,\ i=1,...n

  • 权矢量：w=∑i=1nαizixi\boldsymbol{w}=\sum\limits^{n}_{i=1}\alpha_iz_i\boldsymbol{x}_i

  • 偏置w0w_0：可以用支持向量满足的条件求得zi(wtxi+w0)=1z_i(\boldsymbol{w}^t\boldsymbol{x}_i+w_0)=1

  • 软间隔SVMSVM:

    {zi(wtxi+w0)>0,αi=0支持面外zi(wtxi+w0)=1,0<αi<C支持面上zi(wtxi+w0)<1,αi=C支持面内\begin{cases}z_i(w^tx_i+w_0)>0,&\alpha_i=0\quad\quad\quad支持面外\\z_i(w^tx_i+w_0)=1,&0<\alpha_i<C\quad支持面上\\z_i(w^tx_i+w_0)<1,&\alpha_i=C\quad\quad\quad支持面内\end{cases}

特征选择与特征提取：

  • 什么是维数诅咒：当数学空间维度增加时，体积指数级增加的难题

  • 主成分分析 (PCA)

    • Input: 样本集D={x1,...,xn},xi∈RdD=\{x_1,...,x_n\},x_i\in R^d;

    • Output: 降维样本集\{y_1,...,y_2\},y_i\in R^

    • 1: 计算样本集DD 的均值μ\boldsymbol{\mu} 和协方差矩阵SS;

    • 2: 计算矩阵SS 的特征值，并从大到小排序；

    • 3: 选择前d′d^\prime 个特征值对应矢量作为列矢量，构造变换矩阵E=(e1,...,ed′)E=(e_1,...,e_{d^\prime});

    • 4: 计算降维样本集：yi=Et(xi−μ),i=1,...ny_i=E^t(x_i-\mu),\quad i=1,...n

  • 线性判别分析：

    • FisherFisher 准则：J(w)=(μ~1−μ~2)2s~12+s~22=wtSbwwtSwwJ(\boldsymbol{w})=\dfrac{(\tilde{\mu}_1-\tilde{\mu}_2)^2}{\tilde{s}_1^2+\tilde{s}_2^2}=\dfrac{\boldsymbol{w}^t\boldsymbol{S}_b\boldsymbol{w}}{\boldsymbol{w}^t\boldsymbol{S}_w\boldsymbol{w}}
    • Sw=∑i=12∑x∈Di(x−μi)(x−μi)tS_w=\sum\limits_{i=1}^2\sum\limits_{x\in D_i}(x-\mu_i)(x-\mu_i)^t
    • Sb=(μ1−μ2)(μ1−μ2)tS_b=(\mu_1-\mu_2)(\mu_1-\mu_2)^t

  • PCA vs LDA:

    • PCA: 无监督的成分分析方法，只考虑了样本集的整体分布，没有使用样本的类别信息
    • LDA: 有监督的成分分析方法，根据 Fisher 准则寻找可分性最大意义的最优线性映射，充分保留样本的类别可分性信息

# 三、贝叶斯决策理论

P(ωi∣x)=p(x∣ωi)p(ωi)p(x)(posterior=likelihood×priorevidence)P(\omega_i|x)=\dfrac{p(x|\omega_i)p(\omega_i)}{p(x)}(posterior=\dfrac{likelihood\times prior}{evidence})

  • 基于最小错误率的贝叶斯决策：

    • 最大后验概率：i=argmax⁡1≤j≤cP(ωj∣x),thenx∈ωii=arg\max_{1\le j\le c}P(\omega_j|x),\quad then\ x\in\omega_i

  • 基于最小风险的贝叶斯决策

    • 将xx 判为ωj\omega_j 类的平均风险：γj(x)=∑i=1cλijP(ωi∣x)\gamma_j(x)=\sum\limits_{i=1}^c\lambda_{ij}P(\omega_i|x)
    • 最小平均风险准则：i=arg⁡max⁡1≤j≤c−γj(x),thenx∈ωii=\arg\max_{1\le j\le c}-\gamma_j(x),\quad then\ x\in\omega_i

正态分布的贝叶斯分类器：

  • 假设每个类别的类条件概率密度函数p(x∣ωi)p(x|\omega_i) 都满足正态分布

    p(x)=1(2π)d2∣Σ∣12exp[−12(x−μ)tΣ−1(x−μ)]p(x)=\dfrac{1}{(2\pi)^{\frac{d}{2}}|\Sigma|^{\frac{1}{2}}}exp[-\frac{1}{2}(x-\mu)^t\Sigma^{-1}(x-\mu)]

  • 最小错误率贝叶斯函数的对数表示：

    gi(x)=lnp(x∣ωi)+lnP(ωi)g_i(x)=ln\ p(x|\omega_i)+ln\ P(\omega_i)

  • 情况一:P(ωi)=1/c,Σi=σ2IP(\omega_i)=1/c,\Sigma_i=\sigma^2\bold{I} 距离分类器

  • 情况二:Σi=Σ\Sigma_i=\Sigma 线性分类器

  • 情况三:Σi\Sigma_i 任意 二次判别函数

朴素贝叶斯分类器：

  • 协方差矩阵难以估计

  • 假设样本的各位特征相互独立

    p(x∣ωi)=∏j=1dp(xj∣ωi)=∏j=1d{12πσijexp[−(xj−μij)22σij2]}p(x|\omega_i)=\prod\limits_{j=1}^dp(x_j|\omega_i)=\prod\limits_{j=1}^d\{\dfrac{1}{\sqrt{2\pi}\sigma_{ij}}exp[-\dfrac{(x_j-\mu_{ij})^2}{2\sigma_{ij}^2}]\}

    gi(x)=lnP(ωi)−∑j=1dlnσij−∑j=1d(xj−μij)22σij2g_i(x)=ln\ P(\omega_i)-\sum\limits_{j=1}^dln\sigma_{ij}-\sum\limits_{j=1}^d\dfrac{(x_j-\mu_{ij})^2}{2\sigma_{ij}^2}

# 三、非参数估计和参数估计

非参数估计 vs 参数估计：

  • 非参数估计不需要任何关于分布的先验知识，适用性好；参数估计方法需要关于分布形式的先验知识，估计的准确程度依赖于先验知识是否准确
  • 非参数估计能取得的准确的估计结果，需要的训练样本数量远多于参数估计；参数估计由于有先验知识的存在，参数估计方法使用比较少的训练数据就可以得到较好的估计结果

非参数估计：

  • Parzen 窗法：区域体积VV 是总样本数nn 的函数，如:Vn=1nV_n=\dfrac{1}{\sqrt{n}}

    • 窗函数条件：

      • 满足以下函数：φ(u)≥0,∫φ(u)du=1\varphi(u)\ge0,\int\varphi(\boldsymbol{u})d\boldsymbol{u}=1
      • 最常使用窗函数 Gauss 函数：φ(x−xihn)=1(hn2π)dexp(−∥x−xi∥22hn2)\varphi(\dfrac{x-x_i}{h_n})=\dfrac{1}{(h_n\sqrt{2\pi})^d}exp(-\dfrac{\lVert x-x_i\rVert^2}{2h_n^2})

    • 判断样本xix_i 是否在超立方体RR 内：

      φ(xi−xhn)={1,xi∈R0,xi∉R\varphi(\dfrac{x_i-x}{h_n})=\begin{cases}1, & x_i\in R \\ 0, & x_i\notin R\end{cases}

    • 超立方体内的样本数：kn=∑i=1nφ(x−xihn)k_n=\sum_{i=1}^n\varphi(\dfrac{x-x_i}{h_n})

    • 概率密度函数的估计：p(x)≈k/nV=1n∑i=1n1Vnφ(x−xihn)p(x)\approx\dfrac{k/n}{V}=\dfrac{1}{n}\sum_{i=1}^n\dfrac{1}{V_n}\varphi(\dfrac{x-x_i}{h_n})

    • Input: 训练集DD，窗函数φ(x)\varphi(x)，窗函数宽度hh

    • Output: 待识别模式xx 所属类别

    • 1: 保存每个类别的训练样本集Di={x1i,...,xnii}D_i=\{x_1^i,...,x^i_{n_i}\};

    • 2:for i=1i=1 to cc do

    • 3: 计算ωi\omega_i 类的概率密度函数值：

    • p(x∣ωi)=1ni∑j=1ni1Vnφ(x−xjh)p(x|\omega_i)=\dfrac{1}{n_i}\sum\limits_{j=1}^{n_i}\dfrac{1}{V_n}\varphi(\dfrac{x-x_j}{h})

  • K - 临近法：落在区域内的样本数kk 是总样本数nn 的函数，如:k_n=\sqrt

    • Input: 训练集D={x1,...,xn}D=\{x_1,...,x_n\}，参数kk
    • Output: 待识别模式xx 所属类别
    • 1：计算待识别模式与每个训练样本的距离：D(x,xi)D(x,x_i)
    • 2：选择距离最小的前kk 个样本，统计其中包括各个类别的样本数kjk_j；
    • 3：return argmax⁡1≤j≤c[kj]arg\max_{1\le j\le c}[k_j]

参数估计：

  • 最大似然估计：

    p(D∣θ)=p(x1,x2,...,xn∣θ)=∏i=1np(xi∣θ)p(D|\theta)=p(x_1,x_2,...,x_n|\theta)=\prod\limits_{i=1}^np(x_i|\theta)

    • 对数似然函数：l(θ)=lnp(D∣θ)=∑i=1nlnp(xi∣θ)l(\theta)=ln\ p(D|\theta)=\sum_{i=1}^nln\ p(x_i|\theta)
    • 求解优化问题：θ^=arg⁡max⁡θl(θ)\hat\theta=\arg\max_\theta l(\theta)
    • ∇θl(θ)=0\nabla_\theta l(\theta)=0
    • 一维正态分布的最大似然估计：μ^=1n∑i=1nxi\hat\mu=\frac{1}{n}\sum\limits_{i=1}^nx_i，σ^2=1n∑i=1n(xi−μ^)2\hat\sigma^2=\frac{1}{n}\sum\limits_{i=1}^n(x_i-\hat\mu)^2
    • 多维正态分布的最大似然估计：μ^=1n∑i=1nxi\hat\mu=\frac{1}{n}\sum\limits_{i=1}^nx_i，Σ=1n∑i=1n(xi−μ^)(xi−μ^)t\Sigma=\frac{1}{n}\sum\limits_{i=1}^n(x_i-\hat\mu)(x_i-\hat\mu)^t

# 四、高斯混合模型

GMM 可以看作是一种 "通用" 的概率密度函数

p(x)=∑k=1MαkN(x;μk,Σk)p(x)=\sum\limits_{k=1}^M\alpha_kN(\boldsymbol{x};\boldsymbol{\mu}_k,\boldsymbol{\Sigma}_k)

  • GMM 的最大似然估计

    θ=(α1,...,αM,μ1,...μM,Σ1,...ΣM)\theta=(\alpha_1,...,\alpha_M,\mu_1,...\mu_M,\Sigma_1,...\Sigma_M)

    • EM 算法
      • 初始化参数
      • 根据参数估计隐变量的概率
      • 根据隐变量的概率，最大化模型的参数
      • 迭代直到满足收敛精度

  • 举例：硬币 A 和 B，抛出正面的概率θA\theta_A 和θB\theta_B 未知

    Flips:HTTTHTHTH,HHHHTHHHHH,HTHHHHHTHH,HTHTTTHHTT,THHHTHHHTHFlips: HTTTHTHTH,HHHHTHHHHH,HTHHHHHTHH,HTHTTTHHTT,THHHTHHHTH

    使用 EM 算法进行求解：

    假设抛出正面的概率θA=0.6,θB=0.5\theta_A=0.6,\theta_B=0.5

    EE 步：

    P(ZA∣E)=P(E∣ZA)P(ZA)P(E∣ZA)P(ZA)+P(E∣ZB)P(ZB),P(ZB∣E)=P(E∣ZB)P(ZB)P(E∣ZA)P(ZA)+P(E∣ZB)P(ZB)P(Z_A|E)=\dfrac {P(E\vert Z_A)P(Z_A)}{P(E\vert Z_A)P(Z_A)+P(E\vert Z_B)P(Z_B)},P(Z_B|E)=\dfrac {P(E\vert Z_B)P(Z_B)}{P(E\vert Z_A)P(Z_A)+P(E\vert Z_B)P(Z_B)}

    NheadsN\ headsP(ZA∣E)P(Z_A\vert E)P(ZB∣E)P(Z_B\vert E)HeadAHead_ATailATail_AHeadBHead_BTailBTail_B
    50.450.552.22.22.82.8
    90.80.27.20.81.80.2
    80.730.275.91.52.10.5
    40.350.651.42.12.63.9
    70.650.354.51.92.51.1
    TotalTotal21.38.611.78.4

    θA1=21.321.3+8.6=0.71,θB1=11.711.7+8.4=0.58\theta_A^1=\dfrac{21.3}{21.3+8.6}=0.71,\theta_B^1=\dfrac{11.7}{11.7+8.4}=0.58

    以此类推

  • K-Means 聚类方法

    Input: 数据集DX={x1,...,xn}D_X=\{x_1,...,x_n\}，聚类数KK

    Output: 数据集的聚类标签D_Y=\

    1、随机初始化聚类中心\

    2、repeat

    3、 更新聚类标签：

    yi=argmin⁡1≤k≤K∥xi−μk∥2y_i=arg\min_{1\le k\le K}\lVert x_i-\boldsymbol{\mu}_k\rVert^2

    4、 更新聚类中心：

    μk=∑i=1nI(yi=k)xi∑i=1nI(yi=k)\mu_k=\dfrac{\sum_{i=1}^nI(y_i=k)x_i}{\sum_{i=1}^nI(y_i=k)}

    5、until DYD_Y 不再改变

# 五、隐马尔可夫

  • 在时刻tt 由隐状态w(t)w(t) 输出观察值v(t)\in\
  • 经过TT 个时刻后，可以观察到 HMM 输出一个观察序列VT=v(1)v(2)...v(T)V^T=v(1)v(2)...v(T)

隐马尔可夫模型：

  • 模型参数:θ=(π,A,B)\theta=(\pi,A,B)

  • 根据参数绘制模型

  • 估值问题：

    • 已知 HMM 模型参数θ\theta，计算模型输出特定观察序列VTV^T 的概率P(VT∣θ)P(V^T|\theta)

      举例：

      S={Ssunny,Srainy}(HiddenStates)S=\{S_{sunny},S_{rainy}\}(Hidden\ States),O={Oclean,Obike,Oshop,Opaint}(Observables)O=\{O_{clean},O_{bike},O_{shop},O_{paint}\}(Observables)

      π=∣0.60.4∣(InitialProbabilities),A=∣0.80.20.40.6∣(TransitionProbabilities)\pi=|0.6\ 0.4|(Initial\ Probabilities),A=\begin{vmatrix}0.8&0.2\\0.4&0.6\end{vmatrix}(Transition\ Probabilities)

      B=∣0.40.10.20.30.30.450.20.05∣(EmissionProbabilities)B=\begin{vmatrix}0.4&0.1&0.2&0.3\\0.3&0.45&0.2&0.05\end{vmatrix}(Emission\ Probabilities) 分别对应(paint,clean,shop,bike)(paint,clean,shop,bike)

      O={Opaint,Oclean,Oshop,Obike},P(O∣θ)=???O=\{O_{paint},O_{clean},O_{shop},O_{bike}\},P(O|\theta)=???

    • Day1:P(O1∣sunny)=0.6×0.4=0.24,P(O1∣rainy)=0.4×0.3=0.12Day1:P(O_1|sunny)=0.6\times0.4=0.24,P(O_1|rainy)=0.4\times0.3=0.12

    • Day2:P(O1O2∣sunny)=P(O1∣sunny)×0.8×0.1+P(O1∣rainy)×0.4×0.1=0.24×0.8×0.1+0.12×0.4×0.1=0.024P(O1O2∣rainy)=P(O1∣sunny)×0.2×0.45+P(O2∣rainy)×0.6×0.45=0.24×0.2×0.45+0.12×0.6×0.45=0.054Day2:P(O_1O_2|sunny)=P(O_1|sunny)\times0.8\times0.1+P(O_1|rainy)\times0.4\times0.1=0.24\times0.8\times0.1+0.12\times0.4\times0.1=0.024\\P(O_1O_2|rainy)=P(O_1|sunny)\times0.2\times0.45+P(O_2|rainy)\times0.6\times0.45=0.24\times0.2\times0.45+0.12\times0.6\times0.45=0.054

    • Day3:P(O1O2O3∣sunny)=P(O1O2∣sunny)×0.8×0.2+P(O1O2∣rainy)×0.4×0.2=0.00816P(O1O2O3∣rainy)=P(O1O2∣sunny)×0.2×0.2+P(O1O2∣rainy)×0.6×0.2=0.00744Day3:P(O_1O_2O_3|sunny)=P(O_1O_2|sunny)\times0.8\times0.2+P(O_1O_2|rainy)\times0.4\times0.2=0.00816\\P(O_1O_2O_3|rainy)=P(O_1O_2|sunny)\times0.2\times0.2+P(O_1O_2|rainy)\times0.6\times0.2=0.00744

    • Day4:P(O1O2O3O4∣sunny)=P(O1O2O3∣sunny)×0.8×0.3+P(O1O2O3∣rainy)×0.4×0.3=0.0028512P(O1O2O3O4∣rainy)=P(O1O2O3∣sunny)×0.2×0.05+P(O1O2O3∣rainy)×0.6×0.05=0.0003048Day4:P(O_1O_2O_3O_4|sunny)=P(O_1O_2O_3|sunny)\times0.8\times0.3+P(O_1O_2O_3|rainy)\times0.4\times0.3=0.0028512\\P(O_1O_2O_3O_4|rainy)=P(O_1O_2O_3|sunny)\times0.2\times0.05+P(O_1O_2O_3|rainy)\times0.6\times0.05=0.0003048

    • P(O∣θ)=0.0028512+0.0003048=0.003156P(O|\theta)=0.0028512+0.0003048=0.003156

  • 解码问题：

    • 已知 HMM 模型参数θ\theta，计算最有可能的特定观察序列VTV^T 的隐状态转移序列WTW^T

      举例：

      S={Ssunny,Srainy}(HiddenStates)S=\{S_{sunny},S_{rainy}\}(Hidden\ States),O={Oclean,Obike,Oshop,Opaint}(Observables)O=\{O_{clean},O_{bike},O_{shop},O_{paint}\}(Observables)

      π=∣0.60.4∣(InitialProbabilities),A=∣0.80.20.40.6∣(TransitionProbabilities)\pi=|0.6\ 0.4|(Initial\ Probabilities),A=\begin{vmatrix}0.8&0.2\\0.4&0.6\end{vmatrix}(Transition\ Probabilities)

      B=∣0.40.10.20.30.30.450.20.05∣(EmissionProbabilities)B=\begin{vmatrix}0.4&0.1&0.2&0.3\\0.3&0.45&0.2&0.05\end{vmatrix}(Emission\ Probabilities) 分别对应(paint,clean,shop,bike)(paint,clean,shop,bike)

      O={Oshop,Oclean,Obike,Opaint},W=???O=\{O_{shop},O_{clean},O_{bike},O_{paint}\},W=???

      保存两个回溯数组ϕsunny\phi_{sunny},\phi_

    • Day1:P(O1∣sunny)=0.6×0.2=0.12,P(O2∣rainy)=0.4×0.2=0.08ϕsunny=[0,],ϕrainy=[0,]Day1:P(O_1|sunny)=0.6\times0.2=0.12,P(O_2|rainy)=0.4\times0.2=0.08\\ \phi_{sunny}=[0,] , \phi_{rainy}=[0,]

    • Day2:P(O1O2∣sunny)=0.12×0.8×0.1+0.08×0.4×0.1=0.0096+0.0032Day2:P(O_1O_2|sunny)=0.12\times0.8\times0.1+0.08\times0.4\times0.1=0.0096+0.0032

      可以看到由sunnysunny 转过来的概率更大，因此ϕsunny=[0,sunny,]\phi_{sunny}=[0,sunny,]

      P(O1O2∣rainy)=0.12×0.2×0.45+0.08×0.6×0.45=0.0108+0.0216P(O_1O_2|rainy)=0.12\times0.2\times0.45+0.08\times0.6\times0.45=0.0108+0.0216；

      可以看到由rainyrainy 转过来的概率更大，因此ϕrainy=[0,rainy,]\phi_{rainy}=[0,rainy,]

    • Day3:P(O1O2O3∣sunny)=0.0096×0.8×0.3+0.0216×0.4×0.3=0.002304+0.002592Day3:P(O_1O_2O_3|sunny)=0.0096\times0.8\times0.3+0.0216\times0.4\times0.3=0.002304+0.002592

      经过比较，从rainyrainy 转过来的概率更大，因此ϕsunny=[0,sunny,rainy,]\phi_{sunny}=[0,sunny,rainy,]

      P(O1O2O3∣rainy)=0.0096×0.2×0.05+0.0216×0.6×0.05=0.000096+0.000648P(O_1O_2O_3|rainy)=0.0096\times0.2\times0.05+0.0216\times0.6\times0.05=0.000096+0.000648

      经过比较，从rainyrainy 转过来的概率更大，因此ϕrainy=[0,rainy,rainy,]\phi_{rainy}=[0,rainy,rainy,]

    • Day4:P(O1O2O3O4∣sunny)=0.002592×0.8×0.4+0.000648×0.4×0.4=0.00082944+0.00020736Day4:P(O_1O_2O_3O_4|sunny)=0.002592\times0.8\times0.4+0.000648\times0.4\times0.4=0.00082944+0.00020736

      经过比较，从sunnysunny 转移过来的概率更大，因此ϕsunny=[0,sunny,rainy,sunny]\phi_{sunny}=[0,sunny,rainy,sunny]

      P(O1O2O3O4∣rainy)=0.002592×0.2×0.3+0.000648×0.6×0.3=0.00015552+0.00011664P(O_1O_2O_3O_4|rainy)=0.002592\times0.2\times0.3+0.000648\times0.6\times0.3=0.00015552+0.00011664

      经过比较得到，从sunnysunny 转移过来的概率更大，因此ϕrainy=[0,rainy,rainy,sunny]\phi_{rainy}=[0,rainy,rainy,sunny]

    • 经过最后计算，最后一天时，sunnysunny 的概率为0.000829440.00082944，rainyrainy 的概率为0.000155520.00015552

      因此W=[?,?,?,sunny]W=[?,?,?,sunny]

      开始回溯，最后一天是sunnysunny，所以从ϕsunny\phi_{sunny} 回溯，找到的是sunnysunny，W=[?,?,sunny,sunny]W=[?,?,sunny,sunny]

      继续回溯，也是从ϕsunny\phi_{sunny} 找，找到rainyrainy，W=[?,rainy,sunny,sunny]W=[?,rainy,sunny,sunny]

      继续回溯，这次从ϕrainy\phi_{rainy} 找，找到rainyrainy，W=[rainy,rainy,sunny,sunny]W=[rainy,rainy,sunny,sunny]

      因此最后的答案就是W=[rainy,rainy,sunny,sunny]W=[rainy,rainy,sunny,sunny]

  • 学习问题

    • Baum−WelchBaum-Welch 算法（了解就行，出题的话计算量过大，多半不会考）

# 六、集成学习、聚类分析（除了红色标记，其他可以只做了解）

无监督学习：

  • 在不知道训练样本的标记信息时，揭示训练数据的内在性质和规律

  • 无监督学习中，训练样本的标记信息时未知的

  • 学习的目标是要揭示训练数据的内在性质和规律

有监督学习与无监督学习区别 [.red]：

  • 有监督学习有标签，无监督学习无标签，有监督学习是为了在训练集中找到规律，然后对测试数据集运用这种规律，达到分类的效果，而无监督学习寻找数据集中的规律性不一定要达到划分数据集的目的。

无监督学习的作用和应用：

  • 揭示训练数据的内在性质和规律
  • 应用：降维算法 (如 PCA)，聚类算法 (如 K-Means)，异常检测算法

聚类：

  • K-means
    • 普通 K-means 算法
    • 模糊 K 均值聚类
  • 层次聚类
    • AGNES 算法
  • 聚类数的选择
    • Dunn 指数："最小聚类间距" 除以 "最大聚类直径"
      • 聚类间距：聚类之间最近一对样本的距离
      • 聚类直径：类内距离最远的两个样本之间的距离
    • Davies-Bouldin 指数：每个聚类与其他聚类之间的最大相似度的均值
      • 类内离散度：聚类均值之间的距离
      • 类内离散度：样本到聚类均值的均方距离度量
      • 类内相似度：类内离散度之和 / 类间离散度

竞争学习

  • 竞争网络学习算法
  • SOFM 学习算法

集成学习：

  • Bagging：

    • 自助法（Bootstrapping）

      • 从数据集DD 中有放回地随机抽样nn 个样本，构成训练集SS
      • 从数据集DD 中有放回地随机抽样nn 个样本，构成训练集TT
      • 重复若干次，计算平均的评估结果

    • 通常来说，集成学习具有相似的偏差，但方差更低

    • Random-Forrest

  • Boosting

    • AdaBoost
      • 学习KK 个基分类器，加权线性组合
      • 基分类器的权重αk\alpha_k 是算法学习得到的参数
      • 样本集的加权重采样

  • Stacking

    • 可以将训练集分为两份，一份用来训练一级分类器，训练出来的一级分类器在另一份数据上进行预测，预测结果来训练元分类器

    • 更健壮的方法：k - 折交叉验证，k-1 折用来训练一级分类器，另一折产生分类器的预测