...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >Individual Sequence Prediction Using Memory-Efficient Context Trees
【24h】

Individual Sequence Prediction Using Memory-Efficient Context Trees

机译：使用内存高效上下文树的单个序列预测

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Context trees are a popular and effective tool for tasks such as compression, sequential prediction, and language modeling. We present an algebraic perspective of context trees for the task of individual sequence prediction. Our approach stems from a generalization of the notion of margin used for linear predictors. By exporting the concept of margin to context trees, we are able to cast the individual sequence prediction problem as the task of finding a linear separator in a Hilbert space, and to apply techniques from machine learning and online optimization to this problem. Our main contribution is a memory efficient adaptation of the perceptron algorithm for individual sequence prediction. We name our algorithm the shallow perceptron and prove a shifting mistake bound, which relates its performance with the performance of any sequence of context trees. We also prove that the shallow perceptron grows a context tree at a rate that is upper bounded by its mistake rate, which imposes an upper bound on the size of the trees grown by our algorithm.
机译：上下文树是用于压缩，顺序预测和语言建模等任务的流行且有效的工具。我们提出了上下文树的代数观点，用于单个序列预测的任务。我们的方法源于用于线性预测变量的余量概念的概括。通过将边界的概念导出到上下文树，我们能够将单个序列预测问题强制转换为在希尔伯特空间中找到线性分隔符的任务，并将从机器学习和在线优化中获得的技术应用到该问题。我们的主要贡献是针对单个序列预测的感知器算法的内存高效适配。我们将算法命名为浅层感知器，并证明了一个转移错误的界限，这将其性能与上下文树序列的性能相关联。我们还证明，浅层感知器以其错误率上限来限制上下文树的生长速度，这给我们算法所生长的树的大小施加了上限。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号