[cs224n] 5강 의존성 파싱 (3/4, 전이 기반 파싱 (transition-based parsing))

이것이 파싱에 대한 개념이었죠. 와킴 니브르 (Nivre), 이 사람에 의해서 인기가 많아 졌는데, 스웨덴의 컴퓨터 언어학자였죠. 여러분이 하는 작업은 쉬프트 리듀스트 (shift-reduced) 파싱에 영감을 받은 겁니다. 컴파일러 수업 같은 곳에서 쉬프트 리듀스트 파싱을 봤을 겁니다. 이건 일종의 쉬프트 리듀스트 파서인데, 우리가 언제 리듀스트 해야 할지와는 별개로, 우리는 컨스티튜언트 대신 의존성을 만듭니다. 이건 매우 기술적인 설명을 많이 가지고 있는데, 봐 봤자 쉬프트 리듀스트 파서가 뭘 하는지 이해하는 데 별 도움이 안되서 넘어가겠습니다.

여기 전이 기반 쉬프트 리듀스트 파서에 대한 형식적인 설명이 있습니다. 이것도 별 도움이 안됩니다.

대신 우린 이 예를 보겠습니다. 이게 도움이 되길 바랍니다. 제가 하고 싶은건 "I ate fish."를 파싱하는 겁니다. 그러나 형식적으로 제가 가진것은 출발하는 곳에서 취할 수 있는 3개의 액션이 있죠. 형식적 파싱을 위한 종료 조건이 있습니다. 여기 제가 하는 건, 여기 스택이 있고, 버퍼가 있습니다. 스택은 제가 만든 건데, 버퍼는 문장의 모든 단어들로 아직 제가 다루지 않은 것들입니다. 파싱을 멈추고, 여기 일종의 지침이 있는데, 문장을 위한 스택에 루트를 넣고, 버퍼는 문장 전체가 되죠. 아직 의존성을 찾은 건 없습니다. 내가 취할 수 있는 액션은 단어를 스택으로 옮기는 거죠. 혹은 리듀스와 동등한 것을 하여 의존성을 만드는 겁니다. 의존성을 만들 수 없는데 왜냐면 스택에는 루트만 있기 때문입니다. 제가 할 수 있는 유일한 건 쉬프트죠. 'I'를 스택으로 쉬프트합니다. 이 지점에서 의존성을 만들자고 얘기를 할 수 있죠. 'I'는 루트의 디펜던트가 됩니다. 근데 그건 잘못된 분석이죠. 왜냐면 이 문장의 진짜 헤드는 'ate'거든요. 그래서 저는 영리하니까 다시 쉬프트를 합니다. 이제 스택에 루트, I, ate가 있죠. 이 지점에서, 제가 하려고 하는 건 구조를 만드는 리덕션 (reduction)입니다. 여기 'I ate'가 있고, 'I'가 'ate'의 의존성 주어라고 얘기하고 싶습니다. 그걸 리덕션으로 하는거죠. 그래서 하는 액션은 왼쪽-아크 (Left-arc) 리덕션이죠. 스택의 위에서 두번째 것을 스택의 제일 위에 있는 것의 디펜던트로 처리하는 겁니다.

그렇게 해서, 헤드로부터 두번째 것을 'ate'의 주어 디펜던트로 만들었죠. 그리고 스택에 헤드, 'ate'를 남겨놓습니다. 그러나 이 의존성을 제가 만든 다른 의존성에 추가했습니다. 이제 저는 즉시 다시 리듀스를 할 수 있고 ate가 루트의 디펜던트라고 할 수 있습니다. 그러나 제 문장은 'I ate fish'니까, 이제 하고 싶은 것은, 'fish'가 버퍼에 있다면 먼저 해야 할 건 쉬프트를 또 하는 거죠. 이제 루트, 'ate', 'fish'가 있죠. 여기서 이렇게 얘기할 수 있습니다. 이 스택의 탑에 있는 것을 스택의 탑으로부터 두번째 있는 것의 오른쪽 디펜던트로 만들고 싶다구요. 그걸 롸이트-아크 무브 (right-arc move)라고 합니다. 그래서 롸이트 아크라고 하고 리덕션을 하죠. 거기서 새로운 의존성을 만들고 스택의 탑의 2개를 취해서 'fish'가 'ate'의 디펜던트라고 하는 거죠. 헤드는 계속 가지고 있구요. 저는 항상 헤드를 스텍에 가지고 있습니다. 그리고 이 새로운 아크를 만들죠. 이 지점에서 저는 같은 위치에 있고 이 'ate'가 루트의 오른쪽 디펜던트라고 얘기하고 싶습니다. 그래서 라이트 아크를 다시 할 겁니다. 그래서 여기 추가적인 의존성을 만듭니다. 그래서 성공적으로 파싱된 문장의 종료 조건은 버퍼가 비었고 루트만 스택에 남는 것입니다. 왜냐면, 종료 조건으로 버퍼가 비는 것을 얘기 했으니까요. 이제 문장을 파싱했습니다. 잘 동작했는데요. 저는 사실 언제 쉬프트하고 언제 리듀스 할지에 대한 여러 선택지가 있었죠. 그리고 저는 기적적으로 매 지점마다 올바른 선택을 했죠.이 지점에서 여러분은 모든 선택을 탐색해 봤어야 하는 거 아니냐고 말할 수 있을 겁니다.그리고 다른 파서가 어떻게 됐는지 확인해 보구요. 할 수 있었죠. 하지만 그게 제가 해야 한 것이라면, 여러 가능한 파서의 지수 사이즈 트리를 탐색해야 했을 겁니다. 그걸 제가 했다면, 효율적으로 파싱할 수 없었을 겁니다. 실제로 60, 70, 80년대에 사람들도 이것을 하지 않았습니다. 60년대 영리한 사람들은 여기서 형편없는 서치를 하는 대신, 영리한 다이내믹 프로그래밍 (dynamic programming) 알고리즘을 생각해 낼 수 있다고 얘기했죠. 여러분은 효율적으로 모든 가능한 파서의 공간을 탐색할 수 있는데, 그게 일종의 그 시대의 파싱의 중심이었죠. 이후 요아킴 니브르가 나와서, "그건 사실이지만, 여기 영리한 아이디어가 있습니다"라고 말했죠.

우리는 2000년대에 있고 머신러닝을 알기 때문에, 그 대신 할 수 있는 것이 있죠. 예를 들어 파싱의 특정 위치에 있다면, 머신 러닝으로 분류기를 만들고, 그 머신 러닝 분류기가 다음에 뭘 할 건지를 알려줄겁니다라고 얘기했습니다. 쉬프트할지, 왼쪽 아크할 지 오른쪽 아크할 지를요. 만약 우리가 어떻게 화살표를 만들지에 대해서만 얘기한다면, 단지 3개가 있습니다. 시프트, 왼쪽 아크, 오른쪽 아크요. 만약 우리가 의존성에 레이블을 붙이고 싶다면, 그리고 여러 레이블이 있다면, 그럼 2R + 1 액션들이 있죠. 왜냐면 왼쪽 아크 주어, 왼쪽 아크 목적어 같은 것들이 있을 테니까요. 어쨌든, 액션 집합이 있고, 여러분은 머신 러닝으로 분류기를 만들거고 맞는 액션을 예측할 겁니다. 요아킴 니브르는 약간 놀라운 사실을 보여줬는데, 바로 여러분이 취할 올바른 액션을 높은 정확도로 예측할 수 있다는 겁니다. 가장 간단한 버전에서, 여기엔 서치 (search)는 전혀 없는데도, 각 단계에서 분류기를 실행하면, 그건 '다음으로 할 건 시프트입니다'라고 말하죠. 그럼 시프트하면 되고, 그게 '다음으로 할 건 왼쪽 아크'라고 하면 왼쪽 아크하면 되는거죠. 그는 경험적으로 그렇게 하는 것 만으로도 문장을 높은 정확도로 파싱할 수 있다고 보여줬습니다.

서칭을 좀 하면 더 잘 할 수 있죠. 그러나 그게 필요한 건 아닙니다. 분류기를 실행하고, 액션을 예측하고, 분류기를 실행하고, 액션을 예측하기만 해도 우린 놀라운 결과를 얻습니다. 우리가 얻는 것은 선형 타임 (linear time) 파서죠. 왜냐면 우리는 문장을 한꺼번에 받아 들일거고 각각에 단어에 대해 선형 작업량을 처리할 거니까요. 그건 엄청난 돌파구입니다. 60년대 사람들이 다이나믹 프로그래밍 알고리즘을 생각했지만, 문장에 대한 다이나믹 프로그램은 3제곱이거나 더 나빴죠. 전체 웹을 다 파싱하려면 그건 별로 좋은게 아니죠. 반면 이런 선형 시간의 뭔가를 가지고 있으면, 목표에 도달할 수 있습니다.

이것이 예전 방법으로 행해진 것들입니다. 우리는 어떤 것이 어떤 것에 의존하는지에 대한 작업을 했다면, 여기 스택이 있고, 어떤 구조를 만들었겠죠. 우리가 다루지 않은 단어들의 버퍼가 있고, 우리는 다음 행동을 예측하고 싶어합니다. 기존의 방법은 우리는 피쳐 (feature)를 갖고 싶다고 하는 거죠. 갖고 싶어하는 피쳐의 종류는 보통 연결이나 곱하는 거죠. 만약, 스택의 제일 위의 단어가 good이면, 그리고 뭔가가 참이고, 스택의 두번째 탑에 있는 건 has이고, 그건 그 문장의 동사죠. 그건 아마도 어떤 행동을 가리키는 것일 겁니다. 그래서 여기 매우 복잡한 바이너리 인디케이터 피쳐를 가지게 됩니다. 글자 그대로 수 백만개의 이 바이너리 인디케이터 피쳐를 가집니다. 그걸 큰 로지스틱 회귀나 서포트 벡터 머신 (support vector machine)에 집어넣고, 파서를 만드는거죠. 근데 이 파서가 꽤 잘 동작합니다. 그러나 여러분은 이런 종류의 매우 복잡한 손으로 엔지니어링한 바이너리 피쳐를 가집니다.

의존성 파서를 어떻게 평가하는지 설명하죠. 그건 정말 간단해요. 문장에 대한 맞는 의존성 파서가 있다고 가정하죠. She saw the video lecture. 이것들은 맞는 화살표들이고, 우리의 의존성 파서를 평가하려면 우리는 단순히 어떤 아크가 맞는지 얘기하면 됩니다. 여기 골드 아크들이 있는데, 2에서 1로요. She는 주어고, 골드 아크가 루트인 0에서 2으로 있네요. 이게 골드 아크고, 우리가 파싱을 만들면, 우리는 뭐가 그 단어의 헤드 인지에 대해서 몇 가지 아크를 제안하죠. 우리는 각각의 아크를 따로 취급하면서 단순히 그들 중 몇 개가 맞았는지 더하면 됩니다. 2가지 방법이 있는데, 레이블을 무시하는 언레이블드 부가 점수 (unlabled attachment score)가 있는데, 제 의존성 파서는 아크의 대부분은 맞지만 3 4는 틀렸죠. 그래서 저의 언레이블드 부가 점수는 80퍼센트입니다. 또 레이블을 볼 수도 있습니다. 제 파서가 그건 잘 하지 못해서 40%만 맞았네요. 우리는 의존성 숫자를 세서 우리가 얼마나 많이 맞았는지를 알아 내는 것으로 정확도를 구합니다.