for textmining

비터비 알고리즘

|

이번 글에서는 비터비 알고리즘(Viterbi Algorithm)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 참고해 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.

concept

비터비 알고리즘이란 히든 스테이트의 최적 시퀀스(the most likely sequence of hidden states)를 찾기 위한 다이내믹 프로그래밍(dynamic programming) 기법의 일종입니다. 여기서 히든 스테이트란 은닉마코프모델 등의 추정 대상인 품사, 개체명 등을 가리킵니다. 은닉마코프모델에 적용된 비터비 알고리즘을 파이썬 코드로 구현한 내용은 이곳을 참고하시면 좋을 것 같습니다.

어쨌든 비터비 알고리즘을 이해하기 위해서는 은닉마코프모델 등의 아키텍처뿐 아니라 다이내믹 프로그래밍 개념(반복되는 계산 결과를 저장해 두었다가 풀기)을 익히고 있어야 하는데요. 이 글에서는 다이내믹 프로그래밍의 대표적 예시 가운데 하나이자 비터비 알고리즘과 유사한 기법인 Assembly-Line Scheduling을 중심으로 살펴 보겠습니다.

Assembly-Line Scheduling

Assembly-Line Scheduling 문제는 2개(혹은 그 이상)의 조립라인 사이에서 생산비용을 최소화하는 최적 경로(path)를 찾는 문제입니다. 다음 그림과 같습니다.

위 그림에서 동그라미는 비용(cost)을 나타냅니다. 제품은 1번 내지 2번 라인을 자유롭게 오갈 수 있습니다. 제품이 첫번째 공정에서 1번 라인에 보내진다면 그 비용은 2+7, 즉 9가 됩니다. 제품이 첫번째 공정에서 2번 라인에 보내진다면 비용은 4+8, 즉 12가 됩니다. 이를 식으로 쓰면 다음과 같습니다.

  • $f_1[1]=2+7=9$
  • $f_1[2]=4+8=12$

그러면 두번째 공정에서 제품이 1번 라인에 있다면 그 최소 비용(=$f_2[1]$)은 얼마일까요? 두 가지 경우의 수를 생각해 볼 수 있습니다. 첫번째 공정에서 1번 라인, 두번째 공정도 1번 라인인 case입니다. 또 첫번째 공정에서 2번 라인, 두번째 공정은 1번 라인인 case입니다. 두 경우 중 작은 값을 취해 구합니다.

그렇다면 두번째 공정의 1번 라인을 기준으로 보면, 1번 라인을 유지하는게 나을까요, 아니면 1번에서 2번으로 라인을 바꾸는 것이 좋을까요? 각각의 비용은 18, 23이므로 유지하는 것이 좋습니다. 제품이 두번째 공정에서 1번 라인에 있다면 생산비용을 줄이기 위한 제품의 최적 경로는 1번 라인(직전 공정) → 1번 라인(현재 공정)입니다.

이를 식으로 나타내면 다음과 같습니다.

  • $l_2[1]=1$

같은 방식으로 $f_2[2]$와 $l_2[2]$를 구하면 각각 다음과 같습니다. 다시 말해 제품이 두번째 공정에서 2번 라인에 있다면 제품의 최적 경로는 1번 라인 → 2번 라인입니다.

  • $f_2[2]=min(4+8+5,2+7+2+5)\=min(f_1[2]+5,f_1[1]+2+5)=min(17,16)=16$
  • $l_2[2]=1$

그런데 구하는 과정을 자세히 보면 처음에 구한 $f_1[1]$과 $f_1[2]$을 다음 공정에 소요되는 최소 비용을 구할 때 재활용한다는 사실을 알 수 있습니다. 이처럼 계산과정이 반복될 때 중간 계산과정을 저장해 두었다가 해당 계산결과가 필요할 때 다시 써먹는 기법을 다이내믹 프로그래밍이라고 합니다.

위와 같은 과정을 반복해 각 단계별 최소 생산비용을 구한 표는 다음과 같습니다.

$j$ 1 2 3 4 5 6
$f_j[1]$ 9 18 20 24 32 35
$f_j[2]$ 12 16 22 25 30 37

각 단계별 최적 경로는 다음과 같습니다.

$j$ 2 3 4 5 6
$l_j[1]$ 1 2 1 1 2
$l_j[2]$ 1 2 1 2 2

자, 이제는 제품이 라인을 빠져나가는 경우를 생각해 봅시다. 제품이 여섯번째 공정까지 왔고 1번 라인에 있는 경우의 최소 소요비용($f_6[1]$)은 35입니다. 1번 라인에서 출하하는 데 드는 비용은 위의 그림을 보니 3입니다. 둘을 더한 38이 총 생산비용이 됩니다. 마찬가지로 2번 라인에 대해 총 생산비용을 구하면 37+2로 39가 됩니다.

따라서 총 생산비용을 최소화하는 제품 생산 경로는 마지막 여섯번째 공정 때 1번 라인에 있어야 합니다. 위 단계별 최적 경로에서 $l_j[1]$ 행을 선택해야 한다는 얘기죠. 말로 풀어쓰면 다음과 같습니다.

  • 총 생산비용을 최소화하려면, 제품은 다섯번째 공정에서 2번 라인에 있어야 한다. (∵ $l_6[1]=2$)
  • 제품은 네번째 공정에서 1번 라인에 있어야 한다.
  • 제품은 세번째 공정에서 1번 라인에 있어야 한다.
  • 제품은 두번째 공정에서 2번 라인에 있어야 한다.
  • 제품은 첫번째 공정에서 1번 라인에 있어야 한다.

이를 그림으로 나타내면 다음과 같습니다. 처음에 소개한 그림과 동일합니다.

Viterbi Algorithm

비터비 알고리즘을 애니메이션으로 만든 그림은 다음과 같습니다(출처). 현재 스테이트로 전이할 확률이 가장 큰 직전 스테이트를 모든 시점, 모든 스테이트에 대해 구합니다.

모든 시점, 모든 스테이트에 대해 구한 결과는 다음과 같습니다. (원래는 그물망처럼 촘촘하게 되어 있으나 경로가 끊어지지 않고 처음부터 끝까지 연결되어 있는 경로가 유효할 것이므로 그래프를 그린 사람이 이해를 돕기 위해 이들만 남겨 놓은 것 같습니다)

위 패스에서 만약 최대 확률을 내는 $k+2$번째 시점의 상태가 $θ_0$라면 backtrace 방식으로 구한 최적 상태열은 다음과 같습니다.

  • $[θ_0, θ_2, θ_2, θ_1, θ_0, θ_1]$

Comment  Read more

Disjoint Set

|

이번 글에서는 디스조인트 셋(Disjoint Set)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의와 위키피디아, 그리고 이곳을 참고해 정리하였음을 먼저 밝힙니다. 예시 그림과 파이썬 코드는 이곳을 참고하였습니다. 그럼 시작하겠습니다.

concept

디스조인트 셋이란 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조입니다. 디스조인트 셋은 전체 집합이 있을 때 구성 원소들이 겹치지 않도록 분할(partition)하는 데 자주 쓰입니다. 이와 관련해 몇 가지 용어를 살펴보겠습니다.

  • 셋(set)은 개체들의 집합입니다. (리스트 등과 달리 순서는 고려하지 않음)
  • 셋 $A$의 모든 원소가 셋 $B$에 포함될 때 $A$를 $B$의 부분집합(subset)이라 합니다. 이 때 $B$는 $A$의 초월집합(superset)이라 합니다.
  • 셋 $A$와 셋 $B$가 공유하는 원소가 하나도 없을 때 $A$와 $B$를 mutually disjoint하다고 합니다.
  • 임의의 셋을 분할(partition)한다는 건 각 부분집합이 다음 두 가지 속성을 만족하는 디스조인트 셋이 되도록 셋을 쪼개는 걸 뜻한다. (1) 파티션된 부분집합을 합치면 원래의 셋이 된다. (2) 파티션된 부분집합끼리는 mutually disjoint, 즉 겹치는 원소가 없다.

예컨대 $S={1,2,3,4}$이고, $A={1,2}$, $B={3,4}$, $C={2,3,4}$, $D={4}$라면 $A$와 $B$는 $S$의 분할입니다. 이 때 $A$와 $B$가 디스조인트 셋입니다. 하지만 $A$와 $C$는 $S$의 분할이 아닙니다. 겹치는 원소가 있기 때문입니다. $A$와 $D$ 또한 $S$의 분할이 아닙니다. 둘을 합쳐도 $S$가 되지 않기 때문입니다.

operations

디스조인트 셋은 세 가지 연산이 있는데요. make-set은 초기화 연산이므로 unionfind가 핵심이라고 할 수 있겠습니다.

  • make-set(x) : $x$를 유일한 원소로 하는 새로운 셋을 만듭니다.
  • union(x, y) : $x$가 속한 셋과 $y$가 속한 셋을 합칩니다.
  • find(x) : $x$가 속한 셋의 대표값(루트노드 값)을 반환합니다.

예를 들어 보겠습니다. $A={3,4}$인 디스조인트 셋이 이미 만들어져 있다고 칩시다. 이 경우 첫번째 들어간 원소인 3이 루트노드가 되며 3이 $A$를 대표하는 값이 됩니다. 다음과 같습니다.

find(4)는 4가 속한 셋의 대표값을 출력하라는 뜻입니다. 따라서 이 예에서는 3이 됩니다. 마찬가지로 find(3) 또한 출력 결과가 3입니다.

이번엔 다른 디스조인트 셋 $B={1,2}$가 있다고 치겠습니다. $B$의 대표값은 루트노드인 3입니다. $A$와 $B$를 합칠 때는 루트노드들끼리 이어줍니다. 다음과 같습니다.

새롭게 만든 디스조인트 셋의 루트노드는 1입니다. 따라서 예컨대 4가 속한 셋의 대표값을 출력하라는 $find(4)$를 수행하면 출력 결과가 1이 됩니다.

array로 구현

디스조인트 셋의 세 가지 기본연산을 배열(array)로 구현해보겠습니다. $A={3,4}$, $B={1,2}$ 이렇게 두 개 디스조인트 셋이 이미 만들어져 있다고 칩시다.

이를 배열로 구현하면 다음과 같습니다. $N$은 입력원소들을 가리킵니다. $S$는 입력원소가 루트노드인지 아닌지, 부모노드가 어떤 위치에 있는지 나타냅니다. 예컨대 31은 루트노드이기 때문에 이들에 해당하는 $S$의 값이 0입니다. 4의 부모노드는 $N$의 첫번째 요소, 즉 3이라고 표시가 되어 있네요. 마찬가지로 2의 부모노드는 $N$의 세번째 요소, 즉 1입니다.

  • $N=[3,4,1,2]$
  • $S=[0, 1, 0, 3]$

union 연산을 하면 $S$가 다음과 같이 바뀝니다.

  • $S=[0, 1, 1, 3]$

그렇다면 union(x,y) 연산의 계산 복잡성은 얼마나 될까요? 크게 세 가지 단계로 나눠 생각해볼 수 있습니다.

  • $x$가 속한 디스조인트 셋을 찾아야 합니다 : find(x)
  • $y$가 속한 셋을 찾아야 합니다 : find(y)
  • 찾은 셋을 합칩니다.

그런데 생각해보면 find 연산의 계산복잡성은 디스조인트 셋의 원소 수가 $n$개일 때 $O(\log{n})$입니다. 부모노드를 반복적으로 역추적해 루트노드를 찾습니다. 예컨대 잎새노드에서 루트에 이르기까지 일렬로 3-4-5-2-1 이렇게 구성돼 있는 디스조인트 셋이 있다고 할 때 find(3)은 엣지를 트리의 높이만큼 네 번 거슬러 올라가야 루트인 1을 찾을 수가 있습니다. find 연산을 좀 더 효율적으로 수행하기 위한 방법이 바로 path compression인데 조금 있다가 다루겠습니다.

find 연산을 두 번 수행해 합칠 셋을 찾았다고 칩시다. 그러면 이제 이 두 셋을 합칠 차례입니다. 합치는 방법에는 union-by-sizeunion-by-height가 있는데 바로 다음에서 다루겠습니다.

union

임의의 두 디스조인트 셋을 합칠 때는 원소수가 적은 셋을 많은 셋의 서브트리로 합치는 것이 효율적입니다(union-by-size). 마찬가지로 트리의 높이가 작은 셋을 큰 셋의 서브트리로 합쳐야 합니다(union-by-height). 다음 union 연산 때 반드시 find 연산을 수행해야 하는데 find 연산의 효율성을 높여주기 위해서입니다. 원소수와 트리의 높이는 비례하는 경향이 있고 find 연산의 계산복잡성은 이들에 매우 의존적입니다.

union-by-sizeunion-by-height를 구현하는 것은 간단합니다. 배열 $S$의 루트노드 정보를 바꾸면 됩니다. 루트노드일 때 0을 넣었던 기존과 달리 다음과 같이 바꿉니다.

  • union-by-size : $-$size of tree
  • union-by-height : $-$height of tree

요컨대 find 연산에서 찾은 두 개 디스조인트 셋의 원소수 혹은 높이를 비교해서 더 큰 쪽으로 합쳐줍니다. 이렇게 하면 이후 find 연산을 조금 더 효율적으로 수행할 수 있습니다.

union-by-sizeunion-by-height의 계산복잡성은 $O(1)$입니다. find 연산에서 이미 두 디스조인트 셋의 루트노드를 찾았기 때문에 $S$에서 이 두 루트노드 위치에 저장돼 있는 원소수 혹은 높이를 비교합니다. 둘 중 작은 쪽의 루트노드에 해당하는 $S$의 값을 큰 쪽 루트노드의 인덱스를 가리키도록 바꿉니다. 이 모든 연산이 $O(1)$에 해당합니다.

path compression

path compression은 다음과 같이 모든 노드가 루트를 가리키도록 만드는 것입니다. $S$에 부모노드 인덱스 대신 루트노드를 저장하는 방식입니다. find 연산을 수행할 때 트리의 높이만큼 거슬러 올라가야 루트노드를 찾을 수 있는데, 이러한 비효율성을 완화해보자는 취지입니다. path compression을 한번 수행해 놓으면 루트노드를 찾는 find 연산의 계산복잡성을 확 낮출 수 있습니다.

Comment  Read more

한국어 주절의 문법상

|

이번 글에서는 한국어 주절의 문법상(grammatical aspect)을 가장 잘 드러내면서 널리 쓰이고 있는 보조용언 구성인 -어 있--고 있-에 대해 살펴보도록 하겠습니다. 이번 글은 고려대 정연주 선생님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

-어 있-

-어 있-은 크게 결과상(resultative)정태상(stative)을 나타냅니다. 차례대로 살펴 보겠습니다.

결과상

결과상이란 과거 사태의 결과가 지속되는 걸 가리킵니다. 동사가 나타내는 사태가 종결된 뒤 그 결과 상태가 주어에게 성립됨을 나타냅니다. 예문을 보겠습니다.

꽃이 피어 있다.

위 예문의 동사 피다가 나타내는 사태(開花)가 끝난 뒤, 그 결과 상태가 주어 에게 성립되고 있음을 알 수 있습니다. 다시 말해 꽃이 과거 어느 시점에 피었는데, 핀 상태가 현재도 계속되고 있다는 의미로 -어 있-이 쓰였다는 얘기입니다.

하지만 -어 있-이 아무 동사에나 결합하는 것은 아니고 결합 제약이 있습니다. -어 있-은 ‘놓이다’, ‘깔리다’, ‘숨다’, ‘앉다’, ‘눕다’와 같이 시간적 끝점을 갖는 자동사(목적어를 취하지 않는 동사)와 결합합니다. 예문을 보겠습니다.

