2011年12月28日,星期三

标签不平衡的二进制上下文

在我的 以前的帖子 我注意到,在对正样本进行二次抽样时,重要性加权经验风险的方差低于对正样本而非负样本进行检验时的实证风险的方差(在非抽样分布上)。我希望这可以扩展到更广泛的假设集,因为``好''假设在肯定中更可能是正确的,因为它们更普遍。不幸的是,当一个标签盛行($ q>1/2 $)有一些非常好的假设(损失$ l(h)= \ rho $)可以完美地将不太普遍的标签实例分类($ r_0 = 1 $),并在更普遍的标签实例上犯一些错误标签实例($ r_1 = 1-\ rho / q $)。这种假设的重要性加权经验风险方差将在二次抽样下增加($ r_1<r_0 $),这似乎是一件坏事。因此,我决定退后一步并进行一些模拟,以确保我没有发疯。

二进制上下文分类

因此,让我描述一个二进制上下文分类的游戏。有两个由$ X = \ {0,1 \} $索引的硬币。每个硬币都有由对手选择的正面$ q_ {1 | x} $的概率,并且对手也选择了硬币零$ q_0 $的概率。玩家可以观察到$ n $ IID训练示例$(x,y)$,包括选择硬币和抛硬币。然后玩家必须将每个硬币分类为``正面硬币''$(\ hat y = 1 | x)$或``尾硬币''$(\ hat y = 0 | x)$。然后,玩家根据每个示例向对手支付预期的遗憾,即,平均而言,与最佳常量对相比,玩家犯下的预测错误要多多少倍。玩家将再次在训练集上使用经验风险最小化策略,并随机断开联系。现在玩游戏的方法如下:
  1. 裁判宣布训练套装大小$ n $。
  2. 对手选择$ q_0 $,$ q_ {1 | 0} $和$ q_ {1 | 1} $。
  3. 裁判通过重复以下IID生成大小为$ n $的训练集:
    1. 当概率$ q_0 $时选择$ x = 0 $;否则$ x = 1 $。
    2. 选择概率为$ q_ {1 | x} $的$ y = \ mathrm {heads $},否则选择$ y = \ mathrm {tails} $。
  4. 玩家将经验风险降至最低,并报告$(\ hat y | 0,\ hat y | 1)$。
  5. 对手会从Player收集每个示例的预期遗憾。
预期的遗憾由\ [
q_0 \ Psi(q_0,q_ {1 | 0},n)+(1-q_0)\ Psi(1- q_0,q_ {1 | 1},n)
\] 其中\ [
\ begin {aligned}
\ Psi(s,q,n)&= \ sum_ {c = 0} ^ n {n \选择c} s ^ c(1-s)^ {n-c} \ Phi(q,c),\\
\披(q,n)&= \bigl|2 q - 1\bigr| \;p(\ hat y \ neq y ^ * | q; n)。
\ end {aligned}
\] $ \ Phi $是上下文无关游戏的遗憾,它必须在与每个硬币相关的(现在是随机的)训练示例数上取平均。

有一个分析上可证明的局部最优形式,其期望后悔形式为$ q ^ * _ 0 = 1/2 $,$ q ^ * _ {1 | 0} = q ^ * _ {1 | 1} $成为全局最优值:其中有四个对应于硬币的对称性,约为$ 1/2 $。换句话说,对对手来说,最好的选择是选择每个硬币具有相同的概率,并为每个硬币选择相同的中间偏差。这是$ q ^ * _ {1 | 0} = q ^ * _ {1 | 1}的最佳选择>1/2 $代表$ n $的变化,以及游戏对对手的价值,

标签不平衡

现在,我将修改二进制上下文分类的游戏,以便对手必须选择与$ E [1_ {y = 1}] \ geq \ rho一致的参数>1/2 $,即,对手必须总体上有利于正面反面。给定设置,这意味着$ q_0 q_ {1 | 0} +(1-q_0)q_ {1 | 1} \ geq \ rho>1/2 $。现在玩游戏的方法如下:
  1. 裁判员宣布训练集合大小$ n $,最小无条件头部概率$ \ rho> 1/2$.
  2. 对手选择$ q_0 $,$ q_ {1 | 0} $和$ q_ {1 | 1} $,这样$ q_0 q_ {1 | 0} +(1-q_0)q_ {1 | 1} \ geq \ rho $。在不失一般性的前提下,我将标记硬币,使得$ q_ {1 | 1} \ geq q_ {1 | 0} $。
  3. 裁判通过重复以下IID生成大小为$ n $的训练集:
    1. 当概率$ q_0 $时选择$ x = 0 $;否则$ x = 1 $。
    2. 选择概率为$ q_ {1 | x} $的$ y = \ mathrm {heads $},否则选择$ y = \ mathrm {tails} $。
  4. 玩家将经验风险降至最低,并报告$(\ hat y | 0,\ hat y | 1)$。
  5. 对手会从Player收集每个示例的预期遗憾。
