УДК 004.02

Интерпретация задач классического машинного обучения в форме квадратичной неограниченной бинарной оптимизации

Масленников Владимир Владимирович – ассистент кафедры Корпоративных информационных систем МИРЭА – Российского технологического университета.

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

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

Введение

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

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

В настоящей статье рассматривается представление задач линейной регрессии и метода опорных векторов (Support Vector Machine, далее – SVM) в формулировке квадратичной неограниченной бинарной оптимизации с целью возможности реализации данных алгоритмов на базе физических адиабатических квантовых компьютеров [3].

Матрица QUBO

Квадратичная неограниченная бинарная оптимизация или квадратичная оптимизация без ограничений (Quadratic Unconstrained Binary Optimization, далее – QUBO) – это форма задач, для которых не существуют отдельные ограничения, а функция стоимости представляется в виде многочлена второй степени от входных переменных. На выходе таких задач получается бинарный вектор вида  при , (). Таким образом, функция стоимости представляется как:

(1)

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

(2)

QUBO-формулировка для задачи линейной регрессии

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

(3)

где  – прогнозируемое значение;

 – истинное значение;

 – смещение.

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

(4)

Тогда аналитическое решение для уравнения (4) будет иметь вид:

(5)

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

Рассмотрим уравнение (4) в полном виде:

(6)

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

(7)

Бинарные элементы логично интерпретировать с точки зрения индикаторов наличия (отсутствия) степеней двойки в двоичном представлении для всех действительных чисел. Введём вектор-столбец , отсортированный по возрастанию, состоящий из степеней двойки со знаками и определяющий точность представления:

(8)

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

(9)

Используя формулу (9), возможно ввести вектор  такой, что:

(10)

Составим бинарный вектор :

(11)

Составим матрицу точности c размерностью  для задания перехода векторов к бинарному виду:

, (12)

где  – единичная матрица размера .

Тогда исходный вектор весовых коэффициентов можно записать как:

(13)

Получаем QUBO-формулировку для задачи линейной регрессии, подставляя формулу (13) в уравнение (6):

(14)

Для изначально поставленной задачи регрессии (уравнение 4) количество значений в наборе данных  равняется . Введены  бинарных переменных для каждого из  весовых коэффициентов, что указывает на  переменных полученной интерпретации QUBO. Соответственно, для решения задачи рассматриваемым подходом требуется  кубитов [5] в пространственной сложности.

С целью оценки временной сложности QUBO-формулировки линейной регрессии важно учитывать три основополагающих фактора:

  1. Временные затраты на конвертацию регрессионной задачи в QUBO составляют .
  2. Временные затраты на выполнение QUBO-задачи на физическом квантовом вычислительном устройстве равны .
  3. При расчёте временных затрат на реализацию квантового отжига [6] для получения наиболее точного конечного решения берётся достаточная высокая вероятность получения оптимального решения. На практике для квантовых компьютеров модели D-Wave [7] с ограниченным количеством доступных кубитов время отжига и число повторений считаются константными значениями.

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

QUBO-формулировка для метода опорных векторов

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

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

(15)

Запишем лагранжиан [8] к задаче:

(16)

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

Построим двойственную функцию на основе уравнений [9] для точки минимума лагранжиана при любых фиксированных значениях  и :

(17)

Выполнение условий [9] гарантирует, что двойственная функция никогда не обратится в . Объединив условия неотрицательности двойственных переменных  и [9] в , получаем двойственную задачу с единственным максимумом:

(18)

Перепишем (18) с точки зрения задачи минимизации:

(19)

Задачу минимизации (19) возможно представить в виде, который учитывает периферийные обучающие объекты  (при , тогда ) и опорные обучающие объекты  (при ):

(20)

где  – вектор из  единиц;

.

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

(21)

Вектор  содержит  элементов. При подходящем наборе  и  на достаточном уровне выполняется равенство:

(22)

Конкатенация по вертикали всех  даёт:

(23)

Вводим матрицу :

(24)

Приближённо получается:

(25)

Осуществим замену в системе уравнений (20) на основе выражения (25):

(26)

