逻辑回归:从入门到精通

本文由 天眼查创始人 柳超 原创首发于腾讯

导读

与算法、随机森林、支持向量积、神经网络、以及各种算法的花式排列组合相比,逻辑回归在多数人看来似乎是太过传统的统计方法。2014年底的我带着拯救世界的梦想投向硅谷怀抱的时候,也是这么认为的。

但是在工作的过程中我渐渐发现,不管听起来多fancy、多高大上的项目,硅谷的数据分析大佬们多数都会首选逻辑回归。而我之前自以为可以拯救世界的那些花式算法,其实都是逻辑回归的变换和推广,只是原理有轻微的不同。

后来做到了别的领域的项目,比如搜索,比如广告投放,也愈发认识到逻辑回归的重要性。因此,作为一名统计学出身的数据科学家,我极力向不喜欢看教科书的各位读者推荐以下这篇文章。我不知道怎么描述我第一次看到这篇文章的心情,就好比高考的时候突然有人给我了一份答案的感觉(虽然这个比喻不恰当但是真的是那种感觉,相信你们能感受到的)。

至于怎么能看透花式,洞悉一切,请看大神的文章吧!(By纪思亮)

◆ ◆ ◆

Abstract

逻辑回归(Logistic    Regression,简称LR)可以说是互联网领域应用最广的自动分类算法:从单机运行的垃圾邮件自动识别程序到需要成百上千台机器支撑的互联网广告投放系统,其算法主干都是LR。由于其普适性与重要性,大家在工作中都或多或少的谈论着LR,但是笔者发现很多同学对于LR的理解可以进一步提高与深化。所以,笔者准备了这样一个关于逻辑回归从入门到精通的文章和同学们一同探讨。本文的目标不像是基维百科那样泛泛而谈、面面俱到地介绍LR,相反而是更注重对LR的理解和其背后的优化算法的掌握,从而使大家更有信心的实现中需要的大规模LR模型,并根据实际问题持续地改进它。另外,由于求解LR是一个性质很好的优化问题。本文也借此机会比较系统的介绍了从最速梯度下降法,到牛顿方法,再到拟牛顿方法(包括DFP、BFGS、L-BFGS)这一系列数值优化算法的脉络,也算是对数值优化算法中文教程的一个补充吧。最后,请各位领导、大拿、和冲在一线的研究猿与攻城狮们不吝赐教、切磋琢磨、一同进步!

◆ ◆ ◆

    1、动机与目标读者

大家在平时的工作与学习当中经常会遇到各种决策问题:例如这封邮件是不是垃圾邮件,这个用户是不是对这个商品感兴趣,这个房子该不该买等等。熟悉或接触过机器学习(Machine    Learning,简称ML)的同学知道如果我们需要对这类问题进行决策的时候,最常用的方法是构建一个叫做分类器(Classifier)的程序。这种程序的输入待决策问题的一系列特征(feature),输出就是程序判定的结果。以垃圾邮件分类为例,每一封邮件就是一个待决策的问题,而通常使用的特征就是从这个邮件本身抽取一系列我们认为可能相关的信息,例如,发件人、邮件长度、时间、邮件中的关键词、标点符号、是否有多个收件人等等。给定了这些特征,我们的垃圾邮件分类器就可以判定出这封邮件是否是垃圾邮件。至于怎么得到这个垃圾邮件分类器程序,通常的做法是通过某些机器学习算法。之所以称其为”学习“ ,是因为这些算法通常需要一些已经标注好的样本(例如,100封邮件,每封信已经被明确标注为是否是垃圾邮件),然后这个算法就自动的产生一个关于这个问题的自动分类器程序。我们在这篇文章中将要讲得逻辑回归(Logistic    Regression,简称LR)就是最常用的一个机器学习分类算法。

很多同学可能知道机器学习中有几十种分类器,那么我们为什么偏偏挑LR来讲呢?原因有三:

  1. LR模型原理简单,并且有一个现成的叫LIBLINEAR 的工具库,易于上手,并且效果不错。
  2. LR可以说是互联网上最常用也是最有影响力的分类算法。LR几乎是所有广告系统中和推荐系统中点击率(Click    Through    Rate(CTR))预估模型的基本算法。
  3. LR同时也是现在炙手可热的“深度学习”(Deep    Lerning)的基本组成单元,扎实的掌握LR也将有助于你的学好深度学习。

但是文本并不是一篇关于LR的科普性文章,如果你想泛泛地了解LR,最好的办法是去维基百科或者找一本像样的机器学习教材翻一下。相反的,本文的目标是是你不仅仅“知其然”,并且更“知其所以然”,真正做到从入门到精通,从而更加有信心地解决LR实践中出现的新问题。我们可以粗略的把入门到精通分为三个层次。

  • 了解LR:了解LR模型、L1和L2规则化(Regularization)、为什么L1规则化更倾向于产生稀疏模型(Sparse    Model)、以及稀疏模型的优点。
  • 理解LR:理解LR模型的学习算法、能够独自推导基于L-BFGS的L1和L2规则化的LR算法,并将其在MPI平台上并行化实现。
  • 改进LR:能够在实际中自如应用LR,持续改进LR来解决实际中未曾遇见到的问题。例如,当数据中的正样本远远小于负样本的情况下(例如,广告点击率预告问题),该怎么调整LR?当数据中有相当部分缺失时该如何调整算法?

由于求解LR是一个性质很好的无约束优化问题,本文在介绍LR的同时,也相对系统的介绍了无约束优化问题中的几个常用的数值方法,包括最速梯度下降方法、牛顿方法、和拟牛顿方法的DFP、BFGS、与L-BFGS。期望同学们能在知道了解这些算法的同时真正明白其原理与应用场景,例如理解为什么L-BFGS中的二次循环方法(two    iteration    method )能够近似计算牛顿方向,并且可以轻松的并行化。这些算法是关于无约束问题的通过优化算法,应用场景非常广泛,但笔者并未发现关于他们比较系统化的、又同时比较容易理解中文教程,本文也算是填补这方面空白的一个尝试吧。所以,希望能在学习LR的同时将优化算法一并学了,相得益彰吧。

所以,本文预期的读者大概如下几类:

  1. 高阶机器学习人员:硕士毕业后5年及以上的机器学习经历,你就把这个当成一个关于LR和无约束优化算法的回顾材料好了,如有错误和不足请加以斧正。
  2. 中阶机器学习人员:硕士毕业后3~5年的机器学习经历,你可以把这个当做学习资料,把以前学过的东西串在一起,查漏补缺,做到真正懂得LR和相关优化的算法,从而能对工程实践做出正确的指导。
  3. 入门机器学习人员:硕士毕业后少于3年的机器学习经历,请你把纸和笔拿出来,把里面的公式一个个推导一遍,从而当你的leader告诉你某些事情的时候,你知道如何下手。
  4. 机器学习人员以外的高富帅和白富美们:你只需要知道LR是一个好用的自动分类算法,吩咐研究猿和攻城狮做就好了。另外,还可以用这篇文章嘲弄机器学习的屌丝们:累死累活,死那么多脑细胞,挣那两儿钱。

总而言之,不管你在机器学习上的造诣几何,希望这篇文章或多或少的都能给你带来点什么。笔者非常欢迎各方人士对本文以及任何与机器学习、数据挖掘相关问题的垂询、切磋、与探讨,好吧,闲话不多说,进入正题。

◆ ◆ ◆

正文概览

*鉴于文章的长度,这里只对文章内容做标题概览

2、初识逻辑回归

 3、L1    vs.    L2规则化

4、求解L2规则化的逻辑回归

5、OWL-QN:用L-BFGS求解L1规则化的逻辑回归

6、相关工作

7、前沿研究

◆ ◆ ◆

关于作者

柳超博士,天眼查创始人、董事长兼总经理,国家青年“千人计划”专家、北京市特聘专家、北京航空航天大学“大数据”特聘教授、中国大数据专家委员会委员、国家下一代互联网产业技术创新联盟专家。柳超博士创办天眼查之前,曾任搜狗科技首席科学家,美国微软研究院总部研究经理,美国国家自然科学基金数据挖掘方向的评审专家。

柳超于2007年在美国伊利诺伊大学获得计算机博士学位,并获得伊利诺伊大学杰出毕业论文奖,之后在数据挖掘、云计算、大数据分析、软件工程等方面取得了出色的研究成果。2008年至2012年,柳超博士任职于美国微软研究院,主管数据智能团队,期间在信息检索、数据挖掘和机器学习等诸多大数据相关领域作出了突出贡献,共计出版了 3 本英文专著、5篇国际期刊文章,以及30余篇国际一流学术会议文章,共计1300+次独立引用。

柳超博士在美期间曾担任美国国家自然科学基金数据挖掘方向的评审专家,多次应邀赴国际知名会议做主题报告。其工作成果在国际上备受关注,曾被国际电子电气工程师协会的IEEE Computer专业杂志以特邀封面文章的形式进行报道。

2012年,柳超博士回国加入腾讯科技(北京)有限公司,领导“腾讯搜索”的相关数据挖掘与机器学习业务。2014年,在腾讯与搜狗的战略合并之际加入搜狗科技,出任首席科学家,从零组建了搜狗数据科学研究院,全面负责搜狗互联网业务的数据挖掘与机器学习的前沿研究。
柳超博士创办的天眼查公司是中国首款关系发现平台,秉持“让每个人公平地看清这个世界”的使命,天眼查系列产品不仅可以可视化呈现复杂的商业关系,还可以深度挖掘和分析相关数据,预警风险等。目前,天眼查已经形成了针对媒体、金融、政府、法律等众多领域的大数据解决方案。更多精彩,请访问:www.tianyancha.com。

原文下载: LR_intro

算法与算法工程师,技术与技术人员

作者:伯乐在线 – 水石头stone

网址:http://blog.jobbole.com/89500/

点击“阅读原文”,加入伯乐在线专栏作者

在和刘同学长谈之后,我再次对前一段时间的想法进行了反思,结合聊天中的新感受,整理在这里。

