Расскажу про алгоритм обучения с подкреплением Q-learning и его применении в сфере майнинга процессов. Алгоритм позволяет оптимизировать бизнес-процесс, превращая его из хаотичного графа, с большим количеством связей и ветвлений, в понятный и однозначный оптимальный путь исполнения.

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-значением:

При exploration действие выбирается случайно. Выбранным действием агент переходит в следующее состояние s’. Случайные выборы позволяют заполнять новые части таблицы.

Выбор между режимами происходит случайно. На практике вероятность exploitation устанавливают более высокой.

Обновление Q-таблицы происходит по формуле:

Выражение в квадратных скобках называется Temporal Difference. Оно включает в себя:

1. R(s, a) - награду за действие a в состоянии s

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

Будущие значения дисконтируются с коэффициентом

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

Пример

Рассмотрим простой пример. Мы хотим найти кратчайший путь из вершины, а (отмечена зеленым) в вершину d (отмечена красным) на некотором графе G:

Задаем вознаграждения: прохождение через существующее ребро будет стоить 15 единиц, а попадание в финальную вершину d – 999 единиц. При попадании в вершину d проход по графу будет останавливаться. Для простоты будет предполагать

Составим таблицу наград для агента:

Инициализируем Q-таблицу нулями:

Первый проход фактически случаен. Пусть выбран путь <a, b, d>. Из-за нулевых Q значений агент заполняет таблицу значениями наград.

Таблица 3. Первые Q-значения для пути <a, b, d>

Далее при exploitation агенты выбирают путь <a, b, d>.

Ко второй итерации Q-значения сходятся.

Таблица 4. Итоговые Q-значения пути <a, b, d>

При случайном выборе пути <a, c, d> его значения сходятся таким же образом.

Далее агент выбирает случайно путь <a, d>. Тогда значение (a, d) заполняется следующим образом:

В режиме exploitation агент будет выбирать переход <a,d>.

Значения таблицы сошлись. Для поиска оптимального пути надо из вершины a через максимальные Q-значения прийти в вершину d.

Оптимальный путь - <a,d>.

Финальный граф выглядит так:

Недостижимые вершины и циклы

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

Python реализация

Для начала необходимо создать матрицу Q-значений и матрицу наград. Для демонстрации утверждений выше добавим в граф G цикл в вершине a – назовем его G’.

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]])

Получаем граф, который выглядит следующим образом:

Чтобы найти оптимальный путь сделаем проход по максимальным значениям 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 однако создает матрицу с наградами, которая может быть использована для представления субоптимальных, но близких к оптимуму ветвей процесса или нескольких оптимумов.

Q-Learning в сфере оптимизации бизнес-процессов