[cs224n]Lecture 6. Dependency parsing

1. 문장의 구조를 나타내는 방법 2가지

문장의 구조 (linguistic structure) 를 나타내는 방법에는 두 가지가 있다. 

- Context-free grammars (CFGs) 

- Dependency tree parsing 

 

우선 Context-free grammars 은 내가 예전에 배웠던 syntax tree 생각하면 된다. 왜 context free 라고 부르는지 생각해보면, 문장 내의 단어 의미나 context 에 상관없이 문장의 각 성분을 어떤 큰 chunk 를 이루는 구성요소로 보기때문이 아닐까 싶다. NP -> Det N 이런식으로.

 

하지만 요새 대세는 dependency parser 로 굳어지는 듯 하다. 장점은 여러가지가 있겠지만 우선 다음의 장점이 있다. 

1) 언어에 상관없이 적용 가능 <-> CFGs 는 영어 문법 위주로 작성됨. 

2) 문장의 의미 구조 파악 가능 

3) 어떤 단어를 표현함에 있어서 그것을 다른 단어 와의 관계로 설명하려고 한다는 점에서 우리가 이미 했던 distributed word representation 과 비슷한 맥락이다. good 

 

2. Dependency grammar 와 Dependency structure

"Bills on ports and immigration were submitted by Senator Brownboack, Republican of Kansas." 에 대한 문장을 아래에서 Dependency 관계로 나타낸 것이다. 우선 dependency tree 는 head 와 그것의 dependent (= modifier, subordinate) 로 이루어진다. 우선 modifier 때문에 이 관계가 굉장히 헷갈렸다. 보통 modifier 는 명사를 수식하는 형용사나 전치사구로 알고있었기 때문이다. 근데 위치 피디아를 찾아보니 dependent 에 해당하는 것은 modifier 뿐만이 아니라 argument (예 - 동사의 목적어) 혹은 complement (예 - 동사의 보어) 도 포함한다. 

 

그 외 몇 가지 dependency structure 를 나타내는 규칙을 몇 가지 더 보자. 

 

1) pseudo element 인 ROOT 를 추가해서 문장의 모든 성분의 최종 head 는 결국 이 ROOT 가 되게 한다는 것이다. 그리고 ROOT 의 dependent 는 거의 항상 문장의 main verb 이다 (내가 이해한대로는 그렇다). 

 

2) 그리고 모든 성분은 단 하나의 head 만을 가진다. 

 

3) Universal Treebank 에서는 전치사를 case 로 본다. 이게 특이한 점인데 기존의 문법에서는 전치사는 전치사의 목적어를 가진다고 정의했다. 그런데 Universal treebank 에서는 이 전치사를 단지 어떤 case 를 나타내는 marker 로만 인식한다. 그래서 전치사와 함께 오는 명사의 dependent 로 포함시켜 버린다. 

 

4) 화살표는 head 에서 dependent 로 그린다

: 사실 이건 그리는 사람에 따라 다르다고 한다. 하지만 이 수업에서는 head -> dependent 로 통일해 혼란을 줄이자. 

 

 

Dependency parsing 을 할 때 사실 의존 관계를 나타내는 화살표 외에도, 그 관계를 정의하는 label 을 붙여서 많이 쓴다 (아래 그림 참조) 

 

 

그럼 이제 이 dependency 를 나타낼 때, 어떤 기준을 가지고 나타내느냐가 좀 더 궁금해지는데, 아래의 슬라이드를 보자. 

 

1) 우선 2단어 간의 의미 관계가 상당히 중요하다. dependency 는 상당히 lexicalized representation 이다. 

2) dependency 관계는 주로 인접한 단어끼리 이루어진다. 

3) dependency 관계는 동사나 구둣점을 뛰어 넘어서 이루어지지 않는다.

4) Head 와의 결합가 (valency) - 즉, head 가 무엇이냐에 따라서 그것이 갖는 dependents (종류와 방향 - 왼, 오) 에 대한 패턴이 어느 정도 존재한다는 것이다. 예를 들어, 관사 the 는 dependent 가 없는 반면, 동사는 많은 dependents 를 갖는다. noun 도 많은 dependents 를 갖는데, 형용사 dependent 는 (주로) 왼쪽에 위치하고, 전치사 dependent 는 오른쪽에 위치한다. 

 

 

 

근데 수업 초반에 어떤 단어가 어떤 단어를 modify 하는지에 대한 문제는 완전한 free choice 가 아니라고 설명하면서, 문장 내에서 dependeny 를 나타내는 화살표 끼리는 서로 크로스 하지 않는다고 얘기 했다. 이를 nesting contraint 라고 했는데 우리는 그렇지 않은 예외 문장을 마주치곤 한다. 어떤 문장이냐면 다음과 같은 문장이다. 

 

