2010年12月29日,星期三

快如闪电的LDA

好吧,我在一家基于Twitter的初创公司有一个新的演出。提示,有一个 vowpal wabbit的新版本 可用,所以我认为我会努力。

新vowpal的热门功能之一是 在线LDA (谢谢 马特·霍夫曼!)。但是Tweets确实很小,因此很自然地要问像LDA这样的模型对于这样的简短文档是否有效。 拉米奇等等 想知道同一件事。
尽管LDA和相关模型在新闻报道和学术摘要中的应用已有很长的历史,但一个开放的问题是,它们是否适用于像Twitter帖子一样短的文档,并且其文本与传统研究的馆藏大不相同–在这里我们发现答案是肯定的。
因此,我抽取了400万条推文样本,对其进行了标记化,然后将其提供给vowpal,并提出了10个主题模型。播放时间:3分钟。除了要注意的是,一条推文平均以11个令牌(即不多)结尾,我将为您省去令牌化的详细信息。

尽管10个主题实在太小了,除了笔触广泛(我只是在热身)之外,什么都没有,但是结果很有趣,所以我想我应该把它粘贴在这里。这是每个主题的前十个标记,每行1个主题。
arenas  carter  villain guiding hoooo   ipods   amir    crazzy   confessions     snort   #awesome
de      la      a       y       que     el      en      no      me     mi      es
the     to      a       my      is      and     in      for     of     you     on
na      ka      sa      ko      ng      mo      ba      ang     ni     pa      wa
di      yg      ga      ada     aja     ya      ini     ke      mau    gw      dan
#fb     alpha   在 lantic        2dae    orgy    und     tales   ich    fusion  koolaid creme
ik      de      je      een     en      met     is      in      op     niet    het
maggie  paula   opposition      gems    oiii    kemal   industrial     cancun  ireng   unplug  controllers
9700    t0      bdae    concentration   0ut     day'    armpit  kb     2007    0f      s0
yu      ma      ii      lmaoo   lml     youu    juss    mee     uu     yeaa    ohh
除了成为一个体面的语言检测器之外,该模型还确定了Twitter用户认为很棒的内容(在竞技场中吸食,用ipod欺骗平民)以及人们选择同时选择性地发到Facebook的鸣叫(发牢骚,奶油和koolaid)。

按比例放大,在3500万条推文上运行的100个主题模型在我的笔记本电脑上花费了3小时15分钟。 拉米奇等等 报告称在96个工作日内对800万条推文进行了大约800个主题的LDA模型培训(24台机器为4天)。这不是一个苹果一个苹果,但我认为vowpal中的在线LDA实施要快2到3个数量级。

2010年12月21日,星期二

adPredictor:各种想法

我正在读 adPredictor论文 因为我最近在NIPS上看到了一个演讲。它是我所谓的``贝叶斯在线学习''系统家族的一部分,该系统(以贝叶斯学说)保持模型参数的后验分布,而不是点估计。粗略地说,这样做的好处是,某些特定模型参数对更新的敏感性低于非常不确定的模型参数。实际上,这意味着频繁出现的特征对模型更新的敏感性降低。什么时候 信心加权学习 第一次出现时,这很重要,尤其是轶事证据表明,即使使用Zipf分布的名义特征(例如单词指示符变量)也只需要传递一次训练数据即可。从那时起,非贝叶斯方法 每个参数的学习率 已经出现了 vowpal兔子的版本5 通过--adaptive标志实现此功能。根据eHarmony的经验,仅通过使用vowpal的第5版和--adaptive标志对相同的数据进行重新训练,我们看到了多个预测变量的立即改进。

但是,还有另一个方面,与系统部署的上下文强盗性质有关。引用adPredictor论文
第二个问题是勘探与开发之间的权衡。为了能够估算新广告的点击率,有必要向用户展示广告并观察他们的点击/非点击响应。同时,根据已知的情况向用户展示高点击率广告符合每个参与者的利益。探索问题可以通过利用adPredictor保持权重不确定以及任何特定广告印象的CTR保持不确定的事实来解决。当使用(2)评估预测时,系统可以从后验权重分布中采样,而不必总是将预期的点击率提供给广告拍卖,这一思想可以追溯到汤普森(Thompson,1933)。这样做的效果是使广告的点击率上升,系统的不确定性仍然很高。
这不能完全解释正在做的事情,但是也许期望具有如此商业重要性的系统的精确细节有些不切实际。他们正在做什么的一种解释是,他们从模型的后验分布中获取一个样本,然后像对待实际模型一样对待它们,使用该样本模型对所有备选方案进行评分,然后对这些评分进行贪婪的行动。我不确定该策略是否有理论上的保证,或者它是否具有启发性。凭直觉,它应该在估计值与估计值的不确定性相比具有较小估计值差异的替代方案之间分配勘探。

当我考虑必须从一堆历史数据中学习针对背景强盗问题的策略时,我希望历史探索策略的显式状态-动作密度$ \ pi(a | x)$是可用的,因此我可以重视权衡数据。如果没有的话 你可以估计一下,但如果我是从头开始设计系统,则将尝试使其显式计算$ \ pi(a | x)$并将结果记录在历史记录中。因此,有没有一种方法可以利用后验来指导勘探,同时拥有明确的$ \ pi(a | x)$?

看似简单的想法不会导致显式的$ \ pi(a | x)$。例如,考虑到每个臂$ k $用已知的累积分布函数$ F_k(\ cdot)$独立分布,并采取联合独立实现的最大值似乎是合理的,但会导致表达式[[
P(Y_i = \ max_ {k \ in K} Y_k)= \ prod_ {k \ neq i} P(Y_k<Y_i)= \ int d F_i(y)\ prod_ {k \ neq i} F_k(y)。
\]通常很难解析。如果我对adPredictor系统的工作方式是正确的,那么情况就更加复杂了,因为这些支路不是独立分布的(模型参数是采样的,并且不同的支路具有不同的重叠模型参数集,这些参数有助于它们的估算) )。

所以我怀疑adPredictor家伙在``估计历史国家行为''密度区域中。没关系,广告投放由于业务规则和外部波动而变得非常复杂,以至于``精确的''$ \ pi(a | x)$实际上可能不如估计的准确。但这仍然表明要么需要在线估计$ \ pi(a | x)$,要么需要离线进行学习。鉴于探索是通过对模型后验进行采样来进行的,因此后者似乎很危险(您将需要更新模型后验,以避免过度探索)。

关于adPredictor的另一个有趣之处:它是分类器,而不是重要性加权分类器。当然,后者可以简化为前者 成本核算,但是重要性权重为$ 1 / pi(a | x)$,这可能会变得很大,导致拒绝采样会丢弃大部分训练数据。为了避免丢弃过多的数据,可能需要$ 1 / \ max \ {\ pi(a | x),\ tau \} $裁剪技巧。但是,根据我的直觉,如果您知道$ \ pi(a | x)$,而不是进行估计,则您确实不想削减重要性权重;最好有一个重要度加权分类器,该分类器可以处理广泛的重要度动态范围。并非巧合的是,vowpal wabbit的版本5能够以封闭形式模拟具有重要重要性的单个实例与具有重要重要性的多个实例之间的等效性。 adPredictor更新可能有类似的技巧。

通过随着时间的推移衰减似然项来处理非平稳性的adPredictor策略似乎比较干净。像CW一样,在线贝叶斯Probit的属性是,随着每次观察,(均值)估计方差总是在减小,因此它最终会停顿下来(就像在vowpal中实施的Adagrad一样)。这在固定环境中是适当的,但在非固定环境中,常见的破解方法是在移动的最近数据窗口上进行训练,并且adPredictor可能性衰减在本质上是相似的。看到用于稀疏高维上下文的在线贝叶斯分类器很酷,该分类器试图检测非平稳性并实际上允许估计的方差以数据相关的方式增加(例如,受困惑驱动)。也许一旦展示出窍门,非贝叶斯主义者便会证明使用后代完全相同的更新来最大程度地减少后悔的结果:)开个玩笑。

2010年12月16日,星期四

进一步抽样零奖励示例

关于对零奖励示例进行二次抽样,我遇到了一些很好的问题,我认为他们的回答将成为一篇不错的博客文章。

为什么这样做?

我知道我毕竟在逆势而上,``没有像其他数据一样的数据。''如果您可以轻松地处理所有数据,则请务必使用所有数据。 NIPS研讨会 在核心,集群和云上学习 都是关于扩大机器学习的。仍然在实践中,我认为即使有这样的并行性,在许多情况下也无法处理所有数据,在这种情况下,如果您知道数据非常不均衡,则有偏的子采样比统一的子采样要好。以下是一些方案:
  1. 在移动应用程序中,可能必须在本地处理数据(使用宝贵的功率)或传输数据进行集中处理(使用宝贵的带宽)之间进行选择。二次采样可以使任一选择的成本降低。
  2. 在在线学习应用程序(不是应用于离线数据集的在线学习算法,而是实际在线应用)中,当输入数据流超过学习者的吞吐量时,需要一种流量控制策略。
    1. 在具有反馈循环(例如广告)的在线学习中,我对未来最复杂的系统将如何控制回报流的猜测是主动学习。但是,有偏差的二次采样现在很容易实现:)
  3. 在进行实验时,即使可以忍受最终产品的学习延迟,人机学习专家也不希望在尝试时有很多学习延迟。在固定示例预算的情况下,有偏次抽样优于均匀抽样在保持经验风险与实际风险之间的严格界限上更好(也许:请参见下文)。我在研究生院的导师告诉我,HMM总是在语音识别中发挥神经网络的作用,这不是因为HMM本质上更好,而是因为它们可以更快地被训练,所以在实践中人们可以尝试更多的事情。 (糟糕,现在我听起来很古老)。
