TIMESTAMP
@200919 시작~4.1
@200920 4.2~
@200922 완료
- 한정된 숫자의 비트에서 알고리즘이 여전히 작동할까?
- 알고리즘은 보통 실수(real numbers)로 지정되지만, 유한의(finite) 컴퓨터에서는 실수를 구현할 수 없다.
- 입력값의 작은 변화가 출력값에서 큰 변화를 일으킬까?
- 반올림 오류, 노이즈, 측정 오류로 인해 큰 변화가 발생할 수 있다.
- 최상의 입력값을 위한 Iterative search는 어렵다.
단위 벡터 방향에서의 방향도함수(directional derivative)는 함수 의 방향에서의 기울기다.
를 최소화하기 위해서는 가장 빠르게 를 감소시키는 방향을 찾고자 하고, 이때 방향도함수를 사용할 수 있다 (는 와 기울기 사이의 각도)
Steepest descent는 아래와 같은 새로운 지점을 제시한다.
Steepest descent는 기울기의 모든 지점이 0이거나 0에 가까울 때 수렴한다. 여러 경우에서는 이러한 반복적인(iterative) 알고리즘을 하지 않고, 에 대해 을 풀어 바로 critical points로 직행할 수 있다.
비록 gradient descent는 연속적인 공간에서의 최적화로 국한되어 있지만, 더 나은 곳을 향해 반복해서 조금씩 움직인다는 개념은 이산 공간으로 일반화될 수 있다. 이산적인 파라미터들의 목적함수를 증가시키는 것은 hill climbing이라고 한다.
도함수의 도함수를 구해야할 때가 있고, 이를 이계도함수(second derivative)라고 한다.
이계도함수는 입력값이 달라짐에 따라 도함수가 얼마나 변하는지를 나타내는 것으로, gradient step으로 인해 우리가 기대하는 더 나은 결과가 나올지를 기울기를 기반으로 말해준다.
이계도함수는 곡률(curvature)을 측정하는 것으로 생각할 수 있다.
[예시] 이차함수에서의 이계도함수
실제로 많은 함수는 이차함수는 아니지만 국소적으로는 이차함수로 근사할 수 있다
(1) 만약 이계도함수가 0이라면, 곡률이 없고 완전한 직선을 의미한다. 만약 기울기가 1이라면, 기울기의 반대방향으로 크기만큼 이동할 수 있고 이 경우 비용함수는 만큼 감소할 것이다.
(2) 만약 이계도함수가 음수라면, 아래쪽으로 휘어진 형태이므로 비용함수는 보다 크게 감소할 것이다.
(3) 만약 이계도함수가 양수라면, 위쪽으로 휘어진 형태이므로 비용함수는 보다 작게 감소할 것이다.
다차원에서는 한 지점에서 각 방향에 대해 서로 다른 이계도함수가 있다. 이 점의 헤세 행렬의 조건수는 서로 이계도함수가 얼마나 다른지를 측정한다. 헤세 행렬이 poor condition numer을 가질때, gradient descent는 제대로 수행되지 않는다. 이는 한 방향에서는 미분이 빠르게 증가하고 다른 방향에서는 느리게 증가하기 때문이다. Gradient descent는 이러한 미분의 변화를 인지하지 못하기 때문에 미분이 더 오랫동안 음수로 유지되는 방향을 우선적으로 탐색해야한다는 것을 모른다. 또한 적절한 스텝 사이즈를 선택하기가 어렵다. 스텝 사이즈는 최소값을 오버슈팅하거나 양의 곡률이 강한 방향으로 오르지 않도록 충분히 작아야 한다. 이는 보통 스텝 사이즈가 너무 작아서 곡률이 작은 다른 방향으로 상당한 진전을 이루지 못하는 것을 의미한다.
헤세 행렬의 정보로부터 이러한 이슈를 해결할 수 있다. 가장 간단한 방법은 뉴턴의 방법(Newton's method)이다. 뉴턴의 방법은 2차 테일러 급수를 사용하여 근처의 를 근사한다.
이 함수의 critical point에 대해 풀어보면:
근사치를 반복적으로 업데이트하고 근사치의 최소값으로 점프하면 gradient descent보다 critical point로 더 빠르게 도달할 수 있다. 이는 local minimum 근처에서 유용하지만 saddle point 근처에서는 위험하다. 뉴턴의 방법은 근처 critical point가 최소인 경우(헤세 행렬의 모든 고유값이 양수)에만 적절하지만, gradient descent는 saddle points로 끌려가지는 않는다.
- gradient descent처럼 gradient만을 이용하는 최적화 알고리즘을 first-order optimization algorithms라고 부른다.
- 뉴턴의 방법과 같이 헤세 행렬도 사용하는 최적화 알고리즘을 second-order optimization algorithms이라고 한다.
이 책의 대부분의 최적화 알고리즘은 다양한 함수에 적용할 수 있지만 보장할 수는 없다. 딥러닝에 사용되는 함수는 꽤 복잡하기 때문에 딥러닝 알고리즘은 확신을 할 수 없는 경향이 있다. 다른 많은 분야에서 최적화에 대한 지배적인 접근 방식은 제한된 함수군에 대한 최적화 알고리즘을 설계하는 것이다.
딥러닝의 맥락에서는 립시츠 연속(Lipschitz continuous)이거나 립시츠 연속 도함수를 가지는 것으로 제한할 때 몇 개의 보장을 할 수 있다. 립시츠 연속 함수는 변화율이 립시츠 상수 (Lipschitz constant)로 바운드된 함수 이다.
이 속성은 gradient descent와 같은 알고리즘에 의한 입력값의 작은 변화가 출력값의 작은 변화를 가질 것이라는 가정을 정량화할 수 있기 때문에 유용하다. 립시츠 연속성도 상당히 약간 제약 조건이며, 딥러닝의 많은 최적화 문제는 비교적 작은 변경으로 립시츠를 연속적으로 만들 수 있다.
때로는 우리는 가능한 모든 값 외에도 어떤 집합 에서 값들에 대해 의 최대/최소값을 구하고자할 때가 있으며, 이를 contrained optimization이라고 한다. 집합 내에 있는 점 을 feasible points라고 한다.
가장 일반적인 접근 방식은 과 같은 norm 제약을 가하는 것이다.
contrained optimization의 하나의 간단한 접근 방식은 제약 조건을 고려하여 gradient descent를 수정하는 것이다. 스텝 사이즈로 작은 크기의 상수 를 사용한다면, gradient descent를 수행할 수 있고, 이 결과를 다시 로 넣는다.
Karush-Kuhn-Tucker (KKT) 접근 방식은 매우 일반적인 솔루션을 제공한다. KKT 접근을 통해 generalized Lagrangian 혹은 generalized Lagrange function이라는 함수를 도입할 수 있다.
Lagrangian을 정의하기 위해, equations와 inequalities의 측면에서 를 표현해야 한다. 을 개의 함수 와 개의 함수 의 측면에서 표현하여, { and }이 되도록 한다.
와 관련된 equations들을 equality constraints라고 하고 와 관련된 inequalities를 inequality constraints라고 한다.
각 제약에 KKT multipliers인 새로운 변수 와 를 도입하면, generalized Lagrangian은 다음과 같다: