机器学习问题总结 - WenlSun的博客

逻辑回归

逻辑回归虽然被称为是回归，但实际上是分类模型，常用于二分类，逻辑回归因其简单、可并行化、可解释性强深受工业届喜欢。逻辑回归假设数据服从伯努利分布，通过极大化似然函数的方法，运用梯度下降来求解参数，来实现对数据进行二分类的问题。

逻辑回归的基本假设

逻辑回归的第一个基本假设是假设数据服从伯努利分布。在逻辑回归模型中，假设$h_\theta(x)$为样本为正的概率，$1-h_\theta(x)$为样为负的概率，则整个模型可以表示为$h_\theta(x;\theta) = p$。逻辑回归的第二个假设是假设样本为正的概率是$p = \frac{1}{1+e^{-\theta^Tx}}$。所以逻辑回归的最终形式是$h_\theta(x;\theta) =\frac{1}{1+e^{-\theta^Tx}}$。

逻辑回归的损失函数

逻辑回归的损失函数的通过极大似然估计推导出来的，其形式是对数损失函数，所以从损失函数的角度来看，逻辑回归的损失函数就是对数损失函数。

\[L_\theta\left(x\right )= \prod _{i=1}^{m}h_\theta(x^{i};\theta )^{y{i}}*(1-h_\theta(x^{i};\theta))^{1-y^{i}}\]

逻辑回归为什么不用均方误差作为损失函数，而是使用极大似然函数求解参数？

其一是因为如果你使用平方损失函数，会发现梯度更新的速度和sigmod函数本身的梯度是很相关的。sigmod函数在它在定义域内的梯度都不大于0.25。这样训练会非常的慢。
其二是在使用 Sigmoid 函数作为正样本的概率时，同时将平方损失作为损失函数，这时所构造出来的损失函数是非凸的，不容易求解，容易得到其局部最优解。
而如果使用极大似然，其目标函数就是对数似然函数，该损失函数是关于未知参数的高阶连续可导的凸函数，便于求其全局最优解，而且对数损失函数的梯度更新和sigmod函数本身的梯度是无关的，这样更新的速度是可以自始至终都比较的稳定，其求解参数的速度是比较快的。对数损失函数的梯度更新公式

\[\theta _j=\theta _j-\left ( y^{i} -h_\theta (x^{i};\theta ) \right )\ast x^{i}_j\]

逻辑回归的求解方法

由于该极大似然函数无法直接求解，我们一般通过对该函数进行梯度下降来不断逼急最优解。常用的有随机梯度下降算法、批梯度下降算法和小批量梯度下降算法。

简单来说批梯度下降会获得全局最优解，缺点是在更新每个参数的时候需要遍历所有的数据，计算量会很大，并且会有很多的冗余计算，导致的结果是当数据量大的时候，每个参数的更新都会很慢。
随机梯度下降是以高方差频繁更新，优点是使得sgd会跳到新的和潜在更好的局部最优解，缺点是使得收敛到局部最优解的过程更加的复杂。
小批量梯度下降结合了随机梯度下降算法和批梯度下降算法的优点，每次更新的时候使用n个样本。减少了参数更新的次数，可以达到更加稳定收敛结果，一般在深度学习当中我们采用这种方法。

逻辑回归的手推以及简单的代码实现

逻辑回归（LR）公式推导及代码实现逻辑回归是用来解决分类问题用的，与线性回归不同的是，逻辑回归输出的不是具体的值，而是一个概率。除去了sigmoid函数的逻辑归回和线性回归几乎是一样的。

import numpy as np
import matplotlib.pyplot as plt


def sigmoid(x):
    return 1.0 / (1 + np.exp(-x))

# 训练
def train(data_set, label, alpha=0.01, max_epoch=10):
    data_set = np.mat(data_set)
    m, n = data_set.shape
    W = np.ones((n, 1))
    for e in range(max_epoch):
        h = sigmoid(data_set * W)
        err = h - label
        print("err: ", err)
        W = W - alpha * data_set.transpose() * err
    return W

# 测试
def test(W, x, th=0.5):
    return sigmoid(W.transpose() * x) > th


if __name__ == "__main__":
    data = np.random.rand(1000,5)
    label = np.vstack([np.ones((600,1)),np.zeros((400,1))])
    print(data.shape)
    print(label.shape)
    W = train(data,label)
    print(W.shape)
    test_data = np.random.rand(5,1)
    res = test(W,test_data)
    print(res)

逻辑回归的目的

逻辑回归的目的是对数据进行二分类。逻辑回归作为一个回归(也就是y值是连续的)，如何应用到分类上去呢。y值确实是一个连续的变量。逻辑回归的做法是划定一个阈值，y值大于这个阈值的是一类，y值小于这个阈值的是另外一类。阈值具体如何调整根据实际情况选择。一般会选择0.5做为阈值来划分。

逻辑回归如何解决多分类问题？

把sigmoid函数换成softmax函数，即可适应多分类场景，softmax回归是直接把逻辑回归在多分类的推广，相应的模型也可以叫做多元逻辑回归，当多分类的k=2时。与使用sigmoid二分类一致。

逻辑回归如何解决线性不可分问题？

逻辑回归的本质是一个线性模型，可以通过两种方式实现非线性数据的分类。

利用特殊核函数对特征进行变换，把低维空间线性不可分的数据转换到高维空间线性可分。
扩展逻辑回归算法，提出FM算法：可以通过在基本线性回归模型的基础上引入交叉项，实现非线性分类。

特征交叉的作用

引入特征之间的交互，即引入非线性，增强模型的表达能力。

如何选择LR和SVM？

n是feature的数量 m是样本数

如果n相对于m来说很大，则使用LR算法或者不带核函数的SVM（线性分类）n远大于m，n=10000，m=10-1000
如果n很小，m的数量适中（n=1-1000，m=10-10000）使用带有核函数的SVM算法
如果n很小，m很大（n=1-1000，m=50000+）增加更多的feature然后使用LR算法或者不带核函数的SVMLR和不带核函数的SVM比较类似。

逻辑回归在训练的过程当中，如果有很多的特征高度相关或者说有一个特征重复了100遍，会造成怎样的影响？

先说结论，如果在损失函数最终收敛的情况下，其实就算有很多特征高度相关也不会影响分类器的效果。但是对特征本身来说的话，假设只有一个特征，在不考虑采样的情况下，你现在将它重复100遍。训练完以后，数据还是这么多，但是这个特征本身重复了100遍，实质上将原来的特征分成了100份，每一个特征都是原来特征权重值的百分之一。如果在随机采样的情况下，其实训练收敛完以后，还是可以认为这100个特征和原来那一个特征扮演的效果一样，只是可能中间很多特征的值正负相消了。

为什么我们还是会在训练的过程当中将高度相关的特征去掉？

去掉高度相关的特征会让模型的可解释性更好;
可以大大提高训练的速度，如果模型当中有很多特征高度相关的话，就算损失函数本身收敛了，但实际上参数是没有收敛的，这样会拉低训练速度。其次是特征多了，本身就会增大训练时间。

逻辑回归为什么要对特征进行离散化？

在工业界，很少直接将连续值作为特征喂给逻辑回归模型，而是将连续特征离散化为一系列0、1特征交给逻辑回归模型，这样做的优势有以下几点：

