Posts archived in Cool Stuff

在以前的文章中我介绍过囚徒困境,并且介绍了 Tit for Tat 策略,这种策略可以在多轮囚徒困境中不至于受益太差。那么,假如囚徒困境的游戏只有一轮呢? 有什么好的方法可以达到左上角那个双赢状态而不是左下角那个对两者都不是最优的状态呢?

囚徒困境是一个纯博弈论的模型,这个模型里面的赋值就直接决定了想要最大化自己利益的局中人必然会陷入困境,这是模型无法避免的。 所以想要跳出这个困境,只能靠博弈论之外的手段。 所幸的是,我们人类早就发现了这两种方法,并且都在实践中尝试过了这样两种方法。 第一种方法可以看成是直接的斩草除根法,即直接剥夺两个局中人选择“不合作”这个选项的自由,让他们都只有一个合作的选项。 这种政治学方法的优缺点在此我们不做讨论,我们关心的是第二种方法,一种经济学的方法–通过改变游戏受益矩阵,在新的游戏中,让局中人偏好合作。 在宏观经济的实践中,第二种的一般实现方法则是通过道德和法律手段对选择不合作的进行惩罚,对选择合作的实施奖励,以期改变整个收益矩阵,让这个收益矩阵不再满足囚徒困境的条件。 因为道德手段不确定太多,我们只考虑现代社会的最普遍手段,即法律手段。 具体来说,就是让局中人构建合同,并通过合同法等立法手段保护这个合同的实行,从而改变收益矩阵。

从博弈论的角度理解合同的话,通过订立合同,规定合同和法律效力,调控局中人不合作所获得的收益,使得局中人不再偏好”不守约定”选项。 具体的做法也很简单,估计聪明的各位早就想到了:

假定双方都选择合作则收益为 a, 而甲方合作,乙方背叛的时候,甲的收益是 b, 而乙的收益是 c。 按照我们的囚徒困境假设,背叛的收益 c 要大于合作的收益 a, 这样乙才会偏好背叛。 现在我们假设甲乙事先签订一个合同,规定背叛的一方要向合作(没有背叛)的一方支付损失。 我们假设这个值为 r。 显然的,现在乙背叛之后的收益就变成了 c-r, 而 甲合作的收益就是 b+r。 对于乙来说,我们的目的是要让他偏好合作,所以我们一定要让 a 大于等于 c-r。 最极限的情况就是 a = c-r, 于是, r = c-a。 这样, 乙的收益变成了 a, 而甲的收益变成了 b+c-a, 乙即使背叛也占不到好处,而甲也收到了合作的回报。

当然我这里说的是一个简化的模型。 不同的司法实践可能会取不同的 r 值,但是法的精神都是一样的,法律本身不限制你的选择,只是通过合理的奖励和惩罚,让理性的人自然的做出符合自己利益的选择。

从经济学角度来说,人类社会的运行中必然会有这样那样的博弈,尤其是市场经济发达的现代社会,可以说博弈无处不在, 而避免如囚徒困境这样的博弈情景也是社会效率所必须的。 如果单纯地剥夺局中人的选择权,通过”下一盘很大的棋”的方式去掉博弈选项,逃避囚徒困境, 那么局中人就可能不能完成充分博弈,利益得不到最大化。 而事实也证明, 这种方法在实践中效率不够高,因为人类社会运行这盘旗完全复杂到任何人都不能全盘掌控, 而且很容易就造成哈耶克说的”通向奴役之路”。 而法律为我们提供了另一种截然不同的思路,即仍然保持博弈,但调控收益矩阵,这样,仍然保证了合同双方的博弈选择自由。 在合同法和自由的关系的阐述上, 西方学者马克思韦伯曾经说过一段著名的话: “规范合同双方的那些法律的发展,以及在规范的框架下允许自由意志的法律的充分发展,往往被视为个人自由发展的标志[1]“。  通过对囚徒困境的解决方法和韦伯的这句话,应该不难理解为什么市场经济发达的国家恰好就法律制度健全,且恰好有较多的个人自由。

—-

[1] 这个自由具体来说叫做 Freedom of Contract, 有兴趣的读者可以阅读  “Max Weber on Law in Economy and Society”

松鼠会最近有篇文章, 叫做从庄家不输钱谈起, 用概率论的知识解释了庄家为什么不输钱. 作者的解释是和庄家玩, 庄家的数学期望总是正的, 赌钱的人的数学期望总是负的, 所以总是庄家赚钱. 其实这个解释是不准确的.

如果赌博仅仅是一个人和一个庄家之间的零和博弈的话(你的赢就是庄家的输, 反之一样), 那么, 去赌钱的人, 就没有所谓的技术差异了, 反正都是死. 事实上, 赌博, 比如赌球, 赌扑克这些, 高手和新手差距是很大的. 这也就是说, 如果我们把赌博看成是庄家和玩家之间的概率游戏的话, 高手和新手的获胜概率还不大一样, 这样, 用数学期望就解释不通了, 因为庄家在不出老千的情况下, 是没法让高手的数学期望为负数的, 这样, 庄家只对新手有正的数学期望, 而这个, 是和我们观察矛盾的, 庄家其实不管你来赌钱的是谁都是赢钱的, 这是和赌博的人是不是高手一点关系没有的.

要解释这个现象, 最核心的是要承认一点: 庄家其实不是直接和玩家赌钱的. 庄家乃是让玩家之间赌钱, 自己通过巧妙的方法赚钱. 我简要介绍这些方法中非常巧妙的, 也是和金融息息相关的一个手段, 叫做对冲.

我们以赌马为例. 假设有两匹马 A 和 B, 第一匹马赢得概率是 0.6, 第二匹是 0.4, 有两个赌徒, 第一个买A赢, 第二个买B赢, 来说, 两人如果不带庄家面对面各自下注的话, 假设第一个人出 x 元, 第二个人出 y 元(单位都是美元, 下同). 则第一个人赢的钱的期望是 0.6*y – 0.4*x, 第二个是 0.4*x – 0.6y. 很自然的, 如果要游戏公平的话, 两个人中, x 应该取 60, y 取 40. 这样, 两个人赢钱的数学期望都是 0, 这是对两个人都公平的游戏.

这时候, 庄家出现了, 这两个人, 现在都向庄家买马. 庄家想要赚钱, 最重要的一条就是旱涝保收. 所谓的旱涝保收, 就是说, 不管A, B 两匹马怎么跑, 庄家总能赚钱. 怎么做呢, 这就是庄家牛B 的地方了.

我们假设A 马和 B 马上, 各自共有 100 块钱 和 200块钱的赌注. 那么, 庄家一共收到了 300 块钱的赌注.  自然的, 庄家想自己抽水2成, 剩下的 240 块钱作为奖金回报给赌徒. 如果 A 赢了, 对于买 A 马赢了的人, 庄家就给你240块. 同样, 买B的也一样. 请注意, 这时候, 庄家不关心 A 还是 B 赢的概率的, 这就是关键.

那么, 为什么有人赌呢, 因为对于投 A 赢的人来说, A 赢了, 他能赢 140 块钱; 对于 B 来说, B 赢了, 他能得到 40 块钱. 那么, 对于投 A 的来说, 只要在他心目中, A 赢的概率超过 5/12, 他就愿意赌博 (他得到的钱的期望是  0 + 5/12 * 240 = 100 = 他的投资), 因为他赢钱的数学期望超过他的投资了.  对于下注到 B 的赌徒也是, 在他们心目中, 只要 B 赢的概率超过 10/12 了, 他就愿意了 (期望 = 0 + 10/12 * 240 = 200).  庄家定出的这个回报, 对于买 A, 就是投 100 最后还返还 140, 所以有叫做 1 赔 1.4; 同样, 对于 B, 叫做 1 赔 0.4. 这就是赔率的通俗定义.

可以看到, 庄家加入之前, 两个人赌钱的时候, 一匹马能赢的概率, 是一个变量, 这个量, 由两个玩家之间的协商. 而庄家来了之后,  一匹马能不能赢, 就看赔率. 不同的赔率其实对应了不同的概率. 至于您相信哪种概率, 就是你自己的事情了.  所以, 你完全不觉得自己的数学期望是小于0的. 事实上, 你总认为你猜的概率是真实的概率, 继而相信自己下注的数学期望大于0, 这时候,  您才会去充满自信的赌球的.

可是上面说的这些, 需要一个前提, 就是庄家知道投A 和投B 的人的比例. 否则的话, 庄家就有可能赔钱. 比方说, 庄家开出了 A 1 赔 1.4, 结果来了一个大玩家, 一下子买了1000美元的 A. 这时候, 赌资总共是 1300 美元. 这 1300 美元, 庄家可就不一定稳赚了, 因为假如 A 赢了, A 上的赌资一共是 1100 美元, 庄家就要赔 1100*1.4  > 1540 美元. 而庄家一共才收了 1300 美元的赌资.

庄家是资本家, 不是赌马专家, 他不会仔细研究 A 赢的概率(其实也会, 但是不会依赖于这个概率, 我下面有讲), 看看自己以多大的概率输掉这个 1540 美元, 而是立即采取补救措施, 消解自己的风险, 这个风险消解, 就叫做对冲. 没错, 就是对冲基金的那个对冲.

一般来说, 庄家有两种做法. 第一种是调整赔率法. 庄家赔钱的本质, 是因为 B 上现在没有足够的赌注, 来补偿 A 上的赔率. 那么, 庄家就调整 A 的赔率, 让 A 赔的少一点, B 多一点. 这样, 这个杠杆就会向 B 倾斜. (对于已经买了的, 赔率照旧, 这个只对新的玩家有效). 这样, 庄家就能利用这个杠杆, 让自己的风险得到对冲. 庄家也能拒绝那个买 1000 美元 A 的大玩家, 这样让整个赌注的比例得到控制.  但是这些方法不能搞太多的, 因为一个博彩公司老是调节赔率, 或者老是拒绝客户, 这个博彩公司就离倒台不远了.

所以, 博彩公司采用另外一种方法: 自己也买. 比如, 博彩公司知道 A 上面赌注太多了, 赔率又太高, 一旦 A 赢了, 自己要把内裤的输掉的, 所以, 他也跑到市场上, 找到另外一下博彩公司, 也买A. 一般来说, 博彩公司之间的赔率相差不大. 这样, 就算 A 赢了, 博彩公司也不怕, 因为他可以从别人博彩公司赚一笔, 对冲掉自己为了 A 要付出的风险.

正是因为博彩公司采用了其实更加复杂的赔率的计算方法和巧妙的对冲方法, 才能保证赚钱. 不过, 要搞这两个, 一要有很多现金随时调动, 二要很准确的初始赔率的设置(需要赌马专家和数学家一起估计), 所以, 在美剧里面, 不是大资本家和数学家在搞, 就是犯罪分子绑架数学家在搞.

总之, 庄家赢钱, 不是简单的数学期望结果, 而是复杂的赔率方法和巧妙的对冲操作的结果.

最近在看 <Advice for a Young Investigator> 看得我是心潮澎湃. 以前不注意自己有很多做科研的坏毛病, 甚至是心理上的缺陷, 都被人家一针见血的说出来. 说实话真是后背发凉的在看. 这书得看几十遍才能领会大义, 所以一时半会儿写不出书评.

既然写不出书评, 我就八卦吧. 因为我刚看完了书上说的”科学家的家庭对科研有很大的作用” 这一段, 觉得说的有道理, 因此八卦一下 (其实书中比我这里八卦的更加有道理的内容更多). 请注意以下所有观点都是原书的, 不代表我个人观点. 原书作者是西班牙人, 而西班牙在当时是欧洲一个科学和经济都不发达的弱国.

1. 在寻找另一半前, 科学家要清醒的认识到自己性格上的缺陷(比如内向, 没空照料家庭, 等等), 并且, 坚决不让别人帮自己选择生活的另一半, 而是自己寻找. 在选择伴侣上, 要选择那些性格上与和科学家的性格兼容的, 而不是有钱财和容貌的; 要选择一个属于自己的伴侣, 而不简单的只是一个伴侣, 因为有的伴侣能够让科学家一路顺利, 也有的伴侣能成为科学家的累赘.

2. 一般来说, 科学家偏好中产阶级的女性, 也最好找中产阶级的女性. 在这个层次, 有四种女性可以选择: 知识女性, 富有的女性, 艺术家, 职业女性.

3. 知识女性 (作者指有知识和受过高等教育的, 以和知识打交道为职业的女性) 一般来说选择自然科学或者人文科学作为她们的职业. 这是一类美好的人生伴侣. 但是不幸的是, 这样的女性在西班牙是稀有物种. 相比而言, 在国外(作者指西班牙以外的欧洲发达国家), 这样的女性很多, 原因是国外的经济和教育更加发达. 这样的女性一般能够成为科学家科研的好助手, 或者给予科学家信心和爱.

3. 富婆类型的. 这类在英国和法国很多, 但是在西班牙很少. 不过她们一般很少会资助科学家. 她们的生活是安逸, 豪华和排场. 而且她们会想: 我们已经有美好生活了, 为什么你不享受而是天天呆在实验室呢? 同时, 科学家也不能提供她们需要的豪华生活, 如果科学家为了女人的豪华的珠宝和漂亮的衣服工作, 那么追求科学就不再是一种思维的享受, 而是一种人生的双重折磨.

4. 艺术家或者文学女青年(用现代话讲, 就是小资女). 这样的女性, 很少例外的, 会给科学家的生活带来无尽的烦恼. 她们一般是以展示她们自己的能力, 才华等为生活状态的; 而且她们一和男人一起生活, 她们的魅力就消失了. 科学家的生活往往在于幕后,而她们会喜欢幕前. 小资女会叫得出每一样名牌化妆品和宝石店的每一样商品, 但是却不是学术书籍和学术杂志的好朋友.

5. 所以, 身体和心理都健康的职业女性成了科学家的最后一种选择. 她们比较务实, 而且性格良好, 所受到的教育程度也使得她们能够理解和支持科学家的工作. 家庭生活也因此变得和谐. 这样的女性在中产阶级中很多. 如果一个科学家很不幸的一个这样的伴侣都找不到, 那就是命不好了.

这些道理在原书里面都有详细的展开, 我这里说的八卦, 只是作者大师顺带写的一点不重要的内容罢了, 这本书里面更加有其他的内容才是重点, 我推荐每一位想成为科学家的人阅读.

部分内容试读可参见 非常牛逼,相当见血

(过新年了, 找到了以前写的一篇没发出来的旧文章, 算作一篇贺岁吧)

最近日本著名演员饭岛老师去世了. 在我这个年龄段的人中, 熟悉饭岛老师的相信十有八九都是通过奇妙的叫做 bt 或者 电驴 的软件认识的. 今天我们就来八卦一下程序设计人员是如何设计这些客户端的策略使得您既能下载欣赏到饭岛老师的片子, 又不会浪费您太多的上传带宽的. 简单的说, 就是 P2P 软件的客户端的策略该如何设计, 使得整个系统能够帮助每个用户获得相应的利益最大化.

要研究这个问题, 我们得从博弈论谈起. 但是因为这个是给程序员看的八卦, 不是数学专业课, 我们不在这里说太多的数学, 而是用例子和八卦引入.

大家都知道, 1994 年的诺贝尔经济学奖给了一个数学家, 约翰.纳什 (电影”美丽心灵”为证). 纳什的理论工作是推广了冯诺伊曼开创的极大极小定理(博弈论的基本定理). 而在通俗的对博弈论的介绍中, 提到纳什, 一般都是着重在纳什均衡和囚徒困境上. 我们不具体深究纳什均衡的数学意义, 而是以下面一个具体的极其简化的例子来说明囚徒困境:

假设 BT 网络中两个节点 阿强(A) 和 B哥(B) 要交换文件. 文件很大, 我们假设需要非常多轮交换才能完成. 每一轮, 每个节点可以选择 平衡上传/下载 和 几乎不上传/贪婪下载两组策略. 我们按照博弈论的一般用语, 把第一种策略称为 C(合作), 第二种称为 D(叛变). 同时, 假设A, B 都是使用 ADSL 网络, 所以上传成本比下载成本要高很多, 我们在计算回报的时候考虑这样的不对称. 现在, 假设 A 和 B 各自有对方需要的文件, 那么, 如果 A, B 同时选择策略 C, 即平衡的上传和下载, 他们得到的回报都是 3, 如果其中一个人偷鸡选择 D, 即几乎不上传, 光下载; 而另一个节点选择 C, 则选择 D 的能够下载到所要的文件且几乎不需要付出上传的代价, 我们记回报为 5, 而另一个人付出了上传的费用, 却得到了一点点的下载, 可以把回报看成是0. 如果两个人都选择贪婪下载, 几乎不上传, 那么两个人都得到了一点点下载, 现在这样的下载量没有3多, 但是因为本身付出的上传成本也少, 我们把这时候两者的回报都定为 1.

说了这么多, 只是为了让问题更加的真实. 这些交代的条件的数学本质, 可用表格表示, 博弈论中称之为支付矩阵:

C D
C (3,3) (0, 5)
D (5,0) (1, 1)

现在的问题是, 阿强和B哥都是理性的, 也是自私的, 因此, 他们都认为, “假如我选 C, 对方可能选 C 或者 D, 那么我这个策略最糟糕的情况下收益是 0, 而假如我选 D, 最糟糕的情况下收益是 1″ 那么, 因为 D 下最糟糕的收益比 C 最糟糕的情况下收益要大, 理智的人肯定选D. 我们看到, 两者选择 D 都是理性的, 但是实际上从对两者的收益分析看, 两者都选择 C 才是更加优的. 这个表面上看上去很理智但是最后没有到达对双方最好的结果的困境, 就是所谓的囚徒困境. (看过这篇八卦, 您也可以叫做饭岛老师困境)

关于囚徒/饭岛困境的简单介绍就到这里, 现在我们看我们的原始问题. 我们知道, BT 交换文件是分成一块一块的, 也就是说, 是一次一次的交换的. 我们把每次交换叫做一轮的话, 整个系统是一个多轮的博弈问题(或者叫做多阶段的博弈问题). 这个博弈问题, 就显得好玩起来了. 为什么呢, 因为多阶段博弈, 居然能够让自私的A和B两个节点为了自己的利益, 进化出合作来.

我们先简单的说明一下多阶段博弈不必然的能跳出囚徒困境. 比方说, 如果 A 和 B 知道一共有 N 轮博弈, 那么最后一轮, 理智的他们肯定都陷入了囚徒困境, 在第 N 轮 的策略清楚之后, N 的问题就转化为 N-1 轮的问题. 所以, 必然的, A 和 B 在所有 N 轮上, 都会陷入囚徒困境 (好比奸商一辈子只和你做有限次买卖的话, 就会一直黑你, 不黑白不黑). 他们等到花儿也谢了, 也不能得到自己想要的内容. 但是, 问题的奥妙在于, 假如A 和 B 不知道一共多少轮, 或者有无限轮呢? 假如阿强在某轮选择平衡的上传和下载(C), 则可能正好碰上 B 哥 也选择”友好合作”, 那么, 两个人都舒舒服服的交换了饭岛老师的片片. 所以, 对于一个设计良好的BT客户端, 问题的关键在于怎么选择自己的策略, 使得既能完成自己自私的下片目标, 又能注意和其他客户端良好的合作使得自己的收益最大, 而不在于在特定的一轮中自己的得失.

