Modeling dynamic substate chains among massive states

Abstract

This paper proposes a novel framework, named HIgh-order Substate Chain (HISC) modeling, to capture the entire system dynamics underlying the transaction time series, where the transaction contains explosive states due to the combinatorics of massively observed inputs. In a practical situation, the objective system consists of multiple subsystems where a state of each subsystem is represented by a subset of the transaction. Thus, a transaction observed from the entire objective system is considered to be a collection of such subsets, and each subset is called a “substate” of the objective system. The basic task of our HISC modeling is to efficiently and simultaneously identify the substates and their transitions embedded in the time series. For application, the methods for system dynamics simulation and substate prediction by using the HISC model have been developed. Its significant performance has been confirmed through the evaluation on synthetic data, the comparisons with some High-order Markov chain models in the state of the art and the application to practical data analysis.