볼록이면 왜 쉬운가: 극소가 곧 최소

혼동하기 쉬운 점과 요약

토론 1. 볼록 함수의 최소점은 하나인가

가중치 둘, 데이터 하나인 회귀의 손실 ½(w₁ + w₂ − 1)²은 볼록이다. 최소점은 몇 개이고, 경사하강은 어디에 닿는가?

선생님 T01
선생님

가중치가 둘인데 데이터는 하나뿐인 회귀를 생각해 봐요. 손실은 ½(w₁ + w₂ − 1)²이고 볼록이에요. 최소점은 몇 개일까요?

이서연 S01
이서연

볼록 함수는 극소가 곧 최소니까, 내려가다 멈추는 데가 하나로 정해지겠죠. 최소점도 하나일 것 같아요.

김민준 M03
김민준

학습률 0.1로 (0, 0)에서 출발하면 (0.5, 0.5), (2, 0)에서 출발하면 (1.5, −0.5), (−1, 3)에서 출발하면 (−1.5, 2.5)에 닿아. 손실은 셋 다 0이야.

이서연 S06
이서연

세 점이 다 다른데 손실은 다 0이네. w₁ + w₂ = 1이기만 하면 0이니까… 최소점이 직선 하나 전체구나.

선생님 T02
선생님

볼록이라는 성질이 보장한 것은 무엇이었죠?

이서연 S04
이서연

멈춘 곳의 높이가 가장 낮다는 거였어요. 최소점이 하나라는 건 보장하지 않았네요. max(|x| − 1, 0)에서 −1부터 1까지가 다 최소점이던 것도 같은 일이고요.

선생님 T01
선생님

그럼 하나로 정해지게 하려면 무엇을 더하면 될까요?

김민준 M01
김민준

가중치 감쇠요. ½ × 0.1 × |w|²을 더해서 세 출발점에서 다시 돌리면 셋 다 (0.4762, 0.4762)에 닿아요. 손실은 0.0238이고요.

이서연 S01
이서연

곡률이 어느 방향으로나 0.1 이상이 됐으니까 강볼록이야. 직선을 따라 평평하던 방향에도 곡률이 생긴 거고.

선생님 T14
선생님

그래요. 볼록이면 최소의 높이는 하나지만 최소점은 구간이나 직선 전체일 수 있어요. 최소점이 하나로 정해지는 것은 강볼록일 때예요. 파라미터가 데이터보다 많은 모델에서 어디에 닿는지는 출발점과 옵티마이저가 정한다는 것도 이 장면에서 나와요.

토론 2. 학습 데이터에 멀리 있는 점을 더하면 분류 직선이 움직이나

SVM 예의 점 12개에 마진 가장자리에서 아주 먼 점을 100개 더 찍으면 직선은 어떻게 되는가? 로지스틱 회귀라면?

선생님 T01
선생님

서포트 벡터 예의 점 12개에, 마진 가장자리에서 아주 먼 곳에 같은 클래스의 점 100개를 더 찍는다고 해 봐요. 직선은 어떻게 될까요?

김민준 M01
김민준

점이 100개나 늘면 그 클래스의 무게중심이 크게 옮겨 가니까, 직선도 그쪽으로 끌려가겠죠.

이서연 S01
이서연

새로 찍은 점들은 마진 가장자리에 닿아 있어?

김민준 M03
김민준

멀리 있으니까 안 닿지. … 그럼 넷째 조건 때문에 승수가 0이네.

선생님 T02
선생님

승수가 0인 점은 직선을 적는 합에 어떻게 들어가죠?

김민준 M04
김민준

w = Σνᵢyᵢxᵢ에서 0을 곱해 빠져요. 100개를 더해도 직선은 그대로예요. 무게중심으로 생각한 게 엇나갔네요. SVM은 평균을 보는 게 아니었어요.

이서연 S03
이서연

