까마귀와 택시

까마귀는 곧장 날고 택시는 블록을 돌아갑니다. '얼마나 먼가'에는 답이 하나가 아니고, 어떤 거리를 고르느냐가 통계⁠(statistics)⁠와 기계 학습⁠(machine learning)⁠의 답을 바꿉니다.

이 글의 처럼 점선이 그어진 숫자는 좌우로 끌 수 있고(키보드 ←/→도 됩니다), 밑줄 친 말에 마우스를 올리면 그림에서 그 부분이 빛납니다. 그림 속 색 점은 직접 끌 수 있고, 색이 칠해진 선택지는 눌러서 바꿀 수 있습니다. 그림의 자료는 따로 밝히지 않으면 원리를 보이려고 만든 가상의 자료입니다. 휴대폰에서는 마우스를 올리는 대신 누르면 됩니다.

맨해튼의 한 교차로에 서 있다고 해 봅시다. 커피를 마시고 싶은데 근처에 카페가 두 곳 있습니다. 지도 앱의 직선거리로는 A가 더 가깝습니다. 그런데 걸어가거나 택시를 타면 B에 먼저 닿습니다. 어느 쪽이 '더 가까운' 카페일까요?

까마귀라면 A라고 답할 것입니다. 건물 위로 곧장 날아가니까요. 영어권에서 직선거리를 '까마귀가 나는 대로'라고 부르는 까닭입니다. 택시 기사라면 B라고 답할 것입니다. 택시는 건물을 뚫고 달릴 수 없고, 격자 모양의 길을 따라 가로로 몇 블록, 세로로 몇 블록을 가야 합니다. 두 대답은 모두 옳습니다. 서로 다른 거리를 쓰고 있을 뿐입니다.

이 글은 이 작은 불일치에서 출발합니다. '거리'에 답이 하나가 아니라면 무엇이 거리를 거리로 만들까요? 어떤 거리를 고르느냐에 따라 무엇이 달라질까요? 이 선택은 지도 위의 카페를 넘어, 화성에서 사진을 보내는 통신 부호와 철자 교정기, DNA 비교, 이상값⁠(outlier)⁠ 찾기, 그리고 자료에서 규칙을 스스로 찾아내는 기계 학습의 분류기까지 좌우합니다.

1 · 1811년의 격자까마귀 거리와 택시 거리

이 절의 물음은 이것입니다. 바둑판처럼 길이 난 도시에서 '두 곳 사이의 거리'를 재는 방법은 몇 가지이고, 방법이 바뀌면 무엇이 달라질까? 그 무대가 된 도시부터 봅시다.

19세기 초 뉴욕시는 맨해튼섬의 남쪽 끝에 몰려 있었고, 북쪽은 언덕과 농지, 습지였습니다. 1807년 뉴욕주 의회는 세 사람으로 된 위원회에, 앞으로 도시가 자랄 땅에 길을 미리 그어 두는 일을 맡겼습니다. 위원회는 1811년 계획을 확정했습니다. 남북으로 달리는 애비뉴 12개와 동서로 달리는 스트리트 155개가 직각으로 만나는 격자였습니다. 측량사 존 랜들 주니어가 몇 해에 걸쳐 섬 곳곳에 교차점 표지를 박았고, 언덕은 깎이고 습지는 메워졌습니다. 위원회는 설명문에서 굽은 길과 원형 광장 같은 장식을 마다한 이유를 이렇게 적었습니다.

도시는 주로 사람이 사는 집들로 이루어지며, 변이 곧고 모서리가 직각인 집이 짓기에 가장 싸고 살기에 가장 편하다는 점을 염두에 두지 않을 수 없었다.— 맨해튼 도로 계획 위원회의 설명문(1811)

반듯한 필지는 사고팔기도 쉬웠습니다. 격자 도시 자체는 훨씬 오래되었습니다. 기원전 5세기에 이미 밀레투스의 건축가 히포다모스가 격자 도시 설계로 이름을 남겼고, 동아시아에서는 당나라의 장안과 그것을 본뜬 헤이안쿄(교토)가 바둑판처럼 나뉘었습니다. 1859년 도시 계획가 일데폰스 세르다가 설계한 바르셀로나의 신시가지는 모서리를 깎은 네모 블록으로 유명합니다.

맨해튼의 격자에는 몇 가지 개성이 있습니다. 우선 격자 전체가 정북에서 29°쯤 돌아가 있어서, 5월 말과 7월 중순 무렵이면 해가 동서 방향 거리의 끝으로 정확히 지는 광경이 벌어집니다. 격자를 비스듬히 가로지르는 예외도 하나 있습니다. 옛길을 따라 난 브로드웨이입니다. 이 길이 애비뉴와 엇갈리는 곳마다 타임스 스퀘어, 헤럴드 스퀘어 같은 삼각형 광장이 생겼습니다.

이런 도시에서 두 교차로 사이의 거리는 두 가지로 잴 수 있습니다. 동쪽으로 3블록, 북쪽으로 4블록 떨어진 교차로를 예로 들어 봅시다. 까마귀는 곧장 날아갑니다. 가로 3, 세로 4를 두 변으로 하는 직각삼각형⁠(right triangle)⁠의 빗변⁠(hypotenuse)⁠이니, 피타고라스 정리⁠(Pythagorean theorem)⁠로 $\sqrt{3^2 + 4^2} = \sqrt{25} = 5$블록입니다. 이렇게 곧게 잰 거리를 유클리드 거리⁠(Euclidean distance)⁠라고 합니다. 택시는 건물 사이로 가로 3블록과 세로 4블록을 달려야 하니 3 + 4 = 7블록입니다. 가로 차이와 세로 차이를 더한 이 거리를 맨해튼 거리⁠(Manhattan distance)⁠ 또는 택시 거리라고 부릅니다. 아래 그림에서 나와 두 카페 A, B를 교차로 위로 끌어 보세요. 볼 것은 까마귀로 더 가까운 카페와 택시로 더 가까운 카페가 언제 서로 달라지는지입니다.

지금 A까지는 까마귀로 블록, 택시로 블록이고, B까지는 까마귀로 블록, 택시로 블록입니다. .

위 식은 나에서 A까지를 두 방식으로 잰 계산입니다. 세로 막대 |…|는 절댓값⁠(absolute value)⁠, 곧 부호를 떼고 크기만 본다는 뜻입니다. 서쪽으로 3블록이든 동쪽으로 3블록이든 달리는 길이는 3이기 때문입니다.

