Hidden Markov Models (HMMs) are a class of probabilistic graphical models used to understand observable events (called ‘symbols’) that depend on some unobservable or ‘hidden’ internal factors (called ‘states’). Such stochastic probabilistic models assume that a system's future states only depend on current hidden and observable states and not on other prior events.
A typical example of an HMM is predicting future weather conditions (hidden variable) based on current weather observations or the type of clothing people wear (observations).
A dynamic programming approach called the Viterbi algorithm helps get a probability estimate of the most likely sequence of hidden states (called ‘Viterbi path’) that result in a sequence of observable events in HMMs.
HMMs are applied to many different real-world use cases, such as:
-
Financial market analysis: Predicting market trends, such as bull or bear markets, based on observations such as stock prices or returns.
-
Robotics: for tasks such as recognizing complex sequences of movements and path planning.
-
Anomaly detection: in network monitoring or cybersecurity areas to detect unusual patterns in system behavior that may lead to system failure or cyber-attack.
-
Tools maintenance: for predictive maintenance of machines based on error messages or sensor readings.
-
Bioinformatics: to analyze biological sequences such as those of DNA.
-
Natural Language Processing (NLP): for parts-of-speech (PoS) tagging.
-
Speech and gesture recognition: to model the sequences of spoken words and body movements in computer vision applications.
-
Music analysis: to analyze and transcribe musical arrangements.
-
Predicting the behavior of complex thermodynamic or hydrological systems such as river flooding and weather.
This blog discusses the Hidden Markov Models code sample in the oneAPI GitHub repository. The sample demonstrates how to implement the Viterbi algorithm using SYCL* and offload complex computations of the Viterbi path to GPU using the Intel® oneAPI DPC++/C++ library.
An Overview: Intel® oneAPI DPC++/C++ Compiler
The Intel oneAPI DPC++/C++ Compiler is an industry-leading LLVM-based compiler that helps compile ISO C/C++ and SYCL applications across heterogeneous architectures. It is the world’s first compiler fully supporting the latest SYCL 2020 specification. With that and support for accelerated computing frameworks like OpenMP*, the compiler lets you achieve both industry standards compliance and high performance. It allows you to easily leverage oneAPI libraries such as oneDPL and oneTBB for optimized parallel execution and offload compute acceleration with code reusability across diverse hardware, including CPUs, GPUs, and FPGAs.
About the Code Sample
The Hidden Markov Models sample illustrates SYCL implementation of the Viterbi algorithm to find the most likely sequence of hidden states in HMMs. For faster results, it solves sequential steps of multiple graph traversals simultaneously by offloading the computations to GPU using Intel oneAPI DPC++/C++ Compiler.
The implementation involves a square transition matrix A of size N (N is the number of states/graph nodes). At any given step of the Markov process, each element (i,j) of the matrix denotes the probability of moving from state i to state j (i=j if the state does not change at that step).
The sample assumes that there are visible observations depending on the current Markov process. The dependency is represented using an emission matrix B in terms of a conditional probability distribution.
Pi is the probability distribution of initial states.
How is the Viterbi algorithm implemented?
-
Initialize the matrix of Viterbi values on the first states using matrices Pi and B.
-
Initialize a matrix of back pointers with (–1).
-
At each step, set the Viterbi matrix to the maximal possible value using A, B, and Pi.
-
In the last step, set the state with the maximum Viterbi value as the final state of the Viterbi path.
-
Determine the previous states of the Viterbi path using the rows of back pointers’ matrix corresponding to each step except the last one.
→ For implementation details, check out the C++ source code.
→ For steps to build and execute the code sample, check out the
key implementation details.
Sample Output
Here’s an example output of executing the code on an Intel CPU using Linux*:
[100%] Built target hidden-markov-models
Device: Intel(R) Core(TM) i7-6820HQ CPU @ 2.70GHz Intel(R) OpenCL
The Viterbi path is:
19 18 17 16 15 14 13 12 11 10
The sample completed successfully!
[100%] Built target run
What’s Next?
Check out the Hidden Markov Models code sample for a GPU-offloaded SYCL implementation for finding the Viterbi path in an HMM.
Try several other code samples available on the oneAPI GitHub repository.
Get started with the Intel oneAPI DPC++/C++ Compiler today to efficiently compile C/C++ and SYCL applications across heterogeneous architectures.
Also, explore other AI, HPC, and Rendering tools in Intel’s oneAPI-powered software portfolio.
Get the Software
You can install the Intel oneAPI DPC++/C++ Compiler as a part of the Intel® oneAPI Base Toolkit or Intel® HPC Toolkit. You can also download a standalone version of the compiler or test it across Intel® CPUs and GPUs on the Intel® Tiber™ Developer Cloud platform.
Additional Resources
-
Intel oneAPI DPC++/C++ Compiler Documentation