가장 좋은 것 고르기

가장 짧은 길, 가장 크게 접히는 상자, 점들 사이를 가장 잘 지나는 직선, 잡음 속에서 가장 많이 보낼 수 있는 부호, 가장 적게 틀리는 신경망. 서로 상관없어 보이는 이 질문들은 모두 '가장'이라는 말을 품고 있고, 뿌리가 같은 대답을 가집니다. 가장 좋은 자리에서는 조금 움직여도 거의 달라지지 않는다. 매끄러운 산꼭대기에서 한 발짝 옮기면 높이는 발걸음의 크기가 아니라 그 제곱에 비례하는 만큼만 변합니다. 갈림길을 고르는 문제처럼 '조금 움직이기'가 없는 곳에서는 이 말이 '조금 바꿔도 나아지지 않는다'로 모양을 바꿉니다. 이 '작은 변화에 대한 무감각'이 최적을 알아보는 표지이고, 동시에 최적을 찾아가는 길잡이입니다.

아래 그림의 문제: (누르면 바뀝니다). 왼쪽은 문제의 장면, 오른쪽은 조절 손잡이 하나에 따른 비용(또는 이득)의 그래프입니다. 왼쪽의 노란 점을 끌거나 가장 좋은 곳으로를 눌러 보세요.

문제는 전혀 다르지만 오른쪽 그래프에서 일어나는 일은 같습니다. 가장 좋은 곳에서 접선(청록)이 수평이 되고, 그래서 손잡이를 조금 움직여도 값이 거의 변하지 않습니다. 그리고 그 '수평' 조건을 원래 문제의 말로 옮기면 문제마다 이름난 법칙이 나옵니다. 상자에서는 도함수⁠(derivative function)⁠가 0이라는 식, 빛에서는 굴절의 사인⁠(sine)⁠ 법칙, 직선 맞추기에서는 잔차⁠(residual)⁠가 x와 직교⁠(orthogonality)⁠한다는 정규방정식입니다.

꼭대기는 평평하다. 1615년 천문학자 요하네스 케플러는 포도주 통의 부피를 재는 책을 쓰면서, 통의 모양이 가장 좋은 비율 근처에 있을 때는 비율을 조금 바꿔도 부피가 거의 변하지 않는다는 것을 알아챘습니다. 20년쯤 뒤 페르마가 이것을 계산법으로 만들었습니다. $x(b-x)$를 가장 크게 하려면 x를 아주 조금 옮긴 값과 원래 값을 '거의 같다'고 놓고, 차이를 옮긴 양으로 나눈 뒤 그 양을 지웁니다. 미분⁠(differentiation)⁠이 태어나기도 전에 '최댓값에서 기울기⁠(slope)⁠는 0'이라는 원리가 먼저 있었던 셈이고, 그래서 최적화⁠(optimization)⁠는 주로 도함수의 0점을 찾는 문제가 되었습니다. 다만 이 원리는 구간의 안쪽, 미분할 수 있는 점에서만 통하니, 구간의 끝과 꺾인 점은 따로 살펴야 합니다. 변수가 여럿이면 모든 방향의 기울기가 0이어야 합니다. 변수마다의 기울기를 모은 벡터⁠(vector)⁠를 그래디언트⁠(gradient)⁠라 하는데, 그래디언트는 값이 가장 가파르게 커지는 방향을 가리키고, 최적에서는 그 벡터가 0이 됩니다.

빛은 가장 빠른 길로 간다. 1세기 알렉산드리아의 헤론은 거울에 비친 빛이 두 점 사이의 가장 짧은 길을 간다는 것으로 반사의 법칙(입사각 = 반사각)을 설명했습니다. 굴절은 더 어려웠습니다. 빛은 물로 들어가며 꺾이니 가장 짧은 길로 가지 않습니다. 1662년 페르마는 빛이 가장 짧은 시간이 걸리는 길로 간다고 보고, 물속에서 빛이 더 느리다고 가정해 데카르트가 발표했던 굴절의 사인 법칙을 이끌어 냈습니다. 그림의 '빛의 굴절'에서 접선⁠(tangent line)⁠이 수평이 되는 곳을 찾으면 $\sin\theta_1 / \sin\theta_2 = v_1 / v_2$가 저절로 나옵니다. 데카르트는 빛이 물속에서 더 빠르다는 정반대의 가정으로 같은 법칙에 이르렀고, 어느 쪽이 옳은지는 1850년 프랑스의 물리학자 레옹 푸코가 물속의 빛이 더 느리다는 것을 잰 실험으로 가려졌습니다. 페르마 쪽이었습니다. 곡면 위의 가장 짧은 길인 측지선⁠(geodesic)⁠과 지구 위의 대원 항로(구면기하⁠, spherical geometry⁠)도 같은 원리의 후손입니다.

곡선 전체를 고르기. 1696년 스위스의 수학자 요한 베르누이는 한 점에서 다른 점으로 가장 빨리 미끄러져 내려가는 곡선(최단 강하선⁠, brachistochrone⁠)을 물었고, 뉴턴, 라이프니츠, 형 야코프 베르누이가 답이 직선이 아니라 사이클로이드⁠(cycloid)⁠, 곧 굴러가는 바퀴 위의 한 점이 그리는 곡선임을 보였습니다. 처음에 가파르게 떨어져 속도⁠(velocity)⁠를 먼저 얻는 편이 길이 조금 길어도 더 빠른 것입니다. 이번에는 수 하나가 아니라 곡선 전체가 손잡이입니다. 그래도 원리는 같습니다. 가장 좋은 곡선을 아주 조금 비틀어도 걸리는 시간은 거의 변하지 않아야 합니다. 이 조건을 방정식으로 만든 것이 오일러와 열아홉 살 라그랑주의 변분법⁠(calculus of variations)⁠이고, 1830년대 해밀턴은 역학 전체를 이 원리로 다시 썼습니다. 물체가 실제로 가는 길은 '작용', 곧 운동 에너지⁠(kinetic energy)⁠에서 위치 에너지를 뺀 값을 시간에 걸쳐 더한 양이 길을 조금 비틀어도 거의 변하지 않는(정체하는) 길이라는 것입니다. 조건이 붙으면 모양이 조금 바뀝니다. 곡선 $g = c$ 위에서 f를 가장 크게 하는 점에서는 f의 등고선이 조건의 곡선에 접해 두 그래디언트가 평행합니다($\nabla f = \lambda \nabla g$). 이 λ가 라그랑주 승수⁠(Lagrange multiplier)⁠이고, 0 이상의 값을 갖고 평균⁠(mean)⁠이 정해진 분포 가운데 엔트로피⁠(entropy)⁠가 가장 큰 것을 찾으면 지수 모양이, 분산⁠(variance)⁠까지 정하면 정규분포⁠(normal distribution)⁠가 나오는 최대 엔트로피 원리⁠(principle of maximum entropy)⁠의 계산도 이것입니다. 둘레가 정해진 끈으로 가장 넓은 땅을 두르는 문제는 카르타고를 세운 디도 여왕의 전설로 전하고, 답이 원이라는 것은 뻔해 보이지만 빈틈없는 증명은 19세기 후반에야 나왔습니다.

오차를 가장 작게. 관측이 늘 조금씩 틀린다면, 여러 관측을 하나로 모으는 가장 좋은 방법은 무엇일까요? 르장드르(1805)와 가우스의 답은 잔차의 제곱합을 가장 작게 하는 것이었습니다(최소제곱 회귀⁠, least-squares regression⁠). 제곱합을 계수로 미분해 0으로 놓은 정규방정식⁠(normal equations)⁠은, 기하⁠(geometry)⁠로 읽으면 '잔차 벡터가 가능한 답들의 평면(열공간⁠(column space)⁠)과 직교한다'는 말입니다. 곧 가장 좋은 답은 정사영⁠(orthogonal projection)⁠이고, 그림의 '직선 맞추기'에서 잔차와 x 편차의 곱의 합이 0이 되는 곳이 바로 접선이 수평인 자리입니다. 기준을 바꾸면 답도 바뀝니다. 수직선 위의 점들까지 제곱 거리의 합을 줄이는 점은 평균이고, 거리의 합을 줄이는 점은 중앙값⁠(median)⁠입니다. 투영한 데이터의 퍼짐이 가장 큰 방향을 찾으면 주성분 분석⁠(principal component analysis)⁠의 고유벡터⁠(eigenvector)⁠가 나오고, 점과 중심 사이 거리 제곱합을 줄이면 k-평균 군집⁠(k-means clustering)⁠이 됩니다.

갈림길이 유한할 때. 지도 위의 가장 빠른 길은 기울기로 찾을 수 없습니다. 갈림길은 유한하지만 그 조합의 수가 폭발하기 때문입니다. 1956년 암스테르담의 데이크스트라는 가까운 곳부터 거리를 하나씩 확정해 나가는 방법으로 최단 경로를 찾았습니다. 여기서도 '조금 바꿔도 나아지지 않는다'가 열쇠입니다. 가장 짧은 길의 일부분은 그 두 점 사이의 가장 짧은 길이어야 합니다. 그렇지 않다면 그 부분만 바꿔 전체를 더 짧게 할 수 있으니까요. 이 원리가 동적 계획법⁠(dynamic programming)⁠의 뼈대입니다. 매 순간 가장 좋아 보이는 것을 고르는 욕심쟁이 알고리즘⁠(greedy algorithm)⁠은 최소 신장 트리⁠(minimum spanning tree)⁠와 허프만 부호⁠(Huffman coding)⁠에서는 정확하지만 많은 문제에서 틀립니다. 1939년 무렵 소련의 레오니트 칸토로비치는 합판 공장의 생산 계획을, 1947년 미국의 조지 댄치그는 군의 보급 계획을 일차 부등식들로 적고 그 안에서 가장 좋은 답을 찾는 선형 계획법⁠(linear programming)⁠을 내놓았습니다. 이를테면 '재료는 100kg 이하, 기계 시간은 40시간 이하'처럼 일차 부등식들이 모이면 허용되는 답들은 모서리가 곧은 볼록한 영역을 이루고, 이익이 일차식이면, 가장 좋은 답이 있고 영역에 꼭짓점⁠(vertex)⁠이 있는 한(모든 양이 0 이상이라는 조건이 있으면 늘 그렇습니다) 꼭짓점 가운데 하나에서도 반드시 그 값을 얻습니다. 댄치그의 단체법⁠(simplex method)⁠은 꼭짓점에서 이웃한 더 나은 꼭짓점으로 모서리를 따라 옮겨 가는 방법입니다. 댄치그의 설명을 들은 폰 노이만은 선형 계획의 최대화 문제마다 짝이 되는 최소화 문제가 있고, 한쪽에 가장 좋은 답이 있으면 두 답이 같다는 쌍대 정리⁠(duality theorem)⁠를 곧바로 짐작했다고 전합니다. 흐름을 최대로 하는 문제의 짝이 가장 좁은 절단⁠(cut)⁠을 찾는 문제라는 최대 흐름 최소 절단 정리⁠(max-flow min-cut theorem)⁠, 1781년 프랑스의 가스파르 몽주가 처음 묻고 칸토로비치가 선형 계획으로 다시 쓴, 흙을 옮기는 비용의 최솟값인 최적 수송⁠(optimal transport)⁠이 그 예입니다.

통로와 부호의 한계. 벨 연구소의 섀넌이 1948년에 정의한 통로 용량도 최댓값입니다. 입력의 분포를 바꿔 가며 입력과 출력의 상호 정보량⁠(mutual information)⁠을 가장 크게 만든 값이고, 그 값이 믿을 만하게 보낼 수 있는 속도의 한계라는 것이 통로 부호화 정리⁠(noisy-channel coding theorem)⁠입니다. 반대쪽 끝에는 최솟값이 있습니다. 한 기호를 적는 데 드는 평균 비트 수의 최솟값이 엔트로피라는 원천 부호화 정리⁠(source coding theorem)⁠, 조금 틀려도 될 때 필요한 비트 수의 최솟값을 정하는 율–왜곡 이론⁠(rate–distortion theory)⁠입니다. 수학이 '가장 좋은 것'을 정의하는 순간, 그보다 나은 것은 없다는 한계도 함께 얻습니다.

발밑만 보고 내려가기. 변수가 수백만 개면 그래디언트가 0인 곳을 식으로 풀 수 없습니다. 그래서 1847년 코시가 제안한 방법으로 돌아갑니다. 지금 자리의 기울기 반대쪽으로 조금 움직이고, 다시 기울기를 재는 경사 하강법⁠(gradient descent)⁠입니다. 오늘날의 신경망은 수십억 개의 가중치⁠(weight)⁠를 이렇게 고치며, 그 기울기는 역전파⁠(backpropagation)⁠로 구합니다. 곡률⁠(curvature)⁠까지 쓰는 뉴턴 방법⁠(Newton's method)⁠을 도함수의 0점 찾기에 쓰면 이차함수에서는 한 걸음에 바닥에 닿지만, 변수가 많으면 한 걸음이 너무 비쌉니다. 무엇이 가장 좋은지 아는 것과 그곳에 닿는 것은 다른 문제입니다.

가장 좋은 것이 말썽일 때. 기울기 0은 최적의 필요조건⁠(necessary condition)⁠일 뿐입니다. 골짜기가 여럿이면 발밑만 보는 방법은 가까운 골짜기에 멈추고, k-평균 군집이 시작점에 따라 다른 답을 내는 것도 그래서입니다. 함수⁠(function)⁠가 그릇처럼 어디서나 위로 휜 볼록 함수⁠(convex function)⁠라면 극소가 곧 최소라는 보장이 있고, 그래서 최적화 이론은 볼록성을 그토록 반깁니다. 갈림길이 유한한 문제는 원리적으로 모두 비교하면 되지만, 도시 여러 곳을 한 번씩 들르고 돌아오는 가장 짧은 순회로를 찾는 외판원 문제⁠(traveling salesman problem)⁠처럼 답을 확인하기는 쉬운데 찾기는 어려워 보이는 문제가 많고, 그 경계를 묻는 것이 P 대 NP 문제⁠(P versus NP problem)⁠입니다. 가장 좋은 것이 있기는 한지부터 문제일 수도 있습니다. 1850년대 리만은 복소함수론에서 어떤 적분⁠(integral)⁠을 가장 작게 하는 함수가 당연히 있다고 보고, 베를린에서 배운 스승 디리클레의 이름을 붙인 이 원리를 증명의 기둥으로 썼습니다. 1870년 카를 바이어슈트라스는 값이 최솟값에 한없이 다가가기만 할 뿐 어떤 함수에서도 닿지는 않는 예를 내놓아 그 기둥을 흔들었고, 이 원리를 조건을 붙여 되살린 것은 1900년 무렵 괴팅겐의 힐베르트였습니다. 마지막으로, 최적화는 우리가 정한 기준에만 충실합니다. 학습 데이터⁠(training set)⁠의 오차를 끝까지 줄인 모형이 새 데이터에서 크게 틀리는 과적합⁠(overfitting)⁠은 잘못 고른 목표를 너무 잘 최적화한 결과입니다.

이어지는 곳. 최적의 조건 '기울기 0'은 선형화⁠(linearization)⁠로 얻은 일차 근사⁠(first-order approximation)⁠가 평평하다는 말입니다. 최대화 문제와 최소화 문제가 짝을 이루는 선형 계획의 쌍대 정리는 쌍대성⁠(duality)⁠에서 더 이어집니다. 발밑의 기울기만으로 전체의 최솟값에 닿을 수 있는지는 국소에서 전체로의 질문이고, 매 걸음 데이터의 일부만 무작위로 골라 기울기를 어림하는 확률적 경사 하강법⁠(stochastic gradient descent)⁠처럼, 일부러 섞는 잡음이 계산을 싸게 하고 얕은 골짜기에서 빠져나오게 돕는 일은 무작위성의 쓰임입니다. 둘레가 같은 도형 가운데 원이 가장 넓은 것처럼 최적의 답이 문제의 대칭을 물려받는 모습은 대칭과 불변량⁠(invariant)⁠에서 다시 만납니다. 최소제곱과 정사영은 오차의 크기를 정한 뒤 그것을 가장 작게 하는 근사를 고르는 일이기도 합니다.