论文标题
通过两个依赖历史的专家的建议来预测二进制序列的PDE方法
A PDE Approach to the Prediction of a Binary Sequence with Advice from Two History-Dependent Experts
论文作者
论文摘要
二进制序列的预测是在线机器学习的经典示例。我们喜欢将其称为“股票预测问题”，将序列视为在每个时间步骤中向上或下降一个单位的股票的价格历史记录。在这个问题中，投资者可以访问两个或更多“专家”的预测，并努力将她对表现最佳专家的最终后悔最小化。概率不起作用；相反，假定市场是对抗性的。我们考虑有两个依赖历史的专家的情况，他们的预测是由D最近的股票移动决定的。为了关注适当的连续限制，并使用最佳控制，图形理论和部分微分方程的方法，我们讨论了投资者和对抗性市场的策略，我们确定了投资者最终遗憾的相关上限和下限。当d小于4时，我们的上限和下限结合结合，因此提出的策略在渐近上是最佳的。与预测的部分微分方程的其他最新应用相比，我们的元素有一个新元素：有两个次数，因为最近的历史在每个步骤都发生了变化，而遗憾的积累较慢。
The prediction of a binary sequence is a classic example of online machine learning. We like to call it the 'stock prediction problem,' viewing the sequence as the price history of a stock that goes up or down one unit at each time step. In this problem, an investor has access to the predictions of two or more 'experts,' and strives to minimize her final-time regret with respect to the best-performing expert. Probability plays no role; rather, the market is assumed to be adversarial. We consider the case when there are two history-dependent experts, whose predictions are determined by the d most recent stock moves. Focusing on an appropriate continuum limit and using methods from optimal control, graph theory, and partial differential equations, we discuss strategies for the investor and the adversarial market, and we determine associated upper and lower bounds for the investor's final-time regret. When d is less than 4 our upper and lower bounds coalesce, so the proposed strategies are asymptotically optimal. Compared to other recent applications of partial differential equations to prediction, ours has a new element: there are two timescales, since the recent history changes at every step whereas regret accumulates more slowly.
