2013年3月28日星期四

state-of-the-art-计算机界的传奇- 高德纳



2013年3月22日发表评论阅读评论93 views   
state-of-the-art这个词我想在很多学术文章中都会被引用到,原义是 最先进的;已经发展的;达到最高水准的。科学与艺术看似貌不同,但是很多地方都神相似。
今天突然想起找找这个词的来源,原因是突然发现一个很传奇的人,他写了一本书叫《the art of computer programming》, 堪称当今计算机科学的根基,最开始我还以为这个词是因他而产生。虽然经查证后不是,但是看完作者的背景和经历足以让人半夜想睡觉的时候也能打上几针鸡血。
这本书的作者:Donald E. Knuth他给自己的主页上面放了一个醒目的中文名字:高德纳,是现在香港城市大学计算机系主任Frances Yao给他取的。谈起这位老爷子,我想没有人不会对他的成就肃然起敬。Computer Sciencitist不同于程序员,他们借助自己对数学的理解,用更加概括抽象的理论,推动计算机硬件和软件设计的进步,并让这些外在形式推动人类生产力的进步。
下面就列举下这位老爷子的传奇,作为晚上睡觉前的精神享受。

1. 高德纳曾在自传的开头幽默地发问:“Donald Knuth真的只是一个人么?”作为现代计算机科学的鼻祖,他完成了编译程序、属性文法和运算法则等领域的前沿研究,出版专著17部,发表论文150余篇(涉及巴比伦算法、圣经、字母“s”的历史等诸多内容),写出两个数字排版系统,同时在纯计算数学领域也有独特贡献。他获得的奖项难以胜数,其中包括ACM Turing Award颁发的图灵奖(1974),美国国家科学奖(1979),日本KYOTO奖(1996),瑞典科学院的Adelskold奖及冯诺伊曼奖。而他对荣誉从不经意,据说那只代表至高荣誉的图灵碗被用来盛放水果。——回首过往,几十年时光如白驹过隙,大约是他自己对做出的成果如此之多也感到吃惊,所以才有以上一问。
2.八岁时的高德纳即显出超凡智力:当时某糖果商以小学生为参与对象举办了一项益智趣味比赛,要求用“Ziegler’s Giant Bar”(分别为糖果厂名和出产的棒棒糖名)里的字母写出尽可能多的单词。高假装胃疼宅家两周,依靠一部大字典列出了4500个单词(超出裁判掌握的2000个单词一倍多),不仅使所在班级夺冠(奖品为一台电视机和每人一块Giant Bar),本人也赢得一付雪撬。其赛后感言曰:我还能写出更多。
3.在高中第一学年,高德纳并未对数学发生太大兴趣,他更喜欢听音乐与作曲,一度考虑过报考音乐专业。这个爱好深度影响到他后来的生活及研究——他将写作喻为演奏管风琴,其书房里的确也摆放有一台特制的84管管风琴,此外他还会萨克斯和大号等乐器。所著《娱乐和游戏论文集》一书有四个章节内容涉及到高的“主要副业”——音乐;进入90年代,当连续工作几天需要放松一下时,他会着手谱写管风琴乐曲。
4.1956年以科均97.5的分数高中毕业进入凯斯理工学院物理专业后,高德纳中学时创作的科幻小说《普茨比度量衡体系》发表于著名的《疯狂》(Mad)杂志,挣得平生第一笔稿费25美元及西屋“科学天才”提名奖。这个作品曾多次再版,直到作者即将退休的1991年还重印过一次。
5.大学一年级留校打工,毗邻的计算机房新到了一台IBM650——这个指示灯闪烁不定的庞然大物让高德纳生出莫大兴趣。当获准在晚上操作那台计算机后,他几天不眠不休地观察探究,并且改动了说明手册上的程序使之更加好用。一年后,高改入数学系,自此终生同计算机结缘。当时兼职学校篮球队的他用IBM650写了一个程序,用于对球员在每场比赛中得分、助攻、抢断、篮板球、盖帽等一揽子数据的分析评估,球队教练据此挑选球员,使凯斯理工学院赢得了1960年的联赛冠军。这个“神奇的公式和程序”引来了当地媒体乃至CBS电视台的大肆报道,高所在球队和IBM650的合影被IBM印到了产品宣传册上。这段经历的重要性不言而明,以至高德纳在巨著《计算机程序设计的艺术》第一卷卷首写下“献给曾经安装在开思理工学院的650型计算机,以纪念那些愉快的夜晚”的题辞。
6.上大二那年,某教授在课堂上给出一个刁钻的题目,宣称谁能破解就可记成绩“A”。高跟大多数同学都以为那是道无解的题,直到某日他未赶上公共汽车,只能步行去看一个演出时,方决定利用路上的闲暇碰下运气。不承想问题很快便获得解决,成功地得到了“A”。在接下来的那个学年里,他的离散数学成绩又一次被老师评为“A”。
7.高德纳1960年毕业于开思理工学院,因学业特别出色,被破例同时授予学士和硕士学位。之后在伯克利攻读数学博士期间,ALGOL60经常因为编译器不成熟出现故障,他为此编写了一个简单的测试程序,人称“Man or boy test”(男人或男孩测试),可以译成“是男人就得-67”。高解释,用ALGOL60来编译这段程序,只要运行结果等于-67,就说明这个编译器没有问题了,是纯爷们儿。
8.习惯用铅笔而非键盘写初稿,高将原因归咎于打字速度远高于思考速度(每分钟 80 个单词以上),而这会导致思考出现太多停顿,用铅笔可以让思考与输入速度保持一致——“我打字的速度比我思考的速度更快,这样当我试图用键盘创作重要内容时,就会产生同步问题。速度通常不会是最重要的标准。科学一般都难以迅速解释或迅速领会……我通常的工作方式是用铅笔和纸先把所有东西都写下来,然后在旁边放一个大废纸篓。然后使用Emacs将所有文本键入到机器中……特定的Emacs快捷键使得写书的过程有点儿像演奏风琴……”
9.“我戴着一顶计算机科学家的帽子,而不是一顶数学家的帽子。”这似乎暗示了身为加州理工学院数学博士的高对数学家的某种成见——在他看来后者只知道“What is it(这是什么)”,而前者还知道“How to do it(如何做到这一点)”这可能是他心目中的数学与计算机科学的区别。
10.斯坦福大学曾让高德纳为自己选择一个头衔,他确定的是“计算机程序设计艺术名誉教授”。高认为“计算机科学”不是科学(他很讶异人们为何如此喜欢科学),而是一门艺术。它们的区别在于:艺术是人创造的,而科学不是;艺术是可以无止境提高的,而科学不能;艺术创造需要天赋,而科学不需要。
11.传闻高改作业通常是随机翻到一页认真批阅,有了一个初步印象后,对剩下的内容就只大概看看了。阅读大致也照此办理:遇上大部头先读第316页,如果书比较薄就看第100页;随后就可以作出判断了,据说准确率还八九不离十。如果追随他的人很多,以后著书就要注意了:写到第316页或100页时一定要停下来多推敲下。这或许是高德纳推崇随机算法的结果。
12.“文学化编程(Literate Programming)”是高写的又一程序,他自称写这个程序的动机有二:A.让一个程序员(或许就是他自己)在某一日拿到普利策奖;B.让那些提出“结构化程序”的家伙在写“非文学程序”时,就像他当年写“非结构化程序”时一样怀有罪恶感——娃哈哈。有关“文学编程”设想的文字最先发表于英国的《计算机学报》,有人问为何不在美国发表,高答曰:美国人没文化,他们理解不了啊。
13.《美国数学月刊》刊载过高德纳一篇名为“卫生纸问题” 的论文,研究如何合理使用厕纸的算法,小节标题中使用了大量的“粪便学”词汇。编辑警告他,过度调侃的文风在我们这里是危险的,请三思!高替换了小标题里的某些词,但不想动文章标题,遂在给编辑的回信里写道:我用这个题目做过两次演讲,主题早已被广泛采用和讨论……云云。编辑无奈之下只好表示:“你的厕纸被接受了!”(斯坦福大学计算机科学系楼内的厕纸架可并放两筒厕纸,供如厕者取用。卷筒大小不等时,喜欢从大筒拿纸的叫big-chooser【大的选择器】,喜欢从小筒拿纸的则称little-chooser【小的选择器】;若两筒大小接近,一般人的选择可能是离手最近的。厕纸平时由janitor【看门人】负责更换,用完一筒换掉一筒;不过要是同时用完,恐怕就会有人遇上麻烦了……高研究的似是两筒纸同时用完的窘境出现的概率)
14.在伯克利毕业的前一年,著名的艾迪生-韦斯利出版社约初露头角的高德纳写一本编译器和程序设计方面的书,这件原本寻常的事最终成就了计算机科学史上的一个奇观。出版社1962年约稿,可直到1966年还动静全无,编辑忍不住去电催促,说都过去4年了,书写到啥程度了啊?高答才3000来页。编辑惊呼那干嘛还不交稿?答曰还没进入正题呢。编辑崩溃地说,那只能出多卷本了……
15.《计算机程序设计艺术》第一卷于1968年推出,可真正能读完读懂的人为数并不多(传比尔•盖茨费时几个月才读完这一卷,然后说,如果你想成为一个优秀的程序员,那就去读这个《基本算法》吧)。高对此解释道:“我知道我的书是不容易读,不过要知道的是,如果不是我精雕细琢地写的话,它们会比现在难读一百倍。”1973年,这部刚出到第三卷的书(计划写七卷)已被计算机界视为“神作”,最初几年就卖出100多万套;译为俄、日、西、葡、匈牙利、罗马尼亚等多种文字后,更创造了计算机类图书的销售纪录。美国计算机协会(ACM)也不淡定了,1974年就将国际计算机界的至高荣誉“图灵奖”授予了他——此时的高德纳年方36岁,他迄今还是这项最年轻图灵奖获得者纪录的保持者。
16.获此殊荣后,令业界大跌眼镜的是:高宣布暂停写作,理由是现有的计算机排版软件效果太差,破坏了这套书的美。这不免引发作者是否江郎才尽,见好就收的猜测与怀疑——不料辍笔10年的高德纳以三个重量级创造性成果:字体设计系统METAFONT(其价值一言以蔽之:计算机界最懂字体的俩大腕,一是乔布斯,一是高德纳)、文学化编程(充分展示程序设计的艺术性:清晰,美感,诗意),尤其是最具革命性的排版系统TEX(至今仍是全球学术排版的不二之选)给出了强力回应。尽管如此,仍有人说高写完三卷 TAOCP就去研究TeX,其实是害怕写第四卷——不过他对这类风言风语根本不以为意:“一个人要把事情做的完美,只有跟上帝的意图保持和谐,现在上帝要我去写第四卷了。”
17.搁置手头的重要工作,费时10年专研排版美学打造TEX系统,原因其实很简单:数理图文排版以前一直使用金属活字,70年代以降始有激光照排,然而当时的计算机虽能替代人工排出普通的报纸杂志,但对处理复杂的数理公式却力不从心。高德纳试图为计算机写一个小玩艺儿解决上述问题,TeX的前半部分由此产生。编写过程中,他想参考J•伯克霍夫的Aesthetic Measures(《美学标准》)一书,在哈佛的图书馆几经查阅也未能如愿,之后好不容易在麻省理工学院找到。参考的结果是在TeX里加入一个变量badness,用以衡量一行文字的美感,变量越小文字就越美。
18. TEX功能强大、几近无懈可击,其版本号非自然数列,也非年份,而是不断逼近的圆周率(最新版本为3.1415926)——这等于宣告产品接近完美,已经不可能作大的改进了。高为此设置了悬赏奖金:谁找出TEX里的一个bug,就付给其2.56美元,找出第二个5.12美元,第三个10.24美元……依此累加。算法大师不可能不明白指数增长的可怕性(传说中的国王就是玩指数游戏输掉了江山),然而直到今天,他也未能为此付出多少钱。高的另一悬赏是向发现其著作中错误的人发奖,数额依旧是2.56美元始,因为“256美分刚好是十六进制的一美元”。不过寥寥几位获奖者都将有他签名的支票当作文物珍藏,并未打算去银行兑现。
19.作为开源代码运动最早的倡导者之一,高德纳将Tex 和Metafont无偿贡献给了世界,自己没有从中获取任何报酬。他的想法是,一个人一旦能够喂饱自己并有个安身之所,剩下的就是为别人做点什么了。“我尝试尽我所能的去熟悉电脑科学里的一些领域,然后把这些知识摘要成大家比较容易了解的方式,让没有那么多时间做这种学习的人也能够吸收它们”。为此他常常需要阅读超过20万页的文献,然后将之浓缩为两千页——他无意追赶最流行的内容,而是希望从日新月异的信息中萃取出能够存活到下个世纪的精华。
20. 1992年,高为潜心写作TAOCP从斯坦福提前退休,同时停用电子邮箱(他自1975年就开始玩电邮)。2008年,TAOCP前三卷出版30年后,第四卷在高粉的千呼万唤中终于面世,此际的高德纳已然是满头白发。对计算机科学的倾心热爱,使他为这部作品耗费了毕生心血:从及冠之年直至古稀老人。
21.高做过大受欢迎的“信仰与科学的关系”系列讲座,对访者问及的写作和信仰之间的关系,他回答说:“计算机科学是既壮观又幽美的,我尝试尽自己所能,以最恰当的方式来解释我所了解的某些片断……我相信,总有一些神秘的东西是超越人类的理解而存在的……我认为,上帝希望我能创造某些成果,而这些东西能够启发其他人去创造别的成果。”
22.高德纳这个中文名来自储枫教授(香港城大计算机科学系主任,华裔图灵奖得主姚期智的夫人)。以“高”为姓,据Knuth自述是因其个头高大,且辅音G和K读音接近;“德纳”则与“Donald”相谐,且在中文里含体面高贵之义。其时(1977年)高德纳携夫人及儿女John和与Jen正准备访问中国大陆——储枫给孩子也分别起了“高小强”、“高小珍”的名字,他们全家还同中国孩子在公园玩过无须语言交流的游戏。
23.有人视高为文艺复兴时期式的天才人物,因其不仅博学,更难得的是具超一流的动手能力——在分工日益细化,专业领域愈来愈狭窄的现代社会,这种博而专,基础与应用兼能,理论和操作并行的人才类型尤为罕见。如同一个人独力设计制造一架飞机,除了需要精通空气动力学理论,还须考虑机身上每一颗螺丝钉的固定方式,这确实不免让人想到欧洲文艺复兴时期列奥纳多•达•芬奇那样的全能巨人。
24. 唐纳德•欧文•克努特(Donald Ervin Knuth):1938年生于美国威斯康辛州密歇根湖畔的密尔沃基,斯坦福大学计算机科学系荣誉退休教授,排版软件TeX和字型设计系统Metafont发明人,所著描述基本算法与数据结构的巨作《计算机程序设计的艺术》被《美国科学家》杂志列为20世纪最重要的12本物理科学类专著之一,与爱因斯坦《相对论》、狄拉克《量子力学》、理查•费曼《量子电动力学》等经典比肩而立。
Knuth很早就提前退休,为的是集中精力把巨著The Art of Computer Programming写完。他一生共带过二十四个(此数字也许不准)博士生,发誓不会再带更多的学生。但是,他有一个奇妙的承诺:在他定期进行的讲座中,会不断提出一些新的难题。如果有人能在给定的期限内解出任何一道难题,他将为那个人的博士论文签名(大约相当于名誉导师吧)!不知道世界之大,有没有哪位后起之秀能获得这样的殊誉?希望有机会能去stanford看看,哈哈!