二次采样增益往往与并行化增益结合在一起,即,如果并行化得到两个数量级,二次采样得到两个数量级,那么一起得到四个数量级。

它行得通吗?

我有一些经验轶事。

在eHarmony,我们完成了以下实验序列,事后看来是合理而科学的。实际发生的情况是,这里的每个阶段都代表了模型构建的另一个实例,并且由于不耐烦的人们,我们一直想知道如何比上次更快地做事。但是,我们害怕搞砸了(代码甚至超过了数学),因此我们在每个阶段都对控件进行了仔细检查。
  • [阶段0]:我们如何开始:分类任务(实际上是对二进制变量的密度估计)。
    • 用于训练,校准和验证的非子采样数据。
  • [阶段1]:婴儿要解决分类问题。
    • 用于训练的二次抽样数据与用于训练的非二次抽样数据。
    • 非二次采样数据,用于校准和验证。
    • 指出,对样本外数据进行训练不会影响样本外的概括(验证)(从统计意义上来说)。
  • [阶段2]:赢得对分类问题的信心。
    • 二次采样数据进行训练。
    • 用于校准的二次采样数据与用于校准的非二次采样数据。
    • 非子采样数据进行验证。
    • 指出,对样本外数据进行训练不会影响样本外的概括(验证)(从统计意义上来说)。
  • [阶段3]:希望尽快解决分类问题。
    • 用于训练和校准的二次采样数据。
    • 用于验证的二次抽样数据与用于验证的非二次抽样数据。
    • 注意,两种验证技术都可以得出统计上相同的泛化误差估计。
  • [阶段4]:希望尽快解决回归问题。
    • 次要重新考虑了所有子样本机制,以便将其应用于回归,而不仅仅是分类。
    • 感到我们的厌倦之处:只需尝试像分类一样在任何地方进行子采样数据。
    • 喜欢结果,宣布胜利。
最终结果是,如今,我们在模型构建的所有阶段都专门处理子采样数据。

不幸的是,我从未尝试过的一件事是将统一采样与有偏向子采样进行比较,即确定示例总数。以上所有实验均未将二次采样与偏向二次采样进行比较,即保留了正向奖励示例的数量,并尝试使用了较少的零奖励示例。此外,上述所有实验都提出了一个问题``子采样的结果是否同样好''。相比之下,将统一采样数与有偏子采样与固定数量的总样本进行比较可能会问到``子采样的结果更好吗? ''

它应该工作吗?

通常,我考虑使用固定的示例预算,然后优化经验风险与实际风险之间的偏差范围。

我在一个 以前的帖子 对于AUC损失,对于给定的示例预算,当数据集的正负数相等时,经验AUC与实际AUC的偏差范围将最小化。因此,对AUC丢失问题进行二次采样是非常合理的。

对于更一般的损失,例如对应于回归或分类 以前的帖子 我讨论了 科尔特斯(Cortes)等。等 专门用于对高度偏差的集合进行二次采样的情况,\ [
R(h)\ leq \ widehat R_w(h)+ \ frac {2(\ log | H | + \ log \ frac {1} {\ delta})} {3 m} \ frac {p_0} {\ beta} + \ sqrt {\ frac {2(\ log | H | + \ log \ frac {1} {\ delta})} {m} \ left(1-\ frac {(\ beta-p_0)^ 2} {\ beta(1-\ beta)} \ right)}。
\]这里$ p_0 $是原始分布中零奖励示例的分数,$ \ beta $是二次抽样分布中零奖励示例的分数。相对于$ \ beta $(对于较小的$ m $和$ p_0 \至1 $),最小化此约束会产生\ [
\ beta ^ * = \ frac {4 \ Psi} {8 \ Psi-9 m} + O(p_0-1),
\]其中\ [
\ Psi = 2 \ left(\ log | H | + \ log \ frac {1} {\ delta} \ right)。
\]因此,对于$ m \ ll \ Psi $,建议以大致相等的比例进行二次采样是最佳选择。但是$ m \ ll \ Psi $是无趣的,因为它暗示边界是松散的。对于大$ m $,通过\ [
\ beta ^ * = p_0 + O \ left(\ frac {1} {\ sqrt {m}} \ right),
\]建议不要进行二次采样(或统一二次采样)。嘿,那不是我想要的结果...我需要一个更好的界限:)

也许正确的答案是一个时间表,在该时间表中,首先对零奖励示例进行积极的子采样,然后随着示例采样中的流变得不那么积极,直到最终使用原始分布(并且在整个过程中,重要性加权与重要性一起使用-二次抽样的权重趋于统一)。

总体而言,当前对回归或分类问题进行二次抽样的理论案例比对二次抽样AUC损失问题的理论案例更具吸引力。我能说什么我一直都这样做,并且对结果感到满意。 YMMV。