这里, 我们的目标是设计一个良好的策略. 通常, 在设计一个实践中性能良好的算法的时候, 数学家和计算机科学家在这里的方法就鲜明的分野了. 数学家, 会证明这样算法的存在性, 性能上下界, 和众多的必要条件, 以及算法之间在最理想的情况下的好坏比较. 而计算机科学家, 会像搭积木一样, 用不同的基本模块, 直接尝试不同的组合, 一一做实验, 看哪种方法最好. 在这里, 我仅介绍一种计算机科学家的方法: 通过让不同方法比赛, 取出赢家, 赢家的方法最好的方法. 其实准确的说, 这个就是达尔文的适者生存的方法. 而这个比赛本身又是一段非常有趣的八卦, 因此我着重花笔墨介绍一下.

在心理学和行为学领域, 有一本非常著名的书, 叫做<合作的进化>. 其作者, 记载了在80年代, 他组织的两次比赛, 叫做IPD (Iterative Prisoner’s Dilemma, 多轮囚徒困境). 竞赛的目的是在一个多轮的囚徒困境中找出最好的策略, 参赛者自己写好算法程序, 然后由组织者让这些程序两两对弈, 看谁在多轮囚徒困境中得到最多的分. 在所有的数学家计算机科学家等提交的很多程序中, 表现最好的一个策略, 超乎寻常的只有四行简单的 Basic 程序. 这四行 Basic 程序, 勾勒出了一个叫做 “针锋相对” 的算法(Tit for Tat).  这个算法策略很简单, 一开始采用合作, 假如对方上一轮合作, 则本轮合作. 如果对方上一轮对抗, 则本轮对抗. 用中国人熟悉的话说, 叫做”人不犯我, 我不犯人; 人若犯我, 我必犯人”. (四句话正好对应四行程序, 不是巧合). 其他的算法, 比如随机算法呀, 永远敌对的算法呀, 都比不过这个算法. 因此, 这个算法赢得了第一年的竞赛.

第二次, 各位吸取教训, 继续开发好算法. 猜猜第二次谁赢了? 居然还是那四行程序! 在合作的进化中, 作者从”宽容, 以牙还牙”等社会学的角度去解释为啥这四行程序会赢. 或许对人生有深刻思考的人会感叹, 这四行程序的确蕴含了深刻的智慧. 但是, 很不幸的是, 这个程序在现实中, 有一个非常大的漏洞, 而因为这个漏洞, 使得BT程序如果不修改策略, 先现实中会寸步难行. 这个看上去非常理智非常聪明的策略到底是怎样的大漏洞呢, 我先卖个关子, 下回分解.

