<!--
Abstract:

CS 461
Introduction to Deep Learning
Lecture 11
-->

# CS 461 - Lecture 12

## Machine Learning Principles

### Hidden Markov Models

Bernhard Firner

2025-10-15

---

## Reading

* Recommended reading
  * Machine Learning: A Probabilistic Perspective by Murphy
    * 17 Markov and hidden Markov models

---

## Markov Model Review

* We represented a sequential dependency as a Markov chain
* Observe tokens, $X_1,...,X_T$
  * $T$ is the last step in the chain
  * The probability of observing $X_T$ considers the entire pathway
  * $p(X_T) = p(X_1)\prod_{t=2}^{T}p(X_t|X_{t-1})$
* Every possible value of X will be our `vocabulary`

---

## Representation

* We'll represent the $P(X_t|X_{t-1})$ as a matrix
  * Called a `transition matrix`
  * $KxK$, where $K$ is the number of tokens
  * $k=27$ for the letter + space unigram
* Let's call the transition matrix $A$ for simplicity

---

## Transition Matrix

* $A_{ij}$ is the probability of getting from $i$ to $j$ in one step
* An n-step transition's probability is
  * $A_{ij}(n) \triangleq P(X_{t+n} = j|X_t = i)$
  * At state $i$ at time $t$ and arrive at state $j$ at time $t+n$

---

## Modelling

* We don't want to create models so specific that they need an entire sequence
  * e.g. $X_{t=1}$ could be the first word of a book or email
  * Feels too specific to start there and predict the thousandth word

---

## Time-Invariant

* Instead, we want to assume that $P(X_t|X_{t-1})$ is independent of how we got to $X_{t-1}$
  * e.g. Melville is very likely to write "whale" after the word "the"
    * Regardless of the previous sentences
* We call this time-invariance
  * We'll act as though it doesn't matter how we reached $X_{t-1}$

---

## Sparsity

* In reality, we may not store the transition matrix
  * Many tokens in the vocabulary do not lead to other tokens
* Consider "whale wombat nickel chives"
  * contains valid tokens
  * but that phrase has probability near 0

---

## Storage

* Since the space is so sparse, it is easier to hold transitions in a dictionary
  * Use $x_{t-1}$ as the key
* With longer history, store a tuple of the past values as the key

---

## Sentence Predictor

```python
#! /usr/bin/python3

import argparse
import itertools
import numpy as np
import string
import sys

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument(
        "path",
        type=str,
        help="Path to a text file.")
    parser.add_argument(
        "order",
        type=int,
        help="Number of past words to look at. 0 for unigrams.")
    parser.add_argument(
        "start",
        type=str,
        nargs='+',
        help="Starting words for the predictions. Should be > order-1")

args = parser.parse_args()

assert(args.order < len(args.start)+1)

try:
        with open(args.path, 'r', encoding='utf-8') as corpus:
            text = corpus.read()
    except FileNotFoundError:
        print(f"Error: The file '{args.path}' was not found.")
        sys.exit(1)

# Change everything to lowercase.
    # Count the end of sentences as their own tokens.
    text = text.lower().replace('\n', ' ').replace('.', ' .').replace('?', ' ?').replace('!', ' !')
    # Replace unknown characters with a space
    text = ''.join([c if (c.isalpha() or c in ['.', '?', '!']) else ' ' for c in text])
    words = text.split()

# Observations
    # We could initialize this to 0, but, depending upon the ngram length, some occurences may not occur at all
    ngram_chains = dict()

# Now loop through the words
    for i in range(args.order, len(words)):
        ngram = words[i-args.order:i+1]
        # Loop through the ngram chain and fill in any missing links
        cur_dict = ngram_chains
        for gram in ngram[:-1]:
            if gram not in cur_dict:
                cur_dict[gram] = dict()
            cur_dict = cur_dict[gram]
        if ngram[-1] not in cur_dict:
            cur_dict[ngram[-1]] = 0
        cur_dict[ngram[-1]] += 1

# Use the starting word to predict some sentences
    for sample in range(10):
        cur_sentence = [word for word in args.start]
        while cur_sentence[-1] not in ['.', '?', '!'] and len(cur_sentence) < 50:
            # Use the tokens from our sentence to fetch the next word probabilities
            tokens = cur_sentence[-args.order:]
            cur_dict = ngram_chains
            for token in tokens:
                cur_dict = cur_dict[token]
            possible_words = list(cur_dict.keys())
            frequencies = np.array(list(cur_dict.values()))

probabilities = frequencies/np.sum(frequencies)
            next_word = np.random.choice(possible_words, p=probabilities)
            cur_sentence.append(next_word)
        print(' '.join(cur_sentence))

```

