一、机器学习相关

1. 基本概念

1.1. 排序

1. Why does sorting a collection have (at least) $O(n log n)$ complexity? n is the length of the collection.

• $O(n log n)$ is the optimal value for a comparison sort. [https://theartofmachinery.com/2019/01/05/sorting_is_nlogn.html].

2. 几种排序算法介绍以及复杂度分析。

• 排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

• 排序的稳定性是指：若待排序的序列中，存在多个具有相同元素，经过排序， 这些元素的相对次序保持不变，则称该算法是稳定的；若经排序后，元素的相对次序发生了改变，则称该算法是不稳定的。

• 常见的八种排序方法都属于内部排序，交换排序（冒泡排序、快速排序）、选择排序（简单选择排序、堆排序）、插入排序（直接插入排序、希尔排序）、归并排序、基数排序。
  

• 冒泡排序：两两比较待排序数据元素的大小，如果两个数据元素的次序相反时则进行交换，直到没有反序的数据元素未知。平均时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$，属于稳定排序。

• 快速排序： 在当前无序区任取一个元素作为待比较的基准，用此基准将当前无序区划分为左右两个较小的无序区，其中左边无序子区的数据元素均小于等于基准元素，右边无序子区中的元素均大于等于基准元素，而基准则始终位于最终排序位置上。依次再对左右两个无序子区进行上述划分过程，直到所有无序子区中的元素都已排序为止。平均时间复杂度为 $O(n \log_2 n)$，空间复杂度为 $O(\log_2 n) - O(n)$ （可能退化为冒泡排序），属于不稳定算法。

• 简单选择排序：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列最后，直到全部待排序的数据元素排完。平均时间复杂度为 $O(n^2)$，空间复杂度为$O(1)$，属于稳定排序。

• 堆排序：将数组看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中的双亲结点和孩子结点之间的内在关系来选择最小的元素。小根堆：树中任一非叶子结点的值均小于等于其孩子结点的值（堆顶最小）；大根堆：树中任一非叶子结点的值均大于等于其孩子结点的值（堆顶最大）。平均时间复杂度为 $O(n \log_2 n)$，空间复杂度为 $O(1)$，属于不稳定排序。

• 直接插入排序：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。平均时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$，属于稳定排序。

• 希尔排序：先取一个小于 n 的整数 $d_1$ 作为第一个增量，把所有元素分为若干组，所有下标距离为 $d_1$ 的倍数的元素放在同一组中。先在各组内进行直接插入排序。然后取第二个增量 $d_2 < d_1$，按照原始位置下标，重复上述分组和排序，直到所取的增量 $d_t = 1$，即所有元素都放在同一组中进行直接插入排序为止。平均时间复杂度为 $O(n^{1.3} )$，空间复杂度为O(1)，不稳排序。

• 归并排序：归并排序最核心的部分是合并（merge）过程，将两个有序的数组 a 和 b 合并为一个有序数组 c。从左往右枚举 a[i] 和 b[j]，找出最小的值并放入数组 c[k]；重复上述过程直到 a 和 b 有一个为空时，将另一个数组剩下的元素放入 c。为保证排序的稳定性，前段首元素小于或等于后段首元素时（a[i] <= b[j]）而非小于时（a[i] < b[j]）就要作为最小值放入 c[k]。平均时间复杂度为 $O(n \log n)$，空间复杂度为 $O(1)$，稳定排序。

• 基数排序：将待排序的元素拆分为 $k$ 个关键字，先对第 $1$ 关键字进行稳定排序，然后对于每组具有相同关键字的元素 再对第 $2$ 关键字进行稳定排序（递归执行）。最后对于每组 具有相同关键字的元素 再对第 $k$ 关键字进行稳定排序。如果对自然数进行比较，将自然数按个位对齐后往高位补齐 $0$，则一个数字从左往右数第 $i$ 位数就可以作为第 $i$ 关键字。设数据量为$n$, 数据为$d$进制, 最大位数为 $k$, 则对某一位执行计数排序使用$O(n+d)$时间，排序所有 $k$ 位使用$O((n + d) \times k)$ 时间。空间复杂度为 $O(n + d)$, 非原地排序。如果对内层关键字的排序是稳定的，则基数排序是稳定的排序算法。

1.2. 二分查找

以在一个升序数组中查找一个数为例。它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

二分查找的最优时间复杂度为 $O(1)$。二分查找的平均时间复杂度和最坏时间复杂度均为 $O(\log n)$。因为在二分搜索过程中，算法每次都把查询的区间减半，所以对于一个长度为 $n$ 的数组，至多会进行 $O(\log n)$ 次查找。

迭代版本的二分查找的空间复杂度为 $O(1)$。

1.3. 回归模型和分类模型常用损失函数有哪些？

回归模型常用的损失函数

1. 0-1损失函数：

$L(\hat{y},y) = \begin{cases} 1, & y \neq \hat{y} \\ 0, & y = \hat{y} \end{cases}$

2. 平均绝对误差MAE：异常点多的情况下鲁棒性更强，不像MSE那样过度惩罚大误差；但不方便求导

   $L(\hat{y}, y) = \frac{1}{n} \sum_{i=1}^{n}|y_i - \hat{y}_i|.$

3. 均方误差MSE：求导方便，能够用梯度下降法优化；对异常值敏感，异常值的存在会导致MSE值急剧增大，从而影响模型效果。

   $L(\hat{y},y) = \frac{1}{n} \sum_{i=1}^{n}(y_i - \hat{y}_i)^2.$

4. 对数损失函数/对数似然损失函数：

   $L(P(Y|X),Y) = -{\rm log} P(Y|X)$

5. Huber 损失函数：结合了MAE和MSE的优点，对异常值更加鲁棒，比MSE对大的误差的惩罚更加温和；在误差较小时仍然能够提供与MSE类似的梯度更新；缺点是需要调整超参数 $\delta$

   $L_{Huber}(\hat{y}, y) = \begin{cases} (\hat{y}-y)^2 & |\hat{y}-y| \leq \delta \\ 2 \delta |\hat{y}-y| - \delta^2 & |\hat{y}-y| > \delta \end{cases}$

6. 对数余弦 Log-Cosh 损失函数：近似于MSE，但对大误差的惩罚更温和，兼顾了MSE和MAE的优点。同时二阶处处可微（牛顿法要求二阶可微），更加平滑且容易优化。但是，不如MSE那样简单直观，在某些应用中表现不如MSE。

   $L(\hat{y},y) = \log \cosh(\hat{y}-y)$

分类模型中常用的损失函数

1. 交叉熵损失。对于二元分类，公式为如下。其中，$y$是真实标签，$p$是模型预测的概率。

$L(p,y) = -[y \log p + (1-y) \log (1-p)].$

• 优点：直接衡量模型预测的概率与真实分类标签之间的差异，适合分类任务。对概率差异敏感，能够较好地区分高概率和低概率的预测。
• 缺点：当预测的概率非常接近0或1时，交叉熵的梯度可能变得极端，导致训练不稳定。对于不平衡数据，模型倾向于偏向多数类，需要配合其他技术如加权损失函数或欠采样来处理。

2. Hinge loss。通常用于支持向量机，公式如下。$y \in {-1,1}$是真实标签，$f(x)$是模型输出。

$L(f(x),y) = \max(0, 1 - y \times f(x))$

• 优点：强调分类边界的最大化，适用于SVM；对小的误差不敏感，能够防止过拟合。
• 缺点：不适用于概率输出的分类模型。仅适用于二分类问题，多分类任务中扩展性较差。

3. Kullback-Leibler 散度。假设$p(x)$是真实分布，$q$是模型预测的概率分布，公式如下：

$D_{\text{KL}}(p||q) = \sum p(x) \log(\frac{p(x)}{q(x)}),$

• 优点：可以量化两个分布之间的差异，适合概率模型；
• 缺点：对极端概率值（接近于1或0）的预测非常敏感，可能导致数值不稳定。

1.4. 什么是结构误差和经验误差？

经验风险（经验损失）：模型 $f(X)$关于训练数据集的平均损失

$R_{\rm emp}(f) = \frac{1}{N} \sum_{i=1}^N L(y_i,f(x_i)).$

结构风险：是在经验风险上加上表示模型复杂度的正则化项

$R_{\rm srm}(f) = \frac{1}{N} \sum_{i=1}^{N}L(y_i,f(x_i))+\lambda J(f).$

经验风险最小化的策略认为，经验风险最小的模型是最优的模型。

结构风险最小化是为了防止过拟合而提出的，结构风险最小化等价于正则化。结构风险最小化的策略认为结构风险最小的模型是最优的模型。

1.5. 如何选择合适的模型评估指标？ROC、AUC、精准度、召回率、F1值

模型评估指标用于衡量机器学习模型在测试集或验证集上的表现，帮助评估其性能。

混淆矩阵，又称误差矩阵，就是分别统计分类模型归错类，归对类的观测值个数，然后把结果放在一个表里展示出来。这个表就是混淆矩阵。

混淆矩阵是ROC曲线绘制的基础，同时它也是衡量分类型模型准确度中最基本，最直观，计算最简单的方法。

混淆矩阵	预测结果	预测结果
真实情况	反例	正例
反例	TN（真反例）	FP（假正例）
正例	FN（假反例）	TP（真正例）

• TN：True Negative，将样本中的负类样本预测为负类的数量
• FP：False Positive，将样本中的负类样本预测为正类的数量
• FN：False Negative，将样本中的正类样本预测为负类的数量
• TP：True Positive，将样本中的正类样本预测为正类的数量

分类任务指标

Accuracy（准确率）：分类正确的样本占总样本个数的比例

$\text{Accuracy} = \frac{n_{correct}}{n_{total}}$

• 缺点：不同类别的样本比例非常不均衡时，占比大的类别往往成为影响准确率的最主要因素。比如，当负样本占99%时，分类器把所有样本都预测为负样本也可以获得99%的准确率。
• 解决：可以使用每个类别下的样本准确率的算术平均（平均准确率）作为模型评估的指标。

在数据集不平衡的情况下（阴性数据多，阳性数据少），精确度和召回率是合适的性能指标。精确度和召回率都只关注阳性类（少数类），而不关心真正的阴性类（多数类）。简单地说，在数据类别不平衡的情况下，即有大量反类和少量正类时，精确度和召回率是首选指标。换句话说，精确度和召回率可以评估分类器在少数类别上的性能。

Precision（精确率）：分类正确的正样本个数占分类器判定为正样本的样本个数的比例

取值范围：0 到 1，其中 1 表示完全精确（没有误报），0 表示没有正确的正预测。

$\text{Precision} = \frac{TP}{TP+FP}$

Recall（召回率， 又称灵敏度 sensitivity）：分类正确的正样本数占真正的正样本个数的比例

取值范围：0 至 1，其中 1 表示完全召回（无假阴性），0 表示未识别出真阳性。

$\text{Recall} = \frac{TP}{TP+FN}$

F1-score：precision和recall的调和平均值；当精确率和召回率都高时，F1值也会高；特别适用于类别不平衡的数据集

$F1 = \frac{2 \times \text{Precision} \times \text{Recall} }{\text{Precision} + \text{Recall} }$

取值范围：0 到 1，其中 1 表示精确度和召回率之间的最佳平衡，0 表示精确度、召回率或两者均为 0。

如果我们认为精确率或召回率中的某一个比另一个更重要，那么可以使用 $F_{\beta}$分数，这是精确率和召回率的加权调和平均数。这个分数特别适用于一些特定的应用场景，例如在医学检测中，假阴性可能比假阳性代价更高的情况。$F_{\beta}$ 能够根据实际需求调整精确率和召回率的相对权重。

$F_{\beta}$ 分数公式：

$F_{\beta} = (1 + \beta^2) \cdot \frac{ {\text{Precision} \cdot \text{Recall}}}{ {\beta^2 \cdot \text{Precision} + \text{Recall}} }.$

• $\beta$: 用于控制精确率和召回率之间的权衡。

  • 如果 $\beta>1$，则更重视召回率；适用于假阴性代价较高的场景。
  • 如果 $\beta<1$，则更重视精确率；适用于假阳性代价较高的场景。
  • 当 $\beta = 1$时，$F_{\beta}$ 分数即为常见的 F1 分数，它将精确率和召回率同等看待。

• 在医学检测中，假阴性可能意味着病人未能及时得到治疗，因此我们可能更关注召回率，选择较高的 $\beta$ 值以降低漏诊的概率。

• 在反垃圾邮件系统中，假阳性（将正常邮件误判为垃圾邮件）可能带来更大影响，此时可以使用较小的 $\beta$ 值，更加注重精确率。

PR指标应用场景

• 一个完美的分类器的精确度和召回率都等于 1。
• 精确度和召回率应一并报告，不应单独报告。因为很容易通过改变模型的召回率（灵敏度）来提高精确度，反之亦然。

在正类（也称为少数类）稀少的情况下，PR 能够处理类不平衡问题。但是，如果数据集不平衡，负类是罕见的一类，那么 PR 曲线就不是最佳曲线，可能会产生误导。在这种情况下，ROC 曲线可能更合适。

具体应用场景：

• 当两个类别同样重要时：如果模型的目标是在两个类别上都有同样好的表现，那么 PR 是可使用的指标。猫和狗的图像分类就是一个很好的例子，因为在猫上的表现与在狗上的表现同样重要。
• 当少数类别更重要时：如果模型的重点是正确识别出尽可能多的正面样本，那么 PR 就是要使用的指标。以垃圾邮件检测器为例，其目标是找出所有可能的垃圾邮件。普通邮件根本不值得关注–它们会影响阳性样本的数量。

P-R 曲线

在排序问题中，通常没有一个确定的阈值把得到的结果直接判定为正样本或负样本，而是采用Top N返回结果的Precision和Recall值来衡量排序模型的性能。即认为模型返回的Top N结果就是模型判定的正样本，计算前N个位置的Precision@N和Recall@N。为了综合评估一个排序模型的好坏，不仅要看模型在不同Top N下的Precision@N和Recall@N，而且最好画出模型的P-R曲线。P-R曲线的横轴是Recall，纵轴是Precision。

当数据集的类别不平衡时，精度和召回率是比准确率更好的指标。同样，对于不平衡的类别，精度-召回曲线比 ROC 曲线更合适。精确度-召回率曲线是不同阈值下精确度（y 轴）和召回率（x 轴）的曲线图，与 ROC 曲线类似。需要注意的是，在计算精确度和召回率时，绝对不能使用真实负值，这些指标只考虑正确预测。

Area Under the PR Curve (AUPRC)：AUPRC 将一系列阈值的曲线汇总为一个分数。该分数可作为二元分类问题中不同模型之间的比较点，其中 1.0 分代表最完美的分类器。

ROC 曲线适用于每个类别之间的样本平衡的情况，而精度-召回曲线则适用于不平衡的数据集。

特异性（specificity）

Specificity（特异性）用于衡量模型在识别负类时的准确性。特异性反映了模型避免将真实的负类样本误判为正类样本的能力，通俗地说就是“没有病的人被正确地诊断为没有病的比例”。

$\text{Specificity} = \frac{\text{TN}}{\text{TN} + \text{FP}}$

• 如果特异性高，说明模型能够很好地避免误报（将实际的负类错判为正类）。
• 特异性常与敏感性(sensitivity)一起使用，后者用于衡量模型识别正类（“有病”的人）能力的表现。

Image credits to source

ROC 曲线

横坐标为假阳性率（False Positive Rate，FPR）；纵坐标为真阳性率（True Positive Rate，TPR）

$FPR = \frac{FP}{N}, \quad TPR = \frac{TP}{P},$

其中，P是真实的正样本的数量，N是真实的负样本的数量，TP是P个正样本中被分类器预测为正样本的个数，FP是N个负样本中被预测为正样本的个数。

如何绘制ROC曲线

通过不断移动分类器的“截断点”来生成曲线上的一组关键点。在二分类问题中，模型输出一般是预测样本为正例的概率，在输出最终的正例负例之前，我们需要制定一个阈值。大于该阈值的样本判定为正例，小于该阈值的样本判定为负例。通过动态调整截断点，绘制每个截断点对应位置，再连接所有点得到最终的ROC曲线。
比如，阈值为0时，此时所有样本被预测为负例，TPR = 0, FPR = 0；当阈值增加为1时，此时所有样本被预测为正例，TPR = 1, FPR = 1.

一般情况下，PR曲线易受样本数量的影响，样本数量不均衡情况下PR曲线会有明显变化，故一般使用ROC曲线。

AUC：ROC曲线下的面积大小。计算AUC值只要沿着ROC横轴做积分就可以。AUC取值在0.0~1之间。AUC越大，分类性能越好。AUC表示预测的正例排在负例前面的概率。

指标想表达的含义，简单来说其实就是随机抽出一对样本（一个正样本，一个负样本），然后用训练得到的分类器来对这两个样本进行预测，预测得到正样本的概率大于负样本概率的概率。AUC为0.5表明对正例和负例没有区分能力，对于不论真实类别是1还是0，分类器预测为1的概率是相等的。

我们希望分类器达到的效果：对于真实类别为1的样本，分类器预测为1的概率（TPR）要大于真实类别为0而预测类别为1的概率（FPR），即y>x

AUC的计算方法同时考虑了分类器对于正例和负例的分类能力，在样本不平衡的情况下，依然能够对分类器作出合理的评价。

回归任务指标

均方根误差RMSE：计算预测值和实际值的平均误差

${\rm RMSE} = \sqrt{\frac{\sum_{i=1}^n (y_i-\hat{y}_i)^2}{n}}$

均方误差MSE

平均绝对误差MAE

决定系数 $R^2$

表示模型解释变量总方差的比例，反映了模型拟合的好坏。

SST: sum of squares total，总的偏差平方和，表示变量$y$相对于中心$\bar{y}$的异动。

$SST = \sum_{i=1}^n (y_i - \bar{y}_i)^2.$

SSR: sum of squares regression, 回归平方和，表示估计值 $\hat{y}$相对于中心 $\bar{y}$的异动。

$SSR = \sum_{i=1}^{n} (\hat{y}_i - \bar{y}_i)^2.$

SSE: sum of squares error, 残差平方和，表示拟合数据和原始数据之间的误差的平方和。

$SSE = \sum_{i=1}^n(y_i - \hat{y}_i)^2.$

$R^2 = 1 - \frac{\sum_{i=1}^n(y_i - \hat{y}_i)^2}{\sum_{i=1}^n(y_i - \bar{y})^2} = 1 - \frac{SSE}{SSR}.$

决定系数$R^2$的取值范围为$[0,1]$，0表示没有线性关系，1表示拟合模型可以解释所有变异y。

调整的决定系数 $\bar{R}^2$

对于决定系数 $R^2$，当解释变量个数增加（即模型复杂度提高，偏差降低）时，$R^2$ 会不断增加。但是，随着模型复杂度的提高，方差可能会越来越大。因此，引入了调整的决定系数$\bar{R}^2$：

$\bar{R}^2 = 1 - \frac{SSE/df_{err}}{SSR/df_{tot}} = 1 - （1 - R^2) \times \frac{n-1}{n-p-1},$

