常见面试问题

1、SVM原理

支持向量机、二分类模型

学习策略：间隔最大化

可转化为一个凸二次规划问题

通过寻找有着最大间隔的超平面 $\rightarrow$ 函数间隔、几何间隔

函数间隔：（超平面 $w*x+b=0$ 确定的情况下， $\vert w*x+b \vert$ 能够表示点x距离超平面的远近，根据 $w*x+b$ 的符号与类标记 $y$ 的符号是否一致可判断结果是否正确）

$\hat{ \Upsilon } =y(w^Tx+b)=yf(x)$

$\hat{ \Upsilon } = min \hat{ \Upsilon _{i} } \ \ \ (i=1,...,n)$

此时若成比例改变 $w$ 和 $b$ ，则 $f(x)$ 变为2倍，函数间隔的值也随之增大，但我们知道实践上超平面并没有改变，所以使用几何间隔。

几何间隔：假设有点x、超平面， $w$ 为垂直于超平面的向量， $\Upsilon$ 为 $x$ 到超平面的距离，有 $x_0$ 为 $x$ 到超平面的投影的对应点，则

$x = x_0 + \Upsilon \frac{w}{||w||}$ ( $\frac{w}{||w||}$ 为单位向量， $||w||$ 为 $w$ 的二阶范数）

$\Upsilon = \frac{w^Tx+b}{||w||} = \frac{f(x)}{||w||}$

为得到 $\Upsilon$ 的绝对值，令其乘上对应类别 $y$ ，即得几何间隔 $\tilde{\Upsilon }$

$\tilde{\Upsilon } =y\Upsilon = \frac{\hat{\Upsilon } }{||w||}$

通过最大化几何间隔有最大间隔分类器。

目标函数： $y_i(w^Tx_i+b) = \hat{\Upsilon _i} \geq \hat{\Upsilon }$ , $i$ =1,...,n

$max_{\Upsilon ,w,b} \frac{\hat{\Upsilon } }{||w||}$ , $s.t.\ \ y_i(w^Tx_i+b) = \hat{\Upsilon _i} \geq \hat{\Upsilon }$ , $i$ =1,...,n

可简化：令 $\hat{\Upsilon } =1$ （方便推导、优化）

则 $max \frac{1 }{||w||}$ ， $s.t.\ \ y_i(w^Tx_i+b) \geq 1$ ， $i$ =1,...,n

求 $max \frac{1 }{||w||}$ 相当于求 $min \frac{1}{2}||w||^2$

则转化为

$min \frac{1}{2}||w||^2$ $s.t.\ \ y_i(w^Tx_i+b) \geq 1$ ， $i$ =1,...,n

就转变为了一个凸二次规划问题。

如何优化？三种情况（凸优化问题）

1、无约束优化问题 $min(f(x))$ 费马定理

2、带等式约束的优化问题：拉格朗日乘子法，对偶性

拉格朗日函数 $L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^n \alpha_i(y_i(w^Tx_i+b)-1)$

若令 $\theta(w)=max_{a_i\geq 0}L(w,b,\alpha)$

目标函数： $min_{w,b}\theta(w) = min_{w.b}max_{a_i \geq 0}L(w,b,\alpha)=p^*$

对偶 $\implies$ $max_{a_i \geq 0}min_{w.b}L(w,b,\alpha)=d^*$ ，有 $d^* \leq p^*$

3、带不等式约束的优化问题： KKT条件

$minf(x)\ \ s.t.\ \ h_j(x)=0$ , $j$ =1,...,p， $g_k(x)\leq0$ , $k$ =1,...,q， $x\in X\subset R^n$

$f(x)$ 是需最小化的函数， $h(x)$ 是等式约束， $g(x)$ 是不等式约束，p，q为约束的数量

（凸优化： $X\subset R^n$ 为一凸集， $f:X\rightarrow R$ 为一凸函数。凸优化为找出一点 $x^*\in X$ ，使每一 $x \in X$ 满足 $f(x^*)\leq f(x)$ ）

KKT的意义：

是一个非线性规划问题，能有最优化解法的必要和充分条件

对于线性不可分的情况，通过核函数，将低维映射到高维

2、哪些机器学习算法不需要做归一化处理？

通过梯度下降法求解的模型一般都需要归一化，如Linear、LR、KNN、SVM、神经网络等

树形模型不需要归一化，如：DT、RF

扩展：

标准化：特征均值为0，方差为1

公式： $\frac{x-np.mean(x)}{np.std(x)}$

归一化：把每个特征向量（特别是奇异样本数据）的值都缩放到相同数值范围，如0-1，-1-1（常用形式，将特征向量调整为L1范数（绝对值相加），使特征向量数值之和为1）（能使迭代次数减少）

公式： $\frac{x-min(x)}{max(x)-min(x)}$

3、树形结构为什么不需要归一化？

因为数值缩放不影响分裂点的位置，对树模型的结构不造成影响

按照特征值进行排序的，排序的顺序不变，那么所属的分支以及分裂点就不会有不同。而且，树模型不能进行梯度下降，因为构建树模型（回归树）寻找最优点时是通过寻找最优分裂点完成的。所以树模型是跃迁的。跃迁点不可导且求导没意义，故不用归一化。

4、欧氏距离与曼哈顿距离的区别

欧氏距离用于计算两点或多点之间的距离

$d(x,y)=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+...+(x_n-y_n)^2}=\sqrt{\sum_{i=1}^n (x_i-y_i)^2}$

缺点：将样本的不同属性之间的差别等同看待。比如年龄学历对工资的影响，将年龄与学历等同看待

曼哈顿距离：欧式几何空间两点之间的距离在两个坐标轴的投影

$d_{1 2}=\sum_{k=1}^n |x_{1k}-x_{2k}|$

5、数据归一化的原因

因为各维度的量纲不同，收敛速度不统一，用梯度下降法计算数值时，使用归一化能加速收敛，但一般能不用归一化最好不用

6、机器学习项目的流程

1、抽象为数学问题

2、获取数据

3、特征预处理（a）与特征选择（b）

关键步骤：a、归一化、离散化、因子化、缺失值处理、去除共线性等

b、相关系数、卡方检验、平均互信息、条件熵、后验概率、逻辑回归权重等

4、训练模型与调优

5、模型诊断（拟合、误差分析）

6、模型融合（提升准确度主要是3与6）

7、上线运行

7、LR为什么要对特征离散化？

1、非线性：LR属于广义线性模型，表达能力受限，离散化为模型引入了非线性，提升表达能力，加大拟合，易于快速迭代。

2、速度快

3、鲁棒性：离散化后的特征对异常数据有很强的鲁棒性

4、方便交叉与特征组合

5、稳定性：使模型更稳定

6、简化模型：降低过拟合的风险

8、LR

二分类器、在线性回归的基础上增加sigmoid函数 $\frac{1}{1+e^{-x}}$

代价函数选择最大对数似然函数，可改写为：

$Cost(h_{\theta}(x),y)=-ylog(h_{\theta}(x)-(1-y)log(1-h_{\theta}(x)))$

常使用0.5作为分界

使用正则化项用于防止过拟合

9、处理overfitting

正则化： L2： $\sum_{j=1}^n \theta_j ^2$ L1: $\sum_{j=1}^n |\theta_j|$

随机失活（dropout）：神经网络中让神经元以超参数p的概率被激活，每个w随机参与

逐层归一化（batch normalization）：给每层的输出都做一次归一化，使得下一层输入接近高斯分布

提前终止

增加训练数据

10、LR与SVM的联系与区别

联系：一般都用于处理二分类问题（改进后可处理多分类问题）、线性分类器、监督学习、判别模型

区别：1、LR是参数模型，SVM是非参数模型，Linear与rbf（径向基）则是针对数据线性可分和不可分的区别

2、目标函数不同，LR为logistical loss，SVM常为hinge loss（锁链损失函数），都增加对分类影响较大的数据点的权重，减少关系小的数据点的权重。

LR： $J(\theta) = -\frac{1}{m}\sum_{i=1}^{m} [y^{(i)}logh_\theta(x^{(i)}) + (1-y^{(i)})log(1-h_\theta(x^{(i)}))]$

SVM： $L(w,b,\alpha) = \frac{1}{2}||w||^2 - \sum_{i=1}^{n} \alpha_i(y_i(w^Tx_i + b)-1)$

3、SVM只考虑support vectors，即和分类最相关的少数点，LR通过非线性映射，提升与分类最相关的数据点的权重

4、SVM用途大于LR，但有的时候LR的准确性高于SVM

5、SVM基于距离分类，LR基于概率分类

11、牛顿法和梯度下降法的不同

牛顿法为近似求解，使用 $f(x)$ 泰勒级数的前几项寻找 $f(x)=0$ 的根，收敛速度快，是二阶收敛，是局部算法，考虑方向和步子大小，对步长的估计使用二阶逼近

梯度下降法仅考虑方向，是一阶收敛。

12、拟牛顿法

用于求解非线性优化问题，最有效之一

思想：改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，使用正定矩阵来近似Hessian矩阵的逆，简化运算复杂性。（不用求二阶导，构造近似的海森矩阵）

13、共轭梯度法

介于梯度下降法与牛顿法之间，仅需利用一阶导数信息，同时克服梯度下降收敛慢的缺点，又避免了牛顿法需要计算海森矩阵并求逆的缺点。

是解决大型线性方程组最有用的方法之一；

是解决大型非线性最优化最有效的算法之一。

14、核函数

多项式核： $K(x_1,x_2)=(<x_1,x_2>+R)^d$ d次多项式核函数

高斯核： $K(x_1,x_2)=exp(- \frac{||x_1 - x_2||^2}{2\sigma ^2})$ 可将原始空间映射为无穷维空间，通过调控参数 $\sigma$ ，可具有相当高的灵活性

线性核： $K(x_1,x_2)=<x_1,x_2>$ 实际上是原始空间中的内积，其存在的主要目标是使映射前后空间中的问题在形式上统一起来

核函数本身与映射没有关系，只是用来计算映射到高维空间后的内积的一种简便方法

15、从决策树到集成学习

决策树：回归树：用于响应变量是数值的或连续的 CART

分类树：ID3：信息增益没有剪枝，信息增益会偏向于那些取值较多的特征

C4.5：信息增益率可对连续值与缺失值进行处理，可剪枝，克服ID3偏向的不足

CART： Gini系数

剪枝：预剪枝、后剪枝

集成：bagging：学习器间不存在强依赖关系；学习器可并行训练生成；结果投票 eg：RF

boosting：学习器间存在强依赖关系；必须串行生成；加权，不放回抽样 eg：Adaboost、GBDT、XGBoost等

16、正则化

正则化项：惩罚复杂模型，鼓励更加简单的模型，防止过拟合

保留所有特征，但是降低参数 $\theta_j$ 的值

好处：当特征很多时，每一个特征都会提供合适的作用

目的：防止过拟合

L1、L2：L1可以产生稀疏矩阵，即产生一个稀疏模型，可以用于特征选择

L2可以防止过拟合，某种程度上L1也可以

17、损失函数

用于度量预测错误的程度

是经验风险函数的核心部分，也是结构风险函数的重要组成部分。

模型的结构风险函数 = 经验风险项 + 正则项

常见： 0-1损失函数： $L(y,f(x)) = 1,y\neq f(x)\ \ \ ;0,y=f(x)$

绝对值损失函数： $L(y,f(x))=|y-f(x)|$

对数损失函数： $L(y,P(y|x))=-logP(y|x)$

对LR，取对数为了方便计算极大似然估计

对LR， $P(Y=y|x)= \begin{cases} h_{\theta}(x)=g(f(x))=\frac{1}{1+e^{-f(x)}},y=1 \\ 1-h_{\theta}(x)=1-g(f(x))=\frac{1}{1+e^{f(x)}},y=0\end{cases}$

得到 $L(y,P(Y=y|x))= \begin{cases}log(1+e^{-f(x)}),y=1 \\ log(1+e^{f(x)}),y=0\end{cases}$

平方损失函数： $L(Y,f(X))=(Y-f(X))^2$

最小二乘法，一般线性回归，凸优化；假设样本和噪声都服从高斯分布

指数损失函数： $L(y,f(x))=e^{-yf(x)}$ Adaboost

Hinge损失函数： $L(y) = max(0,1-y\tilde{y} ),y=\pm 1$ SVM

18、XGBoost为什么要用泰勒展开，有何优势

XGBoost使用了一阶偏导与二阶偏导，使用泰勒展开取得函数做自变量的二阶导形式，把损失函数的选取和模型优化算法优化及参数选择分开了。

这种去耦合增加了XGBoost的适用性，使其可以按需选取loss function，可用于回归、分类。

19、线性分类器、非线性分类器

线性分类器：LR、贝叶斯、单层感知器、线性回归、SVM（线性核）

非线性分类器：DT、RF、GBDT、多层感知器、SVM（高斯核）

20、L1、L2先验服从什么分布

L1：拉普拉斯分布

L2：高斯分布

21、朴素贝叶斯的朴素

因为其假定所有特征在数据集中的作用同样重要且是独立的

22、EM算法

最大期望算法，在概率模型中寻找参数最大似然估计或最大后验估计的算法

步骤：（交替进行计算）

一、计算期望（E）：利用对隐藏变量的现有估计值，计算其最大似然估计值

二、最大化（M）：最大化在E步上求得的最大似然估计值来计算参数的值，并用于下一个E步计算中。

23、KNN中K值得选取

K小过拟合、K大欠拟合，可通过先验知识选取近似值，通过交叉验证选取最合适的值，一般较小

24、简述KNN最邻近分类算法的过程

1、计算测试样本和训练样本中每个样本点的距离

2、对距离值进行排序

3、选前K个最小距离的样本

4、根据这K个样本的标签进行搜索，得到最后的分类类别

25、贝叶斯定理

$P(H|X)=\frac{P(X|H)P(H)}{P(X)}$

26、模型对缺失值的敏感性

树模型不敏感

涉及距离度量会敏感，如KNN

线性模型的代价函数往往涉及距离计算

神经网络鲁棒性强

27、K-MEANS及优化

思想：事先确定常数K，随机选定初始点为质心，并通过计算每个样本点与质心之间的距离，对最靠近质心的对象归类，通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果

步骤：1、随机选取K个元素，作为K个子集的重心

2、根据剩下元素到K个子集重心的距离划归到最近的子集

3、根据结果重新计算重心

4、根据新重心重新聚类

5、重复，直至结果不再改变

优点：a、简单、高效、易于理解 b、聚类效果好

缺点：a、对K初始值的选择较敏感，容易陷入局部最小值

优化：使用多次的随机初始化，计算每次建模的代价函数的值，选最小的作为聚类结果；二分K_MEANS算法

b、K值由用户指定，不同K的结果可能有很大的不同

优化：肘部法则、按需选择、观察法、Gap statistics方法

c、局限性，有些数据分布无法处理，如非球状数据

优化：DBSCAN：基于密度的方法

思想：A、指定合适的 $\varepsilon$ 邻域（ $\varepsilon$ 为半径）和Minpoints（最小样本点数）

B、计算所有样本点，若点p的 $\varepsilon$ 邻域里点数大于Minpoints，创建以p为核心的新簇

C、反复寻找这些核心的的直接密度可达与密度可达，将其加入到相应的簇，对核心点发生“密度相连”的簇，给予合并

D、没有新点可以被添加到簇时，结束

d、数据量大时，收敛慢

优化：Mini Batch K_MEANS

步骤：A、将数据集随机抽取形成小批量，分配给最近的质心

B、更新质心

28、特征选择

数据预处理的一个重要过程

常见方式：1、去除方差较小的特征

2、正则化

3、RF，对于分类，采用基尼不纯度或信息增益；对于回归，常采用方差或最小二乘拟合

4、稳定性选择：思想：在不同的数据子集和特征子集上运行特征选择算法，不断重复，最终汇总特征选择结果

29、衡量分类器好坏

精度、召回率、F1值、ROC曲线、AUC等

30、数据预处理

数据可能存在的问题：数据缺失、数据噪声、数据不一致、数据冗余、数据集不均衡、离群点/异常值、数据重复

步骤：1、数据清洗 2、数据转换 3、数据描述 4、特征选择或特征组合 5、特征抽取

数据清洗：处理缺失数据、离群点、重复数据

缺失数据处理：删除、手工填补、自动填补（均值、概率、公式计算等）

离群点处理根据具体情况而定，但首先要检测出来

重复数据：如果高度疑似的样本是挨着的，就可以用滑动窗口对比，为了让相似记录相邻，可以每条记录生成一个hash key，根据key去排序

数据转换：采样处理、类型转换、归一化

数据描述：可视化等

特征选择：熵增益，分支定界；顺序向前、顺序向后、模拟退火、竞技搜索、遗传算法等优化

特征抽取：PCA、LDA（线性判别分析）

均假设数据服从高斯分布，都用了矩阵分解思想

PCA无监督，对降低后的维度无限制，目标为投影方差最大

LDA有监督，降低后的维度小于类别数，目标为类内方差最小，类间方差最大

31、梯度消失问题

梯度消失：在神经网络中，当前面隐藏层的学习速率低于后面隐藏层的学习速率，即随着隐藏层数目的增加，分类准确率反而下降了

根本原因：梯度反向传播中的连乘效应

原因：隐藏层过多；采用了不合适的激活函数

反向传播（用于优化神经网络参数）：根据损失函数计算的误差通过反向传播的方式，指导深度网络参数的更新优化

32、特征工程

目的：最大限度地从原始数据中提取特征以供算法和模型使用

特征工程：特征使用方案：需要哪些数据并做可用性评估（获取速度、覆盖率、准确率）

特征获取方案：如何获取、如何存储

特征处理

特征监控：特征有效分析（重要性、权重），监控重要特征（防止质量下降）

特征处理：特征清洗：清洗异常样本、采样（数据不均衡、样本权重）

预处理：单个特征：归一化、离散化、虚拟编码、缺失值处理

多个特征：降维（PCA、LDA）

特征选择：filter：自变量和目标变量之间地关联（相关系数、卡方检验、信息增益、互信息等）

wrapper：通过目标函数（AUC/MSE）来决定是否要加入一个变量；迭代，产生特征子集；评价

Embedded：学习器自身自动选择特征，正则化（LASSO、Ridge），决策树（熵、信息增益），深度学习

衍生变量：对原始数据做加工

33、数据不平衡问题解决方法

采样：随机采样、上采样（小样本复制或加噪声）、下采样（大样本剔出一些或只选大样本）

数据生成：利用已知样本生成新的样本

加权：Adaboost、SVM

采用对不平衡数据不敏感地算法

改变评价标准：AUC/ROC

采用集成方法

设计模型时考虑数据地先验分布

34、常见监督算法

感知机、SVM、人工神经网络、决策树、LR等

35、优化算法比较

随机梯度下降：优点：一定程度上解决局部最优解问题

缺点：收敛速度慢

批量梯度下降：优点：收敛速度快

缺点：容易陷入局部最优解

mini-batch梯度下降：是上述两种的中和方法

牛顿法：二阶，Hessian

拟牛顿法：逼近Hessian

36、特征向量归一化方法

线性函数转换： $\frac{x-min}{max-min}$

对数函数转换： $\frac{ln(x)}{ln(max)}$

反余切函数转换： $\frac{arctanx^2}{\pi }$

减去均值，除以标准差

38、共线性

多变量之间高度相关，会使结果不准确，会造成冗余导致过拟合

解决：PCA，排除变量相关性/加入权重正则

39、维度极低的特征

非线性分类器

40、偏差与方差

泛化误差可以分解为偏差^2 + 方差^2 + 噪声

偏差：度量了学习算法的期望与真实值的偏离程度，刻画拟合能力

方差：度量了同样大小训练集的变动导致学习性能的变化，刻画数据扰动所造成的影响

噪声：刻画问题本身难度

偏差：bias $E_D[(\bar{ f(x) }-y )^2]$

方差：variance $E_D[(f(x,D)-\bar{f(x)} )^2]$

high bias解决：boosting，复杂模型，增加特征

high variance解决：bagging，简化模型，降维

41、检查多重共线性

创建相关矩阵

计算VIF（方差膨胀因子）

用容差作为指标

42、选择重要变量

方法：1、选择之前除去相关变量

2、用线性回归然后基于P值选择

3、使用前向选择，后向选择，逐步选择

4、使用RF和XGBoost，然后画出变量重要性图

5、使用LASSO回归

6、测量可用的特征集的信息增益，并相应地选择前n个特征量

43、分类问题的抽样

使用分层抽样而不是随机抽样，前者考虑比例

44、连续特征可离散，可幅度缩放

离散化一般是线性模型用到，如LR

幅度缩放一般有计算模型里会用到，如LR，DNN

45、线性回归因变量

对线性回归，当因变量服从正态分布，误差项满足高斯-马尔可夫条件（零均值、等方差、不相关）时，回归参数的最小二乘估计是一致最小方差无偏估计。

线性回归的假设前提是噪声服从正态分布、即因变量服从正态分布。