[DeepLearningBook] Chapter 4 : Numerical Computation

이 책 내용을 정리한 포스트입니다.

https://www.deeplearningbook.org/,

Ian Goodfellow and Yoshua Bengio and Aaron Courville, An MIT Press book

책 전체 목차

contents



머신러닝은 막대한 수치연산을 필요로 한다. 반복되는 과정을 통해 수학적 문제를 풀어나가는데, 주로 최적화와 선형 방정식을 푸는 연산들이 많다. 수치 연산을 하는 것은 잘 작동하더라도 한정된 메모리 때문에 효율문제가 발생할 수 있다.

Overflow and Underflow

연속된 범위의 (무한한) 실수를 유한한 비트의 패턴으로 표현해야 하는 것에서 근본적인 문제가 발생한다. 즉, 실수를 컴퓨터로 표현하는 과정에서 반올림에 대한 오차가 발생할 수밖에 없다. 이런 오차가 쌓이면 이론상으로 잘 작동하는 알고리즘도 실제로는 실패할 수 있다.
Underflow는 이러한 반올림 오차중 하나다. 0 근처의 값을 반올림해서 0 으로 만들 때 발생한다. 많은 함수들이 인자가 0 근처의 값일 때와 0 일때의 작동이 다르다. 예를 들면 나눗셈의 경우도, 0 으로 나누게 되면 에러가 발생하는 경우가 많다. 로그를 취할 때도 $\log 0 $은 숫자가 아닌 $- \infty$ 가 된다. 따라서 인자가 0이 되는 경우에 대한 대비를 해주어야 한다.
Overflow는 숫자의 크기가 너무 커서 비트의 표현 범위를 넘어서는 경우다.
Underflow와 Overflow를 잘 피해야 하는 함수중 하나의 예시는 Softmax함수다. Softmax는 주로 모델의 출력값을 확률분포로 바꾸어주기 위해 사용되는데, 아래와 같은 수식으로 정의된다.

$x_i$가 상수 $c$로 고정되어있다고 생각해보면, 아웃풋의 확률은 $\frac{1}{n}$으로 동일하다. 만약 상수 $c$가 매우 작은 음수라면, $exp(c)$는 0이 될 것이고 underflow가 발생하고 결과를 정의할 수 없다. 만약 상수 $c$가 매우 큰 양수라면 $exp(c)$는 무한대가 될 것이고 overflow가 발생하고 마찬가지로 결과를 정의할 수 없다. 이를 해결하기 위해 $softmax(\boldsymbol{x})$대신 $softmax(\boldsymbol{z})$를 사용하는데, 이때 $\boldsymbol{z}=\boldsymbol{x}-max_ix_i$ 이다. 원래 벡터에서 최댓값을 각각 빼줌으로써 연산 결과는 동일하지만 분모에서 overflow나 underflow가 발생하지 않도록 만들어준다. 그러나 분자에서는 여전히 underflow가 발생할 수 있는데, $exp$ 를 씌우기 전에 $\log$ 함수를 취하는 log softmax를 사용하여 해결한다.
그러나 이런 이슈들은 로우레벨을 직접 코딩한다면 중요하게 고려해야겠지만, 그렇지 않다면 대부분 훌륭한 라이브러리들이 해결해준다.

Poor Conditioning

Conditioning은 입력값의 작은 변화에 함숫값이 얼마나 급격하게 변하는지에 대한 지표다. 함수$f(\boldsymbol{x})$에 대하여 $f(\boldsymbol{x}) = \boldsymbol{A}^{-1}\boldsymbol{x}$이고, $\boldsymbol{A}$는 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ 이고 eigenvalue decomposition 을 갖는다고 하자. 이때 condition number(조건수)은 다음과 같다.

이것은 가장 큰 고유값과 가장 작은 고유값의 비율이다. 이 값이 크면 역행렬은 입력의 오차에 민감하다. 민감도는 행렬 고유의 특성이지, 역행렬과정에서 생기는 반올림 오차가 아니다. Poorly conditioned matrix는 역행렬을 곱할때 작은 오차도 크게 만든다. 실제로 역행렬 프로세스에서 발생하는 수치 오차때문에 이 오차는 더 복잡해진다.

Gradient-Based Optimization

