2011年6月2日,星期四

尺寸分析和梯度下降

考虑根据损失函数$ l $,\ [
\ begin {aligned}
p ^ {(t)}&= w ^ {(t)\ top} x ^ {(t)},\\
w ^ {(t + 1)}&= w ^ {(t)}-\ eta \ frac {\ partial l} {\ partial p} x ^ {(t)}。
\ end {aligned}
\]假设最佳权重向量为$ w ^ * $。如果所有输入均按恒定量$ r $进行缩放,则最佳权重向量为$ w ^ * / r $,如果学习算法生成的输出尊重该身份,那将是很好的选择。沿着这些思路思考的更一般的方法是尺寸分析。

假设预测的维度为\ rho $,输入的维度为\ chi \。那么权重必须具有$(\ rho / \ chi)$的维数才能计算出预测方程。假设损失的大小为$ \ lambda $,这意味着学习率$ \ eta $必须具有$ \ rho ^ 2 / /(\ lambda \ chi ^ 2)$的单位才能计算出更新方程。在实践中,这意味着,如果我们有一个权重向量序列收敛到我们喜欢的某个位置,然后我们更改所有输入以使它们加倍,则学习率必须四分之一,以使生成的权重向量的整个序列将其减半,以使整个预测序列相同。

所以这些想法已经被纳入 Vowpal兔子 (实际上,这就是我意识到它们的方式:我请Vowpal团队帮助我理解我在源代码中看到的内容)。特别是在命令行上指定的$ \ eta $由$ x ^ {(t)\ top} x ^ {(t)} $规范化,对应于$ {1 / / chi ^ 2)$部分。 $ \ eta $维数;但是,这不能解决$ \ rho ^ 2 / \ lambda $部分。 (为什么这么重要?假设我创建了一个新的损失函数,该函数是另一个损失函数的输出的两倍;在命令行上指定的学习率必须降低一半。)