(1) 진이가 *뛰어 있다.

(2) 진이가 예쁜 옷을 *입어 있다.

(1)의 뛰다는 에너지만 공급되면 계속 뛸 수 있다는 점에서 끝점이 없는 동사입니다. (2)의 입다는 끝이 있는 동사이지만 목적어를 갖는 타동사입니다. (1), (2) 모두 비문입니다. 다시 말해 서술어가 끝점이 없거나, 타동사라면 -어 있-이 결합할 수 없습니다.

물론 -어 있-과 결합할 수 있는 타동사가 일부 있기는 합니다. 이를 이해하기 위해선 우선 자동사와 타동사 개념을 살짝 살펴봐야 할 것 같습니다. 예문을 보겠습니다.

아이가 잔다.

자동사 자다가 가리키는 행위로 영향을 받는 대상은 주어 아이입니다. (1)과 (2) 예문에서도 서술어 동사가 가리키는 행위로 영향을 받는 대상은 주어 진이입니다.

반면 타동사는 해당 동사가 가리키는 행위로 영향을 받는 대상이 목적어입니다. 다음 예문과 같습니다.

철수가 친구를 때렸다.

자, 이제 원래 목적으로 돌아와서 -어 있-과 결합할 수 있는 타동사를 살펴보겠습니다. 다음 예문과 같습니다.

진이가 등대를 향해 있다.

위 예문의 타동사 향하다가 가리키는 행위로 영향을 받는 대상은 무엇일까요? 대충 봐서는 목적어인 등대일 것 같지만 사실 주어인 진이가 영향을 받는 의미로 전달됩니다.

요컨대 -어 있-과 결합할 수 있는 타동사는 타동사이면서도 목적어가 변화를 겪는 것이 아니라 주어가 변화를 겪는 의미로 사용되는 단어들입니다. 이러한 예로는 ‘향하다’, ‘떠나다’, ‘넘어서다’, ‘건너오다’, ‘초과하다’ 등이 있습니다.

정태상

과거 사건의 발생 여부에 대해서는 아무런 함축도 갖지 않고 단지 현재 상태만 나타내는 상 범주를 정태상이라고 합니다. 다음 예문과 같습니다.

우리 마을은 산으로 둘러싸여 있다.

이 길은 바닷가까지 뻗어 있다.

정태상은 의미적으로 결과상에서 파생된 용법이라고 합니다.

-고 있-

-고 있-은 크게 결과상(resultative), 정태상(stative), 연속상(continuous), 반복상(iterative)을 나타냅니다. 차례대로 살펴 보겠습니다.

결과상

-고 있-이 결과상의 의미로 쓰인 예문은 다음과 같습니다.

철수는 흰 셔츠를 입고 있다.

위 예문의 -고 있-은 철수가 흰 셔츠를 착용하는 동작을 완결한 뒤 그 결과 상태(옷을 입은 상태)가 지속되고 있음을 나타내고 있습니다. 결과 상태가 타동사의 주어에게 성립되고 있습니다. 다시 말해 입다라는 행위로 당장 영향을 받는 대상은 흰 셔츠이지만, 결과적으로 옷을 입은 행위(服着)의 결과로 주어인 철수가 옷을 입은 상태로 변화했다는 이야기입니다.

이처럼 타동사가 가리키는 행위로 영향을 받는 대상이 1차적으로는 목적어이지만, 결과적으로 주어에 영향을 미친다는 의미를 갖는 타동사를 재귀성 타동사라고 합니다. -어 있-은 재귀성 타동사와 결합할 때 결과상(결과 상태의 지속)의 의미를 갖습니다. 이러한 동사의 예로는 ‘(신발을)신다’, ‘(명찰을)달다’, ‘(이불을)덮다’, ‘(고개를)숙이다’ 등이 있습니다.

그러나 다음과 같은 경우도 있어 분석에 주의를 기울여야 합니다.

(가) 철수가 이불을 덮고 있다.

(나) 철수가 지붕에 짚을 덮고 있다.

(가)의 덮다는 결과적으로 주어인 철수를 변화시키기 때문에 재귀성을 가졌지만, (나)는 그렇지 않습니다. 재귀성 타동사가 쓰인 (가)의 -고 있-은 결과상, 그렇지 않은 (나)의 -고 있-은 연속상(진행상)의 의미로 쓰인 것을 확인할 수 있습니다.

이번엔 다른 사례를 보겠습니다.

관중들이 경기장을 가득 메우고 있다.

위 예문의 결과 상태가 타동사의 목적어에 성립된 경우여서 재귀성이 없습니다. 다만 경기장을 가득 메우는 데 주어 관중들의 적극적인 개입이 있어서 ` -어 있-`이 결과상의 의미를 갖습니다.

정태상

-고 있-의 정태상 관련 예문은 다음과 같습니다.

이 도시를 여러 산들이 병풍처럼 둘러싸고 있다.

연속상(진행상)

연속상이란 사태가 지속되고 있는 걸 가리킵니다. 예문을 보겠습니다.

철수는 흰 셔츠를 입고 있다.

위 예문은 결과상으로도, 연속상으로도 해석할 수 있는 중의적인 구문입니다. 연속상으로 해석할 경우 철수가 현재 흰 셔츠를 착용하는 동작을 수행하고 있음을 나타냅니다.

한국어의 연속상은 영어의 be+현재분사와 유사하지만 다른 점도 있습니다. 가장 다른 점은 -고 있-이 정적인 사태를 나타내는 동사와도 매우 자유롭게 결합할 수 있다는 점입니다. 다음 예문과 같습니다.

  • 알고 있다, 모르고 있다, 믿고 있다, 생각하고 있다, 사랑하고 있다…

이와 별개로 -ㄴ 중-은 정적인 사태를 나타내는 동사와 잘 결합하지 않습니다.

  • *아는 중이다, *모르는 중이다, *믿는 중이다, *생각 중이다, *사랑 중이다…

하지만 다음과 같은 예문이 자주 쓰이는데, 아래의 생각하다는 동적 사태(적극적으로 고민하고 있음)에 가까운 사태를 동사이기 때문인 것 같습니다.

나는 생각하는 중이야.

반복상

반복상이란 그 사태가 반복해서 발생함을 나타내는 상 범주입니다. 다음 예문과 같습니다.

최근 이와 비슷한 사건이 자주 발생하고 있다.

-어 있-, -고 있- 모두 결합할 수 있는 동사

-어 있--고 있-은 각각 특정 종류의 동사와만 결합하는 제약이 있으나 둘 모두 쓰이는 동사도 있습니다. 성장하다가 대표적인 사례입니다.

  • 성장해 있다(결과상) : 성장이라는 상태 변화가 어떤 완결점에 이미 도달해서 그 결과 상태가 지속됨을 나타냅니다.
  • 성장하고 있다(연속상) : 성장이라는 상태 변화가 아직 완결되지 않고 진행 중임을 나타냅니다.

동사가 다의어여서 둘 모두 결합하는 경우도 있습니다. 살다가 대표적인 사례입니다.

  • 살아 있다(결과상) : 살다alive 정도의 의미를 가질 때에는 시작점(태어난 순간), 끝점(죽는 순간)을 가지는 유계동사(telic verb)로서 생명력이 있는 상태가 지속됨을 나타냅니다.
  • 살고 있다(연속상) : 살다가 거주하다의 의미일 때는 무계동사(atelic verb)로서 해당 지역에 거주하는 중이다 정도의 의미를 나타냅니다.

Comment  Read more

Conditional Random Fields

|

이번 글에서는 Conditional Random Fields에 대해 살펴보도록 하겠습니다. 이 글은 고려대 정순영 교수님 강의를 정리했음을 먼저 밝힙니다. 이밖에 다양한 자료를 참고하였는데요, 인용한 부분에 표시를 해 두었습니다. 비터비 알고리즘 관련 설명 그림은 제가 직접 그렸습니다. 제가 잘못 이해하고 있거나 미진한 점 있으시면 언제든 댓글로 알려주시면 바로 반영하겠습니다. 그럼 시작하겠습니다.

overview

CRF를 설명하는 데 있어 가장 유명한 그림 아닐까 싶습니다. 다음과 같습니다.

CRF, MEMM, HMM과의 차이점은 다음과 같습니다. 간결하고 직관적인 설명이어서 직접 인용을 해봤습니다. (출처 : Quora)

CRFs and MEMMS are discriminative sequence models whereas HMMs are generative sequence models. HMM essentially uses Bayes Rule as a local model over the transition and emission probabilities, whereas CRF and MEMM’s local models are MaxEnt models over transition and observable features. The chief difference between MEMM and CRF is that MEMM is locally renormalized and suffers from the label bias problem, while CRFs are globally renormalized.

CRF가 강점을 지니는 이유는 구성하기에 따라서 얼마든지 HMM 같은 구조로 바꿀 수 있다는 점입니다. 아래 그림과 같습니다. (출처 : C Sutton, “An Introduction to CRF”)

For example, in an HMM, a transition from state $i$ to state $j$ receives the same score, log $p(y_t = j$|$y_{t−1} = i)$, regardless of the input. In a CRF, we can allow the score of the transition $(i, j)$ to depend on the current observation vector, simply by adding a feature $1{y_t=j}$, $1{y_{t−1}=1}$, $1_{x_t=o}$.

CRF는 본질적으로 시퀀스 분류기이기 때문에 최근 주목받고 있는 Recurrent Neural Network와도 직, 간접적으로 연관을 맺고 있는 것 같습니다. 이와 관련한 설명 또한 인용해봤습니다. (출처 : Quora)

RNNs have a latent state that is never observed (e.g. the memory in a LSTM). In contrast, the CRF has a latent state that is observed for training data (the model has to learn how to recreate those latent states for test data). Both are similar in that there is a set of parameters that tell you how to evolve the latent state from one time step to the next.

수식과 파이썬 구현

CRF의 수식을 살펴보겠습니다. 수식만 살펴봐서는 되레 복잡하므로, 파이썬 코드와 함께 살펴보겠습니다. 파이썬 코드는 이곳을 참고해 대폭 손질하였습니다. (수식 이해를 돕기 위한 코드로 대단히 느립니다, 혹시 학습 용도로 필요하시다면 라이브러리 활용을 추천해 드립니다)

기본 구조