---

## Predicting Sentences

* We can use this to predict sentences:

<pre>
$ python3 predict_similar_sentences.py MobyDick_HermanMelville.txt 2 the whale
the whale .
the whale whose distant jet is so passing wonderful !
the whale ship carries no cargo but herself and crew their weapons .
the whale by his subsequent ocean life and only god bullied hull thou firm deck and in that quarter of the various lines and courses on the point of all oceanica .
the whale .
the whale as much blood as will presently be seen .
the whale s is to be borne in mind it s not the whiteness of the narwhale however that may be mine let me learnedly define it .
the whale fishery had been made to spout thick blood such a basis .
the whale .
the whale alongside a day and though from the whale .
</pre>

* Fairly meaningless without longer ngrams

---

## Two Open Items

* First, longer ngrams are data starved
  * We can either add lots more data or find a way to estimate missing values
* Second, how do we make estimates about the source of the observations?
  * We'll deal with the second one today

---

## Hidden Markov Models

* What if our observations are being created by some unseen process?
* Our observations are `emitted` by the hidden states
* The hidden states may `transition` without us knowing

---

## Hidden States

* With K hidden states we now have a new KxV matrix
  * K rows, one for each state
  * V columns, one for each token in our vocabulary
* Called the emission matrix
* The transition matrix now refers to the chances of moving from one hidden state to another

---

## How does this help?

* The hidden states can encode information that we gave up with the time-invariant assumption
* They can also help us build classifiers
  * Some observations will be more likely to have come from particular hidden states
  * Doesn't that sound like clustering?

---

## Clusters and HMM

* If there were no temporal dependency:
  * Hidden states would be clusters
  * Parameters would be optimized to match the observations through the iterative EM algorithm
* But there *are* temporal dependencies

---

## Probabilities with Hidden States

* We'll have to estimate three things:
  * $\pi$: the initial state distribution
  * A: the transition matrix
  * B: the emission matrix
* All together, we call them $\Theta$

---

## The initial state distribution

* Probability of the hidden states
* $\pi(i) = p(z_1=i)$
* These are the same as the gating priors in mixture models
* Probabilities are just the relative frequency of the hidden states

---

## The Transition Matrix

* $A(i,j) = p(z_t=j|z_{t-1}=i)$
* Looks the same as before
  * Transitions are between hidden states now, not observations
  * There will not be too many states
    * We don't have to worry about it being mostly empty

---

## The Emission Matrix

* $B(i,j) = p(x_i|z_j)$
  * The probability of seeing token $x_i$ given we are in hidden state $z_j$
* This generates the observations, but now it has no temporal dependence

---

## Observation Probability

* We want to maximize the likelihood of our observations
  * So what is the probability of an observation?
* Given an observation at time $t$, $x_t$:
  * What is the probability of seeing $x_t$ over all of the possible hidden states?
* Similar to the shared responsibility from clustering

---

## forwards-backwards algorithm

* The probability for each hidden state, $z$, given all observations is
  * $p(z_t=j|x_{1:T})$
* From $1:t$:
  * What are the hidden state probabilities given the past observations?
* From $t+1:T$
  * What are the probabilities we were in those hidden states given future observations?

---

## Sometimes unfair coin example

* Let's say we're flipping a coin
  * $p(tails)$ and $p(head)$ are both 0.5
* Unbeknownst to us, sometimes we grab an unfair coin from our pocket
  * $p(tails) = 0.1$ and $p(head) = 0.9$

<p><math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>B</mi><mo>=</mo><mrow><mo stretchy="true" form="prefix">(</mo><mtable><mtr><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.5</mn></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mn>0.1</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.9</mn></mtd></mtr></mtable><mo stretchy="true" form="postfix">)</mo></mrow></mrow><annotation encoding="application/x-tex">B = 
  \begin{pmatrix}
    0.5 & 0.5\\
    0.1 & 0.9
  \end{pmatrix}</annotation></semantics></math></p>

---

## Unfair Coin Transitions

* The transition probabilities come from how many flips we do at a time and how many coins are in our pocket
* Let's say that they are

<p><math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>A</mi><mo>=</mo><mrow><mo stretchy="true" form="prefix">(</mo><mtable><mtr><mtd columnalign="center" style="text-align: center"><mn>0.8</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.2</mn></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mn>0.2</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.8</mn></mtd></mtr></mtable><mo stretchy="true" form="postfix">)</mo></mrow></mrow><annotation encoding="application/x-tex">A = 
  \begin{pmatrix}
    0.8 & 0.2\\
    0.2 & 0.8
  \end{pmatrix}</annotation></semantics></math></p>

---

## Initial State Distribution

* We have the transition matrix, A, and the emission matrix B
* What is the initial state distribution?
  * Let's say we're equally likely to pull out the fair or unfair coins
  * $\pi = [0.5, 0.5]$

---

## Observation Probability

* We observe THH (tails and then two heads)
  * In vector form, $O = [[1, 0], [0, 1], [0, 1]]$
  * What is the probability of that heads at t?
* Begin at t=0, calculate for both hidden states
  * $\pi BO[0]$
    * $p(z_i=0|O(0)) = 0.5 * 0.5 = 0.25$
    * $p(z_i=1|O(0)) = 0.5 * 0.1 = 0.05$
  * $p(x_0) = [0.25, 0.05]$

---

## Forward Pass

* $BO[1] = [0.5, 0.9]$
* Need to multiply by the probability that we were in those hidden states
* Given likelihood of the hidden states at the previous time, the probability of being in state 0 or 1 now
  * $p(x_{t-1})ABO[t] = [0.25, 0.05]A[0.5, 0.9]$
  * $= [0.2+0.01,0.05+0.04][0.5, 0.9] = [0.105, 0.081]$

---

## Observation

* The first column of A captures the probability that we were in $z_0$ and stayed in $z_0$, or that we were in $z_1$ and switched
* This calculation will only ever depend upon the state at $t-1$
  * So the forward pass will take $T$ steps
    * An $k$ operations at each step, where $k$ is the number of hidden states
  * $k^2T$ in total

---

## Finished Forward Pass

* $\alpha = [[0.25, 0.05], [0.105, 0.081], [0.0501 , 0.07722]]$
* Tells us the hidden state probabilities given the past observations at each t
* Notice that long sequences will have tiny probabilities

---

## Backward Pass

* What are the probabilities we were in those hidden states given future observations?
* The initial probabilities begin at 1
* Iterate beginning at T-2, check transitions in pairs

---

## Backward Pass

* What's the probability of going from $O[-1]$ given $O[-2]$?
* $\beta = A B O[t] p(x_{t+1}|x_{t+1:T})$
  * $BO[t]$ is the probability of the observation for each hidden state
  * $A$ (the transition matrix) governs how likely each state is

---

## Backward Pass

* Initialize $p(x_{t+1}|x_{t+1:T})$ to 1 at T
* $\beta = A B O[t+1]1 = [0.58, 0.82]$
  * Makes sense; given $O[-1]$ was heads, hidden state 2 was more likely

---

## Forward and Backward

* $\alpha = [[0.25, 0.05], [0.105, 0.081], [0.0501 , 0.07722]]$
* $\beta = [[0.141288, 0.121032], [0.3364, 0.6724], [0.58, 0.82]]$
* These show the likelihood of $O$ for each hidden state
  * e.g. hidden states $[0, 1, 1]$ look the most probable
  * If the transition from fair to unfair was really low, that second state could stay fair

---

## Expectations

* We should combine $\alpha$ and $\beta$ to get a expectations
* One expectation for the states, and one for the transitions
  * Remember we need to update A, B, and $\pi$
  * A is the state transitions
  * B is the emission probabilities
  * $\pi$ are the initial state probabilities

