机器学习算法工程师精选的算法面试这些知识你多了解吗？

通往机器学习算法工程师的进阶之路是崎岖险阻的。《线性代数》《统计学习方法》《机器学习》《模式识别》《深度学习》，以及《颈椎病康复指南》，这些书籍将长久地伴随着你的工作生涯。

除了拥有全面、有条理的知识储备，我认为，想成为一名优秀的算法工程师，更重要的是对算法模型有着发自心底的热忱，对研究工作有一种匠心精神。这种匠心精神，直白来讲，可以概括为：发现问题的眼光、解决问题的探索精神，以及对问题究原竟委的执着追求。这里，我想给大家分享一个发生在我身边的真实情景。

在微信红包占领家家户户年夜饭的那个时代，我们的小伙伴也没有例外。一群心有猛虎、细嗅蔷薇的算法研究员深切意识到自己不仅手速慢，运气也可谓糟糕。在埋头疯点手机屏幕的间隙，他们查阅了抢红包策略的相关文献，发现国内外对这一理论框架的探究极度匮乏。

知识拯救命运，他们决定将红包机制的公平性提升到理论高度。通过大量的模拟实验，统计在不同顺位领到红包的大小。数据分析显示，越后面领到红包的人，虽然红包金额的期望（均值）和前面的人相同，但方差会更大，这也意味着他们更容易获得一些大额红包。从此，掌握这一规律的研究员们在各个群中“屡试不爽”，再也没有抢到过红包，留下的只有“手慢了，红包派完了”几个大字。

*编辑配图

新年钟声敲响的时分临近，Boss级别的人物往往会在群里发一些超级大额的红包。最夸张的一次有一位幸运儿在10人红包中领到2角钱，还没来得及在心中完成“老板真抠门”的碎碎念，抬头定睛一看，最佳手气500多元。判若云泥的手气虽没有埋下同事关系间的芥蒂，却让这帮算法工程师们产生了新的思考—如果把大额红包分成多份给大家抢，会减小“人品”因素带来的“贫富差距”吗？理论结合实际，他们不仅通过数学推导确认这一结论，还设计了一系列实验证明了多个红包的确会缩小不同人领到红包金额之间的差异性（方差）。从此，他们组的Leader在发大红包的时候都会刻意平均分成几份，既增加了大家抢红包的乐趣，又避免了有人因运气不佳而扼腕兴叹的愤懑。

当然，故事不止于此。他们还利用红包的特性编写了一系列面试题——《百面机器学习——算法工程师带你去面试》，筛选着一批又一批的机器学习算法工程师。

工作中的算法工程师，很多时候，会将生活中转瞬即逝的灵感，付诸产品化。

将算法研究应用到工作中，与纯粹的学术研究有着一点最大的不同，即需要从用户的角度思考问题。很多时候，你需要明确设计的产品特征、提升的数据指标，是不是能真正迎合用户的需求，这便要求算法工程师能在多个模型间选择出最合适的那个，然后通过快速迭代达到一个可以走向产品化的结果。这种创新精神与尝试精神便是“匠心”一词在工作中的体现。

当然，匠心精神诚可贵，知识储备作为成功的根底亦必不可少，以下是营长为你精选的算法面试，帮你检查下自己的技能是否在线。

*编辑配图

▌1. LDA(线性判别分析) 和 PCA 的区别与联系

首先将LDA 扩展到多类高维的情况，以和问题1 中PCA 的求解对应。假设有N 个类别，并需要最终将特征降维至d 维。因此，我们要找到一个d 维投影超平面，使得投影后的样本点满足LDA 的目标—最大化类间距离和最小化类内距离。

回顾两个散度矩阵， 类内散度矩阵在类别增加至 N 时仍满足定义， 而之前两类问题的类间散度矩阵在类别增加后就无法按照原始定义。图4.6 是三类样本的分布情况，其中分别表示棕绿黄三类样本的中心，μ 表示这三个中心的均值（也即全部样本的中心），Swi表示第i 类的类内散度。我们可以定义一个新的矩阵St，来表示全局整体的散度，称为全局散度矩阵

如果把全局散度定义为类内散度与类间散度之和，即St=Sb+Sw，那么类间散度矩阵可表示为

其中mj 是第j 个类别中的样本个数，N 是总的类别个数。从式（4.29）可以看出，类间散度表示的就是每个类别中心到全局中心的一种加权距离。我们最大化类间散度实际上优化的是每个类别的中心经过投影后离全局中心的投影足够远。

根据LDA 的原理，可以将最大化的目标定义为

其中W是需要求解的投影超平面，WTW=I，根据问题2 和问题3 中的部分结论，我们可以推导出最大化J(W) 对应了以下广义特征值求解的问题

