EM 算法的快速替代方案

机器算法验证 机器学习 优化 期望最大化 潜在语义分析
2022-03-23 07:08:52

EM 算法是否有任何快速的替代方法来学习具有潜在变量(尤其是 pLSA)的模型?我可以牺牲精度来换取速度。

4个回答

通常可以使用 Newton-Raphson 算法。我对 pSLA 不熟悉,但是将 Newton-Raphson 算法用于潜在类模型是很常见的。Newton-Raphson 算法比 EM 更容易受到初始值差的困扰,因此一种策略是首先使用 EM 的几次迭代(比如 20 次),然后切换到 Newton-Raphson 算法。我使用的一种算法取得了很大的成功:Zhu、Ciyou、Richard H. Byrd、Peihuang Lu 和 Jorge Nocedal (1997),“算法 778:L-BFGS-B:Fortran subroutines for large-scale bound-约束优化”,ACM 数学软件交易 (TOMS) 档案,23 (4), 550-60。

与 EM 算法非常相似的是MM 算法,它通常利用凸性而不是在对目标函数进行大写或小写时丢失数据。不过,您必须检查 MM 算法是否适用于您的特定问题。

对于 LDA,“在线 LDA”比标准 EM(http://www.cs.princeton.edu/~blei/papers/HoffmanBleiBach2010b.pdf)等批处理方法更快。

David Blei 在他的页面上提供了软件:http ://www.cs.princeton.edu/~blei/topicmodeling.html

到目前为止,答案中未提及的另一种替代方法是变分近似。尽管这些算法并非在所有情况下都完全是 EM 算法,但在某些情况下,EM 算法是贝叶斯平均场变分算法的限制情况。限制与超参数的限制情况有关,选择限制值(在某些情况下)将为您提供 EM 算法。

在任何一种情况下(EM、VB 甚至 MM 算法),都有两种通用方法可以加快速度:

(1) 降低问题的维数——从一个p-dim 问题p单变量问题。这些通常是坐标下降算法,但我见过 MM 算法也可以进行这种类型的加速。

(2) 提高您的 EM(或其他类型)算法的收敛速度。在评论中,JohnRos 提到了 Aitken 加速。这来自数值分析领域,但在 McLachlan 和 Krishnan 的 EM 书中进行了讨论。

可能还有其他我错过了,但这些似乎是两个大的。