당신이 마치 배송 트럭의 가장 효율적인 경로를 계획하거나 완벽한 와인 한 배치를 혼합하는 것처럼, 거대하고 복잡한 퍼즐을 풀려고 노력하고 있다고 상상해 보십시오. 종종 게임의 규칙은 '블랙박스' 안에 숨겨져 있습니다. 즉, 수백만 개의 사례를 관찰하며 세상이 어떻게 돌아가는지 학습한 복잡한 컴퓨터 프로그램(신경망)입니다. 당신은 무엇이 들어가고 무엇이 나오는지 알지만, 그 안의 비밀스러운 수학적 원리는 알지 못합니다. 최상의 해결책을 찾기 위해서는 이 블랙박스를 열어 당신의 퍼즐 속에 끼워 넣어야 합니다. 문제는 가장 흔한 유형의 블랙박스가 삐죽삐죽하고 지그재그로 꺾인 미로라는 점입니다. 이 미로 속에서 완벽한 경로를 찾는 것은 눈을 가리고 루빅스 큐브를 푸는 것만큼이나 어려워서, 컴퓨터는 답을 찾기도 전에 포기해 버리곤 합니다.

이 논문은 바로 그 골칫거리를 다룹니다. 이 논문은 **입력 볼록 신경망(Input Convex Neural Network, ICNN)**이라는 특별한 종류의 블랙박스를 소개합니다. 이것을 삐죽삐죽한 미로가 아니라, 매끄럽고 그릇 모양인 슬라이드라고 생각하십시오. 이 형태는 매우 예측 가능하기 때문에(오직 한 방향으로만 휘어짐), 컴퓨터는 걸리지 않고 바닥까지 미끄러져 내려갈 수 있습니다. 저자들은 이 매끄러운 슬라이드를 사용함으로써, 기존의 방식보다 훨씬 더 빠르고 적은 컴퓨팅 자원으로 최적화 퍼즐을 해결할 수 있음을 보여줍니다. 그들은 단순히 이렇게 될 것이라고 추측한 것이 아니라, 이를 증명하기 위해 새로운 수학적 도구를 구축했으며, 식량 구호 전달이나 석유 시추와 같은 실제 문제에 적용하여 그들의 방법이 기존 방식보다 종종 천 배 더 빠르다는 것을 확인했습니다.

문제점: 삐죽삐죽한 미로 vs. 매끄러운 슬라이드

운영 연구(의사결정을 내리는 과학)의 세계에서, 우리는 종-종 신경망을 대리 모델(surrogate)로 사용합니다. 대리 모델은 복잡하고 계산 비용이 많이 드는 프로세스를 흉내 내어 우리가 빠르게 결정을 내릴 수 있도록 돕는 '대역 배우'와 같습니다. 수년 동안 표준적인 대역 모델은 **피드포워드 신경망(Feedforward Neural Network, FNN)**이었습니다. FNN을 수천 개의 작고 날카로운 계단과 절벽으로 이루어진 지형이라고 상상해 보십시오. 이는 결과 예측에는 매우 정확하지만, 너무나 삐죽삐죽하기 때문에 최적화하기에는 악몽과 같습니다. 최적의 해를 찾기 위해 컴퓨터는 문제를 거대한 "예/아니오" 질문(이진 변수) 목록으로 변환해야 하며, 이는 조합 폭발을 일으킵니다. 이는 마치 모든 돌 하나하나를 일일이 확인하며 산맥에서 가장 낮은 지점을 찾는 것과 같습니다. 네트워크가 커질수록 소요되는 시간은 너무 빠르게 증가하여 컴퓨터가 시간을 다 써버리게 됩니다.