求解最佳投影平面即求解矩阵特征值前d 大对应的特征向量组成的矩阵，这就将原始的特征空间投影到了新的d 维空间中。至此我们得到了与PCA 步骤类似，但具有多个类别标签高维数据的LDA求解方法。

（1）计算数据集中每个类别样本的均值向量μj，及总体均值向量μ。

（2）计算类内散度矩阵Sw，全局散度矩阵St，并得到类间散度矩阵。

（3）对矩阵行特征值分解，将特征值从大到小排列。

（4）取特征值前 d 大的对应的特征向量，通过以下映射将n 维样本映射到d 维 

从PCA 和LDA 两种降维方法的求解过程来看，它们确实有着很大的相似性，但对应的原理却有所区别。

首先从目标出发，PCA 选择的是投影后数据方差最大的方向。由于它是无监督的，因此PCA 假设方差越大，信息量越多，用主成分来表示原始数据可以去除冗余的维度，达到降维。而LDA 选择的是投影后类内方差小、类间方差大的方向。其用到了类别标签信息，为了找到数据中具有判别性的维度，使得原始数据在这些方向上投影后，不同类别尽可能区分开。

举一个简单的例子，在语音识别中，我们想从一段音频中提取出人的语音信号，这时可以使用PCA 先进行降维，过滤掉一些固定频率（方差较小）的背景噪声。但如果我们的需求是从这段音频中区分出声音属于哪个人，那么我们应该使用LDA 对数据进行降维，使每个人的语音信号具有区分性。

另外，在人脸识别领域中，PCA 和LDA 都会被频繁使用。基于PCA 的人脸识别方法也称为特征脸（Eigenface）方法，该方法将人脸图像按行展开形成一个高维向量，对多个人脸特征的协方差矩阵做特征值分解，其中较大特征值对应的特征向量具有与人脸相似的形状，故称为特征脸。Eigenface forRecognition 一文中将人脸用7 个特征脸表示（见图4.7），于是可以把原始65536 维的图像特征瞬间降到7 维， 人脸识别在降维后的空间上进行。然而由于其利用PCA 进行降维，一般情况下保留的是最佳描述特征（主成分），而非分类特征。如果我们想要达到更好的人脸识别效果，应该用LDA 方法对数据集进行降维， 使得不同人脸在投影后的特征具有一定区分性。

从应用的角度，我们可以掌握一个基本的原则—对无监督的任务使用PCA 进行降维，对有监督的则应用LDA。

▌2.K-均值算法收敛性的证明

首先，我们需要知道K 均值聚类的迭代算法实际上是一种最大期望算法（Expectation-Maximizationalgorithm），简称EM算法。EM算法解决的是在概率模型中含有无法观测的隐含变量情况下的参数估计问题。假设有m 个观察样本，模型的参数为θ，最大化对数似然函数可以写成如下形式

当概率模型中含有无法被观测的隐含变量时，参数的最大似然估计变为

由于z(i) 是未知的， 无法直接通过最大似然估计求解参数，这时就需要利用EM 算法来求解。假设z(i) 对应的分布为，并满足。利用Jensen 不等式，可以得到 

要使上式中的等号成立，需要满足

其中c 为常数，且满足

因此

不等式右侧函数记为r(x|θ)。当等式成立时，我们相当于为待优化的函数找到了一个逼近的下界，然后通过最大化这个下界可以使得待优化函数向更好的方向改进。

图5.5 是一个θ 为一维的例子，其中棕色的曲线代表我们待优化的函数，记为f(θ)，优化过程即为找到使得f(θ) 取值最大的θ。在当前θ 的取值下（即图中绿色的位置），可以计算，此时不等式右侧的函数（记为r(x|θ)）给出了优化函数的一个下界，如图中蓝色曲线所示，其中在θ 处两条曲线的取值时相等的。接下来找到使得r(x|θ) 最大化的参数θ′，即图中红色的位置，此时f(θ′) 的取值比f(θ)（绿色的位置处）有所提升。可以证明，f(θ′) ≥ r(x|θ)=f(θ)，因此函数是单调的，而且从而函数是有界的。根据函数单调有界必收敛的性质，EM 算法的收敛性得证。但是EM 算法只保证收敛到局部最优解。当函数为非凸时，以图5.5 为例，如果初始化在左边的区域时，则无法找到右侧的高点。

由上面的推导，EM 算法框架可以总结如下，由以下两个步骤交替进行直到收敛。

（1）E 步骤：计算隐变量的期望

（2）M 步骤：最大化

剩下的事情就是说明K 均值算法与EM 算法的关系了。K 均值算法等价于用EM 算法求解以下含隐变量的最大似然问题：

