机器学习.md

机器学习

[toc]

绪论

常见定义

归纳

induction，从特殊到一半的泛化generalization过程，即从具体的事实归结出一般性规律。

演绎

deduction，从一半到特殊的特化specialization过程，即从基础原理推演出具体情况。

假设空间

假设空间（hypothesis space）是指在机器学习算法中，所有可能的候选模型组成的集合。学习过程就是一个在所有假设组成的空间中进行搜索的过程，搜索目标是找到与训练集匹配fit的假设。

泛化能力

模型对未知数据的适应能力，也可以理解为模型的普适性。

鲁棒性

鲁棒性是指模型对于数据噪声、异常值、缺失值等干扰因素的抵抗能力，也可以说是模型对于数据变化的适应能力。

奥卡姆剃刀

若有多个假设与观察一致，则选最简单的那个。

NFL定理

No Free Lunch定理，如果所有“问题”出现的机会相同、或所有问题同等重要，则总误差竟然与学习算法无关。说明不存在绝对好的算法，要结合实际问题寻找算法解决方案。

生成式模型和判别式模型的区别？

$ R $ 其他变量的集合

生成式考虑联合分布 $ P(Y,R,O) $

判别式考虑条件分布 $ P(Y,R|O) $

推断：给定观测值，从 $ P(Y,R,O),P(Y,R|O) $ 推断 $ P(Y|O) $

模型评估与选择

如何获得测试结果？评估方法

如何评估性能优劣？性能度量

如何判断实质差别？比较检验

经验误差与过拟合

常见定义

训练误差training error/经验误差empirical error：学习器在训练集上的误差

泛化误差generalization error：在新样本上的学习器

真实目标是最小化泛化误差，但泛化误差未知，所以大部分情况下在使经验误差最小化。

过拟合和欠拟合

如何判断过拟合和欠拟合？

• 过拟合：方差Variance（对不同数据集的表现差异）大，训练集的准确率高，但是测试集不高，模型的学习能力太强，泛化能力弱
• 欠拟合：偏差Bias（模型预测结果与真实值的差异程度）大，训练集和测试集的准确率都不高

为什么会过拟合？

• 模型复杂度过高：学习能力过于强大， 以至于把训练样本所包含的不太一般的特性、噪声、随机性都学到了
• 训练数据不足
• 训练轮数过多
• 特征选择不当

为什么会欠拟合？

• 模型复杂度不足，特征数量不足，数据集不足或不均衡

预防过拟合的方法？

• data augmentation：通过图像平移、翻转、缩放、切割等手段将数据库成倍扩充；语音：加入噪音。
• early stopping：运行优化方法直到若干次在验证集上的验证误差没有提升时候停止。
• 正则化：加上 $ L_1 $ 或 $ L_2 $ 正则化项
• dropout：通过修改隐藏层神经元的个数来防止网络的过拟合。在每一批次数据被训练时，Dropout按照给定的概率p随机忽略一些神经元，只有被保留下来的神经元的参数被更新。每一批次数据，由于随机性忽略神经元，使得网络具有一定的稀疏性，从而能减轻了不同特征之间的协同效应。而且由于每次被剔除的神经元不同，所以整个网络神经元的参数也只是部分被更新，消除减弱了神经元间的联合适应性，增强了神经网络的泛化能力和鲁棒性。Dropout只在训练时使用，作为一个超参数，然而在测试集时，并不能使用。p为超参，一般置为0或1。
• 简化模型：减少特征数量，或者进行特征选择，以减少模型的复杂度

预防欠拟合的方法？

• 增加模型的复杂度，增加训练数据，减少正则化参数，减少特征选择的限制，增加训练时间和迭代次数

评估方法

留出法

hold out，将数据集划分为两个互斥的集合，其中一个集合作为训练集，另一个作为测试集。在训练集中训练出模型后，用测试集来评估其测试误差，作为对泛化误差的估计。

留出法的缺点

• 不同的训练集/测试集分割会导致不同的模型评估结果，单次使用留出法得到的估计结果往往不够稳定可靠。
• 困境：如果训练集太小，则训练效果差；如果测试集太小，则评估结果不够稳定准确。（一般0.66-0.8）

交叉验证法

k-fold cross validation，k折交叉验证。

先将数据集划分为 $ k $ 个大小相似、分布尽量一致的互斥子集，每次用 $ k-1 $ 个子集的并集训练，一个子集测试。最终返回的是这 $ k $ 个测试结果的均值。

留一法

leave-one-out, LOO，交叉验证的特例，每个子集只有一个样本。

留一法的缺点

1. 当数据集比较大时，计算开销太大
2. 不一定准确：例如随机取球问题（50红，50黑；如果leave红则会猜 黑，反之同理，准确率为0）

自助法

从包含 $ m $ 个样本的数据集中用自主采样法bootstrap sampling为基础采样，

$$ \lim_{m\to\infty}\left(1-\frac1m\right)^m\to\frac1e\approx 0.368 $$

约有36.8%的样本未出现在采样数据集中，用采样数据集作为训练集，未采样到的样本作为测试集。测试结果叫做保外估计out-of-bag estimate。

自助法的优缺点

优：

1. 对于数据集较小，难以有效划分训练/测试集的时候很有用
2. 能产生多个不同的训练集，对集成学习等方法有用处

缺：

1. 改变初始数据集的分布，引入估计偏差
2. 因此在初始数据量足够的情况下，留出法和交叉验证法更常用。

如何调参？

调参是指通过调整模型的超参数，以获得更好的性能和更好的泛化能力。

• 网格搜索：基于一个参数网格，对每一组超参数进行训练和评估，以找到最佳的超参数组合。这种方法可以保证找到全局最优解，但需要对参数空间进行完整搜索，因此比较耗时。
• 实现可视化，用TensorBoard或者Wandb去可视化训练的过程，看loss等等有没有像理想中那样收敛，这个会是调参的一个依据，如果曲线太离谱就直接停止实验。
• 固定其他参数，优化单个参数
• 尽量去找相关论文中给出的数值，以之初始化，再根据训练结果进行微调。如果说没有这样的参考的话，我会依据经验找一个数值，然后二分法由粗到细去调参。
• 调参时可以缩小训练规模来节省时间。

性能度量

错误率

$$ \begin{aligned} E(f;D)&=\frac1m\sum_{i=1}^m\mathbb I(f(x_i)\neq y_i)\\ &=\int_{x\sim D}\mathbb I(f(x)\neq y)p(x)\text dx \end{aligned} $$

精度

$$ \begin{aligned} acc(f;D)&=\frac1m\sum_{i=1}^m\mathbb I(f(x_i)=y_i)=1-E(f:D)\\ &=\int_{x\sim D}\mathbb I(f(x)= y)p(x)\text{d}x \end{aligned} $$

混淆矩阵

查准率P

precision

$$ P=\frac{TP}{TP+FP} $$

查全率R

Recall

$$ R=\frac{TP}{TP+FN} $$

P-R曲线

若一个学习器的P-R曲线被另一个学习器的曲线完全“包住”，则可断言后者的性能优于前者。如果两个学习器的P-R曲线发生了交叉，则难以一般性地断言两者孰优孰劣，只能在具体的查准率或查全率条件下进行比较。

$ F_1 $ 度量

$$ F_1=\frac{2PR}{P+R}=\frac{2TP}{样例总数+TP-TN} $$

（是P和R的调和平均 $ \frac1{F1}=\frac12(\frac1P+\frac1R) $ ）

$ F_\beta $ 度量

对查准率和查全率的重视程度有所不同的度量：

$$ F_\beta=\frac{1+\beta^2PR}{\beta^2P+R} $$

$ \beta>1 $ 查全率更重要， $ \beta<1 $ 查准率更重要， $ \beta=1 $ 退化为 $ F_1 $ 。

Macro

$$ \begin{aligned} \text{macro-}P&=\frac1n\sum_{i=1}^n P_i\\ \text{macro-}R&=\frac1n\sum_{i=1}^n R_i\\ \text{macro-}F_1&=\frac{2\times\text{macro-}P\times\text{macro-}R}{\text{macro-}P+\text{macro-}R} \end{aligned} $$

Micro

$$ \begin{aligned} \text{micro-}P&=\frac{\overline {TP}}{\overline {TP}+\overline {FP}}\\ \text{micro-}R&=\frac{\overline {TP}}{\overline {TP}+\overline {FN}}\\ \text{micro-}F_1&=\frac{2\times\text{micro-}P\times\text{micro-}R}{\text{micro-}P+\text{micro-}R} \end{aligned} $$

ROC & AUC

纵轴TPR，横轴FPR

$$ \begin{aligned} TPR&=\frac{TP}{TP+FN}\\ FPR&=\frac{FP}{TN+FP} \end{aligned} $$

ROC曲线 (Receiver Operating Characteristic)：若一个学习器的ROC曲线被另一个学习器的曲线完全“包住”，则可断言后者的性能优于前者；若两个学习器的ROC曲线发生交叉，则难以以般性地断言两者孰优孰劣。

AUC (Area Under ROC Curve)：

