2011年10月28日,星期五

从众包数据在线多标签提取

我已经申请了 在线EM方法 之前讨论过 标称标签的低等级模型,并减少到我的 多标签模型。此时,它只是以不同的标签发射可能性转动曲柄。

不幸的是,由于多标签减少的组合性质,它在实践中可能非常慢。这是一个示例应用程序,在该应用程序中,我要求Mechanical Turkers将多个标签的短语放入诸如``Politics''和``Entertainment''之类的高级类别中。
pmineiro@ubuntu-152% for r in 4; do rm model.${r}; time ~/src/multionlineextract/src/multionlineextract --model model.${r} --data <(./multicat 10 =(sort -R octoplevel.max3.moe.in)) --n_items $(cat octoplevel.max3.moe.in | wc -l) --n_raw_labels $(./statsfrompm n_raw_labels) --max_raw_labels 3 --rank ${r} --priorz $(./statsfrompm priorz) --predict flass.${r} --eta 0.5; done
seed = 45
initial_t = 1000
eta = 0.500000 
rho = 0.500000 
n_items = 3803
n_raw_labels = 10
max_raw_labels = 3
n_labels (induced) = 176
n_workers = 65536
rank = 4
test_only = false
prediction file = flass.4
priorz = 0.049156,0.087412,0.317253,0.012600,0.135758,0.079440,0.109094,0.016949
,0.157750,0.034519
cumul     since       example   current   current   current
avg q     last        counter     label   predict   ratings
-3.515874 -3.515874         2        -1         0         4
-3.759951 -3.922669         5        -1         0         4
-3.263854 -2.767756        10        -1         0         4
-2.999247 -2.696840        19        -1         0         3
-2.531113 -2.014788        36        -1         9         4
-2.503801 -2.474213        69        -1         3         4
-2.452015 -2.396817       134        -1         3         4
-2.214508 -1.968222       263        -1         6         3
-2.030175 -1.842252       520        -1         3         4
-1.907382 -1.783031      1033        -1         1         4
-1.728004 -1.547266      2058        -1         2         4
-1.582127 -1.435591      4107        -1         2         4
-1.460967 -1.339532      8204        -1         9         4
-1.364336 -1.267581     16397        -1         5         4
-1.281301 -1.198209     32782        -1         3         4
-1.267093 -1.178344     38030        -1         3        -1
applying deferred prior 更新s ... finished
gamma:  0.0010  0.0008  0.0007  0.0006
~/src/multionlineextract/src/multionlineextract --model model.${r} --data      2
717.98s user 3.46s system 99% cpu 45:26.28 total
遗憾的是,是的,这是我笔记本电脑的一个核心需要45分钟。好消息是,在努力加快速度的同时,我提高了 顺序在线提取标称提取物 系数是4。但是推论仍然是$ O(| L | ^ 2)$,因此上面有176个有效标签的问题比二进制问题慢7700倍。更具限制性的假设,例如``所有错误的可能性均等''(在名义情况下)或``错误可能性仅取决于与真实标签的编辑距离''(在多标签情况下)会更便宜确切的推论。

多在线提取 可从 nincompoop Google代码上的存储库。

2011年10月13日,星期四

熊谈论机器学习和移民政策

灵感来自 福布斯文章 关于美国针对技术工人的移民政策改革,我决定制作此视频。请享用!

此外,如果您了解机器学习和优化,请随时与我联系以获取有关就业的信息。

机器学习劳动力市场的状况


更新:我 将此移至github 因为Xtranormal倒闭了。

p

2011年10月12日,星期三

正式的牧群心态

最近,我一直专注于生成模型来处理众包数据。这些模型从一组工作人员那里获取项目和一组相关的建议标签,并在真实标签上合成后验分布。可以将工人视为专家,并且算法提供了将专家意见综合为最终决定的过程。

在有监督的情况下,有多种方法可以实现这种综合,并提供了更好的理论保证。因此,即使生成模型可以包含已揭示的基本事实,但如果基本事实丰富,则将首选其他技术。例如,可以想象一个奇异的世界,其中一个人拥有大量标记数据,但一个人正在尝试组装一个系统,该系统将利用众包工作者将其推广到新数据。在这种情况下,众包工作者将首先检查标记的集合并提供答案,然后将使用受监督的机器学习公式从众包工作者的输出中综合决策系统。随后,将首先由众包工作者分析新颖的实例,然后根据工作者的输出自动做出最终决定。

