Source-linked AI summary
A Data-Driven Approach to State Construction in Markov Models
Linde Van Gestel, Marie-Anne Guerry, Evy Rombaut
TL;DR
The paper addresses how to construct Markov-model states that satisfy transition-probability homogeneity when state creation is neglected or based on prior assumptions. It combines supervised feature selection with unsupervised clustering in a three-step framework and evaluates the resulting state definitions. Spectral clustering receives the strongest overall support, while spectral clustering and SOM capture inherent structure well in the application.
Problem
State construction is often neglected or assumption-driven, risking violation of the homogeneity requirement that underpins Markov-model validity and predictive power.
Method
The framework selects transition-relevant features, forms unsupervised subgroups with HDBSCAN, spectral clustering, or SOM, and aggregates subgroups with similar transition probabilities.
Results
90% of Akaike weights support the spectral model as the best approximating candidate, while spectral and SOM models show strong and consistent cross-validation performance.
Takeaways & Limitations
The framework provides methodological guidance for using latent similarities and unsupervised learning to improve state definitions in applied Markov modelling.
Takeaways & Limitations
The framework requires testing on alternative datasets because dataset-specific characteristics may influence the results.
Abstract
from arXiv · showhide
A Markov chain is a widely used stochastic process modelling random events over time. These models are built on subsets of the entire dataset, referred to as states, which are considered to be homogeneous regarding transition probabilities. However, the creation of these states is often disregarded or based on prior assumption, potentially violating the homogeneity requirement and thus decreasing the validity and predictive power of the model. In order to fill this gap, this paper combines supervised feature selection with unsupervised learning techniques for data-driven state construction. Density-based clustering, spectral clustering, and Kohonen self-organizing maps are examined for their ability to identify latent groups without prior assumptions. The contribution of this study is twofold. First, the paper presents a methodological framework for state construction incorporating suitable unsupervised learning techniques, with appropriate measures both for classification performance and Markov model accuracy. Secondly, the framework is tested on an application, resulting in a comparative analysis showing that spectral clustering and Kohonen self-organizing maps are best at capturing inherent structure. These results serve as a cornerstone in providing theoretical and methodological guidance for improving state definition in applied Markov modelling.
1 Introduction
Markov models rely on states that are homogeneous in transition probabilities, but state construction is often neglected or assumed in advance. The paper proposes a three-step approach combining supervised feature selection with unsupervised grouping to identify data-inherent states.
- Markov chains model random events over time and support applications in biology, manpower planning, and economic analysis.
- Neglected state construction can violate transition-probability homogeneity, reducing model validity and predictive power.
- Prior state-determination research focused mainly on supervised techniques, including logistic regression and decision trees.
- The proposed methodology selects transition-relevant features, clusters observations using unsupervised methods, and merges subgroups with similar transition probabilities.Candidate clustering methods are HDBSCAN, spectral clustering, and Kohonen self-organizing maps.
2 Literature review
The literature defines homogeneous Markov states as groups whose members have similar transition probabilities, while existing state-construction and clustering approaches impose structural or tuning limitations. The review motivates unsupervised methods that can identify intrinsic, potentially non-convex groupings.
- Discrete-time, time-homogeneous Markov chains describe entities moving among a finite number of states at set time intervals.The next-state probability depends only on the current state.
- Homogeneous Subgroups: Homogeneous states contain observations with similar transition probabilities, an assumption necessary for Markov-model accuracy and predictive power.
- Homogeneous Subgroups: Existing state-construction methods split data by research-defined classes and recursively seek homogeneity using regression and hierarchical-clustering thresholds.De Feyter’s procedure balances greater homogeneity against smaller subgroup sizes.
- Homogeneous Subgroups: Decision trees use explanatory variables to maximize within-group homogeneity and between-group heterogeneity, but axis-parallel splits produce convex groups and stopping criteria can bias results.
- Clustering: Clustering seeks unlabeled patterns, but conventional approaches may assume convex or spherical groups, density distributions, or a predetermined cluster count.
- Hierarchical Density-based Clustering: HDBSCAN hierarchically refines density-based clusters using stability, requiring researchers to specify only the minimum cluster size.Its greater complexity increases calculation time.
- Hierarchical Density-based Clustering: HDBSCAN computes core and mutual-reachability distances, cuts graph connections from largest distances downward, and selects the highest-stability clustering.
- Spectral Clustering: Spectral clustering represents observations as a similarity graph and emphasizes connectivity rather than local density.The graph Laplacian is computed as L = D −W, with D containing summed node connectivity on its diagonal.
3 Metholodogy
The methodology section describes preprocessing and postprocessing around unsupervised learning techniques in a Markov-model context. These steps are intended to support effective algorithm operation and homogeneous-state formation.
- Unsupervised learning in a Markov context requires preprocessing and postprocessing for effective algorithm operation and homogeneous-state formation.The proposed methodology is illustrated in Figure 1.
3.1 Pre-processing
Pre-processing divides observations within predefined research classes, selects transition-relevant features, and prepares similarity information for clustering mixed-type data while addressing dimensionality and computational constraints.
- Class-based division: Observations are first divided according to classes inherently associated with the research problem.
- Feature selection: Feature selection is necessary because high-dimensional datasets can prevent algorithms from distinguishing clusters effectively.The paper links this difficulty to the curse of dimensionality.
- Feature selection: Random forests rank features by permutation-based importance, measuring increases in out-of-bag prediction error after feature values are permuted.
- Feature selection: VSURF returns interpretation and prediction-oriented variable subsets, and stability analysis is required across different values of its input factor.
- Distance preparation: Spectral clustering and HDBSCAN use similarity matrices constructed from observation distances, with Gower distance supporting mixed categorical and continuous data.The described mixed-data weighting approach adjusts numerical and categorical feature contributions.
- Dimensionality reduction: UMAP is proposed to reduce the Gower distance matrix for HDBSCAN, while its effects on global structure and the final model are analyzed.The passage notes that UMAP preserves local neighborhoods but may distort distances between well-separated groups.
3.2 Unsupervised Learning
After feature selection and data preparation, three unsupervised techniques separately divide predefined classes into subgroup sets for comparative analysis.
- 3.2 Unsupervised Learning: The analysis applies density-based clustering, spectral clustering, and Kohonen self-organizing maps to separate classes into subgroups.
- 3.2 Unsupervised Learning: Each technique produces its own subgroup collection, denoted SG_HD, SG_SC, or SG_SOM, for the classes in the dataset.
- 3.2 Unsupervised Learning: The resulting subgroup sets support a comparative analysis across the three unsupervised learning techniques.
3.3 Post-hoc Subgroup Merging and Validation
The framework post-processes technique-specific subgroups by merging those with similar transition behavior, producing final homogeneous-state divisions for comparison.
- 3.3 Post-hoc Subgroup Merging and Validation: Subgroups are evaluated using transition probabilities because groups with similar transition behavior are not relevant as separate final Markov states.
- 3.3 Post-hoc Subgroup Merging and Validation: Merging reduces the number of parameters to estimate and may help limit overfitting, thereby improving generalizability.
- 3.3 Post-hoc Subgroup Merging and Validation: Graph-based maximal cliques identify sets of pairwise transition-similar subgroups, with overlapping cliques resolved by highest internal cohesion.Internal cohesion is measured by the lowest average pairwise distance between observations in the original distance matrix.
- 3.3 Post-hoc Subgroup Merging and Validation: The final framework is presented as a flowchart of the proposed clustering and validation procedure.
3.4 Accuracy Measures
Accuracy measures assess covariance-matrix fit, balance fit against model complexity, compare competing models through Akaike evidence, and test distinguishability using the Vuong statistic.
- χ2 fit assessment: Markov-model fit is assessed by comparing the empirical covariance matrix S with the model-implied covariance matrix Σ(θ̂).The χ2 statistic evaluates the significance of the estimated covariance matrix.
- χ2 fit assessment: A non-significant χ2 test with p > 5% indicates insufficient evidence of differences between the empirical and model-implied covariance matrices.
- Akaike information criteria: AIC evaluates model fit while penalizing the number of estimated parameters, addressing the trade-off between approximation and estimation error.
- Akaike information criteria: Differences between AIC values indicate model-selection uncertainty, and differences between 2 and 7 should not automatically dismiss alternative models.The cited cutoffs are described as non-unambiguous.
- Akaike information criteria: Akaike weights normalize candidate models’ relative likelihoods, while evidence ratios express how much more likely the best model is than model i.
- Vuong comparison: The Vuong statistic compares non-nested models by testing whether their case-wise log-likelihood variances differ and can identify the model closest to an undefined true model.
4 Application
The application compares data-driven state constructions with class- and tree-based Markov models for academic employee grades. Spectral clustering provides the strongest overall balance between transition-flow representation and model fit, while model choice varies by grade and complexity.
- Application: The manpower dataset contains yearly records of university employees spanning six hierarchical grades, from PhD to full professor.The grades are G1 through G6, from PhD and post-doc to assistant professor, associate professor, professor, and full professor.
- Models compared: The study compares class and decision-tree states with HDBSCAN, spectral-clustering, and topology-based SOM states.HDBSCAN treats noise as a separate subgroup, while SOM units are merged through agglomerative clustering.
- Transition probabilities: Unsupervised states show more dispersed promotion probabilities than class states, indicating heterogeneity within the original grades.Spectral and HDBSCAN states have relatively similar transition probabilities in the comparison shown in Figure 6.
- Cross-validated performance: Cross-validation consistently favors spectral clustering and SOM on goodness-of-fit, with spectral clustering achieving the lowest AIC for Grades 1 and 2.For Grade 3, SOM has a substantially lower χ2 than the class model despite similar AIC; for Grade 4, spectral and SOM have the lowest χ2.
- Trade-offs: HDBSCAN represents transition flows better than class states for all grades and tree states for most grades, but its many states increase parameter complexity and AIC penalties.The model’s overfragmentation is reflected in a high number of states and many estimated parameters.
- Overall model selection: The spectral model ranks best across the full manpower system, receiving 90% of total Akaike weight and substantially more support than the alternatives.Its evidence ratio is approximately 49, 95, and 107 times larger than those of the other candidate models.
- Robustness: Removing UMAP from HDBSCAN raises χ2 from 74.55 to 99.90 while increasing estimated parameters from 162 to 198, indicating overfragmentation.The results support retaining UMAP because it preserves local structure relevant to the final state construction.
5 Discussion and Conclusion
The study combines feature selection and clustering to construct more homogeneous Markov states, using multiple model-fit measures to compare alternatives. Spectral clustering receives the strongest Akaike-weight support, while the authors emphasize measure-specific differences and further validation needs.
- Methodological contribution: The three-step methodology combines supervised feature selection, unsupervised subgrouping, and aggregation of subgroups with equal transition probabilities into final Markov states.It is designed to identify latent heterogeneity and improve homogeneity with respect to transition probabilities.
- Methodological contribution: The framework can capture complex, non-convex structures and multiple transition-relevant characteristics simultaneously, unlike consecutive splits based on one variable at a time.
- Model comparison: 90% probability: the spectral model is the best approximating model for observed transition flows according to Akaike weights.The spectral model receives the highest support among the candidate models.
- Model comparison: The Vuong test consistently selects the spectral model as preferred, but differs from AIC-based comparisons when differences between models are small.The class model is preferred over the spectral model, while the tree model is preferred over HDBSCAN in some comparisons.
- Caveats: The authors recommend using multiple model-selection measures because the Vuong test does not penalize model complexity through degrees of freedom.They also note concerns about combining estimation-based and null-hypothesis-testing approaches.
- Conclusion: The present case study suggests that employees with comparable characteristics tend to display similar transition behavior, while additional datasets are needed for validation.Dataset-specific characteristics may influence results, including a very large χ2 value for Grade 2 in the SOM model.
6 Further Research
The paper identifies several directions for extending machine-learning-based state construction in Markov models. These include optimizing preprocessing and model inputs, handling applications without inherent class divisions, and balancing predictive performance, overfitting risk, and interpretability.
- Optimization framework: Future work could optimize input parameters and preprocessing decisions to construct states that balance Markov-model fit and complexity.Suggested preprocessing options include mixed-data distance measures and scaling beyond two dimensions with UMAP.
- Class definition: Applications without an inherent class division require investigation of how the framework can help define those classes.Customer lifetime value analyses are given as an example.
- Alternative methods: Future research could also examine supervised neural networks and support vector machines for classifying observations by transition behavior.
- Practical considerations: Further work should balance predictive performance, overfitting risk, and interpretability because highly complex models may be unsuitable in practical settings.
7 Generative AI disclosure
The authors disclose using OpenAI ChatGPT (GPT-5.5) to generate and debug R and LaTeX code. They reviewed and edited the code and retain responsibility for its accuracy and integrity.
- Generative AI use: OpenAI ChatGPT (GPT-5.5) was used to generate and debug code in R and LaTeX.The authors state that they reviewed and edited the code afterward.
- Generative AI use: The authors take full responsibility for the accuracy and integrity of the code and results.
Appendix
The appendix includes tables reporting cross-validated goodness-of-fit measures and observed group sizes with stay and promotion probabilities. The reported goodness-of-fit tables distinguish overall results from results by grade and model, including analyses without UMAP.
- Goodness-of-fit tables: Table 8 reports cross-validated goodness-of-fit measures by grade and model without UMAP.χ2 and AIC values are averages across the three folds.
- Goodness-of-fit tables: Table 9 reports overall cross-validated goodness-of-fit measures across all grades without UMAP.
- State characteristics: Tables 10 and its continuation report observed group sizes and stay/promotion probabilities by grade and model.