Fast maximum a-posteriori inference on Monte Carlo state spaces
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 particlesmoothing 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 naive computation.