볼록 함수와 볼록 최적화(Convex function and convex optimization)

그릇 모양 곡선 $y = x^2$ 위의 두 점을 선분(현)으로 이어 보면, 현은 두 점 사이에서 늘 곡선보다 위에 있습니다. x = −1과 x = 2의 점을 이으면 가운데 x = 0.5에서 현의 높이는 $(1 + 4)/2 = 2.5$이고 곡선의 높이는 $0.25$입니다. 이처럼 어느 두 점을 이어도 현이 그래프 아래로 내려가지 않는 함수를 볼록 함수라 합니다. 식으로는, 정의역(구간처럼, 두 점을 담으면 그 사이의 선분도 담는 집합⁠(set)⁠)의 모든 x, y와 0 ≤ λ ≤ 1인 모든 λ에 대해

$$f\bigl(\lambda x + (1-\lambda) y\bigr) \le \lambda f(x) + (1-\lambda) f(y)$$

입니다. 왼쪽은 x와 y 사이의 한 점에서의 함숫값이고, 오른쪽은 그 점 위에 있는 현의 높이입니다. 우리 교과서의 '아래로 볼록'이 이 뜻의 볼록(convex)이고, '위로 볼록'인 함수는 오목(concave) 함수라 부릅니다. 이름이 헷갈리기 쉬우니 그릇(∪) 모양이 볼록이라고 기억하면 됩니다. 함수: . 두 점 a, b를 끌고 λ = 를 바꿔 보세요.

λ가 가리키는 점에서 현의 높이는 , 곡선의 높이는 , 둘의 차는 입니다. x², |x|, eˣ는 두 점을 어디에 두어도 빨강이 나오지 않습니다. '물결'에서는 가운데의 오목한 부분을 걸치도록 두 점을 고르면 빨강이 나타나고, 접선⁠(tangent line)⁠이 그래프를 뚫고 올라가기도 합니다.

알아보는 법. 모든 현을 확인할 필요는 없습니다. 열린 구간에서 두 번 미분할 수 있는 함수라면, 그 구간의 모든 x에서 $f''(x) \ge 0$인 것과 볼록인 것이 같습니다. $f'' \ge 0$이면 기울기 f′이 줄지 않으니, 곡선이 한쪽(위쪽)으로만 휘기 때문입니다. 변수가 여럿이면 헤세 행렬⁠(Hessian matrix)⁠의 고유값⁠(eigenvalue)⁠이 어디서나 0 이상인 것이 같은 조건입니다. |x|처럼 뾰족한 점이 있어도 볼록일 수 있으니, 미분 가능성은 볼록의 조건이 아닙니다. 볼록 함수끼리 더하거나 양수를 곱하거나 여러 볼록 함수⁠(convex function)⁠ 가운데 가장 큰 값을 취해도 볼록입니다. 벡터⁠(vector)⁠의 길이를 재는 노름⁠(norm)⁠은 삼각부등식⁠(triangle inequality)⁠과 $\|\lambda x\| = |\lambda|\,\|x\|$ 때문에 늘 볼록이고(Lp 노름⁠, Lp norm⁠), 일차함수는 볼록이면서 오목입니다.

극소가 곧 최소. 볼록이 중요한 까닭은 이것입니다. x가 주변보다 낮은 점(극소)인데 어딘가에 더 낮은 점 y가 있다고 해 봅시다. 볼록성에 따라 x와 y 사이의 그래프는 현 아래에 있고, 현은 f(x)에서 출발해 더 낮은 f(y)로 내려가니, x에 얼마든지 가까운 곳에 f(x)보다 낮은 점이 생깁니다. x가 극소라는 가정과 맞지 않으므로, 볼록 함수의 극소는 모두 최소입니다. 미분 가능하다면 더 간단합니다. 접선(변수가 여럿이면 접평면⁠(tangent plane)⁠)이 그래프 전체의 아래에 있어서 $f(y) \ge f(x) + \nabla f(x)\cdot(y - x)$이고, 그림의 노란 점선이 그것입니다. 그러니 $\nabla f(x) = 0$이면 모든 y에서 $f(y) \ge f(x)$입니다. 경사 하강법⁠(gradient descent)⁠ 문서의 '두 개의 골짜기'에서처럼 얕은 골짜기에 갇히는 일은 볼록 함수에서는 생기지 않습니다.

흔한 오해가 둘 있습니다. 첫째, 볼록이라고 최솟값이 있는 것은 아닙니다. eˣ는 볼록이지만 0에 한없이 다가갈 뿐 가장 낮은 점이 없습니다. 둘째, 최소점이 하나라는 보장도 없습니다. −1과 1 사이에서는 0이고 그 밖에서는 $|x| - 1$인 함수는 볼록이지만 바닥이 평평해서 최소점이 무수히 많습니다. 현이 양 끝을 뺀 곳에서 그래프보다 엄밀히 위에 있는 순볼록⁠(strictly convex)⁠ 함수라면, 최소점이 있을 때 하나뿐입니다(순볼록은 충분조건⁠(sufficient condition)⁠일 뿐이어서, |x|처럼 순볼록이 아니어도 최소점이 하나인 함수가 있습니다). 그래도 볼록 함수에서는 두 최소점을 잇는 선분 위의 점도 모두 최소점입니다. 곧 최소점들의 집합은 볼록 집합입니다.

경사 하강법이 얼마나 빨리 가는지도 말할 수 있습니다. 볼록이고 헤세 행렬의 고유값이 어디서나 L 이하인 함수에서 학습률⁠(learning rate)⁠ η = 1/L로 k걸음 가면 $f(x_k) - f^* \le L\,|x_0 - x^*|^2/(2k)$입니다($f^*$는 최솟값, $x^*$는 최소점). 고유값이 어디서나 μ > 0 이상이기까지 하면(강볼록⁠, strongly convex⁠), 남은 오차 $f(x_k) - f^*$가 걸음마다 적어도 $1 - \mu/L$배로 줄어 등비수열⁠(geometric progression)⁠처럼 빨리 작아집니다. $L/\mu$가 바로 조건수⁠(condition number)⁠이고, 이 수가 크면 느립니다.

옌센 부등식⁠(Jensen's inequality)⁠. 현의 조건을 점 여러 개로 늘린 것이 1906년 덴마크의 요한 옌센이 발표한 부등식입니다. 확률변수⁠(random variable)⁠ X가 값 $x_i$를 확률⁠(probability)⁠ $p_i$로 가지면, 볼록 함수 f에 대해

$$f\bigl(\mathbb E[X]\bigr) \le \mathbb E\bigl[f(X)\bigr]$$

입니다. 그래프 위의 점들을 무게 $p_i$로 평균⁠(mean)⁠한 무게중심 $(\mathbb E[X], \mathbb E[f(X)])$는 그 점들을 꼭짓점⁠(vertex)⁠으로 하는 다각형 안에 있고, 볼록 함수의 그래프 위 점들로 만든 다각형은 통째로 그래프 위쪽에 있기 때문입니다. 세 점을 끌고 무게 , , 를 바꿔 보세요(합이 1이 되도록 나눠 씁니다). 함수:

지금 확률은 , $\mathbb E[f(X)] =$ , $f(\mathbb E[X]) =$ , 차는 입니다. f = x²이면 이 차가 바로 분산⁠(variance)⁠입니다($\mathbb E[X^2] - (\mathbb E[X])^2 = \operatorname{Var} X \ge 0$). f = −log x를 고르면 $\mathbb E[-\log X] \ge -\log \mathbb E[X]$입니다. X 자리에 $q(x)/p(x)$를 넣고 분포 p로 기댓값⁠(expected value)⁠을 취하면, 오른쪽의 $\mathbb E_p[q/p]$는 p(x) > 0인 x에 대한 q(x)의 합이라 1 이하이므로 오른쪽 전체는 0 이상이 되고, 왼쪽은 $\sum p\log(p/q)$, 곧 쿨백–라이블러 발산⁠(Kullback–Leibler divergence)⁠입니다. KL 발산⁠(KL divergence)⁠이 음수가 될 수 없다는 깁스 부등식⁠(Gibbs' inequality)⁠이 이렇게 한 줄로 나옵니다. 로그가 오목하다는 데서 나오는 산술평균 ≥ 기하평균, 그리고 값이 n가지인 분포 가운데 엔트로피⁠(entropy)⁠가 균등 분포에서 가장 크다는 사실도 같은 부등식의 경우들입니다.

볼록 최적화. 볼록 함수를 볼록 집합(안의 두 점을 잇는 선분이 늘 안에 있는 집합) 위에서 최소로 만드는 문제를 볼록 최적화 문제라 합니다. 선형 계획법(일차식 목표, 일차 부등식으로 잘라 낸 볼록 다면체), 최소제곱법⁠(method of least squares)⁠, 로지스틱 회귀⁠(logistic regression)⁠의 손실, 계수의 절댓값⁠(absolute value)⁠ 합에 벌점을 매기는 라소⁠(lasso)⁠ 같은 정규화, 서포트 벡터 머신⁠(support vector machine)⁠이 모두 여기에 듭니다. 국소 최적이 곧 전역 최적이라 답을 믿을 수 있고, 1980–90년대에 발전한 내부점 방법⁠(interior-point method)⁠ 같은 알고리즘⁠(algorithm)⁠이 흔히 쓰이는 종류의 볼록 문제를 원하는 정밀도⁠(precision)⁠까지 다항식 시간⁠(polynomial time)⁠에 풉니다. 다만 볼록이라고 모두 쉬운 것은 아니어서, 집합이 까다롭게 주어진 볼록 문제 가운데에는 어려운 것도 있습니다. 제약이 있는 볼록 문제에서는 라그랑주 승수⁠(Lagrange multiplier)⁠로 만든 쌍대 문제⁠(dual problem)⁠가 원래 문제와 같은 값을 줍니다(쌍대성⁠(duality)⁠). 여기에는 가벼운 가정이 필요한데, 흔히 쓰는 것은 부등식 제약을 모두 엄격하게(등호 없이) 만족하는 점이 있다는 슬레이터 조건입니다.

신경망⁠(neural network)⁠의 손실은 볼록이 아닙니다. 신경망에서 숨은 단위 두 개의 가중치⁠(weight)⁠를 통째로 맞바꾸면 같은 함수를 계산하니 손실도 같습니다. 손실이 볼록이라면 최소점들이 볼록 집합⁠(convex set)⁠을 이루므로, 어떤 최소점과 그것을 맞바꾼 것의 중간도 최소점이어야 합니다. 그런데 중간에서는 두 단위의 가중치가 똑같아집니다. 두 단위가 늘 같은 값을 내니, 출력 가중치를 합친 단위 하나로 바꿔 써도 같은 함수입니다. 단위를 하나 덜 가진 신경망이 된 셈이라 대개 손실이 더 큽니다. 그런데도 경사 하강법과 확률적 경사 하강법⁠(stochastic gradient descent)⁠이 큰 신경망에서 잘 듣는 까닭은 아직 완전히 이해되지 않았고, 활발히 연구되고 있습니다.

이어지는 곳. 볼록성은 가장 좋은 것 고르기가 믿을 만해지는 조건입니다. 엔트로피는 순오목하고 '확률의 합이 1, 평균이 정해짐' 같은 제약은 볼록 집합을 이루므로, 최대 엔트로피 원리⁠(principle of maximum entropy)⁠의 답은 있다면 하나뿐입니다. 흙을 옮기는 비용을 최소로 하는 최적 수송⁠(optimal transport)⁠은 칸토로비치의 선형 계획⁠(linear programming)⁠으로 쓰면 볼록 문제가 됩니다. 기울기 벡터⁠(gradient vector)⁠와 헤세 행렬의 뜻은 기울기 벡터와 야코비 행렬⁠(Jacobian matrix)⁠에, 이계도함수로 극소와 극대를 가리는 일은 최적화에 있습니다.