Stanford CS224N - NLP w/ DL | Winter 2021 | Lecture 4 - Syntactic Structure and Dependency Parsing

[ 강의 키워드 ]

Syntatic Structure : "구문 구조", 문장을 하위구조로 쪼개어 보는 것

Constituency Structure : "구성 구조", 구문구조 방법중 하나

Dependency Structure : "의존 구조", 구문구조 방법중 하나

Universial dependencies : 위의 Constituency Structure 와 Dependency Structure 를 동시에 사용하는 구조

Dependency Grammar : 말그대로 의존구조의 문법

Treebank : 구문 분석한것을 tree 구조로 저장해놓은 것(사이트)

Parser : 구문 분석기

Dependency Parser : 의존구조 분석기 (강의 뒷부분 메인 주제)

Greedy transition-based parsing : dependency parser의 알고리즘 중 하나.

 

[ 강의 순서 ]

1. Syntatic Structure <구문구조>

    1) Constituency Structure <구성구조>

    2) Dependency Structure <의존구조>

    - 왜 sentence structure가 필요할까?

    - dependency paths가 문장을 의미단위로 분석하기에 적합하다.

2. Dependency Grammar & Treebanks

    - Dependency Grammar and Dependency Structure

    - The rise of annotated data & Universal Dependencies treebank

    - The rise of annotated data

    - Dependency conditioning preferences

    - Dependency Parsing

    - Projectivity

3. Methods of Dependency Parsing (Transition-based dependency parsing)

    - How to make dependency parser?

    - Greedy transition-based parsing

         - Example

    - MaltParser (2008)

         - How do you choose next action in MaltParser?

    - Conventional Feature Representation

    - Evaluation of Dependency Parsing: (labeled) dependency accuracy

4. Neural dependency parsing  <다음시간에!>

 

---

 

강의에 들어가기에 앞서, cs224n 2021 winter 4강은, 문장을 구문분석하는 방법들에 대해 설명을 한다.

그렇다면 왜 NLP 를 잘하기위해 구문분석을 알아야하는가?

 

사람들이 복잡한 Idea를 소통할 때, 단어들이 큰 unit으로 합쳐진 문장을 이용한다.

따라서, 모델이 문장들을 깊게 이해하기 위해선, 구문분석을 해야한다. 라고 강의에선 설명한다.

 

1. Syntactic Structures

그렇다면, 어떻게 구문분석을 하는게 현명한 구문분석방법일까?

강의에서는 두가지 구문분석(Syntactic Parsing) 방식을 소개한다.

 

1.1) Constituency Structure

첫번째 방식은, context-free grammars(CFGs) 로,

강의에서는 “Phrase strcture organizes words into nested constituents” 라고 설명하였다. 이는,

단어간 종속관계에 상관없이 문장을 마치 캡슐화된 객체처럼(?) 구분한다는 의미이다. 예시를 보면 더 쉽게 이해할 수 있다.

 

the cuddly cat by the door

 

을 해당 방식으로 분석하면,

 

the cuddly cat by the door

{the cuddly cat}, {by the door}

{the, cuddly, cat}, {by, the, door}

 

로 분석할 수 있다. 앞서 말한것처럼 문장이 점점 세부적으로 분해되었다.

 

1.2) Dependency Structure

두번째 방식은, 의존구문 분석방식으로, 

다음과같이, 단어들이 서로 문맥에 따라 parent와 child 관계를 가지게 된다.

 

 

왜 구문분석이 필요할까?

맨 처음에 언급했듯, sentence structure을 알아야하는 더 자세한 이유는 언어의 모호성에 있다.

<아래의 5가지 예시는 서로다른 모호성의 예시로, 간단히 읽고 념겨도 될 것 같습니다.>

1) Prepositional phrase attachment ambiguity

출처, 스탠퍼드 cs224n 강의, Youtube

다음 헤드라인은 두가지로 모호하게 해석될 여지가 있다.

