d0evi1 Reading time ~3 minutes

介绍

在解析XGBoost的源码之前，我们先理解下陈天奇在paper《XGBoost: A Scalable Tree Boosting System》一文中提到的一些概念。

XGBoost的可扩展性(scalability)归因于一些重要的系统优化和算法优化。这些优化包括：

  • 一种新的tree-learning算法(a novel tree learning algorithm)：用于处理稀疏数据(sparse data)
  • 一种理论正确的加权分位数略图过程（a theoretically justified weighted quantile sketch procedure）：用于处理在近似的tree-learning中实例权重

由于XGBoost的并行化和分布式计算，使得learning过程比其它模型实现要快。更重要地，XGBoost实现了核外计算(out-of-core computation: 基于外存)，使得数据科学家们可以在pc机上处理上亿的训练实例。最终，会把这些技术结合起来实现一个end-to-end的系统，可以扩展到集群上。

主要内容：

  • 1.设计和建立了一个高度可扩展的end-to-end tree boosting系统
  • 2.提出了一种理论正确的加权分位数略图过程(theoretically justified weighted quantile sketch procedure)，用于高效地进行预计算
  • 3.介绍了一种新的稀疏感知算法（sparsity-aware algorithm），用于并行化tree learning
  • 4.提出了一种高效的内存感知块结构（cache-aware block structure），用于核外（out-of-core）tree learning

2.tree-boosting回顾

XGBoost的方法源自于Friedman的二阶方法。XGBoost在正则化目标函数上做了最小的改进。

2.1 正则化目标函数

对于一个含n个训练样本，m个features的结定数据集：$ D = {(x_i,y_i)} (|D|=n, x_i \in R^m, y_i \in R) $，所使用的tree ensemble model使用K次求和函数来预测输出：

\[\hat{y_{i}} = \phi(x_i) = \sum_{k=1}^{K} f_k(x_i), f_k \in F\]

…… (1)

其中，$ F = {f(x)=w_{q(x)}}，满足(q: R^m \rightarrow T, w \in R^T) $，是回归树(CART)的空间。q表示每棵树的结构，它会将一个训练样本实例映射到相对应的叶子索引上。T是树中的叶子数。每个$ f_k $对应于一个独立的树结构q和叶子权重w。与决策树不同的是，每棵回归树包含了在每个叶子上的一个连续分值，我们使用$ w_i $来表示第i个叶子上的分值。对于一个给定样本实例，我们会使用树上的决策规则(由q给定)来将它分类到叶子上，并通过将相应叶子上的分值(由w给定)做求和，计算最终的预测值。为了在该模型中学到这些函数集合，我们会对下面的正则化目标函数做最小化：

\[L(\phi) = \sum_{i}l(\hat{y_i}, y_i) + \sum_{i}\Omega(f_k)\]

……(2)

其中：$ \Omega(f) = \gamma T + \frac{1}{2}\lambda||\omega||^2 $

其中，$l$是一个可微凸loss函数（differentiable convex loss function），可以计算预测值$\hat{y_i}$与目标值$y_i$间的微分。第二项$ \Omega $会惩罚模型的复杂度。正则项可以对最终学到的权重进行平滑，避免overfitting。相类似的正则化技术也用在RGF模型(正则贪婪树)上。XGBoost的目标函数与相应的学习算法比RGF简单，更容易并行化。当正则参数设置为0时，目标函数就相当于传统的gradient tree boosting方法。

2.2 Gradient Tree Boosting

等式（2）中的tree ensemble模型将函数作为参数，不能使用在欧拉空间中的传统优化方法进行优化。模型以一种叠加的方式进行训练。正式地，$ \hat{y_i}^{(t)} $为第i个实例在第t次迭代时的预测，我们需要添加$ f_t $，然后最小化下面的目标函数：

\[L^{(t)}=\sum_{i=1}^{n}l(y_i, \hat{y_i}^{(t-1)}+f_t(x_i)) + \Omega(f_t)\]

这意味着，我们贪婪地添加$ f_t $，根据等式(2)尽可能地提升模型。使用二阶近似可以快速优化目标函数。

\[L^{(t)} \backsimeq \sum_{i=1}^{n}[l(y_i,\hat{y}^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^{2}(x_i)] + \Omega(f_t)\]

其中，$ g_i = \partial_{\hat{y}^{(t-1)}} l(y_i,\hat{y}^{(t-1)}) $ ，$ h_i = {\partial}_{\hat{y}^{(t-1)}}^{2} l(y_i, \hat{y}^{(t-1)}) $分别是loss function上的一阶梯度和二阶梯度。我们可以移除常数项，从而获得如下所示的在t次迭代时的简化版目标函数：

\[L^{(t)} = \sum_{i=1}^{n} [g_i f_t(x_i) + \frac{1}{2} h_i f_t^{2}(x_i)] + \Omega(f_t)\]

……(3)

我们定义$ I_j= \{ i | q(x_i)=j \} $是叶子j的实例集合。将(3)式进行重写，并展开$ \Omega $项：

\[L^{(t)} = \sum_{i=1}^{n} [g_i f_t(x_i) + \frac{1}{2} h_i f_t^{2}(x_i)] + \gamma T + \frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^{2} \\ = \sum_{j=1}^{T}[(\sum_{i \in I_j} g_i)w_j + \frac{1}{2}(\sum_{i \in I_j}h_i+\lambda)w_{j}^{2}]+\gamma T\]

……(4)

对于一个确定的结构q(x)，我们可以计算最优的权重 $ w_j^{\ast} $:

\[w_j^{\ast}=-\frac{\sum_{i \in I_j}g_i}{\sum_{i \in I_j}h_i+\lambda}\]

……(5)

代入(5)计算得到对应的loss最优解为：

\[L^{(t)}(q)=-\frac{1}{2}\sum_{j=1}^{T}\frac{(\sum_{i \in I_j}g_i)^2}{\sum_{i \in I_j}h_i+\lambda} + \gamma T\]

……(6)

等式(6)可以作为一个得分函数（scoring function）来衡量一棵树结构q的质量（quality）。该分值类似于决策树里的不纯度(impurity score)，只不过它从一个更宽范围的目标函数求导得到。图2展示了该分值是如何被计算的。

图2:结构得分(structure score)计算。我们只需要在每个叶子上对梯度和二阶梯度统计求和，然后应用得分公式（scoring formula）来获得质量分（quality score）。

通常，不可能枚举所有可能的树结构q。而贪婪算法会从单个叶子出发，迭代添加分枝到树中。假设$ I_L $和$ I_R $是一次划分(split)后的左节点和右节点所对应的实例集合。$ I=I_L \bigcup I_R $，接着，在split之后的loss reduction为：

\[L_{split}=\frac{1}{2}[ \frac{(\sum_{i \in I_L}g_i)^2}{\sum_{i \in I_L}h_i+\lambda} + \frac{(\sum_{i \in I_R}g_i)^2}{\sum_{i \in I_R}h_i+\lambda} - \frac{(\sum_{i \in I}g_i)^2}{\sum_{i \in I}h_i+\lambda}] - \gamma\]

……(7)

该式通常在实际中用于评估split的候选（split candidates）。

2.3 Shrinkage和列子抽样(column subsampling)

除了2.1节所提到的正则化目标函数外，还会使用两种额外的技术来进一步阻止overfitting。第一种技术是Friedman介绍的Shrinkage。Shrinkage会在每一步tree boosting时，会将新加入的weights通过一个因子$ \eta $进行缩放。与随机优化中的learning rate相类似，对于用于提升模型的新增树(future trees)，shrinkage可以减少每棵单独的树、以及叶子空间（leaves space）的影响。第二个技术是列特征子抽样(column feature subsampling)。该技术也会在RandomForest中使用，在商业软件TreeNet中的gradient boosting也有实现，但开源包中没实现。根据用户的反馈，比起传统的行子抽样（row sub-sampling：同样也支持），使用列子抽样可以阻止overfitting。列子抽样的使用可以加速并行算法的计算(后面会描述)。

3.Split Finding算法

3.1 Basic Exact Greedy Algorithm

tree learning的其中一个关键问题是，找到等式(7)的最好划分(best split)。为了达到这个目标，split finding算法会在所有特征（features）上，枚举所有可能的划分（splits）。我们称它为“完全贪婪算法(exact greedy algorithm)”。许多单机版tree-boosting实现中，包括scikit-learn，R’s gbm以及单机版的XGBoost，都支持完全贪婪算法(exact greedy algorithm)。该算法如算法1所示。它会对连续型特征（continuous features）枚举所有可能的split。为了更高效，该算法必须首先根据特征值对数据进行排序，以有序的方式访问数据来枚举等式(7)中的结构得分（structure score）的梯度统计(gradient statistics)。

[算法1]

3.2 近似算法

完全贪婪算法(exact greedy algorithm)很强大，因为它会贪婪地枚举所有可能的划分点。然而，当数据不能整个装载到内存中时，它就变得低效。在分布式设置中也存在相同的问题。为了在两种设置中支持高效地gradient tree boosting计算，需要一种近似算法。

我们总结了一个近似框架（approximate framework），重组了在文献[17,2,22]中提出的思想，如算法2所示。为了进行总结(summarize)，该算法会首先根据特征分布的百分位数(percentiles of feature distribution)，提出候选划分点(candidate splitting points)。接着，该算法将连续型特征映射到由这些候选点划分的分桶(buckets)中，聚合统计信息，基于该聚合统计找到在建议（proposal）间的最优解。

[算法2]

该算法有两个变种，取决于给定的建议（proposal）。全局变种（global variant）会在树构建的初始阶段，建议所有的候选划分，并在所有的层级（level）上使用相同的建议。局部变种（local variant）则在每次划分后重新建议（re-proposes）。比起局部法，全局法需要更少的建议步骤。然而，对于全局建议，通常需要更多的候选点，因为在每次划分之后，不需要重新定义候选。局部建议会在每次划分后重新定义候选，对于更深的树更合适。图3展示了在Higgs boson数据集上不同算法的比较。我们发现，局部建议确实需要更少的候选。如果两者的候选一样多，全局建议比局部建议会更精确。

图3: 在Higgs 10M数据集上的Test AUC收敛比较. eps参数对应于在近似略图（approximate sketch）上的accuracy。这大约可以在proposal中转换成1/eps buckets。我们发现local proposals需要更少的buckets，因为它会重新定义划分候选（split candidates）

大多数分布式tree learning近似算法都遵循该框架。显著的，也可以直接构建近似的梯度统计直方图（approximate histograms of gradient statistics）。也可以使用二分策略（binning strategies）来替代分位数（quantile）。分位数策略(quantile strategy)可以从分布式（distributable）和重计算（recomputable）中受益，详见下一节。从图3中可知，我们发现：给定合理的近似级别（approximation level），分位数策略(quantile strategy)可以获得与exact greedy算法相同的准确率。

对于单机设置，我们的系统高效地支持exact greedy；对于单机和分布式设置，也同时支持带local和global proposal方法的近似算法。用户可以根据需要自由选择。

3.3 加权分位数略图(Weighted Quantile Sketch)

在近似算法中很重要的一步是，提出候选划分点。通常，一个特征的百分位数可以被用来让候选在数据上进行均匀地分布。我们用一个multi-set: $ D_k={(x_{1k}, h_1),(x_{2k},h_2),…(x_{nk},h_n)} $，来表示每个训练实例的第k个特征值以及它的二阶梯度统计。我们可以定义一个排序函数（rank functions）：$ r_k=R \rightarrow [0,+\infty) $：

\[r_{k}(z)=\frac{1}{\sum_{(x,h) \in D_k} h} \sum_{(x,k) \in D_k,x<z}^{} h\]

……(8)

它表示相应第k个特征上的输入值小于z的实例的占比。它的目标是，找好候选划分点 $ {s_{k1}, s_{k2}, …, s_{kl}} $，例如：

\[\|r_k(s_{k,j}) - r_k(s_{k,j+1})\| < \epsilon, s_{k1}=min_{i}^{} x_{ik}, s_{kl}=max_{i}^{} x_{ik}\]

……(9)

其中$ \epsilon $是近似因子（approximation factor）。直觉上，这意味着大约是 $ \frac{1}{\epsilon} $个候选点。这里，每个数据点通过$h_i$加权。为什么$h_i$可以表示权重呢？我们可以重写(3)式：

\[\sum_{i=1}^{n}\frac{1}{2}h_i(f_t(x_i)-g_i/h_i)^2 + \Omega(f_t) + constant\]

它就是真正的加权squared loss，labels为$g_i/h_i $，权重为$h_i$。对于大数据集来说，要找到满足该原则（criteria）的候选集是不容易的。当每个样本实例都具有相同的权重时，有一种已经存在的算法可以解决该问题：分位数略图（quantile sketch）。因而，大多数已存在的近似算法，或者会重新排序来对数据的一个随机子集进行排序（有一定的失败率），或者是启发式的（heuristics），没有理论保障。

为了解决该问题，XGBoost引入了一种新的分布式加权分位数略图算法（distributed weighted quantile sketch algorithm），使用一种可推导证明的有理论保证的方式，来处理加权数据。总的思想是，提出了一个数据结构，它支持merge和prune操作，每个操作证明是可维持在一个固定的准确度级别。算法的详细描述在这里。

3.4 稀疏感知的划分查找（sparsity-aware Split Finding）

在许多现实问题中，输入x是稀疏的。有多种可能的情况造成稀疏：

  • 1)数据中的missing values
  • 2)统计中常见的零条目
  • 3)特征工程：比如one-hot encoding

