같은 계산, 다른 덧셈

가장 짧은 길, 길의 가짓수, 가장 그럴듯한 해석, 갈 수 있는지 없는지. 서로 다른 분야에서 따로 태어난 알고리즘⁠(algorithm)⁠들이 사실은 한 계산입니다. 달라지는 것은 '더하기'와 '곱하기' 자리에 무엇을 넣느냐뿐이고, 그렇게 바꿔 넣어도 되는 까닭의 핵심은 중학교에서 배운 분배법칙입니다.

이 글의 처럼 점선이 그어진 숫자는 좌우로 끌 수 있고(키보드 ←/→도 됩니다), 색이 칠해진 같은 말은 눌러서 바꿀 수 있습니다. 밑줄 친 말에 마우스를 올리면 그림에서 그 부분이 빛납니다. 그림 속의 변과 표의 칸은 대부분 누를 수 있고, 마우스를 올리면 정확한 값이 나옵니다. 휴대폰에서는 마우스를 올리는 대신 누르면 됩니다.

1962년 1월, 『ACM 저널』에 두 쪽짜리 논문이 실렸습니다. 매사추세츠의 컴퓨터 회사에서 일하던 스물여섯 살의 스티븐 워셜이 쓴 「불 행렬⁠(matrix)⁠에 관한 정리」입니다. 물음은 단순했습니다. 일방통행 길로 이어진 마을들이 있을 때, 길을 몇 번 갈아타든 상관없이 어느 마을에서 어느 마을로 갈 수 있는가. 워셜은 자기 방법이 언제나 옳은지를 두고 회사 동료와 럼주 한 병을 걸었고, 하룻밤 만에 증명을 찾아 내기에 이겼다고 전합니다. 같은 해 6월 『ACM 통신』에는 로버트 플로이드가 보낸 몇 줄짜리 프로그램 「알고리즘 97: 최단 경로⁠(shortest path)⁠」가 실렸습니다. 그 무렵 이 학술지는 새 프로그래밍 언어 알골 60으로 적은 짧은 알고리즘들을 번호를 붙여 차례로 싣고 있었고, 97번이 그것이었습니다. 이번 물음은 갈 수 있느냐가 아니라, 가장 짧게 가면 얼마냐였습니다.

두 방법을 오늘날 흔히 쓰는 모양으로 나란히 적으면 이렇습니다. 마을이 n개이고, 마을마다 1부터 n까지 번호를 붙입니다. R은 가로세로 n칸짜리 표이고, i번째 줄 j번째 칸 R[i][j]에는 'i에서 j로 갈 수 있는가'(참·거짓)를 적습니다. D도 같은 모양의 표이고, D[i][j]에는 'i에서 j까지 지금까지 찾은 가장 짧은 거리'를 적습니다. 처음에는 두 마을을 곧장 잇는 길만 적어 둡니다. 세 겹 반복문으로 적는 이 모양은 같은 해 피터 잉거먼이 정리한 것입니다.

워셜 (1962년 1월)                        플로이드 (1962년 6월)
for k = 1..n                             for k = 1..n
  for i = 1..n                             for i = 1..n
    for j = 1..n                             for j = 1..n
      R[i][j] = R[i][j] or                     D[i][j] = min(D[i][j],
                (R[i][k] and R[k][j])                        D[i][k] + D[k][j])

프로그램을 읽지 않는 분을 위해 말로 옮기면 이렇습니다. 'for k = 1..n'은 'k를 1부터 n까지 바꿔 가며 그 아래를 되풀이하라'는 뜻이고, 세 줄이 겹쳐 있으니 k, i, j의 모든 조합에 대해 마지막 줄을 한 번씩 합니다. 마지막 줄은 '마을 k를 거쳐서 i에서 j로 가는 방법'을 따져 표를 고칩니다. 워셜은 'i에서 j로 이미 갈 수 있거나(or), i에서 k로 갈 수 있고 그리고(and) k에서 j로 갈 수 있으면 참'이라고 적습니다. 플로이드는 '지금 적힌 거리와, i에서 k까지의 거리 더하기(+) k에서 j까지의 거리 가운데 작은 쪽(min)'을 적습니다. 예를 들어 i에서 j까지 지금 10이라고 적혀 있는데 i에서 k까지 3, k에서 j까지 4라면, min(10, 3 + 4) = 7로 고칩니다.

두 프로그램에서 다른 곳은 두 군데뿐입니다. 워셜의 or 자리에 플로이드는 min을, and 자리에 +를 썼습니다. 파리의 베르나르 로이는 1959년에 같은 방법을 이미 발표했지만 오래 주목받지 못했습니다. 더 거슬러 올라가면 1951년의 논리학자 스티븐 클리니도 숫자 대신 글자열을 다루며 같은 뼈대의 계산을 했습니다. 그 이야기는 4절에서 정규 표현식⁠(regular expression)⁠과 함께 다시 만납니다.

이 글의 물음은 이것입니다. 왜 같은 계산이 서로 다른 물음에 답할까? 더하기와 곱하기 자리에 무엇을 넣어도 되고, 무엇을 넣으면 안 될까? 답은 '반환(半環, semiring)'이라는 작은 대수 구조입니다. 이 구조를 알아보고 나면 최단 경로, 길의 가짓수 세기, 음성 인식의 비터비 알고리즘⁠(Viterbi algorithm)⁠, 문장의 구문 분석⁠(parsing)⁠, 베이즈 추론이 한 줄의 계산으로 보이고, 신경망⁠(neural network)⁠의 소프트맥스⁠(softmax)⁠와 열대 기하학⁠(tropical geometry)⁠까지 그 줄에 이어집니다. 동적 계획법⁠(dynamic programming)⁠이 왜 되는지, 그리고 언제 안 되는지도 같은 자리에서 나옵니다. 낯선 이름이 많지만, 어느 것이든 먼저 작은 지도나 문장에서 손으로 확인할 수 있는 예를 보인 뒤에 일반적인 말로 적습니다.

1 · 한 장의 지도갈래는 모으고, 길은 잇는다

작은 지도 하나로 시작합니다. 출발점 S에서 도착점 T까지 화살표 방향으로만 갈 수 있는 길이 있고, 변마다 수가 세 개씩 붙어 있습니다. 그 길의 길이, 갈림길에서 그 길을 고를 확률⁠(probability)⁠, 그리고 그 길에 놓인 다리의 폭입니다. 이 지도에 여섯 가지 물음을 던질 수 있습니다. S에서 T까지 가장 짧은 거리는 얼마인가? 길은 모두 몇 가지인가? 갈림길마다 확률대로 고르며 걷는 사람이 T에 닿을 확률은? 가장 그럴듯한 길 하나의 확률은? 트럭이 지나갈 수 있는 가장 넓은 길의 폭은? 애초에 갈 수는 있는가?

여섯 물음은 모두 달라 보이지만 푸는 방법은 하나입니다. S에서 가까운 점부터 차례로, 점마다 'S에서 그 점까지의 답'을 하나씩 적어 나갑니다. 먼저 최단 거리로 해 봅시다. 아래 그림의 지도에서 점 D로 들어오는 변은 셋입니다. S에서 곧장 오는 길이 7의 변, A에서 오는 길이 2의 변, B에서 오는 길이 6의 변입니다. S에서 A까지의 최단 거리가 2, B까지가 4라는 것을 이미 적어 두었다면, D까지 가는 후보는 0 + 7 = 7, 2 + 2 = 4, 4 + 6 = 10의 셋이고, 그 가운데 가장 작은 4가 D의 값입니다.

길의 개수로 같은 일을 하면 이렇습니다. S, A, B까지 가는 길이 각각 1가지이면, D까지 가는 길은 마지막 변이 어느 것이냐에 따라 1 × 1 + 1 × 1 + 1 × 1 = 3가지입니다(변 하나는 길을 한 가지로 이어 주니 1을 곱합니다). 두 계산의 모양이 같습니다. 들어오는 변마다 '앞 점의 값에 변의 값을 잇고'(최단 거리에서는 +, 개수에서는 ×), 그렇게 얻은 후보들을 '모읍니다'(최단 거리에서는 min, 개수에서는 +). 이것을 한 줄로 적으면 이렇습니다.

식을 말로 읽으면 이렇습니다. 점 v의 값은, v로 들어오는 변 u → v마다(큰 ⊕ 아래의 u → v가 그 뜻입니다) 앞 점 u의 값에 그 변의 값 w(u → v)를 ⊗로 이은 것을, 모두 ⊕로 모은 것입니다. ⊕('모으기', 동그라미 안의 더하기)는 여러 갈래를 하나로 모으는 연산이고, ⊗('잇기', 동그라미 안의 곱하기)는 한 길을 따라 한 걸음 더 잇는 연산입니다. 최단 거리라면 잇기는 길이를 더하기(+), 모으기는 짧은 쪽을 고르기(min)입니다. 길의 개수라면 잇기는 곱하기, 모으기는 더하기입니다.

그림 위의 단추로 한 점씩 넘기며 계산을 따라가 보세요. 단추 아래에 그 점의 계산이 식으로 나옵니다. 그다음 물음()을 바꿔 같은 일을 되풀이해 보세요. 볼 것은 물음을 바꿔도 걸음마다 하는 일은 같고 ⊕와 ⊗만 바뀐다는 점입니다.

T의 값은 입니다.

세 가지를 눈여겨보세요. 첫째, 걸음마다 하는 일은 물음과 상관없이 똑같습니다. 들어오는 변마다 ⊗로 잇고 ⊕로 모읍니다. 바뀌는 것은 ⊕와 ⊗가 무엇이냐, 그리고 변에 어떤 수를 적느냐뿐입니다.

둘째, 출발점 S에 적는 값이 물음마다 다릅니다. 최단 거리에서는 0, 개수에서는 1, 폭에서는 ∞(무한대, 어떤 수보다도 큰 값)입니다. 모두 '변을 하나도 지나지 않은 빈 길'의 값입니다. 빈 길은 거리가 0이고, 한 가지이며, 막는 다리가 없으니 폭이 한없이 넓습니다. 이 값들에는 공통점이 있습니다. ⊗로 이어도 상대를 바꾸지 않습니다. 0 + 5 = 5, 1 × 5 = 5, min(∞, 5) = 5입니다. 이런 수를 ⊗의 항등원⁠(identity element)⁠이라 합니다. 마찬가지로 들어오는 변을 모두 끊어 길이 하나도 없는 점의 값은 ⊕로 모아도 상대를 바꾸지 않는 수, 곧 ⊕의 항등원입니다. 최단 거리에서는 ∞(min(∞, 5) = 5), 개수에서는 0(0 + 5 = 5), 도달에서는 거짓('거짓 또는 p'는 p)입니다.

셋째, 가장 짧은 길(S→A→D→E→T, 길이 2 + 2 + 2 + 3 = 9)과 가장 그럴듯한 길(S→A→C→E→T)과 가장 넓은 길(S→A→D→F→T)은 서로 다른 길입니다. 같은 계산이 물음마다 다른 답을 냅니다. 정리하면, 여섯 물음은 '들어오는 변마다 잇고, 후보들을 모은다'는 한 가지 계산이고, 물음마다 달라지는 것은 잇기와 모으기의 뜻과 빈 길·길 없음의 값뿐입니다.

2 · 왜 되는가공통 인수를 묶어 내기

이 절의 물음은 이것입니다. 점마다 값 하나만 남기고 나머지 후보를 버리는데, 왜 답이 맞을까? 그리고 그 덕분에 얼마나 빨라질까?

표를 채우는 방법이 옳다는 것은 당연하지 않습니다. 원래 물음은 S에서 T까지의 모든 길을 하나씩 따로 계산해서(길을 이루는 변의 값을 ⊗로 곱해서) 전부 ⊕로 모으라는 것입니다. 최단 거리라면 길 S→A→D→E→T의 값은 2 + 2 + 2 + 3 = 9이고, 이런 값을 열 개의 길 모두에 대해 구한 뒤 가장 작은 것을 고르라는 뜻입니다. 식으로는 이렇게 적습니다.

말로 읽으면, S에서 T로 가는 길 p마다 그 길의 변 $e_1, e_2, \ldots, e_m$의 값을 차례로 ⊗로 이은 것을, 모든 길에 걸쳐 ⊕로 모은 것입니다. 그런데 표는 점마다 값 하나만 남기고 나머지를 버립니다. 버려도 되는 까닭은 중학교에서 배우는 식 하나입니다.

3 × 4 + 3 × 5 = 12 + 15 = 27이고, 3 × (4 + 5) = 3 × 9 = 27입니다. 왼쪽은 곱셈 두 번과 덧셈 한 번, 오른쪽은 덧셈 한 번과 곱셈 한 번입니다. 공통 인수를 묶어 내면 계산이 줄어듭니다.

지도에서 같은 일이 일어납니다. C를 지나 E로 가는 길은 모두 'S에서 C까지의 어떤 길' 뒤에 변 C → E(길이 3)를 이어 붙인 것입니다. S에서 C까지의 길은 S→A→C(길이 7)와 S→B→C(길이 5) 두 가지입니다. 두 길을 따로 이어 비교하면 min(7 + 3, 5 + 3) = min(10, 8) = 8이고, 먼저 모은 뒤 한 번만 이으면 min(7, 5) + 3 = 5 + 3 = 8입니다. 같은 답이니, C에는 5 하나만 남기고 7은 버려도 됩니다. 일반적으로 적으면 이렇습니다.

이 등식, 곧 ⊗가 ⊕에 대해 분배법칙⁠(distributive law)⁠을 만족한다는 사실 덕분에, 표를 채우는 방법은 모든 길을 따로 계산하는 방법과 같은 답을 냅니다. 한 점에서 성립하는 이 묶어 내기를 앞에서부터 차례로 모든 점에 적용하면 됩니다.

이득은 큽니다. 출발점과 도착점 사이에 점이 K개씩 놓인 층이 L개 있고, 이웃한 층의 점끼리 모두 이어진 격자를 생각합시다. 길 하나는 층마다 점을 하나씩 고르는 것이니, 길의 수는 K를 L번 곱한 $K^L$입니다. 층마다 점이 3개이고 층이 10개면 $3^{10} = 59{,}049$가지입니다. 6절의 은닉 마르코프 모델⁠(hidden Markov model)⁠의 격자(숨은 상태 K개, 시각 L개)가 바로 이런 모양입니다. 층이 개, 층마다 점이 개이면 길은 가지입니다. 길을 하나씩 계산하면 ⊕와 ⊗를 합쳐 번, 표를 채우면 번이면 됩니다. 차이입니다. 층의 수를 늘려 가며 두 수가 어떻게 달라지는지 아래 그림에서 보세요. 세로축은 로그 눈금이라, 1에서 10까지의 거리와 10에서 100까지의 거리가 같습니다. 그래서 곧은 선은 '층마다 같은 배수⁠(multiple)⁠로 커진다'는 뜻입니다.

길을 하나씩 세는 비용은 층이 하나 늘 때마다 약 K배가 되고, 표를 채우는 비용은 층이 하나 늘 때마다 2K² − K번씩 늘 뿐입니다. 셈은 이렇습니다. 층이 하나 늘면 이웃한 두 층 사이의 변 K × K = K²개가 새로 생기고, 변마다 ⊗를 한 번 하니 ⊗가 K²번 늡니다. 새 층의 점 K개는 저마다 들어오는 후보 K개를 ⊕로 모으는데, K개를 모으는 데는 ⊕가 K − 1번 필요하니 ⊕는 K(K − 1) = K² − K번 늡니다. 둘을 더하면 2K² − K번입니다. K = 3이면 18 − 3 = 15번입니다. 한쪽은 층마다 곱해지고(지수함수⁠, exponential function⁠), 다른 쪽은 층마다 더해집니다(일차함수). 음성 인식에서 1초 분량의 소리는 100개 남짓한 짧은 틀로 나뉘고 숨은 상태는 수천 개에 이르기도 합니다. 길을 하나씩 세는 일은 우주의 나이로도 끝나지 않지만, 표는 금방 찹니다.

그렇다면 분배법칙이 없으면 어떻게 될까요? 가장 짧은 길 대신 '길이가 목표 τ(그리스 글자 '타우')에 가장 가까운 길'을 찾는다고 해 봅시다. 연료를 딱 τ만큼 쓰고 싶을 때 같은 경우입니다. 모으는 연산 ⊕를 'τ에 더 가까운 쪽 고르기'로, 잇는 연산 ⊗는 그대로 덧셈으로 두고 똑같이 표를 채울 수는 있습니다. 그러나 답이 틀릴 수 있습니다. τ(지금 )를 바꿔 가며, 분홍 길(표의 답)과 청록 길(참 답)이 갈라지는 τ를 찾아보세요.

무엇이 깨졌는지 식으로 보면 분명합니다. 'τ에 가까운 쪽 고르기'를 near라고 적으면, τ = 10일 때 near(4, 7) = 7이지만 두 수에 똑같이 5를 더하면 near(9, 12) = 9입니다. 뒤에 같은 수를 더했을 뿐인데 고르는 쪽이 바뀝니다. 먼저 고르고 5를 더하면 near(4, 7) + 5 = 12이고, 먼저 더하고 고르면 near(9, 12) = 9이니 결과가 다릅니다. 기호로 적으면 b = 4, c = 7, a = 5일 때 (b ⊕ c) + a ≠ (b + a) ⊕ (c + a)이고, 분배법칙이 깨집니다. 지금 좋아 보이는 앞길이 끝까지 좋다는 보장이 없으니, 앞길 하나만 남기고 나머지를 버리면 안 됩니다.

최솟값은 다릅니다. 두 수에 같은 수를 더해도 어느 쪽이 작은지는 바뀌지 않습니다. min(4, 7) + 5 = 9이고 min(9, 12) = 9입니다. 그래서 가장 짧은 길의 앞부분은 그 자체로도 그 점까지 가장 짧은 길입니다. 앞부분을 더 짧은 길로 바꾸면 전체도 짧아지기 때문입니다. 벨먼이 '최적성의 원리⁠(principle of optimality)⁠'라 부른 성질이 최단 경로에서 성립하는 것은 바로 이 때문입니다.

버리지 않으면 고칠 수 있습니다. 점마다 '만들 수 있는 길이들의 집합⁠(set)⁠'을 통째로 적으면, 모으기는 합집합⁠(union)⁠, 잇기는 집합의 모든 원소⁠(element)⁠에 변의 길이를 더하기가 되고, 이 두 연산은 분배법칙을 만족합니다. 대신 칸 하나에 적을 것이 길이의 가짓수만큼 불어납니다.

정수⁠(integer)⁠들 가운데 몇 개를 골라 합이 정확히 τ가 되게 하는 부분집합 합 문제⁠(subset sum problem)⁠가 이 방법으로 풀립니다. 수 3, 5, 9에서 합 14를 만들 수 있는지 봅시다. 아무것도 고르지 않으면 만들 수 있는 합은 {0}입니다. 3을 쓸지 말지 정하면 {0, 3}, 5까지 정하면 {0, 3, 5, 8}, 9까지 정하면 {0, 3, 5, 8, 9, 12, 14, 17}이고, 14가 들어 있으니(5 + 9) 답은 '된다'입니다. 걸음마다 '안 쓰기'와 '쓰기'의 두 갈래를 합집합으로 모은 것입니다. 그런데 이 집합의 크기⁠(cardinality)⁠는 수들이 커질수록 커집니다. 수가 백만 단위라면 집합에 들 수 있는 합도 백만 가지를 넘을 수 있어서, 걸리는 시간이 수의 크기에 비례해 커집니다.

이 문제는 NP-완전⁠(NP-complete)⁠임이 알려져 있습니다. 답이 맞는지 확인하기는 쉽지만, 이 문제를 빨리 푸는 방법이 있다면 확인하기 쉬운 다른 모든 문제도 빨리 풀리게 되는, 그런 부류에서 가장 어려운 문제라는 뜻입니다. 여기서 '빨리'는 입력을 적는 자릿수 m에 대해 m², m³처럼 m의 거듭제곱 정도의 시간 안에 푼다는 뜻이고, 이런 시간을 다항 시간⁠(polynomial time)⁠이라 합니다. 'P = NP'는 '답을 쉽게 확인할 수 있는 문제는 모두 쉽게 풀 수도 있다'는 미해결 추측입니다. 이 추측이 참이 아닌 한, 부분집합 합 문제를 다항 시간에 푸는 알고리즘은 없습니다.

그렇다면 앞의 집합 방법은 왜 이 추측과 부딪치지 않을까요? 그 방법의 시간은 수의 크기에 비례하는데, 크기는 자릿수가 하나 늘 때마다 10배가 되니 다항 시간이 아닙니다. 정리하면, 분배법칙이 성립하는 작은 요약을 찾으면 표가 작고, 찾지 못하면 표가 커집니다.

'동적 계획법'이라는 이름은 응용수학자 리처드 벨먼이 1950년대 초 RAND 연구소에서 붙였습니다. 그는 자서전에서, 연구(research)라는 말을 몹시 싫어하던 국방 장관 윌슨의 눈을 피하려고 수학처럼 들리지 않는 이름을 골랐다고 회고했습니다. 다만 그가 이 말을 쓴 첫 논문(1952년)이 윌슨이 장관이 된 1953년보다 앞서서, 이 일화가 그대로 사실일 수는 없다는 지적이 있습니다. 여기서 'programming'은 컴퓨터 프로그램이 아니라 선형 계획법(linear programming)에서처럼 '계획표 짜기'를 뜻합니다.

