118강 문제 5에서 경사흐름이 나왔습니다.
그때는 안정성 판정의 예시였지만, 이번에는 이것을 최적화 알고리즘 자체로 봅니다.
핵심 관찰은 한 줄입니다. 109강의 경사하강법
을 이항해서 로 나누면 이렇게 됩니다.
왼쪽은 미분의 차분 근사입니다. 즉 경사하강법은 경사흐름을 전진 오일러로 이산화한 것이고, 학습률 는 시간 간격입니다.
이 관점이 왜 값진지는 04단원 전체를 다시 읽으면 보입니다.
| 04단원에서 본 것 | 흐름 관점의 대응 |
|---|---|
| 109강의 제한 | 이산화의 안정성 조건입니다 |
| 110강의 수렴 | 흐름의 지수 감쇠를 걸음 수로 환산한 것입니다 |
| 111강의 모멘텀 | 2계 미분방정식의 감쇠 진동입니다 |
| 112강의 뉴턴법 | 좌표를 바꾼 다른 흐름입니다 |
그리고 놀라운 사실이 하나 나옵니다. 연속시간 경사흐름의 수렴 속도는 조건수와 무관합니다. 조건수의 저주는 흐름이 아니라 이산화에서 옵니다. 이것이 이 강의의 도착점입니다.
문제. , , 을 봅니다.
(1) 경사흐름 의 해석해를 구하세요.
(2) 인 경사하강법을 번 돌린 결과와 시각 의 해석해를 비교하세요.
(3) 둘의 차이가 무엇에 비례하는지 설명하세요.
생각의 실마리. 이므로 흐름은 입니다. 118강 문제 1이 그대로 답입니다.
풀이. (1) 118강의 공식에서
입니다. 가 대각이라 성분이 분리됩니다.
(2) 검산에서 이렇게 됩니다.
| 연속해 e^{-Ht}\mathbf{x}_ | GD | 차이 | |
|---|---|---|---|
| 1.525\times10^ | |||
| 1.356\times10^ | |||
| 5.044\times10^ | |||
| 1.516\times10^ |
소수점 셋째 자리까지 같습니다. 걸음 수 가 아니라 시각 가 같은 지점끼리 비교해야 일치한다는 점이 중요합니다.
(3) 차이는 입니다. 를 절반으로 줄이면 오차도 대략 절반이 됩니다.
이 문제에서 배우는 것: 경사흐름과 전진 오일러.
경사흐름.
각 순간 가장 가파른 내리막 방향으로 움직이는 연속 궤적입니다.
96강에서 가 최속강하 방향이라고 했습니다. 경사흐름은 그 방향을 매 순간 따라가는 곡선입니다.
전진 오일러 이산화.
는 를 시간 간격 로 근사한 것입니다.
를 넣으면 정확히 경사하강법입니다. 따라서 대응이 이렇게 정리됩니다.
| 이산 | 연속 |
|---|---|
| 걸음 번호 | 시각 |
| 학습률 | 시간 간격 |
| 번째 반복 \mathbf{x}_ | |
| 걸음 수 | 흐른 시간 |
오차 크기는 테일러로 나옵니다. 100강의 전개에서
이므로 오일러는 항부터 버립니다. 한 걸음의 오차가 이고, 고정된 시간 까지 번 누적하므로 **전체 오차가 **입니다. 이를 1차 정확도라 부릅니다.
바로 확인 1.
확인 1-1. 경사흐름의 방정식을 쓰세요.
답. 입니다.
확인 1-2. 경사하강법에서 학습률은 흐름의 무엇에 해당합니까?
답. 시간 간격입니다.
확인 1-3. 전진 오일러의 전체 오차 차수를 쓰세요.
답. 이며 1차 정확도입니다.
문제. 문제 1의 흐름을 따라 를 봅니다.
(1) 를 연쇄법칙으로 구하세요.
(2) 부호를 판정하세요.
(3) 여러 시각에서 수치 미분과 비교해 확인하세요.
생각의 실마리. 97강의 다변수 연쇄법칙을 씁니다. 와 의 합성이므로 기울기와 속도의 내적이 됩니다.
풀이. (1) 97강에서
인데 흐름이 이므로 대입하면 이렇게 됩니다.
(2) 제곱 노름이므로 항상 이하입니다. 등호는 일 때뿐입니다.
(3) 검산에서 정확히 일치합니다.
| \lVert\nabla f\rVert^ | 수치 | ||
|---|---|---|---|
여덟 자리까지 부호만 뒤집힌 같은 수입니다.
이 문제에서 배우는 것: 리아푸노프 함수로서의 .
소산 항등식.
경사흐름을 따라 는 결코 증가하지 않습니다.
118강 문제 5에서 이것을 안정성의 근거로 썼습니다. 이번에는 최적화의 보장으로 읽습니다.
이산 세계와 비교하면 차이가 선명합니다.
| 감소 보장 | |
|---|---|
| 경사흐름 | 조건 없이 항상 감소합니다 |
| 경사하강법 | 일 때만 감소합니다 |
연속시간에는 학습률 조건이 없습니다. 109강에서 를 잘못 고르면 발산했던 것은 흐름의 성질이 아니라 이산화의 부작용입니다.
감소량도 적분으로 정확히 나옵니다. 양변을 부터 까지 적분하면
이고, 가 아래로 유계면 왼쪽이 유계이므로 오른쪽 적분이 수렴합니다. 따라서 의 시간 적분이 유한하고, 기울기가 으로 갑니다. 볼록성 없이도 임계점 수렴이 나오는 논증입니다.
바로 확인 2.
확인 2-1. 경사흐름을 따라 를 쓰세요.
답. 입니다.
확인 2-2. 등호는 언제 성립합니까?
답. 인 임계점에서만 성립합니다.
확인 2-3. 감소 보장에 학습률 조건이 필요합니까?
답. 연속시간에는 필요하지 않고 이산화할 때만 필요합니다.
문제. 문제 1의 설정에서 , 이므로 조건수가 입니다.
(1) 를 와 비교하세요.
(2) 경사하강법이 시각 까지 가는 데 필요한 걸음 수를 별로 세세요.
(3) 조건수가 어느 단계에서 등장하는지 설명하세요.
생각의 실마리. 흐름의 해가 와 의 조합인데, 오래 살아남는 쪽은 느린 성분입니다.
풀이. (1) 검산에서 비가 일정합니다.
| 비 | |||
|---|---|---|---|
| 5.05000000\times10^ | 5.05000000\times10^ | ||
| 4.09365480\times10^ | 4.13459030\times10^ | ||
| 1.83939721\times10^ | 1.85779118\times10^ | ||
| 9.15781944\times10^ | 9.24939764\times10^ |
비가 로 고정되어 있습니다. 이는 감쇠율이 정확히 라는 뜻입니다. 은 전혀 나타나지 않습니다.
(2) 한 걸음이 만큼의 시간을 나아가므로 걸음 수는 입니다.
| 판정 | 까지 걸음 수 | |
|---|---|---|
| 수렴 | ||
| 수렴 | ||
| 수렴 | ||
| 진동 | 도달하지 못합니다 | |
| 발산 | 도달하지 못합니다 |
를 키우면 걸음 수가 줄지만 에서 벽에 부딪힙니다. 109강에서 본 네 갈래 판정이 그대로입니다.
(3) 필요한 시간이 이고 한 걸음이 갈 수 있는 시간이 이므로
입니다. 조건수는 흐름에는 없고 이산화 제약에서 생깁니다.
이 문제에서 배우는 것: 조건수의 저주는 이산화의 대가다.
연속시간 수렴률. 가 -강볼록이면 경사흐름을 따라
이며 은 등장하지 않습니다.
증명은 문제 2의 항등식과 108강의 PL 부등식 를 합치면 나옵니다.
이고 117강의 분리 변수법으로 지수 부등식이 됩니다.
110강에서 봤던 의존이 어디서 왔는지가 이제 설명됩니다.
| 단계 | 가 있는가 |
|---|---|
| 흐름의 감쇠율 | 없습니다. 뿐입니다 |
| 필요한 시간 | 없습니다. 입니다 |
| 허용 시간 간격 | 여기서 이 들어옵니다 |
| 걸음 수 | 가 나타납니다 |
따라서 조건수를 이기는 길은 두 가지입니다. 첫째는 더 좋은 이산화를 쓰는 것이며 111강의 모멘텀이 이에 해당합니다. 둘째는 흐름 자체를 바꾸는 것이며 112강의 뉴턴법이 이에 해당합니다. 문제 4와 문제 5에서 각각 봅니다.
바로 확인 3.
확인 3-1. 경사흐름의 수렴률을 쓰세요.
답. 이며 과 무관합니다.
확인 3-2. 조건수는 어느 단계에서 등장합니까?
답. 허용 시간 간격이 로 막히는 이산화 단계에서 등장합니다.
확인 3-3. 걸음 수가 에 비례하는 이유를 한 줄로 쓰세요.
답. 필요한 시간이 인데 한 걸음이 까지만 가기 때문입니다.
문제. 모멘텀을 연속시간으로 옮기면 이 됩니다.
(1) 이차함수에서 이를 성분별로 분해하고 특성방정식을 쓰세요.
(2) 를 바꿔가며 느린 쪽 감쇠율을 구하세요.
(3) 최적 와 그때의 속도를 경사흐름과 비교하세요.
생각의 실마리. 118강 문제 4의 2계 방정식입니다. 는 마찰이고 는 복원력입니다. 마찰이 없으면 영원히 진동하고, 너무 크면 꿈쩍하지 않습니다.
풀이. (1) 이면 성분별로
이고, 118강처럼 를 넣으면 특성방정식이 나옵니다.
(2) 검산 결과입니다.
| 의 근 | 의 근 | 느린 쪽 감쇠율 | |
|---|---|---|---|
에서 감쇠율이 가장 좋습니다. 그보다 작으면 마찰이 부족해 실수부가 로 작고, 그보다 크면 느린 모드가 과감쇠되어 오히려 느려집니다.
(3) 이며 그때 감쇠율이 입니다. 경사흐름의 과 비교하면
배 빠릅니다.
이 문제에서 배우는 것: 모멘텀은 가속의 연속시간 정체다.
감쇠 진동 방정식.
은 마찰이 있는 공이 골짜기를 굴러가는 운동입니다. 111강의 모멘텀이 이 방정식의 이산화입니다.
이산 모멘텀 , 에서 , 로 두고 을 보내면 이 방정식이 나옵니다.
임계 감쇠. 고유값 의 모드는 에서 중근 를 가지며, 이때가 가장 빠른 감쇠입니다.
세 구간이 명확히 갈립니다.
| 구간 | 조건 | 근 | 거동 |
|---|---|---|---|
| 과소감쇠 | \gamma<2\sqrt | 복소 | 실수부 로 진동하며 줄어듭니다 |
| 임계감쇠 | \gamma=2\sqrt | 중근 -\sqrt | 진동 없이 가장 빠릅니다 |
| 과감쇠 | \gamma>2\sqrt | 실수 둘 | 느린 근이 에 가까워 느려집니다 |
여러 모드를 동시에 다뤄야 하므로 선택이 절충입니다. 로 두면 느린 모드는 임계감쇠가 되고 빠른 모드는 과소감쇠가 되는데, **과소감쇠 모드의 실수부도 **이므로 결국 모든 모드가 로 균일하게 줄어듭니다. 표의 줄에서 두 모드의 실수부가 모두 인 것이 이 현상입니다.
111강에서 가 클수록 좋다가 어느 지점부터 나빠졌던 이유가 이것입니다. 이므로 를 키우면 가 작아지고, 를 지나 더 작아지면 마찰 부족으로 진동이 길어집니다.
바로 확인 4.
확인 4-1. 모멘텀의 연속시간 방정식을 쓰세요.
답. 입니다.
확인 4-2. 고유값 모드의 임계 감쇠 계수를 쓰세요.
답. 입니다.
확인 4-3. 최적 에서 감쇠율이 경사흐름의 몇 배입니까?
답. 배입니다.
문제. 뉴턴 흐름 를 문제 1의 이차함수에서 봅니다.
(1) 흐름의 해석해를 구하세요.
(2) 경사흐름과 의 감소를 비교하세요.
(3) 이산화 단계에서 어떤 차이가 더 생기는지 설명하세요.
생각의 실마리. 이므로 입니다. 가 통째로 사라집니다.
풀이. (1) 흐름이 가 되므로
입니다. 모든 방향이 똑같이 로 줄어듭니다. 의 고유값이 무엇이든 상관없습니다.
(2) 검산 결과입니다.
| 경사흐름 | 뉴턴흐름 | 경사뉴턴 | |
|---|---|---|---|
| 5.050000\times10^ | 5.050000\times10^ | 1.0000\times10^ | |
| 7.256863\times10^ | 6.834432\times10^ | 1.0618\times10^ | |
| 4.546887\times10^ | 2.292696\times10^ | 1.9832\times10^ | |
| 3.351600\times10^ | 2.145419\times10^ | 1.5622\times10^ |
경사흐름은 , 뉴턴흐름은 이므로 지수에서 배 차이입니다.
(3) 이산화에서 차이가 더 벌어집니다.
| 방법 | 까지 걸음 수 | |
|---|---|---|
| 경사하강법 | ||
| 뉴턴법 |
뉴턴법은 이 안전하며, 이차함수에서는 한 걸음이 에 해당합니다.
이 문제에서 배우는 것: 알고리즘 선택은 흐름 선택이다.
뉴턴 흐름.
는 헤세 행렬이 정의하는 좌표계에서의 경사흐름입니다.
96강 심화 3에서 최속강하 방향이 어떤 노름을 쓰느냐에 따라 달라진다고 했습니다. 그것이 여기서 흐름의 선택으로 나타납니다.
| 노름 | 흐름 | 알고리즘 |
|---|---|---|
| \lVert\mathbf{v}\rVert_ | 경사하강법 | |
| 뉴턴법 | ||
| , 가 대각 | 아담 계열 | |
| 피셔 정보 노름 | 자연경사법 |
공통 꼴은 하나입니다.
이 무엇이냐가 알고리즘의 이름을 정합니다. 그리고 어느 을 써도 문제 2의 소산 항등식이 유지됩니다.
이 양의 정부호면 오른쪽이 이하이므로, 어떤 전처리를 써도 는 감소합니다. 이것이 112강에서 헤세 행렬의 양의 정부호성을 요구했던 이유입니다.
바로 확인 5.
확인 5-1. 뉴턴 흐름의 이차함수 해를 쓰세요.
답. 이며 조건수와 무관합니다.
확인 5-2. 전처리된 흐름의 일반형을 쓰세요.
답. 이며 입니다.
확인 5-3. 이면 의 감소가 보장됩니까?
답. 보장됩니다. 입니다.
| 개념 | 내용 |
|---|---|
| 경사흐름 | |
| 이산화 | 가 시간 간격, |
| 소산 | |
| 연속 수렴률 | , 무관 |
| 모멘텀 흐름 | \ddot{\mathbf{x}}+\gamma\dot{\mathbf{x}}+\nabla f=\mathbf |
| 최적 감쇠 | , 감쇠율 -\sqrt |
| 뉴턴 흐름 | |
| 전처리 흐름 |
| 가 나타나는 자리 | 있는가 |
|---|---|
| 흐름의 감쇠율 | 없습니다 |
| 필요한 시간 | 없습니다 |
| 허용 | 여기서 이 들어옵니다 |
| 걸음 수 | 가 나타납니다 |
| 감쇠 구간 | 조건 |
|---|---|
| 과소감쇠 | \gamma<2\sqrt |
| 임계감쇠 | \gamma=2\sqrt |
| 과감쇠 | \gamma>2\sqrt |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 걸음 수끼리 비교합니다 | 시각 끼리 비교합니다 |
| 흐름도 제한이 있다고 봅니다 | 흐름에는 없고 이산화에만 있습니다 |
| 가 흐름의 성질이라 봅니다 | 이산화 제약에서 생깁니다 |
| 는 클수록 좋다고 봅니다 | 가 최적이고 넘으면 느려집니다 |
문제 6. 경사흐름의 방정식을 쓰세요.
답. 입니다.
문제 7. 는 흐름의 무엇에 해당합니까?
답. 시간 간격이며 걸음이 에 대응합니다.
문제 8. 전진 오일러의 한 걸음 오차와 전체 오차 차수를 쓰세요.
답. 한 걸음이 이고 전체가 입니다.
문제 9. 흐름을 따라 를 쓰세요.
답. 입니다.
문제 10. 가 아래로 유계면 무엇이 따라옵니까?
답. 가 수렴하므로 기울기가 으로 갑니다.
문제 11. -강볼록일 때 연속시간 수렴률을 쓰세요.
답. 입니다.
문제 12. 이 수렴률에 이 없는 이유를 쓰세요.
답. PL 부등식이 만 쓰고 흐름에는 시간 간격 제약이 없기 때문입니다.
문제 13. 걸음 수가 에 비례하는 이유를 쓰세요.
답. 필요한 시간이 인데 한 걸음이 까지만 가기 때문입니다.
문제 14. 모멘텀의 연속시간 방정식을 쓰세요.
답. 입니다.
문제 15. 모드의 임계 감쇠 계수와 그때의 근을 쓰세요.
답. 이며 중근 입니다.
문제 16. 과소감쇠일 때 감쇠율을 쓰세요.
답. 이며 와 무관합니다.
문제 17. 뉴턴 흐름을 이차함수에서 풀면 무엇이 됩니까?
답. 이며 모든 방향이 같은 속도입니다.
문제 18. 전처리 흐름 에서 의 감소 조건을 쓰세요.
답. 이 양의 정부호이면 감소합니다.
심화 1. 흐름 관점으로 04단원을 다시 정리하세요.
04단원의 결과들이 하나의 관점으로 묶입니다.
| 04단원 | 흐름 관점 |
|---|---|
| 109강의 | 전진 오일러의 안정성 조건입니다 |
| 109강의 진동 | 안정성 경계이며 감쇠가 입니다 |
| 110강의 | 볼록이지만 강볼록이 아니라 지수 감쇠가 없습니다 |
| 110강의 | 강볼록이라 를 걸음으로 환산한 것입니다 |
| 111강의 모멘텀 | 2계 방정식의 이산화입니다 |
| 111강의 한계 | 를 지나 마찰이 부족해진 것입니다 |
| 112강의 뉴턴법 | 다른 노름의 흐름입니다 |
110강의 두 수렴률 차이도 흐름에서 설명됩니다. 강볼록이면 PL 부등식이 를 주어 지수 감쇠가 나오지만, 강볼록이 아니면 가 작아질 때 가 그보다 빨리 작아져 감쇠가 느려집니다. 110강에서 가 이었던 것이 이 현상의 구체적인 예입니다.
심화 2. 명시적 이산화와 암시적 이산화를 비교하세요.
문제 1은 전진 오일러를 썼습니다.
기울기를 현재 점에서 잽니다. 대신 다음 점에서 재면 후진 오일러가 됩니다.
오른쪽에 미지수가 있어 방정식을 풀어야 합니다. 이차함수 에서는 풀 수 있습니다.
성분별 인자를 비교하면 차이가 보입니다.
| 방법 | 인자 | 안정 조건 |
|---|---|---|
| 전진 오일러 | ||
| 후진 오일러 | 모든 |
후진 오일러는 가 아무리 커도 발산하지 않습니다. 이면 가 항상 에 있기 때문입니다. 이를 무조건 안정이라 부르며, 118강 심화에서 언급한 뻣뻣한 계에 쓰는 표준 대응입니다.
그런데 이 갱신에는 다른 이름이 있습니다.
의 최적성 조건이 이고 이것이 후진 오일러입니다. 근접점 방법이라 부르며, 안정성을 얻는 대신 매 걸음 부분 최적화를 풀어야 합니다.
심화 3. 네스테로프 가속의 연속시간 방정식을 설명하세요.
문제 4는 가 상수였습니다. 강볼록이 아니면 를 모르므로 를 고를 수 없습니다. 이때 쓰는 것이 시간에 따라 줄어드는 감쇠입니다.
계수 가 네스테로프 가속법의 연속시간 극한입니다. 초기에는 마찰이 크고 시간이 지나면 마찰이 줄어드는 구조입니다.
이 방정식의 해는 다음을 만족합니다.
이며 경사흐름의 보다 빠릅니다. 이산화하면 110강에서 말한 가속률이 됩니다.
계수 의 정체가 흥미롭습니다. 리아푸노프 함수
를 미분하면 이 되는데, 계수가 일 때 딱 맞아떨어집니다. 보다 작으면 감쇠가 부족하고 크면 필요 이상으로 느려집니다.
심화 4. 경사흐름이 임계점에 도달하지 못하는 경우를 설명하세요.
문제 2에서 은 보였지만 가 수렴한다는 보장은 아닙니다.
첫째로 발산할 수 있습니다. 이면 흐름이 이므로 로 무한대로 갑니다. 가 아래로 유계가 아니면 문제 2의 논증이 무너집니다.
둘째로 유한 시간에 폭발할 수 있습니다. 면 이고 117강에서 본 대로
이라 에서 무한대가 됩니다. 흐름이 정의되는 시간 자체가 유한합니다.
셋째로 유계여도 진동할 수 있습니다. 임계점 집합이 곡선을 이루면 궤적이 그 위를 돌 수 있습니다. 다만 경사흐름은 118강 문제 5에서 본 대로 리아푸노프 함수가 있어 극한주기를 가질 수 없고, 실제 병리적인 예는 만들기 까다롭습니다. 해석함수라면 로자시에비치 부등식이 수렴을 보장합니다.
실무에서 중요한 것은 첫째와 둘째입니다. 손실함수가 아래로 유계인지 확인하는 것이 학습 안정성의 첫 점검입니다.
심화 5. 확률적 경사하강법의 연속시간 극한을 설명하세요.
실제 학습에서는 미니배치 기울기를 씁니다.
여기서 는 평균이 인 잡음입니다. 이것의 연속시간 극한은 확률미분방정식이 됩니다.
는 브라운 운동이고 는 기울기 잡음의 공분산입니다.
여기서 두 가지가 읽힙니다.
첫째로 잡음의 크기가 에 비례합니다. 학습률이 클수록 궤적이 요동칩니다. 110강에서 학습률이 클 때 수렴이 어느 지점에서 멈췄던 현상이 이것입니다.
둘째로 잡음이 얕은 극소를 탈출시킵니다. 결정론적 경사흐름은 극소에 갇히지만, 잡음이 있으면 장벽을 넘을 확률이 있습니다. 장벽 높이 를 넘는 데 걸리는 기대 시간이 대략
이라 얕은 극소는 금방 빠져나오고 깊은 극소에는 오래 머뭅니다. 학습률을 처음에 크게 두었다가 줄이는 관행의 이론적 근거입니다.
심화 6. 흐름 관점이 실무에서 무엇을 바꾸는지 정리하세요.
첫째로 하이퍼파라미터의 단위가 생깁니다. 가 시간 간격이므로 걸음 수가 흐른 시간입니다. 배치 크기를 두 배로 키우면서 도 두 배로 키우는 선형 스케일링 법칙이 여기서 나옵니다. 같은 시간을 흐르게 하려는 것입니다.
둘째로 서로 다른 알고리즘을 같은 언어로 비교합니다. 경사하강법, 모멘텀, 아담, 뉴턴법이 모두 또는 그 2계 확장이며, 차이는 과 뿐입니다.
셋째로 학습률 스케줄을 시간 재척도로 읽습니다. 를 줄이는 것은 시간을 천천히 흐르게 하는 것이며, 심화 5의 잡음 크기를 줄이는 것과 같습니다.
넷째로 안정성 문제를 진단합니다. 학습이 발산하면 인지 의심하고, 진동하면 경계이거나 모멘텀이 과소감쇠인지 봅니다. 118강의 고유값 판정이 그대로 도구가 됩니다.
다섯째로 새 알고리즘을 설계할 실마리를 줍니다. 미분방정식 수치해법에는 룽게쿠타를 비롯한 고차 방법이 축적되어 있으며, 120강에서 이를 다룹니다.
import numpy as np
# mu = 0.01, L = 1, kappa = 100
H = np.array([[0.01, 0.0], [0.0, 1.0]]); mu, L = 0.01, 1.0
kap = L/mu
f = lambda x: 0.5*(x @ H @ x); gf = lambda x: H @ x
x0 = np.array([1.0, 1.0]); f0 = f(x0)
flow = lambda t: np.array([np.exp(-mu*t), np.exp(-L*t)])
vec = lambda v: "(%9.6f, %9.6f)" % (v[0], v[1])
# --- 문제 1: 경사하강법은 경사흐름의 오일러 이산화다 --------------------
print(" 경사흐름 dx/dt = -grad f, H = diag(0.01, 1), x0 = (1, 1)")
print(" t 연속해 e^{-Ht}x0 GD (eta=0.01) 차이")
e = 0.01
xg = x0.copy(); want = {int(round(T/e)): T for T in [0.5, 2.0, 10.0, 50.0]}
got = {}
for k in range(1, max(want)+1):
xg = xg - e*gf(xg)
if k in want: got[k] = xg.copy()
for k, T in sorted(want.items()):
c = flow(T); d = got[k]
print(" %7.1f %s %s %.3e" % (T, vec(c), vec(d), np.linalg.norm(c-d)))
print(" eta 가 시간 간격이고 k 걸음이 t = k*eta 에 대응합니다")
# 경사흐름 dx/dt = -grad f, H = diag(0.01, 1), x0 = (1, 1)
# t 연속해 e^{-Ht}x0 GD (eta=0.01) 차이
# 0.5 ( 0.995012, 0.606531) ( 0.995012, 0.605006) 1.525e-03
# 2.0 ( 0.980199, 0.135335) ( 0.980198, 0.133980) 1.356e-03
# 10.0 ( 0.904837, 0.000045) ( 0.904833, 0.000043) 5.044e-06
# 50.0 ( 0.606531, 0.000000) ( 0.606515, 0.000000) 1.516e-05
# eta 가 시간 간격이고 k 걸음이 t = k*eta 에 대응합니다
# --- 문제 2: 흐름을 따라 f 는 단조 감소한다 -----------------------------
print(" df/dt = grad f . dx/dt = -|grad f|^2 <= 0")
print(" t f(x(t)) |grad f|^2 수치 df/dt")
for T in [0.0, 1.0, 5.0, 20.0]:
x = flow(T); h = 1e-6
d = (f(flow(T+h)) - f(flow(T-h)))/(2*h)
print(" %7.1f %12.8f %14.8f %14.8f" % (T, f(x), gf(x) @ gf(x), d))
print(" f 자신이 리아푸노프 함수입니다")
# df/dt = grad f . dx/dt = -|grad f|^2 <= 0
# t f(x(t)) |grad f|^2 수치 df/dt
# 0.0 0.50500000 1.00010000 -1.00010000
# 1.0 0.07256863 0.13543330 -0.13543330
# 5.0 0.00454689 0.00013588 -0.00013588
# 20.0 0.00335160 0.00006703 -0.00006703
# f 자신이 리아푸노프 함수입니다
# --- 문제 3: 연속시간 수렴률은 mu 만으로 정해진다 -----------------------
print(" 경사흐름은 L 과 무관하게 e^{-2*mu*t} 로 줄어듭니다")
print(" t f(x(t)) e^{-2*mu*t}*f(x0) 비")
for T in [0.0, 10.0, 50.0, 200.0]:
v = f(flow(T)); b = np.exp(-2*mu*T)*f0
print(" %7.1f %14.8e %16.8e %8.4f" % (T, v, b, v/b))
print(" 비가 일정하므로 감쇠율이 정확히 -2*mu 입니다")
print(" 그런데 GD 한 걸음이 나아갈 수 있는 시간은 eta < 2/L = %.1f 로 막혀 있습니다" % (2/L))
print(" eta 판정 t=50 까지 필요한 걸음 수")
for e2 in [0.5, 1.0, 1.9, 2.0, 2.1]:
r = abs(1 - e2*L)
tag = "수렴" if r < 1 else ("진동" if r == 1 else "발산")
n = ("%d" % int(np.ceil(50.0/e2))) if r < 1 else "-"
print(" %7.2f %-8s %10s" % (e2, tag, n))
print(" 필요한 걸음 수 ~ (1/mu)/(2/L) = kappa/2 = %.0f 이고 조건수는 이산화에서 나옵니다" % (kap/2))
# 경사흐름은 L 과 무관하게 e^{-2*mu*t} 로 줄어듭니다
# t f(x(t)) e^{-2*mu*t}*f(x0) 비
# 0.0 5.05000000e-01 5.05000000e-01 1.0000
# 10.0 4.09365480e-03 4.13459030e-01 0.0099
# 50.0 1.83939721e-03 1.85779118e-01 0.0099
# 200.0 9.15781944e-05 9.24939764e-03 0.0099
# 비가 일정하므로 감쇠율이 정확히 -2*mu 입니다
# 그런데 GD 한 걸음이 나아갈 수 있는 시간은 eta < 2/L = 2.0 로 막혀 있습니다
# eta 판정 t=50 까지 필요한 걸음 수
# 0.50 수렴 100
# 1.00 수렴 50
# 1.90 수렴 27
# 2.00 진동 -
# 2.10 발산 -
# 필요한 걸음 수 ~ (1/mu)/(2/L) = kappa/2 = 50 이고 조건수는 이산화에서 나옵니다
# --- 문제 4: 모멘텀 흐름은 sqrt(mu) 로 빨라진다 -------------------------
print(" 모멘텀 흐름 x'' + gam*x' + grad f = 0 의 모드: s^2 + gam*s + lam = 0")
def modes(gam, lam):
disc = gam*gam - 4*lam
if disc >= 0:
r = np.sqrt(disc); return np.array([(-gam+r)/2, (-gam-r)/2])
r = np.sqrt(-disc); return np.array([-gam/2 + 1j*r/2, -gam/2 - 1j*r/2])
sh = lambda m: ("(%+7.4f, %+7.4f)" % (m[0].real, m[1].real) if m.dtype == float
else "(%+7.4f +- %6.4f i)" % (m[0].real, m[0].imag))
print(" gam lam=0.01 의 근 lam=1 의 근 느린 쪽 감쇠율")
for gam in [0.05, 0.1, 0.2, 0.5, 2.0]:
m1, m2 = modes(gam, mu), modes(gam, L)
slow = max(m1.real.max(), m2.real.max())
print(" %7.2f %-24s %-26s %+10.4f" % (gam, sh(m1), sh(m2), slow))
print(" 최적 gam = 2*sqrt(mu) = %.2f 에서 감쇠율이 -sqrt(mu) = %.2f 로 균일해집니다"
% (2*np.sqrt(mu), -np.sqrt(mu)))
print(" 경사흐름의 -mu = %.2f 보다 %.0f 배 빠르고 이 값이 sqrt(kappa) = %.0f 입니다"
% (-mu, np.sqrt(mu)/mu, np.sqrt(kap)))
# 모멘텀 흐름 x'' + gam*x' + grad f = 0 의 모드: s^2 + gam*s + lam = 0
# gam lam=0.01 의 근 lam=1 의 근 느린 쪽 감쇠율
# 0.05 (-0.0250 +- 0.0968 i) (-0.0250 +- 0.9997 i) -0.0250
# 0.10 (-0.0500 +- 0.0866 i) (-0.0500 +- 0.9987 i) -0.0500
# 0.20 (-0.1000, -0.1000) (-0.1000 +- 0.9950 i) -0.1000
# 0.50 (-0.0209, -0.4791) (-0.2500 +- 0.9682 i) -0.0209
# 2.00 (-0.0050, -1.9950) (-1.0000, -1.0000) -0.0050
# 최적 gam = 2*sqrt(mu) = 0.20 에서 감쇠율이 -sqrt(mu) = -0.10 로 균일해집니다
# 경사흐름의 -mu = -0.01 보다 10 배 빠르고 이 값이 sqrt(kappa) = 10 입니다
# --- 문제 5: 뉴턴 흐름은 조건수를 흐름 단계에서 지운다 ------------------
print(" 뉴턴 흐름 dx/dt = -H^{-1}*grad f = -x -> x(t) = e^{-t}*x0")
print(" t 경사흐름 f 뉴턴흐름 f 경사/뉴턴")
for T in [0.0, 1.0, 5.0, 20.0]:
a = f(flow(T)); b = f(np.exp(-T)*x0)
print(" %7.1f %14.6e %14.6e %12.4e" % (T, a, b, a/b))
print(" 경사흐름은 e^{-2*mu*t}, 뉴턴흐름은 e^{-2*t} 라 지수에서 1/mu = %.0f 배 차이입니다" % (1/mu))
print(" 이산화에서도 뉴턴법은 eta = 1 이 안전해 걸음 제한이 없습니다")
xN = x0.copy(); n = 0
while f(xN) > 1e-12*f0 and n < 100000:
xN = xN - np.linalg.solve(H, gf(xN)); n += 1
xG = x0.copy(); n2 = 0
while f(xG) > 1e-12*f0 and n2 < 100000:
xG = xG - 1.0*gf(xG); n2 += 1
print(" 방법 eta f < 1e-12*f0 까지 걸음 수")
print(" 경사하강법 %.2f %10d" % (1.0, n2))
print(" 뉴턴법 %.2f %10d" % (1.0, n))
print(" 이차함수에서 뉴턴법은 한 걸음이 t = 무한대 에 해당합니다")
# 뉴턴 흐름 dx/dt = -H^{-1}*grad f = -x -> x(t) = e^{-t}*x0
# t 경사흐름 f 뉴턴흐름 f 경사/뉴턴
# 0.0 5.050000e-01 5.050000e-01 1.0000e+00
# 1.0 7.256863e-02 6.834432e-02 1.0618e+00
# 5.0 4.546887e-03 2.292696e-05 1.9832e+02
# 20.0 3.351600e-03 2.145419e-18 1.5622e+15
# 경사흐름은 e^{-2*mu*t}, 뉴턴흐름은 e^{-2*t} 라 지수에서 1/mu = 100 배 차이입니다
# 이산화에서도 뉴턴법은 eta = 1 이 안전해 걸음 제한이 없습니다
# 방법 eta f < 1e-12*f0 까지 걸음 수
# 경사하강법 1.00 1146
# 뉴턴법 1.00 1
# 이차함수에서 뉴턴법은 한 걸음이 t = 무한대 에 해당합니다
문제 3이 이 강의의 도착점입니다. 04단원 내내 따라다니던 조건수 가 흐름에는 없고 이산화 제약에서만 생긴다는 것이 표 하나로 드러납니다.
문제 4의 줄을 다시 보십시오. 두 모드의 감쇠율이 모두 정확히 입니다. 하나는 중근이고 다른 하나는 복소근인데 실수부가 같습니다. 서로 다른 방식으로 같은 속도에 도달하는 것이며, 이것이 가속의 정체입니다.
문제 5의 걸음 수 대 이 96강 심화 3의 결론을 수치로 확인합니다. 노름을 바꾸면 같은 함수가 전혀 다른 난이도가 됩니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 경사흐름 | gradient flow | |
| 전진 오일러 | forward Euler | 현재 점에서 기울기를 잽니다 |
| 후진 오일러 | backward Euler | 다음 점에서 기울기를 잽니다 |
| 소산 항등식 | dissipation identity | \dot f=-\lVert\nabla f\rVert^ |
| 조건수 | 이산화 제약에서 나타납니다 | |
| 감쇠 계수 | 모멘텀의 마찰입니다 | |
| 임계 감쇠 | critical damping | \gamma=2\sqrt |
| 과소감쇠 | underdamped | 진동하며 줄어듭니다 |
| 과감쇠 | overdamped | 진동 없이 느립니다 |
| 근접점 방법 | proximal point method | 후진 오일러의 다른 이름입니다 |
| 무조건 안정 | unconditionally stable | 모든 에서 발산하지 않습니다 |
| 양의 정부호 전처리 | 흐름의 노름을 정합니다 |
다음 120강에서는 수치 적분법: 오일러법과 룽게쿠타법을 다룹니다. 이 강의에서 전진 오일러가 정확도라고 했는데, 같은 걸음 수로 훨씬 정확해지는 방법들이 있습니다. 91강의 수치적분과 100강의 테일러 전개가 다시 도구가 되며, 06단원과 S5 전체가 마무리됩니다.