여러 개의 가능한 경우의 수 중에서 가장 적합한 시퀀스 하나를 찾는 문제를 풀어봅시다. 확률 모델을 활용해서 확률이 최대가 되는 시퀀스를 찾는 문제로 바꿔 풀 수 있습니다. 시퀀스의 심볼이 증가함에 계산량은 기하급수적으로 늘어나지만, 부분 중복이 많다는 시퀀스 특징을 이용하면, 비터비(viterbi) 알고리즘으로 효율적인 연산을 할 수 있습니다. HMM 확률 모델과 함께 품사태깅 문제를 푸는 과정에서 비터비 알고리즘이 어떻게 동작하는지 살펴봅시다.


1. 준비 & 동기

준비: HMM 모델 & 품사태깅 문제

품사 태깅(Part-Of-Speech (POS) tagging)은 기본적인 자연어처리 문제 중 하나로 단어마다 적합한 품사 태그를 붙여 구문 정보를 추가해주는 문제이다. 보통 언어는 단어 하나만 존재하는 것이 아니라 문장, 단락, 문서와 같은 단어들의 시퀀스로 구성된다. 단어 시퀀스를 품사 시퀀스로 매핑하는 시퀀스 라벨링 문제와 같다. 품사태깅으로 구문 정보를 획득할 뿐만 아니라 형태소 중의성을 해소해주는 역할도 할 수 있다.

하나의 단어가 여러 개의 품사를 가지고 문맥에 따라 달라지므로 단순한 규칙 리스트로 매핑하기 어렵다. 이를 해결하기 위해 데이터 기반의 확률 모델을 사용한다. 시퀀스 데이터에서 카운트 기반으로 확률 추정이 가능한 대표적인 모델은 HMM이다. 이에 대한 내용은 Hidden Markov 모델 (feat. 품사태깅) 글을 참조하길 바란다. HMM 모델을 통해 시퀀스 확률 추정을 효율적으로 할 수 있지만, 시퀀스 연산의 양이 매우 많아 알고리즘 속도 개선이 필요하다.

동기

품사 태그의 종류가 40개, 문장(시퀀스)의 최대 길이(단어 개수)가 20이라고 하자. 계산해야 될 모든 시퀀스 개수는 다음과 같은데, 이 정도의 계산을 다하려면 슈퍼컴퓨터가 필요할 것이다.

40^{20} = 1099511627776.0 \times 10^{20}

시퀀스를 일렬로 쭉 나열해보자. 이들의 특징은 맨 끝 토큰이 틀려도 아예 다른 시퀀스로 여겨진다. 토큰 단위로 보면 중복이 매우 많은 것을 알 수 있다. 이들의 중복 연산을 피할 수 있으면 노트북의 연산 능력이라도 계산이 가능할 수 있다.

(1) [명사] [주격조사] [명사] [부사격조사] [동사] [선어말어미] [종결어미]

(2) [명사] [주격조사] [명사] [부사격조사] [동사] [선어말어미] [연결어미]

(3) [명사] [주격조사] [명사] [부사격조사] [동사] [선어말어미] [접미사]

(4) ...

2. 비터비 알고리즘

동적 계획법

품사태깅 문제를 HMM과 같은 확률 모델로 풀면, 시퀀스 확률을 최대로 하는 최적화 문제와 같다. 이러한 시퀀스 최적화 문제는 수학 이론에서 유래된 동적 계획법(dynamic programming) 기법으로 쉽게 풀 수 있다. 동적 계획법은 분할 정복(divide and conquer)과 같이 주어진 문제를 부분문제로 쪼개고 이들의 결과물을 결합하면서 해결하는 방식이다. 분할 정복과의 차이점은 똑같은 부분문제가 재등장하는 점이다. 이렇게 재등장하는 부분문제의 결과물을 기억(캐시)함으로써 속도 향상을 꾀한다.

