分层模型的稀疏在线更新

将SGD用于参数上具有先验分布的概率模型或具有规则决策边界的分类器时，有一个稀疏更新的技巧。饰演Alex Smola 已经讨论过 这已经在SVM中用于在线学习了一段时间，并且在 Vowpal Wabbit LDA实施。我将描述它，然后描述我为适应它而遇到的一些挑战 在线学习分层生成模型 用于众包数据。

故事始于训练数据集$ D $和由$ \ lambda $参数化的概率模型，其中包括似然函数$ L $和先验分布$ P $。这导致目标函数\ [
f（D; \ lambda）= \ log P（\ lambda）+ \ sum_ {d \ in D} \ log L（d | \ lambda）。
\]将前一项移到总和中会得出\ [
f（D; \ lambda）= \ sum_ {d \ in D} \ left（\ frac {1} {| D |} \ log P（\ lambda）+ \ log L（d | \ lambda）\ right），
\]看起来像是SGD优化的候选人，\ [
\ lambda（t + 1）= \ lambda（t）+ \ eta（t）\ frac {\ partial} {\ partial \ lambda} \ left（\ frac {1} {| D |} \ log P（\ lambda （t））+ \ log L（d（t）| \ lambda（t））\ right）。
\]通常情况是，仅对于$ \ lambda $的少量分量（即，似然项稀疏），特定基准面的似然项的梯度才为非零。例如，在众包生成模型中，未标记特定项目的工人不会增加可能性。不幸的是，由于先前项比较密集，因此生成的SGD更新并不稀疏。众所周知的技巧涉及在似然梯度为非零的示例之间，唯一的参数更新来自先前的梯度。用连续动力学近似逼近离散梯度动力学，\ [
\ frac {d} {dt} \ lambda_i（t）= \ frac {1} {| D |} \ eta（t）\ frac {\ partial} {\ partial \ lambda_i（t）} \ log P（\ lambda （t）），
\]从上一个更新值$ \ lambda_i（s）$进行积分时，有时会具有解析解。例如，在高斯先验和幂律衰减学习率下，\ [
\ begin {aligned}
\ log P（\ lambda（t））＆=-\ frac {1} {2} \ sum_i \ left（\ lambda_i（t）-\ mu \ right）^ 2，\\
\ eta（t）＆= \ eta_0（t + t_0）^ {-\ rho}，\\
\ lambda_i（t）＆= \ exp \ left（\ frac {\ eta_0} {| D |} \ left（\ frac {（s + t_0）^ {1-\ rho}} {1-\ rho}-\ frac {（t + t_0）^ {1-\ rho}} {1-\ rho} \ right）\ right）\ left（\ lambda_i（s）-\ mu \ right）+ \ mu。
\ end {aligned}
\] 到现在为止还挺好。不幸的是，我的生成模型是分层的，因此先前的分布本身是使用具有自己的超优先级的超参数来参数化的。目标函数变为\ [
f（D; \ lambda，\ mu）= \ log P（\ mu）+ \ log P（\ lambda | \ mu）+ \ sum_ {d \ in D} \ log L（d | \ lambda），
\]，更新将变为\ [
\ begin {aligned}
\ lambda（t + 1）＆= \ lambda（t）+ \ eta（t）\ frac {\ partial} {\ partial \ lambda} \ left（\ frac {1} {| D |} \ log P（\ lambda（t）| \ mu）+ \ log L（d（t）| \ lambda（t））\ right），\\
\ mu（t + 1）＆= \ mu（t）+ \ eta（t）\ frac {\ partial} {\ partial \ mu} \ left（\ frac {1} {| D |} \ log P（\ mu）+ \ frac {1} {| D |} \ log P（\ lambda（t）| \ mu）\ right）。
\ end {aligned}
\]双重！第一个问题是，即使似然梯度为零，由于超优先级，所有参数都具有耦合动力学。第二个问题是超参数的梯度计算不稀疏（即参数数量是线性的）。如果我是从头开始的，我可能会说``拧紧它，超级优先级不值得''，但我试图从批处理优化中重现我的结果，其中超级优先级更易于合并并提供了一些改进（和诊断性）值）。

如何进行？还有另一个（迄今为止未知吗？）技巧将在超优先级对该模式具有解析表达式的任何时间应用。在我的情况下，先验和超验都是高斯，因此对于固定的\\ lambda $，我知道最优的\\ mu $是什么，\ [
\ begin {aligned}
\ log P（\ lambda | \ mu）＆=-\ frac {1} {2} \ sum_i（\ lambda_i-\ mu）^ 2，\\
\ log P（\ mu）＆=-\ frac {1} {2}（\ nu-\ mu）^ 2，\\
\ mu ^ *（\ lambda）＆= \ frac {1} {| I | + 1} \ left（\ nu + \ sum_i \ lambda_i \ right），
\ end {aligned}
\]其中$ | I | $是参数数。这表明，每当$ \ lambda $发生更改时，最佳$ \ mu ^ * $都会经历相同的更改，该更改由$ \ frac {1} {| I | + 1} $。这建议以下过程：

1. 对于当前示例中每个具有非零似然梯度贡献的$ \ lambda_i $，
1. 像$ \ mu $是常数一样执行``纯先验''更新逼近，然后更新$ \ mu $以更改$ \ lambda_i $，\ [
   \ begin {aligned}
   \ epsilon＆\ leftarrow \ exp \ left（\ frac {\ eta_0} {| D |} \ left（\ frac {（s + t_0）^ {1-\ rho}} {1-\ rho}-\ frac { （t + t_0）^ {1-\ rho}} {1-\ rho} \ right）\ right），\\
   \ Delta \ lambda_i＆\ leftarrow（1-\ epsilon）（\ mu-\ lambda_i），\\
   \ lambda_i＆\ leftarrow \ lambda_i + \ Delta \ lambda_i，\\
   \ mu＆\ leftarrow \ mu + \ frac {1} {| I | + 1} \ Delta \ lambda_i。
   \ end {aligned}
   \] $ s $是$ \ lambda_i $的最后更新的时间戳。
2. 使用非零梯度贡献对每个$ \ lambda_i $执行似然SGD更新，并将结果更改传播到$ \ mu $，\ [
   \ begin {aligned}
   \ Delta \ lambda_i＆\ leftarrow \ eta_0（t + t_0）^ {-\ rho} \ frac {\ partial} {\ partial \ lambda_i} \ log L（d | \ lambda），\\
   \ lambda_i＆\ leftarrow \ lambda_i + \ Delta \ lambda_i，\\
   \ mu＆\ leftarrow \ mu + \ frac {1} {| I | + 1} \ Delta \ lambda_i。
   \ end {aligned}
   \]

现在，这有点令人不满意，因为实际上$ | I | $是一个自由参数，原因是 哈希技巧，而且通常会将其设置为比训练过程中利用的实际参数数量大得多。在限制$ | I | \ to \ infty $基本上减少到固定的先验设置，其中固定的先验均值是为$ \ mu $选择的初始值（而$ \ mu = \ nu $是初始化的正确选择，如果$ \ lambda（0 ）= 0 $）。在实践中，如果$ | I | $设置得不太大，则会给出看起来合理的超优先级（否则，它们将停留在超优先级均值）。这很有用，因为在我的标称标签提取技术中，超均值混淆矩阵可以帮助识别任务问题（或数据处理中某处的错误）。