그럼 로지스틱 회귀도 그래? 거기도 멀리 있는 점은 무시해?

선생님 T01
선생님

로지스틱 회귀에서 점 하나가 그래디언트에 보태는 무게는 σ(−점수)예요. 점수 y(w·x + b)가 1, 2.18, 10인 점이면요?

김민준 M05
김민준

0.269, 0.101, 0.0000454예요. 작아지긴 하는데 0이 되지는 않네요.

이서연 S07
이서연

그러니까 로지스틱 회귀에서는 먼 점도 아주 조금씩은 직선을 당기고, 100개를 더하면 그 조금이 쌓여. SVM은 마진 가장자리 밖의 점에 승수 0을 주니까 정말로 아무 역할도 안 하고. 직선을 정하는 건 가장자리에 걸친 서포트 벡터뿐이야.

혼동하기 쉬운 점

혼동하기 쉬운 생각 나온 문제 바로잡는 법
계속 내려가기만 하면 결국 가장 낮은 곳에 닿는다고 봄 1 경사하강은 둘레보다 낮은 곳(극소)에서 멈춘다. 가장 낮은 곳(최소)과 같다는 보장은 함수가 볼록일 때 있다
꺾인 데가 있으면 볼록이 아니라고 봄 2 볼록은 현으로 정의한다. 미분할 수 없어도 현이 그래프 아래로 내려가지 않으면 볼록이다
볼록 함수의 최소점은 하나라고 봄 토론 1 극소가 모두 최소라는 말은 멈춘 곳의 높이가 같다는 뜻이다. 최소점이 구간 전체일 수도 있다. 하나로 정해지는 것은 강볼록일 때다
극소가 모두 최소면 볼록이라고 봄 2 거꾸로는 성립하지 않는다. (x² − 1)²는 극소가 모두 최소지만 볼록이 아니다
파라미터가 많이 다르면 손실도 다르다고 봄 3 은닉 유닛을 맞바꾼 신경망은 파라미터가 멀어도 손실이 같다. 그 가운데 점의 손실이 높아서 신경망의 손실은 볼록이 아니다
출발이 같으면 끝나는 때도 비슷하다고 봄 4 최소점 근처의 곡률이 0이면 스텝이 거리보다 빨리 짧아져 비율로 줄지 않는다. 곡률이 μ > 0 이상이어야 스텝마다 같은 비율로 준다
볼록이 아니면 같은 비율로 줄 수 없다고 봄 5 비율을 보장한 것은
손실이 계속 줄면 파라미터도 수렴한다고 봄 6 다 분리할 수 있는 데이터의 로지스틱 회귀는 최소점이 없어(무한히 멀리 있어) 가중치가 끝없이 자란다. 가중치 감쇠를 더하면 강볼록이 되어 최소점이 생긴다
제약을 지키는 둘을 섞으면 늘 제약을 지킨다고 봄 7 제약이 볼록 집합일 때만 그렇다. 「이거나」로 이은 규칙은 제약을 쪼갠다
제약이 매끈하면 문제가 쉽다고 봄 8 결정하는 것은 매끈함이 아니라 볼록 집합인지다. 모서리 있는 상자는 볼록이고, 매끈한 원(길이가 정확히 1)은 볼록이 아니다
승수를 제약을 늦출 때의 변화량으로 그대로 씀 9 승수는 지금 제약 값에서 측정한 최솟값의 변화율이다. 제약을 크게 늦추면 실제 변화는 승수와 다르다
KKT 첫 줄만 만족하면 답이라고 봄 10 ν ≥ 0과 νc(θ*) = 0까지 네 줄을 모두 따진다. ν < 0인 점은 제약이 막고 있지 않은 점이다
멀리 있는 샘플이 SVM 직선을 크게 바꾼다고 봄 토론 2 마진 가장자리 밖의 샘플은 승수가 0이라 직선에 아무 역할을 하지 않는다. 직선은 서포트 벡터가 정한다

