youtube的基于深度学习的推荐系统,主要分成两大部分:

一、候选生成

将推荐当成是一个多分类问题,预测问题为:视频库V,有上百万的视频,某用户U,在上下文C上,在时间t时的观看行为$w_t$,刚好是某个视频i.

其中u表示一个高维的(user,context)pair的“embedding”, v表示每个候选视频的emdedding。在该假设中,一个emdedding可以简化成一个稀疏实体的映射(视频,用户等各有一个),映射到一个N维的dense vector中。深度神经网络的任务是:学到user embeddings: u,作为用户历史和上下文的函数,使用一个softmax分类器,用于判别视频。

使用隐式反馈(观看行为)来训练模型,其中,用户完成一个视频可以认为是一个正例。

Efficient Extreme Multiclass

为了有效地训练这样一个上百万分类的模型,我们采用的技术是:从后台分布中对负例采样(sample negative classes),接着通过按权重重要性加权(importance weighting)纠正这些样本。对于每个样本,为true-label和negative-label,学习目标是最小化cross-entropy loss。实际中,会抽样上千个负样本,这种方法可以比传统的softmax快100倍。另一个可选的方法是:hierarchical softmax,但这里我们不去做对比。

在提供服务的阶段(serving time),我们需要计算最可能的N个分类(视频),以便选中其中的top N,来展现给用户。对上百w级的item进行打分,会在10ms左右的延迟内完成。之前的Youtube系统靠hashing技术[24]解决,和这里描述的分类器使用相类似的技术。由于在serving time时并不需要对softmax输出层校准(calibrated)likelihoods,打分问题(scoring problem)可以缩减至在点乘空间中的最近邻搜索问题,可以使用[12]中提供的库来完成。我们发现,在最近邻搜索算法上做A/B test效果并不特别明显。

1.1 模型架构

受语言模型中的CBOW(continuous bag of words)的启发,我们为固定视频库中的每个视频学到了高维emdeddings,并将它们的emdeddings作为输入前馈(feed)给一个前馈神经网络。用户的观看历史,被表示成一个关于稀疏视频id的可变长的序列,通过embeddings,它被映射到一个dense vector表示中。该网络需要固定大小的dense inputs,以及在不同策略中(sum, component-wise max,等)执行的emdeddings的简单平均。最重要的,emdeddings会和其它一些模型参数,通过普通的梯度下降后向传播更新即可学到。特征被级联到一个很宽的第一层上(wide first layer),后面跟着许多层的完全连接的ReLU层[6]。图3展示了整体架构,带有下面将要描述的额外的非视频观看特征(no-video watch features)。

1.2 多种信号

使用深度神经网络作为普通的矩阵分解,其中一个关键优点是,任何连续的特征和类别特征都可以很方便地加进模型中。搜索历史的处理,可以与观看历史的处理方式相类似 – 每一个查询(query)可以tokenized化成1-gram和2-gram,每一个token都可被嵌入。一旦求平均,用户的tokenized化的嵌入式query,代表了一个总结型的稠密搜索历史(summarized dense search history)。人口统计学特征(Demographic features),对于新用户的推荐很重要。用户的地域和设备信息(device),都可以被嵌入和串联。简单的二元特征和连续特征,比如用户性别,登陆态,年龄,都可以归一化到[0,1]上的实数值,直接输入到该网络。

“样本年龄”特征(”Example Age” Feature)

YouTube上,每秒都有许多视频上传上来。推荐这些最新上传的新鲜(“fresh”)内容,对于YouTube产品来说相当重要。我们一致观察到:用户喜欢新鲜内容,尽管并非相关。除了简单的推荐用户想看的新视频所带来的一次传播效果外,还存在着关键的病毒式的二次传播现象。

机器学习系统经常展示出对过往内容的一个隐式偏差(implicit bias),因为它们通常是基于历史样本的训练,来预测将来的行为。视频流行度的分布是高度不稳定的,但是由推荐系统生成的在视频库上的多项分布(multinomial distribution),将影响在多周训练窗口上的平均观看似然。为了纠正这一点,我们将训练样本的age,作为一个训练特征。在serving time时,该特征被置为0(或者为一个微小的负数),反映出模型在训练窗口的最末尾正在做预测。

图4展示了该方法在选择视频上的效果。

图4: 对于一个给定的视频[26],使用样本age作为特征训练的模型能够精准表示数据的上传时间和与时间相关的流行度间的关系。如果没有该特征,模型将会预测在训练窗口上的近似平均似然(baseline)。

1.3 Label和Context选择

需要重点强调的是,推荐(recommendation)通常涉及到求解一个替找问题(surrogate problem),并将结果转换成一个特殊上下文。一个经典的示例是,如果能准确预测rating,会产生有效的电影推荐[2]。我们已经发现,这种代理学习问题(surrogate learning problem)在A/B testing上很重要,但很难在离线试验中进行衡量。

训练样本需要从所有YouTube观看行为(即使嵌入在别的网站上)上生成,而非仅仅只使用我们生成的推荐的观看行为。否则,新内容将很难浮现出来,推荐系统在探索(exploitation)上将过度偏差。如果用户正通过别的方法探索发现视频,而非使用我们的推荐,我们希望能够快速通过协同过滤传播该发现给他人。 一个核心点是,提升live metrics的目的是为每个用户生成一个固定数目的训练样本,有效地在loss function上对我们的用户做平等的加权。这可以防止一少部分高活跃度用户主宰着loss

一定程度上这与我们的直觉相反,必须注意:为防止模型利用网站布局,以及代理问题的过拟合,不要告诉分类器信息(withhold information from the classifier)。可以考虑将一个样本看成是用户已经发起的一个查询query: “taylor swift”。由于我们的问题是预测下一个要看的视频。通过给定该信息,分类器将会预测要观看的最可能的视频,是那些出现在相应搜索结果页中关于”taylor swift”的视频。一点也不惊奇的是,如果重新生成用户最新的搜索页作为主页推荐,效果会很差。通过抛弃顺序信息,使用无顺序的词袋(bag of tokens)表示搜索query,该分类器不再直接认识到label的来源。

视频的自然消费模式,通常会导致非常不对称的co-watch概率。插话式的剧集(Episodic series)通常被按顺序观看,用户经常发现,对于同一个流派(genre)中的艺术家们(artists),在关注更小众的之前,会从最广为流行的开始。因此我们发现对于预测用户的下一次观看行为上有着更好的效果,而非去预测一个随机held-out观看(a randomly held-out watch)(见图5)。许多协同过滤系统隐式地选择标签和上下文,通过hold-out一个随机item,然后通过用户历史观看中的其它item来预测它(5a)。这会泄露将来的信息(future information),并忽略任何不对称的消费模式(asymmetric consumption patterns)。相反的,我们通过选择一个随机观看(a random watch),然后“回滚(rollback)”一个用户的历史,只输入用户在hold-out label的watch之前(5b)的动作。

图5: 选择labels和输入上下文给模型,在离线评估时很有挑战性,但对真实的效果有巨大提升。这里,实心事件•表示网络的输入特征,而空心事件◦表示排除在外。我们发现,预测一个将来的观看(5b),在A/B test中效果更好。在(5b)中,样本的age通过t_max-t_N来表示,其中t_max是训练数据中观察到的最大时间。

1.4 特征和深度的试验

