量子サポートベクターマシンのカーネル法による２値分類

https://qiita.com/hiro949/items/8528983d13d88ac1a8e8

で量子サポートベクターマシン(QSVM)の話をしましたが、ここではそれをカーネル法で計算してみたいと思います。QSVMはカーネル法を持ちることによってアルゴリズムがぐっと簡単になります。

# 古典カーネル法

まずは古典コンピューターの場合をおさらいします。
サポートベクターマシンの分類器

```math
f_{SVM}(x;w,b) = w^T x + b
```

について学習データ

```math
D = \{(_i,y_i) \mid x_i \in \mathbb{R}^n, y_i = \pm 1 \}
```

に対する適切なパラメーター$w,b$を求めてやればよいわけですが、まずはこれを双対問題に書き換えます。

## 最適化問題の双対問題

次の最適化問題(主問題)を解くことを考えます。

```math
\min_x f(x) \\
\text{subject to } g_i(x) \leq 0 \quad (i=1,\cdots, m)
```

この問題に対して、ラグランジュ関数

```math
L(x,\alpha) = f(x) + \alpha^T g(x)
```

を用いて

```math
\max_\alpha \min_x L(x,\alpha) \\
\text{subject to } \alpha_i \geq 0 \quad (i=1,\cdots, m)
```

と書き換えることができます。

## KKT条件(カルーシュ・クーン・タッカー条件)
主問題のようなタイプの問題の最尤値の条件としてKKT条件というものがあります。

```math
\nabla f(x) + \sum_{i=1}^m \alpha_i \nabla g_i(x) = 0 \\
g_i \leq 0 \\
\alpha_i \geq 0 \\
\alpha_i g_i(x) = 0
```

### サポートベクターマシンの場合
制約条件は

```math
y_i(w^Tx_i+b)=1 \quad ((x_i,y_i) \in D)
```

と書けます。そこで$w^Tw$をこの条件下で最小化することを考えるとその双対問題のラグランジュ関数は

```math
L(w,b,\alpha) = w^Tw + \sum_{i=1}^{|D|}\alpha_i[1-y_i(w^Tx_i+b)]
```

となります($\alpha_i \geq 0$)。

$\min_{w,b} L(w,b,\alpha)$は停留条件(KKT条件の最初の式)より

```math
\frac{\partial L}{\partial w}|_{\tilde{w},\tilde{b}} = \tilde{w} - \sum_{i=1}^{|D|}\alpha_iy_ix_i = 0\\
\frac{\partial L}{\partial b}|_{\tilde{w},\tilde{b}} = \sum_{i=1}^{|D|}\alpha_iy_i = 0
```

となるので、双対問題は

```math
\tilde{L}(\alpha) = L(\tilde{w},\tilde{b},\alpha) = \sum_{i=1}^{|D|}\alpha_i - \frac{1}{2}\sum_{i=1}^{|D|}\sum_{j=1}^{|D|}\alpha_i \alpha_j y_i y_j x_i^T x_j 
```

を最適化関数として

```math
\max \tilde{L}(\alpha) \\
\text{subject to } \sum_{i=1}^{|D|}\alpha_iy_i, \quad \alpha_i \geq 0
```

となります。これで$w$の最尤値が求まります。

またKKT条件の最後の式は

```math
\alpha_i(1-y_if_{SVM}(x_i;w,b))=0
```

となり、

```math
S = \{ (x_i,y_i) \in D \mid \alpha_i \neq 0 \} \subset D
```

の元$(x_j,y_j) \in S$に対して

```math
y_i (w^tx+b) = 1 \\
 y_i \left( \sum_{i=j}^{|D|} \alpha_j y_j x_j^T x_i + b \right) = 1 \\
\sum_{j=1}^{|S|} \alpha_j y_j x_j^T x_i + b = y_i \\
b = y_i - \sum_{j \in \text{index}(S)} \alpha_j y_j x_j^T x_i
```

となります。

そこで$S$について平均をとって

```math
b = \frac{1}{|S|}\sum_{i \in \text{index}(S)} \left(  y_i - \sum_{i \in \text{index}(S)} \alpha_j y_j x_j^T x_i \right)
```

で$b$の最尤値を求めます。

ちなみに$S$の元となるデータのことをサポートベクターと言います。

以上の結果を基に必要な式をまとめると

