이 단원은 113강부터 116강까지를 맡습니다. 실행가능영역을 더합니다.
04단원에서 최소를 찾는 알고리즘을 세웠고, 그 전제는 하나였습니다.
∇f(x∗)=0
제약이 있으면 이 조건이 성립하지 않습니다.
xminf(x)subject tog(x)=0, h(x)≤0
최소점이 제약에 갇혀 있으므로, 자유로웠다면 더 내려갔을 자리에 멈춰 섭니다. 그 점에서 기울기가 0일 이유가 없습니다.
답이 이미 있었습니다. 95강 문제 4에서 기울기가 등고선에 수직임을 증명했고, 심화 4에서 이것이 라그랑주 승수법의 근거라 예고했습니다.
제약곡선 g=0은 g의 등위집합입니다. 그 위를 움직여도 f가 늘지 않아야 하고, 움직일 수 있는 방향은 ∇g에 수직인 것뿐입니다.
∇f⊥(제약 방향),∇g⊥(제약 방향)
같은 방향에 수직인 두 벡터는 평행합니다.
∇f=λ∇g
한 문장의 기하가 단원 전체를 낳습니다.
승수는 제약의 가격입니다
| 강의 |
가격의 형태 |
| 113 |
df∗/dc=λ, 잠재가격 |
| 114 |
df∗/dt=−μ, 부호가 정해짐 |
| 115 |
쌍대변수, 자원의 가격 |
| 116 |
복잡도 한 단위의 훈련오차 |
네 강의가 같은 양을 네 번 다르게 부릅니다. 검산에서 매번 소수점까지 정확히 일치합니다.
이 단원의 강의는 개념을 먼저 나열하지 않습니다. 문제를 먼저 던지고, 그 문제를 푸는 과정에서 개념과 공식을 끌어냅니다. 각 문제는 문제, 생각의 실마리, 풀이, 이 문제에서 배우는 것, 바로 확인의 다섯 단계로 진행합니다.
등식 제약은 언제나 경계에 붙어 있습니다. 부등식은 붙을 수도 안 붙을 수도 있고, 어느 쪽인지 미리 모릅니다.
| 상황 |
이름 |
다루는 법 |
| h(x∗)=0 |
활성 |
등식처럼 |
| h(x∗)<0 |
비활성 |
없는 것처럼 |
제약이 m개면 조합이 2m가지라 하나씩 시도할 수 없습니다.
114강이 그 둘을 하나의 방정식으로 묶습니다.
μh=0
**"둘 중 하나는 0"**이며 이것이 상보성입니다. 그리고 새로 생긴 부호 조건 μ≥0은 억지 규칙이 아니라 논리의 결과입니다.
영역을 넓히면 최솟값이 늘 수 없으므로 df∗/dt≤0
115강이 순서를 바꿔 봅니다.
xminμ≥0maxLvsμ≥0maxxminL
뒤쪽이 언제나 앞쪽 이하입니다. 먼저 움직이는 쪽이 불리하기 때문이며, 이것이 약쌍대성입니다.
볼록이면 둘이 같아집니다. 그렇지 않으면 간극이 생기며, 검산에서 이산 제약 문제의 간극이 정확히 1입니다.
| 문제 |
실행가능집합 |
간극 |
| minx2 s.t. x≥1 |
볼록 |
0 |
| 정수계획 |
이산 |
1 |
쌍대 간극은 볼록화에서 잃은 정보입니다
116강이 이 단원을 기계학습으로 잇습니다.
minL(w)+λ∥w∥2⟺minL(w) s.t. ∥w∥2≤t
λ가 승수의 기호인 것이 우연이 아닙니다. 검산에서 d(RSS)/dt=−λ가 정확히 성립합니다.
그리고 90강 문제 1의 예고가 회수됩니다. 그때 ℓ1 단위구가 마름모라 그 꼭짓점이 축 위에 있어 해가 축에 붙기 쉽다고 했는데, 이 강의가 그 말을 정확히 합니다.
| 목표 |
ℓ2 해 |
ℓ1 해 |
| (1.5,0.2) |
(0.9912,0.1322) |
(1,0) |
| (1,0.35) |
(0.9439,0.3303) |
(0.825,0.175) |
첫 줄에서 꼭짓점에 붙어 성분이 0이 되고, 둘째 줄에서는 그렇지 않습니다. 희소성은 보장이 아니라 경향입니다.
- 이 단원은 113,114,115,116강 순서로 읽어야 합니다.
- 74강의 네 부분공간이 113강 심화 1의 증명입니다.
- 80강의 정사영이 114강 문제 5의 일반화입니다.
- 86강의 레일리 몫이 113강 심화 3에서 라그랑주 문제로 다시 나옵니다.
- 88강의 특이값이 116강 심화 5의 핵노름입니다.
- 90강의 ℓ1 단위구가 116강 희소성의 기하입니다.
- 95강 문제 4가 이 단원 전체의 씨앗입니다.
- 97강의 연쇄법칙이 113강 포락선 정리의 증명입니다.
- 107강의 볼록성이 114강 심화 2와 115강 강쌍대성의 전제입니다.
- 108강의 매끄러움이 116강 심화 2의 근위 경사법에 쓰입니다.
- 112강의 뉴턴법이 113강 심화 4의 KKT 행렬로 확장됩니다.
- 등식 제약과 라그랑주 승수
- 부등식 제약과 KKT 조건
- 쌍대 문제 입문
- 정규화를 제약으로 읽기
-
- 등식 제약과 라그랑주 승수
제약이 있으면 ∇f=0이 조건이 아님을 보이고, 두 기울기가 평행해야 함을 증명합니다. 라그랑주 함수로 제약 문제를 제약 없는 문제로 바꾸고, 승수가 제약 완화의 잠재가격임을 확인합니다.
-
- 부등식 제약과 KKT 조건
활성과 비활성을 구별하고 상보성 조건으로 둘을 묶습니다. 승수의 부호 조건이 완화 방향에서 나옴을 보이고, 사영이 KKT 해임을 확인합니다.
-
- 쌍대 문제 입문
쌍대 함수를 정의하고 약쌍대성을 증명합니다. 이산 제약에서 간극이 생김을 수치로 보이고, 안장점과 최소최대 교환의 관계를 다루며, SVM 쌍대에서 지지 벡터가 나오는 이유를 봅니다.
-
- 정규화를 제약으로 읽기
벌점 형태와 제약 형태가 같은 문제임을 보이고 λ가 승수임을 확인합니다. 연성 문턱을 유도해 희소성의 근거를 밝히고, 두 공의 기하 차이가 결과를 가름을 봅니다.
- 제약이 있는데 ∇f=0을 찾고 있지 않은가?
- 제약자격을 확인했는가?
- 라그랑주 함수를 최소화하려 하지 않았는가?
- 활성인지 비활성인지 판정했는가?
- 승수의 부호 조건을 지켰는가?
- 상보성을 빠뜨리지 않았는가?
- KKT를 충분조건으로 오해하지 않았는가?
- 쌍대 간극이 없다고 가정하지 않았는가?
- 벌점과 제약을 다른 문제로 보지 않았는가?
- ℓ1이 항상 희소해를 준다고 믿지 않았는가?
- 등식 제약 문제를 라그랑주 조건으로 풀 수 있습니다.
- 승수를 잠재가격으로 해석할 수 있습니다.
- KKT 조건을 세우고 확인할 수 있습니다.
- 활성집합의 기하적 의미를 설명할 수 있습니다.
- 쌍대 함수를 계산하고 하한으로 쓸 수 있습니다.
- 강쌍대성의 조건을 판정할 수 있습니다.
- 정규화를 제약으로 읽고 λ의 뜻을 말할 수 있습니다.
- ℓ1 희소성의 기하적 근거를 설명할 수 있습니다.
| 이 단원의 것 |
쓰이는 곳 |
| 라그랑주 승수 |
289강 PPO의 KL 제약 |
| KKT 상보성 |
214강 SVM의 지지 벡터 |
| 쌍대와 커널 |
214강 커널 기법 |
| 약쌍대성 하한 |
정수계획의 분기한정법 |
| 최소최대와 안장점 |
272강 GAN |
| 연성 문턱 |
211강 라소, 근위 방법 |
| 정규화의 승수 해석 |
210강 편향-분산, 212강 교차검증 |
| 켤레함수 |
203강 KL, 262강 ELBO |
다섯째 줄이 특히 어렵습니다. GAN은 최소최대 게임이라 안장점을 찾아야 하는데, 최소화보다 훨씬 까다롭습니다. 115강 심화 3에서 원시-쌍대 방법을 다루며 그 어려움의 뿌리를 봅니다.
117강부터 시작하는 06단원 미분방정식과 흐름은 방향을 바꿉니다.
dtdx=−∇f(x)
최적화를 시간에 따라 흐르는 연속 과정으로 봅니다. 109강의 경사하강법이 이 미분방정식을 이산화한 것이며, 그 관점에서 여러 가지가 새로 보입니다.
| 강의 |
하는 일 |
| 117 |
1계 미분방정식을 세웁니다 |
| 118 |
선형 미분방정식과 안정성 |
| 119 |
경사흐름과 연속시간 최적화 |
| 120 |
수치 적분법: 오일러법과 룽게쿠타법 |
118강이 101강과 만납니다. 평형점의 안정성을 야코비의 고유값으로 판정하는데, 경사흐름에서 그 야코비가 −H이므로 극소가 안정한 평형점이고 안장이 불안정한 평형점입니다.
119강이 111강을 다시 봅니다. 모멘텀이 감쇠 진동 방정식의 이산화였고, 그 관점에서 최적 감쇠를 물리로 이해할 수 있습니다.
120강 뒤에 관문 3이 있으며 62강부터 120강까지를 섞어 묻습니다.