其中，df_{err} 表示残差平方和的自由度，为$n-p-1$，df_{tot} 表示关于总平方和的自由度，为 $n-1$。

调整后的 $\bar{R}^2$ 可以是负值，其值总是小于或等于 ${R}^2$。当引入更多解释变量时，决定系数${R}^2$会增加，导致$\bar{R}^2$的增加。但是后面的分数项会降低$\bar{R}^2$。只有当减少的偏差大于引入的方差时，$\bar{R}^2$才会增加。因此，$\bar{R}^2$ 可以看作是对 bias-variance间的tradeoff.

平均绝对百分比误差：（Mean Absolute Percentage Error, MAPE）

MAPE表示预测误差相对于真实值的百分比。

$MAPE = \frac{1}{n}\sum_{1}^{n} |\frac{y_i - \hat{y}_i}{y_i}| \times 100\%.$

优点：易于解释，特别适用于需要对误差进行相对度量的场景。缺点：当真实值接近0时，MAPE会变得不稳定。

1.6. Bias-variance trade-off，模型过拟合、欠拟合

误差分析：通过训练误差和测试误差来分析模型是否存在高方差、高偏差。

• 如果训练误差较高：说明模型的偏差较大，模型出现了欠拟合。
• 如果训练误差较低，而测试误差较高：说明模型的方差较大，出现了过拟合。
• 如果训练误差较低，测试误差也较低：说明模型的方差和偏差都适中，是一个比较理想的模型。
• 如果训练误差较高，且测试误差更高：说明模型的方差和偏差都较大。

上述分析的前提是：训练集、测试集的数据来自于同一个分布，且最优误差较小。否则讨论更复杂。

欠拟合：模型过于简单，没有很好地学习到数据间的关系，训练集效果差。模型复杂度低，此时模型预测的方差较小，表示预测较稳定。但是模型预测的偏差会较大，表示预测不准确。。

过拟合：指学习时选择的模型所包含的参数过多，以至出现这一模型对已知数据预测得很好，但对未知数据预测得很差的现象。训练集效果好，测试集效果差。 模型复杂度高，此时模型预测的方差大，偏差小。

欠拟合解决方法

1. 增加特征
2. 提高模型复杂度：神经网络提高神经元数、增加层数；SVM使用核函数；
3. 减小正则项的系数

过拟合解决方法

1. 提高样本数量。神经网络：Data Augmentation（数据增强）
2. 简化模型。神经网络使用 Dropout、Early Stopping；决策树剪枝、限制树的深度。
3. 加入正则化项（L1或L2）或提高惩罚系数
4. 使用集成学习
5. 神经网络中使用dropout机制
6. early stopping

1.7. 奥卡姆剃刀定律是什么？对机器学习模型优化有何启发？

奥卡姆剃刀定律：若有多个假设与观察一致，则选最简单的那个。

奥卡姆剃刀原理应用于模型选择时变为以下想法：在所有可能选择的模型中，能够很好地解释已知数据并且十分简单才是最好的，也就是应该选择的模型。

从贝叶斯估计的角度来看，正则化项对应于模型的先验概率。可以假设复杂的模型有较小的先验概率，简单的模型有较大的先验概率。

1.8. 线性模型 vs. 非线性模型， 生成式模型 vs. 判别式模型， 概率模型 vs. 非概率模型， 参数化模型 vs. 非参数化模型

线性模型 vs. 非线性模型

非概率模型可以分为线性模型和非线性模型。如果函数 $y=f(x)$ 或 $z = g(x)$ 是线性函数，则称模型是线性模型，否则成模型为非线性模型。

线性模型：感知机、线性支持向量机、k近邻、k均值、潜在语义分析

非线性模型：核函数支持向量机、AdaBoost，神经网络

生成式模型 vs. 判别式模型

监督学习方法分为生成方法（generative approach）和判别方法（discriminative approach）。所学习到的模型分别称为生成模型和判别模型。监督学习的模型一般形式为决策函数：$Y = f(X)$ 或者条件概率分布 $P(Y|X)$。

生成方法：由数据学习联合概率分布 $P(X,Y)$，然后求出条件概率分布 $P(Y|X)$作为预测模型：

$P(Y|X) = \frac{P(X,Y)}{P(X)}$

之所以叫做生成方法，是因为模型表示了给定输入 $X$ 产生输出 $Y$的生成关系。典型的生成模型：朴素贝叶斯法、隐马尔可夫模型。

判别方法：由数据直接学习决策函数 $f(X)$ 或者条件概率分布 $P(X,Y)$作为预测的模型，关心的是对给定的输入 $X$，应该预测什么样的输出 $Y$。典型的判别模型：k近邻、感知机、决策树、逻辑斯蒂回归、最大熵模型、支持向量机、提升方法、条件随机场。

概率模型 vs. 非概率模型

概率模型与非概率模型的区别在于模型的内在结构。概率模型一定可以表示为联合概率分布的形式，其中的变量表示输入、输出、因变量甚至参数。而针对非概率模型则不一定存在这样的联合概率分布。

统计学习的模型可以分为概率模型（probabilistic model）和非概率模型（non-probabilistic model）或者确定性模型（deterministic model）。在监督学习中，概率模型取条件概率分布形式 $p(y|x)$，非概率模型取函数形式 $y=f(x)$，其中$x$是输入，$y$是输出。在无监督学习中，概率模型取条件概率分布形式 $p(z|x)$或 $p(x|z)$，其中$x$是输入，$z$是输出。在监督学习中，概率模型是生成模型，非概率模型是判别模型。

概率模型：决策树、朴素贝叶斯、隐马尔可夫模型、条件随机场、概率潜在语义分析、潜在狄利克雷分布、高斯混合模型

非概率模型：感知机、支持向量机、k近邻、AdaBoost、k均值、潜在语义分析、神经网络

逻辑斯蒂回归即可看做概率模型，又可看做非概率模型。

参数化模型 vs. 非参数化模型

统计学习模型又可以分为参数化模型（parametric model）和非参数化模型（non-parametric model）。参数化模型假设模型参数的维度固定，模型可以由有限维参数完全刻画；非参数模型假设模型参数的维度不固定或者说无穷大，随着训练数据量的增加而不断增大。

参数化模型：感知机、朴素贝叶斯、逻辑斯蒂回归、k均值、高斯混合模型

非参数化模型：决策树、支持向量机、AdaBoost、k近邻、潜在语义分析、概率潜在语义分析、潜在狄利克雷分配

1.9. 缺失值如何处理？

1. 缺失值较多.直接将该特征舍弃掉，否则可能反倒会带入较大的噪声，对结果造成不良影响。

2. 缺失值较少,其余的特征缺失值都在10%以内，我们可以采取很多的方式来处理:（1）把NaN直接作为一个特征，假设用0表示；（离散特征取值k维扩充到k+1维）（2）用均值填充；（连续特征-均值，离散特征-特征取值的众数）（3）用随机森林等算法预测填充。

1.10. 标准化、归一化介绍

为了消除数据特征之间的量纲影响，我们需要对特征进行归一化/标准化处理，使得不同指标之间具有可比性。以梯度下降过程为例，如果不做归一化/标准化处理，在学习速率相同的情况下，大量纲变量的更新速度会大于小量纲，需要较多迭代才能找到最优解。如果将其变换到相同的数值区间后，更新速度变得更为一致，容易更快地通过梯度下降找到最优解。

1. 归一化（Min-Max Scaling）：将数据缩放到一个特定的范围（通常是 [0, 1] 或 [-1, 1]）。它的核心思想是通过线性变换，将数据映射到指定区间中。

$X_{norm} = \frac{X-X_{min}}{X_{max}-X_{min}}$

用于输入范围已知的模型（如神经网络），或者需要对距离敏感的算法（如 KNN）。不适用于有异常值的数据，例如有异常大的数值，其他数据会被压缩到很小的数值。

2. 标准化（Z-score Normalization）：是将数据进行中心化和缩放处理，使得数据的均值为 0，标准差为 1。这是通过减去数据的均值再除以数据的标准差来实现的，也叫Z-score 标准化。假设原始特征的均值为 $\mu$，方差为 $\sigma$ ，那么标准化公式定义为

$z = \frac{x-\mu}{\sigma}.$

适用于数据服从高斯分布（正态分布）或在模型中需要假设数据是标准正态分布的情况，尤其在一些线性模型（如线性回归、逻辑回归、支持向量机）和PCA等算法中较为常用。

3. 对比分析：归一化可以保持原数据的形状和分布，仅改变其取值范围，因此不会改变数据的分布类型（例如正态分布仍是正态分布）。标准化会改变了数据的中心和尺度，将数据转化为标准正态分布，因此数据的分布会被改变。

1.11. L1和L2正则，为什么L1比L2更容易产生稀疏解?

L1和L2正则，都可以防止过拟合，增强模型的泛化能力；区别在于L1使参数更稀疏，达到特征选取的作用；L2使参数更接近于0.

从解空间的形状来看： L1正则项约束后的解空间是多边形，而L2正则项约束后的解空间是圆形。而多边形的解空间更容易在尖角处与等高线碰撞出稀疏解。图中红色等高线表示不同正则参数下的残差平方和，椭圆中心点为最小二乘估计。绿色区域分别表示使用 $l_1$ 正则函数和$l_2$正则函数对应的约束域。等高线与约束域的切点表示目标函数的最优解。从图中可以看出，当使用$l_1$ 正则函数时，最优解有可能为稀疏解。

从函数叠加的观点： L2正则化使得权重衰减，降低模型复杂度，避免模型过拟合问题。（1）通过限制权重的大小，L2 正则化可以让模型更为“平滑”，即更关注输入特征的整体趋势而不是单个特征的微小变化。这降低了模型过度拟合训练数据中的噪声。（2）权重较小的模型通常更具泛化性，因为它们对数据中偶然的扰动（噪声）不太敏感。权重减小后，模型在验证集或测试集上也会有更好的表现。

2. 经典机器学习算法

2.1 线性回归和逻辑回归

线性回归

线性回归的五个基本假设条件：

1. 自变量（解释变量）与因变量（响应变量）之间为线性关系。
2. 自变量之间相互独立，无多重共线性。如果存在多重共线性，就很难确定每个预测因子的单独影响。可以通过计算皮尔逊相关系数，或者方差膨胀因子系数（VIF)进行检验。
3. 误差项之间相互独立，不存在自相关性。尤其是对时间序列数据尤为重要。可以使用DW检验。如果存在自相关性，可以采取自回归模型。
4. 误差项与自变量之间相互独立，无内生性。这一假设可确保自变量真正独立于误差项，且不会产生遗漏变量偏差。可以使用工具变量法等进行检验和处理。
5. 误差项应该呈正态分布，期望为0，方差为定值。这两个假设是为了保证回归模型在小样本下能够顺利进行假设检验，在进行假设检验（如计算 p 值或置信区间）时尤为重要。可以使用Q-Q图可视化来检验是否满足正态分布，Q-Q图趋近于落在一条直线上，说明残差满足正态分布。如果误差项的方差不是恒值（可以通过可视化残差观察到），那么存在异方差性，可以使用加权回归、稳健回归等方法解决。

关于内生变量和外生变量：与干扰项（误差项）相关的变量称为内生变量(endogenous variable)；与干扰项不相关的变量称为外生变量(exogenous variable)。对于线性回归模型，自变量会对因变量产生影响，干扰项也会对因变量产生影响，且干扰项与自变量假设无关。那么此时，自变量就是外生变量，因变量是内生变量。但是有时，可能由于某种原因，干扰项也会对因变量产生一定影响，此时干扰项和因变量相关，出现内生性。主要原因有遗漏变量、双向因果和测量误差等导致无法满足第四条假设。

线性回归模型：

$y = \beta_0 + \beta_1 x_1 + \beta_2 x_2 + ...+ \beta_p x_p + \epsilon.$

通过最小化残差平方和SSE来进行求解。最小二乘解为：

$\hat{\beta} = (X^T X)^{-1}X^T y.$

模型评估： MSE 和 决定系数 $R^2$。二者的具体定义可见section 1.5。

• 线性假设指的是模型参数的线性，而不一定是原始数据的线性。可以引入变换或非线性特征（如交叉项 $x_1 \times x_2$、多项式项 $x_1^2$），只要因变量与参数之间的关系保持线性即可。此时加入非线性特征（如交叉特征或多项式项）并不违反线性回归的假设，因为模型的参数仍然是 “线性的”。

多重共线性

当线性回归模型中的两个或多个自变量高度相关，导致信息重叠或冗余时，就会产生多重共线性。在这种情况下，模型很难分离出每个自变量对因变量的单独影响，从而导致不可靠的系数估计、标准误差膨胀以及解释上的挑战。

如何检测和解决多重共线性问题？

1. 方差膨胀因子 (VIF)：VIF 是一种常见的诊断工具，用于衡量回归系数的方差因多重共线性而膨胀的程度。VIF 超过 5 或 10 表示多重共线性很高。
2. 相关矩阵：检查自变量的相关矩阵可以发现高度相关的变量对（相关性接近 1 或-1）。这表明存在潜在的多重共线性。
3. 放弃其中一个相关变量：如果两个或多个变量高度相关，可考虑放弃其中一个变量。这可以简化模型并减少多重共线性。
4. 主成分分析（PCA）：PCA 可以将相关变量转化为一组不相关的成分，用于回归分析。这可以降低数据维度，避免多重共线性。
5. 岭回归或lasso回归：这些正则化技术有助于减轻多重共线性的影响。岭回归会对系数的大小进行惩罚，从而降低系数对多重共线性的敏感性（不具备变量筛选的能力，无法完全解决）。lasso回归则更进一步，可以将某些系数缩减为零，从而有效地选择预测因子的子集。

逻辑回归

逻辑回归是一种广泛用于二元分类任务的监督学习算法。在机器学习中，监督学习包括对输入输出对进行模型训练，以学习能够预测未见数据的模式。逻辑回归专门预测基于输入特征的分类结果的概率，其中结果属于两个类别之一。虽然逻辑回归可以扩展到多个类别，但其最常见的应用还是二元分类。

逻辑回归模型：

$p(y = 1 | x) = sigmoid(z) = \frac{1}{1 + e^{-z}}, z = {\beta}_0 + {\beta}_1 x_1 + ...+ {\beta}_k x_k.$

模型评估

逻辑回归模型使用损失函数进行评估，该函数用于衡量模型预测真实结果的能力。对于二元分类，合适的损失函数是 Log-Loss（也称为二元交叉熵）。对于有 $n$ 个样本的给定数据集，Log-Loss 的定义为:

$Log-loss = - \sum_{i=1}^{n} [y_i \log p_i + (1-y_i)\log (1-p_i)],$

其中，$y_i$ 为第$i$个样本的真实标签，$p_i$ 为第$i$个样本的输出概率。

系数估计算法

有两种主流的方式去估计模型的参数 ${\beta}$，（1）梯度下降；（2）最大似然估计（MLE).

最大似然估计：对于逻辑回归，定义函数 $h_{\beta}(x) = \frac{1}{1 + e^{-z}}$，其似然函数为所有样本观测值出现概率的乘积，可以表示为：

$L(\beta) = \prod_{i=1}^{n} [h_{\beta}(x_i)]^{y_i}[1 - h_{\beta}(x_i)]^{(1-y_i)}.$

最大化该似然函数，通常会转化为最大化其对数似然，然后用梯度下降法求解。对数似然函数为：

$\log L(\beta) = \sum_{i=1}^{n} [y_i \log h_{\beta}(x_i)+(1-y_i)\log(1 - h_{\beta}(x_i))].$

显然，最大化对数似然等价于最小化log-loss。

多标签分类：假设每个样本属于不同标签的概率服从几何分布，可以使用softmax regression进行分类：

$h_\theta = \left[ \begin{matrix} p(y=1|x;\theta)\\ p(y=2|x;\theta) \\ \vdots \\ p(y=k|x;\theta) \end{matrix} \right] = \frac{1}{\sum_{j=1}^{k} e^{\theta^T x}} \left[ \begin{matrix} e^{\theta_1^T x}\\ e^{\theta_2^T x} \\ \vdots \\ e^{\theta_k^T x} \end{matrix} \right] \tag{3}$

其中 $\theta_1,\theta_2 \dots,\theta_k \in \mathbb{R}^n$

如果存在样本可能属于多个标签的情况时，可以训练k个二分类的逻辑回归分类器。第i个分类器用以区分每个样本是否可以归为第i类。

二者之间的联系

如果把一个事件的几率（odds）定义为该事件发生的概率与不发生概率的比值 $\frac{p}{1-p}$ ，那么逻辑回归可以看做是对于"y=1|x"这一事件的对数几率的线性回归

${\rm log} \frac{p}{1-p} = \theta^{T}x ，其中\ p = P(y=1|x).$

2.2. K-近邻算法（K-Nearest Neighbors，KNN）

K-近邻算法（KNN）是一种监督学习算法，主要用于分类和回归问题。KNN 是一种基于实例的学习方法，其核心思想是：给定一个未标记的样本，找到与该样本最相似的 $k$ 个已知标签的样本（最近邻居），然后通过这些邻居的类别信息进行预测。
KNN 适合小数据集的分类和回归任务。然而，随着数据规模的增长和维度的增加，KNN 的计算成本和性能都会变得较差，因此在实际应用中常结合其他优化技术使用，比如 KD 树、Ball 树等。

计算流程

1. 数据预处理：对于每个输入样本，首先需要进行标准化或归一化操作，确保不同特征值处于相同的数值范围，否则距离计算时可能会被某些特征主导。

2. 计算距离：对新的测试样本，基于某一距离标准，计算它与所有训练样本之间的距离。

3. 选择K值：选择一个合适的 $k$ 值（即考虑的邻居数量），通常是一个正整数。较小的 $k$ 可能导致模型过拟合，较大的 $k$ 则可能导致模型过于平滑。

4. 选择最近的K个邻居：根据距离计算的结果，选择离测试样本最近的 $k$ 个训练样本。

5. 进行投票或加权：

   • 分类问题：通过这 $k$ 个最近邻居的类别进行投票，选择出现最多的类别作为预测结果。
   • 回归问题：通过这 $k$ 个最近邻居的数值标签，通常取它们的均值或加权平均值作为预测结果。

6. 输出预测结果：得到最终预测值，完成预测。

在实际应用中，$k$ 值一般取一个比较小的数值，例如采用交叉验证法来选择最优的 $k$ 值。

优点

1. 简单易懂：KNN 不需要进行复杂的模型训练，只需要存储所有训练数据，直观易理解。

2. 无参数学习：KNN 不假设数据的分布情况，它是一种非参数学习方法，因此对数据的分布形式没有要求。

3. 灵活性强：可以用于分类和回归问题，距离度量方法也可以根据实际需要灵活更改。

4. 增量学习：KNN 可以适应动态变化的数据集，因为新样本只需要加入到训练集中即可，不需要重新训练模型。

缺点

1. 计算量大：每次预测都需要计算新样本与所有训练样本之间的距离，因此计算开销大，特别是在样本数量多时，效率较低。

2. 高维数据效果较差：在高维空间中，数据变得稀疏，“距离"的直观意义减弱，KNN 在高维数据下表现通常不佳，这就是所谓的"维度灾难”。

3. 对数据量敏感：KNN 对噪声和异常值敏感，噪声点可能严重影响最终的分类结果，尤其在 $ k $ 值较小的情况下。

4. 对特征缩放敏感：不同特征的量纲差异可能会导致某些特征主导距离计算，因此需要对数据进行标准化或归一化处理。

常用的距离衡量公式

1. 闵可夫斯基距离

假设特征空间 $\mathcal X$ 是n维实数向量空间 $\mathbf{R}^n$ ，$x_i, x_j \in \mathcal{X}, x_i = (x_i^{(1)}, x_i^{(2)},\cdots x_i^{(n)} ), x_j = (x_j^{(1)}, x_j^{(2)}, \cdots, x_j^{(n)})$ 。则 $x_i, x_j$ 的 $L_p$ 距离（闵可夫斯基距离）定义为

$L_p(x_i, x_j) = (\sum_{l=1}^n |x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}}, \quad p \geq 1.$

2. 欧式距离

当闵可夫斯基距离公式中 $p=2$ 时，称为欧氏距离，用来衡量两点在多维空间中的直线距离，是严格定义的距离，满足正定性、对称性、三角不等式。

$L_2(x_i, x_j) = (\sum_{l=1}^n |x_i^{(l)}-x_j^{(l)}|^2)^{\frac{1}{p}}.$

欧式距离对较大的差异很敏感，如果某个特征值差异大，欧氏距离会受到很大影响，因此数据常需要进行归一化或标准化。

3. 曼哈顿距离

当闵可夫斯基距离公式中 $p=1$ 时，称为曼哈顿距离，用于衡量点与点之间的坐标差异之和，即从一个点到另一个点走直角路径的总距离。

$L_1(x_i, x_j) = \sum_{l=1}^n |x_i^{(l)}-x_j^{(l)}|.$

曼哈顿距离通常用于街区格子的路径计算，模拟只能沿着水平和垂直方向移动的场景。在高维空间中，由于它对特征值间差异的处理方式相对温和，因此它可能比欧氏距离对噪声更加鲁棒。

4. 切比雪夫距离

当 $p = \infty$ 时，称作切比雪夫距离。两个向量各个坐标距离数值差的绝对值的最大值。

$L_{\infty}(x_i, x_j) = \mathop{\max}_{l} \ |x_i^{(l)}-x_j^{(l)}|.$

切比雪夫距离对数据的最大变化特别敏感。

5. 马氏距离

考虑各个分量（特征）之间的相关性并与各个分量的尺度无关。给定一个样本集合 $X$，$X=(x_{ij})_{m\times n}$，其协方差矩阵记为 $S$。样本 $x_i$ 与样本 $x_j$ 之间的马氏距离 $d_{ij}$ 定义为

$d_{ij} = [(x_i - x_j)^TS^{-1}(x_i - x_j)]^{\frac{1}{2}}.$

当 $S$ 为单位矩阵时，即样本数据的各个分量互相独立且各个分量的方差为1时，马氏距离就是欧氏距离。

马氏距离不仅考虑了点与点之间的距离，还考虑了特征之间的相关性（通过协方差矩阵），适合特征相关性较强的场景，在这些情况下比欧氏距离更加准确。

6. 汉明距离

汉明距离用于衡量两个等长的二进制向量或字符串之间有多少位不相同。换句话说，它表示两个字符串之间的不同字符个数。通常用于编码、错误检测与纠正等领域。

对于两个长度相同的二进制序列 $ p $ 和 $ q $，汉明距离的定义为：

$d(p, q) = \sum_{i=1}^{n} \delta(p_i, q_i).$

其中，$ \delta(p_i, q_i) $ 为指示函数，当 $ p_i \neq q_i $ 时，$ \delta(p_i, q_i) = 1 $，否则 $ \delta(p_i, q_i) = 0 $。

1011101 与 1001001 之间的汉明距离是 2。

2143896 与 2233796 之间的汉明距离是 3。

“toned” 与 “roses” 之间的汉明距离是 3。

7. 相关系数（correlation coefficient）

相关系数用于衡量两个向量或变量之间的线性相关性。它的值范围在 $[-1, 1]$ 之间：

• $ 1 $ 表示完全正相关；
• $ -1 $ 表示完全负相关；
• $ 0 $ 表示没有线性关系。

最常用的相关系数是皮尔逊相关系数（Pearson Correlation Coefficient）。
$x_i$ 与 $x_j$ 之间的相关系数定义为

$r_{ij} = \frac{\sum_{k=1}^{m}\left(x_{k i}-\overline{x}_{i}\right)\left(x_{k j}-\overline{x}_{j}\right)}{\left[\sum_{k=1}^{m}\left(x_{k i}-\overline{x}_{i}\right)^{2} \sum_{k=1}^{m}\left(x_{k j}-\overline{x}_{j}\right)^{2}\right]^{\frac{1}{2}}}.$

$\overline{x}_{i}=\frac{1}{m} \sum_{k=1}^{m} x_{k i}, \quad \overline{x}_{j}=\frac{1}{m} \sum_{k=1}^{m} x_{k j}$

8. 余弦相似度

余弦相似度用于衡量两个向量之间的夹角，它用于计算两个向量在方向上的相似性，而不是在大小上的相似性。不是严格定义的距离，满足正定性、对称性，不满足三角不等式。
余弦相似度的取值范围在 $[-1, 1]$ 之间:

• 1 表示两个向量完全相同（方向一致）；
• 0 表示两个向量正交（没有相似性）；
• -1 表示两个向量方向完全相反。

公式定义为：

$cos(A,B) = \frac{A \cdot B}{||A||_2 ||B||_2}.$

使用场景

1. 欧氏距离：适合维度较低、特征彼此独立且已归一化的数据。计算点与点之间的"直线距离"。

2. 曼哈顿距离：当特征值的分布差异较大或者关注的是各维度变化总和时效果较好。用于计算只能沿着水平和垂直方向的移动（如城市网格或棋盘）。

3. 闵可夫斯基距离：通用的度量方式，适合需要灵活调整距离公式的场景。

4. 切比雪夫距离：适合在某些场景下只关心各坐标轴的最大差异，如国际象棋中的"国王路径"问题。

5. 马氏距离：适用于多维数据且特征之间存在相关性，考虑数据的分布情况。

6. 汉明距离：适用于二进制向量或字符串的比较，主要衡量离散值之间的差异。

7. 相关系数：用于衡量两个数值变量的线性相关性，适合线性关系的分析。

8. 余弦相似度：用于评估向量之间的方向相似性，广泛用于文本处理和推荐系统中。

2.3. 支持向量机（SVM，Support Vector Machine）

支持向量机（SVM）是一种监督学习算法，主要用于分类和回归问题，尤其擅长处理二分类问题。
它的基本模型是定义在特征空间的间隔最大的线性分类器。SVM 尝试在多维空间中找到一个超平面，将不同类别的数据点分开。在许多情况下，数据是线性不可分的，因此 SVM 通过将数据映射到高维特征空间，使得在这个新空间中可以找到一个线性可分的超平面。

• 线性可分支持向量机：当训练数据线性可分，通过硬间隔最大化，学习一个线性的分类器

• 线性支持向量机：当训练数据近似线性可分，通过软间隔最大化，学习一个线性的分类器

• 非线性支持向量机：当训练数据线性不可分，通过使用核技巧及软间隔最大化，学习非线性分类器

超平面与支持向量

• 超平面：在二分类问题中，超平面是将数据点划分为两类的决策边界。在二维空间中，超平面是一个直线；在三维空间中，超平面是一个平面；在更高维的情况下，超平面是一个 $n-1$ 维的结构。

• 支持向量：支持向量是距离超平面最近的数据点。SVM 通过这些支持向量来定义和构建超平面，因此它们对决策边界的确定具有重要作用。

• 间隔（Margin）：SVM 的核心思想是找到一个能最大化间隔的超平面，即使得支持向量到超平面的距离最大化。间隔越大，模型的泛化能力越强。

线性可分 SVM

在线性可分的情况下，SVM 寻找的是能够完全分离两类数据的超平面。给定一组训练样本 ${(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)} $，其中 $ x_i \in \mathbb{R}^n $ 是样本，$ y_i \in {-1, 1} $ 是类别标签，SVM 要找到的超平面可以表示为：

$w \cdot x + b = 0,$

其中，$ w $ 是超平面的法向量，$ b $ 是偏移量。为了使超平面将两类数据完全分开，我们希望满足以下约束条件：

• 对于 $ y_i = 1 $ 类别的点，要求 $ w \cdot x_i + b \geq 1 $。
• 对于 $ y_i = -1 $ 类别的点，要求 $ w \cdot x_i + b \leq -1 $。

对于一个点 $ x $，它到超平面 $ w \cdot x + b = 0 $ 的几何距离可以表示为：

$d(x, \text{hyperplane}) = \frac{|w \cdot x + b|}{\|w\|}.$

对于支持向量 $ x_i $，它们距离超平面最近，因此满足 $ w \cdot x_i + b = \pm 1 $ 的约束。
两个类别的支持向量分别位于 $ w \cdot x + b = 1 $ 和 $ w \cdot x + b = -1 $ 的平面上。

间隔（即两个支持向量之间的距离）可以表示为两个支持向量平面之间的距离：

$\text{Margin} = \frac{|1 - (-1)|}{\|w\|} = \frac{2}{\|w\|}$

SVM 的目标就是最大化间隔，等价于最小化 $ |w| $。最终的优化问题可以写作：

$\min \frac{1}{2} \|w\|^2 \quad \text{s.t.} \quad y_i (w \cdot x_i + b) \geq 1, \, \forall i$

线性不可分 SVM

在很多实际场景中，数据并非线性可分。此时，我们可以引入软间隔（Soft Margin），允许一些数据点出现在错误的侧面，从而使模型更具弹性。
为了处理这种情况，SVM 引入了松弛变量 $ \xi_i $，允许某些数据点不满足分类约束条件。优化问题变为：

$\min \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{n} \xi_i \quad \text{s.t.} \quad y_i (w \cdot x_i + b) \geq 1 - \xi_i, \, \xi_i \geq 0,$

其中，$C$ 是一个正的常数，用于控制间隔大小和分类错误惩罚之间的权衡。较大的 $ C $ 值会导致模型更加关注分类准确性，忽略间隔；较小的 $ C $ 值则更关注间隔大小，允许更多的分类错误。

通过拉格朗日乘子法，将 SVM 原始问题中的约束优化问题转化为对偶形式的二次规划问题。使用二次规划求解器或 SMO 算法求解对偶问题。

$\max_{\alpha} \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j).$

$\text{s.t.} \quad \sum_{i=1}^{n} \alpha_i y_i = 0, \quad 0 \leq \alpha_i \leq C.$

对于训练一个不加入松弛变量的SVM模型时，训练误差为0的SVM分类器一定存在。对于加入松弛变量的SVM的训练误差不一定能达到0。

核方法（Kernel Trick）

在处理非线性分类问题时，直接在原始特征空间中很难找到线性可分的超平面。SVM 通过核方法（Kernel Trick）将原始数据映射到一个高维空间，在这个空间中数据可以线性分离。

核函数定义：设 $\mathcal{X}$ 是输入空间，又设 $\mathcal{H}$ 为特征空间，如果存在一个从 $\mathcal{X}$到 $\mathcal{H}$ 的映射

$\phi(x) : \mathcal{X} \rightarrow \mathcal{H}$

使得对所有$x, z \in \mathcal{X}$，函数$K(x, z)$满足条件

$K(x, z)=\phi(x) \cdot \phi(z)$

则称 $K(x, z)$为核函数，$\phi(x)$ 为映射函数，式中 $\phi(x) \cdot \phi(z)$ 为 $\phi(x)$ 和 $\phi(z)$的内积。

在对偶问题中，可以将 $x \cdot z$ 中的数据分别进行变换，即 $\phi(x) \cdot \phi(z)$。为方便计算，可以直接使用核函数 $K(x, z)$ 代替。

线性核函数

$K(x,z) = x \cdot z$

主要用于线性可分的情况。可以看到特征空间到输入空间的维度是一样的，其参数少速度快，对于线性可分数据，其分类效果很理想，因此我们通常首先尝试用线性核函数来做分类，看看效果如何，如果不行再换别的。

多项式核函数（polynomial kernel function）

$K(x, z)=(x \cdot z+1)^{p}$

对应的支持向量机是一个p次多项式分类器。分类决策函数为

$f(x)=\operatorname{sign}\left(\sum_{i=1}^{N_{s}} a_{i}^{*} y_{i}\left(x_{i} \cdot x+1\right)^{p}+b^{*}\right)$

其中 $x$ 是待分类样本。
多项式核函数可以实现将低维的输入空间映射到高维的特征空间，但是多项式核函数的参数多，当多项式的阶数比较高的时候，核矩阵的元素值将趋于无穷大或者无穷小，计算复杂度会大到无法计算。

高斯核函数（Gaussian kernel function）

$K(x,z) = exp(-\frac{1}{2} \ ||x - z ||_2 ) = \phi(x) \cdot \phi(z)$

对应的支持向量机是高斯径向基函数（radial basis function）分类器，分类决策函数为

$f(x)=\operatorname{sign}\left(\sum_{i=1}^{N_{s}} a_{i}^{*} y_{i} \exp \left(-\frac{\|x-x_i\|^{2}}{2 \sigma^{2}}\right)+b^{*}\right)$

高斯径向基函数是一种局部性强的核函数，其可以将一个样本映射到一个更高维的空间内，该核函数是应用最广的一个，无论大样本还是小样本都有比较好的性能，而且其相对于多项式核函数参数要少。

Sigmod核函数

$K\left(x, z\right)=\tanh \left(\eta \ x \cdot z +\theta\right)$

核方法的关键在于，我们无需显式地将数据映射到高维空间，而是通过核函数直接在原始空间中计算高维空间的内积，从而实现非线性分类。

优缺点

优点：

• 高效处理高维数据：SVM 在高维空间中仍能表现良好，尤其是使用核方法时可以处理复杂的非线性分类问题。
• 强大的泛化能力：通过最大化间隔，SVM 通常能够很好地避免过拟合问题，具有良好的泛化性能。
• 对少量样本较为有效：即使在样本量较小的情况下，SVM 也能表现出色，因为它只关注支持向量而非所有样本点。

缺点：

• 对大规模数据集的效率较低：由于 SVM 的复杂度较高，在处理非常大规模的数据集时，训练时间可能较长。
• 对核函数的选择敏感：选择不恰当的核函数可能导致模型性能不佳，且参数（如 $ C $ 和 $ \sigma $）需要精心调优。
• 不适合噪声数据：SVM 对噪声敏感，尤其是在数据中有重叠或混合时，模型可能表现不稳定。
• 仅支持二分类问题：原生的 SVM 是二分类模型，虽然可以通过某些策略扩展到多分类（如一对一、多对多方法），但相对其他多分类算法显得复杂。

SVM 和 感知机的区别

• 感知机的目标是找到一个可以将数据点分开的线性超平面，即将两类数据点尽可能正确地划分。感知机的训练过程是通过逐步调整权重来消除分类错误，直到找到一个可以完全分类的数据超平面。它不考虑分类间隔。SVM 不仅要求找到一个分离超平面，还要找到能**最大化分类间隔（margin）**的超平面。最大化间隔可以使模型具有更好的泛化能力，因此 SVM 的目标是找到分类超平面并且使到支持向量的间隔最大化。

• 感知机使用的是误分类驱动的梯度下降法，即每次在出现误分类时更新权重，直到所有数据点都被正确分类。SVM 通过凸优化技术，直接求解带约束的优化问题。其目标函数是最大化分类间隔，通常通过拉格朗日对偶优化或二次规划求解，或者通过梯度下降法结合核方法来求解非线性问题。

• 感知机的泛化能力较弱，它只要找到一个可以完全分离数据的超平面即可，但在实际应用中可能会过拟合。SVM 最大化间隔的策略使得它对噪声和过拟合有更强的抗性，泛化能力更强。尤其是在小样本或高维数据下，SVM 的表现优于感知机。

• 感知机不考虑数据的线性不可分性，如果数据是线性不可分的，它将无法收敛。SVM 可以通过引入软间隔处理线性不可分的情况，允许一些数据点处于错误的一侧。此外，SVM 可以通过**核技巧（Kernel Trick）**将数据映射到高维空间，在高维空间中实现线性分离。

2.4. 朴素贝叶斯模型

朴素贝叶斯（Naive Bayes）模型是一种基于贝叶斯定理的简单而高效的分类算法，广泛应用于文本分类、垃圾邮件检测、情感分析等任务。它在假设特征之间相互独立的前提下进行分类，尽管这一假设在现实中通常不成立，但朴素贝叶斯在许多实际应用中表现仍然相当好。

贝叶斯定理

朴素贝叶斯模型的基础是贝叶斯定理，该定理描述了在给定某些证据的情况下，如何计算某个事件发生的概率。贝叶斯定理的公式如下：

$P(C|X) = \frac{P(X|C) \cdot P(C)}{P(X)},$

其中：

• $ P(C|X) $：给定特征 $ X $ 时类别 $ C $ 发生的后验概率；
• $ P© $：类别 $ C $ 的先验概率，即在没有观察到特征 $ X $ 时类别 $ C $ 发生的概率；
• $ P(X|C) $：给定类别 $ C $ 时，特征 $ X $ 发生的概率，即似然函数；
• $ P(X) $：特征 $ X $ 的边缘概率，即所有类别中特征 $ X $ 发生的概率。

朴素贝叶斯分类器

朴素贝叶斯模型被称为“朴素”的原因是它基于一个朴素的独立假设，即假设所有特征 $ X = [X_1, X_2, \ldots, X_n] $ 之间是相互独立的，给定类别 $ C $ 时，特征之间没有相关性。根据这一假设，贝叶斯定理中的 $ P(X|C) $ 可以简化为：

$P(X|C) = P(X_1|C) \cdot P(X_2|C) \cdot \ldots \cdot P(X_n|C)$

即特征的联合概率可以表示为每个特征条件概率的乘积。

基于上述假设，朴素贝叶斯分类器的目标是对于每个类别 $ C $，计算后验概率 $ P(C|X) $，并选择概率最大的类别作为预测结果：

$\hat{C} = \arg\max_C P(C|X) = \arg\max_C P(C) \prod_{i=1}^{n} P(X_i|C)$

朴素贝叶斯模型之所以被认为是线性分类器，主要是因为它在对数空间下，分类决策边界呈现为一个线性函数。

后验概率最大化的含义是什么？

朴素贝叶斯法将实例分到后验概率最大的类中。后验概率最大化这等价于期望风险最小化。

假设选择0-1损失函数：