저자들은 만약 우리가 모델링하려는 실제 프로세스가 자연스럽게 매끄럽고 곡선 형태(예: 그릇이나 언덕)라면, 삐죽삐죽한 FNN에게 그 일을 강요해서는 안 된다고 주장합니다. 대신 **입력 볼록 신경망(ICNN)**을 사용해야 합니다. ICNN은 엄격한 규칙을 가진 신경망입니다. 즉, 오직 한 방향으로만 휘어져야 한다는 것입니다. 이것은 매끄러운 슬라이드나 완벽한 그릇과 같습니다. 이러한 구조적 제약은 수학적 처리를 훨씬 쉽게 만듭니다.

발견: 두 가지 승리 방법

이 논문은 이러한 매끄러운 ICNN을 사용하여 최적화 문제를 해결하는 두 가지 주요 방법을 탐구했으며, 두 방법 모두 기존 방식보다 우월하다는 것을 발견했습니다.

1. "더 타이트한 압착" (ICNN-MIP)
첫째, 저자들은 여전히 표준적인 "예/아니오" 방식(혼합 정수 계획법, MIP)을 사용하되, 삐죽삐죽한 FNN을 매끄러운 ICNN으로 교체했을 때 어떤 일이 일어나는지 살펴보았습니다. 그들은 ICNN의 "완화(relaxation)"(답을 추측하기 위해 사용하는 단순화된 버전의 문제)가 믿을 수 없을 정도로 타이트하다는 것을 수학적으로 증명했습니다.

• 비유: 수박의 무게를 추측한다고 상상해 보십시오. FNN 방식은 수박이 어디에든 있을 수 있는 아주 크고 헐거운 상자를 제공합니다. 반면 ICNN 방식은 수박을 완벽하게 감싸는 상자를 제공합니다.
• 결과: ICNN의 상자가 매우 타이트하기 때문에, 컴퓨터는 거의 많은 가능성을 확인할 필요가 없습니다. 테스트 결과, ICNN 버전은 FNN 버전이 한 시간 동안 해결하지 못한 문제를 단 몇 초 만에 해결했습니다. 어떤 경우에는 ICNN 방식이 분기(branching)를 전혀 할 필요 없이 즉시 완벽한 답을 찾아냈으며, 반면 FNN 방식은 수백만 개의 막다른 길에서 헤맸습니다.

2. "미끄러운 슬라이드" (ICNN-BB)
둘째, 그리고 아마도 더 흥-미로운 점은, 그들이 ICNN-BB라는 완전히 새로운 알고리즘을 개발했다는 것입니다. 이 방법은 "예/아니오" 질문을 완전히 버립니다. ICNN은 매끄럽고 볼록하기 때문에, 저자들은 이 전체 네트워크를 이진 변수 없이 오직 간단한 선형 방정식(직선과 같은)만으로 설명할 수 있다는 것을 깨달았습니다.

• 비유: 로프와 갈고리를 들고 삐죽삐죽한 산을 오르는 대신, 그냥 마찰이 없는 매끄러운 슬라이드를 타고 내려가는 것입니다.
• 주의점: 이 슬라이드는 문제가 특정 방식으로 설정되었을 때(최소화 문제일 때) 완벽하게 작동합니다. 만약 문제가 더 복잡하다면, 슬라이드에 작은 틈이 생길 수 있습니다. 이를 해결하기 위해 저자들은 슬라이드 위에 놓여 빈틈을 잡아주는 안전망인 "오목 포락선(concave envelope)"을 구축했습니다. 그들은 슬라이드(에피그래프)와 안전망(오목 포괄선)을 결합하여 신경망에 대한 가장 강력한 수학적 설명을 만들어냈습니다.
• 결과: 그들의 새로운 알고리즘인 ICNN-BB는 내부 뉴런이 아닌 입력 변수(당신이 결정하려는 것들)에서 직접 분기합니다. 이는 엄청난 효율성 향상입니다. 테스트에서 이 방법은 특히 문제가 너무 복잡하지 않을 때 가장 빨랐습니다.

실제 세계 테스트

