论文《Label Partitioning For Sublinear Ranking》是由Jason Weston等人在2013年发表在第三十届国际机器学习大会上。
1.简介
现实中许多任务需要对巨大的目标量进行打分并且排序。例如在推荐系统里，响应一个用户的请求时，可能需要对数百万个视频打分并排序，然后把前k个视频呈现给用户。针对这类问题已经提出了许多强大的算法，通常这些方法是通过依次对每个标签评分并排序。由于独立地给标签评分，这些方法中的许多方法在标签数量上都是线性的，所以当标签的数量达到数百万或更多时，这些算法不能够满足实时性。
本文提出一种基于标签分割的算法，只需要套在原有算法的外层，就可以实现亚线性排序；目的是使这些方法可用于带有大量标签的实际问题。不是提出了替代的算法，而是提出了“包装器”方法，该方法是使这些方法易于处理，同时保持甚至在某些情况下甚至提高准确性的算法。（该方法缩短了测试时间，而不是训练时间，并且由于包装方法实际上训练起来并不快。）
2.算法
假设我们有一个数据集，，其中
是输入(也称作样本，example)，
是所有标签的集合，
是
的子集。我们的目标是给定一个新样本
的情况下，对
中所有标签排序，并将前 k 个最相关的标签呈现给用户。举个例子，在视频推荐系统里，
是某个状态（搜索历史，观看历史，地理位置 )下的用户，D是整个视频库，
是和用户最相关的视频集合，假设
表示
中视频的数量。假设在响应用户
的请求时，我们需要给用户呈现 k=10 个视频，假设和用户最相关的视频集为
，如果
，那我们希望这 k 个视频都属于
，如果
，我们希望
中所有视频都在这k个视频里。
假设传统的方法有一个打分函数，可以对一个样本标签对进行打分，这里的y是指单个标签。每次有用户请求时，都需要对视频库中的每个视频打分，如果视频库是百万量级甚至以上，显然耗时太多，不能满足实时性。因此，本文提出了一种标签分割的算法，包含两个部分：
（1）输入分割：给定一个输入样本，将其映射成一个key，这里表示为
（2）标签分配：为每个key分配一个标签子集
另一个叫 Weighted Embedding Partitioner，它是通过对训练样例的转换使得 label 相同的训练样例尽可能被划分到一个集合中去，即作采用embedding的方法，将标签相似的样本映射到相似的空间，：
其中
因此，可以写出目标函数为：
其中，
（2）然后讨论 k>1 的情况，每个样本
其中
（4）最后讨论通用情况，即k>1，每个样本
则目标函数可表示为：
但是注意到式(9)中，如果相关标签排在第k+1位，和排在最后一位的损失是一样的，这是不可优化的，因此，引入标签的排名作为分母，即
其中，
然后使用随即梯度下降法去优化该目标函数就好了。
3.总结
本文提出了一种“包装器”方法来加快标签得分排名。它采用了一种新颖的优化方法来进行输入分割和标签分配。结果与原始标签评分器相似或更好，但速度快了几个数量级，这使该技术可以在数量级很大的视频推荐系统中使用。
网友评论