经典机器学习方法

笔记内容包含常见的经典机器学习中遇到的一些概念，每个章节的内容都可独立观看，目标是对每个机器学习概念给出严谨的推导或适当的例子进行说明

极大似然估计

• 参考资料
  • “损失函数”是如何设计出来的？直观理解“最小二乘法”和“极大似然估计法”_哔哩哔哩_bilibili

似然函数是用真实数据来拟合理论模型，首先要假设数据服从某一分布 $N$，对于真实数据 $x$，要满足 $\prod _{x_i\in X}^{N}P(x_i|N)$ 最大，即让真实数据在理论模型的分布下构成的概率尽可能大

举一个扔硬币的例子，在这个例子中，左侧是理论分布，右侧是实验的真实数据，根据实验结果不能反推出理论模型；根据理论模型也不能够说明实验结果就和模型中的概率分布一样，但是我可以找到一个理论分布的参数，让真实数据的分布概率尽可能和理论分布一致，这个过程就是找似然函数的过程，求得理论分布参数的过程就是求极大似然估计的过程

Example

• 以 logistic 回归为例：
• 目标是最大化似然函数： $\prod _{x_i\in X}^{N}P(x_i|\theta )$
• $P(x_i|\theta )$ 是一个从一个概率分布得到的概率，$x_i$ 是输入的真实数据，$\theta$ 代表整个神经网络的权重参数，$y_i$ 表示神经网络输出的概率
• 类比上述抛硬币过程，由 $x_i$ 的标签可知，$x_i$ 的分布符合伯努利分布 $f(x)=P^x(1-P{)}^{1-x}$，因此最后的 $\prod _{x_i\in X}^{N}P(x_i|\theta )$ 可以被转换为 $\prod _{x_i\in X}^N{y}_i^{x_i}(1-y_i{)}^{1-x_i}$，通过取对数 $\log$ 就可以求得最后要优化的损失函数为：$-\sum _{i=1}^N(x_i\log y_i+(1-x_i)\log (1-y_i))$

KL 散度

KL散度（Kullback-Leibler divergence），可以以称作相对熵（relative entropy）或信息散度（information divergence）。

KL散度的理论意义在于度量两个概率分布之间的差异程度，当KL散度越大的时候，说明两者的差异程度越大；而当KL散度小的时候，则说明两者的差异程度小。如果两者相同的话，则该KL散度应该为0。

现有两个连续随机变量 $P$ 和 $Q$，它们对于的概率密度函数分别为 $p(x)$ 和 $q(x)$，如果我们用 $q(x)$ 去近似 $p(x)$，则 KL 散度可以表示为：

$$KL(P\mid \mid Q)=\int p(x)\log \frac{p(x)}{q(x)}dx$$

• KL 散度的性质：
  1. 非负性，即 $KL(P\mid \mid Q)\ge 0$
  2. 非对称性，即 $q(x)$ 去近似 $p(x)$ 不等于 $p(x)$ 去近似 $q(x)$

逆变换采样

如果我有一个服从均匀分布 $U(0,1)$ 的随机数，怎么把这个随机数扩展到任意分布 $N$ 上，并保持随机特性呢？

• 使用逆变换采样，先找到分布 $N$ 的逆概率分布函数，然后将服从 $U$ 的随机数带入，即可得到对应的 $N$ 分布上的随机数

Summary

证明： 设分布 $N$ 的概率分布函数为 $P(N\le n)=F_N(n)$，$U$ 是一个分布的随机变量，满足 $u=F_N(n)$ ，其对应的逆概率分布函数为 $n=F_N^{-1}(u)$，对其随机变量进行变换就是 $N=F_N^{-1}(U)$，现在要证明随机变量 $U$ 服从均匀分布 $F_N(n)=P(N\le n)=P(F_N^{-1}(u)\le n)=P(U\le F_N(n))=F_U(F_N(n))$ 等式两边就是 $U$ 为均匀分布的定义，因此可以证明 $U$ 为均匀分布，且逆概率分布函数就是其采样函数

朴素贝叶斯

• 参考资料：
  • 《统计学习方法第 2 版》——李航

从统计角度分析，对于给定数据 $X$ 和标签 $Y$ 预测任务相当于计算 $P(Y|X)$，将该概率公式用条件概率公式展开可得：

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

因此 $P(Y|X)$ 的计算变成了估算 $P(X,Y)$ 和 $P(X)$，使用贝叶斯公式可得：

