Part-of-Speech Tagging Markov Model Tagger를 중심으로 부산대학교 컴퓨터공학과 한국어정보처리 연구실 정성원

일반적인 태깅 품사 태깅 기법 일반적 통계 기반 품사 태깅 목 차 한국어 품사 태깅 어절 확률 추정에 기반한 한국어 태깅 모델 한국어의 형태 ◦ 통사적 특징 통계 기반 한국어 품사 태깅 형태소 n-gram 모델 보완 어절 확률 추정에 기반한 한국어 태깅 모델 어절 확률 추정 어절 확률 추정에 기반한 HMM 모델 성능 평가 먼저, 품사 태깅에 관한 연구의 전반적인 사항과 관련연구를 알아보겠습니다.

Part-of-speech tagging (품사 태깅) Part-of-speech tagging, PoS tagging: Assigning a part-of-speech category to each word-token in a text.

품사(범주) 분류 (Tagset) 일반적 품사 분류의 목적 품사 분류 기준 품사 태그 집합 크기의 변이 요소 문장구조를 효율적으로 기술하고 처리하기 위함 되도록이면 자세하게 분류하는 것이 좋음 Major English tagsets: Penn (45 tags); Brown (87 tags); Lancaster: CLAWS series of tagsets, C5, and C7 (for BNC, 146 tags). 품사 분류 기준 기능(function) : 각 단어(or 형태소)가 어느 문장 성분(주어, 서술어, 목적어, 수식어, 관계어 등) 자리에 놓일 수 있는지에 따른 분류 형태(form): 각 형태소의 어형 변화나 굴절 특성에 따른 분류 의미(meaning): 각 형태소의 의미에 따른 분류 품사 태그 집합 크기의 변이 요소 적용한 품사 분류 기준 문장부호 및 조사의 세분화 정도 품사분류의 일반적 목적에 부합하여 대부분의 연구들에서 기능 기준 분류를 일차적으로 고려함 4

품사(범주) 분류 (영어, Penn Treebank)

품사(범주) 분류 비교 (한국어) 기타 범주 : 22, 12, 19, 10

일반적 통계 기반 품사 태깅 1 통계적 품사 태깅 일반적인 통계 기반 모델에서 tag의 확률 일반적 통계 기반 품사 태깅 1 관련연구 통계적 품사 태깅 한 문장을 이루는 어절열 w1,n이 주어졌을 때, 가장 확률이 높은 태그열 t1,n을 구함 일반적인 통계 기반 모델에서 tag의 확률 이전의 history에 대한 조건부 확률로 구함 현실적으로는 전체 history에 대해 조건부확률을 구하는 것이 불가능 ∴ n-gram 모델을 도입하여 국부적인 문맥(local context)을 이용

Markov Assumptions Let X=(X1, .., Xt) be a sequence of random variables taking values in some finite set S={s1, …, sn}, the state space, the Markov properties are: Limited Horizon: P(Xt+1=sk|X1, .., Xt)=P(X t+1 = sk |Xt) i.e., a word’s tag only depends on the previous tag. Time Invariant: P(Xt+1=sk|X1, .., Xt)=P(X2 =sk|X1) i.e., the dependency does not change over time. If X possesses these properties, then X is said to be a Markov Chain Tagging에서의 Limited Horizon property

Markov Model Visible Markov Model Hidden Markov Model h a p e t i 1.0 0.4 0.3 0.6 start P(t,i,p) = P(t)P(i|t)P(p|i) = 1.0 x 0.3 x 0.6 = 0.18 {lemonade, ice tea} CP IP cola iced tea lemonade 0.3 0.5 0.7 0.6 0.1 0.2 0.7x0.3x0.7x0.1 + 0.7x0.3x0.3x0.1 + 0.3x0.3x0.5x0.7 + 0.3x0.3x0.5x0.7 = 0.084

품사 태깅에서의 HMM HMM이 성립될 요소 {S, V, A, B, π} S : 상태 (품사) π : 초기 상태 확률

일반적 통계 기반 품사 태깅 2 관련연구 n-gram 차수가 높을수록 통계 기반 모델의 정확도는 더 높지만 현실적으로 n이 큰 모델은 구축하기 힘듦 타입(가짓수)의 통계정보를 유지하기 위한 사전의 메모리가 많이 필요 n-gram 차수가 높을 수록 자료부족 문제 심각 20,000개의 연속된 어절 타입으로 이루어진 말뭉치에서 추출할 수 있는 이전 문맥을 고려한 bi-gram  19,999개 (vs. 이론적 4억 개의 조합) 말뭉치 내 타입 bi-gram tri-gram four-gram … 20,000 4x108 8x1012 1.6×1017

