컨벡스 최적화
우리는 전역 최적성(global optimality)을 보장할 수 있는 특히 유용한 최적화 문제의 범주에 주의를 집중한다. $f(\cdot)$ 가 볼록 함수(convex function)이고, $g(\cdot)$ 와 $h(\cdot)$ 를 포함하는 제약 조건들이 볼록 집합(convex sets)일 때, 이를 볼록 최적화 문제(convex optimization problem)라고 부른다. 이 설정에서 우리는 강한 쌍대성(strong duality)을 가진다. 즉, 쌍대 문제의 최적해는 원초 문제의 최적해와 동일하다. 기계 학습 문헌에서는 볼록 함수와 볼록 집합 사이의 구분이 종종 엄밀하게 제시되지 않지만, 문맥으로부터 내포된 의미를 자주 추론할 수 있다.
정의 7.2. 임의의 $\boldsymbol{x}, \boldsymbol{y} \in \mathcal{C}$ 와 $0 \leqslant \theta \leqslant 1$ 인 임의의 스칼라 $\theta$ 에 대하여 다음을 만족할 때, 집합 $\mathcal{C}$ 를 볼록 집합(convex set)이라고 한다.
$\quad$ 볼록 집합은 집합의 임의의 두 원소를 연결하는 직선이 집합 내부에 놓이는 집합이다. 그림 7.5와 7.6은 각각 볼록 집합과 비볼록 집합을 설명한다.
$\quad$ 볼록 함수는 함수의 임의의 두 점을 연결하는 직선이 함수 위쪽에 놓이는 함수이다. 그림 7.2는 비볼록 함수를 보여주고, 그림 7.3은 볼록 함수를 보여준다. 또 다른 볼록 함수가 아래 그림 7.7에 나타나 있다.
정의 7.3. 정의역이 볼록 집합인 함수 $f : \mathbb{R}^D \rightarrow \mathbb{R}$ 를 고려하자. 함수 $f$ 의 정의역에 있는 모든 $\boldsymbol{x}, \boldsymbol{y}$ 와 $0 \leqslant \theta \leqslant 1$ 인 임의의 스칼라 $\theta$ 에 대하여 다음을 만족할 때, 함수 $f$ 는 볼록 함수(convex function)이다.
주의 (Remark). 오목 함수(concave function)는 볼록 함수의 음수이다.
$\to$ 부등식 (7.30)의 좌변은 정의역에서의 볼록 결합이고, 우변은 치역에서의 볼록 결합이다.
$\quad$ (7.28)에서 $g(\cdot)$ 와 $h(\cdot)$ 를 포함하는 제약 조건들은 스칼라 값에서 함수를 잘라내어(truncate), 결과적으로 집합을 생성한다. 볼록 함수와 볼록 집합 사이의 또 다른 관계는 볼록 함수를 “채워 넣어서(filling in)” 얻은 집합을 고려하는 것이다. 볼록 함수는 그릇 모양의 물체이며, 우리는 그것을 채우기 위해 물을 붓는 것을 상상한다. 이렇게 채워진 결과 집합을 볼록 함수의 에피그래프(epigraph)라고 부르며, 이는 볼록 집합이다.
$\quad$ 만약 함수 $f : \mathbb{R}^n \rightarrow \mathbb{R}$ 가 미분 가능하다면, 우리는 볼록성을 그것의 기울기(gradient) $\nabla_{\boldsymbol{x}} f(\boldsymbol{x})$ 의 관점에서 명시할 수 있다 ([5.2절]). 임의의 두 점 $\boldsymbol{x}, \boldsymbol{y}$ 에 대하여 다음이 성립할 때, 그리고 오직 그때만(if and only if) 함수 $f(\boldsymbol{x})$ 는 볼록 함수이다.
만약 함수 $f(\boldsymbol{x})$ 가 두 번 미분 가능함을 추가로 안다면, 즉 $\boldsymbol{x}$ 의 정의역에 있는 모든 값에 대해 헤시안(Hessian) 행렬이 존재한다면, 함수 $f(\boldsymbol{x})$ 는 $\nabla_{\boldsymbol{x}}^2 f(\boldsymbol{x})$ 가 양의 준정부호(positive semidefinite)일 때, 그리고 오직 그때만 볼록 함수이다 (Boyd and Vandenberghe, 2004).
$\to$ 식 (7.31)은 함수 f의 1차 테일러 근사는 볼록 함수의 하한임을 말해준다.?
$\to$ 부등식 (7.31)을 변형하면 다음과 같다.
이는 실제 높이 변화량이 접선 상의 예측 높이 변화량(곡률을 고려하지 않은)보다 크거나 같음을 뜻한다.
간단한 볼록 함수의 예시로 일변수 2차 함수 $f(x) = x^2$ 로 식 (7.31)을 증명해볼 수 있다. 임의의 좌표 $x = 1$ , $y = 3$ 에 대해 시작점에서의 높이: $f(1) = 1$ , ,시작점에서의 기울기: $f’(1) = 2$ , 변위: $(3 - 1) = 2$ 이며, 이를 (7.31)에 대입하면 다음과 같다.
이는 특정 점에 국한되는게 아닌, 모든 점에 대해 성립한다.
우변을 모두 좌변으로 이항하면
임의의 두 실수 $y, x$ 에 대해 두 실수의 차이 역시 실수이며, 그의 제곱은 항상 0보다 크기 때문에 7.31이 모든 정의역에서 참이 된다.
예제 7.3
음의 엔트로피(negative entropy) $f(x) = x \log_2 x$ 는 $x > 0$ 에 대해 볼록하다. 이 함수의 시각화는 그림 7.8에 나타나 있으며, 우리는 이 함수가 볼록함을 볼 수 있다. 앞서 다룬 볼록성의 정의들을 설명하기 위해 두 점 $x = 2$ 와 $x = 4$ 에 대한 계산을 확인해 보자. $f(x)$ 의 볼록성을 증명하기 위해서는 모든 점 $x \in \mathbb{R}$ 에 대해 확인해야 함에 유의하라.
$\quad$ 정의 7.3을 상기하라. 두 점의 중간에 있는 점( $\theta = 0.5$ )을 고려하면, 좌변은 $f(0.5 \cdot 2 + 0.5 \cdot 4) = 3 \log_2 3 \approx 4.75$ 이다. 우변은 $0.5(2 \log_2 2) + 0.5(4 \log_2 4) = 1 + 4 = 5$ 이다. 따라서 정의가 만족된다.
$\quad$ $f(x)$ 가 미분 가능하므로, 우리는 대안적으로 (7.31)을 사용할 수 있다. $f(x)$ 의 도함수를 계산하면 다음을 얻는다.
동일한 두 테스트 점 $x = 2$ 와 $x = 4$ 를 사용하면, (7.31)의 좌변은 $f(4) = 8$ 로 주어진다. 우변은 다음과 같다.
$\quad$ 우리는 정의를 상기함으로써 함수나 집합이 볼록한지 제1원리(first principles)로부터 확인할 수 있다. 실제로는, 특정 함수나 집합이 볼록한지 확인하기 위해 볼록성(convexity)을 보존하는 연산들에 종종 의존한다. 세부 사항은 크게 다르지만, 이는 우리가 2장에서 벡터 공간에 대해 소개했던 닫힘(closure)의 개념과 다시 한번 동일하다.
$\to$ 위 정의 7.2, 7.3를 통해 함수가 집합이 볼록한지 증명하는 과정은 함수의 복잡해짐에 따라 다루기 힘들다. 때문에 함수 전체를 정의식에 대입하는 대신, 함수를 분해하여 덧셈, 스칼라배를 통해 볼록성을 유지하는지 확인할 수 있다.
예제 7.4
볼록 함수들의 음이 아닌 가중합(nonnegative weighted sum)은 볼록하다. $f$ 가 볼록 함수이고 $\alpha \geqslant 0$ 이 음이 아닌 스칼라라면, 함수 $\alpha f$ 는 볼록함을 관찰하라. 우리는 정의 7.3의 방정식 양변에 $\alpha$ 를 곱하고, 음이 아닌 수를 곱해도 부등호가 변하지 않음을 상기함으로써 이를 확인할 수 있다.
$\quad$ 만약 $f_1$ 과 $f_2$ 가 볼록 함수라면, 우리는 정의에 의해 다음을 얻는다.
양변을 더하면 다음이 주어진다.
여기서 우변은 다음과 같이 재배열될 수 있으며,
볼록 함수들의 합이 볼록하다는 증명을 완성한다.
$\quad$ 앞선 두 가지 사실을 결합하면, 우리는 $\alpha, \beta \geqslant 0$ 에 대해 $\alpha f_1(\boldsymbol{x}) + \beta f_2(\boldsymbol{x})$ 가 볼록함을 알 수 있다. 이 닫힘 성질(closure property)은 유사한 논증을 사용하여 두 개 이상의 볼록 함수들의 음이 아닌 가중합으로 확장될 수 있다.
주의. (7.30)의 부등식은 때때로 젠슨의 부등식(Jensen’s inequality)이라고 불린다. 사실, 볼록 함수들의 음이 아닌 가중합을 취하는 부등식들의 전체 클래스가 모두 젠슨의 부등식이라고 불린다.
$\to$ 곡률의 관점에서 볼록 함수들의 합이 $F(x) = f_1(x) + f_2(x)$ 라고 할 때, 이 함수의 곡률은 $F’‘(x) = f_1’‘(x) + f_2’‘(x)$ 이다. 볼록 함수의 정의상 $f_1’‘(x) \geqslant 0$ 이고 $f_2’‘(x) \geqslant 0$ 이므로 $F’‘(x)$ 또한 0보다 크거나 같기 때문에 결과 함수 또한 볼록 함수이다.
$\quad$ 요약하자면, 제약 조건이 있는 최적화 문제는 다음과 같은 경우에 볼록 최적화 문제라고 불린다.
여기서 모든 함수 $f(\boldsymbol{x})$ 와 $g_i(\boldsymbol{x})$ 는 볼록 함수이고, 모든 $h_j(\boldsymbol{x}) = 0$ 은 볼록 집합이다. 다음에서는 널리 사용되고 잘 이해되고 있는 두 가지 클래스의 볼록 최적화 문제에 대해 설명할 것이다.
7.3.1 Linear Programming
선형계획법
앞선 모든 함수가 선형인 특별한 경우를 고려하자. 즉,
$\to$ 여기서 변수에 대한 비음 조건 ( $\boldsymbol{x} \geqslant \boldsymbol{0}$ )이 명시되지 않은 것은, 파라미터의 범위를 전 구간으로 확장하는 경우를 생각했을 수 있고(1), 비음 조건( $=-\boldsymbol{x} \leqslant \boldsymbol{0}$ )이 제약 조건에 이미 포함되있을 수도 있다(2).
여기서 $\boldsymbol{A} \in \mathbb{R}^{m \times d}$ 이고 $\boldsymbol{b} \in \mathbb{R}^m$ 이다. 이것은 선형 계획 문제(linear program)로 알려져 있다. 이는 $d$ 개의 변수와 $m$ 개의 선형 제약 조건을 가진다. 라그랑지안은 다음과 같이 주어진다.
여기서 $\boldsymbol{\lambda} \in \mathbb{R}^m$ 는 음수가 아닌 라그랑주 승수 벡터이다. $\boldsymbol{x}$ 에 해당하는 항들을 재배열하면 다음이 산출된다.
$\boldsymbol{x}$ 에 대해 $\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})$ 의 미분을 취하고 이를 0으로 설정하면 다음을 얻는다.
따라서 쌍대 라그랑지안은 $\mathfrak{D}(\boldsymbol{\lambda}) = -\boldsymbol{\lambda}^\top \boldsymbol{b}$ 이다. 우리는 $\mathfrak{D}(\boldsymbol{\lambda})$ 를 최대화하고자 함을 상기하라. $\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})$ 의 미분이 0이 되는 것에 의한 제약 조건 외에도, $\boldsymbol{\lambda} \geqslant \boldsymbol{0}$ 이라는 사실이 있으며, 결과적으로 다음의 쌍대 최적화 문제가 도출된다.
이 또한 선형 계획 문제이지만, $m$ 개의 변수를 가진다. 우리는 원초 문제의 선형 계획 문제에서 변수의 수인 $d$ 와 제약 조건의 수인 $m$ 중 어느 것이 더 큰지에 따라 원초 프로그램 (7.39) 또는 쌍대 프로그램 (7.43)을 푸는 것을 선택할 수 있다.
선형 계획 문제는 산업계에서 가장 널리 사용되는 접근 방식 중 하나이다. 원초 문제를 최소화하고 쌍대 문제를 최대화하는 것이 관례이다.
예제 7.5 (선형 계획 문제)
두 개의 변수를 가진 다음의 선형 계획 문제를 고려하자.
이 프로그램은 그림 7.9에도 나와 있다. 목적 함수가 선형이므로 등고선(contour lines)도 선형이 된다. 표준 형태의 제약 조건 집합이 그래프의 범례(legend)로 변환되어 있다. 최적값은 반드시 음영 처리된 (실행 가능한) 영역 안에 있어야 하며, 별표로 표시되어 있다.
(그림 7.9: 선형 계획 문제의 일러스트레이션. 제약이 없는 문제(등고선으로 표시됨)는 오른쪽에서 최솟값을 갖는다. 제약 조건이 주어졌을 때의 최적값은 별표로 표시된다.)
7.3.2 Quadratic Programming
이차 계획법
제약 조건이 아핀(affine)이고 목적 함수가 볼록 이차 함수인 경우를 고려하자. 즉,
여기서 $\boldsymbol{A} \in \mathbb{R}^{m \times d}$ , $\boldsymbol{b} \in \mathbb{R}^m$ , 그리고 $\boldsymbol{c} \in \mathbb{R}^d$ 이다. 정방 대칭 행렬(square symmetric matrix) $\boldsymbol{Q} \in \mathbb{R}^{d \times d}$ 는 양의 정부호(positive definite)이며, 따라서 목적 함수는 볼록하다. 이를 이차 계획 문제(quadratic program)라고 부른다. 이는 $d$ 개의 변수와 $m$ 개의 선형 제약 조건을 가짐을 관찰하라.
예제 7.6 (이차 계획 문제)
두 개의 변수를 가진 다음의 이차 계획 문제를 고려하자.
이 프로그램은 그림 7.4에도 예시되어 있다. 목적 함수는 양의 준정부호(positive semidefinite) 행렬 $\boldsymbol{Q}$ 를 가진 이차 함수이며, 결과적으로 타원형의 등고선(elliptical contour lines)을 생성한다. 최적값은 반드시 음영 처리된 (실행 가능한) 영역 안에 있어야 하며, 별표로 표시되어 있다.
$\quad$ 라그랑지안은 다음과 같이 주어진다.
여기서 다시 항들을 재배열하였다. $\boldsymbol{x}$ 에 대해 $\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})$ 의 미분을 취하고 이를 0으로 설정하면 다음을 얻는다.
$\boldsymbol{Q}$ 가 양의 정부호이고 따라서 역행렬이 존재하므로(invertible), 우리는 다음을 얻는다.
(7.50)을 원초 라그랑지안 $\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})$ 에 대입하면, 쌍대 라그랑지안을 얻는다.
따라서 쌍대 최적화 문제는 다음과 같이 주어진다.
우리는 12장에서 기계 학습(machine learning)에 이차 계획법이 응용되는 것을 보게 될 것이다.
식 7.45, 7.46을 보면 이차 형식 앞에 $\frac{1}{2}$ 을 곱하여 미분 상수를 상쇄하였는데, 이에 대해 따로 글을 적어보았다.
7.3.3 Legendre-Fenchel Transform and Convex Conjugate
르장드르-펜철 변환과 볼록 켤레
제약 조건을 고려하지 않고, 섹션 7.2의 쌍대성(duality) 개념을 다시 살펴보자. 볼록 집합에 관한 한 가지 유용한 사실은, 그것이 받침 초평면(supporting hyperplanes)들에 의해 동등하게 설명될 수 있다는 것이다. 초평면이 볼록 집합과 교차하고, 그 볼록 집합이 초평면의 오직 한쪽에만 포함되어 있을 때, 이를 볼록 집합의 받침 초평면이라고 부른다. 우리는 볼록 함수를 채워 넣어 에피그래프(epigraph, 함수 곡선 위쪽의 집합)를 얻을 수 있으며, 이는 볼록 집합임을 상기하라. 따라서 우리는 볼록 함수 역시 그것의 받침 초평면들을 관점에서 설명할 수 있다. 나아가, 받침 초평면은 볼록 함수에 ‘살짝 닿아(just touches)’ 있으며, 사실상 그 지점에서의 함수에 대한 접선(tangent)임을 관찰하라. 그리고 주어진 점 $\boldsymbol{x}_0$ 에서 함수 $f(\boldsymbol{x})$ 의 접선은, 그 점에서의 함수의 그래디언트를 평가한 값 $\left. \frac{df(\boldsymbol{x})}{d\boldsymbol{x}} \right\vert _{\boldsymbol{x}=\boldsymbol{x}_0}$ 임을 상기하라.
$\to$ 함수가 뾰족한 V자 모양(예: $y = \vert x\vert$ )인 경우, 원점( $x=0$ )에서는 미분이 불가능하여 유일한 ‘접선’이 존재하지 않는다. 그러나 원점을 지나며 V자 아래를 떠받치는 직선은 무수히 많이 그을 수 있다(기울기가 -1과 1사이인 모든 직선). 즉, 엄밀히 말하면 미분 불가능한 점에서는 접선이 아니라 subgradient가 된다.
“볼록집합이 받침 초평면들에 의해 동등하게 설명될 수 있다”는 것은 무슨 의미인가?
기존에 우리는 함수를 점들의 집합으로 보았지만, 르장드르 변환은 어떤 함수를 초평면(그래디언트)들로 설명하였다.
$\to$ “초평면이 볼록 집합과 교차하고, 그 볼록 집합이 초평면의 오직 한쪽에만 포함되어 있다”는 것은 무슨 뜻인가?
함수 $x^2$ 의 에피그래프(마치 곡선 안쪽에 물을 가득 담은 형상)를 생각해보자. 이때 이 함수의 받침 초평면은 모두 에피그래프를 교차하지 않고, 한 점에 맞닿아있으므로, 에피그래프가 받침 초평면의 한쪽에만 포함된다.
초평면(hyperplane)이란 3차원 공간 속의 평면을 일반한 개념인데, 유한 차원 유클리드 공간에서, 여차원이 1인 초평면은 항상 두 개의 반공간으로 공간을 나눈다).
요약하자면, 볼록 집합이 받침 초평면들에 의해 동등하게 설명될 수 있기 때문에, 볼록 함수 역시 그것의 그래디언트(기울기)의 함수로 동등하게 설명될 수 있다. 르장드르 변환(Legendre transform)은 이 개념을 공식화한다.
$\quad$ 우리는 불행히도 직관에 반하는 형태를 가진 가장 일반적인 정의부터 시작하여, 앞 단락에서 설명한 직관과 정의를 연관 짓기 위해 특수한 경우들을 살펴볼 것이다. 르장드르-펜첼 변환은 (푸리에 변환의 의미에서) 미분 가능한 볼록 함수 $f(\boldsymbol{x})$ 를 접선 $\boldsymbol{s}(\boldsymbol{x}) = \nabla_{\boldsymbol{x}} f(\boldsymbol{x})$ 에 의존하는 함수로 바꾸는 변환(transformation)이다. 이것은 함수 $f(\cdot)$ 의 변환이지, 변수 $\boldsymbol{x}$ 나 $\boldsymbol{x}$ 에서 평가된 함수의 변환이 아님을 강조할 가치가 있다. 르장드르-펜첼 변환은 볼록 켤레(convex conjugate)로도 알려져 있으며 (그 이유는 곧 보게 될 것이다), 쌍대성과 밀접한 관련이 있다.
물리학과 학생들은 종종 고전 역학에서 라그랑지안과 해밀토니안을 연관 짓는 것으로 르장드르 변환을 소개받는다.
$\to$ 푸리에 변환은 시간이나 공간에 대한 함수를 주파수 성분으로 분해하는 변환을 말한다. 르장드르 변환도 비슷한 맥락으로 위치 좌표( $x, f(x)$ )에 대한 함수를 접선의 기울기들로 분해한다.
$\to$ 고전 역학에서 라그랑지안은 계의 운동에너지( $T$ )에서 위치에너지( $V$ )를 뺀 값( $L(q, \dot{q})=T-V$ )으로 정의된다( $q$ 는 물체의 위치, $\dot{q}$ 는 위치를 시간으로 미분한 속도). 즉, 물체의 상태를 ‘현재 위치’와 속도를 기준으로 서술하는 체계이다. 이 체계는 물체가 출발지에서 도착지까지 어떤 궤적을 그리며 이동하는지, 그 전체적인 경로를 추적하고 예측하는 데 초점을 둔다.
해밀토니안은 속도( $\dot{q}$ ) 대신 운동량( $p$ )으로 물체가 가진 총 에너지의 상태( $H(q, p) = T + V$ )를 분석한다. 이 체계는 양자역학이나 통계역학으로 이론을 확장할 때 구조가 잘 맞아떨어진다고 한다.
물리학에서 운동량 $p$ 는 라그랑지안( $L$ )을 속도 $\dot{q}$ 에 대해 편미분한 값으로 정의된다.
이는 함수의 기울기 $\boldsymbol{s}$ 를 구하는 것과 같다.
라그랑지안( $L$ )을 르장드르 변환하여 도출된 해밀토니안( $H$ )과 정의 7.4의 식 (7.53)은 같은 구조를 가진다.
일상적인 거시 세계에서는 물체의 속도를 측정하여 궤적을 추적하는 것은 직관적이며 정확하다. 하지만 입자의 위치와 속도를 동시에 특정할 수 없는 양자역학이나, 수많은 입자가 무작위로 움직이는 열역학에서는 속도라는 개념이 직관적이지 않다. 때문에 물체의 속도를 운동량으로 변환하여 보다 복잡한 공간으로 확장이 가능하다.
정의 7.4. 함수 $f: \mathbb{R}^D \rightarrow \mathbb{R}$ 의 볼록 켤레 $f^*$ 는 다음과 같이 정의된 함수이다.
$\quad$ 위의 볼록 켤레 정의는 함수 $f$ 가 볼록하거나 미분 가능할 필요가 없음에 유의하라. 정의 7.4에서 우리는 일반적인 내적(inner product)을 사용했지만, 너무 많은 기술적 세부 사항을 피하기 위해 이 섹션의 나머지 부분에서는 유한 차원 벡터들 사이의 표준 점곱(dot product, $\langle \boldsymbol{s}, \boldsymbol{x} \rangle = \boldsymbol{s}^\top \boldsymbol{x}$ )을 고려할 것이다.
$\quad$ 정의 7.4를 기하학적인 방식으로 이해하기 위해, 예를 들어 $f(x) = x^2$ 과 같은 나이스하고 단순한 1차원 미분 가능 볼록 함수를 고려해 보자. 우리가 1차원 문제를 다루고 있으므로, 초평면은 선(line)으로 축소됨에 유의하라. 선 $y = sx + c$ 를 고려하자. 우리가 볼록 함수를 그것의 받침 초평면들로 설명할 수 있음을 상기하고, 이 함수 $f(x)$ 를 받침선(supporting lines)들로 설명해 보도록 하자. 선의 그래디언트 $s \in \mathbb{R}$ 를 고정하고, $f$ 의 그래프 위 각 점 $(x_0, f(x_0))$ 에 대하여, 선이 여전히 $(x_0, f(x_0))$ 와 교차하도록 하는 $c$ 의 최솟값을 찾자. $c$ 의 최솟값은 기울기가 $s$ 인 선이 함수 $f(x) = x^2$ 에 “살짝 닿는(just touches)” 위치임에 유의하라. 그래디언트가 $s$ 이고 $(x_0, f(x_0))$ 를 지나는 선은 다음과 같이 주어진다.
이 선의 $y$ 절편은 $-sx_0 + f(x_0)$ 이다. 따라서 $y = sx + c$ 가 $f$ 의 그래프와 교차하게 만드는 $c$ 의 최솟값은 다음과 같다.
이 유도는 추론 과정을 그려가면서 이해하는 것이 가장 쉽다.
$\to$ 기울기( $m$ )와 한 점( $x_0, y_0$ )이 주어진 경우, 직선의 방정식은 다음과 같다.
이는 식 (7.54)과 같으며, 표준형으로 바꾸면 다음과 같다.
이때 y절편( $c$ )는 $c := -sx_0 + f(x_0)$ 이다.
식(7.55)에서 절편 $c$ 를 최소화한다고 했는데, 정의 7.4에서 볼록 켤례의 상한을 구하는 것과 어떻게 연결될까?
우리가 최대화 문제의 목적함수에 음수를 취하여 최소화 문제로 변환하듯이, $\inf(-A) = -\sup(A)$ 가 성립한다.
이는 켤레 함수 $f^*(s)$ 의 음수를 취한 것은, y절편 $c$ 를 최소화 하는것과 같다.
이는 식 (7.57)과 같다.
앞선 볼록 켤레(convex conjugate)는 관례상 이것의 음수(negative)로 정의된다. 이 단락에서의 추론은 우리가 1차원 미분 가능 볼록 함수를 선택했다는 사실에 의존하지 않았으며, 비볼록(nonconvex)이거나 미분 불가능한 $f: \mathbb{R}^D \rightarrow \mathbb{R}$ 에 대해서도 성립한다.
고전적인 르장드르 변환은 $\mathbb{R}^D$ 의 볼록 미분 가능 함수에 대해 정의된다.
주의(Remark). 예제 $f(x) = x^2$ 과 같은 미분 가능한 볼록 함수는 상한(supremum)이 필요 없는 나이스한 특수 사례이며, 함수와 그 르장드르 변환 사이에 일대일 대응(one-to-one correspondence)이 존재한다. 제1원리로부터 이를 도출해 보자. 미분 가능한 볼록 함수에 대해, 우리는 $x_0$ 에서의 접선이 $f(x_0)$ 에 닿는다는 것을 알고 있으므로 다음이 성립한다.
우리가 볼록 함수 $f(x)$ 를 그것의 그래디언트 $\nabla_x f(x)$ 의 관점에서 설명하고 싶어 한다는 점과, $s = \nabla_x f(x_0)$ 임을 상기하라. $-c$ 에 대한 식을 얻기 위해 항을 재배열하면 다음을 얻는다.
$-c$ 는 $x_0$ 에 따라 변하고 따라서 $s$ 에 따라 변한다는 점에 유의하라. 이것이 우리가 그것을 $s$ 의 함수로 생각할 수 있는 이유이며, 이를 다음과 같이 부른다.
(7.58)을 정의 7.4와 비교해 보면, (7.58)이 (상한이 없는) 특수한 경우임을 알 수 있다.
$\quad$ 켤레 함수는 멋진 성질들을 가지고 있다. 예를 들어, 볼록 함수에 대해 르장드르 변환을 다시 한번 적용하면 원래의 함수로 되돌아간다. $f(x)$ 의 기울기가 $s$ 인 것과 같은 방식으로, $f^*(s)$ 의 기울기는 $x$ 이다. 다음 두 예제는 기계 학습에서 볼록 켤레가 흔히 사용되는 용례를 보여준다.
예제 7.7 (볼록 켤레)
볼록 켤레의 응용을 설명하기 위해, 양의 정부호 행렬 $\boldsymbol{K} \in \mathbb{R}^{n \times n}$ 에 기반한 다음의 이차 함수를 고려하자.
우리는 원초 변수(primal variable)를 $\boldsymbol{y} \in \mathbb{R}^n$ 로, 쌍대 변수(dual variable)를 $\boldsymbol{\alpha} \in \mathbb{R}^n$ 로 표기한다.
$\quad$ 정의 7.4를 적용하면, 다음 함수를 얻는다.
함수가 미분 가능하므로, $\boldsymbol{y}$ 에 대해 미분을 취하고 이를 0으로 설정함으로써 최댓값을 찾을 수 있다.
따라서 그래디언트가 0일 때 우리는 $\boldsymbol{y} = \frac{1}{\lambda} \boldsymbol{K} \boldsymbol{\alpha}$ 를 얻는다. 이를 (7.60)에 대입하면 다음이 산출된다.
$\to$ 내적 $\langle \boldsymbol{\alpha}, \boldsymbol{y} \rangle$ 은 기하학적으로 1차함수(평면의 방정식)이며, 이는 원점을 지나고 $\boldsymbol{\alpha}$ 방향을 가지는 초평면이다.
$\to$ 식 (7.62)는 $\boldsymbol{K}$ 가 대칭행렬임을 이용하여 유도된다.
어떤 행렬이 양의 정부호인것이 대칭행렬이기 위한 필요충분조건은 아니다. 가령 행렬 $\boldsymbol{A} = \begin{bmatrix} 1 & -1 \ 1 & 1 \end{bmatrix}$ 는 비대칭이지만 양의 정부호이다.
모든 정방 행렬은 대칭인 부분과 비대칭(교대) 부분으로 나눠질 수 있는데, 이차 형식을 전개할 때 비대칭 부분이 상쇄되어 사라지기 때문에 우리는 다차원 공간에서 함수의 곡률을 결정할 때 암묵적으로 대칭임을 가정한다.
$\to$ 기계학습에서 종종 역행렬을 직접 계산하는 것은 매우 까다로운데, 르장드르 변환을 통해 쌍대 문제를 유도하면 원래 행렬로 최적해를 계산할 수 있다.
예제 7.8
기계 학습에서, 우리는 종종 함수들의 합을 사용한다. 예를 들어, 훈련 세트(training set)의 목적 함수는 훈련 세트 내 각 예제(example)에 대한 손실(losses)들의 합을 포함한다. 다음에서 우리는 $\ell : \mathbb{R} \rightarrow \mathbb{R}$ 인 손실들의 합 $\ell(t)$ 에 대한 볼록 켤레를 도출한다. 이것은 또한 벡터 경우에 대한 볼록 켤레의 적용을 예시한다. $\mathcal{L}(\boldsymbol{t}) = \sum_{i=1}^n \ell_i(t_i)$ 라고 하자. 그러면,
$\to$ 손실들의 합 $\ell(t)$ 은 MSE를 포함한 모든 손실 함수를 추상적인 함수로 표현한 것이다.
$\quad$ 섹션 7.2에서 우리가 라그랑주 승수를 사용하여 쌍대 최적화 문제를 도출했음을 상기하라. 나아가, 볼록 최적화 문제에 대해 우리는 강한 쌍대성(strong duality)을 가지며, 이는 원초 문제와 쌍대 문제의 해가 일치함을 의미한다. 여기서 설명된 르장드르-펜첼 변환 역시 쌍대 최적화 문제를 도출하는 데 사용될 수 있다. 더 나아가, 함수가 볼록하고 미분 가능할 때, 상한(supremum)은 유일하다. 이 두 접근법 사이의 관계를 더 자세히 조사하기 위해, 선형 등식 제약을 가진 볼록 최적화 문제를 고려해 보자.
예제 7.9
$f(\boldsymbol{y})$ 와 $g(\boldsymbol{x})$ 를 볼록 함수라 하고, $\boldsymbol{A}$ 를 $\boldsymbol{A}\boldsymbol{x} = \boldsymbol{y}$ 를 만족하는 적절한 차원의 실수 행렬이라 하자. 그러면
제약 조건 $\boldsymbol{A}\boldsymbol{x} = \boldsymbol{y}$ 에 대한 라그랑주 승수 $\boldsymbol{u}$ 를 도입하면,
여기서 $\max$ 와 $\min$ 을 스왑(swapping)하는 마지막 단계는 $f(\boldsymbol{y})$ 와 $g(\boldsymbol{x})$ 가 볼록 함수라는 사실에 기인한다. 점곱 항을 쪼개고 $\boldsymbol{x}$ 와 $\boldsymbol{y}$ 에 대해 모으면(collecting),
$\quad$ 볼록 켤레(정의 7.4)와 점곱이 대칭적이라는 사실을 상기하면,
<일반적인 내적에 대해, $\boldsymbol{A}^\top$ 는 수반 연산자(adjoint) $\boldsymbol{A}^{*}$ 로 대체된다.>
따라서, 우리는 다음을 증명하였다.
$\quad$ 르장드르-펜첼 켤레는 볼록 최적화 문제로 표현될 수 있는 기계 학습 문제들에 대해 상당히 유용함이 밝혀졌다. 특히, 각 예제에 독립적으로 적용되는 볼록 손실 함수들에 대하여, 켤레 손실은 쌍대 문제를 도출하는 매우 편리한 방법이다.