{"id":2903,"date":"2023-11-19T02:40:07","date_gmt":"2023-11-18T17:40:07","guid":{"rendered":"https:\/\/saraheee.com\/?p=2903"},"modified":"2023-11-20T23:39:09","modified_gmt":"2023-11-20T14:39:09","slug":"hidden-markov-models-three-key-problems-and-algorithms","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2023\/11\/hidden-markov-models-three-key-problems-and-algorithms\/","title":{"rendered":"Hidden Markov Models & three key Problems and Algorithms"},"content":{"rendered":"

Contents<\/h3>\n\n\n\n
Introduction\nHidden Markov Models\nThree Key HMM Problems\n\n1) Forward-Backward algorithm\n2) Viterbi algorithm\n3) Baum-Welch algorithm<\/pre>\n\n\n\n
<\/p>\n\n\n\n
Introduction<\/h2>\n\n\n\n
This is a compilation of a series of videos in which Prof. Patterson describes the Hidden Markov Model, starting with the Markov Model and proceeding to the three core questions for HMMs.
A Hidden Markov Model is a machine learning model for predicting sequences of states from indirect observations.<\/p>\n\n\n\n
Hidden Markov Model<\/h2>\n\n\n\n
Markov property: a mathematical modeling constraint<\/p>\n\n\n\n
Discrete markov model
: discrete if it has distinct states that the model can be in at a given moment<\/p>\n\n\n\n
At discrete times the system changes state (possibly to the same state) according to the transition probabilities<\/p>\n\n\n\n
\\(P(q_t = S_z | q_{t-1} = S_y, … , q_2 = S_j, q_1 = S_i)\\)<\/p>\n\n\n\n
A full probabilistic description of a given system would require knowledge of the current state and all previous states<\/p>\n\n\n\n
But not so with the Markov property<\/p>\n\n\n\n
\\(P(q_t = S_j | q_{t-1} = S_i)\\)<\/p>\n\n\n\n
If we assume that our transition probabilities don’t vary over time then<\/p>\n\n\n\n
\\(a_{ij} = P(q_t = S_j | q_{t-1} = S_i) 1 \\leq i, j \\leq N\\)<\/p>\n\n\n\n
\\(a_{ij} \\geq 0\\)<\/p>\n\n\n\n
\\(\\sum_{j=1}^{N} a_{ij} = 1\\)<\/p>\n\n\n\n
zero means we’re not going to make that transition ever<\/p>\n\n\n\n
An Observable Markov Model<\/h5>\n\n\n\n
Given the model is in a known state, what is the probability that it will stay in that state for d days?<\/p>\n\n\n\n
The formal observation sequence is<\/p>\n\n\n\n
\\(O = \\{S_i, S_i, S_i, …, S_i, S_j \\neq S_i\\}\\)<\/p>\n\n\n\n
\\(P(O|Model, q_1 = S_i) = (a_{ii})^{d-1}(1-a_{ii}) = p_i(d)\\)<\/p>\n\n\n\n
This is the discrete probability density function of duration d in state i \\(p_i(d)\\)<\/p>\n\n\n\n
From this we can calculate the average stay in any state conditioned on the model and starting in the state<\/p>\n\n\n\n
\\(\\bar{d_i} = \\sum_{d=1}^{\\infty}dp_i(d)\\)<\/p>\n\n\n\n
\\(\\bar{d_i} = \\sum_{d=1}^{\\infty}d(a_{ii})^{d-1}(1-a_{ii}) = \\frac{1}{1-a_{ii}}\\)<\/p>\n\n\n\n
So, the expected number of consecutive sunny<\/strong> days (given the model) is \\(\\frac{1}{1-a_{ii}} = \\frac{1}{0.2} = 5\\)<\/p>\n\n\n\n
Imagine a person flipping a coin behind a curtain
Each result is called out and becomes an observation<\/p>\n\n\n\n
    \n
  • How should we model this situation?<\/li>\n\n\n\n
  • Should we assume a single fair coin is being flipped?<\/li>\n\n\n\n
  • Should we assume the caller is accurate?<\/li>\n<\/ul>\n\n\n\n
    A Hidden Markov Model has N states
    They are hidden, but they typically correspond to something we know about the world
    States are generally connected aka ergodic<\/strong> S = \\(\\{S_1, S_2, S_3, S_4, S_5, …, S_N\\}\\)
    state at time t is \\(q_t\\), \\(\\forall i : q_i \\in S (1 \\leq i \\leq t)\\)<\/p>\n\n\n\n
    A Hidden Markov Model has M observable symbols
    They are what can be observed
    They are a discrete alphabet
    V = \\(\\{V_1, V_2, V_3, V_4, V_5, …, V_M\\}\\)<\/p>\n\n\n\n
    A Hidden Markov Model has State transition matrix A<\/p>\n\n\n\n
    A = \\({a_{ij}}\\)<\/p>\n\n\n\n
    \\(a_{ij} = P(q_t = S_j | q_{t-1} = S_i) 1 \\leq i, j \\leq N\\)<\/p>\n\n\n\n
    if a_{ij} = 0 then a transition between \\(S_i\\) and \\(S_j\\) is not possible<\/p>\n\n\n\n
    \\(\\sum_{j=1}^{N}a_{ij} = 1\\)<\/p>\n\n\n\n
    A Hidden Markov Model has Observation probabilities<\/p>\n\n\n\n
    B = \\({b_j(k)}\\)<\/p>\n\n\n\n
    \\(b_j(k) = P(v_k at t | q_t = S_j)\\), 1 \u2264 j \u2264 N, 1 \u2264 k \u2264 M<\/p>\n\n\n\n
    A Hidden Markov Model has Initial state probabilities<\/p>\n\n\n\n
    \\(\\pi = {\\pi_i}\\)<\/p>\n\n\n\n
    \\(\\pi_i = P(q_1 = S_i) 1 \\leq i \\leq N\\)<\/p>\n\n\n\n
    HMM = {N, M, A, B, \u03c0<\/em>}<\/p>\n\n\n\n
    \\(O = {O_1, O_2, O_3, …, O_T}\\)<\/p>\n\n\n\n
    To generate observations
    Choose \\(q_1 = S_i\\) according to \\(\\pi_i\\)
    Set t = 1
    Choose \\(O_t = v_k\\) according to B ie \\(b_i(k)\\)
    Transit to a new state \\(q_{t+1} = S_j\\) according to A ie \\(a_{ij}\\)
    set t = t + 1 repeat until t > T<\/p>\n\n\n\n
    Markov Model is a special case of a Hidden Markov Model<\/p>\n\n\n\n
      \n
    • One in which the observation distribution has one non-zero entry<\/li>\n\n\n\n
    • There is one observation symbol for each state<\/li>\n<\/ul>\n\n\n\n
      Three Key HMM Problems<\/h4>\n\n\n\n
      What is the probability that a model generated a sequence of observations?<\/p>\n\n\n\n
      \\(O = {O_1, O_2, O_3, …, O_T}, \\lambda = (A, B, \\pi)\\)
      \\(P(O|\\lambda) ?\\)<\/p>\n\n\n\n
        \n
      • Given a sequence of observations, which apartment is the robot in?<\/li>\n\n\n\n
      • Which model best explains the observations?<\/li>\n<\/ul>\n\n\n\n
        <\/p>\n\n\n\n
        Forward-Backward algorithm<\/h3>\n\n\n\n
        Let’s start by imagining all possible state sequences<\/p>\n\n\n\n
        \\(Q = q_1, q_2, q_3, …, q_T\\)<\/p>\n\n\n\n
        Probability of seeing observations given those states is<\/p>\n\n\n\n
        \\(P(O|Q, \\lambda) = \\prod_{t=1}^{T}P(O_t|q_t, \\lambda)\\)<\/p>\n\n\n\n
        \\(P(O|Q, \\lambda) = b_{q1}(O_1) \\cdot b_{q2}(O_2) \\cdots b_{qT}(O_T)\\)<\/p>\n\n\n\n
        Probability of seeing those state transitions is \\(P(Q|\\lambda) = \\pi_{q1q2}a_{q2q3} \\cdots a_{qT-1qT}\\)<\/p>\n\n\n\n
        Probability of those seeing observations and<\/strong> those state transitions is P(O, Q|\u03bb) = P(O|Q, \u03bb)P(Q|\u03bb)<\/p>\n\n\n\n
        But we want the probability of the observations regardless of the particular state sequence P(O|\u03bb) = \\(\\sum_{all Q}\\)P(O|Q, \u03bb)P(Q|\u03bb)<\/p>\n\n\n\n
        Calculating this directly is infeasible P(O|\u03bb) = \\(\\sum_{q_1,q_2,\u2026,q_T}\\pi_{q_1}b_{q_1}(O_1)a_{q_1q_2}b_{q_2}(O_2)a_{q_2q_3} \\cdots a_{q_{T-1}q_T}b_{q_T}(O_T)\\)<\/p>\n\n\n\n
        How many state sequences are there? \\(N^T\\)<\/p>\n\n\n\n
        How many multiplications per state sequence? 2T-1<\/p>\n\n\n\n
        Total number of operations? \\((2T-1)N^T + (N^T-1)\\)<\/p>\n\n\n\n
        T = 100 and N = 5, How many operations?<\/p>\n\n\n\n
        \\((2T-1)N^T + (N^T-1) = (2(100) – 1)5^100 + (5^100 – 1) = 199 \\cdot 5^100 + 5^100 – 1 = 200 \\cdot 5^100 – 1 \\approx 5^103 \\approx 10^{72}\\)<\/p>\n\n\n\n
        We need a better way The forward-backward algorithm<\/p>\n\n\n\n
        Let’s introduce a helper function<\/p>\n\n\n\n
        \\(\\alpha_t(i) = P(O_1, O_2, O_3, …, O_t, q_t = S_i | \\lambda)\\)<\/p>\n\n\n\n
        Let’s solve for it inductively<\/p>\n\n\n\n