从众包数据在线提取标签

到目前为止，我一直在使用批处理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代码上的代码存储库。我将在短期内将其他算法的在线版本放在一起（基本方法适用于所有算法，但是每种特定的可能性都有不同的技巧）。