CRF & HSMM Temporal Smoothing — From Flicker to Stable Segments

Chapter 1: Why Independent Predictions Flicker

Let us make the flicker quantitative, because a feeling is not an explanation. We will work a concrete miniature. Imagine just two classes, A and B, and seven frames. The true label is A A A B B B B — a single clean switch from A to B after frame 3. A perfect oracle would output exactly that. Our network is good but not perfect: its scores are the truth plus a little noise.

Concretely, suppose the network's score margin for "B over A" (call it s = score(B) − score(A)) should be strongly negative in the A region and strongly positive in the B region. The argmax rule is dead simple: predict B whenever s > 0, else A. Here are seven frames where the underlying truth is clear but two frames got unlucky noise:

Read what happened. Frame 2 caught a big positive noise spike (+2.6), which dragged its margin to +0.6 — just barely positive — so argmax flipped it to B. A phantom B inside the A region. Frame 5 caught a big negative spike (−3.1), dragging its margin to −1.1, so argmax flipped it to A. A phantom A inside the B region. The result is A B A B A B B instead of A A A B B B B: two wrong frames, and worse, four extra label switches that the real activity never made.

Here is the deep point. The per-frame error rate is only 2 of 7 ≈ 29%, which sounds survivable. But the structure is wrecked: the prediction has 5 transitions where the truth has 1. Many downstream systems care far more about the number and timing of switches (the segmentation) than about raw per-frame accuracy. A single spurious switch can trigger an alarm, a state machine, a billing event. Independent prediction optimizes the wrong thing: it minimizes per-frame error while ignoring the catastrophic cost of needless switches.

The widget makes the threshold-sensitivity tangible. The blue curve is the clean margin s; the dots are the noisy per-frame margins. The dashed line is the argmax threshold at s=0. Every dot that lands on the wrong side of the line is a flickered frame. Drag the noise and watch dots leap across the threshold near the boundary, where the clean margin is small. Notice that flicker concentrates exactly where the network is genuinely uncertain — at transitions — and that's the worst place for it.

Chapter 2: The Linear-chain CRF

We need a model that scores a whole label sequence, not each frame alone, so that "label paths that switch too much" are penalized. The linear-chain Conditional Random Field (CRF) is exactly that. It assigns a single number — a score (or negative energy) — to any candidate label path, and the best path is the one with the highest score. Two ingredients build that number.

Ingredient 1 — emission scores. For each frame t and each possible label y, an emission score φ_t(y) says "how well does frame t look like label y?" These are exactly your network's per-frame scores (the logits before softmax). Big φ_t(B) means frame t looks like B. This is the local evidence term — the only thing per-frame argmax ever used.

Ingredient 2 — transition scores. For each pair of labels (i, j), a transition score ψ(i, j) says "how compatible is it to be in label i at one frame and label j at the next?" We arrange these in a transition matrix T where T[i][j] = ψ(i, j). The whole temporal prior lives here: we make "staying" (T[i][i], the diagonal) large and "switching" (T[i][j] for i≠j, off-diagonal) small. That single design choice is what discourages flicker.

The score of a full label path y = (y₁, …, y_L) is the sum of every emission it touches plus every transition it makes:

Read it slowly. The first sum walks every frame and adds how well the chosen label fits that frame's evidence. The second sum walks every adjacent pair and adds the compatibility of the chosen transition. A path that follows the per-frame argmax gets high emission but may pay heavy transition penalties for flickering; a path that stays put pays small transition costs but may sacrifice some emission. The best path balances the two. That balance is the smoothing.

Notice what just happened: a path is no longer scored frame-by-frame in isolation. The transition term couples each frame's label to its neighbor's. Now a lone spike is expensive: to honor one flickered frame the path must pay two switch penalties (jump out and jump back), which usually costs more emission than it gains. The spike gets out-voted. The widget lets you build a path by clicking and watch its score decompose into the emission part and the transition part — see directly how flicker bleeds score through the transition term.

Why is it called conditional? Because the CRF models the label sequence conditioned on the observations (it never tries to model the pixels themselves, unlike a generative HMM). And random field is the formal name for the graph of coupled variables. Linear-chain means each label is coupled only to its immediate neighbors — a chain — which is what makes exact decoding cheap, as the next chapter shows. To turn scores into a probability over paths, the CRF normalizes by the sum of exp(score) over all paths; we will need that sum (the partition function) only for training, in Chapter 4. For decoding, we just want the highest-scoring path, and the score alone suffices.

Chapter 3: Viterbi — Finding the Best Path

We can score any path now. But there are K^L possible paths (K labels, L frames) — for 5 labels and 100 frames that's 5¹⁰⁰, more than the atoms in the universe. We cannot enumerate them. We need an algorithm that finds the single best-scoring path without listing all of them. That algorithm is Viterbi, and it is one of the most elegant pieces of dynamic programming you will ever meet.

The trick rests on one observation. Suppose I tell you the best path's last label is B. Then the rest of that path — everything up to the second-to-last frame — must itself be the best possible path ending in whatever label sits before B. There is no benefit to making an earlier choice worse. This is the principle of optimality: the best path is built from best sub-paths. So instead of tracking whole paths, we track only the best score of a path ending in each label at each frame, and extend it frame by frame.

Define δ_t(j) = the score of the best path that covers frames 1..t and ends in label j at frame t. The recursion is:

In words: the best score ending in j now equals frame t's emission for j, plus the best way to arrive at j — we look back at every possible previous label i, add its accumulated best score δ_t−1(i) and the cost T[i][j] of stepping from i to j, and keep the maximum. We also remember which i achieved the max (the backpointer) so we can trace the winning path back at the end. The base case is δ₁(j) = φ₁(j): the first frame has only its emission.

Count the work. At each of L frames, for each of K destination labels, we look back over K source labels: that is L·K² operations. For K=5, L=100 that's 2,500 — instant — instead of 5¹⁰⁰. Viterbi turns an astronomically large search into a tiny grid sweep. This is the whole reason linear-chain CRFs are practical: the chain structure makes exact global decoding cheap.

The widget animates the lattice. Columns are frames, the two rows are labels A and B; each cell shows its running δ. Step through and watch the recursion fill the grid left to right, with the surviving backpointer arrows highlighted. At the end, the bright path traced from the best final cell is the global optimum — the smoothed label sequence. Compare it to the raw argmax row at the bottom to see flicker get erased.

One subtlety that trips people: Viterbi finds the single most probable whole path, which is not the same as taking the most probable label at each frame independently (that latter, "posterior marginal" decoding, comes from the forward–backward algorithm of Chapter 4). For smoothing we almost always want the best whole path, because it is guaranteed to be a consistent sequence — it never proposes a transition the model considers impossible, and it respects the smoothness prior globally rather than locally.

Chapter 4: Training a CRF — The Forward Algorithm

So far T (the transition matrix) was a knob we set by hand. Often that's fine for a pure smoother. But we can also learn T (and even the emission weights) from labeled sequences, so the CRF discovers the real transition costs. Training a CRF means maximizing the sequence log-likelihood of the true paths, and doing that forces us to compute a famous quantity: the partition function.

Recall the CRF turns a path score into a probability by exponentiating and normalizing over all paths:

Z is the partition function: the sum of exp(score) over every possible label path. Training maximizes log P(y_true) = score(y_true) − log Z. The first term pushes the true path's score up; the second term (log Z) pushes every path's score down, so the model can't just inflate all scores. The gradient is intuitive: it nudges T so that observed transitions get more probable and unobserved ones less. But Z sums over K^L paths — the same astronomical number Viterbi dodged. We need the same dynamic-programming trick, in a "soft" form.

That soft form is the forward algorithm. It is Viterbi with one operator swapped: replace max with log-sum-exp. Where Viterbi kept the single best way to reach each cell, the forward algorithm keeps the total (log) score mass of all ways to reach it. Define α_t(j) = log of the summed exp-scores of all paths covering frames 1..t and ending in label j. The recursion:

Compare to Viterbi: identical, but max_i became logsumexp_i. At the end, log Z = logsumexp_j α_L(j): combine the final column. We need log-sum-exp (not plain sum-of-exp) for the same reason softmax subtracts its max — numerical stability. exp of a large score overflows to infinity; computing it in log-space keeps everything finite.

Let us also see Z agree with brute force on a tiny case, so the algorithm isn't a black box. Two labels, two frames, emissions φ(A)=[1,0], φ(B)=[0,1], T=[[0.5, −0.5],[−0.5, 0.5]]. There are 4 paths: AA score 1+0+0.5=1.5; AB score 1+1−0.5=1.5; BA score 0+0−0.5=−0.5; BB score 0+1+0.5=1.5. Brute Z = e^1.5+e^1.5+e^−0.5+e^1.5 = 4.482·3 + 0.607 = 14.05, so log Z = 2.643. The forward algorithm reaches the same 2.643 by combining columns — you'll verify exactly this in the Code Lab below.

