Posts archived in aerospace

对航空感兴趣的人都知道,美国自取消阿波罗登月计划之后,其空间探索的主要精力,都放在了航天飞机主导的太空任务和国际空间站上。 和中国,俄罗斯的宇宙飞船不一样的地方在于,航天飞机是一种可以重复飞行的飞行器。

美国和前苏联都设计过航天飞机。他们设计的初衷都是一样: 航天器重复飞行能够降低制造和设计成本。 美国成功的做出了7艘航天飞机,而前苏联的航天飞机计划从来没成功的进入空间轨道过。 NASA 虽然成功的做出了航天飞机,限于当时的科学技术和认识的缺陷,还是没有避免一些致命的设计缺陷。 挑战者号和哥伦比亚号的事故都集中体现了这些设计缺陷。

Space shuttle Endeavor (Source: NASA)

航天飞机在发射时候,是将一个飞机状的东西(最后进入轨道并返回的飞行器,也叫轨道飞行器)挂载在一个巨大的土黄色的液氢/液氧燃料仓上。这个燃料仓旁边,又绑上了两个固体火箭增加推力。 发射后,固体火箭会掉入海中被回收,而巨大的土黄色燃料仓会坠入大气层烧毁。 不需要懂太多火箭知识就知道, 这等于是把航天飞机挂在一个火药桶上起飞,而且发射一旦出现什么问题,载有宇航员的轨道飞行器不能与燃料仓分离,固态火箭的使用更加使得火箭变得不可控(液态燃料可以随时关闭,固态燃料一点燃就没法熄灭) 。 这样,一旦火箭有了问题,爆炸和机毁人亡全都无法避免。挑战者号的事故就正好反映了这些设计缺陷。

同时,航天飞机使用表面瓷砖隔热,这些瓷砖在飞出和重返大气层的时候会被烧灼,可能会被损坏,所以航天飞机每次起飞都要重新装修一次,而且一旦在起飞的时候损坏,重返的时候就是听天由命了。哥伦比亚号航天飞机就是这样的事故。 航天飞机从设计到现在已经近30年了,因为当年使用的技术老旧,NASA 不得不养着一帮工程师来支撑航天飞机的飞行和维护。这些团队,不管航天飞机在天上还是在地下,都是要拿工资的。 于是,算下来,航天飞机的发射总成本,居然比发射一枚不回收的火箭还要高。

航天飞机有这么多的问题,是必然要退役的。这一点在哥伦比亚号事故后就变得尤其清晰。但是迄今为止,除了航天飞机和俄罗斯的大火箭,人类还没有其他方法把超过20顿的有效载荷送上 LEO (地球低轨轨道)的能力。而俄罗斯的火箭的载荷还是太小,送人没问题,送哈勃天文望远镜这样的大东西就要靠N次输送,对接和太空行走装配才能完成。之所以要巨大的火箭,因为克服地球重力井所需要的推力是如此之大。所以不管是登月也好,维护国际空间站也好,未来去火星探索也好,只要想让足够的东西逃离地球的引力,都离不开一个东西: 大推力火箭。 而美国除了航天飞机,居然就没有大推力火箭(送阿波罗登月的土星五号早就退役几十年了,当年的那些工程师都找不着了)。

小布什做总统的时候,带着和其他国家太空竞赛的意思,提出了 2020 年重返月球的计划。航天飞机自然不是送人和设备去月球的选择,于是,NASA 顺着登月的思路,提出了星座 (Constellation) 计划。 整个星座计划的总思路,是研发两枚大推力火箭,分开执行送人和送设备上天的任务,再将人和设备在月球轨道上对接。总所周知,在美国,人的生命是最重要的,因此载人的那枚火箭侧重于安全性,而载物的那枚火箭则侧重于大推力,和土星5号一样,有粗大的身材(见下图,胖的火箭旁边绑了两个固体的推进器,而瘦的火箭则完全是安全的液体推进,且有逃逸装置)。

Constellation Project (Source: NASA)

在我看来,星座计划是一个先天不足,又完全没什么创新的计划。首先,NASA 根本没有那么多钱来烧两枚火箭的研发。何况,月球美国已经去过好几次了,再去也是挖土。 最为关键的是,Bush 的星座计划里,居然要求 NASA 最大程度的重用原来阿波罗计划和航天飞机的技术和知识。 这就把一个本来可以做出革命性技术的项目,变成了重复一次阿波罗计划的项目,这样就完全失去了技术转化和民用化的巨大前景。 本来美国政府就已经是赤字累累了,再烧这个钱,完全没理由没价值。事实也的确如此,在布什任期,NASA 并没有在星座计划上按照时间表研发出对应的火箭技术,也没有看到什么革新的技术用在星座计划上。

Obama 总统上台后,委托一个由航空专家组成的小组对美国下一代空间探测计划做了一个总的评测。这个委员会对星座计划的意见是:工期拖沓,超过预算,没什么创新。于是,Obama 政府顺着这个,在2010年一月份的时候起草了一个提案,主要的思路是放弃重返月球的计划,跳过月球直接研究火星和小行星的机器人和载人探测计划,航天飞机退役,把往国际空间站等低轨轨道送人和设备的任务交给商业化的航空公司托管,不依赖于航天飞机技术发展下一代大推力火箭。平心而论,这个计划是完全可行也有创新意识的,而且可以降低不少成本。特别是现在私人航空公司送一个人上地球低轨轨道完全不费力气,况且美国作为月球俱乐部的唯一一个成员,和中印俄日这几个国家比谁在21世纪先登月一点意思没有,不如探索太阳系内其他星球。 这一点完全秉承了二战时候美国海军攻占西太平洋时使用的蛙跳跨岛战术,跳过月球,宇宙还很广阔。

当然,一个提案要想通过,还得参众两院投票通过才行。NASA 在航天飞机和火箭研发上已经雇佣了很多人,如果将 NASA 的一些项目外包,或者不依赖于NASA 现有技术,就意味着 NASA 雇员的失业。 在美国,失业和地方经济和选票都是直接关联的。因此,这个法案自然会得到 NASA 基地所在的那些州的议员的反对。加上普通人对放弃登月,感情上完全接受不了(想想中国还计划2025年登月呢),觉得是放弃了美国在太空探索上的领头羊地位,所以这个提案直接被枪毙了。

于是,参院的部分议员修改了原来的提案,这就是昨天参院刚刚通过的提案。其中,Obama 政府做了不少的妥协,原来计划的投资给私人航天的三十多亿美元砍成了16亿,国际空间站延长服役几年,航天飞机延长服役一次(这样NASA的配套工程师不至于瞬间失业),登月计划取消,大推力火箭换个名字继续开发,准备火星和小行星的机器人和载人探测。在上篇文章里我说了,载人火星探测要想成功,没有新一代的推进技术是痴人说梦。NASA 现在没有了登月的压力,应该可以潜心开发下一代的可以让人在太阳系自由穿梭的推进技术。 到时候,人类就真的摆脱了地球的重力的限制了。

跨过月球,2030年登上火星,这就是美国下一代空间计划的大体意思。

1969 年,美国国家宇航局 (NASA)完成了人类历史上的一次创举:首次把人送上了月球。执行此任务的推进器,是由纳粹德国的著名火箭科学家,二战后加入美国国籍的冯布劳恩设计的“土星五号”火箭。

“土星五号”火箭是人类历史上最大,最高和最重的多级火箭,比已经是庞然大物的航天飞机要庞大许多。 “土星五号”之所以这么庞大,原因在于阿波罗计划需要将一个轨道舱,一个登月舱和能够让宇航员从月球轨道再返回地球轨道的燃料送到月球轨道。即使是使用液氢这样比冲 (Specific Impulse) 较大的推进剂,在发射期间,平均前进一英里,也要消耗掉两万五千磅的液氢推进剂。送上月球尚且需要如此费力,载人送上其他比月球还要远很多的行星的难度就更加难以想像了。

事实上,在火箭科学中,有一个著名的“火箭公式”,大致是说火箭在飞行过程中的速度变化,和火箭发射前后的重量的比例的对数成正比。如果想要足够快的行星际航行,火箭的飞行速度,要从发射时候的零到变到很大,才能逃逸地球的重力陷阱,进入太阳轨道;最后,又要减慢速度,才行进入其他行星轨道或者着陆。简单的数学推倒可以发现,这样大的速度变化,会导致火箭发射时候所携带的燃料和火箭的有效载荷成指数级别的关系。 不大精确的说,如果要送一个载人航天器和所需的设备,食物等在半个月之内到火星的话,我们要把波斯湾一天出产的石油全部装在火箭里做燃料才行,而这需要一个十几千米高的火箭。 所以,科学家一度认为, 仅靠喷气式引擎,人类不要说星际迷航了,在足够短的时间里飞到太阳系的其他行星都是个大问题。

其实这个问题早就有了解决的方法。 1918年苏联科学家夏格尔就提出,如果想要行星际旅行中航天器的速度加快,一个方法是让航天器掠过一个运动的行星。 因为行星本身也是运动的,航天器能够获得两倍行星速度的加速。 这就好比用一个运动的铁球去撞一个玻璃球,玻璃球能够反方向弹开,而且还能获得两倍的铁球的速度。 在这个巧妙方法的协助下,美国的水手10号探测卫星掠过金星被推送到了目的地水星,而著名的旅行家号,更是利用100多年一遇的行星排列的机会,一举掠过木星, 土星, 天王星和海王星。 现在,凡是 NASA 的行星探测器,没有一个不是通过掠过其他行星的方法获得加速到达目的地的。

如果对速度没有要求, 太阳系行星间旅行还有另一种方法,就是利用行星的合力。 如果一个人类卫星位于两个行星平面上的某些点的话(黑话讲叫三体问题的拉格朗日点), 这个卫星受到两个行星重力的合力的效果,能够让卫星处于一个相对两个行星静止的位置。因为行星本身是运动的,所以卫星完全以不消耗能量或消耗极低能量的方式在太阳系里面按照一定轨道运行。 只要精确的计算和利用这些轨道,卫星就能在太阳系里面以一种非常节能的形式从一个点滑到另一个点,当然需要的时间可能巨长无比。当然这不要紧,如果人类要建立火星或其他行星基地的话,我们可以极低的代价把大规模的物资在太阳系里运来运去。

喷气式引擎带来的第一代推进技术让人类终于可以进入近地轨道, 重力加速技术让太阳系中行星际旅行成为可能,可是如果人类需要星际间的航行,靠以上两种技术就完全不够了。 到底下一代的推进器技术是反重力引擎,还是 WarpDrive, 就等聪明的人类再发明吧。 但愿在有生之年能看到星际航行成为现实。

在以前的文章中我介绍过囚徒困境,并且介绍了 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

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