Please enable JavaScript.
Coggle requires JavaScript to display documents.
Markhov (Hidden (Probabilities (Initial, Transition, Emission), Output…
Markhov
Hidden
Data we're interested in is
Output independence
Output only depends on state that produced output
\( P(o_i|q_1 ...q_i,...,q_T ,o_1,...,o_i ,...,o_T ) = P(o_i |q_i)\)
Connecting observed state -> Hidden state
Probabilities
Initial
Transition
Emission
Complexity
Dynamic
Probability of single state
Given state = i and time = t
\(p_t(i) = \sum_j^Kp_{t - 1}(j)q_{ij}\)
O(K)
Probability of single state
given just the current time
\(p_t(i) = \sum_i^K \sum_j^Kp_{t - 1}(j)q_{ij}\)
\(O(K^2)\)
Computing an entire sequence for all possible states
\(p_t(i) = \sum_t^{T} \sum_i^K \sum_j^Kp_{t - 1}(j)q_{ij}\)
\(O(K^2(T-1))\)
Naive Approach
States
Future
Markov Assumption
Only depends on present
\(P(q_i = a|q_1...q_{i−1}) = P(q_i = a|q_{i−1})\)
Transitions
Matrix
Elements
\(q_{11}\) means what is the probability we start in state 1 and stay in state 1
\(q_{31}\) means what is the probability we start in state 1 but move to state 3
\(q_{end,start}\)
Rows
Each row must add up to 1
Origin
Chain
Diagrams
Algorithm
Dynamic
Applications
Hidden
Speach
Input: Sound waves
Interest: Words
Sequence of probabilities
Sequential Processes
Problems
Decoding
Naive
\(O(K^T)\)
Dynamic
Decoding Problem
Dynamic
Path that ends with hidden state = k
Go through all the observed states,
all the hidden states up to t -1
set the final state t as = k
Maximize since we want most likely
Virtrube
Most Probable Path(MPP) with length T that ends in state k
\(v_t(k)\)
max\(v_t(k)\) = Most Probable Path
Solving
Dynamic