The widget contrasts the two recursions side by side on the same lattice. The left grid fills with Viterbi's max (sharp — one winner per cell); the right grid fills with the forward algorithm's log-sum-exp (soft — it blends all incoming scores). Watch how the soft version is always ≥ the max version (summing ≥ picking the biggest), and how the final log Z (right) is always ≥ the best path score (left). That gap, score(y_true) − log Z, is exactly the (negative) training loss.

Chapter 5: HSMM — Modeling How Long States Last

The CRF's transition prior says "switching is costly," which discourages flicker. But it has a hidden blind spot. Think about what a constant stay-bonus implies about durations. If staying always adds the same fixed score, then the probability of remaining in a state for d more frames decays geometrically: each extra frame multiplies by the same factor. A geometric distribution's most likely duration is … one frame. The model's built-in belief is "states are probably very short," which is often badly wrong — a walking bout lasts seconds, a phoneme tens of milliseconds, a cooking step many seconds.

The Hidden Semi-Markov Model (HSMM) fixes exactly this. The "semi-Markov" part means: instead of deciding "stay or switch" at every frame, the model enters a state, draws an explicit duration d from a learned duration distribution p_state(d), emits for d frames, and only then transitions to a new state. Durations are now a first-class, freely-shaped distribution — you can say "walking segments are usually 60–120 frames, almost never 1 frame," which a plain CRF/HMM literally cannot express.

So an HSMM segment has a score with three parts: the duration score log p_state(d) (how plausible is a segment of this length for this state), the emission score summed over the d frames in the segment, and the transition score for the jump into the next state. The full sequence score sums these over all segments:

The widget shows the contrast directly. The orange curve is the geometric duration distribution baked into a constant-stay CRF (always peaking at d=1). The teal curve is an HSMM's explicit duration distribution, which you can recenter with a slider to match reality — say, "segments are usually ~40 frames." Slide the target and watch the HSMM put its mass where the real durations live, while the geometric curve is stuck insisting "probably one frame."

Decoding an HSMM uses a generalized Viterbi. Instead of "best path ending in label j at frame t," we track "best score of a segmentation ending a segment of state j exactly at frame t," and to fill it we look back over all possible segment start points — trying durations d = 1, 2, 3, … up to some max D — adding the duration score and the summed emissions for that span. The cost rises to about L·K²·D (the extra D from scanning durations), but with a capped D it stays perfectly practical. The payoff is that the smoother now respects realistic segment lengths: it won't carve a 2-second action into three tiny pieces, and it won't let a half-second blip become a "segment" if your duration prior says segments are long.

When should you reach for an HSMM over a CRF? When durations carry real signal you want to enforce — minimum dwell times (a phoneme can't be 1 frame), typical lengths (assembly steps), or hard floors (a stable medical state must persist N frames before you believe it). When durations don't matter much, a CRF's constant stay-bonus is simpler, faster, and usually enough. The HSMM is the heavier tool you deploy when "how long" is as important as "which".

Chapter 6: Smoothing Deep Predictions as a Post-Processor

Now the practical payoff. You already have a deep network — a CNN, a temporal convolutional network, a Transformer — that produces per-frame logits (raw class scores before softmax). The cleanest way to use a CRF or HSMM is as a post-processor: feed the network's logits in as the emission scores φ_t(y), pick a transition matrix T, run Viterbi, and read out the smoothed path. You retrain nothing. The deep net is the expensive, frozen feature engine; the CRF is a microsecond of dynamic programming bolted on the end.

The data flow is short and worth memorizing. Input: logits of shape (L, K) — L frames, K classes — straight from model(video), no softmax needed (Viterbi is monotone, softmax doesn't change the argmax path). Choose T of shape (K, K): a common cheap choice is T = λ·I with the off-diagonal at −λ (a single smoothing strength λ). Run the L·K² Viterbi sweep. Output: a length-L integer array of smoothed labels. That's it — a few dozen lines, no GPU, no gradients.

Here is the entire post-processor in code, by hand first so nothing is hidden:

python
import numpy as np

# logits: (L, K) per-frame class scores straight from the deep net (no softmax needed)
def crf_smooth(logits, stay=2.0, switch=-1.0):
    L, K = logits.shape
    T = np.full((K, K), switch); np.fill_diagonal(T, stay)   # the smoothing prior
    delta = np.zeros((L, K)); bp = np.zeros((L, K), dtype=int)
    delta[0] = logits[0]                                       # base case: frame 0 = emission only
    for t in range(1, L):                                    # Viterbi sweep — O(L*K^2)
        for j in range(K):
            cand = delta[t-1] + T[:, j]                       # arrive at j from each previous label
            bp[t, j] = np.argmax(cand)                       # best predecessor (backpointer)
            delta[t, j] = logits[t, j] + cand[bp[t, j]]      # emission + best arrival
    path = [int(np.argmax(delta[-1]))]                       # start at best final label
    for t in range(L-1, 0, -1): path.append(int(bp[t, path[-1]]))   # trace back
    return path[::-1]                                       # the smoothed label sequence

# usage: raw = logits.argmax(1)  flickers;  smooth = crf_smooth(logits)  is stable

And the library version — a learnable CRF layer you train jointly with the network — is the same idea with gradients flowing through it:

python
# pip install pytorch-crf — a trainable linear-chain CRF as a final layer
from torchcrf import CRF
crf = CRF(num_tags=K, batch_first=True)
emissions = model(video)                       # (B, L, K) the deep net's logits = CRF emissions
loss = -crf(emissions, labels)               # neg sequence log-lik = score(true) - logZ (forward algo inside)
path = crf.decode(emissions)                   # Viterbi decode -> smoothed label paths

Two ways to deploy, and the choice matters. Post-hoc smoothing (the by-hand version): train the network normally with per-frame loss, then bolt a fixed CRF on at inference. Zero retraining, instant, great when you already shipped a model. Joint training (the library version): make the CRF the final layer and train end-to-end with the sequence log-likelihood loss, so the network learns features aware that a smoother follows. Joint training usually wins on accuracy because the emission scores and transition costs co-adapt; post-hoc wins on engineering simplicity and is shockingly effective for the cost.

The widget shows the full post-processing pipeline on a noisy logit stream. Top: the deep net's raw per-frame argmax (flickery). Middle: the same logits after Viterbi smoothing with your chosen stay-bonus. Bottom: ground truth. Slide the stay-bonus and watch the middle strip snap from confetti to clean segments matching the truth. This is the entire chapter in one picture: logits in, T chosen, Viterbi run, flicker gone.

Chapter 7: Showcase — Smooth a Noisy Label Stream Live

Everything converges here. This is a full, live smoother you can drive and break. We generate a ground-truth label sequence over many frames with three classes (call them stand, walk, run), corrupt it with adjustable noise to simulate a flickery deep net, and then smooth it with a Viterbi CRF whose transition strength you control in real time. Three strips stack on the canvas: raw argmax (the flickery input), Viterbi-smoothed (the output), and ground truth (the target). A live readout reports the per-frame accuracy and, crucially, the number of label switches in each strip versus the truth.

Here is the whole lesson made tactile. Push the noise up and watch the raw strip shatter while the smoothed strip holds its shape. Push the transition strength (stay-bonus) up and watch the smoothed strip go from "still a little jittery" to "clean stable blocks" — and then, if you push too far, watch it over-smooth, swallowing short real segments and lagging the true transitions. That over-smoothing is Chapter 8's tradeoff, and you can feel it directly here.

Three experiments, each proving a chapter:

• Crank noise, keep transition strength moderate. The raw switch-count explodes (dozens of spurious transitions); the smoothed switch-count stays near the true 2–3. This is the flicker-suppression of Chapters 1–3 in action.
• Set transition strength to 0. The smoothed strip collapses onto the raw strip — with no coupling, Viterbi is per-frame argmax. This proves the smoothing comes entirely from the transition prior.
• Set transition strength very high. The smoothed strip becomes one or two giant blocks — it has thrown away real short segments and its boundaries lag the truth. You've over-smoothed: maximum stability, but you've started ignoring the evidence.

If you removed this simulation, would you lose understanding? Yes — because "the transition prior trades fidelity for consistency" is an abstract sentence until you watch the smoothed strip transform from confetti to blocks as you slide one lever, and then watch it overshoot into lagging mega-blocks. The napkin drawing of this entire lesson is exactly this: noisy strip in, one smoothness dial, clean strip out — with a visible price when you turn the dial too far.

Chapter 8: Tradeoffs — Smoothing vs Lag

Smoothing is never free. Every spurious switch you suppress comes from a model that is reluctant to switch — and that same reluctance makes it slow to react to real switches. This is the central tradeoff of temporal smoothing, and understanding it is what separates someone who tunes a CRF well from someone who ships a laggy or a jittery system. There are three costs to name.

Cost 1 — boundary lag. When the true label genuinely changes at frame t, the smoother resists for a few frames before conceding, because near the boundary the accumulated stay-bonus still favors the old label until enough new-label emissions pile up. A strong stay-bonus needs more new evidence to be overruled, so the detected transition lands a few frames late. For a fall-detector or a trading signal, that latency can matter.

Cost 2 — swallowed short segments. A genuinely brief event — a one-second gesture, a quick glance — may be shorter than the smoother's effective "minimum believable duration." With a high stay-bonus (or an HSMM duration prior centered on long segments), the smoother decides the short event is cheaper to ignore than to switch in and out for, and it erases a real segment entirely. You traded flicker for missed detections.

Cost 3 — offline vs online. Full Viterbi needs the whole sequence before it can decode (the backtrace starts from the last frame), so it is inherently offline / batch. Real-time systems must decode online, seeing only the past. Online variants exist — fixed-lag smoothing (decode frame t once you've seen up to t+Δ, accepting Δ frames of latency) or forward-only/greedy decoding — but they are weaker than full Viterbi. There is no free lunch: more look-ahead buys more accuracy at the cost of more latency.

The widget makes the tradeoff a single curve you can read. As you increase the stay-bonus (x-axis), two quantities move in opposite directions: flicker (spurious switches) falls toward zero, while boundary lag (frames late on real transitions) rises. The sweet spot is the knee where flicker is mostly gone but lag is still small. Slide the bonus and watch both curves; the vertical marker shows where you are, and the readout tells you whether you're under-smoothing, near optimal, or over-smoothing.

Two practical rules fall out of this. First, match the smoothing to the cost asymmetry of your application. If false alarms are expensive (an alert system), smooth hard — accept lag, kill flicker. If missing a brief event is expensive (catching a quick anomaly), smooth gently — accept some flicker, keep responsiveness. Second, an HSMM gives you a finer instrument than a stay-bonus. Instead of one global "how reluctant to switch," you set per-state minimum and typical durations, so you can be very reluctant to leave a long, stable state but quick to register a state that's genuinely allowed to be short. Durations let you decouple "stable states" from "transient states" — something a single stay-bonus cannot.

Chapter 9: Connections & Where It's Used

You now hold a small, reusable machine: take any per-element sequence of scores, add a transition prior (and optionally a duration prior), and decode the globally-consistent path with Viterbi. That machine recurs across an astonishing range of problems, and naming the connections turns one lesson into a map.

It's the cousin of the HMM you may already know. A Hidden Markov Model (HMM) is the generative sibling: it models how observations are generated from hidden states (emission probabilities) and uses the same Viterbi and forward algorithms. The CRF is the discriminative version — it scores label paths conditioned on observations without modeling how observations arise, which is exactly what you want when your "observations" are a deep net's logits. Same dynamic programming, different probabilistic framing. See Hidden Markov Models for the generative foundation and the casino example where Viterbi first earns its keep.

It's the temporal layer in classic speech and modern hybrids. The original automatic speech recognition stacks were DNN–GMM–HMM hybrids: a neural net (or Gaussian mixture) produces per-frame phone scores, and an HMM with duration structure decodes them into a consistent phone/word sequence — precisely "deep frame scores, smoothed by a temporal model." The HSMM's explicit durations matter enormously there, because phones have characteristic lengths. See DNN–GMM–HMM Hybrids for how this exact pattern built speech recognition.

It's the standard smoother for whole-signal-over-time classification. In Acoustic Scene Classification and video action recognition, a deep net labels each short window and a CRF/HSMM stitches the windows into stable scene/action segments — the same flicker-to-segments story, audio or video instead of pose. And in NLP, the linear-chain CRF is the classic output layer for sequence tagging (named-entity recognition, part-of-speech tagging), where the transition matrix enforces label grammar (a B-tag must precede an I-tag) — identical machinery, "frames" are now word tokens.

Where to go next in the corpus. The dynamic-programming spine is taught from scratch in Hidden Markov Models; the deep-feature front-ends that produce the emissions live in Acoustic Scene Classification and Visual Scene Classification; the speech-recognition application is DNN–GMM–HMM Hybrids; and the broader Bayesian-filtering view of "fuse a model prior with noisy measurements over time" is in The Bayes Filter and The Kalman Filter — the continuous-state cousins of this discrete-label smoother.

Cheat sheet

"The world doesn't change every frame — so don't let your labels." The whole discipline of temporal smoothing is teaching a flickering model that one quiet fact.