2011年9月23日,星期五

从众包数据在线提取标签

到目前为止,我一直在使用批处理EM优化我开发的用于处理众包数据的各种生成模型( 名义上的 , 序数 多标签)。尽管我很喜欢在线技术,但是在行走之前我不得不爬网,并且数据集的大小相当适中。但是,企业对Mechanical Turk的结果感到满意,并希望将其从涉及多个$ 10 ^ 4 $项目的任务扩展到涉及多个$ 10 ^ 6 $项目的任务。尽管这仍然可以存储在笔记本电脑上的内存中,但是开发该算法的在线变体似乎是一个很好的借口。

我以前的批量EM方法可以认为是最大化辅助函数\ [
F(\ alpha,\ beta,\ gamma,q)= E_ {Z \ sim q} [\ log L(D | \ alpha,\ beta,\ gamma,Z)] + \ log P(\ alpha,\ beta ,\ gamma)+ E_ {Z \ sim q} [\ log P(Z)] + H(q),
\]其中$ \ alpha $是工作人员索引的参数,$ \ beta $是项目索引的参数,$ \ gamma $是全局参数,$ q $是所有未观察到的标签的联合分布,$ Z $是所有未观察到的标签,$ D $是项目-工人标签三元组的数据集,$ \ log L(D | \ alpha,\ beta,\ gamma,Z)$是数据集的对数似然,$ P (\ alpha,\ beta,\ gamma)$是生成模型参数上的先验分布,$ P(Z)$是先验未观察到的标签分布,而$ H(q)$是未观察到的标签分布的熵。

假定未观察到的标签分布会影响项目$ q(Z)= \ prod_i q_i(Z_i)$,先前的分布$ P(Z)= \ prod_i P_i(Z_i)$也是如此。可替代地,在该约束条件下,仅找到辅助函数的最大约束。假定数据似然独立于$(\ alpha,\ beta,Z)$,导致\ [
\ begin {split}
F(\ alpha,\ beta,\ gamma,q)&= \\
&\ sum_i E_ {Z_i \ sim q_i} [\ log L(D_i | \ alpha,\ beta_i,\ gamma,Z_i)] + \ log P(\ alpha,\ beta,\ gamma)\\
&+ \ sum_i E_ {Z_i \ sim q_i} [\ log P_i(Z_i)] + \ sum_ {q_i} H(q_i),
\ end {split}
\]其中$ i $为项目建立索引,而$ D_i $是与项目$ i $相关联的数据集。进一步假设先验分布的形式为$ P(\ alpha,\ beta,\ gamma)= P(\ alpha,\ gamma)\ prod_i P(\ beta_i)$,并重新排列收益率[[
\ begin {aligned}
F(\ alpha,\ beta,\ gamma,q)&= \ sum_i F_i(\ alpha,\ beta_i,\ gamma,q_i),\\
F_i(\ alpha,\ beta_i,\ gamma,q_i)&= \\
E_ {Z_i \ sim q_i} [\ log L&(D_i | \ alpha,\ beta_i,\ gamma,Z_i)] + \ frac {1} {| I |} \ log P(\ alpha,\ gamma)+ \ log P(\ beta_i)+ E_ {Z_i \ sim q_i} [\ log P_i(Z_i)] + H(q_i),
\ end {aligned}
\]其中$ | I | $是项目总数。现在,目标函数看起来像项的总和,其中$ \ beta_i $和$ q_i $仅出现一次。这表明,如果在对应于同一项目的块中流传输数据,并且已知最佳$ \ alpha $和$ \ gamma $,则可以单独最大化$ \ beta_i $和$ q_i $并将其丢弃。当然,最优的\\ alpha $和$ \ gamma $尚不清楚,但是随着时间的推移,随着遇到更多数据,估计值会越来越好。这表明以下过程:
  1. 接收与单个项目相对应的item-worker-label三元组$ D_i $。
  2. 相对于$ \ beta_i $和$ q_i $,最大化$ F_i(\ alpha,\ beta_i,\ gamma,q_i)$。
    • 基本上,我使用固定的$ \ alpha $和$ \ gamma $对这块数据运行EM。
  3. 设置$ \ alpha \ leftarrow \ alpha + \ eta_t \ nabla _ {\ alpha} F_i \ bigr | _ {\ alpha,\ beta ^ * _ i,\ gamma,q ^ * _ i} $和$ \ gamma \ leftarrow \ gamma + \ eta_t \ nabla _ {\ gamma} F_i \ bigr | _ {\ alpha,\ beta ^ * _ i,\ gamma,q ^ * _ i} $。
    • $ \ eta_t $是随时间衰减的学习,例如$ \ eta_t = \ eta_0(\ tau_0 + t)^ {-\ rho} $。
    • $ \ eta_0 \ geq 0 $,$ \ tau_0 \ geq 0 $和$ \ rho \ geq 0 $是学习算法的调整参数。
    • 有效地,$ | I | $也是一个设置先验相对重要性的调整参数。
  4. 如果需要(例如``推理模式''),输出$ \ beta ^ * _ i $和$ q ^ * _ i $。
  5. 丢弃$ \ beta ^ * _ i $和$ q ^ * _ i $。
  6. 返回到(1)。
相对于项目数,它具有很好的可伸缩性,因为没有跨输入块维护每个项目的状态。它确实要求汇总特定项目的所有标签:但是,即使在真正的在线众包场景中,也不会出现可伸缩性问题。在实践中,项目以编程方式单独提交以进行众包分析,并且冗余评估的数量通常很少(例如5个),因此,一个缓冲众包数据直到整个项目标签可用的接收系统对空间的要求非常小。以我为例,我实际上是将此在线算法应用于以前离线收集的数据集,因此我可以轻松地将与特定项目相对应的所有标签放在一起。

关于工人数量的可伸缩性是一个潜在的问题。这是因为$ \ alpha $被保留为state,并且由worker索引(例如, 标称提取物,$ \ alpha_w $是工作人员$ w $的混淆矩阵)。为了克服这个问题,我使用 哈希技巧:我有固定数量的$ \ alpha $参数,并且我对工作人员ID进行了哈希处理以获得该工作人员的$ \ alpha $。当我遇到哈希冲突时,这意味着我将两个(或更多)工作程序视为同等工作,但这使我可以预先限制算法的空间使用量。在实践中,像这样的哈希技巧似乎总是奏效。在这种特殊的情况下,在大量工人的限制下,我将使用人口混淆矩阵对每个工人进行建模。由于样本复杂性压倒了(固定的)模型复杂性,因此这是一种降级的优雅方法。 (我实际上并不期望有大量的工作人员;众包似乎走的路是,一个人要做一些小的任务来确定高素质的工作人员,然后再执行较大的任务以限制那些工作人员)。

这是一个示例运行,涉及在一个小的测试数据集上进行40次传递。
% time ~/src/nincompoop/nominalonlineextract/src/nominalonlineextract --initial_t 10000 --n_items 9859 --n_labels 5 --priorz 1,1,1,1,1 --model flass --data <(./multicat 40 =(sort -R ethnicity4.noe.in)) --eta 1 --rho 0.5
initial_t = 10000
eta = 1.000000 
rho = 0.500000 
n_items = 9859
n_labels = 5
n_workers = 65536
symmetric = false
test_only = false
prediction file = (no output)
priorz = 0.199987,0.199987,0.199987,0.199987,0.199987
cumul     since       example   current   current   current
avg q     last        counter     label   predict   ratings
-1.183628 -1.183628         2        -1         0         5
-1.125888 -1.092893         5        -1         0         5
-1.145204 -1.162910        10        -1         0         5
-1.081261 -1.009520        19         0         0         5
-1.124367 -1.173712        36        -1         3         3
-1.083097 -1.039129        69        -1         0         4
-1.037481 -0.988452       134        -1         1         2
-0.929367 -0.820539       263        -1         1         5
-0.820125 -0.709057       520        -1         4         5
-0.738361 -0.653392      1033        -1         1         4
-0.658806 -0.579719      2058        -1         1         5
-0.610473 -0.562028      4107        -1         4         5
-0.566530 -0.522431      8204        -1         0         3
-0.522385 -0.478110     16397        -1         2         4
-0.487094 -0.451771     32782        -1         0         3
-0.460216 -0.433323     65551        -1         4         5
-0.441042 -0.421860    131088        -1         2         5
-0.427205 -0.413365    262161        -1         0         5
-0.420944 -0.408528    394360        -1         1        -1
~/src/nincompoop/nominalonlineextract/src/nominalonlineextract --initial_t     85.77s user 0.22s system 99% cpu 1:26.41 total
如果那种输出格式看起来很熟悉,那是因为我(再次)提高了vowpal wabbit的输出风格。第一列是渐进式验证的辅助函数,即在更新模型参数($ \ alpha $和$ \ gamma $)之前评估的(项的平均数)$ F_i $函数。这类似于对数可能性,如果一切正常,随着消耗更多数据,它应该会变得更大。

标称提取物,批处理EM类似物的实现(在上述数据集上)在大约90秒内收敛,因此运行时间非常困难。对于较大的数据集,无需对数据集进行太多遍,因此我希望在线版本变得越来越有优势。此外,我一直在改善 标称提取物 几个月,而我刚写 标称在线提取 因此后者可能会进一步提高速度。但是,对于适合于内存批处理EM的数据集来说,它具有竞争力。

标称在线提取 可从 nincompoop Google代码上的代码存储库。我将在短期内将其他算法的在线版本放在一起(基本方法适用于所有算法,但是每种特定的可能性都有不同的技巧)。

2011年9月6日,星期二

多标签众包数据建模:第二部分

先前 我讨论了两种分析通过众包获得的多标签分类数据集的策略。 (此处的``多标签''是指将固定集中的零个或多个标签分配给特定项目)。第一种策略是减少到一组独立的二元标记数据集(IBR),该数据集对应于观测值和地面真实情况中不存在特定标记的情况。 IBR速度很快,但是在成本敏感型多标签(CSML)分类的背景下,加权Hamming损失仅能持续减少。换句话说,由IBR产生的基本事实多标签集的分布必然是各个标签分布的产物。第二种策略是在强大的标签集上减少到多类标签数据集,我称之为 多低位提取 (这是执行任务的可执行文件的名称)。 多低位提取 对应于CSML始终如一地减少为成本敏感的多类分类(CSMC),但遭受组合爆炸的困扰。中的``低等级'' 多低位提取 是指对混淆矩阵使用低秩方法来降低样本复杂性要求(不幸的是,这不能减轻计算复杂性要求)。

我从一个相对较小的测试数据集中介绍了一个轶事,该数据表明从0/1(整个集)损失的角度来看,两种方法产生的结果相同。由于IBR比 多低位提取 对于后一种方法,这并不是一个好兆头。随后,我尝试了更大的数据集,我可以说 多低位提取 有时可以大大提高后验模式的质量。一个引人注目的示例是一项涉及在Twitter上将标签分配给面向流行文化的个人资料的任务。对于印度电影演员来说,众包工作者可靠地分配了``电影演员''标签,但通常无法为个人资料分配额外的``宝莱坞''标签。使用IBR,这些配置文件的后验模式通常为{``电影演员'')。但是用 多低位提取,如果只有一个工作人员为配置文件分配了“宝莱坞”标签,而所有工作人员均分配了“电影演员”标签,则该配置文件的后验模式为{“宝莱坞”,“电影演员”导致0/1(整个设定)的损失大大减少。尽管这可以说是设计不良的任务,但这恰恰是IBR无法捕获的标签相关性,并且可能在实践中出现。

回想起来,毫不奇怪 多低位提取 需要更大的数据集才能胜过IBR。 IBR本质上将标签的所有遗漏视为等效,但是要可靠地推断出联合标签上的更复杂的错误模式,则需要足够的数据。不幸, 多低位提取 比IBR慢得多;根据上述流行文化数据集,IBR大约需要一分钟,而 多低位提取 需要4个核心小时。注意 多低位提取 是经过合理优化的代码:用C编写,利用了 代表性体操SSE使用基于SGD的稀疏M步骤,并具有多核E步骤。不幸的是,我处于尝试加快慢速学习算法的位置,这从来都不是一件好事。

中的最新版本 nincompoop 代码存储库在速度方面有很大的改进,但仍然不是我认为的快速。但是,如果您遇到一个标签总数不多的标签问题(例如20个),并且在实际情况下可以出现的标签最大数目的合理上限(例如3个),我认为值得尝试。在入睡之前将其启动,也许您会在早晨感到惊喜。