稀疏向量内积乘法运算速度快，计算结果方便存储，容易扩展。
离散化后的特征对异常数据有很强的鲁棒性。比如一个特征是年龄>30是1，否则0。如果特征没有离散化，一个异常数据“年龄300岁”会给模型造成很大的干扰。
逻辑回归属于广义线性模型，表达能力受限，单变量离散化为N个后，每个变量有单独的权重，相当于为模型引入了非线性，能够提升模型的表达能力，加大拟合。
离散化后可以进行特征交叉(特征组合)，由$M+N$个变量变为$M\times N$个变量，进一步引入非线性，提升表达能力。
特征离散化后，模型会更加稳定。如如果对用户年龄离散化，20-30作为一个区间，不会因为一个用户年龄长了一岁就变成一个完全不同的人。

总结：（1）计算简单；（2）简化模型；（3）增强模型的泛化能力，不受噪声的影响。

在逻辑回归模型中，为什么常常需要做特征交叉(特征组合)？

逻辑回归模型属于线性模型，线性模型不能很好的处理非线性特征，特征组合可以引入非线性特征，提升了模型的表达能力。另外，基本特征可以认为是全局建模，组合特征更加精细，是个性化建模，但对全局建模会对部分样本有偏，对每一个样本建模又会导致数据爆炸、过拟合，所以基本特征+特征组合兼顾了全局和个性化。

逻辑回归模型是线性模型吗？

逻辑回归模型是一种广义线性模型，它虽然引入了sigmoid函数，是非线性模型，但是本质上还是一个线性回归模型。
逻辑回归和线性回归首先都是广义的线性回归，在本质上没多大区别，区别在于逻辑回归多了个Sigmod函数，使样本映射到[0,1]之间的数值，从而来处理分类问题。另外逻辑回归是假设变量服从伯努利分布，线性回归假设变量服从高斯分布。逻辑回归输出的是离散型变量，用于分类，线性回归输出的是连续性的，用于预测。逻辑回归是用最大似然法去计算预测函数中的最优参数值，而线性回归是用最小二乘法去对自变量因变量关系进行拟合。

逻辑回归模型的输出值的实际意义是什么？

