[ Week 9-1 ] Structured Classification

Lecture : Machine Learning

Date : week 9, 2024/04/29

Topic : Structured Classification 

 

 

1. Markov chain & Markov model 

2. Hidden Markov Model 

3. Probability evaluation

4. Optimal state sequence

 

 

---

1. Markov chain & Markov model 

1) Markov chain

(위키백과) 마르코프 연쇄(Markov chain)는 이산 시간 확률 과정이다. 마르코프 성질은 과거와 현재 상태가 주어졌을 때의 미래 상태의 조건부 확률 분포가 과거 상태와는 독립적으로 현재 상태에 의해서만 결정된다는 것을 뜻한다. 과거의 상태가 알려져 있더라도, 이는 미래 상태의 조건부 기댓값에 영향을 미치지 않는다.

 

- 한 state에서 다른 state로 넘어가는 과정을 확률 규칙으로 설명한 시스템 
- Markov Chain의 가정 

• 이산적인 시간 흐름에 따른 state 변화 
• t 시점에서 state는 바로 직전 t-1 state의 상태에만 의존한다
• 일련의 이전 state sequence가 주어졌을때, 다음 state의 조건부 확률 분포는 과거 state와는 독립적으로 바로 직전 state의 상태에 의해서만 결정된다.

 

 

2) Markov model (MM) 

- 여러개의 state, 각 state마다의 observatinon 

- sequence를 구성하는 사건들 간 Markov chain(혹은 Markov property)가 적용된다고 가정하는 모델 

- 이전의 모든 state를 다 고려할 필요없이 바로 직전의 state에 의해서만 현재 observation이 결정된다고 가정 
- n차 markov model : 현재 observation에 직전 n개의 state만 영향을 준다고 가정하는 모델 

- markov property를 사용함으로써 model parameter 개수를 줄이고 계산 효율을 높일 수 있음 

 

 

 

 

 

2. Hidden Markov Model (HMM) 

(위키백과) 은닉 마르코프 모형(영어: hidden Markov model, HMM)은 통계적 마르코프 모형의 하나로, 시스템이 은닉된 상태와 관찰가능한 결과의 두 가지 요소로 이루어졌다고 보는 모델이다. 은닉 마르코프 모형에서는 상태를 직접적으로 볼 수 없고 상태들로부터 야기된 결과들만을 관찰할 수 있다. 은닉 마르코프 모형로부터 생성된 결과들의 나열은 기저에 은닉된 상태들에 대한 정보들을 제공하고 있다고 생각할 수 있다.

 

출처 : https://yganalyst.github.io/ml/hmm/

 

- MM 모델 중 state가 숨겨져 있는 조건에서 사용하는 모델 

- 관측가능한 observation 결과로부터 state에 관한 정보를 예측 

- probability evaluation, decoding(optimal state sequence), learning(parameter estimation) task에 사용 

 

 

1) HMM 구성요소 2가지

• 관측할 수 없는 state sequence
• 관측할 수 있는 observation sequence

 

2) HMM 파라미터 3가지

• A : transition probability matrix, 상태전이 확률 행렬
• B : output probability matrix, 출력 확률 행렬
• Π : initial state distribution, 초기 확률분포

 

 

 

 

3. Probability evaluation

 

- 현재 모델에서 주어진 observation sequence가 관측할 확률을 계산하는 task 

- 현재 모델이 주어진 관측 결과를 얼마나 잘 관측할 수 있는지 판단 

   or 주어진 관측 결과가 현재 모델에 있어 얼마나 유효한 case인지 판단 

 

- forward algorithm을 이용하여 구체적으로 계산 

 

 

 

 

 

4. Optimal state sequence

- observation sequence가 주어졌을때 가장 가능성이 높은 state sequence를 예측하는 task 

- 관측 결과 뒤에 숨겨진 hidden state sequence를 decoding하는 task 

 

- Viterbi algorithm을 이용하여 구체적으로 계산 

: 전체 observation sequence state별로 delta와 pi값 계산 

  → Backtracking을 통해 주어진 sequence를 관측할 확률이 가장 높은 각 state 값 q_t*를 찾음 

 

 

 

 

 

 

 

 

Reference

https://ko.wikipedia.org/wiki/%EB%A7%88%EB%A5%B4%EC%BD%94%ED%94%84_%EC%97%B0%EC%87%84
https://ko.wikipedia.org/wiki/%EC%9D%80%EB%8B%89_%EB%A7%88%EB%A5%B4%EC%BD%94%ED%94%84_%EB%AA%A8%ED%98%95
https://sanghyu.tistory.com/17