離散構造のオンライン予測に関する研究

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

本研究では，オンライン組合せ最適化問題を扱った．この問題は，決定空間が組合せ論的に定義されるオンライン最適化問題であり，実世界に多くの応用を持つ．一方，有用な問題の多くは，対応するオフライン版の組合せ最適化問題がNP困難であることから，計算量の問題を克服する必要がある．既存の研究成果として，効率的なオンライン組合せ最適化アルゴリズムが存在するための十分条件が与えられている．その条件とは，ある凸な緩和空間が存在して，(i) その緩和空間への射影が容易であること，および，(ii) 緩和空間からの効率の良いメタラウンディングが存在することである．それに対する本年度の研究成果として，上記の十分条件をさらに一般化することに成功した．具体的には，上記の条件 (i) を緩め，緩和空間を含む複数の階層的な緩和空間が存在して，外側の緩和空間から内側の緩和空間に向けて段階的に射影する問題が効率よく解ければ良いことを示した．本手法の適用例として，オンラインジョブスケジューリングがあり，最適な性能を持つアルゴリズムを与えた．また，大規模機械学習に対する新しいアプローチとして，圧縮データ上の学習法を提案した．提案手法は，まず訓練データを閉路のない有向グラフによる圧縮表現に変換し，データを陽に展開することなく，訓練データ上のブースティングを正確に模倣する．本手法では，訓練データの各事例が有向グラフの道に1対1対応するため，本手法におけるブースティングは，グラフの道集合を決定空間とするオンライン組合せ最適化問題とみなすことができる．道集合に対する効率的なオンライン組合せ最適化アルゴリズムを利用することにより，提案手法は，各試行につきグラフのサイズに比例する時間で動作する．これは，訓練データの圧縮率が高いほど計算効率が良いことを意味し，大規模機械学習の新しい方法論として期待できる．