Candidate Sampling介绍

Reading time ~2 minutes

1.介绍

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

1.1 F(x,y)

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

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

1.2

  • target classes(正样本):
  • candidate classes(候选样本):
  • randomly chosen sample of classes(负样本):

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

随机样本可以依赖(或者不依赖)和/或

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

图1

  • : 被定义为:给定context x,根据抽样算法在sampled classes的集合中得到class y的概率(或:expected 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——也就是说,该class在给定context上的相对log概率(relative log probabilities):

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

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

抽样函数:

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

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

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

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

使用Bayes’ rule:bayes

…(b)

得到:

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

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

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

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

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

#

以tensorflow中的tf.random.log_uniform_candidate_sampler为例。

它会使用一个log-uniform(Zipfian)base分布。

该操作会随样从抽样分类(sampled_candidates)中抽取一个tensor,范围为[0, range_max)。

sampled_candidates的元素会使用base分布被无放回投样(如果:unique=True),否则会使用有放回抽样。

对于该操作,基础分布是log-uniform或Zipf分布的一个近似:

当target classes近似遵循这样的一个分布时,该sampler很有用——例如,如果该classes以一个字母序表示的词语,并以频率降序排列。如果你的classes没有通过词频降序排列,就不需要使用该op。

另外,该操作会返回tensors: true_expected_count,

sampled_softmax_loss

def _compute_sampled_logits(weights,
                            biases,
                            labels,
                            inputs,
                            num_sampled,
                            num_classes,
                            num_true=1,
                            sampled_values=None,
                            subtract_log_q=True,
                            remove_accidental_hits=False,
                            partition_strategy="mod",
                            name=None,
                            seed=None):
    # 核心代码实现:
    if isinstance(weights, variables.PartitionedVariable):
        weights = list(weights)
    if not isinstance(weights, list):
        weights = [weights]

    # labels_flat:  batch_size.
    with ops.name_scope(name, "compute_sampled_logits",
                        weights + [biases, inputs, labels]):
        if labels.dtype != dtypes.int64:
            labels = math_ops.cast(labels, dtypes.int64)

        labels_flat = array_ops.reshape(labels, [-1])

    # 抽取num_sampled个样本.
    if sampled_values is None:
        sampled_values = candidate_sampling_ops.log_uniform_candidate_sampler(
            true_classes=labels,
            num_true=num_true,
            num_sampled=num_sampled,
            unique=True,
            range_max=num_classes,
            seed=seed)

    # 这三个值不会进行反向传播
    sampled, true_expected_count, sampled_expected_count = (array_ops.stop_gradient(s) for s in sampled_values)

    # 转成int64
    sampled = math_ops.cast(sampled, dtypes.int64)

    # label + sampled (labels基础上拼接上抽样出的labels)
    all_ids = array_ops.concat([labels_flat, sampled], 0)

    # 合并在一起,使用all_ids一起进行查询
    all_w = embedding_ops.embedding_lookup(
        weights, all_ids, partition_strategy=partition_strategy)

    # 分割出label的weight.
    true_w = array_ops.slice(all_w, [0, 0],
                             array_ops.stack(
                                 [array_ops.shape(labels_flat)[0], -1]))

    # 分割出sampled weight.
    sampled_w = array_ops.slice(
        all_w, array_ops.stack([array_ops.shape(labels_flat)[0], 0]), [-1, -1])

    # user_vec * item_vec
    sampled_logits = math_ops.matmul(inputs, sampled_w, transpose_b=True)

    # bias一起查询.
    all_b = embedding_ops.embedding_lookup(
        biases, all_ids, partition_strategy=partition_strategy)

    # true_b is a [batch_size * num_true] tensor
    # sampled_b is a [num_sampled] float tensor
    true_b = array_ops.slice(all_b, [0], array_ops.shape(labels_flat))
    sampled_b = array_ops.slice(all_b, array_ops.shape(labels_flat), [-1])

    # element-wise product.
    dim = array_ops.shape(true_w)[1:2]
    new_true_w_shape = array_ops.concat([[-1, num_true], dim], 0)
    row_wise_dots = math_ops.multiply(
        array_ops.expand_dims(inputs, 1),
        array_ops.reshape(true_w, new_true_w_shape))

    # true label对应的logits, bias.
    dots_as_matrix = array_ops.reshape(row_wise_dots,
                                       array_ops.concat([[-1], dim], 0))
    true_logits = array_ops.reshape(_sum_rows(dots_as_matrix), [-1, num_true])
    true_b = array_ops.reshape(true_b, [-1, num_true])


    true_logits += true_b
    sampled_logits += sampled_b

    # 减去先验概率.
    if subtract_log_q:
      # Subtract log of Q(l), prior probability that l appears in sampled.
      true_logits -= math_ops.log(true_expected_count)
      sampled_logits -= math_ops.log(sampled_expected_count)

    # 输出logits,拼接在一起.
    out_logits = array_ops.concat([true_logits, sampled_logits], 1)

    # 输出的labels.
    out_labels = array_ops.concat([
        array_ops.ones_like(true_logits) / num_true,
        array_ops.zeros_like(sampled_logits)
    ], 1)

    return out_logits, out_labels

得到logits和labels后,就可以计算softmax_cross_entropy_with_logits_v2了。

log_uniform_candidate_sampler

1
2
3
4
5
6
7
8
9
tf.random.log_uniform_candidate_sampler(
true_classes,
num_true,
num_sampled,
unique,
range_max,
seed=None,
name=None
)

使用一个log-uniform(Zipfian)的基础分布来采样classes集合。

该操作会对一个sampled classes(sampled_candidates) tensor从范围[0, range_max)进行随机抽样。

sampled_candidates的elements会从基础分布进行无放回抽样(如果unique=True)或者有放回抽样(unique=False)。

对于该操作的base distribution是一个近似的log-uniform or Zipfian分布:

当target classes近似遵循这样的一个分布时,该sampler很有用——例如,如果该classes表示字典中的词以词频降序排列时。如果你的classes不以词频降序排列,无需使用该op

另外,该操作会返回true_expected_count和sampled_expected_count的tensors,它们分别对应于表示每个target classes(true_classes)以及sampled classes(sampled_candidates)在sampled classes的一个平均tensor中期望出现的次数。这些值对应于在上面的。如果unique=True,那么它是一个post-rejection概率,我们会近似计算它。

paper2

另外在paper 2《On Using Very Large Target Vocabulary for Neural Machine Translation》的第3节部分,也做了相应的讲解。

paper2 第3节

在该paper中,提出了一种model-specific的方法来训练具有一个非常大的目标词汇表(target vocabulary)的一个神经网络机器翻译(NMT)模型。使用这种方法,训练的计算复杂度会是target vocabulary的size的常数倍。另外,该方法允许我们高效地使用一个具有有限内存的快速计算设备(比如:一个GPU),来训练一个具有更大词汇表的NMT模型。

训练一个NMT的计算低效性,是由等式(6)的归一化常数引起的。为了避免计算该归一化常数的成长复杂度(growing complexity),我们这里提出:在每次更新时使用target vocab的一个小子集。提出的方法基于早前Bengio 2008的工作。

等式(6), next target word的概率:

…(6)

其中Z是归一化常数(normalization constant):

…(7)

假设我们考虑在等式(6)中output的log-probability。梯度的计算由一个正部分(positive part)和负部分(negative part)组成:

…(8)

其中,我们将energy 定义为:

梯度的第二项(negative)本质上是energy的期望梯度:

…(9)

其中P表示

提出的方法主要思想是,通过使用少量samples进行importance sampling来逼近该期望,或者该梯度的负项。给定一个预定义的分布Q和从Q中抽取的一个样本集合,我们使用下式来逼近等式(9)中的期望:

…(10)

其中:

…(11)

该方法允许我们在训练期间,使用target vocabulary的一个小子集来计算归一化常数,每次参数更新时复杂度更低。直觉上,在每次参数更新时,我们只会更新与correct word 以及在中的sampled words相关的vectors。一旦训练完成,我们可以使用full target vocabulary来计算每个target word的output probability。

尽管提出的方法可以天然地解决计算复杂度,使用该方法本质上不能在每个句子对(sentance pair:它们包含了多个target words)更新时保证参数数目。

实际上,我们会对training corpus进行分区(partition),并在训练之前为每个分区(partition)定义一个target vocabulary子集。在训练开始之前,我们会顺序检查训练语料中的每个target sentence,并累积唯一的target word,直到唯一的target words达到了预定义的阀值。然后在训练期间将累积的vocabulary用于corpus的partition。我们会重复该过程,直到达到训练集的结尾。假设对于第i个partition的target words的子集用表示。

这可以理解成,对于训练语料的每个partition具有一个单独的分布。该分布会为在子集中包含的所有target words分配相等的概率质量(probability mass),其它words则具有为0的概率质量,例如:

提议分布(proposal distribution)的选择会抵消掉correction term——来自等式(10)-(11)中importance weight的,使得该方法等价于,使用下式来逼近等式(6)中的准确output probability:

需要注意的是,Q的这种选择会使得estimator有偏。

对比常用的importance sampling,提出的该方法可以用来加速,它会利用上现代计算机的优势来完成matrix-matrix vs. matrix-vector乘法。

参考

facebook DLRM介绍

# 介绍facebook在2019在《Deep Learning Recommendation Model forPersonalization and Recommendation Systems》。# 摘要facebook开发了一种SOTA的深度学习推荐模型(DLRM)...… Continue reading

ali reranking模型介绍

Published on October 15, 2019

youtube MMoE排序系统

Published on October 11, 2019