我们先来看下Google Inc的paper:Wide & Deep Learning for Recommender Systems。

一、介绍

推荐系统可以看成是一个搜索排序系统,其中输入的query是一个用户和上下文的集合,输出是一个item列表。给定一个query,推荐任务就是在数据库中找到相关的items,接着基于目标(比如:点击or购买)去对items进行排序。

推荐系统与常见的搜索排序问题相同的一个挑战是,同时满足Memorization和Generalization。Memorization可以宽泛地定义成学到items或features的共现率,并利用(exploiting)这种在历史数据中的相关关系(correlation)。Generalization则基于相关关系的转移,并探索(explores)在过往很少或从不出现的新的特征组合。基于Memorization的推荐系统通常更局部化(topical),将items与执行相应动作的users直接相关。而基于Generalization的推荐则更趋向于推荐多样化的items。在本papers中,我们主要关注Google Play Stores的推荐问题,方法本身可用于其它场景。

对于工业界大规模的在线推荐和排序系统,常用的线性模型(比如:logistic regression)被广泛使用,因为它的简单性、可扩展性以及可解释性。模型通常在使用one-hot编码的二值化的稀疏特征上。例如,二值化特征”user_installed_app=netflix”,如果用户过去安装(installed)了Netflix,则具有特征值1. 通过在稀疏特征上使用cross-product transformation可以有效地达到Memorization,比如AND(user_installed_app=netflix, impression_app=pandora),如果用户过去安装了Netflix,接着被曝光了Pandora,那么它的值是1. 这可以解释一个特征对(feature pair)的共现率与目标label间的相关关系。通过使用更少(粗)粒度的特征可以添加Generalization,例如:AND(user_installed_category=video, impression_category=music),(注:上面Memorization使用的是具体的app,而此处Generalization使用的仅仅是app的category),但人工的特征工程通常是必需的。(cross-product transformation)的一个限制是,不能泛化到那些在训练数据上没有出现过的query-item特征对。

Embedding-based的模型,比如因子分解机(FM)或深度神经网络,只需要很少的特征工程,通过为每个query和item特征对(pair)学到一个低维的dense embedding vector,可以泛化到之前未见过的query-item特征对,。然而,当底层的query-item矩阵很稀疏和高秩(high-rank)时(比如,用户具有特殊偏好或很少出现的items),很难为query-item pair学到有效的低维表示。在这种情况下,大多数query-item pairs之间是没有交叉的,但dense embeddings会为所有的query-item pairs生成非零的预测,这样会过泛化(over-generalize),并生成不相关的推荐。另一方面,使用交叉特征转换(cross-product features transformations)的线性模型可以使用更少的参数就能记住(memorize)这些“异常规则(exception rules)”。(embedding 优点:泛化,缺点:稀疏时)

在本文中,我们提出了Wide&Deep learning框架来在同一个模型中达到Memorization 和 Generalization,通过联合训练一个如图一所示的线性模型组件和一个神经网络组件。

本文的主要贡献:

  • Wide & Deep 学习框架,可以用于联合训练带embeddings的feed-forward神经网络以及带特征转换的线性模型,用于带稀疏输入的常见推荐系统中。
  • Wide & Deep推荐系统的实现和评估在Google Play上已经产品化,这个app store具有数十亿的活跃用户、以及上百万的app。
  • 开源,在Tensorflow上提供了一个高级API

思想很简单,我们展示了Wide & Deep框架,它极大地提升了App的获得率(acquisition rate)并且同时满足training和serving的速度要求。

推荐系统总览

app推荐系统如图二所示。一个query,它包含着许多用户和上下文特征,当一个用户访问app store时生成。推荐系统会返回一个app列表(曝光:impressions),用户在此之上会执行特定的动作(点击:click或购买:purchase)。这些用户动作,伴随着queries和impressions,会以日志的形式记录下来。

由于在数据库中有超过百万的app,对于在serving延迟条件之内(通常为O(10)ms)的每一个query,尽可能得对每一个app进行评分是相当困难。因此,上述第一步收到一个query的过程是检索(retrieval)。检索系统会返回一个最匹配query的item的短列表,通常使用机器学习模型和人工定义规则来达到。在数量减至候选池后,排序系统(ranking system)会通过它们的得分对所有items进行排序。得分通常是$ P(y|x) $,对于给定的特征x,一个用户的动作标签y,包括用户特征(比如:国家,语言,人口属性信息),上下文特征(比如:设备,天的小时,周的天),曝光特征(比如:app age, app的历史统计信息)。在本文中,我们只关注在排序系统中使用Wide & Deep 学习框架。

3. Wide & Deep Learning

3.1 Wide组件

wide组件是一个泛化的线性模型,形式为:$ y=w^Tx+b $,如图1(左)所示。y是预测,$ x = [x_1, x_2, …, x_d] $是d维的特征向量, $ w = [w_1, w_2,…, w_d] $是模型参数,其中b为bias。特征集包括原始的输入特征和转换后的特征,一个最重要的转换是,cross-product transformation。它可以定义成:

…(1)

其中$c_{ki}$为一个boolean变量,如果第i个特征是第k个变换$\phi_k$的一部分,那么为1; 否则为0.对于二值特征,一个cross-product transformation(比如:”AND(gender=female, language=en)”)只能当组成特征(“gender=female” 和 “language=en”)都为1时才会为1, 否则为0. 这会捕获二值特征间的交叉,为通用的线性模型添加非线性。

3.2 Deep组件

Deep组件是一个前馈神经网络(feed-forward NN),如图1(右)所示。对于类别型特征,原始的输入是特征字符串(比如:”language=en”)。这些稀疏的,高维的类别型特征会首先被转换成一个低维的、dense的、real-valued的向量,通常叫做“embedding vector”。embedding的维度通常是O(10)到O(100)的阶。该embedding vectors被随机初始化,接着最小化最终的loss的方式训练得到该值。这些低维的dense embedding vectors接着通过前向传递被feed给神经网络的隐层。特别地,每个隐层都会执行以下的计算:

…(2)

其中,l是层数,f是激活函数(通常为ReLUs),$a^{(l)}, b^{(l)}和W^{(l)}$分别是第l层的activations, bias,以及weights。

3.3 Wide & Deep模型的联合训练

Wide组件和Deep组件组合在一起,对它们的输入日志进行一个加权求和来做为预测,它会被feed给一个常见的logistic loss function来进行联合训练。注意,联合训练(joint training)和集成训练(ensemble)有明显的区别。在ensemble中,每个独立的模型会单独训练,相互并不知道,只有在预测时会组合在一起。相反地,联合训练(joint training)会同时优化所有参数,通过将wide组件和deep组件在训练时进行加权求和的方式进行。这也暗示了模型的size:对于一个ensemble,由于训练是不联合的(disjoint),每个单独的模型size通常需要更大些(例如:更多的特征和转换)来达到合理的精度。相比之下,对于联合训练(joint training)来说,wide组件只需要补充deep组件的缺点,使用一小部分的cross-product特征转换即可,而非使用一个full-size的wide模型

一个Wide&Deep模型的联合训练,通过对梯度进行后向传播算法、SGD优化来完成。在试验中,我们使用FTRL算法,使用L1正则做为Wide组件的优化器,对Deep组件使用AdaGrad。

组合模型如图一(中)所示。对于一个logistic regression问题,模型的预测为:

…(3)

其中Y是二分类的label,$ \sigma(·) $是sigmoid function, $ \phi(x) $是对原始特征x做cross product transformations,b是bias项。$w_{wide}$是所有wide模型权重向量,$w_{deep}$是应用在最终激活函数$a^{(l_f)}$上的权重。

4.系统实现

app推荐的pipeline实现包含了三个stage:数据生成,模型训练,模型serving。如图3所示。

4.1 数据生成

在这一阶段,用户和app的曝光数据在一定时间内被用于生成训练数据。每个样本对应于一个曝光。label为app的获得率(acquisition):如果曝光的app被下载则为1, 否则为0.

词汇表(Vocabularies),它是一个关于将类别特征字符串映射到integer ID上的表,也在该阶段生成。该系统会为至少出现过某个最小次数的所有的string特征计算ID空间。连续的real-valued特征被归一化到[0, 1],通过将一个特征值x映射到它的累积分布函数$P(X <= x)$,将它分成$n_q$份 (quantiles)。对于第i个份(quantiles),对应的归一化值为:$ \frac{i-1}{n_q-1}$。分位数(quantiles)边界在数据生成阶段计算。

4.2 模型训练

我们在试验中使用的模型结构如图4所示。在训练期间,我们的输入层接受训练数据和词汇表的输入,一起为一个label生成sparse和dense特征。wide组件包含了用户安装app和曝光app的cross-product transformation。对于模型的deep组件,会为每个类别型特征学到一个32维的embedding向量。我们将所有embeddings联接起来形成dense features,产生一个接近1200维的dense vector。联接向量接着输入到3个ReLU层,以及最终的logistic输出单元。

此处做个注解(美食推荐场景FoodIO):wide模型的目的是,记住(memorize)哪些items能更好地对应每个query。因此,你训练带交叉特征转换的线性模型,是为了捕获一个query-item feature pair与相应的目标label(一个item是否被消费、购买)间的共现关系。该模型会预测每个item的消费概率 ,接着FoodIO会返回最高预测购买率的top item。例如,模型学到了特征:AND(query=”炸鸡(fried chicken)”, item=”鸡肉和华夫饼(chicken and waffles)”)的效果很好,而AND(query=”炸鸡(fried chicken)”, item=”鸡肉炒饭(chicken fried rice)”)这个并不受喜欢,尽管字符上更匹配。换句话说,它可以记住哪些用户喜欢,从而获得更多的交易额。

同理:上述wide中提到的installed app和impressed app可以理解成是上面的item和query。

