2012年12月14日,星期五

潜在模型的光谱方法

今年在NIPS上有几个热门趋势,我将在以后的文章中对会议进行广泛介绍。现在,我想深入研究正在迅速发展且看起来非常有前途的特定研究领域: 潜在变量模型的谱算法。这是我对该主题的第三次主要曝光,并最终获得点击。正如我们将看到的,我需要3个观察值是合适的。

tl; dr版本如下:
  1. 潜在变量模型的频谱方法基于 瞬间法 而不是最大可能性。希望矩方法可以在学习过程中避免E步(``推论''),从而提高计算效率。
  2. 具有相关潜值的观测时刻具有低秩结构,当解码时可识别模型。
  3. 如果观测值足够高维,那么第三刻就足以识别模型(``维数祝福'')。特别是从前三个矩得出的对称张量的正交分解所产生的方向(``螺旋方向'')揭示了潜在结构。
这里的一切都是基于一组研究人员的开创性工作,其中包括Animashree Anandkumar,Dean P. Foster,Rong Ge,Daniel Hsu,Furong Huang,Sham M. Kakade,Yi-Kai Liu,Matus Telgarsky,还有可能是我俯瞰(对不起,提前!); 阿南库玛(Anandkumar)等等 提供了此博客文章的具体灵感。

瞬间方法

从某种意义上说,概率潜在变量模型与任何其他参数概率模型没有什么不同,因为一个人实际上从不观察概率分布的参数,仅是实现。例如,以Wikipedia示例为例,如果给您一个示例$ \ {x_i \} $从Gamma分布\ [
\ begin {aligned}
X&\ sim \ Gamma(\ alpha,\ beta),\\
\ frac {d \ Gamma(\ alpha,\ beta)} {d \ mu}&\doteq g (x;\ alpha,\ beta)= \ frac {x ^ {\ alpha-1} e ^ {-x / \ beta}} {\ beta ^ \ alpha \ Gamma(\ alpha)},
\ end {aligned}
\],则可以使用最大似然法或矩量法从样本中估算$ \ alpha $和$ \ beta $。要使用矩量方法,请将您关心的参数$(\ alpha,\ beta)$与可观测量的期望\ [
\ begin {aligned}
\ mathbb {E} [X]&= \ alpha \ beta,\\
\ mathbb {E} [X ^ 2]&= \ beta ^ 2 \ alpha(\ alpha +1),
\ end {aligned}
\]然后将期望值替换为样本估计值并求解参数。

从历史上看,矩方法被最大似然率所取代,主要是因为统计效率,这在机器学习术语中是一个样本复杂性问题。但是,如今,我们拥有大量数据,并且本质上是受计算限制的(作为此断言的证据,请考虑 大学习NIPS研讨会)。因此,最重要的是,如果矩量方法在计算上更易处理,那么它将胜过样本复杂性问题。相信基于矩量法的方法在计算上会便宜得多的原因之一是,潜在变量模型的最大可能性看起来像 电磁,而E-step(“推论”)价格昂贵;而矩量法则避免了学习过程中的E步。

相关潜在结构的观测

考虑以下简单的潜在变量模型:翻转有偏差的硬币,在该硬币的基础上翻转,从两个有偏差的硬币中选择一个,然后翻转该硬币并报告正面或反面,\ [
\ begin {aligned}
Z&\ sim \ mathcal {B}(\ pi,1),\\
X | Z&\ sim \ mathcal {B}(q_Z,1)。
\ end {aligned}
\]这里有3个未知数,因此直观地讲我们需要3个方程。让我们开始计算一下,从平均值\ [
\ begin {aligned}
\ mu&\ doteq \ mathbb {E} [X] = \ pi q_0 +(1-\ pi)q_1。 \\
\ end {aligned}
到目前为止,一切顺利,现在让我们再试一下,考虑两个观察值的乘积的期望值,
\ begin {aligned}
\ mathbb {E} [X_1 X_2]&= \ pi ^ 2 q_0 ^ 2 + 2 \ pi(1-\ pi)q_0 q_1 +(1-\ pi)q_1 ^ 2 = \ mu ^ 2。
\ end {aligned}
\]糟糕。实际上,我们并不需要所有的代数:由于观测值是同余的,因此所有高阶矩将是$ \ mu $的幂,并且上述形式的观测结果中没有其他信息。这不是力矩方法的限制,因为仅给出此信息,最大似然度也会失败。从根本上仅给出以上信息,就无法区分两种非常偏向的硬币的混合物与两种中等偏向的硬币的不同混合物。

