작성자: 성균관대학교 사회학과 박지은

Contents

1. Constituency and Dependency
2. Dependency Grammar and Treebanks
3. Transition-based Dependency Parsing
4. Neural Dependency Parsing

1. Constituency and Dependency

우선 parsing이 무엇인지부터 살펴보겠습니다. Parsing은 단어 그대로 각 문장을 쪼개어, 문법적인 구성 또는 구문을 분석하는 과정입니다. 문장을 input으로 넣으면, output으로 구문분석 트리를 구성하게 되고, 컴파일러와 비슷하게 NLP에서는 이렇게 얻은 parse tree를 문장의 구조를 분석하는 데에 쓰입니다. Parsing은 목적에 따라 constituency parsing과 dependency parsing으로 구분할 수 있습니다. Constituency parsing의 문법적으로 접근하여 문장의 구성요소를 파악하여 구조를 분석하는 방법이며, dependency parsing은 단어 간의 의존 관계를 파악하여 구조를 분석합니다. 이 둘에 대해서는 뒤에서 더 자세히 살펴보겠습니다.

1-1. Constituency Parsing

먼저 constituency parsing은 우리말로 구 구문분석이라 할 수 있으며, phrase structure를 이용하여 문장을 중첩된 성분으로 나누어 분석하는 방법입니다.
구를 파악하여 분석하고, 단어의 의미보다 문법을 이용하기 때문에 phrase-structure grammar 또는 context-free grammar라고도 합니다. 또한 영어처럼 어순이 비교적 고정적인 언어에서 주로 사용됩니다. 문장이 주어지면 문장을 이루는 구를 파악할 수 있으며, 여기서 더 작은 구나 구를 이루는 단어들을 분류할 수 있습니다. 오른쪽 트리처럼, the cuddly cat by the door는 명사구 NP와 전치사구 PP로 나누고, 최종적으로는 각 단어가 가지는 문법적 의미까지 분해할 수 있습니다.

1-2. Dependency Parsing

이제 dependency parsing에 대하여 알아보겠습니다. Dependency parsing은 우리말로 의존 구문분석이라 하며, input 문장의 단어들 사이에 서로 영향을 주는 어떠한 관계가 있음을 전제합니다. 또한, 각 단어 간 의존 또는 수식 관계를 파악하여 문장 구조를 분석하는 방법으로 이를 화살표를 이용하여 표기할 수 있습니다. 화살표를 그리는 방식은 다양할 수 있지만, 해당 강의에서는 수식 받는 단어를 head로 화살표의 시작 부분으로 했고, 수식하는 단어는 dependent라고 하여 화살표가 가리키는 곳으로 표기합니다. 정리하자면 dependent parsing의 목적은 개별 단어 간의 관계를 파악하여 화살표의 방향과, 라벨을 결정하는 것이 됩니다. 그 결과 output은 오른쪽의 트리 구조로 표현할 수 있습니다. Dependence parsing은 한국어처럼 자유 어순을 가지거나 문장 성분이 생략 가능한 언어에서 선호하지만, 영어권에서도 점차 dependency parsing에 대한 관심이 증가하고 있다고 합니다. 이번 시간에는 dependency parsing에 대해서 중점적으로 다루겠습니다.

1-3. Why do we need sentence structure?

그렇다면 이러한 dependency parsing을 이용하여 문장 구조를 분석해야 하는 이유는 무엇일까요? 이에 관련하여 해당 강의에서는 2가지 ambiguity에 대하여 언급합니다.

Phrase Attachment Ambiguity

위의 두 개의 문장은 같은 문장이지만 빨간 괄호가 쳐진 from space가 어떤 단어를 수식하는지에 따라 의미가 달라집니다. 위의 문장에서는 from space가 observe를 수식하며 과학자들은 우주에서 고래를 관측했다는 뜻이 되지만, 반대로 아래의 문장에서는 from space가 whales를 수식하여 과학자들은 우주에서 온 고래를 관측했다는 의미가 됩니다. 이렇게 첫 번째 ambiguity는 phrase attachment ambiguity로 형용사구, 동사구, 전치사구 등이 어떤 단어를 수식하는지에 따라 의미가 달라지는 모호성을 말합니다.

Coordination Attachment Ambiguity

이와 달리 coordination scope ambiguity는 작용적 중의성으로 형용사구, 동사구, 전치사구 등의 구들이 어떤 단어를 수식하는지, 그 범위에 따라 달라지는 모호성을 말합니다. 위 두 문장도 역시나 같은 문장이지만, Fred Gregory를 수식하는 범위에 따라서 의미가 변하는 것을 볼 수 있습니다. 위의 방식처럼 shuttle veteran과 longtime NASA executive를 묶어서 생각하면 이 두 개가 모두 Fred Gregory에 해당이 되게 되고, shuttle veteran과 longtime NASA executive를 따로 나누어 후자만 Fred Gregory를 수식한다면 이사로 임명된 사람이 2명이게 됩니다.

이렇게 인간은 복잡한 아이디어에 대한 소통을 할 때, 복잡한 의미를 내포하기 위해 많은 단어들을 함께 사용합니다. 따라서 듣는 이는 문장 안의 어떠한 객체가 어느 부분과 연관성이 있는지 생각하면서 들어야하는데, 모델도 마찬가지로 말을 정확히 알아듣기 위해 문장의 구조를 이해할 필요성이 있습니다.

2. Dependency Grammar and Treebanks

2-1. Grammar and Structure

그럼 이제 dependency parsing의 문법과 구조 등에 대해 더 자세히 알아보겠습니다.

• dependency parsing은 sequence 형태와 tree 형태로 표현할 수 있으며, 이 둘의 결과는 동일한 output을 가져야 함
• 가상의 노드 ROOT를 문장의 맨 앞에 추가하여 모든 성분의 최종 head를 ROOT로 설정
  → ROOT는 모든 단어가 최소 1개 노드의 dependent가 되어 의존 관계를 가지도록 함
• 화살표는 수식을 하는 head에서 수식을 받는 dependent로 향하며, dependency의 문법적 관계를 label로 표현
• 화살표는 순환하지 않으며, 중복 관계는 형성되지 않음

2-2. Dependency Conditioning Preferences

다음은 dependency parsing의 전형적 특징으로, 항상 참인 것은 아니지만 대개의 경우 해당되는 특징이라고 보시면 되겠습니다.

• Bilexical affinities: 두 단어 사이의 실제 의미가 드러나는 관계
  ex) discussion - issues
• Dependency distance: dependency의 거리는 주로 가까운 위치에서 dependent 관계 형성
• Intervening material: 동사나 구두점을 사이에 두고 dependency 관계가 잘 형성되지는 않음
• Valency of heads: head가 문장 내에서 결합하는 문장 구성 성분의 수 고려
  ex) was completed는 다른 문장 성분을 꼭 필요로 함

3. Transition-based Dependency Parsing

3-1. Methods of Dependency Parsing

1. Dynamic programming: 동적 계획법을 사용하여 긴 문장을 여러 개로 나누어 하위 문자열에 대한 트리를 만들고 최종적으로 다시 합치는 방식으로 parsing 진행
2. Graph algorithms: 가능한 의존 관계를 모두 고려한 뒤 가장 확률이 높은 구문분석 트리 선택
3. Constraint Satisfaction: 문법적 제한 조건을 초기에 설정하고, 조건을 만족한 경우만 남기고 나머지는 제거하여 조건을 만족하는 단어만 parsing
4. Transition-based parsing: 두 단어의 의존 여부를 순서대로 결정하여 점진적으로 구문분석 트리 구성

Dependency parsing에 대해, 강의에서는 위와 같이 총 4가지 방법이 있다고 소개합니다. 그 중에 해당 발표에서는 Transition-based parsing에 대하여 구체적으로 다루겠습니다.

3-2. Transition-based Parsing

Transition-based parsing의 특징은 다음과 같습니다.