$$ \ell_{rank}=\frac1{m^+m^-}\sum_{x^+\in D^+}\sum_{x^-\in D^-}\left(\mathbb I\left((f(x^+)<f(x^-)\right)+\frac12\mathbb I\left((f(x^+)=f(x^-)\right)\right) $$

即考虑每一对正、反例，若正例的预测值小于反例，则记一个“罚分”，若相等，则记0.5 个“罚分”。容易看出， $ \ell_{rank} $ 对应的是ROC曲线之上的面积。

代价敏感错误率

cost-sensitive

$$ E(f;D;cost)=\frac1m\left(\sum_{x_i\in D^+}\mathbb I\left(f(x_i)\neq y_i\right)\times cost_{01}+\sum_{x_i\in D^-}\mathbb I\left(f(x_i)\neq y_i\right)\times cost_{10}\right) $$

代价曲线 & 期望总体代价

比较检验

比较检验是

比较检验：比较评估学习器的性能

存在什么问题？

1. 我们希望比较的是泛化性能，实际比较的是测试集性能，两者的对比结果不一定相同
2. 测试集性能与测试集本身的选择有很大关系
3. 很多机器学习本身有一定的随机性

假设检验[还没看]

“假设”是对学习器泛化错误率分布的猜想，假设检验根据测试错误率估推出泛化错误率的分布。

泛化错误率 $ \epsilon $ ，测试错误率 $ \hat{\epsilon} $

偏差与方差

偏差、方差、噪声

偏差：度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力。

方差：度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响。

噪声：表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度。

偏差-方差分解

bias-variance decomposition，泛化误差可分解为偏差、方差与噪声之和。说明泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的。 $ E(f:D)=bias^2(x)+var(x)+\epsilon $

以回归任务为例，学习算法的期望预测为：

$$ \overline f(x)=\mathbb E_D[f(x;D)] $$

使用样本数相同的不同训练集产生的方差：

$$ var(x)=\mathbb E_D\left[(f(x;D)-\overline f(x))^2\right] $$

噪声：

$$ \epsilon ^2=\mathbb E_D\left[(y_D-y)^2\right] $$

期望输出与真实标记的差别称为偏差 (bias)，即

$$ bias^2(x)=\left(\overline f(x)-y\right)^2 $$

证明：

$$ \begin{aligned} \mathbb E_D(f;D)=&\mathbb E_D\left[\left(f(x:D)-y_D \right)^2\right]\ =&\mathbb E_D\left[\left(f(x:D)-\overline f(x)+\overline f(x)-y_D \right)^2\right]\ =&\mathbb E_D\left[\left(f(x:D)-\overline f(x) \right)^2\right]+\mathbb E_D\left[\left(\overline f(x)-y_D \right)^2\right]\ &+\mathbb E_D\left[2\left(f(x:D)-\overline f(x) \right)\left(\overline f(x)-y_D \right)\right]\ =&\mathbb E_D\left[\left(f(x:D)-\overline f(x) \right)^2\right]+\mathbb E_D\left[\left(\overline f(x)-y_D \right)^2\right]\ =&\mathbb E_D\left[\left(f(x:D)-\overline f(x) \right)^2\right]+\mathbb E_D\left[\left(\overline f(x)-y+y-y_D \right)^2\right]\ =&\mathbb E_D\left[\left(f(x:D)-\overline f(x) \right)^2\right]+\mathbb E_D\left[\left(\overline f(x)-y \right)^2\right]\ &+\mathbb E_D\left[\left(y-y_D \right)^2\right]+\mathbb E_D\left[\left(\overline f(x)-y \right)\left(y-y_D \right)\right]\ =&\mathbb E_D\left[\left(f(x:D)-\overline f(x) \right)^2\right]+\left(\overline f(x)-y \right)^2+\mathbb E_D\left[\left(y_D-y \right)^2\right]

\end{aligned} $$

偏差-方差困境

偏差与方差是有冲突的，这称为偏差-方差窘境 (bias-variance dilemma)。假定我们能控制学习算法的训练程度，则在训练不足时学习器的拟合能力不够强，训练数据的扰动不足以便学习器产生显著变化，此时偏差主导了泛化错误率；随着训练程度的加深，学习器的拟合能力逐渐增强，训练数据发生的扰动渐渐能被学习器学到，方差逐渐主导了泛化错误率。在训练程度充足后，学习器的拟合能力已非常强，训练数据发生的轻微扰动都会导致学习器发生显著变化，若训练数据自身的、非全局的特性被学习器学到了，则将发生过拟合。

线性模型

线性回归

线性回归的目标

$$ (w^,b^)=\arg \min_{(w,b)}\sum_{i=1}^m(f(x_i)-y_i)^2=\arg \min_{(w,b)}\sum_{i=1}^m(y_i-wx_i-b)^2 $$

最小二乘

最小二乘“参数估计”：求解 $ w,b $ 使 $ \mathbb E_{(w,b)}=\sum_{i=1}^m(y_i-wx_i-b)^2 $ 最小化的过程。将 $ \mathbb E_{(w,b)} $ 对 $ w,b $ 求导，令之为零后得到 $ w,b $ 最优解的闭式解。

对数线性回归

log-linear regression， $ \ln y=w^\top x+b $

广义线性模型

generalized linear model， $ y=g^{-1}(w^\top x+b) $ ，其中 $ g(\cdot) $ 为联系函数link function

逻辑斯蒂回归

什么是逻辑斯蒂回归？

逻辑斯蒂回归为一个分类算法，通过对输入特征进行加权求和，并将结果通过一个值域为0-1的sigmoid函数（也称为逻辑函数）进行映射，从而得到输出概率值。

Sigmoid函数是什么？为什么要用Sigmoid函数？

Sigmoid函数即形似S的函数，目的是近似不连续不可导的单位阶跃函数（值域 $ {0,1} $ ），作为它的替代函数surrogate function。又称对数几率函数。公式为

$$ y=\frac1{1+e^{-z}} $$

值域为 $ [0,1] $

如何求解参数？

将后验概率估计代入对数几率的式子，用极大似然法找到Loss函数。然后用梯度下降法、牛顿法等数值优化方法找到使得Loss最小的 $ \beta $ ，即可得到参数。

具体见p59。

梯度下降

什么是梯度下降法？

一阶迭代数值优化算法，用于寻找可微函数的局部最小值。

更新公式：

$$ x_{n+1}=x_{n}-\gamma\nabla f(x_n) $$

其中， $ \gamma $ 是学习率。 $ \nabla f $ 指向函数值增长最快的方向，则 $ -\nabla f $ 指向函数值增长最快的方向。理论上当 $ \gamma $ 足够小，则 $ f(x_n)\geq f(x_{n+1}) $

需要满足什么条件？

前提：

1. 目标函数可导
2. 目标函数是凸函数（否则可能会陷入局部最优解）

有什么优缺点？

优点：

1. 可以应用于许多不同的优化问题（线性回归，逻辑回归，神经网络）
2. 算法简单
3. 只需要计算一阶导数，计算成本相对较低。
4. 可以在大规模数据集上进行优化。

缺点：

1. 可能会陷入局部最小值，无法得到全局最小值。
2. 当函数存在平台、峡谷和其他复杂的非凸结构时，可能会出现震荡或缓慢收敛的情况。
3. 需要选择合适的学习率，过大或过小都会影响优化结果。
4. 对于某些问题，可能需要较多的迭代次数才能达到收敛。

什么是牛顿迭代法？需要满足什么条件？有什么优缺点？

目的：求 $ f(x)=0 $ 的解

初始化： $ x_0 $

重复：过 $ x_i $ 求 $ f(x) $ 的切线 $ L:y=f(x_{i})+f'(x_{i})(x-x_i) $ ，与x轴交点为 $ x_{i+1}=x_i-\frac{f(x_i)}{f'(x_i)} $

迭代公式：

$$ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} $$

对于 $ \beta^*=\arg\min_{\beta}\ell(\beta) $ 的优化问题，更新公式为：

$$ \beta^{t+1}=\beta^t-\left(\frac{\part^2\ell(\beta)}{\part \beta\part \beta^\top}\right)^{-1}\frac{\part\ell(\beta)}{\part \beta} $$

必要条件：

1. 目标函数二价可微
2. 目标函数的海森矩阵必须正定或负定

优点：

1. 可以更快地收敛到最优解，尤其是在函数存在二阶导数且二阶导数连续的情况下。
2. 可以解决梯度下降等一阶方法无法收敛的问题。
3. 可以自动调整学习率，减少手动调参的工作量。

缺点：

1. 对于高维问题，计算海森矩阵的代价非常昂贵。
2. 当海森矩阵不正定时，可能会导致算法发散。
3. 可能会陷入局部最小值，无法得到全局最小值。
4. 由于需要计算二阶导数，所以计算成本相对较高。
5. 当函数存在平台、峡谷和其他复杂的非凸结构时，可能会出现震荡或缓慢收敛的情况。

线性判别分析

LDA, Linear Discriminant Analysis

什么是LDA？

LDA是一种常用的分类算法和数据降维方法。它可以将一个高维数据集降到一个更低的维度，同时保持样本类别信息，从而方便后续的分类任务。

LDA 假设数据符合高斯分布，且各类别的协方差矩阵相等，基于此，它通过线性变换，将数据投影到一个低维空间中，使得同一类别的数据尽可能的接近，不同类别的数据尽可能的远离。这种投影方式保留了最大的类间差异性和最小的类内差异性，因此可以有效的提高分类准确率。

具体来说，LDA 算法主要包含两个步骤：（1）计算类内散度矩阵和类间散度矩阵；（2）通过求解广义瑞利商的特征向量，得到用于投影的变换矩阵。

LDA 广泛应用于图像识别、人脸识别、语音识别等领域，并且在实际应用中表现良好。

什么是类内散度矩阵，类间散度矩阵？

$ X_i,\mu_i,\Sigma_i $ ：第 $ i $ 类示例的集合、均值向量、协方差矩阵。

$ w^\top \mu_i,w^\top \Sigma_i w $ ：投影后的结果

目标：同类样例投影点的协方差尽可能小，即 $ w^\top \Sigma_0 w+w^\top \Sigma_1 w $ 尽可能小；类中心之间的距离尽可能大，即 $ ||w^\top \mu_0-w^\top\mu_1||_2^2 $ 尽可能大。即最大化

$$ J=\frac{||w^\top \mu_0-w^\top\mu_1||_2^2}{w^\top \Sigma_0 w+w^\top \Sigma_1 w}=\frac{w^\top (\mu_0-\mu_1)(\mu_0-\mu_1)^\top w}{w^\top(\Sigma_0+\Sigma_1)w} $$

其中类内散度矩阵within-class scatter matrix：

$$ S_w=\Sigma_0+\Sigma_1=\sum_{x\in X_0}(x-\mu_0)(x-\mu_0)^\top+\sum_{x\in X_1}(x-\mu_1)(x-\mu_1)^\top $$

类间散度矩阵between-class scatter matrix：

$$ S_b=(\mu_0-\mu_1)(\mu_0-\mu_1)^\top $$

这就是LDA想要最大化的目标，即 $ S_b,S_w $ 的广义瑞利商generalized Rayleigh quotient：

$$ J=\frac{w^\top S_b w}{w^\top S_w w} $$

如何求解LDA？

即确定能最大化 $ J $ 的 $ w $

令 $ w^\top S_ww=1 $ ，原式等价于

$$ \begin{aligned} &\min_w &&-w^\top S_b w\\ &s.t. && w^\top S_w w=1 \end{aligned} $$

由拉格朗日乘子法，等价于

$$ S_b w=\lambda S_ww $$

$ S_b w $ 方向恒等于 $ \mu_0-\mu_1 $ ，令

$$ S_b w=\lambda(\mu_0-\mu_1) $$

有：

$$ w=S_w^{-1}(\mu_0-\mu_1) $$

考虑到数值解的稳定性，在实践中通常是对 $ S_w $ 进行奇异值分解，即 $ S_w= U\Sigma V^\top $ ，这里 $ \Sigma $ 是一个实对角矩阵，其对角线上的元素是 $ S_w $ 的奇异值，然后再由 $ S_w^{-1}=V\Sigma^{-1}U^\top $ 得到 $ S_w^{-1} $

如何推广到多分类？[再看看！]

定义全局散度矩阵（ $ \mu $ 是所有示例的均值之和）

$$ S_t=S_b+S_w=\sum_{i=1}^m(x_i-\mu)(x_i-\mu)^\top\\ S_w=\sum_{i=1}^N S_{w_i}=\sum_{i=1}^N\sum_{x\in X_i}(x-\mu_i)(x-\mu_i)^\top\\ S_b=S_t-S_w=\sum_{i=1}^N m_i(\mu_i-\mu)(\mu_i-\mu)^\top $$

优化目标：

$$ \max_W\frac{tr(W^\top S_bW)}{tr(W^\top S_wW)} $$

通过求解 $ S_b W=\lambda S_w W $ 可得， $ W $ 的闭式解为 $ S_w^{-1}S_b $ 的 $ N-1 $ 个最大广义特征值所对应的特征向量组成的矩阵。

多分类学习

有什么拆分策略？

OvO（一对一，one vs one）： $ \frac{N(N-1)}{2} $ 个分类器

OvR（一对剩余，one vs rest）： $ N $ 个分类器，选择置信度最大的类别标记

MvM（多对多，many vs many）：需要用ECOC编码特殊构造。

类别不平衡

class-imbalance

有什么解决方法？

“再缩放”，也是“代价敏感学习”cost-sensitive learning的基础

1. 对反例进行“欠采样”
2. 对正例进行“过采样”
3. 阈值移动

决策树

基本流程

什么是决策树？

决策树是一种基于树结构的分类算法，其中每个内部节点表示一个属性或特征，每个叶子节点代表一个类别。该算法可以用于分类和回归问题，它通过对样本集合进行递归分治来构建决策树。

在构建决策树时，算法会选择一个最好的属性或特征，将样本集合分成更小的子集。这个过程会不断重复，直到所有的子集都属于同一个类别，或者已经达到了预先定义的最大深度。

决策树算法具有可解释性和易于理解的优点，因为它可以清楚地显示分类决策的过程，还可以处理缺失值和噪声数据。不过，决策树算法在处理高维数据时可能会遇到困难，并且容易受到过拟合和欠拟合等问题的影响。

决策树算法的基本流程是什么？

决策树的生成是基于分治策略的递归过程。

首先生成结点，如果训练集中的样本均属于同一类别，则将该节点标记为该类叶子结点，返回。如果属性集为空或训练集在属性集上的取值相同，则将该节点标记为叶子结点，类别为数据集中样本数最多的类，返回。如果都不满足这两种情况的话，从属性集中选择最优划分 $ a^* $ 。对最优划分中的每一个值，为结点生成一个分支，构造相应取值的样本子集。如果样本子集为空，则将该节点标记为叶子结点，类别为数据集中样本数最多的类，返回。否则递归地对样本子集和最优划分的子集生成决策树。

什么情况会导致递归返回？

1. 当前结点包含的样本全属于同一类别，无需划分
2. 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分
3. 当前结点包含的样本集合为空，不能划分。

划分选择

有什么划分的指标？它们的具体定义？

划分选择的目标是希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度” (purity) 越来越高。

划分的指标有：（ID3）信息增益、（C4.5）增益率、（CART）基尼指数。

$ p_k $ ：当前样本属于第 $ k $ 类的比例

假设离散属性 $ a $ 有 $ V $ 个可能的取值 $ {a^1,\dots,a^V} $ ，若使用 $ a $ 来对样本集 $ D $ 进行划分，则会产生 $ V $ 个分支结点，其中第 $ v $ 个分支结点包含了 $ D $ 中所有在属性 $ a $ 上取值为 $ a^v $ 的样本，记为 $ D^v $

信息熵：值越小，纯度越高

$$ Ent(D)=-\sum_{k=1}^{\mathcal Y}p_k\log_2 p_k $$

信息增益：值越大，说明使用属性 $ a $ 来划分所获得的纯度提升越大。

$$ Gain(D,a)=Ent(D)-\sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v) $$

增益率：信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，引入增益率。其中 $ IV(a) $ 为属性 $ a $ 的固有值intrinsic value

$$ Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}\\ IV(a)=-\sum_{v=1}^V\frac{|D|^v}{|D|}\log_2\frac{|D|^v}{|D|} $$

基尼指数Gini index：Gini反映从数据集 $ D $ 中随机抽取两个样本，其类别标记不一致的概率。越小纯度越高

$$ Gini(D)=\sum_{k=1}^{|\mathcal Y|}\sum_{k'\neq k}p_kp_{k'}=1-\sum_{k=1}^{|\mathcal Y|}p_k^2\\ \text{Gini_Index}(D,a) =\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v) $$

剪枝

简述预剪枝和后剪枝的策略？

预剪枝：基于贪心思想，如果划分后验证集精度 $ \leq $ 原来的精度，则剪枝，禁止这些分支展开。

后剪枝：生成完整决策树后，从叶子结点开始遍历，如果划分后验证集精度 $ \leq $ 原来的精度，则剪枝，禁止这些分支展开。

两者的优缺点？

	预剪枝	后剪枝
时间开销	测试时间降低，训练时间降低	测试时间降低，训练时间提高
过/欠拟合风险	过拟合风险降低，欠拟合风险增加	过拟合风险降低，欠拟合风险基本不变
泛化性能		后剪枝通常优于预剪枝

连续值与缺失值

如何处理连续值？

基本思路是连续属性离散化

1. 二分法
2. 对于从大到小排序好的取值 $ {a^1,\dots,a^n} $ ，令划分点集合为 $ T_a=\left{\frac{a^i+a^{i+1}}2|i\leq i\leq n-1\right} $ ，然像离散属性值一样来考察这些划分点

需注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还 可作为其后代结点的划分属性。

如何处理缺失值？

需要解决 1. 训练 2. 测试时的处理

令 $ \tilde D $ 为 $ D $ 在属性 $ a $ 上没有缺失值的样本子集，定义：

无缺失值比例： $ \displaystyle \rho=\frac{\sum_{x\in\tilde D} w_x}{\sum_{x\in D} w_x} $

无缺失值样本中第 $ k $ 类的比例： $ \displaystyle \tilde p_k=\frac{\sum_{x\in\tilde D_k} w_x}{\sum_{x\in \tilde D} w_x},1\leq k\leq|\mathcal Y| $

无缺失值样本中在属性 $ a $ 上取值为 $ a^v $ 的比例： $ \displaystyle \tilde r_v=\frac{\sum_{x\in\tilde D^v} w_x}{\sum_{x\in \tilde D} w_x},1\leq v\leq V $

推广：

