机器学习的算法和普通《算法导论》里的算法有什么本质上的异同？

点击上方“Jerry的算法和NLP”，选择“星标”公众号

重磅干货，第一时间送达

有一个笑话是：需要多少个数学家来修灯泡?

答案是3个：

1. 第一个数学家证明修灯泡的办法存在（existence），

2. 第二数学家证明修灯泡的方法只有一个（uniqueness），

3. 第三个数学家找到了一个算法 （constructive algorithm）。

因此一种定义算法的方法就是把 算法当成是解决一个问题的一系列步骤 。算法导论里面的大部分内容是符合这个描述的，比方说排序，动态规划，深搜广搜，字符串处理。机器学习里面常用的迭代优化的方法本质也是解决问题的一系列步骤。所以从 本质上他们和算法导论里面的算法是一样的 。

当然了，个人认为机器学习会需要区分建模（modelling) 和学习（inference）这两个不同的部分，题主说到的

...是用数学的方式试图去描述和理解我们的世界...

指的其实是建模的部分，大概的意思就是我们试图去建立一个模型来描述我们想要解决的问题。比方说我们可以用一个线性模型来描述两个变量之间的关系，用一个HMM来对自然语言建模等。

处理问题的部分在机器学习里面我们叫做学习，这个就对应到给予我们一些给予某个模型假设下面的一些数据，我们如何找出最好的这个模型的参数(MLE)，或者参数的后验分布(MAP)，或者推断这个模型里面我们没有观察到的隐变量(latent variables)。解决这些问题的方法包括了比方优化（凸非凸，组合或者连续），或者蒙特卡洛类算法（e.g. Policy Gradients, Black-box variational inference)。

另外，机器学习里面的算法长得跟算法导论里面的算法不太像还和我们想要解决的问题有关。机器学习里面大部分想要解决的问题是NP困难的 (比方说最宽泛的优化问题）。这类问题一般会考虑用迭代求解的办法尝试寻找一个近似解。又或者有时候直接求解一个问题的复杂度会是O(n^3)但是迭代的话现实中会比理论的更快收敛(e.g. matrix inversion by conjugate gradients vs. by direct inversion)，算法导论里面的问题比如 排序 或者字符串处理并不在这一类NP困难的问题内, 因此迭代的方法可能不那么常见。

此外，算法长得不太一样还可能是因为算法研究的关注点出现了变化，引用Sanjeev Arora的notes里面的一番话。

> Undergrad algorithms is largely about algorithms discovered before 1990; grad algorithms is a lot about algorithms discovered since 1990. What happened in 1990 that caused

> this change, you may ask? Nothing. I chose this arbitrarily; maybe I could have said 1985

> or 1995. There was no single event but just a gradual shift in the emphasis and goals of

> computer science as it became a more mature field.

> In the first few decades of computer science, algorithms research was driven by the goal

> of designing basic components of a computer: operating systems, compilers, networks, etc.

> Other motivations were classical problems in discrete mathematics, operations research,

> graph theory. The algorithmic ideas that came out of these quests form the core of undergraduate course: data structures, graph traversal, string matching, parsing, network

> flows, matchings, etc. Starting around 1990 theoretical computer science broadened its

> horizons and started looking at new problems: algorithms for bioinformatics, algorithms

> and mechanism design for e-commerce, algorithms to understand big data or big networks.

> This changed algorithms research and the change is ongoing. One big change is that it is

> often unclear what the algorithmic problem even is. Identifying it is part of the challenge.

> Thus good modeling is important. This in turn is shaped by understanding what is possible

> (given our understanding of computational complexity) and what is reasonable given the

> limitations of the type of inputs we are given

总结下来就是算法导论里面的算法大致是为了解决传统CS领域比方说操作系统编译器里面会遇到的问题，而更新的算法研究（包含了很多我们今天看到的机器学习算法）则尝试解决一些我们甚至不知道怎么建模的问题。这也是为什么在经典算法里面我们经常看到输入是一个数组，或者一个图，但是机器学习的问题里面我们会看到输入是矩阵，因为矩阵这种描述方法可以让我们不给我们的问题的结构加上太多的假设，同时我们可以通过研究这些抽象的输入的性质然后给他们赋予现实意义（SVD as best rank-k approximations vs. used it for collaborative filtering in recommender systems).

《算法导论》的算法与机器学习算法的关系，就好像做数学题和数学建模的关系。

算法导论的算法是面向有精确解的问题的求解方法。而机器学习算法更多的是一种面向无精确解（或精确解很难得到）的问题的一种逼近策略。

举个栗子：

做一道数学题（算法题），用到了麦克劳林公式（动态规划算法），得到了一个精确的解（最优的方案）。其中，数学题中精确的解、算法问题中的最优方案，都是唯一的、精确的。《算法导论》中涉及的算法大多都是上述这样有精确解的问题的求解方法。

而当需要预测明天的天气时，没有算法可以百分之百地保证预测一定是准确的，不到明天没有人能精确知道明天的天气。但我可以了解今天晚上的风向、湿度等等信息，利用机器学习算法来预测明天是否会下雨。最后的预测结果会or不会下雨都不是一个精确的结果，机器学习预测的结果只是一个估计的、近似的结果，但仍是有价值。另外，机器学习算法的一大特点是，它没有面向问题直接编写程序，而是建立学习模型解决问题，也是其与算法导论中的算法的一大不同。

算法导论只用到了：数学分析、简单概率论、线性代数；基本是工科大一大二所学；

而能用到的，基本都是证明算法的正确性；不需要证明的话，基本用不到数学工具，实际应用，照抄其中的代码，可以直接应用到工程中；如果不考虑证明，基本不存在什么数学模型（图论除外），而是人们对实际工程应用的巧妙构思和巧妙解法。

而想要参透 机器学习 ，除了上述基本数学工具，必须掌握：概率论、数理统计、最优化、凸分析、甚至是泛函分析等等高级数学工具，这些就已经基本涉及到应用数学专业大三、大四的数学水平了。这里面基本都是数学模型，解法基于数学理论；如果不搞懂这里面的数学，连基本的原理都无法搞清楚，更何谈应用了。

寒假马上就来了，博主搜到了这本机器学习实战的电子书，愿与君共同进步

后台回复 「 机器学习实战 」 ，将这本书PDF带回家过年把！

Jerry的算法和NLP，一个注重技术领域的平台！

千山万水总是情，点个「好看」行不行。