[CS224N] Lecture 5 - Dependency Parsing

Sentence Structure

• 문장의 구조를 파악하는 방법은 총 2가지가 있다.
  1. Phrase-structure grammar(context-free grammar, CFG)
  2. dependency structure grammar
• 문장 구조를 제대로 파악해야지 문장의 의미를 정확하게 이해할 수 있다.

Phrase-structure grammar

• 문장을 unit으로 구성
  • 각 unit 들을 progressively nest 

Phrase-structure grammar

Dependency structure grammar

• 한 단어가 어떤 다른 단어에 의존적인지 나타내는 방식

dependency structure grammar

Treebank

• 사람이 직접 문장들의 dependency를 파악해서 dependency structure 를 구성한 데이터셋
• 영어 뿐만 아니라, 다양한 언어들에 대해서 생성

Dependency parser

• 다양한 method 가 존재한다.
  1. dynamic programming
  2. graph algorithm
  3. constraint satisfaction
  4. transition-based parsing

Greedy transition-based parsing

• 초기 상태
  • [root] 만 요소로 보유하고 있는 stack
  • 문장 전체를 구성하는 단어들로 구성된 buffer
  • 결과를 저장하는 A
• example : "I ate fish" 라는 문장으로 transition-based parsing 수행

• 종료 조건
  • stack 에 [root] 만 원소로 남는 경우
  • buffer 가 비어있는 경우
• 다양한 규칙을 기반으로 dependency 를 찾아내는데, 이러한 규칙들에는 문제가 있다.
  • 종류가 정말 많지만, 실제로 사용되는 것은 매우 적다. (sparse)
  • 관계를 계산하는데 비용이 많이 든다.
  • 그러므로, neural dependency parser를 사용해보자!

Neural Dependency Parser

• neural net 을 이용해서 문장의 dependency 를 파악하는 방법
• Maltparser
  • 다음 action(shift, left/right arc)을 어떻게 취해야 하는지 softmax classifier에 의해서 결정한다.
  • state-of-art 의 성능을 내지는 못했지만, linear time parsing을 제공한다는 점에서 의미가 있다.
• C&M parser
  • Maltparser 와 유사항 방식으로 동작한다.
  • 단어와 함께, POS(Part-of-Speech), dependency-label을 input 으로 제공한다.
  • 좋은 성능과 빠른 처리 속도를 제공한다.

• neural dependency parser evaluation
  1. unlabeled attachment score (UAS) : arc(dependency) 만 일치하는지 확인한다. label은 별도로 확인하지 않는다.
  2. labeled attachment score (LAS) : arc 와 label 모두 일치하는지 확인한다.