Faster computation of likelihood gradients for discrete observation Hidden Markov model

In this article we present an algorithm for faster computation of HMM likelihood gradients when the observation space is discrete. Many parameter estimation algorithms for HMM require repeated computation of gradient to optimize the likelihood function. Gradient computation is costly therefore its faster computation can improve their performance greatly. We develop an algorithm for faster computation of gradient using ideas from data compression. Our algorithm decreased computation cost of gradients by a factor of three to five. We apply our methods to speed up the Baum-Welch algorithm by similar factors.