RAND는 1948년 미 공군의 연구 계획에서 독립⁠(independence)⁠한 비영리 연구소로, 냉전기의 게임 이론⁠(game theory)⁠, 선형 계획법⁠(linear programming)⁠, 시스템 분석이 이곳을 거쳐 갔습니다. 벨먼이 붙든 것은 여러 단계에 걸친 결정 문제⁠(decision problem)⁠였습니다. 보급, 재고, 무기 배치처럼 지금의 선택이 다음 선택의 조건을 바꾸는 문제입니다. 1957년의 책 『동적 계획법』에서 그는 최적성의 원리를 내세우는 한편, 상태를 적는 변수가 하나 늘 때마다 채워야 할 표가 몇 배씩 불어나는 어려움을 '차원의 저주⁠(curse of dimensionality)⁠'라고 불렀습니다. 이 글의 표가 작았던 것은 점마다 수 하나만 적으면 되었기 때문입니다. 칸 하나가 변수 여럿의 조합을 적어야 한다면, 위의 부분집합⁠(subset)⁠ 합처럼 표 자체가 커집니다. 같은 저주가 높은 차원의 거리에서는 어떤 모습으로 나타나는지는 「까마귀와 택시」 8절에 있습니다. 같은 RAND에서 레스터 포드는 1956년 길이가 음수인 변이 있어도(길이가 음수인 고리만 없다면) 쓸 수 있는 최단 경로 방법을 내놓았습니다. 벨먼이 1958년 이를 동적 계획법으로 다시 정리했고, 오늘날 이것을 벨먼–포드 알고리즘⁠(Bellman–Ford algorithm)⁠이라 부릅니다.

3 · 두 연산의 약속1934년의 이름, 반환⁠(semiring)⁠

2절에서 분배법칙이 표 채우기를 되게 한다는 것을 보았습니다. 이 절의 물음은 이것입니다. 두 연산의 짝이 정확히 어떤 약속을 지켜야 표 채우기가 맞을까? 그 약속을 지키는 짝과 지키지 않는 짝은 어떻게 가려낼까?

지금까지 나온 연산의 짝을 표로 모아 봅시다. 마지막 줄은 4절에서 다시 나옵니다.

표의 0과 1은 보통의 수 0과 1이 아니라 역할의 이름입니다. 0은 '길 없음'(⊕의 항등원), 1은 '빈 길'(⊗의 항등원)입니다. 그래서 최단 거리 줄에서는 0 자리에 +∞가, 1 자리에 수 0이 옵니다. 이 짝들이 공통으로 지키는 약속은 네 가지입니다. 집합 하나와 두 연산 ⊕, ⊗, 그리고 두 원소 0, 1이 있어서 다음이 성립합니다. 괄호 안은 최단 거리의 (min, +)로 확인한 예입니다.

• ⊕는 결합법칙과 교환법칙⁠(commutative law)⁠을 만족하고 0이 항등원입니다. 갈래를 모으는 순서와 묶음은 상관없고, '길 없음'을 모아도 달라지지 않습니다. (min(min(3, 5), 2) = min(3, min(5, 2)) = 2, min(3, 5) = min(5, 3), min(3, ∞) = 3)
• ⊗는 결합법칙을 만족하고 1이 항등원입니다. 길을 어디서 끊어 잇든 같고, 빈 길을 이어도 달라지지 않습니다. 교환법칙은 요구하지 않습니다. 글자열을 이어 쓰는 순서는 중요하니까요(ab와 ba는 다른 글자열입니다). ((2 + 3) + 4 = 2 + (3 + 4), 3 + 0 = 3)
• ⊗는 ⊕에 대해 양쪽으로 분배됩니다. a ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c)이고 (b ⊕ c) ⊗ a = (b ⊗ a) ⊕ (c ⊗ a)입니다. ⊗가 교환되지 않을 수 있으니 양쪽을 따로 적습니다. (2 + min(3, 5) = min(2 + 3, 2 + 5) = 5)
• 0은 ⊗에 대해 흡수원입니다. 0 ⊗ a = a ⊗ 0 = 0. 길이 없는 곳에 무엇을 이어도 길은 없습니다. (∞ + 3 = ∞)

이 약속을 지키는 구조를 반환(半環, semiring)이라고 부릅니다. 연산 하나가 결합법칙을 지키고 항등원을 가지면 그 짝을 모노이드⁠(monoid)⁠라 하는데, 반환은 ⊕와 0이 교환하는 모노이드를, ⊗와 1도 모노이드를 이루고, 둘이 분배법칙으로 엮인 것입니다.

정수의 환(ring)과 다른 점은 빼기를 요구하지 않는다는 것입니다(정수처럼 빼기가 있는 환도 반환의 한 예입니다). 정수에서는 a + x = 0이 되는 x = −a가 늘 있습니다. 5 + (−5) = 0처럼요. 그러나 최단 거리에서 min(5, x) = +∞(길 없음)이 되게 하는 x는 없습니다. min(5, x)는 어떤 x를 넣어도 5 이하이기 때문입니다. 한 번 찾은 짧은 길을 '찾지 않은 것'으로 되돌릴 방법이 없는 것입니다. 그래서 '반쪽짜리 환'입니다.

흔히 min을 '덧셈'이라 부르는 것을 말장난으로 여기지만, 여기서 덧셈과 곱셈은 연산의 생김새가 아니라 역할의 이름입니다. 갈래를 모으는 쪽이 덧셈, 길을 잇는 쪽이 곱셈입니다. 그렇다고 아무 두 연산이나 짝지을 수는 없습니다. 아래 표에서 ⊕ 후보 세 가지(+, min, max)와 ⊗ 후보 네 가지(+, ×, min, max)를 짝지어 분배법칙이 성립하는지 확인했습니다. 칸을 누르면 그 짝이 골라지고(반례가 있으면 반례가 들어갑니다), a = , b = , c = 의 값을 바꿔 가며 직접 따져 볼 수 있습니다. 그림 아래에 a ⊗ (b ⊕ c)와 (a ⊗ b) ⊕ (a ⊗ c)가 한 걸음씩 계산되어 나오니, 두 값이 같은지 보면 됩니다.

표에서 규칙이 보입니다. ⊕가 min이나 max인 줄은 × 칸 하나만 빼고 모두 초록이고, × 칸도 0 이상에서는 됩니다. 까닭은 한 줄입니다. ⊗가 순서를 지키는 연산이면, 다시 말해 b ≥ c일 때 늘 a ⊗ b ≥ a ⊗ c이면, 큰 쪽을 먼저 고르고 a를 붙이든 a를 먼저 붙이고 큰 쪽을 고르든 같은 쪽이 뽑힙니다. 덧셈, min, max는 언제나 순서를 지키고, 곱셈은 a가 0 이상일 때만 지킵니다. −1을 곱하면 큰 수가 작은 수가 되어 max가 엉뚱한 쪽을 고릅니다. a = −1, b = 3, c = 2라면 먼저 고르면 −1 × max(3, 2) = −3이고, 먼저 곱하면 max(−3, −2) = −2입니다. 그래서 확률처럼 0 이상인 값에서는 (max, ×)가 반환이 되지만, 음수를 곱하는 곳에서는 안 됩니다. 반대로 ⊕가 +인 줄에서는 ⊗가 ×일 때만 됩니다. 이 후보들 가운데 덧셈 위로 분배되는 것은 곱셈뿐입니다.

표의 반환들은 두 부류로 나뉩니다. min, max, ∨처럼 모으기가 두 값 가운데 하나를 '고르는' 쪽에서는 답이 어느 한 길의 값이므로, 표를 채우며 고른 변을 기억해 두면 그 길을 되짚어 찾을 수 있습니다. 1절 그림의 청록 변이 그것입니다. +처럼 모으기가 '합치는' 쪽에서는 답이 어느 한 길의 값이 아니라 모든 길의 몫을 더한 것입니다. 개수나 전체 확률에서 '그 길'을 물을 수 없는 까닭입니다. 글자열의 합집합도 이쪽입니다. 같은 것을 두 번 모아도 그대로라는 점(a ⊕ a = a)은 min과 같지만, 모은 결과는 여러 글자열을 함께 담은 집합입니다.

정리하면, 반환은 '모으기는 순서와 묶음에 상관없고, 잇기는 끊는 자리에 상관없으며, 잇기가 모으기 위로 분배된다'는 약속이고, 이 약속을 지키는 짝이면 무엇이든 1절의 표 채우기가 맞는 답을 냅니다.

