问题标签 [information-theory]

编辑：哇，很多很棒的回应。是的，我使用它作为适应度函数来判断遗传算法执行的排序的质量。因此，评估成本很重要（即，它必须快速，最好是O(n)。）

作为我正在玩弄的 AI 应用程序的一部分，我希望能够根据其单调性（也称为“排序性”）对候选整数数组进行评分。目前，我正在使用一种计算最长排序运行的启发式算法，然后将其除以数组的长度：

这是一个好的开始，但它没有考虑到排序子序列可能存在“团块”的可能性。例如：

这个数组被分成三个排序的子序列。我的算法将它评为只有 40% 的排序，但直观地说，它应该得到比这更高的分数。这种事情有标准算法吗？

这更像是一个计算机科学/信息论问题，而不是一个简单的编程问题，所以如果有人知道一个更好的网站来发布这个，请告诉我。

假设我有一条 N 位数据，它将在 M 条消息中冗余发送，其中至少有 M-1 条消息将被成功接收。我对以每条消息更少的位数对 N 位数据进行编码的不同方法感兴趣。（这类似于RAID，但级别要小得多，其中 N = 8 或 16 或 32）

示例：假设 N = 16 和 M = 4。那么我可以使用以下算法：

如果我能保证 4 条消息中的 3 条能够通过，那么每个组中至少有一条消息能够通过。因此，我可以用 9 位或更少的位来完成这项工作，可能有一种方法可以用更少的总位来做到这一点，但我不确定如何。

是否有一些简单的编码/解码算法来做这种事情？这个问题有名字吗？（如果我知道它叫什么，我可以谷歌它！）

注意：在我的特定情况下，消息要么正确到达，要么根本没有到达（没有消息到达时有错误）。

（编辑：将第二部分移至单独的问题）

信息论在存在编码和解码的地方发挥作用。例如：压缩（多媒体）、密码学。

在信息论中，我们遇到诸如“熵”、“自我信息”、“互信息”之类的术语，整个主题都基于这些术语。这听起来不过是抽象的。坦率地说，它们没有任何意义。

是否有任何书籍/材料/解释（如果可以）以实用的方式解释这些事情？

编辑：

约翰·罗宾逊·皮尔斯 (John Robinson Pierce )的《信息论导论：符号、信号和噪声》这本书以我想要的方式（实际上）解释它。它太好了。我开始阅读它。

我知道维基百科和麦凯的信息论、推理和学习算法（它适合作为教科书吗？）。一本从香农熵开始，经过条件熵和互信息的教科书……有什么想法吗？如果你在你的大学学习这样的课程，使用哪本教科书？

谢谢。

我有一个我认为涉及信息论领域的“条件熵”的问题。我试图绕过它，但可以使用一些帮助。考虑一个我们有四个房子的例子。一屋八人，二屋四人，三屋二人，四屋二人。所以，四间房子和十六个人。如果我只是随机选择其中一个人，那么该选择是从 16 个人中选择的，为该选择产生 4 位的信息熵。

但是现在考虑一个两步选择，首先我随机选择一所房子，然后我在选定的房子里选择一个人。所以第一步，从四个可用的房子中挑选一个房子，会产生两个信息熵。但是现在，在我选择第一所房子的 25% 的时间里，第二步在从第一所房子的八个人中选择一个人时又增加了三位。在另外 25% 的情况下，我只需要另外两个位来从住在第二所房子的四个人中选择一个人。最后，在一半的情况下，我只需要一点点就可以从居住在第三宫或第四宫的一对中挑选一个人。

不知何故，在我看来，两步法的加权平均位数应该产生与单步法所需的相同的四位总数。但我无法将这些数字加起来，所以很明显，数学比我考虑的要多。我期待您应该能够简单地将概率相加，如下所示：

但这会产生 3.75 位的结果，而不是我期望的 4 位。这是我用来评估这个的一些python。

所以，我的数字中缺少一些东西。谁能指出我正确的方向？

给定一个无限的随机 0 和 1 流，它来自一个有偏的（例如，1 比 0 更常见的已知因子），但在其他方面是理想的随机数生成器，我想将它转换成一个（更短的）无限流，就像理想但不偏不倚。

查找熵的定义会发现这张图显示了理论上我应该能够从每一位输入中获得多少位输出。

问题：是否有任何实用的方法来实际实现几乎理想高效的转换器？

我很抱歉，因为我不知道这更多的是属于mathoverflow的数学问题，还是属于这里的计算机科学问题。

也就是说，我相信我理解数据、信息和知识之间的根本区别。我的理解是信息既承载数据又承载意义。我不清楚的一件事是信息是否是数据。信息被认为是一种特殊的数据，还是完全不同的东西？

我知道来自正确使用的一次性密码的密文绝对不会显示有关加密消息的数据。

这是否意味着无法将使用一次性密码加密的消息与完全随机的噪声区分开来？或者是否有某种理论上的方法可以确定存在消息，即使您对此一无所知？

希望有人能给我一些关于这个熵问题的指示。

假设 X 是从均匀整数分布 0-32（含）中随机选择的。

我计算熵，H(X) = 32 位，因为每个 Xi 具有相同的发生概率。

现在，假设执行以下伪代码。

int r = rand(0,1); // 一个随机整数 0 或 1

r = r * 33 + X;

我将如何计算两个变量 r 和 X 之间的互信息？

互信息定义为 I(X; Y) = H(X) - H(X|Y) 但我真的不明白如何将条件熵 H(X|Y) 应用于这个问题。

谢谢

我正在学习信息论，但有一件事我似乎无法解决。

我知道给定一个线性代码 C 和一个生成矩阵 MI 可以计算出 C 的所有可能的代码字。

但是我不明白：

• 什么是奇偶校验矩阵http://en.wikipedia.org/wiki/Parity-check_matrix
• 如何从生成矩阵制作奇偶校验矩阵

我真的很感激任何指示！

谢谢！