$$ Ent(\tilde D)=-\sum_{k=1}^{\mathcal Y}\tilde p_k\log_2 \tilde p_k\\ Gain(D,a)=\rho \times Gain(\tilde D,a)=\rho \times\left(Ent(D)-\sum_{v=1}^V \tilde r_v Ent(D^v)\right) $$

多变量决策树

multivariate decision tree，在多变量决策树的学习过程中， 不是为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。

神经网络

支持向量机

基本概念

英文介绍

Support Vector Machine (SVM) is a powerful machine learning algorithm used for classification and regression analysis. SVM finds the best hyperplane that separates different classes in a high-dimensional space. The hyperplane is chosen in such a way that it maximizes the margin or the distance between the two closest points of different classes. These closest points are called support vectors, and they play a crucial role in defining the hyperplane.

SVM can handle both linearly separable and non-linearly separable data by using different types of kernel functions such as linear, polynomial, radial basis function (RBF), and sigmoid. The choice of kernel function depends on the data and the problem at hand. SVM can also handle multi-class classification problems using various techniques such as one-vs-one and one-vs-all.

SVM has several advantages over other classification algorithms such as logistic regression and decision trees. It is less prone to overfitting, works well with high-dimensional data, and is computationally efficient. However, SVM has some limitations, such as the need for careful selection of kernel functions and hyperparameters, and the difficulty in handling large datasets.

SVM是什么？

支持向量机是一种可以用于解决分类和回归问题的机器学习算法，目标是在高维空间中找到最佳的超平面，以最大化间隔，也就是margin。

SVM问题的基本型（是一个凸二次优化问题）：

$$ \begin{aligned} &\min_{w,b} \quad\frac12||w||^2\\ &s.t. \quad y_i(w^\top x_i+b)\geq1,i=1,\dots,m \end{aligned} $$

SVM中的“支持向量”指什么？在SVM中如何确定支持向量？

“支持向量”是指离分隔超平面最近的训练样本点。这些样本点是最能影响分隔超平面位置和方向的点，如果它们的位置发生变化，会直接影响到分隔超平面的位置和方向。

我们在SVM的训练过程中确定支持向量。在SVM的训练过程中，我们首先随机初始化超平面参数，然后迭代地优化超平面参数，直到收敛为止。在每一次迭代中，我们根据当前的超平面参数计算每个训练样本点到超平面的距离，并根据这些距离来判断哪些样本点是支持向量。

SVM在分类问题中如何定义“边界”（decision boundary）？

在SVM中，边界（decision boundary）是指将不同类别的数据点分开的超平面（hyperplane）。SVM的目标是寻找一个最优的超平面，将不同类别的数据点分开，并且使得该超平面与最近的数据点之间的距离（即margin）最大化。

SVM有什么优点和缺点？

优点：

1. 能有效处理高维数据，例如图像和文本分类
2. 在小数据集处理时表现优异，因为它只需要少量的支持向量来定义边界
3. SVM对数据中的噪声具有鲁棒性，因为决策边界由支持向量确定，它们是距离边界最近的数据点。
4. 泛化性好

缺点：

1. 不适用于大数据集，因为计算开销过大
2. 对核函数选择和参数选择敏感
3. 只适用于二元问题
4. 缺乏概率解释
5. 不适用于有缺失值的数据

原问题和对偶问题

如何将SVM转化为对偶问题？

对偶问题(dual problem)是指将一个优化问题的原问题(primal problem)转化为一个新的优化问题，对偶问题和原问题有相同的最优解，但对于一些问题，通过求解对偶问题可以更方便或更有效地得到原问题的解。

对偶问题一定是凸优化问题。

可以使用拉格朗日乘子法得到SVM的对偶问题：

拉格朗日函数：

$$ L(w,b,\alpha)=\frac12||w||^2+\sum_{i=1}^m\alpha_i(1-y_i(\omega^\top x_i+b)) $$

令 $ L(w,b,\alpha) $ 对 $ \omega,b $ 的偏导为零可得：

$$ w=\sum_{i=1}^m\alpha_i y_ix_i\quad(1)\\ 0=\sum_{i=1}^m\alpha_i y_i\quad(2) $$

将(1)代入拉格朗日函数可消去 $ w,b $ ，考虑(2)的约束可以得到对偶问题：

$$ \begin{aligned} &\max_{\alpha}\quad \sum_{i=1}^m\alpha_i-\frac12\sum_{i=1}^m\sum_{i=1}^m\alpha_i\alpha_jy_iy_jx_i^\top x_j\\ &s.t. \quad \sum_{i=1}^m\alpha_i y_i=0,\alpha_i\geq 0,i=1,\dots,m \end{aligned} $$

要满足KKT条件：