如图6所示,添加特征和深度,可以极大提升在holdout data上的precision。在这些试验中,1M的视频量,和1M的搜索tokens,被嵌入到256个float值上,每个都在一个最大的bag-size:50个最近的watches和50个最近的searches。softmax层输出一个在1M个视频classes、256维的多项分布(可以看成是一个独立的output video emdedding)。这些模型被训练,直接覆盖所有的YouTube用户,对应在数据上的多个epochs上。网络结构按一个公共的”tower”模式,在网络的底部是最宽的,每个后继的隐层,将单元数二等分(与图3相同)。深度为0的网络,是一个有效的线性因式分解模型,它的效果与以往的系统很相似。增加宽度(width)和深度(depth),直到增量的效果越来越小,收敛越来越难:

  • Depth 0: 一个线性层,可简单地将串联层转换成与softmax相匹配的256维.
  • Depth 1: 256 ReLU
  • Depth 2: 512 ReLU -> 256 ReLU
  • Depth 3: 1024 ReLU -> 512 ReLU -> 256 ReLU
  • Depth 4: 2048 ReLU -> 1024 ReLU -> 512 ReLU -> 256 ReLU

二、Ranking

Ranking的主要作用是,针对指定的UI,使用曝光数据来特化和校正候选预测(specialized and calibrate candidate predictions)。例如,用户通常会观看一个probability值较高的视频,但不大可能去点击指定主页上缩略图的曝光。在Ranking时,我们会访问许多描述视频的特征、以及视频与用户关系的特征,因为在候选集生成阶段,只有一小部分的视频被打过分,而非上百w的视频。Ranking对于聚合不同的候选源很重要,因为每个源的得分不能直接对比。

我们使用一个与候选生成阶段相似的架构的深度神经网络,它会使用logistic regression(图7)为每个视频的曝光分配一个独立的值。视频的列表接着会通过该分值进行排序,并返回给用户。我们最终的ranking objective会基于线上的A/B testing结果进行调整,但总体上是一个关于每次曝光的期望观看时长(expected watch time)的简单函数。根据ctr的排序通常会促进视频期诈现象:用户不会播放完整(标题党:点击诱惑”clickbait”),而观看时长(watch time)可以捕获更好的参与度(engagement)[13,25]。

图7: 深度ranking网络架构,描绘了嵌入的类别特征(单值和多值类别都存在),与归一化的连续特征的embeddings和powers共享。所有的层都是完全连接的。惯例上,成百上千的特征都可以输入到网络中。

2.1 特征表示

我们的特征,与传统的类别特征分类,以及连续型/普通特征相互隔离开来。类别型特征,在基数上变化多样–一些是二元的(比如:用户是否登陆),而其它一些则可能有上百万种可能的值(比如:用户最新的搜索query)。特征会根据它们是否是单值(“univalent”),或者多值集合(“multivalent”),再做进一步分割。关于单值类别特征的一个示例是:被打过分的曝光视频id;而相应的多值特征可能是一批(a bag of)关于该用户已经观看过的N个视频id。我们也会根据特征是否描述了item的属性(“impression”)或者user/context的属性(”query”),将特征进行分类。Query特征在每次请求时被计算一次,而impression特征则会为每个评过分的item计算。

特征工程(Feature Engineering)

我们通常在我们的排序模型中使用成百上千的特征,它们被分成类别型和连续型特征。尽管深度学习可以缓和手工建立特征工程的负担,但我们的原始数据天然就不能直接输入到前馈神经网络中。我们仍需要花费可观的工程资源来将用户和视频数据转换成有用的特征。最主要的挑战主要在:表示用户动作的临时顺序,以及如何将这些动作与被打分的视频曝光(impression)相关联。

我们观察到,最重要的信号是,那些描述一个用户与item本身、以及其它相似item的之前交互行为,这与广告排序(randing ads)上的经验相类似。例如,考虑用户的过往历史,以及上传被打分的频道-该用户从该频道观看了多少视频?该用户在该主题上观看一个视频的最近时间是何时?这些连续特征相当强大,它们描述了用户在相关item上的过往动作,因为它们在不同的item上泛化得很好。我们也发现,很重要,从候选生成阶段(Candidate generation)到排序阶段(Ranking)以特征的形式进行信息传递,比如:哪个源被指定给该视频候选?会分配什么分值?

