1.介绍

Fackbook提出的gbdt+LR来预测广告点击，本文简单重温下相应的paper。

在付费搜索广告领域(sponsored search advertising)，用户query被用于检索候选广告（candidate ads），这些广告可以显式或隐式与query相匹配。在Facebook上，广告不与query相关联，但可以通过人口统计学(demographic)和兴趣（interest）来定向(targeting)。因而，当一个用户访问Facebook时，适合展示的广告容量（the volume of ads），比付费搜索中的要大。

为了应付每个请求上非常大量的候选广告，当用户访问Facobook时触发广告请求，我们会首先构建一连串的分类器，它们会增加计算开销。在本文中主要放在点击预测模型上，它会对最终的候选广告产生预测。

2.实验Setup

为了达到严谨受控的实验，我们会取2013年第4季度某一个周的数据作为离线训练数据。为了在不同条件下维护相同的训练／测试数据，我们准备了离线训练数据，它与线上观测到的数据相似。我们将这些保存下来的离线数据划分成：训练数据和测试数据，并使用它们来模拟在线训练和预测的streaming数据。

评估的metrics: 由于我们最关心的是机器学习模型的影响因子，我们使用prediction的accuracy作为metrics，而非利润和回报。在本文中，我们使用归一化熵（NE: Normalized Entropy）以及calibration作为主要的评测指标。

Nonmalized Entropy，或者更准确地被称为NCE：归一化的Cross-Entropy，等价于：【每次曝光（impression）的平均log loss】除以【如果一个模型为每个曝光预测了相应后台CTR(background CTR)，每个曝光的平均log loss】。换句话说，它是预测log loss，通过s通过background CTR进行归一化。background CTR是训练数据集的平均期望CTR(average empirical CTR)。它可能更多描述是指关于归一化log loss（Normalized Logarithmic Loss）。值越低，通过该模型预测的效果越好。使用该归一化的原因是，background CTR越接近0或1,也容易达到一个更好的log loss。除以background CTR的熵，使得NE对于background CTR不敏感。假设一个给定的数据集，具有N个样本，对应的labels为: $ yi \in {-1,+1} $，点击概率\(p_i\)，其中i=1,2,…,N。平均期望CTR为p：

……（1)

NE是用于计算相关的信息增益(RIG: Relative Information Gain)的一个必需单元. RIG=1-NE

Calibration(校准)是一个关于【平均估计CTR】和【期望CTR】的ratio。该比值相当于：【期望点击数】与【实际观察点击数】。Calibration是一个非常重要的指标，因为关于CTR的accurate、well-calibrated的预测，对于在线竞价和拍卖的成功很重要。Calibration与1的差异越小，模型越好。我们只会报告：在实验中的calibration，它是non-trivial的。

注意，对于评估ranking的质量，AUC也是一个相当好的指标，无需考虑Calibration。真实环境下，我们希望预测够准确，而非仅仅获取最优的rank顺序，以避免欠拟合（under-delivery）或过拟合（overdelivery）。NE可以measure预测的好坏，并隐式地影响calibration。例如，如果一个模型过度预测了2倍，我们可以使用一个全局的乘子0.5来修正calibration，对应的NE也会提升，尽管AUC仍相同。详见paper[12]

3.预测模型结构

本部分我们提出了一种混合模型结构：将GBDT与一个概率稀疏的线性分类器相串联，如图1所示。在3.1中，决策树对于输入特征的转换十分强大，可以极大增加概率线性分类器的accuracy。在3.2中，会展示训练数据的新鲜度是如何影响更准确的预测。这激发了我们使用一个在线学习方法来训练线性分类器。在3.3中，我们比较一些在线学习变种。

图1: 混合模型结构。输入特征通过boosted决策树的方式进行转换，每棵树的输出作为一个类别型输入特征，输入到一个稀疏的线性分类器上。Boosted决策树提供了非常强的特征转换.

我们评估的在线学习模式，是基于SGD算法的，应用于稀疏线性分类器。在特征转换后，给定一个ad的曝光，具有一个vector形式：$ x=(e_{i1},…,e_{in}) $，其中ei表示第i个unit vector，$i_1,…,i_n$是n种类别输入特征的值。在训练阶段，我们假设，给定一个二元标签 $y \in {-1,+1}$，用于表示点击or未点击。

给定一个加上label的广告曝光：(x,y)，我们将激活权重的线性组合表示成：

……(2)

其中w是线性点击分值的weight vector。

对于概率回归(BOPR)，目前最state-of-art的Bayesian在线学习scheme在[7]中有描述，似然和先验如下：

3.1 决策树特征转换

为了提升accuracy，有两种简单的方法，来对线性分类器的输入特征进行转换。对于连续型特征，用于学习非线性变换的一个简单的trick是，将特征二值化（bin），将将二值索引(bin index)看成是一个类别型特征。线性分类器可以有效地为该特征学到一个分段(piece-wise)常量的非线性映射。学到有用的二值边界很重要，有许多方法。

第二个简单但有效地转换包含在构建tuple型输入特征中。对于类别型特征，在笛卡尔积中采用的暴力搜索方法，比如，创建一个新的类别型特征，将它看成是原始特征的所有可能值。并不是所有的组合都有用，那些不管用的可以对其进行剪枝。如果输入特征是连续的，可以做联合二值化（joint binning），使用k-d tree。

我们发现boosted决策树很强大，非常便于实现非线性和上面这种tuple型转换。我们将每棵树看成是一个类别型特征，它把值看成是将叶子的索引。对于这种类型的特征，我们使用1-of-K的编码。例如，考虑图1中的boosted tree模型，有2棵子树，其中第1棵子树具有3个叶子，第2棵具有2个叶子。如果一个实例在第1棵子树的叶节点2上结束，在第2棵子树的叶节点1上结束，那么整体的输入到线性分类器上的二元向量为：[0,1,0,1,0]，其中前3个实体对应于第1棵子树的叶子，后2个对应于第2棵子树。我们使用的boosted决策树为：Gradient Boosting Machine(GBM)[5]，使用的是经典的L2-TreeBoost算法。在每个学习迭代中，会对前面树的残差进行建模创建一棵新树。我们可以将基于变换的boosted决策树理解成一个监督型特征编码（supervised feature encoding），它将一个实数值向量(real-valued vector)转换成一个压缩的二值向量(binary-valued vector)。从根节点到某一叶子节点的路径，表示在特定特征上的一个规则。在该二值向量上，再fit一个线性分类器，可以本质上学到这些规则的权重。Boosted决策树以batch方式进行训练。

我们开展实验来展示将tree features作为线性模型的效果。在该实验中，我们比较了两个logistic regression模型，一个使用tree feature转换，另一个使用普通的(未转换)特征。我们也加了一个单独的boosted决策树模型作为对比。所表1所示：

相对于没有树特征转换的模型，树特征变换可以帮助减小3.4%的NE。这是非常大的相对提升。作为参考，一个典型的特征工程实验，可减小20-30%左右的相对NE。LR和树模型以独立方式运行下的比较也很有意思（LR的预测accuracy更好一点点），但它们组合起来会有大幅提升。预测acuracy的增益是很大；作为参考，特征工程的好坏可以影响NE更多。

3.2 数据新鲜度

点击预测系统经常被部署在动态环境上，数据分布随时间变化。我们研究了训练数据的新鲜度对于预测效果的提升情况。我们在特定的某一天训练了一个模型，并在连续的数天对该模型进行测试。我们同时运行boosted决策树模型，以及一个使用树转换的LR模型。