这将通过两种方式降低游戏对对手的价值。首先,对手的选择越来越多地限制为$ \ rho \至1 $,因此最佳可用游戏将不是很好。其次,如果玩家知道限制条件,则可以排除(``tails'',``tails'')的答案,因为这是不可能的。在剩余假设上将经验风险最小化将导致玩家说出(``heads'',``tails'')或(``tails'',``heads''),即使两个上下文都不占多数在训练集中。

首先假设约束对对手选择的影响,假设玩家仍然在不考虑约束的情况下进行经验风险最小化。据我所知,共有三种制度:
  1. 如果$ \ rho $足够接近1/2,则不会影响对手的最佳玩法(除非它必须选择与$ q ^ * _ {y | x}相对应的模式>1/2 $):分别通过$ q ^ * _ 0 = 1/2 $和$ q ^ * _ {1 | 0} = q ^ * _ {1 | 1} = \ theta $对待每个硬币。
  2. 当$ \ rho $增加到$ \ theta $以上时,最初的最佳操作仍然是通过$ q ^ * _ 0 = 1/2 $相同地对待每个硬币,但要调整$ q ^ * _ {1 | 0} = q ^ * _ {1 | 1} = \ rho $符合约束。
  3. 最终会有一个相变,选择$ q_0 $来满足约束条件使$ q ^ * _ {1 | 1} \ neq q ^ * _ {1 | 0} $变得更好。非常快地将$ q ^ * _ {1 | 1} \转换为1 $,尽管它仍然具有减少与另一枚硬币关联的训练数据量并使另一枚硬币保持在$ 1/2 $附近的双重目的。当$ \ rho $增加$ q ^ * _ {1 | 1} = 1 $时,$ q ^ * _ {1 | 0} \至1 $,而$ q ^ * _ 0 \至0 $。
现在,我将结合玩家意识到的约束条件,并因此在减少的假设集上进行经验风险最小化,即从不选择(``尾巴'',``尾巴'')。边界和最佳位置略有变动,但这并没有从根本上改变对手的策略;但是,它确实会明显降低$ q_ {1 | 1}中对手的游戏价值<1美元制度(出于比较目的,我在下图中复制了上图的预期遗憾)。
在$ q_ {1 | 1} = 1 $的情况下,玩家进行无约束的经验风险最小化时选择的机会(“尾巴”,“尾巴”)很小,以至于基本上没有影响游戏价值。

二次抽样

现在,我将修改游戏,以便对训练数据进行二次采样。由于对手被迫在总体上偏向于正面而不是正面,因此我们将对正面进行子采样。现在玩游戏的方法如下:
  1. 裁判员宣布训练集合大小$ n $,最小无条件头部概率$ \ rho> 1/2$.
  2. 玩家宣布$ w $。
  3. 对手选择$ q_0 $,$ q_ {1 | 0} $和$ q_ {1 | 1} $,这样$ q_0 q_ {1 | 0} +(1-q_0)q_ {1 | 1} \ geq \ rho $。在不失一般性的前提下,我将标记硬币,使得$ q_ {1 | 1} \ geq q_ {1 | 0} $。
  4. 裁判通过重复以下IID直到生成$ n $个样本来生成训练集:
    1. 当概率$ q_0 $时选择$ x = 0 $;否则$ x = 1 $。
    2. 选择概率为$ q_ {1 | x} $的$ y = \ mathrm {heads $},否则选择$ y = \ mathrm {tails} $。
    3. 如果$ y = \ mathrm {heads} $,则以概率$ w $拒绝样本。
  5. 玩家将重要性加权的经验风险降至最低,并报告$(\ hat y | 0,\ hat y | 1)$。玩家将所有假设最小化,包括(``tails'',``tails'')。
  6. 对手会从Player收集每个示例的预期遗憾。
