[CS224n] Lecture 5 - Linguistic Structure: Dependency Parsing

tobigsNLP·2020년 12월 29일

NLP cs224n dependency linguistic structure parsing

CS224n Review

목록 보기

5/16

작성자 : 투빅스 13기 오진석

Contents

Syntactic Structure: Consitituency and Dependency

Dependency Grammar and Treebanks

Transition-based dependency parsing

Neural Denpendency parsing

CS224n의 5번째 강의는 문장의 정확한 이해를 위한 분석 방법인 parsing에 대해 다루고 있습니다. 특히 parsing의 방법 중 Dependency parsing을 통해 문장 구조를 분석하고 이해하는 방법을 주로 소개하고 있습니다.

첫번째 목차에서는 문장 구조를 분석하는 방법인 Consitituency parsing과 Dependency parsing의 개념에 대해서 간단히 다루고 두번째 목차에서는 Dependency parsing에 대해서 보다 자세하게 다룹니다. 세번째 목차에서는 Dependency parsing의 전통적인 방법인 transition-based dependency parsing의 개념과 parsing 과정에 대해서 소개하며 마지막 목차에서는 neural network가 적용된 방법인 neural dependency parsing이 어떻게 문장 구조를 분석하는 지에 대해 설명합니다.

1. Syntactic Structure: Consitituency and Dependency

Parsing이란 각 문장의 문법적인 구성 또는 구문을 분석하는 과정이라고 할 수 있습니다. 주어진 문장을 이루는 단어 혹은 구성 요소의 관계를 결정하는 방법으로, parsing의 목적에 따라 Consitituency parsing과 Dependency parsing으로 구분할 수 있습니다.

Consitituency parsing은 문장의 구성요소를 파악하여 구조를 분석하는 방법이며, Dependency parsing은 단어간 의존 관계를 파악하여 구조를 분석하는 방법입니다.

Consitituency parsing은 문장을 구성하고 있는 구(phrase)를 파악하여 문장 구조를 분석하는 방법입니다. 보통 각 단어들은 해당 단어의 문법적 의미를 가지고 있습니다.'the'는 '관형사(Det)', 'cat'은 '명사(N) 등을 예로 들 수 있습니다.

이렇게 각 문법적 의미를 가지고 있는 단어들은 단어끼리 결합해서 어떠한 구(phrase)를 구성할 수 있습니다. 그리고 구성된 구는 구와 또 결합할 수 있으며, 이는 곧 문장이 될 수 있음을 의미합니다.

그렇다면 반대로 주어진 문장이 있을 때에는, 문장을 이루는 구(phrase)를 파악할 수 있으며, 구를 이루는 구, 혹은 구를 이루는 단어들을 최종적으로 분류할 수 있습니다.

'The cuddly cat by the door'에서는 명사구(Noun Phrase)인 'The cuddly cat'과 전치사구(Preprositional Phrase)인 'by the door'로 먼저 구분할 수 있으며 최종적으로는 각 단어가 가지는 문법적 의미까지 분해할 수 있습니다.

Dependency parsing은 문장에 존재하는 단어 간 의존 또는 수식 방향으로 관계를 파악하여 문장 구조를 분석하는 방법입니다. 이는 문장을 이루는 단어 사이에 서로 영향을 미치는 어떠한 관계가 있음을 전제합니다.

단어 간 존재하는 관계를 의존 관계 혹은 수식 관계로 표현할 수 있으며, 수식을 하는 단어는 'head' 혹은 'governor', 수식을 받는 단어를 'dependent' 혹은 'modifier'이라고 합니다.

이렇게 단어 간 관계를 정립하게 되면 우측과 같이 문장을 트리 구조로 표현할 수 있게 됩니다.

이렇게 문장 구조를 parsing이라는 방법을 통해 분석해야하는 이유는 문장의 의미를 보다 정확하게 파악하기 위해서입니다.

의사소통은 보통 단어의 복잡한 구성을 통해 이루어지기 때문에 보다 정확하게 해석 및 이해하기 위해서는 문장 구조의 연결 구조를 파악할 필요가 있습니다.

문장 구조를 분석해야하는 이유로 해당 강의에서는 문장에서 발생하는 2가지 모호성(ambiguity)을 소개합니다.

먼저 Phrase Attachment Ambiguity는 형용사구, 동사구, 전치사구 등이 어떤 단어를 수식하는지에 따라 의미가 달라지는 모호성을 말합니다.

Coordination Scope Ambiguity는 특정 단어가 작용(수식)하는 대상의 범위가 달라짐에 따라 의미가 변하는 모호성을 말합니다.

