问题标签 [information-theory]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
5712 浏览

matlab - MATLAB矩阵的互信息

我有一个方阵,它表示数据集中共现的频率计数。换句话说,行代表特征 1 的所有可能观察值,列是特征 2 的可能观察值。单元格 (x, y) 中的数字是特征 1 同时被观察为 x 的次数特征 2 是 y。

我想计算这个矩阵中包含的互信息。MATLAB 有一个内置information函数,但它需要 2 个参数,一个用于 x,一个用于 y。我将如何操纵这个矩阵来获得它期望的参数?

或者,我编写了自己的互信息函数,该函数采用矩阵,但我不确定它的准确性。看起来对吗?

0 投票
2 回答
153 浏览

information-theory - 最大化存储信息(熵?)

所以我不确定这个问题是属于这里还是数学溢出。无论如何,我的问题是关于信息论的。

假设我有一个 16 位字。该数字中有 65,536 个独特的 1 和 0 配置。这些配置中的每一个代表什么并不重要,因为取决于您的符号(2 的补码与有符号幅度等),相同的配置可能意味着不同的东西。

我想知道是否有任何技术可以存储比 16 位字更多的信息?

我最初的想法就像奇偶校验或其他东西,但后来我意识到这已经由配置决定......即其中没有编码额外的信息。我开始怀疑是否不存在这样的事情。

编辑例如,假设一些神奇的计算机(在这里思考量子或其他东西)可以理解 0,1,a。那么显然我们有 3^16 个配置,现在可以存储超过数字 [0 - 65,536] 的数量。为了在比特流中编码额外信息,您是否可以使用 16 位字的任何其他属性?

EDIT2我真的很难用语言表达出来。现在,当我在计算机中查看一个 16 位字时,该属性向我传达了单个 1 和 0 的相对顺序的信息。是否有另一种查看 16 位字的属性或方式,它允许超过 2^16 个独特的“配置”?(请注意,它不再是配置,而是 2^16 xxxx,其中 xxxx 是描述该属性实例的名词)。我唯一能真正想到的是,如果我们查看 1 到 0 转换的数量或其他东西,而不是每个位实际上是 1 还是 0?现在转换不会产生超过 2^16 个组合,因为它最终完全取决于 1 和 0 的配置。我正在寻找从 1 和 0 的配置派生的属性以及其他导致超过2^16 的属性。有没有人知道如果它确实存在会被称为什么?


EDIT3好的,我明白了。我的问题归结为:我们如何证明一个词中的 1 和 0 的配置完全定义了它?IE 我们如何证明除了位图之外不需要其他信息来显示两个 16 位字之间的相等性?


最终编辑

