5장 — 르장드르 변환

볼록 껍질: 두 번 변환해도 돌아오지 않는 곳

공장에서 본 「두 번 하면 제자리」를 정리로 적으면 이렇다. f가 볼록이고 그래프에 끊긴 곳이 없으면 f*의 켤레는 다시 f다. 이 정리에는 「f가 볼록이면」이라는 조건이 붙어 있다. 그런데 신경망의 손실처럼 실제로 다루는 함수에는 골짜기가 여럿인 것이 흔하다. 가운데가 불룩 솟은 함수, 이를테면 x = −1과 x = 1에 골짜기가 두 개 있고 x = 0에서 높이 1까지 솟은 f(x) = (x² − 1)²에는 무슨 일이 생길까? 이런 모양은 흔히 이중 우물(double well)이라 부른다.

이중 우물

먼저 물리 교재의 계산법이 막힌다. s = 0이면 f′(x) = 0인 점이 x = −1, 0, 1 세 개라서 「기울기가 s인 점」이 하나로 정해지지 않기 때문이다. 하지만 sup으로 쓴 정의는 여전히 쓸 수 있고, 세 후보 가운데 sx − f(x)가 가장 큰 것을 고르면 된다. 이렇게 수치로 구한 f*는 f*(0) = 0, f*(±1) ≈ 1.056, f*(±2) ≈ 2.207로 매끄러운 볼록 함수다. 사실 f가 어떤 함수든 f*는 항상 볼록이다. s의 직선들 sx − f(x)에서 가장 높은 것을 이은 함수이기 때문이다.

문제는 한 번 더 변환해서 돌아올 때 생긴다. f*의 켤레 f**를 격자 위에서 계산하면 다음과 같다.

골짜기 밖에서는 원래 함수가 그대로 돌아오지만, 두 골짜기 사이 −1 ≤ x ≤ 1에서는 불룩 솟은 부분이 사라지고 높이 0의 평평한 바닥이 남는다. 이유는 접선 그림으로 보면 분명하다. 곡선 아래에서 자를 밀어 올리면 자는 두 골짜기 바닥에 먼저 걸리므로, 그 사이의 불룩 솟은 곳에는 어떤 기울기의 자도 닿지 못한다. 자의 위치만 기록한 f*에는 그 부분의 정보가 애초에 들어 있지 않은 것이다.

일반적으로 f**는 f 아래에 있는 볼록 함수 가운데 가장 큰 것이고, 이를 f의 볼록 껍질 (움푹한 곳을 메운 함수, convex envelope)이라 부른다. 등호는 f가 이미 볼록일 때만 성립한다.

격자 위의 르장드르 변환

르장드르 변환은 미분을 몰라도 계산할 수 있다. x와 s를 각각 촘촘한 격자로 두고, 각 s마다 sx − f(x)의 최댓값을 찾으면 된다. 아래 코드는 ½x²의 켤레를 확인하고, 이중 우물에 변환을 두 번 적용해 볼록 껍질이 나오는 것을 보인다.

import numpy as np

def legendre(f_vals, x, s):
    # f*(s) = max_x (s x - f(x)) 를 격자 위에서 계산
    return np.max(s[:, None] * x[None, :] - f_vals[None, :], axis=1)

x = np.linspace(-3, 3, 6001)       # 원래 변수의 격자
s = np.linspace(-30, 30, 6001)     # 기울기 변수의 격자

f = 0.5 * x**2                     # 볼록 함수
f_star = legendre(f, x, s)
i = np.argmin(abs(s - 2.0))
print(f_star[i])                   # 2.0  (= 2²/2)

f = (x**2 - 1)**2                  # 볼록하지 않은 이중 우물
f_2star = legendre(legendre(f, x, s), s, x)
for xv in [0.0, 0.5, 1.5]:
    j = np.argmin(abs(x - xv))
    print(xv, round(f[j], 4), round(f_2star[j], 4))
# 0.0 1.0 0.0
# 0.5 0.5625 0.0
# 1.5 1.5625 1.5625

두 번 변환한 결과가 골짜기 밖(x = 1.5)에서는 원래 값과 같고, 두 골짜기 사이(x = 0, 0.5)에서는 0으로 내려가 있다. 격자 계산은 모든 x를 빠짐없이 훑으므로 f′(x) = s의 해가 여러 개여도 알아서 가장 큰 것을 고른다는 점도 눈여겨볼 만하다. 한 가지 주의할 점은 격자의 범위다. f*가 +∞인 기울기에서도 격자 계산은 유한한 값을 내놓는데, 이 값은 격자를 넓힐수록 계속 커진다. 값이 격자 범위에 따라 변하는지 확인하는 것이 「사실은 무한대」를 가려내는 가장 쉬운 방법이다.

ML에서: 쌍대 문제의 간극

ML에서 이 차이를 만나는 곳은 제약이 붙은 최적화다. 이중 우물에서 x를 0에 묶어 둔 채 f가 가장 작아지는 값을 찾는다고 하자. 답은 뻔히 f(0) = 1이다. 그런데 제약을 직접 지키는 대신, x를 한 단위 쓸 때마다 가격 s를 치르게 해서 min_x(f(x) − sx)를 구하고, 그 값이 가장 커지는 가격을 고르는 방식으로 풀 수도 있다. 제약을 어기는 만큼 벌점을 매기고 벌점의 계수까지 함께 조절하는 학습 방법이 이 방식이다. 안쪽의 최솟값은 −f*(s)이므로 이 방식의 답은 가장 큰 −f*(s), 곧 f**(0) = 0이 되어 참답 1보다 1만큼 낮다. 가격을 매겨 바꿔 쓴 문제를 쌍대 문제(dual problem)라 하고, 두 답의 차이를 쌍대성 간극(duality gap)이라 한다. 볼록하지 않은 문제에서는 쌍대 문제가 원래 함수가 아니라 그 볼록 껍질을 풀기 때문에 이런 간극이 생길 수 있다. 다만 볼록하지 않다고 늘 간극이 생기는 것은 아니다. 보상과 함께 안전 조건 같은 제약을 붙인 강화학습은 정책에 대해 볼록하지 않은데도 간극이 0이라는 것이 증명되어 있다(Paternain 외, 2019). 그래서 이런 문제는 가격을 매기는 쪽에서 풀어도 원래 답을 잃지 않는다.

문제 3. 이틀에 한 번 굽는 빵집

동네 빵집이 하루에 식빵 x백 개를 구울 때 드는 비용(만 원)은 오븐을 데우는 가스비 때문에 x = 0이면 0, x = 5(500개)이면 40, x = 10(1,000개)이면 50이다. 가게는 하루 평균 500개를 팔아야 하고, 빵은 이틀 동안 팔 수 있다. (가) 매일 500개씩 구울 때와 이틀에 한 번 1,000개씩 구울 때의 하루 평균 비용을 견주라. (나) 이 빵집의 가격별 최대 이윤표 c*(s) = max(0, 5s − 40, 10s − 50)만 받은 사람이 되찾은 c**(5)는 얼마인가?

(가)는 매일 굽는 쪽이 40만 원, 몰아서 굽는 쪽이 50만 원이니까 매일 굽는 게 싸네요.

50만 원은 이틀 치 비용이잖아. 하루로 나누면 25만 원이야.

아, 이틀에 한 번이니까 나눠야죠. 그럼 몰아서 굽는 게 하루 15만 원 싸요. 오븐을 한 번 데우면 많이 구울수록 이득이네요.

(나)로 가 볼까요. 이윤표의 세 항 가운데 5s − 40이 가장 큰 항이 되는 가격이 있나요?

5s − 40이 10s − 50보다 크려면 s < 2여야 하는데, 그러면 5s − 40이 음수라서 0에 져요. 그런 가격은 없네요.

그러니까 매일 500개를 굽는 선택은 어떤 가격에서도 가장 좋은 선택이 아니었고, 이윤표에는 그 흔적이 남지 않아요. 그럼 되찾은 값은요?

c**(5) = max_s(5s − c*(s))를 격자로 돌리면 s = 5에서 25예요. (가)에서 구한 몰아서 굽는 하루 비용이랑 같아요!

이윤표만 본 사람에게는 이 가게가 처음부터 이틀에 한 번 몰아서 굽는 가게로 보이는 거네요. 40짜리 봉우리가 25로 메워졌어요.

개발 환경을 켜는 데만 한 시간 걸리는 과제는 매일 조금씩 하는 것보다 이틀에 한 번 몰아서 하는 게 나은 거랑 같네요.

문제 4. 두 번 하면 정말 제자리인가

f(x) = (x² − 1)² + 2, 곧 골짜기 바닥이 높이 2에 있는 이중 우물에 대해 f*(0)과 f**(0)을 구하라. (풀어 본 뒤 위젯 2의 「문제 4 불러오기」로 확인해 보자.)

빵집은 비용표가 세 줄뿐이라 그랬던 거고, 이건 매끄러운 곡선이니까 두 번 변환하면 제자리겠죠. f**(0)은 계산할 것도 없이 f(0) = 3이에요.

저는 f*(0)부터 할게요. f′(x) = 4x³ − 4x = 0을 풀면 x = 0이 바로 보이니까, f*(0) = 0·0 − f(0) = −3.

4x³ − 4x = 0의 해는 몇 개죠?

−1, 0, 1… 세 개네요. 하나만 찾고 멈췄어요.

정의는 sup이에요. 세 후보에서 0·x − f(x)를 다 계산해서 가장 큰 걸 골라야 해요.

x = 0이면 −3, x = ±1이면 −2. 그럼 f*(0) = −2예요. 제가 고른 건 하필 가장 나쁜 후보였네요.

볼록 함수에서는 기울기가 s인 점이 하나뿐이라 찾자마자 끝이지만, 볼록이 아니면 그런 점이 여럿이고 그중 대부분은 답이 아니에요. 이제 서연 학생의 답을 검산해 볼까요. f**(0) = sup_s(−f*(s))이고, f*는 볼록이면서 가장 작은 값이 f*(0) = −2예요.

그럼 −f*(s)의 최댓값은 2니까 f**(0) = 2… 3이 아니네요. 제자리가 아니에요. 잠깐만요, 매끄러운지가 문제가 아니었어요. 정리에 「f가 볼록이면」이 붙어 있었는데 제가 그걸 흘려 읽었어요.

맞아요. 볼록이 아닌 함수는 두 번 변환하면 볼록 껍질이 돼요. 골짜기 사이의 봉우리는 어떤 기울기의 자로도 닿지 않으니까 f*에 기록되지 않고, 돌아올 때는 평평하게 메워져요. 그럼 한 번 더, f**를 다시 변환하면요?

f**는 이미 볼록이니까 그 뒤로는 바뀌지 않겠네요. 선형대수에서 배운 사영이랑 같아요. P² = P라서 두 번 사영해도 한 번 한 것과 같지만, 사영하기 전 벡터로 돌아가지는 못하잖아요.

그럼 f*만 들고 있는 사람은 x = 0에 봉우리가 있었는지 영영 모르는 거네요. 문제 1에서 말한 「충분히 자세한 채점표」가 아닌 거고요.