Alternatif cepat untuk algoritma EM

13

Apakah ada alternatif cepat untuk algoritma EM untuk model pembelajaran dengan variabel laten (terutama pLSA)? Saya baik-baik saja dengan mengorbankan presisi demi kecepatan.

machine-learning optimization expectation-maximization lsa Aslan986
sumber
1
Sudahkah Anda melakukan survei literatur? Makalah ini terlihat sangat relevan: Convex Relaxations of Latent Variable Training
Emre
1
Bagaimana dengan LSA? :-)
conjugateprior
1
Cara umum untuk mempercepat EM disebut "akselerator Aitken". Jika presisi bukan masalah, mungkin coba estimasi momen atau estimasi momen umum sebagai gantinya.
JohnRos

Jawaban:

4

Algoritma Newton-Raphson sering dapat digunakan. Saya tidak terbiasa dengan pSLA, tetapi cukup umum untuk menggunakan algoritma Newton-Raphson untuk model kelas laten. Algoritma Newton-Raphson sedikit lebih bermasalah oleh nilai awal yang buruk daripada EM, jadi salah satu strateginya adalah pertama menggunakan beberapa iterasi (katakanlah 20) dari EM dan kemudian beralih ke algoritma Newton-Raphson. Salah satu algoritma yang saya telah banyak sukses adalah: Zhu, Ciyou, Richard H. Byrd, Peihuang Lu, dan Jorge Nocedal (1997), "Algoritma 778: L-BFGS-B: Subrutin Fortran untuk skala besar terikat- optimasi terbatas, "Transaksi ACM pada perangkat lunak Matematika (TOMS) arsip, 23 (4), 550-60.

Tim
sumber
4

Sangat mirip dengan algoritma EM adalah algoritma MM yang biasanya mengeksploitasi konveksitas alih-alih data yang hilang dalam mayorisasi atau minorisasi fungsi objektif. Anda harus memeriksa apakah algoritma MM dapat diterapkan untuk masalah khusus Anda.

rumput laut
sumber
3

Untuk LDA, "LDA online" adalah alternatif cepat daripada metode batch seperti EM standar (http://www.cs.princeton.edu/~blei/papers/HoffmanBleiBach2010b.pdf).

David Blei menyediakan perangkat lunak di halamannya: http://www.cs.princeton.edu/~blei/topicmodeling.html

pengguna1149913
sumber
2

Alternatif lain yang tidak disebutkan sejauh ini dalam jawaban adalah perkiraan variasional. Meskipun algoritma ini bukan algoritma EM pada semua kasus, pada beberapa kasus, algoritma EM membatasi kasus algoritma variasional bidang-rata Bayesian. Batas berkaitan dengan kasus pembatas dari parameter-hiper, memilih nilai pembatas-dalam beberapa kasus-akan memberi Anda algoritma EM.

Dalam kedua kasus (EM, VB, atau bahkan algoritma MM) ada 2 cara umum untuk mempercepat:

(1) mengurangi dimensi masalah-dari a halmasalah -dim untuk halmasalah univariat. Ini biasanya mengkoordinasikan algoritma penurunan tetapi saya telah melihat algoritma MM yang juga melakukan speedup jenis ini.

(2) meningkatkan laju konvergensi algoritma EM Anda (atau tipe lainnya). Dalam komentar JohnRos disebutkan akselerasi Aitken. Ini dari dunia analisis numerik tetapi dibahas dalam buku EM oleh McLachlan dan Krishnan.

Mungkin ada orang lain yang saya lewatkan tetapi ini sepertinya dua yang besar.

Lucas Roberts
sumber