이것이 단순히 종이 위의 수학이 아님을 증명하기 위해, 저자들은 세 가지 매우 다른 실제 시나리오에서 그들의 아이디어를 테스트했습니다.

1. 인도적 식량 구호: 그들은 비용을 최소화하면서 영양 및 맛 요구 사항을 충족하면서 사람들에게 식량을 전달하는 시스템을 모델링했습니다. 여기서 "맛" 부분이 블랙박스였습니다.

   • 결과: ICNN 방식은 믿을 수 없을 정도로 빨랐습니다. 표준 FNN 방식은 더 큰 네트워크에서 해결책을 찾지 못한 채 한 시간 넘게 걸리며 실패했습니다. ICNN 방식은 동일한 문제를 1초도 안 되어 해결했습니다. 더욱이, ICNN-BB 방식은 너무 정확해서 첫 번째 단계에서 즉시 멈췄는데, 이는 "슬라이드"가 이 문제에 완벽했음을 입증합니다.

2. 유정 경로 지정: 이것은 유정에서 처리 시설로 기름을 보내는 경로를 결정하는 문제로, 까다로운 물리 법칙과 이진 선택(파이프를 열거나 닫기)이 가득한 문제입니다.

   • 결과: 여기서도 ICNN 방식이 승리했지만, 경기는 더 치열했습니다. ICNN-MIP 방식은 FNN 방식이 손댈 수 없는 문제를 해결했습니다. ICNN-BB 방식은 작은 규모의 문제에서는 가장 빨랐지만, 가장 큰 규모의 문제에서는 "안전망"(오목 포괄선)을 계산하는 것이 너무 복잡해져서 속도가 느려졌습니다. 이는 명확한 한계를 보여주었습니다: ICNN-BB는 저~중간 복잡도에서는 놀랍지만, 변수가 너무 많아지면 "안전망"이 너무 무거워집니다.

3. 와인 블렌딩: 와인 메이커가 최고의 맛을 내면서도 비용을 최소화하기 위해 여러 공급업체의 포도를 혼합하는 문제입니다.

   • 결과: 유정 문제와 유사하게, ICNN 방식은 FNN 방식보다 훨씬 빠르고 신뢰할 수 있었습니다. ICNN-BB 방식은 작은 배치에서는 챔피언이었지만, 블렌딩의 수가 증가함에 따라 "안전망"을 계산하는 비용이 커졌고, 결국 표준 ICNN-MIP 방식이 더 나은 선택이 되었습니다.

핵심 요약

이 논문은 기반이 되는 관계가 매끄럽거나 곡선 형태인 최적화 문제에서 **입력 볼록 신경망이 새로운 기본 선택(default choice)**이라고 결론짓습니다. 이들은 두 단계의 이점을 제공합니다:

1. 표준 솔버와 함께 사용할 경우(ICNN-MIP), 이전보다 훨씬 더 타이트하고 효율적인 탐색을 얻을 수 있습니다.
2. 그들의 새로운 특화 알고리즘(ICNN-BB)을 사용할 경우, 이진 변수 없이 문제를 해결할 수 있어 엄청난 속도 향상을 가져올 수 있습니다.

하지만 저자들은 이것이 모든 것에 대한 마법의 해결책은 아니라는 점을 주의 깊게 언급합니다. ICNN-BB 방식은 입력 변수의 수가 너무 많아지면(와인 블렌딩 테스트의 55차원처럼) 벽에 부딪히는데, 이는 "안전망"을 계산하는 비용이 너무 많이 들기 때문입니다. 하지만 광범위한 문제들에 대해, 이 접근 방식은 계산적으로 불가능했던 악몽을 빠르고 매끄러운 슬라이드로 바꿔놓습니다. 저자들은 미래에 더 스마트한 방식으로 이러한 안전망을 구축하거나, 볼록(convex) 신경망과 비볼록(non-convex) 신경망을 혼합하여 두 세계의 장점만을 취하는 방법이 나타날 것이라고 제안합니다.