[cs224n] 5강 의존성 파싱 (1/4, 구문 구조 (phrase structure))

오늘은 먼저 사람 언어로 된 문장의 구조에 대해 설명하고 동기부여를 해보겠습니다. 일종의 20분짜리 언어학이죠. 그다음 특히 의존성 (dependency) 문법에 대해 집중해 보겠습니다. 그리고 의존성 구조로 작업하는 방법을 소개하겠습니다. 전이 (transition) 기반 의존성 파싱 (parsing)이라고 불리는 의존성 문법 파싱을 볼 거구요. 그다음 어떻게 신경망 의존성 파서를 만들 수 있는지에 대해 얘기하죠.

문장의 구조에 대해서 얘기해 보죠. 인간의 언어로 된 문장 구조를 얘기할 거고 사람들이 그 구조를 어떻게 생각하는 지에 대해서 얘기합니다. 그리고 자연어처리를 하는 사람들이 어떤 목표를 가지고 있는지에 대해서 얘기해 보죠. 그건, 문장의 구조를 이해할 수 있는 구조를 만드는 건데요. 오늘 제가 예로 드는 것들은 모두 영어로 된 겁니다. 왜냐면 그 언어는 여러분들이 잘 아는 것일 테니까요. 하지만 이건 영어에 대한 팩트 (fact)를 의미하는 건 아닙니다. 이건 여러분이 모든 언어에 적용될 수 있는 인간 언어의 문장 구조에 대해 어떻게 생각할 수 있는지에 대한 아이디어죠. 언어학자들이 문장 구조에 대해 생각해 온 두 가지 다른 방법이 있습니다. 둘 사이엔 어떤 관계가 있지만요.

하나는 구문 (phrase) 구조라고 부릅니다. 혹은 구문 구조 문법이라고도 합니다. 만약 CS103에서 배운 걸 희미하게 기억해 보면, 문맥 없는 문법에 관한 강의를 들었다면요. 구문 구조 문법은 문맥 없는 문법을 도구로 사용하여 문장에 대한 구조를 놓습니다. 간단히 소개하면, 사실 이게 우리가 수업시간에 사용할 주요 도구입니다. 문장위에 의존성 구조를 놓는거죠. 구문 구조의 아이디어는 문장들이 점진적으로 네스트 (nest)하는 (사이에 자리를 잡는) 단위들로 만들어졌다는 겁니다. 그래서 the, cat, cuddly... 단어로 시작해 보죠. 그다음 우리는 그것들을 구문이라고 부르는 더 큰 단위에 넣어보죠. the cuddly cat by the door처럼요. 이런식으로 여러분은 그것들을 계속해서 더 큰 단위로 합칠 수 있죠.

이게 어떻게 되죠? 이 아이디어는, 일종의 언어학자들이 생각하는 방식인데, 자, 여기 언어가 있는데, 영어가 아닐 수도 있죠. 오하칸이나 다른 언어라도요. 그게 어떤 구조를 가지죠? 우리는 언어의 많은 문장을 볼 수 있습니다. 그리고 언어학자들은 이렇게 생각할 겁니다. "난 the cat, a dog, the dog, a cat 등등의 패턴을 볼 수 있어".라구요. 그건 하나의 단어 클래스 (class)가 (a, the 같은) 있고, 언어학자들은 그걸 한정사라고 하죠. 영어에선 관사라고 하구요. 여기 명사를 위한 다른 클래스가 있죠. 이 패턴을 잡기 위해서, 우리는 언어의 곳곳에서 보는 이것을 단위로 만들 수 있을 것 같네요. 그건 바로 한정사 뒤에 명사로 만들어진 거죠. 저는 구문 구조 문법 법칙이라고 합니다. ,혹은 문맥없는 문법 (context-free grammar)법칙이라구요. 명사 구문은 한정사와 명사로 된다는 거죠. 이것만 볼 수 있는게 아니죠. 다른 예도 볼 수 있는데, 우리 언어에서 the large cat 같은 예를요. 혹은 a barking dog이요. 혹은 the cuddly cat, the cuddly dog처럼요. 그걸 보니 제 문법에 뭔가를 더 넣어야 할 것 같군요. 아마 저는 제 문법으로부터 이렇게 말할 수 있을 것 같네요. 명사 구문은 한정사가 오고 그 다음 선택적으로, 형용사를 넣을 수 있고, 그리고 명사를 넣을 수 있다구요. 그 다음 좀 더 살펴보면, the cat in a crate 같은 예를 찾을 수 있죠. 혹은 a barking dog by the door 같은 예도요. 그래서 저는 그것들을 문법에 넣고 싶습니다. 그러나 그 지점에, 뭔가 특별한 걸 알아챘는데, 여기 다른 것들이 있죠. 한정사 + 명사는 처음에 시작한 명사와 매우 비슷해 보입니다. 잠재적으로 더 큰 문장 안으로 들어가서 확장할 수 있는 구문을 가지는 거죠. 이것도 확장을 할 수 있죠. the 와 door 사이에 green을 넣어서요. 이런 점을 어떤 식으로든 잡아 내고 싶죠. 아마도 저는 이렇게 말할 수 있을 텐데요. 명사 구문은 한정사 선택적으로 형용사, 그리고 명사이고 또 다른 어떤 것을 저는 전치사 구문이라고 부를텐데요. 그럼 저는 두번째 규칙 (rule)을 적을 수 있죠. 그 규칙은 전치사 구문은 전치사 다음 명사 구문으로 이뤄진다라는 겁니다. 그럼 저는 앞에서 정의한 명사구문을 여기서 다시 쓰는 거죠. 그 즉시 저는 다른 것도 만들어 낼 수 있습니다. "the cat by the large door"같은 걸요. 또 "the cat by the large crate" "the cat by the large crate on the table" 같은 걸요. 왜냐면 일단 전치가 구문이 명사 구문을 포함하는 순간 그리고 명사 구문이 전치가 구문을 포함하는 순간 저는 명사 구문을 반복적으로 왔다 갔다 하면서 무한대로 큰 문장을 만들 수 있는거죠. 맞죠? 그래서 이렇게 쓸 수 있죠. the cat by the large crate on the large table by the door... 계속해서 큰 문장을 만들 수 있고, 이걸 슬라이드에 넣을 공간이 없지만 제 문법에 따라 이것에 대한 분석을 했죠. 즉, 명사 구문은 한정사, 명사, 전치사 구로 이뤄진다구요. 전치사 구문은 전치사와 명사 구문으로 이뤄진다구요. 이 명사 구문은 다시 한정사, 명사, 전치사 구문으로 이뤄지죠. 이렇게 계속하면 큰 문장을 만들 수 있죠. 그 다음 더 많은 문법을 볼 수 있는데, "Well, now I can talk to the cat"에서 이 고양이에게 얘기한다는 것은 동사죠. 말하다 걷다 같은 것은 동사죠. talk to the cat은 그 뒤에 전치사 구문이 있죠. 그럼 또 다른 규칙을 적을 수 있는데, 동사 구문은 동사와 전치사구로 이뤄진다구요. 그럼 더 큰 문장을 만들 수 있습니다. 그리고 언어의 더 많은 문장을 보고 이 문맥없는 문법 규칙을 만들어서 언어의 구조를 설명할 수 있습니다. 이것이 언어학자들이 하는 일입니다. 그리고 다른 언어들은 다른 구조를 가지고 있죠. 예를 들면, 여기 있는 작은 문법이나 일반적으로 영어에서 볼 수 있는 것은 전치사 구문이 동사 뒤에 나온다는 거죠. 그러나 중국어 같은 언어는 전치사 구문이 동사 앞에 옵니다. 중국어에 대한 규칙은 다르죠. 그리고 저는 그것들을 위한 문맥 없는 문법을 작성할 수 있습니다. 이것이 문맥 없는 문법의 아이디어죠. 근데 사실 이게 여러분이 언어학과에 가서 언어학 수업을 들으면 볼 수 있는 지배적인 언어학적 구조 입니다. 그 사람들은 이런 종류의 구문 구조 문법 트리를 만들죠. 그러나 반대로, 반대는 아니고 다른 방식이, 컴퓨터 언어학에서 매우 지배적이었죠. 그 대신 보여줄 것은 의존성 구조의 관점입니다. 의존성 구조의 아이디어는 이런 종류의 명사 구문, 전치사 구문 같은 구문 카테고리를 갖기 보다는 바로 문장의 구조를 보여줄 겁니다. 어떻게 단어들과, 다른 언어의 논항 (argument)과 한정사가 재귀적인 방식으로, 다른 단어에 어떻게 의존하고 있는지를 얘기하는 구조입니다.

여기 "Look in the large crate in the kitchen by the door"라는 문장이 있죠. 만약 이 단어들에 단어 클래스 (class)를 주고 싶다면, 이건 동사 이건 전치사 이건 한정사 이건 형용사 이건 명사라고 할 수 있을 것입니다. 그러나 우리가 구조를 나타내기 위해서는 이렇게 말해야 할 겁니다. 여기 동사가 전체 문장의 루트 (root)고, 거기서 문장이 시작하죠. 그 다음 우리가 볼 건 "in the large crate"죠 . 그건 Look에 의존적이죠. crate를 보면 그건 한정사가 있죠. the large crate로요. the는 crate에 의존적이죠. large도 crate에 의존적이죠. 이 의존성 시스템에서 제가 보여주고 싶은건 'in the large crate'에서 한정사입니다. 이 crate 자체도 한정이 되는데, 왜냐면 crate in the kitchen이니까요. in the kitchen은 crate의 한정사죠. 그 다음 by the door 있죠. by the door가 한정하는 건 뭐죠? 역시 crate죠. crate by the door이니까요. by the door도 crate에 의존적이죠. 이렇게 우리는 의존성 구조를 얻을 수 있습니다.

어떤 단어들이 다른 단어를 한정하죠? 그것이 우리가 문장의 여러 부분이 다른 부분과 어떻게 연관되는지 이해하도록 해 줍니다. 여러분들은 왜 문장 구조가 필요하냐고 물을 지도 모르겠습니다. 여러분의 친구들에게 얘기할 때 언어가 동작하는 방식은 어떤 실수를 좀 해도 우린 '니 말이 뭔지 이해해'라고 얘기하죠. 그 이상으로 의식에 접근하지는 못합니다. 그러나 언어를 제대로 이해하는 머신을 갖기 위해서는 문장 구조를 이해해야 합니다. 왜냐면 우리가 어떤 단어가 다른 단어의 논항인지 한정사인지 모르면 우리는 문장이 뭘 의미하는지 알 수 없죠. 어떻게 잘못될 수 있는 지 예를 보여주죠. 많은 경우 여러가지 해석이 있을 수 있습니다. 여태까지 우리는 단어의 의미를 봤습니다. 워드 벡터를 했고, 단어들이 비슷한 의미를 가질 수 있는 것도 알았죠.

인간 언어에서는 단어를 말하는 것으로 어느 정도 이해를 할 수 있죠. 제 말은 "hi"라고 친절하게 말하면, 말에서 그렇게 다르게 이해할 수 없다는 겁니다. 사람이 복잡한 방식을 표현하고 설명하고 서로 가르쳐주는 방식은 단어들을 함께 붙여서 복잡한 의미를 표현하는 것입니다. 그걸 계속 반복하죠. 재귀적으로 더욱 더 복잡한 의미를 쌓기 위해서요. 여러분들이 아침 뉴스를 읽을 때, 여러분은 문장들이 20-30단어로 된 것을 알 수 있고, 어떤 복잡한 의미, "지난밤 상원 공화당원들은 뭐뭐하지 않기로 결의했다" 등을 여러분을 실수하지 않고 이해할 수 있죠. 단어의 의미들을 서로 붙여서요. 우리가 알아야 하는 것은 무엇과 무엇이 연결되어 있는가입니다. 그것이 중요한데, 어떻게 하면 잘못될 수 있을까요?

