2011年5月13日,星期五

双向重要性感知更新

所以最近我谈到 二元建模,以及它看起来如何与目前在vowpal wabbit内部实现的模型非常接近。但是,由于``明显较小''的差异,会出现一些皱纹。

vowpal中的基本算法本质上是 GLM 用优化 新元 。引擎盖下的巧妙技巧之一是 重要体重感知更新。关键的观察结果是,对于GLM,特定示例的所有梯度都指向同一方向,并且仅在幅度上有所不同,即,如果预测为$ p = w ^ \ top x $,则$ \ nabla_w l(p, y)= x \ frac {\ partial l} {\ partial p} | _ {p = w ^ \ top x} $。 Karampatziakis和Langford利用此方法通过求解一个常微分方程来模拟大量小梯度步的极限。产生的更新具有三个不错的属性。第一个是安全性:对于可能超出标签的损失函数,重要性感知更新将永远不会超出标签,这与渐变的天真缩放不同。第二个是不变性:重要性加权为$ w_1 $和$ w_2 $的两个顺序更新等效于重要性加权为$ w_1 + w_2 $的单个更新。安全性使SGD的结果对准确选择学习率的敏感性降低;而不变性对于利用重要性权重的减少非常重要。什么是第三个不错的酒店?事实证明,对于各种常用损失函数都有封闭式更新,因此,重要性感知更新的计算成本较低。

二元模型不是GLM,但是某些原理仍然适用。考虑一个简单的二元模型,\ [
\ begin {aligned}
p&= a ^ \ top b,\\
\ nabla_a l(p,y)&= b \ frac {\ partial l} {\ partial p} | _ {p = a ^ \ top b},\\
\ nabla_b l(p,y)&= a \ frac {\ partial l} {\ partial p} | _ {p = a ^ \ top b}。
\ end {aligned}
\]所有的梯度都不指向相同的方向,但是尽管如此,尝试创建重要性加权感知更新仍会产生一对方程,\ [
\ begin {aligned}
a'(h)&=-\ eta b(h)\ frac {\ partial l} {\ partial p} \ biggr | _ {p = a(h)^ \ top b(h)},\\
b'(h)&=-\ eta a(h)\ frac {\ partial l} {\ partial p} \ biggr | _ {p = a(h)^ \ top b(h)}。
\ end {aligned}
\] Mathematica只能为我解决铰链丢失问题;在线性状态下,解看起来像\ [
\ begin {aligned}
a(h)&= a_0 \ cosh(\ eta h y)+ b_0 \ sinh(\ eta h y),\\
b(h)&= b_0 \ cosh(\ eta h y)+ a_0 \ sinh(\ eta h y),
\ end {aligned}
\],然后只要有人到达$ a(h)^ \ top b(h)= y $的边界,就不会再有变化。 Mathematica还可以分析得出最小的$ h_ {min} $,其中$ a(h)^ \ top b(h)= y $并且计算起来也不算太糟(涉及$ \ cosh ^ {-1} $和平方根);尽管当$ a_0 \ approx b_0 $时需要一些注意(有系列扩展可用)。

此更新具有所有三个理想的属性。产品碰到标签后立即停止,以确保安全。不变性成立,可以通过利用等式$ \ cosh(a + b)= \ cosh(a)\ cosh(b)+ \ sinh(a)\ sinh(b)$来证明线性不变性。最后,该更新的计算成本相对较低。

如果用$ p = w ^ \ top x + a ^ \ top b $代替预测,则故事基本上保持不变。方程是\ [
\ begin {aligned}
a'(h)&=-\ eta b(h)\ frac {\ partial l} {\ partial p} \ biggr | _ {p = a(h)^ \ top b(h)+(w-s( h)x)^ \ top x},\\
b'(h)&=-\ eta a(h)\ frac {\ partial l} {\ partial p} \ biggr | _ {p = a(h)^ \ top b(h)+(w-s( h)x)^ \ top x},\\
s'(h)&= \ eta \ frac {\ partial l} {\ partial p} \ biggr | _ {p = a(h)^ \ top b(h)+(w-s(h)x)^ \ top x},
\ end {aligned}
\]对于铰链丢失有解决方法\ [
\ begin {aligned}
a(h)&= a_0 \ cosh(\ eta h y)+ b_0 \ sinh(\ eta h y),\\
b(h)&= b_0 \ cosh(\ eta h y)+ a_0 \ sinh(\ eta h y),\\
s(h)&=-\ eta h y。
\ end {aligned}
\]但是$ h_ {min} $的计算更为复杂;我无法获得解析表达式,因此很遗憾,需要一维求根,\ [
\ text {求解} \ left [\ frac {1} {2} \ left(|| a_0 || ^ 2 + || b_0 || ^ 2 \ right)\ sinh(2 \ eta hy)+ a ^ \ top b \ cosh(2 \ eta hy)+ x ^ \ top(\ eta hx y + w)= y,h \ right]。
\]这可能会使更新没有资格被视为``便宜的计算''。

总的来说,我认为此更新可能与二元分类问题有关,因为铰链丢失将是一个合理的选择。从理论上讲,分位数损失也可以接受,但其他损失则不行。

当我对从不同起点开始的一维二元更新进行$ a(h)$和$ b(h)$的参数图绘制时,我得到了一张很酷的图片,我想发布。这让我想起了科幻小说之类的东西。
通过数值积分将上述方程式用于不同的损失会产生相似的图像,尽管对于某些损失(例如逻辑损失)没有边界,所以耐克不断前进。这表明铰链损耗情况捕获了更新的基本曲率,但是由于损耗的非线性,对于不同的损耗,更新的大小是不同的。这进一步暗示了像\ [
\ begin {aligned}
a(h)&= a_0 \ cosh(-s(h))+ b_0 \ sinh(-s(h)),\\
b(h)&= b_0 \ cosh(-s(h))+ a_0 \ sinh(-s(h)),\\
s'(h)&= \ eta \ frac {\ partial l} {\ partial p} \ biggr | _ {p = a(h)^ \ top b(h)+(w-s(h)x)^ \ top x}。
\ end {aligned}
\]因此,这里有一些有关此黑客的猜测。首先猜测:这是一个下降方向,因为如果损耗在$ h = 0 $处线性化,我将得到上述等式重现的铰链损耗更新。第二个猜测:此更新是不变的,因为通过替换,我可以将其简化为一阶ODE,并且cosh和sinh不会破坏损失函数的连续微分性。第三个猜测:此更新具有安全性。

当然,此更新涉及对一维ODE进行数值积分,因此在实践中可能会过于昂贵。基本上,hack将多维ODE简化为一维ODE,这在计算上是节省的,但绝对不如封闭形式那么酷。

要了解不变性为何起作用,请考虑在使用重要性权重$ h_1 $和$ h_2 $进行两次连续更新后,$ a $的值是什么,\ [
\ begin {aligned}
a(p_1,h_2)&= a(p_0,h_1)\ cosh(-s(p_1,h_2))+ b(p_0,h_1)\ sinh(-s(p_1,h_2)),\\
p_0&= a_0 ^ \ top b_0 + w ^ \ top x \\
p_1&= a(p_0,h_1)^ \ top b(p_0,h_1)+(w-s(p_0,h_1)x)^ \ top x \\
\ end {aligned}
\]明确了对初始预测$ p_0 $和中间预测$ p_1 $的依赖性。现在注意\ [
\ begin {aligned}
a(p_0,h_1)&= a_0 \ cosh(-s(p_0,h_1))+ b_0 \ sinh(-s(p_0,h_1)),\\
b(p_0,h_1)&= b_0 \ cosh(-s(p_0,h_1))+ a_0 \ sinh(-s(p_0,h_1))。 \\
\ end {aligned}
\]代入上述并使用双曲加法恒等式得出\ [
a(p_1,h_2)= a_0 \ cosh(-s(p_0,h_1)-s(p_1,h_2))+ b_0 \ sinh(-s(p_0,h_1)-s(p_1,h_2)),
\]因此,如果\ [
s(p_0,h_1 + h_2)= s(p_0,h_1)+ s(p_1,h_2),
\] 然后 \[
a(p_0,h_1 + h_2)= a(p_1,h_2),
\],同样也适用于$ b $。

没意见:

发表评论