CRF를 그래피컬하게 나타낸 그림은 다음과 같습니다. 입력벡터 $x$의 위치에 상관없이 모두 활용하기 때문에 매우 유연한 구조입니다.

입력 시퀀스(예컨대 단어들) 벡터 $x$가 주어졌을 때 레이블 시퀀스(예컨대 품사) 벡터 $y$가 나타날 확률은 다음과 같이 정의됩니다. 최대엔트로피모델(로지스틱 회귀)와 완전히 같습니다만, 최대엔트로피가 single observation을 분류하는 모델이라면, CRF는 sequential classifer라는 점이 다릅니다. 위 식을 파이썬 코드로 구현하면 다음과 같습니다.

import math
def calc_prob_y_given_x(y_prime, x, all_labels, FeatureFunction, weights):
    n = len(y_prime)
    m = len(weights)
    nominator = 0
    for j in range(1, n):
        for i in range(1, m):
            nominator += weights[i] * FeatureFunction(y_prime, x, i, j)
    denominator = calc_Z(x, n, m, all_labels, FeatureFunction, weights)
    return math.exp(nominator) / denominator

Feature Functions

CRF는 최대엔트로피모델이나 최대엔트로피마코프모델처럼 Feature를 연구자가 유연하게 설정할 수 있습니다. 이를 파이썬 코드로 구현한 결과는 다음과 같습니다.

# x : words (observation sequence)
# y : lables (e.g: POS TAGS, label sequence)
def FeatureFunction(x, y, i, j):
    # f_1
    if i == 1 and y[j-1] == 'NN':
        return 1
    # f_2
    elif i == 2 and y[j-1] == 'VBZ':
        return 1
    # f_3
    elif i == 3 and x[0] == 'DT':
        return 1
    else:
        return 0

Label Bias 문제와 극복 방안

CRF는 Label Bias 문제를 극복하기 위해 제안된 기법입니다. Label Bias란 다음과 같은 문제를 가리킵니다.

  • Preference of states with lower number transitions over others

이를 해결하기 위해 확률값을 구할 때 global normalize를 합니다. 이를 구현한 파이썬 코드는 다음과 같습니다.

def calc_Z(x, n, m, all_labels, FeatureFunction, weights):
    Z = 0
    all_possible_Y = itertools.product(all_labels, repeat=n)
    for y_prime in all_possible_Y:
        tmpZ = 0
        for j in range(1, n):
            for i in range(1, m):
                tmpZ += weights[i] * FeatureFunction(y_prime, x, i, j)
        Z += math.exp(tmpZ)
    return Z

그런데 보시다시피 가능한 모든 조합의 레이블 시퀀스에 대한 확률을 구해야 합니다. 가령 품사 종류가 명사(NN), 동사(VB) 등 다섯 가지이고, 시퀀스 길이가 5(개 단어)라면 다음 표처럼 $5^5$=3125가지의 경우의 수를 고려해야 합니다.

$y_1$ $y_2$ $y_3$ $y_4$ $y_5$
NN NN NN NN NN
NN NN NN NN VBN
NN NN NN NN VBZ
NN NN NN NN IN
NN NN NN NN DT
NN NN NN VBN NN
NN NN NN VBN VBN
NN NN NN VBN VBZ
NN NN NN VBN IN
NN NN NN VBN DT

CRF에서 가장 계산량이 많은 부분이 바로 $Z$를 구하는 부분입니다. 위 파이썬 코드는 수식 이해 용도로 수식을 그대로 옮겨놓은 형태이지만, 실제로는 다이내믹 프로그래밍(dynamic programming) 등 최적화 기법을 쓴다고 합니다.

파라메터 학습 : 최대우도추정

CRF의 파라메터는 로지스틱 회귀의 파라메터를 추정하는 방식과 같이 최대우도추정법(Maximum Likelihood Estimation)으로 구합니다. 식이 매우 복잡한데, 저 또한 정리 용도로 남겨둡니다. CRF의 로그 우도함수는 다음과 같습니다. 식의 첫 줄 두번째 항은 과적합(overfitting) 방지를 위한 정규화(regularization) 항입니다.

위 로그 우도함수는 파라메터 $λ$로 편미분한 값이 0인 지점에서 최대값을 가집니다. 이를 3등분해서 각각 $λ$에 대해 편미분한 결과는 다음과 같습니다. 우선 $A$를 편미분한 결과입니다.

다음은 $B$를 파라메터 $λ$에 대해 편미분한 결과입니다.

마지막으로 $C$입니다.

$A$는 데이터의 empirical distribution으로 해석할 수 있습니다. 식과 파이썬 코드는 다음과 같습니다.

def calc_empirical_expectation_feature_i(train_data, FeatureFunction, i):
    empirical_expectation_feature_i = 0
    for x, y in train_data:
        n = len(y)
        for j in range(1, n):
            empirical_expectation_feature_i += FeatureFunction(y, x, i, j)
    return empirical_expectation_feature_i

$B$는 모델이 내놓는 distribution으로 해석할 수 있습니다. 식과 파이썬 코드는 다음과 같습니다.

import itertools
def calc_predicted_expectation_feature_i(train_data, FeatureFunction, 
									  all_labels, weights, i):
    predicted_expectation = 0
    for x, y in train_data:
        n = len(y)
        all_possible_Y = itertools.product(all_labels, repeat=n)
        for y_prime in all_possible_Y:
            predicted_expectation += \
                (calc_prob_y_given_x(y_prime, x, all_labels, FeatureFunction, weights)
                 * sum([FeatureFunction(x, y, i, j) for j in range(1, n)]))
            print(predicted_expectation)
    return predicted_expectation

로그우도 함수에 대한 편미분 식을 다시 적으면 다음과 같은데요. $A$와 $B$가 비슷할 수록 로그우도 함수의 도함수가 작아집니다. 데이터의 분포와 모델의 분포가 비슷할 수록, 즉 모델이 데이터의 분포를 잘 모사할 수록 학습이 잘 되었다는 이야기입니다.

이제 거의 다 왔습니다. 파라메터 $λ$를 랜덤 초기화한 뒤 이제까지 구한 로그우도 함수가 커지는 방향(그래디언트)로 파라메터를 조금씩 업데이트해 주면 됩니다(gradient ascent). 이를 파이썬 코드로 구현한 결과는 다음과 같습니다.

#train data set = {(x, y)}
def get_all_labels(train_data):
    available_labels = set()
    for x, y in train_data:
        available_labels.update(y)
    return list(available_labels)

# m = feature vector size
import random
def initial_weights(m):
    return [random.random() for _ in range(m)]
   
def train(train_data, FeatureFunctions, m, iterations=100, learning_rate=0.1):
    all_labels = get_all_labels(train_data)
    weights = initial_weights(m)
    for _ in range(iterations):
        for i in range(1, m):
            empirical_expectation = \
                calc_empirical_expectation_feature_i(train_data, FeatureFunction, i)
            predicted_expectation = \
                calc_predicted_expectation_feature_i(train_data, FeatureFunction,
                                                     all_labels, weights)
            weights[i] = weights[i] + \
            			learning_rate * (empirical_expectation - predicted_expectation)

비터비 알고리즘

시퀀스 분류를 하기 위해 이 먼길을 돌아왔습니다. CRF가 최적 상태열을 inference하는 기법인 비터비 알고리즘은 다음과 같이 동작합니다.

다음 과정입니다.

다음 과정입니다.

마지막으로 backtrace 과정입니다.

Comment  Read more

한국어 관형사절의 시간 표현

|

이번 글에서는 한국어 관형사절의 시간 표현에 대해 살펴보도록 하겠습니다. 이 글은 고려대 정연주 선생님 강의를 정리하였음을 먼저 밝힙니다. 참고로 말씀드리면 한국어 관형사절의 시간 표현을 이해하려면 시제 개념을 모두 알고 있어야 한다고 합니다(링크 참고). 그럼 시작하겠습니다.

관형사절?

관형사란 명사류(체언) 앞에서 그 명사류의 뜻을 분명하게 제한하는 품사입니다. 주어와 서술어가 함께 나타난 구성을 이라고 합니다. 관형사절이란 관형사가 들어갈 자리에서 관형사 역할을 하는 절을 가리킵니다. 다음 예문과 같습니다.

  • 관형사 :
  • 관형사절 : 철수가 본

관형사절을 만드는 어미를 관형사형 전성어미라고 합니다. 대표적으로 -ㄴ-ㄹ이 있습니다. -ㄴ은 현실화된 일을 나타내는 절에 결합하고, -ㄹ은 현실화되지 않고 아직 사고의 영역에 있는 일을 나타내는 절에 결합하는 경향이 있습니다. 예문을 보겠습니다.

  1. [쥐를 잡] 고양이가 낮잠을 잔다.
  2. [쥐를 잡] 고양이가 낮잠을 잔다.

(1)의 고양이는 이미 쥐를 잡았고, (2)의 고양이는 아직 잡지 않았다는 점에서 의미상 차이가 있습니다.

한국어 관형사절의 시간 표현

한국어 주절(모절)의 시제 체계는 다음과 같이 정리할 수 있습니다. 요컨대 한국어 주절의 시제는 -었-(과거), -는-(현재), -겠-(미래)의 3분 체계입니다.

한국어 관형사절의 시간 표현은 다음과 같습니다.

첫번째 표와 두번째 표를 비교해서 보면 주절의 시간 표현과 관형사절의 시간 표현이 이루는 체계가 사뭇 다른 점을 확인할 수 있습니다. 관형사형 전성어미 -ㄴ-ㄹ를 제거하면, 관형사형 시간 표현은 -더-(과거), -느-(현재), -∅-(미래)의 3분 체계인데요. 각각이 어떤 문법적 의미를 지니는지 확실하지 않습니다. 동사와 형용사의 아주 다른 체계를 이루고 있는 점도 주목할 점입니다.

이러한 세 가지 의문점을 중심으로 설명해 보겠습니다.

중세 한국어의 시간 표현

국어학자들의 연구에 따르면 중세 한국어의 시간 표현 체계는 주절이든 관형사절이든 상관없이 다음과 같았다고 합니다. 완망, 비완망 개념과 관련해서는 이곳을 참고하시면 좋을 것 같습니다.

그런데 17세기쯤 과거 표시 형태소 -었-(='-어 있-')이 등장하면서 기존의 -∅--더-와 경쟁 구도를 이루다가, 현대에 와서는 -었-이 완승에 가깝게 널리 쓰이고 있습니다. -∅-는 이 경쟁에 져서 사라지고, -더-는 새로운 의미를 가지게 되면서 겨우 살아남았습니다.

