Stanford CS224N - Lecture 4. Syntactic Structure and Dependency Parsing

본 글은 Stanford CS224N: NLP with Deep Learning | Winter 2021 내용을 기반으로 합니다.

강의를 듣고 정리한 글로 혹시 잘못된 부분이나 수정할 부분이 있다면 댓글로 알려주시면 감사하겠습니다.

---

강의 순서

1. Syntactic Structure: Consistency and Dependency

2. Dependency Grammar and Treebanks

3. Transition-based dependency parsing

4. Neural dependency parsing

1. Syntactic Structure: Consistency and Dependency

NLP 모델이 문장을 깊게 이해하기 위해서 구문 구조를 분석하는 것이 필요하다.

구문 구조를 분석하는 것에는 두 가지 방법이 있다.

 

1) Consistency structure

 

context-free grammars(CFGs)로 문장에서 각각의 단어는 문법적 역할을 한다. 단어들의 조합으로 구문을 구성하고 구문들 간의 조합으로 더 큰 구문을 구성한다.

Starting unit: words
{the}, {cat}, {cuddly}, {by}, {door}

Words combine into phrases
{the cuddly cat}, {by the door}

Phrases can combine into bigger phrases
{the cuddly cat by the door}

 

2) Dependency structure

 

의존 구문 구조 분석 방법으로 한 단어와 다른 단어 간의 의존적인 관계를 파악하는 방법이다.

 

위와 같은 문장이 있을 때, Look은 crate를 수식하고 crate는 in과 the, large를 수식한다. 그리고 kitchen은 in과 the를 수식하고 door은 by와 the를 수식한다. 그리고 crate는 kitchen과 door를 수식한다.

 

문장의 구조를 왜 알아야 할까?

 

인간은 단어를 통해서 매우 복잡한 아이디어를 구성하고 전달할 수 있다. 마치, 우리가 정말 복잡한 아이디어를 한 단어로 전달할 수 없는 것처럼 말이다. 그래서 우리는 언어의 문법으로 단어들을 더 큰 단위로 묶어서 복잡한 의미를 전달한다. 따라서, 문장의 의미를 이해할 수 있는 신경망 모델을 만들고 싶다면, 모델들은 문장 구조를 이해해야만 언어를 올바르게 해석할 수 있다.

 

Prepositional phrase attachment ambiguity

 

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

San Jose cops kill man with knife
Scientists count whales from space.

 

첫 번째 문장을 보면 경찰이 칼을 든 남자를 죽인것인지 칼로 남자를 죽인것인지 문장의 뜻이 모호하다.

두 번째 문장은 과학자들이 우주에서 고래들을 센건지 우주에 있는 고래들을 센건지 문장의 뜻이 모호하다.

 

위 예제들 이외에도 여러 가지 문장의 모호성이 존재할 수 있다.

 

그렇다면 이러한 dependency structure을 어떻게 표현할 수 있을까?

위 예시처럼 트리구조로 표현할 수 있다.

2. Dependency Grammar and Dependency Structure

이전까지는 구문 구조를 분석하는 방법과 표현하는 방법, 왜 구문 구조를 분석해야하는 지 배웠다. 다음은 구문 구조가 분석된 단어들을 이용해 tree 형태로 표현된 dependency 문법과 구조를 보여준다.

 

 

"treebank"는 구문 분석이나 언어학적 정보를 포함하는 주석이 달린 텍스트의 모음이다. 이 주석은 주로 문장의 구조를 나타내는 데 사용되는 구문 트리의 형태로 이루어져 있다.

 

treebank의 장점

- 재사용이 가능하다

- 커버할 수 있는 범위가 넓다

- 문장 구조 분석을 통해 통계 정보를 얻을 수 있고 이를 활용하기 좋다

- NLP 평가에 사용될 수 있다

3. Transition-based dependency parsing

Dependecy parsing의 방법은 4가지가 있다.

• Dynamic programming : O(n^3) 차원으로 비효율적
• Graph algorithms : 그래프로 표현하여 neural graph-based parser에서 성공적
• Constraint Satisfaction 
• Transition-based pasing or deterministic dependency parsing

Greedy transition-based parsing

 

parsing 과정은 buffer, stack, Set of Arcs라는 3가지 구조를 가지고 있다. stack은 현재 처리할 단어가 있는 곳이고 buffer는 아직 처리되지 않은 단어들이 있는곳이고, Set of Arcs에는 parsing의 결과물이 담기게 된다. parsing에는 3가지 decision이 존재한다.

1. shift : Buffer의 토큰이 stack으로 이동
2. Right-Arc : stack에 있는 두 단어 중 오른쪽 단어를 지움
3. Left-Arc : stack에 있는 두 단어 중 왼쪽 단어를 지움

"I ate fish"라는 문장을 예시로 보면 다음과 같다.

 

검은색 테두리가 stack으로 현재 처리할 단어가 있는 곳이므로 처음에는 아무 것도 없다. 주황색 테두리가 buffer로 아직 처리되지 않은 단어들이 있는 곳이다. 처음 들어온 상태에서 stack에는 root밖에 없으므로 할 수 있는 decision은 shift이다. 그 후, I가 들어와도 분석할 구문이 없으므로 ate도 shift한다.

 

그 후, Left-Arc를 통해 I와 ate의 관계를 Arcs 집합(A)에 추가하고 dependent I를 제거한다. 그리고 다음 shift를 하여 fish를 stack으로 가져온다. 이 후 Right-Arc를 통해 ate에서 fish로의 관계를 Arcs 집합(A)에 추가하고 dependent fish를 제거한다. Right-Arc를 한 번 더해서 root와 ate의 관계를 Arcs 집합(A)에 추가하고 ate를 제거 후 종료 조건을 만족하므로 종료한다.

 

Evaluation of Dependency Parsing

 

각 단어의 왼쪽의 숫자는 단어가 의존하고 있는 단어의 index이고 UAS(Unlabelled Accuracy Score)는 index를 기준으로 한 accuracy이고 LAS(Labelled Accuracy Score)는 index와 품사를 잘 예측했는지에 대한 accuracy이다.