Markov-switching decision trees

Adam, Timo; Ötting, Marius; Michels, Rouven Article — Published Version Markov-switching decision trees AStA Advances in Statistical Analysis Provided in Cooperation with: Springer Nature Suggested Citation: Adam, Timo; Ötting, Marius; Michels, Rouven (2024) : Markov-switching decision trees, AStA Advances in Statistical Analysis, ISSN 1863-818X, Springer, Berlin, Heidelberg, Vol. 108, Iss. 2, pp. 461-476, https://doi.org/10.1007/s10182-024-00501-6 This Version is available at: https://hdl.handle.net/10419/315185 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Vol.:(0123456789) AStA Advances in Statistical Analysis (2024) 108:461–476 https://doi.org/10.1007/s10182-024-00501-6 1 3 ORIGINAL PAPER Markov‑switching decision trees TimoAdam1,2· MariusÖtting2 · RouvenMichels2 Received: 30 November 2022 / Accepted: 31 October 2023 / Published online: 29 May 2024 © The Author(s) 2024 Abstract Decision trees constitute a simple yet powerful and interpretable machine learning tool. While tree-based methods are designed only for cross-sectional data, we propose an approach that combines decision trees with time series modeling and thereby bridges the gap between machine learning and statistics. In particular, we combine decision trees with hidden Markov models where, for any time point, an underlying (hidden) Markov chain selects the tree that generates the corresponding observation. We propose an estimation approach that is based on the expectationmaximisation algorithm and assess its feasibility in simulation experiments. In our real-data application, we use eight seasons of National Football League (NFL) data to predict play calls conditional on covariates, such as the current quarter and the score, where the model’s states can be linked to the teams’ strategies. R code that implements the proposed method is available on GitHub. Keywords Decision trees· EM algorithm· Hidden Markov models· Time series modeling Timo Adam and Marius Ötting have contributed equally to this work. * Timo Adam [email protected] * Marius Ötting [email protected] Rouven Michels [email protected] 1 Department ofMathematical Sciences, University ofCopenhagen, Universitetsparken 5, 2100Copenhagen, Denmark 2 Faculty ofBusiness Administration andEconomics, Bielefeld University, Universitätsstraße 25, 33615Bielefeld, Germany 462 T.Adam et al. 1 3 1 Introduction Driven by an ever-increasing amount of data, machine learning has revolutionised empirical research in various fields. In many of these fields, machine learning tools have been applied to time series, e.g., in ecology (Wang 2019; Wijeyakulasuriya etal. 2020; Nathan etal. 2022), finance (Choudhry and Garg 2008; Das and Padhy 2012), and sports (Power etal. 2017; Decroos etal. 2019), to name but a few examples. However, standard machine learning tools are designed only for cross-sectional data, as they assume the observations of the response variable to be independent of each other. Moreover, as machine learning tools lack a time series component, they are not able to account for common characteristics typically found in time series, such as trends or cyclical fluctuations around these trends. In this paper, we demonstrate how to overcome such limitations by proposing a combination of decision trees and time series modeling. In particular, we combine decision trees with a versatile class of time series models, namely hidden Markov models (HMMs), where the observations are assumed to be driven by underlying (hidden) states. In practical applications, such states can serve as proxies for the state of the economy (Goodwin 1993; McCulloch and Tsay 1994; Oelschläger and Adam 2021; Adam etal. 2022), the behavioural mode of an animal (DeRuiter etal. 2017; Leos-Barajas etal. 2017, 2017b; Adam etal. 2019), or, in the context of sports, the momentum or tactics of teams (Sandholtz and Bornn 2020; Sandri etal. 2020; Ötting etal. 2021; Ötting and Karlis 2022). The state process is modeled by a Markov chain, which induces serial correlation in the observations. Adding such a time series component to machine learning tools, as we will demonstrate here for the specific case of decision trees, can improve the model’s fit, its prediction accuracy, and its interpretability. To fit such Markov-switching decision trees to time series, we consider the expectation-maximisation (EM) algorithm, which is routinely used for model fitting in HMMs (Zucchini etal. 2016). The EM algorithm alternates between an expectation (E) step, in which the states are guessed based on the current parameter estimates, and a maximisation (M) step, in which the model’s likelihood is maximised with respect to the parameters using the state guesses obtained in the previous E step. To demonstrate the usefulness of the proposed method, we present a simulation experiment and a case study from sports analytics, namely American football, a sport which has seen a steady rise in statistical analyses in recent years (see, e.g., Yam and Lopez 2019; Yurko etal. 2019, 2020; Chu etal. 2020; Dutta etal. 2020; Lopez 2020; Reyers and Swartz 2021). In particular, we model play calls, which can either be a run or a pass. Due to their intuitive interpretation, decision trees have previously been used to predict such play calls in American football (Joash Fernandes etal. 2020). In our case study, the hidden states can serve as proxies for the level of risky playing style, and covariates, such as the current score or the number of yards teams need for a new first down, are considered to build the state-dependent trees. 463 1 3 Markov-switching decision trees The paper is structured as follows: in Sect.2, we introduce HMMs as well as decision trees and outline the EM algorithm that is used for model fitting. In Sect.3, we simulate data from Markov-switching decision trees and demonstrate the feasibility of our approach by comparing misclassification rates between fitted Markovswitching decision trees and standard decision trees. In Sect. 4, we present our case study of play call predictions, where we compare the predictive power of the proposed method to standard decision trees. R code that implements the proposed method is available on GitHub.1 2 Methods In this section, we provide a brief introduction to HMMs and decision trees (Sect.2.1) and introduce the EM algorithm that is used for model fitting (Sect.2.2). 2.1 Model formulation anddependence structure HMMs comprise two stochastic processes; the observation process, {Yt}t=1,…,T , and the underlying (hidden) state process, {St}t=1,…,T . The latter is modeled by an N-state, first-order Markov chain. The N×N transition probability matrix (t.p.m.), 𝚪 , summarises the state transition probabilities, 𝛾ij =Pr(St=j∣St−1=i),i,j=1, …,N . For the start of the time series, one can assume the Markov chain to be in its stationary distribution, such that the initial distribution 𝜹 is given by the solution to 𝜹𝚪=𝜹 subject to ∑N i=1 𝛿 i = 1 . If this assumption is not being made, then the N−1 (free) parameters in 𝜹 need to be estimated. In basic HMMs, the state that is active at time t, St , selects one of N possible distributions that generates the corresponding observation, Yt . For instance, for binary variables, a standard choice for the state-dependent distributions would be different Bernoulli distributions, where the success probabilities vary across the states. In this paper, we do not make any such parametric distributional assumption, and instead let the Markov chain select one of N possible decision trees that generates the corresponding observation. The dependence structure of Markov-switching decision trees is illustrated in Fig.1. For fitting the state-dependent trees, we use the CART algorithm proposed by Breiman et al. (1984), where we focus on classification trees. In particular, we use the Gini index as impurity measure to select the splitting variables and the split points. For each state i, we thus obtain a tree consisting of Mi regions, Rmi,i=1, …,N,mi=1, …,Mi , which is built using p covariates, xt=(xt1,…,xtp) . To select the tree size, we consider standard procedures, such as stopping the 1 See https:// github. com/ timoa dam/ Marko vSwit ching Decis ionTr ees. 464 T.Adam et al. 1 3 splitting only when a minimum node size is reached or using cost-complexity pruning as proposed by Breiman etal. (1984). 2.2 Model fitting using theEM algorithm 2.2.1 The complete‑data log‑likelihood We start by representing the state sequence {St}t=1,…,T by the indicator variables ui(t)=I(St=i) and vi,j(t)=I(St−1=i,St=j) , i,j=1, …N , t=1, …,T . The joint log-likelihood of the observations and the states (i.e., the complete-data log-likelihood; CDLL) can then be written as where pi(yt)=Pr(Yt=yt∣St=i) and l (𝜽)=log ( 𝛿s1 T ∏ t=2 𝛾st−1,st T ∏ t=1 Pr(Yt=yt∣St=st) ) =log(𝛿s1)+ T ∑ t=2 log(𝛾st−1,st)+ T ∑ t=1 log(pst(yt)) = N ∑ i=1 ui(1)log(𝛿i)+ N ∑ i=1 N ∑ j=1 T ∑ t=2 vi,j(t)log(𝛾i,j)+ N ∑ i=1 T ∑ t=1 ui(t)log ( pi(yt) ) Fig. 1 Dependence structure of Markov-switching decision trees. The (hidden) state that is active at time t, St , selects one of N (in this illustration, N=2 ) possible decision trees that generates the corresponding observation, Yt (in this illustration, Yt∈{F, S} (i.e., “success” or “failure”) is a binary outcome) 465 1 3 Markov-switching decision trees with mi∈1, …,Mi being the node for which x t ∈R m i and n m i denoting the number of observations in region R m i for the tree of statei. In other words, Eq. (1) gives the probability that Yt equals k in state i by calculating the proportion of class k observations for the node mi that is uniquely determined by xt . Note that the CDLL consists of three separate summands, each of which only depends on (i) the initial state probabilities, (ii) the transition probabilities, and (iii) the probabilities of the observations under the state-dependent trees, which considerably simplifies the maximisation within the M-step. 2.2.2 The E‑step The E-step consists of computing the conditional expectations of the indicator variables that represent the state sequence. To compute these, we require the forward and backward probabilities. The forward probabilities, which are denoted by 𝛼t(i)=Pr(Y1=y1,…,Yt=yt,St=i) , are summarised in the row vectors 𝜶t=(𝛼t(1),…, 𝛼t(N)) , which can be evaluated via the forward algorithm by applying the recursion t=2, …,T , with N×N diagonal matrix P( y t)=diag( p 1( y t),…, p N( y t)) . The backward probabilities, which are denoted by 𝛽t( j )= f ( y t+1,…, y T∣ S t= j ) , are summarised in the row vectors 𝜷t=( 𝛽 t(1),…, 𝛽 t( N )) , which can be evaluated via the backward algorithm by applying the recursion t=T−1, …,1 , with P(yt+1) as defined above. We let 𝛼 [m] t(i) and  𝛽[m] t(j) denote the forward and backward probabilities obtained in the m-th iteration, which are computed using the estimates obtained in the (m−1) -th iteration (or initial values in the first iteration). The m-th E-step involves the computation of the conditional expectations of the indicator variables given the current parameter estimates and fitted, state-dependent trees. • Since ui(t)=Pr(St=i∣y1,…,yT)=f(y1,…,yt,St=i)f(yt+1,…,yT∣St=i)∕f(y1,…,yT) and f(y 1 ,…,y T )= ∑N i=1 f(y 1 ,…,y T ,S t =i ) , it follows from the definition of the forward and backward probabilities that (1) Pr (Yt=k∣St=i)= 1 nmi ∑ j=1, …,T∶ x j ∈R mi I(yj=k) , 𝜶 1 =𝜹P(y 1 ); 𝜶t=𝜶t−1 𝚪P (yt), 𝜷 T =1; 𝜷 ⊤ t =𝚪P(y t+1 )𝜷⊤ t+1, 466 T.Adam et al. 1 3 i=1, …,N , t=1, …,T . • Since vi,j(t)= Pr (St−1=i , St=j∣y1 , … , yT)=f(y1 , … , yt−1 , St−1=i) Pr(St=j∣St−1=i) Pr (yt , … , yT∣St=j)∕ Pr (y1 , … , yT) , it follows from the definition of the forward, backward, and transition probabilities that i,j=1, …,N , t=1, …,T . Note that, while the indicator variables are deterministic, the above conditional expectations are probabilities: Eq. (2) denotes the probability of state i being active at time t, while Eq. (3) denotes the probability of switching from state i to state j at time t. 2.2.3 The M‑step The m-th M-step involves the maximisation of the CDLL with the indicator variables replaced by their current conditional expectations [see Eq. (2)] with respect to the model parameters: • As only the first term in the CDLL depends on 𝛿i , using a Lagrange multiplier to ensure that ∑N i=1  𝛿 [m] i = 1 results in i=1, …,N . • Similarly, as only the second term in the CDLL depends on 𝛾i,j , using a Lagrange multiplier to ensure that ∑N j=1 𝛾 [m] i,j = 1 , i=1, …,N , results in i,j=1, …,N . • As only the third term in the CDLL depends on Eq. (1), the optimisation problem effectively reduces to maximising the joint probability of the observations under the state-dependent trees, where the t-th observation is weighted by the u[m] i (t ) ’s. Thus, we can exploit existing algorithms, namely the CART algorithm (Breiman (2)  u [m] i(t)= 𝛼 [m] t(i)  𝛽 [m] t(i) ∑ N k=1 𝛼 [m] T (k) , (3)  v [m] i,j(t)= 𝛼 [m] t−1(i)𝛾 [m−1] i,jpj(yt) 𝛽 [m] t(j) ∑ N j=1 𝛼 [m] T (j) ,  𝛿 [m] i= u [m] i(1) ∑ N i=1 u[m] i (1) =u[m] i(1) , 𝛾 [m] i,j= ∑ T t=2v [m] i,j(t) ∑ N k=1∑ T t=2 v[m] i,k (t) , 467 1 3 Markov-switching decision trees etal. 1984), to fit the state-dependent trees, where the observations are weighted according to Eq. (2) (i.e., the state-dependent trees are re-fitted in each M-step using the weights that were obtained in the previous M-step). Such weighting of the observations within the CART algorithm is implemented in the R package rpart (Therneau and Atkinson 2019). The EM algorithm alternates between the E- and the M-step until some convergence criterion is satisfied. Here, we consider the absolute difference between the CDLLs obtained in two consecutive iterations and stop the algorithm if it falls below 10−3 . 3 Simulation experiment As decision trees are a non-parametric machine learning tool, it is not feasible to compare estimated parameters with true parameters, as is typically done in a regression context. However, we can explore the viability of Markov-switching decision trees by simulating data from a Markov-switching decision tree and comparing the performance of fitted trees with and without a Markovian structure. Specifically, we simulate 100 time series, each consisting of 2000 observations. For each time series, we generate binary observations, denoted as Yt , where Yt can take values from the set {F, S} (representing “success” or “failure”) based on a Markov-switching decision tree with initial state distribution 𝜹=(0.5, 0.5) , t.p.m. a uniformly distributed covariate x1∈[0, 20] , and a categorical covariate x2∈{1, …,4} . Figure2 displays the true data-generating trees along with the results obtained from fitted standard decision trees and Markov-switching decision trees for a single simulation run. In the bottom panel, it is evident that the Markov-switching decision trees effectively capture the splits of the data-generating trees. Furthermore, the success probabilities estimated in the leaf nodes closely align with those of the datagenerating process. The means of the estimated diagonal values of the t.p.m. are calculated as 0.949 and 0.948 for 𝛾11 and 𝛾22 , respectively. These estimates are remarkably close to the corresponding true values of 0.95. In contrast, as depicted in the middle panel of Fig.2, standard decision tree fail to identify the correct thresholds for the splits and do not accurately estimate the “success” and “failure” probabilities. This visual assessment is substantiated by comparing the predictive performance of both approaches using out-of-sample observations. For forecasting observations in the Markov-switching context, we employ the standard hidden Markov model (HMM) framework to generate one-step-ahead forecasts (Zucchini etal. 2016). The resulting misclassification rates across 100 simulation runs are presented in Fig.3. It is evident that the predictive performance of the Markov-switching decision trees (median misclassification rate: 0.115) surpasses that of the standard decision trees (median misclassification rate: 0.275) by a substantial margin. In addition, due to 𝚪 = ( 0.95 0.05 0.05 0.95 ), 468 T.Adam et al. 1 3 the lack of flexibility caused by the missing time-series component, the standard decision trees are, on average, deeper than the Markov-switching trees. While the average tree depth obtained for the former is 2.8, the average tree depth obtained for the latter is 2.1. Hence, the average depth of the Markov-switching trees is much closer to the true depth (i.e., 2), which is due to the fact that the standard decision trees are less flexible and therefore require more splits. In this simple simulation experiment, we demonstrated potential pitfalls associated with the application of decision trees to time series that exhibit serial correlation and state-switching over time. Without incorporating this time series structure, standard decision trees fail to deliver precise forecasts of future observations. On the contrary, Markov-switching decision trees appropriately account for state-switching over time, Fig. 2 True data-generating trees (top), example fitted standard decision trees (middle), and example fitted Markov-switching decision tree (bottom). When the state process is in state 1, a “success” outcome is generated with a probability of 95% for x1 < 5 if x2=1 and for x1≥5 if x2=1 . When the state process is in state 2, this pattern is reversed, i.e., the above combination of higher and lower values most likely leads to a “failure” outcome 475 1 3 Markov-switching decision trees Das, S.P., Padhy, S.: Support vector machines for prediction of futures prices in Indian stock market. Int. J. Comput. Appl. (2012). https:// doi. org/ 10. 5120/ 5522- 7555 Decroos, T., Bransen, L., VanHaaren, J., etal.: Actions speak louder than goals: valuing player actions in soccer. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp 1851–1861. https:// doi. org/ 10. 1145/ 32925 00. 33307 58 (2019) DeRuiter, S.L., Langrock, R., Skirbutas, T., etal.: A multivariate mixed hidden Markov model for blue whale behaviour and responses to sound exposure. Ann. Appl. Stat. 11(1), 362–392 (2017). https:// doi. org/ 10. 1214/ 16- AOAS1 008 Dutta, R., Yurko, R., Ventura, S.L.: Unsupervised methods for identifying pass coverage among defensive backs with NFL player tracking data. J. Quant. Anal. Sports 16(2), 143–161 (2020). https:// doi. org/ 10. 1515/ jqas- 2020- 0017 Goodwin, T.H.: Business-cycle analysis with a Markov-switching model. J. Bus. Econ. Stat. 11(3), 331– 339 (1993). https:// doi. org/ 10. 2307/ 13919 58 Heiny, E.L., Blevins, D.: Predicting the Atlanta Falcons play-calling using discriminant analysis. J. Quant. Anal. Sports 7(3), 2 (2011). https:// doi. org/ 10. 2202/ 1559- 0410. 1230 Joash Fernandes, C., Yakubov, R., Li, Y., etal.: Predicting plays in the National Football League. J. Sports Anal. 6(1), 35–43 (2020). https:// doi. org/ 10. 3233/ JSA- 190348 Langrock, R., Kneib, T., Glennie, R., etal.: Markov-switching generalized additive models. Stat. Comput. 27, 259–270 (2017). https:// doi. org/ 10. 1007/ s11222- 015- 9620-3 Leos-Barajas, V., Gangloff, E.J., Adam, T., etal.: Multi-scale modeling of animal movement and general behavior data using hidden Markov models with hierarchical structures. J. Agric. Biol. Environ. Stat. 22(3), 232–248 (2017). https:// doi. org/ 10. 1007/ s13253- 017- 0282-9 Leos-Barajas, V., Photopoulou, T., Langrock, R., et al.: Analysis of animal accelerometer data using hidden Markov models. Methods Ecol. Evol. 8(2), 161–173 (2017). https:// doi. org/ 10. 1111/ 2041- 210X. 12657 Lopez, M.J.: Bigger data, better questions, and a return to fourth down behavior: an introduction to a special issue on tracking datain the national football league. J. Quant. Anal. Sports 16(2), 73–79 (2020). https:// doi. org/ 10. 1515/ jqas- 2020- 0057 McCulloch, R.E., Tsay, R.S.: Statistical analysis of economic time series via Markov switching models. J. Time Ser. Anal. 15(5), 523–539 (1994). https:// doi. org/ 10. 1111/j. 1467- 9892. 1994. tb002 08.x Nathan, R., Monk, C.T., Arlinghaus, R., etal.: Big-data approaches lead to an increased understanding of the ecology of animal movement. Science 375(6582), abg780 (2022). https:// doi. org/ 10. 1126/ scien ce. abg17 80 Oelschläger, L., Adam, T.: Detecting bearish and bullish markets in financial time series using hierarchical hidden Markov models. Stat. Modell. (2021). https:// doi. org/ 10. 1177/ 14710 82X21 10340 48 Ötting, M., Karlis, D.: Football tracking data: a copula-based hidden Markov model for classification of tactics in football. Ann. Oper. Res. (2022). https:// doi. org/ 10. 1007/ s10479- 022- 04660-0 Ötting, M., Langrock, R., Maruotti, A.: A copula-based multivariate hidden Markov model for modelling momentum in football. AStA Adv. Stat. Anal. (2021). https:// doi. org/ 10. 1007/ s10182- 021- 00395-8 Power, P., Ruiz, H., Wei, X., etal.: Not all passes are created equal: objectively measuring the risk and reward of passes in soccer from tracking data. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp 1605–1613, (2017) https:// doi. org/ 10. 1145/ 30979 83. 30980 51 Reyers, M., Swartz, T.B.: Quarterback evaluation in the national football league using tracking data. AStA Adv. Stat. Anal. (2021). https:// doi. org/ 10. 1007/ s10182- 021- 00406-8 Sandholtz, N., Bornn, L.: Markov decision processes with dynamic transition probabilities: an analysis of shooting strategies in basketball. Ann. Appl. Stat. 14(3), 1122–1145 (2020). https:// doi. org/ 10. 1214/ 20- AOAS1 348 Sandri, M., Zuccolotto, P., Manisera, M., etal.: Markov switching modelling of shooting performance variability and teammate interactions in basketball. J. R. Stat. Soc. Ser. C 69(5), 1337–1356 (2020). https:// doi. org/ 10. 1111/ rssc. 12442 Therneau, T., Atkinson, B.: Rpart: recursive partitioning and regression trees. https:// CRAN.R- proje ct. org/ packa ge= rpart, R package, version 4.1–15 (2019) Wang, G.: Machine learning for inferring animal behavior from location and movement data. Ecol. Inform. 49, 69–76 (2019). https:// doi. org/ 10. 1016/j. ecoinf. 2018. 12. 002 Wijeyakulasuriya, D.A., Eisenhauer, E.W., Shaby, B.A., etal.: Machine learning for modeling animal movement. PLoS ONE 15(7), 0235750 (2020). https:// doi. org/ 10. 1371/ journ al. pone. 02357 50 476 T.Adam et al. 1 3 Wu, J., Gunnell, E., Sun, Y.: PlayGuessr: commercial application of machine learning in football play prediction. In: CS & IT Conference Proceedings, CS & IT Conference Proceedings. (2021) https:// doi. org/ 10. 5121/ csit. 2021. 111714 Yam, D.R., Lopez, M.J.: What was lost? A causal estimate of fourth down behavior in the national football league. J. Sports Anal. 5(3), 153–167 (2019). https:// doi. org/ 10. 3233/ JSA- 190294 Yurko, R., Ventura, S., Horowitz, M.: nflWAR: a reproducible method for offensive player evaluation in football. J. Quant. Anal. Sports 15(3), 163–183 (2019). https:// doi. org/ 10. 1515/ jqas- 2018- 0010 Yurko, R., Matano, F., Richardson, L.F., etal.: Going deep: models for continuous-time within-play valuation of game outcomes in American football with tracking data. J. Quant. Anal. Sports 16(2), 163– 182 (2020). https:// doi. org/ 10. 1515/ jqas- 2019- 0056 Zucchini, W., MacDonald, I.L., Langrock, R.: Hidden Markov Models for Time Series: an Introduction Using R. Chapman & Hall/CRC, Boca Raton (2016). https:// doi. org/ 10. 1201/ b20790 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.