Deepmind AlphaCode - конкурент OpenAI Codex, который работает примерно так:

Сначала языковую модель претрейнят на всём GitHub.

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

Сэмплирование программы гораздо хитрее:
- Генерируется куча (до 10^6) программ, фильтруются по образцам из условия
- Отдельная модель генерирует тестовые данные для задачи (корректность не важна), и по выходам на этих данных программы кластеризуют.
- Представители кластеров отправляются на тестирование.

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

Также для хайпа модель отправили на Codeforces и она там нарешала на медианный рейтинг.

Сила в простоте

Я думаю, что если предлагаемая система (алгоритм, что угодно) в разы "сложнее" бейзлайна, и она даёт небольшой прирост по метрикам, то такой работе не уготовано место в истории. Это может иметь смысл, когда вы хотите выжать любыми способами максимум здесь и сейчас, как это бывает в проде, но в рамках технологического прогресса это не так.

Что я имею ввиду под "сложностью"?
Прежде всего, это количество составных частей в основе системы и их используемость по отдельности.

Из используемости компоненты следует выработанная интуиция и понимание, как и когда данная компонента работает, что от неё ожидать в различных ситуациях. Также если компоненту используют, то, скорее всего, для неё есть отточенный код/инструменты. А от количества этих компонент зависит возможность дебага, анализа системы и её воспроизведения.

На мой взгляд, время сметает монстров, а системы из простых компонент, собранных правильным образом, совершают прорывы и сами по себе становятся новыми простыми компонентами. Так и работает прогресс.

Прекрасный положительный пример - это self-attention (на картинке).

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

CodeRL - Франкенштейн от Salesforces
Чего у человека не отнять, так это желания прикрутить RL ко всему, к чему прикручивается.

В данной работе генерация программы токен за токеном рассматривается как последовательность действий, а успех программы, получаемой в конце - это награда в конце эпизода. От -1 (compile error) до +1 (passed tests).

Для обучения используется навороченный RL-алгоритм (невозможно описать его тут), а сложность схемы применения вы можете наблюдать на картинке, о ней я как раз скажу пару слов.

Так как у нас есть модель "среды" (состояние среды это просто текущий текст программы), мы можем использовать поиск по состояниям, как в AlphaGo.
Что в урезанном виде и делает модуль program refining.

Модуль program repairing подаёт ошибку, которую выдаёт программа/компилятор, обратно в генеративную модель, чтобы она попробовала её починить. Я также пробовал делать, когда программировал с помощью ChatGPT, эта схема работает не так круто, как можно вообразить.

Результат: всё те же 25% решённых задачек уровня Intro в APPS у лучшей модели, хотя сама модель похудела, и программ нужно генерировать меньше. Если взять тот же бюджет на программы, то у Codex и AlphaCode получается немного хуже. На сложных задач прирост около процента.

Думаю, что пятикратное усложнение системы не стоит того профита, который она даёт.

@knowledge_accumulator

При контакте с RL человеческий мозг даёт сбой
(навеяно предыдущим постом)

В своё время этот же сбой затянул и меня самого. Но за эти долгие годы знакомства с RL я вроде бы осознал его феномен.

Ставьте 🤯 под этим постом, если вам интересен мета-взгляд на RL, почему люди сходят от него с ума, и почему они делают это совершенно напрасно.

Завтра я расскажу про последнюю статью на тему решения задачек языковыми моделями, а дальше, если будет поставлено хотя бы два 🤯 (1 из которых я поставлю сам), то напишу серию постов про RL - про область в целом и про прикольные статьи, с долей скептицизма к происходящему.

Это позволит мне с чистой совестью пользоваться RL-терминологией (за прошлый пост мне немного стыдно).

Parsel - новый подход к генерации алгоритмов.

Авторы предлагают разбить процедуру генерации программы по описанию на несколько шагов:

1) Просят GPT сгенерировать high-level описание пошагового решения задачи.

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

3) Далее эту Parsel-программу "компилируют" - просят Codex сгенерировать реализации функций, заданных в Parsel, автоматически разрешают зависимости, тестируют на отдельных тестах, содержащихся в программе, и так отметают большее количество плохих сэмплов из языковой модели.

4) В результате хорошие реализации отдельных функций склеивают в готовые программы.

К замерам есть некоторые вопросы, потому что сравнение с конкурентами не очень полное и не в равных условиях. Тем не менее, по одной из метрик выбивает до 25% сложных задач в APPS, что кратно лучше, чем у оригинальных Codex и Alphacode.

@knowledge_accumulator

Не хочу грузить вас больше в этот день, только сообщу, что я вас немного обманул, и завтра всё-таки будет ещё одна статья про код - я её как-то изначально упустил из виду.

Всех причитающихся с праздником и хорошего вечера! ❤️🌹

CodeT: Code Generation with Generated Tests

То, что языковую модель нужно использовать для генерации тестов, стало общей точкой в статьях. Подход к выбору программ в этой статье чуть более хитрый, чем в AlphaCode, и работает он лучше - авторы воспроизвели его. При этом вся система сильно проще, чем Parsel.

1) Генерируем программы и тесты (всё с помощью запросов к Codex).
2) Прогоняем все программы на всех тестах, разбиваем их на кластеры по тому, какие тесты были пройдены программой (до этого момента всё, как в AlphaCode)
3) AlphaCode ранжирует кластеры только по размеру, а CodeT по величине (размер кластера) * (кол-во пройденных тестов), дальше их представители и подаются, как решения.

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

Результат - +6% Intro-задач и +3.7% сложных задач из APPS даёт эта процедура поверх Codex. К сожалению, в сетапе, который был в Parsel у лучшей модели, алгоритм не прогоняли, но на одинаковых сетапах CodeT лучше.

Подводим итог по кодогенерации

1) Системы генерации кода неплохо умеют справляться с простыми запросами.
Это весьма полезно, когда вы работаете с малознакомым языком программирования, а также, когда вы хотите генерировать себе шаблонный скучный код.
Если вы поймёте, как правильно декомпозировать код так, чтобы его куски можно было отдать системе типа Copilot, то вы, может быть, станете продуктивнее.
На простом датасете HumanEval лучшая модель может генерировать с ~70% точностью правильную программу с 1 попытки.

2) Системы генерации кода ломаются при первой встрече со сложностью/логикой/математикой.
Несмотря на объём данных для обучения и последние нововведения, абсолютные результаты на датасетах с задачками всё ещё страшные - 34% на задачках уровня Intro при 1 попытке.
Тут важно сделать наблюдение - процент решения сильно возрастает, когда мы начинаем считать метрику при большом количестве попыток - 5, 10, 50. Это всё не особо удивительно, если вспомнить, что мы имеем дело всего лишь с дообученной языковой моделью, а не с системой поиска решения задачи.

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

Так что бояться рано - нейросети ничего сложного написать пока не способны.

Reinforcement Learning - самое главное.

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

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

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

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

Но что многие не замечают - прелесть постановки является её же проклятием. Про это будет в вечерном посте.

Reinforcement Learning - главная проблема

То, что в терминах RL можно описать всё, что угодно, показывает, как мало априорной информации нам известно в данной постановке задачи.
- Среда - это чёрный ящик, про неё может быть ничего не известно.
- Награды могут жить своей жизнью, или могут быть сколь угодно редкими.
- Среда может быть рандомной, а информация о состоянии может быть неполной.

На это RL отвечает специфичными методами, которые это берут в расчёт.
При этом в реальных задачах это очень часто не так.

Именно поэтому применений RL в реальности меньше, чем у простого DL - очень часто мы можем, используя информацию о задаче, свести её к частному случаю, в котором есть гораздо более эффективные методы.

Конечно, есть ситуации, когда мы не можем никак свести к более простой постановке, и в этом случае RL как крайняя мера может нам помочь.

В канале я разберу набор статей про применение RL, и аргументирую свою позицию из этого поста.

Playing Atari with Deep Reinforcement Learning [2013] - с чего начался хайп

Игры из набора Atari 2600 - это около 50 отлично вписывающихся в RL задач:
1) Каждый кадр мы получаем картинку из игры на входе
2) Мы можем нажать одну из 18 комбинаций кнопок в ответ
3) Каждый кадр среда нам отдаёт награду - изменение "очков" в игре.

Мысль о том, что играть в компьютерную игру система можно научиться сама с полного нуля, ускоряет сердцебиение и сводит с ума всех мечтающих о создании GLaDOS в реальной жизни.

В рамках научпопа могу дать такую интуицию принципа обучения:

Собирая траектории "<>-действие-состояние-награда-действие-состояние-награда-<>" мы можем пробрасывать информацию об отложенных наградах "назад во времени" с помощью хитрого способа обучения - таким образом можно научить систему совершать цепочку правильных действий, даже если положительная награда за них будет только в конце цепочки.

Метод в статье был использован достаточно базовый, но его хватило, чтобы обойти человека в ряде игр, требующих простой стратегии для победы - например, Pong или Breakout (первые 2 игры на картинке).

Обратная сторона игры в Atari

Посмотрим на кривую обучения, приведённую в статье, для игры Breakout - это та, где нужно отбивать красный "кубик" доской, которую вы перемещаете в нижней части экрана.

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

В режиме Supervised learning при размеченном датасете мы бы могли обучить такую нейросеть гораздо быстрее и используя гораздо меньше данных - всего для обучения в каждой игре было сыграно по 10 миллионов кадров. Но в рамках поставленной задачи предполагается, что такого датасета у нас нет, и нейросеть учится сама методом проб и ошибок, что и делает процесс обучения чудовищно жадным в плане данных.

Отмечу, что революции в data-efficiency с тех пор не произошло, и все следующие годы количество данных для обучения только росло. Но про те безумные числа мы поговорим в другой раз.

Конечно, это не приговор - всего лишь нужно научиться переносить знания между доменами и средами. А это уже совсем другая история.

@knowledge_accumulator

Проблема Montezuma's Revenge

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

Это называют проблемой exploration - нам нужно "исследовать" среду и побывать в как можно большем наборе состояний среды, и уже в них пытаться нажимать случайные кнопки 😄

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

В 2018 году был предложен абсурдно простой и при этом эффективный метод, который закрепился во многих последующих работах. Про такой эффект я уже говорил.

Завтра я про него расскажу, не переключайтесь!

@knowledge_accumulator

Как мы пытаемся сводить RL к Supervised Learning

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

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

Мы могли бы применить в данном случае RL, но благодаря пониманию задачи мы можем привязать награду к нужному действию с помощью lookahead - заглядыванию в будущее при расчёте награды каждого показа. Не 100% надёжно, но близко.

Если у каждого действия есть конкретная награда, то при некотором предположении мы можем отказаться от "долгосрочного" RL-планирования и решать задачу с помощью Supervised Learning - по векторам фичей пользователя и товара предсказывать награду, и потом по предсказанию ранжировать в проде.

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

@knowledge_accumulator

Exploration by Random Network Distillation [2018]

Как нам решить проблему исследования среды и награждать агента за посещение новых состояний?

1) Берёте две случайные свёрточные сети. Одна - учитель, другая - ученик.
2) На встречающихся данных тренируете ученика предсказывать то же, что и учитель. Учителя не трогаем.
3) Если наша ошибка высокая, значит мы подали более новое состояние, если низкая, то более баянистое.
4) Добавляем MSE предсказания ученика с весом к обычной награде из среды.

Удивительно на первый взгляд, но результат прорывной - даже без настоящей награды нейросеть может научиться бродить и исследовать "мир" в игре с врагами и препятствиями.

На картинке можно посмотреть иллюстрацию того, как оно работает в реальности, с пояснениями, наслаждайтесь :)

@knowledge_accumulator

Agent57 [2020] - Atari повержен

Нам важно не столько то, как мы обходим человека в среднем по всем играм, а то, как мы работаем в худшем случае - именно здесь и добивается прорыва Agent57, который обходит человека во всех 57 играх Atari.

Данный алгоритм - это модификация Never Give Up (NGU), со следующими изменениями:

1) Мы теперь учимся предсказывать отдельными нейросетями 2 вида награды - настоящую и исследовательскую (из NGU). А смешивать их уже будем во время применения, обозначим вес NGU-награды как beta.

2) Используется многорукий бандит, который для каждого воркера, собирающего данные, сэмплирует значения beta и горизонт планирования (gamma). Таргетом для выбора этих значений является производительность в игре - набранная суммарная награда.

У каждого воркера при этом есть своя неизменная "рандомизация" (epsilon) - вероятность, с которой будет выбрано случайное действие во время применения.
Такое кол-во степеней свободы позволяет системе адаптивно выбирать такой набор параметров, который помогает лучше всего обучаться в данный момент.

80 миллиардов кадров - и готово.

@knowledge_accumulator

General Problem Solver - наконец-то AI способен решать задачи в произвольном домене.

С новыми возможностями искусственного интеллекта нас ждёт всеобщая автоматизация и потеря рабочих мест - утверждают известные экономисты. Во второй раз в истории термин "технологическая безработица" резко набирает популярность - на этот раз мы уже видим для этого реальную причину.

Как пользоваться алгоритмом? Нужно всего лишь:

1) Задать пространство состояний
2) Задать возможные переходы между ними
3) Задать начальное и целевое состояние
4) Запустить и через какое-то время программа найдёт решение.

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

Оставайтесь с нами, ибо в ближайшее время я расскажу про то, как обстоят дела с интеллектом у машин спустя >60 лет после появления брут-форс-ИИ. Вы удивитесь, насколько всё недалеко ушло.

@knowledge_accumulator