Apa perbedaan antara algoritma Baum-Welch dan pelatihan Viterbi?

18

Saat ini saya menggunakan pelatihan Viterbi untuk masalah segmentasi gambar. Saya ingin tahu apa keuntungan / kerugian dari menggunakan algoritma Baum-Welch, bukan pelatihan Viterbi.

machine-learning hidden-markov-model image-processing viterbi-algorithm baum-welch Gal Digital
sumber
3
Apa yang Anda maksud dengan 'pelatihan viterbi' sebenarnya?
bmargulies
2
Dalam masalah saya, saya memiliki array data bernilai nyata yang saya modelkan sebagai HMM (khusus campuran fungsi kepadatan ganda masing-masing dengan parameter yang tidak diketahui). Untuk saat ini saya berasumsi bahwa saya tahu probabilitas transisi keadaan. Yang saya maksud dengan Viterbi Trainig adalah algoritma berikut. 1) Secara sewenang-wenang menetapkan status ke setiap titik data (inisialisasi) 2) Lakukan MLE dari parameter fungsi kerapatan. 3) Re-estimasi keadaan untuk setiap poin (dapat dilakukan dengan Viterbi Alg). 4) Ambil langkah 2 dan ulangi kecuali kriteria berhenti terpenuhi.
Digital Gal
1
Pertanyaan yang sama ditanyakan pada stack overflow: pelatihan viterbi vs algoritma baum-welch
Franck Dernoncourt

Jawaban:

21

Algoritma Baum-Welch dan algoritma Viterbi menghitung berbagai hal.

Jika Anda mengetahui probabilitas transisi untuk bagian tersembunyi dari model Anda, dan probabilitas emisi untuk output terlihat dari model Anda, maka algoritma Viterbi memberi Anda urutan lengkap kemungkinan kondisi tersembunyi yang bergantung pada output dan spesifikasi model Anda.

Algoritma Baum-Welch memberi Anda baik probabilitas transisi tersembunyi yang paling mungkin maupun seperangkat probabilitas emisi yang paling mungkin diberikan hanya keadaan yang diamati dari model (dan, biasanya, batas atas pada jumlah keadaan tersembunyi). Anda juga mendapatkan "kemungkinan titik tertinggi" poin di negara-negara tersembunyi, yang seringkali sedikit berbeda dari urutan tersembunyi tunggal yang secara keseluruhan paling mungkin.

Jika Anda tahu model Anda dan hanya menginginkan status laten, maka tidak ada alasan untuk menggunakan algoritma Baum-Welch. Jika Anda tidak tahu model Anda, maka Anda tidak bisa menggunakan algoritma Viterbi.

Diedit untuk menambahkan: Lihat komentar Peter Smit; ada beberapa tumpang tindih / ketidakjelasan dalam nomenklatur. Beberapa orang menuntun saya ke bab karya Luis Javier Rodrıguez dan Ines Torres dalam "Pengenalan Pola dan Analisis Gambar" (ISBN 978-3-540-40217-6, hlm. 845-857) yang membahas kecepatan versus akurasi pertukaran timbal balik dari dua algoritma.

Secara singkat, algoritma Baum-Welch pada dasarnya adalah algoritma Expectation-Maximization (EM) yang diterapkan pada HMM; sebagai algoritma tipe-EM yang ketat, Anda dijamin akan bertemu setidaknya dengan maksimum lokal, dan untuk masalah unimodal temukan MLE. Ini membutuhkan dua lintasan data Anda untuk setiap langkah, dan kompleksitasnya menjadi sangat besar dalam panjang data dan jumlah sampel pelatihan. Namun, Anda berakhir dengan kemungkinan bersyarat penuh untuk parameter tersembunyi Anda.

Algoritma pelatihan Viterbi (berbeda dengan "algoritma Viterbi") mendekati MLE untuk mencapai peningkatan kecepatan dengan biaya akurasi. Ini segmen data dan kemudian menerapkan algoritma Viterbi (seperti yang saya mengerti) untuk mendapatkan urutan keadaan yang paling mungkin di segmen, kemudian menggunakan urutan keadaan yang paling mungkin untuk memperkirakan kembali parameter tersembunyi. Ini, tidak seperti algoritma Baum-Welch, tidak memberikan kemungkinan bersyarat penuh dari parameter tersembunyi, dan akhirnya mengurangi keakuratan sekaligus menghemat waktu komputasi yang signifikan (bab melaporkan 1 sampai 2 pesanan).

Kaya
sumber
7
Jika saya benar, Anda mencampur pelatihan Viterbi dan decoding Viterbi.
Peter Smit
1
Kamu benar. Saya tidak menyadari bahwa ada prosedur yang hanya menggunakan algoritma Viterbi untuk menghitung probabilitas transisi juga. Tampaknya - pada bacaan lebih lanjut - seperti ada beberapa tumpang tindih nomenklatur antara waktu diskrit / analisis keadaan HMM diskrit, dan waktu diskrit / analisis keadaan kontinyu menggunakan distribusi campuran Gaussian. Jawaban saya berbicara dengan pengaturan DTDS HMM, dan bukan pengaturan model campuran.
Kaya
@ Rich: Bisakah Anda mengarahkan saya ke beberapa materi yang dapat diakses (seperti tutorial HMM asli Rabiner) di Pelatihan Viterbi?
Yakub
4
Pelatihan @Jacob Viterbi juga dikenal dengan nama Segmental K-Means, lihat makalah ini oleh Juang dan Rabiner.
alto
1
@Anoldmaninthesea. Melihat kemungkinan antara zaman adalah cara normal untuk menilai konvergensi (kemungkinan harus selalu meningkat pada setiap zaman dan kemudian berhenti ketika Anda telah mencapai maksimum lokal). Hal lain yang dapat Anda lakukan adalah berhenti lebih awal dengan memantau kemungkinan data tidak digunakan selama EM.
alto
0

Maju-mundur digunakan ketika Anda ingin menghitung 'hal-hal yang tidak terlihat'. Misalnya, ketika menggunakan EM untuk meningkatkan model melalui data yang tidak diawasi. Saya pikir kertas Petrov adalah contoh. Dalam teknik yang saya pikirkan, Anda pertama-tama melatih model dengan data beranotasi dengan anotasi yang cukup kasar (misalnya tag untuk 'Verb'). Kemudian Anda secara acak membagi massa probabilitas untuk keadaan itu dalam dua kuantitas yang sedikit tidak sama, dan berlatih kembali, berjalan maju-mundur untuk memaksimalkan kemungkinan dengan mendistribusikan kembali massa antara kedua negara.

bmargulies
sumber