We describe a computationally efficient method to produce a specific Bayesian mixture of all the models in a finite set of feature-based models that assign a probability to the observed data set. Special attention is given to the bound on the regret of using the mixture instead of the best model in the set. It is proven theoretically and verified through synthetic data that this bound is relatively tight. Comparing the workload of the proposed method with the direct implementation of the Bayesian mixture shows an almost exponential improvement of computing time.

Two low-complexity methods are proposed for sequential probability assignment for binary independent and identically distributed (i.i.d.) individual sequences with empirical distributions whose governing parameters are known to be bounded within a limited interval. The methods can be applied to different problems where fast accurate estimation of the maximizing sequence probability is very essential to minimizing some loss. Such applications include applications in finance, learning, channel estimation and decoding, prediction, and universal compression. The application of the new methods to universal compression is studied, and their universal coding redundancies are analyzed. One of the methods is shown to achieve the minimax redundancy within the inner region of the limited parameter interval. The other method achieves better performance on the region boundaries and is more robust numerically to outliers. Simulation results support the analysis of both methods. While non-asymptotically the gains may be significant over standard methods that maximize the probability over the complete parameter simplex, asymptotic gains are in second order. However, these gains translate to meaningful significant factor gains in other applications, such as financial ones. Moreover, the methods proposed generate estimators that are constrained within a given interval throughout the complete estimation process which are essential to applications such as sequential binary channel crossover estimation. The results for the binary case lay the foundation to studying larger alphabets.

An efficient implementation of a Huffman code can be based on the Shannon-Fano construction. An important question is exactly how complex is such an implementation. In the past authors have considered this question assuming an ordered source symbol alphabet. In the case of the compression of blocks of binary symbols this ordering must be performed explicitly and it turns out to be the complexity bottleneck.

Summary form only given. We consider the coding of a binary IID source using variable-to-fixed length (VF) source codes. The goal is to design "good" codes of low complexity. A VF code maps variable length source sequences (segments) into fixed length code sequences (codewords). We conclude that Petry codes are an efficient implementation of Tunstall codes and moreover that by approximating the enumeration an even better trade-off between redundancy and complexity is achieved.

Context weighting procedures are presented for sources with models (structures) in four different classes. Although the procedures are designed for universal data compression purposes, their generality allows application in the area of classification.

Describes a sequential universal data compression procedure for binary tree sources that performs the "double mixture." Using a context tree, this method weights in an efficient recursive way the coding distributions corresponding to all bounded memory tree sources, and achieves a desirable coding distribution for tree sources with an unknown model and unknown parameters. Computational and storage complexity of the proposed procedure are both linear in the source sequence length. The authors derive a natural upper bound on the cumulative redundancy of the method for individual sequences. The three terms in this bound can be identified as coding, parameter, and model redundancy, The bound holds for all source sequence lengths, not only for asymptotically large lengths. The analysis that leads to this bound is based on standard techniques and turns out to be extremely simple. The upper bound on the redundancy shows that the proposed context-tree weighting procedure is optimal in the sense that it achieves the Rissanen (1984) lower bound.>

Presents a detailed result on Franaszek's (1968) principal state method for the generation of run-length constrained codes. The authors show that, whenever the constraints k and d satisfy k/spl ges/2d>0, the set of "principal states" is s/sub 0/, s/sub 1/, /spl middot//spl middot//spl middot/, s/sub k-1/. Thus there is no need for Franaszek's search algorithm anymore. The counting technique used to obtain this result also shows that "state independent decoding" can be achieved using not more than three codewords per message. Previously, it was not known beforehand that one could use fewer codewords per message than there were principal states. The counting technique also allows one to compare the principal state method with other practical schemes originating from the work of Tang and Bahl (1970) and allows one to use an efficient enumerative coding implementation of the encoder and decoder.>

It is shown that the modified Lawrence algorithm is universal over the class of binary memoryless sources and that the rate converges asymptotically optimally fast to the source entropy. It is proven that no codes exist that have a better asymptotic performance. The asymptotic bounds show that universal variable-to-fixed-length codes can have a significantly lower redundancy than universal fixed-to-variable-length codes with the same number of codewords.>

Petry's efficient and optimal variable to fixed-length source code for discrete memoryless sources was described by Schalkwijk. By extending this coding technique we are able to give an algorithm for Markov sources that is easy to implement. We can bound the loss of efficiency as a function of the code complexity and the mismatch between the source and the code. Rates arbitrarily close to the source entropy are shown to be achievable. In this sense the codes introduced are optimal.