```math
\tilde{L}(\alpha) = \sum_{i=1}^{|D|}\alpha_i - \frac{1}{2}\sum_{i=1}^{|D|}\sum_{j=1}^{|D|}\alpha_i \alpha_j y_i y_j x_i^T x_j \\

f_{SVM}(x,\alpha) = \sum_{i \in \text{index}(S)}\alpha_iy_ix_i^T x + \frac{1}{|S|}\sum_{i \in \text{index}(S)} \left(  y_i - \sum_{i \in \text{index}(S)} \alpha_j y_j x_j^T x_i \right)
```

です。

## カーネル法

$x$に非線形変換$\phi$を施すとサポートベクターマシンの双対問題は

```math
\tilde{L}(\alpha) = \sum_{i=1}^{|D|}\alpha_i - \frac{1}{2}\sum_{i=1}^{|D|}\sum_{j=1}^{|D|}\alpha_i \alpha_j y_i y_j \phi(x_i)^T \phi(x_j) \\
f_{SVM}(x,\alpha) = \sum_{i=1}^{|S|}\alpha_iy_i \phi(x_i)^T \phi(x)  + \frac{1}{|S|}\sum_{i \in \text{index}(S)} \left(  y_i - \sum_{i \in \text{index}(S)} \alpha_j y_j \phi(x_j)^T \phi(x_i)  \right)
```

となります。ここで$\phi(x_i)^T \phi(x_j) $の部分をより一般的な非線形関数$K(x_i,x_j)$に置き替えて問題を拡張すると、

```math
\tilde{L}(\alpha) = \sum_{i=1}^{|D|}\alpha_i - \frac{1}{2}\sum_{i=1}^{|D|}\sum_{j=1}^{|D|}\alpha_i \alpha_j y_i y_j K(x_i,x_j) \\
f_{SVM}(x,\alpha) = \sum_{i=1}^{|S|}\alpha_iy_i K(x_i,x)  + \frac{1}{|S|}\sum_{i \in \text{index}(S)} \left(  y_i - \sum_{i \in \text{index}(S)} \alpha_j y_j K(x_i,x_j)  \right)
```

となります。この方法をカーネル法と言います。

# カーネル法による量子サポートベクターマシン(QSVM)の解法
では量子サポートベクターマシンをカーネル法の表現にしてみましょう。

量子サポートベクターマシンの分類器は

https://qiita.com/hiro949/items/8528983d13d88ac1a8e8

より

```math
\tilde{m}(x) = sgn[\langle\phi(x)|\mathcal{U}_{\phi(x)}^\dagger W^\dagger(\theta) \hat{f} W(\theta) \mathcal{U}_{\phi(x)} |\phi(x) \rangle + b]
```

と書けました。$W$は各ビットの操作を設定して精度が出るまで何度もループさせる必要がありましたが、カーネル法を使えばこの部分はラグランジュ関数のパラメーター$\alpha$によって決まり、必要がなくなります。
具体的にはカーネルを

```math
K^{Q}(x,z) = \left| \langle 0 |^{\otimes n_{bit}}\mathcal{U}_{\phi(z)}^\dagger \mathcal{U}_{\phi(x)} |0\rangle^{\otimes n_{bit}} \right|^2
```

と定義して

```math
L(\alpha) = \sum_{i=1}^{|D|} \alpha_i - \frac{1}{2}\sum_{i=1}^{|D|}\sum_{j=1}^{|D|}\alpha_i \alpha_j y_i y_j K^{Q}(x_i,x_j) \\
\tilde{m}(x) = sgn[ \sum_{i \in \text{index}(S)} y_i \alpha_i K^{Q}(x_i,x) + b]
```

とします(古典では$b$は$\alpha$から求めていましたが、ここでは$b$も最適化します)。これによって2値分類を行うと$W(\theta)$の部分の計算が要らなくなり、量子計算の部分は次図の回路だけで済みます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2445529/e29916bd-8c6b-9093-69fb-115073b92c86.png)

$f$や各ビットの操作を定義する必要がなくなってずいぶんシンプルになりましたね。

# 参考
- 仲川裕志 「東京大学工学教程 情報工学 機械学習」 (丸善出版)
- KKT条件：https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%AB%E3%83%BC%E3%82%B7%E3%83%A5%E3%83%BB%E3%82%AF%E3%83%BC%E3%83%B3%E3%83%BB%E3%82%BF%E3%83%83%E3%82%AB%E3%83%BC%E6%9D%A1%E4%BB%B6
- https://qiskit.org/documentation/machine-learning/locale/ja_JP/tutorials/index.html
- https://arxiv.org/pdf/1804.11326.pdf