d0evi1 Reading time ~1 minute

关于fastText，有两篇paper需要看下，见下面的参考。如果你的目的是用来训练词向量，可以查看paper 1. 如果是用来进行文本分类，参考paper 2.

第1为《Enriching Word Vectors with Subword Information》：使用subword的信息来增强词向量。

对于常规的一些词向量模型，它们将词汇表中每个词表示成一个不同的向量，在训练中会忽略词形。这对于一些大词汇量、许多罕见字、且词形丰富的语言来说（比如：Turkish语 或 Finnish语），是个很大限制，很难使用这些模型训练到较好的词级别(word-level)的向量。fastText是一种基于skip-gram模型的新扩展，它会使用subword的信息，将每个词被表示成一个字符级n-gram词袋(a bag of character n-grams)。每个向量表示与每个字符级n-gram相关联，而词(word)则可以看成是这些n-gram向量表示的求和(sum)。fastText在大语料上训练很快。

1.介绍

在NLP领域学习词的连续表示(continuous representations)已经有一段历史了(rumelhart et al., 1988)。这些表示通常来自于大型无标记语料来使用共现统计获得(Deerwester et al., 1990)。大部分工作称为“分布式语义（distributional semantics）”，已经研究了这些方法的属性（turney et al.,2010..）。在神经网络社区，Collobert和Weston(2008)提出了使用一个前馈网络来学习word embeddings，它通过基于一个词的左前两词和右后两词来预测中心词。最近，Mikolov(2013b)提出了一种简单的log-bilinear模型来高效学习大规模语料的连续表示。

通过一个不同的向量（distinct vector）来表示词汇表中的每个词，不需要参数共享。特别的，它们忽略了词的内部结构，对于词型丰富的语言（ morphologically rich languages）来说，比如Turkish语 和 Finnish语，这是个重要的限制。这些语言包含了许多罕见词，使得很难学习很好的word-level representations。在本paper中，我们提出了为character n-grams学习词表示，并将words表示成n-gram vectors的求和（sum）。我们的主要贡献是对Mikolov的skip-gram做了一个扩展，让它能解释subword information。我们在五种语言上（它们具有不同的词型）评估了该模型，展示了我们的方法的好处。

2.相关工作

形态学词表示（Morphological word representations）: 最近几年提出了不少方法，将形态学信息插入到词向量中。为了更好地建模罕见字，Alexandrescu和Kirchhoff（2006）引入了因子化的自然语言模型，其中词被表示成关于特征的集合。这些特征可以包含形态学信息，该技术被成功应用于形态学丰富的语言中，比如：Turkish（Sak 2010）。最近，一些相关的工作提出了不同复合函数来从词素（morphemes）生成词表示。这些不同的方法依赖于词的一个形态学解耦，但我们的方法不会。相似的，Chen(2015)介绍了一个方法来联合学习中文词和字符的embeddings。Soricut(2015)提出了将形态相似的词限制到具有相似表示。Soricut(2015)描述了一个方法来学习形态学转移的向量表示，允许通过应用规则来获取对未登陆词的表示。Cotterell(2015)则在形态学标注的数据上学习词表示。与我们的方法最接近的是Schutze(1993)，它通过SVD来学习字符级4-grams的表示，并通过对4-gram representations进行求和来生成词表示。

NLP的字符级特征（Character level features）：与我们工作相关的另一个研究领域是，NLP的字符级模型，它直接从字符序列中学习表示。这种模型的最高级方法是RNN，应用到语言建模（Mikolov 2012）、文本归一化（Chrupala, 2014）,、词性标注(Ling.2015)、parsing（Ballesterors.2015）。该模型的另一个家族是在字符上训练的CNN，它可以被应用到：词性标注（Santos,2014）、情感分析（dos Santos.2014）、文本分类（zhang.2015）、语言建模（Kim.2016）。(Sperr.2013)提出了基于受限波尔茨曼机的语言模型，其中词被编码成字符级别n-grams的一个集合。最后，在机器翻译中的最近工作也提出了使用subword units来获取罕见词的表示。（Sennrich.2016）

3.模型

本节中，我们提出了一个模型来学习representations来解释词形。

1.1 通用模型

先简单回顾下(Mikolov et al.,2013b)提出的continuous skip-gram模型，给定一个size=W的词汇表，其中词通过它的索引进行表示 \(w \in {1, ..., W}\)，目标是为每个词w学习一个向量表示。受分布式假设的启发，这些表示被训练来预测在一个给定词的上下文中出现的词。更正式的，给定一个大型训练语料，一个词序列: \(w_1, ..., w_T\)，它的skip-gram模型的目标函数是最大化log似然：

\[\sum_{t=1}^{T}\sum_{c \in {C_t}}log p(w_c|w_t)\]

其中，上下文\(C_t\)表示在词\(w_t\)周围词的索引集合，给定\(w_t\)，预测观察到\(w_c\)的概率。使用一个scoring函数s，可以将(word,context)pair映射到一个R空间的分值上:

\[p(w_c|w_t)=\frac{e^{s(w_t,w_c)}}{\sum_{j=1}^{W}e^{s(w_t,j)}}\]

该问题也可分解为多个二分类问题，目标是预测对应的\(w_c\)是否出现。对于位置t的词，以及上下文c，我们可以得到negative log-likelihood:

\[log(1+e^{-s(w_t,w_c)})+\sum_{n \in {N_{t,c}}} log(1+e^{s(w_t,n)})\]

其中\(N_{t,c}\)是一个从词汇表抽样出的负样本集合。logistic loss函数\(l:x \rightarrow log(1+e^{-x})\)，我们可以获得相应的目标函数：

\[\sum_{t=1}^{T}\sum_{c \in C_t}l(s(w_t,w_c))+\sum_{n \in N_{t,c}}l(-s(w_t,n))\]

\(w_t\)和上下文词\(w_c\)采用标量积：$ s(w_t,w_c)=u_{w_t}^{T}v_{w_c} $

1.2 Subword模型

由于每个词会使用一个不同的向量表示，skip-gram模型会忽视词的内部结构。在本部分，我们接着提出一个不同的scoring函数 s，将subword信息考虑进行。给定一个词w，我们定义在w上出现的n-gram集合为：$ G_w\subset{1,…,G} $.我们将一个向量表示\(z_g\)与每个n-gram g相关联。我们可以通过对这些n-gram的向量进行求和来表示一个词。我们获得一个scoring函数：

\[s(w,c)=\sum_{g \in {G_w}}z_g^Tv_c\]

对于词w，它的n-gram集合中总是包含着它，也可以为每个词学到一个向量表示。n-gram集合也是词汇表的一个超集(superset)。需要注意的是，对于共享相同的字序列(sequence of characters)的一个词和一个n-gram，会分配不同的向量给它们。例如，单词”as”和出现在词”paste”中的bigram “as”，会分配给不同的向量。这种简单模型允许在不同的词之间共享representations，从而对一些罕见词学到可靠的向量表示。

1.3 n-gram字典

上述模型很简单，并在\(G_w\)的定义上留下了设计选择的空间。在本paper中，我们采用了一个非常简单的scheme：所有n-gram的长度在[3,6]范围内. 可以使用n-gram的不同集合，例如前缀和后缀。同时，也添加一个特殊字符做为词的开头和结尾，这样就可以区分前缀和后缀。

为了限定模型的内存，使用一个hashing函数，将n-gram映射到[1,K]上。下面，我们使用的K等于200w。在结尾处，一个词可以被表示成在词典中的索引，以及它的n-gram的hash值。为了提升模型效率，我们不会使用n-gram来表示在词汇表中最频繁的P个词。P的选择需要权衡，值越小表示计算代价越高，但性能越好。当P=W时，我们的模型就是skip-gram模型。

1.4 试验

数据集和baseline：将新模型与word2vec的cbow和skip-gram相比较。数据集：5种语言的Wikipedia数据。三种size：小(50M tokens)，中(200M tokens)，完整。训练使用的epoch为：5.

其它参数：negative-sample: 5, rejection threshold: $ 10^{-4} $， window-size: 5, min-count:5.

  • 小数据集：100维, 中数据集：200维，完整数据集:300维.
  • skip-gram baseline learning-rate: 0.025; CBOW: 0.05, 新模型:0.05

对于英文语料，新模型的训练速度比skip-gram慢1.5倍。

人肉相似度判断

评估向量的质量：计算人肉判断（human judgement）与向量表示之间的cosine相似度之间的Spearman rank相关系数。

使用的数据集：

  • 英文：使用 WS353 (Finkelstein et al.2001)以及 RW (Luong et al.2013)
  • 德文：Gur65, Gur350,ZG222(Gurevych, 2005; Zesch and Gurevych, 2006）
  • 法文：RG65(Joubarne and Inkpen, 2011)
  • 西班牙文：WS353(Hassan and Mihalcea, 2009)

这些数据集中的一些词不会在训练数据中出现，对于CBOW方法和skip-gram baseline方法，我们不能获取这些词的向量表示。因此，我们决定排序包含这些词的pairs进行评测。我们在表1中上报了OOV比率。需要注意，我们的方法和baseline共享着相同的词汇表，因此，在相同训练集中的不同方法的结果是可以比较的。另一方面，不同训练语料上的结果是不可比较的，因为词汇表并不相同（具有不同的OOV rates）。

表1:

我们注意到，使用subword信息的新模型的效果在大多数数据集上的效果要好。我们也观察到，字符n-grams的效果，在德文上远比英文、西班牙文上好。一点也不令人吃惊，因为德文的字形更丰富。数据集越小，区别越重要。在RW英文数据集（罕见词数据集）上，新方法效要比baseline要好。

词类比任务（Word analogy）

使用Mikolov et al.(2013a)提出的：句法：syntactic(en-syn)，以及语义：semantic(en-sem)来评测，数据集使用cs-all（Svoboda and Brychcin (2016), for Czech, 捷克文）。一些包含words的questions不会在训练语料中出来，我们会排除这些questions，并上报oov rate。所有的方法在相同数据上进行训练，因此可比较。我们上报了表1中的不同模型。我们观察到，字形（morphological）信息对于syntactic任务有极大的帮助，新方法在en-syn上效果要比baseline好。相反的，它在小数据集的semantic任务上，效果有所下降。第二，对于捷克文，一个字形丰富的语言，使用subword信息可以很强地提升效果（对比baseline）。

2.高效文本分类tricks

Mikolov等在中提到了多种高效文本分类的tricks，并提出了fastText。它的分类速度快，又不失精准。在标准多核CPU上训练，超过10亿词上只需要10分钟左右；而对50w的句子，在312K个分类上进行分类，1分钟之内即可完成。听上去有些小激动。

对应paper的研究主要是基于：有名标签预测（namely tag prediction）， 情感分析（sentiment analysis），这两个领域做出的。

2.1 模型架构

baseline: 对于句子分类，简单又有效的baseline为：BOW向量 + 一个线性分类器(LR或SVM)。

线性分类器不会共享特征和分类间的参数。对于输出空间很大，但某些类上的训练样本很少的上下文上，这种方法的泛化能力受限。常用的解决方法是，将线性分类器分解为低秩矩阵（Schutze, 1992; Mikolov et al., 2013），或者使用多层神经网络(Collobert and Weston, 2008;Zhang et al., 2015)

图3展示了简单线性模型的秩约束（rank constraint）。第一个权重矩阵A，是一个在words上的look-up table。词向量被平均成一个文本向量，然后输入(feed)到一个线性分类器。文本向量是一个隐变量，它可以尽可能被复用。该架构与Mikolov提出的CBOW模型相似，中间的word被一个label所取代。我们使用softmax函数f来计算在预定义分类上的概率分布。对于N个文档的集合，目标是在这些类上最小化负log-likelihood：

\[-\frac{1}{N}\sum_{n=1}^{N}y_nlog(f(BAx_n))\]

其中xn是第n个文档的归一化的bag of features，yn是label，A和B是权重矩阵。该模型可以在多核CPU上使用SGD和一个线性衰减的learning_rate进行异步训练。

Hierarchical softmax

由于类的数目相当大，计算线性分类器的开销很大。计算复杂度是O(kh)，其中k是类的个数，h是文本向量的维度。为了在运行时提升，可以使用基于Huffman树的Hierarchical softmax，具体可以详见另一篇。在训练期，它的计算复杂度下降到O(hlog2(k)).

当在测试阶段时，当查询最可能的分类时，Hierarchical softmax也很有优势。每个节点与一个概率相关，该概率表示从根节点到该节点上路径的概率。如果节点的深度为l+1，相应的父节点为：n1, n2, …, nl，概率为：

\[P(n_{l+1})=\prod_{i=1}^{l}P(n_i)\]

这意味着一个节点的概率总是比它的父节点要低。搜索某一深度的该树时，以及在叶子间跟踪最大概率，允许我们抛弃掉所有小概率的分枝。实际上，我们观察到在测试时，复杂度降到O(hlog2(k))。该方法会进一步扩展到使用binary heap来计算top T个target，开销为O(log(T))。

N-gram features

BOW与词序无关，显式采用该顺序的计算开销通常很大。作为替代，我们使用bag-of-n-grams作为额外的特征来捕获一些关于局部词序的部分信息(partial information)。这在惯例上很有效（Wang and Manning, 2012).

我们使用hashing trick(Weinberger et al., 2009)，以及Mikolov et al.(2011)中相同的hashing function，以及10M的bins（如果我们只使用bigrams，否则可能100M），来维持一个快速的、内存高效的n-gram映射。

2.2 实验评测

fastText在两个不同的任务上进行评测。首先，会比较在情感分析（sentiment analysis）问题上的文本分类器。模型的实现可以使用Vowpal Wabbit library，但实际上使用的定制版本要比它快2-5x倍。

情感分析(Sentiment analysis)

数据集与baseline。使用8份由Zhang et al. (2015)提供的相同的数据集以及评测约定。使用Zhang et al. (2015)提供的n-gram和TF-IDF做为baselines。以及Zhang and LeCun (2015)提出的字符级卷积模型(char-CNN)， (Xiao and Cho, 2016)提出的字符级卷积RNN模型(char-CRNN)， Conneau et al. (2016)提出的极深卷积网络(VDCNN)。我们另外采用了Tang et al. (2015)的评测约定，上报了我们的方法以及他们的两种方法 (Conv-GRNN 和 LSTM-GRNN).

结果：使用10个隐单元，fastText迭代5轮(epochs)，learning_rate为{0.05, 0.1, 0.25, 0.5}。在该任务上，添加bigram信息可以提升1-4%的效果。整体的accuracy比char-CNN和char-CRNN稍好一些，比VDCNN略差些。注意，可以使用更多的n-gram可以（略微）提升accuracy，例如：使用trigrams，在Sogou语料上的效果可以提升到97.1%。最终，下图展示了我们的方法与Tang et al. (2015)的比较。在验证集上调整超参数，并观察到：使用n-gram为5-gram时，会达到最佳性能。不同于Tang的方法，fastText不会使用pre-trained word-embeddings，据说在accuarcy上可以有1%的提升。

在训练时间上： char-CNN 和 VDCNN在NVIDIA Tesla K40 GPU训练，fastText的模型在使用20线程的CPU上训练。对于char-CNN，使用最新的CUDA实现，可以有10x的速度提升。fastText则可以在1分钟内完成训练。。。

标签预测

数据集和baselines: 采用YFCC100M数据集(Thomee et al., 2016)，包含了100M的图片，带说明(captions)，标题(titles)，以及标签(tags)。我们只关注title和caption（不使用图片）来预测tags。将出现次数少于100次的words/tags进行移除，将数据分割成训练集／验证集／测试集。训练集包含大于9000W的样本(1.5B的tokens)，验证集93W的样本，测试集54W的样本。词汇表的size为30W左右，有31W左右是唯一的tags。我们发布了一个脚本来重新创建该数据集。

我们使用一个基于频率的方法作为baseline，来预测最频繁的标签。我们也比较了Tagspace(Weston et al.,2014)的方法，它与我们的模型相类似，但基于Wsabie model of Weston et al. (2011)。Tagspace模型使用卷积进行描述，我们使用它的线性版本作为baseline。

结果与训练时间：上表为fastText与baseline的比较。比较了fastText 5轮的迭代，与两种隐层size(50, 100)的Tagspace算法。两种模型的隐层size都是小值时，在accuracy上效果相似，但如果增加bigram，会有极大的提升。在测试时，tagspace需要为所有类计算分值，这会相当慢，当类数目很大时（本例中为：300K），fastText的inference则会很快！

参考

d0evi1 Reading time ~4 minutes

我们来看下2010提出的《Learning from Logged Implicit Exploration Data》，LinUCB的姐妹篇，具体方法如下：

摘要

对于在”contextual bandit”或”partially labeld” setting中（只有一个选中的action的值会被学到）使用非随机探索数据（nonrandom exploration data），我们提供了一个合理和一致的基础。在许多settings中的主要挑战是：探索策略（exploration policy）并非显式可知，“离线(offline)”数据会记录下。之前提出的解决方案是需要在学习期间对actions进行控制，记录下随机探索、或者以一种可重复的方式遗忘式(obliviously)的选择actions。这里提出的该技术会解除这些限制，学习一个policy，使得：在给定来自历史数据的features（随机化没有出现或者被记录）下选择actions。

介绍

考虑广告展示问题，一个搜索引擎公司会选择一个ad来展示给它的目标用户。当用户点击展示的ad时，会产生来自广告主付费的收益(Revenue)。该问题的经济特性，产生了许多著名的公司。

在讨论提出的方法前，我们将该问题公式化，接着解释为什么许多常见方法会失败。

上下文探索（contextual exploration）的warm-start问题：

假设：

  • X是一个任意输入空间
  • \(A=\lbrace 1, \cdots, k \rbrace\)是一个actions集合

那么，contextual bandit问题的一个实例，可以通过在tuples \((x, \vec{r})\)上的一个分布D来指定，其中：\(x \in X\)是一个输入，\(\vec{r} \in [0, 1]^k\)是一个关于rewards的向量。事件（Events）会以一个round-by-round的方式发生，其中每个round t有：

  • 1.抽取\((x, \vec{r}) \sim D\)，并公布x
  • 2.算法会选择一个action \(a \in A\)，可以是一个关于x和历史信息的函数
  • 3.公布action a的reward为\(r_a\)，但不会公布\(a'\neq a\)是\(r_{a'}\)

理解以下这点很重要：这不是一个标准的监督学习问题，因为其它actions \(a' \neq a\)的reward并没有透露（注：有点绕，即隐式的）。

在该setting中标准的目标是：在多轮交互上最大化rewards \(r_a\)的求和。为了这样做，使用之前记录的events来在第一轮交互上形成一个好的policy是很重要的。因而，这就是一个”warm start”问题。

正式的，给定一个形如\(S=(x, a, r_a)^*\)的dataset，它通过一个uncontrolled logging policy进行交互（interaction）生成，我们希望构建一个policy h来最大化（近似或逼近）下面的期望：

\[V^h := \underset{(x,r) \sim D}{E} [r_{h(x)}]\]

有许多方法尝试解决该问题的会失败：以下是一些尝试解决该问题的方法，但被证明是不适合的：

  • 1.监督学习：我们可以学到一个regressor \(s: X \times A \rightarrow [0,1]\)，它可以在观察到的events上基于action a和其它信息x，训练来预测reward。从该regressor，一个policy可以根据\(h(x)=argmax_{a \in A} s(x,a)\)来生成。该方法的缺点是，argmax会超出在训练数据中未包含的选择集合，因此不能被泛化。这可以通过一些极端情况进行验证。假设，有两个actions a和b，其中action a出现\(10^6\)次，action b出现\(10^2\)次。由于action b的次数比例只占\(10^{-4}\)，一个学习算法会强迫在预测\(r_a\)和\(r_b\)的期望值间做权衡，并压倒性地偏向于估计\(r_a\)，代价是精准估计\(r_b\)。然而，在应用上，action b可能会被argmax选中。当action b出现0次时，该问题会更糟糕
  • 2.Bandit方法：略
  • 3.Contextual Bandits：略
  • 4.Exploration Scavenging：略
    1. 倾向指数（Propensity Scores）, naively：当进行一个调查时，提问一个关于收入的问题，接着在不同收入级别上的回答者的比例，可以与基于参与该调查所选中的某些人的收入估计一个条件概率进行对比。给定该估计概率，结果可以被importance-weighted来估计在整个人口(population)上的平均调查结果。这里，该方法是有问题的，因为policy会做出决策，当记录数据是deterministic而非probabilistic。换句话说，对logging policy选择一个ad的概率的精准预测，意味着总是预测0或1, 这对于我们的目标是没用处的。尽管propensity scores的直接使用并不work，我们采用的该方法可以被认为是，对于一个propensity score的更好使用，下面会讨论。Lambert[4]提供了一个在互联网ad环境中关于propensity scoring的一个良好解释。

而我们的方法分为三个step:

  • 1.对于每个event \((x,a,r_a)\)，使用回归(regression)来估计logging policy会选择action a的概率(probability) 为\(\hat{\pi}(a \mid x)\)。这里，“probability”是随时间变化的——我们可以想像：在不同时间点，采用一个均匀随机的方式从policies集合（可能是deterministic）中抽取。
  • 2.对于每个event \((x,a,r_a)\)，根据\((x,a,r_a, \frac{1}{max \lbrace \hat{\pi}(a \mid x), \tau \rbrace})\)，创建一个synthetic controlled contextual bandit event，其中\(\tau > 0\)是一些参数。\(\frac{1} { max \lbrace \hat{\pi}(a \mid x), \tau \rbrace}\)这个量是一个importance weight，它指定了当前event对于训练是有多重要。需要明确的是，参数\(\tau\)对于数值稳定性很重要。
  • 3.应用一个offline contextual bandit算法到synthetic contextual bandit events集合上。在我们第二个实验结果的集合（4.2节）中，采用的argmax regressor的变种使用了两个关键修改之处：(a) 我们将argmax的范围限定在具有正概率的那些actions上 (b) 我们对events进行importance weight，以便训练过程会强调对于每个action平等的好估计。需要强调的是，在本paper中的理论分析可以应用于对于在contextual bandit events学习上的任何算法——我们选择该方法是因为它很容易在已存在方法上进行简单修改。

上述方法与前面提到的Propensity Score方法相似。相对它来说，我们使用一个不同的概率定义，当logging policy完全确定时该概率不必是0或1.

当考虑该方法时，会有三个关键问题：

  • 1.在当给定特征x时，logging policy会确定式(deterministically)选中一个action (ad) a，\(\hat{\pi}(a \mid x)\)意味着什么，？基本observation：一个policy如果在day 1会确定式选中action a、接着在day 2会确定选中action b，这可以被看成是：(当events数目在每天都相同时，并且events间是IID的），在action a和b间使用概率0.5进行随机化。因而，在logged events的时间跨度上，\(\hat{\pi}(a \mid x)\)是一个给定特征x关于action a被展示的期望频率的估计。第3节中，我们会展示该方法在期望上是合理的，它提供了关于new policy的值的一种无偏估计。
  • 2.在\(\hat{\pi}(a \mid x)\)上的客观误差（inevitable errors）是如何影响该过程的？结果表明它们有影响，取决于\(\tau\)。对于非常小的\(\tau\)值，\(\hat{\pi}(a \mid x)\)的估计必须极其精准来生成好的效果；而对于更大的值，会需要更小的accuracy。第3.1节会证明健壮性
  • 3.参数\(\tau\)是如何影响最终结果的？当在估计过程中创建一个bias时，结果表明该bias的形式是很轻微的并且相对合理的——基于条件x具有低频展示的actions具有一个under-estimated value。这与期望的对于没有频率的actions的限制是一致的。

2.问题设定和假设

假设：

  • \(\pi_1, \cdots, \pi_T\)是T个policies，

对于每个t，\(\pi_t\)是一个函数，它会将X的input映射到在A上的一个可能的deterministic分布。该学习算法会给定一个关于T个样本的dataset，每个样本形如：\((x,a,r_a) \in X \times A \times [0,1]\)（注：0,1为reward），其中：

  • \((x,r)\)按第1节所述的方式从D中抽取
  • action \(a \sim \pi_t(x)\)根据第t个policy被选中。

我们将该随机过程通过\((x,a,r_a) \sim (D, \pi_t(\cdot \mid x))\)来表示。相似的，与T个policies的交互会产生一个关于T条样本的序列S，我们表示为：\(S \sim (D, \pi_i(\cdot \mid x))_{i=1}^T\)。该learner不会给出关于\(\pi_t\)的先验知识。

offline policy estimator：

给定一个数据集：

\[S = \lbrace (x_t, a_t, r_{t,a_t}) \rbrace_{t=1}^T\]

…(1)

其中：\(\forall t, x_t \in X, a_t \in A, r_{t,a_t} \in [0, 1]\)

我们会生成一个predictor \(\hat{\pi}: X \times A \rightarrow [0,1]\)，接着使用它与一个阀值\(\tau \in [0,1]\)为一个policy h的value形成一个offline estimator。

正式的，给定一个new policy h: \(X \rightarrow A\)以及dataset S，将estimator 定义为：

\[\hat{V}_{\hat{\pi}}^h(S) = \frac{1}{|S|} \sum\limits_{(x,a,r) \in S} \frac{r_a I (h(x)=a)}{max \lbrace \hat{\pi}(a \mid x), \tau \rbrace}\]

…(2)

其中，\(I(\cdot)\)是指示函数（indicator function）。我们会使用符号\(\hat{V}_{\hat{\pi}}^h\)，因为没有歧义。\(\tau\)的目标是sum中个别项的上界，与之前的robust importance sampling方法相似。

3.理论成果

我们接着展示了我们的算法和主要理论成果。主要思想有两个：

  • 1.我们具有一个policy estimation阶段，其中我们估计未知的logging policy;
  • 2.我们具有一个policy optimization阶段，其中我们会使用我们估计的logging policy。

我们的主要结果，提供了一个泛化边界——解决estimation和optimization error对于total error贡献的问题。

logging policy \(\pi_t\)可能是确定的(deterministic)，这意味着：基于logging policy中的随机化的常用方法是不可用的。我们会在下面展示：当现实情况是IID条件、并且policy会随actions的不同而变化时，这是ok的。我们会有效使用算法中的随机化标准方法来替代现实中的随机。

一个基本断言（假设）是：在期望上的estimator等价于一个随机policy(stochastic policy)，定义如下：

\[\pi(a | x) = \underset{t \sim UNIF(1,\cdots,T)}{E} [\pi_t (a | x)]\]

…(3)

其中，\(UNIF(\cdots)\)表示均匀分布。

stochastic policy \(\pi\)会在T policies \(\pi_t\)上随机均匀选择一个action。我们的第一个结果是，当现实中根据\(\pi\)或者policies序列\(\pi_t\)进行选择actions时，我们的estimator的期望值与是相同的。尽管该结果和它的证明是简单的，它是本paper后面部分的基础。注意，policies \(\pi_t\)可以是任意的，但我们会假设，它们不依赖于用于evaluation的数据。该假设只对证明来说是必要的，可以在实际中放宽些，如4.1节。

定理3.1: 对于在T轮上做出相同抽取的任意contextual bandit问题D，对于任意可能的stochastic policies \(\pi_t(a \mid x)\)的序列(\(pi\)由上面求得)，以及对于任意的预测 \(\hat{\pi}\)，有：

\[E_{S \sim (D,\pi_i(\cdot|x))_{i=1}^T} \hat{V}_{\hat{\pi}}^h(S) = E_{(x,\vec{r}) \sim D, a \sim \pi(\cdot |x)} \frac{r_a I (h(x)=a)}{max \lbrace \hat{\pi}(a|x), \tau \rbrace}\]

…(4)

S就是上面指的dataset。

当在更简单、更标准的setting中（使用单一固定的(fixed) stochastic policy）使用T个policies时，该定理与我们的estimator的期望值相关。

3.1 Policy Estimation

在本节中，我们展示了如果\(\tau\)和\(\hat{\pi}\)的值选得合适，我们的estimator在评估new policies h时会足够精准。我们会进而使用前面章节的简化版，它展示了：我们可以将数据看成是由一个确定的stochastic policy \(\pi\)生成，比如：对于所有t来说，\(\pi_t = \pi\)。

对于一个给定的关于\(\pi\)的估计（estimate）： \(\hat{\pi}\)，我们通过下式来定义一个”regret”函数（\(reg:X \rightarrow [0,1]\)）：

\[reg(x)= \underset{a \in A}{max} [(\pi(a \mid x) - \hat{\pi}(a \mid x))^2]\]

…(5)

上面我们没有使用\(l_1\)和\(l_\infty\) loss，因为它们比\(l_2\) loss更难最小化。我们接下来的结果是：new estimator是一致的(consistent)。在接下来的理论声明中：

  • \(I(\cdot)\)表示了indicator function
  • \(\pi(a \mid x)\)是logging policy在输入x上选择action a的概率
  • \(\hat{V}_{\hat{\pi}}^h\)是由等式(2)基于参数\(\tau\)的定义

引理3.1：

假设：

  • \(\hat{\pi}\)是从X到在actions A分布上的任何函数
  • \(h: X \rightarrow A\)是任意的deterministic policy。
  • \(V^h(x) = E_{r \sim D(\cdot \mid x)}[r_{h(x)}]\)表示在input x上执行policy h的期望值

我们有：

\[E_x [ I(\pi(h(x) | x) \geq \tau) \cdot (V^h(x) - \frac{\sqrt{reg(x)}}{\tau}) ] \leq E[\hat{V}_{\hat{\pi}}^h] \leq V^h + E_x [ I(\pi(h(x) \mid x) \geq \tau) \cdot \frac{\sqrt{reg(x)}}{\tau} ]\]

注：在上式中，期望\(E[\hat{V}_{\hat{\pi}}^h]\)会在关于T个tuples \((x,a,r)\)的所有序列上计算，其中\((x,r) \sim D\)以及\(a \sim \pi(\cdot \mid x)\)

该引理限制了在我们的estimate \(V^h(x)\)上的bias。有两个bias来源：一个来自于在估计\(\pi(a \mid x)\)的\(\hat{\pi}(a \mid x)\)引入的error，另一个来自于阀值\(\tau\)。 对于第一个来源，我们根据squared loss分析了结果，因为限定在squared loss估计上的regret的抽样复杂度是可行的。

引理3.1展示了：一个policy h的估计\(\hat{V}_{\pi}^h\)的期望值（expected value），是关于policy h的真实值（true value）的一个下界的近似，其中该近似(approximation)主要归因于在estimate \(\hat{\pi}\)中的errors，下界(lower bound)主要归因于阀值\(\tau\)。当\(\hat{\pi} = \pi\)时，引理3.1可以简化成：

\[E_x [ I(\pi(h(x) | x) \geq \tau) \cdot V^h(x)] \leq E[\hat{V}_{\hat{\pi}}^h] \leq V^h\]

这样，有了一个关于\(\pi\)的完美predictor，estimator \(\hat{V}_{\hat{\pi}}^h\)的期望值（expected value）是一个在policy h的真实值（true value）（即\(V^h\)）上有保证的下界。然而，正如该断言的左侧建议，它可以是一个非常松的界，特别是当由h选中的action被\(\pi\)选中概率通常较小时。

引理3.1中\(1/\tau\)的依赖有点烦，但不可避免。考虑到bandit问题的一个实例：它具有一个input x，两个action \(a_1,a_2\)。

假设：对于一些positive \(\epsilon\)有\(\pi(a_1 \mid x) = \tau + \epsilon\)，\(h(x)=a_1\)就是我们正评估的policy。

进一步假设：rewards总是为1，并且\(\hat{\pi}(a_1 \mid x) = \tau\)。

那么，该estimator满足：

\[E[\hat{V}_{\hat{\pi}}^h]=\pi(a_1 \mid x) / \hat{\pi}(a_1 \mid x) = (\tau + \epsilon) / \tau\]

因而，在estimate中的期望值是：

\[E[\hat{V}_{\hat{\pi}}^h] - V^h = |(\tau+\epsilon)/\tau - 1| = \epsilon /\tau\]

其中：\(\hat{\pi}\)的regret为：

\[(\pi(a_1 \mid x) - \hat{\pi}(a_1 \mid x))^2 = \epsilon^2\]

3.2 Policy Optimization

之前章节证明，我们可以通过观察一个stochastic policy \(\pi\)来有效评估一个policy h，只要由h选中的actions在\(\pi\)下有足够的支持，特别的：对于所有inputs x来说，有\(\pi(h(x) \mid x) \geq \tau\)。然而，我们通常感兴趣的是：在观察到logged data后，从一个policies集合H中选择最好的policy h。再者，如第2节所述，logged data从T个固定的、可能是deterministic的policies \(\pi_1, \cdots, \pi_T\)来生成，而非单个stochastic policy。如第3节所述，我们通过等式3定义了stochastic policy \(\pi\)：

\[\pi(a | x) = E_{t \sim UNIF(1,\cdots,T)}[\pi_t(a | x)]\]

3.1节的结果可以应用到policy optimization问题上。然而，注意，该数据被看成是通过从一个关于T个policies \(\pi_i, \cdots, \pi_T\)的执行序列上抽取得到，而非从\(\pi\)上进行T个抽取得到。

接下来，我们展示了使用在H（在\(\pi\)下得到充分支持）中最好的hypothesis可能效果很好。（即使数据不是从\(\pi\)中生成的）

定理3.2

假设：

  • \(\hat{\pi}\)是任意从X到actions A分布的函数
  • H是任意deterministic policies的集合

定义：

  • \[\tilde{H}=\lbrace h \in H \mid \pi(h(x) \mid x) > \tau, \forall x \in X \rbrace\]
  • \[\tilde{h} = argmax_{h \in \tilde{H}} \lbrace V^h \rbrace\]

假设：

  • \(\hat{h} = argmax_{h \in H} \lbrace \hat{V}_{\hat{\pi}}^h \rbrace\)是最大化在等式(2)中定义的empirical value estimator的hypothesis。

接着，概率至少为\(1-\delta\)：

\[V^{\hat{h}} \geq V^{\tilde{h}} - \frac{2}{\tau} (\sqrt{E_x[reg(x)]} + \sqrt{\frac{ln(2|H|/\delta)}{2T}})\]

…(6)

其中，reg(x)是定义好的，对应于\(\pi\)，在等式(5)中

定理3.2的证明依赖于我们estimator的下界特性（引理3.1的左侧不等式）。换句话说，如果H包含了一个非常好的policy，它在\(\pi\)下得到较小支持，我们不能通过我们的estimator来检测它。换句话说，我们的estimation是安全的，我们从不会激烈地过度估计(overestimate)在H中任意policy的value。“underestimate, but don’t overestimate”的特性，对于应用optimization技术来说很重要，这意味着我们可以使用一个不受限的学习算法来生成一个warm start policy。

4.评估

我们在两个来自Yahoo!的真实数据集中评估了我们的方法。第一个数据集包含了均匀随机的曝光数据，该数据集中可以获取一个关于任意policy的无偏估计。该数据集接着用于验证我们的offline evaluator(2)的accuracy。第二个数据集接着会演示如何从非随机离线数据中去做policy optimization。

4.1 实验I

第一个实验涉及了在Yahoo!首页”Today Module”上的新闻推荐。对于每个用户访问，该模块会从一个小的候选池中（由编辑人工挑选）选出一个高质量的新闻文章进行展示。该池子会在任意时刻包含20篇左右的文章。我们的目标是：对highlighted出的该文章的点击率（ctr）最大化。该问题可以被建模成一个contextual bandit问题，其中，context包含了user和article的信息，arms对应于articles，一篇被显示文章如果被点击则reward是1, 否则为0. 因此，一个policy的值就刚好等于它的整体(overall)CTR。为了保护商业敏感信息，我们只提供了归一化CTR（nCTR: normalized CTR），它被定义成是：真实(true) CTR与一个random policy间的比值(ratio)。

我们的数据集被表示成\(D_0\)，它从Yahoo!首页的真实流量中收集，时间为2009年6月的两个星期。它包含了\(T=64.7M\) events，形式为三元组(x,a,r)：其中context x包含了user/article的特征，arm a从一个动态候选池A中随机均匀的方式选中，r是一个二元reward信号表示用户是否点击了a。由于actions的选择是随机的，我们有：\(\hat{\pi}(a \mid x) = \pi(a \mid x) \equiv 1/ \mid A \mid\)且\(reg(x) \equiv 0\)。因此，引理3.1意味着当提供\(\tau < 1/ \mid A \mid\)时\(E[\hat{V}_{\hat{\pi}}^h] = V^h\)。更进一步，Hoeffding不等式的简单应用，保证了对于任意的policy h，\(\hat{V}_{\hat{\pi}}^h\)以\(O(1/\sqrt{T})\)的速率向\(V^h\)集中，这在经验上是可被验证的。给定dataset的size大小，我们使用该dataset并在(2)中使用\(\hat{\pi}(a \mid x)=1/\mid A \mid)\)来计算\(\hat{V}_0 = \hat{V}_{\hat{\pi}}^h\)。结果\(\hat{V}_0\)接着被看成是”ground truth”，当使用非随机log data来替代时，可以评估offline evaluator (2)有多准确。

为了获取非随机的log data，我们使用offline bandit仿真过程来运行LinUCB算法，在我们的随机log data \(D_0\)上，对于被记录的events \((x,a,r)\)，UCB会在context x下选择arm a。注意，这里的\(\pi\)是一个deterministic学习算法，在不同的timesteps上对于相同的context可以选择不同的arms。我们称该被记录的events子集为 \(D_\pi\)。该recorded events集合与我们在真实的yahoo!首页的用户访问上运行LinUCB具有相同的分布。我们使用\(D_{\pi}\)作为非随机的log data，并进行了evaluation。

为了定义policy h进行evaluation，我们使用\(D_0\)跨所有用户来估计每篇article的整体CTR，接着h被定义成使用最高的估计得到的（estimated）CTR来选择该篇article。

我们接着使用offline evaluator (2)在\(D_\pi\)上对h进行评估。由于关于articles的A集合会随时间变化（新的文章会被增加，老文章被淘汰），\(\pi(a \mid x)\)会非常小，因为在两周时间中的文章量会很大，从而产生大的variance。为了解决该问题，我们将dataset \(D_\pi\)划分成子集，在每个子集中候选池仍是常数，接着使用ridge regression在特征x上为每个子集单独估计\(\pi(a \mid x)\)。我们注意到，这可以使用更多高级的条件概率估计技术。

图1绘出了：以ground truth \(\hat{V}_0\)为参照，\(\hat{V}_{\hat{\pi}}^h\)会随着\(\tau\)变化。正如所愿，随着\(\tau\)变得更大，我们的estimate可以变得更（向下）偏离(biased)。对于一个大范围的\(\tau\)值，我们的estimates是非常准确的，这意味着我们提出的方法是有意义的。作为对比，一个naive方法：假设\(\pi(a \mid x) = 1/\mid A \mid\)会给出一个非常差的估计。

图1:

对于十分小的\(\tau\)值，看起来是一个趋向该policy value的过度估计。这是因为，事实上一个正随机变量的负moments，通常到大于它对应期望的moments。

注意，我们使用的logging policy \(\pi\)，会与证明引理3.1所使用的一个假设相矛盾，也就是说，在timestep t上的exploration policy不会与一个更早的event相依赖。我们的offline evaluator在该setting中是准确的，这意味着该假设在实际中是可变宽松的。

4.2 实验II

在第二个实验中，我们会在warm-start问题上研究我们的方法。该数据集由Yahoo!提供，包含了在2008年一个月周期的数据。该数据由events日志(x,a,y)组成，其中，每个event表示了一个user访问了一个特定web页面x（它来自于一个大的web页集合X）。商业系统会从一个大的广告集合A中选择单个广告a放置到最前置、最重要的位置。它也会选择额外的广告来展示，但在我们的测试中会忽略。输出y是一个indicator，表示用户是否点击了该ad。

在该dataset中的ads数近似为880000个。训练数据集包含了3500w的events。test数据集包含了1900w的event，它们在训练集中的events之后发生。去重的web页数目为3400w。

我们基于当前页，训练一个policy h来选择一个广告，使得能最大化点击概率。为了学习，每个ad和page在内部都被表示成一个稀疏高维的feature vector。在page中或ad中出现的词(words)所对应于的features，可以通过词频进行加权。每个ad平均包含了30个ad features，每个page包含了大约50个page features。f的特征形式在它的输入(x,a)的特征上是线性的。（注：所使用的feature vector通常是page vector和ad vector的笛卡尔积）

被优化的指定policy，具有一个argmax形式：\(h(x)=argmax_{a \in C(x)} \lbrace f(x,a) \rbrace\)，在关于f(x,a)如何被训练的问题上与之前的方法不同。这里：\(f: X \times A \rightarrow [0,1]\)是一个regression函数，它被训练用来估计点击概率，并且\(C(x)=\lbrace a \in A \mid \hat{\pi}(a \mid x) > 0 \rbrace\)是一个可行ads的集合。

训练样本的形式为：(x,a,y)，其中y=1表示ad a在被展示到page x时被点击，否则为0。regressor f被选择用来逼近最小化weighted squared loss：\(\frac{(y-f(x,a))^2}{max \lbrace \hat{\pi}(a_t \mid x_t), \tau \rbrace}\)。使用SGD来最小化squared loss。

在评估期间，我们会计算在test data \((x_t, a_t, y_t)\)上的estimator：

\[\hat{V}_{\hat{\pi}}^h = \frac{1}{T} \sum\limits_{t=1}^T \frac{y_t I(h(x_t)=a_t)}{max \lbrace \hat{\pi}(a_t | x_t) , \tau \rbrace}\]

…(7)

如简介所述，该estimator是有偏的，因为使用了参数\(\tau > 0\)。如第3节分析所示，该bias通常会欠估计（underestimate）policy h的true value。

我们解释了使用不同的阀值\(\tau\)以及其它参数。结果如表2所示。

Interval列的计算使用Chernoff bound相对熵的形式，\(\delta=0.05\)持有假设：变量是IID的，（即：在我们的case中，用于estimator计算的样本）。注意，该计算有些复杂，因为变量的范围是\([0, 1/\tau]\)，而非常见的\([0, 1]\)。这可以通过乘以\(\tau\)来进行缩放，应用到bound上，接着将结果乘以\(1/\tau\)进行缩放。

“random” policy指的是，从feasible ads集合中随机选择：\(Random(x)=a \sim UNIF(C(X))\)，其中\(UNIF(\cdot)\)表示均匀分布。

“Naive” policy对应于理论上有缺陷的监督学习方法（在介绍中详细说过）。这种policy的evaluation相当昂贵，需要每个example每个ad进行一个evaluation，在此，test set的size被减小到一个click 8373个examples，这会减小结果的重要性。通过按时间先后顺序选择在test set中的第一个events（例如：在training set中与它们最相似的events），我们会将该结果偏向于naive policy。然而，naive policy会收到0 reward，这要比其它方法都要小很多。使用这种evaluation的一个可能担忧之处是，naive policy总是会找到那些不会被explored的good ads。一种快速验证表明：这是不正确的——naive argmax会简单地做出难以置信的选择。注意，我们只上报了evaluation against \(\tau=0.05\)，因为evaluation against \(\tau=0.01\)并不明显，尽管reward仍是0.

“Learned” policies会依赖于\(\tau\)。如定理3.2所示，随着\(\tau\)是减小，我们相竞争的hypotheses的有效集合是增加的，从而允许learned policy具有更好的效果。确实，当我们把\(\tau\)从0.05减小到0.01时，learned policy和random policy的估计会同时提升。

在test set上的empirical CTR是0.0213，要比最好的learned policy的estimate稍稍大些。然而，该数目并不直接可比，因为estimator在该policy的true value上提供了一个下界（这是由于一个非零的\(\tau\)会引入bias，因为任意部署的policy只会从可以展示的ads集合中选择，而非所有的ads集合（它们可能在某个时间点上未被展示过））。

empirical结果与理论方法大致是consistent的——它们提供了一个一致的关于policy value的最坏估计，不过它们具有足够动态的范围来区分learned polices vs. random policies，以及learned policies在更大空间(更小\(\tau\))vs.更小空间(更大\(\tau\))上，理论上不完善的naive方法 vs 合理的方法(在ads的explored空间上进行选择)。

5.结论

我们在理论上和经验上发表、调整、和评估了首个方法：使用来自controlled bias和estimation的logged data，解决在exploration的warm-start问题。该问题对于推荐内容给用户的互联网公司的应用是很有吸引力的。

然而，我们相信，这对于机器学习的其它应用领域也具有吸引力。例如，在reinforcement learning中，offline policy evaluation的标准方法会基于importance weighted samples[3,11]。这里发表的这个基本结果可以被应用到RL setting中，消除了这个必要条件：即显式(explicitly)一个选中action的概率，从而允许RL agent从来自其它agents的外部observations中进行学习。

参考

d0evi1 Reading time ~3 minutes

yahoo在2010年在《A contextual-bandit approach to personalized news article recommendation》中介绍了contextual bandit算法。

2.公式&相关工作

在本节，我们定义了K-armed contextual bandit问题，作为示例，展示了如何用它来建模个性化新闻推荐问题。

2.1 Multi-armed Bandit公式

个性化新闻推荐的问题可以天然建模成：带context信息的multi-armded bandit问题。根据[18]，我们称之为”contextual bandit”。正式的，一个contextual-bandit算法A会以离散方式处理实验(trials) t=1,2,3,…，在试验t上，有：

  • 1.该算法会观察当前用户\(u_t\)和一个关于arms或actions的\(A_t\)集合，以及对于arm \(a \in A_t\)的它们的特征向量(feature vectors) \(x_{t,a}\)。 vector \(x_{t,a}\)会同时总结用户\(u_t\)和arm a的信息，被称为context。
  • 2.基于在之前实验中的已观察收益(observed payoffs)，算法A会选择一个arm \(a_t \in A_t\)，并得到新的收益(payoffs): \(r_{t,a_t}\)，它的期望取决于user \(u_t\)和arm \(a_t\)两者
  • 3.算法接着使用新的observation \((x_{t,a_t}, a_t, r_{t,a_t})\)提升它的arm-selection策略。这里需要重点强调的是：对于未选中的arms \(a \neq a_t\)，此处没有观察到feedback（也就是：payoff \(r_{t,a}\)）。

上述过程中，算法A的total T-trial payoff被定义成：\(\sum_{t=1}^T r_{t,a_t}\)。相似的，我们将它的最优期望定义为：\(E[\sum_{t=1}^T r_{t,a_t^*}]\)，其中\(a_t^*\)是在实验t中具有最大期望payoff的arm。我们的目标是：设计一个算法A以便total payoff期望最大化。也相当于：我们会发现一个算法，以便对应各最优的arm-selection策略的regret最小化。这里，T-trail regret \(R_A(T)\)被定义为：

\[R_A(T) \equiv E[\sum\limits_{t=1}^T r_{t,a_t^*}] - E[\sum\limits_{t=1}^T r_{t,a_t}]\]

…(1)

一般的contextual bandit问题的一个重要特例是：著名的K-armed bandit，其中:

  • (i) arm set \(A_t\)保持不变，对于所有t都包含K个arms
  • (ii) user \(u_t\)（或者相等的，context \(x_{t,1}, \cdots, x_{t,K}\)）对于所有t都相同

因此，在每个实验中的arm set和contexts两者都是常数，对于一个bandit算法来说没啥区别，因此我们可以将该类型的bandit称为是一个context-free bandit。

在文章推荐的场景中（context），我们将池子中的文章(articles)看成是arms。当一篇曝光的文章被点击时，会带来一个等于1的payoff；否则payoff为0。有了关于payoff的该定义，一篇文章的期望(expected)payoff就是它的点击率（ctr），使用最大CTR来选择一篇文章等价于从最大化用户点击数目的期望，这与在我们的bandit公式中最大化总期望payoff（total expected payoff）相同。

再者，在网络服务中，我们通常会访问用户信息，它们被用于推断一个用户的兴趣，并用来选择他可能感兴趣的新闻文章。例如，对于一个男青年来说，他很可能对iPod产品的文章感兴趣，而非对退休计划的文章感兴趣。因此，我们会通过一个可以密切描述它们的关于信息特征的集合来“总结(summarize)”用户(users)和文章(articles)。通过这样做，一个bandit算法可以从一个 文章/用户 泛化(generalize) CTR信息给另一个文章/用户，并能学到更快地选择好的文章，特别是对于新用户和新文章。

2.2 已存在的Bandit算法

bandit problems的基本挑战是，需要对exploration和exploitation做平衡。为了最小化等式(1)中的regret（越小表示两者越接近），一个算法A会利用（exploits）它的过往经验来选择看起来最好的arm。另一方面，看起来最优的arm可能在实际上是次优的，因为在算法A的知识(knowledge)中是不精准的（imprecision）。为了避免这种不希望的情况，算法A必须通过实际选择看起来次优的arms来进行explore，以便收集关于它们的更多信息（在bandit过程中的step 3在之前的章节已定义）。Exploration可以增加short-term regret，因为会选到一些次优的arms。然而，获得关于arms的平均payoffs信息（例如：exploration）可以重新定义(refine)算法A的arms payoffs，从而减小long-term regret。通常，即不会存在一个纯粹的exploring，也不会存在一个纯粹的exploiting算法，需要对两者做平衡。

context-free K-armed bandit问题已经被统计学家研究过许多。一种最简单和最直接的算法是ε-greedy。在每个实验t中，该算法会首先估计每个arm a的平均payoff \(\hat{\mu}_{t,a}\)。接着使用概率\(1 - e\)来选择greedy arm（例如：具有最高payoff估计的arm）；使用概率e来选择一个random arm。在极限上，每个arm会尝试无限次，以便payoff估计\(\hat{\mu_{t,a}}\)会收敛到具有概率为1的真值(true value)\(\mu_a\)。另外，通过对e进行适当的衰减(decaying)，每一step的regret \(R_A(T)/T\)会收敛到0, 概率为1.

对比于ε-greedy所采用的无向导(unguided)的exploration策略，另一类算法通常被称为UCB算法（upper confidence bound算法），它使用一个更聪明的方式来对E&E进行平衡。特别的，在实验t中，这些算法会同时估计：每个arm a的平均payoff \(\hat{\mu}_{t,a}\)、以及一个相应的置信区间\(c_{t,a}\)，以便\(\mid \hat{\mu}_{t,a} - \mu_a\mid < c_{t,a}\)具有较高的概率。它们接着选接arm来达到一个最高的上限置信边界(UCB)：\(a_t = argmax_a (\hat{\mu}_{t,a} + c_{t,a})\)。由于合理地定义了置信区间，这样的算法具有一个较小的total T-trail regret，它是trials T的总数的log倍，看起来是最优的。

而context-free K-armed bandits最近被广泛研究，最通用的contextual bandit问题仍然充满挑战。EXP4算法[8]使用指数加权技术来达到一个\(\hat{O}(\sqrt{T})\)的regret，但计算复杂度是特征数的指数倍。另一个常用的contextual bandit算法是epoch-greedy算法[18]，它与使用shrinking ε的ε-greedy相似。该算法计算更高效，给定一个oracle optimizer，但具有更弱的regret guarantee：\(O(T^{2/3})\)。

具有更强regret guarantees的算法可以在关于bandit的许多建模假设下被设计。假设一个arm的期望payoff在它的特征中是线性的，Auer[6]描述了LinRel算法，它本质上是一种UCB-type方法，并展示了它的变种之一具有一个regret：\(\hat{O}(\sqrt{T})\)，比其它算法有极大提升。

最终，我们注意到，存在另一种基于Bayes rule的bandit算法，比如：Gittins index方法。由于合理定义了先验分布，Bayesian方法具有良好的效果。这些方法需要大量离线工程来获得较好的先验模型.

3.算法

对于context-free bandit算法，给定了渐定最优性（asymptotic optimality）以及较强的regret bound UCB方法；我们可以为contextual bandit问题尝试设计相似的算法。给定关于payoff函数的参数形式，存在许多方法来从数据中估计参数的置信区间，从而我们可以计算估计后的arm payoff的一个UCB。然而，通常这样的方法代价高。

在该工作中，我们展示了：当payoff模型是线性时，一个置信区间可以以closed form的形式高效计算，我们称该算法为LinUCB。出于表述(exposition)的需要，我们首先描述了disjoint线性模型的更简单形式，接着将在3.2节中考虑hybird模型的一般形式。我们注意到：LinUCB是一个通用的contextual bandit算法，它可以应用到其它应用中，而非个性化新闻推荐上。

3.1 不相交(disjoint)线性模型的LinUCB

使用2.1节的概念，我们假设：一个arm a的期望payoff在d维特征\(x_{t,a}\)上是线性的，它具有一些未知系数向量(coefficient vector)\(\theta_a^*\)；对于所有t：

\[E[r_{t,a} | X_{t,a}] = X_{t,a}^T \theta_a^*\]

…(2)

该模型称为disjoint的原因是：不同arms间的参数不共享(每个arm各有一组权重，与d维特征存在加权关系得到期望payoff)。假设：

  • \(D_a\)是在实验t上的一个m x d维的设计矩阵(design matrix)，它的行对应于m个训练输入（例如：对于文章a，之前已经观察到的m个contexts）
  • \(c_a \in R^m\)是相应的响应向量(corresponding response vector) （例如：相应的m个 点击/未点击 user feedback） (注：paper写的是\(b_a\)而非\(c_a\)，应该是笔误)

我们将岭回归（ridge regression）应用到训练数据\((D_a, c_a)\)上，给定了系数的一个估计（即伪逆）：

\[\hat{\theta}_a = (D_a^T D_a + I_d)^{-1} D_a^T c_a\]

…(3)

其中：\(I_d\)是d x d的identity matrix。当在\(c_a\)中的元素（components）与\(D_a\)中相应行是条件独立时，它至少具有\(1 - \delta\)的概率：

\[| x_{t,a}^T \hat{\theta}_a - E[r_{t,a} | x_{t,a}] | \leq \alpha \sqrt{x_{t,a}^T (D_a^T D_a + I_d)^{-1} x_{t,a}}\]

…(4)

对于任意的\(\delta > 0\)以及\(x_{t,a} \in R^d\)，其中\(\alpha = 1 + \sqrt{ln(2/\delta) / 2}\)是一个常数。换句话说，上述不等式为arm a的期望payoff给出了一个合理的紧凑的UCB，从中生成一个UCB-type arm-selection策略，在每个实验t上，选择：

\[a_t \equiv argmax_{a \in A_t} (x_{t,a}^T \hat{\theta}_a + \alpha \sqrt{x_{t,a}^T A_a^{-1} x_{t-a}})\]

…(5)

其中：\(A_a \equiv D_a^T D_a + I_d\)。

在等式(4)中的置信区间可以受其它准则的启发。例如， ridge regression可以被解释成一个Bayesian点估计，其中系数向量的后验分布被表示成：\(p(\theta_a)\)，它是一个关于(mean=\(\hat{\theta}_a, covariance=A_a^{-1})\))的高斯分布。给定当前模型，期望payoff \(x_{t,a}^T \theta_a^*\)的预测变量被评估成\(x_{t,a}^T A_a^{-1} x_{t,a}\)，接着\(\sqrt{x_{t,a}^T A_a^{-1} x_{t,a}}\)变为标准差。接着，在信息论中，\(p(\theta_a)\)的微分熵被定义成：\(-\frac{1}{2} ln((2 \pi)^d det A_a)\)。当\(p(\theta_a)\)的熵由new point \(x_{t,a}\)的杂质(inclusion)更新时，接着变为：\(-\frac{1}{2} ln((2 \pi)^d det (A_a + x_{t,a} x_{t,a}^T))\)。模型后验的熵减（entropy reduction）是\(\frac{1}{2} ln(1 + x_{t,a}^T A_a^{-1} x_{t,a}\)。该质量（quatity）通常被用于估计来自\(x_{t,a}\)的模型提升。因此，在等式(5)中的arm selection的准则可以被认为是在payoff估计和model uncertianty reduction间的一个额外的trade-off。

算法1

算法1给出了一个关于整个LinUCB算法的详细描述。只有输入参数\(\alpha\)。注意，在等式(4)中给定的\(\alpha\)值在一些应用中会比较大，因此对这些参数最优化实际可能会产生更高的total payoffs。不同于所有的UCB方法，LinUCB总是会选择具有最高UCB的arm（正如等式(5)中）.

该算法具有一些良好的性质。

  • 1.它的计算复杂度对于arms的数量来说是线性的，对于特征数目最多是三次方。为了减少计算量，我们可以在每一step中更新\(A_{a_t}\)，周期性计算和缓存\(Q_a \equiv A_a^{-1}\)，而非实时。
  • 2.该算法对于一个动态的arm set来说工作良好，仍能高效运行，只要\(A_t\)的size不能太大。该case在许多应用中是true的。例如，在新闻文章推荐中，编辑会从一个池子中添加/移除文章，池子的size本质上是个常数。
  • 3.尽管不会该paper的重点，我们仍会采用[6]的分析来展示：如果arm set \(A_t\)是确定的，包含了K个arms，接着置信区间（比如：等式(4)的右手边）会随着越来越多的数据快速减小，接着证明\(\hat{O}(\sqrt{KdT})\)的强regret bound，匹配满足等式(2)的bandits的state-of-art结果[6]。这些理论结果预示着算法的基础牢固以及高效性。

最后，我们注意到，在该假设下，输入特征\(x_{t,a}\)会从一个正态分布中i.i.d的方式抽出，Pavlidis[22]提出了一个相似的算法，它使用一个最小二乘解\(\hat{\theta_a}\)来替代我们的ridge-regression解 （等式(3)中的\(\hat{\theta_a}\)）来计算UCB。然而，我们的方法更通用，当输入特征不稳定时仍合量(valid)。更重要的是，我们在下一节中讨论了，如何将算法1展开到一个更有意思的case。

3.2 Hybrid线性模型的LinUCB

算法1计算了矩阵的逆，\(D_a^T D_a + I_d\)（或者：\(D_a^T D_a\)），其中\(D_a\)是design matrix，它的行对应于训练数据中的特征。所有arms的这些矩阵具有固定维度d x d，可以高效地进行增量更新。另外，它们的逆（ inverses）可以通过算法1的disjoint参数很方便地进行计算：在等式(3)中的解\(\hat{\theta}_a\)不会被其它arms的数据数据所影响，因为计算是独立的。我们现在考虑使用hybrid模型的case。

在许多应用中（包含新闻推荐），除了arm-specific情况之外，所有arms都会使用共享特征。例如，在新闻文章推荐中，一个用户可能只偏爱于政治文章，因而可以提供这样的一种机制。因此，同时具有共享和非共享components的特征非常有用。正式的，我们采用如下的hybrid模型来额外添加其它的线性项到等式(2)的右侧：

\[E[r_{t,a} | x_{t,a}] = z_{t,a}^T \beta^* + x_{t,a}^T \theta_a^*\]

…(6)

其中：

  • \(z_{t,a} \in R^k\)是当前user/article组合的特征
  • \(\beta^*\)是一个未知的系数向量(coefficient vector)，它对所有arms是共享的

该模型是hybrid的，广义上系数\(\beta^*\)的一些参数是会被所有arms共享的，而其它\(\theta_a^*\)则不会。

算法2

对于hybrid模型，我们不再使用算法1作为多个不相互独立的arms的置信区间，因为它们共享特征。幸运的是，有一种高效方式来计算一个UCB，与之前章节相似。该导数(derivation)严重依赖于块矩阵转置技术。由于空间限制，我们给出了算法2的伪码（第5行和第12行会计算关于系数的redge-regression的解，第13行会计算置信区间），详细导数见完整paper。这里我们只指出了重要的事实：

  • 1.由于算法中使用的构建块（\(A_0, b_0, A_a, B_a, b_a\)）具有固定的维度，可以进行增量更新，该算法计算十分高效。
  • 2.另外，与arms相关联的质量（quatities）在\(A_t\)中并不存在，因而在计算量上不再相关。
  • 3.最后，我们也周期性地计算和缓存了逆(\(A_0^{-1}\)和\(A_a^{-1}\))，而非在每个实验尾部来将每个实验的计算复杂度\(O(d^2 + k^2)\)。

4.评估技术

对比在一些标准监督机器学习setting，contextual bandit setting的评估是相当难的。我们的目标是评估一个bandit算法\(\pi\)的效果，也就是说，在每个time step上选择一个arm的规则会基于之前的交互来完成（比如：上述算法描述的）。由于该问题的天然相交特性，看起来只能在真实数据上运行该算法。然而，实际上，该方法可能不可行，因为严重的logistical挑战。更确切的说，我们只具有离线数据提供，它们使用一整个不同的日志策略（logging policy）在之前收集得到。由于payoffs只会被logging policy选中的arms所观察到，它们很可能通常与被评估的算法\(\pi\)所选中的不同。该评估问题可以看成是在增强学习中“off-policy evaluation problem”的一个特例。

一种解决方案是：构建一个模拟器（simulator）来从日志数据中建模bandit过程，接着使用该simulator来估计\(\pi\)。然而，modeling step会引入在simulator中的bias，使它很难满足这种simulator-based评估方法的可靠性。作为对比，我们提出了一种方法：它很容易实现，基于日志数据，并且是无偏的（unbiased）。

在该节中，我们描述了一种被证明可靠的技术来执行这样的评估。假设，单独事件是i.i.d的，被用于收集日志数据的logging policy会在每个time step上随机均匀的方式选中任一arm。尽管我们会忽略细节，后面的假设会变弱，以便任何随机的logging policy会被允许，我们的解决方案可以根据使用rejection sampling来进行修改，但代价是降低了效果。

更精确的是，我们假设：一些已知分布D，从中进行i.i.d.抽取tuples：\((x_1, \cdots, x_K, r_1, \cdots, r_K)\)，每个tuple包含了已观察到的特征向量和对于所有arms的hidden payoffs。我们也可以访问关于日志事件的大序列，它从logging policy的交互产生。每个这样的事件包含了：context vectors：\(x_1, \cdots, x_K\)、一个被选中的arm a、以及产生的observed payoff \(r_a\)。关键的，只有payoff \(r_a\)被随机均匀选中的单个arm a所观察到。出于简洁性，我们将日志事件序列看成是一个无限长的流；然而，我们也在实际有限数目的事件（评估方法所需）上给出了显式的边界。

我们的目标是：使用该数据来评估一个bandit算法\(\pi\)。正式的，\(\pi\)是一个mapping（可能随机化）来在时间t上基于历史行为\(h_{t-1}\)和t-1个之前的事件，结合上当前的context vectors \(x_{t1}, \cdots, x_{tK}\)来选择arm \(a_t\)。

算法3

我们提出的policy评估器如算法3所示。该方法会将输入一个policy \(\pi\)以及一个基于该评估之上的关于“good”事件（event）T的期望值。我们接着沿着日志事件的流（stream）一个接一个地前行。给定当前历史\(h_{t-1}\)，有：

  • 如果policy \(\pi\)选择了与logging policy所选arm的相同的arm a，那么：event仍被添加到历史中，total payoff \(R_t\)会被更新。
  • 如果policy \(\pi\)选择了与logging policy所选arm所不同的arm，那么：event会被完全忽略，该算法会处理下一event，在该state上无需任何变化。

注意，由于logging policy会随机均匀地选择每个arm，被该算法所维持(retain)的每个event会具有1/K的概率，相互独立。这意味着这些events仍保留与被D选中的相同的分布。作为结果，我们可以证明两种方式是相等价的：第一种采用来自D的T个真实events对policy进行评估，第二种会在日志事件流上使用policy evaluator进行评估。

定理1: 对于contexts的所有分布D、所有policies \(\pi\)、所有T、以及所有事件序列\(h_T\)，有：

\[\underset{policy\_evalutar(\pi,S)}{Pr} (h_T) = Pr_{\pi, D} (h_T)\]

其中S是从一个均匀随机的logging policy和D中i.i.d.的方式抽取出的一个事件流。另外，从流中获得的事件的期望数目（会收集到一个长度为T的历史\(h_t\)）是KT。

该定理说明，每一个在真实世界中的历史\(h_T\)与在policy evaluator中具有相同的概率（比如：返回由算法3的平均payoff \(R_T / T\)），即：算法\(\pi\)的值无偏估计。另外，该定理表明：KT个日志事件对于维持一个size=T的抽样来说是必需的。

证明：该证明通过引入\(t=1, \cdots, T\)，以一个t=0时在所有评估方法下概率为1的空历史作为base case开始。在归纳法下，假设我们对于所有t-1:

\[\underset{policy\_evaluator(\pi,S)}{Pr} (h_{t-1}) = Pr_{\pi,D}(h_{t-1})\]

并希望证明对于任意历史\(h_t\)都有相同的声明。由于该数据是i.i.d.的，任何在policy中的随机化（randomization）与世界中的随机化相互独立，我们只需要证明在基于历史\(h_{t-1}\)条件，在第t个事件(event)上的分布与每个过程（process）相同。换句话说，我们必须展示：

\[\underset{Policy\_evaluator(\pi,S)}{Pr} ((x_{t,1}, \cdots, x_{t,K}, a, r_{t,a}) | h_{t-1}) = Pr_D(x_{t,1}, \cdots, x_{t,K}, r_{t,a}) Pr_{\pi(h_{t-1})} (a | x_{t,1}, \cdots, x_{t,K})\]

由于该arm a在logging policy中被随机均匀选中，对于任意policy、任意history、任意features、以及任意arm，policy evaluator退出内循环的概率是相同的, 这意味着对于最近的event，它的概率为\(Pr_D(x_{t,1}, \cdots, x_{t,K}, r_{t,a})\)。相似的，由于该policy \(\pi\)在arms上的分布与基于history \(h_{t-1}\)和features \((x_{t,1}, \cdots, x_{t,K})\)的条件是相互独立的，arm a的概率就是\(Pr_{\pi(h_{t-1}} (a \mid x_{t,1}, \cdots, x_{t,K})\)。

最后，由于来自该stream的每个event仍会保持概率1/K，需要保持T个event的期望数值是KT。

5.实验

在本节中，我们在一个真实应用中使用第4节中的offline评估法来验证提出的LinUCB的能力(capacity)。我们在Yahoo! Today模块上开始该问题setting的介绍，接着描述在实验中所使用的user/item属性。最终，我们定义了performance metrics，并上报了与一些标准(contextual)bandit算法的实验比较结果。

5.1 Yahoo! Today模块

图1

Today模块是在Yahoo! Front Page（流量最大）的最显著位置的panel，详见图1. 在Today Module上缺省的”Featured” tab会对高质量文章（主要新闻）的1/4进行高亮（highlight）, 而4篇文章通过一个小时级别更新的由人工编辑的文章池中进行选择。如图1所示，在底部存在4篇文章，索引为F1-F4. 每篇文章由一张小图和一个标题进行表示。其中之一会在story位置进行着重展示，它由一个大图、一个标题、一个简介、以及相关链接进行着重(featured)。缺省的，在F1的文章会在story位置强调。一个用户可以点击在story位置上的highlightd文章，如果她对文章感兴趣会读取更多的详情。event被看成是一次story click。为了吸引访问者的注意力，我们想根据个人的兴趣对提供的文章进行排序，对于每个visitor在story位置上highlight最有吸引力的文章。

5.2 实验设置

这部分会详细描述实验设置，包括：数据收集，特征构建，效果评估，算法比较。

5.2.1 数据收集

我们收集了在2009年五朋的一个随机bucket上的events。在该bucket上的用户会被随机选中，每个visiting view都有一定的概率。在该bucket中，文章会从池子中随机被选中来服务给用户。为了避免在footer位置处的曝光偏差（exposure bias），我们只关注在story位置处的F1文章的用户交互。每个用户交互event包含了三个部分：

  • (i) 提供给用户随机选中的文章
  • (ii) user/article信息
  • (iii) 在story位置处用户是否对该文章有点击

第4部分展示了这些随机events可以被用于依赖估计一个bandit算法的期望payoff。

在5月1号的随机bucket中有4700W的events。我们使用该天的events（称为：tuning data）来进行模型验以决定最优的参数来对比每个bandit算法。接着，我们使用调过的参数在一周的event-set（称为：evaluation data，从5月03-09号）上运行这些算法，它包含了3600w的events。

5.2.2 特征构建

我们现在描述user/article的特征构建。对于disjoint和hybrid模型分别有两个集合的特征，用于测试在第3节中LinUCB的两种形式，以验证我们的猜想：hybrid模型可以提升学习速率。

我们从原始user features开始，它们通过“support”被选中。一个feature的support指的是，用户具有该feature的比例。为了减少数据中的噪声，我们只选取了具有较高值support的features。特别的，当它的support至少为0.1时，我们才使用该feature。接着，每个user最初通过一个在1000个类别型特征(categorical components)上的原始特征向量（raw feature vector）进行表示，包含了：

  • (i) 人口属性信息(demographic information)：性别（2个分类）、年龄（离散化成10个分段）
  • (ii)地理特征（geographic features）：包含世界范围和美国的大约200个大都市；
  • (iii)行为类别(behavioral categories)：大约1000个二分类别（binary categories），它们总结了用户在Yahoo!内的消费历史。

除了这些特征之外，不会使用其它信息来标识一个用户。

相似的，每篇文章通过一个原始的feature vector进行表示，它以相同的方式构建了100个类别型特征。这些特征包括：

  • (i) URL类别：数十个分类，从文章资源的URL中推断得到
  • (ii) editor类别：数十个主题，由人工编辑打标签总结得到

我们使用一个之前的过程[12]来将类别型user/article特征编码成二分类向量（binary vectors），接着将每个feature vector归一化成单位长度（unit length）。我们也会使用一个值为1的常数特征来增加每个feature vector。现在，每个article和user都可以分别表示成一个关于83个条目和1193个条目的特征向量。

为了进一步减小维度，以及捕获在这些原始特征中的非线性关系，我们会基于在2008年九月收集的随机曝光数据来执行关联分布。根据之前的降维方法[13]，我们将用户特征投影到文章类目上，接着使用相似偏好将用户聚类成分组(groups)。更特别的：

  • 我们首先通过原始的user/article features，来使用LR来拟合一个关于点击率（click probability）的bilinear model，以便\(\phi_u^T W \phi_a\)来近似用户u点击文章a的概率，其中\(\phi_u\)和\(\phi_a\)是相应的feature vectors，W是由LR最优化得到的权重矩阵。
  • 通过计算\(\psi_u = \phi_u^T W\)，原始的user features接着被投影到一个induced space上。这里，用于user u，在\(\psi_u\)的第i个元素可以被解释成：用户喜欢文章的第i个类别的度（degree）。在induced的\(\psi_u\) space中使用K-means算法将用户聚类成5个clusters。
  • 最终的user feature是一个6向量（six-vector）：5个条目对应于在这5个clusters中的成员（使用一个Gaussian kernel计算，接着归一化以便他们总和一致），第6个是一个常数特征1.

在实验t中，每篇文章a具有一个独立的6维特征\(x_{t,a}\)（包含一个常数特征1）。与一个user feature的外积（outer product）给出了6x6=36个特征，表示为\(z_{t,a} \in R^{36}\)，对应于等式(6)的共享特征，这样\((z_{t,a}, x_{t,a})\)可以被用于在hybrid线性模型中。注意，特征\(z_{t,a}\)包含了user-article交互信息，而\(x_{t,a}\)只包含了用户信息。

这里，我们故意使用5个用户／文章分组（users group），在分段分析中具有代表性[13]。使用一个相对小的feature space的另一个原因是，在在线服务中，存储和检索大量user/article信息在实际上代价高。

5.3 算法比较

我们的实验中评估的算法有三组：

I.不使用特征的算法

这对应于context-free K-armed bandit算法，它们会忽略所有contexts（例如：user/article信息）

  • random: random policy总是会以等概率的方式从池子中选中候选文章之一。该算法无需参数，不会一直学习
  • ε-greedy：在第2.2节所述，它会估计每篇文章的CTR；接着，它会选择具有概率e的一篇随机文章，接着选择具有概率1-e的最高CTR估计的文章。该policy只有一个参数e。
  • ucb: 如2.2节所述，policy会估计每篇文章的CTR，也会估计它的置信区间，总是会选择具有最高UCB的文章。特别的，根据UCB1[7]，我们会通过\(c_{t,a} = \frac{a}{\sqrt{n_{t,a}}}\)来计算一篇文章a的置信区间，其中\(n_{t,a}\)是在实验t之前a被选中的次数，\(\alpha>0\)是一个参数
  • omniscient(无所不知的): 这样的一个policy会从后见之明（from hindsight）达到最好的经验型的context-free CTR。它首先会从日志事件(logged events)中计算每篇文章的经验CTR，当使用相同的logged events评估时，接着总是选择具有最高经验CTR的文章。该算法无需参数，不需要学习。

II.热启动（warm start）算法

个性化服务的一种中间步骤。它的思想是，在文章的整个流量上的context-free CTR提供一种offline估计的特定用户的调整。该offset会为新内容对CTR估计的实始化，也称为：“warm start”。我们在2008九月的随机流量数据上，使用特征\(z_{t,a}\)重新训练了bilinear LR模型。选择原则接着变成context-free CTR估计与一个user-specific CTR adujstment的bilinear项的和。在训练中，CTR估计使用context-free ε-greedy，其中e=1.

  • ε-greedy(warm):
  • ucb(warm):

III.在线学习user-specific CTR的算法

参考

d0evi1 Reading time ~1 minute

0.介绍

Yoon Kim在《Convolutional Neural Networks for Sentence Classification》介绍了使用CNN来做句子分类的任务。下面基于对该paper的理解，简单地做个介绍：

1.模型架构

图1. 对于一个语句，使用双通道的模型架构

$ x_i \in R^k $ 为句子中第i个词的k维词向量。句子长度为n（不足补齐: pad），表示成：

\[x_{1:n} = x_1 \oplus x_2 \oplus x_3 ... \oplus x_n\]

… (1)

其中：

$ \oplus $为串联操作符(concatenation operator)。 $ x_{i:i+j} $ 表示 $ x_i $至$ x_{i+j} $的串联。

卷积（convolution）操作符涉及到一个过滤器（filter）： $ w \in R^{h \times k} $，它可以应用于一个含h个词的窗口，来生成一个新的特征。例如，可以由一个词窗口$ x_{i:i+h-1}$来生成一个特征$c_i$：

\[c_i = f(w \cdot x_{i:i+h-1} + b)\]

…(2)

这里 $ b \in R^{n-h+1} $是一个bias项，f是一个非线性函数（例如：假设函数tangent）。将filter应用在每个可能的句子中的词窗口：$ {x_{1:h}, x_{2:h+1},…,x_{n-h+1:n}} $来生成一个特征图（feature map）。

\[c = [c_1, c_2, ..., c_{n-h+1}]\]

…(3)

其中$ c \in R^{n-h+1}$，我们接着在该feature map上应用一个max-over-time pooling操作，并采用最大值$ \hat{c} = max \{ c \} $作为该指定filter相应的特征。该思路用来捕获最重要的特征——对于每个feature map取最大值得到。该pooling scheme天然就可以处理不同的句子长度。

我们接着描述该过程，通过从一个filter上抽取一个feature。该模型使用多个filters(具有不同的窗口size)来获得多个feature。这些特征构成了倒数第二层（penultimate layer），并被传到一个fully connected softmax layer，它的输出为在label上的概率分布。

在另一个模型变种中，我们试验了具有两个词向量的通道（channels）——一个保持static throughout training，另一个通过backpropagation进行 fine-tuned。在多通道的架构上，如图1所示，每个filter被应用于多个channel。被添加的结果用来计算等式(2)式中的$c_i$。该模型和单个channel的架构相似。

2.1 Regularization

对于Regularization，我们在倒数处二层（penultimate layer）使用dropout，使用一个关于权重向量的l2-norm的约束（constraint）。通过进行随机dropout， Dropout可以阻止隐单元的相互适应现象（co-adaptation）——这样，在前向传播（forward-backpropagation）期间将比例为p的隐单元置为0. 也就是说，给定倒数第二层（penultimate layer）：$ z = [\hat{c}_1, …, \hat{c}_m] $（注意：这里有m个filter），做为替换，不再使用：

\[y = w \cdot z + b\]

…(4)

对于在前向传播（forward propagation）中的输出单元y，dropout使用：

\[y = w \cdot (z \circ r) + b\]

…(5)

其中$ \circ $是element-wise乘法操作，$ r \in R^{m}$是一个关于Bernoulli随机变量的’masking’向量，它具有概率p的部分为1。梯度通过后向传播，只通过unmasked的单元。在测试时，学到的weight向量通过p进行归一化，例如：$ \hat{w} = pw $，其中$ \hat{w} $被用来（没有dropout）对未见过的句子（unseen sentences）进行打分。我们又额外增加权重向量的l2-norms约束，通过对w进行rescaling，使得：$ {||w ||}_{2}$，在经历一个梯度下降的step后，将永远$ {||w ||}_2 > s $。

数据集

  • MR: 电影评论(Movie Reviews)。分类检测正负语义。（Pang and Lee, 2005）
  • SST-1: Stanford Sentiment Treebank——MR的扩展，具有train/dev/test splits，提供了细粒度标签（very positive, positive, neutral, negative, very negative）。 Socher et al. (2013)
  • SST-2: 类似SST-1. 移除了neutral评论，增加了binary labels
  • Subj：Subjectivity数据集，分类任务：将句子分类成：subjective or objective。(Pang and Lee, 2004).
  • TREC: TREC question数据集——将一个question分类成6个问题类型（该问题是关于：person, location, numeric information, etc.） (Li and Roth, 2002)
  • CR： 多种商品的顾客评价(Customer reviews)。预测positive/negative 评论。(Hu and Liu, 2004).
  • MPQA：MPQA数据集的意见极性检测（Opinion polarity detection）。 (Wiebe et al., 2005).

3.1 超参数和训练

对于所有数据集，统一使用：

  • ReLU
  • filter window(h)为：3, 4, 5
  • 每个window具有100个feature map
  • dropout rate (p)为：0.5
  • l2 constraint (s)为：3
  • mini-batch size为：50

这些值的选择在 SST-2 dev set上通过grid search找到。

我们不执行任意的指定数据集的调整，而是在dev sets上做early-stopping。对于没有标签dev set的数据集，我们随机选对10%的训练数据作为dev set。训练过程通过在shuffled mini-batchs数据上，使用Adadelta update rule（Zeiler, 2012），以及SGD来完成。

3.2 Pre-trained词向量

从非监督神经语言模型中获取词向量进行初始化，这种方法很流行。我们使用word2vec对Google News的1000亿个词进行训练。这些向量具有300维，使用CBOW架构，不在pre-trained词向量中的词则随机初始化。

3.3 模型变种

  • CNN-rand: 作为baseline模型，所有的词都是随机初始化，接着在训练中进行修改。
  • CNN-static: 使用来自word2vec的pre-trained vector的model。所有的词（包括随机初始化的未登陆词）保持static，只有模型中的其它参数是通过学习得到。
  • CNN-non-static: 与上面的方法相似，但对于每个任务，pre-trained vectors都会进行微调（fine-tuned）。
  • CNN-multichannel: 模型具有两个词向量集合。每个向量集都看成是一个’channel’，每个filter都会作用于两个channel，但梯度的后向传播只通过其中一个channel进行。这里模型可以fine-tune一个向量集，让另一个保持static。两个channel都通过word2vec进行初始化

为了对上述变种vs.其它随机因子进行比较，我们消除了其它源的随机性——CV-fold任务，未登陆词向量的初始化，CNN参数的初始化——在每个数据集上对它们保持统一。

4.结果

表2: CNN模型vs.其它方法。其它方法详见paper解释.

结果如表2所示。baseline model是CNN-rand：全随机初始化词，表现并不理想。通过使用pre-trained vector，会获得效果的提升。使用CNN-static的效果很显著，比起其它更复杂的深度学习模型(使用pooling或parse tree等)，结果也有得一拼。这些结果说明了pre-trained vector很好、很通用（‘universal’）的feature extractors，并且可以跨数据集使用。对pre-trained vector进行微调（finetuning），可以为每个任务获得更进一步的提升（CNN-non-static）。

4.1 Multichannel vs. Single Channel Model

我们原先以为multichannel架构会阻止overfitting的发生（通过确保学到的vector与原先的值偏离太远），会比single channel效果更好，尤其是在小数据集的情况下。然而，结果参半，需要更进一步对fine-tuning过程进行正则化（regularizing）。例如，对于no-static部分使用一个额外的channel，你可以保持一个single channel，并可以额外的维度，它们允许在训练过程中进行修改。

表3: top 4个邻近词——基于consine相似度——static channel(左列)中的向量，在SST-2数据集上，在训练后的multichannel模型中的non-static channel(右侧)中的finetuned vector。

4.2 static vs. Non-static表示

正如single channel non-static model的情况，multichannel模型能够对 non-static channel进行微调（fine-tune），来使要处理任务更具指定性。例如：good在word2vec中与bad最相似，推测起来是因为它们在句子结构(syntactically)上（大至）是相等的。但对于在SST-2数据集上进行微调的non-static channel中的词向量，不再有表3中的情况。相似的，在表示语义上，good与nice更接近（比起good与great），这的确可以反映在学到的向量中。

对于不在pre-trained vector中的token（随机初始化），进行fine-tuning可以使这些token学到更有意义的表示（representation）：该网络可以学到：感叹号（exclamation marks）与感情表达有关，逗号与连接词有关。

4.3 进一步观察

  • Kalchbrenner et al. (2014)，使用一个 CNN得到更糟的结果，本质上与single model的架构一致。例如，它们的Max-TDNN(Time Delay Neural Network)使用随机初始化的词，在SST-1上获得了37.4%，而我们的模型则为45.0%。我们将这种差异归因于：我们的CNN具有更大的容量（多个filter widths和feature maps）。
  • Dropout被证明是一种很好的regularizer, 它很容易使用一个更大的网络，只需dropout去进行regularize即可。Dropout可以增加2-4%的效果提升
  • 当随机初始化的词不在word2vec中时，通过从U[-a,a]中抽样每一维，可以获得微小的提升，其中选中的a，可以使随机初始化的向量具有与pre-trained vector具有相似的variance。在初始化过程，使用更复杂的方法来反映(mirror)pre-trained vectors的分布，来获得提升是挺吸引人的一件事。
  • 我们试验了另一个公共的词向量（由Collobert et al. (2011) on Wikipedia训练得到），发现word2vec可以获得更好的效果提升。这一点不是很清楚：是否是因为o Mikolov et al. (2013)的架构，还是因为google news 1000亿词的数据集的原因。

5.结论

本文描述了在word2vec上构建CNN的一些试验。只需很少的超参数的调参，一个简单的CNN具有一层的卷积层，就可以得到令人吃惊的效果。本文的结果也有效验证了在Deep NLP中pre-trained word vector相当重要。

参考

Convolutional Neural Networks for Sentence Classification

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