描述过往视频曝光的频率的特征,对于在推荐中引入“搅动(churn)”很重要(连续的请求不会返回相同的列表)。如果一个用户最近被推荐了某个视频,但没有观看它,接着模型将自然地在下一页加载时降级该曝光(impression)。Serving即时曝光和观看历史,是一项工程壮举,超出了本paper的范围,对于产生响应式推荐至关重要。

类别特征embedding (embedding categorical features)

与候选生成阶段相类似,我们使用embeddings,将稀疏的类别型特征映射到dense表征上,更适合于神经网络。每个唯一的ID空间(视频库:”vocabulary”) 都具有一个单独学到的emdedding,它维度的递增与唯一值的数目的log成比例。这些库是简单的look-up table,在训练前由整个数据一次构建。非常大的基数ID空间(视频ID或者搜索query terms)被截断,通过只包含topN,在基于点击曝光的频率排序之后。Out-of-vocabulary的值,可以简单地映射到零嵌入上(zero embdding)。正如在候选生成阶段,多值类别特征的embeddings是被平均化的,在被输入到网络之前。

重要的是,相同ID空间的类别型特征,也共享着底层的embeddbings。例如,存着单个关于视频ID的全局embedding,供许多不同的特征使用(曝光的视频ID,该用户观看的最近视频ID,作为推荐系统”种子”的视频ID等等)。尽管共享emdedding,每个特征独自输入到网络中,因此,上面的层可以学到每个特征的特定表征(representation)。共享嵌入(sharing emdeddings)对于提升泛化、加速训练、及减小内存等相当重要。绝大多数模型参数都是在这些高基数(high-cardinality)的embedding空间中 - 例如,100w的ID,嵌入到32维的空间上,与2048个单元的宽完全连接层多7倍多的参数。

归一化连续特征(Normalizing Continuous Features)

众所周知,神经网络对于输入的归一化和分布是很敏感的[9],其它方法(比如:决策树ensembles)对于独立特征的缩放(scaling)是稳定的。我们发现,对连续特征进行合理的归一化,对于收敛来说很重要。连续特征x,具有分布f,被转换成x^,通过对值进行归一化,比如:特征平均地分布在[0,1)上使用累积分布,。该积分与特征值的分位数的线性插值相近似,在训练开始这,在所有数据上的单个pass中计算。

另外,原始的归一化特征$ \hat{x} $,我们也输入$ \hat{x}^2 $和$ \sqrt{\hat{x}} $,给网络更多有表现力的阶,通过允许它,很容易形成特征的super-linear和sub-linear function。我们发现:输入连续特征的阶,可以提升离线的accuracy。

2.2 对期望的观看时长建模

我们的目标是,给定训练样本:包含正例(曝光的视频被点击)和负例(曝光的视频没被点击),来预测期望的观看时间。正例可以解释成:该用户花费观看该视频的时间量。为了预测期望的观看时间,我们出于该目的,开发并使用加权logistic regression技术。

该模型的训练通过logistic regression和cross-entropy loss进行(图7)。然而,正例(被点的)的曝光,会由视频所观察到的观看时间进行加权。所有负例(未点击)的曝光,都使用单位加权。这种方式下,通过logistic regression学到的差异(odds)是:$ \frac{\sum{T_i}}{N-k} $,其中N是训练样本的数目,k是正例曝光的数目,Ti是第i个曝光的观看时间。假设,正例曝光很小(真实情况就这样),学到的差异(odds)近似为:$ ET $,其中P是点击概率,而E[T]是该曝光所期望的观看时间。由于P很小,该乘积近似为E[T]。为便于推理,我们使用指数函数e^x作为最终的激活函数,来产成这些odds,来近似估计期望的观看时长。

2.3 隐层的试验

