介绍
上周投了美团点评机器学习、自然语言处理岗的实习生岗位，今天晚上7点参加了在线笔试，该篇博客总结记录今天晚上笔试的相关问题。
题型
- 单选题
- 多选题
- 问答题
- 编程题
涉及知识点
单选题、多选题涉及数据结构、机器学习相关的基础知识，题目中出现了以下知识点：
- 入栈出栈顺序
- 复杂度分析
- 哪些模型可用于回归
- 哪些模型属于生成机
- CART的特点
- 增大训练样本的数量是否会使训练结果逼近测试结果
问答题是关于决策树复杂度的分析，题目：
- 给定树高H，样本数N，特征数M，每个节点分裂值的个数为10，求决策树训练的复杂度。
编程题题目：
- 给定一张图的邻接表，判断图中是否有环，给出思路，平均复杂度分析，并编程实现。
笔记
判别式模型与生成式模型
相关链接：
生成方法的特点：
- 从统计的角度表示数据的分布情况，能够反映同类数据本身的相似度;
- 生成方法还原出联合概率分布，而判别方法不能;
- 生成方法的学习收敛速度更快、即当样本容量增加的时候，学到的模型可以更快地收敛于真实模型;
- 当存在隐变量时，扔可以用生成方法学习，此时判别方法不能用。
判别方法的特点：
- 判别方法寻找不同类别之间的最优分类面，反映的是异类数据之间的差异;
- 判别方法利用了训练数据的类别标识信息，直接学习的是条件概率P(Y|X)或者决策函数f(X)，直接面对预测，往往学习的准确率更高;
- 由于直接学习条件概率P(Y|X)或者决策函数f(X)，可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题;
- 缺点是不能反映训练数据本身的特性。
邻接表
相关链接
bootstrap, boosting, bagging
相关链接
分类中通常使用将多个弱分类器组合成强分类器进行分类的方法，统称为集成分类方法（Ensemble Method）。比较简单的如在Boosting之前出现Bagging的方法，首先从从整体样本集合中抽样采取不同的训练集训练弱分类器，然后使用多个弱分类器进行voting，最终的结果是分类器投票的优胜结果。这种简单的voting策略通常难以有很好的效果。直到后来的Boosting方法问世，组合弱分类器的威力才被发挥出来。Boosting意为加强、提升，也就是说将弱分类器提升为强分类器。而我们常听到的AdaBoost是Boosting发展到后来最为代表性的一类。所谓AdaBoost，即Adaptive Boosting，是指弱分类器根据学习的结果反馈Adaptively调整假设的错误率，所以也不需要任何的先验知识就可以自主训练。
bootstrps bagging boosting这几个概念经常用到，现仔细学习了一下： 他们都属于集成学习方法，(如：Bagging，Boosting，Stacking)，将训练的学习器集成在一起,原理来源于PAC学习模型（ProbablyApproximately CorrectK）。Kearns和Valiant指出，在PAC学习模型中，若存在一 个多项式级的学习算法来识别一组概念，并且识别正确率很高，那么这组概念是强可学习的；而如果学习算法识别一组概念的正确率仅比随机猜测略好，那么这组概念是弱可学习的。他们提出了弱学习算法与强学习算法的等价性问题，即是否可以将弱学习算法提升成强学习算法。如果两者等价，那么在学习概念时，只要找到一个比随机猜测略好的弱学习算法，就可以将其提升为强学习算法，而不必直接去找通常情况下很难获得的强学习算法。
bootstraps:名字来自成语“pull up by your ownbootstraps”，意思是依靠你自己的资源，它是一种有放回的抽样方法，学习中还发现有种叫jackknife的方法，它是每一次移除一个样本。
bagging:bootstrapaggregating的缩写。让该学习算法训练多轮，每轮的训练集由从初始的训练集中随机取出的n个训练倒组成，初始训练例在某轮训练集中可以出现多次或根本不出现训练之后可得到一个预测函数序列h．，⋯⋯h 最终的预测函数H对分类问题采用投票方式，对回归问题采用简单平均方法对新示例进行判别。 –(训练R个分类器fi，分类器之间其他相同就是参数不同。其中fi是通过从训练集合中(N篇文档)随机取(取后放回)N次文档构成的训练集合训练得到的。–对于新文档d，用这R个分类器去分类，得到的最多的那个类别作为d的最终类别.)
boosting:其中主要的是AdaBoost（AdaptiveBoosting）。初始化时对每一个训练例赋相等的权重1／n，然后用该学算法对训练集训练t轮，每次训练后，对训练失败的训练例赋以较大的权重，也就是让学习算法在后续的学习中集中对比较难的训练铡进行学习，从而得到一个预测函数序列h一⋯h其中h．也有一定的权重，预测效果好的预测函数权重较大，反之较小。最终的预测函数H对分类问题采用有权重的投票方式，对回归问题采用加权平均的方法对新示例进行判别。(类似Bagging方法，但是训练是串行进行的，第k个分类器训练时关注对前k-1分类器中错分的文档，即不是随机取，而是加大取这些文档的概率).
Bagging与Boosting的区别：在于Bagging的训练集的选择是随机的，各轮训练集之间相互独立，而Boostlng的训练集的选择是独立的，各轮训练集的选择与前面各轮的学习结果有关；Bagging的各个预测函数没有权重，而Boosting是有权重的；Bagging的各个预测函数可以并行生成，而Boosting的各个预测函数只能顺序生成。对于象神经网络这样极为耗时的学习方法。Bagging可通过并行训练节省大量时间开销。bagging和boosting都可以有效地提高分类的准确性。在大多数数据集中，boosting的准确性比bagging高。在有些数据集中，boosting会引起退化。—Overfit
简单来说，Adaboost有很多优点:
- 1、adaboost是一种有很高精度的分类器
- 2、可以使用各种方法构建子分类器，adaboost算法提供的是框架
- 3、当使用简单分类器时，计算出的结果是可以理解的。而且弱分类器构造极其简单
- 4、简单，不用做特征筛选
- 5、不用担心overfitting！
- 总之：adaboost是简单，有效。
Adaboost可以用来做特征选择。