(注:标题里的算法,指机器学习算法,或者说“算法工程师”这个职位名称里的“算法”,不是“算法与数据结构”里的那个算法。谁能告诉我有没有什么更好的名字来区别这它们,或许是“机器学习算法”与“传统算法”?)

算法与算法工程师

先来一段我在知乎里回答“做算法工程师是一种怎样的体验?”的答案(其中的思想并非原创,而是山寨自新加坡某大学一门Quantitative Investment课程的ppt)

理想中的算法工程师:提出假设->收集数据->训练模型->解释结果。

实际中的算法工程师:提出假设->收集数据->预处理->预处理->训练模型->调试->调试->重新收集数据->预处理->收集更多数据->调试->调试->调试->…->放弃。

这个答案被点了几十个 zan,在24个答案中排在第二位,说明具有一定的普遍性。排名第一的有 100+ 顶,而他的观点是:每天最重要的就是跑数据!

这不是段子,而是事实。为什么“高大上”的算法工程师实际上是个数据民工,要寻找这种理想与现实的差距的原因,首先要理解一个事实:只有人能够理解数据,机器不能。

不管我们用什么机器学习算法——无论是LR,SVM,k-means,EM——对于它们来说,输入数据都是一堆浮点数组成的矩阵而以(如果说的更本质一点,只是一堆01序列)。如果有一个特征是“小时”,而它出现了25,任何一个智商正常的人类都能明白,这是一个错误,然后在数据清洗的时候把这样的数据排除。但是机器就无法理解这一点。要具备小时的概念,又要理解什么是时间,一天有多少个小时…机器怎么能自动化完成这样的数据清洗工作?更进一步,如果人发现“小时”这个特征中大部分数据是0到12,而混入少量13(但13的数量又不是太少以至不能被当成离群点排除),人就会怀疑,是不是使用了12小时制而13是一个错误。机器目前是无法做到这一点的。

再说人肉特征。一个是特征变换,比如需要一个特征是某两列数据的比率,这种除法是线性模型不能涵盖的。当然可以增大模型的假设空间,但是太小涵盖不了需要的变换,太大又容易过拟合。另一个是加特征,比如我认为点击率和屏幕分辨率有关系。于是我去找屏幕分辨率数据加入特征,如果没有还要想办法采集。这些机器都做不了。

但是,人一但把数据准备好,接下来就是机器学习算法发挥的时候了。但是,算法工程师的主要工作不在这里,这是因为软件有个特点,可以近乎无成本的复制。只要这个世界上有一个人实现了LR(知识产权的问题这里不考虑,更何况开源软件很多),其他需要用LR的人都可以拿过来用了。显然,这些算法工程师们也正是这么做的。

然而,等算法输出结果以后,又需要人的工作了——怎样用结果解释实际问题,应用到业务中去。显然这个过程和前面数据清洗、人肉特征的性质类似,都是只有人能完成,机器做不到的任务。

做过数学建模的同学对这个过程可能很熟悉——如何把一个问题描述成数学问题,再如何把结果应用到实际问题上。这有点类似于通信中的“最后一公里”问题,主干网的光纤建设的很强大,而最终用户的接入却成了一个麻烦事。对于机器学习的应用问题来说,算法和相应的软件包都是标准化、通用化的,像骨干网;而数据如何“接入”,则是只能由人完成。因为,只有人能够理解数据。

技术与技术人员

这个问题可以推广到整个计算机领域。把算法工程师代换成程序员,把机器学习算法代换成软件,这个观点就变成了:大部分程序员所解决的,是通用的计算机工具和具体的实际业务之间的“最后一公里”接入问题。

为什么这么说,我们先来看历史:计算机技术发展了几十年,程序员的入门门槛是逐步降低的。最初的程序,要在裸机上写汇编。后来有了unix,c语言,程序员至少不用亲自调度进程了。java出现之后,连内存都不用管了。而(世界上最伟大的)php出现之后,网络编程的门槛进一步降低,任何人都可以在短时间内搭建一个网站。

原来的那些问题去哪儿了呢?被少数造“”轮子的程序员们解决了——那些写操作系统、编译器、虚拟机、运行时环境、框架…等等的程序员们。这个趋势一直在持续——新兴的rust、golang等语言试图解决多核时代出现的并发问题,hadoop、spark、mesos试图屏蔽分布式系统底层的细节……可以预见,以后的并行编程和分布式编程门槛将会大大降低。这个过程是必然的,因为一项技术的发展,就是为了让更多的人能更方便的使用它。

而这些计算机工具不能直接应用于业务,因为计算机不能理解人类的语言,所以就有了大量的程度员存在,把人类的语言“翻译”成计算机语言。这些程序员是使用“轮子”的。当然这之间并不是非黑即白的,一个软件在多大程度上可以被称为轮子,取决于它的复用性。如果一段代码只能在一个地方使用,它显然不能称为轮子。而事实是,大部分为具体的业务逻辑所写的代码,复用程度很低。

对于把通用计算机工具应用到具体业务这个过程,中间到底有多少问题是技术性的?大部分技术困难被操作系统、编译器、虚拟机解决掉了,剩下的主要是大型软件(如果这是个大型软件)的复杂性控制——而这个问题又主要由少数高级别的架构师负责。对于写具体代码的程序员,剩下的技术性困难已经很少了。

举一个我供职过的公司,这是一家互联网公司,整个网站99%的代码是php,基本上没有java。没有专门的前端工程师,php、html和javascript代码混在一起。测试几乎等于没有,基本都是开发人员自测。上线流程只是个形式,质量控制部门唯二的作用就是向服务器上同步代码和出现事故之后给开发人员定责任。我曾经和另一个部门合作,他调用我提供的接口,而他在我的接口没上线的时候就上线了,导致一场事故。我本来是算法工程师,写php只是客串,而在这个过程中,没有任何上线依赖的控制,连提示也没有,甚至没有人对我进行上线流程的培训。然而,这是一家中等规模的互联网公司,己经发展了十来年,占据了所在细分市场领域的头号份额,并且己经上市。

我举这个例子并不是要黑它,而是想用事实支持上面的观点:大部分程序员,大部分所谓的“科技”公司,所面临的技术问题比想象的要少的多(这也许是那家公司没有CTO的原因)。

这不是个别情况,大多数公司都存在类似的问题——从技术角度看,它就是个渣,你会很奇怪它怎么还没死。然而事实是,它不但没死,反而活的生机勃勃,甚至上市了。公司的拥有者们早已实现了屌丝逆袭迎娶白富美的理想,而辱骂他们的程序员们还在苦苦的为房贷或者首付挣扎。这里面,有大量的非技术因素起着关键作用,尽管它们都自称科技公司。

越来越多的人意识到了技术的局限性。年初,一个同学找工作,他向来是个“纯技术流”的工程师,曾经写过很好的技术博客,甚至发起过开源项目。然而这次他说,“不想再做最底层的工程师了”,希望能做一些“高层的、能看到项目整体的”、以及“和人打交道,能够把自己的想法向外推动,并产生价值”的工作。于是,他去某公司负责带几个小弟去了。当我把这些转述给另一个同学的时候,他的反应是“我最近也有这样的想法”。还有个同学,说写了几年C++,技术上没学到多少,反而是接触的业务知识比较多。再比如我之前的leader,他是数学博士出身,曾经对算法有一种近乎天真的信仰;在我离职的时候,他已经完全转型为业务和产品导向了。而某个几年前就开始淡化技术,聚会时大讲“软实力”的同学,早已在BAT做了Team Leader,生活滋润,终日以跑步为乐。为何?其实原因很简单:公司里没有那么多技术问题需要解决。

《代码大全》里有个比喻,如果你的问题是给自己的爱犬造一个小窝,那么动手做就是了,如果出了什么错误,大不了重做一个,最多浪费一下午的时间。而造一个摩天大楼就不同了。所以,如果写一份“狗窝”级别的程序,算法、数据结构、设计模式这些又有多大意义呢?甚至违反了DRY原则也没关系,反正一段代码也拷贝不了几次,出了bug就改,大不了重写一次,最多浪费一下午。而且,说不定这个项目两周之后就被砍掉了。如果你做的是一份“造狗窝”的工作,就算你有造摩天大楼的技术,和屠龙之技又有什么分别呢?唯一的“好处”就是你会据此向老板提出更多的加薪要求,以至于老板对你“另眼相看”。

程序员应当破除对技术不切实际的幻想——这不是说技术不重要,而是说要实事求是的分清,哪些是造狗窝的工作,哪些是建普通楼房的工作,哪些是造摩天大楼的工作。

再谈算法

同理,算法工程师应当破除对算法不切实际的幻想,把注意力集中到数据的理解、清洗、预处理、人肉特征、业务应用(而这些往往和屌丝、苦逼等形容词联系在一起)上来。

未来,机器学习工具将更加标准化、平台化、通用化,并且进一步降低使用门槛。与算法本质无关的工程细节,比如数据存储方式、梯度下降过程、并行化、分布式计算等,将被制造“轮子”的程序员们屏蔽。算法工程师可能只需用类似Hive的方式,写几个类似SQL的语句就可以完成模型的训练、交叉验证、参数优化等工作。

而机器唯一不能替代的就是对数据的理解,这是算法工程师存在的价值。而数据是和业务强相关的,算法工程师将更加接近产品经理的角色,而不是程序员。深入理解数据、业务和产品,寻找模型和它们的结合点,将成为算法工程师的核心竞争力。

插一句,相对于本文的观点,Deep Learning在某种程度上是一种的例外。它试图解决特征工程的问题,也就是在某种程度上代替人提取特征。当然,它还比较初级,另外它最多只能解决特征变换问题,仍然处理不了数据清洗和预处理中需要用到领域知识的情况。

这里刘同学提出一个问题,那就是算法工程师对算法需要理解到何种程度?事实是,即使从算法的应用出发,工程师也需要掌握模型的优缺点、适用场景、模型选择、参数调优等技术。这是毫无疑问的,从这一点上说,算法工程师需要一定的技术能力,这点又和产品经理不同。

但是这就有另外一个问题:模型选择和参数调优技术,是否是通用的?还是和具体的数据高度相关的?比如,是否存在这样的现象,同样的调优技术,在(比如说)电商数据上表现很好,到了社交数据上就不行了?这个问题我暂时没有答案,如果谁知道,请告诉我。不过,一个现象是,目前做机器学习模型相关的项目,在改进的时候,基本上都采用试错的方式,就是先做出改动,然后上线观察效果;如果不好,就换种方法;如果效果有所改进,也往往没有人知道为什么。如果存在一种通用的判断模型优劣的技术,我们为什么还要采取这种近乎穷举的方式呢?

从“IT精英”到“IT民工”或者“码农”,这种称呼上的转变并非笑谈,而是真实的反应了计算机编程领域门槛逐步降低的过程。所以,我们应当给听上去高大上的“算法工程师”或者“数据科学家”起一个类似的外号,比如“数据民工”、“机农”或者“蒜农”之类,以免不明真相的孩子们被“高大上”的称号吸引而误入歧途。

其它

看的出我是一个比较纯粹的技术人员,因为对于非技术的东西,我了解不够,说不出那是什么,只能用“其它”一词概括。

这“其它”,基本上是“人”的问题——比如前面提到的“如何推动自己的想法”,“软实力”之类,大的包括机遇,小到“发邮件应该抄送给谁”这种细节。

当然,如果你是个对技术本身感兴趣的人,这些讨论不适用,因为对于这类人,技术本身就是目的,不是手段。这里的视角,仅仅是社会普遍意义上的职业发展角度。无论是想在公司内部获得升迁,还是通过跳槽而得到晋升,还是自行创业而实现人生目标,技术都只是你的一种技能。如果再想想大部分公司里提供的是一份“造狗窝”级别的职位,这种技能起的作用又有多大呢?

不过多说一句,要求程序员“对技术感兴趣”,甚至“在业余时间以写代码为消遣”,是一种相当荒谬的事情。试想,招聘销售人员的时候,从未有人要求求职者“对喝酒应酬感兴趣”;招聘财务人员的时候,也没有人要求“对加减数字感兴趣”;招聘外科医生的时候,也绝不会要求“平时以解剖人体为消遣”。为什么程序员这种职业就要搞特殊?

究其原因,大概是大家还沉浸在对技术的一种非理性崇拜之中(当然崇拜和亵渎往往并存)——“技术改变世界”这句话常常被提到。这句话没错,但是要搞清楚,“技术改变世界”不等于“每一项技术都能改变世界”,更不等于“每一个技术人员都能改变世界”。其实,程序员这一行和其它任何一个需要专业技能的行业没什么区别,只是一种谋生的手段而已。

大部分所谓的“科技公司”也并不是真正的科技公司,最多是“使用科技的公司”。其实,在金融领域,对IT的要求要高多了,各大银行也有自己的软件开发部门,但是没人把它们归到IT行业,而是属于金融行业。然而,那些开商店的,开饭店的,卖房子的,给人说媒的,集资的,他们似乎只要做个网站,就成了“科技公司”了,这难道不是很荒谬吗?(当然,像亚马逊这种从一个卖书的起家,居然后来搞起了云计算、推荐系统、无人飞行器等技术创新的,不在此列。)在这些公司当中,技术到底起多大作用呢?

也许相当一部分程序员们会自以为技术很重要,他们沉浸在对技术的憧憬和信仰中,内心深处坚定的相信自己可以通过技术能力的提升,来谋取更高的职位,走向人生巅峰。然而,大多数时候这只是一种自欺欺人的幻想罢了。天朝的程序员们有一种矛盾心态,一方面自称“民工”,认为编程是一种只适合30岁之前的年轻人从事的体力劳动,而另一方面却又把技术看的非常重要,甚至在业余时间也喜欢大谈技术,或者以攻击其他程序员使用的技术为乐。如此抱着技术不放,并不是因为多么热爱技术,而是因为他们只会技术。没有人愿意在别人面前展示自己的劣势。把技术的地位抬的越高,仿佛自己就显得越重要,而那些在需要人际交往、推动自己的想法、和产品经理讨论需求的时候所表现出的能力低下,似乎就不重要了。

这是人性的弱点——对自己某种能力盲目而过分的自信,甚至把它作为自己的精神支柱。也许他在这个方面的确很擅长,但是自我评估却比实际更高。诚然,自信是必要的,也是人生存和立足的精神基础之一。然而自信是把双刃剑——不切实际的自信(也许应该叫自大了),会蒙蔽人的双眼,扭曲事实。

那么我们应该怎么做呢?首先比较悲观的一点是,如果你从事着一份技术上处于“造狗窝”级别的工作,那么很遗憾,提高自己的技术水平恐怕对于在公司内部的职业发展没什么帮助。

如果你是一个真正对技术有兴趣的人,可以考虑一下《黑客与画家》里提到的一类“真正的程序员”的工作方式:他们求的一份“白天的工作”,这份工作仅仅用来生存,而在业余时间写一些“真正有价值”的代码。

恐怕大部分程序员都不是对技术有兴趣的吧?如果你的目标是事业上的发展,无非是跟人混和创业两种方式。跟人混,要么内部晋升,要么通过跳槽。前者需要老板认为你牛逼;后者需要别的公司的老板认为你牛逼。注意,这里有个关键词“认为”,因为人的主观印象和客观事实之间总是有差距的,而且这个差距往往超乎人的想象。所以重点是制造一种“牛逼”的印象,而实际上牛不牛逼并不重要,牛逼更好,不牛逼也可。

如果你想走技术路线,可以考虑去找一份“建造大楼”级别的工作,在那里,技术成为决定产品成败的主要因素。这种级别的项目,一般只有大公司做的起。老板对于员工技术能力的评估,还是比较容易做到客观的,因为代码在那里,牛不牛逼,一运行便知。但是对于所谓“软实力”,往往就不好评判了,主观性很大。

也正因如此,往往有很多人觉得自己很牛逼,而老板不这么认为(错的不一定是老板,也可能是这个人自大),所以一怒之下走上创业的道路。自己给自己当老板,终于不用在意老板的印象和事实之间的差距。然而这条路往往更为艰难,它对人的综合素质要求比较高。如果一个程序员在工作中不能和同事顺利的合作,那很难想象他能够满足创业者所需要的各种素质。所以,要走这条路,得有心理准备。

总结

技术是为人服务的,IT业的发展过程,是在逐步降低计算机的使用门槛,使得越来越多的人能够使用这种工具。这是好的,但它同时也降低了程序员这种职业的技术含量。如果真的想做技术,那么去做一些真正的技术。否则,就需要多多关注技术以外的东西,单纯寄希望于技术,只能用来安慰自己,而不能获得真正的职业发展。

既懂数学又会编程,全方位解读如何成为一名投行Quant工

2016-04-12 UniCareer

Quant是做什么的?

Quant的工作就是设计并实现金融的数学模型(主要采用计算机编程),包括衍生物定价,风险估价或预测市场行为等。所以Quant更多可看为工程师,按中国的习惯性分类方法就是理工类人才,而不是文科人才,这个和金融有一定的区别(当然金融也有很多理工的内容)。

有哪几种 Quant?

(1) Desk Quant

Desk Quant 开发直接被交易员使用的价格模型,优势是接近交易中所遇到的Money和机会,劣势是压力很大。

(2) Model Validating Quant

Model Validating Quant 独立开发价格模型,不过是为了确定Desk Quant开发的模型的正确性。优势是更轻松,压力比较小,劣势是这种小组会比较没有作为而且远离Money。

(3) Research Quant

Research Quant 尝试发明新的价格公式和模型,有时还会执行Blue-Sky Research(不太清楚是什么),优势是比较有趣(对喜欢这些人来说),而且你学到很多东西。劣势是有时会比较难证明有你这个人存在(跟科学家一样,没有什么大的成果就没人注意你)

(4) Quant Developer

其实就是名字被美化的程序员,但收入很不错而且很容易找到工作。这种工作变化很大,它可能是一直在写代码,或者调试其他人的大型系统。

(5) Statistical Arbitrage Quant

Statistical Arbitrage Quant 在数据中寻找自动交易系统的模式(就是套利系统),这种技术比起衍生物定价的技术有很大的不同,它主要用在对冲基金里,而且这种位置的回报是极不稳定的。

(6) Capital Quant

Capital Quant 建立银行的信用和资本模型,相比衍生物定价相关的工作,它没有那么吸引人,但是随着巴塞尔II银行协议的到来,它变的越来越重要,你会得到不错的收入(但不会很多),更少的压力和更少的工作时间。

人们投资金融行业就是为了赚钱,如果你想获得更多的收入,你就要更靠近那些钱的”生产”的地方,这会产生一种接近钱的看不起那些离得比较远的人的现象,作为一个基本原则,靠近钱比远离钱要来得容易。

Quant工作的领域?

(1) FX

FX就是外汇交易的简写。合同趋向于短期,大量的金额和简单的规定,所以重点在于很快速度的建立模型。

(2) Equities

Equities的意思是股票和指数的期权,技术偏向于偏微分方程(PDE)。它并不是一个特别大的市场。

(3) Fixed Income

Fixed Income的意思是基于利息的衍生物,这从市值上来说可能是最大的市场,他用到的数学会更加复杂因为从根本上来说他是多维的,技术上的技巧会用的很多,他的收入比较高。

(4) Credit Derivatives

Credit Derivatives是建立在那些公司债务还清上的衍生产品,他发展的非常快并有大量需求,所以也有很高的收入,尽管如此,他表明了一些当前经济的泡沫因素。

(5) Commodities

Commodities因为最近几年生活用品价格的普遍涨价,也成为一个发展迅速的领域。

(6) Hybrids

Hybrids是多于一个市场的衍生物市场,典型情况是利息率加上一些其它东西,它主要的优势在于可以学到多种领域的知识,这也是当前非常流行的领域。

Quant一般在哪些公司工作?

(1) 商业银行 (HSBC, RBS)

商业银行对你要求少,也给的少,工作会比较稳定。

(2) 投行 (高盛, Lehman Brothers)

投行需要大量的工作时间但工资很高,不是很稳定的工作,总的来说,美国的银行收入比欧洲银行高,但工作时间更长。

(3) 对冲基金 (Citadel Group)

对冲基金需要大量的工作时间和内容,他们也处在高速发展同时不稳定的情况中,你可能会得到大量的回报,也可能几个月后就被开除。

(4) 会计公司

大型会计公司会有自己的顾问quant团队,有些还会送他们的员工去Oxford读Master,主要的劣势在于你远离具体的行为和决策,而且厉害的人更愿意去银行,所以你比较难找到人请教。

(5) 软件公司

外包quant模型变得越来越流行,所以你去软件公司也是一个选择,劣势和会计公司比较类似。

成为一个Quant需要看哪些书?
UniCareer诚意推荐书单
 
《Options Future and Other Derivatives》
John C. Hull

不管是找工作还是senior quant都会用到。John Hull本人也是非常厉害的,各个方面都有开创性的成果。现在Toronto Uni,经典中的经典,涉猎还算广泛,不过不够数学—-人称华尔街的圣经,自然不算很难。

《Stochastic Calculus for Finance II》
Steven E. Shreve

Shreve的新书,非常elegant, 非常仔细,非常数学完备,适合数学背景, 但是比较厚,对于入门来说还是3好。作者现在CMU纽约。教授。顶尖人物。I是讲离散模型,II讲连续模型。

《Liar’s Poker》
Michael Lewis 

讲以前Solomon brothers的Arb team的,当时是世界最厉害的quant trader。这本书搞trading的人都会看。

《C++ Design Patterns and Derivatives Pricing》
Mark S. Joshi 

对于懂得C++基础的人来说很重要,更重要的是教你学会Monte Carlo。

《Modeling Derivatives in C++ (Wiley Finance)》
Justin London 
学习了一年的金工,其实就这本书最核心最实用,其他的理论书看看就好。很多理论书还有重复部分,注意区分。
《The Concepts and Practice of Mathematical Finance》
Mark S. Joshi 
这本书的目标在于覆盖一个优秀quant应该知道的知识领域,其中包括强列推荐你在应聘工作之前看的一些编程项目。
《Interest Rate Models – Theory and Practice》
Damiano Brigo / Fabio Mercurio 
评价超高的书。这本书最大的精华是关于Libor market model的论述。本书的特点是作者将所有细节和盘托出,包括大量的数值结果,这样可以方便读者自学和验证。
《Probability with Martingales》
David Williams
主要是围绕martingale展开的,前面一部份介绍必要的measure theory的部分,点到即止,都是后面基本的probability theory需要用到的。即使你之前不懂measure theory也能看懂。难怪是给undergraduate用的。Williams是这个方向上文笔最好的数学家了。
 
《Monte Carlo Methods in Financial Engineering》
Paul Glasserman
本书很实用,紧扣标题,就是围绕着金融工程中蒙特卡洛的应用展开,真正读过的人可能会有感受,此书不太适合作为first book来读,最好两方面都已经有所涉及,再来读收获更大也更舒服些。
《My Life as a Quant: Reflections on Physics and Finance》
Emanuel Derman
作者是第一代quant,以前是GS的quant 研究部门head,现在哥大。是stochastic vol领域顶尖人物,其实也是很多其他领域顶尖人物。
福利领取方式
1. 关注公众号:UniCareer2. 回复关键字:我爱读书

3. 按照提示完成操作

3个工作日内,Quant十本书福利就会送到你的邮箱啦~

成为一个Quant需要知道一些什么?

根据你想工作的地方不同,你需要学习的知识变化很大,在写着篇文章的时间(1996),我会建议将我的书全部学会就可以了。很多人错误的把学习这些知识看作仅仅看书而已,你要做的是真正的学习,就像你在准备参加一个基于这些书内容的考试,如果你对能在这个考试里拿A都没有信心的话,就不要去面试任何的工作。

面试官更在乎你对基本知识的了解是否透彻,而不是你懂得多少东西,展示你对这个领域的兴趣也很重要,你需要经常阅读Economist, FT 和Wall Street Journal,面试会问到一些基本微积分或分析的问题,例如Logx的积分是什么。问到类似Black-Scholes公式怎么得出的问题也是很正常的,他们也会问到你的论文相关的问题。

面试同样也是让你选择公司的一个机会,他们喜欢什么样的人,他们关心的是什么之类的答案可以从他们的问题中得出,如果问了很多关于C++语法的问题,那么要小心选择除非那是你想做的工作。一般来说,一个PhD对得到Quant的Offer是必需的。

有一个金融数学的Master学位会让你在银行风险或交易支持方面却不是直接Quant方面的工作,银行业变得越来越需要数学知识,所以那些东西在银行的很多领域都有帮助。

在美国,读了一个PhD之后再读一个Master变得越来越普遍,在UK这依然比较少见。

一般哪些专业对口Quant?

据观察,Quant一般的专业会是数学,物理,金融工程(金融数学)。其实虽然不是特别多,但是还是有一些投行招手Master金工的Quant,一般几个好的FE专业都有去做Quant的硕士生。

编程      

所有类型的Quant都在编程方面花费大量时间(多于一半)。尽管如此,开发新的模型本身也是很有趣的一件事,标准的实现方法是用C++。一个想成为quant的人需要学习C++,有些其他地方使用Matlab所以也是一个很有用的技能,但没C++那么重要。VBA也用的很多,但你可以在工作中掌握它。

收入   

一个Quant能赚多少?一个没有经验的Quant每年大概会挣到税前60k-100k美元。奖金的话不会太高,但是如果行情好的话,也非常的客观,一般我听说的话,刚入职第一年一般可以拿到一两万刀的奖金。如果你的工资超出这个范围,你要问自己Why?收入会迅速的增长,奖金也是总收入中一个很大的组成部分,不要太在乎开始的工资是多少,而是看重这个工作的发展机会和学习的机会。

工作时间 

一个Quant工作的时间变化很大。在RBS我们8:30上班,6pm下班。压力也是变化很大的, 一些美国银行希望你工作时间更长。 在伦敦有5-6个星期的假期,而在美国2-3个是正常的。

纯粹数学的雪崩效应:庞加莱猜想何以造福了精准医疗?

2016-04-12 顾险峰 赛先生


图1 庞加莱猜想电脑三维模型

顾险峰 (纽约州立大学石溪分校终身教授,清华大学丘成桐数学科学中心访问教授,计算共形几何创始人)

最近英国上议院议员马特瑞德利(Matt Ridley)在《华尔街日报》上撰文《基础科学的迷思》(The Myth of Basic Science)。他认为“科学驱动创新,创新驱动商业”这一说法基本上是错误的,反而是商业驱动了创新,创新驱动了科学,正如科学家被实际需求所驱动,而不是科学家驱动实际需求一样。总之,他认为“科学突破是技术进步的结果,而不是原因”。

瑞德利先生的言论反映了许多人对基础科学的严重误解,会给年轻学子们带来思想混乱和价值观念上的困扰,有必要加以澄清。诚然,商业需求和工程实践会为基础科学提供研究的素材,比如历史上最优传输理论(OptimalMass Transportation Theory)和蒙日-安培方程(Monge-Ampere)起源于土石方的运输,最后猜想被康塔洛维奇解决,康塔洛维奇为此获得了诺贝尔经济学奖。数年前,为了解决医学图像的压缩问题,陶哲轩提出了压缩感知(Compressive Sensing)理论。但是,从根本上而言,基础科学的源动力来自于科学家对于自然真理的好奇和对美学价值的追求。基础科学上的突破,因为揭示了自然界的客观真理,往往会引发应用科学的革命。纯粹数学的研究因为其晦涩抽象,实用价值并不明显直观,普罗大众一直倾向于认为其“无用”。但实际上,纯粹数学对应用科学的指导作用是无可替代的。

计算机科学和技术发展的一个侧面就在于将人类数千年积累的知识转换成算法,使得没有经历过职业训练的人也可以直接使用最为艰深的数学理论。在拓扑和几何领域,往往很多具有数百年历史的定理仅仅在最近才被转换成算法。但是,依随计算机技术的迅猛发展,从定理到算法的过程日益加速。很多新近发展的数学理论被迅速转换成强有力的算法,并在工程和医疗领域被广泛应用。

历史一再表明,以满足人类好奇心为出发点的基础理论研究,其本质突破往往不能引起当时人类社会的重视,宛若冰川旷谷中一声微弱的呐喊,转瞬间随风消逝,但是这一声往往会引发令天空变色,大地颤抖的雪崩。庞加莱猜想的证明就是一个鲜明的实例,虽然雪崩效应还没有被大众所察觉,但是雪崩已经不可逆转地开始了!

1  庞加莱猜想

法国数学家庞加莱(Jules Henri Poincaré)是现代拓扑学的奠基人。拓扑学研究几何体,例如流形,在连续形变下的不变性质。我们可以想象曲面由橡皮膜制成,我们对橡皮膜拉伸压缩,扭转蜷曲,但是不会撕破或粘联,那么这些形变都是连续形变,或被称之为拓扑形变,在这些形变下保持不变的量就是拓扑不变量。如果一张橡皮膜曲面经由拓扑形变得到另外一张橡皮膜曲面,则这两张曲面具有相同的拓扑不变量,它们彼此拓扑等价。如图2 所示,假设兔子曲面由橡皮膜做成,我们象吹气球一样将其膨胀成标准单位球面,因此兔子曲面和单位球面拓扑等价。

图2. 兔子曲面可以连续形变成单位球面,因此兔子曲面和球面拓扑等价。

兔子曲面无法连续形变成轮胎的形状,或者图3中的任何曲面。直观上,图5中小猫曲面有一个“洞”,或称“环柄”;图3中的曲面则有两个环柄。拓扑上,环柄被称为亏格。亏格是最为重要的拓扑不变量。所有可定向封闭曲面依照亏格被完全分类。


图3. 亏格为2的封闭曲面。亏格是曲面最重要的拓扑不变量。

庞加莱思考了如下深刻的问题:封闭曲面上的“洞”是曲面自身的内蕴性质,还是曲面及其嵌入的背景空间之间的相对关系?这个问题本身就是费解深奥的,我们力图给出直观浅近的解释。我们人类能够看到环柄形成的“洞”,是因为曲面是嵌入在三维欧式空间中的,因此这些“洞”反应了曲面在背景空间的嵌入方式,我们有理由猜测亏格反映了曲面和背景空间之间的关系。

