[CS224N] Lecture 5 – Dependency Parsing

이번 시간에는 자연어의 의미를 이해하기 위해 자연어의 구조를 파악하는 방법을 알아본다.

언어의 구조에는 두 가지 관점이 있는데, 그 중 하나가 phrase structure이다.

이 관점에서는 단어들을 더 작은 구성요소로 분해한다.

예를 들어, 각 단어를 분해하고 품사를 정의해 품사에 따라 순차적으로 결합해갈 수 있다.

예를 들어 [한정사 + (형용사) + 명사 + (전치사구)]를 명사구라 정의하면,

명사구 안의 전치사구는 다시 [전치사 + 명사구] 로 분해될 수 있다.

여기에서의 명사구는 다시 [한정사 + (형용사) + 명사 + (전치사구)]로 분해될 수 있다.

언어마다 문법이 다르기 때문에 당연히 규칙도 달라질 수 있지만,

요지는 phrase structure는 이런 식으로 문장을 계층적으로 분해해 문장의 구조를 표현한다는 것이다.

다른 관점으로는 dependency structure가 있다.

dependency structure는 단어 사이의 의존성을 표현한다.

여기서의 의존성이란 한 단어가 다른 단어를 수정하는 관계를 의미한다.

왜 문장의 구조를 파악해야 하는걸까?

앞서 배운 것처럼 벡터에 의미를 녹여내는 방법으로도 문장의 의미를 어느정도 표현할 수 있지만,

사람들은 단어를 복잡하게 조합해 더 풍부한 의미를 만들어내기 때문에

문장의 진짜 의미를 이해하기 위해서는 어떤 단어가 argument인지, 어떤 단어가 modifier인지 알아야 한다.

아래 예시들은 모두 어떤 단어가 어떤 단어를 modify하는지에 따라 의미가 완전히 달라지는 문장의 예시이다.

우리가 문장의 구조를 파악해 하고싶은 것은 이런 것이다.

단어의 관계를 일종의 tree처럼 나타내는 것

dependency syntax에서는 단어 사이의 관계를 정의하고, 이 관계에는 문법적 정의가 붙기도 한다.

각 화살표는 dependency의 시작점인 head와 dependent를 연결하고,

일반적으로 connected/acyclic/single-head tree 형태를 가진다.

이런 dependency syntax는 오랜 역사를 가지고 있다.

지금까지 문법을 표현하기 위한 대부분의 시도가 여기에 해당되며, constituency는 비교적 최근 등장했다.

참고할 점 두 가지

• 화살표 방향은 상관없지만 수업에서는 head → dependent 방향 사용할 것
• 모든 단어가 다른 node에 의존하는 경우 fake ROOT를 추가하기도 함

여기에서 treebank가 나오는데.. 뭔지 모르겠어서 찾아보니 그냥 구문 구조가 주석으로 달린 말뭉치이다.

수동이나 반자동으로 만든 treebank를 이용해 구문 분석기를 만들 수 있다.

언뜻 보기에는 느리고 안좋아보이지만 의외로 장점이 있다.

• 한 번 구축해놓으면 재사용이 가능함
• 커버리지가 넓고, 통계적 정보가 들어있어 ML에서도 사용 가능
• 시스템을 평가할 수 있음

dependency parsing은 어떤 단어가 어떤 단어에 의존하는지를 정의하며 진행된다.

여기에는 몇 가지 제약이 있다.

• 하나의 단어만이 ROOT의 dependent이다.
• cycle은 없어야 한다.

이런 제약사항들이 tree 구조를 만든다.

dependency parsing의 방법에는 여러가지가 있지만, 그 중 우리가 볼 것은 transition-based parsing이다.

구글에서도 웹페이지를 파싱할 때 사용했다고 한다.

첫번째로 볼 transition-based parsing 방법은 greedy transition-based parsing이다.

parser는 stack, buffer, set of dependency arcs, set of actions로 구성된다.

첫 단계에서 stack에는 ROOT만이 존재하고, 나머지 단어들은 모두 buffer에 들어있다.

이 상태에서 buffer의 단어들을 하나씩 stack으로 옮겨가며 stack 맨 끝 두 단어의 관계를 정의하고,

관계가 정의된 단어는 stack에서 사라진다.

정의된 관계는 set of dependency arcs에 쌓인다.

이 동작을 stack이 빌 때까지 반복한다.

하지만 이 방식은 각 단어에 대해 모든 경우(shift, left arc, right arc)를 고려해야 하기 때문에 비효율적이다.

이 점을 보완하기 위해 MaltParser가 등장한다.

MaltParser는 각 단계에서 어떤 action을 선택할지를 분류기에 맡긴다.

정확도가 조금 떨어지긴 했지만 성능이 O(n) 수준으로 매우 빨라졌다.

이런 방식에서는 훈련을 위해 feature를 위와 같이 미리 정해둬야 했다.

각 feature를 1~3개씩 결합해 binary state로 표현하면, 위와 같이 sparse vector로 state를 나타낼 수 있다.

평가는 몇 개의 arc가 맞았는지를 카운트하는 방식으로 이루어졌다.

이 때 label인 무시할수도 있고 포함할수도 있다.

하지만 이런 방식은 문제가 있었다.

• state가 sparse representation
• 단어의 의미 반영 불가
• 매우 많은 feature로 계산이 비쌈

그래서 neural dependnecy parser가 등장한다.

MaltParser가 기존 graph based parser보다 빠르고 성능은 조금 떨어지는 반면,

neural dependency parser인 C&M은 기존 parser들보다 빠르고 정확하기까지 하다.

신경망 최고.

입력값을 벡터로 만들어준다는 점은 비슷하지만 여기에서는 word embedding 등 단어의 의미를 담은 dense vector를 이용한다.

또한 품사나 dependency label도 벡터로 나타낼 수 있다.

훈련을 위해 이미 파싱된 train set을 만들고, 이것들을 벡터로 바꾼 후 concat해 훈련할 수 있다.

모델 구조는 위와 같다.

input layer에서 앞서 설명한대로 vector를 입력받으면,

hidden layer에서 weight를 곱한 후 ReLU를 통과시키고

output layer에서 softmax를 이용해 동작을 결정한다.

이런 구조를 사용한 결과 정확도와 속도 면에서 월등히 뛰어난 parser를 만들 수 있었다.

그 이후로도 neural net을 이용한 parser는 계속해서 개발되었는데,

network가 깊어지며 beam search가 이용되기도 했다.