d0evi1 Reading time ~1 minute

关于itemcf的topk问题，我们看下Mohammad Khabbaz的paper《TopRecs: Top-k Algorithms for Item-based Collaborative Filtering》：

介绍

现代信息系统的items数增长很快。对普通用户来就，浏览大量collections并发现合适感兴趣的item很重要。推荐系统可以帮助用户发现个性化兴趣它们可以利用用户评分来做出预测。大多数流行的推荐会使用CF。CF方法会输入一个巨大的稀疏矩阵（它包含了在items上的用户评分），接着通过在candidate items上预测它的未知评分，来为current user或active user输出最相关的items。大多数CF的研究主要关注提升预测的accuracy。很明显，在accuracy之外，可扩展性(scability)也是很重要的一点，因为在当今推荐系统中用户数和items数增长很快。举个例子，Google News这样的系统每天都有上百万用户，每秒都会增长许多news feeds数。Netflix和Amazon则具有大量items和users。新的ratings、items、users会不断被添加到ratings matrix中，并需要对top-k推荐做出影响。为所有users、或者登陆的active user重复计算top-k items的列表开销是很大的，因此需要高效的top-k算法。

CF的最流行方法是itemCF。它可以提供高质量的top-k结果。它的主要思想是：计算一个similarity matrix，相应的entries对应于pairwise item相似度（Person相关系数是一种流行选择）。为active users从头到尾计算推荐开销很大，因此，CF-based推荐通常会预计算好item-wise相似度，并以一种可快速检索的方式存储它们。根据该方法，预测active user (\(u_i\))在item (\(v_j\))上的得分的任务包含了以下steps：

  • 1.为\(v_j\)寻找N个最相似的items（被\(u_i\)评分过），这被称为\(v_j\)在\(u_i\) profile中的N个最近邻。
  • 2.基于在这N个items上的用户评分，通过相似度计算一个加权平均

一旦item scores被预测，那些带有最高预测得分的items会提供服务给用户。寻找top-k items的高效算法是项大挑战。在经典top-k settings中，对于m个features每个feature上的items得分可以从m个score-sorted lists中得到。这个问题的挑战是：设计一种可以访问最小数目items的top-k算法。该挑战可以通过TA/NRA算法族以及它的许多后代变种来解决。对比起经典的settings，在item-based CF中寻找top-k会有两个主要挑战：

  • (1) 我们需要处理：每个candidate item的聚合得分必须通过来自一个不同的lists集合(set)的entries来决定。这是因为：在一个给定user profile中，每个candidate item的N个最相似items可能不同
  • (2) 加权平均并不是一个单调聚合函数（monotone aggregate function），该特性会在经典top-k算法中常使用. 在top-k算法中有一些工作是使用非单调聚合函数的[10,18,21]，据我们所知，在top-k问题上还没有工作是使用非单调聚合函数来解决lists的多个集合的组合。

我们的目标是，设计一种可扩展的CF方法，它仍具有已知CF的accuracy。我们展示了一种基于将TA/NRA思想扩展到CF框架的直接方法，它需要非实时的预处理以及存储需求，否则会导致算法像naive算法一样不能访问尽呆能多的entries。因而，我们提出了一种新方法：它会通过两步操作（probe和explore）抽取CF中的核心计算逻辑。Probe是identifying的过程：为一个给定candidate item聚合N个lists；explore是finding的过程：在聚合的lists中寻找top-k items进行推荐。我们的方法会通过使用一个相似度阀值（similarity threshold）来让probe过程更高效。我们提出了一种probabilistic cost-based方法，将我们top-k算法的整体期望开销表示成一个关于相似度阀值的函数，并通过最小化cost来决定阀值的最佳值。

我们在核心的itemCF之上提出了一种可扩展的推荐系统，架构包含以下层（见图1）：

  • (i) 数据层（Data layer）: 包含了user/item rating matrix
  • (ii) 中间层（Intermediate layer）: 由item-item matrix组成，需要让similarity matrix时刻保持最新
  • (iii) 应用层（Application layer）: 在中间层数据之上运行的高效运行topk算法。该层会使用相似度阀值(通过cost-based最优化得到)来调用probe操作，并通过explore操作寻找top-k items

图1

top-k算法可以独立于中间层（intermediate layer），并可以访问中间层最新的数据结构。我们提出了一个two-phase top-k算法。在第一阶段，我们会基于相似度值计算一个阀值。该阀值以这样的方式进行寻找：最大化（最小化）相似度值更大（更小）的items的概率，接着该阀值会介于items的N个最近邻之间。在第一phase后，相似度矩阵的大部分会被过滤，size问题会极大缩减。第二个phase会使用剩下的值来计算要预测的ratings。我们会定义一个目标函数，它是两个phases的期望cost的一个上限，会寻找关于threhold的最优值来最小化该cost。我们会使用概率分布来建模相似度矩阵，以便进行概率分析。我们提出了一种高效算法来寻找top-k推荐。我们的贡献如下：

  • 1.为itemCF提出了一种分层系统。
  • 2.提出了两种naive算法，作为baseline来校准算法效果。
  • 3.我们展示了基于TA/NRA算法扩展的方法
  • 4.为itemCF设计了一种新的top-k算法
  • 5.根据运行时间和top-k结果质量来评估算法

