«Московская проблема» получила решение

Молодые российские математики впервые продвинулись вперед в доказательстве гипотезы, сформулированной еще в 1997 году в работах академика Евгения Тыртышникова. Старшие научные сотрудники Института AIRI Михаил Паутов и Ричик Сенгупта доказали важный частный случай задачи, которая десятилетиями не поддавалась специалистам и до сих пор считается одним из самых сложных открытых вопросов в теории матриц. «Ъ-Наука» поговорила с учеными о том, почему эта гипотеза важна не только для математиков, об экспериментах с ИИ, который помог подступиться к задаче, и о красоте математики.

— Для начала: что такое гипотеза Тыртышникова?

Михаил Паутов: История началась в 1997 году. Евгений Тыртышников (советский и российский математик, профессор, академик РАН, заведующий кафедрой вычислительных технологий и моделирования ВМК МГУ.— «Ъ-Наука») с коллегами исследовал методы приближения матриц с помощью матриц малого ранга. Такие представления очень важны в вычислительной математике: они требуют меньше памяти, ускоряют вычисления и позволяют работать с большими данными.

В работе рассматривался так называемый скелетный метод аппроксимации. Это способ представлять огромные матрицы в компактном виде. Идея довольно наглядная. Мы выбираем некоторые строки и столбцы исходной матрицы, строим из них своего рода «скелет», а затем пытаемся восстановить всю матрицу по этой информации.

Ричик Сенгупта: Важно, что этот подход очень хорошо интерпретируется. Например, если матрица описывает оценки фильмов пользователями, то мы выбираем реальные строки и столбцы — конкретных пользователей и конкретные фильмы. Во многих других методах, например, в сингулярном разложении, используются абстрактные математические объекты, которые имеют геометрический смысл, но которые трудно связать с исходными данными. Здесь же все элементы имеют понятный смысл.

— А в чем заключается сама гипотеза?

М. П.: Когда вы строите приближение, возникает естественный вопрос: насколько оно отличается от исходной матрицы? Иными словами, какова ошибка аппроксимации?

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

Р. С.: Если перевести это на язык рекомендательных систем, про которые я уже говорил, то раньше казалось, что качество найденного «скелета» зависит и от количества пользователей, и от количества фильмов. Гипотеза утверждает, что количество фильмов вообще не играет роли. Это важно, потому что от качества такого скелета напрямую зависит ошибка приближения. Если хороший «скелет» гарантированно существует, то можно давать строгие гарантии качества вычислений.

— Если формулировка относительно простая, почему задачу не удается решить десятилетиями?

М. П.: Именно поэтому она и стала известной. Есть задачи, которые очень легко объяснить, но невероятно трудно доказать. Почти 30 лет численные эксперименты показывали, что гипотеза, скорее всего, верна. Для практически любой матрицы удавалось найти нужную подматрицу. Но доказательства не было. Все известные методы упирались в барьер. Они позволяли получить оценки, близкие к гипотезе, но не саму гипотезу. Получалось доказать утверждения, в которых качество найденной подматрицы зависело и от числа строк, и от числа столбцов. А гипотеза утверждает, что зависимость должна остаться только от числа строк. Очень много, кто еще пробовал подступиться к задаче, но статей написано меньше десяти.

Р. С.: Думаю, дело в том, что в математике редко публикуют статьи о том, что что-то не получилось. При этом были диссертации и исследования, связанные с поиском таких подматриц и алгоритмов их построения.

Первый по-настоящему серьезный результат появился совсем недавно. Профессор Юрий Нестеренко доказал гипотезу для одного конкретного размера матриц — 4 на 2. Мы вдохновились, решили тоже попробовать копать в эту сторону.

— Как началась ваша работа над задачей?

М. П.: Мне ее предложили еще в начале аспирантуры, задолго до защиты диссертации. Сразу предупредили, что задача очень сложная и над ней безуспешно работают много лет. Поэтому я решил начать с частного случая — матриц ранга два, то есть фактически с двумя столбцами. Через несколько месяцев удалось доказать гипотезу для одного класса таких матриц. После этого стало ясно, что весь случай ранга два распадается на две части: одна уже понятна, а другая остается открытой. В прошлом году мы с Ричиком начали работать вместе.

Р. С.: Мы постоянно придумывали новые подходы, проверяли идеи, находили ошибки. Часто бывало так: я присылаю очередное доказательство, а Михаил через некоторое время отвечает: «Не работает». Прошло больше года. В какой-то момент казалось, что мы зашли в тупик.

— Не было ощущения, что можно потратить несколько лет и не получить вообще никакого результата?

М. П.: Осознание, что попытки других исследователей решить эту задачу были в основном безуспешными, признаю, оказывает давление: «Что, если снова не получится?». В минуты сомнений я рассуждал просто: определенно должен быть какой-то трюк, который поможет решить задачу. Если искать долго и упорно, он, несомненно, найдется. Конечно, и удача в таком поиске совсем не помешает.

Р. С.: Такое чувство возникает почти всегда, и это случается очень часто. Хотя меня это и мотивирует, поскольку я чувствую, что столкнулся с очень красивой и нетривиальной проблемой.

— Когда вы впервые рассказали о своей работе, вы упомянули ИИ. В какой момент появились нейросети?

М. П.: Когда количество исписанной бумаги превысило размер комнаты. Шутка, конечно, но к правде близко. Мы использовали их скорее как очень продвинутый поиск по литературе. Важно понимать, что никакого решения они не предлагали. Они выдавали идеи, ссылки на теоремы, возможные направления. Все приходилось тщательно проверять. Причем большая часть утверждений оказывалась ошибочной, я в какой-то момент расстроился и решил, что с этим работать больше нельзя.

Р. С.: Мы, правда, будто зашли в тупик и решили, что, видимо, нужно временно перестать пытаться решить задачу и переключиться на что-то еще. В этот день я долго не мог уснуть. Уже глубокой ночью я собрал все наши наработки и выкладки и решил дать ИИ последний шанс. Закинул промпт в одну из публичных нейросетей. Модель вдруг начала рассказывать про пространство Минковского, метрический тензор и физику, которая вообще на первый взгляд не имела отношения к нашей задаче. Я уже сказал себе: «Ну, все понятно», но затем модель упомянула теорему Фробениуса—Перрона. Это такой классический результат из линейной алгебры, который тоже на первый взгляд не относится к нашей задаче. Я все-таки провел часть расчетов, добавил их к имеющимся выкладкам и отправил их Михаилу с комментарием: «Не знаю, правда ли это или у меня тоже галлюцинация, и пригодится ли нам в итоге пространство Минковского, но вроде получилось».

— Пригодилось, получается?

М. П.: В итоге пространство Минковского нам вообще не понадобилось, но вот идея использовать теорему Фробениуса—Перрона неожиданно сработала. Удалось получить противоречие с предположением, что гипотеза неверна. А значит, гипотеза в рассматриваемом случае верна.

Р. С.: На самом деле это был последний недостающий кусочек пазла. Почти все остальные идейные куски доказательства к тому моменту уже были готовы, хотя изначально мы не знали, какие конкретно пригодятся. Кстати, забавно, что эту теорему нейросети несколько раз предлагали еще давно, но все предложения сопровождались неправильным применением и казались вне контекста.

— Что именно вам удалось доказать?

Р. С.: До нас был доказан случай 4х2. Мы доказали случай Nх2 — любое число строк и два столбца. То есть это существенно более широкий класс матриц.

М. П.: Общая гипотеза по-прежнему остается открытой. Но, по словам автора задачи, это действительно нетривиальный результат. Мы, конечно же, написали Евгению Тыртышникову и рассказали о решении.

— Если объяснять неспециалисту, насколько велик шаг от случая 4х2 к случаю Nх2? Почему математики считают это существенным продвижением?

М. П.: Предполагается, что гипотеза верна для матриц всех размеров. Из доказательства ее для матриц какого-то конкретного размера может быть непонятно: вдруг это просто удачный случай? Вдруг гипотеза верна только для достаточно маленьких матриц?

— Расскажите поподробнее, какие вопросы вы отправляли моделям. Если кто-то захочет попробовать решить свою задачу, как ему следует формулировать промпты?

Р. С.: Формулировку задачи, какие-то промежуточные идеи и выкладки, применить какой-то метод из литературы, спрашивать, уверен ли ИИ. Попросить написать код и запустить какие-нибудь численные эксперименты. Нужно понимать, что, если задача нетривиальная, ИИ вряд ли правильно ее решит, и относиться к нему как к продвинутому поисковику или партнеру по мозговому штурму.

— А если мысленно убрать ИИ из этой истории, вы все равно пришли бы к доказательству?

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

М. П.: Может быть, каким-то другим путем. Но это определенно заняло бы больше времени.

— До этой работы и после нее вы по-разному смотрите на возможности нейросетей в фундаментальной математике? Где проходит граница между полезным инструментом и бесполезной генерацией идей?

Р. С.: ИИ на самом деле хорошо научился решать какие-то задачи по фундаментальной математике. Мне кажется, нужно сосредоточиться на задачах, которые ИИ решить не может.

М. П.: Я всегда относился со скепсисом к прогрессу нейросетей в решениях математических задач. До недавнего времени они были способны лишь воспроизводить части решений уже решенных задач, а сейчас уже превращаются в полезный инструмент для поиска предположительно рабочих идей. Сегодня нельзя отрицать, что часто они находят связи между, казалось бы, не связанными друг с другом фактами из разных областей математики. Такие связи легко могут оставаться незамеченными для целых коллективов на протяжении многих лет.

— Есть ли у результата практические последствия?

М. П.: Да. Ведь сама гипотеза возникла как часть анализа конкретного численного алгоритма. Если гипотеза все-таки верна, то можно получить существенно более сильные оценки ошибки этого алгоритма.

Р. С.: Возвращаясь к рекомендательным системам. Мы хотим быть уверены, что даже на сложных данных ошибка не начнет неожиданно расти. Наш результат показывает, что для соответствующего класса задач ошибка остается под контролем. Это означает, что подобные методы аппроксимации можно применять более уверенно — и не только в рекомендациях фильмов, но и при работе с другими большими массивами информации.

М. П.: За этой абстрактной математикой, точнее говоря, линейной алгеброй, скрываются вполне практические вопросы, с которыми сталкиваются современные технологии. Сегодня объемы данных растут беспрецедентными темпами, из каждого, как говорится, утюга слышно: нейросети, стриминги, большие данные, финансовая аналитика! Представляете, какой объем информации накопился вокруг? Полученные результаты уже показывают, что во многих задачах можно находить компактные и информативные представления данных эффективнее, чем считалось ранее. Уже сейчас это укрепляет теоретическую базу методов сжатия и аппроксимации, которые используются в самых разных областях.

Р. С.: Разработчики систем искусственного интеллекта получают дополнительные гарантии того, что большие модели можно упрощать без существенной потери качества. Если получится доказать общий случай гипотезы, то более эффективными могут стать и технологии сжатия нейронных сетей.

М. П.: В конце концов, новый результат в математике — это очень красиво.

— А откуда взялось название «Московская проблема»?

М. П.: Это отдельная история. После появления гипотезы ее авторы сами пытались понять, как ее доказать. В какой-то момент они обратились за советом к одному из крупнейших специалистов в этой области — американскому математику Гилберту Стренгу. Они отправили ему описание задачи и попросили свежий взгляд. Стренг ответил: «Кажется, я понимаю, что здесь происходит. Напишу вечером».

Через несколько дней пришло новое письмо. В нем было сказано примерно следующее: «Нет, знаете, я совершенно не понимаю, что здесь происходит. This is a very hard Moscow problem» (с англ. «Это очень сложная московская проблема»). Так иностранный ученый фактически и дал задаче ее неофициальное название — «Московская проблема».

Р. С.: Мы, кстати, уже опубликовали препринт, а потом получили рекомендацию к публикации в журнале «Доклады Академии наук». Надеемся, что новый результат вдохновит людей заниматься как открытыми проблемами в чистой математике, так и в прикладных алгоритмах анализа данных.

— Если бы сейчас к вам пришел студент и сказал: «Я хочу заниматься задачей, которую никто не может решить уже 30 лет», что бы вы ему ответили?

М. П.: Самый серьезный шаг такой студент уже сделал сам — он сделал выбор в пользу попытки внести заметный вклад в науку. Конечно, стоит обговорить, что такие задачи не решаются просто, что решение не обязательно получится найти. Но даже в таком случае можно получить множество промежуточных полезных результатов, просто повысить свою математическую грамотность. Я бы определенно поддержал такого студента.

Р. С.: Наука бывает разной. Не обязательно всегда решать открытые проблемы, можно придумывать свои задачи или теории, не менее интересные и полезные. Кроме того, многие, включая успешных ученых, часто предостерегают молодежь от решения открытых задач, поскольку это полный неопределенности путь и он не для всех. Однако мало что в науке может сравниться с ощущением после решения очень сложной проблемы. Поэтому надеюсь, что наш пример поможет студентам не бояться нерешенных проблем, в какой бы области они ни работали, вдохновит их решать все более сложные и нетривиальные задачи, которые их захватывают, в конечном итоге продвигая российскую науку вперед.

Елизавета Певная