Проблема «черного ящика» в нейросетевых решениях TSP
Традиционные методы обучения с подкреплением или обучением с учителем для задачи коммивояжера (TSP) часто оцениваются только по итоговому туру, полученному после декодирования. При этом сама нейросеть обучается в «суррогатном пространстве» — например, генерирует тепловые карты (heatmaps), политики построения или оценки для поиска. Это скрывает фундаментальный вопрос: какую именно гамильтонову структуру модель выучила до этапа финального декодирования? Часто структура тура формируется лишь на этапе постобработки, а не является результатом осмысленного обучения.
Решение C2TSP: Обучение через «Connected-by-Construction»
Авторы (Ke Sun, Xinyuan Zhang, Xinwu Qian) предлагают метод C2TSP (Connected by Construction), который учит модель работать с структурно значимым латентным объектом. Вместо того чтобы полагаться на финальный этап декодирования для формирования связности, C2TSP использует семейство Гиббса для корневых 1-деревьев (rooted 1-trees). Это позволяет модели напрямую обучаться распределению, близкому к реальному туру.
Ключевые технические компоненты пайплайна:
- Непрерывное дифференцирование: Модель учит остаточные возмущения рёбер (residual edge perturbations) от unbiased TSP cost через неявную дифференциацию (implicit differentiation).
- Слой Хелда-Карпа (Held-Karp layer): Используется для структурной коррекции, восстанавливая баланс ожидаемых степеней вершин (expected degree balance), что критично для формирования цикла.
- Sharpening с сертификатами: Метод «заточения» распределения, направленный на то, чтобы сделать вероятностное распределение более «туроподобным» (tour-like), отбрасывая слабые связи.
Результаты и значимость
Эксперименты показывают, что C2TSP обеспечивает сильную производительность при декодировании, сохраняя при этом интерпретируемую структурную информацию. Аблиционные исследования (ablations) подтверждают, что именно совместное использование возмущений рёбер и sharpening с сертификатами дает прирост как в стоимости тура, так и в структурном сходстве с оптимальным решением.
Этот подход меняет парадигму: вместо того чтобы заставлять модель «угадывать» путь через вероятности рёбер, мы заставляем её учить структуру графа, которая уже почти является решением задачи.
Источник: arXiv cs.AI ↗