Introduction

Hidden Markov Models, usually shortened to HMMs, are useful when a system has hidden states but produces visible observations. In C++, the model maps cleanly to vectors and matrices, so you can implement the core algorithms without much framework code.

Model States, Observations, and Probabilities

An HMM has three probability tables. The start distribution says how likely each hidden state is at time zero. The transition matrix says how likely it is to move from one hidden state to another. The emission matrix says how likely a state is to produce each observation.

A classic teaching example is weather prediction. The hidden state is the weather, but the observed symbol is an activity such as walking or shopping. If you observe a sequence of activities, the model can estimate how likely that sequence is under the weather model.

1#include <iostream>
2#include <string>
3#include <vector>
4
5struct HMM {
6    std::vector<double> start;
7    std::vector<std::vector<double>> transition;
8    std::vector<std::vector<double>> emission;
9    std::vector<std::string> states;
10    std::vector<std::string> symbols;
11};
12
13int symbolIndex(const HMM& hmm, const std::string& symbol) {
14    for (std::size_t i = 0; i < hmm.symbols.size(); ++i) {
15        if (hmm.symbols[i] == symbol) return static_cast<int>(i);
16    }
17    return -1;
18}

This layout is intentionally plain. You do not need templates, inheritance, or external libraries to get started. A small struct with nested vectors is enough for experimenting with algorithms and test data.

Compute Sequence Probability with the Forward Algorithm

The forward algorithm uses dynamic programming. For each time step, it stores the probability of ending in each hidden state after consuming the observations seen so far. That avoids recomputing the same subproblems repeatedly.

1#include <iomanip>
2
3double forwardProbability(const HMM& hmm, const std::vector<std::string>& observations) {
4    const std::size_t stateCount = hmm.states.size();
5    const std::size_t timeSteps = observations.size();
6
7    std::vector<std::vector<double>> alpha(
8        timeSteps, std::vector<double>(stateCount, 0.0));
9
10    int firstSymbol = symbolIndex(hmm, observations[0]);
11    for (std::size_t s = 0; s < stateCount; ++s) {
12        alpha[0][s] = hmm.start[s] * hmm.emission[s][firstSymbol];
13    }
14
15    for (std::size_t t = 1; t < timeSteps; ++t) {
16        int obs = symbolIndex(hmm, observations[t]);
17        for (std::size_t current = 0; current < stateCount; ++current) {
18            double total = 0.0;
19            for (std::size_t previous = 0; previous < stateCount; ++previous) {
20                total += alpha[t - 1][previous] * hmm.transition[previous][current];
21            }
22            alpha[t][current] = total * hmm.emission[current][obs];
23        }
24    }
25
26    double probability = 0.0;
27    for (double value : alpha.back()) {
28        probability += value;
29    }
30    return probability;
31}
32
33int main() {
34    HMM hmm{
35        .start = {0.6, 0.4},
36        .transition = {
37            {0.7, 0.3},
38            {0.4, 0.6}
39        },
40        .emission = {
41            {0.6, 0.3, 0.1},
42            {0.1, 0.4, 0.5}
43        },
44        .states = {"Sunny", "Rainy"},
45        .symbols = {"walk", "shop", "clean"}
46    };
47
48    std::vector<std::string> observations = {"walk", "shop", "clean"};
49    double p = forwardProbability(hmm, observations);
50
51    std::cout << std::fixed << std::setprecision(6)
52              << "Sequence probability: " << p << '\n';
53}

Compile it with g++ -std=c++17 hmm.cpp -o hmm and run ./hmm. The output is a single likelihood value for the observation sequence. That value is not a classification by itself, but it becomes useful when you compare several models or evaluate candidate parameter sets.

Extend the Implementation for Decoding

The forward algorithm answers, "How likely was this observation sequence?" If you want the most likely hidden state path, use the Viterbi algorithm instead. Viterbi looks similar, but it keeps the best previous state rather than summing all previous states.

In practice, many C++ implementations expose both operations. Forward is good for scoring. Viterbi is good for decoding. Once the data structure is in place, the main difference is the recurrence step and the extra backpointer array used by Viterbi.

For short toy sequences, raw probabilities are fine. For longer sequences, probabilities quickly become extremely small. Real HMM code usually works in log space or applies scaling at each time step to avoid underflow.

Common Pitfalls

One common mistake is mixing up the dimensions of the transition and emission matrices. A transition row should describe where one state can go next, while an emission row should describe which observations that state can produce.

Another problem is forgetting to validate the observation symbols before using them as indexes. If symbolIndex returns -1, the program should reject the input instead of reading invalid memory.

Numeric underflow is another frequent issue. Even correct code can drift toward zero when the sequence is long. If your probabilities suddenly become zero for nontrivial inputs, move to log probabilities or scale each step.

Summary

• HMMs model hidden states and visible observations with start, transition, and emission probabilities.
• In C++, a simple struct backed by vectors is enough to implement the core algorithm.
• The forward algorithm computes the likelihood of an observation sequence efficiently with dynamic programming.
• Viterbi solves a different problem: recovering the most likely hidden state path.
• Longer sequences need scaling or log space to avoid floating-point underflow.