Как мы пытаемся сводить 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

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

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

Всем хорошей пятницы! ❤️

On the Measure of Intelligence [2019]

Что такое интеллект? Этот вопрос становится всё более важным, так как человечество начинает создавать системы, демонстрирующие свойства, которыми до сих пор обладали только люди.

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

На мой взгляд, отличную попытку определить интеллект делает автор данной работы (F. Chollet, создатель Keras):
The intelligence of a system is a measure of its skill-acquisition efficiency over a scope of tasks, with respect to priors, experience, and generalization difficulty.

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

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

О предлагаемом способе измерять интеллект поговорим в следующем посте.

@knowledge_accumulator

Abstraction and Reasoning Challenge [2019] - простейший тест на интеллект

Способна ли система понимать простые зависимости по нескольким примерам? Именно это проверяет данный бенчмарк.

Говоря формальнее, тестируемый субъект должен посмотреть на несколько (1-5) пар образцов "вход-выход", понять, в чём закономерность, и научиться генерировать правильный выход по тестовому входу.

"Задачки" являются очень простыми для любого человека, и он решит около 90% из датасета, понимая решение почти всегда за несколько секунд.

Одна из таких задачек есть на картинке - что нужно сделать с картинкой слева, чтобы она стала картинкой справа? Вы понимаете, как будет выглядеть выход, если, например, подвигать зелёные прямоугольники, или заменить цвета на другие?

На основе этого бенчмарка было организовано весьма необычное соревнование на Kaggle, где я с командой даже взял золото 😄

А в следующем посте я расскажу его итоги и решение, которое заняло первое место!

@knowledge_accumulator

Самый умный ИИ в Abstraction and Reasoning Challenge

1) Определим 142 операции вида *картинка -> картинка*.
Это преобразования картинки, такие как "соедини точки одинакового цвета", "отрази картинку", "отфильтруй цвет" и т.д. Список операций был составлен, смотря на тренировочные задачки из соревнования.

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

3) Применяем найденные верные программы к тестовому входу.

4) Всё это пишем на плюсах очень аккуратно и эффективно, чтобы влезть по ограничениям.

5) Решаем 20% задачек и получаем первое место!

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

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

Ну как вам, далеко мы продвинулись за 60 лет?

@knowledge_accumulator

Что можно вынести из Abstraction and Reasoning Challenge

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

При этом определить такой набор "подпрограмм", склеивая которые, можно сгенерировать решение, оказалось слишком сложно:
1) Если они будут слишком простые, мы не сможем сгенерировать достаточно длинные программы
2) Если они будут слишком сложные, мы не покроем большое количество задач
3) Если их будет слишком много, мы сможем генерировать только очень короткие программы.

Так что, поиск (перебор) это тупик в развитии машинного интеллекта?

Я считаю, что нет. Тупиком является только поиск по всем вариантам. Но если нам удалось бы каким-то образом направлять поиск так, чтобы перебирать как можно меньше программ в поиске решения, то наша система научилась бы решать тест за адекватное время. И именно направлять поиск человечество пока ещё только учится делать.

Когда это получается - результат получается потрясающий. О примерах такого мы и поговорим в следующих постах.

@knowledge_accumulator

AlphaZero [2018] - история о плодотворной дружбе поиска и глубокого обучения

Обобщая, есть 2 поколения подходов в настольных играх:

1) Поиск по всем вариантам с оптимизациями
Шахматные алгоритмы, начиная с появления компьютеров, как минимум до Deep Blue [1997], работали на основе таких подходов. В глубине души они по эффективности похожи на полный перебор, но засчёт хитростей (вроде дебютной книги и эвристических оценок позиций в листьях дерева поиска) алгоритмам удаётся как-то работать.

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

Слабые точки AlphaZero понятны - требует много данных, обучается отдельно под одну игру. Но все революции за раз не совершить!

@knowledge_accumulator

MuZero [2020] - AlphaZero выходит из плена настольных игр

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

Тем не менее, в рамках MuZero пытаются применить подход к выбору действий с помощью планирования, как в AlphaZero, в ситуации, когда доступа к модели среды нет.

Что делают с проблемой сложности среды? Оказывается, можно просто забить на состояния, и при обучении своей модели динамики среды пытаться предсказывать только будущие награды и действия нашей стратегии. Ведь чтобы их предсказывать, нужно извлечь всё самое полезное из динамики и не более. Удивительно, но это работает! Более того, эта система может играть в Го на уровне AlphaZero, у которой доступ к модели есть.

