Low-Rank Tensors for Multi-Dimensional Markov Models

Madeline Navarro 1 , Sergio Rozada 2 , Antonio G. Marques 2 , Santiago Segarra 1 · 2024

Read Low-Rank Tensors for Multi-Dimensional Markov Models by Madeline Navarro 1 , Sergio Rozada 2 , Antonio G. Marques 2 , Santiago Segarra 1 (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-02098.txt.

Description

Abstract This work presents a low-rank tensor model for multi-dimensional Markov chains . A common approach to simplify the dynamical behavior of a Markov chain is to impose low-rankness on the transition probability matrix. Inspired by the success of these matrix techniques, we present low-rank tensors for representing transition probabilities on multi-dimensional state spaces.

Catalog record

CREATORMadeline Navarro 1 , Sergio Rozada 2 , Antonio G. Marques 2 , Santiago Segarra 1
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-02098

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Low-Rank Tensors for Multi-Dimensional Markov Models Thanks: This work was partially supported by the NSF under award CCF-2340481, the Spanish AEI PID2022-136887NB-I00 and the Community of Madrid via the ELLIS Madrid Unit. Research was sponsored by the Army Research Office and was accomplished under Grant Number W911NF-17-S-0002. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Office or the U.S. Army or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. Emails: [email protected] , [email protected] , [email protected] , [email protected] Madeline Navarro 1 , Sergio Rozada 2 , Antonio G. Marques 2 , Santiago Segarra 1 Abstract This work presents a low-rank tensor model for multi-dimensional Markov chains . A common approach to simplify the dynamical behavior of a Markov chain is to impose low-rankness on the transition probability matrix. Inspired by the success of these matrix techniques, we present low-rank tensors for representing transition probabilities on multi-dimensional state spaces. Through tensor decomposition, we provide a connection between our method and classical probabilistic models. Moreover, our proposed model yields a parsimonious representation with fewer parameters than matrix-based approaches. Unlike these methods, which impose low-rankness uniformly across all states, our tensor method accounts for the multi-dimensionality of the state space. We also propose an optimization-based approach to estimate a Markov model as a low-rank tensor. Our optimization problem can be solved by the alternating direction method of multipliers (ADMM), which enjoys convergence to a stationary solution. We empirically demonstrate that our tensor model estimates Markov chains more efficiently than conventional techniques, requiring both fewer samples and parameters. We perform numerical simulations for both a synthetic low-rank Markov chain and a real-world example with New York City taxi data, showcasing the advantages of multi-dimensionality for modeling state spaces. I Introduction Dynamic processes provide a mathematical framework for modeling the evolution of complex systems [ 1 , 2 ] . When the system and its dynamics are known, control theory has a long history of successful applications [ 3 , 4 ] . However, the dynamics are not always available and oftentimes probabilistic, and they must instead be estimated from sampled trajectories. Learning the dynamics of complex systems is challenging due to non-linear behavior, the presence of uncertainties , high dimensionality, and data scarcity [ 5 ] . Assuming specific properties of the system can render the problem tractable. In this work, we rely on two assumptions: Markovianity, where future behavior relies only on the current state of the system, and low-rankness [ 6 ] , where the system dynamics can be represented by a small set of hidden variables [ 7 ] . Low-rank methods are widely used for learning the transition probabilities of Markov systems, which can be represented via probability transition matrices. When the full matrix is known, low-rank techniques enable compression for lower-dimensional models [ 8 , 9 ] . Moreover, low-rankness has shown success in estimating an unknown probability matrix from samples, a classical problem in estimation theory [ 10 , 11 ] . Markov chains pose a challenging case, where samples within a trajectory of observed states are typically correlated. Many works propose low-rank Markov transition matrix estimation for a simpler problem that is feasible for limited samples [ 12 , 13 , 14 ] . Beyond practical considerations, the concept of low-rankness arises naturally when transitions occur in a low-dimensional hidden space, such as for hidden Markov chains [ 15 , 16 , 17 ] . However, past literature does not fully exploit the ubiquitous multi-dimensionality of state spaces. Tensors provide natural models for transition probabilities between multi-dimensional states, where tensor dimensions correspond to those of the state space [ 18 , 19 , 20 ] . By considering the tensor to be low-rank, we postulate a parsimonious model that also deals with the curse of dimensionality. We thus leverage the notion of low-rankness for tensors to formulate an interpretable model of the transition probabilities, both for the entire state space and for each dimension. Previous works exploit tensor low-rankness for learning Markov models via higher-order moments [ 21 , 22 , 23 ] , for locally-interacting Markov chains [ 24 , 25 , 26 , 27 ] , and for value functions of multi-dimensional Markov decision processes [ 28 , 29 , 30 , 31 , 32 ] . However, this is the first work to use low-rank tensors for modeling transitions in such spaces. Moreover, we consider the practical task of estimating a transition tensor from trajectories via a provably convergent optimization approach. Our contributions are as follows. C1 We propose a tensor-based probabilistic model for Markov chains on multi-dimensional state spaces, which provides a link between probabilistic models and low-rank tensor decompositions. C2 We present an optimization-based approach to estimate a low-rank Markov transition tensor from trajectories, which enjoys convergence when solved with alternating minimization. C3 We demonstrate the advantages of tensors for modeling Markovian systems and the viability of their estimation through synthetic and real-world simulations. II Tensor low-rank model In this section, we first relate tensors to Markov models. Then, we introduce our probabilistic tensor model, for which we describe the consequences of tensor low-rankness. II-A Preliminaries We consider an ergodic Markov chain with a finite D -dimensional state space {\mathcal{S}}:={\mathcal{S}}_{1}\times\cdots\times{\mathcal{S}}_{D} , where {\mathcal{S}}_{d}:=[I_{d}]=\{1,2,\dots,I_{d}\} for every d\in[D] . For each {\mathbf{s}},{\mathbf{s}}^{\prime}\in{\mathcal{S}} , the transition probability p({\mathbf{s}}^{\prime}|{\mathbf{s}}) is the conditional probability of transitioning to state {\mathbf{s}}^{\prime} from state {\mathbf{s}} . Learning a Markov model is equivalent to estimating the transition distribution p . Since we assume ergodicity, the Markov model has a unique stationary distribution \pi , where \pi({\mathbf{s}}) is the probability of being in the state {\mathbf{s}}\in{\mathcal{S}} . Additionally, let the joint probability distribution be q , where q({\mathbf{s}},{\mathbf{s}}^{\prime})=p({\mathbf{s}}^{\prime}|{\mathbf{s}})\pi({\mathbf{s}}) models the likelihood of the co-occurrence of two consecutive states {\mathbf{s}},{\mathbf{s}}^{\prime}\in{\mathcal{S}} . We exploit our knowledge of the multi-dimensional state space by arranging the probabilities p({\mathbf{s}}^{\prime}|{\mathbf{s}}) in a tensor format. Specifically, consider the state {\mathbf{s}}\in{\mathcal{S}} , which is a vector {\mathbf{s}}=[s_{1},\dots,s_{D}]^{T} for s_{d}\in{\mathcal{S}}_{d} . We can thus arrange the transition probabilities p(s^{\prime}_{1},\dots,s^{\prime}_{D}|s_{1},\dots,s_{D}) into the transition probability tensor {\hbox{\hskip 3.93053pt\hskip-3.93053pt\hbox{$\mathbf{P}$}\hskip-3.93053pt\hskip 0.0pt\raisebox{-1.2pt}{\hbox{\rule{3.44444pt}{0.32289pt}}}\hskip 0.0pt\hskip 3.93053pt}}\in[0,1]^{I_{1}\times\dots\times I_{D}\times I_{1}\times\dots\times I_{D}} , where {\hbox{\hskip 3.93053pt\hskip-3.93053pt\hbox{$\mathbf{P}$}\hskip-3.93053pt\hskip 0.0pt\raisebox{-1.2pt}{\hbox{\rule{3.44444pt}{0.32289pt}}}\hskip 0.0pt\hskip 3.93053pt}}({\mathbf{s}},{\mathbf{s}}^{\prime})=p({\mathbf{s}}^{\prime}|{\mathbf{s}}) for every {\mathbf{s}},{\mathbf{s}}^{\prime}\in{\mathcal{S}} . Analogously, we also define the stationary probability tensor {\hbox{\hskip 4.31247pt\hskip-4.31247pt\hbox{$\mathbf{R}$}\hskip-4.31247pt\hskip 0.0pt\raisebox{-1.2pt}{\hbox{\rule{3.44444pt}{0.32289pt}}}\hskip 0.0pt\hskip 4.31247pt}}\in[0,1]^{I_{1}\times\dots\times I_{D}} for \pi and the joint probability tensor {\hbox{\hskip 4.31941pt\hskip-4.31941pt\hbox{$\mathbf{Q}$}\hskip-4.31941pt\hskip 0.0pt\raisebox{-3.14444pt}{\hbox{\rule{3.44444pt}{0.32289pt}}}\hskip 0.0pt\hskip 4.31941pt}}\in[0,1]^{I_{1}\times\dots\times I_{D}\times I_{1}\times\dots\times I_{D}} for q . II-B Probabilistic Model Similar to existing works that learn Markov chains via low-rank decomposition [ 13 ] , we propose first estimating the joint distribution q , from which we derive the transition distribution p . This enables a connection between probabilistic models and low-rank tensor decompositions, as we will show. In particular, we model the joint probability tensor \mathbf{Q} with a low-rank tensor decomposition. To derive the decomposition of \mathbf{Q} , we first note that any joint distribution can be represented using a naive Bayes model [ 33 ] , which assumes the existence of a hidden dimension with F possible values that generates q [ 34 , Proposition 1]

Read the complete text