可惜的是,众包数据通常不会揭示可笑的事实。在机器学习中,获取标记数据通常是采用众包服务的主要原因。生成模型可以在没有标记训练数据的情况下继续进行,原因是 典型的工人通常是正确的。这种假设的最终结果是,倾向于倾向于多数的工人比倾向于少数的工人更加准确,并且对后方的贡献更大。如果此基本假设不成立,则生成模型可能会做出任意错误的决定,这就是为什么在适用的情况下会首选其他技术的原因。

我所描述的是一个潜在的不正确的统计假设,由于缺乏信息而迫使系统进行统计,从而导致人们倾向于达成共识。换句话说,是成群心态的正式典范!我想知道这是否对行为金融有任何影响。毕竟,当我考虑自己的日常经历时,我当然会感到有很多意见和事实的匮乏。

2011年10月8日,星期六

从众包数据在线序标签提取

我已经应用了在线EM方法 先前讨论过 给我 序标签的生成模型。真的没有什么奇怪的,只是详细说明与 戴维德·史凯恩多发性拉希 作为标签发射可能性。如果您使用的标签具有明显的总排序量(例如, 热不热),您应该真正使用此模型而不是标称标签模型。主要优点在于,每个评估者的特征在于$ O(| L |)$参数而不是$ O(| L | ^ 2)$参数,其中$ L $是标签集。这种减少是由于假设相邻标签之间的错误(按顺序排列)比远端标签之间的错误更有可能。顺便说一下,这就是为什么订购必须突出的原因。标签集上的任意总排序将不会显示所需的错误模式。

这是数据集的示例应用程序,在该数据集中,我让Mechanical Turkers估算了Twitter个人资料所有者的年龄,并从一组固定的年龄范围中选择最佳答案。
pmineiro@ubuntu-67% ~/src/nincompoop/ordinalonlineextract/src/ordinalonlineextract --initial_t 10000 --n_worker_bits 16 --n_items 4203 --n_labels 6 --priorz 555,3846,7786,5424,1242,280 --model flass --data <(./multicat 80 =(sort -R agehit.ooe.in)) --eta 1 --rho 0.9
initial_t = 10000
eta = 1.000000
rho = 0.900000
n_items = 4203
n_labels = 6
n_workers = 65536
test_only = false
prediction file = (no output)
priorz = 0.029004,0.201002,0.406910,0.283449,0.064908,0.014633
cumul     since       example   current   current   current
avg q     last        counter     label   predict   ratings
-1.092649 -1.092649         2        -1         2         4
-1.045608 -1.017383         5        -1         2         5
-1.141637 -1.233824        10        -1         2         5
-1.230889 -1.330283        19        -1         2         5
-1.199410 -1.159306        36        -1         3         3
-1.177825 -1.155147        69        -1         2         4
-1.151384 -1.122146       134        -1         2         5
-1.153009 -1.154689       263        -1         1         5
-1.151538 -1.149990       520        -1         3         4
-1.146140 -1.140607      1033        -1         2         5
-1.124684 -1.103209      2058        -1         1         5
-1.107670 -1.090658      4107        -1         0         4
-1.080002 -1.052260      8204        -1         2         4
-1.051428 -1.022821     16397        -1         5         5
-1.023710 -0.995977     32782        -1         4         2
-0.998028 -0.972324     65551        -1         2         3
-0.976151 -0.954265    131088        -1         2         3
-0.958616 -0.941080    262161        -1         2         5
-0.953415 -0.935008    336240        -1         5        -1
applying deferred prior 更新s ... finished
kappa = 0.0423323
rho_lambda = 0.00791047
gamma = 0.4971 1.4993 2.5006 3.5035 4.5022
这比我想要的慢:上面的输出需要9分钟才能在笔记本电脑上完成。希望我会在不久的将来发现一些其他优化(更新:现在只需不到4分钟的时间; 另一个更新:现在大约需要30秒)。

该模型在标签上产生后验分布,可直接用于决策或构建成本向量以训练成本敏感的分类器。为了显示后验的非平凡性质,这是两个记录的简洁示例,两个记录的每种类型的评级具有相同的编号,但是对于该模型,模型在地面实况上选择了非常不同的后验分布。首先,输入:
KevinWihardjo|A1U4W67HW5V0FO:2 A1J8TVICSRC70W:1 A27UXXW0OEBA0:2 A2V3P1XE33NYC3:2 A1MX4AZU19PR92:1
 塔尼亚扎赫里纳|A3EO2GJAMSBATI:2 A2P0F978S0K4LF:2 AUI8BVP9IRQQJ:2 A2L54KVSIY1GOM:1 A1XXDKKNVQD4XE:1