Чтобы избавиться от ограничения в виде равенства, введём штраф за его нарушение:

(27)

где  – константа с большим значением;

 – гиперплоскость.

Конечная QUBO-формулировка для метода опорных векторов получается добавлением выражения (27) к :

(28)

В задаче (20) в данных содержится  значений и  параметров . Интерпретация данной задачи в QUBO (28) содержит такое же число значений в данных, но при этом количество параметров  увеличено в  раз (, что указывает на необходимость применения  кубитов.

Временная сложность классического SVM равняется  [10]. Оценка временной сложности для QUBO-формулировки требует рассмотрения трёх составляющих:

  1. Временные затраты для конвертации в QUBO в соответствии с (19) и (22) равняются .
  2. Временные затраты на выполнение QUBO-задачи на физическом квантовом вычислительном устройстве равны .
  3. При расчёте временных затрат на реализацию квантового отжига, как в случае с линейной регрессией, время отжига и число повторений считаются константными значениями.

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

Заключение

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

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

  1. Масленников, В. В. Математическая модель интеллектуальной системы прогнозирования инсульта и её реализация на базе гибридного нейросетевого алгоритма рекуррентного типа / В. В. Масленников // Современная наука: актуальные проблемы теории и практики. Серия: Естественные и технические науки. – 2022. – № 11-2. – С. 107-122. – DOI 10.37882/2223-2966.2022.11-2.19. – EDN QVPEND.
  2. Ulyanov, S. V. Quantum software engineering Pt II: Quantum computing supremacy on quantum gate-based algorithm models / S. V. Ulyanov, O. Yu. Tyatyushkina, V. V. Korenkov // . – 2021. – No. 1. – P. 81-129. – EDN EIMGEI.
  3. N + 1. [Электронный ресурс]: https://nplus1.ru/material/2015/12/15/D-wave (дата обращения: 05.05.2023).
  4. С-86 Стронгина Н.Р. Курс «Численные методы»: Итерационные методы
    решения СЛАУ для вычислительно-трудоемких задач (Модули 10 – 11):
    Учебно-методическое пособие. – Нижний Новгород: Нижегородский
    госуниверситет, 2021. – 79 с.
  5. Date, Prasanna & Patton, Robert & Schuman, Catherine & Potok, Thomas. (2019). Efficiently embedding QUBO problems on adiabatic quantum computers. Quantum Information Processing. 18.10.1007/s11128-019-2236-3.
  6. Применение оптимизационных методов для решения задачи минимизации шумов в системах квантового распределения ключей при их интегрировании в волоконно-оптические линии связи с применением технологии плотного мультиплексирования по длине волны / А. Д. Тарабрина, Д. В. Тупяков, И. О. Воронцова [и др.] // Оптический журнал. – 2022. – Т. 89, № 9. – С. 66-74. – DOI 10.17586/1023-5086-2022-89-09-66-74. – EDN ADZMYL.
  7. D-Wave. [Электронный ресурс]: https://www.dwavesys.com/ (дата обращения: 07.05.2023).
  8. Хорькова, Н. Г. О классификации лагранжианов, обладающими линейными уравнениями Эйлера-Лагранжа, и генерировании заданий по вариационному исчислению / Н. Г. Хорькова, О. Ю. Чигирева // Modern European Researches. – 2021. – № 3. – С. 146-151. – EDN QIKKAE.
  9. Сиротко, С. И. К условиям регулярности в задачах математического программирования / С. И. Сиротко, А. В. Пашук // Труды БГТУ. Серия 3: Физико-математические науки и информатика. – 2022. – № 1(254). – С. 10-14. – DOI 10.52065/2520-6141-2022-254-1-10-14. – EDN NZHCPY.
  10. Accuracy improvement of geographical indication of rice by laser-induced breakdown spectroscopy using support vector machine with multi-spectral line / P. Yang, H. T. Liu, Z. L. Nie, X. N. Qu // Zurnal Prikladnoj Spektroskopii. – 2022. – Vol. 89, No. 3. – P. 434. – EDN BHWKYN.

Интересная статья? Поделись ей с другими: