THEORY-1045: On synthetic data from factorial hidden Markov models with three or five hidden chains of two or three states, an unconstrained hidden Markov model with as many states as the chains have joint settings overfits, its test-set excess over the true model rising to 175 bits per observation at five three-state chains against 4.5 for the factorial model trained exactly, while factorial models trained with completely factorized or structured variational E steps are not significantly worse than exact training

Source

Ghahramani and Jordan (1997), Factorial hidden Markov models, LIT-1628, read in full in NOTE-1203: §4.1 and Table 1.

What was actually shown

Data from factorial HMMs with parameters drawn uniformly and normalized, C = 0.0025I, four sizes (M, K) = (3, 2), (3, 3), (5, 2), (5, 3), 15 parameter sets each; 20 training and 20 test sequences of length 20; each algorithm run once per set, for at most 100 EM iterations. Test-set negative log likelihood in bits per observation relative to the true model, mean ± one standard deviation over 15:

(M, K)	HMM	exact	Gibbs	CFVA	SVA
(3, 2)	2.29 ± 1.02	1.05 ± 0.72	1.78 ± 1.22	1.20 ± 1.11	1.04 ± 1.01
(3, 3)	9.81 ± 2.55	1.26 ± 0.99	2.50 ± 0.87	1.50 ± 1.53	0.90 ± 0.84
(5, 2)	11.57 ± 3.71	2.51 ± 1.21	3.35 ± 1.14	2.07 ± 1.74	1.53 ± 1.05
(5, 3)	175.35 ± 84.74	4.49 ± 2.24	3.95 ± 1.14	5.14 ± 0.69	4.30 ± 1.62

The HMM’s training excess at (5, 3) is −4.80: it fits the training sequences better than the generating model. By the paper’s tests, Gibbs (ten samples per variable) is significantly worse than exact on the three smaller sizes; the completely factorized approximation is never significantly different; the structured one is not different on three sizes and better at (5, 2), p < 0.05.

What this does not say

• Not that the approximations are accurate in general. The problems are tiny (sequences of 20 steps), nearly noiseless, and drawn from the model itself.
• Not that the structured approximation regularizes. The authors offer that as one of two explanations of the (5, 2) difference, the other being chance.
• Not anything about the Bach result, which is read from a chart.

Connections

• LIT-1577. The infinite factorial HMM keeps the factorial structure and lets M grow; its experiments compare priors, not inference methods.
• CASE-165. A fitted version of the case’s per-member chains would face this paper’s trade-off between exact and approximate E steps (NOTE-1203).