8

我对熵公式的理解是它用于计算表示某些数据所需的最小位数。它通常在定义时措辞不同，但之前的理解是我直到现在所依赖的。

这是我的问题。假设我有一个 100 '1' 后跟 100 '0' = 200 位的序列。字母表是{0,1}，熵的底是2。符号“0”的概率是0.5，“1”是0.5。所以熵是 1 或 1 位来表示 1 位。

但是，您可以使用类似 100 / 1 / 100 / 0 的方式对其进行游程长度编码，其中输出的位数后跟位。似乎我的表示小于数据。特别是如果您将 100 增加到更大的数字。

我目前正在使用：http ://en.wikipedia.org/wiki/Information_entropy作为参考。我哪里做错了？是分配给符号的概率吗？我不认为这是错的。还是我把压缩和熵之间的联系弄错了？还要别的吗？

谢谢。

编辑

我的后续回答是：您会将熵公式应用于消息的特定实例以尝试找出其信息内容吗？接受消息“aaab”并说熵是~0.811是否有效。如果是，那么 1...10....0 的熵是多少，其中 1 和 0 使用熵公式重复 n 次。答案是1？

是的，我了解您正在创建输入符号的随机变量，并根据您的消息猜测概率质量函数。我要确认的是熵公式没有考虑消息中符号的位置。

4

4 回答 4

7

还是我把压缩和熵之间的联系弄错了？

你非常接近，但最后一个问题是错误在哪里。如果您能够将某些内容压缩为小于其原始表示的形式，则意味着原始表示至少具有一些冗余。消息中的每一位实际上都没有传达一点信息。

因为冗余数据对消息的信息内容没有贡献，所以它也不会增加它的熵。例如，想象一个仅返回值“0”的“随机位生成器”。这根本不传达任何信息！（实际上，它传达了不确定数量的信息，因为任何仅包含一种符号的二进制消息都需要在熵公式中除以零。）

相比之下，如果您模拟大量随机抛硬币，则很难大幅减小此消息的大小。每一位将贡献接近 1 位的熵。

当您压缩数据时，您会提取冗余。作为交换，您必须设计一个知道如何压缩和解压缩这些数据的方案，从而付出一次性的熵代价；这本身需要一些信息。

但是，您可以使用类似 100 / 1 / 100 / 0 的方式对其进行游程长度编码，其中输出的位数后跟位。似乎我的表示小于数据。特别是如果您将 100 增加到更大的数字。

总而言之，您可以设计一种方案来使数据的编码小于原始数据，这一事实告诉您一些重要的事情。也就是说，它说您的原始数据包含的信息很少。

进一步阅读

要对此进行更彻底的处理，包括如何通过一些示例准确计算任意数字序列的熵，请查看这个简短的白皮书。

于 2009-03-16T16:37:49.037 回答
6

看看Kolmogorov 复杂度

在不丢失信息的情况下，可以将字符串压缩成的最小位数。这是相对于由通用图灵机给出的固定但通用的解压缩方案定义的。

在您的特定情况下，不要将自己局限于字母 {0,1}。对于您的示例，请使用 {0...0, 1...1} （数百个 0 和数百个 1）

于 2009-03-16T16:25:36.083 回答
4

您的编码在此示例中有效，但可以设想一个同样有效的情况：010101010101... 将被编码为 1 / 0 / 1 / 1 / ...

熵是针对可以在给定字母表中构建的所有可能消息进行测量的，而不仅仅是病态示例！

于 2009-03-16T16:49:09.990 回答
4

John Feminella 说得对，但我认为还有更多话要说。

香农熵是基于概率的，而概率总是在旁观者的眼中。

您说 1 和 0 的可能性相同（0.5）。如果是这样，那么 100 个 1 后跟 100 个 0 的字符串的概率为 0.5^200，其中 -log(base 2) 为 200 位，如您所料。但是，该字符串的熵（用香农术语）是它的信息内容乘以它的概率，或者 200 * 0.5^200，仍然是一个非常小的数字。

这很重要，因为如果您使用运行长度编码来压缩字符串，在这个字符串的情况下，它会得到一个小的长度，但是对所有 2^200 个字符串进行平均，它就不会做得很好。运气好的话，平均会达到 200 左右，但不会更少。

另一方面，如果您查看原始字符串并说它是如此惊人以至于生成它的人可能会生成更多类似它，那么您实际上是在说它的概率大于 0.5^200，所以您正在制作一个不同的关于字符串生成器的原始概率结构的假设，即它的熵低于 200 位。

就个人而言，我发现这个主题非常有趣，尤其是当您查看 Kolmogorov（算法）信息时。在这种情况下，您将字符串的信息内容定义为可以生成它的最小程序的长度。这导致了对软件工程和语言设计的各种见解。

我希望这会有所帮助，并感谢您的提问。

于 2009-03-21T01:33:10.510 回答