在该实验中，我们训练了一天的数据，在后面的6天进行评估，计算每天的NE。结果如图2所示。

图2: 预测accuracy和时间关系

随着训练集与测试集间的时延的增长，预测accuracy明显下降。一周内两种模型的NE都下降大概1%左右。

该发现表明，需要以天为基础重新训练模型。一种选择是：使用一个周期天级任务，以batch方式重新训练模型。重新训练boosted决策树的时间各有不同，具体依赖于训练样本数，树的数目，每棵树的叶子，cpu，内存等。对于单核cpu，1亿左右的样本，有可能会超过24小时来构建一个上百棵树的boosting模型。实际情况中，训练过程可以在多核机器上，内存量足够存储整个训练集，通过足够的并发，使用几个小时来完成。下一部分，我们可以使用另一种方法。boosted决策树，可以每天或者每两天进行训练，但是线性分类器可以通过在线学习方式，接近实时进行训练。

3.3 在线线性分类器

为了最大化数据的新鲜度，一个选择是，当广告曝光数据到达标注后，直接在线训练线性分类器。在下面的第4部分，我们会描述一些基础，用来生成实时训练数据。在这部分，我们评估了许多方式，为基于SGD的LR在线学习设置不同的learning-rate。我们接着比较BOPR模型的在线学习最好变种。

在语术(6)中，我们可以有以下选择：

1.Per-coordinate学习率。该learning rate对于特征i在第t次迭代可设置成：

α, β 是两个可调的参数。

2.Per-weight均方根学习率。

3.Per-weight学习率：

4.全局学习率：

5.常数学习率：

前三种scheme可以为每个feature独立设置learning rate。后两种为所有feature使用相同的learning rate。所有可调的参数可以通过grid search进行优化。

对于连续学习（continuous learning），我们可以将learning rate设置为一个较低的边界0.00001. 我们使用上述的learning rate scheme来在相同的数据上训练和测试LR模型。相应的试验结果如图3所示。

图3: 不同learning rate schema的实验. X表示不同的learning rate。左侧为calibration，y轴右侧为NE.

从上面的结果可知，使用per-coordinate learning rate的SGD可以达到最好的预测accuracy，它可以降低5%的NE，比使用per weight learning rate要低（这种最差）。该结果的结论在[8]。per-weight square root学习率和常数学习率，几乎相同。另两种则比前面的都要差很多。global学习率失败的原因主要是因为训练实例的数目在每个特征上是不平衡的(imbalance)。由于每个训练实例可能包含不同的feature，一些流行的feature比起其它feature会具有更多的训练实例。在global学习率scheme下，具有更少训练实例的features的learning rate，会降得更快，以阻止最优weight（optimum weight）的收敛。尽管per-weight的learning rate的scheme也有相同的问题，它仍会失败，因为对于所有features，它会很快地减小learning rate。训练会过早终结，而模型会收敛到一个次优的点（sub-optimal point）。这解释了为什么该scheme在所有选择中具有最差的performance。

有意思的是，需要注意BOPR更新式(3)，意味着最接近LR SGD的per-coordinate learning rate版本。BOPR的有效学习率可以指定到每个coordinate上，取决于权重的后验variance，与每个单独的coordinate相关。

。。

4.Online data JOINER

前面的部分确定了训练数据中新鲜度会增加预测accuracy。同时也介绍了一个简单的模型架构，其中的线性分类器这一层是在线方式训练的。

本部分介绍一个实验系统，它生成实时训练数据，通过online learning来训练线性分类器。我们将该系统看成是”online joiner”，因为它的临界操作(critical operation)是将labels(click/no-click)和训练输入(ad impressions)以在线方式join起来。相同的基础设施可以用于流式学习（stream learning），例如Google Advertising System[1]。该online joiner会输出一个实时的训练数据流到一个称为“Scribe”的基础设施上[10]。而positive labels(clicks)是定义良好的，它没有提供给用户”no click”按钮。出于该原因，如果用户看到该广告后，在一个确定、足够长的时间周期上没有点击该广告，那么这次曝光(impression)可以认为是具有一个negative的no-click label。等待的时间窗口需要小心调节。

• 太长的时间窗口(time window)：实时训练数据会延迟，并增加额外内存分配开销来缓存要等待点击信号的impressions。
• 过短时间的时间窗口：会造成一些点击丢失，因为相应的impression可以会被冲掉，并当成no-clicked label来对待。这种负面影响称为”点击覆盖（click coverage）”，它是一个关于所有成功的clicks与impressions相join的一个分数。

作为结果，online joiner系统必须在最新性（recency）和点击覆盖(click coverage)间做出一个平衡。

不具有完整的点击覆盖，意味着实时训练集是有偏的(bias)：经验CTR(empirical CTR)会比ground truth要低。这是因为：一部分被标注为未点击（no-clicked）的曝光（impressions），如果等待时间足够长，会有可能会被标注成点击数据。实际上，我们会发现，在内存可控范围内，随着等待窗口的size的变大，很容易减小bias到小数范围内。另外，这种小的bias是可衡量和可纠正的。关于window size的研究可以见[6]。

online joiner被设计成执行一个在ad impressions和ad clicks之间的分布式stream-to-stream join，使用一个请求ID(request ID)作为join的主键。每一时刻当一个用户在Facebook上执行一个动作时，都会生成一个请求ID，会触发新鲜的内容曝光给他们。图4展示了online joiner和online learning的数据和模型流。当用户访问Facebook时，会生成初始的数据流，会发起一个请求给ranker对候选广告进行排序。广告会被传给用户设备，并行的，每个广告、以及和它相关的用于ranking的features，会并行地添加到曝光流（impression stream）中。如果用户选择点击该广告， 那么该点击(click)会被添加到点击流中（click stream）。为了完成stream-to-stream join，系统会使用一个HashQueue，它包含了一个先入先出的队列（FIFO queue）作为一个缓存窗口；以及一个hashmap用于快速随机访问label曝光。一个HashQueue通常在kv-pair上具有三种类型的操作：enqueue, dequeue和lookup。例如，为了enqueue一个item，我们添加该item到一个队列的前面，并在hashmap中创建一个key，对应的值指向队列中的item。只有在完整的join窗口超期后(expired)，会触发一个有标签的曝光(labeled impression)给训练流。如果没有点击join，它会触发一个negative的标注样本。

在该实验设置中，训练器(trainer)会从训练流中进行持续学习，并周期性发布新模型给排序器(Ranker)。这对于机器学习来说，最终会形成一个紧的闭环，特征分布的变更，或者模型表现的变更都能被捕获，学到，并在后续得到修正。

一个重要的考虑是，当使用实时训练数据生成系统进行试验时，需要构建保护机制来处理在线学习系统崩溃时引发的异常。例如：由于某些数据基础设施的原因，点击流（click stream）过期了，那么online joiner将产生这样的数据：它具有非常小或近乎0的经验CTR（empirical CTR）。作为结果，该实时训练器会开始以非常低、或近乎0的点击概率来进行错误的预测。一个广告的期望值会自然的决策于估计的点击概率，不正确预测成非常低的CTR的一个结果是，系统会降低广告曝光数。异常检测机制在这里就很有用。例如，如果实时训练数据分布突然发生变更，你可以从online joiner上自动断开online trainer。

5.内存与延迟

5.1 boosting trees的数目

模型中树越多，训练时间越长。这部分会研究树的数目在accuracy上的影响。