일반적 통계 기반 품사 태깅 3 태그 확률 우선 전개 마르코프 가정 적용 일반적 통계 기반 품사 태깅 3 관련연구 태그 확률 우선 전개 마르코프 가정 적용 현재 품사의 발생은 바로 이전의 품사에만 의존 (n=2, 품사 bi-gram) 현재 어절의 발생은 현재의 품사에만 의존 (n=1, 품사에 대한 어절 uni-gram) 태그 확률 우선 전개 HMM 품사 태깅 모델 ( n=2, bi-gram 모델 )[Charniak93]

일반적 통계 기반 품사 태깅 4 어절 확률 우선 전개 마르코프 가정 적용 일반적 통계 기반 품사 태깅 4 관련연구 어절 확률 우선 전개 마르코프 가정 적용 현재 어절의 발생은 바로 이전의 어절에만 의존 (n=2, 어절 bi-gram) 현재 품사의 발생은 현재의 어절에만 의존 (n=1, 어절에 대한 품사 uni-gram) 어절 확률 우선 전개 품사 태깅 모델 [Charniak93]

통계 정보 추출 ti-1 ti ti+1 wi-1 wi wi+1 P(NN|AT) = 48636/(48636+19) = 99.96

최적 후보 열 선택 방법- Best choice 후보들 중 선택 확률이 가장 높은 것을 선택 (전후 어절 사이에 존재하는 전이 확률을 사용하는 것도 가능) 음식을 해 가지고 갈 생각 명사+조사 자타동사+어미 타동사+어미 명사 1 0.5 0.6 명사+조사 수의존명사 명사+조사 명사 명사 1 0.2 0.3 0.5 0.1 0.6 0.4 명사 수의존명사+어미 타동사+어미 자타동사+어미 타동사+어미 보조용언+어미 보조용언+어미

The Viterbi Algorithm works as follows: Initialization: δj(1) = πj, 1≤ j≤ N Induction: δj (t+1) = max1≤ i≤N δi(t)aijbijo_t 1≤ j≤ N Store backtrace: ψj(t+1) = argmax1≤ i≤N δj(t)aij bijo_t 1≤ j≤ N Termination and path readout: XT+1 = argmax1≤ i≤N δj(T+1) Xt = ψXt+1(t+1) P(X) = max1≤ i≤N δj(T+1)

Viterbi algorithm 방법 앞 어절들과의 관계 중 가장 확률이 높은 것을 선택 Si+1a = argmax(Si-1 * Pi * Pi-1a) 계산이 끝난 후 back track하면서 선택 함 명사 타동사+어미 보조용언+어미 Pia Pi-1a Pi-1b Pi-1c Pib Pic Pi+1a Pia Si-1a Si+1a Pi+1a Si-1b Pib Si-1c Pic 음식을 명사+조사 해 수의존명사 명사 자타동사+어미 가지고 수의존명사+어미 타동사+어미 갈 보조용언+어미 생각 S 명사+조사 자타동사+어미 타동사+어미 명사 보조용언+어미 S S S S S S S S S S S S S

한국어 품사 태깅 한국어의 형태 ◦ 통사적 특징 통계 기반 한국어 품사 태깅 형태소 n-gram 모델 보완 목 차 일반적인 태깅 품사 태깅 기법 일반적 통계 기반 품사 태깅 한국어 품사 태깅 한국어의 형태 ◦ 통사적 특징 통계 기반 한국어 품사 태깅 형태소 n-gram 모델 보완 어절 확률 추정에 기반한 한국어 태깅 모델 어절 확률 추정 어절 확률 추정에 기반한 HMM 모델 성능 평가 먼저, 품사 태깅에 관한 연구의 전반적인 사항과 관련연구를 알아보겠습니다. 18 18

통계 기반 한국어 품사 태깅 관련 연구 한국어 품사 태깅 어절 n-gram 기반 HMM 모델을 그대로 응용 관련연구 통계 기반 한국어 품사 태깅 관련 연구 어절 n-gram 기반 HMM 모델을 그대로 응용  한국어 어절의 다양한 변화로 인한 자료부족 문제가 심각 형태소 n-gram 기반 모델로 수정  어절 내의 형태소결합제약에 따른 한국어의 어절 문맥정보를 효율적으로 반영하지 못함 형태소 n-gram 모델 보완 형태소 bi-gram 이상의 정보를 사용 어절 문맥정보를 포함하기 위한 규칙 혼합 모델 제안 경계 태그 사용

어절 내와 어절 간은 통계적인 분포가 다르므로 이중 HMM모델을 구성 한국어의 형태 ◦ 통사적 특징 1 연구 대상 언어의 특징 형태소 구분 어휘형태소(실질형태소) : 명사, 수사, 동사, 형용사, 부사 등 문법형태소(의존형태소) : 어미류, 조사류, 접사류 어절 내 형태소 결합 제약 각 형태소들이 형태소 범주 간의 결합 제약 하에 어절을 형성 어절 간 형태소열 결합 제약 한국어에서 각 어절은 이웃하는 어절과 (국부적) 통사 제약 관계를 이룸 어절 내와 어절 간은 통계적인 분포가 다르므로 이중 HMM모델을 구성

세종 Corpus Tagged Corpus 한국어의 통계적 언어처리를 위한 Golden Standard 구성 어절 수 문어 90% 신문 20% 약 10,000,000 잡지 10% 책/정보 35% 책/상상 20% 기타 5% 순구어(전사) 5% 준구어(대본) 5%

실제 데이터 (일부) 원본 형태소 Tag unigram 형태소 Tag bigram 형태소 unigram

한국어 품사 태깅 관련연구 어절 n-gram HMM을 한국어 품사 태깅에 그대로 응용 형태소 n-gram 기반 모델로 수정 [이운재92]: 태그 17개 고려 90%의 정확도 형태소 n-gram 기반 모델로 수정 [이상호93 외] 고려사항 : 형태소 분석경계가 일치하는 것만 transition을 설정 어절을 인식하지 못하고 어절간의 문맥 정보를 고려하지 못함 93.59%의 정확도

형태소 n-gram 모델 보완 1 이중 HMM(Two-ply HMM) 모델 [김진동96] 관련연구 품사열 전이 확률: 어절 간 품사 전이 확률 + 어절 내 품사 전이 확률 어절 간 문맥 매개변수를 형태소 단위로 모델링 장점 어절 단위 문맥 고려 자료부족문제를 완화한다는 장점 단점 한국어의 언어적 특성을 반영하는 어절 간 형태소열 결합 제약조건에 비추어볼 때 직관적이지 못한 문맥 정보를 사용하는 경우 발생 hi = i번째 품사열(어절)의 머리(head)품사; ti = i번째 품사열(어절)의 꼬리(tail)품사 “관형형어미”와 “동사” 간의 전이 이중 HMM(Two-ply HMM) 모델은 품사열 전이 확률을 어절 간과 어절 내 품사 전이 확률을 고려합니다. 이 모델은 어절 단위 문맥 매개 변수를 형태소 단위로 모델링 했기 때문에 자료부족문제를 완화한다는 장점이 있습니다. 그러나, 한국어의 언어적 특성을 반영하는 어절 핵 기반 어절간 결합 제약조건에 비추어볼 때, 직관적이지 못한 문맥 정보를 사용하는 경우 발생합니다. (클릭한다.) 예제의 문장에서 어절간 전이 확률로 “관형형어미”와 “동사” 간의 전이를 가정하는 것은 일반적인 한국어 언어현상에 위배됩니다.

∧(C[s](2:2), M[s](2:2)) => tri-gram일 때 최고 성능(96.97%) 형태소 n-gram 모델 보완 2 관련연구 HMM을 확장하고 어절 경계 매개 변수를 적용한 모델 [Lee00] 새로운 매개변수 도입 장점: 어절경계 인식: 띄어쓰기 태그(어절 경계) p 도입 단점: 어절 내의 구조성은 파악을 못함 tri-gram을 통한 충분한 성능 확보: 메모리 문제 ∧(C[s](2:2), M[s](2:2)) => tri-gram일 때 최고 성능(96.97%) 다음은 HMM모델을 확장하고 어절간 경계 매개 변수를 적용한 모델이 있습니다. 이는 띄어쓰기 매개변수 P를 도입함으로써 어절 경계를 인식하고 tri-gram을 사용함으로써 96.97이라는 높은 정확도를 얻고 있습니다. 그러나 이 모델은 어절 경계는 인식했지만, 어절내 의 구성 요소들 간의 구조성은 파악하지 못하며 tri-gram을 사용했기 때문에 많은 메모리가 필요합니다.

어절 확률 추정에 기반한 한국어 태깅 모델 어절 확률 추정 어절 확률 추정에 기반한 HMM 모델 성능 평가 목 차 일반적인 태깅 품사 태깅 기법 일반적 통계 기반 품사 태깅 한국어 품사 태깅 한국어의 형태 ◦ 통사적 특징 통계 기반 한국어 품사 태깅 형태소 n-gram 모델 보완 어절 확률 추정에 기반한 한국어 태깅 모델 어절 확률 추정 어절 확률 추정에 기반한 HMM 모델 성능 평가 26 26

Word Probability Estimation (1) Word내 HMM을 이용한 Word 추정 가정 1 : Word내 형태소들은 독립이다. Eq(1) Eq(2)

Word Probability Estimation (2) 가정 2 : 단어의 출현확률은 형태소 태그 패턴과 연관이 있다. 가정 3 : 단어의 생성은 각 형태소의 태그과 연관이 있다. Eq(3) wwt 형태소 태그 패턴의 가충치 Eq(4) wmt 형태소 태그의 가중치

