পাঠ ৩৮ · ৪৫-এর মধ্যে · মডিউল ৫

Home / AI Courses / Machine Learning / Viterbi & Baum-Welch

Viterbi ও Baum-Welch

Viterbi decoding & Baum-Welch training

৮ মিনিট পড়া উচ্চ · Advanced NumPy / hmmlearn

এই পাঠে যা শিখবেন

Viterbi algorithm — argmax dynamic programming
Forward-backward — likelihood ও smoothing
Baum-Welch — full EM iteration
Underflow problem — log-space ও scaling
scratch implementation NumPy-তে; production-এ hmmlearn

১ · Viterbi — most likely state sequence

L37-এ আমরা Forward algorithm দেখেছি — $P(\mathbf{o} \mid \lambda)$ compute। কিন্তু decoding problem ভিন্ন — observation sequence given, কোন state sequence সবচেয়ে likely?

Naive approach: $N^T$ state sequence enumerate — exponential, infeasible।

Andrew Viterbi (১৯৬৭) — DP দিয়ে $O(N^2 T)$।

Define $\delta_t(i) = \max_{s_1, \ldots, s_{t-1}} P(s_1, \ldots, s_{t-1}, s_t = i, o_1, \ldots, o_t \mid \lambda)$ — সবচেয়ে likely path যা $t$-তে state $i$-তে এসে শেষ।

Recurrence:

$$\delta_1(i) = \pi_i \cdot b_i(o_1)$$

$$\delta_{t+1}(j) = \max_i \left[ \delta_t(i) \cdot a_{ij} \right] \cdot b_j(o_{t+1})$$

Forward-এ sum ছিল, Viterbi-তে max। সাথে backpointer $\psi_t(j) = \arg\max_i [\delta_{t-1}(i) a_{ij}]$ — কোথা থেকে এলো।

Final: $s_T^* = \arg\max_i \delta_T(i)$, তারপর backtrace via $\psi$।

২ · Backward algorithm

Forward — past evidence থেকে current state-এর probability। Backward — future evidence থেকে।

$\beta_t(i) = P(o_{t+1}, \ldots, o_T \mid s_t = i, \lambda)$ — state $i$ থেকে শেষ পর্যন্ত observation-এর probability।

Recurrence:

$$\beta_T(i) = 1$$

$$\beta_t(i) = \sum_j a_{ij} \cdot b_j(o_{t+1}) \cdot \beta_{t+1}(j)$$

Forward-Backward together:

$$P(s_t = i \mid \mathbf{o}, \lambda) = \frac{\alpha_t(i) \beta_t(i)}{P(\mathbf{o} \mid \lambda)}$$

একে বলে $\gamma_t(i)$ — smoothed posterior — past + future evidence ব্যবহার করে state-এর probability।

৩ · Baum-Welch — parameter learning

Lloyd Baum, George Welch (১৯৭০) — HMM parameter MLE-এর iterative algorithm। আসলে — EM-এর (Dempster-Laird-Rubin, ১৯৭৭) HMM-specific instance, EM-এর আগে আবিষ্কৃত!

Initialize: random $\lambda^{(0)} = (\boldsymbol{\pi}, \mathbf{A}, \mathbf{B})$।

Repeat until convergence:

E-step: Forward $\alpha$, Backward $\beta$ compute। Then:

$$\gamma_t(i) = \frac{\alpha_t(i) \beta_t(i)}{\sum_k \alpha_t(k) \beta_t(k)}$$

$$\xi_t(i, j) = \frac{\alpha_t(i) a_{ij} b_j(o_{t+1}) \beta_{t+1}(j)}{P(\mathbf{o} \mid \lambda)}$$

$\gamma_t(i)$ = state $i$-এ থাকার probability at time $t$। $\xi_t(i,j)$ = transition $i \to j$ at time $t$।

M-step:

$$\pi_i^{\text{new}} = \gamma_1(i)$$

$$a_{ij}^{\text{new}} = \frac{\sum_{t=1}^{T-1} \xi_t(i, j)}{\sum_{t=1}^{T-1} \gamma_t(i)}$$

$$b_i(v_k)^{\text{new}} = \frac{\sum_{t : o_t = v_k} \gamma_t(i)}{\sum_{t=1}^T \gamma_t(i)}$$

Likelihood প্রতি iteration-এ monotonically increases (EM property)। Local optimum-এ converge — global guarantee নেই।

৪ · Underflow ও log-space

