Very Predictive Ngrams for Space-Limited Probabilistic Models

Paul R. Cohen; Charles A. Sutton

doi:10.1007/978-3-540-45231-7_13

Very Predictive Ngrams for Space-Limited Probabilistic Models

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	Advances in Intelligent Data Analysis V
Subtitle of host publication	5th International Symposium on Intelligent Data Analysis, IDA 2003, Berlin, Germany, August 28-30, 2003. Proceedings
Editors	Michael R. Berthold, Hans-Joachim Lenz, Elizabeth Bradley, Rudolf Kruse, Christian Borgelt
Publisher	Springer
Pages	134-142
Number of pages	9
ISBN (Electronic)	978-3-540-45231-7
ISBN (Print)	978-3-540-40813-0
DOIs	https://doi.org/10.1007/978-3-540-45231-7_13
Publication status	Published - 2003

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	2810
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-540-45231-7_13

vprAccepted author manuscript, 236 KB

http://dx.doi.org/10.1007/978-3-540-45231-7_13

Cite this

Cohen, P. R., & Sutton, C. A. (2003). Very Predictive Ngrams for Space-Limited Probabilistic Models. In M. R. Berthold, H.-J. Lenz, E. Bradley, R. Kruse, & C. Borgelt (Eds.), Advances in Intelligent Data Analysis V: 5th International Symposium on Intelligent Data Analysis, IDA 2003, Berlin, Germany, August 28-30, 2003. Proceedings (pp. 134-142). (Lecture Notes in Computer Science; Vol. 2810). Springer. https://doi.org/10.1007/978-3-540-45231-7_13

Cohen, Paul R. ; Sutton, Charles A. / Very Predictive Ngrams for Space-Limited Probabilistic Models. Advances in Intelligent Data Analysis V: 5th International Symposium on Intelligent Data Analysis, IDA 2003, Berlin, Germany, August 28-30, 2003. Proceedings. editor / Michael R. Berthold ; Hans-Joachim Lenz ; Elizabeth Bradley ; Rudolf Kruse ; Christian Borgelt. Springer, 2003. pp. 134-142 (Lecture Notes in Computer Science).

@inproceedings{95fbcc619d20482e84d1520fe8636d50,

title = "Very Predictive Ngrams for Space-Limited Probabilistic Models",

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.",

author = "Cohen, {Paul R.} and Sutton, {Charles A.}",

year = "2003",

doi = "10.1007/978-3-540-45231-7_13",

language = "English",

isbn = "978-3-540-40813-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "134--142",

editor = "{R. Berthold}, Michael and Hans-Joachim Lenz and Elizabeth Bradley and Rudolf Kruse and Christian Borgelt",

booktitle = "Advances in Intelligent Data Analysis V",

address = "United Kingdom",

}

Cohen, PR & Sutton, CA 2003, Very Predictive Ngrams for Space-Limited Probabilistic Models. in M R. Berthold, H-J Lenz, E Bradley, R Kruse & C Borgelt (eds), Advances in Intelligent Data Analysis V: 5th International Symposium on Intelligent Data Analysis, IDA 2003, Berlin, Germany, August 28-30, 2003. Proceedings. Lecture Notes in Computer Science, vol. 2810, Springer, pp. 134-142. https://doi.org/10.1007/978-3-540-45231-7_13

Very Predictive Ngrams for Space-Limited Probabilistic Models. / Cohen, Paul R.; Sutton, Charles A.
Advances in Intelligent Data Analysis V: 5th International Symposium on Intelligent Data Analysis, IDA 2003, Berlin, Germany, August 28-30, 2003. Proceedings. ed. / Michael R. Berthold; Hans-Joachim Lenz; Elizabeth Bradley; Rudolf Kruse; Christian Borgelt. Springer, 2003. p. 134-142 (Lecture Notes in Computer Science; Vol. 2810).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Very Predictive Ngrams for Space-Limited Probabilistic Models

AU - Cohen, Paul R.

AU - Sutton, Charles A.

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-45231-7_13

DO - 10.1007/978-3-540-45231-7_13

M3 - Conference contribution

SN - 978-3-540-40813-0

T3 - Lecture Notes in Computer Science

SP - 134

EP - 142

BT - Advances in Intelligent Data Analysis V

A2 - R. Berthold, Michael

A2 - Lenz, Hans-Joachim

A2 - Bradley, Elizabeth

A2 - Kruse, Rudolf

A2 - Borgelt, Christian

PB - Springer

ER -

Cohen PR, Sutton CA. Very Predictive Ngrams for Space-Limited Probabilistic Models. In R. Berthold M, Lenz HJ, Bradley E, Kruse R, Borgelt C, editors, Advances in Intelligent Data Analysis V: 5th International Symposium on Intelligent Data Analysis, IDA 2003, Berlin, Germany, August 28-30, 2003. Proceedings. Springer. 2003. p. 134-142. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-45231-7_13

Very Predictive Ngrams for Space-Limited Probabilistic Models

Abstract

Publication series

Access to Document

Fingerprint

Cite this