Fast maximum a posteriori inference in Monte Carlo state spaces
Mike Klaas, Dustin Lang, Nando de Freitas · 2005
Many important algorithms for statistical inference can be expressed as a weighted maxkernel search problem. This is the case with the Viterbi algorithm for HMMs, message construction in maximum a posteriori BP (max-BP), as well as certain particle-smoothing algorithms. Previous work has focused on reducing the cost of this procedure in discrete regular grids [4]. MonteCarlo state spaces, which are vital for highdimensional inference, cannot be handled by these techniques. We present a novel dualtree based algorithm that is appliable to a wide range of kernels and shows substantial performance gains over nave computation.