動的計画法に基づくオンライン予測に関する研究

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

本研究は,オンライン予測モデルに基づく一連の最適化問題のクラスに対し,一般に適用可能なアルゴリズムの設計の指針を与えようとするものである.オンライン予測モデルとは,次のような一般的なスキーマとして述べることができる.各時刻t=1,2,...ごとに,アルゴリズムはエキスパートと呼ばれるn個のオラクルから予測値系列x_t,1,...,x_<t,n>を受け取り,それに基づいて自らの予測値y^^<^>_tを出力する.その後,真のデータy_tを観測する.このとき,ある定められた損失関数Lに基づいて,アルゴリズムは損失L(y_t,y^^<^>_t)を被るとする.アルゴリズムの目標は,損失の総和Σ_tL(y_t,y^^<^>_t)を,最適なエキスパートの損失min_iΣ_tL(y_t,x_<t,i>)と同程度に抑えることである.これまで,さまざまなオンライン予測モデルに対しさまざまなアルゴリズムが提案されているが,いずれも損失の上界はエキスパート数nの対数を用いて与えられることが示されている.これは,nが指数関数的に大きい場合でも損失はそれほど大きくならないことを意味しており,さらに,エキスパートがある特殊な構造を持ち,これらの予測値系列を圧縮して表現できるならば,効率の良いアルゴリズムが存在する可能性を示唆している.HelmboldとSchapireは,決定木の枝刈り問題がこのような構造を持つことを示した.すなわち,すべての枝刈りをエキスパートとみなしたのと同等のデータ構造を線形空間に圧縮して表現することができる.本研究では,枝刈り問題をバッチモデルの下で考えた場合,すなわち,アルゴリズムに観測データy_1,y_2,...が一度に全部与えられるとした場合には,この問題は動的計画法を用いて効率良く解ける構造を持っていることを見い出した.そして,この観測に基づき,オンライン予測アルゴリズムを設計することによって,HelmboldとSchapireと同様の結果を導き出せることを示した.さらに,本研究ではこれを一般化し,問題がバッチモデルの下で動的計画法を用いて効率良く解けるとき,その問題がオンライン予測モデルの下でも効率のよい予測アルゴリズムを持つ条件を与え,そのアルゴリズムの設計指針を与えた.