Přehled relevantních metod strojového učení

V této části si zopakujeme některé klíčové pojmy a metody z klasického strojového učení, které nám pomohou lépe pochopit postupy v kvantovém strojovém učení. Nejprve představíme obecné pojmy a pak se podrobněji zaměříme na dva typy strojového učení: kernelové metody (zejména v kontextu podpůrných vektorových strojů) a neuronové sítě. Mezi těmito metodami jistě existují souvislosti, ale budeme je považovat za odlišné kvůli rozdílům v kvantových postupech popsaných zde a v dalších lekcích. Jde pouze o stručný přehled a spoustu nuancí záměrně vynecháváme. Pro úplnější přehled strojového učení doporučujeme zdroje jako [1-3].

Typy strojového učení

Jednoduše řečeno, strojové učení je soubor algoritmů, které analyzují data a vyvozují závěry ze vzorů a vztahů v nich. V zásadě lze algoritmy strojového učení rozdělit do tří hlavních kategorií podle typu dat a způsobu, jakým se algoritmy učí bez explicitního programování:

1. Učení s učitelem: Při učení s učitelem jsou data používaná k trénování modelu označena (opatřena štítky). Cílem těchto algoritmů je naučit se vztah mezi daty a odpovídajícími štítky nebo výstupy a zobecnit ho na neviděná data. Běžnými úlohami v této třídě jsou klasifikace a regrese.
2. Učení bez učitele: Na rozdíl od učení s učitelem využívá učení bez učitele neoznačená data k trénování modelu strojového učení. Cílem těchto algoritmů je odhalit skryté vzory a struktury v datech. Do této třídy patří například shlukovací algoritmy a algoritmy pro redukci dimenzionality. Lze sem zařadit i některé generativní modely, jako jsou generativní adversariální sítě a variační autokodéry.
3. Zpětnovazební učení: Algoritmy v této kategorii strojového učení jsou definovány agentem, který interaguje s prostředím. Agent provádí akce a přijímá zpětnou vazbu od svého prostředí v podobě odměn a trestů. Prostřednictvím tohoto mechanismu zpětné vazby se agent nakonec naučí provádět správnou sadu akcí k plnění konkrétního úkolu.

Levý obrázek ukazuje dvě kategorie označených dat jako při učení s učitelem. V tomto případě jsou kategorie lineárně separabilní. Pravý obrázek zobrazuje shluky dat. Při úloze učení bez učitele by tato data nebyla zpočátku označena a algoritmus by studoval jejich rozložení, přičemž by hledal například shluky. Pro účely vizualizace shluků, které by algoritmus mohl identifikovat, jsou datové body nyní označeny. Klíčový rozdíl mezi oběma přístupy spočívá v tom, že při učení s učitelem začínáme s již označenými daty, zatímco při učení bez učitele začínáme s neoznačenými daty, i když na konci mohou být data označena.

Zavedení pojmu „kvantový" do strojového učení

Nyní můžeme začít zkoumat, jak se do strojového učení zavádí „kvantový" přístup. V tomto širším členění bereme v úvahu jak typ modelu/algoritmu na výpočetním zařízení, tak typ dat, která do něj vstupují. Obrázek výše shrnuje možné kombinace.

Například CC znamená, že máme klasickou datovou sadu – například obrázky, zvuk nebo text, které lze uložit na klasických počítačích – a ke spuštění algoritmu strojového učení používáme také klasický počítač. To je přesně klasické nastavení strojového učení. Naproti tomu QQ znamená, že ke zpracování kvantových dat používáme kvantový počítač. Pojem „kvantová data" může mít různé významy a může záviset na kontextu. Kvantová data lze chápat jako soubor výsledků měření získaných z kvantového zařízení, nebo mohou odkazovat na stavy připravené na kvantovém počítači jiným algoritmem. V budoucnu by to mohlo odkazovat i na data uložená v QRAM (Quantum Random Access Memory), která v současnosti neexistuje. Když výzkumníci hovoří o kvantovém strojovém učení, obvykle mají na mysli režim CQ, kde je zpracovávaná datová sada klasická a zařízení provádějící algoritmus strojového učení je kvantový počítač. V následujících částech kurzu se zaměříme právě na takové algoritmy.

Podpůrné vektorové stroje

Nyní si zrekapitulujeme třídu algoritmů nazývanou podpůrné vektorové stroje (support vector machines) z pohledu klasického strojového učení. Později ukážeme, jak do tohoto algoritmu zapojit kvantové výpočty.

Představme si úlohu binární klasifikace na datové sadě s dvourozměrným příznakovým prostorem, jak je znázorněno v grafu. Jednou z možností klasifikace této datové sady je najít přímku, nebo obecněji nadrovinu, která odděluje dvě třídy. V praxi existuje nekonečně mnoho oddělujících nadrovin, takže otázka zní: Jak definovat tu optimální? Myšlenka spočívá v tom, že obzvláště dobrá rozhodovací hranice by měla maximalizovat okraj (margin), definovaný jako vzdálenost k nejbližším bodům v každé třídě. V tomto kontextu se datové body s nejmenší vzdáleností k rozhodovací hranici nazývají podpůrné vektory.

Lineární rozhodovací hranici lze popsat různými způsoby; v jistém smyslu nejpřímočařejší je způsob zobrazený v $f_1$ níže. Zde je $\Theta$ soubor parametrů definujících nadrovinu, $\vec{x}$ je tvá datová sada a $b$ je konstantní posun. $\Phi$ je zobrazení z prostoru vstupních datových bodů, často (ale ne nutně) do prostoru vyšší dimenze. K tomuto zobrazení se vrátíme níže.

V modelu $f_1$ je $\Theta$ vektor laditelných parametrů, které by se model naučil. Tuto formulaci nazýváme „primární formulací". Pomocí určité matematické manipulace lze ukázat, že existuje druhý způsob, jak formulovat stejný problém. Tuto formulaci nazýváme „duální formulací", znázorněnou rovnicí $f_2$ níže. Pro tuto formulaci je nutné optimalizovat přes parametry alfa. Hlavní rozdíl spočívá v tom, že v primární formulaci obsahuje rovnice skalární součin příznakového vektoru a laditelných parametrů, zatímco v duální formulaci je skalární součin mezi příznakovými vektory. Přestože duální forma zahrnuje jak příznaky trénovacích dat, tak odpovídající štítky, v příští části uvidíme, proč se ukazuje jako užitečnější než primární forma.

$$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$$

Kernel metody a jak do nich může vstoupit kvantová výpočetní technika

Následující video motivuje, jak může kvantová výpočetní technika hrát roli v lineárních klasifikátorech. Podrobnější popis najdeš v textu níže.

Přechod do vícerozměrných prostorů

Tato a následující část se zaměřují na zobrazení do vyšších dimenzí. Cílem je vysvětlit „kernel trick" v kontextu zobrazení mezi prostory, a tím připravit půdu pro to, co je to kvantový kernel. Důležité je, že nejde o to, že vyšší dimenze kvantových vlnových funkcí vyřeší všechny naše problémy. Jak bylo zmíněno v úvodu, klasická Gaussova příznaková zobrazení jsou už tak nekonečněrozměrná. Dimenzionalita příznaků dat je důležitá, ale vysokorozměrné kvantové stavy samy o sobě nestačí k tomu, aby překonaly klasické metody.

Graficky lze snadno ukázat, jak lze přístup SVM zobecnit na případy, kde původní data nejsou lineárně separabilní – pokud máme správné zobrazení do vyšších dimenzí. Podíváme-li se na dvourozměrná data vlevo, vidíme, že neexistuje žádná lineární rozhodovací hranice, která by oddělila dvě třídy. Můžeme však uvažovat o přidání třetího příznaku do příznakovéhoprostoru. Pokud je tento nový příznak – například – vzdálenost od počátku předchozích dvou příznaků $x_1$ a $x_2$, pak se data stanou lineárně separabilními. To také znamená, že teď můžeme úspěšně spustit algoritmus support vector machine na tomto vícerozměrném příznakovém prostoru.

