직접적으로 측정이 불가능한 상태의 존재와 이 기술이 적용될 다양한 데이터 셋에 대해 분명하게 옳은 정답은 얻을 수 없다는 것을 상정 한다. 그러면 은닉 상태들의 선험적 지식 없이 이 알고리즘은 은닉 상태들을 어떻게 식별 할 까? 그 대답은 바로 반복성에 있다. 관측을 설명 가능한 가장 적절한 은닉 상태를 도출하는 마법 같은 해결책은 존재하지 않는다. 그러나 완전하게 구체화된 시스템이 있다면 추정을 향해 나아갈 가능성은 열린다.
HMM은 시스템이 다음의 정보로 완전히 묘사된다고 상정 한다.
- x(t) 에서 x(t) +1로 전환될 확률, 이는 앞서 언급된 상태 A와 B간의 전환과 같은 행렬을 명시하는 것과 같다. 이 행렬의 크기는 가성을 세운 상태의 개수에 따라 다르다.
- x(t) 가 주어 졌을 때 관측 y(t)의 확률 또는 방출 확률 emission probability
- 시스템의 초기 상태
좀 더 구체적으로 HMM 과정의 묘사와 적합에는 다음의 변수가 필요하다.
- 시스템을 구성하는 개별 상태 : $Q = q_1, q_2, \cdot\cdot\cdot , q_N $
- 모든 시간 단계에서 상태 i에서 j로 바뀌는 전환에 대한 전환 확률 행렬 $ A = a_{i,j} = a_{1,1}, a_{1,2}, \cdot\cdot\cdot, a_{N,N}$
- 상태 $q_i$일 때 관측될 값 $o_t$의 방출 확률 : $b_{i(ot)}$
- 시스템 시작 시 갖는 $q_1 , q_2 , \cdot\cdot\cdot q_N$ 상태에 초기 확률 분포 : $p = p_1, p_2, \cdot\cdot\cdot, p_N$
그러나 이 변수들을 실제 데이터로 알 수 있는 경우는 거의 없다. 실제 데이터에서는 오직 실제로 관측된$ y_1, y_2, \cdot\cdot\cdot , y_t$ 만 알 수 있는 것이 보통이다.
바움 - 웰치 알고리즘
은닉 마르코프 모형에서는 바움-웰치 알고리즘 Baum - Welch algorithm 사용해 파라미터를 추정한다. 앞에서 나열한 모든 파라미터 값을 추정하는 복잡한 작업의 가이드 역할을 하는 알고리즘 이다. 그러나 전체적으로 다음 두 단계로 작업 한다.
- 가능한 각 은닉상태에 대한 개별 방출 확률, 즉 각 은닉상태 간의 전환 확률을 식별한다. 여기서 바움-웰치 알고리즘을 사용한다.
- 전체 관측에서 각 시간 단계별 가장 가능성이 높은 은닉 상태를 식별 한다. 여기서 비터비 알고리즘 Viterbi algorithm을 사용한다.
이 두 작업은 서로 연관되어 있다. 또한 각각은 어렵고, 계산적으로 부담이 큰 작업이다. 심지어 이 둘은 서로 의존 관계가 있다. 파라미터 추정과 우도 최대화같이 서로 작업이 연관된 경우, 기대 값 최대화 알고리즘을 사용하여 합리적인 해결책을 찾을 때까지 두 작업 사이를 반복해서 수행 할 수 있다.
바움-웰치 알고리즘을 적용하는 첫 번째 단계는 우도함수 likelihood function를 정의하는 것이다. 여기서의 가설 파라미터는 상정된 상태별 수학적 파라미터 이다.
예를 들어 두 상태로 구성된 모델에서 각 상태가 개별적인 평균 및 표준 편차로 가우스 분포를 가진 관측값을 만들어내면 이 모델은 $μ_1, σ_1,μ_2, σ_2$로 묘사될 수 있다. 여기서 $μ_{u=i}$와 $σ_i$는 각각 i번째 상태의 평균과 표준편차를 의미 합니다. 이들은 방출 확률을 묘사할 수 있고 이 방출 확률을 모아서 θ로 표현한다. 또한 상태의 순서를 $x_1, x_2, ...., x_t)$ (줄여서 $X_t)라고 상정한다. 이 상태의 순서는 관측 할 수 없지만 지금은 그럴 수 있다고 가정 한다.
그러면 우도함수는 주어진 방출확률(주어진 특정 상태에서의 관측확률)의 파라미터에 대한 관측 순서의 우도, 즉 $p(y_1, y_2, ... , y_t | μ_1, σ_1,μ_2, σ_2, ..., μ_N, σ_{N_t}) = p(y_1, y_2, ... , y_t | μ_1, σ_1,μ_2, σ_2, ..., μ_N, σ_N) $ d에 대한 모든 가능한 $X_t$를 묘사한다.
# 조건부 확률
어떤 사건 B가 일어났을 때 사건 A가 발생할 확률을 뜻한다. 기호는 P(A│B)로 표기하며, 확률 공간에서 두 사건 A, B가 있고 P(B)>0일 때, 사건 B가 일어나고 사건 A가 일어날 조건부 확률은 $ P(A|B) = { P(A∩B) \over P(B) }$가 된다. 이는 두 사건이 동시에 일어날 확률을 사건 B가 일어날 확률로 나눈 것으로, 조건부 확률에 있어서 사건 A가 발생할 확률이 사건 B의 확률에 영향을 받는다는 것을 나타낸다.
그러나 여기에는 시간 단계가 많아 질수록 복잡도가 지수적으로 증가하므로 격자 탐색이 현실적이지 못하게 되는 등 여러 가지 어려움이 있다. 따라서 다음과 같은 EM 알고리즘을 적용하여 작업을 간소화 해야 한다.
- 방출 확률별수를 무작위로 초기화 한다.
- 주어진 방출 확률값을 가정하여 가능한 $X_t$를 계산 한다.
- 더 나은 방출 확률변수의 추정치 생성에 $X_t$의 값을 사용한다.
- 수렴할 때까지 두 번째와 세 번째 단계를 반복한다.
쉽게 풀어 설명 하면, 두 개의 분포를 상정하는 무작위 사건 및 각 시간 단계에서 특정 상태일 확률을 결정한다. (예 : 시간 단계 t에서 상태 A나 B가 될 확률) 각 시간 단계에 추정상 상태를 할당하면, 그 추정 상태로 방출 확률을 재 추정한다. (상태에 대한 더 나은 평균 및 표준편차가 되도록 바로 잡는 과정이다.) 그리고 이 과정을 반복하여 $X_t$ 궤적의 추적 향상을 위해 새롭게 갱신 된 방출 확률 변수를 사용한다.
EM 알고리즘 사용에 대해 기억해야 할 중요한 사실은 전역적으로 최적의 파라미터를 찾는 것이 보장되지 않는 다는 것이다. 따라서 적합 과정을 여러 번 수행해 다양한 초기화에 걸쳐 전역적으로 공통된 최적 파라미터가 무엇인지 알아보는 것이 좋다. 또 다른 중요한 사실은 데이터와 모델의 세부 사항에 따라 적절한 정도의 예열시간이 필요하다는 점을 기억 해야 한다.
비터비 알고리즘
바움-웰치 알고리즘에 의해 HMM 과정의 파라미터가 추정되고 나면 그 다음 관측 가능한 측정값으로 구성된 시계열을 구성하는 가장 가능성 높은 상태들의 계열이 무엇인지 궁금할 것이다.
바움-웰치 알고리즘과는 다르게 비터비 알고리즘은 흥미로운 질문에 대한 최상의 해답을 제공한다. 비터비 알고리즘이 동적 프로그래밍 알고리즘이기 때문이다. 즉 특정 해결책에 도달하기 위해 부분적인 해결책을 만들고 저장하여, 적합 범위를 완전하면서도 효율적으로 탐색하게끔 설계된 것이다. 그러면 해결책에 도달하는 경로가 길어지더라도 모든 부분 경로의 해결책을 다시 계산할 필요가 없다.
 |
| 비터비 알고리즘은 주어진 관측된 시계열의 가능한 모든 경로를 검색한다. 여기서 경로는 각 시간단계에서의 상태를 뜻한다. |
데이터 과학자들이 표준적인 알고리즘을 항상 사용하는 것은 아니다. 하지만 시간상 정렬된 데이터의 개념에서 보면 추론과 반복이 유용한 시계열 분석에서는 기본적인 알고리즘이 꽤 유용 할 수도 있다.
동적 프로그래밍은 피보나치 수열 Fibonacci sequence로 예를 들어 설명하는 것이 쉽다. 여덟 번째의 피보나치 수를 계산 하는 상황을 떠올려 보자. 여섯 번째와 일곱 번째 피보나치 수를 알면 쉽게 계산 할 수 있다는 것을 직감적으로 알고 있을 것이다. 그러기 위해서는 네 번재와 다섯 번째 피보나치 수가 필요하다. 이런 식으로 계속 반복한다. 피보나치의 나중 수는 이전 수에 의해 결정된다는 사실을 알고 있으므로 피보나치 수를 계산할 때는 값들을 어디엔가 저장해야 한다. 이러한 이유로 동적 프로그래밍은 메모이제이션 memoization 기법으로도 묘사 되곤 한다.
동적 프로그래밍의 적용 가능한 상황은 다음과 같은 특징을 가진다.
- 크기 N-1 문제의 해결책을 알고 있다면 크기 N 문제의 해결책의 계산이 가능하다. 덜 복잡한 문제에 대한 해결책을 기억하거나 메모이제이션하면, 더 복잡한 문제를 효율적으로 해결 하는데 유용할 것이다.
- 작은 문제에서 큰 문제로 확장하기 위해 명확히 정의된 순서를 가진다.
- 즉시 쉽게 계산 할 수 있는 기본적인 상황을 식별 할 수 있다.
# 참고 : 실적 시계열 분석 - 한빛 미디어
댓글 없음:
댓글 쓰기