Dependency Parsing

fla1512·2022년 9월 28일

NLP

NLP Study

목록 보기

8/23

Dependency parsing 관련 논문: https://nlp.stanford.edu/pubs/emnlp2014-depparser.pdf

0. Sentence Structure

참고

문장의 구조를 파악하는 두 가지 방법
-> 문장의 의미를 정확하게 파악하기 위해, 정확한 문장 구조 파악은 중요하다

1. Phrase-structure grammar(context-free grammar, CFG)

문장을 unit으로 구성
CFG(Context Free Grammer, 문맥자유문법)
- 파싱의 툴로 사용되거나 텍스트 생성에 사용하는 방법

2. dependency structure grammar

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

1. Parsing

참고1 참고2 참고3

parsing(구문분석)
- 단어 그대로 문장을 쪼개서, 문법적인 구성이나 구문을 분석하는 과정
- input으로 문장을 넣고, output으로 구문분석 트리를 얻음
목적에 따라,
1. Constituency parsing(구성성분분석)
- 문법적으로 접근해 문장의 구성 요소를 파악하고 구조를 분석
- 텍스트를 반복적으로 하위 구문으로 분리
  2. Dependency parsing(의존구문분석)
- 단어 간의 의존 관계를 파악해 구조를 분석
- 개별 단어와 다른 단어들 사이의 관계를 고려해 연결함
- transition-based dependency parsing(전이 기반 의존 구문 분석)은 문장 길이가 선형적이어서 널리 사용(추후 소개)
구문 분석기는 순차적으로 단어를 읽어서 구문 구조에 결합시키려는 결정을 내린다

1.1 Constituency parsing(구성성분분석)

phrase structure로 문장을 중첩된 성분으로 나누어 분석하는 방법
구를 파악하며 분석
단어의 의미보다 문법을 이용
명사구 NP와 전치사구 PP로 나누어짐
최종적으로 각 단어가 가지는 문법적 의미까지 분해됨

2. Dependency parsing(의존구문분석)

가정: input 문장의 단어들 사이에 서로 영향 주는 관계가 있다
각 단어 간 의존, 수식 관계를 파악하며 문장 구조를 분석하는 방법(화살표로 표시)
- 수식 받는 단어: head
- 수식하는 단어: dependent
  -> 개별 단어 간의 관계를 파악해 화살표의 방향과 라벨을 결정하자
output은 트리 구조로 표현

2.1 dependency parsing이 왜 필요한가?

-> 문장의 구조적 모호성을 해결하고자 !
1. Phrase Attachment Ambiguity

어떤 단어를 수식하는지에 따라 의미가 달라지는 모호성
"from space"가 어떤 단어에 의해서 수식 받냐에 의해서 의미가 다름

2. Coordination Attachment Ambiguity

작용적 중의성으로, 구들이 어떤 단어를 수식하는지 범위에 따라 달라지는 모호성
수식하는 범위에 따라서 의미가 변하는 것

2.2 Dependency Grammar and Treebanks

1. Grammar and Structure

ROOT(가상노드)를 문장 맨 앞에 추가
- 최종 head를 ROOT로 설정해서 모든 단어가 1개의 의존관계를 가지도록 설정
Dependency Structure는 sequence 형태와 tree 형태로 표현 가능
- 결과는 동일한 output임
- 화살표는 head -> dependent로
  - 수식 관계인 화살표는 순환하지 않음(중복 관계 형성 X)

2. Dependency Conditioning Preferences

dependency parsing의 전형적 특징

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

2.3 Dependecy parsing의 방법

1. Dynamic programming

긴 문장이 있을 때, 해당 문장을 몇 개로 나누어 하위 문자열에 대한 하위 트리를 만들고 최종적으로 그것들을 다시 합치는 방법

2. Constraint Satisfaction

문법적 제한 조건을 초기에 설정
해당 조건을 만족하면 남기고, 만족하지 못하면 제거 -> 조건에 만족하는 단어들만 parsing하는 방법

3. Graph-based dependency parsing(그래프 기반 의존 구문 분석)

