자연어에서의 재귀와 카탈랑 수

구슬아이스크림 @icecream_mable@hackers.pub

자연어에서의 재귀

자료구조와 알고리즘을 공부하다보면 꼭 만나게 되는 개념 중 하나가 바로 재귀(Recursion)입니다. 함수가 재귀하지 않음으로써 본인 스스로가 무한히 호출되지 않는 기저 조건(Base case)을 갖고 있고 이후엔 Induction step을 따라서 계산되는 바로 그거죠. 수학에서는 수리적 귀납법(Mathematical induction or a proof by induction)이라는 증명 테크닉으로서 소개됩니다.

이 재귀라는 개념은 사실 언어학에서도 굉장히 중요하게 다루어지는데 (특히 통사론), 인간의 언어능력(Language faculty)의 창조성 혹은 창의성을 보여주는 특징 중 하나로서 관찰되기 때문입니다. 예컨대 아래 문장들을 보죠.

  • (1a) 예쁜 은지의 여동생이 있다.
  • (1b) 예쁜 은지의 여동생의 인형이 있다.
  • (1c) 예쁜 은지의 여동생의 인형의 옷이 있다.
  • (1d) 예쁜 은지의 여동생의 인형의 옷의 단추가 있다.

(1a)에서 (1d)를 살펴보면 문장이 점점 더 길어지는 것을 알 수 있는데, 결국엔 소유의 기능을 나타내는 '-의'라는 조사를 이용해 문장을 생성시키는 것을 알 수 있습니다. 다시 말해, 'X의 Y의 Z의 ...'와 같은 재귀를 보여주는 것이죠.

1, 1, 2, 5, 14 ...

사실 재귀가 1, 1, 2, 5, 14 ...로 나열되는 카탈랑 수(Catalan numbers)와 연관되어 있는 건 많이들 알려진 겁니다. 근데 이게 자연어에도 관찰될 수 있다는 사실은 알고 계셨을까요?

통사론이나 언어학개론 수업에서 재귀를 배울 때 보통은 어떤 한정된 문법 규칙을 갖고선 그 규칙을 이용해 무한한 길이의 문장을 만들 수 있다는 점을 배우고, 앞서 말했듯 인간의 언어능력의 창조성 또는 창의성을 보여주는 걸로 끝나는 경우가 많습니다. 근데 구문분석(Parsing) 관점에서 본다면 이 재귀에서 우리는 카탈랑 수를 관찰할 수 있습니다. 이번에는 영어 예시를 한 번 봐보죠.

  • (2a) Put the block in the box on the table.

이 문장은 사실 중의적(Ambiguous)인데, 왜냐하면 (2a)은 아래와 같이 두 가지 경우로 구문분석이 가능하기 때문입니다.

  • (2b) Put the block [in the box on the table].
  • (2c) Put [the block in the box] on the table.

즉, (2a)는 (2b)와 같이 [책상 위에 있는 박스 안에](=in the box on the table) 블록을 넣으라고 해석하거나, 아니면 (2c)와 같이 [박스 안에 있는 블록](=the block in the box)을 책상 위에 놓으라고 해석할 수 있다는 것이죠.[1] 일단 여기까지는 어느 정도는 간단해 보입니다. 중의적인 문장을 어떻게 분석하느냐에 따라서 의미가 달라진다는 거죠. 근데 만약 이 문장이 아래와 같이 확장되면 어떨까요?

  • (3a) Put the block in the box on the table in the kitchen.

이전 문장과 비교했을 때 (3a)에서 추가된 건 "in the kitchen"이란 전치사구(Prepositional phrase)[2]가 추가된 것뿐입니다. 하지만 마찬가지로 중의적인데, 이 경우 시행할 수 있는 구문분석은 총 5가지 경우입니다.

  • (3b) Put the block [[in the box on the table] in the kitchen].
  • (3c) Put the block [in the box [on the table in the kitchen]].
  • (3d) Put [[the block in the box] on the table] in the kitchen.
  • (3e) Put [the block [in the box on the table]] in the kitchen.
  • (3f) Put [the block in the box] [on the table in the kitchen].

그리고 여기서 만약 전치사구가 또 하나 더 생성된다면, 구문분석을 할 수 있는 경우의 수는 위 5가지 경우보다 훨씬 더 많아질 겁니다. 직접 쓰면 머리만 아퍼질 때니 조금 더 간단한 구조를 갖고 이야기 해봅시다. 다음과 같은 생성 규칙을 지닌 문법이 있다고 해보죠.

(4) NP→NP \rightarrow 은지 ∣  NP|\; NP 그리고 NPNP

