Blog

数学之美番外篇:平凡而又神奇的贝叶斯方法

概率论只不过是把常识用数学公式表达了出来。 ——拉普拉斯 记得读本科的时候,最喜欢到城里的计算机书店里面去闲逛,一逛就是好几个小时;有一次,在书店看到一本书,名叫贝叶斯方法。当时数学系的课程还没有学到概率统计。我心想,一个方法能够专门写出一本书来,肯定很牛逼。后来,我发现当初的那个朴素归纳推理成立了——这果然是个牛逼的方法。 ——题记 这是一篇关于贝叶斯方法的科普文,我会尽量少用公式,多用平白的语言叙述,多举实际例子。更严格的公式和计算我会在相应的地方注明参考资料。贝叶斯方法被证明是非常 general 且强大的推理框架,文中你会看到很多有趣的应用。

数学之美番外篇:快排为什么那样快

知道这个理论是在TopLanguage上的一次讨论,先是g9转了David MacKay的一篇文章,然后引发了牛人们的一场关于信息论的讨论。Anyway,正如g9很久以前在Blog里面所说的: 有时无知是福。俺看到一点新鲜的科普也能觉得造化神奇。刚才读Gerald Jay Sussman(SICP作者)的文章,Building Robust Systems – an essay,竟然心如小鹿乱撞,手心湿润,仿佛第一次握住初恋情人温柔的手。 而看到MacKay的这篇文章我也有这种感觉——以前模糊的东西忽然有了深刻的解释,一切顿时变得明白无比。原来看问题的角度或层面能够带来这么大的变化。再一次印证了越是深刻的原理往往越是简单和强大。所以说,土鳖也有土鳖的幸福:P 这篇文章相当于MacKay原文的白话文版。MacKay在原文中用到了信息论的知识,后者在我看来并不是必须的,尽管计算的时候方便,但与本质无关。所以我用大白话解释了一通。

数学之美番外篇:进化论中的概率论

偶然性在进化中确实存在(例如,偶然性的突变可以产生新的特征),但是进化并不依赖偶然性来产生新的器官、蛋白质或其他实体。截然相反的是,自然选择,作为进化中已知的最主要机制,却会明确保留“需要的”(能适应的)特性,消除“不需要的”(无法适应的)特性。只要选择的影响力存在,自然选择就能把进化向一个方向推进,在出乎意料的短时间内产生复杂的结构。举个例子,现有由13个字母构成的序列“TOBEORNOTTOBE”,假设有几百万只猴子,每只猴子每秒钟挑一条短语,需要78,800年才能从26^13种可能中选出这样的排列。不过,Glendale College的Richard Hardison在20世纪80年代写过一个程序,它能够在随机产生序列的同时,保证那些已经出现在正确位置上的字母不会变化(这样做倒有点《汉姆雷特》 的味道。译注:这个句子看了大半天才明白,嘿嘿)。这个程序平均只需要336次迭代就能生成上文提到的短语,时间少于90秒。更神奇的是,把莎士比亚的整个剧本重新生成一遍也只需要四天半时间。

康托尔、哥德尔、图灵——永恒的金色对角线(rev#2)

哥德尔的不完备性定理震撼了20世纪数学界的天空,其数学意义颠覆了希尔伯特的形式化数学的宏伟计划,其哲学意义直到21世纪的今天仍然不断被延伸到各个自然学科,深刻影响着人们的思维。图灵为了解决希尔伯特著名的第十问题而提出有效计算模型,进而作出了可计算理论和现代计算机的奠基性工作,著名的停机问题给出了机械计算模型的能力极限,其深刻的意义和漂亮的证明使它成为可计算理论中的标志性定理之一。丘齐,跟图灵同时代的天才,则从另一个抽象角度提出了lambda算子的思想,与图灵机抽象的倾向于硬件性不同,丘齐的lambda算子理论是从数学的角度进行抽象,不关心运算的机械过程而只关心运算的抽象性质,只用最简洁的几条公理便建立起了与图灵机完全等价的计算模型,其体现出来的数学抽象美开出了函数式编程语言这朵奇葩,Lisp、Scheme、Haskell… 这些以抽象性和简洁美为特点的语言至今仍然活跃在计算机科学界,虽然由于其本质上源于lambda算子理论的抽象方式不符合人的思维习惯从而注定无法成为主流的编程语言,然而这仍然无法妨碍它们成为编程理论乃至计算机学科的最佳教本。而诞生于函数式编程语言的神奇的Y combinator至今仍然让人们陷入深沉的震撼和反思当中…