• 두 단어의 의존 여부를 차례대로 결정하여 점진적으로 dependency structure를 구성하고 구문분석 트리 구성
• 문장에 존재하는 sequence를 차례대로 입력하여 각 단어 사이에 존재하는 dependency를 결정
  : Deterministic Dependency Parsing, 단어 간 dependency의 classification과 유사
• 문장의 sequence라는 단방향 분석이 이루어지기 때문에 모든 경우를 고려할 수는 없음
• Graph-based 방법론에 비해 상대적으로 분석 속도는 빠르지만 낮은 정확도
  : graph-based 방법론은 모든 경우를 고려하여 그 중에 가장 좋은 것을 고르기 때문에 속도는 느리지만 정확도가 높은 반면, transition-based는 점진적으로 트리를 만들어내므로 속도는 빠르지만 정확도는 상대적으로 낮은 방법으로 알려져있었음
• 그러나 2014년 dense feature를 사용한 neural network 기반 transition-based parser가 제안되며 속도와 성능을 모두 향상시켰고, 현재는 다시 neural network 기반 Graph-based parser가 가장 높은 성능 기록

3-3. Transition-based Parsing Process

그럼 예를 들어 transition-based parsing의 과정을 살펴보겠습니다. 우선 아래 그림처럼 Buffer, Stack, Set of Arcs라는 3가지 자료구조로 이루어져있고, 현재 상태인 initial state c는 이 자료구조들에 의해 결정됩니다. Input sentence의 단어 토큰들은 입력되어 이 자료구조들을 왔다갔다하며 트리를 구성하게 됩니다.

⓪ initial state에서는 John hit the ball이라는 문장이 토큰화되어 buffer에 입력됨

stack에는 root만 있는 모습을 확인할 수 있습니다. 그리고 parsing의 결과물인 화살표 방향이나 라벨은 set of arcs는 공집합인 상태입니다. 그리고 parsing을 하기 위해 decision을 내려야하는데, 모든 decision은 state c를 input으로 하는 함수 f(c)에 의해 이루어집니다. Buffer, stack, set of arcs로 이루어진 state는 임베딩 과정을 거칠 것이고, 임베딩된 벡터 c를 f라는 함수에 넣어서 이 함수가 dependency를 결정하는 구조로 dependency parsing을 하게 됩니다. 이 때 f라는 함수는 SVM이 될 수도 있고 신경망이 될 수도 있는 등 다양한 모델을 활용할 수 있습니다. 이때 내릴 수 있는 decision의 종류는 다음과 같습니다.

• Shift: BUFFER에서 STACK으로 이동
• Right-Arc: 오른쪽으로 dependency
• Left-Arc: 왼쪽으로 dependency

① (Shift) John이 BUFFER에서 STACK으로 이동

따라서 예시 문장 John hit the ball을 input 문장으로 넣은 경우, John이 제일 첫번째 단어이기 때문에 BUFFER에서 STACK으로 이동합니다.

② (Shift) hit이 BUFFER에서 STACK으로 이동

BUFFER가 비워질 때까지 STACK 안에 있는 ROOT는 decision의 대상이 될 수 없습니다. 따라서 STACK 안의 John과 ROOT로는 의존 관계를 결정할 수 없으므로, hit도 shift 되어 BUFFER에서 STACK으로 이동합니다. 그럼 이제 f라는 함수가 c를 통해 decision을 내려서 STACK 안에 있는 John과 hit의 의존 관계를 결정합니다.

③ (Left-Arc) hit이 John을 수식하는 dependency 결정

이 때 Stack에 있는 Root, John, hit라는 state는 hit가 John을 수식하는 Left-Arc라는 decision이 내려지게 됩니다. 그리고 이 right-arc와 left-arc decision의 경우 stack의 top 1, 2의 단어를 대상으로 이루어지며, label의 유무에 따라 의사결정 경우의 수가 많이 달라집니다. 만약 label의 개수를 $N_l$개라고 한다면, label을 같이 예측할 경우 $2N_l+1$개의 의사결정 개수를 가지게 됩니다. 보통 $N_l$은 17이나 45가 된다고 하는데, 만약 라벨을 함께 예측할 경우에는 결국 c라는 state를 임베딩시켜서 함수 f가 결정하게 되는 것을 dependency parsing이라고 합니다.