在处理二元模型时,我不得不弄清楚如何对此进行概括,因此我开始考虑它。通过$ x ^ {(t)\ top} x ^ {(t)} $进行归一化肯定会针对输入的全局缩放进行调整,但是如果仅对输入的一个维度进行缩放会怎样?这开始进入以下领域 预处理 这导致了自适应方法 杜契,哈桑和歌手 又名DHS(也同时在 麦克马汉和史特勒 但我将专注于DHS)。在那里他们定义了一个矩阵$ G ^ {{(t)} = \ mathrm {diag} \ left(1 / \ sqrt {\ sum_ {s \ leq t}(g ^ {{s}} _ i} ^ {2}} \ right)$,并使用更新\ [
w ^ {(t + 1)} = w ^ {(t)}-\ eta \ frac {\ partial l} {\ partial p} G ^ {(t)} x ^ {(t)},
\]其中$ g ^ {{s}} =(\ partial l / \ partial p ^ {{s}})x ^ {{s}} $。在此更新中,$ G ^ {((t)} $)的尺寸为$ \ rho /(\ lambda \ chi)\ ldots $越来越近!不幸的是,$ \ eta $仍然不是无量纲的,其尺寸为$ \ rho / \ chi $。请注意,DHS推论1中$ \ eta $的最佳选择与$ \ max_t || w_t-w ^ * || _ {\ infty} $成正比,其单位为$(\ rho / \ chi)$。换句话说,如果所有输入都加倍,我们仍然必须将以前的最佳学习率降低一半才能获得最佳行为。

这就留下了一个问题:单位$(\ rho / \ chi)$可以用来对$ \ eta $进行规范化,使得在命令行上指定的参数是无量纲的。任何与$ t $相关的变化都不在DHS的分析范围之内,但我暂时将其忽略。两件事表明了自己:$ 1 / || x ^ {(t)\ top} x ^ {(t)} || _p $和$ 1 / /(x ^ {(t)\ top} G ^ {(t)} x ^ {(t)})$。 (这些单位为$ 1 / \ chi $,但越来越近了)。它们具有不同的属性。

直观地使自适应学习算法具有优势的是,它们在频繁出现的特征上更加保守,而在很少出现的特征上更具攻击性。使用$ || x ^ {(t)\ top} x ^ {(t)} || _p $归一化,如果遇到一个例子,其中所有特征以前都被广泛地看过和训练过,那么有效学习率将很小。因此,与在训练序列中较早看到此示例相比,预测的变化将很小。相反,通过$ x ^ {(t)\ top} G ^ {(t)} x ^ {(t)} $归一化,如果遇到一个例子,其中所有特征之前都已被广泛了解和训练,则有效学习速率将被归一化以补偿,使得相对于在训练序列中较早看到该示例而言,预测的变化不会很小。另一方面,对于一个在训练序列中较晚出现的新颖特征和频繁特征混合的示例,相对于该示例是否已发生,与采用任一归一化方案的频繁特征权重相比,更新对新颖特征权重的影响将更大。在训练序列中更早。

维度$(\ rho / \ chi)$还有其他内容。自适应学习方法的关键见解之一是使用来自整个输入历史的信息,而不仅仅是当前输入,来驱动学习。到目前为止,总结所有输入的一件事是权重向量。 DHS推论1中的最佳权重向量与$ \ max_t || w_t-w ^ * || _ {\ infty} $成正比,并且由于$ w_0 = 0 $,所以这大约是$ || ww ** ||。 _ \ infty $。 $ w ^ * $的一个近似值(可能太可怕了!)是当前的权重向量。当它为零时,这在开始时是一个特别糟糕的近似值,因此我考虑将提供的$ \ eta $缩放为$ \ max(1,|| w ^ {(t)} || __infty)$,其中仅考虑$ w ^ {(t)} $的具有$ x ^ {(t)} $的相应非零值的分量。

一个实验

有很多想法,所以我决定进行一个实验。我有数以千万计的推文,这些推文根据写该推文的人的性别进行了标记。由于推文中令牌数量的变化,输入向量具有有趣的范数。我使用恒定的学习速率(vowpal按$ x ^ \ top x $进行缩放)和DHS自适应学习算法按不同的值进行缩放进行了训练。我只对数据进行了一次传递,并且报告了训练集上渐进的验证折损。我在命令行上使用$ \ eta = 1 $进行了所有这些测试。 \ [
\ begin {array} {c | c | c}
\ mbox {方法}&\ mbox {损失}&\ mbox {评论} \\ \ hline
\ mbox {最佳常数}&\ mbox {0.722}&\ mbox {在Twitter上,女人比男人多(为什么?)}} \\
\ mbox {非自适应}&\ mbox {0.651}&\ mbox {在这种情况下,大众汽车通过$ || x ^ {(t)} || ^ 2_2 $归一化}} \\
\ mbox {自适应$ || x ^ {(t)} || _1 $规范化}&\ mbox {0.588}&\\
\ mbox {自适应$ || x ^ {(t)} || _2 $规范化}&\ mbox {0.554}和\\
\ mbox {自适应$ || x ^ {(t)} || __infty $归一化}&\ mbox {0.579}&\\
\ mbox {自适应$ x ^ {(t)\ top} G ^ {(t)} x ^ {(t)} $规范化}&\ mbox {0.621}&\ mbox {比替代方案差得多! } \\
\ mbox {自适应$ \ max(1,|| w ^ {(t)} || __infty)$缩放}&\ mbox {0.579}&\\
\ mbox {自适应$ \ max(0.1,|| w ^ {(t)} || __infty)$缩放}&\ mbox {0.562}&\\
\ mbox {自适应$ \ max(1,|| w ^ {(t)} || __infty)$缩放}&\ mbox {0.579}&\ mbox {忽略$ || w ^ {{t )} || __infty $} \\
\ mbox {自适应$ \ max(0.1,|| w ^ {(t)} || __infty)$缩放}&\ mbox {0.560}&\ mbox {忽略$ || w ^ {{t )} || __infty $} \\
\ end {array}
\]
实际上,对于$ z \ leq 0.1 $尝试$ \ max(z,|| w ^ {(t)} || __infty)$会得到相同的结果。我认为这可能是由于常量特征的权重(始终以值1表示;因此,在某种意义上,它具有固定的比例,不会随输入而变化),因此我尝试在计算时不使用常量特征$ || w ^ {(t)} || _ \ infty $,但结果大致相同。

因此,该实验表明,通过自适应范数$ x ^ {(t)\ top} G ^ {(t)} x ^ {(t)} $进行归一化确实会破坏自适应策略的有效性。否则,在此实验的基础上,很难真正偏爱一种策略。话虽如此,我个人最喜欢的是$ \ max(0.1,|| w ^ {(t)} || __ \ infty)$缩放比例,因为它直接来自遗憾分析并具有正确的单位。

现在,我需要回到最初的目标:在训练一个 二元模型.

4条评论:

  1. 来自John Langford的个人通讯:"我有点喜欢|| x || _2规范化,该规范在您的实验中似乎效果很好,但看起来也不太客气。但是,您的实验有些轻率,因为我'm愿意设置默认优化参数。例如,现在在大众汽车中,默认值为eta = 10,这从一开始就非常激进。如果它'合理方便,您能否针对每种算法在eta = 32,16,8,4,2,1,0.5,0.25,0.125上进行搜索并告诉我们最小错误率? (随时添加为评论。) "

    回复删除
  2. 我尝试将学习率从2 ^ 5提高到2 ^ -3(含)。我在这里报告每种方法的最佳结果。

    非自适应eta = 0.25 0.621
    自适应1 / || x || _1 eta = 4 0.562
    自适应1 / || x || _2 eta = 1 0.554
    自适应1 / || x || _infinity eta = 0.25 0.555
    自适应1 /(x ^ T G x)eta = 0.25 0.584
    最大值(0.1,|| w || __infinity)eta = 0.5 0.554
    最大值(0.1,|| w || __infinity)nc eta = 2 0.560

    方向相似的结果,但差异被压缩。

    回复删除
  3. 见表6
    "强化学习的神经优化器搜索"
    //arxiv.org/abs/1709.07417

    回复删除
    回覆
    1. 野生!元学习无疑是一个蓬勃发展的领域。

      删除