Edinburgh Research Explorer

Very Predictive Ngrams for Space-Limited Probabilistic Models

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://dx.doi.org/10.1007/978-3-540-45231-7_13
Original languageEnglish
Title of host publicationAdvances in Intelligent Data Analysis V
Subtitle of host publication5th International Symposium on Intelligent Data Analysis, IDA 2003, Berlin, Germany, August 28-30, 2003. Proceedings
EditorsMichael R. Berthold, Hans-Joachim Lenz, Elizabeth Bradley, Rudolf Kruse, Christian Borgelt
PublisherSpringer-Verlag GmbH
Pages134-142
Number of pages9
ISBN (Electronic)978-3-540-45231-7
ISBN (Print)978-3-540-40813-0
DOIs
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume2810
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Abstract

In sequential prediction tasks, one repeatedly tries to predict the next element in a sequence. A classical way to solve these problems is to fit an order-n Markov model to the data, but fixed-order models are often bigger than they need to be. In a fixed-order model, all predictors are of length n, even if a shorter predictor would work just as well. We present a greedy algorithm, VPR, for finding variable-length predictive rules. Although VPR is not optimal, we show that on English text, it performs similarly to fixed-order models but uses fewer parameters.

Download statistics

No data available

ID: 14900520