[ICML 2021] 1편: Neural Combinatorial Optimization in ICML 2021

ICML 2021(International Conference on Machine Learning 2021)은 올해로 38회째를 맞은, 매년 약 7만 명 이상이 참가하는 대규모 국제 학회입니다. 논문 채택률 20%, 임팩트 팩터 6.99로 AI 분야에서 가장 영향력 있는 인공지능 학회 중 하나이기도 합니다. 지난 7월 18일부터 24일까지 온라인으로 개최되었던 'ICML 2021'에 참관한 LG AI연구원의 세 연구원이 학회 내용 중 유의미한 논문을 골라 소개합니다. - 1편: Neural Combinatorial Optimization in ICML 2021 - Di Lab 이강훈님 - 2편: Generative model for OOD detection in ICML 2021 - Di Lab 정혜민님 - 3편: Spatio-temporal Time-series Forecasting in ICML 2021 - Di Lab 유주현님

LG AI연구원의 Data Intelligence Lab은 현실에서 마주하는 다양한 형태의 데이터로부터 의미 있는 정보를 찾아내고, 이를 통해 그동안 풀리지 않은 난제에 도전하여 해결하는 목표를 가지고 있습니다. 현실, 특히 산업계에서 흔하게 존재하며 쉽게 마주할 수 있음에도, 딥 러닝(Deep Learning)으로 대표되는 최신 인공지능 및 기계학습 방법론에서 상대적으로 많은 주목을 받지 못한 문제로 조합 최적화(Combinatorial Optimization)^[1]가 있습니다.

외판원 문제(Traveling Salesman Problem), 최소 신장 트리(Minimum Spanning Tree), 배낭 문제(Knapsack Problem) 등으로 대표되는 조합 최적화는 수학적 최적화(Mathematical Optimization)의 한 분야로, 컴퓨터 공학을 전공한 학생들에게는 알고리즘 수업 시간에 한 번쯤 들어봤을 법한 문제들을 이야기합니다. 조합 최적화 문제의 특징은 실행 가능해(Feasible Solution)의 영역이 이산적(Discrete)이거나 이산적으로 환산(Reduction) 가능해야 한다는 점입니다. 이러한 문제들은 계산 복잡도 이론(Computational Complexity Theory)에서 NP-Complete^[2]에 속하는 어려운 문제들이 많은데, 여전히 풀리지 않은 난제로 남아 최근 인공지능 연구자들에게 매우 도전적인 문제로 인식되고 있습니다.

그림 1. 배낭 문제 예제^[3] 

위에서 본 그림 1의 배낭 문제란, 최대 15kg을 담을 수 있는 배낭과 각각 특정한 가치와 무게를 가지는 물건들이 있을 때, 배낭의 최대 무게 15kg을 넘지 않는 범위에서 가치의 합을 최대로 만드는 물건의 조합을 선택하는 문제입니다. 이러한 배낭 문제는, 여행가방에 넣을 옷과 짐을 고를 때나 화물운송에서 최대 적재 무게를 고려하여 화물을 싣고자 할 때와 같이 현실에서 쉽게 마주할 수 있는 문제입니다. 그림 1에서 최적해(Optimal Solution)는, $4의 가치를 가지지만 12kg으로 너무 무거운 연두색 물건을 제외하고 나머지 4개의 물건들(회색: $2, 1kg, 노란색: $10, 4kg, 빨간색: $1, 1kg, 파란색: $2, 2kg)을 선택하는 것입니다. 이렇게 선택된 4개의 물건은 총 무게 8kg으로 배낭의 최대 무게 15kg 이하라는 조건을 만족시키면서도 가치의 총 합은 $15을 가지게 되어, 최대 무게 15kg이라는 제약 조건 아래에서 고려할 수 있는 모든 가능한 물건 선택의 조합 중 가장 높은 가치 $15를 가집니다.

위 배낭 문제에서 관찰할 수 있는 대표적인 특징으로는, (1) 각 물건의 선택 여부를 “0-1” 이진 변수(Binary Variable)로 표현할 수 있고, (2) 5개의 물건에서 생각할 수 있는 선택의 조합은 총 32(= 2⁵)개로 이산적인 환경에 있다는 사실입니다. 특히, 두 번째 특징으로부터 유심히 살펴볼 점은, 물건의 개수가 많아질수록 우리가 고려해야 하는 선택의 조합이 2^{물건의 개수}가 되어 기하급수적(Exponential)으로 증가한다는 사실입니다. 이처럼 문제의 크기는 선형적(Linear)으로 증가하더라도 문제를 풀기 위해 고려해야 할 실행 가능해의 영역이 기하급수적으로 커지게 되는 현상은 많은 조합 최적화 문제에서 나타나고, 이러한 현상이 조합 최적화 문제의 가장 큰 특징이자 어려운 점이라 할 수 있습니다.

배낭 문제를 수학적으로 일반화하여 정의하면 다음과 같습니다^[3]. n개의 물건 {x₁, x₂, ... x_n}이 있고, 각각의 물건  x_i ∈ {0,1} (단,  i ∈ {1,2, ..., n})는 이진 변수로써, 물건  x_i를 선택하여 배낭에 담거나, x_{i = 1,} 물건 x_i를 선택하지 않아 배낭에 담지 않음(x_{i = 0})을 표현할 수 있습니다. 또한 배낭이 담을 수 있는 물건들의 최대 무게를 W ∈ R⁺라 하고, 각각의 물건 x_i는 v_i ∈ R⁺ 의 가치와 w_i ∈ R⁺의 무게를 가진다고 할 때, 배낭 문제는 아래와 같은 정수 계획법(Integer Programming 또는 Integer Linear Programming)으로 표현할 수 있습니다.
 
이 때, 물건의 총 개수 n, 각 물건의 가치 와 무게 , 그리고 배낭의 최대 무게 W는 문제의 정의로부터 주어지고, 배낭에 담을 물건의 선택 여부를 나타내는 가 위 정수 계획법을 통해 결정해야 할 변수(Variables)가 됩니다. 정수 계획법에서는 변수 가 정수 집합으로 이산적인 환경에 속해 있고, 최적화해야 하는 목적 함수(Objective)(즉, )와 제약 조건들(Constraints)(즉, )이 선형 함수로 나타내어져, 정수 계획법 또는 정수 선형 계획법 등으로 불립니다. 정수 계획법에서 최적화 목적 함수 및 제약 조건들은 여전히 선형 함수인데 반해, 변수의 집합이 연속적인 실수의 집합인 경우 선형 계획법(Linear Programming)이라고 부릅니다.

선형 계획법은 일반적으로 Simplex Method 등을 통해 효율적인 최적해 계산이 가능하다고 알려져 있으나, 정수 계획법의 경우, 변수 가 가질 수 있는 값이 이산적이고 또한 가능한 모든 경우의 수는 2ⁿ으로 변수의 개수 n이 증가함에 따라 기하급수적으로 증가하기 때문에 효율적인 최적해의 계산이 매우 어렵다고 알려져 있습니다. 또한, 변수이 정수와 실수가 서로 섞여 있는 경우, 혼합 정수 계획법(Mixed-Integer Programming 또는 Mixed-Integer Linear Programming)으로 불리고, 정수 계획법과 같이 효율적인 최적 해의 계산은 일반적으로 매우 어렵다고 알려져 있습니다.

위의 배낭 문제와 같이 정수 계획법으로 문제가 정의되면, 수학적 최적화 소프트웨어 패키지를 사용하여 해당 문제의 최적해를 구할 수 있습니다. 수학적 최적화를 위한 대표적인 소프트웨어 패키지로는 CPLEX[4]가 있습니다. CPLEX는 선형 계획법에서 가장 대표적인 수학적 최적화 도구이지만, 정수 계획법과 혼합 정수 계획법에서도 최적화 기능을 제공해주고 있습니다. 최근 정수 계획법(또는 혼합 정수 계획법) 문제에서 주로 사용되는 최적화 도구로는 GUROBI^[5]와 SCIP^[6]가 있는데, GUROBI는 유료로 사용이 가능한 반면 SCIP는 무료로 사용이 가능하다는 장점이 있습니다. 또한 구글의 OR-Tools^[7]를 통해서도 위의 수학적 최적화를 수행할 수 있습니다.

수학적 최적화 소프트웨어 패키지를 활용하면 기본적으로는 조합 최적화 문제를 쉽게 기술하고 최적해를 찾을 수 있지만, 여전히 풀고자 하는 문제의 복잡도(변수 및 제약 조건의 수)가 조금만 증가해도 소프트웨어 패키지가 구해주는 최적해의 수준(Quality)이 급격히 떨어지는 한계가 있습니다. 이러한 한계를 극복하기 위해서, 최근 딥 러닝을 이용하여 데이터 기반의 학습으로 조합 최적화를 연구하는 Neural Combinatorial Optimization 분야가 많은 주목을 받고 있습니다. 대표적으로 2015년 조합 최적화 문제를 딥러닝 지도학습(Supervised Learning)으로 해결하고자 했던 ‘Pointer Networks’^[8] 연구가 있었고, 2017년 딥 강화학습(Deep Reinforcement Learning)의 방법론을 도입한 ‘Neural Combinatorial Optimization with Reinforcement Learning’^[9]이라는 제목의 연구가 있었습니다. 최근 Google 및 DeepMind 연구진에서 제안한 ‘Neural Branching + Neural Diving’^[10] 연구에서는 트리 탐색(Tree Search)과 딥 러닝, 그리고 수학적 최적화 소프트웨어 패키지 SCIP^[6]를 조합함으로써 혼합 정수 계획법의 성능과 확장성(Scalability)을 크게 증가시켰습니다.

올해 ICML 2021에서도 다수의 의미 있는 딥러닝 기반 조합 최적화 연구 결과들이 발표되었습니다. 특히, 기존의 수학적 최적화 기반 정수 계획법과 최신 데이터 기반 딥 러닝 방법론의 적절한 조합을 통해 현실 세계(Real-World)에서 마주할 수 있는 다양한 조합 최적화 문제를 해결하고자 하는 시도들을 많이 볼 수 있었는데, 아래에서는 이 중 두 가지 연구 결과인 (1) Neural A* Search^[11] 및 (2) CombOptNet^[12]에 대하여 소개합니다.


Path Planning using Neural A* Search (Yonetani et al., ICML 2021)

경로 계획(Path Planning)은 주어진 출발 지점에서 시작하여 목적지까지 도달할 수 있는 최적의 경로를 찾는 문제입니다. 자동차를 이용하여 목적지까지의 운전 경로를 탐색하는 것 등 경로 계획은 우리 일상 생활에 매우 밀접하게 연관되어 있고, 많은 사람들이 스스로 머릿속으로 자신이 알고 있는 길을 바탕으로 계산을 하거나 혹은 스마트폰 지도 앱으로 최단 경로를 찾아 이용하고 있습니다. A* 탐색(A* Search)^[13]은 대표적인 경로 계획 알고리즘으로, 적절한 휴리스틱(Heuristic) 함수를 이용하여 탐색의 정확도를 유지하면서도 탐색의 효율을 높일 수 있어 많은 내비게이션 시스템에서 경로 탐색의 기본 알고리즘으로 활용되고 있습니다.

그림 2. A* 경로 탐색 예제^[14]

그림 2는 A* 경로 탐색 알고리즘의 한 예제입니다. 그림에서 보듯이, 왼쪽 아래 빨간 점에서 시작하여 오른쪽 위 빨간 점까지 도달하는 최단 경로를 찾는 문제인데, 왼쪽 아래의 빨간 점은 검은색 영역의 벽을 지나칠 수 없습니다. 이 때, A* 경로 탐색 알고리즘은 오른쪽 위 빨간 점의 목적지를 향해 나아가기 위해 그림 상에서 초록색 영역으로 표시된 주변 영역들을 순차적으로 탐색하게 됩니다. A* 알고리즘이 오른쪽 위 빨간 점에 도달하게 되면, 탐색 이력(Search History)를 나타내는 초록색 영역은 경로 탐색을 위해 소모한 시간 또는 비용을 나타내고, 이러한 탐색 비용을 지불한 후 얻게 되는 최종 경로는 빨간색 선으로 표현되어 있습니다.

그림 3. 이미지 기반 경로 탐색 탐색 예제^[14]

본 연구에서는 그림 2의 경로 탐색 예제와 같은 인공적(Synthetic)으로 만들어진 문제뿐만 아니라, 그림 3처럼 이미지 기반의 실제 사진에서 보행자들의 이동 경로 예측에서도 A* 탐색 알고리즘이 동작할 수 있도록 데이터 기반 학습을 포함하는 Neural A* 탐색(Neural A* Search)을 제안합니다.

그림 4. 데이터 기반 Guidance Map 학습 및 변환^[14]

Neural A* 알고리즘이 기존 A* 알고리즘 대비 탐색의 효율을 증가시킬 수 있는 것은 주어진 문제 사례(Problem Instance)로부터 경로 탐색 시 우선순위가 높은 후보 경로들에 대한 정보를 제공하는 Guidance Map 덕분입니다. 그림 4와 같이, Guidance Map은 A* 알고리즘이 최적의 경로를 찾기 위해 탐색했던 이력인 초록색 영역과 실제 정답 경로(Ground-Truth Path) 사이의 차이를 최소화하는 방향으로 학습이 이루어집니다. 이렇게 얻어진 Guidance Map은 A* 알고리즘에서 필요로 하는 휴리스틱 함수의 역할을 함으로써, Guidance Map이 실제 정답 경로에 가까운 정보를 제공할수록 Neural A* 알고리즘의 탐색 효율은 증가하게 됩니다.

그림 5. Neural A* 알고리즘 개요도^[11]

그림 5는 Neural A* 알고리즘의 전체 과정을 보여줍니다. 앞서 설명했듯이, 문제 사례가 주어지면 학습된 Encoder 네트워크로부터 Guidance Map을 얻을 수 있습니다. 얻어진 Guidance Map은 A* 알고리즘의 휴리스틱 함수 역할을 하게 되며, Neural A*의 두 번째 단계에서는 이렇게 얻어진 휴리스틱 함수를 이용해 효율적인 A* 트리 탐색이 이루어지게 됩니다. 마지막으로 A* 트리 탐색의 결과로 나오는 탐색 이력 데이터는, 실제 정답 경로와의 차이를 줄이는 방향으로 Guidance Map에 대한 Encoder 네트워크를 재학습시키는데 사용됩니다.

여기서 본 연구의 가장 중요한 기여로써, 미분 가능한(Differentiable) A* 모듈(Module)을 볼 수 있습니다. 일반적으로 A* 탐색은 이산적인 환경에서 이루어지고, 이는 곧 그림 5의 두 번째 단계에서 그래디언트(Gradient)가 흐르지 않아 Encoder 네트워크의 업데이트가 불가능함을 의미합니다. 저자들은 위 문제를 해결하기 위하여, 기존의 A* 알고리즘에서 필요로 하는 연산(Operation)들을 행렬(Matrix) 기반의 연산으로 치환하는 방법을 고안했고, 이를 통해 미분 가능한 A* 모듈이 구현 가능했습니다.

그림 6. 행렬 기반 미분 가능한 A* 트리 확장^[15]

그림 6은 Neural A* 알고리즘에서의 트리 확장(Tree Construction)을 나타냅니다. A* 알고리즘은 탐색 트리를 확장을 통해 생성하게 되는데, 실제로 탐색을 진행해 본 노드(Node)들을 초록색 Closed 리스트(List)로, Closed 리스트에 인접하여 앞으로 탐색을 진행할 후보 노드들을 노란색 Open 리스트라는 이름으로 관리합니다. 효율적인 A* 탐색 트리는 노란색 Open 리스트에 속한 노드 중 (Guidance Map 등으로부터 계산된) 휴리스틱 기반 가치가 가장 높은 빨간색 노드를 선택하고, 선택된 빨간색 노드는 이제 Closed 리스트로 옮겨진 후 빨간색 노드에 인접한 새로운 노드들을 Open 리스트에 추가하는 형태로 트리가 확장됩니다. 이 전 과정은 일반적으로 이산적인 연산을 필요로 하지만, 그림 6에서는 Closed 리스트와 Open 리스트를 각각의 노드가 각 리스트에 속해 있는지 여부를 나타내는 이진 행렬(Binary Matrix) C, O로 표현하고, 각 이진 행렬 및 노드의 가치를 나타내는 행렬 V* 등을 Convolution 연산자 ⊙를 사용하여 업데이트합니다.

다시 그림 5로 돌아가서 살펴보면, A* 트리 탐색이 이루어지는 중간 모듈이 그림 6에서와 같이 행렬 기반의 미분 가능한 연산들로 대체되어, 탐색 이력과 실제 정답 경로와의 차이에 대한 Loss 함수로부터 Guidance Map을 구하기 위한 Encoder 네트워크까지 그래디언트가 흐를 수 있는 구조가 되었음을 알 수 있습니다.

그림 7. 기존 A* 경로 탐색(왼쪽)과 Neural A* 경로 탐색(오른쪽)의 비교 예제^[14]

그림 7은 왼쪽의 일반적인 A* 알고리즘이 탐색하는 경로, 오른쪽의 Guidance Map 학습을 통한 Neural A* 알고리즘이 탐색하는 경로를 비교하여 보여줍니다. Neural A* 알고리즘은 경로 탐색에 필요한 시간을 나타내는 초록색 영역이 훨씬 적어 더 빠르게 최적의 경로를 찾아냄을 알 수 있습니다.

그림 8. Point-to-Point 최적 경로 탐색 비교 실험^[15]

그림 8은 Neural A* 알고리즘을 기존에 데이터 기반 학습을 통한 최적 경로 탐색 알고리즘과 비교합니다. Neural A* 알고리즘이 탐색의 효율을 나타내는 초록색 영역이 훨씬 적고, 생성된 경로도 최단 경로에 더 가까운 것을 알 수 있습니다.

그림 9. 실제 이미지에서 최적 경로 탐색 비교 실험^[15]

그림 9는 실제 도로 이미지에서의 이동 경로에 대한 실험 결과입니다. 그림 8에서와 마찬가지로 Neural A* 알고리즘의 결과가 좀 더 정답 경로에 가까운 모습으로 학습이 되었음을 알 수 있습니다.

지금까지 대표적인 경로 계획 알고리즘인 A* 탐색을 데이터 기반 학습을 통한 Guidance Map 및 미분 가능한 A* 모듈을 이용하여, 좀 더 효율적인 학습 기반의 최적 경로 탐색이 가능함을 알 수 있었습니다. 기존에 이산적인 환경에서 정의되었던 A* 탐색을 미분 가능하게 확장함으로써 데이터 기반의 학습을 가능케 한 점은, 본 연구에서 가장 중요하게 살펴봐야 하는 부분이었습니다. 다만, A* 알고리즘처럼 휴리스틱 기반의 트리 탐색 알고리즘에서는 어떤 휴리스틱 함수를 사용하는지에 따라 얻어지는 경로의 수준 및 탐색 효율이 결정되는데, 의미 있는 Guidance Map이 학습되기 이전 또는 Guidance Map의 학습이 실패한 경우에 대한 실험 결과 및 이에 대한 언급이 없었던 점은 조금 아쉬웠습니다. 또한 A* 탐색이 갖는 큰 장점 중 하나는 허용적 휴리스틱(Admissible Heuristic) 함수에 대해서 최적 경로 탐색에 대한 이론적 보장(Guarantee)이 가능하다는 점이지만, Neural A* 탐색에서는 학습된 Guidance Map을 휴리스틱 함수로 곧바로 사용함으로써 이러한 이론적 보장이 빠지게 되었다는 점도 아쉬운 점 중 하나였습니다.

* 참고 자료 논문 http://proceedings.mlr.press/v139/yonetani21a/yonetani21a.pdf 발표자료 https://icml.cc/media/icml-2021/Slides/9055.pdf 발표영상 https://crossminds.ai/video/path-planning-using-neural-a-search-614bd1e23c7a224a90903035/ 블로그 https://omron-sinicx.github.io/neural-astar/ 소스코드 https://github.com/omron-sinicx/neural-astar

CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints (Paulus et al., ICML 2021)

앞서 배낭 문제에서 살펴본 정수 계획법은 결정해야 할 변수가 정수 집합으로 이산적인 환경에 속해 있었고, 정수 계획법은 최적화 대상인 목적 함수와 변수들이 만족시켜야 할 제약 조건들로 구성되어 있었습니다. 본 연구에서는 배낭 문제와 같은 조합 최적화 문제에서 데이터 기반의 학습을 통해 최적해를 구하는 새로운 방법을 제시합니다. 특히, 본 연구는 주어진 데이터로부터 정수 계획법의 목적 함수 및 제약 조건을 학습하고, 학습된 정수 계획법을 수학적 최적화 도구인 GUROBI[5]를 사용하여 수학적 최적화 과정을 진행한다는 점에서 기존의 데이터 기반 조합 최적화 연구와는 다른 차별점을 보입니다.

그림 10. 정수 계획법의 정의 및 기하학적 의미^[16]

그림 10의 왼쪽 식은 앞서 배낭 문제를 예를 들어 설명했던 정수 계획법의 일반적인 형태입니다. 변수 y는 정수 계획법을 통해 결정해야 할 변수이고 정수 집합 Y에 속해 있습니다. 목적 함수 y·c는 최적화 대상인 비용(Cost) c와 변수 y와의 곱으로써 선형 함수로 정의되고, 제약 조건 Ay ≤ b는 행렬 A와 벡터 b를 통해 마찬가지로 선형 함수로 정의됩니다. 그림 10의 오른쪽 그림은 목적 함수와 제약 조건의 기하학적 의미를 보여줍니다. 선형 함수 Ay ≤ b로 표현된 제약 조건은 그림에서 회색 영역에 해당합니다. 회색 영역의 경계는 제약 조건의 개수(즉, 행렬 A의 행(Row) 개수)만큼의 초평면(Hyper-Plane)들로 구성되어 있고, 주어진 정수 계획법의 실행 가능해 y는 회색 영역 안에서 격자로 표현된 정수값들로써 표현할 수 있습니다. 이 때 정수 계획법의 목적 함수 y·c는 c의 기울기를 갖는 파란색 초평면으로 표현되고, 이러한 파란색 초평면을 기울기 c를 유지하며 점점 회색 영역에 다가가다가 처음으로 실행 가능해 y와 만나는 시점의 y값이 바로 우리가 구하고자 하는 최적 해가 됩니다. 선형 계획법의 경우, 변수 y는 실수값을 가지므로, 실행 가능해는 격자가 아닌 회색 영역 전부가 되어 초평면들로 구성된 회색 영역의 코너 점들 중 하나가 최적해가 됨을 알 수 있습니다. 이에 반해, 정수 계획법의 경우, 실행 가능해 y의 영역이 격자점들이 되어 일반적으로 선형 계획법보다 최적해를 구하기 더 어렵다고 알려져 있습니다.

그림 11. CombOptNet 네트워크 구조 개요도^[16]

그림 11은 저자들이 제안하는 CombOptNet의 네트워크 구조를 나타냅니다. 입력 데이터로부터 정수 계획법의 목적 함수를 나타내는 c와 제약 조건을 나타내는 A,b를 추론(Inference)하고, 추론된 정수 계획법 파라미터(Parameter) A,b,c로부터 수학적 최적화 도구 GUROBI[5]를 사용하여 최적 해 y(A,b,c)를 구합니다. 이렇게 얻은 최적해 y(A,b,c)는 정답 레이블(Label) y와의 차이를 줄이는 방향으로 Loss 함수가 정의되어 학습이 진행될 수 있습니다. 여기서 생각할 수 있는 어려움은, 앞서 살펴본 Neural A* 알고리즘과 마찬가지로 그림 11의 중간에 위치한 정수 계획법의 미분 불가능한 성질 때문에 네트워크 업데이트를 위한 그래디언트가 제대로 흐리지 못한다는 점입니다.

그림 12. 정수 Basis에 따른 그래디언트 분해의 기하학적 의미^[16]

저자들은 이러한 문제를 해결하기 위해 그림 12와 같이 정수 Basis에 따른 그래디언트의 분해(Decomposition) 방법을 제안했습니다. 이를 통해 정수 계획법의 각 파라미터 A, b, c를 위 정수 Basis 기반의 그래디언트로 업데이트할 수 있습니다.

그림 13. 텍스트 기반 배낭 문제^[16]

CombOptNet의 실험적 성능을 보여주기 위한 첫 번째 실험은 그림 13의 텍스트 기반 배낭 문제입니다. 앞에서 설명한 배낭 문제와 동일한 문제이지만, 입력이 문장의 형태로 들어오기 때문에 자연어 처리를 위한 임베딩(Embedding) 네트워크가 추가로 필요합니다. 이때 학습에 사용하는 데이터는 문장으로 입력으로 들어오는 10개의 물건들에 대해 전처리된 임베딩 벡터 x와, 각 물건이 선택되었는지를 나타내는 이진 벡터 y입니다.

그림 14. 텍스트 기반 배낭 문제 실험 결과 비교^[16]

그림 14는 위 텍스트 기반 배낭 문제의 실험 결과 비교입니다. 본 연구에서 제안하는 CombOptNet이 정수 계획법 파라미터 학습의 수학적 최적화 없이 지도 학습 기반을 수행하는 MLP(Multi-Layer Perceptron) 및 선형 계획법으로의 완화(Relaxation)를 통한 근사 해를 구하는 LPmax, 그리고 CombOptNet의 정수 계획법 모듈을 선형 계획법 기반의 CVXPY^[17]로 대체한 CVXPY 대비 높은 정확도를 보임을 알 수 있습니다.

그림 15. 키포인트 매칭 실험 결과^[12]

두 번째 실험은 두 이미지 사이의 키포인트(Key-Point) 매칭입니다. 그림 15에서와 같이, 동물 또는 사물의 특징점들 간의 관계는 Bipartite 그래프로 나타낼 수 있어 조합 최적화 문제로 정의될 수 있습니다. CombOptNet은 이미지 입력에 대해서도 정수 계획법 파라미터 추론을 통해 위와 같은 키포인트 매칭이 가능함을 보여주었습니다.

본 연구는 정수 계획법의 구체적인 공식이 주어지지 않은 조합 최적화 데이터로부터, 명시적인 정수 계획법 파라미터 추론 및 미분 가능한 정수 계획법 모듈을 통한 학습 알고리즘을 제안하였습니다. 이를 통해 텍스트, 이미지 등의 다양한 형태의 데이터에서 조합 최적화 문제를 효과적으로 해결할 수 있는 미분 가능한 네트워크 구조를 제안한 점이 가장 큰 기여라고 보입니다. 다만, 여전히 수학적 최적화 도구에 의존해 정수 계획법의 최적 해를 계산하기 때문에, 문제 자체가 가지는 복잡도가 커지게 되면 수학적 최적화 도구의 한계에 따라 최적 해의 수준이 같이 떨어지는 문제가 생길 여지가 있다는 점이 아쉬운 부분으로 남았습니다.

* 참고 자료 논문 http://proceedings.mlr.press/v139/paulus21a/paulus21a.pdf 발표자료 https://icml.cc/media/icml-2021/Slides/9555.pdf 소스코드 https://github.com/martius-lab/CombOptNet

여기까지 이번 ICML 2021에 발표된 두 가지 딥러닝 기반의 조합 최적화 연구에 대해 살펴봤습니다. 이산적인 환경을 가지는 조합 최적화 문제는 최근의 딥 러닝 기반 인공지능 연구에 익숙한 분들에게는 조금은 낯설고 다른 방향의 생각을 필요로 하는 어려움이 있습니다. 하지만 현실에서 우리가 마주하며 해결해야 하는 문제들 중에는 조합 최적화 문제로 접근해야 하는 경우가 우리의 생각보다 훨씬 잦습니다. 전자 제품 생산에 사용되는 부품이나 식료품 등 다양한 생필품들에 대한 생산 계획 최적화, 화물 트럭 또는 택배 운송 시 물류의 적절한 적재 및 이동 경로 최적화 등은 대표적인 조합 최적화 문제로써, 여전히 해결해야 할 문제들로 남아 있습니다. 또한, 전자 회로 설계 시 전자 부품의 적절한 배치 및 부품 간 배선이라는 조합 최적화 문제도 아직 풀리지 않은 난제로 남아 있습니다. 이러한 문제들에 있어, 딥 러닝을 기반으로 하는 조합 최적화 연구는 아직까지 해결하지 못한 난제에 대한 새로운 해결의 실마리를 제공해 줄 수 있을 것이라고 생각합니다.


LG AI연구원 Di Lab 이강훈님의 ICML 2021 Review 영상 보러 가기 (Link)