每个配置文件都有三个图尔克语说``2''(20-24)和两个图尔克语说``1''(15-19)。现在后验分布
KevinWihardjo   -0.142590       0.000440        0.408528        0.590129        0.000903        0.000000        0.000000
taniazahrina    0.954630        0.000003        0.999001        0.000996        0.000000        0.000000        0.000000
第二列是项目难度($ \ log \ alpha $),其余列是标签上的后验分布。对于第一个轮廓,后验分布在标签1和2之间,且模式为2;而对于第二个轮廓,后验集中在标签1上。模型执行此操作的原因很多,例如,评价者说“为2 塔尼亚扎赫里纳 可能会对整个数据集的较高年龄响应产生偏见。老实说,对于这些配置文件,我不知道他们的真实年龄是多少,所以我不知道哪个后验``更好''。我确实有数据表明序号标签模型是 比奥运裁判的启发法更准确 (即放弃最高和最低分数,然后平均剩余的分数)。

顺序在线提取 可从 nincompoop Google Code中的存储库。

2011年10月3日,星期一

分层模型的稀疏在线更新

将SGD用于参数上具有先验分布的概率模型或具有规则决策边界的分类器时,有一个稀疏更新的技巧。饰演Alex Smola 已经讨论过 这已经在SVM中用于在线学习了一段时间,并且在 Vowpal Wabbit LDA实施。我将描述它,然后描述我为适应它而遇到的一些挑战 在线学习分层生成模型 用于众包数据。

故事始于训练数据集$ D $和由$ \ lambda $参数化的概率模型,其中包括似然函数$ L $和先验分布$ P $。这导致目标函数\ [
f(D; \ lambda)= \ log P(\ lambda)+ \ sum_ {d \ in D} \ log L(d | \ lambda)。
\]将前一项移到总和中会得出\ [
f(D; \ lambda)= \ sum_ {d \ in D} \ left(\ frac {1} {| D |} \ log P(\ lambda)+ \ log L(d | \ lambda)\ right),
\]看起来像是SGD优化的候选人,\ [
\ lambda(t + 1)= \ lambda(t)+ \ eta(t)\ frac {\ partial} {\ partial \ lambda} \ left(\ frac {1} {| D |} \ log P(\ lambda (t))+ \ log L(d(t)| \ lambda(t))\ right)。
\]通常情况是,仅对于$ \ lambda $的少量分量(即,似然项稀疏),特定基准面的似然项的梯度才为非零。例如,在众包生成模型中,未标记特定项目的工人不会增加可能性。不幸的是,由于先前项比较密集,因此生成的SGD更新并不稀疏。众所周知的技巧涉及在似然梯度为非零的示例之间,唯一的参数更新来自先前的梯度。用连续动力学近似逼近离散梯度动力学,\ [
\ frac {d} {dt} \ lambda_i(t)= \ frac {1} {| D |} \ eta(t)\ frac {\ partial} {\ partial \ lambda_i(t)} \ log P(\ lambda (t)),
\]从上一个更新值$ \ lambda_i(s)$进行积分时,有时会具有解析解。例如,在高斯先验和幂律衰减学习率下,\ [
\ begin {aligned}
\ log P(\ lambda(t))&=-\ frac {1} {2} \ sum_i \ left(\ lambda_i(t)-\ mu \ right)^ 2,\\
\ eta(t)&= \ eta_0(t + t_0)^ {-\ rho},\\
\ lambda_i(t)&= \ exp \ left(\ frac {\ eta_0} {| D |} \ left(\ frac {(s + t_0)^ {1-\ rho}} {1-\ rho}-\ frac {(t + t_0)^ {1-\ rho}} {1-\ rho} \ right)\ right)\ left(\ lambda_i(s)-\ mu \ right)+ \ mu。
\ end {aligned}
\] 到现在为止还挺好。不幸的是,我的生成模型是分层的,因此先前的分布本身是使用具有自己的超优先级的超参数来参数化的。目标函数变为\ [
f(D; \ lambda,\ mu)= \ log P(\ mu)+ \ log P(\ lambda | \ mu)+ \ sum_ {d \ in D} \ log L(d | \ lambda),
\],更新将变为\ [
\ begin {aligned}
\ lambda(t + 1)&= \ lambda(t)+ \ eta(t)\ frac {\ partial} {\ partial \ lambda} \ left(\ frac {1} {| D |} \ log P(\ lambda(t)| \ mu)+ \ log L(d(t)| \ lambda(t))\ right),\\
\ mu(t + 1)&= \ mu(t)+ \ eta(t)\ frac {\ partial} {\ partial \ mu} \ left(\ frac {1} {| D |} \ log P(\ mu)+ \ frac {1} {| D |} \ log P(\ lambda(t)| \ mu)\ right)。
\ end {aligned}
\]双重!第一个问题是,即使似然梯度为零,由于超优先级,所有参数都具有耦合动力学。第二个问题是超参数的梯度计算不稀疏(即参数数量是线性的)。如果我是从头开始的,我可能会说``拧紧它,超级优先级不值得'',但我试图从批处理优化中重现我的结果,其中超级优先级更易于合并并提供了一些改进(和诊断性)值)。

