用户行为定向的目的是根据用户的历史行为，来选择最合适的广告投放，按如下思路介绍：

  • 模型、目标、算法
  • 大规模数据上的应用技巧
    • 数据压缩
    • 特征选择和变换
    • 生成训练集合测试集
    • 并行的Multiplicative迭代
  • 实验设定&结论

模型、目标、算法

a.模型

$$p(y) = \frac{{{\lambda ^y}\exp \left( { - \lambda } \right)}}{{y!}},\; {\lambda _i}={w^T}{x_i} $$ $y$:预测CTR(click-through rate)，即用户某个特定类别上的点击率。 $x$:表示广告的点击, 用户的浏览行为，也可以购买、搜索等等行为。 $\lambda_t$:为相应的控制点击行为到达频繁性的参数。 点击行为是离散到达的随机变量，对数量最自然的描述规则是泊松分布。

b.目标

优化目标：
最大化似然函数：
$$ \prod\limits_i^n {p\left( {{{\mathbf{y}}_i}} \right)} = \prod\limits_i^n {\frac{{{{\left( {{{\mathbf{w}}^T}{{\mathbf{x}}_i}} \right)}^{{{\mathbf{y}}_i}}}\exp \left( { - {{\mathbf{w}}^T}{{\mathbf{x}}_i}} \right)}}{{{{\mathbf{y}}_i}!}}} $$ 转求常用log似然： $$l\left( y \right) = \log L\left( y \right) = \sum\limits_i^{} {\left( {{y_i}\log \left( \lambda \right) - \lambda - \log \left( {{y_i}!} \right)} \right)} $$

c.算法

1.梯度下降gd, 2.bfgs 3.multiplicative rule. 梯度下降更新规则： $$\Delta w = \frac{{\partial l\left( y \right)}}{{\partial {w_j}}} = \sum\limits_i {\left( {\frac{{{y_i}}}{{{\lambda _i}}}{x_{ij}} - {x_{ij}}} \right)} $$ (作者实际上采用multiplicative进行迭代，15-20轮收敛) CTR公式： $$CT{R_{ik}} = \frac{{\lambda _{ik}^{click} + \alpha }}{{\lambda _{ik}^{view} + \beta }}$$
  • 符号说明：$i,j,k$分别表示用户，特征，广告类型
  • 注1:训练数据平滑，对于CTR公式的$\alpha \beta$`按每个类别计算，结果为给新用户推荐最热的类别。
  • 注2:$\lambda = {w^T}x$为什么不用指数型$bda = \exp \left( {{w^T}x} \right)$，使用线性形式。初衷是方便在线计算,对于新的线上用户行为，$bda ' = \lambda {\delta ^{\Delta t}} + {w_j}\Delta {x_j}$
  • 注3:为什么用NMF，W用来表示用户兴趣权重的，如果用户对某类广告不感兴趣，我们把它调为零即可。
  • 注4：对于每个特征的权重$w_kj$的初始化可以用两种方式进行，
    • a.类似TF-IDF：$${w_{kj}} \leftarrow \frac{{\sum\nolimits_i {\frac{{{y_{ik}}{x_{ij}}}}{{\sum\nolimits_{j'} {{x_{ij'}}} }}} }}{{\sum\nolimits_i {{x_{ij}}} }}$$
    • b.全局类别上进行$${w_{kj}} \leftarrow \frac{{\sum\nolimits_i {\left( {{y_{ik}}{x_{ij}}} \right)\sum\nolimits_i {\left( {{y_{ik}}} \right)} } }}{{\sum\nolimits_{j'} {\left[ {\sum\nolimits_i {{y_{ik}}{x_{ij'}}} \sum\nolimits_i {{x_{ij'}}} } \right]} }}$$
      b的思考出发点是部分类别的模型训练时间较长，给一个较适合的初值，可能使得整体迭代数据速度变快。

大规模数据的应用技巧

1.log数据的预处理，指定数据的字段抽取，以cookie为单位合并数据。
2.再以用户和时间为组合键，按时间间隔合并次数 ，这里时间间隔需要和模型所需一致。一个月的数据能减少到2-3TB(这里尚未进行广告分类)

特征选择和反向索引

广告点击、页面浏览、和搜索query，这些特征空间比较复杂和稀疏，作者使用频次阈值进行筛选，得到（特征类型 click / search / view，实体entity，freq）组合，不选择互信息，互信息容易受数据稀疏影响。最后输出为3类特征的词典，从实验配置可以认为是ad_id、page_id、query，三种词典。得到上述词典以后，特征向量可以用(下标，值)的形式存储，下标指词典的偏移。
trick 1.特征过滤卡频次用cookie为单位计数的原因是防爬虫
trick 2.直接对特征卡频次，这样无需做排序取topN
trick 3.在无需排序归并的阶段，reducer可以用值排序。这样避免对复杂key进行排序，增加时耗

生成训练集合测试集

如图显示，通过滑动窗口的采集方式，可以在$o(1)$的时间内完成特征数据的生成。
图1

数据驱动的权重更新

这里主要提及下权重更新的并行化
1.通过一个稀疏矩阵D，我们想估计一个dense的权重矩阵W。给定$Y$,$X$，求得$\arg {\max _w}\log p\left( {{Y^T}|W{X^T}} \right)$的解$W^*$. （按：这里和目标泊松分布log-似然函数有关联）
2.${Y^T} \approx W{X^T}$，可以复用NMF非负矩阵分解中的高效乘法方式，通过log似然进行约束。
a. W是dense的矩阵，因为集群节点内存限制，我们需要拆开读入。由于拆以后计算$W{X^T}$复杂度较高，引入下一步的内存caching
b. In-memory Caching.对样本xy进行cache，预先求得cache内数据的 $\sum\nolimits_i {\frac{{{y_{ik}}{x_{ij}}}}{{{\lambda _{ik}}}}} $ 向后传递。
c. 按k为key进行reduce，最后累积更新到权重$W$。伪代码在论文4.5.3节

图2

实验部分：

  • 数据和参数
    a.数据来源，广告点击，页面浏览，搜索query
    b.效果衡量方式，1.baseline对比，见下表CTR lift，2.ROC曲线比较。60种主要BT行为
  • 基线模型： Logistic Regression，分别为两个模型的结果积在一起，一部分预测下一天的点击，一部分预测下一小时点击。

实验结果：

a.数据量方面：
图3
数据均分为512份，训练集不同的量带来的效果如图。
b.特征方面比较：
图4
（PS.之所以控制特征为ads和pages变化是因为，query在点击预估的影响比较小）
（之前的加速措施使得训练时间有不受特征数目显著影响的特性）
c.target时间窗方面比较（意义可能不大，略）：
d.分层抽样的效果
用户分三类：1.有点击行为 2.无广告点击，有广告view。3.广告点击和广告view都无
需要对后两类用户进行采样，第一栏的数字代表采样率。
图5
(负样本只对分母有影响，而且是提前算好的。结果看一个较小的neg采样组合一个较大的view采样可以带来一个比较好的效果)

e.引入时间间隙，模拟训练。
因为在线的训练的时候，有data延迟，在特征时间窗和目标时间窗中间插入一个间隙。带来的效果对比，右边是模拟在线的时候的效果
图6
可以看到如果无间隙的时候，CTR有显著收益，说明实时的特征对CTR预估影响较大。

总结：作者根据用户历史行为预测用户对不同类别广告的CTR，同时给了在大规模数据上的实现框架。
（summarizes by：shawn_xiao@baidu）
引文：
[1]Chen, Ye，Pavlov, Dmitry，Canny, John， Large-scale behavioral targeting, [2010]