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

基于动态规划的在线预测研究

• 批准号: 10780160
• 负责人: 瀧本 英二
• 金额: $ 1.28万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 1999
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-10780160/
• 关键词: 計算学習理論; オンライン予測モデル; エキスパートモデル; 動的計画法; 決定木; 枝刈り

本研究は,オンライン予測モデルに基づく一連の最適化問題のクラスに対し,一般に適用可能なアルゴリズムの設計の指針を与えようとするものである.オンライン予測モデルとは,次のような一般的なスキーマとして述べることができる.各時刻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と同様の結果を導き出せることを示した.さらに,本研究ではこれを一般化し,問題がバッチモデルの下で動的計画法を用いて効率良く解けるとき,その問題がオンライン予測モデルの下でも効率のよい予測アルゴリズムを持つ条件を与え,そのアルゴリズムの設計指針を与えた.

这项研究试图为设计基于在线预测模型的一系列优化问题设计通常适用算法的指南。在线预测模型可以描述为以下一般架构：每次t = 1,2，...，该算法从n个oracles中接收到名为专家的n oracles的预测值序列x_t，1，...，x_ <t，n>，并输出其自己的预测值y ^^ <^> _ t。之后，观察到真实的数据y_t。目前，获得了一定的定义损失。基于函数L，算法假设损失L（y_t，y ^^ <^> _ t）。该算法的目标是将损失的总和（y__t，y ^^ <^> _ t）与损失的程度相同的程度与MIN_I_IDL（Y__TL（y__tl（y_tl），y_tl（y__t，x_________________）的程度相同。过去，已经为各种在线预测模型提出了各种算法，并且已经表明，使用专家编号n的对数给出了损失的上限。这意味着即使n呈指数级，损失也不那么大。这意味着没有，进一步表明，如果专家具有特殊的结构并可以压缩这些预测序列，则可能会有有效的算法。Helmbold和Schapire表明，决策树的修剪问题具有这种结构。也就是说，可以通过压缩它们在线性空间中表达等于所有被考虑的专家的数据结构。在本研究中，当修剪问题被视为批处理模型时，即在算法中使用观察到的数据y_1，y_2。如果 。立即给出，我们发现此问题具有可以使用动态编程有效解决的结构。基于此观察，我们表明与Helmbold和Schapire相同的结果可以通过设计在线预测算法来得出。此外，在这项研究中，当可以在批处理模型下使用动态编程有效地解决问题时，该问题即使在在线预测模型下也具有有效的预测算法，并提供了算法设计准则。

项目成果

Eiji Takimoto: "Structured Weight-Based Prediction Algorithms" Lecture Notes in Artificial Intelligence. 1501号. 127-142 (1998)

Eiji Takimoto：《基于结构化权重的预测算法》人工智能讲座笔记，第 1501 期。127-142 (1998)