대부분의 딥러닝 알고리즘은 최적화를 포함한다. 최적화는 특정 함수 $f(\boldsymbol{x})$를 최대 또는 최소로 만드는 $\boldsymbol{x}$를 찾는 것이다. 대체로 $f(\boldsymbol{x})$를 최소화 하는 방향으로 문제를 정의해서 푼다. $f(\boldsymbol{x})$를 최대화 하는 것은 $-f(\boldsymbol{x})$를 최소화 하는 것과 같기 때문이다.
$f(\boldsymbol{x})$를 objective fucntion 또는 criterion이라고 한다. 이를 최소화 시켜야 할때는 $f(\boldsymbol{x})$를 cost function, loss function, error function 등으로 부른다.
$f(\boldsymbol{x})$를 최적화(최소화 또는 최대화)하는 값을 표기할 때 $\ast$를 이용한다. 예를 들어, 이다.
실수 영역에서 정의된 함수 $y = f(x)$를 가정하자. 이 함수의 미분은 $f’(x)$ 또는 $\frac{dy}{dx}$로 나타낸다. $f’(x)$는 점 $x$에서 $f(x)$의 기울기다. 또는, $x$의 작은 변화에 대한 함숫값의 변화다. $f(x+\epsilon) \approx f(x) + \epsilon f’(x)$
미분은 입력에 대한 출력의 변화를 나타내주므로 함수를 최적화 할때 유용하다. 특정 함수를 최대/최소로 만들기 위해 입력을 줄여야할지 키워야할지에 대한 정보를 제공해주기 때문이다. 이를 gradient descent라고 부른다. 그림 1에 그 예시가 나와있다.

DBL-04-01 그림 1 : Gradient descent. 함수의 최솟값을 찾기 위해 미분을 이용한다.

$f’(x)=0$ 일때는 움직일 방향에 대한 정보가 없다. 이 점을 critical points, stationary points라고 한다. local minimum (극솟값)은 주변보다 함숫값이 작은 지점이다. 따라서 무한소만큼 움직여도 더이상 $f(x)$ 를 작게 만들 수 없다. local maximum (극댓값)은 주변보다 함숫값이 큰 지점이다. 따라서 무한소만큼 움직여도 더이상 $f(x)$ 를 크게 만들 수 없다. 어떤 critical point는 maxima도, minima도 아니다. 이를 saddle points (안장점)라고 한다. 그림 2에 critical point의 종류가 나와있다.

DBL-04-02 그림 2 : Critical point의 종류

함수 $f(x)$중에 가장 작은 값을 global minimum이라 한다. global minima는 하나일 수도, 여러개일 수도 있다. local minima이면서 global minima는 아닐수도 있다. 딥러닝에서 최적화 하는 함수는 여러개의 (global optima가 아닌) local optima를 갖거나 주변 기울기가 평평해서 미분을 이용해 최적화하기 힘든 saddle point들을 가질 수도 있다. 특히 다차원의 데이터를 다룰때 이런 함수는 최적화 하기 어렵다. 그래서 보통 최솟값/최댓값이 아니더라도 어느 정도 최적화 된 값을 찾는 것에 그친다.
다차원의 입력을 갖는 함수 $f : \mathbb{R}^n \rightarrow \mathbb{R}$를 다룰때 편미분을 사용한다. 편미분$\frac{\partial}{\partial x_i} f(\boldsymbol{x})$은 입력 변수 $\boldsymbol{x}$중에 $x_i$의 변화에 따른 함숫값의 변화를 나타낸다.

DBL-04-03 그림 3 : local optima와 global optima

Directional derivative는 단위벡터 $\boldsymbol{u}$의 방향으로의 기울기다. 함수 $f$ 를 최소화 하기 위해서 우리는 $f$를 가장 빠르게 감소시킬 방향을 찾아야한다.

$\theta$는 gradient와 $\boldsymbol{u}$ 사이의 각이다. $\left\Vert \boldsymbol{u} \right\Vert_{2} = 1$ 이고, $\boldsymbol{u}$에 무관한 텀을 무시하면, $\text{min}_{\boldsymbol{u}} \cos \theta$로 간소화된다.$\boldsymbol{u}$ 가 gradient와 반대 방향일 때 최소가 된다. 이렇게 gradient의 반대방향으로 움직여 함숫값 $f$를 최소화 하는 것을 method of steepest descent, gradient descent라고 한다.Steepest descent는 다음과 같은 방법으로 지점을 이동한다.

$\epsilon$은 양수이고, 한 스텝에 이동할 양을 결정하는 learning rate를 의미한다. 주로 $\epsilon$을 상수로 고정해서 사용한다. 또 다른 방법으로는, 몇몇 $epsilon$의 후보를 이용하여 다음 스텝의 함숫값인 $f(\boldsymbol{x}-\epsilon \nabla_{\boldsymbol{x}}f(\boldsymbol{x}))$를 계산해보고, 그 중 가장 효과적인 (함숫값을 가장 작게 만드는) $\epsilon$ 을 선택하기도 한다. 이 방법을 line search라고 한다.
Steepest descent는 모든 입력 변수에 대해 함수의 기울기가 0인 (0에 근접한), 지점에서 수렴한다. gradient descent 방법은 연속공간에서 다소 제한적이지만, 이산공간에서 조금씩 나아지는 방향으로 함수를 최적화하는 일반적인 방법이다.

Beyond the Gradient: Jacobian and Hessian Matrices

입력과 출력이 모두 벡터인 함수의 모든 편미분을 알고 싶을 때, 이런 편미분을 모두 포함한 것이 Jacobian matrix이다. 함수 $\boldsymbol{f} : \mathbb{R}^m \rightarrow \mathbb{R}^n $ 에서 Jacobian matrix는 $\boldsymbol{J} \in \mathbb{R}^{n \times m}$이고, 행렬의 각 인자는 $J_{i,j} = \frac{\partial}{\partial x_j}f(\boldsymbol{x})_i$ 이다. DBL-04-04 그림 4 : Jacobian matrix

미분의 미분, second derivative를 이용할 때도 있다. 함수 $\boldsymbol{f} : \mathbb{R}^m \rightarrow \mathbb{R} $ 에서 $x_j$의 미분에 대한 $x_i$의 미분은 $\frac{\partial}{\partial x_i \partial x_j}$ 이다. second derivative는 입력의 변화에 따른 일차미분의 변화를 의미한다. Curvature을 측정한다고 볼 수 있다. quadratic function 에 대해 보면, (많은 함수들이 quadratic은 아니지만 국소적으로는 quadratic으로 가정 할수 있다.)
이차 미분값이 0이면 curvature이 없는 직선이다. 함수의 기울기를 1이라 뒀을때, cost function은 $\epsilon$만큼 감소한다.
이차 미분값이 음수면 함수가 위로 볼록이므로 cost function이 $\epsilon$보다 많이 감소한다.
이차 미분값이 양수면 함수가 아래로 볼록이므로 cost function이 $\epsilon$보다 적게 감소한다.
그림 5에 일차미분(dash line)을 사용했을 때 예측되는 cost function 감소량과 실제 quadratic function의 curvature이 나타나있다. DBL-04-05 그림 5 : The second derivative determines the curvature of a function.

함수가 다변수를 입력으로 받는다면, 각 변수의 조합마다 이차미분이 필요하다. 이를 나타낸 행렬이 Hessian matrix다. Hessian matrix $\boldsymbol{H}(f)(\boldsymbol{x})$는 아래와 같이 정의된다.

이차 편미분이 연속이면 미분연산자의 순서가 바뀌어도 같으니까, $i,j$의 순서가 바뀌어도 값이 같은 symmetric matrix다. 딥러닝에서 다루는 함수의 대부분은 Hessian matrix는 symmetric하다. 실수이면서 symmetric한 행렬이기 때문에 이를 실수 eigenvalues와 orthogonal basis eigenvector로 분해할 수 있다.
$\boldsymbol{d}^{\top}\boldsymbol{Hd}$에서 단위벡터 $\boldsymbol{d}$가 이차미분의 방향을 나타낸다. $\boldsymbol{d}$가 $\boldsymbol{H}$의 eigenvector일때 이차 미분값은 상응하는 eigenvalue가 된다.
이것과 second-order Taylor series approximation를 이용하여 포인트 $\boldsymbol{x}^{(0)}$ 에서의 gradient descent step을 예측할 수 있다.

$\boldsymbol{g}$는 $\boldsymbol{x}^{(0)}$에서의 gradient이다. 만약 learning rate로 $\epsilon$을 사용하면, 새로운 포인트 $\boldsymbol{x}$는 $\boldsymbol{x}^{(0)}-\epsilon \boldsymbol{g}$가 된다. 위의 식에 대입해보면 아래의 식을 얻을 수 있다.

여기서 $f(\boldsymbol{x}^{(0)}$는 원래 포인트에서의 함숫값, $\epsilon \boldsymbol{g}^{\top} \boldsymbol{g}$는 함수의 기울기를 이용한 cost 감소, $\frac{1}{2} \epsilon^2 \boldsymbol{g}^{\top} \boldsymbol{H} \boldsymbol{g}$가 함수의 curvature을 이용한 조정값이다. 만약 $\boldsymbol{g}^{\top} \boldsymbol{H} \boldsymbol{g}$ 값이 너무 크다면 gradient descent 는 함수를 최소화 하지 못하고 오히려 값을 키울 것이다. 만약 $\boldsymbol{g}^{\top} \boldsymbol{H} \boldsymbol{g}$이 0 이하라면 cost function의 값이 감소할 것이다. 테일러 시리즈가 큰 $\epsilon$ 값에 대해서는 정확하지 않기 때문에 이럴땐 실험적으로 $\epsilon$를 정한다. $\boldsymbol{g}^{\top} \boldsymbol{H} \boldsymbol{g}$값이 양수일때 step size를 정하기 위해 아래의 수식을 따른다.

최악의 경우엔 $\boldsymbol{g}$가 가장 큰 eigenvalue $\lambda_{max}$와 상응하는 $\boldsymbol{H}$의 eigenvector의 방향과 일치하는 경우다. 이때 step size 는 $\frac{1}{\lambda_{max}}$이다. 이렇게 이차 미분과 Hessian을 이용하여 learning rate의 크기를 정할 수 있다.

Hessian을 이용하면 critical point(기울기가 0인 지점)가 local maximum, local minimum, saddle point중 어떤 것인지 알 수 있다. 만약 Hessian matrix가 positive definite (모든 eigenvalue가 양수)면 local minimum이다. 만약 Hessian matrix가 negative definite (모든 eigenvalue가 음수)면 local maximum이다. 하나 이상의 eigenvalue가 양수이면서 하나 이상의 eigenvalue 가 음수면 한방향으로는 local minimum이면서 또 다른방향으로는 local maximum이다. 그림 6에 이런 경우가 그려져 있다.

DBL-04-06 그림 6 : positive curvature과 negative curvature이 모두 있는 saddle point

다변수 입력 함수에서, 하나의 점에서 각 방향으로 서로 다른 이차미분이 존재한다. Hessian의 condition number가 크면 gradient descent는 효과가 썩 좋진 않다. 한 방향($\lambda_{max}$에 대응하는 eigenvector방향)으로는 급격하게 변하고, 다른 방향($\lambda_{min}$에 대응하는 eigenvector방향)으로는 조금 변하기때문이다. 단순한 gradient descent는 이런 부분을 반영하지 못한다. 또한 적절한 step size를 정하는 것도 힘들다. 그림 7에 이런 경우가 나와있다.

DBL-04-07 그림 7 : Hessian matrix의 curvature을 충분히 반영하지 못한 gradient descent

이런 이슈를 해결하는 방법중 하나가 Newton’s method다. Hessian matrix의 정보를 이용하여 탐색하는데, Newton’s method는 second-order Taylor series expansion을 이용하여 $\boldsymbol{x}^{(0)}$ 근처의 $f(\boldsymbol{x})$를 근사한다.

Critical point(기울기가 0인 점)으로 위 식을 풀면 아래와 같은 식을 얻는다.

함수 $f$가 positive definite quadratic 이면 Newton’s method는 위 식을 이용해서 한번에 minimum으로 갈 수 있다. 그러나 현실적으로 $f$는 국소적으로 positive definite quadratic이고 전체적으로는 아니므로, 여러번 반복해야 한다. 이를 이용해 gradient descent보다 더 빠르게 critical point로 도달할 수 있다.그러나 8장 2.3 섹션에서 다루겠지만, saddle point에서는 오히려 안좋을 수 있다. critical point가 minimum일때, (Hessian의 모든 eigenvalue가 양수인) 그 근처에서만 효과적이다.
Gradient만을 이용하는 gradient descent같은 방법을 first-order optimization algorithms라고 하고, Newton’s method처럼 Hessian matrix를 이용하는 것을 second-orderoptimization algorithms라고 한다.

딥러닝에서 함수에 제약을 걸어둠으로써 성능을 보장하기도 하는데, 그 일례가 Lipschitz continuity다. Lipschitz continuous function은 아래와같이 변화율이 Lipschitz constant $\boldsymbol{\mathcal{L}}$ 에 의해 제한되는 함수다.

이 특성은 입력의 변화가 작을 때 함수의 출력의 변화도 작게 만들어준다. Lipschitz continuity는 약한 제약이고, 많은 딥러닝 알고리즘이 약간의 변형으로 이 연속성을 적용하고 있다.

가장 성공적인 최적화 알고리즘은 아마 convex optimization일 것이다. convex optimization은 강한 제약들을 이용하여 더 많은 성능 보장을 한다. 이 알고리즘은 오직 convex function에서만 적용가능한데, convex function은 모든 지점에서 Hessian이 positive semidefinite (eigenvalue가 모두 0 이상)이다. 이러한 함수는 saddle point가 없고 local minima가 global minima이기 때문에 최적화가 잘 된다. 그러나 딥러닝을 모두 이러한 함수로 표현하기는 어렵고, 일부 알고리즘에서 서브루틴으로 적용한다. convex optimization에서 나온 아이디어는 딥러닝의 convergence를 증명하는데 유용하게 사용된다. 그러나 일반적으로 딥러닝에서는 크게 중요하게 다뤄지지는 않는다.

Constrained Optimization

함수를 최적화 할때, 모든 $\boldsymbol{x}$에 대해서 최적화 하는 것이 아니라, 특정 집합 $\mathbb{S}$에 속하는 $\boldsymbol{x}$에 대해서 최적화 할 때가 있다. 이를 constrained optimization이라고 하고, $\mathbb{S}$를 feasible points라고 한다. 예를들면, norm constraint인 $\left\Vert \boldsymbol{x} \right\Vert \leq 1$ 와 같은 조건 내에서의 최적화이다.
constrained optimization의 간단한 방법중 하나는 제약조건을 고려하여 gradient descent를 수정하는 것이다. step size $\epsilon$을 정하고 gradient descent step을 만든 후, 결과가 다시 $\mathbb{S}$로 돌아오게끔 사영(projection)해주면 된다.
좀 더 복잡한 방법은, unconstrained optimization문제를 constrained optimization 문제로 변환하는 것이다. 예를 들면, 함수 $f(\boldsymbol{x})$를 $\boldsymbol{x} \in \mathbb{R}^2$에 대해 $\boldsymbol{x}$가 단위 $L^2$ norm을 갖도록 제한조건을 거는 경우다. 이럴 때, $g(\theta) = f([\cos \theta, \sin \theta]^{\top})$를 각각 $\theta$에 대해 최적화하는 문제로 바꿀 수 있다. 그리고 $\boldsymbol{x} = [\cos \theta, \sin \theta]$를 반환하면 된다.

Karush–Kuhn–Tucker (KKT)는 매우 일반적인 constrained optimization의 일종이다. KKT와 함께, generalized Lagrangian, generalized Lagrangefunction를 다룬다. Lagrangian을 정의하기 위해서 먼저 $\mathbb{S}$를 등식과 부등식으로 정의해야 한다. 으로 정의하고, $g^{(i)}$의 텀을 equality constraints, 의 $h^{(j)}$텀을 inequality constraints라고 한다. 각각의 constraint를 위해 KKT multiplier 이라고 불리는 새로운 변수 $\lambda_i, \alpha_j$를 사용한다. generalized Lagrangian은 아래와 같이 정의된다.

generalized Lagrangian의 unconstrained optimization을 이용하여 constrained optimization을 풀 수 있다. 적어도 하나의 가능한 포인트가 존재하고 $f(\boldsymbol{x})$가 $\infty$를 허용하지 않는다면, $\underset{\boldsymbol{x}}{\text{min}} \ \underset{\boldsymbol{\lambda}}{\text{max}} \ \underset{\boldsymbol{\alpha},\boldsymbol{\alpha}\geq 0}{\text{max}}\ L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\alpha})$ 은 $\underset{\boldsymbol{x} \in \mathbb{S}}{\text{min}} f(\boldsymbol{x})$와 동일한 최적함수와 최적 포인트 $\boldsymbol{x}$를 갖는다. Constraints를 만족시킬 땐,

Constraint에 어긋나면,

이러한 특성은 infeasible point는 optimal point가 될 수 없다는 것을 보장하면서 feasible point인 원함수의 optimal point는 그대로 유지한다.

부등식 constraints는 좀더 살펴볼만 하다. $h^{(i)}(\boldsymbol{x}^*)=0$ 일 때 $h^{(i)}(\boldsymbol{x})$가 active하다고 표현한다. active하지 않은 경우의 solution은 적어도 constraint가 없을 때의 local solution과 같다. 왜냐하면 $h^{(i)}(\boldsymbol{x})$가 음수인 경우에 $\underset{\boldsymbol{x}}{\text{min}} \ \underset{\boldsymbol{\lambda}}{\text{max}} \ \underset{\boldsymbol{\alpha},\boldsymbol{\alpha} \geq 0}{\text{max}} L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\alpha})$에서 $\alpha_i$는 0의 값을 갖기 때문이다.

Example: Linear Least Squares

아래의 식을 최소화 하는 $\boldsymbol{x}$를 찾는다고 가정해보자.

선형대수 알고리즘의 한 방법으로 위 문제를 해결할 수 있지만, gradient-based 최적화 방법을 사용하는 것에 대해 알아볼 것이다. 우선, gradient를 구한다.

이 gradient에 step size $\epsilon$을 곱해서 업데이트 한다.

또는, Newton’s method를 사용하여 업데이트 할 수 있다. 이 경우엔 true function이 quadratic이므로, 한번에 global minima를 구할 수 있다.

위의 함수를 최소화 하되, constraint로 $\boldsymbol{x}^\top\boldsymbol{x} \leq 1$ 을 추가하는 경우엔 Lagrangian을 사용한다.

이제 $\underset{\boldsymbol{x}}{\text{min}}\ \underset{\lambda,\lambda \geq 0}{\text{max}} \ L(\boldsymbol{x},\lambda)$를 풀면 된다. 위 식을 $\boldsymbol{x}$에 대해 미분하고 풀면 아래와 같다.

이때 $\lambda$의 크기는 이 cosntraint를 따라야 한다. gradient ascent를 통해 $\lambda$를 구할 수 있다. ($\lambda$의 기울기가 0이 될때까지 조정한다.)

$\boldsymbol{x}$의 크기가 1보다 크다면, gradient는 양수다. 이를 따라 업데이트 하면 $\lambda$와 Lagrangian은 증가한다. 따라서 원래의 목적인 minimization 측면에서 보면 $\boldsymbol{x}$의 크기는 penalty로 작용하기 때문에 $L(\boldsymbol{x},\lambda)$는 더 작은 $\boldsymbol{x}$를 solution으로 내뱉는 것이다.

DBL-04-08 그림 8 : KKT condition optimization, image from wikipedia. 왼쪽은 f(x)의 optima $\boldsymbol{x}^{\ast}$가 constraint g(x)를 이미 만족하기 때문에 $\lambda$가 0이 되어 constraint가 영향을 미치지 않는 경우. 오른쪽은 기존의 f(x)의 optima가 constraint g(x)를 만족하지 못하기 때문에 strong constraint $\underset{\lambda}{\text{max}}\ L(\boldsymbol{x},\lambda)$에 의해 $\boldsymbol{x}^\ast$가 constraint를 만족하도록 이동한 경우.

위의 문제를 그림8로 다시 생각해보면, $g(\boldsymbol{x}) = \boldsymbol{x}^\top\boldsymbol{x}-1$ 라고 볼 수 있다. 등고선처럼 표현된 것은 $f(\boldsymbol{x})$다. 이 때 우리는 $f(\boldsymbol{x})$를 최소화 하는 것이 목표지만, constraint $g(\boldsymbol{x})$를 반드시 만족시켜야 하는 것이다. 그냥 한번에 gradient descent를 하면 $f(\boldsymbol{x})$의 optima와 $g(\boldsymbol{x})$의 optima의 그저 중간쯤 어딘가에서 gradient가 0가 되어, 학습을 멈추게 된다. 여기서 constraint $g(\boldsymbol{x})$에 의한 패널티를 극대화 하기 위해 $L(\boldsymbol{x},\lambda) = f(\boldsymbol{x}) + \lambda g(\boldsymbol{x})$ 로 설정한 후 $\lambda$는 gradient ascent를 통해 $L(\boldsymbol{x},\lambda)$를 maximize하는 값으로 정해주는 것이다. 즉, $f(\boldsymbol{x})$를 minimize하되, $g(\boldsymbol{x})$의 조건을 반드시 만족하도록 하는 것이다.
만약 $g(\boldsymbol{x})$가 음수로, 조건을 만족하면 $\lambda$는 0이 되어 constraint가 없을 때의 $f(\boldsymbol{x})$ optima를 갖게 만든다 (그림8의 왼쪽 그림처럼).