즉, 정리하자면 문장은 많은 단어가 복잡한 관계로 이루어져 있기 때문에 올바르게 이해하기 위해서는 문장의 구성요소에 대한 분석과 이해가 요구됩니다.

2. Dependency Grammar and Treebanks

Dependency parsing에 대해서 보다 구체적이게 알아보겠습니다. 해당 parsing 방법은 sequence 형태와 tree 형태로 표현할 수 있으며, 2가지 형태의 결과는 정확히 동일한 output을 가져야 합니다.

Dependency parsing의 특징은 다음과 같습니다.

먼저 'ROOT'라는 가상의 노드를 문장의 맨 처음에 추가함으로써, 최종 head를 'ROOT'를 설정하고 모든 단어가 1개의 dependent(의존 관계)를 가지도록 설정합니다.

수식을 하는 head와 수식을 받는 dependent는 화살표로 표현하며 문법적 관계 또한 같이 적어줍니다. 마지막으로 수식 관계인 화살표는 순환하지 않으며 중복 관계는 형성되지 않는다고 합니다.

Dependecy parsing에서 고려되는 보편적인 특징은 다음과 같습니다.

이는 항상 정답이라고 할 수는 없지만 parsing 과정과 결과에서 발생하는 전형적인 특징들을 정리해 놓은 것으로 생각됩니다.

3. Transition-based dependency parsing

Dependecy parsing의 방법으로 강의에서는 4가지 방법이 있다고 소개합니다. 하지만 이번 강의와 목차에서는 Transition-based 방법에 대해서 보다 구체적이게 다루고자 합니다.

Transition-based dependency parsing은 두 단어의 의존 여부를 차례대로 결정해나가면서 점진적으로 dependency structure를 구성해나가는 방법입니다.

이 방법은 문장에 존재하는 sequence를 차례대로 입력하게 되면서 각 단어 사이에 존재하는 dependency를 결정해나가는 방법으로 'Deterministic dependecy parsing'이라고도 불립니다.

문장의 sequence라는 한 방향으로 분석이 이루어지기 때문에 모든 경우를 고려하지는 못합니다. 그렇기 때문에 분석 속도는 보다 빠를 수 있겠지만 낮은 정확도를 보이기도 합니다.

Transition-based dependency parsing이 진행되는 과정에 대해서 살펴보겠습니다. 먼저, parsing 과정에는 BUFFER, STACK, Set of Arcs라는 3가지 구조를 가지고 있습니다.

input으로 문장이 입력되면, 위 3가지 구조를 거침으로써 output이 도출되는 parsing 과정입니다. parsing 초기 상태에서 BUFFER에는 주어진 문장이 토큰 형태로 모두 입력되어 있는 상태이며, STACK에는 ROOT만이 존재하고 Set of Arcs에는 parsing의 결과물이 담기게 됩니다.

parsing 과정에 대해서 간단하게 설명하면 다음과 같습니다. BUFFER에 존재하는 문장의 토큰이 STACK으로 이동하게 되면서 어떠한 state를 형성하게 됩니다. 그리고 해당 state를 기반으로 Decision이라는 결정을 내리게 되고 output으로 결과가 이동하게 됩니다.

먼저 BUFFER에서 STACK으로 토큰이 이동하는 과정은 문장의 sequence를 따릅니다. 즉 BUFFER('Joe', 'ate', 'the', 'cake')가 존재한다면 문장의 첫번째 토큰인 'Joe'가 먼저 STACK으로 이동하게 됩니다.

그렇게 되면 STACK에는 'ROOT'와 'Joe'가 존재하게 되면서 어떠한 state를 형성하게 됩니다. 그 때, 이 state를 통해 Decision이라는 결정을 내리게 됩니다. Decision을 결정하는 방법으로는 단순히 함수와 같은 역할이라고 볼 수 있으며 강의에서는 SVM, Neural Network등의 모델이 적용될 수 있습니다.

STACK에서 토큰과 토큰의 존재로 다양한 state가 형성되겠지만 결정되는 Decision은 여기서 3가지를 소개합니다.

Shift: BUFFER에서 STACK으로 이동하는 경우
Right-Arc: 우측으로 dependency가 결정되는 경우
Left-Arc: 좌측으로 dependency가 결정되는 경우

정리하자면, STACK에서 발생하는 state가 정해진 모델을 통해 3가지 Decision이 결정되는 과정을 가진다로 이해하면 될 것 같습니다.

실제로 'Joe ate the cake.' 문장이 Transition-based 방법을 통해 parsing되는 과정을 알아보겠습니다.

초기 상태는 위에서 언급한대로 BUFFER에는 주어진 문장이 토큰 형태로 입력되어 있으며 STACK에는 ROOT만이 존재합니다.