GDP不能告诉我们什么?

最近在读曼昆的《宏观经济学》,对GDP的概念有了更多理性的认识。

首先GDP(gross domestic product,国内生产总值)的定义
是在某一既定时期一个国家内生产的所有最终物品与劳务的市场价值。
经济学家们用了下面的公式来量化它。
Y(GDP) =  C + I + G +NX
其中C代表消费,I表示投资,G代表政府购买,NX表示净出口。
但是要注意的是由于有货币通胀和紧缩的存在,因此有名义GDP和真实GDP的区别。真实GDP是按不变价格评价的物品和劳务的生产。因此需要选择一个基年价格进行计算,例如10年前1元RMB的雪糕,现在卖5元RMB了,但是依然按照1元RMB价格乘以产出的雪糕数量加入到今年的GDP。
所以我们可以得到一个GDP的平减指数如下:
由此可以得到第二年相比于第一年的通货膨胀率如下:
当然还有很多灰色收入并没有被GDP统计近来,这让我想起了近来看过的一篇文章,有兴趣的朋友可以点击这里
这些未被统计入GDP的暗流资金,很可能对国家的经济造成重大的损失,也对宏观经济决策造成了极大的困难,房价越调越高的结果可以从中显现无疑。
“地下经济很好地衡量了一个国家的进步和健康程度。当许多事情是错误的时候,就需要将其隐藏起来。”
之所以写这篇文章,是因为GDP作为一个经济学概念,被我们国家作为发展的重要衡量指标,在近些年已经暴露除了很多问题。在这本书里的23.5节中就直接提出疑问:GDP是衡量经济福利的好指标吗?
1968年肯尼迪竞选美国总统的时候,就曾慷慨激昂地批评GDP:
GDP并没有考虑到我们孩子的健康,他们的教育质量,或者他们游戏的快乐。它也没有包括我们的诗歌之美,或者婚姻的稳定;没有包括我们关于公共问题争论的智慧,或者我们公务员的清廉。它既没有衡量我们的勇气、智慧,也没有衡量对祖国的热爱。简言之,它衡量一切,但并不包括使我们的生活有意义的东西。
首先,GDP没有考虑到收入分配问题,少数个人的垄断收入暴涨和绝大多数人停滞不前,并不是社会繁荣的景象。
因此GDP忽略社会福利的提高,只是追求每个人不停地产出。同时更重要地是,在现在化技术革命推进工业浪潮的过程,人们为了追求经济的发展,直接忽视的就是环境生活的牺牲,这些隐性成本的投入,应该给GDP的衡量加一个大大的负分,这样才是合理衡量GDP意义的公式。
举个例子,一位先生发现他雇佣的保姆勤劳、贤惠、可爱,把她娶为妻子。在此之前,他需向保姆支付工资,保姆从事的做饭、清扫房间、照顾老人等活动被计算到GDP中。当保姆变成妻子,她仍然从事同样的劳动,甚至在家务上付出更多,但丈夫不再向她支付报酬,从而这些活动不再增加GDP。保姆变成妻子之后,这个国家的经济活动并没有因此而减少,但GDP却减少了。
这个故事告诉我们:GDP不是万能的。
总结一下:
第一,GDP不能反映经济发展对资源环境所造成的负面影响。
比如,只要采伐树木,GDP就会增加,但过量采伐后会造成森林资源的减少,GDP却不考虑相应的代价。再比如,某些产品的生产会向空气或水中排放有害物质,GDP会随着产品产量的增加而增加,却不考虑对环境造成的损害。显然,GDP在反映经济增长的同时,没有反映它所带来的资源耗减和环境损失的代价。
第二,GDP不能准确地反映一个国家财富的变化。
目前,经济学家们对一个国家的国民财富尽管有不同的解释,但都把固定资本存量作为它的重要组成部分。一个国家财富能否有效地增长,不仅取决于GDP中固定资本形成总额的大小,还取决于其质量。如果固定资本的质量不好,没有到使用期限就不得不报废,那么固定资本形成总额再多也许都不能有效地提高一国的国民财富。
比如,我们在2001年建造了一座桥梁,2002年由于工程质量问题拆除了这座桥梁,2003年又重新建造一座同样的桥梁。2001年建造的桥梁增加了2001年的GDP,2003年建造的桥梁又增加了2003年的GDP,从而GDP增加了两次。然而2003年年底的国民财富中只包括当年建造的那座桥梁,2001年建造的那座桥梁因被拆除,在2002年年底的国民财富统计中就已经被剔除了。同时,2003年在建造这座桥梁时又消耗了一次自然资源(如果2001年建造的那座桥梁不出现质量问题,这些资源就不会被消耗掉),所以,与2001年年底的国民财富相比,2003年年底的国民财富不仅没有增加,反而会减少。
所以,我们不仅要注重GDP的数量,还要注重它的质量。如果我们盖了许多厂房、住房,修了许多道路、桥梁、码头,而不注重其质量,没有多久就不得不拆除,虽然GDP表现得一派繁荣,但国民财富不会迅速增加,反而可能会减少。
第三,GDP不能反映某些重要的非市场经济活动。
有些非市场经济活动在人们的日常生活中占有很重要的位置,比如家庭妇女做饭、照顾老人、养育儿童,等等,这些活动没有发生支付行为,按照国际标准,GDP不反映这些活动。但是,如果这些工作由雇佣的保姆来承担,雇主就要向保姆支付报酬,按照国际标准,相应的活动就必须反映在GDP中。可见,由于GDP不能反映某些非市场经济活动,使得它在某种程度上损失了客观性和可比性。
在发达的市场经济国家,家务劳动市场化的程度比较高,比如,大多数家庭都把孩子送到幼儿园去育养,许多老人被送到养老院去照顾等等。而发展中国家家务劳动市场化程度比较低,大部分家务劳动都由家庭成员自己来承担。同样的家务劳动,发达的市场经济国家市场化程度高,对GDP的贡献就大;发展中国家市场化程度低,对GDP的贡献就小。因此,就这一点来说,发展中国家的GDP与发达国家的GDP并不完全可比。
第四,GDP并不能全面地反映人们的福利状况。
人均GDP的增加代表一个国家人民平均收入水平的增加,从而当一个国家的人均GDP增加时,这个国家的平均福利状况将得到改善。但是,由于收入分配的不平等,一小部分人得到了更多的收入,大多数人的收入水平并没有增加,或增加得较少,因此他们的福利状况并没有得到改善,或没有得到明显的改善。从人均GDP中就看不出这种由于收入分配的差异状况而产生的福利的差异状况。

三、深度学习(Deep Learning)算法简介



查看最新论文
深度(Depth)
从一个输入中产生一个输出所涉及的计算可以通过一个流向图(flow graph)来表示:流向图是一种能够表示计算的图,在这种图中每一个节点表示一个基本的计算并且一个计算的值(计算的结果被应用到这个节点的孩子节点的值)。考虑这样一个计算集合,它可以被允许在每一个节点和可能的图结构中,并定义了一个函数族。输入节点没有孩子,输出节点没有父亲。
对于表达1 的流向图,可以通过一个有两个输入节点2 和3 的图表示,其中一个节点通过使用23 作为输入(例如作为孩子)来表示4 ;一个节点仅使用2作为输入来表示平方;一个节点使用6 和7 作为输入来表示加法项(其值为5 );最后一个输出节点利用一个单独的来自于加法节点的输入计算SIN。
这种流向图的一个特别属性是深度(depth):从一个输入到一个输出的最长路径的长度。
传统的前馈神经网络能够被看做拥有等于层数的深度(比如对于输出层为隐层数加1)。SVMs有深度2(一个对应于核输出或者特征空间,另一个对应于所产生输出的线性混合)。
深度架构的动机
学习基于深度架构的学习算法的主要动机是:
不充分的深度是有害的;
大脑有一个深度架构;
认知过程是深度的;
不充分的深度是有害的
在许多情形中深度2就足够(比如logical gates, formal [threshold] neurons, sigmoid-neurons, Radial Basis Function [RBF] units like in SVMs)表示任何一个带有给定目标精度的函数。但是其代价是:图中所需要的节点数(比如计算和参数数量)可能变的非常大。理论结果证实那些事实上所需要的节点数随着输入的大小指数增长的函数族是存在的。这一点已经在logical gates, formal [threshold] neurons 和rbf单元中得到证实。在后者中Hastad说明了但深度是d时,函数族可以被有效地(紧地)使用O(n)个节点(对于n个输入)来表示,但是如果深度被限制为d-1,则需要指数数量的节点数O(2^n)。
我们可以将深度架构看做一种因子分解。大部分随机选择的函数不能被有效地表示,无论是用深地或者浅的架构。但是许多能够有效地被深度架构表示的却不能被用浅的架构高效表示(see the polynomials example in the Bengio survey paper)。一个紧的和深度的表示的存在意味着在潜在的可被表示的函数中存在某种结构。如果不存在任何结构,那将不可能很好地泛化。
大脑有一个深度架构
例如,视觉皮质得到了很好的研究,并显示出一系列的区域,在每一个这种区域中包含一个输入的表示和从一个到另一个的信号流(这里忽略了在一些层次并行路径上的关联,因此更复杂)。这个特征层次的每一层表示在一个不同的抽象层上的输入,并在层次的更上层有着更多的抽象特征,他们根据低层特征定义。
需要注意的是大脑中的表示是在中间紧密分布并且纯局部:他们是稀疏的:1%的神经元是同时活动的。给定大量的神经元,任然有一个非常高效地(指数级高效)表示。
认知过程看起来是深度的
  • 人类层次化地组织思想和概念;
  • 人类首先学习简单的概念,然后用他们去表示更抽象的;
  • 工程师将任务分解成多个抽象层次去处理;