---

## Expectation Estimation

* There are other ways, but we'll use the following
* Going to normalize values by the chain probability
  * $p(O) = \prod(\alpha)$
  * We know that the observations occurred, so that is the maximum probability we can achieve
* Call state estimate $\gamma$, call transition estimate $\xi$

---

## Expectation continued

* $\gamma = \frac{\alpha\beta}{p(O)}$
  * Just the normalized probability of the observations given our current parameters
* $\xi$ will be size $[T,k,k]$
  * Transition probability at each time
  * Will be built from the forward pass probability, the current transition probability, the probability of the next observation, and the backward probabilities

---

## $\xi$ continued

* Recall $A B O[t]$ was how we estimated the probability of transitioning into a state and observing $O[t]$
* $\xi[t] \leftarrow \frac{\alpha[t] A B O[t] \beta[t+1]}{p(O)}$
  * Read this as:
    * the probability of the left chain
    * the probability of seeing the observation given our model
    * the probability of seeing this given the right chain
    * normalized by the entire chain probability

---

## Expectation-Maximization

* Getting $\gamma$ and $\xi$ finishes our expectation calculation
  * Analogous to estimating the normalized probability of all points during clustering
  * Here, the relative responsibilities of the hidden states for each point were calculated whenever we multiplied $A B O[t]$

---

## Maximization Updates

* $\pi \leftarrow \gamma[0]$
  * Use the initial state estimate as our initial state distribution
* $A \leftarrow \frac{\sum\xi}{\sum\gamma}$
  * For each $A_{jk}$
    * The expected number of transitions from j to k (from $\xi$, the $TxNxN$ matrix)
    * Divided by the expected number of transitions from j to anything

---

## Maximizing Emission (B)

* Compute the emission for each symbol in the vocabulary
* Sum the expected number of times we are in state $j$ and see symbol $l$
* Divide by expected number of times we are in state $j$
* Select indices with $\mathbb{I}(x_{i,t}=l)$, but we'll use a loop in reality
* Assume $j$ is the index of vocabulary $l$
* $B[j] \leftarrow \frac{\sum\gamma[j,(where O[t]=l)]}{\gamma[j]}$

---

## EM Algorithm

* Now repeat
* The EM algorithm for HMMs is called the Baum-Welch algorithm
* Concern:
  * Those chain probabilities will be small
  * All math will be in logarithms again

---

## Forward Code

```python
def forward_pass_log(log_pi, log_A, log_B, observations):
    """Computes the forward probabilities (alpha) in log space.
    This is the first part of the equation below:
      p(z_t = j|x_{1:T}) = p(z_t = j|x_{1:t})p(x_{t+1:T}|z_t = j)
    """
    T = len(observations)
    # The number of hidden states
    N = log_A.shape[0]
    # Initialize with negative infinity (log(0))
    log_alpha = np.full((T, N), -np.inf)

# Initialization (t=0)
    # Begin with the probabilities of seeing the first observation for the emissions of each hidden state
    log_alpha[0, :] = log_pi + log_B[:, observations[0]]

# Iterate over the history (t=1 to T-1)
    # This fills in the forward probabilities at each value
    for t in range(1, T):
        # log_B_t is the log emission probability for the observation at time t
        # That's p(z_t = j | x_t)
        log_B_t = log_B[:, observations[t]]

# Loop over the hidden states
        # See 17.54 through 17.58 of Murphy's book
        for j in range(N):
            # Remember, non-log space these are multiplications
            # We are computing p(z_t = j|x_{1:t}), but with a history of 1
            # log_alpha[t-1, i] + log_A[i, j] + log_B_t[j]
            # Sum log probabilities (using np.logaddexp.reduce for numerical stability)
            log_sum = np.logaddexp.reduce(log_alpha[t-1, :] + log_A[:, j])
            log_alpha[t, j] = log_sum + log_B_t[j]

# Termination: Log-likelihood of the observation sequence
    log_likelihood = np.logaddexp.reduce(log_alpha[T-1, :])

return log_alpha, log_likelihood
```

---

## Backward Code