只有在满足： y服从伯努利分布；η和x之间存在线性关系时，输出值才是概率值。不满足的情况下，得到的输出值，只是置信度。假设 y 是一个服从伯努利分布的二值随机变量。该分布的参数为$\Phi = P(y=1)$。伯努利分布属于指数家族的一种情况，指数分布家族的形式为：$P(x|\eta)=h(x)exp(\eta^TT(x)-A(\eta))$ 它告诉我们：对于随机变量x，只要确定三个函数$h(x)$、$T(x)$、$A(\eta)$，就可以确定一类分布。 $\eta$用来确定该类分布的具体参数。从伯努利分布出发，可变形到与指数分布族一样的形式： $P(y;\Phi) = \Phi^y(1-\Phi)^{1-y}\\=exp(log\Phi^y(1-\Phi)^{1-y}\\=exp(ylog\Phi+(1-y)(1-\Phi)\\=exp(log\frac{\Phi}{1-\Phi}y+log(1-\Phi))$

对应上面提到的三个函数：

\[A(\eta)=-log(1-\Phi)=log(1+e^\eta)\\h(y) = 1\\T(y) = y\]

$\eta$和$\Phi$之间的关系：

\[\eta = log\frac{\Phi}{1-\Phi}\\\Phi = \frac{1}{1+e^{-\eta}}\]

因此，伯努利分布可以改写为指数分布族的形式，而且，伯努利分布的参数$\Phi$与$\eta$之间，还满足sigmoid函数的关系。如果能找到x和$\eta$之间的关系，就找到了x和$\Phi$之间的关系。假设$\eta$和x之间存在线性的关系，即：$\eta = \theta x$。将$\Phi$作为预测值。$\Phi$既是伯努利分布的唯一参数，也是该分布的期望，也是逻辑回归的输出。至此，找到了我们要用的模型的样子，也就是逻辑回归。

如果你的情况满足上面所说的两个假设，那么你训练模型的过程，就确实是在对概率进行建模。但是这两个假设并不是那么容易满足的。所以，很多情况下，我们得出的逻辑回归输出值，无法当作真实的概率，只能作为置信度来使用。

逻辑回归模型的优缺点(偏向工业界)

优点

形式简单，模型的可解释性非常好。从特征的权重可以看到不同的特征对最后结果的影响，某个特征的权重值比较高，那么这个特征最后对结果的影响会比较大。
模型效果不错。在工程上是可以接受的，如果特征工程做的好，效果不会太差，并且特征工程可以大家并行开发，大大加快开发的速度。
训练速度较快。分类的时候，计算量仅仅只和特征的数目相关。并且逻辑回归的分布式优化sgd发展比较成熟，训练的速度可以通过堆机器进一步提高，这样我们可以在短时间内迭代好几个版本的模型。
资源占用小,尤其是内存。因为只需要存储各个维度的特征值。
方便输出结果调整。逻辑回归可以很方便的得到最后的分类结果，因为输出的是每个样本的概率分数(置信度)。

缺点

准确率并不是很高。因为形式非常的简单(非常类似线性模型)，很难去拟合数据的真实分布。
很难处理数据不平衡的问题。
处理非线性数据较麻烦。逻辑回归在不引入其他方法的情况下，只能处理线性可分的数据，或者进一步说，处理二分类的问题。
逻辑回归本身无法筛选特征。有时候，我们会用gbdt来筛选特征，然后再上逻辑回归。

正则化

正则化是一个通用的算法和思想，所有会产生过拟合现象的算法都可以使用正则化来避免过拟合。在经验风险最小化的基础上（也就是训练误差最小化），尽可能采用简单的模型，可以有效提高泛化预测精度。如果模型过于复杂，变量值稍微有点变动，就会引起预测精度问题。正则化之所以有效，就是因为其降低了特征的权重，使得模型更为简单。正则化一般会采用 $L_1$ 范式或者 $L_2$ 范式。

$L_1$正则化 (Lasso回归)

相当于为模型添加了一个先验知识，即w服从零均值拉普拉斯分布

\[f(w|\mu,b)=\frac{1}{2b}exp(-\frac{|w-\mu|}{b})\]

由于引入了先验，似然函数变为

取 log 再取负，得到目标函数

等价于原始损失函数的后面加上了 $L_1$ 正则，因此 $L_1$ 正则的本质其实是为模型增加了“模型参数服从零均值拉普拉斯分布”这一先验知识。

$L_2$正则化 (岭回归)

相当于为模型添加了一个先验知识：即 w 服从零均值正态分布。

由于引入了先验知识，所以似然函数这样写：

取 ln 再取负，得到目标函数：

等价于原始的损失函数后面加上了 $L_2$正则，因此 $L_2$ 正则的本质其实是为模型增加了模型参数服从零均值正态分布这一先验知识。

$L_1$和$L_2$正则化的区别

$L_1$ 正则化增加了所有权重 w 参数的绝对值之和逼迫更多 w 为零，也就是变稀疏。我们对稀疏规则趋之若鹜的一个关键原因在于它能实现特征的自动选择。一般来说，大部分特征 $x_i$ 都是和最终的输出 $y_i$ 没有关系或者不提供任何信息的。在最小化目标函数的时候考虑 $x_i$ 这些额外的特征，虽然可以获得更小的训练误差，但在预测新的样本时，这些没用的特征权重反而会被考虑，从而干扰了对正确 $y_i$ 的预测。$L_1$ 正则化的引入就是为了完成特征自动选择的光荣使命，它会学习地去掉这些无用的特征，也就是把这些特征对应的权重置为0。

$L_2$正则化中增加所有权重 w 参数的平方之和，逼迫所有 w 尽可能趋向零但不为零（$L_2$的导数趋于零）。因为在未加入 $L_2$正则化发生过拟合时，拟合函数需要顾忌每一个点，最终形成的拟合函数波动很大，在某些很小的区间里，函数值的变化很剧烈，也就是某些 w 值非常大。为此，$L_2$正则化的加入就惩罚了权重变大的趋势。

$L_1$正则化指权值向量中各个元素的绝对值之和，$L_2$正则化是指权值向量中各个元素的平方和再求平方根。$L_1$正则会产生稀疏解，$L_2$正则会产生比较小的解。以二维为例，$L_1$正则化项和误差项的交点常出现在坐标轴上，是个菱形，$w_1$或$w_2$为0，即权值向量中有零值元素，而$L_2$正则化项与误差项的交点常出现在某个象限中，是个圆，$w_1$和$w_2$均非0。

工程上，怎么实现逻辑回归的并行化？有哪些并行化工具？

逻辑回归的并行化最主要的就是对目标函数梯度计算的并行化。目标函数的梯度向量计算中只需要进行向量间的点乘和相加，可以很容易将每个迭代过程拆分成相互独立的计算步骤，由不同的节点进行独立计算，然后归并计算结果。算法的并行化有两种：无损并行化和有损并行化。基于Batch的算法(Batch-GD, LBFGS, OWLQN)都是可以进行无损的并行化的。而基于SGD的算法（Ad Predictor， FTRL－Proximal）都只能进行有损的并行化。

无损的并行化：算法天然可以并行，并行只是提高了计算的速度和解决问题的规模，但和正常执行的结果是一样的。
有损的并行化：算法本身不是天然并行的，需要对算法做一些近似来实现并行化，这样并行化之后的双方和正常执行的结果并不一致，但是相似的。

并行化的工具有MPI和OpenMP。

逻辑回归与其他模型的比较

与线性回归模型

逻辑回归是在线性回归的基础上加了一个 sigmoid 函数（非线形）映射，使得逻辑回归称为了一个优秀的分类算法。本质上来说，两者都属于广义线性模型，但他们两个要解决的问题不一样，逻辑回归解决的是分类问题，输出的是离散值，线性回归解决的是回归问题，输出的连续值。

sigmoid的作用：

线性回归是在实数域范围内进行预测，而分类范围则需要在 [0,1]，逻辑回归减少了预测范围；
线性回归在实数域上敏感度一致，而逻辑回归在 0 附近敏感，在远离 0 点位置不敏感，这个的好处就是模型更加关注分类边界，可以增加模型的鲁棒性。

与最大熵模型

逻辑回归和最大熵模型本质上没有区别，最大熵在解决二分类问题时就是逻辑回归，在解决多分类问题时就是多项逻辑回归。

与SVM模型

相同点：

都是分类算法，本质上都是寻找划分超平面
都是监督学习算法
都是判别式模型
都可以通过核技巧的方法对非线性情况进行分类
都能减少离群点的影响

不同点：

损失函数不同，LR是对数损失函数，SVM是合页损失函数。
LR对异常值敏感，SVM对异常值不敏感。解释：支持向量机只考虑局部的边界线附近的点，而逻辑回归考虑全局。LR模型找到的那个超平面，是尽量让所有点都远离他，而SVM寻找的那个超平面，是只让最靠近中间分割线的那些点尽量远离，即只用到那些支持向量的样本。支持向量机改变非支持向量样本并不会引起决策面的变化。逻辑回归中改变任何样本都会引起决策面的变化。
对非线性问题的处理方式不同。解释：LR主要通过特征构造，特征组合(特征交叉)、特征离散化来处理非线性问题。SVM通常采用核函数来高效处理非线性问题。
理论基础不一样。LR基于统计，而SVM基于严格的数学推导。
输出不同。LR可以对每个样本点给出类别判断的概率值(或置信度)，SVM无法做到。
计算复杂度不同。对于海量数据，SVM的效率较低，LR的效率比较高。解释：当样本较少，特征维数较低时，SVM和LR的运行时间均比较短，SVM较短一些。准确率的话，LR明显比SVM要高。当样本稍微增加些时，SVM运行时间开始增长，但是准确率赶超了LR。SVM时间虽长，但在可接受范围内。当数据量增长到20000时，特征维数增长到200时，SVM的运行时间剧烈增加，远远超过了LR的运行时间。但是准确率却和LR相差无几。(这其中主要原因是大量非支持向量参与计算，造成SVM的二次规划问题)
防止过拟合的能力不同。解释：SVM模型中内含了L2正则，可有效防止过拟合。LR要自己添加正则项。
对数据要求不同。解释：SVM依赖于数据表达出的距离测度，所以需要对数据进行标准化处理，而LR不需要。
SVM会用核函数而LR一般不用核函数。
SVM自带结构风险最小化，LR则是经验风险最小化。

支持向量机

SVM总结

SVM的原理

支持向量机是一种二分类模型，它的基本模型是在特征空间中寻找间隔最大化的分离超平面的线性分类器。学习策略是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。

当训练数据线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机。
当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机。
当训练数据线性不可分时，通过使用核技巧以及软间隔最大化，学习一个非线性支持向量机。

SVM为什么采用间隔最大化？

当训练数据线性可分时，就会存在无数个分离超平面可以将训练数据正确分开 (感知机模型)。
线性可分支持向量机利用间隔最大化求得最优分离超平面，这时，解释唯一的。
另一方面，通过最大化间隔求得的分离超平面所产生的的分类结果是最鲁棒的，对未知实例的泛化能力最强。

可以借此机会阐述一下几何间隔以及函数间隔的关系。

SVM推导中的函数间隔和几何间隔

函数间隔

几何间隔

SVM的推导？

函数间隔 -> 几何间隔 -> 几何间隔最大化 -> 函数间隔最大化 -> 拉格朗日函数 -> 求解对偶问题 -> SMO算法手推！！！

线性可分 - 硬间隔最大化 - 线性可分支持向量机线性近似可分 - 软间隔最大化 - 线性可分支持向量机线性不可分 - 核函数 - 非线性支持向量机

SVM为什么转换为对偶问题求解？

转换对偶问题求解减少算法复杂度，使得算法更高效，从求解w,b转换成求解$\alpha$；
不等式约束是优化问题中的难点，求解对偶问题可以将支持向量机原问题中的不等式约束转换成等式约束；
支持向量机在解决非线性可分问题时，需要将数据映射到高维空间，但映射函数的具体形式不容易确定，而转换成对偶问题时，可以使用核函数来解决这个问题。

SVM 为什么要引入核函数？

当样本在原始空间线性不可分时，可将样本从原始空间映射到一个更高维的特征空间，使得样本在高维特征空间内线性可分。
引入这样的映射后，在所要求解的对偶问题的求解中，无需求解真正的映射函数，而只需要知道其核函数。
核函数的引入避免了“维数灾难”，大大减小了计算量。
无需知道非线性变换函数$\Phi$的形式和参数，只需要给定具体的核函数即可，这样使得求解的难度大大降低。
核函数的形式和参数变换会隐式的改变从输入空间到特征空间的映射，进而对特征空间的性质产生影响，最终改变各种核函数方法的性能。

SVM核函数的选择依据，以及各种核函数的区别？

一般选择线性核和高斯核，也就是线性核和RBF核。需要注意的是需要对数据归一化处理。

线性核：主要用于线性可分的情形，参数少，速度快，对于一般数据，分类效果已经很理想了。
RBF核：主要用于线性不可分的情形。参数多，分类结果非常依赖于参数。可通过交叉验证来寻找合适的参数，不过这个过程比较耗时。如果特征的数量很大，跟样本数量差不多，这时候选用线性核的SVM；如果特征的数量比较小，样本数量一般，不算大也不算小，选用高斯核的SVM。
对于某些参数，RBF和sigmoid具有相似的性能。
其他核函数：cosin核，Chi-squared核。

SVM如何处理多分类问题？

一般有两种做法：一种是直接法，直接在目标函数上修改，将多个分类面的参数求解合并到一个最优化问题里面，看似简单但是计算量却非常的大。另外一种做法是间接法：对训练器进行组合。其中比较典型的有一对一，和一对多。

一对多：就是对每个类都训练出一个分类器，由于svm是二分类，因此将目标类作为一类，其余类作为另外一类。这样针对k个类可以训练出k个分类器，当有一个新的样本来的时候，用这k个分类器来测试，哪个分类器的概率高，那么这个样本就属于哪一类。这种方法效果不太好，bias比较高。
一对一：针对任意两个类训练出一个分类器，如果有k类，一共训练出C(2,k) 个分类器，这样当有一个新的样本要来的时候，用这C(2,k)个分类器来测试，每当被判定属于某一类的时候，该类就加一，最后票数最多的类别被认定为该样本的类。

SVM的主要优势、特点

泛化性能比较好，不容易过拟合(合页损失函数+自带正则)。
可以在较少的数据下取得较好的性能(支持向量)。
存在全局最优解 (严格数学推导, 凸二次规划问题)。
存在高效实现的训练算法(SMO算法)。
可以使用核技巧处理非线性问题。
SVM的最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。

SVM的主要缺点

SVM算法对大规模训练样本难以实施，速度慢。
用SVM解决多分类问题存在困难。
对缺失数据(缺失的特征数据)敏感，对参数和核函数的选择敏感。

为什么SVM对缺失数据敏感？

这里说的缺失数据是指缺失某些特征数据、向量数据不完整。
因为SVM没有处理缺失值的策略，而SVM希望样本在特征空间线性可分，所以特征空间的好坏对SVM的性能很重要，缺失特征数据将影响训练结果的好坏。

SMO算法的求解对偶问题流程？

SMO算法是一种启发式算法，其基本思路是：如果所有变量都满足此优化问题的KKT条件，那么这个最优化问题的解就得到了(因为KKT条件是该最优化问题的充分必要条件)。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题，这时构建的这个子问题可以通过解析方法求解，大大提高了算法的计算速度，子问题有两个变量，一个是违反KKT最严重的那一个，另一个是由约束条件自动确定。SMO包括两部分：求解两个变量的二次规划的解析方法和选择变量的启发式方法。

变量的选择方法：

第一个变量的选择：SMO称第一个变量选择过程为外层循环，选取最违反KKT条件的样本点，在检验过程中，先遍历所有满足条件的$0\le \alpha_i \le C$的样本点(即在间隔边界上的支持向量点)，检验是否满足KKT条件，如果都满足，那么遍历整个训练集。检验他们是否满足KKT条件。
第二个变量的选择：称为为内层循环，选择标准为希望能使$\alpha_2$有足够大的变化，一种简单的做法是选择$\alpha_2$,使其对应的|$E_1-E_2$|最大。在特殊情况下，若以上方法找不到$\alpha_2$，则遍历间隔边界上的支持向量点，依次将其对应的变量作为$\alpha_2$试用，直到目标函数有足够的的下降。若找不到合适的$\alpha_2$,那么遍历整个训练集，若仍找不到，则放弃$\alpha_1$,重新找$\alpha_1$。

SMO算法不断地将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，知道所有的变量满足KKT条件为止，因为子问题有解析解，所以每次计算子问题都很快，虽然计算子问题的次数很多，但总体还是高效的。

SVM和逻辑回归的异同

相同点：

LR和SVM都是分类算法
LR和SVM都是监督学习算法
LR和SVM都是判别式模型
如果不考虑核函数，LR和SVM都是线性分类算法，即他们的分类决策面是线性的。(注意：LR也可以核化，但是计算量太大，一般不这么做)

不同点：

LR采用-log损失(对数损失函数)，SVM采用合页损失函数(hinge)
LR对异常值敏感，SVM对异常值不敏感
计算复杂度不同，对于海量数据，SVM效率较低，LR效率较高
对于非线性问题的处理方式不同
SVM的损失自带正则
SVM自带结构风险最小化，LR则是经验风险最小化。
SVM一般会使用核函数，LR一般不使用核函数。

决策树

[决策树（Decision Tree）-ID3、C4.5、CART比较]

什么是决策树？简述决策树的原理

决策树是一种基本的分类回归方法，可以从三个层面理解它：

决策树模型是一种描述对实例进行分类和回归的树型结构，由结点和有向边组成，内部结点表示一个特征或属性，叶结点表示一个类。
可以将决策树看成是一个if-then规则的集合，从根节点到叶结点的每一条路径构建一条规则，叶结点的类对应着规则的结论。这个规则集合互斥并完备。
还可以将决策树表示为给定条件下类的条件概率分布，这个概率分布是定义在特征空间上的一个划分上。将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布就构成一个条件概率分布。决策树的一条路径对应于划分中的一个单元，决策树所表示的条件概率分布由各个单元给定条件下的类的条件概率分布组成。决策树分类预测时将该节点的实例强行分到条件概率大的那一类去。

简述决策树的构建过程和学习过程

决策树学习的算法通常是一个递归地选择最优特征并根据该特征对训练数据集进行分割，使得对各个子数据集有一个最好的分类的过程。开始，构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按照这一特征将训练数据分割成子集，使得各个子集在当前条件下有一个最好的分类，如果这些子集已经基本被正确分类，那么构建叶子结点，并将这些子集分到所对应的叶子结点中去，如果还有子集不能被正确分类，则对这些子集选择新的最优特征，继续对其进行分割，构建结点，递归这一过程，直到所有子集都基本被正确分类，或没有合适的特征可供选择时，则停止，最后，每个子集都有了明确的类别标签。

决策树学习的本质上是从训练数据集中归纳出一组分类规则，它是一个与训练数据有较小矛盾，同时在具有很好的泛化能力的决策树。从另一个角度来看，决策树学习是由训练数据集估计条件概率模型。决策树学习的损失函数通常是正则化的极大似然函数，决策树学习的策略是以损失函数为目标函数的最小化。

如果特征数量很多时，可以在决策树学习的开始时，对特征进行选择，只留下对训练数有足够分类能力的特征。

决策树生成的迭代终止条件

子节点中的样本属于同一类
该子节点没有样本了
特征已经用完了

如何选择最优特征？

选取对训练数据具有分类能力的特征。常用的评价特征的准则有：信息增益，信息增益率，基尼指数等。以信息增益为例，它表示得知特征X的信息而使得类Y的信息不确定性减少的程度。信息增益越大，说明特征X减少Y的不确定的程度越大

谈谈对信息增益和信息增益率的理解

要理解信息增益，首先要理解熵这个概念。从概率统计的角度看，熵是对随机变量不确定性的度量，也可以说是对随机变量的概率分布的一个衡量。熵越大，随机变量的不确定性就越大。对同一个随机变量，当他的概率分布为均匀分布时，不确定性最大，熵也最大。对有相同概率分布的不同的随机变量，取值越多的随机变量熵越大。其次，要理解条件熵的概念。正如熵是对随机变量不确定性的度量一样，条件熵是指，有相关的两个随机变量X和Y，在已知随机变量X的条件下，随机变量Y的不确定性。当熵和条件熵中概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别为经验熵与经验条件熵。
信息增益，也叫互信息，就是指集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D∣A)之差。ID3算法在每一次对决策树进行分叉选取最优特征时，会选取信息增益最高的特征来作为分裂特征。信息增益准则对那些特征的取值比较多的特征有所偏好，也就是说，采用信息增益作为判定方法，会倾向于去选择特征取值比较多的特征作为最优特征，为了减少这种偏好带来的不利影响，信息增益率对这一问题进行了校正。 $g_R(D,A) = \frac{g(D,A)}{H(D)}$

决策树出现过拟合的原因及其解决办法？

对训练数据预测效果很好，但是测试数据预测效果较差的现象称为过拟合。

原因：

在决策树的构建过程中，对决策树的生长没有进行合理的限制(剪枝)；
样本中有一些噪声数据，没有对噪声数据进行有效的剔除；

解决办法：

选择合理的参数进行剪枝，可以分为预剪枝和后剪枝，一般采用的后剪枝的方法。
有效地抽样，用相对能够反映业务逻辑的训练集去产生决策树

为什么决策树需要进行剪枝？如何进行决策树的剪枝？

决策树生成算法迭代地产生决策树，直到不能继续下去为止，这样产生的决策树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即会出现过拟合的现象，过拟合的原因在于学习时过多的考虑如何提高对训练数据的正确分类，从而构建出了过于复杂的决策树。决策树的剪枝就是为了解决过拟合的现象。

决策树的剪枝通常通过极小化决策树整体的损失函数来实现。

\[C_{\alpha}(T) = \sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|\]

其中$H_t(T)$为经验熵，$N_t$为样本点数，|$T$|为树T的叶结点个数。

\[H_t(T) = -\sum_k \frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}\\C(T) = \sum_{t=1}^{|T|}N_tH_t(T) = -\sum_{t=1}^{|T|} \sum_{k=1}^K N_{tk}log\frac{N_{tk}}{N_t}\\C_{\alpha} = C(T)+\alpha|T|\]

