Viterbi-algoritmus

• IPA:

Viterbi-algoritmus

1. (matematika)

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.

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: ${\displaystyle 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: ${\displaystyle P(o_{t}|s_{t}=s_{j})}$.
• **Kezdeti valószínűségek** (\(\pi\)): Az állapotok kezdeti eloszlása: ${\displaystyle P(s_{1}=s_{i})}$.

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

1. Inicializáció:

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

1. Rekurzió:

  A maximális valószínűségi úton keresztüli értékek kiszámítása időben haladva:
  $${\displaystyle \delta _{t}(j)=\max _{i}\left\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\).

1. Nyomkövetés (traceback):

  Egy külön nyomkövetési mátrix (\(\psi_t(j)\)) tárolja az optimális előző állapotokat:
  $${\displaystyle \psi _{t}(j)=\arg \max _{i}\left}$$

1. Visszavezetés:

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

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

• **Állapotok**: \(S = \{\text{Sunny, Rainy}\}\)
• **Megfigyelések**: \(O = \)
• **Kezdeti valószínűségek**:

  $${\displaystyle \pi =}$$

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

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

• **Megfigyelési mátrix**:

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

A legvalószínűbb állapotsorozat: \(\)

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 = start_prob * emit_prob]
        psi = 0

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

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

    return path

# Példa használat
states = 
observations =   # Megfigyelések: 
start_prob = 
trans_prob = , ]
emit_prob = , ]

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

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

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

• **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.

• 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)