データの学習容易性解析に基づく実ケース学習理論の確立

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

主に以下の成果を得た．１．オンライン行列補完問題は，推薦システムの基盤となる問題である．この問題では，各試行において，アルゴリズムが0-1行列を予測すると，環境から行列のある成分 (i,j) における真の値が与えられる．アルゴリズムの目標は，予測の誤り回数を最小化することである．従来手法は，初めに真値行列に関する補助情報が与えられると一般化した上で，オンライン半正定値計画（OSDP）問題に帰着するものであるが，タイトな誤り回数の上界を達成できていなかった．本研究では，この帰着において，OSDP問題を解くアルゴリズムで用いる正則化項を，補助情報を用いて補正することで，誤り回数のタイトな上界を導出することに成功した．２．エキスパート統合問題では，学習容易性解析に基づき，現実的な仮定のもとで非自明なリグレット上界を導出した．既存研究では，環境が開示する損失ベクトルを並べることにより得られる損失行列のランクを学習容易性指標とするものがあるが，損失行列が低ランクであるという強い仮定をおく必要があった．また，この仮定を緩和し，損失行列が低ランク行列で近似可能とした場合の研究もあるが，その低ランク行列に関する情報をアルゴリズムに与えておく必要があり，実用的ではなかった．本研究では，そのような事前情報を与えることなく，損失行列が低ランク行列で近似できる場合に，非自明なリグレット上界を導出することに成功した．３．センサーネットワークにおいて，スループットとエネルギー消費効率の両方を最適化するように近隣のセンサーを選んでネットワークを動的に構築する問題に対し，バンディットの手法を応用した手法を提案し，実験によってその有効性を示した．