11 2018/12 01
25262728293001
02030405060708
09101112131415
16171819202122
23242526272829
30310102030405
Click セミナー

過去のセミナー

開催日2018年10月3日(水曜日)
開催時間13時30分-14時30分
発表者Holakou Rahmanian 
発表者の紹介Department of Computer Science,
University of California Santa Cruz
タイトルOnline Dynamic Programming 
発表の概要
We consider the problem of repeatedly solving a variant of the same dynamic programming problem in successive trials. An instance of the type of problems we consider is to find a good binary search tree in a changing environment. At the beginning of each trial, the learner probabilistically chooses a tree with the n keys. The learner is then told the frequencies of the keys and is charged by the average search cost for the chosen tree. The problem is online because the frequencies can change between trials. The goal is to develop algorithms with the property that their total average search cost (loss) in all trials is close to the total loss of the best tree chosen in hindsight for all trials. The challenge, of course, is that the algorithm has to deal with exponential number of trees. We develop a general methodology for tackling such problems for arbitrary dynamic programming algorithms with min-sum recurrence relations. Our framework allows us to extend online learning algorithms like Expanded Hedge and Component Hedge to a significantly wider class of combinatorial objects than was possible before.
開催場所京都大学 情報学研究科 総合7号館235号室
接続サイト北大VBL、神田ラボ