DMQM 연구실
김영훈 Nortwestern University 연수 후기.

안녕하세요. 김영훈입니다. 제가 한국을 떠나온 지도 벌써 2달이 되었습니다. 처음에는 Large Scale Optimization이 무엇인지도
몰라 어리둥절해 하고 있었는데 어느새 시간이 지나 한국에 돌아가게 되었습니다. 두 달간 저는 Northwestern University Kellog Business School에 계신 심상호 박사님과 Large Scale Optimization에 대해서 공부하고, 관련
주제로 연구를 진행했습니다. 또한 연수 기간 동안 개인적으로 부족하다고 생각되는 점들을 보완하기 위해서
남는 시간에는 Computer Science, Probabilistic Graphical Model과
관련한 주제들에 대해 공부를 했습니다. 이번 연수 후기 작성을 통해서 지난 2개월을 저 스스로도 정리하고, 2달간 어떻게 생활했는지 궁금해하실
연구원 여러분들께 제 소식을 전하고자 합니다. 저의 생활은 앞서 말씀드린 것처럼 3가지로 나눠질 수 있는데, Large Scale Optimization 공부
및 연구, 개인적인 공부, 일상생활들로 나눠서 소개해 드리도록
하겠습니다.

1. Large Scale Optimization 소개, 공부 및 연구

Large Scale Optimization 소개     

 우선
Large Scale Optimization(LSO)에 대해서 간략하게 설명드리자면, 기존에 연구되어있는 Linear Programming(LP), Integer
Programming(IP), Mixed Integer Programming(MIP) 모델을 사이즈가 굉장히 큰 모델에 대해서 적용할
수 없기 때문에 연구되는 학문이라고 생각하시면 됩니다. 마치 데이터 마이닝 분야에서도 빅데이터 시대가
와서 하둡, GPU Computing과 같은 프레임워크가 새롭게 대두되었 듯이, 최적화 분야에서도 과거에 큰 사이즈의 문제를 다루기 위해 연구된 수학적인 프레임 워크라고 볼 수 있습니다.

일반적으로 최적화 문제를 해결할 때는 Cplex, Gurobi와 같은 패키지가
많이 사용되는데, Large Scale Optimization이 다루는 문제는 포뮬레이션한 다음 패키지에
넣을 경우 메모리가 부족하거나 계산량이 너무 많아 해결 조차 되지 않는 사이즈의 문제입니다. 그래서
이러한 문제를 풀기 위해서는 수학적인 배경을 가지고 본래의 문제를 좀 더 쉬운 문제로 변형시키거나, 여러
개의 쉬운 문제들로 쪼개거나 문제를 업데이트 하면서 풀어야 합니다. 이와 연관되는 최적화의 개념이 Dual, Column (Constraint) Generation, Decomposition 등이 있습니다. 이러한 테크닉을 사용해서, 문제를 변형한 후에 패키지를 이용할 경우, 메모리 부족 문제를 피하면서 빠르고 효율적으로 문제를 해결할 수 있습니다.

Large Scale Optimization은
이러한 일련의 과정을 포함하는 학문이라 할 수 있습니다. LP, IP, MIP 지식을 기반으로 하고, 큰 사이즈의 문제를 해결하는 것입니다. 이러한 방법론은 1980년대를 기점으로 해서 빠르게 발전해 왔다고 합니다. 과거 비행기가
새로운 교통 수단으로 대두되고, 항공 산업이 각광 받는 시절에 항공사 간의 경쟁이 매우 치열했는데, 이 Large Scale Optimization이 항공 산업에 접목되면서, 해당 산업의 경쟁 패러다임이 바뀌게 됩니다. 현재는 매우 잘 알려져
있고 큰 항공사인 American Airline이 1980년대에는
규모의 경쟁력이 약한 중, 소 항공사에 속했다고 합니다. 그런데
이 항공사가 최적화를 도입해서 항공 및 화물 서비스의 스케줄링을 시작하고 1년만에 미국의 가장 큰 항공사가
무너지고 American Airline이 1등 항공사가 되는
전설적인 사건이 일어나게 됩니다. 그래서 미국에서는 이 최적화가 강한 관심을 받고 활발하게 연구되게
됩니다. 우리 나라에서는 최적화가 유명하게 알려져 있지는 않았습니다.
왜냐하면, 국토의 면적이 너무 좁고, 사람 수도
적어서, 서비스 과정에서 최적화 방법론을 적용하는 것이 큰 이익을 창출하지 못하기 때문입니다. 그런데 앞으로는 많은 분야에서 쓰이게 될 것이라 생각됩니다. 기업들의
국제화로 자국의 국토 면적의 크기는 의미가 사라진 지 오래이고, 물류,
스케줄링, 서비스 최적화 외에도 다양한 분야에 대한 응용 연구가 활발히 진행되고 있기 때문입니다. 데이터 마이닝 분야에서, 특히 대용량을 데이터를 통해 모델을 만들
경우 효과적으로 사용될 수 있다고 생각합니다. 뒤에 제가 하고 있는 연구 소개에서 간단히 소개하겠지만, 사이즈가 매우 큰 회귀분석, 분류,
군집 분석 모델을 만들 때 최적화 모델 해결 과정에서 사용될 수 있다고 생각합니다.

Large Scale Optimization 공부
및 연구

 심상호 박사님과는 1월
2주차부터 공부를 시작해서 2월 초까지 기본적인 이론 공부를
마무리했고, 그 다음에는 개인적으로 관심 있는 주제를 가지고서 연구를 진행했습니다. 앞서 소개 장에서 말씀드린 바와 같이 가장 기본은 LP, IP, MIP에
대한 이해로부터 출발하게 됩니다. 특히 이 중 하나만 뽑으라고 한다면 LP 모델이 가장 기본이 됩니다. 저는 한국에 있을 때 기본적인 최적화
이론들에 대해서 공부를 했기 때문에, 바로 이 LP를 응용한
Large Scale Optimization에 대해서 공부를 시작했습니다.

 우선 가장 처음으로 시작한 것은
Column Generation입니다. 이것은
Primal 문제를 풀 때 제약 조건을 구성하는 행렬의 Column을 생성해 나가면서 효율적으로
문제를 풀어가는 방법입니다. 우리가 행렬을 완벽하게 구성할 수 없지만 행렬의 Column이 가지는 속성을 알고 있을 때 좋은 Column(최적해와
연관이 큰)을 하나 하나 생성해 가면서 효율적으로 푸는 방법입니다.

 그 다음으로 공부한 것은 Primal
Dual Simplex Algorithm입니다. 이것은 Primal
문제를 Dual 공간에서 해결해 나가는 방법입니다. 일반적으로
최적화 모델을 만들면 우리는 그에 상응하는 Dual 문제도 만들 수가 있습니다. 선형대수의 Orthogonality 개념을 보면 Column Space와 Low Space가 하나의 행렬에서 정의될
수 있는 두 개의 공간임을 알 수 있습니다. 이러한 개념이 최적화 모델에서도 적용됩니다. LP는 선형모델로서 행렬로 제약 조건들을 표현할 수 있고, Primal
Space와 Dual Space라고 하는 최적의 해를 공유하는 두 개의 해 공간이 공존하게
됩니다. Primal Dual Simplex는 이러한 특성을 활용해서 Dual 공간에서 해를 찾게 되는데, 해를 찾는 방향과 이동 거리를
현재의 해와 Primal 해 공간의 정보를 통해 업데이트 하면서 최적의 해를 찾게 됩니다.

우선 여기까지 공부를 한 이후에 Gurobi와
Python을 활용한 실습을 통해서 두 개의 알고리즘을 구현해 보았습니다. 최적화 문제를 푼다는 것이 문제를 포뮬레이션 한 다음 패키지에 넣어주기만 하면 되는 줄 알았는데, 실습을 통해서 훨씬 어렵고 복잡한 과정이 디자인되어야 한다는 것을 깨달을 수 있었습니다.

이 과정이 끝난 이후에는 Branch
& Bound, Quadratic Programming, KKT Condition, Max flow Min Cut 등과 같이
다음 단계로 넘어가기 위한 기본적인 개념들에 대해서 미팅을 하면서 공부를 했습니다.

기본적인 내용이 끝난 이후에는 본격적으로 Largrangean Method에 대해서 공부를 시작했습니다. 미적분학
시간이나 미시 경제학 시간에 배울 수 있는 그러한 Largrangean과 개념은 동일합니다. LP를 해결할 때에도 해결하기 어려운 제약 조건을 목적식으로 옮겨서 해결하는 방법이 사용될 수 있습니다. LP의 경우에는 이 Largrangea Method로 푸는 것이
본 문제와 동일한 해를 주게 됩니다. 반면 IP의 경우에는
정확한 최적 해는 주지 못하지만, 최적해를 계산하기 위한 좋은 Low
Bound/Upper Bound를 주고, 이를 활용하면 빠르게 IP의 최적해를 구할 수 있습니다. Large Scale Optimization에서는
일반적인 방법처럼 모든 제약식을 목적식으로 옮기는 것은 아니고, 어려운 해 공간을 목적식으로 이동시키게
됩니다. 여기서 어려운 해 공간이라 하면, 우리가 공간의
특성을 알기 어려운 형태로 제약식이 구성된 것을 의미합니다. 쉬운 공간을 예를 들자면 Diagonal Matrix 같이 Column이 하나의 Dimension과 연관되는 행렬이 만드는 제약 공간이 있겠습니다. 이렇게
제약식을 분리한 이후에 최종적으로는 쉬운 공간에서 나온 해들을 가지고 Convex Combination을
해서 어려운 공간의 제약까지 만족시키는 방식으로 문제를 해결합니다.

IP
문제의
경우에도 동일한 방법이 이용됩니다. 단 Largrangean IP의
경우 최적에 근사하는 해를 줍니다. 이 근사하는 해를 기점으로 Branch
and Bound 알고리즘을 적용했을 때 원래 IP 문제의 최적해를 구할 수 있게 됩니다. IP 최적해를 근사해서 구할 수 있는 방법에는 LP Relaxaiton이란
방법도 있습니다. 이것은 우리가 결정해줘야 하는 변수가 정수일 때 이를 실수 조건으로 Relax한 다음 푼다고 해서 붙여진 이름입니다. 일반적으로 결정 변수가
실수일 때 Simplex Algorithm을 사용할 경우 O(n^2)의
복잡도로 문제를 해결할 수 있습니다. 하지만 결정 변수가 정수일 때는 대부분 매우 어려운 문제가 되서
NP-Complete 문제가 되기 때문에 문제 사이즈가 커지면 풀기가 매우 어려워집니다. 그래서 이와 같이 실수로 Relax하거나 Largrangean으로 Relax해서 해를 얻고, 더 좋은 출발점에서 문제를 풀어서 좀 더 쉽고 빠르게 문제를 해결하게 됩니다.
LP Relaxation이 간단하지만 Largrangean을 써야 하는 이유는 Largrangea이 더 좋은 Bound(최적값에 가까운)를 주기 때문에 Branch and Bound를 적용했을 때 훨씬
빠르게 최적해를 구할 수 있습니다.

저는 여기까지 공부한 이후에 Facility
Location Problem이란 문제를 Largrangean IP와 Branch and Bound를 활용해서 빠르게 해결하는 실습을 진행했습니다. 그리고
글을 쓰고 있는 지금은 Largrangean Facet(Largrangean 해 공간을 구성하는 평면)들을 좀 더 빠르게 찾아내는 방법을 연구한 이후에 한국에 돌아갈 것 같습니다.

제가 이 Largrangean 문제를
좀 더 자세하게 설명한 이유는 제 연구와도 연관이 크기 때문입니다. 저는 원래 Subset Selection에 관심이 많아서 Lasso, Fused
Lasso, Elastic net에 대해서 관심을 가지고 공부를 해왔습니다. 작년에는 이와
관련해서 모기 Spectra 데이터를 분석하는 논문을 작성하기도 했고요. 이번에는 좀 더 알고리즘 개발 쪽으로 중점을 맞춰서 연구를 하게 되었습니다.
MIP를 활용해서 Lasso와 비슷한 Subset
Selection 방법을 연구하는 중인데, 이 문제를 해결할 때 Largrangean Method가 사용되고 Facility Location
Problem이 응용 될 것 같습니다. 자세한 내용은 한국에 돌아가서 세미나를 갖거나 간단한
Discussion Meeting을 통해서 말씀드리면 좋을 것 같습니다.

