In this paper, we use a linear program to empirically decompose fitted neural networks into ensembles of low-bias sub-networks. We show that these sub-networks are relatively uncorrelated which leads to an internal regularization process, very much like a random forest, which can explain why a neural network is surprisingly resistant to overfitting. We then demonstrate this in practice by applying large neural networks, with hundreds of parameters per training observation, to a collection of 116 real-world data sets from the UCI Machine Learning Repository. This collection of data sets contains a much smaller number of training examples than the types of image classification tasks generally studied in the deep learning literature, as well as non-trivial label noise. We show that even in this setting deep neural nets are capable of achieving superior classification accuracy without overfitting.

There is a large literature explaining why AdaBoost is a successful classifier. The literature on AdaBoost focuses on classifier margins and boosting's interpretation as the optimization of an exponential likelihood function. These existing explanations, however, have been pointed out to be incomplete. A random forest is another popular ensemble method for which there is substantially less explanation in the literature. We introduce a novel perspective on AdaBoost and random forests that proposes that the two algorithms work for similar reasons. While both classifiers achieve similar predictive accuracy, random forests cannot be conceived as a direct optimization procedure. Rather, random forests is a self- averaging, interpolating algorithm which creates what we denote as a spiked-smooth classifier, and we view AdaBoost in the same light. We conjecture that both AdaBoost and random forests succeed because of this mechanism. We provide a number of examples to support this explanation. In the process, we question the conventional wisdom that suggests that boosting algorithms for classification require regularization or early stopping and should be limited to low complexity classes of learners, such as decision stumps. We conclude that boosting should be used like random forests: with large decision trees, without regularization or early stopping.

The log-optimal or Kelly portfolio forms the basis of a theoretically appealing investment strategy. However, it is difficult to compute, and this hinders its adoption in practice. In this paper we consider an approximate Kelly portfolio based on maximizing the expected value of a quadratic approximation to log utility. We show that this semi-log approximation gives an information-theoretic justification for portfolio selection based on either the mean-variance efficient frontier or the Sharpe ratio. We further show that there is a strong connection between estimated approximate fractional Kelly portfolios and shrinkage estimators, which leads to an optimal choice of a fractional Kelly parameter. We conclude by showing that the fractional Kelly portfolio succeeds not because of reduced risk, but because of reduced estimation error. We simulate to show that this property is largely responsible for the good empirical performance of fractional Kelly strategies.

Cover's universal portfolio has deep connections to universal data compression. In this paper, we provide a statistical view of universal portfolios in order to develop a clearer understanding of their performance on actual financial data sequences. By recasting the analysis of a universal portfolio in statistical terms - with a special emphasis on means and covariances - we are able to resolve a long standing and false perception of a disconnect between information theory and empirical finance. We first show that the universal portfolio can be characterized as a conditional expectation of a multivariate normal random variable. We then show that this implies that the universal portfolio algorithm is asymptotically approximately equal to a constrained sequential Markowitz mean-variance portfolio optimization based on estimates of the mean of a multivariate normal distribution. In light of this equivalence, we propose alternative estimation methods and conclude with some practical investment advice

We offer two noiseless codes for blocks of integers X/sup n/ = (X/sub 1/, ..., X/sub n/). We provide explicit bounds on the relative redundancy that are valid for any distribution F in the class of memoryless sources with a possibly infinite alphabet whose marginal distribution is monotone. Specifically, we show that the expected code length L (X/sup n/) of our first universal code is dominated by a linear function of the entropy of X/sup n/. Further, we present a second universal code that is efficient in that its length is bounded by nH/sub F/ + o(nH/sub F/), where H/sub F/ is the entropy of F which is allowed to vary with n. Since these bounds hold for any n and any monotone F we are able to show that our codes are strongly minimax with respect to relative redundancy (as defined by Elias (1975)). Our proofs make use of the elegant inequality due to Aaron Wyner (1972).

We discuss a family of estimators for the entropy rate of a stationary ergodic process and prove their pointwise and mean consistency under a Doeblin-type mixing condition. The estimators are Cesaro averages of longest match-lengths, and their consistency follows from a generalized ergodic theorem due to Maker (1940). We provide examples of their performance on English text, and we generalize our results to countable alphabet processes and to random fields.

In this paper, the role of pattern matching in information theory is motivated and discussed. We describe the relationship between a pattern's recurrence time and its probability under the data-generating stochastic source. We show how this relationship has led to great advances in universal data compression. We then describe nonasymptotic uniform bounds on the performance of data-compression algorithms in cases where the size of the training data that is available to the encoder is not large enough so as to yield the asymptotic compression: the Shannon entropy. We then discuss applications of pattern matching and universal compression to universal prediction, classification, and entropy estimation.

The fixed-database version of the Lempel-Ziv algorithm closely resembles many versions that appear in practice. We ascertain several key asymptotic properties of the algorithm as applied to sources with finite memory. First, we determine that for a dictionary of size n, the algorithm achieves a redundancy /spl rho//sub n/=Hlog log n/log n+0(log log n/log n) where H is the entropy of the process. This is the first, nontrivial, lower bound on any Lempel-Ziv-type compression scheme. We then find the limiting distribution and all moments of the lengths of the phrases by comparing them to a random-walk-like variable with well-known behavior.

The Lempel-Ziv data compression algorithm has the property that for finite-memory sources the redundancy /spl rho//sub n/ (defined as the difference between the average code rate and the entropy when the memory size is n) is O (log log n/log n). We suggest a new version of the algorithm with redundancy /spl rho//sub n/=O (1/log n).>