{'fraction_non_alphanumeric': 0.04131888948085006, 'fraction_numerical': 0.011128869946131534, 'mean_word_length': 4.559065482066469, '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': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Filtering for Aggregate Hidden Markov Models with Continuous Observations

We consider a class of filtering problems for large populations where each individual is modeled by the same hidden Markov model (HMM). In this paper, we focus on aggregate inference problems in HMMs with discrete state space and continuous observation space. The continuous observations are aggregated in a way such that the individuals are indistinguishable from measurements. We propose an aggregate inference algorithm called continuous observation collective forward-backward algorithm. It extends the recently proposed collective forward-backward algorithm for aggregate inference in HMMs with discrete observations to the case of continuous observations. The efficacy of this algorithm is illustrated through several numerical experiments.


I. INTRODUCTION
Hidden Markov Models (HMMs) [1] are widely used in the systems and control community to model dynamical systems in areas such as robotics, navigation, and autonomy. An HMM has two major components, a Markov process that describes the evolution of the true state of the system and a measurement process corrupted by noise. One critical task in HMMs is to reliably estimate the state using the available noisy measurements, known as inference or filtering. Over the years, many filtering algorithms have been proposed. The most well-known one could be the Kalman Filter [2], which is optimal for HMMs with Gaussian transition probability and Gaussian measurement noise. Several other well-known algorithms include the forward-backward algorithm [1] for discrete time discrete state HMMs and the Wonham algorithm [3] for continuous time discrete state HMMs with Gaussian measurement noise.
Recently a new class of filtering problems for large populations with aggregate measurements has attracted much attention [4], [5], [6]. In these filtering problems with aggregate observations, instead of individual measurements, only aggregate population-level data in the form of counts or contingency table is available [4]. Such scenarios may occur due to privacy or economic reasons. For instance, in the study of animal flocking, it is too expensive, if not impossible, to track each individual. Aggregate measurements from surveillance cameras or other sensors are instead used. Another timely example is the modeling of pandemic. In such studies, the goal is to use available testing data to predict the evolution Filtering for large population is a difficult task. The lack of individual measurement makes it even more challenging, and most of the standard algorithms such as the forward-backward algorithm for HMMs are no longer applicable. A recent framework developed to address aggregate inference problems is the collective graphical models (CGMs). Briefly, a CGM is a graphical model for the collective dynamics of a population. Within the CGM framework, several algorithms have been proposed for aggregate inference including approximate MAP inference [7], non-linear belief propagation [8] and Betheregularized dual averaging [9]. Several other recent works on filtering with aggregate observations include [10], [11], [6], [12].
In [5], [6] we proposed a novel algorithm, Sinkhorn belief propagation (SBP), for addressing aggregate filtering problems. It is built upon the connection [13], [14] between multimarginal optimal transport (MOT) [15], [16], [17] and inference in probabilistic graphical models [18] with fixed marginal constraints. When used in aggregate inference problems for HMMs, it is under the name collective forward-backward (CFB) algorithm to reflect its similarity and connections to the standard forward-backward algorithm. However, all the previous mentioned methods for aggregate inference only account for discrete observations. The goal of this work is to establish a counterpart of collective forward-backward (CFB) algorithm that is applicable to aggregate HMMs with continuous observations.
In this work, we propose continuous observation collective forward-backward algorithm (CO-CFB) to achieve this goal. The CO-CFB is closely related to the CFB algorithm for HMMs with discrete observations. The latter can be readily extended to HMMs with continuous observation but it leads to an algorithm which is not directly implementable. Rewriting a key step in it in terms of expectation circumvents this difficulty, and we arrive at the CO-CFB that only uses samples from the aggregate observations. Just like CFB, CO-CFB also exhibits convergence guarantees. We remark that although CO-CFB is developed for HMMs, it can be extended to more general graphs.
The rest of the paper is organized as follows. In Section II, we review basis concepts in HMMs, aggregate inference and a previous algorithm for aggregate inference. In Section III, we present the CO-CFB algorithm, where several properties of it and its connections to other algorithms are also discussed.
arXiv:2011.02521v2 [stat.ML] 6 Nov 2020 We demonstrate the efficacy of our algorithm using several numerical examples in Section IV. This is followed by a concise conclusion in Section V.

II. BACKGROUND
In this section, we provide a brief introduction to HMMs and present existing results for aggregate inference in HMMs including the CFB algorithm.

A. Hidden Markov Models
An HMM is a Markov process accompanied by observation noise. It consists of a sequence of unobservable states X t (also known as hidden states) and another sequence O t whose behavior depends on X t . Here X t and O t are random variables taking values from X and O respectively. In general, both X and O can be either finite sets or infinite sets. In this work, we assume X to be a set with d elements throughout.
An HMM is characterized 1 by the distribution π(x 1 ) of the starting state X 1 , the transition probability p(x t+1 |x t ), and the observation model p(o t |x t ). The joint probability distribution over trajectories of T steps reads where x t ∈ X denotes a realization of X t , o t ∈ O denotes a realization of O t , and τ = {x 1 , o 1 , · · · , x t , o t , · · · , x T , o T } denotes a sample trajectory. A HMM can also be understood as a special case of probabilisitic graphical models [18]; its graphical structure is depicted in Figure 1. One of the most important problems in HMMs is Bayesian inference where the goal is to calculate the posterior distributions of the hidden states X t given a sequence of observations. This is also known as filtering [1] in systems and control community. A well-known and efficient algorithm for this task is the standard forward-backward algorithm (summarized in Algorithm 1). It relies on the following factorization (4)

B. Aggregate Hidden Markov Models
Aggregate HMMs [8], [6] deal with the problems of estimating the behavior of a collection of indistinguishable HMMs based on aggregate observations. Assume the observation space O is a finite set. Given M trajectories {τ (1) , T }, sampled from the same HMM, the associated aggregate HMM is concerned with the aggregate quantities n = {n t ,ñ t , n tt ,ñ tt } over the entire population defined bỹ where I denotes the indicator function. These quantities represent the counts of M realizations of HMM taking specific values. Clearly, n ∈ L Z M , the integer-valued scaled local Each vertical plane stands for one sample trajectory from the underlying HMM. The blue nodes represent aggregate observations, and red nodes represent aggregate hidden states.
polytope [8], that is, the entries of n are all integers and they satisfy the following constraints The HMMs are aggregate in the sense that they are indistinguishable to each other. In this setting, the observations 2 are y t with y t (o) denoting the number of trajectories such that o (m) t = o, imposing the constraintsñ t = y t for t = 1, . . . , T . An example of aggregate HMM is illustrated in Figure 2.
The goal of inference in aggregate HMMs is to estimate the most likely n given the aggregate measurements {y t }. The exact inference is proved to be computationally infeasible [4] for problems with large T and M . It is proposed in [6] that this aggregate inference can be approximately achieved by solving a free energy minimization problem. Moreover, the approximation error vanishes as the size M of the population goes to infinity. For the sake of simplicity and without loss of generality, we normalize the observation y t as well as the statistics n by population size M , yielding a modification on Equation (6a) o∈Oñ t (o) = 1, x∈X n t (x) = 1 ∀t ∈ {1, · · · , T }. (7) Denote the local polytope (without integer constraints) described by Equation (7)-(6b)-(6c)-(6d) by M [19], and define 2 A slightly different observation has been considered in [8]. the free energy term then the aggregate inference problem is equivalent [6] to the following convex optimization problem subject toñ t = y t , ∀t ∈ {1, · · · , T }. (9b)

C. Collective forward-backward algorithm
An efficient algorithm known as collective forwardbackward (CFB) algorithm (Algorithm 2) was proposed in [6] to address Problem 1. It leverages an elegant connection between multi-marginal optimal transport [15], [16], [17] and this inference problem with fixed marginal constraints. We refer the reader to [6] for more details on Collective Forwardbackward algorithm and its connections to multi-marginal optimal transport. The solution to Problem 1 is characterized by the following theorem.
Theorem 1 ([6, Corollary 1]). The solution to the filtering problem (Problem 1) for aggregate HMM is where α t (x t ), β t (x t ), γ t (x t ), and ξ t (o t ) are the fixed points of the following updates with boundary conditions while not converged do Forward pass:

III. MAIN RESULTS
We consider filtering problems for aggregate HMMs with continuous observations. More specifically, we consider an inference problem similar to Problem 1 but assume the observation space of the underlying HMM to be a subset of the Euclidean space, i.e., O ⊂ R . An important instance of this observation model corresponds to the Gaussian measurement noise, that is, p(o t |x t ) = N (µ(x t ), Σ(x t )) with N (µ, Σ) denoting the probability density with mean µ and covariance Σ.

A. Aggregate inference with Continuous observations
We start with an ideal setting when the full distributions of the observations are given. More precisely, we assume the observations are the full distributions y t (o t ), o t ∈ O. In this scenario, the aggregate inference can again be formulated by Problem 1 with two modifications due to the continuous observations. First, the constraints (7)-(6c) become Thus, the constraint set M is described by (13a)-(6b)-(13b)-(6d). Second, the free energy objective becomes It turns out that the solution to this aggregate inference problem with continuous observation has a similar characterization as in the discrete setting as in the following Theorem.
Theorem 2. The solution to aggregate filtering problem (Problem 1) in an aggregate HMM with continuous observation is where α t (x t ), β t (x t ), and γ t (x t ) are the fixed points of the following updates with boundary conditions

B. Continuous Observation Collective Forward-Backward Algorithm
In Section III-A, we assumed that the full distributions of the observations are given, which is hardly the case in real applications. Very often only samples from these marginal distributions are accessible. Of course, one can always estimate a probability density based on these samples and then run the updates (16). The performance of this approach highly depends on that of the density estimators. Another reason that makes this approach undesirable is that the step (16c) requires numerical integration which is expensive when the dimension of observation space O is large.
A better approach is to rewrite the step (16c) as } be the aggregate observation at time t, then this update formula for γ t (x t ) can be estimated by With this update in hand, we propose continuous observation collective forward-backward (CO-CFB) algorithm (Algorithm 3) for solving aggregate inference in aggregate HMMs with continuous observations.

