什么是熵的计算机科学定义？

Question

我最近在我的大学开设了数据压缩课程.但是,我发现使用术语"熵",因为它适用于计算机科学而不是模棱两可.据我所知,它大致转化为系统或结构的"随机性".

计算机科学"熵"的正确定义是什么？

Answer 1

熵可能意味着不同的东西:

计算

在计算中,熵是由操作系统或应用程序收集的随机性,用于密码学或需要随机数据的其他用途.这种随机性通常是从硬件源收集的,既可以是现有的,也可以是鼠标移动或专门提供的随机生成器.

信息论

在信息论中,熵是与随机变量相关的不确定性的度量.在该上下文中,该术语本身通常是指香农熵,其在期望值的意义上量化消息中包含的信息,通常以比特为单位.等效地,香农熵是当不知道随机变量的值时丢失的平均信息内容的度量.

数据压缩中的熵

数据压缩中的熵可以表示您输入到压缩算法的数据的随机性.熵越多,压缩比越小.这意味着文本越随机,您压缩它的次数越少.

Shannon的熵表示对任何通信的最佳可能无损压缩的绝对限制:将消息编码为一系列独立且相同分布的随机变量,Shannon的源编码定理表明,在极限中,最短的平均长度对给定字母表中的消息进行编码的可能表示是它们的熵除以目标字母表中符号数的对数.

Answer 2

我最喜欢的定义,具有更实际的重点,可以在Andrew Hunt和David Thomas 出版的优秀书籍The Pragmatic Programmer:From Journeyman to Master中找到:

软件熵

虽然软件开发几乎不受所有物理定律的影响,但是熵会让我们难以接受.熵是物理学中的一个术语,指的是系统中"无序"的数量.不幸的是,热力学定律保证了宇宙中的熵趋于最大化.当软件无序增加时,程序员称之为"软件腐烂".

有许多因素可能导致软件腐烂.最重要的一个似乎是项目工作中的心理学或文化.即使你是一个团队,你的项目的心理可能是一个非常微妙的事情.尽管有最好的计划和最好的人,但一个项目在其生命周期中仍然会经历毁灭和腐烂.然而,还有其他一些项目,尽管面临巨大的困难和不断的挫折,但却成功地打击了大自然的无序倾向,并且能够很好地解决问题.

...

...

破窗户.

一个破碎的窗户,在任何相当长的时间内都没有修复,给建筑物的居民灌输了一种遗弃感 - 一种不关心建筑物的感觉.所以另一个窗口被打破了.人们开始乱扔垃圾.涂鸦出现了.严重的结构损坏开始.在相对较短的时间内,建筑物的损坏超出了主人修复它的愿望,并且放弃感变为现实.

"破窗理论"启发了纽约和其他主要城市的警察部门,以打击小东西,以阻止大事.它起作用:保持在破碎的窗户,涂鸦和其他小的违规行为之上,降低了严重的犯罪水平.

提示4

不要与破碎的Windows一起生活

不要将未破坏的"破窗"(糟糕的设计,错误的决定或糟糕的代码)留下.一发现就修复每一个.如果没有足够的时间来正确修理它,请将其登上.也许您可以注释掉有问题的代码,或者显示"未实现"消息,或者替换虚拟数据.采取一些行动,以防止进一步的损害,并表明你是最重要的.

文字取自:http://pragprog.com/the-pragmatic-programmer/extracts/software-entropy

Answer 3

我总是在香农熵的意义上遇到熵.

来自http://en.wikipedia.org/wiki/Information_entropy:

在信息论中,熵是与随机变量相关的不确定性的度量.在该上下文中,该术语本身通常是指香农熵,其在期望值的意义上量化消息中包含的信息,通常以比特为单位.等效地,香农熵是当不知道随机变量的值时丢失的平均信息内容的度量.

Answer 4

_{(来源:mit.edu)}

来自墨西哥大学

熵的信息理论概念是物理概念的概括.描述熵的方法有很多种.它是随机变量随机性的度量.它也是随机变量或随机过程包含的信息量的度量.它也是可以压缩消息量的下限.最后,需要询问有关随机实体确定其价值的是/否问题的平均数量.

用于概率计算的示例应用中的熵方程:

它是该值乘以该概率的对数的概率的rv的所有值的总和(即p(x)logp(x)).该等式可以从信息属性的第一原理导出.

Answer 5

超级简单的定义

熵这个词可以用一句话来定义：

“描述一个系统所需的信息量。”

想象一下宇宙膨胀的例子：从一开始，所有物质在大爆炸之前都聚集在一个小点中，所以我们可以用“所有物质都在一个点内”来描述这个系统。虽然今天需要更多的信息来描述系统（即宇宙），但人们需要描述所有行星的位置、它们的运动、它们上面的东西等。就信息论而言，这个定义也是有效的：例如：添加到密码（系统）的字母越多，描述密码所需的信息就越多。然后你可以用不同的单位来测量它，例如位或字符，例如“hello”= 5个字符熵= 40位熵（如果charsize是8位）。

由此还得出，您拥有的信息越多，您可以安排该信息的方式就越多。如果您有 40 位，则可以有 2^40 种不同的方式来安排它们。如果我们在这里谈论密码，那么信息（位）的可能排列越多，破解（使用暴力或字典攻击）所需的时间就越长。

Answer 6

这是对信息论中熵的一个很好的替代解释。

熵是进行预测所涉及的不确定性的度量。

我们也可以将熵描述为如果我们在做出初步预测后得到结果，我们会感到多么惊讶。

假设我们有一个弯曲的硬币，它在 99% 的情况下是正面，在 1% 的情况下是反面。由于只有百分之一的机会得到尾巴，如果我们真的得到尾巴，我们会非常惊讶。另一方面，如果我们得到一个人头也不会太令人惊讶，因为我们已经有 99% 的机会得到一个人头。

让我们假设我们有一个函数被调用Surprise(x)，它会给我们每个结果的惊喜数量；然后我们可以平均概率分布上的惊喜数量。这个惊喜的平均数量也可以用来衡量我们的不确定性。这种不确定性称为熵。

更新：

我做了这个可视化来描述动物图像分类器模型（机器学习）中预测类的熵和置信度之间的关系。在这里，熵用作衡量分类器模型对其预测的置信度的度量。

这些图显示了来自两个分类器模型的预测的熵值的比较。右边的图以相对较高的置信度（低熵）预测了马的图像，而左边的分类器无法真正区分（高熵）它是马、牛还是长颈鹿。

Answer 7

在压缩和信息理论方面，源的熵是来自源的符号可以传达的平均信息量（以位为单位）。通俗地说，一个符号越不可能，它的出现带来的惊喜就越多。

如果您的来源有两个符号，例如A和B，并且它们的可能性相同，则每个符号传达相同数量的信息（一位）。具有四个等可能符号的源每个符号传送两个比特。

举一个更有趣的例子，如果您的来源有三个符号 、A、B和C，其中前两个的可能性是第三个的两倍，那么第三个更令人惊讶，但可能性也更小。该源的净熵为 1.52，计算如下。

您将熵计算为“平均惊喜”，其中每个符号的“惊喜”是其概率乘以概率的负二元对数：

                            binary
symbol  weight  probability   log    surprise
  A        2        0.4      -1.32    0.53
  B        2        0.4      -1.32    0.53
  C        1        0.2      -2.32    0.46
total      5        1.0               1.52

使用二进制日志的负数（当然）是因为 0 和 1（不包括）之间的值的日志是负数。