최적화 알고리즘을 최적화하는 방법

KISTI 미리안 『글로벌동향브리핑』 2015-01-27

수학적인 함수에서 최소값을 찾는 최적화 알고리즘은 공학 분야에서 항상 존재하게 된다. 이러한 값은 디자인적인 상충관계를 평가하거나, 제어시스템을 액세스하고 데이터에서 패턴을 찾는데 사용되고 있다. 어려운 최적화 문제를 해결하기 위한 한 가지 방법은 연관되어져 있으며, 훨씬 더 간단한 문제로 축소시키는 것이다. 그러고서 점차 복잡도를 추가하여 순서대로 각각의 새로운 문제를 해결하고 다음 문제를 해결하기 위한 방법을 사용하는 것이다. 이러한 방법은 실제로 잘 동작하는 것처럼 보여지지만 이론적으로는 결코 특징지을 수 없다. 이번 달에 열린 컴퓨터비전 및 패턴인식의 에너지 절감방법에 대한 국제 컨퍼런스(International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition)에서 MIT CSAIL(Computer Science and Artificial Intelligence Laboratory)의 박사 후 연구원인 Hossein Mobahi와 이 연구소의 수석연구과학자인 John Fisher는 가장 적합한 최적화를 보장할 수 있도록 연속적인 단순화 함수를 발생시키는 방법에 관하여 발표하였다. “이러한 방법에 관한 몇 가지 기본적인 질문에 우리가 먼저 대답을 해야 한다. 예를 들어, 나는 단순한 문제로부터 시작했지만 단순한 문제를 선택하는 방법에 관하여 당신에게 말할 수 없다. 왜냐하면 당신이 시작할 수 있는 무한한 많은 함수들이 있기 때문이다. 심지어 어떤 함수를 가지고 시작했다고 말했을지라도, 실제 문제를 변화시키기 위한 무한히 많은 문제들이 존재하게 된다. 그래서 이러한 변화가 최종적으로 당신이 얻게 되는 결과에 영향을 주게 된다”고 Mobahi가 말했다. 최적화가 동작하는 방법을 이해하기 위해서, 통조림 식품 소매업체가 철을 대한 비용을 절약하려고 가정하는 상황을 가정해 볼 때, 내용물에 대한 표면적의 비율을 최소화하기 위한 캔 디자인을 원하게 될 것이다. 이러한 비율은 캔의 높이와 직경에 대한 함수이다. 그래서 최소화 함수값을 찾게 된다면, 캔의 최적화된 크기를 알게 되는 것이다. 만약 당신이 자동차의 중량과 바람에 대한 저항에 대하여 여러 가지 재료들로 구성된 부품의 비용을 조절하려는 자동차 디자이너라면, 비용함수로서의 최적화라는 함수는 훨씬 더 복잡해질 것이다. 그러나 원리는 동일하다. 기계 학습 알고리즘은 종종 분류 작업에 유용하게 사용되는 데이터 셋 특징들을 찾아내기 위해서 시도하고 있다. 즉, 자동차에 대한 시각적인 기능 지수와 같은 것을 말한다. 최고의 예측치를 갖는 특징에 대한 최소의 셋을 찾는 것도 또한 최적화 문제이다. “우리가 최적화 문제를 해결하기 위해서 가지고 있는 가장 효율적인 알고리즘들은 국부적인 검색에 기반을 하고 있다. 이것은 문제에 관하여 몇 가지 가정을 가지고 초기화하여 그것을 증명할 수 있는 어떤 방향을 찾으려고 시도를 하게 된다. 이러한 기술을 사용하면 국소 최소점(local minimum)이라는 어떤 값으로 수렴할 수 있다. 이것은 주변과 비교하여 더 낮은 값을 갖는 지점을 의미하는 것이다. 그러나 전체적으로 최소가 될 수 없을지도 모른다. 왜냐하면 훨씬 멀리 떨어져 있는 지점이 더 낮은 값을 가질 수도 있기 때문”이라고 Mobahi가 말했다. 그러나 함수에서 경사도가 최소값 주변의 사방으로 퍼져있게 되는 볼록한 경사도를 가지게 된다면 국소 최소점은 전체적인 최소값으로 보장될 수 있다. 함수 y = x2는 볼록하다. 그래서 초기값을 중심으로 포물선으로 표현된다. 함수 y = sin x는 위아래로 파도모양을 가진 사인파의 모양으로 나타나기 때문에 볼록하지 않다. Mobahi와 Fisher의 방법은 최적화 문제에 대한 볼록면 근사치를 찾는 것으로부터 시작하였으며 가우시안 스무딩(Gaussian smoothing)이라는 기술을 사용하였다. 가우시안 스무딩은 비용함수를 관련 함수로 변환하는 것으로서 비용함수가 되는 값이 주어지지는 않지만, 모든 주변 값들의 가중치 평균은 주어지게 된다. 이것은 비용 함수의 그래프에서 갑작스런 상승 또는 하강에 대한 변화를 제거하는 효과를 갖게 된다. 주변 값들에 할당된 가중치는 정규분포인 가우시안 함수에 의해서 결정된다. 이것은 기본 통계와 유사한 벨 곡선이다. 주변의 값들은 멀리 있는 값들보다 더 평균값에 가까워지게 된다. 가우시안 함수의 폭은 하나의 파라미터에 의해서 결정된다. Mobahi와Fisher는 어떤 조건에 있는 매우 넓은 가우시안 값을 가지고 시작하였으며, 볼록 함수를 산출하게 되었다. 그러고서 그들은 가우시안 함수의 폭을 계속 감소시켜서 연속된 인터미디어리(intermediary) 문제를 생성하게 되었다. 각 단계에서 그들은 다음 문제를 위한 해결방법의 검색을 초기화하기 위해서 마지막 문제에 대한 해결방법을 사용하였다. 그래서 분포도의 폭이 0에 가깝게 축소되면, 원래의 비용함수로 복구되기 때문에 모든 값이 간단하게 그 자체의 평균값이 되는 것이다. “최적화를 위한 연속성 방법은 실제로 폭넓게 사용되고 있으며, 컴퓨터 비전 분야에서 할당 문제를 해결하고, 다른 장소에 있는 무리들을 추적하는 문제를 해결하는데 사용되고 있다. 그러나 이것은 잘 이해되고 있지는 않다. 일반적으로 Hossein의 연구에서 관심 있는 분야이며, 특히 이 논문에서 관심 있는 분야는 이러한 연속성 방법을 자세히 밝혀내는 것이다. 그리고 이것에 관하여 분석적으로 말할 수 있도록 계속 연구해가는 것”이라고 컬럼비아대학교 전기공학과의 John Wright가 말했다. 그는 이 연구에 참여하고 있지는 않다. “이 연구의 실제적인 유용성은 스무딩을 하거나 세밀하게 최적화를 할 수 있는 다양한 방법들이 될 수 있다는 점이다. 만약 당신이 미리 올바른 것을 알아낼 수 있다면, 틀린 것을 찾는데 많은 시간을 소비하지 않아도 될 것이기 때문에 처리방법을 바로 알 수 있게 되는 것”이라고 Wright가 말했다. MIT-Nonconvex-Optimization.jpg http://newsoffice.mit.edu/2015/optimizing-optimization-algorithms-0121