Probability multiply continuously — $T$ বড় হলে $0$-এ vanish। দু'টি সমাধান:

Log-space: $\log \alpha$ store, multiplication → addition। Sum-এ logsumexp trick।
Scaling: প্রতি step-এ $\alpha_t$ normalize, scaling factor track।

Production library-গুলোতে এটা built-in — শুধু interface clean থাকে।

৫ · উদাহরণ — Viterbi run

L37-এর Sprinkler-like example। Observation: Umbrella, Sunglasses, Umbrella।

States: Sunny (0), Rainy (1)।
$\pi = (0.6, 0.4)$।
$\mathbf{A} = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix}$।
$\mathbf{B}$: Sunny → (Umbrella ০.১, Sunglasses ০.৭, Raincoat ০.২); Rainy → (০.৬, ০.১, ০.৩)।

Viterbi run করলে most-likely sequence — (Rainy, Sunny, Rainy)। Umbrella → Rainy বেশি likely; middle Sunglasses → Sunny; final Umbrella → Rainy।

Viterbi trellis — প্রতিটি (state, time) node-এ best score $\delta$। Edge-এর সবচেয়ে best ধরে রাখি (ψ backpointer)। Final-এ argmax → backtrace।

৬ · NumPy scratch — Viterbi

Python · NumPy

import numpy as np

def viterbi(obs, A, B, pi):
    T, N = len(obs), len(pi)
    # log-space — underflow-প্রতিরোধী
    logA, logB, logpi = np.log(A + 1e-300), np.log(B + 1e-300), np.log(pi + 1e-300)

    delta = np.zeros((T, N))
    psi   = np.zeros((T, N), dtype=int)

    delta[0] = logpi + logB[:, obs[0]]

    for t in range(1, T):
        # delta_{t-1}[:, None] + logA — broadcasting
        scores = delta[t-1, :, None] + logA   # shape (N, N)
        delta[t] = scores.max(axis=0) + logB[:, obs[t]]
        psi[t]   = scores.argmax(axis=0)

    # backtrace
    path = np.zeros(T, dtype=int)
    path[-1] = delta[-1].argmax()
    for t in range(T-2, -1, -1):
        path[t] = psi[t+1, path[t+1]]

    return path, delta[-1].max()

# Sprinkler example
A  = np.array([[0.7, 0.3], [0.4, 0.6]])
B  = np.array([[0.1, 0.7, 0.2],   # Sunny
               [0.6, 0.1, 0.3]])  # Rainy
pi = np.array([0.6, 0.4])
obs = [0, 1, 0]   # Umbrella, Sunglasses, Umbrella

path, log_p = viterbi(obs, A, B, pi)
states = ["Sunny", "Rainy"]
print("Best path:", " → ".join(states[s] for s in path))
print(f"Log-probability: {log_p:.4f}")

Viterbi log-space-এ একটি practical implementation। Production-grade hmmlearn এই pattern-ই ব্যবহার করে — কিন্তু C-extension দিয়ে দ্রুত।

৭ · Baum-Welch — full iteration

Python · NumPy (sketch)

def baum_welch(obs, N, M, n_iter=20):
    T = len(obs)
    # init random
    pi = np.random.dirichlet(np.ones(N))
    A  = np.random.dirichlet(np.ones(N), size=N)
    B  = np.random.dirichlet(np.ones(M), size=N)

    for it in range(n_iter):
        # forward
        alpha = np.zeros((T, N))
        alpha[0] = pi * B[:, obs[0]]
        for t in range(1, T):
            alpha[t] = (alpha[t-1] @ A) * B[:, obs[t]]

        # backward
        beta = np.zeros((T, N))
        beta[-1] = 1.0
        for t in range(T-2, -1, -1):
            beta[t] = A @ (B[:, obs[t+1]] * beta[t+1])

        # E-step: gamma, xi
        gamma = alpha * beta
        gamma /= gamma.sum(axis=1, keepdims=True)

        xi = np.zeros((T-1, N, N))
        for t in range(T-1):
            num = alpha[t, :, None] * A * B[:, obs[t+1]] * beta[t+1]
            xi[t] = num / num.sum()

        # M-step
        pi = gamma[0]
        A  = xi.sum(axis=0) / gamma[:-1].sum(axis=0)[:, None]
        for k in range(M):
            mask = (np.array(obs) == k)
            B[:, k] = gamma[mask].sum(axis=0) / gamma.sum(axis=0)

    return pi, A, B