```python
def backward_pass_log(log_A, log_B, observations):
    """Computes the backward probabilities (beta) in log space.
    This is the second part of the equation below:
      p(z_t = j|x_{1:T}) = p(z_t = j|x_{1:t})p(x_{t+1:T}|z_t = j)
    """
    T = len(observations)
    # The number of hidden states
    N = log_A.shape[0]
    # Initialize with negative infinity (log(0))
    log_beta = np.full((T, N), -np.inf)

# Initialization (t=T-1): P(nothing | S_T-1) = 1, so log(1) = 0
    log_beta[T-1, :] = 0.0

# Iterate from (t=T-2 down to 0)
    # This fills in the backward probabilities at each value
    for t in range(T - 2, -1, -1):
        # log_B_t_plus_1 is the log emission probability for the observation at time t+1
        log_B_t_plus_1 = log_B[:, observations[t+1]]

for i in range(N):
            # Remember, non-log space these are multiplications
            # We are computing p(x_{t+1:T}|z_t = j), but only looking ahead 1
            # log_A[i, j] + log_B_t_plus_1[j] + log_beta[t+1, j]
            log_sum = log_A[i, :] + log_B_t_plus_1 + log_beta[t+1, :]
            log_beta[t, i] = np.logaddexp.reduce(log_sum)

return log_beta
```

---

## Expectation Code

```python
def compute_expectations_log(log_alpha, log_beta, log_A, log_B, observations, log_likelihood):
    """
    Computes gamma (single-state expectation) and xi (two-state transition expectation)
    in log space.
    These are from Murphy 17.101 and 17.102
      gamma is p(z_t = j|x_{i,1:T_i},\Theta)
      xi is p(z_{t-1} = j,z_{t}=k|x_{i,1:T_i},\Theta)
    Keep in mind that T is actually just as long as our history, although we'll
    loop over all values in this function.
    """
    # T is the number of observations, N is the number of hidden states
    T, N = log_alpha.shape

# Log P(O) is the log_likelihood from the forward pass
    log_PO = log_likelihood

# log_gamma[t, i] = log P(St=i | O)
    # Gamma is analogous to the soft clustering via assignment from mixture models
    # alpha*beta has the forward-backward probabilities, normalized by the likelihood of the observations
    log_gamma = log_alpha + log_beta - log_PO

# log_xi[t, i, j] = log P(St=i, St+1=j | O)
    log_xi = np.full((T - 1, N, N), -np.inf)

for t in range(T - 1):
        # Sum of logs for the numerator (P(St=i, St+1=j, O))
        # log(alpha_t(i)) + log(A_ij) + log(B_j(O_t+1)) + log(beta_t+1(j))
        log_B_t_plus_1 = log_B[:, observations[t+1]]

# For all N hidden states, this is the probability from the forward pass * transition probability * emission probability * backward probabilities
        # This is 17.66 from Murphy's book
        # These are the transition probabilities over every possible transition
        # Also called the (smoothed) two-slice marginal
        log_terms = (
            log_alpha[t, :, np.newaxis] +   # log alpha_t(n),    shape (N, 1)
            log_A +                         # log A_ij,          shape (N, N)
            log_B_t_plus_1[np.newaxis, :] + # log B_j(x_{t+1}),  shape (1, N)
            log_beta[t+1, np.newaxis, :]    # log beta_{t+1}(j), shape (1, N)
        )

# Divide (or subtract in log space) by the probability of this observation, normalizing this observation
        log_xi[t, :, :] = log_terms - log_PO

return log_gamma, log_xi
```

---

## Maximization Code

