Combinatorial secretary problems and online machine learning

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

本年度は、昨年度に引き続いて「適応的劣モジュラ比」に関する研究をおこなう一方で、「局所探索による集合関数最大化」に関する研究にも取り組んだ。昨年度、適応的な意思決定問題の解きやすさを表す指標として適応的劣モジュラ比（adaptive submodularity ratio）を考案した。適応的劣モジュラ比とは、「目的関数がどれくらい適応的劣モジュラ関数に近いか」を表す値である。適応的劣モジュラ比を用いれば、貪欲法がよい近似解を出力することを保証できる。今年度は、適応的劣モジュラ比の枠組みを利用して、オンライン機械学習のさまざまな問題を解析した。また、現実的な意思決定問題に用いられるバッチ適応的最適化の設定へと、適応的劣モジュラ比の枠組みを拡張した。適応的劣モジュラ比に関する研究成果の一部は機械学習分野の国際会議International Conference on Machine Learning（ICML2019）に採択された。さらに、「局所探索による集合関数最大化」に関する研究もおこなった。集合関数最大化は、スパース回帰やグラフィカルモデルの構造推定など、機械学習の重要なタスクに現れる最適化問題である。集合関数最大化問題に対してよく用いられるアルゴリズムの一つに局所探索がある。局所探索は、実用的にはよい解を出力することが知られているが、その理論的性質は十分には知られていない。本研究では、集合関数が満たすべき性質として局所化可能性（localizability）を提案し、いくつかの応用にこの性質が表れることを示した。この成果をまとめた論文は機械学習分野の国際会議に現在投稿中である。