(想看剧透的, 可以看 Wikipedia 的条目: Tit for Tat: http://en.wikipedia.org/wiki/Tit_for_Tat )

新年快乐!

和世界上大多数国际机场一样, 美国夏威夷国际机场非常大. 为了方便旅客在航站之间转运, 航站之间用巴士提供交通服务. 在夏威夷, 他们用本地人的语言把这种巴士命名为 wiki wiki, 意思是”很快”. 因为在本地人的语言里面, wiki 是”快”的意思. 

1995 年的时候, “极限编程”方法论大牛, Ward Cunningham, 觉得应该建立一个公共的网站, 让人能够输入一个 Pattern 的名字, 就能查阅到一个 Design Pattern 的用法, 而且这个网站还能被人编辑, 实现知识共享. 从此, 世界上第一个 wiki 网站就建立起来了, 他把它的东西叫做 WikiWikiWeb, 意思就是”快速查阅的网站”. 这时候 wiki 还只是在程序员之间流行, 直到 2001 年, 一个叫 Jimmy Wales 的, 创建了 Wikipedia, 从此, 才算是普及了. Wiki 和 Wikipedia 彻底改变了我们的生活. 试想, 人类协作创造了一本共享智慧的, 随时可访问(中国大陆和朝鲜除外)的百科全书, 是多么值得荣耀的伟大成就! 

且慢, 以前人类难道没有百科全书么? 有, 几乎每个像样的图书馆都有大英百科全书, 为什么这些百科全书没有如此大的改变我们的信息获取方式呢? 沿着同样的逻辑链条, 我们可以问更多的问题: 在没有 Google 之前, 似乎搜索引擎也有, 但这个东西我们很少用, 也很少听说, 为什么就是 Google 一出现, 就彻底改变了我们的检索方式呢? 

问题的答案很多, 我说我的答案: 很多事情, 只有在人能很快的完成的时候, 才有了做的可能. 这句话可能比较拗口, 反过来说可能更加好懂: 如果用某种方法做一件事情太耗时间了, 那么人就不可能用这个方法做事情. 只有一个方法能够让人足够快的做好事情的时候, 这个方法才会变得实用, 同时这个事情才有做的可能性. 

为避免过于抽象, 我们仍然用例子说明. 美国宪法规定要10年做一次人口普查, 但是直到 1890 年, 美国才进行了历史上第一次完整的全国人口普查. 传统上, 人口普查的数据提取上来, 要花多于10年的时间才能处理完, 因此, 人口普查从来就做不完. 直到1890年左右, IBM 公司发明打孔卡片, 卖给了美国人口统计局, 美国人口统计局采用了打孔卡片作为报表, 从此才能在2年内做完一次人口普查统计. 打孔卡片比人填表统计快多少呢, 也就快5倍而已. 但是就这个5倍, 把原本不可能做到的全国人口普查变成了可能. 

天气预报也是很好的例子. 天气预报的原理是解一个数值偏微分方程, 这个道理科学家在1922年就知道了. 但在计算机没出现前, 是没有天气预报员这个职业的. 直到1955年, 在电子计算机的帮助下, 天气预报才变成了现实. 那么, 1955 年的电子比1922年的机械式计算机快了多少倍呢? 也就1000倍. 另外有一个未经证实传说说, 以前预报24小时内的天气预报需要计算机计算25小时, 直到更快的计算机出现, 才使得2小时之内可以算出24小时的天气预报, 使得天气预报实用化. 这个, 也就是10倍的更新. 

快工具和慢工具的差别, 带来了一件事情可做与不可做的差别. 其实不光是表面上速度的改变, 对应内里是整个方法体系的本质改变才是关键. 比如, 在 UNIX 下数一个文档有几个a开头的词是很简单的事情, 只需要知道正则表达式和管道就行了. 在没有正则表达式和管道的环境里, 这个事情就比较难 (或者有更加好的方法我不知道?). 当然, 这事也可以做, 只是慢了10倍而已. 同理, 从纽约到华盛顿步行也能到, 就是慢了一点而已. 而汽车让从纽约到华盛顿变成了一件很平常的事情, 其实小汽车也就比步行快了不到20倍而已. 到图书馆查百科全书也是一种获取资料方式, 在网上 Google 也是一种方式, 后者(一分钟)比起前者(一小时), 也就快了10倍到100倍而已. 可不同的仅仅是速度么? 正则表达式提供了新的描述角度; 汽车是一种新的不耗费体力的快速交通工具; Google 是一种新的获取信息的手段, 这些速度的表面差异, 对应的内里, 是本质差异. 虽然改变的是速度, 却不仅仅是速度. 甚至, 我们可以大胆的断定, 如果没有本质的内里的变化, 速度也不可能有10倍的提升. 

我们都知道, 做事情要高效, 要 WikiWiki. WikiWiki,  是每一个想要管理好时间的人的圣杯, 是每一个想多做点事情的人的魔咒; 可是很显然, 平凡的工具, 至多越用越熟; 即使用到烂熟, 也不能带来本质的效率提升的; 一成不变的思想, 最多用到极致, 形成一个自我体系, 但跳出体系外, 是不能带来崭新的角度和本质的提升的. 特别的, 是在计算机科学以及计算机编程领域, 快工具和新思想层出不穷. 依我的观察, 在计算机科学的发展史中, 每一个时代都有很多新思想涌现, 带来的是革命性的思维方法和崭新的理论实践, 以及快好几个数量级的效率提升; 在在编程方面, 我们大多数人也见识了 UNIX 管道哲学, 和函数式编程的哲学对效率的提升.  这些新思想, 好工具, 是我们计算机科学领域最好的珠玑, 也是在大海边玩耍的孩子不可错过的晶亮的贝壳. 

那么, 心急的读者要问了, 到底哪些是晶亮的贝壳和藏着的珠玑呢? 别急, 我会把我见到的认为是晶亮的贝壳和珠玑的好东西记录在这里, 所以, 请继续关注我这个系列的后续文章 :) 

最后附送几个不算八卦的八卦, 算是本文花絮: 

1. 本文中间那句拗口的中文是翻译自 Software Tools 中的一句: < Many jobs will not get done at all unless they can be done quickly.> 里面还有 “We consider people cost a great deal more than machines, and the disparity will increase in the future” 以及 “The extra freedom permitted by got’s is just what you don’t want” 等道理深刻的话语.  有时候我真的怀疑, Software Tools 是一本讲哲学的书, 而不是一本编程书. 

2. Wiki 最早的思想来自于苹果机上的 hypertalk. 这个软件相当于是个人多媒体 Wikipedia. 苹果的 Applescript 自然语言编程的语法, 也是借鉴的这个软件的语言, 叫做 hypertalk. 这个软件称得上是个人计算机的 killer app, 但是不幸被苹果收购之后就中断开发了.  Steve Jobs 这家伙很没文化, 收购并扼杀了很多苹果上的经典软件, 这些故事等以后有空细说. 

3. 关于汽车之比人快10倍, 但是本质上改变了人的生活的例子是借用的 Knuth 的, 具体可见 <Mathematics and Computer Science: Coping with Finiteness>, 文章发在 1976 年的 Science. 这是一篇好文章!

4. Ward Cunningham 的网站, http://c2.com/cgi/wiki 是历史上最早的 wiki 百科, 只是全是关于计算机和编程的而已.

