Разрабатываются графовые нейронные сети основанные на физике

Прочитано: 79 раз(а)


Графовые нейронные сети, основанные на физике, для решения задач комбинаторной оптимизации.

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

Исследователи из лаборатории квантовых решений Amazon, входящей в состав лаборатории интеллектуальных и передовых компьютерных технологий AWS, недавно разработали новый инструмент для решения задач комбинаторной оптимизации на основе графовых нейронных сетей (GNN). Подход, разработанный Шютцем, Брубейкером и Кацграбером и опубликованный в журнале Nature Machine Intelligence , можно использовать для оптимизации множества реальных проблем.

«Наша работа была очень вдохновлена ​​потребностями клиентов», — сказал TechXplore Мартин Шютц, один из исследователей, проводивших исследование. «В нашей повседневной работе в лаборатории квантовых решений Amazon мы взаимодействуем со многими клиентами из разных вертикалей, чтобы подготовиться к квантовым технологиям, то есть подготовиться к будущему, когда эта новая технология станет коммерчески жизнеспособной. Большинство вариантов использования клиентов связаны с комбинаторными проблемы с оптимизацией».

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

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

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

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

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

«Наша ключевая идея состоит в том, чтобы сформулировать задачи комбинаторной оптимизации как неконтролируемые задачи классификации узлов, посредством которых GNN изучает назначения цвета (другими словами, спина или переменной) для каждого узла», — объяснил Шютц. «С этой целью GNN итеративно обучается с помощью пользовательской функции потерь, которая кодирует конкретную интересующую проблему оптимизации во взаимно однозначном соответствии с исходным гамильтонианом, что обеспечивает принципиальный выбор функции потерь GNN».

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

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

«Наш оптимизатор GNN основан на прямой и общей математической связи между прототипическими спиновыми гамильтонианами Изинга и дифференцируемой функцией потерь, с помощью которой мы обучаем GNN, тем самым обеспечивая одну унифицирующую структуру для широкого класса задач комбинаторной оптимизации и открывая мощный набор инструментов физики до современных подходов к глубокому обучению», — сказал Брубейкер. «Сочетая концепции из физики с современными инструментами машинного обучения, мы предлагаем простой, универсальный и надежный решатель, который не полагается на функции потерь, созданные вручную».

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

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

В будущем новый метод на основе GNN, представленный этой группой исследователей, можно будет использовать для решения множества сложных реальных задач оптимизации . Поскольку он изначально масштабируемый, Amazon Quantum Solutions Lab и AWS планируют предложить его своим клиентам в качестве инструмента, который может облегчить их переход на квантовые технологии. Фактически, их метод может позволить клиентам подойти к обеим проблемам, связанным с конкретными вариантами использования, в рамках квантового моделирования, как в небольших, так и в отраслевых масштабах.

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

Разрабатываются графовые нейронные сети основанные на физике



Новости партнеров