Local Minima 문제에 대한 새로운 시각

기계학습 2015.03.23 11:29

작년(2014년)에 local minima 문제에 대한 흥미로운 논문이 하나 발표되었다. 정식으로 출판된 논문은 아니고 arXiv(아카이브)에만 등록된 논문이다. => NIPS 2014에서 발표된 논문이라고 합니다.


[Dauphin14] Y. Dauphin, R. Pascanu, C. Gulcehre, K. Cho, S. Ganguli, Y. Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization.


Local minima 문제는 에러를 최소화시키는 최적의 파라미터를 찾는 문제에 있어서 아래 그림처럼 파라미터 공간에 수많은 지역적인 홀(hole)들이 존재하여 이러한 local minima에 빠질 경우 전역적인 해(global minimum)를 찾기 힘들게 되는 문제를 일컫는다.


<그림 1> local minima 문제


그리고 기존에 기계학습(machine learning)이 잘 안되거나 성능이 잘 안나오는 이유는 학습 도중 이러한 local minima에 빠졌기 때문이라는 게 일반적인 상식이었다.


하지만 이 논문은 기존의 상식을 깨고 local minima 문제가 사실은 고차원(high dimensional)의 공간에서는 발생하기 힘든 매우 희귀한 경우라고 주장한다.


그 이유는 예를 들어, local minimum이 형성되기 위해서는 함수의 변화 그래프가 모든 축의 방향으로 밥그릇처럼 오목한 형태가 되어야 하지만 아래 그림의 p처럼 어느 한 방향이라도 아래로 흘러내리면 local minima가 형성되지 않기 때문이다. 그리고 고차원의 공간에서 모든 축의 방향으로 오목한 형태가 형성될 확률은 거의 0에 가깝다는게 주장의 요지이다.


<그림 2> 그림출처: [Dauphin14]


함수 최적화 문제를 풀때 일차적으로는 미분값이 0인 즉, f' = 0인 지점을 찾는 것이 일반적이다. 그리고 일차 미분이 0인 지점을 critical point라 부른다. 어떤 critical point가 local minima가 되기 위해서는 모든 축의 방향으로 함수 그래프가 아래로 볼록(f''>0)이 되어야만 한다. 즉, n차원의 다변수 함수 f(x1, x2, ..., xn)이 있을 때 다음의 조건을 만족해야 한다.


 --- (1)


Critical point에서 모든 축 방향으로 곡률(이차미분)이 양수인 경우는 위로 볼록, 아래로 볼록이 랜덤하게 발생한다고 가정하면 차원이 증가할수록 확률적으로 매우 힘든 일이므로(1/2n) 대부분의 critical point는 local minima가 아니라는 것이다.


처음 이 내용을 접했을 때 꽤나 신선하고 재미있는 주장이라고 생각했다. 그러면서 정말 그럴까? 그렇다면 고차원의 최적화 문제에 대해서는 이제 더이상 local minima 문제를 걱정하지 않아도 되는 것일까? 하는 의구심도 들었다.


먼저, [Dauphin14] 논문의 내용을 그대로 옮겨보면 다음과 같다.


Intuitively, in high dimensions, the chance that all the directions around a critical point lead upward is exponentially small w.r.t. the number of dimensions, unless the critical point is the global minimum or stands at an error level close to it, i.e., it is unlikely one can find a way to go further down.


즉, 고차원의 공간에서 발생하는 critical point(일차 미분이 0인 지점)는 거의 대부분 saddle point이며 만일 saddle point가 아닌 경우는 global minimum이거나 또는 global minimum과 유사한 수준의 local minima라는 것이다.


잘 보면 이 내용에는 2가지 주장이 함께 섞여 있다. 하나는 고차원의 공간에서 대부분의 critical point는 local minima가 아니라 saddle point라는 점이다. 그리고 다른 한가지는 고차원의 공간에서 설령 local minima가 발생한다 하더라도 이는 global minimum이거나 또는 global minimum과 거의 유사한 수준의 에러 값을 갖는다는 것이다.