(1) STACK에 ROOT만이 존재하는 state는 'shift'라는 decision이 내려지게 되면서 'Joe'가 BUFFER에서 STACK으로 이동하게 됩니다.

(2) STACK에는 ROOT, Joe라는 state가 'shift'라는 decision이 내려지게 되고 'ate'이 BUFFER에서 STACK으로 이동하게 됩니다.

(3) STACK에는 ROOT, Joe, ate라는 state는 'ate'이 'joe'를 수식하는 'Left-Arc'라는 decision이 내려지게 됩니다.

이 때, 'ate'과 'Joe'가 관계가 형성되었기 때문에 해당 결과는 Set of Arcs로 이동하게 됩니다. 또한 dependent가 되는 단어(Joe)는 STACK에서 사라지게 됩니다.

(4) STACK에는 ROOT, ate라는 state가 'shift'라는 decision이 내려지게 되면서 'the'가 BUFFER에서 STACK으로 이동하게 됩니다.

(5) STACK에는 ROOT, ate, the라는 state에서도 어떠한 관계가 형성되지 않는다고 판단했기에 'shift'라는 decision이 내려지게 되고 'cake'가 BUFFER에서 STACK으로 이동하게 됩니다.

(6) STACK에는 ROOT, ate, the, cake라는 state에서 'cake'가 'the' 수식하는 'Left-Arc'라는 decision이 내려지게 되고 해당 결과(cake, det, the)는 Set of Arcs로 이동하게 됩니다.

(7) STACK에는 ROOT, ate, cake라는 state에서 'ate'가 'cake'를 수식하는 'Right-Arc'라는 decision이 내려지게 되고 해당 결과(ate, dobj, cake)는 이동합니다.

(8) STACK에는 ROOT, ate라는 state에서 BUFFER에 토큰이 존재하지 않기 때문에 'shift'가 발생할 수 없습니다. 하지만 모든 토큰은 하나의 dependent를 가진다는 dependency parsing의 특징으로 'ROOT'가 'ate'를 수식하는 'Right-Arc'라는 decision이 내려지게 되고 해당 결과(Root, root, ate)는 이동합니다.

이렇게 문장의 모든 토큰이 BUFFER와 STACK을 통해 어떠한 관계가 결정되고 형성됨으로써 output으로 트리 형태로 표현이 가능해집니다.

앞서 언급했듯이, STACK에서 발생하는 어떠한 state를 기반으로 Decision을 결정하기 위해서는 SVM, NN, maxnet과 같은 모델이 적용됩니다. 이 과정에서 state를 모델이 input으로 받기 위한 state 임베딩 과정이 필요하게 됩니다.

state를 임베딩하는 방법으로 2005년데 발표된 Nivre and Hall의 논문인 MaltParser: A Data-Driven Parser-Generator for Dependency Parsing의 feature representation을 살펴볼 수 있습니다.

먼저 (4)와 같은 state일 때, 해당 state가 임베딩되는 과정에 대해서 설명하겠습니다. 임베딩 과정을 알아보기에 앞서 임베딩을 위한 feature를 표현하기 위해서 notation을 확인할 수 있습니다. 이 때, 각 토큰의 tag를 활용하기도 합니다.

해당 state에 알맞은 notation 결과를 다음처럼 확인할 수 있습니다. 보여지는 notation은 일부분을 예시로 보여준 것으로, STACK의 두번째 단어 'ate'과 같은 notation을 추가적으로 뽑아낼 수 있습니다.

그리고 해당 notation의 결과를 찾아볼 수 없을 때에는 그냥 NULL을 부여하게 됩니다.

그렇다면 이러한 notation 기반으로 indicator features라는 조건을 설정함으로써 state를 임베딩할 수있다고 말합니다.

예시를 보게 되면 STACK의 첫번째 단어가 'the'이고 STACK의 첫번째 태그가 'DT'면 1 아니면 0 이라는 값이 부여지게 됩니다. 이러한 조건들로 하여금 해당 state를 $10^6 ~ 10^7$ 차원의 벡터로 표현하게 되는 것이 state를 임베딩하는 방법이라고 합니다.

해당 과정에서 indicator features에 설정되는 조건이 어떠한 기준으로 정해지는 것인지 여전히 이해하지 못하고 있는 부분입니다. 개인적으로는, 발생할 수 있는 notation의 모든 조합 혹은 조합들로 조건을 동일하게 구성하는 것으로 이해하였습니다.

이렇게 state를 임베딩하는 방법은 1과 0인 binary로 표현되게 됩니다. 그렇기 때문에 sparse한 형태의 특징을 가지게 됩니다.

