Маршрутизация в разреженном графе: подход с использованием распределенного Q-обучения.

Распределенным агентам достаточно принять решение всего лишь об одном шаге вперед.

Делиться

Вы, вероятно, слышали об эксперименте «Такой же маленький мир», проведенном Стэнли Милграмом в 1960-х годах. Он разработал эксперимент, в котором добровольцу в Соединенных Штатах передавали письмо с инструкцией переслать его своему личному контакту, который, скорее всего, знал другого человека — целевую аудиторию — в той же стране. В свою очередь, получателя письма просили пересылать его снова и снова, пока не будет достигнута целевая аудитория. Хотя большинство писем так и не дошли до адресата, среди тех, что дошли (здесь проявляется эффект выжившего!), среднее количество переходов составило около 6. «Шесть рукопожатий» стали культурным символом тесной взаимосвязи общества.

Меня до сих пор поражает мысль о том, что люди, имеющие около 102 контактов, умудряются связаться со случайным человеком в сети, насчитывающей около 108 человек, всего за несколько шагов.

Как это возможно? Эвристические методы.

Допустим, меня просят отправить письмо целевому лицу в Финляндии1.

К сожалению, у меня нет контактов в Финляндии. С другой стороны, я знаю человека, который много лет жил в Швеции. Возможно, она знакома с людьми в Финляндии. Если нет, то, вероятно, у нее все еще есть контакты в Швеции, которая является соседней страной. Она — мой лучший шанс приблизиться к нужному человеку. Суть в том, что, хотя я не знаю топологии социальной сети за пределами своих личных контактов, я могу использовать эмпирические правила, чтобы направить письмо в нужном направлении.

Если мы примем точку зрения узлов сети (людей, участвующих в эксперименте), то их действия сводятся к пересылке сообщения (письма) одному из своих исходящих ребер (личных контактов). Эта проблема передачи сообщения в нужном направлении открывает возможности для увлекательного применения машинного обучения!

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

Тем, кто заинтересован в запуске кода, доступ к репозиторию можно получить здесь.

Проблема

Нам будет представлен ориентированный граф, в котором ребра между узлами разрежены, то есть среднее число исходящих ребер от узла значительно меньше числа узлов. Кроме того, каждое ребро будет иметь свою стоимость. Эта дополнительная особенность обобщает случай эксперимента «малый мир», где каждый переход буквы учитывался как стоящий 1.

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

Q-обучение

Q-обучение — это метод обучения с подкреплением, в котором агент поддерживает таблицу пар «состояние-действие», связанных с ожидаемым дисконтированным кумулятивным вознаграждением — качеством, отсюда и название Q-обучение. В ходе итеративных экспериментов таблица обновляется до тех пор, пока не будет достигнут критерий остановки. После обучения агент может выбрать действие (столбец Q-матрицы), соответствующее максимальному качеству для заданного состояния (строка Q-матрицы).

Правило обновления, заданное для пробного действия aj, приводящего к переходу из состояния si в состояние sk, вознаграждения r и наилучшей оценки качества следующего состояния sk, выглядит следующим образом:

[ Q(i, j) leftarrow (1 – alpha) Q(i, j) + alpha left( r + gamma max_{l} Q(k, l) right) ]

Уравнение 1: Правило обновления для Q-обучения.

В уравнении 1:

• α — это скорость обучения, определяющая, насколько быстро новые результаты будут стирать старые оценки качества.
• γ — это коэффициент дисконтирования, определяющий, насколько будущие вознаграждения сопоставимы с немедленными.
• Q — это матрица качества. Индекс строки i — это индекс исходного состояния, а индекс столбца j — индекс выбранного действия.

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

В нашей постановке задачи возможной формулировкой состояния будет пара (текущий узел, целевой узел), а множеством действий — множество узлов. Тогда множество состояний будет содержать N² значений, а множество действий — N значений, где N — количество узлов. Однако, поскольку граф разреженный, данный исходный узел имеет лишь небольшое подмножество узлов в качестве исходящих ребер. Такая формулировка приведет к Q-матрице, в которой подавляющее большинство из N³ элементов никогда не посещаются, что приведет к ненужному потреблению памяти.

Распределенные агенты

