What does Hidden Markov Models for Customer Decision Stages conclude, in numbers, about “Identifiability and Label Switching: What Clickstreams Cannot Say”?

Answer: Chapter 5 treats label switching, the number of stages and weak identifiability: naming stages by average position within a visit gives an accuracy of 0.4477, close to 0.4623 with true labels, and with blurred pages clicks keep only 0.022 of the information.

Scope of the numbers: Marked boxes separate published evidence, runnable Python calculations (18 programs), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.4477, 0.4623

part 124 relabellings of the true model, p21 visit
log P(clicks) min -12.588330510522 max -12.588330510522
part 2: runs of p42; naming rules against the oracle
run oracle E P acc: orc E P ready: E P
13012 3021 3021 0.4303 0.4277 0.4277 0.7181 0.7181
20213 0123 0213 0.5039 0.4910 0.5039 0.7406 0.7716
30123 1023 0213 0.4845 0.3026 0.4465 0.7813 0.7413
42301 2310 2301 0.4619 0.4226 0.4619 0.7813 0.7813
53210 2130 3120 0.3877 0.3600 0.3787 0.6458 0.6458
60321 0312 0312 0.4129 0.4032 0.4032 0.7413 0.7413
73201 2301 1302 0.4329 0.4303 0.3910 0.7129 0.7097
83012 3102 3021 0.5181 0.3065 0.4974 0.7703 0.7471
91230 1230 2130 0.5123 0.5123 0.4903 0.7884 0.7587
103201 3012 3102 0.4787 0.3219 0.4768 0.7703 0.7703
mean 4-stage acc: oracle 0.4623, rule E 0.3978, rule P 0.4477
rule E matches the oracle in 1 of 10 runs, rule P in 2
Show the full program
# Chapter 5. p51: label switching, and two ways to name fitted stages.
# Model: the four-stage HMM of p11 (illustrative). Part 1: permuting the
# stage labels of the true model (all 24 orders) leaves the likelihood
# of the p21 visit unchanged. Part 2: the same 150 visits and the same
# 10 random starts as p42 (same seed, 40 Baum-Welch iterations). The
# fitted states carry arbitrary numbers. Two naming rules that need no
# true labels are compared with the oracle relabelling of p42:
# rule E orders states by their share of SHIP and CART pages; rule P
# orders states by mean posterior click position within a visit.
import itertools
import math
import random

TRUE_PI = [0.70, 0.20, 0.08, 0.02]
TRUE_A = [[0.70, 0.22, 0.06, 0.02],
          [0.08, 0.64, 0.23, 0.05],
          [0.02, 0.10, 0.66, 0.22],
          [0.01, 0.03, 0.16, 0.80]]
TRUE_B = [[0.45, 0.30, 0.08, 0.07, 0.06, 0.04],
          [0.15, 0.35, 0.25, 0.12, 0.08, 0.05],
          [0.08, 0.22, 0.15, 0.30, 0.17, 0.08],
          [0.05, 0.12, 0.08, 0.15, 0.30, 0.30]]
K, M = 4, 6
VISIT = [0, 1, 2, 3, 1, 3, 4, 5]


def draw(rng, probs):
    u, acc = rng.random(), 0.0
    for k, p in enumerate(probs):
        acc += p  # step
        if u < acc:
            return k
    return len(probs) - 1


def rand_row(rng, n):
    w = [rng.random() + 0.2 for _ in range(n)]
    z = math.fsum(w)
    return [x / z for x in w]


def fb(pi, a, b, obs):
    T = len(obs)
    al, cs = [], []
    x = [pi[k] * b[k][obs[0]] for k in range(K)]
    for t in range(T):
        if t:
            x = [math.fsum(al[-1][i] * a[i][j] for i in range(K))
                 * b[j][obs[t]] for j in range(K)]
        c = math.fsum(x)
        cs.append(c)
        al.append([v / c for v in x])
    be = [[1.0] * K]
    for t in range(T - 2, -1, -1):
        nb = be[0]
        be.insert(0, [math.fsum(a[i][j] * b[j][obs[t + 1]] * nb[j]
                                for j in range(K)) / cs[t + 1]
                      for i in range(K)])
    gam = [[al[t][k] * be[t][k] for k in range(K)] for t in range(T)]
    xi = [[[al[t][i] * a[i][j] * b[j][obs[t + 1]] * be[t + 1][j]
            / cs[t + 1] for j in range(K)] for i in range(K)]
          for t in range(T - 1)]
    return math.fsum(math.log(c) for c in cs), gam, xi


def em_step(pi, a, b, data):
    ll, g1 = [], [[] for _ in range(K)]
    na = [[[] for _ in range(K)] for _ in range(K)]
    da = [[] for _ in range(K)]
    nb = [[[] for _ in range(M)] for _ in range(K)]
    db = [[] for _ in range(K)]
    for obs in data:
        lv, gam, xi = fb(pi, a, b, obs)
        ll.append(lv)
        for k in range(K):
            g1[k].append(gam[0][k])
        for t, o in enumerate(obs):
            for k in range(K):
                nb[k][o].append(gam[t][k])
                db[k].append(gam[t][k])
                if t < len(obs) - 1:
                    da[k].append(gam[t][k])
                    for j in range(K):
                        na[k][j].append(xi[t][k][j])
    n = len(data)
    pi = [math.fsum(g1[k]) / n for k in range(K)]
    a = [[math.fsum(na[i][j]) / math.fsum(da[i]) for j in range(K)]
         for i in range(K)]
    b = [[math.fsum(nb[k][m]) / math.fsum(db[k]) for m in range(M)]
         for k in range(K)]
    return pi, a, b, math.fsum(ll)


