Scala: Guide for Data Science Professionals

Performance consideration

The time complexity for decoding and evaluating canonical forms of the hidden Markov model for N states and T observations is O(N²T). The training of HMM using the Baum-Welch algorithm is O(N²TM), where M is the number of iterations.

There are several options to improve the performance of HMM:

• Avoid multiplication by 0 in the emission probabilities matrix by using sparse matrices or keeping tab of the null entries
• Try to train HMM on a relevant subset of the training data, particularly in the case of tagging

The training of the linear chain conditional random fields is implemented using the same dynamic programming techniques as HMM implementation (Viterbi, forward-backward passes). Its time complexity for training T data ...