本記事で紹介する論文では、D-Waveマシンを用いた量子アニーリングにより二値変数制約のついた 非負値行列分解 の手法と顔画像認識に応用した結果を示している。速度性能評価のために、古典的アルゴリズムを用いるGurobiとqbsolv（タブーサーチ）を用いた場合とD-Wave 2Xで得られた最適解に逹する累積TTT (time-to-target)を測り、そのアニーリング回数依存性を比較・検討している。
文献情報
Daniel O’Malley, Velimir V. Vesselinov, Boian S. Alexandrov, Ludmil B. Alexandrov, “Nonnegative/binary matrix factorization with a D-Wave quantum annealer”, arXiv:1704.01605.
非負値行列分解 (NMF)とは
非負値行列分解 (Nonnegative Matrix Factorization; NMF) は、$n \times m$行列$V$を全て非負値の要素からなる$n \times k$行列$W$と$k \times m$行列$H$の積で表すものである。完全な分解が得られない場合でも、両辺の差が最も小さくなるような近似値を得るための古典的なアルゴリズムはいくつか知られており、例えば[D.D. Lee and H.S. Seung, Nature 401 (1999) 788.]はその一例であり、また顔画像認識への応用が示されている。非負値行列分解はこのようにパターン認識や時系列解析など様々な局面で応用されている重要な手法である。
本論文で扱う手法 -二値制約非負値行列分解 (NBNF)-
本記事で扱う論文では分解先の二つの行列のうち一つを、その成分が0, 1の二値のみを取りうる二値制約付き非負値行列分解をD-Waveマシンを用いて行うための方法を扱っている。すなわち、
$$V \approx WH$$
ここで$W$のいかなる要素も非負値を取ること($W_{ij}>0$)。$H$の要素は($H_{ij} \in \{0, 1\}$)の二値しか取らない。
量子アニーリングをどこに用いるか
基本的にNMFは行列$W$と$H$に関して、交互に最小二乗法を用いて逐次更新することで解くことができる。このうち二値制約のある行列$H$の更新にのみ、以下の模式図のようにD-Waveマシンを用いる。
行列$H$の更新に際しては、
$$
H_{i}=\arg\min _{X \in \{0,1\}^{k}}\|V_{i}-(WX)_{i} \|_{2}
$$
のように行ごとに独立して行うことができるため、これにより変数を$k$個まで減らすことができる。D-Wave 2Xの備える量子ビットは1024であり、実際に用いることのできる変数の数はこれ以下に制限されるため、このように変数の数を減らす工夫は非常に大切である。
D-Waveマシンに実装するためのQUBO表現
行列$H_{i}$の更新式は次のようにQUBO表現に置き換えることができる。QUBO表現の一般形を
$$
f({\bf q}) = \sum^{}_{i} a_{i} q_{i} + \sum^{}_{i<j}b_{ij} q_{i} q_{j}
$$
のように表した時、その時の係数は以下のように与えられる。
$$
a_{j} = \sum^{}_{k}W_{kj} (W_{kj} – 2V_{ij})
$$
$$
b_{jk} = 2 \sum^{}_{l} W_{lj} W_{lk}
$$
この問題においては、D-Wave 2Xのチップの欠陥を考慮し、変数の数を35個に制限した。
結果
顔画像認識への応用結果
過去に非負値行列分解を使って顔のパーツを学習するために分析されたものと同じである2,429個の顔画像を分析した。（参照：Learning the parts of objects by non-negative matrix factorization） 下図は10,000回アニーリングを実行したときに学習された特徴である。一見、真っ黒に見える画像もあるが、実際微かな特徴を含んでいる。
二値制約付きに限定した影響
NBMFをNMFの優劣を次の表に示す。
| NMF | NBMF | ||
|---|---|---|---|
| $H$（選択する特徴の数） | 13% スパース | 83% スパース | NBMFが有利 |
| $\|V-WH\|_{F}$（誤差） | NBMFの半分の誤差 | NMFの２倍の誤差 | NMFが有利 |
| $W$（特徴の複雑さ） | 43% スパース | 密 | NMFが有利 |
すなわち、誤差が2倍になる一方、必要となる成分の数は1/4程度に削減することができている。必要となるデータ数の削減に対して、誤差の増大のスケーリングが小さいため用途によっては十分に活用できる場面が存在しうると記事担当者は考える。
古典ソルバーとの速度性能比較
D-Waveのパフォーマンスを古典ソルバーであるqbsolv (タブーサーチ)とGurobiで比較する。D-Waveマシンは最適解を得るために10, 100, 1,000, 10,000回のアニーリング回数が与えられる。そこで得られる最適解をターゲット値とし、qbsolvとGurobiが少なくともその値くらいに良い解を得るまでの時間(TTT)を計算する。もし、10分以上かかった場合は計算を打ち切り、TTTは10分とした。実際には、Gurobiは10分以上かかる事は無かったが、qbsolvはいくつかのケースにおいて10分以上時間を要した。
計算時間の比較結果は次のようになった。
Gurobiとqbsolvのパフォーマンスは異なる傾向を示した。qbsolvは頻繁に一回一回のアニーリング時間よりも早くターゲット解に到達したが、アニーリング時間内に到達できなかったときは比較的に長い時間を要した。このせいで、qbsolvの累積TTTは大きくなっている。D-Waveがより多くのサンプルをとるに従い、アニーリング時間を超える回数が増えた。Gurobiはターゲット解に到達するのに長い時間を要さなかったが、とても速く解くことも滅多になかった。
本記事の担当者
羽場廉一郎 （編集：観山正道）