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在没有训练数据的情况下预测上下文,我可能会得到不同的结果。

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

没意见:

发表评论