[读书笔记]《西瓜书》第四章 决策树 铺垫

第四章 决策树 铺垫

从这个章节开始，就是对具体的机器学习模型的学习开展了，而《机器学习》这本书安排的第一个章节就是决策树，面对这个章节，从自己的经验看来，并不是具体的决策树的模型的学习，而是对信息论基础知识的铺垫，当然模型固然也很重要，但是在此之前，还是需要铺垫一下相关内容，更容易对后续的模型学习的展开。可能这就是我基础不够扎实的原因吧（后悔当初有时间的时候没有多读几本书~）

机器学习中的信息论

1948年Shannon博士的《A Mathematical Theory of Communication》（通信的数学理论）横空出世，创世般地开辟了信息论，信息论从此便在通信领域发光发热，为通信工程方面的成功奠定了坚实的理论基础。然而信息论是一门普适性理论，它被认为当下热潮的人工之能和机器学习修炼“内功”，这是因为人工智能本质是处理信息的，本人以为机器学习的算法可以用信息论的思维去理解。

在决策树的整个模型集合中，信息论中的信息熵（Entropy）的概念几乎就是串联起各种模型的一条脉络线，想要很好的掌握这个部分的内容，必须要先掌握这个部门的知识。不仅在决策树中信息熵占有了大量的比重，其实对于损失函数的定义来说，基本也是围绕着信息论中的交叉熵和相对熵来展开的，这点，在后续学了感知机模型和神经网络之后会有切实的感悟。

PS: 写道这个地方，不得不感叹一下，机器学习这门学科真的是对计算科学的一集大成者~

OK，回过头来，开始正式摘抄别人梳理的内容放在下面，主要是帮助自己梳理相应的知识点，毕竟本人也不能算上信息论的大神或者机器学习的大神，只是作为一个备忘录，帮助自己整理思路。

信息熵

定义：信息是用来消除随机不确定性的东西，信息熵是消除不确定性所需信息量的度量，也即未知事件可能含有的信息量，是所有类别中所有可能值包含的信息期望。

公式定义：

$$\text{Ent}(X)=-\sum_{i=1}^n p_i \log_2 p_i,\quad i=1,2,\cdots,n$$

几个要点

• 噪音是获取信息时的干扰
• 消除熵 = 获得信息
• 数据 = 噪声 + 信息

相对浅层的理解

信息熵只反映内容的随机性，与内容本身是什么无关，较大的信息熵只表示可能出现的符号较多，即编码的时候所需要的信息位数较大，但并不意味着你可以从中获得更大量的信息。

• 熵值越大，随机变量不确定性越大，熵值越小，随机变量不确定性越小
• 随机变量的取值个数越多，状态数也就越多，信息熵就越大，混乱程度就越大
• 当随机分布为均匀分布时，熵最大，且 $0 \le \text{Ent}(X) \le \log n$

相对深层的理解

信息熵是相对于观察者已经对该事件的实际了解程度而言的，是客观存在一种物理量，不随观测者的主观意识而改变，但是度量的时候是相对个体和事件层面而言的，即既是客观的又是主观的。

• 与媒介无关
• 相对个体而言
• 相对事件而言

此外在进行信息的传递时，假设我们一编码的形式来传递信息，则显而易见的就是我们可以利用非均匀分布的特点，避免造成以过量容量的编码形式来传递较少的信息内容，所以：“使用更短的编码来描述更可能的事件，使用更长的编码来描述不太可能的事件” 是显而易见的。

因为对数的运算法则是 $\log_a(mn)=\log_a m + \log_a n$ 因此，我们有 $I(x)=−\log_a p(x)$。其中负号是用来保证信息量是正数或者零(因为$p(x)$通常是概率值)。而 $\log$ 对数函数基的选择是任意的（信息论中基常常选择为2，因此信息的单位为比特bits；而机器学习中基常常选择为自然常数，因此单位常常被称为奈特nats）

补充一点：Shannon 编码表明熵是传输一个随机变量状态值所需的比特位下界（最短平均编码长度）

在了解了上述的基础上，继续衍生一下，就有了下面的四个概念，其实相对来说理解就不这么困难了，很好掌握。

联合熵（Joint-Entropy）

