읽기일기

패턴 인식 (7) 순차 데이터의 인식


패턴인식, 오일석 지음/교보문고

7. 순차 데이터의 인식

본질적으로 특징 간에 시간 관계가 존재하고 그것을 적절히 이용하지 않으면 원하는 성능을 얻을 수 있는 데이터가 있다. 지진파나 음성, 주식 거래량 등의 시계열 데이터들이 여기에 해당한다. 이러한 시간성(temporal property)를 갖는 데이터를 순차 데이터(sequential data)라고 부른다. 또는 시간성을 갖는 것은 아니지만 비슷한 속성을 지닌 경우도 있다. 문서에 나타나는 문장은 단어 간 앞 뒤 관계가 있고 단어 속 문자들도 앞 뒤 관계를 갖는다. 이러한 데이터들을 총칭하여 문맥 의존(context-dependent) 데이터라고도 한다.

이러한 패턴을 인식하기 위해서는 시간성을 적절히 표현하고 그것으로부터 원하는 정보를 추론할 수 있는 모델이 필요하다. 은식 마코프 모델(hidden markov model, HMM)은 이런 능력을 가진 대표적인 방법이다.

7.1 순차 데이터

시간 성이 없는 특징 벡터에서는 특징들이 서로 위치를 바꾸어도 아무 문제가 되지 않는다. 하지만 순차 데이터는 특징들이 나타나는 순서를 바꾸면 패턴의 물리적인 특성이 왜곡되어 버린다. 또한 순차 데이터는 대부분 가변 길이를 갖는다. 표기 상으로는 시간 개념을 표시하여 첨자를 i대신 t로 쓰고, 길이를 d 대신 T로 쓰는 것이 일반적이다. 특징 $x_t$를 보통 시간 t에서의 관측(observation)이라고 부르고 $o_t$로 표시한다.

HMM은 관측이 스칼라이고 이산인 경우를 다룬다. 따라서 관측 벡터는 아래와 같이 표시할 수 있다.

$$O = ( o_1, o_2, \dots, o_{t-1}, o_t, t_{t+1}, \dots, o_T )$$

관측은 이산 값을 가지므로 유한한 수의 값 중 하나를 갖게 된다. 이러한 값의 집합을 알파벳이라 하고 $ V = \{ v_1, \dots, V_m \} $으로 표시한다. 알파벳을 구성하는 값 $ v_i $를 기호(symbol)이라고 한다.

순차 데이터가 갖는 중요한 특성이 있다. 알파벳을 구성하는 기호들이 시간에 따라 의존성을 갖는다는 것이다. 특정 기호는 다른 어떤 기호 뒤에 나올 확률이 높거나 낮을 수 있는 것이다.

7.2 마코프 모델

은닉 마코프 모델은 베이시언 분류기와 마찬가지로 확률 분포와 그것의 연산에 바탕을 두고 잇는 확률 모델(stochastic model)을 이용한다.

마코프 사슬(chain) 이론은, 시간 t에서의 관측은 가장 최근 r개의 관측에만 의존한다는 가정을 하고 있다. 이를 수식으로 나타내면 아래와 같다.

  • 0차 마코프 체인 (r=0) : $ P(o_t | o_{t-1}o_{t-2} \dots o_1) = P(o_t) $
  • 1차 마코프 체인 (r=1) : $ P(o_t | o_{t-1}o_{t-2} \dots o_1) = P(o_t | o_{t-1}) $
  • 2차 마코프 체인 (r=2) : $ P(o_t | o_{t-1}o_{t-2} \dots o_1) = P(o_t | o_{t-1}, o_{t-2}) $

HMM에서는 마코프 모델을 1차 마코프 체인을 사용한다. 1차를 사용하는 이유는, 패턴 인식에서 풀고자 하는 문제들이 견딜 수 있을 정도의 오차로 1차 마코프 체인 가정을 만족하기 때문이다. 두 번째 이유는 2차 이상의 마코프 체인을 사용하면 보다 정확한 결과를 얻을 수 있지만, 추정해야 하는 매개 변수가 너무 많아서 현실적으로 적용이 불가능한 경우가 대부분이기 때문이다.

