机器学习方面常考的面试题总结，随时更新，参考了一些博客和书籍，力求简单易懂。第一部分主要介绍LR和决策树两个简单的模型。第二部分介绍SVM相关，第三部分介绍boosting、隐马模型，第四部分介绍特征选择与计算学习理论，第五部分介绍无监督学习与强化学习。
一、LR
1. 介绍逻辑回归。
logistic 回归为判别模型，不是线性回归模型。
经过学习后的 LR 分类器是一组权值 w0,w1…wn，权值与测试数据按照线性加和得到：x=w0+w1x1+…+wnxn
这里x1…xn是样本的n个特征。然后按照sigmoid函数的形式求出f(x)=1/(1+exp(-x))
sigmoid 函数的定义域为（-INF,+INF）,值域为(0,1)，在0的附近函数变化比较陡峭，因此适合作为分类函数。
w0,w1…wn这组权值是通过极大似然估计得到的。（梯度上升法或者牛顿法）
2. LR 为什么用 sigmoid 函数，这个函数有什么优缺点？
优点：模型简单，可导（导数形式简单），0-1阶跃，定义域为（-INF,+INF）,值域为(0,1)
缺点：幂运算比较耗时，容易出现梯度消失。
数学原理 https://www.zhihu.com/question/35322351
二、梯度下降，牛顿法与拟牛顿法
1. 梯度下降法
在判别式模型中，往往需要学习参数，使得模型f(x)逼近真实的y.
梯度下降法和牛顿、拟牛顿法是常用的参数学习方法。
梯度是函数值变化最快的方向。
梯度下降过程：0.每个参数初始化为1 1.计算整个数据集的梯度 2.alphagradient更新系数 3.达到阈值，收敛。
随机梯度下降过程：0. 每个参数初始化为1 1.计算样本的梯度（batch_size） 2.alphagradient更新系数 3. 达到阈值，收敛。
2. 牛顿法与拟牛顿法
假设任务是优化目标函数f，求f的极大极小问题可以转化为求解f的导数f’=0的问题。为了求解f’=0,把f(x)泰勒展开到二阶形式,最终可以得到deta(x)=-(f’(xn))/(f’’(xn)),得出迭代公式：xn+1=xn-(f’(xn)/f’’(xn)),n=0,1…
牛顿法可以得到曲线本身的信息，比梯度下降法更容易收敛（迭代次数更少。
对于正定二次函数，牛顿法一步迭代就可以达到最优解。但是牛顿法是局部收敛，初始点选择不恰当时，往往会导致不收敛。牛顿法不是下降算法，二阶海塞矩阵非正定时，不能保证产生的方向是下降方向。二阶还塞矩阵还必须可逆，否则算法进行困难。总结起来缺点：算法运算量大，对函数要求苛刻（二阶连续可微分，海塞矩阵可逆）
考虑到牛顿法的这些缺点，设计了拟牛顿法，基本思想是：不用二阶偏导数而构造出可以近似海塞矩阵（海塞矩阵的逆）的正定对称阵，在拟牛顿条件下优化目标函数，不同的构造方法就产生了不同的拟牛顿法。主要的拟牛顿法有DFP算法、BFGS算法，L-BFGS算法。（具体推导看 http://blog.csdn.net/itplus/article/details/21896981 ）
三、决策树
1. 决策树原理
一棵决策树包含一个根节点，一系列内部节点与叶节点，每个叶节点对应于决策结果，其他每个节点对应于一个属性测试，每个节点的样本集合根据属性测试的结果被划分到子节点中，根节点包含样本全集，从根节点到每个叶节点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一棵泛化能力强的决策树。决策树是一个递归划分过程，其最核心的问题就是如何选择最优划分属性。
2. 决策树如何防止过拟合
剪枝是决策树学习中防止过拟合的主要手段，在决策树学习过程中，为了尽可能正确分类训练样本，节点划分不断重复，造成决策树分支过多，这时就容易导致过拟合。决策树剪枝主要策略有预剪枝和后剪枝，预剪枝是指在决策树生成过程中，对每个节点划分前先进行估计，若当前节点的划分不能带来泛化性能的提升，则停止划分。后剪枝则是先训练生成一棵完整的决策树，然后自底向下的对非叶节点进行考察，若将某子树直接替换成叶节点能带来泛化性能提升，那就将该子树替换为叶节点。
3. C45,ID3与CART
ID3 与 C45算法最大的区别就是，ID3使用了信息增益来划分属性，C45先从候选划分属性中找出信息增益高于平均水平的属性，再从其中选择信息增益率最高的。（主要原因是，信息增益比较偏重可取值数目较多的属性，信息增益率则比较偏重可取值数目较少的属性）
样本集合D的信息熵定义为 Ent(D)=-∑pklog2pk (对每种标注求和)pk是第k类样本所占的比例。Ent(D)越小，则D的纯度越高。
假定离散属性a有V个可能的取值，所有在a上取值为v的样本记为Dv,给每个分支节点赋予权重Dv/D（个数相除，包含样本越多权重越大），那么用属性a对样本D进行划分所获得的信息增益为：Gain(D,a)=Ent(D)-∑(Dv/D)Ent(Dv)（对每种取值求和），信息增益越大，则意味着使用属性a来进行划分所获得的纯度提升越大。
而ID3使用的信息增益率则定义为 Gain_ratio(D,a)=Gain(D,a)/IV(a)
IV(a)=-∑(Dv/D)log2(Dv/D)(对每种取值求和)
CART 决策树使用基尼系数来选择划分属性。Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini(D)越小，则D的纯度越高。
Gini(D)=1-∑pk^2(对每个标记求和)，Gini_index(D,a)=∑(Dv/D)*Gini(Dv),在候选属性集合中，选择那个使得划分后基尼系数最小的属性作为划分属性。