Multi-objective optimization on networks and its applications to machine learning

点击翻译按钮获取中文摘要

今年度は機械学習の重要な分野の一つである逐次的意思決定問題に取り組んだ． 具体的には「限られた観測に基づく密グラフ抽出に対するバンディットアルゴリズム」に関する研究を行なった：実ネットワーク上の密な部分構造の抽出は, グラフマイニングにおける重要な操作の一つである．本研究では，（重みが未知の）枝集合からの限られた観測に基づく密グラフ抽出を考え， バンディット問題としての定式化と二つのアルゴリズムを提案した． この研究成果は機械学習の難関国際会議であるICML2020に採択されている．また上記の研究をさらに発展させる一般的な枠組みを提案する研究として， 報酬関数がリプシッツ連続性を満たす任意の場合に対するアルゴリズムの提案と理論解析を与えた． この結果は人工知能の難関国際会議であるAAAI2021に採択された. さらに， 選択した行動を構成する各要素( e.g. ネットワークにおける枝)が観測として得られる場合に対しては， 情報論的下界と一致する最適なアルゴリズムを提案した． また， 非線形関数の特殊ケースとして，選択した行動を構成する要素のうち最も報酬が小さいもので全体の報酬が定義されるbottleneck rewardという重要な設定に対してはよりタイトな理論保証を持つアルゴリズムを設計した．これらの結果をまとめた論文は機械学習の国際会議に投稿中である．今年度は本課題のまとめとしても，国際的にインパクトのある研究成果を出すことができた． 本研究の総括を基に， さらなる実社会への汎用性の高いアルゴリズム設計とその理論解析を目指す予定である．