算法的起源

在很多人看来，算法这两个字好像就是跟机器学习或者人工智能绑定，总是包含着一些很高深的数学推导和计算机知识，但实际上早在计算机开始使用算法之前，人类就将算法应用到生活当中了。

“算法”()一词得名于波斯数学家花拉子密。公元9世纪，这位数学家写过一本书，讨论用纸笔解决数学问题的技巧。［书名为“al-Jabr wa’l-Muqabala”，其中的“al-jabr”就是后来“algebra”（代数）这个词的前身。］不过，最早的数学算法早于花拉子密。在巴格达附近出土的4000年前的苏美尔人泥板文献上，就刻有一幅长除法示意图。

而在中国古代，算法被称为”术”,最早出现在《周髀算经》、《九章算术》。特别是《九章算术》，给出四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃拉托斯特尼筛法，线性方程组求解的算法。三国时代的刘徽给出求圆周率的算法：刘徽割圆术。自唐代以来，历代更有许多专门论述“算法”的专著：

• 唐代：《一位算法》 一卷，《算法》 一卷；
• 宋代：《算法绪论》 一卷、《算法秘诀》 一卷；最著名的是杨辉的《杨辉算法》；
• 元代：《丁巨算法》；
• 明代：程大位 《算法统宗》
• 清代：《开平算法》、《算法一得》、《算法全书》。

所以我们最早接触到算法可能就是:

二次方程求根就是一个算法，即使是从严格的算法定义上来看也一样，它具有输入和输出，也有明确的步骤，并且可以在有限的时间内得到结果。而这个算法也从公元前2000年左右时只能解形如

的正数根的形式一直被先人们完善到最终我们在课本上学到的复数范围内恒有解的最终形式。

但是算法却不仅限于数学。比如在按照一份每个步骤都明确定量的食谱烤面包时，食谱就可以看作是一个算法。同样对于设计师来说，按照一套明确的流程解决一个设计问题也是在遵循着一种算法。

Brian Christian在《algorithms to live by》里说: 算法是数学和工程技术糅合而成的怪异混合体。今天的算法设计不仅需要借助计算机科学、数学和工程技术，还需要得到统计学、运筹学等相关领域的帮助。此外，我们不仅需要考虑计算机算法设计与人类思维活动之间的关系，还需要认真研究认知学、心理学、经济学等学科。

所以当我们再来面对“算法”这个词的时候，我们就不必纠结各个词条对他的释义到底是在数学领域还是计算机领域，也并不需要特别在意那些定语，它的关键词更应该是“解决一类问题”，但如果我们想利用计算机来执行算法，我们需要将整个解题过程编成一系列精准的指令，并经过一系列诸如对其占用内存，运行时间等的验证和分析以明确算法的性能。

优化算法与机器学习

我们的生活中已经充满了机器学习带给我们的奇妙的体验，比如邮箱自动为我们过滤垃圾邮件，淘宝的智能推荐，短视频网站的推荐系统，我们一定知道不可能有一个人在手机背后给每个人找出他可能喜欢的商品，没错，这些功能背后就是机器学习算法。是的，就是通过算法让计算机学习垃圾邮件有哪些特征，学习喜欢这一类商品的人还会喜欢哪些商品，学习爱看这种视频的人还会被什么样的视频所吸引。

机器学习在不同时期，领域，用途上有很多不同的形式，也和很多领域有交叉和共同发展，如模式识别、数据挖掘等等。而且如果我们细心的话也会发现一个问题，当我们在视频网站看电影时，有的网站会给我们推荐与刚播放完的影片相同主演，导演的电影，有的网站会推荐同类型的，而有的网站推荐的电影是我们从未尝试过的类型，我们可能隐隐约约会感觉到他们可能在挖掘我们观影倾向上的不同的关注点，这就是针对同一问题（推荐）所使用的不同算法。

可能这些问题离我们的职业比较遥远，我们最熟悉的问题还是优化(optimization)。2012年10月华盛顿大学的教授Pedro Domingos发表在《communications of the acm》的文章《A Few Useful Things to Know About Machine Learning》中有这样的总结

Learning = Representation +Evaluation + Optimization

Representation包含很多东西，主要是如何对一个问题建模，选用什么样的模型（比如神经网络，决策树等），我们到底需要算法发现那些特征之间的关系等（对应模型的输入输出）。Evaluation指的是评价函数，目标函数(比如均方误差,似然函数等)，这是评价模型性能的指标。Optimization是指对目标函数的优化（比如梯度下降，牛顿法等）， 原文中给出了每个部分具有代表性的算法

优化算法我们在之前的文章中已经介绍过几种了，比如NSGA-II,粒子群等。

Domingos教授把机器学习算法分为五个流派 分别是Symbolists(符号主义)，贝叶斯派(Bayesians),联结主义(Connectionist),进化主义(Evolutionaries)和类推学派(Analogizer)。这是他在2015年的Smart Data 2015 Conference会议上的PPT中的一页

这里我们最熟悉的应该就是进化主义了，遗传算法就是进化主义代表人物Holland在上世纪60年代提出的。有趣的是，Holland最开始研究的是神经网络（联结学派的代表算法），后在读研时受到（Ronald Fisher）的经典著作《The Genet: Cal Theory of Natural Selection》的影响，开始将进化论的精华理论变成一种算法。

在最初遗传算法开始被人熟知的时候，适应度函数是算法的一个关键输入，给定一个待定程序和某个设定的目标，适应度函数会给程序打分，反映它与目标的契合度。虽然在真实的自然选择中，整个进化过程并没有明确，已知的目标，但对于机器学习来说，设定一个适应度函数是一个直观且明确的事情。遗传算法就有点像选择育种。达尔文在《物种起源》开篇时就谈到这个问题。现在我们自然而然地认为，经过驯化的动植物就是一代一代经过选择和交配的结果，是最能让我们达到各种用途的有机体：果实最大的玉米、最甜的果树、毛最多的羊、最强健的马匹。遗传算法也会做同样的事情，它产出的是程序而不是活的生物体，而一代对它而言是几秒的计算机时间，而不是生物的一生（Pedro Domingos，2015）。

当然现在我们知道进化的原因是DNA，这也是遗传算法最重要的一部分，DNA依据碱基对的序列对有机体进行编码，同理，我们也可以依据一串二进制数字对程序进行编码。DNA的4个基本组成单位，不是0和1，而是4个基本碱基，包括腺嘌呤、胸腺嘧啶、胞嘧啶、鸟嘌呤，但这仅仅是表面上的差异。变量，无论在DNA序列中，还是在位串中，都可通过几种方法产生。最简单的方法就是点突变，即随意翻转位串中的一个比特值，或者改变一段DNA中的单个基本碱基（Pedro Domingos，2015）。染色体的交叉也会产生两条新的染色体，而虽然NSGA-II并没有适应度函数（用排序等过程代替），但仍然包含交叉变异等过程（关于遗传算法的具体过程和案例可以参考之前的文章）。

联结学派的神经网络我们也在之前的公众号文章中有过简单的介绍，其主要思想就是对大脑的仿真（如神经网络模拟的是神经元），类比进化学派模拟进化的过程，我们已经能发现这些机器学习算法的起源似乎并不是计算机也不是数学，而是对我们人类自身的探索，然而真的是这样吗？我们会在本系列的下一篇文章介绍另外几个学派的主要思想和算法以及我们究竟如何使用算法解决我们遇到的问题。