먼저 첫번째 주장은 비교적 직관적으로 쉽게 수긍할 수 있다. Critical point란 모든 축의 방향으로 일차 미분값이 0인 지점(f' = 0)으로서 다른 말로 stationary point라고도 한다. 그리고 이러한 critical point에는 크게 극대점(maxima), 극소점(minima), 그리고 saddle point가 있는데 saddle point란 극대 또는 극소가 아닌 모든 critical point로 정의된다. 따라서, 고차원의 공간에서 critical point는 대부분 확률적으로 saddle point인 것으로 볼 수 있다.


그런데 두 번째 주장 즉, 고차원의 공간에서 발생하는 local minima는 global minimum이거나 또는 global minimum과 거의 유사한 수준의 에러 값을 갖는다는 점에 대해서는 쉽게 수긍이 가지 않는다.


논문에서는 그 근거로서 실험적으로 critical point들에서 에러를 측정해 보니 critical point에 포함된 위로 볼록인 방향축의 비율이 크면 클수록 높은 에러를 가진다는 실험 결과를 예로 든다. 그리고 local minim는 위로 볼록인 경우가 하나도 없는 경우이기 때문에 결과적으로 매우 낮은 에러를 갖게 될 것이라는 게 이들의 주장이다.


하지만 차원이 증가할수록 만일 critical point 자체의 수도 같이 증가한다면 여전히 local minima도 다수 존재하게 되는 것은 아닐까 하는 의문이 든다. 그리고 고차원의 세계에서는 그만큼 어떤 예측하기 힘든 다양성들이 존재할텐데 global minimum 하나밖에 존재하지 않는다는 것은 그 자체로 상상하기 힘든 측면이 있다.


그리고 두 번째 주장에 대해서는 하나의 실험적 사례 외에는 별다른 논리적 근거가 제시되어 있지 않다. 그리고 그 실험적 사례 또한 local minima가 global minimum에 근접할 것이라는 직접적인 증거는 되지 못한다고 생각한다. 그건 하나의 실험 예에서 높은 에러를 가진 local minima를 발견하지 못했다고 해서 다른 문제에서도 나타나지 않을 것이라고 일반화하긴 힘들다고 생각하기 때문이다.


하지만 아직은 이들의 주장이 명확하게 증명되거나 반증된 것이 아니기 때문에 어떤 것이 사실인지는 알지 못한다.


☞ 이 글에서는 local minima의 존재 여부에만 초점을 맞추었지만 사실 [Dauphin14] 논문의 초점은 조금 다른데 있습니다. 이 논문의 핵심은 "Critical point 근처에서는 함수의 수렴속도가 느려지기 때문에 기존의 기계학습이나 최적화 기법에서 변화가 거의 없이 정체가 되는 현상이 발생하였는데 이를 기존에는 local minima 문제라고 착각하였다. 하지만 사실은 이들이 local minima가 아니라 실제로는 대부분 saddle point들이며 기존 기계학습 방법 또는 최적화 기법들이 잘 동작하지 않았던 이유는 기존 탐색 방법이 saddle point에서 벗어나지 못하는 문제가 있었기 때문이다. 그리고 우리는 이러한 saddle point 문제를 극복할 수 있는 새로운 탐색 방법을 제시한다"입니다. 이 논문에서 제시한 새로운 탐색 방법도 꽤 유용해 보이며 한번쯤 읽어볼 만한 좋은 논문으로 생각됩니다.


by 다크 프로그래머


  • thinkpad 2015.03.25 11:34 신고 ADDR 수정/삭제 답글

    안녕하세요 매번 좋은 글 감사드립니다.
    제가 수학실력이 좀 부족해서 이해가 안가는 부분이 있어서 그런데 조금 더 설명을 부탁드려도 될런지 모르겠습니다.

    1차 미분이 0인 critical point에 대해서는 이해를 했는데 "모든 축의 방향으로 함수 그래프가 아래로 볼록(f''>0)이 되어야만 한다." 이 부분이 이해가 잘 안가는데 설명을 조금 부탁드려도 될런지요?

    • BlogIcon 다크pgmr 2015.03.25 14:20 신고 수정/삭제

      안녕하세요. 아래로 볼록이라는 의미는 아실테고 아마도 '모든 축의 방향으로'라는 표현 때문에 그러신 것 같은데요, 본문 내용중의 식 (1)을 보시면 좋을 것 같습니다. n차원 공간에서 정의된 다변수 함수 f(x1,...,xn)이 점 p(p1,...,pn)에서 어떤 변화 특성을 갖는지 분석할 때, x1만 변수로 놓고, p2, ..., pn은 상수로 놓은 함수 f(x1,p2,p3,...,pn)를 생각해 보면 x1 값이 변할 때 f의 값이 어떤 변화를 갖는지 분석할 수 있을 것입니다. 마찬가지 방식으로 x2, x3, ... 에 대해서도 각각의 방향으로의 함수값 변화 특성을 분석할 수 있습니다. 그리고 모든 축 방향으로 함수 변화가 아래로 볼록인 형태면 이 지점(p)에서 함수 f는 local minimum을 갖는다고 말할 수 있습니다.

    • thinkpad 2015.03.26 11:38 신고 수정/삭제

      다크프로그래머님 답변 감사드립니다.

  • 밥버러지 2015.03.27 12:24 신고 ADDR 수정/삭제 답글

    흥미로운 주제의 논문이네요... 저도 항상 최적화 시에 이상한 곳으로 수렴할 때에는 local minima에 빠져버렸구나.. 이렇게 핑계 아닌 핑계(?)를 했었는데 그게 아니었나 싶습니다ㅎㅎ 다크 프로그래머님 말씀대로 saddle point가 아니라고 해서 global minima라고 하는 거는 저도 선뜻 이해가 잘 되지 않습니다. 분명 차원이 높아진 대로 그만큼 local minima가 더 생길거같은데... 흥미롭습니다!!

  • 참좋은 2015.03.27 14:06 신고 ADDR 수정/삭제 답글

    오 좋은주제 감사합니다.

  • 초보 2015.04.02 01:10 신고 ADDR 수정/삭제 답글

    항상 좋은글 잘보고 있습니다. 감사합니다.

  • 위촉 2015.05.22 14:33 신고 ADDR 수정/삭제 답글

    히히히 최신 논문 내용을 이해 할 수 있게 설명해주시는 능력이 참 대단하시네요 ㅎㅎ

    잘배워갑니다!

  • 메모광 2015.08.11 01:50 신고 ADDR 수정/삭제 답글

    해당 논문이 NIPS 2014에 실렸나보네요. (참고: http://ynd.github.io/)

  • BlogIcon 조영군 2016.03.14 21:40 신고 ADDR 수정/삭제 답글

    좋은글 잘봤습니다. 여기서 언급하는 고차원은 대략 몇차원에 해당할까요?

  • d 2016.08.08 13:47 신고 ADDR 수정/삭제 답글

    오 신선한 논문이네요..머신러닝 뿐만 아니라, 분자물리학의 energy landscape 이론에 주는 시사점도 꽤 있어보이는군요.

  • 치치 2016.09.13 18:35 신고 ADDR 수정/삭제 답글

    논문 주제도 신선하고 그걸 이해하실 수 있게 잘 설명해주시니 더욱 더 감탄했습니다. 감사합니다

  • 임도형 2017.02.15 11:06 신고 ADDR 수정/삭제 답글

    local minima에 빠져서 더이상 학습이 불가하다 싶었는데, 아닐 수 있네요.
    그렇다면 학습 데이타가 충분하고, 학습 시간이 충분하다면 원하는 만큼의 학습이 가능하겠네요.
    요즘 왜 그렇게 학습 속도 향상에 집중하는지도 이해가 되네요.

    글 감사합니다.

  • 이인묵 2017.06.08 16:51 신고 ADDR 수정/삭제 답글

    좋은 글 항상 감사합니다.

  • BlogIcon rlj1202 2017.07.10 13:42 신고 ADDR 수정/삭제 답글

    saddle point는 모든 방향으로의 기울기가 0인 지점인가요? 평평한 지점?

    • BlogIcon 다크pgmr 2017.07.10 15:17 신고 수정/삭제

      모든 방향으로 기울기가 0이면서 극점(극대 or 극소)이 아닌 점을 saddle point라 합니다. 말안장처럼 어떤 방향으로는 아래로 볼록이지만 다른 방향으로는 위로 볼록인 형태를 상상하시면 됩니다.

  • 히구 2017.12.09 18:24 신고 ADDR 수정/삭제 답글

    안녕하세요. 질문이 있어서 덧글 남깁니다. 일반적인 MSE등을 lossing func으로 사용하는 뉴럴넷에서도 위와 같은 모양의 saddle point가 나올수 있나요? 위로 볼록인 모양도 안 나올것 같고 2차함수꼴인데 saddlepoint가 나오는 것도 상상이 잘 안되네요 ㅠ

    • BlogIcon 다크pgmr 2017.12.10 20:32 신고 수정/삭제

      네, 나올 수 있다고 생각합니다. loss 함수가 L = (f - y)^2 형태인 경우, L은 f에 대한 함수가 아니라 f를 구성하는 변수들에 대한 함수입니다. 즉, L은 f에 대해서는 2차이지만 실제 변수들에 대해서는 2차가 아니며 위로 볼록, 아래로 볼록, saddle 등 어떤 형태라도 나올 수 있습니다. 간단한 예로, f - y가 양수이면서 위로 볼록인 형태였다면 (f - y)^2도 위로 볼록인 형태가 됩니다.

    • 히구 2017.12.18 14:21 신고 수정/삭제

      답변 감사합니다. 많은 도움이 된것 같아요

  • ㅇㅇ 2017.12.20 14:25 신고 ADDR 수정/삭제 답글

    좋은 논문 소개 감사드립니다.

    개인적으로는 저자의 두번째 주장(=차원이 커진다면 local minia가 나타날 확률은 줄어들 것이다.)은 단순히 확률이나 통계적인 관점으로 봤을 때는 크게 문제가 없을것 같다고 생각됩니다.

    임계점이 극소 점이나 극대 점이 되려면 모든 차원에서 극대 혹은 극소 방향이어야 하고 나머지는 모두 안장점이 될텐데
    만약 2차원이라면 어느 점이 극소점이 되려면
    극대점 = {극대, 극대}
    극소점 = {극소, 극소}
    안장점 = {극대, 극소}, {극소, 극대}
    확률론적으로만 생각했을 경우에는 약 1/4 정도가 될것이고,

    3차원의 경우에는
    극소 = {극소, 극소, 극소}
    극대 = {극대, 극대, 극대}
    안장점 = {극소, 극소, 극대}, {극소, 극대, 극대}, ..., {극대, 극대, 극소}
    로 1/8이 될거고,

    n차원의 경우에는
    극소 = {극소, 극소, ..., 극소}
    극대 = {극대, 극대, ..., 극대}
    안장점 = o.w.
    1/(2^n)만이 극소점이 될거니깐요.

    결국 충분히 큰 고차원 N에서는 극소점이 극도로 줄어들 것이라는 거죠.

    좀 더 정성적으로 설명해 보자면 차원이라는 것은 결국 어떠한 대상을 묘사하는데 필요로 하는 단위의 갯수, 즉 어떤 대상을 다른 대상과 구분하는 측면으로 볼 수 있는데,
    이러한 면에서 봐도 작고, 저러한 면에서 봐도 작고, 정말 여러가지 차원에서 살펴봐도 모두 극소점이면 최소점이거나 그에 준하는 작은 점이라는거죠.

    그리고 본문에는 만약 차원이 커지면서 임계점 자체의 숫자도 같이 커지는 경우를 반론의 예시로 들었는데, 임계점이 성립하려면 해당 점이 저차원에서도 모든 점이 극점이어야 했기 때문에, 차원이 증가하면 증가할수록 임계점의 성립 요건이 까다로워지기 때문에, 단순히 통계적으로 생각하였을 경우에는 임계점의 숫자는 줄어들것으로 생각됩니다.

    물론 이러한 이야기들은 모두 확률론적인 관점으로 바라본 이야기로, 그럴 가능성이 높다는 이야기지 항상 그렇다는 이야기는 아니며, 이러한 확률론적인 관점에서 살펴 보았을 때에는 본 포스팅에서 소개한 저자의 두 번째 주장이 큰 문제가 없지 않을까 생각이 듭니다.

    • BlogIcon 다크pgmr 2017.12.21 15:31 신고 수정/삭제

      네.. 아주 논리적인 설명이라 저도 읽다가 깜박 빠져들었습니다.

      본문에도 적었듯이 어떤 점이 임계점(critical point)이라고 했을 때, 이 점이 극소점이 될 확률이 고차원에서 극히 낮다는 데에는 저도 이견이 없습니다. 다만 저는 고차원에서는 임계점 자체의 숫자가 증가하니 결과적으로 극소점이 발생할 기회도 많아지는 것이 아닌가 하는 의문을 가지고 있습니다. 결국 임계점의 숫자가 증가하느냐 증가하지 않느냐가 관건인 것 같은데요.. 관련해서 아래와 같이 계산을 해 봤습니다.

      임계점의 개수:
      1차원(일변수)에서 어떤 한 지점이 임계점일 확률을 p, 변수의 정의역을 실수 전체의 집합 R로 가정,
      1차원 임계점 갯수 = 데이터갯수 * 확률 = Rp
      2차원 임계점 개수 = R^2 * p^2 = (Rp)^2 (각 변수축으로의 임계점 형성은 서로 독립 가정)
      n차원 임계점 개수 = (Rp)^n

      어떤 임계점이 극소점일 확률:
      1차원: 1/4 (위로볼록, 아래로볼록, 단조증가 saddle, 단조감소 saddle 중 1)
      2차원: (1/4)^2
      n차원: (1/4)^n

      n차원 극소점의 개수:
      임계점 개수 * 임계점이 극소점일 확률 = (Rp)^n * (1/4)^n = (Rp/4)^n
      1차원: Rp/4
      2차원: (Rp/4)^2
      n차원: (Rp/4)^n

      와 같이 (정말 말도 안되는 계산이지만) 숫자상으로는 (Rp/4)^n로 계산이 됩니다.

      정리를 해보면, 숫자(확률)상으로는 임계점의 개수는 (Rp)^n으로 Rp>1이기만 하면 차원이 증가할수록 기하 급수적으로 임계점의 개수도 증가합니다. 그리고 극소점의 개수는 (Rp/4)^n으로 각 변수축으로의 함수의 복잡도가 3차 이상이라면 차원이 증가할수록 극소점의 개수도 증가하고, 만일 그 이하의 복잡도라면 차원이 증가할수록 극소점의 개수가 작아져서 0에 가까운 값으로 수렴합니다 (계산상으로).

      단지 숫자상의 계산이라 단정할 수는 없지만 이렇게 계산을 해 놓고 보니 case by case란 생각이 들고 또 함수를 구성하는 각 변수의 차수가 관건인 것 같습니다.

  • abc 2018.02.14 13:52 신고 ADDR 수정/삭제 답글

    saddle point 관련 질문이 있습니다.
    "Domain adversial neural networks"라는 논문을 보다 saddle point에 대해서 궁금한 점이 있어서 질문드립니다.
    해당 논문에서 특정 목적함수를 정의를 하였는데 (9페이지 equation (9) 입니다)
    근데 최종적으로 원하는 것이 목적함수를 최소화 시키는 parameter를 구하는 것이 아니라
    목적함수의 saddle point를 주는 parameter를 구하는 것입니다..

    상식적으로 목적함수으 ㅣ최소를 구하는것이 맞는것 같은데 어떤 이유? 제한? 때문에 saddle point를 주는 것으로 바꾸는 것인지 궁금합니다!

    • BlogIcon 다크pgmr 2018.02.14 17:57 신고 수정/삭제

      안녕하세요. 제가 논문은 보지 않아서 모르겠습니다만 논문에서 saddle point가 아니라 critical point를 구하는 것이 아닌지요? 목적함수의 극소점을 찾기 위해 critical point를 구하는 것은 자연스러운 과정이라 생각합니다. 만일 말씀하신 것처럼 논문에서 saddle point를 구했다면 그건 저도 잘 이해가 안가네요.. 논문의 context를 잘 살펴보셔야 할 것 같습니다.

  • 나그네 2018.04.11 17:05 신고 ADDR 수정/삭제 답글

    기계학습의 관점에서, local optima에 빠지는 주 요인은 모델의 문제라기 보다는 학습에 사용되는 데이터가 'local' hypothesis를 표현하고 있기 때문이라고 개인적으로 생각하고 있습니다. 학습이라는 것이 데이터가 내포한 hypothesis와 모델의 hypothesis 간의 차이를 스칼라로 나타내는 loss function을 설계하고 이를 최소화하는 파라미터를 찾는 optimization 문제를 해결하는 과정인 것인데요, 애시 당초 데이터가 'local' hypothesis 를 가졌다면 아무리 optimization을 잘했다하더라도 데이터의 'local' hypothesis를 만족하는 파라미터를 찾은 것이고 이는 global optima와 차이가 벌어질 수 밖에 없는 것이라고 봅니다. 결국은 global optima를 찾기 위해선 학습 데이터가 global hypothesis에 가까운 hypothesis를 내포해야 하는 것이고 이를 위해서는 다양한 case가 담긴 '대량의' 데이터가 필요하다고 생각합니다. 쓰고보니 그냥 당연한 이야기네요.

    • BlogIcon 다크pgmr 2018.04.13 09:32 신고 수정/삭제

      안녕하세요. 좋은 말씀 주셔서 감사합니다. 데이터가 원 시스템의 pdf를 잘 포괄할 수 있어야 하는 건 당연한 것이겠지만 그걸 local minima 문제로는 연관을 짓지 못했습니다. 모델, 데이터, 에러함수, local minima 이런 것들이 자꾸 머리에서 맴돌면서 한참을 생각했습니다. 덕분에 좋은 공부가 되었습니다. ^^

    • 딥 피직스 2018.06.29 16:26 신고 수정/삭제

      나그네님 좋은 관점입니다. 데이터가 'local' hypothesis를 가지기 때문에 데이터에만 모델이 적응하면 글로벌하게는 성능이 떨어지는 오버피팅이 일어난다고 이해할 수 있겠네요! ㅎㅎㅎ

  • 2018.05.02 14:12 신고 ADDR 수정/삭제 답글

    초보적인 질문일수 있겠습니다만..
    1) 로컬미니마 문제가 발생하지 않을 안전한 인풋차원수의 범위는 알수없는것이네요? 저기서 말하는것은 "여러분이 생각하는것보다 로컬미니마의 문제는 발생확률 자체가 적다; "충분히" 고차원의 인풋이라면" 인데.. 그래서 "어느정도차원이면 충분히 안전하다"에 대한건 아직 밝혀지지 않은걸까요?

    2) "구덩이"가 여러개인지 , 정말 한개뿐인지 알아내는 방법론같은것은 아직까진 없는걸까요? 글로벌미니마는 수만차원에서도 단 하나뿐이겠지만(lowest cost), 새들포인트가 아닌=확률적으로 발생하기 힘든 "구덩이"들은 실제로 많이 존재할수도 있을테니까요?..;

    • BlogIcon 다크pgmr 2018.05.02 16:12 신고 수정/삭제

      네.. 저도 딱히 그 이상에 대해서는 아는 바가 없습니다. ^^

  • 딥 피직스 2018.06.29 16:38 신고 ADDR 수정/삭제 답글

    논문 그림을 살짝 보고 깨달았는데, ring모양의 로칼 미니멈이라면 아주 오랜 시간 또는 영원히 갇혀 있겠네요