共同研究・競争的資金等の研究課題

2018年4月 - 2021年3月

複数目的を考慮したネットワーク最適化法の構築と機械学習への応用

日本学術振興会  科学研究費助成事業 特別研究員奨励費
  • 黒木 祐子

課題番号
18J23034
配分額
(総額)
2,200,000円
(直接経費)
2,200,000円
(間接経費)
0円

本年度は強化学習の一つである多腕バンディット問題に取り組んだ.道路ネットワークや通信ネットワークにおける経路は,グラフとして数学的に表現することでグラフ上の「木」や「パス」といった組合せ構造として捉えることができる.本研究ではこのように実用上でも重要な応用を持つ組合せバンディットにおける最適腕識別問題に取り組んだ.既存研究では単一の腕を一つずつ探索することを許すなど応用上では実現が難しい仮定を置いていたが,本研究では腕集合を直接探索しその報酬のフィードバックのみから最適な腕集合を求める画期的なアルゴリズム設計に成功し,サンプル数の上界を証明した.このアルゴリズムを得るために,サイズ制約付きの0-1二次計画問題に対する近似アルゴリズムを新たに提案し,バンディット問題で生成されうるインスタンスの良い性質を利用することで,この問題に対する理論的な精度保証を与えた.
以上の研究と並行してハブネットワーク設計問題に対する近似アルゴリズムの研究に取り組んだ.ハブネットワーク設計問題は総輸送費用を最小にするようにハブと非ハブの割当を決定する問題であり,数学的にはメトリックラベリング問題と呼ばれる画像分割におけるエネルギー最小化問題とも等価である.この問題は一般にはO(log |ハブの数|)近似が近似の限界として示されているが,どのような特殊クラスが定数近似アルゴリズムを認めるかは未解決であった.本研究ではハブのネットワーク形態が通信ネットワークで現れる特殊な形態を仮定することで,定数近似アルゴリズムが存在することを証明し,多項式時間定数近似を認める新たなクラスを発見した.

ID情報
  • 課題番号 : 18J23034