여기 신문 기사가 있죠. San Jose cops kill man with knife. 이건 여러분이 결정하는 것에 따라서 2개의 의미를 가지고 있죠. 뭐가 뭐를 한정하는지에 따라서요. 두 의미가 뭐죠? 의미 1, 경찰이 그 사람을 칼로 죽인거죠. 여기서 우리가 얻는 것은 우리는 사람을 죽이는 경찰을 얻죠. kill의 주어가 cops라는 거죠. man은 kill의 목적어죠. cop은 죽이기 위해서 칼을 사용했죠. knife는 경찰이 사람을 칼로 죽였다고 말하기 위한 인스트루멘탈 (instrumental) 한정사죠. 이게 가능한 하나의 분석이구요. 문장이 가질 수 있는 2번째 의미는 man이 knife를 가졌다는 거죠. 그 경우 우리가 말하고 싶은 건 man이 명사 한정사를 가져서 man이 뭔가를 가졌다고 하는 거죠. with와 knife 의존성은 똑같습니다. 이 문장의 해석들은 문장에 다른 구조를 놓는 것에 따라서 얻을 수 있죠. 무엇이 무엇을 한정하냐에 관해서요. 여기 비슷한 다른게 있는데요.

Scientists count whales from space.

역시 이 문장은 2개의 구조를 가질 수 있죠. 과학자가 count의 주어죠. 고래는 목적어구요. 하나의 가능성은 이게 세는 방식이라는 거죠. 그래서 인공위성 같은 걸로 우주에서 센다는 것을 의미하죠. 다른 가능성은 앞부분은 같은데, 과학자가 주어, 고래가 목적어, 근데 이 부분은 우주에서 온 고래. 우리는 명사 구문이 명사와 전치사로 이뤄진다는 것으 봤으니, 의존 문법에서는 from space가 whales의 한정사로 볼 수 있죠. 명백하게 여러분이 원하는 것은 위의 것이 맞고 아래쪽이 틀린거죠. 그래서 이 선택은 전치사구 부가 모호성 (prepositional phrase attachment ambiguity)라고 합니다.

영어를 파싱하는데 가장 흔한 모호성 중 하나죠. 여기 from space라는 전치사구가 있고, 그 전에 동사가 있고 이후에 명사 혹은 명사구가 있다면 전치사구가 앞에온 둘중의 하나를 한정할 수 있죠. 이건 인간의 언어가 프로그래밍 언어와 어떻게 다른 지에 대한 매우 중요한 방식인데, 프로그래밍 언어에서는 여러분이 어떻게 뒤에 매달린 것을 어떻게 해석하는지에 대한 엄격한 규칙이 있죠. 프로그래밍 언어에서는 else는 가장 가까운 if에 해당하는 것으로 이해하죠. 그게 원하는 것이 아니라면 괄호를 사용하거나 들여쓰기를 하던가 해야 하죠. 파이썬과 C에서 다르지만요. 인간 언어는 그렇지 않습니다. 인간 언어에서는 이 전치사 구가 앞선 어떤 것과도 연결될 수 있죠. 듣는 사람이 충분히 똑똑해서 맞는 것으로 이해하도록 되어 있는데, 그것이 인간의 의사소통이 그렇게 효율적인 이유의 큰 부분이죠. 우리는 서로서로 의사소통을 잘 할 수 있는데, 대부분의 경우 우리는 많이 얘기할 필요가 없거든요. 반대편엔 우리가 말한 단어들을 올바르게 이해할 수 있는 매우 똑똑한 사람이 있죠. 그래서 만약 여러분이 인공지능이나 똑똑한 컴퓨터를 갖고 싶다면, 우리는 언어를 이해할 수 있고 그 기초 위에서 동작하는 기기를 만들 필요가 있고, 그것들은 from space가 한정하는 것이 무엇인지 제대로 결정할 수 있어야 하겠죠. 그게 잘 동작한다면, 그걸 프로그래밍 언어에도 적용할 수 있겠죠. 여러분의 프로그래밍 언어에 괄호를 안넣어도 컴파일러가 여러분이 의미한 대로 동작하겠죠. 이것이 전치사구 부가 모호성입니다. 별로 안어려워 보이지만 점점 더 어려워 집니다.

이건 예제처럼 재밌지 않은데, 월스트리트 저널 (The Wallstreet Journal)의 실제 예입니다.  The board approved its acquisition by Royal Trustco Ltd. of Toronto for $27 a share at its monthly meeting. 재미없는 문장이죠. 이 문장의 구조가 뭐죠? 여기 동사가 있고, 주어가 있고, 명사가 있고, 목적어죠. 그 다음을 보면, 여기 전치사구가 있고, 다음에도 전치사구가 있고, 연속으로 4개의 전치사구가 있죠. 하고 싶은 건 각각의 전치사 구에 대해 그들이 뭘 한정하느냐는 걸 알아보는 겁니다. 거기엔 2개의 선택이 있는데, 전에 봤듯이 앞선 동사와 명사죠. 그러나 이건 들여다 보면 더 복잡한데, 또 다른 명사가 전치사구들 안에 있기 때문이죠. 그래서 더 깊숙이 갈 수록 더 많은 가능성이 있습니다. 우리가 해결할 수 있는지 보죠. by Royal Trusto Ltd.는 뭘 한정하죠? acquisition이죠. The board approved by Royal Trustco Ltd.가 아니죠. acquisition by Royal Trustco Ltd.죠. 이건 acquisition에 의존하고 있죠. of Toronto로 가보죠. 3개의 선택지가 있습니다. of Toronto는 Royal Trustco Ltd.를 한정하죠. of Toronto는 Royal Trustco Ltd.에 의존적이죠. Royal Trustco Ltd.도 명사구니까 전치사구가 한정할 수 있죠. for $27 a share는 acquisition을 한정하나요? 그렇죠. 건너뛰어서 acquisition을 한정합니다. 마지막으로 at monthly meeting은 approved를 한정하죠. 우리는 단어들이 한정하는 패턴을 얻었습니다. 일단 이렇게 선택지가 많아지면, 잠시 멈춰서 이 문장에 대해 분석해서 맞는 구조를 만들려고 하면, 잠재적으로 가능한 구조의 지수로 생각을 해봐야 할 겁니다. 왜냐면, 이런 상황에서는, 첫번째 전치사구에 대해 한정을 할 수 있는 2개가 있고, 두번째 전치사구에서 3개의 경우가 있고 4번째의 경우 한정할 수 있는 게 5개가 있죠. 팩토리얼 (factorial) 같네요. 팩토리얼 만큼 나쁘진 않겠지만요. 왜냐면 일반적으로 이런 중간의 절을 빼 버리면 더 먼 전치사구는 적어도 그들이 한정하는 것에 대해 뒤에 있어야죠. 이런 조합을 하게 되면, 여러 개의 전치사구가 있을 때 분석된 숫자는 카탈란 수 (Catalan numbers)라고 불리는 숫자입니다. 여전히 지수로 증가하죠. 트리같은 문맥에서 많이 등장합니다.

트라이앵귤라 (triangular) 확률적 그래픽 모델을 하고 삼각형이 얼마나 많은지 질문했다면, 그것이 일종의 변수에 대한 트리를 만드는 것이죠. 그게 카탈란 시리즈 수를 줍니다. 우리는 많은 애매함을 가지고 끝났습니다. 그게 전치사구 부가 모호성이죠.

몇 가지 다른 것도 얘기해 보죠. Shuttle veteran and longtime NASA executive Fred Gregory appointed to board. 이 문장은 왜 애매하죠? 다른 의미가 뭐죠? 2개의 가능성이 있죠. Shuttle veteran and longtime NASA executive, 그의 이름은 Fred Gregory 그가 이사회에 임명되었다는 거죠. 다른 가능성은 Shuttle veteran과 longtime NASA executive, Fred Gregory가 둘 다 이사회에 임명된거죠. 또 다시, 우리는 우리의 의존성 구조를 나타내 볼 수 있습니다. 우리는 그림처럼 2개의 다른 구조로 의존성을 표현할 수 있습니다. 그게 별로 웃기진 않죠.

여기 같은 애매함을 효과적으로 보여주는 더 웃긴 예가 있는데요. President's first physical. Doctor: No heart, cognitive issues. 여긴 사실 명시적인 접속어 (coordintation word)가 없죠. 사실상 자연어 혹은 영어에선 쉼표를 사용해서 목록 억양을 사용해서, 그게 and나 or인것 처럼 역할을 하죠. 여기 우린 2개의 가능성이 있는데, issues가 있고, issues에 대한 의존성은 No issues죠. 그게 한정사죠. 그리고 그건 No heart or cognitive issues죠. heart가 또 다른 의존하는 것이고. 일종의 명사 복합어 heart issues죠. 우리는 그걸 독립성이라고 하죠.  이 'No heart or cognitive issues'에서 heart or cognitive는 합쳐진 구 (phrase)죠. 다른 가능성이 있는데, 최상층에서 접속어는 'No heart' 그리고 'cognitivie issues'라고 할 수 있죠. 그 점에서, 우리는 cognitive issues는 형용사 한정사를 가지고 No heart에서 No는 그냥 heart의 한정사죠. 그 다음 이게 합쳐지는 겁니다. heart는 issues의 접속어 의존성을 가지죠.

더 웃긴 게 있죠. 우리는 형용사 한정사 모호함이 있죠. 의도된 읽기는 first가 first hand의 형용사 한정사고 그건 first hand experience죠. first hand experience의 한정사고, job도 experience의 한정사죠. 그리고 같은 주어가 있죠. 목적어도 있구요. 그러나 불행하게도 이 문장은 다르게 읽을 수 있는데 한정 관계를 바꾸면요. 그건 first experience고 이렇게 (녹색 화살표처럼) 되는 거죠.

하나의 예가 더 잇네요. Mutilated body washes up on Rio beach to be used for Olympics beach volleyball. 이걸로 해석할 수 있는 두가지는 뭐죠? 여기 'to be used for Olympics beach volleyball'이라는 구조의 큰 구문이 있죠. 이건 일종의 전치사 부가 모호성 같죠. 그러나 이번엔 부가된 게 전치사인게 아니라, 우리는 이 큰 동사 구를 가지는 겁니다. 그래서 여러분은 일종의 문장의 대부분을 주어 없이 가지는거죠. 'to be used for Olympics beach volleyball'은 일종의 동사구죠. 부정사 형태로 되어 있네요. 때로는 그건 'being used for Olympics beach volleyball' 처럼 CPO 형태의 부분에 있는데요. 이런 종류의 동사구는 전치사 구와 같습니다. 그것들이 오른쪽에 끝에 나타날 때마다, 그것들은 동사나 명사를 한정할 수 있죠. 여기 2개의 가능성이 있는데, 이 'to be used for Olympics beach volleyball'이 의미하는 정답은 Rio beach에 의존적인 거죠. Rio beach의 한정사입니다. 웃긴 읽는 방법은 그 대신, 여기 'Mutilated body' 명사구가 'to be used' 될 거라는 거죠. 그럼 이게 명사구의 한정사가 되는거죠. 해석을 이해하기 위해서 올바른 문장 구조를 아는 것은 중요하죠. 여러분이 의도한 해석을 얻고 의도하지 않은 해석은 얻지 않기 위해서요.

분명히 이유가 있어서 웃긴 예를 선택한거죠. 이건 우리가 대부분의 경우 언어에서 얻어 내고 싶은 모든 것의 본질적인 것입니다.이건 우리가 종종 바이오 메디컬 연구 기사를 읽어서, 단백질-단백질 상호작용에 대한 사실을 추출해 내려고 하는 재미없는 건데요. 그 결과는 KaiC는 rythmically SasA KaiA와 KaiB와 상호작용한다는 걸 보여주죠. 만약 우리가 단백질-단백질 상호작용 팩트를 얻어 내고 싶다면, 우리는 KaiC가 다른 단백질과 상호작용한다는 것이 여기 있고, 우리가 할수 있는 방식은, 우리의 의존성 분석에서 패턴을 보는 거죠. 우리는 여기 반복된 패턴을 볼 수 있죠. 명사 주어가 명사 한정사와 상호작용하죠. 그리고 그건 SasA 아래에 있는 것들이죠. 그리고 그건 KaiA와 KaiB를 엮고 있고 그 둘은 상호작용하고 있죠. 그래서 우린 사실 이 두개를 우리가 찾을 수 있는 패턴과 의존성이라고 생각할 수 있죠. 바이오 메디칼 문서에 나타나는 단백질-단백질 상호작용 예를 찾기 위한 것으로요. 이게 우리가 하고 싶은 전체적인 아이디어입니다.