Wednesday, November 23, 2011

从数楼层问题到最大熵原理

先来看一道智力题目。
有2个鸡蛋和100层楼。可以站在某层往下扔鸡蛋,问尝试多少次,可以一定能获知在哪一层的时候刚好让鸡蛋碎。

——————分割线,请先自行思考30s————————

初看此题,可能认为答案是100。很自然,挨着试呗。
我们假设第k层(k=1...100)的时候鸡蛋刚好碎,那么从第一层开始依次往上是最保险的。因为一旦一开始某次尝试的楼层>k,则鸡蛋碎掉。
当我们手头只有一个鸡蛋的时候,确实只能采取这种方法,因为我们不知道k,不能去冒险。但是,现在有2个鸡蛋,能否减少尝试的次数?
毫无疑问,肯定是可以减少的,比如我们在第50层扔下来第一个鸡蛋,如果碎了,说明k<=50,然后从1...49挨着试第二个即可,最多需要50次(1次第一个,49次第二个)。如果第一个鸡蛋没碎,说明k>50,再用这两个鸡蛋尝试剩下的51...100楼层即可。
那么最优解是多少呢?
仔细思考这个问题,我们尝试扔鸡蛋有两种方法,一种是可以冒险猜一层,一种是挨着保险的线性尝试。对于第一个鸡蛋来说,冒险或者保险都可以。问题在于,一旦第一个鸡蛋碎了,则我们手头就只剩下一个鸡蛋了,这个时候就不能冒险了,只能采取保险的线性方法。因此,关键在于第一个鸡蛋应该采取什么样的策略?冒险还是保险?

——————分割线,请再自行思考30s————————

先暂时把刚才的问题放到一边,我们来看“最大熵原理”。
“最大熵原理是在1957 年由E.T.Jaynes 提出的,其主要思想是,在只掌握关于未知分布的部分知识时,应该选取符合这些知识但熵值最大的概率分布。”
这段话来自百度百科,未必是最准确的定义,但意思已经讲透了。熟悉信息论的同仁相比已经理解了。
用大白话解释这段话,就是说,如果我们不知道足够多的信息,那么对于不知道的部分应该采取最保守的策略,不能添加任何的先验预测。
或者更直白点,如果不知道,千万不要蒙。
一个很平凡的例子就是掷骰子。假如实现你对这个骰子一无所知,请问它掷的结果该是什么样子的?很显然,大家都会说,六个面概率一样,肯定都是1/6.
那么现在告诉你它掷出来1的概率是1/2,那么结果是啥?因为我们只知道1的概率,对其他面依然一无所知,所以,六个面的概率只能是(1/2,1/10,1/10,1/10,1/10,1/10),即剩下的五个面应该是彼此均匀等价的。
回到我们的问题,我们在扔第一个鸡蛋的时候,假如我们选择了第N层作为第一次扔的层数,则有两个可能:
N >= k: 鸡蛋1碎,鸡蛋2可以线性查找1...N-1层,一共需要1+N-1=N次。
N<k: 鸡蛋2没有碎,我们在N+1...100层中解决同一个问题,但是扔的次数少了1.
按照最大熵原理,因为我们不知道任何事先的信息,这两种选择的概率都是等价的,我们要求得最优,就只能让它俩带来的代价一致,也即我们应当选择N,使得无论那种情形发生,我们最终的尝试次数都是一致的。
对于N >= k的情况,一共需要N次,所以对于N<k的情况一共也必须是N次才成。则我们在N+1...100中解决问题,所尝试的次数应当为N-1,此时我们已经成功排除了N层.
可以观察到类似的决策中,从第一次到第N次,我们依次排除了N, N-1, ...1层。
所以我们有
N+N-1+...+1 = 100,或者
N(N+1)/2 =100
容易求得N=14

就是按照这样一个平凡的基本原理,我们求出了这个问题的最优解。实际上,从最大熵原理出发,可以推出近现代信息学上一堆著名的公式和方法,比如大名鼎鼎的卡尔曼滤波器,比如人工智能中的语义分析。或许,越是简单自然的东西,越能反映出这个世界终极的秘密吧。

备注:
这道问题是一个朋友出给我的,我想了大约一分钟,就想透了其中的关键。问题本身并不难,但其解决思路却蕴含了一个基本的原理——最大熵。这或多或少让我感到意外和惊喜。

扩展思考,
一般的,如果我们手头有m个鸡蛋,去尝试n层楼,需要试多少次?

2 comments:

  1. I still cannot understand some points here. Can you explain the following part?
    所以对于N<k的情况,我们在N+1...100中解决问题,所尝试的次数应当为N-1.
    可以观察到从第一次到第N次,我们依次避免了N, N-1, ...1层。(especially here.)
    所以我们有
    N+N-1+...+1 = 100,或者
    N(N+1)/2 =100
    容易求得N=14

    ReplyDelete
    Replies
    1. Hi, glad you're interested with the problem.
      I just updated the explanation, to make it more clear.
      Hope you could get the idea now.
      Besides, welcome for further question.

      Delete