Bayesian inference as iterated random functions with applications to sequential inference in graphical models
We propose a general formalism of iterated random functions with semigroup property, under which exact and approximate Bayesian posterior updates can be viewed as specific instances. A convergence theory for iterated random functions is presented. As an application of the general theory we analyze convergence behaviors of exact and approximate message-passing algorithms that arise in a sequential change point detection problem formulated via a latent variable directed graphical model. The sequential inference algorithm and its supporting theory are illustrated by simulated examples.
This paper gives a new perspective on the Bayesian 
      posterior updates (BPU) asa system of iterated random functions (IRF) 
      [4].By proving a general convergence theorem of IRF with semigroup 
      property,the convergence of algorithms for change point detection 
      problems [17] are analyzed.The major contributions are- to 
      establish a general convergence theory for IRF with semigroup property 
      (Theorem 1),- to cast existing (exact) algorithms for the classical 
      change point problem (CCPP) and the multiple change point problem 
      (MCPP) in the IRF framework, and prove their convergence, based on 
      Theorem 1.- to propose a fast approximate algorithm for MCPP and prove 
      its convergence,based on Theorem 1.I think this is a nice 
      paper with a significant impact.BPU is clearly a Markov chain, and so 
      it might be natural that it is analyzed in the IRF 
      framework.However, the previous convergence results on IRF are not 
      directly applicable to BPU,because the Lipschitz condition is not 
      satisfied in BPU.Instead, the authors use semigroup property of 
      BPU,and establish another type of convergence theory.I expect that 
      the established theory would have wide range of 
      applications.Pros:- A new perspective on BPU as a special case 
      of IRF with semigroup property (3) is given.- A general convergence 
      theory (Theorem 1) for IRF with semigroup property is established, 
      which might have wide range of potential applications.- A fast 
      algorithm (Section 4.1) for MCPP is proposed with its convergence 
      guarantees (Theorem 2).Cons:- The relation between the 
      theory (Theorem 2) and the experiment (Figure 1) is not clear (see the 
      first one in 'Other comments' below).- No practical application of the 
      multiple change point detection is introduced (see the second one in 
      'Other comments' below).Quality:The paper is technically 
      sound, and the claims are supported by theory.Clarity:The 
      paper is clearly written, and well-organized.Originality:The 
      perspective on BPU as IRF with semigroup property, and the obtained 
      convergence theorem (Theorem 1) are novel.Significance:The 
      found relation between BPU and IRF with semigroup property, and the 
      established convergence theory could be used by other theoreticians to 
      analyze algorithms for other problems.Other comments:- It 
      would be nice if Eqs.(19) and (20) are somehow expressed in the posterior 
      pathgraphs in Figure 1. This would make it clear that the simulation 
      supports Theorem 2.In Section 4.3, it is said that 'in some cases, 
      they might deviate for a while, but quickly snap back together once 
      the change points have occurred.'Readers cannot see this because the 
      change points are not indicated.- It would be nice if any practical 
      example of MCCP is introduced(I could not find any also in 
      [17]).Especially, I wonder in what applications the rulelambda_e = 
      min(lambda_s1, lambda_s2) is appropriate.To me, it seems more natural 
      to assume that the distribution of X_echanges both at lambda_s1 and at 
      lambda_s2.Moreover, if I understand correctly, Theorem 2 guarantees 
      the convergence after all the sensors are broken.I suppose people 
      are more interested in the convergence after any of the sensors is 
      broken, or the sensor on which a user focuses is broken.- Perhaps, 
      some thetas in and around Eq.(4) should not be bold-faced.- In Line 
      225, 'probabilities 10 by message-passing' looks corrupted.Is 10 a 
      citation?- In the last line in Section 5, parentheses for Eq.(29) are 
      missing.