初探计算机视觉的三个源头、兼谈人工智能｜正本清源

2016-11-22 视觉求索

谈话人：

杨志宏 视觉求索公众号编辑

朱松纯 加州大学洛杉矶分校UCLA统计学和计算机科学教授

Song-Chun Zhu
　
www.stat.ucla.edu/~sczhu

时间: 2016年10月

杨: 朱教授，你在计算机视觉领域耕耘20余年，获得很多奖项， 是很资深的研究人员。近年来你又涉足认知科学、机器人和人工智能。受 《视觉求索公众号》编辑部委托，我想与你探讨一下计算机视觉的起源，这个学科是什么时候创建的， 有哪些创始和代表人物。兼谈一下目前热门的人工智能。

朱: 好， 我们首先谈一下为什么需要讨论这个问题。 然后， 再来探讨一下计算机视觉的三个重要人物David Marr， King-Sun Fu， Ulf Grenander以及他们的学术思想。我认为他们是这个领域的主要创始人、或者叫有重要贡献的奠基人物。

第一节： 为什么要追溯计算机视觉的源头， 这有什么现实意义?

中国有句很有名的话：“一个民族如果忘记了历史,她也注定将失去未来。” 我认为这句话对一个学科来讲，同样发人深省。我们先来看看现实的状况吧。

首先，假设你当前是一个刚刚进入计算机视觉领域的研究生，很快你会有一种错觉，觉得这个领域好像就是5年前诞生的。 跟踪最新发表的视觉的论文，很少有文章能够引用到5年之前的文献，大部分文献只是2-3年前的，甚至是1年之内的。现在的信息交换比较快，大家都在比一些 Benchmarks,把结果挂到arXiv 网上发布。 很少有一些认真的讨论追溯到10年前，20年前， 或30年前的一些论文，提及当时的一些思想和框架性的东西。现在大家都用同样的方法，只是比拼，你昨天是18.3%的记录（错误率），我今天搞到17.9%了。大家都相当短视，那么研究生毕业以后变成了博士，可能也会带学生做研究，他只知道这几年的历史和流行的方法的话，怎么可能去传承这个学科，让其长期健康发展呢？特别是等当前这一波方法退潮之后，这批人就慢慢失去了根基和源创力。这是一个客观的现象。

其次，还有一个现象是，随着视觉与机器学习结合，再混合到人工智能的这么一个社会关注度很高的领域去以后，目前各种工业界，资本、投资界都往这里面来炒作。所以，你可以在互联网上看到各种推送的文字，什么这个大师，那个什么牛人、达人说得有声有色，一大堆封号。中国是有出“大师”的肥沃的土壤的，特别是在这个万众创新、浮躁的年代。 这些文字在混淆公众的视听。也有的是一些中国的研究人员、研究生， 半懂不懂，写出来一些， 某某梳理机器学习、神经网络和人工智能的历史大事。说得神乎其神。我的大学同学把这种帖子转发给我，让我担忧。

杨：这大多是以学术的名义写的软文，看起来像学术文章，实际上就是带广告性质的，一般都是说创投、创业公司里的人，带着资本的目的，带商业推广性质的。

朱: 我甚至不排除有些教授，比如与硅谷结合很紧密的、在IT公司或者风投公司兼职的，有意识地参与、引领这种炒作。

这对我们的年轻学生其实是很致命的，因为他们不了解这背后的动机， 缺乏免疫力。而且现在年轻人和公众都依赖短平快的社交媒体，很少去读专业文献。当公众的思想被这些文字占领了，得出错误的社会性的共识，变成了 false common sense， 对整个社会， 甚至对学术界，都会产生长久的负面冲击。

这就形成了新时代的皇帝的新装。我们需要对这种现象发声， 做一些严肃的探讨。所以，正本清源有着重要的现实意义。

第二节：计算机视觉和人工智能、机器学习的关系

杨：谈到这里，我想先问一下计算机视觉和人工智能是什么关系？还有机器学习这三个东西。

朱：人工智能是在60年代中后期起步的。一直到80年代，翻开它的教科书，就是一些启发式搜索，研究最多的是下棋， 从国际象棋一直到最近的围棋，都是比较抽象的表达。棋盘的位置是有限的、下棋的动作也是有限的， 没有感知和动作执行的不确定性。 所有的问题都变成一个图搜索的问题，教科书上甚至出现了一个通用图搜索算法号称可以解决任何人工智能问题。当时视觉问题还没引起大家重视。我这里有一份1966 年7月 的 MIT AI 实验室的第100号报告（备忘录memo 100），很短，题目叫做“The Summer Vision Project”。这个备忘录的基本意思就是暑假的时候找几个学生构造一个视觉系统。他们当时可能就觉得这个问题基本上是不需要做什么研究的。所以你就一个暑假，几个人一起写个程序，就把它干掉算了。现在说起来，当然是个笑话。

人的大脑皮层的活动， 大约70%是在处理视觉相关信息。视觉就相当于人脑的大门，其它如听觉、触觉、味觉那都是带宽较窄的通道。视觉相当于八车道的高速， 其它感觉是两旁的人行道。如果不能处理视觉信息的话，整个人工智能系统是个空架子，只能做符号推理，比如下棋、定理证明， 没法进入现实世界。所以你刚才问到的人工智能和计算机视觉的关系，视觉，它相当于说芝麻开门。大门就在这里面，这个门打不开, 就没法研究真实世界的人工智能。

到80年代，人工智能， 连带机器人研究就跌入了低谷， 所谓的冬天。那个时候，很多实验室都改名字了， 因为拿不到经费了。 客观来说，80年代， 一个微型计算机的它的内存只有640K字节，还不到一兆（1MB一百万字节），我们现在一张图像，随便就是几个兆的大小，它根本无法读入一张图像，还谈什么理解呢？等到我做博士论文的时候（1992-1996），我导师把当时哈佛机器人实验室最好的SUN工作站给我用，也就是32兆字节。我们实验室花了25万美元构建了一个图像采集系统，因为当时没有数字照相机。可以这么说，一直到90年代中期的时候，我们基本上不具备研究视觉这个问题的硬件条件和数据基础。只能用一些特征点的对应关系做射影几何，用一些线条做形状分析。因为图像做不了，所以80年代计算机视觉的研究，很大部分是做几何。

杨：90 年代后，就是数字照相机大量生产了。

朱：在90年代的末期的时候，发生了一个叫做感知器的革命。带动了大数据和机器学习的蓬勃发展。

杨：那机器学习与计算机视觉的关系呢？

朱：计算机视觉是一个domain， 它有很多问题要研究， 就像物理学。 而机器学习基本是一个方法和工具，就像数学和统计学。 这个名词的兴起应该还是最近的事情， 在我看来，是来自于两股人马。 80年代人工智能走入低谷后，迎来了人工神经网络的一个高潮， 所谓的从符号主义到连接主义的过渡。在中国80年代与气功、人体科学一起走红，但这基本是昙花一现。到了90年代初， 退潮之后，就开始搞 NIPS这个会议， 引入统计的方法来做。还有一股就是做模式识别的一些工程人员EECS 背景的。 按道理来说， 这个领域应该叫做 统计学习 （Statistical Learning），因为它的方法都是由概率统计领域拿来的。这些人中的领军人物很有商业头脑， 把统计和物理的数理模型， 改名叫做机器， 比如模型（model）就叫机（machine），把一些层次模型（hierarchical model）说成是“网”（net）。这样，搞出了几个“机”和“网”之后， 这个领域就有了地盘。另一方面，我的那些做统计的同事们也都老实、图个清静，不与他们去争论， 也大多无力去争。当然，统计学领域也有不少人参与了机器学习的浪潮。简单说，机器学习中的 “机器”就是统计模型，“学习”就是用数据来拟合模型。 是由做计算机的人抢占了统计人的理论和方法，然后，应用到视觉、语音语言等 domains。 我在计算机和统计两个系当教授， 看得一清二楚。 这个问题我以后可以专门讨论。

这个机器学习的群体在2000年之后，加上大量数据的到来，很快就成长了， 商业上取得很大的成功。机器学习和计算机视觉大概有百分之六七十是重合的。顺便说一句，2019年我们两个领域会在一起在洛杉矶开CVPR 和 ICML年会， 我是CVPR19的大会主席。因为学习搞来搞去，最丰富的数据是在视觉（图像和视频）。现在这次机器学习的一些大的动作和工程上的推广工作，还是从计算机视觉这边开始的。

杨：谢谢你讲述人工智能,计算机视觉和机器学习的关系。下面我们回到本次访谈的主题。刚才说了这个感知器革命是90年代以后，出了很多的数据要处理了。那么为什么马尔（Marr）在70年代末思考的问题，在面对我们当今处理这个数据的时候, 还有意义？就是说马尔用了什么方法？什么思路框架？使它有生命力？

朱：好，就回到1975-1980年这个时间段。我们今天的主题是想初步探讨一下计算机视觉的起源。我们这个领域也没有一个统一的教科书来谈这个事情。我认为视觉的起源，可以追溯到三个人，David Marr, King-Sun Fu 和Ulf Grenander。这三个人代表三个完全不同的方面，为计算机视觉这个领域奠定了基础。

杨：好， 我们逐个来介绍吧。

第三节：视觉的开创者之一：David Marr 的学术思想

朱： David Marr 【1945-1980】，中文音译为马尔， 他奠定了这个领域叫做Computational Vision计算视觉，这包含了两个领域： 一个就是计算机视觉（Computer Vision），一个是计算神经学（Computational Neuroscience）。他的工作对认知科学（CognitiveScience）也产生了很深远的影响。

我们计算机视觉CV，第一届国际会议ICCV 1987年就以David Marr的名字来命名最佳论文奖， 而且一直到2007年之前的20年间， 是CV唯一的奖项和最高的荣誉，两年一次。认知科学年会 （CogSci）也设有一个 Marr Prize给最佳的学生论文。这三个领域在80-90年代走得很近， 最近十多年交叉越来越少了。就是说，原来都是亲戚，表兄弟， 现在很少有人在之间走动了。

Marr 1972年从剑桥大学毕业，博士论文是从理论的角度研究大脑功能，具体来说，是研究的小脑， 主管运动的Cerebellum。1973年受MIT 人工智能实验室主任Minsky的邀请， 开始是做访问学者（博士后）。 1977年转为教职。 可是， 1978年冬诊断得了急性白血病。1980年转为正教授不久就去世了， 时年35岁。他在得知来日无多后，就赶紧整理了一本书，就叫 “Vision：A Computational Investigation into the HumanRepresentation and Processing of Visual Information”, 《视觉：从计算的视角研究人的视觉信息表达与处理》。他去世后由学生和同事修订，1982年出版。

杨：“Vision”2010年再版了，再版了以后在亚马逊仍然是卖得很好。

朱：它是个经典的东西。我是1989年冬天本科三年级从中科大认知科学实验室的老师那里，读到这本书的中文译本。因为缺乏背景知识，我当时基本读不懂。因为是中文，每句话都明白，但是一段话就不知道是什么意思了。在过去的20多年中， 我每隔1-2年都会再翻一翻这本书。后来我和同事花了大约8年时间，将他的一些思路转化成数理模型，比如primal sketch。

杨：这个人生故事是可以拍电影的。

朱：的确。 很多年前我与他的大弟子 Shimon Ullman饭桌上谈到这段历史， 他说当时大家到处找药，就是救不过来。当年这是一个30多岁正值科学顶峰的、交叉学科的领军人物。顺便说一句， 当年中日友好，1984播放日本电视剧《血疑》， 那是万人空巷， 感人至深。里面的大岛幸子（三口百惠饰）得的就是同样的病。

可惜， 目前计算机视觉这个领域，你如果去问学生的话，他们很多人都没听说过David Marr。“喔，想起来了，好像有个Marr奖吧”。可是你去问认知科学、神经科学的人，他们基本上对Marr非常的清楚。这也是我所担心的， 计算机视觉的发展太工程化、功利化了，逐步脱离了科学的范畴。这是短视和危险的。最近又受到机器学习来的冲击。

我这里顺便说一句， Marr 对我的另外一个间接的影响。他1973年来到MIT， 就租住在JayantShah的房子里， Shah 与 Minsky很熟， 他当时是研究代数几何（Algebraic geometry）的。 而我导师Mumford也是研究代数几何的， 并获得1974年的菲尔兹奖。他们两人很熟，后来在Shah的影响下，Mumford转入计算机视觉， 他们从提取物体边缘开始 （boundarydetection），也就是产生了著名的 Mumford-Shah 模型，搞图像处理的应用数学人员基本都是从这个模型开始做。这是后话。关于这段历史，我们以后可以展开谈。

杨：好， 那么 Marr的学术贡献是什么呢？

朱：在我看来，David Marr对我们这个学科最主要的贡献有三条。从而基本上可以说，定义了这个学科的格局。

第一条，就是说在那个时代，60年代开始的时候大家已经很多人研究视觉神经生理学、心理学问题。也有人做一些边缘检测的工作。但是，视觉到底要解决哪些问题？是怎么实现的？大家莫衷一是，谈不清楚，那么David Marr的第一个贡献就是分出了三个层次。他说， 要解决这个问题，可以把它分成计算（其实应该说成是表达）、算法、和实现三层次。首先，在表达的层次，我们问一下这是个什么问题呢？如何把它写成一个数学问题。任务是什么？输出是什么？这是独立于解决问题的方法的。其次，对这个数学问题去求解时，可以选择不同的算法， 可以并行或者串行。再次，一个算法如何在硬件上实现，可以用CPU，DSP， 或者神经网络来实现。 很多观察到的心理学和神经科学的现象都是跟系统硬件有关的东西，比如说人的一些注意机制，记忆力。这些应该从表达层面剔除。这样， 视觉就可以从纯粹的理论、计算的角度来研究了。我们可以参考心理学和神经科学的结论， 但这不是主要的。 打个比方，要造飞机， 可以参考鸟类的结构， 但关键还是建立空气动力学，才能从根本上解释这个现象， 并创造各种飞行器， 走得更远。

杨：他这么一说，今天看来好像很自然的可以理解了，但是在当时，可能没有多少人，是把问题这样分解的。

朱：当时分不开。因为当时站在像神经科学和认知科学角度，是拿一些实验现象来说事，但是不知道这个现象是在哪一层出现的。

比如神经网络和目前的深度神经网络的学习，他们的模型（表达）、算法、和实现的结构三层 是混在一起的。就变成一个特用的计算设备， 算法就是由这个结构来实现的。当它性能不好的时候，到底是因为表达不对，还是算法不对，还是实现不对？ 这个不好分析了，目前的神经网络，或者是机器学习，深度学习，它的本源存在这个问题。

以前我们审稿的时候，会追问论文贡献是提出了一个新的模型？还是一个新的算法？在哪一个层级上你有贡献，必须说得清清楚楚。2012年，我作为国际计算机视觉和模式识别年会（CVPR）的大会主席， 就发生一个事件。收到神经网络和机器学习学派的一个领军人物 LeCun的抱怨信，他的论文报告了很好的实验结果， 但是审稿的三个人都认为论文说不清楚到底为什么有这个结果， 就拒稿。他一气之下就说再也不给CVPR投稿了，把审稿意见挂在网上以示抗议。2012 年是个转折点。

现在呢？随着深度学习的红火， 这三层就又混在一块去了。 一般论文直接就报告结果， 一堆表格、曲线图。我就是这么做，然后再这么做，我在某些个数据集上提高了两个百分点，那就行了。你审稿人也别问我这个东西里面有什么贡献，哪个节点代表是什么意思，你别问，我也不知道。那算法收敛了吗？是全局收敛还是一个局部收敛？我也不知道，但是我就提高了两个百分点。

杨：或者要用多少数据来训练材料才能够呢？

朱：对，这个也不用管，而且说不清。反正我这个数据集就提高是吧？所以从这个角度来讲，它就很难是一个科学的方法。可以认为它就是一个工程或者是一个经验的，有点像中医。那么要往前再发展的时候，你必须要理清楚这三层的事情。

杨：对。

朱：那么他第二个贡献的话，是理清视觉到底要计算什么。Marr提出了一个系列的表达，从primal sketch（首要简约图）， 到2 ½ D sketch（深度简约图）， 到3D sketch。 这里面还包含了纹理、立体视觉、运动分析、表面形状、等等。比如说我要估计一个物体的深度和形状，我就估计它的光照，和物理材料特性；还有，三维几何形状怎么去表达？ 他试图去建立一个完整的体系。

现在的视觉就基本上被很多人错误地看成一个分类问题，你给我一张图像，我说这个图像里有一只狗或者没有狗，狗在哪儿都不知道。头在哪？脚在哪？不知道。Marr框架是有秩序的，现在的秩序在做深度学习的人眼中还不存在，或者没有忙过来。各人做各人的分类问题，比如说有人算这个动物分类，有的人算这个家具的分类。各种分类以后，他们之间怎么样的关系呢？要对这个图像或者场景要产生一个整体的语义解释。

第三个贡献，Marr提出了一个非常重要的概念，到现在一直还没有一个完整的解答。他说，计算视觉是一个计算的“过程”。这是什么意思？ 我们以前用贝叶斯方法（以及现在的深度网络）认为视觉就是表达成为一个后验概率，寻求一个最优解。这个解就是图像的解释。这个求解过程就会终止。可是Marr说的这个事情，它不是单纯去求一个解，而是一个连续不断的计算过程。我给你一张图像，你越看、越琢磨，你可能看到的东西会越多。

我给你一秒钟，你可能看到某些东西。我给你一分钟，你可能有另外一种理解，这两个理解可能是不一样的。还有一个重要的概念是你的任务决定了你怎么去看这个图像，比如说我在慌忙之中在做饭，那么我对这个场景，只看其中的很小一部分，足够来完成我的任务就行了。里面好多东西改变你根本没注意到。

杨：好像有些魔术就利用了这一点。

朱：就是， 很多心理学实验表明，你眼睛盯着这个图片看的时候，眼睛不眨，我告诉你这个图片在改变。你盯着看，结果它改了你都没看见。在让你看这个图片的时候，把你的注意力引到某个任务所需要计算的关键要素上，其它部分你就视而不见。视觉是受任务驱动的。而任务是时刻在改变之中。 比方说， 视觉求解不是打一个固定的靶子， 而是打一个运动目标。

杨：这听起来是一个耳目一新的概念。

朱：回到人工智能这个问题，视觉，它最后的用途，要给机器人用，机器人目前面临一个什么任务，来决定它要计算什么。这第三个贡献是在算法的层面。就是说我根据我们目前面临的任务，我才决定要计算什么。而且人的任务是在不断变化的，在此时此刻我任务都在变化，那么计算的过程中是没完没了地在改变。这个理念到目前，我们目前在研究这个事情，还没有完全实现。就是说，这将是人工智能和机器人视觉的一个关键。

杨：明白。

朱：我们现在很多人研究这个智能，比如说分类问题。他都是从谷歌的一些应用，比如搜索图片、广告投放，变成分类问题。 从而忽视了更大的本质问题。如果说人工智能往前发展机器人，要从机器人的角度来用视觉的话，那么它就有很多不同的任务。我现在做饭，我在打球，我在欣赏风景，这个时候我看到的东西是完全不一样的。我怎么样通过这千千万万的任务，而不是简单一个分类，来驱动我的计算的过程，来找到我的需求，来支持我目前的任务，这是一个巨大的研究的方向。David Marr的思想，到今天，反而意义非常重大，因为大家现在一窝蜂的去搞深度学习，把这些基本东西给忘掉了。但是这才是人工智能和机器人视觉的长远发展方向。

我前两年给过几个谈话，说研究视觉要从一个agent（执行者）的角度，带着任务进来的这么一个人或机器人，主动地去激发视觉。

目前的计算机视觉的研究还有一大部分是由视频监控的应用来驱动的，比如说我检测一些异常现象，看这个人是男还是女？那这也是一种被动的，就是说它只是在看，没有去做。要去做的话，就涉及到因果关系和更多的不确定性。所以现在的研究生觉得，他整天在做机器学习， 就在调参数，就在跟别人比拼百分之几的性能。 一些公司的研究所就报道， 他们在某某问题（数据集）上国际领先了，排名第一了。他们自己也觉得这个研究没多少意思。那是因为他们没有接触到这些基本的问题上来。

杨：他们可能还没有发现这个问题本身是多么有趣。

朱：因为作为一个科学来发展的话，那它就是要认认真真的来做，把这个理清楚。当前的火热来源于工业界， 工业界没有多少耐心资助他们的研究人员去做科学研究，大家很现实。 那么，David Marr先谈这么多好不好？以后我们可能还会继续深入谈的。

杨：好。那我们第二个人就谈一下傅京孫。

第四节：视觉的开创者之二：傅京孫（King-Sun Fu）的学术思想

朱： David Marr是从这个神经科学和脑科学这个方向来的。傅京孫【1930-1985】，他当时代表的是计算机科学，搞人工智能的人。他是一个有领导才能的人物。他和其他人于1973年组织了第一届国际模式识别会议（ICPR），并担任主席。会议后来演变成国际模式识别学会IAPR，在1976年成立，并被选为其主席。他重组了另外一个IEEE学会下面的模式识别委员会，并于1974年成为其第一任主席，创办了IEEE模式分析和机器智能（PAMI）会刊，并于1978年担任第一任总编。这是目前计算机视觉和相关领域最权威的一本期刊了。很多中国学生现在不知道，这个领域的老大本来是华人。目前， 国际模式识别学会IAPR设立了一个傅京孫奖， 作为终身成就奖， 是模式识别的最高荣誉。

杨：可惜他1985年去世了。听说去世前他每年都在中国举办讲座，并于1978年担任台湾的中央研究院院士。

朱：我正要说的这一点。他去世的时候55岁，在普渡大学，据说他的实验室是一个Chinatown。1978年中国打开国门，中国最早的一批中科院的计算机人员都到他那里进修，在普渡。所以他对中国计算机的发展，可以说是一个贡献非常巨大的人。我也是受到他的恩惠，我大学一二年级就开始跟着科大陈国良老师学习，他之前去普度进修。周末我有时就到陈老师家听他讲外面的一些研究人员和工作。你想想，计算机界那时候华人在美国站住脚的可能没几个人。

杨：对，他对中国计算机发展真的是有历史性的贡献的。我在科学院上研究生的时候，我们那些老师是说他过世太早了，要不然对中国的研究还会更好，他多活10来年就会好很多。

朱：他1985年拿到一个很大的国家项目，好像是开宴会的时候心脏病突发了。 他要是活着，华人在这个领域的话，不止是现在这个样子。不过在他之后， 稍晚一点我们有另外一个杰出华人，黄煦涛（Tom Huang）。他当时也在普渡任教，培养了大量华人研究人员。 我们以后会专门介绍。

杨：傅京孫的故事也可以拍电影。

朱：这是我们这个领域的不幸，两个奠基人很快就走了。他们刚刚把这个地基打起来，人就没了。

杨：那傅的主要贡献是什么呢？

朱：傅京孫的贡献， 我也谈三点。第一个贡献应该就是对这个学科和学会的建设，以及工程师的培养上面，他起到了开创性的作用。一般公认他是模式识别的开山鼻祖，模式识别与计算机视觉分不开的。第二个作用，就是关于他的这个句法结构性的表达与计算，就是句法模式识别，Syntactic Pattern Recognition这个词，这个词其实非常深刻。他在走之前，他那个时候也没有多少数据，那么他只是画一些图，图表性的东西，来表达他的概念，他从计算机这边来的，你想很自然就会用到形式语言，因为计算机里面的几个基础之一是形式语言。逻辑、形式语言，对吧？

杨：这好像是在编译原理里面学到过，因为编译的基础是形式语言。

朱：我们这个世界的模式， 一个最基本的组织原则是composition。一张图像就像语言、句子符合语法结构， 视频中的一个事件也有语法结构。寻找一个层次化、结构化的解释是计算视觉的核心问题。从傅京孫1985年丢下来这个摊子后，基本很少有人去碰。差不多18年以后，我和我第一个博士生继续做图像解译Image Parsing这个方向，于2003年得了Marr马尔奖。然后我和我导师专门于2006年写了一本小书，总结了图像的随机语法。我刚才谈到了，在做识别，做分类的时候，只是单独在分类某一个东西，怎么去把各个识别器和分类器给它整合在一起，变成一个统一的表达？就必须产生一个结构上的表达。现在机器学习界把它换了另外名字，叫做结构化的输出，其实是一个东西。他们提出一个新的名词，把原创的图像解译名称覆盖住，这事现在经常发生。所以我说机器学习领域经常到别人那里偷概念，改头换面。数学界不允许这样做的。我还是坚持把它叫做解译、语法。

因为语法，它就是一些规则，其实语法并不见得是一个确定性的，它可以跟统计连在一块，它也可以跟目前的一些神经网络结合，这个都没问题。它表达了一个骨架或者支柱，形成一个统一表达。

第三点，从算法的角度来讲，有一个层次化的表达以后，意义就不一样了，比如自底向上或自顶向下的计算的过程就可以在上面体现出来，就是马尔说的计算的过程，就可以在这里面体现出来。视觉的计算过程应该是由大量的自底向上（bottom-up）和 自顶向下（top-down）过程交互和同时进行的。顺便再说一句，当前的深度神经网络就是一个feedforward的自底向上的计算， 缺乏自顶向下的过程。而在人脑计算中，自顶向下的计算占据很大一部分。

杨：那就是说， 这个语法结构对计算过程有了规范和表达的途路。

朱：对，你的搜索的过程，这个计算的过程是什么？马尔他提出了第二个概念，说视觉是个计算的过程，那么这个计算过程你什么时候算哪个，这是个调度的问题，就像操作系统。那么David Marr计算的过程，没完没了的，随着你的任务不断改变，那么它就有一个调度的问题。所以说我现在要去做饭，或者我要欣赏风景，或者说我要去走路，开车，那么它的不同的任务产生了不同的进程。这个进程，要在层次化的表达里面的统一起来调度。从这个意义看，感知是计算一个解译图（parse graph）， 认知是对这个parse graph进一步推理扩大， 而机器人的任务规划（task planning）也是一个同样结构的parse graph， 那就更别说语言是用parse graph来表达的。所以，人工智能的一个核心表达就是随机的语法和解译图。

杨：对。

朱：这个是绕不掉的，不管谁来做，都要做这个事情。当然，现在有人千方百计想绕过去，重新发明一套名词， 让新来的学生忘记历史， 这样他们就可以变成社会公认的大师。有些教授、研究人员在学术上没什么原创贡献， 却在网上、社会上成了当红明星, 学科代言人。用社会上的知名度再给学术界施压。

总结一下，傅京孫三点主要贡献：一是学科的人才和组织基础，二是他提出这么一个的语法表达方法， 三是这个表达支撑了自底向上或自顶向下的计算的过程。他去世后， 这个方向一直处于一种休眠状态，我的研究有一条线是跟着这个方向做。2011年马里兰大学周少华他的导师有一个演讲，题目叫：语法模式识别—从傅到朱 （From Fu to Zhu）。我们在继承他的框架往前走。

杨：真好！那么咱们下面就谈第三个人Ulf Grenander。

朱：这个人的话，知道的人非常少。

杨：我翻看了网上资料，他是这个领域里头真正的是大神了，但绝对是个小众人物。

第五节：视觉的开创者之三：Ulf Grenander的学术思想

朱：Ulf Grenander 【1923-2016】是很少有人知道的。感觉有点像金庸小说《天龙八部》里的在藏经阁扫地的灰衣老僧。武功和思想都出神入化，但是，他基本是世外高人，不参与江湖争斗， 金庸也没有交代他的名字。所以江湖上的人大多没听说过他。 这样也好， 他自自在在活了93岁， 今年刚刚去世的。国际应用数学季刊邀请我和其他人写纪念文章，正准备出版专刊呢。

杨：对，我读他的生平，他这个人简直就是把欧洲美洲的，还有俄国的所有的精华的人物都接触过。

朱：那是，他出身在瑞典，他的导师叫Harald Cramér。概率论里面的一个重要的定理，还有数论里的一个猜想是用他命名的。然后，他也跟 Bohr（波尔），Kolmogorov（科尔莫戈罗夫）他们走得比较近。他的起点就是做概率统计， 时间序列， 随机过程，因为你现在想概率论和统计学的一些重要应用，就是那个时候发力了。

杨：从保险业开始了，北欧那边因为航海，保险业非常发达，所以这也有点道理。

朱：关于概率和统计学对于科学、视觉、以及人工智能的重要意义， Mumford 1999年写了一篇论文，是在一个大会的发言，叫做《随机性时代的曙光》（Dawning of the Age of Stochasticity）。

杨：对，那是你们老师写的， 网上能找到。

朱：他总结说，过去两千多年的西方科学的发展是建立在亚里士多德以来的数理逻辑基础之上的。但是，后面一千年包括人工智能、人的思维这些东西是随机性过程。人的思维应该是建立在概率推理基础之上。其实， 我们看到现在的机器学习， 人工智能完全就是从这个方向走了。

杨：你的导师说，整个世界的数学可以用概率的这套思想重新写一遍，就像罗素和怀特海的写这个数学原理似的，可以把数学重新建立起来，用概率的这种思想。

朱：这个工作已经有人做了。E. T. Jaynes就是发明最大熵原理的那个人，他写了一本很厚的书，《Probability Theory: The Logic of Science》， 他就是用这个原理去写。这也是一篇遗作。他没写完就过世了。这也是以后可以谈的话题。

