面试准备基础算法篇

作者: 小石头在长大 | 来源:发表于2019-06-29 15:23 被阅读50次

    机器学习:

    继承学习:bagging、boosting、stacking的区别

    指标:准确率、召回率、f1、auc,阈值变化的影响

    阈值提升,tp减少,tn增大,tp+tn不变,fp减少,fn增大,准确率不变,精确率提高,召回率下降

    类别比例1:100,召回率99%,误报率1%(1-精确率),求准确率

    https://www.jianshu.com/p/665f9f168eff

    https://www.jianshu.com/p/4dde15a56d44

    https://www.cnblogs.com/taro/p/8643335.html

    https://blog.csdn.net/u013006675/article/details/81589782

    梯度下降陷入局部最优:

    batch gd非凸函数收敛局部最优,sgd收敛速度慢,mini batch提高学习速度,momentum加上一次更新量,对方向相同的参数加速学习,梯度改变方向的参数减少更新,抑制震荡,加速收敛,难以学习较好的学习率,anagrad每个参数使用不同的学习率,学习速率衰减过快,rmsprop在梯度大的方向减小学习率,梯度小的方向增大学习率,依赖全局学习率,adam结合了anagrad和rmrsprop的优点

    自适应性算法https://www.jianshu.com/p/1ec8c1c01e8a

    l1l2正则:

    正则是范数,l1是所有参数绝对值相加,l2是所有参数平方和开根号,目标是优化损失函数+正则,当损失函数和正则相切的时候取最小值,l1正则容易使权重为0,l2正则使权重趋向于更小,防止过拟合

    https://blog.csdn.net/jinping_shi/article/details/52433975

    https://blog.csdn.net/red_stone1/article/details/80755144

    lr推导:

    似然函数是每一个样本概率的联合概率分布,sigmoid函数的导数是(1-f(x))*f(x)

    https://www.jianshu.com/p/e8dca5613da6

    lr离散化:

    优点,增加减少都很容易,便于调整,增强特征鲁棒性,增强特征表达能力,引入非线性

    https://blog.csdn.net/suv1234/article/details/72628919

    极大似然估计:https://blog.csdn.net/qq_39355550/article/details/81809467

    决策树系列:

    分类变量直接计算信息增益,连续变量先将变量升序,按照两个点的加权均值进行分裂

    https://www.jianshu.com/p/3a6162ca4aa2

    https://blog.csdn.net/roguesir/article/details/76619919

    4、剪枝有哪几种方式(贝壳)

    前剪枝和后剪枝,参考周志华《机器学习》。预剪枝提前结束决策树的省长,后剪枝效果更好,但是后剪枝会浪费在叔的生长过程中的计算。

    5、树集成模型有哪几种实现方式?(贝壳)boosting和bagging的区别是什么?(知乎、阿里)

    树集成模型主要有两种实现方式,分别是Bagging和Boosting。二者的区别主要有以下四点:

    1)样本选择上:

    Bagging:训练集是在原始集中有放回选取的,从原始集中选出的各轮训练集之间是独立的.

    Boosting:每一轮的训练集不变,只是训练集中每个样例在分类器中的权重发生变化.而权值是根据上一轮的分类结果进行调整.

    2)样例权重:

    Bagging:使用均匀取样,每个样例的权重相等

    Boosting:根据错误率不断调整样例的权值,错误率越大则权重越大.

    3)预测函数:

    Bagging:所有预测函数的权重相等.

    Boosting:每个弱分类器都有相应的权重,对于分类误差小的分类器会有更大的权重.

    4)并行计算:

    Bagging:各个预测函数可以并行生成

    Boosting:各个预测函数只能顺序生成,因为后一个模型参数需要前一轮模型的结果.

    6、随机森林的随机体现在哪些方面(贝壳、阿里)

    随机森林的随机主要体现在两个方面:一个是建立每棵树时所选择的特征是随机选择的;二是生成每棵树的样本也是通过有放回抽样产生的。

    从原始训练样本集N中有放回地重复随机抽取n个样本生成新的训练样本集合训练决策树,然后按以上步骤生成m棵决策树组成随机森林,新数据的分类结果按分类树投票多少形成的分数而定。

    随机森林大致过程如下:

    1)从样本集中有放回随机采样选出n个样本;

    2)从所有特征中随机选择k个特征,对选出的样本利用这些特征建立决策树(一般是CART,也可是别的或混合);

    3)重复以上两步m次,即生成m棵决策树,形成随机森林;

    4)对于新数据,经过每棵树决策,最后投票确认分到哪一类。

    2.随机森林特点:

    随机森林有很多优点:

    1) 每棵树都选择部分样本及部分特征,一定程度避免过拟合;

    2) 每棵树随机选择样本并随机选择特征,使得具有很好的抗噪能力,性能稳定;

    3) 能处理很高维度的数据,并且不用做特征选择;

    4) 适合并行计算;

    5) 实现比较简单;

    缺点:

    1) 参数较复杂;

    2) 模型训练和预测都比较慢。

    7、AdaBoost是如何改变样本权重,GBDT分类树的基模型是?(贝壳)

    AdaBoost改变样本权重:增加分类错误的样本的权重,减小分类正确的样本的权重。

    最后一个问题是我在面试之前没有了解到的,GBDT无论做分类还是回归问题,使用的都是CART回归树。

    8、gbdt,xgboost,lgbm的区别(百度、滴滴、阿里,头条)

    首先来看GBDT和Xgboost,二者的区别如下:

    1)传统 GBDT 以 CART 作为基分类器,xgboost 还支持线性分类器,这个时候 xgboost 相当于带 L1 和 L2 正则化项的逻辑斯蒂回归(分类问题)或者线性回归(回归问题)。

    2)传统 GBDT 在优化时只用到一阶导数信息,xgboost 则对代价函数进行了二阶泰勒展开,同时用到了一阶和二阶导数。顺便 一下,xgboost 工具支持自定义代价函数,只要函数可一阶和二阶求导。

    3)xgboost 在代价函数里加入了正则项,用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的 score 的 L2 模的平方和。从 Bias-variance tradeoff 角度来讲,正则项降低了模型的variance,使学习出来的模型更加简单,防止过拟合,这也是 xgboost 优于传统GBDT 的一个特性。

    4)Shrinkage(缩减),相当于学习速率(xgboost 中的eta)。xgboost 在进行完一次迭代后,会将叶子节点的权重乘上该系数,主要是为了削 弱每棵树的影响,让后面有更大的学习空间。实际应用中,一般把 eta 设置得小一点,然后迭代次数设置得大一点。(补充:传统 GBDT 的实现 也有学习速率)

    5)列抽样(column subsampling)。xgboost 借鉴了随机森林的做法,支 持列抽样,不仅能降低过拟合,还能减少计算,这也是 xgboost 异于传 统 gbdt 的一个特性。

    6)对缺失值的处理。对于特征的值有缺失的样本,xgboost 可以自动学习 出它的分裂方向。

    7)xgboost 工具支持并行。boosting 不是一种串行的结构吗?怎么并行的? 注意 xgboost 的并行不是 tree 粒度的并行,xgboost 也是一次迭代完才能进行下一次迭代的(第 t 次迭代的代价函数里包含了前面 t-1 次迭代 的预测值)。xgboost 的并行是在特征粒度上的。我们知道,决策树的学习最耗时的一个步骤就是对特征的值进行排序(因为要确定最佳分割点),xgboost在训练之前,预先对数据进行了排序,然后保存为 block 结构,后面的迭代中重复地使用这个结构,大大减小计算量。这个block结构也使得并行成为了可能,在进行节点的分裂时,需要计算每 个特征的增益,最终选增益最大的那个特征去做分裂,那么各个特征的增益计算就可以开多线程进行。

    8)可并行的近似直方图算法。树节点在进行分裂时,我们需要计算每个特征的每个分割点对应的增益,即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下,贪心算法效率就会变得很低,所以 xgboost 还 出了一种可并行的近似直方图算法,用于高效地生成候选的分割点。

    再来看Xgboost和LightGBM,二者的区别如下:

    1)由于在决策树在每一次选择节点特征的过程中,要遍历所有的属性的所有取 值并选择一个较好的。XGBoost 使用的是近似算法算法,先对特征值进行排序 Pre-sort,然后根据二阶梯度进行分桶,能够更精确的找到数据分隔点;但是 复杂度较高。LightGBM 使用的是 histogram 算法,这种只需要将数据分割成不同的段即可,不需要进行预先的排序。占用的内存更低,数据分隔的复杂度更低。

    2)决策树生长策略,我们刚才介绍过了,XGBoost采用的是 Level-wise 的树 生长策略,LightGBM 采用的是 leaf-wise 的生长策略。

    3)并行策略对比,XGBoost 的并行主要集中在特征并行上,而 LightGBM 的并 行策略分特征并行,数据并行以及投票并行。

    9、bagging为什么能减小方差?(知乎)

    这个当时也没有答上来,可以参考一下博客:https://blog.csdn.net/shenxiaoming77/article/details/53894973

    树模型相关的题目以上就差不多了。接下来整理一些最近群友提出的问题,我觉得有一些可能作为面试题,有一些是准备校招过程中的经验:

    10、关于AUC的另一种解释:是挑选一个正样本和一个负样本,正样本排在负样本前面的概率?如何理解?

    我们都知道AUC是ROC曲线下方的面积,ROC曲线的横轴是真正例率,纵轴是假正例率。我们可以按照如下的方式理解一下:首先偷换一下概念,意思还是一样的,任意给定一个负样本,所有正样本的score中有多大比例是大于该负类样本的score?那么对每个负样本来说,有多少的正样本的score比它的score大呢?是不是就是当结果按照score排序,阈值恰好为该负样本score时的真正例率TPR?理解到这一层,二者等价的关系也就豁然开朗了。ROC曲线下的面积或者说AUC的值 与 测试任意给一个正类样本和一个负类样本,正类样本的score有多大的概率大于负类样本的score是等价的。

    xgboost:

    https://www.jianshu.com/p/c32af083be5b

    https://www.jianshu.com/p/c558d0448ac7

    调参:

    1、选择较高的学习速率(learning rate),0.1,通过cv确定决策树的数量  

    2、 max_depth 和 min_weight 两个参数同时调,网格搜索  

    3、gamma 分裂节点时,损失函数减小值只有大于等于gamma节点才分裂 

    4、调整subsample 和 colsample_bytree subsamle是构建每棵树对样本的采样率,如果设置成0.5,XGBoost会随机选择一半的样本作为训练集。colsamle列采样率,也就是特征采样率。

    5、正则参数 reg_alpha l1 

    6、减小学习率

    https://blog.csdn.net/han_xiaoyang/article/details/52665396

    https://blog.csdn.net/anshuai_aw1/article/details/82970489

    rf和xgb的区别:

    http://www.sohu.com/a/274023024_100285715

    https://blog.csdn.net/blank_tj/article/details/82453535

    softmax和交叉熵:https://www.jianshu.com/p/2b35be46a098?utm_source=oschina-app

    https://blog.csdn.net/bitcarmanlee/article/details/82320853

    tf-idf公式:

    tf-idf=tf*idf。tf为文档中的词频比率,idf为log(文档总数/(包含该词文档总数+1))

    http://www.360baidu.cn/seo/tf-idf.html

    fm:fm和ffm时间复杂度和参数个数

    Wij的权重矩阵为n*k的vi矩阵和k*n的vj矩阵相乘

    https://www.jianshu.com/p/152ae633fb00?utm_campaign=maleskine&utm_content=note&utm_medium=seo_notes&utm_source=recommendation

    deepfm:https://www.jianshu.com/p/e7b2d53ec42b

    wide&deep:https://blog.csdn.net/Zhangbei_/article/details/90544265

    深度学习:

    embedding:https://blog.csdn.net/l7H9JA4/article/details/86326935万物皆embedding

    https://www.jianshu.com/p/e8986d0ff4ff

    为什么要做深度学习不是宽度学习:

    从实验结果来看,深度较少的神经元拟合比浅度较多神经元拟合好

    跟样本的数量有关

    https://blog.csdn.net/pengchengliu/article/details/89393016

    激活函数:

    增加神经网络的非线性拟合

    sigmoid:容易梯度消失、不是0均值,导师要么为正要么为负,收敛慢、前向和反向传播计算量大

    relu:计算量小,收敛速度非常快、是一部分神经元输出为0,减少过拟合、在正区间解决了梯度消失的问题,不是0均值函数。缺点:某些神经元永远不会被激活,原因是(1) 非常不幸的参数初始化,这种情况比较少见 (2) learning rate太高导致在训练过程中参数更新太大,不幸使网络进入这种状态。使用anagrad等自适应调参方式可以解决。还有解决方法:leak relu

    tanh:是0均值函数,梯度消失和幂运算的问题仍然存在

    https://www.cnblogs.com/ya-qiang/p/9258714.html

    bn:

    原因:1、训练和测试数据分布不一致,泛化能力降低 2、训练每一个batch的分布不同,参数要重新适应新的分布,训练速度降低

    训练的时候,数据往激活函数上下两边偏移,导致梯度消失,无法收敛,bn把数据分布拉回到正态分布,避免梯度消失的问题

    好处:收敛速度大大加快,不用各种调学习率,可以不用设置dropout、l1、l2正则,解决过拟合,梯度消失,梯度爆炸

    https://www.jianshu.com/p/94f7985a957d

    https://blog.csdn.net/lx10271129/article/details/78984623

    优化函数

    word2vec:

    神经网络模型——层次softmax——负采样

    神经网络模型:输入层——词向量连接到投影层——隐藏层词向量——输出层softmax

    层次softmax:输入层——词向量累加平均到投影层——哈夫曼树

    负采样:输入层——词向量累加平均到投影层——输出

    https://www.cnblogs.com/pinard/p/7160330.html

    https://www.jianshu.com/p/a6321cd6e003

    https://www.jianshu.com/p/44139f1b46c5

    https://www.jianshu.com/p/d534570272a6

    https://www.jianshu.com/p/1c73e01f9e5c

    https://www.jianshu.com/p/9b64d98b0fcb

    https://www.jianshu.com/p/471d9bfbd72f

    bp前向传播和反向传播:

    https://www.jianshu.com/p/ee08ed75844b

    tensorflow实现https://blog.csdn.net/gaoyueace/article/details/79017532

    numpy实现https://blog.csdn.net/francislucien2017/article/details/86762178

    https://blog.csdn.net/u014303046/article/details/78200010

    https://blog.csdn.net/sxf1061926959/article/details/72728244

    https://blog.csdn.net/shaomingliang499/article/details/50587300

    cnn:

    卷积层:稀疏链接,权值共享,减少参数个数,提高训练速度

    池化层:最大池化,减少参数个数,减少过拟合

    https://www.jianshu.com/p/49ab6568e472

    https://blog.csdn.net/u014303046/article/details/86021346

    https://blog.csdn.net/wwwq2386466490/article/details/79004814

    https://www.cnblogs.com/skyfsm/p/6790245.html

    https://www.cnblogs.com/charlotte77/p/7783261.html

    tensorflow实现:https://blog.csdn.net/skullFang/article/details/80434973

            numpy实现:https://github.com/ahmedfgad/NumPyCNN/blob/master/NumPyCNN.py

    textcnn:本地代码

    三个大小为[3,4,5]的卷积核,分别卷积,relu,最大池化后拼接在一起,flat后输入给全连接

    https://www.jianshu.com/p/5a6c63149708

    https://www.cnblogs.com/bymo/p/9675654.html

    bptt推导:

    https://zhuanlan.zhihu.com/p/28687529

    https://zhuanlan.zhihu.com/p/28749444

    https://blog.csdn.net/Dark_Scope/article/details/47056361

    textrnn:

    将rnn前向输出和后向输出拼接起来,输入给全连接层

    https://www.cnblogs.com/xuruilong100/p/8506949.html

    https://www.jianshu.com/p/b38760250281

    https://blog.csdn.net/wcx1293296315/article/details/81228575

    https://blog.csdn.net/zhangbaoanhadoop/article/details/81952284

    https://blog.csdn.net/qq_32241189/article/details/80461635

    https://blog.csdn.net/Torero_lch/article/details/82588732

    https://www.libinx.com/2018/text-classification-rnn-by-tensorflow/

    https://www.jianshu.com/p/e2f807679290

    lstm:tensorflow实现:https://blog.csdn.net/kirito_pio/article/details/85165398

    双向lstm和lstm的区别:https://www.jianshu.com/p/9c96354fc767

    https://blog.csdn.net/w275840140/article/details/89503458

    attention:

    将前向输出和后向输出相加,将这个和经过tanh非线性变换,和初始化权重相乘,softmax归一化,对原始输出加权求和,tanh,dropout后接全连接层

    https://www.zhihu.com/question/68482809/answer/264632289

    https://www.cnblogs.com/jiangxinyang/p/9367497.html

    https://www.cnblogs.com/jiangxinyang/p/10208227.html

    https://www.cnblogs.com/huangyc/p/10409626.html

    损失函数、公式

    transformer:

    生成position位置向量,与原始词向量拼接,定义q,k,v三个全连接层,激活函数为relu,将q,k,v切分为多头,计算切分后q和k的点积相似度,除以向量的长度的根号,将相似度进行softmax归一化,对v求加权和,将多头的结果拼接起来,dropout,加上原始向量,建立参差连接,normalize归一化,后接前向传播神经网络

    https://baijiahao.baidu.com/s?id=1622064575970777188&wfr=spider&for=pc

    https://www.cnblogs.com/huangyc/p/9813907.html

    https://www.cnblogs.com/jiangxinyang/p/10069330.html

    https://kexue.fm/archives/4765

    https://www.jianshu.com/p/b1030350aadb

    transformer结构

    防止过拟合的方法:L1和L2正则化、数据增强、Early stopping、dropout、交叉验证、决策树剪枝、减少模型大小

    https://www.jianshu.com/p/1ec8c1c01e8a

    spark:

    https://www.jianshu.com/p/8d578b46d0c6

    相关文章

      网友评论

        本文标题:面试准备基础算法篇

        本文链接:https://www.haomeiwen.com/subject/dqhpcctx.html