我们区分了树的数目，从1到2000棵，在一个完整天的数据上训练模型，并在下一天预测效果。我们限制了每棵树的叶子节点不超过12个。与之前的试验类似，我们使用NE作为评测的metric。试验结果如图5所示。NE会随着boosted trees的数目增加而增加。然而，通过添加树获得的增益，所获得的回归会减少。几乎所有的NE提升，都来自于前500棵树。最后的1000棵树减少的NE比0.1%还要少。另外，我们看到，NE对于子模型2(submodel 2), 会在1000棵树后开始倒退。这种现象的可能原因是overfitting。因为子模型2的训练数据比子模型0和1的要小。

图5: boosting tree的数目的实验。不同系统对应着不同的子模型。x轴表示boosting trees的数目。Y轴表示NE.

5.2 Boosting feature importance

特征数（feature count）是另一个模型特性，它可以影响估计的accuracy和计算性能。为了更好理解特征数的影响，我们首先为每个特征应用一个特征重要性（feature importance）。

为了衡量一个特征的重要性，我们使用statistic Boosting Feature Importance，它可以捕获一个feature的累积loss衰减属性（cumulative loss reduction）。在每个树节点构建中，会选择最好的feature，并将它进行split，来达到最大化平方误差衰减（squared error reduction）。由于一个feature可以被用在多棵树中，每个feature的（Boosting Feature Importance）可以通过在所有树上对一个指定feature做总的reduction的求和。

通常，只有少量的特征对可解释性(explanatory power)有主要贡献，对可解释性，而其余的特征则只有少量贡献。我们可以看到，当绘制特征数 vs. 累积特征重要性时（如图6所示），这种现象。

图6: Boosting feature importance。x轴表示特征数。在y轴左侧表示log scale中抽取了特征重要性，而y轴右侧表示累积特征重要性。

从上面的结果看来，top 10的特征占握着总的特征重要性的一半，而最后300个特征只贡献了少于1%的feature importance。基于该发现，我们进一步试验，只保留top 10,20,50,100,200个特征，并评估是如何影响表现的。试验的结果如图7所示。从图中可知，我们可以看到，当增加更多的特征时，NE的回报很少。

图7: 对于top features，Boosting模型的结果. 我们在y轴的左边，抽取了calibration，而在右边的y轴对应于NE.

下面，我们将研究，历史特征(historical feature)和上下文特征（contextual feature）是否有用。由于数据敏感性，我们不能展示实际使用的特征细节。一些上下文特征举例：一天里的local time，week里的天等。历史特征可以是：在一个广告上的点击累计，等。

5.3 历史型特征

Boosting模型中使用的特征可以归类为两类：上下文型特征（contextual features）和历史型特征（ historical features）。上下文特征的值仅仅取决于取决于一个广告所处的上下文当前信息，比如，用户使用的设备，或者用户停留的当前页面。相反的，历史特征则取决于广告(ad)或用户(user)之前的交互，例如，该广告在上周的点击通过率（click through rate），或者该用户的平均点击通过率。

图8: 历史型特征百分比的结果。X轴表示特征数。Y轴表示历史型特征在top-k个重要特征中的占比。

在这一部分，我们研究了该系的表现是如何受这两种特征影响的。首先，我们检查了两种类型的相对重要性。我们通过将所有特征按重要性进行排序，接着计算在top-k个重要的特征中，历史特征的占比。结果如图8所示，从该结果看，我们可以看到，比起上下文型特征，历史型特征更具可解释性。通过重要性排序的top 10个特征全部都是历史型特征。在top 20个特征间，只有2个上下文特征，尽管历史型特征在数据集上占据着75%的特征。为了更好地理解在aggregate中每种类型的比较值，我们训练了两种Boosting模型：一种只使用上下文型特征，另一种只使用历史型特征，接着将两个模型与带所有特征的完整模型相比较。结果如表4所示。

[表4]

从该表中，我们可以再次验证，历史型特征比上下文型特征更重要。如果只有上下文型特征，我们在预测accuracy上计算4.5%的loss。相反地，没有上下文型特征，我们在预测accuracy上有1%的loss。

需要注意到，上下文型特征对于处理冷启动问题很重要。对于新用户和新广告，上下文型特征对于合理的点击率预测是必不可少的。

在下一步，我们会评估在连续几周中，只使用历史型特征的训练模型，或者只使用上下文特征的训练模型，来测试在数据新鲜度上的特征依赖性。结果如图9所示。

图9: 不同类型特征对数据新鲜度的结果。X轴表示评估时期，Y表示NE.

从该图看到，比起历史型特征，使用上下文型特征的模型更依赖于数据新鲜度。这与我们的直觉相符合，因为历史型特征描述了长期累积的用户行为，它比起上下文型特征更稳定。

6.大规模训练数据

Facebook的一整天的广告曝光数据是海量的。注意，我们不会展示实际数量。但一天的一定比例的数据可以有几百万的实例。一个控制训练开销的常用技术是：减少训练数据的量。在本节中，我们评估了两种方法用于下采样：均匀子抽样（uniform subsampling）和负下采样(negative down sampling)。在每个case上，我们会训练一个使用600棵树的boosted tree模型的集合，然后使用calibration和NE进行评估。

6.1 均匀子抽样

训练行的均匀子抽样(uniform subsampling)是一种减少数据量的好方法，因为它可以很容易实现，生成的模型不需要修改，就可以在抽样的训练数据上以及未抽样的测试数据上直接使用。在本部门，我们会评估抽样率会指数式增加。对于每个在基础数据集上进行抽样的rate，我们分别训练了一个boosted tree模型。subsampling rate为{0.001, 0.01, 0.1, 0.5, 1}。

图10: 数据量的实验结果。X轴表示训练实例数。y左表示calibration。y右表示NE.

数据量及结果如图10. 它与我们的直觉相一致，越多的数据会导致更好的表现。再者，数据量展示了预测accuracy的回报会越来越少。通过使用10%的数据，NE只有在表现上，相较于整个训练数据集只有1%的减少。在该sampling rate上calibration几乎没有减少。

6.2 负下采样

类别不均衡（class imbalance）问题，许多研究者都有研究，它会对学到的模型具有重大的影响。在该部分，我们探索了使用负下采样（Negative down sampling）来解决类别不均衡的问题。经验上，我们使用不同负下采样率，来测试学到模型的accuracy。相应的rate为：{0.1, 0.01, 0.001, 0.0001}。结果如图11所示。

图11: 负下采样的实验结果。X轴对应于不同的负下采样率。y左表示calibration，y右表示NE.

从结果上看，我们可知，负下采样率在训练模型的表现上具有极大的提升。当负下采样率设置在0.025时具有最好的表现。

6.3 模型Re-Calibration

负下采样可以加速训练，提升模型表现。注意，如果在一个数据集上使用负下采样来训练一个模型，它可以校正(calibrate)在下采样空间上的预测。例如，如果平均CTR在采样之前只有0.1%，我们做一个0.01的负下采样，经验CTR（empirical）大约有10%的提升。对于真实的流量实验(hive traffic experiment)，我们需要重新校准模型，会获得0.1%的回报，$ q=\frac{p}{p+(1-p)/w} $。其中p是在下采样空间中的预测，w是负下采样率。

略.

参考：

1.Practical Lessons from Predicting Clicks on Ads at Facebook 2.kaggle:gbdt+libffm

2013 google发表的paper：<Ad Click Prediction: a View from the Trenches>。来看一下核心部分：

