什么是“熵和信息获得”?

我正在阅读这本书( NLTK ),它很混乱。 被定义为 :

熵是每个标签的概率乘以相同标签的对数概率的总和

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

我假设熵是在构build决策树的背景下提到的。

为了说明这一点,设想学习 把男性名字分为男性/女性的任务。 给出了一个名字列表,每个名字用mf标记,我们想要学习一个适合数据的模型 ,可以用来预测一个新的看不见的名字的性别。

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

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

 # 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 

目标是build立一个决策树 。 树的一个例子是:

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

基本上每个节点都代表一个属性的testing,我们根据testing的结果向左或向右。 我们继续遍历树,直到到达包含类预测的叶节点( mf

所以如果我们在这棵树上运行Amro这个名字,我们从testing开始“ 是长度<7? ”,答案是肯定的 ,所以我们沿着这个分支走。 在分支之后,下一个testing“ 是元音的数量<3? ”再次评估为 。 这导致一个叶节点标记为m ,因此预测是男性 (我碰巧是,所以树预测结果正确 )。

决策树是以自上而下的方式构build的 ,但问题是如何select在每个节点上分割哪个属性? 答案是find将目标类最好地分解成最纯粹的子节点的特征(即:不包含男性和女性的混合节点,而仅包含一个类的纯节点)的特征。

这种纯度的测量称为信息 。 它代表了指定一个新的实例(名字)是否应该被分类为男性还是女性所需要的信息的预期量,以给出该节点的例子为例。 我们根据节点上的男性和女性的人数进行计算。

另一方面是衡量杂质 (相反)。 它被定义为值为a / b的二进制类 :

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

这个二进制熵函数如下图所示(随机variables可以取两个值中的一个)。 当概率为p=1/2时,它达到最大值,这意味着p(X=a)=0.5或类似的p(X=b)=0.5 ,其中ab的概率为50%/ 50%是最大的)。 当概率为p=1p=0时,熵函数的最小值为零,且p(X=a)=1p(X=a)=0 ,后者意味着p(X=b)=1 )。

https://en.wikipedia.org/wiki/File:Binary_entropy_plot.svg

当然,熵的定义可以推广到具有N个结果的离散随机variablesX(而不仅仅是两个):

熵

(公式中的对数通常取为2的对数 )


回到我们的名字分类任务,让我们来看一个例子。 想象一下在构build树的过程中,我们正在考虑如下的分割:

  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/14P(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 

现在通过比较分裂之前和之后的熵,我们获得了信息增益的度量,或者通过使用该特定特征进行分割而获得了多less信息:

 Information_Gain = Entropy_before - Entropy_after = 0.1518 

您可以将上述计算解释为:通过使用end-vowels特征进行分割,我们能够将子树预测结果的不确定性减less0.1518(以位 单位为单位的信息 )。

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

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

首先,理解the measure of information是最好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

公平的硬币翻转:

我们可以从一枚硬币翻转多less信息?

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

例2

如果一颗meteor明天袭击地球,那么我们可以得到22位信息。

如果太阳明天升起, p ~ 1则是0位信息。

所以如果我们对事件Yinteresting-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) 

logging所有日志的基数2。

我不能给你图像,但也许我可以给一个清晰的解释。

假设我们有一个信息通道,比如每天闪烁一次红色或绿色的光。 它传达了多less信息? 第一个猜测可能是每天一点。 但是如果我们添加蓝色,那么发件人有三个选项呢? 我们希望有一个能够处理除了2的幂以外的东西的信息,但仍然是可加的(将可能消息的数量乘以2的方式增加一位)。 我们可以通过logging2 (可能的消息的数量)来做到这一点,但事实certificate有一个更一般的方法。

假设我们已经回到了红色/绿色,但是红色的灯泡已经烧坏了(这是常识),所以灯必须一直闪烁绿色。 这个频道现在是无用的, 我们知道下一个闪光灯会是什么样子,闪光灯不传达任何信息,没有消息。 现在我们修理灯泡,但强制规定红灯泡可能不会连续闪烁两次。 当灯闪红灯时,我们知道下一个闪光是什么。 如果你试图通过这个频道发送一个比特stream,你会发现你必须用比它更多的闪存对它进行编码(事实上多了50%)。 如果你想描述一系列的闪光,你可以用更less的位来实现。 如果每个闪光灯都是独立的(上下文无关),但是相同的情况也适用,但是绿色闪光比红色更普遍:越可能越less倾向于描述序列所需的位数越less,所包含的信息越less,一直到全绿,灯泡烧坏限制。

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

 -log p i

越小,这个值就越大。 如果x i变得不太可能,那么这个值增加一个固定的量(log(2))。 这应该会提醒您在消息中添加一位。

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

 I =-Σp i log(p i

这是一闪而过的信息内容。

红色灯泡烧毁:p  = 0,p 绿 = 1,I =  - (0 + 0)= 0
红色和绿色等概率:p  = 1/2,p 绿= 1/2 ,I =  - (2 * 1/2 * log(1/2))= log
三种颜色,等概率:p i = 1/3,I =  - (3 * 1/3 * log(1/3))= log(3)
绿色和红色,绿色两次可能:p  = 1/3,p 绿 = 2/3,我=  - (1/3日志(1/3)+ 2/3日志(2/3))=日志3) -  2/3 log(2)

这是消息的信息内容或熵。 当不同的符号等概率时,它是最大的。 如果你是一个物理学家,你使用自然日志,如果你是一个计算机科学家,你使用日志2,并获得位。

我真的build议你阅读关于信息论,贝叶斯方法和MaxEnt。 David Mackay写的这本书(免费在线)

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

这些推理方法实际上比文本挖掘更普遍,我不能真正想出如何学习如何将其应用于NLP,而无需学习本书或其他有关机器学习和MaxEnt贝叶斯的入门书籍中的一般基础知识方法。

熵和概率论在信息处理和存储方面的联系真的很深刻。 为了体会它,有一个定理,由于香农说,你可以通过一个有噪声的通信通道没有错误的最大量的信息等于噪声过程的熵。 还有一个定理,它连接了多less可以压缩一块数据,以占用计算机中最小可能的内存,以及生成数据的进程的熵。

我不认为你真的有必要去了解所有关于交stream理论的定理,但是如果不学习关于什么是熵的基础知识,它是如何计算的,与信息和推论的关系是什么等等,这是不可能的。 …

当我执行algorithm来计算图像的熵时,我发现这些链接,请看这里和这里 。

这是我使用的伪代码,你需要适应它与文本而不是图像,但原则应该是相同的。

 //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) 

我从某个地方得到了这个代码,但我无法挖掘出这个链接。

正如你正在读一本关于NLTK的书,你会读到MaxEnt Classifier Module http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent

对于文本挖掘分类的步骤可能是:预处理(标记,蒸,用信息增益特征select…),转换为数字(频率或TF-IDF)(我认为这是了解使用文本作为只接受数字的algorithm的input),然后用MaxEnt进行分类,当然这只是一个例子。