学习/发现这些概念(知识工程由于没有反省而失败?)是很美好的。对语言可表达的概念的反省也建议我们一个稀疏的表示:仅所有可能单词/概念中的一个小的部分是可被应用到一个特别的输入(一个视觉场景)。
学习深度架构的突破
2006年前,尝试训练深度架构都失败了:训练一个深度有监督前馈神经网络趋向于产生坏的结果(同时在训练和测试误差中),然后将其变浅为1(1或者2个隐层)。
2006年的3篇论文改变了这种状况,由Hinton的革命性的在深度信念网(Deep Belief Networks, DBNs)上的工作所引领:
在这三篇论文中以下主要原理被发现:
  • 表示的无监督学习被用于(预)训练每一层;
  • 在一个时间里的一个层次的无监督训练,接着之前训练的层次。在每一层学习到的表示作为下一层的输入;
  • 用无监督训练来调整所有层(加上一个或者更多的用于产生预测的附加层);
DBNs在每一层中利用用于表示的无监督学习RBMs。Bengio et al paper 探讨和对比了RBMs和auto-encoders(通过一个表示的瓶颈内在层预测输入的神经网络)。Ranzato et al paper在一个convolutional架构的上下文中使用稀疏auto-encoders(类似于稀疏编码)。Auto-encoders和convolutional架构将在以后的课程中讲解。
从2006年以来,大量的关于深度学习的论文被发表,一些探讨了其他原理来引导中间表示的训练,查看Learning Deep Architectures for AI

