Efficient Tracking of Large Classes of Experts
Efficient Tracking of Large Classes of Experts
复制标题
DOI：
10.1109/tit.2012.2209627
复制
发表时间：
2011-10
影响因子：
2.5
通讯作者：
A. György;T. Linder;G. Lugosi
中科院分区：
文献类型：
--
作者：
A. György;T. Linder;G. Lugosi
在预测单个序列的框架中，要构建顺序预测方法，其表现几乎与给定类别的最佳专家一样好。我们认为预测策略，竞争的切换策略，可以将一个给定的序列分割成几个块的类，并遵循不同的“基地”专家在每个块的意见。通常，该算法的性能是通过后悔来衡量的，后悔定义为相对于事后为要预测的特定序列选择的最佳切换策略的超额损耗。在本文中，我们构造的预测策略的低计算成本的情况下，基专家集是大的。特别地，我们提供了一种方法，该方法可以将为基类设计的任何预测算法A转换为跟踪算法。所得到的跟踪算法可以利用A的预测性能和潜在的计算效率，在某种意义上，它可以以仅为A的时间和空间复杂度的O（n γ lnn）倍来实现，其中n是时间范围，γ ≥ 0是算法的参数。通过适当地选择A，我们的算法实现了γ>; 0的最优阶的遗憾界，并且对于我们检查的所有典型遗憾界类型，仅比γ = 0的最优阶大O（lnn）倍。例如，对于对数损失下的带开关参数的二元序列预测，对于任意的γ ∈（0，1），我们的方法获得了时间复杂度为O（n1 + γ lnn）的O（lnn）的最优后悔率.
In the framework of prediction of individual sequences, sequential prediction methods are to be constructed that perform nearly as well as the best expert from a given class. We consider prediction strategies that compete with the class of switching strategies that can segment a given sequence into several blocks, and follow the advice of a different “base” expert in each block. As usual, the performance of the algorithm is measured by the regret defined as the excess loss relative to the best switching strategy selected in hindsight for the particular sequence to be predicted. In this paper, we construct prediction strategies of low computational cost for the case where the set of base experts is large. In particular, we provide a method that can transform any prediction algorithm A that is designed for the base class into a tracking algorithm. The resulting tracking algorithm can take advantage of the prediction performance and potential computational efficiency of A in the sense that it can be implemented with time and space complexity only O(nγ lnn) times larger than that of A, where n is the time horizon and γ ≥ 0 is a parameter of the algorithm. With A properly chosen, our algorithm achieves a regret bound of optimal order for γ >; 0, and only O(lnn) times larger than the optimal order for γ = 0 for all typical regret bound types we examined. For example, for predicting binary sequences with switching parameters under the logarithmic loss, our method achieves the optimal O(lnn) regret rate with time complexity O(n1+γlnn) for any γ ∈ (0,1).