범주 패턴 종류

학습 과정 형태소 태그 패턴 통계 정보 추출을 위한 학습 자료 준비 및 학습 어절 내 형태소 태그 패턴통계 정보 추출 세종 Corpus 어절 내 형태소 태그 패턴통계 정보 추출 학습 시간의 단축을 위하여 균형적으로 표본 추출 형태소 태그의 가중치 학습(시뮬레이티드 어닐링 알고리즘 사용) 범주 패턴 통계 정보 추출을 위한 학습 자료 준비 및 학습과정은 그림과 같습니다. 먼저, 학습 말뭉치를 수집한 후 규칙 기반 태깅 시스템으로 품사를 부착합니다. 총 말뭉치 크기는 약 3천3백만 어절입니다. 다음으로, 범주 패턴 별로 통계 정보를 추출하여 수집합니다. 추출한 총 범주 패턴은 2,626개입니다. 학습시간의 단축을 위하여 각 범주 패턴을 표본 추출합니다. 표본으로 추출된 각 범주 패턴에 대한 범주별 가중치 학습을 위해 시뮬레이티드 어닐링 알고리즘을 사용합니다. 학습 시간의 단축을 위하여 ms가 1,000개 이상 10,000개 미만인 CPMS은 1,000개의 균등한 샘플을 추출 10,000개 이상일 경우에는 10개중 1개의 샘플을 추출 1,000개 미만일 때는 CPMS의 모든 ms는 표본으로 SCPMS에 포함: 총 2,193개(1,026개의 IntraCP + 1,167개의 InterCP)

학습 알고리즘 학습 형태소 태그 가중치 학습 실제 관측된 형태소 열의 출현 확률과 형태소 태그 패턴을 기반으로 추정한 형태소 열 출현 확률의 오차가 최소가 되는 방향으로 형태소 태그 가중치 학습 Tmtj = 학습에 사용한 총 형태소 태그 패턴 개수 mγ = 학습에 사용한 패턴 집합 중 형태소 태그 패턴 mtj로 어절을 형성하는 γ 형태소열 RP = 실 관측 확률 EP = 추정 확률 범주 가중치는 실제 관측된 ms의 출현 확률과 범주 패턴을 기반으로 추정한 ms 출현 확률의 오차가 최소가 되는 방향으로 학습합니다. 힐 클라이밍 방법은 그리디 메소드로써 항상 좋은 방향으로 해를 찾아 나간다. 이렇게 할 경우 local maxima에 빠질 위험이 있다. 따라서 local maxima에 빠졌을 때 극복하는 여러가지 알고리즘이 제안되었는데, 시뮬레이티드 어닐링도 그 중 하나이다. 아주 어려운 문제를 풀기위해 점진적으로 그 해 (solution)에 가까운 방향으로 이동하되 적은 확률로 예상되는 해(즉 안 좋은 쪽)에 아주 먼 방향으로 이동해 보는 것이다. 이 때, 탐색의 초기에는 확률의 폭을 크게, 그러니까 변화의 폭에 대한 가능성을 크게 주었다가 탐색의 후기로 갈 수록 그 가능성을 점차 줄여 나간다. 이러한 부분은 알고리즘의 if ( ΔE <= 0 ) or ( exp (E(X) - E(Y) / T ) > random(0,1) ) then X  Y; // 다음 상태로 변경 이다. 여기에서 T를 이용하여 가능성의 크기를 줄여 나간다. T의 초기 값은 100이며, 초기값에 0.9998을 곱하면서 T를 계속 줄여 나간다. 예: <NN+PCO>: 총 1/1,855,195  학습에 사용한 인스턴스 191,477

어절 확률 추정 모델 평가 Model Cross entropy Equation (1) 17.53 Equation (2) 19.45 Equation (3) 15.11 Equation (4) 14.99

CAP-TM 적용 모델 적용 “시기를”에 IntraCP와 범주 가중치를 적용

HMM using the estimated word probability Eq(5)

Smoothing Good-Turing Estimation 각 통계 정보마다 모두 Good-Turing Esitmation값을 구함 형태소 unigram 형태소 tag bigram 어절 tag unigram 어절 tag bigram

Estimation of word probability 성능 평가 Model Precision MHMM 94.21% Estimation of word probability EWHMM Equation (5) Equation(1) 94.12% 95.57% Equation (2) 93.09% 95.35% Equation (3) 94.73% 96.56% Equation (4) 95.18% 96.75% Equation (1). Estimation of word probability based on HMM applied to inner-word morpheme string. Equation (2). Estimation of word probability assuming independence. Equation (3). Estimation of word probability using the weight of an MTL. Equation (4). Estimation of word probability using the weight of an mt.