(4)에서 NP는 명사구(Noun phrase)의 약자입니다. "예쁜 은지", "그 똑똑한 사람", "멋있는 베이스를 치는 료"와 같은 게 그 예시들인데, 사실 NP에 대한 생성규칙(예: NP→(det)  NNP \rightarrow (det)\; N)을 만들어야하나 이 포스트에선 크게 중요하지 않은 부분이므로 단순히 명사를 지칭하는 걸로 합시다.

다시 생성 규칙 (4)로 돌아가봅시다. 먼저 (4)는 아래 두 가지 경우들을 생성합니다.

  • (4a) 은지
  • (4b) 은지1 그리고 은지2

(4b)에서 "은지1"과 "은지2"는 명사, 즉, NP이므로 생성 규칙 (4)를 재귀적으로 각각 적용할 수 있습니다.

  • (4c) 은지1 그리고 은지3 그리고 은지2
  • (4d) 은지1 그리고 은지2 그리고 은지3

보다시피 (4c)와 (4d)를 생성했는데 각각 "은지"의 라벨링(=아래첨자 숫자)가 서로 다른 것을 알 수 있습니다 (이는 제가 구분의 편의를 위해 임의로 지정한 겁니다). 이를 좀 더 구문분석에 친화적으로 표기를 바꾸면 다음과 같습니다.

  • (4e.I) [[은지 그리고 은지] 그리고 은지]
  • (4e.II) [은지 그리고 [은지 그리고 은지]]

즉, 구문분석 단계에서는 "은지 그리고 은지 그리고 은지"는 앞서 살펴보면 영어 문장 (2) ~ (3)처럼 중의적이기에 (4e.I) 또는 (4e.II)로 분석될 수 있다는 걸 알 수 있습니다. 즉, 두 개의 트리가 생기는 것이죠. 우리는 이러한 트리를 중의성 계수(Ambiguity coefficient)라 합시다. 이를 적용하면 (4e)의 중의성 계수는 2임을 알 수 있으며, (4e)에서 생성규칙 (4)를 다시 적용하면 위 영어 문장 (3)처럼 5개의 구문분석이 시행 가능한 트리가 나오며 이는 중의성 계수가 5임을 보여주죠. 이를 순차적으로 쭉 표현하면 다음과 같습니다.

  • (5a) 1[은지]
  • (5b) 1[은지 그리고 은지]
  • (5c) 2[은지 그리고 은지 그리고 은지]
  • (5d) 5[은지 그리고 은지 그리고 은지 그리고 은지]
  • (5e) 14[은지 그리고 은지 그리고 은지 그리고 은지 그리고 은지]
  • ...

따라서 우리는 (5)와 같은 상황들을 아래와 같이 일반화해볼 수 있습니다. 먼저 XX가 임의의 명사구 NP라 할 때, XnX_{n}에 대한 생성 규칙을 아래와 같이 정의합니다.

  • (6) Xn=X_{n} = 은지 + (Xn−1(X_{n-1} • 그리고 • Xn−1)X_{n-1})

(4)에서 "+"는 하나의 명사를 생성하는 두 가지 다른 방식을 연결(Connect)하는 기능을 하며, "•"은 하나의 명사를 결합(Concatenate)하는 기능을 합니다 ("은지"와 "그리고" 대신에 다른 명사나 접속사가 되어도 상관없습니다. 예컨대 "봇치"와 "하지만"도 가능.). 이 표현들이 어색하다면 배커스-나우르 표기법(BNF)으로 쓰면 다음과 같이 표현 가능합니다.

  • (6a) Xn::=X_{n} ::= 은지 | (Xn−1(X_{n-1} • 그리고 • Xn−1)X_{n-1})

또한 X0X_{0}에 대해서 먼저 아래와 같이 기저 조건을 정의합니다.

  • (7) X0=0X_{0} = 0

이제 (7)과 (6)을 이용해 연속 근사(Successive approximation)을 해볼까요? 사실 (3) ~ (5)에서 했던 걸 다시 반복하는 겁니다.

  • (8a) X0=0X_{0} = 0
  • (8b) X1=X_{1} = 은지 + X0X_{0} • 그리고 • X0X_{0}
                    == 은지 + 00 • 그리고 • 00
                    == 은지
  • (8c) X2=X_{2} = 은지 + X1X_{1} • 그리고 • X1X_{1}
                    == 은지 + 은지 그리고 은지
  • (8d) X3=X_{3} = 은지 + X2X_{2} • 그리고 • X2X_{2}
                    == 은지 + (( 은지 + 은지 그리고 은지 )) • 그리고 • (( 은지 + 은지 그리고 은지 ))
                    == 은지 + 은지 그리고 은지
                                  + 은지 그리고 은지 그리고 은지
                                  + 은지 그리고 은지 그리고 은지
                                  + 은지 그리고 은지 그리고 은지 그리고 은지
                    == 은지 + 은지 그리고 은지
                                  + 2(은지 그리고 은지 그리고 은지)
                                  + 은지 그리고 은지 그리고 은지 그리고 은지
                    . . .

