QBoost を用いた画像認識
坂倉

1

佑季

(指導教員：工藤和恵)

はじめにとの差の二乗を最小化する問題とする。d 番目の画像
ベクトル x(d) に対する教師データを y (d) とすると、コスト関数は次式で与えられる。

インターネットが広く普及し、IoT(モノのインターネット化) や AI が発展してきている現代において、膨大な量のデータが手軽に収集可能になり、大量の選択肢の中から最適なものを選ぶ「組合せ最適化問題」を高速に解く需要が高まってきている。実際に社会や産業界において、配送計画、勤務シフト、機械学習など数多くの組合せ最適化問題があり、幅広い応用分野がある。しかし、このような組合せ最適化問題はデータが多くになるにつれて選択肢の数が爆発的に増加し、従来のコンピュータでは解くのに非常に時間がかかる。
そんな最適化問題を高速かつ高精度に解いてくれると期待されているのが、アニーリングマシンである。
そこで、様々な分野で応用されている画像認識を組み合わせ最適化問題に置き換え、アニーリングマシンで解くことによって、処理の高速化を実現したいと考えている。本研究では手始めに手書き数字認識を行う。

2モデルと方法

2.1Boosting)2NN∑
1 ∑(d)(d)H(w) =wi ci (x ) − y+λwi
N i=1i=1
d=1()ND∑
2 ∑(d) (d)=λ−ci (x )ywi
Ni=1
d=1(D)N1 ∑ ∑(d)(d)+ 2ci (x )cj (x ) wi wj + const
N i,j=1D∑(d=1(3)
ここで、D は画像の枚数、N は弱識別器の数、λ は過学習を防ぐための正則化パラメータである。
そして、画像認識は以下のように行われる。例えば、
図 1 のように「0」という画像が与えられた時、弱識別器が 0 であると判断した場合は’1’、0 でないと判断した場合は’−1’ が出力される。そして、使用した弱識別器の中で多数決が取られ、強識別器の出力が決まる。

Boosting とは、性能の低い識別器を順番に学習し組み合わせることによって、性能の高い識別器を作る手法のことである [1]。最終的な強識別器は弱識別器の重み付き多数決によって構成され、それを式で表すと以下のようになる。
(N)∑
C(x) = sign
wi ci (x)(1)
i=1

この時、x は入力画像ベクトル、wi（実数値）は弱識別器の重み、ci ∈ {−1, 1} は弱識別器の出力、C(x) は強識別器の出力を表している。

2.2

図 1: 方法

QBoost2.3

Boosting の中で最もよく利用されている方法として、
AdaBoost と呼ばれるものがあるが、AdaBoost において弱識別器に対する重み wi は連続値となっており、本研究で用いるアニーリングマシンにそのまま載せることができないので、アニーリングマシン用の Boostingアルゴリズムである QBoost を用いることにする [2]。
QBoost では弱識別器の重みは 0 か 1 の値を取り、i番目の識別器を使用するかどうかを表しており、最適な重み wi の組を求めることによって、どの識別器を使えば出来るだけ少ない数の弱識別器でより良い性能を得ることができるかを明らかにすることができる。
最適な重み wi の組合せを決定するために、アニーリングマシンを用いる。アニーリングマシンに組合せ最適化問題を解かせるためには、解く問題を QUBO
(Quadratic unconstrained binary optimization) という形式 (次式) に変換する必要がある。
∑∑
H=
hi wi +Jij wi wj
(2)
i

決定木

本研究では、弱識別器として決定木を用いた。決定木とは、変数とその値の組によって表現されたデータを、条件分岐によってグループに分類する手法である。
条件分岐を繰り返すことで、データはツリー状にどんどん展開され、解くべき最小単位に分割される。

3結果と考察手書き数字データセット mnist[3] を用いて手書き数字認識を行なった。
まず最初に、正則化項のパラメータ λ = 3、弱識別器の数は 35 個、木の深さは 1 とし、数字 0 と 1、数字3 と 8 の二値分類を行った。それぞれ、訓練データを増やしていった時の正答率をグラフにしたものが図 2と図 3 である。この時、訓練データとテストデータの割合は 8:2 になるようにした。
数字 0 と 1 の分類では、訓練データが 100 個ぐらいあれば正答率９割以上を得られており、精度が良いことがわかる。また、弱識別器の数を減らしても正答率は９割以上得られ、数字０と１だけの二値分類が簡単だったためだと考えられる。

i<j

問題を QUBO の形にするために識別器の出力と正解9いる。これもまた、訓練データを増やすと正答率も上昇する。また、弱識別器の個数を増やすと正答率が上がっており、弱識別器をまとめることでより精度のよい強識別器が作れていることが分かる。
次に、訓練データを 10000 枚、テストデータを 2000枚、パラメータ λ = 5 に固定して弱識別器の個数を変化させた時の正答率を見た。結果を図 5 に示す。

図 2: 数字 0 と 1 の分類結果：
正答率のデータ数への依存性

図 5: 正答率の弱識別器の個数への依存性
弱識別器の個数を増やしていくに連れ途中まではだんだんと正答率が上がっていくことが分かる。しかし、途中からは正答率が下がっていき、過学習が起こっていると考えられる。そこで、過学習が起こっている弱識別器 45 個の時に、パラメータ λ の値を調整した。すると、λ = 15 あたりで使用する弱識別器の数は 34 個に減り、正答率 0.9765 が得られ、過学習が防ぐことができた。

図 3: 数字 3 と 8 の分類結果：
正答率のデータ数への依存性

4

図 3 は青の線が訓練データ、オレンジの線がテストデータに対する正答率を表している。訓練データの数を増やすにつれて正答率が上がった。また、数字 0 と1 の二値分類と比べると、3 と 8 の分類の方が正答率が低く 3 と 8 の分類の方が難しいことが分かる。
次に、数字 0 とそれ以外の 1∼9 の二値分類を行った。
これまでと同様に、正則化項のパラメータ λ = 3、弱識別器の数は 35 個、木の深さは 1、訓練データとテストデータの割合は 8:2 とした。

まとめと今後の課題

アニーリングマシン用の Boosting アルゴリズムである QBoost を用いて、画像の二値分類を行うことができた。訓練データや弱識別器の個数を増やすことによって、正答率が上がることを確認した。また、弱識別器の個数を増やしすぎると過学習を起こすが、パラメータ λ を調整することによって、過学習を防ぐことができた。今後は二値分類を組み合わせて多値分類を行い、最終的には車のナンバープレートの画像認識を行いたいと考えている。

謝辞
本研究は一部、未踏ターゲット事業の支援を受けている。

参考文献[1] 西森秀稔, 大関真之, 「量子アニーリングの基礎」(共立出版, 2018).
[2] H. Naven, et al., ”NIPS 2009 demonstration: Binary classification using hardware implementation of quantum annealing.”, arXiv:0912.0779.
(2009)

図 4: 数字 0 とそれ以外 (1∼9) の分類結果。

[3] 手 書 き 数 字 デ ー タ セット(mnist),https://www.kaggle.com/c/digitrecognizer/data (2018 年 10 月 23 日 ア クセス)

凡例の数字は弱識別器数。
図 4 は訓練データを増やしていった時の正答率をグラフにしたものである。青の線は弱識別器が 35 個で、オレンジの線は弱識別器 15 個の時の正答率を表して10