Re: [TopLanguage] 说到解题的思路

[pongba]

2008/5/22 Yong Yuan <yyc...@gmail.com>:

今天看到David MacKay的文章：http://users.aims.ac.za/~mackay/sorting/sorting.html。里面提到利用信息论，称12球的问题可以系统地解决，不需要试错。学过信息论的大大们可能觉得火星了。我对信息论一知半解，所以看到这套思路觉得非常新鲜。有种用惯罗马计数法的人突然明白阿拉伯计数法，或者用惯加法的人突然领略乘法时的惊喜。文章里提到的教材Information Theory, Inference, and Learning Algorithms有详尽的讨论，而且作者还免费开放下载：http://users.aims.ac.za/~mackay/itila/book.html。

赞！这就是称为"本质"的东西。越是接近本质的理论，往往越是简洁，越具有普遍性，能解决的问题也越多。
上次的一道几何证明题，hayate提到，虽然可以用初等方法解，但是如果用解析几何，就可以非常朴素的解出来，虽然计算起来麻烦一点。很多需要用到初等方法中的奇技淫巧的问题，用上触摸到问题真正本质的手法，就没什么神秘了。
信息论真是个好理论啊~

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[Googol Lee]

我看过一个用向量法解中学初等几何等边问题的方法，一时想不起在哪里看到的了……

2008/5/22 pongba <pon...@gmail.com>:

--
新的理论从少数人的主张到一统天下，并不是因为这个理论说服了别人抛弃旧观点，而是因为一代人的逝去。

My blog: http://googollee.blog.163.com

[星染流云]

嗯，我以前在google黑板报上看到吴军先生推荐过另外一本书，就是下面这本。按他的话说，作者"科弗教授是当今最权威的信息论专家"：

信息论基础
http://www.china-pub.com/25215

这是他的那篇文章：
http://www.googlechinablog.com/2006/05/blog-post_25.html

刚才惊喜地发现，今年已经出了这书的第二版翻译了：

信息论基础(原书第2版)
http://www.china-pub.com/36979

On 5月22日, 下午3时34分, "Yong Yuan" <yycs...@gmail.com> wrote:
> 今天看到David MacKay的文章：http://users.aims.ac.za/~mackay/sorting/sorting.html。里面提到利用信息论，称12球的问题可以系统地解决，不需要试错。学过信息论的大大们可能觉得火星了。我对信息论一知半解，所以看到这套思路觉得非常新鲜。有种-用惯罗马计数法的人突然明白阿拉伯计数法，或者用惯加法的人突然领略乘法时的惊喜。文章里提到的教材Information

[星染流云]

信息论、推理与学习算法（翻译版）
Information Theory,Inference and Learning Algorithms
http://www.china-pub.com/415868

[dailiangren]

我觉得纵然采用信息论依然无法给出具体的方法，但是信息论可以给具体方法的提出给出一个方向上的指导。

 

 

---

dailiangren

2008-05-22

---

发件人： pongba

发送时间： 2008-05-22 15:58:54

收件人： pon...@googlegroups.com

抄送：

主题： [TopLanguage] Re: 说到解题的思路

[dailiangren]

还有说到上次的那个几何习题，说不准就是我们日常生活中司空见惯的一个现象的变化了的形式。

我觉得，真正思考出问题的本质，才能真正的启迪人的思维。我觉得如果中国的老师都能这样去做，中国的教育应该会比现在进步不少。

 

---

dailiangren

2008-05-22

---

发件人： pongba

发送时间： 2008-05-22 15:58:54

收件人： pon...@googlegroups.com

抄送：

主题： [TopLanguage] Re: 说到解题的思路

 

[hayate]

说到信息论 我想起一个问题

说有5个整数，最多比较7次，就排好序

具体的比较步骤不记得了，比较精巧。

但是这里为什么是7次呢，7次是不是下界呢？

 

5个整数，产生的全排列有5!=120种，从信息论的角度，信息量就是log_2{120} = 6.90689059560852 bit

而两个数比较一次，显然可以产生1bit的信息量，所以7次比较几乎就是极限了。

 

这个解释不是我的，我当时就感叹，有时理论的魅力不在于是否能找到具体的解，而是一开始就知道问题有没有解，解在哪个范围。

2008/5/22 pongba <pon...@gmail.com>:

[lbaby]

呵呵，听起来很好玩

On May 23, 3:08 pm, hayate <hayate...@gmail.com> wrote:
> 说到信息论 我想起一个问题
> 说有5个整数，最多比较7次，就排好序
> 具体的比较步骤不记得了，比较精巧。
> 但是这里为什么是7次呢，7次是不是下界呢？
>
> 5个整数，产生的全排列有5!=120种，从信息论的角度，信息量就是log_2{120} = 6.90689059560852 bit
> 而两个数比较一次，显然可以产生1bit的信息量，所以7次比较几乎就是极限了。
>
> 这个解释不是我的，我当时就感叹，有时理论的魅力不在于是否能找到具体的解，而是一开始就知道问题有没有解，解在哪个范围。
>
> 2008/5/22 pongba <pon...@gmail.com>:
>

> > 2008/5/22 Yong Yuan <yycs...@gmail.com>:

[pongba]

2008/5/23 hayate <haya...@gmail.com>:

5个整数，产生的全排列有5!=120种，从信息论的角度，信息量就是log_2{120} = 6.90689059560852 bit

而两个数比较一次，显然可以产生1bit的信息量，所以7次比较几乎就是极限了。

赞哪！
但信息量为什么是log_2{120} bit呢？ 是怎么定义的？暂时不想去翻那本大部头了:)hayate科普一下吧

[hayate]

我的信息论学的很差，还重修过呢，哈哈。估计学信号处理的比我知道的要多

信息论是香农老大在贝尔实验室搞出来的，他认为越不确定的事物信息量越大，也是概率越小的事物信息量越大，于是借用物理学中的熵的概念，用信息熵来刻画信息量。

就是:

信息熵

H = -

∑

pilogpi

其中p_i是概率空间每个元素的概率，总和为1，也就是信息载体不同表现的概率。

上面那个例子，所有情况的概率都是1/5！。当对数的底为2时，信息熵的单位为bit，其实也可以用其它的数为底。

至于为什么要用对数来刻画，我也不知道。但是这个bit的概念和计算机中bit的概念是一致的。1个bit位表现出0和1，信息熵正是1。

就知道这么多了

2008/5/23 pongba <pon...@gmail.com>:

[silwile]

那为什么比较一次的结果可以看成是1一个比特信息呢？
索性再科普一下吧:-)

2008/5/23 hayate <haya...@gmail.com>:

[hayate]

我是这么理解的。如果定义了偏序关系，也就是大小关系，那么两个数的关系非此即彼，含有1bit的信息量。

比较一次，对象的信息量就会减少1bit

2008/5/23 silwile <sil...@gmail.com>:

[Eric]

我来解释一下吧

我们看比特的定义就行了。 说一个抛硬币 正反各 1/2 概率。 如果信号源是这个， 所含有的信息量就是 - 1/2 * log (1/2)
+ -1/2 * log(1/2) = 1 bit

所以, 一个能生成 1/2 1/2 概率分布的信号所含的信息量就是 1bit

比较就是这样的运算, 看作 cmp(a, b) 看作是抛硬币. 每次返回的是1个 bit.

有人会质疑，因为有时候要满足序的性质, 如 a>b, b>c 则 a>c 导致第三次问 cmp(a, c) 的时候不能以 1/2 1/2 的
概率生成随机信号. 其实， 一个好的排序算法就是避免使用了 cmp(a, b) cmp(b, c) 得到 a>b b>c 后还比较一次 a,
c. 最佳的排序算法, 就是每次都能从 cmp 得到1bit 的信息

而整个数据的熵是 log_2 (n!) 每次1bit, 用一下 strinlings 近似， 很容易知道结果.

其实算法分析里面用2叉树来解释为啥一定是 nlogn 也是这个原理. 只是没有明显的用信息论的角度解释.

David MacKay 的文章底下还有精华, 是讲为啥Heap Sort 平均没有 QuickSort 快, 虽然两个都是号称 nlogn
他的解释就是 Heap Sort 每次获取的平均信息量比 Quicksort 要来的低

说到每次平均获取的信息量, 这个就牵扯到两个有趣的东西， 有兴趣的可以延伸学习一下

第一个是决策树 这个是 Machine Learning 里面比较经典的一个模型. 直观上很好理解, 假如一个人要做决策(比如给人分类, 人有
很多属性, 机器根据样本学习怎么分类), 机器判断的依据是什么呢. 机器会建立一个树状的东西, 根据这个树的分支做出判断. 就像我们人做判断一
样, 如果这个人是男的, 又很强, 我们就判定为强哥. 机器也是一样.

机器面对很多样本, 并不知道如人一样先按照男女分类. 怎么办呢. 信息论. 机器发现, 如果按照男, 女来分, 分出来的样本强哥， 挫哥；
强姐， 挫姐各在一组 （如果一组里面样本概率为1或者为0， 那么信息量为0）。 机器发现，通过这么一分， 样本的信息量下降很大。（也就是机器通
过这么分获得的比较多的信息量） 机器就认为， 呵呵， 看来我抓住关键的东西了， 按照这个关键的一分， 剩下来的东东不是那么太混乱了。 按照
这个思路， 机器就一层一层的选择属性做， 最后生成一个决策树，每个样本都变成了树的末节点。


第二个是最大熵原理， 其实这个原理就是解释快速排的。 做算法， 就好比和未知世界做斗争。 要想让一个算法表现好， 就要让未知世界无机可趁。 举
个简单的例子， 小熊分饼饼。 A 熊分，B 熊选。 那么， A 熊必须分得一样，否则B总是选大的， 到头还是A吃亏。

用这个思路，我们看我们的算法（A熊）在解决实际问题的时候， 对于未知世界 (B熊） 要保持敬畏， 要让B熊不管怎么折腾， 自己的代价都有一个确
定的上界. 也就是所谓的 max min 原则. 一个算法想要做到 max min, 又没有外界的任何信息 (不知道 B 熊会怎么选) 只能假
设每种情况都有可能。 而且是等可能。 所谓的每种情况等可能，就是说未知世界的熵最大。 这个就是通俗的最大熵的理解。 我们看 David
MacKay 的文章里面也写了， HeapSort 没有给剩余的数据均等的概率分布，所以坏情况下的复杂度要大于 QuickSort 关于最大熵
的入门，可看 Google 数学之美系列的这篇
http://www.googlechinablog.com/2006/10/blog-post.html

On May 23, 6:51 am, silwile <silw...@gmail.com> wrote:
> 那为什么比较一次的结果可以看成是1一个比特信息呢？
> 索性再科普一下吧:-)
>

> 2008/5/23 hayate <hayate...@gmail.com>:

>
> > 我的信息论学的很差，还重修过呢，哈哈。估计学信号处理的比我知道的要多
> > 信息论是香农老大在贝尔实验室搞出来的，他认为越不确定的事物信息量越大，也是概率越小的事物信息量越大，于是借用物理学中的熵的概念，用信息熵来刻画信息量。
> > 就是:
> > 信息熵

> > *H* = - ∑ *p**i*log*p**i*
> > 其中*pi*是概率空间每个元素的概率，总和为1，也就是信息载体不同表现的概率。

> > 上面那个例子，所有情况的概率都是1/5！。当对数的底为2时，信息熵的单位为bit，其实也可以用其它的数为底。
> > 至于为什么要用对数来刻画，我也不知道。但是这个bit的概念和计算机中bit的概念是一致的。1个bit位表现出0和1，信息熵正是1。
> > 就知道这么多了
> > 2008/5/23 pongba <pon...@gmail.com>:
>

> >> 2008/5/23 hayate <hayate...@gmail.com>:

[silwile]

Eric讲得太好了...

2008/5/23 Eric <xu.ma...@gmail.com>:

[hayate]

强大！！！

版主加精啊

2008/5/23 Eric <xu.ma...@gmail.com>:

[windstorm]

我已经在gmail里面加星标了，呵呵

2008/5/23 hayate <haya...@gmail.com>:

--
Yours Sincerely

Kun

[pongba]

2008/5/23 Eric <xu.ma...@gmail.com>:

我来解释一下吧

我们看比特的定义就行了。 说一个抛硬币 正反各 1/2 概率。 如果信号源是这个， 所含有的信息量就是 - 1/2 * log (1/2)
+ -1/2 * log(1/2) = 1 bit

所以, 一个能生成 1/2 1/2 概率分布的信号所含的信息量就是 1bit

那为什么信息熵偏偏定义成那样的呢？即，这个定义的本质内涵是什么。

[Eric]

可怜我回复了超级长的一段 全没了

用公理化定义吧 想想概率论是怎么定义的

信息量如果定义成概率的函数 必须有的性质是什么？ 再解一个函数方程 就得到 -log p 了

熵就是信息量的数学期望

On May 23, 9:14 am, pongba <pon...@gmail.com> wrote:
> 2008/5/23 Eric <xu.math...@gmail.com>:

[pongba]

有的有的，你是直接发到我的邮箱了，我重贴一下吧:-)

===以下===

我的这个理解不见得是"最" 本质的， 不过是我自己想出来的，手推了一下， 不难。 随口所写，语言不见得像教科书一样精当。

－－
要理解熵为啥这样定义， 我们先假设一下我们能天才般的体会到香农同学的"熵是对于不确定

性的度量"，也就是说， 我希望大家先同意， 熵是和统计有关
的。 有了这个想法，我才好用统计的方法来推导熵。 要是你觉得信息熵和统计没关系，我就没法做了 :) 我这里的思路，就是公理化信息熵的思路，和
Kolmogorov 公理化概率论的思路是一致的。以下不区分使用 （系统的信息量／熵）。 这个公理定义系统是我自己想的，不见得对哈。

首先， 我们先假设有这么几条对于（自信息量，即一个事件自己带有的信息量）的公理，这个公里体系是类比于概率公理的。 我想大家都承认的。

1。 非负性。 信息量是 >= 0 的东东, 是个非负的实数。 显然嘛，一条消息带有的信息，要不废话，要不告诉你点啥，不管怎么样，一件事情不可
能带给你负的信息量。 就像没啥东东概率是负的一样。 这个公理大家都同意吧， 同意我就往下说了 :)

2。 信息量这个东东， 和概率是联系在一起的。 假如一个人天天告诉你你早就确定的东东， 那么这个人给你的信息量为0。 概率上说就是，假如一个随
机事件发生的概率是1， 那么这个事件系统作为一个信号源， 带有的信息量＝0。  我们把这个叫规范性。 假如你非要认为概率为1的事件也能给你信息
量，你可以天天看太阳东升西落也能学知识 :)

3.   可列可加性。 独立分布事件带有的信息量可以加起来。 消息 X 和 消息 Y 如果独立的， 那么 XY 的联合信息量＝ 消息X信息量
＋ 消息Y 信息量。  我想这个没人反对的 对吧。

有了这个，我们看， 怎么定义信息量和信息熵。 我们已经说了，假设我们天才的知道信息量就是概率的函数。 我们假设这个函数叫 f(p),
我们研究研究这个函数的性质：

我们通过1 知道 f(p) >= 0 for all 0=<p<=1
通过2 我们知道  f(p) =0 if p =1
通过3 我们知道， f(p * q) = f(p) + f(q) 这个是因为独立同分布事件的概率是两个概率相乘。

我们研究这个好玩的东东， 其实就是解一个函数方程了。 大家都知道 f(x+y) = f(x) + f(y) 这个函数方程的解是 f(1) *
x [假设f 是连续函数]
为了转化为上面那个形式，我们把概率取对数,  写成  t = log p 就有

f(t) >= 0, for    t<=0
f(t) = 0 if t = 0
f(t1 + t2) = f(t1)  + f(t2)

从最后一个我们知道 f = f(1) * t  = f(1) * log p. 我们看符号就知道， f(1) < 0. 我们不妨就取
f(1) = -1. 这个地方这个常数不重要， 取几，就相对于香农的标准定义膨胀了几倍信息量而已。 这个解满足所有的形式。

现在，我们就有了自信息量的定义了。 概率为 p 的事件 按照我们的公理体系，一定含有 - a * log p 的信息量。 其中 a 是正实
数。

有了这个自信息量， 熵就是很显然的了。 熵就是这个总体的信息量，就是一个系统关于信息量的平均值，或者说数学期望， 所以呢，就是

sum p * - a log p  = - a sum p log p. 假设 a =1, 就是香农的定义鸟。

2008/5/24 Eric <xu.ma...@gmail.com>:

[hayate]

很受启发。

顺便问一下，eric是学什么的？

2008/5/24 pongba <pon...@gmail.com>:

[windstorm]

个人感觉eric的定义方法不错，但是不属于最容易切入的思考方式

我觉得理解熵的定义，主要是把握两点

1 如eric所说，信息量是非负的，而信息量代表确定性，熵代表不确定性，信息量与熵是一个相反的量，所以熵是负数，是负"信息量"

2 接下来只需要考虑如何定义这个"信息量"

到这里的思考就比较顺畅了，香农是用bit来定义的，信息量p的度量就可以用 log p表示，以2为底，这是bit的本质决定的。总的信息量就是数学期望，eric已经具体说了。

所以理解熵的本质是"一个系统中的总信息量的负数"后，就好理解了，这样即使熵应用在其他方面，此时信息量的计算方式和现在不同时，也无碍于熵的计算。

2008/5/23 hayate <haya...@gmail.com>:

--
Yours Sincerely

Kun

[hayate]

但是为什么非要用log呢

2008/5/24 windstorm <likunar...@gmail.com>:

[windstorm]

为什么用对数的原因，就是在这里信息量的量化方式，我说了，香农一开始是用bit来度量信息量的，一个最直接的想法就是对这个信息量做以2为底的对数，得出的结果就刚好以bit表示。如果是更具体的理由，eric之前那个帖子我觉得说得很清楚。

这就是我刚才说的，不同的方面有不同的定义，只是在信息论这里，熵是这样定义的。我觉得不能想成熵就是用对数表示，而要想成，在这里，熵和对数通过二进制表达体系很好得联系在一起，方便我们的计算研究。

2008/5/23 hayate <haya...@gmail.com>:

--
Yours Sincerely

Kun

[kicool]

深受启发
另外，有个猜数字的游戏，想必大家都玩过，有人说7次比能猜中，这个能不能从信息论的角度解释一下？

[zl]

还有一种解释方法
7个数的全排列有7！中，每一次比较可以去掉状态空间中一半不合适的节点
只需要log(7!)次即可缩减到最终节点

On 5月24日, 上午10时01分, pongba <pon...@gmail.com> wrote:
> 有的有的，你是直接发到我的邮箱了，我重贴一下吧:-)
>
> ===以下===
>
> 我的这个理解不见得是"最" 本质的， 不过是我自己想出来的，手推了一下， 不难。 随口所写，语言不见得像教科书一样精当。
>
> －－

> 要理解熵为啥这样定义， 我们先假设一下我们能天才般的体会到香农同学的"熵是对于不确定性的度量"，也就是说， 我希望大家先同意， 熵是和统计有关

> 2008/5/24 Eric <xu.math...@gmail.com>:

[Eric]

windstrom 我想你被一些科普的书迷惑了。信息熵不是信息量的相反数。那个负号是本来就存在的/ 符号的来源一方面可见我的推导 另一方面可见
经典bit 的定义。 要描述一个 1/n 的事件 至少要 log n = - log (1/n) 个 bit/
负号是本身就有的，不是你“理解成相反” 然后获得的。

你的理解，即熵是不确定， 信息量是确定， 当然从某个层面上说是对的，下面我用猜数字的例子解释一下。

猜数字如果是2分法 1-100, 原来是 log 100 bit 每次获得 1 bit 信息量 7次后可以猜出数字来. 原来的系统， 要描
述， 至少要获得7个bit. 算法就是想办法获得 7 个 bit. 从而对于未知世界有认识。

理解1 ： 从算法的角度，可以认为获得了7个bit, 从而算法重构了原来的信息. [算法从0开始，最后能输出1-100，必然内部需要log
100 的信息量]

理解2： 可以认为原来系统的熵被你慢慢减小为0 任何排序和猜数字的算法可以理解为通过获得信息量去消减原来的熵，直到降为 0。

但请注意，你获得一个条件后，其实不是说就是原来的熵，减去获得的信息量，而是要重构原来的熵。 新的熵是在获得条件{ Y: 猜的数字 >
50} 后， 条件熵 I(X|Y) 正好比原先的熵 I(X) 小了一个 bit. 恰好在这个例子中，你定义的每次获得的 bit ， 就是加了
这个条件之后系统失去的熵。 但是一般情况不是这样的， 一般情况下，不好的算法， 可能每次看上去获得了 1bit, 实际上在条件熵意义下并没
有 （如我说的排序， 在知道 a>b b>c 后 问 a>c 就是废话 信息量为0) 这个地方不借用条件熵而光用加减是没法解释的/

所以，所谓熵是信息量的相反数　其实是一个误导。　熵就是信息量的数学期望，是系统的平均信息量，　是描述这个系统需要的信息量，这个地方并没有符号相
反的说法。　熵也是一个算法获得多少信息量后能够把这个系统的状态完全确定的一个度量。　一个是从系统本身条件熵的意义来说, 在逐步减小，一个是从算
法本身获得信息重建系统的角度来说，　在逐步变大。　熵以信息量的形式从系统流向算法，从而算法最后能确定结果。

