Ukryte modele Markowa: algorytm Viterbiego i nieuczciwe kasyno

Ukryty model Markowa, trzy zadania według Rabinera, algorytm w przód, algorytm Viterbiego, dekodowanie a posteriori i algorytm Bauma–Welcha — na kasynie, które od czasu do czasu potajemnie zamienia kostkę na fałszywą.

14 minut Matěj Žalmánek 2026-10-15

Seria Podstawy AI Część 39 z 52

1. Mapa sztucznej inteligencji: co jest czym i jak to do siebie pasuje
2. Krótka historia sztucznej inteligencji: od Turinga do modeli językowych
3. Dane, model, trening, inferencja: podstawowe pojęcia na jednym przykładzie
4. Jak czytać zapis matematyczny: symbole, indeksy, sumy i kwantyfikatory
5. Zbiory i relacje: klocki, z których składają się definicje w AI
6. Funkcje i odwzorowania: dlaczego każdy model AI jest funkcją
7. Logika i dowody: reguły, według których rozumuje AI
8. Grafy i drzewa: struktura, na której opierają się przeszukiwanie i sieci neuronowe
9. Algebra liniowa dla uczenia maszynowego: wektory, macierze i dlaczego AI głównie mnoży
10. Pochodne, gradient i reguła łańcuchowa: jak model ustala, w którą stronę się uczyć
11. Spadek gradientu: jak uczy się model
12. Czym jest prawdopodobieństwo: od rzutu kostką do aksjomatów Kołmogorowa
13. Prawdopodobieństwo warunkowe i twierdzenie Bayesa: jak zmienić ocenę, gdy dowiesz się czegoś nowego
14. Zmienna losowa i dystrybuanta: jedna funkcja, która mówi o rozkładzie wszystko
15. Funkcja gęstości i funkcja prawdopodobieństwa: dlaczego zmienna ciągła ma w punkcie prawdopodobieństwo zero
16. Wartość oczekiwana, wariancja i kowariancja: gdzie leży rozkład, jak jest szeroki i co z czym się wiąże
17. Przegląd rozkładów prawdopodobieństwa: Bernoulliego, dwumianowy, Poissona, jednostajny, normalny i wykładniczy
18. Prawo wielkich liczb i centralne twierdzenie graniczne: dlaczego średnie zachowują się tak przewidywalnie
19. Statystyka i estymacja parametrów: największa wiarygodność, MAP i przedziały ufności
20. Teoria informacji: entropia, entropia krzyżowa i dywergencja KL — skąd się biorą funkcje straty
21. Przeszukiwanie przestrzeni stanów: BFS, DFS, UCS i A* z animacjami
22. Gry i przeciwnik: minimax, przycinanie alfa-beta i Monte Carlo tree search
23. Spełnianie ograniczeń: backtracking, propagacja ograniczeń i AC-3 na sudoku i mapie czeskich krajów
24. Logika i systemy z bazą wiedzy: wnioskowanie w przód i wstecz, rezolucja i systemy ekspertowe
25. Planowanie: STRIPS, świat klocków, heurystyki z relaksacji i planowanie w agentach AI
26. Przeszukiwanie lokalne i symulowane wyżarzanie: komiwojażer przez czeskie miasta wojewódzkie
27. Algorytmy genetyczne: populacja, krzyżowanie, mutacja i selekcja na plecaku na wycieczkę
28. Strategie ewolucyjne i programowanie genetyczne: od reguły jednej piątej do prawa Keplera
29. Optymalizacja kolonią mrówek: jak ślad feromonowy znajduje krótką drogę
30. Optymalizacja rojem cząstek: bezwładność, własne doświadczenie i doświadczenie roju
31. Neuroewolucja: ewolucja wag i kształtu sieci neuronowych oraz algorytm NEAT
32. Zbiory rozmyte i funkcje przynależności: jak zapisać „trochę ciepło”
33. Logika rozmyta a prawdopodobieństwo: dlaczego „trochę ciepło” nie znaczy „prawdopodobnie ciepło”
34. Logika rozmyta: t-normy, implikacje i reguły JEŻELI–TO
35. Sterowanie rozmyte: Mamdani i Sugeno od wentylatora po wahadło na wózku
36. Klasteryzacja rozmyta: algorytm fuzzy c-means i punkty między skupieniami
37. Systemy neuro-rozmyte (ANFIS): reguły rozmyte, które uczą się z danych
38. Łańcuchy Markowa: macierz przejścia, rozkład stacjonarny i PageRank
39. Ukryte modele Markowa: algorytm Viterbiego i nieuczciwe kasyno
40. Sieci bayesowskie: dlaczego trawa jest mokra i co z tego wynika dla zraszacza
41. Filtr Kalmana: jak z niedokładnych pomiarów oszacować, gdzie jest samochód i jak szybko jedzie
42. Rodzaje uczenia maszynowego: nadzorowane, nienadzorowane, półnadzorowane i inne
43. Prompty, kontekst i RAG: jak dać modelowi właściwe informacje
44. Wariacyjne autoenkodery (VAE): nowe obrazki z ciągłej przestrzeni latentnej
45. Generatywne sieci przeciwstawne (GAN): fałszerz kontra detektyw
46. Modele dyfuzyjne: jak z czystego szumu powstaje obraz
47. Procesy decyzyjne Markowa: stany, akcje, nagrody i równania Bellmana
48. Q-learning i DQN: uczenie się wartości akcji od tabeli po sieć neuronową
49. Policy gradient i PPO: uczenie się bezpośrednio polityki
50. Jak działa agent AI: model językowy w pętli z narzędziami
51. Programowanie z agentami AI: zadanie, testy i kontrola
52. Ocena i bezpieczeństwo systemów AI: jak mierzyć i jak pilnować

