Viterbi-algoritmus

Magyar

Kiejtés

IPA: [ ˈvitɛrbiɒlɡoritmuʃ]

Főnév

(matematika)

Viterbi-algoritmus

A **Viterbi-algoritmus** egy dinamikus programozási módszer, amelyet leggyakrabban rejtett Markov-modell (HMM) esetén alkalmaznak a legvalószínűbb állapotsorozat meghatározására. Az algoritmus hatékonyan találja meg a maximális valószínűségű úton alapuló megoldást, és széles körben használják olyan területeken, mint például a természetes nyelvfeldolgozás, beszédfelismerés és bioinformatika.

Probléma

Egy **rejtett Markov-modellben** adott:

**Állapotok** ($S$): A rendszer állapotainak halmaza ($s_1, s_2, \ldots, s_n$).
**Megfigyelések** ($O$): Egy megfigyelés-sorozat ($o_1, o_2, \ldots, o_T$).
**Állapotátmeneti valószínűségek** ($A$): Az $a_{ij}$ valószínűség, hogy $s_i$ állapotból $s_j$-be lépünk: $P(s_{t}=s_{j}|s_{t-1}=s_{i})$ .
**Megfigyelési valószínűségek** ($B$): Az $b_j(o_t)$ valószínűség, hogy az $o_t$ megfigyelést látjuk az $s_j$ állapotban: $P(o_{t}|s_{t}=s_{j})$ .
**Kezdeti valószínűségek** ($\pi$): Az állapotok kezdeti eloszlása: $P(s_{1}=s_{i})$ .

Feladat: Találjuk meg a legvalószínűbb állapotsorozatot ($S^*$), amely maximalizálja $P(S | O)$-t.

Működése

Inicializáció:

  A kezdő állapotok valószínűségének kiszámítása:
   $\delta _{1}(i)=\pi _{i}\cdot b_{i}(o_{1})$

Rekurzió:

  A maximális valószínűségi úton keresztüli értékek kiszámítása időben haladva:
   $\delta _{t}(j)=\max _{i}\left[\delta _{t-1}(i)\cdot a_{ij}\right]\cdot b_{j}(o_{t})$ 
  Ahol \(\delta_t(j)\) a maximális valószínűség, hogy a \(t\)-edik időpillanatban az állapot \(s_j\).

Nyomkövetés (traceback):

  Egy külön nyomkövetési mátrix (\(\psi_t(j)\)) tárolja az optimális előző állapotokat:
   $\psi _{t}(j)=\arg \max _{i}\left[\delta _{t-1}(i)\cdot a_{ij}\right]$

Visszavezetés:

  Az utolsó időpillanatból indulva követjük az állapotok sorozatát az optimális útvonal mentén.

Pszeudokód

VITERBI(O, S, π, A, B):
  1. Inicializáció:
     for j in S:
       δ[1][j] = π[j] * B[j][O[1]]
       ψ[1][j] = 0
  2. Rekurzió:
     for t = 2 to T:
       for j in S:
         δ[t][j] = max(δ[t-1][i] * A[i][j]) * B[j][O[t]]
         ψ[t][j] = argmax(δ[t-1][i] * A[i][j])
  3. Visszavezetés:
     S_T = argmax(δ[T][j])
     for t = T-1 to 1:
       S_t = ψ[t+1][S_t+1]
  4. return (S_1, S_2, ..., S_T)

Példa

Bemenet

**Állapotok**: $S = \{\text{Sunny, Rainy}\}$
**Megfigyelések**: $O = [\text{Dry, Wet, Dry}]$
**Kezdeti valószínűségek**:

   $\pi =[0.6,0.4]$

**Állapotátmeneti mátrix**:

   $A={\begin{bmatrix}0.7&0.3\\0.4&0.6\end{bmatrix}}$

**Megfigyelési mátrix**:

   $B={\begin{bmatrix}0.9&0.1\\0.2&0.8\end{bmatrix}}$

Kimenet

A legvalószínűbb állapotsorozat: $[ \text{Sunny, Rainy, Sunny} ]$

Python implementáció

import numpy as np

def viterbi(observations, states, start_prob, trans_prob, emit_prob):
    T = len(observations)  # Megfigyelések hossza
    N = len(states)        # Állapotok száma

    # Inicializáció
    delta = np.zeros((T, N))
    psi = np.zeros((T, N), dtype=int)
    path = np.zeros(T, dtype=int)

    # Kezdeti lépés
    for j in range(N):
        delta[0][j] = start_prob[j] * emit_prob[j][observations[0]]
        psi[0][j] = 0

    # Rekurzió
    for t in range(1, T):
        for j in range(N):
            probabilities = [delta[t-1][i] * trans_prob[i][j] for i in range(N)]
            delta[t][j] = max(probabilities) * emit_prob[j][observations[t]]
            psi[t][j] = np.argmax(probabilities)

    # Nyomkövetés
    path[T-1] = np.argmax(delta[T-1])
    for t in range(T-2, -1, -1):
        path[t] = psi[t+1][path[t+1]]

    return path

# Példa használat
states = ['Sunny', 'Rainy']
observations = [0, 1, 0]  # Megfigyelések: [Dry, Wet, Dry]
start_prob = [0.6, 0.4]
trans_prob = [[0.7, 0.3], [0.4, 0.6]]
emit_prob = [[0.9, 0.1], [0.2, 0.8]]

# Legvalószínűbb állapotsorozat
state_path = viterbi(observations, states, start_prob, trans_prob, emit_prob)
print("Legvalószínűbb állapotsorozat:", [states[s] for s in state_path])

Előnyök

**Pontosság**: Garantáltan megtalálja a legvalószínűbb állapotsorozatot.
**Hatékonyság**: Az algoritmus $O(T\cdot N^{2})$ időbonyolultságú, ahol $T$ a megfigyelések száma, $N$ pedig az állapotok száma.

Hátrányok

**Méretkorlát**: Nagy állapot- vagy megfigyelési halmaz esetén magas memóriaigény.
**HMM-feltételek**: Csak Markov-feltételeket kielégítő rendszerekben alkalmazható.

Alkalmazások

**Beszédfelismerés**: Hangokhoz tartozó szavak felismerése.
**Természetes nyelvfeldolgozás**: Szófajok elemzése (POS tagging).
**Bioinformatika**: Génsorozatok elemzése és összehasonlítása.

Fordítások

Tartalom

angol: Viterbi algorithm (en)

További információk

Viterbi-algoritmus - Értelmező szótár (MEK)
Viterbi-algoritmus - Etimológiai szótár (UMIL)
Viterbi-algoritmus - Szótár.net (hu-hu)
Viterbi-algoritmus - DeepL (hu-de)
Viterbi-algoritmus - Яндекс (hu-ru)
Viterbi-algoritmus - Google (hu-en)
Viterbi-algoritmus - Helyesírási szótár (MTA)
Viterbi-algoritmus - Wikidata
Viterbi-algoritmus - Wikipédia (magyar)