$L(Y, f(X))=\left\{ \begin{array} {ll}{1,} & {Y \neq f(X)} \\ {0,} & {Y=f(X)} \end{array} \right.$

其中 $f(X)$是分类决策函数。这是期望风险函数为

$R_{\operatorname{cap}}(f)=E[L(Y, f(X))]$

期望是对联合分布 $P(X,Y)$ 取的。由此取条件期望

$R_{\mathrm{exp}}(f)=E_{X} \sum_{k=1}^{K}\left[L\left(c_{k}, f(X)\right)\right] P\left(c_{k} | X\right)$

为了使期望奉献最小化，只需对 $X=x$ 逐个最小化，由此得到

$\begin{aligned} f(x) &=\arg \min _{y \in \mathcal{Y}} \sum_{k=1}^{K} L\left(c_{k}, y\right) P\left(c_{k} | X=x\right) \\ &=\arg \min _{y \in \mathcal{Y}} \sum_{k=1}^{K} P\left(y \neq c_{k} | X=x\right) \\ &=\arg \min _{y \in \mathcal{Y}}\left(1-P\left(y=c_{k} | X=x\right)\right) \\ &=\arg \max _{y \in \mathcal{Y}} P\left(y=c_{k} | X=x\right) \end{aligned}$

这样一来，根据期望风险最小化准则就得到了后延概率最大化准则：

$f(x)=\arg \max _{c_{k}} P\left(c_{k} | X=x\right)$

即朴素贝叶斯法所采用原理

朴素贝叶斯的三种常见类型

根据特征的不同类型，朴素贝叶斯模型可以分为几种常见的变体：

1. 高斯朴素贝叶斯（Gaussian Naive Bayes）

当特征是连续值时，假设特征符合正态分布（高斯分布）。对于每个类别 $ C $，特征的条件概率 $ P(X_i|C) $ 可以用以下正态分布的概率密度函数表示：

$P(X_i|C) = \frac{1}{\sqrt{2\pi\sigma_C^2}} \exp\left( -\frac{(X_i - \mu_C)^2}{2\sigma_C^2} \right),$

其中，$ \mu_C $ 和 $ \sigma_C $ 是特征 $ X_i $ 在类别 $ C $ 下的均值和标准差。

1. 多项式朴素贝叶斯（Multinomial Naive Bayes）

用于离散值特征，特别适合处理文本分类任务。假设每个特征是某个离散事件发生的次数或频率。此时，条件概率 $ P(X_i|C) $ 被建模为多项式分布：

$P(X_i|C) = \frac{N_{i,C} + 1}{N_C + |V|},$

其中：

• $ N_{i,C} $ 是类别 $ C $ 中特征 $ X_i $ 出现的次数；
• $ N_C $ 是类别 $ C $ 中所有特征的总和；
• $ |V| $ 是特征词汇表的大小（加 1 处理为拉普拉斯平滑）。

3. 伯努利朴素贝叶斯（Bernoulli Naive Bayes）

适用于二元离散特征，即特征值仅为 0 或 1（表示特征是否存在）。这在文本分类中常用于二元词袋模型（Binary Bag of Words），其中每个词的出现与否作为特征：

$P(X_i|C) = p_C^{X_i} (1 - p_C)^{(1 - X_i)},$

其中，$ p_C $ 是特征 $ X_i $ 在类别 $ C $ 中的概率。

训练过程

1. 计算先验概率：先验概率 $ P© $ 可以通过类别 $ C $ 在训练集中出现的频率估计：

$P(C) = \frac{\text{样本中类别 } C \text{ 的数量}}{\text{样本总数}}$

2. 计算条件概率：对于每个特征 $ X_i $，计算它在类别 $ C $ 下的条件概率 $ P(X_i|C) $。根据具体任务的不同，这个概率可能通过频率估计或假设的分布（如高斯分布）来计算。

3. 构建分类器：利用贝叶斯定理，将计算得到的条件概率和先验概率结合在一起，构建分类模型。

优缺点

优点：

• 简单高效：模型非常简单，易于实现，尤其适用于高维数据。
• 计算速度快：训练和预测的计算开销很小，适合大规模数据集。
• 对小数据集有效：朴素贝叶斯模型对小数据集通常表现良好。
• 处理缺失数据：可以轻松处理部分特征缺失的样本。
• 适合文本分类：在文本分类任务中，朴素贝叶斯模型表现良好，常用于垃圾邮件分类、情感分析等任务。

缺点：

• 特征独立性假设不现实：朴素贝叶斯的独立性假设通常在现实数据中不成立，导致模型性能可能受到影响。
• 对稀有类别敏感：如果某一类别中某个特征从未出现过（即其条件概率为 0），模型可能会错误地认为该类别不可能发生。这可以通过拉普拉斯平滑来缓解。
• 无法处理复杂关系：由于假设特征之间相互独立，朴素贝叶斯无法处理特征之间复杂的依赖关系。

贝叶斯网络

朴素贝叶斯法假设输入变量都是条件独立的，如果假设它们之间存在概率依存关系，模型就被成了贝叶斯网络。
贝叶斯网络也称为“信念网”，借助有向无环图来刻画属性之间的依赖关系，并使用条件概率表来描述属性的联合概率分布。贝叶斯网结构有效地表达了属性的条件独立性。

具体来说，一个贝叶斯网B由结构 $G$ 和参数 $\theta$ 表示，即 $B = <G,\theta>$ 。网络结构G是一个有向无环图，其每个节点对应于一个属性，若两个属性有直接依赖关系，则它们由一条边连接起来；参数 $\theta$ 定量描述这种依赖关系，假设属性 $x_i$ 在G中的父节点集为 $\pi_i$，则 $\theta$包含了每个属性的条件概率 $\theta_{x_i|\pi_i} = P_B(x_i|\pi_i)$。

给定父节点集，贝叶斯网假设每个属性与它的非后裔属性独立，于是将属性的联合概率分布定义为

$P_{B}\left(x_{1}, x_{2}, \ldots, x_{d}\right)=\prod_{i=1}^{d} P_{B}\left(x_{i} | \pi_{i}\right)=\prod_{i=1}^{d} \theta_{x_{i} | \pi_{i}}$

贝叶斯网的一个核心概念是条件独立性。通过有向无环图，可以直接可视化出哪些变量在条件下是独立的。具体来说，贝叶斯网通过图的结构来表示变量之间的条件独立性，简化联合概率的计算。

• 父子节点之间的依赖性：每个节点依赖于它的父节点。
• 马尔可夫性：给定某个节点的父节点，节点与其非后代节点条件独立。

贝叶斯网的推断可以通过多种算法实现，常见的推断算法包括：

• 精确推断：如变量消去算法（Variable Elimination）、信念传播算法（Belief Propagation）。
• 近似推断：如马尔可夫链蒙特卡罗方法（Markov Chain Monte Carlo, MCMC）和粒子过滤（Particle Filtering）。

2.5. 决策树（Decision Tree）

决策树是一种监督学习算法，广泛用于分类和回归任务。决策树通过一系列的特征划分逐步将数据集分成不同的子集，从而生成树状的结构，最终可以对输入样本进行分类或预测。其结构类似于树形图，由节点和分支组成：

• 根节点（Root Node）：包含整个数据集，代表模型开始进行决策的地方。
• 内部节点（Internal Nodes）：表示根据某个特征进行的决策（如按年龄划分，收入划分等）。
• 叶节点（Leaf Nodes）：代表最终的输出（分类标签或回归值）。

建树过程

1. 选择划分特征。 在每一步，决策树会选择一个最优特征将数据集划分成若干子集。这个选择标准可以是信息增益、基尼系数等。

2. 划分数据集。 选择最优的特征后，数据集被划分为若干子集。决策树的每一个子节点对应一个划分后的子集。

3. 递归地构建子树。 对于每个子节点，重复第1步和第2步，直到满足停止条件。停止条件一般有以下几种：

• 节点的所有样本属于同一类别（即纯节点）。
• 达到树的最大深度。
• 节点中的样本数量少于某个阈值。

4. 生成叶节点。 当递归停止时，生成叶节点，叶节点代表最终的决策结果（分类标签或回归值）。

决策树生成的算法

1. ID3算法（Iterative Dichotomiser 3）。 该算法使用信息增益作为选择特征的标准，选择信息增益最大的特征进行划分。

2. C4.5算法。 这是ID3算法的改进版本，使用信息增益比作为划分标准，以避免ID3算法偏向多值特征的问题。

3. CART算法（Classification and Regression Tree）。 适用于分类和回归问题。对于分类任务，CART使用基尼指数选择特征；对于回归任务，使用最小方差来进行划分。

决策树的剪枝

通过剪枝防止过拟合。

预剪枝是指在决策树生成的过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分，并将当前节点标记为叶子节点；此时可能存在不同类别的样本同时存于同个节点中，按照多数投票的原则判断节点所属类别

预剪枝对于何时停止决策树的生长：

1. 当树达到一定深度

2. 当到达当前节点的样本数量小于某个阈值

3. 计算每次分裂对测试集的准确度提升，小于某个阈值时停止

后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶子节点进行考察，若该节点对应的子树替换成叶子结点能带来泛化性能提升，则将该子树替换为叶子节点。

熵、联合熵、条件熵、KL散度、信息增益、信息增益比、gini系数

熵

熵（entropy）是表示随机变量不确定性的度量， $X$ 是一个取有限个值的离散随机变量，其概率分布为

$P(X = x_i) = p_i, \ i=1,2,\cdots,n$

则随机变量 $X$ 的熵定义为

$H(X) = -\sum_{i=1}^{n} p_i {\rm log } \ p_i$

熵越大，随机变量的不确定性就越大。

而熵其实表示的是一个系统的平均信息量。自信息量是用来描述某一事件带来的信息量大小

$I = - {\rm log} \ p_i$

通常以2为底，单位是bit；事件的概率越低，那么该事件发生时带来的信息量越大。而通常我们衡量整个系统的信息量，系统存在多个事件 $X=\{x_1,\cdots,x_n\}$ ，每个事件的概率分布$P=\{p_1,\cdots,p_n\}$ ，熵是整个系统的平均信息量 。

联合熵：将一维随机变量分布推广到多维随机变量分布

$H(X,Y) = -\sum\limits_{x,y} p(x,y)\ {\rm log}\ p(x,y)$

条件熵：某个特征A对于数据集D的经验条件熵 $H(D|A)$ 为

$H(D|A) = - \sum_{i=1}^{n} \frac{|D_i|}{|D|} H(D_i) \\ = - \sum_{i=1}^{n} \frac{|D_i|}{|D|} \lgroup \sum_{k=1}^{K} \frac{|D_{ik}|}{|D_i|} {\rm log } \frac{|D_{ik}|}{|D_i|} \rgroup$

信息增益： $g(D,A)$ 定义为数据集D的经验熵 $H(D)$ 与特征A给定条件下D的经验条件熵 $H(D|A)$ 的差

$g(D,A) = H(D) - H(D|A)$

信息增益比：特征A对于数据集D 的信息增益比定义为

$g_R(D|A) = \frac{g(D|A)}{H_A(D)}$

其中

$H_A{(D)} = - \sum_{i=1}^{n} \frac{|D_i|}{|D|} {\rm log } \frac{|D_i|}{|D|}$

为数据集D关于A的取值熵；n为特征A在D上的取值数目；

Gini系数：描述数据的不确定性。数据集D的Gini系数为

${\rm Gini}(D) = 1 - \sum_{k=1}^{K }(\frac{|C_k|}{|D|})^2$

其中 $C_k$是 D中第k类的样本子集，K是类的个数。例如二分类问题，K=2。基尼系数越大，样本集合的不确定性也就越大，这一点与熵相似。基尼系数Gini(D,A)表示经A=a分割后集合D的不确定性。

交叉熵：刻画两个概率分布之间的距离，通过q来表示p的交叉熵为；一般p(x)为真实分布，q(x)为预测分布

交叉熵不对称。交叉熵越小，概率分布越接近

$H(p,q) = - \sum\limits_{x} p(x) {\rm log } \ q(x)$

KL散度/相对熵

$D_{K L}(p \| q)=\sum_{i=1}^{n} p\left(x_{i}\right) \log \left(\frac{p\left(x_{i}\right)}{q\left(x_{i}\right)}\right)$

n表示事件可能发生的情况总数，KL散度的值越小表示两个分布越接近。

$D_{KL}(p||q) = H(p,q) - H(p)$

机器学习中，我们常常使用KL散度来评估predict和label之间的差别，但是由于KL散度的后半部分是一个常量，所以我们常常将前半部分的交叉熵作为损失函数，其实二者是一样的。

ID3 最大信息增益

信息增益 $g(D,A)$ 定义为数据集D的经验熵 $H(D)$ 与特征A给定条件下D的经验条件熵 $H(D|A)$ 的差

$g(D,A) = H(D) - H(D|A)$

选择 $g(D,A)$ 最大的特征，所有样本根据此特征，划分到不同的节点上。在经验熵不为0的节点中继续生长。ID3算法只有树的生成，容易产生过拟合。

C4.5 最大信息增益比

因为信息增益对取值数目多的属性有所偏好，为了减少这种偏好带来的影响，使用信息增益比来选择最优划分属性。

CART 基尼指数

基尼系数Gini（D）用来表示集合D的不确定性。CART在每一次迭代中选择划分后基尼指数最小的特征及其对应的切分点进行分类。CART是一颗二叉树，每次将数据按特征A的区分分成两份，分别进入左右子树。

优缺点

优点

• 简单易懂，直观可解释。
• 适合处理类别和数值型数据。
• 可以处理不完整的数据。
• 无需进行特征缩放。

缺点

• 容易过拟合，特别是当树很深时。
• 对数据的微小变化敏感，可能生成完全不同的树。

2.6. 随机森林（Random Forest）

随机森林是一种基于集成学习（Ensemble Learning）思想的算法，它通过构建多个决策树进行训练，并结合这些树的结果进行预测。随机森林可以用于分类和回归任务。由于它结合了多棵树的优点，具有较强的鲁棒性、抗噪能力，且能够有效防止过拟合。

随机森林通过组合多棵决策树的输出结果来提高预测的准确性。其基本原理主要包括两个关键部分：

1. Bootstrap抽样：从原始数据集中随机选择多个有放回的子集，用于训练每一棵树。这意味着每棵树看到的数据并不完全相同，有些样本会被多次选择，而有些样本可能不会被选中。

2. 特征随机性：在每次节点分裂时，随机选择特征的子集进行划分，而不是使用所有特征。这进一步增加了树的多样性，减少了单棵树的过拟合风险。

随机森林使用了Bagging的思想，通过对数据再抽样，然后在每组样本上训练出来的模型取平均。Bagging是降低方差，防止过拟合。对n个独立不相关的模型的预测结果取平均，方差近似为原来单个模型的 $1/n$ 。

工作流程

随机森林的工作可以分为以下步骤：

1. 构造随机森林

   • 数据集随机抽样：从训练数据集中进行Bootstrap抽样，生成若干个随机的子集，每个子集用于训练一棵决策树。
   • 构建决策树：对于每个样本子集，训练一棵决策树。不同于传统决策树，每次分裂时会随机选择特征子集来决定最优的划分。

2. 训练过程

   • 对于每个决策树，通过数据子集和随机选择的特征构造完全树，通常不对树进行剪枝。
   • 每棵树会独立学习数据集中的模式。

3. 预测过程

   • 分类问题：随机森林中的每棵树都会对输入样本进行预测，然后通过投票机制决定最终的分类结果。即选择预测次数最多的类别作为最终分类。
   • 回归问题：随机森林中的每棵树都会给出一个预测值，最终的预测结果通过所有树的平均值来决定。

可否将RF的基分类模型由决策树改成线性模型或者knn？

随机森林属于bagging类的集成学习方法，主要好处是减小集成后分类器的方差，比基分类器的方差小。所以Bagging所采用的的基分类器最好是本身对样本分布较为敏感（不稳定分类器），这样bagging才能体现效果。而线性分类器和KNN属于较为稳定的分类器，本身方差不大，所以将他们作为基分类器使用bagging不能再原基分类器的基础上获得更好的表现。相反地，可能因为bagging的采样而使得训练中难以收敛从而增大集成分类器的偏差。

优缺点

优点

1. 高精度：在多数情况下，随机森林的准确性高于单个决策树，特别是在大数据集或复杂任务上。
2. 抗过拟合能力强：由于集成了多棵树，随机森林的模型复杂度较低，避免了单棵决策树容易过拟合的问题。
3. 处理高维特征能力强：随机森林可以处理包含大量特征的数据集，且不需要对特征进行筛选。
4. 处理缺失值和不平衡数据：随机森林能够处理部分缺失的数据和类别不平衡的问题。
5. 重要特征选择：通过计算特征的重要性，随机森林可以帮助确定哪些特征对预测最为重要。

缺点

1. 计算开销大：构造大量的决策树需要较多的计算资源，尤其是在数据集较大时，训练时间可能较长。
2. 模型解释性较弱：相比于单棵决策树，随机森林的结构较为复杂，不容易解释单个决策路径。
3. 预测时间较慢：虽然训练时间较长，但随机森林的预测时间也会因为多棵树的组合而增加，尤其在实时预测系统中表现较为明显。

2.7. Gradient Boosting（梯度提升）

Gradient Boosting 是一种集成学习方法，通过将多个弱学习器（通常是决策树）串联起来，形成一个强大的预测模型。它逐步改进模型的预测能力，通过每一步的模型修正先前模型中的错误。常见的变种包括XGBoost，LightGBM，CatBoost等。

工作原理

Gradient Boosting 的核心思想是：每个新的模型都尝试减少前一组模型的残差（误差）。具体流程如下：

1. 初始模型：从简单的模型（如决策树）开始，预测目标变量。
2. 计算残差：计算模型的预测值和真实值之间的误差（残差）。
3. 构建新模型：新模型拟合前一个模型的残差（目标是修正错误）。新模型用来减少误差而不是直接预测目标变量。
4. 迭代过程：重复第2步和第3步，不断加入新的模型来修正前一轮模型的误差。
5. 加权求和：最终的预测结果是所有模型加权后的和，通常最后使用的是步长（learning rate）来控制加权的比例。

算法步骤

以回归为例，假设我们有训练数据 $ (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n) $，目标是拟合一个模型 $ F(x) $ 来最小化损失函数 $ L(y, F(x)) $：

• 步骤1：初始化模型 $ F_0(x) $，使其最小化损失函数（通常为目标值的均值）。

  $F_0(x) = \arg \min \sum_{i=1}^{n} L(y_i, F(x_i))$

• 步骤2：对每个迭代步骤 $ m = 1, 2, …, M $，执行以下步骤：

  1. 计算残差 $ r_{im} = -\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} $，即目标函数的梯度。
  2. 训练一个新的模型 $ h_m(x) $ 来拟合残差 $ r_{im} $。
  3. 更新模型 $ F_{m}(x) = F_{m-1}(x) + \nu h_m(x) $，其中 $ \nu $ 是学习率，控制每一步的模型更新步长。

