BlackBox Challenge: Что внутри черного ящика?

в 10:39, , рубрики: artificial intelligence, big data, blackbox challenge, cython, deep learning, machine learning, reinforcement learning, искусственный интеллект, машинное обучение, нейронные сети, обучение с подкреплением, Спортивное программирование, метки:

Всем привет!

Сегодня речь пойдет о состязании, в области машинного обучения, BlackBox Challenge, а также о самом черном ящике, механизмах его работы, изменения состояний, начисления вознаграждений и конечно о том, что же там внутри.
Чуть ниже я опубликую решение, входящее, на момент публикации, в 5-ку лучших.
Уверен оно поможет другим участникам улучшить свои результаты, а возможно и отыскать новый подход.

BlackBox Challenge: Что внутри черного ящика? - 1

Что же такое Black Box Challenge?

BlackBox Challenge — это соревнование по машинному обучению и в частности обучению с подкреплением
(Reinforcement Learning).
Задача участников — научить бота набирать максимальное количество очков в недетерминированной игре с неизвестными правилами. На каждом шаге бот может узнать состояние игровой среды и выбрать одно из действий. Обучающий, тестовый и валидационный уровни принципиально не отличаются друг от друга, однородны по состояниям и игровой механике.

Что мы имеем?

Итак, нам даны тестовый и обучающий уровень, состоящих из 1,214,494 и 1,258,935 шагов соответственно. Как говорилось выше, на каждом шаге, агент может узнать вектор состояний, содержащий 36 элементов и выбрать одно из 4-х действий.
Если решение готово, участник загружает его на сервер организаторов, где результат проверяется на тестовой и валидационной выборке, на основе результата на последней и строится лидерборд.
Время тестирования на серверах ограниченно 1200 секундами, чего более чем достаточно даже для сложных моделей, при использовании cython.
Использование фреймворков, любого open-source кода не ограничивается, предустановлены sklearn, xgboost, pybrain, theano etc.
Победитель определится в начале июня, по результатам финального тестирования.
Размерность вектора состояний, действий и сами правила игры, при финальном тестировании, меняться не будут, что неоднократно подчеркивали кураторы челеджа.

Базовый агент. Почему линейная регрессия не спасет мир?

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

Как успехи у других участников?

Из 1200 участников превзойти результат базового агента удалось лишь 65.
Обычные подходы оказались не очень-то успешны, люди, привыкшие получать результат, нажимая на кнопки в нейропрограммах/фреймворках, по сути обучая один черный ящик, для «победы» над другим, не достигли заметных результатов.
Попытки применения Q/Deep Q Learning также оказались безуспешны.
Сложные рекуррентные архитектуры из-за раннего переобучения демонстрировали далеко не лучшие результаты.
Большая часть участников, которые немного превзошли базовый рекорд, сделали это лишь благодаря небольшим изменениям коэффициентов примера с линейной регрессией.

Какова структура уровня?

Все уровни в целом однотипны и по всей видимости состоят из некоторых подуровней.
Каждые ~140к итераций происходит обнуление 36-й переменной вне зависимости от действий агента, в тестовой и обучающей выборке таких подуровней 10.

Как изменяется состояние среды в зависимости от действий агента?

Как мы уже говорили, вектор состояний игровой среды состоит из 36 элементов.
Рассмотрим график корреляций, стоит заметить, при построении оного по четным/нечетным компонентам должно получится более наглядно:
BlackBox Challenge: Что внутри черного ящика? - 2

Первые 35 переменных всегда идут в одной и той же последовательности, согласно предопределенным данным уровня, и не зависят от действий агента.
36-я переменная представляет большой интерес и возможно приблизит нас к ответу на вопрос о том, что же внутри черного ящика.
Её состояние изменяется в промежутке [-1.1;1.1], в зависимости от действий.
3-е действие оставляет переменную без изменений.
2-е действие уменьшает значение на 0.1
1-е действие увеличивает значение на 0.1
0-е действие изменяет переменную на «случайную» величину в ту или иную сторону.
Чуть ниже мы рассмотрим влияние 36-ой переменной на вознаграждение.

