{'fraction_non_alphanumeric': 0.06982371240926374, 'fraction_numerical': 0.026961631524369166, 'mean_word_length': 4.719367588932807, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exact Bayesian restoration in non-Gaussian Markov-switching Trees

Let X1:N=(X1,…,XN) be a continuous hidden random process, Y1:N=(Y1,…,YN) a continuous observed process and R1:N=(R1,…,RN) a discrete random process taking its values in a finite set. The chain R usually models the random changes of regime, or so-called switches of the distribution of (Xn,Yn). The three chains are linked via some probability distribution p(x1:N,r1:N,y1:N). Bayesian restoration consists in efficiently computing a posterior probability function (pdf) of interest, namely p(xk|y1:n) for some values of k and n. 
 
It is well known that the exact (recursive) computation of p(xk|y1:n) is not feasible in many commonly used stochastic models and one needs to resort to approximations. This is the case for instance of the so-called jump-Markov state-space system, in which Bayesian restoration is NP-hard, and for which different approximations (either deterministic or Monte-Carlo based) must be used [1-2]. 
 
However, in most situations we are actually interested by some moment E(g(xk)|y1:n), and in particular the conditional expectation E(xk|y1:n), rather than by pdf p(xk|y1:n) itself. A particular class of stochastic dynamical models with Markov regime has been recently developed [3], in which the conditional expectation can be exactly computed, with complexity linear in time. The key property of this model is that (R,Y) is a Markov Chain, which enables exact Bayesian restoration. 
 
In this paper we extend this model to Markov Trees, which are widely used in multiresolution analysis and multiscale algorithms (see e.g. tutorial [4]). Let the Triplet Markov Tree defined by : 
(1) (RS,YS) is a Markov Tree 
(2) Xs=Fs-(Rs-,Y s-)X s- +W s- , 
where S={S1,…,Sn} is the set of all the generations of the tree, s is a given node and s- its unique parent. Noises Ws are random zero-mean vectors, mutually independent and independent of X, R and Y. In the context of this particular model (1)-(2) we propose an exact calculation of the filtering and predictive conditional expectations by an algorithm with computational cost linear in the number of nodes of the tree. 
 
[1] J. K. Tugnait, “Adaptive estimation and identification for discrete systems with Markov jump parameters”, IEEE Transactions on Automatic Control, AC-25, pp. 1054-1065, 1982. 
 
[2] O. Zoeter and T. Heskes, “Deterministic approximate inference techniques for conditionally Gaussian state space models”, Statistical Computation, 16, pp. 279-292, 2006. 
 
[3] W. Pieczynski, “Exact calculation of optimal filter in semi-Markov switching model”, Fourth World Conference of the International Association for Statistical Computing (IASC 2008), December 5-8, Yokohama, Japan, 2008. 
 
[4] A.S.Willsky, “Multiresolution Markov Models for Signal and Image Processing”, Proceedings of the IEEE, Vol. 90, N. 8, pp. 1396-1458, August 2002