猜猜食谱有多敏感?

在里面 以前的帖子 我基于对真实零奖励概率$ \ hat p_0 $的猜测给出了一个简单的方法。此猜测确定零奖励二次采样率$ l =(1-\ hat p_0)/ \ hat p_0 $,以及重要性权重$ w(x,0)= 2 \ hat p_0 $和$ w(x, y \ neq 0)= 2(1-\ hat p_0)$。猜测会有些偏离,但是,这些值仍然有效吗?

由于采样因子($ l $)是一个自由参数,因此无法使其``错误'',但是重要性权重取决于$ p_0 $和$ l $,因此可能不正确。如果真正的零奖励概率是$ p_0 $,则\ [
\ begin {aligned}
w(x,0)&= 2 \ hat p_0 + \ frac {1-2 -hat p_0} {1-\ hat p_0}(p_0-\ hat p_0),\\
w(x,y \ neq 0)&= 2(1-\ hat p_0)+ \ frac {1-2 -hat p_0} {\ hat p_0}(p_0-\ hat p_0)。
\ end {aligned}
\]后一行表示健壮性,但前一行是一个问题,因为当$ \ hat p_0 \到1 $时,零奖励重要性权重对$ \ hat p_0 $和$ p_0 $之间的差异越来越敏感。本质上发生的是,如果$ p_0 = 1 $,则正确的重要性权重为1,但是在该无意义的限制中,每个零奖励示例都被拒绝,并且没有观察到数据。从那个极端退后,因为$ p_0 \ 1 $低估了真实的零回报率,将导致超过1/2的子采样示例为零回报,这意味着$ w(x,0)$太大,并略微高估了真实的零奖励率将导致少于1/2的二次抽样示例为零奖励,这意味着$ w(x,0)$太小。

但是,通过正确的$ w(x,0)$下界为1而估计值上界为2的事实,可以缓解整个情况。因此,当使用SGD优化方法时,这等效于调整学习速率最多2倍(因为比率$ w(x,y \ neq 0)/ w(x,0)= l $是正确的)。这与使用(不正确!)权重$ \ tilde w(x,0)= l ^ {-1} $,$ \ tilde w(x,1)= 1 $形成鲜明对比,当与SGD耦合时,权重等于缩放学习率的差异因素。

因此总的来说,当使用SGD作为优化策略时,我对使用配方加速在线学习感到非常满意。另一方面,如果将非基于SGD的在线算法应用于离线数据堆,则最好将配方权重作为未归一化的权重开始,然后对权重进行归一化,如 科尔特斯(Cortes)等。等 第6节。如果在线使用基于非SGD的在线算法,我不确定该怎么做,但是也许可以使用类似于权重归一化的在线方案,例如,对最近(未采样)历史进行归一化。

知情子采样又如何呢?

在食谱中,我谈到了完全基于忽略上下文($ x $)的奖励($ y $)进行子采样。还要看$ x $呢?我认为这是个好主意,尤其是在输入空间存在明显的分割而大大影响奖励分配的情况下。在eHarmony,我们按客户类型(新用户,付费客户,以前的付费客户等)进行细分。这些客户类型很少,每个客户在历史数据中都有很多支持,并且对于我们想要建模的所有事物,它们的基准费率都非常不同。因此,在这种情况下,我们会根据客户类型来猜测$ \ hat p_0(x)$,其重要性权重和采样率由每个常量$ \ hat p_0(x)$区域中的配方值给出。完成此操作后,我最终会为每种客户类型构建完全不同的模型,但这是因为我使用的是vowpal wabbit,并且希望隐式地与其他类型交互客户类型。我认为即使将数据全部馈给一个学习者,这种方法也应该仍然有效,但是我从未尝试过完全公开。

在知道$ p_0(x)= E_P [1_ {y = 1} | x] $,二次采样将产生学习分布$ Q $,使得在每个点上零和非零奖励标签均等价。的 科尔特斯(Cortes)等。等 bound并不表示这是有利的($ d_2(P || Q)$项可能会增加,而另一个项不会得到改善)。但是,这也没有表明仅基于$ y $的有偏子采样还是有利的,除了较小的$ m $。因此,我再次凭经验看到了这项工作,但是对于YMMV,我没有很好的理论解释。

2010年12月10日,星期五

更多关于零的不重要

在一个 以前的帖子 我谈到了在高度偏倚的分布中对零奖励示例进行二次采样如何使学习成本降低(以实际美元计算或时下使用云计算进行演讲)。在政策估计和回归的情况下,重要性加权对于``统计上消除''有偏抽样的影响很重要。通常,我只是谈论重要性加权是如何无偏的,但是我也谈到了比率估算器,并说
该比率的期望值不是期望值的比率,因此后一个估计量可能有偏差,但希望并非如此(我应该对此有更好的理解)。
好在NIPS 2010 科尔特斯(Cortes)等。等 我已经对重要性加权进行了分析,其中除其他外,上述引证使我们得以了解,因此我认为我将把他们的分析专门用于对零奖励进行二次抽样的情况。