Wide & Deep模型在超过5000亿的样本上进行训练。每一时刻有新的训练数据集到达时,模型需要重新训练。然而,每次从头到尾重新训练的计算开销很大,数据到达和模型更新后serving间的延迟较大。为了解决该问题,我们实现了一个warm-starting系统,它会使用前一个模型的embeddings和线性模型权重来初始化一个新的模型

在将模型加载到模型服务器上之前,需要做模型的演习,以便确保它不会在serving的真实环境上出现问题。我们在经验上会验证模型质量,对比前一模型做心智检查(sanity check)。

4.3 模型Serving

一旦模型被训练和验证后,我们会将它加载到模型服务器上。对于每个请求,服务器会从app检索系统上接收到一个app候选集,以及用户特征来从高到低排序,接着将app按顺序展示给用户。得分的计算通过在Wide&Deep模型上运行一个前向推断传递(forward inference pass)来计算。

为了在10ms的级别服务每个请求,我们使用多线程并行来优化性能,运行运行更小的batches,而不是在单个batch inference step中为所有的候选app进行scoring。

5.试验结果

为了在真实的推荐系统上评估Wide & Deep learning的效果,我们运行了在线试验,并在两部分进行系统评测:app获得率(app acquisitions)和serving性能。

5.1 App Acquisitions

我们在一个A/B testing框架上做了3周的试验。对于控制组,1%的用户被随机选中,推荐由之前版本的排序系统生成,它是一个高度优化的wide-only logistic regression模型,具有丰富的cross-product特征转换。对于试验组,随机选中1%的用户,使用相同的特征进行训练。如表1所示,Wide & Deep模型在app store的主页上提升了app acquisition rate,对比控制组,有+3.9%的提升。另一个分组只使用deep组件,使用相同的神经网络模型,具有+1%的增益。

除了在线试验,我们也展示了在held-out离线数据上的AUC。其中Wide & Deep具有更高的离线AUC,在线也更好。一个可能的原因是,曝光和点击在离线数据集上是确定的,而在线系统通过混合generalization和memorization,从新的用户响应学到,生成新的探索推荐。

5.2 Serving Performance

Serving时具有高的吞吐率(throughout)和低延时是很有挑战性的。在高峰期,我们的推荐服务每秒处理1000w个app得分。单个线程上,在单个batch上为所有的候选得进行scoring会花费31ms。我们实现了多线程,并会将每个batch分割到更小的size上,它会将客户端的延迟的延迟减小到14ms上,所图2所示。

6.相关工作

将使用特征交叉转换的wide linear model与使用dense embeddings的deep neural networks,受之前工作的启发,比如FM:它会向线性模型中添加generalization,它会将两个变量的交互分解成两个低维向量的点积。在该paper中,我们扩展了模型的能力,通过神经网络而非点积,来学习在embeddings间的高度非线性交叉(highly nonlinear interactions)。

在语言模型中,提出了RNN和n-gram的最大熵模型的joint training,通过学习从input到output之间的直接权重,可以极大减小RNN的复杂度(hidden layer)。在计算机视觉中,deep residual learning被用于减小训练更深模型的难度,使用简短连接(跳过一或多层)来提升accuracy。神经网络与图模型的joint training被用于人体姿式识别。在本文中,我们会探索前馈神经网络和线性模型的joint training,将稀疏特征和output unit进行直接连接,使用稀疏input数据来进行通用的推荐和ranking问题。

7.Tensorflow

只需要3步,即可以使用tf.estimator API来配置一个wide,deep或者Wide&Deep:

  • 1.选中wide组件的特征:选中你想用的稀疏的base特征列和交叉列特征列
  • 2.选择deep组件的特征:选择连续型的列,对于每个类别型列的embedding维,以及隐层的size。
  • 将它们放置到一个Wide&Deep模型中(DNNLinearCombinedClassifier)

关于更详细的操作,示例代码在:/tensorflow/tensorflow/examples/learn/wide_n_deep_tutorial.py,具体详见tensorflow tutorial。

参考

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的可变长的序列,这些id通过embeddings技术被映射到一个dense vector表示中。该网络需要固定大小的dense inputs,在不同策略中(sum, component-wise max,等),对emdeddings的简单平均(simply averaging)效果最好。最重要的,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)上使用累积分布,$ \hat{x}=\int_{-\infty}^{x}df $。该积分与特征值的分位数的线性插值相近似,在训练开始这,在所有数据上的单个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

我们来看下Bryan Perozzi的

1.介绍

网络表示的稀疏性,即是它的强项,也是它的弱项。稀疏性允许有效离散算法的设计,但使它很难泛化到统计学习(statistical learning)中。在网络上的机器学习应用(比如:网络分类、内容推荐、异常检测、缺失环节预测missing link prediction等),必须能处理这种稀疏性。

本文引入了deep learning(非监督特征学习)技术来进行网络分析,它在NLP上取得了成功。我们开发了一个算法(DeepWalk),它会通过建模一个关于短随机游走的流(stream),会学到一个图的节点(graph vertices)的社群表示(social representations)。社群表示是节点的隐特征,它可以捕获邻节点的相似度和社群关系。这些隐表示(latent representation)可以将在连续特征空间中的社交关系使用相对少量的维度进行编码。DeepWalk会将自然语言模型泛化来处理一个特殊的语言:它由一个随机生成的游走集合组成。这些自然语言模型被用于捕获人类语言中的语法和语义结构、以及逻辑类比。

图1

DeepWalk会将一个图作为输入,并生成一个隐表示作为它的输出。将我们的方法应用于Karate network上,结果如图1所示。图1a通过力导向(force-directed)的布局进行表示,图1b展示了我们使用2个隐维度的方法。除了显著的相似性外,我们注意到1b中线性可分的部分,对应于通过输入图1a的模块最大化(modularity maximization)的聚类(clusters): 通过顶点颜色区分。

为了演示DeepWalk在真实世界场景中的潜力,我们在多标签网络分类问题上评估了它的性能。在关系分类(relational classification)问题上,特征向量间的连结(links)与传统的独立同分布(i.i.d)假设冲突。解决该问题的技术通常使用近似推断技术(approximate inference )来增加依赖信息来提升分类结果。我们通过增加图表示(representations of the graph)的标签独立性(label-independent)来解决。我们的representation质量不会因labeled vertices的选择而受影响,因而它们可以在任务间共享。

DeepWalk比其它用于创建社交维度(social dimension)隐表示方法要好,尤其是当labeled nodes很稀少时。我们的表示法的性能可能与最简单的分类器(LR)相当。我们的表示是可泛化的,可以结合任何分类方法(包含迭代型推断法)。DeepWalk可以完成所有,它是一个在线算法,可并行化。

本paper贡献:

  • 引入深度学习作为一个工具来分析图,来构建健壮的表示,很适合于统计建模。DeepWalk会学到在短随机游走(short random walks)内表示的结构化规律。
  • 我们对多个社交网络上使用我们的表示法在多标签分类上进行了评估。我们发现可以极大提升存在标签稀疏性情况的分类效果,在Micro F1上可以提升5%-10%。在一些case中,即使只给了更少的60%的数据,DeepWalk的表示也可以胜出其它对手。
  • 我们展示了我们的算法的可扩展性,使用一个并行实现去构建web-scale图(比如:Youtube)的表示。另外,我们描述了最小的必要变化来构建一个流版本(streaming version)。

本paper的其余部分如下安排。在第2-3节,打架述了在数据网络中的分类问题范式,以及如何与我们的工作相结合。在第4节,我们描述了DeepWalk算法。第5、6节描述实验以及实验结果。等

2.问题定义

问题是:对一个社交网络的成员进行分类,分成成一或多个类(categories)。更正式地表示:G=(V, E),其中V是网络的成员,E是它们的边,。给定一个部分标记的社交网络,属性, 其中S是每个属性向量的特征空间size,,其中是labels的集合。

在传统的机器学习分类设定中,我们的目标是学习一个假设函数H,它会将元素X映射到标签集合上。在我们的case中,我们可以利用关于样本依赖的显著信息,嵌入到G的结构中来完成更好的效果。

在学术上,这被称为是关系分类(relational classification)或者称为协作分类(collective classification)。关系分类的传统方法将该问题假装成是在一个无向马尔可夫网络上做推断,接着使用迭代近似推断算法(比如:迭代型分类算法,Gibbs Sampling,或者 标记松弛法label relaxation)来计算给定网络结构下的标签后验分布。

我们提出了一个不同的方法来捕获网络拓朴信息。这种方法不再使用将标签空间进行混合作为特征空间的一部分,而是提出了一种无监督的方法,经可以学到这样的特征:它能捕获与标签分布相独立的图结构。

结构化表示与标记任务间的分隔,可以避免重复错误,这常在迭代型方法中出现。另外,相同的表示可以被用于网络的多分类问题。

我们的目标是,学习,其中,d是隐维度(latent dimensions)是最小数目。这些低维度表示是分散的(distributed); 这意味着每个社交现象(social phenomena)可以通过维度的某个子集进行表示,每个维度会。

使用这些结构化特征,我们可以增大属性空间来帮助分类决策。这些特征是通用的,可以被用于任何分类算法(包括迭代型方法)。然而,我们相信,这些特征的最大作用是,它们很容易与简单的机器学习算法集成。它们可以很适合地在现实网络中扩展,在第6节会介绍。

3.学习社交表示

我们使用以下的特征来探索社交表示学习(learning social representations):

  • 适配性(Adaptability):真实社交网络是不断演进的;新的社交关系不需要再次所有重复学习过程。
  • 社群意识(Community aware):隐维度间的距离可以作为评估网络成员的社交相似性的一个metric。这允许泛化到同质的网络中。
  • 低维(Low dimensional):当标记数据很少时,低维模型泛化更好,加速收敛和推断。
  • 连续(Continuous):我们需要隐表示来建模在连续空间中的部分社群成员关系(community membership)。除了提供一个关于社群关系的细微视图外,连续表示法具有在社群间的平滑决策边界,这可以允许更健壮的分类。

