Как стать автором
Обновить
323.58
Сбер
Технологии, меняющие мир

Обучение с подкреплением: как работают новые возможности библиотеки SberPM

Время на прочтение 6 мин
Количество просмотров 5.4K

Что такое Process Mining и как его применять, мы рассказывали в первом посте. Во второй части мы представили краткое руководство пользования библиотекой для интеллектуального анализа процессов SberPM. В данной статье мы подробнее раскроем функционал библиотеки и расскажем о новом модуле оптимизации процессов и клиентских путей, использующем обучение с подкреплением для поиска оптимального пути.  

Оптимизация бизнес-процессов играет важнейшую роль в повышении операционной эффективности компании. В SberPM обучение с подкреплением используется для реконструкции процесса в соответствии с заданными критериями:

  • Отсутствие зацикленности.

  • Минимальное время выполнения этапов.

  • Минимальное число этапов.

  • Успешное завершение процесса.

Когда применять?

  • Анализ процесса, где слишком много этапов. Процессы с сотнями и тысячами этапов сложны для анализа и практически непригодны для наглядного отображения.

  • Есть редко используемые пути. Не все пути в процессе используются равномерно. С помощью RL можно определить и отсеять неоптимальные пути. 

  • Нужен редизайн процесса. Еще один кейс – понять, как улучшить процесс для редизайна.

  • Необходимо сформировать клиентский путь. Узнать, как быстро и безболезненно «провести» клиента до успешного завершения процесса.

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

Немного теории

Сперва поговорим о том, что такое обучение с подкреплением, или Reinforcement Learning, и чем оно отличается от других разделов Machine Learning.

Все алгоритмы машинного обучения упрощенно можно разделить на 3 большие группы: 

  • Supervised Learning, или обучение с учителем. Модель обучается на заранее размеченных данных c правильными и неправильными ответами. К таким алгоритмам относятся различные классификаторы и регрессоры, на этом же принципе функционируют нейронные сети, решающие задачи сегментации, детекции и т.д.

  • Unsupervised Learning, или обучение без учителя. Здесь нет разметки, поэтому используются различные закономерности в структуре данных, их размещение в пространстве и другие характеристики. В эту группу входят всевозможные кластеризаторы, алгоритмы понижения размерности, эмбеддеры и так далее.

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

Рассмотрим подробнее, каким образом это происходит. Обычно в обучении с подкреплением выделяют два абстрактных объекта – среда (environment) и агент (agent). Агент взаимодействует со средой, получая от нее фидбэк в виде наград. В процессе обучения агент стремится совершать действия, которые максимизируют получаемые им награды.

Для лучшего понимания того, что происходит в RL, также необходимо ознакомиться с Markov Decision Process (MDP). МDP позволяет математически корректно сформулировать любую проблему, возникающую в обучении с подкреплением. 

Markov Decision Process – это набор пар(кортеж) (S, A, P, R, 𝛾), где:

  • S – конечное множество состояний;

  • A – конечное множество действий;

  • P – матрица вероятностей перехода;

  • R – награда, которую аккумулирует агент;

  • 𝛾 – discount factor, определяющий, насколько важны для агента мгновенные награды по сравнению с удаленными по времени.

Как уже было сказано, «адекватный» агент при обучении стремится максимизировать математическое ожидание наград EttRst, где 0 ≤ 𝛾 ≤ 1 – наш discount factor. Для того, чтобы агент действовал эффективно, нам необходимо найти функцию policy π, сопоставляющую каждому состоянию S наилучшее действие A, Ai:Si∀ i. Эту задачу можно решить с помощью уравнений Беллмана:

Bellman Expectation Equation for State-Action Value Function (Q-Function)
Bellman Expectation Equation for State-Action Value Function (Q-Function)
Bellman Optimality Equation for State-Action Value Function
Bellman Optimality Equation for State-Action Value Function

Первое уравнение позволяет оценить, к какой именно policy сойдется агент, совершая действие at в состоянии st .Полученные Q-values Q(s, a) говорят о том, насколько хороша в смысле оптимальности конкретная пара состояние-действие.  

Благодаря второму уравнению (Bellman Optimality Equation) становится возможным найти наилучшую policy * среди всех π в пространстве заданного MDP.Оно также говорит о том, что в любом MDP есть как минимум одна оптимальная policy *.

Интуитивно видно, что типичный процесс в Process Mining и MDP очень похожи: состояниями s являются активности (или узлы на графе процесса), а действиями a являются переходы между активностями (или ребра на графе процесса). Для удобства вероятностями переходов P можно пренебречь или считать их равновероятными, так как для задачи поиска оптимального пути они несущественны. Осталось понять, как решать приведенные выше уравнения.

Алгоритмы RL можно разделить на 2 группы:

  • Model-free. Данные алгоритмы при обучении полагаются только на реальные объекты из среды, в зависимости от структуры которой агент меняет свое поведение. К ним относятся Monte-Carlo, Q-Learning, SARSA, Actor-Actor, Actor-Critic, REINFORCE и т. д.

  • Model-based. Алгоритмы, использующие принципы динамического программирования для поиска оптимальной policy *, напрямую вычисляя ее из заданных вероятностей переходов, состояний и действий. Их использование трудозатратно, поэтому на данный момент они применяются довольно редко. К ним относятся Policy iteration, Value iteration.

Еще одна проблема, встречающаяся в RL, называется Exploration-Exploitation trade-off. Ее суть заключается в том, что при обучении агента можно пойти двумя путями:

  • Exploit. Здесь агента обучают исключительно на известных действиях и примерах, которые, по мнению разработчика, являются наилучшими. В ряде случаев этот подход действительно надежен, но обычно при его применении есть большой риск оказаться в «глобальном минимуме» наград.

  • Explore. В данном случае при обучении агент будет сам пытаться найти лучшие действия для всех состояний, жертвуя временем и силами.

Мы подошли к решению этой проблемы основательно – в SberPM у пользователя есть выбор между двумя подходами. В случае эксплуатации известных примеров используется Monte-Carlo, а для исследования среды предназначен уже популярный и известный Q-Learning. Остановимся на нем подробнее.

Как показано выше, Q-Learning основан на уравнениях Беллмана и позволяет быстро и эффективно найти оптимальные Q-values для каждой пары состояние-действие. Изначально все Q-values инициализируются нулями, после каждого действия агента они обновляются в соответствии с заданным Learning Rate. Таким образом, Q-Learning напрямую аппроксимирует оптимальную policy *. Фактически алгоритм строит таблицу S-A-Q(S, A), которую еще называют Q-table, а затем выбирает из них комбинации с максимальными Q-Values.

Перейдем к реализации указанных алгоритмов в SberPM.

Использование SberPM для поиска оптимального пути в процессе

Как применять?

Шаг 1. Создание среды и выбор метода.

  • data_holder содержит лог-файл по процессу;

  • RLOptimizer создает среду по процессу, в которой состояния это этапы процесса, а действия – переходы между этапами. Каждый переход награждается в зависимости от того, насколько он оптимален по заданным критериям.

Рассмотрим для примера следующий процесс:

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

При создании среды необходимо выбрать тип обучения: 

  • Exploitation: агент следует только по цепочкам, которые присутствуют в лог-файле, обучая свою политику выбора действий. После обучения агенту разрешается выбирать действия самостоятельно для реконструкции процесса.

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

Например, с методом Exploitation более вероятно обнаружить оптимальную цепочку begin->A->C->success->end. В случае Exploration такой путь можно не найти, если в данных были только пути begin->A->B->…

Шаг 2. Задание наград.

Дизайн наград – ключ к построению успешной реконструкции. Необходимо оценить, какая из метрик наиболее важна для процесса, задать успешные исходы и определиться с штрафом за циклы. Если некоторые зацикливания для процесса являются нормой, штраф может быть уменьшен.

Шаг 3. Обучение и реконструкция.

Запустим обучение RL-агента. Результатом метода fit будет pandas.DataFrame со сгенерированными агентом цепочками активностей и наградами за них. Совокупность лучших цепочек и будет реконструированным процессом.

Продемонстрируем работу алгоритма на примере открытого лог-файла процесса по возмещению расходов на командировки с BPI Challenge 2020

Исходный процесс выглядит так:

Граф имеет заметную структуру, видны разнообразные отклонения от основного течения процесса.

  • 2.36% – средняя зацикленность этапа процесса;

  • 8 этапов – средняя длина пути;

  • 74% – вероятность успешного завершения.

Это хорошие показатели для такого процесса. Обучим реконструкцию с помощью модуля RL SberPM и сравним результаты.

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

  • 0% – средняя зацикленность;

  • 4.7 этапа – средняя длина пути (на 40% меньше);

  • 100% – вероятность успешного завершения.

Модуль RL уже успешно применяется в анализе бизнес-процессов и клиентских путей и теперь он находится в открытом доступе репозитория библиотеки SberPM на GitHub.

Нам важна обратная связь по разработкам, ваши коммиты и отзывы очень помогут нам в развитии удобного и функционального продукта. 

Теги:
Хабы:
+8
Комментарии 0
Комментарии Комментировать

Информация

Сайт
www.sber.ru
Дата регистрации
Дата основания
Численность
свыше 10 000 человек
Местоположение
Россия