Attention: This blog is a reading note of Tree - Information Theory in Chinese, which is written in English. As missing or misunderstanding might be included, please reference the original text if needed. We believe that the original text containing some misunderstandings on information theory itself, and we correct it in our version.
注意：本系列主要关注涉及分类决策和回归树/森林的理论，以及回归树/森林的代码实现。
近年来，基于决策树的集成算法在机器学习和数据挖掘界被广泛应用，并受到了大多数人的好评和欢迎。随机森林（Random Forest）是这批算法中的佼佼者，其拥有很高的准确率，同时兼具很高的运行效率和对于异常数据与过拟合的鲁棒性。因而，我们撰写了这一系列的博客，希望能够系统地介绍随机森林的原理和实现的方法。
随机森林的本质是决策树的集成，我们需要先阐述决策树背后的原理。而在此之前，我们需要先了解他们共同依赖的理论基础：信息论。（注意：本篇仅涉及对于其理论的直观认识，如需要严格的数学论证，请参阅原论文）
何为信息
如果我们希望传输一个由四个字符构成的字符串，例如 ACABBDAA，我们需要多少比特？一种常见的想法是通过一个定长的比特串来表达每个字符，也就是令 A = 00, B = 01, C = 10, D = 11，那么我们可以得到我们的答案：2 * 8 = 16 位比特。
那么我们可以使用更少的比特来表达相同的信息吗？答案是肯定的。首先，我们刚才的问题抽象为公式可以表达为：
$$E(N)=\sum_{k\in A,B,C,D}n_k* p(x=k)$$
其中，$n_k$ 是字符 $k$ 所占用的比特数量，$p(x=k)$ 是字符
$k$ 在字符串 $N$ 中出现的频率。对于四个字符，这个值分别是 0.5, 0.25, 0.125, 0.125。
因为因为我们上面的例子中，ABCD并非是均匀分布的，所以我们可以考虑通过改变 $n_k$ 的大小来使用更少的比特传输同样的数据。一种常见的办法是使用 Huffman 编码来压缩信息所需的空间。在此例中即令 A = 0, B = 10, C = 110, D = 111，最终我们可以在平均每个字符 1.75 个比特的情况下，实现对于原信息的表达。
似乎巧合的是，我们用来表达字符的比特数量似乎刚好满足 $n_k=-log_2(p(x=k))$。实际上，这是由二进制为载体的信息传输的性质决定的。每个比特都可以将一个值集合划分为两个子集，直到所有子集均只有一个值为止。因而我们实际上寻求的是一个最优的划分方法——而这显然是不断在数量上进行平分。为了方便理解，我们可以将其抽象为一棵二叉树，左子树和右子树分别代表在一位上为 0 和 1，而叶节点则指示了各值的编码。在此语境下，$n_k=-log_2(p(x=k))$ 表示的就是叶节点所处的层数，也就是所需的二进制的位数。
综上，我们能够得到表达一段信息所需要的最少平均比特数：
$$H(X)=-\sum_ip_i*log_2p_i$$
这在某种意义上可以代表信息的量。在信息论中，我们称之为信息熵（Information Entropy），或者简称为熵（Entropy），并用来衡量信息的多少（对于连续量，该值为 $H(X)=-\int_xp(x)*log_2p(x)dx$）。
熵：更进一步
为什么是「熵」？
熵并不是 Andrew 教授生造的概念，而是一个热力学中表征物质状态的参量。在物理上，熵是体系混乱程度的度量。直观地来讲，一个系统越混乱，其包含的信息就越多。例如一块100%纯净的有序晶体，要描述它的构造，我们只需要晶胞的构造式和数量即可；而要描述一块路边的碎石，我们则需要描述其内复合的各种物质，以及他们之间的结合关系——这是由混乱带来的信息量增长，也就是信息熵的本质。
而之后我们将要讲到的决策树将这种混乱称为“杂质”，它期望的是将通过将充满杂质的碎石通过某种规则“纯化”为数个有序晶体，并将这个学习到的规则应用到更广泛的样本中来达到回归或分类的效果。
交叉熵（Cross Entropy）
交叉熵（Cross Entropy） 用于描述两个在同一数据集上的概率分布的信息差。更直观地来说，交叉熵是对同一组对象的两个信息之间的“歧义”，讨论的对象是一个“目标”信息和一个“当前”信息，这个信息可以是规则（如决策树的分类规则），数据等等。其研究的是两个信息之间的差距。或者说使用当前的信息，需要多少 bit 才能描述目标信息。基于前面的叙述，令 $p$ 为目标信息分布，$q$ 为当前信息分布，那么交叉熵的公式是直观的：
$$H(p, q)=-\sum_{x\in\mathcal{X}}p(x)\ log\ q(x)$$
从压缩的角度来说，它表示一个压缩模式 $q$ 对于真实模式 $p$ 的效果，或者说使用 $q$ 来表示 $p$ 内信息所需要的平均比特数量。
信息增益（Information Gain）
继续跟随我们刚才的逻辑，我们已经知道，$H(Y,X)$ 是在引入了信息 $X$ 后，与 $Y$ 信息之间的差距，或者说歧义。也可以说是在引入 $X$ 后 $Y$ 中仍不确定的信息量。考虑 $H(Y)$ 为随机变量 Y 所携带的信息量，令它减去 $H(Y,X)$，得到的 $H(Y)-H(Y,X)$ 就是“通过引入 $X$ 所确定的信息量”。在信息论中，我们称之为信息增益（Information Gain）：
$$IG = H(Y) - H(Y,X)$$
注意：在某些文献中，Information Gain 被认为与 Kullback–Leibler divergence 同义，而实际上后者的定义式为 $D_{KL}(Y||X)=\sum_{x\in\mathcal{X}}Y(x)log(\frac{Y(x)}{X(x)})=H(Y,X)-H(Y)$
一个直观的认识是，当 $X$ 和 $Y$ 具有某种联系的时候，通过确定 $X$ 的信息，我们就能一定程度上了解 $Y$ 的信息，从而降低了 $Y$ 的信息熵，减少的这部分就是引入 $X$ 所带来的信息增益。决策树算法的主要理论依据正是信息增益。