```python
def maximization_step(log_gamma, log_xi, observations, vocabulary):
    """
    Compute the new HMM parameters (pi_new, A_new, B_new) from the expectations.
    """
    T = len(observations)
    # Shape is T, N, N
    N = log_xi.shape[1]

# 1. Update Initial Probabilities (pi)
    # pi'_i = gamma_0(i)
    # From 17.103 in Murphy
    log_pi = log_gamma[0, :]

# 2. Update Transition Matrix (A)
    # Numerator: \sum_{t=0}^{T-2}(xi_t(i, j))
    # Denominator: \sum_{t=0}^{T-2}(gamma_t(i))
    # From 17.103 in Murphy
    log_xi_sum = np.logaddexp.reduce(log_xi)
    log_gamma_sum = np.logaddexp.reduce(log_gamma[:-1, :])

# For A, we take the number of expected transitions from j to k,
    # and divide by the expected transitions from j to any other state.
    # This guarantees that each row sums to 1.

# Use broadcasting for A_new[i, j] = xi_sum[i, j] / gamma_sum[i]
    # np.newaxis ensures the denominator broadcasts correctly across columns j
    # From 17.103 in Murphy
    log_A = log_xi_sum - log_gamma_sum[:, np.newaxis]

# 3. Update Emission Matrix (B)
    # Numerator: sum(gamma_t(i) * I(O_t = k))
    # Denominator: sum(gamma_t(i)) from t=0 to T-1 (total expected time in state i)
    # Numerator from 17.104 in Murphy
    # It is the expectation of the multinomial, E[M_{jl}]
    # This is conceptually simple. It's the expected number of times we observe symbol l while in state j
    # We normalize by dividing by the expected number of times we are in state j
    log_gamma_sum_all_t = np.logaddexp.reduce(log_gamma)

# If there was only one state, this would just be the expected number of
    # times we see symbol l divided by the total number of observations.
    # That would give us the emission probability into l for markov model
    # without a hidden state.

# Population the emission matrix. Initialize with 0 probabilities.
    log_B = np.zeros((N, len(vocabulary))) - np.inf

for k in vocabulary:
        # Find indices where observation O_t equals k
        indices_k = (observations == k)

if len(indices_k) > 0:
            # Sum log_gamma over time t where O_t=k
            log_gamma_sum_k = np.logaddexp.reduce(log_gamma[indices_k, :])
            # log(B'_jk) = log_gamma_sum_k[j] - log_gamma_sum_all_t[j]
            log_B[:, k] = log_gamma_sum_k - log_gamma_sum_all_t
        else:
            # If an observation never appears, its log-probability will be -inf (or very small)
            #log_B[:, k] = -np.inf
            # We already initialized these to 0
            pass

return log_pi, log_A, log_B
```

---

## So what does this do?

* Let's take an easy example
* Can we determine if the coin being flipped is fair or fake?

---

## Data Generation

```
def getDieObservations(k=250):
    # true emission probabilities for a fair die
    fair_emission = [1.0/6] * 6
    # true emission probabilities for a loaded die that rolls a 6 50% of the time
    loaded_emission = [0.1]*5 + [0.5]

actual_emission_matrix = np.array([fair_emission, loaded_emission])

actual_transition_matrix = [ [0.95, 0.05],
                                 [0.05, 0.95]]

# Using the values above, we can generate some data

actual_states = []
    observations = []

cur_state = 0

# Die rolls should be 1-6, but we'll simplify some code and use 0-5
    vocabulary=list(range(6))

for i in range(k):
        # Generate the next state from the current state and the transition matrix
        new_state = random.choices([0, 1], weights=actual_transition_matrix[cur_state])[0]
        # Generate a die roll from the new state and the emission matrix
        new_roll = random.choices(vocabulary, weights=actual_emission_matrix[new_state])[0]
        # Remember the results
        actual_states.append(new_state)
        observations.append(new_roll)
        cur_state = new_state
    observations = np.array(observations)
    return actual_states, observations, vocabulary
```

---

## Predictions

<pre>
$ python3 12_occassionally_unfair_casino.py coin --samples 300
Converged after 242 steps
Transition probabilities for fixed coin: [0.40704574 0.59295426]
Transition probabilities for fair coin: [0.68086784 0.31913216]
Emission probabilities for fixed coin: [0.00214286 0.99785714]
Emission probabilities for fair coin: [0.53567622 0.46432378]
Log-Likelihood P(O): -181.5306
Total Expected Time in Fair State (0): 167.48 / 300 steps
Total Expected Time in Fixed State (1): 132.52 / 300 steps
State prediction accuracy 0.6733333333333333
</pre>

---

## Not bad!

* How about for a die?