이와 같은 방식으로 쭉 근사를 한 것을 수열처럼 표현하면 다음과 같습니다. (제곱 표시는 괄호 안의 단어 전체가 제곱만큼 반복된다는 것입니다.)

  • (9) X=X = 1(은지)
                    + 1(은지 그리고 은지)
                    + 2은지 (그리고 은지)2^2
                    + 5은지 (그리고 은지)3^3
                    + 14은지 (그리고 은지)4^4
                    + ...

(9)는 예시 (5)와 비슷한 모양새를 갖고 있습니다. 즉, 예시 (5)가 보여주는 중의성 계수들인 1, 1, 2, 5, 14 ...이 (9)에서도 똑같이 나타난다는 거죠. 그리고 이는 처음에 언급했듯 카탈랑 수와 동일합니다. 실제로 On-Line Encyclopedia of Integer Sequences에서 A000108 수열로 등록된 카탈랑 수를 보면 동일한 수열이 나열 되어있는 것을 알 수 있습니다.

사실 봤던 겁니다. 근데 말이죠...

위 자연어 예시는 우리가 컴파일러 책들을 보다보면 늘 나오는 산술 표현식에서 x * y * z를 컴퓨터로 하여금 어떻게 처리해야할지 ((x * y) * z)로 해야할지 아니면 (x * (y * z)로 해야할지)에 대한 예시와 동일합니다. 차이점이라면, 산술 표현식의 경우에는 어느 것을 더 우선으로 할지 어느 정도 정답이 정해져있는 반면, 자연어의 경우에는 그렇지 않다는 거죠. 왜 그럴까요? 맨 처음에 봤던 한국어 문장을 다시 살펴봅시다.

(1a') 예쁜 은지의 여동생이 있다.

(1a')는 한국어 문장에서 중의성을 보여주는 유명한 예시 중 하나입니다. 왜냐하면 다음과 같이 두 가지 경우로 구문 분석이 가능하기 때문이죠.

(1a.I) [예쁜 은지]의 여동생이 있다.
(1a.II) [예쁜 은지의 여동생]이 있다.

즉, (1a.I)와 같이 "예쁜"을 수식하는 것이 은지이거나(=은지가 예쁘다) 아니면 (1a.II)처럼 은지의 여동생을 수식할 수도 있다(=은지의 여동생이 예쁘다)는 거죠. 이는 산술 표현식과는 달리, 정답이 없는 문제입니다. 그저 이 두 가지 분석 중에 어느 것이 '선호'될 수 있다고만 말할 뿐이죠. 즉, 둘 중 어느 한 쪽이 확률적으로 더 높느냐에 따라 (1a')에 대한 해석이 정해진다는 겁니다. 이를 알기 위해선 실제로 코퍼스(=말뭉치)를 분석하거나 사람들에게 직접 실험을 해봐야 알 수 있는 문제이고, 전산/심리언어학에선 굉장히 고전적인 문제 중에 하나입니다.

정리하면 자연어에서 어떤 동일한 구조가 재귀적으로 반복되어 중의성이 관찰될 때, 그 중의성의 갯수가 조합론에 나오는 카탈랑 수와 동일하게 대응된다는 것이겠네요. 하지만 그 중의성을 어떻게 해소해야될지에 대한 문제는 우선 순위를 정할 수 있는 산술 표현식의 경우와 달리 자연어에선 확률에 의존해야 합니다. 어때요? 신기하지 않나요?

참고문헌

Church, K., Patil, R. (1982). Coping with syntactic ambiguity or how to put the block in the box on the table. American Journal of Computational Linguistics.

  1. 이 두 개의 해석 중에 어느 것이 선호되느냐는 또 다른 문제입니다. ↩︎

  2. 전치사구란 영어를 예시를 들어 얘기하면 in, on, at과 같은 전치사를 중심으로 함께 분포되는 단어들의 집합을 말합니다. 참고로 한국어는 후치사(Postposition) 시스템입니다. ↩︎

7
0
0

No comments

If you have a fediverse account, you can comment on this article from your own instance. Search https://hackers.pub/ap/articles/019a3942-968a-763a-bd5b-326cdb2c8c73 on your instance and reply to it.