朱： Ulf Grenander就诞生在这么一个概率发源的中心的地带，跟几个大师学习，博士毕业后出来游历，做概率论随机过程的这些东西。到六、七十年代的时候，他就开始提出来，想用数学来把这个模式识别与智能的现象的问题定义清楚。我们前面谈到的David Marr 是从神经科学、认知科学来的。傅京孫是一个计算机科学与工程的人。这两者基本没有多少严格的数学定义，提出的框架是漂浮的。Ulf是从数学的角度，奠定基础。他提出来一个应用数学的分支， 叫做 Pattern Theory。他的出发点完全不同， 就是要给世界上的各种模式、现象， 建立一个数学的框架来研究。 格局就很宏伟。而不是急于去解决某种实际问题， 后者叫做模式识别 （pattern recognition）。 他在90岁高龄出版了最后一本书， 想用数学来研究人的思想是从哪里来的。 你看我们脑袋里的念头、主意也往往是随机产生，像冒泡一样， 所谓思如泉涌。到底怎么来的？

杨：那太了不起了。这个事说起来，我想到当时我的老师是让我读Geman and Geman 1984年的吉布斯采样算法，那就已经了不起了。

朱：Grenander最后落脚在布朗大学应用数学系，Geman是他当年（70年代末80年代初）招到组里的年轻教员之一。这个吉布斯采样（Gibbs Sampler）的算法是一个里程碑的东西，在80年代初引起轰动。但那只是这个学派的诸多贡献的一个片段。

Grenander的理论解释起来的确有点费劲，既然谈历史，我先从我个人的经历谈一下。

他1994年出了一部总结性的书，900多页，叫做《General Pattern Theory》，广义模式理论。有点爱因斯坦做广义相对论的意思。但这本书很抽象， 没多少人读。我1995年在哈佛研究纹理模型（texture models），因为我用的学习算法就是吉布斯采样，在训练的时候，跑一遍要等两个星期才收敛，机器被占了，我就有时间，也是耐着性子把这本书读完了。我估计世界上不超过20人，能有耐心完整地读他的书。然后，我1996年1月答辩论文，我导师和我每周开车去布朗大学参加讨论。波士顿的冬天很冷， 哈佛到布朗1个小时左右，漫天大雪， 我们有时在高速上车被陷住， 下来铲雪。到了6月， 我导师从哈佛提前退休，带着我一起加入布朗的应用数学系。那在当时是一个学术思想的中心。组会里有Grenander，Mumford， Geman 还有其他20来人， 一坐就是2个多小时。这些人都明察秋毫， 做报告的人无法含混过去的， 一步一步都必须理清楚，说不清楚你就下去想， 下次再来。

我一直认为计算机视觉和模式识别领域亏欠Grenander, 因为统计建模和随机计算逐渐成为我们领域的核心理论基础，而大家并不知道，很多思想、算法都源于这个人或者他的学派。所以，2012年， 我主持CVPR（国际计算机视觉和模式识别）大会， 特意放到布朗大学附近召开，我和另外两个主席一说，大家立即就同意了。并特制了一个银质的大奖章， 在大会上颁给他，表达我们的敬意。这里发生很多故事，我们以后再谈吧。

杨：那你能简短总结一下Grenander对计算机视觉、甚至人工智能的主要贡献吗。

朱：还是谈三点主要的吧。 首先，他提出了一个思想， 叫做 analysis-by-synthesis， 这是所谓 产生式建模的核心理念。当你要去识别、分析一个模式，比如一个动物，人脸， 一个事件， 你首先要建立一个数理模型， 这个模型通过数据来拟合， 也就是当前的机器学习。 那么， 判断这个模型好坏， 或者模型是否充分，的一个依据是什么呢？产生式建模的方法就是对这个模型随机抽样，也就是，合成（synthesis）。 我把这个过程直观叫做“计算机之梦”。计算机模型一开始初始化为空（完全随机）， 那它做的梦就是白噪声， 或者一张白纸。通俗来说， 这个模型就是一个“白痴”。人脑有这个功能，我们把眼睛一闭，没有外界输入了，就能做梦， 白日梦就是想象力的体现。一个好的模型采样产生的图片（模式）， 与真实观察的图片（模式）， 就应该是真假难辨。如果你能分辨，那说明这个模型不到位。 现在很多机器学习的方法是没法去随机合成图片的。 举个例子来说，我要检验你是不是真的听懂和理解中文，就看你能不能说流利的中文。如果你说话语法有错，词汇量不够，或者有口音，那就揭示你在哪方面还需要提高。

杨：这个要求好像比光是听懂 要更严格。

朱：的确。我们当年考英语， 多半是读，说和写都不行。我们考TOEFL， GRE Verbal的时候， 就算没搞懂， 也能蒙个60%-70%。 新东方的题海战术也很奏效。当你做了大量考题， 就算不懂， 也能考好。当前大数据、机器学习就用题海战术。 这个方法强调在实战中检验，考什么就拼命复习什么，不考的东西就不学，这也很有道理，很直接， 来得快。 但是， 因为你的模型没有真正理解， 没有“真懂”，考试大纲外面的东西更不懂， 那么后遗症就是， 遇到新考题， 缺乏泛化能力，遇到新问题，缺乏创造力。

想一想， 如果我的学生一步步考试都是靠题海战术这么学过来的， 那多可怕，要让他们去搞研究、创新，那就基本不可能。很遗憾的是，现在中国学生从幼儿园开始，就是在题海中泡大的。机器人、人工智能，靠题海战术是可以演示不少功能的， 但是， 那还离真正的智能比较遥远。

杨：好， 我明白这个analysis-by-synthesis 的意义了。他的第二贡献呢？

朱：他提出了一整套建模的理论和方法。把代数、几何、概率整合起来。 代数指的是一些结构，比如群论， 记得在科大本科我学过 群、环、域这些概念吧？也就是说我有一些基本元素，叫 generator，连接成为图graph，然后是群group，在上面进行操作, 产生了各种各样的变化。还有很多几何， 变换， 在连续情况就产生形变。通过组合，语法、产生丰富的图模式。然后，再在这个图模式的空间上定义距离（测度）和概率。

朱：比如一个概率模型， 是定义在一个什么样的结构上，它是个什么样的解空间？这个数理上你必须交代清楚，否则你的论文写不下去了。现在它的一个很大的应用在医疗图像上面，比如说一个病人，他的肝变形了，那么他的肝的形状和正常人的肝的形状之间怎么定义一个合理的距离？两张人脸，怎么定义这个距离的呢？这个距离定义在一个流型上，数学的流型（manifold）。

杨：这些东西真用上了吗？

朱：他有个Postdoc，名叫Michael Miller， 现在是Johns Hopkins 大学图像中心主任， 就用这一套方法来做医疗图像、脑科学（Brain Mapping）等方面的应用。

杨：他的第三方面的贡献呢？

朱：第三个方面主要是算法上面。当我们去做求解的时候，在一个解空间，这个求解空间肯定是一个非凸的，他有千千万万的局部最优解local minimum 在里面。

杨：对。这是当时八十年代的时候提出来一个很尖锐的问题，好像有什么模拟煺火方法。

朱：很多蒙特卡洛算法都是他和这个学派的人提出来的。这个解空间是一个异构空间，空间里面非常复杂的，包含有很多子空间，子空间里面又包含又子空间，每个子空间维度又不一样，他们之间，从一个解跳到另外一个解的时候，这跳转必须是可逆的。在计算机里面就叫可以回溯。从这个学派走出来的人，他们设计算法每一个步骤都是有章法的，要做到合规合矩。包括上面提到的吉布斯采样算法、可逆蒙特卡洛跳转法，还有变分法（variational methods）和偏微分方程式， 还有一些随机下降法（stochastic gradient）， 这后者是目前训练深度学习模型的主要办法。他也开创了非参数模型的学习方法。这里面东西太多，先谈到这里吧。

正因为很多人没有接触过Grenander的理论， 缺乏这方面的理论素养， 造成我们学科发展的一个巨大的问题：很多教授、博士、研究生就是用别人的模型（机），拿来调试，基本缺乏自己发明新模型、新算法的能力。我们这个领域，很多美国名牌大学助理教授、副教授、教授， 他们的论文中的公式错误百出。现在干脆大家在论文中都不写公式了， 直接报告最后的实验结果，提高了几个百分点。这就“一俊掩百丑”了。 英文有个类似的说法叫做 “sweep the dirt under the carpet把污垢扫到地毯下”。 这些人在大量培养博士、他们出来的人评审论文。 这样一来，学科的发展堪忧！

第六节：结束语

杨：听了你番谈话，我明白很多。记得我当时念研究生，包括念博士生的时候，实际上是很糊涂的。就是对这个领域到底做多少东西，没有信心。觉得很多研究像画鬼一样，原理不清楚。我觉得那样的话，与其那样做事情, 那不如干脆到工业界那更快乐。

朱：正因为我们这个领域很多历史、框架性的东西，没有搞清楚，培养出来的博士，缺乏分析能力。大家被一些工程的任务和数据驱动，被一些性能的指标牵制，对科学的发展比较迷茫。

杨：好， 谈了很多， 我们做个总结吧。

朱：那我就说两点。

首先， 我在开场白中提到 “一个民族如果忘记了历史, 她也注定将失去未来。”一个学科要健康发展，需要研究人员、研究生们理解自己领域的历史和大的发展方向，建立文化的认同。否则，自己家的东西，被别人偷取，浑然不知。就像日本打入中国，想把我们的地名改掉，大家开始说日语，把名字都改做山本太郎之类，感觉很酷吗？ 或者是韩国人把中国的文化拿去申报世界文化遗产，这都是要制止的。否则，过了一代人，还真说不清楚了。我记得刚来美国的时候，美国同事把汉字叫做“Kang-ji”，说是日本字。 我们领域很多人对保护这个领域的文化和传统缺乏清醒认识。皮之不存，毛将焉附？

其次，一个学科内部，大家互相不够了解，各自为政。特别现在会议审稿人很多是研究生，以自己的狭窄的眼光和标准去评判别人的方法，造成很多混乱。搞工程的看不到理论的重要性，反之亦然。大家又都疏远心理学和认知科学的研究。我提倡我们的研究人员、学生要提高理论修养、培养长远眼光，向相关学科取经，取长补短。

我希望这个微信公众号，能够帮助大家正视问题，让计算机视觉这个领域健康、稳健、可持续地发展。

文本挖掘

1.背景

随着互联网的大规模普及和企业信息化程度的提高,文本信息的快速积累使公司、政府和科研机构在信息处理和使用中面临前所未有的挑战。一方面,互联网和企业信息系统每天都不断产生大量文本数据,这些文本资源中蕴含着许多有价值的信息;而另一方面因为技术手段的落后,从大量数据资源中获取需要的信息十分困难。人们迫切需要研究出方便有效的工具去从大规模文本信息资源中提取符合需要的简洁、精炼、可理解的知识,文本挖掘就是为解决这个问题而产生的研究方向。

传统的自然语言理解是对文本进行较低层次的理解,主要进行基于词、语法和语义信息的分析,并通过词在句子中出现的次序发现有意义的信息。在这一层次遇到的问题多与句法和语义歧义性相关。对文本较高层次的理解主要集中在研究如何从各种形式的文本和文本集中抽取隐含的模式和知识。文本高层次理解的对象可以是仅包含简单句子的单个文本也可以是多个文本组成的文本集,但是现有的技术手段虽然基本上解决了单个句子的分析问题,但是还很难覆盖所有的语言现象,特别是对整个段落
或篇章的理解还无从下手。

在19世纪早期发展起来的以统计技术为基础的数据挖掘技术已经发展的较为成熟,并在大规模结构化关系数据库上应用取得成功。将数据挖掘的成果用于分析以自然语言描述的文本,这种方法被称为文本挖掘(Text Mining, TM)或文本知识发现(Knowledge Discovery in Text, KDT)。与传统自然语言处理(Natural Lnaguage Proeessing, NLP)关注词语和句子的理解不同,文本挖掘的主要目标是在大规模文本集中发现隐藏的有意义的知识,即对文本集的理解和文本间关系的理解。因此,文本挖掘是自然语言处理和数据挖掘技术发展到一定阶段的产物。

在现实世界中,可获取的大部信息是以文本形式存储在文本数据库中的,由来自各种数据源的大量文档组成,如新闻文档、研究论文、书籍、数字图书馆、电子邮件和Web页面。由于电子形式的文本信息飞速增涨,文本挖掘已经成为信息领域的研究热点。

2.定义

文本数据库中存储的数据可能是高度非结构化的,如Web网页;也可能是半结构化的,如Email消息和一些XML网页;而其它的则可能是良结构化的。良结构化文本数据的典型代表是图书馆数据库中的文档,这些文档可能包含结构字段,如标题、作者、出版日期、长度、分类等等,也可能包含大量非结构化文本成分,如摘要和内容。通常,具有较好结构的文本数据库可以使用关系数据库系统实现,而对非结构化的文本成分需要采用特殊的处理方法对其进行转化。

文本挖掘是一个交叉的研究领域,它涉及到数据挖掘、信息检索、自然语言处理、机器学习等多个领域的内容,不同的研究者从各自的研究领域出发,对文本挖掘的含义有不同的理解,不同应用目的文本挖掘项目也各有其侧重点。因此,对文本挖掘的定义也有多种,其中被普遍认可的文本挖掘定义如下:

定义: 文本挖掘是指从大量文本数据中抽取事先未知的、可理解的、最终可用的知识的过程,同时运用这些知识更好地组织信息以便将来参考。

直观的说,当数据挖掘的对象完全由文本这种数据类型组成时,这个过程就称为文本挖掘。

文本挖掘也称为文本数据挖掘[Hearst97]或文本知识发现[Fedlmna95],文本挖掘的主要目的是从非结构化文本文档中提取有趣的、重要的模式和知识。可以看成是基于数据库的数据挖掘或知识发现的扩展F[ayyda96,Simoudis96]。

文本挖掘是从数据挖掘发展而来,因此其定义与我们熟知的数据挖掘定义相类似。但与传统的数据挖掘相比,文本挖掘有其独特之处,主要表现在:文档本身是半结构化或非结构化的,无确定形式并且缺乏机器可理解的语义;而数据挖掘的对象以数据库中的结构化数据为主,并利用关系表等存储结构来发现知识。因此,有些数据挖掘技术并不适用于文本挖掘,即使可用,也需要建立在对文本集预处理的基础之上。

3.文本挖掘过程

文本知识发现主要由以下步骤组成：

文档集合---[文本预处理]--->文档中间形式----[文本挖掘]----->模式----[评估与表示]----->知识

1)文本预处理:

选取任务相关的文本并将其转化成文本挖掘工具可以处理的中间形式。

文本集--->特征抽取--->特征选择--->文本特征矩阵

通常包括两个主要步骤:

(a)特征抽取:建立文档集的特征表示,将文本转化成一种类似关系数据且能表现文本内容的结构化形式,如信息检索领域经常采用的向量空间模型就是这样一种结构化模型。

(b)特征选择:一般说来结构化文本的特征空间维数较高,需要对其进行缩减,只保留对表达文本内容作用较大的一些特征。

