本文根据Google2013年发表的论文《Ad Click Prediction: a View from the Trenches》总结。 CTR预估中的在线学习算法 在广告点击率预估模型中，面临着特征维度巨大的问题，这导致了模型参数的存储空间极高，以及模型进行预测时的时间代价大的问题。 Online gradient descnet(OGD) 在线梯度下降法类似于随机梯度下降，一次只处理一个样本，但不同的是不要求序列的样本满足独立同分布的性质。 OGD方法在许多问题上均有不错的表现，但是获得的解不够稀疏。 L1 OGD 在OGD目标函数中添加L1正则化项，可以带来一定的稀疏性，使得模型的参...

常见的特征选择方法大致可分为三类：过滤式(filter)，包裹式(wrapper)和嵌入式(embedding) 过滤式选择 过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。  相当于先用特征选择过程个对初始特征进行“过滤”，再用过滤后的特征来训练模型。 方差阈值选择 方差很小的属性，意味着该属性的识别能力很差。极端情况下，方差为0，意味着该属性在所有样本上的值都是一个常数。  sklearn库提供feature_selection.VarianceThreshold(threshold=0.0)方法可以通过计算各个属性上的方差过滤掉小于指定阈值的属性。 单变...

循环神经网络或RNN是一类用于处理序列数据的神经网络。 展开计算图 考虑一个又外部信号 <nobr> x(t) </nobr>驱动的动态系统，   <nobr> s(t)=f(s(t−1),x(t);θ) </nobr>  当前状态包含了整个过去序列的信息。   我们可以用一个函数 <nobr> g(t) </nobr>代表t步展开后的循环：     <nobr> h(t)=g(t)(x(t),x(t−1),x(t−2),...,x(2),x(1))=f(h(t−1),x(t);θ) </nobr>...

卷积运算  <nobr> s(t)=∫x(a)w(t−a)da </nobr>  这种操作叫做卷积。卷积运算通常用星号表示：   <nobr> s(t)=(x∗w)(t) </nobr>  卷积的第一个参数通常叫做输入，第二个参数叫做核函数。输出有时被称为特征映射。  如果假设 <nobr> x </nobr>和 <nobr> w </nobr>都定义在整数t上，可定义离散形式的卷积:   <nobr> s(t)=(x∗w)(t)=∑a=−∞∞x(a)w(t−a) </nobr&g...

梯度下降沿着整个训练集的梯度方向下降。可以使用随机梯度下降很大程度地加速，沿着随机挑选的小批量数据的梯度下降。 批量算法和小批量算法 使用小批量的原因  n个样本均值的标准差是 <nobr> σn√ </nobr>，其中 <nobr> σ </nobr>是样本值真实的标准差。分母 <nobr> n√ </nobr>表明使用更多的样本来估计梯度的方法的回报是低于线性的。 另一个促使从小数目样本中获得梯度的统计估计的动机是训练集的冗余。大量样本可能对梯度做出了非常相似的贡献。 可能是由于小批量在学习过程中加入了噪声，它们会有一...

引入正则化 在深度学习背景下，大多数正则化策略都会对估计进行正则化。估计的正则化以偏差的增加换取方差的减少。一个有效的正则化是有利的权衡，也就是能显著减少方差而不过度增加偏差。 参数范数惩罚 许多正则化方法通过对目标函数 <nobr> J </nobr>添加一个参数范数惩罚 <nobr> Ω(θ) </nobr>，限制模型的学习能力。正则化后的目标函数记为 <nobr> J~ </nobr>   <nobr> J~(θ;X,y)=J(θ;X,y)+αΩ(θ) </nobr> 通常，在神经网络中只对每...

为什么引入非线性激活函数 如果不使用非线性的激活函数，无论叠加多少层，最终的输出依然只是输入的线性组合。  引入非线性的激活函数，使得神经网络可以逼近任意函数。 常用激活函数  sigmoid函数    <nobr> σ(z)=11+e−z </nobr>   <nobr> σ(z)′=σ(z)(1−σ(z)) </nobr>  sigmoid函数是最常见的激活函数，常用于输出层。其值域为0到1。 tanh双曲正切函数    <nobr> g(z)=ez−e−zez+e−z </nobr>   <nobr> g...

梯度下降法    牛顿法 牛顿法要求函数具有二阶连续偏导数，利用了函数在极小值点处一阶偏导数为0的必要条件进行优化。    拟牛顿法 基本思想  在牛顿迭代法中，需要计算Hessian矩阵的的逆矩阵 <nobr> H−1 </nobr>，这一计算比较复杂，考虑用一个n阶矩阵 <nobr> Gk=G(x(k)) </nobr>来近似代替 <nobr> H−1k=H−1(x(k)) </nobr>。   BFGS  Broyden类算法   参考资料  《统计学习方法》 附录

测试准确率和测试错误率 混淆矩阵  查准率和查全率(TPR)和FPR 查全率TPR  查准率  FPR 实际未负的样本中被错分为正样本的比例。   权衡  查全率导向任务   传统的搜索和信息提取 瘤检测 经常伴随人类专家过滤处假正例  查准率导向   搜索引擎排序，查询建议 文档分类 许多面向客户的任务（用户会记住失败的例子！！）    F1_score和Fbeta_score    <nobr> β>0 </nobr>度量了查全率对查准率的相对重要性。 PR曲线和ROC曲线 PR曲线 PR曲线一般X轴是Recall，Y轴是Precision   ROC曲线  ...

提升方法    树的生长策略    LightGBM的改进    直方图优化    通过直方图算法对内存的使用进行优化。    直方图作差加速   选取样本量少的叶子结点进行统计，就可以通过作差得到另一个叶子结点直方图。 带深度限制的叶子生长策略  提升缓存命中率    类别特征支持  并行学习支持  特征并行    数据并行    投票并行 投票并行，合并部分特征的直方图，降低通信量。    Voting parallel，参考论文“A Communication-Efficient Parallel Algorithm for Decision Tree”  其他特性    https:/...

模型函数形式    正则化的目标函数  梯度提升树 令 <nobr> y^(t)i </nobr>表示第t次迭代时对第i个样本的预测值。现在需要添加 <nobr> ft </nobr>来使得下面的目标函数最小化   <nobr> L(t)≈∑i=1nl(yi,yi^(t−1)+ft(xi))+Ω(ft) </nobr> 二阶近似算法可以用来快速优化目标函数。    样本累加统一为叶结点累加形式 可以看到当前的损失函数为     <nobr> L^(t)==∑i=1n[gift(xi)+12f2t(xi)]+Ω(...

Bagging Bagging是Bootstrap AGGregatING的缩写。  Bagging基于自助采样法(bootstrap sampling)。给定包含m个样本的数据集，先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中。这样，经过m次随机采样操作，我们得到含m个样本的采样集，初始训练集中有的样本再采样集里多次出现，有的则从未出现。  采样出T个含有m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基本学习器进行结合。  Bagging通常对分了任务使用简单投票法，对回归任务使用简***均法。  与标准AdaBoost只适...

密度聚类 基于密度的聚类，假设聚类结构能够通过样本分布的紧密程度确定。通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性。 基于密度聚类的特性  发现任意形状的聚类 处理噪声 一遍扫描（只检查局部区域来判断密度） 需要密度参数作为终止条件  一些研究  DBSCAN (KDD’96) OPTICS (sigmod’99) DENCLUE (kdd’98) CLIQUE (SIGMOD’98)也是基于网格的  DBSCAN 全称Density-Based Spatial Clustering Appliacations with Noise  DBSCAN，它基于一组”领域”参数 ...

待补充