Label Partitioning介绍

Reading time ~2 minutes

在google 发表的paper: 《Label Partitioning For Sublinear Ranking》中,有过介绍:

一、介绍

许多任务的目标是:对一个巨大的items、documents 或者labels进行排序,返回给其中少量的top K给用户。例如,推荐系统任务,比如:通过协同过滤,需要对产品(比如:电影或音乐)的一个大集合,根据给定的user profile进行排序。对于注解任务(annotation),比如:对图片进行关键词注解,需要通过给定的图片像素,给出的可能注解的一个大集合进行排序。最后,在信息检索中,文档的大集合(文本、图片or视频)会基于用户提供的query进行排序。该paper会涉及到实体(items, documents, 等),被当作labels进行排序,所有上述的问题都看成是标签排序问题(label ranking problem)。在机器学习界中,提出了许多强大的算法应用于该领域。这些方法通常会通过对每个标签(label)依次进行打分(scoring)后根据可能性进行排序,可以使用比如SVM, 神经网络,决策树,其它流行方法等。我们将这些方法称为标签打分器(label scorers)。由于对标签打分是独立进行的,许多这些方法的开销与label的数量上是成线性关系的。因而,不幸的是,当标签数目为上百万或者更多时变得不实际,在serving time时会很慢。

本paper的目标是:当面临着在现实世界中具有海量的labels的情况时,让这些方法变得实用。这里并没有提出一种新方法来替换你喜欢的方法,我们提出了一个”wrapper”方法,当想继续维持(maintaining)或者提升(improve) accuracy时,这种算法能让这些方法更容易驾驭。(注意,我们的方法会改善测试时间,而非训练时间,作为一个wrapper方法,在训练时实际不会更快)

该算法首先会将输入空间进行划分,因而,任意给定的样本可以被映射到一个分区(partition)或者某分区集合(set of partitions)中。在每个分区中,只有标签的一个子集可以由给定的label scorer进行打分。我们提出该算法,用于优化输入分区,以及标签如何分配给分区。两种算法会考虑选择label scorer,来优化整体的precision @ k。我们展示了如何不需考虑这些因素,比如,label scorer的分区独立性,会导致更差的性能表现。这是因为当标签分区时(label partitioning),对于给定输入,最可能被纠正(根据ground truth)的是labels的子集,原始label scorer实际上表现也不错。我们的算法提供了一个优雅的方式来捕获这些期望。

本paper主要:

  • 引入通过label partitioning,在一个base scorer上进行加速的概念
  • 对于输入划分(input partitioning),我们提供了一个算法来优化期望的预测(precision@K)
  • 对于标签分配(label assignment),我们提供了一个算法来优化期望的预测(precision@K)
  • 应用在现实世界中的海量数据集,来展示该方法

二、前置工作

有许多算法可以用于对标签进行打分和排序,它们与label set的size成线性时间关系。因为它们的打分操作会依次对每个label进行。例如,one-vs-rest方法,可以用于为每个label训练一个模型。这种模型本身可以是任何方法:线性SVM,kernel SVM,神经网络,决策树,或者其它方法。对于图片标注任务,也可以以这种方法进行。对于协同过滤,一个items的集合可以被排序,好多人提出了许多方法应用于该任务,也是通常依次为每个item进行打分,例如:item-based CF,latent ranking模型(Weimer et al.2007),或SVD-based系统。最终,在IR领域,会对一个文档集合进行排序,SVM和神经网络,以及LambdaRank和RankNet是流行的选择。在这种情况下,不同于注解任务通常只会训练单个模型,它对输入特征和要排序的文档有一个联合表示,这样可以区别于one-vs-test训练法。然而,文档仍然会在线性时间上独立打分。本paper的目标是,提供一个wrapper方法来加速这些系统。

有许多算法用来加速,这些算法取决于对输入空间进行hashing,比如通过局部敏感哈希(LSH: locality-sensitive hashing),或者通过构建一棵树来完成。本文则使用分区的方法来加速label scorer。对于该原因,该方法可以相当不同,因为我们不需要将样本存储在分区上(来找到最近邻),我们也不需要对样本进行划分,而是对label进行划分,这样,分区的数目会更小。

在sublinear classification schemes上,近期有许多方法。我们的方法主要关注点在ranking上,而非classification上。例如:label embedding trees(bengio et al.,2010)可以将label划分用来正确分类样本,(Deng et al.,2011)提出一种相似的改进版算法。其它方法如DAGs,filter tree, fast ECOC,也主要关注在快速分类上。尽管如此,我们的算法也可以运行图片标注任务。

3.Label Partitioning

给定一个数据集: pairs $(x_i, y_i), i=1, …, m $. 在每个pair中,$ x_i $是输入,$ y_i $是labels的集合(通常是可能的labels D的一个子集)。我们的目标是:给定一个新的样本 $ x^{*} $, 为整个labels集合D进行排序,并输出top k给用户,它们包含了最可能相关的结果。注意,我们提到的集合D是一个”labels”的集合,但我们可以很容易地将它们看成是一个关于文档的集合(例如:我们对文本文档进行ranking),或者是一个items的集合(比如:协同过滤里要推荐的items)。在所有情况下,我们感兴趣的问题是:D非常大,如果算法随label集合的size规模成线性比例,那么该算法在预测阶段并不合适使用。

假设用户已经训练了一个label scorer: $f(x,y)$, 对于一个给定的输入和单个label,它可以返回一个real-valued型的分值(score)。在D中对这些labels进行ranking,可以对所有$ y \in D$,通过简单计算f(x,y)进行排序来执行。这对于D很大的情况是不实际的。再者,在计算完所有的f(x,y)后,你仍会另外做sorting计算,或者做topK的计算(比如:使用一个heap)。

我们的目标是:给定一个线性时间(或更差)的label scorer: f(x,y),能让它在预测时更快(并保持或提升accuracy)。我们提出的方法:label partitioning,有两部分构成:

  • (i)输入分区(input partititoner): 对于一个给定的样本,将它映射到输入空间的一或多个分区上
  • (ii)标签分配(label assignment): 它会为每个分区分配labels的一个子集

对于一个给定的样本,label scorer只会使用在相对应分区的labels子集,因此它的计算更快。

在预测时,对这些labels进行ranking的过程如下:

  • 1.给定一个测试输入x,input partitioner会将x映射到partitions的某一个集合中: $ p=g(x) $
  • 2.我们检索每个被分配到分区 $ p_j $上的标签集合(label sets):$$ L = \bigcup_{j=1}^{ p } \mathscr{L}{p_j} \mathscr{L}{p_j} \subseteq D $$是分配给分区 $ p_j $的标签子集。
  • 3.使用label scorer函数$ f(x,y) $对满足$ y \in L $的labels进行打分,并对它们进行排序来产生我们最终的结果

在预测阶段ranking的开销,已经被附加在将输入分配到对应分区(通过计算$ p=g(x) $来得到)上的开销;以及在相对应的分区上计算每个label(计算: $ f(x,y), y \in L $)。通过使用快速的input partitioner,就不用再取决于label set的size大小了(比如:使用hashing或者tree-based lookup)。提供给scorer的labels set的大小是确定的,相对小很多(例如:$ |L| « |D| $),我们可以确保整个预测过程在$ |D| $上是亚线性(sublinear)的。

3.1 输入分区(Input Partitioner)

我们将如何选择一个输入分区(input partitioner)的问题看成是:$ g(x) \rightarrow p \subseteq \mathcal{P} $,它将一个输入点x映射到一个分区p的集合中,其中P是可能的分区:$ \mathcal{P} = \lbrace 1,…,P \rbrace $。g总是映射到单个整数上,因而,每个输入只会映射到单个分区,但这不是必须的。

有许多文献适合我们的input partitioning任务。例如:可以使用最近邻算法作为input partitioner,比如,对输入x做hashing(Indyk & Motwani, 1998),或者tree-based clustering和assignment (e.g. hierarchical k-means (Duda et al., 1995),或者KD-trees (Bentley, 1975),这些方法都可行,我们只需关注label assignment即可。然而,注意,这些方法可以对我们的数据有效地执行完全非监督式划分分区(fully unsupervised partitioning),但不会对我们的任务的唯一需求考虑进去:即我们希望在加速的同时还要保持accuracy。为了达到该目标,我们将输入空间进行分区:让具有相似相关标签(relevant labels:它们通过label scorer进行高度排序)的相应样本在同一个分区内

我们提出了一种层次化分区(hierarchical partitioner)的方法,对于:

  • 一个标签打分函数(label scorer):$f(x,y)$
  • 一个训练集:$(x_i,y_i), i=\lbrace 1,…,m \rbrace $,(注:x为input,y为label)
  • 之前定义的label集合D

它尝试优化目标:precision@k。对于一个给定的训练样本$(x_i,y_i)$以及label scorer,我们定义了:

accuracy的measure(比如:precision@k)为:

以及最小化loss为:

注意,上述的f(x)是对所有labels的得分向量(f(x)与f(x,y)不同):

其中$ D_i $是整个label set上的第i个label。然而,为了衡量label partitioner的loss,而非label scorer,我们需要考虑$l(f_{g(x_i)}(x_i), y_i)$,该值为ranking时$x_i$对应的分区上的label set的loss。比如:$ f_{g(x)}(x)=(f(x,L_1),…,f(x,L_{|L|)})) $