2)文本挖掘:

在完成文本预处理后,可以利用机器学习、数据挖掘以及模式识别等方法提取面向特定应用目标的知识或模式。

3)模式评估与表示
最后一个环节是利用已经定义好的评估指标对获取的知识或模式进行评价。如果评价结果符合要求,就存储该模式以备用户使用;否则返回到前面的某个环节重新调整和改进,然后再进行新一轮的发现。

4.研究现状

在文本挖掘过程中,文本的特征表示是整个挖掘过程的基础;而关联分析、文本分类、文本聚类是三种最主要也是最基本的功能。

4.1文本特征表示

传统数据挖掘所处理的数据是结构化的,其特征通常不超过几百个;而非结构化或半结构化的文本数据转换成特征向量后,特征数可能高达几万甚至几十万。所以,文本挖掘面临的首要问题是如何在计算机中合理的表示文本。这种表示法既要包含足够的信息以反映文本的特征,又不至于太过庞大使学习算法无法处理。这就涉及到文本特征的抽取和选择。

文本特征指的是关于文本的元数据,可以分为描述性特征,如文本的名称、日期、大小、类型以及语义性特征,如文本的作者、标题、机构、内容。描述性特征易于获得,而语义特征较难获得。在文本特征表示方面,内容特征是被研究得最多的问题。

当文本内容被简单地看成由它所包含的基本语言单位(字、词、词组或短语等)组成的集合时,这些基本的语言单位被称为项(Term)。如果用出现在文本中的
项表示文本,那么这些项就是文本的特征。

对文本内容的特征表示主要有布尔模型、向量空间模型、概率模型和基于知识的表示模型。因为布尔模型和向量空间模型易于理解且计算复杂度较低,所以成为文本表示的主要工具。

(1)特征抽取

中文文档中的词与词之间不像英文文档那样具有分隔符,因此中、英文文档内容特征的提取步骤略有不同。

英文文档集合--->消除停词--->词干抽取--->特征词集合
中文文档集合--->消除停词--->词语切分--->特征词集合

消除停词:
文本集有时包含一些没有意义但使用频率极高的词。这些词在所有文本中的频率分布相近,从而增加了文本之间的相似程度,给文本挖掘带来一定困难。解决这个问题的方法是用这些词构造一个停词表或禁用词表(stop word list)[Ricardo1991],在特征抽取过程中删去停词表中出现的特征词。

常用的停词包括虚词和实词两种,如

(i)虚词:英文中的”a,the,of,for,with,in,at,…”
中文中的”的,地,得,把,被,就…”

(ii)实词:数据库会议上的论文中的“数据库”一词,可视为停词。

词干抽取:

定义: 令V(s)是由彼此互为语法变形的词组成的非空词集,V(s)的规范形式称为词干(stem)。

例如,如果V(s)={connected,connecting,connection,connections},那么s=connect 是V(s)的词干。

词干抽取(stemming)有四种不同的策略:词缀排除(affix rermoval)、词干表查询(table lookup)、后继变化(successor variety)和n-gram。其中词缀排除最直观、简单且易于实现。多数词的变形是因添加后缀引起的,所以在基于词缀排除策略的抽取算法中后缀排除最为重要,Porter算法[Porter80]是后缀排除算法中最常用的一种。

词干抽取将具有不同词缀的词合并成一个词,降低文本挖掘系统中特征词的总数,从而提高了挖掘系统的性能。

当然,也有两点需要注意:

(1)词干抽取对文本挖掘性能的提高仅在基于统计原理的各种分析和挖掘技术下有效。在进行涉及语义和语法的自然语言处理时,不适宜采用词干抽取技术。

(2)词干抽取对文本挖掘或信息检索准确性的影响至今没有令人信服的结论,因此许多搜索引擎和文本挖掘系统不使用任何词干抽取算法。

汉语切分:

汉语的分词问题己经基本解决,并出现了多种分词方法。这些分词方法可以分为两类:一类是理解式分词法,即利用汉语的语法知识、语义知识及心理学知识进行分词;另一类是机械式分词法,一般以分词词典为依据,通过文本中的汉字串和词表中的词逐一匹配完成词语切分。第一类分词方法算法复杂,实际应用中经常采用的是第二类分词方法。机械式分词法主要有正向最大匹配法,逆向最
大匹配法,逐词遍历法。

由于词典的容量有限,在大规模真实文本处理中,会遇到许多词典中未出现的词,即未登录词。未登录现象是影响分词准确率的重要原因。为解决这个问题,人们提出利用N-gram语言模型进行词项划分[周01a,01b],从而摆脱基于词典的分词方法对词典的依赖。与基于词典的分词方法不同,基于N-gram技术得到的词项不一定具有实际意义。

例如:“文本挖掘”的所有N-gram项为:

1-gram:文,本,挖,掘
2-gram:文本,本挖,挖掘
3-gram:文本挖,本挖掘
4-gram:文本挖掘

其中除1-gram是单字外,2-gram中的“本挖”,3-gram中的“文本挖”,“本挖掘”都不具有实际意义。

(2)特征选择

特征选择也称特征子集选择或特征集缩减。经过特征抽取获得的特征词数量很多,有时达数万个特征。如此多的特征对许多文本挖掘方法,如文本分类、聚类、文本关联分析来说未必都是有意义的;而过大的特征空间还会严重影响文本挖掘的效率,因此选择适当的特征子集十分必要。

通常采用机器学习的方法进行文本特征选择。虽然机器学习中有许多选取特征子集的算法,但有些算法复杂且效率低下,不适于处理庞大的文本特征集。

国外对特征选择的研究较多[Mladenic99,Mladenic03,Lewis92,Liu96],特别是已有专门针对文本分类特征选择方法的比较研究[Yang97]。国内对这一问题的研究以跟踪研究为主,集中在将国外现有特征评估函数用于中文文本特征选择[周
02]及对其进行改进[李99]。

4.2基于关键字的关联分析

文本数据一旦被转化成结构化中间形式后,这种中间形式就作为文本挖掘过程的基础。

与关系数据库中关联规则的挖掘方法类似,基于关键词的关联规则产生过程包括两个阶段:

关联挖掘阶段:
这一阶段产生所有的支持度大等于最小支持度闭值的关键词集,即频繁项集。

规则生成阶段:
利用前一阶段产生的频繁项集构造满足最小置信度约束的关联规则。

Feldman等人实现了基于上述思想的文本知识发现系统KDT[Feldman96]、FACT[Feldman97],KDT系统在Reuter22173语料集中发现的关联规则示例:

[Iran,Nicaragua,Usa]->Reagan 6/1.00
[gold,copper]->Canada 5/0.556
[gold,silver]->USA 19/0.692

根据不同的挖掘需要,可以利用不同的挖掘方法,如关联挖掘、最大模式挖掘或层次关联挖掘,完成相应的文本分析任务。

4.3文本分类

文本分类是文本挖掘中一项非常重要的任务,也是国内外研究较多的一种挖掘技术。在机器学习中分类称作有监督学习或有教师归纳,其目的是提出一个分类函数或分类模型(也称作分类器),该模型能把数据库中的数据项映射到给定类别中的一个。

一般来讲,文本分类需要四个步骤:

(1)获取训练文本集:训练文本集由一组经过预处理的文本特征向量组成,每个训练文本(或称训练样本)有一个类别标号;

(2)选择分类方法并训练分类模型:文本分类方法有统计方法、机器学习方法、神经网络方法等等。在对待分类样本进行分类前,要根据所选择的分类方法,利用训练集进行训练并得出分类模型;

(3)用导出的分类模型对其它待分类文本进行分类;

(4)根据分类结果评估分类模型。

另外需要注意的是,文本分类的效果一般和数据集本身的特点有关。有的数据集包含噪声,有的存在缺失值,有的分布稀疏,有的字段或属性间相关性强。目前,普遍认为不存在某种方法能适合于各种特点的数据[Yang99a,Yang99b]。

随着nIetmet技术的发展和普及,在线文本信息迅速增加,文本分类成为处理和组织大量文本数据的关键技术。而近二十多年来计算机软、硬件技术的发展和自然语言处理、人工智能等领域的研究进展为文本自动分类提供了技术条件和理论基础。迄今为止,文本分类研究已经取得了很大的进展,提出了一系列有效的方法,其中分类质量较好的有k最近邻(k-Nearest Neighbor,KNN),[Iwayama95,Yang97,Yang99a]、支持向量机(Support Vector Machine,SVM)[Joachims98]、朴素贝叶斯(Naive Bayes,NB)[Lewis94,Chakra97,Lewis98]。1998年文献[Liu98]提出了基于关联规则的分类方法CBA,此后陆续有人进行这方面的研究,如CAEP[Dong99]、JEP[Li00a,Li00c]、DeEPs[Li0Ob]、CMAR[Li01]和用于文本分类的ARC[Zaiane02]。

国内对中文文本自动分类的研究起步较晚,尽管己有一些研究成果[李04,姚03,邹99,周01a],但由于尚没有通用的标准语料和评价方法,很难对这些成果进行比较。而对基于关联规则的文本分类的研究在国内还未见到。

4.4文本聚类

文本聚类是根据文本数据的不同特征,将其划分为不同数据类的过程。其目的是要使同一类别的文本间的距离尽可能小,而不同类别的文本间的距离尽可能的大。主要的聚类方法有统计方法、机器学习方法、神经网络方法和面向数据库的方法。在统计方法中,聚类也称聚类分析,主要研究基于几何距离的聚类。在机器学习中聚类称作无监督学习或无教师归纳。聚类学习和分类学习的不同主要在于:分类学习的训练文本或对象具有类标号,而用于聚类的文本没有类标号,由聚类学习算法自动确定。

传统的聚类方法在处理高维和海量文本数据时的效率不很理想,原因是:
(1)传统的聚类方法对样本空间的搜索具有一定的盲目性;
(2)在高维很难找到适宜的相似度度量标准。

虽然,文本聚类用于海量文本数据时存在不足。但与文本分类相比,文本聚类可以直接用于不带类标号的文本集,避免了为获得训练文本的类标号所花费的代价。根据聚类算法无需带有类标号样本这一优势,Nigam等人提出从带有和不带有类标号的混合文本中学习分类模型的方法[Ngiam98]。其思想是利用聚类技术减少分类方法对有标号训练样本的需求,减轻手工标记样本类别所需的工作
量,这种方法也称为半监督学习。

文本聚类包括以下四个步骤:

(1)获取结构化的文本集。

结构化的文本集由一组经过预处理的文本特征向量组成。从文本集中选取的特征好坏直接影响到聚类的质量。如果选取的特征与聚类目标无关,那么就难以得到良好的聚类结果。对于聚类任务,合理的特征选择策略应是使同类文本在特征空间中相距较近,异类文本相距较远。

(2)执行聚类算法,获得聚类谱系图。聚类算法的目的是获取能够反映特征空间样本点之间的“抱团”性质。

(3)选取合适的聚类阈值。在得到聚类谱系图后,领域专家凭借经验,并结合具体的应用场合确定阈值。阈值确定后,就可以直接从谱系图中得到聚类结果。

目前,常见的聚类算法可以分成以下几类[Han01]:

(1)平面划分法:对包含n个样本的样本集构造样本集的k个划分,每个划分表示一个聚簇。常见的划分聚类算法有k-均值算法,k-中心点算法,CLARANS算法。

(2)层次聚类法:层次聚类法对给定的样本集进行层次分解。根据层次分解方向的不同可分为凝聚层次聚类和分裂层次聚类。凝聚法也称为自底向上的方法,如AGNES;分裂法也称自顶向下的方法,如DIANA、CURE、BIRCH、Chameleon。

(3)基于密度的方法:多数平面划分法使用距离度量样本间的相似程度,因此只能发现球状簇,难以发现任意形状簇。基于密度的聚类法根据样本点临近区域的密度进行聚类,使在给定区域内至少包含一定数据的样本点。DBSCAN就是一个具有代表性的基于密度的聚类算法。

(4)基于网格的方法:采用多分辨率的网格数据结构,将样本空间量化为数量有限的网格单元,所有聚类操作都在网格上进行,如STING算法。

(5)基于模型的方法:为每个簇假定一个模型,然后通过寻找样本对给定模型的最佳拟合进行聚类。

有些聚类算法集成多种算法的思想,因此难以将其划归到上述类别中的一类,如CLIQUE综合了密度和网格两种聚类方法。

文本聚类有着广泛的应用,比如可以用来:

(1)改进信息检索系统的查全率和查准率[Ricardo99];

(2)用于文本集浏览[Cutting92];

(3)搜索引擎返回的相关文本的组织[Zamir97];

(4)自动产生文本集的类层次结构[Koller97]。在带有类标号的文本集上发现自然聚类[Aggarwal99],然后利用自然聚类改进文本分类器。

5.文本挖掘与相近领域的关系

5.1自然语言处理与文本挖掘的区别

文本挖掘与自然语言处理有着千丝万缕的联系,但也存在明显的不同:

(1)文本挖掘通过归纳推理发现知识,而传统的自然语言处理多采用演绎推理的方法,很少使用归纳推理方法。

(2)文本挖掘在大规模文本集而不是少数文本中发现知识,其目的不在于改善对文本的理解而是发现文本中的关系。虽然自然语言处理的两个新兴领域:信息检索(Information Retrieval,IR)和信息提取(Information Extraction,IE)也是以大规模文本集为对象,但只要使用严格的演绎推理,那么就不能称作文本挖掘。主要原因是它们没有发现任何知识,只是发现符合某种约束条件的文本而不是知识本身。

[比较][方法不同][目标不同][对象范围不同]
自然语言处理：[演绎推理方法][更好的理解文本][以一篇或少数文本为研究对象，发现表示文本特点的关系]
文本挖掘：[归纳推理方法][更好的使用文本][以大量文本组成的文本集为研究对象，在文本集中发现文本间或文本集中词与词之间的关系]

1)信息检索与文本挖掘

信息检索是与数据库技术并行发展多年的领域,其中以文本为对象的文本信息检索以非结构或半结构化数据为处理对象,研究大量文本的信息组织和检索问题。

文本信息检索主要发现与用户检索要求(如关键词)相关的文本。例如,基于关键词的文本检索使用相关度量计算文本与用户查询间的相关性并按相关程度高低排序获得的文档。

近年来,基于自然语言处理技术发展起来的智能检索技术包含了对歧义信息的检索处理,如“苹果”,究竟是指水果还是电脑品牌;“华人”与“中华人民共和国”的区分,这类检索通过歧义知识描述库、全文索引、上下文分析以及用户相关反馈等技术实现文本信息检索的智能化。与文本挖掘不同,智能信息检索仍然只是关注从文本集中更有效地识别和提取相关文档,而不发现任何新的信息或知识。

2)信息提取与文本挖掘

信息提取(IE)是指提取文本集中预定义的事件或任务信息的过程,例如关于恐怖事件信息的提取,可以包括事件时间,地点,恐怖分子,受害者,恐怖分子采用的手段等等。其目的在于发现文本中的结构模式。主要过程是先根据需要确定结构模式,然后从文本中提取相应的知识填进该结构模式。文本挖掘任务则与之正好相反,它需要自动发现那些IE中给定的模式。

5.2文本挖掘与相关领域的交叉

虽然以上介绍的研究领域与文本挖掘存在明显的不同,但它们在某种程度上也存在交叉。最典型的交叉就是通过技术和方法的互相借鉴为各自领域提供新的有效的方法,如许多文本挖掘系统中采用的预处理方法就是最先在信息检索领域中提出并使用的。除此之外,还有其它的例子,如:

(1)基于文本挖掘的汉语词性自动标注

利用文本挖掘研究词及词性的序列模式对词性的影响是非常有新意的研究,这与人在根据上下文对词性进行判断的方法是一致的,不但根据上下文的词、词性,而且可以根据二者的组合来判断某个词的词性。

国内从数据挖掘的角度对汉语文本词性标注规则的获取进行了研究[李01]。其方法是在统计语料规模较大的情况下,利用关联规则发现算法发现词性标注规则。只要规则的置信度足够高,获得的规则就可以用来处理兼类词的情况。该过程完全是自动的,而获取的规则在表达上是明确的,同时又是隐含在数据中、用户不易发现的。

(2)基于信息抽取的文本挖掘

为将非结构化的自然语言文档表示成结构化形式以便直接利用传统的数据挖掘技术来进行文本挖掘。已有多种结构化方法被提出,如前面提到的文本特征表示方法就是最典型的一种。此外,随着信息抽取技术的不断发展[Freitag98,Clifton99],它在文本挖掘领域扮演着日益重要的角色。信息抽取的主要任务是从自然语言文本集中查找特别的数据段,然后将非结构化文档转化为结构化的数据库,以便更容易地理解文本。基于信息抽取
的文本挖掘系统框架[Nahm01]:

Text->{Information Extraction->DB->KDD}->Rule Base

在这个系统中,IE模块负责在原始文本中捕获特别的数据段,并生成数据库提供给知识发现模块进一步挖掘。

5.3文本挖掘技术在Email处理方面的应用

由于Email文档和普通文档之间有许多相似之处,所以可以将挖掘普通文档涉及的技术和方法用于Email信息挖掘。目前,有许多关于利用文本挖掘技术有效地组织和分析Email信息的研究。例如,通过分析Email的语言和作者性别群进行计算机取证[Rajman97];将Email信息的结构特征和语言学特征与SVM结合进行作者身份鉴别。

文本挖掘技术除了用于组织Email信息外,还可以用于对Email消息进行分类。如:利用朴素贝叶斯算法[Rennie00]、Rocchio算法、SVM方法和Bayesian方法[sahami98,Andr00,Sakkis01]对Email信息进行分类和过滤。此外,文献[Cohen96]和[Lewis94]则提出两个基于规则的系统,这两个系统都是利用文本挖掘技术来分类Email信息。

天下第一铭

作者：汤晓鸥

2003年3月8日，陪秋梅过了最后一个属于我们二人世界的妇女节（一直觉得妇女节比情人节重要），第二天，我们安静的二人世界就变成了吵闹的三口之家。新来的第三者白白胖胖，叫铭铭，是在香港威尔士亲王医院10层楼的产科病房出生的。铭铭出生的那天，11层楼住进了一个特殊的病人，说是肺病。可是我们那几天太高兴了，根本没注意。过了两天医生叫我们去他办公室问我们要不要提前出院，因为楼上有个传染病人。我们觉得还有很多东西要和护士学，肺炎也没什么可怕的，不想早出院。等我们回到病房，发现一个层楼的新任妈妈都在收拾行李,已经走的差不多了。我们才明白问题很严重。回家后的两个多月，再没敢带铭铭出门一步。后来才知道11层的病人是香港第一例SARS.

铭铭的全名叫汤之铭，是佛教大师南怀瑾先生起的名字。一直觉得是老先生取的名字保佑了铭铭。名字是老先生根据2000多年前的一部畅销书《大学》里面的典故起的。经历了SARS的苦其心志，又有老先生的保佑, 我一直觉得天将降大任于铭铭，常和秋梅讲，铭铭将来很可能成就“天下第一铭”。真是想什么来什么，果然四个月大时，就显灵了。

那时我父母第一次从国内来看铭铭，第二天就要到了，可是我们一直在为一件很头疼的事伤脑筋，铭铭已经14天没大便了，看了几次医生，都说孩子活蹦乱跳的没问题，可能消化太好，听医生讲14 天可能是香港地区的纪录了，不知是不是华南地区纪录。不管怎样说，我儿子有了他自己的第一个地区级纪录了，可惜后来再没能破此纪录，最多一次才四天，可能上次太难受了，看来铭铭也不傻，不愿为虚名太苦了自己。好在我父母来的头一天，问题解决了。父母来了后抱着铭铭说，这孩子没照片上看着胖了，怎么这么轻，我当时后悔不已，不该逼铭铭做他不愿意做的事，否则铭铭至少比头一天重一倍。这孩子其实用心良苦。

铭铭六个月大的时候，妈妈的假期结束了，不得不回北京工作了。铭铭当然毫不犹豫地决定跟妈妈走（主要是从他的哭声中判断的），这样我又开始了对微软亚洲研究院的经久不息的访问。可能是访问实在太频了，结果我访问的媒体计算组的主任，时任研究院副院长的张宏江问我愿不愿意接管他的媒体计算组，还没等我们开始谈条件，没过多久，研究院重组，宏江成了新成立的工程院院长，另一位副院长Harry(沈向洋)成了研究院新院长。Harry好像觉得我来管媒体计算组不大合适。我也没问为啥。过了没多久，一个周三的下午，Harry突然来电邮说想和我谈谈。原来Harry想找我接管他自己的视觉计算组，又觉得对不起媒体计算组，所以干脆将两个组合并成一个，问我愿不愿带。我第二天就答应了，Harry也怕夜长梦多，隔天我们就把很多细节敲定了，没有经过任何面试，我就在几天之内成了研究院的人了。周六，我就买了房子。那一周，感觉上像两个恋人生怕对方反悔而匆匆领了结婚证。

我当然不会反悔，我对研究院其实爱慕已久，研究院在我心里很像铭铭，大有天下第一铭的气势。我一直觉得Bill一生中做了两个了不起的决定，第一是和IBM签了DOS协议，第二就是建立了微软亚洲研究院。当然，有些同学可能不同意这种说法，我有时也想，和世界上最大的计算机公司签约怎么能和同世界上最大的国家签约相比呢，所以也许建立了亚洲研究院应该更重要。

北京的学校差不多集中了中国十几亿人中最优秀的人才。研究院是中国唯一的一所由跨国公司成立的从事基础研究的地方。和国外一流研究机构相比，研究院近水楼台；和国内的一流研究院比，亚洲研究院具有国际一流的理念和管理模式；和IBM 及Google 在中国的研究院比，亚洲研究院从事基础研究而不是产品开发。这样独树一帜的地位，天下无双。

其后果自然是人才的高度集中。其程度让我想起了中国科大和麻省理工学院(MIT)。三个地方的人都挺好，却不太一样。说起来上世纪80年代的科大最难进，因为她只看高考成绩，没什么别的好说的。这样的后果是人才比较同质化，大家的长处都差不多，学生都很像运动员，会比赛，但缺少解决实际问题的能力。MIT就好申请多了，允许书面申请，这样即使某一方面较弱也可以申诉，强调自己的强项。课外活动有超常的地方也可以加分不少。微软亚洲研究院就更好进了，不但有书面申请，还可以当面申诉（面试），有机会全面表现自己。当然，全面表现的后果也很严重，就是进去以后要全面兑现。研究能力，编程能力，写作能力，吹牛能力，缺一不可。

视觉计算组的同事就具有这样的特性，感觉和他们在一起，没有什么题目做不出来的。所以我又想起了铭铭，总感觉和铭铭在一起的时间太少，想把每一分钟都记录下来，结果照了大量照片。于是很自私地号召大家做照片管理方面的研究，就有了我们在SIGCHI注1上的第一篇长论文。接着为了更方便地把照片中的人像一次从多张照片中分割出来，又做了多图分割的题目。为了快速方便地查找图像，我们做了实时图像检索技术。为了找到更多有趣的应用，又用人脸检测和照片管理技术做了一个将真人头像植入卡通图片的技术，于是很容易的用铭铭的照片将“小兵张嘎”动画图片系列变成了“小兵汤嘎”。我在研究院和一些高校做报告时经常把我们的研究课题总结为“下一代”图象处理技术，因为我们的技术多是应用在我们“下一代”儿童的照片上。

铭铭的照片经常用在视觉计算组的各种实验数据里，成了组里最受欢迎的形象模特

我们做的一些好玩的技术已经开始影响微软的图像管理和搜索产品开发。在计算机研究领域有个矛盾，要想在实际产品中应用，一项技术必需简单实用，要想发表文章，这项技术又必需显得复杂深奥。要想既像Google那样做出实用产品，又像MIT那样在顶级会议发表文章，就要付出更多辛苦。作为一个做基础研究的地方，我们对在顶级会议发表文章的重视程度和MIT没有什么区别。在过去三年中，我们在一流的计算机视觉会议（ICCV注2, CVPR注3, ECCV注4）发表了60多篇论文。至少在数量上已差不多“天下第一铭”。我常讲做研究就像比武论剑一样,要论剑就要到华山论剑,如果你一定要去太行山论剑, 去挺进大别山，那别人只能当你是游击队, 永远也别想成正规军。在计算机视觉领域，农村是永远也包围不了城市的。华山以外，很难论出好剑。

发这些论文的另外一个好处是吸引了很多好学生，这些年我见过很多非常优秀的学生，有些已不能用优秀来形容，只能说是天才。晓刚注5是我见到的第一个天才学生，在硕士阶段就发表了五篇CVPR/ICCV。他的才华和人品如此出众，以至于我毫不犹豫地将妹妹嫁给了他。后来我的另一个天才级学生达华注6发表了更多的文章，可是我已经没有妹妹可以再嫁了。好在最近的一个天才级学生靖宇注7，来的时候就有女朋友了。靖宇编程打字的速度是如此之快，以至于我看不清他在键盘上快速移动的手。这三个学生共同特点是都收到MIT 和斯坦福的全额奖学金。晓刚和达华去了MIT, 靖宇选择了斯坦福。我有种感觉，将来他们都会非常成功，成为各自领域的“天下第一铭”。我有种感觉，他们会越来越多。我更有种感觉，铭铭不属于他们。

铭铭让我自豪的地方也很多。比如铭铭长的很漂亮。这不是我一个人说了算，你可以去问晓晓，桃桃，月月，同同，扬扬，希希……我家院里每个四五岁大的小女孩儿都认为铭铭是她最好的朋友。铭铭四岁前所结交的女朋友（在幼儿园结识的不算）已超过他爸爸四十年艰苦努力的成果（在研究院结识的不算）。

可惜铭铭对学习的态度就像功夫熊猫阿波对面条的感觉，毫无兴趣。铭铭对面条的感觉倒像阿波对功夫的感觉，兴趣盎然。铭铭的人生理想和同龄孩子很不一样，不是做医生，警察，或宇航员，而是“吃饭，睡觉，做佳菲猫”。而且说到做到，铭铭唯一喜欢的课程是厨艺课。厨艺课老师Mariana也觉得铭铭是五岁孩子中厨艺最精湛的了。可惜和同龄孩子一起的时候，极少有比厨艺的时候，反倒是认字，背诗经常被拿出来做表演项目。为了培养铭铭对体育的兴趣，对艺术的热爱，及对中华民族的自豪感，秋梅和我一起带铭铭去看了奥运会开幕式。对于这场人类历史上最精彩最完美最盛大的演出，铭铭印象最深刻的是我在现场餐厅为他买的两根烤香肠。想起来那一定是这世界上代价最高的两根香肠了。

也许铭铭的血液里真的是流淌着面条汤？希望铭铭长大时，可以选择的已不只华山这一条路，总不能人人都上华山，太挤了，希望有更多的山可以上，有更多的路可以走。总得给铭铭这样不爱学习又厨艺精湛的孩子一条出路吧，但愿那条路不像面条一样弯延曲折。

秋梅近来常怪我乱讲天下第一铭，给讲坏了。我只好苦笑，怪自己当初求上帝的时候忘了说是正着数还是倒着数了。我就安慰秋梅说“在认字，背诗，音乐，数学，中文，英文，这几个小的方面，铭铭是比别人差一点，好吧，不只一点，差一节，一大节，我们可能也不用太担心，或许铭铭是想后发制人。”

秋梅温柔地看了我一眼，冷冷地说，“制谁呀！你看后面还有人么？”

作者介绍

汤晓鸥教授，是汤之铭的爸爸。1990年于中国科学技术大学获学士学位，1996年于麻省理工学院(MIT)获博士学位。现于香港中文大学信息工程系任终身教授。2005到2007年，于微软亚洲研究院担任视觉计算组主任。现任IEEE ICCV’09程序委员会主席 (Program Chair)及IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI)编委 (Associate Editor)。他的研究领域包括计算机视觉、模式识别、及视频处理。

晓鸥在亚洲研究院期间，被一致推选为研究院文工团团长，兼团委书记，连续三年出任研究院年度文艺晚会主持人，他的演艺生涯开始于研究院，也是在研究院达到顶峰，为此，他为自己起了个艺名叫“小o”。小o的名言是：“看事物要一分为二，任何事物都有两个方面，有可笑的一面，同时也有更可笑的一面”。他就是这样看着铭铭一天天长大。

注1，SIGCHI: Special Interest Group for Computer Human Interaction，是世界上人机交互领域最大的专业组织，这是一个多学科交叉的学术组织，包括计算机科学家、软件工程师、心理学家、交互设计人员、图形设计人员、社会学家和人类学家等等。大家共同理念是”设计有用且可用的技术是一个多学科交叉的过程，这一过程的恰当实施可以改变人们的生活”。
注2，ICCV: International Conference on Computer Vision，由IEEE主办的国际计算机视觉大会。作为世界顶级的学术会议，首届国际计算机视觉大会于1987年在伦敦揭幕，其后两年举办一届。2005年第10届ICCV在北京举行。
注3，CVPR: Computer Vision and Pattern Recognition, 由IEEE主办的国际计算机视觉与模式识别大会，它是计算机视觉领域最顶级的三大学术会议之一。
注4，ECCV: European Conference on Computer Vision，两年举办一次，是计算机视觉领域三大顶级学术会议之一。
注5，王晓刚：中国科大本科毕业，少年班第一名，郭沫若奖学金获得者，于香港中文大学取得硕士学位，现于麻省理工学院攻读博士学位。
注6，林达华：中国科大本科毕业，于香港中文大学取得硕士学位，获香港中文大学工程院优秀硕士论文奖（每年度全院只选一人），现于麻省理工学院攻读博士学位。
注7，崔靖宇：清华大学本科及硕士毕业，随汤晓鸥在研究院做了一年半的实习生，获微软学者奖学金，现于斯坦福大学攻读博士学位。

