2011年7月13日,星期三

更多重要的更新

重要性感知更新

在重要性加权回归或分类中,每个示例损失是按比例缩放的规范损失,\ [
L (w) = E_{x \sim D} \left[ \epsilon (x) 长(x; w) \right],
\]通过随机梯度下降优化,
w_ {n + 1} = w_n-\ eta \ epsilon(x_n)\ frac {\ partial L(x_n; w)} {\ partial w} \ biggr | _ {w = w_n},
\]其中$ \ eta $是学习率。实际上,当重要性权重$ \ epsilon(x_n)$过大(相对于$ \ eta $)时,此更新变得不稳定。不稳定比说更新不会减少总损失要糟糕得多。很容易发生损失 在这个例子中 我认为这就是为什么物流损失如此流行的原因,因为它从本质上防止了这种情况,因此不会因更新而减少。但是当使用铰链损耗,平方损耗或分位数损耗时,凭经验很难遇到这种不稳定性。

的见识 Karampatziakis和Langford 将上述更新视为方程\ [的一阶Euler积分器
w ^ \ prime(h)=-\ eta \ epsilon(x_n)\ frac {\ partial L(x_n; w)} {\ partial w} \ biggr | _ {w = w(h)},
\]在这种情况下 GLM 针对实际中常用的损失函数提供了一种解析解决方案。这是因为对于GLM,损失函数采用$ L(x_n; w)= l(w ^ \ top x_n)$的形式,其梯度始终是$ x_n $的缩放版本。因此,存在一个\ [
宽(高)= w - s (h) x_n,
\]其中\ [
s ^ \ prime(h)= \ eta \ epsilon(x_n)\ frac {\ partial l} {\ partial p} \ biggr | _ {p =(w-s(h)x_n)^ \ top x_n},
\]是一维ODE,具有用于$ l $的许多常见选择(例如,铰链,平方,对数等)的分析解决方案。

尽管最初是由主动学习(它会产生很大的动态范围的重要性权重)激励,但是重要性感知更新甚至对于非重要性加权问题也很有用,因为它提供了关于学习率规范的鲁棒性。我已经沉迷于重要性感知更新在实际数据上凭经验表现出的健壮性,因此,当我遇到新情况时,我总是在寻找重要性感知更新。我对此做了一些调查 二元模型 以前,但是还有其他两种情况。在这两种情况下,由于减少,损失函数一次要在多个输入上进行评估。

通过成对分类排名

为了优化AUC,有一个 归结为成对分类 混合标签实例。在使用SGD进行训练时,这意味着将成对的示例$(x_ +,x _-)$提供给分类器,其中$ x _ + $的排名高于$ x _- $。如果所需结果是线性计分函数$ f(x; w)= w ^ \ top x $,则目标为$ 1_ {w ^ \ top(x_ +-x_-)>0} $,将其放宽到以下每个示例对的凸损失\ [
\ begin {aligned}
L(x_ +,x_-; w)&= \ epsilon(x_ +,x_-)l \ left(w ^ \ top(x_ +-x_-),1 \ right),\\
w ^ \素数(h)&= -\eta \epsilon (x_+, x_-) \frac{\partial L (x_+, x_-;w)} {\ partial w} \ biggr | _ {w = w(h)} \\
&=-\ eta \ epsilon(x_ +,x_-)\ frac {\ partial l} {\ partial p} \ biggr | _ {p = w(h)^ \ top(x_ +-x_-)}(x_ +-x_-)。
\ end {aligned}
\]再次将所有梯度指向同一方向,因此寻找形式为$ w(h)= w-s(h)(x_ +-x _-)$,[[
\ begin {aligned}
s ^ \ prime(h)&=-\ eta \ epsilon(x_ +,x_-)\ frac {\ partial l} {\ partial p} \ biggr | _ {p =(w-s(h)(x_ + -x _-))^ \ top(x_ +-x_-)}。
\ end {aligned}
\]可能不足为奇的是,重要性感知更新与分类相同,只是它是使用差异向量计算的。换一种说法,
  1. 接收具有重要权重$ \ epsilon(x_ +,x _-)$的示例对$(x_ +,x _-)$。
  2. 使用$ \ Delta x = x_ +-x _- $作为输入,$ y = 1 $作为目标,计算标准重要性更新$ s(h)$。
    • 如果您总是将目标设为1似乎很奇怪,请考虑在以后的时间出现相同的输入转置。
    • 注意$ \ Delta x $不包含常量功能。
  3. 使用$ s(h)\ Delta x $更新权重。
重要提示:此过程与依次训练带有标签1的$ x _ + $和随后带有标签0的$ x _- $的训练不同;具有平方损失的过程对应于在平衡的训练集上学习回归变量,尽管该序列一致,但与成对分类的减少相比,其后悔约束更糟。您无法使用 Vowpal兔子 作为一个黑盒子(由于具有常数功能):您必须将其打开并修改代码。 (也许对Vowpal的一个很好的补丁就是让它接受一个命令行标志来抑制常量功能)。

布法尼等等 讨论减少 DCG 和NDCG的损失函数具有与上面相同的形式(该论文中的公式6),因此对它们的损失进行重要性感知的SGD将导致类似的更新。

评分筛选树

得分 过滤树 是从成本敏感的多类别分类减少到重要性加权二元分类。以前我已经讨论过了 从概念上讲 并且还提供了 实作 通过perl脚本包装器在Vowpal Wabbit之上。 (我随后编写了一个C ++实现,速度大约快10倍)。

用于训练的(某种)松弛(但仍不是凸的)目标函数是\ [
\ begin {aligned}
长(x; w) &= \sum_{\nu \in T} \left| c_{\lambda (\nu;>c _ {\ rho(\ nu; x,w)}} \ right)。
\ end {aligned}
\]这里$ \ lambda(\ nu; x,w)$和$ \ rho(\ nu; x,w)$是节点$ \ nu $的左右输入的标识。这看起来真的很讨厌:通常,每个输入向量在树中出现多次,并且输入到节点的传播也以非凸的方式取决于$ w $(即函数$ \ lambda $和$ \ rho $不凸)。

仅考虑树的单个级别$ k $,\ [
\ begin {aligned}
L_k(x; w)&= \sum_{\nu \in T_k} \left| c_{\lambda (\nu;>c _ {\ rho(\ nu; x,w)}} \ right),
\ end {aligned}
\]在这种情况下可以取得一些进展,因为$ x $是正交的,每个$ x $最多出现一次。忽略$ \ lambda $和$ \ rho $对$ w $的依赖性,寻找形式为[[
\ begin {aligned}
宽(高)&= w - \sum_{\nu \in T_k} s_\nu (h) (x_{\lambda (\nu;x,w)}-x _ {\ rho(\ nu; x,w)}),
\ end {aligned}
\]产生\ [
s ^ \ prime_ \ nu(h)=-\ eta \ left | c _ {\ lambda(\ nu; x,w)}-c _ {\ rho(\ nu; x,w)} \ right | \ frac {\ partial l} {\ partial p} \ biggr | _ {p =(w-s_ \ nu(h)(x _ {\ lambda(\ nu; x,w)}}-x _ {\ rho(\ nu ; x,w)}))^ \ top(x _ {\ lambda(\ nu; x,w)}-x _ {\ rho(\ nu; x,w)})}}。
\]本质上是树的$ k $级每个节点的排名更新。

受上述推理的启发,使用以下每个示例过程对过滤树进行评分,获得了非常好的结果:
  1. 确定比赛的总冠军,以估计损失。
  2. 对于树的每个级别,从下到上
    1. 确定每个父节点$ \ lambda(\ nu; x,w)$和$ \ rho(\ nu; x,w)$的输入,即谁在锦标赛中晋级。
    2. 使用上面的公式,为树的此级别上的每个节点计算$ s_ \ nu(h)$,并更新模型。
    3. 可选的速度改善:如果所有剩余成本向量条目都相同(即,所有剩余可能的重要权重均为零),则短路。
    4. 重新计算$ w ^ \ top x _ {\ lambda(\ nu; x,w)} $和$ w ^ \ top x _ {\ rho(\ nu; x,w)} $的值,分别用于比赛。
此过程的动机是需要二元模型,以绝对排除过度使用标签的可能性。我发现它也给非二元问题带来了更好的损失。足以补偿步行时树的重新计算量的降低。 (这种放慢的速度甚至比听起来还糟,因为树的每个级别在并发估计线程之间引入了同步屏障。请耐心等待。)

没意见:

发表评论