Conjugate Gradient

Conjugate Gradient

가파른 하강의 한계를 피하기 위해 Hestenes와 Stiefel이 1951 년경에 Conjugate Gradient (CG)에 대한 아이디어를 제안했습니다. 우리를 괴롭히는 것은 처음에 수행하는 단계가 일반적으로 같은 방향이라는 것입니다. 각 단계에서 최선의 방향을 찾을 수 있다면 훨씬 더 효과적 일 것입니다. 여기서 매우 직관적 인 아이디어는 방향을 일련의 직교 검색 방향으로 분해하려는 것입니다.

n 개의 차원의 방향 벡터이다.

그리고 각 방향에서 정확히 한 걸음을 내딛습니다. 다음은 켤레 기울기의 매우 직관적 인 데모입니다.

RL-Conjugate Gradient의 Jonathan Hui의 이미지
대상 데이터의 차원만큼 CG를 반복 수행하여 최적해를 찾는다. 즉 AX=b에 대한 해를 계산한다고 할 경우 X의 차원에 해당하는 만큼 CG를 반복 수행하여 X값을 얻어낼 수 있다.

수학적으로 말하면 CG(Conjugate Gradient)는?

1) 2 차 방정식의 최적화 문제를 푸는 반복 알고리즘입니다.

비 제약 볼록(Convex)  2 차 문제

여기서 Q는 다음 요구 사항을 충족해야 하는 대칭적이고 명확한 행렬입니다.

대칭 및 한정 행렬의 정의.

2) Ax = b 형식으로 선형 연립 방정식 문제 풀기. 여기서 A는 대칭적이고 한정적입니다. CG는 Ax = b를 푸는 데 가장 널리 사용되는 반복 방법입니다.

다음에는 2 차 방정식을 최적화하기위한 구현과 선형 방정식 시스템의 수치 예제를 소개합니다.

Conjugate Gradient 구현 (최적화를 위해) :

문제를 해결하려면 :

Q가 대칭 및 한정 행렬 인 경우 x와 q는 모두 n 차원입니다.

먼저 x₀의 초기 지점을 선택하고 다음 방향을 업데이트합니다.

위의 함수가 0이면 최소값에 도달합니다. 0이 아니면 다음과 같이 업데이트합니다.

여기서 람다(새로운 학습률)와 d(새로운 방향)는 다음과 같다.

람다는 새로운 학습률이며 다음과 같다.

d는 새로운 방향이며 다음과 같다.

학습률은 d_k 방향에서 f (x)의 최소값을 찾는 것을 목표로합니다.

여기서 감마는 다음과 같다.

이것은 현재 기울기와 마지막 방향을 기반으로 새로운 방향을 계산하는 데 도움이됩니다.

위의 결과는 다음과 같습니다.

그리고 n 개의 직교 방향에 대해 n 번 반복하면 해를 찾을 수 있습니다.

수치 예 (선형 방정식의 경우)

켤레 기울기의 구현은 다음 그래프에서 설명 할 수 있습니다.

여기서 r은 redidual이라고도합니다.

수치 예제를 통해 이를 구현하는 방법을 살펴 보겠습니다. 다음 예제는 이 분야의 유명한 논문에서 발췌 한 것입니다.

1994 년에 작성된 Jonathan Richard Shewchuk의 고통 을주지 않는 Conjugate Gradient Method에 대한 소개 .

이 주제에 대한 Wikipedia 페이지에서도 유사한 예제를 찾을 수 있습니다. 여기에 제시된 솔루션은 원본이며 Matlab에서 수행했습니다.

Ax = b의 다음 선형 시스템을 고려하고 이 시스템에서 CG를 수행합니다.

= b

솔루션에 대한 초기 추측은 다음과 같습니다.

시작하기 전에 생각할 사항 :이 문제에서 n = 2이므로 2 차원에서 작업해야하며 최대 2 번의 반복 작업을 수행해야 함을 예측할 수 있습니다.

첫 번째 반복 : 먼저 초기 지점 p₀ = r₀ = b-Ax₀에서 첫 번째 방향을 계산해 봅시다.

그런 다음 학습률을 계산합니다.

이제 x_1을 계산하여 첫 번째 반복을 완료합니다.

두 번째 반복 : 먼저 잔차를 찾아 방향을 직교 방향으로 업데이트하겠습니다.

그런 다음 다음 방향을 찾기위한 베타를 계산합니다.

그런 다음 방향을 업데이트합니다.

새로운 방향으로 학습률을 계산합니다.

마침내 해결책을 얻었습니다.

 

Conjugate Gradient의 한계

CG는 비선형 프로그래밍 문제를 해결하는 데 강력한 것으로 입증되었지만 다음과 같은 이유로 딥 러닝 연구에는 최선의 선택이 아닙니다.

사유는 CG(Conjugate Gradient)가 전체 데이터 세트의 기울기를 계산하여 업데이트하는 방법을 사용하기 때문입니다. 따라서 데이터 세트가 크면 느리게 실행되며 이는 딥러닝에서 일반적으로 발생될 것으로 예상되는 이슈사항입니다.