追根溯源，算法岗面试「完整脉络」梳理：手推公式、通用问题、常见算法
共 5464字，需浏览 11分钟
·
2020-09-11 22:44
极市导读
正值2021秋招季，本文梳理了常见的机器学习面试题的完整脉络，包括手推公式、机器学习通用问题以及常见机器学习、深度学习算法等。内容非常详尽，可为正在准备面试的同学提供有效参考。
一.常见手推公式部分
1.1 LR手推、求导、梯度更新
1.2 SVM原形式、对偶形式
1.3 FM公式推导
1.4 GBDT手推
1.5 XGB推导
1.6 AUC计算
1.7 神经网络的反向传播
pytorch写简单DNN
二.常见机器学习通用问题
2.1评价指标
2.1.1 分类问题指标：
分类问题的评价指标大多基于混淆矩阵计算所得
缺点：类别比例不均衡时影响评价效果。
特点：AUC的评价效果不受正负样本比例的影响。因为改变正负样本比例，横纵坐标大小同时变化。整体不变。
2.1.2回归问题评价指标：
2.2.1 梯度下降法（gradient descent）
选择最陡峭的地方下山——这是梯度下降法的核心思想：它通过每次在当前梯度方向（最陡峭的方向）向前“迈”一步，来逐渐逼近函数的最小值。
梯度下降法根据每次求解损失函数LL带入的样本数，可以分为：全量梯度下降（计算所有样本的损失），批量梯度下降（每次计算一个batch样本的损失）和随机梯度下降（每次随机选取一个样本计算损失）。
缺点：
2.2.2 Momentum
为了解决随体梯度下降上下波动，收敛速度慢的问题，提出了Momentum优化算法，这个是基于SGD的，简单理解，就是为了防止波动，取前几次波动的平均值当做这次的W。
beta为新引入的超参，代表之前的dW的权重。
缺点：
依旧使用同一学习率alpha，比较难学习一个较好的学习率。
2.2.3 Adagrad
在前面介绍的算法中，每个模型参数θi使用相同的学习速率η，而Adagrad在每一个更新步骤中对于每一个模型参数θi使用不同的学习速率ηi。其更新方程为:
其中，Gt∈Rd×d是一个对角矩阵，其中第i行的对角元素eii为过去到当前第i个参数θi的梯度的平方和，epsilon是一个平滑参数，为了使得分母不为0。
缺点：
梯度衰减问题，Gt是不断增加的，导致学习率不断衰减，最终变得非常小。
2.2.4 RMSprop
RMSprop使用指数加权平均来代替历史梯度的平方和：
RMSprop对梯度较大的方向减小其学习速率，相反的，在梯度较小的方向上增加其学习速率。
缺点：
仍然需要全局学习率：n
2.2.5 Adam
Adam是Momentum 和 RMSprop的结合，被证明能有效适用于不同神经网络，适用于广泛的结构。是目前最常用的优化方法，优势明显。
简单选择方法：
数据量小可以用SGD。
稀疏数据则选择自适应学习率的算法；而且，只需设定初始学习率而不用再调整即很可能实现最好效果。
Adagrad, Adadelta, RMSprop, Adam可以视为一类算法。RMSprop 与 Adadelta本质相同，都是为了解决Adagrad的学习率消失问题。
目前来看，无脑用 Adam 似乎已经是最佳选择。
2.3 过拟合问题
1.解空间形状：加入正则化项即为约束条件：形成不同形状的约束解空间。
2 导数：L2的导数为2X，平滑。L1导数为X，-X，存在突变的极值点
3.先验：加入正则化项相当于引入参数的先验知识：L1引入拉普拉斯，L2引入高斯分布
L1可以做到特征筛选和得到稀疏解。L2加速训练
减小参数规模
随机丢弃产生不同网络，形成集成，解决过拟合，加速训练
加快训练、消除梯度消失（爆炸）、防止过拟合 不适用太小batch、CNN
常见激活函数
sigmoid只做值非线性变化映射到(0,1)，用于二分类。
softMax变化过程计算所有结果的权重，使得多值输出的概率和为1。用于多分类。指数运算速度慢。梯度饱和消失。
双曲正切函数。以0为中心，有归一化的作用。
大于0为1，小于0为0，计算速度快。
leaky输入为负时，梯度仍有值，避免死掉。
样本不平衡
模型评估指标
距离衡量与相似度
损失函数
MAE、MSE、Huber loss
通过极大似然估计生成似然函数，取对数求极大值--损失函数
用一个猜测的分布的编码去编码真实的分布，得到的信息量
交叉熵p(x)对应真实标记y，q(x)对应预测值。
特征选择的方法
覆盖率、皮尔逊相关系数、Fisher、最大方差阈值、卡方检验
决策树剪枝
WOE/IV值计算公式
常见的数据分箱方法
处理海量数据方法
Kmean缺陷与改进
随机森林
criterion：度量分裂质量，信息熵或者基尼指数
max_features：特征数达到多大时进行分割
max_depth:树的最大深度
min_samples_split:分割内部节点所需的最少样本数量
bootstrap:是否采用有放回式的抽样方式
min_impurity_split：树增长停止的阀值
XGB
max_depth、min_child_weigh：树深，孩子节点最小样本权重和
gamma、alpha、lambda：后剪枝比例，L1，L2正则化系数
subsample、colsample_bytree：样本采样、列采样
eta:削减已学树的影响，为后面学习腾空间
tree_method：gpu_histGPU 加速
LGB
-常用调参：
num_iterations、learning_rate：迭代次数，学习率
max_depth、min_data_in_leaf、num_leaves：控制树的大小
lambda_l1、lambda_l2、min_split_gain：L1、L2、最小切分
feature_fraction、bagging_fraction：随机采样特征和数据
device：GPU
GBDT、XGB、LGB比较
1.损失函数：加入正则化项：L1叶子节点数，L2叶子节点输出Score
2.导数：使用代价函数的二阶展开式来近似表达残差
3.基分类器：XGB支持线性分类器做基分类器
4.处理缺失值：寻找分割点时不考虑缺失值。分别计算缺失值在左右的增益。测试首出现缺失，默认在右。
5.近似直方图算法：采用加权分位数法来搜索近似最优分裂点 6.Shrinkage(缩减）：将学习到的模型*系数，削减已学模型的权重
7.列采样：特征采样。
8.并行计算：特征预排序，特征分裂增益计算（均在特征粒度上）
1.节点分裂准则：XGB一次分裂一层节点（浪费），LGB深度优先分裂（过拟合）
2.决策树算法：基于histogram直方图分箱操作。减存加速
3.直接支持类别特征，无需独热操作
4.特征并行，数据并行
5.GOSS：单边采样：保留大梯度样本，随机采样小梯度样本
6EFB：归并很少出现的特征为同一类
Stacking和Blending
LDA、PCA与SVD
线性判别分析 Linear Discriminate Analysis（监督）
PCA用于方阵矩阵分解
SVD用于一般矩阵分解 - LDA（类别区分最大化方向投影）
在标签监督下，进行类似PCA的主成分分析
构造类间的散布矩阵 SB 以及 类内散布矩阵 SW - PCA（方差最大化方向投影） 构建协方差矩阵 最大化投影方差：信号具有较大方差，让数据在主轴方向投影方差最大 最小平方误差：方差最大，即样本点到直线距离最小（最小平方误差）
- SVD
左右为正交矩阵：用于压缩行、列 中间为对角阵：奇异值
SVM
方便核函数的引入（转化后为支持向量内积计算，核函数可以在低纬中计算高维的内积），改变复杂度（求W变成求a（支持向量数量））
有效性：核函数矩阵KK是对称半正定矩阵
常见核函数：线性核函数，多项式核函数，高斯核函数，指数核函数
区别：线性简单，可解释性强，只用于线性可分问题。多项式可解决非线性，参数太多。高斯只需要一个参数，计算慢，容易过拟合。
特征维数高选择线性核
样本数量可观、特征少选择高斯核（非线性核）
样本数量非常多选择线性核（避免造成庞大的计算量）
EM
用于含有隐变量的概率模型参数的极大似然估计
推荐阅读