对于一个给定的分区,我们定义它的整个loss为:

不幸的是,当训练输入分区(input partitioner)时,L(label assignments)是未知的,它会让上述的目标函数不可解(infeasible)。然而,该模型发生的errors可以分解成一些成分(components)。对于任意给定的样本,如果发生以下情况,它的precision@k会收到一个较低值或是0:

  • 在一个分区里,相关的标签不在该集合中
  • 原始的label scorer在排第一位的分值就低

当我们不知道label assignment时,我们将会把每个分区上labels的数目限制在一个相对小的数($ |L_j|«|D| $)。实际上,我们会将考虑两点来定义标签分区(label partitioner):

  • 对于共享着高度相关标签的样本,应被映射到相同的分区上
  • 当学习一个partitioner时,对于label scorer表现好的样本,应被优先(prioritized)处理

基于此,我们提出了方法来进行输入分区(input partitioning)。让我们看下这种情况:假如定义了分区中心(partition centroids) $c_i, i=1,…,P$,某种划分,它使用最接近分配的分区:

这可以很容易地泛化到层次化的情况中(hierarchical case),通过递归选择子中心(child centroids)来完成,通常在hierarchical k-means和其它方法中使用。

加权层次化分区(Weighted Hierarchical Partitioner) ,这是一种来确保输入分区(input partitioner)对于那些使用给定label scorer表现较好的样本(根据precision)进行优先处理的简单方法。采用的作法是,对每个训练样本进行加权:

实际上,一个基于该目标函数的层次化分区(hierarchical partitioner),可以通过一个“加权(weighted)”版本的 hierarchical k-means来完成。在我们的实验中,我们简单地执行一个”hard”版本:我们只在训练样本集合 $ \lbrace (x_i,y_i): \hat{l}(f(x_i),y_i) \geq \rho \rbrace $上运行k-means,取ρ = 1。

注意,我们没有使用 $ l(f_{g(x_i)}(x_i), y_i) $, 而是使用$ l(f(x_i),y_i) $,但它是未知的。然而,如果$ y_i \in L_{g(x_i)}$,则:$ l(f_{g(x_i)}(x_i), y_i) \leq l(f_D(x_i),y_i) $,否则,$ l(f_{g(x_i)}(x_i), y_i)=1$。也就是说,我们使用的proxy loss,上界逼近真实值,因为比起完整的集合,我们只有很少的label,因而precision不能降低——除非真实label不在分区中。为了阻止后面的情况,我们必须确保具有相似label的样本在同一个分区中,我们可以通过学习一个合适的metrics来完成。

加权嵌入式分区(Weighted Embedded Partitioners), 在上述构建加权层次式分区器(weighted hierarchical partitioner)时,我们可以更进一步,引入约束(constraint):共享着高度相关labels的样本会被映射到同一个分区(partitioner)上。编码这些constraint可以通过一种metric learning阶段来完成(Weinberger et al., 2006).。

接着,你可以学习一个input partitioner,通过使用上面的weighted hierarchical partitioner目标函数,在要学的”embedding”空间上处理:

然而,一些label scorer已经学到了一个latent “embedding” space。例如,SVD和LSI等模型,以及一些神经网络模型(Bai et al., 2009). 在这样的case中,你可以在隐空间(latent space)上直接执行input partitioning,而非在输入空间上;例如:如果label scorer模型的形式是:$ f(x,y)= \Phi_{x}(x)^T \Phi_{y}(y) $,那么partitioning可以在空间 $ \Phi_x(x) $上执行。这同样可以节省计算两个embeddings(一个用于label partitioning,一个用于label scorer)的时间,在特征空间中的进一步分区则为label scorer调整。

3.2 Label Assignment

本节将来看下如何选择一个L(label assignment)。

  • 训练集$ (x_i,y_i), i=1,…,m $,label set为:D
  • input partitioner: g(x),使用之前的方式构建
  • 线性时间label scorer: f(x,y)

我们希望学到label assignment: $ L_j \subseteq D $,第j个分区对应的label set。我们提出的label assignment方法会应用到每个分区中。首先,来考虑下优化precision@1的情况,这种简化版的case中,每个样本只有一个相关的label。这里我们使用索引t来索引训练样本,相关的label为$ y_t $。我们定义:$ \alpha \in \lbrace 0,1 \rbrace^{|D|}$,其中$ \alpha_{i} $决定着一个label $ D_i $是否会被分配到该分区上($ \alpha_{i}=1 $),或不分配($ \alpha_{i}=0 $)。这里的$ \alpha_{i} $就是我们希望优化的变量。接下去,我们通过给定的label scorer对rankings进行编码:

  • $ R_{t,i} $是对于样本t的label i的rank分值:
  • $ R_{t,y_t} $是样本t的true label的rank分值

我们接着将需要优化的目标函数写出来:

…(1)

服从:

…(2)

…(3)

其中,C是分配给该分区的label数。对于一个给定的样本t,为了最大化precision@1,需满足两个条件:

  • (1) true label必须被分配给该分区
  • (2) true label必须是所有被分配labels上排序分值最高的

我们可以看到,等式1可以精确计算precision@1,因为项$ \alpha_{y_t} $和$ (1-max_{R_{t,i}<R_{t,y_t}} \alpha_{i}) $ 会对这两个条件各自进行measure。我们的目标函数会统计训练样本数precision@1。

有意思的是,注意,label partitioning的性质意味着:

  • (i) 如果训练样本t在原始的label scorer上标记不正确,但由于高度不相关的label不会被分配到该分区上,会被label partitioner正确标注
  • (ii) 原始的label scorer可以正确标注样本,但由于相关的label没有被分配到该分区上,会被label partitioner标注不正确

该优化问题,尽可能地将多个相关的label放在同一分区中,并且尽可能消除尽可能混淆的labels(高排序值但不正确),如果通过移除它们,更多的样本会被正确标注。如图1所示:

图1: 如何从D中选择2个labels的label assignment问题,只考虑它的precision@1。这里的$ R_i $是样本排序后的labels(粗体为true labels)。当选择为sky时,会正确预测样本1和2;而对于样本3-5,sky比true labels的排序还要高。最优的选择是car和house,它们在样本3-5中可以被正确预测,因为所有有更高排序但不相关labels(higher-ranked irrelevant labels)会被抛弃掉。这种选择问题就是我们在label assignment任务中要面临的挑战。

不幸的是,等式2的二元限制(binary constraint)致使等式(1)的最优化变得很难,但我们可以将约束放松些:

…(4)

$ \alpha $的值不再离散(discrete),我们不会使用等式(3)的约束,但在训练后会对连续值$ \alpha_{i}$做排序,会采用最大的C label作为分区的成员。

我们将上述泛化成pricision@k(k>1)的情况。如果至少一个“不相关(violating)”的label排在相关label之上,我们必须统计排在相关label之上的violations的数目。回到未放松约束的最优化问题上,我们有:

…(5)

服从:

…(6)

这里对于precision@k的优化,如果 r<k,我们可以简单地取$ \Phi(r) = 0 $,否则取1。

我们已经讨论了具有一个相关标签的情况,但在许多情况下,样本具有多个相关标签的情况是很常见的,它可以使得loss的计算变得稍微更具挑战性些。我们回到precision@1的情况。在这种情况下,原始的目标函数(等式(1))将返回为:

…(7)

服从:

…(8)

这里,$ y_t $包含着许多相关标签 $ y \in y_t $,如果它们中的所有都是排在前面的(top-ranked),那么会得到一个precision@1为1,这样我们可以取 $ max_{y \in y_t}$

我们可以结合等式(5)和等式(7)来形成一个关于precision@k的cost function,用于multi-label的训练样本上。为了更适合优化,我们使用一个sigmoid来将在等式(7)中的约束$max_{y \in y_t}$放松到一个均值和近似值 $ \Phi(r) $:

我们的目标接着变成:

…(9)

服从:

…(10)

对于单个样本,期等的目标是一个相关label出现在top k中。然而,当penalty不会影响真实排序位置的情况下不成立(例如:我们原始的cost等价于在位置k+1的排序,或者在位置$|D|$的位置)。早前我们希望那些label scorer的执行很差的样本降低其重要性。为了达到该目的,我们引入了一个带加权项(term weighting)的样本,通过使用原始label scorer得到的相关label排序的反序来实现,等式(4)和等式(9)变为:

这里我们作了简化:$w(R_{t,y}) = (R_{t,y})^{\lambda}, \lambda \geq 0 $,在我们的试验中,设置$\lambda=1$(该值越高会抑制具有更低排序的相关label的样本)。这些等式表示了label assignment objective的放宽条件版本的最终形式,可以使用SGA(随机梯度上升:A: ascent)进行优化。

最优化注意事项(Optimization Considerations) 我们考虑这样的情况,被选中的输入分区g(x),表示每个输入x映射到单个分区上。每个分区的label assignment问题是独立的,这允许它们可以并行的求解(例如:使用MapReduce框架)。为了进一步减小训练时间,对于每个分区我们在完整label set上的一个子集上进行优化(例如:选择 $ \hat{D} \subseteq D, C < |\hat{D}| < |D| $)。对于每个分区,我们选择$ \hat{D} $:它是在该分区的训练样本中使用原始label scorer进行排序的最高排序的相关label。在所有的实验中,我们设置$ | \hat{D} | = 2C $。注意,在我们的实验中,我们发现设置成$ | \hat{D} | = 2C $后减少参数集的size,影响可忽略不计。原因是,任何分区中在任何训练样本中,在D中大部分labels不会作为相关labels出现。因为这样的labels不会接受任何正值的梯度更新。

统计Heuristic baseline 通过比较我们提出的label assignment的最优化,在我们的实验中,我们也考虑了一个更简单的Heuristic:只考虑等式(1)的第一项,例如:$ max_{\alpha} \sum_{t} \alpha_{t_t}$。这种情况下,最优化可以简化为:只需统计在分区中的每个true label的出现次数,并让C保持为最多的labels。这种基于统计的assignment提供了一个很好的baseline,来对比我们提出的优化。

4.实验

4.1 图像注解

首先使用ImageNet数据集来测试图片注解任务。ImageNet是一个很大的图片数据集,它将人口验证通过的图片与WordNet的概念相绑定。我们使用Spring 2010的版本,它具有9M的images,我们使用:10%用于validation, 10%用于test,80%用于training。该任务会对15589个可能的labels做rank,它们的范围从animals(“white admiral butterfly”)到objects(“refracting telescope”).

…【略】

4.2 视频推荐

从一个大型在线视频社区给用户推荐视频。上百万最流行的视频被认为是集合D,我们的目标是,对一个给定用户排序这些视频,并提供给该用户相关的视频。训练数据的格式中每个训练pair都基于一个匿名用户。对于每个用户,输入$x_i$是表示他的偏好的一个特征集合。这些特征通过聚合每个用户所感兴趣的所有视频的主题来生成。这些主题集合接着被聚类成各特征列。有2069个这样的聚类特征列(clusters)来表示用户,其中任何时候有10个聚类特征列是表示活跃的(意思:每个用户大致都有10个以上的特征)。label $y_i$是已知相关视频的一个集合。该数据集包含了1亿的样本,每个样本具有2069个输入特征,平均接近有10个相关视频。我们设置另外50w的样本用于validation,1M样本用于test。

我们的baseline label scorer $W_{SABIE}$在P@10上对比于Naive Bayes,它给出了108%的提升。因而,baseline已经足够强了。我们接着使用hierarchical k-means,它具有10000个分区,以及许多种label assignment set sizes,结果如表2所示。我们的方法可以提速990x倍,而在label scorer上的P@10提升13%。该结果和我们见到的一样重要:我们使用的label scorer是一个线性模型,其中label partitioner在某种程度上是“非线性”的:它可以在输入空间的不同分区上更改label sets——这可以纠正原始scorer的错误(在某种程度上,这有点像个re-ranker)。注意基于最优化的label partitioner比counting heuristic效果要好。

表2

我们的label partitioner被用于视频推荐系统中,用来尝试提升一个比较强的baseline ML系统。在我们的上述实验中使用的是precision,但precision只是一个online metrics,而在观看期视频的ctr作为衡量更好。当在实际系统中评估label partitioner时,它可以在ctr和观看时长(接近2%)上获得极大的提升。注意,我们不会将它与原始的label scorer做比较,那种情况下使用它是不可行的。

5.结论

我们提出了一种“wrapper”方法来加速label scoring rankers。它使用一种新的优化法:通过学习一个input partitioning和label assignment,来胜过其它baseline。该结果与原始的label scorer效果相似(或者效果更好),同时运行更快。这使得该技术被用于现实的视频推荐系统中。最终,我们我们觉得提出的label assignment是解决该问题的好方法,input partitioners间的巨大性能差距意味着,将来还有重大问题需要解决。

参考

Label Partitioning For Sublinear Ranking

TrueSkill排名系统

前一阵子的AlphaGo和围棋很火,当时的AlphaGo在战胜kejie后排名世界第一;最近王者荣耀很火,它的排位赛机制中的内部匹配系统也十分令人诟病。不管是在围棋赛场,还是在多人竞技电子赛场上,排位系统是很重要的。常见的算法有:Elo,TrueSkill™。Elo在上一篇...… Continue reading

Elo排名系统

Published on August 21, 2017

基于Wide & Deep Learning的推荐系统

Published on December 20, 2016