요약

학습 규칙도 학습률도 같은데 왜 로지스틱 회귀는 출발점을 잊고 신경망은 출발점이 도착지를 정했을까? 로지스틱 회귀의 손실은 볼록이고, 은닉 유닛을 맞바꿔도 같은 손실을 내는 신경망의 손실은 볼록일 수 없기 때문이다. 볼록이면 발밑만 보고 멈춘 곳이 곧 가장 낮은 곳이고, 멈춘 자리의 그래디언트 조건(제약이 없으면 그래디언트 0, 제약에 닿았으면 KKT 조건)이 최소의 증거가 된다.

경사하강은 그래디언트가 0인 곳에서 멈추고, 그곳은 둘레보다 낮은 극소점일 뿐이다. 그릇 모양과 W자 모양의 4차 함수를 같은 규칙으로 내려가면, 그릇에서는 어디서 출발해도 같은 최소점에 닿고 W자에서는 출발점이 도착지를 정한다. 둘을 구분한 것은 현이 그래프 아래로 내려가는지였다. 어느 두 점의 현도 그래프 아래로 내려가지 않는 볼록 함수에서는, 현 부등식 하나만으로 극소가 곧 최소임을 증명할 수 있다.

볼록 함수라도 얼마나 빨리 닿는지는 최소점 근처의 곡률이 정한다. 최소점에서도 곡률이 μ 이상인 강볼록 함수는, 그래디언트의 립시츠 상수 L에 맞춘 학습률(η ≤ 1/L)로 남은 오차가 스텝마다 1 − ημ배 아래로 준다. 강볼록이 아닌 볼록 함수는 1/k로 준다는 것까지만 장담할 수 있다. 비율을 보장한 핵심은 |∇f|² ≥ 2μ(f − f*)라는 폴랴크의 조건이고, 가중치 감쇠는 이 μ를 손실에 더한다.

제약이 있어도 제약이 볼록 집합이면 극소는 곧 최소인데, 같은 증명이 「두 점을 잇는 선분이 제약 안에 있다」는 한 줄을 더 쓸 뿐이다. 원판은 볼록 집합이라 사영 경사하강이 어디서 출발해도 한 점에 닿고, 말굽이나 원(길이가 정확히 1)은 볼록 집합이 아니라 도착지가 달라진다. 제약에 닿은 최소점은 KKT 조건으로 알아본다. 손실의 그래디언트와 제약 함수의 그래디언트가 승수 ν ≥ 0으로 맞서고, 제약에 닿지 않으면 ν = 0이다. 볼록 문제에서는 KKT 조건이 충분조건이 되고, 승수는 제약을 한 단위 늦출 때 최솟값이 내려가는 양이다. SVM의 서포트 벡터는 승수가 0이 아닌 샘플이다.

정리 연습문제

물음. 경사하강이 멈춘 곳이 가장 낮은 곳(최소)이라고 장담할 수 있는 것은 언제인가?

  • [ ] 계속 내려가기만 하면 언제나 장담할 수 있다 〔틀림: 경사하강은 둘레보다 낮기만 한 극소에서도 멈춘다.〕
  • [x] 함수가 볼록일 때 〔맞음: 볼록 함수에서는 현 부등식 하나로 극소가 모두 최소임을 증명할 수 있다.〕
  • [ ] 학습률을 아주 작게 잡으면 언제나 장담할 수 있다 〔틀림: 학습률이 작아도 W자 모양 함수에서는 출발점이 도착지를 정한다.〕

물음. 절댓값 함수 |x| 는 0에서 꺾여 미분할 수 없다. 이 함수는 볼록인가?

  • [ ] 꺾인 데가 있으니 볼록이 아니다 〔틀림: 볼록은 미분이 아니라 현으로 정의한다.〕
  • [x] 볼록이다. 어느 두 점을 이은 현도 그래프 아래로 내려가지 않는다 〔맞음: 미분할 수 없는 점이 있어도 현 조건만 지키면 볼록이다.〕
  • [ ] 극소가 모두 최소이니 그것만으로 볼록이다 〔틀림: 거꾸로는 성립하지 않는다. 극소가 모두 최소인데도 볼록이 아닌 (x² − 1)² 같은 함수가 있다.〕