동적 계획법은 크게 하향식(top-down)과 상향식(bottom-up) 접근법이 있다. 전자는 대표적으로 재귀적(recursive) 방식을, 후자는 순환적(iterative) 방식을 가진다. 재귀적 방식은 코드가 간결하지만 순환적 방식보다 (캐쉬의) 공간 복잡도가 더 높다. 문제에 따라 선호되는 방식이 다르다는 점을 알아두자.

비터비 알고리즘 – 수도코드

비터비 알고리즘은 HMM 모델에서 가장 높은 확률의 (단어) 시퀀스를 출력하는 Hidden State의 (태그) 시퀀스를 찾는 알고리즘으로 동적 계획법에서 상향식(bottom-up) 접근법에 해당한다.

먼저, 수도코드(Pseudocode)로 비터비 알고리즘을 알아보자.

연산에 필요한 데이터와 이들의 변수명은 다음과 같다.

  • 관측(observation) 데이터 벡터: O = \{ o_1, o_2, ..., o_N \} – ‘단어
  • 히든(hidden) State 데이터 벡터: S = \{ s_1, s_2, ..., s_K \} – ‘태그
  • 전이확률 행렬: T of size K \times K such that T_{jj'} stores the transition probability of transiting from state s_j to s_{j'} – ‘태그태그 확률
  • 출력확률 행렬: E of size K \times N such that E_{ij} stores the probability of observing o_i from state s_i – ‘태그단어 확률
  • 통합확률 행렬: V of size N \times K such that V_{ij} stores the total probability of { 이전 time의 통합확률 \times 현재 time의 전이확률 \times 현재 time의 출력확률 } at each state
  • 백포인터 벡터: B = \{ b_0, b_1, b_2, ..., b_N, b_{N+1}  \} such that B_i stores 이전 관측 time에서의 최대의 통합확률을 가지는 태그 인덱스 저장

미리 준비해야 되는 것들은 다음과 같다.

  • 전이확률과 출력확률은 사전에 모두 준비해야 한다. 이들은 보통 코퍼스로부터 추정된다.
  • 확률 데이터가 없는 경우(태그-태그 또는 태그-단어)는 smoothing 처리를 하여 확률이 모두 0 초과인 아주 작은 값으로 할당되어야 한다.

Hidden State와 관측 데이터의 맨 앞 뒤 바운더리를 추가한다.

  • ‘START’ 태그와 ‘END’ 태그를 s_0 s_{K+1}로 따로 두어서 초기확률이 전이확률에 포함되도록 한다. ‘START’와 ‘END’ 태그가 포함된 전이확률은 실제 데이터에서 추정 가능하다.
  • 관측 데이터의 맨 앞 o_0 과 맨 뒤 o_{N+1}에 각각 <S>, </S> 와 같은 더미 데이터를 둔다. o_0 의 통합확률은 1.0 이고 o_{N+1}의 출력확률은 1.0이다.
function `Viterbi`(O,S,T,E ): X 

        # initialization step
        for each state k = 1,2,...,K  in S   do
                V[0,0] \leftarrow  1.0    # start at <s>
                V[1,j] \leftarrow  V\lbrack0,0\rbrack \times T_{0j} \times E_{ij}  
                B[1,j] \leftarrow  0

        # bottom-up step
        for each observation i = 2,...,N  in O  do
                for each state j = 1,2,...,K  in S   do
                        for each state k = 1,2,...,K  in S   do
                                temp[k] \leftarrow   V\lbrack{i-1},j\rbrack \times T_{kj} \times E_{ij} 
                        V[i,j] \leftarrow  max(temp[k])
                        B[i,j] \leftarrow  temp[k].index(V[i,j])

        # termination step
        for each state k = 1,2,...,K  in S   do
                E[N+1,K+1] \leftarrow  1.0    # end at </s>
                for each state k = 1,2,...,K  in S   do
                        temp[k] \leftarrow   V\lbrack{N},k\rbrack \times T_{k(K+1)} \times E_{(N+1)(K+1)} 
                V[N+1,K+1] \leftarrow  max(temp)
                B[N+1,K+1] \leftarrow  temp.index(V[N+1,K+1])
     
        # backtracing step
        for each observation ri = N+1,N,...,2  in O  do
                if ri is N+1:
                        cur_idx \leftarrow  B[ri,K+1]
                else:
                        cur_idx \leftarrow  B[ri,prev_idx]
                X[ri-1] \leftarrow  S_{cur\_idx} 
                prev_idx = cur_idx

        return X

실질적으로 알고리즘이 실행되는 단계는 bottom-up 단계와 backtracing 단계이다. initialization 단계와 termination 단계는 바운더리를 처리하기 위함이다. bottom-up 단계에서 forward 방향으로 index가 이동하면서 각 state 마다 필요한 계산을 미리 해놓는다. 이 과정에서 max 함수를 통해 최대 통합확률을 가지는 이전 time의 태그 인덱스를 백포인터에 저장한다. 캐싱된 내용은 backtracing 단계에서 베스트 시퀀스를 선형 시간으로 찾도록 해준다.

비터비 알고리즘 – 그림

비터비 알고리즘의 실행 흐름을 비주얼하게 살펴보자.

문제를 간소화하여 태그는 ‘명사’, ‘동사’, ‘조사’만 구성되고, 관측 데이터는 ‘아빠’, ‘가’, ‘방’, ‘을’, ‘보다’로 구성된다. 이들의 가능한 모든 연산의 경우는 다음과 같이 비터비 격자(lattice)로 표현할 수 있다.

위는 bottom-up 단계를 진행한다. 이는 먼저 필요한 계산을 다 해놓는 느낌이다. 시퀀스 계산을 통째로 하는 것이 아니라 어느 한 시점 (특정 observation time과 특정 state)을 기준으로 확률 계산을 따로 한다.

예를 들어, 어느 한 시점인 Observation Time 2와 State 2를 기준으로 통합확률, 전이확률, 출력확률은 다음 그림과 같이 계산된다. Observation time과 state time으로 하나씩 이동하면서 이런 확률들을 모두 계산한다.

Observation Time 순으로 비터비 알고리즘 계산이 수행된다. 여기서 중요한 점은 매 순간 이전 Time에서 가장 통합확률이 높은 State를 백포인터 벡터에 저장한다(비터비 알고리즘의 캐싱). 다음 그림에서 굵은 화살표는 캐싱된 이전 State를 표현한다.

END state 까지 이러한 계산을 반복한다.

마지막으로 backtracing을 해서 다음과 같이 가장 확률이 높은 State 시퀀스를 구한다. END 부터 START 까지 각 단계에서 최대 확률로 저장된 state만 거꾸로 쭉 따라가기만 하면 된다. 여기서는 빨간색으로 표현했다. 이를 viterbi path라고도 한다.

이렇게 비터비 알고리즘을 거치면 단어 시퀀스, ‘아빠’, ‘가’, ‘방’, ‘을’, ‘보다’에 대해서 가장 적합한 태그 시퀀스, ‘명사’, ‘조사’, ‘명사’, ‘조사’, ‘동사’를 출력할 수 있다.

형태소 분석을 하면 세그멘트 조합이 여러 개 생길 수 있다. 위에서는 ‘아빠’, ‘가’, ‘방’, ‘을’, ‘보다’로 1개로만 표현했지만 ‘아빠’,’가방’,’을’,’보다’와 ‘아빠가방’,’을’,’보다’ 등으로 여러 개의 세그먼트 조합이 생길 수 있다. 비터비 알고리즘으로 품사태깅을 하는 과정에서 이러한 세그먼트 조합의 중의성도 해결할 수 있다.


3. 마무리

자연어처리는 시퀀스 모델링이 어려운 문제입니다. 비터비 알고리즘은 다이나믹 프로그래밍의 일종으로 시퀀스 연산을 효율적으로 할 수 있습니다. 이에 자연어처리에서 비터비 알고리즘을 많이 활용되며 품사태깅을 위한 통계적 방법론에서도 사용됩니다. 시퀀스 길이가 길어질수록 연산의 양은 기하급수적으로 늘어나지만, 비터비 알고리즘으로 이러한 연산량을 획기적으로 줄일 수 있습니다.

4. 참고