转载自：http://blog.sina.com.cn/s/blog_4caedc7a0100bgu9.html

lpsolve是sourceforge下的一个开源项目，它的介绍如下：

Mixed Integer Linear Programming (MILP) solver lp_solve solves pure linear, (mixed) integer/binary, semi-cont and special ordered sets (SOS) models.lp_solve is written in ANSI C and can be compiled on many different platforms like Linux and WINDOWS .

lpsolve是一个混合整数线性规划求解器，可以求解纯线性、（混合）整数/二值、半连续和特殊有序集模型。并且经过实际验证，有极高的求解效率。

sourceforge主页

1.在Windows x64和Matlab环境下使用lpsolve

需要在网址lpsolve_5.5.2.5 提供的文件列表中下载文件lp_solve_5.5.2.5_MATLAB_exe_win64.zip。或者下载文件lp_solve_5.5.2.5_source.tar.gz自行编译dll。

注：在Matlab下运行示例报错：

Error using mxlpsolve
Failed to initialise lpsolve library.

参考Using lpsolve from MATLAB: http://web.mit.edu/lpsolve/doc/MATLAB.htm给出的说明，需要将编译得到的mxlpsolve.dll拷贝到 WINDOWS\system32文件夹下。

2.在MacOS下使用lpsolve

参考Using lp_solve in Java with Mac OS X的配置说明，下载源文件lp_solve_5.5.2.5_source.tar.gz，然后跳转到lp_solve_5.5/lpsolve55文件夹内，并执行ccc.osx：

cd lp_solve_5.5/lpsolve55
sh ccc.osx

生成的文件所在的文件夹：lpsolve55/bin/osx64/，将此文件夹内生成的两个文件liblpsolve55.dylib，liblpsolve55.a拷贝到/usr/local/lib文件夹内即可：

sudo cp liblpsolve55.a liblpsolve55.dylib /usr/local/lib

测试demo：

cd lp_solve_5.5/demo
sh ccc
./demo

3.在MacOS的Matlab中需要文件mxlpsolve.mexmaci64

需要从lpsolve主页下载源文件lp_solve_5.5.2.5_MATLAB_source.tar.gz，解压缩后，在Matlab中执行文件Makefile.m，期间需要添加各种头文件：

lp_Hash.h
lp_lib.h
lp_matrix.h
lp_mipbb.h
lp_SOS.h
lp_types.h
lp_utils.h

可下载lp_solve_5.5.2.5_dev_ux64.tar.gz并从中获取即可。

4.举例

mxlpsove.m是建模的核心函数，一个线性规划模型的所有配置和求解都是通过这个函数完成的。lp_maker.m和lp_solve.m是对mxlpsolve.m的高层包装，简化了模型建立和求解的过程。例如用lpsolve求解数学规划问题：

$$ \max 4x_1+2x_2+x_3\\
s.t.~ 2x_1+x_2\le 1\\
x_1+2x_3\le 2\\
x_1+x_2+x_3=1\\
0\le x_1\le1\\
0\le x_2\le1\\
0\le x_3\le2$$

相应的Matlab语句为：

f = [4 2 1];
A = [2 1 0; 1 0 2; 1 1 1];
b = [1; 2; 1];
l = [ 0 0 0];
u = [ 1 1 2];
lp=mxlpsolve('make_lp', 1, 3);
mxlpsolve('set_verbose', lp, 3);
mxlpsolve('set_obj_fn', lp, f);
mxlpsolve('add_constraint', lp, A(1, :), 1, b(1)); 
mxlpsolve('add_constraint', lp, A(2, :), 1, b(2)); 
mxlpsolve('add_constraint', lp, A(3, :), 0, b(3); 
mxlpsolve('set_lowbo', lp, l); 
mxlpsolve('set_upbo', lp, u); 
mxlpsolve('write_lp', lp, 'a.lp'); 
mxlpsolve('get_mat', lp, 1, 2) 
mxlpsolve('solve', lp) 
mxlpsolve('get_objective', lp) 
mxlpsolve('get_variables', lp) 
mxlpsolve('get_constraints', lp) 
mxlpsolve('delete_lp', lp)

重要函数说明：

lp_solve

LP_SOLVE  Solves mixed integer linear programming problems.

SYNOPSIS: [obj,x,duals] = lp_solve(f,a,b,e,vlb,vub,xint,scalemode,keep)

  solves the MILP problem

          max v = f'*x
            a*x <> b
              vlb <= x <= vub
              x(int) are integer

ARGUMENTS: The first four arguments are required:

        f: n vector of coefficients for a linear objective function.
        a: m by n matrix representing linear constraints.
        b: m vector of right sides for the inequality constraints.
        e: m vector that determines the sense of the inequalities:
                  e(i) = -1  ==> Less Than
                  e(i) =  0  ==> Equals
                  e(i) =  1  ==> Greater Than
      vlb: n vector of lower bounds. If empty or omitted,
           then the lower bounds are set to zero.
      vub: n vector of upper bounds. May be omitted or empty.
     xint: vector of integer variables. May be omitted or empty.
scalemode: scale flag. Off when 0 or omitted.
     keep: Flag for keeping the lp problem after it's been solved.
           If omitted, the lp will be deleted when solved.

   OUTPUT: A nonempty output is returned if a solution is found:

      obj: Optimal value of the objective function.
        x: Optimal value of the decision variables.
    duals: solution of the dual problem.

    Example of usage. To create and solve following lp-model:

max: -x1 + 2 x2;
C1: 2x1 + x2 < 5;
-4 x1 + 4 x2 <5;

int x2,x1;
The following command can be used:

>> [obj, x]=lp_solve([-1, 2], [2, 1; -4, 4], [5, 5], [-1, -1], [], [], [1, 2])

obj =

         3

x =

        1
         2

lp_maker　　 　　

LP_MAKER  Makes mixed integer linear programming problems.
SYNOPSIS: lp_handle = lp_maker(f,a,b,e,vlb,vub,xint,scalemode,setminim)
      make the MILP problem
        max v = f'*x
          a*x <> b
            vlb <= x <= vub
            x(int) are integer

   ARGUMENTS: The first four arguments are required:
            f: n vector of coefficients for a linear objective function.
            a: m by n matrix representing linear constraints.
            b: m vector of right sides for the inequality constraints.
            e: m vector that determines the sense of the inequalities:
                      e(i) < 0  ==> Less Than
                      e(i) = 0  ==> Equals
                      e(i) > 0  ==> Greater Than
          vlb: n vector of non-negative lower bounds. If empty or omitted,
               then the lower bounds are set to zero.
          vub: n vector of upper bounds. May be omitted or empty.
         xint: vector of integer variables. May be omitted or empty.
    scalemode: Autoscale flag. Off when 0 or omitted.
     setminim: Set maximum lp when this flag equals 0 or omitted.

   OUTPUT: lp_handle is an integer handle to the lp created.
Example of usage. To create following lp-model:

max: -x1 + 2 x2;
C1: 2x1 + x2 < 5;
-4 x1 + 4 x2 <5;

int x2,x1;
The following command can be used:

>> lp=lp_maker([-1, 2], [2, 1; -4, 4], [5, 5], [-1, -1], [], [], [1, 2])

lp =

     0
To solve the model and get the solution:

>> mxlpsolve('solve', lp)

ans =

     0

>> mxlpsolve('get_objective', lp)

ans =

     3

>> mxlpsolve('get_variables', lp)

ans =

     1
     2

注意：Don’t forget to free the handle and its associated memory when you are done:

>> mxlpsolve('delete_lp', lp);

5.参考

https://diegoresearch.wordpress.com/2008/07/10/using-lp_solve-in-java-with-mac-os-x/

http://web.mit.edu/lpsolve/doc/MATLAB.htm

http://www.cnblogs.com/kane1990/p/3428129.html

参考官方给出的文档：https://developer.clarifai.com/guide/tag#guide-tag-responses，在本机进行简单的体验。

首先注册账户，然后创建Application，获取ID及Secret，并在Application页面下生成“Access Token”码：XXx2QXEzmXXfj1eXkXXXUFLYXXX7DX

〇、客户端API参考：https://github.com/Clarifai/clarifai-python

pip install clarifai==2.0.10
clarifai config
CLARIFAI_APP_ID:
CLARIFAI_APP_SECRET:

在python中实现测试：

from clarifai.rest import ClarifaiApp
app = ClarifaiApp()
model = app.models.get('general-v1.3')
print model.predict_by_url('https://samples.clarifai.com/metro-north.jpg')
# or local image
print model.predict_by_filename('/Users/USER/my_image.jpeg')

一、打开MAC终端，输入Request命令：

1. 测试在线图片

   curl "https://api.clarifai.com/v1/tag/" \
         -X POST --data-urlencode "url=https://samples.clarifai.com/metro-north.jpg" \
         -H "Authorization: Bearer XXx2QXEzmXXfj1eXkXXXUFLYXXX7DX"
   

2. 测试本地图片

   curl "https://api.clarifai.com/v1/tag/" \
         -X POST -F "encoded_data=@/Users/USER/my_image.jpeg" \
         -H "Authorization: Bearer XXx2QXEzmXXfj1eXkXXXUFLYXXX7DX"
   

3. 测试多幅图像

   curl "https://api.clarifai.com/v1/tag/" \
         -X POST -F "encoded_data=@/Users/USER/my_image1.jpeg" \
         -F "encoded_data=@/Users/USER/my_image2.jpeg" \
         -F "encoded_data=@/Users/USER/my_image3.jpeg" \
         -F "encoded_data=@/Users/USER/my_image4.jpeg" \
         -H "Authorization: Bearer XXx2QXEzmXXfj1eXkXXXUFLYXXX7DX"
   

二、读取Response结果

在python中使用json来解析文本结果：

# -*- coding: utf-8 -*-
import json
for line in open("response.txt"):
    print line
str=json.loads(line)
results=str['results']
strNum=len(str['results'])
for ind in range(0,strNum):
    print ind
    print results[ind]['result']['tag']['classes']

输出解析结果（图像的tag类别）：

0
[u'sketch', u'illustration', u'cute', u'man', u'no person', u'funny', u'fun', u'vector', u'character', u'graphic design', u'business', u'child', u'art', u'retro', u'love', u'moon', u'Halloween', u'graphic', u'design', u'isolated']
1
[u'illustration', u'vector', u'sketch', u'retro', u'design', u'sketch', u'business', u'symbol', u'man', u'family', u'no person', u'graphic', u'humor', u'people', u'outdoors', u'image', u'art', u'nature', u'house', u'animal']
2
[u'vector', u'vector', u'illustration', u'no person', u'internet', u'technology', u'design', u'symbol', u'graphic design', u'data', u'flat', u'data', u'business', u'stripe', u'set', u'design', u'square', u'science', u'education', u'creativity']
3
[u'sleeve', u'illustration', u'isolated', u'polo', u'shirt', u'vector', u'design', u'image', u'wear', u'garment', u'sale', u'man', u'fashion', u'shopping', u'casual', u'front', u'shop', u'apparel', u'graphic', u'flat']
4
[u'illustration', u'vector', u'sketch', u'Halloween', u'cute', u'animal', u'skittish', u'funny', u'design', u'art', u'graphic', u'fun', u'ghost', u'scary', u'no person', u'vicious', u'desktop', u'retro', u'image', u'business']

（一）DeepLearning (DL)概述

1. 什么是DL？

机器学习ML的框架：

(1)数据：\({(x_i,y_i)}, 1\le i \le m\)

(2)模型：\(\mathcal{F}={f(x;\theta)}, \theta\in\Theta\)

i. 线性： \(y=f(x)=w^Tx+b\) 【x——>y】

ii. 广义线性：\(y=f(x)=w^T\phi(x)+b\) 【x——>[\(\bar{x}=\phi(x)\)]——>y，其中的\(\phi\)为模式识别中的特征Feature，这一步也称为特征学习。】

iii. 非线性：人工神经网络（ANN）

(3)准则：损失函数\(L(y,f(x))\)

经验风险：\(R(\theta)=\frac{1}{m}\sum_{i=1}^m{L(y,f(x_i,\theta))}\)

正则化项：\(|w|_2^2\)

Minimizing： \(R(\theta)+\lambda|w|_2^2\)，或稀疏正则项L1.

因此转化为一个最优化问题。

神经网络ANN中 \(y=\sigma(\sum_i{w_i x_i+b})\) 相当于从P维到Q维的一个映射函数。则DL就是解决这个深度前馈神经网络的算法。

2. 存在的困难及挑战

可训练的参数太多；【参数过多带来的问题具体包括：计算资源要大，数据要多(否则出现过拟合)，算法效率要高】

多层网络以后的优化问题变为非凸优化问题；

梯度弥散问题，即从网络层由上往下的参数调节变得非常困难；

解释困难(可通过一些可视化的方法一定程度上来进行解释)；

3.算法历史

1958年，感知机Perception：一个神经细胞的处理能力较差，与或运算无法实现。

1986年，神经网络的概念出现：BP算法，对浅层网络做了很多的工作。一方面受限于当时的硬件和软件问题。

1998年，CNN卷积神经网络，在手写体识别中取得了成功。—LeCun

2006年，DBN深度置信网络，—Hinton

4.为什么学习DL

有效！【语音识别，目标识别，NLP，CV….】

5.领域概述

学术机构：

TorontoU，Hinton，1975年EdinburghU’s PHD;
NewYorkU，LeCun，1987年PHD;
MentrealU，Bengio，1991年McGillU’s PHD;
StanfordU, Ng，2003年UCBerkeley’s PHD;

学术会议：
NIPS，ICML，ICRL，…

参考: 深度学习课程-概述

（二）FNN & BP

一.前馈神经网络FNN

1.神经元、神经层、神经网

神经元
x_1 -w_1-\
..  -w_i--〇z--->a
x_p -w_p-/

一个神经元的输出是一个线性函数与一个非线性函数的复合：\([z=\sum w_ix_i+b,~a=f(z)]=>a=f(\sum w_ix_i+b)\).

其中激活函数包括：sigmod: \(\sigma(x)=\frac{1}{1+e^x};~\tan(x)=\frac{e^x-e^{-x}}{e^x+e^{-x}};~|x|;~\)等

神经层
x_1 -w_1--〇--\-〇-->a_1 
              X
..  -w_i--〇--X-〇-->...
              X
x_p -w_p--〇--/-〇-->a_p

神经层上的每个神经元的输入时相同的，但权值是不同的。我们用 \( a^{(l)}_i \)表示第 \( l \)层第 \( i \)单元的激活值（输出值）。

神经网
-〇-\    -〇-\
-〇--〇-/-〇--〇-...
-〇--〇-\-〇--〇-...
-〇-/    -〇-/
n_1  n_2  n_3   ...   n_L

2.记号

超参数(并不是学习出来的，而是认为根据需要设定的参数，也称元参数)：层数L，第l层的神经元个数\(n^{(l)}\)，神经元非线性函数\(f_l()\).

要学习的参数：连接权weight参数\(w_i^{(1)},w_i^{(2)},..w_i^{(L)}\)，两层之间的连接权。 偏bias参数\(b^{(1)},b^{(2)},..b^{(L)}\).

第l层神经元的状态\(z^{(l)},1\le l\le L\)；第l层神经元的激活activation：\(a^{(l)}\)

3.前馈计算

(1)基本公式

\(z^{(l+1)}=w^l a^l+b^l \)

\(a^l=f_l(z^l) \)

\(h_{w,b}(x)=a^{(l+1)}=f(z^{(l+1)})\)

(2)前馈计算(\(W=(w^1,…,w^l),b=(b^1,..,b^l)\))

\(l=1, a^l=x\)

计算步骤：\(a^1->z^2->a^2->…->z^L->a^L\)

“目前为止，我们讨论了一种神经网络，我们也可以构建另一种结构的神经网络（这里结构指的是神经元之间的联接模式），也就是包含多个隐藏层的神经网络。最常见的一个例子是\(nl\)层的神经网络，第1层是输入层，第 \(n_l\)层是输出层，中间的每个层 \(l\)与层 \(l+1\)紧密相联。这种模式下，要计算神经网络的输出结果，我们可以按照之前描述的等式，按部就班，进行前向传播，逐一计算第 \(L_2\)层的所有激活值，然后是第 \(L_3\)层的激活值，以此类推，直到第 \(L{n_l}\)层。这是一个前馈神经网络的例子，因为这种联接图没有闭环或回路。”——UFLDL

4.应用于ML

数据D：\((x_i,y_i),1\le i\le N\)

模型M：\(y=h(x|w,b)\)

准则C: \(\sum_i|y_i-a^l(x|w,b)|^2+\lambda|w|_F^2) \)=min

其中，第二项是一个规则化项（也叫权重衰减项），其目的是减小权重的幅度，防止过度拟合: \(||w||F^2=\sum_i\sum_jw{ij}^2\)

权重衰减参数 \( \lambda \)用于控制公式中两项的相对重要性。

使用梯度下降法进行求解这个优化问题。

将上式写为：\(\sum_i J(x_i,y_i;w,b)+\lambda|w|_F^2\)=min

目标函数关于待求参数的导数：

其中：$$\frac{\partial|w|_F^2}{\partial w}=2w$$

然后重点求:$$\frac{\partial \sum J(.)}{\partial w};~~\frac{\partial \sum J(.)}{\partial b}$$

迭代公式：
$$w^{t+1}=w^t-\alpha \frac{\partial \sum J(.)}{\partial w}$$
$$b^{t+1}=b^t-\alpha \frac{\partial \sum J(.)}{\partial b}$$
其中\(\alpha\)是学习速率。

二.BP算法

“我们的目标是针对参数 \( W \)和 \( b \)来求其函数 \( J(W,b) \)的最小值。为了求解神经网络，我们需要将每一个参数 \( W^{(l)}{ij} \)和 \( b^{(l)}_i \)初始化为一个很小的、接近零的随机值（比如说，使用正态分布 \( {Normal}(0,\epsilon^2) \)生成的随机值，其中 \( \epsilon \)设置为 \( 0.01 \) ），之后对目标函数使用诸如批量梯度下降法的最优化算法。因为 \( J(W, b) \)是一个非凸函数，梯度下降法很可能会收敛到局部最优解；但是在实际应用中，梯度下降法通常能得到令人满意的结果。最后，需要再次强调的是，要将参数进行随机初始化，而不是全部置为 0。如果所有参数都用相同的值作为初始值，那么所有隐藏层单元最终会得到与输入值有关的、相同的函数（也就是说，对于所有 \( i\)，\( W^{(1)}{ij}\)都会取相同的值，那么对于任何输入 \( x \)都会有：\( a^{(2)}_1 = a^{(2)}_2 = a^{(2)}_3 = \ldots \)）。随机初始化的目的是使对称失效。”——UFLDL

1.多元函数的偏导数

(1)
$$X=[x_1,…,x_p]^T\in R^p,~ y=f(X)=f(x_1,…,x_p)$$
$$\nabla_x f(x)=\nabla_x y=\frac{\partial y}{\partial x}=[\frac{\partial f(x_1)}{\partial x},…,\frac{\partial f(x_p)}{\partial x}]^T\in R^p$$
(2)
$$x\in R^p, y=[..]^T\in R^q$$
$$y=[f_1(x),..,f_q(x)]^T$$
$$\nabla_xy=\nabla_x f(x)=\frac{\partial y}{\partial x}=[\frac{\partial f(x)}{\partial x_i}]^T\in R^{p\times q}$$
(3) 导数法则：链式法则

2.BP算法

BP思路：给定一个样例 \( (x,y)\)，我们首先进行“前向传导”运算，计算出网络中所有的激活值，包括 \( h_{W,b}(x) \)的输出值。之后，针对第 \( l \)层的每一个节点 \( i\)，我们计算出其“残差” \( \delta^{(l)}_i\)，该残差表明了该节点对最终输出值的残差产生了多少影响。对于最终的输出节点，我们可以直接算出网络产生的激活值与实际值之间的差距，我们将这个差距定义为 \( \delta^{(n_l)}_i \)（第 \( n_l \)层表示输出层）。对于隐藏单元我们如何处理呢？我们将基于节点（第 \( l+1 \)层节点）残差的加权平均值计算 \( \delta^{(l)}_i\)，这些节点以 \( a^{(l)}_i \)作为输入。

BP算法步骤：

(i)进行前馈传导计算，利用前向传导公式，得到 \( L2, L_3, \ldots \) 直到输出层 \( L{n_l} \)的激活值。

(ii)对于第 \( n_l \)层（输出层）的每个输出单元 \( i\)，我们根据以下公式计算残差：

$$\delta_i^{(n_l)}= \frac{\partial J}{\partial z_i^{n_l}}=-(y_i-a_i^{(n_l)})\cdot f’(z_i^{(n_l)})$$

(iii)令\(\delta^l=\frac{\partial J}{\partial z^l}\)，则对 \( l = n_l-1, n_l-2, n_l-3, \ldots, 2 \)的各个层，第 \( l \)层的第 \( i \)个节点的残差计算方法如下：（矩阵向量形式）

$$\begin{equation}\begin{split}\delta^{l}&=\frac{\partial J}{\partial z^{l}}=\frac{\partial a^l}{\partial z^l}\frac{\partial z^{l+1}}{\partial a^l}\frac{\partial J}{\partial z^{l+1}}\\
&=diag(f’(z^l))\cdot((w^l)^T\cdot\delta^{l+1})\\
&=(f’_l(z^l))\odot((w^l)^T\cdot\delta^{l+1})\\
&=((w^l)^T\cdot\delta^{l+1})\odot(f’_l(z^l))
\end{split}\end{equation}$$
以上逐次从后向前求导的过程即为“反向传导（BP）”的本意所在.

(iv)计算所需的偏导数：
$$\frac{\partial J}{\partial w^l}=\delta^{l+1}\cdot(a^l)^T$$
$$\frac{\partial J}{\partial b^l}=\delta^{l+1}$$

其中，假设 \( f(z) \)是sigmoid函数，并且我们已经在前向传导运算中得到了 \( a^{(l)}_i\)。那么，使用我们早先推导出的 \( f’(z)\)表达式，就可以计算得到 \( f’(z^{(l)}_i) = a^{(l)}_i (1- a^{(l)}_i)\)。

3.梯度下降法求解过程

(1) 对所有 \( l\)，令 \( \Delta W^{(l)} := 0 \), \( \Delta b^{(l)} := 0 \)（设置为全零矩阵或全零向量）

(2) For \( i = 1 \) to \( m\)，使用反向传播算法计算:

\(\nabla_{W^{(l)}} J(W,b;x,y) \)

\( \nabla_{b^{(l)}} J(W,b;x,y) \)

\( \Delta W^{(l)} := \Delta W^{(l)} + \nabla_{W^{(l)}} J(W,b;x,y) \)

\( \Delta b^{(l)} := \Delta b^{(l)} + \nabla_{b^{(l)}} J(W,b;x,y) \)

(3) 更新参数：
$$ \begin{align}
W^{(l)} &= W^{(l)} - \alpha \left[ \left(\frac{1}{m} \Delta W^{(l)} \right) + \lambda W^{(l)}\right] \\
b^{(l)} &= b^{(l)} - \alpha \left[\frac{1}{m} \Delta b^{(l)}\right]
\end{align}$$

重复梯度下降法的迭代步骤来减小代价函数 \( J(W,b)\) ，以训练我们的神经网络。

Clarifai 公司：www.clarifai.com

Clarifai创始人Matt Zeiler是New York University (NYU) Rob Fergus教授门下的学生。从上个世纪开始，NYU就一直是neural computation的重镇。现在Deep net的前身ConvNet，就是出自 NYU 的 Yann LeCun教授组.

ImageNet Large Scale Visual Recognition Competition 2013 (ILSVRC2013)

其中Matt Zeiler (http://Clarifai.com) 的算法排名第一，在不用额外训练数据的情况下，跑到了error rate 0.1174这样的成绩。

这个成绩是这样解读的：任选一张图片，扔给算法，算法返回5个结果。如果5个结果中，有一个猜对了物体类别，就算正确。换言之，如果允许猜5次，Clarifai已经有接近90%的准确率了。这里的物体类别包括了英语中两万多个名词，几乎涵盖了各大类别。

Clarifai API

参考

https://zhuanlan.zhihu.com/p/19821292

1.收到NVIDIA资助的显卡GeForce Titan X (12GB)

2.其他硬件设备：

CPU： Intel i7-6700
主板：华硕B150M-PLUS (LGA1151)
内存：4GB x 2
硬盘：希捷1TB
电源：鑫谷Segotep GP700G（金牌认证、宽幅） 额定600W 
机箱：Tt小板机箱
显卡接口转换器：DVI->VGI

3.备注

深度学习对CPU的要求并不是特别高，根据实际情况选择。
主板建议还是选择一个好的品牌，预算充足，可以考虑X99平台。
显卡GTX1080比老Titan X的性价比要高。
内存建议32G(16x2)，近期内存价格暴涨。
硬盘，最好配SSD，用来存放软件和数据集，提升IO效率。
电源根据显卡和整机功率需求选择(TitanX+CPU等差不多350W)。
机箱可扩展，散热好即可。

4.组装
主板安装CPU及散热器，将主板安装到机箱内(面板接口要仔细)，然后按照电源、硬盘，最后将电源线依次插入相应供电接口位置。

5.参考

个人深度学习环境搭建：主机配置与组装

手动安装：

$ # in a terminal, run the commands
$ git clone https://github.com/torch/distro.git ~/torch --recursive
$ cd ~/torch; bash install-deps;
$ ./install.sh

－－－－－－－－－－－－－－－－－－－－－－－－－

$ source ~/torch/install/bin/torch-activate

－－－－－－－－－－－－－－－－－－－－－－－－－
$ th

   ______             __   |  Torch7                                         
 /_  __/__  ________/ /   |  Scientific computing for Lua. 
   / / / _ \/ __/ __/ _ \  |  Type ? for help                                
 /_/  \___/_/  \__/_//_/  |  https://github.com/torch         
                         |  http://torch.ch                  

th> torch.Tensor{5,6,7}
 5
6
 7
[torch.DoubleTensor of size 3]

退出 th>

os.exit()

1.需要安装CUDA，不管有没有N卡
2.安装OpenBLAS，并在caffe设置文件中设置为：

# BLAS choice:
# atlas for ATLAS (default)
# mkl for MKL
# open for OpenBlas
BLAS := open
# Custom (MKL/ATLAS/OpenBLAS) include and lib directories.
# Leave commented to accept the defaults for your choice of BLAS
# (which should work)!
BLAS_INCLUDE := /opt/OpenBLAS/include
BLAS_LIB := /opt/OpenBLAS/lib

3.安装依赖库，可用brew list检查安装是否完全
4.添加路径：

export DYLD_FALLBACK_LIBRARY_PATH=/usr/local/cuda/lib:/usr/local/lib  

export DYLD_FALLBACK_LIBRARY_PATH=/usr/local/cuda/lib:$HOME/anaconda/lib:/usr/local/lib:/usr/lib:/opt/OpenBLAS/lib:/opt/OpenBLAS

5.下载caffe源文件，编译：make all时报错：

    PROTOC src/caffe/proto/caffe.proto  
    make: protoc: No such file or directory 

解决： 

    sudo chown yourname /usr/local  

    brew link yourlibpackage

6.Build: 继续编译：make test， make runtest

添加路径：

    export DYLD_LIBRARY_PATH=/usr/local/cuda/lib

    #python
    for req in $(cat python/requirements.txt); do pip install $req; done
    make pycaffe
    export PYTHONPATH=~/technologies/caffe/python/:$PYTHONPATH
    cd ..

make runtest的结果：

[----------] 10 tests from PowerLayerTest/0, where TypeParam = N5caffe9CPUDeviceIfEE
[ RUN      ] PowerLayerTest/0.TestPower
[       OK ] PowerLayerTest/0.TestPower (2 ms)
[ RUN      ] PowerLayerTest/0.TestPowerZeroGradient
[       OK ] PowerLayerTest/0.TestPowerZeroGradient (1 ms)
[ RUN      ] PowerLayerTest/0.TestPowerTwoGradient
...
[----------] 10 tests from PowerLayerTest/0 (16 ms total)

Bugs:

    library not found for -lboost_python

解决： 

    brew install boost-python

测试

MNIST

下载mnist数据，如下代码，报错，需安装brew install wget

./data/mnist/get_mnist.sh 

转数据：

./examples/mnist/create_mnist.sh
Creating lmdb...
Done.

./examples/mnist/train_lenet.sh

问题：

Cannot use GPU in CPU-only Caffe: check mode.

解决： 修改lenet_solver.prototxt 最后一行的GPU改为CPU，继续执行./examples/mnist/train_lenet.sh

I0407 00:51:59.023721 2035871744 caffe.cpp:178] Use CPU.
I0407 00:51:59.024705 2035871744 solver.cpp:48] Initializing solver from parameters: 
test_iter: 100
test_interval: 500
base_lr: 0.01
display: 100
max_iter: 10000
lr_policy: "inv"
gamma: 0.0001
power: 0.75
momentum: 0.9
weight_decay: 0.0005
snapshot: 5000
snapshot_prefix: "examples/mnist/lenet"
solver_mode: CPU
net: "examples/mnist/lenet_train_test.prototxt"
I0407 00:51:59.024927 2035871744 solver.cpp:91] Creating training net from net file: examples/mnist/lenet_train_test.prototxt
I0407 00:51:59.026877 2035871744 net.cpp:313] The NetState phase (0) differed from the phase (1) specified by a rule in layer mnist
I0407 00:51:59.026897 2035871744 net.cpp:313] The NetState phase (0) differed from the phase (1) specified by a rule in layer accuracy