二次采样在此游戏中具有三种效果。
  1. 它改变了训练数据中出现的上下文的分布,从而导致更可能产生拖尾的上下文更加频繁地出现。特别是训练集的有效$ q_0 $为\ [
    \ tilde q_0(q_0,q_ {1 | 0},q_ {1 | 1},w)= \ frac {q_0(q_ {1 | 0} w +1-q_ {1 | 0})} {q_0(q_ {1 | 0} w +1-q_ {1 | 0})+(1-q_0)(q_ {1 | 1} w +1-q_ {1 | 1})}。
    \] 实际上可能会引起问题:如果Player没有针对特定上下文的任何训练数据,则对该上下文的预测是随机的,并且在$ q_ {1 | 0}时进行极端子采样<1 $和$ q_ {1 | 1} = 1 $将消除上下文1的所有训练数据,从而增加遗憾。但是,中等量的二次采样将避免在“显而易见”的$ q_ {1 | 1} = 1 $上下文中“浪费”训练数据,因为只需要一个观察就可以使该上下文正确。
  2. 上下文中头与尾的分布被修改,\ [
    \ tilde q_ {1 | x}(q_ {1 | x},w)= \ frac {q_ {1 | x} w} {q_ {1 | x} w +(1-q_ {1 | x})} 。
    \]
  3. 它将说出``正面''的阈值从看到训练数据中的$ n / 2 $正面更改为$ n w /(1 + w)$。如果有特殊要求,价格为$ w<1美元,非零的关系被打破,有利于团长。 (如果没有针对特定情况的训练数据,则对于每种选择,重要性加权的经验风险都相同,因此,玩家平均分配随机数)。
以下是$ n = 21 $发生的情况:
  1. 当$ \ rho $接近1/2时,播放器会选择少量的二次采样$ w ^ * = 1-\ epsilon $,从本质上讲,这种关系会导致有利于头的关系破裂。对手通过打一个正面硬币和一个反面硬币来缓解平局的效果。
  2. 随着$ \ rho $的增加,满足一枚正面硬币和一枚反面硬币的约束变得太昂贵了,因此,对手打出两个相同的正面硬币,玩家获得决胜局优势。
  3. 随着$ \ rho $进一步增加,对手将设置$ q_ {1 | 1} = 1 $。此时,玩家选择一个$ w ^ * $,这会使对手无视播放$ q ^ * _ {1 | 0}<1/2 $与$ q ^ * _ {1 | 0}>1/2 $。 (该图似乎在此间隔内在这两个解决方案之间随机切换:因此,我选择了$ q ^ * _ {1 | 0}<1/2 $点使图表更清晰可见)。
  4. 随着$ \ rho $的进一步增加,玩家有时会切换到$ w ^ * = 1/2-\ epsilon $。对手通过选择$ q ^ * _ {1 | 0}进行响应>1/2 $。 $ w ^ * $的这种选择打破了2 / 3rd的平局,转为正面。
  5. 随着$ \ rho $进一步增加,玩家有时会切换回选择$ w ^ * $,这会使对手无视播放$ q ^ * _ {1 | 0}<1/2 $与$ q ^ * _ {1 | 0}>1/2 $。 (同样,为了清晰起见,我选择了$ q ^ * _ {1 | 0}< 1/2$ points).
  6. 作为$ \ rho \ uparrow 1 $,$ w ^ * \ uparrow 1 $,而对手则扮演$ q_ {1 | 0}>1/2 $。二次抽样的好处再次由决胜局效应控制。

评论

负采样消除确实有助于简化设置。但是,打破非零关系(即,在特定情况下训练头部和尾部的次数相等)是举升机的主要组成部分。这可能是基本的东西,也可能是设置的产物。在$ \ rho $的某些值中,子采样似乎以打破平局的方式起作用,但是选择的子采样量很小。
特别是我看不到$ w ^ * \ to 0 $就像$ \ rho \ to 1 $。这可能是因为每当$ q_ {1 | 0}<1 $和$ q_ {1 | 1} = 1 $,因为$ w ^ * \ to $$ 0对于上下文1没有训练数据的机会趋于统一,然后随机化规则引起一些遗憾。如果Player在没有训练数据的情况下预测上下文,我可能会得到不同的结果。

总体而言,该示例不支持对与更频繁出现的标签相关联的数据进行积极的子采样以减小分类训练集的大小的想法。回到绘图板!

2011年12月20日,星期二

负采样:一些进展

在我的 以前的帖子 我用数字方法研究了无上下文分类游戏,并指出对更普遍的类标签进行二次采样是有利的。我试图使用 Azuma-Hoeffding不等式,但得出的结果表明建议对期望的均衡标签频率进行二次抽样,这在经验上过于激进。

幸好 贝内特不等式 也适用;在零均值变量$ \ left(\ tilde q(q,w)-Y_i \ right)$上,它给出\ [
\ begin {aligned}
\ mathrm {Pr} \ left(\ sum_i Y_i<\ frac {n w} {1 + w} \ right)&=
\ mathrm {Pr} \ left(n \ tilde q(q,w)-\ sum_i Y_i>n \ left(\ tilde q(q,w)-\ frac {w} {1 + w} \ right)\ right)\\
&\ leq \ exp \ left(-\ frac {n \ sigma ^ 2} {a ^ 2} h \ Bigl(\ frac {a t} {\ sigma ^ 2} \ Bigr)\ right),\\
\ sigma ^ 2&= E [\ left(\ tilde q(q,w)-Y_i \ right)^ 2] = \ tilde q(q,w)(1-\ tilde q(q,w)),\ \
a&= \ max \ {\ tilde q(q,w),1-\ tilde q(q,w)\},\\
t&= \ tilde q(q,w)-\ frac {w} {1 + w},\\
h(u)&=(1 + u)\ log(1 + u)-u。 \\
\ end {aligned}
\] 该界限在捕获作为$ w $函数的后悔结构方面做得更好。
在这里,红色和蓝色点是整数截止边界上下的实际遗憾,绿色是Azuma-Hoeffding边界,橙色是Bennett边界。垂直虚线是每个边界的最小值。尽管Azuma过于激进,但Bennett过于保守,但做得更好。在给定$ p $的情况下,两个边界都预测了一个最佳$ w $,它独立于$ n $;这是它们与各种$ p $的精确计算相比的方式。 (确切的计算取决于$ n $,但是收敛为$ n \ to \ infty $; $ n = 105 $似乎接近此限制。)

概括

贝内特的不等式对更普遍的问题有何看法?假设在$ X乘以Y $的分布$ D $和一个假设$ h:X \ to Y $,我们正在根据0-1损失进行评估。实际风险为\ [
l(h)= E _ {(x,y)\ sim D} [1_ {h(x)\ neq y}]。
\] 现在假设我们从$ \ tilde D_w $绘制训练数据,定义为
  1. 从$ D $中提取$(x,y)$。
  2. 如果$ y = 1 $,则以概率$(1- w)$拒绝$(x,y)$。
  3. 否则,接受$(x,y)$。
换句话说,对正样本进行二次采样。给定从$ \ tilde D_w ^ n $中抽取的样本$ S $,重要性加权经验风险为\ [
\ begin {aligned}
\ hat L(w,h)&= \ frac {1} {| S |} \ sum _ {(x,y)\ in S} \ frac {D(x,y)} {\波浪线D(x,y )} 1_ {h(x)\ neq y} \\
&= \frac{1}{|S|} \sum_{(x, y) \in S} \lambda (y;w,q)1_ {h(x)\ neq y},\\
\ lambda(y; w,q)&= \ begin {cases}
w ^ {-1}(1- q(1- w))& \mathrm{if}\;\; y = 1 \\
1-q(1-w)& \mathrm{if}\;\; y = 0
\ end {cases},
\ end {aligned}
\] 其中$ q = E _ {(x,y)\ sim D} [1_ {y = 1}] $。 $ \ hat L(w,h)$是所有$ 0的$ l(h)$的无偏估计量<w \ leq 1 $。很高兴证明当$ w时发生``最佳估计''$ \ hat L(w,h)$< 1$ 如果 $q >1/2 $。注意$ \ hat L(1,h)$只是$ D ^ n $样本中未加权的经验风险。

\ i ^ \ mathrm {th} $样本的瞬时损失由\ [
\ begin {aligned}
L_i(w,h)&= \lambda (Y_i;w,q)1_ {h(X_i)\ neq Y_i},\\
&= \ begin {cases}
0 & \mathrm{with\;可能性}\;\; \ tilde q(q,w)r_1 +(1-\ tilde q(q,w))r_0 \\
\ lambda(0; w,q)& \mathrm{with\;可能性}\;\; (1-\波浪线q(q,w))(1-r_0)\\
\ lambda(1; w,q)& \mathrm{with\;可能性}\;\; \ tilde q(q,w)(1-r_1)
\ end {cases},\\
\ tilde q(q,w)&= \ frac {q w} {q w +1-q},
\ end {aligned}
\] 其中$ r_z = E _ {(x,y)\ sim D} [1_ {h(x)= z} | y = z] $。 (注意$ r_z $不受子采样的影响。)序列$ \ sum_i \ left(L_i(w,h)-l(h)\ right)$是a,因此Azuma-Hoeffding不等式成立。但是,Azuma-Hoeffding是由相邻序列成员之间的最大可能偏差驱动的,当$ w = 1 $时偏差最小,因此它并不表示二次采样有帮助。但是Bennett的不等式也适用,并且受方差驱动,有时会更好。 \ [
\ begin {aligned}
E [L_i(w,h)^ 2]&= (1 - \tilde q (q, w)) (1 - r_0) \lambda (0;w,q)^ 2 + \ tilde q(q,w)(1-r_1)\ lambda(1; w,q)^ 2,\\
\ frac {d} {dw} E [L_i(w,h)^ 2]&=-\ frac {(1- q)q(1- r_1-(1- r_0)w ^ 2)} {w ^ 2 },\\
\剩下。 \ frac {d} {d w} E [L_i(w,h)^ 2] \ right | _ {w = 1}&=(1-q)q(r_1-r_0),\\
\frac{d^2}{d w^2} E [L_i(w,h)^ 2]&= \frac{2 (1 - q) q (1 - r_1)}{w^3} > 0.
\ end {aligned}
\] 的意思是:如果$ r_1>r_0 $的取值范围为$ w <1 $,估计量的方差低于$ w = 1 $时。这表明,只要要评估的假设在阳性实例上比阴性实例更可能正确时,对阳性样本进行一定程度的子采样是有益的,例如琐碎的假设$ h(\ cdot)= 1 $。有趣的是,即使$ q也是如此< 1/2$.