如果您只关心结果 食谱 对于具有零奖励子采样的在线回归,请跳到最后。

设置

我将处理在$ X \ times Y $上的分布$ P $和通过以下方式定义的零奖励二次抽样分布$ Q $的特殊情况
  1. 从$ P $绘制$(x,y)$;
  2. 如果$ y = 0 $,则以概率$(1-1)$拒绝;
  3. 输出实例$ \ left(x,y \ right)$,
一个激励性的示例是在线回归,当大多数示例的值为零时,在这种情况下,拒绝过程会增加在线估计量的吞吐量。我对正数很少见的情况特别感兴趣,即$ E_P [1_ {y = 0}] \到1 $,而``积极的''二次抽样旨在平衡数据集。如果目标是实现$ E_Q [1_ {y = 0}] = \ beta \ leq E_P [1_ {y = 0}] $,则\ [l = \ frac {\ beta} {1-\ beta} \ frac {(1-E_P [1_ {y = 0}])} {E_P [1_ {y = 0}]}。 \]典型的$ \ beta $是$ 1/2 $,即为实现完美平衡而进行的二次采样。
重量功能
权重函数定义为$ w(\ cdot)= P(\ cdot)/ Q(\ cdot)$,指示如何将对$ P $的期望转换为对$ Q $的期望,该期望是绝对连续的与$ P $。对于二次采样,权重函数由\ [\ begin {aligned}
w(x,y)&= \ frac {l ^ {-1} 1_ {y = 0} + 1_ {y \ neq 0}} {E _ {(x,y)\ sim Q} [l ^ {-1 } 1_ {y = 0} + 1_ {y \ neq 0}]} \\
&= \ frac {1 +(l ^ {-1}-1)1​​_ {y = 0}} {E _ {(x,y)\ sim Q} [1 +(l ^ {-1}-1)1​​_ {y = 0}]} \\
&= \ frac {1 +(l ^ {-1}-1)1​​_ {y = 0}} {1 +(l ^ {-1}-1)q_0} \\
&= \ left(1 +(l ^ {-1}-1)1​​_ {y = 0} \ right)\ left(1 +(l-1)p_0 \ right),
\ end {aligned}
\]其中$ p_0 = E_P [1_ {y = 0}] $和$ q_0 = E_Q [1 _ {y = 0}] = l p_0 /(l p_0 +1-p_0)$。注意,我实际上并不知道$ w $,因为我不知道先例出现零奖励示例的频率。但是,我可以说以下,\ [
\ underset {x,y} {\ operatorname {sup \;}}} w(x,y)= w(x,0)= l ^ {-1} +(1-l ^ {-1})p_0,
\]和我感兴趣的领域\ [
\ underset {x,y} {\ operatorname {sup \;}}} w(x,y)\ biggr | _ {l = \ frac {\ beta(1-p_0)} {(1-\ beta)p_0}} = \ frac {p_0} {\ beta} \ underset {p_0 \ to 1} {\ longrightarrow} \ frac {1} {\ beta}。
\]因此,即使在二次采样非常激进的情况下,重要性权数实际上还是有界的,因为正数非常罕见。如果这与我以前的帖子似乎矛盾,那是因为在我之前的帖子中,我没有考虑分母项$ E _ {(x,y)\ sim Q} [l ^ {-1} 1_ {y = 0} + 1_ { y \ neq 0}] $;有关此的更多信息。
Rènyi Divergences
此数量描述了分布$ Q $和绝对连续有$ Q $的分布$ P $之间的差,\ [D _ {\ alpha}(P || Q)= \ frac {1} {\ alpha-1} \ log_2 E _ {(x,y)\ sim P} \ left [\ left(\ frac {P(x,y)} {Q(x,y)} \ right)^ {\ alpha-1} \ right], \],并另外定义$ d _ {\ alpha}(P || Q)= 2 ^ {D _ {\ alpha}(P || Q)} $。对于二次采样,由\ [\ begin {aligned}
D _ {\ alpha}(P || Q)&= \ frac {1} {\ alpha-1} \ log_2 \ frac {E _ {(x,y)\ sim P} \ left [\ left(l ^ {- 1} 1_ {y = 0} + 1_ {y \ neq 0} \ right)^ {\ alpha-1} \ right]} {\ left(E _ {(x,y)\ sim Q} \ left [l ^ {-1} 1_ {y = 0} + 1_ {y \ neq 0} \ right] \ right)^ {\ alpha-1}} \\
&= \ frac {1} {\ alpha-1} \ log_2 \ frac {E _ {(x,y)\ sim P} \ left [l ^ {1-\ alpha} 1_ {y = 0} + 1_ {y \ neq 0} \ right]} {\ left(E _ {(x,y)\ sim Q} \ left [l ^ {-1} 1_ {y = 0} + 1_ {y \ neq 0} \ right] \右)^ {\ alpha-1}} \\
&= \ frac {1} {\ alpha-1} \ log_2 \ frac {E _ {(x,y)\ sim P} \ left [1 +(l ^ {1-\ alpha}-1)1​​_ {y = 0} \ right]} {\ left(E _ {(x,y)\ sim Q} \ left [1 +(l ^ {-1}-1)1​​_ {y = 0} \ right] \ right)^ { \ alpha-1}} \\
&= \ frac {1} {\ alpha-1} \ log_2 \ frac {1 +(l ^ {1-\ alpha}-1)p_0} {\ left(1 +(l ^ {-1}-1) q_0 \ right)^ {\ alpha-1}}。 \\
\ end {aligned}
\]
在引理1科尔特斯等。等节目 \[
\ begin {aligned}
E _ {(x,y)\ sim Q} [w(x,y)]&= 1,\\
E _ {(x,y)\ sim Q} [w ^ 2(x,y)]&= d_2(P || Q)\\
&= \ frac {l +(1-1)p_0} {l +(1-1)q_0} \\
&= \ frac {\ left(l(1-p_0)-p_0 \ right)(1-(1-l)p_0)} {l},
\ end {aligned}
\]和我感兴趣的领域\ [
E _ {(x,y)\ sim Q} [w ^ 2(x,y)] \ biggr | _ {l = \ frac {\ beta(1-p_0)} {(1-\ beta)p_0}} = 1 + \ frac {(\ beta-p_0)^ 2} {\ beta(1-\ beta)} \ underset {p_0 \ to 1} {\ longrightarrow} \ frac {1} {\ beta}。
\]

