Markov Models & Hidden Markov Models

Markov Chains

: Markov chain이란 sequences of random variables, states, values에 대한 probabilities를 말해주는 model이다. 이러한 set은 words, tages, symbols 등의 표현이 될 수 있다. 이는 current state에서 야기된 우리가 sequence에서 예측을 원하는 미래에 대한 강한 가정을 제공한다.

→ 과거 states(current state 이전)는 current state를 통하여 future expect에 영향을 끼치지 못한다.

- 아래 Markov chain figure을 보면 state는 graph에서 node로 표시되고, transition은 probability와 함께 edge로 표시된다. transition은 probability를 의미하며, given state를 떠나는 arcs의 값은 합이 1이어야 한다.

1. 특정 state의 probability는 previous state에만 의존한다.

: Sequence of state variables를 q_1, q_2, ... , q_i라고 하면, Markov model은 이 sequence의 probability에 대한 Markov assumption을 구현한다. Markov assumption은 미래를 예측할 때 과거는 중요하지 않고 오직 현재만 중요하다.

- Markov chain은 다음의 components로 세분화 된다.

set of N states

transition probability matrix A. 각 a_ij는 state i에서 j로의 probability를 나타낸다.

initial probability distribution over states. π_i는 state i에서 시작하는 Markov chain에서의 probability이다. 몇 state j는 π_j =0을 가지는데, 이는 해당 state가 initial state가 될 수 없다는 것을 의미한다.

Hidden Markov Model

: Markov chain이 sequence of observable events에서 probability를 계산하는데 유용하지만, 많은 problem에서 우리는 events를 직접적으로 observe 할 수 없다는 hidden 특성을 가지고 있다. 예를 들어, 문장 번역 시에 일반적으로 text에서 품사 tag를 관찰하지 않고, 오히려 word를 보고 word sequence에서 tag를 추론해야 한다. 이 때, tag를 관찰할 수 없기에 tag를 hidden이라고 부른다.

- Hidden Markov model(HMM)을 사용하면 우리가 probabilstic model에서 인과 요인으로 생각하는 observed event(input에서 보는 word와 같은)와 hidden event(예: 품사 tags)에 대해 알 수 있다. HMM은 다음 component로 정의된다.

set of N states

transition probability matrix A. 각 a_ij는 state i에서 j로의 probability를 나타낸다.

sequence of T observations

sequence of observation likelihoods, also called emission probabilities. 각각 state i에서 생성되는 observation o_t's probability

HMM assumptions

: first-order hidden Markov model은 두 가지 단순화 가정을 instatnce화 한다.

1. Markov chain과 마찬가지로 특정 state의 probability는 previous state에만 의존한다.

2. Output observation o_i의 probability는 observation q_i를 생성한 state에만 의존하며 다른 state 또는 다른 observation에는 의존하지 않는다.

HMM example

: 2022 여름 날씨에 대한 기록은 없지만, 그 여름에 Jason이 매일 먹은 아이스크림의 수를 나열한 일기를 찾을 수 있다. 목표는 이러한 observation을 사용하여 매일 온도를 추정하는 것이다. 추운 날(C)와 더운 날(H) 두 종류만 있다고 가정하여 날씨 작업을 단순화 하면 위 문제는 다음과 같이 정의할 수 있다.

observation sequence O(주어진 날에 먹은 아이스크림 수를 나타내는 integer)가 주어지면 Jason이 아이스크림을 먹게한 날씨 state(H or C)의 'hidden' sequence Q를 찾으시오.

HMM problems

: 해당 HMM은 3가지 fundamental problems로 구분된다.

Problem 1 (Likelihood): HMM λ = (A,B)과 observation sequence O가 주어지면 likelihood P(O | λ)를 결정한다.

Problem 2 (Decoding): HMM λ = (A,B)과 observation sequence O가 주어지면, best hidden state sequence Q를 찾는다.

Problem 3 (Learning): observation sequence O와 set of states in HMM이 주어지면, HMM parameter A와 B를 학습한다.

Likelihood Computation: The Forward Algorithm

Problem 1 (Likelihood): HMM λ = (A,B)과 observation sequence O가 주어지면 likelihood P(O | λ)를 결정한다.

: Problem 1인 특정 observation sequence에서의 likelihood를 계산하는 방법을 알아본다. Markov chain에서 surface observations이 hidden events와 동일한 Markov chain의 경우, 우리는 state 3 1 3에 대해 각 probability를 계산할 수 있다. 그러나 HMM의 경우에는 간단하지 않다. 우리는 3 1 3과 같은 아이스크림 observation sequence의 확률을 결정하고 싶지만, hidden state sequence가 뭔지 모른다.

- 이미 날씨를 알고 있고 Jason이 얼마나 많은 아이스크림을 먹을지 예측하고 싶다고 가정한다. given hidden state sequence(예: H H C)에 대해 3 1 3의 output likelihood를 쉽게 계산할 수 있다.

Hidden Markov Model의 경우, 각 hidden state는 single observation만 생성한다. 따라서 hidden state sequence와 observation sequence의 length는 동일하다.

- 특정 hidden state sequence Q = q_0, q_1, q_2, ... , q_T일 때, observation sequence O = o_1, o_2, ... , o_T, observation sequence의 likelihood는 다음과 같다.

- possible hidden state sequence H H C일 때, 아이스크림 observation이 3 1 3인 forward probability 계산은 다음과 같다. 아래 figure은 해당 계산에 대한 graphic representation이다.

- 그러나 우리는 hidden state (weather) sequence에 대한 실제 값을 모른다. 그 대신 weight를 부여한 모든 가능한 weather sequence를 합산하여, 아이스크림 event 3 1 3에 대한 확률을 계산한다. 먼저 특정 weather sequence Q에 있고, 아이스크림 event의 특정 sequence O를 생성할 joint probability은 다음과 같다.

- 아이스크림 observation 3 1 3과 하나의 가능한 hidden state sequence H H C의 joint probability는 아래와 같고 아래 figure는 계산의 graphic representation을 보여준다.

- 이제 특정 hidden state sequence일 때, observation에 대한 joint probability를 계산할 수 있다. 모든 hidden state sequence에 대한 observations의 total probability 계산은 다음과 같다.

- N hidden states와 T observation sequence가 있는 HMM의 경우, N^T개 가능한 hidden sequence가 존재한다. 실제 task에서는 N과 T 모두 크고, N^T는 매우 큰 숫자이므로 각 hidden state sequence에 대해 별도 observation likelihood를 계산한 다음 합산하여 total observation likelihood를 계산할 수 없다.

Forward algorithm

: 이러한 extremely exponential algorithm을 사용하는 대신, 우리는 forward algorithm이라고 하는 효율적인 O(N^2*T) algotirhm을 사용한다. forward algotirhm은 DP의 일종이며, table을 사용하여 observation sequence의 probability를 구축하면서 중간 value를 저장한다. obseration sequence를 생성할 수 있는 모든 가능한 hidden state paths의 probability를 합산하여 observation probability를 계산하지만, 이러한 각 path를 single forward trellis로 접음으로써 효율적이다.

- 아래 figure은 hidden state sequence H H C일 때, 3 1 3의 likelihood를 계산하기 위한 forward trellis의 예를 보여준다. a_2(2)를 보면, time step 2 state 2에서의 forward probability는 partial observation 3 1을 생성하고 있다. 우리는 위의 세 가지 요소로 구성된 두 개의 path로 ,step 1에서 a probabilities를 확장하여 계산한다. a_2(2) = α1(1)×P(H|C)×P(1|H) + α1(2)×P(H|H)× P(1|H)

- 각 cell에서의 forward algorithm trellis a_t(j)는 first t observation를 본 이후에 state j에서의 probability이다. 각 cell a_t(j)의 value는 해당 cell로 이어질 수 있는 모든 path의 probability를 합산하여 계산된다. formally, 각 cell은 다음 probability를 나타낸다.

- q_t = j는 "sequence of states에서 t th state가 state j이다."라는 의미이다. 현재 cell로 이어지는 모든 path의 extensions를 합산하여 probability a_t(j)를 계산한다. 시간 t에서 주어진 state q_j에 대해 value a_t(j)는 다음과 같이 계산된다.

- 위 equation에서 time t에서 forward probability를 계산하기 위해 이전 path를 확장할 때, 3가지 factors가 곱해진다.

이전 step으로 부터의 previous forward path probability

previous state q_i로부터 current state q_j로의 transition probability

주어진 current state j에서 observation symbol o_t의 state observation likelihood

- 아래 그림은 trellis의 하나의 새로운 cell에서 value를 계산하기 위한 유도 단계의 시각화를 보여준다.

- Forward algorithm에 대한 두 가지 formal definition을 제공한다.

Decoding: The Viterbi Algorithm

저작자표시 비영리

'논문 리뷰 > 개인 정리' 카테고리의 다른 글

DQN, DDQN, D3QN 비교 (0)	2022.07.04

Don't hesitate

Markov Models & Hidden Markov Models

Markov Chains