Огляд методів машинного навчання

У цьому розділі ми розглянемо деякі ключові терміни та методи класичного машинного навчання, що допоможуть краще розуміти робочі процеси квантового машинного навчання. Спочатку введемо загальні терміни, а потім детальніше розглянемо два типи МН: ядерні методи (зокрема у контексті машини опорних векторів) та нейронні мережі. Між цими методами безумовно є зв'язки, але ми розглядаємо їх окремо через відмінності у квантових робочих процесах, описаних тут і в наступних уроках. Це лише короткий огляд, де ми свідомо оминаємо багато нюансів. Для повнішого огляду машинного навчання рекомендуємо ресурси [1-3].

Типи машинного навчання

Просто кажучи, машинне навчання — це сукупність алгоритмів, що аналізують дані і роблять висновки на основі закономірностей і зв'язків у них. Загалом алгоритми МН можна поділити на три основні категорії залежно від типу даних і того, як алгоритми навчаються без явного програмування:

1. Навчання з учителем: У навчанні з учителем дані, що використовуються для тренування моделі, є міченими. Мета цих алгоритмів — вивчити зв'язок між даними і відповідними мітками або виходами та узагальнити його на нові дані. Типові задачі: класифікація та регресія.
2. Навчання без учителя: На відміну від навчання з учителем, тут для тренування моделі використовуються немічені дані. Мета таких алгоритмів — виявити приховані закономірності та структуру в даних. До цього класу належать алгоритми кластеризації та зниження розмірності, а також деякі генеративні моделі, як-от генеративно-змагальні мережі та варіаційні автоенкодери.
3. Навчання з підкріпленням: Алгоритми цієї категорії визначаються агентом, який взаємодіє з середовищем. Агент здійснює дії та отримує зворотній зв'язок у вигляді винагород і штрафів. Через цей механізм зворотного зв'язку агент зрештою навчається виконувати правильний набір дій для вирішення конкретного завдання.

На лівому зображенні показано два класи мічених даних (навчання з учителем), де класи лінійно роздільні. На правому — кластери даних. У задачі навчання без учителя ці дані спочатку не були б мічені, і алгоритм вивчав би розподіл, шукаючи кластери. Для наочності точки даних підписано. Ключова відмінність: у навчанні з учителем дані мічені від початку, а в навчанні без учителя — ні, навіть якщо наприкінці мітки й з'являються.

Додаємо «квантове» до машинного навчання

Тепер можна почати досліджувати, як «квантове» входить у машинне навчання. У цій ширшій класифікації ми розглядаємо тип моделі/алгоритму на пристрої обробки, а також тип даних, що подаються на вхід. Наведена схема підсумовує можливі комбінації.

Наприклад, КК означає, що маємо класичний набір даних (зображення, звук, текст, що зберігаються на класичних комп'ютерах) і класичний комп'ютер для запуску алгоритму МН — це класичне машинне навчання. QQ означає використання квантового комп'ютера для обробки квантових даних. «Квантові дані» можуть означати різне: результати вимірювань квантового пристрою, стани, підготовлені на квантовому комп'ютері іншим алгоритмом, або в майбутньому — дані в QRAM (Quantum Random Access Memory), якої поки не існує. Коли дослідники говорять про квантове машинне навчання, зазвичай мають на увазі режим КQ: класичний набір даних обробляється квантовим комп'ютером. Саме на таких алгоритмах ми й зосередимося далі.

Машини опорних векторів

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

Припустимо задачу бінарної класифікації на наборі даних із двовимірним простором ознак. Один зі способів класифікувати ці дані — знайти пряму, або в загальному випадку гіперплощину, що розділяє два класи. На практиці розділяючих гіперплощин може бути нескінченно багато, тому питання полягає у виборі оптимальної. Хороша межа рішення має максимізувати відступ — відстань до найближчих точок кожного класу. Точки даних, що знаходяться найближче до межі рішення, називаються опорними векторами.

Лінійну межу рішення можна описати кількома способами; один із найпростіших — формула $f_1$ нижче. Тут $\Theta$ — набір параметрів, що визначає гіперплощину, $\vec{x}$ — набір даних, $b$ — константа зсуву. $\Phi$ — відображення з простору вхідних точок, як правило (але не обов'язково), у простір вищої розмірності.

У моделі $f_1$ вектор $\Theta$ — це навчені параметри. Це «пряма формулювання». Шляхом математичних перетворень можна показати, що існує «двоїсте формулювання» $f_2$. У ньому скалярний добуток береться між векторами ознак, а не між ознаковим вектором і параметрами. Хоча у двоїстому формулюванні фігурують і ознаки тренувальних даних, і їхні мітки, воно виявляється кориснішим, що ми побачимо в наступному розділі.

$$f_1(\vec{x}) = \Theta^T \Phi(\vec{x})+b$$ $$f_2(\vec{x}) = \sum_{i=1}^n \alpha_i y_i \Phi^T(\vec{x}_i)\Phi(\vec{x})+b$$

Ядерні методи та роль квантових обчислень

Відео нижче мотивує участь квантових обчислень у лінійних класифікаторах. Детальніше це описано в тексті.

Перехід у простори вищої розмірності

У цьому та наступному підрозділах мова піде про відображення у вищі розмірності. Мета — пояснити «ядерний трюк» у контексті переходів між просторами і підготувати ґрунт для поняття квантового ядра. Важливо: не стверджується, що висока розмірність квантових хвильових функцій вирішує всі наші проблеми. Як зазначено у вступі, класичні гаусівські карти ознак уже є нескінченновимірними. Розмірність ознак важлива, але висока розмірність квантових станів сама по собі не гарантує переваги над класичними методами.

Графічно легко побачити, як можна узагальнити підхід МОВ на випадки, коли вихідні дані не є лінійно роздільними, якщо вибрати правильне відображення у вищий вимір. Дивлячись на двовимірні дані ліворуч, видно, що немає лінійної межі, яка розділяє два класи. Але якщо додати третю ознаку — наприклад, відстань до початку координат для $x_1$ і $x_2$ — дані стають лінійно роздільними. Це означає, що алгоритм МОВ тепер успішно застосовується у цьому просторі вищої розмірності.

Це «відображення ознак» ми теж позначаємо $\Phi$. Воно часто переводить дані у простір вищої розмірності, як тут, хоча існують і відображення в нижчу розмірність. Вищий вимір — просто найзручніший для візуалізації і розуміння приклад.

$$\vec{x} = \begin{pmatrix}x_1 \\ x_2 \end{pmatrix}$$ $$\vec{\Phi}(\vec{x}) = \begin{pmatrix}x_1 \\ x_2 \\ {x_1}^2+{x_2}^2\end{pmatrix}$$

Деякі відображення ознак переводять дані у простори дуже великої розмірності, де обчислення скалярних добутків стає дорогим. До цього ми ще повернемося.

Навіщо двоїсте формулювання?

Згадаємо пряме та двоїсте формулювання лінійної межі:

$$f_1(\vec{x}) = \Theta^T \Phi(\vec{x})+b$$ $$f_2(\vec{x}) = \sum_{i=1}^n \alpha_i y_i \Phi^T(\vec{x}_i)\Phi(\vec{x})+b$$

Знаючи, що відображення у простір вищої розмірності дозволяє знайти розділяючу гіперплощину, замінимо вихідний вектор $\vec{x}$ на відображені вектори ознак. Якщо зробити це в прямому формулюванні, виникне проблема: треба обчислювати скалярні добутки між параметрами і потенційно дуже великими відображеними векторами. У двоїстому формулюванні скалярні добутки беруться між відображеними векторами різних вхідних точок.

Для деяких відображень ознак скалярний добуток $\vec{\Phi}^T(\vec{x}_i)\cdot \vec{\Phi}(\vec{x}_j)$ можна записати як просту функцію $k(\vec{x}_i, \vec{x}_j)$ вихідних (нижчовимірних) змінних. Це дуже вигідно обчислювально: ми отримуємо доступ до простору, де дані лінійно роздільні, без витрат на роботу у вищих вимірах. Оскільки відображені вектори з'являються в $f_2$ лише як скалярні добутки, явно будувати відображення навіть не потрібно. Функцію $k(\vec{x}_i, \vec{x}_j)$, що обчислює скалярні добутки, називають «ядерною функцією», а цей прийом — «ядерним трюком». Відображені вектори можуть бути навіть нескінченновимірними, а ядро все одно ефективно обчислюється.

Ядерна функція — це функція двох векторів вхідних даних. Підставляючи всі пари векторів набору даних, отримуємо симетричну напівдовизначену матрицю — матрицю ядра:

$$k = \begin{pmatrix}k(\vec{x}_1,\vec{x}_1) & k(\vec{x}_1,\vec{x}_2) & ... \\ k(\vec{x}_2,\vec{x}_1) & k(\vec{x}_2,\vec{x}_2) & ... \\ \vdots & \vdots & \ddots\end{pmatrix}$$

Маючи матрицю ядра, знаходимо оптимальні параметри $\alpha_i$ методами квадратичного програмування або алгоритмом «послідовної мінімальної оптимізації». Це, звісно, передбачає існування ефективно обчислюваного ядра, що відповідає відображенню, яке лінійно роздільне для ваших класів. Пов'язаний, але новий підхід — квантова оцінка ядра.

Квантові ядра

Квантові комп'ютери (та квантові стани загалом) допускають дуже природне визначення «квантового ядра». Кодування вхідного $\vec{x}$ у квантовий стан $|\Phi(\vec{x})\rangle$ можна інтерпретувати як відображення ознак. Цей процес може переводити дані у простір дуже великої розмірності (як у класичних відображеннях), але конкретна розмірність залежить від методу кодування (дивись урок «Кодування даних»). Нагадаємо: скалярний добуток двох квантових станів $\langle \psi | \phi \rangle$ пов'язаний із ймовірністю виміряти стан $|\phi\rangle$, перебуваючи в стані $|\psi\rangle$. Скалярний добуток двох відображених точок $\vec{\Phi}(\vec{x}_i)$ і $\vec{\Phi}(\vec{x}_j)$ можна оцінити достатньою кількістю вимірювань відповідної схеми.

Як ми побачимо далі в курсі, вимірювання квантової схеми, подібної до наведеної вище, дозволяють оцінити ядро, а потім класично запустити оптимізацію МОВ на матриці ядра для навчання параметрів.

Варіаційні квантові класифікатори та нейронні мережі

Ще один алгоритм квантового машинного навчання для найближчого майбутнього — «варіаційні квантові схеми» (VQC). Коли ці схеми застосовуються в задачі класифікації, ту ж абревіатуру можна зустріти у значенні «варіаційні квантові класифікатори». Вони часто використовують структури, аналогічні класичним нейронним мережам (НМ), і в таких випадках їх називають квантовими нейронними мережами (QNN). Важливо розуміти, що VQC є більш загальними і не обов'язково слідують структурі НМ. Почнемо з аналогії з НМ, щоб прояснити роль квантових обчислень у цій парадигмі, а потім перейдемо до узагальнень. Спочатку — короткий огляд класичних нейронних мереж.

Відео нижче коротко оглядає нейронні мережі та їхній зв'язок із варіаційними квантовими схемами. Детальніше — у тексті.

Нейронна мережа — це обчислювальна модель, що вільно натхнена структурою та функцією нейронів головного мозку. Нейрони (вузли на малюнку) організовані в шари і з'єднані вагами.

Перший шар — вхідний, активації $a_n^0$ нейронів цього шару беруться безпосередньо з даних $\vec{x}$ (наприклад, значення яскравості пікселів зображення). Останній шар — вихідний, що описує класифікацію (наприклад, ймовірність 90% «собака» і 10% «кіт»).

Нейрони кожного шару обробляють сигнали від попереднього шару і передають їх у наступний через ваги $w_i$ (зв'язки на схемі). Якщо розглянути один нейрон, отримаємо будівельний блок нейронної мережі — «перцептрон». Математично перцептрон приймає вектор $\vec{x}$ і обчислює його скалярний добуток із навчальним вектором ваг плюс деяке зміщення. Критично важливо: перцептрон застосовує нелінійну функцію активації ($\sigma$). Без нелінійності вся нейронна мережа зводилась би до одного великого матричного множення — лінійної моделі, що не може захопити складні закономірності.

Функції вигляду

$$f(\vec{x}) = \sigma (\vec{w}\cdot \vec{x}+\vec{b})$$

обчислюються в кожному нейроні на основі відомих даних $\vec{x}$, нелінійного $\sigma$ та невідомих векторів ваг $\vec{w}$ і зміщень $\vec{b}$. Загалом між усіма нейронами всіх шарів можуть бути ненульові ваги; ваги від шару $L$ до $L+1$ між нейронами $m$ і $n$ позначаємо $w^L_{m,n}$. Зміщення $n$-го нейрона $L$-го шару — $b^L_n$. Ці $b$ не пов'язані з $b$ у дискусії про квантові ядра.

Тренування зазвичай починають із випадкового набору ваг і зміщень. Потім перевіряють якість класифікації та покращують її. Функція витрат описує, наскільки мережа відхиляється від правильної класифікації. Один із поширених прикладів — середньоквадратична помилка (MSE):

$$C(w^L_{m,n},b^L_n) = \frac{1}{N}\sum_{i=1}^{N_\text{train}}\sum_{j=1}^{N_\text{outputs}}{(v_{i,j}-p_{i,j})^2}$$

Тут $v_{i,j}$ — справжнє значення для зображення $i$ і виходу $j$ (наприклад, 1.0 для нейрона «собака» і 0 для решти), $p_{i,j}$ — передбачене значення. Різниці піднімаємо до квадрату, підсумовуємо за категоріями і по всіх прикладах навчальної вибірки. Потім варіюємо ваги і зміщення; класичні методи оптимізації, як-от градієнтний спуск, шукають локальний мінімум функції витрат.

Квантовий перцептрон

Щоб побудувати квантовий аналог перцептрона, потрібно реалізувати нелінійність квантовими схемами — це роль функції активації в класичних НМ. Без додаткових заходів квантові схеми реалізують лише унітарні (лінійні) операції. Існує кілька методів введення нелінійності: вимірювання як джерело нелінійності, методи на основі квантового перетворення Фур'є, вимірювання в середині схеми та відслідковування кубітів.

Квантова нейронна мережа

Квантова нейронна мережа (QNN) спочатку кодує вхідні дані унітарним шаром $U$ (на малюнку), потім застосовує квантові схеми, що відповідають вагам між шарами ($W$), і нарешті — шар вимірювань. Кілька ключових моментів:

• Завантаження даних і ваги — лінійні операції.
• Вимірювання — нелінійні.
• Як і в класичній НМ, є і лінійні, і нелінійні компоненти.
• Схеми ваг містять варіаційні параметри, тому класична мінімізація все ще потрібна.

Схему вище можна використати для обчислення функції $f_{QNN}(x) = \langle 0|U^{\dagger}(X)W^{\dagger}OWU(x)|0\rangle$ Зауваж, що ця функція загалом не збігається з $f(x)$ класичних НМ. Зокрема, вона включає потенційно багато шарів ваг і застосовується до всіх даних, завантажених у схему за допомогою $U$.

Узагальнення

Розглянемо один зі способів побудувати квантовий аналог нейронної мережі. У цій моделі потік інформації відрізняється від класичної НМ прямого поширення. У класичному варіанті інформація рухається зліва направо (і у зворотному напрямку під час зворотного поширення).

У цій квантовій нейронній мережі унітарний блок, що кодує дані, повторюється між варіаційними унітарними блоками з навчальними параметрами. Ця стратегія — «повторне завантаження даних» — підкріплена цікавими теоретичними результатами. Зокрема, стаття Pérez-Salinas et al. показує, що «за допомогою кількох повторних завантажень даних один кубіт забезпечує достатні обчислювальні можливості для побудови універсального квантового класифікатора при підтримці класичного підпрограміста». Таким чином, повторне завантаження даних дозволяє підвищити виразність моделі та наблизити квантову нейронну мережу до апроксимації складних функцій.

Посилання

[1] "Reinforcement Learning: An Introduction", Richard S. Sutton and Richard G. Barto, MIT Press, Second Edition, Cambridge, MA, 2018

[2] "Pattern Recognition and Machine Learning", Christopher M. Bishop, Springer, 2006

[3] "Foundations of Machine Learning", Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, MIT Press, Second Edition, 2018.