我有一个例子......如果不是查看 1 和 0 的存在,而是查看位之间的转换,我们可以存储 2^16 个字母字符。如果左边的位相同,则将其视为 1,如果转换,则将其视为 0。使用 16 位字作为循环链表类型结构,其中每个链接表示 0/1,我们基本上是 16 位位之间的转换字。这是我正在寻找的一个确切的例子,但结果是 2^16,没有比这更好的了。我相信你不能做得更好并且正在标记正确的答案=(

0 投票
3 回答
8450 浏览

graph - 如何计算图的熵?

我有一组随机生成的形式图,我想计算每个图的熵。同一个问题,不同的话:我有几个网络,想计算每个网络的信息内容。

以下是包含图熵正式定义的两个来源:
http ://www.cs.washington.edu/homes/anuprao/pubs/CSE533Autumn2010/lecture4.pdf (PDF) http://arxiv.org/abs/0711.4175v1

我正在寻找的代码将图形作为输入(作为边列表或邻接矩阵)并输出一些位或其他信息内容的度量。

因为我在任何地方都找不到它的实现,所以我打算根据正式定义从头开始编写代码。如果有人已经解决了这个问题并愿意分享代码,将不胜感激。

0 投票
1 回答
6075 浏览

python - Python中的连续互信息

[Frontmatter] (如果你只是想问这个问题,请跳过这个)

我目前正在研究使用Shannon-Weaver 互信息标准化冗余来测量按特征组织的离散和连续特征值袋之间的信息屏蔽程度。使用这种方法,我的目标是构建一个看起来与ID3非常相似的算法,但不是使用香农熵,该算法将寻求(作为循环约束)最大化或最小化单个特征和基于完整输入特征空间的特征集合之间的共享信息,当(且仅当)新特征增加或分别减少互信息。实际上,这将 ID3 的决策算法移动到对空间中,将集成方法与这两种方法的所有预期时间和空间复杂性结合在一起。

[/前线]


关于这个问题:我正在尝试让一个使用SciPy在 Python 中工作的连续积分器。因为我正在比较离散变量和连续变量,所以我当前对特征-特征对的每次比较的策略如下:

  • 离散特征与离散特征:使用互信息的离散形式。这导致概率的双重求和,我的代码可以毫无问题地处理。

  • 所有其他情况(离散与连续、逆和连续与连续):使用连续形式,使用高斯估计器平滑概率密度函数

对于后一种情况,我可以执行某种离散化,但由于我的输入数据集本质上不是线性的,这可能是不必要的复杂。


这是显着的代码:

请注意,为了防止 SciPy 的gaussian_kde类出现奇点,故意过度计算一个点。随着 x 和 y 的大小相互接近无穷大,这种影响变得可以忽略不计。


我目前的障碍是试图在 SciPy 中针对高斯核密度估计进行多重集成。我一直在尝试使用 SciPy 的dblquad来执行集成,但在后一种情况下,我收到了令人震惊的以下消息。

当我设置numpy.seterr ( all='ignore' )

警告:检测到舍入错误的发生,这会阻止达到请求的容差。错误可能被低估了。

当我将其设置为'call'使用错误处理程序时:

浮点错误(下溢),带有标志 4

浮点错误(无效值),标志为 8

很容易弄清楚发生了什么,对吧?好吧,差不多:IEEE 754-2008和 SciPy 只告诉我这里发生了什么,而不是为什么如何解决它


结果:minfo_xy通常解析为nan; 在执行 Float64 数学运算时,其采样不足以防止信息丢失或无效。

使用 SciPy 时是否有针对此问题的一般解决方法?

更好的是:如果 Python 有一个稳健的、固定的连续互信息实现,其接口采用两个浮点值集合或对的合并集合,它将解决这个完整的问题。如果您知道存在一个,请链接它。

先感谢您。


编辑:这解决了nan上面示例中的传播问题:

然而,舍入校正的问题仍然存在,对于更强大的实现的要求也是如此。任何一个领域的任何帮助都将不胜感激。

0 投票
3 回答
152 浏览

assembly - 子程序推理

是否有任何论文描述了从编译程序中推断子程序的任何算法/技术?换句话说:是否有一种算法可以找到在程序中出现多次的代码块?这些块可以重新排序指令(当然没有程序行为改变),以便更有可能找到匹配项。

这个过程可以看作与编译器为避免调用而完成的子例程内联相反,但会增加二进制大小。

在我看来,这是一个非常困难的理论问题。

0 投票
1 回答
72 浏览

algorithm - 生成带有熵参数的伪随机流

如何生成长度为n的二进制结果流,其中 0 和 1 的数量相等,但成对结果的频率有偏差,即给定交替率k ( freq(01) + freq(10) ) / ( freq(00) + freq(11) ) = k

0 投票
2 回答
260 浏览

probability - 概率不均匀时的马尔可夫熵

我一直在考虑马尔可夫方程的信息熵:

H = -SUM(p(i)lg(p(i)),其中 lg 是以 2 为底的对数。

这假设所有选择 i 具有相等的概率。但是,如果给定的一组选择中的概率不相等怎么办?例如,假设 StackExchange 有 20 个站点,并且用户访问除 StackOverflow 之外的任何 StackExchange 站点的概率为 p(i)。但是,用户访问 StackExchange 的概率是 p(i) 的 5 倍。

马尔可夫方程在这种情况下不适用吗?还是有我不知道的高级马尔可夫变体?

0 投票
1 回答
1289 浏览

matlab - 香农通道容量和熵的实现问题

将相空间划分为多个Alpha分区后,旨在找出该分区的好坏程度。从这个角度来看,我们需要找出源熵。现在,我用谷歌搜索了很多,但找不到源熵是什么。谁能解释一下:

  • 香农熵与源熵有何不同,源熵如何实现?

  • 如何计算通道容量?下面是计算数据 x 的香农熵的代码。如果修改以下代码以计算通道容量,我将有义务。

  • 用较少的技术术语来说,Kolgomorov 熵和香农熵有什么区别?理解 Kolgomorov 复杂度返回的复杂度数的重要性/含义令人困惑。
0 投票
1 回答
420 浏览

text-mining - 不常用词的相互信息

在使用大约 3000 字的大文档计算两个词之间的 MI 时,当我计算文档中第一个词重复次数不多的概率时,第二个词的概率很低,并且相同;这个低值会影响联合概率 =p(x) * P(y)导致互信息的值为零或 NaN。我怎样才能避免这种情况?

0 投票
3 回答
1879 浏览

encoding - 决策树中的香农熵测度

为什么在决策树分支中使用香农熵度量?

熵(S) = - p(+)log( p(+) ) - p(-)log( p(-) )

我知道这是对否的衡量标准。编码信息所需的比特数;分布越均匀,熵越大。但我不明白为什么它如此频繁地应用于创建决策树(选择分支点)。