Я думаю, что отказ от попытки предсказывать будущее состояние это верно, потому что убирает ненужную сложность. От этого отказались в RND, NGU, в MuZero и не только.
Глобально говоря, от этого имеет смысл отказываться всегда, когда генерация не является самоцелью. И я думаю, что это рано или поздно будут делать во всех доменах, даже в текстах.

@knowledge_accumulator

AlphaStar [2019] - мы упёрлись в лимит self-play learning?

С одной стороны, перед нами романтичная история о том, как Oriol Vinyals, будучи в юности крутым Starcraft-игроком, стал ML-исследователем и через полтора десятка лет изобрёл первую Grandmaster-level-систему для Starcraft. В этом подкасте у Lex Fridman он рассказывает много интересного об этом проекте, советую интересующимся.

С другой стороны, при переходе на такой уровень сложности среды мы начинаем видеть пределы такого метода обучения, который используется здесь (он похож на AlphaZero):

1) Без использования человеческих знаний и данных это не работает.
В отличие от Go, в Starcraft вы не можете обучить сильный алгоритм, плавно меняя вашу стратегию, начиная с рандомной. В Go вы можете начать из рандома, потом играть лучше рандома, потом ещё лучше и так далее. В Starcraft вы сразу же натыкаетесь на локальный максимум, в котором вы берёте всех своих стартовых юнитов и идёте бить морду противнику, а не строить базу.

2) Количество данных, которое тут требуется, безумно. Увеличение размерности печально влияет на способность алгоритмов обучаться. Тут мы и видим проблему низкого интеллекта таких систем - они не могут использовать данные так же эффективно, как это делает человек.

В общем, применение прикольное, но технологии у нас пока ещё совсем слабенькие.

@knowledge_accumulator

Почему интуиция это ключ к интеллекту?

Когда мы проводим оптимизацию в большом пространстве для какой-то задачи, будь то Го или шахматы, Abstraction and Reasoning Challenge, или пытаемся придумать решение задачи по математике, ключом к успеху, как я уже говорил, является направленность поиска решения.

Есть 2 способа эту направленность получить:

1) Оракул
Если у нас есть фидбек от задачи, которую мы пытаемся решать, мы можем плавно двигаться нашим решением в сторону правильного, ориентируясь на то, насколько фидбек улучшается. Этот вариант имеет опасность - он может привести вас в локальный максимум, как это происходит в Starcraft, где в качестве оракула выступает то, выигрываете ли прошлые итерации себя. Но если оракул таков, что не допускает плохих локальных максимумов, он вам поможет. Эти случаи достаточно редки!

2) Интуиция
Я только недавно отрефлексировал её ключевую важность. Интуиция позволяет AlphaZero перебирать правильные ходы в Go. Интуиция позволяет математикам находить длинные доказательства теорем, хотя задача поиска доказательства является, в каком-то смысле, NP-задачей (экспоненциальное время на поиск решения, и маленькое время на проверку решения). Нерешённая проблема в сфере ИИ, то, что позволяет человеку обучаться так быстро - это универсальная интуиция, не привязанная к домену, которая позволяет посмотреть на картинку из Abstraction & Reasoning Challenge и мгновенно увидеть паттерн из жизни.

Никакие алгоритмы (пока что) на это не способны, и это является очевидным препятствием к тому, чтобы мы получили "Human-level intelligence".

@knowledge_accumulator

AutoML-Zero [2020] - когда оракул помогает поиску.

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

Применяем эволюционный поиск программ:
1) Задаём базовую структуру программы: нам нужно обучить 3 куска кода - для инициализации, для шага обучения и применения. То, как они используется, заранее задано, там простой train-loop. То есть одна программа это реализация трёх функций.
2) Определяем набор операций, которые можно использовать - берём базовые математические операции над скалярами, матрицами и векторами. И добавляем возможность самому инициализировать новые такие объекты.
3) Поддерживаем "популяцию" из N программ
4) В процессе оптимизации берём программы и применяем к ним мутации (случайно добавляем/удаляем/изменяем команду или другие случайные изменения)
5) Оцениваем новые программы, прогоняя процесс обучения, оставляем удачные варианты в популяции.
6) Прогоняем триллион программ в рамках оптимизации и готово!

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

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

Но зато всё это крайне весело.

@knowledge_accumulator

AlphaTensor [2022] - пример сверхчеловеческой интуиции в математике

Подход "поиск + нейросетевая интуиция" позволил AlphaZero планировать в играх с помощью с обученной на огромном разнообразном датасете аппроксиматором функции полезности, позволившим радикально сократить пространство перебора.

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

Говоря общими словами (глубокий часовой обзор есть тут):
1) Наша задача - разработать алгоритм, который можно применить к 2 матрицам, чтобы получить в результате их произведение.
2) Мы работаем с пространством алгоритмов, которые задаются последовательностью векторов-параметров. Эти векторы-параметры говорят нам (хитро), что на что умножать и что с чем складывать.
3) В терминах RL действиями являются эти векторы, наградой является то, насколько близкий результат будет давать алгоритм (со штрафом за кол-во действий), а состоянием среды является размерность матриц и прошлые действия.

К этому всему мы применяем в точности AlphaZero - нужно только реализовать "RL-среду" по правилам выше. В результате обучения алгоритм находит более быстрые способы перемножать матрицы, чем знало человечество!

Я в восторге от результатов данной работы, потому что система демонстрирует сверхчеловеческое понимание своей задачи, а я люблю такое. Она способна смотреть на данные той размерности, которые мы не способны воспринимать. Результаты на картинке говорят, что чем больше размерность, тем больше отрыв между ней и нами. Такие вот дела!

@knowledge_accumulator

Как пытаются подходить к автоматическому доказательству теорем с помощью ИИ?

К сожалению, у меня не получилось в небольшом посте одновременно объяснить задачу и подход, поэтому сегодня будет только про задачу. Итак, поехали.

Существует Metamath, где формализованы доказательства ~38к утверждений в математике, опираясь друг на друга, и в конечном счёте на базовые аксиомы.

Все доказательства теорем в Metamath базируются на подстановке - это когда мы применяем аксиому или уже доказанную ранее теорему к имеющимся "объектам", чтобы сгенерировать новое промежуточное утверждение. И так, пока не дойдём до теоремы. Этот подход называется forward manner.

Нас же интересует backward manner - это когда у нас есть доказываемое утверждение, и мы применяем к нему тактику, то есть предполагаем, какие промежуточные утверждения, при применении какой-нибудь аксиомы или теоремы, доказали бы желаемое.
Пример: чтобы доказать, что A=C, мы должны доказать, что A=B и B=C, и потом применить транзитивность. Теперь пытаемся доказать, что A=B и B=C.

Таким образом, в backward manner процесс доказательства - это построение дерева.
У каждого утверждения есть дети-тактики - попытки по-разному декомпозировать его на более базовые. И у каждой тактики есть дети-утверждения, все из которых мы должны доказать. Если какая-то вершина оказывается аксиомой или уже доказанным утверждением, то она автоматически доказана. Соответственно, шаг поиска это добавление тактики-ребёнка вместе с его детьми-утверждениями к уже существующей вершине. Это всё похоже на настольную игру. См. картинку.

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

А в следующих постах я расскажу о том, как поиск доказательств теорем ускоряют с помощью нейросетей, насколько плохо пока получается, и подумаем над фундаментальными причинами.

@knowledge_accumulator

GPT-f [2020] - LLM пытается доказывать теоремы.

Обязательно посмотрите предыдущий пост, если не видели, там объясняется задача.

Претрейн: помимо кучи текстов из интернета, модель учат на смеси GitHub, arXiv Math, и Math StackExchange.

Файнтюн: На основе базы доказательств Metamath строится датасет для файнтюна, состоящий из последовательностей вида <цель # шаг доказательства>, где нужно предсказать шаг доказательства по цели. Иначе говоря, учимся генерировать тактику доказательства заданного на вход утверждения.

Как работает процесс: мы храним в очереди с приоритетом все вершины дерева доказательства, которые мы ещё не пытались доказывать. Вначале в дереве только корень.
Выбираем вершину из очереди, пытаемся доказать, генерируя 32 тактики доказательства. Скорим их по сумме log-prob-ов всех токенов, и прибавляем скор родителя - это и будут приоритеты, с которыми мы их кладём в очередь.
На попытку доказательства выделяем до 128 таких шагов, и 4 попытки всего процесса, начиная с чистого листа.

После инференса модели на тренировочном датасете задач:
1) Учим value-функцию вида цель -> [0; 1] - предсказывает то, докажет ли модель данное утверждение.
2) Дообучаем генератор тактик на успешных тактиках

Весь процесс применения на трейнсете повторяем заново, теперь уже скоря вершины value-функцией. И потом повторяем 2 пункта выше. Так можно делать сколько угодно раз. То есть претрейн -> файнтюн -> инференс -> файнтюн на инференсе -> инференс №2 -> ...

Результат - 56% успешных док-в на тесте вместо 21% у предыдущего SOTA, и в ходе работы было сгенерировано 23 более коротких доказательств для базы Metamath, которые туда внедрили.

Это открыло ярмарку статей на эту тему, о которых мы ещё поговорим.

@knowledge_accumulator