问什么是“熵和信息增益”？

EN

我假设熵是在构建的上下文中提到的。

为了说明这一点，想象一下learning将名字classify到男性/女性组中的任务。也就是说，给定一个名字列表，每个名字都标有m或f，我们希望学习一个符合数据的model，并可以用来预测一个新的看不见的名字的性别。

name       gender
-----------------        Now we want to predict 
Ashley        f              the gender of "Amro" (my name)
Brian         m
Caroline      f
David         m

第一步是deciding，数据的与我们想要预测的目标类相关。一些示例特征包括:首字母/末尾字母、长度、元音数量、是否以元音结尾等。因此，在特征提取之后，我们的数据如下所示：

# name    ends-vowel  num-vowels   length   gender
# ------------------------------------------------
Ashley        1         3           6        f
Brian         0         2           5        m
Caroline      1         4           8        f
David         0         2           5        m

我们的目标是构建一个decision tree。tree的一个例子是：

length<7
|   num-vowels<3: male
|   num-vowels>=3
|   |   ends-vowel=1: female
|   |   ends-vowel=0: male
length>=7
|   length=5: male

基本上，每个节点代表对单个属性执行的测试，我们根据测试结果向左或向右移动。我们继续遍历树，直到到达包含类预测(m或f)的叶节点

所以如果我们在这棵树下运行Amro这个名字，我们首先测试"is the length<7?“答案是肯定的，所以我们沿着那条支路走下去。在分支之后，下一个测试"is the number of vowels<3?“再次计算为true。这导致了一个标记为m的叶节点，因此预测是男性的(我碰巧是男性，所以树预测了结果correctly)。

决策树是built in a top-down fashion，但问题是如何选择在每个节点上拆分哪个属性？答案是找到最能将目标类划分为最纯粹的子节点的功能(即:不包含男性和女性混合的节点，而不是只包含一个类的纯节点)。

这种纯度的度量被称为。它表示在给定到达节点的示例的情况下，指定新实例(名字)应该被归类为男性还是女性所需的information的expected大小。我们根据节点上的男性和女性类的数量来计算它。

另一方面，是杂质的度量(相反)。它为具有值a/b的binary class定义为：

Entropy = - p(a)*log(p(a)) - p(b)*log(p(b))

此binary entropy function如下图所示(随机变量可以取两个值中的一个)。当概率为p=1/2时，它达到最大值，这意味着p(X=a)=0.5或类似的p(X=b)=0.5有50%/50%的机会是a或b (不确定性最大)。当概率为p=1或p=0且完全确定(分别为p(X=a)=1或p(X=a)=0，后者意味着p(X=b)=1)时，熵函数为零最小。

​

​

当然，熵的定义可以推广到具有N个结果(而不仅仅是两个)的离散随机变量X：

​

​

(公式中的log通常作为)

回到我们的名称分类任务，让我们来看一个例子。想象一下，在构建树的过程中，我们考虑了以下拆分：

     ends-vowel
      [9m,5f]          <--- the [..,..] notation represents the class
    /          \            distribution of instances that reached a node
   =1          =0
 -------     -------
 [3m,4f]     [6m,1f]

如你所见，在拆分之前，我们有9个男性和5个女性，即P(m)=9/14和P(f)=5/14。根据熵的定义：

Entropy_before = - (5/14)*log2(5/14) - (9/14)*log2(9/14) = 0.9403

接下来，我们将其与考虑拆分后通过查看两个子分支计算的熵进行比较。在ends-vowel=1的左分支中，我们有：

Entropy_left = - (3/7)*log2(3/7) - (4/7)*log2(4/7) = 0.9852

在ends-vowel=0的右侧分支中，我们有：

Entropy_right = - (6/7)*log2(6/7) - (1/7)*log2(1/7) = 0.5917

我们使用每个分支下的实例数作为weight factor来组合左右熵(7个实例向左，7个实例向右)，并在拆分后获得最终的熵：

Entropy_after = 7/14*Entropy_left + 7/14*Entropy_right = 0.7885

现在，通过比较拆分前和拆分后的熵，我们获得了的度量，或通过使用该特定特征进行拆分获得了多少信息：

Information_Gain = Entropy_before - Entropy_after = 0.1518

您可以将上面的计算解释为:通过使用end-vowels功能进行拆分，我们能够将子树预测结果中的不确定性减少0.1518 (以度量为)。

在树的每个节点，对每个特征执行该计算，并且以greedy方式选择具有最大信息增益的特征用于分割(从而有利于产生具有低不确定性/熵的纯分割的特征)。此过程从根节点向下递归应用，并在叶节点包含具有相同类的实例时停止(不需要进一步拆分它)。

请注意，我跳过了一些details，这些内容超出了本文的范围，包括如何处理numeric features、missing values、overfitting和pruning树等。

首先，最好理解the measure of information。

我们如何measure这些信息？

当一些不太可能发生的事情发生时，我们说这是个大新闻。此外，当我们说一些可预测的东西时，它并不是真的有趣。因此，要量化此interesting-ness，函数应满足

• 如果事件发生的概率为1(可预测)，则函数给出0
• 如果事件发生的概率接近于0，则函数应给出较高的数值
• 如果事件发生的概率为0.5，则函数应给出one bit of one bit

满足约束条件的一个自然度量是

I(X) = -log_2(p)

其中p是事件X的概率。这个单元是bit的，和计算机使用的是相同的位。0或1。

示例1

公平的掷硬币：

我们能从一次抛硬币中得到多少信息？

答案：-log(p) = -log(1/2) = 1 (bit)

示例2

如果明天有一颗流星撞上地球，p=2^{-22}，那么我们就能得到22比特的信息。

如果太阳明天升起，p ~ 1，那么它就是0比特的信息。

熵

因此，如果我们对事件Y的interesting-ness进行期望，那么它就是熵。即熵是事件的兴趣度的期望值。

H(Y) = E[ I(Y)]

更正式地说，熵是事件的预期位数。

示例

Y=1:事件X发生的概率为p

Y=0:事件X不会以概率1-p出现

H(Y) = E[I(Y)] = p I(Y==1) + (1-p) I(Y==0) 
     = - p log p - (1-p) log (1-p)

以2为底数的所有日志。

我真的推荐你阅读有关信息论、贝叶斯方法和MaxEnt的知识。从David Mackay写的这本书(在线免费下载)开始：

http://www.inference.phy.cam.ac.uk/mackay/itila/

这些推理方法真的比文本挖掘要通用得多，如果不学习本书或其他关于机器学习和MaxEnt贝叶斯方法的介绍性书籍中包含的一些一般基础知识，我真的无法设计如何将其应用于自然语言处理。

熵和概率论与信息处理和存储之间的联系真的很深。为了体验一下，香农的一个定理表明，通过嘈杂的通信通道可以无差错地传递的最大信息量等于噪声过程的熵。还有一个定理，将压缩一段数据以占用计算机中最小内存的程度与生成数据的过程的熵联系起来。

我不认为你真的有必要去学习所有这些关于沟通理论的定理，但如果不学习关于熵的基础知识，它是如何计算的，它与信息和推理的关系，等等，你就不可能学习这些定理。