Pełny program serii Gotowe: 52 z 83 tematów

W poprzedniej części stan łańcucha widzieliśmy: dziś świeci słońce, jutro pada. Często jednak widzimy tylko jego przejawy. Mikrofon rejestruje falę dźwiękową, a nie słowo, które ją wytworzyło. Sekwenator odczytuje litery DNA, a nie to, gdzie zaczyna się gen. A w kasynie widzimy, co wypadło, a nie to, którą kostką rzuca krupier. Ukryte modele Markowa to łańcuchy, których stanów nie widzimy — i algorytmy, którymi mimo to da się ustalić, co dzieje się w środku. Przez dziesięciolecia opierało się na nich rozpoznawanie mowy.

Nawiązuje do części Łańcuchy Markowa.

1. Nieuczciwe kasyno

Klasyczny podręcznikowy przykład (Durbin i in., 1998): krupier rzuca albo uczciwą kostką, albo fałszywą, na której szóstka wypada z prawdopodobieństwem 1/2, a pozostałe liczby z 1/10. Po każdym rzucie z prawdopodobieństwem 0,05 zamienia uczciwą na fałszywą, a z prawdopodobieństwem 0,1 fałszywą z powrotem na uczciwą. Zamiany nie widzimy. Widzimy tylko ciąg liczb — w naszym eksperymencie 300 rzutów, które zaczynają się tak:

163665521623524236522511663566613666222461626262162666626516…

Pytamy: czy gra się tu uczciwie? A jeśli nie, to kiedy dokładnie w grze była fałszywa kostka?

2. Ukryty model Markowa

Definicja — ukryty model Markowa

Ukryty model Markowa (HMM) λ = (π, A, B) ma ukryte stany 1, …, N i obserwowalne symbole 1, …, M:

• ukryte stany X₁, X₂, … tworzą łańcuch Markowa z rozkładem początkowym π i macierzą przejścia A, a_ij = P(X_t+1 = j | X_t = i);
• w każdej chwili stan X_t = i generuje obserwację O_t według prawdopodobieństw emisji b_i(o) = P(O_t = o | X_t = i), niezależnie od wszystkiego innego.

Z definicji wynika, jak prawdopodobna jest jedna konkretna „historia”: ciąg kostek x = (x₁, …, x_T) razem z rzutami O = (O₁, …, O_T).

P(x, O | λ) = π_x1 b_x1(O₁) · ∏_t=2^T a_{xt−1 xt} b_xt(O_t)

π_x1

pierwsza kostka nie ma poprzednika, z którego by się na nią przeszło — jej prawdopodobieństwo daje rozkład początkowy

a_{xt−1 xt}

każda kolejna kostka zależy tylko od poprzedniej (własność Markowa), więc na każdy krok wystarczy jedna liczba z macierzy A

b_xt(O_t)

rzut zależy tylko od kostki, którą właśnie się rzuca — bierzemy prawdopodobieństwo liczby, która naprawdę wypadła

∏_t=2^T

w ogólności mnożyłoby się prawdopodobieństwa warunkowane całą przeszłością (reguła łańcuchowa); oba założenia niezależności z definicji skracają je do tych lokalnych liczb, i dlatego całość jest zwykłym iloczynem

Przykład — dwie historie pierwszych trzech rzutów

Nasz ciąg zaczyna się rzutami 1, 6, 3. Oznaczmy przez U uczciwą, a przez F fałszywą kostkę. Historia „trzy razy fałszywa”:

P(FFF, 1, 6, 3) = 0,5 · 0,1 · 0,9 · 0,5 · 0,9 · 0,1 = 0,002025,

historia „trzy razy uczciwa”:

P(UUU, 1, 6, 3) = 0,5 · ¹/₆ · 0,95 · ¹/₆ · 0,95 · ¹/₆ = 0,002089.

Uczciwa historia wychodzi o włos bardziej prawdopodobna: szóstka na fałszywej kostce wprawdzie dostaje 0,5 zamiast ¹/₆, ale jedynka i trójka tylko 0,1 zamiast ¹/₆. (W symulacji przy tym wszystkie trzy rzuty wykonano fałszywą kostką — z trzech rzutów nie da się tego poznać).

Lawrence Rabiner w słynnym przeglądzie z 1989 roku streścił to, co można zrobić z takim modelem, w trzech zadaniach: ocena (jak prawdopodobny jest zaobserwowany ciąg?), dekodowanie (jakie ukryte stany najpewniej za nim stały?) i uczenie (jakie parametry ma model, gdy znamy tylko obserwacje?). Na każde istnieje elegancki algorytm.

3. Jak prawdopodobny jest ciąg: algorytm w przód

Prawdopodobieństwo zaobserwowanego ciągu to suma po wszystkich możliwych ciągach ukrytych stanów. Dla 300 rzutów i dwóch kostek jest ich 2³⁰⁰ ≈ 2 · 10⁹⁰ — więcej, niż jest atomów we wszechświecie. Wprost tego zsumować się nie da. Własność Markowa pozwala jednak liczyć stopniowo.

Przykład — prawdopodobieństwo trzech rzutów jako suma po wszystkich historiach

Prawdopodobieństwo obserwacji to suma prawdopodobieństwa łącznego po wszystkich możliwych historiach: P(O | λ) = ∑_x P(x, O | λ). Dla rzutów 1, 6, 3 jest ich 2³ = 8:

Historia	P(x, O)
UUU	0,002089
UUF	0,000066
UFU	0,000035
UFF	0,000188
FUU	0,000132
FUF	0,000004
FFU	0,000375
FFF	0,002025
suma	0,004913

Każda historia kosztuje 2T − 1 = 5 mnożeń, razem 8 · 5 = 40. Dla T rzutów to (2T − 1) · 2^T — przy 300 rzutach niewyobrażalnie dużo.

Algorytm — algorytm w przód

Oznaczmy α_t(j) = P(O₁, …, O_t, X_t = j). Wtedy

α₁(j) = π_j b_j(O₁),   α_t+1(j) = [∑_i α_t(i) a_ij] b_j(O_t+1),   P(O | λ) = ∑_j α_T(j).

Obliczenie trwa O(N² T) zamiast O(N^T). Żeby liczby nie uległy niedomiarowi, α_t normalizuje się w każdym kroku, a sumuje się logarytmy stałych normalizujących.

α_t+1(j) = ∑_i α_t(i) a_ij · b_j(O_t+1)

α_t(i)

wszystko, co wiemy o przeszłości: prawdopodobieństwo dotychczasowych rzutów i tego, że teraz w grze jest kostka i; w tej jednej liczbie zlane są wszystkie historie kończące się w i

a_ij

krok łańcucha z i do j; dzięki własności Markowa nie ma znaczenia, jak dotarliśmy do i

∑_i

nie wiemy, którą kostką rzucano ostatnio, a do j da się dojść z każdej — dlatego sumujemy po wszystkich możliwościach (historie są zdarzeniami wzajemnie rozłącznymi)

b_j(O_t+1)

nowy rzut musi naprawdę wygenerować kostka j; nie zależy od i, więc da się go wyciągnąć przed sumę

Przykład — algorytm w przód na rzutach 1, 6, 3

Start: α₁(U) = 0,5 · ¹/₆ = 0,0833, α₁(F) = 0,5 · 0,1 = 0,0500. Drugi rzut to szóstka:

α₂(U) = (0,0833 · 0,95 + 0,0500 · 0,1) · ¹/₆ = 0,0140,
α₂(F) = (0,0833 · 0,05 + 0,0500 · 0,9) · 0,5 = 0,0246.

t	rzut	αt(U)	αt(F)	suma = P(O1, …, Ot)	ct
1	1	0,0833	0,0500	0,133333	0,1333
2	6	0,0140	0,0246	0,038611	0,2896
3	3	0,0026	0,0023	0,004913	0,1273

Suma w ostatnim wierszu to dokładnie suma ośmiu historii z poprzedniego przykładu, tylko zamiast 40 mnożeń wystarczyło 2 + 2 · 6 = 14. Ostatnia kolumna c_t = P(O_t | O₁, …, O_t−1) to stała normalizująca ze skalowania: jak prawdopodobny był rzut t przy znanych poprzednich. Ich iloczyn to P(O | λ), więc log P(O | λ) = ∑_t log c_t.

Dlaczego logarytmy? Przy 3 000 rzutów P(O | λ) wychodzi około 10^−2 278, a najmniejsza dodatnia liczba, jaką komputer zapisze w zwykłej podwójnej precyzji (IEEE 754), to około 4,9 · 10⁻³²⁴. Bez skalowania α spadłoby do zera.

def dopredu(hody, pi, A, B):
    alfa = pi * B[:, hody[0]]
    logP = 0.0
    for t in range(len(hody)):
        if t > 0:
            alfa = (alfa @ A) * B[:, hody[t]]       # suma po i, potem emisja
        c = alfa.sum()                              # c_t = P(O_t | O_1, …, O_t−1)
        alfa = alfa / c                             # skalowanie: α_t sumuje się teraz do 1
        logP += np.log(c)
    return logP                                     # log P(O | λ)

Dla naszych 300 rzutów wychodzi P(rzuty | model kasyna) ≈ 10^−230,03. Gdyby przez cały czas grano uczciwie, prawdopodobieństwo wyniosłoby (1/6)³⁰⁰ ≈ 10^−233,45. Model z okazjonalną fałszywą kostką wyjaśnia zaobserwowane rzuty mniej więcej 2 600 razy lepiej — mocny dowód, że ktoś tu oszukuje, choć żaden pojedynczy rzut oszustwa nie zdradza.

Definicja — iloraz wiarygodności (czynnik Bayesa)

Dla dwóch modeli M₁, M₂ i danych O czynnik Bayesa to K = P(O | M₁) / P(O | M₂). Z twierdzenia Bayesa (zapisanego dla obu modeli i podzielonego) wynika:

P(M₁ | O) / P(M₂ | O) = P(O | M₁) / P(O | M₂) · P(M₁) / P(M₂)

P(M₁ | O) / P(M₂ | O)

iloraz szans po obserwacji — to, co nas interesuje: o ile bardziej wierzymy w oszustwo niż w uczciwą grę, gdy już widzieliśmy rzuty

P(O | M₁) / P(O | M₂)

