Крупнейшие открытия ушедшего года в области Computer Science

17.02.2023

В 2022 году учёные-компьютерщики узнали, как передавать совершенно секретные сведения, почему трансформеры хорошо справляются, кажется, с любыми задачами и как улучшить алгоритмы более чем десятилетней давности (с небольшой помощью искусственного интеллекта).

Введение

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

CS и квантовые вычисления во многом пересекаются с физикой. В одном из крупнейших журналов, посвящённых теоретической CS, в 2022 году исследователи опубликовали доказательство гипотезы NLTS, которая, среди прочего, утверждает, что призрачная связь между частицами, известная как квантовая запутанность, не так хрупка, как некогда представлялось физикам. Доказательство NLTS имеет последствия не только для нашего понимания физического мира, но и для бесчисленных криптографических возможностей, которые даёт запутывание.

Искусственный интеллект всегда флиртовал с биологией: эта область черпает вдохновение в мозге человека — возможно, самом совершенном компьютере. Хотя понимание работы мозга и создание искусственного интеллекта, похожего на интеллект человеческого мозг, долгое время казалось учёным-компьютерщикам и нейробиологам несбыточной мечтой, новый тип нейронных сетей, известный как трансформер (transformer), судя по всему, обрабатывает информацию аналогично мозгу.

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

Красные частицы с меняющимися спинами и некоторой запутанностью

Запутанные ответы

Когда дело доходит до квантово-механической запутанности, т. е. свойства, которое тесно связывает даже удалённые друг от друга частицы, физики и другие учёные оказываются в тупике. Все согласны с тем, что полностью запутанную систему невозможно полностью описать. Однако физики считали, что проще описать системы, которые лишь близки к полной запутанности. Учёные же не согласились с этим и заявили, что и такие системы столь же невычислимы; это убеждение легло в основу гипотезы об отсутствии низкоэнергетических тривиальных состояний (NLTS, no low-energy trivial state conjecture). В июне группа учёных опубликовала доказательство этой гипотезы. Физики были удивлены, ведь это доказательство означает, что запутанность необязательно такая хрупкая, а компьютерщики рады, что на шаг приблизились к доказательству фундаментальной теоремы, известной как теорема квантового вероятностно проверяемого доказательства (quantum probabilistically checkable proof theorem), которая требует истинности NLTS.

Эта новость появилась на фоне результатов работы 2021 года, которые показали возможность использования квантовой запутанности для достижения совершенной криптостойкости зашифрованных сообщений. А в октябре 2022 года исследователи успешно запутали три частицы, находящиеся на значительных расстояниях друг от друга, тем самым расширив возможности квантового шифрования.

![Иллюстрация, где показана оранжево-синяя сеть линий, которые фокусируются в прозрачную пирамиду, становятся белым светом и переходят в прозрачный глаз]

Трансформация понимания вещей искусственным интеллектом

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

Крах криптографии

Безопасность онлайн-связи основана на сложности различных математических задач: чем труднее решить задачу, тем больше усилий должен приложить хакер, чтобы взломать канал. И, поскольку современные протоколы шифрования для квантового компьютера стали бы простой работой, исследователи находят новые задачи, чтобы противостоять им. Но в июле всего за час вычислений на ноутбуке упал один из самых многообещающих лидов. «Вот облом», — сказал Кристофер Пейкерт, криптограф из Мичиганского университета.

Эта неудача подчёркивает сложность поиска подходящих вопросов. Исследователи показали, что создать надёжно защищённый код, который никогда не упадёт, можно, только если доказать существование односторонних функций — задач, которые легко решить, но после решения трудно размотать. Мы до сих пор не знаем, существуют ли они (это открытие помогло бы нам узнать, в какой криптографической вселенной мы живём), но два исследователя обнаружили, что этот вопрос эквивалентен другой задаче, которую называют Колмогоровской сложностью и которая включает анализ рядов чисел: односторонние функции и настоящая криптография возможны только в том случае, если определённая версия сложности по Колмогорову трудно поддаётся вычислениям.

Машины помогают обучать машины

В последние годы навыки искусственных нейросетей по распознанию паттернов искусственных нейросетей дали толчок к развитию искусственного интеллекта. Но, прежде чем сеть начнёт работу, исследователи должны её обучить, потенциально точно настроив миллиарды параметров в процессе, для которого потребуются месяцы работы и огромное количество данных. Либо же за них всё это может сделать машина. С новым видом гиперсети — сети, которая обрабатывает и выплёвывает другие сети, — они уже в ближайшее время смогут это сделать. Гиперсеть под названием GHN-2 анализирует любую заданную сеть и выдаёт набор значений параметров, которые, как показало исследование, в целом не менее эффективны, чем таковые в нейросетях, обученных традиционными методами. Даже когда наилучшие возможные параметры не достигались, предложения GHN-2 оставались отправной точкой, которая была ближе к идеалу, поскольку позволяла сократить время и данные, требуемые для полного обучения.

Кроме того, летом прошлого года в журнале Quanta был рассмотрен новый подход, призванный помочь обучению машин. Он известен как воплощённый ИИ (embodied AI) и обеспечивает обучение алгоритмов на основе реагирующих трёхмерых сред (responsive three-dimensional environments), а не статичных изображений или абстрактных данных. Будь то агенты, изучающие смоделированные миры, или роботы, изучающие мир реальный, эти системы обучаются совершенно иначе и во многих случаях лучше, чем традиционно обученные системы.

Улучшенные алгоритмы

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

В марте исследователи опубликовали ускоренный алгоритм решения задачи максимального потока, одной из старейших задач информатики. Комбинируя используемые ранее подходы по-новому, группа создала алгоритм определения максимально возможного потока материала через заданную сеть, который Дэниэл Шпильман из Йельского университета назвал абсурдно быстрым. «Я был склонен полагать, что … не существует столь хороших алгоритмов для этой задачи».

Марк Брейверман в оранжевой рубашке на аллее среди деревьев

Новые способы передачи информации

Марк Брейверман, теоретик из Принстонского университета, потратил более четверти жизни на разработку новой теории интерактивной связи. Его работа позволяет исследователям выразить такие термины, как «информация» и «знание», количественно. Это не только дало лучшее теоретическое понимание взаимодействий, но и создало новые методы, обеспечивающие более эффективную и точную связь. За это и другие достижения Международный математический союз в июле этого года наградил Брейвермана медалью IMU Abacus — одной из высших наград в теоретической CS.

А полезная теория и ещё больше практики с погружением в среду IT ждут вас на наших курсах: