The Infinite Markov Model

by Daichi Mochihashi and Eiichiru Sumita

The paper illustrates how it is possible to extend an n-gram model with Dirichlet process (here with Chinese restaurant process interpretation, actually a more general form is Pitman-Yor process). An n-gram model is simply an order-n Markov model, which can be presented with suffix tree. The generation can be then extended to arbitrary depth (unlike n-gram, the depth is fixed). The important thing is the inference part. The posterior is difficult to compute and we simply use a Gibbs sampler (the conditional posterior is easy to compute, a Beta distribution given a Beta prior).

Maybe we can try a variational version?