重提The Art of Computer Programming

前几日看到一位朋友的帖子里提到工作多年的人读研时需要看什么书。主要提到了三本书：

SICP： Structure and Interpretation of Computer Programs

TAOCP： The Art of Computer Programming

Computer Architecture: A Quantitative Approach

遗憾的是这三本书我都没有看过，开始怀疑自己是怎么学习计算机的了。好在第二本TAOCP我读过第一卷，但是卡在了Knuth发明的MIX。随后便未能坚持学下去。现在想来感觉有点遗憾。

今 天看到对面师弟桌子上放了TAOCP的第二卷，顿时又想起了这段往事。于是心里有个默默的计划，那就是有空时多读读这三本书，尤其是TAOCP。这绝对是 意志和耐力的考验，也是增强计算机本质水平的途径。就把这三本书的学习看成是计算机学习方面的马拉松吧。不积圭步无以至千里啊！

这里转载豆瓣上对TAOCP的两条自觉非常不错的评论：

------------------------------------------------------------------------------------

应该怎样读TAOCP http://www.douban.com/review/1319513/

　　谈谈我自己读这套书的心得。抛砖引玉。
　　首先要清楚这套书的定位：它是古典的算法分析的工具书。
　　1.古典（classic）体现在模型和问题上。
　　模型就是顺序算法（sequential algorithms）的经典模型。大名鼎鼎的MIX并非是个程序设计语言这么简单，而是一个计算模型：即标准指令集RAM。这是个非常经典，也是非常符合现实的上界（upper bounds）模型。
　　该书涉及到的问题是计算机科学诞生之初就自然面对的几个基本的算法和数据结构的问题。时至今日，这些问题还在应用中扮演着重要角色；在很多研究课题中，它们是基础或原型。
　　2.算法分析（analysis of algorithms）是此书的核心。
　 　TAOCP并没有综述算法设计（design of algorithms）的各种思想；也没有介绍证明问题下界（lower bounds）的各种技巧；也并没有对问题、模型、复杂度这些专题作出体系性的阐述。可以说，TAOCP的几乎所有的篇幅都放在了对具体算法的性能分析 上，并把这条路走到了极致。
　　3.工具书。这最有争议，因为毕竟还有习题。一些介绍也饶有趣味，不太符合大家对工具书的枯燥这一成见。
　　但把TAOCP看作工具书还是教材，这就关系到怎么去读这本书。
　 　（一）该顺着读还是跳着读：个人认为，没有哪本专业书是不能跳着读的。但前提是你对整个书的结构比较清楚，对它的内容也一定程度的熟悉。知道自己想要查 阅的部分。如果是初学者，则不建议这么作，至少还是老老实实的把第一章顺序读下来。可是TAOCP并不是给初学者看得。
　　（二）初学者适合 读TAOCP吗：不太建议。但也要看如何定义初学者——吾生而有涯，而知也无涯。一定程度上，每个人都是初学者。读 TAOCP的前提，就是自己至少比较清楚轻重缓急，可以大概判断那些是根本，那些过时，那些是炫技。这根据每个人的需要，都有各自的具体情况，但至少心里 要有点数。如果读书时觉得前路茫茫，完全不知哪里重要。那么去正经的选一门算法基础课才是更应该作的。
　　（三）MIX值得用心学吗：这要首 先清楚Knuth为什么要在这个讲算法的书里搞出个MIX。个人理解，原因有三。其一，如上所述，计算模型；其二，作者个人的审美品味；其三，用于描述算 法的语言。第一条里MIX是桥梁作用，确保数学上的严谨，同时也足以代表现实中典型的计算机体系结构。第二条是美学意义。第三条的作用等于伪码。算法用 MIX写一遍，这是为了确保上界算法在模型内的严谨性。整个书都没有用MIX模型来证明任何下界，因此除了确保严谨性，MIX没有在数学上起到实际的用 途。因此，过分钻研MIX对于理解书中算法没有太多帮助。但如果纯粹只是个人兴趣则另说。
　　（四）习题该怎么对待：TAOCP是为数不多的计算机专著里面能出这么多高水平习题的了。如果有大块的时间，能做一做当然最好不过。但如果只是一般的查阅，习题并非必要。不过有的习题本身就是经典问题。如果正文里没有找到想要的东西，不仿看看习题。
　 　（五）如何读正文里的算法分析：TAOCP里面的算法分析，算是古典算法分析里面的原教旨主义。始作俑者就是Knuth本人，后面还有 Sedgewick和Flajolet等一干人等给他发扬光大。这一派的作风可以说分毫必究，连常数都不放过。但数学工具却无外乎初等的《具体数学》的工 具。这是很好很强大的东西，掌握好了，无论研究还是工作都很方便。但其实TAOCP的数学都不算太难，仔细倒是真的。因此，如果时间不是特别充裕，对书中 结构的了解，要比具体分析步骤重要。这些经典内容多少年就没变过，每次有用时都可以回来查查看，每查一次说不定会有新的收获。
　　 （六）TAOCP的不足：前面已经提过了，下界（lower bounds）介绍的不够。下界结果，大多数只在章节结束的讨论部分引用一下。第三卷的查找（searching）一章，一些近些年的下界方面的新进展都 没有被引用，Knuth可能没有想到，数据结构这个经典方向这么多年来都在不温不火的不断前进着，尤其是下界。类似的也有第二卷的随机数（random numbers）一章，可以说连上界都严重过时，错过了去随机（derandomization）的黄金时代。好在其他几章这么多年来无甚进展，没怎么过 时。
　　许多人对TAOCP的推崇是无条件的，这里难免有人云亦云的成分。其实大可不必，读的人尽管放轻松。这么说不是因为TAOCP不值得推崇，而是就算把一切溢美之词都抛于脑后，随着岁月流逝，反复的阅读，你也一定会越来越喜欢这部书的。它的魅力经的起时间的考验。

------------------------------------------------------------------------------------

不要把它想象成葵花宝典，否则你就会走火入魔 http://www.douban.com/review/1294615/

　　书自然是好书，况且就算不是，也不是我这种级别的人能够评论的。
　　但看之前，请先端正自己的态度。
　　如果想通过这本书达到一个绝对的境界的人，可以歇歇了。
　　我虽不是科班出身的，但毕竟也看过几本书，基本上大家最好不要认为哪一本书能够让你成为一劳永逸的一族，即使这本书也不能。
　　国内对这本书的吹捧，估计主要因为盖茨老兄的那句话吧。
　　须知，盖茨并非因编程出名，Windows也并非盖茨所写。
　　想要发财学盖茨，趁早做生意去，学编程，只能误了你的前程。
　　总而言之一句话，书是好书，但是看之前请端正态度，彻底放下那种“看了这本书我就如何如何了，我是高手了”的思想。
　　曾有高手说过（针对什么十日内学会什么什么语言的书）“十年内学会编程”。
　　我想说，用一生学习计算！
　　ps(我未看过此书）

------------------------------------------------------------------------------------

[转帖]机器学习与人工智能学习资源导引

<从CSDN上转载的>
机器学习与人工智能学习资源导引
我经常在 TopLanguage 讨论组上推荐一些书籍，也经常问里面的牛人们搜罗一些有关的资料，人工智能、机器学习、自然语言处理、知识发现（特别地，数据挖掘）、信息检索这些无疑是 CS 领域最好玩的分支了（也是互相紧密联系的），这里将最近有关机器学习和人工智能相关的一些学习资源归一个类：
首先是两个非常棒的 Wikipedia 条目，我也算是 wikipedia 的重度用户了，学习一门东西的时候常常发现是始于 wikipedia 中间经过若干次 google ，然后止于某一本或几本著作。
第一个是“人工智能的历史”（History of Artificial Intelligence），我在讨论组上写道：
而今天看到的这篇文章是我在 wikipedia 浏览至今觉得最好的。文章名为《人工智能的历史》，顺着 AI 发展时间线娓娓道来，中间穿插无数牛人故事，且一波三折大气磅礴，可谓"事实比想象更令人惊讶"。人工智能始于哲学思辨，中间经历了一个没有心理学（尤其是认知神经科学的）的帮助的阶段，仅通过牛人对人类思维的外在表现的归纳、内省，以及数学工具进行探索，其间最令人激动的是 Herbert Simon （决策理论之父，诺奖，跨领域牛人）写的一个自动证明机，证明了罗素的数学原理中的二十几个定理，其中有一个定理比原书中的还要优雅，Simon 的程序用的是启发式搜索，因为公理系统中的证明可以简化为从条件到结论的树状搜索（但由于组合爆炸，所以必须使用启发式剪枝）。后来 Simon 又写了 GPS （General Problem Solver），据说能解决一些能良好形式化的问题，如汉诺塔。但说到底 Simon 的研究毕竟只触及了人类思维的一个很小很小的方面 —— Formal Logic，甚至更狭义一点 Deductive Reasoning （即不包含 Inductive Reasoning , Transductive Reasoning (俗称 analogic thinking）。还有诸多比如 Common Sense、Vision、尤其是最为复杂的 Language 、Consciousness 都还谜团未解。还有一个比较有趣的就是有人认为 AI 问题必须要以一个物理的 Body 为支撑，一个能够感受这个世界的物理规则的身体本身就是一个强大的信息来源，基于这个信息来源，人类能够自身与时俱进地总结所谓的 Common-Sense Knowledge （这个就是所谓的 Emboddied Mind 理论。 ），否则像一些老兄直接手动构建 Common-Sense Knowledge Base ，就很傻很天真了，须知人根据感知系统从自然界获取知识是一个动态的自动更新的系统，而手动构建常识库则无异于古老的 Expert System 的做法。当然，以上只总结了很小一部分我个人觉得比较有趣或新颖的，每个人看到的有趣的地方不一样，比如里面相当详细地介绍了神经网络理论的兴衰。所以我强烈建议你看自己一遍，别忘了里面链接到其他地方的链接。
顺便一说，徐宥同学打算找时间把这个条目翻译出来，这是一个相当长的条目，看不动 E 文的等着看翻译吧:)
第二个则是“人工智能”（Artificial Intelligence）。当然，还有机器学习等等。从这些条目出发能够找到许多非常有用和靠谱的深入参考资料。
然后是一些书籍
书籍：
1. 《Programming Collective Intelligence》，近年出的入门好书，培养兴趣是最重要的一环，一上来看大部头很容易被吓走的:P
2. Peter Norvig 的《AI, Modern Approach 2nd》（无争议的领域经典）。
3. 《The Elements of Statistical Learning》，数学性比较强，可以做参考了。
4. 《Foundations of Statistical Natural Language Processing》，自然语言处理领域公认经典。
5. 《Data Mining, Concepts and Techniques》，华裔科学家写的书，相当深入浅出。
6. 《Managing Gigabytes》，信息检索好书。
7. 《Information Theory：Inference and Learning Algorithms》，参考书吧，比较深。
相关数学基础（参考书，不适合拿来通读）：
1. 线性代数：这个参考书就不列了，很多。
2. 矩阵数学：《矩阵分析》，Roger Horn。矩阵分析领域无争议的经典。
3. 概率论与统计：《概率论及其应用》，威廉·费勒。也是极牛的书，可数学味道太重，不适合做机器学习的。于是讨论组里的 Du Lei 同学推荐了《All Of Statistics》并说到
机器学习这个方向，统计学也一样非常重要。推荐All of statistics，这是CMU的一本很简洁的教科书，注重概念，简化计算，简化与Machine Learning无关的概念和统计内容，可以说是很好的快速入门材料。
4. 最优化方法：《Nonlinear Programming, 2nd》非线性规划的参考书。《Convex Optimization》凸优化的参考书。此外还有一些书可以参考 wikipedia 上的最优化方法条目。要深入理解机器学习方法的技术细节很多时候（如SVM）需要最优化方法作为铺垫。
王宁同学推荐了好几本书：
《Machine Learning, Tom Michell》, 1997.
老书，牛人。现在看来内容并不算深，很多章节有点到为止的感觉，但是很适合新手（当然，不能"新"到连算法和概率都不知道）入门。比如决策树部分就很精彩，并且这几年没有特别大的进展，所以并不过时。另外，这本书算是对97年前数十年机器学习工作的大综述，参考文献列表极有价值。国内有翻译和影印版，不知道绝版否。
《Modern Information Retrieval, Ricardo Baeza-Yates et al》. 1999
老书，牛人。貌似第一本完整讲述IR的书。可惜IR这些年进展迅猛，这本书略有些过时了。翻翻做参考还是不错的。另外，Ricardo同学现在是Yahoo Research for Europe and Latin Ameria的头头。
《Pattern Classification (2ed)》, Richard O. Duda, Peter E. Hart, David G. Stork
大约也是01年左右的大块头，有影印版，彩色。没读完，但如果想深入学习ML和IR，前三章（介绍，贝叶斯学习，线性分类器）必修。
还有些经典与我只有一面之缘，没有资格评价。另外还有两本小册子，论文集性质的，倒是讲到了了不少前沿和细节，诸如索引如何压缩之类。可惜忘了名字，又被我压在箱底，下次搬家前怕是难见天日了。
（呵呵，想起来一本：《Mining the Web - Discovering Knowledge from Hypertext Data》 ）
说一本名气很大的书：《Data Mining: Practical Machine Learning Tools and Techniques》。Weka 的作者写的。可惜内容一般。理论部分太单薄，而实践部分也很脱离实际。DM的入门书已经不少，这一本应该可以不看了。如果要学习了解 Weka ，看文档就好。第二版已经出了，没读过，不清楚。
信息检索方面，Du Lei 同学再次推荐：
信息检索方面的书现在建议看Stanford的那本《Introduction to Information Retrieval》，这书刚刚正式出版，内容当然up to date。另外信息检索第一大牛Croft老爷也正在写教科书，应该很快就要面世了。据说是非常pratical的一本书。
对信息检索有兴趣的同学，强烈推荐翟成祥博士在北大的暑期学校课程，这里有全slides和阅读材料：http://net.pku.edu.cn/~course/cs410/schedule.html
maximzhao 同学推荐了一本机器学习：
加一本书：Bishop, 《Pattern Recognition and Machine Learning》. 没有影印的，但是网上能下到。经典中的经典。Pattern Classification 和这本书是两本必读之书。《Pattern Recognition and Machine Learning》是很新（07年），深入浅出，手不释卷。
最后，关于人工智能方面（特别地，决策与判断），再推荐两本有意思的书，
一本是《Simple Heuristics that Makes Us Smart》
另一本是《Bounded Rationality: The Adaptive Toolbox》
不同于计算机学界所采用的统计机器学习方法，这两本书更多地着眼于人类实际上所采用的认知方式，以下是我在讨论组上写的简介：
这两本都是德国ABC研究小组（一个由计算机科学家、认知科学家、神经科学家、经济学家、数学家、统计学家等组成的跨学科研究团体）集体写的，都是引起领域内广泛关注的书，尤其是前一本，後一本则是对 Herbert Simon （决策科学之父，诺奖获得者）提出的人类理性模型的扩充研究），可以说是把什么是真正的人类智能这个问题提上了台面。核心思想是，我们的大脑根本不能做大量的统计计算，使用fancy的数学手法去解释和预测这个世界，而是通过简单而鲁棒的启发法来面对不确定的世界（比如第一本书中提到的两个后来非常著名的启发法：再认启发法（cognition heuristics）和选择最佳（Take the Best）。当然，这两本书并没有排斥统计方法就是了，数据量大的时候统计优势就出来了，而数据量小的时候统计方法就变得非常糟糕；人类简单的启发法则充分利用生态环境中的规律性（regularities），都做到计算复杂性小且鲁棒。
关于第二本书的简介：
1. 谁是 Herbert Simon
2. 什么是 Bounded Rationality
3. 这本书讲啥的：
我一直觉得人类的决策与判断是一个非常迷人的问题。这本书简单地说可以看作是《决策与判断》的更全面更理论的版本。系统且理论化地介绍人类决策与判断过程中的各种启发式方法（heuristics）及其利弊（为什么他们是最优化方法在信息不足情况下的快捷且鲁棒的逼近，以及为什么在一些情况下会带来糟糕的后果等，比如学过机器学习的都知道朴素贝叶斯方法在许多情况下往往并不比贝叶斯网络效果差，而且还速度快；比如多项式插值的维数越高越容易overfit，而基于低阶多项式的分段样条插值却被证明是一个非常鲁棒的方案）。
在此提一个书中提到的例子，非常有意思：两个团队被派去设计一个能够在场上接住抛过来的棒球的机器人。第一组做了详细的数学分析，建立了一个相当复杂的抛物线近似模型（因为还要考虑空气阻力之类的原因，所以并非严格抛物线），用于计算球的落点，以便正确地接到球。显然这个方案耗资巨大，而且实际运算也需要时间，大家都知道生物的神经网络中生物电流传输只有百米每秒之内，所以 computational complexity 对于生物来说是个宝贵资源，所以这个方案虽然可行，但不够好。第二组则采访了真正的运动员，听取他们总结自己到底是如何接球的感受，然后他们做了这样一个机器人：这个机器人在球抛出的一开始一半路程啥也不做，等到比较近了才开始跑动，并在跑动中一直保持眼睛于球之间的视角不变，后者就保证了机器人的跑动路线一定会和球的轨迹有交点；整个过程中这个机器人只做非常粗糙的轨迹估算。体会一下你接球的时候是不是眼睛一直都盯着球，然后根据视线角度来调整跑动方向？实际上人类就是这么干的，这就是 heuristics 的力量。
相对于偏向于心理学以及科普的《决策与判断》来说，这本书的理论性更强，引用文献也很多而经典，而且与人工智能和机器学习都有交叉，里面也有不少数学内容，全书由十几个章节构成，每个章节都是由不同的作者写的，类似于 paper 一样的，很严谨，也没啥废话，跟《Psychology of Problem Solving》类似。比较适合 geeks 阅读哈。
另外，对理论的技术细节看不下去的也建议看看《决策与判断》这类书（以及像《别做正常的傻瓜》这样的傻瓜科普读本），对自己在生活中做决策有莫大的好处。人类决策与判断中使用了很多的 heuristics ，很不幸的是，其中许多都是在适应几十万年前的社会环境中建立起来的，并不适合于现代社会，所以了解这些思维中的缺点、盲点，对自己成为一个良好的决策者有很大的好处，而且这本身也是一个非常有趣的领域。

不谈国事

让人心寒的国家大事一件又一件，金钱的魅力看来无比巨大啊。记得《康熙大帝》评书里，纪晓岚多次说过一句“钱真是好东西啊。”那种感慨和如今的世风，哎！

近日负责协助一个项目的管理，在启动阶段困难不少。好在每天看几页偶像陈儒推荐的《项目管理艺术》，总能联想到目前的处境，当然也能借鉴到一些书中推荐的方法。继续细细摸索和体味咯！

舍得

2008年以来论文方面比较不顺，先是ACL未能投出，再是EMNLP被拒。今天在重新整理EMNLP实验时感觉有点做不动了。和xiaofeng说明决定放弃时，xiaofeng的一段话让我深受启发：“以后有新的idea, 想要想想你的方法比别人的好在哪里。这个图模型，从一开始，你就对它的优越性很模糊。最后变成是为了用这个方法而用这个方法。”

做研究很枯燥，因为要承载无数的失败。但是这个过程中，不管是实验设计还是论文写作，我都得到了很大的提高。由衷感谢谢xiaofeng！

载一句名言，“我没有失败，只是发现有一万种办法行不通。—— 爱迪生”。

整理思路，吸取经验教训，继续前行～！

看《计算机学会通讯》4卷8期有想

这期通讯主要介绍中国的人工智能研究情况，几篇文章都很让人受益。看完后摘录加瞎想记录如下，有空时再多多消化一下：



蚁群算法能用于聚类算法

OpenCYC

神经网络用于模式识别、联想记忆和形象思维

以获得尽可能高的互信息熵

Hownet for RE and CR

指代歧义消解属于仍未能得到彻底有效解决的问题

综观整个自然语言处理领域，尚未建立起一套完整的、系统的理论框架体系，许多理论研究甚至处于盲目的摸索阶段，如尝试一些新的机器学习方法或未曾使用的数学模型，这些尝试和实验带有很强的主观性和盲目性

相对而言，我们学者主要是跟踪国外技术潮流，缺少原创性理论、模型或算法。

背景知识和数据特有的性质可能是决定机器学习成败的关键

支持向量机存在以下几个问题：
1. 基于边缘的繁华界不能很好的解释Adaboost
2. 对实际问题，边缘的上界太松
3. 在噪音条件下，无论大样本还是小样本集合，边缘的界不能很好的预测未来实例
4. 边缘将偏差、方差混合在一起，不能清楚的表示边缘成功的贡献是哪个方面，更不能描述不同损失函数带来的影响和分析解凸优化问题得到的分类器和贝叶斯分类器时间的逼近程度。
5. 很多损失函数具有贝叶斯一致的性质。支撑向量机使用Hnge损失，但成功的关键不是因为边缘，而是因为使用了具有贝叶斯一致性质的Hinge损失函数。

沙皮尔证明了概率近似理论提出的另一个命题，即概念是弱可学习的，当且仅当它是强可学习的（弱可学习是指在多项式复杂度算法下，学习的正确率略好于随机猜测的结果（50%），而强可学习的概率是略小于100%。但沙皮尔正迷宫了可以找到复杂度可以接受的算法，使弱可学习的概念类变为强可学习的。）这意味着，如果我们可以建造一组精度大于50%的模型，并使用适当的规则集群它们，就可以获得具有高精度的模型。，目前这种学习称为集群学习（Essemble）。从算法设计角度，可以将学习问题考虑为在所有这些弱分类器为基张成的空间上的优化问题。这就是目前流行的提升（Boosting）算法的基础。

关系学习是指有些样本的变量之间存在某些关系。这个和共指消解问题非常接近。目前解决该问题的方法是归纳逻辑，其本质是根据背景知识将数据打碎，让各个碎片满足属性-值形式，并采用统计学习的方法将这些碎片建立模型，然后再根据背景知识将它们拼接起来。这是一类非常困难但是对实际应用又有重要意义的学习形式。

罗生门(Rashomon)问题指明Feature Selection的必要性。

惦念zhanghui

前几日看到zhanghui的msn上写“缝了好几针，破相了，很低落现在”。发了两次消息都没有回复。今晚一打听，才得知伤得有点重，还缝了好多针住了一天院。推荐朋友去给他买祛疤液了。

晚上健身时又想起了SG的健身团队，也就想到了zhanghui。希望zhanghui能很快康复起来，重新投入火热的研究中。

Recover fitness in gym

晚上在学校健身房进行了回国来的第一次Gym，锻炼后的感觉就是很爽啊。健身房旁就是健美操房，女友在那边也练得很开心。

学 校健身房比SG I2R的老健身房强出10倍不止，多出了很多单项目的健身大型设备，但是没有蹬腿自行车和跑步机，哑铃也很少。健身房里人山人海，很热闹，但是比起SG时 xiaofeng，zhanghui，junhui，kimi一起健身时的那种亲切感差了很远。记录一下，今天卧推直接恢复到40KG，增加了手臂锻炼， 也尝试了一些新新型器械。

有一点非常奇怪，就是明明我自己缴费报名参加的健身班，为什么一定需要注册呢？我又不是为了学分 :(

哈哈，总之锻炼的感觉很好啊，终于进入正常的生活状态了。感谢SG的朋友们让我养成了这个好习惯～！

终于有点状态了

8月10日离开SG，8月20日回到HRB，今天9月8日，终于有点工作状态了。继续调整自己，做最重要的事情，而不是当前最紧急的。