$$P(Y=c_k|X=x)=\frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum _{k}P(X=x|Y=c_k)P(Y=c_k)}$$

在计算分类时，所以的分类都包含 $\sum _{k}P(X=x|Y=c_k)P(Y=c_k)$，直接可以省略，只需计算 $P(X=x|Y=c_k)P(Y=c_k)$

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$X^{(1)}$	1	1	1	1	1	2	2	2	2	2	3	3	3	3	3
$X^{(2)}$	S	M	M	S	S	S	M	M	L	L	L	M	M	L	L
$Y$	-1	-1	1	1	-1	-1	-1	1	1	1	1	1	1	1	-1

Example

根据上表，计算下列概率 $P(Y=1)=\frac{9}{15},P(Y=-1)=\frac{6}{15}$ $P(X^{(1)}=1|Y=1)=\frac{2}{9},P(X^{(1)}=2|Y=1)=\frac{3}{9},P(X^{(1)}=3|Y=1)=\frac{4}{9}$ $P(X^{(2)}=S|Y=1)=\frac{1}{9},P(X^{(2)}=M|Y=1)=\frac{4}{9},P(X^{(2)}=L|Y=1)=\frac{4}{9}$ $P(X^{(1)}=1|Y=-1)=\frac{3}{6},P(X^{(1)}=2|Y=-1)=\frac{2}{6},P(X^{(1)}=3|Y=-1)=\frac{1}{6}$ $P(X^{(2)}=S|Y=-1)=\frac{3}{6},P(X^{(2)}=M|Y=-1)=\frac{2}{6},P(X^{(2)}=L|Y=-1)=\frac{1}{6}$

对于数据 $x=(3,M{)}^T$ 可得出： $P(Y=1)P(X^{(1)}=3|Y=1)P(X^{(2)}=M|Y=1)=\frac{9}{15}\times \frac{3}{9}\times \frac{4}{9}=\frac{4}{45}$ $P(Y=-1)P(X^{(1)}=3|Y=-1)P(X^{(2)}=M|Y=-1)=\frac{6}{15}\times \frac{1}{6}\times \frac{2}{6}=\frac{2}{90}$ 根据两个概率可以得出，应该预测分类为 $Y=1$

决策树

• 参考资料：
  • 《统计学习方法第 2 版》——李航
  • 数据挖掘技术课程

决策树由节点和有向边组成，节点分为内部节点和叶子节点，内部节点表示划分属性，叶子节点是最后的分类结果

下图是决策树算法的主要内容：

信息增益

假设有一组数据，有 n 个不同的属性特征，对任意一个特征 $x$ 有以下分析：

• 熵的概念 设 X 为一个取有限值的离散随机变量，对整个系统的熵为：$H(X)=-\sum _{i=1}^n{p}_i\log p_i$，熵越大，随机变量的不确定性就越大，公式中的 $p_i$ 表示取离散值 $x_i$ 的概率 $P(X=x_i)$
• 条件熵的概念 条件熵 $P(Y|X)$ 表示在已知随机变量 $X$ 的条件下，随机变量 $Y$ 的不确定性 $H(Y|X)=\sum _{i=1}^n{p}_{i}H(Y|X=x_i)$

信息增益表示得知特征 $X$ 的信息而使类 $Y$ 的信息不确定性减少的程度

• 信息增益的定义： 特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$，定义为集合 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$ 之差，即 $g(D,A)=H(D)-H(D|A)$

Note

上文的“经验”指的是通过统计结果计算熵和条件熵，其思想是极大似然估计

Example