Dependency structure를 graph(directed tree)로 표현
- vertex: nodes(wi, i번째 단어)집합
- edges: arcs(wi, wj, I), I은 label: wi -> wj
가능한 의존 관계를 모두 고려한 후, 가장 확률이 높은 구문 분석 트리를 선택하는 방법
모든 경우의 수를 다 고려 -> 속도는 느림, 정확도는 높음
비결정적 의존 구문 분석(non-deterministic dependency parsing)에 해당
- 문장이 가질 수 있는 모든 의존트리 중에서 가장 높은 점수의 의존트리를 선택하는 방법

4. Transition-based dependency parsing(전이 기반 의존 구문 분석) 참고1 참고2

두 단어의 의존 여부를 차례대로 결정하면서 점진적으로 dependency structure를 구성하는 방법
결정적 의존 구문 분석(Deterministic dependecy parsing)에 해당
- 일종의 탐욕적 알고리즘(greedy algorithm)에 기반한 방법으로 지역적 학습 모델(locally training model)을 사용
  
  greedy algorithm: 선택의 순간마다 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
  => 의사결정을 현재 branch 에서 최고인 방법을 정하고 다음 branch로 넘어가는 것
- 문장에 존재하는 sequence를 차례대로 입력하면서 각 단어 사이에 존재하는 dependency를 결정하는 방법
- 문장의 sequence라는 한 방향으로 분석이 진행돼 모든 경우 고려X
  (분석 속도는 빠름, 정확도는 낮음)
진행 과정
- input으로 문장이 입력되면 세 구조를 거치면서 output이 도출
- BUFFER에 존재하는 문장의 토큰이 STACK으로 이동하면서 state를 형성하고 해당 state를 기반으로 Decision이라는 결정을 내린 후, output으로 결과가 이동
- 문장의 모든 단어는 STACK 혹은 BUFFER에 위치
3가지 구조: BUFFER, STACK, Set of Arcs
- BUFFER: 토크나이징한 단어들 중에 파싱을 기다리는 단어들을 담고 있는 공간
- STACK: 토크나이징한 단어들 중 파싱 작업을 진행 중인 단어들을 담는 공간
- Set of Arcs: parsing의 결과물이 담김
condition
1. start condition: stack에는 단어 한개(ROOT), buffer에는 모든 단어
  - 처음에 BUFFER에는 주어진 문장이 토큰 형태로 입력되어 있는 상태
    STACK에는 ROOT(가상노드)만 존재
2. end condition: stack에 단어 한 개, buffer는 비어있음
  - parsing의 종료 조건
    (1) stack에 ROOT만 원소로 남아 있는 경우
    (2) buffer가 비어있는 경우
행동
- shift: BUFFER에 있는 가장 앞의 단어 하나(top word)를 STACK의 top position(가장 오른쪽)으로 옮기는 행동
- reduce: STACK에 있는 단어에 대해 문법 규칙을 적용하고, 하나의 단어만 남기는 행동
  1. Left Reduce(left-arc): STACK의 top word를 화살표(<-)로 연결, 그리고 dependent를 제거
  2. Right Reduce(right-arc): STACK의 top word를 화살표(->)로 연결, 그리고 dependent를 제거
    => 3가지 행동 중 한 가지를 선택한다는 관점에서 classifier로도 해석 가능

arc-standard system(Nivre, 2004)

transition system 중 하나

configuration c = (s, b, A), stack s, a buffer b, and a set of dependency arcs A

initial configuration: s = [ROOT], b =[w1, . . . , wn], A = ∅

si (i = 1, 2, . . .) as the ith top element on the stack

bi (i = 1, 2, . . .) as the ith element on the buffer

예1) "I booked a flight from LA"

처음
shift
shift
Left-Reduce
Final state

예2) "I ate fish"
문제점
- 다양한 규칙을 기반으로 dependency를 찾는데, 한계가 있다
  1. 종류는 많은데 실제로 사용된 것은 적다
  2. 계산 비용이 크다
    -> 해결책: Neural Dependency Parser

2.4 Neural Dependency Parser

참고1 참고2

neural net 을 이용해서 문장의 dependency 를 파악하는 방법
기본적인 neural network 형태

2.4.1 Feature Selection

참고

sentence S는 다음의 subset을 포함한다
1. Sword: Vector representations for some of the words in S (and their dependents) at the top of the stack σ and buffer β.
2. Stag: Part-of-Speech (POS) tags for some of the words in S. POS
  tags comprise a small, discrete set: P = {NN, NNP, NNS, DT, J J, ...}