그런데 신기한 것은 -었-은 유독 관형사절에 침투하지 못했다는 점입니다. 그래서 현대 한국어의 관형사절에서만큼은 중세 한국어의 시간 표현 체계가 화석처럼 남았습니다. 다음 예문을 보겠습니다.

내가 먹

위 관형사절을 일반적인 문장으로 바꾸면 아래와 같이 비문이 됩니다. -더-라는 형태소가 과거 표시 기능을 하는 게 아니라 다른 새로운 의미를 가지게 됐다는 것이죠.

*내가 밥을 먹라.

관형사절은 한국어 시간 표현 체계 전체의 변화에서 제외된 원인과 관련해 다양한 의견이 제시되고 있지만 다음과 같은 설명도 가능할 것 같습니다.

  • 새로운 문법소(예컨대 -었-)는 주로 정보 전달의 초점에서 발달한다.
  • 관형사절은 정보 전달의 초점이 아니라 이미 전제된 내용이 언급되는 부분이다.
  • 따라서 관형사절에서는 기존의 오래된 문법소가 계속해서 쓰이는 경향이 있다.

동사 관형사절의 시간표현

-더-, -느-, -∅--ㄴ, -ㄹ의 조합으로 관형사절 시간표현 관련 어미들의 의미를 곱씹어볼 수 있습니다. 우선 현재에 대응하는 -는-부터 살펴보겠습니다.

-는은 ‘현재’와 ‘현실’의 조합으로 생각해볼 수 있겠습니다. 즉 현재 일어나고 있는 일을 나타냅니다. 다음 예문과 같습니다.

내가 먹

이번엔 과거에 대응하는 -은, -던, -었던을 살펴보겠습니다.

-은은 ‘과거 완망’과 ‘현실’의 조합으로 생각해볼 수 있습니다. 과거의 일인데 사태의 시작과 끝이 시야에 들어와 있음을 나타냅니다. 쉽게 말해 ‘끝난 과거’를 가리킵니다. 다음 예문과 같습니다.

내가 먹 밥 (밥을 다 먹었음)

꽃이 들판 (꽃이 핀 상태가 지속됨)

-던은 ‘과거 비완망’과 ‘현실’의 조합으로 생각해볼 수 있습니다. 과거의 일인데 화자가 사태의 내부를 들여다 보고 있음을 나타냅니다. 쉽게 말해 ‘끝나지 않은(혹은 끝났는지 모르는) 과거의 일’을 가리킵니다. 다음 예문과 같습니다.

내가 먹 밥 (밥을 먹었긴 했으나 다 먹었는지는 나타나지 않음)

-었던은 과거의 일이지만 현재와의 접점이 없는 걸 나타냅니다. 쉽게 말해 ‘단절된 과거’를 가리킵니다. 이는 주절의 시제 표현에서 -었었-과 비슷합니다.

꽃이 피었던 들판 (과거에 꽃이 피었으나 지금은 꽃이 피지 않음)

마지막으로 미래에 대응하는 -을을 살펴보겠습니다.

-을은 아직 현실화되지 않은 일을 나타냅니다. 다음 예문과 같습니다.

내가 먹 밥 (아직 밥을 먹지 않았으나 앞으로 먹을 예정)

형용사 관형사절의 시간 표현

형용사 관형사절은 중세 국어의 시간 표현 체계를 그대로 따르고 있습니다. 차례대로 살펴보겠습니다. 우선 -은은 형용사 관형사절에서 현재 성립하는 상태를 표현할 때 씁니다. 다음 표, 예문과 같습니다.

지지율이 높 정치인

-은은 과거 완망의 -∅-과 현실의 -ㄴ의 조합으로도 생각해 볼 수 있습니다. 그런데 ‘과거 완망’과 ‘현실’이 합쳐진 -은현재를 나타낸다는 게, 지금까지의 설명에 비추어봤을 때 다소 생소하긴 합니다. 이와 관련해서는 이런 견해가 있습니다.

형용사에는 시간과 끝이라는 개념이 없고 시간을 초월해서 펼쳐진 개념이다. 따라서 사태의 시작과 끝을 전제로 한 완망/비완망 개념과 애초에 양립이 불가능하다. 형용사의 과거를 나타낼 때 -더-를 늘 쓰다보니, -더-를 안쓰면 현재로 해석되게 되었다. 그래서 -∅-의 의미가 동사에서는 과거 완망, 형용사에서는 현재로 그 의미가 달라지게 된 것이다.

혛용사 관형사절에서 과거의 상태를 표현할 때는 -던 또는 -었던을 씁니다. 둘 모두 과거 비완망의 -더-와 현실의 -ㄴ의 조합입니다.

다만 형용사 관형사절의 과거를 나타내는 -더-는 완망, 비완망 개념은 없고 순전히 과거의 의미만 나타냅니다. 아울러 형용사 관형사절의 -었던-던과 큰 의미 차이가 없습니다. 다음 예문과 같습니다.

지지율이 높 정치인

지지율이 높았던 정치인

마지막으로 형용사 관형사절의 미래의 상태, 즉 현실화되지 않은 상태를 나타낼 때는 -을을 씁니다. 다음 표, 예문과 같습니다.

지지율이 높 정치인

Comment  Read more