Probabilistic Models
Instead of drawing a boundary between classes, a probabilistic model says how likely each answer is, and for sequences, how likely each next state is. The page starts with naive Bayes and Bayesian belief networks, moves to Markov models and the hidden Markov model, then to input-output HMMs, and ends with conditional random fields.
PROBABILISTIC ALGORITHMS
The path runs from the simplest probabilistic classifier to sequence models where each label depends on the one before it.
NAIVE BAYES
Naive Bayes is the entry point: apply Bayes' rule and assume the features are independent. A Vidhya piece on NB used to open this list; that address no longer opens and is kept at the end of the page. Baysian tree is the UBS-IB bayesian_tree repository on GitHub. Jake VanderPlas's Python Data Science Handbook chapter, In Depth: Naive Bayes Classification, covers NB, GNB, multi nominal NB.
BAYES, BAYESIAN BELIEF NETWORKS
Naive Bayes is one fixed use of Bayes theorem; a belief network lets the dependencies between variables be drawn explicitly. Mastery on bayes theorem is MachineLearningMastery's gentle introduction to Bayes theorem for machine learning. Introduction To BBS is Sachin Joglekar's blog post introducing Bayesian belief networks. A complementing SLIDE presentation that shows how to build the network’s tables, and a very nice presentation regarding BBS, used to follow; both are kept at the end of the page.
Fitting those tables is an estimation problem. Maximum Likelihood (log likelihood) - proofs for bernoulli, normal, poisson. For Another example, the same Sachin Joglekar post works one through.
MARKOV MODELS
Belief networks have no notion of time; Markov models add it, and they need two words kept straight first. Random vs Stochastic (here and here): the first question asks what the difference between stochastic and random is, and the second asks how a random vector differs from a stochastic process. A variable is 'random'. A process is 'stochastic'.
Apart from this difference the two words are synonyms
In other words, a random vector is a generalization of a single random variables to many, and a stochastic process is a sequence of random variables, or a sequence of random vectors (and then you have a vector-stochastic process).
(What is a Markov Model?) A Markov Model is a stochastic(random) model which models temporal or sequential data, i.e., data that are ordered. It provides a way to model the dependencies of current information (e.g. weather) with previous information. It is composed of states, transition scheme between states, and emission of outputs (discrete or continuous). Several goals can be accomplished by using Markov models: learn statistics of sequential data, do prediction or estimation, and recognize patterns.
The weather version makes it concrete. (sunny cloudy explanation) Markov Chains is a probabilistic process, that relies on the current state to predict the next state. To be effective the current state has to be dependent on the previous state in some way: if it looks cloudy outside, the next state we expect is rain. If the rain starts to subside into cloudiness, the next state will most likely be sunny. Not every process has the Markov Property, such as the Lottery, this weeks winning numbers have no dependence to the previous weeks winning numbers.
The tutorial then walks these steps:
They show how to build an order 1 markov table of probabilities, predicting the next state given the current.
Then it shows the state diagram built from this table.
Then how to build a transition matrix from the 3 states, i.e., from the probabilities in the table
Then how to calculate the next state using the “current state vector” doing vec*matrix multiplications.
Then it talks about the setting always into the rain prediction, and the solution is using two last states in a bigger table of order 2. He is not really telling us why the probabilities don't change if we add more states, it stays the same as in order 1, just repeating.
MARKOV MODELS / HIDDEN MARKOV MODEL
In a plain Markov chain the state is visible; in a hidden Markov model only its effects are. The same notes are in Timeseries.
HMM tutorials
The tutorials that used to lead this section, a four-part HMM tutorial (Part 1, 2, 3, 4), a Medium intro to HMM / MM, and HMM with sklearn and networkx, no longer open and are kept at the end of the page. What remains from the Medium thread is the Paper like example, a Medium post on the hidden Markov model.
HMM variants
Implementations come next. Stack exchange on hmm asks which stable, well-documented Python library can implement Hidden Markov Models. HMM LEARN is hmmlearn, Hidden Markov Models in Python, with scikit-learn like API (sklearn, still being developed). Pomegranate is the pomegranate documentation, and it covers more than HMMs:
General mixture models
Hmm
Basyes classifiers and naive bayes
Markov changes
Bayesian networks
Markov networks
Factor graphs
There is also GHMM with python wrappers, and Hmms is lopatovsky's continuous-time Hidden Markov Model on GitHub (old).
With the tools listed, the idea itself: HMM (what is? And why HIDDEN?) - the idea is that there are things that you CAN OBSERVE and there are things that you CAN'T OBSERVE. From the things you OBSERVE you want to INFER the things you CAN'T OBSERVE (HIDDEN). I.e., you play against someone else in a game, you don't see their choice of action, but you see the result.
In Python, the hmmlearn code is the main option. HMMs were previously part of sklearn Python previously part of the library, until the sklearn.hmm module was deprecated for no longer matching the project's scope and API. For sequence labeling, Python seqLearn is the seqlearn API reference.
This youtube video part1 - explains about the hidden markov model. It shows the visual representation of the model and how we go from that the formula:
It breaks down the formula to three parts, which the next figure (also copied from the original hosted image) writes out:
transition probability formula - the probability of going from Zk to Zk+1
emission probability formula - the probability of going from Zk to Xk
(Pi) Initial distribution - the probability of Z1=i for i=1..m
In part2 of the video, mathematicalmonk's Hidden Markov models (part 2) continues from there.
* HMM in weka, with github, working on 7.3, not on 9.1; that link no longer opens and is kept at the end of the page.
If the formulas are still opaque, simpler explanations help:
Probably the simplest explanation of Markov Models and HMM as a “game” - link
This video explains that building blocks of the needed knowledge in HMM, starting probabilities P0, transitions and emissions (state probabilities)
This post This explains HMM and ties our understanding together, as the Quora answer to what a simple explanation of the Hidden Markov Model algorithm is. A cute explanation on quora from that thread comes with these figures:
This is the iconic image of a Hidden Markov Model. There is some state (x) that changes with time (markov). And you want to estimate or track it. Unfortunately, you cannot directly observe this state (hidden). That's the hidden part. But, you can observe something correlated with the state (y).
OBSERVED DATA -> INFER -> what you CANT OBSERVE (HIDDEN).
Considering this model, P(X0) is the initial state for happy or sad, P(Xt | X t-1) is the transition model from time-1 to time, and P(Yt | Xt) is the observation model for happy and sad (X) in 4 situations (w, sad, crying, facebook). The last figure fills in those tables.
INPUT OUTPUT HMM (IOHMM)
A plain HMM only emits outputs; an input-output HMM also conditions on inputs. The Incomplete python code for unsupervised / semi-supervised / supervised IOHMM - training is there, prediction is missing. The reference behind it is Machine learning - a probabilistic approach, david barber; that link no longer opens and is kept at the end of the page.
CONDITIONAL RANDOM FIELDS (CRF)
HMMs model how observations are generated; a CRF models the labels given the observations directly, which is why it shows up in templatization and NER. The same notes are in CRF for templatization, Named Entity Recognition (NER), and Timeseries.
Make sense intro to CRF, comparison against HMM is Ravish Chawla's overview: CRFs are a discriminative model for predicting sequences that use contextual information from previous labels. HMM, CRF, MEMM is Alibaba Cloud's comparative analysis of those three statistical modeling methods. Another crf article is Phylypo Tum on text segmentation, showing how CRF, a special case of the log-linear model, solves the label bias issue of MEMM. The neural network CRF, NNCRF, builds the sequence probability from the softmax outputs the network assigns to each label. The author's list had a fifth item, another one, without an address.
For code, scikit-learn inspired API for CRFsuite is TeamHG-Memex/sklearn-crfsuite, Sklearn wrapper is the supercoderhawk fork of the same scikit-learn inspired API, and Python crfsuite is scrapinghub's python binding for crfsuite. Pycrf suite vidahya is the Analytics Vidhya complete guide to text classification using conditional random fields in Python.
Two last references close the loop back to Markov models. What is a Markov Model?) The Introduction to Markov Models notes show how to establish the transition probabilities between states from collected data: http://cecas.clemson.edu/~ahoover/ece854/refs/Ramos-Intro-HMM.pdf. Another one is Freddy Boulton's CRF tutorial in PyTorch, which starts from two identical dice, one fair and one not: https://towardsdatascience.com/conditional-random-fields-explained-e5b8256da776
Deprecated links
These links and images no longer work. The original wording is kept here. A same-resource copy, when one was checked, is used above.
- Vidhya on NB. This address no longer opens: https://towardsdatascience.com/my-secret-sauce-to-be-in-top-2-of-a-kaggle-competition-57cff0677d3c - very nice presentation. This address no longer opens: http://chem-eng.utoronto.ca/~datamining/Presentations/Bayesian_Belief_Network.pdf - 1. This address no longer opens: http://gekkoquant.com/2014/05/18/hidden-markov-models-model-description-part-1-of-4/ - 2. This address no longer opens: http://gekkoquant.com/2014/05/26/hidden-markov-models-forward-viterbi-algorithm-part-2-of-4/ - 3. This address no longer opens: http://gekkoquant.com/2014/09/07/hidden-markov-models-examples-in-r-part-3-of-4/ - 4. This address no longer opens: http://gekkoquant.com/2015/02/01/hidden-markov-models-trend-following-sharpe-ratio-3-1-part-4-of-4/ - Intro to HMM. This address no longer opens: https://towardsdatascience.com/introduction-to-hidden-markov-models-cd2c93e6b781 - HMM with sklearn and networkx. This address no longer opens: http://www.blackarbs.com/blog/introduction-hidden-markov-models-python-networkx-sklearn/2/9/2017 - HMM in weka, with github, working on 7.3, not on 9.1. This address no longer opens: http://www.doc.gold.ac.uk/~mas02mg/software/hmmweka/index.html - Machine learning - a probabilistic approach, david barber.. This address no longer opens: https://pdfs.semanticscholar.org/a632/9a41ee67fae978ccac1e37370f074497a4fe.pdf - complementing SLIDE presentation. This address no longer opens: https://www.slideshare.net/GiladBarkan/bayesian-belief-networks-for-dummies
Last updated
Was this helpful?