其中是模型的隐变量。直观地理解，就是当样本x 离第k个簇的中心点μk 距离最近时，概率正比于，否则为0。

在 E 步骤，计算

这等同于在K 均值算法中对于每一个点x(i) 找到当前最近的簇z(i)。

在M步骤，找到最优的参数，使得似然函数最大：

经过推导可得

因此，这一步骤等同于找到最优的中心点，使得损失函数

达到最小，此时每个样本x(i) 对应的簇z(i) 已确定，因此每个簇k 对应的最优中心点μk 可以由该簇中所有点的平均计算得到，这与K 均值算法中根据当前簇的分配更新聚类中心的步骤是等同的。

▌3.如何确定 LDA (隐狄利克雷模型) 中主题的个数

在LDA中，主题的个数K 是一个预先指定的超参数。对于模型超参数的选择，实践中的做法一般是将全部数据集分成训练集、验证集、和测试集3 部分，然后利用验证集对超参数进行选择。例如，在确定LDA 的主题个数时，我们可以随机选取60% 的文档组成训练集，另外20% 的文档组成验证集，剩下20% 的文档组成测试集。在训练时，尝试多组超参数的取值，并在验证集上检验哪一组超参数所对应的模型取得了最好的效果。最终，在验证集上效果最好的一组超参数和其对应的模型将被选定，并在测试集上进行测试。

为了衡量LDA 模型在验证集和测试集上的效果，需要寻找一个合适的评估指标。一个常用的评估指标是困惑度（perplexity）。在文档集合D 上，模型的困惑度被定义为

其中 M 为文档的总数，wd 为文档 d 中单词所组成的词袋向量，p(wd) 为模型所预测的文档d 的生成概率，Nd 为文档d 中单词的总数。

一开始，随着主题个数的增多，模型在训练集和验证集的困惑度呈下降趋势，但是当主题数目足够大的时候，会出现过拟合，导致困惑度指标在训练集上继续下降但在验证集上反而增长。这时，可以取验证集的困惑度极小值点所对应的主题个数作为超参数。在实践中，困惑度的极小值点可能出现在主题数目非常大的时候，然而实际应用并不能承受如此大的主题数目，这时就需要在实际应用中合理的主题数目范围内进行选择，比如选择合理范围内困惑度的下降明显变慢（拐点）的时候。

另外一种方法是在LDA 基础之上融入分层狄利克雷过程（Hierarchical Dirichlet Process，HDP），构成一种非参数主题模型HDP-LDA。非参数主题模型的好处是不需要预先指定主题的个数，模型可以随着文档数目的变化而自动对主题个数进行调整；它的缺点是在LDA 基础上融入HDP 之后使得整个概率图模型更加复杂，训练速度也更加缓慢，因此在实际应用中还是经常采用第一种方法确定合适的主题数目。

▌4.随机梯度下降法的一些改进算法

随机梯度下降法本质上是采用迭代方式更新参数，每次迭代在当前位置的基础上，沿着某一方向迈一小步抵达下一位置，然后在下一位置重复上述步骤。随机梯度下降法的更新公式表示为

其中，当前估计的负梯度−gt 表示步子的方向，学习速率η 控制步幅。改造的随机梯度下降法仍然基于这个更新公式。

动量（Momentum）方法

为了解决随机梯度下降法山谷震荡和鞍点停滞的问题，我们做一个简单的思维实验。想象一下纸团在山谷和鞍点处的运动轨迹，在山谷中纸团受重力作用沿山道滚下，两边是不规则的山壁，纸团不可避免地撞在山壁，由于质量小受山壁弹力的干扰大，从一侧山壁反弹回来撞向另一侧山壁，结果来回震荡地滚下；如果当纸团来到鞍点的一片平坦之地时，还是由于质量小，速度很快减为零。纸团的情况和随机梯度下降法遇到的问题简直如出一辙。直观地，如果换成一个铁球，当沿山谷滚下时，不容易受到途中旁力的干扰，轨迹会更稳更直；当来到鞍点中心处，在惯性作用下继续前行，从而有机会冲出这片平坦的陷阱。因此，有了动量方法，模型参数的迭代公式为

具体来说，前进步伐−vt由两部分组成。一是学习速率η乘以当前估计的梯度gt；二是带衰减的前一次步伐vt−1。这里，惯性就体现在对前一次步伐信息的重利用上。类比中学物理知识，当前梯度就好比当前时刻受力产生的加速度，前一次步伐好比前一时刻的速度，当前步伐好比当前时刻的速度。为了计算当前时刻的速度，应当考虑前一时刻速度和当前加速度共同作用的结果，因此vt直接依赖于vt−1和gt，而不仅仅是gt。另外，衰减系数γ扮演了阻力的作用。