(没空写长的, 先写个备忘好了, 以后展开来介绍.  所有的想法都不是我的)

CLRS 第16章专门讲了贪心算法 (Greedy Algorithm) 的理论基础是拟阵 (matroid) . 具体理论就不重复废话了. 实际上更加贴切的模型叫做 Greedoid. 相关的理论看一下CLRS就好懂了. 注意 CLRS 中间讲到的所谓的带权拟阵, 实际上表明目标函数是线性的 (函数值 F(A) 等于集合A中每个元素权值之和). Edmonds 1970 早在70年代一篇没有摘要的装逼论文中就证明了拟阵结构上对线性函数的贪心算法一定是最优的. (http://portal.acm.org/citation.cfm?id=885912 )

实 际上应用中却不是线性的了, 而是一个叫亚模的(submodular), 具体的细节看维基百科. (http://en.wikipedia.org/wiki/Supermodular ). 亚模这个性质用通俗的话说, 就是随着加入集合的元素越多,  F 函数值获得的受益越少(效用边际递减). 显然世界的很多问题的效用函数都是这个性质. 如信息量 (Information Gain) 等其他效用函数. 这个函数在机器学习, 经济学和博弈论中用途广泛. 比如传感器的安排, Google 最优化广告词的安放, 传感器网络的优化放置, 集合覆盖问题等等. 同时亚模函数和拟阵是有紧密联系的, 如拟阵的秩(rank)的定义, 就必须是一个次模函数.

最好玩的结果是, 除非P=NP, 否则对于拟阵上的亚模函数来说, 贪心算法是多项式时间里面能完成的界最好的最大化算法. 这个就彻底打消了同志们研究新算法的热情鸟:直接用呗,反正没更好的了. 至于呀模函数的最小化, 又是一个多项式的算法. 和线性规划一样, 椭圆方法能解. 其他多项式方法阶也不高.

卡梅. MIT, UIUC 最近都有应用亚模函数做 WSN 或者图分区的文章. 有兴趣的自己去下载吧. 八卦的是, Google 关于 AdWords 最优化拍卖的论文, 一点拟阵和亚模都没扯到, 得到了同样的理论结果, 并且花了很多功夫强证上面贪心算法在界估计上最优这个结论. 不得不说, 学数学还是有点好处滴, 至少不要重新花了老半天重证一个定理鸟. 卡梅的一个团队更加豪言壮语, 说以前的机器学习全是做的啥凸函数的优化 (如 SVM ), 下个十年, 亚模函数就要统治机器学习优化领域啦.

有兴趣的各位老大随喜以下的文章.

An Introduction to Submodular Functions and Optimization. 属于简介
www.ima.umn.edu/optimization/seminar/queyranne.pdf

卡没在ICML上做的tutorial. 讲了和机器学习的联系
http://www.select.cs.cmu.edu/tutorials/submodularity-slides.pdf

Adwords Auctions with Decreasing Valuation Bids.  Google 的论文
www-static.cc.gatech.edu/grads/g/gagang/wine07_full.pdf

Revisiting the Greedy Approach to Submodular Set Function Maximization. MIT Sloan 管理学院的论文
http://www.optimization-online.org/DB_FILE/2007/08/1740.pdf

Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies.卡梅用来做传感器放置的一篇.
http://www.select.cs.cmu.edu/publications/paperdir/jmlr2008-krause-singh-guestrin.pdf

各位随喜了.我还得继续和论文做斗争.

TopLanguage 论坛上有人问为啥信息论要使用 H = -K \sum_{x \in X} p(x)\log p(x) 的形式. 或者说, 为啥要用不直观的对数.

古典的解释很简单, 对于一个有  N 种状态的事件, p 进制编码的时候, 需要的位数是  \log_p N . 也就是  - \log_p (1/N) .

这种古典方法有很多局限. 最显著的就是  N, p 必须是整数. 熵的概念既不能推广到一般概率, 也不能推广到一般的对数为底.

下面我介绍两个公理化的定义. 一个是 Shannon 的原始定义, 一个是我偶然想到的模仿 Kolmogroov 概率公理化定义一样, 关于自信息量的定义.

Shannon 在 A mathematical theory of communication 的公理化定义被很多人忽略了. 我简单的归纳一下.

0. 信源可以看成是一个 Markov 过程. 现在相信大家都知道这一点了, 比如抛硬币, 就是这样的图:

m.png

这里, 信源的熵(不确定度量)只和均衡状态下各态的到达概率有关. 而和其他量无关. 也就是说, 迥然不一样的Markov过程只要稳定状态下各态概率一样, 不确定度量也一样. 这样, 信源就抽象成了和具体工作机理无关的 Markov 信号发生器. 这个是信息论的关键前提.

1. 假设离散事件发生的概率为  p_1, p_2, \ldots, p_k . 其所含的”不确定度量”  H 是关于 p_i 的一个连续函数.

2. 假设 p_i = \frac{1}{n}. 则  H 关于  n 是增函数. 因为  n 变大, 表示可选择的更加多, 也表示“不确定度量”在增加.

3. 如果随机变量  X 的概率分布依赖于 随机变量  Y 的分布, 那么 X 的熵  H(X) 可以表示为  H(X) = \sum_{y \in Y} p(y) H(X|y)

从这三个公理出发, Shannon 证明, H = -K \sum_{x \in X} p(x)  \log p(x) 是唯一可能的信息熵的表示. 具体的证明也不难. 从因为从 3 出发可以简单推出.

假设  H(\frac{1}{n}, \ldots, \frac{1}{n}) = A(n)
则有,  A(t^{n}) = n A(t) . 按照连续函数的性质, 解一下函数方程, 可以得到  A(t) = K \log t.

我想到的公理化定义说起来也比较简单, 是依赖于自信息量的公理化定义. 基于和香农同样的假设, 一个事件的自信息量 S(X) 定义为该事件概率分布的一个连续函数.类比于 Kolmogorov 建立的概率公理体系, 自信息量是概率度量空间上的一个实度量, 满足一下几条公理:

1. 非负性. 对于任何事件 X,  S(X) \ge 0

2. 信息量的可列可加性. 即在条件概率的意义下, 以两项为例, 有,
S(X, Y) = S(X) +  S(Y|X)  = S(Y) + S(X|Y)

直观的解释是, 事件  X 与事件  Y 联合提供的信息量, 等于知道  X 的信息量加上知道  X  Y 提供的信息量.

根据公理2, 很简单可以得出独立同分布事件  X ,  Y 联合信息量  S(X, Y) = S(Y) + S(X) . 根据这个可以推导出两个结论, 一是概率为 1 的事件的信息量必然为 0. 二是因为独立分布事件的概率是两个概率相乘. 令  t_x = p(X), t_Y = p(Y) , 则有  f(t_x * t_y) = f(t_x) + f(t_y), 此函数方程的解为  k \log t . 其中 t 是概率,  \alpha 是任意常数. 根据1 可知,  \alpha 必须取负数. 因此, 令  k = - \alpha , 得自信息量公式  - K \log p . 与古典结果一致.

在自信息量的定义之上, 熵就是很显然的了. 事实上, 熵就是系统各状态自信息量的数学期望, 即:

H = -K \sum_{x \in X} p(x) \log p(x)

公理化定义的好处是, 整个信息论建立在了现代数学的磐石之上, 并且能与其他数学领域相结合. 信息论诞生以后, 到最近, 都一直受到数学家的重视. 在关于下一代移动通讯网络 (4G)* 的研究中, 非常纯数学非常抽象的代数数论和代数几何, 居然和信息论相结合, 产生了令人惊讶的代数几何码, MIMO 空时码等先进的编码技术. 编码理论和代数结构相结合, 不光在实际上产生了效果好的应用, 而且在理论上也出人意料, 建立了不同学科之间的深刻联系. 信息论早就已经超出了一个工程分支的范畴, 成了非常新, 非常有活力的一个数学练兵场. 有兴趣致力这方面研究的可以阅读几篇 IEEE Transaction on IT 上面的一些经典文章.

延伸材料:

1. A Mathematical Theory of Communication by Claude E. Shannon (http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html)

2. Wikipedia Article: “Entropy in thermodynamics and information theory” (http://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_information_theory)

* 3G (第三代移动通信) 的编码, 据我有限的知识, 一般是基于 Turbo 码这样一个随机的编码方式. 关于这个编码有一段非常有趣且有启示的故事: http://jcst.ict.ac.cn/downloads/xsqy/qy1503.pdf

Ipopt is a leading nonlinear optimization tool. There are a bunch of interfaces, e.g. C/C++ standard interfaces, Java and MATLAB interface, FORTRAN interface for programmers.  However, no existing interface to python was presented. I started to connect ipopt with python two months ago inspired by OpenOpt. After lots of extensive development and nasty testing,  today, I proudly announce that the python interface of ipopt, aka, pyipopt, version alpha, is ready to go.

With the help of this module, in python, you can just use

import pyipopt
nlp = pyipopt.create(n, xl, xu, m, gl, gu, nnzj, nnzh, f, gradf, g, gradg, h, apply_new)
solution = nlp.solve(x0)

to get your NLP problem which n variables (xl, xu are boundaries for variables), m constraints (gl, gu are boundaries for constraints), and objective function f (gradf is the gradient, h is the Hessian matrix) with constraints g (gradg is the Jacobian value) optimized by IPOPT.

The package is available via google code: http://code.google.com/p/pyipopt/   An OpenOpt hooker is under development.

The code has BSD license. you can use this module whatever you want. For bug report and other related things, reach me at youxu AT wustl.edu.

To write a  package is not rocket science, but it might save you some time in your research.

[Special thanks to Dmitrey Kroshko from OpenOpt and Scipy community; Dominique Orban from Nlpy community]