一、系统总览

当一个用户做出一个搜索q时，会基于广告主投放的关键词（advertiser-chosen keywords）根据q匹配一个初始的候选ad集合。竞价机制接着会决定这些广告是否展示给该用户，以及以什么顺序展示给用户，以及广告商的广告被点击要付的费用。除了广告主投标（advertiser bids），竞拍的一个重要输入是，对于每个广告a，会有一个被点击的概率估计：$ P(click | q, a) $。

在我们的系统中所使用的特征，从多个源抽取，包括query、广告文本、多种与广告相关的元信息。数据会趋向于相当稀疏，对于每个样本通常只有一个很小的部分具有非零特征。

基于正则的LR等方法天然就可以处理该问题。对于每天可以做出数十亿次的预测，并可以在观察到新点击/非点击数据时快速更新模型。当然，该数据比例意味着训练数据集是很庞大的。数据的提供通过基于Photon系统的流式服务提供。

由于大规模学习已经在近些年研究得很好，在该paper中不再详细描述系统架构。我们注意到，训练方法可以具有与Downpour SGD方法（from google brain team）相似之处，不同之处是，我们训练了一个单层模型而非多层的深度模型。这允许我们处理更大数据集、更大模型，具有数十亿的参数。由于训练的模型可以被复制到多个数据中心进行serving，我们更广告在serving时上的稀疏化（sparsification），而非训练时。

二、在线学习和稀疏化

对于大规模学习，对于常用的线性模型（比如：LR）在线算法，具有许多优点。尽管特征向量x可能具有数十亿维，通常每个样本都只有数百个非零值。这使得在大数据集上通过从硬盘或网络的流式样本(streaming examples)可以有效进行训练，因为每个训练样本只需要被考虑一次。

为了精准地表述该算法，我们需要建立一些注解。$ g_t \in R^d $表示向量，其中t表示当前训练实例的索引；向量$g_t$中的第$i^{th}$个条目表示为$g_{t,i}$。我们也使用压缩过的求和：$g_{1:t}= \sum_{s=1}^{t} g_s $。

如果我们希望使用LR进行建模，我们可以使用下面的在线框架。在第t轮，我们通过特征向量$x_t \in R^d$来预测一个实例；给定模型参数$w_t$，我们预测$p_t=\sigma(w_t · x_t)$，其中$ \sigma(a)=1/(1+exp(-a)) $是sigmoid函数。接着我们观察到label $y_t \in {0,1} $，使用LogLoss：

\(l_t(w_t) = -y_t log p_t - (1-y_t) log(1-p_t)\) …(1)

$ y_t $的负log似然会给出概率p。$ \triangledown{l_t(w)}=(\sigma(w · x_t) - y_t) x_t = (p_t-y_t) x_t $，该梯度就是我们要优化的目标。

在线梯度下降（OGD：online gradient descent）对于这类问题很有效，只需要少量的计算资源就可以产生很好的预测精度。然而，实际上另一个关键考虑点是：最终模型的size；因为模型可以被稀疏存储，w中的非零参数是内存使用量的决定因子。

不幸的是，OGD在产生稀疏模型上并不特别有效。事实上，简单添加L1罚项的一个次梯度（subgradient）到loss的梯度中，将不会产生等于0的参数。更复杂的方法（比如：FOBOS）和截断梯度（truncated gradient）在引入稀疏化上是很成功的。对比于FOBOS算法，RDA（ Regularized Dual Averaging）算法会产生更好的准确率（accuracy）。然而，在我们的数据集上，比起RDA，我们已经观察到梯度下降的方法可以产生更好的准确率。问题是，我们是否可以同时满足稀疏化（由RDA产生）和准确率（OGD产生）？答案是：yes！使用RTRL-Proximal算法（Follow The (Proximally) Regularized Leader）。没有正则化，该算法会等同于标准的在线梯度下降法，但因为它使用了另一种模型参数w的延迟表示（lazy representation），L1正则可以被更有效地实现。

FTRL-Proximal算法之前主要在理论分析方面。这里，我们主要描述实际实现。给定一个梯度的序列$g_t \in R $，OGD执行更新：

其中$ \eta_t $是一个非增长(non-increasing)的学习率schedule，例如：$ \eta_t = \frac{1}{\sqrt{t}} $。FTRL-Proximal算法则使用下面的更新作为替代：

其中我们定义了$ \sigma_{s} $表示learning-rate schedule，比如：$\sigma_{1:t}=\frac{1}{\eta_t}$。表面上，这些更新看起来很不同，但实际上，当我们采用$ \lambda_1=0 $，它们产生一个系数向量的相同序列。然而，FTRL-Proximal会使用$ \lambda_1 > 0$更新，在引入稀疏化上效果很好（详见试验结果）。

快速检查下，你可能认为FTRL-Proximal的更新比梯度下降更难，或者需要存储所有过去的参数。实际上，每个参数只有一个需要存储，因为我们可以重写更新作为argmin：

这里，如果我们已经存储了 $ z_{t-1} = g_{1:t-1} - \sum_{s=1}^{t-1} \sigma_s w_s $，在第t轮的开始处，我们设置：$z_t = z_{t-1} + g_t + (\frac{1}{\eta_t} - \frac{1}{\eta_{t-1}})w_t$进行更新，以闭式(closed form)求解$w_{t+1}$：

这样，FTRL-Proximal会在内存中存储 $ z \in R^d $，其中OGD会存储$ w \in R^d $。算法1就采用该方法，但也会添加一个per-coordinate learning rate schedule，并支持在$lambda_2$的L2正则。另一种方法是，我们会存储 $-\eta_t z_t $，而非直接存储$z_t$；接着，当$ \lambda_1=0 $，我们会准确存储正常的梯度下降参数。注意，当$eta_t$是一个常数值$\eta$，$\lambda_1=0$，很容易看到，OGD的等价物，因为我们已经有$w_{t+1}=-\eta z_t = -\eta \sum_{s=1}^{t} g_s$，与梯度下降的角色相同。

试验结果。在我们数据集上小版本上的试验，在size-vs-accuracy权衡上，McMahan等展示了使用L1正则的FTRL-Proximal比RDA和FOBOS的效果有极大提升；这些之前的结果见表1: 行2和行3.

在许多样本上，一种简单的启发式也工作良好。我们的straw-man算法，OGD-Count，简单维持它看到某个特征的count数；直到count数传递一个阀值k，参数被固定在0上，但在count传入k后，OGD（不带L1正则）会和往常处理一致。为了测试FTRL-Proximal，我们在大数据集上运行。我们对k进行调参，来生成与FTRL-Proximal相同的准确率；使用更大的k来产生更差的AucLoss。结果如表1:第4行所示。

总体上，这些结果展示了FTRL-Proximal，它可以极大提升了稀疏性，同昌使用相同或更好的预测准确率。

Per-Coordinate Learning Rates

OGD的标准理论建议使用一个全局的learning-rate schedule $\eta_t = \frac{1}{\sqrt{t}}$，这对于所有坐标来说都通用。一个简单的试验展示了这种方式是不理想的：假设我们为10个硬币正估计 $Pr (heads | coin_i)$，使用LR。每个第t轮，只有一个硬币i会进行抛币试验，我们看到特征向量$x \in R^{10} $，其中$x_i = 1$，$x_j=0$，对于$ j \neq i$。 这样，我们求解10个独立的LR问题，并打包到单个问题中。

我们可以运行10个独立的OGD copy，其中对于问题i的算法实例，可以使用一个learning rate: $ \eta_{t,i} = \frac{1} {\sqrt{n_{t,i}}}$，其中 $n_{t,i}$是硬币i至今被抛的的次数号。如果硬币i比硬币j抛的次数更多，硬币i的learning rate将下降的更快，印证了在多数据集上得到的事实；对于硬币j，它的learning rate仍将很高，因为我们已经在我们当前的估计上具有更少的置信度，因此需要对新数据反应更快。

另一方面，如果我们将这种看成是单个learning-rate问题，标准的learning rate schedule为：$\eta_{t} = \frac{1}{\sqrt{t}}$被应用到所有坐标上：也就是说，我们会对硬币i的learning rate进行下降，即使它没有被翻转。这很明显不是最优的行为。事实上，Streeter和McMahan已经展示了一个熟悉的问题：其中标准算法的性能渐近地比运行独立copy的效果要更差。因而，对于这些问题，per-coordinate learning rates会提供一个实质上的优点。

回忆下，$g_{s,i}$是梯度$g_s=\nabla {l_s}{w_s} $第i个cordinate。per-coordinate rate的如下：

……(2)

在某种程度上是近似最优的。实际上我们会使用这样的learning rate：选择$\alpha$和$\beta$它们可以在progressive validation上生成好的效果（见5.1）。我们已经试验：使用counter $n_{t,i}$上的一个power，而非0.5. $\alpha$的最优值可以随着特征和数据集的不同而不同，$\beta=1$通常足够好；简单确保早期的learning rate不要太高。

正如前面所述，该算法需要我们跟踪梯度求和，以及每个feature的梯度平方和。第4.5节将描述一种可选的节约内存的方式，其中梯度平方和在多个模型上进行分摊（amortize）。

per-coordinate learning rate的一个相对简单的分析在paper[29]中，它在小的google数据集上试验结果很好；该工作直接使用Zinkevich的方法。对于FTRL-Proximal的一种更理论的解释在paper[26]中。Duchi等人分析了RDA以及mirror-descent版本，也给出了多种试验结果。

试验结果。通过测试两种相同的模型，我们对per-coordinate learning rate的影响进行评估：一个使用单一的global learning rate，另一个使用per-coordinate learning rates。基础参数$\alpha$对每个模型进行独立调参。我们在一个有代表性的数据集上运行，使用AucLoss作为我们的评估metric（见第5部分）。结果展示出，对比于global-learning rate的baseline，使用per-coordinate learning rate可以将AucLoss可以减小11.2%。

4.在大规模上节约内存

如上所述，我们使用L1正则来在预测时节约内存。在本节中，我们描述了额外的tricks来在训练期间节约内存。

4.1 概率特征包含（Probabilistic Feature Inclusion）

在许多领域具有高维数据，大多数特征是相当稀疏的。事实上，在我们的一些模型中，半数唯一特征（（unique features）在整个数十亿的样本训练集上只出现一次。

对于这些罕见的特征进行跟踪统计是很昂贵的，实际上它们可能从不会被用到。不幸的是，我们不知道哪个特征是罕见的。对数据进行预处理来移除罕见特征在online环境下是棘手的：一个额外的读数据和写数据是相当昂贵的，如果一些特征被丢弃掉（因为它们出现少于k次），它们不再可以尝试这样的模型：这些模型使用这些特征来估计预处理在accuracy方面的代价。

一种家族式方法，可以在训练时完成稀疏化，通过实现L1正则，它不需要跟踪特征统计，参数为0。这允许少量有益的特征可以在训练过程中被移除。然而，我们发现，对比起其它方法（比如FTRL-Proximal：在训练时会跟踪更多特征，在serving时会稀疏化），这种稀疏化会在accuracy上导致一个不可接受的loss。另一种常见的解决方案是，对碰撞进行hashing，但这不会结出有用的好处。

另一大类方法是：probalilistic feature inclusion，在该方法中，新特征会在它们第一次出现时，有概率的被包含在模型中。这会让数据预处理的完成更有效，但在online时被执行。

我们按该方法测试了两种方式：

• 泊松包含（Poisson Inclusion）。当我们遇到一个特征时（它不在我们的模型中），我们使用概率p将它添加到模型中。一旦一个特征被添加，后续的观察，我们照例更新它的参数值，和OGD所用到的相关统计量。特征在添加到模型之前被看到的次数，会服从一个几何分布：期望值为$\frac{1}{p}$
• 布隆过滤器包含（Bloom Filter Inclusion）。我们使用一个counting Bloom filters的集合，来检查一个特征在训练集中首先出现的n次。一旦特征出现超过n次（根据该filter），我们就将它添加到模型中，并使用它来在后续观察中进行训练。注意，该方法也是概率化的（probalilistic），因为一个counting bloom filter可以是false positives（但不会是false negatives）。也就是说，我们有时会包含一个特征：它们的出现次数少于n次。

试验结果：这些方法的效果见表2,两种方法效果都不错。在预测质量的loss以及RAM saving的tradeoffs上，但Bloom filter方法给出了更好的效果。

4.2 使用更少的Bits来编码值

OGD的Naive实现，使用32或64位浮点值（floating point）编码来存储参数值。浮点编码通常受欢迎，是因为它们更大的动态范围以及更细的precision；然而，对于我们的正则LR模型的参数，这被证明是过度伤害的。几乎所有的参数值的范围在(-2,+2)。分析之后表明，细粒度的precision是没有必要的，这推动着我们去探索fixed-point q2.13编码的使用，而非floating point。

在q2.13编码中，我们保留两位给binary decimal point的左部，十三位给binary decimal point的右部，一位留给符号，每个值共16位。

这个reduced precision，可能会在OGD环境下创建一个带有累积舍入偏差（accumulated roundoff error）的问题，它需要大量小步骤的累积。（事实上，我们已经看到严重的舍入问题，它使用32位floats，而非64位）。然而，一个简单随机的rounding策略可以纠正该问题，以一个小的添加的遗忘项的代价。关键点是，通过显式的rounding，我们可以确保离散化error具有零均值。

特别的，如果我们存储参数w，我们设置：

…(3)

其中，R是一个在[0,1]间的均匀分布的一个随机偏离。$g_{i,rounded}$接着存储在q2.13 fixed point格式中；在[-4,4)范围外的值会被裁减。对于FTRL-Proximal，我们可以以这种方式存储$\eta_t z_t$，它与$w_t$有相似的幅值。

试验结果。实际上，对比起使用q2.13 encoding（替代floating point值）的模型的结果，我们观察到没有可测量的loss损失。我们可以节约75%的RAM来存储参数。

4.3 训练多个相类似的模型

当对超参数或feature的变更进行测试时，评估多个小的变种是很有用的。这种常见的用例允许有效的训练策略。一个有意思的地方是paper[19]，它使用一个fiexed model作为先验，允许多个变种在残差（residual error）上进行评估。这种方法开销很小，但不容易对特征移除（feature removal）或可选的learning setting进行评估。

我们的主要方法依赖于该观察：每个coordinate依赖于一些数据，它们可以被有效地在模型变种间共享，而其它数据（比如：参数值自身）被指定给每个模型变种，不能被共享。如果我们在hash table中存储模型参数，我们可以对所有变种使用单个表，分摊存储key的开销（string或many-byte hash）。在下一节，我们展示了，每个模型的learning-rate counters $n_i$是如何被所有变种的统计共享替代的，它会减小存储。

