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$ if $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$ and $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 = nominalembed
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 updates ... 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代码存储库.