• 计算标签类别的经验熵$H(D)$，熵越小表示数据越稳定： $H(D)=-\frac{6}{15}\log \frac{6}{15}-\frac{9}{15}\log \frac{9}{15}=0.971$
• 设年龄、有工作、有自己的房子、信贷情况为特征 $A_1,A_2,A_3,A_4$，分别计算它们的经验条件熵和信息增益
  1. $H(D|A_1)=\frac{5}{15}\times \left(-\frac{2}{5}\log \frac{2}{5}-\frac{3}{5}\log \frac{3}{5}\right)+\frac{5}{15}\times \left(-\frac{3}{5}\log \frac{3}{5}-\frac{2}{5}\log \frac{2}{5}\right)+\frac{5}{15}\times (-\frac{4}{5}\log \frac{4}{5}-\frac{1}{5}\log \frac{1}{5})=0.888$ $g(D,A_1)=0.971-0.888=0.083$
  2. $H(D|A_2)=\frac{5}{15}\times (-1\log 1-0\log 0)+\frac{10}{15}\times (-\frac{4}{10}\log \frac{4}{10}-\frac{6}{10}\log \frac{6}{10})$ $g(D,A_2)=0.324$
  3. $H(D|A_3)=\frac{6}{15}\times 0+\frac{9}{15}(-\frac{3}{9}\log \frac{3}{9}-\frac{6}{9}\log \frac{6}{9})=0.551$ $g(D,A_3)=0.420$
  4. $H(D|A_4)=\frac{5}{15}\times \left(-\frac{1}{5}\log \frac{1}{5}-\frac{4}{5}\log \frac{4}{5}\right)+\frac{6}{15}\times \left(-\frac{4}{6}\log \frac{4}{6}-\frac{2}{6}\log \frac{2}{6}\right)+\frac{4}{15}\times 0=0.608$ $g(D,A_3)=0.363$ 从上面的计算来看，特征 $A_3$ 最合适用来划分数据

信息增益比

信息增益偏向于生成分支较多的树，因为分支越多，它的条件熵就可能越低

为了修正这个问题，我们需要使用信息增益比：

$g_R(D,A)=\frac{H(D)-H(D|A)}{H_A(D)}$，其中 $H_A(D)$ 表示特征 $A$ 的经验熵（有点像对信息增益做了一次标准化），$H_A(D)=-\sum _{i=1}^n\frac{|D_i|}{|D|}\log \frac{|D_i|}{|D|}$

基尼指数

适用于分类树的生成，能够决定改特征的最优二值切分点

分类问题中，假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_k$，则概率分布的基尼指数定义为

$$Gini(p)=\sum _{k=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K{p}_k^2$$

对于二分类问题，可简化为

$$Gini(D)=p(1-p)+(1-p)(1-(1-p))=2p(1-p)$$

基尼指数和熵的概念有异曲同工之妙，当划分的类概率为 $p_k$ 时，与其不是 $p_k$ 的概率 $(1-p_k)$ 对系统的熵为 $Entro=-p_k\log p_k-(1-p_k)\log (1-p_k)$，基尼指数的表示更加简单，但也反映了所包含的信息量

对于给定样本的集合 $D$，其基尼指数为

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

在特征 $A$ 的条件下，集合 $D$ 的基尼指数定义为

$$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$$

剪枝算法

剪枝算法=损失函数+正则化惩罚项

设树 T 的叶结点个数为 $|T|$，$t$ 是树 $T$ 的叶结点，该叶结点有 $N_t$ 个样本点，其中 $k$ 类的样本点有 $N_{tk}$ 个，$k=1,2,\cdots ,K$，$H_t(T)$ 为叶结点 $t$ 上的经验熵，$\alpha \ge 0$ 为参数，则决策树学习的损失函数可以定义为：

$$C_{\alpha }(T)=\sum _{t=1}^{|T|}{N}_t{H}_t(T)+\alpha |T|$$

其中经验熵为：

$$H_t(T)=-\sum _k\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}$$

如果将第一项记为 $C(T)=-\sum _{t=1}^{|T|}\sum _{k=1}^K{N}_{tk}\log \frac{N_{tk}}{N_t}$ ，则公式可以简化为：

$$C_{\alpha }=C(T)+\alpha |T|$$

Note

算法步骤：

1. 计算每个节点的经验熵
2. 递归地从叶节点向上回缩 比较回缩 $T(A)$ 与不回缩 $T(B)$ 的剪枝损失，然后进行比较 如果 $C_{\alpha }(A)\le C_{\alpha }(B)$，则进行剪枝操作
3. 重复步骤 2，直到不能继续为止

Attention

优点：可以从结构上简化决策树，提高泛化能力 缺点：简化决策树容易造成欠拟合，不能保证划分准确性的提升

在进行剪枝时，我们可以利用数据集的验证集，进行预剪枝/后剪枝

• 预剪枝：预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛化性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点
• 后剪枝：后剪枝就是先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛化性能的提升，则把该子树替换为叶结点

最小二乘回归树

• 参考资料
  • 回归树的生成 - 知乎 (zhihu.com)

假设已将输入的特征空间划分为 $M$ 个单元 $R_1,R_2,\dots ,R_M$，并且在每个单元 $R_m$ 上有一个固定的输出值 $c_m$，于是回归树模型可以表示为

