研究展示

データと学習の科学

01

混み具合いを学習して空いてる経路を見つけます

二分決定グラフを用いたオンライン最短経路アルゴリズム

どんな研究

通信ネットワーク等において経路を繰り返し選定する際に、混雑が少ない経路を自動的に選定します。混雑度は急速かつ不規則に変化し得るため送信時の混雑度はわからず、かつ可能な経路の数は膨大であるため、過去データからの臨機応変な学習技術と効率的な計算技術が求められます。

どこが凄い

混雑度の学習や経路の選定を素朴な方法で行うと、経路の多さゆえに莫大な計算時間がかかります。私達は二分決定グラフとよばれるデータ構造を用いて経路全体の集合を小さく表現し、そのデータ構造上での学習手法を開発することで、現実的な時間で動作する世界初の手法を実現しました。

めざす未来

本技術を用いることで、混雑度が急激に変化し得る状況下でも、高効率なネットワーク通信経路や短時間で移動可能な道路網上の経路を選定できます。今後はより大規模な通信ネットワークや広域道路網などへの適用を行い、様々な現実的場面で活用できる技術の実現を目指します。

関連文献

  • [1] S. Sakaue, M. Ishihata, S. Minato, “Efficient bandit combinatorial optimization algorithm with zero-suppressed binary decision diagrams,” in Proc. 21st International Conference on Artificial Intelligence and Statistics (AISTATS), 2018.
  • [2] N. Cesa-Bianchi, G. Lugosi, “Combinatorial bandits,” Journal of Computer and System Sciences, Vol. 78, No. 5, pp. 1404—1422, 2012.

ポスター

アイコンをクリックすると、展示ポスターのPDFが開きます。
PDFの表示にはAdobe Acrobat Reader等のPDF閲覧表示が必要です。

当日の様子

連絡先

坂上 晋作 (Shinsaku Sakaue) 協創情報研究部 言語知能研究グループ
Email: