Candidate Sampling介绍

Reading time ~1 minute

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

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

“穷举(Exhaustive)”训练法,比如:softmax和logistic regression需要我们为每个训练样本,每个类去计算F(x,y)。当很大时,计算开销会很大。

“候选采样(Candidate Sampling)”训练法,涉及到构建这样一个训练任务:对于每个训练样本,我们只需要为候选类评估F(x,y)。通常,候选集合是target classes的union,它会随机选择对(其它)classes 进行抽样。

随机样本可能或不可能依赖于和/或

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

图1

  • : 被定义为:给定context x,在抽样classes的集合中,根据抽样算法得到class y的概率(或:期望count)。
  • :是一个任意函数(arbitrary function),不依赖于候选类(candidate class)。由于softmax涉及到一个归一化(normalization),对这种函数的求和不会影响到计算概率。
  • logistic training loss=
  • softmax training loss =
  • NCE 和Negatvie Sampling可以泛化到是一个multiset的情况。在这种情况中,表示在中y的期望数(expected count)。相似的,NCE,Negative Sampling和Sampled Logistic可以泛化到是一个multiset的情况。在这种情况下,表示在中y的期望数(expected count)。

Sampled Softmax

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

假设我们有一个单标签问题(single-label)。每个训练样本包含了一个context以及一个target class。我们将作为:给定context x下,一个target class y的概率。

我们可以训练一个函数F(x,y)来生成softmax logits——也就是说,给定context,该class相对log概率:

其中,K(x)是一个任意函数,它不依赖于y。

在full softmax训练中,对于每个训练样本,我们会为在中的所有类计算logits 如果类L很大,计算很会昂贵

在”Sampled Softmax”中,对于每个训练样本我们会根据一个选择抽样函数来选择一个关于“sampled” classese的小集合。每个被包含在中的类,它与概率完全独立。

我们创建一个候选集合,它包含了关于target class和sampled classes的union:

我们的训练任务是为了指出:在给定集合上,在中哪个类是target class

对于每个类,给定我们的先验,我们希望计算target class y的后验概率。

使用Bayes’ rule:

[bayes]{https://math.stackexchange.com/questions/549887/bayes-theorem-with-multiple-random-variables}

…(b)

得到:

接着,为了计算,我们注意到为了让它发生,可以包含y或也可以不包含y,但必须包含所有其它元素,并且必须不包含在任意classes。因此:

其中,是一个与y无关的函数。因而:

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

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

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

参考

https://www.tensorflow.org/extras/candidate_sampling.pdf

淘宝embedding介绍

阿里在KDD 2018上开放了它们的方法:《Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba》, 我们来看下:# 介绍互联网技术持续改变着商业版图,电商变得无处不在。Alib...… Continue reading

airbnb embedding介绍

Published on November 02, 2018

Tree-based Deep Match

Published on October 12, 2018