• 步骤3：最终模型为 $ F_M(x) = F_0(x) + \sum_{m=1}^{M} \nu h_m(x) $。

负梯度方向就是残差拟合的方向，拟合负梯度就是在最小化损失函数，这使得每一轮的弱学习器都朝着减少预测误差的方向优化。

优缺点

优点：

• 强大的预测能力：通过修正之前模型的残差，最终模型性能通常非常优秀。
• 处理偏差-方差权衡：通过调整基学习器的复杂度（如决策树的深度）和学习率，Gradient Boosting 可以很好地在偏差与方差之间取得平衡。

缺点：

• 训练时间长：由于是逐步构建模型，训练时间相对较长。
• 参数敏感：模型对超参数（如学习率、树的深度等）比较敏感，通常需要仔细调参。
• 容易过拟合：如果基学习器数量过多或者树太深，模型可能会过拟合，需要通过正则化手段（如早停、学习率调整等）来避免。

梯度提升和梯度下降有什么区别和联系？

两者都是在每一轮迭代中，利用损失函数相对于模型的负梯度方向的信息来对当前模型进行更新。梯度下降是一种优化算法，用于找到函数的最小值或最大值。通常应用在单一模型的训练过程中，用于优化模型的参数（如线性回归、神经网络等）。它通过计算损失函数的梯度，逐步调整模型参数，直到损失函数达到局部或全局最小值。梯度提升是一种集成学习方法，通过多个弱学习器（如决策树）的组合来提升预测性能。它逐步构建多个模型，每个模型通过拟合前一个模型的残差（即负梯度），从而改进预测结果。梯度提升算法使用梯度下降的思想来优化整个模型的性能，但其目标不是直接优化模型参数，而是优化模型集成的效果。

特性	梯度下降（Gradient Descent）-优化算法	梯度提升（Gradient Boosting） - 集成学习方法
作用对象	单一模型的参数	集成模型中的多个弱学习器（如决策树）
目标	优化模型参数，使损失函数最小化	通过弱学习器的逐步组合，减少整体预测误差
更新方式	逐步更新模型的参数，沿着负梯度方向调整	逐步添加弱学习器，拟合前一轮的残差（负梯度）
算法流程	计算梯度 -> 更新参数 -> 重复迭代	计算残差（负梯度）-> 训练新模型拟合残差 -> 组合模型
使用场景	线性回归、神经网络等优化问题	回归、分类等场景下的集成学习方法，如 XGBoost、LightGBM

Boosting和Bagging的异同？

Bagging通过模型集成降低方差，提高弱分类器的性能。

Boosting通过模型集成降低偏差，提高弱分类器的性能。

特性	Bagging	Boosting
工作机制	并行训练：多个弱学习器独立训练，并行执行。	串行训练：多个弱学习器顺序训练，每个模型依赖上一个模型的结果。
样本处理	有放回随机抽样：每个弱学习器在一个随机采样的子集上训练。	加权训练：每个弱学习器在原始训练集上训练，但每个样本有不同的权重。
目标	通过减少模型的方差，提升模型的稳定性和泛化能力。	通过逐步减少偏差和方差，提升模型的整体准确性。
模型关注点	各模型独立，无关其他模型的错误。	每个模型依赖前一个模型，集中在纠正之前模型的错误。
弱学习器权重	各个弱学习器权重相同，预测结果通过简单投票（分类）或平均（回归）来合并。	每个弱学习器根据其性能赋予不同权重，表现好的学习器权重大。
处理偏差/方差	主要减少方差，通过减少模型对数据噪声的敏感性来提高泛化能力。	同时减少偏差和方差，通过纠正错误逐步改进模型。
算法代表	Random Forest 是 Bagging 的典型算法。	AdaBoost、Gradient Boosting 是 Boosting 的典型算法。
并行性	支持并行训练，因各模型独立，可在多核或分布式系统上加速。	顺序训练，难以并行化，因为每个学习器依赖于前一个学习器的结果。

2.8. K-means

K-means 是一种常用的无监督学习算法，用于聚类分析。它试图将数据集划分为 $ K $ 个互不重叠的簇（Cluster），每个簇由具有相似特征的数据点组成。K-means 的目标是最小化簇内数据点与簇中心（质心，Centroid）之间的距离，从而使簇内的数据点更加紧密，簇间的数据点差异更大。

K-means 算法的步骤

1. 确定簇的数量 $ K $：事先指定 $ K $，即要将数据集划分成 $ K $ 个簇。

2. 随机初始化质心：随机选择 $ K $ 个数据点作为初始的质心（Centroid），质心是用于表示每个簇中心的点。

3. 分配数据点到簇：将每个数据点分配给距离其最近的质心，形成 $ K $ 个簇。距离通常通过欧氏距离计算：

   $\text{距离} = \sqrt{(x_1 - \mu_1)^2 + (x_2 - \mu_2)^2 + \cdots + (x_n - \mu_n)^2}$

   其中，$ x_i $ 表示数据点的坐标，$ \mu_i $ 表示质心的坐标。

4. 更新质心：对每个簇，重新计算该簇所有数据点的平均值，作为该簇的新质心：

   $\mu_j = \frac{1}{|C_j|} \sum_{x \in C_j} x$

   其中，$ \mu_j $ 是簇 $ C_j $ 的新质心，$ |C_j| $ 是簇中数据点的数量。

5. 重复分配和更新：反复执行分配数据点到簇和更新质心这两个步骤，直到质心不再变化或变化很小，或者达到指定的迭代次数。

6. 算法结束：当质心收敛时，K-means 算法结束，最终形成 $ K $ 个簇。

K-means 的目标是最小化簇内平方误差和（Sum of Squared Errors, SSE），即每个簇内数据点与其质心的距离平方和。数学形式为：

$SSE = \sum_{j=1}^{K} \sum_{x \in C_j} ||x - \mu_j||^2$

其中，$ K $ 是簇的数量，$ C_j $ 是第 $ j $ 个簇，$ x $ 是簇内的数据点，$ \mu_j $ 是第 $ j $ 个簇的质心。

优缺点

优点：

1. 简单易实现：K-means 算法的流程清晰明了，容易理解和实现。

2. 计算效率高：K-means 的时间复杂度为 $ O(n \times K \times d \times t) $，其中 $ n $ 是数据点数，$ K $ 是簇的数量，$ d $ 是特征维度，$ t $ 是迭代次数。适合大规模数据集的处理。

3. 适用于凸形簇：对于形状规则、分布较为均匀的数据，K-means 能很好地分离不同的簇。

缺点：

1. 需要预先指定 K 值：K-means 需要事先确定聚类数 $ K $，但是在实际应用中，往往无法确定数据集的簇数量。

2. 对初始质心敏感：K-means 的结果依赖于初始质心的选择，可能会陷入局部最优解。为了解决这个问题，可以使用K-means++，通过一种巧妙的质心初始化方法来改进初始质心的选择。 kmeans聚类属于启发式方法，不能保证收敛到全局最优，初始中心的选择会直接影响聚类结果。

3. 只能找到线性可分的簇：K-means 只能找到形状为圆形或球形的簇，不能很好地处理非凸形的簇。

4. 对噪声和离群点敏感：K-means 使用欧氏距离来衡量相似度，容易受到极端数据点（离群点）的影响，导致结果偏差。

5. 簇大小不平衡问题： 对于大小相差较大的簇，K-means 可能无法正确聚类，较大的簇可能会掩盖较小的簇。

K-means++

K-means++ 是 K-means 算法的一种改进版本，主要针对初始质心选择问题。
K-means++ 的初始化步骤如下：

1. 随机选择一个数据点作为第一个质心。
2. 对于每一个剩下的数据点，计算它与最近质心的距离平方。
3. 按照距离平方的概率，随机选择下一个质心。距离较大的数据点有更大的概率被选为质心。
4. 重复第 2 和第 3 步，直到选出 $ K $ 个质心。

通过这种初始化方法，K-means++ 可以有效避免 K-means 对初始质心的敏感性，减少迭代次数，并提高聚类效果。

常用聚类评估指标

内部评估指标

1. 轮廓系数（Silhouette Coefficient）

轮廓系数结合了簇内距离和簇间距离，用来评估每个数据点的聚类效果。其定义为：

$s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))}$

其中：

• $ a(i) $：数据点 $ i $ 到同簇内其他数据点的平均距离（簇内距离）。
• $ b(i) $：数据点 $ i $ 到最近的其他簇的质心的平均距离（簇间距离）。

轮廓系数的取值范围为 $[-1, 1]$：

• $ s(i) \approx 1 $：表示该点聚类效果良好，距离同簇点近，离其他簇远。
• $ s(i) \approx 0 $：表示该点处于两个簇的边界上。
• $ s(i) \approx -1 $：表示该点可能被错误分类到其他簇。

通过计算所有数据点的平均轮廓系数来评估整个聚类模型的效果，轮廓系数越大越好。

2. SSE（Sum of Squared Errors，簇内误差平方和）

SSE 是 K-means 等聚类算法中常用的评估指标，表示簇内所有数据点与其质心的距离平方和。公式为：

$SSE = \sum_{j=1}^{K} \sum_{x \in C_j} ||x - \mu_j||^2$

SSE 越小，表示数据点与质心越接近，聚类效果越好。SSE 随着 $ K $ 值的增加通常会减小，因此不能单独依赖 SSE 来选择最优 $ K $。

3. Calinski-Harabasz 指数（方差比准则）

Calinski-Harabasz 指数衡量簇的分离度和紧密度之比：

$CH = \frac{\text{簇间方差}}{\text{簇内方差}} \times \frac{n - K}{K - 1}.$

其中，$ n $ 是数据点总数，$ K $ 是簇的数量。簇间方差越大、簇内方差越小，表示聚类效果越好。Calinski-Harabasz 指数越大，聚类效果越好。

4. Davies-Bouldin 指数