I'll give a talk tomorrow on bootstrapping.

 

사실 이 문장의 원래 I'll give a talk on bootstrapping tomorrow 인데, bootstrapping 이라는 단어가 길어서 rightward movement 가 일어났다고 본다. 그렇기 때문에 최종 문장이 위에서와 같이  I'll give a talk tomorrow on bootstrapping  이 된 것이고 이런 경우에는 arrows 끼리 cross 가 일어난다는 거다. 

 

 

이 때, 어떤 학생이 "이런식으로 cross 가 나타내는데 이걸 dependency structure 로 나타낼 경우 그럼 dependency tree 로부터 기본 문장의 orders를 역으로 찾아낼 수 있냐"고 하자 교수님이 "없다" 고 시원하게 대답했다. 

 

 

 Automatic dependency parser 를 만드는 데는 여러 가지 방법이 있는데, 가장 많이 쓰이며 이 수업에서 집중할 method 는 Transition-based parsing 이다. 

 

3. Greedy transition-based parsing 

우리가 쓸 transition-based parsing 모델을 Joakim Nivre 가 만든 모델에서 영감을 얻은 모델이다. 그의 모델을 상당히 간단하다. Dependency 를 결정하는 문제를 단순히 classification 문제로 만들어 버리는 것! 

 

더 설명하기 전에 앞서서 greedy 라는 말이 algorithm 과 같이 쓰일 때 무슨 의미일지 항상 궁금해서 찾아봤다. Tree decision 같이 가지를 뻗어나가는 방식으로 의사 결정이 이루어져야 하는 문제일 때, 의사결정을 현재 branch 에서 최고인 방법을 정하고 다음 branch로 넘어가는 것이다. 그 의사 결정이 tree 전체를 보았을 때 최고의 결정인지는 모르나 현재 주어진 가지에서는 최고의 선택인 것이다 (statistical 자동 번역 모델을 생각해보기). 이런 결정을 'greedy' 하다고 한다. 즉, alternatives (예 - 조합 가능한 여러 개의 번역 옵션) 를 생각해보지 않고, 결정 내리는 branch 에서 최고의 선택을 내리고 다음 스텝으로 진행하는 것. 그리고 한번 선택을 내린 이상, 이 선택이 설사 틀린 것이었다고 해도 다시 돌아와서 바꿀 수 없다. 앞으로 계속 나아가면서 그 타입스텝에서의 최고의 선택을 할뿐이다. 

 

 

자 그럼, transition-based parser 의 알고리즘을 살펴보자. 상당히 간단하다! 

 

1) 우선 문장의 모든 단어는 stack 혹은 buffer 에 위치한다. 

2) 이 상태에서 가능한 action 은 딱 3가지**이다. 

- shift : buffer의 top word 를 (가장 왼쪽 단어) stack 의 top position (가장 오른쪽)으로 이동 

- left arc : stack 의 top word 를 화살표로 연결 (<-), 그리고  dependent 제거 

- right arc :  stack 의 top word 를 화살표로 연결 (->) 그리고  dependent 제거  

 

 

3) start condition / end condition

- start condition : buffer 에 단어가 한 개 (root), stack 에는 모든 단어. 

- end condition : buffer 에 단어 한 개 (root), stack 은 empty. 

 

결국 automatic parser 는 각 step 에서 2)번의 3가지 actions 중 하나를 선택하는 classifier 라고 보면 된다!     

 

** 여기서는 단순화를 위해 3가지 action 뿐이라고 했지만 real application 에서는 관계마다 label 까지 정의하기 때문에 80여개 정도의 action 중에서 골라야 함. 

ex) Left arc - modifier, Left arc - subj, .... 등등 

 

 

앞서서 parser 를 3가지 액션 중 하나를 선택하는 classifier 라고 했는데 그럼 그 classify 는 어떻게 이루질까? 기존의 machine learning 방법을 이요했던 Joakim 의 MaltParser 는 다음과 같다. 

 

우선 classification 을 위해 사용한 feature 는 다음과 같다 : top of stack word, 그 단어의 POS, top of buffer word, 그 단어의 POS 등등.. 

그리고 search 를 사용하지 않았다. 즉 대안(alternatives) 없이 current word 에 대해서 3 가지 액션 중 하나만 classify 하고 바로 그 뒤로 넘어갔다.  Lenear 하게 쭉쭉 뻗어나가며 classify 하고 지나간 선택에 대해서는 다시 돌아가지 않는다. 

 

 

 