我们的方法满足这些需求,从一个短随机游走流中,使用语言建模上的优化技术来为顶点学到表示。这里,我们会复习下随机游走和语言建模,并描述两者如何结合来满足我们的需要。

3.1 随机游走

一个根顶点的随机游走的定义为:。它是一个随机过程,具有随机变量:是从顶点的邻节点上随机选中的顶点。随机游走已经被用于在内容推荐和社群发现领域的多个问题上作为一个相似度衡量方法。他们也是输出敏感算法(output sensitive algorithms)大类的基础,使用它们来及时计算局部社群结构信息,与输入图的size成次线性关系(sublinear)。

这种局部结构的连接特性,启发我们来使用一个短随机游走作为我们的基础工具来从一个网络中抽取信息。除了捕获社群信息外,在我们的算法中使用随机游走作为基础,能给我们带来其它两个特性。

  • 1.局部探索(local exploration)很容易并行化。多个随机游走者(random walkers)以不同线程、进程、机器可以并行探索同一个graph下的不同部分。
  • 2.依靠从短随机游走上获取信息,可以使它更能适应在图结构上的小变动,无需进行全局重新计算。我们可以迭代式地更新学到的模型,从变动区域上使用新的随机游走,它对整个graph是在时间上是次线性的。

3.2 连接:二八法则(power law)

已经选择在线随机游走作为我们的基础来捕获图结构,我们现在需要一个更适合的方法来捕获这种信息。如果一个连接图的度分布(degree distribution)遵循一个power law(scale-free),我们会观察到,出现在短随机游走上的哪个顶点的频次也是遵循power-law分布的。

图2

在自然语言中,词频会遵循一个相似的分布,其中,语言建模领域的技术可以对该分布行为作出解释。为了强调该相似性,如图2所示,我们展示了两个不同的power-law分布。第1个图来自在一个scale-free的graph上进行一系列短随机游走,第2个图来自关于英文wikipedia的10w篇文章的文本。

我们的工作的一个核心贡献是,用于建模自然语言的技术(其中,符号频次遵循power-low分布)可以被用于建模在网络中的社群结构。该节剩余部分将讨论语言建模,并将它迁移到我们的case中来学习顶点表示。

3.3 语言建模

语言建模的目标是,在语料中出现的一个指定词序列的似然。更正式地,给定一个词序列:

其中,(V是词汇表),我们想最大化在所有训练语料上的

在表征学习上的最近工作,主要使用概率神经网络来构建词的通用表示,可以扩展到语言建模范围之外。

在本paper中,我们使用一个语言建模的泛化版本、结合短随机游走的一个流(stream)来探索图。这些游走可以被认为是在一个特殊语言中的短句、短段落。直接类比是,给定在随机游走中所有访问过的前节点,估计观察顶点的似然。

我们的目标是学习一个隐表示,它不仅仅是节点共现的一个概率分布,而且我们引入了一个映射函数 。该映射函数表示与在图中每个顶点v相关的隐社交表示。(实际上,我们通过一个的自由参数矩阵来表示,它可以在之后作为我们的服务)。接着该问题是,估计以下似然:

…(1)

然而,随机游走长度的增长,计算该目标函数会变得不可行。

在自然语言中的最近实验是,开始转变预测问题。首先,它不同使用上下文来预测一个缺失的词(word),而是使用一个词来预测它的上下文。第二,上下文由给定词的右侧和左侧组成。最后,它在该问题上会移除顺序限制。作为替代,该模型需要最大化出现在该上下文中的任何词的概率,无需知道与给定词间的偏移。

用顶点表示建模的优化问题,如下:

…(2)

我们发现这些条件放宽,特别适合于社交表征学习。首先,顺序无关性假设可以更好捕获由随机游走提供的“邻近度(nearness)”。另外,该relaxation通过一次只为一个顶点构建小模型对于加速训练时间相当有用。

对等式(2)的优化问题进行求解来构建表示,可以捕获在顶点间的局部图结构的共享相似度。具有相同邻节点的顶点可以获取相似的表征(encoding cocitation similarity),允许在机器学习任务上进行泛化。

通过组合截短的随机游走和自然语言建模,我们会对该方法公式化,它可以满足所有我们期待的特性。该方法可以生成社交网络的表征,具有低维、连续空间的特性。它的表示会对社群的隐形式进行编码,因为该方法会输出有用的中间表征,可以用来更改网络拓朴。

4.方法

在本节中,我们讨论算法的主要构成。

4.1 总览

在任何语言建模算法中,只需要一个语料和词汇表V。DeepWalk会考虑短截断的随机游走的一个集合作为它的语料,图顶点作为它的词汇表()。其中,它有利于知道在训练之前的随机游走上顶点的词频表V和频次分布。

4.2 算法:DeepWalk

该算法包含了两个主要部分:

  • 1.随机游走生成器
  • 2.一个更新过程