任意变种不会有一个特定的feature，它会为该feature存储参数成0，浪费一点空间。（我们通过将这些特征的learning rate设置成0）。因为我们只与高度相似的模型一起训练，从这种表示(不表示该key)中获得的内存savings，以及每个模型的counts比不常见的特征的loss要更大的多。

当多个模型一起训练时，分摊的开销会压低，所有per-coordinate的元数据，比如per-coordinate learning rates所需要的counts，递加的额外模型的开销依赖于需要存储的额外参数值。该saves不仅仅是内存，还有网络带宽（值以相同的方式通过网络进行通信，但我们只读取一次训练数据），CPU（只有一个hash table lookup，而非多个，从训练数据中生成的特征只需一次，而非每个模型一次），磁盘空间。这个捆绑的架构会极大增加我们的训练容量。

4.4 单值架构

有时我们希望评估非常大的模型变种的集合，它们只会在少量特征组上进行增加和移除。这里，我们可以采用一种压缩数据结构，它是有损耗的（lossy），(adhoc)，但实例上会给出十分有用的结果。这种单值架构会为每个coordinate存储只有一个参数值，它们通过包含这些特征的模型变种进行共享，而非存储独立的参数值。一个位域（bit-field）可以被用于跟踪哪个模型变种包含了给定的coordinate。注意，这与paper [19]中的方法精神相类似，但也允许特征移除的评估。该RAM的开销增长得很慢，比起4.3节的方法。

学习过程如下：对于一个在OGD中的给定更新，每个模型变种会计算使用包含它在内在coordinates的子集的预测和loss，为每个参数抽取存储的单个值。对于每个特征i，每个模型会使用i为给定的参数计算一个新的期望值。产生的值被平均，存储成单个值，它将接着被下一步中所有变种所共享。

我们评估该启发法（heuristic），通过计算模型变种（它们使用单值架构进行训练，对比起相同的变种，它们由4.3节的方法进行训练）的大组来进行。展示的几科等同于跨变种的相关效果，但单值结构会保存RAM的幅度顺序（magnitude order）。

4.5 计算带Counts的learing rates

在3.1节所示，我们需要存储每个特征的梯度求和及梯度平方和。重要的一点是，梯度计算可以被纠正，但可以做出总近似值，以便计算learning rate。

假设包含了一个给定的特征的所有事件，都具有相同的概率。（总这，这是一个可怕的近似，但它可以行得通）。进一步假设模型已经准确学到了该概率。如果它们有N个负样本(negative events)，P个正样本（positive events），接着该概率为 p = P/(N+P)。如果我们使用LR，正样本的梯度为p-1,负样本的梯度为p，等式2对应的learning rate所需要的梯度求和如下：

这种残酷的近似允许我们跟踪N和P的counts，无需存储$ \sum{g_{t,i}^2}$。经验上，learning rates的计算和该近似，可以有效工作，正如我们使用完整的求和（full sum）计算的learning rates。使用第4.3节的框架，总的存储开销会更低，因为所有的变种模型具有相同的counts，因而对于N和P的存储开销会被分摊。该counts会使用变长的位编码进行存储，大多数features不需要多个bits。

4.6 对训练数据子抽样(subsampling)

通常，CTR会低于50%，这意味着正样本（点击数）会相当稀少。这样，简单的统计计算表明：点击（clicks）在CTR预估学习中相对更有价值。我们可以利用这一点来极大减少训练数据的size，在accuracy上具有最少的影响。我们创建了子采样过的训练数据，包含在我们的样本中：

• 对于这个训练数据，任意query至少有一个广告被点击
• $r \in (0,1] $比例的queries，其中没有广告被点击

在query级别进行抽样是令人满意的，因为计算多个features需要在query阶段进行公共处理。当然，在该子抽样数据上直接进行原始训练(naively training)，将导致极大的预测偏差。这个问题可以通过分配一个重要性权重（importance weight）$w_t$给每个样本来轻易地解决：

因为我们控制着抽样的分布，我们不需要在通用抽样选择中估计权重w。重要性权重可以简单地按比例放大在每个样本上的loss，如等式(1)，因而也可以放大梯度。为了看到它具有特意的影响，考虑到在未抽样数据中的一个随机选中的样本t对子抽样目标函数的的期望贡献。$s_t$为它表示样本t被抽样到（不管是1还是r）的概率，由定义：$s_t=\frac{1}{w_t}$。因而，我们具有：

期望的线性(Linearity)，预示着在子抽样训练数据上的期望加权目标函数，等于在原始数据集上的目标函数。试验验证了：即使对非点击的query进行子抽样，也会在accuracy上有一个非常轻度的影响，预测的效果不会受指定值r的影响。

5.评估模型效果

模型质量的评估的完成开销很小，通过使用日志历史数据即可。（线上的模型评估很重要，但更昂贵；见[30]）

因为不同的metrics对应着模型更改的不同方式，我们发现，对于评估模型变化很有用。我们计算了metrics，比如AucLoss（也就是说1 - AUC，其中AUC是在ROC曲线下的标准区域面积），LogLoss（见等式(1)），以及SquaredError。出于一致性，我们也设计了我们的metrics，越小值越好。

5.1 Progressive Validation

我们总体上使用progressive validation（有时也称为online loss），而非cross-validation，或者在held-out dataset上进行评估。因为计算一个梯度需要计算一个预测，我们可以很方便地将这些预测(predictions)进行流式化，以便后续的分析，按小时聚集。我们也在数据的多个子切片计算这些metrics，比如：通过国家，查询主题，布局进行划分。

online loss对于在serving queries的accuracy来说，是一个好的代理，因为它可以衡量只在大多数最近数据上的效果，

一、介绍

参考

• 0.Ad Click Prediction: a View from the Trenches
• 1.Follow-the-Regularized-Leader and Mirror Descent: Equivalence Theorems and L1 Regularization

在推荐系统中，用于测试模型性能，通常会选定随机选定部分用户，观察这些用户在推荐项上的行为。这就是我们常说的分桶测试（bucket tests）。

假定有两个推荐模型：模型A和模型B。我们可以创建两个不相交的样本：基于用户（用户id）的样本选择方式创建、或基于请求（用户访问行为）的样本选择方式创建。接着，对于第一个样本，使用模型A； 对于第二个样本，使用模型B。并持续服务一段时间。这里的每个样本，称为一个桶（bucket）。通常有两种常用的分桶方式：

• 1.基于用户的分桶（User-based bucket）：这样的桶，是一个随机选定用户的集合。一种简单的方式是，使用一个hash函数，为每个user id生成一个hash值，选择一个特定的范围指向一个桶。例如：Ron Rivest设计的md5。

• 2.基于请求的分桶（Request-based bucket）：这样的桶，是一个随机选择的请求的集合。常用的做法是，为每个请求生成一个随机数，然后将对应指定范围的请求随机数指定到某个桶内。注意，在这样的桶中，在实验期间，同一个用户不同的访问，有可能属于不同的分桶。

基于用户的分桶，通常比基于请求的分桶更简洁、更独立。例如，当使用基于请求的分桶时，一个用户使用模型A的响应（Response），可能会影响到模型B。但是，在基于用户的分桶中，这个现象不会发生。另外，任何长期用户行为都可以在基于用户的分桶中进行。然而，如果在基于用户的分桶中使用一个简单模型，该分桶的用户可能会收到不好的结果，这样也会导致较差的用户体验。而基于请求的分桶则对这种模型相对不敏感些，因为一个用户的所有请求不一样分配到相同的bucket中。总之，基于用户的分桶更受欢迎些。