图4. 曲面上生活的蚂蚁如何检测曲面的拓扑?

但是另一方面,假设有一只蚂蚁自幼生活在一张曲面上,从未跳离过曲面,因此从未看到过曲面的整体情形。蚂蚁只有二维概念,没有三维概念。假设这只蚂蚁具有高度发达的智力,那么这只蚂蚁能否判断它所生活的曲面是个亏格为0的拓扑球面,还是高亏格曲面?

图5. 亏格为1的曲面上,无法缩成点的闭圈。

庞加莱最终悟到一个简单而又深刻的方法来判断曲面是否是亏格为0的拓扑球面:如果曲面上所有的封闭曲线都能在曲面上逐渐缩成一个点,那么曲面必为拓扑球面。比如,我们考虑图5中小猫的曲面,围绕脖子的一条封闭曲线,在曲面上无论怎样变形,都无法缩成一个点。换言之,只要曲面亏格非零,就存在不可收缩成点的闭圈。如果流形内所有的封闭圈都能缩成点,则流形被称为是单连通的。庞加莱将这一结果向高维推广,提出了著名的庞加莱猜想:假设M是一个封闭的单连通三维流形,则M和三维球面拓扑等价。

图6. 带边界的三流形,用三角剖分表示。

在现实世界中,无法看到封闭的三维流形:正如二维封闭曲面无法在二维平面上实现,三维封闭流形无法在三维欧式空间中实现。图6显示了带有边界的三维流形,例如实心的兔子和实心的球体拓扑等价。这些三维流形用三角剖分来表示,就是用许多四面体粘合而成。如图所示,体的三角剖分诱导了其二维边界曲面的三角剖分。实心球实际上是三维拓扑圆盘,我们可以将两个三维拓扑圆盘沿着边界粘合,就得到三维球面,恰如我们可以将两个二维拓扑圆盘沿着边界粘合而得到二维球面一样。当然,这已经超出人们的日常生活经验。

2  曲面单值化定理

近百年来,庞加莱猜想一直是拓扑学最为基本的问题,无数拓扑学家和几何学家为证明庞加莱猜想而鞠躬尽瘁死而后已。相比那些最后成功的幸运儿,众多默默无闻,潦倒终生的失败者更加令人肃然起敬。老顾曾经访问过吉林大学数学学院,听闻了有关何伯和教授的生平事迹。何教授终生痴迷于庞加莱猜想的证明,苦心孤诣,废寝忘食,愈挫愈奋,九死不悔,直至生命终结,对于庞加莱猜想依然念念不忘。何教授绝对不是为了任何实用价值或者商业利益而奋斗终生的,而是为了对于自然界奥秘的好奇,对于美学价值的热切追求,这种纯粹和崇高,是人类进步的真正动力!


图7. 人脸曲面上连接两点的测地线。

作为拓扑学最为基本的问题,庞加莱猜想的本质突破却来自于几何。给定一个拓扑流形,如给定图6中四面体网格的组合结构,我们可以为每条边指定一个长度,使得每个四面体都是一个欧式的四面体,这样我们就给出了一个黎曼度量。所谓黎曼度量,就是定义在流形上的一种数据结构,使得我们可以确定任意两点间的最短测地线。图7显示了人脸曲面上的两条测地线。黎曼度量自然诱导了流形的曲率。曲率是表征空间弯曲的一种精确描述。给定曲面上三个点,我们用测地线连接它们成一个测地三角形。如果曲面为欧几里德平面,那么测地三角形内角和为180度。球面测地三角形的内角和大于180度,马鞍面的测地三角形的内角和小于180度。测地三角形内角和与180度的差别就是三角形的总曲率。那么,给定一个拓扑流形,我们能否选择一个最为简单的黎曼度量,使得曲率为常数呢?

图8. 曲面单值化定理,所有封闭曲面都可以保角地形变成常曲率曲面。

这一问题的答案是肯定的,这就是曲面微分几何中最为根本的单值化定理。单值化定理是说大千世界,各种几何形状千变万化,但是无论它们如何变化,都是万变不离其宗:所有的曲面都可以共形地变换成三种标准曲面中的一种,单位球面,欧几里德平面和双曲平面。标准空间对应着常数值曲率,+1,0和-1,如图8所示。所谓共形变换,就是保持局部形状的变换,局部上看就是相似变换。相似变换保持角度不变,因此共形变换也被称为是保角变换。图9显示了从曲面到平面的一个共形变换。单值化定理断言了所有封闭曲面可以配有三种几何中的一种:球面几何,欧氏几何和双曲几何。曲面微分几何中几乎所有的重要定理都绕不过单值化定理。


图9. 共形变换保持局部形状。

3  瑟斯顿几何化猜想

为了证明庞加莱猜想,菲尔兹奖得主瑟斯顿推广了单值化定理到三维流形情形。任何三维流形,都可以经历一套标准手续分解成一系列的最为简单的三维流形,即所谓的素流形。素流形本身无法被进一步分解,同时这种分解本质上是唯一的。瑟斯顿提出了石破天惊的几何化猜想:所有的素三维流形可以配有标准黎曼度量,从而具有8种几何中的一种。特别地,单连通的三维流形可被配有正的常值曲率度量,配有正的常值曲率的3维流形必为3维球面。因此庞加莱猜想是瑟斯顿几何化猜想的一个特例。

图10. 瑟斯顿的苹果,几何化猜想。

图10显示了瑟斯顿几何化的一个实例。假设我们有一个苹果,三只蛀虫蛀蚀了三条管道,如左帧所示,这样我们得到了一个带边界的三维流形。根据几何化纲领,这个被蛀蚀的苹果内部容许一个双曲黎曼度量,使得其边界曲面的曲率处处为-1。我们将配有双曲度量的苹果周期性地嵌在三维双曲空间之中,得到右帧所示图形。

4  哈密尔顿的里奇曲率

本质的突破来自于哈密尔顿的里奇曲率流(Hamilton’s Ricci Flow)。哈密尔顿的想法来自经典的热力学扩散现象。假设我们有一只铁皮兔子,初始时刻兔子表面的温度分布并不均匀,依随时间流逝,温度渐趋一致,最后在热平衡状态,温度为常数。哈密尔顿设想:如果黎曼度量依随时间变化,度量的变化率和曲率成正比,那么曲率就像温度一样扩散,逐渐变得均匀,直至变成常数。如图11所示,初始的哑铃曲面经由曲率流,曲率变得越来越均匀,最后变成常数,曲面变成了球面。

图11. 曲率流使得曲率越来越均匀,直至变成常数,曲面变成球面。

在二维曲面情形,哈密尔顿和Ben Chow证明了曲率流的确将任何一个黎曼度量形变成常值曲率度量,从而给出了曲面单值化定理的一个构造性证明。但是在三维流形情形,里奇曲率流遇到了巨大的挑战。在二维曲面情形,在曲率流过程中,在任意时刻,曲面上任意一点的曲率都是有限的;在三维流形情形,在有限时间内,流形的某一点处,曲率有可能趋向于无穷,这种情况被称为是曲率爆破(blowup),爆破点被称为是奇异点(singularity)。

如果发生曲率爆破,我们可以将流形沿着爆破点一切两半,然后将每一半接着实施曲率流。如果我们能够证明在曲率流的过程中,曲率爆破发生的次数有限,那么流形被分割成有限个子流形,每个子流形最终变成了三维球面。如果这样,原来流形由有限个球粘合而成,因而是三维球面,这样就证明了庞加莱猜想。由此可见,对于奇异点的精细分析成为问题的关键。哈密尔顿厘清了大多数种类奇异点的情况,佩雷尔曼解决了剩余的奇异点种类。同时,佩雷尔曼敏锐地洞察到哈密尔顿的里奇流是所谓熵能量的梯度流,从而将里奇流纳入了变分的框架。佩雷尔曼给出了证明的关键思想和主要梗概,证明的细节被众多数学家进一步补充完成。至此,瑟斯顿几何化猜想被完全证明,庞加莱猜想历经百年探索,终于被彻底解决。

5 庞加莱猜想带来的计算技术

庞加莱猜想本身异常抽象而枯燥:单连通的闭3-流形是三维球面,似乎没有任何实用价值。但是为了证明庞加莱猜想,人类发展了瑟斯顿几何化纲领,发明了哈密尔顿的里奇曲率流,深刻地理解了三维流形的拓扑和几何,将奇异点的形成过程纳入了数学的视野。这些基础数学上的进展,必将引起工程科学和实用技术领域的“雪崩”。比如,里奇曲率流技术实际上给出了一种强有力的方法,使得我们可以用曲率来构造黎曼度量

里奇曲率流属于非线性几何偏微分方程,里奇流的方法实际上是典型的几何分析方法,即用偏微分方程的技术来证明几何问题。几何分析由丘成桐先生创立,庞加莱猜想的证明是几何分析的又一巨大胜利。当年瑟斯顿提倡用相对传统的拓扑和几何方法,例如泰西米勒理论和双曲几何理论来证明,也有数学家主张用相对组合的方法来证明,最终还是几何分析的方法拔得头筹。

哈密尔顿的里奇流是定义在光滑流形上的,在计算机的表示中,所有的流形都被离散化。因此,我们需要建立一套离散里奇流理论来发展相应的计算方法。历经多年的努力,笔者和合作者们建立了离散曲面的里奇曲率流理论,证明了离散解的存在性和唯一性。因为几乎所有曲面微分几何的重要问题,都无法绕过单值化定理。我们相信离散曲率流的计算方法必将在工程实践中发挥越来越重要的作用 [1]


图12. 离散里奇流计算的带边曲面单值化。

图8和图12显示了离散里奇流算出的封闭曲面和带边界曲面的单值化。本质上,这两幅图统摄了现实生活中所有可能的曲面,它们都被共形地映到了三种标准曲面上,球面、欧氏平面和双曲平面。这意味着,如果我们发明了一种新的几何算法,适用于这三种标准曲面,那么这一算法也适用于所有曲面。因此,离散曲率流的技术极大地简化了几何算法设计。

6 精准医疗

庞加莱猜想所诱发的离散曲率流方法被广泛应用于精准医疗领域。人体的各种器官本质上都是二维曲面或三维流形,曲率流方法对于这些器官几何特征的分析和比较起到了不可替代的作用。


图13. 虚拟肠镜技术。

虚拟肠镜 

直肠癌是男子的第四号杀手,仅在心脑血管疾病之后。中年之后,每个人都会自然长出直肠息肉,息肉会逐年增长,如果息肉直径达到一定尺寸,由于摩擦息肉会发生溃疡,长期溃疡会导致癌变。但是直肠息肉的生长非常缓慢, 一般从息肉出现直到临界尺寸需要七八年,因此对息肉的监控对于预防直肠癌起着至关重要的作用。中年人应该每两年做一次肠镜检查。传统的肠镜检查方法需要对受检者全身麻醉,将光学内窥镜探入直肠。老年人肠壁比较薄弱,容易产生并发症。同时,肠壁上有很多皱褶,如果息肉隐藏在皱褶中,医生会无法看到而产生漏检。

近些年来,北美和日本采用了虚拟肠镜技术。受检者的直肠图像由断层扫描技术来获取,直肠曲面可以从图像重建出来,如图14所示。我们需要将直肠展开摊平,从而使所有皱褶暴露出来,以便于寻找息肉和测量它们的尺寸。同时,如图13所示,在检查中同一受检者的直肠被扫描两次,每次扫描都是采用不同的姿态。直肠曲面柔软而富有弹性,不同的扫描得到的曲面之间相差很大的弹性形变。我们需要在两张曲面间建立光滑双射。在两张三维曲面间建立映射相对困难,当我们将曲面摊开展平成平面长方形后,在平面区域间计算映射会简单很多。将直肠曲面摊开展平等价于为曲面赋上一个曲率处处为0的黎曼度量,我们可以直接应用里奇曲率流的算法加以实现,如图14所示。

图14. 用里奇曲率流将直肠曲面摊开展平。

目前,虚拟肠镜技术在北美和日本被广泛采用,(但在中国还没有普及),主要是因为这种方法可以提高安全性,降低漏检率,降低人力成本。虚拟肠镜技术的普及极大地提高了早期直肠癌的发现几率,降低了直肠癌的死亡率,为人类的健康事业做出了巨大贡献。


图15. 虚拟膀胱镜。

同样的方法可以用于膀胱等其他器官,如图15所示。膀胱癌的最主要特征是膀胱壁变厚,同时内壁不再光滑,出现菜花状的几何纹理。这些症状可以用虚拟膀胱镜的方法定量得到。传统膀胱镜的方法病人需要忍受很大的痛苦,虚拟膀胱镜的方法极大地减轻了病患的疼痛,因而具有很大的优势。


图16. 用里奇曲率流将大脑皮层曲面共形映到单位球面,以便于对照比较。

脑神经疾病的预防诊断

脑退化症(Alzheimer’s disease,俗称老年痴呆症),癫痫,儿童自闭症等脑神经疾病严重地威胁着人类的健康安全。对于这些疾病的预防和诊断具有重要的现实意义。通过核磁共振成像技术,我们能够获取人类的大脑皮层曲面,如图16所示。大脑皮层曲面的几何非常复杂,有大量的皱褶沟回结构,并且这些几何结构因人而异,依随年龄变化而变化。例如老年痴呆症往往伴随大脑皮层一部分区域的萎缩。为了监控病情的发展,我们需要每隔几个月就扫描一下病人的大脑,然后将不同时期得到的大脑皮层曲面进行精确地对比。在三维空间中直接对比难度很高,我们非常容易将不同的沟回错误地对齐,算法落入在局部最优陷阱中。如图16所示,我们将大脑皮层曲面共形地映到球面上,然后在球面之间建立光滑映射,这种方法更加简单而精确。将大脑皮层映到球面等价于为大脑皮层曲面赋以曲率为+1的黎曼度量,我们可以用里奇曲率流的方法得到。


图17. 大脑海马体的几何分析。

如果说大脑皮层是数据库,那么海马体就是数据库的索引,如图17所示。如果海马体发生病变,长期记忆就无法形成,同时大脑中的长期记忆也无法被取出。很多神经疾病都能够引起海马体的变形,例如癫痫、吸毒、脑退化症等等。对海马体的几何形状进行定量比较分类是非常重要的。一种精确的方法是将海马体共形映到单位球面上,则面积的变化率给出了初始黎曼度量的全部信息,再加上平均曲率,那么海马体的所有几何信息被完美保留。换言之,我们将海马体曲面转换为球面上的两个函数(面积变化率,平均曲率)。在球面上比较不同的海马体曲面,从而精确衡量曲面之间的相似程度,进行分类诊断。相比于传统方法,这种基于几何的诊断方法更加定量而精确。

图18. 人脸曲面的精确匹配。

美容技术

在美容手术领域中,术后效果评估是重要的一个环节,这需要将术前和术后的人脸曲面进行精确的匹配。如图18所示,我们扫描了同一个人的带有不同表情的两张人脸曲面,然后在人脸曲面之间建立了精确的双射。平静表情的人脸上每一个小圆映到微笑表情的人脸上对应的小椭圆,由此我们可以测量对应点的几何变化。因此,三维人脸曲面间精确映射是美容领域中至关重要的技术。


图19. 三维人脸曲面被共形地映到二维平面上,所用方法就是里奇曲率流。

如图19所示,我们用里奇曲率流方法,将人脸曲面的黎曼度量变成曲率为0的平直度量,将三维人脸曲面平铺到二维平面上面,然后在二维平面区域之间建立光滑双射,从而诱导三维人脸曲面间的双射。当然,这种方法也可以用于三维人脸识别,但是人脸识别对于映射的精确度要求没有如此之高。

在精准医疗的其他领域,例如牙齿整形、人造心脏瓣膜、人造骨骼、放射治疗实时监控、肝脏手术计划等等,都需要对各种人体器官进行影像获取、几何重建、特征分析等,里奇流方法都会起到重要的作用。

7 总结和展望

庞加莱猜想本身纯粹而抽象:单连通的闭三维流形是三维球面,这一猜想本身似乎并没有任何实用价值。其结论的简单直观,往往给非数学专业人员无病呻吟之感。但是纯粹数学所追求的严密性迫使无数拓扑和几何学家们前仆后继,奉献终身,终于在众多数学家的共同努力下完成了证明。二维曲面的几何化定理——单值化定理从理论证明到算法提出,历经了百年;三维流形的瑟斯顿几何化纲领从理论证明到算法提出,几乎是同时。三维流形的拓扑理论和计算理论一开始就深刻地纠缠在一起。这表明,在现代,依随计算机技术的发展,纯粹理论到应用算法的开发周期越来越短。

同时,我们看到,在证明庞加莱猜想的过程中,瑟斯顿的几何化纲领将三维流形的风景一览无遗,哈密尔顿的里奇流给出从曲率来构造黎曼度量的强有力的工具,哈密尔顿和佩雷尔曼的奇点演化理论使得原来理论的禁区被彻底打破。笔者和许多数学家发展了离散里奇流的理论和算法,并且系统性地将曲率流应用到许多工程和医疗领域。在实践中,我们深深体会到,在许多关键的应用中,曲率流的方法无法被其它任何方法所取代。目前在社会实践中,里奇流在二维曲面上的应用已经开始逐步展开。但是里奇流在三维流形上的应用更为深邃奥妙,强悍有力,目前还没有任何实际应用。一方面因为三维流形远远超越日常生活经验,另一方面也是因为和曲面微分几何相比,三维流形的拓扑和几何知识远未普及。但是作为自然真理的忠实刻画,迟早三维流形的拓扑和几何会在社会实践中大行其道。庞加莱猜想所引发的雪崩效应终究会改写历史进程。

当庞加莱提出他的拓扑猜想,瑟斯顿洞察三维流形的基本几何结构,哈密尔顿悟出里奇曲率流,佩雷尔曼看出哈密尔顿的曲率流本质上是所谓熵能量的梯度流,他们所追求的是体悟几何结构的壮美,和自然真理的深邃。他们绝不会将实用价值作为其终极目的。实用技术的积累往往只能带来进化(Evolutio),好奇心的满足却能真正带来革命(Revolution)。愿更多的年轻人在万丈红尘中,在浮躁喧嚣中,能够保持诚挚纯真,保持强烈好奇,保持对自然界美丽的敏感,保持对科学真理的激情!

(如果读者对于离散曲面里奇流的理论、算法和应用有兴趣,可以进一步查阅专著【1】)

参考文献

[1] W. Zeng and X. Gu, Ricci Flow for Shape Analysis and Surface Registration Theories, Algorithms and Applications, Springer 2013

延伸阅读

  如果没有基础科学,我们将会失去什么?②  视频 | 拓扑为何?

③  纯粹数学走出象牙塔:丘成桐和三维科技有何关系?

Essentials of Machine Learning Algorithms (with Python and R Codes)

Source: http://www.analyticsvidhya.com/blog/2015/08/common-machine-learning-algorithms/

Introduction

Google’s self-driving cars and robots get a lot of press, but the company’s real future is in machine learning, the technology that enables computers to get smarter and more personal.

– Eric Schmidt (Google Chairman)

We are probably living in the most defining period of human history. The period when computing moved from large mainframes to PCs to cloud. But what makes it defining is not what has happened, but what is coming our way in years to come.

What makes this period exciting for some one like me is the democratization of the tools and techniques, which followed the boost in computing. Today, as a data scientist, I can build data crunching machines with complex algorithms for a few dollors per hour. But, reaching here wasn’t easy! I had my dark days and nights.

 

Who can benefit the most from this guide?

What I am giving out today is probably the most valuable guide, I have ever created.

The idea behind creating this guide is to simplify the journey of aspiring data scientists and machine learning enthusiasts across the world. Through this guide, I will enable you to work on machine learning problems and gain from experience. I am providing a high level understanding about various machine learning algorithms along with R & Python codes to run them. These should be sufficient to get your hands dirty.

