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

这是个很好的问题。如果只是看算法的“样子”，可能会比较迷惑，机器学习算法中也使用了经典算法策略，例如监督学习的决策树用了分治、流型学习的isomap用了最短路径，强化学习的策略评估是动态规划等等，看上去也没什么区别，但是直觉上机器学习算法与经典算法又很不一样，这里面的关键区别在哪呢，我们可以尝试从另一个视角来看待算法。

在一些人眼里，算法是解决问题的步骤，在另一些人眼里，算法只是一个证明，是关于一个问题可以在多少时间内求解到何种程度的证明。后者更关心的，是哪些问题可以求解哪些问题不可以、可以求解的问题哪些是能高效求解的等等。于是有了关于问题类的定义，例如可（有效）计算的类别——NP类问题的（优化）定义大致可以描述为

存在非确定图灵机，对于任给问题的实例，能在关于问题规模的多项式时间找到该问题的解。

相似的，对于学习问题也有类别划分，Leslie Valiant给出了可（有效）（监督）学习问题类的定义——近似概率正确可学习，大致描述为

对于任给的[0,1]间的误差常数和概率常数，存在算法A对于任给学习问题的实例，使用不超过关于误差常数和概率常数（实际上是它们的倒数）的多项式个独立同分布采样的样本，就能以足够的概率（1-概率常数）找到一个模型，其真实误差小于误差常数。

从上面的定义中可以看到，对于经典问题类的定义非常清晰：图灵机有形式定义，“问题的解”指优化问题最优解，定义中不存在任何不确定的部分。然而学习问题的定义中包含了一处很不确定的地方：算法的输入是有限样本，输出却是关于真实误差。在输入有限样本时，算法无从得知真实误差。从经典算法角度，这是要解决一个看不见的问题，也就是不适定问题，是没法解决的。因此在学习问题的定义中，加入了概率，让算法去猜面临的问题是什么，容忍一定猜错的可能。

因此，经典算法是在解决问题，然而学习算法中有些环节并不是在解决问题，而是在猜测问题，有了对问题的猜测，才开始解决问题，不同的学习算法就包含了不同的猜问题的策略，也就是归纳偏执（inductive bias）。这一部分就是经典算法中所没有的部分，是机器学习研究的核心。

机器学习论文看起来常常以优化技术为中心，容易让人误以为机器学习就是优化。Pedro Domingos 2012年在CACM发表的《A Few Useful Things to Know about Machine Learning》

是一篇有意思的文章，里面给出了一个定义：

学习=表示+评价+优化

大体来讲，“表示”指数据和模型的表达形式，例如数据是一个向量还是一个图、模型是神经网络还是决策树；“评价”定义了我们想要什么样的模型；“优化”则是学习过程的实施者。从这个定义看，"优化"对应了经典算法（包括组合优化、凸优化等），而"表示+评价"则是机器学习独有的，决定了学习系统能够达到的泛化能力。不同的"表示+评价"，关系到猜问题的策略，定义了优化要解决的问题是什么。因此也可以看到，机器学习算法，不仅包含了如何解决问题的部分，还包含了如何定义问题的部分。

总的来说，经典算法是在适定(well-defined)问题下的求解过程，机器学习算法是在病态(ill-posed)问题下的问题重定义与求解的过程。个人理解仅供参考。

====

写了个开头有这么多人点赞，感觉很惭愧，自己挖的坑，赶在年三十前，含泪也要填完。。。

另外“非精确求解”和“概率求解”都不是机器学习算法的特征，在经典算法中同样有近似算法和随机算法，这些算法本身并不认为是机器学习算法（当然可以用于机器学习），因为它们仍然面对的是适定问题。