О применении квантовых алгоритмов оптимизации к задачам машинного обучения

В рамках постоянно действующего научно-исследовательского семинара  «Суперкомпьютерное моделирование в науке и инженерии, или Вычислительные среды»  (Магистерская программа "Суперкомпьютерное моделирование в науке и инженерии") выступил с докладом «Применение квантового отжига к задачам машинного обучения» Игорь Побойко (ИТФ им. Л.Д.Ландау РАН, Сколковский Институт Науки и Технологий, НИУ ВШЭ).

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

Доклад основан на работе Carlo Baldassi и Riccardo Zecchina, «Efficiency of quantum versus classical annealing in non-convex learning problems» (arXiv:1706.08470v3). 

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

Одним из традиционных методов глобальной оптимизации является так называемый метод имитации отжига (simulated annealing, SA), основанный на простой физической аналогии: при понижении температуры, физическая система приходит в состояние с наименьшей энергией. В методе SA искомая целевая фунцкия отождествляется с энергетическим профилем воображаемой физической системы. Метод SA состоит в моделировании поведения данной воображаемой физической системы при конечной температуре, обычно с помощью техники Монте-Карло. В процессе моделирования, температура постепенно понижается согласно некоторому протоколу, и система приходит в состояние с наименьшей энергией --- т.е., искомый глобальный минимум.

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

Для таких задач предложен метод имитации квантового отжига (simulated quantum annealing, SQA): рассматривается квантово-механический гамильтониан, зависящий от параметра (приложенного внешнего поля), предел которого при стремлении внешнего поля к нулю представляет собой целевую функцию. Моделирование методом Монте-Карло стартует с конечного (большого) значения внешнего поля, которое в процессе моделирования уменьшается согласно заданному протоколу. В работе рассмотрено несколько приложений, в которых метод SQA позволяет значительно ускорить поиск основного состояния системы (т.е., глобального минимума энергии) за счет квантово-механического туннелирования между метастабильными состояниями (т.е., локальными минимумами).