Stabilized Best-of-$K$ Training for Neural Combinatorial Optimization

당신이 거대한 실타래를 풀려고 노력하고 있다고 상상해 보세요. 하지만 전체 그림을 한 번에 볼 수는 없습니다. 한쪽 끝을 잡아당겨 보고, 그것이 어디로 가는지 확인한 다음, 다시 시도해야 합니다. 이것은 컴퓨터 과학자들이 인공지능에게 '외판원 문제'(여러 도시를 방문하는 가장 짧은 경로 찾기)와 같은 복잡한 퍼즐을 푸는 법을 가르치는 분야인 '신경 조합 최적화(Neural Combinatorial Optimization)'의 일상적인 사투입니다. 목표는 간단합니다. 완벽한 경로를 찾는 것입니다. 하지만 경로는 숨겨져 있고, 컴퓨터는 추측해야 합니다.

추측을 더 잘하기 위해, 이 컴퓨터들은 '강화 학습(Reinforcement Learning)'이라는 기술을 사용합니다. 이것은 강아지를 훈련시키는 것과 같습니다. 강아지가 앉으면 간식(보상)을 줍니다. 만약 뛰어오르면 아무것도 얻지 못합니다. 시간이 흐르면서 강아지는 더 자주 앉는 법을 배웁니다. AI의 세계에서 '강아지'는 신경망이고, '간식'은 그 솔루션이 얼마나 좋은지에 기반한 점수입니다. POMO(다중 최적해를 이용한 정책 최적화)라고 불리는 인기 있는 방법은 AI가 동시에 여러 가지 시작점에서 퍼즐을 시도하게 함으로써 작동합니다. 마치 열 명의 서로 다른 탐험가를 보내 가장 짧은 경로를 찾게 하는 것과 같습니다. 보통 AI는 이 모든 탐험가의 평균적인 성과로부터 학습합니다. 그러나 '리더 리워드(Leader Reward)'라는 새로운 아이디어는 AI가 그룹 내의 단 한 명의 최고 탐험가에게 각별한 주의를 기울여, 그 '리더'를 주인공처럼 대우해야 한다고 제안했습니다.

이제, 당신이 퍼즐을 풀기 위해 탐험가 팀을 고용한다고 상상해 보세요. 하지만 당신에게는 엄격한 규칙이 있습니다. 그들이 가져온 지도 중 가장 좋은 것 하나만 남길 것이라는 규칙입니다. 한 연구는 흥미로운 질문을 던집니다. 만약 당신이 100개의 지도 중 상위 8개만을 보관할 것이라는 것을 알고 있다면, 당신의 팀을 단 하나의 최고가 되도록 훈련시켜야 할까요, 아니면 상위 8등 안에 들 수 있는 '누구라도' 될 수 있도록 훈련시켜야 할까요? 이것이 바로 독립 연구자인 멜비나 졸리(Melveena Jolly)와 미둔 자비어(Midhun Xavier)가 수행한 최근 연구의 핵심입니다. 그들은 새로운 종류의 탐험가를 발명하거나 새로운 퍼즐을 만든 것이 아닙니다. 대신, 기존 AI의 훈련 규칙을 약간 수정하여, '상위 8위'의 사고방식이 실제로 배치되었을 때 팀을 더 똑똑하게 만들 수 있는지 확인했습니다.

실험: "베스트 오브 에이트(Best of Eight)"를 위한 훈련

연구진은 TSP-100(100개 도시 방문)이라는 고전적인 퍼즐에 대해 훈련된 표준 AI 설정을 가져와 특정 테스트를 실행했습니다. 그들은 AI가 실수를 통해 배우는 방식을 바꾸는 것이, AI가 여러 솔루션을 생성하고 그중 최고를 선택하도록 요청받았을 때 도움이 되는지 확인하고 싶었습니다.

기존 방식(리더 리워드)에서 AI는 100번의 시도 중 단 하나의 최고 솔루션에 집착하도록 훈련되었습니다. 그것은 마치 코치가 "첫 번째로 들어온 사람만 중요해! 나머지는 다 집에 가!"라고 소리치는 것과 같았습니다. 'Stabilized Best-of-K'라고 부르는 새로운 방법은 코치의 목소리를 바꾸었습니다. 단 한 명의 승자만을 무시하는 대신, 새로운 코치는 "만약 네가 상위 8위 안에 든다면 간식을 줄게! 하지만 9위 이하라면 못 받아!"라고 말했습니다. 이름의 'K'는 이 숫자 8을 의미합니다. 연구진은 또한 훈련 수치가 너무 커지거나 노이즈가 심해지지 않도록 수학적 안전장치인 '스테빌라이저(stabilizer, 안정화 장치)'를 추가했습니다.

결과: 게임에 따라 다르다

결과는 "좋은 소식"과 "상황에 따라 다르다"가 섞여 있었습니다.

먼저, 연구진은 그들의 새로운 시스템이 표준 게임을 플레이할 때 기존의 방식을 따라잡을 수 있는지 확인했습니다. 특정 디코딩(AI의 답을 읽는 방식)을 사용하여 기존의 "100번 시작, 최고 선택" 방식을 사용했을 때, 새 시스템은 이전 기록인 7.766을 거의 똑같이 달着하며 7.7662의 점수를 기록했습니다. 이는 그들이 동일한 규칙으로 플레이하고 있으며 무언가를 망가뜨리지 않았음을 증명했습니다.

하지만 진짜 마법은 게임의 규칙을 새로운 훈련에 맞춰 변경했을 때 일어났습니다. 그들이 AI에게 8개의 독립적인 솔루션을 생성하고 그중 최고를 선택하도록 요청했을 때(Best-of-8 시나리오), 새로운 'Stabilized Best-of-K' 방식이 승리했습니다. 수행된 모든 테스트 실행에서, 새로운 방식은 기존 방식보다 더 짧은 경로를 찾아냈습니다. 평균적으로 새로운 방식은 비용(경로의 길이)을 약 0.25% 줄였습니다. 이것이 작게 느껴질 수 있지만, 이러한 퍼즐의 세계에서 아주 미세한 거리라도 줄이는 것은 매우 큰 일입니다. 이는 AI의 성능을 이론적인 '완벽한' 솔루션에 더 가깝게 만들었습니다.

그러나 여기에는 반전이 있습니다. 새로운 방식이 모든 상황에서 통하는 마법의 탄환은 아닙니다.

• 하나만 선택한다면: AI가 단 하나의 솔루션만 선택할 수 있는 경우(Best-of-1), 기존의 "리더 리워드" 방식이 실제로 더 좋았습니다.
• 매우 많은 수를 선택한다면: 만약 AI가 128개의 솔루션을 선택할 수 있게 한다면, 새로운 방식이 여전히 약간 더 나았지만, 선택지가 늘어날수록 그 이점은 작아졌습니다.
• 다른 디코더를 사용한다면: 다른 방식의 답변 읽기(augmented greedy)를 사용했을 때는 기존 방식이 다시 약간 더 나았습니다.

결론

그렇다면 이 모든 것이 무엇을 의미할까요? 연구진은 만약 당신이 소규모 배치(예: 8개)를 생성하고 그중 최고를 선택하는 방식으로 AI를 사용할 계획이라면, AI에게 단순히 '챔피언'이 되기보다는 '상위권 경쟁자'가 되도록 가르치는 것이 현명한 선택이라는 것을 발견했습니다. 이것은 마치 단 한 명의 슈퍼스타가 아니라 강력한 스쿼드를 갖춘 팀을 훈련시키는 것과 같습니다.

하지만 저자들은 과도한 홍보를 경계하며 매우 신중하게 접근합니다. 그들은 이것이 모든 것을 해결하는 '최첨단(state-of-the-art)'의 돌파구가 아님을 명시적으로 밝힙니다. 이것은 특정 설정에 대한 구체적인 개선입니다. 그들은 단 세 개의 '시드(seed, 무작위 시작점)'에 대해서만 테스트했는데, 이는 패턴을 보기에는 충분하지만 이 방법이 영원히 작동한다는 것을 증명하기에는 부족합니다. 또한 그들은 자신들의 방법이 완벽한 수학적 증명이라기보다는 하나의 '엔지니어링 레시피'임을 인정합니다.

요약하자면, 이 연구는 만약 당신이 라우팅 퍼즐을 풀기 위해 AI를 구축하고 있고, 승자를 뽑기 전에 몇 번의 시도를 허용할 의도가 있다면, AI에게 '1등'이 아닌 '상위 8위'를 목표로 하도록 가르치는 것이 좋은 전략임을 시사합니다. 하지만 단 한 번의 기회만 있거나, 혹은 엄청나게 많은 시도가 가능하다면, 기존의 방식이 여전히 최선일 수 있습니다. 이것은 모든 것을 바꾸는 혁명이 아니라, AI 세계의 특정 영역을 위한 정교하고 유용한 미세 조정입니다.