Application of the synergetic control theory for training hidden markov models with biased neighborhood-simulated annealing algorithm
Juan E. Vargas, Anton Bezuglov · 2006
The dissertation focuses on problems related to training hidden Markov models (HMMs) and estimating their optimal dimensionality. Finding optimal solutions of these problems is crucial for the efficient application of HMMs in areas of science such as molecular biology, time series analysis, speech recognition, and other scientific endeavors that suffer from the 'data-deluge' phenomenon, which is likely to characterize most scientific pursuits in the 21st century. Most conventional algorithms that train HMMs from data are local search methods that can only find sub-optimal models and cannot guarantee global optimality. The difference in accuracy between locally and globally optimal HMMs can be quite significant and gets worse with the growth of complexity. This dissertation proposes an algorithm for optimal training HMMs that attempts to deal with the 'dimensionality curse'. The algorithm draws concepts from Simulated Annealing (SA), which is a widely known stochastic global optimization framework. Unfortunately, the global optimality of the SA framework does not come without a penalty. To guarantee global optimality SA requires a large number of iterations, which become intractable as the complexity of the training grows. This dissertation offers a solution based on a theory conceived to control non-linear dynamical processes; called Synergetic Control Theory (SCT). The connection between that theory and the problem at hand, is that SA is similar to a dynamical process which is to be controlled by an artifact that follows the principles of the SCT. In doing so, the SA process is coupled to a synergetic controller, which maintains the optimal operation mode of the training algorithm and significantly improves its convergence rate for multidimensional problems. The superior performance of the training algorithm with the synergetic controller is discussed in Chapters 3 and 4. The performance of the training algorithm---Biased Neighborhood-Simulated Annealing (BN-SA)---is demonstrated in Chapter 4, with an example related to the alignment of protein sequences. The BN-SA algorithm was used to train profile HMMs, which were compared to profile models produced by other training algorithms, such as the Baum-Welch and the Viterbi approximation to Baum-Welch. This comparison demonstrated that BN-SA produces significantly more accurate models than the conventional training algorithms. At the same time, due to the dimensionality reduction technique applied, BN-SA achieves its better accuracy at a significantly faster rate.