...结果...

I0407 00:57:52.664399 2035871744 solver.cpp:317] Iteration 10000, loss = 0.0032766
I0407 00:57:52.664429 2035871744 solver.cpp:337] Iteration 10000, Testing net (#0)
I0407 00:57:54.761032 2035871744 solver.cpp:404]     Test net output #0: accuracy = 0.9901
I0407 00:57:54.761072 2035871744 solver.cpp:404]     Test net output #1: loss = 0.0290336 (* 1 = 0.0290336 loss)
I0407 00:57:54.761081 2035871744 solver.cpp:322] Optimization Done.
I0407 00:57:54.761087 2035871744 caffe.cpp:222] Optimization Done.

get youku videos using “flvcd.com”

借用flvcd.com实现对优酷视频的爬取。

参考：
www.flvcd.com

格式：

http://www.flvcd.com/parse.php?kw=...&format=...

format='normal'; 'high'; 'super'

# -*- coding:utf-8 -*-
from lxml import etree
import urllib2
import urllib
import os
import requests

def getHtml(url):
    html = requests.get(url).content
    selector = etree.HTML(html)
    return selector


def getContent(htm, xpathStr):
    selector = htm
    content = selector.xpath(xpathStr)
    return content

def getFlv(cons, title, folder):
    fn = '%s' % title
    pa = os.path.dirname(__file__) + '/' + 'youku/' +  folder
    # check and create folder
    if not os.path.exists(pa):
        os.mkdir(pa)
    fl = pa + '/%s.flv' % fn
    r = requests.get(cons)
    with open(fl, "wb") as code:
        code.write(r.content)

# = = = = = = #
videourl = 'http://v.youku.com/v_show/id_XMTUyMjE2MTcwOA==.html'
format = 'normal'  # 'high'  'normal'  'super'

url = 'http://www.flvcd.com/parse.php?kw=' + urllib.quote(videourl) + '&format=' + format
print url
req = urllib2.Request(url)
req.add_header('Referer', 'http://www.flvcd.com/')
req.add_header('User-Agent', 'Mozilla/5.0 (Windows NT 6.2; rv:16.0) Gecko/20100101 Firefox/16.0')
res = urllib2.urlopen(req)

html = res.read()
# print html
selector = etree.HTML(html)

# get flv title
xp_title='//*[@id="subtitle"]'
htm0=getHtml(videourl)
cons=getContent(htm0,xp_title)
title=cons[0].text
print title

# get flv href
xp = '//*[@class="mn STYLE4"]//@href'
content = selector.xpath(xp)
print '%s' % len(content)

x=0
for con in content:
    if 'http://k.youku.com' in con:
        print con
        getFlv(con,  '%s' % x, title)
        # urllib.urlretrieve(con, getPath('%s' % x, title))# , callbackfunc)
        x+=1

每天都要去arxiv上关注最新一天的论文（computer vision）更新，而且每次下载的论文的名称都是arxiv的代号，需要花时间去整理，于是用python写一个非常简单的爬虫，自己使用，足够节省时间了。

import requests
from lxml import etree
import os
import time
import re
from multiprocessing.dummy import Pool

def getHtml(url):
    html = requests.get(url).content
    selector = etree.HTML(html)
    return selector

def getContent(htm, xpathStr):
    selector = htm
    content = selector.xpath(xpathStr)  
    return content

def getDownPdf(cons, title, folder):
    fn = '%s' % title
    pa = os.path.dirname(__file__) + '/' + 'arxiv' + '/%s' % folder
    # check and create folder
    if not os.path.exists(pa):
        os.mkdir(pa)
    fl = pa + '/%s.pdf' % fn
    r = requests.get(cons)
    with open(fl, "wb") as code:
        code.write(r.content)

#### main ###
url0 = 'http://arxiv.org/list/cs.CV/recent'
print url0
# xpath of each page
xp1 = '//dl[1]//*[@class="list-identifier"]//a[2]//@href'  # pdf href list
xp2 = '//dl[1]//*[@class="list-title"]/text()'  # Title
xp_date = '//*[@id="dlpage"]/h3[1]/text()'  # date->folder

htm0 = getHtml(url0)
cons1 = getContent(htm0, xp1)  # get pdfs' href
cons2 = getContent(htm0, xp2)  # get papers' title
cons_date = getContent(htm0, xp_date) # get date

folder = cons_date[0].split(', ') # get date string

print folder[1] + ': having %s' % len(cons1) + '  files'
print 'pdfs are downloading...'

for indx in range(0, len(cons1)):
    href = 'http://arxiv.org' + cons1[indx]
    title = cons2[2 * indx + 1]
    print '%s.' % (1 + indx) + ' ' + href + ' ' + title
    getDownPdf(href, title, folder[1])

Python

1. Theano is a python library for defining and evaluating mathematical expressions with numerical arrays. It makes it easy to write deep learning algorithms in python. On the top of the Theano many more libraries are built.
   a. Keras is a minimalist, highly modular neural network library in the spirit of Torch, written in Python, that uses Theano under the hood for optimized tensor manipulation on GPU and CPU.
   b. Pylearn2 is a library that wraps a lot of models and training algorithms such as Stochastic Gradient Descent that are commonly used in Deep Learning. Its functional libraries are built on top of Theano.
   c. Lasagne is a lightweight library to build and train neural networks in Theano. It is governed by simplicity, transparency, modularity, pragmatism , focus and restraint principles.
   d. Blocks a framework that helps you build neural network models on top of Theano.

2. Caffe is a deep learning framework made with expression, speed, and modularity in mind. It is developed by the Berkeley Vision and Learning Center (BVLC) and by community contributors. Google’s DeepDream is based on Caffe Framework. This framework is a BSD-licensed C++ library with Python Interface.

3. nolearn contains a number of wrappers and abstractions around existing neural network libraries, most notably Lasagne, along with a few machine learning utility modules.

4. Gensim is deep learning toolkit implemented in python programming language intended for handling large text collections, using efficient algorithms.

5. Chainer bridge the gap between algorithms and implementations of deep learning. Its powerful, flexible and intuitive and is considered as the flexible framework for Deep Learning.

6. deepnet is a GPU-based python implementation of deep learning algorithms like Feed-forward Neural Nets, Restricted Boltzmann Machines, Deep Belief Nets, Autoencoders, Deep Boltzmann Machines and Convolutional Neural Nets.

7. Hebel is a library for deep learning with neural networks in Python using GPU acceleration with CUDA through PyCUDA. It implements the most important types of neural network models and offers a variety of different activation functions and training methods such as momentum, Nesterov momentum, dropout, and early stopping.

8. CXXNET is fast, concise, distributed deep learning framework based on MShadow. It is a lightweight and easy extensible C++/CUDA neural network toolkit with friendly Python/Matlab interface for training and prediction.

9. DeepPy is a Pythonic deep learning framework built on top of NumPy.

10. DeepLearning is deep learning library, developed with C++ and python.

11. Neon is Nervana’s Python based Deep Learning framework.

Matlab

1. ConvNet Convolutional neural net is a type of deep learning classification algorithms, that can learn useful features from raw data by themselves and is performed by tuning its weighs.

2. DeepLearnToolBox is a matlab/octave toolbox for deep learning and includes Deep Belief Nets, Stacked Autoencoders, convolutional neural nets.

3. cuda-convnet is a fast C++/CUDA implementation of convolutional (or more generally, feed-forward) neural networks. It can model arbitrary layer connectivity and network depth. Any directed acyclic graph of layers will do. Training is done using the backpropagation algorithm.

4. MatConvNet is a MATLAB toolbox implementing Convolutional Neural Networks (CNNs) for computer vision applications. It is simple, efficient, and can run and learn state-of-the-art CNNs

More… http://www.teglor.com/b/deep-learning-libraries-language-cm569/

Author: teglor

爬取指定用户的页面内容，并将图片下载保存到本地

import requests
import urllib2
from lxml import etree
import re
from multiprocessing.dummy import Pool
def tosave(texta):
    f = open('weibo.txt', 'a')    
    f.write(texta + '\n')    
    f.close()
cook = {"Cookie": "XXXXXX"}
url0 = 'http://weibo.cn/u/XXXXX'
def getContent(url, cook):
    html = requests.get(url, cookies=cook).content
    selector = etree.HTML(html)
    # read text from weibo
    content = selector.xpath('//span[@class="ctt"]')
    for each in content:
        text = each.xpath('string(.)')
        print text        
content = selector.xpath('//*[@class="ib"]/@src')  # copy from chrome # print content
return content

def getDownImg(cons, page):
    x = 0
    for each in cons:
       print each
       fn = '%s' % page + '%s' % x
       fl='%s.jpg' % fn
       url=each.replace('wap180','large')
       print url
       print fn
       r = requests.get(url)
       with open(fl, "wb") as code:
           code.write(r.content)
       x += 1

for page in range(1, 4):
   url = url0 + '?page=' + '%s' % page
   print url
   cons = getContent(url, cook)
   getDownImg(cons, page)

爬取微博（weibo.cn）指定用户的关注者，最多200条记录（20页，每页10条记录）。

# -*- coding: utf-8 -*-

import requests
import urllib2
from lxml import etree
import os
import time
import codecs
import re
from multiprocessing.dummy import  Pool
# import sys
# reload(sys)
# sys.setdefaultencoding('utf-8')

# write text to .txt
def tosave(texta):
    fn = 'following'
    pa = os.path.dirname(__file__) + '/' + username
    # check and create folder
    if not os.path.exists(pa):
        os.mkdir(pa)
    fl = pa + '/%s.txt' % fn
    f = codecs.open(fl, 'a', 'utf-8')
    f.write(texta + '\n')
    f.close()

def getHtml(url, cook):
    html = requests.get(url, cookies=cook).content
    selector = etree.HTML(html)
    return selector


def getContent(htm, xpathStr):
    selector = htm
    content = selector.xpath(xpathStr)  # copy from chrome # print content
    return content

def getPageNum(htm):
    xps='//*[@id="pagelist"]/form/div/input[1]//@value'
    pnum = getContent(htm, xps)
    print pnum[0]
    return int(pnum[0])

cook = {"Cookie": "XXXXXX"}
username = 'XXXXX' 
url0='http://weibo.cn/%s/follow' % username
print url0
htm = getHtml(url0, cook)
pagenum=getPageNum(htm)
for pn in range(1, pagenum):
    urls = url0 + '?page=%s' % pn
    print urls
    htms = getHtml(urls, cook)
    xptxt = '//td[2]//a[1]'  # homepage contains many tables
    xphref='//td[2]//a[1]//@href' # href
    consTxt = getContent(htms, xptxt)
    consHref=getContent(htms,xphref)
    for indx in range(1,len(consTxt)):
        followTxt=consTxt[indx].text + '     ' + consHref[indx]
        print followTxt
        tosave(followTxt)

在Markdown中插入数学公式可以采用如下几种方式：

解决方法1:
使用Google Chart的服务器

<img src="http://chart.googleapis.com/chart?cht=tx&chl= \frac{1}{\pi}=\frac{2\sqrt{2}}{9801}\sum_{k=0}^\infty\frac{(4k)!(1103+26390k)}{(k!)^4396^{4k}}" style="border:none;">

解决方法2:
使用CodeCogs网站的latex服务接口

<img src="http://latex.codecogs.com/svg.latex? \frac{1}{\pi}=\frac{2\sqrt{2}}{9801}\sum_{k=0}^\infty\frac{(4k)!(1103+26390k)}{(k!)^4396^{4k}}" style="border:none;">

解决方法3:
使用forkosh服务器

<img src="http://www.forkosh.com/mathtex.cgi? \frac{1}{\pi}=\frac{2\sqrt{2}}{9801}\sum_{k=0}^\infty\frac{(4k)!(1103+26390k)}{(k!)^4396^{4k}}">

解决方法4:
使用MathJax引擎

<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default"></script>

$$\frac{1}{\pi}=\frac{2\sqrt{2}}{9801}\sum_{k=0}^\infty\frac{(4k)!(1103+26390k)}{(k!)^4396^{4k}}$$ 行间

\\(\frac{1}{\pi}=\frac{2\sqrt{2}}{9801}\sum_{k=0}^\infty\frac{(4k)!(1103+26390k)}{(k!)^4396^{4k}}\\) 行内

$$\frac{1}{\pi}=\frac{2\sqrt{2}}{9801}\sum_{k=0}^\infty\frac{(4k)!(1103+26390k)}{(k!)^4396^{4k}}$$

\(\frac{1}{\pi}=\frac{2\sqrt{2}}{9801}\sum_{k=0}^\infty\frac{(4k)!(1103+26390k)}{(k!)^4396^{4k}}\)

UnicodeEncodeError: ‘ascii’ codec can’t encode

解决方案1：

import sys
reload(sys)
sys.setdefaultencoding('utf-8')

解决方案2:

不使用open打开文件，而使用codecs.open(), 在输出中文文本时，采用UTF-8编码：

f = codecs.open(‘XX.txt’, ‘a’, ‘utf-8’)
f.write(txts)
f.close()

Math for Machine Learning

author：Hal Daume III

The goal of this document is to provide a “refresher” on continuous mathematics for computer science students. It is by no means a rigorous course on these topics. The presentation, motivation, etc., are all from a machine learning perspective. The hope, however, is that it’s useful in other contexts. The two majortopics covered are linear algebra and calculus (probability is currently left off).

PDF

Homebrew安装时”-bash:brew:command not found”的问题

按照[Homebrew]官网上的安装教程安装，安装成功后，运行brew时，终端提示：

-bash:brew:command not found    

无法找到brew命令。

卸载Homebrew重装后，终端提示：

/usr/local/bin不在PATH中    

解决：

用vim打开，在profile文件最后添加如下语句：

PATH=“.;$PATH:/usr/local/bin”    

注意，若以前修改过该文件，或者PATH中已有多个路径，只需在后面添加即可，使用：隔开。

ImportError: Need nose

import numpy;numpy.test()

Running unit tests for numpy

Traceback (most recent call last):

File "", line 1, in 

File "/usr/lib/python2.7/site-packages/numpy/testing/nosetester.py", line 326, in test
self._show_system_info()

File "/usr/lib/python2.7/site-packages/numpy/testing/nosetester.py", line 187, in _show_system_info

nose = import_nose()

File "/usr/lib/python2.7/site-packages/numpy/testing/nosetester.py", line 69, in import_nose
raise ImportError(msg)

ImportError: Need nose >= 0.10.0 for tests - see http://somethingaboutorange.com/mrl/projects/nose

安装 pip

mac默认是不带pip的：

sudo easy_install pip    

安装nose

最好用easy_install：

sudo easy_install nose    

别用pip，我用pip装出各种问题

terminal退出phthon命令：

quit()    

or

Control + D    

安装matplotlib

sudo pip install matplotlib