学习保证

所以科尔特斯等。等描述假设$ h $(相对于$ P $)的真实风险之间的一些关系\ [R(h)= E _ {(x,y)\ sim P} [L(h(x),y​​)] \]和经验重要性加权风险(对于从$ Q ^ m $抽取的有限样本而言)\ [\ widehat R_w(h)= \ frac {1} {m} \ sum_ {i = 1} ^ mw( x_i,y_i)L(h(x_i),y)。 \]这里的情况略有不同,因为我的重要性权重取决于$ y $,而在本文中则不然。我应该验证这不会破坏他们的定理。

他们的定理2给出了有限假设集\ [
R(h)\ leq \ widehat R_w(h)+ \ frac {2 M(\ log | H | + \ log \ frac {1} {\ delta})} {3 m} + \ sqrt {\ frac {2 d_2(P || Q)(\ log | H | + \ log \ frac {1} {\ delta})} {m}},
\]其中$ M $是$ \ sup_ {x,y} w(x,y)$。使用$ l = \ frac {\ beta(1-p_0)} {(1-beta)p_0} $对我的情况进行专门处理,得出\ [
R(h)\ leq \ widehat R_w(h)+ \ frac {2(\ log | H | + \ log \ frac {1} {\ delta})} {3 m} \ frac {p_0} {\ beta} + \ sqrt {\ frac {2(\ log | H | + \ log \ frac {1} {\ delta})} {m} \ left(1-\ frac {(\ beta-p_0)^ 2} {\ beta(1-\ beta)} \ right)}。
\]如果$ \ beta $变得非常小,则此界限会变坏,但是这里的典型$ \ beta $是$ 1/2 $,因此一切看起来都合理,这会导致问题$ \ ldots $

为什么过去有麻烦?

权重函数的上界是有界的,因此Cortes等。等建议我应该在学习上没有问题;但实际上在进行在线二次抽样时,我的重要性加权了回归,因为如果我过于积极地进行二次抽样,就会变得不稳定。如何解决这个矛盾?简单: 我做错了。这是我过去所做的事情:决定使用参数$ l $对零奖励进行二次采样,然后使用\ [给定的重要性加权$ \ tilde w $
\ begin {aligned}
\ tilde w(x,0)&= l ^ {-1}&\ mbox {(invalid!)},\\
\ tilde w(x,y \ neq 0)&= 1&\ mbox {(不正确!)}。
\ end {aligned}
\]我(有缺陷的)推理是,由于二次采样,每个观察到的零奖励示例都像$ l ^ {-1} $个实际的零奖励示例。不幸的是,当二次采样率变为0时,这些权重的上限不受限制。实际权重函数的上限受$ 1 /β限制。由于我正确设置了两个重要权重的比率,因此好像在提高学习速度,这导致失败。

