沙韬伟，苏宁易购高级算法工程师。
曾任职于Hewlett-Packard、滴滴出行。
数据学院特邀讲师。
主要研究方向包括风控、推荐和半监督学习。目前专注于基于深度学习及集成模型下的用户行为模式的识别。
最近抽风，出去面试了不少公司，和不少算法工程师招聘的朋友有所交流，整理了相关比较有意思的题目，供大家参考：
1
基于每日用户搜索内容，假设只有少量已知商品的情况下，如何根据用户搜索内容获取平台内没有的新商品？
答案：这是一条类似于分词“新词获取问题”，答案是基于信息熵＋聚合度。
这边需要考虑排除，首先做stop词库，先去除形容词等。
信息熵：比如用户搜索“曲面显示屏 白色”，假设现在我们的商品库中没有显示屏这个商品，我们需要判断“显示屏”是否是潜在的商品，我们需要考虑“显示屏”左词、右词出现的可能。换句话说，如果大家都在搜索“显示屏”商品的话，会出现大量的“便宜显示屏”、“可旋转显示屏”、“显示屏 黑色”等搜索短语，根据信息熵计算公式-p∑logp，“显示屏”前后出现的词语类别越多，信息熵越大，代表用户搜索的需求越旺盛，“显示屏”越有可能是没有的商品。
聚合度：根据信息熵的理论也会出现“显示”等高频出现的干扰词，再用聚合度，比如先计算出p(“显示”)、p(“屏”)、或p(“显”)、p(“示屏”)的概率，如果“显示”是一个高频合理的搜索词的话，p(“显示”)*p(“屏”)应该远远大于p(“显示屏”)，p(“显”)＊p(“示屏”)应该远远大于p(“显示屏”)的概率，而实际电商搜索中，用户连贯搜索“显示屏”的概率才是远超其它。
2
为什么logistic回归的要用sigmoid函数？优缺点？
答案：
优点：
1.数据压缩能力，将数据规约在［0，1］之间
2.导数形式优秀，方便计算
缺点：
1.容易梯度消失，x稍大的情况下就趋近一条水平线
2.非0中心化，在神经网络算法等情况下，造成反向传播时权重的全正全负的情况。
为什么要用？
答案1: logistic是基于Bernoulli分布的假设，也就是y|X~Bernoulli分布，而Bernoulli分布的指数族的形式就是1/(1+exp(-z))
其实还有一个答案二，我当时没想起来，如就是：
对于logistic多分类而言，
x1、x2、...、xn，属于k类的概率正比于：
我们回到2类：
x1、x2、...xn属于1的概率是：
分子分母同除以分子极为1/(1+exp(-z))，z＝w11-w01，个人觉得这样的证明才有说服力
3
对比牛顿法、梯度下降法的关系
讲真，大学学完牛顿法就丢了，一时没回答出来，回来整理如下：
答案：牛顿法快于梯度下降法，且是梯度下降法的极限。
首先，我们有展开式：
f′(x+Δx)=f′(x)+f″(x)∗Δx
Δx=−μ∗f′(x)
合并两个式子，有：
f′(x+Δx)=f′(x)+f″(x)∗(−μ∗f′(x))
令f′(x+Δx)＝0，
μ＝1/f″(x)，极为牛顿法在随机梯度下降中的μ
4
两个盒子，50个红球，50个白球，问如何放球，抽到红球的概率最高？（每个盒子必须有球）
答案：一个盒子1个红球，另外一个盒子剩余的99个球
先假设第一个盒子放x个红球，y个白球，另外的一个盒子里面就有50-x红球，50-y个白球.
求的目标函数：p＝1/2(x/(x+y))+1/2((50-x)/(100-x-y))
subject to. x+y>0 & 100-x-y>0
常规解法如上，被坑了一手的是，面试的说没有常规解，我回来思考了半天，可能是盒子里面的排练顺序有差异，上层的抽取概率>下层的抽取概率，所以需要通过EM算法，先得到若干次抽取的结果下，每层的最大概率密度函数，再结合上述的结果去回答。
5
常见的正则化有是么，有什么作用，为什么l1是会把feature压缩到0而l2做不到？
答案：
(1)l1,l2正则化
l1对应python里面numpy.linalg.norm(ord=1)
形如|w1|+|w2|+|w3|+...
l2对应python里面numpy.linalg.norm(ord=2)
形如w12+w22+w3^2+...
(2)防止过拟合
其它防止过拟合的方法还有：
1.增加数据量
2.采取bagging算法，抽样训练数据
**
(3)画图解决
左边的l1，右边的l2，
l1在作图只要不是特殊情况下与正方形的边相切，一定是与某个顶点优先相交，那必然存在横纵坐标轴中的一个系数为0，起到对变量的筛选的作用。
l2的时候，其实就可以看作是上面这个蓝色的圆，在这个圆的限制下，点可以是圆上的任意一点，所以q＝2的时候也叫做岭回归，岭回归是起不到压缩变量的作用的，在这个图里也是可以看出来的。
6
我这边参考了《Do we Need Hundreds of Classifiers to Solve Real World Classification Problems》里面的结论，有兴趣的自行去搜。
答案
整体上讲：数据量越大，神经网络越好；维度越多，bagging算法越优秀；数据量上不多不少的情况下，SVM效果最好；
常用判断：roc、auc、ks、f1值、recall等；
AUC计算方法：roc曲线下方的面积积分即可，或者大数定律的投点实验
最熟悉的集成分类模型，我说的是randomforest，详述了原理及实际应用的注意点，后来我问了面试管，主要在这块想了解的是实际解决的相关项目的真实性：
1、randomforest是由若干颗cart树构成的，每棵树尽情生长不枝剪，最后采取加权投票或者均值的方式确定输出值；
2、每棵树的数据是采取bagging式的随机抽取特征及数据样本，两颗树之间的数据有可能会重复；
3、一般流程会先以sqrt(feature_number)作为每次输入的特征数，采取grid_search的方法观察tree的数量由0-500，oob的变化
这边被打断了，解释什么叫做oob，也就是out of bag，每次抽取的数据样本进行训练，没有被抽取到的数据作为检验样本，检验样本上的误差就叫做oob；
4、根据实际要求的精度上后期可以跟进调整：每次输入的特征个数、每棵树的最大深度、每个节点的分支方式（GINI还是信息增益率）、子节点最少数据量、父节点最少数据量等等。
这边又被打断了，问，什么叫做信息增益率？
首先熵的计算如下：
信息增益如下：
比如14个人，好人5个坏人9个。这14个人被通过性别划分开，10个男性中3个坏人，7个好人；4个女性中2个坏人，2个好人。
信息增益就是:
IGain＝(-5/14)log(5/14)+(-9/14)log(9/14)-(10/14(-3/10log(3/10)-7/10log(7/10))+4/14(-1/2log(1/2)-1/2log(1/2)))
看到这样的计算方式，必然会存在问题，假设我们身份证为区分类别的化，每个身份证号码都是独一无二的，势必存在存在1/n*log(1)=0这样的最佳划分，但是这样的结果就是将所有的情况分别作为子节点，很明显没有意义，所以引出下面的信息增益率。
信息增益率就是:
比如上面分人的例子，Info＝-10/14log(10/14)-4/14log(4/14)
很明显也可以看出，当你划分的子类别越多，你的info会越大，Gain_ratio就越小，信息增益率就越低，惩罚了刚才身份证分类这种行为。
这也是id3和c4.5之间最大的差异，c4.5以信息增益率代替率id3里面的信息增益，除此之外，id3只能对分类变量处理而c4.5既可以分类变量也可以连续变量，还是很强的，同时他们都可以做多分类，而后续的cart等做多分类的成本会增加（叠加的方式）。
其实，这些都很基础但是时间长了，真的很绕人，我也是先自己默默的在纸上画了挺久才和面试管聊，有点出乎我的意料。
7
我说的是LSTM。
首先，先跑出了循环的机制，同时点明了RNN潜在隐藏节点对output的影响，做了下图：
当前的预测结果，与input及上次的layer1节点下的结果相关。
正向循环：
节点1的值 = sigmoid(np.dot(输入参数,神经元1) + np.dot(上次节点1的值,潜在神经元))
输出值＝sigmoid(np.dot(节点1的值,神经元2))
误差计算：
真实y－输出值
delta：
节点2处的deltas=误差计算*sigmoid(np.dot(节点1的值,神经元2))／(1-sigmoid(np.dot(节点1的值,神经元2)))
反向修正神经元：
神经元2 += (节点1的值).T.dot(节点2处的delta)
潜藏神经元 += (上次的节点1的值).T.dot(节点1处的delta)
神经元1 += 输入值.T.dot(节点1处的delta)
核心强调了：sigmoid(np.dot(输入参数,神经元1) + np.dot(上次节点1的值,潜在神经元))，输出值与输出值及上次节点1处的输入值有关。
然后讲了简单的在语义识别的实际作用。
8
原理是送分题。
原理：在给定K值和K个初始类簇中心点的情况下,把每个点(亦即数据记录)分到离其最近的类簇中心点所代表的类簇中，优点在于易于理解和计算，缺点也是很明显，数据一多的情况计算量极大，且标签feature定义距离的难度大。
K的选择，我答的一般，欢迎大家补充，
1、根据具体的业务需求，实际需求确定最后聚成的类的个数
2、grid_search去试，看那种距离下，损失函数最小（其实这样回答不好，数据量大的情况下，机会不可能）
这边的损失函数类别较多，可能包括组内间距和／组外间距和等
3、随机抽样下的层次聚类作为预参考
理论上，随机采样的数据分布满足原来的数据集的分布，尤其是大量采样次数下的情况，针对每一个较小的数据集合采取层次聚类确定最后的聚类个数，再针对原始的数据集合进行kmeans聚类
如何选取初始点？
这个问题我被问过好多次，其实，不管是r或者python里面，或者大家日常使用中都是默认的随机选取，然后通过多次k-折等方法不断的去迭代，其实这样存在的问题就是如果初始点随机选取的有误，导致无论这么迭代都得不到最优的点，如：
随机初始点
修正初始点
在随机初始点的情况下，红色区域的部分点被蓝色和绿色侵占为己点，修正初始点，也就是将随机初始点的聚类中心全部上移的情况下，蓝色点区收回了原属于自己的点区。
之前我恶补过一片论文：《K-means 初始聚类中心的选择算法》，里面提出了两个指标来衡量：
1.k-dist
某个点 p 到它的第k 个最近点的距离为点 p 的 k-dist 值。点的 k-dist 半径范围内至少包含k + 1 个点，理论上同一个聚类中改变k值不会引起k-dist值明显变化。将 k-dist 值由小到大排序，a、b、c表示平缓点，d，e，f为跃迁点。
2.DK图
k-dist 图中相邻两点的 k-dist 值之差记为 DK。k-dist 图中相邻两点pm和pm－1的 k-dist的差为DKm=k-distm －k-distm－1 ( m ＞ 1) 。由于 k-distm 非递减，显然 DKm ＞ 0。DK 值接近的连续邻近点处于 k-dist 图的同一条平缓曲线上，即处于
同一个密度层次; DK 值大幅跳动的点处于密度转折曲线或噪声曲线上。
3.选择
对 DK 值从小到大排序，得到 DK 标准范围δ。依据 DK 标准范围内对应的数据点的分布情况，在 k-dist 图中找出 k' 个平缓曲线，代表 k' 个主要密度水平。选择每个密度水平的第一个点作为初始聚类中心。
重复若干次，得到若干组的优化聚类中心，在根据优化聚类中心组下的组内间距和／组外间距和判断那个点组为最优点组。
其实这样的开销也挺大的，目前也没有看到其它比较易理解的kmeans的初始点计算的方式。
9
当我们求解一个函数的最小值，且这个函数也被某些确定的限制条件限制的时候：
我们可以将限制条件加入f(x)中一同进行后续的偏导计算：
至于KKT我了解的其实不多，也是回来之后恶补了一下，通过例子入手：
求解上面这个问题的化，我们需要考虑构造两个约束变量a1，b1，使得
h1(x，a1)＝g1(x)＋a1^2＝a－x＋a1^2=0
h2(x，b1)＝g2(x)＋b1^2＝b－x＋b1^2=0
在根据普通拉格朗日乘子的方法对下面公式的每一项求偏导：
这个条件就是KKT条件
其实我觉得，http://www.cnblogs.com/zhangchaoyang/articles/2726873.html，这篇文章写的挺好的，想要详细了解的可以仔细参考一下。
10
之前正好整理过，内心大喜：
1、6个西格玛的原理
2、箱式图大于3/2QI＋Q3，小于Q1－3/2Qi
3、基于距离离群检测（聚类），包括欧式、马氏距离、街道距离
这边被打断了，问了马氏距离的细节，好处：
追问了协方差Sigma怎么算：
Cov(X,Y)=E(XY)-E(X)E(Y)
追问了什么时候用马氏距离比较好：
举例很有名的曲线分布图，如下：
4.pca的基于特征值压缩的方法
5.基于isolation forest识别的方法。
这边被追问了一次原理：
method:
1.从原始数据中随机选择一个属性feature；
2.从原始数据中随机选择该属性的下的一个样本值value；
3.根据feature下的value对每条记录进行分类，把小于value的记录放在左子集，把大于等于value的记录放在右子集；
4.repeat 1-3 until：
4.1.传入的数据集只有一条记录或者多条一样的记录；
4.2.树的高度达到了限定高度；
以s(x,n)为判断数据是否异常的衡量指标。
其中，h(x)为x对应的节点深度，c(n)为样本可信度，s(x,n)~[0,1]，正常数据来讲s(x,n)小于0.8，s(x,n)越靠近1，数据异常的可能性越大。
详细的可以参见我的另一篇博客：http://www.jianshu.com/p/ac6418ee8e3f
本来准备一次写完的，后来写着写着发现真的挺多，准备写个系列，最后谢谢大家的阅读。
沙韬伟，苏宁易购高级算法工程师。
曾任职于Hewlett-Packard、滴滴出行。
数据学院特邀讲师。
主要研究方向包括风控、推荐和半监督学习。目前专注于基于深度学习及集成模型下的用户行为模式的识别。
接着上回写的《最全常见算法工程师面试题目整理(一)》,继续填接下来的坑。
11
答案：
boost的核心思想不同于bagging，它在基于样本预测结果对照与真实值得差距，进行修正，再预测再修正，逐步靠近正确值。
我对adaboost和gbdt了解的也不算很全面：大概的梳理如下：
不足：
1、adaboost存在异常点敏感的问题；
2、gbdt一定程度上优化了adaboost异常点敏感的问题，但是存在难以并行的缺点；
3、两者的目标都是优化bias，必然导致训练出来的数据var的不稳定。
亮点：
1.发现非线性的特征关系，网格化的切分feature
2.拟合的效果相较于其他分类器更加精准，且训练参数较少
adaboost初始数据权重都是1/M，然后通过训练每一个弱分类器Classifier使得在每一次y_pred误差最小，得到每一个弱Classifier的权重方法对：（αi，yi）然后提高错分了的数据的权重，降低正确分类的数据权重，循环训练，最后组合最后若干次的训练弱Classifier对，得到强分类器。
其中，αi由误差决定：
该弱分类器分类错误率em越大，则该若分类器作用越小。
剖析了原理之后，我们发现，这样做对异常点非常敏感，异常点非常容易错分，会影响后续若干个弱分类器。
gbdt的核心在于下面这个公式：
L（y，y_pred）：预测值与实际值间的误差
F(x):前若干个弱分类器的组合。
关键的在于当前预测结果=对前若干个弱分类器+当前弱分类器修正，所以对前若干个分类器组合求偏导的方向进行梯度处理，保证L（x）出来的值最小。
这边结果在于你选取什么样的误差函数：
Loss即为损失函数，Derivative即为导数。
除此之外，在每一步弱分类器构建的同时，它还考虑了正则化：
Ω=入T+μ*linalg.norm(f(xi))
T为子叶节点数目，同时也对预测结果得分的值进行了l1或者l2压缩，避免过拟合。
我个人更喜欢用xgboost，在求解速度上，对异常值处理上面都要比gbdt要快，而且基于R、python版本都有package。
12
听说你做过用户关系，你用的什么方法？社群算法有了解，讲讲什么叫做Modularity Q？
答案一、我用的是Jaccard相关。
比如，用户1一共收过150个红包，发了100个红包，其中20个被用户2抢过。
用户2一共收过100个红包，发了50个红包，其中30个被用户1抢过。
similarity(user1=>user2)=(30+20)/(150+100)
similarity(user2=>user1)=(30+20)/(50+100)
similarity(user2=>user1)=(30+20+30+20)/(150+100+50+100)
答案2、社区算法主要是用来衡量用户关系网中，不同用户、链接、信息之间的相似程度。
本来这边我准备讲pagerank的，结果被打断了，说需要讲内部结构相关的，其实我觉得PageRank这边来描述更加合适。不过，无所谓，我这边谈的是一个很基本的叫做：Kernighan-Lin算法（后面简称了KL算法）
KL算法中，先随机切分原数据集群，得到不同社区集，随机交换不同社区集内的不同点，观察优化值得变化程度是否为正向，循环即可。
共需执行次数：循环次数x集群A内点的个数x集群B内点的个数
感觉这边答的不行，被嫌弃了，有知道的大神可以自行去研究一下相关的社区算法，我这边只了解PageRank和LK。
答案3、Q-modularity：
这个简单，E：关系点连接线之间的个数，I：关系点连接线两端都在社群内的数量，O：关系点连接线有至少一端在社群外的连接线的数量。
这个指标是用来衡量社群划分的稳定性的，讲真我也没用过，只是在周志华的算法的书上看过。
13
讲真，这个点，我起码说了有25分种，对面的面试管也很耐心的听完了，并且还给予了很多点的反馈，个人觉得非常受到尊重，我下面细节梳理一下。
首先，我个人非常赞同阿里现在的推荐算法这边的设计思路：
推荐＝人＋场景＋物
其中，
人＝新用户＋老用户＋综合特征＋...
场景＝属性偏好＋周期属性＋黏度偏好＋...
物＝相关性＋物品价值＋特殊属性＋...
接下来，我简单的剖析三个最常见也最重要的问题：
很多人有一种错觉，只要业务上线时间长了就不存在所谓的冷启动问题，实则不是，新用户是持续进入的、流失用户也是在增长的、很多盲目用户（没有有价值行为）等等都可以归纳为冷启动问题，这类问题的核心在于你可用的数据很少，甚至没有，我这边采取的是热门推荐的方法。
然而在热门推荐的算法中，我这边推荐一些方法：
威尔逊区间法：综合考虑总的行为用户中，支持率与支持总数的平衡
hacker new排序：综合考虑时间对支持率的影响
pagerank排序：考虑用户流向下的页面权重排序
梯度效率排序：考虑商品增速下的支持率的影响
...
方法很多，但是核心的一点是热门推荐是冷启动及实时推荐必不可少的一环，优化好实时推荐的算法是占到一个好的推荐算法的30%以上的权重的，切忌0推荐。
这个是苏宁易购的首页推荐位，1、2、3分别是三个推荐位，我们在做算法的时候常常会特别注意，不能用太多相关性比较高的变量，会产生共线性，但在推荐内容上，“58同城”的算法推荐团队之前有一份研究证明，同一个页面上由不同算法产出的推荐结果不存在相互影响。
所以，我非常赞同不同的算法产出不同的结果同时展示，因为我们不知道对目标用户是概率模型、距离模型、线性模型等不同模型中哪个产出的结果更加合适。
关于常用的推荐算法，我之前梳理过，这边也不再多加重复，需要仔细研究的可看我上面的图，或者看我之前的文章：《深度学习下的电商商品推荐》（http://www.jianshu.com/p/00a28141521f）、《偏RSVD及扩展的矩阵分解方法》（http://www.jianshu.com/p/a3e633e396a0）等等。
我在苏宁呆的时间不长，但是我有个感觉，身边算法工程师很容易把自己陷入数字陷阱，近乎疯狂去用各种算法去拟合当前的用户数据，以求得得到高的ctr或者转化率。
不同的推荐场景需要使用不同的用户行为。举例假设存在经典的关系：买了炸鸡和番茄酱的用户，接下来的一周有35%的用户会来买汽水。所以，很多工程师会选择只要买了炸鸡和番茄酱的用户，就弹窗汽水，因为就35%的百分比而言，是非常高的支持度了。其实只要有用户画像的支持就会发现，这35%的用户中，80%的都是年龄在青少年，如果在推送之前做一个简单的逻辑判断只针对所有青少年进行推送汽水的话，35%轻而易举的上升到了70%，这是任何算都无法比拟的。
最上方的橙黄色的横条中，橙色代表原始的目标用户，黄色代表非目标用户，假设我们知道黑色方框所框选的用户的转化率达到最小置信度的时候，我们可以通过特征映射、非线性分解、用户画像刻画等不同方法得到左右完全不同的新的用户分布，在同样的用户框选占比下，效果也是完全不同的。
真实推荐中，比如针对用户冬装推荐，我不仅仅以用户近期的搜索、浏览、购买商品等行为判断用户的偏好，我也根据他夏天的购买风格款式、他的年龄、生理性别、浏览性别等综合判断他可能会买什么。推荐算法才不会是冷漠的。
至于想要了解具体实现算法及创新的一些想法可以看上方的脑图，但是我觉得那并不是最重要。
14
P：很快可以得出解的问题
NP：一定有解，但可很快速验证答案的问题
后面两个我没答出来，网上搜了下，分享下：
NP-Hard：比所有的NP问题都难的问题
NP-Complete：满足两点：
1、是NP-Hard的问题
2、是NP问题
个人不喜欢这种问题。
15
当被问了第一个问题的时候，我愣了下，因为我觉得挺简单的，为什么要问这个，我感觉接下来有坑。
我回答的是：
先甩出了下面的图解释了一波欠拟合、正常、过拟合：
然后举了几个例子：
针对error递归的问题，l1，l2正则化
扩充数据量，使得数据更加符合真实分布
bagging等算法技巧
当问到为什么的时候，我觉得自己回答的不好，有点蛋疼：
我说的是，l1以：
l2以：
l1中函数与约束点偏向相切于四个端点，端点处压缩了某个特征＝0；l2中函数与约束点偏向相切于圆，会造成某些特征值压缩的接近于0；
根据奥卡姆剃刀原理，当两个假说具有完全相同的解释力和预测力时，我们以那个较为简单的假说作为讨论依据，而通常过拟合的模型的特征维度过高过多，所以一定程度可以缓解过拟合。
面试管以一种奇怪的眼神看着我，然后表示他其实想让我通过先验概率解释，不过我这样说仿佛也有道理。我回来之后就研究了一下，比如l2，大致如下：
首先，我们确定两点：
l2，其实就给了系数w一个期望是0，协方差矩阵是 1/alpha的先验分布。l1对应的是Laplace先验。
我们相当于是给模型参数w设置一个协方差为1/alpha 的零均值高斯分布先验。
根据贝叶斯定律：
这一步我没看懂，我计算了半天也没由最大似然估计算出下面这个式子，有会的朋友可以私信我一下。
有了上面的式子就很简单了，alpha在0-正无穷之间，如果a接近0的话，左侧及为正常的MSE也就是没有做任何的惩罚。如果alpha越大的话，说明预测值越接近真实值的同时，协方差也控制的很小，模型越平稳，Var也越小，所以整体的模型更加有效，避免了过拟合导致训练数据拟合效果很差的问题。
到这里，我觉得常见的算法题目都讲完了，很多简单的知识点我没有提，上面这些算是比较经典的，我没答出来的，希望对大家有所帮助，最后谢谢大家的阅读。