2.相关工作

ItemCF和可扩展性：User-CF算法会基于N个最近邻用户(对该item评过分)来预测未知评分. 它需要计算和维护一个n x n的user-user相似度矩阵。用户数n通常大于items数m。Item-CF可以克服这个缺限。除了对可扩展性改进外，它会寻找pairwise相似度来产生更好的accuracy。在ItemCF中，一个active user在一个candidate item上的rating会基于与该用户在该candidate item相似的N个items上的rating进行预测。

top-K算法：topK算法被广泛研究。大多数相关工作构建在经典的TA/NRA算法之上。这些算法假设有一个单调聚合函数，以及一个关于多个列表的集合，在这之上执行聚合是事先知道的。对比这些算法，在我们的问题中，面临着两个主要挑战：

  • i) 我们的聚合函数不是单调的(monotone)
  • ii) 列表集合中被聚合的值是不固定的，可能会随着item间相互变化

据我们所知，许多最近工作表明，通过处理不同列表集合来聚合分值的解决非单调聚合函数的问题，在这之间没有发表过。这些情况下，主要思想是定义对于未见item（unseen objects）分值的一个上界，以及在top-k items得分上的一个下界。当前者不再大于后者时，该算法会停止。在本文中，会采用一种类似TA／RNA的方法来处理会变化列表集合中的聚合分值，。作为对比，我们提出了一种非常不同的算法来计算top-k items。

3.先决条件与Naive算法

在CF中，数据被表示成：

  • R：稀疏的\(n \times m\)矩阵
  • \(r_{ij}\)：为entry（表示在第i个user上对第j个item的评分(rating)），值采用\(\lbrace 1, 2, \cdots, C \rbrace, C>1\)来表示

主要挑战是：在R中预测missing ratings。此后，我们使用\(r_{ij}\)来表示第i个user在第j个item上已存在评分（exsiting ratings)。

  • \(u_i\)：表示第i个user(row)。注意，从行为角度看，我们可以使用row \(u_i\)表示第i个user（列也如此）
  • \(v_j\)：表示第j个item(column)
  • \(r \in u_i\)：表示一个在user \(u_i\)的row上的已存在评分（existing rating）
  • \(\hat{r}_{ij}\)：来做为active user \(u_i\)在一个candidate item \(v_j\)上的未知评分(unknown rating)的预测值。
  • \(\mu_i\)：作为被\(u_i\)评分过的items数目
  • \(\mu\)：表示被任意user评分过的items平均数目

在ItemCF中\(\hat{r}_{ij}\)的预测通常通过采用对\(u_i\)在\(v_j\)上最相似的N个items的ratings进行加权平均来求得。更正式的，我们可以使用以下公式，其中，\(N(v_j, u_i)\)表示由\(u_i\)评分的与\(v_j\)最相似的N个items的集合(其中：s为相似度)：

\[\hat{r}_{ij} = (\sum\limits_{x=1}^N s_{xj} \times r_{ix}) / ( \sum\limits_{v_y \in N(v_j,u_i)} s_{yj})\]

…(1)

待研究的问题：给定一个active user \(u_i\)，高效找出具有最高预测评分(predicted rating)的top-k个items。我们称该问题为：寻找top-k推荐。对一个candidate item \(v_j\)预测rating需要找到由\(u_i\)评分过的与\(v_j\)最相似的N个items，接着将它们的ratings使用等式(1)进行聚合。

首个天然问题是，（在top-k算法的TA/NRA family中给出了主体），我们是否采用这些算法并设计高效的top-k算法来寻找top-k推荐。我们会在第4节解决该问题。在下一节，我们会叙述两个naive算法，它们作为top-k算法的baseline。出于便利，对于一个给定item \(v_j\)，\(v_j\)的N个最近邻（nearest neighbors）意味着N个最相似的items。

3.1 Naive-1算法

对于Naive-1和Naive-2算法，我们假设：pair-wise item相似度是已知的。对于\(u_i\)来说寻找top-k items的过程如下：

  • 1.使用等式(1)为每个单独的candidate item \(v_j\)预测score。

这通常涉及到在\(u_i\)的profile中为\(v_j\)寻找N个最相似的items（例如：\(N(v_j,u_i)\)集合）。在一个关于m个items的list中找到具有最高值的K个items被称为“K-select problem”。这里，由于N的值在实际上范围是10-30，我们可以通过对该list做一个简单扫描、并维护一个优先级队列的方式来执行该任务。它的复杂度为\(O (m logN)\)。由于N通常是一个较小的数，该方法通常比一般K-select problem的最佳判断式算法（采用median of medians算法的复杂度为\(\Theta(10m)\)）更高效。

在为每个item（被\(u_i\)进行评分）找到N个最近邻后，将它们的ratings进行聚合，并计算\(\hat{r}_{ij}\)会花费\(O(N)\)的时间。因而，为单个candidate item预测得分的总开销为\(O(m logN + N)\)，为所有candidate items预测scores的开销为\(O(m^2 logN + mN)\)。实际上，通过只在由该user评分过的items list内为\(v_j\)搜索N个最近邻，可以提升性能，可以产生\(O(m \mu_i logN + mN)\)的开销，其中\(\mu_i\)是user \(u_i\)评分过的items数目。由任意给定user评分过的items的list所提供的该提升，会与评分矩阵（ratings matrix）独立进行存储。存储这样的信息会在存储上增加一个\(O(n\mu)\)的开销，其中\(\mu\)是由一个user评分过的items的平均数目。这与高效存储稀疏评分矩阵的开销同阶。我们假设可以访问该禾目禾已。

  • 2.一旦每个item的score在前一步被计算，寻找具有最高scores的k个items的时间复杂度为\(O(m logk)\)

上述算法的总运行时间为\(O([\mu_i log N + N + logk] \times m])\)。

我们可以看到，为一个给定user寻找top-k items进行推荐，会涉及到两步：

  • (i) 探测(Probe)：探测每个candidate item，以便寻找在user profile中的最相似的N个items。
  • (ii) 探索(Explore)：探索关于candidate items的list，并计算它们的scores，接着寻找具有最高scores的top-k items。

step (ii)是必要的，以便寻找到具有最好得分的k个items。对于任意item，决定它的score需要我们知道与它最相似的N个items（由step(i)得到）。

probe阶段涉及到\(O(m\mu_i logN)\)个操作，而explore阶段需要\(O(m(logk + N)))\)个操作。实际上，N的值通常为30或更小。另外，logk通常不超过5, 主要原因是我们不希望用户被太多的推荐所淹没。在probe开销中\(\mu_i\)因子的存在，表明：Naive1算法的probe部分的开销占支配地位。例如，在MovieLens数据集中，有100w个ratings，\(\mu_i\)的平均值为165. 而在Netflix数据集中，100M的ratings、500k users，每个user的ratings平均数目为200.

3.2 Naive-2算法

我们定义了一个数据结构L，除相似矩阵外的一个有序列表集合(sorted lists)，每个item各一个。L的一个schematric如图2所示。

图2

\(L_i \in L\)表示与item \(v_i\)相关的list。

  • \(L_i\)的elements：是形如(item_pointer, similarity)的pairs
  • lists以非增的相似度(与\(v_i\))进行排序；
  • item_pointer：是一个指向item所在的实际内存位置的指针，或者简化为item id。所使用的pointers在ratings matrix R以及相似列表L间的具有一个统一的items表示。
  • \(L_{ij}\)：表示list \(L_i\)的第i个entry。\(L_{ij}\)的similarity表示对于\(v_i\)的第j个最相似item。

在L中的每个有序列表通过一个优先级队列进行维护，当item相似度随时间变化时有效更新。Naive-2的算法如下：

  • 1.标记由\(u_i\)评分的所有\(\mu_i\)个items，时间复杂度为\(O(\mu_i)\)
  • 2.对于每个candidate item \(v_j\)，从该list的头部头取\(L_j\)，直到发现N个已标记items。
  • 3.计算聚合得分，并发现具有最高得分的k个items，时间复杂度为\(O(m log k)\)

总共有m个items，在它之外有\(\mu_i\)个被标记。因此，一个随机选中的item在该list上的任何位置都具有相同的概率。因此，我们可以假设：\(\mu_i\)个被标记的items被划分成\(\mu_i+1\)个buckets中。在每个bucket中的未标记items的期望数字是\((m-\mu_i)/(\mu_i+1)\)，待访问的items（直到N个已标记items被观察到）的期望数目是\(N + N \times \frac{(m-\mu_i)}{(\mu_i+1)}\) 或 \(O(Nm/\mu_i)\)，它会让算法的期望运行时间为\(O(mN(m/\mu_i) + m logk)\)。

。。。

4.经典的top-k算法

由于TA/NRA风格的算法依赖于：聚合函数是单调的，使用这样的算法的一个简单方法是：将该问题转化成单调聚合函数的问题。在等式(1)中，定义由用户\(u_i\)评分过的item \(v_x\)，对item \(v_j\)的预测评分的贡献是：\(e_j^x = s_{xj} r_{ix} / \sum_{v_y \in N(v_j,u_i)} s_{yj}\)。很容易看到预测评分是：\(\hat{r}_{ij} = \sum\limits_{v_x \in N_{(v_j,u_i)}} e_j^x\)。TA/NRA算法族可以被使用是因为：sum是一个单调聚合函数。然而，为了实现这一点，对于每个user \(u_i\)，我们需要维护N个lists来保储每个candidate item \(v_j\)的相似度以及它各自被\(u_i\)评分过的N个最近邻。为每个被评分过的candidate item发现N个最相似的items，需要\(O(nmN)\)的存储，这是过高的。除了存储之外，它还需要为每个用户的每个item保存一个最新时间的关于N个最近似的list，这在计算上开销很大。实际上，我们只需要为每个用户在进入到系统后找到top-k个推荐。