表1展示了,我们在下一天的holdout数据上,使用不同的隐层配置所获得的结果。Value展示了每个配置(”加权,每用户的loss”),包括正例和负例,曝光展示给单个页内的某个用户。我们首先使用我们的模型对两种曝光进行打分。如果负例的曝光接受到更高的分值,那么我们会认为,正例的观看时长为:误预测的观看时长(mispredicted watch time)。加权的每用户loss,就是误预测的观看时间的总量,作为一个分数,在heldout曝光pair上的一个总观看时长。

这些结果展示了隐层的width的增加会提升效果,同样depth的增加也会。然而,服务器的CPU时间需要进行权衡下。该配置是一个1024-wide的ReLU,后面跟着一个512-wide的ReLU,再接一个256-wide的ReLU,会给我们最佳的结果,而允许我们在CPU预算范围内。

对于1024->512->256的模型,我们尝试只输入归一化连续特征,而不输入它们的powers,会增加0.2%的loss。相同的隐层配置,我们也训练了一个模型,其中正例和负例的加权相同。不令人惊讶,观看时间加权loss会增加4.1%之多。

表1:在基于观看时长加权的pairwise loss上,更深和更宽的隐ReLU层的效果

参考

- 0.Deep Neural Networks for YouTube Recommendations

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

第1为:使用subword信息来增强词向量。

1.模型:使用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.1 普通模型

先简单回顾下(Mikolov et al.,2013b)提出的continuous skip-gram模型:

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

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

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

wt和上下文词wc采用标量积:$ 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} $.我们将一个向量表示zg与每个n-gram g相关联。我们可以通过对这些n-gram的向量进行求和来表示一个词。我们获得一个scoring函数:

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

1.3 n-gram字典

将所有的n-gram使用一个length>=3, length<=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:

其中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,概率为:

这意味着一个节点的概率总是比它的父节点要低。搜索某一深度的该树时,以及在叶子间跟踪最大概率,允许我们抛弃掉所有小概率的分枝。实际上,我们观察到在测试时,复杂度降到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则会很快!

参考

0.介绍

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

1.模型架构

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

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

… (1)

$ \oplus $为串联操作符(concatenation operator)。$ x_{i:i+j} $ 表示 $ x_i $至$ x_{i+j} $的串联。卷积(convolution)操作符涉及到一个过滤器(filter) $ w \in R^{hk} $,它可以应用于一个含h个词(word)的窗口(window),来生成一个新的特征(feature)。例如,可以由一个词窗口$ x_{i:i+h-1}$来生成一个特征$c_i$:

…(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)。

…(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),做为替换,不再使用:

…(4)

对于在前向传播(forward propagation)中的输出单元y,dropout使用:

…(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

介绍

在解析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次求和函数来预测输出:

…… (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给定)做求和,计算最终的预测值。为了在该模型中学到这些函数集合,我们会对下面的正则化目标函数做最小化:

……(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 $,然后最小化下面的目标函数:

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

其中,$ 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次迭代时的简化版目标函数

……(3)

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

……(4)

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

……(5)

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

……(6)

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

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

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

……(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) $:

……(8)

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

……(9)

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

它就是真正的加权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,原始的稀疏感知算法的时间复杂度:

这里,我们使用 来表示在训练数据中未缺失条目(non-missing entries)的数目。另一方面,块结构上的tree boosting的开销为:

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

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

其中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

最新一朋友在做比特币矿池方向的创业,受邀请帮忙研究下运营矿池的破产概率问题,以尽可能地规避风险。下面会将相应的一些概念与问题一一道来。

1.泊松分布与挖矿问题

泊松分布

  • 泊松分布适合于描述单位时间内随机事件发生的次数。
  • 泊松分布的参数λ是单位时间(或单位面积)内随机事件的平均发生率。
  • 泊松分布的期望和方差均为λt.

1.1 问题

比特币挖矿的数目服从泊松分布。

这是为什么?且细细看来。

  • 1.btc挖矿机的一次计算是否产生一个合法区块可以认为是一个随机事件,任何所有的计算hash彼此相互独立。

  • 2.每次hash计算有对应的计算难度,标为D,决定着发现一个合法块的难度。

  • 3.每次hash计算(32位hash计算,共有1/2^32个hash值)都会有 $ \frac{1}{2^{32}D} $的概率产生一个合法区块。

  • 4.矿工的算力(hashrate:每秒计算hash的次数):h

ok,这个问题可以化简为:

t时间内,该算力的矿工可以挖到多少btc区块?它服从什么分布?

1.2 解释

ok,很明显,速率问题,泊松分布.

速率λ(即:每秒能挖到多少个区块)为:$ \lambda=\frac{h}{2^{32}D} $

  • 单人在t时间内挖到的区块数目期望:$ E(X)=\lambda t=\frac{ht}{2^{32}D} $
  • 单人在t时间内挖到的区块数目方差:$ D(X)=\lambda t=\frac{ht}{2^{32}D} $

另外,还有一个条件:即一个合法区块对应着B个btc。换算成btc的话,这一个常数项的线性变换,即是一个POI(BX)的问题.

根据期望和方差的性质:

  • C为常数,X为随机变量
  • 期望性质:$ E(CX)=CE(X) $
  • 方差性质:$ D(CX)=C^{2}D(X), D(X+C)=D(X) $

从而,我们得到:

单人在t时间内对应回报的期望为:$ E(BX)=BE(X)=\frac{htB}{2^{32}D} $

单人在t时间内对应回报的方差为:$ D(BX)=B^{2}D(X)=\frac{htB^{2}}{2^{32}D} $

单人在t时间内对应回报的标准差为: $ \sigma(BX)=\sqrt{D(BX)}=\sqrt{\frac{htB^{2}}{2^{32}D} $

单人在t时间内对应回报的标准差/期望(标准差是期望的多少倍)为: $ \frac{\sigma(BX)}{E(BX)}=\sqrt{\frac{2^{32}D}{ht}} $

1.3 进一步

矿池挖矿模式与单人solo挖矿模式略有不同:

  • 1.它集合了矿池内所有矿工的算力:其hashrate为:H

矿池将在周期t内获得的区块数同样服从泊松分布(为做区分,此处为随机变量Y)。修改一下算力,得到相应的期望/方差:

矿池将在周期t内获得的区块数期望:$ E(Y)=\frac{Ht}{2^{32}D} $

矿池将在周期t内获得的区块数方差:$ D(Y)=\frac{Ht}{2^{32}D} $

将区块数换算成btc,对应的期望/方差:

矿池在周期t内获得的btc期望:$ E(BY)=\frac{HtB}{2^{32}D} $

矿池在周期t内获得的btc方差:$ D(BY)=B^2D(Y)=\frac{HtB^2}{2^{32}D} $

那么在矿池中,单个矿工的收益又是肿么样的一个期望/方差呢?

这里又有另外一项变换:单个矿工的hashrate为:h=qH(其中:q是该矿工对该矿池中总算力的贡献,0<q<1)

根据期望/方差性质,再做一次换算:

在矿池中,个人在周期t内获得的btc期望: $ E(X)=E(qBY)=qE(BY)=\frac{qHtB}{2^{32}D}=\frac{htB}{2^{32}D} $,该值与solo模式一样

在矿池中,个人在周期t内获得的btc方差:$ D(X)=D(qBY)=q^{2}D(BY)=\frac{q^{2}HtB^2}{2^{32}D}=\frac{qhtB^2}{2^{32}D} $,是solo模式的q倍。(0<q<1,因而方差变小,风险也变小了)

2.矿池如何实现收支平衡?

2.1 一般的矿池

矿池通常由一个矿池运营者(pool operator)来维护,它会在相应的服务上花费一定的费用。这通常是区块回报的一个固定百分比:f。因此,对于每个发现的区块,operator都将收到一笔fB的费用,余下的(1-f)B将分配给矿工。

再做一次变换,利用期望/方差的性质:

矿池中,单个矿工获得的的实际btc收入的期望为:$ E(X)=E((1-f)qBY)=(1-f)E(qBY)=\frac{(1-f)htB}{2^{32}D} $,与solo模式略有下降(但其实个人挖一样需要支付电费等问题存在)

矿池中,单个矿工获得的的实际btc收入的方差为: $ D(X)=D((1-f)qBY)=(1-f)^{2}D(qBY)=(1-f)^{2}q\frac{htB^2}{2^{32}D} $,是solo模式的(1-f)^2q倍. 方差更小。

2.2 变态的矿池

PPS矿池就是这样。

只要挖,不管有没挖到,在周期t时间里,矿工都会有收入。

在矿池中,单个矿工的收入的方差为0。operator承担所有的方差,风险更大,因而需要对operator再做一定的补偿。如果operator不正确平衡矿池的费用以及他的财产准备金,矿池有很大可能会破产。

这里有两个问题:

  • 补偿方式有变化?
  • 在有限资源的情况下,准备金至少需要多少,才能让破产机率更低?

先回到原先讲的:

  • 1.矿池中每次hash计算成为一个share的概率:$ \frac{1}{2^{32}} $
  • 2.每个share成为合法区块都有一个概率:$ p=\frac{1}{D} $
  • 3.矿工在每次提交一个share时将平均接收到的回报:pB
  • 4.对于operator则收到的费用: $ (1-f)pB $

2.2.1 推导阶段一

如何分配它?

这里,每次提交share可以当成一个step。在这个周期t内,计算出来的share本身有两个状态:合法(可得到btc)、非法(无效计算,得不到btc)。合法的概率为p,非法的概率为:1-p。

如果合法,则获得B个btc。然后拿出(1-f)pB进行分配给矿工,剩余的归operator自己。如果非法,那就没有收入了,但仍要拿出(1-f)pB进行分配给矿工。这是一个典型的连续时间随机过程,可以用马尔可夫链来表示。一个周期间,operator所得到的收入(包括损失):

$ X_{t+1}-X_{t}={ \begin{aligned} &-(1-f)pB+B & w.p. & & p \ &-(1-f)pB & w.p. & & 1-p \end{aligned} $$

它的期望为:

同理使用方差计算公式可得,真实的方差为:$ p(1-p)B^{2} $ ,而btc矿池paper将它近似认为:$ pB^{2} $,这里有些疑问(只有当p的概率较大时,才有可能近似)。

根据中心极限定理可知(这一步有待进一步求证),长期行为服从$ (fpB, p(1-p)B^{2}) $的正态分布。而这面的这个随机过程正好服从该分布(期望/方差一致),因而可以近似等价为:

我们再对这个初始条件按因子$ \sqrt{p}/B $做一下缩放:

这样缩放的好处,对后面推导有利。每次输赢为常量(f恒定, p恒定)。

2.2.2 推导阶段二

剩下的问题,其实就等价于随机过程中马尔可夫链的经典问题:《赌徒输光问题》。

$a_n$表示,从状态n开始要达到0的概率(表示矿池破产)。我们在第一步得到的条件,表示:$q=(1+f\sqrt{p})/2 $

这个随机过程可以表示为:

可以用常系数齐次线性方程求解该多项式特征方程:

该方程的解为:

整个特征方程,它的通解形式为:

代入初始值(边界条件):$a_0=1,a_{\infty}=0 $

即:A=0, B=1,得到$ a_n $:

如果operator以一个R的话准备金启动,矿池的破产概率为:

相反地,为了维持一个破产概率最大为$ \delta $,矿池应至少保有准备金:

参考:

1.Analysis of Bitcoin Pooled Mining Reward Systems. Meni Rosenfeld