什么是"熵和信息增益"？

Question

我正在读这本书(NLTK),这令人困惑. 熵被定义为:

熵是每个标签乘以同一标签的对数概率的概率之和

如何在文本挖掘方面应用熵和最大熵？有人可以给我一个简单,简单的例子(视觉)吗？

Answer 1

我假设在构建决策树的背景下提到了熵.

为了说明这一点,想象的任务学习到分类第一名称为男性/女性群体.这给出了一个名称列表,每个名称都标有m或者f,我们想要学习一个适合数据的模型,并且可以用来预测一个新的看不见的名字的性别.

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

第一步是确定数据的哪些特征与我们想要预测的目标类相关.一些示例功能包括:第一个/最后一个字母,长度,元音数量,是否以元音结尾等.因此,在提取特征后,我们的数据如下所示:

# 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

目标是构建决策树.树的一个例子是:

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,我们首先测试" 长度<7？ "并且答案是肯定的,所以我们沿着那个分支走下去.在分支之后,下一个测试" 是元音的数量<3？ "再次评估为真.这导致标记的叶节点m,因此预测是男性(我恰好是,所以树正确地预测了结果).

决策树以自上而下的方式构建,但问题是如何选择在每个节点拆分哪个属性？答案是找到最能将目标类拆分为最纯粹的子节点的功能(即:不包含男性和女性混合的节点,而只包含一个类的纯节点).

这种纯度测量称为信息.它代表了预期的量的信息,将需要指定一个新的实例(直呼其名)是否应归类男性或女性,因为到达节点的例子.我们根据节点上的男性和女性类的数量来计算它.

另一方面,熵是杂质的量度(相反).它是一个定义二进制类与值a/b为:

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

这个二元熵函数如下图所示(随机变量可以取两个值中的一个).当概率达到最大值时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公式中的公式通常作为基数2的对数)

回到我们的名称分类任务,让我们看一个例子.想象一下在构建树的过程中的某个时刻,我们正在考虑以下分裂:

     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

我们使用每个分支下的实例数作为权重因子(左边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(以位为单位的信息单位测量).

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

请注意,我跳过了一些超出本文范围的细节,包括如何处理数字特征,缺失值,过度拟合和修剪树等.

Answer 2

首先,最好理解the measure of information.

我们如何获得measure这些信息？

当不太可能发生的事情发生时,我们说这是一个重大新闻.而且,当我们说出可预测的东西时,它并不是真的很有趣.所以要量化这个interesting-ness,函数应该满足

• 如果事件的概率是1(可预测),则函数给出0
• 如果事件的概率接近0,那么函数应该给出高数
• 如果发生概率0.5事件则给出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位的信息.

熵

因此,如果我们对interesting-ness事件采取期望Y,那么它就是熵.即熵是事件兴趣的预期值.

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.

Answer 3

我不能给你图形,但也许我可以给出一个明确的解释.

假设我们有一个信息通道,例如每天闪烁一次红色或绿色的灯.它传达了多少信息？第一个猜测可能是每天一点.但是如果我们添加蓝色,那么发送者有三个选项呢？我们希望有一些信息可以处理除2的幂之外的其他信息,但仍然是可加性的(将可能的消息数乘以2的方式增加一位).我们可以通过记录₂(可能的消息数)来做到这一点,但事实证明这是一种更通用的方式.

假设我们回到了红色/绿色,但红色灯泡烧坏了(这是常识),因此灯必须始终闪烁绿色.这个频道现在没用了,我们知道下一个闪光灯会是什么,所以闪光灯没有传达信息,没有新闻.现在我们修理灯泡,但规定红灯泡可能不会连续两次闪光.当指示灯闪烁红色时,我们知道下一个闪光灯会是什么.如果你尝试通过这个通道发送一个比特流,你会发现你必须使用比你有更多的闪存编码它(事实上多50%).如果你想描述一系列闪光,你可以用更少的比特来完成.如果每个闪存是独立的(无上下文),则同样适用,但绿色闪烁比红色更常见:概率越多,描述序列所需的位越少,所包含的信息越少,一直到全绿色,灯泡烧坏限制.

事实证明,有一种方法可以根据不同符号的概率来测量信号中的信息量.如果接收符号x _i的概率是p _i,则考虑数量

-log pi

p _i越小,该值越大.如果x _i变得不可能的两倍,则该值增加固定量(log(2)).这应该提醒您在消息中添加一位.

如果我们不知道符号是什么(但我们知道概率)那么我们可以通过总结不同的可能性来计算这个值的平均值,我们将获得多少:

I = -Σ pi log(pi)

这是一次性的信息内容.

Red bulb burnt out: pred = 0, pgreen=1, I = -(0 + 0)  = 0
Red and green equiprobable: pred = 1/2, pgreen = 1/2, I = -(2 * 1/2 * log(1/2)) = log(2)
Three colors, equiprobable: pi=1/3, I = -(3 * 1/3 * log(1/3)) = log(3)
Green and red, green twice as likely: pred=1/3, pgreen=2/3, I = -(1/3 log(1/3) + 2/3 log(2/3)) = log(3) - 2/3 log(2)

这是消息的信息内容或熵.当不同的符号是等概率时,它是最大的.如果您是物理学家,则使用自然日志,如果您是计算机科学家,则使用log ₂并获取位.

Answer 4

我真的建议你阅读有关信息理论,贝叶斯方法和MaxEnt的内容.开始的地方是David Mackay撰写的这本(免费在线)书籍:

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

这些推理方法实际上远比文本挖掘更普遍,我无法真正设计如何在不学习本书或其他关于机器学习和MaxEnt贝叶斯的入门书籍中包含的一般基础知识的情况下如何将其应用于NLP方法.

熵和概率论对信息处理和存储的联系确实非常深刻.为了体验它,香农有一个定理,即通过噪声通信信道可以无错误地传递的最大信息量等于噪声过程的熵.还有一个定理可以连接您可以压缩一块数据以占用计算机中最小可能内存的数量与生成数据的过程的熵.

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

Answer 5

非正式地

熵是信息或知识的可用性，缺乏信息将导致预测未来的困难，即高熵（文本挖掘中的下一个词预测），而信息/知识的可用性将帮助我们更现实地预测未来（低熵）。

任何类型的相关信息都会减少熵并帮助我们预测更现实的未来，这些信息可以是句子中出现“肉”这个词或不出现“肉”这个词。这称为信息增益

正式地

熵是缺乏可预测性的顺序

Answer 6

When I was implementing an algorithm to calculate the entropy of an image I found these links, see here and here.

This is the pseudo-code I used, you'll need to adapt it to work with text rather than images but the principles should be the same.

//Loop over image array elements and count occurrences of each possible
//pixel to pixel difference value. Store these values in prob_array
for j = 0, ysize-1 do $
    for i = 0, xsize-2 do begin
       diff = array(i+1,j) - array(i,j)
       if diff lt (array_size+1)/2 and diff gt -(array_size+1)/2 then begin
            prob_array(diff+(array_size-1)/2) = prob_array(diff+(array_size-1)/2) + 1
       endif
     endfor

//Convert values in prob_array to probabilities and compute entropy
n = total(prob_array)

entrop = 0
for i = 0, array_size-1 do begin
    prob_array(i) = prob_array(i)/n

    //Base 2 log of x is Ln(x)/Ln(2). Take Ln of array element
    //here and divide final sum by Ln(2)
    if prob_array(i) ne 0 then begin
        entrop = entrop - prob_array(i)*alog(prob_array(i))
    endif
endfor

entrop = entrop/alog(2)

I got this code from somewhere, but I can't dig out the link.