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

자연어에서의 재귀

자료구조와 알고리즘을 공부하다보면 꼭 만나게 되는 개념 중 하나가 바로 재귀(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 …

통사론이나 언어학개론 수업에서 재귀를 배울 때 보통은 그냥 어떤 문법 규칙을 갖고선 그 규칙을 이용해 무한한 길이의 문장을 만들 수 있다는 점을 배우고 앞서 말했듯 인간의 언어능력의 창조성 또는 창의성을 보여주는 걸로 끝나는 경우가 많다. 사실 이 재귀란 건 구문분석(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)을 책상 위에 놓으라고 해석할 수 있다는 것이다.¹ 일다 여기까지는 어느 정도는 간단해 보인다. 중의적인 문장을 어떻게 분석하느냐에 따라서 의미가 달라진다는 것. 근데 만약 이 문장이 아래와 같이 확장되면 어떨까?

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

이전 문장과 비교했을 때 (3a)에서 추가된 건 “in the kitchen”이란 전치사구(prepositional phrase)²가 추가된 것뿐이다. 하지만 마찬가지로 중의적인데, 이 경우 시행할 수 있는 구문분석은 총 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 \rightarrow$ 은지 $|\; NP$ 그리고 $NP$

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

다시 생성 규칙 (4)로 돌아가보자. 먼저 (4)는 아래 두 개의 문장들을 생성한다.

• (4a) 은지
• (4b) 은지₁ 그리고 은지₂

(4b)에서 “은지₁”과 “은지₂”는 명사, 즉, NP이므로 생성 규칙 (4)를 재귀적으로 각각 적용할 수 있다.

• (4c) 은지₁ 그리고 은지₃ 그리고 은지₂
• (4d) 은지₁ 그리고 은지₂ 그리고 은지₃

보다시피 (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)와 같은 상황들을 아래와 같이 일반화해볼 수 있다. 먼저 $X$가 임의의 명사구 NP라 할 때, $X_{n}$에 대한 생성 규칙을 아래와 같이 정의한다.

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

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

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

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

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

이제 (7)과 (6)을 이용해 연속 근사(successive approximation)을 해보자. 사실 (3) ~ (5)에서 했던 걸 다시 반복하는 거다.

• (8a) $X_{0} = 0$
• (8b) $X_{1} =$ 은지 + $X_{0}$ • 그리고 • $X_{0}$
                  $=$ 은지 + $0$ • 그리고 • $0$
                  $=$ 은지
• (8c) $X_{2} =$ 은지 + $X_{1}$ • 그리고 • $X_{1}$
                  $=$ 은지 + 은지 그리고 은지
• (8d) $X_{3} =$ 은지 + $X_{2}$ • 그리고 • $X_{2}$
                  $=$ 은지 + $($ 은지 + 은지 그리고 은지 $)$ • 그리고 • $($ 은지 + 은지 그리고 은지 $)$
                  $=$ 은지 + 은지 그리고 은지
                                + 은지 그리고 은지 그리고 은지
                                + 은지 그리고 은지 그리고 은지
                                + 은지 그리고 은지 그리고 은지 그리고 은지
                  $=$ 은지 + 은지 그리고 은지
                                + 2(은지 그리고 은지 그리고 은지)
                                + 은지 그리고 은지 그리고 은지 그리고 은지
•                .
•                .
•                .

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

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

5와 비슷한 모양새를 갖고 있다. 즉, 5가 보여주는 중의성 계수들인 1, 1, 2, 5, 14 …이 (9)에서도 똑같이 나타난다는 것이다. 그리고 이는 사실 카탈랑 수(Catalan numbers)를 나타낸다. 실제로 On-Line Encyclopedia of Integer Sequences에서 A000108 수열로 등록된 카탈랑 수를 보면 동일한 수열이 나열 되어있는 것을 알 수 있다.

참고문헌

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.