图4: 带缺省方向的树结构。当在split时相应的feature缺失时，一个样本可以被归类到缺省方向上

让算法意识到数据中的稀疏模式很重要。为了这么做，我们提出了在每个树节点上增加一个缺省的方向（default direction），如图4所示。当稀疏矩阵x中的值缺失时，样本实例被归类到缺省方向上。在每个分枝上，缺省方向有两种选择。最优的缺省方向可以从数据中学到。如算法3所示。关键的改进点是：只访问非缺失的条目$I_k$。上述算法会将未出现值（non-presence）当成是一个missing value，学到最好的方向来处理missing values。当未出现值对应于一个用户指定值时，应用相同的算法，可以通过将枚举(enumeration)限定到一致的解上。

[算法3]

据我们所知，大多数已存在的tree learning算法，或者只对dense data进行优化，或者需要指定函数来处理受限的情况：比如对类别编码（categorical encoding）。XGBoost以统一的方式处理稀疏模式。更重要的是，我们的方法充分使用稀疏性，它的计算复杂度与在输入中的未缺失条目(non-missing entries)的数目成线性关系。图5展示了在Allstate-10K数据集上稀疏感知和naive实现间的比较。我们发现，稀疏感知算法比naive版本要快50倍。这证实了稀疏感知算法的重要性。

图5: 稀疏感知算法（sparsity aware algorithm）在Allstate-10K上的影响。数据集很稀疏，主要因为one-hot编码。稀疏感知算法比naive版本（不会考虑稀疏性）要快50倍。

4.系统设计

4.1 用于并行学习的Column Block

tree learning最耗时的部分，是以有序方式获得数据。为了减少排序的开销，我们提出了将数据存储到内存单元（in-memory units）中，它们被称为“块（block）”。每个块中的数据，以压缩列（CSC）格式存储。每列由相应的特征值进行排序。输入数据的布局，在训练前只需要计算一次，在后续迭代中可复用。

在exact greedy algorithm中，我们将整个数据集存储到单个块中，通过对预排序的条目进行线性扫描的方式，来运行split search算法。我们会对所有叶子共同进行split finding算法，因而，在块上的一次扫描，将收集到在所有叶分枝上的划分候选的统计信息。图6展示了，我们如何将一个数据集转成该格式，并找到使用该块结构的最优划分（optimal split）。

图6: 用于并行学习的块结构。块中的每个列通过相应的特征值(feature value)进行排序。在块中的某列上进行一次线性扫描，足够枚举所有的划分点

当使用近似算法时，块结构也有用。这种情况下，可以使用多个块，每个块对应于数据集中行的子集。不同的块可以跨机器分布，或者以out-of-core设置的方式存储在磁盘中。使用排序过的结构，quantile finding步骤会在排好序的列上进行一次线性扫描（linear scan）。这对于局部建议算法（local proposal algorithms）特别有用，局部法的候选集通常在每次划分时生成。在直方图聚合(histogram aggregation)上进行二分查找，也变为一个线性时间的merge style算法。

为每列收集统计信息可以并行化，给定一个并行化算法来处理split finding。更重要的是，列块（column block）结构也支持列子抽样（column subsampling），它可以很容易地在一个块中选择列的一个子集。

时间复杂度分析

d为树的最大深度，K为树的总树目。对于exact greedy algorithm，原始的稀疏感知算法的时间复杂度：

\[O(K d |x|_{0}logn)\]

这里，我们使用 \(|x|_{0}\) 来表示在训练数据中未缺失条目（non-missing entries）的数目。另一方面，块结构上的tree boosting的开销为：

\[O(Kd {|x|} _0 + {|x|}_{0}logn)\]

这里， \(O( {\|x\|}_{0}log n)\) 是一次预处理开销(one time preprocessing cost)，可以分期(be amortized)。该分析展示了块结构可以帮助节省一个额外的$ log n $因子，其中当n非常大时就很大。对于近似算法，使用二分查找的原始算法时间复杂度为：

\[O(K d {|x|}_{0} log q)\]

这里的q是在数据集中建议候选的数目。其中，q通常为32~100之间，log因子仍会引入间接开销。使用块结构，我们可以将时间减小到：

\[O(K d{|x|}_{0} + {|x|}_{0} logB)\]

其中B是在每个块中的行的最大数。同样的，我们可以在计算中节约额外的log q因子。