czynnik Bayesa — jedyne miejsce, którym do wzoru wchodzą dane; obie wiarygodności oblicza algorytm w przód. Mianownik P(O) z twierdzenia Bayesa przy dzieleniu się skraca, dlatego nie trzeba go znać

P(M₁) / P(M₂)

iloraz szans z góry — kto z góry ufa kasynu, potrzebuje mocniejszego dowodu; dane tylko go przemnożą

Obliczenie. log₁₀ K = −230,03 − (−233,45) = 3,42 (z niezaokrąglonych wartości 3,413), czyli K ≈ 10^3,413 ≈ 2 590, w zaokrągleniu 2 600. Kto z góry uważał oszustwo i uczciwą grę za jednakowo prawdopodobne, po 300 rzutach ma szanse około 2 600 : 1 na korzyść oszustwa. Według powszechnie używanej skali Kassa i Raftery’ego (1995) czynnik Bayesa powyżej 150 to „bardzo mocny” dowód.

4. Kiedy oszukiwano: algorytm Viterbiego

Algorytm — algorytm Viterbiego (1967)

Szukamy najbardziej prawdopodobnego ciągu stanów argmax_x P(x, O | λ). Oznaczmy przez δ_t(j) prawdopodobieństwo najlepszej ścieżki, która w chwili t kończy się w stanie j:

δ₁(j) = π_j b_j(O₁),   δ_t+1(j) = max_i [δ_t(i) a_ij] · b_j(O_t+1),

a przy każdym δ_t+1(j) zapamiętaj, z którego i przyszło. Na końcu wybierz najlepszy stan i według zapamiętanych odsyłaczy idź z powrotem. Liczy się w logarytmach; czas znów wynosi O(N² T).

δ_t+1(j) = max_i δ_t(i) a_ij · b_j(O_t+1),   ψ_t+1(j) = argmax_i δ_t(i) a_ij

δ_t(i)

prawdopodobieństwo najlepszej historii, która w chwili t kończy się kostką i; gorszych historii prowadzących do i już nie potrzebujemy — gdyby najlepsza pełna ścieżka prowadziła przez i, dalej szłaby tą najlepszą

a_ij

koszt przejścia z i do j; małe a_UF = 0,05 to powód, dla którego Viterbiemu nie chce się przełączać z powodu jednej szóstki

max_i, ψ_t+1(j)

w odróżnieniu od algorytmu w przód nie sumujemy, lecz wybieramy najlepszego poprzednika — chcemy jednej ścieżki, a nie prawdopodobieństwa wszystkich; ψ pamięta, kto wygrał (na kracie bursztynowe strzałki), żeby ścieżkę dało się na końcu odtworzyć wstecz

b_j(O_t+1)

jak dobrze kostka j wyjaśnia nowy rzut — tak samo jak przy α

Na dwunastu rzutach widać, jak Viterbi podejmuje decyzję. Pierwsze sześć rzutów (5, 2, 2, 5, 1, 1) wygląda uczciwie. Potem wypadają dwie szóstki z rzędu i kolejne dwie kawałek dalej — i najlepsza ścieżka przełącza się na fałszywą kostkę. W rzeczywistości krupier wymienił kostkę dopiero cztery rzuty później; dwie szóstki z rzędu wypadają też na uczciwej kostce.

Przykład — Viterbi krok po kroku na rzutach 1, 6, 3

Start jest taki sam jak dla α: δ₁(U) = 0,0833, δ₁(F) = 0,0500. Dla szóstki w drugim rzucie:

δ₂(U) = max(0,0833 · 0,95; 0,0500 · 0,1) · ¹/₆ = 0,0792 · ¹/₆ = 0,0132   (wygrało U),
δ₂(F) = max(0,0833 · 0,05; 0,0500 · 0,9) · 0,5 = 0,0450 · 0,5 = 0,0225   (wygrało F).

t	rzut	δt(U)	ψt(U)	δt(F)	ψt(F)
1	1	0,083333	—	0,050000	—
2	6	0,013194	U	0,022500	F
3	3	0,002089	U	0,002025	F

Na końcu wygrywa U (0,002089 > 0,002025) i wstecz po odsyłaczach ψ wychodzi ścieżka UUU — dokładnie ta historia z pierwszego przykładu, która była najbardziej prawdopodobna ze wszystkich ośmiu. Algorytm w przód daje jednak dla trzeciego rzutu P(F | O₁, O₂, O₃) = 0,002283 / 0,004913 = 0,465. Najlepsza ścieżka i najbardziej prawdopodobny stan są tu zgodne (U), ale „zwycięstwo” jest nieznaczne, a trzy rzuty nie wystarczą do pewności. W ogólności zgodne być nie muszą — wrócimy do tego przy dekodowaniu a posteriori.

import numpy as np

def viterbi(hody, pi, A, B):
    T, N = len(hody), len(pi)
    delta = np.log(pi) + np.log(B[:, hody[0]])
    odkud = np.zeros((T, N), dtype=int)
    for t in range(1, T):
        kandidati = delta[:, None] + np.log(A)       # z każdego i do każdego j
        odkud[t] = kandidati.argmax(axis=0)
        delta = kandidati.max(axis=0) + np.log(B[:, hody[t]])
    cesta = [int(delta.argmax())]
    for t in range(T - 1, 0, -1):                     # wstecz po zwycięskich odsyłaczach
        cesta.append(odkud[t][cesta[-1]])
    return cesta[::-1]

5. Wszystkie 300 rzutów

Fałszywa kostka była w grze 88 razy, w dziewięciu odcinkach. Viterbi oznaczył jako fałszywe 62 rzuty, z czego 56 poprawnie, i łącznie poprawnie określił kostkę dla 87,3 % rzutów. Długie odcinki oszustwa znalazł, krótkie jednak przeoczył albo zlał ze sobą — zamiast dziewięciu odcinków widzi dwa. Na krótkim odcinku po prostu nie wypada dość szóstek, żeby opłacała się „droga” zamiana kostki (prawdopodobieństwo zamiany to tylko 0,05).

Definicja — prawdopodobieństwo a posteriori stanu

Algorytm w przód i wstecz oblicza dodatkowo β_t(i) = P(O_t+1, …, O_T | X_t = i) od końca i z obu dostaje γ_t(i) = P(X_t = i | O) ∝ α_t(i) β_t(i).

γ_t(i) = α_t(i) · β_t(i) / P(O | λ),   β_t(i) = ∑_j a_ij b_j(O_t+1) β_t+1(j),   β_T(i) = 1

γ_t(i)

prawdopodobieństwo, że w chwili t w grze była kostka i, gdy znamy wszystkie rzuty — dla fałszywej kostki to czerwona krzywa na obrazku

α_t(i)

dowody z przeszłości: rzuty od 1 do t i stan i w chwili t

β_t(i)

dowody z przyszłości: jak dobrze stan i wyjaśnia rzuty od t + 1 do T. Liczy się od końca tym samym trikiem co α — jeden krok łańcucha, emisja, reszta przyszłości. Mnożyć α i β wolno nam, bo przy znanym stanie X_t przeszłe i przyszłe rzuty są niezależne

P(O | λ)

iloczyn α·β to prawdopodobieństwo łączne P(X_t = i, O); dzieląc przez prawdopodobieństwo wszystkich rzutów, robimy z niego warunkowe. To ta sama liczba, którą dał algorytm w przód, i w każdym t zachodzi ∑_i α_t(i) β_t(i) = P(O | λ)

Przykład — drugi rzut: co dodaje przyszłość

Zostańmy przy rzutach 1, 6, 3 i zapytajmy o drugi rzut (szóstkę). Krok wstecz od β₃ = 1 z trzecim rzutem (trójką):

β₂(U) = 0,95 · ¹/₆ + 0,05 · 0,1 = 0,1633,   β₂(F) = 0,1 · ¹/₆ + 0,9 · 0,1 = 0,1067.

γ₂(F) = 0,024583 · 0,106667 / 0,004913 = 0,534.

Gdybyśmy znali tylko pierwsze dwa rzuty, byłoby P(F | O₁, O₂) = α₂(F) / (α₂(U) + α₂(F)) = 0,637. Trójka, która wypadła potem, jest na fałszywej kostce mniej prawdopodobna, więc wstecznie obniża podejrzenie co do drugiego rzutu do 0,534.

Definicja — dekodowanie a posteriori i dokładność

Dekodowanie a posteriori wybiera w każdej chwili osobno x̂_t = argmax_i γ_t(i). Dokładność dekodowania x̂ względem prawdziwych stanów x to odsetek zgodności (1/T) ∑_t [x̂_t = x_t], gdzie [·] wynosi 1, gdy stwierdzenie jest prawdziwe, w przeciwnym razie 0.

Dekodowanie a posteriori maksymalizuje oczekiwaną liczbę poprawnie określonych rzutów, Viterbi prawdopodobieństwo, że poprawna jest cała ścieżka naraz. Dlatego ciąg a posteriori może zawierać nawet przejście, które ma w modelu prawdopodobieństwo zero — w kasynie takiego nie ma, ale w ogólności może się to zdarzyć.

Gdybyśmy przy każdym rzucie wybrali kostkę z większym prawdopodobieństwem a posteriori, trafilibyśmy w 87,7 % — o włos więcej niż Viterbi (263 rzuty z 300 wobec 262, różnica jednego rzutu). (Viterbi szuka najlepszej całej ścieżki, dekodowanie a posteriori najlepszego oszacowania każdego rzutu osobno; to nie to samo). I uwaga na pojedynczą symulację: w dwunastu różnych eksperymentach dokładność algorytmu Viterbiego wahała się od 73,3 do 90,0 %, średnio 83,4 %. Zależnie od tego, jak długie odcinki oszustwa wytworzy przypadek.

6. Uczenie: algorytm Bauma–Welcha

Do tej pory parametry kasyna znaliśmy. Co, jeśli wiemy tylko tyle, że kostki są dwie, a wszystko inne trzeba wyczytać z rzutów?

Algorytm — algorytm Bauma–Welcha

To algorytm EM (Baum i in., około 1970 roku). Powtarzaj:

1. krok E: przy bieżących parametrach oblicz algorytmem w przód i wstecz γ_t(i) oraz oczekiwane liczby przejść ξ_t(i, j) = P(X_t = i, X_t+1 = j | O);
2. krok M: nowe a_ij = ∑_t ξ_t(i, j) / ∑_t γ_t(i), nowe b_i(o) = udział γ w chwilach, gdy wypadło o.

Wiarygodność P(O | λ) w żadnej iteracji nie maleje; algorytm zbiega do maksimum lokalnego.

Oczekiwaną liczbę przejść oblicza się z tych samych α i β co γ, tylko wstawia się między nie jeden krok łańcucha:

ξ_t(i, j) = α_t(i) a_ij b_j(O_t+1) β_t+1(j) / P(O | λ)

α_t(i)

rzuty do chwili t i kostka i w chwili t — lewy koniec przejścia

a_ij

samo przejście i → j, którego częstość szacujemy

b_j(O_t+1)

rzut t + 1 musi wygenerować nowa kostka j

β_t+1(j)

reszta rzutów od t + 2 dalej, wyjaśniona z kostki j — prawy koniec przejścia

P(O | λ)

dzieląc, robimy z łącznego prawdopodobieństwa „przejście i wszystkie rzuty” warunkowe „przejście, gdy znamy rzuty”

â_ij = ∑_t=1^T−1 ξ_t(i, j) / ∑_t=1^T−1 γ_t(i)

â_ij

nowe oszacowanie prawdopodobieństwa przejścia — częstość względna, jakbyśmy liczyli kreski

∑ ξ_t(i, j)

oczekiwana liczba przejść i → j; zamiast „przeszło się albo nie” (1 lub 0) sumujemy prawdopodobieństwa, bo stanów nie widzimy

∑ γ_t(i)

oczekiwana liczba wyjść ze stanu i; sumuje się tylko do T − 1, bo z ostatniego stanu żadne przejście już nie prowadzi. Dzięki temu wiersz nowej macierzy sumuje się do 1

