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

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

• 批准号: 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と同様の結果を導き出せることを示した.さらに,本研究ではこれを一般化し,問題がバッチモデルの下で動的計画法を用いて効率良く解けるとき,その問題がオンライン予測モデルの下でも効率のよい予測アルゴリズムを持つ条件を与え,そのアルゴリズムの設計指針を与えた.

In this paper, we propose a method to solve the optimization problem of the basic system, which is generally applicable to the design of possible systems. The first is to predict the future, and the second is to predict the future. Each time t= 1, 2,... The estimated value series of n numbers is x_t,1,..., x_<t,n> is a function of the input force, y^<^>_t is a function of the input force. After that, the truth is that the y_t is not measured. The loss L(y_t, y^^<^>_t) is the loss L(y_t,y^^<^>_t). The loss sum Σ_tL(y_t,y^^<^>_t) is the optimal loss min_iΣ_tL(y_t,x_<t,i>). The number of pairs of pairs. In this case, the loss of n is large and the exponential relationship is large.Helmbold and Schapire indicate the possibility of existence of a good efficiency in the case of a special structure. The structure of the linear space is compressed. In this paper, we study the problem of branch cutting and the problem of branch cutting. For example, if you want to use the method of planning, you can use the method of planning. The results of Helmbold and Schapire are shown below. In addition, this study generalizes the problem of how to use the dynamic planning method to solve the problem of how to predict the efficiency of the system.

项目成果

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

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