알파벳이 $ V= \{v_1, v_2, \dots, v_m \} $일 때 m개의 기호를 각각 상태(state)로 간주한다. 어느 한 상태에서 다른 상태로 변화될 확률을 알고 있다고 가정한다면 이를 행렬로 나타낼 수 있다. 이러한 행렬을 상태 전이 확률 행렬(state transition probability matrix)이라고 한다. 이 행렬은 마코프 모델의 모든 정보를 담고 있으므로 그 자체를 마코프 모델로 간주할 수 있다.

확률 행렬을 그래프를 이용하여 시각적으로 표현할 수도 있는데 이것을 상태 전이도(state transition diagram)이라고 한다.

마코프 모델 하에서 관측 벡터 $O$의 확률 $ P(O | \text{markov model}) $은 아래와 같이 나타낼 수 있다.

$$PO | \text{markov model}) = P(o_1) \prod_{i=1}^{T-1} p(o_{i+1} | o_{i})$$

온라인 필기 숫자의 예제를 들어보면, 기존의 훈련 집합을 통하여 상태 전이 확률 행렬 $A$를 생성한다. 주의할 점은 한 행의 확률 값은 1이어야 한다는 것이다. 초기 확률 $ \pi_i $또한 구하자.

이제 주어진 샘플에 대하여 확률을 계산할 수 있다.

또한 모든 상태 전이에 대하여 확률을 알고 있으므로, 첫번째 코드를 생성한 후 A의 확률 분포에 따라 코드를 생성해나갈 수 있다. 따라서 이는 생성 모델(generative model)로 취급된다.

2차 마코프 체인을 사용하려면 상태 전이 확률 행렬의 크기가 더 커져야 할 것이다.

7.3 은닉 마코프 모델로의 발전

마코프 모델은 그 자체로 여러 응요에 사용되지만 모델링 능력에 한계가 있다. 특히 훈련 집합으로 학습을 한 후 새로 들어오는 샘플을 높은 성능으로 분류하는 일에는 한계를 들어낸다. 따라서 상태를 숨긴 은닉 마코프 모델(HMM)로 확장하여 본다.

7.3.1 동기

마코프 체인의 차수가 늘어남에 따라 다루어야 할 매개변수는 기하급수적으로 늘어난다. 즉 모델의 크기가 증가하는 것이다. 일반적으로 r차 마코프 체인은 $ m^r(m-1)$개의 매개변수를 추정해야 한다. 따라서 차수를 늘리면 정확한 모델링이 가능하나 계산량이 감당하기 어려울 정도로 늘어나버린다. HMM은 차수를 미리 고정하지 않고 모델 자체가 확률 프로세스에 따라 적응적으로 정하도록 한다. 따라서 먼 과거의 관측이라도 현재에 영향을 미친다.

상태 전이 그래프의 관점에서 살펴보도록 하자. 마코프 모델에서는 각 노드가 곧 상태를 나타내고 노출되어있다. 하지만 HMM에서는 모든 노드에서 모든 상태를 관측할 수 있다. 단지 노드에서 각 상태가 관측될 수 있는 확률을 가지며, 이들 확률 값은 모두 다르다. 관측된 상태와 노드가 일치하지 않으므로 실제 문제를 푸는 과정에서는 노드가 은닉되었기애 현재 어느 노드에 있는지 알지 못하고 관측 값만을 다루게 된다.

7.3.2 HMM의 예

7.3. 구성 요소와 세가지 문제

그렇다면 은닉된 상태로 훈련 집합을 통하여 HMM을 어떻게 학습하여야 할까? 수학적으로 공식화해보자.

아키텍처

HMM은 가중치를 갖는 방향으로 표현된다. 노드는 상태를 나타내며, 상태는 $s_i$로 표기한다. 모든 노드 간에 완전히 에지를 갖는 구조를 어고딕(ergodic) 모델이라 부르고, 단방향으로 배열한 모델은 좌우(left-to-right) 모델이라 부른다.

각 상태에서는 m개의 기호를 관측할 수 있는데, 어느 순간에서는 그 중 하나가 관측된다.

매개 변수

HMM은 세 가지 매개 변수 $ \Theta = (A, B, \pi) $를 갖는다.

  1. 상태 전이 확률 $ A= |a_{ij}|$
    A는 HMM 작동하는 도중, 다음 상태로 전이될 확률을 결정한다. $a_{ij}$는 시간 t에 상태 $s_i$에 있다가 시간 t+1에 $s_j$로 이동할 확률이다.

    $$a_{ij} = P(q_{t+1} = s_j | q_t = s_i)$$

    $$\sum_{j=1}^n a_{ij} = 1$$

  2. 관측 확률 $ B = |b_j(v_k)| $
    B는 HMM이 어떤 상태에 도달하였을 때, 그 상태에서 관측될 기호를 결정한다. $ b_j(v_k)$가 상태 $s_j$에서 기호 $v_k$가 관측될 확률이다. 수식으로 나타내면 다음과 같다.

    $$b_(v_k) = P(o_t = v_k | q_t = s_j)$$

    $$\sum_{k=1}^m b_j(v_k) = 1$$

  3. 초기 상태 확률 벡터 $ \pi = | \pi_i | $
    $\pi$는 HMM을 기동시킬 때 어느 상태에서 시작할 지를 결정하는데 쓰인다. $ \pi_i $는 상태 $ s_i $에서 시작할 확률이다. $ \pi_i = P(q_t = s_i) $ 역시 이들의 합은 1이 되어야 한다.

세가지 문제

HMM을 실제 문제에 적용하기 위해서는 세가지 문제를 풀어야 한다.

  1. 평가(evaluation)
    모델 $ \Theta $가 주어져있고, 관측 벡터 $ O = o_1, \dots, o_T $를 얻었을 때 관측값이 발생할 확률 $ P(O | \Theta)$를 구하는 문제. 이러한 문제는 분류 목적으로 사용된다.

  2. 디코딩(decoding)
    모델 $ \Theta$가 주어져 있고 관측 벡터 O를 얻었을 때 최적의 상태 열 $ Q = (q_1, \dots, q_T) $을 구하여라.

  3. 학습
    N개의 관측 벡터를 가진 훈련 집합 $ X = \{ O_1, \dots, O_N \} $이 주어져있을 때, 이들 관측 벡터가 발생할 확률을 최대화하는 매개변수 $\Theta$를 찾아라.

7.4 알고리즘

이제 세가지 문제에 대하여 알고리즘을 알아보자.

7.4.1 평가

매개변수를 알고 있는 상태라면 확률 값을 구하는 것은 간단하다. 관측과 전이를 반복하는 과정에서 발생하는 확률을 모두 곱하면 된다.

$$P(O, Q | \Theta) = \pi_{q1} b_{q1} (o_1) a_{q1 ,q2} b_{q2}(o_2) a_{q_2,q_3} \dots$$

하지만 실제로 상태 열 Q를 알지 못하므로, 직접 계산하지 못하기 때문에 모든 가능한 상태 열 Q에 대하여 모두 더하여 답을 찾는 것이 합리적이다.

$$P(O | \Theta) = \sum_{Q} P(O, Q | \Theta)$$

이러한 접근법은 가능한 상태열의 수가 많아질 수록 엄청난 계산이 필요하여 계산 폭발(computational explosion)이 발생해버린다.

계산의 효율을 위해서 각 상태 경로마다 중복되는 부분을 이용하면 순환적으로 계산할 수 있다. 바로 동적 프로그래밍 방버을 사용한다.

$$\alpha_1(i) = \pi_i b_i(o_1)$$

$$\alpha_t(i) = (\sum_{j=1}^n \alpha_{t-1}(j) a_{ji}) * b_i(o_t)$$

$$P(O | \Theta) = \sum_{j=1}^n a_T(j)$$

이러한 방법을 전방 알고리즘(forward algorithm)이라 부른다.

자세한 알고리즘은 책을 참고하자.

7.4.2 디코딩

디코딩은 관측 벡터를 얻었을 때 상태 열을 구하는 것이다. 단순하게 생각한다면 전후 관계를 생각지 않고 각 관측 값에서 가장 높은 확률을 갖는 상태를 선정하는 방법을 사용할 수도 있을 것이다. 하지만 이는 마코프 체인을 전혀 고려하지 않는 방법이다.

문제를 제대로 풀기 위해서는 $ P(O, Q | \Theta)$를 기준 함수로 채택하고 이것을 최대화 하는 $\hat{Q}$를 찾으면 된다. 역시 마찬가지로 모든 열에 대해서 계산하기에는 후보가 너무 많다. 비슷한 방법으로 동적 프로그래밍을 사용하여보자. 앞에서 사용했던 방법에서 확률을 합하는 연산을 최대 값을 선택하는 방법으로 바꾸어주기만 하면 된다.

$$\chi_1(i) = \pi_i b_i(o_1)$$

$$\chi_t(i) = (\max x_{t-1}(j) a_{ji}) * b_i(o_t)$$

$$\tau_t(i) = \arg \max(\chi_{t-1}(j)a_{ji})$$

$ \chi_t(i)$는 관측 벡터 일부를 관측하는 시간 t에서 상태 $s_i$에 있을 최대 확률이다. $ \tau_t(i)$는 n개 상태 중 선택한 것을 기록한다.

디코딩 문제는 전방 계산을 마친 후 $tau$를 역추적하여 경로를 찾는 작업을 추가로 해야한다. 이렇게 찾은 경로를 $\hat{Q} = (\hat{q}_1, \dots \hat{q}_T) $로 표시한다.

$$\hat{q}_T = \arg \max \chi_T(j)$$

$$\hat{q}_t = \tau_{t+1} (\hat{q}_{t+1})$$

이러한 방법을 Viterbi 알고리즘이라 부른다.

7.4.3 학습

앞의 두 가지와는 반대의 작업이다. 역시 모든 경로를 계산하는 것은 적절치 않다. 기본적인 아이디어는 다음과 같다.

  1. $\Theta$의 초기화
  2. 적절한 방법으로 $P(O | \Theta_{new}) \gt P(O | \Theta) $$\Theta_{new}$를 찾는다.
  3. 만족스러운 파라미터를 찾을 때 까지 2를 반복

다시 한번 문제를 살펴보면, 관측 벡터 O를 알고 있고 찾아야 하는 것은 파라미터들인데 이들은 O와는 직접적으로 관련이 없고 상태 변수 Q와 관련이 있다. 즉 매개 역할을 하는 변수 Q가 더 필요한 것이다. 이것을 이미 EM 알고리즘에서 등장하였고 은닉 변수(latent variable)이라고 부른다. 앞의 가우시안 혼합 문제에서는 은닉 변수가 독립 동일 분포(independent and identical distribution, iid)라고 가정하였지만 HMM은 분포들이 시간에 따라 관련성을 갖는다고 생각하는 것이 다른 점이다. 비슷한 방법으로 EM알고리즘을 적용하여 보자.

Baum-Welch 알고리즘이 사용하는 은닉 변수는 $\gamma_t(i)$$\kappa_t(i,j)$ 두가지가 있다. $\gamma_t(i)$는 모델 $\Theta$와 관측 벡터 $O$가 주어져있을 때, 시각 t에서 상태 $s_i$에 있을 확률이다. 즉 다른 t에 대해서는 무방하다.