定义：顾名思义就是借由联合分布概念演化过来的联合分布情况下的信息熵的求解。前面说的信息熵从公式就可以看的出来是基于一维随机变量分布得来的，那么推广到多维随机变量分布时，就变为了联合熵。

公式定义：

$$\text{Ent}(X,Y) = \sum_{x,y}p(x,y) \log p(x,y) = -\sum_{i=1}^n \sum_{j=1}^m p(x_i, y_j) \log p (x_i, y_j)$$

条件熵（Conditional-Entropy）

定义：条件熵 $\text{Ent}(Y|X)$ 表示在已知随机变量 $X$ 的条件下随机变量 $Y$ 的不确定性，即也是可以建立在随机过程中的条件概率推演过来进行类比学习的，因此，条件熵 $\text{Ent}(Y|X)$ 即表示了 $X$ 在给定条件下 $Y$ 的条件概率分布的熵对 $X$ 的数学期望。

公式定义：

$$\text{Ent}(Y|X)= \sum_x p(x) \text{Ent}(Y|X=x) = -\sum_{x,y}p(x,y) \log p(y|x)$$

PS: 条件熵 相当于 联合熵 减去 信息熵。即：$\text{Ent}(Y|X) = \text{Ent}(X,Y) - \text{Ent}(X)$

相对熵（Relative-Entropy）

定义：假设队医同一个随机变量 $x$ 有两个单独的概率分布，相对熵可以用来衡量这两个概率分布之间的差异，即通俗的可以这么理解：当我们面前有两个离散随机分布的时候，我们想知道这两个随机分布是否一致，则这个时候就可以用相对熵来衡量，也称KL散度（Kullback-Leibler Divergence）

公式定义：

$$D_{KL}(p||q) = \sum_{x} p(x) \log \frac{p(x)}{q(x)} = E(p(x)) \log \frac{p(x)}{q(x)}$$

PS: 相对熵具有不对称性，即 $D_{KL}(p||q) \neq D_{KL}(q||p)$，$D_{KL}的值越小，表示q分布与p分布越接近$

交叉熵（Cross-Entropy）

定义：交叉熵是用来衡量在给定的真实分布下，使用非真实分布指定的策略消除系统的不确定性所需要付出努力的大小，目的是：让熵尽可能小，即存储空间小（消除系统的不确定的努力小）。这是引用别人所给出的定义，独立看来并不是很好理解，但是结合相对熵的概念看，就容易理解多了。

公式定义：

这里在给出公式之前，先对相对熵的公式做一个变形

$$ \begin{align} D_{KL}(p||q) & = \sum_{i=1}^n p(x_i) \log p(x_i) - \sum_{i=1}^n p(x_i) \log q(x_i) \\
& = -\text{Ent}(p(x)) - \sum_{i=1}^n p(x_i) \log q(x_i) \end{align} $$

可以看出前面是 $p$ 随机分布下的信息熵，而后面则是二者的交叉熵。

$$\text{Ent}(p, q) = - \sum_{i=1}^n p(x_i) \log q(x_i)$$

PS: 在机器学习中，我们需要评估label和predicts之间的差距，使用相对熵（KL散度）刚刚好，但由其公式中前面一部分是不改变的，因此在优化过程中，只需要关注交叉熵就行了，所以一边机器学习都是直接使用交叉熵做损失函数评估和优化模型。

这里不知道自己理解的对不对，同时也是参考了别人的见解: “这其实蕴含了一个小trick，如果损失函数使用相对熵的话，则局部极小值点是真实分布下信息熵的值，而交叉熵的局部极小值点是0，而真实分布下的信息熵又该如何获得呢？也是一个难题”

下面是YJango大佬的B站视频直达链接和知乎专栏链接搬运

Reference:

• 详解机器学习中的熵、条件熵、相对熵和交叉熵
• 信息论（1）——熵、互信息、相对熵
• 信息论（2）——熵的唯一性定理
• 【直观详解】信息熵、交叉熵和相对熵
• Why You Should Use Cross-Entropy Error Instead Of Classification Error Or Mean Squared Error For Neural Network Classifier Training

以上内容也可以到我的 Github 去查看(附了相应实现代码哟) Machine-Learning-Notes