Deep Learning的基本思想和方法



实际生活中,人们为了解决一个问题,如对象的分类(对象可是是文档、图像等),首先必须做的事情是如何来表达一个对象,即必须抽取一些特征来表示一个对象,如文本的处理中,常常用词集合来表示一个文档,或把文档表示在向量空间中(称为VSM模型),然后才能提出不同的分类算法来进行分类;又如在图像处理中,我们可以用像素集合来表示一个图像,后来人们提出了新的特征表示,如SIFT,这种特征在很多图像处理的应用中表现非常良好,特征选取得好坏对最终结果的影响非常巨大。因此,选取什么特征对于解决一个实际问题非常的重要。
然而,手工地选取特征是一件非常费力、启发式的方法,能不能选取好很大程度上靠经验和运气;既然手工选取特征不太好,那么能不能自动地学习一些特征呢?答案是能!Deep Learning就是用来干这个事情的,看它的一个别名Unsupervised Feature Learning,就可以顾名思义了,Unsupervised的意思就是不要人参与特征的选取过程。因此,自动地学习特征的方法,统称为Deep Learning。
1)Deep Learning的基本思想
假设我们有一个系统S,它有n层(S1,…Sn),它的输入是I,输出是O,形象地表示为: I =>S1=>S2=>…..=>Sn => O,如果输出O等于输入I,即输入I经过这个系统变化之后没有任何的信息损失,保持了不变,这意味着输入I经过每一层Si都没有任何的信息损失,即在任何一层Si,它都是原有信息(即输入I)的另外一种表示。现在回到我们的主题Deep Learning,我们需要自动地学习特征,假设我们有一堆输入I(如一堆图像或者文本),假设我们设计了一个系统S(有n层),我们通过调整系统中参数,使得它的输出仍然是输入I,那么我们就可以自动地获取得到输入I的一系列层次特征,即S1,…, Sn。
另外,前面是假设输出严格地等于输入,这个限制太严格,我们可以略微地放松这个限制,例如我们只要使得输入与输出的差别尽可能地小即可,这个放松会导致另外一类不同的Deep Learning方法。上述就是Deep Learning的基本思想。
2)Deep Learning的常用方法
a). AutoEncoder
最简单的一种方法是利用人工神经网络的特点,人工神经网络(ANN)本身就是具有层次结构的系统,如果给定一个神经网络,我们假设其输出与输入是相同的,然后训练调整其参数,得到每一层中的权重,自然地,我们就得到了输入I的几种不同表示(每一层代表一种表示),这些表示就是特征,在研究中可以发现,如果在原有的特征中加入这些自动学习得到的特征可以大大提高精确度,甚至在分类问题中比目前最好的分类算法效果还要好!这种方法称为AutoEncoder。当然,我们还可以继续加上一些约束条件得到新的Deep Learning方法,如如果在AutoEncoder的基础上加上L1的Regularity限制(L1主要是约束每一层中的节点中大部分都要为0,只有少数不为0,这就是Sparse名字的来源),我们就可以得到Sparse AutoEncoder方法。
b). Sparse Coding
如果我们把输出必须和输入相等的限制放松,同时利用线性代数中基的概念,即O = w1*B1 + W2*B2+….+ Wn*Bn, Bi是基,Wi是系数,我们可以得到这样一个优化问题:
Min |I – O|
通过求解这个最优化式子,我们可以求得系数Wi和基Bi,这些系数和基础就是输入的另外一种近似表达,因此,它们可以特征来表达输入I,这个过程也是自动学习得到的。如果我们在上述式子上加上L1的Regularity限制,得到:
Min |I – O| + u*(|W1| + |W2| + … + |Wn|)
这种方法被称为Sparse Coding。
c) Restrict  Boltzmann Machine (RBM)
假设有一个二部图,每一层的节点之间没有链接,一层是可视层,即输入数据层(v),一层是隐藏层(h),如果假设所有的节点都是二值变量节点(只能取0或者1值),同时假设全概率分布p(v, h)满足Boltzmann 分布,我们称这个模型是Restrict  Boltzmann Machine (RBM)。下面我们来看看为什么它是Deep Learning方法。首先,这个模型因为是二部图,所以在已知v的情况下,所有的隐藏节点之间是条件独立的,即p(h|v) =p(h1|v)…..p(hn|v)。同理,在已知隐藏层h的情况下,所有的可视节点都是条件独立的,同时又由于所有的v和h满足Boltzmann 分布,因此,当输入v的时候,通过p(h|v) 可以得到隐藏层h,而得到隐藏层h之后,通过p(v|h) 又能得到可视层,通过调整参数,我们就是要使得从隐藏层得到的可视层v1与原来的可视层v如果一样,那么得到的隐藏层就是可视层另外一种表达,因此隐藏层可以作为可视层输入数据的特征,所以它就是一种Deep Learning方法。
如果,我们把隐藏层的层数增加,我们可以得到Deep Boltzmann Machine (DBM);如果我们在靠近可视层的部分使用贝叶斯信念网络(即有向图模型,当然这里依然限制层中节点之间没有链接),而在最远离可视层的部分使用Restrict  Boltzmann Machine,我们可以得到Deep Belief Net (DBN) 。
当然,还有其它的一些Deep Learning 方法,在这里就不叙述了。总之,Deep Learning能够自动地学习出数据的另外一种表示方法,这种表示可以作为特征加入原有问题的特征集合中,从而可以提高学习方法的效果,是目前业界的研究热点。

