Let stock market vectors form a stationary ergodic sequence. For fixed d /spl isin/ N, a log-optimal portfolio selection function of the past d observed vectors is iteratively estimated on the basis of a training sequence by use of gradients and nonparametric regression. Strong consistency is obtained under a boundedness and /spl alpha/-mixing condition without further assumptions on the distribution.

Summary form only given. The multilevel pattern matching data compression system is one of a class of compression algorithms introduced by Kieffer and Yang (see ERA Amer. Math. Soc., vol.3, p.11-16, 1997). The MPM system is currently of interest because of its good redundancy performance in losslessly compressing data strings of arbitrary length over a finite alphabet. An MPM system consists of a preprocessor, encoder/decoder, and a reconstruction engine. The preprocessor detects matching patterns in the input data string (substrings of the data appearing in two or more nonoverlapping positions). The preprocessor operates at several levels sequentially, with the number of levels selected by the user. The matching patterns detected at each level are of a fixed length which decreases by a constant factor from level to level, until this fixed length becomes one at the final level. The preprocessor represents information about matching patterns at each level as a string of tokens which is passed to the encoder of the MPM system. The decoder of the MPM system recovers these token strings, from which the reconstruction engine rebuilds the input data string. The preprocessor is the most complex component of the MPM system. We exhibit an implementation of the preprocessor of linear complexity in terms of execution time and space requirements; the number of levels satisfies O(log/sub 2/log/sub 2/n) for input data strings of length n.

In a given binary image, we identify two disjoint sets of image subblocks of varying size which we call range blocks and domain blocks. The range blocks form a partition of the image called a self-referential partition because each range block is represented via a pointer to a matching domain block. The encoder transmits encoded versions of these pointers together with one pixel from each domain block. This information, when decoded, allows progressive reconstruction of the image. On several archival images, our progressive lossless image coder gave better compression performance than that provided by the 2-D Lempel-Ziv (1986) algorithm, multi-window quadtree coding, and Huffman coding of runlengths. The progressive image coder is fast and has a worst-case redundancy performance better than the best currently known worst-case redundancy upper bound for the 2-D Lempel-Ziv algorithm.

This article concerns problems of time-series forecasting under the weakest of assumptions. Related results are surveyed and are points of departure for the developments here, some of which are new and others are new derivations of previous findings. The contributions in this study are all negative, showing that various plausible prediction problems are unsolvable, or in other cases, are not solvable by predictors which are known to be consistent when mixing conditions hold.

The conditional distribution of the next outcome given the infinite past of a stationary process can be inferred from finite but growing segments of the past. Several schemes are known for constructing pointwise consistent estimates, but they all demand prohibitive amounts of input data. We consider real-valued time series and construct conditional distribution estimates that make much more efficient use of the input data. The estimates are consistent in a weak sense, and the question whether they are pointwise-consistent is still open. For finite-alphabet processes one may rely on a universal data compression scheme like the Lempel-Ziv (1978) algorithm to construct conditional probability mass function estimates that are consistent in expected information divergence. Consistency in this strong sense cannot be attained in a universal sense for all stationary processes with values in an infinite alphabet, but weak consistency can. Some applications of the estimates to on-line forecasting, regression, and classification are discussed.

Assume a completion time T0 and a graph having edges with randomly chosen weights are specified. Each time an edge is traversed, the weight is selected at random, according to a fixed probability law indexed by that edge. Successive observations are independent, and independent of realizations at other edges. We consider the stochastic shortest path and traveling salesman problems of finding paths which maximize the probability of completion by the specified time. The methodology combines techniques of machine learning with the “k-opt” heuristic. The algorithm is supported by convergence analysis, and is also shown in computational experiments to be successful for randomized versions of TSP problems already in the literature and having from 10 to 57 vertices. To our knowledge, this success is well beyond other computational stochastic traveling salesman studies reported elsewhere. A feature of the algorithm is that the distributions of the random edge weights need not be specified, and so the technique is suited to on-line operation.

Previous works by the authors have advanced a novel frequency location technique based on recursive filtering concepts. The complexity is proportional to the signal length, which motivates the term, "fast." Asymptotic theory reported elsewhere does not give the full picture. The main objective is to discuss practical computational considerations, and through simulation, compare the performance of our algorithm with alternatives. The gist of our findings is that for low signal-to-noise power ratios, our method is supreme among the available fast detectors. There is a theoretical reason to anticipate this. We have extended earlier explorations by devising an enhancement which simultaneously narrows the bandwidth while the location recursion proceeds. The effect is to vastly amplify the signal-to-noise ratio as the detector homes in on the target frequency. A practical procedure is offered which, experimentally, appears to be an effective guide in determining whether the detector output is meaningful or spurious (because the signal is too weak, or is nonexistent).>

A fast technique for efficient online signal detection and tracking is extended by analyzing the asymptotic distribution of the detector. A version of the technique is seen to have potentially greater precision than other fast estimators, the upper bound being O(1/n/sup 2/3/). Coupled with another device, there is potential for achieving the convergence precision of the maximum likelihood estimate, which, by conventional methods, entails considerably computational expense.>

The author derives a useful information-theoretical technology from the tunable filter that automatically detects the frequency of an unknown signal in white Gaussian noise by adjusting its parameter to the correlation coefficient of its output. The tunable filter earlier proposed by S. He and B. Kedem (see ibid., vol.35, no.2, p.360-9, 1989) is known as the HK filter. The methodology sidesteps the white noise and normality assumptions. More importantly, it is shown that broad classes of linear filters can be made to implement the detection plan. In particular, bandpass filters can be expected to lock-in even more quickly and accurately than the HK filter. This analysis yields a formula for the error contraction at each recursion.>

An approximation to the existing optimal algorithm for simultaneously tracking several moving targets is proposed which greatly reduces the required memory and number of calculations, but nevertheless retains reasonable accuracy (as is shown by analytic consideration and by Monte Carlo simulations) when the number of states is much greater than the number of targets. It is shown where errors arise in the approximation and how the errors tend to stabilize as the process evolves. Computational results on a highly idealized biological population surveillance problem are given that tend to confirm assertions concerning the relative computational efficiency and accuracy of the suboptimal rule in comparison to the optimal solution. A more realistic radar simulation study (20 targets and 10 000 states) is reported that suggests the scope of application of thc methodology proposed here.

The first portion of this paper is tutorial. Beginning with a standard definition of an abstract pattern-recognition machine, "learning" is given a mathematical meaning and the distinction is made between supervised and unsupervised learning. The bibliography will help the interested reader retrace the history of learning in pattern recognition. The exposition now focuses attention on unsupervised learning. Carefully, it is explained how problems in this subject can be viewed as problems in the identification of finite mixtures, a statistical theory that has achieved some maturity. From this vantage point, it is demonstrated that identification theory implies unsupervised learning is possible in many important cases. The remaining sections present a general method for achieving unsupervised learning. Other authors have proposed schemes having greater computational convenience, but no method previously published is as inclusive as the one revealed here, which we demonstrate to be effective for all the many cases wherein unsupervised learning is known to be possible.