Davies-Bouldin 指数衡量的是簇间相似性和簇内相似性的比值：

$DB = \frac{1}{K} \sum_{i=1}^{K} \max_{j \neq i} \left( \frac{\sigma_i + \sigma_j}{d(\mu_i, \mu_j)} \right)$

其中：

• $ \sigma_i $ 是簇 $ i $ 的簇内数据点与质心的平均距离。
• $ d(\mu_i, \mu_j) $ 是簇 $ i $ 和 $ j $ 质心之间的距离。

Davies-Bouldin 指数越小，表示簇内距离较小且簇间距离较大，聚类效果越好。

5. 轮廓系数图（Elbow Method）

轮廓系数图或肘部法（Elbow Method）是一种用于确定最优 $ K $ 值的方法。绘制不同 $ K $ 值对应的 SSE 曲线，曲线通常是先快速下降，然后变得平缓。最优的 $ K $ 通常位于曲线的“肘部”位置，即 SSE 开始平缓下降的点。

外部评估指标

外部评估指标用于在有真实标签的情况下评估聚类结果的效果。它通过将聚类结果与真实的类别标签进行对比，计算聚类效果的准确性。这类指标适用于有标注的数据集，常见的外部评估指标有：

1. 调整兰德指数（Adjusted Rand Index, ARI）

调整兰德指数是基于兰德指数（Rand Index） 的一种改进，用来衡量聚类结果与真实标签之间的一致性。其计算依据是聚类结果中的点对是否被正确地分配到同一簇或不同簇。

Rand Index计算所有点对之间的组合，统计两点是否被正确地分配到同一簇或不同簇：

$RI = \frac{a + b}{a + b + c + d}$

其中：

• $ a $：同属于一个簇，且真实标签也相同的点对数。
• $ b $：属于不同簇，且真实标签也不同的点对数。
• $ c $：属于同一个簇，但真实标签不同的点对数。
• $ d $：属于不同簇，但真实标签相同的点对数。

兰德指数的取值范围是$[0,1]$。兰德指数的一个主要问题是，即使聚类结果是随机的，RI 也往往会得到一个较高的值，而不是真正反映聚类效果。

由于 Rand Index 没有考虑随机聚类可能带来的效果，调整兰德指数（ARI） 引入了随机化校正：

$ARI = \frac{RI - E[RI]}{\max(RI) - E[RI]}$

2. 互信息（Mutual Information, MI）与归一化互信息（Normalized Mutual Information, NMI）

互信息（Mutual Information, MI） 用于衡量聚类结果与真实标签之间的信息共享程度。它基于信息论，反映了一个聚类结果中有多少信息可以解释真实的标签分布。

互信息的公式为：

$MI(U, V) = \sum_{i=1}^{|U|} \sum_{j=1}^{|V|} P(U_i, V_j) \log \frac{P(U_i, V_j)}{P(U_i) P(V_j)}$

其中：

• $ U $ 是聚类结果的簇分布，$ V $ 是真实标签的分布。
• $ P(U_i) $ 是聚类簇 $ U_i $ 的概率。
• $ P(V_j) $ 是真实标签 $ V_j $ 的概率。
• $ P(U_i, V_j) $ 是数据同时属于簇 $ U_i $ 和真实标签 $ V_j $ 的联合概率。

互信息的取值越高，说明聚类结果与真实标签之间的关联性越强。

为了消除样本数量对互信息的影响，可以对 MI 进行归一化，得到归一化互信息（NMI），其定义为：

$NMI(U, V) = \frac{MI(U, V)}{\sqrt{H(U) H(V)}}$

其中，$ H(U) $ 和 $ H(V) $ 分别是聚类结果和真实标签的熵，表示其不确定性。
NMI 的取值范围是 $[0, 1]$，$ 1 $ 表示聚类结果与真实标签完全匹配。$ 0 $ 表示聚类结果与真实标签没有相关性。

3. 同质性、完整性和 V-measure

这三者是相互关联的聚类评估指标，分别用于衡量聚类结果与真实标签之间的不同特性。

同质性表示每个簇内部的所有数据点都属于同一个真实类别。若每个聚类的簇仅包含单一类别的数据点，则该聚类是同质的。公式为：

$H = 1 - \frac{H(C|K)}{H(C)}$

其中，$ H(C|K) $ 是给定聚类结果 $ K $ 后的真实标签 $ C $ 的条件熵。$ H© $ 是真实标签 $ C $ 的熵。

同质性越高，表示同簇数据点的真实类别越统一，理想情况下，应该接近 1。

完整性表示真实类别的所有数据点都被划分到同一个簇中。若每个真实类别的所有数据点都集中在某个簇中，则聚类具有完整性。公式为：

$C = 1 - \frac{H(K|C)}{H(K)}$

其中：

• $ H(K|C) $ 是给定真实标签 $ C $ 后的聚类结果 $ K $ 的条件熵。
• $ H(K) $ 是聚类结果 $ K $ 的熵。

完整性越高，表示聚类结果能更好地包含每个真实类别的数据点。

V-measure是同质性和完整性的调和平均数，用来综合衡量聚类的整体效果。公式为：

$V = 2 \times \frac{H \times C}{H + C}$

V-measure 的取值范围是 $[0, 1]$，其含义与同质性和完整性相似，越接近 1，表示聚类效果越好。V-measure 兼顾了同质性和完整性，因此是一个较为平衡的评估指标。

4. 纯度（Purity）

把每个簇中最多的类作为这个簇所代表的类，然后计算正确分配的类的数量，然后除以 $N$ 。

$(\Omega, \mathbb{C})=\frac{1}{N} \sum_{k} \max _{j}\left|\omega_{k} \cap c_{j}\right|$

其中 $\Omega=\left\{\omega_{1}, \omega_{2}, \ldots, \omega_{K}\right\}$ 是聚类结果的集合 $\omega_{k}$表示第k个聚类的集合；$\mathbb{C}=\left\{c_{1}, c_{2}, \ldots, c_{J}\right\}$ 是原始分类的集合，$c_j$表示第j个分类的集合。

purity优点是方便计算，值在0~1之间；缺点：当簇的数量很多的时候，容易达到较高的纯度——特别是，如果每个文档都被分到独立的一个簇中，那么计算得到的纯度就会是1。因此，不能简单用纯度来衡量聚类质量与聚类数量之间的关系。

选择评估指标的依据

1. 无监督聚类：如果没有真实标签，推荐使用轮廓系数、Calinski-Harabasz 指数和Davies-Bouldin 指数等内部评估指标。
2. 有监督聚类：如果有真实标签，可以使用ARI、NMI、V-measure等外部评估指标。
3. 最优簇数量：使用肘部法和轮廓系数图来帮助选择最优簇数量 $ K $。

常见的聚类算法

• 基于划分的算法：如 K-means，简单高效，但对簇形状和初始条件敏感。
• 基于层次的算法：如层次聚类，自上而下或者自下而上。能构建簇的层次结构，但计算复杂度较高。
• 基于密度的算法：如 DBSCAN，高密度区域找到簇，适合发现任意形状的簇并处理噪声，但对参数敏感。
• 基于网格的算法：如 STING，适合大规模数据集，速度快，但依赖网格划分方式。
• 基于模型的算法：如高斯混合模型 GMM，假设数据来自多个高斯分布的混合，每个簇对应一个高斯分布。通过**期望最大化算法（EM算法）**来估计簇的参数和分布。但对模型假设和参数选择敏感。
• 谱聚类。基于图论，通过构造相似度矩阵并对其进行谱分解，从而将数据映射到低维空间，在低维空间中进行聚类。

2.9. 主成分分析 PCA

主成分分析（PCA, Principal Component Analysis） 是一种常用的降维和数据分析技术。它的主要目标是通过线性变换，将原始的高维数据映射到较低维度的空间中，同时尽可能保持数据的方差或信息量。这种方法在高维数据集中的应用非常广泛，可以帮助减少特征数量、可视化数据结构，或是去除噪声等。

PCA 的核心思想是通过构建一组新的正交基向量，即主成分（Principal Components），这些主成分是数据集中特征方差最大的方向。在降维的过程中，PCA 会根据数据的方差信息，选取前几个主成分来表示数据，从而达到降维的目的。

PCA的步骤

PCA 的计算过程大致可以分为以下几个步骤：

1. 标准化数据。 在使用 PCA 之前，通常需要将每个特征进行标准化处理，即将数据归一化为均值为 0、方差为 1 的形式。这是因为 PCA 依赖于特征的方差，而不同尺度的特征（如米和千克）会对结果产生不公平的影响。

2. 计算协方差矩阵。 PCA 的核心是对数据进行线性变换，因此需要计算数据的协方差矩阵，以了解各特征之间的线性关系。协方差矩阵的元素描述了两个特征间的协方差，即它们的联合变化情况。

3. 计算特征值和特征向量。 对协方差矩阵进行特征值分解，得到特征值和特征向量。特征向量代表主成分的方向，而特征值表示沿着该方向的方差大小。特征值越大，说明主成分捕捉到的方差越多。

$\text{Cov}(X) v = \lambda v$

其中，$ v $ 是特征向量，$ \lambda $ 是特征值。

4. 选择主成分。 根据特征值的大小对特征向量排序，选择其中最大的 $ k $ 个特征向量作为主成分。这些主成分构成新的低维空间，数据将被投影到这些主成分上，从而实现降维。

5. 将数据投影到主成分空间。 通过选取的主成分矩阵，将原始数据投影到新空间中。假设我们选择了前 $ k $ 个主成分，则数据 $ X $ 被投影后的新数据表示为：

$Z = X W,$

其中， $W$ 是主成分向量矩阵。

PCA的几何解释

PCA 的几何解释是，它通过找到新的坐标轴（即主成分），使得这些新坐标轴是原始数据的最佳线性组合。在新的坐标系下，数据沿着第一个主成分（最大方差方向）投影最多的方差，第二个主成分与第一个正交，捕捉剩余的最大方差，依此类推。

• 第一主成分：方差最大的方向。
• 第二主成分：与第一主成分正交且方差次大的方向。
• 以此类推。

PCA的性质

• 正交性：各主成分之间是相互正交的，即彼此独立不相关。
• 方差解释率：每个主成分解释了原始数据的方差总量的某一比例。通过特征值的比率可以衡量主成分的重要性。通常会选择能解释大部分方差的前几个主成分，达到降维的效果。
• 最大方差方向：PCA 总是试图在数据中找到方差最大的方向作为新的坐标轴，从而保证保留最多的信息。

优缺点

优点

1. 降维效果好：可以有效减少数据维度，保留尽可能多的有用信息。
2. 特征解耦：主成分是线性不相关的，有助于去除多重共线性。
3. 可视化：将高维数据映射到低维空间，方便进行可视化分析。

缺点

1. 线性假设：PCA 假设主成分是数据的线性组合，不能捕捉到非线性结构。
2. 信息损失：降维过程中可能会丢失部分信息，特别是方差较小的主成分对应的信息。
3. 解释性差：PCA 转换后的主成分没有原始特征的具体意义，难以解释。

线性判别分析和主成分分析有何区别和联系？

• PCA 是无监督的。PCA 忽略类别信息，专注于保持数据的总方差，寻找能捕捉最多信息的方向。选择的是投影后数据方差最大的方向。由于PCA是无监督的，因此假设方差越大，信息量越多，用主成分来表示原始数据可以去除冗余的维度，达到降维。

• LDA 是有监督的。LDA 利用类别标签信息，目标是找到一个投影向量w，使得数据投影后，类间距离最大化，同时类内距离最小化。

二、数理统计和优化

1. 常见的分布

伯努利分布（0-1分布），Beta分布，二项分布，泊松分布，t分布，多项式分布。详见教材

2. 参数估计有哪些方法？

极大似然估计MLE

在统计学中，常常使用极大似然估计法来估计参数。即找到一组参数，使得在这组参数下，我们数据的似然度（概率）最大。(极大似然估计：就是利用已知的样本结果信息，反推最具有可能（最大概率）导致这些样本结果出现的模型参数值，即‘模型已定，参数未知’)

极大似然估计的前提一定是要假设数据总体的分布，如果不知道数据分布，是无法使用极大似然估计的

求极大似然估计的步骤

（1）写出似然函数；

（2）对似然函数取对数，并整理；

（3）求导数，令导数为 0，得到似然方程；

（4）解似然方程，得到的参数。

最大后验概率估计MAP

极大似然估计中采样需满足一个重要的假设，就是所有的采样都是独立同分布的。

那么我们就知道了极大似然估计的核心关键就是对于一些情况，样本太多，无法得出分布的参数值，可以采样小样本后，利用极大似然估计获取假设中分布的参数。

极大似然估计就是经验风险最小化的一个例子。当模型是条件概率分布、损失函数是对数损失函数时，经验风险最小化就等价于极大似然估计。

最大后验概率是计算给定数据条件下模型的条件概率，即后验概率。使用模型的先验分布是贝叶斯学习的特点。

期望极大化EM

EM 算法解决这个的思路是使用启发式的迭代方法，既然我们无法直接求出模型分布参数，那么我们可以先猜想隐含参数（EM 算法的 E 步），接着基于观察数据和猜测的隐含参数一起来极大化对数似然，求解我们的模型参数（EM算法的M步)。由于我们之前的隐含参数是猜测的，所以此时得到的模型参数一般还不是我们想要的结果。我们基于当前得到的模型参数，继续猜测隐含参数（EM算法的 E 步），然后继续极大化对数似然，求解我们的模型参数（EM算法的M步)。以此类推，不断的迭代下去，直到模型分布参数基本无变化，算法收敛，找到合适的模型参数。

一个最直观了解 EM 算法思路的是 K-Means 算法。在 K-Means 聚类时，每个聚类簇的质心是隐含数据。我们会假设 K 个初始化质心，即 EM 算法的 E 步；然后计算得到每个样本最近的质心，并把样本聚类到最近的这个质心，即 EM 算法的 M 步。重复这个 E 步和 M 步，直到质心不再变化为止，这样就完成了 K-Means 聚类。

EM算法和极大似然估计的前提是一样的，都要假设数据总体的分布，如果不知道数据分布，是无法使用EM算法的。

EM算法是通过不断求解下界的极大化逼近求解对数似然函数极大化的算法

3. 频率学派和贝叶斯学派什么区别？

频率学派