(정확한 번역일진 몰라서, 문장은 모호성을 가진다는것이 핵심이었습니다.)

 

1. San Jose라는 경찰들이, 사람을 칼로 죽였다.

2. 칼을 가진 사람이, San Jose cops 를 죽였다.

 

모델이 매번 이런 모호성을 완벽히 분석하기란 불가능이다. 

2) PP attachment ambiguities multiply

출처, 스탠퍼드 cs224n 강의, Youtube

PP (Prepositional Phrase) : 전치사 + 명사 구

또 다른 종류의 모호성이다.

expoential 하게 어떤 ambiguity 가 증가한다.

3) Coordination scope ambiguity

무엇이 무엇을 꾸미는지 명확하지 않은 매우 흔한 모호성의 경우라고 설명한다.

 

4) Adjectival/Adverbial Modifier Ambiguity

또다른 모호성의 경우이다.

 

5) Verb Pharse(VP) attachment ambiguity

또다른 모호성의 경우이다.

이처럼, 사람 언어의 structure 은 복잡하고 모호하다고 설명한다.

 

Dependency paths help extract semantic interpretation

dependency structure을 그렇다면, 어떻게 표현할 수 있을까? 위에서 봐서 직관적으로 알듯, 아래 예시의 tree 구조처럼 표현할 수 있다. 아래의 예시는 문장이 아닌, 단백질구조의 계층관계를 그래프로 나타낸 것 이다. 그림만 보고 넘어가도 좋다.

** simple practical example: extracting protein-protein interpretation **

dependency path 의 예시이다. 이처럼 dependency structure을 표현할 수 있다.

protein-protein interpretation이 뭔지 궁금해서 찾아본 위의 예시에서 말하는 단백질 구조이다.

 

 

 

2. Dependency Grammar & Treebank

앞서 구문을 분석하는 방법과 표현하는 방법, 왜 구문분석이 필요한지에 대해 설명을 쭉 하셨고, 이런 구분분석된 데이터들에 대해 다음 설명을 하신다.

구문을 분석한 annotated data들이 많이 생기기 시작했다고 말씀하시고, 나의 해석이 맞다면 교수님께서 Ph.D 를 하시면서 처음으로 하셨던 일이 종이에 구문들을 분석하시는 일이라고.. 말씀하신다...

문장내 종속관계를 Graph로 표현할 수 있다.

이러한 문장을 그래프로 표현하는 방식은 역사가 아주 깊다고 말씀하신다.

이처럼, 앞서 말했던 두가지 구문분석방법중 dependency structure(위의 그래프 방식)은 오래된 역사가 깊은 방식이고, Constituency Structure은 비교적 현대에 등장한 방법이라고 설명하신다.

(나는 여기서, 더 디테일하게 문장의 관계를 표현하는 방식이 더 옛날방식이라는것이 특이하다고 생각했다.)

 

Dependency Grammar and Dependency Structure

Dependency Grammar 에선, 화살표의 tail은 상위구조, head는 하위구조를 의미한다.

 

The rise of annotated data & Universal Dependencies tree bank

많은 사람들이 parser을 만들려 했다.

treebank는 http://universaldependencies.org/ 에서 공개데이터로 공유되는 parsed sentencies라고 이해했다.

해당 링크에 들어가보니, KAIST에서 2018년에 만들어놓은 treebank가 있었다. 궁금해서 열어보았다.

The rise of annotated data

인력으로 treebank를 만드는 것은 너무 값비싸다. 하지만 treebank는 재사용성이 놓고, NLP system가 제대로 parse 했는지 evaluate 할 수 있는 좋은 도구이다.

Dependency conditioning Preferences

dependency parsing 의 다양한 특징들을 설명한다.

Projectivity 투사성

From 이 문장에서 도치되어있는데, 이런 경우를 non-projective 한 경우라고 말한다. 어디에 쓰인다는거고, 왜 만든 개념인진 아직 모르겠다.

 

3. Methods of Dependency Parsing (Transition-based dependency parsing)

