[자연어]Statistical Parsing

[Chunking]

Chunking: 의미있는 chunk(NP, VP등)를 찾아내는 것

 

Phrase Chunking as Sequence Labeling

Tag individual words with one of 3 tags.

 - B (Begin) word starts new target phrase

 - I (Inside) word is part of target phrase but not the first word

 - O (Other) word is not part of target phrase

--> 위의 tagging 방법을 통해서 문장의 단어의 classification문제로 바꿈

 

Evaluating Chunking

recall과 precision은 반비례 관계에 있음

따라서, F1를 사용 = 2PR/(P+R)

 

 

 

[Statistical Parsing]

목적: assign probabilities to each parse tree

방법: tree-banks를 사용하여 supervised learning을 수행함

사용 알고리즘: PCFG(Probabilistic Context Free Grammar) 사용

PCFG: Probabilistic version of a CFG

determiner가 나왔을때 그게 the가 될 확률 = 0.6

가정: 모든 단어의 출현확률은 indenpendent하다고 가정

--> 따라서, 모든 확률의 곱이 그 문장의 확률

--> 문법적으로 옳은 parse tree들의 합이 최종적인 sentence probability임

 

 

 

PCFG Tasks의 활용 사례 3가지

• Observation likelihood: To classify and order sentences.

--> Eg) 음성인식, 번역 (sentence probability 찾는 목적)

• Most likely derivation: To determine the most likely parse tree for a sentence.

--> 가장 그럴듯한 parse tree를 찾기위해

• Maximum likelihood training: To train a PCFG to fit empirical training data.

--> PCFG를 training시키는 것

 

 

Most likely derivation - CKY Parsing

이때 사용하는 CNF(Chomsky normal form)는 아래와 같음

CNF와 그에 따른 확률값이 있는게 기존 CNF와의 차이

 

 

Probabilistic CKY Parser계산하기(max)

Cell[i,j]에는 확률값이 높은 값만 들어감

여기서 0.00001296<0.0000216이므로 0.0000216만 최종적으로 표시

 

 

Probabilistic CKY Parser for Inside algorithm(observation likelihood)

문법적으로 옳은 parse tree들의 합이 최종적인 sentence probability임

즉, 위의 CKY Parser의 최종 sentence probability를 합해줌

0.00001296+0.0000216 = 0.00003456

 

 

Supervised training: PCFG

tree bank활용 -> 모두 count해서 확률값을 정함

--> 단점. 의미적정보를 배제하기 때문에 syntactic ambiguity가 존재함

--> eg. ate spagetti with fork vs. meatballs에서 fork는 ate를 수식하고

     meatballs는 spagetti를 수식함

--> 근데 보통 PP는 명사를 수식하기 때문에 tree bank를 통한 확률은 부정확함

--> 해결책. lexicalized rule을 만들어서 적용

밑에 in the pen이 the dog를 수식하게 하면 틀린 문법이라고 미리 rule을 만들어 놓음

즉, Lexicalized rule에 들어가는 head-word를 정해놓음

 

 

 

Head-words의 4가지 rule

1. NP의 head는 main noun

2. VP의 head는 main verb

3. PP의 head는 preposition

4. S의 head는 VP

즉, put 뒤에 in이라는 전치사는 put을 수식하는 전치사라고 head-word를 정함(the dog를 수식X)

 

 

Parsing Evaluation Metrics

precision과 recall 사용

P: system's parse tree, T: human's parse tree

labeled precision & labeled recall(NP, VP등등)

--> 보통 이걸 주로 사용

F1스코어로 최종 계산함

 

 

[한국어 구문분석]

의존문법을 이용한 한국어 구문 분석

참고로 영어는 phrase structure를 활용

한국어는 문장 성분들간의 의존관계를 사용

- 개념: 문장 성분들 간의 의존 관계(수식 관계)를 통해문장의 구조를 기술

- 특징1: 두 성분들 간의 방향성을 갖는 이진 관계

  종속성분(Modifier=수식어) -> 지배성분(Head) : 맛있는 사과 

- 특징2: 종속 성분들 간의 순서 무시

부분 자유 어순

 

부분 자유어순: 한국어에 적용

철수가 빵을 먹었다. = 빵을 청수가 먹었다.

Mary hits Jane != Jane hits Mary

 

한국어의 특징

– 문장 성분들 간의 부분 자유 어순

– 문장 필수 성분의 생략 빈발

– 지배성분(피수식성분) 후위의 원칙

 

분석 Algorithm

챠트를 이용한 분석(normal chart parsing)

 

분석 방향

좌 => 우 (from left to right)

우 => 좌 (from right to left): 한국에서 더 효율적인 방법

 

 

한국어 분석 시의 제약사항 3가지

투영의 원칙(projectivity) : 엇갈린 의존관계를허용하지 않음

지배 성분 유일의 원칙 : 임의의 문장 성분은 다른 하나의 문장성분만을 수식

지배성분 후위의 원칙

 

 

2가지 의존 규칙 형태

- 어절 의존규칙

형식형태소가 많으면 가장 끝에를 형식형태소로 해주면 됨. 참고로 실질 형태소는 단 1개 밖에 없음

- 형태소 의존규칙

 

 

분석 알고리즘

분석알고리즘에 투영원칙의 준수 규칙을 넣어주면 더 빠르게 진행할 수 있음

** 투영원칙의 준수는 cross가 발생하지 않는 것

 

기존 11단계에서 8단계로 끝냄

 

 

Dependency Grammars(의존규칙) for ENG

영어도 의존규칙(dependency grammar)을 쓰기도 함

 

 

결론: 통계적 parsing 기법은 사람의 labeling보다 성능이 떨어짐

DNN을 활용하면 거의 사람만큼의 성능을 얻을 수 있음