假设您有不同的信息:告诉您观察对共享相同的(未知!)潜在值。 \ [
\ begin {aligned}
\ mathbb {E} [X_1 X_2 | Z_1 = Z_2] = \ pi q_0 ^ 2 +(1-\ pi)q_1 ^ 2。
\ end {aligned}
\]哈哈!第二条信息。需要我们只需要1,因此请考虑具有相同(未知!)潜在值\ [
\ begin {aligned}
\ mathbb {E} [X_1 X_2 X_3 | Z_1 = Z_2 = Z_3] = \ pi q_0 ^ 3 +(1-\ pi)q_1 ^ 3。
\ end {aligned}
\]现在我们有3个方程,并假设$ q_0 \ neq q_1 $,我们可以估计$ q_0 $,$ q_1 $和$ \ pi $,\ [
\ begin {aligned}
\ mathbb {E} [X]&= \ pi q_0 +(1-\ pi)q_1,\\
\ mathbb {E} [X_1 X_2 | Z_1 = Z_2]&= \ pi q_0 ^ 2 +(1-\ pi)q_1 ^ 2,\\
\ mathbb {E} [X_1 X_2 X_3 | Z_1 = Z_2 = Z_3]&= \ pi q_0 ^ 3 +(1-\ pi)q_1 ^ 3,
\ end {aligned}
\]在实践中,我们将期望值替换为样本均值。

关键是具有相关潜在结构的观测集是可识别性的关键。在上面的示例中,潜在值完全相同,但是(惊奇!)足以知道该潜在值是从相同的分布中得出的(又名``来自同一文档'')。

维度的祝福

对于更复杂的潜在结构,我们是否需要提高阶数?让我们修改模型,使其具有三个潜在状态。 \ [
\ begin {aligned}
Z&\ sim \ mathrm {Trinomial}(\ pi),\\
X | Z&\ sim \ mathcal {B}(q_Z,1)。
\ end {aligned}
\]现在我们有五个未知数($ \ pi_0,\ pi_1,q_0,q_1,q_2 $),因此看来我们必须转到五阶统计信息来识别参数。但是事实证明,这是观察到的结果是单次掷硬币的结果。如果观测值具有足够高的维数,则(惊奇!)三阶统计量就足够了。让我们再次修改模型,以便观察值是向量值\ [
\ begin {aligned}
Z&\ sim \ mathrm {Trinomial}(\ pi),\\
\ mathbb {E} [X | Z]&\ sim \ mu_Z。
\ end {aligned}
\]请注意,我们可以使用单次热编码$ \ mu_Z =(1- q_Z,q_Z)$恢复先前的二项式观察模型,但是现在我们将$ \ mu_Z $视为$ d>2 $尺寸。乍一看,这似乎没有任何优势,因为我们每个观测都有额外的信息,但也有额外的参数可以估算。但是,较高时刻中的信息内容比其他参数的数量增长得更快,从而使三阶时刻就足够了。看到这一点,瞬间展开,\ [
\ begin {aligned}
\ mathbb {E} [X]&= \ sum \ pi_i \ mu_i,\\
\ mathbb {E} [X_1 \ otimes X_2 | Z_1 = Z_2]&= \ sum \ pi_i \ mu_i \ otimes \ mu_i,\\
\ mathbb {E} [X_1 \ otimes X_2 \ otimes X_3 | Z_1 = Z_2 = Z_3]&= \ sum \ pi_i \ mu_i \ otimes \ mu_i \ otimes \ mu_i。
\ end {aligned}
\]天真的参数计数表明,第一和第二阶矩足以识别模型,但是$ \ mu_i $不是正交的,因此我们不能仅用例如SVD。但是,我们可以在协方差上使用SVD来构建$ \ mu_i $跨度的正交标准,并且在此基础上,三方差张量具有唯一的正交分解,其特征向量确定$ \ mu_i $。

如果$ \ mu_i $不是线性独立的,则前一个参数将失败,并且特别是这意味着观测值的维数必须至少是潜在变量的基数。幸运的是,我们在机器学习中通常具有非常高的维度数据,这种情况通常会产生问题(``维度的诅咒''),但在这里却创造了机会,可以从低阶矩中识别出丰富的潜在结构(``维度的祝福'')。 ”)。

对于更复杂的潜在模型,如何操纵前三个矩以提取所需的潜在参数的细节会发生变化,但基本策略是将问题简化为使用前三个矩构造的张量的正交分解。张量分解是一个特殊的优化问题,由于其广泛的适用性,我怀疑这可能是新的``$ L_2 $惩罚性铰链损失'',即在不久的将来有相当一部分机器学习可以被表征为找出如何(近似)快速解决此特定优化问题。

2条评论: