Мы разработали алгоритм, основанный на алгебраическом градиенте (AGS), новый решатель для приблизительного маргинального вывода MAP. Алгоритм строит приближенный граф алгебраических вычислений, фиксирующий маргиналы переменных состояния и вознаграждения при допущениях о независимости. Затем он использует автоматическую дифференциацию и поиск по градиенту для оптимизации выбора действий. Наш анализ показывает, что значение, вычисленное графиком вычислений AGS, идентично решению распространения убеждений (BP), когда оно обусловлено действием. Это обеспечивает явное соединение между алгоритмами эвристического планирования и приблизительным выводом.

Существует глубокая взаимосвязь между планированием и выводом, и в течение последнего десятилетия многие исследователи ввели явные сокращения, показывающие, как стохастическое планирование может быть решено с помощью вероятностного вывода с приложениями в робототехнике, планировании и экологических проблемах. Однако эвристические методы и поиск по-прежнему являются наиболее эффективными подходами к планированию в больших комбинаторных состояниях и пространствах действий. Мои соавторы и я используем новый подход в нашей статье «От стохастического планирования до маргинальной MAP» (авторы: Хао Цуй, Раду Маринеску, Рони Хардон) на конференции по системам нейронной обработки информации (NeurIPS) 2018 года, показав, как идеи для планирования могут быть использованы для вывода.

Более конкретно, мы пересматриваем связь между стохастическим планированием и вероятностным выводом. Мы предлагаем в первый раз использовать эффективный эвристический алгоритм, который был первоначально разработан для решения задач планирования для решения задачи центрального вывода для вероятностных графических моделей, а именно предельной максимальной задачи апостериорной вероятности (MMAP).

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

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

Для иллюстрации рассмотрим байесовскую сеть, показанную на рисунке 1, в которой показана простая проблема диагностики для вычислительной системы. Модель фиксирует прямые причинные зависимости между шестью случайными величинами, используемыми для описания этой проблемы. В частности, сбой системы может быть вызван сбоем оборудования, сбоем ОС или наличием вредоносного ПО в системе. Аналогичным образом, отказ питания может быть общей причиной отказа оборудования и ОС, а Stormy Weather может привести к сбою питания. Возможным запросом MMAP было бы вычисление наиболее вероятной конфигурации аппаратных и системных сбоев, учитывая, что мы наблюдаем Stormy Weather, независимо от состояния других переменных (вредоносное ПО, системный сбой или сбой питания).

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

 

Динамическая байесовская сеть (DBN) для стохастического планирования

 

Рисунок 2. Динамическая байесовская сеть (DBN) для стохастического планирования. Фото: IBM

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

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

 

По материалам phys.org