같은 거리를 달리는 택시 길은 하나가 아닙니다. 옅게 칠한 격자 안에서 오른쪽(또는 왼쪽)과 위(또는 아래)로만 가면 어떤 길이든 길이가 같습니다. A까지 가장 짧은 택시 길은 가지, B까지는 가지입니다. 가로 $m$블록, 세로 $n$블록을 가야 한다면 $m+n$번의 걸음 가운데 어느 $m$번을 가로로 갈지 고르는 문제이므로 길의 수는 이항계수⁠(binomial coefficient)⁠ $\binom{m+n}{m}$('m+n개 가운데 m개를 고르는 가짓수')입니다. 가로 3블록, 세로 2블록이라면 다섯 걸음 가운데 가로로 갈 세 걸음을 고르는 셈이라 $\binom{5}{3} = 10$가지입니다. 교차로마다 그곳에 이르는 길의 수를 적어 가면, 왼쪽 이웃과 아래 이웃의 수를 더하는 파스칼의 삼각형⁠(Pascal's triangle)⁠이 비스듬히 나타납니다. 오른쪽 위로 가는 길이라면 어느 교차로든 마지막 한 걸음은 왼쪽에서 오거나 아래에서 오니, 두 이웃에 이르는 길의 수를 더하면 되기 때문입니다. 인도의 운율학자들이 짧은 음절과 긴 음절의 무늬를 세다가 같은 삼각형에 이른 이야기는 「세지 않고 세기」 2절에 있습니다.

택시 길을 그려 보세요. 대각선에 바짝 붙은 계단 길도 ㄱ자 길과 길이가 똑같습니다. 블록을 한없이 잘게 나누면 계단은 대각선과 구별되지 않을 만큼 가까워지지만, 길이는 끝까지 가로와 세로의 합에 머뭅니다. 모양이 다가간다고 길이까지 다가가는 것은 아닙니다. 곡선의 길이를 극한⁠(limit)⁠으로 정의할 때 조심해야 하는 까닭입니다.

'원'도 달라집니다. 원은 한 점에서 거리가 같은 점들의 모임이니까요. 나를 중심으로 A를 지나는 원을 그려 봅시다. 지금 그림에는 . 택시의 원은 45° 돌아간 정사각형, 마름모입니다. 나에게서 택시로 3블록인 교차로는 (동 3, 북 0), (동 2, 북 1), (동 1, 북 2), (동 0, 북 3)처럼 가로와 세로의 합이 3인 곳들이라, 한 줄로 비스듬히 늘어서기 때문입니다. 네 방향에서 이런 비스듬한 변이 하나씩 생겨 마름모가 됩니다. B가 이 원 안쪽에 있으면 그 거리로는 B가 더 가깝습니다. 까마귀의 원 안에는 없는 B가 택시의 원 안에는 들어가는 것, 그것이 두 대답이 엇갈리는 이유의 전부입니다. 처음 자리로

정리하면, 까마귀 거리는 가로·세로 차이를 피타고라스 정리로 모으고, 택시 거리는 그냥 더합니다. 두 거리는 늘 택시 쪽이 같거나 길고, 차이는 대각선 방향에서 가장 큽니다. 어느 카페가 가까운지 두 대답이 엇갈리는 것은 이 차이 때문입니다.

실제 맨해튼의 블록은 정사각형이 아닙니다. 스트리트 사이는 80m쯤으로 짧고, 애비뉴 사이는 곳에 따라 190–280m쯤으로 두 배 반에서 세 배 반쯤 깁니다. 그래서 실제 택시 거리는 두 방향의 블록 수에 서로 다른 무게를 곱해 더해야 합니다. 이 '무게를 어떻게 줄 것인가'라는 물음은 7절에서 기계 학습의 문제로 다시 나타납니다.

2 · 거리의 가족민코프스키의 단위원⁠(unit circle)⁠

이 절의 물음은 이것입니다. 까마귀와 택시 말고도 거리는 더 있을까? 있다면 그것들을 한 식으로 묶을 수 있을까?

체스판의 킹은 가로, 세로, 대각선으로 한 칸씩 움직입니다. 킹이 한 칸에서 다른 칸까지 가는 데 필요한 걸음 수는 가로 차이와 세로 차이 가운데 큰 쪽입니다. 대각선으로 가면 가로와 세로를 한꺼번에 줄일 수 있으니까요. 가로 3, 세로 4라면 대각선으로 3걸음 가서 가로를 다 줄이고 세로로 1걸음 더 가니 모두 4걸음입니다. 이것을 체비쇼프 거리⁠(Chebyshev distance)⁠라고 부릅니다. 킹의 '원'은 축에 나란한 정사각형입니다. 킹이 4걸음에 닿는 칸들은 가로·세로 차이가 모두 4 이하이고 적어도 하나가 4인 칸들, 곧 가로세로 9칸짜리 정사각형의 테두리이기 때문입니다.

19세기 페테르부르크의 수학자 파프누티 체비쇼프는 증기기관의 연결 장치를 연구하다가 '가장 큰 오차를 가장 작게 하는' 근사 문제에 몰두했습니다. 복잡한 함수⁠(function)⁠를 다항식⁠(polynomial)⁠ 같은 단순한 함수로 흉내 낼 때, 구간 전체에서 둘이 가장 크게 어긋나는 곳의 차이를 되도록 작게 만드는 문제입니다(근사 이론⁠(approximation theory)⁠). 차이 가운데 가장 큰 것 하나로 재는 이 거리에 그의 이름이 붙은 것도 그 기준과 이어져 있습니다.

까마귀, 택시, 킹의 거리는 사실 한 가족입니다. 두 점의 좌표 차이를 $(x, y)$라 하면 셋 모두 다음 식의 특별한 경우입니다.

왼쪽의 $\lVert (x, y) \rVert_p$는 '차이 (x, y)의 p-길이'라고 읽습니다. 두 차이의 절댓값을 각각 $p$제곱해 더한 뒤, 그 합의 $p$제곱근(p제곱하면 그 합이 되는 수, 지수로는 $1/p$제곱)을 취한다는 뜻입니다. 차이가 (3, 4)인 경우로 따라가 봅시다.

• p = 1: (3 + 4)¹ = 7. 택시 거리입니다.
• p = 2: $(3^2 + 4^2)^{1/2} = \sqrt{25} = 5$. 까마귀 거리입니다.
• p = 10: $(3^{10} + 4^{10})^{1/10} = (59{,}049 + 1{,}048{,}576)^{1/10} \approx 4.02$. 킹의 거리 4에 거의 붙었습니다.

그러니 $p = 1$이면 택시, $p = 2$이면 까마귀이고, $p$를 한없이 키우면 두 차이 가운데 큰 쪽만 살아남아 킹의 거리가 됩니다. 이 끝을 흔히 p = ∞(무한대)라고 적습니다. 차이가 (3, 4)라면 $p = 1$일 때 7, $p = 2$일 때 5, $p = 10$일 때 약 4.02입니다. 거듭제곱의 지수가 클수록 큰 쪽이 압도적으로 커져서 작은 쪽의 몫이 사라지는 것입니다. $4^{10}$은 $3^{10}$의 18배쯤입니다. 이 가족을 Lp 노름⁠(Lp norm)⁠이라 하고(노름⁠(norm)⁠은 원점에서 잰 길이라는 뜻입니다), 두 점 사이의 거리로 쓸 때는 민코프스키 거리⁠(Minkowski distance)⁠라고 부릅니다. 원점에서 거리가 1인 점들, 곧 이 거리의 단위원을 그려 봅시다. 지금 $p =$ 입니다. p를 바꿔 가며 단위원의 모양이 어떻게 변하는지, 그리고 파란 점 Q까지의 거리가 p에 따라 어떻게 달라지는지 보세요.

p를 1에서 키우면 단위원은 마름모에서 부풀어 원을 지나 정사각형으로 다가갑니다. p = 1 p = 2 p = 8 Q까지의 거리는 p = 1이면 , p = 2이면 , p = ∞이면 이고, 지금의 p로는 입니다. p가 클수록 같은 점까지의 거리가 짧아지고(축 위의 점이면 그대로), 그래서 단위원은 바깥으로 부풉니다. 단위원만 알면 거리를 모두 알 수 있습니다. Q까지의 거리는 Q가 단위원 위의 점보다 몇 배 멀리 있느냐입니다.

그렇다면 p를 1보다 작게 하면 어떨까요? p = 0.5 단위원이 안쪽으로 오목한 별 모양이 됩니다. 이때 원점에서 $(1, 1)$까지 곧장 가는 거리는 $(1^p + 1^p)^{1/p}$, 곧 $2^{1/p} =$ 인데, $(1, 0)$을 거쳐 돌아가면 두 구간이 각각 1이라 $1 + 1 = 2$입니다. p = 0.5라면 곧장 가는 거리가 $2^{2} = 4$로, 돌아가는 길의 두 배입니다. 지금은 . 돌아가는 길이 더 짧다면 '거리'라고 부르기 어렵습니다. 단위원이 볼록할 때에만, 곧 p가 1 이상일 때에만 이런 일이 없습니다. 도형이 볼록하다는 것은 도형 안의 어떤 두 점을 이어도 그 선분이 도형 밖으로 나가지 않는다는 뜻입니다. p = 0.5의 별 모양은 (1, 0)과 (0, 1)을 잇는 선분의 가운데가 바깥으로 나가므로 볼록하지 않습니다. 4절에서 이 조건을 '삼각부등식⁠(triangle inequality)⁠'이라는 이름으로 다시 만납니다.

정리하면, 택시·까마귀·킹의 거리는 p = 1, 2, ∞인 한 가족이고, 가족의 구성원마다 단위원의 모양이 다릅니다. p가 1 이상이어야 단위원이 볼록하고, 그래야 돌아가는 길이 곧장 가는 길보다 짧아지는 일이 없습니다.

원점에 대해 대칭이고 볼록한 도형이면 무엇이든 단위원이 될 수 있다는 것, 그래서 도형 하나가 거리 하나를 정한다는 것을 처음 체계적으로 쓴 사람이 독일의 수학자 헤르만 민코프스키입니다. 1896년 『수의 기하학⁠(geometry of numbers)⁠』에서 그는 이 생각으로 정수⁠(integer)⁠의 성질을 다루는 정수론⁠(number theory)⁠의 문제를 풀었습니다. 예를 들어 원점에 대해 대칭인 볼록한 도형의 넓이⁠(area)⁠가 4보다 크면, 그 안에는 원점 말고도 좌표가 모두 정수인 점이 반드시 들어 있습니다. 반지름 1.2인 원은 넓이가 약 4.52라 (1, 0) 같은 정수점을 품습니다. 원점을 중심으로 한 변이 1.9인 정사각형은 넓이가 3.61로 4보다 작고, 실제로 원점 말고는 정수점을 품지 않습니다. 모양에 관한 사실이 정수에 관한 사실이 된 것입니다.

민코프스키의 이름은 물리학에도 남았습니다. 1908년 9월 쾰른에서 그는 옛 제자 아인슈타인의 특수 상대성 이론⁠(special relativity)⁠을 4차원 기하⁠(geometry)⁠로 다시 썼습니다. 특수 상대성 이론은 빛의 속도⁠(velocity)⁠가 누구에게나 같다는 데서 출발해, 시간의 흐름과 길이가 관찰자의 움직임에 따라 달라진다는 것을 보인 1905년의 이론입니다.

이제부터 공간 그 자체와 시간 그 자체는 완전히 그림자 속으로 가라앉고, 오직 둘의 일종의 결합만이 독립성을 지키게 될 것입니다.— 헤르만 민코프스키, 강연 「공간과 시간」(1908)

이 시공간⁠(spacetime)⁠에서는 두 사건⁠(event)⁠ 사이의 '거리'를 $c^2\Delta t^2 - \Delta x^2$처럼 빼기가 섞인 식으로 잽니다. $c$는 빛의 속도, $\Delta t$와 $\Delta x$는 시간과 공간의 차이입니다(Δ는 '델타'라 읽고, 차이를 뜻합니다). 빼기가 들어 있으니 서로 다른 두 사건 사이의 값이 0이 되거나 음수가 될 수도 있습니다. 빛 신호 하나가 출발하는 사건과 도착하는 사건 사이는 공간의 차이가 정확히 (빛의 속도) × (걸린 시간), 곧 $\Delta x = c\,\Delta t$이니 값이 0입니다. 곧 볼 거리의 규칙들을 일부러 어긴 이 '거리'가 뒤에 휘어진 시공간의 측지선⁠(geodesic)⁠을 다루는 일반 상대성 이론⁠(general relativity)⁠의 바탕이 되었습니다(「평행선의 반란」). 처음부터 환영받은 것은 아닙니다. 아인슈타인의 전기를 쓴 물리학자 에이브러햄 파이스가 전하는 바로는, 옛 제자는 처음에 이 4차원 기하를 '쓸데없는 학식'이라고 여겼습니다. 그러나 중력을 다루려고 씨름하던 1912년 무렵 그는 이 언어 없이는 나아갈 수 없다는 것을 깨달았습니다. 민코프스키는 그보다 앞선 1909년에 세상을 떠나 그 모습을 보지 못했습니다.

'택시 기하⁠(taxicab geometry)⁠'라는 이름은 1950년대에 수학자 카를 멩거가 시카고 과학 산업 박물관의 전시와 함께 낸 소책자에서 썼다고 전합니다. 1975년 유진 크라우스의 대중서 『택시 기하』가 이 이름을 널리 퍼뜨렸습니다. 택시 기하에서는 유클리드 기하의 공리⁠(axiom)⁠ 대부분이 그대로 성립하지만, 두 변과 끼인각이 같으면 두 삼각형이 합동⁠(congruence)⁠이라는 성질은 성립하지 않습니다.

3 · 가장 가까운 우물보로노이 지도

이 절의 물음은 이것입니다. 우물이나 학교처럼 기준이 되는 곳이 여럿일 때 '누가 어디에 가장 가까운가'로 땅을 나누면, 거리의 종류에 따라 그 경계가 어떻게 달라질까?

「담배와 폐암」에서 존 스노의 콜레라 지도를 보았습니다. 1854년 런던 소호에서 스노는 집마다 가장 가까운 펌프를 따져 동네를 나누었고, 브로드 가 펌프의 구역에 사망자가 몰려 있음을 보였습니다. 그 그림에서 집을 가장 가까운 펌프의 색으로 칠한 지도가 바로 보로노이 다이어그램⁠(Voronoi diagram)⁠입니다. 평면에 기준점 몇 개를 찍고, 모든 점을 가장 가까운 기준점의 영역으로 나눈 지도입니다. 그 글에서는 '걸어서 가는 거리'와 '직선거리'를 바꾸면 경계가 움직였습니다. 이번에는 거리를 로 바꾸어 봅시다.

유클리드 거리로는 두 기준점 사이의 경계가 두 점을 잇는 선분의 수직이등분선⁠(perpendicular bisector)⁠, 곧 선분의 한가운데를 직각으로 지나는 직선입니다. 두 점에서 곧게 잰 거리가 같은 점들이 바로 이 직선을 이루기 때문입니다. 그래서 모든 영역이 곧은 변으로 둘러싸인 볼록한 다각형입니다. 맨해튼 거리로 바꾸면 경계가 수평선, 수직선, 45° 사선이 이어진 꺾은선이 되고, 체비쇼프 거리로는 그 꺾이는 방향이 바뀝니다. 같은 기준점인데도 가장 넓은 영역은 , 가장 좁은 영역은 를 차지하며, 거리의 종류를 바꾸면 이 비율도 달라집니다. 어느 학교에 배정되는지, 어느 소방서가 출동하는지가 거리의 정의에 따라 바뀔 수 있다는 뜻입니다. 기준점 제자리로

정리하면, 가장 가까운 기준점으로 땅을 나눈 지도는 거리의 종류에 따라 경계의 모양과 영역의 넓이가 달라집니다. 같은 기준점을 두고도 '누가 누구 담당인가'가 거리의 선택에 달린 것입니다.

이 나눔에는 여러 사람의 이름이 붙어 있습니다. 여러 분야에서 저마다 다시 발견했기 때문입니다. 1850년 독일의 수학자 디리클레가 이차 형식($ax^2 + bxy + cy^2$ 꼴의 식)을 연구하며 썼습니다. 1908년에는 러시아 제국 시절 바르샤바 대학의 게오르기 보로노이가 이것을 공간 전체로 일반화했습니다. 1911년 미국의 기상학자 앨프리드 티센은 흩어진 관측소의 강수량으로 지역 평균⁠(mean)⁠을 낼 때 각 관측소가 맡을 넓이를 이렇게 정했습니다. 17세기 데카르트가 우주를 소용돌이들로 나누어 그린 그림이 이미 이 모양을 닮았다고 보는 사람도 있습니다.

4 · 무엇이 거리인가프레셰와 하우스도르프의 세 규칙

이 절의 물음은 이것입니다. 거리가 이렇게 여러 가지라면, 무엇이 어떤 수를 '거리'라고 부를 자격을 줄까? 그리고 그 자격을 갖춘 거리는 점 말고 무엇 사이에서 잴 수 있을까?

20세기 초 수학자들은 점과 점 사이만이 아니라 곡선과 곡선, 함수와 함수 사이의 거리를 재야 했습니다. 어떤 함수를 다항식이나 푸리에 급수⁠(Fourier series)⁠로 근사할 때 '얼마나 가까운가'를 말하려면 두 함수 사이의 거리가 필요합니다. 체비쇼프처럼 두 그래프가 가장 크게 벌어진 곳의 차이로 잴 수도 있고, 차이의 제곱을 적분⁠(integral)⁠해 잴 수도 있습니다(「잃어버린 소행성」의 최소제곱⁠(least squares)⁠이 바로 이 거리입니다).

그렇다면 이 모든 거리에 공통된 것은 무엇일까요? 1906년 파리의 수학자 모리스 프레셰는 박사 논문에서 대담한 걸음을 내디뎠습니다. 대상이 무엇이든, 두 대상 사이에 몇 가지 규칙을 지키는 수가 주어지기만 하면 극한과 연속, 수렴⁠(convergence)⁠을 같은 방식으로 논할 수 있다는 것입니다. 1914년 독일의 수학자 펠릭스 하우스도르프는 『집합론⁠(set theory)⁠ 개요』에서 이것을 오늘날의 모습으로 다듬고 '거리 공간⁠(metric space)⁠'이라는 이름을 붙였습니다. 규칙은 셋입니다.

d(x, y)는 'x와 y 사이의 거리'라고 읽습니다. 기호를 풀면, ≥는 '크거나 같다', ≤는 '작거나 같다', ⟺는 '왼쪽이 참이면 오른쪽도 참이고, 오른쪽이 참이면 왼쪽도 참'이라는 뜻입니다. 세 규칙을 말로 적으면 이렇습니다.

1. 거리는 음수가 아니고, 같은 것끼리만 0입니다.
2. 가는 거리와 오는 거리가 같습니다(대칭).
3. 중간에 y를 들렀다 가는 길이 곧장 가는 길보다 짧을 수 없습니다(삼각부등식).

택시 거리로 셋째 규칙을 확인해 봅시다. x = (0, 0), y = (1, 0), z = (1, 1)이면 곧장 가는 d(x, z) = 2이고, 들렀다 가는 d(x, y) + d(y, z) = 1 + 1 = 2이니 2 ≤ 2로 지켜집니다. 2절의 p = 0.5 '거리'로는 곧장 가는 길이 4, 들렀다 가는 길이 2였으니 4 ≤ 2가 거짓이 되어 규칙이 깨집니다. 이 세 규칙을 지키는 함수를 거리 함수⁠(metric)⁠라고 부릅니다. 앞에서 본 유클리드, 맨해튼, 체비쇼프 거리는 모두 이 규칙을 지키고, p가 1보다 작은 '거리'는 셋째 규칙인 삼각부등식을 어겼습니다. 규칙만 지키면 수렴(차례로 늘어선 대상들이 어떤 대상에 한없이 다가감)은 "거리가 0으로 간다"로, 연속성⁠(continuity)⁠은 "입력이 가까우면 출력도 가깝다"로 똑같이 정의됩니다. 한 번 증명한 정리가 점에도, 함수에도, 뒤에 볼 문자열에도 그대로 통합니다. 수학이 '무엇을 재는가'에서 '재는 방식이 어떤 규칙을 지키는가'로 눈을 돌린 순간이었습니다.

정리하면, 거리란 음수가 아니고 같은 것끼리만 0이며, 대칭이고, 삼각부등식을 지키는 수입니다. 이 세 규칙만 지키면 무엇 사이의 거리든 같은 수학으로 다룰 수 있습니다. 이 절의 나머지는 이 틀로 재는 여러 대상입니다.

2절의 Lp 가족도 이 무렵 함수의 세계로 건너갔습니다. 1910년 헝가리의 리스 프리제시는 절댓값의 p제곱을 적분해 재는 함수들의 공간, 오늘날의 Lp 공간을 정의했습니다.

1920년 무렵 르부프, 오늘날 우크라이나의 리비우에서는 스테판 바나흐가 이 공간들을 한꺼번에 공리로 다루었습니다. 그가 본 공간에는 원점에서 잰 길이, 곧 2절의 $\lVert \cdot \rVert_p$ 같은 노름이 있고, 두 점의 거리는 둘의 차이의 길이입니다. 게다가 빈틈이 없습니다. 점점 서로 가까워지는 점들의 열이 다가가는 극한이 늘 공간 안에 있다는 뜻입니다. 르부프의 수학자들이 스코틀랜드 카페의 탁자에서 문제를 주고받으며 키운 이 함수해석학(함수 하나하나를 공간의 점처럼 다루는 수학)이 무한 차원에서 '가깝다'를 말하는 오늘날의 표준 언어가 되었습니다. 카페의 문제 공책 이야기는 「이기는 쪽이 존재한다」에 있습니다.

1973년 로베어는 여기서 한 걸음 더 나아가, 삼각부등식을 '두 길을 이으면 길이 된다'는 화살표의 합성으로, $d(a, a) = 0$을 항등 화살표⁠(identity arrow)⁠로 읽으면 거리 공간이 곧 하나의 범주⁠(category)⁠라는 것을 보였습니다. 대칭과 '거리가 0이면 같은 점'이라는 규칙을 요구하지 않는 이 풍부화된 범주⁠(enriched category)⁠의 거리는, 일방통행 길이나 오르막길을 오르는 시간처럼 가는 길과 오는 길이 다른 경우까지 담습니다. 대상을 속이 아니라 화살표로 보는 이 언어가 최대공약수⁠(greatest common divisor)⁠, 쌍대 공간⁠(dual space)⁠, 연쇄법칙⁠(chain rule)⁠에서 하는 일은 「화살표만으로 본 수학」에 모아 두었습니다.

지구 위의 거리. 규칙이 같아도 공간이 다르면 거리도 다릅니다. 지구 표면에서 두 도시 사이의 가장 짧은 길은 지구 중심을 지나는 평면이 지구를 자른 대원⁠(great circle)⁠의 호, 곧 구면의 측지선입니다(「평행선의 반란」에서 서울–뉴욕 항로가 북쪽으로 휘는 이유를 보았습니다). 위도 $\varphi$와 경도 $\lambda$로 이 거리를 구하는 표준 공식이 하버사인 공식⁠(haversine formula)⁠입니다. 아래 식에서 $d$는 구하려는 거리, $R$은 지구 반지름(약 6,371 km)이므로, $d/R$은 지구 중심에서 본 두 도시 사이의 각도입니다.

식을 말로 읽어 봅시다. φ('파이')는 위도, λ('람다')는 경도이고, 아래 첨자 1, 2는 두 도시를 가리킵니다. hav('하버사인')는 각의 절반의 사인⁠(sine)⁠을 제곱한 값, 곧 $\sin^2(\theta/2) = (\sin(\theta/2))^2$입니다. 식은 '중심에서 본 각의 하버사인 = 위도 차이의 하버사인 + (두 위도의 코사인⁠(cosine)⁠의 곱) × 경도 차이의 하버사인'이라는 뜻입니다. 경도 차이 앞에 코사인이 붙는 것은, 위도가 높을수록 위선이 짧아져서 같은 경도 차이가 더 짧은 거리가 되기 때문입니다. 두 도시가 같은 경선 위에 있으면 경도 차이가 0이라 둘째 항이 사라지고, 중심에서 본 각이 그냥 위도 차이가 됩니다.

구면기하⁠(spherical geometry)⁠의 코사인 법칙⁠(law of cosines)⁠으로도 같은 거리를 구할 수 있는데, 왜 굳이 $\sin^2(\theta/2)$라는 낯선 함수를 썼을까요? 19세기 항해사들은 로그 표로 곱셈을 덧셈으로 바꾸어 계산했습니다. 로그는 양수에만 쓸 수 있는데, 하버사인은 언제나 0 이상이라 부호를 따질 필요가 없었습니다. 정밀도⁠(precision)⁠도 문제였습니다. 가까운 두 점이면 코사인 법칙은 1에 아주 가까운 값들(0.99998과 0.99997처럼)의 차이를 봐야 해서, 다섯 자리 표로는 유효숫자가 거의 남지 않습니다. 0.99998 − 0.99997 = 0.00001에는 믿을 수 있는 숫자가 끝자리 하나뿐입니다. 하버사인은 작은 각에서 각의 제곱에 비례하는 작은 수 자체를 다루므로 이런 손실이 없습니다.

하버사인 표를 항해사들의 손에 쥐여 준 사람은 해군 학교의 교사였습니다. 영국 포츠머스의 왕립 해군 학교에서 가르친 제임스 인먼이 1835년 무렵 항해 교재에 하버사인 표를 실었고, 이 이름도 그때 생겼다고 전합니다. 이 공식은 지금도 지도 앱이 두 좌표 사이의 거리를 계산할 때 널리 쓰입니다. 서울과 뉴욕 사이는 1만 1천 km 남짓입니다. 별의 위치를 재던 삼각함수⁠(trigonometric function)⁠ 표의 긴 역사는 「원에서 파동으로」에 있습니다.

이름은 19세기에 붙었지만 재료와 문제는 훨씬 오래되었습니다. 1 − cos θ를 뜻하는 '버스드 사인'(versine)은 인도 천문학의 산스크리트 문헌에서 이미 사인과 함께 표로 쓰였고, 하버사인은 그 절반입니다($\sin^2(\theta/2) = (1 - \cos\theta)/2$). 두 도시 사이의 거리를 구면 위에서 구하는 일도 오래된 과제였습니다. 1025년 무렵 오늘날 아프가니스탄의 가즈니에서 박식가 알비루니가 완성한 책의 제목은 『도시 사이의 거리를 바로잡기 위한 장소들의 좌표 결정』입니다. 그는 같은 월식을 두 곳에서 본 시각의 차이 같은 천문 관측으로 도시들의 경도와 위도를 정하고, 구면 위의 삼각형을 풀어 도시 사이의 거리와 메카의 방향을 구했습니다. 예배 방향을 정해야 하는 신앙의 필요가 구면 위의 거리 계산을 키운 것입니다.

길 위의 거리. 스노의 '걸어서 가는 거리'는 도로를 선, 교차로를 점으로 본 그래프 위의 최단 경로⁠(shortest path)⁠ 길이입니다. 도로망이 모두 이어져 있고 길이 양방향이라면 이것도 세 규칙을 지킵니다. 그런데 일방통행로가 있으면 가는 길과 오는 길이 달라져 둘째 규칙, 대칭이 깨집니다. 수학자 사이의 '에르되시 수⁠(Erdős number)⁠'나 여섯 단계의 분리 같은 좁은 세상⁠(small world)⁠의 거리도 그래프 거리입니다(「일곱 다리의 도시」). 해리 벡이 그려 1933년부터 배포된 런던 지하철 노선도는 실제 거리를 과감히 버리고 역 사이의 연결만 남겼습니다. 승객에게 필요한 것이 바로 그래프 거리였기 때문입니다.

집합⁠(set)⁠ 사이의 거리. 점도 길도 아닌 것 사이의 닮음을 재야 할 때도 있습니다. 1901년 스위스의 식물학자 폴 자카드는 알프스와 쥐라 산지의 여러 지역에 어떤 식물 종들이 자라는지 목록을 만들고, 두 지역의 식물상이 얼마나 닮았는지를 두 목록에 함께 있는 종의 비율로 쟀습니다. 두 집합(여기서는 종의 목록)의 교집합(두 목록에 모두 있는 종) 크기를 합집합(어느 한 목록에라도 있는 종) 크기로 나눈 이 수를 자카드 지수⁠(Jaccard index)⁠라고 부릅니다. 한 골짜기에 참나무·소나무·자작나무가, 다른 골짜기에 소나무·자작나무·단풍나무가 자란다면, 함께 있는 종은 2개, 어느 한쪽에라도 있는 종은 4개이니 자카드 지수는 2/4 = 0.5입니다. 반세기 가까이 뒤 미국 미시간의 생태학자 리 다이스(1945)와 덴마크 코펜하겐의 식물학자 토르발 쇠렌센(1948)이 각자 따로 비슷한 지수에 이르렀습니다. 이것이 쇠렌센–다이스 계수⁠(Sørensen–Dice coefficient)⁠입니다.

∩는 교집합⁠(intersection)⁠, ∪는 합집합⁠(union)⁠이고, 세로 막대 |…|는 여기서 '원소⁠(element)⁠의 개수'를 뜻합니다. 다이스 계수⁠(Dice coefficient)⁠는 겹친 개수를 두 목록 크기의 평균으로 나눈 것입니다. 위의 두 골짜기라면 2 × 2 ÷ (3 + 3) ≈ 0.67입니다.

두 골짜기의 식물 목록에서 골짜기 A에만 있는 종이 개, B에만 있는 종이 개, 둘 다에 있는 종이 개라고 합시다. 자카드 지수는 , 쇠렌센–다이스 계수는 입니다. 닮음을 거리로 바꾸려면 1에서 빼면 됩니다. $1 - J$는 , $1 - D$는 입니다. 두 계수는 $D = 2J/(1+J)$로 이어져 있습니다. 두 목록 크기의 합은 합집합 크기에 교집합 크기를 더한 것이기 때문이고, 위의 예라면 J = 0.5에서 2 × 0.5 ÷ 1.5 ≈ 0.67입니다. 그래서 순위를 매기면 두 계수는 늘 같은 순서를 내지만, 거리로서의 자격은 다릅니다. $1 - J$는 세 규칙을 모두 지키는데, $1 - D$는 삼각부등식을 어길 수 있습니다. 세 집합 $A = \{a\}$, $B = \{a, b\}$, $C = \{b\}$를 보세요.

계산을 따라가 봅시다. A와 B는 a 하나를 함께 가지고 크기가 1과 2이니 D(A, B) = 2 × 1 ÷ 3 = 2/3이고, 거리로는 1 − 2/3 = 1/3입니다. B와 C도 같은 까닭으로 1/3입니다. A와 C는 겹치는 것이 없어 D = 0, 거리 1입니다. 곧장 가는 거리 1이 B를 들렀다 가는 거리 2/3보다 크니 삼각부등식이 깨집니다. A와 C는 공통점이 하나도 없는데, 둘 다 B와는 꽤 닮았습니다. 자카드로 재면 J(A, B) = 1/2이라 거리가 1/2씩이고, $1 \le \tfrac12 + \tfrac12$로 가까스로 규칙을 지킵니다.

오늘날 이 두 지수는 생태학을 넘어 쓰입니다. 컴퓨터 비전에서는 예측한 영역과 정답 영역이 얼마나 겹치는지를 자카드 지수로 평가하는데, 이것을 흔히 IoU라고 부릅니다. 의료 영상에서는 종양 경계를 얼마나 잘 따냈는지를 다이스 계수로 평가합니다. 검색 엔진은 거의 똑같은 웹 문서를 가려낼 때 단어 집합의 자카드 지수를 빠르게 어림하는 기법을 씁니다.

A–B–C의 사슬은 철학의 오래된 문제를 떠올리게 합니다. '놀이'라는 말로 묶이는 것들, 곧 바둑과 공놀이와 술래잡기와 혼자 하는 카드놀이에 모두 공통된 특징이 있을까요? 오스트리아 태생의 철학자 루트비히 비트겐슈타인은 그런 하나의 특징은 없고, 한 가족의 얼굴처럼 겹치고 엇갈리는 닮음의 그물이 있을 뿐이라고 보았습니다. 그는 이것을 '가족 유사성⁠(family resemblance)⁠'이라 불렀습니다.

그것들을 들여다보면 모두에 공통된 무언가를 보지는 못하겠지만, 닮음들과 친족 관계들을, 그것도 한 무더기를 보게 될 것이다. 다시 말하지만, 생각하지 말고, 보라!— 루트비히 비트겐슈타인, 『철학적 탐구』 66절(1953)

가족 유사성은 수 하나로 재는 거리와는 다른 그림입니다. A는 B를 닮고 B는 C를 닮았는데 A와 C는 전혀 닮지 않을 수 있고, 무엇이 닮았는지는 어느 특징을 보느냐에 달려 있습니다.

심리학은 이것을 실험으로 확인했습니다. 1977년 심리학자 아모스 트버스키는 사람이 느끼는 닮음이 거리의 규칙을 자주 어긴다는 것을 보였습니다. 사람들은 "북한은 중국과 닮았다"에는 쉽게 동의하면서 "중국은 북한과 닮았다"에는 덜 동의했습니다. 대칭이 깨진 것입니다. 그가 든 예로 널리 인용되는 것도 있습니다. 당시 자메이카는 쿠바와 닮았고(지리), 쿠바는 소련과 닮았지만(정치), 자메이카와 소련은 전혀 닮지 않았습니다. 삼각부등식이 깨진 것입니다. 그렇다면 거리를 고르는 일은 세계의 사실을 적는 일이 아니라, 무엇을 같은 것으로 볼지 정하는 일에 가깝습니다. 이 물음은 7절에서 다시 날카로워집니다.

물리 공간의 거리를 두고도 같은 물음이 오갔습니다. 프랑스의 수학자 앙리 푸앵카레는 1902년 『과학과 가설』에서, 같은 관측을 '공간이 휘었다'로도 '자가 줄어든다'로도 설명할 수 있으니 어느 기하가 참인지는 관측만으로 가려지지 않으며, 기하는 더 편리한 쪽을 고르는 약속이라고 했습니다. 1921년 1월 아인슈타인은 베를린의 프로이센 과학 아카데미에서 한 강연 「기하학과 경험」으로 답했습니다. 그는 원리상으로는 푸앵카레가 옳다고 인정하면서도, 단단한 자로 길이를 재는 방법까지 함께 정해 두면 기하는 경험으로 시험할 수 있는 자연과학, 곧 물리학의 가장 오래된 분야가 된다고 보았습니다. 거리가 약속인지 사실인지는, 거리를 재는 절차를 무엇으로 정해 두느냐에 달려 있다는 것입니다. 가장자리로 갈수록 자가 줄어드는 푸앵카레의 원판 세계는 「평행선의 반란」에서 직접 볼 수 있습니다.

5 · 틀린 비트, 틀린 글자해밍과 레벤시테인

이 절의 물음은 이것입니다. 0과 1의 줄이나 낱말처럼 좌표가 없는 것들 사이의 거리는 어떻게 잴까? 그리고 그 거리로 무엇을 할 수 있을까?

1940년대 말 뉴저지주 머리힐의 벨 연구소에서 리처드 해밍은 계전기(전기 신호로 여닫는 스위치)로 돌아가는 계산기를 쓰고 있었습니다. 그가 뒷날 여러 번 회고한 바로는, 주말에는 기계를 지키는 사람이 없어서 기계가 오류를 찾아내면 그 작업을 버리고 다음 작업으로 넘어가 버렸고, 월요일에 와 보면 계산이 날아가 있기 일쑤였습니다. 오류가 있다는 것을 알아낼 수 있다면 어디가 틀렸는지도 알아내 고칠 수 있지 않을까? 1950년 『벨 시스템 기술 저널』에 실린 그의 논문이 그 답이었고, 그 바탕에 새로운 거리가 있었습니다.

길이가 같은 두 문자열에서 서로 다른 자리의 개수를 해밍 거리⁠(Hamming distance)⁠라고 합니다. 1011001과 1001011을 위아래로 맞대어 한 자리씩 견주면, 셋째 자리(1과 0)와 여섯째 자리(0과 1)만 다릅니다. 그래서 1011001과 1001011의 해밍 거리는 2입니다. 한 문자열을 다른 문자열로 바꾸려면 비트 몇 개를 뒤집어야 하는가, 라고 읽어도 됩니다.

가장 단순한 오류 정정은 같은 비트를 세 번 보내는 것입니다. 0은 000, 1은 111로 보냅니다. 두 부호어⁠(codeword)⁠의 해밍 거리는 3이므로, 비트 하나가 뒤집혀 010이 오면 000과는 거리 1, 111과는 거리 2입니다. 가장 가까운 부호어로 고쳐 읽으면 됩니다. 여기서 부호어는 실제로 보내기로 약속한 비트 줄(여기서는 000과 111)입니다. 받은 말들을 가장 가까운 부호어별로 나누는 이 방법은 3절의 보로노이 지도를 0과 1의 공간에 그린 것과 같습니다.

해밍은 더 영리한 방법을 찾았습니다. 데이터 비트 4개에 2로 나눈 나머지⁠(remainder)⁠, 곧 홀짝을 맞추는 검사 비트⁠(check bit)⁠ 3개를 덧붙이면, 어떤 두 부호어도 적어도 세 자리가 다르게 만들 수 있습니다. 세 배가 아니라 1.75배만 보내고도 오류 하나를 고칩니다. 부호어들을 서로 멀리 떨어뜨려 놓으면, 잡음이 조금 밀어도 원래 자리를 알아볼 수 있다는 것입니다. 일반적으로 부호어 사이의 최소 거리가 $d$이면 $(d-1)/2$개 이하의 오류는 언제나 고칠 수 있습니다. 세 번 보내기라면 d = 3이라 (3 − 1)/2 = 1개입니다. 그만큼 밀려도 원래 부호어가 여전히 가장 가깝기 때문이고, 이것은 삼각부등식에서 바로 나옵니다.

그 한 줄을 풀어 봅시다. 보낸 부호어가 c이고, 오류 t개로 받은 말 r이 c에서 거리 t만큼 밀렸다고 합시다. 다른 부호어 c′은 c에서 적어도 d만큼 떨어져 있으니, 삼각부등식 d(c, c′) ≤ d(c, r) + d(r, c′)에서 d(r, c′) ≥ d − t입니다. t가 (d − 1)/2 이하이면 2t < d라서 d − t > t, 곧 r은 c′보다 c에 더 가깝습니다. 그래서 가장 가까운 부호어로 고쳐 읽으면 언제나 c로 돌아옵니다.

받는 쪽이 세 검사 비트만으로 틀린 자리의 번호를 곧바로 읽어 내는 해밍 부호⁠(Hamming code)⁠의 계산은 「짧게 보내기」 7절에서 직접 해 볼 수 있습니다.

해밍은 1947년에 이미 연구소 안의 메모로 자기 부호를 적어 두었지만, 회사가 특허를 먼저 내느라 논문은 3년 뒤에야 나왔습니다. 그 사이 그와 한때 한 사무실을 쓴 같은 연구소의 섀넌이 1948년 정보 이론 논문에서 해밍의 이름을 밝히며 그의 부호 하나를 예로 소개했습니다. 1949년에는 뉴저지 육군 통신 연구소의 마르셀 골레이가 그 예를 읽고, 오류 셋까지 고치는 부호를 한 쪽이 채 안 되는 메모로 발표했습니다(「잡음 너머로」). 해밍의 이름이 붙은 부호가 해밍의 논문보다 먼저 세상에 알려진 셈입니다.

이 생각은 멀리까지 갔습니다. 1969년 화성 곁을 지난 매리너 탐사선들은 부호어끼리 해밍 거리가 16 이상 떨어진 리드–뮬러 부호⁠(Reed–Muller code)⁠로 사진을 보냈습니다. 위의 규칙대로 (16 − 1)/2 = 7.5 이하, 곧 32비트마다 오류 7개까지 고칠 수 있었습니다. 1960년 MIT 링컨 연구소의 어빙 리드와 구스타브 솔로몬이 만든 리드–솔로몬 부호⁠(Reed–Solomon code)⁠는 뒤에 보이저 탐사선, 음악 CD, 그리고 1994년 일본 덴소가 자동차 부품을 추적하려고 만든 QR 코드에 들어갔습니다. QR 코드는 가장 높은 등급으로 만들면 30%쯤이 가려지거나 더러워져도 읽힙니다.

그렇다면 부호를 아무리 잘 만들어도 넘을 수 없는 선이 있을까요? 있습니다. 잡음 속에서 오류 확률⁠(probability)⁠을 원하는 만큼 작게 하면서 보낼 수 있는 정보의 양에는 한계가 있고, 1948년 섀넌이 정보의 양을 재는 엔트로피⁠(entropy)⁠를 바탕으로 그 한계를 정했습니다. 그 한계 자체의 이야기는 「잡음 너머로」에 있습니다. 그의 다른 얼굴인 암호 이론은 「나머지로 지키는 비밀」에 나옵니다.

해밍 거리는 길이가 같을 때만 쓸 수 있습니다. 'distance'를 'distnace'로 치면 해밍 거리는 2이지만, 'dstance'처럼 글자 하나를 빠뜨리면 길이가 달라지고 뒤의 모든 자리가 한 칸씩 어긋납니다. 사람의 오타는 대개 이런 빠뜨림과 끼워 넣음입니다.

1965년 블라디미르 레벤시테인은 모스크바의 소련 과학 아카데미 응용수학 연구소(지금의 켈디시 연구소)에서 글자가 빠지거나 끼어드는 오류를 고치는 부호를 연구하고 있었습니다. 그는 한 문자열을 다른 문자열로 바꾸는 데 필요한 글자 삽입·삭제·치환의 최소 횟수를 거리로 삼았습니다. 이것이 편집 거리⁠(edit distance)⁠, 또는 레벤시테인 거리입니다. 예를 들어 kitten을 sitting으로 바꾸려면 k를 s로, e를 i로 바꾸고 끝에 g를 넣으면 되니 세 번이면 됩니다. 아래 표로 계산해 보면 두 번으로는 안 되어, 편집 거리는 3입니다.

편집 거리는 표 하나를 채워 구합니다. 앞 글자부터 차례로 맞추어 가는 그 표의 규칙은 이렇습니다.

기호부터 읽어 봅시다. min{…}은 괄호 안의 세 값 가운데 가장 작은 것, $a_i$는 첫 단어의 i번째 글자, $b_j$는 둘째 단어의 j번째 글자이고, $[\,a_i \ne b_j\,]$는 두 글자가 다르면 1, 같으면 0입니다. 칸 $D_{i,j}$는 첫 단어의 앞 $i$글자를 둘째 단어의 앞 $j$글자로 바꾸는 최소 비용입니다. 위 칸에서 내려오면 글자 하나를 지우고, 왼쪽 칸에서 오면 하나를 넣고, 대각선으로 오면 바꾸거나(다르면 1) 그대로 둡니다(같으면 0). 세 길 가운데 가장 싼 것을 고르는 것입니다. 한 칸의 수는 이미 채운 이웃 세 칸만 보고 정해지니, 왼쪽 위에서 오른쪽 아래로 한 칸씩 채워 가면 맨 오른쪽 아래 칸이 두 단어 전체의 편집 거리입니다. 맨 윗줄과 맨 왼쪽 열은 빈 문자열에서 글자를 하나씩 넣거나 지우는 경우라 0, 1, 2, …로 시작합니다. 단어 쌍을 골라 보세요. 지금은 입니다.

편집 거리는 이고, 노란 길을 따라가면 (→는 바꾸기, +는 넣기, −는 지우기)로 바뀝니다. 해밍 거리는 . GATTACA 쌍처럼 길이가 같으면 편집 거리는 해밍 거리보다 클 수 없습니다. 바꾸기만으로도 해밍 거리만큼의 편집이 되니까요.

이 거리도 여러 곳에서 따로 태어났습니다. 레벤시테인보다 한 해 앞선 1964년, IBM의 프레드 대머로는 컴퓨터에 입력된 낱말의 철자 오류를 조사했습니다. 그리고 오류의 대부분이 글자 하나의 삽입, 삭제, 치환, 또는 이웃한 두 글자의 뒤바뀜이라는 것을 보이고, 그것을 잡아내는 프로그램을 만들었습니다. 1968년 소련의 빈츄크는 말소리의 빠르기가 다른 두 녹음을 맞대는 음성 인식에서 같은 모양의 표를 썼습니다. 표를 채우는 계산 순서가 로버트 와그너와 마이클 피셔의 이름으로 정리된 것은 1974년입니다.

표를 한 칸씩 채워 큰 문제를 작은 문제들의 답으로 푸는 이 방법을 동적 계획법⁠(dynamic programming)⁠이라 부릅니다. 이름을 붙인 사람은 1950년대 샌타모니카의 RAND 연구소에 있던 리처드 벨먼입니다. 그의 자서전에 따르면, 당시 국방 장관이 '연구'라는 말을 싫어해서 수학 연구처럼 들리지 않는 이름을 일부러 골랐습니다. 벨먼은 8절에 다시 나옵니다. 편집 거리의 표에서 칸마다 '세 후보 가운데 최솟값'을 고르고 비용을 '더해' 가는 계산은 지도 위의 최단 경로 계산과 같은 모양입니다. 최솟값과 덧셈 자리에 다른 연산을 넣으면 길의 가짓수나 가장 그럴듯한 해석을 구하는 계산이 됩니다. 이 이야기는 「같은 계산, 다른 덧셈」에 있습니다.

편집 거리는 곧 철자 교정기가 되었습니다. 잘못 친 단어와 편집 거리가 가장 작은 사전의 단어를 후보로 내놓으면 됩니다. 후보가 여럿일 때 더 흔한 단어를 고르도록 확률을 곁들인 교정기는 「말을 세는 기계」 7절에 나옵니다. 생물학에서는 더 큰 일을 했습니다. 1970년 시카고 노스웨스턴 대학의 솔 니들먼과 크리스천 운슈는 두 단백질의 아미노산 서열을 틈을 넣어 가며 맞대는 가장 좋은 방법을 같은 종류의 표로 구했습니다. 진화 과정에서 DNA에는 글자가 바뀌고, 빠지고, 끼어드는 변이가 쌓입니다. 그래서 두 서열의 편집 거리는 두 생물이 얼마나 오래전에 갈라졌는지 알려 주는 실마리가 됩니다. 오늘날 유전체 분석의 서열 정렬 도구들은 대부분 이 생각의 후손입니다. 빠른 도구들은 표 전체를 채우는 대신 가망 있는 부분만 골라 채웁니다.

정리하면, 해밍 거리는 길이가 같은 두 줄에서 다른 자리의 수이고, 편집 거리는 넣기·지우기·바꾸기의 최소 횟수입니다. 앞의 것은 부호어를 멀리 떨어뜨려 오류를 고치는 데, 뒤의 것은 오타와 DNA 변이처럼 글자가 빠지고 끼어드는 차이를 재는 데 쓰입니다.

6 · 퍼짐을 아는 거리캘커타의 마할라노비스

이 절의 물음은 이것입니다. 키와 몸무게처럼 단위도 다르고 서로 얽혀 있는 여러 수치를 한꺼번에 볼 때, 한 사람이 평균에서 '얼마나 멀리', 곧 얼마나 드물게 떨어져 있는지를 어떻게 잴까?

이제 거리가 통계학으로 들어갑니다. 1920년대 캘커타의 물리학 교수 프라산타 찬드라 마할라노비스는 인류학자들이 모은 신체 측정 자료를 분석해 달라는 부탁을 받았습니다. 벵골의 여러 카스트와 부족 집단에서 잰 머리 길이, 머리 너비, 코 높이 같은 수치들이었습니다. 시작은 인도 동물학 조사국장 넬슨 애넌데일이 맡긴 자료였습니다. 캘커타의 앵글로인디언, 곧 영국계와 인도계의 혼혈 공동체에게서 잰 자료로, 그 분석이 1922년 그의 첫 통계 논문이 되었습니다. 1927년 그는 런던 칼 피어슨의 연구실에서 몇 달을 보내며, 피어슨이 두 집단의 차이를 재려고 1926년에 내놓은 '인종 유사 계수'를 따져 보았습니다. 이 계수는 특징마다의 차이를 따로따로 더할 뿐 특징들 사이의 상관을 무시했고, 표본⁠(sample)⁠ 크기에 따라 값이 크게 흔들렸습니다. 그 약점을 고치려는 시도가 1930년의 첫 논문을 거쳐 1936년의 '일반화된 거리'가 되었습니다.

이 자료에는 어두운 배경이 있었습니다. 이런 자료는 영국 식민 당국의 인구 조사와 함께 쌓였고, 그 뒤에는 몸의 치수로 집단의 서열을 매기려던 당시 인종 과학의 그늘이 있었습니다. 1901년 인도 인구 조사를 이끈 허버트 리즐리는 코의 모양으로 카스트를 줄 세우기까지 했습니다. 오늘날 그런 서열화는 과학적으로도 윤리적으로도 받아들여지지 않습니다. 인구 조사의 자료로 사람을 가르고 줄 세운 일이 다른 나라들에서 어떤 결과를 낳았는지는 「줄 세우기의 한계」 8절에 있습니다. 그런데 이 자료에서 마할라노비스가 붙든 것은 순수하게 통계적인 물음이었습니다. 여러 특징을 한꺼번에 잰 두 무리가 서로 얼마나 다른가? 그 답은 원래의 물음보다 훨씬 오래 살아남았습니다.

특징들을 좌표로 놓고 유클리드 거리를 재면 두 가지 문제가 생깁니다. 첫째, 단위가 다른 특징들이 섞입니다. 센티미터로 잰 키와 킬로그램으로 잰 몸무게를 그대로 더할 수는 없습니다. 표준편차⁠(standard deviation)⁠는 값들이 평균에서 보통 얼마나 떨어져 있는지를 나타내는 수입니다. 각 특징에서 평균을 빼고 표준편차로 나누면(표준화⁠, standardization⁠) '평균에서 표준편차 몇 개만큼 떨어졌나'라는 단위 없는 수가 되어 서로 견줄 수 있습니다. 예를 들어 평균 키가 170cm, 표준편차가 6cm라면 182cm인 사람은 (182 − 170) ÷ 6 = 2, 곧 표준편차 두 개만큼 큽니다.

둘째, 특징들이 상관되어 있습니다. 한쪽이 크면 다른 쪽도 큰 경향이 있다는 뜻입니다. 이 경향의 세기를 −1에서 1 사이의 수로 나타낸 것이 상관계수⁠(correlation coefficient)⁠이고, 0이면 경향이 없고 1에 가까울수록 강합니다. 키가 큰 사람은 대개 몸무게도 많이 나가므로 키와 몸무게가 둘 다 큰 것은 놀랍지 않지만, 키가 큰데 몸무게가 가벼운 것은 드뭅니다. 표준화한 값으로 (2, 2)인 사람과 (2, −2)인 사람은 평균에서 곧게 잰 거리가 같지만, 둘째 사람이 훨씬 드뭅니다. 1936년 마할라노비스가 발표한 '일반화된 거리', 오늘날의 마할라노비스 거리⁠(Mahalanobis distance)⁠는 이 두 가지를 모두 계산에 넣습니다. 아래는 가상의 400명에게서 잰 키와 몸무게를 표준화한 자료이고, 둘 사이의 상관은 입니다(표본에서 잰 상관계수 ). P와 Q를 끌어 보며, 곧게 잰 거리로는 비슷한 두 사람이 마할라노비스 거리로는 얼마나 달라지는지 보세요.

평균에서의 직선거리는 P가 , Q가 입니다. 그런데 마할라노비스 거리로는 P가 , Q가 입니다. . 400명 가운데 P보다 마할라노비스 거리가 먼 사람은 , Q보다 먼 사람은 입니다. 직선거리로 따지면 각각 와 입니다. 누가 정말 드문 사람, 곧 이상값인지는 마할라노비스 거리가 알려 줍니다.

식이 낯설어 보이지만 특징이 하나뿐일 때를 먼저 보면 뜻이 드러납니다. 그때 이 식은 $|x - \mu| / \sigma$, 곧 '평균에서 표준편차 몇 개만큼 떨어졌나'가 됩니다(σ는 표준편차). 위의 182cm인 사람이라면 2입니다. 마할라노비스 거리는 이 '표준편차 몇 개'를 특징이 여럿이고 서로 얽혀 있을 때로 넓힌 것입니다.

식의 기호를 읽어 봅시다. $\mathbf{x}$는 한 사람의 측정값들을 묶은 것, $\mu$('뮤')는 평균, $\Sigma$('시그마')는 공분산⁠(covariance)⁠ 행렬⁠(matrix)⁠입니다. 여기서 Σ는 합의 기호가 아니라 이 행렬의 이름입니다. 행렬은 수를 가로세로로 늘어놓은 표이고, 이 표의 대각선에는 각 특징이 퍼진 정도(분산⁠(variance)⁠, 표준편차의 제곱)가, 나머지 칸에는 두 특징이 함께 움직이는 정도(공분산)가 들어 있습니다. 식 옆의 표가 지금 자료의 Σ입니다. 윗첨자 T는 세로로 적은 값들을 가로로 눕힌다는 표시로, 곱셈의 모양을 맞추는 장치입니다. $\Sigma^{-1}$('시그마 역행렬⁠(inverse matrix)⁠')을 곱하는 것은 공분산으로 나누는 셈이라, 퍼짐이 큰 방향의 차이일수록 작게 셉니다. 한 특징일 때 σ로 나누던 것을 여러 특징으로 넓힌 것입니다.

기하학적으로 보면, 이 거리는 비스듬히 늘어진 타원 모양의 구름을 둥근 구름으로 펴는 선형변환⁠(linear transformation)⁠을 한 뒤에 잰 유클리드 거리입니다. 타원의 축은 공분산 행렬⁠(covariance matrix)⁠의 고유벡터⁠(eigenvector)⁠이고, 축의 길이는 고유값⁠(eigenvalue)⁠의 제곱근에 비례합니다. 자료가 가장 넓게 퍼진 방향을 찾는 주성분 분석⁠(principal component analysis)⁠과 같은 재료입니다. 행렬을 곱해도 방향이 바뀌지 않는 벡터⁠(vector)⁠가 고유벡터이고, 그때 곱해지는 배수⁠(multiple)⁠가 고유값입니다.

자료가 정규분포(평균 둘레에 종 모양으로 몰리는 분포)를 따르면, 두 특징일 때 거리 $d$보다 바깥에 있을 비율은 $e^{-d^2/2}$입니다. 거리 2이면 $e^{-2} \approx 0.14$, 곧 14%쯤이고, 거리 3이면 $e^{-4.5} \approx 0.011$, 곧 100명에 한 명꼴입니다. 표를 보지 않고도 얼마나 드문지 말할 수 있습니다. 상관을 0으로 내리면 타원이 원이 되고 두 거리가 같아집니다. 처음으로

정리하면, 마할라노비스 거리는 '평균에서 표준편차 몇 개'를 여러 특징으로 넓힌 것으로, 자료가 퍼진 모양을 따라 늘어진 타원을 '같은 거리'의 곡선으로 삼습니다. 그래서 자료의 흐름에서 벗어난 점을 멀다고, 곧 드물다고 판정합니다.

이 거리는 오늘날 공장 센서의 이상 신호, 카드 결제의 이상 거래를 찾는 데 쓰입니다. 같은 1936년, 런던의 로널드 피셔는 붓꽃 세 종의 측정값으로 종을 가르는 판별 분석⁠(discriminant analysis)⁠을 발표했습니다. 이것도 같은 공분산 행렬로 기울어진 구름을 다루는 방법입니다. 피셔가 어떤 인물이었는지는 「담배와 폐암」에 있습니다.

마할라노비스의 일은 캘커타를 중심으로 퍼졌습니다. 케임브리지에서 들고 온 학술지, 산티니케탄의 타고르, 마하나디강의 홍수 기록, 그리고 델리의 계획 위원회. 식민지의 통계 기관이 독립 국가의 계획 기관이 되어 가는 길이자, 인류학 자료실에서 태어난 거리 하나가 나라 전체를 표본으로 재는 도구 상자로 옮겨 간 길입니다.

7 · 이웃에게 묻기최근접 이웃⁠(nearest neighbor)⁠, k-평균, 그리고 공정함

이 절의 물음은 이것입니다. 거리만 있으면 새 대상이 어느 무리에 속하는지 가릴 수 있을까? 그리고 거리를 어떻게 고르느냐가 그 판정을, 나아가 사람을 두고 내리는 판단을 어떻게 바꿀까?

거리를 알면 분류를 할 수 있습니다. 1951년 캘리포니아 대학교 버클리의 통계학자 에벌린 픽스와 조지프 호지스는 미 공군 항공의학교의 보고서에서, 자료가 어떤 분포를 따르는지 가정하지 않는 판별법을 제안했습니다. 새 대상이 오면 이미 답을 아는 예들 가운데 가장 가까운 몇 개를 찾아 다수결로 정하는 것입니다. 이것이 최근접 이웃 분류⁠(k-nearest neighbors classification)⁠입니다. 1967년 정보이론가 토머스 커버와 피터 하트는 예가 충분히 많으면 가장 가까운 이웃 하나만 보는 규칙도, 가능한 가장 좋은 분류기의 오류율의 두 배를 넘지 않는다는 것을 증명했습니다. 여기서 '가장 좋은 분류기'는 자료를 만든 확률 분포를 완전히 알고서 자리마다 더 그럴 법한 쪽을 고르는 분류기로, 어떤 방법도 이보다 오류를 적게 낼 수는 없습니다. 예를 모두 외워 두고 가까운 것을 따르는 이 방법과 정반대로, 예를 하나씩 보며 경계선 하나를 스스로 고쳐 가는 퍼셉트론⁠(perceptron)⁠은 1958년에 나왔습니다(「배우는 기계」 2절).

아래 그림의 분홍과 파랑 점이 답을 아는 예이고, 배경은 평면의 모든 점을 이웃 $k =$ 개의 다수결로 칠한 결과입니다. 거리는 를 쓰고, 가로 차이를 배로 늘려 잽니다. 가로축의 단위를 바꾸는 것과 같습니다.

노란 점의 이웃 투표는 , 그래서 으로 분류됩니다. 예를 하나씩 빼고 나머지로 그 예를 맞혀 보면 정답률은 입니다. k를 1로 내리면 경계가 점 하나하나를 따라 들쭉날쭉해지고, k를 크게 올리면 매끈해지다가 끝내 세부를 잃습니다. 이번에는 k를 15로 두고 가로 배율을 5로 올려 보세요. 가로로 조금만 떨어져도 먼 이웃이 되어 버려, 이웃이 거의 같은 세로줄에서만 뽑힙니다. 그래서 경계가 세로 줄무늬로 무너지고 정답률이 89%쯤에서 73%쯤으로 떨어집니다. 배율 0.2로 내리면 이번에는 세로 차이만 보게 되어, 정답률은 거의 그대로이지만 경계의 물결이 눈에 띄게 납작해집니다. 자료는 그대로인데 '누가 이웃인가'를 정하는 방식만 바꾸었을 뿐입니다.

이 방법의 밑바탕에는 가까운 것은 닮았으리라는 믿음이 있습니다. 지리학자 월도 토블러는 1970년 이것을 '지리학의 제1법칙'이라 불렀습니다. "모든 것은 다른 모든 것과 관련되어 있지만, 가까운 것이 먼 것보다 더 관련되어 있다." 최근접 이웃 분류는 이 법칙을 특징의 공간으로 옮긴 것이고, 그 공간에서 무엇을 '가깝다'고 할지는 우리가 정합니다.

이웃의 생각을 뒤집으면 무리 짓기가 됩니다. 점들을 k개의 무리로 나누고 싶다면, 무리마다 중심을 하나씩 두고 각 점을 가장 가까운 중심에 배정한 뒤(곧 중심들의 보로노이 지도를 그린 뒤), 각 무리의 평균으로 중심을 옮기기를 되풀이하면 됩니다. 이것이 k-평균 군집⁠(k-means clustering)⁠입니다.

거리와 이어지는 대목은 중심을 옮기는 규칙입니다. 중심을 평균으로 옮기는 것은 평균이 거리의 제곱 합을 가장 작게 하는 점이기 때문입니다. 수직선 위의 세 점 1, 2, 6으로 확인해 봅시다. 평균 3에서 재면 제곱 합이 4 + 1 + 9 = 14이고, 다른 어느 점에서 재도 이보다 큽니다(예를 들어 2에서는 1 + 0 + 16 = 17). 제곱 대신 맨해튼 거리, 곧 차이의 절댓값의 합을 쓰면 평균 자리에 좌표마다의 중앙값⁠(median)⁠이 들어갑니다. 세 점의 중앙값 2에서 재면 절댓값 합이 1 + 0 + 4 = 5로, 평균 3에서의 2 + 1 + 3 = 6보다 작습니다. 어떤 거리를 쓰느냐가 '무리의 중심'이라는 말의 뜻까지 바꾸는 것입니다.

이 방법은 여러 사람이 따로 찾아냈습니다. 1957년 벨 연구소의 스튜어트 로이드는 전화 신호를 몇 개의 대표값으로 줄이는 문제에서 이 방법을 만들었지만, 그의 내부 문서는 1982년에야 학술지에 실렸습니다. 그보다 앞선 1956년에는 폴란드 브로츠와프의 수학자 후고 슈타인하우스가 비슷한 생각을 냈고, 1967년에는 통계학자 제임스 맥퀸이 'k-평균'이라는 이름을 붙였습니다. 제곱과 절댓값 사이의 선택에도 역사가 있습니다. 18세기 예수회 수학자 루제르 보스코비치가 절댓값 기준을 택하고 르장드르와 가우스가 제곱을 택한 이야기가 「잃어버린 소행성」에 있습니다.

'가깝다'를 정하는 일에는 결과가 따릅니다. 대출 심사에서 신청자의 특징에 우편번호를 넣었다고 합시다. 인종을 특징으로 쓰지 않았더라도 문제가 생깁니다. 1930년대 미국의 주택 소유자 대출 공사는 흑인과 이민자가 많은 동네를 지도에 붉게 칠했는데, 이른바 '레드라이닝'이 남긴 이 거주 분리가 미국 도시의 우편번호와 강하게 상관되어 있기 때문입니다. 그러면 특징 공간의 이웃들이 과거의 차별을 그대로 물려받고, 모형은 인종을 한 번도 보지 않은 채 인종에 따라 다른 답을 냅니다. 이런 특징을 대리 변수⁠(proxy variable)⁠라고 부릅니다. 어떤 특징을 넣고 각 특징에 얼마의 무게를 줄지, 곧 어떤 거리를 고를지는 기술적인 선택이면서 동시에 무엇을 같은 것으로 취급할지를 정하는 가치 판단입니다. 4절의 트버스키가 보여 준 대로, 닮음은 세계에 적혀 있는 사실이 아니라 우리가 고르는 관점입니다.

8 · 높은 차원의 거리차원의 저주⁠(curse of dimensionality)⁠, 방향의 닮음, 흙 옮기기

이 절의 물음은 이것입니다. 좌표가 수백, 수천 개인 자료에서도 거리는 여전히 쓸모가 있을까? 쓸모가 줄어든다면 무엇으로 바꿔 재야 할까?

벨먼은 동적 계획법을 다룬 1957년 무렵의 책에서, 변수가 하나 늘 때마다 살펴야 할 격자가 몇 배씩 불어나는 어려움을 '차원의 저주'라고 불렀습니다. 한 변을 10칸으로 나누면 2차원은 100칸, 10차원은 100억 칸입니다. 거리에도 차원의 저주가 있습니다. $d$차원 정육면체 안에 무작위로 점 60개를 뿌리고, 1,770쌍의 거리를 모두 재어, 각 거리를 평균 거리로 나눈 비율로 히스토그램⁠(histogram)⁠을 그려 봅시다. 차원은 $d =$ 입니다. 2 10 100 1000

지금 평균 거리는 이고, 거리들의 퍼짐(표준편차 ÷ 평균)은 입니다. 첫 번째 점에서 보면 가장 먼 점이 가장 가까운 점보다 배 멉니다. 차원을 올리면 히스토그램이 평균 둘레의 좁은 기둥으로 모여듭니다. 1,000차원에서는 거의 모든 쌍이 평균 거리의 몇 퍼센트 안에 있고, 가장 가까운 이웃과 가장 먼 이웃이 거의 같은 거리에 있습니다. '가장 가까운 이웃'이라는 말이 뜻을 잃기 시작하는 것입니다.

까닭은 확률에 있습니다. 거리의 제곱은 서로 독립인 $d$개의 좌표 차이 제곱을 더한 것입니다. 0과 1 사이에서 두 수를 아무렇게나 고르면 그 차이의 제곱은 평균이 $1/6$입니다. 그래서 그 합의 평균은 $d/6$으로 차원에 비례해 커지지만, 흔들림(표준편차)은 $\sqrt d$에 비례해서만 커집니다. 서로 독립인 값들을 더하면 어떤 것은 평균보다 크고 어떤 것은 작아서, 들쭉날쭉함이 서로 상쇄되기 때문입니다. 100차원이면 평균은 100배, 흔들림은 10배로 커지니, 흔들림을 평균으로 나눈 비율은 10분의 1로 줄어듭니다. 큰 수의 법칙(「도박판에서 온 편지」)이 거리에서 작동해, 상대적인 퍼짐이 $1/\sqrt d$로 줄어듭니다. 이 그림 자체가 무작위 점으로 답을 어림하는 몬테카를로 방법⁠(Monte Carlo method)⁠입니다. 그래서 수백 차원의 자료를 다루는 사람들은 차원을 줄이거나(6절의 주성분 분석), 크기 대신 방향만 보는 거리를 씁니다.

방향의 닮음. 두 문서가 비슷한 주제인지 보려고 단어마다 나온 횟수를 적은 벡터를 만든다고 합시다. 긴 문서는 모든 단어가 많이 나오니 벡터가 길고, 짧은 문서와의 유클리드 거리는 주제가 같아도 멉니다. 길이를 무시하고 두 벡터 사이의 각만 보면 됩니다. 내적⁠(dot product)⁠을 길이로 나눈 코사인 유사도⁠(cosine similarity)⁠입니다. 내적은 두 벡터의 같은 자리 성분끼리 곱해 모두 더한 값이고, 길이는 성분의 제곱 합의 제곱근(유클리드 길이)입니다.

단어가 '고양이', '개' 둘뿐이라 치고, 한 문서에서 두 단어가 각각 2번, 1번 나오고 두 배 긴 다른 문서에서 4번, 2번 나온다고 합시다. 벡터 (2, 1)과 (4, 2)는 유클리드 거리가 $\sqrt{2^2 + 1^2} = \sqrt 5 \approx 2.24$이지만 방향이 같습니다. 내적은 2 × 4 + 1 × 2 = 10, 길이는 $\sqrt 5$와 $\sqrt{20}$이니 코사인 유사도는 $10 / \sqrt{100} = 1$, 곧 사잇각 0°입니다. 주제의 비율이 같으면 길이와 상관없이 1이 나옵니다.

식의 $\mathbf u \cdot \mathbf v$는 내적, $\lVert \mathbf u \rVert$는 u의 길이입니다. 오른쪽 식은 길이를 1로 맞춘 두 벡터 사이의 거리와 코사인의 관계로, 거리의 제곱을 풀어 쓰면 나옵니다. $\lVert \mathbf u - \mathbf v \rVert^2 = \lVert \mathbf u \rVert^2 - 2\,\mathbf u \cdot \mathbf v + \lVert \mathbf v \rVert^2 = 1 - 2\cos\theta + 1$입니다. 그래서 길이를 1로 맞춘 벡터끼리는 코사인이 클수록 유클리드 거리가 짧으니 둘은 같은 순위를 줍니다. 1960–70년대 제라드 솔턴은 SMART라는 문서 검색 시스템에서 이 '벡터 공간⁠(vector space)⁠ 모형'을 다듬었습니다. SMART는 하버드에서 시작해 1965년부터 코넬 대학에서 이어 간 시스템이고, 이 모형은 검색 엔진의 뿌리가 되었습니다. 통계학자에게도 낯익은 식입니다. 평균을 뺀 두 벡터의 코사인이 바로 피어슨의 상관계수입니다(「담배와 폐암」 3절).

코사인은 단어의 뜻을 재는 데까지 갔습니다. 2013년 구글의 토마시 미콜로프와 동료들은 word2vec으로 단어 하나하나를 수백 차원의 벡터로 바꾸어, 비슷하게 쓰이는 단어일수록 코사인 유사도가 크게 만들었습니다. '왕 − 남자 + 여자'에 가장 가까운 벡터가 '여왕'이라는 예가 유명해졌습니다. 다만 이 결과는 보통 입력한 단어들을 후보에서 빼고 얻은 것이고, 빼지 않으면 '왕' 자신이 가장 가깝게 나오는 경우가 많다는 반론이 있습니다. 2016년에는 같은 방법으로 '남자 : 프로그래머 = 여자 : 주부' 같은 유추가 나온다는 연구가 발표되어, 말뭉치⁠(corpus)⁠에 담긴 편견이 벡터의 거리에 그대로 새겨진다는 것이 드러났습니다. 오늘날의 언어 모델⁠(language model)⁠ 속 어텐션⁠(attention)⁠도 낱말마다 만든 쿼리⁠(query)⁠ 벡터와 키 벡터의 내적으로 어느 낱말을 얼마나 참고할지 정합니다. 다만 길이로 나누지 않고 벡터 차원의 제곱근으로만 나누므로 코사인 유사도와 같지는 않습니다(「다음 단어를 맞히는 기계」). 질문과 코사인이 큰 문서를 찾아 언어 모델의 문맥에 넣어 주는 검색 증강 생성⁠(retrieval-augmented generation)⁠은 솔턴의 벡터 공간 모형이 반세기 뒤 언어 모델과 만난 모습입니다.

흙을 옮기는 거리. 점과 점 사이가 아니라 분포와 분포 사이의 거리도 잴 수 있을까요? 이 물음은 뜻밖에 공병의 일에서 시작했습니다. 메지에르 왕립 공병학교에서 요새 축성을 가르치던 수학자 가스파르 몽주는 1781년 파리 과학 아카데미에 낸 논문에서, 한곳에서 파낸 흙을 다른 곳에 쌓을 때 흙의 양에 옮긴 거리를 곱한 총비용을 가장 작게 하는 방법을 물었습니다.

이 문제는 전혀 다른 곳에서 되살아났습니다. 150여 년 뒤 레닌그라드의 수학자 레오니트 칸토로비치는 합판 공장에서 원목과 기계를 어떻게 짝지어야 생산이 가장 많은지 알려 달라는 자문 요청을 받았습니다. 그리고 1939년 그 답에서 선형 계획법⁠(linear programming)⁠의 뼈대를 세웠습니다. 선형 계획법은 '기계마다 하루 몇 시간까지'처럼 일차식으로 적힌 제약을 모두 지키면서, 생산량처럼 일차식으로 적힌 목표를 가장 크게(또는 비용을 가장 작게) 만드는 값을 찾는 방법입니다. 1942년에는 흙을 쪼개어 여러 곳으로 나눌 수 있게 몽주의 문제를 넓혔습니다. 계획 경제의 소련에서 그의 '최적 가격'은 한동안 이념적인 의심을 받았다고 전하지만, 1975년 그는 전시 미국에서 수송 문제를 연구한 네덜란드 출신 경제학자 찰링 쿠프만스와 함께 노벨 경제학상을 받았습니다. 흙 대신 사람과 일을 하나씩 짝지어 비용을 가장 작게 하는 배정 문제⁠(assignment problem)⁠도 있습니다. 1955년 미국의 수학자 해럴드 쿤은 헝가리 수학자 쾨니그 데네시와 에게르바리 예뇌가 1931년에 쓴 논문들에서 얻은 생각으로 '헝가리안 방법⁠(Hungarian method)⁠'을 만들어 이 문제를 풀었습니다(「짝을 찾는 알고리즘」 3절).

이 최소 비용이 두 분포 사이의 거리, 최적 수송⁠(optimal transport)⁠ 거리 또는 바서슈타인 거리입니다. 흙의 전체 양을 1로 잡고, 흙더미 하나를 모양 그대로 오른쪽으로 2만큼 옮겨야 한다면 모든 흙이 2씩 움직이니 거리는 2입니다. 흙의 절반만 3만큼 옮기면 되는 경우라면 0.5 × 3 = 1.5입니다. 한 줄 위의 분포라면 이 값은 두 누적분포함수(값이 $x$ 이하일 확률을 $x$마다 적은 곡선) 사이의 넓이와 같습니다.

이 거리에는 이름이 여럿입니다. '바서슈타인'은 1969년 이 거리를 확률 과정 연구에 쓴 소련의 수학자 레오니트 바세르시테인의 이름을 독일식으로 읽은 것입니다. 1998년 스탠퍼드의 컴퓨터 비전 연구자 루브너, 토마시, 기바스는 이 거리를 이미지 검색에 쓰면서, 흙더미를 옮기는 비유를 딴 '흙 옮기는 거리'(Earth Mover's Distance)라는 이름을 널리 퍼뜨렸습니다. 몽주의 공병 문제가 두 세기 넘게 지나 같은 비유로 돌아온 셈입니다. 최적 수송의 수학을 깊이 파고든 세드리크 빌라니는 2010년 필즈상⁠(Fields Medal)⁠을 받았고, 2017년에는 이 거리로 생성 모형을 학습시키는 방법인 바서슈타인 GAN이 나왔습니다. 두 사진의 색 분포를 비교하는 이미지 검색, 생성 모형의 학습에 이 거리가 쓰이는 것은, 두 분포가 겹치지 않을 때에도 '얼마나 옮겨야 하는지'를 부드럽게 알려 주기⁠(period)⁠ 때문입니다. 땅 위의 거리를 재료로 확률 분포들 사이의 거리를 짓는 셈이고, 옮기는 비용이 유한한 분포끼리라면 이 거리도 4절의 세 규칙을 모두 지킵니다.

정리하면, 차원이 높아지면 모든 점이 서로 거의 같은 거리에 놓여 '가장 가까운 이웃'이 흐려집니다. 그래서 크기 대신 방향을 재는 코사인 유사도나, 점이 아니라 분포 전체를 옮기는 비용으로 재는 최적 수송 거리처럼 대상에 맞춘 거리가 필요해집니다.

9 · 이어지는 길열 가지 거리, 한 장의 표

이 글에 나온 거리들을 한곳에 모아 봅시다. 아래 그림의 두 점 P, Q를 끌면 표의 위쪽 다섯 줄이 바뀝니다. 문자열과 집합은 앞의 절들에서 고른 것을 그대로 쓰고, 도시는 표 안에서 고릅니다.

문자열은 5절에서 고른 쌍() 그대로입니다. 코사인과 자카드, 다이스는 닮을수록 커지는 유사도입니다. 1에서 빼면 멀수록 커지는 값이 되지만, 4절의 세 규칙까지 모두 지키는 것은 $1 - J$뿐입니다. $1 - D$는 4절에서 보았듯 삼각부등식을 어길 수 있습니다. $1 - \cos\theta$도 마찬가지입니다. 방향이 0°, 45°, 90°인 세 화살표라면 이웃끼리는 1 − cos 45° ≈ 0.29씩인데 양 끝은 1 − cos 90° = 1입니다. 0.29 + 0.29 = 0.58이 1보다 작으니 삼각부등식이 깨집니다. 게다가 방향이 같으면 서로 다른 점에도 0을 줍니다. 방향 사이의 참된 거리가 필요하면 사잇각 θ 자체를 쓰면 됩니다. 점 P를 원점 쪽으로 끌어당겨 보세요. 유클리드 거리는 바뀌지만 방향이 그대로인 한 코사인 유사도는 변하지 않습니다.

한 번 더 멀리서 보면, 이 글에 나온 거리들은 실용적인 기관에서 태어난 경우가 많았습니다. 요새를 쌓는 공병학교(몽주), 전화 회사의 연구소(해밍, 로이드, 섀넌), 공군이 세운 연구소와 학교(벨먼, 픽스와 호지스), 식민지와 독립 국가의 통계 기관(마할라노비스), 계획 경제의 합판 공장(칸토로비치), 자동차 부품 공장(QR 코드). 이론은 대개 파리와 괴팅겐의 대학에서 다듬어졌지만, 물음은 흙과 전화선과 인구 조사표에서 왔습니다.

위: 1750년부터 오늘까지. 수학 줄(파랑)의 사건들이 18세기 파리에서 20세기 초 괴팅겐·파리·바르샤바를 거쳐 1950년대 미국의 연구소들로 옮겨 가는 것을 보세요. 철학 줄에서는 푸앵카레와 아인슈타인이 물리 공간의 거리가 약속인지 사실인지를 다투었고, 비트겐슈타인, 토블러, 트버스키가 '닮음'을 다른 쪽에서 물었습니다. 아래: 사람과 생각이 오간 길. 노란 선은 자리를 옮긴 사람, 주황 선은 이어진 생각입니다.

• 제곱이냐 절댓값이냐: 유클리드 거리의 제곱 합을 줄이면 평균과 최소제곱 회귀⁠(least-squares regression)⁠가, 맨해튼 거리의 합을 줄이면 중앙값과 최소절댓값 회귀가 나옵니다. 그 선택의 역사가 「잃어버린 소행성」입니다.
• 거리로 벌점 매기기: L2 노름의 제곱을 벌점으로 붙이면 릿지 회귀⁠(ridge regression)⁠가, L1 노름을 붙이면 대부분의 계수가 정확히 0이 되는 성긴 답이 나옵니다. 마름모 모양의 L1 단위원이 모서리에서 답을 붙잡기 때문입니다. 흐린 사진과 CT에서 이 선택이 하는 일은 「거꾸로 푸는 문제는 왜 어려운가」에 있습니다.
• 자의 길이에 따라 달라지는 길이: 해안선은 짧은 자로 잴수록 길어집니다. 하우스도르프가 1918년 내놓은 차원과, 거리를 재는 방식이 결과를 바꾸는 여러 이야기는 「재는 순간 바뀐다」에 있습니다.
• 굽은 공간의 거리: 리만은 1854년 점마다 길이를 재는 규칙으로 휘어진 공간을 정의했고, 그 공간의 가장 짧은 길이 측지선입니다. 민코프스키의 평평한 시공간을 리만의 방식으로 휘게 하고 그 휨을 중력으로 읽은 것이 일반 상대성 이론입니다(「평행선의 반란」).
• 그래프의 거리: 도로망의 최단 경로, 사람 사이의 여섯 단계, 웹 페이지 사이의 링크 거리는 모두 그래프 거리입니다(「일곱 다리의 도시」).
• 멀어지는 두 궤적: 거의 같은 곳에서 출발한 두 궤적 사이의 거리가, 아직 작은 동안 기하급수적으로 커지는 것이 혼돈⁠(chaos)⁠의 핵심 징표입니다. 거리의 증가율이 예측의 한계를 정합니다(「나비의 날갯짓」).
• 부호와 암호: 해밍 거리는 잡음을 이기는 부호를, 모듈러 연산⁠(modular arithmetic)⁠은 엿듣는 사람을 이기는 암호를 만듭니다. 벨 연구소의 섀넌은 잡음 속 통신의 한계(1948)와 암호의 수학적 이론(1949)을 함께 썼습니다(「나머지로 지키는 비밀」).
• 함수 사이의 거리: 푸리에 급수가 원래 함수에 '수렴한다'는 말은 어떤 거리로 재느냐에 따라 참이 되기도 거짓이 되기도 합니다. 함수들의 공간은 무한 차원이라, 거리의 규칙만으로 버티는 추상화가 꼭 필요했습니다(「원에서 파동으로」).
• 말의 거리: 편집 거리와 단어 임베딩⁠(word embedding)⁠이 언어 연구의 긴 역사 속에서 어디쯤 있는지는 「말을 세는 기계」에서 이어집니다.