$$f(x)=\sum _{m=1}^M{c}_{m}I(x\in R_m)$$

其中 $I$ 为指示函数，上面的式子表示输入 x 在回归树的划分 $I$ 下最终有一个唯一的输出 $c_m$

我们使用平方误差 $\sum _{x_i\in R_m}(y_i-f(x_i))$ 来表示回归树对于训练数据的预测误差，我们的目标是 $\min {\sum _{x_i\in R_m}(y_i-f(x_i))}^2$，并取 ${\hat{c}}_m=avg(y_i|x_i\in R_m)$

看电视时长	婚姻状况	职业	年龄
3	未婚	学生	12
4	未婚	学生	18
2	已婚	老师	26
5	已婚	上班族	47
2.5	已婚	上班族	36
3.5	未婚	老师	29
4	已婚	学生	21

Example

下面我们将利用上面的数据对年龄进行预测 首先将 $j$ 的属性选为职业，则有三种划分情况{“老师”，“学生”}、{“上班族”}以及{“老师”，“上班族”}、{“学生”}，最后一种为{“学生”，“上班族”}、{“老师”}

1. 第一种情况 R1={“学生”}，R2={“老师”，“上班族”} $c_1=\frac{12+18+21}{3}=17$ $c_2=\frac{26+47+36+29}{4}=34.5$ $y_i=(\{12,18,21\},\{26,47,36,29\})$ 最小平方误差为：$m=42+261=303$
2. R1={“老师”}，R2={“学生”，“上班族”} $c_1=\frac{26+29}{2}=27.5$ $c_2=\frac{12+18+47+36+21}{5}=26.5$ $y_i=(\{26,29\},\{12,18,47,36,21\})$ 最小平方误差为：$m=4.5+738.16=742.66$
3. 划分情况为 R1={“上班族”}，R2={“学生”，“老师”} $c_1=\frac{47+36}{2}=41.5$ $c_2=\frac{12+18+26+29+21}{5}=21.2$ $y_i=(\{47,36\},\{12,18,26,29,21\})$ 最小平方误差为：$m=60.5+178.8=239.3$

由上面的分析可知，应该选择第三种划分

CART

• 参考资料
  • 5.6 决策树：CART算法（6）——剪枝_哔哩哔哩_bilibili

ID3 和 C4.5 都是基于信息增益的方法，适用于离散特征的分类，不再赘述

CART 生成算法和最小二乘法回归树方法差不多，分别计算出每个特征的最优切分点，然后找到最优特征的最优切分点作为划分的分支

在决策树的剪枝算法 中，我们需要考虑代价 $C(T)$ 和复杂度 $\alpha |T|$ 两个因素，如果取 $\alpha =0$ 就是一棵完整的树，如果取 $\alpha =+\infty$ 则是一个单结点树，因此 $\alpha$ 的取值十分重要，在 CART 中，考虑以下情况：

取 $0\le {\alpha }_0<{\alpha }_1<{\alpha }_2<\cdots <{\alpha }_n<{\alpha }_{n+1}<+\infty$，其中每一个 ${\alpha }_i$ 都是一个临界值，每个范围 $[{\alpha }_i,{\alpha }_{i+1})$ 都表示一个树 $T_i$

假如树 T 存在一个子树 $T_t$，则

![image.png](https://obsidian-pic-1258776558.cos.ap-nanjing.myqcloud.com/blog/20230605151055.png)

• 剪枝前损失函数为：$C_{\alpha }(T_t)=C(T_t)+\alpha |T_t|$
• 剪枝后损失函数为：$C_{\alpha }(t)=C(t)+\alpha$ （剪枝后只有一个叶子节点） 存在临界点使得 $C_{\alpha }(T_t)=C_{\alpha }(t)$，如果 $\alpha$ 再大一点，剪枝后损失函数的损失值就会小于剪枝前，偏向于进行剪枝，求出这个 $\alpha$ 临界值就是公式 $\alpha =\frac{C(t)-C(T_t)}{|T_t|-1}$

Summary

从上面的剪枝过程可以看出，$T_0,T_1,\dots$ 是有嵌套关系的，后者是前者的子树，在搞清楚 $\alpha$ 的取值过程后，我们需要利用公式求得最优决策树 $T_{\alpha }$

ensemble 算法

Kmeans、Kmedoid、DBSCAN、系统聚类、谱聚类、PCA 降维、EM 算法