# Conflict and Computation on Wikipedia:
## Appendix B Choosing the Number of States in an HMM  
Choosing the number of states to include in an HMM is an example of a model selection problem; one is selecting between models with different numbers of states. In general, the larger the HMM, the better the data can be fit: when does one stop improving the fit because the model is becoming \"too complex\"? A generic solution to model selection is cross-validation: one fits the model using a subset of the data (the \"training set\"), and sees how well the model performs when predicting out of sample (the \"test set\" or \"hold-out\" set). Cross-validation uses the phenomenon of over-fitting to determine when a model is too complex: if a model has too many parameters, it will overfit to the training set, finding \"patterns\" that are really due to coincidence. These patterns will fail to hold in the test set, and will degrade performance on the fit; this degradation can be measured, and one stops increasing model complexity when performance on the test set first starts to decline. Standard cross-validation techniques work best when the data are independently sampled, i.e., when it is possible to construct a test set that is uncorrelated with the training set conditional on the underlying model. As increasing levels of correlation appear in the data, the construction of an appropriate training set becomes difficult. When, as is the case for HMMs, the model is Bayesian, another method is possible: the likelihood penalty. To use a likelihood penalty, you fit the model to all of the data and note the posterior log-likelihood. You then apply a penalty, reducing the log-likelihood depending on features related to the complexity of the model, including, usually, the total number of parameters. After applying this penalty, it is usually the case that one particular model, often not the most complex one, maximizes the penalized log-likelihood, and this is the one considered preferred. Numerous likelihood penalties exist, including the Bayesian Information Criterion (BIC [36]), the Bayesian Evidence (introduced in [94]; used on Wikipedia data in [1, 16]) and the Akaike Information Criterion (AIC; introduced in [35]). The existence of both long- and short-range correlations in data fit using an HMM makes the use of cross-validation and hold-out techniques difficult. The work in [92] proposes two methods for cross-validation on HMMs that attempt to compensate for the failure of independence. Both methods have difficulties, and work well only on a subset of HMMs, where correlations are not particularly long-range and the transition matrix is not too sparse. Because we find that both conditions are violated in our data, we do not attempt cross-validation tests. The work in [92] also considers the AIC and BIC methods; they find that both work well in recovering the true size of an HMM used to generate simulated data. We are not aware of work that has tested the use of Bayesian Evidence on simulated data and defer this interesting, but involved, question to later work. The authors of Ref. [92] find that, when it fails, BIC tends to slightly underestimate, and AIC to slightly overestimate, the true number of states, although both criteria work well. Work by [93] confirms this result. However, both papers consider regimes that do not directly apply here, and both papers found cases where (for example) BIC significantly underestimated model complexity. In addition, both papers consider problems with an order of magnitude less data than we have and true model HMM sizes much smaller than ten. In the main text, we use the AIC penalty, a common choice made across the biological and signal processing communities, and strongly argued for on general grounds by [95] when the goal is minimizing prediction loss. To validate our choice and, in particular, to determine whether AIC or BIC produces more valid results for the regimes relevant here, we did an in-depth test with a particular model: the eight-state HMM associated with the God page.