Метод информированного исследования на основе графов знаний и механизма рассуждений в обучении с подкреплением тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Письмеров Алексей Максимович

• Письмеров Алексей Максимович
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Письмеров Алексей Максимович

Реферат

Synopsis

Введение

ГЛАВА 1. Графы знаний и обучение с подкреплением:

подходы, ограничения и гипотеза интеграции

1.1 Основы машинного обучения с подкреплением

1.2 Графы знаний и механизмы рассуждения

1.3 Символьные, субсимвольные и нейросимвольные подходы

1.4 Интеграция графов знаний в RL

1.5 Вывод по главе

ГЛАВА 2. Инъекция знаний в обучение с подкреплением:

Подходы и методы

2.1 Методы обучения с подкреплением: Абстракции и инъекция знаний

2.2 Типы знаний: Эксплицитные и имплицитные знания

2.3 Методы инъекции знаний в процесс обучения с подкреплением

2.4 Графы знаний: построение, векторизация и применение для path-based reasoning

2.5 Вывод по главе

ГЛАВА 3. Метод информированного исследования

3.1 Концептуальные основы поиска на графах в RL

3.2 Постановка задачи

3.3 Реализация алгоритма

3.4 Подходы к управлению исследованием на основе графов: использование графа знаний для оптимизации стадии исследования

3.5 Вывод по главе

ГЛАВА 4. Проведение и анализ экспериментов в динамичных

средах

4.1 Механизм обновления и аугментации графа знаний

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

4.3 Эксперимент инъекции знаний

4.4 Вывод по главе

Заключение

Словарь терминов

Список литературы

Приложение

Приложение

Тексты публикаций

Реферат

Введение диссертации (часть автореферата) на тему «Метод информированного исследования на основе графов знаний и механизма рассуждений в обучении с подкреплением»

Актуальность темы

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

— Здравоохранение. Диагностирование заболеваний на основе анализа изображений или данных анализов пациента. Составление индивидуального плана лечения, сопровождение в процессе его осуществления.

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

— Транспорт и логистика. Управление логистическими хабами, контроль и управление потоками, навигация и оптимизация маршрутов. Работа беспилотных автомобилей и роботизированной техники.

— Маркетинг. Персонализированная реклама, анализ поведения клиентов, предоставление предложений на основе его поведения.

— Образование. Адаптация контента, его сложности. Индивидуальная учебная программа.

Многие крупные компании уже используют различные системы принятия решений для своих нужд. Так, компания Google развивает проект DeepMind и использует его для диагностики заболеваний по медицинским изображениям. Система автопилота Tesla принимает решения на многих этапах: от построения маршрута в навигации до реакции на обстановку и дорожные условия в реальном времени. Яндекс также разрабатывает беспилотный автомобиль и применяет системы принятия решений для управления таксопарком. Нефте-и газодобывающие компании "Газпромнефть" и "Роснефть" используют нейронные сети для системы "Цифровое месторождение", которая, основываясь на показателях, принимает решения для оптимизации работы месторождения. Аналогичные подходы применяются и в энергетике для управления распределёнными сетями и оптимизации использования ресурсов.

Одним из основных подходов для построения системы принятия решений является использование моделей с подкреплением (RL). Модели RL наиболее активно применяются в задачах, где необходимо принимать несколько последовательных решений в динамично меняющемся окружении. Такие задачи наиболее близки к реальным по условиям, ограничениям и требованиям, поэтому эта область активно исследуется. Однако, несмотря на существенные успехи применения RL-моделей в различных областях, проблема «exploration vs. exploitation»(«исследование vs. использование») [1] все еще представляет собой важное направление для исследования. Наиболее остро возникает вопрос использования стадии исследования, так как она может как привести к повышению награды для агента, так и к уменьшению, а в некоторых случаях и к потерям. Данное исследование посвящено решению проблемы применения стадии исследования в рамках обучения с подкреплением в динамически меняющемся окружении при помощи алгоритма поиска пути на графе, применяемом к графу знаний, содержащему накопленное описание окружения, его сущностей и связей между ними. Таким образом, исследование путей повышения эффективности стадии исследования в RL является одной из актуальных задач современной теории и практики обучения с подкреплением.

Проблема «исследование vs. использование» была обозначена сразу же после начала использования RL-моделей. Уже в 1989 году были предприняты активные действия по исследованию этой задачи. Предполагались различные подходы для повышения эффективности использования стадии исследования. Например, предлагались подходы с использованием метапараметров для подбора оптимального значения при работе метода. Также был предложен подход с разделением стадий исследования и использования на независимые этапы. Все эти подходы демонстрируют улучшенную работу на средах, в которых они тестировались. Современные исследования показывают, что несмотря на множественные попытки предложить подход для решения проблемы исследования, в сложных системах, предложенные методы все еще не являются универсальными и оптимальными как для одноагентных моделей, так и для мультиагентных.

На начальном этапе исследования RL предлагались табличные методы, такие как Q-Learning и SARSA. Эти алгоритмы основывались на представлении функций ценности для состояний и действий в виде таблиц. Основная идея заключалась в обновлении этих таблиц по мере того, как агент получает новые данные о среде. Основными алгоритмами на этом этапе можно назвать: Q-Learning — базовый алгоритм обучения с подкреплением, который асинхронно оценивает функцию ценности действия без модели среды. SARSA — on-policy алгоритм, который учитывает конкретную политику при обновлении ценностей действий. При этом табличные методы плохо масштабируются на задачи с большим числом состояний. Как правило, они работают только для задач с дискретными пространствами состояний и действий.

Следующим этапом можно назвать алгоритмы актор-критик, которые разделяют архитектуру на два компонента: актор (actor), который выбирает действия, и критик (critic), который оценивает качество этих действий. АЗС предложил идею асинхронного обучения нескольких агентов параллельно, что значительно ускоряет обучение. АЗС предлагает параллельное обучение, что увеличивает стабильность и скорость конвергенции. А2С — более стабильная и синхронная версия АЗС. Однако, даже с асинхронностью и улучшениями, такие модели могут быть нестабильными в зависимости от выбранной среды и

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

Следующим этапом развития после актор-критик алгоритмов стало использование нейронных сетей для аппроксимации функций ценности вместо табличного представления. DQN успешно применил эту технику для игры в Atari, решая проблему высокоразмерных пространств состояний. DQN решает проблему "проклятия размерности", используя сверточные нейронные сети для представления сложных пространств состояний. Double DQN решает проблему переоценки Q-значений, улучшая стабильность и точность. Тем не менее остаётся неэффективность при работе с непрерывными пространствами действий. DQN требует большого количества данных для обучения. Кроме того, сохраняются трудности при применении для задач, требующих долгосрочного планирования. Успех DQN положил начало целому направлению deep RL, став отправной точкой для многих последующих модификаций.

На следующем этапе развития появился алгоритм DDPG, он стал одним из первых методов, работающих с непрерывными пространствами действий. Он объединяет идеи из DQN и Actor-Critic. TRPO и РРО предложили улучшения методов оптимизации политики, обеспечивающие более стабильное обучение. DDPG показал хорошие результаты в задачах с непрерывными действиями, например, в робототехнике. РРО, благодаря ограничению на изменение политики, обеспечивает более стабильное обучение, чем TRPO и другие методы. Однако DDPG подвержен нестабильности и сильно чувствителен к выбору гиперпараметров. РРО всё ещё требует сложной настройки гиперпараметров, особенно в сложных средах.

Meta-RL фокусируется на создании агентов, которые могут быстро адаптироваться к новым задачам, используя знания, полученные в предыдущих задачах. Это важно для построения универсальных агентов, способных работать в различных средах с минимальным количеством данных. MAML позволяет агенту

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

Помимо исследований направленных на общее улучшение работы RL предпринимались попытки модифицировать отдельно процесс исследования для улучшения работы моделей, например: Epsilon-Greedy, Bayesian Optimization for Exploration, Random Network Distillation, Count-Based Exploration, ModelBased Exploration.

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

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

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

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

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

Таким образом, существуют подходы использующие графы знаний для внедрения и хранения информации, существуют подходы рассуждения (reasoning) для извлечения новых знаний на основании уже известных объектов и связях в графах знаний. При этом, в рамках работы агента в моделях обучения с подкреплением, на этапе исследования требуется предоставить агенту выбор из действий, выходящих за рамки его представления об окружающей среде. Хотя в литературных источниках имеются результаты исследований по совместному применению рассуждений на графах знаний и моделей обучения с подкреплением, известные работы направлены на повышение эффективности вывода и поиска в графе с помощью RL либо рассматривают графы как внешнее средство

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

Цель

Целью является разработка метода, который повышает среднее вознаграждение, получаемое ИЬ-агентом в процессе обучения с подкреплением путём определения действий на основе информированного исследования в условиях динамически изменяющейся среды. Поставленная цель отражает стремление повысить эффективность агентов, функционирующих в условиях высокой неопределённости и изменчивости среды, где классические методы демонстрируют ограниченные результаты.

Задачи

Для достижения данной цели в рамках диссертации были поставлены и решены следующие задачи:

Задача 1 - Аналитический обзор методов решения задачи принятия решений в задачах машинного обучения с подкреплением для обозначения направления исследования.

Задача 2 - Исследование и анализ современных методов анализа пути графа и принятия решений в задачах машинного обучения с подкреплением, классификация и обобщение рассмотренных подходов.

Задача 3 - Разработка метода принятия решений с использованием алгоритма поиска пути на графе и его применение в задаче машинного обучения с подкреплением.

Задача 4 - Проектирование и подготовка среды для проведения экспериментов, включая сбор информации, анализ подходящих для исследования задач и окружений.

Задача 5 - Исследование эффективности инъекции знаний в граф знаний на стадии исследования агентом.

Задача 6 - Сравнение результатов предложенного метода в рамках эксперимента с аналогами, рассмотренными ранее в обзоре.

Методы исследования

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

Основные положения, выносимые на защиту На защиту выносятся:

1. Метод обучения агента в системе обучения с подкреплением, основанный на модифицированной архитектуре Actor-Critic, реализующей этап исследования посредством рассуждения в графах знаний и обеспечивающей

формирование агентом контекстуально релевантных действий в соответствии с текущим состоянием среды.

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

Научная новизна

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

Научная новизна 2 - для разработанного метода инъекции априорных знаний в долговременную память ИЬ-агента предложена гибридная нейросимвольная архитектура, повышающая способность адаптации агента к динамическим средам и ускоряющая фазу исследования, отличающаяся совместным хранением априорных знаний и приобретённого опыта взаимодействия со средой в памяти агента на основе графа знаний, динамически обновляемого в процессе обучения агента.

Научно-техническая задача

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

Объект исследования

Объектом исследования являются методы машинного обучения с подкреплением в условиях динамически изменяющегося окружения.

Предмет исследования

Предметом исследования является механизм принятия решений модели с подкреплением на стадии исследования.

Теоретическая значимость

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

Практическая значимость

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

Достоверность

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

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

Внедрение результатов работы

Результаты диссертационной работы внедрены в виде программной реализации разработанного метода информированного исследования для задач обучения с подкреплением в учебный процесс Университета ИТМО для проведения занятий по дисциплинам «Графы знаний» и «Валидация и тестирование систем искусственного интеллекта», а предложенные метод и программная реализация опубликованы в репозитории Bitbucket1. Разработанный метод повышает устойчивость и скорость обучения агентов в динамических средах и может применяться в интеллектуальных системах управления и обучающих платформах.

Апробация результатов работы

По теме диссертационного исследования опубликовано 6 научных работ, из которых 4 публикации в изданиях, рецензируемых Web of Science или Scopus, 1 публикация в журналах из перечня ВАК. Основные результаты исследования нашли отражение в одной статье в рецензируемом международном журнале и двух публикациях в материалах ведущих международных конференций.

В статье Pismerov А., Mouromtsev D. "Boosting Exploration in Reinforcement Learning Agents via Path-Based Knowledge Graph Reasoning" // Lobachevskii

^ttps://bitbucket.org/Alekceu/iac.git

Journal of Mathematics, 2025, Vol. 46, No. 5 представлены теоретические основы и экспериментальные результаты, связанные с разработкой метода Path-Based Reasoning для стадии исследования в моделях обучения с подкреплением. Работа индексируется в Scopus и Web of Science, входит в Перечень ВАК и в Белый список РИНЦ. Публикация демонстрирует вклад предложенного метода в улучшение метрик средней награды и устойчивости обучения, а также подчёркивает универсальность подхода для различных типов сред.

В материалах международного семинара по интеллектуальным системам опубликована статья Wardenga R., Kovriguina L., Pliukhin D., Radyush D., Smoliakov I., Xue Y., Muller H., Pismerov A., Mouromtsev D., Kudenko D. "Knowledge Graph Injection for Reinforcement Learning" // CEUR Workshop Proceedings, 2023, Vol. 3559. В работе представлена концепция инъекции априорных знаний в графы знаний для ускорения обучения агентов. Особое внимание уделено экспериментальной проверке метода на текстовых средах, где было показано снижение времени сходимости и рост успешности эпизодов. Публикация индексируется в Scopus.

На международной конференции 5th International Conference on Algorithms, Computing and Artificial Intelligence (АСАГ22) была опубликована статья Pismerov A., Pikalov M. "Applying Embedding Methods to Process Mining" // Proceedings, 2022, pp. 430-434. Работа рассматривает применение методов графовых эмбеддингов для анализа и оптимизации процессов, демонстрируя возможность переноса предложенных в диссертации идей в смежные области анализа данных и интеллектуальных систем. Статья индексируется в Scopus.

Все перечисленные публикации напрямую связаны с темой диссертационной работы и отражают ключевые этапы её реализации: разработку и обоснование метода исследования на основе графов знаний, внедрение механизма инъекции априорных знаний, а также применение методов в смежных задачах анализа данных.

Результаты исследования апробированы в рамках международных научных мероприятий, включая ACM Genetic and Evolutionary Computation Conference (GECCO 2023) и АСАГ22.

Таким образом, апробация диссертационной работы подтверждается публикацией материалов в рецензируемых изданиях, индексируемых в ведущих мировых базах данных.

Личный вклад автора

Автор провёл исследование, включающее обзор литературы о существующих современных методах обучения моделей с подкреплением, подходах, применяемых в качестве механизма рассуждения на графах знаний. Проведена работа по оценке изученности подходов, применяемых на этапе исследования. В результате анализа предложена постановка задачи, затем выдвинута идея о возможности разработки нового метода, выносимого на защиту. Разработан метод. Разработан программный комплекс, реализующий работу модели машинного обучения с подкреплением в динамически изменяющейся среде с возможностью ее замены. На этапе исследования в рамках разработанного программного комплекса внедрен механизм рассуждения на графе знаний, реализованный путем использования алгоритма A*Net. Результаты авторской работы легли в основу публикаций на международных конференциях и в рецензируемых журналах.

Структура и объем диссертации

Диссертация включает в себя следующие разделы:

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

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

На сегодняшний день существует множество различных алгоритмов, подходов и их модификаций для решения задач в условиях неопределённости, требующих принятия решений, основываясь на ограниченных знаниях о среде, условиях и ограничениях, накладываемых внешними факторами. Одним из наиболее популярных классов таких подходов является машинное обучение с подкреплением. В данном разделе работы освещены ключевые аспекты машинного обучения с подкреплением, которое зарекомендовало себя как одно из наиболее эффективных направлений в решении задач, связанных с динамическим принятием решений в условиях неопределённости. Методы ИТ позволяют формализовать процесс обучения агента в среде, где требуется выработка оптимальных стратегий взаимодействия, минимизируя ошибки и максимизируя выгоды на основе ограниченной информации о внешних условиях. Такой подход делает НЬ универсальным инструментом для моделирования поведения систем в широком спектре приложений — от игр до управления робототехникой.

Список литературы диссертационного исследования кандидат наук Письмеров Алексей Максимович, 2025 год

Список источников:

1.Lobo F. J., Lima С. F., Michalewicz Z. (ed.). Parameter setting in evolutionary algorithms. - Springer Science & Business Media, 2007. - T. 54.

2. Mersmann О., Preuss M., Trautmann H. Benchmarking evolutionary algorithms: Towards exploratory landscape analysis //International Conference on Parallel Problem Solving from Nature. - Springer, Berlin, Heidelberg, 2010. - C. 73-82.

3. Dang N., Doerr C. Hyper-parameter tuning for the (1+(X, X)) GA //Proceedings of the Genetic and Evolutionary Computation Conference. - 2019. -C. 889-897.

4. Weise Т., Wu Z. Difficult features of combinatorial optimization problems and the tunable w-model benchmark problem for simulating them //Proceedings of the Genetic and Evolutionary Computation Conference Companion. - 2018. - C. 1769-1776.

5. Kerschke P., Trautmann H. The R-Package FLACCO for exploratory landscape analysis with applications to multi-objective optimization problems //2016 IEEE Congress on Evolutionary Computation (CEC). - IEEE, 2016. - C. 5262-5269.

6. Svozil D., Kvasnicka V., Pospichal J. Introduction to multi-layer feedforward neural networks //Chemometrics and intelligent laboratory systems. -1997.-T. 39. - №. l.-C. 43-62.

98

Applying Embedding Methods to Process Mining

Aleksei Pismerov Maxim Pikalov

[e-mail] [e-mail]

ITMO University Saint Petersburg, Russia

ABSTRACT

The performance of process mining algorithms on a particular event log highly depends on the number of different processes present in the logs. Prior event log clustering can help find out which processes certain events in the logs belong to. Since log clustering is not always a simple task, a preliminary transition from logs to log embeddings can be an important step in solving process mining problems.

In this paper, we apply different embedding methods to a dataset of event logs. By transitioning to log embeddings and applying clustering methods we improve the efficiency of process mining. The experiment results suggest that embeddings capturing events order perform better than others.

CCS CONCEPTS

• Information systems ^ Association rules; Data cleaning; Data analytics.

KEYWORDS

Process mining, Process Discovery, Embeddings ACM Reference Format:

Aleksei Pismerov and Maxim Pikalov. 2022. Applying Embedding Methods to Process Mining. In 2022 5th International Conference on Algorithms, Computing and Artificial Intelligence (ACAI2022), December 23-25, 2022, Sanya, China. ACM, New York, NY, USA, 5 pages. https://doi.org/10.1145/3579654. 3579730

1 INTRODUCTION

The emergence of the ability to store and process data in electronic form led to the formation of a new section in computer science -data mining [4]. It is aimed at discovering and extracting patterns and new knowledge from a large volume of data. Responding to the challenges that arise when faced with more definitive or specific tasks of data processing and analysis, different branches of data mining began to form.

Process mining [34] is one of the most actively developing areas of data processing in the last ten years. The main trait of process

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [e-mail]. ACAI 2022, December 23-25, 2022, Sanya, China

© 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-9833-6/22/12... $15.00 https://doi.org/10.1145/3579654.3579730

mining problems is that they are usually formulated on the basis of event data or logs of various processes. Such tasks have begun to arise recently more and more often [11] due to the development of tools and instruments for collecting and storing records of the events that have occurred. For example, information systems nowadays are everywhere and usually include logging systems for managing event records [13]. This generates a huge amount of information about events and processes. Additionally, corporation business processes have become so complex and distributed that the stored data cannot be analyzed and processed using conventional approaches.

Process mining methods were developed to meet today's challenges. Currently, various approaches are presented to solve process mining problems [31]. The main algorithms are the alpha and inductive algorithms and approaches based on heuristic estimates. All these methods are not a universal solution to heterogeneous data problems, so the development of new approaches remains relevant as more and more information and business processes are created. New methods require their own approach due to the nature of the data or the problem statement.

Machine learning methods are considered the most suitable for solving problems in the uncertainty or the lack of information [23]. Therefore, in this paper, we consider the feasibility of using various embeddings for event data, analyze the results of clustering such representations, and compare different embedding methods currently used in the machine learning area. This will allow us to conclude that the development of machine learning approaches for solving process mining tasks is promising.

2 PROCESS MINING

The task of processing event data has only recently begun to be studied [7]. Still, it is already possible to list algorithms that have gained popularity both in academic and practical environments. One of the most fundamental algorithms is the alpha algorithm [33], which is based on the idea ofdetecting relationships between events presented in the dataset. Another approach used to solve mining problems is the heuristic algorithm [35], which is the development of the idea of the alpha algorithm and is resistant to noise due to the use of heuristics when calculating significant relationships of events from logs. Another important algorithm is the inductive algorithm [15], the idea of which is to loop a directly follows graph and then cut it based on predefined rules. This allows the log to be split into sub-logs and create a representation of the process described by the event data in the form of a process tree.

In addition to the fact that there are different algorithms for mining problems, there are three categories of tasks that require different problem formulation and solution [32]. The most popular

ACAI 2022, December 23-25, 2022, Sanya, China

one is the discovery process, for which most existing algorithms have been developed. The purpose of the discovery process task is to extract knowledge about the process and build a representation of the studied process on data from the logs. If there is a pre-existing process model, then the task of conformance checking is to build a process model based on its event logs and to compare it with an existing model. The third type of task implies that there is not just a process model, but this is an a priori model so that performance can be analyzed for the model based on event data. Generally, the main task of process mining is the task of building processes based on event log data. Additionally it deals with tasks of comparing different process models and the search for the best performing model.

3 PROBLEM STATEMENT

As already stated in Section 2, the mining process is an important task, the solution of which is not trivial due to the incompleteness of the data [2]. Such conditions arise due to the fact that event data is a large amount of unstructured information whose relation to the process model that is described by these logs is not obvious.

Establishing relationships between event data records and calculating their similarity is a difficult task, which sometimes is solved with insufficient accuracy even by popular existing algorithms [5]. For example, some algorithms could generate process models with phantom loops or phantom links between events from log files [28]. Or, on the contrary, could underestimate the strength of the connection between events, ignoring the existing real connections in the created models.

The task we are solving in our study can be formulated as follows: let there be a log file L consisting of various events

L = {at,bi,ci,...di ,kt ,qp }, where the elements of the set L are events associated with various processes. We are faced with the problem of dividing the elements of the set L into subsets in such a way that they would describe real logged processes.

L = {Pt,P2 ...,Pi-!,Pi}. At the same time, an essential requirement of the process modeling task is not only to group events related to one process but also to preserve the links between the process stages recorded in the log file. In other words, our problem can be formulated as a search of sets P\,P2,P3..., Pi such that each of these sets contains elements of one process and at the same time describes the connections between these elements.

Pn = {< ai, b\, c\ >, < b\, ai >, < c\, a\ > ... < a\, e\,j\, hi >}.

In our work, we propose to use both text embeddings and graph embeddings. For text embeddings, we propose representing events from the logs and their connections as strings, with events being words and event sequences being sentences. Graph embedding usage seems natural since events in the logs and their connections are essentially graphs. We use clustering methods on computed embeddings to solve the process mining problem. Our assumption is that the use of embeddings will help to cluster events related to

Aleksei Pismerov and Maxim Pikalov

Table 1: Dataset from BPI Challenge 2019

Field name Unique values count

concept:name 42

case:Item Category 4

case:concept:name 251734

case:Vendor 1975

one process with high accuracy. We also hope that resulting models built from graph or string event logs representation will capture existing event connections and won't generate phantom ones.

4 DATASET

In order to test our approach, we selected the dataset presented at the International Business Process Intelligence Challenge 2019 [6]. This dataset is a set of order processing event data from a process for more than sixty companies placing orders with one of the largest international suppliers of coloring and surface treatment materials. Orders include various items and can be represented by the two-way or three-way matching payable process; orders also may be presented in the form of a consignment. For this dataset, the task is to present order process models which accurately represent the original processes. Considering the information about the dataset and the types of flows presented, we conclude that at least four process models are expected to be generated. However, the number of models may differ as long as they accurately describe the actual ordering processes.

Looking into the dataset in more detail, we can see that it is an event log with 25 fields and 1595923 event entries, consisting of 42 activities of over 600 participants. The event ID is a composite key from the purchase document ID and item ID. For a brief introduction, we will describe only the most important fields of the dataset.

The dataset field used as a case ID of the process mining task is case:concept:name field, which is the combination of the purchase document and the purchased item. The timestamp is a date field related to the moment of the occurrence of the event described in the logs file with concept:name, Document Type, Item Category and Name fields.

Table 1 presents some statistics reflecting the number of unique values for some fields like unique activities performed during the order process, categories of economic relations associated with the order, unique combinations of the purchase document ID and the item ID, and the number of vendors participating in the product orders described in the dataset. Considering the statistics, we can conclude that the ordering processes are relatively small since they consist of no more than forty-two unique stages, with several vendors possibly participating in the same order and with a large amount of documentation being generated during the ordering process. We conclude that we expect about four different models as the results of the process model generation, with each model corresponding to the economical category presented in the event data.

5 EMBEDDINGS

Embedding techniques [17] are a variety of methods that convert objects into some numerical representation, most often a vector.

Applying Embedding Methods to Process Mining

Each object is associated with a certain vector, which usually contains various characteristics of this object in relation to the entire set of objects. Currently, embedding methods are actively studied [29], and there are algorithms to compute embeddings for almost all entities encountered in data mining and machine learning problems. With embeddings, various operations that are difficult to carry out with original objects can be effectively carried out, in particular, the identification of the similarity and dissimilarity of objects. In our research, we consider several popular embedding methods that are currently being actively studied.

5.1 Word2Vec

Word2Vec [20] is a shallow two-layer neural network trained to recover the linguistic context of words. The model takes a large text corpus as input and maps each unique word to a vector, usually of several hundred dimensions. First, a dictionary is created, and then the corresponding vector representation is calculated for the words from the dictionary. The vector representation is based on contextual proximity: words that occur in the text next to the same words (and therefore have a similar meaning) in the vector representation have a high cosine similarity.

, ч A -в Z"=1 AiBi

similarity (A B) = cos 0 = -—-—-—- = —. . -

} IAIM|B" —

There are two main learning models in Word2Vec [9]: Skip-gram and Continuous Bag of Words (CBOW). In the Skip-gram model, words from the context of a single word are predicted, and in the CBOW model, words are predicted as the most probable in the current context. The output layer uses the softmax function, or a variation of it, to output the probability distribution of each word. In both models, the input and output words are given in one-hot encoding, and the result is given as a trained matrix W connecting the input and hidden layers since its rows contain vector representations of words.

5.2 GloVe

GloVe (Global Vectors for Word Representation) [26] is an alternate method to create word embeddings. GloVe is essentially a log-bilinear model with a weighted least-squares objective. The main intuition underlying it is the simple observation that ratios of word-word co-occurrence probabilities can potentially encode some form of meaning. By constructing a matrix of co-occurrence information, GloVe captures both global statistics and local statistics of a corpus[30] in order to come up with word vectors. GloVe uses a weighted least squares objective that minimizes the difference between the dot product of the vectors of two words and the logarithm of their number of co-occurrences. Word co-occurrence probabilities are a 'ratio' used as a word representation.

5.3 Node2Vec

Node2Vec [10] is based on the Word2Vec approach. A graph is first sampled by performing random walks from each node. Authors suggest performing from 32 to 64 random walks of about 40 steps in length. Random walk parameters Q and P define how probable it is that the random walk would discover the undiscovered part

ACAI 2022, December 23-25, 2022, Sanya, China

of the graph and how probable it is that the random walk would return to the previous node. These random walks are then treated as sentences in Word2Vec [27], and a skip-gram model is trained on one-hot encoded nodes to maximize the probability of predicting neighbor nodes. Like in Word2Vec, node embedding is the output of a hidden layer of the network.

5.4 Graph2Vec

Graph2Vec [21] methods are usually based on Doc2Vec [14] and consist of three steps. First, for each node, a sub-graphs of nodes not further than the selected number of edges away is sampled. Then the skip-gram model is trained to maximize the probability of predicting the sub-graph that exists in the graph on the input provided as a one-hot vector. Like in Doc2Vec, another feature vector, which is graph-unique, is added when training embedding vectors. Finally, embeddings are extracted as the result of the hidden layer of the model by providing a graph ID.

5.5 Word2Mat

Word2Mat [24] is a method to represent words as matrices. The main motivation for developing the method was the need to capture the information about the order of words which Word2Vec is not capable of [16]. Word2Mat proposes an approach called Continual Multiplication of Words (CMOW), capable of capturing the word order but inferior to CBOW in capturing word context. Combining CMOW and CBOW, the authors show that the hybrid model performs better than Word2Vec on a large number of tasks.

Word2Mat proposes to model each word as a square matrix rather than a vector and compose multiple word embeddings via matrix multiplication rather than addition. The advantage of this is the non-commutativity of matrix multiplication as opposed to addition, which results in order-aware embeddings. The training objective consists of maximizing the conditional probability of a word in a certain context. The results of the hidden layer represent concatenated columns of the matrix corresponding to a specific word.

6 CLUSTERING

The clustering task has long been very important in the field of data analysis and structuring based on similarity [18]. The idea of clustering is that objects are combined based on their similarity in accordance with the clustering metric into sets of objects called clusters.

Clustering is often used in various tasks of ecology [19], text analysis [22], economics [8], urban studies [25] and others. This approach demonstrates high efficiency, customization flexibility, transparency of the process and results of the algorithm. At the same time, active research and development provide the opportunity to formulate and solve clustering problems on data of various origins.

Embedding techniques make it possible to cluster objects of different origins based on their similarity [36]. Embeddings appeared as an approach for presenting data in a representation form well suited for calculating similarity metrics between objects. That is, embeddings allow to represent objects of any domain or structure in the representation form that makes it possible to use classic metrics to estimate the similarity of these objects.

ACAI 2022, December 23-25, 2022, Sanya, China

Aleksei Pismerov and Maxim Pikalov

Table 2: Experiment results

Embedding method Recall Precision Silhouette

Word2Vec 0.70 0.63 0.58

GloVe 0.74 0.77 0.66

Node2Vec 0.82 0.86 0.69

Graph2Vec 0.79 0.90 0.72

Word2Mat 0.81 0.93 0.76

6.1 Embedding clustering

As part of this work, we propose an approach that uses clustering to search for a set of event chains contained in the event log, which form common clusters based on the similarity metric. Each formed cluster can represent a separate model of the real process from event logs.

Since the description of the events in the dataset is not suitable for similarity estimation, we propose to represent the sequences of process steps as strings, with events being words and event sequences being sentences. This allows us to use word embedding algorithms with no additional steps. We use graph representation

as well since related events are essentially graphs which allows us to use graph embedding methods. Both representations take into account the sequential origin of the data making it possible to capture this information in embeddings.

To calculate the similarity between event sequences, we compare the similarity of the corresponding embedding vectors using similarity metrics described in Section 5. Process models built from clusters include all elements assigned to these clusters and take into account the connections between the stages of the processes taking advantage of representations of the event chains. Therefore we reduce the process mining problem to the problem of clustering embeddings with well-defined similarity metrics.

7 EXPERIMENTS

In order to test the proposed approach, we evaluated the performance of the k-means [12] clustering algorithm on the embeddings of event logs from the dataset described in Section 4. For text embedding methods, we used a representation of the logs where each event was treated as a word and sequences of events were treated as sentences. Since the events in the logs are interconnected and essentially represent a set of graphs, graph embedding methods can be applied without any difficulties. For each embedding method considered in Section 5 we computed embedding vectors of events from the dataset on the size 100.

We compare the performance of embedding clustering as well as the performance of the subsequent process mining. To compare methods used in the study, we use several metrics. We use the silhouette metric to compare the clustering algorithm results. Calculating the distance between objects inside clusters, this metric evaluates the score of the clustering algorithm. To compare the generated process models, we use precision and recall metrics [3]

Results for different embedding methods are presented in Table 2. The table shows calculated recall, precision and silhouette metrics for the clustering of event logs embeddings considered in Section 5 and the process model generation.

Figure 1: Word2Mat clustering results

As seen in Table 2, Word2Mat shows the best results among all the considered embedding methods. Most likely, Word2Mat shows the best results because it captures information about the order of events in event sequences, while other embedding methods only capture the context information.

Based on the results of the experiments, we conclude that Word2Mat is the most suitable algorithm for process mining tasks, so we will demonstrate the results of its work in Figure 1. Figure 1 shows projected results of the clustering of Word2Mat embeddings. We can observe four clusters corresponding to the four types of orders presented in the logs. As can be seen, some processes are clearly separated from others, while elements related to other processes can overlap. The figure, in conjunction with the data of the metrics presented in Table 2 allows us to conclude that the application of embedding methods with clustering algorithms to the process mining problems results in an efficient model with a high level of accuracy which can compete with other approaches.

8 CONCLUSION AND FUTURE WORK

Successful application of embedding methods in modern machine learning problems motivates similar research in the process mining domain. With this work, we evaluate the possibility of applying embedding methods for process mining tasks.

In this study, we applied different embedding methods to the dataset from the International Business Process Intelligence Challenge 2019. Using a clustering algorithm on the embeddings, we managed to separate different processes presented in the logs from each other. The experimental results show that the proposed approach can improve the performance of process mining on large datasets with multiple processes.

Our next goal is to develop a method specially designed for event log embedding. It is also essential to consider how the usage of log field information may affect the performance of our approach [1].

REFERENCES

[1] Jan Niklas Adams, Gyunam Park, Sergej Levich, Daniel Schuster, and Wil MP van der Aalst. 2022. A framework for extracting and encoding features from

Applying Embedding Methods to Process Mining

object-centric event data. In International Conference on Service-Oriented Computing. Springer, 36-53.

[2] Alessandro Berti, Sebastiaan J Van Zelst, and Wil van der Aalst. 2019. Process mining for python (PM4Py): bridging the gap between process-and data science. arXivpreprint arXiv:1905.06169 (2019).

[3] Fabian Rojas Blum. 2015. Metrics in process discovery. Tech. Rep. TechnicalReport TR/DCC-2015-6, Computer ScienceDept., UniversityofChile (2015).

[4] Wojciech W Charemza, Derek F Deadman, et al. 1997. New directions in econometric practice. Books (1997).

[5] Dusanka Dakic, Srdjan Sladojevic, Teodora Lolic, and Darko Stefanovic. 2019. Process mining possibilities and challenges: a case study. In 2019 IEEE 17th International Symposium on Intelligent Systems and Informatics (SISY). IEEE, 000161000166.

[6] Chiara Di Francescomarino, Remco Dijkman, and Uwe Zdun. 2020. Business Process Management Workshops: BPM 2019 International Workshops, Vienna, Austria, September 1-6, 2019, Revised Selected Papers. Vol. 362. Springer Nature.

[7] Cleiton dos Santos Garcia, Alex Meincheim, Elio Ribeiro Faria Junior, Marcelo Rosano Dallagassa, Denise Maria Vecino Sato, Deborah Ribeiro Carvalho, Eduardo Alves Portela Santos, and Edson Emilio Scalabrin. 2019. Process mining techniques and applications-A systematic mapping study. Expert Systems with Applications 133 (2019), 260-295.

[8] Hamed Ghoddusi, Germán G Creamer, and Nima Rafizadeh. 2019. Machine learning in energy economics and finance: A review. Energy Economics 81 (2019), 709-727.

[9] Yoav Goldberg and Omer Levy. 2014. word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method. arXiv preprint arXiv:1402.3722 (2014).

[10] Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 855-864.

[11] Antonella Guzzo,MikelJoaristi, Antonino Rullo, and Edoardo Serra. 2021. Amulti-perspective approach for the analysis of complex business processes behavior. Expert Systems with Applications 177 (2021), 114934.

[12] John A Hartigan and Manchek A Wong. 1979. Algorithm AS 136: A k-means clustering algorithm. Journal of the royal statistical society. series c (applied statistics) 28, 1 (1979), 100-108.

[13] Shilin He, Pinjia He, Zhuangbin Chen, Tianyi Yang, Yuxin Su, and Michael R Lyu. 2021. A survey on automated log analysis for reliability engineering. ACM computing surveys (CSUR) 54, 6 (2021), 1-37.

[14] Quoc Le and Tomas Mikolov. 2014. Distributed representations of sentences and documents. In International conference on machine learning. PMLR, 1188-1196.

[15] Sander JJ Leemans, Dirk Fahland, and Wil MP Van Der Aalst. 2013. Discovering block-structured process models from event logs-a constructive approach. In International conference on applications and theory of Petri nets and concurrency. Springer, 311-329.

[16] Wang Ling, Chris Dyer, Alan W Black, and Isabel Trancoso. 2015. Two/too simple adaptations of word2vec for syntax problems. In Proceedings of the 2015 conference of the North American chapter of the association for computational linguistics: human language technologies. 1299-1304.

[17] Qi Liu, Matt J Kusner, and Phil Blunsom. 2020. A survey on contextual embeddings. arXiv preprint arXiv:2003.07278 (2020).

[18] T Soni Madhulatha. 2012. An overview on clustering methods. arXiv preprint arXiv:1205.1117 (2012).

[19] Abbas Mardani, Huchang Liao, Mehrbakhsh Nilashi, Melfi Alrasheedi, and Fausto Cavallaro. 2020. A multi-stage method to predict carbon dioxide emissions using

dimensionality reduction, clustering, and machine learning techniques. Journal

ofCleanerProduction 275 (2020), 122942.

[20] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781 (2013).

[21] Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. 2017. graph2vec: Learning distributed representations of graphs. arXiv preprint arXiv:1707.05005 (2017).

[22] Aytug Onan. 2019. Two-stage topic extraction model for bibliometric data analysis based on word embeddings and clustering. IEEE Access 7 (2019), 145614-145633.

[23] Abdullahi Sidow Osman. 2019. Data mining techniques. (2019).

[24] Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. 2016. Asymmetric transitivity preserving graph embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 11051114.

[25] Jiaming Pei, Kaiyang Zhong, Jinhai Li, Jiyuan Xu, and Xinyi Wang. 2022. ECNN: evaluating a cluster-neural network model for city innovation capability. Neural Computing and Applications 34, 15 (2022), 12331-12343.

[26] Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). 1532-1543.

[27] Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. 2018. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and

ACAI 2022, December 23-25, 2022, Sanya, China

node2vec. In Proceedings of the eleventh ACM international conference on web search and data mining. 459-467.

[28] Hind R'bigui and Chiwoon Cho. 2017. The state-of-the-art of business process mining challenges. International Journal of Business Process Integration and Management 8, 4 (2017), 285-303.

[29] Pedro L Rodriguez and Arthur Spirling. 2022. Word embeddings: What works, what doesn't, and how to tell the difference for applied research. The Journal of

Politics 84, 1 (2022), 101-115.

[30] Tianze Shi and Zhiyuan Liu. 2014. Linking GloVe with word2vec. arXiv preprint arXiv:1411.5595 (2014).

[31] Wil Van Der Aalst. 2012. Process mining. Commun.ACM 55, 8 (2012), 76-83.

[32] Wil Van Der Aalst. 2012. Process mining: Overview and opportunities. ACM Transactions on Management Information Systems (TMIS) 3, 2(2012), 1-17.

[33] Wil Van der Aalst, Ton Weijters, and Laura Maruster. 2004. Workflow mining: Discovering process models from event logs. IEEE transactions on knowledge and data engineering 16, 9 (2004), 1128-1142.

[34] Wil MP van Der Aalst, Arthur HM Ter Hofstede, Bartek Kiepuszewski, and Alistair P Barros. 2003. Workflow patterns. Distributed and parallel databases 14, 1 (2003), 5-51.

[35] AJMMWeijters, WilMP vanDer Aalst, and AK Alves De Medeiros. 2006. Process mining with the heuristics miner-algorithm. Technische Universiteit Eindhoven, Tech. Rep. WP 166, July 2017 (2006), 1-34.

[36] JunyuanXie, Ross Girshick, and Ali Farhadi. 2016. Unsupervised deep embedding for clustering analysis. In International conference on machine learning. PMLR, 478-487.

Exploratory Landscape Analysis Based Parameter Control

Maxim Pikalov

ITMO University St. Petersburg, Russia

ABSTRACT

Parameter tuning in evolutionary algorithms is a very important topic, as the correct choice of parameters greatly affects their performance. Fitness landscape analysis can help identify similar problems and allow for gathering problem structure insights for fitness-aware optimization algorithm parameter choice.

In this paper, we present an approach to an automatic dynamic parameter control method that uses exploratory landscape analysis and machine learning. Using a dataset of optimal parameter values we collected on different instances of W-model benchmark problem, we trained a machine learning model capable of suggesting parameter values for the (1 + (A, A)) genetic algorithm. The results of our experiments show that the machine learning model is able to capture important landscape features and recommend algorithm parameters based on this information. The comparison results with other tuning methods suggest this approach is more effective than static tuning or heuristics-based dynamic parameter control.

CCS CONCEPTS

• Theory of computation ^ Random search heuristics.

KEYWORDS

Parameter Tuning, Exploratory Landscape Analysis, Black-box Optimization

ACM Reference Format:

Maxim Pikalov and Aleksei Pismerov. 2023. Exploratory Landscape Analysis Based Parameter Control. In Genetic and Evolutionary Computation Conference Companion (GECCO '23 Companion), July 15-19, 2023, Lisbon, Portugal. ACM, New York, NY, USA, 4 pages. https://doi.org/10.1145/3583133.3596364

1 INTRODUCTION

The choice of efficient parameters of evolutionary algorithms is one of the key tasks in the field of metaheuristics application [9]. There are two main approaches to a parameter setting that differ in the frequency of parameter computations.

One group of methods is commonly referred to as parameter tuning and usually involves methods based on the initial evaluation of multiple parameter combinations in search of the best-performing one. Examples of such methods include irace [10] and SMAC [6]. The use of these methods is not always possible due to the restrictions imposed on the number of fitness function evaluations.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [e-mail]. GECCO '23 Companion, July 15-19, 2023, Lisbon, Portugal

© 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 979-8-4007-0120-7/23/07. ..$15.00 https://doi.org/10.1145/3583133.3596364

Aleksei Pismerov

ITMO University St. Petersburg, Russia

Another group is known as parameter control and includes methods based on the choice of parameters directly during the optimization process without prior training. This allows us to configure the parameters more flexibly since they can be changed depending on the current state of the optimization process, which could require certain parameter values [3, 7].

Advances in fitness landscape analysis [12] can help gain insights into a given optimization problem instance, helping to tune metaheuristics for maximum efficiency on a particular problem instance. Exploratory landscape analysis [11] extracts landscape features from intermediate solutions of the optimization problem and the corresponding fitness function values and makes it possible to extract problem information even in the black-box environment.

Exploratory landscape analysis is currently widely used for various tasks [13]. For instance, it has been used for automatic optimization algorithm selection based on landscape analysis and machine learning results or even for dynamic adaptive algorithm selection during the optimization process. We believe that these ideas can also be applied to design a dynamic parameter control method, which selects the algorithm parameters based on the information about the landscape of the current problem.

In this paper, we present our first steps in developing an approach to an automated dynamic parameter control method using landscape analysis techniques and machine learning for a fitness-aware recommendation of effective algorithm parameters. Our proposed approach is to preliminarily collect a dataset of effective algorithm parameters for various landscapes represented by feature vector sequences and then train a machine learning model whose task is to recommend a set of algorithm parameters based on the feature vector sequence of the landscape. Since we are faced with the task of dynamic parameter control, we consider sequences of landscape feature vectors evaluated over the population of the optimization algorithm at different steps of its work.

We collected a dataset oflandscape feature sequences for various instances of the W-model benchmark problem [15] and corresponding optimal parameter values for the (1 + (A, A)) genetic algorithm (GA) [4] with four adjustable parameters. For landscape feature extraction, we use the flacco package in R [8], which is capable of calculating various landscape features for a population of individuals with known fitness function values. We train the neural network on the collected dataset, and with its help, we can then recommend the following (1 + (A, A)) GA parameters based on the sequence of landscape features evaluations from the previous iterations of the algorithm. Our model can recommend algorithm parameters for different optimization problem instances as long as we can compute their fitness landscape features.

The results of experiments on various instances of the W-model problem suggest that the proposed parameter control approach based on landscape analysis is capable of determining effective parameters of the (1 + (A, A)) GA since the algorithm with the

2378

GECCO '23 Companion, July 15-19, 2023, Lisbon, Portugal

Maxim Pikalov and Aleksei Pismerov

n ^ problem size

X\ ^ mutation phase population size X2 ^ crossover phase population size k ^ mutation coefficient c ^ crossover probability Initialize: x ^ uniformly from {0,1}n for t ^ 1, 2, 3,... do I ~ B{n, k/n)

for i e 1, 2,..., A1 do > Phase 1: Mutation

flip I uniformly chosen bits in x

end for

x' ^ uniformly from {x() | f (x()) = max{/(x(i))}} for i e 1, 2,..., A2 do > Phase 2: Crossover

for j e 1, 2,..., n do

yj') ^ x'. with probability c, otherwise Xj end for end for

y ^ uniformly from {y ( ) | f (y ( )) = max{ / (y(i ))}} if f (y) > f (x ) then

x ^ y end if end for

> Selection

parameters suggested by our method turns out to be more efficient than other considered methods of dynamic parameter control methods of the (1 + (A, A)) GA.

2 PRELIMINARIES

2.1 (1 + (A,A)) GA

The (1 + (A, A)) genetic algorithm [4] employs a two-phase approach to explore the search space. The first phase utilizes high mutation rates to conduct an extensive search. In the second phase, a crossover mechanism is implemented to counteract any negative effects that the high mutation rates may have on individuals. In this study, we focus on the (1 + (A, A)) GA, which has four parameters {Ai, X2, k, c}, similar to the one examined in [2]. Algorithm 2.1 provides the pseudocode of the algorithm, which operates as follows:

• at the first stage of every iteration, the algorithm employs the mutation operator with a mutation rate of k/n to create A1 mutant individuals;

• the mutant individual with the highest fitness is chosen to

perform a crossover with the parent individual;

• the second phase involves generating A2 individuals using the crossover operator, which selects bits from the mutant individual based on a probability of c;

• if the top-performing individual produced by the crossover operation is better than the parent individual, it replaces the parent;

• the aforementioned process is iterated until the optimal solution is discovered.

In our experiments, we utilize the generic version of the (1 + (A, A)) GA introduced in the publication by Bassin and Buzdalov [1].

2.2 W-Model Benchmark Problem

The W-model problem [15] is a benchmark optimization problem that can be configured according to specific requirements. It includes multiple customizable layers that modify the problem's fitness landscape, making it appropriate for a range of benchmarking purposes. These tunable layers of the W-model problem consist of:

• neutrality: this layer creates regions within the fitness landscape with equivalent fitness values;

• epistasis: this layer introduces a dependence among different genes in an individual, affecting the overall fitness value;

• ruggedness: this layer adds uneven terrain to the fitness landscape, with peaks and valleys of fitness values;

• dummy: this layer includes variables that have no impact on the fitness of an individual, therefore can be considered irrelevant.

For this study, we utilized the C++ implementation of the W-model problem over the OneMax problem on binary strings. This implementation was taken from the IOHProfiler [5].

2.3 Landscape Analysis

Flacco [8] R-package is widely used for analyzing fitness landscapes based on their features. It offers an array of tools for feature evaluation, analysis, and visualization. In this study, we utilize three different feature sets:

• Level-Set: The feature set is generated by training classifiers, namely LDA (Linear Discriminant Analysis), QDA (Quadratic Discriminant Analysis), and MDA (Mixture Discriminant Analysis), on a given set of candidate solutions. These classifiers predict whether the fitness value is below a specific threshold. The resulting features are represented by the mean misclassification errors for each classifier calculated during cross-validation.

• Meta-Model: The feature set is obtained by constructing linear and quadratic models that approximate the objective function using samples of candidate solutions. This feature set is represented by various values, including the adjusted R2 of linear and quadratic models, the smallest and largest absolute coefficients of the models, and their ratios. These features aim to approximate the problem's structure and complexity using analytical functions and identify the relationship between variables.

• Y-distribution: The feature set is generated by estimating the density of candidate solutions using a kernel-based method and computing various statistics, such as the number of peaks, skewness, and kurtosis. These features provide an overall understanding of the landscape's shape and offer a deeper insight into its characteristics. They also enable the identification of areas with high neutrality, ruggedness, and plateaus in the search space.

3 EXPERIMENTS 3.1 Dataset

We collected a dataset of the average runtime of the parameterized (1 + (A, A)) GA presented in Section 2.1 with different parameters

2379

Parameter Control

and at different iterations on various W-model instances for the subsequent training of our model.

For the (1 + (A, A)) genetic algorithm we consider the following parameters:

• A! e [2, 3,4,..., 9];

• A2 e [2, 3,4,..., 9];

• fc e [1, 3, 5, 7, 9];

• c e [0.01,0.03, 0.05, 0.07,0.09].

We consider all possible combinations of (1 + (A, A)) GA parameters and compute the average runtime on all W-model instances with the parameters:

• n e [8,16, 32, 64,128];

• dummy e [1,1 - 1/«, 1 - 2/rc,..., 0.8];

• neutrality e [0, 1, 2,..., n X 0.2];

• epistasis e [0,1,2,3].

Note that some of these values were chosen because we wanted to collect the dataset with problem instances of different landscapes in a reasonable time. Turns out, high epistasis values lead to a significant increase in the (1 + (A, A)) GA runtime. As for the ruggedness parameter value, we left it unchanged since it does not correlate with landscape complexity.

So, we run the (1 + (A, A)) GA 25 times for each pair of W-model parameters {rc, dummy, neutrality, epistasis} and (1 + (A, A)) GA parameters {Ax, A2, fc, c}. We consider the parameters with the lowest mean runtime as the best parameters of the corresponding problem instance landscape.

3.2 Landscape Features

For real-life problems, we do not have parameters as we do in the W-model problem; therefore we use landscape analysis methods to get information about the given optimization problem. To increase the amount of the collected data for training the machine learning model, considering that evaluated feature values are random in nature, we evaluate 25 feature vectors of 35 flacco features for each instance of the W-model problem. Each feature vector is evaluated over 10 individuals, which are taken into account in further calculations of the algorithm budgets. We reuse individuals evaluated for the feature vector calculations in the algorithm, and we initialize the optimization process with the best individual observed during the initial feature evaluation.

We train the machine learning model capable of suggesting parameter values for a given set of landscape features on a dataset of best (1 + (A, A)) GA parameters for certain fitness landscapes features ^ {A1, A2, fc, c} combined from features and performance data results.

3.3 Machine Learning Model

Considering several options for machine learning models and architectures, we decided to focus on FNN (Feedforward Neural Network) with two hidden layers: 32 and 16 nodes, respectively. For the optimization algorithm, we chose Adam, which performed better than SGD (Stochastic Gradient Descent) and Limited-memory BFGS (Broyden-Fletcher-Goldfarb-Shanno algorithm). As an activation function, we used ReLU (Rectified Linear Unit) with a constant learning rate of 10-3 and a regularization parameter of 10-4.

GECCO '23 Companion, July 15-19, 2023, Lisbon, Portugal

We also considered several options for training the model on sequences of landscape features. In the first option, all sequences had the maximum trace length, and padding was applied for the missing elements. In the second option, we used a sliding window of 25, training the model on the last 25 elements of the trace. The latter model proved to be the best, so it was chosen as the final model.

3.4 Benchmarking

To check whether the suggested parameter selection approach is effective, we assessed how well the (1 + (A,A)) GA performed when using the recommended parameter values on various instances of the W-model problem.

We conducted a performance comparison between the algorithm using the suggested parameter values, referred to as (1 + (A, A)) GA tuned, and several variations of the (1 + (A, A)) GA algorithm available in the generic (1 + (A, A)) GA repository.

• (1 + (A, A)), A = 4: (1 + (A, A)) GA with default parameter choices A2 = A1, fc = A1, c = 1/A1 for A1 = 4;

• (1 + (A,A)),A < 2 ln n and (1 + (A,A)),A < n: (1 + (A,A)) GA with dynamic A tuned according to the 1/5-th rule with the listed upper bound on A;

• (1 + (A,A)),A ~ pow(2.5) the (1 + (A, A)) GAwith A sampled from the power-law distribution with p = 2.5;

Additionally, we analyzed the set of parameters from the training dataset that demonstrated the best overall performance out of all available parameter sets. The specific parameter values are Ai = 2, A2 = 2, fc = 8, c = 0.02 and we refer to the (1 + (A, A)) GA algorithm using these parameters as (1 + (A, A)), single best.

We utilized the W-model problem instances with sizes of n = 256 and n = 512 for the experimental evaluation. It's important to mention that the neural network only had data for n < 128 during training. The dummy, neutrality, and epistasis parameters were chosen from ranges similar to those in the performance dataset. We generated 25 distinct sets of landscape features for each problem instance, and for each feature set, we calculated the suggested parameters for the (1 + (A, A)) GA algorithm by utilizing the trained neural network.

We present the performance data for n = 256 in Table 1 and for n = 512 in Table 2. The tables show the average rank, the standard deviation of the rank, and the mean difference in runtime compared to the optimized (1 + (A, A)) GA, measured in fitness evaluations, for each algorithm. A negative difference would indicate that the algorithm performs better than our method, while a positive difference value shows the opposite. We recalculate algorithm parameters every 25 iterations based on the landscape data from the previous iterations.

Upon analyzing the results, it becomes apparent that the optimized (1 + (A, A)) GA is, on average, the highest-ranked algorithm out of all the variations of the (1 + (A, A)) GA that were considered. The fitness-aware parameter selection method proves to be superior to (1 + (A, A)), A = 4 parameter values tuned according to the one-fifth rule or power-law distribution. We can infer from the significant discrepancy in performance between the tuned (1 + (A, A)) GA and (1 + (A, A)) GA based on the one-fifth rule or the power-law

2380

GECCO '23 Companion, July 15-19, 2023, Lisbon, Portugal Table 1: Comparison of algorithms' performance n = 256

Algorithm Mean rank Rank SD Mean diff

(1 + (A, A)), tuned 3.25 1.38 0

(1 + (A, A)), single best 3.79 1.92 89.53

(1 + (A, A)), A ~ pow(2.5) 4.05 1.45 63.57

(1 +(A,A)),A = 4 6.43 1.09 318.05

(1 + (A,A)),A < n 6.62 1.52 1970.51

(1 + (A, A)), A < 2/«« 6.76 1.41 2046.35

Table 2: Comparison of algorithms' performance n = 512

Algorithm Mean rank Rank SD Mean diff

(1 + (A, A)), tuned 2.92 1.69 0

(1 + (A,A)),A < n 3.45 1.95 197.92

(1 + (A,A)),A < 2lnn 3.78 1.18 210.85

(1 +(A,A)),A = 4 4.73 0.83 404.62

(1 + (A, A)), A ~ pow(2.5) 6.09 0.51 698.42

(1 + (A, A)), single best 7.71 0.52 1301.72

distribution that the neural network can learn parameter choices dependent on the landscape features.

Furthermore, we analyzed performance results for distinct W-model parameter values to better understand the trained model and our suggested approach's strengths and limitations. To achieve this, we grouped the parameter values into intervals and compared the average rankings of various algorithms on the corresponding W-model cases, as well as the average differences in the number of function evaluations.

We divided the neutrality and dummy parameter values into groups of 5, and upon analysis, we found that our proposed approach performs exceptionally well on W-model cases with low or moderate neutrality values (< 40), with an average rank of approximately 2.5. However, in instances with high neutrality values (> 50), the single best (1 + (A, A)) GA and power-law (1 + (A, A)) GA algorithms manage to catch up to our approach, with an average rank of 3.8 and 3.7, respectively, while our solution has an average rank of 3.4. When analyzing the dummy W-model parameter intervals, we found contrasting results compared to the neutrality values. Our proposed approach yields the best outcomes on W-model cases with moderate or high dummy parameter values (> 30), with an average rank of 2.5. In contrast, the single best and power-law (1 + (A, A)) GA algorithms perform better on W-model cases with low dummy values (< 20), with average ranks of 3.8 and 3.9, respectively, while our approach has an average rank of 3.3.

4 CONCLUSION AND FUTURE WORK

The successful utilization of exploratory landscape analysis and machine learning techniques for algorithm selection and static parameter tuning inspires further research in the domain. In this study, we take the first step towards automating dynamic parameter selection for discrete optimization problems using fitness landscape analysis and neural networks.

In this work, we gathered a dataset of the best parameter values for the (1 + (A, A)) GA on different instances of the W-model problem. We used this dataset to train a neural network to choose the

Maxim Pikalov and Aleksei Pismerov

best parameters for the (1 + (A, A)) algorithm for a specific optimization problem instance. Our tests showed that this landscape-aware approach can help find good parameter settings for the (1 + (A, A)) GA.

For future work, it is crucial to conduct additional testing of the proposed method on different optimization problems and try it with other optimization algorithms. By doing so, we can improve the training data by examining problems with unique landscapes that the W-model does not cover. We need to consider how the utilization of certain individuals can impact the effectiveness of our approach since landscape features were shown to be sensitive to the sampling strategy [14]. Furthermore, we plan to explore the appropriate frequency at which algorithm parameters should be modified.

REFERENCES

[1] Anton Bassin and Maxim Buzdalov. 2020. The (1 +(A,A)) Genetic Algorithm for Permutations. In Proceedings of Genetic and Evolutionary Computation Conference Companion. ACM, 1669-1677.

[2] Nguyen Dang and Carola Doerr. 2019. Hyper-Parameter Tuning for the (1 + (Ä, Ä)) GA. In Proceedings of Genetic and Evolutionary Computation Conference. 889-897.

[3] Benjamin Doerr and Carola Doerr. 2020. Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Springer, 271-321. Also available online at https://arxiv.org/abs/1804.05650v2.

[4] Benjamin Doerr, Carola Doerr, and Franziska Ebel. 2015. From black-box complexity to designing new genetic algorithms. Theoretical Computer Science 567 (2015), 87-104.

[5] Carola Doerr, Hao Wang, Furong Ye, Sander van Rijn, and Thomas Bäck. 2018. IOHprofiler.A Benchmarking and Profiling Tool for Iterative Optimization Heuristics. https://arxiv.org/abs/1810.05281 IOHprofiler is available at https://github.com/ IOHprofiler.

[6] Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. 2011. Sequential modelbased optimization for general algorithm configuration. In Proceedings of Learning and Intelligent Optimization. Springer, 507-523.

[7] Giorgos Karafotias, Mark. Hoogendoorn, and Ágoston E. Eiben. 2015. Parameter Control in Evolutionary Algorithms: Trends and Challenges. IEEE Transactions

on Evolutionary Computation 19, 2 (2015), 167-187.

[8] Pascal Kerschke and Heike Trautmann. 2016. The R-package FLACCO for exploratory landscape analysis with applications to multi-objective optimization

problems. In 2016 IEEE Congress on Evolutionary Computation (CEC). IEEE, 52625269.

[9] Fernando G. Lobo, Cláudio F. Lima, and Zbigniew Michalewicz (Eds.). 2007. Parameter Setting in Evolutionary Algorithms. Number 54 in Studies in Computational Intelligence. Springer.

[10] Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Leslie Pérez Cáceres, Thomas Stüt-zle, and Mauro Birattari. 2016. The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives 3 (2016), 43-58.

[11] Olaf Mersmann, Bernd Bischl, Heike Trautmann, Mike Preuss, Claus Weihs, and Günter Rudolph. 2011. Exploratory landscape analysis. In Proceedings of the 13th annual conference on Genetic and evolutionary computation. 829-836.

[12] Olaf Mersmann, Mike Preuss, and Heike Trautmann. 2010. Benchmarking evolutionary algorithms: Towards exploratory landscape analysis. In International Conference on Parallel Problem Solving from Nature. Springer, 73-82.

[13] Gabriela Ochoa and Katherine Malan. 2019. Recent Advances in Fitness Landscape Analysis. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (Prague, Czech Republic) (GECCO '19). Association for Computing Machinery, New York, NY, USA, 1077-1094. https://doi.org/10.1145/3319619. 3323383

[14] Quentin Renau, Carola Doerr, Johann Dreo, and Benjamin Doerr. 2020. Exploratory landscape analysis is strongly sensitive to the sampling strategy. In International Conference on Parallel Problem Solving from Nature. Springer, 139153.

[15] Thomas Weise and Zijun Wu. 2018. Difficult Features of Combinatorial Optimization Problems and the Tunable W-Model Benchmark Problem for Simulating

them. In Proceedings of Genetic and Evolutionary Computation Conference Companion. 1769-1776.

2381

ISSN 1995-0802, Lobachevskii Journal of Mathematics, 2025, Vol. 46, No. 5, pp. 2410-2424. © Pleiades Publishing, Ltd., 2025.

Boosting Exploration in Reinforcement Learning Agents via Path-Based Knowledge Graph Reasoning

A. M. Pismerov1* and D. I. Mouromtsev1**

(Submitted by E. K. Lipachev)

1ITMO University, St. Petersburg, 197101 Russia Received November 21, 2024; revised March 12, 2025; accepted March 22, 2025

Abstract—This paper proposes and presents a novel methodology for enhancing the exploration process in reinforcement learning algorithms, based on applying an optimal path search algorithm on a knowledge graph. Traditional approaches in the exploration phase used in agent-based models often rely on random and probabilistic strategies, which may prove inefficient in complex and dynamic environments. This work introduces an alternative approach that leverages structured information from a knowledge graph to identify and select the most promising actions. The methodology includes a path-based reasoning module that uses the knowledge graph to determine suitable action directions for the agent. Experimental results indicate that the proposed method improves agent performance in complex, dynamic environments with non-deterministic action sets, demonstrating superior results in tasks with complex knowledge structures and high adaptation requirements.

2010 Mathematics Subject Classification: 68T42, 68Q32, 68T20. DOI: 10.1134/S1995080224607896

Keywords and phrases: accelerating the convergence, reinforcement learning algorithm, path-based reasoning, knowledge graphs

1. INTRODUCTION

Reinforcement Learning (RL) has become one of the leading fields in artificial intelligence due to its unique ability to train agents in performing complex actions under uncertainty. This method is inspired by the natural learning process where organisms develop skills based on experience and feedback from their environment. In RL, an agent learns to make decisions by interacting with the world and gradually adjusts its actions to maximize received rewards. This approach makes RL a versatile tool for solving a wide range of tasks—from the gaming industry to autonomous control.

One of the most striking examples of RL's success has been breakthroughs in gaming, especially in strategy and board games that require deep analysis. Landmark achievements, such as AlphaGo's victory over the world champion in Go, showcased to the world the incredible capabilities of reinforcement learning in tasks that demand not only computational power but also strategic thinking. Beyond gaming, RL is also actively used in robotics, where its ability to "learn" appropriate actions helps robots adapt to the real world with its inherent variability. Robots trained with RL can perform complex tasks such as object grasping, manipulation, and even navigation in obstacle-filled environments.

The popularity of RL is also driven by its potential applicability to real-world, practical tasks. For instance, in the financial sector, RL can be used to develop algorithms that optimize investment strategies based on market analysis and dynamically changing information. In medicine, RL is utilized to optimize treatment plans and create decision-support systems capable of considering multiple variables for individual patients. Reinforcement learning enables agents to develop adaptive strategies that would

E-mail: [e-mail]

E-mail: [e-mail]

be challenging to program using traditional methods, making it a powerful tool in any field where flexibility and autonomous learning are important.

However, like other approaches, RL faces a number of challenges when applied to certain classes of tasks, particularly those with limited data or significant delays in rewards. These limitations significantly affect the quality and stability of RL performance, especially in complex fields such as real-world robotics control, financial trading, and medical applications, where errors can be costly. For example, in the control of robots and drones, RL encounters the problem of expensive interactions-each action taken by the agent incurs resource costs and risks physical wear and tear. The training process, which requires numerous iterations, can become impractical or overly expensive. In domains like medicine, where RL is used, not only are resources costly, but there is also the danger of harming patients. Another example is the use of RL in trading, where obstacles also arise. Financial data can be noisy and unpredictable, and a strategy that worked once might not replicate in the future. Additionally, in long-term planning tasks where rewards come after a significant delay, such as strategic planning in chess, RL models often struggle to find correlations between actions and outcomes.

Understanding these problems and methods for addressing them can significantly enhance the applicability of RL to real-world tasks. One approach to mitigating RL's shortcomings is data injection, which helps address data scarcity or limited access to environments. This approach is effective in tasks involving hard-to-access or costly data, such as robotics, medicine, and financial modeling. Data injection involves providing the model with additional information collected outside the current environment, which helps accelerate learning, improve robustness, and reduce the risk of overfitting when data is limited.

One prominent example of data injection is simulation. Instead of relying on the physical world for training, many RL models are trained in virtual simulations [1], where mistakes do not cause damage, and the agent can collect experience much faster. A notable example is the approach used by OpenAI [2], which trained a robotic hand to manipulate objects through simulations. The simulation data were then "injected" into the real world, helping the hand adapt to real environments and tasks. In trading, synthetic data are used to simulate various market conditions [3] that the model may not encounter in historical data. This technique allows the agent to train on rare but significant events, such as sudden price changes. The use of data injection greatly expands the possibilities of RL in areas where direct training in the environment is impossible or undesirable. Another method of data injection in RL is the use of knowledge graphs [4], which significantly enhance the model's adaptability, allowing the agent to make more informed decisions based on structured information. This approach helps the agent effectively generalize knowledge and adapt faster to new conditions by utilizing the relationships and dependencies between entities represented in the graph. As a result, the model becomes more robust in tasks with large state spaces and less dependent on unknown environment data, reducing training costs and improving decision accuracy. While RL is actively applied across many fields and industries, its use often remains resource-intensive and narrowly focused on specific tasks. In medicine or robotics, developing RL algorithms is costly and tailored to particular systems. However, there are environments with similar characteristics and requirements for the approaches used to solve them. One such class of tasks is text-based games. Their simplicity of implementation and convenience for training and testing agents make text-based games an excellent benchmark for RL methods. They require no financial costs, special equipment, or environment, do not pose risks to others, and enable an objective assessment of the effectiveness of developed methods.

Text-based games represent a unique class of tasks [5], where an agent interacts with the environment through text commands and receives text-based responses. These tasks, despite their apparent simplicity, require a complex combination of skills from the participant: natural language understanding, decision-making under uncertainty, and multi-step planning [6].

Solving tasks in text-based environments is relevant for several reasons. Firstly, such games often simulate real-life situations where the player needs to work with textual information, for example, in automated question-answering systems or virtual assistants. Secondly, methods that demonstrate successful solutions for text-based games can be transferred to other areas, such as dialogue management and decision-making tasks [7].

Existing methods for solving tasks in text-based environments can be broadly divided into two groups: symbolic approaches and machine learning-based methods. Symbolic methods often involve the use of grammars and rules that allow the agent to analyze and generate text commands. However,

such approaches are often inflexible and struggle with the diversity of natural language. Machine learning methods, particularly deep learning, have significantly improved results in solving text-based tasks [8]. Among them, sequence-based models, such as LSTM and transformers, stand out as they enable agents to consider context and predict the most likely actions. However, despite their success, such models often require large amounts of data and computational resources.

2. TEXT-BASED GAMES

Text-based games, or interactive fiction (IF), represent a unique category of interactive entertainment where the entire interface is based on text messages. In these games, the player interacts with the game environment by entering text commands, and the game responds with text messages describing the events and changes in the environment, as well as providing information about the player's status. These games have a rich heritage, beginning with the first computer games like "Adventure" and "Zork" and continue to evolve to this day.

The main components of text-based games include: text descriptions of the environment, characters, objects, and interactions, as well as a command input system. The player enters commands such as "look at the room" or "take the key", and based on these commands, the game changes the state of the world and provides corresponding text responses. An important element is interactivity: the player's actions directly influence the events occurring in the virtual world, thus creating a nonlinear storyline and a variety of possible paths for progression.

The significance of text-based games for the field of machine learning is due to their demands on various skills of the agent. First, successfully completing such games requires a deep understanding of natural language. The agent must not only parse text descriptions and commands but also be able to generate meaningful responses. Second, text-based games often include elements of logical puzzles and planning. Consequently, the agent must make decisions under uncertainty, plan its actions ahead, and adapt to changing conditions based on its actions. Text-based games can be classified into several types, each of which imposes its own requirements on the agents:

1. Adventure games

Games of this type focus on world exploration and puzzle-solving. Players explore different locations, collect items, and interact with characters to progress through the storyline. Examples include games like "Zork" and "The Hitchhiker's Guide to the Galaxy".

2. Role-playing games (RPG)

In these games, the player controls one or more characters, develops their abilities, and participates in battles. A classic example is "MUD" (Multi-User Dungeon), where players interact with other players in text mode.

3. Interactive stories

These games focus on the storyline and characters, giving the player the ability to make decisions that affect the development of the story. Examples include "80 Days" and "Choice of Robots".

4. Puzzles and quests

Games that focus on solving puzzles. Players must use logic and ingenuity to progress through the game. Examples include "Counterfeit Monkey", "Coin collector".

The interest in text-based games can be explained by several factors. First, text-based games offer a rich and diverse experience that is difficult to replicate in other formats. They require the player (or agent) to apply creativity, analyze situations, and engage in mental effort to solve problems and achieve goals. Second, they provide an ideal testing ground for verifying and improving natural language processing and reinforcement learning methods, given the complexity of their solutions. Agents need to understand the context, generate meaningful commands, and adapt to dynamic changes in the game, which makes these tasks quite challenging and interesting for researchers in the field of machine learning.

Interest in text-based interactive games has been revived in recent years in the context of research in artificial intelligence (AI). These games provide an appropriate platform for developing and testing

natural language processing algorithms, action planning, reinforcement learning, and similar methods. However, despite significant progress, solving text-based games remains a challenging task.

The main difficulty of text-based interactive games lies in the need for understanding and interpreting text, which in itself is one of the most complex tasks in natural language processing. Unlike classical games with clearly defined rules and a limited number of possible actions (such as chess or go), text-based games require the system to understand the entire context and knowledge of the environment described through text. This leads to challenges in syntactic and semantic text analysis, extracting meaningful information, and making decisions based on incomplete or multi-tasking data.

An additional challenge is the need to generate the player's own text commands that are contextually appropriate for the game. This requires algorithms not only to passively understand the text but also to actively participate in a text-based dialogue with the game. This task is further complicated by the fact that the possible actions of the player in such interactive games are typically not limited to a small set of commands and require a creative approach to problem-solving. For example, in some games, achieving goals may require using unconventional combinations of items or commands, which demands a high degree of adaptability and the ability to generate previously unused solutions.

Moreover, text-based games often contain narrative elements that imply the need for long-term planning and remembering previous actions and events. Unlike most other games, where strategies based on rules are used, text-based interactive games require the system to have the ability to maintain a dialogue with the game engine and adapt to changing game conditions, making them an ideal testing ground for models with long-term memory and complex decision-making strategies.

The development of approaches to solving text-based games has several important motivations that determine the relevance and prospects of this field.

First, successfully solving text-based interactive games requires a synergy of various approaches, such as natural language processing, planning, text generation, and reinforcement learning. In other words, games of this class provide researchers with a unique opportunity to integrate and test interdisciplinary approaches, which contributes to the development of new technologies and methodologies.

Second, solving text-based interactive games is directly related to the development of approaches that enable deeper interaction with humans. Successful algorithms developed for IF games can be applied in various fields, such as virtual assistants, intelligent decision-support systems, as well as the development of new forms of interactive entertainment and educational applications.

Third, text-based games allow for the exploration and development of methods capable of adaptive behavior in conditions of uncertainty and the need for long-term planning. This opens up new prospects for creating more intelligent and flexible systems capable of functioning effectively in complex and changing environments.

Thus, the motivation for researching approaches to solving text-based interactive games is based on their unique ability to combine various tasks, such as natural language processing, planning, and reinforcement learning. These games provide an ideal platform for developing and testing innovative algorithms capable of more complex forms of interaction and decision-making.

3. OVERVIEW OF EXISTING RESEARCH

Since the publication of Mnih et al. [9], which introduced the approach of using reinforcement learning for playing Atari games, there has been a significant increase in interest in applying this approach to other tasks of a similar nature. One subset of such tasks is text-based games. The need to interact with the environment using natural language presents researchers with new challenges, requiring consideration of the complexities of applying NLP, such as Narasimhan, Kulkarni, and Barzilay's LSTMDQN [8] or He et al.'s adjusted DRRN [10].

As a result of these works, models using long short-term memory for the Q-function were introduced. Later, a modification was proposed consisting of two independent models for encoding context and commands, which use a pairwise interaction function to calculate Q-values. Research on DQN approaches continued, but a significant breakthrough in solving such tasks was demonstrated by the approach using A2C as the main method. Despite all the progress, solving TextWorld games still demonstrated insufficient convergence speed due to the vast action space arising from the use of natural language as an interaction tool (Ammanabrol and Riedl 2020 [11]). For large action spaces, various

approaches were proposed, such as the Action Eliminating Network (AEN), which limits the number of potential actions to the most likely ones, using the reward from the emulator for ranking.

The works of Ammanabrol et al. [12] demonstrated that knowledge graphs, which allow representing knowledge as structured historical information, are useful for working in environments with partial observability. Approaches for integrating RL with KG (Knowledge Graphs) were presented. Thus, this approach helped mitigate some of the shortcomings of RL agents in this class of tasks by leveraging knowledge of observations stored in the knowledge graph. The work by Murugesan et al. [13] showed that using knowledge graphs improves the performance of reinforcement learning by enabling its hierarchical learning. In other words, agents applied to text-based games can be divided into two classes. The first class includes agents whose main idea is the application of rules, heuristics, and expert knowledge. The second class uses RL to adapt the agent during the solution of game tasks. With these approaches, the first class faces the problem of rigid constraints on flexibility, while the second class shows poor performance in complexly modeled environments. The use of agents with knowledge graphs serves as a compromise, which implies using structured knowledge and avoiding various limitations.

In addition to demonstrating their effectiveness in improving the performance of agents for text-based games by providing structured and historical information, knowledge graphs (KG) have their own potential for significant enhancement through the use of path-based reasoning approaches Wenqiang Lei [14]. These approaches allow for more efficient extraction and utilization of information from graphs by analyzing connections and paths between nodes.

Path-based reasoning approaches enable drawing conclusions and making decisions based on sequences of related events and objects represented in the knowledge graph. This helps to better understand the context and consequences Zhaocheng Zhu [15].

4. REINFORCEMENT LEARNING IN TEXT-BASED GAMES

Recently, there has been growing attention towards reinforcement learning methods. Reinforcement learning algorithms have shown high effectiveness in tasks where an agent needs to make decisions under uncertainty and learn based on interactions with the environment through observations of its state.

Reinforcement learning is an approach in which an agent learns to interact with the environment through successive trial and error. The agent makes decisions based on the current state of the environment and receives feedback in the form of rewards or penalties. The main goal of the agent is to maximize the accumulated reward by improving its decision-making strategy. In the context of text-based interactive games, such as text adventure games, reinforcement learning finds particular application as it requires the agent to understand natural language, plan, and make decisions under uncertainty.

As described earlier, text-based interactive games represent complex environments where the agent must interact with the surroundings using text commands. This creates unique challenges for reinforcement learning algorithms, as the agent needs to interpret text descriptions of the game state and formulate actions based on them to achieve the game's goal. The learning process in such an environment can be divided into several key stages.

The first step is defining the environment and the states that the agent will perceive. In text-based games, states are described through text, which outlines the current situation, the environment, characters, and available actions. The agent needs to learn to recognize the important elements of these descriptions and correctly interpret them to form an accurate understanding of the current game state. This requires the use of natural language processing models capable of extracting relevant information from the text.

The next step is formulating the possible actions. In each situation, the agent can choose from a limited set of commands available to it at that moment. These commands can include actions like "examine" "take item" "talk to a character" and so on. An important aspect here is the agent's ability to match the text-based description of the state with the appropriate commands. To achieve this, text generation methods or libraries of predefined commands are often used, which the agent must learn to apply in the correct context.

The third step is the selection of a strategy, which defines how the agent will act in the long term. In text-based games, the agent often needs to not only solve tasks but also plan its actions, taking

into account future consequences. The strategy should be flexible and adaptive so that the agent can successfully handle various gaming situations, especially in conditions of uncertainty and incomplete information.

The evaluation of actions through rewards is another crucial aspect of reinforcement learning. Each action taken by the agent leads to specific consequences, which affect its further progress in the game. The reward can be positive if the action brings the agent closer to its goal, or negative if it leads to undesirable outcomes. The main task of the agent is to learn to maximize the total reward by making optimal decisions at each step. The process of learning and adaptation allows the agent to gradually improve its abilities. Based on accumulated experience, the agent adjusts its strategy, making it more effective. In text-based games, this process can be especially challenging due to the need to consider a wide range of possible states and actions.

In recent years, several approaches have been proposed for applying reinforcement learning (RL) in text-based games. One of the most well-known examples is the previously mentioned work by researchers from Facebook AI Research, who developed the Text-based Adventure Reinforcement Learning (TARL) system. In this system, the agent was trained to play the game Zork. TARL uses deep neural networks to process the textual descriptions of game states and select the most appropriate actions. The model was trained using Q-learning, which allowed the agent to gradually improve its strategy based on the rewards received. The main advantage of this approach was that the agent could learn directly from raw text data, without the need to manually develop rules for interpreting the text. However, one of the challenges faced by the researchers was the high computational complexity involved in processing textual data and training deep networks. Despite this, TARL demonstrated that agents can effectively learn in text-based games, achieving good results in complex scenarios.

Another prominent example is the Jericho system, which serves as a platform for exploring text-based games using various reinforcement learning methods. A key feature of this system is its ability to interact with a wide range of text-based games. Jericho provides tools for automatically extracting information from texts and generating action sets, significantly simplifying the process of creating agents for text-based games. This flexibility makes it easier to experiment with different models and techniques, enabling researchers to advance the development of agents capable of effectively navigating diverse interactive fiction environments.

One of the outcomes of working with Jericho was the development of the DRRN (Deep Reinforcement Relevance Network) agent. In DRRN, the agent uses a deep neural network to map text descriptions of the game state to a list of possible actions. The network is trained using Q-learning, but with one key difference: the agent learns to differentiate between relevant actions for a given state. This improves the agent's ability to make more meaningful decisions in environments with an infinite number of possible actions. DRRN demonstrated significant improvement over simpler approaches, although researchers noted that it is still limited in complex gaming scenarios due to the difficulty of processing long and intricate texts.

Equally important is the LSTM-DQN agent approach [16]. This system used a recurrent neural network (LSTM) to process sequences of text descriptions, allowing the agent to take into account previous game states when selecting actions. Unlike classical Q-learning, Double DQN was applied here, which reduced the overestimation of action values and helped the agent avoid local optima.

Another important example of reinforcement learning applied to text-based interactive games is the use of the Advantage Actor-Critic (A2C) method [17], which has been adapted for text-based games. A2C is an enhanced version of the classical Actor-Critic algorithm, where two models are trained simultaneously: the actor, responsible for selecting actions, and the critic, which evaluates the quality of these actions.

In this implementation, the agent was trained to select text commands based on textual descriptions of the game state, with both the actor and the critic being updated synchronously, which helped improve training stability and reduced the risk of overfitting. The application of A2C allowed the agent to more efficiently utilize the reward information received for actions and find optimal strategies in text-based games more quickly. One of the main advantages of A2C in the context of text-based games is its ability to learn in high-uncertainty conditions and complex game scenarios. This method also proved to be more computationally efficient compared to other approaches, such as DQN, as the synchronous updating of the actor and critic allows for better management of the learning process and faster convergence to the optimal strategy. Despite these advantages, A2C also has its limitations. For

example, it requires careful tuning of hyperparameters and can be sensitive to the quality of the input data, particularly in games with long textual descriptions and a large number of possible actions.

These examples demonstrate that reinforcement learning has already made significant strides in the field of text-based games, offering solutions capable of effectively handling text data and complex scenarios. However, each of these approaches faces unique challenges, such as the need for large datasets, computational costs, and difficulties in processing long textual sequences. Additionally, all of these methods encounter the typical "Exploration vs Exploitation" challenge common to all RL models.

The application of reinforcement learning in text-based games allows agents to adapt to changes in the environment and learn from experience, making them a powerful tool for solving tasks in dynamic and uncertain conditions. Despite the limitations associated with reinforcement learning, these approaches demonstrate the potential for research in solving tasks in text-based games using them.

5. PATH-BASED REASONING

Path-based reasoning on knowledge graphs is a method that allows searching and analyzing information based on the paths between nodes in the graph. A knowledge graph is a data structure that represents a network of interconnected entities and their relationships, where nodes correspond to objects or concepts, and edges represent the relationships between them. In the context of path-based reasoning, the main task is to find paths between nodes that are useful for answering questions or performing specific tasks, such as logical inference, data interpretation, or predicting connections.

The process of path-based reasoning can be divided into several key stages. The first stage involves identifying the target nodes and relationships that need to be explored. In this stage, it is important to select the starting and ending nodes, as well as define constraints on the types of paths that may be useful for solving the task. This may include determining the maximum path length or specific types of edges that should be considered.

The second stage is the actual path search process. There are several algorithms that can be used for this. One classic example is the A* algorithm, which has been applied in the context of path finding in knowledge graphs [18]. The A* algorithm uses heuristic functions to estimate the cost of a path and directs the search through the graph towards the most promising paths. In this context, A* with net path-based reasoning allows for the efficient discovery of paths between nodes, minimizing unnecessary transitions and speeding up the search process.

The third stage is the analysis and interpretation of the found paths. At this stage, it is important to evaluate how well the discovered paths align with the task and whether they can be used for further computations or interpretations. For example, in the task of predicting relationships between entities, the discovered paths can be used to assess the likelihood of new connections based on already known data.

The application of path-based reasoning has been implemented in a number of studies. For example, the Path Ranking Algorithm (PRA) method [19], proposed by researchers for the task of relationship prediction, uses paths as the primary unit of analysis. PRA generates multiple paths between pairs of nodes and evaluates their relevance for predicting new relationships. The method has shown good results in tasks related to relationship prediction in biomedical knowledge graphs, such as graphs representing relationships between genes and diseases.

Another approach, Recurrent Neural Network for Path Reasoning (RNN-PR) [20], integrates neural networks for processing path information in knowledge graphs. This method uses recurrent neural networks to analyze the sequence of edges and nodes in a path, allowing it to capture complex dependencies between entities.

In the context of text-based games, path-based reasoning methods can be used to extract new dependencies in approaches that utilize Knowledge Graphs (KG) as a structure for storing environmental knowledge, which is generated during the training process of RL agents.

The advantages of path-based reasoning lie in its ability to efficiently discover and leverage hidden dependencies between entities, making it useful in a wide range of applications.

6. PROBLEM STATEMENT

In this work, an approach will be considered that includes the RL method and KG containing information about the environment. Therefore, let us represent the task of passing through a text-based game as a partially observable Markov decision process (POMDP). Thus, the problem can be defined as a 7-tuple consisting of: a set of states S, a set of actions A, state transition probabilities T, a reward function R, a set of observations Q, conditional observation probabilities O, and a discount factor Y e (0,1]. At each time step, the agent receives an observation ot e Q, which depends on the current state and the previous action via the conditional observation probability O(ot|st, at-1). By performing an action at e A, the environment transitions to a new state based on the state transition probability T(st+1|st,at), and the agent receives a reward rt+1 = R(st,at). As in Markov decision processes (MDPs), the goal of the agent is to learn the optimal policy n* in order to maximize the expected future sum of rewards at each step of the method at every time moment

Rt = E

I] Yk rt+k+1 ,k=0

At the same time, the knowledge graph (KG) for a text-based game is constructed using the standard rule from a set of triplets (Subject, Relation, Object), meaning that the Subject has a Relation with the Object. For example, (Player, Has, Sword). The knowledge graph is introduced as G = (V, E), where V and E are the sets of nodes and edges, respectively. Both the Subject and the Object belong to the set of nodes V. The Relation, corresponding to the edge connecting them, belongs to the set E and represents the relation between the object and the subject of the triplet.

Text-based games require the agent to respond to the environment or event descriptions presented in the form of textual information in order to complete the tasks set within the game. The description received by the agent often contains additional information or expands the understanding of the state of knowledge. Since many hidden states and factors are not observed by the agent at every moment in time, text-based games can be formulated as partially observable Markov decision processes (POMDPs). At each step, we form the current state st as a combination of three components: observation in the form of natural language representation ot)text, score ot,score, and knowledge graph ot,KG. The textual observation represents a description in natural language of the current situation observed by the agent, what items or objects are in the visible area and available for interaction, the description of changes that occurred after the environment's reaction to the agent's action, reflecting effects and newly arisen conditions, opportunities, or limitations. The observation includes not only information about the current state but also about the environment, inventory with item descriptions, and so on. Here, ot,text and ot>score are necessary to reflect the current state observed by the agent, and ot,KG captures the knowledge accumulated during the game. At each step of the agent's operation or learning, the triplets obtained from the current textual observation ot,text are used to update the state of the graph.

In the context of interactive text-based games, the player's goal is to achieve the maximum possible score, in other words, to maximize their score within the game's reward system. Therefore, the agent's task is to find the optimal policy n*(at, |ht) that maximizes the expected sum of discounted rewards. Here, ht represents the history of observations and actions, including all available information up to time t. The agent's overall goal can be written as an optimization problem

n* = arg maxE

n

^Yk rt+k+1 I ht

k=0

where

E

Y^ Yk rt+k+i 1 ht

k=0

E

YkR(st+k,at+k) I ht

k=0

At each time step t, the state st includes:

1. Text observation ot,text

2. Current score ot score

3. Knowledge graph ot,KG

4. Gt = (Vt, Et) is updated based on the triplets (Subject, Relation, Object) extracted from the text

description Ot,text.

5. The observation ot = (ot, .text) ot,score, ot,kg) is formed taking into account the current state st and the previous action at-i through the conditional probability O(ot | st, at-i).

More formally, the agent's state st can be defined as a function that maps the observation and accumulated knowledge into a vector space and calculates the current reward when the state changes:

st = St(Te(ot), Ge(Gt), Rv(st,st-i)),

where

1. Te(ot) is the function for extracting entities and relationships from the text and transforming them into a vector representation.

2. Ge(Gt) is the mapping of accumulated information in the knowledge graph to a vector representation.

3. Rv(st, st-1) is the function that calculates the agent's score when transitioning from the previous state to the current one.