powtarzaj (u nas 100 razy):
    α, β, P(O) ← algorytm w przód i wstecz z bieżącymi π, A, B
    # krok E: miękkie liczności
    dla każdego t, i:         γ[t][i]    ← α[t][i] · β[t][i] / P(O)
    dla każdego t < T, i, j:  ξ[t][i][j] ← α[t][i] · a[i][j] · b[j](O[t+1]) · β[t+1][j] / P(O)
    # krok M: częstości względne
    π[i]    ← γ[1][i]
    a[i][j] ← ∑_{t<T} ξ[t][i][j] / ∑_{t<T} γ[t][i]
    b[i](o) ← ∑_{t: O[t]=o} γ[t][i] / ∑_t γ[t][i]

Zaczęliśmy od złego oszacowania: kostki prawie się nie różnią i wymieniają się często. Z 300 rzutów algorytm Bauma–Welcha doszedł do modelu, który kostek prawie wcale nie wymienia, a fałszywej kostce daje szóstkę tylko z prawdopodobieństwem 0,39 — do wiarygodnego oszacowania 300 rzutów to za mało. Z 3 000 rzutów (innej symulacji tego samego kasyna) wyszło już bardzo blisko prawdy:

Dlaczego 300 rzutów nie wystarcza, pokazuje wiarygodność. W ciągu 100 iteracji na naszych 300 rzutach wzrosła z 10^−231,26 do 10^−227,14 — a to więcej niż 10^−230,03 prawdziwego modelu kasyna. Wyuczony model wyjaśnia więc właśnie te rzuty lepiej niż prawda: dopasował się nawet do przypadkowych wahań konkretnych danych. Estymator największej wiarygodności zbliża się do prawdy dopiero wraz z przybywaniem danych.

7. Ukryte modele Markowa w praktyce

• Rozpoznawanie mowy. Od lat osiemdziesiątych do nadejścia głębokich sieci około 2010 roku niemal wszystkie systemy opierały się na HMM: ukryte stany to części głosek, obserwacje to krótkie fragmenty widma dźwięku, a Viterbi szuka najbardziej prawdopodobnego ciągu słów.
• Język. Rozpoznawanie części mowy: ukryty stan to część mowy, obserwacja to słowo. „Piec” może być rzeczownikiem albo czasownikiem — rozstrzyga kontekst.
• Bioinformatyka. Szukanie genów w DNA (odcinki kodujące i niekodujące to ukryte stany) albo profilowe HMM dla rodzin białek w bazie Pfam.
• Stany ciągłe. Gdy ukryty stan to nie „kostka A albo B”, lecz położenie i prędkość, zamiast HMM używa się filtru Kalmana — ma w programie własną część.

8. Podsumowanie

• Ukryty model Markowa to łańcuch Markowa ukrytych stanów, z których widzimy tylko emisje; wyznaczają go π, A i B.
• Algorytm w przód oblicza prawdopodobieństwo obserwacji w czasie O(N²T) zamiast sumy po 2³⁰⁰ ścieżkach; kasyno z oszustwem wyjaśnia nasze rzuty mniej więcej 2 600 razy lepiej niż uczciwa gra.
• Algorytm Viterbiego znajduje najbardziej prawdopodobną ścieżkę ukrytych stanów programowaniem dynamicznym — w naszej symulacji poprawnie określił kostkę dla 87,3 % rzutów, krótkie odcinki jednak przeoczył.
• Algorytm w przód i wstecz daje prawdopodobieństwo a posteriori stanu w każdej chwili.
• Algorytm Bauma–Welcha uczy się parametrów tylko z obserwacji — ale potrzebuje dość danych: 300 rzutów nie wystarczyło, 3 000 tak.

Chcesz to wypróbować? Niech agent AI nauczy HMM z dwoma stanami na dziennych stopach zwrotu indeksu giełdowego — i sprawdź, czy sam znajdzie „spokojne” i „burzliwe” okresy na rynku.

Masz inne zdanie? Napisz na support@coden-app.com.