目前尚不清楚如何使用此结果,因为通常一个人想对一组假设限制经验风险的偏差,其中一些假设不能满足$ r_1>r_0 $。这是一个主意:因为我们知道$ q = E _ {(x,y)\ sim D} [1_ {y = 1}]>1/2 $,假设我们有某种方式(很有可能?)仅考虑以下假设:$ E _ {(x,y)\ sim D} [1_ {h(x)= 1}] \ geq \ rho \ geq q $。在这种情况下,解决方案\ [
\ begin {aligned}
\ min \;&r_1-r_0 \\
&s.t。 \\
0&\ leq r_1 \ leq 1 \\
0&\ leq r_0 \ leq 1 \\
\ frac {1} {2}&<q \ leq \ rho \ leq 1 \\
E _ {(x,y)\ sim D} [1_ {h(x)= 1}]&= q r_1 +(1- q)(1-r_0)\ geq \ rho,\\
\ end {aligned}
\] 由$(r_1-r_0)=(\ rho-q)/(1-q)\ geq 0 $给出,即,这样的假设集将受益于二次采样。这个约束与我在机器学习软件中见过的任何东西都不对应。但是,假设$ E _ {(x,y)\ sim D} [1_ {h(x)= 1}] \ leq \ chi \ leq q $。然后解\
\ begin {aligned}
\ min \;&l(h)=(1-q)(1-r0)+ q(1-r1)\\
&s.t。 \\
0&\ leq r_1 \ leq 1 \\
0&\ leq r_0 \ leq 1 \\
\ frac {1} {2}&< q \leq 1 \\
E _ {(x,y)\ sim D} [1_ {h(x)= 1}]&= q r_1 +(1-q)(1-r_0)\ leq \ chi \\
0&\ leq \ chi \ leq q,\\
\ end {aligned}
\] 由$ l(h)= q-\ chi $给出。由于常数假设$ h(\ cdot)= 1 $损失了$ 1-q $,因此它比$ \ chi的任何假设都好<2 q-1 $。因此,当数据集非常不平衡($ q \ to 1 $)时,可能的情况是,其估计量因二次抽样而退化的假设远非最小值,因此不太可能使经验风险最小化器混淆。这个论点显然需要改进,但它确实与在非常不平衡的数据集上进行在线学习时发生的情况相对应:首先,该模型迅速学会说一切都是主导类,然后开始找出各种例外情况。

2011年12月18日,星期日

负采样:一个简单的例子

我最近读了Agarwal等人的论文。等上 万亿级学习。他们注意到数据集的统一子采样会降低分类器的性能(换言之,它有助于使用所有数据),从而激发了Terascale学习。这让我再次考虑了数据集的非均匀子采样。

我尤其对二进制分类问题中与更普遍的标签相关的数据进行二次采样感兴趣。这不同于典型的主动学习方案:我假设所有数据标签都可用并且可以免费检查,但是由于某些原因,您不想全部处理。也许数据是由分布式传感器网络收集的,您想通过在外围设备中放置数据来最大程度地降低通信成本,或者您有一个大数据集,并且想要生成一个适合笔记本电脑的样本,以便进行实验在旅行时。

我有 凭经验说好运 面对涉及非常不平衡数据的分类问题而偏向负样本时,对负样本进行二次抽样。这种做法很合理 当目标函数是AUC时,因为当数据集具有相同数量的正数和负数时,由于经验AUC与实际AUC之间存在偏差,对于给定的示例预算,该偏差会最小化。但是,尽管经验上我在分类损失和有偏的子采样方面表现不错,但我仍然没有类似的分类结果。因此,我提出了以下激励性的例子。

上下文无关分类

让我首先描述一个上下文无关分类的游戏。
  1. 对手选择$ q $。
  2. 裁判通过重复以下IID直到接受$ n $个样本来生成训练集$ S $:
    1. 选择概率为$ q $的$ y = \ mathrm {heads} $,否则选择$ y = \ mathrm {tails} $。
  3. 玩家检查训练集$ S $,通过均等随机化将$ \ {\ mathrm {heads},\ mathrm {tails \} $打破平局的经验风险降至最低,并报告$ \ hat y(S)$。
  4. 裁判员根据示例收集来自玩家的预期遗憾,定义为\ [
    | 2 q-1 | 1 _ {\ hat y(S)\ neq y ^ *(q)},
    \] 其中\ [
    y ^ *(q)= \ begin {cases}
    \ mathrm {heads}& \mathrm{if}\;\; q \ geq \ frac {1} {2} \\
    \ mathrm {tails}和\ mathrm {other}
    \ end {cases}。
    \] 换句话说,玩家根据平均平均比最佳常量多多少个预测错误来支付费用。
在训练集中最小化经验风险的策略归结为说出玩家在训练集中看到的头数超过$ n / 2 $的头,如果在训练集中看到少于$ n / 2 $头的头则说的尾巴,以及如果正好在训练集中$ n / 2 $的头部说出正面或反面的可能性相等。 $ n $为奇数时,玩家犯错的机会由\ [
\ mathrm {Pr}(\ hat y \ neq y ^ * | q; n)= \ begin {cases}
\ sum_ {c = 0} ^ {\ lfloor n / 2 \ rfloor} {n \ choose c} q ^ c(1-q)^ {n-c}& \mathrm{if}\;\; q \geq 1/2 \\
\ sum_ {c = \ lfloor n / 2 \ rfloor + 1} ^ n {n \ choose c} q ^ c(1-q)^ {n-c}& \mathrm{if}\;\; q < 1/2
\ end {cases}。
\] 当$ n $甚至是偶数时,有一个附加项对应于给定随机值的随机数。玩家犯错的可能性最大为$ q \至1/2 $,但是预期后悔与$ | 2 q-1 | $成正比;因此,对手的最佳选择是选择一个中间$ q $。对于$ n = 21 $,它看起来如下所示:
随着$ n $的增加,对手的最佳比赛向$ q = 1/2 $移动,而对手的游戏价值也随之下降。

重要性加权的上下文自由分类

现在考虑当玩家决定对训练数据中的样本进行二次抽样,然后将重要性加权的经验风险降到最低时会发生什么。需要明确的是,游戏如下:
  1. 玩家选择正面的二次采样率$ w $。
  2. 对手选择$ q $。
  3. 裁判通过重复以下IID直到接受$ n $个样本来生成训练集$ S $:
    1. 选择概率为$ q $的$ y = \ mathrm {heads} $,否则选择$ y = \ mathrm {tails} $。
    2. 如果$ y = \ mathrm {heads} $,则以概率$ w $拒绝样本。
  4. 玩家检查训练集$ S $,通过相等随机性将$ \ {\ mathrm {heads},\ mathrm {tails \} $打破平局的重要性加权经验风险最小化,并报告$ \ hat y(S)$。
  5. 裁判按照示例从玩家那里收集预期的遗憾(如上所述)。

理论建议

二次采样有两个作用。首先是将训练中头部的概率设置为\ [
\ tilde q(q,w)= \ frac {q w} {1-q + q w}。
\] 第二个方法是将猜测磁头所需的计数数量从$ n / 2 $更改为$ n w /(1 + w)$。

当$ q> 1/2$ 和 $0 <w \ leq 1 $,$ \ frac {w} {1 + w}<\ tilde q(q,w)$,因此不正确的概率在上方受 Azuma-Hoeffding不等式 在the $ \ sum(Y_i-\ tilde q(q,w))上$,\ [
\ begin {aligned}
\ mathrm {Pr}(\ hat y \ neq y ^ * | q; w; n)&= \mathrm{Pr} \left(Y <\ frac {n w} {1 + w} \ right)+ \ frac {1} {2} \ mathrm {Pr} \ left(Y = \ frac {n w} {1 + w} \ right)\\
&\ leq \ mathrm {Pr} \ left(Y \ leq \ frac {n w} {1 + w} \ right)\\
&= \ mathrm {Pr} \ left(Y-n \ tilde q(q,w)\ leq n \ left(\ frac {w} {1 + w}-\ tilde q(q,w)\ right)\对) \\
%&\ leq \ exp(\ frac {-n ^ 2 \ left(\ frac {w} {1 + w}-\ tilde q(q,w)\ right)^ 2} {2 n \ max \ {\波浪线q(q,w)^ 2,(1-\波浪线q(q,w))^ 2 \}}))\\
&\ leq \ exp \ left(-\ frac {n} {2 \ max \ {\ tilde q(q,w)^ 2,(1-\ tilde q(q,w))^ 2 \}} \ left (\波浪线q(q,w)-\ frac {w} {1 + w} \ right)^ 2 \ right)\\
&\ doteq \ varphi(q,n,w)。
\ end {aligned}
\] 这是关于此绑定的有趣之处:当$ \ tilde q(q,w)= \ frac {1} {2} $时,由于\ [
\ begin {aligned}
\ frac {d} {dw} \ log \ varphi(q,n,w)&= \ begin {cases}
-\ frac {n w} {4(1-3 q + 2 q ^ 2)^ 2(1 + w)^ 3} < 0 & \mathrm{if}\;\; \tilde q (q, w) < \ frac {1} {2}\\ \frac{n}{4 (1 - 2 q)^2 q^2 (1 + w)^3} > 0 & \mathrm{if}\;\; \tilde q (q, w) > \ frac {1} {2}
\ end {cases}。
\ end {aligned}
\] 因此,边界建议对均衡的标签期望值进行二次采样。考虑到熵在 大偏差理论.

请注意,如果对手选择$ q<1/2 $,我们可以重新标记硬币并重复参数(即对另一枚硬币进行二次采样)。但是,由于在游戏中是在对手选择$ q $之前选择了二次采样率,因此玩家应选择$ w = 1 $来使maxmax最优,除非对手被限制为拥有$ q >1/2 $。这个游戏太简单了,无法以这种方式限制对手,而又不会使玩家策略变得微不足道,但是在更丰富的背景下,这种约束是有道理的。

实际发生了什么

不幸的是,界限有些松散,并且在无上下文的游戏中暗示了比精确计算所保证的更具攻击性的子采样。这是当对手玩$ q = 3/4 $时,预期的后悔与$ w $对于$ n = 21 $的关系,
二次采样率是连续的,但实现是离散的,因此遗憾的是离散的跳跃,因为``收支平衡''的点击次数通过整数值(红色= $ \ epsilon $以上=``打破联系而赞成尾巴'';蓝色= $ \ epsilon $以下=``打破领带而赞成头'')。虚线是$ w = 1 $时的遗憾,绿线是界限。确实有一个最佳$ w<1 $,但这可能是由于实现的离散性质,而不是根本原因。现在让我们看一下$ n = 105 $的同一个图形。
现在很明显,有一个最佳的$ w<1 $,而且很明显,界限表明$ w $过于激进。

回到绘图板。

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年11月7日,星期一

2011年11月3日,星期四

人工智能与劳动力市场

机器学习会议通常会邀请来自机器学习之外但与机器学习有关的领域的从业者进行邀请演讲。我希望看到一位受邀的经济学家谈论有关人工智能将如何改变劳动力市场的当前最佳猜测。

当前的经济环境让人想起反乌托邦小说 钢琴演奏者 在美国,富裕的工程师阶层与因自动化而流离失所的体力劳动阶层之间存在着巨大的失业和极端的收入不平等,这在美国颇受困扰。实际上,尽管失业率尚未恢复,但GDP已恢复到衰退前的水平,导致一些经济学家制定了 零边际产品工人假说。零MP假设的前提是,自从大衰退开始以来``与此同时,没有重大技术突破'',因此当工人被雇用时,他们的MP为零,但没人注意到。但是,正如NPR指出的那样, 技术正在淘汰熟练的工作。他们举了一个与我很接近的法律职业的例子:首先是因为我妻子是被解雇的律师,其次是因为我咨询了一家有兴趣在Vowpal Wabbit中使用LDA功能的电子发现公司。以提高他们的电子发现效率。我要说的是,自从大萧条(2007)开始以来,机器学习发生了技术变革,伴随着知识的扩散和开源工具包的出现。此外,由于经济好时机延迟了成本压力,因此可能尚未应用过去十年机器学习中的一些技术变革(取得了巨大的进步!)。因此,我怀疑工人以过时的方式流离失所,即正式成为国会议员,但由于技术变革而不再需要。

总的来说,我对技术和生产率的提高将为所有人带来更好的生活水平感到乐观。但是,美国最近的收入不平等历史表明,创造的财富并不一定在整个人口中公平分配。对于我们正在创造的人工智能未来而言,了解谁可能是劳动力市场的赢家和输家对机器学习社区而言将是一件大事。

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

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个),我认为值得尝试。在入睡之前将其启动,也许您会在早晨感到惊喜。

2011年8月29日,星期一

从众包数据集中提取多标签

之前,我已经讨论了用于处理众包数据的技术,这些数据与``给定项目,从一组固定的标签中选择最佳的单个标签''形式的任务相对应,这对应于成本敏感的多类分类(CSMC)。该处理的结果可能是最终决定,或者可能是用于训练监督学习系统的成本向量。

现在我关注的形式是``给定一个项目,从一组固定的标签中选择零个或多个适用标签'',这与成本敏感的多标签分类(CSML)相对应。处理CSML的一种策略是将一系列独立的二进制分类问题简化为一组,每个问题都预测是否应为项目分配特定的标签。我将此策略称为IBR。如果对原始CSML问题的成本函数进行加权,则IBR是一致的减少 汉明损失 , 但是 与其他CSML损失不一致 (例如,整个组合损失0/1)。在实践中,对于引起的子问题有一定的遗憾,它甚至可能不是加权汉明损失的好策略。

尽管如此,这是我执行过的唯一方法。例如,如果我有一个10标签CSML问题,我将把众包数据处理成10个对应于二进制分类的数据集,运行 标称提取物 在10个数据集的每个数据集上,然后合并结果。此策略存在一些不良方面,所有这些方面都是同一潜在问题的不同方面。首先,如上所述,当将众包处理的结果直接用于决策时,仅对于加权汉明损失是一致的。其次,当用于构造训练集时,它产生的地面真值分布始终是可分离的(即一维分布的乘积)。第三,生成的工人错误生成模型无法对标记错误中的相关性进行建模,因为每个诱发的二进制子问题都将所有错误视为等效。特别是,如果一个工人持续混淆两个不同的标签,那么这种减少就无法利用(因为在诱发的子问题中,``信息错误''与所有其他负面响应混合在一起)。

在标签集$ L $上使用CSML的另一种方法是在标签功率集$ \ mathcal {P}(L)$上减少为CSMC。由于功率集基数的组合爆炸,这是每个人都知道并且没人喜欢的减少之一,但是它确实在成本上捕获了更高阶的结构。它与任何损失函数都是一致的,但通常会遇到样本复杂性问题,而用于减轻样本复杂性的技巧可能会导致遗憾在实践中不佳。这里的情况没有什么不同,因为当我简化为CSMC时,我将利用低秩近似 标称低秩提取 我最近介绍过,这在实践中可能会或可能不会很好地起作用。

我做了直接的事情 标称低秩提取 并通过映射多标签数据集 组合号码系统, 导致 多低位提取。因为中的参数数量 标称低秩提取 模型与标签$ | L | $的数量成正比, 多低位提取 模型与$ 2 ^ {|| L |} $之类的东西成比例。实际上,它有点小,因为我可以说如果标签集过多,则标签集的概率为零,例如,对于11个标签问题,其中某个项目的基础事实集最多具有3个标签诱导子问题中标签的数量为$ \ sum_ {k = 0} ^ 3 {11 \ choose k} = 232 $。这个技巧非常重要,因为推理仍然是$ O(| L | ^ 2)$ 标称低秩提取 因此,使诱导标签集保持较小是降低血压的关键。

我还在评估 多低位提取 比IBR好。我从0/1(整个集合)损失的角度看了一个问题,即我从这两种技术看了最可能的(后验)集合。两种方法趋于一致:在一个有853个项目的测试问题上,两种方法具有相同的后验模式718倍,而不同的是135倍。这不足为奇:当众包工作者达成强烈共识时,任何合理的模型都会将共识作为后验模式输出,因此``具有创造力''的唯一机会是众包工作者不同意。如果这种情况经常发生,则表明必须重新设计任务,因为任务要么定义不明确,模棱两可,要么极其困难。对于这两种方法不同的135个项目,我手动确定了我更喜欢哪个标签集。我更喜欢IBR 29次,我喜欢30次 多低位提取 更好,有76次我没有偏好(并且可以理解为什么众包工人不同意!)。这是一个统计死角。

鉴于IBR的计算扩展能力比 多低位提取,对于大标签集(例如$ | L | \ gg 10 $)而言,当前是明确的选择。对于小标签集,我正在使用 多低位提取 因为我喜欢它产生的更丰富的后验分布,但这仅是直觉,目前我还没有任何量化的支持。

您可以获得当前的实现 多低位提取 作为...的一部分 标称低秩提取 来自 nincompoop 代码存储库.