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

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

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

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

新年钟声敲响的时分临近，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）中的一个变量进行采样，交替进行即可。