Scala for Machine Learning

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 the 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 the HMM:

• Avoid unnecessary multiplication by 0 in the emission probabilities matrix by either using sparse matrices or tracking the null entries.
• Train the HMM on the most relevant subset of the training data. This technique can be particularly effective in the case of tagging of words or a bag of words in natural language processing.

The training of the linear chain conditional random fields is implemented using the same dynamic programming ...