강의를 보게 되면 'Feature templates: usually a combination of 1~3 elements from the configuration'이라고 말하는데, notation의 1~3개의 조합으로 indicator feature의 조건을 설정하는 것으로 이해하였습니다.

어쨌든, $10^6 ~ 10^7$ 차원을 모두 계산하여야 하기 때문에 해당 과정에서는 feature 연산이 대부분을 차지하고 단어 또는 단어의 태그의 의미를 반영하지는 못하는 단점이 있습니다.

4. Neural Denpendency parsing

최근에는 신경망 기반의 방법론들이 발전하게 되면서 neural network가 적용된 Dependency Parsing에 대한 방법론도 제기되었습니다. 모델 구조는 기본적인 neural network 형태를 가지고 있습니다.

이 때, input으로 들어가는 state를 representation하는 방법에 대해서 보다 구체적이게 다루도록 하겠습니다.

input으로 들어가는 feature는 words 부분, POS tag(태그) 부분, arc labels 부분 3가지로 구분할 수 있습니다.

먼저 words feature로 들어가게 되는 데이터는 총 18개로 구성되어 있습니다.

STACK과 BUFFER의 TOP 3 words (6개)
STACK TOP 1, 2 words의 첫번째, 두번째 left & right child word (8개)
STACK TOP 1,2 words의 left of left & right of right child word (8개)

다음 POS tags feature로 들어가게 되는 데이터는 words feature에서 들어가는 데이터의 태그를 의미하기 때문에 똑같이 18개가 됩니다.

마지막으로 arc labels에서는 STACK과 BUFFER의 TOP 3 words 6개를 제외한 12개의 label(dependent 관계 표시) 데이터로 구성되게 됩니다.

(4)의 state일 때의 input layer의 데이터를 확인하게 되면 각 feature별로 다음과 같이 확인할 수 있습니다. 이 feature에 해당하는 데이터들을 원핫으로 표현할 수 있게 됩니다.

words feature는 (18 x 단어의 총 개수)
POS tag feature는 (18 x POS tag 총 개수)
Arc-label feauture는 (12 x label 총 개수)

이 때, 일반적으로 POS tag의 개수는 45개 정도라고 말합니다.

이렇게 포함된 데이터를 원핫으로 표현한 후에 word embedding matrix를 참고하여 해당 토큰의 벡터를 가져올 수 있습니다. 그렇다면 각 토큰별로 벡터가 있는 상태에서 모두 concat한 뒤에 input layer에 들어가게 됩니다.

각 feautre별로 임베딩된 벡터가 input layer를 입력된 이후에 hidden layer에서는 일반적인 feed forward network의 계산이 진행됩니다.

이 때, 신경망에서 보통 쓰이는 ReLU, Sigmoid, Tanh과 같은 activation function을 사용하지 않고 cube function을 사용하게 됩니다. (논문에서는 위 처럼 cube function을 적용했다고 했지만 강의에서는 그냥 ReLU를 적용한 것으로 보아 activation function의 차이가 그렇게 크지 않는 것으로 이해했습니다.)

논문에서 cube function을 적용하게 되면 input으로 들어가는 3개의 feature인 word, POS tag, arc-label의 조합이 계산되면서 feature간의 상호관계를 파악할 수 있다고 말합니다.

마지막으로 output layer에서 Decision이 결정되는 과정은 다음과 같습니다.

hidden layer를 통과하고 나서는 softmax()를 통해 Decision으로 나타날 수 있는 모든 경우의 수의 확률을 구하게 됩니다. 다음 가장 높은 확률로 분류될 Decision이 선택되게 되며 해당 state에서는 conj의 관계를 가지는 Left-Arc의 경우가 Decision으로 선택되게 됩니다. (해당 결과는 (4)의 state와는 관계 없습니다. (4)의 state에서는 Shift Decision이 가장 높은 확률을 가질 것으로 예측됩니다.)

Neural Dependency parsing을 evaluation하는 방법으로는 Arc 방향만을 예측하는 UAS evaluation과 Arc 방향과 관계 label까지 예측하는 LAS가 있습니다.

각 parsing 방법에 따른 성능을 비교해보자면 목차 3에서 다뤘던 conventional features representation이 적용된 Transition-based parser(첫번째 parser)의 경우 모든 경우의 수를 체크하는 Graph-based parser보다 훨씬 빠르지만 성능이 조금 낮은 것을 확인할 수 있습니다. 하지만 Neural Network를 적용함으로써 Graph-based parser보다 빠르고 좋은 성능을 이끌 수 있게 됩니다.