$$ \left{\begin{aligned} &\alpha_i\geq0\\ &y_if(x_i)-1\geq 0\\ &\alpha_i(y_if(x_i)-1)=0 \end{aligned}\right. $$

什么是KKT条件？[x]

Karush-Kuhn-Tucker (KKT)条件是非线性规划(nonlinear programming)最佳解的必要条件。

对于Lagrangian函数

$$ L(x,\lambda,\mu)=f(x)+\sum_{j=1}^m\lambda_jg_j(x)+\sum_{k=1}^n\mu_kh_k(x) $$

KKT条件包括：[术语怎么说？KKT只是必要条件，要到充分条件该如何做？内点]

$$ \left{\begin{aligned} &\nabla_xL=0\\ &g_j(x)=0,j = 1,\dots,m\\ &h_k(x)\leq 0,\\ &\mu_k\geq 0,\\ &\mu_kh_k(x)=0,k=1,\dots,p \end{aligned}\right. $$

为什么要将SVM转化为对偶问题？

虽然原问题本身就是一个凸二次规划(convex quadratic programming)问题，可以直接用现成的优化计算包求解，但是转化为对偶问题求解更高效。

原始的SVM问题是一个凸二次规划问题，通常使用二次规划算法求解。然而，当数据集的规模很大时，使用原始问题求解SVM会变得很慢，甚至变得不可行。此外，对于非线性SVM，计算的复杂度会随着特征空间的维度增加而急剧增加。

将SVM转化为对偶问题，就可以使用SMO算法等更高效的方法求解。

对偶问题和内积有关，可以引入核函数

什么是SMO算法？

为什么SMO算法不能用于求解原问题？

核函数

kernel function

SVM中的核函数是什么？

核函数是一种常用的技巧，用于将低维空间中线性不可分的数据映射到高维空间，从而使其在高维空间中变得线性可分。

如果原始空间是有限维（属性有限），那么一定存在一个高维特征空间使样本可分。

令 $ \phi(x) $ 为将 $ x $ 映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为

$$ f(x)=w^\top\phi(x)+b $$

原问题

$$ \begin{aligned}&\min_{w,b} \quad\frac12||w||^2\&s.t. \quad y_i(w^\top \phi(x_i)+b)\geq1,i=1,\dots,m\end{aligned} $$

对偶问题

$$ \begin{aligned} &\max_{\alpha}\quad \sum_{i=1}^m\alpha_i-\frac12\sum_{i=1}^m\sum_{i=1}^m\alpha_i\alpha_jy_iy_j\phi(x_i)^\top\phi( x_j)\\ &s.t. \quad \sum_{i=1}^m\alpha_i y_i=0,\alpha_i\geq 0,i=1,\dots,m \end{aligned} $$

核函数就是 $ \kappa(x_i,x_j)=<\phi(x_i),\phi(x_j)>=\phi(x_i)^\top\phi(x_j) $

核函数有什么性质？

[充要条件] $ \kappa $ 是核函数当且仅当对于任意数据 $ D={x_1,\dots,x_m} $ ，核矩阵 $ K=[\kappa(x_i,x_i)]_{m\times m} $ 总是半正定的。

也就是说，对于一个半正定的核矩阵，总能找到一个与之对于的映射 $ \phi $ 。

有什么常用的核函数？

名称	表达式	参数	适用场景
线性核	$ \kappa(x_i,x_j)=x_i^\top x_j $		输入特征维度较低，数据线性可分
多项式核	$ \kappa(x_i,x_j)=(x_i^\top x_j)^d $	$ d\geq 1 $ ，多项式次数	数据中存在多项式关系
高斯核(RBF)	$ \kappa(x_i,x_j)=\exp(-\frac{		x_i- x_j
拉普拉斯核	$ \kappa(x_i,x_j)=\exp(-\frac{		x_i-x_j
Sigmoid核	$ \kappa(x_i,x_j)=\tanh(\beta x_i^\top x_j+\theta) $	$ \beta>0,\theta<0 $	数据集合线性不可分时，将数据映射到一个非线性空间中。表现不是很好，高斯核和拉普拉斯核更常用。

此外，若 $ \kappa_1,\kappa_2 $ 为核函数，则

• $ \gamma_1\kappa_1+\gamma_2\kappa_2 $ 也是核函数
• $ \kappa_1\otimes\kappa_2(x,z)=\kappa_1(x,z)\kappa_2(x,z) $ 也是核函数
• 对于任意函数 $ g(x) $ ， $ g(x)\kappa_1(x,z)g(z) $ 也是核函数

如何选择合适的核函数？[x]

[未完善]核函数需要满足什么性质？（很好地度量在希尔伯特空间里的距离，自反性，来回一样，对于自己为0...）

根据根据具体的问题和数据选择。

软间隔与正则化

什么是软间隔SVM？

软间隔（soft margin）SVM通过设置松弛变量（slack variable），以允许某些样本不满足约束。传统硬间隔SVM要求数据完全线性可分，然而在实际情况下，由于数据可能存在一些噪声和异常点，很难找到完全线性可分的数据集。软间隔SVM通过允许一些样本出现在超平面的错误一侧，以此来解决线性不可分的问题。

优化目标可以写为

结构风险最小化+经验风险最小化

$$ \min_{w,b}\quad\frac12\vert\vert w\vert\vert^2+C\sum_{i=1}^{m}\ell_{0/1}\left(y_i(\omega^\top x_i+b)-1\right) $$

其中正则化常数 $ C>0 $ ， $ \ell_{0/1} $ 为“0/1损失函数”， $ \ell_{0/1}=\left{\begin{aligned}&1&z<0\&0&otherwise\end{aligned}\right. $

$ C\to\infty $ 时，会迫使所有样本均满足约束，等价于硬间隔； $ C $ 有限值时，允许一些样本不满足约束。

什么是替代损失？

由于 $ \ell_{0/1} $ 非凸、不连续，数学性质不好，使得优化目标难以直接求解，于是，使用其他一些函数替代 $ \ell_{0/1} $ ，称为替代损失（surrogate loss）

• hinge损失（最常用）： $ \ell_{hinge}(z)=\max(0,1-z) $
• 指数损失exponential loss： $ \ell_{\exp}(z)=\exp(-z) $
• 对率损失logistic loss： $ \ell_{\log}=\log(1+\exp(-z)) $

若采取hinge损失，优化目标可以改写为：

$$ \min_{w,b}\quad\frac12\vert\vert w\vert\vert^2+C\sum_{i=1}^{m}\max\left(0,1-y_i(\omega^\top x_i+b)\right) $$

为什么使用Hinge Loss?[不知道！]

Hinge Loss的优点在于它可以将最小化分类错误和最大化间隔相结合，即最小化损失的同时，最大化分类间隔。相比于其他损失函数，Hinge Loss对异常值的容忍度更高，可以更好地处理噪声和异常点的情况。同时，Hinge Loss的导数在0处不连续，使得模型更加稳定，不容易陷入局部最优解。（ChatGPT的回答）

什么是松弛变量？

引入松弛变量（slack variables），可将优化目标重写为

$$ \begin{aligned} &\min_{w,b}&\frac12\vert\vert w\vert\vert^2+C\sum_{i=1}^{m}\xi_{i}\\ &s.t.&y_i(w^\top x_i+b)\geq1-\xi_{i}\\ &&\xi_i\geq0,i=1,\dots,m \end{aligned} $$

噪声和异常点的区别？

噪声(noise)	异常值(outliers)
数据中存在的错误或不准确的值	与其他数据点不同的、明显偏离正常情况的数据点
可能是由于测量设备、传输问题或人为因素导致的	可能是由于记录或测量错误、系统故障或自然变异等原因导致的
在整个数据集中分布较均匀
可能会对模型的性能产生一定影响，但它们不一定是非常明显的异常值	可能会对模型的训练和预测造成不良影响，因为它们可能会导致模型的偏差和方差增大，从而影响模型的泛化性能
数据清洗和预处理噪声	使用特定的算法或技术来检测和处理异常点

与硬间隔SVM相比有何优势和劣势？

hard margin

优势：

1. 对于存在噪声或异常点的数据，软间隔SVM可以允许一些样本不满足约束条件，从而更好地适应这些数据；
2. 更好地处理线性不可分数据集。

劣势：

1. 在使用松弛变量的情况下，软间隔SVM更容易出现过拟合现象，需要谨慎调参；
2. 计算复杂度增加，需要花费更多的计算资源和时间。

如何在SVM中使用正则化？

正则化(regularization)问题如下：

$$ \min_{f}\quad\Omega(f)+C\sum_{i=1}^{m}\ell(f(x_i),y_i) $$

$ \Omega(f) $ ：“结构风险”structural risk，正则化项用于描述模型 $ f $ 的某些性质

$ \sum_{i=1}^{m}\ell(f(x_i),y_i) $ ：“经验风险”empirical risk，用于描述模型与训练数据的契合程度

$ C $ ：正则化常数，折中两者，C越大，表示分类错误的惩罚越严厉，对于训练集的拟合效果更好，但是可能会过拟合；C越小，则表示更容忍分类错误，对于新数据的泛化性能更好，但是可能会欠拟合。

$ L_1 $ 和 $ L_2 $ 正则化有何区别？

$ L_p $ 范数是常用的正则化项， $ L_2 $ 倾向于 $ w $ 的分量取值尽量均衡，即非零分量个数尽量稠密； $ L_0 $ 范数（向量中非0的元素的个数）和 $ L_1 $ 范数倾向于 $ w $ 的分量尽量稀疏，即非零分量个数尽量少。

支持向量回归

（Support Vector Regression，SVR）

什么是SVR？

有别于传统回归模型，SVR可以容忍 $ f(x) $ 和 $ y $ 之间最多有 $ \epsilon $ 的偏差，即仅当 $ f(x) $ 与 $ y $ 之间的差别绝对值大于 $ \epsilon $ 时才计算损失。这相当于构建了一个宽度为 $ 2\epsilon $ 的间隔带，若训练样本落入此间隔带，则认为预测正确。

SVR可形式化为

$$ \min_{w,b}\quad\frac12\vert\vert w\vert\vert^2+C\sum_{i=1}^{m}\ell_{\epsilon}\left(f(x_i)-y_i\right) $$

其中正则化常数 $ C>0 $ ， $ \ell_{\epsilon} $ 为 $ \epsilon $ -不敏感损失（ $ \epsilon $ -insensitive loss）函数， $ \ell_{\epsilon}=\left{\begin{aligned}&0&|z|\leq\epsilon\&|z|-\epsilon&otherwise\end{aligned}\right. $

优化目标

核方法

KLDA[还没写]

具体任务

百万样本量可以用SVM吗？

对于百万级别的样本量，求解SVM的原问题计算复杂度过大，时空开销较大，可能存在着困难。不过，存在一些优化算法，使得可以在大规模数据集上使用SVM。

1. 一种方法是使用随机梯度下降（SGD）算法等在线学习算法，在每次迭代中随机选择一部分数据进行训练。这种方法的计算复杂度低，但可能会影响模型的收敛性和精度。
2. 另一种方法是使用核函数的低秩近似，例如随机核近似（RKA）或核特征映射（KFM），以降低计算复杂度。这些方法将数据集投影到一个低维空间中，从而减少了计算量。不过，这些方法可能会对模型的精度产生一定的影响。
3. 此外，还有一些并行化的方法，例如基于GPU的实现或者分布式计算框架的使用，可以加速SVM的训练过程。

在使用SVM时，如何处理不平衡的训练数据？

• 改变类别权重：为少数样本增加权重
• 过采样少数样本
• 欠采样多数样本

SVM中如何处理非线性可分数据？

• 使用核函数：将原始数据映射到高维特征空间，从而使得原本线性不可分的数据在新的高维空间中成为线性可分的。
• 引入软间隔：允许某些样本不符合约束。

在SVM中如何处理多分类问题？

• One-vs-All：对于 $ k $ 类问题，训练 $ k $ 个二元分类器，每个分类器的正例为第 $ i $ 类样本，负例为其他类别的所有样本。测试时，选择具有最高决策函数值的分类器。
• One-vs-One：对于 $ k $ 类问题，在任意两类样本之间设计一个SVM，因此 $ k $ 个类别的样本就需要设计 $ k(k-1)/2 $ 个SVM。当对一个未知样本进行分类时，最后得票最多的类别即为该未知样本的类别。Libsvm中的多类分类就是根据这个方法实现的。

在SVM中如何处理缺失数据？

1. 删除缺失值：直接删除包含缺失数据的样本，在剩余的完整数据上进行SVM训练。但是，这种方法会损失有用的信息，并且可能导致训练数据的减少。
2. 插值：可以使用基于均值、中位数或其他统计量的简单插值方法，也可以使用更高级的插值方法，例如多重插值或KNN插值。然后使用填充后的数据进行SVM训练。

都会对SVM的性能造成负面影响。

训练细节

如何解决SVM模型过拟合（overfitting）的问题？

1. 减少特征数：使用特征选择技术，如主成分分析（PCA），来减少特征数量。
2. 增加正则化：惩罚过于复杂的模型，防止过拟合。
3. 增加数据量。
4. 调整模型参数：如惩罚参数C、核函数类型等，来寻找最优模型。
5. 使用交叉验证：可以使用交叉验证来评估模型性能和泛化能力，并进行模型选择。

SVM中如何选择合适的超参数？如何通过网格搜索来选择超参数？

交叉验证。

正则化项 $ C $ ：较大的值将使模型更加倾向于正确分类每个训练样本，但也可能导致过拟合。较小的值将允许更多的分类错误，但也可能导致欠拟合。

（RBF核） $ \gamma $ ：较大的值将导致决策边界更加复杂，可能会导致过拟合。较小的值将导致决策边界更加简单，可能会导致欠拟合。

需要避免使用测试集来选择，应该使用验证集来选择超参数，而将测试集保留到最后评估模型的性能。

SVM模型的复杂度是如何计算的？如何通过交叉验证来选择合适的SVM模型？

• 基于训练数据集大小（训练数据集大小 $ N $ ，特征维度 $ d $ ， $ O(Nd^2) $ ）
• 基于支持向量的复杂度（支持向量的数量为 $ m $ ， $ O(md) $ ）

模型对比

SVM与逻辑回归相比有哪些优势和劣势？

	SVM	LR
数据特征	对于线性可分的数据效果往往更好	能够处理非线性问题，可以使用多项式特征
数据规模	小数据集效果好	需要较多数据才能获得较好分类效果
噪声数据	容易受影响	容易受影响
参数选择	对参数的选择比较敏感	参数的选择比较简单
模型复杂度	复杂度较高	训练时间和内存开销相对较小，适合处理大规模数据

SVM与神经网络有何异同点？

(Answered by ChatGPT)

1. 工作原理不同：SVM是一种基于几何距离的分类器，它通过最大化分类间隔，寻找超平面将不同类别的数据分开；而神经网络则是通过模拟生物神经元的方式，使用一系列非线性变换来构建模型，实现分类和回归等任务。
2. 模型结构不同：SVM的模型结构比较简单，只有一个决策边界；而神经网络的模型结构比较复杂，由多个神经元和层组成。
3. 特征处理不同：SVM通常使用核函数将数据从低维空间映射到高维空间，以便找到更好的决策边界；而神经网络则通常使用输入层、隐藏层和输出层来提取和处理特征，不需要显式的特征转换过程。
4. 训练方法不同：SVM使用凸优化算法来训练模型，而神经网络通常使用反向传播算法来训练模型。
5. 适用场景不同：SVM适用于小规模、高维度的数据集，特别是在样本数目相对于特征数目较小的情况下表现更好，而神经网络适用于大规模、高维度的数据集，可以处理非线性问题和复杂的关系。

总之，SVM和神经网络都是有效的分类算法，但它们的实现方式和适用场景有所不同，需要根据具体的问题和数据情况选择适当的算法。

贝叶斯分类

贝叶斯决策论

Bayes decision theory

贝叶斯判定准则，贝叶斯最优分类器，贝叶斯风险

贝叶斯判定准则Bayes decision rule：目标是找到最小化总体风险的判定准则 $ h:\mathcal X\to\mathcal Y $ ，只需在每个样本上选择那个能使条件风险 $ R(c|x) $ 最小的类别标记，即 $ h^(x)=\arg\min_{c\in\mathcal Y} R(c|x) $ ，这里 $ h^ $ 是贝叶斯最优分类器 (Bayes optimal classifier) ，与之对应的总体风险 $ R(h^*) $ 称为贝叶斯风险 (Bayes risk)，即通过机器学习所能产生的模型精度的理论上限。

定义：

• 条件风险： $ \lambda_{ij} $ 为将 $ c_j $ 类别的样本误分类为 $ c_i $ 的损失

  $$ R(c_i|x)=\sum_{j=1}^N\lambda_{ij}P(c_j|x) $$

• 总体风险

  $$ R(h)=\mathbb E_x[R(h(x)|x)] $$

生成式模型，判别式模型

然而，后验概率 $ P(c|x) $ 难以直接获得，所以学习器要基于有限的训练样本集尽可能准确地估计出后验概率。

• 判别式：直接建模 $ P(c|x) $
• 生成式：先建模联合概率分布 $ P(x,c) $ ，也就是 $ P(c) $ （先验）和 $ P(x|c) $ （似然）再得到 $ P(c|x) $

极大似然估计

见概率论

朴素贝叶斯分类器

Naive Bayes classifier

朴素贝叶斯分类器 (naÏve Bayes classifier) 采用了属性条件独立性假设(attribute conditional independence assumption)：假设每个属性独立地对分类结果发生影响。简化类条件概率 $ P(x|c) $ 的建模。

重写贝叶斯公式： $ x_i $ 为 $ x $ 在第 $ i $ 个属性上的取值.

基于贝叶斯判定准则，朴素贝叶斯分类器表达式：

$$ h_{nb}(x)=\arg\max_{c\in\mathcal Y}P(c)\prod_{i=1}^d P(x_i|c) $$

离散：

$$ P(c)=\frac{|D_c|}{|D|}\quad P(x_i|c)=\frac{|D_{c,x_i}|}{|D_c|} $$

拉普拉斯修正（防止训练集中某个属性值没有与某个类同时出现过， $ |D_{c,x_i}|=0 $ 带来的误差。假设了属性值与类别的均匀分布，这是额外引入的 bias。 $ N $ 类别数， $ N_i $ 第 $ i $ 个属性可能的取值数）

$$ \hat P(c)=\frac{|D_c|+1}{|D|+N}\quad P(x_i|c)=\frac{|D_{c,x_i}|+1}{|D_c|+N_i} $$

连续：考虑概率密度函数

半朴素贝叶斯分类器

属性条件独立性假设在现实中很难成立，于是半朴素贝叶斯分类器(semi-naïve Bayes classifiers)对属性条件独立性假设进行一定程度的放松，适当考虑一部分属性问的相互依赖信息，从而既不需进行完全联合概率计算，又不至于彻底忽略了比较强的属性依赖关系。

采用独依赖估计(One-Dependent Estimator ，简称 ODE)，新假设：每个属性在类别之外最多仅依赖于一个其他属性

其中 $ pa_i $ 为属性 $ x_i $ 所依赖的属性，称为 $ x_i $ 的父属性，如何确定副属性引出不同算法

SPODE

super-parent ODE，假设所有属性都依赖于同一个属性，通过交叉验证等模型选择方法来确定超父属性

TAN

ADOE

averaged one-dependent estimator，基于集成学习，尝试将每个属性作为超父来构建SPODE，然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果。

kDE

将属性 $ pa_i $ 替换为包含 $ k $ 个属性的集合，随着 $ k $ 的增加，准确估计概率 $ P(x_i| y ,pai ) $ 所需的训练样本数量将以指数级增加。可能又会陷入求高阶联合概率的泥沼。

贝叶斯网

贝叶斯图（Bayesian network），也被称为信念网络（belief network）或概率有向无环图（probabilistic directed acyclic graph，PDAG），是一种图形化的概率模型，用于描述变量之间的概率依赖关系。变量（或节点）用圆圈表示，而变量之间的概率依赖关系则用有向箭头连接。箭头从一个变量指向依赖于它的变量，表示变量之间的因果关系或条件依赖关系。

贝叶斯网的条件独立性

$$ P(x_1,x_2,x_3,x_4,x_5)=P(x_1)P(x_2)P(x_3\vert x_1)P(x_4\vert x_1,x_2)P(x_5|x_2) $$

一个变量取值的确定与否，能对另两个变量间的独立性发生影响

同父：given $ x_1 $ , $ x_3,x_4 $ 独立

V型：给定 $ x_4 $ ，必不独立； $ x_4 $ 未知，两者独立（边际独立性marginal independence， $ x_1\perp!!!\perp x_2 $ ，两个随机变量在给定其他变量的边际分布下是独立的）

边际分布

Gibbs采样[没看]

EM算法

EM算法（Expectation-Maximization algorithm）是一种迭代优化算法，用于在存在隐变量（或缺失数据）的概率模型中进行参数估计。它是一种常用的无监督学习方法，通常用于处理含有不完整数据或观测数据中存在隐含变量的情况。非梯度

EM算法的基本思想是通过迭代的方式，交替进行两个步骤：E步（Expectation step）和M步（Maximization step），以较好地逼近参数的最大似然估计。

已观测变量 $ X $ ，隐变量（未观测变量） $ Z $ ，模型参数 $ \Theta $ ，若对 $ \Theta $ 做极大似然估计，则应该最大化对数似然（对 $ Z $ 算期望）

$$ LL(\Theta |X)=\ln P(X|\Theta)=\ln\sum_Z P(X,Z|\Theta) $$

EM算法步骤

1. 初始化模型参数。
2. 
3. 重复执行E步和M步，直到收敛或达到预定的停止条件。

集成学习

基本概念

什么是集成学习？

集成学习ensemble learning（读“昂”）是一种机器学习方法，首先训练一组基学习器（也称为弱学习器），再将它们的预测结果通过某种策略结合，来完成学习任务。集成学习的核心思想是通过组合多个弱学习器，来达到比单个弱学习器更好的泛化性能，从而提高模型的预测能力。

为什么集成学习需要集成“好而不同”的学习器？

好指的是基学习器的准确性，不同指的是基学习器间的多样性。

直觉上，模型的准确性当然是越高越好，基学习器的准确率较低，集成学习的预测性能也会受到影响。基学习器具有多样性意味着不同的学习器可以捕捉到数据中的不同特征，因此可以相互补充、互相弥补，从而提高整体的学习性能。

数学上，可以用“误差-分歧分解”(error-ambiguity decomposition)证明：个体学习器准确性越高、多样性越大，则集成越好。

我们通过“分歧”来反应个体学习器的多样性，分歧的定义是各个学习器预测结果与集成的MSE的加权均值。

学习器 $ h_i $ 的分歧： $ A(h_i|x)=(h_i(x)-H(x))^2 $

集成 $ H $ 的分歧： $ \overline A(h|x)=\sum_{i=1}^T w_i(h_i(x)-H(x))^2 $

个体学习器的平方误差： $ E(h_i|x)=(f(x)-h_i(x))^2 $

集成的平方误差： $ E(H|x)=(f(x)-H(x))^2 $

个体学习器误差的加权均值： $ \overline E(h|x)=\sum_{i=1}^T w_i E(h_i|x) $

有：

$$ \begin{aligned} \overline A (h|x)&=\sum_{i=1}^Tw_i E(h_i|x)-E(H|x)\\ &=\overline E(h|x)-E(H|x)\\ \end{aligned} $$

该式对所有样本 $ x $ 均成立，令 $ p(x) $ 表示样本的概率密度，则在全样本上有：

$$ \sum_{i=1}^Tw_i\int A(h_i|x)p(x)\text{d}x=\sum_{i=1}^Tw_i\int E(h_i|x)p(x)\text{d}x-\int E(H|x)p(x)\text{d}x $$

类似地，个体学习器 $ h_i $ 在全样本上的泛化误差和分歧项、集成的泛化误差分别为：

$$ \begin{aligned} E_i &= \int E(h_i|x)p(x)\text{d}x\\ A_i &= \int A(h_i|x)p(x)\text{d}x\\ E &= \int E(H|x)p(x)\text{d}x \end{aligned} $$

令 $ \overline E=\sum_{i=1}^Tw_i E_i $ 表示个体学习器的泛化误差的加权均值， $ \overline A=\sum_{i=1}^T w_iA_i $ 表示个体学习器的加权分歧值。有：

$$ E = \overline E-\overline A $$

这个漂亮的式子明确提示出：个体学习器准确性越高、多样性越大，则集成越好。

[然而，个体学习器的"准确性"和"多样性"本身就存在冲突。一般的，准确性很高之后，要增加多样性就需牺牲准确性。因此我们需要达到两者的平衡。]

[如何产生并结合“好而不同”的个体学习器，恰是集成学习研究的核心。]

有什么集成学习的方法？

1. 以Boosting为代表的，个体学习器问存在强依赖关系、必须串行生成的序列化方法
2. 以Bagging, Random Forest为代表的，个体学习器间不存在强依赖关系、可同时生成的并行化方法
3. 两者混合的方法

学习器结合的优点？

1. 减小泛化性能不佳的风险
2. 降低陷入糟糕局部极小点的风险
3. 扩大假设空间，可以学到更好的近似

各个算法的优缺点？

Boosting：

优点：准确，鲁棒，泛化能力强。

缺点：因为是序列化训练，所以训练时间长；对噪声敏感，可能过拟合，可以增加正则化项、减少弱分类器数量；受初始值影响较大，需要用随机化的丰富减少影响。

Bagging：

优点：可并行，准确，鲁棒，泛化能力强。

缺点：对高偏差模型效果不明显：Bagging主要的优势在于减少方差，对于高偏差的模型并不能很好地发挥作用。可解释性差。

学习器是越多越好吗？

不是，根据选择性集成，给定一组个体学习器，从中选择一部分来构建集成，经常会比使 用所有个体学习器更好 （更小的存储/时间开销，更强的泛化性能）。选择过程需考虑个体性能与多样性/互补性，仅选择“精度最高的”通常不好。

Boosting

什么是Boosting？

Boosting是一组可以将弱学习器提升为强学习器的算法。工作机制为：先从初始训练集中训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器。如此重复进行，直至基学习器数目达到事先指定的值 $ T $ 。最终将这 $ T $ 个基学习器进行加权结合。

AdaBoost的计算过程是什么？

原始的AdaBoost算法只能处理二分类问题，计算过程如下：

1. 初始化数据分布
2. 在训练的每一轮中：
   1. 使用当前的样本权重训练基学习器
   2. 计算分类误差率
   3. 如果分类误差率大于0.5，为了避免它进一步降低整个模型的准确率，算法会从循环中退出，停止训练
   4. 计算这个基学习器的权重
   5. 基于对分类正误情况更新数据分布，增加分错样本的影响，降低分对样本的影响
3. 最后基于各个基学习器的权重，得到最终的分类器

为什么分布这样更新？[没回答]

在AdaBoost中，如何更新数据分布？

1. 重赋权法re-weighting：在训练过程的每一轮中，根据样本分布为每个训练样本重新赋一个权重
2. 重采样法re-sampling：（对无法接受带权样本的基学习算法）在每一轮学习中，根据样本分布对训练 集重新进行采样，再用重采样而得的样本集对基学习器进行训练
   1. 可能获得重启动的机会以避免训练过程过早停止，即在抛弃不满足条件的当前基学习器之后，可根据当前分布重新对训练样本进行采样，再基于新的采样结果重新训练出基学习器，从而使得学习过程可以持 续到预设的 $ T $ 轮完成。

一般而言，这两种做法没有显著的优劣差别。

Bagging，随机森林

什么是Bagging算法？

bootstrap aggregating

基于自助采样法 (bootstrap sampling)，得到含 $ m $ 个样本的采样集，基于每个采样集训练出一个基学习器，再将这些基学习器进行结合。对于分类任务，使用简单投票法；对于回归任务，使用简单平均法。

若分类预测时出现两个类收到同样票数的情形，则最简单的做法是随机选择一个，也可进一步考察学习器投票的置信度来确定最终胜者。

包外估计out-of-bag estimation: bootstrap使得每个基学习器值使用了初始训练集中约63.2%的样本，剩下的样本可以作为验证集来对泛化性能进行“包外估计“。

Bagging的计算复杂度？

假定基学习器的计算复杂度为 $ O(m) $ ，则Bagging的复杂度大致为 $ T(O(m)+O(s)) $ ，采样与投票、平均过程的复杂度 $ O(s) $ 很小。

随机森林

Random Forest

在以决策树为基学习器的Bagging集成的基础上，进一步在决策树的训练中引入了随机属性选择。（传统决策树：在当前结点的属性集合中选择一个最优属性；RF：对基决策树的每个接待您，先从结点的属性集合中随机选择一个包含 $ k $ 个属性的子集，然后再从一个子集中选择一个最优属性用于划分，推荐 $ k=\log_2 d $ ）

在Bagging仅通过样本扰动增加多样性的基础上，引入了属性的扰动。

Stacking

Stacking 先从初始数据集训练出初级学习器，然后“生成”一个新数据集用于训练次级学习器。在这个新数据集中，初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当作样例标记。这里我们假定初级学习器使用不同学习算法产生，即初级集成是异质的。若直接用初级学习器的训练集来产生次级训练集，则过拟合风险会比较大，因此一般是通过使用交叉验证或留一法这样的方式，用训练初级学习器未使用的样本来产生次级学习器的训练样本。

多样性

有什么多样性度量的方法？

	$ h_i=+1 $	$ h_i=-1 $
$ h_j=+1 $	a	c
$ h_j=-1 $	b	d

• 不合度量disagreement measure：

$$ dis_{ij}=\frac{b+c}m $$

$ dis_{ij} $ 值域为 $ [0,1] $ ，值越大则多样性越大。

• 相关系数correlation coefficient

$$ \rho_{ij}=\frac{ad-bc}{\sqrt{(a+b)(a+c)(c+d)(b+d)}} $$

$ \rho_{ij} $ 的值域为 $ [-1,1] $ 。若 $ h_i $ 与 $ h_j $ 无关，则值为0；若 $ h_i $ 与 $ h_j $ 正相关，则值为正，否则为负。

• Q-统计量 Q-statistic

$$ Q_{ij}=\frac{ad-bc}{ad+bc} $$

$ Q_{ij} $ 与相关系数 $ \rho_{ij} $ 的符号相同，且 $ |Q_{ij}|\leq |\rho_{ij}| $

• $ \kappa $ -统计量 $ \kappa $ -statistic

$$ \kappa=\frac{p_1-p_2}{1-p_2} $$

其中 $ p_1 $ 是两个分类器取得一致的概率； $ p_2 $ 是两个分类器偶然达成一致的概率，它们可以由数据集 $ D $ 估算：

$$ \begin{aligned} p_1&=\frac{a+d}{m}\\ p_2&=\frac{(a+b)(a+c)+(c+d)(b+d)}{m^2} \end{aligned} $$

若分类器 $ h_i $ 与 $ h_j $ 在 $ D $ 上完全一致，则 $ \kappa = 1 $ ；若它们仅是偶然达成一致，则 $ \kappa = 0 $ 。188 $ \kappa $ 通常为非负值，仅在 $ h_i $ 与 $ h_j $ 达成一致的概率甚主低于偶然性的情况下取负值。

如何增强多样性？

对数据样本、输入属性、输出表示、算法参数进行扰动。

聚类

聚类任务

什么是聚类任务？

聚类试图将数据集中的样本划分为若干个通常是不相交的“簇”(cluster)。用于找寻数据内在的分布结构，也可作为分类等其他学习任务的前驱过程。

性能度量

直观上，什么样的聚类好？

直观上看，我们希望“物以类聚“，即同一簇的样本尽可能彼此相似，不同簇的样本尽可能不同。换言之，聚类结果的“簇内相似度 (intra-cluster similarity) 高且“簇间相似度” (inter-cluster similarity) 低。

什么是外部指标，内部指标？具体有什么指标？

外部指标external index，将聚类结果与某个“参考模型”reference model进行比较：

$ a= |SS| $ ，属于同一簇且在参考模型中也属于同一簇的样本对数

$ b= |SD| $ ，属于同一簇但在参考模型中不属于同一簇的样本对数

$ c= |DS| $ ，不属于同一簇但在参考模型中属于同一簇的样本对数

$ c= |DD| $ ，不属于同一簇且在参考模型中也不属于同一簇的样本对数

• Jaccard系数，Jaccard Coefficient, JC
• FM指数
• Rand指数(p198)

内部指标internal index，直接考察聚类结果而不利用任何参考模型：

• DBI，越小越好
• Dunn，越大越好

距离计算

距离度量需要满足什么基本性质？

非负性，同一性（距离为零当且仅当两点相等），对称性（ $ \operatorname{dist}(a,b)=\operatorname{dist}(b,a) $ ），直递性（ $ \operatorname{dist}(a,b)\leq\operatorname{dist}(a,c)+\operatorname{dist}(c,b) $ ）

有什么常见的距离度量？

• 对连续属性

闵可夫斯基距离Minkowski distance

$$ \operatorname{dist}{mk}(x_i,x_j)=\left(\sum{u=1}^n |x_{iu}-x_{ju}|^p\right)^{\frac1p} $$

$ p=2 $ ，欧氏距离Euclidean distance

$ p=1 $ ，曼哈顿距离Manhattan distance

$ p=\infty $ ，切比雪夫距离 $ =\max(|x_2-x_1|,|y_2-y_1|) $

• 对离散属性

  • 对有序属性：接近连续

  • 对无序属性：VDM, value difference metric

    $ m_{u,a} $ 在属性 $ u $ 上取值为 $ a $ 的样本数， $ m_{u,a,i} $ 在第 $ i $ 个样本簇中在属性 $ u $ 上取值为 $ a $ 的样本数， $ k $ 样本簇数

    $$ VDM_p(a,b)=\sum_{i=1}^k\left\vert\frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{m_{u,b}}\right\vert^p\ $$

• 对混合属性

  基于闵可夫斯基距离，括号里加上无序属性的VDM。

什么是距离度量学习？

在现实任务中基于数据样本来确定合适的距离计算式。

常见聚类方法

• 原型聚类

  • 亦称“基于原型的聚类”(prototype-based clustering)

  • 假设：聚类结构能通过一组原型刻画

  • 过程：先对原型初始化，然后对原型进行迭代更新求解

  • 代表：

    • k均值聚类：找到一组原型向量来刻画聚类结构，每个簇以该簇中所有样本点的“均值”表示
    • 学习向量量化(LVQ)：找到一组原型向量来刻画聚类结构，假设数据样本带有类别标记
    • 高斯混合聚类Gaussian Mixture Clustering：生成式模型。采用概率模型来表达聚类原型，假设样本由高斯混合过程（先选成分，再根据其概率密度函数采样）生成相应的样本。用EM算法迭代优化求解其最大对数似然。

• 密度聚类

  • 亦称“基于密度的聚类”(density-based clustering)
  • 假设：聚类结构能通过样本分布的紧密程度确定
  • 过程：从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇
  • 代表：DBSCAN, OPTICS, DENCLUE

• 层次聚类 (hierarchical clustering)

  • 假设：能够产生不同粒度的聚类结果
  • 过程：在不同层次对数据集进行划分，从而形成树形的聚类结构
  • 代表：AGNES (自底向上)，DIANA (自顶向下)

降维与度量学习

k近邻学习

给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个"邻居"的信息来进行预测 .

lazy learning，即在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。

维数灾难

是什么

curse of dimensionality，高维情形下出现的数据样本稀疏、 距离计算困难等问题

解决

降维dimension reduction，某种数学变换将原始高维属性空间转变为一个低维子空间，在这个子空间中样本密度大幅提高，距离计算也变得更为容易。

为什么可以降维

与学习任务密切相关的也许仅是某个低维分布，即高维空间中的一 个低维嵌入(embedding)

MDS[没看]

经典降维方法，要求原始空间中样本之间的距离在低维空间中得以保持

主成分分析

Principal Component Analysis，常用降维方法

推导[自己推一遍]

根据最近重构性（样本点到这个超平面的距离都足够近）和最大可分性（样本点在这个超平面上的投影能尽可能分开）的两个推导

计算过程

中心化：

$ x_i=x_i-\overline {x_i} $

优化目标：

$$ \min_W -\text{tr}(W^\top XX^\top W)\\ s.t. W^\top W=E $$

拉格朗日乘子法：

$$ XX^\top W=\lambda W $$

对 $ XX^\top $ 特征值分解并将求得的特征值从大到小排序，选择前 $ d' $ 维特征值对应的特征向量构成 $ w_1,\dots,w_{d'} $

重构维度选择

一般事先指定，可以通过重构阈值设置。例如 $ t=95% $

选择满足 $ \displaystyle \frac{\sum_{i=1}^{d'}\lambda_i}{\sum_{i=1}^{d}\lambda_i}\geq t $ 的最小 $ d' $

与LDA, FDA

p231

借鉴LDA的方法，假设每个 样本自成一个类型，那么则 希望所有样本在超平面上的 投影尽可能分开。 LDA既要优化类间散度又要 优化类内散度，PCA相当于 通过固定类内散度来限制它

PCA - FDA => LDA PCA是无监督学习方法，FDA是监督学习方法，考虑了标记的作用

应用[没看！]

特征脸(eigenface) robust PCA

度量学习

度量学习（Metric Learning）是机器学习领域的一个子领域，旨在通过学习适当的距离或度量函数，使得在特征空间中具有类似特性的样本之间的距离更小，而不同类别之间的距离更大。

马氏距离

优化目标

特征选择与稀疏学习

L1正则化和

计算学习理论

PAC学习

PAC理论

probably approximately correct。PAC理论是机器学习中的理论框架，通过控制样本复杂度和近似误差的方式，以一定的概率保证算法学得误差满足预设上限的模型。

PAC辨识

PAC可学习

一个学习问题被称为PAC可学习，当且仅当存在一个学习算法，对于给定的样本数量和质量，以一定的概率保证在未见过的数据上产生近似正确的输出。

PAC学习算法

（考虑时间复杂度）

样本复杂度

半监督学习

概率图模型

用图表示变量的相关关系的概率模型，点：变量，边：变量间的概率相关关系

有向无环图 - 贝叶斯网 - HMM

无向图 - 马尔科夫网

HMM

静态过程/动态过程？

$ P(X_{t+1}|X_t) $ 是否改变

马尔科夫链

具有马尔科夫性，系统下一时刻的状态仅由当前状态决定，不依赖于以往的任何状态。

简化模型，避免了维度灾难的问题。

参数？

三个要解决的问题？

问题1：Evaluation估值，评估模型与观测序列 之间的匹配程度

问题2：Decoding解码，如何根据观测序列推断出隐藏的模型状态

维特比算法

问题3：Learning学习，如何训练模型使其能最好地描述观测数据

Baum-Welch算法（EM的特例）

前两者都是DP，计算简单

1、什么是马尔科夫过程？

假设一个随机过程中，t_n 时刻的状态 x_n 的条件发布，只与其前一状态x_(n-1) 相关，即：

则将其称为 马尔可夫过程。

2、马尔科夫过程的核心思想是什么？

对于马尔可夫过程的思想，用一句话去概括：当前时刻状态仅与上一时刻状态相关，与其他时刻不相关。

可以从 马尔可夫过程图去理解，由于每个状态间是以有向直线连接，也就是当前时刻状态仅与上一时刻状态相关。

3、隐马尔可夫算法中的两个假设是什么？

齐次马尔可夫性假设：即假设隐藏的马尔科夫链在任意时刻 t 的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻 t 无关；

观测独立性假设：即假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态，与其他观测及状态无关。

4、隐马尔可夫模型三个基本问题是什么？

（1）概率计算问题：给定模型(A,B, $ \pi $ )和观测序列，计算在模型下观测序列出现的概率。(直接计算法理论可行，但计算复杂度太大（O(N^2T)）；用前向与后向计算法)

（2）学习问题：已知观测序列，估计模型参数，使得在该模型下观测序列概率最大。（极大似然估计的方法来估计参数，Baum-Welch算法（EM算法））

（3）预测问题，也称为解码问题：已知模型和观测序列，求对给定观测序列条件概率最大的状态序列。（维特比算法，动态规划，核心：边计算边删掉不可能是答案的路径，在最后剩下的路径中挑选最优路径）

5、隐马尔可夫模型三个基本问题的联系？

三个基本问题 存在 渐进关系。首先，要学会用前向算法和后向算法算观测序列出现的概率，然后用Baum-Welch算法求参数的时候，某些步骤是需要用到前向算法和后向算法的，计算得到参数后，我们就可以用来做预测了。因此可以看到，三个基本问题，它们是渐进的，解决NLP问题，应用HMM模型做解码任务应该是最终的目的。

6、隐马尔可夫算法存在哪些问题？

因为HMM模型其实它简化了很多问题，做了某些很强的假设，如齐次马尔可夫性假设和观测独立性假设，做了假设的好处是，简化求解的难度，坏处是对真实情况的建模能力变弱了。

在序列标注问题中，隐状态（标注）不仅和单个观测状态相关，还和观察序列的长度、上下文等信息相关。例如词性标注问题中，一个词被标注为动词还是名词，不仅与它本身以及它前一个词的标注有关，还依赖于上下文中的其他词。可以使用最大熵马尔科夫模型进行优化。

规则学习

强化学习