machine learning algorithms, supervised, unsupervised

I have deliberately skipped the statistics behind these techniques, as you don’t need to understand them at the start. So, if you are looking for statistical understanding of these algorithms, you should look elsewhere. But, if you are looking to equip yourself to start building machine learning project, you are in for a treat.

 

Broadly, there are 3 types of Machine Learning Algorithms..

1. Supervised Learning

How it works: This algorithm consist of a target / outcome variable (or dependent variable) which is to be predicted from a given set of predictors (independent variables). Using these set of variables, we generate a function that map inputs to desired outputs. The training process continues until the model achieves a desired level of accuracy on the training data. Examples of Supervised Learning: Regression, Decision Tree, Random Forest, KNN, Logistic Regression etc.

 

2. Unsupervised Learning

How it works: In this algorithm, we do not have any target or outcome variable to predict / estimate.  It is used for clustering population in different groups, which is widely used for segmenting customers in different groups for specific intervention. Examples of Unsupervised Learning: Apriori algorithm, K-means.

 

3. Reinforcement Learning:

How it works:  Using this algorithm, the machine is trained to make specific decisions. It works this way: the machine is exposed to an environment where it trains itself continually using trial and error. This machine learns from past experience and tries to capture the best possible knowledge to make accurate business decisions. Example of Reinforcement Learning: Markov Decision Process

List of Common Machine Learning Algorithms

Here is the list of commonly used machine learning algorithms. These algorithms can be applied to almost any data problem:

  1. Linear Regression
  2. Logistic Regression
  3. Decision Tree
  4. SVM
  5. Naive Bayes
  6. KNN
  7. K-Means
  8. Random Forest
  9. Dimensionality Reduction Algorithms
  10. Gradient Boost & Adaboost

1. Linear Regression

It is used to estimate real values (cost of houses, number of calls, total sales etc.) based on continuous variable(s). Here, we establish relationship between independent and dependent variables by fitting a best line. This best fit line is known as regression line and represented by a linear equation Y= a *X + b.

The best way to understand linear regression is to relive this experience of childhood. Let us say, you ask a child in fifth grade to arrange people in his class by increasing order of weight, without asking them their weights! What do you think the child will do? He / she would likely look (visually analyze) at the height and build of people and arrange them using a combination of these visible parameters. This is linear regression in real life! The child has actually figured out that height and build would be correlated to the weight by a relationship, which looks like the equation above.

In this equation:

  • Y – Dependent Variable
  • a – Slope
  • X – Independent variable
  • b – Intercept

These coefficients a and b are derived based on minimizing the sum of squared difference of distance between data points and regression line.

Look at the below example. Here we have identified the best fit line having linear equation y=0.2811x+13.9. Now using this equation, we can find the weight, knowing the height of a person.

Linear_Regression

Linear Regression is of mainly two types: Simple Linear Regression and Multiple Linear Regression. Simple Linear Regression is characterized by one independent variable. And, Multiple Linear Regression(as the name suggests) is characterized by multiple (more than 1) independent variables. While finding best fit line, you can fit a polynomial or curvilinear regression. And these are known as polynomial or curvilinear regression.

Python Code

#Import Library
#Import other necessary libraries like pandas, numpy...
from sklearn import linear_model
#Load Train and Test datasets
#Identify feature and response variable(s) and values must be numeric and numpy arrays
x_train=input_variables_values_training_datasets
y_train=target_variables_values_training_datasets
x_test=input_variables_values_test_datasets
# Create linear regression object
linear = linear_model.LinearRegression()
# Train the model using the training sets and check score
linear.fit(x_train, y_train)
linear.score(x_train, y_train)
#Equation coefficient and Intercept
print('Coefficient: \n', linear.coef_)
print('Intercept: \n', linear.intercept_)
#Predict Output
predicted= linear.predict(x_test)

R Code

#Load Train and Test datasets
#Identify feature and response variable(s) and values must be numeric and numpy arrays
x_train # Train the model using the training sets and check score
linear <- lm(y_train ~ ., data = x)
summary(linear)
#Predict Output
predicted= predict(linear,x_test) 

 

2. Logistic Regression

Don’t get confused by its name! It is a classification not a regression algorithm. It is used to estimate discrete values ( Binary values like 0/1, yes/no, true/false ) based on given set of independent variable(s). In simple words, it predicts the probability of occurrence of an event by fitting data to a logit function. Hence, it is also known as logit regression. Since, it predicts the probability, its output values lies between 0 and 1 (as expected).

Again, let us try and understand this through a simple example.

Let’s say your friend gives you a puzzle to solve. There are only 2 outcome scenarios – either you solve it or you don’t. Now imagine, that you are being given wide range of puzzles / quizzes in an attempt to understand which subjects you are good at. The outcome to this study would be something like this – if you are given a trignometry based tenth grade problem, you are 70% likely to solve it. On the other hand, if it is grade fifth history question, the probability of getting an answer is only 30%. This is what Logistic Regression provides you.

Coming to the math, the log odds of the outcome is modeled as a linear combination of the predictor variables.

odds= p/ (1-p) = probability of event occurrence / probability of not event occurrence
ln(odds) = ln(p/(1-p))
logit(p) = ln(p/(1-p)) = b0+b1X1+b2X2+b3X3....+bkXk

Above, p is the probability of presence of the characteristic of interest. It chooses parameters that maximize the likelihood of observing the sample values rather than that minimize the sum of squared errors (like in ordinary regression).

Now, you may ask, why take a log? For the sake of simplicity, let’s just say that this is one of the best mathematical way to replicate a step function. I can go in more details, but that will beat the purpose of this article.

Logistic_RegressionPython Code

#Import Library
from sklearn.linear_model import LogisticRegression
#Assumed you have, X (predictor) and Y (target) for training data set and x_test(predictor) of test_dataset
# Create logistic regression object
model = LogisticRegression()
# Train the model using the training sets and check score
model.fit(X, y)
model.score(X, y)
#Equation coefficient and Intercept
print('Coefficient: \n', model.coef_)
print('Intercept: \n', model.intercept_)
#Predict Output
predicted= model.predict(x_test)

R Code

x # Train the model using the training sets and check score
logistic <- glm(y_train ~ ., data = x,family='binomial')
summary(logistic)
#Predict Output
predicted= predict(logistic,x_test)

 

Furthermore..

There are many different steps that could be tried in order to improve the model:

 

3. Decision Tree

This is one of my favorite algorithm and I use it quite frequently. It is a type of supervised learning algorithm that is mostly used for classification problems. Surprisingly, it works for both categorical and continuous dependent variables. In this algorithm, we split the population into two or more homogeneous sets. This is done based on most significant attributes/ independent variables to make as distinct groups as possible. For more details, you can read: Decision Tree Simplified.

IkBzK

source: statsexchange

In the image above, you can see that population is classified into four different groups based on multiple attributes to identify ‘if they will play or not’. To split the population into different heterogeneous groups, it uses various techniques like Gini, Information Gain, Chi-square, entropy.

The best way to understand how decision tree works, is to play Jezzball – a classic game from Microsoft (image below). Essentially, you have a room with moving walls and you need to create walls such that maximum area gets cleared off with out the balls.

download

So, every time you split the room with a wall, you are trying to create 2 different populations with in the same room. Decision trees work in very similar fashion by dividing a population in as different groups as possible.

MoreSimplified Version of Decision Tree Algorithms

Python Code

#Import Library
#Import other necessary libraries like pandas, numpy...
from sklearn import tree
#Assumed you have, X (predictor) and Y (target) for training data set and x_test(predictor) of test_dataset
# Create tree object 
model = tree.DecisionTreeClassifier(criterion='gini') # for classification, here you can change the algorithm as gini or entropy (information gain) by default it is gini  
# model = tree.DecisionTreeRegressor() for regression
# Train the model using the training sets and check score
model.fit(X, y)
model.score(X, y)
#Predict Output
predicted= model.predict(x_test)

R Code

library(rpart)
x # grow tree 
fit y_train ~ ., data = x,method="class")
summary(fit)
#Predict Output 
predicted= predict(fit,x_test)

 

4. SVM (Support Vector Machine)

It is a classification method. In this algorithm, we plot each data item as a point in n-dimensional space (where n is number of features you have) with the value of each feature being the value of a particular coordinate.

For example, if we only had two features like Height and Hair length of an individual, we’d first plot these two variables in two dimensional space where each point has two co-ordinates (these co-ordinates are known as Support Vectors)

SVM1

Now, we will find some line that splits the data between the two differently classified groups of data. This will be the line such that the distances from the closest point in each of the two groups will be farthest away.

SVM2

In the example shown above, the line which splits the data into two differently classified groups is the black line, since the two closest points are the farthest apart from the line. This line is our classifier. Then, depending on where the testing data lands on either side of the line, that’s what class we can classify the new data as.

More: Simplified Version of Support Vector Machine

Think of this algorithm as playing JezzBall in n-dimensional space. The tweaks in the game are:

  • You can draw lines / planes at any angles (rather than just horizontal or vertical as in classic game)
  • The objective of the game is to segregate balls of different colors in different rooms.
  • And the balls are not moving.

 

Python Code

#Import Library
from sklearn import svm
#Assumed you have, X (predictor) and Y (target) for training data set and x_test(predictor) of test_dataset
# Create SVM classification object 
model = svm.svc() # there is various option associated with it, this is simple for classification. You can refer link, for mo# re detail.
# Train the model using the training sets and check score
model.fit(X, y)
model.score(X, y)
#Predict Output
predicted= model.predict(x_test)

R Code

library(e1071)
x # Fitting model
fit <-svm(y_train ~ ., data = x)
summary(fit)
#Predict Output 
predicted= predict(fit,x_test)

 

5. Naive Bayes

It is a classification technique based on Bayes’ theorem with an assumption of independence between predictors. In simple terms, a Naive Bayes classifier assumes that the presence of a particular feature in a class is unrelated to the presence of any other feature. For example, a fruit may be considered to be an apple if it is red, round, and about 3 inches in diameter. Even if these features depend on each other or upon the existence of the other features, a naive Bayes classifier would consider all of these properties to independently contribute to the probability that this fruit is an apple.

