标签: information-theory

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

作为我正在使用的AI应用程序的一部分,我希望能够根据其单调性(也就是其"排序性")对整数的候选数组进行评级.目前,我正在使用一种计算最长排序运行的启发式算法,然后将其除以数组的长度:

public double monotonicity(int[] array) {
    if (array.length == 0) return 1d;

    int longestRun = longestSortedRun(array);
    return (double) longestRun / (double) array.length;
}

public int longestSortedRun(int[] array) {

    if (array.length == 0) return 0;

    int longestRun = 1;
    int currentRun = 1;

    for (int i = 1; i < array.length; i++) {
        if (array[i] >= array[i - 1]) {
            currentRun++;
        } else {
            currentRun = 1;
        }

        if (currentRun > longestRun) longestRun = currentRun;
    }

    return …

从我的算法教科书:

一年一度的县赛马比赛将引进三羽从未参加过比赛的纯种马.很兴奋,你研究他们过去的200场比赛并总结这些比赛的概率分布超过四个结果:第一("第一名"),第二名,第三名和其他.

                       Outcome     Aurora   Whirlwind    Phantasm
                        first        0.15      0.30          0.20

                        second       0.10      0.05          0.30

                        third        0.70      0.25          0.30

                        other        0.05      0.40          0.20

哪匹马最可预测？这个问题的一个定量方法是研究可压缩性.将每匹马的历史记录为200个值(第一,第二,第三,其他)的字符串.然后可以使用霍夫曼算法计算编码这些跟踪记录串所需的总位数.这对于Aurora来说是290位,对于Whirlwind来说是380位,对于Phantasm来说是420位(检查它!).Aurora具有最短的编码,因此在强烈意义上是最可预测的.

他们是如何为Phantasm获得420的？我一直得到400字节,如下所示:

首先结合,其他= 0.4,结合第二,第三= 0.6.最终以2位编码每个位置.

有没有我对霍夫曼编码算法误解的东西？

教科书可在此处获得:http://www.cs.berkeley.edu/~vazirani/algorithms.html(第156页).

我在解释熵包中的mi.plugin()(或mi.empirical())函数的结果时遇到问题.据我所知,MI = 0告诉您,您要比较的两个变量是完全独立的; 随着MI的增加,两个变量之间的关联越来越不随机.

那么,为什么在R中运行以下命令(使用{entropy}包)时,我得到的值为0 :

mi.plugin( rbind( c(1, 2, 3), c(1, 2, 3) ) )

当我比较两个完全相同的向量时？

我认为我的困惑是基于我的理论误解,有人可以告诉我哪里出错了吗？

提前致谢.

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

这是我的问题.假设我的序列为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吗？

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

我知道维基百科和麦凯的信息理论,推理和学习算法(它是否适合作为教科书？).寻求以香农的熵开始并通过条件熵和相互信息的教科书......任何想法？如果您正在大学学习这门课程,那么使用哪本课本？

谢谢.

让我澄清一点,我不是在谈论能够压缩任何给定源材料的算法意义上的完美压缩,我意识到这是不可能的.我想要得到的是一种能够将任何源位串编码到其绝对最大压缩状态的算法,由其的Shannon熵确定.

我相信我听说过一些关于霍夫曼编码在某种意义上最优的东西,所以我相信这个加密方案可能是基于这个,但这是我的问题:

考虑位串:a ="101010101010",b ="110100011010".

使用简单的Shannon熵,当我们将位串简单地视为0和1的符号时,这些位串应该具有完全相同的熵,但是这种方法是有缺陷的,因为我们可以直观地看到位串a具有比位串b更少的熵,因为它只是一个重复10的模式.考虑到这一点,我们可以通过计算复合符号00,10,01和11的香农熵来更好地了解源的实际熵.

这只是我的理解,我可能完全偏离基础,但从我的理解,对于一个遍历源为真正随机,对于长度为n的遍历源.所有n长度符号组的统计概率必须具有相同的可能性.

我想比标题中的问题更具体,我有三个主要问题:

使用单个位作为符号的霍夫曼编码是否会像最佳一样压缩位串,即使我们在2位符号级别分析字符串时会出现明显的模式？如果没有,可以通过循环通过霍夫曼编码的不同"级别"(抱歉,如果我在这里屠宰术语)来最佳地压缩源,直到找到最佳压缩率？在某些情况下,可以通过霍夫曼编码的不同"轮次"进一步提高压缩率吗？(首先使用5位长的符号进行霍夫曼编码,然后对4位长的符号进行霍夫曼编码？huff_4bits(huff_5bits(bitstring)))

众所周知,GZIP或DEFLATE(或任何压缩机制)有时会增加文件大小.是否可以增加文件的最大值(百分比或常量)？它是什么？

如果一个文件是X字节,并且我要gzip它,我需要提前预算文件空间 - 最糟糕的情况是什么？

更新:有两个开销:GZIP添加一个标头,通常是18个字节,但基本上是任意长的.DEFLATE怎么样？这可以通过乘法因子扩展内容,我不知道.有谁知道它是什么？

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

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

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

function [mutualinfo] = mutualInformation(counts)

  total = sum(counts(:));
  pX = sum(counts, 1) ./ total;
  pY = sum(counts) ./ total;
  pXY = counts ./ total;

  [h, w] = size(counts);

  mutualinfo = 0;

  for row = 1:h
    for col = 1:w
      mutualinfo = mutualinfo + pXY(row, col) * log(pXY(row, col) / (pX(row)*pY(col)));
    end;
  end;

end

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

这个过程可以看作是子程序内联的反面,它由编译器完成,以避免调用,但增加了二进制大小.

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

我有一个大小为MxN的数组,我喜欢计算每一行的熵值.最快的方法是什么？