机器学习前沿热点–Deep Learning

深度学习是机器学习研究中的一个新的领域,其动机在于建立、模拟人脑进行分析学习的神经网络,它模仿人脑的机制来解释数据,例如图像,声音和文本。深度学习是无监督学习的一种。
深度学习的概念源于人工神经网络的研究。含多隐层的多层感知器就是一种深度学习结构。深度学习通过组合低层特征形成更加抽象的高层表示属性类别或特征,以发现数据的分布式特征表示。
深度学习的概念由Hinton等人于2006年提出。基于深信度网(DBN)提出非监督贪心逐层训练算法,为解决深层结构相关的优化难题带来希望,随后提出多层自动编码器深层结构。此外Lecun等人提出的卷积神经网络是第一个真正多层结构学习算法,它利用空间相对关系减少参数数目以提高训练性能。

一、Deep Learning的前世今生

图灵在 1950 年的论文里,提出图灵试验的设想,即,隔墙对话,你将不知道与你谈话的,是人还是电脑 [1]。
这无疑给计算机,尤其是人工智能,预设了一个很高的期望值。但是半个世纪过去了,人工智能的进展,远远没有达到图灵试验的标准。这不仅让多年翘首以待的人们,心灰意冷,认为人工智能是忽悠,相关领域是“伪科学”。
2008 年 6 月,“连线”杂志主编,Chris Anderson 发表文章,题目是 “理论的终极,数据的泛滥将让科学方法过时”。并且文中还引述经典著作 “人工智能的现代方法”的合著者,时任 Google 研究总监的 Peter Norvig 的言论,说 “一切模型都是错的。进而言之,抛弃它们,你就会成功”[2]。
言下之意,精巧的算法是无意义的。面对海量数据,即便只用简单的算法,也能得到出色的结果。与其钻研算法,不如研究云计算,处理大数据。
如果这番言论,发生在 2006 年以前,可能我不会强力反驳。但是自 2006 年以来,机器学习领域,取得了突破性的进展。
图灵试验,至少不是那么可望而不可即了。至于技术手段,不仅仅依赖于云计算对大数据的并行处理能力,而且依赖于算法。这个算法就是,Deep Learning。
借助于 Deep Learning 算法,人类终于找到了如何处理 “抽象概念”这个亘古难题的方法。
于是学界忙着延揽相关领域的大师。Alex Smola 加盟 CMU,就是这个背景下的插曲。悬念是 Geoffrey Hinton 和 Yoshua Bengio 这两位牛人,最后会加盟哪所大学。
Geoffrey Hinton 曾经转战 Cambridge、CMU,目前任教University of Toronto。相信挖他的名校一定不少。
Yoshua Bengio 经历比较简单,McGill University 获得博士后,去 MIT 追随 Mike Jordan 做博士后。目前任教 University of Montreal。
Deep Learning 引爆的这场革命,不仅学术意义巨大,而且离钱很近,实在太近了。如果把相关技术难题比喻成一座山,那么翻过这座山,山后就是特大露天金矿。技术难题解决以后,剩下的事情,就是动用资本和商业的强力手段,跑马圈地了。
于是各大公司重兵集结,虎视眈眈。Google 兵分两路,左路以 Jeff Dean 和 Andrew Ng 为首,重点突破 Deep Learning 等等算法和应用 [3]。
Jeff Dean 在 Google 诸位 Fellows 中,名列榜首,GFS 就是他的杰作。Andrew Ng 本科时,就读 CMU,后来去 MIT 追随 Mike Jordan。Mike Jordan 在 MIT 人缘不好,后来愤然出走 UC Berkeley。Andrew Ng 毫不犹豫追随导师,也去了 Berkeley。拿到博士后,任教 Stanford,是 Stanford 新生代教授中的佼佼者,同时兼职 Google。
Google 右路军由 Amit Singhal 领军,目标是构建 Knowledge Graph 基础设施。
1996 年 Amit Singhal 从 Cornell University 拿到博士学位后,去 Bell Lab 工作,2000 年加盟 Google。据说他去 Google 面试时,对 Google 创始人 Sergey Brian 说,“Your engine is excellent, but let me rewirte it!”[4]
换了别人,说不定一个大巴掌就扇过去了。但是 Sergey Brian 大人大量,不仅不怪罪小伙子的轻狂,反而真的让他从事新一代排名系统的研发。Amit Singhal 目前任职 Google 高级副总裁,掌管 Google 最核心的业务,搜索引擎。
Google 把王牌中之王牌,押宝在 Deep Learning 和 Knowledge Graph 上,目的是更快更大地夺取大数据革命的胜利果实。
Reference
[1] Turing Test.
http://en.wikipedia.org/wiki/Turing_test
[2] The End of Theory: The Data Deluge Makes the Scientific Method Obsolete
http://www.wired.com/science/discoveries/magazine/16-07/pb_theory
[3] Introduction to Deep Learning.
http://en.wikipedia.org/wiki/Deep_learning
[4] Interview with Amit Singhal, Google Fellow.
http://searchengineland.com/interview-with-amit-singhal-google-fellow-121342