$$\gamma_t(i) = P(q_t = s_i | O \Theta) = \frac{\alpha_t (i) \beta_t (i)}{\sum_{j=1}^n \alpha_t (j) \beta_t (j)}$$

식에서 $ \alpha$를 전방 변수, $\beta$를 후방 변수로 부르기로 하자.

$$\alpha_t(i) = P(o_1, \dots, o_t, q_t = s_i | \Theta ) = (\sum_{j-1}^n \alpha_{t-1} (j) a_{ji} ) * b_i(o_t)$$

$$\beta_t(i) = P(o_{t+1}, \dots, o_T, q_t = s_i | \Theta ) = (\sum_{j-1}^n a_{ij} b_j(o_t+1) \beta_{t+1}(j)$$

$ \alpha$의 경우 전방 알고리즘으로 구할 수 있다. $ \beta $는 비슷하게 아래 방법으로 계산된다.

$$\beta_T(i) = 1$$

$$\beta_t(i) = \sum_{j=1}^n a_{ij} b_j(o_{t+1}) \beta_{t+1} (j)$$

두번째 은닉 변수 $ \kappa_t(i, j)$는, 시간 t에서는 $s_i$, t+1에서는 $s_j$의 상태에 있을 확률이다. $ \gamma$와 비슷한 방법으로 계싼할 수 있다.

$$\kappa_t(i, j) = \frac{\alpha_t(i) a_{ij} b_j(o_{t+1}) \beta_{t+1}(j)}{\sum_{k=1}^n \sum_{l=1}^n \alpha_t(k) a_{kl} b_l(o_{t+1}) \beta_{t+1}(l) }$$

EM 알고리즘에 적용하여 다음과 같이 업데이트한다.

$$a_{ij}^{\text{new}} = \frac{\sum_{t=1}^{T-1} \kappa_t(i, j)}{\sum_{t=1}^{T-1} \gamma_t(i)}$$

$$b_i(v_k)^{\text{new}} = \frac{\sum_{o_t=v_k, t=1}^{T-1} \gamma_t(i, j)}{\sum_{t=1}^{T-1} \gamma_t(i)}$$

알고리즘 초기에는 난수를 발생시켜 $A, B, \pi$를 초기화하면 된다. 확률 값이기에 이들이 합은 1이 되어야 하며, 0이어야 하는 변수를 제외한 나머지는 0으로 설정되면 안된다.

학습 과정에서 어고딕 모델에서는 t가 커짐에 따라 $ \alpha$의 크기가 점점 작아져 T가 커질 수록 크기 문제(scaling problem)이 발생할 수 있다. 좌우 모델에서는 어떤 상태가 오른쪽 이웃으로 전이해버리면 자신으로 돌아올 수 없어 확률의 추정이 부실할 가능성이 존재한다. 이를 해결하는 방법은 기존의 연구를 참고하도록 하자.

7.5 부연 설명

  1. HMM의 출력은 확률이다. 신경망과 SVM의 출력은 확률이 아님에 비하여 이는 큰 장점이 될 수 잇다.
  2. HMM은 확률 추론에 기반하기 때문에 샘플 생성 능력이 있다.
  3. HMM을 예측 목적으로 사용할 수 있다. 현재 시점까지 관측열이 발생하였을 때 다음 관측을 예측하는 작업이다.
  4. HMM을 분류기로 사용할 수 있다. 각 부류에 대하여 독립적으로 HMM을 구축하고, 이에 관측 벡터를 입력으로 하여 가장 높을 확률을 갖는 부류를 선택하면 된다.
  5. 적절한 아키텍처를 선택하여야 하나 이는 사람의 몫이다.
  6. 상태의 개수도 마찬가지로 사람의 몫이다.
  7. 공개 소프트웨어가 있다. 대표적으로 HTK(HMM Toolkit)이 있다.


Add a Comment Trackback