После моей недавней статьи о применении обучения с подкреплением к реальным жизненным проблемам я решил продемонстрировать это на небольшом примере. Цель состоит в том, чтобы создать алгоритм, который может найти подходящий выбор продуктов питания в рамках бюджета и моих личных предпочтений.
Я также разместил описание, данные и ядро кода в Kaggle, и это можно найти здесь.
Пожалуйста, дайте мне знать, если у вас есть какие-либо вопросы или предложения.
Цель
Когда вы покупаете еду, в супермаркетах есть много разных продуктов для одного и того же ингредиента. Некоторые дешевле, другие более высокого качества. Я хотел бы создать модель, которая для требуемых ингредиентов может выбрать оптимальные продукты, необходимые для приготовления еды, которая одновременно:
- В рамках моего бюджета
- Отвечает моим личным предпочтениям
Для этого я сначала построю очень простую модель, которая может рекомендовать продукты, которые не соответствуют моему бюджету, прежде чем представлять свои предпочтения.
Причина, по которой мы используем модель, заключается в том, что мы могли теоретически масштабировать проблему, чтобы рассматривать все больше и больше ингредиентов и продуктов, которые могли бы вызвать проблему, которая в то время была бы вне возможности каких-либо мысленных расчетов.
Метод
Для этого я построю простую модель обучения с подкреплением и воспользуюсь методом Монте-Карло, чтобы найти оптимальную комбинацию продуктов.
Во-первых, давайте формально определим части нашей модели как Марковский процесс принятия решений:
- У нас есть ограниченное количество ингредиентов, необходимых для приготовления любой еды, и они считаются нашими состояниями
- Для каждого ингредиента существует конечное количество возможных продуктов, поэтому они являются действиями каждого состояния.
- Наши предпочтения превращаются в Индивидуальные награды для выбора каждого продукта, мы рассмотрим это более подробно позже.
Обучение методом Монте-Карло сочетает в себе качество каждого шага к достижению конечной цели и требует, чтобы для оценки качества любого шага мы должны ждать и видеть результат всей комбинации. Этот процесс повторяется снова и снова в эпизодах с множеством разных продуктов, пока не будет найден выбор, который, как представляется, неоднократно приводит к положительному результату. Это процесс обучения с подкреплением, в котором наша среда моделируется на основе полученных нами знаний о затратах и предпочтениях.
Монте-Карло часто избегают из-за того, что требуется время, чтобы пройти весь процесс, прежде чем вы сможете учиться. Однако в нашей задаче это требуется, поскольку наша последняя проверка при установлении того, является ли комбинация выбранных продуктов хорошей или плохой, заключается в суммировании реальной стоимости выбранных продуктов и проверке того, находится ли она ниже или выше нашего бюджета. Кроме того, по крайней мере, на этом этапе мы не будем рассматривать более нескольких ингредиентов, поэтому время, потраченное на это, не имеет большого значения.
Образец данных
Для этой демонстрации я создал несколько образцов данных для еды, состоящей из 4 ингредиентов и 9 продуктов, как показано на диаграмме ниже.
Нам нужно выбрать один продукт для каждого ингредиента в еде.
Это означает, что у нас есть 2 x 2 x 2 x 3 = 24 возможных выбора продуктов для 4 ингредиентов.
Я также включил реальную стоимость для каждого продукта и V_0.
V_0 - это просто начальное качество каждого продукта для удовлетворения наших требований, и мы устанавливаем его на 0 для каждого.
Сначала мы импортируем необходимые пакеты и данные.
Применение модели в теории
На данный момент я не буду вводить какие-либо индивидуальные награды за продукты. Вместо этого я просто сосредоточусь на том, не соответствует ли комбинация выбранных продуктов нашему бюджету. Этот результат определяется как Терминальное вознаграждение за нашу проблему.
Например, предположим, что у нас есть бюджет в 30 фунтов стерлингов, тогда выбор:
a1→b1→c1→d1
Тогда реальная стоимость такого выбора составляет:
£10+£8+£3+£8 = £29 < £30
И поэтому наша конечная награда:
R_T=+1
В то время как,
a2→b2→c2→d1
Тогда реальная стоимость такого выбора составляет:
£6+£11+£7+£8 = £32 > £30
И поэтому наша конечная награда:
R_T=−1
На данный момент мы просто сообщаем нашей модели, хороший или плохой выбор, и наблюдаем, как это повлияет на результаты.
Модельное обучение
Так как же на самом деле учится наша модель? Короче говоря, мы заставляем нашу модель опробовать множество комбинаций продуктов и в конце каждой сказать ей, был ли ее выбор хорошим или плохим. Со временем он поймет, что одни продукты обычно приводят к хорошему результату, а другие - нет.
В конечном итоге мы создаем ценности того, насколько хорош каждый продукт, обозначаемый V (a). Мы уже ввели начальное значение V (a) для каждого продукта, но как перейти от этих начальных значений к фактической возможности принять решение?
Для этого нам понадобится правило обновления. Это сообщает модели, после того как каждый раз она представляла свой выбор продуктов, и мы сообщали ей, хороший или плохой выбор, как добавить это к нашим начальным значениям.
Наше правило обновления выглядит следующим образом:
Сначала это может показаться необычным, но на словах мы просто обновляем значение любого действия V (a) на величину, которая либо немного больше, если результат был хорошим, либо немного меньше, если результат был плохим.
G - это возврат и просто общая полученная награда. В настоящее время в нашем примере это просто вознаграждение терминала (+1 или -1 соответственно). Мы вернемся к этому позже, когда включим отдельные награды за продукт.
Альфа, αα, является скоростью обучения, и мы продемонстрируем, как это влияет на результаты позже, но пока простое объяснение: Скорость обучения определяет, в какой степени вновь полученная информация перекрывает старую информацию. . Коэффициент 0 заставляет агента ничего не узнавать, а коэффициент 1 заставляет агента рассматривать только самую последнюю информацию . (Https://en.wikipedia.org/wiki/Q-learning)
Небольшая демонстрация обновления значений
Итак, как мы на самом деле используем это с нашей моделью?
Давайте начнем с таблицы, в которой есть каждый продукт и его начальный V_0 (a):
Теперь мы выбираем случайный выбор продуктов, каждая комбинация известна как эпизод. Мы также для простоты расчетов сейчас положили α = 0,5α = 0,5.
Например:
Следовательно, все действия, которые приводят к этому положительному результату, также обновляются, чтобы создать следующую таблицу с V1 (a):
Итак, давайте попробуем еще раз, выбрав еще один случайный эпизод:
Следовательно, мы можем добавить V2 (a) в нашу таблицу:
Выбор действия
Вы могли заметить, что в демоверсии я просто случайным образом выбрал продукты в каждом эпизоде. Мы могли бы это сделать, но использование полностью случайного процесса выбора может означать, что некоторые действия выбираются недостаточно часто, чтобы определить, хорошие они или плохие.
Точно так же, если мы пошли другим путем и решили выбирать продукты с жадностью, то есть те, которые в настоящее время имеют лучшую ценность, мы можем пропустить тот, который на самом деле лучше, но никогда не имел шанса. Например, если мы выберем лучшие действия из V2 (a), мы получим a2, b1, c1 и d2 или d3, которые оба обеспечивают положительное конечное вознаграждение, поэтому, если бы мы использовали чисто жадный процесс выбора, мы бы никогда не рассмотрели другие продукты, поскольку они продолжают давать положительный результат.
Вместо этого мы реализуем эпсилон-жадный выбор действия, при котором мы случайным образом выбираем продукты с вероятностью ϵ и жадно выбираем продукты с вероятностью 1 − ϵ1 − ϵ, где:
Это означает, что мы быстро достигнем оптимального выбора продуктов, поскольку мы продолжаем проверять, действительно ли «хорошие» продукты являются оптимальными. Но это также оставляет нам возможность время от времени изучать и другие продукты, просто чтобы убедиться, что они не так хороши, как наш текущий выбор.
Построение и применение нашей модели
Теперь мы готовы построить простую модель, как показано в функции MCModelv1 ниже.
Хотя это кажется сложным, я не сделал ничего, кроме как применил ранее обсужденные методы таким образом, чтобы мы могли варьировать входные данные и при этом получать результаты. По общему признанию, это была моя первая попытка сделать это, поэтому мой код может быть написан не идеально, но должен быть достаточным для наших требований.
В настоящее время для расчета вознаграждения терминала мы используем следующее условие, чтобы проверить, не превышает ли общая стоимость наш бюджет:
Полный код модели слишком велик, чтобы здесь хорошо поместиться, но его можно найти на связанной странице Kaggle.
Теперь запустим нашу модель с некоторыми примерами переменных:
В нашей функции у нас есть 6 выходов из модели:
- Mdl [0]: возвращает сумму всех V (a) для каждого эпизода.
- Mdl [1]: возвращает сумму V (a) для самых дешевых продуктов, которую можно определить благодаря простоте наших выборочных данных.
- Mdl [2]: возвращает сумму V (a) для не самых дешевых товаров.
- Mdl [3]: возвращает оптимальные действия последнего эпизода.
- Mdl [4]: возвращает таблицу данных с окончательным V (a), добавленным для каждого продукта.
- Mdl [5]: показывает оптимальное действие в каждом эпизоде.
Из них можно многое извлечь, поэтому давайте рассмотрим каждый из них и определим, что мы можем узнать, чтобы улучшить нашу модель.
Оптимальные действия финального эпизода
Во-первых, давайте посмотрим, что модель предлагает нам выбрать. В этом прогоне он предлагает действия или продукты, общая стоимость которых ниже бюджета, что хорошо.
Однако есть еще кое-что, что мы можем проверить, чтобы понять, что происходит.
Во-первых, мы можем построить общий V для всех действий, и мы видим, что это сходится, что идеально. Мы хотим, чтобы наша модель сходилась, чтобы по мере того, как мы пробуем больше серий, мы «зонируем» оптимальный выбор продуктов. Причина сходства выходных данных заключается в том, что мы каждый раз уменьшаем количество, которое он узнает, в αα, в данном случае 0,5. Позже мы покажем, что произойдет, если мы изменим это или совсем не применим.
Мы также построили график суммы V для продуктов, которые, как нам известно, являются самыми дешевыми, исходя из возможности оценить небольшой размер выборки и другие продукты по отдельности. Опять же, оба показателя положительно сходятся, хотя более дешевые продукты, похоже, имеют немного более высокую стоимость.
Итак, почему это происходит и почему модель предлагала действия, которые она выполняла?
Чтобы понять это, нам нужно проанализировать предложения, сделанные моделью в каждом эпизоде, и то, как это связано с нашим возвращением.
Ниже мы предприняли оптимальные действия для каждого состояния. Мы можем видеть, что предлагаемые действия сильно различаются между эпизодами, и модель, похоже, очень быстро решает, что именно она хочет предложить.
Поэтому я нанес на график общую стоимость предлагаемых действий для каждого эпизода, и мы видим, что действия сначала меняются, а затем сглаживаются, и итоговая общая стоимость ниже нашего бюджета. Это очень помогает нам понять, что происходит.
Пока что все, что мы сказали модели, - это предоставить выбор, который ниже бюджета, и он есть. Он просто нашел ответ, который не соответствует бюджету, как требуется.
Итак, каков следующий шаг? Прежде чем представить награды, я хочу продемонстрировать, что произойдет, если я изменю некоторые параметры, и что мы можем сделать, если решим изменить то, что мы хотим, чтобы предлагала наша модель.
Эффект от изменения параметров и как изменить цель модели
У нас есть несколько параметров, которые можно изменить:
- Бюджет
- Наша скорость обучения, α
- Параметр выбора выходного действия, ϵ
Различный бюджет
Во-первых, давайте посмотрим, что произойдет, если мы сделаем наш бюджет невероятно низким или высоким.
Небольшой бюджет означает, что мы получаем только отрицательное вознаграждение, означает, что мы заставим нашу V сойтись отрицательно, тогда как слишком высокий бюджет заставит нашу V сойтись положительно, поскольку все действия постоянно положительны.
Последнее похоже на то, что у нас было в нашем первом прогоне, многие эпизоды приводят к положительным результатам, и возможно так много комбинаций продуктов, и между самыми дешевыми продуктами мало отличий от остальных.
Если вместо этого мы рассмотрим разумно низкий бюджет с учетом цен на продукты, мы увидим тенденцию, при которой самые дешевые продукты, похоже, сходятся положительно, а более дорогие - отрицательно. Однако плавность их далека от идеала, оба, кажется, сильно колеблются между эпизодами.
Итак, что мы можем сделать, чтобы уменьшить "остроту" результатов? Это подводит нас к следующему параметру - альфа.
Изменяющаяся альфа
Хорошее объяснение того, что происходит с нашим выводом из-за альфы, описано пользователем переполнения стека VishalTheBeast:
«Скорость обучения показывает величину шага, который делается на пути к решению.
Это не должно быть слишком большим числом, поскольку оно может непрерывно колебаться вокруг минимумов, и оно не должно быть слишком маленьким для числа, иначе для достижения минимумов потребуется много времени и итераций.
Причина, по которой рекомендуется снижение скорости обучения, заключается в том, что изначально, когда мы находимся в совершенно случайной точке в пространстве решений, нам нужно сделать большие скачки к решению, а позже, когда мы приближаемся к нему, мы делаем небольшие скачки и, следовательно, небольшие улучшения в наконец достигли минимумов.
Можно провести аналогию следующим образом: в игре в гольф, когда мяч находится далеко от лунки, игрок очень сильно ударяет по ней, чтобы подобраться как можно ближе к лунке. Позже, когда он достигает отмеченной области, он выбирает другую палку, чтобы сделать точный выстрел.
Так что дело не в том, что он не сможет забить мяч в лунку, не выбрав короткую клюшку, он может отправить мяч вперед два или три раза. Но было бы лучше, если бы он играл оптимально и использовал нужное количество силы, чтобы добраться до лунки. То же самое и со сниженной скоростью обучения ». - "источник"
Чтобы лучше продемонстрировать эффект изменения альфа-канала, я буду использовать анимированный сюжет, созданный с помощью Plot.ly.
Я написал более подробное руководство, как это сделать здесь.
В нашей первой анимации мы изменяем альфа от 1 до 0,1. Это позволяет нам увидеть, что по мере того, как мы уменьшаем альфа, наш результат несколько сглаживается, но все равно остается довольно грубым.
Однако, несмотря на то, что результаты сглаживаются, они больше не сходятся в 100 эпизодах, и, более того, их вывод, кажется, чередуется между каждой альфой. Это происходит из-за комбинации небольших альфа, требующих большего количества эпизодов для изучения, и из-за того, что параметр выбора действия эпсилон равен 0,5. По сути, половину времени выход все еще определяется случайностью, и поэтому результаты не сходятся в пределах кадра 100 эпизодов.
При просмотре наших анимированных графиков получается что-то похожее на следующее:
Различный Эпсилон
Имея в виду предыдущие результаты, мы теперь устанавливаем альфа равной 0,05 и меняем эпсилон между 1 и 0, чтобы показать эффект от полностью случайного выбора действий на жадный выбор действий.
На графиках ниже показаны три снимка из разных эпсилон, но анимированную версию можно просмотреть в ядре Kaggle.
Мы видим, что высокий эпсилон дает очень спорадические результаты. Поэтому мы должны выбрать что-то достаточно маленькое, например 0,2. Хотя эпсилон, равный 0, выглядит хорошо из-за того, насколько гладкая кривая, как мы упоминали ранее, это может привести нас к очень быстрому выбору, но может быть не лучшим. Нам нужна некоторая случайность, чтобы модель могла при необходимости исследовать другие действия.
Увеличение количества серий
Наконец, мы можем увеличить количество серий. Я воздержался от этого раньше, потому что мы запускали 10 моделей в цикле для вывода наших анимированных графиков, и это привело бы к взрыву времени, затраченного на запуск модели.
Мы отметили, что низкая альфа потребует больше эпизодов для изучения, чтобы мы могли запустить нашу модель для 1000 эпизодов.
Тем не менее, мы по-прежнему замечаем, что выходная мощность колеблется, но, как упоминалось ранее, это связано с нашей целью просто рекомендовать комбинацию, которая ниже бюджета. Это показывает, что модель не может найти единственную лучшую комбинацию, когда многие из них соответствуют нашему бюджету.
Следовательно, что произойдет, если мы немного изменим нашу цель, чтобы мы могли использовать модель для поиска самой дешевой комбинации продуктов?
Изменение цели нашей модели - найти самую дешевую комбинацию продуктов
Эта цель состоит в том, чтобы более четко отделить самые дешевые продукты от остальных, и это почти всегда обеспечивает нам самую дешевую комбинацию продуктов.
Для этого все, что нам нужно сделать, это немного адаптировать нашу модель, чтобы обеспечить конечное вознаграждение, которое зависит от того, насколько ниже или выше бюджета эта комбинация в эпизоде.
Это можно сделать, изменив расчет возврата на:
Теперь мы видим, что подчеркивается разделение между самыми дешевыми продуктами и другими.
Это действительно демонстрирует гибкость обучения с подкреплением и насколько легко можно адаптировать модель в соответствии с вашими целями.
Представляем предпочтения
Пока что мы не включаем никаких личных предпочтений в отношении продуктов. Если бы мы хотели включить это, мы можем просто ввести вознаграждение за каждый продукт, при этом все еще имея конечное вознаграждение, которое побуждает модель быть ниже бюджета.
Это можно сделать, изменив расчет возврата на:
Так почему же наш расчет доходности теперь такой?
Ну, во-первых, мы по-прежнему хотим, чтобы наша комбинация была ниже бюджета, поэтому мы обеспечиваем положительные и отрицательные награды за превышение и ниже бюджета соответственно.
Затем мы хотим учесть вознаграждение за каждый продукт. Для наших целей мы определяем вознаграждение как значение от 0 до 1. Возврат MC формально рассчитывается с использованием следующего:
γ - коэффициент дисконтирования, который говорит нам, насколько мы ценим более поздние шаги по сравнению с более ранними шагами. В нашем случае все действия одинаково важны для достижения желаемого результата - ниже бюджета, поэтому мы устанавливаем γ = 1.
Однако, чтобы гарантировать достижение основной цели - быть ниже бюджета, мы берем среднее значение суммы вознаграждений за каждое действие, так что оно всегда будет меньше 1 или -1 соответственно.
Опять же, полную модель можно найти в ядре Kaggle, но она слишком велика, чтобы ссылаться на нее здесь.
Представляем предпочтения с помощью вознаграждений
Допустим, мы решили, что нам нужны продукты a1 и b2, мы можем добавить награду к каждому из них. Давайте посмотрим, что произойдет, если мы сделаем это в выходных данных и на графиках ниже. Мы немного изменили бюджет, так как a1 и b2 в сумме составляют 21 фунт стерлингов, что означает, что нет возможности выбрать еще два продукта, которые снизили бы его бюджет ниже 23 фунтов стерлингов.
Применение очень высокой награды вынуждает модель выбирать a1 и b2, а затем работать над поиском продуктов, которые будут соответствовать нашему бюджету.
Я провел сравнение между самыми дешевыми продуктами и остальными, чтобы показать, что модель теперь снова не ценит самую дешевую. Вместо этого мы получаем продукцию a1, b2, c1 и d3 общей стоимостью 25 фунтов стерлингов. Это как ниже нашего бюджета, так и включает наши предпочтительные продукты.
Попробуем еще один сигнал вознаграждения. На этот раз я даю вознаграждение каждому, но хочу, чтобы оно обеспечивало лучшую комбинацию из моих вознаграждений, которая по-прежнему удерживает нас ниже бюджета.
У нас есть следующие награды:
Выполнение этой модели несколько раз показывает, что она:
- Часто выбирайте a1, так как это дает гораздо более высокую награду.
- Всегда выбирал c1, так как награды такие же, но дешевле
- Было сложно выбрать между b1 и b2, так как вознаграждение составляет 0,5 и 0,6, но затраты составляют 8 и 11 фунтов стерлингов соответственно.
- Обычно выбирает d3 как значительно более дешевый, чем d1, даже если награда немного меньше
Заключение
Нам удалось построить модель обучения с подкреплением по методу Монте-Карло, чтобы:
- рекомендовать продукты ниже бюджета,
- рекомендовать самые дешевые продукты и
- рекомендовать лучшие продукты на основе предпочтений, которые все еще ниже бюджета.
Попутно мы продемонстрировали эффект изменения параметров в обучении с подкреплением и то, как их понимание позволяет нам достичь желаемого результата.
На мой взгляд, мы могли бы сделать гораздо больше, конечной целью было бы применить к настоящему рецепту и продуктам из супермаркета, где необходимо учитывать возросшее количество ингредиентов и продуктов.
Я создал этот образец данных и задачу, чтобы лучше понять принцип обучения с подкреплением, и надеюсь, что вы сочтете его полезным.
Спасибо за прочтение!
Стерлинг Осборн
