111강에서 기울기만 써서 할 수 있는 최선에 도달했습니다.
110강 심화 5의 하한과 일치하므로 일차 방법으로는 더 나아갈 수 없습니다.
그 정보가 헤세입니다. 96강 심화 3에서 이미 봤습니다.
| 방법 | 최소점 방향과의 각 |
|---|---|
| 최급강하 | 44.4271^ |
| 헤세 노름 최급강하 | 0.0000^ |
헤세를 쓰면 방향이 정확합니다. 99강 문제 5에서 그 갱신식도 두 줄로 유도했습니다. 기울기의 선형근사를 으로 두면
이 강의는 이 방법이 얼마나 빠른지, 언제 실패하는지, 큰 문제에서 어떻게 쓰는지를 다룹니다. 그리고 이것으로 04단원이 끝납니다.
문제. 과 시작점 을 봅니다.
(1) 뉴턴 걸음 를 구하세요.
(2) 한 걸음 뒤의 위치와 를 구하세요.
(3) 같은 점에서 경사하강법 걸음과 비교하세요.
생각의 실마리. 이차함수는 자기 자신의 이차 근사입니다. 근사가 정확하니 근사의 최소가 진짜 최소입니다.
풀이. (1) 이고 이므로
**검산에서 **이며, 시작점 에서 원점으로 정확히 향합니다.
(2) 이고 입니다.
(3) 검산에서 경사하강법은 걸음 뒤에도 입니다.
이 문제에서 배우는 것: 뉴턴법.
뉴턴법.
두 가지 유도가 있고 둘 다 봤습니다.
| 관점 | 유도 |
|---|---|
| 기울기를 으로 | 99강 문제 5 |
| 이차 모형을 최소화 | 100강 심화 4 |
| 헤세 노름의 최급강하 | 96강 심화 3 |
세 번째가 가장 개념적입니다. 96강에서 최급강하 방향이 노름 선택에 의존한다고 했고, -노름의 최급강하가 였습니다. 로 두면 뉴턴법입니다.
왜 이차함수에서 한 걸음인지도 분명합니다. 100강 문제 5에서 임계점 근처의 함수가 이차형식이라 했는데, 이차함수는 모든 점에서 자기 이차 근사와 같습니다. 근사가 정확하므로 근사의 최소가 참 최소입니다.
학습률이 없다는 점도 특징입니다. 걸음 크기가 헤세에서 자동으로 정해지므로 조율할 것이 없습니다. 다만 문제 4에서 보듯 그것이 언제나 좋은 것은 아닙니다.
바로 확인 1.
확인 1-1. 뉴턴법의 갱신식을 쓰세요.
답. 입니다.
확인 1-2. 이차함수에서 몇 걸음입니까?
답. 한 걸음입니다.
확인 1-3. 96강의 언어로 뉴턴법을 설명하세요.
답. 헤세를 노름으로 삼는 최급강하입니다.
문제. 에서 세 방법의 걸음 수를 세세요.
(1) 뉴턴법
(2) 경사하강법(최적 )
(3) 모멘텀(최적 파라미터)
생각의 실마리. 뉴턴법은 좌표를 바꿔 등고선을 원으로 만듭니다. **원이면 조건수가 **이니 가 무의미해질 것입니다.
풀이. 검산에서
| 뉴턴 | 경사하강법 | 모멘텀 | |
|---|---|---|---|
| 10^ | |||
| 10^ |
뉴턴법은 언제나 한 걸음입니다.
이 문제에서 배우는 것: 아핀 불변성.
로 좌표를 바꿔도 뉴턴 걸음의 궤적이 같습니다. 확인해 봅니다. 새 좌표에서 이므로 97강의 연쇄법칙으로
따라서 뉴턴 걸음이
이고 원래 좌표로 되돌리면
정확히 같은 걸음입니다.
99강 심화 1과 이어집니다. 그때 좌표를 바꾸면 헤세가 가 되고 조건수가 변한다고 했습니다. 경사하강법은 그 변화에 휘둘리는데, 뉴턴법은 휘둘리지 않습니다.
| 방법 | 좌표변환에 |
|---|---|
| 경사하강법 | 의존합니다 |
| 모멘텀 | 의존합니다 |
| Adam | 대각 변환에만 불변 |
| 뉴턴법 | 완전히 불변 |
셋째 줄이 Adam의 위치를 설명합니다. 성분별 척도 조정이므로 대각행렬로 좌표를 바꾸는 데는 강하지만, 회전에는 약합니다.
91강의 조건수 이야기가 여기서 닫힙니다. 그때 조건수가 크면 계산이 어렵다고 했고, 이 단원 내내 와 싸웠습니다. 뉴턴법은 싸우는 대신 좌표를 바꿔 문제를 없앱니다.
바로 확인 2.
확인 2-1. 뉴턴법의 걸음 수가 에 의존합니까?
답. 이차함수에서는 의존하지 않고 언제나 한 걸음입니다.
확인 2-2. 아핀 불변성을 쓰세요.
답. 좌표를 선형변환해도 궤적이 같습니다.
확인 2-3. Adam은 어떤 변환에 불변입니까?
답. 대각행렬 변환에만 불변입니다.
문제. 를 에서 시작합니다.
(1) 국소 최소 를 고정밀로 구하세요.
(2) 오차 를 여섯 걸음 적으세요.
(3) 을 계산하세요.
생각의 실마리. 이차함수가 아니면 한 걸음에 끝나지 않습니다. 그래도 매우 빠를 것입니다.
풀이. (1) 검산에서 이고 입니다.
(2)와 (3) 검산에서
| x_ | e_ | e_{k+1}/e_{k}^ | |
|---|---|---|---|
| 6.049231\times10^ | |||
| 1.974231\times10^ | |||
| 3.183081\times10^ | |||
| 1.047900\times10^ | |||
| 1.195085\times10^ | |||
| 1.557199\times10^ |
비가 으로 수렴합니다. 검산의 이론값
과 정확히 맞습니다.
이 문제에서 배우는 것: 이차 수렴.
이차 수렴 정리. 가 이고 에서 가 가역이며 가 립시츠이면, 이 충분히 가까울 때
입니다.
오차의 자릿수가 매 걸음 두 배가 됩니다. 검산의 지수를 보면
뒤로 갈수록 급격합니다. 에서 로 한 걸음에 여섯 자릿수를 벌었습니다.
선형 수렴과 비교하면 차원이 다릅니다.
| 수렴 | 오차 |
|---|---|
| 선형 | |
| 이차 | 10^{-1},10^{-2},10^{-4},10^{-8},10^ |
자리 정확도에 이차 수렴은 다섯 걸음이면 되고, 선형 수렴은 일 때 걸음이 필요합니다.
"충분히 가까울 때"라는 조건이 정리에 붙어 있습니다. 멀리서 시작하면 보장되지 않으며, 문제 4에서 그 실패를 봅니다.
초기 걸음의 비가 작은 것도 설명됩니다. 에서 였다가 로 올라갔는데, 멀리 있을 때는 가 다른 값이라 상수가 다릅니다. 가까워지면서 이론값으로 수렴합니다.
바로 확인 3.
확인 3-1. 이차 수렴의 정의를 쓰세요.
답. 입니다.
확인 3-2. 오차의 자릿수가 어떻게 변합니까?
답. 매 걸음 두 배가 됩니다.
확인 3-3. 정리에 붙은 조건을 쓰세요.
답. 헤세가 가역이고 립시츠이며 초기점이 충분히 가까워야 합니다.
문제. 같은 함수를 여러 점에서 시작합니다.
(1) 에서 한 걸음을 계산하세요.
(2) 각 점의 부호를 확인하세요.
(3) 가 늘었는지 줄었는지 보세요.
생각의 실마리. 뉴턴 걸음은 이차 모형의 최소를 향합니다. 모형이 위로 볼록하지 않으면 그 최소가 최소가 아닙니다.
풀이. 검산에서
| 시작 | 한 걸음 뒤 | 변화 | |
|---|---|---|---|
인 세 점에서 모두 가 늘었습니다.
이 문제에서 배우는 것: 헤세의 정치성이 필요합니다.
하강 조건을 확인해 보면 이유가 분명합니다. 109강에서 가 하강 방향이려면 이어야 했습니다.
이면 이라 이 값이 음수입니다. 그런데 가 부정부호이면 부호가 보장되지 않습니다.
실패의 종류를 정리합니다.
| 상황 | 문제 |
|---|---|
| (오목) | 최대점으로 갑니다 |
| 부정부호 | 안장으로 갈 수 있습니다 |
| 특이 | 걸음이 정의되지 않습니다 |
| 거의 특이 | 걸음이 지나치게 큽니다 |
넷째 줄이 검산에서 확인됩니다. 인 곳이 이며, 그 근처에서 걸음이 발산합니다.
101강 문제 5와 합치면 심각합니다. 고차원에서 임계점은 대개 안장이므로 헤세가 부정부호인 영역이 넓습니다. 순수한 뉴턴법은 안장으로 수렴할 수 있습니다.
세 가지 대책이 있습니다.
| 대책 | 내용 |
|---|---|
| 감쇠 뉴턴법 | 직선탐색으로 걸음을 줄입니다 |
| 수정 헤세 | 로 정치로 만듭니다 |
| 신뢰영역 | 걸음 크기를 직접 제한합니다 |
둘째 줄이 레벤버그-마쿼트입니다. 가 크면 라 경사하강법에 가까워지고, 작으면 뉴턴법에 가까워집니다.
두 방법을 잇는 연속적인 다리이며, 를 상황에 맞게 조절합니다.
셋째 줄은 100강 심화 4에서 봤습니다. 모형을 믿을 만한 반경 안에서만 최소화하며, 부정부호 헤세여도 제약 덕분에 해가 존재합니다.
바로 확인 4.
확인 4-1. 뉴턴 걸음이 하강 방향일 조건을 쓰세요.
답. 이어야 합니다.
확인 4-2. 가 거의 특이하면 무엇이 문제입니까?
답. 걸음이 지나치게 커집니다.
확인 4-3. 레벤버그-마쿼트의 걸음을 쓰세요.
답. 입니다.
문제. 인 문제에서 를 풉니다.
(1) 켤레기울기법으로 반복해 풀어 보세요.
(2) 반복 횟수에 따른 잔차와 상대 오차를 보세요.
(3) 직접 풀이와 비용을 비교하세요.
생각의 실마리. 99강 심화 4에서 를 만들지 않고 만 계산할 수 있다고 했습니다. 그것만으로 선형계를 풀 수 있으면 됩니다.
풀이. 검산에서 조건수가 이고
| CG 반복 | 잔차 노름 | 해의 상대 오차 |
|---|---|---|
| 9.0262\times10^ | 4.441967\times10^ | |
| 3.0756\times10^ | 1.348090\times10^ | |
| 3.3254\times10^ | 1.322708\times10^ | |
| 2.6473\times10^ | 1.151784\times10^ | |
| 1.7461\times10^ | 7.714740\times10^ |
(3) 직접 풀이는 규모인데 CG 회는 행렬-벡터곱 번입니다.
이 문제에서 배우는 것: 절단 뉴턴법.
절단 뉴턴법. 뉴턴 방정식 를 반복법으로 근사적으로 풀고, 정확도를 상황에 맞게 조절합니다.
세 가지 이득이 있습니다.
| 이득 | 내용 |
|---|---|
| 를 저장하지 않습니다 | 만 필요합니다 |
| 정확히 풀지 않아도 됩니다 | 근사 방향도 좋습니다 |
| 조기 종료가 안전합니다 | CG 중간 해도 하강 방향입니다 |
셋째 줄이 미묘하고 중요합니다. CG는 일 때 매 반복의 해가 하강 방향을 유지합니다. 음의 곡률을 만나면 그 자리에서 멈추고 그때까지의 방향을 쓰면 되므로, 문제 4의 실패를 자연스럽게 피합니다.
109강 문제 3의 표를 다시 봅니다. 방향이 도 벗어나도 감소율의 가 남으므로, 근사 뉴턴 방향으로도 대부분의 이득을 얻습니다.
준뉴턴법은 다른 접근입니다. 헤세를 계산하지 않고 기울기의 변화에서 추정합니다.
할선 조건이며 98강의 야코비 근사와 같은 발상입니다. BFGS는 이를 만족하는 근사를 랭크 갱신으로 유지합니다.
L-BFGS는 최근 몇 걸음만 저장합니다. 개를 기억하면 저장이 이고 곱셈이 이라, 이 수백만이어도 씁니다.
방법들의 자리를 정리합니다.
| 방법 | 저장 | 한 걸음 비용 | 의 규모 |
|---|---|---|---|
| 뉴턴법 | 10^ | ||
| BFGS | 10^ | ||
| L-BFGS | 10^ | ||
| 절단 뉴턴 | CG 반복 | 10^ | |
| 경사하강 계열 | 10^ |
딥러닝은 마지막 줄입니다. 파라미터가 수십억이라 이차 정보를 쓸 여유가 없고, 게다가 확률적 환경이라 헤세 추정 자체가 잡음에 취약합니다.
바로 확인 5.
확인 5-1. 절단 뉴턴법이 필요로 하는 연산을 쓰세요.
답. 곱만 있으면 됩니다.
확인 5-2. CG가 음의 곡률을 만나면 어떻게 합니까?
답. 그 자리에서 멈추고 그때까지의 방향을 씁니다.
확인 5-3. 준뉴턴법의 할선 조건을 쓰세요.
답. 입니다.
| 항목 | 내용 |
|---|---|
| 뉴턴 걸음 | |
| 세 가지 유도 | 기울기 선형화, 이차 모형 최소화, -노름 최급강하 |
| 이차함수 | 한 걸음 |
| 일반 함수 | 국소적으로 이차 수렴 |
| 아핀 불변 | 좌표변환에 궤적이 같습니다 |
| 방법 | 걸음 수 | 한 걸음 비용 |
|---|---|---|
| 경사하강법 | ||
| 모멘텀 | ||
| 뉴턴법 | 국소 | |
| L-BFGS | 중간 | |
| 절단 뉴턴 | 중간 | CG |
| 실패 | 대책 |
|---|---|
| 수정 헤세 | |
| 멀리서 시작 | 직선탐색이나 신뢰영역 |
| 특이 | 정규화나 유사역행렬 |
| 이 큼 | 와 CG |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 어디서나 하강한다고 봅니다 | 이 필요합니다 |
| 전역 수렴을 기대합니다 | 국소 정리입니다 |
| 를 명시적으로 만듭니다 | 면 됩니다 |
| 학습률이 없다고 안심합니다 | 걸음이 너무 클 수 있습니다 |
문제 6. 뉴턴법의 갱신식을 쓰세요.
답. 입니다.
문제 7. 이차함수에서 몇 걸음입니까?
답. 한 걸음입니다.
문제 8. 아핀 불변성을 쓰세요.
답. 좌표를 선형변환해도 궤적이 같습니다.
문제 9. 이차 수렴의 정의를 쓰세요.
답. 입니다.
문제 10. 한 변수에서 뉴턴법의 이차 수렴 상수를 쓰세요.
답. 입니다.
문제 11. 뉴턴 걸음이 하강 방향일 조건을 쓰세요.
답. 입니다.
문제 12. 인 점에서 무슨 일이 생깁니까?
답. 최대점 방향으로 가서 가 늘어납니다.
문제 13. 레벤버그-마쿼트의 걸음을 쓰고 두 극단을 설명하세요.
답. 이며 가 크면 경사하강법, 작으면 뉴턴법입니다.
문제 14. 준뉴턴법의 할선 조건을 쓰세요.
답. 입니다.
문제 15. L-BFGS의 저장 비용을 쓰세요.
답. 최근 걸음만 저장해 입니다.
문제 16. 절단 뉴턴법이 필요로 하는 연산을 쓰세요.
답. 곱입니다.
문제 17. 를 헤세 없이 계산하는 식을 쓰세요.
답. 입니다.
문제 18. 딥러닝이 이차 방법을 잘 쓰지 않는 이유를 쓰세요.
답. 파라미터가 수십억이고 확률적 환경이라 헤세 추정이 잡음에 취약하기 때문입니다.
심화 1. 이차 수렴을 증명하세요.
한 변수에서 증명하고 다변수로 옮깁니다. 가 이고 이라 합니다.
뉴턴 갱신을 씁니다.
를 둘레로 전개합니다. 54강의 테일러 정리로 와 사이의 가 있어
여기서 입니다. 대입하면
이므로 첫 항이 거의 상쇄되고
검산의 이론값이 이것입니다. 에서 이고 이므로
검산의 비가 정확히 이 값으로 수렴합니다.
증명이 말해 주는 것이 셋 있습니다.
| 관찰 | 뜻 |
|---|---|
| 가 분모 | 헤세가 특이하면 상수가 커집니다 |
| 가 분자 | 곡률 변화가 심하면 느립니다 |
| e_{k}^ | 가까울 때만 유효합니다 |
셋째 줄이 "국소"의 근거입니다. 가 크면 가 되어 오히려 멀어질 수 있습니다.
다변수에서도 같은 구조입니다. 자리에 헤세의 립시츠 상수가 들어가고, 자리에 가 들어갑니다.
여기서 은 헤세의 립시츠 상수이고 는 의 최소 고유값입니다.
심화 2. 감쇠 뉴턴법으로 전역 수렴을 만드세요.
문제 4에서 순수한 뉴턴법이 멀리서 실패했습니다. 걸음 크기를 조절하면 고쳐집니다.
를 직선탐색으로 정합니다. 역추적 직선탐색이 표준입니다.
역추적 직선탐색. 에서 시작해 다음 조건이 만족될 때까지 로 줄입니다.
아르미호 조건이라 하며 , 을 씁니다. **"예측된 감소의 최소 배는 실제로 감소해야 한다"**는 뜻입니다.
두 단계 거동이 나타납니다.
| 단계 | t_ | 수렴 |
|---|---|---|
| 감쇠 단계 | 선형 | |
| 이차 단계 | 이차 |
멀리 있을 때는 걸음을 줄여 안전하게 접근하고, 충분히 가까워지면 이 조건을 만족해 순수 뉴턴법이 됩니다.
이 여전히 필요합니다. 부정부호이면 가 하강 방향이 아니라 어떤 로도 조건을 만족할 수 없습니다. 그래서 수정 헤세를 함께 씁니다.
를 고르는 방법이 여럿 있습니다.
| 방법 | 내용 |
|---|---|
| 고정 | 단순하지만 조율이 필요합니다 |
| 콜레스키 실패 시 증가 | 분해가 안 되면 키웁니다 |
| 고유값 수정 | 음수 고유값을 뒤집습니다 |
| 신뢰영역 | 가 자동으로 정해집니다 |
넷째 줄이 가장 우아합니다. 100강 심화 4에서 본 신뢰영역 부분문제의 해가 꼴이고, 가 반경 에서 자동으로 결정됩니다.
심화 3. 가우스-뉴턴법과 최소제곱의 구조를 이용하세요.
손실이 잔차의 제곱합이면 특별한 구조가 있습니다.
기울기와 헤세를 계산합니다. 를 의 야코비라 하면
둘째 항이 문제입니다. 각 잔차의 헤세를 다 계산해야 하고 비쌉니다.
가우스-뉴턴법은 그 항을 버립니다.
두 경우에 정당합니다. 잔차가 작거나() 모형이 거의 선형이면() 버린 항이 작습니다.
82강의 정규방정식과 같은 형태입니다. 실제로 이는 선형화된 최소제곱 문제
의 해이며, 91강에서 경고한 대로 를 만들지 말고 QR로 풀어야 합니다.
이득이 둘 있습니다.
| 이득 | 내용 |
|---|---|
| 이계 미분이 필요 없습니다 | 만 있으면 됩니다 |
| 항상 준정치라 하강 방향입니다 |
둘째 줄이 문제 4의 실패를 피합니다. 87강에서 가 언제나 준정치라 했고, 그래서 가우스-뉴턴 방향은 하강 방향이 보장됩니다.
레벤버그-마쿼트가 여기에 정규화를 더한 것입니다.
의 계수가 부족해도 안전하며, 393강의 번들 조정에서 표준으로 씁니다.
심화 4. 자연경사법과 정보기하를 예고하세요.
96강 심화 3에서 최급강하가 노름에 의존한다고 했습니다. 뉴턴법은 를 골랐습니다. 다른 선택도 있습니다.
파라미터가 확률분포를 정하는 경우를 봅니다.
파라미터 공간의 유클리드 거리가 의미가 있는지를 물어야 합니다. 를 조금 바꿨을 때 분포가 얼마나 변하는지는 파라미터화 방식에 따라 다릅니다.
분포 사이의 거리로 재는 것이 자연스럽습니다. 203강의 KL 발산을 쓰면
여기서 가 피셔 정보행렬입니다. 이차 근사의 헤세 자리에 있으며, 이 노름에서의 최급강하가
자연경사법입니다.
| 방법 | 노름 | 불변성 |
|---|---|---|
| 경사하강법 | 없음 | |
| 뉴턴법 | 아핀 변환 | |
| 자연경사법 | 재매개화 |
셋째 줄의 불변성이 특별합니다. 같은 분포족을 다른 방식으로 매개화해도 궤적이 같습니다. 문제 2에서 본 뉴턴법의 아핀 불변성을 비선형 재매개화로 넓힌 것입니다.
102강 심화 3의 가우스 정리와 이어집니다. 그때 곡면 안에서 잰 거리가 본질적이라 했는데, 여기서는 분포들이 이루는 다양체 안에서 잰 거리입니다.
236강에서 정면으로 다룹니다. 강화학습의 TRPO와 PPO가 이 발상 위에 서 있으며, 288강과 289강에서 봅니다.
심화 5. 이차 정보를 쓰는 다른 방법들을 정리하세요.
전체 헤세를 쓰는 것과 전혀 쓰지 않는 것 사이에 여러 단계가 있습니다.
첫째, 대각 근사입니다. 111강의 Adam이 여기 속합니다.
**저장과 계산이 **이라 가장 쌉니다. 다만 회전에 약하고, 성분 사이의 상관을 무시합니다.
둘째, 블록 대각 근사입니다. 층별로 블록을 잡으면 층 안의 상관은 잡고 층 사이는 무시합니다.
K-FAC이 대표적이며, 각 블록을 다시 크로네커 곱으로 근사해 비용을 더 줄입니다.
셋째, 저계수 근사입니다. 88강의 저계수 근사를 헤세에 적용합니다.
큰 고유값 몇 개만 잡습니다. 101강 문제 5에서 본 대로 신경망의 헤세는 큰 고유값이 소수이고 나머지가 근처라, 이 근사가 잘 맞습니다.
넷째, 헤세-벡터 곱만 쓰기입니다. 문제 5의 절단 뉴턴법입니다.
다섯째, 준뉴턴 근사입니다. 기울기 이력에서 추정합니다.
정리하면 다음과 같습니다.
| 근사 | 저장 | 잡는 정보 |
|---|---|---|
| 대각 | 성분별 척도 | |
| 블록 대각 | 층 안의 상관 | |
| 저계수 | 주요 곡률 방향 | |
| L-BFGS | 최근 궤적의 곡률 | |
| 전체 | 전부 |
어느 정도까지 쓸지가 과 예산이 정합니다. 그리고 확률적 환경에서는 정확한 헤세가 오히려 해로울 수 있습니다. 잡음이 섞인 헤세 추정으로 역행렬을 취하면 오차가 증폭되기 때문이며, 91강의 조건수 경고가 여기서도 적용됩니다.
심화 6. 04단원을 정리하고 05단원을 예고하세요.
04단원은 와 싸우는 이야기였습니다.
| 강의 | 한 일 |
|---|---|
| 107 | 볼록성이 국소를 전역으로 만듭니다 |
| 108 | 와 로 정량화합니다 |
| 109 | 알고리즘을 세우고 거동을 봅니다 |
| 110 | 수렴을 증명합니다 |
| 111 | 를 로 줄입니다 |
| 112 | 의존성을 없앱니다 |
한 줄로 요약되는 진전이 있었습니다.
대가는 걸음마다의 비용입니다.
96강 심화 3의 한 문장이 단원 전체를 관통했습니다.
| 방법 | 쓰는 노름 |
|---|---|
| 경사하강법 | |
| Adam | 대각행렬 |
| 뉴턴법 | 헤세 |
| 자연경사법 | 피셔 정보행렬 |
S4의 도구가 계속 쓰였습니다.
| S4 | 쓰인 곳 |
|---|---|
| 86 스펙트럼 정리 | 와 의 정의 |
| 87 양정치성 | 볼록성 판정 |
| 90 노름과 조건수 | 매끄러움 상수 |
| 91 조건수 | 수렴 속도 |
| 82 정규방정식 | 가우스-뉴턴법 |
05단원은 제약을 더합니다.
113강의 라그랑주 승수법이 95강 문제 4의 기하에서 두 줄로 나옵니다. 제약곡선 위를 움직여도 가 늘지 않아야 하고, 그 방향이 에 수직이므로
114강의 KKT 조건이 부등식 제약으로 넓히고, 115강의 쌍대 문제가 어려운 문제를 쉬운 문제로 바꿉니다. 116강은 정규화를 제약으로 읽으며, 라소와 능형회귀가 왜 그런 모양인지 답합니다.
그것을 대신할 조건을 세우는 것이 05단원의 일입니다.
import numpy as np
# --- 문제 1: 이차함수에서 한 걸음 ---------------------------------------
H = np.array([[1.0, 0.0], [0.0, 100.0]])
f = lambda x: 0.5*(x @ H @ x); gf = lambda x: H @ x
x0 = np.array([1.0, 1.0])
print(" f = (x^2+100y^2)/2, 시작 (1,1)")
print(" 뉴턴 걸음 h = -H^{-1} grad f = %s" % np.round(-np.linalg.solve(H, gf(x0)), 6))
xn = x0 - np.linalg.solve(H, gf(x0))
print(" 한 걸음 뒤 x = %s, f = %.1f" % (np.round(xn, 12) + 0.0, f(xn)))
xg = x0.copy()
for _ in range(200): xg = xg - 0.01*gf(xg)
print(" 같은 점에서 GD(eta=1/L) 200 걸음 뒤 f = %.6e" % f(xg))
# f = (x^2+100y^2)/2, 시작 (1,1)
# 뉴턴 걸음 h = -H^{-1} grad f = [-1. -1.]
# 한 걸음 뒤 x = [0. 0.], f = 0.0
# 같은 점에서 GD(eta=1/L) 200 걸음 뒤 f = 8.975277e-03
# --- 문제 2: 조건수와 무관하다 ------------------------------------------
print(" kappa 뉴턴 걸음 GD 걸음 모멘텀 걸음")
for kk in [10.0, 100.0, 10000.0, 1000000.0]:
Hk = np.diag([1.0, kk]); g = lambda z: Hk @ z; fv = lambda z: 0.5*(z @ Hk @ z)
z = np.array([1.0, 1.0]); f0 = fv(z); n0 = 0
while fv(z) > 1e-12*f0 and n0 < 100:
z = z - np.linalg.solve(Hk, g(z)); n0 += 1
z = np.array([1.0, 1.0]); eg = 2.0/(1.0+kk); n1 = 0
while fv(z) > 1e-12*f0 and n1 < 30000000: z = z - eg*g(z); n1 += 1
s = np.sqrt(kk); bb = ((s-1)/(s+1))**2; ee = 4.0/(np.sqrt(kk)+1.0)**2
z = np.array([1.0, 1.0]); v = np.zeros(2); n2 = 0
while fv(z) > 1e-12*f0 and n2 < 30000000:
v = bb*v + g(z); z = z - ee*v; n2 += 1
print(" %9.0f %9d %9d %13d" % (kk, n0, n1, n2))
# kappa 뉴턴 걸음 GD 걸음 모멘텀 걸음
# 10 1 69 27
# 100 1 691 95
# 10000 1 69078 1074
# 1000000 1 6907756 11949
# 뉴턴법은 kappa 가 백만이어도 한 걸음입니다.
# --- 문제 3: 일반 함수에서 이차 수렴 ------------------------------------
fn = lambda x: x**4 - 4*x**2 + 0.3*x
d1 = lambda x: 4*x**3 - 8*x + 0.3
d2 = lambda x: 12*x**2 - 8
xs = 1.4 # 참값을 고정밀로 먼저 구합니다
for _ in range(60): xs = xs - d1(xs)/d2(xs)
print(" f = x^4 - 4x^2 + 0.3x 의 국소 최소 x* = %.15f, f'(x*) = %.3e" % (xs, d1(xs)))
seq = [2.0]
for _ in range(5): seq.append(seq[-1] - d1(seq[-1])/d2(seq[-1]))
print(" k x_k e_k = |x_k - x*| e_{k+1}/e_k^2")
for k in range(len(seq)-1):
ek = abs(seq[k]-xs); ek1 = abs(seq[k+1]-xs)
print(" %4d %+.12f %16.6e %14.4f" % (k, seq[k], ek, ek1/ek**2))
print(" %4d %+.12f %16.6e" % (len(seq)-1, seq[-1], abs(seq[-1]-xs)))
print(" 비가 일정하면 이차 수렴입니다. 이론값 |f'''/(2f'')| = %.4f" % abs(24*xs/(2*d2(xs))))
# f = x^4 - 4x^2 + 0.3x 의 국소 최소 x* = 1.395076887569703, f'(x*) = 1.055e-15
# k x_k e_k = |x_k - x*| e_{k+1}/e_k^2
# 0 +2.000000000000 6.049231e-01 0.5395
# 1 +1.592500000000 1.974231e-01 0.8167
# 2 +1.426907697143 3.183081e-02 1.0342
# 3 +1.396124787611 1.047900e-03 1.0883
# 4 +1.395078082654 1.195085e-06 1.0903
# 5 +1.395076887571 1.557199e-12
# 비가 일정하면 이차 수렴입니다. 이론값 |f'''/(2f'')| = 1.0903
# 오차 지수가 1, 1, 2, 3, 6, 12 로 매 걸음 두 배가 됩니다.
# --- 문제 4: 뉴턴법이 실패하는 경우 -------------------------------------
print(" H 가 음수인 곳에서는 뉴턴 걸음이 위로 갑니다")
print(" 시작 x f''(x) 한 걸음 뒤 f 변화")
for xv in [2.0, 0.5, 0.0, -0.5]:
h = -d1(xv)/d2(xv); x1 = xv + h
print(" %8.1f %+8.2f %+11.6f %+11.6f" % (xv, d2(xv), x1, fn(x1)-fn(xv)))
print(" f'' = 0 인 곳 x = +-sqrt(2/3) = %+.6f 에서는 걸음이 발산합니다" % np.sqrt(2/3))
# H 가 음수인 곳에서는 뉴턴 걸음이 위로 갑니다
# 시작 x f''(x) 한 걸음 뒤 f 변화
# 2.0 +40.00 +1.592500 -3.834894
# 0.5 -5.00 -0.140000 +0.667484
# 0.0 -8.00 +0.037500 +0.005627
# -0.5 -5.00 +0.260000 +0.899670
# f'' = 0 인 곳 x = +-sqrt(2/3) = +0.816497 에서는 걸음이 발산합니다
# f'' < 0 인 세 점에서 모두 f 가 늘었습니다.
# --- 문제 5: 큰 문제에서는 H 를 만들지 않는다 ---------------------------
print(" H v 만으로 켤레기울기법을 돌려 H h = -g 를 풉니다")
rng = np.random.default_rng(20260809)
n = 300
A = rng.standard_normal((n, n)); Hb = A.T @ A/n + 0.05*np.eye(n)
gb = rng.standard_normal(n)
def cg(matvec, b, iters):
x = np.zeros_like(b); r = b - matvec(x); p = r.copy(); rs = r @ r
for _ in range(iters):
Ap = matvec(p); al = rs/(p @ Ap)
x = x + al*p; r = r - al*Ap
rs2 = r @ r; p = r + (rs2/rs)*p; rs = rs2
return x, np.sqrt(rs)
exact = np.linalg.solve(Hb, -gb)
print(" n = %d, 조건수 %.1f" % (n, np.linalg.cond(Hb)))
print(" CG 반복 잔차 노름 해의 상대 오차")
for i in [5, 10, 20, 40, 60]:
s, rn = cg(lambda v: Hb @ v, -gb, i)
print(" %10d %13.4e %14.6e" % (i, rn, np.linalg.norm(s-exact)/np.linalg.norm(exact)))
print(" 직접 풀이는 n^3 = %d 규모, CG 20회는 행렬-벡터곱 20 번입니다" % n**3)
# H v 만으로 켤레기울기법을 돌려 H h = -g 를 풉니다
# n = 300, 조건수 77.4
# CG 반복 잔차 노름 해의 상대 오차
# 5 9.0262e+00 4.441967e-01
# 10 3.0756e+00 1.348090e-01
# 20 3.3254e-01 1.322708e-02
# 40 2.6473e-03 1.151784e-04
# 60 1.7461e-05 7.714740e-07
# 직접 풀이는 n^3 = 27000000 규모, CG 20회는 행렬-벡터곱 20 번입니다
문제 2의 표가 04단원의 결론입니다. 조건수가 백만이어도 뉴턴법은 한 걸음이고, 경사하강법은 만 걸음입니다.
의 크기가 그 저울질의 답을 정합니다. 113강에서 제약이 있는 최적화로 넘어갑니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 뉴턴 걸음 | 이차 모형의 최소를 향합니다 | |
| 아핀 불변 | affine invariant | 좌표변환에 궤적이 같습니다 |
| e_{k+1}\le Ce_{k}^ | 이차 수렴 | 자릿수가 두 배씩 늡니다 |
| 아르미호 조건 | Armijo | 직선탐색의 충분감소 조건입니다 |
| 수정 헤세 | 정치로 만듭니다 | |
| 레벤버그-마쿼트 | Levenberg-Marquardt | 뉴턴과 경사하강을 잇습니다 |
| 가우스-뉴턴 근사 | 이계 항을 버립니다 | |
| BFGS | 준뉴턴 | 할선 조건으로 헤세를 추정합니다 |
| L-BFGS | 제한 메모리 BFGS | 최근 걸음만 저장합니다 |
| 절단 뉴턴법 | truncated Newton | CG로 근사적으로 풉니다 |
| 피셔 정보행렬 | Fisher information | 자연경사법의 노름입니다 |
이것으로 04단원 볼록성과 경사법이 끝납니다. 다음 113강부터 시작하는 05단원 제약이 있는 최적화에서는 실행가능영역이 있는 문제를 다룹니다. 제약이 있으면 이 최적성 조건이 아니며, 95강 문제 4의 기하가 그것을 대신할 조건을 줍니다. 113강의 라그랑주 승수법이 두 줄로 나오고, 116강에서 정규화가 왜 제약인지 답합니다.