그렇다면, dependency parser을 어떻게 만들까?

 

1. dynamic programming으로(1996), 경우의수 때려박아서 만들어볼 수 있었지만, time cost가 비쌌다.
2. 그래프 알고리즘의 사용
   • 문장으로 minimum spanning tree 를 만든다.
   • 그리고 dependencies 를 ML classifier 을 사용해서 점수메겼다.
   • GNN-parser(2017) : 성공적!!
3. Dependency의 제약을 느슨하게 만들어도 봄.
4. **transition step을 reduce한다.**⭐
   • MaltParser(2008) : greedy transition-based parsing 에서 사용하는 ML classifier 알고리즘. 아래에 나온다.

 

Greedy transition-based parsing (Nivre 2003)

심플한 greedy discriminative dependency parser이다.

추상적인 알고리즘은 다음과 같다. (예시로 이해하는게 빠르다)

https://www.youtube.com/watch?v=PSGIodTN3KE&list=PLoROMvodv4rOSH4v6133s9LFPRHjEmbmJ&index=4 강의링크, 해당 강의 1:06:00 쯤부터 설명한다. 차근차근 들으니 이해하기 쉬운 개념이었다.

그래도, 대강 설명하자면 동작은 다음과 같다.

개인 Notion에 정리했던 내용입니다.

아래의 예제로 이해하는것이 빠르다. (간단하다 보기완 다르게)

Example : simple transition-based dependency parser

이처럼, [root]가 stack에 유일하게 남으면 종료된다.

root 까지, 양옆을 단어순으로 reduce 시켜주는 알고리즘으로, 이 transition machine으로 문장을 parsing up 할 수 있다.

그렇다면, 의문은, 언제 Left Arc를 사용하고 언제 Right Arc를 사용하고 언제 Shift를 사용한다는 것 일까?

그건은 학습된 ML classifier을 사용한다. 강의에서는 MaltParser(2008)을 사용한다고 설명한다. (구현이 과제이다. 과제 코드는 추후에 또 올릴 예정)

 

MaltParser

앞서 말한것처럼, 알고리즘에서 left arc를 할것인지, right arc를 할것인지 고르는 classifier 이다.

80, 90년대에는 모든 path를 일일히 explore 했지만 당연히 복잡도는 아주아주 높았고,

2000년도 초반에는 ML로 SVM등의 classifier을 훈련하여 다음 action을 선택하도록 하였다.

그렇게 복잡도는 exponential 에서 linear로 내려왔다고 설명한다.

 

Conventional Feature Representation

기존의 Feature Representation을 설명하시는데, 이는 Nivre 가 만든 dependency parser이다. 이것의  Neural form 은 다음에 설명한다고 말씀하신다.

 

symbolic features of this configuration 을 사용함으로 구현했다.

어떤 symbolic features를 사용했는지 → 저 indicator features 를 사용해, subset(보통 1-3개의 원소가진)을 pick한다.

<너무 추상적이어서 pass...>

 

Evaluation of Dependency Parsing: (labeled) dependency accuracy

그렇다면, 이렇게 공들여 만든 parser을 어떻게 evaluate 할 것인지 설명한다.

결론은, labeled sentencies 를 구해와서, UAS와 LAS라는 accuracy 를 변형한 score을 구해보면 된다고 한다.

UAS(Unlabeled Accuracy Score) : 뭐가 subject, object 인지 분석 안한 상태의 accuracy

LAS(Labeled Accuracy Score) : 분석된거까지 고려한 accuracy

 

4. Neural dependency parsing

시간이 모자라는 관계로, 다음 5강에서 다룬다고 말씀하셨다.

 

 

 

 

강의의 6-70%만을 정확하게 알아들은 것 같은데, 그럼에도 아직은 내용이 많이 어렵진 않아서 그런가, 교수님이 방긋?웃으시면서 설명을 해주셔서 그런가 나름 듣기 편했던 것 같다ㅎㅎ 

 

읽어주셔서 감사합니다