量子アニーリングを用いたレビュアー割当最適化の検討
峯尾 真一 1), 野口 孝明 1), 草間 義紀 1), 松田 佳希 2)
1) 高度情報科学技術研究機構
2) 株）フィックスターズ
mineo@rist.or.jp

Optimization of Reviewer Assignment using Quantum Annealing
Shinichi Mineo 1), Takaaki Noguchi 1), Yoshinori Kusama 1), Yoshiki Matsuda 2)
1)Research Organization for Information Science and Technology
2) Fixstars Corporation
概要
HPCI 利用研究課題の審査におけるレビュアー割当問題においては、申請課題とレビュアー候補の数が増えると組合せの数が爆発的に増えるため、AI で計算した申請課題とレビュアー候補の適合度を基に、量子アニーリングを用いて最適解を求める方法を検討した。
量子アニーリングの効果を疑似アニーラにより実現し、過去の実データを試験データとして組合せ最適解探査を行い、試行錯誤的アルゴリズムとの比較を行った。その結果、量子アニーリングの有用性が明らかになり、将来的には AI と連携させてレビュアー割当の全プロセスを人間の介入無しに、迅速に処理することの可能性を示した。

1

り、課題審査委員会がこの中から優れた課題を選はじめに定して計算資源を配分し、選定委員会の承認を経HPCI[1]の課題審査においては、各課題に対して採択される。HPCI においては申請課題をピ予め登録されたレビュアー候補の中から適切な人ア・レビューにより評価することを原則としておを複数選んで評価を依頼している。そこでは、

り、年度毎に各学術分野の専門家にレビュアー就様々な分野の多数の応募課題に対し、多岐に渡る任の依頼を行い、承諾された人をレビュアー候補

専門分野のレビュアー候補から適切な人を選ぶたとして登録する。その数は年度毎に変わるが、現めに、AI を用いて課題毎に全レビュアー候補の在は約 300 人である。
課題審査委員会は、審査の公平性やレビュア適合度を計算している[2]。
そのデータを基に、課題毎のレビュアー数、ーの負荷の観点から課題毎のレビュアー数とレビレビュアー毎の担当課題数の制約条件を満たしたュアー毎の割当課題数の目安を定めている。その課題とレビュアーの最適な組合せを探す必要があ

制約条件を満たした上で各課題に最適なレビュアるが、（100～200）課題×（100～200）レビュアーの組合せを探すことが必要となる。

ー候補の規模となると、組合せの可能性が爆発的

また、課題内容に対して適切なレビュアーを探に大きくなるため、全ての場合を計算して最適解すために、AI を用いて課題毎に全レビュアー候を求めることは現実的ではなくなる。

補の適合度を計算している。この適合度は、課題従来は試行錯誤的に制約条件を満たす解を見毎の各レビュアー候補の相対的な評価値となってつける方法を用いていたが、最適解の探査を行うおり、その課題毎の合計は 1 となる。（詳細は[2]ためには効率が悪い。そのため新しいアプローチ参照）すなわち異なる課題のレビュアーの適合度として量子アニーリングによって組合せ最適解をは、絶対値として相互に比較することができない。

探す方法を検討した。

また、実際には課題の参加者とレビュアー候補が利益相反関係にある場合には、この適合度を-1 と2課題とレビュアーの組合せ問題して、レビュアーとして割り当てられないようにHPCI システム利用研究課題の定期募集において、秋の募集では例年 100〜200 課題の申請があ92している。以上の理由から、レビュアー候補の比較を、この適合度を基にして計算した課題毎の優先順位を用いて行い、割り当てられた全レビュアてられたレビュアーの順位の合計値の試行錯誤ーの順位の合計を評価指標として、最適解はこの的アルゴリズムとの比較、②課題毎に優先順位値が最も小さくなるものと定義した。

が上位のレビュアー採用数の調査、③従来の方3 QUBO 模型による定式化法である試行錯誤的アルゴリズムの結果との一一般的な QUBO(Quadratic Unconstrained BinaryOptimization）による定式化は以下の通りとなる。
M 件の課題があり N 人のレビュアー候補がいる場合、決定変数はここで、試行錯誤的アルゴリズムとは、以下の通りである。
①AI の適合度表から課題毎に上位 15 人のレビュアー候補を抜き出し割当候補とする。

：課題 i にレビュアーj を割り当てる場合に②課題毎に候補の上位からレビュアーの 1 人目を割り当てる。但しレビュアーの割当課題数は1、それ以外の場合に 0 とする。

10 を越えていないことを確認する。

最適解の評価指標となる目的変数は③同様にレビュアーの 2 人目と 3 人目を割り当

𝑀𝑀−1 𝑁𝑁−1𝛴𝛴𝑖𝑖=0𝛴𝛴𝑗𝑗 =0 𝑤𝑤𝑖𝑖𝑖𝑖 𝑞𝑞𝑖𝑖𝑖𝑖て、課題当り 3 人、レビュアー当り最大 10 課となる。但し、プロジェクト i にレビュアーjを割り当てた時の優先順位（1 から始まる整数値）を致度の調査、の三つの方法を用いた。

題の割当表を作成する。
（レビュアー当りに割り当てられた担当課題は 1~10 課題となる）とする。

④レビュアーの課題割当数を調べて、制約条件

制約条件はの 5 課題以上 10 課題以下となるまで適合度表

Ⅰ.１つの課題に対し c 人のレビュアーを割りでなるべく上位のレビュアーに置き換える。この時、1 課題割当者を 2 課題以上の割当者へ置当てる。

き換え、2 課題割当者を 3 課題以上の割当者へ

for all

置き換えという順で最終的に 5 課題以上、10 課

Ⅱ.1 人のレビュアーに割り当てられる課題数は、0 または a 以上 b 以下とし、or題以下の条件に到達するまで続ける。但し 15位までのレビュアー候補で置き換えできない場

andfor

合は、現状のままとする。
上記の結果は、置き換える順序で結果は変化

allするため、操作する課題の順序は乱数を用いてとなる。
この様に定式化された最適化問題は、量子アニ決定し、100 ケースの割当表を作成した。

ーリングにより解くことができる。

5 量子アニーリングの利用
4

評価の方法

今回の評価試験において、量子アニーリング

量子アニーリングの実用性を評価する試験にの実行には、最大課題数 200×最大レビュアー

は、過去に実際に審査された 98 課題と、その時数 200=40,000qubits（量子ビット）の規模の計のレビュアー候補 110 人のデータを用い、制約算が必要となる。現在この規模に対応できる量

条件を、課題当りのレビュアー数を 3 人、レビ子アニーリングマシンは存在しないが、GPU 等

ュアー当りの課題数を 5 課題以上、10 課題以下を活用した疑似アニーリングシステムの利用がとした。

可能である。今回の量子アニーリング評価環境

また、量子アニーリングによる最適解探査結果を評価するために、①評価指標である割り当93としてはクラウドサービス Fixstars Amplify[3]を用い、1 回の探査時間を 10 秒とした。

2．で示した定式化をそのまま Amplify のライブラリで実装したが、制約条件の内、「1 人のレビュアーに割り当てられる課題数が、0 または 5 以上 10 以下」という非連続条件については、以下の通り単純な制約条件を段階的に用いて漸近的な解を求めた。
①全課題に対し、全ｎ人のレビュアー候補の内から 3 人を割り当てる。

できた。但し量子アニーリングには確率的なア->制約条件をレビュアー当り 10 課題以下とルゴリズムが使われているため、同じ解が得らする(Amplify: less_equal())

れる保証はないので、今後は、そのばらつきを②上記の結果から、割当課題数<2 のレビュアー測定して統計的に検証する必要がある。

(n2 人）を外し、全課題に対して(ｎ-n2)人のレ6.2 課題毎の優先順位(1~15)の採用数ビュアー候補で再割当を行う。
->制約条件を 2 課題以上 10 課題以下とする。
(Amplify: clamp())->すなわちレビュアー候補を割当課題数の多量子アニーリングを用いて得られた結果に対して、課題毎の優先順位 1~15 位のレビュアー候補がどれくらい推薦されるかを調べて、表１の結果を得た。これを見ると、3 人×98 課題=延べ 294い人に限定して再試行する。

人のレビュアーはほぼ全て 15 位以内となってい③上記の結果から、割当課題数<3 のレビュアー

る。（5~10 課題の時の延べ 294 人中 1 人を除く）(n3 人）を外し、同様の割り当てを実施。

また、レビュアー当りの課題数条件を厳しくす④以降、制約条件の 5~10 になるまで繰り返す。

ると、より下位のレビュアー候補が推薦される傾

なお、クラウドの利用において、アップロー向があることが分かる。3~10 人であれば、10 位ドされるデータは適合度を順位に変換した二次元行列のみであり、データセキュリティの面かまでのレビュアー候補で組合せが実現できる。
この結果から、量子アニーリングの最適解探査がうまく機能していることが分かる。

らの問題も無くしている。
6.3 試行錯誤的アルゴリズムとの比較

試行錯誤的アルゴリズム 100 回の試行を行っ

6 評価結果た結果として割り当てられたレビュアーと、

6.1 評価指標最適解の指標である全レビュアーの順位合計（レビュアー当りの割当課題数が 5 以上の制約条件）は、量子アニーリングが 954 に対し、試
行錯誤的アルゴリズムでは最小値 965、最大値1043 となっている。量子アニーリングでは組合せ最適解により近いものが得られることが確認

94

Amplify を利用した 1 回の試行の結果割り当てられたレビュアーとの一致度を比較した結果を
図 1 に示す。
試行錯誤的アルゴリズムを 100 回繰り返しても、より最適解に近い量子アニーリングの結果と 84~88%一致する解しか得られない。これは、

試行錯誤的アルゴリズムで最適解を探査するには、さらに多くの試行が必要であることを示唆しており、組合せ最適解探査における量子アニーリングの優位性を示すものと考えられる。

7 まとめ
量子アニーリングによる組合せ最適解探査は、疑似アニーラによる評価により、課題とレビュアー候補の組合せ問題に対し有効であり、また疑似アニーラであっても現実的な手法として性能上問題が無いことが明らかとなった。この探査を組み込むことにより、申請された課題に対して、レビュアー候補の適合度を AI で計算し、その結果を用いて制約条件を満たす課題とレビュアーの最適な組合せを探すところまで、全プロセスで人間を介さない迅速な処理が可能となる。但し、AI の適合度計算の結果には一部に不適切な結果が含まれる可能性があるため、現状では人間による補助と各プロセスにおける結果の検査が必要となる。
人間による補助としては、課題とレビュアーの専門分野を指定して同じ分野同士でマッチングするようなバイアスが掛かるように、レビュアーの適合度を調整することが考えられる。
また AI のモデルは現在単純な 3 層の DNN(DeepNeural Network)となっており、ハイパーパラメータのチューニングも十分ではない。AI をさらに進化させることができれば、将来的には人間の介入を最後の結果の検査だけにすることも可能であると考える。

参考文献[1] HPCI について（HPCI ポータルサイト）,
https://www.hpci-office.jp/pages/about_hpci[2] 峯尾真一,他,「HPCI の課題審査におけるレビュ ア ー 選 定 の た め の AI 活 用 の 試 み 」 ,https://axies.jp/_files/conf/conf2020/FA5-1.pdf,
AXIES2020 年度年次大会, 2020 年．
[3] Amplifyの ホ ー ム ペ ー ジ ,https://amplify.fixstars.com/ja/95