세 강의가 한 줄로 모입니다.
필요한 것이 이미 다 준비됐습니다.
| 강의 | 이 식에 준 것 |
|---|---|
| 96 | 가 가장 가파른 감소 방향입니다 |
| 107 | 볼록이면 도착점이 전역 최소입니다 |
| 108 | 이면 값이 반드시 줄어듭니다 |
이 강의는 그 알고리즘을 실제로 돌려 봅니다. 정리를 세우는 것이 아니라 거동을 관찰합니다.
그리고 96강 심화 3에서 예고한 문제를 정면으로 만납니다.
그때 최급강하가 정답 방향에서 도 벗어난다고 했습니다. 그 어긋남이 반복되면 지그재그가 되고, 조건수가 클수록 심해집니다.
이 강의가 관찰한 것을 110강이 증명하고 111강과 112강이 고칩니다.
문제. 과 시작점 을 봅니다.
(1) 로 여섯 걸음을 적으세요.
(2) 각 걸음의 와 를 보세요.
(3) 두 성분의 거동을 비교하세요.
생각의 실마리. 이 함수는 헤세가 대각이라 두 성분이 서로 간섭하지 않습니다. 각각 따로 봅니다.
풀이. (1)과 (2) 검산에서
| \mathbf{x}_ | |||
|---|---|---|---|
(3) 성분은 한 걸음에 끝나고 성분은 거의 움직이지 않습니다.
의 곱수는 이라 즉시 이 됩니다. 의 곱수는 라 한 걸음에 만 줄어듭니다.
이 문제에서 배우는 것: 성분별 수렴 속도.
경사하강법. 초기점 과 학습률 에 대해
를 반복합니다.
이차함수에서는 정확히 분석됩니다. 이면 이므로
85강에서 다룬 선형 점화식입니다. 로 대각화하고 로 두면 성분마다 분리됩니다.
각 고유방향이 자기 속도로 줄어듭니다.
| 방향 | 곱수 | 일 때 |
|---|---|---|
| , 한 걸음에 끝 | ||
| , 매우 느림 |
전체 속도는 가장 느린 성분이 정합니다. 그것이 방향이고, 곱수가 입니다.
99강 심화 5에서 예고한 긴장이 여기서 구체화됩니다. 를 키우면 방향이 빨라지지만 방향이 발산합니다.
바로 확인 1.
확인 1-1. 경사하강법의 갱신식을 쓰세요.
답. 입니다.
확인 1-2. 이차함수에서 성분별 곱수를 쓰세요.
답. 입니다.
확인 1-3. 전체 수렴 속도는 어느 성분이 정합니까?
답. 가장 느린 성분, 즉 방향입니다.
문제. 같은 함수에 를 씁니다.
(1) 성분을 여덟 걸음 적으세요.
(2) 성분을 여덟 걸음 적으세요.
(3) 두 성분의 곱수를 비교하세요.
생각의 실마리. 이면 의 곱수가 로 음수입니다. 음수를 곱하면 부호가 뒤집힙니다.
풀이. (1) 검산에서
매 걸음 부호가 뒤집히며 크기가 배씩 줄어듭니다.
(2) 검산에서
부호가 그대로이고 천천히 줄어듭니다.
(3) 검산에서 곱수가 는 , 는 입니다.
이 문제에서 배우는 것: 지그재그의 정체.
, 즉 인 방향에서 부호가 뒤집힙니다.
| 조건 | 곱수 | 거동 |
|---|---|---|
| \eta<1/\lambda_ | 한쪽으로 접근 | |
| \eta=1/\lambda_ | 한 걸음에 도달 | |
| 1/\lambda_{i}<\eta<2/\lambda_ | 넘나들며 접근 | |
| \eta>2/\lambda_ | 발산 |
가 크면 셋째 줄과 첫째 줄이 동시에 일어납니다. 하나로 모든 방향을 맞출 수 없기 때문입니다.
96강 심화 3의 도가 이 현상의 한 걸음짜리 모습이었습니다. 그때 최급강하 방향이 목적지에서 크게 벗어났는데, 반복하면 좌우로 튕기며 골짜기를 따라 조금씩 내려갑니다.
등고선으로 보면 분명합니다. 93강 심화 5에서 길쭉한 타원을 봤고, 95강 문제 4에서 가 등고선에 수직이라 했습니다. 좁은 골짜기에서 등고선의 수직 방향은 골짜기를 따라가는 방향이 아니라 반대편 벽을 향합니다.
바로 확인 2.
확인 2-1. 지그재그가 생기는 조건을 쓰세요.
답. 곱수 가 음수인 것, 즉 입니다.
확인 2-2. 곱수가 이 되는 를 쓰세요.
답. 이며 그 방향은 한 걸음에 끝납니다.
확인 2-3. 왜 하나의 로 모든 방향을 맞출 수 없습니까?
답. 고유값이 서로 다르고 최적 가 각각 이기 때문입니다.
문제. 에서 걸음을 돌립니다.
(1) 각각의 최종 를 구하세요.
(2) 을 계산하세요.
(3) 네 가지 거동으로 분류하세요.
생각의 실마리. 문제 1에서 성분별 곱수가 거동을 정한다고 했습니다. 가장 큰 고유값의 곱수가 안정성을 정합니다.
풀이. 검산에서
| 걸음 뒤 | 판정 | |
|---|---|---|
| 3.350930\times10^ | 느림, | |
| 8.975277\times10^ | 수렴, | |
| 1.563462\times10^ | 느림, | |
| 5.000015\times10^ | 진동, | |
| 2.676206\times10^ | 발산, |
한 수 이 모든 것을 가릅니다.
이 문제에서 배우는 것: 네 가지 영역.
| 영역 | 거동 | |
|---|---|---|
| 너무 작음 | 안전하지만 느립니다 | |
| 적정 | 가장 빠릅니다 | |
| 큼 | 진동하며 수렴합니다 | |
| 임계 | 진동만 하고 줄지 않습니다 | |
| 발산 | 커집니다 |
넷째 줄이 미묘합니다. 이면 이라 방향의 크기가 유지됩니다. 검산에서 가 근처에 머무는 것이 그 때문이며, 방향은 여전히 줄지만 방향이 계속 튕겨 전체가 수렴하지 않습니다.
이 보다 나쁘지 않은 것도 볼 만합니다. 를 키우면 방향은 빨라지지만 방향의 진동이 커져, 둘의 균형이 최적점을 만듭니다.
실무에서 어떻게 고르는지를 정리합니다.
| 방법 | 내용 |
|---|---|
| 을 추정 | 멱반복이나 이론적 상한 |
| 학습률 탐색 | 를 키우며 손실이 튀는 지점을 찾습니다 |
| 역추적 직선탐색 | 매 걸음 하강 조건을 확인합니다 |
| 감쇠 일정 | 처음 크게 시작해 줄입니다 |
둘째 줄이 딥러닝의 표준 관행입니다. 를 지수적으로 키우며 손실 곡선을 그리고, 급격히 나빠지기 직전 값의 절반쯤을 씁니다. 이것이 사실상 을 실험으로 찾는 절차입니다.
바로 확인 3.
확인 3-1. 안정성을 정하는 양을 쓰세요.
답. 이며 보다 작아야 합니다.
확인 3-2. 이면 무슨 일이 생깁니까?
답. 방향이 크기를 유지하며 진동해 수렴하지 않습니다.
확인 3-3. 학습률 탐색이 실질적으로 무엇을 찾습니까?
답. 의 실험적 추정치입니다.
문제. 에서 을 봅니다.
(1) 로 가 초기값의 이 될 때까지의 걸음 수를 세세요.
(2) 과 비교하세요.
(3) 비례 관계를 판정하세요.
생각의 실마리. 108강 심화 2에서 걸음 수가 에 비례한다고 유도했습니다. 실제로 그런지 확인합니다.
풀이. 검산에서
| 실제 걸음 수 | ||
|---|---|---|
(3) 실제가 이론의 삼분의 일쯤이지만 에 비례해 늘어납니다. 가 열 배가 될 때 걸음도 대략 열 배가 됩니다.
이 문제에서 배우는 것: 조건수가 비용을 정합니다.
이론이 실제보다 큰 이유가 둘 있습니다.
첫째, 이론은 최악의 경우를 잡습니다. 초기점이 최악의 방향에 놓여 있다고 가정하는데, 검산의 은 그렇지 않습니다.
둘째, 가 에 비례하므로 의 감소율이 의 두 배입니다. 곱수가 이면 는 로 줄어들어 걸음이 절반이면 됩니다.
에서 한 걸음인 것이 중요합니다. 검산의 마지막 줄에서 확인됩니다.
이면 이라 즉시 원점입니다. 등고선이 원이면 최급강하가 곧장 중심을 향합니다.
가 실무에서 얼마나 큰지를 적어 둡니다.
| 문제 | 전형적 |
|---|---|
| 잘 조건화된 이차 | ~ |
| 표준화하지 않은 회귀 | ~10^ |
| 심층 신경망 | 이상 |
| 힐베르트 행렬 | 10^ |
둘째 줄이 특징 표준화의 이유입니다. 특징의 척도가 제각각이면 의 조건수가 커지고, 표준화가 그것을 줄입니다. 91강에서 조건수를 다룰 때 본 그대로입니다.
바로 확인 4.
확인 4-1. 걸음 수의 조건수 의존성을 쓰세요.
답. 에 비례합니다.
확인 4-2. 이면 몇 걸음입니까?
답. 로 한 걸음입니다.
확인 4-3. 특징 표준화가 최적화에 주는 이득을 쓰세요.
답. 조건수를 줄여 걸음 수를 줄입니다.
문제. 기울기 기준 로 멈춥니다.
(1) 에서 멈춘 지점의 를 구하세요.
(2) 108강의 상한 와 비교하세요.
(3) 결과를 해석하세요.
생각의 실마리. 108강 문제 5에서 상한이 헐겁다고 했습니다. 실제로 얼마나 헐거운지 봅니다.
풀이. 검산에서
| 기준 | 멈춘 f-f^ | 상한 |
|---|---|---|
| 10^ | 4.910882\times10^ | 4.910882\times10^ |
| 10^ | 4.921286\times10^ | 4.921286\times10^ |
| 10^ | 4.931713\times10^ | 4.931713\times10^ |
(3) 상한이 실제와 정확히 같습니다.
이 문제에서 배우는 것: 상한이 언제 빡빡한가.
108강 문제 5에서 임의의 점에서는 상한이 배까지 헐거웠는데, 여기서는 정확히 일치합니다. 이유는 수렴한 지점의 위치에 있습니다.
문제 1에서 봤듯 방향은 즉시 죽고 방향만 남습니다. 그래서 멈추는 지점이 꼴입니다.
의 고유벡터 방향에서 PL 부등식이 등호가 되기 때문이며, 108강 문제 5의 에서 비가 정확히 이었던 것과 같은 이유입니다.
이것이 좋은 소식과 나쁜 소식을 함께 줍니다.
| 측면 | 내용 |
|---|---|
| 좋은 점 | 종료 조건의 상한이 정확합니다 |
| 나쁜 점 | 가장 느린 방향에서 시간을 다 씁니다 |
종료 조건의 선택지를 정리합니다.
| 기준 | 식 | 장단점 |
|---|---|---|
| 기울기 | 척도에 의존합니다 | |
| 상대 기울기 | 척도에 무관합니다 | |
| 손실 변화 | 느릴 때 오판합니다 | |
| 위치 변화 | 같은 문제 | |
| 검증 성능 | 조기 종료 | 최적화가 아니라 일반화 기준 |
셋째와 넷째 줄의 위험을 짚어 둡니다. 방향의 곱수가 라 가 크면 한 걸음의 변화가 아주 작습니다. 수렴해서 안 움직이는 것이 아니라 느려서 안 움직이는 것인데 구별이 안 됩니다.
다섯째 줄이 기계학습의 실제 답입니다. 손실의 최소점에 도달하는 것 자체가 목표가 아니며, 212강에서 다룹니다.
101강 심화 5의 경고가 여기서 완성됩니다. 안장 근처에서는 이라 위 상한이 아예 성립하지 않고, 기울기가 작아도 최소 근처가 아닙니다.
바로 확인 5.
확인 5-1. 수렴한 지점에서 상한이 빡빡한 이유를 쓰세요.
답. 방향으로 수렴하며 그 방향에서 PL 부등식이 등호이기 때문입니다.
확인 5-2. 손실 변화 기준의 위험을 쓰세요.
답. 느려서 안 움직이는 것을 수렴으로 오판할 수 있습니다.
확인 5-3. 척도에 무관한 기울기 기준을 쓰세요.
답. 초기 기울기에 대한 상대 기준입니다.
| 항목 | 내용 |
|---|---|
| 갱신식 | |
| 이차함수 | \mathbf{x}_{k+1}=(I-\eta H)\mathbf{x}_ |
| 성분별 곱수 | 1-\eta\lambda_ |
| 안정성 | , 즉 |
| 걸음 수 |
| 거동 | |
|---|---|
| 안전하고 느립니다 | |
| 가장 빠릅니다 | |
| 진동하며 수렴합니다 | |
| 진동만 합니다 | |
| 발산합니다 |
| 관찰 | 이유 |
|---|---|
| 방향이 먼저 끝납니다 | 곱수가 작습니다 |
| 방향이 발목을 잡습니다 | 곱수가 입니다 |
| 지그재그가 생깁니다 | 곱수가 음수인 방향이 있습니다 |
| 이면 한 걸음 | 입니다 |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 를 이상 씁니다 | 발산합니다 |
| 변화가 작으면 수렴이라 봅니다 | 느린 것일 수 있습니다 |
| 기울기 기준을 절대값으로 씁니다 | 상대 기준이 낫습니다 |
| 안장에서 종료 조건을 믿습니다 | 이라 상한이 없습니다 |
문제 6. 경사하강법의 갱신식을 쓰세요.
답. 입니다.
문제 7. 이차함수에서 갱신식을 행렬로 쓰세요.
답. 입니다.
문제 8. 인 방향의 최적 를 쓰세요.
답. 이며 한 걸음에 끝납니다.
문제 9. 일 때 안정한 의 범위를 쓰세요.
답. 입니다.
문제 10. 일 때 방향의 곱수를 쓰세요.
답. 입니다.
문제 11. 이고 이면 방향이 절반이 되는 데 몇 걸음 걸립니까?
답. 에서 걸음입니다.
문제 12. 지그재그가 생기는 의 조건을 쓰세요.
답. 어떤 에 대해 인 경우입니다.
문제 13. 의 거동을 쓰세요.
답. 방향이 크기를 유지하며 진동해 수렴하지 않습니다.
문제 14. 이면 몇 걸음에 끝납니까?
답. 로 한 걸음입니다.
문제 15. 걸음 수의 의존성을 쓰세요.
답. 에 비례합니다.
문제 16. 특징 표준화가 왜 도움이 됩니까?
답. 조건수를 줄여 걸음 수를 줄이기 때문입니다.
문제 17. 손실 변화 기준의 위험을 쓰세요.
답. 느려서 안 움직이는 것을 수렴으로 오판합니다.
문제 18. 학습률 탐색이 찾는 값을 쓰세요.
답. 의 실험적 추정치입니다.
심화 1. 최적 학습률을 정확히 구하세요.
문제 3에서 이 좋다고 했습니다. 정말 최선인지 확인합니다.
이차함수에서 수렴 속도는 가장 느린 성분이 정합니다.
가 작으면 가 크고, 크면 이 큽니다. 최소는 둘이 같아지는 곳입니다.
그때의 수렴률은
93강 심화 5에서 예고한 식이 정확히 나왔습니다.
과 비교합니다.
| 수렴률 | |
|---|---|
가 크면 둘 다 에 가깝지만 미묘하게 다릅니다. 이면 와 이라 최적 가 약 두 배 빠릅니다.
그래도 둘 다 에 비례합니다. 상수 배 개선일 뿐이며, 111강의 모멘텀이 로 차수를 바꾸는 것과는 성격이 다릅니다.
실무에서 를 쓰지 않는 이유는 를 모르기 때문입니다. 은 추정이 쉬워도 는 어렵고, 비볼록에서는 음수일 수도 있습니다. 그래서 근처를 씁니다.
심화 2. 정확한 직선탐색이 왜 지그재그를 만드는지 보이세요.
를 고정하지 않고 매 걸음 최적으로 고르면 어떻게 될까요.
이차함수에서 이 최소는 손으로 구해집니다. 라 두고 미분해 으로 놓으면
놀랍게도 이것이 상황을 개선하지 않습니다. 이유가 기하적입니다.
의 최소에서 이고, 97강의 연쇄법칙으로
연속한 두 기울기가 직교합니다.
직각으로 꺾으며 내려간다는 뜻이고, 이것이 정확히 지그재그입니다. 좁은 골짜기에서 직각으로만 꺾으면 앞으로 나아가는 성분이 작습니다.
탐욕적 선택의 한계이며, 111강의 모멘텀이 이를 고칩니다. 과거 방향을 섞으면 직교 제약이 풀려 골짜기를 따라갈 수 있습니다.
켤레기울기법은 더 나아갑니다. 직교 대신 -직교를 요구하면
차원에서 정확히 걸음에 최소에 도달합니다. 82강의 최소제곱을 푸는 표준 방법이며, 112강에서 다룹니다.
심화 3. 확률적 경사하강법을 예고하세요.
이 강의의 경사하강법은 전체 기울기를 씁니다. 기계학습의 손실은 대개 합 형태입니다.
이 수백만이면 한 걸음에 데이터 전부를 훑어야 합니다. 비용이 큽니다.
해법은 표본입니다. 무작위로 뽑은 미니배치 로 기울기를 추정합니다.
103강 심화 3의 차원의 저주와 같은 논리입니다. 정확한 값을 비싸게 구하는 대신 부정확한 값을 싸게 구합니다.
이 추정이 정당한 이유는 97강 심화 4에서 본 미분과 기댓값의 교환입니다.
불편추정량이므로 평균적으로는 옳은 방향입니다.
대가는 잡음입니다.
| 항목 | 전체 기울기 | 미니배치 |
|---|---|---|
| 한 걸음 비용 | ||
| 방향의 정확도 | 정확합니다 | 잡음이 섞입니다 |
| 수렴 | 최소로 수렴합니다 | 근방에서 맴돕니다 |
셋째 줄이 핵심입니다. 고정 학습률에서는 최소에 정착하지 못하고 잡음 크기에 비례하는 구역을 맴돕니다. 그래서 학습률을 줄여 가야 합니다.
로빈스-먼로 조건이며 236강에서 다룹니다. 가 대표적입니다.
96강 문제 4에서 예고한 것도 여기서 쓰입니다. 방향이 도 벗어나도 감소율의 가 남으므로, 잡음이 섞여도 예각이기만 하면 진전합니다.
잡음이 오히려 도움이 되기도 합니다. 101강 문제 5에서 고차원 임계점이 대개 안장이라 했는데, 잡음이 안장에서 밀어냅니다. 235강과 238강에서 다룹니다.
심화 4. 제약이 있으면 어떻게 되는지 예고하세요.
이 강의는 제약이 없는 문제를 다뤘습니다. 실행가능영역이 있으면 걸음이 밖으로 나갈 수 있습니다.
가장 단순한 해법이 사영입니다.
한 걸음 내딛고 밖으로 나갔으면 가장 가까운 실행가능점으로 되돌립니다. 가 사영이며 80강에서 다룬 정사영의 일반화입니다.
가 볼록이면 사영이 잘 정의됩니다.
사영 정리. 가 닫힌 볼록집합이면 임의의 점에서 로의 최근접점이 유일하게 존재합니다.
볼록성이 여기서도 필요합니다. 비볼록집합에서는 최근접점이 여럿일 수 있습니다.
사영이 쉬운 집합들을 적어 둡니다.
| 집합 | 사영 |
|---|---|
| 상자 \mathbf{a}\le\mathbf{x}\le\mathbf | 성분별 자르기 |
| 공 | 크기를 로 줄이기 |
| 부분공간 | 80강의 정사영 행렬 |
| 단체 | 알고리즘 |
| 비음수 | 음수를 으로 |
첫째 줄과 다섯째 줄이 실무에서 가장 흔합니다. 가중치를 특정 범위로 제한하거나 비음수로 제약할 때 씁니다.
사영이 어려우면 다른 방법을 씁니다. 113강의 라그랑주 승수법과 114강의 KKT 조건이 제약을 목적함수로 옮기는 방법이며, 05단원 전체가 이 주제입니다.
제약이 특별합니다. 116강에서 라소를 다루는데, 공으로의 사영이 계산 가능하고 근위 연산자로 더 깔끔하게 처리됩니다.
심화 5. 이 알고리즘이 어디까지 통하는지 정리하세요.
볼록이고 매끄러우면 이 강의의 분석이 그대로 적용됩니다. 그런데 실무의 문제는 대개 아닙니다.
첫째, 미분불가능한 경우입니다. 나 ReLU가 꺾인 곳에서 가 없습니다.
열등경사법을 씁니다. 107강 심화 4에서 본 열등미분에서 아무 원소나 골라 씁니다.
하강이 보장되지 않습니다. 열등경사 방향으로 가도 값이 늘 수 있고, 그래서 이 필요합니다. 수렴률도 로 느립니다.
둘째, 비볼록인 경우입니다. 하강 보조정리는 여전히 성립하지만(매끄러움만 필요) PL 부등식이 성립하지 않습니다.
"임계점에 가까워진다"만 보장되고 그것이 최소인지는 말하지 않습니다. 110강에서 유도합니다.
셋째, 확률적인 경우는 심화 3에서 다뤘습니다.
정리하면 다음과 같습니다.
| 가정 | 보장 |
|---|---|
| 볼록 + 매끄러움 | 로 최소에 수렴 |
| 강볼록 + 매끄러움 | 로 지수 수렴 |
| 매끄러움만 | 기울기가 로 감소 |
| 볼록만 | , 열등경사 |
| 아무것도 없음 | 보장 없음 |
신경망은 셋째 줄에 가깝습니다. 매끄러움도 엄밀히는 보장되지 않지만, 실용적으로는 이 틀에서 이해합니다.
같은 한 줄이 이 모든 경우에 쓰인다는 점이 이 알고리즘의 힘입니다. 가정이 좋으면 빠르고 나쁘면 느릴 뿐, 작동은 합니다.
심화 6. 110강부터 112강까지를 예고하세요.
이 강의에서 관찰했습니다. 110강이 그것을 증명하고, 111강과 112강이 고칩니다.
110강이 증명할 것은 이 강의가 수치로 본 것들입니다.
| 관찰 | 110강의 정리 |
|---|---|
| 이면 줄어듭니다 | 하강 보조정리의 반복 |
| 걸음이 에 비례합니다 | 선형 수렴률 |
| 이면 느립니다 | 수렴 |
| 비볼록이면 임계점만 | 기울기 노름의 감소 |
111강이 첫 번째 개선입니다. 심화 2에서 본 직교 제약을 모멘텀이 풉니다.
과거 방향을 누적하므로 골짜기를 따라 속도가 쌓이고 좌우 진동은 상쇄됩니다. 네스테로프 가속을 쓰면 걸음 수가
이면 걸음이 걸음이 됩니다. 차수가 바뀌는 개선이라 심화 1의 학습률 조정과는 성격이 다릅니다.
Adam은 다른 방향입니다. 성분마다 척도를 다르게 주어 유효 조건수 자체를 줄입니다. 96강 심화 3의 대각 노름에 해당합니다.
112강이 두 번째 개선입니다. 헤세를 써서 좌표를 바꿉니다.
96강 심화 3에서 본 대로 이 방향이 정확히 최소를 가리킵니다. 그때 헤세 노름 최급강하가 정답에서 도 벗어난다고 했습니다. 이차함수면 한 걸음에 끝나고, 일반 함수에서도 최소 근처에서 이차 수렴합니다.
대가는 비용입니다. 를 만들고 역행렬을 구해야 하며, 99강 심화 4에서 본 대로 이 크면 불가능합니다. 그래서 준뉴턴법과 절단 뉴턴법이 나옵니다.
04단원 전체가 하나의 표로 정리됩니다.
| 방법 | 걸음 수 | 한 걸음 비용 |
|---|---|---|
| 경사하강법 | ||
| 모멘텀 | ||
| 뉴턴법 | ||
| 준뉴턴법 | 중간 |
어느 열을 줄이느냐의 저울질이며, 의 크기가 선택을 정합니다.
import numpy as np
H = np.array([[1.0, 0.0], [0.0, 100.0]])
mu, L = 1.0, 100.0
f = lambda x: 0.5*(x @ H @ x)
gf = lambda x: H @ x
# --- 문제 1: 알고리즘을 돌려 본다 ---------------------------------------
print(" x_{k+1} = x_k - eta grad f(x_k), eta = 1/L = 0.01")
x = np.array([1.0, 1.0]); eta = 1.0/L
print(" k x_k f(x_k) |grad|")
for k in range(6):
print(" %4d (%+9.6f, %+9.6f) %11.6f %10.4f" % (k, x[0], x[1], f(x), np.linalg.norm(gf(x))))
x = x - eta*gf(x)
# x_{k+1} = x_k - eta grad f(x_k), eta = 1/L = 0.01
# k x_k f(x_k) |grad|
# 0 (+1.000000, +1.000000) 50.500000 100.0050
# 1 (+0.990000, +0.000000) 0.490050 0.9900
# 2 (+0.980100, +0.000000) 0.480298 0.9801
# 3 (+0.970299, +0.000000) 0.470740 0.9703
# 4 (+0.960596, +0.000000) 0.461372 0.9606
# 5 (+0.950990, +0.000000) 0.452191 0.9510
# y 는 곱수가 1-1*100*0.01 = 0 이라 한 걸음에 끝나고 x 는 0.99 씩만 줄어듭니다.
# --- 문제 2: 지그재그를 관찰한다 ----------------------------------------
print(" y 성분의 부호가 매 걸음 뒤집히는지 봅니다 (eta = 0.019)")
x = np.array([1.0, 1.0]); e = 0.019
sy = []
for k in range(8):
sy.append(x[1]); x = x - e*gf(x)
print(" y_k =", " ".join("%+.4f" % v for v in sy))
print(" x 성분은 단조 감소:")
x = np.array([1.0, 1.0]); sx = []
for k in range(8):
sx.append(x[0]); x = x - e*gf(x)
print(" x_k =", " ".join("%+.4f" % v for v in sx))
print(" 한 걸음 곱수: y 는 %+.4f, x 는 %+.4f" % (1 - e*100, 1 - e*1))
# y 성분의 부호가 매 걸음 뒤집히는지 봅니다 (eta = 0.019)
# y_k = +1.0000 -0.9000 +0.8100 -0.7290 +0.6561 -0.5905 +0.5314 -0.4783
# x 성분은 단조 감소:
# x_k = +1.0000 +0.9810 +0.9624 +0.9441 +0.9261 +0.9085 +0.8913 +0.8743
# 한 걸음 곱수: y 는 -0.9000, x 는 +0.9810
# 지그재그는 곱수가 음수인 성분입니다.
# --- 문제 3: 학습률에 따른 거동 -----------------------------------------
print(" eta 200걸음 뒤 f 판정")
for e in [0.001, 0.01, 0.0198, 0.02, 0.0201]:
x = np.array([1.0, 1.0])
for _ in range(200): x = x - e*gf(x)
v = f(x); r = abs(1 - e*L)
if r > 1.0 + 1e-12: kind = "발산 (|1-eta L| = %.4f > 1)" % r
elif abs(r - 1.0) <= 1e-12: kind = "진동 (|1-eta L| = 1, 줄지 않음)"
elif v < 1e-2: kind = "수렴 (|1-eta L| = %.4f)" % r
else: kind = "느림 (|1-eta L| = %.4f)" % r
print(" %7.4f %18.6e %s" % (e, v, kind))
# eta 200걸음 뒤 f 판정
# 0.0010 3.350930e-01 느림 (|1-eta L| = 0.9000)
# 0.0100 8.975277e-03 수렴 (|1-eta L| = 0.0000)
# 0.0198 1.563462e-02 느림 (|1-eta L| = 0.9800)
# 0.0200 5.000015e+01 진동 (|1-eta L| = 1, 줄지 않음)
# 0.0201 2.676206e+03 발산 (|1-eta L| = 1.0100 > 1)
# 한 수 |1-eta L| 이 네 가지 거동을 모두 가릅니다.
# --- 문제 4: 조건수와 걸음 수 -------------------------------------------
print(" kappa 실제 걸음 수(f<1e-6) 이론 kappa*log(1/eps)")
for kap in [1.0, 10.0, 100.0, 1000.0]:
Hk = np.array([[1.0, 0.0], [0.0, kap]])
e = 1.0/kap # eta = 1/L
x = np.array([1.0, 1.0]); k = 0
f0 = 0.5*(x @ Hk @ x)
while 0.5*(x @ Hk @ x) > 1e-6*f0 and k < 2000000:
x = x - e*(Hk @ x); k += 1
print(" %7.0f %18d %18.0f" % (kap, k, kap*np.log(1e6)))
# kappa 실제 걸음 수(f<1e-6) 이론 kappa*log(1/eps)
# 1 1 14
# 10 55 138
# 100 458 1382
# 1000 3452 13816
# 이론은 최악의 경우라 세 배쯤 크지만 kappa 비례는 그대로입니다.
# --- 문제 5: 종료 조건 ---------------------------------------------------
print(" 기울기 기준으로 멈출 때 실제 최적성 간격")
print(" 기준 |grad| 멈춘 f-f* 상한 |g|^2/(2mu)")
for tol in [1e-1, 1e-2, 1e-3]:
x = np.array([1.0, 1.0]); e = 0.01
while np.linalg.norm(gf(x)) > tol:
x = x - e*gf(x)
g = gf(x)
print(" %12.0e %14.6e %16.6e" % (tol, f(x), (g @ g)/(2*mu)))
print(" kappa = 1 이면 eta = 1/L = 1 로 한 걸음에 끝납니다")
H1 = np.eye(2); x = np.array([1.0, 1.0]); k = 0
while np.linalg.norm(H1 @ x) > 1e-12:
x = x - 1.0*(H1 @ x); k += 1
print(" 걸음 수 %d, 최종 f = %.1f" % (k, 0.5*(x @ H1 @ x)))
# 기울기 기준으로 멈출 때 실제 최적성 간격
# 기준 |grad| 멈춘 f-f* 상한 |g|^2/(2mu)
# 1e-01 4.910882e-03 4.910882e-03
# 1e-02 4.921286e-05 4.921286e-05
# 1e-03 4.931713e-07 4.931713e-07
# kappa = 1 이면 eta = 1/L = 1 로 한 걸음에 끝납니다
# 걸음 수 1, 최종 f = 0.0
# 수렴한 지점이 mu 방향이라 PL 부등식이 등호가 되어 상한이 정확합니다.
문제 3의 표가 이 강의의 요지입니다. 네 가지 거동이 하나로 완전히 갈립니다.
110강에서 이 관찰을 정리로 만듭니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 학습률, 걸음 크기 | 한 걸음의 배율입니다 | |
| 반복행렬 | 이차함수의 한 걸음입니다 | |
| 1-\eta\lambda_ | 성분별 곱수 | 그 방향의 수렴 인자입니다 |
| 수렴률 | 곱수의 최댓값입니다 | |
| 최적 학습률 | 수렴률 입니다 | |
| 지그재그 | zigzag | 곱수가 음수인 성분의 거동입니다 |
| 직선탐색 | line search | 매 걸음 를 최적화합니다 |
| \Pi_ | 사영 | 실행가능영역으로 되돌립니다 |
| 열등경사 | subgradient | 미분불가능한 곳의 대체입니다 |
다음 110강에서는 학습률과 수렴 속도를 다룹니다. 이 강의가 수치로 관찰한 것을 정리로 만듭니다. 108강의 하강 보조정리와 PL 부등식을 합쳐 선형 수렴을 증명하고, 강볼록이 아닌 경우와 비볼록인 경우로 넓힙니다. 그리고 를 고정하지 않고 줄여 가는 일정이 왜 필요한지 봅니다.