Algebraic Reduction of Hidden Markov Models

• 成果类型: Article
• 署名作者: Grigoletto, Tommaso; Ticozzi, Francesco
• 署名单位: University of Padua
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3279209
• 发表日期: 2023
• 页码: 7374-7389
• 关键词: Algebraic methods; Linear systems; Markov processes; Model reduction

摘要

The problem of reducing a hidden Markov model (HMM) to one of smaller dimension that exactly reproduces the same marginals is tackled by using a system-theoretic approach. Realization theory tools are extended to HMMs by leveraging suitable algebraic representations of probability spaces. We propose two algorithms that return coarse-grained equivalent HMMs obtained by stochastic projection operators: the first returns models that exactly reproduce the single-time distribution of a given output process, while in the second, the full (multitime) distribution is preserved. The reduction method exploits not only the structure of the observed output but also its initial condition, whenever the latter is known or belongs to a given subclass. Optimal algorithms are derived for a class of HMMs, namely observable ones.