Membuat model Markov entropi maksimum dari multi-input maksimum entropy classifier

9

Saya tertarik dengan konsep Maximum Entropy Markov Model (MEMM), dan saya berpikir untuk menggunakannya untuk tagger Part of Speech (POS). Saat ini, saya menggunakan classifier Maximum Entropy (ME) konvensional untuk menandai setiap kata. Ini menggunakan sejumlah fitur, termasuk dua tag sebelumnya.

MEMM menggunakan algoritma Viterbi untuk menemukan jalur optimal melalui Rantai Markov (mis. Untuk menemukan serangkaian tag optimal optimal untuk kalimat daripada optimal individu untuk setiap kata). Membaca tentang itu, ini tampaknya memiliki keanggunan dan kesederhanaan yang indah. Namun, setiap tahap hanya bergantung pada "hasil" dari tahap sebelumnya (yaitu sesuai Rantai Markov).

Namun, model ME saya menggunakan dua tahap sebelumnya (yaitu tag untuk dua kata sebelumnya). Tampaknya saya memiliki dua pendekatan yang mungkin:

  • Seperti dengan implementasi Viterbi konvensional, gunakan satu set jalur yang disimpan sesuai dengan satu (sebelumnya) tahap. Pengklasifikasi ME saya akan menggunakan ini dan tahap 'beku' sebelum ini (dibekukan ke jalur yang sedang dipertimbangkan) untuk menghasilkan fungsi transfer.

  • Atau saya menulis algoritme untuk melacak dua tahap. Ini lebih rumit dan tidak lagi menjadi Model Markov yang sebenarnya karena setiap fungsi transfer (yaitu dari Model ME) akan tergantung pada dua tahap sebelumnya dan bukan satu tahap.

Menurut saya, yang kedua akan lebih akurat, meskipun akan lebih rumit.

Saya belum menemukan contoh ini selama pencarian literatur saya. Sudahkah dicoba? Apakah pendekatan dua tahap memberikan peningkatan akurasi keseluruhan?

menang
sumber

Jawaban:

4

(Ini benar-benar pertanyaan nyata yang saya hadapi dan situs ML StackExchange yang ditayangkan adalah waktu yang cukup sempurna: Saya telah melakukan beberapa hari membaca buku dan riset online dan akan segera mulai diterapkan. Inilah hasil saya. Meskipun mereka tidak keras saya pikir mereka menjawab pertanyaan saya sendiri. Saya akan membiarkan pertanyaan terbuka untuk saat ini jika ada yang punya masukan yang berguna, telah mencoba sesuatu yang serupa, atau memiliki beberapa referensi yang bermanfaat.)

Oke selama beberapa hari terakhir saya sudah membuat kode ini. Kode ini tidak terlalu efisien - banyak pembuatan & penyalinan koleksi, tetapi tujuan dari latihan ini adalah untuk melihat apakah itu akan berhasil, dan seberapa baik kerjanya.

Saya membagi data saya secara acak menjadi dua daftar: data pelatihan, dan data uji. Saya menjalankan data uji melalui Tagger POS Entropy Maksimum konvensional; dan tager MEMM baru saya. Oleh karena itu mereka melihat data tes yang sama, memungkinkan perbandingan langsung - karena keacakan data yang dipilih, saya melihat beberapa variasi antara tes (biasanya sekitar 0,2-0,4%).

Tes pertama menggunakan tager MEMM dengan satu tahap (mis. Rantai Markov yang sebenarnya). Ini secara konsisten berkinerja lebih baik daripada tagger ME sederhana sekitar 0,1-0,25%.

Selanjutnya saya mencoba pendekatan dua tahap yang sepertinya lebih tepat. Namun hasilnya bahkan lebih marjinal. Seringkali hasilnya akan identik, kadang-kadang akan sedikit lebih rendah, tetapi mungkin sebagian besar kali itu sedikit lebih baik (jadi +/- 0,05%).

Tager MEMM lambat. Oke saya belum menerapkan optimasi apa pun, tetapi tahap 1 (rantai Markov sejati) adalah N kali lebih lambat (di mana N = Jumlah label) karena ini adalah jumlah jalur yang ditransfer antara setiap langkah. Implementasi 2 tahap adalah N * N lebih lambat (karena semakin banyak jumlah jalur yang ditransfer). Meskipun optimisasi dapat meningkatkan banyak hal, saya ini mungkin terlalu lambat untuk sebagian besar aplikasi praktis.

Satu hal yang saya coba adalah menerapkan batas probabilitas yang lebih rendah untuk jalur. Yaitu. jalur Viterbi dipangkas selama setiap iterasi dengan semua jalur di bawah probabilitas tertentu (saat ini Log (total jalur P) <- 20,0) dipangkas. Ini memang berjalan sedikit lebih cepat, tetapi pertanyaannya tetap, apakah itu layak. Saya pikir mungkin tidak.

Mengapa kita tidak melihat peningkatan? Saya pikir ini terutama disebabkan oleh perilaku POS tag dan model Entropy Maksimum. Meskipun model mengambil fitur berdasarkan dua tag sebelumnya, tag sebelumnya langsung jauh lebih penting dibandingkan dengan yang sebelumnya. Secara intuitif ini masuk akal untuk bahasa Inggris (mis. Kata sifat biasanya diikuti oleh kata benda atau kata sifat lain tetapi ini tidak benar-benar tergantung pada apa yang ada sebelum kata sifat).

menang
sumber