中学物理还告诉我们，刻画惯性的物理量是动量，这也是算法名字的由来。沿山谷滚下的铁球，会受到沿坡道向下的力和与左右山壁碰撞的弹力。向下的力稳定不变，产生的动量不断累积，速度越来越快；左右的弹力总是在不停切换，动量累积的结果是相互抵消，自然减弱了球的来回震荡。因此，与随机梯度下降法相比，动量方法的收敛速度更快，收敛曲线也更稳定，如图7.5 所示。

AdaGrad 方法

惯性的获得是基于历史信息的，那么，除了从过去的步伐中获得一股子向前冲的劲儿，还能获得什么呢？我们还期待获得对周围环境的感知，即使蒙上双眼，依靠前几次迈步的感觉，也应该能判断出一些信息，比如这个方向总是坑坑洼洼的，那个方向可能很平坦。

随机梯度下降法对环境的感知是指在参数空间中，根据不同参数的一些经验性判断，自适应地确定参数的学习速率，不同参数的更新步幅是不同的。例如，在文本处理中训练词嵌入模型的参数时，有的词或词组频繁出现，有的词或词组则极少出现。数据的稀疏性导致相应参数的梯度的稀疏性，不频繁出现的词或词组的参数的梯度在大多数情况下为零，从而这些参数被更新的频率很低。在应用中，我们希望更新频率低的参数可以拥有较大的更新步幅，而更新频率高的参数的步幅可以减小。

AdaGrad 方法采用“历史梯度平方和”来衡量不同参数的梯度的稀疏性，取值越小表明越稀疏，具体的更新公式表示为

其中θt+1,i 表示（t+1）时刻的参数向量θt+1的第i个参数，gk,i表示k时刻的梯度向量gk 的第i 个维度（方向）。另外，分母中求和的形式实现了退火过程，这是很多优化技术中常见的策略，意味着随着时间推移，学习速率越

来越小，从而保证了算法的最终收敛。

Adam 方法

Adam 方法将惯性保持和环境感知这两个优点集于一身。一方面， Adam 记录梯度的一阶矩（first moment），即过往梯度与当前梯度的平均，这体现了惯性保持；另一方面，Adam 还记录梯度的二阶矩（second moment），即过往梯度平方与当前梯度平方的平均，这类似AdaGrad 方法，体现了环境感知能力，为不同参数产生自适应的学习速率。一阶矩和二阶矩采用类似于滑动窗口内求平均的思想进行融合，即当前梯度和近一段时间内梯度的平均值，时间久远的梯度对当前平均值的贡献呈指数衰减。具体来说，一阶矩和二阶矩采用指数衰退平均（exponential decayaverage）技术，计算公式为

其中β1，β2 为衰减系数，mt 是一阶矩，vt 是二阶矩。

如何理解一阶矩和二阶矩呢？一阶矩相当于估计：由于当下梯度gt 是随机采样得到的估计结果，因此更关注它在统计意义上的期望；二阶矩相当于估计，这点与AdaGrad 方法不同，不是gt2从开始到现在的加和，而是它的期望。它们的物理意义是，当||mt||大且vt 大时，梯度大且稳定，这表明遇到一个明显的大坡，前进方向明确；当||mt||趋于零且vt大时，梯度不稳定，表明可能遇到一个峡谷，容易引起反弹震荡；当||mt||大且vt趋于零时，这种情况不可能出现；当||mt|| 趋于零且vt 趋于零时，梯度趋于零，可能到达局部最低点，也可能走到一片坡度极缓的平地，此时要避免陷入平原（plateau）。另外，Adam 方法还考虑了mt，vt 在零初始值情况下的偏置矫正。具体来说，Adam 的更新公式为

其中,

▌5.L1正则化产生稀疏性的原因

角度1：解空间形状

机器学习的经典之作给出的解释无疑是权威且直观的，面试者给出的答案多数也是从这个角度出发的。在二维的情况下，黄色的部分是L2 和L1 正则项约束后的解空间，绿色的等高线是凸优化问题中目标函数的等高线，如图7.6 所示。由图可知，L2 正则项约束后的解空间是圆形，而L1 正则项约束的解空间是多边形。显然，多边形的解空间更容易在尖角处与等高线碰撞出稀疏解。

上述这个解释无疑是正确的，但却不够精确，面试者往往回答过于笼统，以至于忽视了几个关键问题。比如，为什么加入正则项就是定义了一个解空间约束？为什么L1 和L2的解空间是不同的？面试官如果深究下去，很多面试者难以给出满意的答案。其实可以通过KKT条件给出一种解释。

