1. The Reducibility of Reachable Space for Structured Hidden Markov Models
- Author
-
Man Zheng and Yoshito Ohta
- Subjects
0209 industrial biotechnology ,Computer science ,Linear system ,Stochastic matrix ,Markov process ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,020206 networking & telecommunications ,02 engineering and technology ,Matrix decomposition ,symbols.namesake ,020901 industrial engineering & automation ,Computer Science::Sound ,0202 electrical engineering, electronic engineering, information engineering ,symbols ,Graph (abstract data type) ,Hidden Markov model ,Realization (systems) ,Algorithm ,Subspace topology - Abstract
The order of a hidden Markov model (HMM) is an index of the complexity and is closely related to the reachable subspace in the state of the model. When the reachable subspace is not the whole space, there exists a reduced-order quasi hidden Markov model (quasi-HMM), which may not satisfy the nonnegative constraints, equivalent to the original HMM. Such an HMM will be called reachable-space reducible. In this paper, we explore a necessary and sufficient condition for the reachable-space reducible HMM. The condition indicates that if the transition matrix and the observation matrix jointly have a certain structured non-zero pattern, then the HMM is reachable-space reducible. We show that the connection graph of the HMM characterizes the condition. Subsequently, we prove that the HMM satisfying this particular structure always has a reduced-order HMM realization satisfying the nonnegative constraints. Some examples are given to demonstrate our results.
- Published
- 2020
- Full Text
- View/download PDF