记第一项为$C(T)$，表示模型对训练数据的预测误差，即模型与训练数据的拟合程度。$/T/$表示模型的复杂度。$\alpha$控制两者之间的影响。

剪枝，就是当$\alpha$确定时，选择损失函数最小的模型，即损失函数最小的子树，当$\alpha$确定时，子树越大，拟合的越好，但模型的复杂度越高，反之，子树越小，模型复杂度低但拟合不好。可以看出决策树的生成只考虑了通过提高信息增益对训练数据进行更好的拟合，而决策树剪枝通过优化损失函数还考虑了减小模型的复杂度，决策树的生成学习局部的模型，而决策树的剪枝学习整体的模型。决策树的损失函数极小化等价于正则化的极大似然估计，即利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。

C4.5对ID3做了哪些改进？

ID3的不足

ID3没有考虑连续特征。
ID3采用信息增益大的特征优先建立决策树的节点，对那些特征的取值比较多的特征有所偏好。
ID3算法对于缺失值的情况没有做考虑。
没有考虑过拟合的问题。

C4.5 对 ID3 的改进

对于ID3不能处理连续特征，C4.5的思路是将连续的特征离散化。
针对第二个不足，C4.5采用信息增益率来进行校正。
对于ID3的第3个缺失值处理的问题，主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。对于第一个子问题，对于某一个有缺失特征值的特征A。C4.5的思路是将数据分成两部分，对每个样本设置一个权重（初始可以都为1），然后划分数据，一部分是有特征值A的数据D1，另一部分是没有特征A的数据D2。然后对于没有缺失特征A的数据集D1来和对应的A特征的各个特征值一起计算加权重后的信息增益比，最后乘上一个系数，这个系数是无特征A缺失的样本加权后所占加权总样本的比例。对于第二个子问题，可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征A的样本a之前权重1，特征A有3个特征值A1,A2,A3。3个特征值对应的无缺失A特征的样本个数为2,3,4.a同时划分入A1,A2,A3。对应权重调节为2/9,3/9, 4/9。
对于ID3的第4个问题，C4.5引入了正则化系数进行剪枝。

决策树如何处理连续数值型属性(C4.5中)？

因为连续属性的可取值数目不再有限，因此不能像前面处理离散属性枚举离散属性取值来对结点进行划分。因此需要连续属性离散化，常用的离散化策略是二分法。参考周志华的机器学习(西瓜书)

决策树是如何处理缺失值的（C4.5中）？

主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。对于第一个子问题，对于某一个有缺失特征值的特征A。C4.5的思路是将数据分成两部分，对每个样本设置一个权重（初始可以都为1），然后划分数据，一部分是有特征值A的数据D1，另一部分是没有特征A的数据D2。然后对于没有缺失特征A的数据集D1来和对应的A特征的各个特征值一起计算加权重后的信息增益比，最后乘上一个系数，这个系数是无特征A缺失的样本加权后所占加权总样本的比例。对于第二个子问题，可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征A的样本a之前权重1，特征A有3个特征值A1,A2,A3。3个特征值对应的无缺失A特征的样本个数为2,3,4.a同时划分入A1,A2,A3。对应权重调节为2/9,3/9, 4/9。

CART如何生成回归树？

懒的敲了，我之前手写过，直接上图。。

CART对离散特征取值数目大于等于3的特征如何处理？

分类树的生成中有讲到。分类树的生成中，根据特征A是否取某一可能的值a被分割为D1和D2两部分。

决策树需要进行归一化处理吗？

不需要。概率模型（树形模型）不需要归一化，因为它们不关心变量的值，而是关心变量的分布和变量之间的条件概率，如决策树、RF。而像Adaboost、SVM、LR、Knn、KMeans之类的最优化问题就需要归一化。

这儿可能引出为什么需要进行归一化。

决策树在选择特征进行分类时一个特征被选择过后，之后还会选择到这个特征吗？

在ID3和C4.5中，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。参考周志华机器学习85页。
在CART中，一个特征被选择之后，这个特征还有可能被选择。

和其他模型比，决策树有哪些优点和缺点？

优点：

决策树算法易于理解，机理解释起来简单。
决策树算法可以用于小数据集。
决策树算法的时间复杂度较小，为用于训练决策树的数据点的对数。
能够处理多输出的问题。
对缺失值不敏感。
可以同时处理类别数据和数值数据。
可以处理不相关特征数据。
效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。

缺点：

对连续性的字段比较难预测。
容易出现过拟合。
当类别太多时，错误可能就会增加的比较快
在处理特征关联性比较强的数据时表现得不是太好。

集成学习

集成学习通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统。根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类：(1)个体学习器之间存在强的依赖关系，必须串行生成的序列化方法，代表是Boosting；(2)个体学习器间不存在强依赖关系，可同时生成的并行化方法，代表是Bagging。

Boosting类方法

工作机制：先从初始训练集训练出一个基学习器，再根据学习器的表现对训练样本分布进行调整，即对正确分类的样本降低它的权重，对错分的样本增大它的权重，这样可以使得先前基学习器错分的训练样本在之后的学习中受到更多的关注，然后基于调整后的样本分布来训练下一个基学习器，如此重复进行，直到基学习器数目达到预设的数量时终止，最终模型的输出是这些基学习器的加权组合。
GBDT和Xgboost：原理、推导、比较
 GBDT (Gradient Boosting Decision Tree)
机器学习-一文理解GBDT的原理-20171001
GBDT算法原理深入解析*
机器学习算法系列（8）：XgBoost
GBDT、XGBoost、LightGBM 的使用及参数调优

梯度提升树(GBDT)

采用加法模型和前向分步算法，以决策树为基函数的提升方法称为提升树。由于树的线性组合可以很好地拟合训练数据，即使数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。
提升树
以回归树提升树为例，使用前向分布计算：前向分布计算的思想：因为学习的是加法模型，加法模型的优化是一个复杂的优化问题，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数，那么就可以简化优化的复杂度。

梯度提升树
GBDT利用了提升树的思想，是提升树的一种，是梯度下降法的近似方法，关键是利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树。

XGboost

GBDT算法原理深入解析*
GBDT和Xgboost：原理、推导、比较
 机器学习-一文理解GBDT的原理-20171001
目标函数之所以定义为损失函数和正则项两部分: 是为了尽可能平衡模型的偏差和方差（Bias Variance Trade-off）。最小化目标函数意味着同时最小化损失函数和正则项，损失函数最小化表明模型能够较好的拟合训练数据，一般也预示着模型能够较好地拟合真实数据（groud true）；另一方面，对正则项的优化鼓励算法学习到较简单的模型，简单模型一般在测试样本上的预测结果比较稳定、方差较小（奥坎姆剃刀原则）。也就是说，优化损失函数尽量使模型走出欠拟合的状态，优化正则项尽量使模型避免过拟合。

为什么基于残差的GBDT不是一个好的选择？

当损失函数是平方损失和指数损失函数是，每一步的优化是很简单的，但对于一般损失函数而言，往往每一步优化并不容易。
基于平方损失函数的一个明显的缺点就是对于异常值过于敏感，所以一般回归类的损失函数会使用绝对损失函数或者huber损失函数来代替平方损失函数。

Bagging类方法

Bagging是并行化集成学习中最著名的代表，它是基于自助采样法，我们可以采样出T个含m个训练样本的采样集，然后基于每个采样集训练一个基学习器，再将这些基学习器组合，对预测输出进行组合时，Bagging通常对分类任务采用投票法，对回归任务求平均。

随机森林(RF)

随机森林是Bagging(简单理解为：放回抽样(自主采样法)，多数表决(分类)或简单平均(回归)，其基学习器之间属于并列生成，不存在强依赖关系)的扩展变体，它以决策树为基学习器，构建Bagging集成的基础上进一步在决策树的训练过程中引入了随机属性选择。因此可包括四个部分：随机选择样本(自主采样法)、随机属性选择、构建决策树、随机森林投票(平均)。

随机选择样本与Bagging相同；随机属性选择是在构建树的过程中，先从样本集的特征集合中随机选择部分特征(属性)，然后再从这个子集中选择最优属性用于划分，这种随机性导致随机森林的偏差会有稍微的增加(相比于单棵非随机树)，但由于随机森林的“平均”性质，会使得它的方差减小，而方差减小补偿了偏差的增大，因此总体会得到更好的模型。在构建决策树的时候，RF的每棵决策树都最大可能的进行生长而不进行剪枝，在对预测输出进行结合时，RF对于分类任务采用投票，回归任务采样平均法。

RF的重要特性是不对其进行交叉验证或者使用一个独立的测试集获得无偏估计，它可以在内部进行评估，也就是说在生成的过程中可以对误差进行无偏估计，由于每一个基学习器只使用了训练集中约63.2%的样本，剩余的样本可用作验证集来对其泛化性能进行“包外估计”。

RF和Bagging比较：RF其实性能较差，特别是当只有一个基学习器的时候，随着学习器数目的增多，随机森林通常会收敛于更低的泛化误差。随机森林的训练效率也高于Bagging，因为在单个决策树的构建过程中Bagging使用的是“确定”决策树，即在选择特征划分结点时需要考虑所有的属性，而随机森林则是随机选取部分属性来构建决策树。

优点
1.简单，易实现，计算开销小，容易理解和解释，树可以被可视化；

能够处理很高维的数据，并且不用特征选择，而且训练完成后，给出特征的重要性；
隐含地创建了多个联合特征，并能够解决非线性问题；
自带out-of-bag(包外估计)错误评估能力
容易做成并行化方法

缺点

不适合小样本，只适合大样本；
大多数情况下，RF模型的精度略低于GBDT模型的精度；
适合决策边界是矩形的，不适合对角线型。

为什么梯度提升方法倾向于选择决策树作为基学习器呢？

这与决策树算法自身的优点有很大的关系，决策树可以认为是if-then规则的集合，易于理解，可解释性强，预测速度快。同时，决策树算法相比于其他的算法需要更少的特征工程，比如可以不用做特征标准化，可以很好地处理字段缺失的数据，也可以不用关心特征间是否相互依赖等。决策树能够自动组合多个特征，它可以毫无压力的处理特征间的交互关系并且是非参数化的，因此不必担心异常值或数据是否线性可分。不过，单独使用决策树算法时，有容易过拟合缺点。所幸的是，通过各种方法，抑制决策树的复杂性，降低单颗决策树的拟合能力，再通过梯度提升的方法集成多个决策树，最终能够很好的解决过拟合的问题。由此可见，梯度提升方法和决策树学习算法可以互相取长补短，是一对完美的搭档。

GBDT与XGBoost的区别

基分类器的选择：传统的GBDT以CART作为基分类器，XGBoost还支持线性分类器，这个时候XGBoost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
二阶泰勒展开：传统的GBDT在优化时只用到一阶导数信息，XGBoost则对损失函数进行了二阶泰勒展开，同时用到了一阶导数和二阶导数。顺便提一下，XGBoost工具支持自定义损失函数，只要函数可一阶和二阶求导。
偏差-方差权衡：XGBoost在目标函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数$T$、每个叶子节点上输出分数的$L_2$模的平方和。从偏差-方差权衡角度来讲，正则项降低了模型的方差，使学习出来的模型更加简单，防止过拟合。
列采样：XGBoost借鉴了随机森林的做法，支持列采样，不仅能降低过拟合，还能减少计算量。
缺失值处理：传统的GBDT没有设计对缺失值进行处理，XGBoost可以自动学习出它的分裂方向。XGBoost对于缺失值能预先学习一个默认的分裂方向。
XGBoost工具支持并行：Boosting不是一种串行的结构吗?怎么并行的？注意XGBoost的并行不是tree粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。XGBoost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
可并行的近似直方图算法:树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以XGBoost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

GBDT与RF的区别

相同点

都是由多棵树组成；
最终的结果都是由多棵树一起决定。

GBDT与RF的不同点

组成随机森林的树可以是分类树，也可以是回归树，而GBDT只能是回归树；
组成随机森林的树可以并行生成，而GBDT只能串行生成；
对于最终的输出结果而言，随机森林采用多数投票等，而GBDT则是将所有结果累加起来，或者加权累加起来；
随机森林对异常值不敏感，GBDT对异常值非常敏感；
随机森林对训练集一视同仁，GBDT是基于权值的弱分类器集成；
随机森林是通过减少模型方差提高性能，GBDT是通过减少偏差提高性能。

为什么GBDT的树深度较RF通常都比较浅?

对于机器学习来说，泛化误差可以理解为两部分，分别是偏差（bias）和方差（variance）；偏差指的是算法的期望预测与真实预测之间的偏差程度，反应了模型本身的拟合能力；方差度量了同等大小的训练集的变动导致学习性能的变化，刻画了数据扰动所导致的影响。当模型越复杂时，拟合的程度就越高，模型的训练偏差就越小；但此时如果换一组数据可能模型的变化就会很大，即模型的方差很大，所以模型过于复杂的时候会导致过拟合.
RF: 对于RF来说由于并行训练很多不同的分类器的目的就是降低这个方差（variance）。所以对于每个基分类器来说，目标就是如何降低这个偏差（bias），所以我们会采用深度很深甚至不剪枝的决策树。
GBDT：对于GBDT来说由于利用的是残差逼近的方式，即在上一轮的基础上更加拟合原数据，所以可以保证偏差（bias），所以对于每个基分类器来说，问题就在于如何选择 variance 更小的分类器，即更简单的分类器，所以我们选择了深度很浅的决策树。

贝叶斯分类器(朴素贝叶斯分类器)

小白之通俗易懂的贝叶斯定理
 贝叶斯整理
 朴素贝叶斯算法原理小结
 朴素贝叶斯常见面试题

什么是贝叶斯决策理论？

贝叶斯决策理论是主观贝叶斯派归纳理论的重要组成部分。贝叶斯决策就是在不完全情报下，对部分未知的状态用主观概率估计，然后用贝叶斯公式对发生概率进行修正，最后再利用期望值和修正概率作出最优决策（选择概率最大的类别）。贝叶斯决策理论方法是统计模型决策中的一个基本方法，其基本思想是：
1. 已知类条件概率和先验概率。
2. 利用贝叶斯公式转换成后验概率。
3. 根据后验概率大小进行决策分类。

简述朴素贝叶斯算法原理和工作流程

朴素贝叶斯是基于贝叶斯定理和特征条件独立性假设的分类方法。对于给定的数据集，首先基于特征条件独立性假设学习输入/输出的联合概率分布；然后基于此模型，对给定的输入x，利用贝叶斯定理求出后验概率最大的输出y。朴素贝叶斯法实现简单，学习和预测的效率都很高，是一种常用的方法。朴素贝叶斯分类器的表达式为$h_nb(x) = argmax_{c\in y} P(c)\prod_{i=1}^dP(x_1/c)$

朴素贝叶斯法为什么引入属性独立性假设？

朴素贝叶斯考虑了类条件概率$P(x/c)$是在所有属性上的联合概率，难以从有限的训练样本直接估计得到(基于有限训练样本直接估计联合概率，在计算上会遭遇组合爆炸问题，在数据上将会遭遇样本稀疏问题，属性越多问题越严重)。为了避开这个问题，朴素贝叶斯分类器采用了“属性独立性假设”：对已知类别，假设所有属性相互独立，即每个属性独立地对分类结果发生影响。

\[P(c|x) = \frac{P(c)P(x|c)}{P(x)} = \frac{P(c)}{P(x)}\prod_{i=1}^{d}P(x_i|c)\]

朴素贝叶斯的朴素在哪里，怎么理解朴素贝叶斯中的“朴素”？

在计算类条件概率分布的时候，朴素贝叶斯引入了一个很强的属性独立性假设，即当Y确定时，X的各个特征分量取值之间相互独立。因为它假定所有的特征在数据集中的作用是独立同分布的，但这个假设在现实生活中很不真实，因此很“朴素”。

极大似然估计和贝叶斯估计

极大似然估计与贝叶斯估计
对于参数估计，统计学界有两大学派：频率主义学派和贝叶斯学派。

频率主义学派：认为参数虽然未知，但却是客观存在的固定值，因此，可以通过优化似然函数等准则来确定参数值。极大似然估计：估计类条件概率的一种常用策略就是先假定其具有某种确定的概率分布形式，在基于训练样本对概率分布的参数进行估计。
贝叶斯学派：认为参数是未观察到的随机变量，其本身也可有分布，因此，可假定参数服从一个先验分布，然后基于观测到的数据来计算参数的后验分布。

朴素贝叶斯采用极大似然估计来估计先验概率和类条件概率。但是需要注意的是，如果某个属性值在做训练集中没有与某个类同时出现过，则直接基于极大似然估计会影响到后验概率的计算结果，使分类产生偏差，解决这一问题的方法是采用贝叶斯估计，即为随机变量的各个属性值的频数上赋予一个正数$\lambda > 0$。当$\lambda = 0$时就是极大似然估计，常取$\lambda = 1$，此时称为拉普拉斯平滑。

为什么属性独立性假设在实际情况中很难成立，但是朴素贝叶斯法仍能取得较好的效果？(不确定)

人们在使用分类器之前，首先做的第一步（也是最重要的一步）往往是特征选择，这个过程的目的就是为了排除特征之间的共线性、选择相对较为独立的特征；
对于与分类任务来说，只要各类别的条件概率排序正确，无需精准概率值就可以导致正确分类；
如果属性间依赖对所有类别影响相同，或依赖关系的影响能相互抵消，则属性条件独立性假设在降低计算复杂度的同时不会对性能产生负面影响。

朴素贝叶斯为什么要后验概率最大化？

等价于期望风险最小化。假设选取0-1损失函数，即分类正确取1，错误取0，这时的期望风险最小化为下图

朴素贝叶斯的优缺点

优点：

朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率；
对小规模数据集表现的很好，能够处理多分类任务，适合增量式训练；
对缺失数据不太敏感，适用于文本分类任务，对待预测的样本进行预测时，过程简单速度快。

缺点：

特征条件独立性假设在实际应用中往往是不成立的，在属性个数比较多或者属性之间相关性较大时，分类效果不好。而在属性相关性较小时，朴素贝叶斯性能最为良好
需要计算先验概率，而先验概率很多时候取决于假设，假设的模型可以有很多种，因此在某些时候会由于假设的先验模型的原因导致预测效果不佳
由于我们是通过先验和数据来决定后验的概率从而决定分类，所以分类决策存在一定的错误率
对输入数据的表达形式很敏感

机器学习过程中的问题

梯度消失和梯度爆炸的产生的原理以及常用解决方法是什么？

梯度爆炸现象：损失出现NAN，一般出现在深层网络中和权值初始值太大的情况；梯度消失现象：网络不学习，即参数不更新，一般出现在深层网络和采用了不合适的激活函数。

从深层网络角度来讲：对于深层网络的参数更新，需要梯度的反向传播，使用链式求导法则，当某一部分对激活函数求导大于1时，当层数增多时，梯度更新将以指数级增加，发生梯度爆炸。如果该部分小于1，那么随着层数增多，求出的梯度更新将会以指数级减小，发生梯度消失。总结：从深层网络的角度来看，不同的层学习的速度差异很大，表现为网络中靠近输出的层学习的情况很好，靠近输入的层学习的很慢，有时候甚至训练了很久，前几层的权值和刚开始初始化的值差不多，因次，梯度消失和梯度爆炸的根本原因是反向传播的链式求导法则，属先天不足。

从激活函数角度来讲：激活函数的选择如sigmoid。

详解机器学习中的梯度消失、爆炸原因及其解决方法

解决方法

预训练+微调
梯度剪切、正则
更换激活函数 ReLU LeakReLU等
batchnorm 解释：BN就是通过一定的规范化手段，把每层神经网络输入的分布强行拉回到均值为0方差为1的标准正态分布，使得非线性函数的输入值落入到其比较敏感的区域，这样可以让梯度变大，避免梯度消失的问题，而且可以加快训练速度。
残差结构

生成式模型和判别式模型有什么区别？各自的工作原理是什么？

监督学习方法分为生成方法(生成式模型)和判别方法(判别式模型)：

生成式模型

由数据学习联合概率分布$P(X,Y)$，然后求出条件概率分布$P(Y|X)$作为预测模型，即$P(Y|X) = \frac{P(X,Y)}{P(X)}$，这样的方法之所以称为生成式模型，是因为模型表示了给定输入$X$产生输出$Y$的生成关系。典型的模型有：朴素贝叶斯、隐马尔科夫模型(HMM)、混合高斯模型、贝叶斯网络、马尔可夫随机场(MRF)、深度信念网络(DBN)。

生成式模型的特点：生成式模型可以还原出联合概率分布$P(X,Y)$，而判别式模型则不能，生成式模型的学习收敛速度更快，即当样本容量增加的时候，学到的模型可以更快地收敛于真实模型，当存在隐变量时，仍可以用生成式模型学习，此时判别式模型就不能用了。优点：(1)实际上带的信息要比判别式模型丰富，研究单类问题比判别式模型灵活性强;(2)模型可以通过增量学习得到;(3)生成模型可以应付隐变量的情况，比如混合高斯模型就是含有隐变量的生成方法。缺点：(1)学习过程比较复杂;(2)实践中多数情况下判别模型效果更好。参考文章

判别式模型

由数据直接学习决策函数$f(X)$或者条件概率分布$P(Y| X)$作为预测模型。判别式模型关心的是对给定的输入$X$，应该预测什么样的输出$Y$。典型的判别模型有：K近邻(KNN)、感知机、决策树、逻辑回归、最大熵模型、支持向量机、提升方法、条件随机场、线性回归、线性判别分析。

判别式模型的特点：判别式模型直接学习的是条件概率$P(Y/X)$或决策函数$f(X)$，直接面对预测，往往学习的准确率更高，由于直接学习$P(Y/X)$或$f(X)$，可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题。优点：(1)分类边界更灵活，比使用纯概率方法或生成式模型得到的更高级;(2)准确率往往比生成式模型高;(3)不需要求解类别条件概率，所以允许我们对输入进行抽象(比如降维，定义特征等)，从而能够简化学习问题。缺点：(1)不能反映训练数据的本身特性。

$L_1$正则和$L_2$正则如何理解？有什么区别？为什么能解决过拟合问题？

从贝叶斯的角度来看：正则化是假设模型参数服从先验概率，即为模型参数添加先验，只是不同的正则化方法的先验分布是不一样的，$L_1$正则是拉普拉斯先验，而$L_2$正则是高斯先验。这样就规定了参数分布，使得模型的复杂度降低，对噪声与异常点的抗干扰性的能力增强，从而提高了模型的泛化能力。机器学习防止欠拟合、过拟合方法

Lasso回归：逻辑回归的基础上加了$L_1$正则。岭回归：逻辑回归的基础上加了$L_2$正则。

什么是过拟合,欠拟合，解决过拟合和欠拟合的方法有哪些？

过拟合(over-fitting)：过拟合是指学习时选择的模型所包含的参数过多，以致于出现这一模型图对已知数据预测的很好，但对未知数据预测很差的现象(—来自李航的统计机器学习)，原因总结就是数据太少以及模型太复杂。

过拟合原因

数据层面：(1)数据量太少；(2)训练集和测试集分布不均匀；(3)数据不纯，包含大量的噪声，模型过度拟合噪声数据。
模型层面：模型太复杂

解决欠拟合的方法

添加其它项，有时候模型出现欠拟合是因为特征项不够导致的，可以添加其他特征项来解决
添加多项式特征。将线性模型增加二次项或三次项使模型的拟合能力变强
增加模型的复杂度
减少正则化参数

解决过拟合现象的方法

数据集扩增：(从数据源头采集更多数据，复制原有数据并加上随机噪声，重采样，根据当前数据估计分布，用分布产生数据)
特征选择
正则化
早停(Early Stopping)
dropout
残差结构
交叉验证

有哪些评价指标？AUC怎么求？AUC刻画的是什么？Precision和Accuracy的区别？

	Yes	No	总计
Yes	TP	FN	P(实为Yes)
No	FP	TN	N(实为No)
总计	P’(被分为Yes)	N’(被分为No)	P+N

评价指标

正确率(accuracy):$accuracy = \frac{(TP+TN)}{P+N}$,正确率是被分对的样本数在所有样本数中的占比，通常来说，正确率越高，分类器越好。
错误率(Error rate):错误率与正确率相反，描述被分类器错分的比例。
灵敏度(sensitivity):$sensitivity=\frac{TP}{P}$,表示所有正例中被分对的比例，衡量了分类器对正类的识别能力。
特异性(specificity):$specificity=\frac{TN}{N}$,表示所有负例中被分对的比例，衡量了分类器对负例的识别能力。
精度(Precision):$precision=\frac{TP}{TP+FP}$,精度是精确性的度量，表示被分为正例的样本中实际为正例的比例。
召回率(Recall):$recall=\frac{TP}{TP+FN}$,召回率是覆盖面的度量，度量多少个正例被分为正例，召回率和灵敏度一样。
$F_1$score:综合了查准率(精度)和查全率(召回率)，$F_1=\frac{2\times precision \times recall}{precision+recall}$.

AUC值是一个概率值，当你随机挑选一个正样本以及一个负样本，当前的分类算法根据计算得到的Score值将这个正样本排在负样本前面的概率就是AUC值。当然，AUC值越大，当前的分类算法越有可能将正样本排在负样本前面，即能够更好的分类。AUC越大，模型越可靠。