Deisenroth, Marc Peter, A. Aldo Faisal, and Cheng Soon Ong. Mathematics for machine learning. Cambridge University Press, 2020.
7
Continuous Optimization
머신러닝 알고리즘은 컴퓨터에서 구현되므로, 수학적 공식은 수치 최적화 방법으로 표현된다. 이 장에서는 머신러닝 모델을 훈련하기 위한 기본적인 수치적 방법을 설명한다. 머신러닝 모델을 훈련하는 것은 종종 좋은 매개변수 집합을 찾는 것으로 귀결된다. "좋다"는 개념은 목적 함수(objective function) 또는 **확률 모델(probabilistic model)**에 의해 결정되며, 이에 대한 예시는 이 책의 두 번째 부분에서 살펴볼 것이다. 목적 함수가 주어지면, 최적의 값을 찾는 것은 **최적화 알고리즘(optimization algorithms)**을 사용하여 수행된다.
이 장에서는 연속 최적화의 두 가지 주요 분야(그림 7.1): **비제약 최적화(unconstrained optimization)**와 **제약 최적화(constrained optimization)**를 다룬다. 이 장에서는 목적 함수가 미분 가능하다고 가정하며(5장 참조), 따라서 공간의 각 위치에서 **기울기(gradient)**에 접근하여 최적 값을 찾는 데 도움을 받을 수 있다. 관례적으로, 머신러닝의 대부분의 목적 함수는 최소화되도록 설계되어 있으며, 즉 최적 값은 최소 값이다. 직관적으로 최적 값을 찾는 것은 목적 함수의 **골짜기(valleys)**를 찾는 것과 같으며, 기울기는 우리를 **오르막(uphill)**으로 안내한다. 아이디어는 **내리막(downhill)**으로 이동하여(기울기의 반대 방향) 가장 깊은 지점을 찾기를 바라는 것이다. 비제약 최적화의 경우, 이것이 우리가 필요한 유일한 개념이지만, 7.1절에서 논의할 몇 가지 설계 선택 사항이 있다. 제약 최적화의 경우, 제약을 관리하기 위해 다른 개념을 도입해야 한다(7.2절). 또한 **전역 최적점(global optimum)**에 도달하는 것에 대해 설명할 수 있는 특별한 종류의 문제(7.3절의 볼록 최적화 문제(convex optimization problems))도 소개할 것이다.
그림 7.2의 함수를 고려해 보자. 이 함수는 x=−4.5 근처에 **전역 최솟값(global minimum)**을 가지며, 함수 값은 약 -47이다. 함수가 "매끄럽기(smooth)" 때문에, 기울기는 우리가 오른쪽으로 또는 왼쪽으로 한 걸음 나아가야 하는지를 나타내어 최솟값을 찾는 데 도움을 줄 수 있다. 이는 우리가 올바른 "그릇(bowl)"에 있다고 가정하는데, x=0.7 근처에 또 다른 **지역 최솟값(local minimum)**이 존재하기 때문이다. 함수의 도함수를 계산하고 이를 0으로 설정함으로써 함수의 모든 **정류점(stationary points)**을 풀 수 있다는 것을 상기하자.
ℓ(x)=x4+7x3+5x2−17x+3,
에 대해, 우리는 해당 기울기를 다음과 같이 얻는다:
dxdℓ(x)=4x3+21x2+10x−17.
우리가 RD의 데이터와 모델을 고려하므로, 우리가 직면하는 최적화 문제는 이산 변수에 대한 **조합 최적화 문제(combinatorial optimization problems)**와는 달리 **연속 최적화 문제(continuous optimization problems)**이다.
전역 최솟값
지역 최솟값
정류점은 도함수의 실수 근, 즉 기울기가 0인 점이다.
Figure 7.1 이 장에서 제시된 최적화 관련 개념의 마인드맵. 두 가지 주요 아이디어는 **경사 하강법(gradient descent)**과 **볼록 최적화(convex optimization)**이다.
이것은 3차 방정식이므로, 일반적으로 0으로 설정하면 세 가지 해를 갖는다. 이 예시에서는 그 중 두 개는 최솟값이고 하나는 최댓값이다(x=−1.4 근처). 정류점이 최솟값인지 최댓값인지 확인하려면, 도함수를 두 번 취하고 정류점에서 이계 도함수가 양수인지 음수인지 확인해야 한다. 우리의 경우, 이계 도함수는 다음과 같다:
dx2d2ℓ(x)=12x2+42x+10.
우리가 시각적으로 추정한 x=−4.5,−1.4,0.7 값을 대입하면, 예상대로 중간 지점은 최댓값(dx2d2ℓ(x)<0)이고 다른 두 정류점은 최솟값임을 알 수 있다.
이전 논의에서 x 값을 분석적으로 푸는 것을 피했지만, 위와 같은 저차 다항식의 경우 그렇게 할 수 있었다. 일반적으로 우리는 분석적 해를 찾을 수 없으므로, 어떤 값, 예를 들어 x0=−6에서 시작하여 **음의 기울기(negative gradient)**를 따라야 한다. 음의 기울기는 우리가
Figure 7.2 예시 목적 함수. 음의 기울기는 화살표로 표시되어 있으며, 전역 최솟값은 파란색 점선으로 표시되어 있다.
오른쪽으로 가야 하지만 얼마나 멀리 가야 하는지는 알려주지 않는다(이를 **스텝 크기(step-size)**라고 한다). 또한, 만약 우리가 오른쪽에서 시작했다면(예: x0=0), 음의 기울기는 우리를 잘못된 최솟값으로 이끌었을 것이다. 그림 7.2는 x>−1일 때 음의 기울기가 그림의 오른쪽에 있는 최솟값을 향하고 있으며, 이 최솟값은 더 큰 목적 함수 값을 가진다는 사실을 보여준다.
7.3절에서는 **볼록 함수(convex functions)**라고 불리는, 최적화 알고리즘의 시작점에 대한 이러한 까다로운 의존성을 보이지 않는 함수 클래스에 대해 배울 것이다. 볼록 함수의 경우, 모든 지역 최솟값은 전역 최솟값이다. 많은 머신러닝 목적 함수는 볼록하게 설계되어 있으며, 12장에서 그 예시를 볼 것이다.
이 장의 지금까지의 논의는 1차원 함수에 대한 것이었으며, 기울기, 하강 방향, 최적 값의 아이디어를 시각화할 수 있었다. 이 장의 나머지 부분에서는 고차원에서 동일한 아이디어를 개발한다. 불행히도, 우리는 1차원에서만 개념을 시각화할 수 있지만, 일부 개념은 고차원으로 직접 일반화되지 않으므로 읽을 때 주의가 필요하다.
7.1 Optimization Using Gradient Descent
이제 실수 값 함수의 최솟값을 구하는 문제를 고려해 보자.
xminf(x),
일반적으로 5차 이상의 다항식에 대해서는 대수적 해법이 존재하지 않는다(Abel, 1826).
볼록 함수(convex functions)의 모든 국소 최솟값(local minima)은 전역 최솟값(global minimum)이다.
우리는 기울기(gradients)에 대해 행 벡터(row vectors) 표기법을 사용한다.
여기서 f:Rd→R는 당면한 머신러닝 문제를 포착하는 목적 함수(objective function)이다. 함수 f는 미분 가능하며, 닫힌 형식(closed form)으로 해석적인 해를 찾을 수 없다고 가정한다.
**경사 하강법(Gradient descent)**은 1차 최적화 알고리즘이다. 경사 하강법을 사용하여 함수의 국소 최솟값을 찾으려면, 현재 지점에서 함수의 기울기(gradient)의 음수 값에 비례하는 단계(step)를 밟는다. 5.1절에서 기울기가 가장 가파른 상승 방향을 가리킨다는 것을 상기하자. 또 다른 유용한 직관은 함수가 특정 값(f(x)=c, 여기서 c∈R)을 갖는 선들의 집합, 즉 **등고선(contour lines)**을 고려하는 것이다. 기울기는 우리가 최적화하려는 함수의 등고선에 직교하는 방향을 가리킨다.
다변수 함수를 고려해 보자. 특정 위치 x0에서 시작하는 공이 있는 표면(f(x) 함수로 설명됨)을 상상해 보라. 공이 놓이면 가장 가파른 하강 방향으로 내리막길을 따라 움직일 것이다. 경사 하강법은 x0에서 f의 음의 기울기 −((∇f)(x0))⊤ 방향으로 움직이면 f(x0)가 가장 빠르게 감소한다는 사실을 이용한다. 이 책에서는 함수가 미분 가능하다고 가정하며, 더 일반적인 설정은 7.4절을 참조한다. 그러면,
x1=x0−γ((∇f)(x0))⊤
작은 스텝 크기(step-size) γ⩾0에 대해 f(x1)⩽f(x0)가 성립한다. 기울기에 대해 전치(transpose)를 사용하는 이유는 그렇지 않으면 차원이 맞지 않기 때문이다.
이러한 관찰을 통해 간단한 경사 하강법 알고리즘을 정의할 수 있다. 함수 f:Rn→R,x↦f(x)의 국소 최적값 f(x∗)을 찾고자 한다면, 최적화하려는 매개변수의 초기 추정값 x0에서 시작하여 다음 식에 따라 반복한다.
xi+1=xi−γi((∇f)(xi))⊤.
적절한 스텝 크기 γi에 대해, 수열 f(x0)⩾f(x1)⩾…은 국소 최솟값으로 수렴한다.
초기 위치 x0=[−3,−1]⊤에서 시작하여, (7.6)을 반복적으로 적용하면 최솟값으로 수렴하는 일련의 추정치를 얻을 수 있다.
그림 7.3 2차원 quadratic surface(히트맵으로 표시)에서의 gradient descent. 설명은 예시 7.1을 참조하라.
(그림 7.3에 설명되어 있다). x0에서의 negative gradient가 북쪽과 동쪽을 가리키며, 이는 x1=[−1.98,1.21]⊤로 이어진다(그림에서나 x0를 (7.8)에 γ=0.085와 함께 대입하여 확인할 수 있다). 이 과정을 반복하면 x2=[−1.32,−0.42]⊤ 등을 얻을 수 있다.
비고. Gradient descent는 최솟값에 가까워질수록 상대적으로 느려질 수 있다. asymptotic rate of convergence는 다른 많은 방법보다 떨어진다. 공이 언덕을 굴러 내려가는 비유를 사용하면, 표면이 길고 얇은 계곡일 때 문제는 poorly conditioned이다 (Trefethen and Bau III, 1997). poorly conditioned convex problem의 경우, gradient가 최솟점까지의 최단 방향에 거의 직교하게 되면서 gradient descent는 점점 더 "지그재그" 형태로 움직인다. 그림 7.3을 참조하라. □
7.1.1 Step-size
앞서 언급했듯이, **경사 하강법(gradient descent)**에서 적절한 **스텝 사이즈(step-size)**를 선택하는 것은 중요하다. 스텝 사이즈가 너무 작으면 경사 하강법은 느려질 수 있다. 스텝 사이즈가 너무 크게 선택되면 경사 하강법은 **오버슈트(overshoot)**하거나, 수렴하지 못하거나, 심지어 **발산(diverge)**할 수도 있다. 다음 섹션에서는 **모멘텀(momentum)**의 사용에 대해 논의할 것이다. 모멘텀은 **경사 업데이트(gradient updates)**의 불규칙한 동작을 완화하고 **진동(oscillations)**을 억제하는 방법이다.
**적응형 경사 방법(adaptive gradient methods)**은 함수의 국소적 특성에 따라 각 반복마다 스텝 사이즈를 재조정한다. 두 가지 간단한 **휴리스틱(heuristics)**이 있다 (Toussaint, 2012):
경사 단계 후에 함수 값이 증가하면 스텝 사이즈가 너무 컸던 것이다. 해당 단계를 취소하고 스텝 사이즈를 줄인다.
함수 값이 감소하면 스텝을 더 크게 할 수 있었을 것이다. 스텝 사이즈를 늘려본다.
스텝 사이즈는 **학습률(learning rate)**이라고도 불린다.
"취소(undo)" 단계가 자원 낭비처럼 보일 수 있지만, 이 휴리스틱을 사용하면 **단조 수렴(monotonic convergence)**을 보장한다.
Example 7.2 (Solving a Linear Equation System)
Ax=b 형태의 선형 방정식을 풀 때, 실제로는 유클리드 노름(Euclidean norm)을 사용하여 제곱 오차(squared error)를 최소화하는 x∗를 찾아 Ax−b=0을 근사적으로 푼다.
∥Ax−b∥2=(Ax−b)⊤(Ax−b)
x에 대한 (7.9)의 gradient는 다음과 같다.
∇x=2(Ax−b)⊤A.
이 gradient를 gradient descent 알고리즘에 직접 사용할 수 있다. 그러나 이 특정 특수 사례의 경우, gradient를 0으로 설정하여 찾을 수 있는 **해석적 해(analytic solution)**가 존재한다. 제곱 오차 문제 해결에 대해서는 9장에서 더 자세히 다룰 것이다.
참고. 선형 방정식 시스템 Ax=b의 해를 찾는 데 적용될 때, gradient descent는 수렴 속도가 느릴 수 있다. gradient descent의 수렴 속도는 condition numberκ=σ(A)min σ(A)max 에 따라 달라지는데, 이는 A의 최대 특이값(singular value)과 최소 특이값의 비율이다(4.5절). condition number는 본질적으로 가장 많이 구부러진 방향과 가장 적게 구부러진 방향의 비율을 측정하며, 이는 ill-conditioned 문제가 길고 얇은 계곡과 같다는 우리의 이미지에 해당한다. 즉, 한 방향으로는 매우 구부러져 있지만 다른 방향으로는 매우 평평하다. Ax=b를 직접 푸는 대신, P−1(Ax−b)=0을 풀 수 있는데, 여기서 P는 preconditioner라고 불린다. 목표는 P−1A가 더 나은 condition number를 가지면서 동시에 P−1를 계산하기 쉽게 P−1를 설계하는 것이다. gradient descent, preconditioning, 그리고 수렴에 대한 추가 정보는 Boyd와 Vandenberghe (2004, chapter 9)를 참조한다.
7.1.2 Gradient Descent With Momentum
그림 7.3에서 볼 수 있듯이, 최적화 표면의 곡률이 poorly scaled된 영역을 포함하는 경우 경사 하강법(gradient descent)의 수렴 속도가 매우 느릴 수 있다. 곡률이 이러한 특성을 가질 때, 경사 하강법 단계는 계곡의 벽 사이를 오가며 작은 단계로 최적점에 접근한다. 수렴을 개선하기 위해 제안된 방법은 경사 하강법에 **기억(memory)**을 부여하는 것이다.
모멘텀(momentum)을 사용한 경사 하강법(Gradient descent with momentum) (Rumelhart et al., 1986)은 이전 반복에서 발생한 일을 기억하기 위한 추가 항을 도입하는 방법이다. 이 기억은 진동을 완화하고 경사 업데이트를 부드럽게 만든다. 공 비유를 계속하자면, 모멘텀 항은 방향을 바꾸기 꺼려하는 무거운 공의 현상을 모방한다. 이 아이디어는 **이동 평균(moving average)**을 구현하기 위해 기억을 가진 경사 업데이트를 사용하는 것이다. 모멘텀 기반 방법은 각 반복 i에서 업데이트 Δxi를 기억하고, 현재 경사와 이전 경사의 선형 조합으로 다음 업데이트를 결정한다.
여기서 α∈[0,1]이다. 때로는 경사를 대략적으로만 알 수 있다. 이러한 경우, 모멘텀 항은 경사의 다양한 **노이즈가 있는 추정치(noisy estimates)**를 평균화하기 때문에 유용하다. 근사 경사를 얻는 특히 유용한 방법 중 하나는 다음에 논의할 **확률적 근사(stochastic approximation)**를 사용하는 것이다.
7.1.3 Stochastic Gradient Descent
gradient를 계산하는 것은 매우 시간이 많이 소요될 수 있다. 그러나 종종 gradient의 "저렴한" 근사치를 찾는 것이 가능하다. gradient를 근사하는 것은 실제 gradient와 대략적으로 같은 방향을 가리키는 한 여전히 유용하다.
**Stochastic gradient descent (SGD)**는 미분 가능한 함수들의 합으로 작성된 목적 함수를 최소화하기 위한 gradient descent 방법의 stochastic 근사치이다. 여기서 stochastic이라는 단어는 우리가 gradient를 정확히 알지 못하고, 대신 노이즈가 있는 근사치만 알고 있다는 사실을 인정한다는 것을 의미한다. 근사 gradient의 확률 분포를 제한함으로써, 우리는 여전히 SGD가 수렴할 것이라고 이론적으로 보장할 수 있다.
머신러닝에서 n=1,…,N개의 데이터 포인트가 주어졌을 때, 우리는 종종 각 예시 n에 의해 발생하는 손실 Ln의 합인 목적 함수를 고려한다. 수학적 표기법으로, 우리는 다음과 같은 형태를 갖는다:
L(θ)=n=1∑NLn(θ),
여기서 θ는 관심 있는 파라미터 벡터이다. 즉, L을 최소화하는 θ를 찾고자 한다. 회귀(9장)의 예시로는 음의 로그 우도(negative loglikelihood)가 있는데, 이는 개별 예시의 로그 우도(log-likelihood)의 합으로 표현된다:
L(θ)=−n=1∑Nlogp(yn∣xn,θ),
여기서 xn∈RD는 훈련 입력, yn은 훈련 목표, θ는 회귀 모델의 파라미터이다.
이전에 소개된 표준 gradient descent는 "배치" 최적화 방법이다. 즉, 최적화는 전체 훈련 세트를 사용하여 수행되며, 파라미터 벡터는 다음과 같이 업데이트된다:
θi+1=θi−γi(∇L(θi))⊤=θi−γin=1∑N(∇Ln(θi))⊤
적절한 스텝 크기 파라미터 γi에 대해. 합 gradient를 평가하려면 모든 개별 함수 Ln의 gradient를 비싸게 평가해야 할 수 있다. 훈련 세트가 방대하거나 간단한 공식이 없을 경우, gradient의 합을 평가하는 것은 매우 비싸진다.
(7.15)의 ∑n=1N(∇Ln(θi)) 항을 고려해보자. 우리는 더 작은 Ln 집합에 대해 합을 취함으로써 계산량을 줄일 수 있다. 모든 Ln을 n=1,…,N에 대해 사용하는 batch gradient descent와 달리, mini-batch gradient descent에서는 Ln의 부분 집합을 무작위로 선택한다. 극단적인 경우, gradient를 추정하기 위해 단 하나의 Ln만 무작위로 선택한다. 데이터의 부분 집합을 취하는 것이 합리적인 이유에 대한 핵심 통찰은 gradient descent가 수렴하기 위해서는 gradient가 실제 gradient의 unbiased estimate이기만 하면 된다는 것을 깨닫는 것이다. 사실 (7.15)의 ∑n=1N(∇Ln(θi)) 항은 gradient의 기대값(6.4.1절)에 대한 empirical estimate이다. 따라서 데이터의 어떤 subsample을 사용하는 것과 같이 기대값에 대한 다른 unbiased empirical estimate도 gradient descent의 수렴에 충분할 것이다.
참고. 학습률이 적절한 속도로 감소하고 비교적 완화된 가정을 충족하는 경우, stochastic gradient descent는 거의 확실하게 local minimum으로 수렴한다 (Bottou, 1998).
왜 근사 gradient를 사용하는 것을 고려해야 할까? 주요 이유는 중앙 처리 장치(CPU)/그래픽 처리 장치(GPU) 메모리 크기 또는 계산 시간 제한과 같은 실제 구현 제약 때문이다. 우리는 gradient를 추정하는 데 사용되는 부분 집합의 크기를 empirical mean을 추정할 때 표본의 크기를 생각했던 것과 같은 방식으로 생각할 수 있다(6.4.1절). 큰 mini-batch 크기는 gradient의 정확한 추정치를 제공하여 파라미터 업데이트의 분산을 줄인다. 또한, 큰 mini-batch는 비용 및 gradient의 벡터화된 구현에서 고도로 최적화된 행렬 연산을 활용한다. 분산 감소는 더 안정적인 수렴으로 이어지지만, 각 gradient 계산은 더 비싸질 것이다.
반대로, 작은 mini-batch는 빠르게 추정된다. mini-batch 크기를 작게 유지하면, gradient estimate의 노이즈가 우리가 다른 방법으로는 갇힐 수 있는 일부 좋지 않은 local optima에서 벗어날 수 있도록 해준다. 머신러닝에서 최적화 방법은 훈련 데이터에 대한 목적 함수를 최소화하여 훈련에 사용되지만, 전반적인 목표는 generalization performance를 향상시키는 것이다(8장). 머신러닝의 목표가 목적 함수의 최소값을 정확하게 추정할 필요는 없기 때문에, mini-batch 접근 방식을 사용하는 근사 gradient가 널리 사용되어 왔다. Stochastic gradient descent는 수백만 개의 이미지에 대한 deep neural network 훈련(Dean et al., 2012), topic model(Hoffman et al., 2013), reinforcement learning(Mnih et al., 2015) 또는 대규모 Gaussian process model 훈련(Hensman et al., 2013; Gal et al., 2014)과 같은 대규모 머신러닝 문제에서 매우 효과적이다 (Bottou et al., 2018).
그림 7.4
제약 최적화의 그림. 제약 없는 문제(등고선으로 표시)는 오른쪽에 최소값(원으로 표시)을 갖는다. 상자 제약(−1⩽x⩽1 및 −1⩽y⩽1)은 최적 해가 상자 안에 있어야 함을 요구하며, 별표로 표시된 최적 값을 초래한다.
7.2 Constrained Optimization and Lagrange Multipliers
이전 섹션에서는 함수 f:RD→R의 최솟값을 구하는 문제인
xminf(x),
를 고려했다.
이 섹션에서는 추가적인 제약 조건이 있는 경우를 다룬다. 즉, i=1,…,m에 대해 실수 값 함수 gi:RD→R에 대해 제약 조건이 있는 최적화 문제(그림 7.4 참조)를 고려한다.
minx subject to f(x)gi(x)⩽0 for all i=1,…,m
함수 f와 gi는 일반적으로 **비볼록(non-convex)**일 수 있으며, 다음 섹션에서는 **볼록(convex)**인 경우를 고려할 것이다.
제약 조건이 있는 문제 (7.17)을 제약 조건이 없는 문제로 변환하는 한 가지 분명하지만 실용적이지 않은 방법은 **지시 함수(indicator function)**를 사용하는 것이다.
이는 제약 조건이 충족되지 않으면 무한한 페널티를 부여하므로 동일한 해를 제공한다. 그러나 이 무한 계단 함수는 최적화하기가 똑같이 어렵다. 우리는 Lagrange multiplier를 도입하여 이 어려움을 극복할 수 있다. Lagrange multiplier의 아이디어는 계단 함수를 선형 함수로 대체하는 것이다.
문제 (7.17)에 대해 각 부등식 제약 조건에 해당하는 Lagrange multiplierλi⩾0를 도입하여 Lagrangian을 다음과 같이 정의한다 (Boyd and Vandenberghe, 2004, chapter 4).
L(x,λ)=f(x)+i=1∑mλigi(x)=f(x)+λ⊤g(x)
마지막 줄에서는 모든 제약 조건 gi(x)를 벡터 g(x)로, 모든 Lagrange multiplier를 벡터 λ∈Rm로 연결했다.
이제 Lagrangian duality의 개념을 소개한다. 일반적으로 최적화에서의 duality는 한 변수 집합 x (이를 primal variables라고 함)에 대한 최적화 문제를 다른 변수 집합 λ (이를 dual variables라고 함)에 대한 다른 최적화 문제로 변환하는 아이디어이다. 우리는 두 가지 다른 duality 접근 방식을 소개한다. 이 섹션에서는 Lagrangian duality를 논의하고, 섹션 7.3.3에서는 Legendre-Fenchel duality를 논의한다.
정의 7.1. (7.17)의 문제
minx subject to f(x)gi(x)⩽0 for all i=1,…,m
는 primal variablesx에 해당하는 primal problem으로 알려져 있다. 관련 Lagrangian dual problem은 다음과 같이 주어진다.
maxλ∈Rm subject to D(λ)λ⩾0
여기서 λ는 dual variables이고 D(λ)=minx∈RdL(x,λ)이다.
비고. 정의 7.1의 논의에서 우리는 독립적인 관심사도 있는 두 가지 개념을 사용한다 (Boyd and Vandenberghe, 2004).
첫 번째는 minimax inequality로, 두 개의 인수를 가진 함수 φ(x,y)에 대해 maximin이 minimax보다 작거나 같다는 것을 의미한다. 즉,
(7.24)의 좌변에 대해 y에 대한 최댓값을 취해도 부등식이 유지된다는 점에 유의하라. 왜냐하면 이 부등식은 모든 y에 대해 참이기 때문이다. 마찬가지로, (7.24)의 우변에 대해 x에 대한 최솟값을 취하여 (7.23)을 얻을 수 있다.
두 번째 개념은 weak duality로, (7.23)을 사용하여 primal values가 항상 dual values보다 크거나 같다는 것을 보여준다. 이는 (7.27)에서 더 자세히 설명된다.
(7.18)의 J(x)와 (7.20b)의 Lagrangian의 차이점은 지시 함수를 선형 함수로 완화했다는 것이다. 따라서 λ⩾0일 때, LagrangianL(x,λ)는 J(x)의 **하한(lower bound)**이다. 그러므로 λ에 대한 L(x,λ)의 최댓값은 다음과 같다.
J(x)=λ⩾0maxL(x,λ)
원래 문제는 J(x)를 최소화하는 것이었다.
x∈Rdminλ⩾0maxL(x,λ).
minimax inequality (7.23)에 의해, 최소화와 최대화의 순서를 바꾸면 더 작은 값이 나온다. 즉,
x∈Rdminλ⩾0maxL(x,λ)⩾λ⩾0maxx∈RdminL(x,λ).
이것은 weak duality라고도 알려져 있다. 우변의 내부 부분은 dual objective functionD(λ)이며 정의는 이를 따른다.
제약 조건이 있는 원래 최적화 문제와 달리, minx∈RdL(x,λ)는 주어진 λ 값에 대한 **제약 없는 최적화 문제(unconstrained optimization problem)**이다. 만약 minx∈RdL(x,λ)를 푸는 것이 쉽다면, 전체 문제도 쉽게 풀 수 있다. (7.20b)에서 L(x,λ)가 λ에 대해 affine임을 관찰함으로써 이를 알 수 있다. 따라서 minx∈RdL(x,λ)는 λ의 **affine 함수들의 점별 최솟값(pointwise minimum of affine functions)**이며, 따라서 f(⋅)와 gi(⋅)가 nonconvex일지라도 D(λ)는 concave이다. 외부 문제인 λ에 대한 최대화는 concave 함수의 최댓값이므로 효율적으로 계산할 수 있다.
f(⋅)와 gi(⋅)가 미분 가능하다고 가정하면, Lagrangian을 x에 대해 미분하고, 미분 값을 0으로 설정한 다음, 최적 값을 구하여 Lagrange dual problem을 찾는다. 섹션 7.3.1과 7.3.2에서는 f(⋅)와 gi(⋅)가 convex인 두 가지 구체적인 예시를 논의할 것이다.
비고 (등식 제약 조건). 추가적인 등식 제약 조건이 있는 (7.17)을 고려해보자.
minx subject to f(x)gi(x)⩽0 for all i=1,…,mhj(x)=0 for all j=1,…,n.
등식 제약 조건을 두 개의 부등식 제약 조건으로 대체하여 모델링할 수 있다. 즉, 각 등식 제약 조건 hj(x)=0에 대해 이를 hj(x)⩽0와 hj(x)⩾0의 두 가지 제약 조건으로 동등하게 대체한다. 결과적으로 Lagrange multiplier는 제약이 없게(unconstrained) 된다.
따라서 (7.28)의 부등식 제약 조건에 해당하는 Lagrange multiplier는 **음이 아닌 값(non-negative)**으로 제한하고, 등식 제약 조건에 해당하는 Lagrange multiplier는 **제약이 없는 상태(unconstrained)**로 둔다.
7.3 Convex Optimization
우리는 전역 최적성(global optimality)을 보장할 수 있는 특히 유용한 최적화 문제 클래스에 집중한다. f(⋅)가 convex function이고, g(⋅)와 h(⋅)를 포함하는 제약 조건이 convex set일 때, 이는 convex optimization problem이라고 불린다. 이 설정에서는 strong duality가 성립한다: dual problem의 최적해는 primal problem의 최적해와 동일하다. convex function과 convex set의 구분은 머신러닝 문헌에서 엄격하게 제시되지 않는 경우가 많지만, 문맥을 통해 암시된 의미를 추론할 수 있다.
Figure 7.5 convex set의 예시.
Figure 7.6 nonconvex set의 예시.
정의 7.2. 집합 C는 임의의 x,y∈C와 0⩽θ⩽1인 임의의 스칼라 θ에 대해 다음을 만족하면 convex set이다.
θx+(1−θ)y∈C.
Convex set은 집합의 임의의 두 요소를 연결하는 직선이 집합 내부에 놓이는 집합이다. Figure 7.5와 7.6은 각각 convex set과 nonconvex set을 보여준다.
Convex function은 함수의 임의의 두 점을 잇는 직선이 함수 위에 놓이는 함수이다. Figure 7.2는 nonconvex function을, Figure 7.3은 convex function을 보여준다. 또 다른 convex function은 Figure 7.7에 나와 있다.
정의 7.3. 도메인이 convex set인 함수 f:RD→R가 있다고 하자. 함수 f는 f의 도메인에 있는 모든 x,y와 0⩽θ⩽1인 임의의 스칼라 θ에 대해 다음을 만족하면 convex function이다.
f(θx+(1−θ)y)⩽θf(x)+(1−θ)f(y).
참고. Concave function은 convex function의 음수이다.
(7.28)의 g(⋅)와 h(⋅)를 포함하는 제약 조건은 함수를 스칼라 값으로 잘라내어 집합을 생성한다. convex function과 convex set 사이의 또 다른 관계는 convex function을 "채워서" 얻은 집합을 고려하는 것이다. convex function은 그릇 모양의 객체이며, 우리는 그 안에 물을 부어 채운다고 상상한다. 이렇게 채워진 집합을 convex function의 epigraph라고 하며, 이는 convex set이다.
함수 f:Rn→R가 미분 가능하면, 우리는 그 gradient∇xf(x) (섹션 5.2)를 사용하여 볼록성을 지정할 수 있다. 함수 f(x)는 임의의 두 점 x,y에 대해 다음이 성립할 때 그리고 그 때에만 convex이다.
f(y)⩾f(x)+∇xf(x)⊤(y−x).
Figure 7.7 convex function의 예시.
만약 함수 f(x)가 두 번 미분 가능하고, 즉 x의 도메인에 있는 모든 값에 대해 Hessian (5.147)이 존재한다면, 함수 f(x)는 ∇x2f(x)가 positive semidefinite일 때 그리고 그 때에만 convex이다 (Boyd and Vandenberghe, 2004).
Example 7.3
음의 엔트로피 함수 f(x)=xlog2x는 x>0에 대해 **볼록(convex)**하다. 함수의 시각화는 Figure 7.8에 나와 있으며, 함수가 볼록함을 확인할 수 있다. 볼록성의 이전 정의를 설명하기 위해, 두 점 x=2와 x=4에 대한 계산을 확인해 보자. f(x)의 볼록성을 증명하려면 모든 점 x∈R에 대해 확인해야 한다는 점에 유의한다.
정의 7.3을 상기해 보자. 두 점의 중간 지점(θ=0.5)을 고려하면, 좌변은 f(0.5⋅2+0.5⋅4)=3log23≈4.75이다. 우변은 0.5(2log22)+0.5(4log24)=1+4=5이다. 따라서 정의가 충족된다.
f(x)는 미분 가능하므로, (7.31)을 대신 사용할 수 있다. f(x)의 도함수를 계산하면 다음과 같다.
정의를 상기함으로써 함수나 집합이 볼록한지 **기본 원리(first principles)**로부터 확인할 수 있다. 실제로는 특정 함수나 집합이 볼록한지 확인하기 위해 **볼록성을 보존하는 연산(operations that preserve convexity)**에 의존하는 경우가 많다. 세부 사항은 매우 다르지만, 이는 2장에서 벡터 공간에 대해 소개했던 클로저(closure) 개념과 다시 일치한다.
Example 7.4
볼록 함수의 음이 아닌 가중치 합은 볼록하다. 함수 f가 볼록 함수이고, α⩾0가 음이 아닌 스칼라일 때, 함수 αf는 볼록 함수임을 알 수 있다. 이는 정의 7.3의 방정식 양변에 α를 곱하고, 음이 아닌 수를 곱해도 부등호가 변하지 않는다는 점을 상기하면 알 수 있다.
이로써 볼록 함수의 합이 볼록하다는 증명이 완료된다.
앞선 두 가지 사실을 결합하면, α,β⩾0일 때 αf1(x)+βf2(x)가 볼록하다는 것을 알 수 있다. 이 **폐쇄성(closure property)**은 두 개 이상의 볼록 함수의 음이 아닌 가중치 합에 대해서도 유사한 논증을 통해 확장될 수 있다.
참고. (7.30)의 부등식은 때때로 **Jensen의 부등식(Jensen's inequality)**이라고 불린다. 사실, 볼록 함수의 음이 아닌 가중치 합에 대한 모든 종류의 부등식은 Jensen의 부등식이라고 불린다.
요약하자면, 제약 최적화 문제(constrained optimization problem)는 다음과 같을 때 **볼록 최적화 문제(convex optimization problem)**라고 불린다.
xminf(x) subject to gi(x)⩽0hj(x)=0 for all for all j=1,…,m
여기서 모든 함수 f(x)와 gi(x)는 볼록 함수이고, 모든 hj(x)=0은 볼록 집합이다. 다음에서는 널리 사용되고 잘 이해되는 두 가지 유형의 볼록 최적화 문제에 대해 설명할 것이다.
7.3.1 Linear Programming
선행하는 모든 함수가 선형인 특수한 경우를 고려해 보자. 즉,
x∈Rdmin subject to c⊤xAx⩽b,
여기서 A∈Rm×d이고 b∈Rm이다. 이것은 linear program으로 알려져 있다. 이 linear program은 d개의 변수와 m개의 선형 제약 조건을 가진다. Lagrangian은 다음과 같이 주어진다.
L(x,λ)=c⊤x+λ⊤(Ax−b),
여기서 λ∈Rm는 음이 아닌 Lagrange multipliers의 벡터이다. x에 해당하는 항들을 재배열하면 다음과 같다.
L(x,λ)=(c+A⊤λ)⊤x−λ⊤b.
L(x,λ)를 x에 대해 미분하고 0으로 설정하면 다음을 얻는다.
c+A⊤λ=0.
따라서 dual Lagrangian은 D(λ)=−λ⊤b이다. 우리는 D(λ)를 최대화하고자 한다. L(x,λ)의 미분이 0이 되는 제약 조건 외에도, λ⩾0이라는 사실이 있으므로, 다음 dual optimization problem이 도출된다.
maxλ∈Rm subject to −b⊤λc+A⊤λ=0λ⩾0.
이것 또한 linear program이지만, m개의 변수를 가진다. 우리는 m과 d 중 어느 것이 더 큰지에 따라 primal (7.39) 또는 dual (7.43) program을 풀지 선택할 수 있다. 여기서 d는 primal linear program의 변수 개수이고, m은 제약 조건의 개수이다.
Jensen's inequality
convex optimization problem
linear program Linear program은 산업에서 가장 널리 사용되는 접근 방식 중 하나이다.
primal을 최소화하고 dual을 최대화하는 것이 관례이다.
Example 7.5 (Linear Program)
두 개의 변수를 갖는 다음 선형 프로그램을 고려해 보자.
minx∈R2
−[53]⊤[x1x2]
subject to
22−2002−41−11[x1x2]⩽3385−18
이 프로그램은 그림 7.9에도 나와 있다. 목적 함수는 선형이므로 선형 등고선이 생성된다. 표준 형식의 제약 조건 집합은 범례로 번역된다. 최적값은 음영 처리된 (실현 가능한) 영역에 있어야 하며 별표로 표시된다.
그림 7.9
선형 프로그램의 예시. 제약 조건이 없는 문제(등고선으로 표시됨)는 오른쪽에 최솟값을 갖는다. 제약 조건을 고려한 최적값은 별표로 표시된다.
"Mathematics for Machine Learning" 초안 (2021-07-29). 피드백: https: //mml-book.com.
7.3.2 Quadratic Programming
목적 함수가 볼록 이차 함수이고 제약 조건이 아핀(affine)인 경우를 고려해 보자. 즉,
x∈Rdmin subject to 21x⊤Qx+c⊤xAx⩽b
여기서 A∈Rm×d, b∈Rm, 그리고 c∈Rd이다. 정방 대칭 행렬 Q∈Rd×d는 **양의 정부호(positive definite)**이므로 목적 함수는 볼록하다. 이를 **이차 계획법(quadratic program)**이라고 한다. 이 문제는 d개의 변수와 m개의 선형 제약 조건을 가진다.
Example 7.6 (Quadratic Program)
두 변수에 대한 quadratic program은 다음과 같다:
minx∈R2 subject to 21[x1x2]⊤[2114][x1x2]+[53]⊤[x1x2]1−100001−1[x1x2]⩽1111
이 프로그램은 Figure 7.4에도 설명되어 있다. objective function은 positive semidefinite matrixQ를 갖는 quadratic이며, 이는 elliptical contour lines를 생성한다. 최적값은 음영 처리된 (실현 가능한) 영역에 있어야 하며, 별표로 표시된다.
λ∈Rmmax subject to −21(c+A⊤λ)⊤Q−1(c+A⊤λ)−λ⊤bλ⩾0
quadratic programming의 머신러닝 적용 사례는 12장에서 살펴볼 것이다.
7.3.3 Legendre-Fenchel Transform and Convex Conjugate
제약 조건을 고려하지 않고 7.2절의 이중성(duality) 개념을 다시 살펴보자. 볼록 집합(convex set)에 대한 유용한 사실 중 하나는 **지지 초평면(supporting hyperplane)**으로 동등하게 설명될 수 있다는 것이다. 초평면(hyperplane)은 볼록 집합과 교차하고, 볼록 집합이 초평면의 한쪽에만 포함될 때 해당 볼록 집합의 지지 초평면이라고 불린다.
르장드르 변환(Legendre transform) 물리학 학생들은 고전 역학에서 라그랑지안(Lagrangian)과 해밀토니안(Hamiltonian)을 연결하는 것으로 르장드르 변환을 접하는 경우가 많다. 르장드르-펜첼 변환(Legendre-Fenchel transform)볼록 켤레(convex conjugate) 볼록 집합의 지지 초평면은 볼록 집합과 교차하며, 볼록 집합이 초평면의 한쪽에만 포함될 때 해당 볼록 집합의 지지 초평면이라고 불린다. 우리는 볼록 함수를 채워서 볼록 집합인 **상위 그래프(epigraph)**를 얻을 수 있음을 상기하자. 따라서 볼록 함수도 지지 초평면으로 설명할 수 있다. 또한, 지지 초평면은 볼록 함수에 "살짝 닿아" 있으며, 사실 그 지점에서의 함수의 **접선(tangent)**임을 관찰할 수 있다. 그리고 함수 f(x)의 주어진 점 x0에서의 접선은 그 지점에서의 함수의 기울기(gradient) 평가값 dxdf(x)x=x0임을 상기하자. 요약하자면, 볼록 집합은 지지 초평면으로 동등하게 설명될 수 있기 때문에, 볼록 함수는 기울기의 함수로 동등하게 설명될 수 있다. 르장드르 변환은 이 개념을 형식화한다.
가장 일반적인 정의부터 시작하는데, 불행히도 직관에 반하는 형태를 가지고 있으며, 이전 단락에서 설명한 직관과 정의를 연결하기 위해 특수한 경우들을 살펴볼 것이다. 르장드르-펜첼 변환은 볼록 미분 가능 함수 f(x)를 접선 s(x)=∇xf(x)에 의존하는 함수로 변환하는 변환(푸리에 변환의 의미에서)이다. 이것이 함수 f(⋅)의 변환이지 변수 x 또는 x에서 평가된 함수의 변환이 아니라는 점을 강조할 가치가 있다. 르장드르-펜첼 변환은 볼록 켤레라고도 알려져 있으며(곧 그 이유를 알게 될 것이다), **이중성(duality)**과 밀접하게 관련되어 있다 (Hiriart-Urruty and Lemaréchal, 2001, chapter 5).
정의 7.4. 함수 f:RD→R의 볼록 켤레는 다음과 같이 정의되는 함수 f∗이다.
f∗(s)=x∈RDsup(⟨s,x⟩−f(x))
이전의 볼록 켤레 정의는 함수 f가 볼록하거나 미분 가능할 필요가 없다는 점에 유의하라. 정의 7.4에서는 일반적인 내적(inner product)(3.2절)을 사용했지만, 이 절의 나머지 부분에서는 너무 많은 기술적 세부 사항을 피하기 위해 유한 차원 벡터 간의 표준 점곱(dot product)(⟨s,x⟩=s⊤x)을 고려할 것이다.
정의 7.4를 기하학적으로 이해하기 위해, 예를 들어 f(x)=x2와 같은 좋고 간단한 1차원 볼록 미분 가능 함수를 고려해 보자. 1차원 문제를 다루고 있으므로 초평면은 선으로 축소된다는 점에 유의하라. 선 y=sx+c를 고려해 보자. 볼록 함수를 지지 초평면으로 설명할 수 있음을 상기하고, 이 함수 f(x)를 지지선으로 설명해 보자. 선의 기울기 s∈R를 고정하고, f의 그래프에 있는 각 점 (x0,f(x0))에 대해, 선이 여전히 (x0,f(x0))와 교차하도록 하는 c의 최솟값을 찾는다. c의 최솟값은 기울기 s를 가진 선이 함수 f(x)=x2에 "살짝 닿는" 지점이라는 점에 유의하라. 기울기 s를 가지고 (x0,f(x0))를 통과하는 선은 다음과 같이 주어진다.
y−f(x0)=s(x−x0)
이 선의 y-절편은 −sx0+f(x0)이다. 따라서 y=sx+c가 f의 그래프와 교차하는 c의 최솟값은 다음과 같다.
x0inf−sx0+f(x0).
이전의 볼록 켤레는 관례상 이것의 음수로 정의된다. 이 단락의 추론은 우리가 1차원 볼록 미분 가능 함수를 선택했다는 사실에 의존하지 않았으며, 볼록하지 않고 미분 가능하지 않은 f:RD→R에 대해서도 유효하다.
비고. 예시 f(x)=x2와 같은 볼록 미분 가능 함수는 좋은 특수한 경우이며, **최고값(supremum)**이 필요 없고, 함수와 그 르장드르 변환 사이에 **일대일 대응(one-to-one correspondence)**이 존재한다. 이를 **기본 원리(first principles)**에서 도출해 보자. 볼록 미분 가능 함수에 대해, x0에서 접선이 f(x0)에 닿으므로 다음이 성립함을 안다.
f(x0)=sx0+c.
우리는 볼록 함수 f(x)를 그 기울기 ∇xf(x)로 설명하기를 원하며, s=∇xf(x0)임을 상기하자. −c에 대한 표현을 얻기 위해 재배열하면 다음과 같다.
−c=sx0−f(x0).
−c는 x0에 따라, 따라서 s에 따라 변한다는 점에 유의하라. 이것이 우리가 이를 s의 함수로 생각할 수 있는 이유이며, 이를 다음과 같이 부른다.
f∗(s):=sx0−f(x0).
(7.58)을 정의 7.4와 비교하면, (7.58)이 (최고값 없는) 특수한 경우임을 알 수 있다.
켤레 함수는 좋은 속성을 가지고 있다. 예를 들어, 볼록 함수에 대해 르장드르 변환을 다시 적용하면 원래 함수로 돌아간다. f(x)의 기울기가 s인 것과 같은 방식으로, f∗(s)의 기울기는 x이다. 다음 두 예시는 머신러닝에서 볼록 켤레의 일반적인 사용법을 보여준다.
이 도출은 추론이 진행됨에 따라 그림을 그려서 이해하는 것이 가장 쉽다.
고전적인 르장드르 변환은 RD의 볼록 미분 가능 함수에 대해 정의된다.
Example 7.7 (Convex Conjugates)
convex conjugate의 적용을 설명하기 위해, 양의 정부호 행렬 K∈Rn×n에 기반한 이차 함수를 고려해 보자.
f(y)=2λy⊤K−1y
여기서 primal variable은 y∈Rn이고 dual variable은 α∈Rn이다.
정의 7.4를 적용하면 다음 함수를 얻는다.
f∗(α)=y∈Rnsup⟨y,α⟩−2λy⊤K−1y.
이 함수는 미분 가능하므로, y에 대해 미분하여 0으로 설정함으로써 최댓값을 찾을 수 있다.
∂y∂[⟨y,α⟩−2λy⊤K−1y]=(α−λK−1y)⊤
따라서 gradient가 0일 때 y=λ1Kα가 된다. 이를 (7.60)에 대입하면 다음을 얻는다.
f∗(α)=λ1α⊤Kα−2λ(λ1Kα)⊤K−1(λ1Kα)=2λ1α⊤Kα.
Example 7.8
머신러닝에서 우리는 종종 함수의 합을 사용한다. 예를 들어, 훈련 세트의 목적 함수는 훈련 세트에 있는 각 예시에 대한 손실의 합을 포함한다. 다음에서는 손실 ℓ(t)의 합에 대한 **볼록 켤레(convex conjugate)**를 도출할 것이다. 여기서 ℓ:R→R이다. 이는 또한 벡터 케이스에 대한 볼록 켤레의 적용을 보여준다. L(t)=∑i=1nℓi(ti)라고 하자. 그러면,
L∗(z)=t∈Rnsup⟨z,t⟩−i=1∑nℓi(ti)=t∈Rnsupi=1∑nziti−ℓi(ti) definition of dot product =i=1∑nt∈Rnsupziti−ℓi(ti)=i=1∑nℓi∗(zi). definition of conjugate
7.2절에서 우리는 **라그랑주 승수(Lagrange multipliers)**를 사용하여 **쌍대 최적화 문제(dual optimization problem)**를 도출했다. 또한, 볼록 최적화 문제의 경우 **강한 쌍대성(strong duality)**이 성립하며, 이는 **원 문제(primal problem)**와 쌍대 문제의 해가 일치함을 의미한다. 여기서 설명하는 르장드르-펜첼 변환(Legendre-Fenchel transform) 또한 쌍대 최적화 문제를 도출하는 데 사용될 수 있다. 더욱이, 함수가 볼록하고 미분 가능할 때, supremum은 유일하다. 이 두 접근 방식 간의 관계를 더 자세히 조사하기 위해, 선형 등식 제약이 있는 볼록 최적화 문제를 고려해 보자.
Example 7.9
f(y)와 g(x)가 **볼록 함수(convex functions)**이고, A가 Ax=y를 만족하는 적절한 차원의 실수 행렬이라고 하자. 그러면 다음이 성립한다.
xminf(Ax)+g(x)=Ax=yminf(y)+g(x).
제약 조건 Ax=y에 대한 라그랑주 승수(Lagrange multiplier)u를 도입하면,
**르장드르-펜첼 켤레(Legendre-Fenchel conjugate)**는 볼록 최적화 문제로 표현될 수 있는 머신러닝 문제에 매우 유용하다. 특히, 각 예시에 독립적으로 적용되는 볼록 손실 함수(convex loss functions)의 경우, **켤레 손실(conjugate loss)**은 **쌍대 문제(dual problem)**를 도출하는 편리한 방법이다.
7.4 Further Reading
Continuous optimization는 활발한 연구 분야이며, 우리는 최근 발전 사항들을 포괄적으로 다루려고 시도하지는 않는다.
Gradient descent 관점에서 볼 때, 각각 자체 문헌을 가진 두 가지 주요 약점이 있다. 첫 번째 문제는 gradient descent가 first-order algorithm이며, 표면의 곡률에 대한 정보를 사용하지 않는다는 점이다. 긴 계곡이 있을 때, gradient는 관심 방향에 수직으로 향한다. Momentum의 아이디어는 일반적인 acceleration methods 클래스로 일반화될 수 있다 (Nesterov, 2018). Conjugate gradient methods는 이전 방향을 고려하여 gradient descent가 직면하는 문제를 피한다 (Shewchuk, 1994). Newton methods와 같은 second-order methods는 Hessian을 사용하여 곡률에 대한 정보를 제공한다. Step-size를 선택하는 많은 방법과 momentum과 같은 아이디어는 목적 함수의 곡률을 고려함으로써 발생한다 (Goh, 2017; Bottou et al., 2018). L-BFGS와 같은 Quasi-Newton methods는 더 저렴한 계산 방법을 사용하여 Hessian을 근사화하려고 시도한다 (Nocedal and Wright, 2006). 최근에는 descent direction을 계산하기 위한 다른 측정 기준에 대한 관심이 있었고, 그 결과 mirror descent (Beck and Teboulle, 2003) 및 natural gradient (Toussaint, 2012)와 같은 접근 방식이 등장했다.
두 번째 과제는 non-differentiable functions를 처리하는 것이다. 함수에 꺾임이 있을 때 gradient methods는 잘 정의되지 않는다. 이러한 경우 subgradient methods를 사용할 수 있다 (Shor, 1985). Non-differentiable functions를 최적화하기 위한 추가 정보 및 알고리즘에 대해서는 Bertsekas (1999)의 책을 참조한다. Constrained optimization problems를 위한 알고리즘을 포함하여 continuous optimization problems를 수치적으로 해결하기 위한 다양한 접근 방식에 대한 방대한 문헌이 있다. 이 문헌을 이해하기 위한 좋은 시작점은 Luenberger (1969) 및 Bonnans et al. (2006)의 책이다. Continuous optimization에 대한 최근 조사는 Bubeck (2015)에 의해 제공된다.
머신러닝의 현대적 응용은 종종 데이터셋의 크기가 batch gradient descent의 사용을 금지한다는 것을 의미하며, 따라서 stochastic gradient descent가 대규모 머신러닝 방법의 현재 핵심이다. 문헌에 대한 최근 조사에는 Hazan (2015) 및 Bottou et al. (2018)이 포함된다.
Duality 및 convex optimization에 대해서는 Boyd and Vandenberghe (2004)의 책에 온라인 강의 및 슬라이드가 포함되어 있다. 더 수학적인 설명은 Bertsekas (2009)에 의해 제공되며, 최적화 분야의 주요 연구자 중 한 명인 Nesterov (2018)의 최근 책도 있다. Convex optimization은 convex analysis를 기반으로 하며, convex functions에 대한 더 근본적인 결과에 관심 있는 독자는 Rockafellar (1970), Hiriart-Urruty and Lemaréchal (2001), 그리고 Borwein and Lewis (2006)를 참조한다. Legendre-Fenchel transforms는 앞서 언급된 convex analysis 책에서도 다루어지지만, Zia et al. (2009)에서 더 초보자 친화적인 설명이 제공된다. Convex optimization algorithms 분석에서 Legendre-Fenchel transforms의 역할은 Polyak (2016)에서 조사된다.
Exercises
7.1 다음 단변수 함수를 고려하라.
f(x)=x3+6x2−3x−5.
이 함수의 stationary points를 찾고, 이들이 maximum, minimum 또는 saddle points 중 어느 것인지 표시하라.
7.2 Stochastic gradient descent의 업데이트 방정식(Equation (7.15))을 고려하라. mini-batch size가 1일 때의 업데이트를 작성하라.
7.3 다음 진술이 참인지 거짓인지 고려하라:
a. 임의의 두 convex sets의 교집합은 convex이다.
b. 임의의 두 convex sets의 합집합은 convex이다.
c. 한 convex setB에서 다른 convex setA를 뺀 차집합은 convex이다.
7.4 다음 진술이 참인지 거짓인지 고려하라:
a. 임의의 두 convex functions의 합은 convex이다.
b. 임의의 두 convex functions의 차는 convex이다.
c. 임의의 두 convex functions의 곱은 convex이다.
d. 임의의 두 convex functions의 최댓값은 convex이다.
7.5 다음 최적화 문제를 matrix notation으로 standard linear program으로 표현하라.
x∈R2,ξ∈Rmaxp⊤x+ξ
제약 조건은 ξ⩾0,x0⩽0 및 x1⩽3이다.
7.6 Figure 7.9에 설명된 linear program을 고려하라.
standard dot product를 가정하여 convex conjugate functionf∗(s)를 도출하라.
힌트: 적절한 함수의 gradient를 취하고 gradient를 0으로 설정하라.
7.10 다음 함수를 고려하라.
f(x)=21x⊤Ax+b⊤x+c
여기서 A는 strictly positive definite이며, 이는 invertible하다는 것을 의미한다. f(x)의 convex conjugate를 도출하라.
힌트: 적절한 함수의 gradient를 취하고 gradient를 0으로 설정하라.
7.11 Hinge loss(support vector machine에서 사용되는 loss)는 다음과 같이 주어진다.
L(α)=max{0,1−α}
L-BFGS와 같은 gradient methods를 적용하는 데 관심이 있고, subgradient methods를 사용하고 싶지 않다면, hinge loss의 kink를 smooth하게 만들어야 한다. dual variable인 β에 대한 hinge lossL∗(β)의 convex conjugate를 계산하라. ℓ2proximal term을 추가하고, 결과 함수의 conjugate를 계산하라.
Figure 7.2 예시 목적 함수. 음의 기울기는 화살표로 표시되어 있으며, 전역 최솟값은 파란색 점선으로 표시되어 있다.
그림 7.3 2차원 quadratic surface(히트맵으로 표시)에서의 gradient descent. 설명은 예시 7.1을 참조하라.
그림 7.4
제약 최적화의 그림. 제약 없는 문제(등고선으로 표시)는 오른쪽에 최소값(원으로 표시)을 갖는다. 상자 제약( 및 )은 최적 해가 상자 안에 있어야 함을 요구하며, 별표로 표시된 최적 값을 초래한다.
Figure 7.6 nonconvex set의 예시.
Figure 7.7 convex function의 예시.
