An efficient extension to mixture techniques for prediction and decision trees
Published 1 January 1997Open access
Fernando Pereira, Yoram Singer
Citations8
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
We present a method for maintaining mixtures of prunings of a prediction or decision tree that extends the "node-based" prunings of (BunSO, WST95, HS95] to the larger class of edge-based prunings.
Keywords
Computer Science
C4.5: Programs for Machine Learning
23,665 Citations1992J. R. Quinlan
A complete guide to the C4.5 system as implemented in C for the UNIX environment, which starts from simple core learning methods and shows how they can be elaborated and extended to deal with typical problems such as missing data and over hitting.
Journal of Computer and System SciencesA Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
20,320 Citations1997Yoav Freund, Robert E. Schapire
BiometrikaTHE POPULATION FREQUENCIES OF SPECIES AND THE ESTIMATION OF POPULATION PARAMETERS
3,227 Citations1953I. J. Good
Information and ComputationThe Weighted Majority Algorithm
2,022 Citations1994N. Littlestone, Manfred K. Warmuth
Journal of the American Statistical AssociationStatistical Methods for Speech Recognition
1,988 Citations1999Don X. Sun, Frederick Jelinek
The speech recognition problem hidden Markov models the acoustic model basic language modelling the Viterbi search hypothesis search on a tree and the fast match elements of information theory.
IEEE Transactions on Acoustics Speech and Signal ProcessingEstimation of probabilities from sparse data for the language model component of a speech recognizer
1,645 Citations1987Slava M. Katz
The model offers, via a nonlinear recursive procedure, a computation and space efficient solution to the problem of estimating probabilities from sparse data, and compares favorably to other proposed methods.
IEEE Transactions on Information TheoryThe context-tree weighting method: basic properties
934 Citations1995F.M.J. Willems, Yuri M. Shtarkov +1 more
The authors derive a natural upper bound on the cumulative redundancy of the method for individual sequences that shows that the proposed context-tree weighting procedure is optimal in the sense that it achieves the Rissanen (1984) lower bound.
IEEE Transactions on Information TheoryThe zero-frequency problem: estimating the probabilities of novel events in adaptive text compression
726 Citations1991Ian H. Witten, Tim Bell
The authors propose the application of a Poisson process model of novelty, which ability to predict novel tokens is evaluated, and it consistently outperforms existing methods and offers a small improvement in the coding efficiency of text compression over the best method previously known.
Journal of the ACMHow to use expert advice
647 Citations1997Nicolò Cesa‐Bianchi, Yoav Freund +4 more
This work analyzes algorithms that predict a binary value by combining the predictions of several prediction strategies, called experts, and shows how this leads to certain kinds of pattern recognition/learning algorithms with performance bounds that improve on the best results currently know in this context.
IEEE Transactions on Information TheoryUniversal modeling and coding
463 Citations1981J. Rissanen, Glen G. Langdon
A general class of so-called first-in first-out (FIFO) arithmetic codes is described which require no alphabet extension devices and which therefore can be used in conjunction with the best models.
Machine LearningThe power of amnesia: Learning probabilistic automata with variable memory length
454 Citations1997Dana Ron, Yoram Singer +1 more
It is proved that the algorithm presented can efficiently learn distributions generated by PSAs, and it is shown that for any target PSA, the KL-divergence between the distributiongenerated by the target and the distribution generated by the hypothesis the learning algorithm outputs, can be made small with high confidence in polynomial time and sample complexity.
IEEE Transactions on Information TheoryA universal finite memory source
228 Citations1995M.J. Weinberger, J. Rissanen +1 more
It is shown that this universal source incorporates any minimal data-generating tree machine in an asymptotically optimal manner in the following sense: the negative logarithm of the probability it assigns to any long typical sequence, generated by any tree machine, approaches that assigned by the tree machine at the best possible rate.
IEEE Transactions on Information TheoryComplexity of strings in the class of Markov sources
194 Citations1986J. Rissanen
Shannon's self-information of a string is generalized to its complexity relative to the class of finite-state-machine (FSM) defined sources by a theorem stating that, asymptotically, the mean complexity provides a tight lower bound for the mean length of all so-called regular codes.
How to use expert advice
132 Citations1993Nicolò Cesa‐Bianchi, Yoav Freund +4 more
This work analyzes algorithms that predict a binary value by combining the predictions of several prediction strategies, called `experts', and shows how this leads to certain kinds of pattern recognition/learning algorithms with performance bounds that improve on the best results currently known in this context.
Predicting nearly as well as the best pruning of a decision tree
131 Citations1995David P. Helmbold, Robert E. Schapire
IEEE Transactions on Information TheoryOptimal sequential probability assignment for individual sequences
97 Citations1994M.J. Weinberger, Neri Merhav +1 more
IEEE Transactions on Information TheoryUpper bounds on the probability of sequences emitted by finite-state sources and on the redundancy of the Lempel-Ziv algorithm
97 Citations1992E. Plotnik, M.J. Weinberger +1 more
An upper bound on the probability of a sequence drawn from a finite-state source is derived in terms of the number of phrases obtained by parsing the sequence according to the Lempel-Ziv (L-Z) incremental parsing rule, and is universal in the sense that it does not depend on the statistical parameters that characterize the source.
Learning probabilistic prediction functions
94 Citations1988Alfredo De Santis, George Markowsky +1 more
The question of how to learn rules, when those rules make probabilistic statements about the future, is considered and two results related to these distinct goals are given.
IEEE Transactions on Information TheoryA sequential algorithm for the universal coding of finite memory sources
85 Citations1992M.J. Weinberger, A. Lempe +1 more
The estimation and universal compression of discrete sources are considered, and a sequential algorithm for the universal coding of finite memory sources, attaining asymptotically minimum redundancy, is presented.
Neural ComputationAdaptive Mixtures of Probabilistic Transducers
24 Citations1997Yoram Singer
An online learning algorithm that efficiently infers the structure and estimates the parameters of each probabilistic transducer in the mixture is devised and an application of the model for inducing a noun phrase recognizer is presented.
arXiv (Cornell University)Beyond Word N-Grams
11 Citations1996Fernando C. N. Pereira, Yoram Singer +1 more