事实上，“带正则项”和“带约束条件”是等价的。为了约束w 的可能取值空间从而防止过拟合，我们为该最优化问题加上一个约束，就是w 的L2 范数的平方不能大于m：

为了求解带约束条件的凸优化问题，写出拉格朗日函数

若w* 和λ* 分别是原问题和对偶问题的最优解，则根据KKT 条件，它们应满足

仔细一看，第一个式子不就是w* 为带L2 正则项的优化问题的最优解的条件嘛，而λ* 就是L2 正则项前面的正则参数。

这时回头再看开头的问题就清晰了。L2 正则化相当于为参数定义了一个圆形的解空间（因为必须保证L2 范数不能大于m），而L1 正则化相当于为参数定义了一个棱形的解空间。如果原问题目标函数的最优解不是恰好落在解空间内，那么约束条件下的最优解一定是在解空间的边界上，而L1“棱角分明”的解空间显然更容易与目标函数等高线在角点碰撞，从而产生稀疏解。

角度2：函数叠加

第二个角度试图用更直观的图示来解释L1 产生稀疏性这一现象。仅考虑一维的情况，多维情况是类似的，如图7.7 所示。假设棕线是原始目标函数L(w) 的曲线图，显然最小值点在蓝点处，且对应的w* 值非0。

首先，考虑加上L2正则化项，目标函数变成L(w)+Cw2，其函数曲线为黄色。此时，最小值点在黄点处，对应的w* 的绝对值减小了，但仍然非0。

然后，考虑加上L1 正则化项，目标函数变成L(w)+C|w|，其函数曲线为绿色。此时，最小值点在红点处，对应的w 是0，产生了稀疏性。

产生上述现象的原因也很直观。加入L1 正则项后，对带正则项的目标函数求导，正则项部分产生的导数在原点左边部分是−C，在原点右边部分是C，因此，只要原目标函数的导数绝对值小于C，那么带正则项的目标函数在原点左边部分始终是递减的，在原点右边部分始终是递增的，最小值点自然在原点处。相反，L2 正则项在原点处的导数是0，只要原目标函数在原点处的导数不为0，那么最小值点就不会在原点，所以L2 只有减小w 绝对值的作用，对解空间的稀疏性没有贡献。

在一些在线梯度下降算法中，往往会采用截断梯度法来产生稀疏性， 这同L1 正则项产生稀疏性的原理是类似的。

角度3：贝叶斯先验

从贝叶斯的角度来理解L1 正则化和L2 正则化，简单的解释是， L1 正则化相当于对模型参数w 引入了拉普拉斯先验，L2 正则化相当于引入了高斯先验，而拉普拉斯先验使参数为0 的可能性更大。

图7.8 是高斯分布曲线图。由图可见，高斯分布在极值点（0 点）处是平滑的，也就是高斯先验分布认为w 在极值点附近取不同值的可能性是接近的。这就是L2 正则化只会让w 更接0点，但不会等于0 的原因。

相反，图7.9 是拉普拉斯分布曲线图。由图可见，拉普拉斯分布在极值点（0 点）处是一个尖峰，所以拉普拉斯先验分布中参数w 取值为0 的可能性要更高。在此我们不再给出L1 和L2 正则化分别对应拉普拉斯先验分布和高斯先验分布的详细证明。

▌6.如何对贝叶斯网络进行采样

对一个没有观测变量的贝叶斯网络进行采样，最简单的方法是祖先采样（Ancestral Sampling），它的核心思想是根据有向图的顺序，先对祖先节点进行采样，只有当某个节点的所有父节点都已完成采样，才对该节点进行采样。以场景描述中的图8.9 为例，先对Cloudy 变量进行采样，然后再对Sprinkler 和Rain 变量进行采样，最后对WetGrass 变量采样，如图8.10 所示（图中绿色表示变量取值为True，红色表示取值为False）。根据贝叶斯网络的全概率公式

可以看出祖先采样得到的样本服从贝叶斯网络的联合概率分布。

如果只需要对贝叶斯网络中一部分随机变量的边缘分布进行采样， 可以用祖先采样先对全部随机变量进行采样，然后直接忽视那些不需要的变量的采样值即可。由图可见，如果需要对边缘分布p(Rain) 进行采样，先用祖先采样得到全部变量的一个样本，如（Cloudy=T， Sprinkler=F，Rain=T，WetGrass=T），然后忽略掉无关变量，直接把这个样本看成是Cloudy=T 即可。

