На прошлой неделе GPT-5.6 и Claude Fable, похоже, окончательно разрешили открытый теоретический вопрос в беспроводной связи, который активно изучали с 2000-х по 2010-е годы и над которым я немного поработал, будучи тревожным аспирантом первого года обучения. Ответ наконец-то появился, возможно, потому что я был одним из последних, кто задал этот вопрос, и первым, кто попросил машины решить его 😊
Результат: вы отправляете N бит через гауссовский беспроводной канал размера N×N, и приёмник должен восстановить все их точно. С 2000-х годов известно, что теоретически это возможно с точки зрения теории информации, когда отношение сигнал/шум составляет не менее 2 log N. Но единственным известным методом, позволяющим достичь этого, был алгоритм экспоненциального перебора. Теперь есть доказательство, что простой алгоритм с полиномиальным временем работы справляется на том же самом пороге.
Расскажу ещё немного подробнее.
В 2009 году я работал над своей первой статьёй вместе с Алексом Димакисом (@AlexGDimakis), который вскоре стал моим научным руководителем (не благодаря той статье):
Статья была одной из многих попыток предложить полиномиальное по времени решение для MIMO-детектирования.
Спросите, что такое MIMO-детектирование?
Передатчик отправляет вектор из N бит через беспроводной канал с N передающими и N приёмными антеннами. Канал смешивает все биты и добавляет шум. Приёмник, знающий матрицу канала, должен понять, какие именно биты были отправлены.
Оптимальный по блоковой ошибке приёмник, также известный как детектор максимального правдоподобия (ML), решает именно эту задачу, находя наиболее вероятный вектор, который мог быть отправлен при данном принимаемом сигнале. В этом случае ML-детектирование сводится к решению фундаментальной задачи дискретных наименьших квадратов:
К сожалению, как и со всеми хорошими задачами в жизни… ML-детектирование является NP-трудной задачей.
Но мы не пессимисты из TCS (теоретической информатики), и беспроводные каналы не являются наихудшим случаем — они случайны, и научное сообщество с начала 2000-х работало над следующим вопросом:
Когда восстановление переданных битов статистически возможно, можно ли сделать это за полиномиальное время?
Мы не добились большого прогресса по этому вопросу в той статье 2010 года, и несмотря на множество работ в этой области, проблема, насколько я понимаю, оставалась открытой с 2001 года… то есть ЧЕТВЕРТЬ ВЕКА, если говорить более драматично.
До прошлой недели. И окончательный ответ таков:
ДА! Всякий раз, когда совершенное детектирование статистически возможно, его можно выполнить за полиномиальное время.
MIMO решена; Точка.
Но кому это интересно? Мы вернёмся к этому через секунду.
Прикрепляю статью — я потратил более 5 дней на переписку с моделями, чтобы упростить доказательства и изложение (которое изначально было абсолютной катастрофой). Это заняло намного больше времени, чем первоначальное доказательство, которое GPT выдал примерно за 30 минут. Доказательство длинное, но относительно элементарное. Я проверил всё и, насколько позволили мои способности к проверке, оно корректно.
Теперь расскажу подробнее о самой задаче и её истории, а также о том, почему я считаю, что о ней стоит написать, даже несмотря на то, что область ушла вперёд от этого конкретного уголка теории MIMO-детектирования.
Постановка задачи
Итак, вы передаёте двоичный вектор x из {±1}^N и принимаете
y=SNRNHx+w{\bf y} = \sqrt{\frac{SNR}{N}}{\bf H}{\bf x}+{\bf w}
где H — матрица N×N, и H, и w имеют независимые одинаково распределённые компоненты N(0,1), все независимы. Приёмник знает H и статистику шума, но не знает w, и хочет восстановить x из y. Оптимальное по блоковой ошибке решение задачи восстановления равно
Кстати, эта оптимизация появляется и в других обличиях: MIMO-детектирование, многопользовательское детектирование в CDMA, дискретные наименьшие квадраты, поиск ближайшего вектора в решётке и т.д.
Когда SNR = ∞ (т.е. эффективный шум равен 0), задача становится тривиальной: матрица канала H обратима с вероятностью 1, поэтому вы обращаете её и получаете точный x как inv(H)*y. В другой крайности, когда SNR = 0, из шума невозможно ничего выделить, и ML-детектирование не работает.
Но где-то между 0 и бесконечностью ML-детектирование срабатывает, и срабатывает ровно при SNR = 2 log N. Это означает, что решение указанной выше оптимизационной задачи позволяет идеально восстановить все биты переданной N-битовой последовательности с вероятностью, стремящейся к 1, а ниже (с точностью до аддитивных членов loglogN) вероятность восстановления блока стремится к 0.
Итак, выше 2logN переданный сигнал является оптимумом задачи ML-оптимизации, но решение требует, как кажется, полного перебора всех возможных N-битовых последовательностей. Поэтому вопрос, который нас теперь интересует:
Может ли алгоритм с полиномиальным временем восстановить переданный x, когда ML добивается успеха?
**
Краткая история с толикой драмы
Вопрос о разрешимости задачи дискретных наименьших квадратов восходит как минимум к 1989 году, когда Верду доказал, что в общем случае она NP-трудна. Но NP-трудность — это утверждение о худшем случае, а наши задачи не таковы.
Хасиби и Викало в 2001 году были первыми, насколько я знаю, кто предположил, что существует надежда на полиномиальное решение для среднего случая. Алгоритм, который они анализировали, был популярным в то время методом — сферическим декодером (SD), восходящим к Финке и Посту в 1985 году. Сферический декодер представлял особый интерес по двум причинам: 1) это точный ML-алгоритм, т.е. он всегда выдаёт минимизатор, и 2) на практике он казался намного быстрее экспоненциального времени.
Надежда была на то, что можно доказать, что SD работает за полиномиальное время. Именно это Х. и В. сформулировали в своей статье: они вывели формулу ожидаемой сложности сферического декодера, усреднённую по каналу и шуму, и показали, что она выглядит полиномиальной. Если бы это было верно, вопрос был бы закрыт. Это казалось невероятным результатом.
Затем Ялден и Оттерстен в 2005 году показали, что асимптотическая интерпретация была не совсем корректной: при любом фиксированном SNR, сколь угодно большом, ожидаемая сложность сферического декодирования на самом деле экспоненциальна по размерности задачи.
Поскольку точный и быстрый метод не сработал, область потратила значительные усилия на поиск приближений к задаче ML-оптимизации. Полуопределённые релаксации с гарантиями аппроксимации и условия точности при высоком SNR, но без резкого порога. Локальный поиск с переворотом битов похоже, совпадал с ML в симуляциях, но без полных доказательств совпадения с порогом восстановления ML. Литература по AMP строго охарактеризовала побитовую ошибку при фиксированном SNR, когда восстановление блока невозможно. Статистическая физика дала полиномиальные методы, которые, как предсказывалось, повторяют точный ML на основе аргументов с репликами, но, насколько я понимаю, без доказательства. А в статье с Бабаком и Алексом 2010 года анализировался метод MCMC, где доказывалось, что после перемешивания стационарное распределение придаёт ненулевую массу правильному решению, но ничего не говорилось о времени перемешивания, что и является самой трудной частью.
За все эти годы, как мне кажется, ровно один полиномиальный метод имел строгие гарантии восстановления блока при любых масштабах SNR: box-релаксация 2020 года, которая, как было показано, восстанавливает блок, когда SNR растёт как 4 log N, и, как доказано, не ниже. Заметим, что довольно интересно, что вероятностные инструменты, необходимые для анализа такого метода, созрели в конце 2010-х, то есть в основном уже после того, как сообщество ушло в другие темы и рассеялось.
И с тех пор… активности было мало.
Короче говоря, разрыв между тем, чего достигает ML, и тем, чего доказанно может достичь любой полиномиальный метод, так и не был закрыт.
**
Что сделали GPT и Claude и как мы получили доказательство, которое я, Димитрис, могу проверить?
Вдохновлённый недавними невероятными успехами передовых моделей в сложных математических задачах, я решил вернуться к проблемам, которые преследовали меня в аспирантуре (я когда-то работал в теории информации и кодирования), и начать наводить на них Звезду Смерти. Именно так ощущается, когда задаёшь сложные математические вопросы, а GPT решает их в режиме zero-shot:
GIF
Но я знал, что есть небольшая проблема. Даже если я получу полный ответ на любой заданный вопрос, узким местом станет необходимость его проверить, если я захочу поделиться им с другими. Во-первых, потому что не хочу опозориться, если он окажется неверным, а во-вторых, потому что желание поделиться — это и есть главная причина, по которой мы задаём вопросы и занимаемся наукой.
Поэтому я решил выбрать, как мне казалось, один из самых амбициозных вопросов, который беспокоил меня в начале аспирантуры, при этом чётко формулируемый и всё ещё открытый. И спросил GPT-5.6 и Claude Fable 5, когда ML MIMO-детектирование можно решить за полиномиальное время.
Обе модели уверенно выдали доказательства для разных алгоритмов, утверждающих, что разрыва нет! Существует полиномиальный алгоритм, который успешно работает при SNR выше 2 log N, точно повторяя (с точностью до аддитивных членов loglog, но кому какое дело) порог восстановления ML.
Но была небольшая проблема 😊 Алгоритм GPT был вариантом AMP. А AMP я ненавижу, страстно, потому что я, хоть убей, не понимаю ни одного из его анализов. Поэтому я попросил GPT попробовать передоказать тот же результат, если возможно, для более простого алгоритма. И действительно, GPT выдал ещё один алгоритм, который я тоже счёл неочевидным и никогда раньше не видел, чтобы его использовали!
Fable, с другой стороны, предложил кое-что, что мне действительно понравилось:
знаковый LMMSE, а затем жадные перевороты битов. Алгоритм, который был предложен в прошлом и реально использовался на практике.
Но была и другая проблема! По словам GPT, доказательство Fable было в основном ошибочным.. но его можно было спасти. Поэтому я решил остановиться на алгоритме, предложенном Fable, и попросил GPT взять доказательство Fable и исправить его. И GPT это сделал!
Но была ещё одна проблема: новое доказательство было НЕЧИТАЕМЫМ: стена обозначений, переменные, указывающие на переменные, указывающие на отношения переменных, определяющих другие переменные, экзотический аппарат матричного анализа и теории вероятностей, вещи, близкие к Марченко–Пастуру, от которых у меня начинается крапивница, и прочие прекрасные вещи.
Примерно 4-5 дней я курсировал между двумя моделями, прося их дать мне максимально тупой набор шагов для каждого крупного компонента, необходимого для доказательства. Я явно сказал им, что можно ухудшить оценки и константы, ЛИШЬ БЫ сохранился порог 2 log N, и всё ради простоты.
Всё, чего я хотел, — это доказательство, которое старый динозавр с коротким объёмом внимания сможет переварить без слёз.
Я даже попросил GPT и Claude переслать сообщения, где я больше всего ныл, lol
Мой любимый:
Почему я настаивал на сверхпростых шагах? Потому что хотел проверить это сам, от начала до конца. И нет, я не хочу использовать Lean — он НЕ решает мою проблему. Формальная верификация просто переносит уровень абстракции в другое место!! Всё равно нужно проверять, что английский текст леммы корректно переведён на Lean, а я этого языка не понимаю.
Да, забудьте об этом. Я не люблю Lean, простите.
Но основы линейной алгебры и теории вероятностей я понимаю и доверяю себе в проверке подобных шагов. Поэтому именно на таком уровне я требую доказательство.
Затем потребовались дни и дни промптов, когда модели упрощали аргументы друг друга, а я продолжал жаловаться и отвергать всё, что не мог понять.
И в итоге сработало! Мы получили доказательство, которое я полностью понимаю и которое теперь проверил построчно.
На само доказательство ушло 30 минут, а на то, чтобы сделать его проверяемым для меня — около пяти дней. Соотношение безумное, но что есть, то есть. Итог: простой алгоритм работает всякий раз, когда работает максимальное правдоподобие, за полиномиальное время. В этой задаче нет вычислительно-статистического разрыва.
БУМ!
**
Какова основная идея доказательства?
Алгоритм почти до неприличия прост. Но почему он работает? LMMSE с последующим округлением приближает вас по расстоянию Хэмминга к переданному сигналу с исчезающе малой погрешностью, то есть на расстояние o(N) от истины.
Затем жадный переворот битов не может застрять, потому что выигрыш на каждом шаге (т.е. насколько улучшается стоимость) определяется гауссовскими величинами, и их равномерная концентрация показывает, что каждый вектор, не являющийся истинным, в пределах некоторого шара предлагает строго улучшающий переворот бита гарантированного размера. Это значит, что что бы вы ни делали, вы обязательно улучшите результат на величину, отделённую от нуля.
Однако улучшение стоимости на каждом жадном шаге не означает, что расстояние Хэмминга до истины уменьшается на каждом шаге. Оно может временно ухудшиться. Но не сильно, потому что стоимость растёт с увеличением расстояния Хэмминга от истины. Это значит, что любая достаточно удалённая точка стоит намного больше, чем стартовая, и путь, на котором стоимость только убывает, никогда туда не попадёт. Жадный поиск может блуждать внутри шара по расстоянию Хэмминга, но его сдерживает «стоимостной барьер», который удерживает путь внутри шара.
Итак, 1) каждый шаг улучшает стоимость на величину, отделённую от нуля, и 2) стартовая стоимость ненамного превышает оптимум. Поэтому жадный процесс должен в конце концов остановиться, а если разделить одну величину на другую, получим необходимое число шагов — NlogN.
Более того, жадный поиск не может закончиться нигде, кроме истинного решения: в любой другой точке внутри шара какой-то переворот бита всё ещё даёт улучшение, а алгоритму не разрешено останавливаться там. Единственное возможное место остановки — переданный вектор.
Вот наглядное изображение ключевого аргумента
Это важно?
Сообщество специалистов по беспроводной связи ушло дальше, и я тоже. Но это был по-настоящему важный вопрос. Могу предположить, что означал бы этот результат около 2010 года: награда за лучшую статью на ISIT или от CommSoc/IT Society и, возможно, собеседования в MIT, Беркли и Стэнфорде. С уверенностью скажу, что для аспиранта это был бы результат уровня Святого Грааля и главное событие моей недолгой карьеры в теории информации.
И всё же.. область в значительной степени ушла вперёд 😊
Есть масса подобных задач, которые когда-то были важны и над которыми целые сообщества бились десятилетиями. Затем они постепенно перестали быть важными по мере развития областей науки, и остались открытыми и одинокими — не потому, что были неразрешимыми, а потому что люди постепенно перестали о них заботиться.
Поэтому, когда говорят: «Задача, которой N лет, решена ИИ», я бы попытался объяснить, что это на самом деле значит.
Но в этом есть кое-что невероятно крутое: теперь вы можете вернуться к задачам, которые были вам дороги в молодости, и навести на них Звезду Смерти. Вопросы, которые держали оборону против всей мощи исследовательского сообщества, теперь тихо сидят без защиты в забытом углу вселенной литературы и ждут, когда по ним выстрелит Звезда Смерти; и это стоит 200$ в месяц.
Безумные времена..
В любом случае, я выложу текущий черновик на arXiv, но не уверен, что буду подавать его в журнал (даже не знаю, какой сейчас был бы подходящим). Не хочу никого зря напрягать. Но если вы прочитаете его и найдёте ошибку, я буду рад узнать о ней. 😊
И теперь мы знаем:
ML-детектирование в MIMO — легко, когда оно возможно!
Ура…
**
Дополнение
Полезно отметить кое-что о приведённом выше доказательстве: в нём не изобретено никакой новой математики.
Никаких новых неравенств, методов или математических объектов, которых не существовало в 2010 году. Доказательство длинное, но элементарное, так что его трудность не концептуальная, а связана с усилием, необходимым, чтобы собрать двадцать страниц стандартных шагов с нужной степенью детализации и в нужный момент, чтобы они идеально сошлись воедино.
Думаю, если развить эту мысль дальше, можно очертить класс задач, для решения которых не требуется новой математики, а только сборка известных идей, связанных длинными последовательностями, на которые ни у кого не хватило бы терпения потратить столько токенов или времени. Эти задачи быстро падут под натиском ИИ, потому что перебирать много вариантов, пока что-то не сработает, — это именно то, в чём ИИ невероятно силён. И, возможно, фраза «никто не пытался применять известное достаточно долго» описывает гораздо больше открытых задач, чем мы думаем.
Развивая эту тему, вот мысленный эксперимент: предположим, вы могли бы перенести GPT-5.6 или Fable в 2005 год, с теми же вычислительными затратами на RL, но с данными предобучения, которые существовали только на тот момент. Решили бы они эту задачу?
Не знаю, сложно провести контрфактический эксперимент, но хотя многие инструменты, вероятно, существовали и в 2005 году, «притяжение» к выбору того или иного метода, которое модель «чувствует», может сильно зависеть от популярности данного метода и нашего коллективного инстинкта, зафиксированного в частоте использования идеи в конкретном контексте. Модель, предобученная на данных до 2005 года, могла бы испытывать трудности не из-за нехватки вычислительных мощностей для RL, а из-за отсутствия в предобучении притяжения к правильному набору идей. Это означает, что такие модели — нечто гораздо более интересное, чем математические оракулы истины. Возможно, их стоит рассматривать как дистилляцию наших накопленных инстинктов, дополнительно отточенных с помощью RL.
Последняя мысль, и на этом я закончу:
Если бы я мог отправиться в прошлое и сказать своему тревожному «я» 2009 года: «Брат, расслабься, через 17 лет ты будешь участвовать в решении вопроса о разрешимости ML MIMO-детектирования», и больше ничего. Моё прошлое «я» точно сошло бы с ума и, пытаясь понять, как он к этому придёт, сделал бы единственный разумный на тот момент вывод: должно быть, я остался в теории информации на следующие пятнадцать лет, вероятно, корпел над MIMO-детектированием или, в лучшем случае, над целочисленной оптимизацией, и что где-то, каким-то образом, примерно к 2026 году задача дискретных наименьших квадратов наконец треснет под тяжестью моего огромного интеллекта.
Чёрт… какая бы априорная гордость мной овладела.
Если бы только маленький Димитрис знал, что расстояние Хэмминга между битами той вселенной и нашей нынешней — гигантское, и за это стоит благодарить прорывы другой вещи под названием ML…
