Расскажу про алгоритм обучения с подкреплением Q-learning и его применении в сфере майнинга процессов. Алгоритм позволяет оптимизировать бизнес-процесс, превращая его из хаотичного графа, с большим количеством связей и ветвлений, в понятный и однозначный оптимальный путь исполнения.
![](https://habrastorage.org/getpro/habr/upload_files/756/465/3fc/7564653fc11c1e1d19c88fb4d9592a0a.png)
Reinforcement Learning
Reinforcement Learning (RL) - одна из парадигм машинного обучения (ML). Основной задачей RL является обучение агентов, которые принимают решения и взаимодействуют с заданной средой. Оно происходит на основе системы наград, которые поощряют их за успешные решения. Такая формулировка задачи подходит для многих реальных задач – искусственный интеллект в компьютерных играх, контроль трафика, оптимизация путей и другие, в том числе и оптимизация бизнес-процессов, которые состоят из набора решений.
Q-Learning
Q-Learning является одним из наиболее простых в реализации RL методов. Он является model-free алгоритмом, то есть не основан на моделях. Некоторые исследователи пытаются дополнить идею с использованием методологии ML. Одним из результатов таких попыток является, например, архитектура Deep Q Networks. В данной статье рассматривается классический Q-learning.
Важной предпосылкой для такой оптимизации является Марковское свойство – каждое действие зависит исключительно от предыдущего. Это позволяет принимать решения на основе нескольких состояний, а не всего пути.
Обучение основывается на Q-таблице, которая для каждого состояния s и каждого возможного действия из этого состояния a хранит Q-значения. Q-таблица инициализируется нулями и заполняется в процессе обучения.
Заполнение таблицы происходит на основе решений агентов. Они могут выбирать действия с помощью exploitation и exploration. В режиме exploitation агенты выбирают действие с максимальным Q-значением:
![](https://habrastorage.org/getpro/habr/upload_files/23f/01b/4f3/23f01b4f3af3511c227c43571f80cf85.png)
При exploration действие выбирается случайно. Выбранным действием агент переходит в следующее состояние s’. Случайные выборы позволяют заполнять новые части таблицы.
Выбор между режимами происходит случайно. На практике вероятность exploitation устанавливают более высокой.
Обновление Q-таблицы происходит по формуле:
![](https://habrastorage.org/getpro/habr/upload_files/b96/6c8/009/b966c80097197591c7474fe06ff1efc2.png)
Выражение в квадратных скобках называется Temporal Difference. Оно включает в себя:
1. R(s, a) - награду за действие a в состоянии s
![- максимальное по всем действиям a’ - максимальное по всем действиям a’](https://habrastorage.org/getpro/habr/upload_files/1fe/792/10c/1fe79210c1ecf291fe26c8168325bce2.png)
Q-значение в следующем состоянии s’. Выбор s’ происходит по описанной выше логике.
Будущие значения дисконтируются с коэффициентом
![](https://habrastorage.org/getpro/habr/upload_files/bd4/9ba/994/bd49ba9946cb46413b0a2badca15c965.png)
– таким образом близкие награды более важны, чем далекие, и результатом оптимизации является кратчайший путь до наибольшего значения.
Пример
Рассмотрим простой пример. Мы хотим найти кратчайший путь из вершины, а (отмечена зеленым) в вершину d (отмечена красным) на некотором графе G:
![Рисунок 1. Граф G Рисунок 1. Граф G](https://habrastorage.org/getpro/habr/upload_files/003/c5b/92a/003c5b92a6a3084908e726a02f6af12a.png)
Задаем вознаграждения: прохождение через существующее ребро будет стоить 15 единиц, а попадание в финальную вершину d – 999 единиц. При попадании в вершину d проход по графу будет останавливаться. Для простоты будет предполагать
![](https://habrastorage.org/getpro/habr/upload_files/55a/667/105/55a667105ac9757d3b09c66d8787c77e.png)
Составим таблицу наград для агента:
![Таблица 1. Таблица наград Таблица 1. Таблица наград](https://habrastorage.org/getpro/habr/upload_files/f37/551/177/f37551177864be54a3e3d102b6cd7d9f.png)
Инициализируем Q-таблицу нулями:
![Таблица 2. Q-таблица Таблица 2. Q-таблица](https://habrastorage.org/getpro/habr/upload_files/008/5ae/e63/0085aee63225545ea15ab0ed1a125334.png)
Первый проход фактически случаен. Пусть выбран путь <a, b, d>. Из-за нулевых Q значений агент заполняет таблицу значениями наград.
![Таблица 3. Первые Q-значения для пути <a, b, d> Таблица 3. Первые Q-значения для пути <a, b, d>](https://habrastorage.org/getpro/habr/upload_files/be2/281/570/be2281570c248310dbaa0ca6a664ec17.png)
Далее при exploitation агенты выбирают путь <a, b, d>.
Ко второй итерации Q-значения сходятся.
![Таблица 4. Итоговые Q-значения пути <a, b, d> Таблица 4. Итоговые Q-значения пути <a, b, d>](https://habrastorage.org/getpro/habr/upload_files/5c8/fbc/1b0/5c8fbc1b0f184bfdab5e281526869645.png)
При случайном выборе пути <a, c, d> его значения сходятся таким же образом.
Далее агент выбирает случайно путь <a, d>. Тогда значение (a, d) заполняется следующим образом:
![Таблица 5. Итоговые значения Q-таблицы Таблица 5. Итоговые значения Q-таблицы](https://habrastorage.org/getpro/habr/upload_files/5fa/7ed/ff1/5fa7edff1b4c56f5f3a2cd1b6d0b7a41.png)
В режиме exploitation агент будет выбирать переход <a,d>.
Значения таблицы сошлись. Для поиска оптимального пути надо из вершины a через максимальные Q-значения прийти в вершину d.
Оптимальный путь - <a,d>.
Финальный граф выглядит так:
![Рисунок 2. Граф G с учетом Q-значений Рисунок 2. Граф G с учетом Q-значений](https://habrastorage.org/getpro/habr/upload_files/7d9/470/6de/7d94706deeb61dd752b07d4d33bd008c.png)
Недостижимые вершины и циклы
Недостижимые вершины можно исключать на этапе выбора действия или выучить их с помощью отрицательных наград. На этапе exploitation агенты не будут проходить через несуществующие ребра за счет их низкого Q-значения. Дополнительно, в задачах часто вводится штраф за циклы в пути.
Python реализация
Для начала необходимо создать матрицу Q-значений и матрицу наград. Для демонстрации утверждений выше добавим в граф G цикл в вершине a – назовем его G’.
![Рисунок 3. Graph G' Рисунок 3. Graph G'](https://habrastorage.org/getpro/habr/upload_files/af3/a02/702/af3a02702325e3666d46c75cfffa04c6.png)
import numpy as np
# Дизайн наград
cycle_fine = -60 # Штраф за цикл
absence_fine = -999 # Штраф за несуществующий переход
step_reward = 15 # Награда за существующий переход
finish_reward = 999 # Награда за завершение
# Матрица ребер графа
adjacency_matrix = np.array([[1, 1, 1, 1],
[0, 0, 0, 1],
[0, 0, 0, 1],
[0, 0, 0, 0]])
# Инициализируем обе матрицы нулями
reward_matrix = np.zeros_like(adjacency_matrix)
q_matrix = np.zeros_like(adjacency_matrix) # Заполняется алгоритмом
# Заполняем матрицу наград
mask = (adjacency_matrix != 0)
# Заполняем наградой за прохождение существующие ребра
reward_matrix[mask] = step_reward
# Заполняем значениями существующие переходы в финальное состояние
reward_matrix[:, -1][mask[:, -1]] = finish_reward
# Заполняем несуществующие переходы штрафом за отсутствие
reward_matrix[~mask] = absence_fine
# Заполняем имеющиеся циклы штрафом за циклы, циклы которых нет в adjacency_matrix заполняем штрафом за отсутствие
diagonal_mask = np.diagonal(adjacency_matrix != 0)
diagonal_values = cycle_fine * diagonal_mask
diagonal_values += absence_fine * ~diagonal_mask
np.fill_diagonal(reward_matrix, diagonal_values)
Результат выполнения:
array([[ -60, 15, 15, 999],
[-999, -999, -999, 999],
[-999, -999, -999, 999],
[-999, -999, -999, -999]])
Далее матрицу наград и Q-матрицу можно подать в алгоритм обучения.
# Обучение
# Заполняем Q-значения
import random
epochs = 1000
eps = 0.2 # Доля exploration
alpha = 1 # Скорость обучения
gamma = 0.8 # Коэффициент дисконтирования
num_states = reward_matrix.shape[1] - 1
for i in range(epochs): # Количество прогонов
# Засчитываем окончание, когда происходит переход в последний столбец таблицы
state = 0
while state != num_states:
eps_hat = random.uniform(0, 1) # Случайная величина, на основе которой выбирается режим
if eps_hat < eps:
# Exploration
action = np.random.choice(range(0, num_states + 1))
else:
# Exploitation
action = np.argmax(q_matrix[state, :])
# Заполняем Q-таблицу в соответствии с формулой
q_matrix[state, action] += alpha * (reward_matrix[state, action] + \
gamma * np.max(q_matrix[action, :]) \
- matrix[state, action])
state = action
После 1000 итераций матрица сошлась:
array([[ 739, 814, 814, 999],
[-199, -199, -199, 999],
[-199, -199, -199, 999],
[ 0, 0, 0, 0]])
Получаем граф, который выглядит следующим образом:
![Рисунок 4. Граф G' с Q-значениями Рисунок 4. Граф G' с Q-значениями](https://habrastorage.org/getpro/habr/upload_files/7dd/f2b/68f/7ddf2b68f9949b090d1851dc400a57e8.png)
Чтобы найти оптимальный путь сделаем проход по максимальным значениям Q-матрицы.
state = 0
print(state, end = "->")
while state != num_states:
action = np.argmax(q_matrix[state, :])
print(action, end = "->")
state = action
print("end")
0->3->end
Вывод 0 -> 3 соответствует пути <a,d>, который является оптимальным решением задачи.
Process Mining
Одним из основных методов майнинга процессов является представление лога в виде графа процесса. Лог – набор данных, который содержит некоторое количество описаний выполнения одного и того же процесса. Лог содержит стадии процесса, время выполнения отдельных стадий, время между стадиями, исполнителя и другие характеристики процесса.
Графы бизнес-процесса выглядят крайне запутано – имеют большое количество связей, вершин, циклов и бутылочных горлышек (стадий, которые могут замедлять процесс). В виде графа процесс может быть подан в Q-learning. Наиболее простой случай – поиск кратчайшего пути в процессе. Такой алгоритм, например, реализован в программной среде SberPM. Развить алгоритм можно через использование времени выполнения ребра или других признаков в наградах.
Q-learning достаточно тяжелый с вычислительной точки зрения – его вычислительная сложность
Он может быть заменен на более легковесные алгоритмы для поиска кратчайшего пути. Q-learning однако создает матрицу с наградами, которая может быть использована для представления субоптимальных, но близких к оптимуму ветвей процесса или нескольких оптимумов.