Toto „příznakovézobrazení" označujeme také $\Phi$. Příznakovézobrazení většinou mapuje z prostoru vstupních dat do vyššídimenze, jak je znázorněno zde, ale existují modely a algoritmy, které využívají zobrazení do nižších dimenzí. Zobrazení do vyšší dimenze je jednoduše snadný případ, který lze vizualizovat a pochopit.

$$\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}$$

Některá příznaková zobrazení mohou mapovat do velmi vysokorozměrných prostorů. V takových případech vysoká dimenzionalita zdražuje výpočet skalárních součinů. K tomuto bodu se vrátíme níže.

Proč je duální formulace užitečná?

Vzpomeň si na primární a duální formulaci našeho modelu lineární hranice:

$$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$$

Teď, když víme, že použití příznakovéhozobrazení pro přechod do vyššídimenze nám může umožnit úspěšně najít separující nadrovinu, můžeme nahradit původní příznakovývektory $\vec{x}$ v rovnicích vektory po příznakovémzobrazení. Pokud to ale uděláme v primární formulaci, narazíme na problém: musíme počítat skalární součiny mezi parametry a potenciálně velmi vysokorozměrným příznakovým zobrazením. V duální formulaci jsou naproti tomu tyto součiny nahrazeny skalárními součiny mezi příznakovýmivektory různých vstupů.

Pro některá příznaková zobrazení může být možné zapsat skalární součin zobrazených vektorů $\vec{\Phi}^T(\vec{x}_i)\cdot \vec{\Phi}(\vec{x}_j)$ jako jednoduchou funkci $k(\vec{x}_i, \vec{x}_j)$ původních (nízkodimenzionálních) proměnných $\vec{x}_i$ a $\vec{x}_j$. Pro některé volby $\Phi$ dokonce může být možné zapsat $\vec{\Phi}^T(\vec{x}_i)\cdot \vec{\Phi}(\vec{x}_j)$ jako jednoduchou funkci nízkodimenzionálního skalárního součinu $\vec{x}_i^T\vec{x}_j$. To je výpočetně velmi výhodné, protože získáme přístup do prostoru, ve kterém jsou data lineárně separabilní, ale bez nákladů spojených s manipulacemi ve vyšších dimenzích. Protože se zobrazené vektory v $f_2$ vyskytují pouze ve skalárních součinech, nemusíme příznakovézobrazení explicitně provést, abychom tyto součiny vypočítali. Funkci $k(\vec{x}_i, \vec{x}_j)$, která počítá skalární součiny, nazýváme „kernel funkcí" a tento způsob, jak se vyhnout výpočtu příznakovéhozobrazení, se nazývá „kernel trick". Zobrazené vektory mohou být dokonce nekonečněrozměrné, a přesto může být kernel stále velmi efektivně vypočitatelný.

Kernel funkce sama o sobě je funkcí dvou vstupních datových vektorů. Vložení každého páru datových vektorů z datové sady jako argumentů kernel funkce dává symetrickou, pozitivně semidefinitní matici, nazývanou kernel matice:

$$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}$$

Jakmile kernel matici vypočítáme, můžeme najít optimální parametry ($\alpha_i$) metodami jako software pro kvadratické programování nebo algoritmus zvaný „sekvenční minimální optimalizace". To samozřejmě předpokládá, že existuje efektivně vypočitatelný kernel odpovídající příznakovémuzobrazení, které způsobí lineární separabilitu tříd v datech. Příbuzným, ale novým přístupem je odhad kvantového kernelu.

Kvantové kernely

Kvantové počítače, respektive kvantové stavy obecně, umožňují velmi přirozené zavedení pojmu „kvantový kernel". Kódování vstupu $\vec{x}$ do kvantového stavu $|\Phi(\vec{x})\rangle$ lze interpretovat jako příznakovézobrazení. Tento proces může skutečně mapovat data do velmi vysokorozměrného prostoru, jak je to běžné u klasických příznakovýchzobrazení, ale dimenzionalita závisí na metodě kódování (viz lekce Kódování dat). Vzpomeň si, že skalární součin dvou kvantových stavů $\langle \psi | \phi \rangle$ je spojen s pravděpodobností naměření stavu $|\phi\rangle$, když se nacházíme ve stavu $|\psi\rangle$. Skalární součin dvou zobrazených datových bodů $\vec{\Phi}(\vec{x}_i)$ a $\vec{\Phi}(\vec{x}_j)$ můžeme odhadnout dostatečným počtem měření výsledného Circuit.

Jak uvidíme později v kurzu, pomocí měření na kvantovém Circuit, jako je ten zobrazený výše, lze odhadnout kernel, a poté lze klasickou SVM optimalizaci spustit na kernel matici k naučení laditelných parametrů.

Variační kvantové klasifikátory a neuronové sítě

Dalším kvantovým algoritmem strojového učení vhodným pro blízkou budoucnost jsou tzv. „variační kvantové Circuit" (VQC). Když se tyto Circuit používají ke klasifikaci, můžeš se setkat se stejnou zkratkou ve významu „variational quantum classifiers" (také VQC). Tyto algoritmy často využívají struktury podobné klasickým neuronovým sítím (NN); v takovém případě se označují jako kvantové neuronové sítě (QNN). Je důležité si uvědomit, že VQC jsou obecnější a nemusí nutně sledovat strukturu NN, ale začínáme analogií s NN, abychom objasnili roli, kterou kvantové počítání může hrát ve stávajících pracovních postupech strojového učení. Poté se budeme věnovat zobecněním. Nejprve si ale připomeneme klasické neuronové sítě.

Následující video stručně shrnuje neuronové sítě a jejich průnik s variačními kvantovými Circuit. V textu níže je toto téma rozvedeno podrobněji.

Neuronová síť je výpočetní model volně inspirovaný strukturou a funkcí neuronů v mozku. Tyto neurony, tedy uzly viditelné na obrázku, jsou uspořádány do vrstev a propojeny vahami.

První vrstva je vstupní vrstva a aktivace $a_n^0$ neuronů v ní jsou přiváděny přímo z dat $\vec{x}$, která mají být analyzována (například odstíny jednotlivých pixelů obrázku). Poslední vrstva je výstupní vrstva popisující kategorizaci (například klasifikace obrázku jako 90% pravděpodobnosti, že jde o psa, a 10% pravděpodobnosti, že jde o kočku – abychom zůstali u příkladu s obrázkem).

Neurony v každé vrstvě zpracovávají signály přijímané z předchozí vrstvy a předávají je do vrstvy následující prostřednictvím vah $w_i$ (spojení v diagramu). Zaměříme-li se na jeden takový neuron, dostaneme stavební kámen neuronové sítě – tzv. „perceptron". Matematicky perceptron přijme vstupní vektor $\vec{x}$, vypočítá jeho skalární součin s trénovatelnými váhami a přičte konstantu (bias). A velmi důležité: perceptron na výsledek tohoto výpočtu aplikuje nelineární aktivační funkci ($\sigma$). Tyto nelineární aktivační funkce jsou klíčem k velké vyjadřovací síle neuronových sítí. Dá se to vidět i tak, že kdybychom nelinearitu mezi vrstvami neměli, mohli bychom celou neuronovou síť v principu zapsat jako jedno velké maticové násobení. Výsledkem by byl pouze lineární model, který by nebyl schopen zachytit složité vzory, které hluboké neuronové sítě dokážou. Nelineární aktivační funkce jsou proto pro neuronové sítě zásadní.

Funkce ve tvaru

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

se počítají v každém neuronu za použití známých dat $\vec{x}$, nelineárního $\sigma$ a také neznámých vektorů vah $\vec{w}$ a biasů $\vec{b}$. Obecně mohou existovat nenulové váhy mezi všemi neurony všech vrstev; váhy z vrstvy $L$ do vrstvy $L+1$ mezi neurony $m$ a $n$ označujeme $w^L_{m,n}$. Podobně bias na $n$-tém neuronu $L$-té vrstvy je $b^L_n$. Tyto biasy nesouvisejí s $b$-čky z části o kvantovém kernel.

Neuronovou síť můžeš začít s náhodnou sadou vah a biasů nebo z nějaké rozumné výchozí konfigurace. Cílem je pak zkontrolovat, jak dobře neuronová síť klasifikuje, a zlepšit ji. K popisu toho, jak se síť odchyluje od správné klasifikace, používáme ztrátovou funkci. Ztrátových funkcí existuje mnoho. Popíšeme jeden běžný příklad – střední kvadratická chyba (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 závislosti na aplikaci to může znamenat výpočet rozdílu mezi skutečnou hodnotou $v_{i,j}$ obrázku $i$ z trénovacích dat pro výstup $j$ (například hodnota 1,0 na výstupním neuronu pro „pes" a 0 na všech ostatních) a předpovězenou hodnotou $p_{i,j}$. Tento rozdíl umocníme a sečteme přes všechny kategorie – zachytíme tak nejen to, jestli byla nejvíce aktivována správná kategorie, ale i to, zda jsou nesprávné aktivace potlačeny. Poté sečteme přes všechny příklady v trénovací sadě a získáme celkovou ztrátu.

Parametry, jako jsou váhy v každé vrstvě mezi všemi neurony a biasy na všech neuronech, pak měníme. K hledání lokálního minima ztrátové funkce se používají klasické optimalizační metody, například gradientní sestup.

Kvantový perceptron

Aby bylo možné sestavit kvantovou analogii perceptronu, je třeba mimo jiné zajistit nelinearitu v kvantových Circuit – to odpovídá roli aktivační funkce v klasických neuronových sítích. Kvantové Circuit totiž bez dalších úprav implementují pouze unitární operace, které jsou čistě lineární. Existují různé metody, jak do kvantových Circuit nelinearitu zavést. Jednou z hlavních je využití měření jako zdroje nelinearity. Mezi další možnosti patří metody založené na kvantové Fourierově transformaci, mid-circuit measurements neboli dynamické Circuit a sledování (tracing out) Qubit mimo Circuit.

Kvantová neuronová síť

Kvantová neuronová síť (QNN) funguje tak, že nejprve zakóduje vstupní data pomocí unitární vrstvy $U$ na obrázku, poté aplikuje kvantové Circuit odpovídající vahám mezi vrstvami (níže označené $W$) a nakonec vrstvu měření. Několik klíčových poznámek:

• Načítání dat a aplikace vah jsou lineární operace.
• Měření jsou nelineární.
• Stejně jako v klasické NN tak máme jak lineární, tak nelineární složky.
• Váhové Circuit stále obsahují variační parametry, takže klasická minimalizace je stále nutná.

Pomocí Circuit podobného výše uvedenému můžeme vypočítat funkci $f_{QNN}(x) = \langle 0|U^{\dagger}(X)W^{\dagger}OWU(x)|0\rangle$ Všimni si, že tato funkce obecně není totožná s funkcí $f(x)$ popsanou v klasických NN. Zejména tato funkce zahrnuje potenciálně mnoho vrstev mnoha vah a je aplikována na všechna data načtená do kvantového Circuit pomocí $U$.

Zobecnění

Nyní se podíváme na jeden ze způsobů, jak sestavit kvantovou analogii neuronové sítě. V tomto modelu se tok informací liší od klasické dopředné neuronové sítě. V klasickém případě informace proudí zleva doprava – začínají vstupem a končí výstupem modelu – a v opačném směru při zpětné propagaci pro trénink modelu.

V tomto kvantovém konstruktu neuronové sítě však vidíme, že unitární blok kódující data se opakuje mezi variačními unitárními bloky s trénovatelnými parametry. Tato strategie, kterou označujeme jako „data reuploading", je podložena zajímavými teoretickými výsledky. Článek autorů Pérez-Salinas et al. ukazuje, že díky vícenásobnému data reuploading „jeden Qubit poskytuje dostatečné výpočetní schopnosti k sestavení univerzálního kvantového klasifikátoru, pokud je doplněn klasickým podprogramem." Data reuploading je tedy technika, která umožňuje zvýšit expresivitu a reprezentační schopnosti modelu a kvantové neuronové síti tak aproximovat složité funkce.

Reference

[1] „Reinforcement Learning: An Introduction", Richard S. Sutton a Richard G. Barto, MIT Press, druhé vydání, Cambridge, MA, 2018

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

[3] „Foundations of Machine Learning", Mehryar Mohri, Afshin Rostamizadeh a Ameet Talwalkar, MIT Press, druhé vydání, 2018.