问题标签 [information-theory]

任何人都可以推荐一本关于整数通用代码，尤其是斐波那契代码（在http://en.wikipedia.org/wiki/Fibonacci_code的意义上）的好书/论文/网站/背景读物吗？谢谢！

编辑：感谢到目前为止的答案和有用的链接！很抱歉，如果我没有完全清楚地说明自己：我不是在询问生成或计算斐波那契数的代码（如编写程序），而是询问使用的特定代码（如编码或压缩数据）斐波那契数列。

我最近在我的大学开设了一门数据压缩课程。然而，我发现“熵”这个词在计算机科学中的使用相当含糊。据我所知，它粗略地转化为系统或结构的“随机性”。

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

根据香农的源编码定理，我们知道压缩字符串的熵受原始字符串熵的限制，如下所示：

其中 H(X) 是源字符串的熵，N 是源字符串的长度，L 是压缩字符串的预期长度。

这必然意味着无损压缩是有限度的。

我想知道的是：

• 我们可以直接将熵与一些预期的压缩比联系起来吗？

• 我们可以使用熵来找到压缩比的上限吗？

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

这是我的问题。假设我有一个 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？

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

给定来自某个来源的序列 pf 数字N₁ , N₂ , N₃...，而不是 PRNG，而是说传感器或某种类型的记录数据，假设这样处理它是否安全

Nn/ B = Q_n Rem Mn

会导致序列Q的熵比序列少M吗？

注意：假设B两者Q和M具有相同大小的范围。

这与观察到大多数现实世界的数据集，无论来源或来源，都具有对数分布有关；以 1 开头的数字比以 9 开​​头的数字更常见。但这对低阶部分几乎没有说明。

用一种有趣的方式来测试这个（并通过让他的计算机陷入困境来惹恼你的系统管理员）在 bash 中运行它：

并获取文件大小第一位的直方图。

我有一个信息论问题，关于如何证明（或至少提供统计证据）拍卖网站没有向其用户提供先令。

我们最近推出了一个按出价付费的拍卖网站。这是一种新型的拍卖方式，用户付费竞拍定时拍卖。每次出价都会提高价格并增加拍卖时间。时间用完时，最后一个投标人可以购买该物品。

问题是用户怀疑我们可能在欺骗他们。我没有这样的意图，因为用户的信任对我来说至关重要。但是，该模型可以由其他不道德的网站实施，并且可以直接欺骗投标人。我需要采取措施向我们的用户表明我们是合法的。

我致力于诚实经营。挑战在于如何向世界证明这一点？任何方法都需要与保护用户隐私相平衡。

我的一些想法是：

• 显示每个用户的 IP 地址

• 向收到商品的获奖者征求推荐信。让他们邮寄他们的照片以及他们的商品和当地报纸最近的封面副本。

• 显示有关每个用户的一些广泛信息，例如所在州和国家/地区

我正在寻找任何建议。

更新

一些很棒的建议。至今：

• 提供每个用户的行为信息：

  • 加入时
  • 哪些拍卖参与了
  • 拍卖统计数据 - 出价，成本

• 不发布个人身份信息。没有 IP 地址，因为没有获胜的人可以对获胜者进行报复。

• 讨论和解决问题的公共论坛

• 向用户征求推荐，以表明人们确实赢了并收到了产品。

  • 我们如何在证明中表明它不是我们“发明”的？我正在考虑也许要求在最近的当地报纸上附上一张照片。这将很难大规模伪造，以及如何通过时间和地点分配获胜者。

您认为显示用户所在的州和国家/地区是否可以，或者这将是太多的个人信息？

我遇到了这个问题；

“一种无损压缩算法，号称保证让一些文件变小，不让文件变大。
是这样的吗？

a) 不可能

b) 可能，但可能运行不确定的时间，

c) 压缩系数为 2 或更低时可能，

d) 任何压缩系数都可能吗？”

我倾向于（a），但无法给出一个可靠的解释。（我会列出一个朋友的想法，我想出一个可能的答案）

如果我想发送一个 d 位数据包并添加另一个 r 位用于纠错码 (d>r)
，我最多可以找到并纠正多少个错误？

设想

我正在尝试对 Java GUI 应用程序中的数据集实施监督学习。用户将获得要检查的项目或“报告”列表，并将根据一组可用标签对其进行标记。一旦监督学习完成，标记的实例将被提供给学习算法。这将尝试根据用户想要查看它们的可能性对其余项目进行排序。

为了充分利用用户的时间，我想预先选择将提供有关整个报告集合的最多信息的报告，并让用户标记它们。据我了解，要计算这一点，有必要找到每个报告的所有互信息值的总和，并按该值对它们进行排序。然后，来自监督学习的标记报告将用于形成贝叶斯网络，以找到每个剩余报告的二进制值的概率。

例子

在这里，一个人为的例子可能有助于解释，并且当我无疑使用了错误的术语时可能会消除混乱:-) 考虑一个应用程序向用户显示新闻故事的例子。它根据显示的用户偏好选择首先显示哪些新闻报道。具有相关性的新闻故事的特征country of origin是category或date。因此，如果用户将来自苏格兰的单个新闻故事标记为有趣，它会告诉机器学习器，来自苏格兰的其他新闻故事对用户感兴趣的机会增加。类似于 Sport 等类别或 2004 年 12 月 12 日等日期。

可以通过为所有新闻故事选择任何顺序（例如，按类别、按日期）或随机排序它们，然后在用户进行时计算偏好来计算这种偏好。我想做的是让用户查看少量特定新闻故事并说出他们是否对它们感兴趣（监督学习部分），从而在该排序上获得一种“领先优势”。要选择向用户展示哪些故事，我必须考虑整个故事集合。这就是互信息的用武之地。对于每个故事，我想知道当它被用户分类时，它可以告诉我多少关于所有其他故事的信息。例如，如果有大量来自苏格兰的故事，我想让用户（至少）对其中一个进行分类。其他相关特征（例如类别或日期）也类似。目标是找到在分类时提供关于其他报告的最多信息的报告示例。

问题

因为我的数学有点生疏，而且我是机器学习的新手，所以在将互信息的定义转换为 Java 实现时遇到了一些麻烦。维基百科将互信息的方程式描述为：

但是，我不确定这是否真的可以在没有分类的情况下使用，并且学习算法还没有计算任何东西。

在我的示例中，假设我有大量新的、未标记的此类实例：

在我的具体场景中，字段/特征之间的相关性是基于精确匹配的，因此，例如，一天和 10 年的日期差异在它们的不等式上是等效的。

The factors for correlation (e.g. is date more correlating than category?) are not necessarily equal, but they can be predefined and constant. Does this mean that the result of the function p(x,y) is the predefined value, or am I mixing up terms?

The Question (finally)

How can I go about implementing the mutual information calculation given this (fake) example of news stories? Libraries, javadoc, code examples etc. are all welcome information. Also, if this approach is fundamentally flawed, explaining why that is the case would be just as valuable an answer.

PS. I am aware of libraries such as Weka and Apache Mahout, so just mentioning them is not really useful for me. I'm still searching through documentation and examples for both these libraries looking for stuff on Mutual Information specifically. What would really help me is pointing to resources (code examples, javadoc) where these libraries help with mutual information.

我有这个作业：找到任何给定字母表中符号的代码字。它说我必须对三个符号组使用二进制霍夫曼。这到底是什么意思？我是否在 [字母]^3 上使用常规霍夫曼？如果是这样，那么我该如何区分一组中的 3 个符号？