Hidden Markov Models

Introduction

Hidden Markov Model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobservable (i.e. hidden) states.

In simpler Markov models (like a Markov chain), the state is directly visible to the observer, and therefore the state transition probabilities are the only parameters, while in the hidden Markov model, the state is not directly visible, but the output (in the form of data or “token” in the following), dependent on the state, is visible. Each state has a probability distribution over the possible output tokens. Therefore, the sequence of tokens generated by an HMM gives some information about the sequence of states; this is also known as pattern theory.

Exploration VS Exploitation

Think of a row of slot machines. Each machine has its own probability of winning. As a player you want to make as much money as possible. How do you figure out which of the machine has the best odds, while at the same time maximizing your profit? If you constantly played one of the machines (exploitation) you would never learn anything about the odds of the other machines. If you always picked a machine at random (exploration) you would learn a lot about the odds of each machine but probably wouldn’t make as much money as you could have always playing the “best” machine.

Agents are trained using a mixed approach:

• First, an agent is trained playing against itself with random moves.

• Then, the agent is trained playing against itself with the best moves it learnt.

• Finally, the agent is trained playing against itself but this time it choses both random and best moves.

Note

Transition weights are updated at each round.