앞서 말한대로 사용한 feature 는 top of stack word, 그 단어의 POS, top of buffer word, 그 단어의 POS 등등.. 이다. 기존의 방식대로 단어는 back of words 처럼 나타내고 여기에 단어의 위치 (top of stack, top of buffer) 그리고 다른 features (예- 시제) 까지 one hot vector 로 나타낸 다음 이 vector 을 단순히 concatenate 에서 feature 로 이용한다. 근데 문제는 단어를 back of words 방식으로 나타내면 엄청나게 dimension 이 커져 버리고, 거기에다가 엄청나게 sparse 한 feature 가 된다. 그리고 그 위에 classification model 을 build 하게 되는 것이다... 

 

이 문제를 해결하기 위해서 Neural network 를 사용하게 된다..! 

 

 

 

 

4. Neural net 을 이용한 dependency parser 

교수님은 기존의 classical machine learning 을 이용한 transition-based dependency parser 에서 한 발 더 나아가 우리가 가진 2가지 hammers 를 가지고 Neural net 을 통해 파서를 만들 것을 제안했다. 

 

여기서 2가지 hamemrs 란,

1) Word vector 

2) classifier with feed forwqrd neruql network, with softmax on top 이다. 

 

다시 한번 기존의 parser 의 문제점을 꼽자면 다음과 같다. 

1) Sparseness : 단어를 back of words 로 나타내면 dimension 이 엄청나게 커지고, 여기에 다른 것들도 합쳐서 각 단어에 대한 feature 를 만드는데 (feature table 있음), 그럼 그 feature는 엄청 sparse 해진다. 

2) Incomplete : configuration 에서 본 적이 없는 rare words 나 rare combination of words 이 있을 경우, feature table 에 존재하지 않기 때문에 완전하지 않은 모델이 된다. 

3) Expensive computation : 1)번과 관련된 문제이다. 엉청나게 방대한 feature space 를 가지고 이를 hash map 으로 표현한다 ( feature id : weight of the feature) 그런데 하도 방대한 feature space 에서 검색을 해야 되다 보니 이 자체만으도 엄청나게 많은 시간을 잡아먹게 되는거다! 실제로 계산의 95% 가 단순히 feature map 에서 해당 feature 를 검색하는 것으로 밝혀짐! 

 

 

그럼 Neural net을 통해 만들어 볼까? 

 

우선 특정 위치(top of stack, top of buffer...)에 있는 각각의 단어들에 대해 (loop), word vector와, POS, 그리고 이 전에 했던 arc decision 을 feature 로 쓰는데 각각의 feature vector 를 concatenate 해서 하나의 긴 vector 를 사용. 이미 word vector 를 쓴다는 점에서 dimension 이 굉장히 많이 줄어든다. 

 

 

모델 구조는 상당히 단순. 

1) Input layer 

2) Hidden layer - activation with ReLU 

3) Output layer 

 

 

5. Non linearity & ReLU (Linear rectifier) 

이미 강조한 적이 있지만 Deep neural network 의 핵심은 non linearity 다. Linear 한 함수를 여러겹으로 쌓아봤자 결국은 linear 하기 때문에 각 layer 마다 non linear 한 activation function 을 써 주는 것이 중요하다. 

 

그럼 DNN 에서 쓰는 활성 홤수의 종류는 무엇이 있을까? 수업 시간에 특히나 많이 본 sigmoid 도 있고 또 tanh 도 있다. tanh 은 sigmoid 를 rescale 한 것이라고 보면 된다. sigmoid 는 0~1 사이의 값을 반환 하는 반면, tanh 은 -1 ~ 1 사이의 값을 반환한다. 

 

 

 

그러나 최근(?) 가장 인기 있는 활성화 함수는 ReLU (rectified linear unit) 이라고 한다. 특히나 1번째 layer 의 활성함수로 많이 쓰이는 데 이유가 뭘까? 아무래도 sigmoid 나 tanh 에서 흔히 발생하는 문제였던 vanishing gradient 를 줄여주기 때문이 아닐까. 왜냐면 sigmoid 랑 tanh 에서는 기본적으로 exp 를 쓰기 때문에 최종 값이 굉장히 작아지게 되고, 값이 작아진다는 것은 결국 이 값의 영향력을 줄이는 것이다. 이 값이 겹겹의 layer 를 통과할수록 이 값에서 비록되는 error signal 도 작아지게 되는 거고 그러면 결국 gradient 가 vanish 하는 문제가 생기게 되는건데 ReLU 는 아무래도 이런 점에 있어서는 sigmoid 나 tanh보다 나은 결과를 가져오는 게 아닐까.