接下来考虑含有观测变量的贝叶斯网络的采样，如图8.11 所示。网络中有观测变量（Sprikler=T，WetGrass=T）（观测变量用斜线阴影表示），又该如何采样呢？最直接的方法是逻辑采样，还是利用祖先采样得到所有变量的取值。如果这个样本在观测变量上的采样值与实际观测值相同，则接受，否则拒绝，重新采样。这种方法的缺点是采样效率可能会非常低，随着观测变量个数的增加、每个变量状态数目的上升，逻辑采样法的采样效率急剧下降，实际中基本不可用。

因此，在实际应用中，可以参考重要性采样的思想，不再对观测变量进行采样，只对非观测变量采样，但是最终得到的样本需要赋一个重要性权值：

其中E 是观测变量集合。这种采样方法称作似然加权采样（Likelihood Weighted Sampling），产生的样本权值可以用于后续的积分操作。在有观测变量（Sprikler=T，WetGrass=T）时，可以先对Cloudy 进行采样，然后对Rain 进行采样，不再对Sprinkler 和WetGrass 采样（直接赋观测值），如图8.12 所示。这样得到的样本的重要性权值为

w ∝ p(Sprinkler=T|Cloudy=T)·p(WetGrass=T|Sprinkler=T，Rain=T)=0.1×0.99=0.099.

除此之外，还可以用MCMC采样法来进行采样。具体来说，如果采用Metropolis-Hastings 采样法的话，如图8.13所示，只需要在随机向量（Cloudy, 、Rain）上选择一个概率转移矩阵，然后按照概率转移矩阵不断进行状态转换，每次转移有一定概率的接受或拒绝，最终得到的样本序列会收敛到目标分布。最简单的概率转移矩阵可以是：每次独立地随机选择（Cloudy, Rain）的四种状态之一。如果采用吉布斯采样法的话，根据条件概率p(Cloudy|Rain,Sprinkler, WetGrass) 和p(Rain|Cloudy, Sprinkler,WetGrass)， 每次只对（Cloudy, Rain）中的一个变量进行采样，交替进行即可。

▌7.从方差、偏差角度解释 Boosting 和 Bagging

简单回答这个问题就是：Bagging能够提高弱分类器性能的原因是降低了方差，Boosting能够提升弱分类器性能的原因是降低了偏差。为什么这么讲呢？

首先，Bagging是 Bootstrap Aggregating 的简称，意思就是再抽样，然后在每个样本上训练出来的模型取平均。

假设有n 个随机变量，方差记为σ2，两两变量之间的相关性为ρ， 则n 个随机变量的均值的方差为。在随机变量完全独立的情况下，n 个随机变量的方差为σ2/n，也就是说方差减小到了原来的1/n。

再从模型的角度理解这个问题，对n 个独立不相关的模型的预测结果取平均，方差是原来单个模型的1/n。这个描述不甚严谨，但原理已经讲得很清楚了。当然，模型之间不可能完全独立。为了追求模型的独立性，诸多Bagging 的方法做了不同的改进。比如在随机森林算法中，每次选取节点分裂属性时，会随机抽取一个属性子集，而不是从所有属性中选取最优属性，这就是为了避免弱分类器之间过强的相关性。通过训练集的重采样也能够带来弱分类器之间的一定独立性，从而降低Bagging 后模型的方差。

再看Boosting，大家应该还记得Boosting 的训练过程。在训练好一个弱分类器后，我们需要计算弱分类器的错误或者残差，作为下一个分类器的输入。这个过程本身就是在不断减小损失函数，来使模型不断逼近“靶心”，使得模型偏差不断降低。但Boosting 的过程并不会显著降低方差。这是因为Boosting 的训练过程使得各弱分类器之间是强相关的，缺乏独立性，所以并不会对降低方差有作用。

关于泛化误差、偏差、方差和模型复杂度的关系如图12.5 所示。不难看出，方差和偏差是相辅相成，矛盾又统一的，二者并不能完全独立的存在。对于给定的学习任务和训练数据集，我们需要对模型的复杂度做合理的假设。如果模型复杂度过低，虽然方差很小，但是偏差会很高；如果模型复杂度过高，虽然偏差降低了，但是方差会很高。所以需要综合考虑偏差和方差选择合适复杂度的模型进行训练。

▌8.ResNet的提出背景和核心理论

ResNet的提出背景是解决或缓解深层的神经网络训练中的梯度消失问题。假设有一个L 层的深度神经网络，如果我们在上面加入一层， 直观来讲得到的L+1 层深度神经网络的效果应该至少不会比L 层的差。因为我们简单地设最后一层为前一层的拷贝（用一个恒等映射即可实现），并且其他层维持原来的参数即可。然而在进行反向传播时，我们很难找到这种形式的解。实际上，通过实验发现，层数更深的神经网络反而会具有更大的训练误差。在CIFAR-10 数据集上的一个结果如图9.22 所示，56 层的网络反而比20 层的网络训练误差更大，这很大程度上归结于深度神经网络的梯度消失问题。

为了解释梯度消失问题是如何产生的。回顾第3 节推导出的误差传播公式

将式（9.31）再展开一层，可以得到

可以看到误差传播可以写成参数、以及导数、连乘的形式。当误差由第L 层（记为）传播到除输入以外的第一个隐含层（记为）的时候，会涉及非常多的参数和导数的连乘，这时误差很容易产生消失或者膨胀，影响对该层参数的正确学习。因此深度神经网络的拟合和泛化能力较差，有时甚至不如浅层的神经网络模型精度更高。

ResNet过调整网络结构来解决上述问题。首先考虑两层神经网络的简单叠加（见图9.23（a）），这时输入x 经过两个网络层的变换得到H(x)，激活函数采用ReLU。反向传播时，梯度将涉及两层参数的交叉相乘，可能会在离输入近的网络层中产生梯度消失的现象。ResNet 把网络结构调整为，既然离输入近的神经网络层较难训练，那么我们可以将它短接到更靠近输出的层，如图9.23（b）所示。输入x经过两个神经网络的变换得到F(x)，同时也短接到两层之后，最后这个包含两层的神经网络模块输出H(x)=F(x)+x。

这样一来，F(x) 被设计为只需要拟合输入x 与目标输出的残差，残差网络的名称也因此而来。如果某一层的输出已经较好的拟合了期望结果，那么多加入一层不会使得模型变得更差，因为该层的输出将直接被短接到两层之后，相当于直接学习了一个恒等映射，而跳过的两层只需要拟合上层输出和目标之间的残差即可。 

ResNet 可以有效改善深层的神经网络学习问题，使得训练更深的网络成为可能，如图9.24 所示。图9.24（a）展示的是传统神经网络的结果，可以看到随着模型结构的加深训练误差反而上升；而图9.24（b） 是ResNet 的实验结果，随着模型结构的加深，训练误差逐渐降低，并且优于相同层数的传统的神经网络。

▌9.LSTM是如何实现长短期记忆功能的

有图有真相，我们首先结合LSTM 结构图以及更新的计算公式探讨这种网络如何实现其功能，如图10.2 所示。

与传统的循环神经网络相比，LSTM 仍然是基于xt 和ht−1来计算ht，只不过对内部的结构进行了更加精心的设计，加入了输入门it、遗忘门ft以及输出门ot 三个门和一个内部记忆单元ct。输入门控制当前计算的新状态以多大程度更新到记忆单元中；遗忘门控制前一步记忆单元中的信息有多大程度被遗忘掉；输出门控制当前的输出有多大程度上取决于当前的记忆单元。

经典的LSTM 中，第t 步的更新计算公式为

其中it是通过输入xt和上一步的隐含层输出ht−1进行线性变换，再经过激活函数σ 得到的。输入门it的结果是向量，其中每个元素是0 到1 之间的实数，用于控制各维度流过阀门的信息量；Wi、Ui两个矩阵和向量bi 为输入门的参数，是在训练过程中需要学习得到的。遗忘门ft 和输出门ot 的计算方式与输入门类似，它们有各自的参数W、U 和b。与传统的循环神经网络不同的是，从上一个记忆单元的状态ct−1 到当前的状态ct 的转移不一定完全取决于激活函数计算得到的状态，还由输入门和遗忘门来共同控制。

在一个训练好的网络中，当输入的序列中没有重要信息时，LSTM 的遗忘门的值接近于1，输入门的值接近于0，此时过去的记忆会被保存，从而实现了长期记忆功能；当输入的序列中出现了重要的信息时， LSTM 应当把其存入记忆中，此时其输入门的值会接近于1；当输入的序列中出现了重要信息，且该信息意味着之前的记忆不再重要时，输入门的值接近1，而遗忘门的值接近于0，这样旧的记忆被遗忘，新的重要信息被记忆。经过这样的设计，整个网络更容易学习到序列之间的长期依赖。

▌10.WGAN解决了原始 GAN 中的什么问题

直觉告诉我们：不要让生成器在高维空间傻傻地布网，让它直接到低维空间“抓”真实数据。道理虽然是这样，但是在高维空间中藏着无数的低维子空间，如何找到目标子空间呢？站在大厦顶层，环眺四周，你可以迅速定位远处的山峦和高塔，却很难知晓一个个楼宇间办公室里的事情。

你需要线索，而不是简单撒网。处在高维空间，对抗隐秘的低维空间，不能再用粗暴简陋的方法，需要有特殊武器，这就是Wasserstein 距离（见图13.7），也称推土机距离（EarthMover distance）