3. Slabel: The arc-labels for some of the words in S. The arc-labels
  comprise a small, discrete set, describing the dependency relation:
  L = {amod, tmod, nsubj, csubj, dobj, ...}
input layer에서 진행
현재 state에서 각각의 feature template을 본 후, 태그들이 어떤 것들인지 보고 가져오는 방법
1. word feature로 18개의 데이터가 들어감
2. The top 3 words on the stack and buffer: (s1,s2,s3, b1, b2, b3.)
  => 총 6개 가져옴
3. The first and second leftmost / rightmost children of the top two
  words on the stack: lc1(si),rc1(si), lc2(si),rc2(si), i = 1, 2
  => 총 8개의 토큰을 가져옴
4. The leftmost of leftmost / rightmost of rightmost children of the top two words on the stack: lc1(lc1(si)),rc1(rc1(si)), i = 1, 2.
  => 총 4개 가져옴
5. POS tags feature로 들어감(18개)
  - The corresponding POS tags for Stag (nt = 18)
  - POS tags feature에 들어가는 데이터 = word feature에서 들어가는 태그
6. arc labels에서 STACK과 BUFFER의 TOP 3 단어 6개를 제외한 12개의 라벨 데이터(dependent 관계를 표시)로 구성
- Slabel: The corresponding arc labels of words, excluding those 6
  words on the stack/buffer (nl = 12)
special NULL token을 non-existent elements를 위해 사용
- stack과 buffer가 empty이거나, dependents가 아직 assign 되지 않은 경우

arc labels를 Sl(nl=12)에서 6 word를 빼는 과정을 통해, 우리 모델은 rich set of elements cheaply가 가능하다(hand-crafting many more indicator features 대신에)

2.4.2 One-hot Representation

앞의 피쳐들을 One-hot Representation으로 표현

word => 18개

18×vocabulary 크기의 one-hot matrix

POS tag => 18개

18×POS tag개 크기의one-hot matrix

Arc-label => 12개

12×label 총 개수 크기의 one-hot matrix

2.4.3 Feature Embedding

word embedding matrix를 참고하여 해당 토큰의 벡터를 가져와 임베딩을 진행
Feature Embedding: 각 토큰별로 벡터가 있는 상태에서 모두 concatenate로 결합한 뒤, 이를 word feature로 바꾸는 과정
corresponding dense feature representations을 embedding matices에서 추출해서 inputs [xw, xt, xl].에 concatenate

2.4.4 Hidden Layer

embedding vector와 weight matrix를 곱한 후 bias vector를 더함
활성화 함수로 cube function을 사용
- 세제곱을 해주면 x의 피쳐들이 곱해지는 형태가 상호작용하는 것으로 표현

2.4.5 Output Layer

hidden layer를 거친 feature vector를 softmax layer에 넣음
의사결정으로 나타날 수 있는 모든 경우의 수의 확률을 계산
linear projection을 한 번 거친 후, softmax를 사용하여 shift, left-arc, right-arc 중 가장 확률이 높은 것을 출력

2.4.6 Results

A Fast and Accurate Dependency Parser using Neural Networks 실험 결과

정확도와 속도 모두 우수하다
UAS, LAS에서 2% 정도 성능 향상을 보였다

unlabeled attachment score (UAS) : arc(dependency)만 일치하는지 확인하고 label은 확인X
labeled attachment score (LAS) : arc 와 label 모두 일치하는지 확인.

2.5 Dependecy parsing 구현 - spacy colab

[논문] Parsing with Compositional Vector Grammars

0. Abstract

Natural language parsing은 small sets of discrete categories(NP(Noun phrases), VP(Verb phrases))로 되어왔다
-> 하지만 이들은 full syntactic이나 semantic richness of lingustic phrases를 포착하지 못한다
-> 그래서 해당 문제를 다루고자, exicalizing phrases or splitting categories 같은 시도들이 있었다(at the cost of huge feature spaces and sparseness)
그 대신, 본 논문에서는
Compositional Vector Grammer(CVG)를 제안
- PCFGs를 syntactically untied recursive neural network로 결합한 것
  (syntactico-semantic, compositional vector representations를 학습한다)