对于我的情况,适当的选择由\ [
\ begin {aligned}
w(x,0)&= \ frac {p_0} {\ beta},\\
w(x,1)&= \ frac {l p_0} {\ beta} = \ frac {1-p_0} {1-\ beta},
\ end {aligned}
\],特别是对于$ \ beta = 1/2 $,$ w(x,0)= 2 p_0 $和$ w(x,1)= 2(1-p_0)$。实际上,我不知道$ p_0 $,但我通常有一个不错的猜测(例如,平均点击率约为0.5%,因此$ p_0 \ approx 0.995 $),我也可以使用它来设置$ l = \ beta( 1-p_0)/((1-beta)p_0)$。

为什么我过去没有麻烦

过去,我曾在没有重要性加权的情况下对回归采样器进行二次采样数据的训练,然后使用校准阶段来校正二次采样的影响,从而获得了很好的经验。即使在非常激进的子采样级别上,该方法也非常有效。以上考虑是否可以说明这一点?

答案是肯定的。关键见解是,在离线校准期间,我有效地计算了\ [
\ widehat w(x_i,y_i)= \ frac {\ tilde w(x_i,y_i)} {\ sum_i \ tilde w(x_i,y_i)}
\]并将这些权重用作重要权重。科尔特斯(Cortes)等。等称这些$ \ widehat w $为``标准​​化重要性权重''。他们表明归一化权重很有可能接近真实权重\ [
\ left | \ widehat w(x_i,y_i)-\ frac {w(x_i,y_i)} {m} \ right | \ leq 2 ^ {5/4} \ max \ {d_2(P || Q),d_2(P || \ widehat Q)\} \ sqrt [\ frac {3} {8}] {\ frac {\ log 2我+ \ log \ frac {4} {\ delta}} {m}}。
\]这说明了为什么基于校准的程序对主动子采样的鲁棒性要强得多。这也是我对上一篇文章中自我提出的问题的答案,即通过用期望值的比率替换比率的期望值会引入多少偏差。

最后,它表明,在线过程可以保持对归一化常数的在线估计,以便消除猜测真正的零奖励概率(例如,指数加权移动平均值)的需要。

一个食谱

这是处理零收益示例极为普遍的在线回归或分类问题的处方。它减少了学习算法必须考虑的数据量,从而提高了计算吞吐量。
食谱:零回报二次抽样的在线回归或分类
  1. 猜猜真正的零奖励概率是多少,称为$ \ hat p_0 \ geq 1/2 $。
  2. 定义$ l =(1-\ hat p_0)/ \ hat p_0 $。
  3. 显然拒绝概率为$(1-1)$的零奖励示例。
  4. 接受所有非零奖励示例。
  5. 重要性权重零奖励示例为$ 2 \ hat p_0 $。
  6. 重要性权重非零奖励示例为$ 2(1-\ hat p_0)$。

2010年12月5日,星期日

成本敏感的最佳M的SFF树

约翰·兰福德 最近向我发送了一个有用的建议。
另一种方法是引入代表性的hack。假设我们将成对分类器定义为:$ w_ {left} x_ {left}-w_ {right} x_ {right} $。然后,过滤树的输出为$ \ underset {a} {\ operatorname {arg \,max \,}} w_a x_a $,其形式与回归相同。但是,我们以不同的方式训练事物,以实现较低的后悔$ \ ldots $
与该建议相关的探索方向很多。这是我的一些曲折。

SFF树:定义

我将此建议称为计分没收过滤器(SFF)树。类比是当使用评分功能定义线性排序以减少对分类的排名时。这是一个更精确的定义。
定义:SFF树
SFF树是 没收过滤树 $\Psi$ where 在 each internal node $\nu$ the importance-weighted classifier is of the form \[ \Psi_\nu (x) = 1_{f (x; \lambda) > f (x; \phi)}
\]其中$ \ lambda $和$ \ phi $是输入到$ \ nu $的两个类(分别是左和右子树的预测)。函数$ f $称为计分函数,并且在每个内部节点处都相同(但对于每个操作而言都不同)。

John的建议的妙处在于,可以在测试时通过$ h ^ \ Psi(x,\ omega)= \ underset {k \ in K \ setminus \ omega} {\ operatorname {arg \,max \,}} f(x; k)$看起来就像如何计算输出以进行回归归约。但是后悔的界限更好,因为训练的过程是不同的。

SFF树 平均约束CSMC

由于SFF树是没用的过滤树,因此 后悔 上的“没收过滤器”树 平均约束CSMC 问题成立,即\ [r_ {av}(h ^ \ Psi)\ leq(| K |-1)q(\ Psi),\]其中$ q(\ Psi)$是重要性加权二元遗憾引起的子问题。这与 回归遗憾,\ [r_ {av}(h_g)\ leq \ sqrt {2 | K | \ epsilon_ {L ^ 2}(g)},\]其中$ \ epsilon_ {L ^ 2}(g)$是基础回归问题的损失$ L ^ 2 $。

因此,一开始这似乎很神奇(即,可以将其视为获得更好的回归指标的一种方法),但是我将其理解为训练过程,将子问题预言集中在重要的问题上(例如,区分best和$ 2 ^ \ mathrm { nd} $每个实例的最佳操作),而忽略不存在的问题(例如,准确估计$(n-1)^ \ mathrm {th} $和$ n ^ \ mathrm {th} $最差的选择的值)。

在实践中,强制SFF树中的分类器基于评分函数可能会导致难以学习对诱导子问题的低遗憾解决方案。评分函数在所有内部节点上共享的事实是简化输出计算的关键,但与普通的没收树不同。在原始情况下,很容易设想通过$ \ log_2(| K |)$顺序遍历以从下到上的方式训练树,每次遍历定义内部节点的下一级别的训练数据,并且每次遍历在特定深度训练一组内部节点。但是,现在不同级别的分类器是交织在一起的。

我实际上不确定如何处理这个问题,并且直到尝试尝试时我才知道。凭直觉,如果我要在线上逐步更新热模型,我会尝试忽略依赖关系,而仅应用更新。动机是我每次更新都会进行微小的更改,所以我忽略的是``高阶微小''。当然,决策边界处的大量非线性有点令人不安(并且不是很小)。从冷开始但仍使用在线学习算法(针对脱机数据),我尝试从下到上的方式通过$ \ log_2(| K |)$,在一定深度前热启动整个树在下一个更高的深度训练任何内部节点。与普通情况不同,每次通过都会训练所有内部节点达到一定深度,而不仅仅是训练特定深度的内部节点。希望能奏效,但如果失败了,我会考虑使用softmax风格的方法来减轻决策边界的非线性,例如$ p(\ Psi_ \ nu = 1 | x)= 1 /(1 + e ^ {-\ beta(f(x; \ lambda)-f(x; \ psi))})$并将$ \ beta $退火为$ \ infty $。

SFF树 平均约束CSBM

平均约束CSBM 是在给定实例的情况下选择前$ m $个操作的问题。通过构造分类器列表$ \ {\ Psi_n | |,可以将其减少到受约束的平均CSMC。 n \ in [1,m] \} $每个都经过训练,以选择最佳动作,下一个最佳动作等。

所以这是一个有趣的事情:如果我们在分类器列表中设置$ \ Psi_n = \ Psi $,并且如果我们的平均约束CSMC分类器是SFF树,那么我们可以通过\ [h ^ \ Psi(x, \ omega)= \ underset {k \ in K \ setminus \ omega} {\ operatorname {arg \,max \,^ m}} f(x; k),\]在这里我用符号$ \ operatorname {arg \,max \,^ m} $代表选择前$ m $个元素。同样,这正是在测试时将采用基于回归约简的方法的方式。但是遗憾的界限还是不同的。当将平均约束CSBM减小为平均约束CSMC时, 后悔 是\ [r_ {csbm}(h ^ \ Psi)\ leq m \,q(\ Psi,m),\]其中$ q(\ Psi,m)$是对$ m $的平均成本敏感后悔平均约束CSMC子问题(这些问题又可以简化为重要性加权分类,从而保持对后悔的线性依赖)。相反,当简化为回归 后悔 是\ [r_ {csbm}(h_g)\ leq \ sqrt {2 \ min \ {m,| K | -m \}} \ sqrt {| K |} \ sqrt {\ epsilon_ {L ^ 2}(g)},\]其中$ \ epsilon_ {L ^ 2}(g)$是$ L ^ 2 $的损失关于潜在的回归问题。

因此,我们再次保证可以采用不同的训练程序来获得更好的回归值,但是子问题之间的依存关系也存在类似的问题,使训练画面复杂化。在将CSBM简化为CSMC的典型情况下,每个分类器将按顺序进行训练,并为下一个分类器定义训练输入分布。现在所有分类器都相同,因此需要一些技巧。

再说一次,我实际上不确定如何处理这个问题,直到尝试了一些事情,我才知道。凭直觉,我将再次尝试在线上逐步更新热模型,而忽略依赖关系。对于将离线模型应用于在线模型的冷启动,我将首先针对top-1问题,然后针对top-2问题进行培训,直到达到top- $ m $。有趣的是,如何看待我的两个直观过程的组成如何进行完整的冷启动:
  1. 对于$ n $ in $ [1,m] $
    1. 为$ l $ in $ [\ log_2(| K |),1] $
      1. 更新$ l ^ \ mathrm {th} $和更低级别的内部节点,以解决同时选择顶部$ n $动作的问题
      2. 更新$ l ^ \ mathrm {th} + 1 $和更高级别的内部节点,以解决选择前$(n-1)$个操作的问题。
总共$ m \ log_2(| K |)$通过了数据,这很合理。外循环用于减轻由$ \ Psi_n = \ Psi $创建的依赖关系,而内循环用于减轻在所有内部节点之间共享$ f $所创建的依赖关系。

现在,我想我应该在一些实际数据上尝试一下。