Parse Tree : Dependency 와 Constituency

Parse tree 는 크게 2가지 종류로 나눌 수 있다. 바로 위 제목의 Dependency tree 와 Constituency tree 이다.

 

서로 다른 assumption(가정)을 기반으로 하고 똑같이 sequence 에서 문법 정보를 추출하는것을 목표로 한다.

 

Constituency parsing

Constituency parse 는 context-free grammar 를 기반으로 한다.

 

문장이 constituent 단위로 나뉘고, 즉 sun-phrase 들은 grammar 의 특정 카테고리에 포함된다.

 

예를 들면 a computer on the table, the nice sunset 등은 다 noun phrase 이고, eat a pizza 는 verb phrase 이다.

 

Rule 집합을 사용한다.

 

예를 들면 VP -> VNP 는 VP=verb phrase 를 V 와 Noun phrase 로 표현할 수 있다는 뜻이다.

 

C 파스트리는 항상 문장의 word 를 terminal nodes 로 표현한다.

 

대게 각 word 는 pos tag (noun, adjective, verb, etc…) 를 담고잇는 parent node 를 가진다. 이 친구들은 생략될수도 있다.

 

모든 다른 nonterminal node 들은 문장의 constituent(구성요소?)들을 표현한다. 그리고 보통 non terminal node은 verb phrase, noun phrase, or prepositional phrase (PP) 중 하나이다.

 

 

 

위를 'i saw a fox' 예를 들면, root 아래 첫번째 단계에서 문장은 noun phrase 인 I 1개 단어와 saw a fox 라는 verb phrase 로 나뉜다.

 

이는 grammar가 S->NPVP 의 룰을 가진다는 뜻이고, 이는 문장이 np(noun phrase) 와 vp(verb phrase) 의 concat으로 만들어진다는 뜻이다.

 

비슷하게 vp는 v와 또다른 np 로나눌수잇다. 이도 또다른 grammar 의 rule 이다.

 

즉, c파싱은 context free 그래머에서 문장의 syntactic 표현을 포함하는 트리를 만든다. 이는 매우 hierarchixal 하고 문장을 single phrasal constituents로 나눈다.

 

Dependency parsing

은 c파싱과 반대로, phrasal constituent(구성요소)나 sub phrase 를 사용하지않는다.

 

대신, syntax를 단어간의 dependency들로 표현한다.

 

그래프에서 단어 사이의 typed edge 로 표현한다.

 

G=(V,E) 에서 V는 단어들의집합이고, edge는 2개 단어를연결한다.

 

그래프는 아래 3가지 조건을 만족해야한다.

1. 들어오는 edge 가 없는 단일 Root 노드가 반드시 잇어야한다.
2. V 안에 있는 각 노드 v는 반드시 root 에서 v 로 가는 path 가 있어야한다.
3. Root 외의 각 노드들은 각 1개의 들어오는 edge가 잇다.

** 하지만 결국 위 규칙처럼 acyclic 하기때문에 dependency 파스 그래프도 트리형태로나타낼 수 있다.

각 엣지는 2개 단어 사이의 문법적인 관계가 정의된 type 을 가진다.

 

 

다음 그림처럼 2개 파싱에대한 결과는 매우 다르다.

여기에서는 tree의 루트는 verb 동사이다.

 

자연어 파싱의 도전과제

같은 문장이라도 유효한 여러 개의 파스트리가 잇을 수 있다.

 

사용 case

보통은 dependeny 파싱이 qa나 정보추출 등의 downstream 태스크에서 더 유용하다.

 

더 쉽게 subject-verb-object triples 라는 semantic 관계를 더 잘 추출할 수 있다.

 

c파싱에서도 할수는잇지만 처리가더필요하다.

 

또한 d 파싱은 단어 순서가 자유로운 언어에서 사용하기 더 유리하다.

 

반대로, 문장에서 sub-phrases 를 추출하려고하면 c파싱이 더 유리하다.

참조

https://www.baeldung.com/cs/constituency-vs-dependency-parsing