기술 요약: 학습과 탐색을 통한 조합 최적화에서의 인간 유사 솔루션 이해

1. 문제 정의

유클리드 외판원 문제(TSP)와 같은 조합 최적화 문제는 계산적으로 매우 어렵지만(NP-hard), 인간은 엄격한 시간 및 인지적 제약 하에서도 최적에 가까운 효율성으로 이를 해결하곤 한다. 인간은 수학적 최적해보다 약 10% 정도 더 긴 경로만을 생성하는 데 그치지만, 이러한 "인간다운" 성능의 기저에 깔린 구체적인 인지 알고리즘과 기하학적 원리는 여전히 불분명하다. 기존의 계산 모델들은 대개 전수 조사(계산 비용이 많이 듦)나 단순 휴리스틱(종종 하위 최적이며 인간의 구조적 패턴을 포착하지 못함)에 의존한다. 핵심 과제는 TSP를 효율적으로 해결할 뿐만 아니라, 인간의 솔루션에서 나타나는 특유의 기하학적 시그니처와 체계적인 편차를 재현할 수 있는 계산 프레임워크를 식별하는 것이다.

2. 방법론

2.1 대규모 행동 데이터 수집 (tsp150k)

저자들은 인간의 TSP 수행 능력에 관한 역대 최대 규모의 행동 실험을 수행하여 tsp150k 데이터셋을 생성하였다.

• 참가자: 1,107명.
• 규모: 150,000개의 고유한 TSP 인스턴스와 2,000만 개 이상의 인간 생성 경로.
• 복잡도 수준: 도시 수에 따라 5단계로 구분 (10, 12, 15, 19, 24개 도시).
• 프로토콜: 참가자들은 위챗(WeChat) 통합 플랫폼을 통해 온라인으로 TSP 인스턴스를 해결하였다. 시간 제한은 도시 수의 두 배로 설정되었다 (예: 10개 도시의 경우 20초). 과제 수행 중 경로 길이에 대한 피드백은 제공되지 않았다.
• 데이터 밀도: 각 인스턴스는 92개에서 207개 사이의 인간 경로(평균 139개)를 할당받아, 인간 행동의 견고한 통계적 특성화를 가능하게 했다.

2.2 계산 모델링 프레임워크

본 연구는 **탐색 전용 방식(search-only methods)**과 **하이브리드 학습-탐색 방식(hybrid learning-and-search methods)**으로 분류된 광범 চ범위한 가설 공간을 평가하였다.

• 탐색 전용 베이스라인:

  • 정확해(Exact): 최적해를 위한 Concorde (branch-and-cut).
  • 휴리스틱(Heuristics): 최근접 이웃(Nearest Neighbor), 볼록 껍질 최저 비용 삽입(Convex Hull Cheapest Insertion), 최대 내부각(Largest Interior Angle).
  • 완화(Relaxation): 탄성 망(Elastic Net, 변형 가능한 링에 대한 경사 하강법).

• 신경망 모델 (포인터 네트워크):
  저자들은 유효한 경로에 대한 확률 분포를 정의하기 위해 포인터 네트워크(Attention 기반 포인팅 메커니즘을 가진 RNN)를 활용하였다. 네 가지 뚜렷한 훈련 체계가 테스트되었다:

  1. $p_{optimal}$: 최적 경로(Concorde 솔루션)에 대한 지도 학습(Supervised learning).
  2. $p_{RL}$: 음의 유클리드 경로 길이를 보상으로 사용하는 강화 학습(Reinforcement Learning).
  3. $p_{optimal+RL}$: 최적 경로에 대한 지도 학습 사전 훈련 후 RL 미세 조정.
  4. $p_{human}$: 인간의 경로를 직접 학습 (경험적 상한선 역할).

• 디코딩 전략:
  훈련된 정책으로부터 경로를 생성하기 위해 세 가지 탐색 전략이 적용되었다:

  1. 그리디 디코딩 (Greedy Decoding): 가장 확률이 높은 다음 도시를 근시안적으로 선택.
  2. 빔 서치 (Beam Search): 가장 확률이 높은 전체 시퀀스의 휴리스틱 근사.
  3. Best-of-$N$ 샘플링: $N$개의 완전한 경로를 무작위로 샘플링하고 그 중 가장 짧은 것을 선택.

