转：机器学习中的范数规则化之（一）L0、L1与L2范数
机器学习中的范数规则化之（一）L0、L1与L2范数
&今天我们聊聊机器学习中出现的非常频繁的问题：过拟合与规则化。我们先简单的来理解下常用的L0、L1、L2和核范数规则化。最后聊下规则化项参数的选择问题。这里因为篇幅比较庞大，为了不吓到大家，我将这个五个部分分成两篇博文。知识有限，以下都是我一些浅显的看法，如果理解存在错误，希望大家不吝指正。谢谢。
&监督机器学习问题无非就是“minimizeyour error while
regularizing your
parameters”，也就是在规则化参数的同时最小化误差。最小化误差是为了让我们的模型拟合我们的训练数据，而规则化参数是防止我们的模型过分拟合我们的训练数据。多么简约的哲学啊！因为参数太多，会导致我们的模型复杂度上升，容易过拟合，也就是我们的训练误差会很小。但训练误差小并不是我们的最终目标，我们的目标是希望模型的测试误差小，也就是能准确的预测新的样本。所以，我们需要保证模型“简单”的基础上最小化训练误差，这样得到的参数才具有好的泛化性能（也就是测试误差也小），而模型“简单”就是通过规则函数来实现的。另外，规则项的使用还可以约束我们的模型的特性。这样就可以将人对这个模型的先验知识融入到模型的学习当中，强行地让学习到的模型具有人想要的特性，例如稀疏、低秩、平滑等等。要知道，有时候人的先验是非常重要的。前人的经验会让你少走很多弯路，这就是为什么我们平时学习最好找个大牛带带的原因。一句点拨可以为我们拨开眼前乌云，还我们一片晴空万里，醍醐灌顶。对机器学习也是一样，如果被我们人稍微点拨一下，它肯定能更快的学习相应的任务。只是由于人和机器的交流目前还没有那么直接的方法，目前这个媒介只能由规则项来担当了。
&还有几种角度来看待规则化的。规则化符合奥卡姆剃刀(Occam's
razor)原理。这名字好霸气，razor！不过它的思想很平易近人：在所有可能选择的模型中，我们应该选择能够很好地解释已知数据并且十分简单的模型。从贝叶斯估计的角度来看，规则化项对应于模型的先验概率。民间还有个说法就是，规则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项(regularizer)或惩罚项(penalty
&一般来说，监督学习可以看做最小化下面的目标函数：
&其中，第一项L(yi,f(xi;w))
衡量我们的模型（分类或者回归）对第i个样本的预测值f(xi;w)和真实的标签yi之前的误差。因为我们的模型是要拟合我们的训练样本的嘛，所以我们要求这一项最小，也就是要求我们的模型尽量的拟合我们的训练数据。但正如上面说言，我们不仅要保证训练误差最小，我们更希望我们的模型测试误差小，所以我们需要加上第二项，也就是对参数w的规则化函数Ω(w)去约束我们的模型尽量的简单。
& &&OK，到这里，如果你在机器学习浴血奋战多年，你会发现，哎哟哟，机器学习的大部分带参模型都和这个不但形似，而且神似。是的，其实大部分无非就是变换这两项而已。对于第一项Loss函数，如果是Square
loss，那就是最小二乘了；如果是Hinge Loss，那就是著名的SVM了；如果是exp-Loss，那就是牛逼的
Boosting了；如果是log-Loss，那就是Logistic
Regression了；还有等等。不同的loss函数，具有不同的拟合特性，这个也得就具体问题具体分析的。但这里，我们先不究loss函数的问题，我们把目光转向“规则项Ω(w)”。
&规则化函数Ω(w)也有很多种选择，一般是模型复杂度的单调递增函数，模型越复杂，规则化值就越大。比如，规则化项可以是模型参数向量的范数。然而，不同的选择对参数w的约束不同，取得的效果也不同，但我们在论文中常见的都聚集在：零范数、一范数、二范数、迹范数、Frobenius范数和核范数等等。这么多范数，到底它们表达啥意思？具有啥能力？什么时候才能用？什么时候需要用呢？不急不急，下面我们挑几个常见的娓娓道来。
一、L0范数与L1范数
&L0范数是指向量中非0的元素的个数。如果我们用L0范数来规则化一个参数矩阵W的话，就是希望W的大部分元素都是0。这太直观了，太露骨了吧，换句话说，让参数W是稀疏的。OK，看到了“稀疏”二字，大家都应该从当下风风火火的“压缩感知”和“稀疏编码”中醒悟过来，原来用的漫山遍野的“稀疏”就是通过这玩意来实现的。但你又开始怀疑了，是这样吗？看到的papers世界中，稀疏不是都通过L1范数来实现吗？脑海里是不是到处都是||W||1影子呀！几乎是抬头不见低头见。没错，这就是这节的题目把L0和L1放在一起的原因，因为他们有着某种不寻常的关系。那我们再来看看L1范数是什么？它为什么可以实现稀疏？为什么大家都用L1范数去实现稀疏，而不是L0范数呢？
&L1范数是指向量中各个元素绝对值之和，也有个美称叫“稀疏规则算子”（Lasso
regularization）。现在我们来分析下这个价值一个亿的问题：为什么L1范数会使权值稀疏？有人可能会这样给你回答“它是L0范数的最优凸近似”。实际上，还存在一个更美的回答：任何的规则化算子，如果他在Wi=0的地方不可微，并且可以分解为一个“求和”的形式，那么这个规则化算子就可以实现稀疏。这说是这么说，W的L1范数是绝对值，|w|在w=0处是不可微，但这还是不够直观。这里因为我们需要和L2范数进行对比分析。所以关于L1范数的直观理解，请待会看看第二节。
&对了，上面还有一个问题：既然L0可以实现稀疏，为什么不用L0，而要用L1呢？个人理解一是因为L0范数很难优化求解（NP难问题），二是L1范数是L0范数的最优凸近似，而且它比L0范数要容易优化求解。所以大家才把目光和万千宠爱转于L1范数。
&OK，来个一句话总结：L1范数和L0范数可以实现稀疏，L1因具有比L0更好的优化求解特性而被广泛应用。
&好，到这里，我们大概知道了L1可以实现稀疏，但我们会想呀，为什么要稀疏？让我们的参数稀疏有什么好处呢？这里扯两点：
1）特征选择(Feature Selection)：
&大家对稀疏规则化趋之若鹜的一个关键原因在于它能实现特征的自动选择。一般来说，xi的大部分元素（也就是特征）都是和最终的输出yi没有关系或者不提供任何信息的，在最小化目标函数的时候考虑xi这些额外的特征，虽然可以获得更小的训练误差，但在预测新的样本时，这些没用的信息反而会被考虑，从而干扰了对正确yi的预测。稀疏规则化算子的引入就是为了完成特征自动选择的光荣使命，它会学习地去掉这些没有信息的特征，也就是把这些特征对应的权重置为0。
2）可解释性(Interpretability)：
&另一个青睐于稀疏的理由是，模型更容易解释。例如患某种病的概率是y，然后我们收集到的数据x是1000维的，也就是我们需要寻找这1000种因素到底是怎么影响患上这种病的概率的。假设我们这个是个回归模型：y=w1*x1+w2*x2+…+w1000*x1000+b（当然了，为了让y限定在[0,1]的范围，一般还得加个Logistic函数）。通过学习，如果最后学习到的w*就只有很少的非零元素，例如只有5个非零的wi，那么我们就有理由相信，这些对应的特征在患病分析上面提供的信息是巨大的，决策性的。也就是说，患不患这种病只和这5个因素有关，那医生就好分析多了。但如果1000个wi都非0，医生面对这1000种因素，累觉不爱。
二、L2范数
&除了L1范数，还有一种更受宠幸的规则化范数是L2范数:
||W||2。它也不逊于L1范数，它有两个美称，在回归里面，有人把有它的回归叫“岭回归”（Ridge
Regression），有人也叫它“权值衰减weight
decay”。这用的很多吧，因为它的强大功效是改善机器学习里面一个非常重要的问题：过拟合。至于过拟合是什么，上面也解释了，就是模型训练时候的误差很小，但在测试的时候误差很大，也就是我们的模型复杂到可以拟合到我们的所有训练样本了，但在实际预测新的样本的时候，糟糕的一塌糊涂。通俗的讲就是应试能力很强，实际应用能力很差。擅长背诵知识，却不懂得灵活利用知识。例如下图所示（来自Ng的course）：
&上面的图是线性回归，下面的图是Logistic回归，也可以说是分类的情况。从左到右分别是欠拟合（underfitting，也称High-bias）、合适的拟合和过拟合（overfitting，也称High
variance）三种情况。可以看到，如果模型复杂（可以拟合任意的复杂函数），它可以让我们的模型拟合所有的数据点，也就是基本上没有误差。对于回归来说，就是我们的函数曲线通过了所有的数据点，如上图右。对分类来说，就是我们的函数曲线要把所有的数据点都分类正确，如下图右。这两种情况很明显过拟合了。
&OK，那现在到我们非常关键的问题了，为什么L2范数可以防止过拟合？回答这个问题之前，我们得先看看L2范数是个什么东西。
&L2范数是指向量各元素的平方和然后求平方根。我们让L2范数的规则项||W||2最小，可以使得W的每个元素都很小，都接近于0，但与L1范数不同，它不会让它等于0，而是接近于0，这里是有很大的区别的哦。而越小的参数说明模型越简单，越简单的模型则越不容易产生过拟合现象。为什么越小的参数说明模型越简单？我也不懂，我的理解是：限制了参数很小，实际上就限制了多项式某些分量的影响很小（看上面线性回归的模型的那个拟合的图），这样就相当于减少参数个数。其实我也不太懂，希望大家可以指点下。
&这里也一句话总结下：通过L2范数，我们可以实现了对模型空间的限制，从而在一定程度上避免了过拟合。
&L2范数的好处是什么呢？这里也扯上两点：
1）学习理论的角度：
&从学习理论的角度来说，L2范数可以防止过拟合，提升模型的泛化能力。
2）优化计算的角度：
&从优化或者数值计算的角度来说，L2范数有助于处理 condition
number不好的情况下矩阵求逆很困难的问题。哎，等等，这condition
number是啥？我先google一下哈。
&这里我们也故作高雅的来聊聊优化问题。优化有两大难题，一是：局部最小值，二是：ill-condition病态问题。前者俺就不说了，大家都懂吧，我们要找的是全局最小值，如果局部最小值太多，那我们的优化算法就很容易陷入局部最小而不能自拔，这很明显不是观众愿意看到的剧情。那下面我们来聊聊ill-condition。ill-condition对应的是well-condition。那他们分别代表什么？假设我们有个方程组AX=b，我们需要求解X。如果A或者b稍微的改变，会使得X的解发生很大的改变，那么这个方程组系统就是ill-condition的，反之就是well-condition的。我们具体举个例子吧：
&咱们先看左边的那个。第一行假设是我们的AX=b，第二行我们稍微改变下b，得到的x和没改变前的差别很大，看到吧。第三行我们稍微改变下系数矩阵A，可以看到结果的变化也很大。换句话来说，这个系统的解对系数矩阵A或者b太敏感了。又因为一般我们的系数矩阵A和b是从实验数据里面估计得到的，所以它是存在误差的，如果我们的系统对这个误差是可以容忍的就还好，但系统对这个误差太敏感了，以至于我们的解的误差更大，那这个解就太不靠谱了。所以这个方程组系统就是ill-conditioned病态的，不正常的，不稳定的，有问题的，哈哈。这清楚了吧。右边那个就叫well-condition的系统了。
&还是再啰嗦一下吧，对于一个ill-condition的系统，我的输入稍微改变下，输出就发生很大的改变，这不好啊，这表明我们的系统不能实用啊。你想想看，例如对于一个回归问题y=f(x)，我们是用训练样本x去训练模型f，使得y尽量输出我们期待的值，例如0。那假如我们遇到一个样本x’，这个样本和训练样本x差别很小，面对他，系统本应该输出和上面的y差不多的值的，例如0.00001，最后却给我输出了一个0.9999，这很明显不对呀。就好像，你很熟悉的一个人脸上长了个青春痘，你就不认识他了，那你大脑就太差劲了，哈哈。所以如果一个系统是ill-conditioned病态的，我们就会对它的结果产生怀疑。那到底要相信它多少呢？我们得找个标准来衡量吧，因为有些系统的病没那么重，它的结果还是可以相信的，不能一刀切吧。终于回来了，上面的condition
number就是拿来衡量ill-condition系统的可信度的。condition
number衡量的是输入发生微小变化的时候，输出会发生多大的变化。也就是系统对微小变化的敏感度。condition
number值小的就是well-conditioned的，大的就是ill-conditioned的。
&如果方阵A是非奇异的，那么A的conditionnumber定义为：
&也就是矩阵A的norm乘以它的逆的norm。所以具体的值是多少，就要看你选择的norm是什么了。如果方阵A是奇异的，那么A的condition
number就是正无穷大了。实际上，每一个可逆方阵都存在一个condition
number。但如果要计算它，我们需要先知道这个方阵的norm（范数）和Machine
Epsilon（机器的精度）。为什么要范数？范数就相当于衡量一个矩阵的大小，我们知道矩阵是没有大小的，当上面不是要衡量一个矩阵A或者向量b变化的时候，我们的解x变化的大小吗？所以肯定得要有一个东西来度量矩阵和向量的大小吧？对了，他就是范数，表示矩阵大小或者向量长度。OK，经过比较简单的证明，对于AX=b，我们可以得到以下的结论：
&也就是我们的解x的相对变化和A或者b的相对变化是有像上面那样的关系的，其中k(A)的值就相当于倍率，看到了吗？相当于x变化的界。
& &对condition
number来个一句话总结：conditionnumber是一个矩阵（或者它所描述的线性系统）的稳定性或者敏感度的度量，如果一个矩阵的condition
number在1附近，那么它就是well-conditioned的，如果远大于1，那么它就是ill-conditioned的，如果一个系统是ill-conditioned的，它的输出结果就不要太相信了。
&好了，对这么一个东西，已经说了好多了。对了，我们为什么聊到这个的了？回到第一句话：从优化或者数值计算的角度来说，L2范数有助于处理
number不好的情况下矩阵求逆很困难的问题。因为目标函数如果是二次的，对于线性回归来说，那实际上是有解析解的，求导并令导数等于零即可得到最优解为：
&然而，如果当我们的样本X的数目比每个样本的维度还要小的时候，矩阵XTX将会不是满秩的，也就是XTX会变得不可逆，所以w*就没办法直接计算出来了。或者更确切地说，将会有无穷多个解（因为我们方程组的个数小于未知数的个数）。也就是说，我们的数据不足以确定一个解，如果我们从所有可行解里随机选一个的话，很可能并不是真正好的解，总而言之，我们过拟合了。
&但如果加上L2规则项，就变成了下面这种情况，就可以直接求逆了：
&这里面，专业点的描述是：要得到这个解，我们通常并不直接求矩阵的逆，而是通过解线性方程组的方式（例如高斯消元法）来计算。考虑没有规则项的时候，也就是λ=0的情况，如果矩阵XTX的
condition number 很大的话，解线性方程组就会在数值上相当不稳定，而这个规则项的引入则可以改善condition
&另外，如果使用迭代优化的算法，condition number
太大仍然会导致问题：它会拖慢迭代的收敛速度，而规则项从优化的角度来看，实际上是将目标函数变成λ-strongly
convex（λ强凸）的了。哎哟哟，这里又出现个λ强凸，啥叫λ强凸呢？
& &当f满足：
&时，我们称f为λ-stronglyconvex函数，其中参数λ&0。当λ=0时退回到普通convex
函数的定义。
&在直观的说明强凸之前，我们先看看普通的凸是怎样的。假设我们让f在x的地方做一阶泰勒近似（一阶泰勒展开忘了吗？f(x)=f(a)+f'(a)(x-a)+o(||x-a||).）：
& &直观来讲，convex
性质是指函数曲线位于该点处的切线，也就是线性近似之上，而 strongly convex
则进一步要求位于该处的一个二次函数上方，也就是说要求函数不要太“平坦”而是可以保证有一定的“向上弯曲”的趋势。专业点说，就是convex
可以保证函数在任意一点都处于它的一阶泰勒函数之上，而strongly
convex可以保证函数在任意一点都存在一个非常漂亮的二次下界quadratic lower
bound。当然这是一个很强的假设，但是同时也是非常重要的假设。可能还不好理解，那我们画个图来形象的理解下。
&大家一看到上面这个图就全明白了吧。不用我啰嗦了吧。还是啰嗦一下吧。我们取我们的最优解w*的地方。如果我们的函数f(w)，见左图，也就是红色那个函数，都会位于蓝色虚线的那根二次函数之上，这样就算wt和w*离的比较近的时候，f(wt)和f(w*)的值差别还是挺大的，也就是会保证在我们的最优解w*附近的时候，还存在较大的梯度值，这样我们才可以在比较少的迭代次数内达到w*。但对于右图，红色的函数f(w)只约束在一个线性的蓝色虚线之上，假设是如右图的很不幸的情况（非常平坦），那在wt还离我们的最优点w*很远的时候，我们的近似梯度(f(wt)-f(w*))/(wt-w*)就已经非常小了，在wt处的近似梯度&f/&w就更小了，这样通过梯度下降wt+1=wt-α*(&f/&w)，我们得到的结果就是w的变化非常缓慢，像蜗牛一样，非常缓慢的向我们的最优点w*爬动，那在有限的迭代时间内，它离我们的最优点还是很远。
& &所以仅仅靠convex
性质并不能保证在梯度下降和有限的迭代次数的情况下得到的点w会是一个比较好的全局最小点w*的近似点（插个话，有地方说，实际上让迭代在接近最优的地方停止，也是一种规则化或者提高泛化性能的方法）。正如上面分析的那样，如果f(w)在全局最小点w*周围是非常平坦的情况的话，我们有可能会找到一个很远的点。但如果我们有“强凸”的话，就能对情况做一些控制，我们就可以得到一个更好的近似解。至于有多好嘛，这里面有一个bound，这个
bound 的好坏也要取决于strongly
convex性质中的常数α的大小。看到这里，不知道大家学聪明了没有。如果要获得strongly
convex怎么做？最简单的就是往里面加入一项(α/2)*||w||2。
& &呃，讲个strongly
convex花了那么多的篇幅。实际上，在梯度下降中，目标函数收敛速率的上界实际上是和矩阵XTX的
condition number有关，XTX的 condition number
越小，上界就越小，也就是收敛速度会越快。
这一个优化说了那么多的东西。还是来个一句话总结吧：L2范数不但可以防止过拟合，还可以让我们的优化求解变得稳定和快速。
&好了，这里兑现上面的承诺，来直观的聊聊L1和L2的差别，为什么一个让绝对值最小，一个让平方最小，会有那么大的差别呢？我看到的有两种几何上直观的解析：
1）下降速度：
&我们知道，L1和L2都是规则化的方式，我们将权值参数以L1或者L2的方式放到代价函数里面去。然后模型就会尝试去最小化这些权值参数。而这个最小化就像一个下坡的过程，L1和L2的差别就在于这个“坡”不同，如下图：L1就是按绝对值函数的“坡”下降的，而L2是按二次函数的“坡”下降。所以实际上在0附近，L1的下降速度比L2的下降速度要快。所以会非常快得降到0。不过我觉得这里解释的不太中肯，当然了也不知道是不是自己理解的问题。
&L1在江湖上人称Lasso，L2人称Ridge。不过这两个名字还挺让人迷糊的，看上面的图片，Lasso的图看起来就像ridge，而ridge的图看起来就像lasso。
2）模型空间的限制：
&实际上，对于L1和L2规则化的代价函数来说，我们可以写成以下形式：
&也就是说，我们将模型空间限制在w的一个L1-ball
中。为了便于可视化，我们考虑两维的情况，在(w1, w2)平面上可以画出目标函数的等高线，而约束条件则成为平面上半径为C的一个
norm ball 。等高线与 norm ball 首次相交的地方就是最优解：
& &可以看到，L1-ball 与L2-ball
的不同就在于L1在和每个坐标轴相交的地方都有“角”出现，而目标函数的测地线除非位置摆得非常好，大部分时候都会在角的地方相交。注意到在角的位置就会产生稀疏性，例如图中的相交点就有w1=0，而更高维的时候（想象一下三维的L1-ball
是什么样的？）除了角点以外，还有很多边的轮廓也是既有很大的概率成为第一次相交的地方，又会产生稀疏性。
& &相比之下，L2-ball
就没有这样的性质，因为没有角，所以第一次相交的地方出现在具有稀疏性的位置的概率就变得非常小了。这就从直观上来解释了为什么L1-regularization
能产生稀疏性，而L2-regularization 不行的原因了。
&因此，一句话总结就是：L1会趋向于产生少量的特征，而其他的特征都是0，而L2会选择更多的特征，这些特征都会接近于0。Lasso在特征选择时候非常有用，而Ridge就只是一种规则化而已。
&OK，就聊到这里。下一篇博文我们聊聊核范数和规则化项参数选择的问题。全篇的参考资料也请见下一篇博文，这里不重复列出。谢谢。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。马上国庆节了，首先祝大家最后都能有个满意的offer，国庆几天好好养精蓄锐。
我经常在牛客群里水群，应该不少人看我眼熟的。
本人是一个杭州渣硕，本科也很一般，和211 985半点都粘不到，没有参加过ACM，也没有参加过大型比赛。目前仍然是只有华为1个offer，其他公司都是等通知状态，厚着脸皮来发一下面经。基本状态是：华为优招offer，百度3面通过HR让节后等通知，滴滴HR通过，网易HR通过，挖财HR通过但是不能实习不给offer只能进池子。
第一次参加面试，十分紧张，紧张到很对会的问题都没有答上来。中软OS岗：
1.内存分配的流程，要具体细节； & &我答了伙伴+守护进程+page_fault的处理+slub分配器，面试官很满意。
2.虚实地址转换
3. “./”执行elf文件 操作系统做了哪些事情，为什么不用./ 不行 。（没答出，之后看了程序员修养这本书之后才懂）
1 红黑树 特性和与AVL数比较 B树比较
2 &一个包含联合体的结构体 在64位大端存储的情况下的 代码结果 （当时懵逼了 ，其实很简单，考 结构体对齐 联合体内存共享以及大小端存储）
3.kmalloc vmalloc malloc的区别
4.说一下 c语言 write文件时 OS做了什么，模块间调用关系
2.谈有关压力
3.谈有关华为
4.谈有没有女朋友
网易内推：
内推运维开发，2面之后加了额外的技术面（据说叫总监面？） 然后挂了
一面：.谈项目 ，谈linux 。谈论文
二面：你java如何（答 用得少 python用的多，面试官大黑脸） 谈项目 谈论文
三面：你想搞运维还是运维开发？我：开发 &系统运维也不错的。我：开发 &(面试官黑人问号.jpg)
1.自我介绍
2.500G文本 1G字典 统计前100的KEY &（字典树 ，结果我写了个多线程，然后面试官问了我好几次能加速吗？最后反应过来了，不行，IO没法并行。）
3.String相关字符串常量的问题，以及对象深拷贝（送分题，可惜宝宝用的是python 差点没写出来）
3.你常用Linux命令（awk sed grep telnet netstate tcpdump top ps perf） 如果不会 就少说点，问的很深，比如让你 文本按列排序 还有正则grep 很杂的。
4.用python写字符串逆序，其中baidu关键字不逆序（经典面试题）
5.谈谈对运维的理解
1.智力题（游戏的必胜策略，略难，没答出来）
2.选运维原因
3.职业规划
4 谈谈对百度运维的理解和你理想中运维的模式
1. Python的OO和其他语言的区别，多态 重载和继承 &python实现方法
2.Python的鸭子类型
3.Python的 list和 tuple
4.docker相关问答
5.openstack相关问答
6.面试官：你玩魔兽吗？为了部落 （我穿了部落的战衣去的=。=）
1.谈docker 资源隔离 生态圈 动态扩容
HR面省略，基本都一个套路
网易校招：
1.手写生产者消费者模式
2.用AWK 对一个文本第一列分组，第二列组内排序 （需要你对AWK编程很熟才行。正常人一般也不会用这么用AWK，正常做法一般先sort 然后grep - -）
3.如何测试一支笔
1.对测开理解
2.如何测试微信
3.如何定时执行某个脚本 &（ crond ）
之后是HR面
滴滴出行：
前两面是视频面，用的牛客平台：
1。自我介绍
2.常用linux命令，参考上面的
4.一个情景下多线程的设计
5.敲个99乘法表
1.自我介绍
2.定时任务
3,10分钟时间，不定长字符串数组中找公共后缀 （abcbcd zxcbcd kmibcd 这种 最后找到bcd就好，时间很短，没有自动填充，打字要快，思路要清楚）
4.10分钟时间，输入一周股价，算出 买入卖出的最大利润，（典型DP问题，还是时间短，思路要清晰，打字要快，没有IDE，所以祈祷自己记得关键字把）
5.一个高并发的题（可以只说思路）
6.一个遥控器，说说如何优化（开放题）
线下了，boss气场很足
1.谈项目中遇到的问题，如何解决的，做了哪些方案，为什么选最终方案
2 谈谈遇到不公平待遇怎么办
3.谈如何处理压力
4.找我之前的面试评价，貌似找到之后直接就送我去HR了
后面HR省略
---------------------------------------------------------------------------------------------------------------------------------
迟到的面经，大概就这样了。因为时间跨度比较久，华为是7月底面试的，最近面试有点多，问题可能有部分缺失，实在想不起来了，记得这么多我也挺佩服自己的。
谈谈技术无关的东西：
心态：最重要的，不要紧张，不要患得患失
言行：行走端正，说话不卑不亢，不要像啄木鸟（忘记哪里看到的，说是如果你说话前倾 后仰一直动的话，说明你不自行，别人潜意识里会看轻你）
学校：学校很重要 &憋说不重要。好学校大牛也多，而且好学校有潜在加成，薪水加成什么的，各位有几乎去好学校还是去好学校啊
---------------------------------------------------------------------------------------------------------------------------------
无意当收割机，目前暂时还是1 offer 。
所以面了很多。
不过我的岗位和各位开发大牛应该不冲突的，毕竟我比较偏门
---------------------------------------------------------------------------------------------------------------------------------
补充说明：
HR面基本都是问你现在有哪些offer，面过哪些公司，为什么选这个岗位，对公司的了解，工作地点的选择，家人对工作的看法，职业规划等以及一些人际关系处理方面的问题。
我都是如实回答的。
各位有什么建议也可以提
本人基本情况，本科研究生均为985（靠后），研究生阶段做了一些计算机视觉的项目（终身机器学习和迁移学习），另外参加了阿里天池大数据等数据挖掘竞赛（top10，队名 climbers 个人ID:木木三），在腾讯广告部门实习过（基础研究）。&校招阶段开始就拿到阿里内推的offer, 所以很多公司的校招就没参加了，下面就分享所面试公司的面经：
1.&腾讯&-&基础研究
一面现场面，自我介绍加挑一个项目细讲，还有场景题，第一题是&QQ&添加好友按名称搜索时，怎么区别广告号，诈骗号；第二题是微信朋友圈内容的安全鉴别；第三题是如何鉴别实施诈骗的&QQ&用户；第四题是如何做反作弊，例如公众号的刷阅读量。
二面现场面，自我介绍，聊项目，场景题如何鉴别淘宝上卖假货的商家，价格维度可以用什么策略等
2&．阿里&-&算法工程师
直通终面（一面技术面&+hr&面）
技术电话面主要是聊简历提到的竞赛项目和实习经历，数据结构题目，合并两个有序链表的方法的递归和非递归实现等。
3&．网易游戏&-&数据挖掘研究员
网易游戏的两个面试官一起面试，一面主要问项目，然后问游戏情况，如热爱游戏吗，喜欢哪些游戏，游戏等级多少，游戏的时间多少，另外根据你玩的游戏出了一个场景题，问我对于英雄联盟，假如换了一种新的开局英雄匹配算法，如何衡量新旧算法的好坏（我主要答到了&用户流失率，玩家胜率分布，游戏时间，玩家言论（游戏内，外部论坛），专家文章&）
另外出了一个题是&给定前&N&天&玩家&id,&操作时间，操作类型（登入&/&登出），玩家等级，让你预测第N+1&天的玩家登录情况。
二面主要是聊项目&+&聊三观，问游戏情况，顺便问了一下所玩游戏的平衡性问题还有数据挖掘在游戏中的应用点。
4.&百度-机器学习
一面&自我介绍&+&问项目&+&机器学习基础&+&编程题，机器学习：几种树模型的原理和对比，朴素贝叶斯分类器原理以及公式，出现估计概率值为&0&怎么处理（拉普拉斯平滑），缺点；&k-means&聚类的原理以及缺点及对应的改进；
编程题：实现求正整数平方根整数部分的函数（使用梯度下降）
5.&唯品会&-&算法助理工程师
一面二面都是聊实习内容或者竞赛，没有写代码
1.&腾讯内推&-&基础研究
一面电话面，问项目&+&远程编程，第一题是多位数用链表存储（&e.g. 123&用&1-&2-&3&存储），实现相加功能函数&第二题是两题&sql&，涉及&join,group by,max,min,sum,count&等操作的结合，以及同个题目多种写法。
二面是去微信总部现场总监面&+&组长面，主要问项目
2.&阿里内推&-&算法工程师
一面电话面&自我介绍&+项目细节+3&道数据结构题目，第一题是链表倒数第&k&节点；第二题是二叉树打印路径，第三题是矩阵中将&0&元素所在行列全置&0&的最优空间解法
二面电话面&自我介绍&+&简历所有细节&+&数据结构熟悉程度了解（堆排序等）
三面电话面&自我介绍&+&聊项目&+&机器学习基础（线性回归与逻辑回归区别等）
3.&蘑菇街内推&-&算法工程师
一面电话面，自我介绍，问简历中提到的机器学习模型，&RF&与&GBDT&区别，原理优缺点适用场景分析，哪个具备交叉验证功能等
4.&美图秀秀面试&-&机器学习岗（大数据方向）
主要问最优化方面的知识，梯度下降法的原理以及各个变种（批量梯度下降，随机梯度下降法，&mini&梯度下降法），以及这几个方法会不会有局部最优问题，牛顿法原理和适用场景，有什么缺点，如何改进（拟牛顿法）
5.&华为&-&大数据开发岗
一面二面都是聊项目，项目比赛成绩证明，为什么选择华为等；
数据挖掘岗位笔试面试涉及知识&中文书籍推荐：
周志华 《机器学习》，机器学习入门，通俗易懂，涵盖较全
李航 《统计学习方法》，机器学习的数学理论讲解
何海涛《 剑指offer》，数据结构题目，笔试面试常考题目，（还有leetcode上的题有空最好也刷一下）
程杰 《大话数据结构》，通俗易懂的数据结构入门书籍
最近秋招也已经慢慢接近尾声了，从去年&8&月底开始，先后参加了&datacastle&，阿里天池，牛客网各自举办的数据挖掘比赛（都是&top10&），今年&4&月份又先后去百度，腾讯实习，到现在秋招快结束，也将近一年的时间，最终拿到手的比较有分量的&offer&主要是腾讯，百度，华为三家企业的&offer&，都是&sp&，下面就将过去一年的一些经验做一下小总结，不一定是最合适的方法，但是当毫无头绪的时候，可以参考参考。
（一）&&&简介
1.&&&&&&&&首先介绍企业对该岗位的一些能力需求，直接贴&bat&在该方向的相应岗位&jd&：
（&1&）百度：机器学习&/&数据挖掘工程师
（&2&）阿里：算法工程师
（&3&）腾讯：基础研究
2.&&&&&&&&个人感觉数据挖掘是一个比较大的概念，可以理解为：
数据挖掘&&=&&业务知识&&+&&自然语言处理技术（&NLP&）&+&&计算机视觉技术（&CV&）&+&&机器学习&/&深度学习（&ML/DL&）
（&1&）其中业务知识具体指的是个性化推荐，计算广告，搜索，互联网金融等；&NLP&，&CV&分别是处理文本，图像视频数据的领域技术，可以理解为是将非结构化数据提取转换成结构化数据；最后的ml/dl&技术则是属于模型学习理论；
（&2&）在选择岗位时，各个公司都没有一套标准的称呼，但是所做的事情无非&2&个大方向，一种是主要钻研某个领域的技术，比如自然语言处理工程师，计算机视觉工程师，机器学习工程师等；一种是将各种领域技术应用到业务场景中去解决业务需求，比如数据挖掘工程师，推荐系统工程师等；具体的称呼不重要，重要的是平时的工作内容；
PS&：在互联网行业，数据挖掘相关技术应用比较成功的主要是推荐以及计算广告领域，而其中涉及到的数据主要也是文本，所以&NLP&技术相对来讲比较重要，至于&CV&技术主要还是在人工智能领域（无人车，人脸识别等）应用较多，本人了解有限，相关的描述会较少；
3.&&&&&&&&根据之前的分析，也可以看到该岗位所需要的&3&种基本能力分别是业务经验，算法能力与工程能力；
（二）&&&入门
1.&&&&&&&&工程能力
（&1&）编程基础：需要掌握一大一小两门语言，大的指&C++&或者&JAVA&，小的指&python&或者&shell&脚本；需要掌握基本的数据库语言；
建议：&MySQL + python + C++&；语言只是一种工具，看看语法就好；
推荐书籍：《&C++ primer plus&》
（&2&）开发平台：&Linux&；
建议：掌握常见的命令，掌握&Linux&下的源码编译原理；
推荐书籍：《&Linux&私房菜》
（&3&）数据结构与算法分析基础：掌握常见的数据结构以及操作（线性表，队，列，字符串，树，图等），掌握常见的计算机算法（排序算法，查找算法，动态规划，递归等）；
建议：多敲代码，多上&OJ&平台刷题；
推荐书籍：《大话数据结构》《剑指&offer&》
（&4&）海量数据处理平台：&hadoop&（&mr&计算模型，&java&开发）或者&spark&（&rdd&计算模型，&scala&开发），重点推荐后者；
建议：主要是会使用，有精力的话可以看看源码了解集群调度机制之类的；
推荐书籍：《大数据&spark&企业级实战》
2.&&&&&&&&算法能力
（&1&）数学基础：概率论，数理统计，线性代数，随机过程，最优化理论
建议：这些是必须要了解的，即使没法做到基础扎实，起码也要掌握每门学科的理论体系，涉及到相应知识点时通过查阅资料可以做到无障碍理解；
（&2&）机器学习&/&深度学习：掌握&常见的机器学习模型（线性回归，逻辑回归，&SVM&，感知机；决策树，随机森林，&GBDT&，&XGBoost&；贝叶斯，&&KNN&，&K-means&，&EM&等）；掌握常见的机器学习理论（过拟合问题，交叉验证问题，模型选择问题，模型融合问题等）；掌握常见的深度学习模型（&CNN，&RNN&等）；
建议：这里的掌握指的是能够熟悉推导公式并能知道模型的适用场景；
推荐书籍：《统计学习方法》《机器学习》《机器学习实战》《&》
（&3&）自然语言处理：掌握常见的方法（&tf-idf&，&word2vec&，&LDA&）；
3.&&&&&&&&业务经验
（&1&）了解推荐以及计算广告相关知识；
推荐书籍：《推荐系统实践》《计算广告》
（&2&）通过参加数据挖掘竞赛熟悉相关业务场景，常见的比赛有&Kaggle&，阿里天池，&datacastle&等；
PS:&以上都是一些入门级别的介绍，在长期的学习中，应该多看顶会&paper&，多读开源代码，多学习优秀解决方案；
PS:&以上推荐的书籍对应的电子版可以联系本人（&Q:&）
（三）&&&求职
1.&&&&&&&&简历
（&1&）格式：个人信息（姓名，联系方式，教育背景，求职意向，照片可有可无）&+&&竞赛经历&+&&实习经历&&+&&项目经历&&+&&掌握技能&&+&&获奖情况；
PS:&最好写成一页；
（&2&）加分：博客，&github&，竞赛&top10&，顶会&paper&；
PS:&如果感兴趣的话可以联系我要简历模板（&Q:&）
PS:&牛逼的简历可以让你有更多的面试机会，更关键的是让面试官在面试时潜意识给你打高分，当然前提是简历要真实，所以平时得为了牛逼的简历多做准备工作；
2.&&&&&&&&海投
（&1&）国内设有该岗位且还不错的公司：
百度，腾讯，阿里，网易（互联网，游戏，有道），华为，今日头条，滴滴研究院，一点咨讯，&360&，美团等；
（&2&）如果选择留在广东深圳发展，就业的机会比较少，比较好的主要就是百度深研，腾讯总部，华为深圳，京东好像在深圳也有个做数据挖掘的团队；（楼主倾向去深圳发展）
（&3&）个人建议在&3&月份的时候可以通过实习生的身份进入相关企业，争取实习生留用；一般企业给应届生的&hc&分配比例大概是实习生留用：校招提前批：校招正式&=4&：&3&：&3&，实习生留用相对比较容易；
（&4&）一般投递简历时，尽量联系公司内部的师兄师姐或者熟人，帮忙将简历直接给到团队&leader&手中，这样做的好处是可以同时面试同个公司的多个团队，前提是简历在公司校招系统未被锁定的前提下，具体情况多咨询公司内部熟人，在求职过程中，信息来源非常重要，一定要注意这点，不然会踩很多坑；
（&5&）加入各种求职交流群，多认识些人，共享资源；
（&6&）投简历时候尽量内推，很多公司内推可以免笔试；
PS&：笔试纯属看&rp&，总之就是多刷题，上牛客网多练练并针对性复习就好；
3.&&&&&&&&面试
（&1&）一般该岗位的面试起码都有&3&轮，&2&轮技术面，&1&面&hr&面，&hr&面主要看情商，这里不多说；&2轮技术面的区别就是越到后面面试官的级别越高，所以面试的风格也可能越偏向于技术视野等一些吹水的话题上；
（&2&）一般技术面有以下一些环节：自我介绍，项目介绍，算法提问（推公式），数据结构提问（写代码）；
1&）自我介绍：一般尽量简短，主要讲清楚自己的研究方向，所取得成就以及优势所在即可；
2&）项目介绍：简历上的项目一定要熟悉，介绍时候分三部曲：项目背景，项目方案，项目成果；对项目中涉及到的一些技术点一定要很熟悉；
3&）算法提问：一般是问常见机器学习模型原理或者一些机器学习常见问题的解决方案（比如正负样本不平衡之类的），所以常见的机器学习模型一定要很清楚原理，必须会推公式，能知道工程实现的一些trick&的话，那你就离&sp&不远了；
4&）数据结构提问：常见的数据结构一定要掌握，基础的代码一定要会手写（快排，冒泡，堆排，归并排序，二分查找，二叉树的遍历，二叉树增删查改）；剑指&offer&的题目要会；有精力的话可以刷下leetcode&；
（&3&）面试的时候多准备一些素材，在面试过程中主动引导面试官提问，比如面试官让你讲解&gbdt&原理时，这会你可以跟他说一般说起&gbdt&，我们都会跟&rf&以及&xgboost&一块讲，然后你就可以主动地向面试官输出你的知识；面试并不是死板地你问我答，而是一种沟通交流，所以尽可能地把面试转化成聊天式的对话，多输出自己一些有价值的观点而不是仅仅为了回答面试官的问题；
（&4&）在面试过程中，除了基础的东西要掌握，可以适当地向面试官展示你的一些其他的亮点，比如跟面试官谈论某些最近&paper&的进展以及一些技术方面的想法等，突出自己的与众不同；
（&5&）不同公司的面试风格都略有不同：
1&）百度：技术派，现场面，最大的风格就是写代码，&2&面技术加一面经理面，技术面必写代码；
2&）阿里：内推可以电话面，主要是聊项目跟问一些基础的数据结构方面的知识，看看剑指&offer&一般可以应付；
3&）腾讯：内推可以电话面，主要聊项目跟推公式；
4&）华为：主要聊项目，智力题以及聊价值观之类的东西；
5&）滴滴研究院：百度系，面试风格跟百度差不多；
（&6&）常见面试题（由于有的面试时间较久，主要靠记忆写下来）
1&）几种模型（&svm&，&lr&，&gbdt&，&em&）的原理以及公式推导；
2&）&rf&，&gbdt&的区别；&gbdt&，&xgboost&的区别（烂大街的问题最好从底层原理去分析回答）；
3&）决策树处理连续值的方法；
4&）特征选择的方法；
5&）过拟合的解决方法；
6&）&kmeans&的原理，优缺点以及改进；
7&）常见分类模型（&svm&，决策树，贝叶斯等）的优缺点，适用场景以及如何选型；
8&）&svm&为啥要引入拉格朗日的优化方法；
9&）假设面试官什么都不懂，详细解释&CNN&的原理；
10&）海量的&item&算文本相似度的优化方法；
11&）梯度下降的优缺点；
12&）&em&与&kmeans&的关系；
13&）&L1&与&L2&的区别以及如何解决&L1&求导困难；
14&）如何用尽可能少的样本训练模型同时又保证模型的性能；
15&）解释&word2vec&的原理以及哈夫曼树的改进；
16&）对推荐算法的未来看法；
17&）在模型的训练迭代中，怎么评估效果；
18&）有几个&G&的文本，每行记录了访问&ip&的&log&，如何快速统计&ip&出现次数最高的&10&个&ip&；如果只用linux&指令又该怎么解决；
19&）一个绳子烧完需要&1&个小时，假设所有绳子的材质都不一样，也不均匀，怎么取出&1&小时加&15&分钟；
20&）假设有个&M*N&的方格，从最左下方开始往最右上方走，每次只能往右或者往上，问有多少种走法，假设中间有若干个格子不能走，又有多少种走法；
21&）实现&hmm&的状态转移代码；
22&）最短路径代码；
23&）拼车软件是如何定价的以及如何优化；
24&）&100&张牌，每次只能抽一张，抽过的牌会丢掉，怎么选出最大的牌；
25&）怎么预测降雨量；
26&）&kmeans&代码；
27&）&mr&方案解决矩阵相乘的代码；
28&）&sql&语句的一些优化技巧；
29&）关于集群调度的一些经验&trick&掌握多少；
30&）设计一个系统可以实时统计任意&ip&在过去一个小时的访问量；
31&）设计&LRU&系统；
PS:&以上的面试题仅供参考，主要是提供一个方向，大概了解这个岗位的面试考核方向，具体还得多刷刷面经（牛客网）；
本文已收录于以下专栏：
相关文章推荐
这几天开始学tensorflow，先来做一下学习记录
一.神经网络解决问题步骤：
1.提取问题中实体的特征向量作为神经网络的输入。也就是说要对数据集进行特征工程，然后知道每个样本的特征维度，以此来...
自然语言处理的三个里程碑文章讲述了自然语言处理历史中发现的两个事实和三个里程碑式的进展。两个事实分别为：一、短语结构语法不能有效地描写自然语言。为了识别句子的语法结构，将句子中的词一个一个切分出来，然...
摘自七月算法
/question/456
1、用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。2、用C语言实现函数void...
复杂特征集、合一语法以及词汇主义方法都是在原先理性主义框架（产生式或逻辑推理）框架下做出的重大贡献。尤其词汇主义方法的发展越来越得到语料库和统计学方法的支持，这也是经验主义和理性主义方法的相互融合。他...
1. new 和 malloc的区别
2. hash 冲突 及解决办法
号上午11点半面试的百度NLP，职位是情感分析。对面试的
1、数组补丁
给出一个从小到大排好序的整数数组nums和一个整数n，在数组中添加若干个补丁（元素）使得[1,n]的区间内的所有数都可以表示成nums中若干个数的和。返回最少需要添加的补丁个数。
python的set和其他语言类似, 是一个无序不重复元素集, 基本功能包括关系测试和消除重复元素. 集合对象还支持union(联合), intersection(交), difference(差)和...
“我不知道自己毕业能拿多少年薪，但看到别人20多万，我心想‘我也可以’。” 
      本人男，2017届毕业生，目前还在实习阶段（金山云），鉴于自己的能力上的不足以及不平凡的梦想，决定放弃秋招...
他的最新文章
讲师：刘文志
讲师：陈伟
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)}