④ (Shift) the가 BUFFER에서 STACK으로 이동

이렇게 arc 의사결정이 내려지게 되면, 수식을 하는 단어인 dependent는 STACK에서 지워집니다. 따라서 John은 STACK에서 지워지게 되고, decision을 내린 hit에서 John으로 가는 left-arc 의사결정이 A라는 집합에 들어가게 됩니다. 그럼 STACK에는 다시 ROOT와 hit 밖에 남지 않게 되기 때문에, 이러한 ROOT, hit라는 state가 shift라는 decision을 내리게 하여 the가 BUFFER에서 STACK으로 이동하는 shift 의사결정이 내려집니다.

⑤ (Shift) ball이 BUFFER에서 STACK으로 이동

그러나 현재 상황에서 의사결정을 내릴 때, STACK에 있는 hit과 the는 서로 직접적 의존 관계가 없으므로 shift를 한 번 더 하여 ball이 BUFFER에서 STACK으로 이동하게 됩니다.

⑥ (Left-Arc) ball이 the를 수식하는 dependency 결정

그렇게 STACK으로 the가 shift 되어 들어오게 되고, f(c)는 이에 대하여 left-arc 의사결정을 내립니다. 그 뒤, 수식을 하는 단어인 the는 지워지게 되고 ball에서 the로 가는 arc가 Set of Arcs 집합에 추가되었습니다.

⑦ (Right-Arc) hit이 ball을 수식하는 dependency 결정

그럼 이제 STACK에 hit와 ball이 남게 되었는데, hit에서 ball로 가는 right-arc가 결정됩니다. 그렇게 수식을 받는 ball은 지워지고, hit에서 ball로 가는 arc가 추가됩니다.

⑧ (Right-Arc) root가 hit을 수식하는 dependency 결정

마지막으로, 이제 STACK에는 root와 hit만 남게 되었습니다. Buffer가 empty 상태이므로 root에서 hit로 가는 right-arc 결정을 할 수 있습니다. 그래서 최종 output이 Set of Arcs 집합에 담기고, 이를 트리 형태로 표현하게 되면 오른쪽과 같이 나오게 됩니다. 그리고 final state를 보시면 STACK에는 ROOT만 남게 되고, BUFFER는 비어있고, Set of Arcs는 꽉 차있는 형태로 아웃풋이 이루어지게 됩니다.

지금까지 decision process를 통해서 transition-based dependency parsing이 진행되는 과정을 살펴보았습니다. 그럼 하나 더 짚고 넘어가야 할 것이 있는데요, state c는 어떻게 임베딩을 하고, f 함수는 c를 받아 어떻게 의사결정을 내릴까요?

3-4. Conventional Feature Representation

State Embedding

우선, 이 과정에서 state를 모델이 입력으로 받기 위한 c의 임베딩 과정에 대해 알아보겠습니다. 이를 위해서 notation부터 예시를 중심으로 알아보겠습니다.

그림에서 왼쪽에 있는 state c를 보시면 parsing이 진행 중인 상태로, hit에서 John으로 가는 left-arc만 이루어진 상황인 것을 알 수 있습니다. 또한 추가적으로 POS Tag가 들어가있는데, dependency parsing에서는 이 POS Tag를 유용하게 사용한다고 합니다. 그래서 Pos tagging이 된 상태에서 parsing을 하고 있다고 보시면 되겠습니다.