구조는 이름보다 먼저 있었습니다. 1871년 데데킨트가 정수론⁠(number theory)⁠에 들여온 아이디얼(어떤 수의 배수 전체처럼, 더하고 곱해도 빠져나가지 않는 수의 모임)들은 합과 곱에 대해 이 네 약속을 모두 지키지만, 아이디얼⁠(ideal)⁠을 '빼는' 방법은 없습니다. 페르마의 마지막 정리⁠(Fermat's Last Theorem)⁠를 증명했다는 발표가 무너진 자리에서 아이디얼이 태어난 이야기는 「틀린 증명이 만든 수학」 2–3절에 있습니다. '반환'이라는 이름은 1934년 텍사스 대학의 정수론자 해리 밴디버가 썼습니다. 덧셈의 소거 법칙(a + c = b + c이면 a = b)이 성립하지 않는 대수를 다룬 짧은 논문에서였습니다. 최단 거리의 min이 그런 예입니다. min(3, 1) = min(5, 1) = 1이지만 3과 5는 다릅니다. 이 구조가 널리 연구된 것은 1960–70년대에 마르셀폴 쉬첸베르제와 에일렌베르크 등이 오토마톤(글자를 하나씩 읽으며 상태를 바꾸는 단순한 기계)과 형식 언어⁠(formal language)⁠의 이론을 반환 위에 세우고, 경로 문제를 푸는 사람들이 같은 구조를 찾아내면서부터입니다.

연산을 생김새가 아니라 지키는 약속으로 정의하는 습관은 그리 오래되지 않았고, 처음에는 철학자의 반대에 부딪혔습니다. 1899년 힐베르트는 『기하학의 기초⁠(basics)⁠』에서 점과 직선과 평면이 무엇인지는 말하지 않고, 그것들이 지켜야 할 공리⁠(axiom)⁠만 적었습니다. 그해 말 이 책을 두고 프레게와 주고받은 편지에서 힐베르트는, 점들의 자리에 '사랑, 법, 굴뚝 청소부' 같은 것을 놓아도 공리를 만족하기만 하면 피타고라스 정리⁠(Pythagorean theorem)⁠ 같은 명제가 그대로 성립한다고 썼습니다. 프레게는 반대했습니다. 공리는 뜻이 이미 정해진 낱말에 관한 참인 문장이어야 하고, 낱말의 뜻을 바꿔 끼울 수 있는 문장은 참이라고도 거짓이라고도 할 수 없다는 것입니다. 두 사람의 차이를 어떻게 볼지는 철학에서 지금도 논의되지만, 대수학은 힐베르트의 길을 따랐습니다. 1920년대 괴팅겐의 에미 뇌터와 함부르크의 에밀 아르틴의 강의를 바탕으로 반 데르 바르던이 1930–31년에 낸 『현대 대수학』은 군과 환과 체를 약속의 목록으로 정의하고 다룬 첫 교과서 가운데 하나였고, 곧 대수학 교육의 표준이 되었습니다. 밴디버가 1934년 '빼기 없는 환'에 이름을 붙인 것도 이렇게 구조를 약속으로 가르는 방식이 자리 잡은 뒤였습니다. 이 글의 표 채우기가 ⊕와 ⊗가 '무엇인지' 묻지 않고 약속만 확인하는 것도 같은 생각입니다.

4 · 1951–1971고리가 있는 지도: 별표와 닫힘

1절의 지도에는 되돌아오는 길이 없었습니다. 화살표를 따라가면 늘 T 쪽으로만 나아가므로 점들을 한 줄로 세울 수 있었고, 앞에서부터 한 번씩만 계산하면 됐습니다. 실제 도로망에는 고리가 있습니다. A에서 B로, B에서 다시 A로 갈 수 있으면 길은 끝없이 많아집니다. A → B, A → B → A → B, A → B → A → B → A → B, …처럼 고리를 몇 번이든 더 돌 수 있기 때문입니다. 이 절의 물음은 이것입니다. 끝없이 많은 길을 어떻게 유한한 계산으로 모을까? 그리고 모은 값이 늘 잘 정해질까?

1954년 4월 뉴욕의 한 심포지엄에서 앨폰소 심벨은 통신망의 거리표를 구하는 방법을 발표했습니다(1955년 출판). 심벨은 원래 시카고 대학의 니콜라스 라셰브스키가 펴내던 『수리 생물물리학 회보』에 아나톨 라포포트와 함께 신경계의 통계⁠(statistics)⁠ 이론(1948)을 실었던 사람입니다. 1951년에는 같은 학술지에 통신망을 행렬로 다룬 논문을 실었습니다. 1943년 맥컬러와 피츠의 논리 뉴런 논문이 실린 바로 그 학술지입니다(「배우는 기계」 1절). 신경 그물을 셈하던 도구가 통신망의 거리로 옮겨 간 것입니다. 심벨의 방법은 두 수의 '합'을 최솟값으로, '곱'을 덧셈으로 바꾼 행렬 곱을 거듭하는 것입니다.

행렬은 수를 가로세로로 늘어놓은 표입니다. 아래 그림의 세 마을 지도(1 → 2 길이 4, 2 → 1 길이 1, 2 → 3 길이 2, 3 → 3 길이 3)로 거리표를 만들어 봅시다. i번째 줄 j번째 칸 $A_{ij}$에 'i에서 j로 곧장 가는 변의 길이'를 적고, 변이 없으면 ∞를 적습니다. 왼쪽 위에서 오른쪽 아래로 가는 대각선 칸은 '자기 자신으로 곧장 가는 변'의 자리입니다. 그런 변은 3 → 3 고리 하나뿐이라, 대각선에서는 3 → 3 칸만 3이고 나머지는 ∞입니다.

두 표 A와 B를 (min, +)로 곱하는 규칙은 이렇습니다.

말로 읽으면, 곱의 i번째 줄 k번째 칸은 중간 마을 j를 모두 훑으며 'i에서 j까지(A의 칸) 다음 j에서 k까지(B의 칸)'를 더해 보고, 그 가운데 가장 작은 것을 적는다는 뜻입니다. A를 자기 자신과 곱한 A²에서 1줄 3칸을 구해 봅시다. j = 1, 2, 3을 차례로 넣으면 $\min(\infty + \infty,\ 4 + 2,\ \infty + 3) = 6$입니다. 1에서 2를 거쳐 3으로 가는 길이 6의 길입니다. 같은 방법으로 2줄 2칸을 구하면 $\min(1 + 4,\ \infty + \infty,\ 2 + \infty) = 5$이고, 이것은 2 → 1 → 2의 길이입니다.

일반적으로 A²의 칸 (i, k)는 '변을 정확히 두 개 써서 i에서 k로 가는 가장 짧은 거리'이고, A³은 정확히 세 개입니다. 보통의 행렬 곱(더하기 자리에 +, 곱하기 자리에 ×)에서도 같은 일이 일어납니다. 변이 있는 칸에 1, 없는 칸에 0을 적은 표를 제곱하면, 칸마다 '변을 정확히 두 개 쓰는 길의 개수'가 나옵니다. 위의 계산은 이것을 (min, +) 반환에서 한 것입니다. 두 경우 모두 '변 없음' 자리에는 그 반환의 0이 들어갑니다. 개수에서는 수 0이고, 최단 거리에서는 ∞입니다.

대각선에 반환의 1, 곧 '제자리에 머무는 빈 길'을 더 적어 두면 뜻이 조금 바뀝니다. 최단 거리에서 반환의 1은 수 0이니, 대각선을 모두 0으로 바꾼 표가 됩니다. 이 표를 제곱하면 칸마다 '변을 많아야 두 개 써서 가는 가장 짧은 거리'가 나옵니다. 제자리에 머무는 걸음이 변 하나를 대신할 수 있기 때문입니다. 예를 들어 1 → 2 칸은 변 하나짜리 길 4가 그대로 남습니다.

행렬 곱은 결합법칙을 지킵니다. 다시 말해 (A ⊗ B) ⊗ C = A ⊗ (B ⊗ C)입니다. 이 등식은 반환의 약속(⊕의 결합·교환법칙, ⊗의 결합법칙, 분배법칙)만으로 증명됩니다. 그래서 어느 반환에서든 A³을 (A²)A로 구하든 A(A²)로 구하든 같습니다. 이 이야기는 반환 페이지의 그림에서 직접 거듭제곱해 볼 수 있습니다. 거리 공간⁠(metric space)⁠을 범주⁠(category)⁠로 읽는 풍부화된 범주⁠(enriched category)⁠로도 이어지는데, 9절의 '범주로' 항목에서 짧게 소개합니다.

길이가 제각각인 모든 길을 한꺼번에 모으려면 A의 거듭제곱을 모두 ⊕로 더해야 합니다. 여기서 A는 위에서처럼 곧장 가는 변만 적은 표입니다. 맨 앞의 1은 대각선에 반환의 1, 나머지에 반환의 0을 적은 단위 행렬로, 변을 하나도 지나지 않은 '빈 길'입니다. 최단 거리라면 대각선에 0, 나머지에 ∞를 적은 표입니다.

클리니의 이름을 따 '별표'(*)라 부르는 이 무한 합이 고리를 다루는 열쇠입니다. 수 하나의 별표 a* = 1 ⊕ a ⊕ a⊗a ⊕ …는 '같은 고리를 0번, 1번, 2번, … 도는 것을 모두 모은 값'이고, 반환마다 뜻이 뚜렷합니다. 최단 거리에서 길이 a ≥ 0인 고리는 돌아도 이득이 없으므로 a* = min(0, a, 2a, …) = 0입니다. 도달에서는 a* = 참입니다. 확률에서는 등비급수⁠(geometric series)⁠ 1 + p + p² + … = 1/(1 − p)이고(0 ≤ p < 1일 때), p = 0.5라면 1 + 0.5 + 0.25 + 0.125 + … = 2입니다. 개수에서는 고리가 하나라도 있으면 1 + 1 + 1 + …로 끝없이 커져 한 수로 정해지지 않습니다(발산⁠(divergence)⁠합니다). 최단 거리에서도 길이가 음수인 고리가 있으면 돌수록 짧아져 −∞가 됩니다. 별표가 잘 정해지느냐가 바로 '고리가 있어도 답이 있느냐'입니다.

로이와 워셜과 플로이드의 방법은 이 무한 합을 유한한 계산으로 구합니다. 마을에 번호를 붙이고, '마을 1만 거쳐 가도 되는 길', '마을 1과 2만 거쳐 가도 되는 길', …로 거쳐 가도 되는 마을을 하나씩 늘려 갑니다. 마을 k를 새로 허락하면, i에서 j로 가는 길은 k를 거치지 않거나, i에서 k로 가서 k에서 제자리로 도는 고리를 몇 번 돈 뒤 k에서 j로 가는 것입니다.

화살표 ←는 '오른쪽 값으로 칸을 고쳐 적는다'는 뜻입니다. 오른쪽은 'k를 거치지 않는 지금까지의 값'과 'i에서 k까지, k에서 고리를 몇 번이든, k에서 j까지'를 모은 것입니다. 세 마을 지도의 최단 거리로 확인해 봅시다. 처음 표에는 곧장 가는 변만 있어서 1 → 3 칸은 ∞입니다. 마을 1을 허락한 뒤 2 → 2 칸은 ∞에서 2 → 1 → 2의 길이 1 + 4 = 5로 바뀌고, 이제 마을 2를 허락하면 1 → 3 칸은 $\min(\infty,\ 4 + 0 + 2) = 6$이 됩니다. 가운데의 0은 (D₂₂)* = min(0, 5, 10, …) = 0이고, 이것은 '2에서 고리를 돌지 않는 것이 가장 좋다'입니다.

(D_kk)*는 최단 거리에서는 0, 도달에서는 참이라 눈에 띄지 않을 뿐, 워셜과 플로이드의 식에도 숨어 있습니다. 플로이드의 식이 옳으려면 길이가 음수인 고리가 없어야 하는 것도 이 때문입니다. 물음()을 바꿔 가며 세 마을의 표를 채워 보세요. 단추로 한 걸음씩 넘기면, 걸음마다 허락하는 마을이 하나씩 늘고 바뀐 칸이 노랗게 칠해집니다.

'정규 표현식'을 고르면 표에 글자열의 패턴이 찹니다. 정규 표현식은 글자열의 무늬를 적는 식입니다. 예를 들어 a(ba)*는 'a 다음에 ba를 0번 이상 되풀이한 글자열', 곧 a, aba, ababa, …를 뜻합니다. 변마다 글자를 붙이면 길은 글자열이 되고, 모으기는 '또는'(|), 잇기는 '이어 쓰기', 별표는 '0번 이상 되풀이'가 됩니다. 마지막 표의 1 → 3 칸 a(ba)*cd*는 마을 1에서 3으로 가는 모든 길의 글자열을 빠짐없이 적은 것입니다. 읽으면 'a로 2에 가고, ba(2 → 1 → 2 고리)를 0번 이상 돌고, c로 3에 가고, d(3의 제자리 고리)를 0번 이상 돈다'입니다. 예를 들어 길 1 → 2 → 1 → 2 → 3 → 3의 글자열 abacd가 이 무늬에 들어맞습니다. 클리니는 신경 그물과 유한 오토마톤⁠(finite automaton)⁠이 알아보는 글자열을 모두 정규 표현식으로 적을 수 있음을 보였는데, 그때의 계산이 바로 같은 표 채우기를 글자열의 반환에서 한 것입니다. 워셜과 플로이드의 방법이 클리니의 정리와 같은 뼈대라는 사실은 1970년대에 B. A. 카레, 롤런드 백하우스 같은 사람들이 이런 문제들의 공통 대수를 정리하면서 널리 알려졌습니다.

'들르는 횟수의 기댓값⁠(expected value)⁠'을 고르면 또 다른 얼굴이 나옵니다. 변의 수를 한 걸음에 그 변을 따라갈 확률로 읽고(나머지 확률만큼은 걷기를 그만둡니다), 모으기와 잇기를 보통의 +와 ×로 하면, A*의 칸 (i, j)는 i에서 출발한 사람이 j에 들르는 횟수의 기댓값입니다. 마을 3에는 확률 0.5로 제자리에 머무는 고리가 있어서 3 → 3 칸이 1/(1 − 0.5) = 2입니다. 처음 한 번 있는 것에 더해, 머물 확률 0.5로 한 번 더, 0.25로 두 번 더, …를 모두 더한 1 + 0.5 + 0.25 + … = 2입니다.

이제 수 하나에서 표로 넓혀 봅시다. 수 하나라면 1 + p + p² + … = 1/(1 − p)였습니다. 표에서도 같은 일이 일어납니다. 실수의 +와 ×에서는, 급수⁠(series)⁠ 1 ⊕ A ⊕ A² ⊕ …가 수렴⁠(convergence)⁠하면(걷는 사람이 언젠가는 반드시 멈추면) 그 합이 (I − A)⁻¹입니다. 여기서 I는 단위 행렬이고, (I − A)⁻¹은 I − A의 역행렬⁠(inverse matrix)⁠, 곧 I − A와 곱하면 단위 행렬이 되는 표입니다. 수의 1/(1 − p)를 표로 옮긴 것이라 보면 됩니다. 마르코프 연쇄⁠(Markov chain)⁠에서 '기본 행렬'이라 부르는 것입니다.

값 두 개로 확인해 봅시다. 2 → 2 칸은 2에서 출발한 사람이 2에 들르는 횟수의 기댓값입니다. 2를 떠나 1에 갔다가 2로 돌아올 확률은 2 → 1(0.3) 다음 1 → 2(0.5)이니 0.3 × 0.5 = 0.15입니다. 그러니 2 → 2 칸은 1 + 0.15 + 0.15² + ⋯ = 1/(1 − 0.15) = 1/0.85 ≈ 1.176입니다. 1 → 3 칸은 네 수를 곱해 얻습니다. 1에서 2로 갈 확률 0.5, 그 뒤 2에 들르는 횟수의 기댓값 1/0.85, 2에 들를 때마다 3으로 넘어갈 확률 0.4, 3에 들어간 뒤 3에 들르는 횟수의 기댓값 2입니다. 0.5 × (1/0.85) × 0.4 × 2 ≈ 0.471입니다. 단추를 끝까지 넘긴 그림의 두 칸도 1.176과 0.471입니다. I − A의 역행렬을 직접 풀어도 같은 값이 나옵니다.

그러니 같은 세 겹 반복은 이 반환에서 I − A의 역행렬을 구하는 계산입니다. 다시 말해 연립방정식을 변수 하나씩 지워 가며 푸는 가우스 소거법⁠(Gaussian elimination)⁠의 한 형태입니다. 최단 경로를 찾는 방법과 연립방정식을 푸는 소거법⁠(elimination)⁠은 반환만 다른 같은 계산입니다. 카레가 1971년 논문 「망 경로 문제를 위한 대수」에서 보인 것이 이런 대응입니다. 도박꾼의 파산⁠(gambler's ruin)⁠ 같은 흡수 확률 문제도 이 기본 행렬로 풉니다.

정리하면, 고리가 있는 지도에서는 고리를 몇 번 도는지까지 모두 모으는 별표가 필요하고, 로이–워셜–플로이드의 세 겹 반복은 어느 반환에서든 그 별표를 유한한 계산으로 구합니다. 별표가 끝없이 커지거나 작아지는 경우(개수를 세는데 고리가 있을 때, 최단 거리에 길이가 음수인 고리가 있을 때)에는 유한한 답도 없습니다.

5 · 1965–1999문장의 나무를 세는 표

반환은 길에서만 일하지 않습니다. 영어 문장 "she saw the man with a telescope"는 두 가지로 읽힙니다. 그녀가 망원경으로 남자를 보았다는 뜻과, 망원경을 가진 남자를 보았다는 뜻입니다. 문맥 자유 문법⁠(context-free grammar)⁠으로 말하면 이 문장에는 구문 트리⁠(tree)⁠가 두 개 있습니다. 전치사구 "with a telescope"가 동사구(saw the man)에 붙느냐, 명사구(the man)에 붙느냐의 차이입니다. 이 절의 물음은 이것입니다. 한 문장이 문법에 맞는지, 몇 가지로 읽히는지, 어느 읽기가 가장 그럴듯한지를 같은 표 하나로 답할 수 있을까?

문맥 자유 문법은 '큰 부분이 어떤 작은 부분들로 이루어지는가'를 적은 규칙들입니다. 이 절의 문법은 이렇습니다. S → NP VP(문장은 명사구 다음 동사구), VP → V NP(동사구는 동사 다음 명사구), VP → VP PP(동사구 뒤에 전치사구를 붙여도 동사구), NP → NP PP(명사구 뒤에 전치사구를 붙여도 명사구), NP → Det N(관사 다음 명사), PP → P NP(전치사 다음 명사구). 그리고 낱말마다 품사⁠(part of speech)⁠를 정한 규칙(NP → she, V → saw, Det → the, a, N → man, telescope, P → with)이 있습니다. 구문 트리⁠(parse tree)⁠는 문장 전체 S에서 출발해 이 규칙들을 거듭 써서 낱말들에 닿는 가지 그림입니다.

문법의 규칙이 모두 'A → B C'(기호 하나를 기호 둘로) 또는 'A → 낱말' 꼴이면, 문장의 모든 조각에 대해 '이 조각이 A가 될 수 있는가'를 짧은 조각부터 긴 조각 순으로 표에 채울 수 있습니다. 예를 들어 두 낱말 조각 "the man"은 the가 Det, man이 N이고 규칙 NP → Det N이 있으니 NP가 될 수 있습니다. 세 낱말 조각 "saw the man"은 saw(V)와 "the man"(NP)으로 자르면 규칙 VP → V NP로 VP가 됩니다. 긴 조각은 늘 더 짧은 두 조각으로 잘리니, 짧은 조각의 칸이 먼저 채워져 있으면 됩니다. 이 방법을 CYK 알고리즘⁠(CYK algorithm)⁠이라 부릅니다(이름의 내력은 이 절 끝에 있습니다).

얼마나 걸릴까요? 낱말이 n개인 문장에서 조각은 n(n + 1)/2개이고(이 문장은 n = 7이니 28개), 조각마다 자르는 자리가 많아야 n − 1개이므로, 문법을 고정하면 계산은 n³에 비례합니다. 트리를 하나씩 만들어 보는 것보다 훨씬 빠릅니다.

여기서도 칸 하나가 하는 일은 같습니다. 조각을 두 부분으로 자르는 모든 자리와 모든 규칙 A → B C에 대해, '규칙의 값 ⊗ 왼쪽이 B일 값 ⊗ 오른쪽이 C일 값'을 A에 ⊕로 모읍니다. 1절에서 '앞 점의 값 ⊗ 변의 값'을 모았던 것과 같은 모양이고, 자르는 자리가 들어오는 변 노릇을 합니다.

이 문법에는 규칙마다 확률도 붙어 있습니다. 예를 들어 VP → VP PP(전치사구를 동사구에 붙이기)는 0.3, NP → NP PP(명사구에 붙이기)는 0.2이고, NP → Det N은 0.6, Det → a는 0.5, N → telescope는 0.4입니다. 그러면 조각 "a telescope"가 NP일 값은 '가장 그럴듯한 트리' 물음에서 0.6 × 0.5 × 0.4 = 0.12입니다. 물음()을 바꿔 가며 표를 채우고, 칸을 눌러 그 칸의 계산을 보세요.

네 물음의 답을 나란히 놓아 봅시다. '문장인가'(∨, ∧)로는 이 문장이 문법에 맞는다는 것만 알고, '트리의 개수'(+, ×)로는 트리가 두 개라는 것을, '가장 그럴듯한 트리'(max, ×)로는 더 그럴듯한 트리의 확률 0.0009072를, '문장의 확률'(+, ×)로는 두 트리의 확률을 더한 문장 자체의 확률 0.001512를 얻습니다. 두 트리의 확률은 0.0009072와 0.0006048이어서, 이 문법은 '망원경으로 보았다' 쪽을 1.5배 더 믿습니다. 전치사구를 동사구에 붙이는 규칙의 확률(0.3)이 명사구에 붙이는 규칙의 확률(0.2)보다 크기 때문입니다. 두 트리는 VP → VP PP(0.3)와 NP → NP PP(0.2) 가운데 어느 것을 쓰느냐만 다르고 나머지 규칙은 똑같이 한 번씩 쓰니, 두 확률의 비는 0.3 : 0.2, 곧 1.5입니다.

1999년 조슈아 굿맨은 논문 「반환 구문 분석」에서 이것을 정식으로 보였습니다. 문장을 알아보는 기계, 트리를 세는 기계, 가장 그럴듯한 트리를 찾는 비터비 구문 분석기⁠(parser)⁠, 조각마다 그 조각이 A일 확률을 모든 트리에 걸쳐 더한 '안쪽 확률⁠(inside probability)⁠'을 구하는 기계는 모두 같은 알고리즘이고 반환만 다르다는 것입니다. 반환을 하나 새로 만들면 새 구문 분석기가 저절로 생깁니다. '가장 좋은 트리 k개'를 모으는 반환, 트리 자체의 목록을 모으는 반환이 그런 예입니다. 트리의 개수는 금방 커집니다. 규칙 A → A A와 A → 낱말만 있는 문법에서 낱말 n개로 만들 수 있는 트리의 수는 카탈랑 수⁠(Catalan number)⁠ C_n−1이고, 낱말이 20개면 17억 개가 넘습니다. 개수의 반환으로 표를 채우면 트리를 하나도 만들지 않고 그 수를 셉니다. 정리하면, 문장의 구문 분석도 '조각을 자르는 자리마다 잇고, 모두 모은다'는 같은 표 채우기이고, 반환을 바꾸면 같은 표가 다른 물음에 답합니다.

이 표 채우기는 1965년 가사미 다다오와 1967년 대니얼 영거가 따로 발표했고, 존 코크의 이름을 함께 붙여 CYK 알고리즘이라 부릅니다. 가사미의 방법은 미 공군 케임브리지 연구소의 보고서로 나왔습니다. 이 무렵 문장의 구조를 기계로 읽는 일은 두 곳에서 급했습니다. 알골 같은 새 프로그래밍 언어를 기계어로 옮기는 컴파일러⁠(compiler)⁠, 그리고 냉전기 미국 정부가 러시아어 과학 문헌을 읽으려고 큰돈을 댄 기계 번역입니다. 1966년 미국 국립 과학원의 ALPAC 보고서가 기계 번역⁠(machine translation)⁠을 비관적으로 평가한 뒤 연구비가 크게 줄었지만(「말을 세는 기계」), 그 무렵 다듬어진 구문 분석의 방법들은 컴파일러와 언어학에 남았습니다.

6 · 1967년 로스앤젤레스가장 그럴듯한 하나와 모두의 합

이 절의 물음은 이것입니다. 같은 격자에서 '가장 그럴듯한 설명 하나'를 묻는 것과 '모든 설명의 확률을 더한 것'을 묻는 것은 어떻게 다르고, 어떻게 같을까?

1967년 4월, UCLA의 앤드루 비터비는 잡음 섞인 통신로로 보낸 합성곱 부호⁠(convolutional code)⁠를 풀어내는 방법을 발표했습니다. 합성곱 부호는 보낼 비트마다 바로 앞의 비트 몇 개와 섞어 여분의 비트를 만들어 붙이는 오류 정정 부호입니다. 그래서 부호기는 '바로 앞의 비트 몇 개가 무엇이었나'라는 몇 개의 상태를 오가며 비트를 내보내고, 받는 쪽은 잡음에 뭉개진 신호만 봅니다. 가능한 상태열은 시각마다 가지를 쳐서 지수적으로 불어나지만, 비터비의 방법은 시각마다 상태 하나당 '거기서 끝나는 가장 그럴듯한 앞길' 하나만 남겼습니다. 1절의 (max, ×) 계산 그대로입니다.

그런데 비터비 자신은 이 방법을 최적의 복호기⁠(decoder)⁠로 내세우지 않았습니다. 오류 확률의 한계를 증명하는 도구로 내놓았을 뿐이고, 포니의 회고에 따르면 저장 공간이 너무 많이 들어 실용적이지 않다고 보았다고 합니다. 곧이어 코덱스사의 데이비드 포니가 상태들을 시간 축에 펼친 격자 그림을 그려, 이것이 격자 위의 최단 경로를 정확히 찾는 방법, 곧 최적의 복호기라는 것을 알아보았습니다. UCLA의 짐 오무라는 1968년 5월에 투고한 논문(1969년 출판)에서, 이것이 벨먼의 동적 계획법을 최대 가능도⁠(likelihood)⁠ 복호(받은 신호가 나올 확률이 가장 큰 원래 비트열을 고르는 복호)에 쓴 표준적인 형태라고 지적했습니다. 비터비 복호는 보이저 탐사선의 통신과 디지털 휴대전화에 들어갔습니다.

0부터 1까지의 확률 위의 (max, ×)는, 0 이상의 수와 +∞ 위의 (min, +)와 이름만 다른 같은 반환입니다. 3절 표의 최단 거리처럼 음수까지 쓰는 (min, +)와는 범위가 다릅니다. 확률 p를 −log p로 바꾸면 곱은 합이 되고, 큰 확률은 작은 수가 되어 max는 min이 됩니다. 확률 0은 +∞로, 확률 1은 0으로 갑니다. 밑이 2인 로그로 확인해 봅시다($\log_2 x$는 '2를 몇 번 곱해야 x가 되는가'이고, 1보다 작은 x에서는 음수입니다). 확률 0.5는 −log₂ 0.5 = 1로, 0.25는 2로 갑니다. 곱 0.5 × 0.5 = 0.25는 합 1 + 1 = 2가 되고, max(0.5, 0.25) = 0.5는 min(1, 2) = 1이 됩니다. 이렇게 원소의 이름만 바꾸는 일대일 대응⁠(one-to-one correspondence)⁠이 두 연산과 두 항등원을 모두 보존하므로, 한쪽의 계산은 그대로 다른 쪽의 계산입니다. 로그가 곱셈을 덧셈으로 바꾼다는 사실을 반환 전체에 적용한 것입니다. 실제 음성 인식기가 확률을 곱하지 않고 −log 확률을 더하는 것도 이 때문입니다. 아주 작은 확률을 수백 번 곱하면 컴퓨터의 수가 0으로 뭉개지지만, 로그를 더하면 그런 일이 없습니다.

은닉 마르코프 모델은 눈에 보이지 않는 상태가 정해진 확률에 따라 시각마다 바뀌고, 상태마다 정해진 확률에 따라 눈에 보이는 신호를 내놓는다고 보는 모형입니다. 음성 인식이라면 숨은 상태는 지금 내는 소리의 단위이고, 보이는 신호는 마이크에 잡힌 짧은 소리 조각입니다. 시각을 층으로, 상태를 층의 점으로 펼치면 2절의 격자가 됩니다. 이 모델에서는 같은 격자에 두 물음이 있습니다. '이 소리를 낸 가장 그럴듯한 상태열은 무엇인가?'는 (max, ×)의 비터비 알고리즘이고, '이 모형이 이 소리를 낼 확률은 모두 얼마인가?'는 (+, ×)의 전방 알고리즘입니다. 1960년대 후반 프린스턴 방위 분석 연구소의 레너드 바움 등이 모형의 확률을 자료에 맞추는 방법(1970년 논문)을 만들 때 쓴 것이 뒤쪽입니다. 두 알고리즘은 max와 +, 한 곳만 다릅니다. 앞의 물음은 가장 그럴듯한 설명 하나를 묻고, 뒤의 물음은 모든 설명의 몫을 더합니다. 설명 하나가 압도적인 자료에서는 두 값이 비슷하고, 여러 설명이 비슷하게 그럴듯한 자료에서는 크게 다릅니다. 5절의 문장에서 0.0009072와 0.001512의 차이가 그것입니다. 정리하면, '가장 그럴듯한 하나'와 '모두의 합'은 모으기 자리에 max를 넣느냐 +를 넣느냐의 차이이고, 나머지 계산은 한 글자도 다르지 않습니다.

비터비 자신도 여러 곳을 지나왔습니다. 1935년 이탈리아 베르가모의 유대인 집안에서 태어난 그는 무솔리니 정권의 인종법을 피해 1939년 가족과 함께 미국으로 건너갔습니다. MIT를 거쳐 제트 추진 연구소(JPL)에서 탐사선 통신을 연구했고, 1968년 동료들과 링커빗을, 1985년 어윈 제이컵스 등과 퀄컴을 세웠습니다. 퀄컴이 내세운 휴대전화 방식 CDMA(부호 분할 다중 접속⁠, code-division multiple access⁠)는 비터비 복호로 푸는 합성곱 부호를 부품으로 썼습니다. 이 방식을 처음 나라 규모로 상용화한 곳이 한국입니다. 1993년 한국 정부는 CDMA를 이동 통신 표준으로 정했고, 전자통신연구원(ETRI)과 국내 전자 회사들이 퀄컴과 함께 개발한 끝에 1996년 1월 인천과 부천에서 세계 첫 상용 서비스가 시작되었습니다. 비터비가 1967년 증명의 도구로 내놓은 계산이 30년 가까이 지나 한국의 휴대전화 속에서 돌게 된 것입니다. 우주 탐사선이 이 부호를 어떻게 겹쳐 썼는지는 「잡음 너머로」 7절에 있습니다.

1934년의 이름에서 1970년까지. 수학 줄(파랑)에서 밴디버의 이름(1934)이 홀로 앞서고, 클리니의 정규 사건(1951), 벨먼의 동적 계획법, 심벨의 최소-합 행렬, 로이·워셜·플로이드, CYK, 비터비(1967)가 스무 해가 안 되는 사이에 몰려 있습니다. 여러 사람이 서로 다른 물음에서 같은 계산에 이르렀습니다. 로스앤젤레스 일대(RAND, UCLA, JPL)에 점이 모여 있는 것도 보세요.

7 · 2000년 패서디나일반화된 분배법칙⁠(generalized distributive law)⁠

이 절의 물음은 이것입니다. 길이나 문장이 아니라, 서로 얽힌 여러 불확실한 사실에서 확률을 계산할 때도 같은 묶어 내기가 통할까? 그리고 그 틀은 어디까지 넓어질까?

확률 추론으로 가 봅시다. 비가 오면(R) 잔디가 젖고(W), 잔디가 젖으면 미끄러지고(S), 미끄러지면 다친다(H)는 사슬을 생각합시다. 각 단계는 조건부 확률⁠(conditional probability)⁠로 주어집니다. P(w | r)는 'r일 때 w일 확률'이라고 읽습니다. 예를 들어 P(젖음 | 비)는 비가 왔을 때 잔디가 젖을 확률입니다. 다칠 확률 P(H)를 구하려면 R, W, S가 취할 수 있는 값의 모든 조합마다 확률을 곱해 더해야 합니다.

Σ(시그마)는 아래 적힌 변수의 모든 값에 대해 더하라는 기호입니다. 그러니 이 식은 '비가 왔는지(r), 잔디가 젖었는지(w), 미끄러졌는지(s)의 모든 조합마다 네 확률을 곱해, 그것들을 모두 더하라'는 뜻입니다. 변수마다 두 값(그렇다, 아니다)이면 조합은 2³ = 8개이고, 사슬에 숨은 변수가 n개면 2ⁿ개입니다. 그런데 분배법칙으로 합을 안쪽으로 밀어 넣을 수 있습니다.

무엇을 했는지 한 걸음씩 봅시다. r에 대해 더하는 동안 P(s | w)와 P(H | s)에는 r이 들어 있지 않아서, r이 바뀌어도 같은 값입니다. 그러니 a × b + a × c = a × (b + c)처럼 그 둘을 r의 합 바깥으로 묶어 낼 수 있습니다. 같은 이유로 P(H | s)를 w의 합 바깥으로 묶어 냅니다. 안쪽부터 계산하면 맨 안쪽 합 $\sum_r P(w \mid r)\,P(r)$은 w의 값마다 수 하나, 곧 잔디가 젖을 확률 P(w)이고, 그다음 합은 미끄러질 확률 P(s)입니다. 칸마다 수 두 개(그렇다, 아니다)만 적으면 되니, 곱셈이 사슬의 길이 n에 비례하는 만큼만 필요합니다. 이것은 2절의 격자에서 표를 채운 것과 똑같은 일입니다. 변수가 격자의 층, 변수의 값이 층의 점, 조건부 확률이 변의 값입니다. 이 계산에 베이즈 정리⁠(Bayes' theorem)⁠를 더하면, 사슬의 끝(다쳤다)을 보고 처음(비가 왔을까)을 거꾸로 추론할 수 있습니다.

변수들이 사슬이 아니라 나무 모양으로 얽혀 있어도 같은 일을 할 수 있습니다. 1982년 UCLA의 주디아 펄은 나무 모양의 확률 그물에서 이웃한 변수끼리 '메시지'를 주고받아 모든 변수의 확률을 한꺼번에 구하는 '믿음 전파⁠(belief propagation)⁠'를 발표했습니다. 메시지 하나는 '내 쪽 가지의 모든 가능성을 합쳐 요약한 값'이고, 이렇게 요약해도 되는 것은 역시 분배법칙 덕분입니다. 합을 max로 바꾸면 같은 메시지 전달이 가장 그럴듯한 설명 하나를 찾습니다.

2000년 칼텍의 스리니바스 아지와 로버트 매클리스는 논문 「일반화된 분배법칙」에서 이런 알고리즘들을 하나로 묶었습니다. ⊗도 교환법칙을 만족하는 반환(가환 반환⁠, commutative semiring⁠) 위에서, 여러 변수의 함수⁠(function)⁠들을 ⊗로 곱하고 몇몇 변수에 대해 ⊕로 모으는 문제를 생각합시다. 변수들의 관계가 나무 모양으로 정리되기만 하면, 이 문제는 이웃 사이의 메시지 전달로 효율적으로 풀립니다. 그들이 이 틀의 특수한 경우로 꼽은 목록에는 이 글에서 본 것들이 들어 있습니다. 6절의 비터비 알고리즘과 바움–웰치 알고리즘(바움 등이 만든, 모형의 확률을 자료에 맞추는 방법), 방금 본 펄의 믿음 전파, 그리고 아래에서 볼 고속 푸리에 변환입니다. 여기에 오류 정정 부호⁠(error-correcting code)⁠를 푸는 알고리즘 몇 가지와 확률 그물을 계산하는 다른 방법들이 더해집니다. 고속 푸리에 변환⁠(fast Fourier transform)⁠은 정확히는 유한 아벨 군(시계의 덧셈처럼 원소가 유한하고 계산 순서를 바꿔도 되는 군) 위의 것입니다. 모두 '여러 요인을 ⊗로 곱하고 보이지 않는 변수에 대해 ⊕로 모으는' 계산이라는 점은 같습니다.

목록 가운데 고속 푸리에 변환이 가장 뜻밖입니다. 푸리에 변환은 자료 $x_0, x_1, \ldots, x_{n-1}$을 진동수⁠(frequency)⁠가 다른 파동들로 나누는 계산이고, j번째 결과는 합 $\sum_k x_k\,\omega^{jk}$입니다. 여기서 ω(오메가)는 n번 곱하면 1이 되는 복소수⁠(complex number)⁠로, 한 바퀴를 n등분한 회전⁠(rotation)⁠을 뜻합니다. 이 합도 지수 jk를 j와 k의 자릿수들로 쪼개면 곱의 꼴이 되고, 분배법칙으로 합을 안으로 밀어 넣을 수 있습니다. 그 결과가 곱셈 n²번을 n log n번 정도로 줄인 FFT(고속 푸리에 변환)입니다. 아래 상자에서 n = 4로 직접 쪼개 볼 수 있습니다.

나무 모양이 아니면 어떻게 될까요? 변수들 사이에 고리가 있으면 메시지가 돌고 돌아 자기에게 되돌아오고, 정확한 답이 보장되지 않습니다. 고리를 없애려고 변수들을 크게 묶으면 묶음마다 경우의 수⁠(number of cases)⁠가 지수적으로 커집니다. 그래도 아지와 매클리스가 적었듯이, 고리가 있는 그래프에서 메시지 전달을 그냥 되풀이해도 근사로는 잘 맞는 경우가 많다는 실험적 증거가 많습니다. 다만 이를 뒷받침하는 정리는 일부뿐입니다. 휴대전화와 위성 방송에 쓰이는 터보 부호⁠(turbo code)⁠와 LDPC 부호⁠(low-density parity-check code)⁠가 이렇게 풀립니다. 정리하면, 변수들이 나무처럼 얽혀 있는 한 확률 추론도 이웃끼리 요약을 주고받는 표 채우기이고, 그 요약이 옳은 까닭은 여기서도 분배법칙입니다.

이 연결은 거꾸로 발견되었습니다. 1993년 프랑스 브레스트의 클로드 베루 연구진이 터보 부호를 발표했을 때, 그 복호법은 두 복호기가 서로의 추측을 주고받기를 되풀이하는 공학적 요령이었고, 왜 섀넌의 한계에 그토록 가까이 가는지는 설명되지 않았습니다. 1998년 매클리스와 데이비드 매케이, 정푸 청은 논문 「펄의 믿음 전파 알고리즘의 한 예로서의 터보 복호」에서, 그 요령이 펄의 믿음 전파를 고리가 있는 그래프에 그대로 돌린 것임을 보였습니다. 인공지능⁠(artificial intelligence)⁠의 확률 추론과 통신 공학이 서로를 모른 채 같은 계산에 이른 것입니다. 1960년 로버트 갤러거가 박사 논문에서 LDPC 부호를 풀려고 쓴 방법도 같은 메시지 전달이었습니다. 이 부호들이 섀넌의 약속에 다가간 역사는 「짧게 보내기」 7절과 「잡음 너머로」 7절에 있고, 펄이 믿음 전파 다음에 세운 인과⁠(causation)⁠의 그래프는 「담배와 폐암」에 있습니다.

따로 자란 알고리즘들이 하나로 묶이기까지. 카레의 경로 대수(1971), 시몬의 (min, +) 오토마톤(1978), 펄의 믿음 전파(1982), 굿맨의 반환 구문 분석(1999), 아지–매클리스의 일반화된 분배법칙(2000), 미칼킨의 열대 곡선(2005)이 수학 줄에 이어집니다. 역사 줄의 퀄컴 창업과 과학 줄의 보이저는 이 계산이 실제 통신에 들어간 자리입니다.

8 · 온도를 낮추면로그, 소프트맥스, 열대 기하⁠(geometry)⁠

(+, ×)와 (max, +)는 전혀 다른 세계처럼 보이지만, 로그를 거치면 하나로 이어진 가족입니다. 6절에서는 확률 p를 −log p로 바꿔 (min, +)를 얻었습니다. 이 절에서는 부호를 뒤집지 않은 log를 써서 (max, +)를 얻습니다. 두 반환은 모든 수에 −1을 곱한 것만 다릅니다. 수에 −1을 곱하면 덧셈은 그대로 덧셈이고, 가장 작은 것은 가장 큰 것이 되기 때문입니다. 그러니 6절의 (min, +) 비터비와 이 절의 (max, +) 비터비는 같은 계산입니다. 이 절의 물음은 이것입니다. 모두 더하는 계산과 가장 큰 것 하나를 고르는 계산 사이를 연속으로 오갈 수 있을까? 오갈 수 있다면, 그 사이의 다이얼은 무엇일까?

먼저 도구 두 가지를 적어 둡니다. e는 약 2.718인 수이고, $e^x$는 'e를 x번 곱한 것'을 모든 실수 x로 넓힌 값입니다. 여기서 log는 그 거꾸로 'e를 몇 번 곱해야 그 수가 되는가'(자연로그⁠, natural logarithm⁠)입니다. 그래서 $\log(e^x) = x$이고, 로그는 곱을 합으로 바꿉니다: $\log(xy) = \log x + \log y$.

이제 '온도'라고 부를 양수 T를 하나 정하고, 두 수의 '합'과 '곱'을 이렇게 정의해 봅시다.

수로 먼저 확인합니다. T = 1이면 $1 \oplus_1 0 = \log(e + 1) \approx 1.31$입니다. T = 0.1이면 $1 \oplus_{0.1} 0 = 0.1 \log(e^{10} + 1) \approx 1.000005$로, 두 수 가운데 큰 쪽 1과 거의 같습니다. 온도를 낮출수록 '합'이 '큰 쪽 고르기'에 다가갑니다.

이 이상한 연산이 반환인 까닭은 이렇습니다. 0 이상의 수 x마다 새 이름 a = T log x를 붙인다고 합시다(x ↦ T log x라 적고, 'x를 T log x로 부른다'고 읽습니다). 거꾸로 x = e^a/T입니다. 그러면 보통의 합 x + y는 새 이름으로 T log(e^a/T + e^b/T) = a ⊕_T b가 되고, 보통의 곱 xy는 T log(xy) = T log x + T log y = a + b가 됩니다. 수 0은 −∞로, 1은 0으로 갑니다. 이름만 바꾸었으니 (+, ×)가 지키던 반환의 약속을 그대로 지키고, T가 얼마든 반환입니다.

그런데 T를 0으로 보내면 어떻게 될까요? $e^{a/T}$와 $e^{b/T}$ 가운데 큰 것은 $e^{\max(a,b)/T}$이니, 둘의 합은 그것 이상이고 그것의 두 배 이하입니다. 양쪽에 T log를 씌우면 이렇게 됩니다.

오른쪽 끝의 T log 2는 T가 0에 다가가면 0에 다가가므로 ⊕_T는 max에 다가갑니다. 두 수가 같을 때(a = b) 차이가 가장 커서 꼭 T log 2가 됩니다. 그러니 (max, +) 반환은 (+, ×) 반환의 '온도 0 극한⁠(limit)⁠'입니다. 이 극한은 온도에 따라 연속으로 바뀌는 반환들의 끝이지, T = 0에서 로그를 그대로 쓸 수 있다는 뜻은 아닙니다.

그림으로 보면 더 분명합니다. 세 항 a₀, a₁ + x, a₂ + 2x가 있다고 합시다. 매끄러운 곡선 T log(e^a₀/T + e^(a₁+x)/T + e^(a₂+2x)/T)는 보통의 다항식⁠(polynomial)⁠ c₀ + c₁y + c₂y²(c_i = e^a_i/T, y = e^x/T)을 밑이 e^1/T인 로그 눈금에서 본 것입니다. 온도를 낮추면 이 곡선은 세 직선의 위쪽 테두리, 곧 꺾은선 max(a₀, a₁ + x, a₂ + 2x)에 달라붙습니다. 이 꺾은선이 (max, +) 반환에서의 다항식, '열대 다항식⁠(tropical polynomial)⁠'입니다. 온도 T(지금 )를 바꾸고, 세 점을 위아래로 끌어 계수를 바꿔 보세요. 볼 것은 온도를 낮출수록 청록 곡선이 노란 꺾은선에 얼마나 달라붙는지, 그리고 둘이 가장 크게 벌어지는 곳이 어디인지입니다.

지금 T = 이고, 로그의 밑 e^1/T는 약 입니다. 그림의 범위에서 곡선과 꺾은선의 차이는 가장 큰 곳에서 이고, 이론적 상한⁠(upper bound)⁠은 T log 3 = 입니다. 꺾이는 곳은 x = 입니다. 곡선과 꺾은선은 꺾이는 곳 근처에서 가장 크게 벌어집니다. 두 항의 값이 비슷해서 '모두 더하기'와 '큰 것 고르기'가 가장 다른 곳이기 때문입니다(두 수가 같을 때 차이가 T log 2였던 것과 같습니다). 가운데 항의 계수를 내리면 그 항이 한 번도 가장 크지 않게 되어 꺾이는 곳이 하나로 줄어드는 것도 확인해 보세요.

이 극한은 우리가 이미 두 곳에서 쓰고 있습니다. 하나는 6절의 두 알고리즘입니다. 전방 알고리즘⁠(forward algorithm)⁠을 로그 확률로 계산하면 모으기가 log(e^a + e^b), 이른바 로그합지수⁠(log-sum-exp)⁠가 되고, 비터비는 그 자리에 max를 씁니다. 로그 확률 위에서 ⊕_T를 쓰면 T = 1이 전방 알고리즘이고, T → 0의 극한이 비터비 알고리즘입니다. 비터비는 전방 알고리즘의 온도 0 판입니다. 다른 하나는 신경망의 소프트맥스입니다. 소프트맥스는 점수 a₁, …, a_n을 확률로 바꾸는 식으로, i번째 확률이 e^a_i/T ÷ (e^a₁/T + … + e^a_n/T)입니다. 점수 2와 1이라면 T = 1에서 e² ÷ (e² + e) ≈ 0.73, T = 0.1에서 e²⁰ ÷ (e²⁰ + e¹⁰) ≈ 0.99995입니다. 이것은 로그합지수 T log Σ e^a_i/T를 a_i로 미분⁠(differentiation)⁠한 것입니다. 다시 말해 a_i를 조금 늘릴 때 로그합지수가 따라 느는 비율입니다. 온도를 0으로 보내면 가장 큰 점수 하나에 모든 확률이 몰립니다(가장 큰 점수가 여럿이면 그들끼리 나눕니다). 언어 모델⁠(language model)⁠의 디코딩에서 온도를 낮출수록 가장 그럴듯한 낱말만 고르게 되는 것이 이 극한입니다(「다음 단어를 맞히는 기계」 9절).

정리하면, 로그로 이름을 바꾼 (+, ×)에는 온도라는 다이얼이 있고, 다이얼을 0으로 돌리면 '모두 더하기'가 '가장 큰 것 고르기'가 됩니다. 전방 알고리즘에서 비터비로, 소프트맥스에서 최댓값 고르기로 가는 길이 이 다이얼입니다.

러시아의 빅토르 마슬로프와 그리고리 리트비노프 같은 수학자들은 이 극한을 양자역학에서 플랑크 상수(양자 효과의 크기를 정하는 아주 작은 상수)를 0으로 보내 고전역학을 얻는 것에 빗대어 '탈양자화⁠(dequantization)⁠'라고 불렀습니다.

'열대'라는 이름은 브라질에서 왔습니다. 헝가리에서 태어나 브라질의 상파울루 대학에서 일한 컴퓨터 과학자 이므레 시몬은 1978년 (min, +) 산술 위의 오토마톤⁠(automaton)⁠으로 오토마톤 이론의 한 문제를 풀었습니다. 정규 언어⁠(regular language)⁠ L을 몇 번이고 이어 붙인 L*이 사실은 어떤 유한 번까지만 이어 붙여도 다 나오는지를 판정하는 문제입니다. 프랑스의 동료들이 그를 기려 이 반환을 '열대'라고 불렀고, 이 이름이 굳었습니다. 누가 처음 그렇게 불렀는지는 사람마다 기억이 엇갈립니다. 2000년대 들어 이 산술은 기하학으로 번졌습니다. 열대 다항식이 꺾이는 곳들이 이루는 꺾은선 도형, 곧 '열대 곡선'은 보통의 대수 곡선을 로그 눈금으로 보고 온도를 0으로 보낸 뼈대입니다. 2005년 그리고리 미칼킨은 이런 셈 문제를 다루었습니다. 평면에서 주어진 점들을 지나고 차수와 종수(곡면으로 보았을 때 구멍의 수)가 정해진 곡선은 몇 개인가? 그는 곡선 대신 이 꺾은선 도형들을 알맞은 가중치⁠(weight)⁠를 붙여 세면 이 문제가 풀린다는 것을 증명했습니다. 매끄러운 곡선에 관한 물음이 반환을 바꾸자 선분의 조합을 세는 물음이 된 것입니다.

9 · 이어지는 길한 줄의 계산이 닿는 곳

'갈래는 ⊕로 모으고 길은 ⊗로 잇는다'는 한 줄은 이 사이트의 여러 분야를 가로지릅니다.

• 그래프로: 데이크스트라의 방법은 가까운 곳부터 값을 확정하는데, 이것은 모으기가 '고르기'이고 잇기가 값을 좋게 만들지 않을 때(최단 거리라면 길이가 음수인 변이 없을 때) 옳습니다. 이 조건이 깨지면 이미 확정한 값이 나중에 더 좋아질 수 있어서 틀린 답을 낼 수 있습니다. 그래서 가장 넓은 길에는 그대로 쓰이지만 길의 개수에는 쓸 수 없습니다. 데이크스트라의 방법과 지도 위의 최단 경로는 「일곱 다리의 도시」 5절에 있습니다. (min, max) 짝이 찾는 길, 곧 가장 높은 고개가 가장 낮은 길은, 방향이 없는 지도라면 최소 신장 트리⁠(minimum spanning tree)⁠ 위에 있습니다.
• 선형대수⁠(linear algebra)⁠로: 반환 위에서도 행렬의 곱⁠(matrix multiplication)⁠은 결합법칙을 지키고, 별표 A*는 실수에서 (급수가 수렴할 때) (I − A)⁻¹이 됩니다. 그래서 최단 경로의 표 채우기와 가우스 소거법은 반환만 다른 같은 모양의 계산입니다. 소거법의 역사는 「잃어버린 소행성」 5절의 『구장산술』 이야기에 있습니다.
• 범주로: 범주는 대상들(여기서는 마을)과 대상 사이의 화살표들(여기서는 길), 그리고 화살표를 이어 붙이는 규칙으로 이루어진 구조입니다. 그래프의 길들은 이렇게 이어 붙이기를 합성으로 하는 범주를 이룹니다. 변에 반환의 값을 붙이는 일은 이 범주에서 모노이드 (S, ⊗, 1)로 가는 함자⁠(functor)⁠를 정하는 일과 같습니다. 함자는 한 구조의 화살표를 다른 구조로 옮기되 이어 붙이기를 지키는 대응입니다. 여기서는 길마다 값을 하나 주되, 이어 붙인 길에는 두 값의 ⊗를 줍니다. 로베어는 거리 공간을 풍부화된 범주로 읽었습니다. 두 대상 사이에 화살표 대신 값 하나(여기서는 [0, ∞]의 거리)를 붙인 범주입니다. 삼각부등식⁠(triangle inequality)⁠ d(x, z) ≤ d(x, y) + d(y, z)가 합성의 규칙이 되고, 여기서 쓰는 '더해서 잇고 짧은 것을 고르는' 구조가 (min, +) 반환입니다. 반환의 ⊕와 ⊗ 각각도 모노이드입니다. 「증명은 프로그램이다」에서 범주론⁠(category theory)⁠의 다른 얼굴을 볼 수 있고, 최대공약수⁠(greatest common divisor)⁠와 교집합⁠(intersection)⁠과 '그리고'가 한 가지 보편 성질⁠(universal property)⁠이라는 것처럼 범주론이 여러 분야를 가로지르는 모습은 「화살표만으로 본 수학」에 있습니다.
• 논리로: 참·거짓의 (∨, ∧)는 불 대수⁠(Boolean algebra)⁠이고, 원소가 둘뿐인 작은 반환입니다. 개수, 확률, 거리의 반환에서 값이 '그 반환의 0(길 없음)인가 아닌가'만 보면 두 연산이 모두 보존되어 이 반환으로 내려옵니다(거리에서는 +∞인가 아닌가). 도달 가능성은 이런 경로 문제의 그림자입니다. 음수가 섞인 실수에서는 1 + (−1) = 0처럼 길이 있는데 합이 0이 될 수 있어 그림자가 어긋납니다.
• 언어로: 글자열의 반환에서 별표를 구하면 정규 표현식이 나오고, 이것이 유한 오토마톤과 정규 표현식이 같은 언어를 적는다는 클리니 정리의 한쪽입니다. 문맥 자유 문법의 CYK 표는 촘스키 위계⁠(Chomsky hierarchy)⁠에서 정규 언어 바로 위 단계인 문맥 자유 언어⁠(context-free language)⁠를 다룹니다. 구문 트리와 비터비 품사 태깅⁠(part-of-speech tagging)⁠은 「말을 세는 기계」에 있습니다.
• 확률로: 은닉 마르코프 모델의 비터비와 전방 알고리즘, 마르코프 연쇄의 기본 행렬, 베이즈 정리로 하는 추론이 모두 (+, ×)나 (max, ×)의 표 채우기입니다. 펄이 믿음 전파 다음에 세운 인과 그래프⁠(causal graph)⁠는 「담배와 폐암」에서 이어집니다.
• 통신으로: 비터비 복호와 터보·LDPC 부호의 복호는 오류 정정 부호를 푸는 메시지 전달입니다. 잡음 속에서 신호를 되찾는 이야기는 「잡음 너머로」에 있습니다.
• 미분과 학습으로: 연쇄법칙⁠(chain rule)⁠으로 합성함수⁠(composite function)⁠를 미분하면, 계산 그래프⁠(computational graph)⁠에서 입력에서 출력으로 가는 모든 길에 대해 국소 미분을 곱해 더한 값이 나옵니다. (+, ×) 반환의 경로 합입니다. 역전파⁠(backpropagation)⁠는 이 합을 출력 쪽에서부터 표로 채우는 동적 계획법이고, 그래서 길이 지수적으로 많아도 계산은 그래프의 크기에 비례합니다. 신경망의 학습은 「배우는 기계」에 있습니다.
• 세기로: 격자에서 오른쪽과 위로만 가는 길의 수를 칸마다 더해 채우면 파스칼 삼각형⁠(Pascal's triangle)⁠이 나옵니다. (+, ×) 반환의 오래된 표입니다. 트리의 수로 나오는 카탈랑 수와 함께 「세지 않고 세기」에 있습니다.
• 최적화⁠(optimization)⁠로: (max, +) 산술에서는 적분⁠(integral)⁠ 대신 최댓값을 씁니다. 라플라스 변환은 함수에 지수함수를 곱해 적분하는 변환인데, 그 적분을 최댓값으로 바꾸면 볼록 최적화의 르장드르 변환(볼록 켤레)이 됩니다. 르장드르 변환⁠(Legendre transform)⁠은 볼록함수(그래프가 아래로 볼록한 함수)를 그 접선⁠(tangent line)⁠들의 기울기⁠(slope)⁠와 절편으로 다시 적는 변환입니다. 로그합지수는 max를 매끄럽게 편 볼록함수이고, 그 기울기가 소프트맥스입니다. 그래서 온도를 낮추면 로그합지수는 max로, 소프트맥스는 최댓값 고르기로 함께 다가갑니다.
• 게임으로: 체스 같은 게임은 이미 승패가 정해져 있다는 1912년 체르멜로의 정리를 오늘날에는 흔히 '끝에서부터 거꾸로 따지기⁠(backward induction)⁠'로 증명합니다(체르멜로 자신의 논증은 조금 달랐습니다). 거꾸로 따지기는 국면마다 값을 하나씩 적어 나가는 표 채우기입니다. 내 차례에는 max로, 상대 차례에는 min으로 모으니 반환 하나로 적히지는 않지만, 뒷부분의 답을 한 번만 계산해 되쓰는 생각은 같습니다. 그 이야기는 「이기는 쪽이 존재한다」 1절에 있습니다.
• 압축과 통신으로: 고속 푸리에 변환으로 빠르게 계산하는 JPEG의 코사인⁠(cosine)⁠ 변환, 그리고 터보 부호와 해밍 부호⁠(Hamming code)⁠의 역사는 「짧게 보내기」에 있습니다. 음성 인식의 빔 탐색⁠(beam search)⁠과 비터비 복호가 오늘의 언어 모델로 이어지는 길은 「다음 단어를 맞히는 기계」 3절에 있습니다.
• 대수의 뿌리로: 합과 곱은 있지만 빼기는 없는 데데킨트의 아이디얼이 어떤 실패에서 태어났는지는 「틀린 증명이 만든 수학」에 있습니다.
• 생각의 도구로: −log로 (max, ×)를 (min, +)로 옮기는 것은 표현 바꾸기의 전형입니다. 문제를 바꾸지 않고 이름만 바꿨는데, 곱셈이 덧셈이 되고 확률이 거리가 됩니다.