随机游走生成器会使用一个图G,并且均匀地抽样出一个随机顶点作为随机游走的根节点(root)。一个游走会均匀从最后访问的顶点的邻节点进行抽样,直到到达最大长度(t)。在我们的实验中,随机游走的长度设置是固定的,但是对于随机游走来说没有限制一定要用相同长度。这些游走会重启(restart)(例如:一个传送点(teleport)的概率会返回到它的root),但我们的初步结构不会展示使用重启(restarts)的任何优点。实际上,我们的实现指定了在每个顶点上进行随机游走的数目()和长度(t)。

算法一

在算法1中的3-9展示了我们算法的核心。外层的循环指定了次数,,即我们在每个顶点上启动随机游走的数目。我们认为每个迭代会生成一个对数据的”通路(pass)”,并在该pass期间为每个节点抽样一个walk。在每个pass的开头,我们生成了一个随机顺序来遍历这些顶点。这不是必需的,但可以加速随机梯度下降(SGD)的收敛。

在内层循环中,我们会迭代图的所有顶点。对于每个顶点,我们会生成一个随机游走 ,接着使用它来更新我们的表征represntations(第7行)。我们使用SkipGram算法来更新这些表征,以适应在等式2中的目标函数。

4.2.1 SkipGram

SkipGram是一个语言模型,在一个句子中,它会最大化在同一窗口w中词之间的共现率。

图3: 补充

算法2会迭代在窗口w内出现的随机游走中的所有可能排列(collocations)(第1-2行)。for-each操作中,我们会将每个顶点映射到它的当前表征向量中(见图3b)。给定的表示,我们可以最大化在该walk中的邻节点的概率(第3行)。我们可以有多种分类器选择来学到在walk中这样的后验分布。例如,使用LR建模前面的问题,可以生成一个海量的标签(上百万或数十亿),它等于词汇表数。这样的模型需要大量计算资源,可能会占用整个计算集群。为了加速训练时间,可以使用Hierarchical Softmax来近似概率分布。

算法2

4.2.2 Hierarchical Softmax

给定,计算第3行中是不可行的。计算分区函数(正归化因子)很昂贵。如果我们将顶点设计成一棵二叉树的叶子节点,预测问题就转化成了最大化在树中一条指定路径上的概率(见图3c)。如果到顶点的路径通过一个树节点序列表示,其中:,那么:

现在,可以通过一个二分类器进行建模,该值被分配给节点的父节点。这可以减少计算的计算复杂度:从

我们可以进一步加速训练过程,通过分配更短的路径给在随机游走中的频繁顶点。Huffman编码常用于减小在树中频繁顶点的访问次数。

4.2.3 最优化

模型参数集是,其中每个的size都是。随机梯度下降(SGD)被用于最优化这些参数(算法2第4行)。导数的估计使用BP算法。SGD的learning rate 在训练开始处初始化设置为2.5%,接着随着见过的顶点数进行线性递减。

4.3 并行化(Parallelizability)

如图2所示,在社交网络上的随机游走中,顶点的频率分布与语言中的字分布遵循power law。这会产生一个关于不频繁顶点的长尾,因此,对有影响的更新在本质上很稀疏。这允许我们使用并行版本的ASGD(asynchronous version of stochastic gradient descent),在多个worker上。假定:我们的更新是稀疏的,我们不需要一个锁来访问模型的共享参数,那么ASGD将会达到一个收敛的最优rate。其中我们在单机上使用多线程进行实验,它可以演示这种技术是高度可扩展的,可以用于大规模机器学习上。图4展示了并行的DeepWalk。它展示了处理BLOGCATELOG和Flickr网络的加速与我们增加workers数是一致的(图4a)。也展示了相对于顺序版本的DeepWalk,预测效果并没有损失(图4b)。

图4

4.4 算法变种

我们提出的方法还有一些变种。可能是你感兴趣的。

4.4.1 Streaming

其中一个有意思的变种是streaming方法,它没需知道整个graph就可以实现。在该变种中,从一个图出发的小游走,直接传到表示学习编码上,模型是直接更新的。该学习过程的一些修改是必须的。首先,使用一个衰减的learning rate不再可能。相反地,我们会初始化learning rate ,我们不必构建一个参数树。如果V的基数是已经的(可以限定),我们可以构建Hierachical Softmax tree来最大化值。当顶点被首先看到时,它们会被被分配给余下叶子之一。如果我们能估计顶点频率的一个先验,我们也可以仍使用Huffman编码来减小频繁节点的访问次数。

4.4.2 非随机游走

一些图是作为一系列元素行为的一个副产品被创建的。(例如:用户在一个网站上的导航)。当一个图通过这样的非随机游走方式创起家时,我们可以使用该过程来直接feed该建模阶段。以这种方式抽样的图不仅能捕获与网络结构相关的信息,也能捕获在该路径进行反向的频率。

我们认为,该变种也包括语言建模问题。句子可以看成是通过一个合理设计的语言网络上的一些特定游走,像SkipGram的语言模型可以被设计用来捕获这种行为。

