Головоломка от Jane Street

Компания Jane Street опубликовала сложную задачу для специалистов по машинному обучению. Участникам предоставили полную структуру нейросети, включая все веса, но без описания функции, которую она выполняет. Задача заключалась в том, чтобы понять принцип работы «черного ящика», который на большинство входных данных выдавал ноль.

Особенность модели заключалась в том, что её нельзя было взломать традиционным методом обратного распространения ошибки. Веса были целыми числами, а сама архитектура была спроектирована вручную так, чтобы исключить возможность подбора входных данных через оптимизацию.

Методы анализа и упрощение модели

Студент Алекс приступил к решению, проанализировав последний слой модели PyTorch. Он обнаружил, что веса в нем являются целыми числами, а структура слоев имеет специфическую периодичность. Исследование показало, что сеть состоит из 2500 линейных слоев, при этом около 1500 из них выполняли тождественные преобразования.

Для решения задачи Алекс применил несколько подходов. Сначала он попытался представить нейросеть как задачу целочисленного линейного программирования, но объем переменных оказался слишком велик. После упрощения графа нейросети путем объединения идентичных узлов и отсечения лишних связей количество переменных сократилось с двух миллионов до 75 тысяч. Однако даже это не позволило решателю завершить вычисления.

Переход к SAT-решателю и поиск хеш-функции

Следующим шагом стал переход к SAT-решателю. Используя ограничения на диапазоны значений в каждом узле, Алекс смог сократить количество переменных до 20 тысяч. Несмотря на это, вычислительное ядро сети оставалось слишком сложным для полного перебора.

В итоге исследователь сменил стратегию и предположил, что в основе лежит необратимая функция. Проанализировав периодическую структуру слоев и обратившись к ChatGPT для сопоставления архитектуры с известными алгоритмами, Алекс обнаружил, что 32 повторяющихся блока соответствуют структуре популярных хеш-функций. Проверив гипотезу путем ручного сопоставления активаций предпоследнего слоя с различными алгоритмами, он подтвердил, что внутри нейросети зашифрован MD5.