Re:ゼロから始める量子多クラス分類 - hwakのトリビアルな雑記集

この記事は、量子サポートベクターマシーンを利用して、MNISTから配布されているデータベースの分類を行う方法をある程度略して説明するものです。変分量子計算の方法論は、機械学習における分類問題にも応用されています。その1つがQuantum Support Vector Machine(QSVM)です[1]。これはクラス分類問題において、評価関数に現れるカーネルを量子状態の内積で代用して、それを解くというものです。この方法において、過学習が抑えられるということが報告されています。本来ならば、実装してデータを採りたいところですが、手書き文字の認識分類をさせるだけでも画像を取り込んだ上に数字とアルファベットの全36種類の分類を行わなければならないため、私のパソコン環境では実装出来ないと判断しました。そのため、理論の話にとどめます。まずはタイトル通り、機械学習における2クラス分類の基礎から説明します。

機械学習の基礎:

機械学習の基本は、与えられたデータ $\mathbf{x}$ に対するクラス分類を行うことです。もっとも簡単な例はn次元平面上における一次関数における評価関数の値の範囲の中に有るか無いかを判定する問題です。入力するデータを $\mathbf{x}$ として式で表せば、

$0 = \textbf{ w }^\dagger \textbf{x } + b \tag{1}$

となります。分類のうちどちらかを表す空間 $C \in { +1, -1 }$ 、i番目の入力データに対応するその分類を表す符号変数 $y_i \in { +1, -1 }$ を導入し、 $\mathbf{w}$ のノルムで割りマージンを取ることで、

$y_i ( \textbf{ w }^\dagger \textbf{x }_i + b) \geq 1, \quad i \in \{1, 2, \dots, t \} \tag{2}$

の関係が導かれます。ここで、 $t$ は入力されるトレーニング用データの数です。こうして、データセット $x( \mathbf{w},b)$ に対する評価関数の結果はかっこの中身の符号を返す関数 $\text{sign}()$ を使って、

$m(x( \textbf{ w },b)) = \text{sign}( \textbf{ w }^\dagger \textbf{x } + b) \tag{3}$

となります。これは異なる分類に属する距離（マージン)の最も大きい2点間をつなぐサポートベクトルのノルム $\mathbf{w}$ を最小化する問題です。そのため、ラグランジュの未定乗数法と同じ形に表すことができ、

$L_p = \frac{1}{2} || \textbf{ w }|| - \sum_{i=1}^{t} \alpha_i y_i ( \textbf{ w }^\dagger \textbf{x }_i + b) + \sum_{i=1}^{t} \alpha_i \tag{4}$

となります。

$\frac{\partial L_p}{\partial b} = \frac{\partial L_p}{\partial \textbf{ w }} = 0$

となるため計算機での処理が可能なように、

$L_D = \sum_{i=1}^{t} \alpha_i - \frac{1}{2} \sum_{i,j=1}^{t} \alpha_i \alpha_j y_i y_j \textbf{x }_i^\dagger \textbf{x }_j \tag{5}$

と変換できます。この関数は分類数空間を $C \in {1, 2, \dots, c }$ として束縛条件 $0 \leq \alpha \leq c$ 、 $\sum_{i=1} \alpha_i y_i = 0$ に従います。この関数はコスト関数と呼ばれる、多クラス分類において最も重要な式です。この関数を最大化する $\alpha$ の組を見つけることでデータセットを正しく分類することがクラス分類の目的です。この中の $\textbf{x}_i^\dagger \textbf{x}_j$ は二値カーネルと呼ばれるもので、 $K( \textbf{x }_i, \textbf{x }_j )$ と表されます。

これを問題の特徴に応じて適切なものを選ぶことで、計算の精度が格段に上がることが知られています[2]。

QSVMにおいては、これは異なるデータセットから作った状態間の内積 $|\langle \Phi( \textbf{x }_i) |\Phi( \textbf{x }_j) \rangle|^2$ となります。

量子多クラス分類:

この節では、いよいよ量子多クラス分類の説明をしていきます。多少複雑ですが、それぞれのプロセスで行うことはそれほど複雑ではありません。このアルゴリズムの工程は主に3つです。

量子多クラス分類機にトレーニング用データセットt子を学習させます。
式(5)のコスト関数を計算します。
量子多クラス分類機における1,で最適化された変数θと経験的コスト関数$R _ { emp}$を基に、テストデータセットを分類させます。

