精华内容
下载资源
问答
  • 机器学习面经

    千次阅读 2018-08-10 11:27:02
    机器学习面经 1. 机器学习常见面试问题 算法要从以下几个方面来掌握: 产生背景,适用场合(数据规模,特征维度,是否有 Online 算法,离散/连续特征处理等角度); 原理推导(最大间隔,软间隔,对偶); 求解...

    机器学习面经

    1. 机器学习常见面试问题

    • 算法要从以下几个方面来掌握:
      1. 产生背景,适用场合(数据规模,特征维度,是否有 Online 算法,离散/连续特征处理等角度);
      2. 原理推导(最大间隔,软间隔,对偶);
      3. 求解方法(随机梯度下降、拟牛顿法等优化算法);
      4. 优缺点,相关改进;
      5. 和其他基本方法的对比;

    1.1 各模型优缺点

    • SVM

      • 特性:

        1. 非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射;
        2. 对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心;
        3. 支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量;
        4. SVM 是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律,因此不同于现有的统计方法。从本质上看,它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的 “转导推理”,大大简化了通常的分类和回归等问题。
        5. SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了 “维数灾难”。
        6. 少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。这种“鲁棒”性主要体现在:
          a. 增、删非支持向量样本对模型没有影响;
          b. 支持向量样本集具有一定的鲁棒性;
          c. 有些成功的应用中,SVM 方法对核的选取不敏感;
        7. SVM学习问题可以表示为凸优化问题,因此可以利用已知的有效算法发现目标函数的全局最小值。而其他分类方法(如基于规则的分类器和人工神经网络)都采用一种基于贪心学习的策略来搜索假设空间,这种方法一般只能获得局部最优解。
        8. SVM通过最大化决策边界的边缘来控制模型的能力。尽管如此,用户必须提供其他参数,如使用核函数类型和引入松弛变量等。
        9. SVM在小样本训练集上能够得到比其它算法好很多的结果。支持向量机之所以成为目前最常用,效果最好的分类器之一,在于其优秀的泛化能力,这是是因为其本身的优化目标是结构化风险最小,而不是经验风险最小,因此,通过margin的概念,得到对数据分布的结构化描述,因此减低了对数据规模和数据分布的要求。SVM也并不是在任何场景都比其他算法好,对于每种应用,最好尝试多种算法,然后评估结果。如SVM在邮件分类上,还不如逻辑回归、KNN、bayes的效果好。
        10. 它基于结构风险最小化原则,这样就避免了过学习问题,泛化能力强。
        11. 它是一个凸优化问题,因此局部最优解一定是全局最优解的优点。
        12. 泛华错误率低,分类速度快,结果易解释
      • 不足:

        1. SVM算法对大规模训练样本难以实施
          SVM的空间消耗主要是存储训练样本和核矩阵,由于SVM是借助二次规划来求解支持向量,而求解二次规划将涉及 m 阶矩阵的计算(m为样本的个数),当 m 数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。针对以上问题的主要改进有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM以及O.L.Mangasarian等的SOR算法。
          如果数据量很大,SVM的训练时间就会比较长,如垃圾邮件的分类检测,没有使用SVM分类器,而是使用了简单的naive bayes分类器,或者是使用逻辑回归模型分类。
        2. 用SVM解决多分类问题存在困难
          经典的支持向量机算法只给出了二类分类的算法,而在数据挖掘的实际应用中,一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树;再就是通过构造多个分类器的组合来解决。主要原理是克服SVM固有的缺点,结合其他算法的优势,解决多类问题的分类精度。如:与粗集理论结合,形成一种优势互补的多类问题的组合分类器。
        3. 对缺失数据敏感,对参数和核函数的选择敏感
          支持向量机性能的优劣主要取决于核函数的选取,所以对于一个实际问题而言,如何根据实际的数据模型选择合适的核函数从而构造SVM算法。目前比较成熟的核函数及其参数的选择都是人为的,根据经验来选取的,带有一定的随意性。在不同的问题领域,核函数应当具有不同的形式和参数,所以在选取时候应该将领域知识引入进来,但是目前还没有好的方法来解决核函数的选取问题。
      • 支持向量机的主要应用和研究的热点
        目前支持向量机主要应用在模式识别领域中的文本识别,中文分类,人脸识别等;同时也应用到许多的工程技术和信息过滤等方面。
        当前研究的热点主要是对支持向量机中算法的优化,包括解决SVM中二次规划求解问题,对大规模SVM的求解问题,对SVM中QP问题的求解问题等,另外就是如何更好的构造基于SVM的多类分类器,如何提高SVM的归纳能力和分类速度等,如何根据实际问题确定核函数也是一个重要的研究热点。
    • LR

      • 优点

        1. 实现简单,广泛的应用于工业问题上;
        2. 分类时计算量非常小,速度很快,存储资源低;
        3. 便利的观测样本概率分数;
        4. 对逻辑回归而言,多重共线性并不是问题,它可以结合L2正则化来解决该问题;
      • 不足

        1. 当特征空间很大时,逻辑回归的性能不是很好;
        2. 容易欠拟合,一般准确度不太高;
        3. 不能很好地处理大量多类特征或变量;
        4. 只能处理两分类问题(在此基础上衍生出来的softmax可以用于多分类),且必须线性可分;
    • 决策树

      • 优点

        1. 决策树易于理解和实现. 人们在通过解释后都有能力去理解决策树所表达的意义。
        2. 需要准备的数据量不大,而其他的技术往往需要很大的数据集,需要创建虚拟变量,去除不完整的数据,但是该算法对于丢失的数据不能进行准确的预测
        3. 决策树算法的时间复杂度(即预测数据)是用于训练决策树的数据点的对数
        4. 对于决策树,数据的准备往往是简单或者是不必要的。其他的技术往往要求先把数据一般化,比如去掉多余的或者空白的属性。
        5. 能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。
        6. 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
        7. 对缺失值不敏感
        8. 可以处理不相关特征数据
        9. 效率高,决策树只需要一次构建,反复使用,每一次预测的最大计算次数不超过决策树的深度。
      • 不足

        1. 决策树算法学习者可以创建复杂的树,但是没有推广依据,这就是所谓的过拟合,为了避免这种问题,出现了剪枝的概念,即设置一个叶子结点所需要的最小数目或者设置树的最大深度
        2. 决策树的结果可能是不稳定的,因为在数据中一个很小的变化可能导致生成一个完全不同的树,这个问题可以通过使用集成决策树来解决
        3. 众所周知,学习一恶搞最优决策树的问题是NP——得到几方面完全的优越性,甚至是一些简单的概念。因此,实际决策树学习算法是基于启发式算法,如贪婪算法,寻求在每个节点上的局部最优决策。这样的算法不能保证返回全局最优决策树。这可以减轻训练多棵树的合奏学习者,在那里的功能和样本随机抽样更换。
        4. 在处理特征关联性比较强的数据时表现得不是太好

    1.2 过拟合原因

    数据:数据不规范,数据量少,数据穿越,统计特征用到了未来的信息或者标签信息
    算法:算法过于复杂
    解决:
    1. 将数据规范化,处理缺失值,增加数据量,采样,添加噪声数据
    2. 正则化,控制模型复杂程度
    3. early stoping,减少迭代次数,减少树的深度
    4. 学习率调大/小点
    5. 融合几个模型
    6. dropout、regularization、batch normalizatin

    1.3 L1和L2的区别

    1. L1是Lasso Regression,表示向量中每个元素绝对值的和:L1范数的解通常是稀疏性的,倾向于选择数目较少的一些非常大的值或者数目较多的 insignificant 的小值。
    2. L2是岭回归,Ridge Regression,是欧氏距离也就是平方和的平方根。L2范数越小,可以使得w的每个元素都很小,接近于0,但与 L1 范数不同的是他不会让它等于 0 而是接近于 0。
    3. L1 正则化的w可取的值是转置的方形,L2 对应的是圆形。这样损失函数 lw l ( w ) 的最小值更容易在 L1 对应的边角上取得,从而这些维度变成 0 了。
    4. 从贝叶斯的角度来看,加入正则项相当于加入了一种先验。即当训练一个模型时,仅依靠当前的训练数据集是不够的,为了实现更好的泛化能力,往往需要加入先验项。
      L1范数相当于加入了一个Laplacean先验;
      L2范数相当于加入了一个Gaussian先验。
      L2对大数的惩罚更大,但是解相对来说比较均匀。

    1.4 生成模型和判别模型区别

    • 对于输入x,类别标签y:
      生成式模型先求它们的联合概率分布 P(x,y) P ( x , y ) ,然后根据贝叶斯定理求 P(y|x) P ( y | x )

      判别式模型直接求条件概率分布 P(y|x) P ( y | x )

    • 常见的判别模型有:K近邻、SVM、决策树、感知机、线性判别分析(LDA)、线性回归、传统的神经网络、逻辑斯蒂回归、boosting、条件随机场

    • 常见的生成模型有:朴素贝叶斯、隐马尔可夫模型、高斯混合模型、文档主题生成模型(LDA)、限制玻尔兹曼机

    1.5 SVM 算法

    1. SVM是一种二类分类的模型,它的基本模型是在特征空间中寻找间隔最大化的分离超平面的线性分类器。
    2. 惩罚因子 C 决定了你有多重视离群点带来的损失,显然当所有离群点的松弛变量的和一定时,你定的 C 越大,对目标函数的损失也越大,此时就暗示着你非常不愿意放弃这些离群点,最极端的情况是你把C定为无限大,这样只要稍有一个点离群,目标函数的值马上变成无限大,马上让问题变成无解,这就退化成了硬间隔问题。
    3. 惩罚因子C不是一个变量,整个优化问题在解的时候,C是一个你必须事先指定的值,指定这个值以后,解一下,得到一个分类器,然后用测试数据看看结果怎么样,如果不够好,换一个C的值,再解一次优化问题,得到另一个分类器,再看看效果,如此就是一个参数寻优的过程,但这和优化问题本身决不是一回事,优化问题在解的过程中,C一直是定值,要记住。
    4. 解决过拟合的办法是为 SVM 引入了松弛变量 ξ ξ (slack variable),将SVM公式的约束条件改为 12||w||2+CNi=1ξi 1 2 | | w | | 2 + C ∑ i = 1 N ξ i 。因为松弛变量能够容忍异常点的存在,我们的支持向量和超平面尽量不会受到它的影响。 我们加上松弛变量的平方和,并求最小值。这样就达到一个平衡:
      既希望松弛变量存在以解决异常点问题,又不希望松弛变量太大导致分类解决太差。

    1.6 LR和SVM的联系与区别

    • 联系:
      1. LR和SVM都可以处理分类问题,且一般都用于处理线性二分类问题(在改进的情况下可以处理多分类问题)
      2. 两个方法都可以增加不同的正则化项,如 L1、L2 等等。所以在很多实验中,两种算法的结果是很接近的。
    • 区别:
      1. LR是参数模型,SVM是非参数模型。
      2. 从目标函数来看,区别在于逻辑回归采用的是 logistical loss,SVM采用的是 hinge loss。这两个损失函数的目的都是增加对分类影响较大的数据点的权重,减少与分类关系较小的数据点的权重。
      3. SVM的处理方法是只考虑 support vectors,也就是和分类最相关的少数点,去学习分类器。而逻辑回归通过非线性映射,大大减小了离分类平面较远的点的权重,相对提升了与分类最相关的数据点的权重。
      4. 逻辑回归相对来说模型更简单,好理解,特别是大规模线性分类时比较方便。而SVM的理解和优化相对来说复杂一些,SVM转化为对偶问题后,分类只需要计算与少数几个支持向量的距离,这个在进行复杂核函数计算时优势很明显,能够大大简化模型和计算。
      5. LR 能做的 SVM 能做,但可能在准确率上有问题,SVM 能做的 LR 有的做不了。

    1.7 RF GBDT XGBoost的区别与联系

    • Gradient boosting(GB)
      机器学习中的学习算法的目标是为了优化或者说最小化 Loss Function, Gradient boosting 的思想是迭代生多个(M个)弱的模型,然后将每个弱模型的预测结果相加,后面的模型 Fm+1(x) F m + 1 ( x ) 基于前面学习模型的 Fm(x) F m ( x ) 的效果生成的。

    • Gradient boosting Decision Tree(GBDT)
      GB 算法中最典型的基学习器是决策树,尤其是 CART,正如名字的含义,GBDT是GB和DT的结合。要注意的是这里的决策树是回归树,GBDT中的决策树是个弱模型,深度较小一般不会超过5,叶子节点的数量也不会超过 10,对于生成的每棵决策树乘上比较小的缩减系数(学习率 < 0.1),有些GBDT的实现加入了随机抽样( subsample0.5f0.8 s u b s a m p l e 0.5 ≤ f ≤ 0.8 )提高模型的泛化能力。通过交叉验证的方法选择最优的参数。

    • XGBoost
      XGBoost是 GB 算法的高效实现,XGBoost中的基学习器除了可以是CART(GB tree)也可以是线性分类器(GB linear)。

      1. XGBoost在目标函数中显示的加上了正则化项,基学习为CART时,正则化项与树的叶子节点的数量 T T 和叶子节点的值有关。
      2. GB中使用 Loss Function 对 f(x) 的一阶导数计算出伪残差用于学习生成 fm(x) f m ( x ) ,XGBoost 不仅使用到了一阶导数,还使用二阶导数。
      3. 上面提到 CART 回归树中寻找最佳分割点的衡量标准是最小化均方差,XGBoost 寻找分割点的标准是最大化,lamda,gama与正则化项相关。

        • XGBoost 算法的步骤和 GB 基本相同,都是首先初始化为一个常数,GB 是根据一阶导数 ri r i ,XGBoost 是根据一阶导数 gi g i 和二阶导数 hi h i ,迭代生成基学习器,相加更新学习器。

        • XGBoost 与 GBDT 除了上述三点的不同,XGBoost 在实现时还做了许多优化:

          1. 在寻找最佳分割点时,考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低,XGBoost 实现了一种近似的算法。大致的思想是根据百分位法列举几个可能成为分割点的候选者,然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。
          2. XGBoost 考虑了训练数据为稀疏值的情况,可以为缺失值或者指定的值指定分支的默认方向,这能大大提升算法的效率,paper 提到50倍。 特征列排序后以块的形式存储在内存中,在迭代中可以重复使用;虽然 XGBoost 算法迭代必须串行,但是在处理每个特征列时可以做到并行。 按照特征列方式存储能优化寻找最佳的分割点,但是当以行计算梯度数据时会导致内存的不连续访问,严重时会导致 cache miss,降低算法效率。paper中提到,可先将数据收集到线程内部的buffer,然后再计算,提高算法的效率。
          3. xgboost 还考虑了当数据量比较大,内存不够时怎么有效的使用磁盘,主要是结合多线程、数据压缩、分片的方法,尽可能的提高算法的效率。
    • Random Forest:
      bagging (原本叫Bootstrap aggregating)
      bagging 的关键是重复的对经过 bootstrapped 采样来的观测集子集进行拟合。然后求平均。一个 bagged tree 充分利用近2/3的样本集。所以就有了OOB预估(out of bag estimation)

      学习随机森林模型前,一定要先了解决策树模型。树越深,模型越复杂。

      • 决策树模型的优点如下:
        1. 容易理解和解释,树可以被可视化。
        2. 不需要太多的数据预处理工作,即不需要进行数据归一化,创造哑变量等操作。
        3. 隐含地创造了多个联合特征,并能够解决非线性问题。
      • 决策树模型最大的缺点是容易过拟合。
      • 随机森林由很多棵不同的决策树构成,对于一个给定的预测对象,每棵决策树都输出一个 label,最后采取“投票”的方式,选择得票最多的 label 作为最终结果。随机森林是一种集成方法,也被认为是最近邻预测器的一种。集成方法是将一组弱分类器以一定的方式组合起来,形成一个强分类器。
      • 随机森林的错误率依赖两件事:
        1. 树之间的相关性越大,整体错误率越高。
        2. 单棵树的错误率越高,整体错误率越高。
      • 随机森林的优点与缺点:
        • 优点:
          1. 容易理解和解释,树可以被可视化。
          2. 不需要太多的数据预处理工作,即不需要进行数据归一化,创造哑变量等操作。
          3. 隐含地创造了多个联合特征,并能够解决非线性问题。
          4. 和决策树模型,GBDT模型相比,随机森林模型不容易过拟合。
          5. 自带out-of-bag (oob)错误评估功能。
          6. 易于并行化。
        • 缺点:
          1. 不适合小样本,只适合大样本。
          2. 大多数情况下,RF模型的精度略低于GBDT模型的精度。
          3. 适合决策边界是矩形的,不适合对角线型的。
    • GBDT和随机森林的相同点与不同点:

      • 相同点:

        1. 都是由多棵树组成
        2. 最终的结果都是由多棵树一起决定
      • 不同点:

        1. 组成随机森林的树可以是分类树,也可以是回归树;而GBDT只由回归树组成
        2. 组成随机森林的树可以并行生成;而 GBDT 只能是串行生成
        3. 对于最终的输出结果而言,随机森林采用多数投票等;而GBDT则是将所有结果累加起来,或者加权累加起来
        4. 随机森林对异常值不敏感,GBDT对异常值非常敏感
        5. 随机森林对训练集一视同仁,GBDT是基于权值的弱分类器的集成
        6. 随机森林是通过减少模型方差提高性能,GBDT是通过减少模型偏差提高性能
        7. 随机森林不需要进行数据预处理,即特征归一化。而GBDT则需要进行特征归一化
    • XBGoost 比 GBDT 好的地方:
      二阶泰勒展开
      节点分数惩罚
      增益计算不同,GBDT 是 gini,XBGoost 是优化推导公式

    • XGBoost 泰勒展开的优势
      XGBoost 使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得二阶倒数形式, 可以在不选定损失函数具体形式的情况下用于算法优化分析.本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了 XGBoost 的适用性。

    1.8 优化算法及其优缺点

    • 随即梯度下降
      • 优点:
        1. 可以一定程度上解决局部最优解的问题
      • 缺点:
        1. 收敛速度较慢
    • 批量梯度下降
      • 优点:
        1. 容易陷入局部最优解
      • 缺点:
        1. 收敛速度较快
    • mini_batch梯度下降
      综合随即梯度下降和批量梯度下降的优缺点,提取的一个中和的方法。
    • 牛顿法
      • 优点:
      • 缺点:
    • 拟牛顿法
      • 优点:
      • 缺点:
    • 启发式的优化算法
      启发式的优化算法有遗传算法,粒子群算法等。这类算法的主要思想就是设定一个目标函数,每次迭代根据相应的策略优化种群。直到满足什么样的条件为止。

    1.9 梯度消失和梯度膨胀

    • 梯度消失:

      • 根据链式法则,如果每一层神经元对上一层的输出的偏导乘上权重结果都小于1的话,那么即使这个结果是0.99,在经过足够多层传播之后,误差对输入层的偏导会趋于0
      • 可以采用ReLU激活函数有效的解决梯度消失的情况
    • 梯度膨胀:

      • 根据链式法则,如果每一层神经元对上一层的输出的偏导乘上权重结果都大于1的话,在经过足够多层传播之后,误差对输入层的偏导会趋于无穷大
      • 可以通过激活函数来解决

    1.20 欧氏距离与曼哈顿距离

    • 欧氏距离,最常见的两点之间或多点之间的距离表示法,又称之为欧几里得度量,它定义于欧几里得空间中,对应于L2
    • 曼哈顿距离,我们可以定义曼哈顿距离的正式意义为 L1-距离 或城市区块距离,也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。
    • 通俗来讲,想象你在曼哈顿要从一个十字路口开车到另外一个十字路口,驾驶距离是两点间的直线距离吗?显然不是,除非你能穿越大楼。而实际驾驶距离就是这个“曼哈顿距离”,这也是曼哈顿距离名称的来源, 同时,曼哈顿距离也称为城市街区距离(City Block distance)。

    1.21 数据归一化

    • 归一化为什么能提高梯度下降法求解最优解的速度?
      当使用梯度下降法寻求最优解时,很有可能走“之字型”路线(垂直等高线走),从而导致需要迭代很多次才能收敛;
      对原始特征进行了归一化,其对应的等高线显得很圆,在梯度下降进行求解时能较快的收敛。

    • 归一化有可能提高精度
      一些分类器需要计算样本之间的距离(如欧氏距离),例如KNN。如果一个特征值域范围非常大,那么距离计算就主要取决于这个特征,从而与实际情况相悖(比如这时实际情况是值域范围小的特征更重要)。

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

    • 在工业界,很少直接将连续值作为逻辑回归模型的特征输入,而是将连续特征离散化为一系列 0、1 特征交给逻辑回归模型,这样做的优势有以下几点:
      1. 离散特征的增加和减少都很容易,易于模型的快速迭代;
      2. 稀疏向量内积乘法运算速度快,计算结果方便存储,容易扩展;
      3. 离散化后的特征对异常数据有很强的鲁棒性:比如一个特征是年龄>30是1,否则0。如果特征没有离散化,一个异常数据“年龄300岁”会给模型造成很大的干扰;
      4. 逻辑回归属于广义线性模型,表达能力受限;单变量离散化为N个后,每个变量有单独的权重,相当于为模型引入了非线性,能够提升模型表达能力,加大拟合;
      5. 离散化后可以进行特征交叉,由M+N个变量变为M*N个变量,进一步引入非线性,提升表达能力;
      6. 特征离散化后,模型会更稳定,比如如果对用户年龄离散化,20-30作为一个区间,不会因为一个用户年龄长了一岁就变成一个完全不同的人。当然处于区间相邻处的样本会刚好相反,所以怎么划分区间是门学问;
      7. 特征离散化以后,起到了简化了逻辑回归模型的作用,降低了模型过拟合的风险。

    1.23 XGBoost 和 GBDT 的区别

    • 算法层面的:

      1. XGB加了正则项,普通GBDT没有。为了防止过拟合
      2. XGBoost损失函数是误差部分是二阶泰勒展开,GBDT 是一阶泰勒展开。因此损失函数近似的更精准。
      3. 对每颗子树增加一个参数,使得每颗子树的权重降低,防止过拟合,这个参数叫shrinkage对特征进行降采样,灵感来源于随机森林,除了能降低计算量外,还能防止过拟合。
      4. 实现了利用分捅/分位数方法,实现了全局和局部的近似分裂点算法,降低了计算量,并且在eps参数设置合理的情况下,能达到穷举法几乎一样的性能
      5. 提出并实现了特征带权重的分位数的方法(好像是用到rank 场景下的,没太懂。。。)
      6. 增加处理缺失值的方案(通过枚举所有缺失值在当前节点是进入左子树,还是进入右子树更优来决定一个处理缺失值默认的方向)。
    • 系统层面:

      1. 对每个特征进行分块(block)并排序,使得在寻找最佳分裂点的时候能够并行化计算。这是xgboost比一般GBDT更快的一个重要原因。
      2. 通过设置合理的block的大小,充分利用了 CPU 缓存进行读取加速(cache-aware access)。使得数据读取的速度更快。因为太小的block的尺寸使得多线程中每个线程负载太小降低了并行效率。太大的block尺寸会导致CPU的缓存获取miss掉。
      3. out-of-core 通过将block压缩(block compressoin)并存储到硬盘上,并且通过将block分区到多个硬盘上(block Sharding)实现了更大的IO 读写速度,因此,因为加入了硬盘存储block读写的部分不仅仅使得xgboost处理大数据量的能力有所提升,并且通过提高IO的吞吐量使得xgboost相比一般实利用这种技术实现大数据计算的框架更快。

    2. 机器学习、大数据面试经验、答题思路

    1. 你在研究/项目/实习经历中主要用过哪些机器学习/数据挖掘的算法?
      A、最好是在项目/实习的大数据场景里用过,比如推荐里用过 CF、LR,分类里用过 SVM、GBDT
      B、一般用法是什么,是不是自己实现的,有什么比较知名的实现,使用过程中踩过哪些坑
      C、优缺点分析

    2. 你熟悉的机器学习/数据挖掘算法主要有哪些?
      A、基础算法要多说,其它算法要挑熟悉程度高的说,不光列举算法,也适当说说应用场合;
      B、面试官和你的研究方向可能不匹配,不过在基础算法上你们还是有很多共同语言的,你说得太高大上可能效果并不好,一方面面试官还是要问基础的,另一方面一旦面试官突发奇想让你给他讲解高大上的内容,而你只是泛泛的了解,那就傻叉了。

    3. 你用过哪些机器学习/数据挖掘工具或框架?
      A、主流的分布式框架如 Hadoop,Spark,Graphlab,Parameter Server 等择一或多使用了解;
      B、通用算法包,如 mahout,scikit,weka 等;
      C、专用算法包,如 OpenCV,theano,torch7,ICTCLAS 等。

    4. 基础知识

      A、无监督和有监督算法的区别?

      B、SVM 的推导,特性?多分类怎么处理?

      C、LR 的推导,特性?

      D、决策树的特性?

      E、SVM、LR、决策树的对比?

      F、GBDT 和 决策森林 的区别?

      G、如何判断函数凸或非凸?

      H、解释对偶的概念。

      I、如何进行特征选择?

      J、为什么会产生过拟合,有哪些方法可以预防或克服过拟合?

      K、介绍卷积神经网络,和 DBN 有什么区别?

      L、采用 EM 算法求解的模型有哪些,为什么不用牛顿法或梯度下降法?

      M、用 EM 算法推导解释 Kmeans。

      N、用过哪些聚类算法,解释密度聚类算法。

      O、聚类算法中的距离度量有哪些?

      P、如何进行实体识别?

      Q、解释贝叶斯公式和朴素贝叶斯分类。

      R、写一个 Hadoop 版本的 wordcount。

    5. 开放问题
      A、给你公司内部群组的聊天记录,怎样区分出主管和员工?

      B、如何评估网站内容的真实性(针对代刷、作弊类)?

      C、深度学习在推荐系统上可能有怎样的发挥?

      D、路段平均车速反映了路况,在道路上布控采集车辆速度,如何对路况做出合理估计?

      E、采集数据中的异常值如何处理?

      F、如何根据语料计算两个词词义的相似度?

      G、在百度贴吧里发布 APP 广告,问推荐策略?

      H、如何判断自己实现的 LR、Kmeans 算法是否正确?

      I、100亿数字,怎么统计前100大的?

    腾讯2017年春招内推面试(一)

    1、询问实验室具体情况,偏向于做哪一块;
    2、分布式并行化的了解,sklearn库的运用;
    3、GBDT和随机森林的区别;
    4、模型的方法和偏差的区别;
    5、ROC和AUC分别代表的是什么,ROC的取值范围;(AUC是ROC下面的面积!!)
    6、过拟合是怎么解决的(基本的算法、神经网络的算法中)
    7、神经网络防治过拟合除了dropout还有什么方法;(early stopping,augmentation,正则化)
    8、L1和L2产生的结果有什么区别;
    9、神经网络梯度消失的问题是怎么产生的;
    10、深度学习平常有使用到吗?(问得不深入)
    11、文本的使用?(问得不深入)
    12、spark的MLlib的使用过吗?
    13、PageRank的实现原理,大概思想?(网页排序算法)
    14、前面提到了有向图,那么树的叶子结点和边结点有什么关系?(对于二叉树来说,叶子结点和内部结点是什么关系,这个回答得不好)
    15、什么是平衡二叉树?什么是红黑树?红黑树有哪些实际应用场景呢?(回答了STL的两个底层,实际场景没有回答出来)
    16、哈希冲突的解决方法?(开放定址法、链地址法,其它的没有答出来)
    17、布隆过滤器有没有使用过?原理?(提示与哈希相关)
    18、数据结构里堆的定义和,基本模型是怎样的?时间复杂度是多少?(最大堆、最小堆)
    19、Java和Python哪个用的比较多(答C++,面试官说做大数据C++用的不多吧)
    20、设计模式了解过吗?工厂模式主要解决什么问题?(答了一点,然后gg)

    21、介绍了一下他们BG的主要工作(文章推荐、部落推荐、提升转化、挖掘群用户信息)

    30.请简要说说一个完整机器学习项目的流程
      @寒小阳、龙心尘
      1 抽象成数学问题
      明确问题是进行机器学习的第一步。机器学习的训练过程通常都是一件非常耗时的事情,胡乱尝试时间成本是非常高的。
      这里的抽象成数学问题,指的我们明确我们可以获得什么样的数据,目标是一个分类还是回归或者是聚类的问题,如果都不是的话,如果划归为其中的某类问题。
      2 获取数据
      数据决定了机器学习结果的上限,而算法只是尽可能逼近这个上限。
      数据要有代表性,否则必然会过拟合。
      而且对于分类问题,数据偏斜不能过于严重,不同类别的数据数量不要有数个数量级的差距。
      而且还要对数据的量级有一个评估,多少个样本,多少个特征,可以估算出其对内存的消耗程度,判断训练过程中内存是否能够放得下。如果放不下就得考虑改进算法或者使用一些降维的技巧了。如果数据量实在太大,那就要考虑分布式了。
      3 特征预处理与特征选择
      良好的数据要能够提取出良好的特征才能真正发挥效力。
    特征预处理、数据清洗是很关键的步骤,往往能够使得算法的效果和性能得到显著提高。归一化、离散化、因子化、缺失值处理、去除共线性等,数据挖掘过程中很多时间就花在它们上面。这些工作简单可复制,收益稳定可预期,是机器学习的基础必备步骤。
      筛选出显著特征、摒弃非显著特征,需要机器学习工程师反复理解业务。这对很多结果有决定性的影响。特征选择好了,非常简单的算法也能得出良好、稳定的结果。这需要运用特征有效性分析的相关技术,如相关系数、卡方检验、平均互信息、条件熵、后验概率、逻辑回归权重等方法。
      4 训练模型与调优
      直到这一步才用到我们上面说的算法进行训练。现在很多算法都能够封装成黑盒供人使用。但是真正考验水平的是调整这些算法的(超)参数,使得结果变得更加优良。这需要我们对算法的原理有深入的理解。理解越深入,就越能发现问题的症结,提出良好的调优方案。
      5 模型诊断
      如何确定模型调优的方向与思路呢?这就需要对模型进行诊断的技术。
    过拟合、欠拟合 判断是模型诊断中至关重要的一步。常见的方法如交叉验证,绘制学习曲线等。过拟合的基本调优思路是增加数据量,降低模型复杂度。欠拟合的基本调优思路是提高特征数量和质量,增加模型复杂度。
      误差分析 也是机器学习至关重要的步骤。通过观察误差样本,全面分析误差产生误差的原因:是参数的问题还是算法选择的问题,是特征的问题还是数据本身的问题……
    诊断后的模型需要进行调优,调优后的新模型需要重新进行诊断,这是一个反复迭代不断逼近的过程,需要不断地尝试, 进而达到最优状态。
      6 模型融合
      一般来说,模型融合后都能使得效果有一定提升。而且效果很好。
    工程上,主要提升算法准确度的方法是分别在模型的前端(特征清洗和预处理,不同的采样模式)与后端(模型融合)上下功夫。因为他们比较标准可复制,效果比较稳定。而直接调参的工作不会很多,毕竟大量数据训练起来太慢了,而且效果难以保证。
      7 上线运行
      这一部分内容主要跟工程实现的相关性比较大。工程上是结果导向,模型在线上运行的效果直接决定模型的成败。 不单纯包括其准确程度、误差等情况,还包括其运行的速度(时间复杂度)、资源消耗程度(空间复杂度)、稳定性是否可接受。
      这些工作流程主要是工程实践上总结出的一些经验。并不是每个项目都包含完整的一个流程。这里的部分只是一个指导性的说明,只有大家自己多实践,多积累项目经验,才会有自己更深刻的认识。

    展开全文
  • 机器学习 面经

    2018-10-18 22:50:51
    https://www.cnblogs.com/zuochongyan/p/5407053.html
    展开全文
  • 根据作者阿里机器学习面经整理1、监督学习非监督学习啥区别,word2vec 属于啥类型2、xgb,gbdt啥区别4、xgb中l1正则怎么用的5、python 中 list 底层怎么实现, list 有什么特点6、list dict有什么区别7、手写对dict...

    作者:sosilent
    链接:https://www.nowcoder.com/discuss/75360type=2&order=3&pos=216&page=2

    1、监督学习非监督学习啥区别,word2vec 属于啥类型

    对比一 : 有标签 vs 无标签
    有监督机器学习又被称为“有老师的学习”,所谓的老师就是标签。有监督的过程为先通过已知的训练样本(如已知输入和对应的输出)来训练,从而得到一个最优模型,再将这个模型应用在新的数据上,映射为输出结果。再经过这样的过程后,模型就有了预知能力。
    而无监督机器学习被称为“没有老师的学习”,无监督相比于有监督,没有训练的过程,而是直接拿数据进行建模分析,意味着这些都是要通过机器学习自行学习探索。
    对比二 : 分类 vs 聚类
    有监督机器学习的核心是分类,无监督机器学习的核心是聚类(将数据集合分成由类似的对象组成的多个类)。有监督的工作是选择分类器和确定权值,无监督的工作是密度估计(寻找描述数据统计值),这意味着无监督算法只要知道如何计算相似度就可以开始工作。
    对比三 : 同维 vs 降维
    有监督的输入如果是n维,特征即被认定为n维,也即y=f(xi)或p(y|xi), i =n,通常不具有降维的能力。而无监督经常要参与深度学习,做特征提取,或者干脆采用层聚类或者项聚类,以减少数据特征的维度。
    对比四 :分类同时定性 vs 先聚类后定性
    有监督的输出结果,也就是分好类的结果会被直接贴上标签,是好还是坏。也即分类分好了,标签也同时贴好了。无监督的结果只是一群一群的聚类,如果要进一步识别这些小堆,因此,无监督属于先聚类后定性,有点类似于批处理。
    对比五 :独立 vs 非独立
    对于不同的场景,正负样本的分布可能会存在偏移(可能是大的偏移,也可能偏移比较小)。好比我们手动对数据做标注作为训练样本,并把样本画在特征空间中,发现线性非常好,然而在分类面,总有一些混淆的数据样本。对这种现象的一个解释是,不管训练样本(有监督),还是待分类的数据(无监督),并不是所有数据都是相互独立分布的。或者说,数据和数据的分布之间存在联系。作为训练样本,大的偏移很可能会给分类器带来很大的噪声,而对于无监督,情况就会好很多。可见,独立分布数据更适合有监督,非独立数据更适合无监督。
    Word Embedding的训练方法大致可以分为两类:一类是无监督或弱监督的预训练;一类是端对端(end to end)的有监督训练。
    无监督或弱监督的预训练以word2vec和auto-encoder为代表。这一类模型的特点是,不需要大量的人工标记样本就可以得到质量还不错的Embedding向量。不过因为缺少了任务导向,可能和我们要解决的问题还有一定的距离。因此,我们往往会在得到预训练的Embedding向量( embedding就是用一个低维的向量表示一个物体,可以是一个词,或是一个商品,或是一个电影等等。这个embedding向量的性质是能使距离相近的向量对应的物体有相近的含义,比如 Embedding(复仇者联盟)和Embedding(钢铁侠)之间的距离就会很接近,但 Embedding(复仇者联盟)和Embedding(乱世佳人)的距离就会远一些。)后,用少量人工标注的样本去fine-tune整个模型。

    2、xgb,gbdt啥区别

    总的来说,两者之间的区别和联系可以总结成以
    下几个方面。
    (1)GBDT是机器学习算法, XGBoost是该算法的工程实现。
    (2)在使用CART作为基分类器时, XGBoost显式地加入了正则项
    来控制模型的复杂度,有利于防止过拟合,从而提高模型的泛化能力。
    (3)GBDT在模型训练时只使用了代价函数的一阶导数信息
    XGBoost对代价函数进行二阶泰勒展开,可以同时使用一阶和二阶导数。
    (4)传统的GBDT采用CART作为基分类器, XGBoost支持多
    种类型的基分类器,比如线性分类器。
    (5)传统的GBDT在每轮迭代时使用全部的数据, XGBoost则
    采用了与随机森林相似的策略,支持对数据进行采样。
    (6)传统的GBDT没有设计对缺失值进行处理, XGBoost能够自动学习出缺失值的处理策略。

    4、xgb中l1正则怎么用的

    树的复杂度定义为:
    在这里插入图片描述
    xgb中l1表示对叶节点个数的约束项的系数,而l2则是叶子节点权重的约束项系数。

    5、python 中 list 底层怎么实现, list 有什么特点

    1. 确定数据类型的意义在于确定一个数据在内存中占据的空间大小以及如何解释一段内存的含义;
    2. 同类型数据在内存中连续存储时采用固定的偏移量来定位;
    3. 不同类型数据需要采用元素外置的方式,在顺序表里面只存储外置元素的指针;
    4. 顺序表需要保存【容量】以及【已占用】数据,这个“表头”可以放在顺序表中,也可以分离出来;
    5. 当顺序表的容量不够或者过多时,会自动扩容或者缩容。

    Python中的列表是由对其它对象的引用组成的连续数组。指向这个数组的指针及其长度被保存在一个列表头结构中。这意味着,每次添加或删除一个元素时,由引用组成的数组需要该标大小(重新分配)。

    list有以下几个特点:

    1. 元素有位置下标,以索引就可以直接取到元素 --> 连续的存储空间,以偏移量计算取得元素,不必遍历所有元素
    2. 元素无论如何改变,表对象不变,也就是其id不变 --> 分离式结构,表头和元素内容分开储存,这样在更改list时,表对象始终是同一个,只是其指向的地址不同
    3. 元素可以是任意类型 --> 既要要求是连续存储,又可以存储不同类型的数据,那么其用的就是元素外置的方式,存储的只是地址的引用
    4. 可以任意添加新元素 --> 要能不断地添加新元素,其使用了动态扩充的策略

    6、list dict有什么区别

    Dict是字典类型,里面是key和value的映射关系,无序。list是列表,是一个可变序列,有续,索引是下标。字典内部实现应该是一个hash表 所以查找效率很高
    dict有以下几个特点:
    1. 查找和插入的速度极快,不会随着key的增加而变慢;
    2. 需要占用大量的内存,内存浪费多。
    而list相反:
    1. 查找和插入的时间随着元素的增加而增加;
    2. 占用空间小,浪费内存很少。

    字典是通过哈希表实现的。也就是说,字典是一个数组,而数组的索引是经过哈希函数处理后得到的。哈希函数的目的是使键均匀地分布在数组中。由于不同的键可能具有相同的哈希值,即可能出现冲突,高级的哈希函数能够使冲突数目最小化。

    7、手写对dict排序

    对下面的Dict:

    aps = {}
    for key in T.keys():
    ap = average_precision(T[key], P[key])
    aps[key] = ap
    

    如果用value从大到小排序:

    aps = sorted(aps.items(), key=lambda d:d[1], reverse = True)
    

    在这里插入图片描述
    如果对key排序,用d[0];默认的是从小到大排序,如果是从大到小,需要用reverse = True.
    注意返回的是一个List,不再是Dict.

    8.集成学习介绍(boosting bagging stacking原理)

    https://blog.csdn.net/Shingle_/article/details/81953564

    9.stacking blending区别

    stacking是k折交叉验证,元模型的训练数据等同于基于模型的训练数据,该方法为每个样本都生成了元特征,每生成元特征的模型不一样(k是多少,每个模型的数量就是多少);测试集生成元特征时,需要用到k(k fold不是模型)个加权平均;
    blending是holdout方法,直接将训练集切割成两个部分,仅10%用于元模型的训练;
    1.stacking过程读解
    stacking的主要思想是训练模型来学习使用底层学习的预测结果,下图是一个5折stacking中基模型在所以数据集上生成预测结果的过程,次学习器会基于模型的预测结果在进行训练,单个基模型生成预测的过程是:
    首先,将数据集生成测试集和训练集(假如训练集10000,测试2000),那么上层会进行5折交叉检验,使用训练集中的8000条作为喂养集,剩余2000条作为验证集(橙色)
    在这里插入图片描述
    每次验证,相当于使用了8000调数据训练出一个模型,使用模型对验证集进行验证得到的2000调数据,并对测试集进行预测,得到2500条数据,这样经过5次交叉验证,可以得到中间橙色的52000条验证集的结果(相当于每条数据的预测结果),52000条测试集的预测结果。
    接下来会将验证集的5*2000条预测结果拼接成10000行长的矩阵,标记为A1,而对于5 *2500行的测试集的预测结果进行加权平均的到一个2500一列的矩阵,标记为B1.
    上面得到一个基模型在数据集上的预测结果A1、B1,这样当我们对3个基模型进行集成的话,相当于得到了A1,A2,A3,B1,B2,B3六个矩阵
    之后我们会将A1、A2、 A3并列在一起10000行3列的矩阵作为raining data,B1、B2、 B3合并在一起成2500行3列的矩阵作为testing data ,让下层学习器基于这样的数据进行再训练。
    再训练是基于每个基础模型的预测结果作为特征(三个特征) , 次学习器会学习训练如果往这样的基学习的预测结果上赋予权重w,来使得最后的预测最为准确。
    以上就是Stacking的思想,进行Stacking集成同样需要基学习器尽保持独立(效果相近。
    2.Stacking特点
    使用stacking ,组1000多个模型,有时甚至要计算几十个小时。 但是,这些怪物般的集成方法同样有着它的用处:
    (1)它可以帮你打败当前学术界性能最好的算法
    (2)我们有可能将集成的知识迁移到到简单的分类器上
    (3)自动化的大型集成策略可以通过添加正则项有效的对抗过拟合,而且并不需要太多的调参和特征选择。所以从原则上讲, stacking
    (4)这是目前提升机器学习效果最好的方法,或者说是最效率的方法human ensemble learning。

    3.Blending
    Blending与Stacking大致相同,只是Blending的主要区别在于训练集不是通过K-Fold的CV策略来获得预测值从而生成第二阶段模型的特征,而是建立一个Holdout集,例如10%的训练数据,第二阶段的stacker模型就基于第一阶段模型对这10%训练数据的预测值进行拟合。说白了,就是把Stacking流程中的K-Fold CV 改成 HoldOut CV。

    4.Stacking和Blending对比

    1.Blending方式和Stacking方式很类似,相比Stacking更简单点,两者区别是:
    blending是直接准备好一部分10%留出集只在留出集 上继续预测,用不相交的数据训练不同的Base Model ,将它们的输出取(加权)平均。实现简单,但对训练数据利用少了。
    **2.blending的优点是:**比stacking简单,不会造成数据穿越(所谓数据创越,就比如训练部分数据时候用了全局的统计特征,导致模型效果过分的好) , generaliers和Istackers使用不同的数据,可以随时添加其他模型到blender中。
    3.缺点在于: blending只使用了一部分数据集作为留出集进行验证 ,而stacking使用多折交叉验证,比使用单-留出集更加稳健
    4.两个方法都挺好,看偏好了, 可以一部分做Blending.-部分做Stacking。
    补充一张Stacking训练阶段和测试阶段的图片,便于理解
    在这里插入图片描述

    10.分析为什么使用xgb(提示,从特征维度,样本维度等进行比较)

    XGBoost不是绝对的精确,但它绝对够快:
    1、 xgBoosting借鉴RF的做法,支持列抽样,这样不仅能防止过拟合,还能降低计算;
    2、xgBoosting的代价函数引入正则化项,控制了模型的复杂度,正则化项包含全部叶子节点的个数,每个叶子节点输出的score的L2模的平方和。从贝叶斯方差角度考虑,正则项降低了模型的方差,防止模型过拟合;
    3、XGBoost可并行:提升树算法最消耗时间片的是对连续型特征排序(如你每天开车上班有多远?),稀疏数据结构和聪明的实现方式让XGBoost可为每个列独立排序,通过这种方法,排序工作在CPU的并行线程之间可以分离执行。
    4、XGBoost支持近似分类:为了在连续型特征上找到最佳分类点,梯度提升树需要将所有数据放入内存进行排序,对小数据集来说不会存在什么问题,但当数据集大小超过内存时这个方法就行不通了,XGBoost可以对这些数据使用容器进行粗糙排序而不是完整排序,XGBoost论文作者表示,只要容器数量足够多,分类表现可以接近于精确分类。

    11.过拟合的判断方法

    在这里插入图片描述
    模型欠拟合,即高偏差(high bias),是指模型未训练出数据集的特征,导致模型在训练集、测试集上的精度都很低。如图1左图所示。
    模型过拟合,即高方差(high variance),是指模型训练出包含噪点在内的所有特征,导致模型在训练集的精度很高,但是应用到新数据集时,精度很低。如图1右图所示。
    2、模型过拟合

    12.过拟合如何解决

    判断方法

    过拟合(over-fitting),机器学习模型或者是深度学习模型在训练样本中表现得过于优越,导致在验证数据集以及测试数据集中表现不佳。出现这种现象的主要原因是训练数据中存在噪音或者训练数据太少。

    过拟合问题,根本的原因则是特征维度(或参数)过多,导致拟合的函数完美的经过训练集,但是对新数据的预测结果则较差。

    常见原因

    1)建模样本选取有误,如样本数量太少,选样方法错误,样本标签错误等,导致选取的样本数据不足以代表预定的分类规则;

    2)样本噪音干扰过大,使得机器将部分噪音认为是特征从而扰乱了预设的分类规则;

    3)假设的模型无法合理存在,或者说是假设成立的条件实际并不成立;

    4)参数太多,模型复杂度过高;

    5)对于决策树模型,如果我们对于其生长没有合理的限制,其自由生长有可能使节点只包含单纯的事件数据(event)或非事件数据(no event),使其虽然可以完美匹配(拟合)训练数据,但是无法适应其他数据集。

    6)对于神经网络模型:

    a)对样本数据可能存在分类决策面不唯一,随着学习的进行,,BP算法使权值可能收敛过于复杂的决策面;

    b)权值学习迭代次数足够多(Overtraining),拟合了训练数据中的噪声和训练样例中没有代表性的特征。

    解决方法

    1)在神经网络模型中,可使用权值衰减的方法,即每次迭代过程中以某个小因子降低每个权值。

    2)选取合适的停止训练标准,使对机器的训练在合适的程度;

    3)保留验证数据集,对训练成果进行验证;

    4)获取额外数据进行交叉验证;

    5)正则化,即在进行目标函数或代价函数优化时,在目标函数或代价函数。
    解决过拟合问题,则有2个途径:

    1. 减少特征维度; 可以人工选择保留的特征,或者模型选择算法
    2. 正则化; 保留所有的特征,通过降低参数θ的值,来影响模型

    13.造成过拟合的原因有可以归结为:参数过多或样本过少。那么我们需要做的事情就是减少参数,提供两种办法:

    1、回想下我们的模型,假如我们采用梯度下降算法将模型中的损失函数不断减少,那么最终我们会在一定范围内求出最优解,最后损失函数不断趋近0。那么我们可以在所定义的损失函数后面加入一项永不为0的部分,那么最后经过不断优化损失函数还是会存在。其实这就是所谓的“正则化”。

    一个通俗的理解便是:更小的参数值w意味着模型的复杂度更低,对训练数据的拟合刚刚好(奥卡姆剃刀)。

    下面这张图片就是加入了正则化(regulation)之后的损失函数。这里m是样本数目,表示的是正则化系数。

    当过大时,则会导致后面部分权重比加大,那么最终损失函数过大,从而导致欠拟合。

    当过小时,甚至为0,导致过拟合。
    在这里插入图片描述

    2、对于神经网络,参数膨胀原因可能是因为随着网路深度的增加,同时参数也不断增加,并且增加速度、规模都很大。那么可以采取减少神经网络规模(深度)的方法。也可以用一种叫dropout的方法。dropout的思想是当一组参数经过某一层神经元的时候,去掉这一层上的一部分神经元,让参数只经过一部分神经元进行计算。注意这里的去掉并不是真正意义上的去除,只是让参数不经过一部分神经元计算而已。

    在这里插入图片描述

    13.手写代码 两排序链表合并

    class Solution:
        # 返回合并后列表
        def Merge(self, pHead1, pHead2):
            # write code here
            p1 = pHead1
            p2 = pHead2
            ret = ListNode(0)
            p3 = ret
            while (p1 and p2):
                if p1.val < p2.val:
                    p3.next = ListNode(p1.val)
                    p1 = p1.next
                else:
                    p3.next = ListNode(p2.val)
                    p2 = p2.next
                p3 = p3.next
            if p1:
                p3.next = p1
            if p2:
                p3.next = p2
            return ret.next
    

    14.python 中 key-value的数据结构字典dict

    字典这个概念就是基于现实生活中的字典原型,生活中的使用名称-内容对数据进行构建,Python中使用键(key)-值(value)存储,也就是C++中的map。dict的显著特征

    • 字典中的数据必须以键值对的形式出现
    • 键不可重复,值可重复
    • 键若重复字典中只会记该键对应的最后一个值
    • 字典中键(key)是不可变的,为不可变对象,不能进行修改;而值(value)是可以修改的,可以是任何对象。
    • 在dict中是根据key来计算value的存储位置,如果每次计算相同的key得出的结果不同,那dict内部就完全混乱了。

    dict的增删查改

    1. 可以采用“键值对”的方法和update()方法向字典中添加元素,删除可以使用关键字del以及pop()方法
    在这里插入图片描述2.查询采用如查询列表元素的索引方式,使用键作为索引查找值
    若元素不存在会报错,在进行查找前,可以通过以下两种方法判断key是否存在:
    ① 成员资格运算符–in运算符
    ② get()方法(值不存在时返回NULL,也可指定返回的值)

    >>> test={'Mon':1}
    >>> 'Fri' in test
    False>>> test.get('Fri')
    >>> test.get('Fri',-1)
    -1
    

    3.对值得修改可以采用直接覆盖原值的方法
    4.dict中的元素是无序的,不可以采用分片。

    dict函数
    可以使用dict,通过其他映射或者(键,值)对的序列建立字典。

    >>> test=[('name','Sakura'),('age',20)]
    >>> d = dict(test)
    >>> d
    {'name': 'Sakura', 'age': 20}
    

    dict也可以使用关键字参数创建字典,也可用映射作为dict参数,dict若不带任何参数,将返回一个空字典

    >>> d = dict(name='Sakura',age=20)
    >>> d
    {'name': 'Sakura', 'age': 20}
    >>> a=dict()
    >>> a
    {}
    

    15.dict底层如何实现

    字典也被称为关联数组,还称为哈希数组等。也就是说,字典也是一个数组,但数组的索引是键经过哈希函数处理后得到的散列值。哈希函数的目的是使键均匀地分布在数组中,并且可以在内存中以O(1)的时间复杂度进行寻址,从而实现快速查找和修改。哈希表中哈希函数的设计困难在于将数据均匀分布在哈希表中,从而尽量减少哈希碰撞和冲突。由于不同的键可能具有相同的哈希值,即可能出现冲突,高级的哈希函数能够使冲突数目最小化。Python中并不包含这样高级的哈希函数,几个重要(用于处理字符串和整数)的哈希函数是常见的几个类型。
    字典对象的核心是散列表。散列表是一个稀疏数组(总是有空白元素的数组),数组的每个单元叫做 bucket。每个 bucket 有两部分:一个是键对象的引用,一个是值对象的引用。所有 bucket 结构和大小一致,我们可以通过偏移量来读取指定 bucket。下面通过存储与获取数据的过程介绍字典的底层原理。
    在这里插入图片描述

    16.如何解决哈希冲突

    一、拉链法

    上篇博文我们举的例子,HashMap,HashSet其实都是采用的拉链法来解决哈希冲突的,就是在每个位桶实现的时候,我们采用链表(jdk1.8之后采用链表+红黑树)的数据结构来去存取发生哈希冲突的输入域的关键字(也就是被哈希函数映射到同一个位桶上的关键字)
    二、开发地址法
    开放地址法有个非常关键的特征,就是所有输入的元素全部存放在哈希表里,也就是说,位桶的实现是不需要任何的链表来实现的,换句话说,也就是这个哈希表的装载因子不会超过1。它的实现是在插入一个元素的时候,先通过哈希函数进行判断,若是发生哈希冲突,就以当前地址为基准,根据再寻址的方法(探查序列),去寻找下一个地址,若发生冲突再去寻找,直至找到一个为空的地址为止。所以这种方法又称为再散列法。
    三、再散列法
    再散列法其实很简单,就是再使用哈希函数去散列一个输入的时候,输出是同一个位置就再次散列,直至不发生冲突位置
    缺点:每次冲突都要重新散列,计算时间增加。

    17.非监督学习举例

    18.解释k-means原理

    K-Means是典型的聚类算法,K-Means算法中的k表示的是聚类为k个簇,means代表取每一个聚类中数据值的均值作为该簇的中心,或者称为质心,即用每一个的类的质心对该簇进行描述。

    K-Means步骤
    1. 创建k个点作为起始质心。
    2. 计算每一个数据点到k个质心的距离。把这个点归到距离最近的哪个质心。
    3. 根据每个质心所聚集的点,重新更新质心的位置。
    4. 重复2,3,直到前后两次质心的位置的变化小于一个阈值。

    K值的确定
    K-Means算法一般都只有一个超参数,就是K。那我们拿到一个数据后,要吧数据分成几类呢?我们就来讨论下这个问题。
    1. 首先一个具体的问题肯定有它的具体的业务场景,K值需要根据业务场景来定义。
    2. 如果业务场景无法确定K值,我们也有技术手段来找一个合适的K。这个方法就是手肘法。

    手肘法
    K-Means算法中每一步都可以计算出loss值又称为SSE。loss值的计算方式就是每个聚类的点到它们质心的距离的平方。

    指定一个Max值,即可能的最大类簇数。然后将类簇数K从1开始递增,一直到Max,计算出Max个SSE。根据数据的潜在模式,当设定的类簇数不断逼近真实类簇数时,SSE呈现快速下降态势,而当设定类簇数超过真实类簇数时,SSE也会继续下降,当下降会迅速趋于缓慢。通过画出K-SSE曲线,找出下降途中的拐点,即可较好的确定K值。

    K-Means与KNN
    K-Means是无监督学习的聚类算法,没有样本输出;而KNN是监督学习的分类算法,有对应的类别输出。KNN基本不需要训练,对测试集里面的点,只需要找到在训练集中最近的k个点,用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程,找到k个类别的最佳质心,从而决定样本的簇类别。
    当然,两者也有一些相似点,两个算法都包含一个过程,即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。
    在这里插入图片描述

    19.距离的计算方法

    1、欧氏距离
    两个点的所有维度的坐标差的平方和最后开根号;
    2、曼哈顿距离
    两个点的坐标差的绝对值求和;
    两个点在标准坐标系上的绝对轴距总和;
    dis=abs(x1-x2)+(y1-y2)
    3、切比雪夫
    各个坐标距离(绝对值)的最大值;
    坐标差的绝对值的最大值;
    dis=max(abs(x1-x2),abs(y1-y2))

    20.监督学习模型如何选取

    监督学习主要包括分类和回归
    当输出被限制为有限的一组值(离散数值)时使用分类算法
    当输出可以具有范围内的任何数值(连续数值)时使用回归算法
    相似度学习是和回归和分类都密切相关的一类监督学习,它的目的是使用相似函数从样本中学习,这个函数可以度量两个对象之间的相似度或关联度

    模型选择:

    1、过拟合和欠拟合
    过拟合:特征集过大,把噪声数据的特征也学习到了,不能很好地识别数据,不能正确的分类
    欠拟合:特征集过小,导致模型不能很好地拟合数据【对数据的特征学习得不够】

    2、正则化和交叉验证

    a、正则化(防止过拟合):将结构风险最小化(Structural rick Minimization SRM )的过程。
    在经验风险上加上表示模型复杂度的正则化项(regularizer),或者叫惩罚项。
    正则化项:一般是模型复杂度的单调递增函数,即模型越复杂,正则化值越大。

    b、交叉验证:数据集不足时,可以重复地利用数据。
    简单交叉验证
    S折交叉验证
    留一交叉验证

    21. 详细分析xgb原理,怎么选分裂点,为什么用二阶泰勒展开,xgb里面正则项怎么表示

    选分裂点XGBoost使用的是pre-sorted算法(对所有特征都按照特征的数值进行预排序,基本思想是对所有特征都按照特征的数值进行预排序;然后在遍历分割点的时候用O(#data)的代价找到一个特征上的最好分割点最后,找到一个特征的分割点后,将数据分裂成左右子节点。优点是能够更精确的找到数据分隔点

    为什么用二阶泰勒展开
    泰勒展开的本质是拟合一个函数,二阶泰勒展开可以近似大量的损失函数,比如回归的平方损失函数,分类的对数似然损失函数。通过二阶泰勒展开推导出来的最终式子(叶子结点的得分和分裂标准),具有通用性,也就是说,任何一个损失函数,只要它能够二阶求导,就能够使用这套分裂标准和叶子的score来构造xgboost模型,也就是自定义损失函数。

    xgboost官网上说,用泰勒级数展开是因为损失函数的梯度并不总是容易求得。方便实现应该是最直接的原因。
    一个附加的好处是可能收敛更快。以logloss为例, 其二阶导为h(x)(1-h(x) ,显然在中值0.5附近变化最为剧烈。按照结构得分公式G^2/(H+λ),一阶导接近的情况下,拟合更偏向二阶导变化剧烈的特征,从而加快收敛。有点类似于梯度下降法和牛顿法。

    xgb里面正则项怎么表示
    在这里插入图片描述
    目标函数由两部分构成,第一部分用来衡量预测分数和真实分数的差距,另一部分则是正则化项。正则化项同样包含两部分,T表示叶子结点的个数,w表示叶子节点的分数。γ可以控制叶子结点的个数,λ可以控制叶子节点的分数不会过大,防止过拟合。
    22.L1,L2正则区别(我用概率跟最优化理论分析完,总监大佬又让我从梯度下降解释为什么L1稀疏),L1正则如何求梯度
    1.假设原先损失函数是C0,那么在L2和L1正则条件下对参数求导分别是:
    在这里插入图片描述
    在这里插入图片描述
    可以想象到用梯度下降的方法,当W小于1的时候,L2正则项的惩罚效果越来越小,而L1正则项的惩罚效果依然很大,L可以惩罚到0 ,而L2很难。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    23.xgb,gbdt区别,gbdt为什么用梯度,用梯度什么好处。

    提升树利用加法模型和前向分步算法实现学习的优化过程。当损失函数时平方损失和指数损失函数时,每一步的优化很简单,如平方损失函数学习残差回归树。但对于一般的损失函数,往往每一步优化没那么容易,如上图中的绝对值损失函数和Huber损失函数。针对这一问题,Freidman提出了梯度提升算法:利用最速下降的近似方法,即利用损失函数的负梯度在当前模型的值,作为回归问题中提升树算法的残差的近似值,拟合一个回归树。

    展开全文
  • 二、机器学习算法 1、处理分类问题常用算法 1、交叉熵公式 2、LR公式 3 LR的推导,损失函数 4、逻辑回归怎么实现多分类 5 、SVM中什么时候用线性核什么时候用高斯核? 6、什么是支持向量机,SVM与LR的区别? 7.监督学习...

    二、机器学习算法

    1、处理分类问题常用算法

    1、交叉熵损失函数公式具体可看推导过程

    • 交叉熵公式为下图:
      在这里插入图片描述

    二分类的交叉熵损失函数如下:
    在这里插入图片描述

    • KL散度(相对熵):
      KL散度 = 交叉熵 - label的信息熵
      在这里插入图片描述

    2.监督学习和无监督学习的区别

    • 输入的数据有标签则为监督学习,输入数据无标签为非监督学习。

    3.机器学习中的距离计算方法?

    • 空间中两个

    展开全文
  • 统计学习方法部分: 推导LR 画LSTM的图、画CNN的图 介绍CNN 过拟合得解决方法 方差偏差分解的公式 一道贝叶斯公式的概率题 逻辑回归和svm。 说说逻辑回归怎么实现多分类 svm里什么时候用线性核和高斯核吧,比如...
  • 一、好玩题 (1)人生路上,会遇到很多合适的人,笔者也相信着有情人终将眷属。只是在做出一生一世...#机器学习的入门概念+概率论+极限+积分(有点难) 假设总共遇到女生数量是n,以前k个女生做为训练集合,后n-k...
  • Adagard在训练的过程中可以自动变更学习的速率,设置一个全局的学习率,而实际的学习率与以往的参数模和的开方成反比。 Adam利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率,在经过偏置的校正
  • 机器学习面经---SVM

    2020-12-07 12:09:59
    感知机学习算法会因采用的初值不同而得到不同的超平面。而SVM试图寻找一个最佳的超平面来划分数据。感知机简单求解快速,但是无法解决非线性分类问题,svm可以通过引入核技巧来实现非线性分类但是计算复杂度相对于...
  • 支持向量机包含核技巧使它成为实质上的非线性分类器,利用核函数可以学习非线性支持向量机,等价于隐式的在高维空间中学习线性支持向量机。支持向量机的学习策略是间隔最大化,可形式为求解凸二次规划问题,也等价于...
  • https://www.nowcoder.com/discuss/102895?type=0&order=0&pos=6&page=1 ----------------------------------------------------------------------------------------------------------------- ...
  • 一面七月份的提前批面试,当时面完就决定要把这次经历写出来今年第一次遇到女面试官,主要考察机器学习基础知识。首先打开一个能写公式的编辑器实习经历贝叶斯公式应用题朴素贝叶斯思想手推lr梯度,...
  • 由于百度是秋招的时候面的,现在很多问题都记不住了,这里只写下我还记得的题目吧(当时太懒了,不想写了。。。): 1.文本分类比赛用的什么模型?为什么? 答:LR、SVM、XGBoost。...答:LR受全部样本的影响,...
  • 送你小心心记得关注我哦!!进入正文摘要送你一份贝壳机器学习面经,学了那么久的机器学习,是不是想要迫不及待的测试一下自己的能力呢?想不想知道自己距离一份好的offer到底...
  • vivo 推荐算法、机器学习面经整理

    千次阅读 2019-06-11 10:18:24
    Wide部分是用FTRL(Follow-the-regularized-leader) + L1正则化学习。 Deep部分是用AdaGrad来学习 Embedding维度大小 在Deep模型中需要将稀疏矩阵进行embedding,Wide&Deep的作者指出,从经验上来讲...
  • 面经整理-机器学习

    2019-08-05 11:09:43
    机器学习面经整理
  • 机器学习他人面经

    2016-08-31 18:44:44
     找工作时(IT行业),除了常见的软件开发以外,机器学习岗位也可以当作是一个选择,不少计算机方向的研究生都会接触这个,如果你的研究方向是机器学习/数据挖掘之类,且又对其非常感兴趣的话,可以考虑考虑该岗位...
  • 机器学习面试面经笔记(1)面试题1 面试题1 1、请详细说说支持向量机(support vector machine,SVM)的原理
  • 腾讯机器学习一面面经

    千次阅读 2018-04-15 17:01:46
    1 梯度下降,极大似然2 防止过拟合的方法(正则化)3 bagging,boosting,randomforest,gbdt概念4 海量url中寻找某个url是否存在?5 有用户访问url的日志记录,如何对url进行分类?6 有用户的基本信息、行为等,如何对...
  • 2017年5月百度机器学习实习面经

    千次阅读 2017-05-08 13:40:45
    2017年5月百度机器学习实习面经 古人云:不积跬步无以至千里,不积小流无以成江海。谨以此文为开端,记录我的学习过程。 面试持续1个小时,大致过程如下: 首先自我介绍,然后聊聊自己的项目,感觉百度统招的面试...
  • 美团机器学习面经

    2017-01-07 16:56:36
     简单总结一下,首先基础要扎实,基本的东西要明白,项目和论文要有,尤其是对机器学习与数据挖掘岗位,感觉会关注你的论文情况。当然论文的方向不一定和他们所做的业务是一样的,只是用来证明你有解决机器学习这类...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,815
精华内容 2,726
关键字:

机器学习面经