4.2 内存感知访问（Cache-aware Access）

建议的块结构（the proposed block structure）可以帮助优化split finding的计算复杂度，新算法需要通过行索引（row index）间接取得梯度统计(gradient statistics)，因为这些值是以特征的顺序被访问的。这是非连续内存访问（non-continuous memory）操作。枚举划分（split enumeration）的naive实现，在累加(accumulation)与非连续内存读取操作(non-continuous memory fetch）间（详见图8），引入了立即读写依存（immediate read/write dependency）。当梯度统计（gradient statistics）不能装载进CPU cache里，或者cache miss发生时，会减慢split finding。

图8: 短范围内的数据依赖模式，由于cache miss，可引起停转（stall）

对于exact greedy algorithm，我们通过内存感知预取（cache-aware prefetching）算法来减缓该问题。特别的，我们在每个thread上分配一个internal buffer，获取gradient statistics存到该buffer中，接着以一种mini-batch的方式来执行累计（accumulation）。这种预取法将直接读/写依存，改变成一种更长的依存，当行的数目很大时可以帮助减少运行时开销。图7给出了在Higgs数据集和Allstate数据集上cache-aware vs. no cache-aware 的比较。当数据集很大时，我们发现exact greedy algorithm的cache-aware实现比naive版本的实现要快两倍。

图7: 在exact greedy algorithm中，cache-aware prefetching的影响。我们发现，cache-miss会在大数据集（1000w实例）上影响性能。使用cache-aware prefetching，可以提升数据集很大时的性能。

对于近似算法，我们通过选择一个合适的块大小（correct block size）来解决该问题。我们将块大小（block size）定义为在一个块中包含样本的最大数目，它会影响梯度统计的cache存储开销（cache storage cost）。选择一个过小的block size会导致每个thread会小负载（small workload）运行，并引起低效的并行化(inefficient parallelization)。在另一方面，过大的block size会导致cache miss，梯度统计将不能装载到CPU cache中。block size的好的选择会平衡两者。我们比较了在两个数据集上的block size的选择。结果如图9所示。结果展示选择在每个块上有$ 2^{16} $个样本时，会对cache property和parallelization做很好的平衡。

图9: 在近似算法中，block size的影响。我们发现，过小的块会引起并行化很低效，过大的块由于cache miss会让训练慢下来

4.3 Out-of-core计算

XGBoost的其中一个目标是，充分利用机器资源来达到可扩展的learning（scalable learning）。除了处理器和内存外，很重要的一点是，使用磁盘空间来处理不能完全装载进主存的数据。为了达到out-of-core计算，我们将数据划分成多个块，将每个块存到磁盘上。然而，这不能整体解决该问题，因为磁盘读（disk reading）会花费大多计算时间。减小开销和增加磁盘IO吞吐量很重要。我们主要使用两种技术来提升out-of-core计算。

块压缩（Block Compression） 块通过列(column)进行压缩，当加载进主存时可以由一个独立的线程即时解压(decompressed on the fly)。它会使用磁盘读开销来获得一些解压时的计算。我们使用一个通用目的的压缩算法来计算特征值。对于行索引（row index），我们从块的起始索引处开始抽取行索引，使用一个16bit的整数来存储每个偏移(offset)。这需要每个块有$ 2^{16} $个训练样本，这证明是一个好的设置。在我们测试的大多数数据集中，我们达到大约26% ~ 29%的压缩率。

块分片（Block Sharding） 第二个技术是，在多个磁盘上以一种可选的方式共享数据。一个pre-fetcher thread被分配到每个磁盘上，取到数据，并装载进一个in-memory buffer中。训练线程（training thread）接着从每个bufer中选择性读取数据。当提供多个磁盘时，这可以帮助增加磁盘读(disk reading)的吞吐量。

表1: 主要的tree boosting实现比较

参考

XGBoost: A Scalable Tree Boosting System

d0evi1 Reading time ~1 minute

microsoft在《Position-Normalized Click Prediction in Search Advertising》对coec做了介绍。

1.介绍

竞价排名搜索广告的ctr预估系统的目标是：根据其它上下文知识（比如：用户信息），对一个query-ad pair估计CTR。ctr预估对于ad排序、位置分配（allcation），定价（pricing），以及回报（payoff）很关键。通过估计得到的CTR作为query-ad相关度的一种衡量，并且与其它非相关因子相互独立。然而实际上，有许多外围因子影响着基于相关度的ctr系统，通常会在观察到的点击数据（click-through data）上扮演着重要角色。一个经典的示例是：广告展现位置（ad presentation position）。这些外在因子必须小心处理，否则会导致一个次优的ctr预估，许多真实世界的系统都会存在这种缺陷。

我们提出了一个概率因子模型（probabilistic factor model）作为一个总的原则性方法来研究这些效应。该模型很简单并且是线性的，在广告领域会做出经验性的调整。对于纠正在搜索算法上的位置偏差(positional bias)有大量研究，许多研究都是：检测模型（examination model）[12]，cascade model[5], 动态贝叶斯网络模型(DBN)[3]，而对于搜索广告领域却很少。我们的方法采用了与examination model相似的因子分解假设，也就是说：在item上的点击概率，是一个关于位置先验概率和一个基于相关度的与位置无关的概率的乘积。再者，我们会专门研究广告领域的位置概念，通过合并其它广告特有的重要信号，例如：query-ad keyword match type和广告总数。

来自搜索算法的其它模型(比如：cascade和DBN模型)，通常会假设：一个item的估计得到的ctr（estimated CTR）是与展示在搜索结果页的items的相关度(relevance)相互独立的。这些更复杂的假设对于搜索算法结果更合适，其中用户对于结果链接之一上的点击行为具有一个高概率。然而对于广告，在广告上的点击概率总是相当低，通常是一个百分比。因此，效果越高（非点击）的广告是相互接近的因子的乘积。

2.因子模型

假设：

  • i表示一个query-ad pair
  • j表示ad的位置
  • c表示点击次数
  • v表示曝光次数

观察到的CTR是一个条件概率 \(p(click \mid i,j)\)。对于在竞价搜索广告中的经验假设，我们做出如下简化：

  • 1.一个ad的点击是与它的位置相互独立的 (假设：位置可以物理上进行检查examining)。
  • 2.给定一个ad的位置，检查（examining）一个广告是与它的内容或相关度是相互独立的

正式的，位置依赖的CTR(position-dependent CTR)可以表示为：

\[p(click | i,j) = p(click | exam, i) p(exam | j)\]

…(1)

其中：

  • 第一个因子 \(p(click \mid exam, i)\)：可以简单表示为\(p_i\)，它是一个位置归一化的CTR（position-normalized CTR），可以表示ad的相关度
  • 第二个因子 \(p(exam \mid j)\)，可以简单表示为\(q_j\)，体现了位置偏差（ positional bias）。

有了该CTR因子分解（factorization），我们可以处理关于点击行为的两种自然随机模型，接着在部署模型上通过一个先验进行平滑。【1,9】

3. Binomial模型

很自然的，假设点击数遵循一个二项分布：

\(c_{ij} \sim Binomial(v_{ij}, p_i q_j), \forall i,j\) 。。。

4.POISSON模型

如果尝试次数n足够大，成功概率p (success probability)足够小，那么\(Binomial(n,p) \rightarrow Poisson(np)\)。由于广告(ad)就是这样一个领域，我们可以导出Poisson模型，它会生成一个相似的且足够有效的更新。该生成模型是：

\[c_{ij} \sim Poisson(v_{ij} p_i q_j), \forall i,j\]

…(9)

…

5.GAMMA-POISSON模型

对于empirical和regularization的目的，我们在Poisson模型中在位置因子(positional factor)上引入了一个gamma先验：

\[q_j \sim Gamma(\alpha, \beta), \forall j\]

…(16)

经验上，观察CTR(observed CTR)几何上会随位置的降低而递减【11】，展示出与gamma信号有一个很好的拟合。实例上，次一点的位置（inferior positions，比如：side bar的底部位置）可能会遭受严峻的数据稀疏性问题，尤其是点击；因此，正则化(regularizing)或平滑(smoothing)这些噪声估计会产生更好的泛化。gamma分布是一个常见的选择，因为它是Poisson的一个共轭先验。

。。。

6.点击模型

一个点击模型或CTR预测模型的目标是：为给定的一个query-ad pair，估计一个位置无偏CTR(positional-unbiased CTR)，例如：相关度CTR(relevance CTR) \(p(click \mid exam,i)\)或\(p_i\)。上述描述的位置归一化点击模型(positional normalized click model)会做这样的处理，同时也会发生位置先验概率 \(p(exam \mid j)\)或 \(q_j\)。factor模型的另一个观点是：在ad位置上做过平滑的kNN模型；当特征空间只包含了query-ad pairs，k=1。对于有足够历史点击数据的query-ad pairs这是可信的，因子模型可以合理执行。而对于一个冷启动问题原则性处理方法是，将queries和ads的一元特征（unigram features）添加到特征空间中，当在预测时遇到新的pairs时对CTR预估做backing-off。

位置归一化点击模型也可以被独立应用，并联合其它点击模型来估计relevance-only CTR。更严厉的，我们会所设位置因子与其它相关度因子相互独立。在模型训练时，需要通过它的位置先验\(v_{ij} q_j\)来归一化每个ad曝光。在预测时，CTR预测器会从位置归一化的训练数据中进行学习，并生成完全的relevance-only CTR。

7.实验

7.1 使用人造数据仿真

我们首先在一个通过概率模型（例如：给定一个sound模型）生成的人造数据集上仿造了Gamma-Poisson模型。通过仔细设计模型参数，人造数据可以十分模仿真实的搜索广告数据。尽管模仿数据不能完全反映真实系统，但它至少有两个优点：

  • 1.当从真实噪声中进行抽象时，允许快速研究大量参数
  • 2.通过该数据曝露的真实分布来验证学到的模型，对于真实数据很重要

数据生成如下：

    1. \(\foreach\) 位置 \(position j \in [1,...,m]\)，生成一个\(q_j \sim Gamma(\alpha,\beta)\)，以降序对q排序，通过\(1/q_1\)对q进行缩放
  • 2.

参考

d0evi1 Reading time ~1 minute

lightFM源自于paper: 《Metadata Embeddings for User and Item Cold-start》：

一、介绍

构建推荐系统能在冷启动场景中（新用户、新item）运行良好是个挑战。标准的MF模型在该setting中效果很差：很难有效估计user和item的隐因子，因为协同交互数据很稀疏。

基于内容的（CB）方法，可以通过使用item的metadata来解决该问题。因为这些信息是事先预知的，对于新item（没有协同数据可收集）的推荐依然可以计算。不幸的是，在CB模型中没有迁移学习出来：对于每个用户的建模是以孤立的方式估计得到的，并没有利用其它用户数据。因此，CB模型的执行会比MF模型要差。

最后，解决该问题很关键。我们是一家时尚公司，目标是为我们的用户提供便利的方法进行在线时尚品浏览、购买。为了这个目的，我们维护了一个非常大的商品目标：在写入时，我们会跨网络聚合超过800w的时尚items，并会每天添加上万新的商品。

为我们做出推荐有三个因子。首先，我们的系统包含了一个非常大的items数目。这使得我们的数据很稀疏。第二，我们如下进行处理：通常，最相关的items是那些新释放出的collections，允许我们只有一个短时间窗口来收集数据，并提供有效推荐。最后，我们的用户大比例是首次访问的用户（first-time visitors）：我们希望为他们推荐引人注目的推荐，即使只有少量数据。用户和item的冷启动组合，使得纯粹的协同和CB方法不适用。

为了解决该问题，我们使用一个混合content-collaborative模型，称为LightFM，归因于它会对FM进行resemblance。在LightFM中，就像在一个协同过滤模型中一样，users和items被表示成隐向量（embeddings）。然而，正如在一个CB模型一样，这些都通过描述每个商品或用户的内容特征(content features)的函数进行定义。例如，如果该电影“绿野仙踪（Wizard of Oz）”通过以下的features描述：”音乐幻想剧(musical fantasy)”、“朱迪·加兰（Judy Garland）”、以及“Wizard of Oz”，那么它的隐表示可以通过对这些features的隐表示进行求和得到。

通过这么做，LightFM可以将CB和CF的推荐的优点进行联合。在该paper中，我们会对该模型公式化，并在两个数据集上进行实验，展示：

  • 1.在冷启动和低密度场景，LightFM至少与纯CB模型一样好，实质上，当满足以下二者之一（1）在训练集中提供了协同信息 (2) 在模型中包含了用户特征 时，效果要更好。
  • 2.当协同数据很丰富时（warm-start, dense user-item matrix），LightFM至少与MF模型效果一样好。
  • 3.通过LightFM生成的Embeddings，可以编码关于features的重要语义信息，可以被用于相关推荐任务：比如：标签推荐。

这对于真实推荐系统来说有许多好处。因为LightFM在dense和sparse数据上均表现良好，它不需要为每种setting构建和维护多个特定机器学习模型。另外，它可以同时使用user和item的metadata，它可以应用于user和item的冷启动场景。

LightFM python版的Github地址为：https://github.com/lyst/lightfm.

2.LightFM

2.1 动机

LightFM模型的结构受以下两种考虑的启发：

  • 1.该模型必须能从交互数据中学习user和item表示：如果描述为“舞会袍（ball gown）”和”铅笔裙(pencil skirt)”的items均被用户所喜欢，该模型必须能学到ball gowns与pencil skirts相似。
  • 2.该模型必须能为新items和users计算推荐

第1点通过使用隐表示方法来解决。如果ball gowns和pencil skirts均被相同的用户所喜欢，它们的embeddings会更接近；如果ball gowns和机车夹克（biker jackets）不会被相同的用户所喜欢，它们的embeddings会更远。

这样的表示允许迁移学习出现。如果对于ball gowns和pencil skirts的表示很相近，我们可以自信地推荐ball gowns给一个刚与pencil skirts交互过的新用户。

在纯CB模型之上使用降维技术（比如：LSI）也可以达到该目换，因为它们只会编码由feature co-occurrence给定的信息，而非用户动作。例如，假设所有浏览过由“飞行员（aviators）”描述的items的用户，同时也浏览了由“旅行者(wayfarer)”描述的items，但这两个features从未在相同的item中同时描述过。这种情况下，对于wayfarers的LSI vector不会与aviators的相似，即使协同信息建议应该这样做。

第2点通过将items和users表示成它们的content features的线性组合。由于content features被认为是：当一个user或一个item进入该系统时，它允许直接做出推荐。这种结构很容易理解。“牛仔夹克（denim jacket）”的表示看成是denim的表示和jacket的表示的求和（sum）；一个来自美国的女性用户（a female user from the US）的表示是US的表示和female users的表示的求和。

2.2 模型

为了公式化描述该模型，假设U是用户集，I是items集合，\(F^U\)是user features的集合，\(F^i\)是item features的集合。每个用户与多个items交互，正向或者负向。所有user-item交叉pair \((u,i) \in U \times I\)是正交互\(S^+\)和负交互\(S^-\)的联合。

Users和items通过它们的features进行完全描述。每个user u通过一个特征集合描述 \(f_u \subset F^U\)。为每个item i它们的特征为\(f_i \subset F^I\)。features是提前知道的，可以表示user和item的metadata。

该模型通过d维的user和item的feature embeddings \(e_f^U\)和\(e_f^I\)为每个feature f进行参数化。每个feature也可以通过一个标量bias项(对于user features是\(b_f^U\)，对于item features则是\(b_f^I\))描述。

user u的隐表示，通过对它的features的隐向量进行求和来表示：

\[q_u = \sum_{j \in f_u} e_j^U\]

item i的隐表示类似，如下：

\[p_i = \sum_{j \in f_i} e_j^I\]

user u的bias项，通过对features的biases进行求和得到：

\[b_u = \sum_{j \in f_u} b_j^U\]

item i的bias项如下：

\[b_i = \sum_{j \in f_i} b_j^I\]

该模型对于user u 和 item i的预测，接着通过user向量和item向量的点乘，加上对应的偏置给出：

\[\hat{r_{ui}} = f(q_u \cdot p_i + b_u + b_i)\]

…(1)

有许多函数适合\(f(\cdot)\)。一个identity函数也能对预测评分很好地运行；在本paper中，我们只对二分类数据预测感兴趣，因而选择sigmoid：

\[f(x)= \frac{1} {1 + exp(-x)}\]

模型的最优化目标是，最大化在该参数上的条件似然。该似然如下：

\[L(e^U, e^I, b^U, b^I) = \prod_{(u,i)\in S^+} \hat{r_{ui}} \times \prod_{(u,i)\in S^-} (1-\hat{r_{ui}}\]

…(2)

使用ASGD进行训练。4线程。learning rate使用ADAGRAD。

2.3 与其它模型关系

LightFM与协同MF模型间的关系，由user和item的feature sets的结构决定。如果feature sets只包含了每个user和item的指示变量，LightFM相当于MF模型。如果feature sets也包含了metadata features，它们被至少一个item或user所共享，那么LightFM就扩展了MF模型：通过让feature的隐因子来解释用户交互的部分结构。

这在三方面很重要。

  • 1.在大多数应用中，metadata features要比users或items还要少，因为使用一个确定类型/类目的结构，或者因为维护一个固定size的关于最常用项的字典，当使用原始文本特征时。这意味着，从受限的训练数据中，需要估计更少的参数，减小overfitting机率并提升泛化效果。
  • 2.指示变量的隐向量不能为新的、冷启动users和items进行估计。将它们表示成metadata features的组合，可以从训练集中被估计，并做出冷启动预测。
  • 3.如果只有指定变量，LightFM与标准MF模型相当。

当只有metadata特征、没有指示变量时，模型通常不会缩减到一个纯CB模型。LightFM通过对协同交叉矩阵进行因子分解来估计feature embeddings；这不同于CB模型：它会对纯内容共现矩阵进行因子分解。

一个特别的case是，当每个用户通过一个指示变量描述时，并且只与一个item交互时，此时LightFM会变为CB。在该setting中，user vector等价于在LSI公式中的一个document vector，只有在product descriptions中共同出现过的features具有相似的embeddings。

事实上，LightFM一方面包含了在sparse data的纯CB模型，另一方面包含了在dense data上的MF模型。事实上，经验表明，至少与每种场景的单一模型一样好。

参考

Label Partitioning For Sublinear Ranking

d0evi1 Reading time ~7 minutes

1.介绍

我们有一个multi-class或者multi-label问题，其中每个训练样本\((x_i, T_i)\)包含了一个上下文\(x_i\)，以及一个关于target classes \(T_i\)的小集合（该集合在一个关于可能classes的大型空间L的范围之外）。例如，我们的问题可能是：给定前面的词汇，预测在句子中的下一个词。

1.1 F(x,y)

我们希望学习到一个兼容函数（compatibility function） \(F(x,y)\)，它会说明关于某个class y以及一个context x间的兼容性。例如——给定该上下文，该class的概率。

“穷举（Exhaustive）”训练法，比如：softmax和logistic regression需要我们为每个训练样本，对于每个类\(y \in L\)去计算F(x,y)。当\(\mid L \mid\)很大时，计算开销会很大。

1.2 \(T_i\)、\(C_i\)、\(S_i\)

  • target classes（正样本）: \(T_i\)
  • candidate classes（候选样本）: \(C_i\)
  • randomly chosen sample of classes（负样本）: \(S_i\)

“候选采样（Candidate Sampling）”训练法，涉及到构建这样一个训练任务：对于每个训练样本\((x_i, T_i)\)，我们只需要为候选类（candidate classes）\(C_i \subset L\)评估F(x,y)。通常，候选集合\(C_i\)是target classes和随机选中抽样的classes(非正例) \(S_i \subset L\)的合集(union)。

\[C_i = T_i \cup S_i\]

随机样本\(S_i\)可以依赖（或者不依赖）\(x_i\)和/或\(T_i\)。

训练算法会采用神经网络的形式训练，其中：用于表示F(x,y)的layer会通过BP算法从一个loss function中进行训练。

图1

  • \(Q(y \mid x)\): 被定义为：给定context x，根据抽样算法在sampled classes的集合中得到class y的概率（或：expected count）。
  • \(K(x)\)：是一个任意函数（arbitrary function），不依赖于候选类（candidate class）。由于softmax涉及到一个归一化（normalization），加上这种函数不会影响到计算概率。
  • logistic training loss为：
\[\sum\limits_i (\sum\limits_{y \in POS_i} log(1+exp(-G(x,y)) + \sum\limits_{y \in NEG_i} log(1+exp(G(x_i,y)) )\]
  • softmax training loss为：
\[\sum\limits_i (-G(x_i,t_i) + log (\sum\limits_{y \in POS_i \cap NEG_i} exp(G(x_i,y))))\]
  • NCE 和Negatvie Sampling可以泛化到\(T_i\)是一个multiset的情况。在这种情况中，\(P(y \mid x)\)表示在\(T_i\)中y的期望数（expected count）。相似的，NCE，Negative Sampling和Sampled Logistic可以泛化到\(S_i\)是一个multiset的情况。在这种情况下，\(Q(y \mid x)\)表示在\(S_i\)中y的期望数（expected count）。

Sampled Softmax

参考：http://arxiv.org/abs/1412.2007

假设我们有一个单标签问题（single-label）。每个训练样本\((x_i, \lbrace t_i \rbrace)\)包含了一个context以及一个target class。我们将\(P(y \mid x)\)作为：给定context x下，一个target class y的概率。

我们可以训练一个函数F(x,y)来生成softmax logits（比如：双塔模型的内积、dnn的logit等）——也就是说，该class在给定context上的相对log概率（relative log probabilities）：

\[F(x,y) \leftarrow log(P(y|x)) + K(x)\]

其中：K(x)是一个不依赖于y的任意函数(arbitrary function)。

在full softmax训练中，对于每个训练样本\((x_i,\lbrace t_i \rbrace)\)，我们会为所有class \(y \in L\)计算logits \(F(x_i,y)\)。如果L总数很大(class很多)，计算很会昂贵。

抽样函数：\(Q(y \mid x)\)

在”Sampled Softmax”中，对于每个训练样本\((x_i, \lbrace t_i \rbrace)\)，我们会根据一个选择抽样函数：

\[Q(y \mid x)\]

用它来选择一个“抽样后（sampled）” classes的小集合\(S_i \subset L\)。每个被包含在\(S_i\)中的class，它与概率\(Q(y \mid x_i)\)完全独立。

\[P(S_i = S|x_i) = \prod_{y \in S} Q(y|x_i) \prod_{y \in (L-S)} (1-Q(y|x_i))\]

我们创建一个候选集合\(C_i\)，它包含了关于target class和sampled classes的union：

\[C_i = S_i \cup \lbrace t_i \rbrace\]

我们的训练任务是为了指出：在给定集合\(C_i\)上，在\(C_i\)中哪个class是target class。

对于每个class \(y \in C_i\)，给定我们的先验\(x_i\)和\(C_i\)，我们希望计算target class y的后验概率。我们称它为\(P(t_i=y \mid x_i,C_i)\)。

注：Bayes’ rule：bayes

\[P(Z|X,Y) = P(Y,Z|X) P(X) / P(X,Y) = P(Y,Z|X) / P(Y|X)\]

…(b)

应用Bayes’ rule得到：

\[P(t_i=y|x_i,C_i) = P(t_i=y,C_i|x_i) / P(C_i|x_i) \\ =P(t_i=y|x_i) P(C_i|t_i=y,x_i) / P(C_i|x_i) \\ =P(y|x_i)P(C_i|t_i=y,x_i) / P(C_i|x_i)\]

接着，为了计算\(P(C_i \mid t_i=y,x_i)\)，我们注意到为了让它发生，\(S_i\)可以包含y或也可以不包含y，但必须包含\(C_i\)所有其它元素，并且必须不能包含不在\(C_i\)的任意classes。因此：

\[\begin{align} P(t_i=y|x_i, C_i) & = P(y|x_i) \prod_{y' \in C_i - \lbrace y \rbrace} Q({y'}|x_i) \prod_{y' \in (L-C_i)} (1-Q({y'}|x_i)) / P(C_i | x_i) \nonumber\\ & = \frac{P(y|x_i)}{Q(y|x_i)} \prod_{ {y'} \in C_i} Q({y'}|x_i) \prod_{ {y'} \in (L-C_i)} (1-Q({y'}|x_i))/P(C_i|x_i) \nonumber\\ & = \frac{P(y|x_i)}{Q(y|x_i)} / K(x_i,C_i) \end{align} \nonumber\\\]