有人肯定会质疑，算法不是确定的么，怎么算法系统也有熵呢。我以排序为例解释一下。　排序算法其实是建立一个下标到下标的映射。　这样的下标映射正好是
　n! 个。　对于算法系统来讲，　对于输入数据，　肯定是以　1/n! 的概率输出一个下标到下标的映射。　因此，排序算法比如要获得　log
(1/n!) 的信息量。　把排序算法看作一个信号发生器，　自己的熵也就是　log n!



所以，我的结论是，在系统－算法这样一个消解－重建系统中；　信息是守恒的。

[图灵刘江]

张景中院士用面积法解几何题的思路，我是最近才知道的，
有种当头一棒的感觉。当年做过那么多几何题，咋就没往
这方面想呢？

很多时候，还是需要不着调地空想一下的。

[pongba]

2008/5/22 Yong Yuan <yyc...@gmail.com>:

今天看到David MacKay的文章：http://users.aims.ac.za/~mackay/sorting/sorting.html。里面提到利用信息论，称12球的问题可以系统地解决，不需要试错。学过信息论的大大们可能觉得火星了。我对信息论一知半解，所以看到这套思路觉得非常新鲜。有种用惯罗马计数法的人突然明白阿拉伯计数法，或者用惯加法的人突然领略乘法时的惊喜。文章里提到的教材Information Theory, Inference, and Learning Algorithms有详尽的讨论，而且作者还免费开放下载：http://users.aims.ac.za/~mackay/itila/book.html。

Eric在blog上又详细介绍了熵的公理化定义，见这里：http://blog.youxu.info/2008/05/24/information-theory-explained/

[windstorm]

首先我承认，因为长期倾向于熵的统一理解，所以即使在香农公式中我也倾向于按照熵的"本质化定义"来思考，其实这样的思考，确实是不能直接应用在香农公式上的。但这不一定是我的问题，这个下面我会描述。

但是，我觉得Eric过于纠结熵在算法中的表达应用了。

首先，我刚才说了，你推导的表达式是属于信息论中，以香农的观点和定义方式来定义的熵的表达式，或者说是"信息熵"的表达式，换句话说，不管它的表达式是什么，熵表征系统的不确定性，无序性，而在"信息论"中，信息量表征系统的确定性，有序性，这个本质是不变的，大家都没有争议吧。

其次，那我们就可以从本质上看熵。一个系统序的程度和无序的程度，本身就是相反的。熵最早的应用是在热力学上，熵的表达式是系统末态的序减去出态的序，获得系统的"不确定性"的增加。自然，将熵取反，就表示系统确定性的增加（这是显然的，参考热力学第二定律），即初态的序，减去末态的序。

其三，应用到信息论领域，我们不能从"序"的观点来简单衡量熵了，信息系统和物理系统毕竟是两个东西。信息系统没有序，那么我们应该找一个别的量衡量，这就是不确定性。香农定义狭义信息论时，提出信息，是人们对事物了解的不确定性的消除或减少。而熵表示什么？正是人们对事物了解的不确定性的度量。也就是说，信息量的增加，必然表示熵的减少，但在他们所表征的通信系统中，总不确定性的绝对量是一定的。这和正负数的本质是一样的，正数越大，负数越小，但是两者绝对值相同。

用一个例子表示（这个例子和香农的认识是不同的），在通信系统中，我们把有信源和信宿。信源对于通信系统，是不确定性的表征（熵，或者说是认识上的混乱程度），信宿则是确定性的表征------我们收到一点信息，就消除了一点不确定性。如果我们不考虑干扰，信源发出的信息，是和信宿接受的信息，一一对应的，在这里，熵和信息量得到了统一。量相同，因表征的含义相反而表达式不同------相差一个符号。

维纳作为信息论的另一个创始人，曾说过

The quantity that we here define as amount of information is the negative of the quantity usually defined as entropy in similar situations"

可以说，这是维纳的个人看法，香农是这样看的：

The quantity which uniquely meets the natural requirements that one sets up for "information" turns out to be exactly that which is known in thermodynamics as entropy.

我个人看法，是因为维纳是以一个更高层面的高度来看熵这个东西，无论是在热力学中，生物学中，信息学中，熵的本质都是不变的，只不过其描述的量，因为对象的不同而不同（比如不能用序衡量信息系统）。热力学中熵表示的是"系统混乱状态"，信息论中信息熵表示的是信息量，生物学中熵表示的是生物多样性，仅此而已。

香农本身是不满意"信息论"这个名称的，为什么呢？因为他自己倾向于用"熵"来命名这个理论。我们可以从信息论的发展上看，得出"信息量"在香农公式中，实在无法成为一个完美的统一，甚至可以说，如果香农公式是绝对合理的，那么对于香农公式定义的通信系统来说，它传递的不是"信息量"。

这个怎么理解呢？实际上，香农并不关心你这个信道传递的是什么，我们通过信道传输的所有东西，都是香农所谓的"信息"，包括比如我们说的"nonsense"。更通俗点来说，比如我们聊天时，信息 "I feel fine" 对于我们来说，是信息, 而 "ff eeI efni" 则不属于信息，或者有意义的信息。但是在香农定义中，这也属于信息，对于通信系统是有意义的。这就是为什么香农倾向于用"熵"来命名这个理论。很显然，后者只有对熵，才能叫有意义。

但是，对于信息论研究学者来说，香农这个定义并不是很严密的，这样让后人为他擦屁股吃尽了苦头。Langefors甚至直接就提议，把信息论改为"signal transmission theory"，信号传输论，似乎更好一些。Miller在写书的时候，引用香农公式的时候，直接就把这个负号是去掉了的。后人在理解香农的定义是，还用"entropy contains more information than structure"来解释香农的理论，虽然在无数人看来，这是和common sense相悖的。还有一堆香农继承者在90年代提出的"负信息"，"相对信息"，无一不是对这种contradiction的补充，或者"试图补充"。



所以，用信息量来衡量香农公式，是不对的，信号量是一个更好的表述。在香农看来，通信系统的组成，是信号的发射器和接收器----仅此而已。而Eric，你所举的例子，其一，不属于传统通信领域，其二，全部都是"信息量"的例子，也就是说，这些系统中暂时都不含有"nonsense"，所以理解这些系统，我个人认为，都可以用

"信息熵"和"信息量"相反

来表示。

我说了一大堆废话，主要就是想表明，熵应该是被统一看待和理解的，无论在什么领域，我们不能说在物理领域中熵的推导表示意思A，在信息学中熵的同样表达式（实际上香农用entropy，本身就是参考的热力学），我们就推导出意思B了。

在这点上，我很赞同维纳的看法。香农本身不承认维纳的观点，但是按照概率和对数的推导------这个Eric你已经推导过了------不管你愿意怎么理解，自然推导也好，巧合也好------本质上，最终的形式还是归于"相反的信息量"，还是和熵的原始定义有较好的呼应。熵不是信息量的数学期望，是信息量数学期望的相反数，无论是概念上，还是表达形式上。