Naive Bayesian model is easy to build and particularly useful for very large data sets. Along with simplicity, Naive Bayes is known to outperform even highly sophisticated classification methods.

Bayes theorem provides a way of calculating posterior probability P(c|x) from P(c), P(x) and P(x|c). Look at the equation below:
Bayes_rule

Here,

  • P(c|x) is the posterior probability of class (target) given predictor (attribute).
  • P(c) is the prior probability of class.
  • P(x|c) is the likelihood which is the probability of predictor given class.
  • P(x) is the prior probability of predictor.

Example: Let’s understand it using an example. Below I have a training data set of weather and corresponding target variable ‘Play’. Now, we need to classify whether players will play or not based on weather condition. Let’s follow the below steps to perform it.

Step 1: Convert the data set to frequency table

Step 2: Create Likelihood table by finding the probabilities like Overcast probability = 0.29 and probability of playing is 0.64.

Bayes_4

Step 3: Now, use Naive Bayesian equation to calculate the posterior probability for each class. The class with the highest posterior probability is the outcome of prediction.

Problem: Players will pay if weather is sunny, is this statement is correct?

We can solve it using above discussed method, so P(Yes | Sunny) = P( Sunny | Yes) * P(Yes) / P (Sunny)

Here we have P (Sunny |Yes) = 3/9 = 0.33, P(Sunny) = 5/14 = 0.36, P( Yes)= 9/14 = 0.64

Now, P (Yes | Sunny) = 0.33 * 0.64 / 0.36 = 0.60, which has higher probability.

Naive Bayes uses a similar method to predict the probability of different class based on various attributes. This algorithm is mostly used in text classification and with problems having multiple classes.

Python Code

#Import Library
from sklearn.naive_bayes import GaussianNB
#Assumed you have, X (predictor) and Y (target) for training data set and x_test(predictor) of test_dataset
# Create SVM classification object model = GaussianNB() # there is other distribution for multinomial classes like Bernoulli Naive Bayes, Refer link
# Train the model using the training sets and check score
model.fit(X, y)
#Predict Output
predicted= model.predict(x_test)

R Code

library(e1071)
x # Fitting model
fit <-naiveBayes(y_train ~ ., data = x)
summary(fit)
#Predict Output 
predicted= predict(fit,x_test)

 

6. KNN (K- Nearest Neighbors)

It can be used for both classification and regression problems. However, it is more widely used in classification problems in the industry. K nearest neighbors is a simple algorithm that stores all available cases and classifies new cases by a majority vote of its k neighbors. The case being assigned to the class is most common amongst its K nearest neighbors measured by a distance function.

These distance functions can be Euclidean, Manhattan, Minkowski and Hamming distance. First three functions are used for continuous function and fourth one (Hamming) for categorical variables. If K = 1, then the case is simply assigned to the class of its nearest neighbor. At times, choosing K turns out to be a challenge while performing KNN modeling.

More: Introduction to k-nearest neighbors : Simplified.

KNN

KNN can easily be mapped to our real lives. If you want to learn about a person, of whom you have no information, you might like to find out about his close friends and the circles he moves in and gain access to his/her information!

Things to consider before selecting KNN:

  • KNN is computationally expensive
  • Variables should be normalized else higher range variables can bias it
  • Works on pre-processing stage more before going for KNN like outlier, noise removal

Python Code

#Import Library
from sklearn.neighbors import KNeighborsClassifier
#Assumed you have, X (predictor) and Y (target) for training data set and x_test(predictor) of test_dataset
# Create KNeighbors classifier object model 
KNeighborsClassifier(n_neighbors=6) # default value for n_neighbors is 5
# Train the model using the training sets and check score
model.fit(X, y)
#Predict Output
predicted= model.predict(x_test)

R Code

library(knn)
x # Fitting model
fit <-knn(y_train ~ ., data = x,k=5)
summary(fit)
#Predict Output 
predicted= predict(fit,x_test)

 

7. K-Means

It is a type of unsupervised algorithm which  solves the clustering problem. Its procedure follows a simple and easy  way to classify a given data set through a certain number of  clusters (assume k clusters). Data points inside a cluster are homogeneous and heterogeneous to peer groups.

Remember figuring out shapes from ink blots? k means is somewhat similar this activity. You look at the shape and spread to decipher how many different clusters / population are present!

splatter_ink_blot_texture_by_maki_tak-d5p6zph

How K-means forms cluster:

  1. K-means picks k number of points for each cluster known as centroids.
  2. Each data point forms a cluster with the closest centroids i.e. k clusters.
  3. Finds the centroid of each cluster based on existing cluster members. Here we have new centroids.
  4. As we have new centroids, repeat step 2 and 3. Find the closest distance for each data point from new centroids and get associated with new k-clusters. Repeat this process until convergence occurs i.e. centroids does not change.

How to determine value of K:

In K-means, we have clusters and each cluster has its own centroid. Sum of square of difference between centroid and the data points within a cluster constitutes within sum of square value for that cluster. Also, when the sum of square values for all the clusters are added, it becomes total within sum of square value for the cluster solution.

We know that as the number of cluster increases, this value keeps on decreasing but if you plot the result you may see that the sum of squared distance decreases sharply up to some value of k, and then much more slowly after that. Here, we can find the optimum number of cluster.

Kmenas

Python Code

#Import Library
from sklearn.cluster import KMeans
#Assumed you have, X (attributes) for training data set and x_test(attributes) of test_dataset
# Create KNeighbors classifier object model 
k_means = KMeans(n_clusters=3, random_state=0)
# Train the model using the training sets and check score
model.fit(X)
#Predict Output
predicted= model.predict(x_test)

R Code

library(cluster)
fit

 

8. Random Forest

Random Forest is a trademark term for an ensemble of decision trees. In Random Forest, we’ve collection of decision trees (so known as “Forest”). To classify a new object based on attributes, each tree gives a classification and we say the tree “votes” for that class. The forest chooses the classification having the most votes (over all the trees in the forest).

Each tree is planted & grown as follows:

  1. If the number of cases in the training set is N, then sample of N cases is taken at random but with replacement. This sample will be the training set for growing the tree.
  2. If there are M input variables, a number m<
  3. Each tree is grown to the largest extent possible. There is no pruning.

For more details on this algorithm, comparing with decision tree and tuning model parameters, I would suggest you to read these articles:

  1. Introduction to Random forest – Simplified

  2. Comparing a CART model to Random Forest (Part 1)

  3. Comparing a Random Forest to a CART model (Part 2)

  4. Tuning the parameters of your Random Forest model

Python

#Import Library
from sklearn.ensemble import RandomForestClassifier
#Assumed you have, X (predictor) and Y (target) for training data set and x_test(predictor) of test_dataset
# Create Random Forest object
model= RandomForestClassifier()
# Train the model using the training sets and check score
model.fit(X, y)
#Predict Output
predicted= model.predict(x_test)

R Code

library(randomForest)
x # Fitting model
fit summary(fit)
#Predict Output 
predicted= predict(fit,x_test)

 

9. Dimensionality Reduction Algorithms

In the last 4-5 years, there has been an exponential increase in data capturing at every possible stages. Corporates/ Government Agencies/ Research organisations are not only coming with new sources but also they are capturing data in great detail.

For example: E-commerce companies are capturing more details about customer like their demographics, web crawling history, what they like or dislike, purchase history, feedback and many others to give them personalized attention more than your nearest grocery shopkeeper.

As a data scientist, the data we are offered also consist of many features, this sounds good for building good robust model but there is a challenge. How’d you identify highly significant variable(s) out 1000 or 2000? In such cases, dimensionality reduction algorithm helps us along with various other algorithms like Decision Tree, Random Forest, PCA, Factor Analysis, Identify based on correlation matrix, missing value ratio and others.

To know more about this algorithms, you can read “Beginners Guide To Learn Dimension Reduction Techniques“.

Python  Code

#Import Library
from sklearn import decomposition
#Assumed you have training and test data set as train and test
# Create PCA obeject pca= decomposition.PCA(n_components=k) #default value of k =min(n_sample, n_features)
# For Factor analysis
#fa= decomposition.FactorAnalysis()
# Reduced the dimension of training dataset using PCA
train_reduced = pca.fit_transform(train)
#Reduced the dimension of test dataset
test_reduced = pca.transform(test)
#For more detail on this, please refer  this link.

R Code

library(stats)
pca train, cor = TRUE)
train_reduced  train)
test_reduced  test)

 

10. Gradient Boosting & AdaBoost

GBM & AdaBoost are boosting algorithms used when we deal with plenty of data to make a prediction with high prediction power. Boosting is an ensemble learning algorithm which combines the prediction of several base estimators in order to improve robustness over a single estimator. It combines multiple weak or average predictors to a build strong predictor. These boosting algorithms always work well in data science competitions like Kaggle, AV Hackathon, CrowdAnalytix.

More: Know about Gradient and AdaBoost in detail

Python Code

#Import Library
from sklearn.ensemble import GradientBoostingClassifier
#Assumed you have, X (predictor) and Y (target) for training data set and x_test(predictor) of test_dataset
# Create Gradient Boosting Classifier object
model= GradientBoostingClassifier(n_estimators=100, learning_rate=1.0, max_depth=1, random_state=0)
# Train the model using the training sets and check score
model.fit(X, y)
#Predict Output
predicted= model.predict(x_test)

R Code

library(caret)
x # Fitting model
fitControl predicted= predict(fit,x_test,type= "prob")[,2] 

GradientBoostingClassifier and Random Forest are two different boosting tree classifier and often people ask about the difference between these two algorithms.

End Notes

By now, I am sure, you would have an idea of commonly used machine learning algorithms. My sole intention behind writing this article and providing the codes in R and Python is to get you started right away. If you are keen to master machine learning, start right away. Take up problems, develop a physical understanding of the process, apply these codes and see the fun!

Did you find this article useful ? Share your views and opinions in the comments section below.

If you like what you just read & want to continue your analytics learning, subscribe to our emailsfollow us on twitter or like our facebook page.