물음. 볼록 함수의 최소점에 대해 옳은 것은 어느 것인가?

  • [ ] 늘 한 점이다 〔틀림: 바닥이 평평하면 구간 전체가 최소점일 수 있다.〕
  • [ ] 여러 개일 수 있고, 높이가 서로 다를 수 있다 〔틀림: 볼록이면 극소가 모두 최소라서, 멈춘 곳의 높이는 모두 같다.〕
  • [x] 여러 개일 수 있지만 높이는 모두 같다 〔맞음: 최소점이 하나로 정해지는 것은 최소점에서도 곡률이 0보다 큰 강볼록일 때다.〕

물음. 학습률을 그래디언트의 립시츠 상수에 맞춰 잡고 경사하강을 돌린다. 남은 오차가 스텝마다 같은 비율로 줄어든다고 장담할 수 있는 것은 언제인가?

  • [ ] 함수가 볼록이기만 하면 된다 〔틀림: 최소점 근처의 곡률이 0이면 스텝이 거리보다 빨리 짧아져 비율로 줄지 않는다. 볼록만으로는 스텝 수에 반비례해 준다는 것까지 장담한다.〕
  • [x] 최소점 근처에서도 곡률이 0보다 큰 수 이상으로 남아 있을 때 〔맞음: 강볼록 함수가 그렇다. 비율을 보장하는 것은 그래디언트가 남은 오차에 비해 충분히 크다는 폴랴크의 조건이다.〕
  • [ ] 볼록이 아니면 어떤 경우에도 같은 비율로 줄 수 없다 〔틀림: 폴랴크의 조건은 볼록이 아니어도 그래디언트가 0인 곳이 최소점뿐이면 성립할 수 있다.〕

물음. 볼록 손실을 제약 안에서 사영 경사하강으로 줄인다. 제약 안의 극소가 모두 최소라고 장담하려면 제약에 무엇이 필요한가?

  • [ ] 제약의 경계가 매끈한 것 〔틀림: 길이가 정확히 1이라는 원 제약은 매끈하지만 볼록 집합이 아니라 도착지가 달라진다.〕
  • [ ] 제약에 모서리가 없는 것 〔틀림: 모서리 있는 상자도 볼록 집합이라 괜찮다. 모서리는 상관없다.〕
  • [x] 제약이 볼록 집합인 것 〔맞음: 두 점을 잇는 선분이 제약 안에 있으면, 제약이 없을 때와 같은 증명으로 극소가 모두 최소다.〕

물음. 학습한 SVM 의 마진 가장자리보다 훨씬 바깥, 올바른 편에 샘플 하나를 더하고 다시 학습한다. 분류 직선은 어떻게 되는가?

  • [ ] 샘플이 하나 늘었으니 조금이라도 움직인다 〔틀림: 마진 밖의 샘플은 승수가 0이라 직선에 아무 역할을 하지 않는다.〕
  • [ ] 멀리 있는 샘플일수록 크게 끌어당긴다 〔틀림: 멀리 있을수록 제약에 닿지 않아 승수가 0이다.〕
  • [x] 움직이지 않는다 〔맞음: 직선은 승수가 0이 아닌 샘플, 서포트 벡터만으로 정해진다.〕

막힌 곳

이 장의 보장은 모두 손실이 볼록이라는 데 기댔지만, 파라미터가 수십억 개인 신경망들은 손실이 볼록이 아니어도 씨앗을 바꿔 돌리면 대개 비슷하게 낮은 손실에 닿는다. 볼록이 아닌데 왜 학습이 이렇게 잘 될까?