2008/5/24 Eric <xu.ma...@gmail.com>:

--
Yours Sincerely

Kun

[pongba]

这个帖子是越来越强大了:0)

我也跟hayate八卦一句，windstorm兄是学什么的？

顺便擅自代Eric答hayate，Eric是南大数学系本科出身，现在华盛顿大学读CS的Ph.D，牛人。主页在这里：http://youxu.info/

2008/5/25 windstorm <likunar...@gmail.com>:

首先我承认，因为长期倾向于熵的统一理解，所以即使在香农公式中我也倾向于按照熵的"本质化定义"来思考，其实这样的思考，确实是不能直接应用在香农公式上的。但这不一定是我的问题，这个下面我会描述。

但是，我觉得Eric过于纠结熵在算法中的表达应用了。

首先，我刚才说了，你推导的表达式是属于信息论中，以香农的观点和定义方式来定义的熵的表达式，或者说是"信息熵"的表达式，换句话说，不管它的表达式是什么，熵表征系统的不确定性，无序性，而在"信息论"中，信息量表征系统的确定性，有序性，这个本质是不变的，大家都没有争议吧。

其次，那我们就可以从本质上看熵。一个系统序的程度和无序的程度，本身就是相反的。熵最早的应用是在热力学上，熵的表达式是系统末态的序减去出态的序，获得系统的"不确定性"的增加。自然，将熵取反，就表示系统确定性的增加（这是显然的，参考热力学第二定律），即初态的序，减去末态的序。

其三，应用到信息论领域，我们不能从"序"的观点来简单衡量熵了，信息系统和物理系统毕竟是两个东西。信息系统没有序，那么我们应该找一个别的量衡量，这就是不确定性。香农定义狭义信息论时，提出信息，是人们对事物了解的不确定性的消除或减少。而熵表示什么？正是人们对事物了解的不确定性的度量。也就是说，信息量的增加，必然表示熵的减少，但在他们所表征的通信系统中，总不确定性的绝对量是一定的。这和正负数的本质是一样的，正数越大，负数越小，但是两者绝对值相同。

用一个例子表示（这个例子和香农的认识是不同的），在通信系统中，我们把有信源和信宿。信源对于通信系统，是不确定性的表征（熵，或者说是认识上的混乱程度），信宿则是确定性的表征------我们收到一点信息，就消除了一点不确定性。如果我们不考虑干扰，信源发出的信息，是和信宿接受的信息，一一对应的，在这里，熵和信息量得到了统一。量相同，因表征的含义相反而表达式不同------相差一个符号。

维纳作为信息论的另一个创始人，曾说过

The quantity that we here define as amount of information is the negative of the quantity usually defined as entropy in similar situations"

可以说，这是维纳的个人看法，香农是这样看的：

The quantity which uniquely meets the natural requirements that one sets up for "information" turns out to be exactly that which is known in thermodynamics as entropy.

我个人看法，是因为维纳是以一个更高层面的高度来看熵这个东西，无论是在热力学中，生物学中，信息学中，熵的本质都是不变的，只不过其描述的量，因为对象的不同而不同（比如不能用序衡量信息系统）。热力学中熵表示的是"系统混乱状态"，信息论中信息熵表示的是信息量，生物学中熵表示的是生物多样性，仅此而已。

香农本身是不满意"信息论"这个名称的，为什么呢？因为他自己倾向于用"熵"来命名这个理论。我们可以从信息论的发展上看，得出"信息量"在香农公式中，实在无法成为一个完美的统一，甚至可以说，如果香农公式是绝对合理的，那么对于香农公式定义的通信系统来说，它传递的不是"信息量"。

这个怎么理解呢？实际上，香农并不关心你这个信道传递的是什么，我们通过信道传输的所有东西，都是香农所谓的"信息"，包括比如我们说的"nonsense"。更通俗点来说，比如我们聊天时，信息 "I feel fine" 对于我们来说，是信息, 而 "ff eeI efni" 则不属于信息，或者有意义的信息。但是在香农定义中，这也属于信息，对于通信系统是有意义的。这就是为什么香农倾向于用"熵"来命名这个理论。很显然，后者只有对熵，才能叫有意义。

但是，对于信息论研究学者来说，香农这个定义并不是很严密的，这样让后人为他擦屁股吃尽了苦头。Langefors甚至直接就提议，把信息论改为"signal transmission theory"，信号传输论，似乎更好一些。Miller在写书的时候，引用香农公式的时候，直接就把这个负号是去掉了的。后人在理解香农的定义是，还用"entropy contains more information than structure"来解释香农的理论，虽然在无数人看来，这是和common sense相悖的。还有一堆香农继承者在90年代提出的"负信息"，"相对信息"，无一不是对这种contradiction的补充，或者"试图补充"。



所以，用信息量来衡量香农公式，是不对的，信号量是一个更好的表述。在香农看来，通信系统的组成，是信号的发射器和接收器----仅此而已。而Eric，你所举的例子，其一，不属于传统通信领域，其二，全部都是"信息量"的例子，也就是说，这些系统中暂时都不含有"nonsense"，所以理解这些系统，我个人认为，都可以用

"信息熵"和"信息量"相反

来表示。

我说了一大堆废话，主要就是想表明，熵应该是被统一看待和理解的，无论在什么领域，我们不能说在物理领域中熵的推导表示意思A，在信息学中熵的同样表达式（实际上香农用entropy，本身就是参考的热力学），我们就推导出意思B了。

在这点上，我很赞同维纳的看法。香农本身不承认维纳的观点，但是按照概率和对数的推导------这个Eric你已经推导过了------不管你愿意怎么理解，自然推导也好，巧合也好------本质上，最终的形式还是归于"相反的信息量"，还是和熵的原始定义有较好的呼应。熵不是信息量的数学期望，是信息量数学期望的相反数，无论是概念上，还是表达形式上。

[windstorm]

本科通信出身，所以理解熵大多是从通信系统角度出发的。不过我个人对这玩意不是很感冒，所以即将去帝国主义读嵌入式体系结构。

2008/5/25 pongba <pon...@gmail.com>:

--
Yours Sincerely

Kun

[hayate]

噢 xuyou我知道，你以前介绍过，只是xuyou太出名，反而不识Eric了

从公理出发，纯形式化的建立体系，我感觉是受过专门训练的，:D

2008/5/25 pongba <pon...@gmail.com>:

[hayate]

呵呵 都是牛人。受益匪浅！

2008/5/25 windstorm <likunar...@gmail.com>:

[kicool]

"任何排序和猜数字的算法可以理解为通过获得信息量去消减原来的熵" 看了这句有别开洞天之感

2008/5/24 Eric <xu.ma...@gmail.com>:

[Justin L]

这里要表达120个值，这些信息如果用按bit来保存进内存，则需要log_2{120}个bit位。
就是7位二进制数，可表达超过120种信息。

问题是 如何把表达5个整数的全排列，使每个排列映射成为一个7为二进制数呢？
(例如：ABCDE表示0，EABCD表示1)

[windstorm]

Justin L为什么要关心"如何映射"呢？我们关心的是"5个整数的全排列"中，我们获得某个排列，这个选择的概率，而不是关心，我们如何映射某个排列并获得其中特定的某个排列的方法。

