반환(Semiring)

세 마을 P, Q, R 사이에 일방통행 도로가 있다고 합시다. 칸 (i, j)에 'i에서 j로 곧장 가는 도로의 수'를 적은 표(행렬)를 A라 합시다. 보통의 행렬의 곱⁠(matrix multiplication)⁠으로 A를 제곱하면, A²의 칸 (P, R)는 '도로 두 개를 써서 P에서 R로 가는 길의 수'입니다. $(A^2)_{PR} = \sum_m A_{Pm}A_{mR}$에서 중간 마을 m마다 '앞 도로의 수 × 뒤 도로의 수'를 더하기 때문입니다. 여기서 '길'은 같은 마을을 다시 지나도 되는 도로의 나열입니다. 이제 칸에 도로의 길이를 적고(도로가 없으면 +∞), 곱을 덧셈으로, 합을 최솟값으로 바꿔 봅시다. 그러면 $\min_m (A_{Pm} + A_{mR})$은 '도로 두 개를 써서 P에서 R로 가는 가장 짧은 거리'입니다. 같은 계산이 더하기와 곱하기의 뜻만 바꾸어 다른 물음에 답합니다.

이렇게 바꿔 넣어도 되는 연산의 짝을 반환(半環, semiring)이라고 부릅니다. 집합⁠(set)⁠ S와 두 연산 ⊕, ⊗, 두 원소⁠(element)⁠ 0, 1이 있어서 다음이 성립하면 (S, ⊕, ⊗, 0, 1)은 반환입니다.

• (S, ⊕, 0)은 교환하는 모노이드⁠(monoid)⁠입니다. 갈래를 모으는 순서와 묶음은 상관없고, 0('길 없음')을 모아도 달라지지 않습니다.
• (S, ⊗, 1)은 모노이드입니다. 길을 어디서 끊어 잇든 같고, 1('빈 길')을 이어도 달라지지 않습니다. 교환법칙⁠(commutative law)⁠은 요구하지 않습니다.
• ⊗는 ⊕에 양쪽으로 분배됩니다. $a\otimes(b\oplus c) = (a\otimes b)\oplus(a\otimes c)$, $(b\oplus c)\otimes a = (b\otimes a)\oplus(c\otimes a)$.
• 0은 ⊗의 흡수원입니다. $0\otimes a = a\otimes 0 = 0$. 길이 없는 곳에 무엇을 이어도 길은 없습니다.

익숙한 예가 많습니다. 자연수⁠(natural number)⁠의 (+, ×, 0, 1)은 길의 개수를 세고, 0 이상의 실수⁠(real number)⁠의 (+, ×, 0, 1)은 여러 길의 확률을 더한 총확률을 줍니다. 실수와 +∞의 (min, +, +∞, 0)은 최단 거리를 줍니다. 이것을 헝가리 태생의 브라질 컴퓨터 과학자 이므레 시몬을 기려 '열대 반환⁠(tropical semiring)⁠'이라 부릅니다. [0, 1]의 (max, ×, 0, 1)은 가장 그럴듯한 길 하나의 확률을 주고, 참·거짓의 (∨, ∧, 거짓, 참)은 불 대수⁠(Boolean algebra)⁠로 도달 가능성을 줍니다. 0 이상의 실수와 +∞의 (max, min, 0, +∞)는 병목 경로⁠(bottleneck path)⁠에 답합니다. 길의 폭을 그 길에서 가장 좁은 도로의 폭으로 볼 때, 가장 넓은 길의 폭입니다. 글자열의 집합(언어)들도 합집합(⊕, 0 = 빈 집합)과 이어 쓰기(⊗, 1 = 빈 글자열 하나만 든 집합)로 반환을 이룹니다. 여기서는 ⊗가 교환하지 않습니다('ab'와 'ba'는 다릅니다). 이 반환의 원소 가운데 정규 언어⁠(regular language)⁠를 적는 표기가 정규 표현식⁠(regular expression)⁠입니다. 아닌 것도 있습니다. ⊕ = +, ⊗ = max로 두면 a = 1, b = c = 0에서 $\max(1, 0+0) = 1$인데 $\max(1,0)+\max(1,0) = 2$여서 분배법칙⁠(distributive law)⁠이 깨집니다. 실수 전체의 (max, ×)도 음수를 곱하면 큰 쪽이 작은 쪽이 되어 깨집니다.

반환이 쓸모 있는 까닭은 정리 하나에 있습니다. 행렬의 곱을 반환의 연산으로 정의합니다. $(AB)_{ij} = \bigoplus_m A_{im}\otimes B_{mj}$이고, 칸 $A_{ij}$에는 i에서 j로 가는 도로의 값을 적습니다(도로가 없으면 반환의 0). 어느 반환에서든, k ≥ 1일 때 A^k의 칸 (i, j)는 i에서 j로 가는 변 k개짜리 길 전부에 대해 변의 값을 ⊗로 곱한 것을 ⊕로 모은 값입니다. 증명은 k에 대한 귀납법입니다. 변 k개짜리 길은 변 k − 1개짜리 길 뒤에 변 하나를 붙인 것입니다. 그래서 길들은 마지막 변의 출발점 m에 따라 무리로 나뉩니다. 무리마다 공통인 마지막 변 $A_{mj}$를 분배법칙으로 묶어 내면 $(A^{k})_{ij} = \bigoplus_m (A^{k-1})_{im}\otimes A_{mj}$, 곧 행렬 곱이 됩니다. 분배법칙이 없으면 '모든 길을 하나씩 따로 계산해 모은 값'과 '표를 채워 얻은 값'이 달라질 수 있습니다. 길의 수는 k에 대해 지수적으로 늘 수 있지만, 표 채우기는 한 단계에 n³번 정도의 연산이면 됩니다(n은 마을 수). 동적 계획법의 많은 알고리즘⁠(algorithm)⁠이 바로 이런 반환 위의 표 채우기입니다. 아래 그림에서 물음은 , 길의 변 수는 k = 입니다. 칸을 누르면 그 칸을 이루는 길들이 아래에 풀려 나옵니다.

길이가 몇이든 모든 길을 모으려면 거듭제곱을 모두 모은 $A^{*} = I\oplus A\oplus A^2\oplus\cdots$이 필요합니다(I는 대각선이 1, 나머지가 0인 단위 행렬로, 변 0개짜리 '빈 길'입니다). 스티븐 클리니의 이름을 따 '별표'라 부르는 이 무한한 모음이 잘 정해지는지는 고리가 결정합니다. 수 하나로 보면 $a^* = 1\oplus a\oplus a^2\oplus\cdots$입니다. 최단 거리에서 a ≥ 0이면 고리를 돌아도 이득이 없어서 $a^* = \min(0, a, 2a, \ldots) = 0$이지만, 음수 고리가 있으면 돌수록 짧아져 −∞로 내려갑니다. 확률에서는 등비급수⁠(geometric series)⁠ $p^* = 1/(1-p)$(0 ≤ p < 1)이고, 개수에서는 고리를 지날 수 있는 칸이 무한대로 발산⁠(divergence)⁠합니다. 모든 $D_{kk}^*$가 잘 정해지면 로이–워셜–플로이드의 세 겹 반복 $D_{ij}\leftarrow D_{ij}\oplus D_{ik}\otimes D_{kk}^{*}\otimes D_{kj}$(k를 바깥에 두고 1부터 n까지)이 약 n³번의 연산으로 끝납니다. D = A에서 시작하면 결과는 변 1개 이상인 길을 모은 값이고, 여기에 I를 ⊕하면 A*입니다. 실수의 (+, ×)에서 급수⁠(series)⁠가 수렴⁠(convergence)⁠하면(A의 고윳값의 절댓값⁠(absolute value)⁠이 모두 1보다 작으면) $A^* = (I - A)^{-1}$이고, 이 반복은 가우스 소거법⁠(Gaussian elimination)⁠으로 그 역행렬⁠(inverse matrix)⁠을 구하는 계산과 같습니다. (min, +)에서는 음수 고리가 없을 때 최단 경로⁠(shortest path)⁠의 플로이드–워셜 알고리즘이고, 글자열의 반환에서는 오토마톤⁠(automaton)⁠을 정규 표현식으로 바꾸는 클리니의 방법입니다.

반환의 정의는 빼기를 요구하지 않습니다. 정수⁠(integer)⁠처럼 빼기가 있는 환(ring)도 반환이지만, 빼기가 없는 쪽이 오히려 흔합니다. 이것은 빠뜨린 것이 아니라, 많은 경우 어쩔 수 없는 일입니다. ⊕가 min이나 max나 ∨처럼 늘 $a\oplus a = a$(멱등⁠, idempotent⁠)이면, 0 말고 다른 원소가 하나라도 있는 한 어떤 환 안에도 그대로 넣을 수 없습니다. 환에서 $a + a = a$이면 양쪽에서 a를 빼 $a = 0$이 되기 때문입니다. 흔히 반환을 '덜 갖춘 환'쯤으로 여기지만, 최단 거리나 도달 가능성처럼 '고르는' 계산은 처음부터 빼기와 함께 살 수 없습니다. 대신 멱등인 반환에는 순서가 저절로 생깁니다. $a\oplus b = a$일 때 a ≤ b라고 정하면 되고, (min, +)에서 이것은 'a가 b보다 짧거나 같다'는 뜻입니다. 게다가 min, max, ∨는 $a\oplus b$가 늘 a와 b 가운데 하나입니다. 그래서 모은 값을 실제로 내는 길이 적어도 하나 있고, 그 길을 되짚어 찾을 수 있습니다. 개수의 반환에는 그런 '대표 길'이 없고, 멱등이라도 합집합⁠(union)⁠처럼 둘을 섞은 값이 나오는 반환에도 없습니다.

두 반환 사이에서 ⊕, ⊗, 0, 1을 모두 보존하는 함수(준동형⁠, homomorphism⁠)는 계산을 옮겨 줍니다. 확률 p를 −log p로 보내면 (max, ×)가 (min, +)로 옮겨지므로, 은닉 마르코프 모델⁠(hidden Markov model)⁠의 비터비 알고리즘⁠(Viterbi algorithm)⁠은 −log 확률 위의 최단 경로입니다. 개수, 확률, 거리의 반환에서 '그 반환의 0(길 없음)인가 아닌가'만 보는 함수⁠(function)⁠는 불 반환으로 가는 준동형입니다. 거리에서는 +∞인가 아닌가를 봅니다. 그래서 이런 경로 문제는 모두 '갈 수 있는가'라는 그림자를 갖습니다. 다만 음수가 섞인 실수의 (+, ×)에서는 1 + (−1) = 0처럼 0이 아닌 두 값이 더해져 0이 되므로, 이 함수가 준동형이 아닙니다. 또 온도 T > 0에서 $a\oplus_T b = T\log(e^{a/T}+e^{b/T})$를 ⊕로, 보통의 덧셈을 ⊗로 쓰면 반환이 됩니다. 0 이상의 실수의 (+, ×)를 x ↦ T log x로 옮긴 것이기 때문입니다. T → 0이면 ⊕_T가 max로 다가가 (max, +) 반환이 됩니다. $\oplus_T$를 각 입력으로 미분⁠(differentiation)⁠한 값이 온도 T의 소프트맥스⁠(softmax)⁠이므로, 소프트맥스가 T → 0에서 argmax 쪽으로 몰리는 것은 이 극한⁠(limit)⁠의 다른 얼굴입니다.

이어지는 곳. 반환의 두 연산은 각각 모노이드이고, 반환 위의 행렬의 곱과 거듭제곱이 동적 계획법과 최단 경로의 여러 알고리즘을 한 틀로 묶습니다. 거리 공간⁠(metric space)⁠을 범주⁠(category)⁠로 보는 로베어의 이야기는 풍부화된 범주⁠(enriched category)⁠에 있습니다. 거리를 '더해서 잇고 가장 짧은 것을 고르는' 이 페이지의 (min, +)와 같은 구조를 씁니다. 같은 격자를 (max, ×)로 채우는 비터비 알고리즘과 (+, ×)로 채우는 전방 알고리즘⁠(forward algorithm)⁠은 은닉 마르코프 모델에 있습니다. 문맥 자유 문법⁠(context-free grammar)⁠의 CYK 표는 글자열을 두 조각으로 자르는 모든 방법을 반환으로 모으는 표 채우기입니다. 그래서 반환을 바꾸면 '만들 수 있는가'를 답하던 인식기가 구문 트리⁠(parse tree)⁠의 수를 세거나 확률을 계산합니다. 글자열의 반환에서 별표를 구하는 일은 정규 표현식과 유한 오토마톤⁠(finite automaton)⁠이 같은 언어들을 나타낸다는 클리니의 정리로 이어집니다. 확률 그물의 추론과 오류 정정 부호⁠(error-correcting code)⁠의 복호에 쓰는 여러 알고리즘도 가환 반환⁠(commutative semiring)⁠ 위의 메시지 전달로 한데 묶이는데, 이 틀을 '일반화된 분배법칙⁠(generalized distributive law)⁠'이라 부릅니다(그래프가 나무 모양일 때 정확합니다). 연쇄법칙⁠(chain rule)⁠으로 경로마다 국소 미분을 곱해 더하는 역전파⁠(backpropagation)⁠도 (+, ×) 반환의 경로 합을 출력 쪽에서부터 채우는 계산입니다.