Not about AI, but definitely something interesting is happening.

Youtube video: https://www.youtube.com/watch?v=uOJCS1W1uzg

Quanta article: https://www.quantamagazine.org/physicists-create-a-wormhole-using-a-quantum-computer-20221130/

Nature article: https://www.nature.com/articles/s41586-022-05424-3

"One secret to success was Zlokapa, a waifish orchestra kid who joined Spiropulu’s research group as a Caltech undergrad. A gifted programmer, Zlokapa mapped the particle interactions of the SYK model onto the connections between neurons of a neural network, and trained the system to delete as many network connections as possible while preserving a key wormhole signature. The procedure reduced the number of four-way interactions from hundreds down to five."

[Google UL2R] Transcending Scaling Laws with 0.1% Extra Compute
Yi Tay, Jason Wei, Hyung Won Chung, Vinh Q. Tran, David R. So, Siamak Shakeri, Xavier Garcia, Huaixiu Steven Zheng, Jinfeng Rao, Aakanksha Chowdhery, Denny Zhou, Donald Metzler, Slav Petrov, Neil Houlsby, Quoc V. Le, Mostafa Dehghani
Статья: https://arxiv.org/abs/2210.11399
Пост в блоге: https://ai.googleblog.com/2022/11/better-language-models-without-massive.html

Продолжение темы про UL2 (https://news.1rj.ru/str/gonzo_ML/1113).

Идея простая, давайте продолжим обучение обычной языковой каузальной модели, но с UL2 objective. Это будет стоить 0.1-1% FLOPs от оригинальной модели, и не будет требовать новых датасетов. Новый метод назовём UL2R или UL2Restore.

Берём оригинальную модель PaLM (только декодер, обучается через PrefixLM, https://arxiv.org/abs/2204.02311), уже обученный checkpoint, и тот же самый датасет, на котором её обучали.

Берём стандартные 7 denoiser’ов из UL2. Дальше правда оказывается, что достаточно микса 50% PrefixLM (S-denoiser), 25% Long (extreme) span corruption (X-denoiser), 25% regular span corruption (R-denoiser).

Дообучаем оригинальную 540B PaLM на 20к шагов с батчем 32. Это примерно 1.3B доп.токенов и 0.16% доп.вычислений. Обучается с cosine learning rate decay schedule, где learning rate отжигается с 10E−4 до 10E−6 (низкий постоянный learning rate даёт аналогичный результат).

Эта новая модель называется U-PaLM 540B, на её дообучение уходит 5 дней на 512 TPUv4 чипах. Это примерно $200k в ценах on-demand.

Результаты интересные.

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

Во-вторых, U-PaLM даёт emergent abilities (https://news.1rj.ru/str/gonzo_ML/1031) на более мелких масштабах.

В работе много анализа по разным типам задач, но общее место в том, что заметный прогресс за небольшую цену есть практически везде.

Ещё из интересного то, что очень небольшое дообучение языковой модели PaLM в режиме UL2R с новыми objectives про denoising даёт модели возможности по in-filling’у, то есть открывает возможность решения нового класса задач, к которому оригинальная модель не была готова.

Также поведением модели становится можно управлять с помощью специальных токенов режима, использовавшихся в UL2: [NLU], [NLG] и [S2S]. Это влияет на выход модели.

В общем теперь у нас есть простой эффективный способ улучшения качества имеющихся моделей, которые с нуля заново уже так просто не обучишь. Интересно, конечно, как U-PaLM показал бы себя относительно PaLM целиком обученного с помощью UL2.

Интересно также, использовалось ли что-то подобное в последних моделях семейства GPT-3.5 (https://beta.openai.com/docs/model-index-for-researchers/models-referred-to-as-gpt-3-5), включая ChatGPT, и аналогов, а также секретной GPT-4, или их тоже можно улучшить и дальше.

В целом кейс с UL2R хорошо подсвечивает субоптимальность стандартных подходов к обучению языковых моделей.

Not a paper, but a very cool stuff!

Roman Vershynin, professor of mathematics at the University of California, Irvine, and the author of the well-known book "High dimensional probability. An introduction with applications in Data Science" has just published materials from his course on the same topic!

The book itself is freely available on the internet (https://www.math.uci.edu/~rvershyn/papers/HDP-book/HDP-book.pdf), yet I myself have two hard copies of it :)

Now the videos and lecture notes from the course that was run remotely at Kyiv National University this fall during the bombing are published: https://www.math.uci.edu/~rvershyn/teaching/hdp/hdp.html

GPT-3, InstructGPT, GPT-3.5, ChatGPT, GPT-4, …

Генеративный AI за этот год сильно удивил. Прогресс с изображениями колоссальный (мы писали про это тут и тут). За это время и Midjourney существенно прокачался, и StableDiffusion постоянно обновляется, ещё и Lensa появилась и добавила теме массовости и популярности. Мне лично особенно нравится движуха с генерением кадров из известных фильмов, которые могли бы быть сняты другим режиссёром или в другой культуре (ну вот типа Звёздных Войн Акиры Куросавы). С текстом, похоже, тоже прямо сейчас случается ещё один качественный переход.

Нынешний фаворит — ChatGPT, продолжатель ветки GPT-3 в её текущей версии GPT-3.5 с добавлением RL по аналогии с более ранним InstructGPT.

Генерит прям хорошо, и не только на английском. Весьма достойно и на русском, и не только на человеческом, а, например, на питоне. И более ранние версии уже могли выдавать годное качество (у нас самих есть пример генерации продуктового анонса, где один был написан человеком за немалые деньги и долгое объяснение, а другой сгенерён одной из не самых последних уже GPT-3, и у текста ИИ CTR был в 37 раз выше человеческого), но новая ChatGPT прям приятно удивила (отдельно также ждём когда откроют GPT-4). Недавно один человек с помощью ChatGPT и Midjourney за выходные детскую книжку написал сгенерил и опубликовал на Амазоне. Ещё из свежего интересного есть иерархическая генерация театральных постановок на примере Dramatron’а от DeepMind.

Что интересно, кроме создания контента свежая модель по сути может в некоторых случаях заменять поисковик. Понятны места, где оно ещё косячит.

Во-первых, конечно, модель может безбожно врать. С поисковиками тоже так было и есть, особенно когда индексируются некачественные сайты или мешают злонамеренные акторы. Для GPT контролем источников уже не обойдёшься, придётся, например, воротить отдельные модели, определяющие качество ответа или применять иные способы фактчекинга и постобработки. Для детектирования токсичности и подобных вещей уже есть готовые API, например, от Гугла и OpenAI, а для определения недостоверности, неправильности, и в более широком смысле качества ответа, видимо, будет что-то похожее на новом уровне.

Во-вторых, модель может просто чего-то не знать, либо потому что какая-то специальная область, откуда в обучение ничего не добавляли (или добавляли мало), либо потому что с момента обучения уже что-то поменялось (президентом стал другой, научное открытие только сделали и т.п.). Для этого класса проблем также есть хороший заход — это retrieval-based модели типа WebGPT, которая по факту пользуется текстовым браузером. За последний год было уже несколько крутых результатов, когда модель может чуть ли не поиск Гуглом делать и инкорпорировать его результаты в свой ответ, и следующую радикально лучшую версию GPT, пусть будет SearchGPT, я бы ожидал на этой технологии.

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

Кроме поиска и генерации текста есть также интересное движение в сторону совершения действий (actions). WebGPT уже в общем была моделью с действиями, но есть куда всё это дело расширять. Трансформер типа ACT-1 это вполне себе дальнейший возможный шаг. Будет не только искать в вебе, а и разные операции выполнять, в том же Экселе, например, а там и в апишки ходить (ChatGPT уже умеет генерировать код для дергания некоторых апишек).

Слияние Codex, ChatGPT и WebGPT не за горами, на StackOverflow скоро будете ходить уже не вы :) Сейчас там в моменте в обратную сторону проблема — ввели временный запрет на написание ответов через ChatGPT. Следят за чистотой датасета ;)

Это всё не какое-то далёкое будущее. Я удивлюсь, если этого не произойдет в следующем году. Более далёкое будущее — это отдельная интересная тема.

Дизрапшн идёт, стартапов можно ожидать много, разные полезные продукты прямо просятся, и VC явно темой интересуются. Пост Бессемера я уже приводил, вот ещё хороший пост от Секвойи, и a16z тоже пишут. Мы с Флинтом тоже недавно написали чуток.

Вливайтесь в ряды Фурье, короче!

[DeepMind AlphaTensor] Discovering faster matrix multiplication algorithms with reinforcement learning
Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J. R. Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, David Silver, Demis Hassabis & Pushmeet Kohli
Статья: https://www.nature.com/articles/s41586-022-05172-4
Пост: https://www.deepmind.com/blog/discovering-novel-algorithms-with-alphatensor
Код: https://github.com/deepmind/alphatensor (только найденные алгоритмы и сопутствующее)

После статьи уже прошло сколько-то времени, но она важная, надо разобрать.

В этот раз подход AlphaGo (точнее его вариант Sampled AlphaZero для пространств действий высокой размерности, https://proceedings.mlr.press/v139/hubert21a) применили к задаче нахождения эффективного алгоритма для перемножения матриц.

Перемножение матриц везде вокруг. Без него никуда в компьютерной графике, обработке сигналов, научных вычислениях. Почти любой векторизованный алгоритм использует какое-то перемножение матриц. Злые языки также утверждают, что весь современный ИИ — это перемножение матриц. Наверное, эти кучки атомов просто завидуют. Получается, ускорение алгоритмов для перемножения матриц ускоряет всё вокруг.

Классический ручной алгоритм перемножения матриц, как его учат в школе-институте, прямолинейный и неэффективный, его сложность O(n^3) операций умножения, а в типовых процессорах это более дорогая операция, чем сложение. Для матриц 2x2 это соответственно 8 умножений. В 1969-м году Штрассен показал, что этот алгоритм неоптимален и предложил алгоритм с 7 умножениями. С тех пор понеслось, и учёные пытаются подобраться к квадратичному алгоритму, текущая SoTA O(n^2.37286) (https://www.quantamagazine.org/mathematicians-inch-closer-to-matrix-multiplication-goal-20210323/). Перебрать все возможные алгоритмы нереально, пространство огромно, поэтому поиск нужно делать по-умному.

Интересна репрезентация проблемы. Задача перемножения матриц заданной размерности сводится к тензорам особого вида (matrix multiplication tensor или Strassen’s tensor), которые могут описывать любую билинейную операцию (то есть бинарную операцию, линейную по каждому из аргументов), каковым перемножение матриц и является.

Кстати, хорошая статья “Tensors in computations” (https://www.stat.uchicago.edu/~lekheng/work/acta.pdf) про тензоры есть в предпоследнем Acta Numerica (https://www.cambridge.org/core/journals/acta-numerica). Там вообще хорошие статьи регулярно, следите за ними. В том же номере 2021 года (https://www.cambridge.org/core/journals/acta-numerica/volume/6A0DA33B45D0E5A6BABD1EF331B5E4F0), кстати, есть и известная статья Михаила Белкина, да и много другого интересного.

Тензор, описывающий произведение любых матриц n×n имеет размерность n^2 × n^2 × n^2 и содержит {0, 1}. Этот тензор описывает какие элементы из входных матриц брать, и куда писать результат. Например, для операции c1 = a1*b1 + a2*b3, где ai, bi, ci — элементы квадратных матриц A, B и C, элементы которых пронумерованы от единицы до макс.индекса слева-направо и сверху-вниз, в единицу выставляются элементы тензора с индексами (a1, b1, c1) и (a2, b3, c1).

Когда есть такой тензор, то его можно декомпозировать в сумму R outer products векторов (тензоров ранга 1) u,v,w, и каждая декомпозиция будет очередным рецептом, как именно выполнить умножение матриц, а число термов в этой сумме, R, будет числом операций умножения в данном рецепте. Таким образом, задача поиска алгоритма перемножения матриц сводится к задаче поиска по декомпозициям соответствующего тензора.

Задача поиска формулируется как игра с одним игроком под названием TensorGame. Состояние игры описывается тензором, который изначально равен тензору матричного умножения, который мы хотим разложить. На каждом шаге игры игрок выбирает очередной триплет векторов u,v,w и вычитает из тензора состояния их внешнее произведение. Цель — достичь нулевого тензора за минимальное число шагов (операций умножения). Если это получилось, то последовательность шагов и определяет алгоритм с гарантированной корректностью получения результата. Если не получилось, то в игре есть ограничение на максимальное число шагов. За каждый новый шаг агент по имени AlphaTensor получает штраф -1, а за ненулевой тензор в конце ещё и дополнительный штраф. Целевая функция здесь может быть разной, можно оптимизировать количество операций, скорость под конкретное железо, энергопотребление, память, да что придумаете.

Вектора u,v,w ограничены набором коэффициентов  {−2, −1, 0, 1, 2}, это позволяет избавиться от проблем конечной точности чисел с плавающей точкой. Агент может работать в стандартной арифметике или модулярной, обучается сразу на обеих, это даёт положительный трансфер. Также агент обучается сразу на нескольких целевых тензорах, это тоже помогает.

Как и в AlphaGo, AlphaTensor использует нейросетку для того, чтобы направлять MCTS (Monte-Carlo Tree Search). Сеть принимает входное состояние (текущий тензор), и выдаёт policy и value. Полиси даёт распределение по возможным действиям (u,v,w), и поскольку множество потенциальных действий на каждом шаге огромно, действия из него сэмплятся, а не перечисляются (это собственно и есть Sampled AlphaZero, от него AlphaTensor немного отличается в месте получения value из распределения returns, здесь это не среднее, а так называемое risk-seeking value; и ещё в некоторых деталях). Value даёт оценку распределения cumulative reward от текущего состояния (собственно это distributional RL через quantile regression distributional loss), это моделирует убеждения агента относительно ранга декомпозиции. MCTS возвращает для текущего состояния улучшенное распределение вероятностей следующих шагов, оно используется для обновления весов policy-части сети через KL loss. Оконченные игры с высоким скором используются как фидбек для обучения сети. Кроме них также используются синтетические демонстрации.

Сеть это трансформер с общим стволом и отдельными головами для полиси и value.

На вход сети список тензоров и скаляров, описывающий текущее состояние игры. Текущий трёхмерный тензор состояния неизменного размера и дополняется нулями до максимального 25 × 25 × 25. Также подаются последние h действий (обычно h=7). В скалярах содержится текущий момент времени t. Трансформер оперирует тремя grids размером S×S, которые проецируются из оригинальных S×S×S тензоров, каждый grid представляет два из трёх измерений этого тензора. К ним подмешиваются скаляры через проекцию. Дальше применяется axial attention (https://arxiv.org/abs/1912.12180). Policy head тоже трансформер, value head — MLP.

Важные компоненты, улучшающие результат ванильного агента AlphaZero:

- Собственно трансформер с inductive biases, подходящими для тензорных входов, и генерализованный вариант axial attention.

- Синтетические примеры. Разложение тензора задача NP-сложная (https://arxiv.org/abs/0911.1393), но можно зайти с обратной стороны и легко нагенерить рандомных u,v,r и по ним сконструировать тензоры, это даст датасет пар <тензор, разложение>. Таких пар нагенерили 5M. Сеть дальше можно обучить на миксе supervised loss и RL loss.

- Изменение базиса, в котором тензор описывает операцию (https://www.youtube.com/watch?v=Kyawzy2cEV8), и для каждого тензора вдобавок к разложению через канонический базис генерится ещё порядка 100K эквивалентных разложений в других базисах. Это добавляет разнообразия, и агент может параллельно играть свои игры в разных базисах. К тому же достаточно найти разложение в одном из базисов, чтобы автоматом решить задачу для всех. Это заодно увеличивает покрытие в пространстве алгоритмов, поскольку при ограниченном наборе коэффициентов  {−2, −1, 0, 1, 2} разложение, найденное в одном базисе, не обязательно даст коэффициенты из этого же набора в каноническом базисе. Изменение базиса для трёхмерного тензора S×S×S происходит путём генерации трёх инвертируемых матриц A, B, C размера S×S. Матрицы генерятся с ограничениями A = B = C и унимодулярностью (detA∈{−1,+1}). Благодаря этому после конвертации к каноническому базису все элементы остаются целочисленными.

- Аугментация данных. Поскольку факторизация не зависит от порядка (спасибо коммутативности суммы), то можно поменять местами элементы и получить новую пару <тензор, разложение>. Здесь меняют местами рандомный элемент и последний.

Обучалось на 64 TPUv3 с батчем 2048 в течение 600K итераций. Каждый из 1600 акторов работал на отдельном TPUv4. Вся процедура требовала недели на схождение.

Собственно, какие результаты.

AlphaTensor обучалась на нахождение алгоритмов перемножения матриц n×m и m×p, где n, m, p ≤ 5.

Система переоткрыла лучшие известные алгоритмы для перемножения матриц, например, Штрассена и Ладермана (https://www.ams.org/journals/bull/1976-82-01/S0002-9904-1976-13988-2/S0002-9904-1976-13988-2.pdf). Для некоторых размеров матриц AlphaTensor нашла более эффективные алгоритмы.

AlphaTensor также показала, что пространство алгоритмов сильно богаче, чем думалось. Это может помочь в математических исследованиях.

Поскольку тензоры могут описывать любую билинейную операцию, AlphaTensor может быть применима и для других задач. В работе продемонстрировали это на примере умножения n×n кососимметричной матрицы (skew-symmetric matrix) на вектор длины n, где система нашла SoTA алгоритм.

Также AlphaTensor может находить практически эффективные на конкретном железе алгоритмы, ничего не зная заранее про это железо. Для этого в reward добавляется терм равный отрицательному времени выполнения алгоритма. В остальном ничего не меняется. Попробовали на V100 и TPUv2, факторизация трансформировалась в JAX код, который компилировался под целевое железо перед бенчмарком. Успешно сумели ускорить алгоритм и под GPU, и под TPU. Нашли алгоритм с той же теоретической сложностью, но более быстрый на практике. Из интересного, нашли алгоритм, в котором было больше операций сложения, чем в классическом, но зато эти операции лучше сливались (в смысле fuse) компилятором и по факту работали быстрее.

Такие дела. Мне кажется, что более быстрое умножение матриц — это не главная прелесть работы (людей этот заход зачелленджил, они поднапряглись и улучшили новую соту AlphaTensor ещё на одно умножение для матриц 5×5, https://arxiv.org/abs/2210.04045). Ускорение — это хорошо, но гораздо важнее, это лишнее подтверждение высокой универсальности алгоритма AlphaZero, и ещё один proof-of-concept того, что этот алгоритм способен создавать знание, которое не смогли создать люди. Это важный компонент в деле автоматизации и ускорения науки.

Ещё одна хорошая статья от Quanta Magazine про всю эту историю (правда, кажется, они там сам алгоритм не совсем верно описали, ну да ладно): https://www.quantamagazine.org/ai-reveals-new-possibilities-in-matrix-multiplication-20221123/.