显示带有标签的帖子 在线学习. 显示所有帖子
显示带有标签的帖子 在线学习. 显示所有帖子

2014年9月24日,星期三

子线调试

I have a post on 亚线性调试 on 微软的机器学习博客.
在线学习算法是一类机器学习(ML)技术,它们将输入作为流使用,并在它们使用输入时进行调整。它们通常用于计算方面的需求,例如速度,使用大数据集的能力以及处理非凸目标的能力。但是,它们还有另一个有用的好处,即“sub-linear debugging”.
如果您有兴趣点击 多赫蒂阈值 在机器学习中,阅读 整件事!

2013年4月30日,星期二

学习比优化容易

此博客文章的标题是一个短语,归因于 莱昂·波托(Leon Bottou) (尽管您不会从网络搜索中了解到这一点:显然,创业社区有一个 类似的格言)。这是机器学习中为数不多的深层真理之一,我认为在进入一个勇敢的新世界时要牢记这一点特别重要 数据指数压倒了计算指数。要点是,训练错误是我们真正关心的泛化错误的代名词,因此,过度花费计算精力来优化训练错误可能会适得其反。适得其反产生于(至少)两种不同的方式。首先是过多的计算工作可能会导致您使用较少的数据来补偿计算时间,而使用较少的数据意味着代理的准确性较低。第二个是不太积极的优化可以充当正则化器,当用``更好''的优化例程进行校正时,实际上会导致更严重的泛化错误。

我想到了这种现象的两个例子。一,主导地位 随机梯度下降 (SGD)。当神经网络首次出现时,SGD是唯一的优化算法,但人们很快开始尝试使用基于准牛顿的更先进技术。如今,神经网络仍然使用接近SGD的算法进行训练,可以说,我们今天看到的主要区别在于体系结构和正则化器(而体系结构是一种正则化器)。事实是,SGD是一种一般的优化算法,但它是一种很棒的学习算法。

第二个例子是 哈希技巧。对于在实际矢量表示上运行的算法(即所有算法afaik),必须将特征转换为索引,因此一种策略是构建和维护字典将特征映射到索引。对于非常高的基数特征空间,这不仅繁琐,而且可能导致无法满足的内存需求。当使用散列技巧时,将散列函数应用于特征标识以便确定特征索引。第一次遇到这种情况的每个人都认为:“那里没有碰撞吗?”。答案是:“是的,有冲突”,“在实践中似乎没有多大关系”。可以谈论它如何保留期望的点积,或者说在存在冗余的情况下统计稳定的联结特征如何提供信息,但这是真正的巧妙之处:我已经看到很多例子,其中增加了位数哈希函数会降低性能。换句话说,冲突更少,但泛化能力更差;这是因为哈希冲突为模型的复杂性提供了有用的约束, 学习比优化容易.

好吧,那又如何呢?我们所有人都应该在编码中草率行事吗? 通过把自己扔在地上而失踪飞行?不,但我认为值得保持开放的态度。特别是,要跟上现代数据的洪流,就需要开发分布式算法,而并行编程的最大低效率之一就是同步。因此,我建议对无同步学习算法保持开放的态度。

牛等等他们一直在这种思维的最前沿 霍格威尔德! 关于共享表示形式的无锁并行SGD的建议。当我第一次听说这件事时,我想:“那不可能。”但是,这就是我第一次听说该哈希技巧时所想到的。所以我还没有尝试过霍格威尔德!就个人而言,我不能保证,但是我也不愿意将其驳回。

而牛等。等建议做``脏写'', 松岛等等 提出更直观的``脏读''想法。在提出的多个想法中,有一个解析线程可以维护示例的缓冲区,而并发学习线程可以从缓冲区中训练示例,而这两者之间的同步最少。对于许多在线算法而言,解析是瓶颈,因此学习算法会在解析线程替换示例之前按预期对每个示例进行几次训练。因此,这看起来像一个迷你批处理算法,但是随着时间的推移,迷你批处理的变化缓慢,这听起来是个好主意。我在和他们玩 流支持 软件,手指交叉!

2013年3月15日,星期五

mnist演示

我已经检查了两个演示到的主要分支 威杜布 在里面 演示/ 目录,其中之一是 mnist 基于。该演示练习了由“一反所有”归约构成的神经网络归约。 mnist是规范的神经网络测试数据集,包括从灰度像素表示开始的10位多类分类问题。对于没有完全利用空间结构的方法,现有技术的测试误差约为0.8%,对于利用一切的邪恶集合体的测试误差约为0.25%。使用vee-dub时,对原始像素使用神经网络在mnist上进行训练时的测试错误率为2.2%(在我的台式机的一个核心上花费5分钟),而在mnist上进行训练时的测试错误率为1.1%。 mnist8分钟 (在我的台式机的一个核心上需要一个小时)。

上面的数字是可以的,但不会给任何顽固的神经网络爱好者留下深刻的印象。但是,vee-dub中的神经网络支持并非旨在取代传统特征工程,而是对其进行补充:这是 大声一点 风格。

令人惊讶的是,一点要素工程的效果如何。我已经注意到 n克帮助mnist 但是vee-dub中内置的n-gram支持是针对文本而设计的,因此是一维的。因此我写了一个 小程序 计算垂直,水平和对角线像素n-gram,并将其输入到vee-dub。在mnist上训练时,像素为n-gram的线性模型的测试误差为1.75%,使用3个核进行训练需要1分钟。这些核心中有2个被占用来计算像素n-gram,实际上vee-dub比2个特征提取过程要快,因此在不影响挂钟训练吞吐量的情况下,仍有空间添加一些隐藏单元。仅添加1个隐藏单元(每个班级)可将测试误差降至1.6%,而完全不影响培训时间。在mnist8m上训练像素n-gram线性模型会导致测试误差为1.25%。使用4个核心需要一个小时,其中3个专职用于计算像素n-gram。再次,vee-dub并不是瓶颈,添加5个隐藏单元(每个班级)可使测试误差降至0.9%,而不会影响训练时间。这使vee-dub受到尊重。

在mnist8m上进行培训,尽管对计算的要求更高,但总是有帮助的。 mnist8分钟是通过采用mnist训练集并将其变形的方式构造的,该方式对预测变量进行编码(将其视为利用空间结构),从而对预测变量进行编码。这是一个古老的想法,至少可以追溯到1994年,当时是Abu Mostafa的 提示学习 论文,另外表明可以从未标记的数据构建虚拟示例。虚拟示例是一种成功态度的一部分,它表示1)首先提高模型的复杂性,然后2)担心正则化。还有其他通用的方式进行正则化(例如,装袋,辍学,正确的贝叶斯推断),但虚拟示例可让您编码特定于问题的信息并利用未标记的数据,因此我认为它们很不错。

mnist8分钟数据集由Loosli,Canu和Bottou作为社区服务实现;他们的软件在运行过程中产生了不变的变形,因此虚拟示例可能仍然短暂。这可以很好地映射到vee-dub简化架构,因为可以轻松编写一个简化来从在线实际示例中动态构建临时虚拟示例的简化。

2012年11月27日,星期二

解开您的乙状结肠

我和Nikos找出了如何将神经网络实现为 威杜布 减少。基本思想是为隐藏单元创建虚假示例,以使核心计算的损失函数的梯度与反向传播相对应。结果非常类似于神经网络学习的迭代加权最小二乘法 华纳和米斯拉。一个区别是,Warner和Misra专注于特定的二阶学习方案,而我们没有指定学习算法,我们只是将vee-dub核心视为GLM求解器,并在线构建增强设计矩阵。这使我们能够利用vee-dub中的不同学习算法,即SGD变体和L-BFGS。在单盒设置中,SGD通常比L-BFGS快,尤其是在vee-dub中实现的增强中。因此,使用L-BFGS娱乐的主要原因是分布式学习。

一些注意事项:
  1. 没有多余的装饰。一个隐藏层,激活功能为tanh,唯一的配置是隐藏单元数。
  2. 具有其他减少量的组合应该可以工作,但未经广泛测试。孤立地,归约进行二进制分类和回归。
  3. 它不是一个完整的狗,但是也不能尽可能快:可以进行更多优化。但是,如果您的问题是高维且稀疏的,则vee-dub的基本基础结构(即解析,哈希等)应在假设密集特征向量的神经网络实现方面取得重大胜利。
  4. 它应该与任何可用的损失函数和所有可用的学习算法变体一起工作。
  5. 二次方和ngram起作用,并应用于输入到隐藏层。

