Gizli Markov Modeli (HMM) casino durumuyla nasıl açıklanır?
1. Arka plan tanıtımı: Kumarhane durumu
Son zamanlarda, bir kumarhanenin sahibi, işin iyi gitmediğini fark etti ve etrafa bakmak için ellerini kumarhaneye gönderdi. Casuslar, bir amcanın kumarhanede her zaman para kazanabileceğini ve neredeyse yenilmez olan zarlarla iyi oynayabileceğini bildirdi. Ve her zarı oynadığınızda, etrafınızda birkaç koruma vardır, bu da insanları belirsizleştirir.Oyuna her başladığınızda sadece zarların fırladığını ve sakince indiğini görebilirsiniz. Yılların deneyimine dayanarak, patron bu kötü konuğun uzun yıllardır kaybedilen "hırsızlık zar değişikliğini" kullandığını tahmin ediyor (Editörün notu: gizlice zar yöntemini değiştirmek, gizlice çift zarları cebindeki zarlarla değiştirmek). Patron sakin bir kişidir ve onu kolayca kırmak istemez ve kuralları çiğnemesini istemez. Endişelendiğim için HMM adında yakışıklı bir adam geldi ve patrona iyi bir çözümü olduğunu söyledi.
Yakın olmanıza gerek yok, sadece uzağa bir kamera kurun ve her turda zarların puanlarını kaydedin.
Sonra yakışıklı HMM, bu verilerden türetmek için güçlü matematiksel iç kuvvetlerini kullanacaktır:
- Amca binler ödüyor mu?
- Eğer bin ise kaç tane hile zarı kullanmış, şu anda hiç hile zarı var mı?
- Bu hile zarlarının her noktasının olasılığı nedir?
Tanrım, patron duyduğunda, HMM'nin hile yapıp yapmadığını ya da başkalarının aldattığı zarları anlamaya yakın olmasına bile gerek yoktu. Sonra, hile yaptığı sürece, birisini onu toparlayacak ve konuşmasız hale getirmek için yerinde zarları doğrulayacak birini gönderin.
İkincisi, HMM nerede kutsaldır?
HMM'den soruşturma yapmasını istemeden önce, kumarhane sahibi de HMM hakkında soruşturma yaptı.
Gizli Markov Modeli olarak da bilinen HMM (Gizli Markov Modeli), bir sistemin gizli durumunun geçişini ve gizli durumun performans olasılığını tanımlamak için kullanılan bir olasılık modelidir.
Sistemin resesif durumu, dış dünya tarafından gözlemlenmesi sakıncalı (veya gözlenemeyen) bazı durumları ifade eder.Örneğin, mevcut örnekte, sistemin durumu, zar kullanan amcanın durumunu ifade eder.
{Normal zar, hile zar 1, hile zar 2, ...}
Resesif durumun performansı da, resesif durum tarafından üretilen dış performans karakteristikleri olan gözlemlenebilirdir. Bu, zarın attığı puanların sayısıdır.
{1,2,3,4,5,6}
HMM modeli, sistemin gizli durumunun geçiş olasılığını tanımlayacaktır. Yani amcanın zarı değiştirme olasılığı, aşağıdaki şekil bir örnektir, şu anda amcanın zarı değiştirme olasılığı keskin ve canlı bir şekilde anlatılmıştır.
Elbette, geçiş olasılığını gösteren resesif bir durum da olacaktır. Yani, zarın her noktasının olasılık dağılımı, (örneğin, hile zarının 1'in altıya yuvarlanması için% 90 şansı vardır ve hile zarının% 85 şansı 'küçük' olur). Aşağıdaki gibi bir resim verin:
Resesif durumun performans dağılım olasılığı, bir matris ile de güzel bir şekilde temsil edilebilir:
Bu iki şeyi özetlemek gerekirse, tüm HMM modelidir.
Bu model, resesif durumun geçiş olasılığını açıklar ve ayrıca her bir durumun harici performans olasılığının dağılımını tanımlar. Kısaca HMM modeli, amcanın zar atma sıklığını (zarı değiştirme olasılığı) ve amcanın kullandığı zarın olasılık dağılımını tanımlayabilir. Amcasının HMM modeli ile amcasının arkasını görebilir ve onu güneşte tamamen görünür kılabilir.
Üç, HMM ne yapabilir!
Özetle, HMM üç sorunu halledebilir,
3.1 Kod çözme
Kod çözme, hangilerinin hile zarları ve hangilerinin normal zarlar olduğunu bulmaktır.
Örneğin, yukarıdaki şekilde, bir dizi zar dizisi (3, 6, 1, 2 ..) ve amcanın HMM modeli verildiğinde, hangi zar sonuçlarının (resesif durum performansı) hangi zarla ilişkili olabileceğini hesaplamak istiyoruz. Sonuç (gizli durum).
3.2 Öğrenme
Öğrenme, amcanın bir dizi zardan zarı değiştirme olasılığını ve elbette bu zarların puanlarının dağılım olasılığını öğrenmektir. Bu, HMM'nin en korkunç ve karmaşık numarasıdır! !
3.3 Değerlendirme (Değerlendirme)
Amcanın HMM modelini zaten bildiğimiz durumda, belirli bir zar dizisinin görünme olasılığını tahmin ettiğimiz tahmin edilmektedir. Örneğin, amcanın HMM modelini zaten bildiğimizde, amcanın 106s veya 81s fırlatma olasılığını doğrudan tahmin edebiliriz.
Dördüncüsü, HMM bunu nasıl yapıyor?
(Bu bölüm olasılık teorisi, özyineleme ve dinamik programlama bilgisi gerektirir. İlgilenmiyorsanız, bölüm 5'e geçebilirsiniz)
4.1 Tahmin
Tahmin en kolay yoldur, amcanın HMM modelini tam olarak bildiğimizde kolayca tahmin edebiliriz.
Şimdi amcanın durum geçiş olasılık matrisine sahibiz A, B tahmin edilebilir. Örneğin, amcanın bir sonraki turda arka arkaya 106s dönme olasılığını bilmek istiyoruz?
Bu, başlangıçta resesif durum (s0) 1 olduğunda, yani başlangıçta normal bir zar tuttuğunda bu amcanın arka arkaya 106s atma olasılığı anlamına gelir.
Şimdi sorun zor, HMM'nin geçiş olasılığını ve gözlemlenen V {1: T} durumunu bilmemize rağmen, gerçek gizli durum değişikliğini bilmiyoruz.
Tamam, resesif durumun değişimini bilmiyoruz, o yüzden tamam, ilk önce amcanın ilk 5'inin normal zar kullandığını ve son 5'inin hile zarının 1 kullandığını varsayarak, resesif durum sekansını varsayalım.
Tamam, o zaman bu örtük dizi varsayımı altında 106s yuvarlanma olasılığını hesaplayabiliriz.
Bu olasılık aslında çekinik durum performans olasılığı B'nin ürünüdür.
Ama sorun yeniden ortaya çıktı. Gizli durum dizisi az önce benim tarafımdan varsayıldı ve gerçek sıralamayı bilmiyorum. Ne yapmalıyım? Kullanımı kolaydır, tüm olası gizli durum dizisi kombinasyonlarını deneyin. sonra,
R, tüm olası resesif durum dizilerinin kümesidir. Evet, şimdi problem çözülmüş gibi görünüyor.Tüm kombinasyonları deneyerek oluşma olasılığını elde edebildik ve A, B matrisi üzerinden toplam gerçekleşme olasılığını hesaplayabiliyoruz.
Ama sorun yeniden ortaya çıktı.Mümkün olan set çok büyük. Örneğin, üç çeşit zar varsa ve seçilecek 10 şans varsa, toplam kombinasyon 3 ^ 10 kat olacaktır ... Bu büyüklük O (c ^ T) çok büyük, Problem büyüdüğünde, kombinasyon sayısı hesaplanamayacak kadar büyük olacaktır. Bu yüzden P (V (1: T)) olasılığını hesaplamak için daha etkili bir yönteme ihtiyacımız var.
Örneğin, aşağıdaki şekilde gösterilen algoritma, P (V1: T) 'yi O (cT)' ye hesaplamanın hesaplama karmaşıklığını azaltabilir.
Bu denklem ile P (V1: T) olasılığını t = 0 durumundan ileri doğru çıkarabiliriz. Hadi matematiği yapalım: Amcanın sırayla 3, 2 ve 1 zar atma olasılığı ne kadardır (başlangıç durumunun 1 olduğu, yani amcanın son kez normal bir zar tuttuğu varsayılırsa)?
4.2 Kod çözme
Kod çözme işlemi, bir dizi dizisi verilen ve bilinen HMM modeli verilen en olası gizli durum dizisini bulmaktır.
Matematiksel formülle ifade edilir, (V Görünür'ün görünür dizisidir, w gizli durum dizisidir, A, B HMM durum geçiş olasılığı matrisidir)
Aşağıdaki formülü hatırlayın:
Daha sonra en büyük P'yi (w (1: T), V (1: T)) hesaplamak için tahminde (4.1) ileri türev yöntemini kullanabilirsiniz.
İleri türetme yöntemini tamamladıktan sonra, bu P'yi (w (1: T), V (1: T)) maksimize edebilecek örtük diziyi çözmek için Geri İzleme yöntemini kullanın. Bu algoritmaya Viterbi Algoritması denir.
- Viterbi algoritması en olası çekinik sırayı bulur
Bu bir tür dinamik programlama algoritmasıdır. `` Çözüm yöntemi aynıdır. '' Özyinelemeli denklem bulunur ve sonra ileri türetme ile çözülür. Daha sonra, en uygun çözümü elde etmek için denklem kombinasyonunu bulmak için geriye doğru izleme yöntemi kullanılır. Aşağıda bir hesaplama zar dizisi {1, 2,6) En olası gizli dizi kombinasyonu. (Başlangıç durumu 1 = normal zar,)
4.3 Öğrenme
Öğrenmeye HMM'nin yapısı verilir (örneğin, amcanın 3 zarı ve her zarın 6 yüzü olduğu varsayılarak), en olası model parametrelerini hesaplayın.
HMM'nin yapısını üstlendikten sonra, Olasılığı maksimize etmek için EM (Beklenti Maksimizasyonu) algoritması kullanılabilir.Buradaki maksimum olasılık,
Yapmamız gereken, olasılığı en üst düzeye çıkaran işlevi bulmaktır.Dolayısıyla bu sorun, "Maksimum Olabilirlik Tahmin Problemi (MLE)" haline getirilir. MLE problemindeki gizli parametreleri tahmin etmeniz gerektiğinde, EM algoritmasını kullanmanız gerekir. (EM'ye özgü algoritma türetme için, lütfen JerryLead'in bloguna bakın) tahmin için.
Beş, HMM uygulaması
Yukarıdaki örnek, zarları modellemek ve analiz etmek için HMM'yi kullanmaktır. Elbette sorunları farklı uygulama gereksinimlerine göre modelleyebilen birçok klasik HMM uygulaması vardır.
Bununla birlikte, modelleme için HMM kullanma sorunu aşağıdaki koşulları karşılamalıdır,
- Gizli durum geçişi Markov mülkü karşılanmalıdır . (Durum geçişinin Markov özelliği: bir durum yalnızca önceki durumla ilgilidir)
- Resesif durum Kabaca tahmin edilmelidir.
Koşullar karşılandığında, problemdeki resesif durumun ne olduğunu ve resesif durumun olası tezahürlerinin neler olduğunu belirleyin.
HMM'nin uygun olduğu sorun, gerçek durumun (gizli durum) tahmin edilmesinin zor olması ve durum ile durum arasında bir bağlantı olmasıdır.
5.1 Konuşma tanıma
Konuşma tanıma problemi, bir konuşma sinyalini bir metin dizisine dönüştürme işlemidir. Bu soruda
Gizli durum şudur: konuşma sinyaline karşılık gelen metin dizisi
Ve baskın durum şudur: ses sinyali.
HMM modelinin öğrenilmesi: Konuşma tanımanın öğrenme modeli, yukarıdaki zar dizisini gözlemleyerek en olası modelin oluşturulmasından farklıdır.HMM modeli konuşma tanıma öğreniminin iki adımı vardır:
- Metnin telaffuz olasılığını hesaplayın ve gizli performans olasılık matrisi B'yi oluşturun
- Kelimeler arasındaki geçiş olasılığını hesaplayın (bu adımda sesi dikkate almanız gerekmez, kelimeler arasındaki geçiş olasılığını doğrudan sayabilirsiniz)
Konuşma modelinin değerlendirilmesi (Değerlendirme): "on dörttür", "kırk dört" vb. Olasılığını hesaplayın ve en olası metin dizisini karşılaştırın.
5.2 El yazısı tanıma
Bu, el yazısı tanıma sürecinin kelimenin görüntüsünü baskın bir sıra olarak ele alması dışında konuşmaya benzer.
5.3 Çince kelime segmentasyonu
"Hepimizin bildiği gibi, Çince'de kelimeler arasında ayırıcı yoktur (İngilizce'de kelimeler boşluklarla ayrılır, bunlar doğal kelime bölümleme işaretleri) ve kelimelerin kendisinde belirgin morfolojik işaretler yoktur. Bu nedenle, Çince bilgi işlemenin benzersiz sorunu, Çince karakter dizilerinin makul kelime sırasına nasıl bölüneceğidir.
Örneğin, İngilizce cümle: anaokuluna gitmelisin. Doğal alanlar zaten kelimeleri böldü, sadece içindeki "-" edatını kaldır ve "şimdi anaokuluna gitmelisin" cümlesi aynı anlamı açık bir anlam olmadan ifade ediyor Ayırıcı, Çince kelime segmentasyonunun amacı "sen / şimdi / git / anaokuluna / şimdi" elde etmektir.
Peki, kelime segmentasyonunu nasıl yaparsınız? Üç temel yöntem vardır:
- Tip 1 Dil bilgisine dayalı kural yöntemi Mesela: çeşitli formların maksimum eşleştirme ve minimum bölümleme yöntemleri;
- Tip 2 Büyük ölçekli külliyat tabanlı makine öğrenimi yöntemi Bu, yaygın olarak kullanılan ve daha iyi sonuçlara sahip bir çözümdür. Kullanılan istatistiksel modeller arasında N-gram dil modeli, kanal-gürültü modeli, maksimum beklenti, HMM vb.
- Üçüncü kategori, gerçek kelime bölümleme sisteminde de kullanılır, yani Kurallar ve istatistikler gibi birden çok yöntemin entegrasyonu . Çince kelime segmentasyonu için HMM kullanın.
Yazar: Yu Pang Nong Kaynak: neredeyse biliyorum