在该paper中，我们会探索高效的top-k算法，并满足高效存储需求。更特别的，最低存储需求是，评分矩阵 以及 pairwise item相似度。由于我们不想为每个user basis存储该信息，我们通常需要提供所有pairwise相似度。对应于每个item，会有一个由lists组成的数据结构，以非递增的顺序存储与其它items的相似度，可以高效存储相似度信息，我们假设：top-k算法可以访问该信息。该数据结构称为L，如图2所示，其中active user \(u_i\)会对前\(\mu_i\)个items评过分。我们会讨论关于TA/NRA算法的两种不同实现，并展示TA/NRA算法，可以访问之前通过其中一种naive算法可访问的所有entries。这可以为开发更高效算法做好准备。

更特别的，我们会考虑这样的算法：以相似度排序的方式访问在L中的columns的entries。一旦他们读取在一个candidate item和被该用户评过分的\(\mu_i\)个items其中之一个item之间的相似度时，他们会等待直到可以决定该评过分的item是否在candidate item是N个最近邻内。在为一个candidate item寻到到一个新neighbor之后，他们会更新上界和下界。最后，一旦top-k items得分的下界不低于部分观察到的objects的score的上界时，搜索停止。我们称这样的算法为“经典算法”。考虑两种类型的经典算法：

  • (i) 这种算法可以以有序方式访问L的列，对应于\(u_i\)评过分的items
  • (ii) 这种算法可以访问L的列，对应于candidate items

我们不要假设：被选中进行探测的lists的顺序，以及它们中的每个被探测到的depth。对于任意经典算法，存在许多示例：算法可以访问和naive算法一样多的实例。

定理1

假设CA表示以下方式的任意经典算法（Classic Algorithm）：它可以从L（对应被\(u_i\)评过分的items）的columns中读取相似度值。在这样的CA上的示例，可以访问同Navie-1算法一样多的entries。

证明：略

定理2

假设CA是以下方式的任意经典算法：可以从L的那些列（对应于candidate items）读取相似度值。在这样的CA上存在实例：可以访问如Naive-2一样多的entries。

证明：略

5. two-phase算法

在第3节中，在probe step和explore step之间，probe过程开销更大。为了实现高效的probe，我们描述了一个two-phase过程，它是我们的高效top-k算法的基础。

5.1 two-phase算法

使用第3节的数据结构L，并为每个entry增加第三个element进行扩展。我们将该新数据结构称为LP。特别的，在LP中，一个entry \(LP_{ij}\)是一个三元组，其中(item_pointer, similarity)与L中的elements相当。第3个element为prob，表示在L中任意比similarity高的其它相似度值的概率。尽管在相似度矩阵中提供了所有相似度，但读取所有相关相似度的开销很大。我们使用这样的概率可以在执行期间做出概率决策。做出这样的决策，我们可以避免对评过分的items的所有相似度进行访问（或者对candidate items的所有相似度），直到找到N个最近邻（与Naive-2算法不同）。因此，我们首先只读取candidate items的N个最相似items间的具有一个高概率的值（values）。通过寻到一个阀值(threshold)并使用上述prob values来过滤所有entries。接着，我们会在剩余的values间为candidate items寻找N个最近邻。对某些items来说，有可能缺失一些或所有最近邻。在这样的cases中，我们只会为这些items探测(prob)剩余的neighbors。很明显，选择合适的threhold值是很重要的。我们通过cost-based的最优化来这样做。

\(LP_{ij}.prob\)值可以通过对具有一个合适分布的similarity matrix建模来估计，后续会介绍。当我们使用一个分布来建模similarity matrix时，不需要提供prob values。作为替代，threshold可以被直接转化成一个相似度threshold。出于简洁性，我们假设给定这样的概率。注意：LP的elements包含的similarity值越高，prob值越低。因此，保持LP的列以similarities的非递增顺序进行排序，等同于保持以prob值的非递减顺序进行排序。

图3展示了two-phase过程，对于一个active user (\(u_i\))，他在/7的items评分。在图3中，最顶行的左侧，LP的三列对应于\(u_i\)评分过的items，所有entries都带有prob值低于\(\theta=0.19\)。这些lists只包含了余下的similarity值。假设N=2, 我们可以通过寻找\(v_4\)和\(v_7\)的neighbors来完成。我们已经发现\(v_5\)的最近邻，只需要在被\(u_i\)评分过的余下items（比如：\(v_1\)和\(v_2\)）上寻找第二个最近邻。对比起Naive-1算法，可以为3/4个candidate items减小以下执行时间：在被\(u_i\)评分过的所有\(\mu_i\)个items间，为所有items搜索最近邻所需要时间。然而，注意，该two-phase方法仍需要花费读取一些不相关similarity值的开销（比如：\(s_{13}\)）。另外，为\(v_5\)寻找其余neighbors需要至少需要对由用户评分过的\(\mu_i\)个items进行一次扫描。为了进行剪枝，强调选择合适的threshold很重要。我们可以通过cost-based optimization来完成。

图3也展示了Naive-2算法是如何工作的。在特别的示例中，被评分过的几乎一半items赞同该算法。然而，该two-phase过程只会访问11个entries，而Naive-2为16, Naive-1为12. 在该示例中，我们只是展示了该two-phase过程是如何工作的，以及需要为cost-base optimization选择概率阀值。5.2节中我们会比较two-phase算法与Naive-1和Naive-2的期望开销。

根据probe step的两个phases，expore step则用于寻找top-k items。

为了对two-phase过程与经典top-k算法进行比较。在图3中，假设\(v_5\)是top-k items之一。同时假设\(u_i\)已经为\(v_5\)的最近邻提供了最大评分(C)。在这种情况下，在部分观察到items（partially observed）的得分的上界不会被丢谟，直到我们已经发现\(v_5\)的最近邻。更进一步，我们需要确信，不存在在\(v_5\)和由该user评分过的其它items间的其它相似度，会大于已经读取的。这样做很容易验证，需要读取至多5个entries或者它需要读取超过3个entries，并执行严格的内务操作来跟踪：哪个lists已经被观察到每个item。最坏情况下，读取所有entries可能还要比Naive-1算法差。因此，我们提出一种新方法，它基于two-phase过程，并基于cost-based optimization来选择阀值(thhreshold)。

5.2 Prob值\(\theta\)的阀值选择

略

参考

d0evi1 Reading time ~1 minute

关于itemcf的topk问题，我们看下较老的一篇paper《Evaluation of Item-Based Top-N Recommendation Algorithms》中提到的：

3

在本paper中，我们研究了一种item-based topN推荐算法，它使用item-to-item相似度来计算items间的关系。在模型构建期间，对于每个item j，它具有k个计算好的最相似的items：\(\lbrace j_1,j_2,...,j_k \rbrace\)，它们对应的相似度分值为：\(\lbrace s_{j_1}, s_{j_2}, ..., s_{j_k} \rbrace\)。接着，对于已经购买了商品集合U（购物篮：basket）的每个客户，可以使用上述信息来计算top-N items进行推荐。首先，我们通过对每个item \(j \in U\)上对应的k个最相似items的联集(union)，并移除已在U中存在的items，来标识候选推荐items集合C。接着，对于每个item \(c \in C\)，我们会计算它与集合U的相似度，来作为在所有item \(j \in U\)和c之间相似度的求和，使用只有j的k个最相似items。最终，在C中的items根据各自相似度以降序排序，选择前N个items作为top-N的推荐集合。

3.1 相似度选择

  • cosine-based
  • Conditional Probality-based

3.2 相似度归一化

第3节中，给定一个items集合(basket) U，通过以下的item-based top-N推荐算法决定着要推荐的items：通过计算不在U中的每个item和U中所有items间的相似度，并选择N个最相似的items作为推荐集合。集合U和一个item \(v \notin U\)间的相似度，通过在每个item \(u \in U\)和v间添加相似度来决定（如果v不在u的k个最相似items中）

该方法的一个潜在缺点是，在每个item u和它的k个最相似items间的原始相似度（raw similarity）可能相当不同。也就是说，item的邻近点具有不同的密度。购买了那些不常购的items来说这是特别正确的，由于一个，这对于其它不常购买的items间存在一定适度的重合，可以产生相当高的相似度值。结果是，这些items在top-N items的选择时可以发挥相当强的影响力，有时会导致产生差的推荐。出于该原因，需要通过别的方法来替代3.1节描述的那些真实相似度，对于每个item u，我们首先会归一化相似度以便它们合计为1(add-up to one）。如第4节的实验所示，这通常会在top-N的推荐质量上产生明显提升。

4.实验

4.3 相似度归一化的效果

我们的第一个实验被设计成用来评估3.2节中相似度归一化的效果。图1展示了。由4种不同的item-based推荐算法的accuracy对比。其中两者使用cosine做为相似度函数，另两者使用条件概率(conditional probability)。每个算法对间的不同之处是，一个不会归一化相似度（被标记为“Cos-Sraw”和”CProb-Sraw”），另一个会进行归一化（被标记为”Cos-Snorm”和”CProb-Snorm”）。对于所有这4种算法，矩阵的行都会进行归一化，以便它们具有一致的长度，k（模型中最近邻items的数目）设置为10, “CProb-Sraw”和”CProb-Snorm”的\(\alpha\)设置为0.5.

图1: 相似度归一化在推荐质量上的效果

如图1所示，我们可以看到，使用相似度归一化的算法可以达到更高的推荐accuracies，对比起其它不使用的。实际的提升与数据库和算法有关。总之，基于条件概率的scheme相对提升要比cosine-based scheme要高。cosine-based scheme的效果提升有0%~ 6.5%，平均提升有3.1%，conditional probability-based scheme的提升会有3%-12%，平均提升7%。由于这个优点，在实验的其它地方总会使用相似度归一化。

参考

d0evi1 Reading time ~1 minute

我们先来看下慕尼黑大学的paper：《CAPTCHA Recognition with Active Deep Learning》。

2.介绍

常用的方法是，以两个相互独立的步骤来检测图片中的文本：定位在文本中的词（words）或单个字符（characters）的区域，进行分割（segmenting）并接着对它们进行识别。另外，可以使用一个字典来排除不可能的词（words）。例如，Mori and Malik提出的方法来使用一个411个词的字典来识别CAPTCHAs。等等，然而，在现代CAPTCHAs中，单个字符不能轻易地使用矩形窗口进行分割，另外字符可以相互有交叠。这些CAPTCHAs与手写文本相类似，LeCun提出使用CNN来解决手写数字识别。这些CNNs被设计成用于构建layer by layer体系来执行分类任务。在2014年，Google fellow提出使用deep CNN来结合定位（localzation)，分割（segmentation）以及多字符文本的识别。jaderberg等提出了一种在自然场景图片中的文本识别。然而，对于训练过程，它们人工模拟创建了一个非常大的文本图片的集合。相反的，我们则使用一个更小的训练集。通过探索Active Learning，我们在运行期对该神经网络进行微调（fine-tune），我们的网络接收已正确分好类但高度不确定的测试样本的前馈输入(feed）。

3.用于CAPTCHA识别的Deep CNN

图2. 用于captcha识别的卷积神经网络。该CNN由三个conv layer，三个pooling layer，两个fully-connected layer组成。最后的layer会输出所有数字的概率分布，我们可以由此计算预测数据（prediction）以及它的不确定度

我们提出了一种deep CNN来解决CAPTCHA问题。我们的方法在识别整个sequence时没有预分割（pre-segmentation）。我们使用如图2所示的网络结构。我们主要关注6数字的CAPTCHAs。每个数字（digit）在output layer中由62个神经元表示。我们定义了一个双向映射函数（bijection）：$\sigma(x) $，它将一个字符 $ x \in { ‘0’ … ‘9’ , ‘A’ … ‘Z’, ‘a’ … ‘z’ } $映射到一个整数$ l \in { 0 , … , 61 }$上。

我们分配第一个62输出神经元（output neurons）到第一个序列数字上，第二个62神经元到第二个数字上，以此类推。这样，对于一个数字 $x_i$神经元索引n被计算成 $ n=i * 62 + \theta(x_i) $，其中$ i \in {0,…,5} $是数字索引，例如，output layer具有$ 6 * 62 = 372 $个神经元。为了预测一个数字，我们考虑相应的62个神经元，并将它们归一化成总和（sum）为1. 图4展示了一个神经网络输出的示例。这里，对于首个数字的预测字符索引(predicted character index)是$c_0=52$，预测标签为$ x=\theta^{-1}(c_0)=’q’$。

图4. 对于CAPTCHA “qnnivm”的神经网络样本输出. 左图：每个数字有62个输出。黑箱展示了第一个数字的输出。右图：第一个数字的概率分布。总和归一化为1.

4.使用 Active Learning来减少所需训练数据

为了获得一个好的分类accuracy，CNNs通常需要一个非常大的训练集。然而，收集数百万的人工标注的CAPTCHAs是不可行的。因而，我们提出了使用Active Learning（见图3）。主要思想是，只有在必要时才添加新的训练数据，例如，如果样本的信息量足够用于重新训练（re-learning）。这个决定是基于预测文本的不确定性，它会使用best-versus-secnond-best的策略来计算。

图3. Active Learning流程图. 我们首先在一个小的数据集上训练。接着，分类器被应用到一些新数据上，产生一个label prediction和一个相关的不确定度。有了该不确定度，分类器可以决定是否请求一个ground truth。在我们的case中，该query的完成通过使用prediction来解决给定的CAPTCHA，以及使用正确分类的样本。接着训练数据会增加，learning会被再次执行。在我们的方法中，我们使用一个deep CNN，它可以使用新加的训练样本被更有效的重训练。

4.1 获取不确定性

如上所述，通过将相应的网络输出的求和归一化为1，我们可以估计每个数字的预测分布。这样我们可以使用”best-vs-second-best”来计算整体的不确定度$ \eta $：

\[\eta = \frac{1}{d} * \sum_{i=1}^{d} \frac{argmax{P(x_i) \ argmaxP(x_i)}}}{argmaxP(x_i)}\]

…(2)

其中，$P(x_i)$是数字$d_i$所对应的所有网络输出集。这样，我们通过对每个数字的最佳预测（best prediction）来分割第二佳预测（second-best）。

4.2 查询groud truth信息

我们的CAPTCHA识别问题是场景独特的：无需人工交互就可以执行学习。我们通过只使用这些数据样本进行重新训练（re-training）即可完成这一点：分类器已经为它们提供了一个正常label。然而，简单使用所有这些正确分类的样本进行re-training将非常低效。事实上，训练会越来越频繁，因为分类器越来越好，因而会将这些样本正确分类。为了避免这一点，我们使用不确定值来表示上述情况：在每个learning round通过预测不确定度来区分正确分类的测试样本，以及使用最不确定的样本来进行retraining。我们在试验中发现，这种方法会产生了一个更小规模的训练样本，最不确定的样本对于学习来说信息量越大。

5.实验评估

我们在自动生成CAPTCHAs上试验了我们的方法。所有实验都使用caffe框架在NVIDIA GeForce GTC 750 Ti GPU上执行。

5.1 数据集生成

由于没有人工标注好的CAPTCHA数据集，我们使用脚本来生成CAPTCHAs。在自动生成期间，我们确保它在数据集上没有重复。

我们使用Cool PHP CAPTHCA框架来生成CAPTCHAs。它们由固定长度6个歪曲文本组成，类似于reCAPTCHA。它们具有size：180 x 50. 我们修改了该框架让它生成黑白色的图片。另外，我们已经禁止了阴影（shadow）和贯穿文本的线。我们也没有使用字典词，而是使用随机字符。因此，我们已经移除了该规则：每个第二字符必须是元音字符（vowel）。我们的字体是：“AntykwaBold”。图5展示了生成的一些样本。

图5: 实验中所使用的CAPTCHAs样本

5.2 网络的设计

我们使用如图2所示的网络。

  • 卷积层(conv layers)具有的size为：48, 64和128. 它们具有一个kernel size: 5x5，padding size：2。
  • pooling layers的window size为2x2。
  • 第一个和第三个pooling layers，还有第一个conv layer的stride为2.
  • 该网络有一个size=3072的fully connected layer，还有一个二级的fully connected layer(分类器)具有output size=372.

我们也在每个卷积层和第一个fully conntected layer上添加了ReLU和dropout。每次迭代的batch size为：64.

5.3 量化评估

我们使用SGD来训练网络。然而，对比其它方法，我们以独立的方式为所有数字训练该网络。learning rate通过$ \alpha = \alpha_{0} * (1+\gamma * t)^{-\beta} $的方式变更，其中，基础的learning rate为$ \alpha_{0} = 10 ^{-2}$，$ \beta=0.75, \gamma=10^{-4}$，其中，t为当前迭代轮数。我们设置momentum $ \mu=0.9 $，正则参数$\lambda=5 * 10^{-4} $。

最昂贵的部分是获取训练样本，我们的方法的目标是，降小初始训练集所需的size。因而，我们首先使用一个非常小的初始训练集（含10000张图片）来进行 $5 * 10^4$迭代。我们只达到9.6%的accuracy（迭代越大甚至会降低accuracy）。因而，我们希望使用Active Learning。

首先，我们再次使用含10000张图片的初始训练集进行 $5 * 10^4$迭代。然后，我们分类 $5 * 10^4$ 张测试图片。接着，我们从正确分类的数据中选取新的训练样本。我们可以全取，或者基于不确定度（uncertainty）只取$5 * 10^3$个样本：即有最高的不确定度，最低的不确定度，或者随机。不确定度的计算如4.1节所述。一旦新的选中的样本被添加到训练集中，我们重新训练该网络$5 * 10^4$迭代。接着，我们遵循相同的过程。我们在总共20次Active learning rounds rounds(epoch)中应用该算法。在每次$5 * 10^3$迭代后，在一个固定的验证集上计算accuracy。我们在正确但不确定的预测上获取了最好的表现（见图6）。所有的结果是两种运行的平均。

图6: Active Deep Learning的学习曲线. 上图：训练集在每次迭代后随样选中样本的增加而增加。当使用所有正确的样本时（黑色曲线），在$ 50 \dot 10^4 $我们停止向训练集添加新的图片，因为训练集的size已经超过了 $ 3 \dot 10^6 $。 下图：只在新样本上重新训练该网络。竖直的黑线表示每轮Active Learning epoch的结束。

然而，在训练集上增加样本数需要存储。再者，增加迭代次数可以从累积的集合上受益，但它会占据更长的训练时间。对于所有这些原因，我们建议：在每次迭代进行重训练网络时，只使用选中的样本。因而，我们再次使用使用含10000张图片的初始训练集进行 $5 \dot 10^4$迭代训练。接着，对$10^5$次测试图片进行分类，使用$10^4$正确分类的图片进行替换，并再训练$2.5 \dot 10^5$。接着，我们遵循该过程，根据下面的规则来减小迭代次数：在6轮前使用$2.5 \dot 10^4$，在6-11轮使用$2 \dot 10^4$，在11-16轮使用$1.5 \dot 10^4$，在16-21轮使用$ 1 \dot 10^4$，在21-40轮使用$5 \dot 10^3$。我们再次使用正确但不确定的预测来获取最好的表现（见图6）。这是合理的，因为该网络会正确分类图片，仍对预测仍非常不确定。因而，它可以事实上学到：它对于分类确定是正确的。一旦有争议：误分类样本的学习应产生更好的结果。事实上应该如此，然而实际上并不可能。

参考

d0evi1 Reading time ~3 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）为：

\[\hat{l}(f(x_i),y_i)\]

以及最小化loss为：

\[l(f(x_i),y_i)=1-\hat{l}(f(x_i),y_i)\]

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

\[f(x)=f_{D}(x)=(f(x,D_1),...,f(x,D_{|D|})))\]

其中$ 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为：

\[\sum_{i=1}^{m}l(f_{g(x_i)}(x_i),y_i)\]

不幸的是，当训练输入分区（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$，某种划分，它使用最接近分配的分区：

\[g(x)=argmin_{i=\lbrace 1,...,P \rbrace} \| x-c_i \|\]

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

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

\[\sum_{i=1}^{m}\sum_{j=1}^{P} \hat{l}(f(x_i),y_i)\|x_i-c_j\|^{2}\]

实际上，一个基于该目标函数的层次化分区（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”空间上处理：

\[\sum_{i=1}^{m} \sum_{j=1}{P} \hat{l}(f(x_i),y_i)||Mx_i-c_j||^2\]

然而，一些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,i}= 1 + \sum_{j \neq i}\delta(f(x_t,D_j)>f(x_t,D_i))\]
  • $ R_{t,y_t} $是样本t的true label的rank分值

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

\[max_{\alpha} \sum_{t} \alpha_{y_t}(1 - max_{R_{t,i}<R_{t,y_t}} \alpha_i)\]

…(1)

服从：

\[\alpha_{i} \in {0,1}\]

…(2)

\[| \alpha | = C\]

…(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)的最优化变得很难，但我们可以将约束放松些：

\[max_{\alpha} \sum_{t} \alpha_{t_t} (1 - max_{R_{t,i} < R_{t, y_t}} \alpha_i) , 0 \leq \alpha_i \leq 1\]

…(4)

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

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

\[max_{\alpha} \sum_{t} \alpha_{y_t} (1 - \Phi( \sum_{R_{t,i} < R_{t,y_t}} \alpha_{i}))\]

…(5)

服从：

\[\alpha_i \in \lbrace 0, 1 \rbrace, |\alpha| = C\]

…(6)

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

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

\[max_{\alpha}^{} \sum_{y \in y_t} a_y (1 - max_{R_{t,i} < R_{t,y}} \alpha_i)\]

…(7)

服从：

\[\alpha_{i} \in \lbrace 0, 1 \rbrace, |\alpha|=C\]

…(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) $：

\[\Phi(r) = \frac{1}{1+e^{(k-r)}}\]

我们的目标接着变成：

\[max_{\alpha} \sum_{t} \frac{1}{|y_t|} \sum_{y \in y_t} \alpha_y(1-\Phi(\sum_{R_{t,i}<R_{t,y)}} \alpha_i))\]

…(9)

服从：

\[0 \leq \alpha_i \leq 1\]

…(10)

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

\[max_{\alpha} \sum_{t} \frac{\alpha_{y_t}}{w(R_{t,y_t})}(1 - max_{R_{t,i} < R{t,y_t}} \alpha_i)\] \[max_{\alpha} \sum_{t} \frac{1}{|y_t|} \sum_{y \in y_t} \frac{a_y}{w(R_{t,y})} (1 - \Phi( \sum_{R_{t,i} < R_{t,y}} \alpha_i))\]

这里我们作了简化：$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

d0evi1 Reading time ~1 minute

机器学习中的许多模型中，对类别型变量，常作的处理是，将它们编码成one-hot。但是对于树模型来说，将类别型变量编码成one-hot，这样作是否有意义呢？像一些机器学习工具包（比如：spark gbm实现），你可以指定为类别型变量，内部自己去做one-hot实现。而像xgboost，则将输入全认为是数值型特征去处理。

一、要不要one-hot？

这在机器学习界也有争论。理论上，树模型如果够深，也能将关键的类别型特型切出来。

关于这个，xgboost的作者tqchen在某个issues有提到过：

I do not know what you mean by vector. xgboost treat every input feature as numerical, with support for missing values and sparsity. The decision is at the user

So if you want ordered variables, you can transform the variables into numerical levels(say age). Or if you prefer treat it as categorical variable, do one hot encoding.

在另一个issues上也提到过（tqchen commented on 8 May 2015）：

One-hot encoding could be helpful when the number of categories are small( in level of 10 to 100). In such case one-hot encoding can discover interesting interactions like (gender=male) AND (job = teacher).

While ordering them makes it harder to be discovered(need two split on job). However, indeed there is not a unified way handling categorical features in trees, and usually what tree was really good at was ordered continuous features anyway..

总结起来的结论，大至两条：

  • 1.对于类别有序的类别型变量，比如age等，当成数值型变量处理可以的。对于非类别有序的类别型变量，推荐one-hot。但是one-hot会增加内存开销以及训练时间开销。
  • 2.类别型变量在范围较小时（tqchen给出的是[10,100]范围内）推荐使用

二、one-hot的一致性问题

当你进行one-hot编码时，有些机器学习工具包内置的one-hot编码工具会帮你做这些事，但是真实的情况是，我们有数据集有如下分类：训练集、测试集、预测集（真实数据）等。

这些数据集并不会统一，比如：

训练集上A特征有: a,b,c,d，测试集上A特征有:a,b,d，预测集上可能有b,c,e,f

因此，你需要做的是，将它们统一使用one-hot编码，而非分开做不同的one-hot编码.

参考