在受控的实验中，分桶的所有设置应该一致，除了为每个分桶分配的模型不同；模型A用于服务分桶1；模型B用于服务分桶2。特别的，对于两个分桶来说，我们要使用相同的选择方式准则。例如，某一个分桶只包含登陆用户，那么另一个分桶也必须一致。

当使用基于用户的分桶时，对于不同的测试，最好使用独立的各不相同的hash函数，以保持正交性。例如，假设我们在一个web页面具有两个推荐模块，每个模块对应两个要测试的模型。两个对应的测试模块：test1和test2。对于每个test i，都有两个对应的推荐模型：Ai和Bi。如果我们在两组test上使用相同的hash函数为用户分配hash值，hash值低于某个阀值的使用模型Ai，剩下的使用模型Bi，这样，模型A1的用户与模型A2的用户相同；模型B1的用户与模型B2的用户相同。由于涉及到与A2和B2的交互，这会导致模型A1与模型B1之间的比较不够合理。解决这种问题的一个方法是，确保分配给A1模型的用户概率与test2中的A2或B2模型相互独立。这很容易实现，如果我们在test1中使用的将user id映射后的hash值与test2中相互统计独立即可。使用独立的hash函数，可以帮助我们控制当前测试与之前测试的独立性。

另一个有用的实践是，使用相同的模型服务两组分桶，并确认两个桶对应的性能指标是否统计上相似。这样的测试通常称为A/A test。它不仅为继承的统计变量提供了一个好的估计，而且还可以帮助在实验阶段发现明显错误。另一个有用的实践是，运行一个分桶测试至少需要一到两周，因为，用户行为通常有一周时间里有时间周期性上的不同。当一个新的推荐模型推荐对应在其它模型上完全不同的item时，由于新奇性效应（novelty effect），用户(user)可能倾向于在初始阶段点击更积极。为了减小因此造成的潜在偏差，当监控测试指标时，通常抛弃开始阶段的测试结果是很有用的。

标准的实验设计方法可以用来决定一个分桶所需要size以达到统计显著性（statistical significance）。拔靴法（Bootstrap sampling）在决定性能指标的方差时很管用，它可以用来帮助计算分桶的抽样size。详见：Montgomery(2012)、Efron和Tibshirani(1993).

参考：

• Statistical Methods for Recommender Systems

移动端时代的挑战：手机屏更小，输入更不便，信息过载问题更严重。

用户获取信息的方式：浏览 vs. 查询

点击距离(click-distance):

click-distance(i) = selects(i) + scrolls(i) i为item的意思。

1 个性化用户兴趣

两种点击：

• static hit-table:大众的点击数据，one-size-fits-all
• user hit-table:个人的点击数据

其中static hit-table如下：

某一个用户的hit-table如下：

然后根据此计算这个用户对每个item的喜好概率. 概率计算：

• $ P(B

  A)=(20+10)/(40+100)=0.214 $

• $ P(C

  A)=(20+90)/(40+100)=0.786 $

• $ P(D

  A)=P(B

  A)P(D

  B)=(30/140)(10+5)/(20+10) = 0.107 $

• $ P(E

  A)=P(B

  A)P(E

  B)=(30/140)(10+5)/(20+10) = 0.107 $

• $ P(F	A)=P(C	A)P(F	C)=(110/140)(10+80)/(20+90)=0.642 $
  -$ P(G	A)=P(C	A)P(G	C)=(110/140)(10+10)/(20+90)=0.142 $

该用户的喜好排序为：C>F>B>G>D>E

2 个性化调整

ok，计算好了之后。需要对每个用户做menu的调整。调整方式采用的是：垂直提升（vertical promotions）。举个例子，原先如果是三层：根菜单－父菜单-菜单选项。菜单选项提升到父菜单级别，父菜单提升到根菜单级别。别外同级之间的相对位置也会进行调整。

3 指标评测

• 平均点击距离（是否降低）
• 平均每个session的平均导航时间（是否降低）
• 平均内容浏览时间（是否提升）

参考：

1.personalization techniques and recommender systems, Gulden Uchyigit etc.

此处省略开头，回归核心。。。

尽管word2vec提供了高质量的词汇向量，仍然没有有效的方法将它们结合成一个高质量的文档向量。在本篇文章中，受一个随机过程问题（中餐馆订餐过程CRP）的启发，我们讨论了一种可能的探索。基本思路是，使用CRP来驱动聚类过程，并将各种词向量在合适的聚类中合在一起。

假设我们有一个关于鸡肉订单（chicken recipe）的文档。它包含了下面的词汇：”chicken”, “pepper”,“salt”, “cheese”. 它也包含了其它的词汇：“use”, “buy”, “definitely”, “my”, “the”。 word2vec的模型将为每个单词生成一个vector。简单的，我们可以将所有词向量(word vector)合成一个文档向量（doc vector）。这将引入许多噪声。一种降噪方法是使用加权的合并，基于相应的算法，比如：IDF 或者 POS tag.

那么问题来了：当添加词汇时，是否可以更有选择性？回到鸡肉订单文档上，它不应该考虑以下的词汇：“definitely”, “use”, “my” 。基于权重的idf可以有效地减少一些停留词（”the”、”is”等等）的噪声问题。然而，对于这样的词汇：“definitely”， “overwhelming”，那么idf值将不会如你所愿那样的小。

如果我们首先将词汇聚类，像这样的词“chicken”, “pepper”将聚集到同一个类中，而像其它的词类似“junk”则希望聚到另一个类中。如果我们能区别相关的类，那么我们可以将相关类的词相量（word vector）合并，我们就可以得到一个很好的文档（doc vector）.

当然，我们可以使用通用的算法：K-means，但是大多数这些算法都需要一个距离公式。word2vec可以通过余弦相似度（cosine）很方便地进行相似判断，不一定需要采用欧氏距离。

如果我们使用余弦相似度，我们可以很快进行聚类词汇。

回到中餐馆问题，假设你来到一个中餐馆，发现已经有n张桌子，每张桌子有不同的人。另外还有一张空桌子。CRP有一个超参数 r > 0，它表示这张空桌子上可能的人数。你到了（n+1）的桌子中其中之一，桌子上存在不同数目的人（对于空桌子，数目为r）。当你到达其中的一张桌子时，那么整个过程完成。如果你决定坐在空桌子上，餐厅会自动创建一张空桌子。在这个例子中，如果下一个顾客到来时，他会在(n+2)张桌子上做选择（包括新的空桌子）

受CRP的启发，我们尝试了在CRP中，包含相似因子的的以下变量。过程大致相同：我们给定聚类的M个向量。我们去维护两个东西：聚类和（cluster sum，没有中心），聚类中的各个向量（vector）。通过各向量进行迭代。对于当前的向量V，假设我们已经有了n个聚类。现在我们去找到聚类C，它的聚类和与当前的向量相似。我们将这个分数称为 sim(V,C).

• 变量1: v 创建了一个新的聚类，它的概率为1/(1+n). 否则v就到聚类C中。
• 变量2:如果sim(V,C) > 1/(1+n)，则归到聚类C中。否则概率为1/(1+n)，它将创建一个新的聚类，概率为n/(1+n)，它将归到C。

在任意两个变量中，如果v归到一个聚类中，我们将更新聚类和，及相应的关系。

对于传统CRP，有一个明显的区别是：如果我们不到空桌子上，我们将决定去往“最相似”的桌子上。