其中：\(K(x_i,C_i)\)是一个与y无关的函数。因而：

\[log(P(t_i=y | x_i, C_i)) = log(P(y|x_i)) - log(Q(y|x_i)) + {K'} (x_i,C_i)\]

这些是relative logits，应feed给一个softmax classifier，来预测在\(C_i\)中的哪个candidates是正样本（true）。

因此，我们尝试训练函数F(x,y)来逼近\(log(P(y \mid x))\)，它会采用在我们的网络中的layer来表示F(x,y)，减去\(log(Q(y \mid x))\)，然后将结果传给一个softmax classifier来预测哪个candidate是true样本。

\[training \ softmax \ input = F(x,y) - log(Q(y|x))\]

我们对来自该classifer的梯度进行BP，可以训练任何我们想到的F。

补充：tensorflow实现

以tensorflow中的tf.random.log_uniform_candidate_sampler为例。

它会使用一个log-uniform(Zipfian)base分布。

该操作会随样从抽样分类(sampled_candidates)中抽取一个tensor，范围为[0, range_max)。

sampled_candidates的元素会使用base分布被无放回投样（如果：unique=True），否则会使用有放回抽样。

对于该操作，基础分布是log-uniform或Zipf分布的一个近似：

\[P(class) = \frac{(log(class+2) - log(class+1))} { log(range\_max + 1)}\]

当target classes近似遵循这样的一个分布时，该sampler很有用——例如，如果该classes以一个字母序表示的词语，并以频率降序排列。如果你的classes没有通过词频降序排列，就不需要使用该op。

另外，该操作会返回tensors: true_expected_count，

sampled_softmax_loss

def _compute_sampled_logits(weights,
                            biases,
                            labels,
                            inputs,
                            num_sampled,
                            num_classes,
                            num_true=1,
                            sampled_values=None,
                            subtract_log_q=True,
                            remove_accidental_hits=False,
                            partition_strategy="mod",
                            name=None,
                            seed=None):
    # 核心代码实现：
    if isinstance(weights, variables.PartitionedVariable):
        weights = list(weights)
    if not isinstance(weights, list):
        weights = [weights]

    # labels_flat:  batch_size.
    with ops.name_scope(name, "compute_sampled_logits",
                        weights + [biases, inputs, labels]):
        if labels.dtype != dtypes.int64:
            labels = math_ops.cast(labels, dtypes.int64)

        labels_flat = array_ops.reshape(labels, [-1])

    # 抽取num_sampled个样本.
    if sampled_values is None:
        sampled_values = candidate_sampling_ops.log_uniform_candidate_sampler(
            true_classes=labels,
            num_true=num_true,
            num_sampled=num_sampled,
            unique=True,
            range_max=num_classes,
            seed=seed)

    # 这三个值不会进行反向传播
    sampled, true_expected_count, sampled_expected_count = (array_ops.stop_gradient(s) for s in sampled_values)

    # 转成int64
    sampled = math_ops.cast(sampled, dtypes.int64)

    # label + sampled (labels基础上拼接上抽样出的labels)
    all_ids = array_ops.concat([labels_flat, sampled], 0)

    # 合并在一起，使用all_ids一起进行查询
    all_w = embedding_ops.embedding_lookup(
        weights, all_ids, partition_strategy=partition_strategy)

    # 分割出label的weight.
    true_w = array_ops.slice(all_w, [0, 0],
                             array_ops.stack(
                                 [array_ops.shape(labels_flat)[0], -1]))

    # 分割出sampled weight.
    sampled_w = array_ops.slice(
        all_w, array_ops.stack([array_ops.shape(labels_flat)[0], 0]), [-1, -1])

    # user_vec * item_vec
    sampled_logits = math_ops.matmul(inputs, sampled_w, transpose_b=True)

    # bias一起查询.
    all_b = embedding_ops.embedding_lookup(
        biases, all_ids, partition_strategy=partition_strategy)

    # true_b is a [batch_size * num_true] tensor
    # sampled_b is a [num_sampled] float tensor
    true_b = array_ops.slice(all_b, [0], array_ops.shape(labels_flat))
    sampled_b = array_ops.slice(all_b, array_ops.shape(labels_flat), [-1])

    # element-wise product.
    dim = array_ops.shape(true_w)[1:2]
    new_true_w_shape = array_ops.concat([[-1, num_true], dim], 0)
    row_wise_dots = math_ops.multiply(
        array_ops.expand_dims(inputs, 1),
        array_ops.reshape(true_w, new_true_w_shape))

    # true label对应的logits, bias.
    dots_as_matrix = array_ops.reshape(row_wise_dots,
                                       array_ops.concat([[-1], dim], 0))
    true_logits = array_ops.reshape(_sum_rows(dots_as_matrix), [-1, num_true])
    true_b = array_ops.reshape(true_b, [-1, num_true])


    true_logits += true_b
    sampled_logits += sampled_b

    # 减去先验概率.
    if subtract_log_q:
      # Subtract log of Q(l), prior probability that l appears in sampled.
      true_logits -= math_ops.log(true_expected_count)
      sampled_logits -= math_ops.log(sampled_expected_count)

    # 输出logits，拼接在一起.
    out_logits = array_ops.concat([true_logits, sampled_logits], 1)

    # 输出的labels.
    out_labels = array_ops.concat([
        array_ops.ones_like(true_logits) / num_true,
        array_ops.zeros_like(sampled_logits)
    ], 1)

    return out_logits, out_labels

得到logits和labels后，就可以计算softmax_cross_entropy_with_logits_v2了。

log_uniform_candidate_sampler

1
2
3
4
5
6
7
8
9

tf.random.log_uniform_candidate_sampler(
true_classes,
num_true,
num_sampled,
unique,
range_max,
seed=None,
name=None
)

使用一个log-uniform(Zipfian)的基础分布来采样classes集合。

该操作会对一个sampled classes（sampled_candidates） tensor从范围[0, range_max)进行随机抽样。

sampled_candidates的elements会从基础分布进行无放回抽样（如果unique=True）或者有放回抽样（unique=False）。

对于该操作的base distribution是一个近似的log-uniform or Zipfian分布：

\[P(class) = (log(class + 2) - log(class + 1)) / log(range\_max + 1)\]

当target classes近似遵循这样的一个分布时，该sampler很有用——例如，如果该classes表示字典中的词以词频降序排列时。如果你的classes不以词频降序排列，无需使用该op。

另外，该操作会返回true_expected_count和sampled_expected_count的tensors，它们分别对应于表示每个target classes(true_classes)以及sampled classes（sampled_candidates）在sampled classes的一个平均tensor中期望出现的次数。这些值对应于在上面的\(Q(y \mid x)\)。如果unique=True，那么它是一个post-rejection概率，我们会近似计算它。

即：

1
2
3
4
5

对一个labels tensor进行candidate sampling抽样，抽取num_sampled个负样本。
返回：
    相应的负样本label: sampled_candidates     => 个数与num_sampled相同
    相应的正样本的概率：true_expected_count    => 个数与labels相同
    相应的负样本的概率：sampled_expected_count => 个数与num_sampled相同

paper2

另外在paper 2《On Using Very Large Target Vocabulary for Neural Machine Translation》的第3节部分，也做了相应的讲解。

paper2 第3节

在该paper中，提出了一种model-specific的方法来训练具有一个非常大的目标词汇表（target vocabulary）的一个神经网络机器翻译（NMT）模型。使用这种方法，训练的计算复杂度会是target vocabulary的size的常数倍。另外，该方法允许我们高效地使用一个具有有限内存的快速计算设备(比如：一个GPU)，来训练一个具有更大词汇表的NMT模型。

训练一个NMT的计算低效性，是由等式(6)的归一化常数引起的。为了避免计算该归一化常数的成长复杂度(growing complexity)，我们这里提出：在每次更新时使用target vocab的一个小子集\(V'\)。提出的方法基于早前Bengio 2008的工作。

等式(6), next target word的概率：

\[p(y_t | y_{<t},x) = \frac{1}{Z} exp \lbrace w_t^T \phi(y_{t-1}, z_t, c_t) + b_t \rbrace\]

…(6)

其中Z是归一化常数（normalization constant）：

\[Z = \sum\limits_{k:y_k \in V} exp \lbrace w_k^T \phi (y_{t-1}, z_t, c_t) + b_k \rbrace\]

…(7)

假设我们考虑在等式(6)中output的log-probability。梯度的计算由一个正部分(positive part)和负部分(negative part)组成：

\[\nabla log p(y_t \mid y_{<t}, x) = \nabla \epsilon(y_t) - \sum\limits_{k:y_k \in V} p(y_k | y_{<t}, x) \nabla \epsilon(y_k)\]

…(8)

其中，我们将energy \(\epsilon\)定义为：

\[\epsilon(y_i) = w_j^T \phi(y_{i-1}, z_j, c_j) + b_j\]

梯度的第二项（negative）本质上是energy的期望梯度：

\[E_p[\nabla \epsilon(y)]\]

…(9)

其中P表示\(p(y \mid y_{<t}, x)\)。

提出的方法主要思想是，通过使用少量samples进行importance sampling来逼近该期望，或者该梯度的负项。给定一个预定义的分布Q和从Q中抽取的一个\(V'\)样本集合，我们使用下式来逼近等式(9)中的期望：

\[E_P [\nabla \epsilon(y)] \approx \frac{w_k}{\sum_{k':y_{k'} \in V'} w_{k'}} \nabla \epsilon(y_k)\]

…(10)

其中：

\[w_k = exp \lbrace \epsilon(y_k) - log Q(y_k) \rbrace\]

…(11)

该方法允许我们在训练期间，使用target vocabulary的一个小子集来计算归一化常数，每次参数更新时复杂度更低。直觉上，在每次参数更新时，我们只会更新与correct word \(w_t\)以及在\(V'\)中的sampled words相关的vectors。一旦训练完成，我们可以使用full target vocabulary来计算每个target word的output probability。

尽管提出的方法可以天然地解决计算复杂度，使用该方法本质上不能在每个句子对(sentance pair：它们包含了多个target words)更新时保证参数数目。

实际上，我们会对training corpus进行分区(partition)，并在训练之前为每个分区（partition）定义一个target vocabulary子集\(V'\)。在训练开始之前，我们会顺序检查训练语料中的每个target sentence，并累积唯一的target word，直到唯一的target words达到了预定义的阀值\(\tau\)。然后在训练期间将累积的vocabulary用于corpus的partition。我们会重复该过程，直到达到训练集的结尾。假设对于第i个partition的target words的子集用\(V_i'\)表示。

这可以理解成，对于训练语料的每个partition具有一个单独的分布\(Q_i\)。该分布\(Q_i\)会为在子集\(V_i'\)中包含的所有target words分配相等的概率质量(probability mass)，其它words则具有为0的概率质量，例如：

\[Q_i(y_i) = \begin{cases} \frac{1}{|V_i'|} & \text{if $y_t \in V_i'$} \\ 0 & otherwise. \end{cases}\]

提议分布(proposal distribution)的选择会抵消掉correction term——来自等式(10)-(11)中importance weight的\(log Q(y_k)\)，使得该方法等价于，使用下式来逼近等式(6)中的准确output probability：

\[p(y_t | y_{<t}, x) = \frac{exp \lbrace w_t^T \phi(y_{t-1}, z_t, c_t) + b_t) \rbrace}{ \sum_{k:y_k \in V'} exp \lbrace w_k^T \phi(y_{t-1}, z_t, c_t) + b_k \rbrace}\]

需要注意的是，Q的这种选择会使得estimator有偏。

对比常用的importance sampling，提出的该方法可以用来加速，它会利用上现代计算机的优势来完成matrix-matrix vs. matrix-vector乘法。

参考

d0evi1 Reading time ~1 minute

Microsoft在《Trustworthy Online Controlled Experiments: Five Puzzling Outcomes Explained 》中对A/B testing中存在的5个谜题做了解释。

3.1 搜索引擎的OEC

3.1.1 背景

选择一个好的OEC对于整个商业经营很重要。这些指标驱动着go/no-go的决策。在之前工作中，我们强调了长期关注的必要，并建议将lifetime value作为一个指导原则。像日活用户（DAU）这样的指标被一些公司所使用。在《7 pitfalls to Avoid when Running controlled Experiements on the web》中，首个陷阱是：

从商业角度上看，应选择这样一个OEC：它可以通过做一些很明显“错误（wrong）“的事情就很轻易地击败control组实验

当我们尝试为Bing获得一个OEC时，我们会首先关注商业目标。当前有两个顶级的长期目标：查询分享（query share）以及每次搜索的回报（revenue per search）。确实，许多项目被激励来提升它们，但有一个很好的示例：短期目标和长期目标完全背离。

3.1.2 Puzzling Outcome

当Bing在实验中有个bug，导致了展示给用户非常差的结果，但两个关键的公司级指标提升显著：每个用户的不同查询数（distinct queries per user）涨了10%，每用户回报（revenue per user）提升了30%! Bing应该如何评估该实验？什么是OEC？

很明显，实验中的长期目标与短期指标是不能对齐的。如果它们可以对齐，我们可以降低质量来提升query share和revenue!

3.1.3 解释

从搜索引擎的角度，退化的算法结果（展示给用户的主搜索引擎结果，有时也被称为10个蓝链接(10 blue links)）会强制用户发起更多的查询（这会增加每个用户的queries）以及点击更多的广告（增加回报）。然而，这很明显是短期提升，这与零售商店里提升价格相似：你可以增加短期回报，但客户更偏向于与时间竞赛，因此平均顾客的生命周期价值（lifetime value）将会缩短。

为了理解该问题，我们分解了query share。我们将月查询分享数(monthly query share)定义为：Bing上不同查询数 / 一整个月所有搜索引擎的不同查询数，正如comScore所测量的（distinct意味着：同一用户在半小时内在相同的垂直搜索引擎（比如：网页or图片）上连续重复的queries，被统计成1）。由于在Bing上，我们可以很轻易地测量分子（我们的distinct queries，而非整个makret），该目标是为了增加该component。每个月的distinct queries可以被分解成三个项相乘：

\[\frac{Users}{Month} \times \frac{Sessions}{User} \times {Distinct \ queries}{Session}\]

…(1)

其中，在乘积中的第2项和第3项会在月周期上计算，session被定义为：用户开始发起一个query、30分钟后在搜索引擎上没有活动就结束。

如果一个搜索引擎的目标是，允许用户快速发现它们的答案、或者完成它们的任务，那么减小每个任务的distinct queries是一个明确的目标，它会与关于增加收入的商业目标相冲突。因为该指标与每个sesion不同查询数(distinct queries per session)高度相关（），我们推荐：distinct queries不能单独用来作为搜索实验的OEC。

给定如等式(1)所示的不同查询的分解，我们来看下这三个项：

  • 1.User per month。在一个controlled experiment中，独立用户数由设计决定。例如，在一个相等的A/B test中，用户数会以近似相同的数目分到两个variants中。（如果在variants中用户的比例很不同，这很可能是个bug）。出于该原因，该项不能成为该实验OEC的一部分。
  • 2.每任务查询数（distinct queries per task）应该最小化，但它很难测量。每session不同查询数（distinct queries per session）是一个可用的代理指标(surrogate metric)。这是一个精细指标（subtle metric），然而，由于增加它可能意味着用户需要发起理多查询来完成该任务，但减少它可能表示放弃查询。该指标需要最小化，意味着该任务会被成功完成
  • 3.Sessions/user 是在实验中要优化(增加)的关键指标，因为满意的用户会来得更多。这是一个在Bing中OEC的关键成分（key component）。如果我们有好的方式来标识tasks，等式(1)中的分解可以通过task来进行，我们可以优化tasks/user。

在搜索引擎结果页上展示的退化算法结果，会给用户一个明显更差的搜索体验，但会造成用户点击更多广告（它的相对相关度会增加），从而增加短期回报。在没有其它约束下，每用户回报(Pevenue per user)同样不能被用来当成搜索和广告实验的一个OEC。当关注回报指标时，我们希望：在不会对用户满意度指标（比如：sessions/user）造成负面影响的情况下增加它们。

3.1.4 学到的

query量的分解，搜索的长期目标，展示了冲突的组成(components)：一些会增加短期指标（sessions/user），另一些会减小短期指标（queries/session）表示任务成功完成。我们的假设是，更好的用户体验会增加users/month，最后一项不能在一个control实验中进行测量。

该分析不仅影响搜索实验，也会影响SEM等（search engine marketing）。当决定广告的bid量时，很自然的会尝试和优化在session中的queries数，它会伴随广告点击。然而，长的sessions表示用户找不到满意的东西（例如：驱动用户下拉更多结果页）

顾客生命周期值（Lifetime customer value）通常应是决定OEC的指导准则。对于controlled experiments，特定的短期指标的选择需要很好地理解商业，同时理解以下这点很重要：长期目标不能总是与短期指标相对齐。

3.2 点击跟踪

3.2.1 背景

跟踪用户的在线点击和表单提交（比如：搜索(searches）)对于web分析、controlled experiments、以及商业智能很重要。大多数网站使用web beacons（1x1 pixel图片请求）来跟踪用户动作，但等待beacon在点击和提交上的返回会减慢下一动作（例如：展示搜索结果、或者目标页）。一种可能性是，使用一个较短超时(short timeout)，共识是：跟踪机制（停留在用户动作）的用时越多，数据损失越低。从Amazon、Google、Microsoft的研究表明，数百毫秒的小延迟，对于回报和用户体验会有剧烈的副作用，我们发现许多网站允许较长延时以便更可靠的收集点击数据。例如，到2010年3月，多个microsoft网站等待click beacons返回一个2s的timeout，这会在用户点击上引入一个大约400ms的平均延迟。关于该主题的一个白皮书最新已经发布[23]。据我们所知，该issue并没有被大多数网站owners所理解，它们的实现具有很大的click losses。对于广告，点击与支付相绑定，重定向通常被用于避免click loss。然而，对于用户这会引入一个额外的delay，对于tracking clicks来说并不常用。

3.2.2 Puzzling Outcome

仅仅添加一小段代码，比如：当用户点击一个搜索结果时，执行额外的JavaScript。需要在那个点被执行该段Javascript代码的原因是，在浏览器被允许处理和打开目标站点之前，目标站点的session-cookie被更新。

这会轻微地减慢用户体验，但实验表明用户会点击更多！为什么呢？

3.2.3 解释

用户点击更多的“成功”并不是真实的，准确来说是一个仪表误差（instrumentation difference）。chrome、firfox、safari对于结束从当前页导航走的请求更激进些，关于click beacons的一个不可忽视的比例并不会向server做出[23]。。。

3.初始效应(Initial Effect)

3.3.1 背景

给定，介绍中提到的评估A/Btesting具有很高的失败率，这非常常见，对于在实验的头几天，可以看到新版本是winner或者可以过早结束。 在该内容中会提到当新特性被引入时的两个效应：始效应（Primacy effects）和Novelty effects。这些都是负面效应，有时会影响实验。 当你在网站上变更了导航（navigation）时会出现Primacy effect，体验的用户可能会变得更低效，直到它们习惯了新导航，因而对于Control组有着天然的优势。相反的，当一个新设计或新特性被引入时，一些用户会研究该新特性，到处进行点击，从而引入一个“Novelty” bias，这会快速消逝，因为该特性并不是真的有用。该bias有时与”霍索恩效应(Hawthorne Effect)”有关，例如：一个短暂的提升。上述提到的实验，其中在MSN主页上的hotmail链接被变更成以独立tab/window方式打开hotmail，会有一个很强的Novelty effect：用户可能很吃惊，并尝试它多次。而Novelty effects会在一个较短时间后消逝，并产生一个更小的效应，长期影响(long-term impact)仍会是正向、无效、或负向的。在这个case中，long-term effect是正向的，该特性会驻留在MSN主页上。Primacy effects和Novelty effects可以通过生成在时间上的delta graph（在Control和Treatment间），以可视化或可分析地方式来进行评价，并评估趋势。如果我们怀疑这样的趋势，我们可以拓展该实验。为了评估正向效果（true effect）,可以做一个分析，其中只对在不同variants实验上的新用户计算OEC，因为他们没有受Primacy和Novelty effect的影响。另一个观点是，排除第一周的实验，因为delta通常会在一周之后变得稳定。我们的结果：大多数情况下疑似的Primacy和Novelty effects并不是真实的，只是统计的加工品（statistical artifact）。

3.3.2 Puzzling outcome

在许多实验中，前几天的效果看起来会趋高或者趋低。例如：图3展示了一个真实实验在关键指标上前4天的效果，其中在图中的每个点展示了直到那一天的累积效应（cumulative effect: delta），通过feature owner跟踪得到。

图3

该效果表明：在前4天有一个很强的正趋势。实验者（它希望得到一个正向结果）看到了该intial negtive delta，但使用点虚线来线性推断该趋势，并认为在接下来的几天，该效果将以跨过0%并在第6天开始变成正向。这种思维很常见：我的新特性是明显很棒的，但对用户来说需要花费时间来习惯它，例如：在头几天时我们会看到Primacy effect。用户必须开始越来越喜欢该特性，这对吗？当然是错的！许多情况下，这是可预期的。

3.3.3 解释

对于许多指标来说，均值的标准差与\(1/\sqrt{n}\)成正比，其中n是用户数。出于简洁性，假设没有重复用户。例如，每个用户在实验期间只访问一次（结果不会变化很多，但使用实际会发生的次线性增长时）。因此，n与天数成正比。如图4所示，当实际效应(actual effect)为0时，对于测量效应（measured effet）的95%置信图。

图4

前几天是高度可变的，因此在初始几天的效应(effect)可能会或高或低于在两或三周后的效应(effect)。例如，头一天具有67%的可能性在95%置信区间之外在实验尾部下降；第二天具有55%的可能性在该区间外。由于该序列(series)是自相关的(auto-correlated)，存在两个含义：

  • 1.相对于之前实验发布的最终结果（它们会运行更长的时间），在初始几天的effects通常看起来过度正向或者负向。
  • 2.在前几天期间，累积结果看起来会延伸。例如，假设一个实验在兴趣指标上没有effect。头一天可能是负向的-0.6%，但随着更多数据被累计，该效应(effect)会回归到0均值、95%置信锥的true。feature owners不正确地假设该effect是会延伸的，那将很快会跨过0线。当然，这很少会发生。

图3的graph实际上来自于一个A/A test（control和treatment间没有区别），effect的均值为0. 第一天具有一个负差值(negative delta)（注意：该宽置信区间会与0交叉），随着时间向前，该置信区间会收缩，结果会回归到该均值。确实，如图5所示，该graph会随时间在0附近稳定。

图5

3.3.4 学到的东西

出现”趋势（trends）”是可预期的，因为我们将它看成是一种educational和awareness issue，尽管我们承认后见之明(hindsight)是20/20,我们也会被初始趋势迷惑多次。当你开始涉及实现一个idea、并希望它成功时，确认偏误（confirmation bias）是很强的。当你构建一个假设并希望它趋向正确方向时，初始的负向结果通常进行抑制。

我们运行的实验很少有Primacy effects与intial effects相反的(reverse)，例如：某一特性初始是负向的，直到用户学会它并对它习惯，它才会是正向。由于存在这些效应(effects)，我们不能发现：单个实验在某一方向上具有统计显著的结果，在另一方向上也会统计显著（例如：一个统计显著的负向，变成统计显著的正向）。

大多数实验具有一个稳定效应（常数均值），但高方差意味着需要收集足够数据来得到更好估计；早期结果通常会有误导。由于存在真实的Novelty effects或Primacy effects，对于一个统计显著负效应，最常见的方式是，随时间变得更负向；而对于一个统计显著的正效应，随时间变得更正向。对于在几周之后扩展（extend）那些统计显著负向的实验，是没有多大价值的。

3.4 实验长度（Experiment Length）和统计强度(Statistical Power)

3.4.1 背景

不同于大多数离线实验，在线实验(online experiments)会持续补充（recruit）用户，而非在实验之前具有一个补充期（recruitment period）。因此，sample size随着实验的运行越长会增加。因此，很自然地期望：运行一个实验越长，会提供关于treatment effect的一个更好的估计，也具有更高的statistical power。注意，对于一些指标，比如：Sessions/User，该均值会随实验运行的越久而增加，也会基于百分比变化计算power。

3.4.2 Puzzling Outcome

图6

图7

3.5 延滞效应（carryover effects）

3.5.1 背景

一些在线实验平台，包括：Bing、Google、Yahoo，依赖于“bucket system”来安排用户进行实验[3]。该bucket system会将用户随机化到不同的buckets中，接着安排buckets进行实验。这是个灵活的系统，允许对后验实验上对用户简单复用。

3.5.2 Puzzling Outcome

一个实验运行后，结果非常惊人。它通常是良好的，因为违反直觉的结果帮助我们理解新的ideas，但指标与在非预期方向的变化移动不相关，该效应(effect)是高度统计显著的。我们以一个更大的sample重新运行该实验来增加statistical power，许多该effect会消失。

3.5.3 解释

“bucket system”的一个大缺陷是，它具有carryover effects的缺点，受前一实验影响的相同用户，被用于接下来的实验中。这是已知的，可以运行A/A tests确认carryover effects，但当他们失败时，我们会失去能力直到我们对bucket assignment进行re-randomize。令人吃惊的是，craayover effect的持续时间（duration）。我们分享以下的两个示例。

图8

在首个示例中，我们在三个阶段（stages）上运行了该实验，其中，我们在47天的A/B实验之前，在user buckets上有一个7-day的A/A实验。在我们完成实验后，我们关掉实验，接着在接下来的三周上继续监控相同的user buckets。图8展示了在treatment和control之间，OEC（Sessions/User）上的日常百分误差(daily percent delta)。灰色bars表示三个stages的划分。

很明显在实验完成之后，在用户上有一个carryover effect。该carryover effect看起来会在实验之后的三周左右消失。

图9

在另一个示例中，如图9所示，用户在实验中曝出的一个bug，会引起较差用户体验。carryover effect会持续更长时间。即使在三个月之后，user buckets仍然没有恢复到之前实验的水平。

3.5.4 缓解技术

尽管carryover effect本身对于实验者很重要，但对于一个实验平台来说保证质量更重要，而非抵制它。在bucket system中，由于user buckets会会从一个实验进行回收利用到另一个实验上，任意carryover impact可以很容易对后续实验造成bias。

缓解该问题的一种方式是，局部随机化（local randomization）。造成carryover effect的一个根源是：bucket system没有对每个实验进行重新随机化（re-randomize）。整个bucket system会依赖于一个频次不高的bucket re-assignment来对polulation进行随机化，接着该bucket分配在相当长周期内仍不变(constant)。将用户重新随机化到bucket system可以通过变更hashing function来完成，但该bucket system会以一个“bucket line”或者“layer”[3]的方式将所有实验进行成对化（couple），这样，我们必须停止在该bucket line上所有运行的实验，并变更hashing function，这会伤害（capacity）和敏捷性（agility）。另一个可选方案是，使用一个two-level的bucket system，它可以提供局部随机化；也就是说，只在一个buckets子集上进行重新随机化（re-randomizing），但不需要影响其它buckets。

图10

上图展示了，局部重随机化是如何通过一个two-level bucket system来完成的。顶层的bucket system定义了包含在实验中的experiement units的一个集合，tratment assignment则在第二层bucket system中进行。对于每个experiment，第二层hashing会使用一个不同的hash seed。这保证了每一实验随机（per-experiment randomization），从而treatment的分配独立于任何历史事件，包括之前实验的carryover effects。上述方案的一个缺点是，我们不能使用一个共享的Control组：每个实验都需要它自己的Control，以便来自某一实验的任意carryover被“混合”到Control和Treatment(s)中。

局部随机化的一个好处是，我们可以运行一个“回顾式(retrospective)”的A/A 实验，无需实际占据总有效时间(calendar time)。通过对hashing function进行变更，在重启A/B实验之前，我们可以在前几天运行A/A实验进行评估。由于局部重新随机化的独立性，如果我们在实验之前对于任意周期回顾式地比较被分配到control和treatment组上的用户，该比较会是一个A/A。如果该A/A表明对于核心指标有影响，比如：p value < 0.2(由于划分的”unlucky”）, 我们需要重新变更hashing key并进行重试。

参考：