Algorithm 3 Continuous Observation Collective Forward-Backward (CO-CFB) Algorithm
Initialize all the messages while not converged do Forward pass: Algorithm 3 can be viewed as a counterpart of the Collective forward-backward algorithm (Algorithm 2) for aggregate HMMs with continuous observations. It is almost the same as the latter except for a small difference in the update step for γ t , replacing (11c) by (18). For a given observation }, if we restrict the observation space to o t , then the aggregate HMM with continuous observation reduces to an aggregate HMM with discrete observation over the set o t . Since all the samples in o t are equally important, the corresponding probability vector measurement y t (o t ) should be uniform over o t . That's why it doesn't appear in (18). Thus, to some extent, CO-CFB and CFB are equivalent. Remark 1. An interesting special case of HMMs with continuous observations is the aggregate Gaussian mixture models (GMMs). To see this, simply take T = 1 and let p(o 1 |x 1 ) = N (µ(x 1 ), Σ(x 1 )) be a Gaussian distribution for each x 1 ∈ X . In this case, we assume the aggregate measurement is available and we are interested in the distribution of the hidden variable n 1 . By setting T = 1 in Algorithm 3, we arrive at a closed form solution to aggregate inference problem for GMMs, which reads . Clearly, when M = 1, this is nothing but the posterior distribution of the latent variable in a GMM.