Notations 아래 있는 예시를 보면, $s_1\cdot w$으로, $s_1$은 STACK의 첫번째 단어, $w$는 단어를 의미하기 때문에 STACK의 첫번째 단어인 the를 그대로 쓰면 됩니다. 그리고 세번째 $lc(s2)\cdot w$의 경우에는 $s2$는 STACK의 두번째 단어, hit고 $lc$는 현재 상황에서의 left-child입니다. 그래서 Parsing Tree를 보시면 hit의 left-child가 John이기 때문에 John의 $w$, 단어를 가져오라고 했으므로 John을 그대로 써주시면 됩니다. 마지막 예시 $rc(s_2)\cdot t$에서는 stack 2인 hit의 right-child지만 현재 상태에서는 hit의 right-child가 결정되지 않았기 때문에 NULL이라고 합니다.

Feature Selection

그럼 앞서 notation을 적용한 것을 이용하여 feature selection을 해보도록 하겠습니다.

Conventional한 방식에서는 feature를 Indicator Feature로 표현하여, 각각의 차원들이 주어진 조건을 만족하면 1, 그렇지 않으면 0으로 표현됩니다. 예를 들어 현재 상태에서는 $s1$, STACK의 첫번째 단어가 the고, 태그가 DT면 1, 아니면 0으로 표현을 하는 것이 해당 차원의 feature가 되겠습니다. 이러한 방식으로 밑으로 쭉 10의 6승에서 10의 7승 정도까지의 벡터를 표현하는 것이 conventional dependency feature입니다. 다음으로 stack 2의 단어가 hit이고, tag가 VBD가 맞는데, BUFFER의 첫번째 단어 태그가 DT가 아니라 NN이기 때문에 False가 되어 0이 됩니다. 세번째 예시에서는 stack 2의 단어가 hit인데, hit의 left-child가 John인 것은 맞지만, stack 1의 the는 현재 parsing tree에서 child가 없습니다. 따라서 NULL로 표현해주는 것이 맞기 때문에 0이 들어가게 됩니다.

다음은 이러한 방식의 transition-based dependency parsing의 feature selection에 해당하는 특징들입니다.

• binary & sparse representation
• 일반적으로 1~3개 요소가 결합된 indicator features
• feature 연산의 비용 높음
• 단어나 POS Tag의 유사도 등 의미 반영 불가능

이렇게 계속해서 True인지 False인지 따져본 뒤, 0 또는 1의 binary하고 sparse한 representation으로 표현을 하는 것이 conventional feature representation이라고 보시면 되고, 일반적으로 1개에서 3개의 요소가 결합된 indicator feature 입니다. 이러한 과정은 굉장히 오래 걸리기 때문에 parsing의 소요 시간 중에 95% 이상을 feature 연산이 차지합니다. 또한 True와 False로만 표현하기 때문에 단어 간의 유사도나, pos tag 간의 유사도를 반영할 수 없습니다.

지금까지 전통적인 방법으로 state c를 임베딩하기 위해 indicator feature를 활용해서 binary하고 sparse한 feature로 표현하였고, f라는 함수가 c를 받아서 shift, left-arc, right-arc의 의사결정을 하는 것이 conventional한 방식의 transition-based dependency parsing 이었습니다.

4. Neural Dependency Parsing

앞서 말씀드린 전통적인 dependency parsing의 단점을 보완하기 위해, 이 강의를 하신 Manning 교수님께서는 이전의 방식처럼 feature computing을 하지 않고 STACK과 BUFFER configuration에 neural network를 직접 사용한 neural dependency parsing을 제안하셨습니다.

4-1. Neural Dependency Parser

Neural dependency parser는 모델 구조는 기본적인 feed forward network와 닮았으나, 이 밑에서 feature representation하는 과정과 hidden layer의 활성화 함수에서 차별점이 있습니다.

4-2. Feature Selection

먼저 input lyaer에서 feature를 selection하는 과정을 살펴보겠습니다. Feature selection은 앞서 다룬 notation을 통해 이루어지고, 현재 state에서 각각의 feature template을 본 뒤에, 태그들이 어떤 것들인지 보고 가져오게 됩니다.

우선, words feature로 들어가는 데이터는 총 18개입니다. 가장 먼저 STACK과 BUFFER에서 순서대로 3개씩 가져오고, 다음으로는 STACK top 1, 2 단어의 첫번째와 두번째 오른쪽, 왼쪽 자식 단어를 가져옵니다. 이 말은 가장 왼쪽과 그다음 왼쪽, 가장 오른쪽과 그다음 오른쪽을 각각 가져오라는 뜻으로 총 8개의 토큰을 가져오게 됩니다. 다음으로는 한 단계 더 내려가서 left of left child와 right of right child 단어를 총 4개 가져옵니다. 그 옆에 POS tags feature로 들어가게 되는 데이터는 words feature에서 들어가는 데이터의 태그를 의미하기 때문에 마찬가지로 18개가 됩니다. 마지막으로 arc labels에서는 STACK과 BUFFER의 TOP 3 단어 6개를 제외한 12개의 dependent 관계를 표시하는 라벨 데이터로 구성되게 됩니다. 이렇게 총 48개의 feature를 가지게 됩니다.

4-3. One-hot Representation

다음으로 이 피쳐들을 One-hot representation으로 표현합니다. word 수준에서 18개였으므로 $18\times vocabulary \ size$만큼의 one-hot matrix가 생성되고, POS tag도 18개이므로 $18 \times POS \ tag$의 개수만큼 행렬이 만들어집니다. 마지막으로 arc 라벨은 12개를 가져왔으므로 $12 \times N_l$개 만큼의 one-hot representation이 만들어집니다.

4-4. Feature Embedding

다음으로 word embedding matrix를 참고하여 해당 토큰의 벡터를 가져와 임베딩을 진행합니다. 그러면 각 토큰별로 벡터가 있는 상태에서 모두 concatenate로 결합한 뒤, 이를 word feature로 삼는 것이 임베딩 과정이 됩니다.

4-5. Hidden Layer

그 뒤로 hidden layer에서는 embedding vector와 weight matrix를 곱한 뒤 bias vector를 더하는 일반적인 feed forward 과정이 이루어집니다. 그러나 ReLU나 Sigmoid 같은 일반적 활성화 함수를 쓰지 않고 cube function을 사용합니다. cube function에서 아래 수식처럼 세제곱을 해주면 x의 피쳐들이 곱해지는 형태가 상호작용하는 것으로 표현되기 때문에 word, POS tag, arc-label 간의 상호작용을 잘 반영할 수 있다고 합니다.

4-6. Output Layer

마지막으로 hidden layer를 거친 hidden vector를 softmax layer에 넣어서 의사결정을 합니다. 이때 linear projection을 한 번 더하고 softmax를 사용하여 shift, left-arc, right-arc 중 가장 확률이 높은 것을 출력합니다.

4-7. Evaluation Measures

이제 실험결과와 평가에 대해 말씀드리고 마무리하겠습니다. 이전에 언급한대로, 평가는 arc 방향만 예측하는 Unlabeled Attachment Score(UAS)와 arc 방향과 label을 모두 예측하는 Labeled Attachment Score(LAS) 두 가지로 이루어졌습니다. 사용한 데이터셋은 English Penn Treebank Dataset이고, 아래 표를 보시면 가장 위에 있는 MaltParser가 앞에 나온 전통적인 dependency parsing인, indicator feature를 활용한 transition-based parser 입니다. 그 뒤는 graph based parser, 그리고 neural dependency parser로, 속도면에서는 여전히 transition parser가 높은 반면 graph based parser는 이보다는 좋은 성능을 보이지만 그 중에서도 neural based parser가 성능이 graph와 비슷하면서도 빠른 속도를 보여주었습니다.

References

• CS224 Winter 2019: Natural Language Processing with Deep Learning
• https://velog.io/@tobigs-text1314/CS224n-Lecture-3-Word-Window-Classification-Neural-Networks-and-Matrix-Calculus
• KoreaUniv DSBA, [DSBA]CS224N-05.Linguistic Structure: Dependency Parsing, 노영빈
• A Fast and Accurate Dependency Parser using Neural Networks, Chen & Manning, 2014