[Stanford 강의] Lecture 4 : Dependency Parsing

 

이번 강의는 좀 추상적인 느낌이 드는 강의였다.

 

 

이번 글은 강의에서 언급된 아래 내용들을 알아보자.

Dependency Grammar

Greedy Transition-based Parsing

Neural Dependency Parsing

Graph-Based Dependency Parsing

---

Dependency Grammar

문장의 단어들 사이에 화살표를 그려 의존성을 표현한다.

화살표를 그리는 방향은 중심어에서 의존어 방향이다.

 

 

여기서 ROOT는 추가로 삽입된 부분인데, 분석의 시작을 의미하는 역할로 분석을 조금 편하게 하기 위해 존재한다.

 

이 의존관계는 트리로 표현했을 때 연결이 되어있어야 하고, 순환이 없어야하고, 루트가 하나여야한다.

 

대부분의 문장에서 화살표를 그리면 서로 교차되는 일은 없다. (projective)

 

그러나 의문문 같이 그렇지 않은 문장들도 있다. (non-projective)

 

 

 

 

---

Greedy Transition-based Parsing

의존 파서를 만드는 효율적인 방법이다.

컴파일러를 배웠다면 알고 있는 shift-reduce parser라고 생각하면된다.

 

여기서는 크게 3가지의 동작이 있다.

shift, left-arc, right-arc 가 있다.

• shift: 버퍼에서 스택으로 단어 하나를 가져오는 것이다.
• Left-Arc: 스택의 두 번째 단어가 의존어, 첫 번째 단어가 중심어가 되며 의존 관계를 형성하고 두 번째 단어를 스택에서 제거한다.
• Right-Arc: 스택의 첫 번째 단어가 의존어, 두 번째 단어가 중심어가 되며 의존 관계를 형성하고 첫 번째 단어를 스택에서 제거한다.

아래 사진은 shift를 두 번 한 것이다.

 

 

아래 예시는 의존성까지 포함해 파싱한 사진이다.

첫번째 상황에서 left-Arc를 수행하면 ate → I 방향의 의존성이 생기고, stack에서 I를 제거한다.

그 이후 shift로 fish를 가져오고, 이번에는 right-Arc를 수행해 ate → fish 방향의 의존성을 만든다.

이런식으로 계속하다가 종료는 stack에 root만 있고, 버퍼가 비어있을 때 일어난다.

종료까지 생겼던 의존성들은 모두 기록된다.

아래 예시에서는 A라는 집합에 의존성들이 기록되었다.

이번 내용은 CFG, shift-reduce parser같은 내용에서 컴파일러와 많은 내용이 겹친다.

이 내용들에 대해 조금 더 자세한 설명은 이 블로그의 '컴파일러' 카테고리에서 볼 수 있다.

 

어쨌든, 이 Greedy Transition-based Parsing를 사용하려면 3가지 동작 중 어떤 것을 수행할지  정해야한다.

 

 

---

indicator features

Joakim Nivre라는 사람은 이 결정을 머신러닝에게 맡겨보자는 생각을 했다.

이 사람은 로지스틱 회귀, SVM같은 분류를 사용했다.

이때 판단에 도움을 주기 위해서 indicator features라는 정보를 주었다.

이것은 현재 파싱 상태에 대한 정보이다.

예를 들면 현재 stack의 top에 어떤 단어가 있는지,

stack의 2번째 단어가 무엇인지,

버퍼의 첫 단어가 무엇인지,

이런 백만개 단위의 세세한 질문에 대한 참/거짓 여부를 1/0으로 나타내서 긴 벡터를 만들어서 정보를 나타냈다.

간단히 나타내면,

현재 스택/버퍼 상태를 보고 긴 벡터로 나타낸다.

이 벡터를 로지스틱회귀나 SVM같은 분류기를 사용해 3가지 선택지 중 높은 확률의 선택을 고른다.

 

그러나 특징의 개수가 너무 많고,

대부분의 값들이 0이었고,

파싱 시간의 대부분이 특징을 만드는데 사용된다는 문제가 있었다.

 

 

---

Neural Dependency Parsing

이 문제 상황을 잘 보면,

이전 내용인 word vector에서 원핫 방식의 단어 벡터와 비슷하다는 생각이 든다.

원핫 방식의 단어 벡터를 dense하게 만들어 해결했던 방법을 그대로 가져왔다.

 

Distributed Representations: 단어, 품사, 의존 라벨 등을 밀집 벡터(Dense Vector/Embedding)로 표현하는 방법

이 방식의 구현을 조금 더 자세히 알아보자.

 

1. 입력층: 스택과 버퍼의 핵심 단어 및 그들의 품사/라벨 임베딩을 연결한다.
2. 은닉층: 연결된 벡터를 $Wx + b$ 연산 후 ReLU 활성화 함수를 통과시킨다.
3. 출력층: Softmax를 사용하여 다음에 취할 행동(Shift, Left-Arc, Right-Arc)의 확률을 예측한다.

 

이 방식의 장점은

1. 비선형 함수가 사용되어 더 정확한 예측이 가능하다.

2. 수많은 특징에 대해 맞는지 틀린지 계산하는 과정이 없고, 단순히 이미 있는 벡터들을 연결만 하므로 속도가 빠르다.

 

---

Graph-Based Dependency Parsing

강의 후반부에는 또 다른 방법인 그래프 기반 파싱도 나온다.

기본 아이디어 : 문장의 모든 단어 쌍에 대해 의존 관계가 성립할 점수를 계산한다. ($n^2$ 개)

알고리즘: 계산된 점수들을 바탕으로 최대 신장 트리(MST) 알고리즘 등을 사용해 최적의 트리 구조를 찾는다.

비교: 전이 기반 파싱보다 정확도는 높을 수 있지만, 속도가 훨씬 느리다.