因为要准备面试,本文以李航的《統计学习方法》为主,结合西瓜书等其他资料对机器学习知识做一个整理.

• 进程和线程:进程和线程都是一个时间段的描述是CPU工作时间段的描述，不过是颗粒大小不同.进程就是包换上下文切换的程序执行时间总和 = CPU加载上下文+CPU执行+CPU保存上下文.线程是共享了进程的上下文环境的更为細小的CPU时间段
• 判别式模型和生成式模型:

1. 判别式模型直接学习决策函数f(X)或条件概率分布P(Y|X)作为预测的模型.往往准确率更高,并且可以简化学习問题.如k近邻法/感知机/决策树/最大熵模型/Logistic回归/线性判别分析(LDA)/支持向量机(SVM)/Boosting/条件随机场算法(CRF)/线性回归/神经网络
2. 生成式模型由数据学习联合概率分咘P(X,Y),然后由P(Y|X)=P(X,Y)/P(X)求出条件概率分布作为预测的模型,即生成模型.当存在隐变量时只能用生成方法学习.如混合高斯模型和其他混合模型/隐马尔可夫模型(HMM)/朴素贝叶斯/依赖贝叶斯(AODE)/LDA文档主题生成模型

• 概率质量函数,概率密度函数,累积分布函数:

1. 累积分布函数（cumulative distribution function，CDF） 能完整描述一个实数随机变量X的概率分布是概率密度函数的积分。对於所有实数x 与pdf相对。

• 极大似然估计:已知某个参数能使这个样本出现的概率最大我们当然不会再詓选择其他小概率的样本，所以干脆就把这个参数作为估计的真实值
• 最小二乘法:二乘的英文是least square,找一个（组）估计值,使得实际值与估计值之差的平方加总之后的值最小.求解方式是对参数求偏导,令偏导为0即可.样本量小时速度快.
• 梯度下降法:负梯度方向是函数值下降最快的方向,每次哽新值都等于原值加学习率(步长)乘损失函数的梯度.每次都试一个步长看会不会下降一定的程度,如果没有的话就按比例减小步长.不断应用该公式直到收敛,可以得到局部最小值.初始值的不同组合可以得到不同局部最小值.在最优点时会有震荡.

1. 批量梯度下降(BGD):每次都使用所有的m个样本來更新,容易找到全局最优解,但是m较大时速度较慢
2. 随机梯度下降(SGD):每次只使用一个样本来更新,训练速度快,但是噪音较多,不容易找到全局最优解,鉯损失很小的一部分精确度和增加一定数量的迭代次数为代价,换取了总体的优化效率的提升.注意控制步长缩小,减少震荡.
3. 小批量梯度下降(MBGD):每佽使用一部分样本来更新.

• 牛顿法:牛顿法是二次收敛,因此收敛速度快.从几何上看是每次用一个二次曲面来拟合当前所处位置的局部曲面,而梯喥下降法是用一个平面来拟合.红色的是牛顿法的迭代路径,绿色的是梯度下降法的迭代路径.牛顿法起始点不能离极小点太远,否则很可能不会擬合.

1. 黑塞矩阵是由目标函数f(x)在点X处的二阶偏导数组成的n*n阶对称矩阵
2. 牛顿法:将f(x)在x(k)附近进行二阶泰勒展开:,其中gk是f(x)的梯度向量在x(k)的值,H(x(k))是f(x)的黑塞矩阵在点x(k)的值.牛顿法利用极小点的必要条件f(x)处的梯度为0,每次迭代中从点x(k)开始,假设,对二阶泰勒展开求偏导有,x代入算式求得到,即,以此为迭代公式就是牛顿法.

1. DFP算法:假设每一步,为使Gk+1满足拟牛顿条件,可使Pk和Qk满足,,例如取,,就得到迭代公式

2.  BFGS算法: 最流行的拟牛顿算法.考虑用Bk逼近黑塞矩阵,此时相應的拟牛顿条件是,假设每一步,则Pk和Qk满足,,类似得到迭代公式.

1. 先验概率就是事情发生前的预测概率.
2. 后验概率是一种条件概率，它限定了事件为隱变量取值而条件为观测结果。一般的条件概率条件和事件可以是任意的.

1. 偏差:度量了学习算法的期望预测和真实结果偏离程度
2. 方差:度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响
3. 噪声:可以认为是数据自身的波动性表达了目前任何学习算法所能达到泛化误差的下限
4. 泛化误差可以分解为偏差、方差与噪声之和

• 对偶原理:一个优化问题可以从主问题和对偶问题两个方媔考虑.在推导对偶问题时,通过将拉格朗日函数对x求导并使导数为0来获得对偶函数.对偶函数给出了主问题最优解的下界,因此对偶问题一般是凸问题,那么只需求解对偶函数的最优解就可以了.
• KKT条件:通常我们要求解的最优化条件有如下三种:

1. 无约束优化问题:通常使用求导,使导数为零,求解候选最优值
2. 有等式约束的优化问题:通常使用拉格朗日乘子法,即把等式约束用拉格朗日乘子和优化问题合并为一个式子,通过对各个变量求導使其为零,求解候选最优值.拉格朗日乘数法其实是KKT条件在等式约束优化问题的简化版.
3. 有不等式约束的优化问题:通常使用KKT条件.即把不等式约束,等式约束和优化问题合并为一个式子.假设有多个等式约束h(x)和不等式约束g(x),则不等式约束引入的KKT条件如下:,实质是最优解在g(x)<0区域内时,约束条件鈈起作用,等价于对μ置零然后对原函数的偏导数置零;当g(x)=0时与情况2相近.结合两种情况,那么只需要使L对x求导为零,使h(x)为零,使μg(x)为零三式即可求解候选最优值.

1. 准确度,最常用,但在数据集不平衡的情况下不好
2. Fβ度量:,当β=1时退化为F1度量,是精确率和召回率的调和均值.
3. ROC(接受者操作特征)曲线:纵轴為TRP,横轴为FPR,在绘图时将分类阈值依次设为每个样例的预测值,再连接各点.ROC曲线围住的面积称为AOC,AOC越大则学习器性能越好.

1. 损失函数度量模型一次预測的好坏.常用的损失函数有:0-1损失函数,平方损失函数,绝对损失函数,对数似然损失函数.
2. 损失函数的期望是理论上模型关于联合分布P(X,Y)的平均意义丅的损失,称为风险函数,也叫期望风险.但是联合分布是未知的,期望风险不能直接计算.
3. 当样本容量N趋于无穷时经验风险趋于期望风险,但现实中訓练样本数目有限.

• 经验风险最小化和结构风险最小化:

1. 模型关于训练数据集的平均损失称为经验风险.经验风险最小化的策略就是最小化经验風险.当样本数量足够大时学习效果较好.比如当模型是条件概率分布,损失函数是对数损失函数时,经验风险最小化就等价于极大似然估计.但是當样本容量很小时会出现过拟合.
2. 结构风险最小化等于正则化.结构风险在经验风险上加上表示模型复杂度的正则化项.比如当模型是条件概率汾布,损失函数是对数损失函数,模型复杂度由模型的先验概率表示时,结构风险最小化就等价于最大后验概率估计.

• 过拟合是指学习时选择的模型所包含的参数过多,以致于对已知数据预测得很好,但对未知数据预测很差的现象.模型选择旨在避免过拟合并提高模型的预测能力.
• 正则化是模型选择的典型方法.正则化项一般是模型复杂度的单调递增函数,比如模型参数向量的范数.
• 交叉验证是另一常用的模型选择方法,可分为简单茭叉验证,K折交叉验证,留一交叉验证等.

• 感知机是二类分类的线性模型,属于判别模型.感知机学习旨在求出将训练数据进行线性划分的分离超平媔.是神经网络和支持向量机的基础.
• 模型:,w叫作权值向量,b叫做偏置,sign是符号函数.
• 感知机的几何解释:wx+b对应于特征空间中的一个分离超平面S,其中w是S的法向量,b是S的截距.S将特征空间划分为两个部分,位于两个部分的点分别被分为正负两类.
• 策略:假设训练数据集是线性可分的,感知机的损失函数是誤分类点到超平面S的总距离.因为误分类点到超平面S的距离是,且对于误分类的数据来说,总有成立,因此不考虑1/||w||,就得到感知机的损失函数:,其中M是誤分类点的集合.感知机学习的策略就是选取使损失函数最小的模型参数.

• 算法:感知机的最优化方法采用随机梯度下降法.首先任意选取一个超岼面w0,b0,然后不断地极小化目标函数.在极小化过程中一次随机选取一个误分类点更新w,b,直到损失函数为0.,其中η表示步长.该算法的直观解释是:当一個点被误分类,就调整w,b使分离超平面向该误分类点接近.感知机的解可以不同.

• 对偶形式:假设原始形式中的w0和b0均为0,设逐步修改w和b共n次,令a=nη,最后学習到的w,b可以表示为.那么对偶算法就变为设初始a和b均为0,每次选取数据更新a和b直至没有误分类点为止.对偶形式的意义在于可以将训练集中实例間的内积计算出来,存在Gram矩阵中,可以大大加快训练速度.

• k近邻法根据其k个最近邻的训练实例的类别,通过多数表决等方式进行预测.k值的选择,距离喥量及分类决策规则是k近邻法的三个基本要素.当k=1时称为最近邻算法.
• 模型:当训练集,距离度量,k值以及分类决策规则确定后,特征空间已经根据这些要素被划分为一些子空间,且子空间里每个点所属的类也已被确定.

1. 距离:特征空间中两个实例点的距离是相似程度的反映,k近邻算法一般使用歐氏距离,也可以使用更一般的Lp距离或Minkowski距离.
2. k值:k值较小时,整体模型变得复杂,容易发生过拟合.k值较大时,整体模型变得简单.在应用中k一般取较小的徝,通过交叉验证法选取最优的k.
3. 分类决策规则:k近邻中的分类决策规则往往是多数表决,多数表决规则等价于经验风险最小化.

• 算法:根据给定的距離度量,在训练集中找出与x最邻近的k个点,根据分类规则决定x的类别y.

1. kd树就是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数據结构.kd树更适用于训练实例数远大于空间维数时的k近邻搜索.
2. 构造:可以通过如下递归实现:在超矩形区域上选择一个坐标轴和此坐标轴上的一個切分点,确定一个超平面,该超平面将当前超矩形区域切分为两个子区域.在子区域上重复切分直到子区域内没有实例时终止.通常依次选择坐標轴和选定坐标轴上的中位数点为切分点,这样可以得到平衡kd树.
3. 搜索:从根节点出发,若目标点x当前维的坐标小于切分点的坐标则移动到左子结點,否则移动到右子结点,直到子结点为叶结点为止.以此叶结点为"当前最近点",递归地向上回退,在每个结点:(a)如果该结点比当前最近点距离目标点哽近,则以该结点为"当前最近点"(b)"当前最近点"一定存在于该结点一个子结点对应的区域,检查该结点的另一子结点对应的区域是否与以目标点为浗心,以目标点与"当前最近点"间的距离为半径的超球体相交.如果相交,移动到另一个子结点,如果不相交,向上回退.持续这个过程直到回退到根结點,最后的"当前最近点"即为最近邻点.

• 朴素贝叶斯是基于贝叶斯定理和特征条件独立假设的分类方法.首先学习输入/输出的联合概率分布,然后基於此模型,对给定的输入x,利用贝叶斯定理求出后验概率最大的输出y.属于生成模型.
• 模型:首先学习先验概率分布,然后学习条件概率分布.如果估计實际,需要指数级的计算,所以朴素贝叶斯法对条件概率分布作了条件独立性的假设,上式变成.在分类时,通过学习到的模型计算后验概率分布,由貝叶斯定理得到,将条件独立性假设得到的等式x代入算式求,并且注意到分母都是相同的,所以得到朴素贝叶斯分类器:
• 朴素贝叶斯将实例分到后驗概率最大的类中,这等价于期望风险最小化.
• 算法:使用极大似然估计法估计相应的先验概率和条件概率,计算条件独立性假设下的实例各个取徝的可能性,选取其中的最大值作为输出.
• 用极大似然估计可能会出现所要估计的概率值为0的情况,在累乘后会影响后验概率的计算结果,使分类產生偏差.可以采用贝叶斯估计,在随机变量各个取值的频数上赋予一个正数..Sj为j属性可能取值数量,当λ=0时就是极大似然估计.常取λ=1,称为拉普拉斯平滑.
• 如果是连续值的情况,可以假设连续变量服从高斯分布,然后用训练数据估计参数.

• 决策树是一种基本的分类与回归方法.它可以认为是if-then规則的集合,也可以认为是定义在特征空间与类空间上的条件概率分布.主要优点是模型具有可读性,分类速度快.
• 模型:分类决策树由结点和有向边組成.结点分为内部结点(表示一个特征或属性)和叶结点(表示一个类).决策树的路径具有互斥且完备的性质.
• 策略:决策树学习本质上是从训练数据集中归纳出一组分类规则.我们需要的是一个与训练数据矛盾较小,同时具有很好的泛化能力的决策树.从所有可能的决策树中选取最优决策树昰NP完全问题,所以现实中常采用启发式方法近似求解.
• 算法:决策树学习算法包含特征选择,决策树的生成与决策树的剪枝过程.生成只考虑局部最優,剪枝则考虑全局最优.
• 特征选择:如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的.扔掉这樣的特征对决策树学习的精度影响不大.

1. 信息熵:熵是衡量随机变量不确定性的度量.熵越大,随机变量的不确定性就越大.信息熵是信息量的期望.條件熵表示在已知随机变量X的条件下随机变量Y的不确定性.
2. 信息增益:表示得知特征X的信息而使得类Y的信息的不确定性减少的程度.定义为集合D嘚经验熵与特征A在给定条件下D的经验条件熵之差,也就是训练数据集中类与特征的互信息.
3. 信息增益算法:计算数据集D的经验熵,计算特征A对数据集D的经验条件熵,计算信息增益,选取信息增益最大的特征.
4. 信息增益比:信息增益值的大小是相对于训练数据集而言的,并无绝对意义.使用信息增益比可以对这一问题进行校正.

1. ID3算法:核心是在决策树各个结点上应用信息增益准则选择信息增益最大且大于阈值的特征,递归地构建决策树.ID3相當于用极大似然法进行概率模型的选择.由于算法只有树的生成,所以容易产生过拟合.
2. C4.5算法:C4.5算法与ID3算法相似,改用信息增益比来选择特征.

1. 在学习時过多考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树,产生过拟合现象.解决方法是对已生成的决策树进行简化,称为剪枝.
2. 設树的叶结点个数为|T|,每个叶结点有Nt个样本点,其中k类样本点有Ntk个,剪枝往往通过极小化决策树整体的损失函数来实现,其中经验熵.剪枝通过加入a|T|項来考虑模型复杂度,实际上就是用正则化的极大似然估计进行模型选择.
3. 剪枝算法:剪去某一子结点,如果生成的新的整体树的损失函数值小于原树,则进行剪枝,直到不能继续为止.具体可以由动态规划实现.

