Probabilistic Inference with Generating Functions for Poisson Latent Variable Models
Graphical models with latent count variables arise in a number of fields. Standard exact inference techniques such as variable elimination and belief propagation do not apply to these models because the latent variables have countably infinite support. As a result, approximations such as truncation or MCMC are employed. We present the first exact inference algorithms for a class of models with latent count variables by developing a novel representation of countably infinite factors as probability generating functions, and then performing variable elimination with generating functions. Our approach is exact, runs in pseudo-polynomial time, and is much faster than existing approximate techniques. It leads to better parameter estimates for problems in population ecology by avoiding error introduced by approximate likelihood computations.
The N-mixture model [22] is a simple model with a Poisson latent variable for which no exact inference algorithm is known: (a) the model, (b) the prior and posterior for = 20, ⇢ = 0.25, y 1 = 2, y 2 = 5, y 3 = 3, (c) a closed form representation of the generating function of the unnormalized posterior, which is a compact and exact description of the posterior.
probability ⇢, so each observation y k is Binomial(n, ⇢). From these observations (usually across many sites with shared ), the scientist wishes to infer n and fit and ⇢.
This model is very simple: all variables are marginally Poisson, and the unnormalized posterior has a simple form (e.g., see Figure 1b). However, until recently, there was no known algorithm to exactly compute the likelihood p(y 1:K ). The naive way is to sum the unnormalized posterior p(n, y 1 , . . . , y K ) over all possible values of n. However, n has a countably infinite support, so this is not possible. In practice, users of this and related models truncate the infinite sum at a finite value [22]. A recent paper developed an exact algorithm for the N-mixture model, but one with running time that is exponential in K [8]. For a much broader class of models with Poisson latent variables [5,7,11,15,28], there are no known exact inference algorithms. Current methods either truncate the support [5,7,11], which is slow (e.g., see [4]) and interacts poorly with parameter estimation [6,8], or use MCMC [15,28], which is slow and for which convergence is hard to assess. The key difficulty with these models is that we lack finite and computationally tractable representations of factors over variables with a countably infinite support, such as the posterior distribution in the N-mixture model, or intermediate factors in exact inference algorithms.
The main contribution of this paper is to develop compact and exact representations of countably infinite factors using probability generating functions (PGFs) and to show how to perform variable elimination in the domain of generating functions. We provide the first exact pseudo-polynomial time inference algorithms (i.e., polynomial in the magnitude of the observed variables) for a class of Poisson latent variable models, including the N-mixture model and a more general class of Poisson HMMs. For example, the generating function of the unnormalized N-mixture posterior is shown in Figure 1c, from which we can efficiently recover the likelihood p(y 1 = 2, y 2 = 5, y 3 = 3) = F (1) = 0.0025. For Poisson HMMs, we first develop a PGF-based forward algorithm to compute the likelihood, which enables efficient parameter estimatation. We then develop a "tail elimination" approach to compute posterior marginals. Experiments show that our exact algorithms are much faster than existing approximate approaches, and lead to better parameter estimation.
Related work. Several previous works have used factor transformations for inference. Bickson and Guestrin [2] show how to perform inference in the space of characteristic functions (see also [17]) for a certain class of factor graphs. Xue et al. [26] perform variable elimination in discrete models using Walsh-Hadamard transforms. Jha et al. [14] use generating functions (over finite domains) to compute the partition function of Markov logic networks. McKenzie [18] describes the use of PGFs in discrete time series models, which are related to our models except they are fully observed, and thus require no inference.
This paper generalizes the classical variable elimination algorithm in latent variable models from latent variables with finite discrete values or Gaussian distribution to latent variables with countably infinite discrete values, in particular the Poisson latent variable models. The authors observe that the key property that enables fast and exact inference is that operations like conditioning, marginalization and multiplication are "conjugate", producing exact and compact representation. For models with countably infinite factors, they appeal to probability generating function to achieve analogous "conjugacy" so that these operations boast exact and compact representation. This enables variable elimination in such models. 
The idea of probability generating function achieving similar forms of "conjugacy" as Gaussian random variables and (finite) discrete random variables is very interesting. This enables a fast and exact inference algorithm on Poisson latent variable models.         The formulation involving probability generating function does not seem to be constrained to Poisson random variables but all the simulations and real application pertain to Poisson HMM. It is unclear if there's anything special with Poisson that enables better parameter estimates. It is also unclear if there are other Poisson latent variable models other than Poisson HMMs with wide applications. Would be great to have this question answered in the article.        The comparison of the proposal, in the simulation experiments, is only with truncation in performance and with MCMC in speed. Truncation is known to perform bad when the rate is above the truncation threshold. It would be considered less than complete if it is not compared with MCMC in accuracy. MCMC is known to be particularly slow in convergence. Comparison of computational cost might as well be with truncation and variational inference. By the way, MCMC is also exact but only with sampling -- it is not approximate.         The real experiment is not too satisfying as well. It does not compare with either MCMC or truncation or present any new findings with this new proposal. Thus the merit of this proposal is unclear in real experiments as well. Apart from parameter estimation accuracy, it would also be very interesting to see predictive accuracy in real experiments because all models are wrong and it's interesting to see if some are useful.