那些乐于解决玩具问题的人会很高兴知道vee-dub现在可以用两个隐藏单元解决3-parity。
pmineiro@pmineirovb-931% ./make-parity 3
-1 |f  1:1 2:-1 3:-1
-1 |f  1:-1 2:1 3:-1
1 |f  1:1 2:1 3:-1
-1 |f  1:-1 2:-1 3:1
1 |f  1:1 2:-1 3:1
1 |f  1:-1 2:1 3:1
-1 |f  1:1 2:1 3:1
1 |f  1:-1 2:-1 3:-1
pmineiro@pmineirovb-932% ./make-parity 3 | ../vowpalwabbit/vw --nn 2 --passes 2000 -k -c --cache_file cache -f model -l 10 --invariant                          final_regressor = model
Num weight bits = 18
learning rate = 10
initial_t = 1
power_t = 0.5
decay_learning_rate = 1
randomly initializing neural network output weights 和 hidden bias
creating cache_file = cache
Warning: you tried to make two write caches.  Only the first one will be made.
Reading from
num sources = 1
average    since         example     example  current  current  current
loss       last          counter      weight    label  predict features
1.550870   1.550870            3         3.0   1.0000  -1.0000        4
1.919601   2.288332            6         6.0   1.0000   0.7762        4
2.011137   2.120980           11        11.0   1.0000  -1.0000        4
2.154878   2.298620           22        22.0   1.0000   0.3713        4
2.354256   2.553635           44        44.0  -1.0000   1.0000        4
2.286332   2.216827           87        87.0  -1.0000   1.0000        4
2.222494   2.158657          174       174.0   1.0000   0.8935        4
1.716414   1.210335          348       348.0  -1.0000  -0.9598        4
1.368982   1.021549          696       696.0   1.0000   0.9744        4
1.151838   0.934694         1392      1392.0   1.0000   1.0000        4
0.976327   0.800816         2784      2784.0   1.0000   1.0000        4
0.756642   0.536958         5568      5568.0   1.0000   1.0000        4
0.378355   0.000000        11135     11135.0  -1.0000  -1.0000        4

finished run
number of examples = 16000
weighted example sum = 1.6e+04
weighted label sum = 0
average loss = 0.2633
best constant = -6.25e-05
total feature number = 64000
pmineiro@pmineirovb-933% ./make-parity 3 | ../vowpalwabbit/vw -i model -t -p /dev/stdout --quiet
-1.000000
-1.000000
1.000000
-1.000000
1.000000
1.000000
-1.000000
1.000000
-q ff,我可以对2个隐藏单位进行4个奇偶校验。哇

更加现实,我尝试 mnist。任务是对手写数字进行多类分类,因此我将“一无所有”归约法与神经网络归约法一起使用。原始像素值是不错的功能,因为数字已尺寸标准化并居中。示例行看起来像
pmineiro@pmineirovb-658% zcat test.data.gz | head -1
 |p 202:0.328125 203:0.72265625 204:0.62109375 205:0.58984375 206:0.234375 207:0.140625 230:0.8671875 231:0.9921875 232:0.9921875 233:0.9921875 234:0.9921875 235:0.94140625 236:0.7734375 237:0.7734375 238:0.7734375 239:0.7734375 240:0.7734375 241:0.7734375 242:0.7734375 243:0.7734375 244:0.6640625 245:0.203125 258:0.26171875 259:0.4453125 260:0.28125 261:0.4453125 262:0.63671875 263:0.88671875 264:0.9921875 265:0.87890625 266:0.9921875 267:0.9921875 268:0.9921875 269:0.9765625 270:0.89453125 271:0.9921875 272:0.9921875 273:0.546875 291:0.06640625 292:0.2578125 293:0.0546875 294:0.26171875 295:0.26171875 296:0.26171875 297:0.23046875 298:0.08203125 299:0.921875 300:0.9921875 301:0.4140625 326:0.32421875 327:0.98828125 328:0.81640625 329:0.0703125 353:0.0859375 354:0.91015625 355:0.99609375 356:0.32421875 381:0.50390625 382:0.9921875 383:0.9296875 384:0.171875 408:0.23046875 409:0.97265625 410:0.9921875 411:0.2421875 436:0.51953125 437:0.9921875 438:0.73046875 439:0.01953125 463:0.03515625 464:0.80078125 465:0.96875 466:0.2265625 491:0.4921875 492:0.9921875 493:0.7109375 518:0.29296875 519:0.98046875 520:0.9375 521:0.22265625 545:0.07421875 546:0.86328125 547:0.9921875 548:0.6484375 572:0.01171875 573:0.79296875 574:0.9921875 575:0.85546875 576:0.13671875 600:0.1484375 601:0.9921875 602:0.9921875 603:0.30078125 627:0.12109375 628:0.875 629:0.9921875 630:0.44921875 631:0.00390625 655:0.51953125 656:0.9921875 657:0.9921875 658:0.203125 682:0.23828125 683:0.9453125 684:0.9921875 685:0.9921875 686:0.203125 710:0.47265625 711:0.9921875 712:0.9921875 713:0.85546875 714:0.15625 738:0.47265625 739:0.9921875 740:0.80859375 741:0.0703125
这是一些结果。 \ [
\ begin {array} {c | c | c}
\ mbox {型号}&\mbox{ Test Errors } &\mbox{ Notes } \\ \hline
\ mbox {线性}&\ mbox {848}&\\
\ mbox {Ngram}&\ mbox {436}&\ verb!--ngram 2-跳过1! \\
\ mbox {二次}&\ mbox {301}和\ verb!-q pp! \\
\ mbox {NN}&\ mbox {273}&\ verb!-nn 40!
\ end {array}
\]二次方可提供良好的结果,但训练起来却是s-l-o-w(每个示例都有>10000个功能)。 NGram增强了二次方的功能,并且相当活泼(由于编码,它们是水平n元语法;垂直n元语法也可能会有所帮助)。 40个隐藏单元神经网络的性能优于二次方,并且训练速度也更快。命令行调用如下所示:
pmineiro@pmineirovb-74% ./vw --oaa 10 -l 0.5 --loss_function logistic --passes 10 --hash all -b 22 --adaptive --invariant --random_weights 1 --random_seed 14 --nn 40 -k -c --cache_file nncache train.data.gz -f nnmodel

2012年10月21日,星期日

套袋!

我的 最近的Kaggle比赛 经验使我印象深刻,需要更快地选择模型。我最初的计划是创建一个交叉验证 威杜布 插件(减少),但是 尼科斯 说服我 套袋 具有更多的功能和更连贯的知识。基本思想是在vee-dub中复用权重向量,并同时学习一组模型,每个模型都经历输入序列的不同自举版本。结果有三点好处:
  1. 型号选择。 预算外估计 功能类似于交叉验证的估计。当多次遍历数据集时,监视袋外估计而不是渐进式验证丢失是一个更好的主意。
  2. 置信区间。当开发一个独立的决策系统时,一个点预测通常就足够了;但是,当开发要集成到更大决策系统中的子系统时,区间预测为下游使用者提供了更丰富的摘要。
  3. 更好的结果。归纳可以提高模型的通用性 偏差方差权衡。到目前为止,我还没有看到对数据集的任何实际提升,这是可以理解并可以预期的:线性模型的方差低,因此不能从套袋中受益。为了从套袋中受益,您必须做一些最终输出对训练数据差异更敏感的事情,例如神经网络,树或具有自动数据驱动特征选择的线性模型。
选择模型是我最初的动机,因此这里是利用 KDD世界杯98 数据。竞赛提供了数百个预测功能,但获胜作品仅使用了少量,表明模型选择非常重要。比赛如下:要求您决定向谁发送邀请(蜗牛)邮件;每封邮件的成本为68美分。训练集由特征($ x_i $)对($(x_i,r_i)$)和对应于先前邮件活动的响应捐赠金额(r_i $)组成。评估集仅由$ x_i $组成(除了比赛已结束,因此我们可以窥视并看到评估集的$ r_i $);提交了评估集中每个实例的估计捐赠$ \ hat r_i $,然后根据$ 1 _ {\ hat r_i进行评分>0.68}(r_i-0.68)$。换句话说,即使决定是是否邮寄某人,该决定还是通过估计的大于或小于68美分的答复发送的;否则,就无法评估估计响应的准确性,而实际获得的总利润是评分标准。

我们可以将其建模为重要性加权分类问题,根据\ [将对$ {x_i,r_i)$转换为三元组$(x_i,y_i,c_i)$。
(x_i,r_i)\ to(x_i,1_ {r_i>0.68},| r_i-0.68 |)。
\]对于评估集,我们可以解码是否直接将决定作为模型的预测类邮寄的决定。在这种情况下,常量预测变量对应于不发邮件或发邮件给所有人的策略。正如曾经拥有邮箱的任何人所能证明的那样,向所有人发送邮件比不向任何人发送邮件更有利可图,因此``向所有人发送邮件''是要克服的基本策略。 (从理论上讲:也许不应该使用机器学习的商业秘密垃圾邮件过滤器,而应该使用机器学习并公开分发 其实 想要购买伟哥并拯救其他所有人免于烦恼。)

我建立了一个幼稚的``厨房水槽''模型,方法是采用训练集中的所有功能,将日期自1900年1月起以数字形式编码为月,使用带有经验分母的样条曲线将数字编码为结点,并对所有其他变量进行分类编码。我还整理了一个模型,其中包含10个功能(通过查看获奖者的作品)(使用与厨房水槽相同的策略进行编码)。结果如下:\ [
\ begin {array} {c | c | c | c}
\ mbox {型号}&\ mbox {训练集利润}&\ mbox {培训设置的利润(实际支出)}&\ mbox {评估集利润} \\ \ hline
\ mbox {向所有人发送邮件}& \$10788.54 & \$10704 \pm \$529 & \$10560.08 \\
\ mbox {10个功能}& \$17596.35 & \$14617 \pm \$434 & \$14896.07 \\
\ mbox {厨房水槽}& \$24353.80 & \$493 \pm \$80 & \$154.92 \\
\ end {array}
\]因此,厨房水槽严重超出了训练范围,但实际购买力不足以检测到这一点。哇

不幸的是,减少装袋并不比运行多个vee-dub快。对于具有大量I / O开销的简单模型来说,它的速度更快,但是对于更复杂的模型,摊销I / O只是一个适度的好处。在内部对所有内容进行编排更为方便,减少的内容应与vee-dub的分布式学习功能结合在一起,但是在笔记本电脑领域,这并不是一个巨大的胜利。

当然,一旦有了套袋,自然的下一步就是尝试一些不稳定的学习方法。敬请关注!




2012年5月21日,星期一

教学理论?

在学习理论中,我们经常谈论一种环境,它会忽略我们的算法,或者会完全意识到我们的算法并试图使其表现不佳。如果环境完全意识到我们的算法并试图帮助它成功,那该怎么办?

这是一个具体的例子。假设您正在尝试将消息传递给接收方,并且该消息是一组有限的假设之一。通过发送一系列特征标签对$(X \ times Y)^ * $,您不得不与接收器进行通信。接收方将使用提供的数据,通过假设集上的ERM对消息进行解码。它需要多少个示例,您应该如何选择它们?如果这听起来很老套,则认为进化是通过重用来实现的,因此,如果由于其他选择压力而从经验中学习的能力,可以选择将其用于服务交流 认知语言学.

直观地讲,即使从经验中学到了要传达的假设,但重新传输用于学习假设的确切数据也不是一个好策略。实际上,最好的策略似乎是根本不使用真实数据。通过构建一组人工的训练示例,可以引入有利的结构,例如,可以实现该问题。 (有趣的是:我曾经教授一位教授,他坦言他有时会向本科生开设入门课程,以使他们``更接近真相'';这个想法是,如果他们上了高年级班,他会有能力加深他们的理解,如果不是这样,他们实际上比学习简化的失真更好。

学习理论中的某些概念在此设置中是落后的。例如, 小石城的维度 表示当对抗性地选择示例时,在可实现的顺序预测方案中发生的最大错误数(和 概括到不可知论的情况)。我们可以在这里帮助选择示例(adversarial的反义词是什么?),但实际上 错误,因此许多假设是不正确的,可以迅速消除。不幸的是,我们可能会遇到这样一种情况,即希望传达的假设在任何一点上最多与另一个假设不符。小石城认为这一条件是有利的,因为一个错误会消除除一个假设之外的所有假设,否则就不会造成伤害。但是在我们的情况下,这是最坏的情况,因为这很难通过示例来分离目标假设。换句话说,我们可以有帮助地选择数据,但是如果对抗性地选择假设集,这可能仍然非常困难。

对于发送者而言,发明一个最佳的虚拟数据序列可能在计算上过于困难。在这种情况下,主动学习算法可能会提供良好的启发式解决方案。在此,标签复杂度对应于用于学习假设的原始数据序列与用于传输假设的简化数据序列之间的数据压缩。

有各种各样的变化的沃土,例如,通信信道嘈杂,接收器确实估计了ERM,或者根据通信假设和接收假设之间的损失差异而不是假设的0-1损失对通信进行评分。

2012年5月16日,星期三

主动最小极大值预报

这是我的延续 以前的帖子 我注意到Minimax Forecaster从积极学习的角度着迷。幸运的是,我注意到Abernethy等人的一篇论文。等叫 通过极大极小对偶性的最佳后悔随机视图。本文作者利用杠杆作用以一般方式解开在线凸优化 冯·诺依曼的极小极大定理。通过这样做,他们得出了在线游戏对对手的价值的一般公式。前一篇文章的直觉是,观察和不观察特定结果之间的游戏价值差异将是在对抗环境中做出主动学习决策的关键,因此该公式非常有趣。

Abernethy等。等首先从比上一篇文章更通用的设置入手,但是我将把它们的约定适应于上一篇文章中存在差异的地方。有一个带有$ T $回合的游戏。有一组$ \ mathcal {F} $专家。在每个回合中,每个专家$ f $产生一个预测$ f_t $,玩家产生一个预测$ p_t $,对手同时产生一个结果$ y_t $,并且玩家遭受瞬时损失$ l(p_t,y_t)$。专家是静态的(他们的预测不依赖于先前观察到的结果),因此基本上每个专家都是一个序列$ f_ {1:T} $。玩家想要生成一系列预测$ p_ {1:T} $,以最大程度地减少最坏的后悔\ [
\ sup_ {y_ {1:T} \ in \ mathcal {Y} ^ T} L(p_ {1:T},y_ {1:T})-\ inf_ {f \ in \ mathcal {F}} L( f_ {1:T},y_ {1:T}),
\]其中$ L(p_ {1:T},y_ {1:T})= \ sum_s l(p_s,y_s)$是总损失。 (为简化表示法,除非括号中明确限制,否则极值和极小值将捕获整个表达式的其余部分。)上一篇文章的Minimax Forecaster是该问题特定情况的明确解决方案,而Abernethy等人。等通常关注表征此类游戏。他们考虑最佳玩法下游戏对对手的价值,\ [
\ begin {aligned}
R ^ *(\ mathcal {F})&= \ inf_ {p_1 \ in \ mathcal {P}} \ sup_ {y_1 \ in \ mathcal {Y}} \ ldots \ inf_ {p_T \ in \ mathcal {P}} \ sup_ {y_T \ in \ mathcal {Y}} \ sum_ {t = 1} ^ T l(p_t,y_t)-\ inf_ {f \ in \ mathcal {F}} \ sum_ {t = 1} ^ T l (f_t,y_t)。
\ end {aligned}
\]令人惊奇的结果是,这与\ [
\ begin {aligned}
R ^ *(\ mathcal {F})&= \ sup_ {Y \ in \ mathbb {P}(\ mathcal {Y} ^ T)} \ mathbb {E} _ {y_ {1:T} \ sim Y} \ left [\ sum_ {t = 1} ^ T \ inf_ {p_t \ in \ mathcal {P}} \ biggl(\ mathbb {E} _ {\ tilde y_t} \ left [l(p_t,\ tilde y_t)| y_ {1:t-1} \ right] \ biggr)-\ inf_ {f \ in \ mathcal {F}} \ sum_ {t = 1} ^ T l(f_t,y_t)\ right],
\ end {aligned}
\],其中最高值超过结果序列$ \ mathbb {P}(\ mathcal {Y} ^ T)$的分布。换句话说,这看起来像是在遗忘(非平稳)环境下玩的游戏,但是却在最恶劣的环境下玩。这是一个不错的结果,并导致随后的工作 在IID和对抗设置之间进行插补 通过限制序列分布上的最高点。

现在通过积极学习,我们选择不观察某些结果(由变量$ z_s \ in \ {0,1 \} $表示),从而使对手更加强大。我可以将游戏价值的上限设为\ [
\ begin {aligned}
R ^ *(\ mathcal {F} | z_ {1:T})&\ leq \ sup_ {Y \ in \ mathbb {P}(\ mathcal {Y} ^ T)} \ mathbb {E} _ {y_ { 1:T} \ sim Y} \ left [\ sum_ {t = 1} ^ T \ inf_ {p_t \ in \ mathcal {P}} \ biggl(\ mathbb {E} _ {\ tilde y_t} \ left [l (p_t,\ tilde y_t)| \ Omega_ {t-1} \ right] \ biggr)-\ inf_ {f \ in \ mathcal {F}} \ sum_ {t = 1} ^ T l(f_t,y_t)\对],
\ end {aligned}
\]其中$ \ Omega_t = \ {y_s | s \ leq t,z_s = 1 \} $表示观察到的结果。这是直观上令人愉悦的,因为内部条件期望值表示玩家的知识。要导出上限,请按照本文附录A中的过程进行操作,只要从\ [
\ inf_ {p_1 \ in \ mathcal {P}} \ sup_ {y_1 \ in \ mathcal {Y}} \ cdots \ inf_ {p_s \ in \ mathcal {P}} \ sup_ {y_s \ in \ mathcal {Y}} \ cdots \ inf_ {p_T \ in \ mathcal {P}} \ sup_ {y_T \ in \ mathcal {Y}} \ sum_ {t = 1} ^ T l(p_t,y_t)-\ inf_ {f \ in \ mathcal {F}} \ sum_ {t = 1} ^ T l(f_t,y_t),
\] 至 \[
\ inf_ {p_1 \ in \ mathcal {P}} \ sup_ {y_1 \ in \ mathcal {Y}} \ cdots \ inf_ {p_s \ in \ mathcal {P}} \ cdots \ inf_ {p_T \ in \ mathcal {P }} \ sup_ {y_T \ in \ mathcal {Y}} \ sup_ {y_s \ in \ mathcal {Y}} \ sum_ {t = 1} ^ T l(p_t,y_t)-\ inf_ {f \ in \ mathcal {F}} \ sum_ {t = 1} ^ T l(f_t,y_t),
\],即让对手将未观察到的值的选择推迟到游戏结束。这只是一个上限,因为实际上对手必须在$ s $轮中选择$ s $的结果,所以我可能对对手过于慷慨。

极小极大预报

如果我们在与边界相关联的广泛形式游戏中设计Minimax Forecaster,则会得到优化边界的算法。考虑这样一种情况,其中观察到除了舍入$ s $之外的所有结果。重复原始minimax预报器论文中的向后归纳步骤,得到表达式\ [
\ begin {aligned}
p_t ^ *&= \frac{1}{2} \biggl( 1 - R^* (\mathcal{F}, y_{1:t-1}0 | z_s = 0) + R^* (\mathcal{F}, y_{1:t-1}1 | z_s = 0) \biggr). & (t > s)
\ end {aligned}
\]和\ [
\ begin {aligned}
&R ^ *(\ mathcal {F},y_ {1:t} | z_s = 0)\\
&= \frac{T - t}{2} + \mathbb{E}_{\sigma_{t+1:T}}\left[ \sup_{y_s \in \mathcal{Y}} |p_s - y_s| - \inf_{f \in \mathcal{F}} L (f_{1:T}, y_{1:t} \sigma_{t+1:T}) \right] & (t > s) \\
&= R ^ *(\ mathcal {F},y_ {1:t})\\
&\ quad + \ mathbb {E} _ {\ sigma_ {t + 1:T}} \ left [\ left | p_s-\ frac {1} {2} \ left(1 + \ inf_ {f \ in \ mathcal {F}} \ left(L(f_ {1:T},y_ {1:s-1} 0 \ sigma_ {s + 1:T})\ right)-\ inf_ {f \ in \ mathcal {F}} \ left(L(f_ {1:T},y_ {1:s-1} 1 \ sigma_ {s + 1:T})\ right)\ right)\ right | \对]。
\ end {aligned}
\]因此,玩过$ p_s $且未观察到结果$ s $的剩余游戏价值等于完全观测到的剩余游戏价值加上与所有Rademacher分布播出的平均预期平均损失有关的罚款。这意味着$ p_s $的最佳选择是中位数\ [
\ begin {aligned}
p_s ^ *&= \ mathop {\ operatorname {median}} \ left(\ frac {1} {2} \ left(1 + \ inf_ {f \ in \ mathcal {F}} \ left(L(f_ {1 :T},y_ {1:s-1} 0 \ sigma_ {s + 1:T})\ right)-\ inf_ {f \ in \ mathcal {F}} \ left(L(f(f_ {1:T} ,y_ {1:s-1} 1 \ sigma_ {s + 1:T})\ right)\ right)\ right)。
\ end {aligned}
\]在$ s $和$ T $之间没有额外的下注游戏的情况下,分布中只有一个点,因此中位数是该点,因此最佳下注游戏$ p_s ^ * $与在充分观察的情况下。在$ s $和$ T $之间还有一轮下注的情况下,分布中有两个点,因此均值是中位数,并且最佳下注$ p_s ^ * $与上一遍相同。完全观察到的游戏(与以前的博客文章一致)。在$ s $和$ T $之间有多于一轮的比赛时,平均值不一定是中位数(即,不必将预期的绝对损失最小化),因此最佳比赛$ p_s ^ * $是不同的。也许这就是为什么Mathematica在我尝试解决更长版本的未观察到的游戏时``扑出''的原因。

一旦我们``跳过''了未观察到的点并确定了$ p_s ^ * $,我们就可以继续向后归纳;但我认为有趣的一点是惩罚术语,它表示在给定所有先前和之后的回合的情况下,在$ s $处观察结果的价值,\ [
\ mathbb {E} _ {\ sigma_ {t + 1:T}} \ left [\ left | p_s-\ frac {1} {2} \ left(1 + \ inf_ {f \ in \ mathcal {F}} \ left(L(f_ {1:T},y_ {1:s-1} 0 \ sigma_ {s + 1:T})\ right)-\ inf_ {f \ in \ mathcal {F}} \ left(L(f_ {1:T},y_ {1:s-1} 1 \ sigma_ {s + 1:T})\ right)\ right)\ right | \对]。
\]这个惩罚条款对于决定是否在$ s $轮查询结果非常重要。最好将其推广到未观察到某些先前结果的情况,以及涉及可能未观察到的未来结果的情况。当然,计划后者可能会成倍地困难。

为了使之可行,如果可以廉价且准确地估计出中位数和预期的绝对损失,例如使用随机播放,那将是很好的。同样也许决定是否要查询结果要在游戏价值界限上进行,例如,假设将观察所有后续观察,而不是考虑观察结果的未来决定。此外,该技术从根本上仍是可转导的,因为需要知道对规划范围$ f_ {1:T} $的专家预测。然而,即使有所有这些警告,例如在推荐系统中也可能有一个有趣的应用。



































2012年5月6日,星期日

Minimax预报器和超导主动学习

我一直在NIPS 2011论文清单上走下坡路,发现这份不错的论文 通过随机舍入进行有效的在线学习 由Cesa-Bianchi和Shamir撰写。本文是关于改进和扩展Minimax Forecaster的,在 预测,学习和游戏。 (我拥有一份副本,但我承认没有到那本书中走得太远。)Minimax Forecaster使用不同于在线学习的策略来进行在线学习。 镜面下降 实际上,这是我(以及其他所有人?)每天使用的内容。这种不同的设置提供了思考对抗性主动学习的机会。

这是基本设置。有一个带有$ T $回合的游戏。有一组$ \ mathcal {F} $专家。在每个回合中,每个专家$ f $产生一个预测$ f_t $,玩家产生一个预测$ p_t $,对手同时产生一个结果$ y_t $,并且玩家遭受瞬时损失$ l(p_t,y_t)$。专家是静态的(他们的预测不依赖于先前观察到的结果),因此基本上每个专家都是一个序列$ f_ {1:T} $。玩家想要生成一系列预测$ p_ {1:T} $,以最大程度地减少最坏的后悔\ [
\ sup_ {y_ {1:T} \ in \ mathcal {Y} ^ T} \ biggl(L(p_ {1:T},y_ {1:T})-\ inf_ {f \ in \ mathcal {F} } L(f_ {1:T},y_ {1:T})\ biggr),
\]其中$ L(p_ {1:T},y_ {1:T})= \ sum_s l(p_s,y_s)$是总损失。当观察值为二进制$ \ mathcal {Y} = \ {0,1 \} $时,$ | p_t-y_t | $的瞬时损失对应于玩家随机决策时的预期0-1损失。令人惊讶的是,这种情况为最佳预测\ [
\ begin {aligned}
p ^ * _ t&= \ frac {1} {2} \ biggl(1 + R ^ *(\ mathcal {F},y_ {1:t-1} 1)-R ^ *(\ mathcal {F}, y_ {1:t-1} 0)\ biggr)\\
&= \ frac {1} {2} \ biggl(1 + \ mathbb {E} _ {\ sigma_ {t + 1:T}} \ left [\ inf_ {f \ in \ mathcal {F}} L(f_ {1:T},y_ {1:t-1} 0 \ sigma_ {t + 1:T})-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:T},y_ {1 :t-1} 1 \ sigma_ {t + 1:T})\ right] \ biggr),
\ end {aligned}
\],其中时间序列级联用词法表示,$ \ sigma_t $是$ \ mathrm {Bournelli}(1/2)$ Rademacher平均值,和$ R ^ *(\ mathcal {F},y_ {1:t})$是经过几轮游戏后的剩余游戏价值,\ [
\ begin {aligned}
R ^ *(\ mathcal {F},y_ {1:t})&= \ frac {1} {2} \ biggl(1 + R ^ *(\ mathcal {F},y_ {1:t-1} 0)+ R ^ *(\ mathcal {F},y_ {1:t-1} 1)\ biggr)\\
&= \ frac {T-t} {2}-\ mathbb {E} _ {\ sigma_ {t + 1:T}} \ left [\ inf_ {f \ in \ mathcal {F}} L(f_ {1 :T},y_ {1:t} \ sigma_ {t + 1:T})\ right]。
\ end {aligned}
\]本质上,这里发生的事情是,玩家可以通过玩一个常数加上与玩每个选项相关的剩余游戏值之间的差,使对手在每一轮中都不会玩该选项。这将导致剩余游戏价值为常数加上在玩完每个选项后继续的平均值。递归解开游戏价值会导致Rademacher风格平均值。本文的一个观察结果是,可以通过采样来获得这种期望值,以实现高概率的后悔界限,也就是随机播放。

实际上,即使要进行随机播放,您也需要了解各种专家的$ f_ {1:T} $。将其映射到上下文预测设置时,这对应于提前知道特征序列(但不知道标签)。因此,这本质上是一种转导技术。一些推荐问题自然是转导性的,因此本文讨论了在协作过滤中的应用。

主动学习?

原则上可以修改设置以考虑主动学习。每个回合中,除了产生预测外,玩家还必须做出决定$ z_t \ in \ {0,1 \} $是否遵守$ y_t $。如果$ z_t = 0 $,则玩家无法在后续预测中使用$ y_t $的值。由于玩家观察$ y_t $总是更好,因此必须要付出一定的代价,因此每次观察都要考虑恒定的惩罚$ \ alpha $。玩家想要生成一系列预测$ p_ {1:T} $并查询$ z_ {1:T} $,这可以使\ mathcal {Y中的最坏情况后悔\ [\ sup_ {y_ {1:T} \ } ^ T} \ biggl(\ sum_s \ alpha z_s + L(p_ {1:T},y_ {1:T})-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:T} ,y_ {1:T})\ biggr)。
\]到目前为止,简明的通用闭式表达式使我难以理解,但是有一个平凡的案例可以得出很好的答案:两回合博弈。

观察最终结果$ y_T $从来没有任何意义,因此$ z_T = 0 $。然后,在两轮游戏中,问题是是否观察$ y_1 $。如果未观察到$ y_1 $(即$ z_1 = 0 $),则玩家必须在没有中间反馈的情况下弹道计划两个预测。
\ begin {aligned}
(p_1 ^ *,p_2 ^ *)&= \ mathop {\ operatorname {arg \,inf}} \ limits_ {p_ {1:2} \ in \ mathcal {P} ^ 2} \ sup_ {y_ {1:2 } \ in \ mathcal {Y} ^ 2} \ left(| p_1-y_1 | + | p_2-y_2 |-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},y_ {1 :2})\ right)。
\ end {aligned}
\]可以用Mathematica解决:这是咒语。
Minimize[{ z, 
           p1 + p2 - inf00 <= z, 
           p1 + (1 - p2) - inf01 <= z, 
           (1 - p1) + p2 - inf10 <= z, 
           (1 - p1) + (1 - p2) - inf11 <= z }, 
           { p1, p2, z }] // Simplify
这有解决方案\ [
\ begin {aligned}
p_1 ^ *&= \ frac {1} {2} \ left(1 + \ frac {1} {2} \ sum_ {y_2 = 0} ^ 1 \ left(\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},0y_2)-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},1y_2)\ right)\ right)&(z_1 = 0),\\
p_2 ^ *&= \ frac {1} {2} \ left(1 + \ frac {1} {2} \ sum_ {y_1 = 0} ^ 1 \ left(\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},y_10)-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},y_11)\ right)\ right)&(z_1 = 0),
\ end {aligned}
\]具有游戏价值\ [
\ begin {aligned}
&R(\ mathcal {F},\ emptyset | z_1 = 0)\\
&= 1-\ frac {1} {2} \ min \ left \ {\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},00)+ \ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},11),\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},01)+ \ inf_ {f \ in \ mathcal {F }} L(f_ {1:2},10)\ right \}。 \\
\ end {aligned}
\]现在将其与$ z_1 = 1 $的情况进行比较,这与完全观察到的Minimax Forecaster相同。 \ [
\ begin {aligned}
p_1 ^ *&= \ frac {1} {2} \ left(1 + \ frac {1} {2} \ sum_ {y_2 = 0} ^ 1 \ left(\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},0y_2)-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},1y_2)\ right)\ right)&(z_1 = 1),\\
p_2 ^ *&= \ frac {1} {2} \ left(1 + \ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},y_10)-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},y_11)\ right)&(z_1 = 1)。
\ end {aligned}
\]无论$ z_1 = 0 $还是$ z_1 = 1 $,第一轮预测$ p_1 ^ * $都是相同的,但是第二轮预测$ p_2 ^ * $是不同的。如果$ z_1 = 0 $,则通过对可能的历史记录取平均值来计算$ p_2 ^ * $;而如果$ z_1 = 1 $,则$ p_2 ^ * $是使用实际观察到的历史进行计算的。 (此外:也许恒定时间的Radacher平均数将成为量子计算的杀手级应用。)

为了决定是否观察$ y_1 $,我们需要知道这样做有多好,即游戏价值的差异。当$ z_1 = 1 $时,这与完全观察到的Minimax Forecaster相同,\ [
\ begin {aligned}
&R(\ mathcal {F},\ emptyset | z_1 = 1)\\
&= 1-\ frac {1} {4} \ left(\ inf_ {f \ in \ mathcal {F}} L(f_ {1:T},00)+ \ inf_ {f \ in \ mathcal {F} } L(f_ {1:T},01)+ \ inf_ {f \ in \ mathcal {F}} L(f_ {1:T},10)+ \ inf_ {f \ in \ mathcal {F}} L (f_ {1:T},11)\ right),
\ end {aligned}
\]因此游戏价值的差异为\ [
\ begin {aligned}
&R ^ *(\ mathcal {F},\ emptyset | z_t = 0)-R ^ *(\ mathcal {F},\ emptyset | z_t = 1)\\
&= \ frac {1} {4} \ left | \ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},00)-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},01)-\ left (\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},10)-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},11)\ right )\ right |。 \\
\ end {aligned}
\]看起来像是将来差异的差异。如果游戏价值差超过$ \ alpha $,那么我们应该确定$ z_1 = 1 $,否则。因此,例如,如果每个专家都在第一轮中预测相同的值,则未来差异之差将为零,我们不应观察到$ y_1 $。这听起来确实像是主动学习。

那么一般情况下的$ T $圆形解决方案应该是什么样的呢?凭直觉,人们希望,如果过去做得好的所有专家都在当前实例上预测同一件事,那么观察该实例的$ y_t $的价值将下降。这大致就是不可知主动学习在IID设置中所做的事情。在这里,未来也很重要,但是类似地,如果所有在最后阶段进行角逐的专家都同意一个值,那么观察$ y_t $的价值就应该更少。当我们接近规划阶段的末期时,这主要是由过去的出色表现所驱动。

2012年4月15日,星期日

互动式PAC

最近,我受到启发,总结了以下方面的应用进展 PAC风格 交互式设置的算法设计,最后得到了这个小表格。
P很好地 A近似地 C直立的
被动批量学习 wrt绘制数据集 IID浓度
被动在线学习 wrt绘制数据集 (``在线到批量''转换)
积极的在线学习 wrt绘制数据集和标签检查决定的顺序 ting(风俗?)
情境强盗 wrt绘制数据集和选择的操作顺序 ting(弗里德曼风格)
两件事跳了出来。首先是多功能性 ting 驯服交互式学习。这种推理方式还能走多远?毫无把握地预言是愚蠢的,但是感觉仍然有一定的发展空间。最终,当然存在随机设置的限制:并非所有环境都被很好地近似为遗忘的。所以最终我们都会进行博弈论,除非 像这样 杀死了所有人在此之前,我担心尝试解决强化学习中的学分分配问题时实际上难以克服的样本复杂性问题。人们已经可以看到这种情况的提示,例如,对于不可知论的随机上下文强盗来说,最坏情况的瞬时遗憾表明数据需求与可能采取的行动数量呈线性比例关系。另一方面,数据量的扩展速度甚至比计算速度还要快。如果相对增长无限期地持续下去,那么计算复杂性将胜过样本复杂性,这是一个算法设计问题。

第二是在线学习的基本性质。在1990年代,如果您(像我一样!)将在线学习视为实现细节,那是一种宽恕,这是一种优化策略,特别适合于机器学习中出现的目标函数类型(我完全没有意识到) 预测单个序列)。借助事后观察的优势,很明显,在线学习更适合考虑随着时间的流逝如何向算法显示信息(或由其收集信息),而被动批处理学习更像是具有特定实现可能性的特殊情况。

2011年12月13日,星期二

可视化人群

大约一年前,我读了Welinder等人的论文。等标题 人群的多维智慧。 那时,我刚刚开始大量利用众包来进行机器学习任务,而论文的跳跃开始了我对众包数据集的想法。因此,我很高兴地宣布,我已向 弹奏钢琴 受本文启发。

我说``灵感来自''是因为模型要简单得多。特别是因为在我的数据集中通常每个项目的评分很少(例如3),所以我继承了简单项目模型的传统(即,单个标量难度参数$ \ beta $)。因此,我嵌入了隐藏的标签,而不是嵌入项目。每个工人都被建模为一个概率分类器,该分类器由与隐藏标签原型的距离\ [
p(l_ {ij} = r | \ alpha,\ beta,\ tau,z)\ propto \ exp(-\ beta_j \ lVert \ tau_ {z_j} + \ alpha_ {z_jr}-\ tau_r-\ alpha_ {ir} \ rVert ^ 2)。
\]这里$ l_ {ij} $是工作人员$ i $在项目$ j $上报告的标签,$ \ alpha_ {ir} $是工作人员$ i $的$ d $维偏差矢量,标签为$ r $ ,$ \ beta_j $是项目$ j $的难度参数,$ \ tau_r $是标签$ r $的$ d $维原型向量,$ z_j $是项目$ j $的真实隐藏标签,而$ d $是嵌入的维数。尽管需要随机初始化$ \ tau $才能打破对称性,但是此参数化操作可确保$ \ alpha_ {ir} = 0 $是合理的起始条件。 $ \ alpha $是$ L ^ 2 $正则化的(高斯先验),而$ \ tau $不是正则化的(无信息先验)。关于不变性的注释:通过将$ \ tau $转换并旋转到规范位置来消除$ d $对称性($ \ tau_0 $约束在原点,$ \ tau_1 $约束在由第一个单位向量等)。

尽管我的动机是可视化(对应于$ d = 2 $或$ d = 3 $),但还有其他两种可能的用法。 $ d = 1 $类似于非单调 顺序约束 并且可能适合某些问题。较大的$ d $可能有用,因为每个工人的参数从$ O(| L | ^ 2)$减少到$ O(d | L |)$,这可能与 减少处理的多标签问题.

推理与以前一样(我对分类器使用了多项逻辑回归),但工人模型当然发生了变化。实际上,该工人模型的速度比多项式工人模型的速度慢大约3倍,但是由于该工人模型导致每个工人参数的减少,因此公平的比较可能与低秩逼近比较,后者也较慢。这是完成我的规范演示任务的软件,可从其个人资料预测Twitter用户的种族。
strategy = 名义上的embed
initial_t = 10000
eta = 1.0
rho = 0.9
n_items = 16547
n_labels = 9
n_worker_bits = 16
n_feature_bits = 18
n_dims = 2
seed = 45
test_only = false
prediction file = (no output)
data file = (stdin)
cumul    since    cumul    since      example current current current  current
avg q    last     avg ce   last       counter   label predict ratings features
-1.64616 -1.64616 -1.90946 -1.90946         2      -1       2       4       30
-1.60512 -1.56865 -1.93926 -1.95912         5      -1       2       3       32
-1.38015 -1.15517 -2.13355 -2.32784        10      -1       1       4       28
-1.11627 -0.82685 -2.08542 -2.03194        19      -1       2       3       21
-0.89318 -0.63424 -1.89668 -1.68574        36      -1       1       3       35
-0.90385 -0.91498 -1.62015 -1.31849        69      -1       8       4       27
-0.99486 -1.0903  -1.5287  -1.43162       134      -1       1       4       54
-0.93116 -0.86077 -1.42049 -1.30809       263      -1       1       4       45
-0.90436 -0.87592 -1.47783 -1.5365        520      -1       1       3       13
-0.92706 -0.95001 -1.42042 -1.36223      1033      -1       2       1       11
-0.96477 -1.00259 -1.33948 -1.25791      2058      -1       8       3       21
-0.95079 -0.93672 -1.2513  -1.16272      4107      -1       1       3       44
-0.91765 -0.88423 -1.13014 -1.0087       8204      -1       0       3       26
-0.90145 -0.88529 -0.98977 -0.84921     16397      -1       8       3       23
-0.86520 -0.82882 -0.80860 -0.62731     32782      -1       8       3       20
-0.83186 -0.79852 -0.63999 -0.47132     65551      -1       1       3       56
-0.79732 -0.76279 -0.50123 -0.36243    131088      -1       2       3       35
-0.77279 -0.74826 -0.40255 -0.30386    262161      -1       8       3       41
-0.75345 -0.73413 -0.33804 -0.27352    524306      -1       2       3       43
-0.74128 -0.72911 -0.29748 -0.25692   1048595      -1       1       4       45
-0.73829 -0.72691 -0.28774 -0.25064   1323760      -1       1       3       27
applying deferred prior 更新s ... finished

tau:
     \  latent dimension
      |   0       1   
label |
    0 | 0.0000  0.0000
    1 | 2.6737  0.0000
    2 | 3.5386  -1.3961
    3 | 1.3373  -1.2188
    4 | -1.5965 -1.4927
    5 | 0.0136  -2.9098
    6 | -2.4236 1.4345
    7 | -0.0450 2.2672
    8 | 2.1513  -1.5638
  447.48s user 1.28s system 97% cpu 7:38.84 total
上面的过程会为每个项目的隐藏标签生成估计值(后验分布),以及将尝试推广到新实例的分类器和尝试推广到新工人的工人模型。此外,还有一些可视化的东西:
  1. 隐藏的标签原型向量$ \ tau_r $。靠得更近意味着两个标签更容易混淆。
  2. 每个工人的噪声矢量$ \ alpha_ {ir} $。这些调整每位用户的隐藏标签原型,导致偏差和准确性上的差异。
  3. 通过在标签上的后分布,通过形成隐藏的标签原型向量的凸组合,可以将这些项放置到潜在空间中。
这是主要标签落入二维嵌入的方式。标签的文本以该标签的$ \ tau $的值为中心(对于新工人,$ \ alpha_ {ir} = 0 $,因此$ \ tau $定义默认的混淆矩阵)。典型的$ \ beta $是1,因此在此图上的距离3表示混淆的可能性非常低。 (单击图像放大)。


结果取决于随机种子。最受欢迎的标签(亚洲,西班牙,黑色,白色和N / A)保持相对位置,但不太受欢迎的标签会四处走动。这是上面针对不同随机种子的图:请注意,x轴缩小了,但这对于后续图更方便。 (单击图像放大)。


在其余的情节中,我会坚持使用这种随机种子。现在,我将在绘图上为每个工人的原型矢量($ \ tau_z + \ alpha_ {iz} $)放置一个点。 (单击图像放大)。


点的图案提供了有关整个工人群体中错误图案分布的一些直觉。例如,西班牙裔标签周围的点具有比水平扩展更多的水平扩展。这表明在区分白人和西班牙裔与区分黑人和西班牙裔之间存在更多差异。白人和西班牙裔之间的区别更多是文化而非种族。 美国人口普查局将白人列为种族,但将“西班牙裔或拉丁裔”列为种族;因此,从某种意义上说,这是糟糕的实验设计,但是由于广告商非常关注这种区别,因此我必须使其发挥作用。

最后,这是一些根据个人资料的隐藏标签上的后验分布嵌入到潜在空间中的个人资料照片。单击下面的图像以获取矢量版本,您可以放大并查看详细信息。


在某些情况下,鉴于其嵌入位置,这些照片似乎没有任何意义。其中一些是因为工人是嘈杂的贴标签者。但是,工人可以访问并根据整个配置文件决定标签。因此,最好将这些照片视为``特定种族选择使用的个人资料照片的示例'',而不是这些种族本身的照片的示例。

最新版本 弹奏钢琴 可从 Google代码存储库.

2011年11月28日,星期一

重要性感知多项式逻辑更新

由于我在内部使用多项逻辑回归 弹奏钢琴 我很好奇是否有 重要度更新 为了它。我正在使用的损失函数是目标概率向量$ q $和权重$ w $和输入特征$ x $计算的预测概率向量$ p $的交叉熵。
\ begin {aligned}
l(x,w,q)&= \ sum_ {j \ in J} q_j \ log p_j(x,w),\\
p_k(x,w)&= \ frac {\ exp(x ^ \ top w_k)} {\ sum_ {j \ in J} \ exp(x ^ \ top w_j)},\\
w_0&= 0。
\ end {aligned}
通常,通过集成瞬时损失函数的梯度动力学来得出重要性感知更新,对于该更新,通常的SGD更新步骤可以看作是一阶欧拉逼近。对于$ j>0 $,权重的梯度动力学为\ [
\ begin {aligned}
\ frac {d w_j(t)} {d t}&= \ frac {\ partial l(x,w(t),q)} {\ partial w_j(t)} \\
&= \ bigl(q_j-p_j(x,w(t))\ bigr)x。
\ end {aligned}
\]所有的梯度都指向相同的方向,因此我将寻找形式$ w_j(t)= w_j + s_j(t)x $的解,得出\ [
\ begin {aligned}
\ frac {d s_j(t)} {d t}&= q_j-\ tilde p_j(x,w,s(t)),\\
\ tilde p_k(x,w,s)&= \ frac {\ exp(x ^ \ top w_k + s_k x ^ \ top x)} {\ sum_ {j \ in J} \ exp(x ^ \ top w_j + s_j x ^ \ top x)} \\
&= \ frac {p_k(x,w)\ exp(s_k x ^ \ top x)} {\ sum_ {j \ in J} p_j(x,w)\ exp(s_j x ^ \ top x)},\ \
s_j(0)&= 0。
\ end {aligned}
\]在这一点上,我无法取得分析进展。但是,这现在看起来像$(| J | -1)$维ODE,由于可以记住$ p $和$ x ^ \ top x $,因此其右手边可以用$ O(| J |)$计算。因此,在实践中,可以将其数字化集成,而不会产生大量开销(我只看到整体速度降低了10% 弹奏钢琴)。对于顺序案例,Polytomous Rasch有一个类似的技巧。

即使在所有重要权重都为1的数据集上,我也得到了改进的结果。这不是破天荒的举动,但我确实看到了在一些问题上的泛化误差的持续适度改善。我怀疑如果我详尽地搜索学习参数的空间(初始学习率$ \ eta $和幂律衰减$ \ rho $),我可能会找到无需提升重要性即可更新的提升设置。但这是重要性感知更新的好处之一:它使最终结果对学习速率参数的选择不那么敏感。

2011年11月23日,星期三

有序逻辑回归是一个热点

我已将序数支持添加到 弹奏钢琴。如果您想预测某人是否 热不热,现在这是适合您的工具。[1](来自Wikipedia文章的最佳语段:``此外,根据这些研究人员的说法,大脑的基本功能之一是将图像分类为热门或不分类的类别。''很显然,大脑研究人员拥有 所有的乐趣

虽然我已经有一个 工人模型 我需要一个分类器来搭配它。 有序逻辑回归 似乎是自然选择,但由于计算原因,我最终没有使用它。有序逻辑回归概率模型为\ [
\ begin {aligned}
P(Y = j | X = x; w,\ kappa)&= \ frac {1} {1 + \ exp(w \ cdot x-\ kappa_ {j + 1})}-\ frac {1} {1 + \ exp(w \ cdot x-\ kappa_j)},
\ end {aligned}
\]其中$ \ kappa_0 =-\ infty $,而$ \ kappa_ {n + 1} = \ infty $。所以第一个问题是,除非约束$ i<j \暗示\ kappa_i <\ kappa_j $被强制执行,预测概率变为负数。由于我用对数表示概率,这对我来说是个问题。然而,更糟糕的是,关于类别权重相对于权重的梯度的公式在计算上不是很方便。

将此与 多模型Rasch模型,\ [
\ begin {aligned}
p(Y = 0 | X = x; w,\ kappa)&\ propto 1 \\
p(Y = j | X = x; w,\ kappa)&\ propto \ exp \ left(\ sum_ {k = 1} ^ j(w \ cdot x-\ kappa_j)\ right)
\ end {aligned}
\]违反$ i没有特别的数值困难<j \暗示\ kappa_i <\ kappa_j $。当然,如果确实发生了这种情况,则强烈暗示有一些非常错误的事情(例如,响应变量实际上未按照我的假定顺序排序),但关键是我可以进行无限制的优化,然后最后检查是否合理。另外,计算类别概率相对于权重的梯度是相对令人满意的。因此,我采用了Polytomous Rasch功能形式。

这是一个在数据集上运行的示例,试图从他们的个人资料预测Twitter用户的(离散的)年龄。
strategy = 序数
initial_t = 10000
eta = 0.1
rho = 0.9
n_items = 11009
n_labels = 8
n_worker_bits = 16
n_feature_bits = 18
test_only = false
prediction file = (no output)
data file = (stdin)
cumul    since    cumul    since      example current current current  current
avg q    last     avg ce   last       counter   label predict ratings features
-1.15852 -1.15852 -2.20045 -2.20045         2      -1       2       3       33
-1.21748 -1.25678 -1.8308  -1.58437         5      -1       2       4       15
-1.20291 -1.1873  -1.89077 -1.95075        10      -1       2       3       34
-1.15344 -1.09367 -1.94964 -2.01505        19      -1       2       1       18
-1.21009 -1.2637  -1.99869 -2.05351        36      -1       4       1       29
-1.13031 -1.04421 -1.80028 -1.58384        69      -1       3       2       46
-1.1418  -1.15346 -1.58537 -1.35723       134      -1       3       2       35
-1.14601 -1.15028 -1.38894 -1.18489       263      -1       2       4       31
-1.1347  -1.12285 -1.14685 -0.89911       520      -1       3       2       42
-1.12211 -1.10868 -1.03302 -0.91764      1033      -1       3       3       26
-1.11483 -1.10755 -0.91798 -0.80203      2058      -1       3       3       43
-1.10963 -1.10447 -0.82174 -0.72509      4107      -1       3       4       16
-1.07422 -1.03901 -0.82659 -0.83145      8204      -1       2       4       29
-1.02829 -0.98195 -0.84504 -0.86352     16397      -1       3       2       55
-0.98414 -0.93991 -0.85516 -0.86528     32782      -1       2       1       16
-0.94415 -0.90447 -0.84898 -0.84281     65551      -1       2       4       27
-0.90247 -0.86075 -0.86127 -0.87355    131088      -1       2       4       15
-0.88474 -0.83311 -0.86997 -0.89529    176144      -1       4       3       27
applying deferred prior 更新s ... finished
gamma = 0.4991 1.4993 2.5001 3.5006 4.5004 5.5001 6.5001
  13.65s user 0.19s system 89% cpu 15.455 total
弹奏钢琴 可从 Google代码存储库.

脚注1

实际上,“热还是不热”是一个不好的例子,因为可能没有普遍的地面真理热度。而是一个个性化的概念,因此也许可以通过诸如 这个 适用于垃圾邮件过滤。 弹奏钢琴 更适用于具有客观事实的问题,例如根据Twitter用户的Twitter个人资料预测其年龄。听起来不那么性感,对吗?究竟。这就是为什么在脚注中。

2011年11月16日,星期三

众包数据的Logistic回归

最近我一直在处理众包数据 生成模型 在地面真相标签上创建分布。然后,通过考虑我的分类损失函数相对于地面真实分布的期望,我将该分布转换为成本向量,以进行成本敏感的分类。因为生成模型假设典型的工作人员通常是正确的,所以它们受共识驱动:他们将假定在分配标签时始终与同辈意见不一致的工作人员的准确性较低,因此应减少对基础事实的分配。

雷卡尔(Raykar)等等 请注意,接受众包数据训练的分类器最终将与特定众包标签达成或不同意。最好用它来告知模型每个工作人员可能的错误,但是到目前为止,在我一直使用的顺序过程中,这是不可能的:首先要估算出地面真实性,而不是要对分类器进行估算。因此,他们建议共同估算地面真相和分类器,以使彼此相互告知。

在这一点上,让我提供相同的示意图以帮助阐明。


这是与我迄今为止使用的生成模型相对应的板图。未观察到的地面真相标签$ z $与通过向量$ \ alpha $和标量项目难度$ \ beta $参数化的每个工人模型相结合,以创建用于项目的观察到的工人标签$ l $。 $ \ mu $,$ \ rho $和$ p $分别是$ \ alpha $,$ \ beta $和$ z $先前分布的超优先级参数。根据问题(多类,有序多类或多标签),有关$ z $,$ \ alpha $和$ \ beta $如何产生$ l $变化的分布的详细信息,但是上图给出了一般结构。

雷卡尔(Raykar)等等扩展生成模型以允许观察到的项目特征。


该图假定项目具有$ \ psi $的特征,并且给定真实标签$ z $时有条件地独立发出工作标签$ l $。这听起来像是伪造的,因为大概项目特征直接或至少间接地通过标量困难驱动了工人,除非项目特征对于众包工人而言是完全不可访问的。尝试丰富以上图表以解决问题可能是一个合理的下一步,但是事实是所有生成模型都是方便的小说,因此我现在使用上面的内容。雷卡尔(Raykar)等等提供了用于联合分类的批处理EM算法,但以上内容非常适合我一直使用的在线算法。

对于每个输入对$(\ psi,\ {(w_i,l_i)\})$,这是在线过程。
  1. 使用项目特征$ \ psi $,询问使用 适当的计分规则,并将输出解释为$ P(z | \ psi)$。
  2. 使用$ P(z | \ psi)$作为在线算法中$ z $的优先分布 先前讨论过 用于处理众包标签$ \ {(w_i,l_i)\} $。这将产生结果$ P(z | \ psi,\ {(w_i,l_i)\})$。
  3. 针对分配$ P(z | \ psi,\ {(w_i,l_i)\})$使用预期的先前评分规则损失的SGD更新分类器。例如,对数损失(多类logistic回归)的目标函数是交叉熵\ [
    \ sum_j P(z = j | \ psi,\ {(w_i,l_i)\})\ log P(z = j | \ psi)。
    \]
我有一个图表可帮助可视化在线过程。


请注意,如果您观察到特定实例的地面真理$ \ tilde z $,则更新工作模型,就好像$ P(z = j | \ psi)= 1_ {z = \ tilde z} $作为先验分布,并且分类器将更新为$ P(z = j | \ psi,\ {(w_i,l_i)\})= 1_ {z = \ tilde z} $。在这种情况下,分类器更新与``普通''逻辑回归相同,因此可以认为这是对人群数据进行逻辑回归的概括。

我总是将常量项功能添加到每个输入。因此,在没有项目特征的情况下,该算法与之前相同,除了它正在学习$ z $上的先验分布。太好了,这是一件值得指定的事情。但是,在具有项目功能的情况下,事情会变得更加有趣。如果有一个可以强烈表明地面真实性的特征(例如, lang = es 在Twitter资料上强烈地表明了西班牙裔种族),该模型可以潜在地识别出准确的工人,这些工人在标签上的每个项目上都与同龄人不同, 如果 工人在具有共同特征的物品上与其他工人同意。如果一个工作人员碰巧变得不幸并与多个不准确的工作人员一起完成多项任务,则可能会发生这种情况。当那些不准确的工人对其他比较模糊的项目的影响减小时,这才真正开始得到回报。

这是一个真实的例子。任务是预测Twitter个人资料的性别。要求机械土耳其人工作人员访问特定的个人资料,然后选择性别:男性,女性或两者都不选。 ``都不''主要用于像这样的组织的Twitter帐户 洛杉矶道奇队, 不必要 保罗。物品的功能可以通过以下方式获得 GET用户/查找 (请注意,所有这些功能对于Mechanical Turk工人都是显而易见的)。训练示例最终看起来像
A26E8CJMP5S4WN:2,A8H56XB9K7DB5:2,AU9LVYE38Q6S2:2,AHGJTOTIPCL8X:2 WONBOTTLES,180279525|firstname taste |restname this ? ?? |lang en |description weed girls life cool #team yoooooooo #teamblasian #teamgemini #teamcoolin #teamcowboys |utc_offset utc_offset_-18000 |profile sidebar_252429 background_1a1b1f |location spacejam'n in my jet fool
如果它看起来像Vowpal Wabbit,那是因为我再次撕掉了它们的输入格式,但是标签规范得到了丰富。特别是可以指定零个或多个worker:label对,以及一个可选的true标签(只是一个标签,没有worker)。这是训练集中的多次通过的样子。
initial_t = 10000
eta = 1.0
rho = 0.9
n_items = 10130
n_labels = 3
n_worker_bits = 16
n_feature_bits = 16
test_only = false
prediction file = (no output)
data file = (stdin)
cumul    since    cumul    since      example current current current  current
avg q    last     avg ce   last       counter   label predict ratings features
-0.52730 -0.52730 -0.35304 -0.35304         2      -1       0       4        7
-0.65246 -0.73211 -0.29330 -0.25527         5      -1       0       4       23
-0.62805 -0.60364 -0.33058 -0.36786        10      -1       1       4       13
-0.73103 -0.86344 -0.29300 -0.24469        19      -1       0       4       12
-0.76983 -0.81417 -0.25648 -0.21474        36      -1       0       4       20
-0.75015 -0.72887 -0.26422 -0.27259        69      -1       2       4       12
-0.76571 -0.78134 -0.25690 -0.24956       134      -1       2       4       37
-0.76196 -0.75812 -0.24240 -0.22752       263      -1       0       4       21
-0.74378 -0.72467 -0.25171 -0.26148       520      -1       2       4       12
-0.75463 -0.76554 -0.24286 -0.23396      1033      -1       2       2       38
-0.72789 -0.70122 -0.24080 -0.23874      2058      -1       0       4       30
-0.68904 -0.65012 -0.25367 -0.26656      4107      -1       2       4       25
-0.61835 -0.54738 -0.25731 -0.26097      8204      -1       0       4       11
-0.55034 -0.48273 -0.24362 -0.23001     16397      -1       2       3       12
-0.49055 -0.43083 -0.20390 -0.16423     32782      -1       2       3       29
-0.44859 -0.40666 -0.15410 -0.10434     65551      -1       2       4       12
-0.42490 -0.40117 -0.11946 -0.08477    131088      -1       0       4        9
-0.41290 -0.40090 -0.10018 -0.08089    262161      -1       2       4        9
-0.40566 -0.39841 -0.08973 -0.07927    524306      -1       0       4       33
-0.40206 -0.39846 -0.08416 -0.07858   1048595      -1       2       4       22
-0.40087 -0.39869 -0.08206 -0.07822   1620800      -1       0       4       18
applying deferred prior 更新s ... finished

gamma:
     \  ground truth
      |   0       1       2
label |
    0 | -1.0000 0.0023  0.0038
    1 | 0.0038  -1.0000 0.0034
    2 | 0.0038  0.0018  -1.0000
在我的笔记本电脑上生成该输出大约需要3分钟。如果那看起来像Vowpal Wabbit,那是因为我再次撕掉了它们的输出格式。前两列是EM辅助功能,类似于对数似然,因此,增加的数字表示工作人员模型能够更好地预测工作人员标签。接下来的两列是分类器的交叉熵,因此越来越多的数字表明分类器能够更好地根据项目特征预测地面事实的后验(相对于众包工作者标签)。

以上软件可从 Google代码存储库。叫做 弹奏钢琴,因为我发现使用众包工作者为分类器提供训练数据的过程让人联想到 冯内古特的反乌托邦,其中上一代人类大师级工匠的动作记录在磁带上,然后永久性地从工业生产中驱逐出去。马上 弹奏钢琴 只支持名义上的问题,但是我已经写了一些东西,因此希望将序数和多标签添加到同一可执行文件中会很容易。

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月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兔子 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 | $设置得不太大,则会给出看起来合理的超优先级(否则,它们将停留在超优先级均值)。这很有用,因为在我的标称标签提取技术中,超均值混淆矩阵可以帮助识别任务问题(或数据处理中某处的错误)。

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代码上的代码存储库。我将在短期内将其他算法的在线版本放在一起(基本方法适用于所有算法,但是每种特定的可能性都有不同的技巧)。