【大话IT】如何用算法学习判定“红楼梦（下）”原作者？

Ryan-liumin · 发表于 2017-3-18 08:41

楼主，你知道的太多了

help01 · 发表于 2017-3-20 10:07

不懂算法，但是觉得应该是用递归一类的算法来解决这个问题。

1.如何用算法学习判定“红楼梦（下）”原作者？您是否有更好的思路。
证明一个理论的判定问题可解，只需给出一个算法，并证明这算法就是所要求的，问题就解决了。要证明一个理论的判定问题是不可解的，首先需要把算法（机械程序）概念精确化，并给出算法概念的严格的数学定义，使一切算法的类成为明确的数学对象，从而能用严格的数学方法证明对某个理论来说不存在解决它的判定问题的算法。判定问题的研究推动了对算法理论或称可计算性理论的研究，促进了递归函数论（见递归论）和图林机器理论的建立。

2.如何做好机器学习、数据挖掘工作？需要设计哪方面的语言和算法学习？（可引荐相关专业图书，以及具体算法的学习）
每个人的基础不同起点也不同，需要学的东西也完全不一样。先说我的观点：不要想一下子吃成一个胖子；很多时候，想吃的越多反而什么也消化不了。
让我们先看一道面试题（非原创）：一条路上有N棵树，每棵树都有两个指标，一个是位置a_i（是整数），一个是体积w_i（是整数），现在要把这些树砍下来，运到K个仓库，我该如何选择这些仓库的位置（也是整数），使得搬运的成本尽量小呢？假设理想情况下，每棵树的搬运成本为树的体积 x 搬运的位移^2。
如果你看完这个题目，不能条件反射的告诉我你的思路，你其实并没有真正懂什么是聚类算法（K-means）。每个机器学习算法，犹如这道题一样具有两面性，一面是算法，也就是怎么算；一面是优化目标，为什么这么算。不能区分的看待机器学习的两面性，就不能明白为什么一群号称做机器学习研究的人整天却在玩数学。

3.机器学习应该准备哪些数学预备知识？
该熟练掌握的东西包括：
线性代数（线性空间，矩阵计算，张量）
数值数学（数值代数，数值分析，线性规划，二次规划，凸优化理论，常见的数值优化算法）
概率论和统计（没有这个基础，后面学概率图模型，统计计算都无从谈起）
实分析和泛函的基础（这块内容有助于提升抽线思维的能力，一些经典结论对之后一些理论的理解很有帮助，比如RKHS）
有了这个基础，我们再来看机器学习都有哪些东西，其实真心不多，看我用一个知乎回答就告诉你，
最简单的当然是从分类器（classification）谈起了。总结一下，学习这些东西要先知道哪些数学内容呢？
Naive Bayes：真的只需要懂一点概率论就行了。
Linear Discriminant Analysis：这个你只需要知道什么是多变量Gaussian分布。
Logistic Regression：如果知道线性回归和广义线性回归，LR也不是什么特别的东西。如果知道最大熵原理，并能从它推导出LR那说明你对LR的理解又更深入了。
Linear SVM：这个稍微复杂一点，因为问题的formulation需要先理解max-margin原理。而具体的算法实际上就只是经典的二次规划和凸优化内容。
Kernel SVM：要真正理解这个或许需要先明白什么是RKHS。然后其他算法部分只是仿照Linear SVM的简单推广。RKHS相关内容可以参照umiacs.umd.edu/~hal/doc
Adaboost：这个东西如果只需要知道算法过程，是很简单的东西。但是如果你能明白为什么这么做，在什么假设下这么做会收敛到最优解，那你的理解也非常不错了。
Decision Tree：有两个需要了解CART 和 c4.5。这个很简单，没什么好说的，但是你能不能高效的实现它们呢？
Neural network：这个是我见过最傻的模型，你要知道怎么做优化，乃至怎么做随机优化，结果看天吃饭。
再来看一些非监督模型，比如经典的有
数据处理与可视化：PCA，LDA，MDS，以及其他“高大上”但不一定work的manifold learning算法
聚类算法，以及如何评价聚类结果
稀疏编码：如何把一个带LASSO的问题转化成线性约束？有哪些别的更快的方法求解LASSO。
以上这些东西，算是入门性质的。本科毕业后大概一年左右，这些东西我就基本熟悉了。要学习这些东西，看一些教材自然是好的，但是书里废话比较多呢，而且一本书的作者知道的东西毕竟有限，我都是倾向直接从维基出发找资料看的。说实话，现在很少会自己去实现这些算法了，这些经典算法都有现成的开源工具。事实上要写一个高效的Linear SVM也不是很容易的事情。
书分为两种，一种书看完了就是看完了，你学到了一堆技能，但却不能用这些技能产生新的知识，面对问题也不能因地制宜，如果是这样学估计只能用来应付找工作面试吧；另一种书看完了才是学习新东西的开始，你学到了如何读懂别人的论文，如何开发新的知识，如何根据情况选择和调整算法。
概率图模型（Probabilistic graphical model）：我是在Coursera上学习概率图模型这门课的，讲得真的非常好，正打算过二周目。学完这个课，掌握了图模型的设计，推断，和采样方法之后，就可以开始学习两个核心的机器学习模型，一个是Latent Dirichlet Allocation（LDA），常用于文本处理；一个是Probabilistic Matrix Factorization（PMF），常用于推荐系统。
统计计算（Statistical computing）：这个课系统的介绍了数值积分方法，Monte Carlo方法（importance sampling, MCMC，Sequential/Particle MCMC，bootstrap），EM/MM。学完这门课，你能对这个领域的工具有个全局性的了解，明白每个工具的利弊，它们产生的历史来源，从而在具体问题中正确的选择使用它们。
有了这些工具，你会发现大部分research的工作都是在这些细分领域做一些简单的扩展。比如Bayesian PMF（ICML’08）这篇文章几乎就完全是MCMC在PMF的应用。话说回来，Research大部分时候就是以这样一种循序渐进的方式进行的，把一些现成的idea排列组合。
深度学习（Deep learning）：说实话我刚开始接触这块内容发现，这尼玛就是传说中的黑科技啊。你不知道模型里面发生了什么，好坏都是看天吃饭的感觉。为了搞清楚这个，我决定重头开始实现神经网络。（代码在bobye/neuron · GitHub ）前前后后花了近半年的时间，在实现的过程中，我学习了构造和训练神经网络的各个细节。我是从Stanford这个Tutorial开始学习的UFLDL Tutorial 课程资料里提供了Matlab的源码，不过我喜欢重新造轮子，那个时候恰好在学习Scala，就用Scala重写了一个神经网络的库（这个语言的特性非常适合写神经网络的算法）。
近几年深度学习的主流被深度卷积网络代替，这种监督学习的算法虽然对某些问题十分有效，但是数学上并不是特别神奇的东西，我还是比较关注那些非监督的神经网络。
优化（optimization）：没有优化算法，任何机器学习模型都是空中楼阁，如何用更高效的优化算法，如何trade-off 计算时间和准确度，如何把已有问题scale到更高规模的数据上一直都是“优化大师们”做不完的工作。这也是一个非常大的分支，我觉得现在比较流行的两个大类是随机梯度优化和ADMM。前者用来解决大规模非约束优化问题，现实情景用的很多，但我们对它知道的很少；后者用来解决带约束问题，有很多变体。此外，优化大家庭也又有很多别的成员，这时候我要推荐的资料包括J Nocedal的numerical optimization这本书，讲的内容非常充实。此外ADMM的内容当然看Boyd巨牛11年的Tutorial paper。
PAC学习理论（PAC Learning）：这个理论已经相对古老了，它的历史价值很大，应用价值很有争议，但是一直有人在继续这个方向的工作，并试图用它来构造新的模型，所以还是有必要知道的。推荐一下最近的新书：Understanding Machine Learning： From Theory To Algorithms.
非参数贝叶斯统计（Non-parametric Bayesian statistics）：这个方向还非常年轻，有很多需要挖掘的东西，也是我PhD的一个重要课题。