Как изменяется вознаграждение?

Чем больше значение 36-ой переменной по модулю, тем больше вознаграждение/штраф за действие.
Стоит отметить, что в игровой среде предусмотрен штраф за бездействие, который начинает начисляться при многократном выполнении 3-го действия >~100 раз подряд.
Вознаграждение не зависит от номера текущего хода и напрямую не зависит от количества набранных очков, также, вероятно, существует комиссия за действие.
Награда начисляется не сразу, а с некоторой задержкой, иногда, после десятков выполненных действий, чаще всего однотипных.
Ниже приведен график счета, при выполнении, на всех итерациях, действий 1 и 2 соответственно:
BlackBox Challenge: Что внутри черного ящика? - 3

Что же внутри черного ящика?

Компенсируем комиссию и инвертируем второй график:
BlackBox Challenge: Что внутри черного ящика? - 4

Попробуем еще раз, с первыми 50к итераций тестовой выборки:
BlackBox Challenge: Что внутри черного ящика? - 5

Трудно сделать однозначные выводы, однако весьма заметно, что полученные графики напоминают изменение котировок некого торгового инструмента.
В таком случае 36-ая переменная означает общую позицию, баланс между открытыми сделками buy/sell, действие 3 равнозначно бездействию, а первое и второе действие это лонг и шорт соответственно.
Остается действие 0, можно предположить, что это открытие сделки в случайном направлении, однако, как показывает опыт, оно благоприятно сказывается на наборе очков.
Вероятно положительный эффект достигается за счет более быстрого сбрасывания/наращивания агентом позиции, при выполнении нулевого действия или же оно просто пересчитывает позицию согласно некому техническому индикатору.
В любом случае, роль 0-го действия пока не ясна.
Также стоит заметить, что кураторы соревнования не раз подчеркивали однородность уровней, гарантируя, что игра, которая скачивается в качестве примера — это та же игра, которая идёт в зачет, пусть с другими данными.
С реальными рыночными данными никаких гарантий быть не может, а следовательно существует несколько вариантов. Возможно это эмулятор, построенный на основе модели рынка с определенными законами или же используются коррелирующие валютные пары, акции из одной индустрии.
Однако все это лишь предположения, уверен, по окончанию соревнования, организаторы приоткроют тайну черного ящика :)

Готовое решение

Исходя из таблицы лидеров, многим участникам так и не удалось превзойти возможности линейного робота. Приведенная ниже модель, написана на cython/c и представляет собой быструю и простую реализацию многослойного персептрона с сигмоидальной функцией активации.
Исходный код обучения не привожу, однако замечу, что имел место довольно сложный алгоритм, включающий мутацию, обратное распространение и прюнинг потенциально некорректных изменений весов, все это для уменьшения эффекта переобучения, который, как заметили многие, в данной задаче крайне выражен.
Обратите внимание, в директорию levels необходимо поместить test_level.data и train_level.data из оригинального архива.
Кстати, линейная регрессия легко обобщается до однослойной нейросети, так что вы можете использовать уже имеющиеся коэффициенты (к примеру из базового агента).
Время итерации на обучающей выборке, на VM с Xeon E5-2673 в Microsoft Azure, около двух секунд.
Если желаете протестировать или разобраться в работе сети — добро пожаловать на GitHub:
CyMLP (исходный код сети), BlackBox Solver (код самого решения).

Заключение

В Black Box Challenge от участников требуется наблюдательность, находчивость и оригинальность.
Здесь нет готового решения или «модного чудо-фреймворка», который сделает вас лидером.
Однако, при достаточном упорстве и изобретательности, результат не заставит себя ждать.
На текущий момент ни один из участников не превзошел базовый агент на требуемые 1000 очков.
Надеюсь эта публикация поможет вам улучшить свои результаты, а возможно и отыскать новый подход.

Благодарности и ссылки

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

Благодарю Игоря Водопьянова за график корреляций, Константина Софиюка (cosionix) за графики счета, а также всех участников канала Telegram и форума за идеи.

Автор: GNC

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js