如何进行?还有另一个(迄今为止未知吗?)技巧将在超优先级对该模式具有解析表达式的任何时间应用。在我的情况下,先验和超验都是高斯,因此对于固定的\\ lambda $,我知道最优的\\ mu $是什么,\ [
\ begin {aligned}
\ log P(\ lambda | \ mu)&=-\ frac {1} {2} \ sum_i(\ lambda_i-\ mu)^ 2,\\
\ log P(\ mu)&=-\ frac {1} {2}(\ nu-\ mu)^ 2,\\
\ mu ^ *(\ lambda)&= \ frac {1} {| I | + 1} \ left(\ nu + \ sum_i \ lambda_i \ right),
\ end {aligned}
\]其中$ | I | $是参数数。这表明,每当$ \ lambda $发生更改时,最佳$ \ mu ^ * $都会经历相同的更改,该更改由$ \ frac {1} {| I | + 1} $。这建议以下过程:
  1. 对于当前示例中每个具有非零似然梯度贡献的$ \ lambda_i $,
    1. 像$ \ mu $是常数一样执行``纯先验''更新逼近,然后更新$ \ mu $以更改$ \ lambda_i $,\ [
      \ begin {aligned}
      \ epsilon&\ leftarrow \ exp \ left(\ frac {\ eta_0} {| D |} \ left(\ frac {(s + t_0)^ {1-\ rho}} {1-\ rho}-\ frac { (t + t_0)^ {1-\ rho}} {1-\ rho} \ right)\ right),\\
      \ Delta \ lambda_i&\ leftarrow(1-\ epsilon)(\ mu-\ lambda_i),\\
      \ lambda_i&\ leftarrow \ lambda_i + \ Delta \ lambda_i,\\
      \ mu&\ leftarrow \ mu + \ frac {1} {| I | + 1} \ Delta \ lambda_i。
      \ end {aligned}
      \] $ s $是$ \ lambda_i $的最后更新的时间戳。
  2. 使用非零梯度贡献对每个$ \ lambda_i $执行似然SGD更新,并将结果更改传播到$ \ mu $,\ [
    \ begin {aligned}
    \ Delta \ lambda_i&\ leftarrow \ eta_0(t + t_0)^ {-\ rho} \ frac {\ partial} {\ partial \ lambda_i} \ log L(d | \ lambda),\\
    \ lambda_i&\ leftarrow \ lambda_i + \ Delta \ lambda_i,\\
    \ mu&\ leftarrow \ mu + \ frac {1} {| I | + 1} \ Delta \ lambda_i。
    \ end {aligned}
    \]
现在,这有点令人不满意,因为实际上$ | I | $是一个自由参数,原因是 哈希技巧,而且通常会将其设置为比训练过程中利用的实际参数数量大得多。在限制$ | I | \ to \ infty $基本上减少到固定的先验设置,其中固定的先验均值是为$ \ mu $选择的初始值(而$ \ mu = \ nu $是初始化的正确选择,如果$ \ lambda(0 )= 0 $)。在实践中,如果$ | I | $设置得不太大,则会给出看起来合理的超优先级(否则,它们将停留在超优先级均值)。这很有用,因为在我的标称标签提取技术中,超均值混淆矩阵可以帮助识别任务问题(或数据处理中某处的错误)。