이 외에도, 그래프 클러스터링과
관련한 공부를 조금 했습니다. Bayesian Network, Markov Random Field와
같은 Probabilistic Graphical Model에 관심이 또 많기 때문에 재미있게 공부를
했습니다. 하나의 페이퍼를 가지고 심도있게 읽고 토론하는 시간을 가졌는데 제목은 Graph Clustering and Minimum Cut Tree, Tarjan et al. 입니다. 이것은 Network Flow 최적화를 응용해서 클러스터링을 하는
내용을 담은 논문입니다. 구체적으로는 Graph를 Gomory-Hu Tree라고 하는 Min Cut Tree로 변형시킨
다음 필요없는 노드를 제거해서 간단하게 클러스터링을 하는 내용입니다. 아직 많이 부족한 제가 보기에도
정말 잘 쓰여졌고, 수학적인 논리도 완벽한 좋은 논문이라고 생각됩니다.
혹시 이 쪽 분야에 관심이 있으신 분이라면 꼭 한 번 읽어보시길 권해드립니다.

2. 개인적인
공부

두 달간의 시간 동안에 최적화 공부도 많이 했지만 개인적인 시간도
꽤 남아서 평소에 부족하다고 생각했고, 관심있었던 분야들에 대해서 추가적으로 공부를 할 수 있었습니다. 제가 연수를 온 것의 주 목적은 최적화 공부이기 때문에 이 부분들에 대해서는 간략하게 어떤 공부를 어떻게 했는지만
말씀드리도록 하겠습니다.

일단 저는 컴퓨터 공학에 관심이 많고 관련 주제로 연구도 해보고
싶지만 아직 해당 분야의 지식이 많이 부족하고 실제로 구현할 수 있는 실력도 많이 부족하다 생각되서 이번 기회에 Programming에 대한 공부를 1월 동안 많이 했습니다. Stanford의 컴퓨터 공학과 교수님들이 유튜브에 올려놓은 동영상을 보면서 공부를 했는데, Introduction to Computer Science, Programming Methodology,
Programming Abstraction이란 과목들을 공부했습니다. 단순히 언어의 문법만
가르치는 한국과 달리 컴퓨터 메모리 사용, 계산의 메커니즘과 객체 지향 프로그래밍과의 관계에 대해서
생각해 볼 수 있는 좋은 내용이 담겨있습니다. 이번에 공부한 것을 계속 이어나가기 위해 한국에 돌아가서
미국에서 공부한 C, Java, Python에 대해서 더 많이 공부하고 컴퓨터 자료구조나 알고리즘에
대해 더 공부해 보려고 합니다.

위의 컴퓨터 언어들을 공부하는 이유에 대해서 간략하게 설명드리면, C의 경우에는 매우 오래된 언어이지만 하드웨어를 직접 컨트롤할 수 있는 매우 강력한 언어이기도 합니다. 문법이 복잡하고 메모리 관리의 어려움이 있지만 최근 대세가 되고 있는 GPU
Computing 기술들도 거의 모두 다 이 C 언어로 구현되는 것은 그 장점이 더 크기
때문입니다. 그 다음으로 Java의 경우에는 하둡과 같은
멀티 클러스터 기반의 빅 데이터 처리 시스템의 표준이 되고 있는 언어입니다. C/C++보다 쉬운 문법과
메모리 관리가 필요하지만 네트워크 프로그래밍이 매우 강력하기 때문에 최근 빅데이터가 대두되면서 그 인기가 더욱 높아지고 있는 언어입니다. 마지막으로 Python은 제가 한국에 있을 때부터 써왔던 언어인데, 상대적으로 정말 쉽고 강력합니다. 프로그램 실행 속도는 많이 늦지만
간단한 프로그램을 프로토타이핑할 때는 가장 좋은 언어라고 생각됩니다. 또한 Cython을 사용할 경우 어느 정도 실제에서 사용할만한 성능이 되기 때문에 개인적으로 꼭 배워보시라고 추천드리고
싶습니다.

제가 3개나 되는 언어를
열거하긴 했지만, 사실 공부해보다 보면 컴퓨터 언어라는 것이 동일한 논리를 가지고 작성되었기 때문에
언어간의 약간의 차이만 이해한다면 공부의 시너지가 발생해서 빠르게 공부하실 수 있다고 생각합니다. 혹시, 컴퓨터 공학이나 프로그래밍에 관심이 있으시면 한국에서 같이 더 얘기 나누고 공부해보면 좋을 것 같습니다.