该方法可以结合streaming变种来在连续演化网络上训练特征,无需显式构建整个网络。使用该技术维护表示,可以允许web-scale分类,无需处理一个web-scale规模的graph。

5.实验设计

略.

YouTube是一个社交网络,用户共享流行的视频。这里的labels表示viewers的群组,它们喜欢相同的视频类目(比如:动作 和 摔跤)

6.实验

6.1.3 YouTube

详见paper.

参考

DeepWalk: Online Learning of Social Representations

1.介绍

对于词(words)的分布式组成语义的算法开发是一个长期存在的开放性难题。最近几年的算法有:将word vectors映射到sentence vectors(包括recursive networks, recurrent networks, convolutional networks,以及recursive-convolutional方法)。所有的这些方法会生成句子表示,传给一个监督式任务,依赖一个class label来对组成权重(composition weights)做BP算法。因而,这些方法能学到高质量句子表示,但只能对自己的特定任务进行调整。paragraph vector是另一种方法,它通过引入一个分布式句子索引作为模型的一部分,以非监督式学习进行句子表示。

本文中,我们考虑了另一种loss function,可以用于任何组成操作(composition operator)上。考虑以下的问题:是否存在一个任务,它对应的loss允许我们学习高度泛化的句子表示?受使用word vector学习的启发,我们提出了一个目标函数,它从句子级别上抽象了skip-gram模型。也就是说,它不再使用单个word来预测它的上下文,我们会encode一个句子。因而,任何组成操作(composition operator)都适用于一个句子编码器(sentence encoder),只是目标函数被修改了而已。图1展示了该模型,我们会调用我们的skip-thoughts模型和向量。

图1: skip-thoughts模型。给定一个tuple(),表示book中的第i个句子,被编码并尝试重构前一个句子和下一个句子。在本例中,输入的句子三元组:I got back home. I could see the cat on the steps. This was strange. 未绑定箭头被连接到encoder output上。颜色表示哪个component共享参数。(与skip-gram有点像)

表1: BookCorpus dataset的统计信息

我们的模型依赖于一个关于连续文本的训练语料。我们选择使用一个小说集合BookCorpus dataset来训练我们的模型。这些书由未出版的作者编写。该dataset具有6种不同的种类:Romance, Fantasy, Science fiction , Teen等。表1高亮了该语料的统计。伴随着故事,书包含着对话,感情(emotion)和广泛的字符交叉。另外,训练集的量很大,不会偏向于任何特定领域或应用。表2展示了该语料中句子的最近邻。该结果展示了skip-thought vectors精确地捕获了编码后的句子的语义和结构。

表2: 在每个样本中,第一个句子是一个query,而第二个句子是它的最近邻。通过从语料中随机抽取5w个句子中,通过计算cosine相似度进行最近邻分数排序。

我们以新的setting评估了我们的向量:在学到skip-thoughts后,冻结模型,使用encoder作为一个泛化的特征抽取器(generic feature extractor)以用于特定任务。在我们的实验中,我们考虑了8个任务:句义相关性,段落检测,图像句子排序以及其它5个标准的分类benchmarks。在这些实验中,我们抽取了skip-thought向量,并训练了线性模型来评估它的表示(representations),没有任何额外的参数fine-tuning。结果说明,skip-thoughts提出的泛化表示对所有任务都很robust。

一个难点是,这样的实验会构建一个足够大的词汇表来编码句子。例如,一个从wikipedia文章中的句子可能包含了与我们的词汇表高度不一样的名词。为了解决这个问题,我们学到了一个mapping:从一个模型传递给另一个模型。通过使用cbow模型预训练好的word2vec表示,我们学到了这样的一个线性映射:将在word2vec空间中的一个词映射到encoder词汇表空间中的一个词上。学到的该mapping会使用所有单词,它们共享相同的词汇表。在训练后,出现在word2vec中的任何word,可以在encoder word embedding空间中获得一个vector。

2.方法

2.1 引入skip-ghought vectors

我们使用encoder-decoder模型框架来对待skip-thoughts。也就是说,一个encoder会将words映射到一个句子向量(sentence vector)上,一个decoder会用于生成周围的句子。在该setting中,一个encoder被用于将一个英文句子映射到一个向量。decoder接着根据该向量来生成一个关于源英文句子(source sentence)的翻译(translation)。已经探索了许多encoder-decoder pair选择,包括:ConvNet-RNN,RNN-RNN,LSTM-LSTM。源句子表示(source sentence representation)也可以通过使用一个attention机制来动态变化,用于说明任何时候只有相关的才用于翻译(translation)。在我们的模型中,我们使用一个带GRU activations的RNN encoder,以及一个conditional GRU的RNN decoder。该模型组合近似等同于神经机器翻译中的RNN encoder-decoder【11】。GRU展示了在序列建模任务中效果比LSTM要好,并且更简单。GRU units只有两个gates,不需要使用一个cell。而我们的模型则使用RNN,只要能在它之上进行BP算法,任何encoder和decoder可以被使用。

假设我们给定了一个句子的tuple:。假设表示了句子中的第t个word,表示它的word embedding。我们将模型描述成三部分:encoder,decoder,目标函数。

Encoder:假设是句子中的words,其中N表示在句子中的words数目。在每个step中,encoder会产生一个hidden state:,它可以解释成序列的表示(representation)。hidden state:可以表示整个句子。

为了encode一个句子,我们对下面的等式进行迭代(这里去掉了下标i):

… (1)

… (2)

… (3)

…(4)

其中 是在时间t提出的状态更新,是update gate,是reset gate()表示一个component-wise product。两个update gates会采用0到1间的值。

Decoder: decoder是一个神经语言模型,它的条件是encoder output 。该计算与encoder相似,除了我们引入了矩阵,以及C,它们被用于偏置由句子向量计算得到的update gate,reset gate和hidden state。一个decoder会被用于下一个句子,而第二个decoder被用于前一句子。Separate参数被用于每个decoder,除了词汇矩阵V,它的权重矩阵会连接decoder的hidden state,以便计算在词上的一个分布。我们在下一个句子上描述decoder,通过一个在前一句子上的类似计算得到。假设表示decoder在时间t的hidden state。对下面的等式进行迭代(丢掉下标i+1):

…(5)

…(6)

…(7)

…(8)

给定,单词的概率给出了前(t-1) words,encoder vector为:

…(9)

其中,表示V的行,对应于word 。对于前面句子可以做一个类似的计算。

目标函数。给定一个tuple ,目标优化为:

…(10)

总的目标函数是对所有这样的training tuples进行求和。

2.2 词汇表膨胀

现在,我们会描述如何将我们的encoder的词汇表扩展到那些在训练期间未见过的词上。假设我们有个被训练的模型引入了词表示(word representations),假设表示了RNN的词向量空间。我们假设词汇表更大。我们的目标是构建一个mapping f: ,它由一个矩阵W进行参数化,比如:,其中。受[15]的启发,它会学到在词空间转移之间的线性映射,我们为矩阵W求解一个非正则的L2线性回归loss。这样,对于编码中的句子,任何来自的词可以被映射到

3 实验

在我们的实验中,我们在BookCorpus dataset上评估了我们的encoder作为一个通用的feature extractor的性能。实验setup如下:

  • 使用学到的encoder作为一个feature extractor,抽取所有句子的skip-thought vectors
  • 如果该任务涉及到计算句子对(pairs of sentences)之间的分数,会计算pairs间的component-wise features。
  • 在抽取的features上训练一个线性分类器,在skip-thoughts模型中没有任何额外的fine-tuning或者backpropagation。

我们限定在线性分类器主要出于两个原因。第一个是为了直接评估计算向量的representation quality。如果使用非线性模型可能会获得额外的性能增益,但这超出了我们的目标。再者,它可以允许更好地分析学到的representations的优点和缺点。第二个原因是,重现(reproducibility)很简单。

3.1 训练细节

为了引入skip-thought vectors,我们在我们的book corpus上训练了两个独立的模型。一个是带有2400维的unidirectional encoder,它常被称为uni-skip。另一个是一个bidirectional model,forward和backward每个各1200维。该模型包含了两个encoder,它们具有不同的参数:一个encoder会给出正确顺序的句子,另一个会给出逆序的句子。输出接着被拼接形成一个2400维的向量。我们将该模型称为bi-skip。对于训练,我们会初始化所有的recurrent矩阵:进行正交初始化。non-recurrent weights则从一个[-0.1, 0.1]的均匀分布上进行初始化。使用mini-batches的size=128, 如果参数向量的norm超过10, 梯度会被裁减(clip)。我们使用Adam算法进行optimization。模型会被训练两周。另外作为一个额外的试验,我们使用一个组合模型导出了试验结果,包含了uni-skip和bi-skip,会生成4800维的向量。我们称该模型为combine-skip。

在被模型被训练后,我们接着使用词汇扩展,将word embedding映射到RNN encoder空间上。会使用公开提供的CBOW word vectors[2]。被训练的skip-thought会有一个词汇size=20000个词。在从CBOW模型中移除多个word样本后,会产生一个词汇size=930911个词。这样,即使被训练的skip-thoughts模型具有20000个词,在词汇表扩展后,我们可以对930991个可能的词进行成功编码。

由于我们的目标是将skip-thoughts作为一个通用的feature extractor进行评估,我们将文本预处理保持最低水平。当编码新句子时,除了基本的tokenization,不会有额外的预处理。这样做可以测试我们的vectors的健壮性。作为一个额外的baseline,我们也会考虑来自uni-skip模型学到的word vectors的平均(mean)。我们将该baseline称为bow。这会决定着在BookCorpus上训练的标准baseline的效果。

3.2 语义相关性

3.3 段落检测

3.4 Image-sentence ranking

3.5 Classification benchmarks

3.6 skip-thoughts可视化

t-sne.

参考

Convolutional Neural Networks for Sentence Classification

关于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则会很快!

参考