什么是“熵和信息增益”?

beos 发布于 2019-11-10 math 最后更新 2019-11-10 12:10 219 浏览

我正在阅读这本书(NLTK),它很混乱。熵是defined as

Entropy is the sum of the probability of each label times the log probability of that same label
如何在文本挖掘方面应用熵和最大熵?有人能给我一个简单,简单的例子(视觉)吗?
已邀请:

mnatus

赞同来自:

内容太长未翻译

uid

赞同来自:

当你正在读一本关于NLTK的书时,你会读到关于MaxEnt分类器模块http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent的内容会很有趣。 对于文本挖掘分类,步骤可以是:预处理(标记化,蒸汽,具有信息增益的特征选择......),转换为数字(频率或TF-IDF)(我认为这是使用时理解的关键步骤)文本作为只接受数字的算法的输入,然后用MaxEnt进行分类,这肯定只是一个例子。

set

赞同来自:

首先,最好了解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比特的信息。

因此,如果我们对事件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)
所有日志的日志库2。

id_sed

赞同来自:

当我实现算法来计算图像的熵时,我找到了这些链接,请参阅herehere。 这是我使用的伪代码,你需要调整它来处理文本而不是图像,但原则应该是相同的。

//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)
我从某个地方得到了这个代码,但我无法挖掘出这个链接。

tmodi

赞同来自:

我真的建议你阅读有关信息理论,贝叶斯方法和MaxEnt的内容。开始的地方是David Mackay撰写的这本(免费在线)书籍: http://www.inference.phy.cam.ac.uk/mackay/itila/ 那些推理方法实际上远比文本挖掘更普遍,我无法真正设计如何在不学习本书或其他关于机器学习和MaxEnt贝叶斯的入门书籍中包含的一般基础知识的情况下如何将其应用于NLP方法。 熵和概率论对信息处理和存储的联系确实非常深刻。为了体验它,有一个定理归因于香农,它指出通过噪声通信信道可以无错误地传递的最大信息量等于噪声过程的熵。还有一个定理可以连接您可以压缩一块数据以占用计算机中最小可能内存的数量与生成数据的过程的熵。 我不认为你真的有必要去学习关于通信理论的所有定理,但是如果不学习关于什么是熵,它是如何计算的,它与信息和推理的关系等等的基础知识,就不可能学到这一点。 ...

eenim

赞同来自:

我不能给你图形,但也许我可以给出一个明确的解释。 假设我们有一个信息通道,例如每天闪烁一次红色或绿色的灯。它传达了多少信息?第一个猜测可能是每天一点。但是如果我们添加蓝色,那么发送者有三个选项呢?我们希望有一些信息可以处理除2的幂之外的其他信息,但仍然是可加性的(将可能的消息数乘以2的方式增加一位)。我们可以通过记录log 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 2 并获取位。