实际上，我们将找到这些创建相似结果的变量。有个不同是，变量1趋向于更多但是单个量级更小的聚类；变量2趋向于少量，但是单个量级更大的聚类。变量2的例子如下所示：

对于chick recipe document，聚类如下：

• ‘cayenne’, ‘taste’, ‘rating’, ‘blue’, ‘cheese’, ‘raved’, ‘recipe’, ‘powdered’, ‘recipe’, ‘dressing’, ‘blue’, ‘spicier’, ‘spoon’, ‘cup’, ‘cheese’, ‘cheese’, ‘blue’, ‘blue’, ‘dip’, ‘bake’, ‘cheese’, ‘dip’, ‘cup’, ‘blue’, ‘adding’, ‘mix’, ‘crumbled’, ‘pepper’, ‘oven’, ‘temper’, ‘cream’, ‘bleu’, ……
• ‘the’, ‘a’, ‘that’, ‘in’, ‘a’, ‘use’, ‘this’, ‘if’, ‘scant’, ‘print’, ‘was’, ‘leftovers’, ‘bring’, ‘a’, ‘next’, ‘leftovers’, ‘with’, ‘people’, ‘the’, ‘made’, ‘to’, ‘the’, ‘by’, ‘because’, ‘before’, ‘the’, ‘has’, ‘as’, ‘amount’, ‘is’, ……
• ‘stars’, ‘big’, ‘super’, ‘page’, ‘oct’, ‘see’, ‘jack’, ‘photos’, ‘extras’, ‘see’, ‘video’, ‘one’, ‘page’, ‘f’, ‘jun’, ‘stars’, ‘night’, ‘jul’, ……

很明显地，第一个聚类最相关。接着，我们获取聚类和向量。下面是python代码，word vector通过c版本将 英文Wiki语料训练得到，它将使用gensim.model.word2vec的python库获取模型文件。 c[0]表示聚类0:

>>> similar(c[0], model[“chicken”])

0.95703287846549179

>>> similar(c[0], model[“recipe”] + model[“chicken”])

0.95602993446153006

>>> similar(c[0], model[“recipe”] + model[“fish”])

0.7678791380788017

>>> similar(c[0], model[“computer”])

0.0069432409372725294

>>> similar(c[0], model[“scala”])

0.061027248018988116

看上去语义信息保存完好。我们使用doc向量是可信服的。 菜单文档看起来很简单。我们可以尝试更多的挑战，比如一篇新闻文章。新闻本身是叙事型的，包含很少的“主题词”。我们尝试在这篇文章标题为：“Signals on Radar Puzzle Officials in Hunt for Malaysian Jet”的文章进行聚类。我们可以得到4个聚类：

• ‘have’, ‘when’, ‘time’, ‘at’, ‘when’, ‘part’, ‘from’, ‘from’, ‘in’, ‘show’, ‘may’, ‘or’, ‘now’, ‘on’, ‘in’, ‘back’, ‘be’, ‘turned’, ‘for’, ‘on’, ‘location’, ‘mainly’, ‘which’, ‘to’,, ‘also’, ‘from’, ‘including’, ‘as’, ‘to’, ‘had’, ‘was’ ……
• ‘radar’, ‘northwest’, ‘radar’, ‘sends’, ‘signal’, ‘signals’, ‘aircraft’, ‘data’, ‘plane’, ‘search’, ‘radar’, ‘saturated’, ‘handles’, ‘search’, ‘controlled’, ‘detection’, ‘data’, ‘nautical’, ‘patrol’, ‘detection’, ‘detected’, ‘floating’, ‘blips’, ‘plane’, ‘objects’, ‘jets’, ‘kinds’, ‘signals’, ‘air’, ‘plane’, ‘aircraft’, ‘radar’, ‘passengers’, ‘signal’, ‘plane’, ‘unidentified’, ‘aviation’, ‘pilots’, ‘ships’, ‘signals’, ‘satellite’, ‘radar’, ‘blip’, ‘signals’, ‘radar’, ‘signals’ ……
• ‘of’, ‘the’, ‘of’, ‘of’, ‘of’, ‘the’, ‘a’, ‘the’, ‘senior’, ‘the’, ‘the’, ‘the’, ‘the’, ‘the’, ‘the’, ‘a’, ‘the’, ‘the’, ‘the’, ‘the’, ‘the’, ‘of’, ‘the’, ‘of’, ‘a’, ‘the’, ‘the’, ‘the’, ‘the’, ‘the’, ‘the’, ‘its’, ……
• ‘we’, ‘authorities’, ‘prompted’, ‘reason’, ‘local’, ‘local’, ‘increasing’, ‘military’, ‘inaccurate’, ‘military’, ‘identifying’, ‘force’, ‘mistaken’, ‘expanded’, ‘significance’, ‘military’, ‘vastly’, ‘significance’, ‘force’, ‘surfaced’, ‘military’, ‘quoted’, ‘showed’, ‘military’, ‘fueled’, ‘repeatedly’, ‘acknowledged’, ‘declined’, ‘authorities’, ‘emerged’, ‘heavily’, ‘statements’, ‘announced’, ‘authorities’, ‘chief’, ‘stopped’, ‘expanding’, ‘failing’, ‘expanded’, ‘progress’, ‘recent’, ……

看起来挺不错的。注意，这是个 输入为1的聚类过程，并且我们不必去指定聚类数目。这对于对延迟很敏感的服务来说很有帮助。

缺失了一环：如何找出相关的聚类？我们在这部分不必做扩展实验。可以考虑：

• idf权值
• POS tag。我们不必在文档中标记每个词。根据经验，word2vec趋向于在语法构成上聚在一起。我们对每个簇都抽取出一些tag。
• 计算聚类和总向量，与标题向量

当然，还有其它问题需要考虑：

• 1) 如何合并簇？基于向量间的相似度？或者簇成员间的平均相似度
• 2)词的最小集合，可以重构簇和向量？可以使用关键词抽取方法。

结构：google的word2vec提供了强大的词向量。我们可以以有效的方式，来使用这些vector来生成高质量的文档向量。我们尝试了一个基于CRP变种的策略，并取得了结果。当然，还有很多问题需要研究，BalabalaBala…

代码如下：

# vecs: an array of real vectors
def crp(vecs):
    clusterVec = []         # tracks sum of vectors in a cluster
    clusterIdx = []         # array of index arrays. e.g. [[1, 3, 5], [2, 4, 6]]
    ncluster = 0
    # probablity to create a new table if new customer
    # is not strongly "similar" to any existing table
    pnew = 1.0/ (1 + ncluster)
    N = len(vecs)
    rands = random.rand(N)         # N rand variables sampled from U(0, 1)

    for i in range(N):
        maxSim = -Inf
        maxIdx = 0
        v = vecs[i]
        for j in range(ncluster):
            sim = cosine_similarity(v, clusterVec[j])
            if sim < maxSim:
                maxIdx = j
                maxSim = sim
            if maxSim < pnew:
                if rands(i) < pnew:
                    clusterVec[ncluster] = v
                    clusterIdx[ncluster] = [i]
                    ncluster += 1
                    pnew = 1.0 / (1 + ncluster)
                continue
        clusterVec[maxIdx] = clusterVec[maxIdx] + v
        clusterIdx[maxIdx].append(i)

    return clusterIdx

本文译自：http://eng.kifi.com/from-word2vec-to-doc2vec-an-approach-driven-by-chinese-restaurant-process/