频率学派是上帝视角，认为频率是固定的，事件在多次重复实验中趋于一个稳定的值p，那么这个值就是该事件的概率。

他们认为模型参数是个定值，希望通过类似解方程组的方式从数据中求得该未知数。这就是频率学派使用的参数估计方法-极大似然估计（MLE），这种方法往往在大数据量的情况下可以很好的还原模型的真实情况。

贝叶斯派

他们认为世界是不确定的，因获取的信息不同而异。假设对世界先有一个预先的估计，然后通过获取的信息来不断调整之前的预估计。他们认为模型参数源自某种潜在分布，希望从数据中推知该分布。对于数据的观测方式不同或者假设不同，那么推知的该参数也会因此而存在差异。这就是贝叶斯派视角下用来估计参数的常用方法-最大后验概率估计（MAP）

这种方法在先验假设比较靠谱的情况下效果显著，随着数据量的增加，先验假设对于模型参数的主导作用会逐渐削弱，相反真实的数据样例会大大占据有利地位。极端情况下，比如把先验假设去掉，或者假设先验满足均匀分布的话，那她和极大似然估计就如出一辙了。

4. 大数定理和中心极限定理

5. 假设检验

6. 最优化问题

详见教材 <<数据科学优化方法>> 孙怡帆，中国人民大学出版社，2024.

7. 优化器总结

1. 梯度下降 (Gradient Descent, GD)

梯度下降是一种基于梯度信息来更新参数的优化方法。假设损失函数为 $J(\theta)$，对于每次迭代，更新权重的方式为：

$\theta_{t+1} = \theta_t - \eta \nabla J(\theta_t),$

其中，$ \theta_t $ 是第 $ t $ 次迭代时的参数，$ \eta $ 是学习率，$\nabla J(\theta_t)$ 是损失函数对参数的梯度。

• 是否收敛到最优值：在凸问题中，只要学习率 $\eta $ 选得合适，梯度下降可以收敛到全局最优解。但对于非凸问题，它可能会收敛到局部最优解。
• 优点：简单且易于实现。
• 缺点：对于批量梯度下降，计算梯度会涉及整个训练集，计算成本高。

2. 随机梯度下降 (Stochastic Gradient Descent, SGD)

SGD 是梯度下降的一个变种，它在每次更新时仅使用一个样本的梯度，而不是整个训练集的梯度：

$\theta_{t+1} = \theta_t - \eta \nabla J(\theta_t; x_i, y_i)$

其中 $ (x_i, y_i) $ 是随机选择的训练样本。

• 是否收敛到最优值：在凸问题中，SGD 在学习率逐渐衰减的情况下可以收敛到全局最优值，但波动较大。在非凸问题中，SGD 可能会陷入局部最优，但随机性有时会帮助跳出局部最优。
• 优点：计算开销低，每次迭代只计算一个样本的梯度。
• 缺点：更新频繁，带有随机性，会造成损失函数在收敛过程中严重震荡。收敛较慢，更新过程存在噪声。

3. 小批量梯度下降法（Mini-batch Gradient Descent, MBGD）

小批量梯度下降是批量梯度下降和随机梯度下降的折中，使用一部分数据计算梯度，然后更新参数。这种方式可以降低参数更新时的方差，使得收敛更加稳定。但是对于非凸问题，依旧无法保证得到全局最优解。

在梯度下降公式中，可以从两个角度进行改进。一是自适应选择学习率；二是梯度（动量）。

首先，在修正梯度方面，主要有momentum动量法和nesterov 加速法。

4. 动量梯度下降 (Momentum GD) 和 NAG（Nesterov accelerated gradient）

动量法：参数更新时在一定程度上保留之前更新的方向，同时又利用当前batch的梯度微调最终的更新方向，简言之就是通过积累之前的动量来 (previous_sum_of_gradient) 加速当前的梯度，可能更加稳定、更有利于跳出局部最优。

动量法的更新公式为：

$v_{t+1} = \gamma v_t + \eta \nabla J(\theta_t), \\ \theta_{t+1} = \theta_t - v_{t+1}$

其中， $ \gamma $ 是动量因子（通常取值接近于 1），$ v_t $ 是动量向量。

• 是否收敛到最优值：在凸问题中，动量法可以比标准梯度下降更快收敛。在非凸问题中，它同样可能收敛到局部最优，但动量项可能有助于避免一些局部最优点。
• 优点：加快收敛速度，减少震荡。
• 缺点：动量项的选取较为敏感。

NAG 进一步引入了nesterov 动量，先在计算梯度更新前做一个矫正，更新公式为：

$v_{t+1} = \gamma v_t + \eta \nabla J(\theta_t - \gamma v_t), \\ \theta_{t+1} = \theta_t - v_{t+1}.$

传统的优化算法要么将学习率设置为常数要么根据训练次数调节学习率。往往忽视了学习率其他变化的可能性。然而，学习率对模型的性能有着显著的影响，因此需要采取一些策略来想办法更新学习率，从而提高训练速度。如果学习率太小，则梯度很大的参数会有一个很慢的收敛速度； 如果学习率太大，则已经优化得差不多的参数可能会出现不稳定的情况。

自适应学习率算法主要有：AdaGrad算法，RMSProp算法，Adam算法以及AdaDelta算法等。

5. AdaGrad (Adaptive Gradient Algorithm)

AdaGrad 根据历史梯度信息来调整学习率，能够自动缩放每个参数反比于其所有梯度历史总和的平方根。更新公式为：

$\theta_{t+1, i} = \theta_{t,i}- \frac{\eta}{\sqrt{G_{t,ii} + \epsilon}} g_{t,i}.$

其中，$g_{t,i}$ 为 $t$时刻，参数 $\theta_{t,i}$ 的梯度。$G_t$ 是对角矩阵，$(i,i)$元素为到第$ t $次迭代为止，参数 $\theta_{t,i}$ 的累积梯度平方和。

• 是否收敛到最优值：AdaGrad 在凸问题中可以收敛到最优解，但在非凸问题中，学习率可能会变得非常小，导致无法继续有效更新。
• 优点：具有损失函数最大梯度的参数相应地有个快速下降的学习率，而具有小梯度的参数在学习率上有相对较小的下降。
• 缺点：中后期，分母上梯度累加的平方和会越来越大，学习率会逐渐减小到接近 0，使得训练提前结束，无法学习。

6. RMSProp (Root Mean Square Propagation)

RMSProp 通过调整每个参数的学习率来解决梯度震荡问题。其核心思想是对每个参数的梯度平方值进行指数加权平均，并使用这个平均值来调整每个参数的更新步长：

$E[g^2]_t = \beta E[g^2]_{t-1} + (1 - \beta) g_t^2, \qquad \theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{E[g^2]_t + \epsilon}} g_t$

其中，$ g_t $ 是梯度，$ E[g^2]_t $ 是梯度平方的移动平均，$\beta$是衰减因子，$\epsilon$ 是防止除零的小量。

• 是否收敛到最优值：RMSProp 能够在一定程度上控制学习率的大小，使得在深度学习中的表现较好。在非凸问题中，它能够有较好的局部收敛表现。
• 优点：能够动态调整学习率，对稀疏数据有较好的处理能力。
• 缺点：可能会在学习率过小的情况下导致收敛变慢。

7. Adadelta

Adadelta 是 AdaGrad 的改进版，旨在解决 AdaGrad 中学习率逐渐衰减至过小的问题。

Adadelta 的主要思想是通过使用指数加权移动平均（Exponential Moving Average, EMA）来代替 AdaGrad 中的累积平方梯度和累计学习率。通过这种方式，它能够更稳定地调整学习率，同时避免学习率在训练过程中过度减小。

Adadelta 不仅对梯度平方进行加权平均，还对参数更新的量进行加权平均，因此它不依赖于预设的全局学习率。

(1). 梯度平方的指数加权移动平均：

$E[g^2]_t = \rho E[g^2]_{t-1} + (1 - \rho) g_t^2$

其中，$ g_t $ 是在第 $ t $ 次迭代中计算的梯度，$\rho$ 是衰减率（通常取值在 0.9 左右），$ E[g^2]_t $ 是梯度平方的移动平均值。

(2). 参数更新的移动平均：

$\Delta \theta_t = - \frac{\sqrt{E[\Delta \theta^2]_{t-1} + \epsilon}}{\sqrt{E[g^2]_t + \epsilon}} g_t$

其中，$ E[\Delta \theta^2]_{t-1} $ 是之前参数更新量的移动平均值，$ \epsilon $ 是一个用于防止除零的小量（通常取 $ 10^{-6} $）。

(3). 更新移动平均：

$E[\Delta \theta^2]_t = \rho E[\Delta \theta^2]_{t-1} + (1 - \rho) (\Delta \theta_t)^2$

(4). 参数更新：

$\theta_{t+1} = \theta_t + \Delta \theta_t$

• 是否收敛到最优值：在凸优化问题中，Adadelta 可以收敛到全局最优解。在非凸问题中，它的表现依然较好，能够避免陷入局部最优点。不过，类似于其他基于梯度的优化方法，Adadelta 在非凸问题中并不能保证一定收敛到全局最优解。

• AdaGrad 使用的是累积平方梯度求和来更新学习率，导致学习率在训练过程中逐渐趋近于零，尤其是在处理长时间训练或大量数据时。这会使得 AdaGrad 训练过程后期的学习率非常小，进而导致参数几乎无法更新。

• Adadelta 通过引入指数加权移动平均（EMA）代替了 AdaGrad 中的累积平方梯度求和，避免了学习率过早衰减的现象。同时，Adadelta 不再需要预设学习率，因为它会自动调整学习率。

• 依赖于衰减率的选择：虽然不需要手动设置学习率，但衰减率 $ \rho $ 的选择依然是影响模型收敛速度的一个关键因素。对于不同的数据集和任务，可能需要针对衰减率进行调优。

8. Adam (Adaptive Moment Estimation)

Adam 是 RMSProp 和动量法的结合，通过同时计算梯度的一阶和二阶矩的指数加权平均来调整学习率：

$m_t = \beta_1 m_{t-1} + (1 - \beta_1) g_t, \\ v_t = \beta_2 v_{t-1} + (1 - \beta_2) g_t^2.$

$\hat{m}_t = \frac{m_t}{1 - \beta_1^t}, \quad \hat{v}_t = \frac{v_t}{1 - \beta_2^t}.$

$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{\hat{v}_t} + \epsilon} \hat{m}_t$

其中，$ m_t $ 和 $ v_t $ 分别是梯度的一阶和二阶矩，$ \beta_1 $ 和 $ \beta_2 $ 是超参数。

• 是否收敛到最优值：Adam 在许多实际问题中表现优越，但在某些情况下，Adam 可能会收敛到次优解。理论上，它能收敛到局部最优，但是否能达到全局最优取决于问题的性质。
• 优点：能够动态调整学习率，对稀疏数据和噪声鲁棒性强。
• 缺点：较为复杂，依赖超参数的设置。

9. AdamW (Adaptive Moment Estimation)

AdamW 是 Adam 优化算法的改进版本，它的主要改进是在 Adam 的基础上引入了权重衰减（Weight Decay）的正确实现。这种权重衰减是通过将 L2 正则化直接应用于参数更新公式，而不是像 Adam 那样对梯度进行修正。这种改进旨在提高模型的泛化能力，尤其是避免深度学习模型中过拟合的问题。

• Adam 中的错误正则化实现：在原版的 Adam 中，权重衰减实际上是通过将梯度中的 L2 惩罚项添加到更新公式中。这种做法在 Adam 中并不完全等同于对参数的惩罚，因为 Adam 依赖于动量和梯度的调整，它使得实际的正则化效果被稀释或扭曲，导致权重衰减效果不理想。

• AdamW 的提出：为了解决这个问题，AdamW 提出了更正的权重衰减实现。AdamW 将权重衰减项直接应用到参数本身的更新步骤，而不是施加在梯度上。这种做法能够更加有效地抑制模型的过拟合，提高泛化能力。

AdamW 基本上继承了 Adam 的大部分更新过程，但在参数更新时引入了独立的权重衰减项。

(1). 梯度的移动平均（一阶矩估计）：

$m_t = \beta_1 m_{t-1} + (1 - \beta_1) g_t$

其中，$g_t $是在第 $ t $ 次迭代中计算的梯度，$ m_t $是梯度的移动平均，$\beta_1 $ 是动量衰减因子（通常取 0.9）。

(2). 梯度平方的移动平均（二阶矩估计）：

$v_t = \beta_2 v_{t-1} + (1 - \beta_2) g_t^2$

其中，$ v_t $ 是梯度平方的移动平均，$ \beta_2 $ 是衰减因子（通常取 0.999）。

(3). 偏差修正：
为了消除初期时矩估计的偏差，需要进行偏差校正：

$\hat{m}_t = \frac{m_t}{1 - \beta_1^t}, \quad \hat{v}_t = \frac{v_t}{1 - \beta_2^t}$

(4). 参数更新（AdamW 核心改进部分）：
AdamW 的更新步骤不仅包含 Adam 的参数更新公式，还直接在参数更新时引入了权重衰减项：

$\theta_{t+1} = \theta_t - \eta \frac{\hat{m}_t}{\sqrt{\hat{v}_t} + \epsilon} - \eta \lambda \theta_t$

其中，$ \lambda $ 是权重衰减系数（即 L2 正则化系数），$ \eta $ 是学习率。

AdamW 的关键在于第二个项 $\eta \lambda \theta_t $，它直接将权重衰减施加在参数更新上，而不是施加在梯度上。这种方式与传统 SGD 中的权重衰减更一致。

• Adam：权重衰减通过 L2 正则化实现，并作用在梯度上。这种实现可能会导致正则化效果受到 Adam 的梯度调整机制的干扰，导致模型参数更新不充分，特别是在学习率较小时。
• AdamW：权重衰减直接作用于参数本身，即在每次参数更新时独立加入一个基于参数的衰减项。这样可以保证权重衰减的效果更加直接和有效，避免了 Adam 对梯度的干扰。此外，这种权重衰减更加显式地对模型参数产生作用，从而能够更好地抑制模型过拟合，提高泛化性能。
• 需要调优的超参数增加：相比 Adam，AdamW 多了一个权重衰减系数 $ \lambda $，这增加了模型调优的复杂性。

Reference

DeepLearing-Interview-Awesome-2024

几种排序算法

machine-learning-interview

Distilled AI