C. Connections to Bayesian inference of HMMs
As discussed in Section II-C, for HMMs with discrete observations, the aggregate inference reduces to standard Bayesian inference when the population size is M = 1, and the CFB algorithm (Algorithm 2) reduces to the standard forwardbackward algorithm (Algorithm 1). It turns out that this equivalent relation remains for HMMs with continuous observations. We remark that the Forward-backward algorithm for HMMs with continuous observation is also known as Wonham filtering [3].
With this γ t , the update rules (16a) and (16b) take the form 19b) and the expression for the marginal distributions n t becomes (20) These are exactly the same as the Forward-backward algorithm in (3)-(4).

IV. NUMERICAL EXAMPLES
We conduct several synthetic experiments to evaluate the performance of our CO-CFB algorithm. We consider HMMs with Gaussian observations. The initial state probability π is sampled uniformly over the probability simplex. The transition matrix is generated from a random permutation of a perturbed Identity matrix . A normalization is needed to ensure each row is a valid conditional distribution. The Gaussian emission probability for each hidden state is parameterized by a random mean and variance. The mean is sampled from U nif orm[−5d, 5d] and the variance is sampled from U nif orm [1,5].
We first demonstrate that our algorithm gives excellent estimation of the distributions of the hidden states of aggregate HMMs. We randomly generate M trajectories from the underlying HMM and produce the observations o t , t = 1, . . . , T based on these trajectories. We then use CO-CFB to estimate the hidden state distribution n t . This is compared to the ground truth n * t with respect to 1-norm  To evaluate the efficiency of our algorithm, we test it over different state dimension d and HMM length T . We terminate the algorithm when the relative change of error is less than 1 × 10 −5 . The result is displayed in Figure 5, from which we observe that the CO-CFB algorithm has great scalability. We also validate the linear dependency of computation complexity on population size M in Figure 6.

V. CONCLUSION
In this paper, we proposed an efficient algorithm to solve aggregate inference problems for HMMs with continuous observations. This algorithm is based on the collective forwardbackward [6] algorithm which was designed for aggregate inference for HMMs with discrete observations. The latter was extended to the setting with continuous observations in this work through a reformulation of a key step in the algorithm which enables updating using samples from the observations. Note that though our algorithm is developed for HMM models, the same idea can be generalized to a large class of graphical (21) Setting the derivatives of the Lagrangian with respect to the {n t ,ñ t , n tt ,ñ tt } to zero, we obtain the optimality conditions Define, for all t = 1, 2, · · · , T , Next we present the case with t = 2, · · · , T − 1 in (22a); the other two cases with t = 1 or t = T can be analyzed similarly. It follows directly from (22a) that Plugging (24) and (22d) into n t (x t )n t (x t ) = [ xt−1 n t−1,t−1 (x t−1 , x t )][ xt+1 n tt (x t , x t+1 )], in view of (23), we arrive at e −at(xt) ∝ α t (x t )β t (x t ).