Быстрые альтернативы алгоритму EM

13

Существуют ли какие-либо быстрые альтернативы алгоритму EM для обучения моделей со скрытыми переменными (особенно pLSA)? Я в порядке, жертвуя точностью ради скорости.

Aslan986
источник
1
Вы сделали обзор литературы? Эта статья выглядит особенно актуальной: выпуклая релаксация обучения скрытым переменным
Emre
1
Как насчет ЛСА? :-)
конъюгатприор
1
Общий способ ускорения ЭМ называется «ускоритель Айткена». Если точность не является проблемой, возможно, вместо этого попробуйте оценку момента или обобщенную оценку момента.
JohnRos

Ответы:

4

Часто могут применяться алгоритмы Ньютона-Рафсона. Я не знаком с pSLA, но довольно часто используют алгоритмы Ньютона-Рафсона для моделей скрытых классов. Алгоритмы Ньютона-Рафсона немного более обеспокоены плохими начальными значениями, чем EM, поэтому одна из стратегий состоит в том, чтобы сначала использовать несколько итераций (скажем, 20) EM, а затем переключиться на алгоритм Ньютона-Рафсона. Один алгоритм, с которым у меня был большой успех, это: Чжу, Сиу, Ричард Х. Берд, Пейхуан Лу и Хорхе Носедал (1997), «Алгоритм 778: L-BFGS-B: подпрограммы Фортрана для крупномасштабного связывания. ограниченная оптимизация, "ACM транзакции по математическому программному обеспечению (TOMS)", 23 (4), 550-60.

Тим
источник
4

Алгоритм EM очень похож на алгоритм MM, который обычно использует выпуклость, а не пропущенные данные при мажорировании или миноризации целевой функции. Вы должны проверить, применим ли алгоритм MM для вашей конкретной проблемы.

sebp
источник
3

Для LDA «онлайн-LDA» - это быстрая альтернатива пакетным методам, таким как стандартный EM (http://www.cs.princeton.edu/~blei/papers/HoffmanBleiBach2010b.pdf).

Дэвид Блей предоставляет программное обеспечение на своей странице: http://www.cs.princeton.edu/~blei/topicmodeling.html

user1149913
источник
2

Другой альтернативой, не упомянутой в ответах, являются вариационные приближения. Хотя эти алгоритмы не являются точно EM-алгоритмами во всех случаях, в некоторых случаях EM-алгоритмы являются предельными случаями байесовских вариационных алгоритмов среднего поля. Предел относится к предельному случаю гиперпараметров, выбор предельных значений - в некоторых случаях - даст вам EM-алгоритм.

В любом случае (алгоритмы EM, VB или даже MM) есть 2 общих способа ускорить процесс:

(1) уменьшить размерность проблемы - с ппроблема в подномерные проблемы. Обычно это алгоритмы координатного спуска, но я видел алгоритмы MM, которые также ускоряют этот тип.

(2) улучшение скорости сходимости вашего алгоритма EM (или другого типа). В комментарии JohnRos упомянул ускорение Aitken. Это из мира численного анализа, но обсуждается в книге EM МакЛахлана и Кришнана.

Могут быть и другие, которые я пропустил, но они, кажется, два больших.

Лукас Робертс
источник