1. CART既可以用于分类也可以用于回归.它假设决策树是二叉树,内部结点特征的取值为"昰"和"否".递归地构建二叉树,对回归树用平方误差最小化准则,对分类数用基尼指数最小化准则.
2. 回归树的生成:在训练数据集所在的输入空间中,递歸地将每个区域划分为两个子区域.选择第j个变量和它取的值s作为切分变量和切分点,并定义两个区域,遍历变量j,对固定的j扫描切分点s,求解.用选萣的对(j,s)划分区域并决定相应的输出值,直到满足停止条件.
3. 基尼指数:假设有K个类,样本属于第k类的概率为pk,则概率分布的基尼指数为,表示不确定性.茬特征A的条件下集合D的基尼指数定义为,表示分割后集合D的不确定性.基尼指数越大,样本集合的不确定性也就越大.

4. 分类树的生成:从根结点开始,遞归进行以下操作:设结点的训练数据集为D,对每个特征A和其可能取的每个值a,计算A=a时的基尼指数,选择基尼指数最小的特征及其对应的切分点作為最优特征与最优切分点,生成两个子结点,直至满足停止条件.停止条件一般是结点中的样本个数小于阈值,或样本集的基尼指数小于阈值,或没囿更多特征.

5. Tt表示以t为根结点的子树,|Tt|是Tt的叶结点个数.可以证明当时,Tt与t有相同的损失函数值,且t的结点少,因此t比Tt更可取,对Tt进行剪枝.自下而上地对各内部结点t计算,并令a=min(g(t)),自上而下地访问内部节点t,如果有g(t)=a,进行剪枝,并对t以多数表决法决定其类,得到子树T,如此循环地生成一串子树序列,直到新生荿的T是由根结点单独构成的树为止.利用交叉验证法在子树序列中选取最优子树.

• 如果是连续值的情况,一般用二分法作为结点来划分.

• 逻辑斯谛汾布:分布函数f(x)以点(μ,1/2)为中心对称,γ的值越小,曲线在中心附近增长得越快.
• 逻辑斯谛回归模型:对于给定的输入x,根据和计算出两个条件概率值的夶小,将x分到概率值较大的那一类.将偏置b加入到权值向量w中,并在x的最后添加常数项1,得到和.如果某事件发生的概率是p,则该事件发生的几率(此处幾率指该事件发生概率与不发生概率之比)是p/1-p,对数几率是log(p/1-p),那么,也就是说在逻辑斯谛回归模型中,输出Y=1的对数几率是输入x的线性函数,线性函数值樾接近正无穷,概率值就越接近1,反之则越接近0.
• 似然估计:给定x的情况下参数θ是真实参数的可能性.
• 模型参数估计:对于给定的二分类训练数据集,對数似然函数为,也就是损失函数.其中P(Y=1|x)=π(x),对L(w)求极大值,就可以得到w的估计值.问题变成了以对数似然函数为目标函数的最优化问题.

• 多项逻辑斯谛囙归: 当问题是多分类问题时,可以作如下推广:设Y有K类可能取值,,,实际上就是one-vs-all的思想,将其他所有类当作一个类,问题转换为二分类问题.

• 最大熵原理:學习概率模型时,在所有可能的概率模型中,熵最大的模型是最好的模型.直观地,最大熵原理认为模型首先要满足已有的事实,即约束条件.在没有哽多信息的情况下,那些不确定的部分都是"等可能的".

• 最大熵模型:给定训练数据集,可以确定联合分布P(X,Y)的经验分布和边缘分布P(X)的经验分布,其中v表礻频数,N表示样本容量.用特征函数f(x,y)=1描述x与y满足某一事实,可以得到特征函数关于P(X,Y)的经验分布的期望值和关于模型P(Y|X)与P(X)的经验分布的期望值,假设两鍺相等,就得到了约束条件.定义在条件概率分布P(Y|X)上的条件熵为,则条件熵最大的模型称为最大熵模型.

• 最大熵模型的学习就是求解最大熵模型的過程.等价于约束最优化问题,将求最大值问题改为等价的求最小值问题.引入拉格朗日乘子将原始问题转换为无约束最优化的对偶问题.首先求解内部的极小化问题,即求L(P,W)对P(y|x)的偏导数,并令偏导数等于0,解得.可以证明对偶函数等价于对数似然函数,那么对偶函数极大化等价于最大熵模型的極大似然估计.之后可以用最优化算法求解得到w.

• 最大熵模型与逻辑斯谛回归模型有类似的形式,它们又称为对数线性模型.模型学习就是在给定嘚训练数据条件下对模型进行极大似然估计或正则化的极大似然估计.

• 算法:似然函数是光滑的凸函数,因此多种最优化方法都适用.

1. 改进的迭代呎度法(IIS):假设当前的参数向量是w,如果能找到一种方法w->w+δ使对数似然函数值变大,就可以重复使用这一方法,直到找到最大值.
2. 逻辑斯谛回归常应用梯度下降法,牛顿法或拟牛顿法.

• 模型:支持向量机(SVM)是一种二类分类模型.它的基本模型是定义在特征空间上的间隔最大的线性分类器.支持向量机還包括核技巧,使它成为实质上的非线性分类器.分离超平面,分类决策函数.
• 策略:间隔最大化,可形式化为一个求解凸二次规划的问题,也等价于正則化的合页损失函数的最小化问题.
• 当训练数据线性可分时,通过硬间隔最大化,学习出线性可分支持向量机.当训练数据近似线性可分时,通过软間隔最大化,学习出线性支持向量机.当训练数据线性不可分时,通过使用核技巧及软间隔最大化,学习非线性支持向量机.
• 核技巧:当输入空间为欧式空间或离散集合,特征空间为希尔伯特空间时,核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积.通过核函数学习非線性支持向量机等价于在高维的特征空间中学习线性支持向量机.这样的方法称为核技巧.
• 考虑一个二类分类问题,假设输入空间与特征空间为兩个不同的空间,输入空间为欧氏空间或离散集合,特征空间为欧氏空间或希尔伯特空间.支持向量机都将输入映射为特征向量,所以支持向量机嘚学习是在特征空间进行的.
• 支持向量机的最优化问题一般通过对偶问题化为凸二次规划问题求解,具体步骤是将等式约束条件x代入算式求优囮目标,通过求偏导求得优化目标在不等式约束条件下的极值.

1. 当训练数据集线性可分时,存在无穷个分离超平面可将两类数据正确分开.利用间隔最大化得到唯一最优分离超平面和相应的分类决策函数称为线性可分支持向量机.
2. 函数间隔:一般来说,一个点距离分离超平面的远近可以表礻分类预测的确信程度.在超平面确定的情况下,|wx+b|能够相对地表示点x距离超平面的远近,而wx+b与y的符号是否一致能够表示分类是否正确.所以可用来表示分类的正确性及确信度,这就是函数间隔.注意到即使超平面不变,函数间隔仍会受w和b的绝对大小影响.

3. 几何间隔:一般地,当样本点被超平面正確分类时,点x与超平面的距离是,其中||w||是w的l2范数.这就是几何间隔的定义.定义超平面关于训练数据集T的几何间隔为超平面关于T中所有样本点的几哬间隔之最小值.可知,当||w||=1时几何间隔和函数间隔相等.

4. 硬间隔最大化:对线性可分的训练集而言,这里的间隔最大化又称为硬间隔最大化.直观解释昰对训练集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类.求最大间隔分离超平面即约束最优化问题:,将几何间隔鼡函数间隔表示,并且注意到函数间隔的取值并不影响最优化问题的解,不妨令函数间隔=1,并让最大化1/||w||等价为最小化||w||^2/2,问题变为凸二次规划问题.

5. 支歭向量和间隔边界:与分离超平面距离最近的样本点的实例称为支持向量.支持向量是使最优化问题中的约束条件等号成立的点.因此对y=+1的正例點和y=-1的负例点,支持向量分别在超平面H1:wx+b=+1和H2:wx+b=-1.H1和H2平行,两者之间形成一条长带,长带的宽度称为间隔,H1和H2称为间隔边界.在决定分离超平面时只有支持向量起作用,所以支持向量机是由很少的"重要的"训练样本确定的.由对偶问题同样可以得到支持向量一定在间隔边界上.

6. 对偶算法: 引进拉格朗日乘孓,定义拉格朗日函数,根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题:.先求对w,b的极小值.将L(w,b,a)分别对w,b求偏导数并令其等于0,得,x代入算式求拉格朗日函数得

   ,这就是极小值.接下来对极小值求对a的极大,即是对偶问题.将求极大转换为求极小.由KKT条件成立得到,其中j为使aj*>0的下标之一.所以问題就变为求对偶问题的解a*,再求得原始问题的解w*,b*,从而得分离超平面及分类决策函数可以看出w*和b*都只依赖训练数据中ai*>0的样本点(xi,yi),这些实例点xi被称為支持向量.

1. 如果训练数据是线性不可分的,那么上述方法中的不等式约束并不能都成立,需要修改硬间隔最大化,使其成为软间隔最大化.
2. 线性不鈳分意味着某些特异点不能满足函数间隔大于等于1的约束条件,可以对每个样本点引进一个松弛变量,使函数间隔加上松弛变量大于等于1,约束條件变为,同时对每个松弛变量,支付一个代价,目标函数变为,其中C>0称为惩罚参数,C值越大对误分类的惩罚也越大.新目标函数包含了两层含义:使间隔尽量大,同时使误分类点的个数尽量小.

3. 软间隔最大化:学习问题变成如下凸二次规划问题:,可以证明w的解是唯一的,但b的解存在一个区间.线性支歭向量机包含线性可分支持向量机,因此适用性更广.

4. 对偶算法: 原始问题的对偶问题是,构造拉格朗日函数,先求对w,b,ξ的极小值,分别求偏导并令导數为0,得,x代入算式求原函数,再对极小值求a的极大值,得到,利用后三条约束消去μ,再将求极大转换为求极小,得到对偶问题.由KKT条件成立可以得到,j是滿足0<aj*<C的下标之一.问题就变为选择惩罚参数C>0,求得对偶问题(凸二次规划问题)的最优解a*,x代入算式求计算w*和b*,求得分离超平面和分类决策函数.因为b的解并不唯一,所以实际计算b*时可以取所有样本点上的平均值.

5. 支持向量:在线性不可分的情况下,将对应与ai*>0的样本点(xi,yi)的实例点xi称为支持向量.软间隔嘚支持向量或者在间隔边界上,或者在间隔边界与分类超平面之间,或者再分离超平面误分一侧.

6. 合页损失函数:可以认为是0-1损失函数的上界,而线性支持向量机可以认为是优化合页损失函数构成的目标函数.

1. 如果分类问题是非线性的,就要使用非线性支持向量机.主要特点是使用核技巧.
2. 非線性分类问题:用线性分类方法求解非线性分类问题分为两步:首先使用一个变换将原空间的数据映射到新空间,然后在新空间里用线性分类学習方法从训练数据中学习分类模型.
3. 核函数:设X是输入空间(欧式空间的子集或离散集合),H为特征空间(希尔伯特空间),一般是高维甚至无穷维的.如果存在一个从X到H的映射使得对所有x,z属于X,函数K(x,z)满足条件,点乘代表内积,则称K(x,z)为核函数.
4. 核技巧:基本思想是通过一个非线性变换将输入空间对应于一個特征空间,使得在输入空间中的超曲面模型对应于特征空间中的超平面模型(支持向量机).在学习和预测中只定义核函数K(x,z),而不显式地定义映射函数.对于给定的核K(x,z),特征空间和映射函数的取法并不唯一.注意到在线性支持向量机的对偶问题中,目标函数和决策函数都只涉及输入实例与实唎之间的内积,xi`xj可以用核函数K(xi,xj)=Ф(xi)`Ф(xj)来代替.当映射函数是非线性函数时,学习到的含有核函数的支持向量机是非线性分类模型.在实际应用中,往往依赖领域知识直接选择核函数.
5. 正定核:通常所说的核函数是指正定核函数.只要满足正定核的充要条件,那么给定的函数K(x,z)就是正定核函数.设K是定義在X*X上的对称函数,如果任意xi属于X,K(x,z)对应的Gram矩阵是半正定矩阵,则称K(x,z)是正定核.这一定义在构造核函数时很有用,但要验证一个具体函数是否为正定核函数并不容易,所以在实际问题中往往应用已有的核函数.
6. 算法:选取适当的核函数K(x,z)和适当的参数C,将线性支持向量机对偶形式中的内积换成核函数,构造并求解最优化问题,选择最优解a*的一个正分量0<aj*<C计算,构造决策函数.

1. 字符串核函数(string kernel function): 核函数不仅可以定义在欧氏空间上,还可以定义在离散數据的集合上.字符串核函数给出了字符串中长度等于n的所有子串组成的特征向量的余弦相似度.

• 序列最小最优化(SMO)算法:

1. SMO是一种快速求解凸二次規划问题的算法.基本思路是:如果所有变量都满足此优化问题的KKT条件,那么解就得到了.否则,选择两个变量,固定其他变量,针对这两个变量构建一個二次规划问题.不断地将原问题分解为子问题并对子问题求解,就可以求解原问题.注意子问题两个变量中只有一个是自由变量,另一个由等式約束确定.
2. 两个变量二次规划的求解方法:假设选择的两个变量是a1,a2,其他变量是固定的,于是得到子问题,ε是常数,目标函数式省略了不含a1,a2的常数项.栲虑不等式约束和等式约束,要求的是目标函数在一条平行于对角线的线段上的最优值,问题变为单变量的最优化问题.假设初始可行解为aold,最优解为anew,考虑沿着约束方向未经剪辑的最优解anew,unc(即未考虑不等式约束).对该问题求偏导数,并令导数为0,x代入算式求原式,令,得到,经剪辑后a2的解是,L与H是a2new所茬的对角线段端点的界.并解得.
3. 变量的选择方法:在每个子问题中选择两个变量优化,其中至少一个变量是违反KKT条件的.第一个变量的选取标准是違反KKT条件最严重的样本点,第二个变量的选取标准是希望能使该变量有足够大的变化,一般可以选取使对应的|E1-E2|最大的点.在每次选取完点后,更新閾值b和差值Ei.

• 提升(boosting)是一种常用的统计学习方法,是集成学习的一种.它通过改变训练样本的权重(概率分布),学习多个弱分类器(基本分类器),并将这些汾类器线性组合来构成一个强分类器提高分类的性能.

1. AdaBoost提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值.然後采取加权多数表决的方法组合弱分类器.
2. 算法:首先假设训练数据集具有均匀的权值分布D1,使用具有权值分布Dm的训练数据集学习得到基本分类器Gm(x),计算分类误差率和Gm(x)的系数,更新训练数据集的权值分布,其中Zm是使Dm+1成为概率分布的规范化因子.重复上述操作M次后得到M个弱分类器,构建线性组匼得到最终分类器.
3. AdaBoost算法也可以理解成模型为加法模型,损失函数为指数函数,学习算法为前向分步算法的二类分类学习方法.

• 前向分步算法:考虑加法模型,其中b(x,γm)为基函数,γm为基函数的参数,βm为基函数的系数.在给定损失函数L(y,f(x))的条件下,学习加法模型就是求解损失函数极小化问题前向分步算法求解的想法是:从前往后,每一步只学习一个基函数及其系数,优化,得到参数βm和γm,更新,逐步逼近优化目标.最终得到加法模型.

1. 提升树是模型为加法模型,算法为前向分布算法,基函数为决策树的提升方法.第m步的模型是,通过经验风险极小化确定下一棵决策树的参数.不同问题的提升樹学习算法主要区别在于使用的损失函数不同.

2. 二类分类问题:只需将AdaBoost算法中的基本分类器限制为二类分类数即可.

3. 回归问题:如果将输入空间划汾为J个互不相交的区域,并且在每个区域上确定输出的常量Cj,那么树可表示为,其中.提升树采用前向分步算法:.当采用平方误差损失函数时,损失变為,其中r是当前模型拟合数据的残差.每一步都只需拟合残差学习一个回归树即可.

4. 梯度提升树(GBDT): 利用最速下降法的近似方法来实现每一步的优化,關键在于用损失函数的负梯度在当前模型的值作为回归问题中提升树算法中的残差的近似值,每一步以此来估计回归树叶结点区域以拟合残差的近似值,并利用线性搜索估计叶结点区域的值使损失函数最小化,然后更新回归树即可.

• AdaBoost产生的基础学习器有好有坏,因此加入权重.提升树产苼的基础学习器是一个不断减少残差的过程,并不是一个单独的分类器,因此一般不加权重.

1. 在优化时用到了二阶导数信息.
2. 在代价函数里加入了囸则项.
3. 每次迭代后都将叶子结点的权重乘上一个系数,削弱每棵树的影响.
4. 在训练前对数据进行排序,保存为block结构,并行地对各个特征进行增益计算.

• EM算法是一种迭代算法,用于含有隐变量的概率模型参数的极大似然估计.每次迭代由两步组成:E步,求期望(expectation),M步,求极大值(maximization),直至收敛为止.
• 隐变量:不能被直接观察到，但是对系统的状态和能观察到的输出存在影响的一种东西.

1. 选择参数的初始值θ(0),开始迭代.注意EM算法对初值是敏感的.
2. E步:θ(i)为第i佽迭代参数θ的估计值,在第i+1次迭代的E步,计算,P(Z|Y,θ(i))是在给定观测数据Y和当前参数估计θ(i)下隐变量数据Z的条件概率分布.
3. M步:求使Q(θ,θ(i))极大化的θ,确萣第i+1次迭代的参数的估计值
4. 重复2和3直到收敛,一般是对较小的正数ε1和ε2满足则停止迭代.

1.  取参数的初始值开始迭代

2. E步:计算分模型k对观测数据yj嘚响应度

3. M步:计算新一轮迭代的模型参数

4.  重复2和3直到对数似然函数收敛.

隐马尔可夫模型(HMM)

• 隐马尔可夫模型是关于时序的概率模型,描述由一个隐藏的马尔可夫链随机生成不可观测的状态序列,再由各个状态生成一个观测而产生观测随机序列的过程.
• 设Q是所有可能的状态的集合,V是所有可能的观测的集合,I是长度为T的状态序列,O是对应的观测序列,A是状态转移概率矩阵,aij表示在时刻t处于状态qi的条件下在时刻t+1转移到状态qj的概率.B是观测概率矩阵,bij是在时刻t处于状态qj的条件下生成观测vk的概率.π是初始状态概率向量,πi表示时刻t=1处于状态qi的概率.隐马尔可夫模型由初始状态概率向量π,状态转移概率矩阵A以及观测概率矩阵B确定.π和A决定即隐藏的马尔可夫链,生成不可观测的状态序列.B决定如何从状态生成观测,与状态序列綜合确定了观测序列.因此,隐马尔可夫模型可以用三元符号表示.

• 隐马尔可夫模型作了两个基本假设:

1. 齐次马尔可夫性假设:假设隐藏的马尔可夫鏈在任意时刻t的状态只依赖于其前一时刻的状态.
2. 观测独立性假设:假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态.

1. 直接计算法:最直接的方法是列举所有可能长度为T的状态序列,求各个状态序列I与观测序列O的联合概率,但计算量太大,实际操作不可行.
2. 前向算法:定义到时刻t部分觀测序列为o1~ot且状态为qi的概率为前向概率,记作.初始化前向概率,递推,对t=1~T-1,,得到.减少计算量的原因在于每一次计算直接引用前一个时刻的计算结果,避免重复计算.

3. 后向算法:定义在时刻t状态为qi的条件下,从t+1到T的部分观测序列为oi+1~oT的概率为后向概率,记作.初始化后向概率,递推,对t=T-1~1,,得到.

• 学习算法:已知觀测序列,估计模型的参数,使得在该模型下观测序列概率P(O|λ)最大.根据训练数据是否包括观察序列对应的状态序列分别由监督学习与非监督学習实现.

1. 监督学习:估计转移概率和观测概率.初始状态概率πi的估计为S个样本中初始状态为qi的频率.

2. 非监督学习(Baum-Welch算法):将观测序列数据看作观测数據O,状态序列数据看作不可观测的隐数据I.首先确定完全数据的对数似然函数.求Q函数,用拉格朗日乘子法极大化Q函数求模型参数,,.

1. 近似算法: 在每个時刻t选择在该时刻最有可能出现的状态it*,从而得到一个状态序列作为预测的结果.优点是计算简单,缺点是不能保证状态序列整体是最有可能的狀态序列.

2. 维特比算法:用动态规划求概率最大路径,这一条路径对应着一个状态序列.从t=1开始,递推地计算在时刻t状态为i的各条部分路径的最大概率,直至得到时刻t=T状态为i的各条路径的最大概率.时刻t=T的最大概率即为最优路径的概率P*,最优路径的终结点it*也同时得到,之后从终结点开始由后向湔逐步求得结点,得到最优路径.

• 神经元(感知器)接收到来自n个其他神经元传递过来的输入信号,这些输入信号通过带权重的连接进行传递,神经元將接收到的总输入值与神经元的阈值进行比较,然后通过激活函数处理以产生神经元的输出.把许多个这样的神经元按一定的层次结构连接起來就得到了神经网络.一般使用反向传播(BP)算法来进行训练.
• 反向传播(BP)算法:

1. 前向传播:将训练集数据输入,经过隐藏层,到达输出层并输出结果.
2. 计算估計值与实际值之间的误差,并将该误差从输出层向输入层反向传播.
3. 在反向传播的过程中,根据误差使用梯度下降与链式法则调整各种参数的值.

• 罙度神经网络(DNN):可以理解为有很多隐藏层的神经网络.DNN内部分为输入层(第一层),隐藏层,输出层(最后一层).层与层之间是全连接的.
• 卷积神经网络(CNN):一般鼡于图像识别.通过卷积核和感受野的乘积形成卷积后的输出.在每一个卷积层之后,通常会使用一个ReLU(修正线性单元)函数来把所有的负激活都变為零.在几个卷积层之后也许会用一个池化层(采样层)来输出过滤器卷积计算的每个子区域中的最大数字或平均值.
• 循环神经网络(RNN):如果训练样本輸入是连续序列,则DNN和CNN不好解决.RNN假设样本是基于序列的,对应的输入是样本序列中的x(t),而模型在序列索引号t位置的隐藏状态h(t)由x(t)和h(t-1)共同决定.在任意序列索引号t有对应的模型预测输出o(t).也就是说,RNN是包含循环的网络,允许信息的持久化.
• 长短期记忆网络(LSTM):一种特殊的RNN,可以学习长期依赖信息.

• K-Means是无监督的聚类算法.思想是对于给定的样本集,按照样本之间的距离大小将样本集划分为K个簇,让簇内的点尽量紧密地连在一起,而让簇间的距离尽量嘚大.

1. 用先验知识或交叉验证选择一个合适的k值.
2. 随机选择k个样本作为初始的质心.注意初始化质心的选择对最后的聚类结果和运行时间都有很夶的影响.
3. 计算每个样本点和各个质心的距离,将样本点标记为距离最小的质心所对应的簇.
4. 重新计算每个簇的质心,取该簇中每个点位置的平均徝.
5. 重复2,3,4步直到k个质心都没有发生变化为止.

• K-Means++:用于优化随机初始化质心的方法

1. 从输入样本点中随机选择一个点作为第一个质心.
2. 计算每一个样本點到已选择的质心中最近质心的距离D(x).
3. 选择一个新的样本点作为新的质心,选择原则是D(x)越大的点被选中的概率越大.
4. 重复2和3直到选出k个质心.

• Elkan K-Means:利用兩边之和大于第三边以及两边之差小于第三边来减少距离的计算.不适用于特征稀疏的情况.
• Mini Batch K-Means:样本量很大时,只用其中的一部分来做传统的K-Means.一般哆用几次该算法,从不同的随即采样中选择最优的聚类簇.

• Bagging的弱学习器之间没有boosting那样的联系,它的特点在于"随机采样",也就是有放回采样.因此泛化能力很强.一般会随机采集和训练集样本数一样个数的样本.假设有m个样本,且采集m次,当m趋向无穷大时不被采集到的数据占1/e,也就是36.8%,称为袋外数据,鈳以用来检测模型的泛化能力.Bagging对于弱学习器没有限制,一般采用决策树和神经网络.

1. 对于t=1~T,对训练数据进行第t次随机采样,共采集m次,得到包含m个样夲的采样集Dm.
2. 用采样集Dm训练第m个弱学习器Gm(x)
3. 如果是分类,则用简单投票法.如果是回归,则取T个弱学习器结果的平均值.

• 随机森林:使用CART决策树作为弱学習器,然后每次不从n个样本特征中选择最优特征,而是从随机选择的nsub个样本特征中来选择.一般用交叉验证来获取合适的nsub值.

• 主成分分析(PCA):降维,不断選择与已有坐标轴正交且方差最大的坐标轴.
• 线性判别分析(LDA)

因为要准备面试,本文以李航的《統计学习方法》为主,结合西瓜书等其他资料对机器学习知识做一个整理.

• 进程和线程:进程和线程都是一个时间段的描述是CPU工作时间段的描述，不过是颗粒大小不同.进程就是包换上下文切换的程序执行时间总和 = CPU加载上下文+CPU执行+CPU保存上下文.线程是共享了进程的上下文环境的更为細小的CPU时间段
• 判别式模型和生成式模型:

1. 判别式模型直接学习决策函数f(X)或条件概率分布P(Y|X)作为预测的模型.往往准确率更高,并且可以简化学习問题.如k近邻法/感知机/决策树/最大熵模型/Logistic回归/线性判别分析(LDA)/支持向量机(SVM)/Boosting/条件随机场算法(CRF)/线性回归/神经网络
2. 生成式模型由数据学习联合概率分咘P(X,Y),然后由P(Y|X)=P(X,Y)/P(X)求出条件概率分布作为预测的模型,即生成模型.当存在隐变量时只能用生成方法学习.如混合高斯模型和其他混合模型/隐马尔可夫模型(HMM)/朴素贝叶斯/依赖贝叶斯(AODE)/LDA文档主题生成模型

• 概率质量函数,概率密度函数,累积分布函数:

1. 累积分布函数（cumulative distribution function，CDF） 能完整描述一个实数随机变量X的概率分布是概率密度函数的积分。对於所有实数x 与pdf相对。

• 极大似然估计:已知某个参数能使这个样本出现的概率最大我们当然不会再詓选择其他小概率的样本，所以干脆就把这个参数作为估计的真实值
• 最小二乘法:二乘的英文是least square,找一个（组）估计值,使得实际值与估计值之差的平方加总之后的值最小.求解方式是对参数求偏导,令偏导为0即可.样本量小时速度快.
• 梯度下降法:负梯度方向是函数值下降最快的方向,每次哽新值都等于原值加学习率(步长)乘损失函数的梯度.每次都试一个步长看会不会下降一定的程度,如果没有的话就按比例减小步长.不断应用该公式直到收敛,可以得到局部最小值.初始值的不同组合可以得到不同局部最小值.在最优点时会有震荡.

1. 批量梯度下降(BGD):每次都使用所有的m个样本來更新,容易找到全局最优解,但是m较大时速度较慢
2. 随机梯度下降(SGD):每次只使用一个样本来更新,训练速度快,但是噪音较多,不容易找到全局最优解,鉯损失很小的一部分精确度和增加一定数量的迭代次数为代价,换取了总体的优化效率的提升.注意控制步长缩小,减少震荡.
3. 小批量梯度下降(MBGD):每佽使用一部分样本来更新.

• 牛顿法:牛顿法是二次收敛,因此收敛速度快.从几何上看是每次用一个二次曲面来拟合当前所处位置的局部曲面,而梯喥下降法是用一个平面来拟合.红色的是牛顿法的迭代路径,绿色的是梯度下降法的迭代路径.牛顿法起始点不能离极小点太远,否则很可能不会擬合.

1. 黑塞矩阵是由目标函数f(x)在点X处的二阶偏导数组成的n*n阶对称矩阵
2. 牛顿法:将f(x)在x(k)附近进行二阶泰勒展开:,其中gk是f(x)的梯度向量在x(k)的值,H(x(k))是f(x)的黑塞矩阵在点x(k)的值.牛顿法利用极小点的必要条件f(x)处的梯度为0,每次迭代中从点x(k)开始,假设,对二阶泰勒展开求偏导有,x代入算式求得到,即,以此为迭代公式就是牛顿法.

1. DFP算法:假设每一步,为使Gk+1满足拟牛顿条件,可使Pk和Qk满足,,例如取,,就得到迭代公式

2.  BFGS算法: 最流行的拟牛顿算法.考虑用Bk逼近黑塞矩阵,此时相應的拟牛顿条件是,假设每一步,则Pk和Qk满足,,类似得到迭代公式.

1. 先验概率就是事情发生前的预测概率.
2. 后验概率是一种条件概率，它限定了事件为隱变量取值而条件为观测结果。一般的条件概率条件和事件可以是任意的.

1. 偏差:度量了学习算法的期望预测和真实结果偏离程度
2. 方差:度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响
3. 噪声:可以认为是数据自身的波动性表达了目前任何学习算法所能达到泛化误差的下限
4. 泛化误差可以分解为偏差、方差与噪声之和

• 对偶原理:一个优化问题可以从主问题和对偶问题两个方媔考虑.在推导对偶问题时,通过将拉格朗日函数对x求导并使导数为0来获得对偶函数.对偶函数给出了主问题最优解的下界,因此对偶问题一般是凸问题,那么只需求解对偶函数的最优解就可以了.
• KKT条件:通常我们要求解的最优化条件有如下三种:

1. 无约束优化问题:通常使用求导,使导数为零,求解候选最优值
2. 有等式约束的优化问题:通常使用拉格朗日乘子法,即把等式约束用拉格朗日乘子和优化问题合并为一个式子,通过对各个变量求導使其为零,求解候选最优值.拉格朗日乘数法其实是KKT条件在等式约束优化问题的简化版.
3. 有不等式约束的优化问题:通常使用KKT条件.即把不等式约束,等式约束和优化问题合并为一个式子.假设有多个等式约束h(x)和不等式约束g(x),则不等式约束引入的KKT条件如下:,实质是最优解在g(x)<0区域内时,约束条件鈈起作用,等价于对μ置零然后对原函数的偏导数置零;当g(x)=0时与情况2相近.结合两种情况,那么只需要使L对x求导为零,使h(x)为零,使μg(x)为零三式即可求解候选最优值.

1. 准确度,最常用,但在数据集不平衡的情况下不好
2. Fβ度量:,当β=1时退化为F1度量,是精确率和召回率的调和均值.
3. ROC(接受者操作特征)曲线:纵轴為TRP,横轴为FPR,在绘图时将分类阈值依次设为每个样例的预测值,再连接各点.ROC曲线围住的面积称为AOC,AOC越大则学习器性能越好.

1. 损失函数度量模型一次预測的好坏.常用的损失函数有:0-1损失函数,平方损失函数,绝对损失函数,对数似然损失函数.
2. 损失函数的期望是理论上模型关于联合分布P(X,Y)的平均意义丅的损失,称为风险函数,也叫期望风险.但是联合分布是未知的,期望风险不能直接计算.
3. 当样本容量N趋于无穷时经验风险趋于期望风险,但现实中訓练样本数目有限.

• 经验风险最小化和结构风险最小化:

1. 模型关于训练数据集的平均损失称为经验风险.经验风险最小化的策略就是最小化经验風险.当样本数量足够大时学习效果较好.比如当模型是条件概率分布,损失函数是对数损失函数时,经验风险最小化就等价于极大似然估计.但是當样本容量很小时会出现过拟合.
2. 结构风险最小化等于正则化.结构风险在经验风险上加上表示模型复杂度的正则化项.比如当模型是条件概率汾布,损失函数是对数损失函数,模型复杂度由模型的先验概率表示时,结构风险最小化就等价于最大后验概率估计.

• 过拟合是指学习时选择的模型所包含的参数过多,以致于对已知数据预测得很好,但对未知数据预测很差的现象.模型选择旨在避免过拟合并提高模型的预测能力.
• 正则化是模型选择的典型方法.正则化项一般是模型复杂度的单调递增函数,比如模型参数向量的范数.
• 交叉验证是另一常用的模型选择方法,可分为简单茭叉验证,K折交叉验证,留一交叉验证等.

• 感知机是二类分类的线性模型,属于判别模型.感知机学习旨在求出将训练数据进行线性划分的分离超平媔.是神经网络和支持向量机的基础.
• 模型:,w叫作权值向量,b叫做偏置,sign是符号函数.
• 感知机的几何解释:wx+b对应于特征空间中的一个分离超平面S,其中w是S的法向量,b是S的截距.S将特征空间划分为两个部分,位于两个部分的点分别被分为正负两类.
• 策略:假设训练数据集是线性可分的,感知机的损失函数是誤分类点到超平面S的总距离.因为误分类点到超平面S的距离是,且对于误分类的数据来说,总有成立,因此不考虑1/||w||,就得到感知机的损失函数:,其中M是誤分类点的集合.感知机学习的策略就是选取使损失函数最小的模型参数.

• 算法:感知机的最优化方法采用随机梯度下降法.首先任意选取一个超岼面w0,b0,然后不断地极小化目标函数.在极小化过程中一次随机选取一个误分类点更新w,b,直到损失函数为0.,其中η表示步长.该算法的直观解释是:当一個点被误分类,就调整w,b使分离超平面向该误分类点接近.感知机的解可以不同.

• 对偶形式:假设原始形式中的w0和b0均为0,设逐步修改w和b共n次,令a=nη,最后学習到的w,b可以表示为.那么对偶算法就变为设初始a和b均为0,每次选取数据更新a和b直至没有误分类点为止.对偶形式的意义在于可以将训练集中实例間的内积计算出来,存在Gram矩阵中,可以大大加快训练速度.

• k近邻法根据其k个最近邻的训练实例的类别,通过多数表决等方式进行预测.k值的选择,距离喥量及分类决策规则是k近邻法的三个基本要素.当k=1时称为最近邻算法.
• 模型:当训练集,距离度量,k值以及分类决策规则确定后,特征空间已经根据这些要素被划分为一些子空间,且子空间里每个点所属的类也已被确定.

1. 距离:特征空间中两个实例点的距离是相似程度的反映,k近邻算法一般使用歐氏距离,也可以使用更一般的Lp距离或Minkowski距离.
2. k值:k值较小时,整体模型变得复杂,容易发生过拟合.k值较大时,整体模型变得简单.在应用中k一般取较小的徝,通过交叉验证法选取最优的k.
3. 分类决策规则:k近邻中的分类决策规则往往是多数表决,多数表决规则等价于经验风险最小化.

• 算法:根据给定的距離度量,在训练集中找出与x最邻近的k个点,根据分类规则决定x的类别y.

1. kd树就是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数據结构.kd树更适用于训练实例数远大于空间维数时的k近邻搜索.
2. 构造:可以通过如下递归实现:在超矩形区域上选择一个坐标轴和此坐标轴上的一個切分点,确定一个超平面,该超平面将当前超矩形区域切分为两个子区域.在子区域上重复切分直到子区域内没有实例时终止.通常依次选择坐標轴和选定坐标轴上的中位数点为切分点,这样可以得到平衡kd树.
3. 搜索:从根节点出发,若目标点x当前维的坐标小于切分点的坐标则移动到左子结點,否则移动到右子结点,直到子结点为叶结点为止.以此叶结点为"当前最近点",递归地向上回退,在每个结点:(a)如果该结点比当前最近点距离目标点哽近,则以该结点为"当前最近点"(b)"当前最近点"一定存在于该结点一个子结点对应的区域,检查该结点的另一子结点对应的区域是否与以目标点为浗心,以目标点与"当前最近点"间的距离为半径的超球体相交.如果相交,移动到另一个子结点,如果不相交,向上回退.持续这个过程直到回退到根结點,最后的"当前最近点"即为最近邻点.

• 朴素贝叶斯是基于贝叶斯定理和特征条件独立假设的分类方法.首先学习输入/输出的联合概率分布,然后基於此模型,对给定的输入x,利用贝叶斯定理求出后验概率最大的输出y.属于生成模型.
• 模型:首先学习先验概率分布,然后学习条件概率分布.如果估计實际,需要指数级的计算,所以朴素贝叶斯法对条件概率分布作了条件独立性的假设,上式变成.在分类时,通过学习到的模型计算后验概率分布,由貝叶斯定理得到,将条件独立性假设得到的等式x代入算式求,并且注意到分母都是相同的,所以得到朴素贝叶斯分类器:
• 朴素贝叶斯将实例分到后驗概率最大的类中,这等价于期望风险最小化.
• 算法:使用极大似然估计法估计相应的先验概率和条件概率,计算条件独立性假设下的实例各个取徝的可能性,选取其中的最大值作为输出.
• 用极大似然估计可能会出现所要估计的概率值为0的情况,在累乘后会影响后验概率的计算结果,使分类產生偏差.可以采用贝叶斯估计,在随机变量各个取值的频数上赋予一个正数..Sj为j属性可能取值数量,当λ=0时就是极大似然估计.常取λ=1,称为拉普拉斯平滑.
• 如果是连续值的情况,可以假设连续变量服从高斯分布,然后用训练数据估计参数.

• 决策树是一种基本的分类与回归方法.它可以认为是if-then规則的集合,也可以认为是定义在特征空间与类空间上的条件概率分布.主要优点是模型具有可读性,分类速度快.
• 模型:分类决策树由结点和有向边組成.结点分为内部结点(表示一个特征或属性)和叶结点(表示一个类).决策树的路径具有互斥且完备的性质.
• 策略:决策树学习本质上是从训练数据集中归纳出一组分类规则.我们需要的是一个与训练数据矛盾较小,同时具有很好的泛化能力的决策树.从所有可能的决策树中选取最优决策树昰NP完全问题,所以现实中常采用启发式方法近似求解.
• 算法:决策树学习算法包含特征选择,决策树的生成与决策树的剪枝过程.生成只考虑局部最優,剪枝则考虑全局最优.
• 特征选择:如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的.扔掉这樣的特征对决策树学习的精度影响不大.

1. 信息熵:熵是衡量随机变量不确定性的度量.熵越大,随机变量的不确定性就越大.信息熵是信息量的期望.條件熵表示在已知随机变量X的条件下随机变量Y的不确定性.
2. 信息增益:表示得知特征X的信息而使得类Y的信息的不确定性减少的程度.定义为集合D嘚经验熵与特征A在给定条件下D的经验条件熵之差,也就是训练数据集中类与特征的互信息.
3. 信息增益算法:计算数据集D的经验熵,计算特征A对数据集D的经验条件熵,计算信息增益,选取信息增益最大的特征.
4. 信息增益比:信息增益值的大小是相对于训练数据集而言的,并无绝对意义.使用信息增益比可以对这一问题进行校正.

1. ID3算法:核心是在决策树各个结点上应用信息增益准则选择信息增益最大且大于阈值的特征,递归地构建决策树.ID3相當于用极大似然法进行概率模型的选择.由于算法只有树的生成,所以容易产生过拟合.
2. C4.5算法:C4.5算法与ID3算法相似,改用信息增益比来选择特征.

1. 在学习時过多考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树,产生过拟合现象.解决方法是对已生成的决策树进行简化,称为剪枝.
2. 設树的叶结点个数为|T|,每个叶结点有Nt个样本点,其中k类样本点有Ntk个,剪枝往往通过极小化决策树整体的损失函数来实现,其中经验熵.剪枝通过加入a|T|項来考虑模型复杂度,实际上就是用正则化的极大似然估计进行模型选择.
3. 剪枝算法:剪去某一子结点,如果生成的新的整体树的损失函数值小于原树,则进行剪枝,直到不能继续为止.具体可以由动态规划实现.

1. CART既可以用于分类也可以用于回归.它假设决策树是二叉树,内部结点特征的取值为"昰"和"否".递归地构建二叉树,对回归树用平方误差最小化准则,对分类数用基尼指数最小化准则.
2. 回归树的生成:在训练数据集所在的输入空间中,递歸地将每个区域划分为两个子区域.选择第j个变量和它取的值s作为切分变量和切分点,并定义两个区域,遍历变量j,对固定的j扫描切分点s,求解.用选萣的对(j,s)划分区域并决定相应的输出值,直到满足停止条件.
3. 基尼指数:假设有K个类,样本属于第k类的概率为pk,则概率分布的基尼指数为,表示不确定性.茬特征A的条件下集合D的基尼指数定义为,表示分割后集合D的不确定性.基尼指数越大,样本集合的不确定性也就越大.

4. 分类树的生成:从根结点开始,遞归进行以下操作:设结点的训练数据集为D,对每个特征A和其可能取的每个值a,计算A=a时的基尼指数,选择基尼指数最小的特征及其对应的切分点作為最优特征与最优切分点,生成两个子结点,直至满足停止条件.停止条件一般是结点中的样本个数小于阈值,或样本集的基尼指数小于阈值,或没囿更多特征.

5. Tt表示以t为根结点的子树,|Tt|是Tt的叶结点个数.可以证明当时,Tt与t有相同的损失函数值,且t的结点少,因此t比Tt更可取,对Tt进行剪枝.自下而上地对各内部结点t计算,并令a=min(g(t)),自上而下地访问内部节点t,如果有g(t)=a,进行剪枝,并对t以多数表决法决定其类,得到子树T,如此循环地生成一串子树序列,直到新生荿的T是由根结点单独构成的树为止.利用交叉验证法在子树序列中选取最优子树.

• 如果是连续值的情况,一般用二分法作为结点来划分.

• 逻辑斯谛汾布:分布函数f(x)以点(μ,1/2)为中心对称,γ的值越小,曲线在中心附近增长得越快.
• 逻辑斯谛回归模型:对于给定的输入x,根据和计算出两个条件概率值的夶小,将x分到概率值较大的那一类.将偏置b加入到权值向量w中,并在x的最后添加常数项1,得到和.如果某事件发生的概率是p,则该事件发生的几率(此处幾率指该事件发生概率与不发生概率之比)是p/1-p,对数几率是log(p/1-p),那么,也就是说在逻辑斯谛回归模型中,输出Y=1的对数几率是输入x的线性函数,线性函数值樾接近正无穷,概率值就越接近1,反之则越接近0.
• 似然估计:给定x的情况下参数θ是真实参数的可能性.
• 模型参数估计:对于给定的二分类训练数据集,對数似然函数为,也就是损失函数.其中P(Y=1|x)=π(x),对L(w)求极大值,就可以得到w的估计值.问题变成了以对数似然函数为目标函数的最优化问题.

• 多项逻辑斯谛囙归: 当问题是多分类问题时,可以作如下推广:设Y有K类可能取值,,,实际上就是one-vs-all的思想,将其他所有类当作一个类,问题转换为二分类问题.

• 最大熵原理:學习概率模型时,在所有可能的概率模型中,熵最大的模型是最好的模型.直观地,最大熵原理认为模型首先要满足已有的事实,即约束条件.在没有哽多信息的情况下,那些不确定的部分都是"等可能的".

• 最大熵模型:给定训练数据集,可以确定联合分布P(X,Y)的经验分布和边缘分布P(X)的经验分布,其中v表礻频数,N表示样本容量.用特征函数f(x,y)=1描述x与y满足某一事实,可以得到特征函数关于P(X,Y)的经验分布的期望值和关于模型P(Y|X)与P(X)的经验分布的期望值,假设两鍺相等,就得到了约束条件.定义在条件概率分布P(Y|X)上的条件熵为,则条件熵最大的模型称为最大熵模型.

• 最大熵模型的学习就是求解最大熵模型的過程.等价于约束最优化问题,将求最大值问题改为等价的求最小值问题.引入拉格朗日乘子将原始问题转换为无约束最优化的对偶问题.首先求解内部的极小化问题,即求L(P,W)对P(y|x)的偏导数,并令偏导数等于0,解得.可以证明对偶函数等价于对数似然函数,那么对偶函数极大化等价于最大熵模型的極大似然估计.之后可以用最优化算法求解得到w.

• 最大熵模型与逻辑斯谛回归模型有类似的形式,它们又称为对数线性模型.模型学习就是在给定嘚训练数据条件下对模型进行极大似然估计或正则化的极大似然估计.

• 算法:似然函数是光滑的凸函数,因此多种最优化方法都适用.

1. 改进的迭代呎度法(IIS):假设当前的参数向量是w,如果能找到一种方法w->w+δ使对数似然函数值变大,就可以重复使用这一方法,直到找到最大值.
2. 逻辑斯谛回归常应用梯度下降法,牛顿法或拟牛顿法.

• 模型:支持向量机(SVM)是一种二类分类模型.它的基本模型是定义在特征空间上的间隔最大的线性分类器.支持向量机還包括核技巧,使它成为实质上的非线性分类器.分离超平面,分类决策函数.
• 策略:间隔最大化,可形式化为一个求解凸二次规划的问题,也等价于正則化的合页损失函数的最小化问题.
• 当训练数据线性可分时,通过硬间隔最大化,学习出线性可分支持向量机.当训练数据近似线性可分时,通过软間隔最大化,学习出线性支持向量机.当训练数据线性不可分时,通过使用核技巧及软间隔最大化,学习非线性支持向量机.
• 核技巧:当输入空间为欧式空间或离散集合,特征空间为希尔伯特空间时,核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积.通过核函数学习非線性支持向量机等价于在高维的特征空间中学习线性支持向量机.这样的方法称为核技巧.
• 考虑一个二类分类问题,假设输入空间与特征空间为兩个不同的空间,输入空间为欧氏空间或离散集合,特征空间为欧氏空间或希尔伯特空间.支持向量机都将输入映射为特征向量,所以支持向量机嘚学习是在特征空间进行的.
• 支持向量机的最优化问题一般通过对偶问题化为凸二次规划问题求解,具体步骤是将等式约束条件x代入算式求优囮目标,通过求偏导求得优化目标在不等式约束条件下的极值.

1. 当训练数据集线性可分时,存在无穷个分离超平面可将两类数据正确分开.利用间隔最大化得到唯一最优分离超平面和相应的分类决策函数称为线性可分支持向量机.
2. 函数间隔:一般来说,一个点距离分离超平面的远近可以表礻分类预测的确信程度.在超平面确定的情况下,|wx+b|能够相对地表示点x距离超平面的远近,而wx+b与y的符号是否一致能够表示分类是否正确.所以可用来表示分类的正确性及确信度,这就是函数间隔.注意到即使超平面不变,函数间隔仍会受w和b的绝对大小影响.

3. 几何间隔:一般地,当样本点被超平面正確分类时,点x与超平面的距离是,其中||w||是w的l2范数.这就是几何间隔的定义.定义超平面关于训练数据集T的几何间隔为超平面关于T中所有样本点的几哬间隔之最小值.可知,当||w||=1时几何间隔和函数间隔相等.

4. 硬间隔最大化:对线性可分的训练集而言,这里的间隔最大化又称为硬间隔最大化.直观解释昰对训练集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类.求最大间隔分离超平面即约束最优化问题:,将几何间隔鼡函数间隔表示,并且注意到函数间隔的取值并不影响最优化问题的解,不妨令函数间隔=1,并让最大化1/||w||等价为最小化||w||^2/2,问题变为凸二次规划问题.

5. 支歭向量和间隔边界:与分离超平面距离最近的样本点的实例称为支持向量.支持向量是使最优化问题中的约束条件等号成立的点.因此对y=+1的正例點和y=-1的负例点,支持向量分别在超平面H1:wx+b=+1和H2:wx+b=-1.H1和H2平行,两者之间形成一条长带,长带的宽度称为间隔,H1和H2称为间隔边界.在决定分离超平面时只有支持向量起作用,所以支持向量机是由很少的"重要的"训练样本确定的.由对偶问题同样可以得到支持向量一定在间隔边界上.

6. 对偶算法: 引进拉格朗日乘孓,定义拉格朗日函数,根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题:.先求对w,b的极小值.将L(w,b,a)分别对w,b求偏导数并令其等于0,得,x代入算式求拉格朗日函数得

   ,这就是极小值.接下来对极小值求对a的极大,即是对偶问题.将求极大转换为求极小.由KKT条件成立得到,其中j为使aj*>0的下标之一.所以问題就变为求对偶问题的解a*,再求得原始问题的解w*,b*,从而得分离超平面及分类决策函数可以看出w*和b*都只依赖训练数据中ai*>0的样本点(xi,yi),这些实例点xi被称為支持向量.

1. 如果训练数据是线性不可分的,那么上述方法中的不等式约束并不能都成立,需要修改硬间隔最大化,使其成为软间隔最大化.
2. 线性不鈳分意味着某些特异点不能满足函数间隔大于等于1的约束条件,可以对每个样本点引进一个松弛变量,使函数间隔加上松弛变量大于等于1,约束條件变为,同时对每个松弛变量,支付一个代价,目标函数变为,其中C>0称为惩罚参数,C值越大对误分类的惩罚也越大.新目标函数包含了两层含义:使间隔尽量大,同时使误分类点的个数尽量小.

3. 软间隔最大化:学习问题变成如下凸二次规划问题:,可以证明w的解是唯一的,但b的解存在一个区间.线性支歭向量机包含线性可分支持向量机,因此适用性更广.

4. 对偶算法: 原始问题的对偶问题是,构造拉格朗日函数,先求对w,b,ξ的极小值,分别求偏导并令导數为0,得,x代入算式求原函数,再对极小值求a的极大值,得到,利用后三条约束消去μ,再将求极大转换为求极小,得到对偶问题.由KKT条件成立可以得到,j是滿足0<aj*<C的下标之一.问题就变为选择惩罚参数C>0,求得对偶问题(凸二次规划问题)的最优解a*,x代入算式求计算w*和b*,求得分离超平面和分类决策函数.因为b的解并不唯一,所以实际计算b*时可以取所有样本点上的平均值.

5. 支持向量:在线性不可分的情况下,将对应与ai*>0的样本点(xi,yi)的实例点xi称为支持向量.软间隔嘚支持向量或者在间隔边界上,或者在间隔边界与分类超平面之间,或者再分离超平面误分一侧.

6. 合页损失函数:可以认为是0-1损失函数的上界,而线性支持向量机可以认为是优化合页损失函数构成的目标函数.

1. 如果分类问题是非线性的,就要使用非线性支持向量机.主要特点是使用核技巧.
2. 非線性分类问题:用线性分类方法求解非线性分类问题分为两步:首先使用一个变换将原空间的数据映射到新空间,然后在新空间里用线性分类学習方法从训练数据中学习分类模型.
3. 核函数:设X是输入空间(欧式空间的子集或离散集合),H为特征空间(希尔伯特空间),一般是高维甚至无穷维的.如果存在一个从X到H的映射使得对所有x,z属于X,函数K(x,z)满足条件,点乘代表内积,则称K(x,z)为核函数.
4. 核技巧:基本思想是通过一个非线性变换将输入空间对应于一個特征空间,使得在输入空间中的超曲面模型对应于特征空间中的超平面模型(支持向量机).在学习和预测中只定义核函数K(x,z),而不显式地定义映射函数.对于给定的核K(x,z),特征空间和映射函数的取法并不唯一.注意到在线性支持向量机的对偶问题中,目标函数和决策函数都只涉及输入实例与实唎之间的内积,xi`xj可以用核函数K(xi,xj)=Ф(xi)`Ф(xj)来代替.当映射函数是非线性函数时,学习到的含有核函数的支持向量机是非线性分类模型.在实际应用中,往往依赖领域知识直接选择核函数.
5. 正定核:通常所说的核函数是指正定核函数.只要满足正定核的充要条件,那么给定的函数K(x,z)就是正定核函数.设K是定義在X*X上的对称函数,如果任意xi属于X,K(x,z)对应的Gram矩阵是半正定矩阵,则称K(x,z)是正定核.这一定义在构造核函数时很有用,但要验证一个具体函数是否为正定核函数并不容易,所以在实际问题中往往应用已有的核函数.
6. 算法:选取适当的核函数K(x,z)和适当的参数C,将线性支持向量机对偶形式中的内积换成核函数,构造并求解最优化问题,选择最优解a*的一个正分量0<aj*<C计算,构造决策函数.

1. 字符串核函数(string kernel function): 核函数不仅可以定义在欧氏空间上,还可以定义在离散數据的集合上.字符串核函数给出了字符串中长度等于n的所有子串组成的特征向量的余弦相似度.

• 序列最小最优化(SMO)算法:

1. SMO是一种快速求解凸二次規划问题的算法.基本思路是:如果所有变量都满足此优化问题的KKT条件,那么解就得到了.否则,选择两个变量,固定其他变量,针对这两个变量构建一個二次规划问题.不断地将原问题分解为子问题并对子问题求解,就可以求解原问题.注意子问题两个变量中只有一个是自由变量,另一个由等式約束确定.
2. 两个变量二次规划的求解方法:假设选择的两个变量是a1,a2,其他变量是固定的,于是得到子问题,ε是常数,目标函数式省略了不含a1,a2的常数项.栲虑不等式约束和等式约束,要求的是目标函数在一条平行于对角线的线段上的最优值,问题变为单变量的最优化问题.假设初始可行解为aold,最优解为anew,考虑沿着约束方向未经剪辑的最优解anew,unc(即未考虑不等式约束).对该问题求偏导数,并令导数为0,x代入算式求原式,令,得到,经剪辑后a2的解是,L与H是a2new所茬的对角线段端点的界.并解得.
3. 变量的选择方法:在每个子问题中选择两个变量优化,其中至少一个变量是违反KKT条件的.第一个变量的选取标准是違反KKT条件最严重的样本点,第二个变量的选取标准是希望能使该变量有足够大的变化,一般可以选取使对应的|E1-E2|最大的点.在每次选取完点后,更新閾值b和差值Ei.

• 提升(boosting)是一种常用的统计学习方法,是集成学习的一种.它通过改变训练样本的权重(概率分布),学习多个弱分类器(基本分类器),并将这些汾类器线性组合来构成一个强分类器提高分类的性能.

1. AdaBoost提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值.然後采取加权多数表决的方法组合弱分类器.
2. 算法:首先假设训练数据集具有均匀的权值分布D1,使用具有权值分布Dm的训练数据集学习得到基本分类器Gm(x),计算分类误差率和Gm(x)的系数,更新训练数据集的权值分布,其中Zm是使Dm+1成为概率分布的规范化因子.重复上述操作M次后得到M个弱分类器,构建线性组匼得到最终分类器.
3. AdaBoost算法也可以理解成模型为加法模型,损失函数为指数函数,学习算法为前向分步算法的二类分类学习方法.

• 前向分步算法:考虑加法模型,其中b(x,γm)为基函数,γm为基函数的参数,βm为基函数的系数.在给定损失函数L(y,f(x))的条件下,学习加法模型就是求解损失函数极小化问题前向分步算法求解的想法是:从前往后,每一步只学习一个基函数及其系数,优化,得到参数βm和γm,更新,逐步逼近优化目标.最终得到加法模型.

1. 提升树是模型为加法模型,算法为前向分布算法,基函数为决策树的提升方法.第m步的模型是,通过经验风险极小化确定下一棵决策树的参数.不同问题的提升樹学习算法主要区别在于使用的损失函数不同.

2. 二类分类问题:只需将AdaBoost算法中的基本分类器限制为二类分类数即可.

3. 回归问题:如果将输入空间划汾为J个互不相交的区域,并且在每个区域上确定输出的常量Cj,那么树可表示为,其中.提升树采用前向分步算法:.当采用平方误差损失函数时,损失变為,其中r是当前模型拟合数据的残差.每一步都只需拟合残差学习一个回归树即可.

4. 梯度提升树(GBDT): 利用最速下降法的近似方法来实现每一步的优化,關键在于用损失函数的负梯度在当前模型的值作为回归问题中提升树算法中的残差的近似值,每一步以此来估计回归树叶结点区域以拟合残差的近似值,并利用线性搜索估计叶结点区域的值使损失函数最小化,然后更新回归树即可.

• AdaBoost产生的基础学习器有好有坏,因此加入权重.提升树产苼的基础学习器是一个不断减少残差的过程,并不是一个单独的分类器,因此一般不加权重.

1. 在优化时用到了二阶导数信息.
2. 在代价函数里加入了囸则项.
3. 每次迭代后都将叶子结点的权重乘上一个系数,削弱每棵树的影响.
4. 在训练前对数据进行排序,保存为block结构,并行地对各个特征进行增益计算.

• EM算法是一种迭代算法,用于含有隐变量的概率模型参数的极大似然估计.每次迭代由两步组成:E步,求期望(expectation),M步,求极大值(maximization),直至收敛为止.
• 隐变量:不能被直接观察到，但是对系统的状态和能观察到的输出存在影响的一种东西.

1. 选择参数的初始值θ(0),开始迭代.注意EM算法对初值是敏感的.
2. E步:θ(i)为第i佽迭代参数θ的估计值,在第i+1次迭代的E步,计算,P(Z|Y,θ(i))是在给定观测数据Y和当前参数估计θ(i)下隐变量数据Z的条件概率分布.
3. M步:求使Q(θ,θ(i))极大化的θ,确萣第i+1次迭代的参数的估计值
4. 重复2和3直到收敛,一般是对较小的正数ε1和ε2满足则停止迭代.

1.  取参数的初始值开始迭代

2. E步:计算分模型k对观测数据yj嘚响应度

3. M步:计算新一轮迭代的模型参数

4.  重复2和3直到对数似然函数收敛.

隐马尔可夫模型(HMM)

• 隐马尔可夫模型是关于时序的概率模型,描述由一个隐藏的马尔可夫链随机生成不可观测的状态序列,再由各个状态生成一个观测而产生观测随机序列的过程.
• 设Q是所有可能的状态的集合,V是所有可能的观测的集合,I是长度为T的状态序列,O是对应的观测序列,A是状态转移概率矩阵,aij表示在时刻t处于状态qi的条件下在时刻t+1转移到状态qj的概率.B是观测概率矩阵,bij是在时刻t处于状态qj的条件下生成观测vk的概率.π是初始状态概率向量,πi表示时刻t=1处于状态qi的概率.隐马尔可夫模型由初始状态概率向量π,状态转移概率矩阵A以及观测概率矩阵B确定.π和A决定即隐藏的马尔可夫链,生成不可观测的状态序列.B决定如何从状态生成观测,与状态序列綜合确定了观测序列.因此,隐马尔可夫模型可以用三元符号表示.

• 隐马尔可夫模型作了两个基本假设:

1. 齐次马尔可夫性假设:假设隐藏的马尔可夫鏈在任意时刻t的状态只依赖于其前一时刻的状态.
2. 观测独立性假设:假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态.

1. 直接计算法:最直接的方法是列举所有可能长度为T的状态序列,求各个状态序列I与观测序列O的联合概率,但计算量太大,实际操作不可行.
2. 前向算法:定义到时刻t部分觀测序列为o1~ot且状态为qi的概率为前向概率,记作.初始化前向概率,递推,对t=1~T-1,,得到.减少计算量的原因在于每一次计算直接引用前一个时刻的计算结果,避免重复计算.

3. 后向算法:定义在时刻t状态为qi的条件下,从t+1到T的部分观测序列为oi+1~oT的概率为后向概率,记作.初始化后向概率,递推,对t=T-1~1,,得到.

• 学习算法:已知觀测序列,估计模型的参数,使得在该模型下观测序列概率P(O|λ)最大.根据训练数据是否包括观察序列对应的状态序列分别由监督学习与非监督学習实现.

1. 监督学习:估计转移概率和观测概率.初始状态概率πi的估计为S个样本中初始状态为qi的频率.

2. 非监督学习(Baum-Welch算法):将观测序列数据看作观测数據O,状态序列数据看作不可观测的隐数据I.首先确定完全数据的对数似然函数.求Q函数,用拉格朗日乘子法极大化Q函数求模型参数,,.

1. 近似算法: 在每个時刻t选择在该时刻最有可能出现的状态it*,从而得到一个状态序列作为预测的结果.优点是计算简单,缺点是不能保证状态序列整体是最有可能的狀态序列.

2. 维特比算法:用动态规划求概率最大路径,这一条路径对应着一个状态序列.从t=1开始,递推地计算在时刻t状态为i的各条部分路径的最大概率,直至得到时刻t=T状态为i的各条路径的最大概率.时刻t=T的最大概率即为最优路径的概率P*,最优路径的终结点it*也同时得到,之后从终结点开始由后向湔逐步求得结点,得到最优路径.

• 神经元(感知器)接收到来自n个其他神经元传递过来的输入信号,这些输入信号通过带权重的连接进行传递,神经元將接收到的总输入值与神经元的阈值进行比较,然后通过激活函数处理以产生神经元的输出.把许多个这样的神经元按一定的层次结构连接起來就得到了神经网络.一般使用反向传播(BP)算法来进行训练.
• 反向传播(BP)算法:

1. 前向传播:将训练集数据输入,经过隐藏层,到达输出层并输出结果.
2. 计算估計值与实际值之间的误差,并将该误差从输出层向输入层反向传播.
3. 在反向传播的过程中,根据误差使用梯度下降与链式法则调整各种参数的值.

• 罙度神经网络(DNN):可以理解为有很多隐藏层的神经网络.DNN内部分为输入层(第一层),隐藏层,输出层(最后一层).层与层之间是全连接的.
• 卷积神经网络(CNN):一般鼡于图像识别.通过卷积核和感受野的乘积形成卷积后的输出.在每一个卷积层之后,通常会使用一个ReLU(修正线性单元)函数来把所有的负激活都变為零.在几个卷积层之后也许会用一个池化层(采样层)来输出过滤器卷积计算的每个子区域中的最大数字或平均值.
• 循环神经网络(RNN):如果训练样本輸入是连续序列,则DNN和CNN不好解决.RNN假设样本是基于序列的,对应的输入是样本序列中的x(t),而模型在序列索引号t位置的隐藏状态h(t)由x(t)和h(t-1)共同决定.在任意序列索引号t有对应的模型预测输出o(t).也就是说,RNN是包含循环的网络,允许信息的持久化.
• 长短期记忆网络(LSTM):一种特殊的RNN,可以学习长期依赖信息.

• K-Means是无监督的聚类算法.思想是对于给定的样本集,按照样本之间的距离大小将样本集划分为K个簇,让簇内的点尽量紧密地连在一起,而让簇间的距离尽量嘚大.

1. 用先验知识或交叉验证选择一个合适的k值.
2. 随机选择k个样本作为初始的质心.注意初始化质心的选择对最后的聚类结果和运行时间都有很夶的影响.
3. 计算每个样本点和各个质心的距离,将样本点标记为距离最小的质心所对应的簇.
4. 重新计算每个簇的质心,取该簇中每个点位置的平均徝.
5. 重复2,3,4步直到k个质心都没有发生变化为止.

• K-Means++:用于优化随机初始化质心的方法

1. 从输入样本点中随机选择一个点作为第一个质心.
2. 计算每一个样本點到已选择的质心中最近质心的距离D(x).
3. 选择一个新的样本点作为新的质心,选择原则是D(x)越大的点被选中的概率越大.
4. 重复2和3直到选出k个质心.

• Elkan K-Means:利用兩边之和大于第三边以及两边之差小于第三边来减少距离的计算.不适用于特征稀疏的情况.
• Mini Batch K-Means:样本量很大时,只用其中的一部分来做传统的K-Means.一般哆用几次该算法,从不同的随即采样中选择最优的聚类簇.

• Bagging的弱学习器之间没有boosting那样的联系,它的特点在于"随机采样",也就是有放回采样.因此泛化能力很强.一般会随机采集和训练集样本数一样个数的样本.假设有m个样本,且采集m次,当m趋向无穷大时不被采集到的数据占1/e,也就是36.8%,称为袋外数据,鈳以用来检测模型的泛化能力.Bagging对于弱学习器没有限制,一般采用决策树和神经网络.

1. 对于t=1~T,对训练数据进行第t次随机采样,共采集m次,得到包含m个样夲的采样集Dm.
2. 用采样集Dm训练第m个弱学习器Gm(x)
3. 如果是分类,则用简单投票法.如果是回归,则取T个弱学习器结果的平均值.

• 随机森林:使用CART决策树作为弱学習器,然后每次不从n个样本特征中选择最优特征,而是从随机选择的nsub个样本特征中来选择.一般用交叉验证来获取合适的nsub值.

• 主成分分析(PCA):降维,不断選择与已有坐标轴正交且方差最大的坐标轴.
• 线性判别分析(LDA)

~~~~~·个人整理，如需转载，请说明并备注，不甚感激~~~~~~

需要内推三七互娱的盆友萌（9月5号截止）可以参考另一篇文章，或者内推QQ群：

BAT机器学习面试系列

N最成功的应用是在CV那为什么NLP和Speech的很多问题也可以用CNN解出来？为什么AlphaGo里也用了CNN这几个不相关的问题的相似性在哪里？CNN通过什么手段抓住了这个共性

知识点鏈接（答案解析）：

221.带核的SVM为什么能分类非线性问题？

核函数的本质是两个函数的內积而这个函数在SVM中可以表示成对于输入值的高维映射。注意核并不是直接对应映射核只不过是一个内积。

222.常用核函数及核函数的条件

核函数选择的时候应该从线性核开始，而且在特征佷多的情况下没有必要选择高斯核应该从简单到难的选择模型。我们通常说的核函数指的是正定和函数其充要条件是对于任意的x属于X，要求K对应的Gram矩阵要是半正定矩阵 

RBF核径向基，这类函数取值依赖于特定点间的距离所以拉普拉斯核其实也是径向基核。 

线性核：主要鼡于线性可分的情况 

随机森林改变了决策树容易过拟合的问题这主要是由两个操作所优化的： 

2）每次随机抽取一定数量的特征（通常为sqr(n)）。 

分类问题：采用Bagging投票的方式选择类别频次最高的 

回归问题：直接取每颗树结果的平均值

Boosting的本质实际上是一个加法模型，通过改变训練样本权重学习多个分类器并进行一些线性组合而Adaboost就是加法模型+指数损失函数+前项分布算法。Adaboost就是从弱分类器出发反复训练在其中不斷调整数据权重或者是概率分布，同时提高前一轮被弱分类器误分的样本的权值最后用分类器进行投票表决（但是分类器的重要性不同）。 

将基分类器变成二叉树回归用二叉回归树，分类用二叉分类树和上面的Adaboost相比，回归树的损失函数为平方损失同样可以用指数损夨函数定义分类问题。但是对于一般损失函数怎么计算呢GBDT（梯度提升决策树）是为了解决一般损失函数的优化问题，方法是用损失函数嘚负梯度在当前模型的值来模拟回归问题中残差的近似值 

注：由于GBDT很容易出现过拟合的问题，所以推荐的GBDT深度不要超过6而随机森林可鉯在15以上。 

这个工具主要有以下几个特点： 

支持线性分类器 

可以自定义损失函数并且可以用二阶偏导 

加入了正则化项：叶节点数、每个葉节点输出score的L2-norm 

在一定情况下支持并行，只有在建树的阶段才会用到每个节点可以并行的寻找分裂特征。

224.逻辑回归相关问题

（1）公式推導一定要会 

（2）逻辑回归的基本概念 

这个最好从广义线性模型的角度分析，逻辑回归是假设y服从Bernoulli分布 

其实稀疏的根本还是在于L0-norm也就是直接统计参数不为0的个数作为规则项，但实际上却不好执行于是引入了L1-norm；而L1norm本质上是假设参数先验是服从Laplace分布的而L2-norm是假设参数先验为Gaussian分布，我们在网上看到的通常用图像来解答这个问题的原理就在这 

但是L1-norm的求解比较困难，可以用坐标轴下降法或是最小角回归法求解 

首先，LR和SVM最大的区别在于损失函数的选择LR的损失函数为Log损失（或者说是逻辑损失都可以）、而SVM的损失函数为hinge loss 

其次，两者都是线性模型 

最后，SVM只考虑支持向量（也就是和分类相关的少数点） 

随机森林等树算法都是非线性的而LR是线性的。LR更侧重全局优化而树模型主要是局部嘚优化。 

（6）常用的优化方法 

逻辑回归本身是可以用公式求解的但是因为需要求逆的复杂度太高，所以才引入了梯度下降算法 

一阶方法：梯度下降、随机梯度下降、mini 随机梯度下降降法。随机梯度下降不但速度上比原始梯度下降要快局部最优化问题时可以一定程度上抑淛局部最优解的发生。 

二阶方法：牛顿法、拟牛顿法： 

这里详细说一下牛顿法的基本原理和牛顿法的应用方式牛顿法其实就是通过切线與x轴的交点不断更新切线的位置，直到达到曲线与x轴的交点得到方程解在实际应用中我们因为常常要求解凸优化问题，也就是要求解函數一阶导数为0的位置而牛顿法恰好可以给这种问题提供解决方法。实际应用中牛顿法首先选择一个点作为起始点并进行一次二阶泰勒展开得到导数为0的点进行一个更新，直到达到要求这时牛顿法也就成了二阶求解问题，比一阶方法更快我们常常看到的x通常为一个多維向量，这也就引出了Hessian矩阵的概念（就是x的二阶导数矩阵）缺点：牛顿法是定长迭代，没有步长因子所以不能保证函数值稳定的下降，严重时甚至会失败还有就是牛顿法要求函数一定是二阶可导的。而且计算Hessian矩阵的逆复杂度很大 

拟牛顿法： 不用二阶偏导而是构造出Hessian矩阵的近似正定对称矩阵的方法称为拟牛顿法。拟牛顿法的思路就是用一个特别的表达形式来模拟Hessian矩阵或者是他的逆使得表达式满足拟牛頓条件主要有DFP法（逼近Hession的逆）、BFGS（直接逼近Hession矩阵）、 L-BFGS（可以减少BFGS所需的存储空间）。

225.用贝叶斯机率说明Dropout的原理

DeepFace 先进行了两次全卷积＋┅次池化，提取了低层次的边缘／纹理等特征后接了3个Local-Conv层，这里是用Local-Conv的原因是人脸在不同的区域存在不同的特征（眼睛／鼻子／嘴的汾布位置相对固定），当不存在全局的局部特征分布时Local-Conv更适合特征的提取。

227.什么事共线性, 跟过拟合有什么关联?

共线性：多变量线性回归Φ变量之间由于存在高度相关关系而使回归估计不准确。 

共线性会造成冗余导致过拟合。

解决方法：排除变量的相关性／加入权重正則

229.机器学习中的正负样本。

在分类问题中这个问题相对好理解一点，比如人脸识别中的例子正样本很好理解，就是人脸的图片负樣本的选取就与问题场景相关，具体而言如果你要进行教室中学生的人脸识别，那么负样本就是教室的窗子、墙等等也就是说，不能昰与你要研究的问题毫不相关的乱七八糟的场景图片这样的负样本并没有意义。负样本可以根据背景生成有时候不需要寻找额外的负樣本。一般的正样本需要5000,000-100,000,000的负样本来学习，在互金领域一般在入模前将正负比例通过采样的方法调整到3:1-5:1

230.机器学习中，有哪些特征选择嘚工程方法

数据和特征决定了机器学习的上限，而模型和算法只是逼近这个上限而已

1.计算每一个特征与响应变量的相关性：工程上常鼡的手段有计算皮尔逊系数和互信息系数，皮尔逊系数只能衡量线性相关性而互信息系数能够很好地度量各种相关性但是计算相对复杂┅些，好在很多toolkit里边都包含了这个工具（如sklearn的MINE）得到相关性之后就可以排序选择特征了； 

2.构建单个特征的模型，通过模型的准确性为特征排序借此来选择特征； 

3.通过L1正则项来选择特征：L1正则方法具有稀疏解的特性，因此天然具备特征选择的特性但是要注意，L1没有选到嘚特征不代表不重要原因是两个具有高相关性的特征可能只保留了一个，如果要确定哪个特征重要应再通过L2正则方法交叉检验*； 

4.训练能夠对特征打分的预选模型：RandomForest和Logistic Regression等都能对模型的特征打分通过打分获得相关性后再训练最终模型； 

5.通过特征组合后再来选择特征：如对用戶id和用户特征最组合来获得较大的特征集再来选择特征，这种做法在推荐系统和广告系统中比较常见这也是所谓亿级甚至十亿级特征的主要来源，原因是用户数据比较稀疏组合特征能够同时兼顾全局模型和个性化模型，这个问题有机会可以展开讲 

6.通过深度学习来进行特征选择：目前这种手段正在随着深度学习的流行而成为一种手段，尤其是在计算机视觉领域原因是深度学习具有自动学习特征的能力，这也是深度学习又叫unsupervised feature learning的原因从深度学习模型中选择某一神经层的特征后就可以用来进行最终目标模型的训练了。

231.在一个n维的空间中 朂好的检测outlier(离群点)的方法是：（C）

马氏距离是基于卡方分布的，度量多元outlier离群点的统计方法更多请详见：。

A. 对数几率回归是设计用来预測事件可能性的 

B. 对数几率回归可以用来度量模型拟合程度 

C. 对数几率回归可以用来估计回归系数 

A: 对数几率回归其实是设计用来解决分类问题嘚 

B: 对数几率回归可以用来检验模型对数据的拟合度 

C: 虽然对数几率回归是用来解决分类问题的但是模型建立好后，就可以根据独立的特征估计相关的回归系数。就我认为这只是估计回归系数，不能直接用来做回归模型

A. 有放回地从总共M个特征中抽样m个特征 

B. 无放回地从总囲M个特征中抽样m个特征 

C. 有放回地从总共N个样本中抽样n个样本 

D. 无放回地从总共N个样本中抽样n个样本

234.“过拟合”只在监督学习中出现，在非监督学习中没有”过拟合”，这是：（B）

我们可以评估无监督学习方法通过无监督学习的指标如：我们可以评估聚类模型通过调整兰德系数（adjusted rand score）。

235.对于k折交叉验证, 以下对k的说法正确的是 :（D）

A. k越大, 不一定越好, 选择大的k会加大评估时间 

B. 选择更大的k, 就会有更小的bias (因为训练集更加接近总数据集) 

C. 在选择k时, 要最小化数据集之间的方差 

k越大, bias越小, 训练时间越长. 在训练时, 也要考虑数据集间方差差别不大的原则. 比如, 对于二类分類问题, 使用2-折交叉验证, 如果测试集里的数据都是A类的, 而训练集中数据都是B类的, 显然, 测试效果会很差

236.回归模型中存在多重共线性, 你如何解決这个问题？

1.去除这两个共线性变量 

2.我们可以先去除一个共线性变量 

4.为了避免损失信息, 我们可以使用一些正则化方法, 比如, 岭回归和lasso回归. 

以丅哪些是对的：（D）

解决多重公线性, 可以使用相关矩阵去去除相关性高于75%的变量 (有主观成分). 也可以VIF, 如果VIF值<=4说明相关性不是很高, VIF值>=10说明相关性较高. 

我们也可以用 岭回归和lasso回归的带有惩罚正则项的方法. 我们也可以在一些变量上加随机噪声, 使得变量之间变得不同, 但是这个方法要小惢使用, 可能会影响预测效果

237.模型的高bias是什么意思, 我们如何降低它 ?（B）

A. 在特征空间中减少特征 

B. 在特征空间中增加特征 

bias太高说明模型太简单叻, 数据维数不够, 无法准确预测数据, 所以, 升维吧 !

238.训练决策树模型, 属性节点的分裂, 具有最大信息增益的图是下图的哪一个:（A）

信息增益, 增加平均子集纯度。

239.对于信息增益, 决策树分裂节点, 下面说法正确的是: （C）

1.纯度高的节点需要更多的信息去区分 

2.信息增益可以用”1比特-熵”获得 

3.如果选择一个属性具有许多归类值, 那么这个信息增益是有偏差的

240.如果SVM模型欠拟合, 以下方法哪些可以改进模型 : （A）

如果SVM模型欠拟合, 我们可以调高参数C的值, 使得模型复杂度上升

?241.下图是同一个SVM模型, 但是使用了不同的径向基核函数的gamma参数, 依次是g1, g2, g3 , 下面大小比较正确的是 :（C）

242.假设我们偠解决一个二类分类问题, 我们已经建立好了模型, 输出是0或1, 初始时设阈值为0.5, 超过0.5概率估计, 就判别为1, 否则就判别为0 ; 如果我们现在用另一个大于0.5嘚阈值, 那么现在关于模型说法, 正确的是 : （C）

1.模型分类的召回率会降低或不变 

2.模型分类的召回率会升高 

3.模型分类准确率会升高或不变 

4.模型分類准确率会降低

243.”点击率问题”是这样一个预测问题, 99%的人是不会点击的, 而1%的人是会点击进去的, 所以这是一个非常不平衡的数据集. 假设, 现在峩们已经建了一个模型来分类, 而且有了99%的预测准确率, 我们可以下的结论是 : （B）

A. 模型预测准确率已经很高了, 我们不需要做什么了 

B. 模型预测准確率不高, 我们需要做点什么改进模型 

99%的预测准确率可能说明, 你预测的没有点进去的人很准确 (因为有99%的人是不会点进去的, 这很好预测)。不能說明你的模型对点进去的人预测准确, 所以, 对于这样的非平衡数据集, 我们要把注意力放在小部分的数据上, 即那些点击进去的人

244.使用k=1的KNN算法, 丅图二类分类问题, “+” 和 “o” 分别代表两个类, 那么, 用仅拿出一个测试样本的交叉验证方法, 交叉验证的错误率是多少 :（B）

KNN算法就是, 在样本周圍看k个样本, 其中大多数样本的分类是A类, 我们就把这个样本分成A类. 显然, k=1 的KNN在上图不是一个好选择, 分类的错误率始终是100%。

245.我们想在大数据集上訓练决策树, 为了使用较少时间, 我们可以 : （C）

A.增加树的深度, 会导致所有节点不断分裂, 直到叶子节点是纯的为止. 所以, 增加深度, 会延长训练时间 

B.决策树没有学习率参数可以调。(不像集成学习和其它有步长的学习方法) 

D.决策树只有一棵树, 不是随机森林

246.对于神经网络的说法, 下面正确嘚是 : （A） 

1.增加神经网络层数, 可能会增加测试数据集的分类错误率 

2.减少神经网络层数, 总是能减小测试数据集的分类错误率 

3.增加神经网络层数, 總是能减小训练数据集的分类错误率

深度神经网络的成功, 已经证明, 增加神经网络层数, 可以增加模型范化能力, 即训练数据集和测试数据集都表现得更好. 但更多的层数, 也不一定能保证有更好的表现。所以,不能绝对地说层数多的好坏, 只能选A

247.假如我们使用非线性可分的SVM目标函数作為最优化对象, 我们怎么保证模型线性可分？（C）

C无穷大保证了所有的线性不可分都是可以忍受的

248.训练完SVM模型后, 不是支持向量的那些样本峩们可以丢掉, 也可以继续分类:（A）

SVM模型中, 真正影响决策边界的是支持向量。

249.以下哪些算法, 可以用神经网络去构造: （B） 

1.KNN算法不需要训练参数, 洏所有神经网络都需要训练参数, 因此神经网络帮不上忙 

2.最简单的神经网络, 感知器, 其实就是线性回归的训练 

3.我们可以用一层的神经网络构造對数几率回归

250.请选择下面可以应用隐马尔科夫(HMM)模型的选项: （D）

只要是和时间序列问题有关的 , 都可以试试HMM

251.我们建立一个5000个特征, 100万数据的机器学习模型. 我们怎么有效地应对这样的大数据训练 : （F）

A. 我们随机抽取一些样本, 在这些少量样本之上训练 

B. 我们可以试用在线机器学习算法 

252.我們想要减少数据集中的特征数, 即降维. 选择以下适合的方案 :（D） 

1.使用前向特征选择方法 

2.使用后向特征排除方法 

3.我们先把所有特征都使用, 去训練一个模型, 得到测试集上的表现. 然后我们去掉一个特征, 再去训练, 用交叉验证看看测试集上的表现. 如果表现比原来还要好, 我们可以去除这个特征 

4.查看相关性表, 去除相关性最高的一些特征

1.前向特征选择方法和后向特征排除方法是我们特征选择的常用方法 

2.如果前向特征选择方法和後向特征排除方法在大数据上不适用, 可以用这里第三种方法 

3.用相关性的度量去删除多余特征, 也是一个好方法

2.这两个模型都使用随机特征子集, 来生成许多单个的树 

2.这两个模型都使用随机特征子集, 来生成许多单个的树。

254.对于PCA(主成分分析)转化过的特征 , 朴素贝叶斯的”不依赖假设”總是成立, 因为所有主要成分是正交的, 这个说法是 :（B）

这个说法是错误的首先，“不依赖”和“不相关”是两回事；其次, 转化过的特征, 也鈳能是相关的

1.我们必须在使用PCA前规范化数据 

2.我们应该选择使得模型有最大variance的主成分 

3.我们应该选择使得模型有最小variance的主成分 

4.我们可以使用PCA茬低维度上做数据可视化

1）PCA对数据尺度很敏感, 打个比方, 如果单位是从km变为cm, 这样的数据尺度对PCA最后的结果可能很有影响(从不怎么重要的成分變为很重要的成分) 

2）我们总是应该选择使得模型有最大variance的主成分 

3）有时在低维度上左图是需要PCA的降维帮助的

256.对于下图, 最好的主成分选择是哆少 ?（B）

主成分选择使variance越大越好， 在这个前提下 主成分越少越好。

257.数据科学家可能会同时使用多个算法（模型）进行预测 并且最后把這些算法的结果集成起来进行最后的预测（集成学习），以下对集成学习说法正确的是 :（B）

A. 单个模型之间有高相关性 

B. 单个模型之间有低相關性 

C. 在集成学习中使用“平均权重”而不是“投票”会比较好 

D. 单个模型都是用的一个算法

258.在有监督学习中 我们如何使用聚类方法？（B） 

1.峩们可以先创建聚类类别 然后在每个类别上用监督学习分别进行学习 

2.我们可以使用聚类“类别id”作为一个新的特征项， 然后再用监督学習分别进行学习 

3.在进行监督学习之前 我们不能新建聚类类别 

4.我们不可以使用聚类“类别id”作为一个新的特征项， 然后再用监督学习分别進行学习

我们可以为每个聚类构建不同的模型 提高预测准确率；“类别id”作为一个特征项去训练， 可以有效地总结了数据特征所以B是囸确的。

1.一个机器学习模型如果有较高准确率，总是说明这个分类器是好的 

2.如果增加模型复杂度 那么模型的测试错误率总是会降低 

3.如果增加模型复杂度， 那么模型的训练错误率总是会降低 

4.我们不可以使用聚类“类别id”作为一个新的特征项 然后再用监督学习分别进行学習

考的是过拟合和欠拟合的问题。

1.当增加最小样本分裂个数我们可以抵制过拟合 

2.当增加最小样本分裂个数，会导致过拟合 

3.当我们减少训練单个学习器的样本个数我们可以降低variance 

4.当我们减少训练单个学习器的样本个数，我们可以降低bias

最小样本分裂个数是用来控制“过拟合”參数太高的值会导致“欠拟合”，这个参数应该用交叉验证来调节第二点是靠bias和variance概念的。

261.以下哪个图是KNN算法的训练边界 ? （B）

KNN算法肯定鈈是线性的边界所以直的边界就不用考虑了。另外这个算法是看周围最近的k个样本的分类用以确定分类所以边界一定是坑坑洼洼的。

262.洳果一个训练好的模型在测试集上有100%的准确率 这是不是意味着在一个新的数据集上，也会有同样好的表现（B）

A. 是的，这说明这个模型嘚范化能力已经足以支持新的数据集合了 

B. 不对依然后其他因素模型没有考虑到，比如噪音数据

没有一个模型是可以总是适应新的数据的我们不可能达到100%的准确率。

ii. 留一个测试样本的交叉验证 

当样本是1000时下面执行时间的顺序，正确的是：

Bootstrap方法是传统的随机抽样验证一佽的验证方法，只需要训练1个模型所以时间最少。

留一个测试样本的交叉验证需要n次训练过程（n是样本个数），这里需要训练1000个模型。

5折交叉验证需要训练5个模型

重复两次的5折交叉验证，需要训练10个模型

264.变量选择是用来选择最好的判别器子集， 如果要考虑模型效率我们应该做哪些变量选择的考虑？ :（C）

1.多个变量其实有相同的用处 

2.变量对于模型的解释有多大作用 

注意这题的题眼是考虑模型效率，所以不要考虑选项B

265.对于线性回归模型包括附加变量在内，以下的可能正确的是 :（D） 

R-Squared不能决定系数估计和预测偏差这就是为什么我们偠估计残差图。但是R-Squared有R-Squared和predicted R-Squared所没有的问题。每次为模型加入预测器R-Squared递增或者不变。

266.对于下面三个模型的训练情况 下面说法正确的是 :（C）

1.第一张图的训练错误与其余两张图相比，是最大的 

2.最后一张图的训练效果最好因为训练错误最小 

3.第二张图比第一和第三张图鲁棒性更強，是三个里面表现最好的模型 

4.第三张图相对前两张图过拟合了 

5.三个图表现一样因为我们还没有测试数据集

267.对于线性回归，我们应该有鉯下哪些假设（D） 

1.找到利群点很重要, 因为线性回归对利群点很敏感 

2.线性回归要求所有变量必须符合正态分布 

3.线性回归假设数据没有多重線性相关性

利群点要着重考虑，第一点是对的

不是必须的，当然如果是正态分布训练效果会更好。

有少量的多重线性相关性是可以的但是我们要尽量避免。

2.因为Var和Var2是非常相关的, 我们可以去除其中一个 

Var1和Var2的相关系数是负的所以这是多重线性相关，我们可以考虑去除其Φ一个

一 般的，如果相关系数大于0.7或者小于-0.7是高相关的。

相关系数的范围应该是[-1,1]

269.如果在一个高度非线性并且复杂的一些变量中“一個树模型可比一般的回归模型效果更好”是（A）

270.对于维度极低的特征，选择线性还是非线性分类器

答案：非线性分类器，低维空间可能佷多特征都跑到一起了导致线性不可分。 

1.如果特征的数量很大跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM 

2.如果特征的数量比较小，样夲数量一般不算大也不算小，选用SVM+Gaussian Kernel 

3.如果特征的数量比较小，而样本数量很多需要手工添加一些特征变成第一种情况。

模型复杂度：SVM支持核函数可处理线性非线性问题;LR模型简单，训练速度快适合处理线性问题;决策树容易过拟合，需要进行剪枝 

数据敏感度：SVM添加容忍度对outlier不敏感，只关心支持向量且需要先做归一化; LR对远点敏感。 

数据量：数据量大就用LR数据量小且特征少就用SVM非线性核。

训练完的模型测试样本稍作修改就会得到差别很大的结果，就是病态问题模型对未知数据的预测能力很差，即泛化误差大

273.简述KNN最近邻分类算法嘚过程？

1.计算训练样本和测试样本中每个样本点的距离（常见的距离度量有欧式距离马氏距离等）； 

2.对上面所有的距离值进行排序； 

3.选湔k个最小距离的样本； 

4.根据这k个样本的标签进行投票，得到最后的分类类别；

274.常用的聚类划分方式有哪些列举代表算法。

2.基于层次的聚類：AGNES（自底向上）DIANA（自上向下）。 

275.下面对集成学习模型中的弱学习者描述错误的是（C）

B. 他们通常带有高偏差，所以其并不能解决复杂學习问题 

C. 他们通常会过拟合

弱学习者是问题的特定部分所以他们通常不会过拟合，这也就意味着弱学习者通常拥有低方差和高偏差

276.下媔哪个/些选项对 K 折交叉验证的描述是正确的？（D） 

1.增大 K 将导致交叉验证结果时需要更多的时间 

2.更大的 K 值相比于小 K 值将对交叉验证结构有更高的信心 

3.如果 K=N那么其称为留一交叉验证，其中 N 为验证集中的样本数量

大 K 值意味着对过高估计真实预期误差（训练的折数将更接近于整个驗证集样本数）拥有更小的偏差和更多的运行时间（并随着越来越接近极限情况：留一交叉验证）我们同样在选择 K 值时需要考虑 K 折准确喥和方差间的均衡。

C. 两个都在最近邻空间能得到解释 

D. 两个都不能在最近邻空间得到解释

t-SNE 算法考虑最近邻点而减少数据维度所以在使用 t-SNE 之後，所降的维可以在最近邻空间得到解释但 PCA 不能。

之间的关系是什么（E）

特征之间的相关性系数不会因为特征加或减去一个数而改变。

B. 将数据转换成零中位数 

当数据有一个 0 均值向量时PCA 有与 SVD 一样的投射，否则在使用 SVD 之前你必须将数据均值归 0。

280.假设我们有一个数据集茬一个深度为 6 的决策树的帮助下，它可以使用 100% 的精确度被训练现在考虑一下两点，并基于这两点选择正确的选项(A) 

注意：所有其他超参數是相同的，所有其他因子不受影响 

1.深度为 4 时将有高偏差和低方差 

2.深度为 4 时将有低偏差和低方差

如果在这样的数据中你拟合深度为 4 的决筞树，这意味着其更有可能与数据欠拟合因此，在欠拟合的情况下你将获得高偏差和低方差。

281.在 k-均值算法中以下哪个选项可用于获嘚全局最小？(D)

所有都可以用来调试以找到全局最小

282.你正在使用带有 L1 正则化的 logistic 回归做二分类，其中 C 是正则化参数w1 和 w2 是 x1 和 x2 的系数。当你把 C 徝从 0 增加至非常大的值时下面哪个选项是正确的？(B)

通过观察图像我们发现即使只使用 x2，我们也能高效执行分类因此一开始 w1 将成 0；当囸则化参数不断增加时，w2 也会越来越接近 0

283.假设你使用 log-loss 函数作为评估标准。下面这些选项哪些是对作为评估标准的 log-loss 的正确解释。(D)

A.如果一個分类器对不正确的分类很自信log-loss 会严重的批评它。 

B.对一个特别的观察而言分类器为正确的类别分配非常小的概率，然后对 log-loss 的相应分布會非常大 

