Gizli Markov modeli basit ve anlaşılması kolay örneklerle nasıl açıklanır?
Hidden Markov (HMM) hakkında konuşmak kolay, ancak anlaşılması kolay ve konuşması zor. Ama daha kolay anlaşılır bir örnek vermek istiyorum. Umarım okuyucularım uzman değildir, bu problemle ilgilenen yeni başlayanlardır, bu yüzden daha fazla matematiksel fikir açıklayacağım ve daha az formül yazacağım. Hawking bir keresinde bir formül daha yazarsanız okuyucularınızın yarısını kaybedeceğinizi söylemişti. Yani kısa bir zaman tarihi, fizik üzerine bir kitap, Madonna'nın seks kitabının yanı sıra satıyor. Bu yaklaşımı izleyeceğim ve en erişilebilir cevabı yazacağım. Yine de en klasik örneği kullanın, zarları atın. Elimde üç farklı zar olduğunu varsayalım. İlk zar bizim normal zarımızdır (buna D6 diyelim), 6 yüzlü, her yüzün (1, 2, 3, 4, 5, 6) 1/6 olasılığı vardır. İkinci zar bir tetrahedrondur (buna D4 deyin) ve her yüzün (1, 2, 3, 4) görünme olasılığı 1 / 4'tür. Üçüncü zarın sekiz yüzü vardır (buna D8 deyin) ve her bir tarafın (1, 2, 3, 4, 5, 6, 7, 8) 1/8 olasılığı vardır.
Diyelim ki zar atmaya başladık, önce üç zardan birini seçelim, her zarı seçme olasılığı 1/3. Sonra zarı atıyoruz ve 1, 2, 3, 4, 5, 6, 7 veya 8'den birini alıyoruz. Yukarıdaki işlemi sürekli tekrarlayın, bir dizi sayı alacağız, her sayı 1, 2, 3, 4, 5, 6, 7, 8'den biridir. Örneğin, böyle bir sayı dizisi elde edebiliriz (zarları 10 kez atın): 16 35 27 35 24 Bu sayı dizisine görünür durum zinciri denir. Ancak gizli Markov modelinde, yalnızca böyle bir görünür durum zincirine değil, aynı zamanda bir gizli durum zincirine de sahibiz. Bu örnekte, bu örtük durumlar zinciri, kullandığınız zar dizisidir. Örneğin, örtük durum zinciri şöyle olabilir: D6 D8 D8 D6 D4 D8 D6 D6 D4 D8
Genel olarak konuşursak, HMM'de bahsedilen Markov zinciri aslında gizli durumlar zincirine atıfta bulunur, çünkü gizli durumlar (kalıp) arasında bir geçiş olasılığı vardır. Örneğimizde, D6'nın sonraki durumu D4'tür ve D6 ile D8'in olasılığı 1 / 3'tür. D4 ve D8'in sonraki durumu D4'tür ve D6 ile D8'in geçiş olasılığı da 1/3 ile aynıdır. Bu ayar başlangıçta kolay açıklama içindir, ancak dönüşüm olasılığını istediğimiz gibi ayarlayabiliriz. Örneğin, D6'nın ardından D4'ün gelemeyeceğini, D6'nın ardından D6'nın gelme olasılığının 0,9 ve D8 olasılığının 0,1 olduğunu tanımlayabiliriz. Bu yeni bir HMM'dir.
Benzer şekilde, görünür durum arasında geçiş olasılığı olmamasına rağmen, gizli durum ile emisyon olasılığı adı verilen görünür durum arasında bir olasılık vardır. Örneğimizde, 1'i üreten altı taraflı bir kalıbın (D6) çıktı olasılığı 1 / 6'dır. 2, 3, 4, 5, 6 üretme olasılığı da 1 / 6'dır. Çıktı olasılığının başka tanımlarını da yapabiliriz. Örneğin, kumarhane tarafından hareket ettirilmiş altı yüzlü bir zarım var. 1 atma olasılığı daha büyük, 1/2 ve 2, 3, 4, 5 ve 6 yuvarlanma olasılığı 1/10.
Aslında HMM için, tüm gizli durumlar arasındaki geçiş olasılığını ve tüm gizli durumlar ile tüm görünür durumlar arasındaki çıkış olasılığını önceden biliyorsanız, simülasyon yapmak oldukça kolaydır. Ancak HMM modelini uygularken, bilginin bir kısmı genellikle eksiktir. Bazen kaç tür zar olduğunu ve her bir zar türünün ne olduğunu bilirsiniz, ancak atılan zarların sırasını bilmezsiniz; bazen zarın birçok kez atıldığını görürsünüz Sonuç olarak ne kaldığını bilmiyorum. Bu eksik bilgileri tahmin etmek için bir algoritma kullanılırsa, bu çok önemli bir problem haline gelir. Bu algoritmaları aşağıda detaylı olarak tartışacağım. × × Mahsul
Sadece basit ve anlaşılması kolay bir örnek görmek istiyorsanız, onu okumanıza gerek yoktur.
× × Mahsul
Birkaç saçmalık söylemek gerekirse, cevaplayıcı bir algoritmayı anlamak için şu iki şeyi yapmanız gerektiğini düşünüyor: anlamını anlamak ve şeklini bilmek. Asıl cevabın cevabı aslında ilk noktadır. Ancak bu en önemli noktadır ve pek çok kitapta ele alınmaz. Tıpkı bir kızı kovalarken, kız size "Yanlış bir şey yapmadınız!" Der. Sadece kızın ifadesine bakarsanız ve yanlış bir şey yapmadığınızı düşünürseniz, açıkça yanlış anlarsınız. Kızın "Acele et ve benden özür dile!" Şeklindeki anlamına dikkat etmelisin. Böylece karşılık gelen ifadeyi gördüğünüzde, hatalarınızı çabucak kabul edebilir ve merhamet dileyebilirsiniz. Matematik için de aynı şey anlamını anlamıyorsanız, sadece formüle bakın ve genellikle kafanız karışır. Ancak matematiğin ifadesi en iyi ihtimalle biraz belirsizdir ve bazen kızın ifadesi orijinal niyetine tamamen aykırıdır. Dolayısıyla, katılımcı her zaman kızları anlamanın matematiği anlamaktan çok daha zor olduğunu düşünüyor.
Konuya geri dönersek, HMM modeliyle ilgili algoritmalar esas olarak üç kategoriye ayrılır ve sırasıyla üç problemi çözer:
1) Birkaç zar türü olduğunu (gizli durumların sayısı), her zarın ne olduğunu (dönüştürme olasılığı), zar atışının sonucuna göre (görünür durum zinciri) bilin, her seferinde ne tür zar atıldığını bilmek istiyorum (Zımni durum zinciri).
Konuşma tanıma alanındaki bu soruna kod çözme sorunu denir. Aslında bu sorunun iki çözümü var ve iki farklı cevap verilecek. Her cevap doğrudur, ancak bu cevapların anlamı farklıdır. İlk çözüm, maksimum olabilirlik durumunun yolunu bulmaktır, meslekten olmayanların terimleriyle, bir gözlem sonucu üretme olasılığı en yüksek olan bir zar dizisi buluyorum. İkinci çözüm, bir zar dizisi bulmak değil, atılan her zarın belirli bir zar olma olasılığını bulmaktır. Örneğin, sonucu gördükten sonra, D4 olasılığının ilk atış için 0,5, D6 olasılığının 0,3 ve D8 olasılığının 0,2 olduğunu bulabilirim.İlk çözüm aşağıda bahsedeceğim, ancak ikincisi Buraya bu çözüm hakkında yazmayacağım, eğer ilgileniyorsanız, bir soru daha açalım ve yazmaya devam edelim.
2) Halen zar atma sonucuna göre (görünür durum zinciri) her tür zarın ne olduğunu (geçiş olasılığı) birkaç çeşit zar olduğunu (gizli durum sayısı) biliyorum, bu sonucun olasılığını bilmek istiyorum.
Görünüşe göre bu soru çok az önem taşıyor, çünkü attığınız sonuç genellikle nispeten büyük bir olasılığa karşılık geliyor. Bu soruyu sormanın amacı, gözlemlenen sonuçların bilinen model ile tutarlı olup olmadığını kontrol etmektir. Çoğu kez sonuç nispeten küçük bir olasılığa karşılık geliyorsa, bu, bildiğimiz modelin büyük olasılıkla yanlış olduğu ve birinin gizlice zarımızı değiştirdiği anlamına gelir.
3) Birkaç çeşit zar olduğunu biliyorum (gizli durumların sayısı), her bir zarın ne olduğunu bilmiyorum (geçiş olasılığı) ve zarın birçok kez atılmasının sonucunu gözlemledim (görünür durum zinciri), her bir zar türünün ne olduğunu anlamak istiyorum ( Dönüşüm olasılığı).
Bu soru önemlidir çünkü bu en yaygın durumdur. Çoğu zaman sadece görünür sonuçlara sahibiz ve HMM modelindeki parametreleri bilmiyoruz.Bu parametreleri görünür sonuçlardan tahmin etmemiz gerekiyor Bu, modellemede gerekli bir adımdır.
Şimdi sorun ayrıntılandırıldığına göre, aşağıdaki çözümü açıklayalım. (Sayı 0 yukarıda belirtilmemiştir, yalnızca yukarıdaki sorunları çözmek için bir yardımcı olarak kullanılır)
0. Basit bir soru
Aslında, bu sorunun pratik değeri yüksek değildir. Aşağıdaki daha zor sorulara yardımcı olacağından önce burada bahsedeceğim.
Birkaç çeşit zar olduğunu, her bir zarın ne olduğunu ve her seferinde ne tür bir zar atıldığını bilerek, zar atma sonucuna göre sonucun olasılığını bulun.
Çözüm, olasılıkların çarpılmasından başka bir şey değildir:
1. Görünmez olanı görün, zar dizisini kırın
Burada maksimum olasılıklı yol problemi olan ilk çözümden bahsediyorum.
Örneğin, üç zarım, altı yüzlü zar, dört yüzlü zar ve sekiz yüzlü zarım olduğunu biliyorum. Ayrıca on atışımın sonucunu da biliyorum (16 35 27 35 24) Her seferinde ne tür zar kullandığımı bilmiyorum En olası zar sırasını bilmek istiyorum.
Aslında, en basit ve şiddetli yöntem, olası tüm zar dizilerini tüketmek ve ardından sıfırıncı sorunun çözümüne göre her diziye karşılık gelen olasılığı hesaplamaktır. Sonra en yüksek olasılığa karşılık gelen diziyi seçeriz. Markov zinciri uzun değilse, elbette mümkündür. Uzunsa, yorgunluk çok fazladır ve tamamlanması zor olacaktır.
Bilinen bir diğer algoritma ise Viterbi algoritmasıdır.Bu algoritmayı anlamak için birkaç basit örneğe bakalım.
İlk olarak, zarı yalnızca bir kez atarsak:
Sonucun 1 olduğunu görünce, karşılık gelen maksimum olasılık zar dizisi D4'tür, çünkü D4'ün 1 üretme olasılığı 1 / 6'dır, bu 1/6 ve 1 / 8'den yüksektir. Bu durumu uzatmak için zarları iki kez atarız:
Sonuç 1, 6. Şu anda problem karmaşık hale geliyor.İkinci zarın D6, D4 ve D8 olma olasılığının maksimum olduğu üç değeri hesaplamamız gerekiyor. Açıktır ki, maksimum olasılığı elde etmek için ilk kalıp D4 olmalıdır. Şu anda, ikinci zarın D6 alması için maksimum olasılık:
Benzer şekilde, ikinci kalıp D4 veya D8 olduğunda maksimum olasılığı hesaplayabiliriz. İkinci kalıbın en yüksek D6 alma olasılığına sahip olduğunu bulduk. Bu olasılığı en üst düzeye çıkarmak için ilk kalıp D4'tür. Dolayısıyla maksimum olasılık zar dizisi D4 D6'dır. Genişlemeye devam etmek için zarı üç kez atıyoruz:
Benzer şekilde, üçüncü kalıbın D6, D4 ve D8 olma olasılığını da hesaplıyoruz. Yine maksimum olasılığı elde etmek için ikinci zarın D6 olması gerektiğini bulduk. Şu anda, üçüncü zarın D4 alması için maksimum olasılık:
Yukarıdaki gibi, üçüncü kalıp D6 veya D8 olduğunda maksimum olasılığı hesaplayabiliriz. Üçüncü kalıbın en büyük D4 alma olasılığına sahip olduğunu bulduk. Bu olasılığı en üst düzeye çıkarmak için, ikinci kalıp D6 ve ilk kalıp D4'tür. Dolayısıyla maksimum olasılık zar dizisi D4 D6 D4'tür. Bu noktada herkesin bazı kalıplar görmesi gerekir. Zarların bir, iki veya üç rulosu sayılabildiğinden, aynısı mümkün olduğunca çok kez yapılabilir. En yüksek olasılıklı zar dizisine ihtiyaç duyduğumuzda bu birkaç şeyi yapmamız gerektiğini gördük. Her şeyden önce, sıra ne kadar uzun olursa olsun, sıra uzunluğu 1'den başlayın ve sıra uzunluğu 1 olduğunda her zarı alma olasılığını hesaplayın. Ardından, uzunluğu kademeli olarak artırın ve uzunluğu her artırdığınızda, her zarı bu uzunluğun altındaki son konumda alma olasılığını yeniden hesaplayın. Her zarı bir önceki uzunluğun altına almanın maksimum olasılığı hesaplandığından, onu yeniden hesaplamak zor değildir. Son basamağa kadar saydığımızda, hangi kalıbın en yüksek olasılığa sahip olduğunu biliyoruz. Ardından, bu maksimum olasılığa karşılık gelen sıralamayı arkadan öne doğru itmeliyiz.
2. Zarımı kim hareket ettirdi?
Örneğin, altı yüzlü zarınızın kumarhane tarafından hareket ettirildiğinden şüpheleniyorsanız, başka bir tür altı kenarlı zar ile değiştirilebilir Bu tür altı yüzlü zarın 1 olma olasılığı daha yüksektir ve 1 / 2'dir. 2, 3, 4, 5, 6 olasılığı 1 / 10'dur. Ne yaparsın? Cevap çok basit: Üç normal zarın bir sıra atma olasılığını hesaplayın, ardından anormal altı yüzlü zarın ve diğer iki normal zarın bu diziyi atma olasılığını hesaplayın. İlki ikinciden daha küçükse, dikkatli olmalısınız.
Örneğin, bir zar atmanın sonucu:
Bu sonucu normal üç zarla atma olasılığını hesaplamak için, aslında tüm olası durumların olasılıklarını toplamaktır. Benzer şekilde, basit ve şiddetli yöntem, tüm zar dizilerini numaralandırmak ve her zar dizisine karşılık gelen olasılığı hesaplamaktır.Ancak bu sefer, maksimum değeri seçmek yerine, hesaplanan tüm olasılıkları toplamaktayız. Toplam olasılık, ihtiyacımız olan sonuçtur. Bu yöntem hala çok uzun zar dizilerine (Markov zincirleri) uygulanamaz. Önceki sorunun maksimum olasılıkla ilgili olması ve bu sorunun olasılıkların toplamıyla ilgili olması dışında, önceki probleme benzer bir çözüm uygulayacağız. Bu sorunu çözmek için kullanılan algoritmaya ileri algoritma denir.
İlk olarak, zarı yalnızca bir kez atarsak:
Sonucun 1 olduğuna bakın. Bu sonucu üretmenin toplam olasılığı şu şekilde hesaplanabilir, toplam olasılık 0,18'dir:
Bu durumu uzatmak için zarları iki kez atıyoruz:
Sonucun 1, 6 olduğunu görünce, bu sonucu üretmenin toplam olasılığı şu şekilde hesaplanabilir ve toplam olasılık 0,05'tir:
Genişlemeye devam etmek için zarı üç kez atıyoruz:
Sonuç 1, 6, 3'tür. Bu sonucu üretmenin toplam olasılığı şu şekilde hesaplanabilir, toplam olasılık 0,03'tür:
Aynı şekilde, adım adım hesaplıyoruz ve ne kadar uzun olduğunu hesaplıyoruz ve daha uzun Markov zinciri her zaman hesaplanabiliyor. Aynı yöntemi kullanarak, anormal altı yüzlü zarın ve bu diziyi atan diğer iki normal zarın olasılığını da hesaplayabilir ve ardından kalıbınızın değiştirilip değiştirilmediğini bilmek için iki olasılığı karşılaştırabiliriz. .
Yazar: Yang Eninala
Bağlantı: https://www.zhihu.com/question/20962240/answer/33438846
Kaynak: Zhihu