Более эффективным использованием ресурсов является распределение агентов. Каждый узел можно рассматривать как агента. Состояние агента — это целевой узел, поэтому его Q-матрица имеет N строк и Nout столбцов (количество исходящих ребер для этого конкретного узла). При наличии N агентов общее количество элементов матрицы равно N²Nout, что меньше, чем N³.

В заключение:

• Мы будем обучать N агентов, по одному для каждого узла в графе.
• Каждый агент будет обучаться Q-матрице размерности [N x Nout]. Количество исходящих ребер (Nout) может варьироваться от одного узла к другому. Для разреженно связанного графа Nout << N.
• Индексы строк Q-матрицы соответствуют состоянию агента, т. е. целевому узлу.
• Индексы столбцов Q-матрицы соответствуют исходящему ребру, выбранному агентом для маршрутизации сообщения к целевому узлу.
• Q[i, j] представляет собой оценку узлом качества пересылки сообщения до его j-го исходящего ребра при условии, что целевым узлом является i.
• Когда узел получает сообщение, он включает в него целевой узел. Поскольку отправитель предыдущего сообщения не требуется для определения маршрутизации следующего сообщения, он не будет включен в последнее.

Код

Основной класс, узел, будет называться QNode.

class QNode: def __init__(self, number_of_nodes=0, connectivity_average=0, connectivity_std_dev=0, Q_arr=None, neighbor_nodes=None, state_dict=None): if state_dict is not None: self.Q = state_dict['Q'] self.number_of_nodes = state_dict['number_of_nodes'] self.neighbor_nodes = state_dict['neighbor_nodes'] else: # state_dict is None if Q_arr is None: self.number_of_nodes = number_of_nodes number_of_neighbors = connectivity_average + connectivity_std_dev * np.random.randn() number_of_neighbors = round(number_of_neighbors) number_of_neighbors = max(number_of_neighbors, 2) # Не менее двух количество исходящих соединений number_of_neighbors = min(number_of_neighbors, self.number_of_nodes) # Не более N соединений self.neighbor_nodes = random.sample(range(self.number_of_nodes), number_of_neighbors) # [1, 4, 5, …] self.Q = np.zeros((self.number_of_nodes, number_of_neighbors)) # Оптимистическая инициализация: все вознаграждения будут отрицательными # q = self.Q[state, action]: state = целевой узел; action = выбранный соседний узел (преобразованный в индекс столбца) для маршрутизации сообщения else: # state_dict равен None, а Q_arr не равен None self.Q = Q_arr self.number_of_nodes = self.Q.shape[0] self.neighbor_nodes = neighbor_nodes

Класс QNode имеет три поля: количество узлов в графе, список исходящих ребер и Q-матрицу. Q-матрица инициализируется нулями. Вознаграждения, полученные от среды, будут равны отрицательному значению стоимости ребер. Следовательно, значения качества будут отрицательными. По этой причине инициализация нулями является оптимистичной инициализацией.

Когда сообщение достигает объекта QNode, он выбирает один из исходящих ребер с помощью алгоритма эпсилон-жадности. Если ε мало, алгоритм эпсилон-жадности в большинстве случаев выбирает исходящее ребро с наибольшим значением Q. Иногда он выбирает исходящее ребро случайным образом:

def epsilon_greedy(self, target_node, epsilon): rdm_nbr = random.random() if rdm_nbr < epsilon: # Случайный выбор random_choice = random.choice(self.neighbor_nodes) return random_choice else: # Жадный выбор neighbor_columns = np.where(self.Q[target_node, :] == self.Q[target_node, :].max())[0] # [1, 4, 5] neighbor_column = random.choice(neighbor_columns) neighbor_node = self.neighbor_node(neighbor_column) return neighbor_node

Другой класс — это графы, называемые QGraph.

class QGraph: def __init__(self, number_of_nodes=10, connectivity_average=3, connectivity_std_dev=0, cost_range=[0.0, 1.0], maximum_hops=100, maximum_hops_penalty=1.0): self.number_of_nodes = number_of_nodes self.connectivity_average = connectivity_average self.connectivity_std_dev = connectivity_std_dev self.cost_range = cost_range self.maximum_hops = maximum_hops self.maximum_hops_penalty = maximum_hops_penalty self.QNodes = [] for node in range(self.number_of_nodes): self.QNodes.append(QNode(self.number_of_nodes, self.connectivity_average, self.connectivity_std_dev)) self.cost_arr = cost_range[0] + (cost_range[1] — cost_range[0]) * np.random.random((self.number_of_nodes, self.number_of_nodes))

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

