Hidden Markov models (HMM) have been an important analysis framework in many computer science applications. The estimation of the HMM parameters is crucial as regards the performance of the whole HMM. Generally, HMM parameters estimation is performed with iterative algorithm like the Baum-Welch method, or gradient based methods. The advantage of the iterative algorithms is their computational efficiency. The disadvantage is that their performance depend on the initial value of the parameters and thus they usually yield to local optimum parameter values. In this paper, a Genetic Algorithm (GA) is used to compute optimized HMM parameters. The algorithm has been implemented on a GPU to face the high demand of computational resources of GA. We used this optimized computation of HMM parameters in a process workload classification, and we made experimental assessment and analysis via using the well-known SPEC-2006 benchmarks. The obtained classification accuracy is significantly better than that obtained with the Baum-Welch algorithms. On the other hand, the time needed to obtain the HMM parameters is of the same order than that required by Baum-Welch algorithm.

GPU-Aware Genetic Estimation of Hidden Markov Models for Workload Classification Problems

Cuzzocrea Alfredo;
2016-01-01

Abstract

Hidden Markov models (HMM) have been an important analysis framework in many computer science applications. The estimation of the HMM parameters is crucial as regards the performance of the whole HMM. Generally, HMM parameters estimation is performed with iterative algorithm like the Baum-Welch method, or gradient based methods. The advantage of the iterative algorithms is their computational efficiency. The disadvantage is that their performance depend on the initial value of the parameters and thus they usually yield to local optimum parameter values. In this paper, a Genetic Algorithm (GA) is used to compute optimized HMM parameters. The algorithm has been implemented on a GPU to face the high demand of computational resources of GA. We used this optimized computation of HMM parameters in a process workload classification, and we made experimental assessment and analysis via using the well-known SPEC-2006 benchmarks. The obtained classification accuracy is significantly better than that obtained with the Baum-Welch algorithms. On the other hand, the time needed to obtain the HMM parameters is of the same order than that required by Baum-Welch algorithm.
2016
9781467388450
Genetic Algorithm
Hidden Markov Models
Parameters Estimation
Baum-Welch
GPU.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/312915
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 4
social impact