def viterbi(pi, a, b, obs):
    d = [math.log(pi[k] + 1e-300) + math.log(b[k][obs[0]] + 1e-300)
         for k in range(K)]
    back = []
    for o in obs[1:]:
        ptr = [max(range(K), key=lambda i: d[i] + math.log(a[i][j]
                                                            + 1e-300))
               for j in range(K)]
        d = [d[ptr[j]] + math.log(a[ptr[j]][j] + 1e-300)
             + math.log(b[j][o] + 1e-300) for j in range(K)]
        back.append(ptr)
    path = [max(range(K), key=lambda k: d[k])]
    for ptr in reversed(back):
        path.append(ptr[path[-1]])
    return path[::-1]


def rank_to_perm(score):
    # 分数从小到大依次命名为 BRW、RES、CMP、DEC
    order = sorted(range(K), key=lambda k: (score[k], k))
    perm = [0] * K
    for name, k in enumerate(order):
        perm[k] = name
    return tuple(perm)


lls = []
for perm in itertools.permutations(range(K)):
    inv = [perm.index(k) for k in range(K)]
    pi = [TRUE_PI[inv[k]] for k in range(K)]
    a = [[TRUE_A[inv[i]][inv[j]] for j in range(K)] for i in range(K)]
    b = [TRUE_B[inv[k]] for k in range(K)]
    lls.append(fb(pi, a, b, VISIT)[0])
print("part 1: 24 relabellings of the true model, p21 visit")
print("  log P(clicks) min %.12f max %.12f" % (min(lls), max(lls)))

rng = random.Random(20261113)
data, truth = [], []
for _ in range(150):
    s = [draw(rng, TRUE_PI)]
    for _ in range(rng.randint(6, 14) - 1):
        s.append(draw(rng, TRUE_A[s[-1]]))
    truth.append(s)
    data.append([draw(rng, TRUE_B[k]) for k in s])
print("part 2: runs of p42; naming rules against the oracle")
print("run oracle  E    P     acc: orc    E      P   ready: E      P")
ok_e = ok_p = 0
acc_e, acc_p, acc_o = [], [], []


def score(paths, perm):
    pairs = [(perm[x], y) for p, s in zip(paths, truth)
             for x, y in zip(p, s)]
    n = len(pairs)
    hit = len([1 for x, y in pairs if x == y]) / n
    rdy = len([1 for x, y in pairs if (x >= 2) == (y >= 2)]) / n
    return hit, rdy


for r in range(10):
    pi = rand_row(rng, K)
    a = [rand_row(rng, K) for _ in range(K)]
    b = [rand_row(rng, M) for _ in range(K)]
    for _ in range(40):
        pi, a, b, _ = em_step(pi, a, b, data)
    paths = [viterbi(pi, a, b, o) for o in data]
    oracle, best_hit = None, -1
    for perm in itertools.permutations(range(K)):
        hit = len([1 for p, s in zip(paths, truth)
                   for x, y in zip(p, s) if perm[x] == y])
        if hit > best_hit:
            oracle, best_hit = perm, hit
    pe = rank_to_perm([b[k][4] + b[k][5] for k in range(K)])
    pos = [[] for _ in range(K)]
    wts = [[] for _ in range(K)]
    for obs in data:
        gam = fb(pi, a, b, obs)[1]
        for t in range(len(obs)):
            for k in range(K):
                pos[k].append(gam[t][k] * t / (len(obs) - 1))
                wts[k].append(gam[t][k])
    pp = rank_to_perm([math.fsum(pos[k]) / math.fsum(wts[k])
                       for k in range(K)])
    ok_e += 1 if pe == oracle else 0  # step
    ok_p += 1 if pp == oracle else 0  # step
    so, se, sp = score(paths, oracle), score(paths, pe), score(paths, pp)
    acc_o.append(so[0])
    acc_e.append(se[0])
    acc_p.append(sp[0])
    print("%2d  %s %s %s  %.4f %.4f %.4f  %.4f %.4f"
          % (r + 1, "".join(map(str, oracle)), "".join(map(str, pe)),
             "".join(map(str, pp)), so[0], se[0], sp[0], se[1], sp[1]))
print("mean 4-stage acc: oracle %.4f, rule E %.4f, rule P %.4f"
      % (math.fsum(acc_o) / 10, math.fsum(acc_e) / 10,
         math.fsum(acc_p) / 10))
print("rule E matches the oracle in %d of 10 runs, rule P in %d"
      % (ok_e, ok_p))

Single source and citation

Fan, Y. (2026). Hidden Markov Models and Viterbi Decoding: Inferring a Customer's Hidden Decision Stage from Click Sequences and Timing the Offer (Version 1.0.0), Chapter 5: Identifiability and Label Switching: What Clickstreams Cannot Say. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-300 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026300,
  author    = {Fan, Yafu},
  title     = {Hidden Markov Models and Viterbi Decoding: Inferring a Customer's Hidden Decision Stage from Click Sequences and Timing the Offer},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book