Когда нам нужно сгенерировать путь от начального узла к целевому узлу, мы вызываем метод QGraph.trajectory(), который, в свою очередь, вызывает метод QNode.epsilon_greedy():

def trajectory(self, start_node, target_node, epsilon): visited_nodes = [start_node] costs = [] if start_node == target_node: return visited_nodes, costs current_node = start_node while len(visited_nodes) < self.maximum_hops + 1: next_node = self.QNodes[current_node].epsilon_greedy(target_node, epsilon) cost = float(self.cost_arr[current_node, next_node]) visited_nodes.append(next_node) costs.append(cost) current_node = next_node if current_node == target_node: return visited_nodes, costs # Мы достигли максимального количества переходов return visited_nodes, costs

Метод trajectory() возвращает список посещенных узлов вдоль пути и список затрат, связанных с использованными ребрами.

Последним недостающим элементом является правило обновления уравнения 1, реализованное методом QGraph.update_Q():

def update_Q(self, start_node, neighbor_node, alpha, gamma, target_node): cost = self.cost_arr[start_node, neighbor_node] reward = -cost # Q_orig(target, dest) <- (1 - alpha) Q_orig(target, dest) + alpha * ( r + gamma * max_neigh' Q_dest(target, neigh') ) Q_orig_target_dest = self.QNodes[start_node].Q[target_node, self.QNodes[start_node].neighbor_column(neighbor_node)] max_neigh_Q_dest_target_neigh = np.max(self.QNodes[neighbor_node].Q[target_node, :]) updated_Q = (1 - alpha) * Q_orig_target_dest + alpha * (reward + gamma * max_neigh_Q_dest_target_neigh) self.QNodes[start_node].Q[target_node, self.QNodes[start_node].neighbor_column(neighbor_node)] = updated_Q

Для обучения наших агентов мы итеративно перебираем пары (start_node, target_node) с помощью внутреннего цикла по соседним узлам start_node и вызываем функцию update_Q().

Эксперименты и результаты

Начнём с простого графа из 12 вершин с направленными взвешенными рёбрами.

Из рисунка 1 видно, что единственным входящим узлом для узла 1 является узел 7, и единственным входящим узлом для узла 7 является узел 1. Следовательно, никакие другие узлы, кроме этих двух, не могут достичь узлов 1 и 7. Когда другому узлу поручают отправить сообщение узлу 1 или узлу 7, сообщение будет перемещаться по графу до тех пор, пока не будет достигнуто максимальное количество переходов. В этих случаях мы ожидаем увидеть большие отрицательные значения Q.

При обучении графа мы получаем статистические данные о стоимости и количестве переходов в зависимости от эпохи, как показано на рисунке 2:

После обучения для узла 4 получена следующая Q-матрица:

Траекторию от узла 4 до, скажем, узла 11 можно получить, вызвав метод trajectory() и установив epsilon=0 для жадного детерминированного решения: [4, 3, 5, 11], что составит общую стоимость без дисконтирования 0,9 + 0,9 + 0,3 = 2,1. Алгоритм Дейкстры возвращает тот же путь.

В некоторых редких случаях оптимальный путь не был найден. Например, для перехода от узла 6 к узлу 9 конкретный экземпляр обученного Q-графа вернул [6, 11, 0, 4, 10, 2, 9] с общей стоимостью без учета дисконтирования 3,5, в то время как алгоритм Дейкстры вернул [6, 0, 4, 10, 2, 9] с общей стоимостью без учета дисконтирования 3,4. Как мы уже говорили, это ожидаемо от итеративного алгоритма.

Заключение

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

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

Спасибо за ваше время, и не стесняйтесь экспериментировать с кодом. Если у вас есть идеи для интересных применений Q-обучения, пожалуйста, сообщите мне!

Источник: towardsdatascience.com