yangliang @ Maan Coffee

离开人人时，写过2篇文章，工作总结 以及 LR算法 的总结。这个周末和占空沟通了下LR，觉得有一些新的东西自己之前不知道，有必要再次总结下，于是有了这篇文章。

文章会详细介绍LR算法在广告点击率预估上的使用，包括线下数据处理，模型训练，线上服务等。我们就先从DSP背景讲起。

0 DSP背景介绍

帮助中小广告主投放广告，对接Ad Exchange获取流量，参与实时竞价，从中赚取差价。

广告引擎负责直接对接Ad Exchange，并从广告库初步挑选广告列表。然后实时问询策略组各广告竞价价格。

策略组根据用户信息、广告信息、上下文场景信息来出价。出价主要涉及2个方面：竞价策略和CTR预估，这次我们主要讨论的就是CTR预估。

1 数据／特征提取

1.1 数据准备

原始数据：请求／竞价／展示／点击／转化等数据

数据clean／merge：脏数据的clean／以及数据链条的merge，依据某些id字段(cookie mapping等技术)

1.2 特征提取（单特征／组合特征／转化特征）

单特征示范：用户性别
组合特征示范：广告id＋广告位id
转化特征示范：url转域名；年纪特征分段

关于特征离散化／组合／转化的原因如下[知乎参考url]

特征组合／转化原因：LR模型是线性模型，为刻画y(CTR)和x变量的非线性关系，需对x做一些组合／转化等。至于如何组合和转化，这就是所谓的特征工程的事情。

特征离散化
－ 异常数据有很强的鲁棒性，模型会更稳定：比如一个特征是年龄>30是1，否则0。如果特征没有离散化，一个异常数据“年龄300岁”会给模型造成很大的干扰；
－ 运算快稀疏向量内积乘法运算速度快，计算结果方便存储，容易扩展
－ 为模型引入了非线性，能够提升模型表达能力，加大拟合

特征＋模型的权衡
李沐曾经说过：模型是使用离散特征还是连续特征，其实是一个“海量离散特征+简单模型” 同 “少量连续特征+复杂模型”的权衡。既可以离散化用线性模型，也可以用连续特征加深度学习。就看是喜欢折腾特征还是折腾模型了。通常来说，前者容易，而且可以n个人一起并行做，有成功经验
https://www.zhihu.com/question/31989952/answer/54184582

1.3 采样

按照时间重采样：近距离时间点数据重采样

实践中的数据规模

数据：七天pv/click＋当天小时级数据
特征：十多个特征簇（凭经验选择：操作系统／浏览器／IP；广告id／广告素材等；广告位id）
实际点击率：千分1/2个点；较高的5-8个点
click每天w级别；pv每天kw级别；bind请求：十亿级别

2 特征选择

特征选择评估指标：模型AUC

常见特征选择方法

• L1正则
• 计算皮尔逊系数和互信息系数（信息增益）
• 训练能对特征打分的预选模型：RandomForest和Logistic Regression等都能对模型的特征打分，通过打分获得相关性后再训练最终模型；
  https://www.zhihu.com/question/28641663

之前我们采取的方法：前项特征簇选择

3 LR算法

3.1 LR模型建立

极大似然建立模型；得到最优化目标函数
误差满足高斯分布的前提：极大似然 等价 最小二乘法

3.2 LR模型求解

LR模型的目标函数是一个凸函数，求解凸问题有很多通用的方法。针对大规模的LR，也有针对性的算法。

各种优化算法的基本思路都是：寻找搜索方向以及计算最佳步长。梯度法；牛顿法；BFGS／L-BFGS；OWLQN(LR带L1正则)
梯度法：利用梯度信息寻找最速下降方向。利用平面去逼近原函数，一阶收敛
牛顿法：利用Hessian矩阵寻找下降方向。利用二次曲面去逼近原函数，二阶收敛。－Hessian逆矩阵，计算代价大
BFGS(最好的拟牛顿算法)：根据迭代的最近k步信息（函数值，梯度信息）来构造Hessian矩阵的逆
L-BFGS：BFGS的空间复杂度是o(n^2)，此算法将空间复杂度降为o(n*k)
OWLQN(LR带L1正则)：L1没有梯度，于是提出次梯度的概念

拟牛顿法：采用一定的方法来构造与Hessian矩阵相似的正定矩阵，而这个构造方法计算量比牛顿法小

5 L1/L2正则深入理解

1. 好处：防止过拟合；L1产生稀疏解

2. 含义
似然函数一般是p（y|x,w)，在此基础上乘上p(w)，就得到加入先验的模型，降低模型复杂度
L(w) ＝ p(y|X;w) * p(w)

假设原模型是残差符合高斯分布的线性回归
如果假设w符合高斯分布 -> L2范数
如果假设w符合拉普拉斯分布-> L1范数

先说结论：误差服从高斯分布的情况下， 最小二乘法等价于极大似然估计

从概率论的角度：
Least Square 的解析解可以用 Gaussian 分布以及最大似然估计求得
Ridge 回归可以用 Gaussian 分布和最大后验估计解释
LASSO 回归可以用 Laplace 分布和最大后验估计解释
https://www.zhihu.com/question/35322351

为什么 LR 模型要使用 sigmoid 函数？
满足一些大前提条件下熵最大的解，有paper从最大熵角度证明。
这个和信息论中信息定义函数很相似，可以通过定义好的信息熵性质求解得到信息的定义函数。
https://www.zhihu.com/question/35322351

6 其他

1. log loss损失函数／auc 表示含义
logloss更关注和观察数据的吻合程度，AUC更关注rank order
https://www.zhihu.com/question/54009615

AUC：从排序的角度评估模型预估效果；
MAE（Mean Absolute Error）/MSE（Mean Squared Error），从准确率的角度评估模型预估效果；
Loss：从拟合训练数据的角度评估模型预估效果；
http://www.flickering.cn/uncategorized/2014/10/%E8%BD%AC%E5%8C%96%E7%8E%87%E9%A2%84%E4%BC%B0-2%E9%80%BB%E8%BE%91%E5%9B%9E%E5%BD%92%E6%8A%80%E6%9C%AF/


2. 模型过拟合/模型矫正
特征层面：广告id：高频／低频广告(分类)
模型矫正－ctr预估矫正
分桶矫正
保顺回归

3.其他模型：FM／NB／SVM
LR和NB分别作为Discriminative and Generative Algorithm的代表，虽属不同派系，但在一定假设条件下，却有一定内在联系。从这个联系的推倒过程也可以看到LR模型的可解释性，LR模型求出来的权重实际代表这个特征在正负样本中的均值差异大小。
符号：和预估值的正负相关性
大小：特征的重要程度（均值差异的大小）
常数项含义：即含有普通权重的信息，同时也包含正负样本比信息

Ref