# What/How model
- 표현해야 하는 값들 : 공간적인게 아니라, 시간적인 것들
-> 각각의 데이터들이 independent 하지 않다 (시간의 흐름에 있어서, 서로 의존적이다)
- 이를 표현하는 베이즈 네트워크 모양 : initial state가 다른 시간의 흐름들에게 연쇄적으로 작용한다
-> 모두 dependent 하다
# Hidden Markov 의 구성 확률
1) State Transition Probability
2) State Emission Probability
-> 내가 구해야 하는 것 : Hidden State!!!!
Emission 상태를 보고, 현재 어떤 State에 있을지를 추측함
# HMM 의 기초 질문들
1) Evaluation Question
- 정의 : π, a, b 가 주어져 있을때, X를 발견할 수 있는 확률은?
2) Decoding Question
- 정의 : π, a, b, X 가 주어져 있을때, 어떤 순서 Z 가 가장 확률이 높은가? (maximize 문제)
-> 여기서 Z는, X들의 순서를 의미 (X의 순열이라고 이해)
3) Learning Question
- 정의 : X 가 주어져 있을때, X값을 가장 크게 만들어주는 π, a, b 의 값을 구하라 (maximize 문제)
-> Gaussian 문제와 유사하다. 그때도, 데이터만 주어져있었지, 어떤 정규분포인지는
직접 찾아내야했었다.
** (2)Decoding 은 Supervised 와 유사, (3)Learning 은 Unsupervised 와 유사
** 어찌되었든간에, π, a, b 의 값은 반드시 알아야 한다
-> 최대한 많은 데이터들을 얻은 다음에, Supervised Learning을 해서 π, a, b값을 구한다
-> MLE, MAP, Counting 등등의 방법을 활용한다
# HMM 학습과정 : (1) Evaluation Question
- trainning set인 X, Z가 있다고 하자
- X : trainsition p.
- Z : emission p.
- 이떄, P( X, Z ) 값을 알아야 학습이 가능하다. 어떻게 학습해야할까?
-> Joint P. 를 사용한다!
-> 베이즈 정리를 사용해서, Bayesian Factorization을 수행하자!
- 단점 : 노드의 갯수가 많으면 많을수록, 계산이 엄청나게 복잡해진다
# HMM 학습과정 : (2) Decoding Question - 기본기 다지기
** X만 알고 Z에 대한 정보는 전혀 없을때, 어떻게 대처했었지?
- Gaussian Mixture Model (GMM) : marginalize 해줬음
- HMM : 마찬가지로, marginalize 해주자!!
- Marginal Probability 방식을 이용하면, 흥미롭게도 엄청나게 많은 parameter들이 사라진다
-> 계산이 엄청나게 간단해짐
-> 재귀적인 표현으로 나타낸 것. 반드시 식을 확인해보기
- 알아야 할 개념 : DP
- DP의 기본 방식 : Recursion + Memoization
- Recursion : Top->Down 형식. 큰 것을 작은 것으로 쪼개는 과정
- Memoization : Bottom->Up 형식. 작은 것에서부터 큰 것으로 점차 합쳐나가는 과정
- Forward Probability
- 방식 :
1) 앞서 배웠던, Marginal Probability 방식을 살펴보자
2) a_(n+1) = E * a_n * T 식에서, a_(n+1) 의 맨 첫번째 항을 살펴보자
3) a_1의 값을 구한 뒤엔, 2번에 있는 귀납법을 이용해서 최종 a_T 값을 구하자
-> 바로 이 a_T 값이, Z 값 없이도 구할 수 있는 확률값이 된다 ((1)evaluation question)
why? 애초에, X에 대한 marginalized된 식을 구하는 것이므로,
Z 값을 신경 안쓰고 계속 계산하는 방식이었다
- 이 전체적인 과정에서 DP가 사용되었다고 볼 수 있다.
- memoization table : a_t 값.
-> 작은 값(a_1) 에서부터 시작해서 계속 memoization을 해가며 값을 구하고 있다.
- 한계점 :
- 보통, 어떤 행위를 예측할 때에, 단순히 과거와 현재의 시점에서의 값만 고려하여
예측하지 않는다. (미래에 대한 예측값도 현재의 선택에 영향을 미침)
- 그러나, Forward Probability의 경우, 과거/현재의 사건들만이 현재의 선택에
영향을 미친다고 생각한다
-> 보완 필요!! : Backward Probability
- Backward Probability
- 방식 : Forward Prob.에선 a_(1~t) 까지의 상황만을 관찰해서 Z 값을 확인했다면,
Backward Prob.에선 a_(1~T) 까지의 상황을 관찰해서 Z 값을 확인해야 한다
-> t에서 T로 확장한 것. 즉, X의 일부분에서 X 전체로 확장을 시킨 것이다
- 공식 : P(z_t | X) = α * β
** β : backward prob, α: forward prob.
# HMM 학습과정 : (2) Decoding Question - 실제 적용 : viterbi algo
- forward/backword prob. 목적 환기 : 특정 t에서의 latent factor가 K cluster에 속할 확률을
joint prob. 으로 나타낸 것
** z_t 의 full name은 z_t **(k) 임. 수식을 적기 힘들어서 이렇게 못 표현한것임.
- forward/backward 의 한계점 : z_t **(k) 라는, "특정 시간 t" 에서의 확률값만 구한 것에 불과
-> 내가 진짜 알고싶은 것은, Z의 연쇄적인 series (HMM의 목적)
- Viterbi Decoding :
- 성질 : Supervised Learning
- 전체적인 풀이 방향 : 이전까지는 P(z_t, X) 같이, 딱 특정한 z 값에 대한 확률만 구했다면,
이번에는 P(Z, X) 같이, 모든 Z와 X값에 대한 확률을 구하려 한다
- 방식 : factorization을 통해, emission/transition prob. 을 사용한 식으로 V 식을 변형하자
- 식 : V_t **(k) = E * max( T, V_(t-1) )
- Viterbi 를 완성시키는 방법 ? : V_1 에서부터 차근차근, DP 방식으로 풀어나가자
- vierbi algo. 의 한계점 : 계속 연쇄적으로 확률 계산을 하다보면, 확률값이 너무 작아짐
( 0에 가까운 수가 나옴 -> 컴퓨터가 계산 오류 일으킴)
-> 해결책 : log 를 취해주면 계산이 조금 더 수월해짐
# HMM - unsupervised learning : Baum-Welch algo.
- 전체적인 원리 : Expectation Maximization (EM) 과정
- 문제의식 :
1) 앞서 배웠던 viterbi 의 경우, π, a, b 가 모두 주어진 경우다.
그러나, 대부분의 경우, 이와같은 값들은 주어지지 않는 값들이다.
2) π, a, b 라는 값 자체가, X과 Z 사이의 관찰값이 동시에 주어졌을때만 알 수 있는 값이다.
그러나, 대부분의 경우, 우리는 X 값만 알지, Z값은 알지 못하는 경우가 많다
- 전략 :
1) X 값들을 통해, π, a, b 값들을 추측한다
2) 추측된 π, a, b값들을 통해, Z 값을 추측한다
-> How? EM 알고리즘!!
- 순서 :
1) Z 를 assign 한다 - expectation
2) Z 를 활용해서, π, a, b 값을 갱신한다 - maximization
- maximization 방법? : 미분!!
- 근데, 제약조건이 있는 미분이다? : 라그랑주 method 사용해야함!! (그냥 미분하면 안됨)
-> 각각의 변수에 대한 편미분을 해줘서, π, a, b 값들을 구해낸다
3) 반복
'기계학습 > 카이스트 강의' 카테고리의 다른 글
(카이스트 강의) K-means, Gaussian Mixture Model (0) | 2019.08.17 |
---|---|
(카이스트 강의) Bayesian Network (0) | 2019.08.17 |