Prediction with a short memory
Prediction with a short memory
复制标题
DOI：
10.1145/3188745.3188954
复制
发表时间：
2016-12
期刊：
影响因子：
--
通讯作者：
S. Kakade;Percy Liang;Vatsal Sharan;G. Valiant
中科院分区：
文献类型：
--
作者：
S. Kakade;Percy Liang;Vatsal Sharan;G. Valiant
我们考虑的问题，预测下一个观察给定的一系列过去的观察，并考虑在何种程度上准确的预测需要复杂的算法，明确利用长期的依赖关系。也许令人惊讶的是，我们的积极结果表明，对于一个广泛的序列类，有一个算法，预测平均良好，并根据其预测只有最近的几个观察与一组简单的汇总统计过去的观察。具体来说，我们表明，对于任何分布的观察，如果过去的观察和未来的观察之间的互信息是上界的I，然后一个简单的马尔可夫模型在最近的I/I观测获得预期的KL误差ε-因此，ε 1误差ε ε-相对于最佳预测，可以访问整个过去，并知道数据生成的分布。对于具有n个隐状态的隐马尔可夫模型，I由logn有界，logn是一个不依赖于混合时间的量，并且我们证明了基于观测窗口长度为O（logn/n）的经验频率的平凡预测算法可以实现这种误差，假设序列的长度为dΩ（logn/n），其中d是观测字母表的大小。我们还确定，这个结果不能得到改善，即使是类的HALO，在以下两个意义上：第一，对于HALO与n隐藏状态，一个窗口长度为logn/n是信息理论上必要的，以实现预期的KL错误的，或错误的101错误的。第二，当从大小为d的字母表中提取观测值时，精确估计马尔可夫模型所需的dΘ（logn/logn）样本对于任何计算上易于处理的学习/预测算法都是必要的，假设强烈反驳某类CSP的难度。
We consider the problem of predicting the next observation given a sequence of past observations, and consider the extent to which accurate prediction requires complex algorithms that explicitly leverage long-range dependencies. Perhaps surprisingly, our positive results show that for a broad class of sequences, there is an algorithm that predicts well on average, and bases its predictions only on the most recent few observation together with a set of simple summary statistics of the past observations. Specifically, we show that for any distribution over observations, if the mutual information between past observations and future observations is upper bounded by I, then a simple Markov model over the most recent I/є observations obtains expected KL error є—and hence ℓ1 error √є—with respect to the optimal predictor that has access to the entire past and knows the data generating distribution. For a Hidden Markov Model with n hidden states, I is bounded by logn, a quantity that does not depend on the mixing time, and we show that the trivial prediction algorithm based on the empirical frequencies of length O(logn/є) windows of observations achieves this error, provided the length of the sequence is dΩ(logn/є), where d is the size of the observation alphabet. We also establish that this result cannot be improved upon, even for the class of HMMs, in the following two senses: First, for HMMs with n hidden states, a window length of logn/є is information-theoretically necessary to achieve expected KL error є, or ℓ1 error √є. Second, the dΘ(logn/є) samples required to accurately estimate the Markov model when observations are drawn from an alphabet of size d is necessary for any computationally tractable learning/prediction algorithm, assuming the hardness of strongly refuting a certain class of CSPs.