1,と3,の大まかな工程を図1,2にそれぞれ示します。

図1 トレーニング用データセットを学習させるプログラムの大まかな流れ。 𝜃 は最適化変数、 𝑊 ( 𝜃 ) はハミルトニアンに相当する量子回路です。

図2 学習した最適化変数と経験的コスト関数を利用して 𝑠 ∈ 𝑆 の分類を行う流れ。

2クラス分類の場合はそれらの図において、

$\begin{align*} y \in \{+1, -1\}, \quad f: \{0,1\} \rightarrow \{+1, -1\}, \quad M_y &= \frac{1}{2} \left( I + y \sum_{z \in \{0,1\}^n} f(z) |z\rangle\langle z| \right) \tag{6} \end{align*}$

$|\Phi( \textbf{x })\rangle$ を実現する回路は $R_z(\theta)$ ゲート、 $exp(i\theta Z_i Z_j)$ の回路で実装します。 $\textbf{ w }(\theta)$ も同様です。

$\begin{align*} p_y( \textbf{x }) &= \langle \Phi( \textbf{x }) | \textbf{ w }^\dagger(\theta) M_y \textbf{ w }(\theta) | \Phi( \textbf{x }) \rangle \tag{7} \\ R_{emp}(\theta) &= \frac{1}{T} \sum_{ \textbf{x } \in T} Pr(m~( \textbf{x }) \neq m( \textbf{x })) \tag{8} \end{align*}$

を計算し、経験的コスト関数 $R_{emp}(\theta)$ と変数 $\theta$ を最適化します。 2, は2クラス分類の場合は少々異なり、量子ビット数を $n$ としてパウリゲート $P_{ \alpha}, \alpha \in {1,2, \dots,4n }$ に対して、

$\textbf{ w }_\alpha(\theta)= Tr[ \textbf{ w }^\dagger(\theta) f \textbf{ w }(\theta) P_\alpha ] \tag{9}$

$\Phi_\alpha(\theta) = \langle \Phi( \textbf{x }) | P_\alpha | \Phi( \textbf{x }) \rangle \tag{10}$

から、

$m( \textbf{x }) = sign\left( \frac{1}{2n} \sum_{\alpha} \textbf{ w }_\alpha(\theta) \Phi_\alpha( \textbf{x }) + b \right)$

を量子ビット数 $n$ に対して計算します。また、 $m( \textbf{x }_i) = y_i$ とします。

3,の量子カーネルはSWAP-test[3]で計算し、式(11)を $\alpha_j^{ * } , \alpha_j^{ * }$ とbの連立方程式として解くことで、計算出来ます。多クラス分類の場合は式(6)を、

$\begin{align*} y \in \{1,2,\dots,c\}, \quad f: \{0,1\} \rightarrow \{+1, -1\}, \quad M_y &= \frac{1}{2} \left( I - \Pi_{i=1}^{log_2 c} g_i y_i \right) \tag{12} \end{align*}$

としてあとは1対他あるいは1対1戦略で逐次分類することで図1,2の通りの方法で学習が完了します。 $R_{emp} = P_{err}$ となります。MNISTデータセットも、計算時間と仕様ゲート数は2値分類に比べて大幅に増加しますが、この方法で分類が可能です。

編集後記: 今回は私自身機械学習はタイトル通りゼロから実装を学んだため、非常にざっくりとした説明になってしまいました。もしかしたら、内容に誤りがあるかもしれません。しかしながら、変分量子計算の応用の中で一番難しい部類に入るアルゴリズムの論文を解読し、その内容を分かりやすく説明することは、私にとっても有意義でした。量子機械学習はFault-Tolerant-Quantum-Computer(FTQC)における最有力応用候補として期待されており、更なる発展が期待されています。そしてすでに、量子化学計算においてもクラスターを機械学習で最適化する手法が出ています。なので、私もこれを機に、量子機械学習の研究を始めようと思います。

[1] Vojtech Havlicek, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, Jay M. Gambetta, arxiv, 1804.11326quant-ph

[2] Qiskitで量子SVMを実装して性能評価してみた - Qiita

[3] Juan Carlos Garcia-Escartin and Pedro Chamorro Posada, arxiv, 1304.4923quant-ph

【PR】初心者も安心のサポート充実【DMM FX】