2.3 평가 지표

모델 성능은 홀드아웃 테스트 세트(50,000개 인스턴스)에서 인간의 경로와 모델의 경로를 비교하는 다섯 가지 쌍별 유사도 지표를 사용하여 평가되었다:

1. 에지 중첩 비율 (EOR, Edge Overlap Ratio): 공유된 에지의 비율.
2. 최장 공통 부분 문자열 (LCS, Longest Common Substring): 공유되는 연속적인 도시 시퀀스의 최대 길이.
3. 레벤슈타인 거리 (LD, Levenshtein Distance): 한 경로를 다른 경로로 변환하는 데 필요한 최소 편집 횟수.
4. 프레셰 거리 (FD, Fréchet Distance): 순회 순서상의 대응하는 점들 사이의 공간적 분리.
5. 켄달의 타우 ($\tau$, Kendall's $\tau$): 방문 순서의 순위 상관관계.

• 기하학적 분석: 인간 솔루션의 "기하학적 영역(geometric basin)"을 특성화하기 위해 8가지 특정 기하학적 특징(매끄러움, 회전각 엔트로피, 볼록 껍질 보존, 2-opt 최적성 등)을 추출하였다.

3. 주요 결과

3.1 인간의 수행 특성

• 인간의 경로는 최적에 가깝지만 체계적인 편차를 보이며, "최적에 가까운 기하학적 영역(near-optimal geometric basin)"을 점유한다.
• 인간은 초기 위치에서 숙고하는 데 훨씬 더 많은 시간을 소비하며, 이는 "생각 후 실행(think-then-implement)" 전략을 시사한다.
• 이전에 방문한 도시를 제외한 후, 인간의 다음 도시 선택은 높은 수준의 국소 최적성(local optimality)에서 안정화된다.

3.2 모델 성능 비교

• 탐색 전용 모델: 최적 경로(Concorde)와 탄성 망(Elastic Net)은 단순 휴리스틱 및 무작위 인간 베이스라인보다 우수한 성능을 보이며 인간의 경로와 높은 유사성을 달성했다. 그러나 이들은 인간 특유의 하위 최적성 시그니처(예: 수학적 최적해보다 낮은 매끄러움 및 약한 볼록 껍질 보존)를 포착하는 데 실패했다.
• 순수 지도 학습 ($p_{human}$): 인간의 경로로 직접 훈련되고 빔 서치를 사용한 모델이 가장 높은 전체 정렬도(Aggregate Score: 0.600)를 달s하여 경험적 상한선을 설정했다.
• 가장 일반화 능력이 뛰어난 모델 ($p_{optimal+RL}$): 인간 데이터로 훈련되지 않은 모델 중, 최적 경로로 사전 훈련되고 RL로 미세 조정된 포인터 네트워크를 **Best-of-$N$ 샘플링 ($N=100$)**으로 디코딩했을 때 가장 강력한 인간 유사성(Aggregate Score: 0.600)을 달성했다.
  • 이 모델은 8가지 특징에 대해 피어슨 상관계수($r = 0.583$)를 보이며 인간의 기하학적 특징과 밀접하게 일치했고, 가장 낮은 평균 절대 오차(MAE = 0.021)를 기록했다.
  • 이 모델은 순수 최적해 솔버가 놓치는 특유의 인간적 하위 최적성(예: 완벽하지 않은 볼록 껍질 보존)을 성공적으로 재현했다.

3.3 기하학적 영역 분석

• 인간의 경로는 순수 최적 경로와 구별된다. 즉, 더 낮은 매끄러움과 낮은 2-opt 국소 최적성을 보인다.
• $p_{optimal}$ 모델은 최적의 기하학적 영역으로 너무 빠르게 수렴하여 인간의 편차를 놓친다.
• $p_{RL}$ 모델은 높은 보상을 받는 좁은 경로 집합에 과도하게 집중되어, 테스트 시 탐색을 통해 인간과 유사한 변이(variation)를 찾아내는 데 필요한 다양성이 부족하다.
• $p_{optimal+RL}$은 균형을 잡는다: 지도 학습 사전 훈련은 기하학적으로 최적에 가까운 경로들에 대한 넓은 지지(support)를 제공하고, RL 미세 조정은 다양성을 제거하지 않으면서 경로를 더 짧게 만드는 방향으로 분포를 편향시킨다. 이를 통해 Best-of-$N$ 샘플링이 인간의 행동과 일치하는 영역으로 수렴할 수 있게 한다.

4. 주요 기여

1. tsp150k 데이터셋: 150,000개의 TSP 인스턴스와 2,000만 개 이상의 인간 경로를 포함하는 대규모 고품질 데이터셋을 구축하여 인간 행동의 체계적 특성화를 가능하게 했다.
2. 인간 유사 메커니즘 식별: 인간다운 솔루션이 단순히 최적 경로를 모방하는 것이 아니라, 구조화된 지도 학습(기하학적 지식 습득), 강화 학습(효율성 최적화), 그리고 테스트 시 탐색(Best-of-$N$ 샘플링)의 특정 결합으로부터 발생함을 입증했다.
3. 기하학적 특성화: 인간 솔루션의 "기하학적 영역"을 정의함으로써, 인간이 최적해와 구조적 속성을 공유하면서도 표준 휴리스틱이나 순수 최적 솔버가 포착하지 못하는 체계적인 편차(예: 매끄러움 및 볼록 껍질 보존의 차이)를 유지함을 보여주었다.
4. 인지 모델링 프레임워크 제안: 조합 공간에서의 인간 문제 해결을 두 단계 과정으로 모델링할 것을 제안한다: 고품질 사례로부터 구조적 지식을 습득(모방)하고, 경험 기반 피드백을 통해 이를 정교화(RL)한 뒤, 테스트 시점에 숙고(탐색)하는 과정이다.

5. 의의 및 주장

본 논문은 조합 최적화에서의 인간다운 성능이 고정된 핸드크래프트 휴리스틱이 아니라, 학습과 탐색을 통합하는 계산 아키텍처로부터 발생한다고 주장한다. 구체적으로:

• 학습-탐색 시너지: 인간 행동을 가장 정확하게 모델링하는 것은 인간 데이터를 직접 모방하는 모델이 아니라, 최적 데이터로 훈련되고 RL로 정교화되며 탐색으로 디코딩되는 모델이다. 이는 인간이 고품질 사례에 대한 노출을 통해 광범위한 기하학적 지식을 습득하고, 경험적 피드백을 통해 이러한 표현을 정교화할 수 있음을 시사한다.
• 테스트 시 계산(Test-Time Compute)의 역할: 본 연구는 "테스트 시 계산"(예: Best-of-$N$ 샘플링)이 인지 모델링에서 흔히 간과되는 중요한 요소임을 강조한다. 이는 정적인 신경망이 가중치를 수정하지 않고도 인간과 유사한 솔루션의 변이성을 생성할 수 있게 하며, 이는 거대 언어 모델의 '생각의 사슬(chain-of-thought)' 추론 메커니즘과 평행을 이룬다.
• 일반화 가능성: 연구 결과는 AI의 "쓰라린 교훈(bitter lesson)"—즉, 고정된 휴리스틱보다 학습과 계산에 의존하는 것—이 인간의 인지에도 적용될 수 있음을 시사한다. 복잡한 문제에 대한 인간의 솔루션은 경험으로부터 학습하고 탐색을 통해 계산을 활용하는 범용적인 방법론의 인지적 대응물(analogue)을 반영할 수 있다.

저자들은 인간의 지도 학습을 위한 "최적의 시연(optimal demonstrations)"의 출처가 무엇인지(아마도 더 단순한 인스턴스로부터의 커리큘럼 학습과 관련될 것)는 여전히 열려 있는 과제라고 언급하며 신중한 태도를 취했다.