怎么理解这个公式？想象你有一个很大的院子，院子里有几处坑坑洼洼需要填平，四个墙角都有一堆沙子，沙子总量正好填平所有坑。搬运沙子很费力，你想知道有没有一种方案，使得花的力气最少。直觉上，每个坑都选择最近的沙堆，搬运的距离最短。但是存在一些问题，如果最近的沙堆用完了，或者填完坑后近处还剩好多沙子，或者坑到几个沙堆的距离一样，我们该怎么办？所以需要设计一个系统的方案，通盘考虑这些问题。最佳方案是上面目标函数的最优解。

可以看到，当沙子分布和坑分布给定时，我们只关心搬运沙子的整体损耗，而不关心每粒沙子的具体摆放，在损耗不变的情况下，沙子摆放可能有很多选择。对应式（13.16），当你选择一对(x,y) 时，表示把x 处的一些沙子搬到y 处的坑，可能搬部分沙子，也可能搬全部沙子，可能只把坑填一部分，也可能都填满了。x 处沙子总量为，y 处坑的大小为，从x 到y的沙子量为γ(x,y)，整体上满足等式

为什么Wasserstein 距离能克服JS 距离解决不了的问题？理论上的解释很复杂，需要证明当生成器分布随参数θ 变化而连续变化时，生成器分布与真实分布的Wasserstein 距离也随θ 变化而连续变化，并且几乎处处可导，而JS 距离不保证随θ 变化而连续变化。

通俗的解释，接着“布网”的比喻，现在生成器不再“布网”，改成“定位追踪”了，不管真实分布藏在哪个低维子空间里，生成器都能感知它在哪，因为生成器只要将自身分布稍做变化，就会改变它到真实分布的推土机距离；而JS 距离是不敏感的，无论生成器怎么变化，JS 距离都是一个常数。因此，使用推土机距离，能有效锁定低维子空间中的真实数据分布。

▌11.解释强化学习中的策略梯度

在策略梯度中，我们考虑前后两个状态之间的关系为，其中st、st+1 是相继的两个状态，at 是t 步时所采取的行动，p 是环境所决定的下个时刻状态分布。而动作at 的生成模型（策略）为，其中πθ 是以θ 为参变量的一个分布，at 从这个分布进行采样。这样，在同一个环境下，强化学习的总收益函数，完全由θ 所决定。策略梯度的基本思想就是，直接用梯度方法来优化R(θ)。

可以看出，和Q-learning 不同的是，策略梯度并不估算Q 函数本身，而是利用当前状态直接生成动作at。这有效避免了在连续状态空间上最大化Q 函数的困难。同时，直接用梯度的方法优化R(θ) 可以保证至少是局部收敛的。

要使用梯度法，首先要知道如何计算R(θ) 的导数。设τ 为某一次0到T 时间所有状态及行动的集合（称作一条轨迹），则R(θ)=E(r(τ))，其中函数r 计算了轨迹τ的得分。我们有，所以

注意最后一步是因为环境决定从而与θ 无关，因此。每个轨迹τ 所对应的梯度为 

其中sk，ak 为轨迹τ 上每一步的状态和动作。这样，给定一个策略πθ，我们可以通过模拟获得一些轨迹，对于每条轨迹，可以获得其收益r(τ) 以及每一步的<状态、行动>对，从而可以通过式（11.2）和式（11.3） 获得当前参数下对梯度的估计。一个简单的算法描述如图11.7 所示。

注意到，∇θR(θ) 实际上是一个随机变量g(τ) 的期望。我们对g(τ) 进行若干次独立采样， 可以获得对其期望的一个估计。如果能在不改变期望的前提下减少g(τ) 的方差，则能有效提高对其期望估计的效率。我们注意到， 所以有

对于任一个常量b，我们定义一个强化梯度

易知，而维持期望不变。经过计算可以得到最优的 b 为

于是，得到一个改良的算法，如图11.8 所示。

在上述策略梯度算法中，通过估算一个新的强化梯度可以有效缩减原来梯度的方差，从而提高梯度估算的效率，那么如何推出最优的b值呢？

我们回到策略梯度算法，

定义随机变量

即式（11.4）中的结果。

以上内容来自《百面机器学习》，有删改

本文作者：葫芦娃

作者：诸葛越 主编，葫芦娃 著

出版时间：2018年8月

《百面机器学习——算法工程师带你去面试》学习脉络图

该书收录了超过100道机器学习算法工程师的面试题目和解答，其中大部分源于Hulu算法研究岗位的真实场景。本书从日常工作、生活中各种有趣的现象出发，不仅囊括了机器学习的基本知识，而且还包含了成为优秀算法工程师的相关技能。