Построение и анализ сложности квантовых алгоритмов для задач на ациклических графах тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Сафина Лилия Ильхамовна
Сафина Лилия Ильхамовна
кандидат наук
2025
- Специальность ВАК РФ00.00.00
- Количество страниц 191
Оглавление диссертации кандидат наук Сафина Лилия Ильхамовна
Введение
Глава 1. Постановка задач и модели вычислений
1.1 Задачи поиска кратчайших и максимальных путей в ориентированном ациклическом графе
1.1.1 Определения теории графов
1.1.2 Постановка задачи
1.2 Задача бинарной классификации
1.2.1 Постановка задачи
1.2.2 Ансамблевые модели машинного обучения
1.3 Модели вычислений
1.3.1 Основы квантовых вычислений
1.3.2 Квантовые схемы
1.3.3 Квантовая модель запросов
1.4 Известные квантовые алгоритмы
1.4.1 Алгоритмы Гровера, оценки амплитуды и квантовое преобразование Фурье и их сложность
1.4.2 Алгоритмы для задачи поиска кратчайших и максимальных путей в ациклическом орграфе и
смежных задач теории графов и их сложность
1.4.3 Алгоритмы для задачи бинарной классификации и смежных задач машинного обучения и их сложность
1.5 Выводы по первой главе
Глава 2. Построение квантовых алгоритмов для задачи
бинарной классификации в модели запросов и анализ
их сложности
2.1 Алгоритмы прогнозирования
2.2 Анализ сложности алгоритма
2.3 Выводы по второй главе
Глава 3. Построение квантовых алгоритмов для задачи
бинарной классификации в модели квантовых схем и анализ их сложности
3.1 Квантовая схема для алгоритма прогнозирования моделью машинного обучения случайный лес
3.2 Анализ сложности алгоритма
3.2.1 Сложность по памяти
3.2.2 Гейтовая сложность алгоритма
3.3 Построение оптимизированной схемы
3.3.1 Модифицированные техники оптимизации квантовой схемы для алгоритма прогнозирования моделью случайный лес
3.3.2 Анализ гейтовой сложности с применением модифицированных техник оптимизаций
3.4 Выводы по третьей главе
Глава 4. Построение квантовых алгоритмов для задач поиска кратчайших и максимальных путей в ациклическом орграфе в модели запросов и анализ их сложности
4.1 Построение алгоритма
4.2 Анализ сложности алгоритма
4.3 Выводы по четвертой главе
Заключение
Список литературы
Приложение А. Матричное представление квантового
прогнозирования. Задача adult
Приложение В. Схемная реализация в qiskit. Задача adult
Приложение С. Схемная реализация в qiskit для задачи
бинарной классификации объектов с бинарными атрибутами моделью случайный лес
Приложение D. Оптимизированная схемная реализация в qiskit 163 Приложение Е. Численные эксперименты
Введение
Квантовые вычисления применяются в широком спектре направлений: химия, физика, медицина, логистика, финансы и другие направления [1]. Известно большое количество задач, для которых квантовые алгоритмы эффективнее чем классические (детерминированные и вероятностные) [2].
Квантовые алгоритмы гораздо более трудоемко построить и реализо-вывать по сравнению с классическими. Построение квантовых алгоритмов целесообразно лишь в случае их большей эффективности по сравнению с классическими. Наиболее известными квантовыми алгоритмами, которые демонстрируют свою большую эффективность по сравнению с классическими, являются квантовый алгоритм Шора [3] факторизации числа и квантовый алгоритм Гровера [4] поиска в базе данных.
В теории сложности вычислений показателями эффективности алгоритмов являются характеристики сложности алгоритмов. Традиционно известными мерами сложности являются число элементарных шагов алгоритма (время вычисления) и число используемых ячеек памяти (память, используемая алгоритмом). Для задания меры сложности необходимо фиксировать и формализовать модель вычисления и уровень описания алгоритма. Существует большое число различных моделей вычислений. Выбор модели вычислений определяется решаемой задачей. В рамках данной работы рассматриваются две модели: квантовые схемы и модель запросов.
Квантовая схема или схемная модель может быть рассмотрена как квантовый аналог схемы из функциональных элементов (СФЭ). Она является особенно важной, в связи с тем, что программирование современных квантовых устройств часто осуществляется на уровне составления квантовой схемы. Основными сложностными характеристиками для алгоритмов в рамках данной вычислительной модели является гейтовая сложность и сложность по памяти. Гейтовая сложность это число гейтов или вентилей в схеме (аналог числа вентилей в СФЭ), трактуется как аналог сложности по времени. В то же время количество квантовых битов, используемых в схеме, определяет сложность по памяти для алгоритма [5; 6].
Другой часто используемой для представления квантовых алгоритмов вычислительной моделью является модель запросов [7]. В рамках этой модели
алгоритм представляется в виде последовательности унитарных операторов, в которой чередуются операторы, которые зависят от входных данных и которые не зависят от них.
В рамках этой модели мерой сложности является запросная сложность число унитарных операторов, зависящих от входных данных (запросов к памяти). Здесь предполагается, что наиболее затратной по времени операцией является обращение к памяти, в частности, если данные находятся в медленной (к примеру, внешней) памяти. Таким образом, число запросов является некоторым аналогом временной сложности для алгоритма. Запросная сложность, как число шагов, на которых происходит обращение к памяти, определяется и в классическом случае [7]. В связи с этим квантовые и классические алгоритмы в данной вычислительный модели можно сравнить между собой. Запросная сложность для классических алгоритмов всегда не больше чем временная сложность. Они не совпадают в случае, если не во всех шагах алгоритма происходит обращение к памяти.
Среди наиболее известных квантовых алгоритмов, разработанных в модели запросов, является алгоритм Гровера [4; 8] и его обобщения, решающие различные задачи поиска. Многие из этих алгоритмов имеют квадратичное преимущество по сравнению с нижней оценкой на сложность классических (детерминированных и вероятностных) алгоритмов с точки зрения запросной сложности [9].
Задачи машинного обучения. Одна из областей, в которой квантовые алгоритмы показывают свою эффективность, является квантовое машинное обучение [10]. В обзорных работах [10 13] авторы рассматривают квантовые алгоритмы машинного обучения, имеющие меньшую сложность, чем сложность классических аналогов. В данной работе исследуется задача прогнозирования ансамблевой моделью машинного обучения задачи бинарной классификации, и один из частных случаев ансамблевой модели модель случайный лес (Random Forest) [14], являющаяся ансамблем деревьев решений [15].
В данной работе слово "модель" используется в двух смыслах. С одной стороны, для обозначения моделей вычислений (модель запросов и квантовые схемы). С другой стороны, модель машинного обучения: так принято называть семейство алгоритмов, применяемых для задач машинного обучения. Там, где этот термин может породить двусмысленность, уточняется, о каких моделях идёт речь: вычислительных или моделях машинного обучения.
Исследователями рассмотрена задача построения деревьев решений с точки зрения квантовых вычислений. Предложен квантовый алгоритм в модели запросов для построения деревьев, имеющий меньшую запросную сложность, чем сложность классических аналогов [16 19]. В то же время, для задачи прогнозирования задачи бинарной классификации ансамблевыми моделями, в частности моделью машинного обучения случайный лес, ранее квантовые алгоритмы не строились.
Задачи построения кратчайшего и максимального пути в ациклическом орграфе. Другой областью, где исследователи строят квантовые алгоритмы, которые эффективнее классических аналогов, является теория графов [20; 21].
Среди задач, для которых построены квантовые алгоритмы в модели запросов, имеющих меньшую запросную сложность, чем классические аналоги, в том числе меньшую, чем нижние оценки на запросную сложность в классическом случае, можно перечислить следующие. Алгоритмы для задачи обхода [22], построения Гамильтонова пути [23], поиска максимального паросочетания и потока [24; 25] и другие.
Одна из таких задач это задача построения кратчайших) и максимального по длине пути в ациклическом орграфе G = (V,E). Для данной задачи известно детерминированное решение динамическим программированием [21], имеющее сложность 0(\V| + \Е|).
Для этих задач можно применить алгоритмы, используемые для поиска кратчайшего пути в случае общего графа, такие как алгоритмы Дейкстры, Флойда и другие [21], однако их сложность больше, чем у метода динамического программирования. В работе [22] предложен квантовый алгоритм для поиска кратчайшего пути в общем графе, сложность которого составляет 0(\J\V\\Е\ log2 \ V\). Нижняя оценка запросной сложности для квантовых алгоритмов поиска кратчайшего пути составляет \\Е\) [ ]• Для общего графа задача поиска максимального по длине пути является NP-трудной [26], а её версия, в которой нужно проверить наличие пути, имеющего длину не менее заданного /, является NP-полной [ ]. Любые существующие алгоритмы для общего графа, в том числе квантовые, имеют большую сложность, чем детерминированное решение методом динамического программирования.
Рекомендованный список диссертаций по специальности «Другие cпециальности», 00.00.00 шифр ВАК
Эффективные алгоритмы для решения задач о заданном порядковом расстоянии, о геометрическом минимальном остовном дереве и о максиминных путях2025 год, кандидат наук Каймаков Кирилл Владимирович
Инкрементальные алгоритмы решения задач оптимизации на больших графах2019 год, кандидат наук Гуральник Роман Игоревич
Задачи об оптимальном соединении в пространствах компактов2016 год, кандидат наук Овсянников Захар Николаевич
Статическое моделирование временных характеристик работы СБИС с использованием вычислительных систем с общей памятью2013 год, кандидат физико-математических наук Князев, Николай Александрович
Алгоритмы подбора параметров комбинирования ациклических графов соседства в задачах обработки текстурных изображений2013 год, кандидат технических наук Динь Вьет Шанг
Введение диссертации (часть автореферата) на тему «Построение и анализ сложности квантовых алгоритмов для задач на ациклических графах»
Целью работы является
— исследование квантовой запросной сложности для задачи прогнозирования ансамблевой моделью машинного обучения — задачи бинарной классификации, и один из частных случаев ансамбля — модели случайный лес, являющейся ансамблем деревьев решений;
— исследование сложности квантовых схем для задачи прогнозирования задачи бинарной классификации моделью машинного обучения случайный лес;
— исследование запросной сложности задачи поиска кратчайшего и максимального пути в ациклическом ориентированном графе.
Для достижения поставленной цели необходимо решить следующие задачи:
1. Разработать квантовый алгоритм прогнозирования для задачи бинарной классификации ансамблевыми моделями, имеющий меньшую запросную сложность, чем детерминированные аналоги;
2. Разработать подходы оценки амплитуды, соответствующей вероятности принадлежности объекта заданному классу, для задачи бинарной классификации ансамблевыми моделями, имеющие меньшую запросную сложность, чем классические (детерминированные или вероятностные аналоги);
3. Разработать квантовую схему прогнозирования для задачи бинарной классификации моделью случайный лес и оценить ее гейтовую сложность;
4. Разработать модифицированные техники гейтовой оптимизации для квантовой схемы прогнозирования, позволяющие уменьшить гейтовую сложность для представления модели случайный лес в виде квантовой схемы;
5. Разработать алгоритм поиска кратчайших и максимальных путей в ориентированном ациклическом графе, имеющий меньшую запросную сложность, чем существующие детерминированные и квантовые аналоги.
В данной работе предложены квантовые алгоритмы прогнозирования ансамблевой моделью для задачи бинарной классификации и квантовые алгоритмы для задач поиска кратчайшего и максимального по длине пути в ациклическом орграфе.
В главе 2 рассматривается вопрос построения квантового алгоритма в рамках вычислительной модели запросов для прогнозирования ансамблевой
моделью для задачи бинарной классификации. Квантовый алгоритм прогнозирования ансамблевой моделью для задачи бинарной классификации обладает запросной сложностью, равной 0(Т(&)), где Т(к) — запросная сложность прогнозирования на индивидуальной модели машинного обучения (простом классификаторе) в ансамблевой модели, в частности деревьев решений, к — длина входного набора. Запросная сложность детерминированного алгоритма составляет 0(Ы • Т(к)), где N — количество индивидуальных моделей (простых классификаторов) в ансамблевой модели, в частности, деревьев решений. Таким образом, запросная сложность квантового алгоритма не зависит от количества простых классификаторов. Нижняя оценка для запросной сложности прогнозирования ансамблевой моделью ранее не изучена.
В работе предложены вероятностный и квантовый алгоритмы для прогнозирования вероятности принадлежности входного объекта одному из классов ансамблевой моделью машинного обучения. Запросная сложность разработанного квантового алгоритма составляет О ^—р • Т(к)^, где р — вероятность принадлежности входного объекта к одному из классов. Запросная сложность разработанного вероятностного алгоритма составляет О ^^ • Т(к)^. Сложность детерминированного алгоритма 0(Ы • Т(к)). Таким образом, демонстрируется квадратичное преимущество квантовых алгоритмов перед вероятностным, по аналогии с тем, как запросная сложность квантового алгоритма Гровера квадратично меньше, чем нижняя оценка классической версии (вероятностной или детерминированной) для задачи поиска [9]. Предложенные квантовые алгоритмы основаны на модификации алгоритма Гровера алгоритме усиления амплитуд [28].
В главе 3 рассматривается вопрос построения квантового алгоритма в рамках вычислительной модели квантовых схем для прогнозирования ансамблевой моделью для задачи бинарной классификации. Исследована гейтовая сложность задачи прогнозирования вероятности принадлежности одному из классов в рамках задачи прогнозирования ансамблевой моделью машинного обучения. В работе [17] исследована эта задача для модели дерево решений для ограниченного случая и предложен способ представления модели в виде квантовой схемы. В данной работе рассматривается модель случайный лес, состоящая из деревьев решений, без ограничений. Построена квантовая схема для модели случайны лес, гейтовая сложность которой составляет 0(2ь+Хо^''2м • к), где к — максимальная высота деревьев решений, входящих в лес, N — число дере-
вьев в лесу. Полученная верхняя оценка меньше, чем верхняя оценка, которую можно получить универсальным методом синтеза квантовых схем [29], которая составляет 0(4h+log2N+k), где к — длина входного объекта.
В главе 4 рассматривается вопрос построения квантового алгоритма в рамках модели запросов для задач поиска кратчайшего и максимального путей в ациклическом орграфе. Для данных задач построены квантовые алгоритмы, запросная сложность которых равна 0(д/\V\\Е\ log \ V\), что устанавливает новую верхнюю оценку на сложность этих задач. Данная верхняя оценка меньше, чем существующие оценки как в классическом (детерминированном или вероятностном) случае, так и квантовом.
Научная новизна:
1. Получена верхняя оценка квантовой запросной сложности задачи прогнозирования для задачи бинарной классификации ансамблевыми моделями. Впервые разработан квантовый алгоритм, достигающий эту верхнюю оценку;
2. Продемонстрировано, что квантовая запросная сложность построенного алгоритма меньше запросной сложности существующих детерминированных версий;
3. Предложены подходы оценки амплитуды квантового состояния, соответствующей вероятности принадлежности объекта заданному классу для задачи бинарной классификации. Предложена верхняя оценка для квантовой запросной сложности этой задачи меньшая, чем запросная сложность классических (вероятностных и детерминированных) алгоритмов;
4. Разработаны квантовые схемы прогнозирования для задачи бинарной классификации моделью случайный лес, приведен анализ гейтовой сложности в базисе элементарных гейтов и предложены модифицированные техники гейтовой оптимизации схем прогнозирования, уменьшающие гейтовую сложность схемы;
5. Предложен алгоритм поиска кратчайших и максимальных путей в ориентированном ациклическом графе с меньшей запросной сложностью, чем у детерминированной и квантовой версий.
Теоретическая и практическая значимость в конструктивном построении верхних оценок на квантовую запросную сложность для задач прогнозирования ансамблевыми моделями и поиска кратчайших и максималь-
и
ных путей в ориентированном ациклическом графе. Верхние оценки получены за счет построения квантовых алгоритмов, имеющих меньшую запросную сложность, чем существующие классические аналоги. Впервые построена квантовая схема для алгоритма прогнозирования моделью случайный лес, квантовая схема оптимизирована по числу элементарных операторов.
Методология и методы исследования. Объектом исследования данной научной работы являются алгоритмы квантового машинного обучения и квантовые алгоритмы для задач теории графов, предметом — ансамблевые алгоритмы квантового машинного обучения, основанные на диаграммах решений, и квантовые алгоритмы для поиска кратчайших и максимальных путей в ациклическом орграфе. В качестве метода исследования предмета выбраны построение и анализ квантовых алгоритмов в вычислительных моделях запросов и квантовых схем. Для анализа работы квантового алгоритма прогнозирования выбрана модель машинного обучения — случайный лес. Разработана и протестирована квантовая схема. Реализация позволяет оценить гейтовую сложность алгоритма и сложность по используемой памяти в квантовой схеме.
Основные положения, выносимые на защиту:
1. Разработан квантовый алгоритм прогнозирования ансамблевыми моделями для задачи бинарной классификации, имеющий меньшую запросную сложность чем существующие детерминированные аналоги;
2. Разработаны квантовые алгоритмы для определения вероятности принадлежности одному из классов ансамблевыми моделями, запросная сложность которых меньше детерминированных и вероятностных аналогов;
3. Разработана схемная реализация алгоритма прогнозирования для задачи бинарной классификации моделью случайный лес, оценена ее гейтовая сложность, которая меньше, чем сложность универсальной декомпозиции;
4. С использованием модифицированных техник гейтовой оптимизации предложена схемная реализация алгоритма прогнозирования моделью случайный лес в базисе элементарных гейтов, позволяющая уменьшить гейтовую сложность схемы;
5. Разработан алгоритм поиска кратчайших и максимальных путей в ориентированном ациклическом графе, имеющий меньшую запросную
сложность, чем существующие квантовые и детерминированные аналоги.
Достоверность полученных результатов обеспечивается строгостью приведенных математических доказательств. Результаты находятся в соответствии с результатами, полученными другими авторами работ по квантовому машинному обучению и по квантовым алгоритмам на графах.
Апробация работы. Основные результаты работы докладывались на:
— Международная научная конференция The 18th International Conference on Unconventional Computation and Natural Computation (UCNC2019) Токио Университет электро-коммуникаций 03.06.2019 - 07.06.2019
— Международная научная конференция YRID-2020: International Workshop on Data Mining and Knowledge Engineering, Ставрополь SUR, UI, СКФУ, 15.10.2020 - 16.10.2020.
— Международная научная конференция XIX Проблемы теоретической кибернетики, Казань, КФУ, 28.09.2021 - 01.10.2021.
— Международная научная конференция 14th International Conference Micro- and Nanoelectronics 2021 (ICMNE-2021), Звенигород ФТИАН 04.10.2021 - 08.10.2021.
— Международная научно-практическая конференция 24th Annual Conference on Quantum Information Processing (QIP2021), Технический университет, Мюнхен, 30.01.2021 - 05.02.2021.
— Международная научная конференция Четырнадцатый международный научный семинар Дискретная математика и ее приложения имени академика О.Б. Лупанова 2022, 20.06.2022 - 25.06.2022.
— 11-я Международная научная конференция Дискретные модели в теории управляющих систем, Красновидово, МГУ им. Ломоносова, 26.05.2023 - 29.05.2023.
— 15-я Международная конференция Микро- и наноэлектроника -2023, Звенигород, ФТИАН, 02.10.2023 - 06.10.2023.
— Научные семинары кафедры теоретической кибернетики и научно-исследовательской лаборатрии Квантовые методы обработки данных ИВМиИТ КФУ.
— Научные семинары на кафедре системного программирования СПбГУ, 15.01.2025, 22.01.2025.
— Квантовый консорциум, Университет Иннополис, 06.03.2025.
Личный вклад. Автор принимал активное участие в разработке квантовых алгоритмов прогнозирования задачи бинарной классификации ансамблевыми моделями, алгоритмов построения деревьев решений, и алгоритма поиска кратчайших и максимальных путей в ориентированных ациклических графах, представленных в [18; 19; 30 41].
Публикации. Основные результаты по теме диссертации изложены в 13 печатных изданиях, 8 из которых изданы в периодических научных журналах, которые индексируются в Scopus и Web of Science и входят в перечень ВАК, 5 в тезисах докладов. Зарегистрирована 1 программа для ЭВМ.
Объем и структура работы. Диссертация состоит из введения, 4 глав, заключения и 5 приложений.
В главе 1 введены постановка задач, используемые определения теории графов, машинного обучения и квантовых вычислений, а также приведен обзор существующих квантовых подходов и алгоритмов в теории графов и машинном обучении. В главе 2 приведены эффективные квантовые алгоритмы для задачи прогнозирования задачи бинарной классификации ансамблевыми моделями и их анализ сложности в модели запросов. Глава 3 посвящена построению квантовых алгоритмов для задачи бинарной классификации в модели квантовых схем, для которых представлен анализ сложности по квантовой памяти и числу элементарных гейтов и предложены модифицированные техники гейто-вой оптимизации. Глава 4 содержит построение и анализ запросной сложности квантовых алгоритмов для задачи поиска кратчайших и максимальных путей в ориентированном ациклическом графе в модели запросов.
Полный объём диссертации составляет 191 страницу, включая 40 рисунков и 32 таблицы. Список литературы содержит 157 наименований.
Глава 1. Постановка задач и модели вычислений
1.1 Задачи поиска кратчайших и максимальных путей в ориентированном ациклическом графе
1.1.1 Определения теории графов
Далее представлены необходимые определения из теории графов [20; 42].
Определение 1. [ ] Ориентированным графом или ографом С называется пара множеств V и Е. Множество V называется множеством вершин, Е С V- множеством ребер, соединяющих вершины. Ребра, в ориентированном графе называются ориентированны,ми ребрам,и, или, дугами.
В случае, если Е С {{и,у}, где и,у € V} — множество из неупорядоченных пар {и,у}, то граф называется неориентированным, а элементы множества Е называются неориентированными ребрами или, просто ребра-
Определение 2. Граф называется взвешенным,, если определена, весовая, функция и> : V х V ^ Ж, где /ш(и,у) — это некоторое действительное число, называемое весом ребра. Для ориентированного графа, в случае, если(у,и) € Е, то /ш(у,и) — конечное число. Если (у,и) € Е, то /ш(у,и) = ж. Для неориентированного графа, в случае, еслиу,и € Е, то /ш(у,и) = /ш(и,у) — конечное число. Если, у,и € Е, то т(у,и) = т(и,у) = ж.
Определение 3. Путь в графе — последовательность вершин: у^ ,... ,у1к, в которой каждые соседние вершины соединены между собой ребром,: Зе = (у,1:)) € Е V] € {0,... ,к — 1}]. Путь называется простым, если все вершины в последовательности у,10,... ,у,1к различны.
Если граф взвешенный, то длина пути сумма весов рёбер, входящих в него: 1еп(Р) = ы(уго ).
Определение 4. Вершина У\ достижима из вер шины, у0, если, существует простой путь из вершины у0 в верши ну У\.
Определение 5. Кратчайший путь из вершины v в вершину и во взвешенном графе — простой путь от стартовой вершины v до заданной конечной вершиныи: Р = (v,v¡1,... ,v¡k-1 ,и), имеющий минимальную длину 1еп(Р) среди всех таких путей.
Определение 6. Максимальным пут,ем, из вершиныи в вершину и называется простой путь Р = (v,v¡1,... ,v¡k-1 ,и), имеющий максимальную длину 1еп(Р) среди всех таких путей.
Определение 7. Простой цикл в графе — путь Р = (v¡0,... ,Vik) такой, что Vi0 = Vik, все остальные вер шины v¡0,... ,v¡k-1 различны.
Определение 8. Ациклический граф — граф, в котором отсутствуют простые циклы,.
Определение 9. Топологическая сортировка графа — способ линейного порядка, на вершинах ориентированного ациклического графа, для которого выполняется условие: если существует (v¡,vj) £ Е, тогда i < j.
Определение 10. Дереово — это связный, ациклические неориентированный граф.
Определение 11. Корневрое дерево — это дерево, в котором выделена единственная вершина, называемая корнем, граф ориентированный и получен из исходного ориентированием, ребер следующим образом. Каждое ребро ориентировано от вершины с меньшим расстоянием от корня, до вершины с большим, расстоянием от корня: (v,u) £ Е, если длина простого пут,и от корня, до v меньше, чем длина простого пут,и от корня, до и.
Вершины, из которых не выходят ребра, называются листовыми или, листьями. Оставшиеся вершины называются нелистовыми.
В корневом дереве, если существует путь от корня до вершины, то он единственный.
Определение 12. В корневом дереве длина пути от корня до заданной вершины v называется глубиной вершины v.
Определение 13. Вы,сот,а, дерева (или глубина дерева) — максимальная глубина среди вершин дерева.
Способы хранения графов [21], используемые в работе: — Матрица смежности для графа С = (V, Е), состоящего из [V | вершин, представляет собой матрицу Сг размерно с ти [V | х [V где н а г строке и на ] столбце стоит 1, если между вершинами с номерами % ж ] есть ребро, и 0 в противном случае.
— Список смежности Сг представляет собой список из [V| элементов. Элемент номер г — список смежных с ¿-ой вершиной других вершин (соединенных одним ребром). Пусть вершина с номером г смежна с I вершинами, тогда
СгЩ = (уп ,...,У31), уп ,у32 ,...,у31 € У, Зе: = (1,]1),в2 = (1,]2),...,е1 = (г,]1) : ет € Е,т € [1,1]
Дан взвешенный ациклический ориентированный граф с топологически отсортированными вершинами С = (У,Е) [ ]. Для заданной вершины в € V необходимо найти длину кратчайшего и максимального пути = 1еп(Р), где Р = (в,... ,у) для всех V € V.
Для поиска кратчайших путей в классическом случае используются алгоритм переборного решения, алгоритм Дейкстры, алгоритм Флойда-Уоршелла, алгоритм Форда-Беллмана [21]. Для поиска кратчайших и максимальных путей подходит метод динамического программирования.
Динамическое программирование
Метод динамического программирования разбивает задачу на подзадачи, решает их, а далее объединяет решения [21]. Динамическое программирование эффективно тогда, когда решение текущей подзадачи зависит от предыдущих
1, если Зе = (VI, ^) : е € € V
0,
1.1.2 Постановка задачи
решений. Для поиска кратчайших и максимальных путей в ориентированном ациклическом графе используется Алгоритм 1.
Алгоритм в качестве атрибутов принимает матрицу смежности графаG, стартовую вершину s, число вершин в графе \V\. Алгоритм возвращает массив d с кратчайшими путями в графе.
Algorithm 1 Dynamic programming Require: G, s, \V\ Ensure: d d ^ [œ] d[s] ^ 0
for i = s, s + 1,..., \V\ do if d[i] < œ then
for j = i + 1,..., \ V \ do if G[i][j] > 0 then
d[j] ^ min(d[j], d[i] + w(i,j)) end if end for end if end for return d
Для поиска максимальных путей методом динамичексого программирования алгоритм поиска минимального значения заменяется алгоритмом поиска максимальных значений. Значения в массиве d заменятся на d ^ [-œ].
1.2 Задача бинарной классификации
Машинное обучение область искусственного интеллекта, изучающая способы обучения вычислительного устройства решать задачи самостоятельно на основе данных [44 47]. Главной целью машинного обучения является извлечение знаний из данных [48]. Машинное обучение находится на стыке таких наук, как математический анализ, теория вероятностей, математическая
статистика [48], численные методы, линейная алгебра, методы оптимизации, дискретный анализ и других наук [45].
Все алгоритмы для построения моделей машинного обучения можно разделить на два класса: обучение с учителем, обучение без учителя [45; 48 50]. Одной из задач обучения с учителем является задача классификации. [45; 49]. Классификация маркировка выборки на основе признаков [46].
1.2.1 Постановка задачи
Определение 14. Для некоторого целого числа к дан входной булевый набор X = (х1,... ,Хк) £ {ОДр. Дерево решений — это корневое дерево, в котором с каждой нелистовой вершиной связана переменная х^, исходящие дуги помечены как х^ = 0 ил и х^ = 1, с каждой листовой — некоторое действительное число от 0 до 1.
Процесс вычисления на дереве решений для, входного набора X организован следующим, образом. Вычисление начинается, с корня, который выбирается, текущей вершиной. Далее на каждом, следующем шаге текущей вершиной выбирается, та из дочерних вершин, в которую ведет дуга, соответствующая входному значению переменной х^ то ее ть х^ = 0 ил и х^ = 1. Результатом, вы,числения, является значение, записанное па листовой вершине, в которую приводит описанный процесс.
Определение 15. Для некоторого целого положительного N лесом деревьев решений называется набор из N деревьев решений: д1,...,д^. Для некоторого входного набора X = (х1,... ,хи) £ {ОДр результатом вычисления леса деревьев решений, для, X является значение
1 "
в(Х ) = туЕ 9<{Х),
{=1
где д{(Х) — результат вычисления на г-м дереве решений.
По аналогии с деревьями решений можно рассмотреть набор из N любых других алгоритмов. Такой набор называется ансамблем алгоритмов.
Определение 16. Для некоторого целого числа N и набора функций таких что ^ : {0,1}* ^ [0,1]; реализуемых некоторыми алгоритмами, ансамблем алгоритмов называется функция ]а : {0,1}* ^ [0,1] такая, что для некоторого входного набораХ € {0,1}*7 её результат вычисляется, как
1 М
!а(х ) = ^Е ).
г=\
В рамках данной работы рассматривается задача вычисления значения ансамбля алгоритмов и леса деревьев решений на некотором входном наборе. Исследуется её сложность в рамках различных вычислительных моделей. Данная задача имеет приложение в машинном обучении для задачи классификации и становится задачей прогнозирования для построенных алгоритмов (моделей) машинного обучения. Лес деревьев решений и ансамбль алгоритмов могут быть применены для задачи бинарной классификации.
Задача бинарной классификации
Определение 17. Задача бинарной классификации
Для некоторых целых положительных чисел п и к даны наборы X = (Х 1,...Хп), где Хг = (х\,...хгк) € {0,1}* и У = (у 1,...,уп) уг € {с 1а в в 0,с1а з з 1}. Строится функция / € Р, для, некоторого семейства функций, Р, такая, что минимизируется некоторая функция, ошибки Егг(Х ,У). Значение функции / : {0,1}* ^ [0,1] трактуется как вероятность принадлежности аргумента к с1авво. Для нового элемента Х € {0,1}*7 не встречающегося, в X, требуется вычислить значение у € {с 1а в в 0,с1а з <§1}. Вычисление значения у происходит следующим образом: если /(Х) > 0.57
= о = а 1
Пояснения к определению 17:
— Пара (X,У) называется тренировочным набором;
— Элементы Хг - объекты;
— Набор уг — классы объектов;
_ х'1, ...................... признаки (параметры, атрибуты) объекта Х;
Р
— Процесс выбора классификаторов f G F называют «обучением»;
— Процесс вычисления у = f (X) называют «прогнозированием»;
— Прогнозирование класса для аргумента — вычисление f : {0,1}^ ^ {class0,class1};
— Результат f'(X) = class0 тогда и только тогда, когда f (X) ^ 0.5
— Значения из множества {class0,classi} называют классами объектов, поэтому задачу называют классификацией, а функцию f — классификатором.
В общем случае Xг = (х\,... хгк) G D1 х Dk. Здесь Di = R ^^этеиия х\ можно представить в виде булевого набора, так как действительные числа можно представить в виде бинарной строки фиксированной длины, если сохранять их с некоторой точностью в двоичном виде. Приведенную постановку задачи можно считать универсальной.
В качестве функции ошибки Err можно использовать таблицу сопряженности. Пусть
со,о = |{г : f(Xг) = classo,yl = 0}|
со,1 = |{г : f(Xг) = class о,у1 = 1}|
С1,о = |{г : f(xг) = classиуг = 0}|
ci,i = |{г : f(Xг) = classi,yl = 1}|.
Тогда функция ошибки определяется как Err(X,Y) = од + 1?1 Таблица показывает, сколько раз модель классифицирует объекты тестовой выборки в каждый из классов, сколько из них классифицировано правильно и неправильно [47].
Пусть дано 100 тестовых объектов, которые необходимо распределить по двум классам: класс Ыавво и класс class17 и обученный классификатор. Пусть 49 из них относятся к class^ а 51 — к class1. Допустим, классификатор распределяет 45 объектов к classo., 10 из которых распределено неверно, а 55 объектов — к class17 14 из которых определены в class1 ошибочно. Таблица сопряжённости для этого классификатора представлена в таблице 1. Из таблицы следует, что классификатор возвращает класс корректно для 76 случаев из 100. По таблице сопряжённости можно проанализировать корректность прогнозирования для каждого класса в отдельности вычислить ряд показателей качества [47].
Таблица 1 Пример таблицы сопряжённости для задачи бинарной
к л ас си ф и кации
Спрогнозировано cíass0 Спрогнозировано cíassi Всего
Фактически cías s0 35 14 49
Фактически cías si 10 41 51
Всего 45 55 100
Деревья решений для задачи бинарной классификации
В качестве алгоритма для решения задачи бинарной классификации можно использовать деревья решений.
Один из алгоритмов построения дерева решений [45; 50] заключается в следующем: в каждой вершине рассматривается её поддерево как самостоятельное дерево. Каждое поддерево работает со своим подмножеством Data = (X', У')., в котором X' = (Х^1,... ), У' = (yj1,...,yje), где {i\,...,iр} С {1,... ,п}. Для каждой дочерней вершины такое множество подмножество обучающей выборки родительской вершины. Для любой вершины подмножества дочерних вершин не пересекаются. Шаги алгоритма:
1. Для корневой вершины выбрать атрибут, который даёт лучшую эффективность разбиения по заданному критерию;
2. В соответствии со значениями данного атрибута определить значения веток, которые проложат маршрут в дочерние вершины;
3. В соответствии со значениями на ветвях разделить обучающую выборку корневой вершины на непересекающиеся подмножества для дочерних вершин;
4. Повторить предыдущие шаги для дочерних вершин.
Представленный процесс построения дерева является рекурсивной функцией. Построение продолжается до тех пор, пока не будет выполнено условие остановки. В качестве условия остановки может быть достижение заданной высоты. Высота дерева является гиперпараметром модели. Гиперпараметр настройка алгоритма обучения модели. Гиперпараметры задаются до обучения модели [51; 52]. Другой пример критерия остановки одинаковый результат прогнозирования для всех объектов выборки данной вершины. Например, для задачи классификации все объекты из выборки вершины принадлежат одному классу [48].
Основные алгоритмы построения деревьев решений ЮЗ [53], С4.5 [54], С5.0 [55], алгоритм CART (Classification and regression trees) [15]. Последний не работает с категориальными признаками. Категориальные признаки являются не числовыми значениями, а перечислениями. В качестве примеров категориальных признаков можно привести цвет, форма, день недели, пол и другие [45; 48; 51]. Категориальные признаки можно перевести в последовательность бинарных значений. Известный метод представления категориальных признаков в бинарном виде алгоритм прямого кодирования, в литературе встречается как one-hot-кодирование [45; 48; 56].
Алгоритмы машинного обучения обладают такой характеристикой, как обобщённость [45]. Построенная модель должна уметь прогнозировать результат для любых входных данных, она должна обладать свойством обобщённости. С обобщённостью связаны два понятия переобучение и недообучение.
Похожие диссертационные работы по специальности «Другие cпециальности», 00.00.00 шифр ВАК
Комбинаторно-геометрические свойства полиэдров задач комбинаторной оптимизации2019 год, доктор наук Максименко Александр Николаевич
Моделирование динамических баз данных2016 год, кандидат наук Плетнев Александр Андреевич
Модели, методы и программные средства анализа сходства орграфов и их применение при исследовании темпоральных орграфов2016 год, кандидат наук Кохов Виктор Викторович
О некоторых подграфах графа бинарных отношений2016 год, кандидат наук Аль Джабри Халид Шиа Хайралла
Некоторые наследственные случаи полиномиальной и псевдополиномиальной разрешимости задач о вершинной раскраске графов2021 год, кандидат наук Развенская Ольга Олеговна
Список литературы диссертационного исследования кандидат наук Сафина Лилия Ильхамовна, 2025 год
с использованием
двоичной кучи 0(\Е| log |) О (IV |2)
Алгоритм Дейкстры
с использованием
Фибоначчиевой кучи OdV| log | + ^|) О (IУ|2)
Алгоритм
Форда-Беллмана OdV ЦЕ |)
Алгоритм
Флойда-Уоршелла - OdV |3)
Динамическое
11 рогр ам м и ров ai i и е OdV | + ^ |) OdV |2)
Квантовый алгоритм / \ / \
Дейкстры [22] О (log2 ^V||Д|] О (log2 ||У)
Квантовый алгоритм О (log ЦЕ|) О (log ||У)
Свойство 12. [21J Запросная сложность алгоритма поиска кратчайших путей в ориентированном ациклическом графе G = (V,, Е) с топологически отсортированным,и вершинами, основанный па динамическом программировании и использующий ,,матрицу смежности для, хранения графа, (Алгоритм, ) составляет 0(| V| 2) и в графе, представленного в виде списка, смежности,
0( | V | + | Е |).
Свойство 13. [22[ Запросная сложность квантового алгоритма поиска кратчайших пут,ей, в графе G = (V,E) составляem 0(\V| yJ\V| log2 ^|) для, матрицы смежности и /\VЦЕ| log2 ^|) для, списка смежности.
Теорема 8. За,проема,я слож.ностъ алгоритма поиска, кратчайших и, максимальных путей, (Алгоритмы 4 и 5) в ориентированном, ациклическом, графе С = (V,, Е) с топологически отсортированными вершинами составляет 0(\У\у/\У|) для графа, хранящегося в виде матрицы смежности, и ) для, графа, хранящегося в виде списка, смежности.
Доказательство. Матрица смежности. Для каждой вершины г Е {«+1, \ У \} запускается алгоритм поиска минимального/максимального значения Дюрра-Хойера. Запросная сложность алгоритма Дюрра-Хойера 0(л/\Щ) (согласно свойству ). Запросная сложность алгоритма составляет 0(\V\ \).
Список смежности. Пусть для вершины с номером г количество рёбер, которые входят в вершину г, равно Тогда запросная сложность алгоритма Дюрра-Хойера для вершины % 0(л/т1). Общая сложность алгоритма для графа
(\у\ \
равняется О ^ л/ш1 . По неравенству Коши-Буняковского [ ] сложность
У=1 ) _
алгоритма составляет 0(\/\У\\Е\). □
Теорема 9. Вероятность успеха, Алгоритм,ов 4, 5 для, задачи, поиска, кратчайших и, максимальных путей, от стартовой, вершины, до всех остальных во взвешенном ациклическом ориентированном графе С = (V, Е) с топологически отсортированными вершинами стремится к 0 при \ У\ ^ то.
Доказательство. Поиск минимального/максимального значения для каждой вершины является независимым событием. Вероятность успеха для каждой вершины % составляет^ = 0.5 + е (е > 0) по алгоритму Дюрра-Хойера. Следова-
I
тельно, вероятность успеха для всего графар = П = 0.5;, где I — количество
¡=1
рёбер, которые входят в путь от стартовой вершины до самой удалённой от неё вершины (по количеству рёбер), I ^ \У\, так как в пути может быть не более \У\ вершин, поэтому вероятность успеха для каждой вершины в графе:
* = 2) = 2^1)
и стремится к 0 при \У\ ^ то. □
Теорема 10. Запросная сложность квантового алгоритма, (Алгоритм, 6) поиска, кратчайших и, максимальных путей, в ориентированном, ациклическом, графе С = (V, Е) с топологически отсортированными вершинами составляет
||У)
для графа, хранящегося в виде матрицы смежности, и для, графа, хранящегося в виде списка смежности.
Доказательство. Для увеличения вероятности успеха алгоритма Дюрра-Хой-ера Алгоритм 6 запускает поиск минимального/максимального значения некоторое целое положительное число I раз. Пусть I = IV|. В таком случае в соответствии с теоремой 8 запросные сложности составляют:
для способа храненя графа матрицей смежности и
списком смежности соответственно. □
Теорема 11. Вероятность успеха улучшенного алгоритма (Алгоритм, 6) для,
"Л (у (у
задачи поиска кратчайших и максимальны,х путей от стартовой вершины до всех остальных во взвешенном ациклическом ориентированном графе С = (V., Е) с топологически отсортированными вершинами с заданным значением I = 2^2 ^Стремится к 1 при | ^ то.
Доказательство. Вероятность того, что среди I запусков алгоритма Дюрра-Хойера ни разу не найдено минимальное/максимальное значение, равна
Г-1 - 1 1
2l 221°g2I \V |2'
Следовательно, вероятность найти минимальное или максимальное значение для вершины с номером г равна Pi = 1 — г = 1 — Щ2, а Для графа вероятность
( 1 I ( 1 I
успеха составляет р = i 1 — j , lim i 1 — = 1.
□
В таблице 12 собраны рассмотренные способы решения задачи поиска кратчайших путей в ориентированном взвешенном графе из заданной вершины до всех остальных с топологически отсортированными индексами вершин. Для поиска максимальных путей могут быть использованы алгоритм динамического программирования и квантовый алгоритм, предложенный в работе.
Ранее квантовых алгоритмов для поиска максимальных путей и их анализ сложности не были предложены.
4.3 Выводы по четвертой главе
В данной главе предложены алгоритмы поиска кратчайших и максимальных путей в ориентированном ациклическом взвешенном графе из заданной вершины. Алгоритмы за счет свойств квантовых систем имеют меньшую запросную сложность по сравнению с их детерминированными версиями. Алгоритм поиска кратчайших путей из заданной вершины использует квантовый алгоритм поиска минимального значения, основанный на алгоритме Гровера. С помощью квантового оператора усиления амплитуды наименьшего значения в последовательности осуществляется поиск кратчайшего пути для каждой достижимой из заданной вершины.
В главе приведен анализ запросных сложностей детерминированного и квантового алгоритмов. Запросная сложность квантового алгоритма обладает меньшей запросной сложностью известных детерминированных и квантовых подходов. Запросная сложность предложенного квантового алгоритма составляет 0(log \У\\У\ \) для графа, хранящегося в виде матрицв1 смежности, и
|У\vWPI)
для графа, хранящегося в виде списка смежности. Алгоритм основан на методе динамического программирования. В детерминированном случае сложность составляет: О (|У\2) (граф хранится в виде матрицв1 смежности) и О (\У\ + \Е\) (граф хранится в виде списка смежности).
Свойства квантовых вычислений применимы во многих сферах теоретических и прикладных задач, в том числе для задач из теории графов и машинного обучения. Актуальность квантового машинного обучения и применения квантовых вычислений в задачах из теории графов подтверждается числом научных работ за последние три десятилетия. Работы над созданием квантового устройства ведутся крупными мировыми компаниями и правительствами ведущих стран.
В данной работе предложены алгоритмы поиска кратчайших и максимальных путей в ориентированном ациклическом взвешенном графе и алгоритм прогнозирования для задачи бинарной классификации ансамблевой моделью, основанные на квантовом параллелизме и усилении амплитуды.
Представленный в работе алгоритм поиска кратчайших и максимальных путей в ориентированном ациклическом взвешенном графе С = (V, Е) из заданной вершины до всех остальных с топологически отсортированными вершинами, основанный на усилении амплитуды квантового состояния с заданными свойствами, обладает меньшей запросной сложностью её детерминированной версии. Запросная сложность детерминированного алгоритма, основанного на динамическом программировании, составляет 0(\У\ + \Е\), запросная сложность квантовой версии — \У \ \/\У \ • \Е\), если граф хра-
нится в виде списка смежности. Для графа, хранящегося в виде матрицы смежности, сложности составляют 0(\V\2) в детерминированном случае и 0(log \ V \ • \ V \ • \ V \) в квантовой версии соответственно.
В детерминированном случае запросная сложность алгоритма прогнозирования для задачи классификации ансамблевой моделью составляет 0(Ы• Т(&)), где N — число классификаторов ансамбля, а 0(Т(к)) — запросная сложность прогнозирования на одном классификаторе для входного объекта с к атрибутами. Запросная сложность алгоритма прогнозирования, основанного на квантовом параллелизме, составляет 0(Т(к)).
В работе предложены способы оценки амплитуды квантового состояния, соответствующей вероятности принадлежности заданному классу для ансамблевых моделей. Алгоритмы прогнозирования и оценки вероятности реализованы в виде матричного представления и квантовых схем.
Важной задачей при создании квантовой схемы является оптимизация схемы по числу элементарных квантовых гейтов. Число квантовых операторов влияет на скорость работы и на её корректность. В качестве базиса элементарных квантовых гейтов принято рассматривать все однокубитные операторы и контролируемое отрицание, гейт С NOT. В работе применены модифицированные техники оптимизации схем по числу контролируемых отрицаний.
При универсальной декомпозиции квантовой схемы на элементарные гейты используется О (4 1 ) С NOT операторов и столько же однокубитных, где I — число используемых в квантовой схеме квантовых битов. Для оценки гей-товой сложности использована квантовая схема прогнозирования для задачи бинарной классификации моделью случайный лес для объектов с бинарными атрибутами. Гейтовая сложность схемы составляет О (4h+log2N) контролируемых отрицаний, где h — заданный параметр высота деревьев в лесу, |log2 N] число кубитов, отведенных на хранение индекса дерева для числа деревьев N. Тогда значение степени в общем случае декомпозици I = h + log2 N + к + 3, где к = |ж| — число атрибутов входного объекта х. Гейтовая оценка полученной схемы меньше общего случая.
В работе предложены модифицированные техники оптимизации квантовой схемы прогнозирования, благодаря которым получена гейтовая сложность 0(2log2N+h • h). Техники основаны на изменении структур данных, применении разных алгоритмов декомпозиции многоконтролируемых операторов отрицания, применении равномерно управляемых операторов UCG и другие.
В будущем планируется рассмотреть другие модели машинного обучения, реализовать квантовые схемы для них, проанализировать их и протестировать на разных выборках. Планируется расширить квантовый алгоритм прогнозирования для задачи многоклассовой классификации.
В заключении работы выражаю благодарность научному руководителю — Хадиеву Камилю Равилевичу, а также наставникам — Аблаеву Фариду Манс-уровичу, Васильеву Александру Валерьевичу, Гайнутдиновой Аиде Фаритовне, и коллегам — Хадиевой Алие Ихсановне, Маннапову Ильназу Магсумовичу, Зиннатуллину Илнару Гумаровичу, Зиятдинову Мансуру Тагировичу.
1. Гайнутдинова, А. Квантовые вычисления. Учебно-методическое пособие. Т. 73 / А. Гайнутдинова. Казанский гос. ун-т, 2007.
2. Jordan, S. Quantum Algorithms Zoo / S. Jordan. 2023. http://quantumalgorithmzoo.org/.
3. Shor, P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer / P. Shor // SIAM review. 1999.
T. 41, № 2. C. 303 332.
4. Grover, L. K. A fast quantum mechanical algorithm for database search / L. K. Grover. ACM, 1996.
5. Elementary gates for quantum computation / A. Barenco [и др.] // Physical review A. 1995. T. 52, № 5. C. 3457.
6. On quantum methods for machine learning problems part I: Quantum tools / F. Ablayev [и др.] // Big Data Mining and Analytics. 2019. Т. 3, № 1. C. 41 55.
7. Ambainis, A. Understanding quantum algorithms via query complexity / A. Ambainis // Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018. 2018. C. 3265 3285.
8. Wolf, R. de. Quantum computing and communication complexity / R. de Wolf. 2001.
9. Strengths and weaknesses of quantum computing / C. Bennett [и др.] // SIAM journal on Computing. 1997. T. 26, № 5. C. 1510 1523.
10. Kopczyk, D. Quantum machine learning for data scientists / D. Kopczyk // arXiv preprint arXiv:1804.10068. 2018.
11. Schuld, M. An introduction to quantum machine learning / M. Schuld, I. Sinayskiy, F. Petruccione // Contemporary Physics. 2015. T. 56, № 2. C. 172 185.
12. Quantum machine learning / J. Biamonte [и др.] // Nature. 2017. Т. 549, № 7671. URL: http://dx.doi.org/10.1038/nature23474.
14. Чистяков, С. Случайные леса: обзор / С. Чистяков // Труды Карельского научного центра Российской академии наук. — 2013. — № 1. — С. 117-136.
15. Breiman, L. Classification and regression trees / L. Breiman. — Routledge, 2017.
16. Lu, S. Quantum decision tree classifier / S. Lu, S. Braunstein // Quantum information processing. — 2014. — T. 13, № 3. — C. 757 770.
17. Heese, R. Representation of binary classification trees with binary features by quantum circuits / R. Heese, P. Bickert, A. Niederle // Quantum. — 2022. — T. 6. - C. 676.
18. Khadiev, K. Classical and Quantum Improvements of Generic Decision Tree Constructing Algorithm for Classification Problem / K. Khadiev, I. Mannapov, L. Safina // CEUR Workshop Proceedings. — 2021. — T. 2842. - C. 83 93.
19. Khadiev, K. The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0 / K. Khadiev, I. Mannapov, L. Safina // CEUR Workshop Proceedings. - 2019. - T. 2500.
20. Диет,ель, P. Теория графов. / P. Дистель. — Новосибирск : Изд-во Ин-та математики, 2002.
21. Алгоритмы. Построение и анализ:[пер. с англ.] / Т. Кормен [и др.]. — Издательский дом Вильяме, 2009.
22. Quantum query complexity of some graph problems / C. Durr [и др.] // SIAM Journal on Computing. - 2006. - T. 35, № 6. - C. 1310^1328.
23. Quantum speedups for exponential-time dynamic programming algorithms / A. Ambainis [и др.] // Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. — SIAM. 2019. — C. 1783^1793.
24. Ambainis, A. Quantum algorithms for matching and network flows / A. Ambainis, R. Spalek // Annual Symposium on Theoretical Aspects of Computer Science. - 2006. - C. 172^183.
26. Combinatorial optimization: polyhedra and efficiency. T. 24 / A. Schrijver [h /i,p.]. — Springer, 2003.
27. Introduction to Algorithms / T. H. Cormen [h ,np.]. — McGraw-Hill, 2001.
28. Quantum amplitude amplification and estimation / G. Brassard [h ,np.] // Contemporary Mathematics. - 2002. - T. 305. - C. 53-74.
29. Mottonen, M. Decompositions of general quantum gates / M. Mottonen, J. Vartiainen // Trends in Quantum Computing Research. — 2006. — C. 149.
30. Safina, L. Quantum Amplitude Amplification Algorithm Simulation for Prediction of a Binary Classification Problem / L. Safina // Lobachevskii Journal of Mathematics. - 2023. - T. 44, № 2. - C. 747-756.
31. Khadiev, K. Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs / K. Khadiev, L. Safina // Lecture Notes in Computer Science. — 2019. - T. 11493. - C. 150-163.
32. Khadiev, K. Quantum algorithm for shortest path search in directed acyclic graph / K. Khadiev, L. Safina // Moscow University Computational Mathematics and Cybernetics. - 2019. - T. 43. - C. 47-51.
33. Khadiev, K. Quantum algorithm for dynamic programming approach for DAGs and applications / K. Khadiev, L. Safina // Lobachevskii Journal of Mathematics. - 2023. - T. 44, № 2. - C. 699-712.
34. Quantum Circuit for Random Forest Prediction / L. Safina [h ,np.] // Russian Microelectronics. - 2023. - S384-S389.
35. Khadiev, K. The quantum version of prediction for binary classification problem by ensemble methods / K. Khadiev, L. Safina // Proc. SPIE. —
2022. - T. 12157, № 1215726. - C. 595-603.
36. Khadiev, K. The quantum version of random forest model for binary classification problem / K. Khadiev, L. Safina // CEUR Workshop Proc. — 2021. - T. 2842. - C. 30-35.
37. Хадиев, К. Эксперимент на квантовом симуляторе для задачи прогнозирования бинарной классификации ансамблевыми методами / К. Хадиев, Л. Сафипа // Дискретная математика и ее приложения. — 2022. — Т. 14. - С. 104—106.
38. Квантовая реализация предсказания задачи бинарной классификации методом случайный лес на qiskit / Л. Сафипа [и др.] // Материалы конференции Дискретные модели в теории управляющих систем. — 2023. — С. 87^90.
39. Маннапов, И. Квантовое улучшение алгоритма построения деревьев решений с5. 0 для задач классификации / И. Маннапов, Л. Сафина, К. Хадиев // Материалы XIII Международного семинара Дискретная математика и ее приложенияё имени академика ОБ Лупанова (Москва, МГУ, 17-22 июня 2019 г.) - 2019. - Т. 17. - С. 135.
40. Свидетельство о гос. регистрации программы для ЭВМ Программа квантового алгоритма прогнозирования для задачи бинарной классификации, базирующаяся на модели случайный лес / К. Хадиев, Л. Сафина ; ФГАОУВО КФУ. - № 2023682991 ; заявл. 30.10.2023 ; опубл. 21.11.2023, 2023684985 (Рос. Федерация).
41. Хадиев, К. КВАНТОВЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ ПОИСКА КРАТЧАЙШЕГО ПУТИ В ОРИЕНТИРОВАННОМ АЦИКЛИЧЕСКОМ ГРАФЕ / К. Хадиев, Л. Сафина // Дискретные модели в теории управляющих систем. — 2018. — С. 263 266.
42. Зыков, А. Основы теории графов / А. Зыков. — Москва, Книга по Требованию, 2013.
43. Harary, F. Acyclic Digraph. §8.8 in Graphical Enumeration / F. Harary, E. Palmer. — New York: Academic Press, 1973. — C. 191—194.
44. Smola, A. Introduction to machine learning / A. Smola, S. Vishwanathan. — 2008.
45. Теория и практика машинного обучения / В. Воронина [и др.]. — Ульяновск : УлГТУ, 2017. - 290 с.
46. Харрисощ М. Машинное обучение. Карманный справочник. Краткое руководство по методам структурированного машинного / М. Харрисон. — ООО "Диалектика", 2020. - 322 с.
47. Флат,, 77. Машинное обучение. Наука и искусство построения алгоритмов, которые извлекают знания из данных / П. Флах. 2015. 402 с.
48. Мюллер, А. Введение в машинное обучение с помощью Python / А. Мюллер, С. Гвидо. 2017. 393 с.
49. Brownlee, J. Master Machine Learning Algorithms / J. Brownlee. 2016. 163 p.
50. Harrington, P. Machine Learning in Action / P. Harrington. Manning Publications Co, 2012. 382 p.
51. Альбоп, К. Машинное обучение с использованием Python. Сборник рецептов / К. Альбон. СПб.: БХВ-Петербург, 2019. 384 с.
52. Настройка гиперпараметров для модели, https://docs.microsoft.com/ru-ru/azure/machine-learning/how-to-tune-hyperparameters.
53. Peng, W. An implementation of ID3-decision tree learning algorithm / W. Peng, J. Chen, H. Zhou // From web. arch. usyd. edu. au/wpeng/DecisionTree2. pdf Retrieved date: May. 2009. T. 13.
54. Quinlan, J. R. Improved Use of Continuous Attributes in C4.5 / J. R. Quin-lan // Journal of Artificial Intelligence Research. 1996. P. 77 90.
55. C5.0: An Informal Tutorial. 2019. url — https://www.rulequest.com/see5-unix.html.
56. Brownlee, J. Why One-Hot Encode Data in Machine Learning? / J. Brownlee // Machinelearning mastery. 2017.
57. Воронцов, К. Математические методы обучения по прецедентам (теория обучения машин) / К. Воронцов // Москва. 2011. С. 119 121.
58. Everitt, В. The Cambridge dictionary of statistics, fourth edition / B. Everitt, A. Skrondal. Cambridge University Press, 2010.
59. Kingsford,, C. What are decision trees? / C. Kingsford, S. Salzberg //. 2008.
60. Song, Y. Decision tree methods: applications for classification and prediction / Y. Song, Y. Lu // Shanghai Archives of Psychiatry. 2015. Vol. 27. P. 130 135.
61. Roth, D. Decision Trees / D. Roth. Shri Sant Gajanan Maharaj College of Engineering, 2016.
62. Фофанов, О. Алгоритмы и структуры данных: учебное пособие / О. Фофанов. Издательство Томского политехнического университета, 2014. 126 с.
63. Opitz, D. Popular ensemble methods: An empirical study / D. Opitz, R. Maclin // Journal of artificial intelligence research. 1999. T. 11. C. 169 198.
64. Zhou, Z. Ensemble methods: foundations and algorithms / Z. Zhou. CRC press, 2012.
65. Вгелтащ L. Random forests / L. Breiman. 2001.
66. Biau, G. A random forest guided tour / G. Biau, E. Scornet. TEST 25, 2016.
67. Qi, Y. Random forest for bioinformatics / Y. Qi // Ensemble machine learning: Methods and applications. 2012. C. 307 323.
68. Overview of random forest methodology and practical guidance with emphasis on computational biology and bioinformatics / A. Boulesteix [и др.] // Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. 2012. T. 2, № 6. C. 493 507.
69. Random forest with 200 selected features: An optimal model for bioinformatics research / R. Wald [и др.] //. Т. 1. IEEE. 2013.
С. 154 160.
70. Prediction of protein RNA binding sites by a random forest method with combined features / Z. Liu [и др.] // Bioinformatics. 2010. T. 26, № 13. C. 1616 1622.
71. Википедия. Свободная энциклопедия. https://ru.wikipedia.org/wiki/.
72. Lewoniewski, W. Analysis of references across Wikipedia languages / W. Lewoniewski, K. Wkecel, W. Abramowicz // Information and Software Technologies: 23rd International Conference, ICIST 2017, Druskininkai, Lithuania, October 12 14, 2017, Proceedings. Springer. 2017.
C. 561 573.
73. Lewoniewski, W. Quality and importance of Wikipedia articles in different languages / W. Lewoniewski, K. W^cel, W. Abramowicz // Information and Software Technologies: 22nd International Conference, ICIST 2016, Druskininkai, Lithuania, October 13-15, 2016, Proceedings 22. — Springer. 2016. - C. 613 624.
74. Warncke- Wang, M. Tell me more: an actionable quality model for Wikipedia / M. Warncke-Wang, D. Cosley, J. Riedl // Proceedings of the 9th International Symposium on Open Collaboration. — 2013. — C. 1—10.
75. Фомина, E. Использование алгоритма random forest для обработки социально-экономических данных / Е. Фомина // Вестник Пермского национального исследовательского политехнического университета. Социально-экономические науки. — 2022. — № 1. — С. 142 153.
76. Early detection of depression: social network analysis and random forest techniques / F. Cacheda [и др.] // Journal of medical Internet research. — 2019. - T. 21, № 6. - el2554.
77. Karthika, P. Sentiment analysis of social media network using random forest algorithm / P. Karthika, R. Murugeswari, R. Manoranjithem // 2019 IEEE international conference on intelligent techniques in control, optimization and signal processing (INCOS). - IEEE. 2019. - C. 1-5.
78. Financial fraud detection model: Based on random forest / C. Liu [и др.] // International journal of economics and finance. — 2015. — T. 7, № 7.
79. Zou, Z. The application of random forest in finance / Z. Zou, H. Peng, L. Luo // Applied Mechanics and Materials. - 2015. - T. 740. - C. 947-951.
80. Random forests for classification in ecology / D. Cutler [и др.] // Ecology. — 2007. - T. 88, № 11. - C. 2783-2792.
81. Assessing the accuracy and stability of variable selection methods for random forest modeling in ecology / E. Fox [и др.] // Environmental monitoring and assessment. - 2017. - T. 189. - C. 1-20.
82. The relative importance of race compared to health care and social factors in predicting prostate cancer mortality: a random forest approach / H. Hanson [и др.] // The Journal of urology. - 2019. - T. 202, № 6. - C. 1209-1216.
83. Using random forest for reliable classification and cost-sensitive learning for medical diagnosis / F. Yang [и др.] // BMC bioinformatics. 2009. Т. 10, № 1. С. 1 14.
84. Risk prediction of type II diabetes based on random forest model / W. Xu [и др.] // 2017 Third International Conference on Advances in Electrical, Electronics, Information, Communication and Bio-Informatics (AEEICB). 2017. C. 382 386.
85. Oshiro, Т. M. How many trees in a random forest?. In International workshop on machine learning and data mining in pattern recognition / Т. M. Oshiro, P. S. Perez, J. A. Baranauskas. 2012.
86. Основы квантовых вычислений. Учебное пособие / С. Торгаев [и др.]. Издательство STT, 2020.
87. Кулик, С. Введение в теорию квантовых вычислений / С. Кулик, А. Верков, В. Яковлев. 2008.
88. Чивилихин, С. Квантовая информатика / С. Чивилихин // Университет ИТМО. 2009.
89. Корн, Г. Справочник по математике для научных работников и инженеров / Г. Корн, Т. Корн. 1973.
90. Kyrillidis, A. Introduction to quantum computing: Bloch sphere / A. Kyrillidis // URL: http://akyrillidis.github.io/notes/quant_post_7. 2019.
91. Прескилл, Д. Квантовая информация и квантовые вычисления. Т. 1 / Д. Прескилл. 2008.
92. Новиков, Ф. Дискретная математика: Учебник для вузов. Стандарт третьего поколения / Ф. Новиков. Издательский дом "Питер", 2011.
93. Яблонский, С. Введение в дискретную математику / С. Яблонский. Высш. шк., 2010.
94. Qiskit. url—https://qiskit.org/.
95. Vartiainen, J. Efficient decomposition of quantum gates / J. Vartiainen, M. Mottonen, M. Salomaa // Physical review letters. 2004. T. 92, № 17. URL: https://link.aps.org/doi/10.1103/PhysRevLett.92.177902.
96. Менский, М. Явление декогеренции и теория непрерывных квантовых измерений / М. Менский // Успехи физических наук. 1998. Т. 168, № 9. С. 1017 1035.
97. Knill, Е. Approximation by quantum circuits / E. Knill // arXiv preprint quant-ph/9508006. 1995.
98. Black, P. Gray code / P. Black // From Dictionary of Algorithms and Data Structures. 2005.
99. Прихожлщ А. Обобщение разложения Шеннона для частично определенных функций: теория и применение / А. Прихожий // Системный анализ и прикладная информатика. 2013. № 1/2. С. 6 11.
100. Shende, V. V. Synthesis of quantum logic circuits / V. V. Shende, S. S. Bullock, I. L. Markov // Proceedings of the 2005 Asia and South Pacific Design Automation Conference. 2005. C. 272 275.
101. Shende, V. Smaller two-qubit circuits for quantum communication and computation / V. Shende, I. Markov, S. Bullock // Proceedings Design, Automation and Test in Europe Conference and Exhibition. T. 2. 2004. 980 985 Vol.2.
102. Shende, V. Minimal universal two-qubit controlled-NOT-based circuits / V. Shende, I. Markov, S. Bullock // Phys. Rev. A. 2004. Июнь.
T. 69, вып. 6. С. 062321. URL: https://link.aps.org/doi/10.1103/ PhysRevA.69.062321.
103. Deutsche D. Rapid solution of problems by quantum computation / D. Deutsch, R. Jozsa // Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences. 1992. T. 439, № 1907. C. 553 558.
104. Formalized Operators with Phase Encoding / N. Raychev [и др.] // Journal of Quantum Information Science. 2015. T. 5, № 03. C. 114.
105. An introduction to quantum machine learning for engineers / O. Simeone [и др.] // Foundations and Trends in Signal Processing. 2022. T. 16, № 1/2. С. 1 223.
106. Diirr, C. A quantum algorithm for finding the minimum / C. Diirr, P. Hoyer // arXiv:quant-ph/9607014. 1996.
107. Кандидов, В. Дискретное преобразование Фурье / В. Кандидов, С. Чес-ноков, С. Шленов // Москва. — 2019.
108. Ambainis, A. Quantum lower bounds by quantum arguments / A. Ambainis // Proceedings of the thirty-second annual ACM symposium on Theory of computing. — 2000. — C. 636—643.
109. Born, S. Quantum Algorithms for Matching Problems / S. Dorn // Theory Comput. Syst. - 2009. - T. 45, № 3. - C. 613-628.
110. Окулов, С. Дискретная математика. Теория и практика решения задач по информатике / С. Окулов. — Litres, 2014.
111. Hamerly, G. Accelerating Lloyd's algorithm for k-means clustering / G. Hamerly, J. Drake // Partitional clustering algorithms. — 2015. — 0. 41-78.
112. Analysis of k-means and k-medoids algorithm for big data / P. Arora, S. Varshney [и др.] // Procedia Computer Science. — 2016. — T. 78. — C. 507-512.
113. Aimeur, E. Quantum clustering algorithms / E. Aimeur, G. Brassard, S. Gambs // Proceedings of the 24th international conference on machine learning. - 2007. - C. 1-8.
114. Quantum optimization for training support vector machines / D. Anguita [и др.] // Neural Networks. - 2003. - T. 16, № 5/6. - C. 763-770.
115. Lloyd, S. Quantum principal component analysis / S. Lloyd, M. Mohseni, P. Rebentrost // Nature Physics. - 2014. - T. 10, № 9. - C. 631-633.
116. Trugenberger, C. A. Quantum pattern recognition / C. A. Trugenberger // Quantum Information Processing. — 2002. — Т. 1. — C. 471 493.
117. Wiebe, N. Quantum nearest-neighbor algorithms for machine learning / N. Wiebe, A. Kapoor, K. Svore // Quantum information and computation. — 2015. - T. 15, № 3/4. - C. 318-358.
118. Lloyd, S. Quantum algorithms for supervised and unsupervised machine learning / S. Lloyd, M. Mohseni, P. Rebentrost // arXiv preprint arXiv:1307.0411. - 2013.
119. Романовский, И. Дискретный анализ / И. Романовский. — Невский Диалект, 2008.
120. Eddy, S. What is a hidden Markov model? / S. Eddy // Nature echnology. 2004. T. 22, № 10. C. 1315 1316.
121. Hidden quantum markov models and open quantum systems with instantaneous feedback / L. Clark [и др.] // ISCS 2014: Interdisciplinary Symposium on Complex Systems. Springer. 2015. C. 143 151.
122. Monras, A. Hidden quantum Markov models and non-adaptive read-out of many-body states / A. Monras, A. Beige, K. Wiesner // arXiv preprint arXiv:1002.2337. 2010.
123. Harrow, A. Quantum algorithm for linear systems of equations / A. Harrow, A. Hassidim, S. Lloyd // Physical review letters. 2009. T. 103, № 15. C. 150502.
124. Кугаевских, А. Классические методы машинного обучения / А. Кугаев-ских, Д. Муромцев, О. Кирсанова // СПб.: Университет ИТМО. 2022. Т. 53.
125. Smith., L. A tutorial on principal components analysis / L. Smith. 2002.
126. Kerenidis, /. Quantum recommendation systems / I. Kerenidis, A. Prakash // arXiv preprint arXiv:1603.08675. 2016.
127. Prakash, A. Quantum algorithms for linear algebra and machine learning / A. Prakash. University of California, Berkeley, 2014.
128. An analytical review of quantum neural network models and relevant research / S. Chakraborty [и др.] // 2020 5th International Conference on Communication and Electronics Systems (ICCES). IEEE. 2020.
C. 1395 1400.
129. Quantum-inspired algorithms in practice / J. Arrazola [и др.] // Quantum. 2020. Авг. Т. 4. С. 307. URL: http://dx.doi.org/10.22331/q-2020-08-13-307.
130. Gilyen, A. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension / A. Gilyen, S. Lloyd, E. Tang. 2018. arXiv: 1811.04909 [cs.DS],
131. Chi a, N. Quantum-inspired sublinear classical algorithms for solving low-rank linear systems / N. Chia, H. Lin, C. Wang. 2018. arXiv: 1811.04852 [cs.DS],
132. Tang, E. A quantum-inspired classical algorithm for recommendation systems / E. Tang // Proceedings of the 51st annual ACM SIGACT symposium on theory of computing. 2019. C. 217 228.
133. Harper, F. The movielens datasets: History and context / F. Harper, J. Konstan // Acm transactions on interactive intelligent systems (tiis). 2015. T. 5, № 4. С. 1 19.
134. Qiskit. Controlled-RY gate. url — https://docs.quantum.ibm.com/api/qiskit/qiskit.circuit.library.CRYGate.
135. Qiskit. MCXRecursive. url— https://github.eom/Qiskit/qiskit/blob/stable/l.l/ circuit/library/standard_gates/x.py#L1303-L1389.
136. Song, G. The simplified Toffoli gate implementation by Margolus is optimal / G. Song, A. Klappenecker. 2003. arXiv: quant-ph/0312225 [quant-ph]. URL: https://arxiv.org/abs/quant-ph/0312225.
137. Qiskit. MCXVChain. url—https://github.eom/Qiskit/qiskit/blob/stable/l.l/ qiskit/ (nmiit//library/standard_gates/x.py#L1392-L1538.
138. Qiskit. UCGate. url—https://docs.quantum.ibm.com/api/qiskit/ qiskit. circuit. library.UCGate.
139. Quantum circuits with uniformly controlled one-qubit gates / V. Bergholm [и др.] // Physical Review A. 2005. T. 71, № 5. C. 052330.
140. Maslov, D. On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization / D. Maslov // Phys. Rev. A. 2015. T. 93.
141. Qiskit. Controlled-Z gate. url — https://docs.quantum.ibm.com/api/qiskit/qiskit.circuit.library.CZGate.
142. Transformation of quantum states using uniformly controlled rotations / M. Mottonen [и др.] // Quantum Information & Computation. 2005.
T. 5. C. 467 473.
143. Седракяп, H. Неравенства. Методы доказательства / H. Седракян, А. Аво-ян, Г. Григорян. 2002.
144. Koh.avi, R. Data Mining and Visualization, Silicon Graphics / R. Kohavi, B. Becker. url—http://www.census.gov/ftp/pub/DES/ www/welcome.html.
145. Machine Learning Repository. Adult Data Set. — url=http://archive.ics.uci. edu nil datasets Adult.
146. Kohavi, R. Scaling Up the Accuracy of Naive-Bayes Classifiers: a Decision-Tree Hybrid / R. Kohavi // Proceedings of the Second International Conference on Knowledge Discovery and Data Mining. — 1996. — to appear.
147. Scikit-learn. Machine Learning in Python. — url https: / / scikit-learn.org/stable/.
148. NumPy. The fundamental package for scientific computing with Python. — url littps: /numpy.org/.
149. Pandas. —url littps: pandas.pydata.org .
150. sklearn.preprocessing.OneHotEncoder. — url=https: / / scikit-learn.org/stable/ modules/generated/sklearn.preprocessing.OneHotEncoder.html.
151. A survey on datasets for fairness-aware machine learning / T. Quy [и др.] // WIREs Data Mining and Knowledge Discovery. — 2022. — Март. — T. 12, № 3.
152. Chapter 3 Homework: Exploratory Data Analysis. — url https: / / rstudio-pubs-static.s3.amazonaws.com /352061_0ab7663711cc4b0e978325daca8c2b3f.html.
153. Census Data Project - Part 1: Cleaning and Preprocessing the Data. — url littp: / rstudio-pubs-static.s3.amazonaws.com/ 265200_a8d21a65d3d34b979c5aafb0del0c221.htmll_introduction.
154. RPubs by RStudio. — url littps: rpubs.com juliaHuynh / datapreprocess-assignment3.
155. Chakrabarty, N. A statistical approach to adult census income level prediction / N. Chakrabarty, S. Biswas // International Conference on Advances in Computing, Communication Control and Networking (ICACCCN). - IEEE. 2018. - C. 207-212.
156. Lerman, R. A note on the calculation and interpretation of the Gini index / R. Lerman, S. Yitzhaki. — 1984.
157. A.ro. А. Построение и анализ вычислительных алгоритмов / А. Ахо, Д. Хопкрофт, Д. Ульман. — Москва : МИР, 1979. — 536 с.
Приложение А
Матричное представление квантового прогнозирования. Задача
adult
В данной работе предлагается квантовый алгоритм прогнозирования для задачи бинарной классификации ансамблевыми моделями. Алгоритм прогнозирования протестирован на искусственно созданной задаче бинарной классификации, а также на известной выборке данных: задача adult [144; 145]. В задаче предлагается по социальным характеристикам человека определить, является ли его доход более 50 ООО долларов в год.
В работе [146] предложены первые решения для задачи adult. Использованы такие алгоритмы, как деревья решений, байесовские модели, алгоритмы fc-ближайших соседей и другие. В данной работе, в её практической части, в качестве ансамблевой модели машинного обучения использован случайный лес.
Чтобы проанализировать матричное представление квантового алгоритма прогнозирования, необходимо предобработать данные, обучить ансамблевую модель, осуществить прогноз на обученной модели для тестовых элементов. Для реализации матричного представления прогнозирования необходимо вычислить вероятности принадлежности тестовых объектов к каждому из классов для каждой листовой вершины. Вектор вероятностей получен инструментами sklearn.
Согласно алгоритму прогнозирования на регистры из формулы (2.2) действуют оператор Уолша-Адамара и оператор прогнозирования каждого дерева, как показано в формуле (2.4). После применения операторов получено состояние |"ф) из уравнения ( ). Эти два квантовых регистра в матричном виде представляются вектором амплитуд размерности 2п+1, где п = |log2 N], а N — число деревьев модели случайный лес. Для подготовки состояния |"ф) создан вектор вещественных значений согласно уравнению (2.6).
Алгоритм прогнозирования подготавливает состояние |"ф) = А|0). Далее на состояние |"ф) действует оператор QSearch, использующий алгоритм усиления амплитуды. В матричном виде диффузия вычисляется по формуле: D = 2 • |"ф)("ф| — I, где I — оператор тождественности [8] (матричное пред-
ставление в формуле (1.5)). Матричное представление оператора обращения к оракулу представлено в уравнении (2.7).
Для предобработки данных и обучения модели выбран язык программирования Python, библиотеки: scikit-learn (sklearn) [147], numpy [148] и pandas [149]. Для хранения и обработки данных использована структура данных DataFrame из библиотеки pandas. Данная структура содержит метод, позволяющий удалить все элементы, содержащие пустые ячейки. Так как модели из библиотеки scikit-learn в процессе обучения работают только с числовыми значениями, нужно преобразовать категориальные признаки в их числовое представление.
Выборка adult содержит числовые и категориальные признаки:
— Age (возраст) числовой признак;
— Workclass (тип места работы) категориальный признак, количество уникальных значений 8;
— Fnlwgt (социальный характеристический вес, учитывающий демографические особенности населения): числовой признак;
— Education (образование) категориальный признак, количество уникальных значений 16;
— Marital-status (семейное положение) категориальный признак, количество уникальных значений 7;
— Occupation (вид занятости) категориальный признак, количество уникальных значений 14;
— Relationship (наименование члена в семье) категориальный признак, количество уникальных значений 6.
— Race (раса) категориальный признак, количество уникальных значений 5.
— Sex (пол) категориальный признак, количество уникальных значений 2;
— Capital-gain (годовые накопления) числовой признак;
— Capital-loss (годовые расходы) числовой признак;
— Hours-per-week (количество рабочих часов в неделю) числовой признак;
— Native-country (родная страна) категориальный признак, количество уникальных значений 41.
Для того чтобы категориальные признаки хранить в качестве числовых значений, использован алгоритм прямого кодирования one-hot-кодирова-
ние[56]. Для программной реализации использован класс OneHotEncoder [150]. Объект данного класса принимает на вход массив категориальных значений и вызывает метод transform, который преобразует один категориальный признак в список булевых признаков (0-1 значений). Данный метод использован для атрибутов workclass, education, marital-status, occupation, relationship, race, sex.
Метод прямого кодирования не применен к атрибуту native-country в связи с тем, что количество уникальных значений превышает 40. Данный атрибут поделен на две группы: US (1) и non-US (2). Это обусловлено тем, что более 90% людей из выборки родом из США. В других работах авторы также поделили данный атрибут на 2 или несколько категорий (например, по кон-тингентам) [151 155].
Получено 67 признаков после предобработки данных. В качестве class0 (нулевой класс) установлено наименования класса «<—50К». Для обозначения «>50К» использована метка класса classsi.
В файле preprocessing.ру осуществляется программная предобработка (подготовка) данных для обучения модели. Файл содержит функции:
— one_hot_encoding_for_column(df, col_name): используется для предобработки категориальных признаков; df — объект класса DataFrame (таблица с данными), col_name — наименование столбца с категориальным признаком;
— df_only_float(df): вызывает one_hot_encoding_for_column(df, col_name) для всех категориальных признаков;
— native_country(df): для категориального признака native-country со значением «United-States» ставит значение 2 и 1 для всех остальных значений признака;
— result_column(df ): преобразует текстовые метки классов («<—50К» и «>50К») в числовые значения 1 и 2, соответственно;
— get_data_frame(filename): из заданного файла csv с именем filename считывает данные, записывает их в объект класса DataFrame, удаляет элементы с пустыми значениями, вызывает методы df _only_f loat (df ), native_country(df), result_column(df). Другими словами, создаёт готовые данные для обучения и тестирования;
— write_to_file(df, filename): записывает объект класса DataFrame df в csv-файл с именем filename.
В этом же файле вызываются функции подготовки и записи в новые файлы обучающей и тестовой выборок.
10
15
20
25
30
35
import pandas as pd import numpy as np
from sklearn.preprocessing import OneHotEncoder
def one_hot_encoding_for.column(df, col.name): enc = OneHotEncoder()
enc.fit(df[col_name].values.reshape(-1, 1)) df[enc.get_feature_names_out([col.name])] =
enc.transform(df[col_name].values.reshape(-1, 1)).toarrayO
def df_only_float(df): columns_for_oht = [
'workclass', 'education', 'marital - status' 'occupation', 'relationship', 'race', 'sex
]
for col in columns_for_oht: one_hot_encoding_for_column(df, col) df.drop(columns = col , inplace = True)
def result_column(df):
res_class = np.zeros(shape = [df.shape [0] , 1]) for i in range(df.shape [0]) :
if df ['class'] [i] == ' < = 50K . ' or df ['class '][i] == ' < = 50K
res_class [i] else :
res_class [i] df['class '] =
= 1
= 2 resclass
def native_country(df):
res_class = np.zeros(shape = [df.shape [0] , 1]) for i in range(df.shape [0]) :
if df['native-country'] [i] == 'United-States
res_class [i] = 2 else :
5
res_class [i] = 1 df['native - country ' ] = res_class
50
55
60
65
70
def get_data_frame(filename): df = pd.read.csv( filename, delimiter=',', names=[
'age', 'workclass', 'fnlwgt', 'education', 'education-num', 'marital - status', 'occupation', 'relationship', 'race', 'sex
'capital-gain', ' capital-loss' , 'hours-per-week ' ,
'native - country', 'class' ]
df = df.dropna() df_only_float(df) native_country(df) result.column(df) return df
def get_data(filename):
df = pd.read.csv(filename, header=0) df = df.dropna() x = df.drop ( columns = ['class ']) у = df['class '] return x, у
def write_to_file (df , filename):
df.to.csv(filename , columns = df.columns , index = False)
В файле random_forest.py происходит считывание данных, обучение модели случайный лес и прогнозирование классическим способом моделью и каждым классификатором отдельно. Файлы с вероятностями используются при тестировании функции QSearch.
Для обучения модели случайный лес использован класс из библиотеки sklearn RandomForestClassifier. Для обучения объекта класса используется метод fit. На вход методу подаётся обучающая выборка. В процессе обучения для определения разделяющего параметра использован критерий разбиения индекс Джини [156]. Гиперпараметры конструктора RandomForestClassif ier это количество деревьев решений и их максимальная глубина. Протестированы
значения высоты дерева от 3 до 10. Пусть к — количество тестовых значений, a ktme ~ количество правильно спрогнозированных меток класса. Для анализа точности использована формула (А.1). Точность для разных значений высот деревьев отличается на 0.01-0.02.
kfrue /л \
accuracy = (А.1)
В файле random_forest.py реализованы три функции:
— clean_f older (path): функция очищает папку с путем path от всех содержащихся в ней файлов;
— trees_predict (elf _f , х, y_proba_i, filename): функция записывает в файл с именем filename вероятность прогнозирования случайного леса (clf_f) y_proba_i для теста с г-м объектом х, а также вероятности принадлежности объекта х к class0 каждым классификатором отдельно;
— write_to_files(clf_f, х, y_proba_i, k, correct=True): функция вызывает trees_predict(clf_f, x, y_proba_i, filename), в зависимости от правильности прогнозирования индекса класса переменная correct будет получать значения True (истина) или False (ложь), а от неё зависят путь и имя файла filename, в который записывается результат.
Также в файле реализована часть кода, сохраняющая конфигурации обученной модели в файл. Результаты ирогнозрования представлены в приложении Е.
from sklearn.ensemble import RandomForestClassifier from preprocessing import get_data from sklearn.tree import DecisionTreeClassifier from sklearn.tree import export_text import os import glob import joblib import pickle
10
def clean_folder(path):
files = glob.glob(path , recursive = True) for f in files : try :
os.remove(f) except OSError as e:
print (" 0iiiH6Ka: °/0s : '/,s" °/0 (f , e.strerror))
25
30
35
40
45
50
def trees_predict(elf_f, x, y_proba_i, filename): f = open(filename, 'w') f.write(str(y_proba_i) + '\n') for estimator in clf_f.estimators.:
f.write(str(estimator.predict.proba([x]) [0] [0]) + '\n')
def write_to_files(clf_f, x, y_proba_i, k, path) filename = path + str(k) + '.txt' trees_predict(elf_f, x, y_proba_i, filename)
#clean_folder('data/correct_x/*.txt')
#clean_folder('data/incorrect_x/*.txt')
x_train , y_train = get_data (" dataW df _train . csv11)
x_test , y_test = get_data (" data\\df _test . csv 11)
elf = RandomForestClassifier(n_estimators=4, max_depth=2)
elf.fit(x_train , y_train)
#joblib.dump(elf , 'rf_clf_ (4 , 3).joblib') #print(export_text(elf.estimators_ [0]))
#clf = j oblib . load (' C : WUsers\\liliaWPycharmPro j ects\\ pythonProject\\ClassificationProblem-main\\rf_clf_(128, 9) pkl ')
elf = joblib.load('C:\\Users\\liliaWPycharmProjects\\ pythonProject\\ClassificationProblem-main\\rf_clf_joblib(4 2) .pkl ') #
y = elf.predict(x_test) y_proba = elf.predict_proba(x_test) k_true = 0 k_true_l = 0 k_true_2 = 0 k_false = 0 k_false_l = 0 k_false_2 = 0 for i in range(len(y)): if y[i] == y_test [i] : k_true += 1 if y[i] == 1:
k_true_l += 1 else :
k_true_2 += 1 else :
k_false += 1 if y_test [i] == 1
k_false_l += 1 else :
k_false_2 += 1
print(k_true , k_false, 1)
print (" correct prediction 11 , k_true / 1) print (" incorrect prediction 11 , k_false / 1) #print (" + 1 + 1" , k_true_l , " + 1-1", k_false_2) #print ("-1 + 1" , k_false_l , 11 -1-1" , k_true_2)
В квантовой части quantum_part.py реализованы функции для тестирования алгоритма QSearch:
— q_search(f ilename): реализация алгоритма QSearch filename — имя файла, из которого (учитывается информация о вероятностях;
— apply_q(repeats, amplitudes, d, о): реализация оператора Q = —AS0A-1SX; repeats — количество запусков Q, amplitudes — текущий вектор-столбец |"ф) из формулы ( ), d и о — матрицы-операторы диффузии и оракула соответственно;
— measurement(q_register, repeats=200) реализация функции измерения;
— get_amplitudes(f ile_name): функция создает состояние |"ф) из формулы (2.6);
— inv_about_mean(amplitudes, d): умножение матрицы диффузии d на текущий вектор-столбец amplitudes;
— oracle (amplitudes, о): умножение матрицы оракула о на текущий вектор-столбец amplitudes.
import random
import numpy as np
import math
import os
n_of_trees = 128
size = math.ceil(math.log2 (2 * n_of_trees))
15
20
25
30
35
40
45
def oracle_matrix():
o_matrix = np.zeros((n_of_trees*2, n_of_trees*2)) for i in range(n_of_trees*2) : if i '/. 2 == 0:
o_matrix [i] [i] = -1 else :
o_matrix[i][i] = 1 return omatrix
def oracle(amplitudes, o) :
amplitudes = (o @ amplitudes.T).T return amplitudes
def inv_about_mean_matrix(psi):
d = 2 * psi.T @ psi - np.identity(n_of_trees * 2) return d
def inv_about_mean(amplitudes, d): amplitudes = (d @ amplitudes.T).T return amplitudes
def get_amplitudes(filename): file = open (filename , 'r') y_proba = float(file.readline())
classl_prob = list(map(float, file.read ().split ())) psi = np.ndarray((1, n_of_trees * 2)) for i in range(n_of_trees):
psi[0][2*i] = math.sqrt(l/n_of.trees * classl_prob[i]) psi [0] [2*i + 1] = math.sqrt(l/n_of_trees * (1 - classl_prob[ i]))
return psi, y_proba
def measurement(q_register, repeats = 128) : #128, 64, 10 max_amplitude = 0 max_state = -1 for _ in range(repeats):
rand_state = random.randint(0, n_of_trees * 2-1) if math.fabs(q_register[0][rand_state]) > max_amplitude
60
65
70
75
80
85
max_amplitude = math.fabs(q_register [0] [rand_state]) max_state = rand_state return max_state
def apply_q(repeats , amplitudes, d, o) : for _ in range(repeats):
amplitudes = inv_about_mean(amplitudes, d) amplitudes = oracle(amplitudes, o) return amplitudes
def q_search(filename):
a_on_zero_state , y_proba = get_amplitudes(filename) amplitudes = a_on_zero_state.copy() i_state = measurement(amplitudes) if i_state 2 == 0: return 0, y_proba 1 = 0
c = random.random() + 1 o = oracle_matrix()
d = inv_about_mean_matrix(a_on_zero_state) j = 1
while True : 1 += 1
m = math.ceil(c ** l)
i_state = measurement(amplitudes)
if i_state °/0 2 == 0 or j >5:
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.