컴퓨터 공학에 대한 공부를 한 다음에는 Probabilistic Graphical Model에 대해서 더 공부를 했습니다. Bayesian Network나 Markov Random Field가
여기에 해당하는 모델인데, 복잡한 상관관계를 그래프 형태로 모델링할 수 있는 방법입니다. 저는 이 둘 중에서도 특히 Markov Random Field에
관심이 많습니다. 이 모델은 주로, Computer Vision,
Finance, Forecasting 등에서 많이 쓰이는 것 같은데, 이 모델을 가지고 Variable Inference하는 과정에서 다양한 최적화 방법론들이 쓰일 수 있기 때문에 더욱 관심을 가지고
공부를 하게 되었습니다. 혹시 관심이 있으신 분은 Coursera에
올라온 관련 강의들을 참고하시면 큰 도움이 되실 거라고 생각됩니다.

3. 일상생활
및 관광

미국에서의 일상적인 생활은 한국에서의 일상 생활과 크게 다르지는
않았습니다. 아침에 일어나서 제가 묵고 있는 Garret이라고
하는 신학 대학원의 기숙사 식당에서 아침식사를 하고, 산책이나 간단히 운동을 하고, 방에 돌아와서 미팅 준비를 하거나 공부를 했습니다. 심박사님과의
미팅은 일주일에 3번 화, 목, 토에 걸쳐서 진행했고, 수요일에는 교회 청년부 모임에 나가서 함께
저녁 먹고 교제하는 시간을 가졌고, 일요일은 심박사님이 다니시는 교회에 나가 예배도 드리고 식사도 하면서
시간을 보냈습니다. 그리고 1월 말쯤에는 여기 에반스톤에서
가까운 밀워키라는 도시로 교회 청년부 모임 분들과 함께 여행을 다녀왔고, 2월 말에는 시카고 다운타운에
가서 관광도 했습니다. 간단히 사진들을 첨부하고 소개해 드리도록 하겠습니다.

지면 관계상 사진 파일에 사진 기록은 담았습니다.

4. 연수
기간 동안 느낀점

미국에 나와서 짧은 기간 동안이지만 공부하면서 느낀 것들을 소개할까
합니다. 한국에 있을 때는 몰랐는데, 생각보다 정말 많은
한국분들이 타지에 나와서 열심히 공부하고 계신 것들을 보고, 들을 수 있었습니다. 박사 과정을 나오신 분들도 있고, 박사 후 과정을 나오신 분들도
많이 있었습니다. 타지 생활이 정말 힘들고 고되지만 좋은 연구를 위해 인내하고 정진하는 모습들을 보니
제가 조금 부끄러워지기도 했습니다. 그리고 적당히 공부해서는 안 되겠다는 생각도 들었고요. 또한 많은 한국분들을 만나면서 자신감도 얻을 수 있었습니다. 의외로
한국에서 박사 과정을 하고 연구를 더 하고 계신 분들이 많았는데, 한국에서 박사 과정을 했다고 해서
평가에 크게 차별을 받지 않는 것 같습니다. 연구자로서 얼마나 좋은 연구를 했는지가 더 큰 평가 요소라고
합니다. 제가 여기 와서 잠시 다녔던 고대 선배님을 만날 수 있었는데,
그 분도 우리 학교에서 박사 과정을 마치시고 미국에서 계속 연구를 하셔서 이번에 우리 학교로 임용이 되셨다고 합니다. 꼭 임용이 목적이 아니라 기업을 가더라도, 자신이 있는 자리에서
최선을 다해 연구하고 실력을 갈고 닦으면 좋은 기회가 올 것이라는 희망이 생겼습니다. 자신이 가지고
있는 실력과 여건들을 감사하게 생각하고, 최선을 다해서 도전하다 보면 세계적인 수준의 연구도 할 수
있지 않을까 생각해봅니다. 느낀 점이 참 많지만 2개월 간의
생각들을 글로 옮기려니 잘 되지 않는 것 같습니다. 한국에 돌아가 말씀 나누면서 많은 얘기 드릴 수
있으면 좋겠습니다.

감사의
말씀

정말 많은 것들을 배우고 느낀 미국 연수의 기회를 주신 김성범 교수님께
정말 감사드립니다. 앞으로 더욱 정진하여 좋은 모습으로 보답드리겠습니다. 그리고 미국 생활에 응원 보내주신 연구원분들께도 감사드립니다. 한국에서
뵙겠습니다.

감사합니다.

2014/2/25
Northwestern University Evanston Campus