用你的例子说明，在这里，比特数表示的，是我们至少可以用多少次划分，来获得某个排列（如abdce），比如我只需要7次（最简单的二分法），就一定能确定abdce的表示方式。至于这个abdce你用0000000表示，还是用1111110表示，是没有关系的，我获得的abdce的表示，就是我们需要的信息量。熵的值和你具体对某种可能采用什么映射，也是没有关系的。

另外，这里大家概率一样，所以bit的数目是7，如果在某个应用中，概率不同，那么实际所用次数实际比7小，也就是说，在等概率事件中，信息熵最大。

说通俗点，你扔硬币，你规定正面朝上是1，还是反面朝上是1，都没有关系，不影响这个系统的信息量。

2008/5/26 Justin L <ice...@gmail.com>:

--
Yours Sincerely

Kun

[Justin L]

如果不能取得信息源映射到最后信宿的方法那就是理论研究。
确实，理论上的7次，但是那是你try上千次,上万次得到的一个极限值。
我关心的是我们如何使用理论，"如何映射"是我关心的求解过程。和硬币的哪一面是1当然不是指同一个"映射"。


我们可以停留在等概率事件，熵最大。或者我们干脆更进一步，得到一个方法，或者是一个思维方式。何乐而不为呢 :)

另外，你引用的我例子，最简单的二分法七次不一定能确定abdce的表达方式，熵的改变不能靠你事先揣摩的，也就是说，你每一次操作，不一定就能得到你
要的信息量，说不定你做完一次操作后，发现熵没有变化。
例如你发现bc比a小，ce比a大。但是你是怎么能确保你选择了a呢？

On 5月26日, 下午7时51分, windstorm <likunarmstr...@gmail.com> wrote:
> Justin L为什么要关心"如何映射"呢？我们关心的是"5个整数的全排列"中，我们获得某个排列，这个选择的概率，而不是关心，我们如何映射某个排列并获得其中特定的某个排列的方法。
>
> 用你的例子说明，在这里，比特数表示的，是我们至少可以用多少次划分，来获得某个排列（如abdce），比如我只需要7次（最简单的二分法），就一定能确定abdce的表示方式。至于这个abdce你用0000000表示，还是用1111110表示，是没有关系的，我获得的abdce的表示，就是我们需要的信息量。熵的值和你具体对某种可能采用什么映射，也是没有关系的。
>
> 另外，这里大家概率一样，所以bit的数目是7，如果在某个应用中，概率不同，那么实际所用次数实际比7小，也就是说，在等概率事件中，信息熵最大。
>
> 说通俗点，你扔硬币，你规定正面朝上是1，还是反面朝上是1，都没有关系，不影响这个系统的信息量。
>

> 2008/5/26 Justin L <icer...@gmail.com>:

[windstorm]

是我没有说清楚还是你没有理解清楚？为什么一定要取得信息源映射到最后信宿的方法？这并不是熵的应用范畴。

首先，信息论本来就是理论研究，熵的概念可以用于估计，检测，金融模型，这些都是理论性模型的应用。但不代表它没有实际意义阿。我从开头再重新说一遍好了，拿通信系统举例子来体现"实用性"，熵的概念以香农的"信息熵"为准，也就是Eric所阐述的。

我们知道，一个通信系统，是由信源，信道，信宿所组成，信源发出消息，经过信道，到达信宿，信宿收到消息，获得了信息，这个过程就称作通讯。

然后我们从源头开始看，信息论，或者说熵的提出为了什么？为了表征源头的不确定性，比如源头能发0，1两种码，显然，信宿知道你源头能发两种码，但不知道信源某个时刻具体发0还是发1，这是显然的，因为这就是通信的目的。

怎么判断一个通信系统是否有价值？举个例子，如果一个信源，它发1的概率是100％，那么猜都不用猜，信宿收到的序列肯定是1111111，ok，这就是没有实用价值的通信系统。我们要它没用。如果信源发0和发1的概率为各50％，我们说这是最有价值的通信系统，因为每次通信，我们获得的信息量（在这里等于熵量）都是最大的。如果信道是无噪的，我每一次通信都能消除不确定度，在这里，所获得的信息量就是不确定度（这就是为什么香农本人是倾向于用"熵论"而非"信息论"命名）。

很多教科书在讲述这个问题的时候，都是一笔带过，我一些同学到现在也没完整明白，为什么前者没有价值，后者有价值。原因是这样的，对于一个通信系统来讲（其他任何系统同理）熵最大的意义，是我们因为数据不足而进行的人为假定和人为添加信息最小，从而所获得的解误差最小，最合乎自然，而最自然的解，是所有系统追求的目标。

所以在这里，就是熵的最基础的实际应用，那就是评估通信系统。并可以因此引伸出很多别的概念，比如分析有扰信道下获得的实际平均信息量，或者寻找某种概率分布，让信道容量最大。

这和我最后获得的信息序列是0001101还是0011100有关系么？如果发0和发1概率相等，我最后不管获得什么序列，得到的熵量都是一样的，这和映射一点关系都没有。

然后我们换一个角度，不说通信系统了，说说算法。前面说过，熵的大小，表示事件的不确定性大小，那我们具体怎么来应用熵？举个例子，我们对5，4，3，1，2，五个数字排序，假如我们使用最笨的循环排序，到了第四步时，序列变成了1，2，3，5，4，然后你把5还是按照之前的方法来比较，这显然是做了很多无用功，为什么？因为1，2，3是已经确定了的东西，他们比5小才会在之前的比较中排在前面，我们说，在这一步，5和1，2，3的比较都无法带给我们任何信息量了。所以，理论上最完美的算法，就是每次操作，熵都是最大的。在这里，我们不需要关心1，2，3，4，5这五个数字的全排列，如何映射到某个二进制序列上。

再推广，熵可以衡量你提出的算法模型在某个应用中的错误率，或者说是实用性，比如现在南方都在遭受洪灾，如何让洪水预报的水文模型更加精确，从而让误差最少，是研究人员的目的。此时，水文预报的不确定性，就是是影响预报调度风险率的重要因素。

显然，在这里，熵就派上了用场，从刚才对算法的分析中，我们可以知道，一个不确定性问题的可行解，熵最大的解一定是最好的。于是，我们只需要建立一个最大熵模型，以其为准则求出相应的误差的概率密度函数，就可以知道满足什么条件，误差最小，然后把各种水文特征量带入，就能够知道洪水预报误差的特性。

在这个例子中，你当然也可以用xxxbit来去映射洪水预报误差的各种可能情况，但是和前面一样，这是毫无意义的。对于熵来说，我们更关注的是某个系统具备某个特性或产生某种趋势的概率，而不是要求出一个精确解。

这已经是我能力范围内最多的解释，如果Justin还是要问"如何映射能得到最后解的编码形式"，我只能说，也许有相关研究，但映射方法已经超出我的所学范围。

2008/5/31 Justin L <ice...@gmail.com>:

[natur...@gmail.com]

Eric的是严谨的公理化表示法

On 5月24日, 下午12时45分, windstorm <likunarmstr...@gmail.com> wrote:
> 个人感觉eric的定义方法不错，但是不属于最容易切入的思考方式
>
> 我觉得理解熵的定义，主要是把握两点
>
> 1 如eric所说，信息量是非负的，而信息量代表确定性，熵代表不确定性，信息量与熵是一个相反的量，所以熵是负数，是负"信息量"
>
> 2 接下来只需要考虑如何定义这个"信息量"
>
> 到这里的思考就比较顺畅了，香农是用bit来定义的，信息量p的度量就可以用 log
> p表示，以2为底，这是bit的本质决定的。总的信息量就是数学期望，eric已经具体说了。
>
> 所以理解熵的本质是"一个系统中的总信息量的负数"后，就好理解了，这样即使熵应用在其他方面，此时信息量的计算方式和现在不同时，也无碍于熵的计算。
>

> 2008/5/23 hayate <hayate...@gmail.com>:

> >> 2008/5/24 Eric <xu.math...@gmail.com>:

>
> >>> 可怜我回复了超级长的一段 全没了
>
> >>> 用公理化定义吧 想想概率论是怎么定义的
>
> >>> 信息量如果定义成概率的函数 必须有的性质是什么？ 再解一个函数方程 就得到 -log p 了
>
> >>> 熵就是信息量的数学期望
>
> >>> On May 23, 9:14 am, pongba <pon...@gmail.com> wrote:
> >>> > 2008/5/23 Eric <xu.math...@gmail.com>:
>
> >>> > > 我来解释一下吧
>
> >>> > > 我们看比特的定义就行了。 说一个抛硬币 正反各 1/2 概率。 如果信号源是这个， 所含有的信息量就是 - 1/2 * log (1/2)
> >>> > > + -1/2 * log(1/2) = 1 bit
>
> >>> > > 所以, 一个能生成 1/2 1/2 概率分布的信号所含的信息量就是 1bit
>
> >>> > 那为什么信息熵偏偏定义成那样的呢？即，这个定义的本质内涵是什么。
>
> >>> > --
> >>> > 刘未鹏(pongba)|C++的罗浮宫http://blog.csdn.net/pongba
> >>> > TopLanguagehttp://groups.google.com/group/pongba
>
> >> --
> >> 刘未鹏(pongba)|C++的罗浮宫
> >>http://blog.csdn.net/pongba
> >> TopLanguage
>
> >>http://groups.google.com/group/pongba
>
> --
> Yours Sincerely
>

> Kun- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[pongba]

2008/5/23 hayate <haya...@gmail.com>:

我是这么理解的。如果定义了偏序关系，也就是大小关系，那么两个数的关系非此即彼，含有1bit的信息量。

比较一次，对象的信息量就会减少1bit

说实话这个问题从上次之后我还是一直没有得到直观的感受。虽然徐宥和windstorm两位老大都详细介绍了信息熵的定义，但是也许是因为说得比较学术化还是怎么的，我还是看得云里雾里，总觉得没有摸到问题的本质。

昨天翻到数学之美系列的"怎样度量信息"（以前一直没看），发现上面的一个例子道出了问题的本质：

那么我们如何量化的度量信息量呢？我们来看一个例子，马上要举行世界杯赛了。大家都很关心谁会是冠军。假如我错过了看世界杯，赛后我问一个知道比赛结果的 观众"哪支球队是冠军"？ 他不愿意直接告诉我， 而要让我猜，并且我每猜一次，他要收一元钱才肯告诉我是否猜对了，那么我需要付给他多少钱才能知道谁是冠军呢? 我可以把球队编上号，从 1 到 32， 然后提问： "冠军的球队在 1-16 号中吗?" 假如他告诉我猜对了， 我会接着问： "冠军在 1-8 号中吗?" 假如他告诉我猜错了， 我自然知道冠军队在 9-16 中。 这样只需要五次， 我就能知道哪支球队是冠军。所以，谁是世界杯冠军这条消息的信息量只值五块钱。

具体到hayate提到的5个元素需要7次比较上来，其实根本用不着什么信息熵的概念，可以完全"平民"的解释：

将5个元素的最终正确排列作为一个未知量（显然，这个未知量总共有5!种可能），现在由另一个人来通过问问题的方式去猜测这个未知量的值。

这个猜的人问的第一个问题是：a1 < a2吗？当得到答案之后（不管答案是a1<a2还是a1>a2），未知量的可能性就变成了原来的1/2，即一旦a1和a2的关系确定了，整个数组的排列可能性就剩下了原来的一半！

这个人继续问问题，ai < aj吗？如果机会均等的话，他通过答案能得到的信息只能是排列的可能性再次减半。如果运气不错的话则能得到更多信息。如果运气很糟的话则可能得到少于一半的信息。

如此每问一个问题，可能性大约减半。而又因为可能性一共有5!，所以需要log_2{5!}次询问。

下面以4个元素的比较为例，因为5个元素的排列组合太多了：

a1 a2 a3 a4

step0. 4个元素只有24种排列，其中只有一种排列是正确的排序。每次比较就相当于问一个问题，目的是逼问出那个正确的排列到底是什么。
step1. a1<a2吗？得到a1和a2的关系之后，排列组合的可能性变成一半，即12种。
step2. 不妨假设step1得到的答案是a1<a2。我们继续问：a3<a1吗？容易发现，如果a3>a1那么可能性剩下8种。如果a3<a1则可能性剩下4种。前者是倒霉，后者是运气。另，如果机会均等的话，那么这个问题的答案应该不偏向于任何一方。比如在称小球问题中可以假设机会总是在和你作对，令你无论什么策略都不会得到比"半对半"更佳的信息。
step3. 继续问.. 直到问出最终排列。

[Eric]

我觉得我一开始就解释了排序就是问一个 a>b 否的问题，以及猜数字就是小熊分饼干所以要保证均匀这个事情吧 :) 我也提到了决策树, 最大熵(机
会均等)的问题, 这些问题都是一起的.

其实不管信息论也好 二叉决策树也好, 思路都是一样的, 就是看这个问题值不值得问. 只是角度不同. 或许pangba兄觉得用决策树的方法看更加
本质, 我反而觉得用信息论更加本质, 其实都是一样的, 只是信息论形式化了一下概率变成了信息量而已 :)

另外，这几天我重新把TAOCP 第三卷(第二版)翻出来看了看 Knuth 怎么说这个问题的, 发现真是牛大了:

先说性能:

pp148, section 5.2.3 说:

When N = 1000, the approximate average runiing time on MIX are
160000u for heapsort
130000u for shellsort
80000u for quicksort

这里, Knuth 同学发现一般情况下 heapsort 表现很不好. 于是, 在下文他就说, 习题18 (pp156, 难度21)

(R.W.Floyd) During the selection phase of heapsort, the key K tends to
be quite small, so that nearly all the comparisons in step H6 find
K<K_j. Show how to modify the algorithm so that K is not compared with
K_j in the main loop of the computation, thereby nearly cutting the
average number of comparisons in half.

答案里面的方法和DMK的方法是一样的. (我觉得DMK是看了这个论文或者TAoCP的) 这里说 by half, 就正好和快排差不多了.

再说信息论分析:

在5.3.1 (pp181) 高爷爷就说, "排序问题可以看成是一个书上的鸟儿排排站的问题. (还特地画了一棵树), 下一段就说, 其实这个也
有等价说法, 就是信息论, 我们从称球问题说起....."

然后后面一直讲信息论和最小比较排序

回想当年看这个书的时候，不求甚解, 看到难的数学就跳, 居然这些深入浅出的东西都被跳过了. 撞墙去了.






On Jun 9, 9:48 am, pongba <pon...@gmail.com> wrote:
> 2008/5/23 hayate <hayate...@gmail.com>:

[pongba]

2008/6/14 Eric <xu.ma...@gmail.com>:

我觉得我一开始就解释了排序就是问一个 a>b 否的问题，以及猜数字就是小熊分饼干所以要保证均匀这个事情吧 :) 我也提到了决策树, 最大熵(机
会均等)的问题, 这些问题都是一起的.

其实不管信息论也好 二叉决策树也好, 思路都是一样的, 就是看这个问题值不值得问. 只是角度不同. 或许pangba兄觉得用决策树的方法看更加
本质, 我反而觉得用信息论更加本质, 其实都是一样的, 只是信息论形式化了一下概率变成了信息量而已 :)

嗯嗯，是的。只是我不通信息论，所以不得不寻找一个满足我这个榔头的钉子:D
 

另外，这几天我重新把TAOCP 第三卷(第二版)翻出来看了看 Knuth 怎么说这个问题的, 发现真是牛大了:

先说性能:

pp148, section 5.2.3 说:

When N = 1000, the approximate average runiing time on MIX are
160000u for heapsort
130000u for shellsort
80000u  for quicksort

这里,  Knuth 同学发现一般情况下 heapsort 表现很不好. 于是, 在下文他就说, 习题18 (pp156, 难度21)

(R.W.Floyd) During the selection phase of heapsort, the key K tends to
be quite small, so that nearly all the comparisons in step H6 find
K<K_j. Show how to modify the algorithm so that K is not compared with
K_j in the main loop of the computation, thereby nearly cutting the
average number of comparisons in half.

答案里面的方法和DMK的方法是一样的. (我觉得DMK是看了这个论文或者TAoCP的) 这里说 by half, 就正好和快排差不多了.

再说信息论分析:

在5.3.1 (pp181) 高爷爷就说, "排序问题可以看成是一个书上的鸟儿排排站的问题. (还特地画了一棵树), 下一段就说, 其实这个也
有等价说法, 就是信息论, 我们从称球问题说起....."

然后后面一直讲信息论和最小比较排序

回想当年看这个书的时候，不求甚解, 看到难的数学就跳, 居然这些深入浅出的东西都被跳过了. 撞墙去了.

哦，天哪，高爷爷不愧姓高:-D 赶紧跑去看看他咋说的..

[Yong Yuan]

2008/6/13 Eric <xu.ma...@gmail.com>:

我觉得我一开始就解释了排序就是问一个 a>b 否的问题，以及猜数字就是小熊分饼干所以要保证均匀这个事情吧 :) 我也提到了决策树, 最大熵(机
会均等)的问题, 这些问题都是一起的.

其实不管信息论也好 二叉决策树也好, 思路都是一样的, 就是看这个问题值不值得问. 只是角度不同. 或许pangba兄觉得用决策树的方法看更加
本质, 我反而觉得用信息论更加本质, 其实都是一样的, 只是信息论形式化了一下概率变成了信息量而已 :)

另外，这几天我重新把TAOCP 第三卷(第二版)翻出来看了看 Knuth 怎么说这个问题的, 发现真是牛大了:

先说性能:

pp148, section 5.2.3 说:

When N = 1000, the approximate average runiing time on MIX are
160000u for heapsort
130000u for shellsort
80000u  for quicksort

这里,  Knuth 同学发现一般情况下 heapsort 表现很不好. 于是, 在下文他就说, 习题18 (pp156, 难度21)

(R.W.Floyd) During the selection phase of heapsort, the key K tends to
be quite small, so that nearly all the comparisons in step H6 find
K<K_j. Show how to modify the algorithm so that K is not compared with
K_j in the main loop of the computation, thereby nearly cutting the
average number of comparisons in half.

答案里面的方法和DMK的方法是一样的. (我觉得DMK是看了这个论文或者TAoCP的) 这里说 by half, 就正好和快排差不多了.

再说信息论分析:

在5.3.1 (pp181) 高爷爷就说, "排序问题可以看成是一个书上的鸟儿排排站的问题. (还特地画了一棵树), 下一段就说, 其实这个也
有等价说法, 就是信息论, 我们从称球问题说起....."

然后后面一直讲信息论和最小比较排序

回想当年看这个书的时候，不求甚解, 看到难的数学就跳, 居然这些深入浅出的东西都被跳过了. 撞墙去了.

 

瀑布汗。当年也是看了这部分的。为啥一点印象都没有了呢。就地自卑ing

[fuzhli1007]

是啊，只能给出方向上的指导

On 5月22日, 下午7时31分, "dailiangren" <dailiang...@gmail.com> wrote:
> 我觉得纵然采用信息论依然无法给出具体的方法，但是信息论可以给具体方法的提出给出一个方向上的指导。
>
> dailiangren
> 2008-05-22
>
> 发件人： pongba
> 发送时间： 2008-05-22 15:58:54
> 收件人： pon...@googlegroups.com
> 抄送：
> 主题： [TopLanguage] Re: 说到解题的思路
>
> 2008/5/22 Yong Yuan <yycs...@gmail.com>:

>
> 今天看到David MacKay的文章：http://users.aims.ac.za/~mackay/sorting/sorting.html。里面提到利用信息论，称12球的问题可以系统地解决，不需要试错。学过信息论的大大们可能觉得火星了。我对信息论一知半解，所以看到这套思路觉得非常新鲜。有种用惯罗马计数法的人突然明白阿拉伯计数法，或者用惯加法的人突然领略乘法时的惊喜。文章里提到的教材Information Theory, Inference, and Learning Algorithms有详尽的讨论，而且作者还免费开放下载：http://users.aims.ac.za/~mackay/itila/book.html。
>

> 赞！这就是称为"本质"的东西。越是接近本质的理论，往往越是简洁，越具有普遍性，能解决的问题也越多。
> 上次的一道几何证明题，hayate提到，虽然可以用初等方法解，但是如果用解析几何，就可以非常朴素的解出来，虽然计算起来麻烦一点。很多需要用到初等方法中的奇技淫巧的问题，用上触摸到问题真正本质的手法，就没什么神秘了。
> 信息论真是个好理论啊~

[realfun]

我怎么感觉这种方法是贪心算法里面的决定"下一步"的东东？并不一定是最优解吧
另外，他说的最平均，我觉得可以用标准差来代替信息量
我在建立猜数字程序求解树的时候试过标准差和信息量，结果标准差优于信息量，速度快，效果好。
具体代码参见这里：
猜数字游戏8步以内的完全求解决策树生成程序
http://www.fayaa.com/code/view/128/

2008/6/26 fuzhli1007 <fuzhl...@gmail.com>:

--
代码发芽网： http://www.fayaa.com/code/ （无需插件在blog上贴语法高亮的代码，百种语言，多种配色）
我的Blog: http://www.2maomao.com/blog