# Toy run
np.random.seed(0)
obs = [0, 1, 0, 1, 0, 0, 1, 1, 0, 1]
pi, A, B = baum_welch(obs, N=2, M=2, n_iter=10)
print("Learned π:", pi.round(3))
print("Learned A:\n", A.round(3))
print("Learned B:\n", B.round(3))

Baum-Welch — random init থেকে data-fit parameter। Log-likelihood প্রতি iteration বাড়ে। Production-এ scaling/log-space, multiple init, convergence check — সব hmmlearn-এ built-in।

৮ · hmmlearn-এ production usage

Python · hmmlearn

from hmmlearn import hmm
import numpy as np

# Synthetic: two-regime time series
np.random.seed(0)
X = np.concatenate([
    np.random.normal(0, 1, 500),
    np.random.normal(3, 0.5, 500),
    np.random.normal(0, 1, 500),
]).reshape(-1, 1)

model = hmm.GaussianHMM(n_components=2, n_iter=50, tol=1e-4,
                        covariance_type="full", random_state=0)
model.fit(X)

# Decoding (Viterbi)
states = model.predict(X)
print(f"State 0 mean: {model.means_[0, 0]:.2f}")
print(f"State 1 mean: {model.means_[1, 0]:.2f}")
print(f"Score (log-likelihood): {model.score(X):.2f}")
print(f"State sequence first 30: {states[:30]}")

fit() = Baum-Welch। predict() = Viterbi। score() = forward log-likelihood। তিন core problem one API।

৯ · Convergence ও local optima

Baum-Welch monotonic likelihood — কিন্তু global maximum নয়।
Multiple random init essential — best likelihood বাছুন।
K-Means initialization (Gaussian HMM) ভাল।
Convergence criterion: $|\log L^{(it+1)} - \log L^{(it)}| < \epsilon$।
Typically ৫০-১০০ iteration যথেষ্ট।

Baum-Welch overfit করতে পারে — particularly $N$ বড় হলে। Regularization (Dirichlet prior) বা cross-validated $N$ বাছাই অপরিহার্য। Pure MLE often disappointing in production।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ Viterbi (max) বনাম Forward (sum) — কেন decoding-এ max, likelihood-এ sum?

চমৎকার subtle question। Same DP structure, ভিন্ন operator।

Forward (sum):

$P(\mathbf{o} \mid \lambda) = \sum_{\mathbf{s}} P(\mathbf{o}, \mathbf{s} \mid \lambda)$।
সব state sequence-এর joint probability sum।
"Total likelihood" — কোনো sequence specific নয়।
Use: model comparison, training likelihood।

Viterbi (max):

$\mathbf{s}^* = \arg\max_{\mathbf{s}} P(\mathbf{o}, \mathbf{s} \mid \lambda)$।
Single best sequence-এর probability।
"Best explanation"।
Use: decoding, sequence labeling।

Mathematical analogy:

Forward: probability semiring (+, ×)।
Viterbi: tropical/max-product semiring (max, ×) — log-space (max, +)।
একই algorithm পরিবর্তিত operator।

উদাহরণ:

Two paths to current state — sum probability ০.১ + ০.১৫ = ০.২৫।
Max — ০.১৫।
Forward "any way" likelihood; Viterbi "best way"।

POS tagging example:

"Time flies" — multiple tag sequence possible।
Viterbi: best single sequence, e.g., (N V)।
Forward sum: total likelihood across all sequence।
(N V) more likely than (V N) — Viterbi picks (N V)।

Marginal vs MAP:

Marginal: $P(s_t = i \mid \mathbf{o})$ — forward-backward।
MAP: $\arg\max_{s_t} P(s_t = i \mid \mathbf{o})$ each $t$ independently।
Viterbi: joint MAP — full sequence consistent।

Key insight:

"Per-step MAP" can give inconsistent sequence (transition impossible)।
Viterbi guarantees valid path।
POS tagging — Viterbi standard।

Speech recognition:

Acoustic decoding — best phoneme sequence — Viterbi।
Beam search — Viterbi-এর approximation, top-$k$ paths।

Beyond Viterbi:

$N$-best — top $N$ sequence।
A* — heuristic search।
Posterior decoding — marginal-based, sometimes better accuracy।

মূল উপলব্ধি: Forward "all paths sum"; Viterbi "best path max"। DP framework-এ operator switch — beautiful, একই code-এ implementation।

প্র ০২ Baum-Welch local optima trap — কীভাবে এড়াবেন? Modern alternatives কী?

Practical Baum-Welch-এর সবচেয়ে বড় challenge। সমাধান বহুমাত্রিক।

(১) Multiple random initialization:

১০-২০ different random seed।
Best likelihood-এর model বাছাই।
Standard practice।

(২) Smart initialization:

K-Means clustering: Gaussian HMM-এ — emission mean from cluster centroid।
Hard EM: Viterbi-based hard assignment first, then soft EM।
Domain prior: known transition pattern initialize।

(৩) Annealing:

Deterministic annealing — temperature parameter।
High temperature → smooth posterior।
Gradually cool।
Avoid sharp local minima।

(৪) Bayesian:

Prior on parameters।
Variational Bayes EM — better convergence।
Gibbs sampling (MCMC) — explore posterior।

(৫) Spectral algorithm:

Hsu-Kakade-Zhang (২০১২) — non-iterative, moment-based।
Closed-form solution।
No local optima।
Limited to certain HMMs।

(৬) Discriminative training:

If labeled state available — supervised।
Maximum mutual information (MMI)।
Better task accuracy।

(৭) Model averaging:

Ensemble of HMMs from different inits।
Predict by averaging posterior।
Robust।

Modern alternatives:

Neural HMM: emission model neural — backprop end-to-end।
Variational autoencoder: probabilistic latent।
Hidden semi-Markov: duration explicit।
State-space model: continuous latent।
Transformer: attention replaces Markov।

Implementation tips:

Track likelihood per iteration — drop = bug।
Convergence: relative change < 1e-4।
Max iteration cap।
Numerical stability — log-space আবশ্যিক।

Practical best practice:

K-Means init for emission।
Uniform initial transition।
Run ১০ different seed।
Best likelihood-এর model deploy।
Validation set agreement check।

মূল উপলব্ধি: Baum-Welch elegant but unreliable single-shot। Ensemble + smart init + validation = production-grade। Modern work neural model + small HMM hybrid।

প্র ০৩ Viterbi সবচেয়ে likely path দেয় — কিন্তু individual time step-এ marginal MAP ভিন্ন। কখন কোনটা?

চমৎকার subtle. Decoding-এর দু'টি ভিন্ন approach — কখন সমান, কখন ভিন্ন?

Viterbi (joint MAP):

$\mathbf{s}^* = \arg\max P(\mathbf{s} \mid \mathbf{o})$।
Full sequence joint probability max।

Posterior MAP (marginal):

$s_t^* = \arg\max P(s_t \mid \mathbf{o})$ each $t$ independently।
Forward-backward → $\gamma_t$।

উদাহরণ যেখানে ভিন্ন:

Two paths nearly equal probability।
Path 1: (A B A B), prob 0.3।
Path 2: (B A B A), prob 0.29।
Other paths each 0.001।
Viterbi: (A B A B)।
Marginal at $t=1$: P(A) = 0.3 + 0.001 + ... ≈ 0.3; P(B) ≈ 0.29। MAP = A।
At $t=2$: marginal likely B।
Posterior MAP sequence: (A B A B) — coincidentally same।

Trickier:

Path X: (A A A), prob 0.4।
Path Y: (B B B), prob 0.4।
Path Z: (A B A), prob 0.0।
Viterbi: X or Y।
Marginal at $t=1$: P(A) = 0.4, P(B) = 0.4 — tie।
$t=2$: same tie।
Posterior MAP can give (A B A) — joint probability ০!

Key insight:

Posterior MAP can yield sequence with zero joint probability।
Viterbi guarantees valid (positive) joint probability।

কখন Viterbi:

Hard transition constraints (impossible transitions)।
Sequence interpretation matters।
POS tagging — grammatical structure।
Speech — phoneme transition rules।

কখন posterior:

Per-time accuracy matters more than sequence consistency।
No hard transition constraints।
Bioinformatics — gene segment classification (some studies prefer marginal)।

Empirical:

Speech: Viterbi standard।
POS: Viterbi standard।
Some tagging task: posterior decoding marginally better accuracy।
Test both empirically।

Beyond:

Minimum Bayes risk (MBR) decoding — average loss minimize।
$N$-best Viterbi — top $N$ sequences।
Sampling-based decoding।

Bangladesh case:

Bangla NER — sequence consistency critical (Viterbi)।
Time series anomaly — per-step decision (posterior OK)।

মূল উপলব্ধি: Viterbi — sequence consistent। Posterior — per-step accurate। Different objective, different best। Task semantics decide।

প্র ০৪ Bangla speech recognition baseline-এ Baum-Welch — pipeline ও challenges?

Bangla speech recognition — significantly underexplored। HMM-based অনুপ্রেরণা।

Why Bangla speech hard:

Limited annotated data (English-এর তুলনায়)।
Complex morphology — verb conjugation।
Code-switching (Bangla-English mix)।
Regional dialect — Sylheti, Chittagong, Standard।
Tonal subtleties।

HMM-based pipeline:

Feature extraction: MFCC (39-D)।
Phoneme HMM: Bangla phoneme set (~50)।
Triphone modeling: context-dependent — left+center+right phoneme।
Acoustic model: Gaussian Mixture HMM emission।
Pronunciation lexicon: word → phoneme sequence।
Language model: $n$-gram বা neural।
Decoder: Viterbi on combined HMM+LM lattice।

Training data:

Bangla LibriVox audiobooks।
OpenSLR Bangla TTS dataset।
Common Voice Bangla।
SHRUTI Bangla speech corpus।
Total ~১০০-১০০০ hour available।

Baum-Welch training:

Initial: viterbi-aligned phoneme boundary।
Multiple iteration EM।
Triphone state tying (decision tree)।
Speaker adaptation (MLLR)।

Challenges:

Data scarcity: low-resource language।
Annotation cost: phonetic transcription expensive।
Dialect variation: single model fits poorly।
Code-switching: "আমি bus-এ যাচ্ছি"।
Numbers/dates: mixed pronunciation।

Modern hybrid:

HMM-DNN hybrid — DNN emission, HMM transition।
Better than HMM-GMM significantly।
Kaldi toolkit standard।

End-to-end alternatives:

Wav2Vec 2.0 fine-tuned on Bangla।
Whisper Bangla — multilingual pretrained।
Conformer — state-of-art।
HMM-based now baseline, not champion।

Bangladesh context:

BRAC Bangla speech datasets — emerging।
Daffodil University CSE — academic research।
BRAC, ICT Division — government initiative।
Industry use — call center, voice assistant।

Production stack:

Acoustic: Conformer + CTC।
Language: Bangla LM।
Adaptation: speaker-specific finetune।
Decoder: beam search।
Post-processing: punctuation, normalization।

HMM pedagogical value:

Sequence model intuition।
EM algorithm understanding।
Production system architecture (HMM principles persist)।
Low-resource language baseline।

মূল উপলব্ধি: Bangla speech recognition — HMM historical baseline, modern hybrid neural champion। Baum-Welch foundation; production end-to-end Transformer। Bangladesh AI sovereignty-এ Bangla speech key — investment opportunity।

অনুশীলন

হিসাব করুন: 2-state HMM, π=(0.5, 0.5), A=[[0.6, 0.4], [0.5, 0.5]], B=[[0.7, 0.3], [0.2, 0.8]]। Observe (0, 1)। Viterbi most-likely sequence?
- δ₁(0) = 0.5 × 0.7 = 0.35; δ₁(1) = 0.5 × 0.2 = 0.10।
- δ₂(0): max(0.35×0.6, 0.10×0.5) × 0.3 = 0.21 × 0.3 = 0.063, ψ=0।
- δ₂(1): max(0.35×0.4, 0.10×0.5) × 0.8 = 0.14 × 0.8 = 0.112, ψ=0।
- Best final: state 1 (0.112)। Backtrace ψ₂(1)=0 → start with state 0।
- Most likely: (state 0 → state 1)।

NumPy-তে চেষ্টা: Viterbi scratch + log-space।

import numpy as np
# (উপরের viterbi() function reuse)

A  = np.array([[0.6, 0.4], [0.5, 0.5]])
B  = np.array([[0.7, 0.3], [0.2, 0.8]])
pi = np.array([0.5, 0.5])
obs = [0, 1]

path, log_p = viterbi(obs, A, B, pi)
print("Path:", path)        # [0, 1]
print(f"Log-prob: {log_p:.4f}")

ভাবুন: Bangla typing autocorrect-এ Viterbi-base — কোন state, observation, transition? Limitations?
- State: intended word।
- Observation: typed word (with errors)।
- Transition: bigram language model probability।
- Emission: typo probability — keyboard adjacency, edit distance।
- Viterbi: most-likely intended sentence।
- Limit: bigram simple — long context miss। BERT-based fix superior।
- Hybrid: Viterbi fast suggest, Transformer fallback complex।