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

Paul R. Cohen, Charles A. Sutton

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

1 Scopus citations

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 (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Michael R. Berthold, Hans-Joachim Lenz, Elizabeth Bradley, Rudolf Kruse, Christian Borgelt
Publisher	Springer-Verlag
Pages	134-142
Number of pages	9
ISBN (Print)	3540408134, 9783540408130
DOIs	https://doi.org/10.1007/978-3-540-45231-7_13
State	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2810
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 134-142). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2810). Springer-Verlag. 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.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Michael R. Berthold; Hans-Joachim Lenz; Elizabeth Bradley; Rudolf Kruse; Christian Borgelt. Springer-Verlag, 2003. p. 134-142 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2810).

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

Cohen, PR & Sutton, CA 2003, Very predictive ngrams for space-limited probabilistic models. in MR Berthold, H-J Lenz, E Bradley, R Kruse & C Borgelt (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2810, Springer-Verlag, pp. 134-142. https://doi.org/10.1007/978-3-540-45231-7_13

Cohen PR, Sutton CA. Very predictive ngrams for space-limited probabilistic models. In Berthold MR, Lenz HJ, Bradley E, Kruse R, Borgelt C, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer-Verlag. 2003. p. 134-142. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-45231-7_13

Cohen, Paul R. ; Sutton, Charles A. / Very predictive ngrams for space-limited probabilistic models. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Michael R. Berthold ; Hans-Joachim Lenz ; Elizabeth Bradley ; Rudolf Kruse ; Christian Borgelt. Springer-Verlag, 2003. pp. 134-142 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{3a30c0255beb4045a90476879a80ebff,

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 (US)",

isbn = "3540408134",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "134--142",

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

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - CHAP

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.

UR - http://www.scopus.com/inward/record.url?scp=35248815655&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35248815655&partnerID=8YFLogxK

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

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

M3 - Chapter

AN - SCOPUS:35248815655

SN - 3540408134

SN - 9783540408130

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 134

EP - 142

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Berthold, Michael R.

A2 - Lenz, Hans-Joachim

A2 - Bradley, Elizabeth

A2 - Kruse, Rudolf

A2 - Borgelt, Christian

PB - Springer-Verlag

ER -

Very predictive ngrams for space-limited probabilistic models

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this