支付宝连夜修改安全漏洞 转账付款页面隐藏详情


2013-03-28 11:14:24 来源:光明网科技   查看评论

    【光明网科技】3月28日消息,今天上午,支付宝方面表示,已经连夜修改了生活助手付款结果页面,将付款结果页面详情全部去掉,并增加消费记录详情链接,该链接点击后需要用户登录才可以看到。此前,用户可以通过谷歌等浏览器搜索到一些支付宝交易详情,具体到付款账户、收款账户、姓名、日期等。
支付宝连夜修改安全漏洞,这是修改后的支付宝生活助手付款结果页面
谷歌中依然能检索到转账付款的信息,但是打开后详情已经隐藏
这是修改漏洞以前,支付宝转载付款页面的详情暴露无遗
    支付宝官方微博在回应中称,支付宝生活助手转账付款结果页面一般用于支付双方展示支付结果,不含真实姓名、密码等重要信息,支付宝对这一页面链接加具了安全保护,正常情况下任何搜索引擎都无法抓取。
    对于谷歌中能够搜索到付款结果页面的质疑,支付宝给出的解释是,“在一些论坛和社区里,存在用户主动分享付款成功页面的链接的习惯,主要是为了提供给交易对方查看,这也是我们查看了被抓取的链接,大多数都是邮品交易。”与此相印证的是,xmd5在线解密站长、安全顾问汪利辉认为,“可能是一些用户主动将支付结果的url贴到一些互联网系统中,证明自己自己支付相关费用”。
    不过,支付宝的这一安全漏洞还是引起广大网友一定程度的恐慌,很多人担心如果信息被不法分子窃取后,用户的资金安全、个人隐私会受到极大影响。与此同时,360搜索已经无法搜到相关结果。(战钊)