CS224n의 4번째 lecture는 Dependency Parsing으로 문장의 구조를 분석하고 이해하는 방법에 대해 설명했습니다. 본 lecture의 순서는 다음과 같습니다.
- Syntactic Structure: Consitituency and Dependency
2.Dependency Grammer and Treebanks
3.Transition-based dependency parsing
4.Nerural dependency parsing
1. Syntactic Structure: Consitituency and Dependency
Parsing이란 문장의 문법적인 구문을 분석하는 과정입니다. Parsing은 목적에 따라 2가지 방법이 존재합니다.
- Consitituency parsing
- Dependency parsing
Consitituency Parsing
먼저 Constituency Pasring이란 문장을 중첩된 성분으로 나누어 문장의 구조를 파악하는 방법입니다. 주로 영어와 같이 어순이 고정적인 언어에서 사용됩니다.
the(Det), cat(N), cuddly(Adj), by(P), door(N)
각 단어들은 해당 단어의 문법적인 의미를 가지고 있습니다. ‘the’는 한정사, ‘cat’은 명사, ‘cuddly’는 형용사, 등으로 단어는 품사를 가지고 있습니다. 이러한 단어들을 결합하여 구를 형성합니다.
the cuddly cat -> NP (Det + Adj + N)
by the door -> PP (P + N)
이러한 구와 구를 결합하여 문장을 완성할 수 있습니다.
The cuddly cat by the door. -> NP ( NP + PP )
구는 다음과 같이 각 품사의 집합으로 볼 수 있습니다.
Dependency Parsing
Dependency parsing은 문장에 존재하는 단어가 어떤 다른 단어에 의존적인지 관계를 파악하는 방법입니다.
보통 한국어와 같이 자유 어순을 가지거나 문장성분이 생략 가능한 언어에서 사용하는 방법입니다.
Dependency parsing은 수식을 받는 단어에서 수식을 하는 단어로 화살표를 그립니다.Dependency parsing의 output은 개별 단어간의 관계에 대한label(관계)입니다. 수식을 받는 단어를 head 혹은 governor라고 하고 수식을 하는 단어를 dependent 혹은 modifier라고 합니다.
why do we need sentence structure?
언어를 정확하게 해석하기 위해 문장 구조에 대한 이해가 필요하고 인간은 복잡한 단어의 구성을 통해 의사소통을 하기 때문에 정확한 이해를 위해서는 연결 구조에 대해서 알고 있어야한다.
Prepositional phrase attachment ambiguity
Phrase Attachment Ambiguity는 형용사구, 동사구, 전치사구 등이 어떤 단어를 수식하는지에 따라 의미가 달라지는 모호성을 말합니다.
San Jose cops kill man with knife.
Scientists count whales from space.
첫 문장은 경찰이 칼을 든 남자를 죽인것인지, 칼로 남자를 죽인것인지 문장의 뜻을 정확히 해석할 수 없습니다. 그리고 두번째 문장은 과학자들이 우주에서 고래를 센건지, 우주에 있는 고래들을 센건지 정확히 이해할 수 없습니다.
Coordination Scope Ambiguity
Coordination Scope Ambiguity는 특정 단어가 수식하는 대상의 범위가 달라짐에 따라 의미가 변하는 모호성을 말합니다.
위에 문장을 보면 우주선 베테랑이자 오랜 NASA 임원인 Fred Gregory를 수식하는 것으로 볼 수 있고 우주선 베테랑과 NASA 임원인 Fred Gregory로 해석할 수 있습니다.
즉, 문장은 많은 단어가 복잡한 관계로 구성되어있기 때문에 앞서 본 문장처럼 애매모호한 해석을 맞게 이해하기 위해서는 문장의 구성요소들이 어떻게 연결되어있는지에 대한 이해가 필요합니다.
2. Dependency Grammer and Treebanks
Dependency Grammar and Dependency Structure
문법의 관계는 통사의 구조에서 단어의 관계를 포함한다고 가정하고 이것은 일반적으로 두개의 비대칭한 화살표로 이루어져있습니다.
Dependency Structure는 sequence 형태와 tree 형태로 표현할 수 있습니다.
Dependency parsing은 가짜 ROOT 라는 노드를 문장 맨앞에 추가함으로써, 최종 head를 ROOT로 설정하고 모든 단어들이 의존관계를 가질 수 있게 합니다. 화살표는 임의대로 방향을 설정할 수 있지만 본 lecture에서는 head(수식을 하는)에서dependent(수식을 받는)로 방향을 설정했습니다.
또한 Dependency parsing은 화살표 위 label은 단어간 문법적인 관계를 의미하고 화살표는 순환하지 않으며 그로인해 parsing의 결과물을 tree 형태로 표현할 수 있습니다.
3.Transition-based dependency parsing
본 lecture에서 Dependecy parsing의 방법은 4가지가 있다고 했습니다.
- Dynamic programming
- Graph algorithms
- Constraint Satisfaction
- Transition-based
그 중 Transition-based 방법에 대해서 구체적으로 다뤘습니다.
Transition-based dependency parsing은 문장에 존재하는 단어들을 순서대로 입력하면서 단어 사이에 존재하는 dependency를 결정해나가는 방법입니다. Graph-based와 비교했을 때 속도는 빠르지만 성능이 많이 낮은데 그 이유는 Graph-based는 순서대로가 아닌 의존 관계를 모두 고려하기 때문이라고 했습니다.
Arc-standard transition-based parser
Arc-standard transition-based parser라고 불리우는 transition based dependency parser의 진행과정은 다음과 같습니다.
먼저 parsing 과정은 buffer, stack, Set of Arcs라는 3가지 구조를 가지고 있습니다. Stack으로 현재 처리할 단어가 있는곳이고, buffer로 아직 처리되지 않은 단어들이 있는곳이고, Set of Arcs
에는 parsing의 결과물이 담기게 됩니다.
또한, Parsing에는 3가지 decision이 존재합니다.
- shift : Buffer의 토큰이 stack으로 이동
- Right-Arc : stack에 있는 두 단어 중 오른쪽 단어를 지움
- Left-Arc : stack에 있는 두 단어 중 왼쪽 단어를 지움
다음과 같이 'I ate fish'라는 문장이 input으로 처음 들어오면 검은석 테두리는 stack으로 현재 처리할 단어가 있는곳이고, 주황색 테두리는 buffer로 아직 처리되지 않은 단어들이 있는곳입니다. 처음 들어온 상태에서 stack에는 root밖에 없으므로 할 수 있는 decision은 shift입니다.
이제 stack에 root와 'I'가 들어왔지만 분석할 구문이 없어 한번더 shift를 하게 됩니다.
이제 stack 안에 'I'와 'ate'의 관계를 비교할 수 있고 'I'가 'ate'에 의존하고 있으므로 Set of Arc에 (ate, nsubj, I)라는 형태로 담긴다. 또한, stack에서 의존하는 단어 'I'는 사라지게됩니다.
이러한 알고리즘을 문장이 끝날때까지 반복하면 buffer에는 더이상 토큰이 존재하지 않고 stack에는 root와 마지막 단어만 남아있게된다. 마지막 단어는 root에 의존하기 때문에 stack에는 root만 남게되고 끝나게됩니다. Stack에서 state를 기반으로 Decision을 결정하기 위해서 머신러닝이 적용되고 그 과정에서 state를 embedding하는 과정이 필요합니다.
MaltParser
State를 embedding하는 방법으로 Nivre and Hall의 논문인 MaltParser: A Data-Driven Parser-Generator for Dependency Parsing의 feature representation을 살펴볼 수 있습니다. Pos tagging과 notation을 기반으로 indicator features를 설정함으로 state를 embedding할 수 있습니다.
state에 알맞은 notation 결과는 다음과 같습니다. s1xW는 stack의 첫번째 단어인 'the', b1xW는 buffer의 첫번째 단어인 'cake', s1xt는 stack의 첫번째 단어인 'the'의 품사인 DT, lc(s2)xW는 stack의 두번째 단어인 'ate'의 첫번째 left-child인 'John', rc(s1)xW는 stack의 첫번째 단어인 'the'의 right-child의 값이 없어 Null로, 보여지는 notation은 일부분을 예시로 보여준 것입니다.
그렇다면 이러한 notation 기반으로 indicator features라는 조건을 설정함으로써 state를 임베딩할 수 있습니다. the'이고 STACK의 첫번째 태그가 'DT'면 1 아니면 0 이라는 값이 부여지게 됩니다. 이렇게 state가 one-hot 벡터로 표현이되고 해당 state를 10^6, 10^7 차원의 벡터로 표현하게 됩니다.
차원을 모두 계산해야 하는데, 차원이 너무 높아 Parsing 소요시간 중 95% 이상을 feature 연산이 차지하여 계산 비용이 높습니다.
Evaluation of Dependency Parsing
머신러닝을 이용한 Parsing의 성능을 평가하는 방법은 사람이 직접 dependency parsing을 작성하고 평가하는 것입니다.
각 단어의 왼쪽의 숫자는 단어가 의존하고 있는 단어의 index입니다. 그리고 UAS는 index를 기준으로한 accuracy이고 LAS는 index와 품사를 잘 예측했는지에 대한 accuracy입니다.
Neural dependency parser
최근에는 신경망 기반의 모델들이 발전하게 되면서 neural network가 적용된 Dependency Parsing에 대한 방법론이 제기되었습니다.
이때 Input으로 입력되는 feature는 words, POS tag, arc labels 3가지로 구분됩니다.
먼저 words feature로 들어가게 되는 데이터는 총 18개로 구성되어 있습니다.
STACK과 BUFFER의 TOP 3 words (6개)
STACK TOP 1, 2 words의 첫번째, 두번째 left & right child word (8개)
STACK TOP 1,2 words의 left of left & right of right child word (4개)
POS tags feature로 들어가게 되는 데이터는 words feature에서 들어가는 데이터의 태그를 의미하기 때문에 똑같이 18개가 됩니다.
Arc labels에서는 STACK과 BUFFER의 TOP 3 words 6개를 제외한 12개의 label(dependent 관계 표시) 데이터로 구성되게 됩니다.
이러한 feature들을 모두 one-hot representation으로 표현할 수 있습니다.
그 다음, word embedding matrix를 참고하여 해당 토큰의 벡터를 가져올 수 있습니다. 그렇다면 각 토큰별로 벡터가 있는 상태에서 모두 concat한 뒤에 input layer에 들어가게 됩니다.
또한 머신러닝과는 다르게 word embedding과 같은 dense한 vector를 사용했고 의미가 비슷한 words는 가까운 벡터를 갖고있습니다. 또한 POS tags와 dependency labels도 의미가 비슷할수록 가깝게 위치합니다.
NNS(plural noun) closed to NN(singular noun)
nummod(numerical modifier) closed to amod(adjective modifier)
Input layer를 거치고 hidden layer의 ReLU함수를 통해 hidden vector를 생성합니다. 만들어진 hidden vector를 output layer의 Softmax 함수를 통해 output을 생성합니다.
최종 output은 위에서 언급했던 Decision의 모든 경우의 수를 확률로 나타냅니다. Shift, Left-Arc, Right-Arc중 확률값이 가장 높은 decision이 최종 output이 됩니다.