- Stanford Parser의 PCFG를 3.8% 상승해 F1 score 90.4%를 얻었다
- 훈련하기에 빠르고, 효율적인 reranker로 시행된다
  (current Stanford factored parser보다 20% 빠르다)
- CVG는 soft notion of head words를 학습하고, ambiguities type에서 성능을 향상한다

1. Introduction

Syntactic parsing은 NLP에서 central task다
- linguistic expression 과 meaning 사이에서의 매개효과 때문에
- 예를 들어, 대다수의 일들은 syntactic representations의 usefulness를 다음 task에서 보여왔다
  - relation extraction, semantic role labeling (Gildea and Palmer, 2002) and paraphrase detection (Callison-Burch, 2008).
Syntactic descriptions은 coarse discrete categories(예)noun phrases를 위한 NP, prepositional phrases를 위한 PP)를 prepositional phrases를 위해 사용한다
하지만 최근 연구들은 parsing 결과가 more fine-grained syntactic categories(유사한 행동이 있을 때 phrases를 더 잘 포착해낸다, manual feature engineering이나 automatic learning으로)를 정의함으로써 향상됨을 입증해왔다
하지만 NP 같은 카테고리를 30, 60개의 서브카테고리로 나누는 것은 매우 제한된 representation( phrase meaning, semantic similarity)을 제공한다
그래서 두 가지 시도가 있었다

discriminative parsing에서의 최근 연구는 features에 대한 careful engineering에서 gains를 보였다
lexicalized(어휘화하다) parsers는 각 카테고리를 lexical item으로 associate한다
-> semantic similarity에 대해서 fine-grained notion을 제공한다(ambiguous attachment decisions과 같은 문제를 해결하는데 유용하다)
-> 하지만 이 접근법은 complex shrinkage estimation을 필요로 한다
( lexicalized categories에 대해서 sparsity of observations를 다루기 위해서)

많은 NLP system에서 single words와 n-grams는 distributional similarities에 의해서 유용하게 described된다
하지만 large corpora 때문에 많은 n-grams는 훈련 동안에 보여지지 않는다(특히 n이 클 때)
-> 해당 경우에서, distributional similarities를 사용해서 unseen phrases를 represent하는 것도 어렵다
-> 해당 work에 대해서 새로운 해결책을 제시한다
: 길고 보여지지 않는 n-grams에 대해서 to learn features and phrase representations
Compositional Vector Grammar Parser (CVG)를 structure prediction을 위해 소개한다
모델은 representing phrases and categories의 문제를 다룬다
-> 이때 이전과 달리,
- jointly learns한다
- how to parse + how to represent phrases
  (discrete categories와 continuous vectors 둘다에 대해서)
standard probabilistic context free grammars (PCFG)의 이점과 recursive neural networks (RNNs)의 이점을 합쳤다
PCFG의 이점: can capture the discrete categorization of phrases into NP or PP
RNNs의 이점: can capture fine-grained syntactic and compositional-semantic information on phrases and words.
-> 해당 정보들은 syntactic ambiguity가 semantic information으로 resolve될 수 있을 때 도움이 된다
: 예) PP attachment of the two sentences - They ate udon with forks. vs. They ate udon with chicken.
이전 RNN-based parsers는 모든 nodes에서 같은 weights를 썼다(to compute the vector representing a constituent)
- 이는 composition function이 extremely powerful할 것을 요한다
  (phrases를 different syntactic head words와 결합해야 하기 때문에)
- 또한 optimize하는 것이 어렵다
  (파라미터들이 깊은 neural network를 형성해서)
- 우리는 fully tied RNN을 syntactically untied weights로 일반화했다
  - 각노드에 있는 weights는 child constituents한 카테고리에서 conditionally dependent하다
    -> 이는 different types of phrases를 combining할 때, 다양한 composition functions를 가능하게 한다
    -> 그리고 pasing accuracy에서 큰 성능향상을 보였다
우리의 compositional distributed representation은 CVG parser가 정확한 파싱 결정을 하도록 하고, phrases와 sentences 사이에 유사점을 포착한다
어떠한 PCFG-based parser도 RNN에서 향상될 수 있다
우리는 base PCFG로 Stanford Parser에서의 a simplified version을 사용했고 정확도를 86.56에서 90.44%로 올렸다