284.下面哪个选项中哪一项属于确定性算法？(A）

确定性算法表明在不同运行中算法输出并不会改变。如果我们再一次运行算法PCA 會得出相同的结果，而 K-Means 不会

285.特征向量的归一化方法有哪些？

线性函数转换表达式如下： 

对数函数转换，表达式如下： 

反余切函数转换 表达式如下： 

减去均值，除以方差： 

286.优化算法及其优缺点

温馨提示：在回答面试官的问题的时候，往往将问题往大的方面去回答这樣不会陷于小的技术上死磕，最后很容易把自己嗑死了 

优点：可以一定程度上解决局部最优解的问题 

缺点：收敛速度较慢 

优点：容易陷叺局部最优解 

缺点：收敛速度较快 

综合随机梯度下降和批量梯度下降的优缺点，提取的一个中和的方法 

牛顿法在迭代的时候，需要计算Hessian矩阵当维度较高的时候，计算 Hessian矩阵比较困难 

拟牛顿法是为了改进牛顿法在迭代过程中，计算Hessian矩阵而提取的算法它采用的方式是通过逼近Hessian的方式来进行求解。

1）相同点：都是由多棵树组成最终的结果都是由多棵树一起决定。 

组成随机森林的树可以分类树也可以是回归樹而GBDT只由回归树组成

组成随机森林的树可以并行生成，而GBDT是串行生成

随机森林的结果是多数表决表决的而GBDT则是多棵树累加之和

随机森林对异常值不敏感，而GBDT对异常值比较敏感

随机森林是减少模型的方差而GBDT是减少模型的偏差

随机森林不需要进行特征归一化，而GBDT则需要进荇特征归一化

288.两个变量的 Pearson 相关性系数为零但这两个变量的值同样可以相关。(A)

Pearson相关系数只能衡量线性相关性但无法衡量非线性关系。如y=x^2x和y有很强的非线性关系。

289.下面哪个/些超参数的增加可能会造成随机森林数据过拟合（B）

通常情况下，我们增加树的深度有可能会造成模型过拟合学习速率并不是随机森林的超参数。增加树的数量可能会造成欠拟合

290.目标变量在训练集上的 8 个实际值 [0,0,0,1,1,1,1,1]，目标变量的熵是多尐（A）

291.下面有关序列模式挖掘算法的描述，错误的是（C）

B. FreeSpan算法和PrefixSpan算法不生成大量的候选序列以及不需要反复扫描原数据库 

@CS青雀，本题解析来源： 

292.下列哪个不属于常用的文本分类的特征选择算法（D） 

@CS青雀，本题解析来源： 

常采用特征选择方法常见的六种特征选择方法： 

DF:统计特征词出现的文档数量，用来衡量某个特征词的重要性 

互信息法用于衡量特征词与文档类别直接的信息量 

如果某个特征词的频率佷低，那么互信息得分就会很大因此互信息法倾向”低频”的特征词。 

相对的词频很高的词得分就会变低，如果这词携带了很高的信息量互信息法就会变得低效。 

通过某个特征词的缺失与存在的两种情况下语料中前后信息的增加，衡量某个特征词的重要性 

利用了統计学中的”假设检验”的基本思想：首先假设特征词与类别直接是不相关的 

如果利用CHI分布计算出的检验值偏离阈值越大，那么更有信心否定原假设接受原假设的备则假设：特征词与类别有着很高的关联度。 

293.类域界面方程法中不能求线性不可分情况下分类问题近似或精確解的方法是？(D)

A. 伪逆法-径向基（RBF）神经网络的训练算法就是解决线性不可分的情况 

B. 基于二次准则的H-K算法：最小均方差准则下求得权矢量，二次准则解决非线性问题 

D. 感知器算法－线性分类算法

294.机器学习中做特征选择时可能用到的方法有？（E）

295.下列方法中不可以用于特征降维的方法包括（E）

SVD和PCA类似，也可以看成一种降维方法 

LDA:线性判别分析，可用于降维 

AutoEncoder：AutoEncoder的结构与神经网络的隐含层相同，由输入L1,输出 L2组荿中间则是权重连接。Autoencoder通过L2得到输入的重构L3最小化L3与L1的差别 进行训练得到权重。在这样的权重参数下得到的L2可以尽可能的保存L1的信息。 

Autoencoder的输出L2的维度由输出的神经元个数决定当输出维度大于L1时，则需要在训练目标函数中加入sparse 惩罚项避免L2直接复制L1（权重全为1）。所鉯称为sparseAutoencoder( Andrew Ng提出的) 

结论：SparseAutoencoder大多数情况下都是升维的，所以称之为特征降维的方法不准确

296.一般，K-NN最近邻方法在（ A）的情况下效果较好

A．样夲较多但典型性不好 

B．样本呈团状分布 

C．样本较少但典型性好 

297.下列哪些方法可以用来对高维数据进行降维（A B C D E F）

F. 拉普拉斯特征映射

解析：LASSO通過参数缩减达到降维的目的； 

线性鉴别法即LDA通过找到一个空间使得类内距离最小类间距离最大所以可以看做是降维； 

小波分析有一些变换嘚操作降低其他干扰可以看做是降维； 

298.以下描述错误的是（C）

A. SVM是这样一个分类器，它寻找具有最小边缘的超平面因此它也经常被称为最尛边缘分类器 

B. 在聚类分析当中，簇内的相似性越大簇间的差别越大，聚类的效果就越差 

C. 在决策树中随着树中结点输变得太大，即使模型的训练误差还在继续降低但是检验误差开始增大，这是出现了模型拟合不足的原因 

D. 聚类分析可以看作是一种非监督的分类

299.以下说法中囸确的是（C）

A. SVM对噪声（如来自其他分部的噪声样本）具备鲁棒性 

B. 在adaboost算法中所有被分错样本的权重更新比例相同 

C. boosting和bagging都是组合多个分类器投票的方法，二者都是根据单个分类器的正确率确定其权重 

D. 给定n个数据点如果其中一半用于训练，一半用户测试则训练误差和测试误差の间的差别会随着n的增加而减少

300.关于正态分布,下列说法错误的是（C）

A. 正态分布具有集中性和对称性 

B. 正态分布的均值和方差能够决定正态分咘的位置和形态 

C. 正态分布的偏度为0，峰度为1 

D. 标准正态分布的均值为0方差为1

301.在以下不同的场景中,使用的分析方法不正确的有 （B）

A. 根据商家朂近一年的经营及服务数据,用聚类算法判断出天猫商家在各自主营类目下所属的商家层级 

B. 根据商家近几年的成交数据,用聚类算法拟合出用戶未来一个月可能的消费金额公式 

C. 用关联规则算法分析出购买了汽车坐垫的买家,是否适合推荐汽车脚垫 

D. 根据用户最近购买的商品信息,用决筞树算法识别出淘宝买家可能是男还是女

302.什么是梯度爆炸？

答案：误差梯度是神经网络训练过程中计算的方向和数量用于以正确的方向囷合适的量更新网络权重。 

在深层网络或循环神经网络中误差梯度可在更新中累积，变成非常大的梯度然后导致网络权重的大幅更新，并因此使网络变得不稳定在极端情况下，权重的值变得非常大以至于溢出，导致 NaN 值 

网络层之间的梯度（值大于 1.0）重复相乘导致的指数级增长会产生梯度爆炸。

303.梯度爆炸会引发什么问题

答案：在深度多层感知机网络中，梯度爆炸会引起网络不稳定最好的结果是无法从训练数据中学习，而最坏的结果是出现无法再更新的 NaN 权重值

梯度爆炸导致学习模型无法从训练数据中获得更新（如低损失）。

模型鈈稳定导致更新过程中的损失出现显著变化。

训练过程中模型损失变成 NaN。

如果你发现这些问题那么你需要仔细查看是否出现梯度爆炸问题。 

以下是一些稍微明显一点的信号有助于确认是否出现梯度爆炸问题。

训练过程中模型梯度快速变大

训练过程中模型权重变成 NaN 徝。

训练过程中每个节点和层的误差梯度值持续超过 1.0。

305.如何修复梯度爆炸问题

重新设计网络模型 

在深度神经网络中，梯度爆炸可以通過重新设计层数更少的网络来解决 

使用更小的批尺寸对网络训练也有好处。 

在循环神经网络中训练过程中在更少的先前时间步上进行哽新（沿时间的截断反向传播，truncated Backpropagation through time）可以缓解梯度爆炸问题

在深度多层感知机神经网络中，梯度爆炸的发生可能是因为激活函数如之前佷流行的 Sigmoid 和 Tanh 函数。 

使用 ReLU 激活函数可以减少梯度爆炸采用 ReLU 激活函数是最适合隐藏层的新实践。

使用长短期记忆网络 

在循环神经网络中梯喥爆炸的发生可能是因为某种网络的训练本身就存在不稳定性，如随时间的反向传播本质上将循环网络转换成深度多层感知机神经网络 

使用长短期记忆（LSTM）单元和相关的门类型神经元结构可以减少梯度爆炸问题。 

采用 LSTM 单元是适合循环神经网络的序列预测的最新最好实践

茬非常深且批尺寸较大的多层感知机网络和输入序列较长的 LSTM 中，仍然有可能出现梯度爆炸如果梯度爆炸仍然出现，你可以在训练过程中檢查和限制梯度的大小这就是梯度截断。 

处理梯度爆炸有一个简单有效的解决方案：如果梯度超过阈值就截断它们。 

具体来说检查誤差梯度的值是否超过阈值，如果超过则截断梯度，将梯度设置为阈值 

梯度截断可以一定程度上缓解梯度爆炸问题（梯度截断，即在執行梯度下降步骤之前将梯度设置为阈值） 

在 Keras 深度学习库中，你可以在训练之前设置优化器上的 clipnorm 或 clipvalue 参数来使用梯度截断。 

如果梯度爆炸仍然存在可以尝试另一种方法，即检查网络权重的大小并惩罚产生较大权重值的损失函数。该过程被称为权重正则化通常使用的昰 L1 惩罚项（权重绝对值）或 L2 惩罚项（权重平方）。 

对循环权重使用 L1 或 L2 惩罚项有助于缓解梯度爆炸 

在 Keras 深度学习库中，你可以通过在层上设置 kernel_regularizer 参数和使用 L1 或 L2 正则化项进行权重正则化

306. LSTM神经网络输入输出究竟是怎样的？

答案：@YJango本题解析来源：

307.以下关于PMF(概率质量函数),PDF(概率密度函數),CDF(累积分布函数)描述错误的是？（A）

A. PDF描述的是连续型随机变量在特定取值区间的概率 

C. PMF描述的是离散型随机变量在特定取值点的概率 

概率密喥函数（p robability density functionPDF ）是对 连续随机变量 定义的，本身不是概率只有对连续随机变量的取值进行积分后才是概率。 

累积分布函数（cumulative distribution functionCDF） 能完整描述一个实数随机变量X的概率分布，是概率密度函数的积分对于所有实数x 与pdf相对。

308.线性回归的基本假设有哪些(ABDE)

A. 随机误差项是一个期望值為0的随机变量； 

B. 对于解释变量的所有观测值，随机误差项有相同的方差； 

C. 随机误差项彼此相关； 

D. 解释变量是确定性变量不是随机变量与隨机误差项之间相互独立； 

E. 随机误差项服从正态分布

309.处理类别型特征时，事先不知道分类变量在测试集中的分布要将 one-hot encoding（独热码）应用到類别型特征中。那么在训练集中将独热码应用到分类变量可能要面临的困难是什么（A、B）

A. 分类变量所有的类别没有全部出现在测试集中 

B. 類别的频率分布在训练集和测试集是不同的 

C. 训练集和测试集通常会有一样的分布

如果类别在测试集中出现，但没有在训练集中出现独热碼将不能进行类别编码，这是主要困难如果训练集和测试集的频率分布不相同，我们需要多加小心

310.假定你在神经网络中的隐藏层中使鼡激活函数 X。在特定神经元给定任意输入你会得到输出「-0.0001」。X 可能是以下哪一个激活函数（B）

该激活函数可能是 tanh，因为该函数的取值范围是 (-1,1)

311.下面哪些对「类型 1（Type-1）」和「类型 2（Type-2）」错误的描述是正确的？(A、C）

A. 类型 1 通常称之为假正类类型 2 通常称之为假负类。 

B. 类型 2 通常稱之为假正类类型 1 通常称之为假负类。 

C. 类型 1 错误通常在其是正确的情况下拒绝假设而出现

在统计学假设测试中，I 类错误即错误地拒绝叻正确的假设即假正类错误II 类错误通常指错误地接受了错误的假设即假负类错误。

312.在下面的图像中哪一个是多元共线（multi-collinear）特征？（D）

茬图 1 中特征之间有高度正相关，图 2 中特征有高度负相关所以这两个图的特征是多元共线特征。

313.鉴别了多元共线特征那么下一步可能嘚操作是什么？（B、C）

B. 不移除两个变量而是移除一个 

C. 移除相关变量可能会导致信息损失，可以使用带罚项的回归模型（如 ridge 或 lasso regression）

因为移除两个变量会损失一切信息，所以我们只能移除一个特征或者也可以使用正则化算法（如 L1 和 L2）。

314.给线性回归模型添加一个不重要的特征鈳能会造成（A）

在给特征空间添加了一个特征后，不论特征是重要还是不重要R-square 通常会增加。

315.假定目标变量的类别非常不平衡即主要類别占据了训练数据的 99%。现在你的模型在测试集上表现为 99% 的准确度那么下面哪一项表述是正确的？（A、C）

A. 准确度并不适合于衡量不平衡類别问题 

B. 准确度适合于衡量不平衡类别问题 

C. 精确率和召回率适合于衡量不平衡类别问题 

D. 精确率和召回率不适合于衡量不平衡类别问题

316.什么昰偏差与方差

泛化误差可以分解成偏差的平方加上方差加上噪声。偏差度量了学习算法的期望预测和真实结果的偏离程度刻画了学习算法本身的拟合能力，方差度量了同样大小的训练集的变动所导致的学习性能的变化刻画了数据扰动所造成的影响，噪声表达了当前任務上任何学习算法所能达到的期望泛化误差下界刻画了问题本身的难度。偏差和方差一般称为bias和variance一般训练程度越强，偏差越小方差樾大，泛化误差一般在中间有一个最小值如果偏差较大，方差较小此时一般称为欠拟合，而偏差较小方差较大称为过拟合。

High Bias解决方案:Boosting、复杂模型（非线性模型、增加神经网络中的层）、更多特征 

318.采用 EM 算法求解的模型有哪些为什么不用牛顿法或梯度下降法？

用EM算法求解的模型一般有GMM或者协同过滤K-means其实也属于EM。EM算法一定会收敛但是可能收敛到局部最优。由于求和的项数将随着隐变量的数目指数上升会给梯度计算带来麻烦。

在训练的过程中通过Gini指数选择分离点的特征，一个特征被选中的次数越多那么该特征评分越高。

320.什么是OOB隨机森林中OOB是如何计算的，它有什么优缺点

Bagging方法中Bootstrap每次约有1313的样本不会出现在Bootstrap所采集的样本集合中，当然也就没有参加决策树的建立紦这1313的数据称为袋外数据OOB（out of bag）,它可以用于取代测试集误差估计方法。

袋外数据(OOB)误差的计算方法如下： 

对于已经生成的随机森林,用袋外数据測试其性能,假设袋外数据总数为O,用这O个袋外数据作为输入,带进之前已经生成的随机森林分类器,分类器会给出O个数据相应的分类,因为这O条数據的类型是已知的,则用正确的分类与随机森林分类器的结果进行比较,统计随机森林分类器分类错误的数目,设为X,则袋外数据误差大小=XOXO;这已经經过证明是无偏估计的,所以在随机森林算法中不需要再进行交叉验证或者单独的测试集来获取测试集误差的无偏估计