```python
def getCoinObservations(k=50):
    # true emission probabilities for a fair coin
    fair_emission = [0.5, 0.5]
    # true emission probabilities for a loaded die that rolls a 6 50% of the time
    unfair_emission = [0.1, 0.9]

actual_emission_matrix = np.array([fair_emission, unfair_emission])

actual_transition_matrix = [ [0.8, 0.2],
                                 [0.2, 0.8]]

# Using the values above, we can generate some data

actual_states = []
    observations = []

cur_state = 0

# 0 for tail, 1 for heads
    vocabulary=list(range(2))

---

## Die results

<pre>
$ python3 12_occassionally_unfair_casino.py die --samples 500
Converged after 95 steps
Transition probabilities for fixed die: [0.14749579 0.85250421]
Transition probabilities for fair die: [0.88183479 0.11816521]
Emission probabilities for fixed die: [0.07026388 0.17342299 0.00586357 0.12337442 0.09226615 0.53480899]
Emission probabilities for fair die: [0.17151531 0.11997255 0.20957302 0.14631032 0.19351346 0.15911533]
Log-Likelihood P(O): -844.1528
Total Expected Time in Fair State (0): 275.24 / 500 steps
Total Expected Time in Fixed State (1): 224.76 / 500 steps
State prediction accuracy 0.752
</pre>

---

## Dicussion

* Not only are we predicting the hidden state, we are also predicting A and B
  * And the hidden state has no labels!
* Improvements
  * As with clustering, our initial choices have large impacts
  * How many hidden states? How should they be initialized?
* But as-is we have something useful

---

## Practice Questions

What is required to create a good ensemble?

a. Strong individual learners in the ensemble.

b. Some independence between members of the ensemble.

c. Members must be trained on the same data features.

d. Members must be trained on the same observed samples.

</div>

---

## Practice Questions

Which of these does **not** describe an ensemble technique?

a. For each learner, resample observed samples with replacement, changing the data distribution.

b. For each learner, select a subset of columns, randomly dropping features.

c. For each learner, change the weights of the different samples, pushing the learning to form a different decision boundary.

d. For each learner, find the principal components of the dataset and drop low variance features.

</div>

---

## Practice Questions

Which of these statements about AdaBoost is **true**?

a. Adaboost requires decision trunks.

b. Adaboost can work with any learner as long as errors can be reweighted.

c. Adaboost requires weak learners, like decision trunks or logistic regressors.

d. Adaboost works best with strong learners, like decision trees, but can work with weak learners if necessary.

</div>

---

## Practice Questions

Which of these statement about ensemble techniques and the bias-variance tradeoff is **false**?

a. Bagging reduces the variance of the training dataset

b. Boosting uses high-bias models to produce a model well-suited to high dataset variance.

c. Random forests reduce the variance of the training dataset.

d. Random forests use high-bias models to produce models well-suited to high dataset variance.

</div>

---

## Practice Questions

Which of these is **true** about a Markov Chain?

a. Markov chains can only be used for temporally related data.

b. A time-invariant markov model captures dependencies between the current state and all prior states.

c. A Markov chain cannot encode the probability of a long sequence.

d. A time-invariant markov model only looks at the chain within a finite number of steps.

</div>

<!--
Papers:

An HMM for detecting spam mail by Jose Gordillo, Eduardo Conde

A Hidden Markov Model Variant for Sequence Classification by Sam Blasiak andHuzefa Rangwala
-->

<!--
Converged after 473 steps
Emission probabilities for die 0: [0.13593037 0.10547458 0.08088966 0.14997934 0.09840429 0.42932176]
Emission probabilities for die 1: [0.05367705 0.36635264 0.36544106 0.09845297 0.0859902  0.03008607]
Log-Likelihood P(O): -409.9345
Total Expected Time in Fair State (0): 201.58 / 250 steps
Total Expected Time in Loaded State (1): 48.42 / 250 steps
Total Expected Transitions (should be T-1=249): 249.00

Expected Transitions FROM Fair (State 0):
  Fair -> Fair: 7.05
  Fair -> Fixed: 41.32

Expected Transitions FROM Fair (State 0):
  Fixed -> Fixed: 194.53
  Fixed -> Fair: 6.10
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]
[0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1]
State prediction accuracy 0.676
-->