Information-theoretic capacity notions for a slotted Aloha random-access system are considered in this paper, as well as joint power and retransmission controls for this protocol. The effect of the bursty nature of the arrival and transmission process on the information-carrying capability and spectral efficiency of the system is studied. The nature of the random-access protocol used to resolve decoding failures determines the system stability and dynamics, and in consequence its capacity. System control is carried out by dynamic control of retransmission probability and by power control. It is shown that substantial performance improvements can be achieved under this control scheme in terms of throughput and spectral efficiency for a range of channel parameters. The tradeoffs involving coding rate, system throughput, and spectral efficiency are analyzed from an information-theoretic point of view.

We consider in this study dynamic control policies for slotted Aloha random access systems. New performance bounds are derived when random access is combined with power control for system optimization, and we establish the existence of optimal control approaches for such systems. We analyze throughput and delay when the number of backlogged users is known, where we can explicitly obtain optimal policies and analyze their corresponding performance using Markov Decision Process (MDP) theory with average cost criterion. For the realistic unknown-backlog case, we establish the existence of optimal backlog-minimizing policies for the same range of arrival rates as the ideal known-backlog case by using the theory of MDPs with Borel state space and unbounded costs. We also propose suboptimal control policies with performance close to the optimal without sacrificing stability. These policies perform substantially better than existing "Certainty Equivalence" controllers.

We propose a nonparametric independent component analysis (ICA) algorithm for the case of instantaneous and linear mixtures. Our algorithm combines minimization of correlation among nonlinear expansions of the output signals with good initialization derived from a search guided by statistical tests for independence. Simulation results obtained from both synthetic and real-life data show that our method provides consistent results and compares favorably to existing ICA algorithms.

We revisit the oft-studied asymptotic (in sample size) behavior of the parameter or weight estimate returned by any member of a large family of neural network training algorithms. By properly accounting for the characteristic property of neural networks that their empirical and generalization errors possess multiple minima, we rigorously establish conditions under which the parameter estimate converges strongly into the set of minima of the generalization error. Convergence of the parameter estimate to a particular value cannot be guaranteed under our assumptions. We then evaluate the asymptotic distribution of the distance between the parameter estimate and its nearest neighbor among the set of minima of the generalization error. Results on this question have appeared numerous times and generally assert asymptotic normality, the conclusion expected from familiar statistical arguments concerned with maximum likelihood estimators. These conclusions are usually reached on the basis of somewhat informal calculations, although we shall see that the situation is somewhat delicate. The preceding results then provide a derivation of learning curves for generalization and empirical errors that leads to bounds on rates of convergence.

We introduce a statistically based methodology for the design of neural networks when the dimension d of the network input is comparable to the size n of the training set. If one proceeds straightforwardly, then one is committed to a network of complexity exceeding n. The result will be good performance on the training set but poor generalization performance when the network is presented with new data. To avoid this we need to select carefully the network architecture, including control over the input variables. Our approach to selecting a network architecture first selects a subset of input variables (features) using the nonparametric statistical process of difference-based variance estimation and then selects a simple network architecture using projection pursuit regression (PPR) ideas combined with the statistical idea of slicing inverse regression (SIR). The resulting network, which is then retrained without regard to the PPR/SIR determined parameters, is one of moderate complexity (number of parameters significantly less than n) whose performance on the training set can be expected to generalize well. The application of this methodology is illustrated in detail in the context of short-term forecasting of the demand for electric power from an electric utility.

We study the asymptotic properties of the sequence of iterates of weight-vector estimates obtained by training a feedforward neural network with a basic gradient-descent method using a fixed learning rate and no batch-processing. Earlier results based on stochastic approximation techniques (Kuan and Hornik 1991; Finnoff 1993; Bucklew et al. 1993) have established the existence of a gaussian limiting distribution for the weights, but they apply only in the limiting case of a zero learning rate. We here prove, from an exact analysis of the one-dimensional case and constant learning rate, weak convergence to a distribution that is not gaussian in general. We also run simulations to compare and contrast the results of our analysis with those of stochastic approximation.

We study the asymptotic properties of the sequence of iterates of weight-vector estimates obtained by training a multilayer feed for(cid:173) ward neural network with a basic gradient-descent method using a fixed learning constant and no batch-processing. In the one(cid:173) dimensional case, an exact analysis establishes the existence of a limiting distribution that is not Gaussian in general. For the gen(cid:173) eral case and small learning constant, a linearization approximation permits the application of results from the theory of random ma(cid:173) trices to again establish the existence of a limiting distribution. We study the first few moments of this distribution to compare and contrast the results of our analysis with those of techniques of stochastic approximation.

We estimate the number of training samples required to ensure that the performance of a neural network on its training data matches that obtained when fresh data is applied to the network. Existing estimates are higher by orders of magnitude than practice indicates. This work seeks to narrow the gap between theory and practice by transforming the problem into determining the distribution of the supremum of a random field in the space of weight vectors, which in turn is attacked by application of a recent technique called the Poisson clumping heuristic. 1 INTRODUCTION AND KNOWN RESULTS We investigate the tradeofi"s among network complexity, training set size, and sta(cid:173) tistical performance of feedforward neural networks so as to allow a reasoned choice of network architecture in the face of limited training data. Nets are functions 7](x; w), parameterized by their weight vector w E W ~ Rd , which take as input points x E Rk. For classifiers, network output is restricted to {a, 1} while for fore(cid:173) casting it may be any real number. The architecture of all nets under consideration is N, whose complexity may be gauged by its Vapnik-Chervonenkis (VC) dimension v, the size of the largest set of inputs the architecture can classify in any desired way ('shatter'). Nets 7] EN are chosen on the basis of a training set T = {(Xi, YiHr=l. These n samples are i.i.d. according to an unknown probability law P. Performance of a network is measured by the mean-squared error

The decoding of efficiently encoded messages, from either probabilistic, nonprobabilistic, or unknown message sources, is shown to be often practically impossible. If\tau(S)is a running-time bound on the computational effort of a decoder\Psiaccepting a codewordPfor messageS, and\gamma[K_{\Psi}(S)]is an upper bound to acceptable codeword length\mid P \midwhen the shortest codeword forShas lengthK_{\Psi}(S), then for many message sources\mathcal{M}there exist messagesS \in \mathcal{M}such that: 1) if the encoder satisfies\gamma, then the decoder violates\tau; 2) if the decoder satisfies\tau, then the encoder violates\gamma. These conclusions remain valid even when we allow the decoder to reconstruct only an approximationS \primein a neighborhood\delta(S)ofS. The compatibility of these results with those of information theory rests upon the fact that we are inquiring into the detailed properties of coding systems for individual messages and not into the ensemble average properties.

An explanation is provided for the prevalence of apparently convergent relative frequencies in random sequences. The explanation is based upon the computational-complexity characterization of a random sequence. Apparent convergence is shown to be attributable to a surprising consequence of the selectivity with which relative frequency arguments are applied; it is a consequence of data handling rather than an underlying law or good fortune. The consequences of this understanding for probability and its applications are indicated.

A discrete time, nonlinear system composed of an integrator preceded by a binary quantizer with integrated negative feedback, which can model a tracking loop or a single integrating delta modulation communication system, is discussed with regard to the input-output statistics for two types of input processes: independent inputs and independent increments inputs. A recursion on time for the joint distribution of input and output is obtained for the independent inputs process and explicitly solved for the time asymptotic distribution, when it exists. The solution is examined in greater detail for the special case of IID normal inputs. When the system is excited by a process of independent increments, the asymptotic behavior of the input and output (they diverge) is of less interest than that of the difference between input and output, the tracking error. A recursion in time for the characteristic function of the error is developed and the time asymptotic solution found, The tracking error is interpreted by decomposition into static and dynamic parts, and an exponential bound to its distribution is provided. The particular case of normal increments input is discussed in additional detail.

This paper exhibits an optimum strategy for the sequential estimation of, or search for, the location of the maximumMof a unimodal function, whenMis initially uniformly distributed over some interval. The explicit search strategy which is found is valid for a variety of expected cost functions that add the expected cost of observation to the expected cost of terminal decision. The search problem possesses some of the features of problems in the areas of sequential analysis and stochastic approximation. The search stopping time can be determined as the search proceeds as in problems of sequential analysis. However, unlike many sequential analysis problems, the observational outcomes are somewhat within our control by a choice of observation or trial points. In common with problems of stochastic approximation, we attempt to determine the maximum of an unknown regression function. Contrary to many problems in stochastic approximation, though, the observations are noiseless, and the regression function is not required to be smooth or regular in the neighborhood ofM. The main result is that the strategy minimizing the expected cost, drawn from the class of randomized, optional stopping strategies, is nonrandomized and of a size that can be fixed in advance of observation.

A model representative of any time-sampled, real-valued input and output digital system without feedback from system input to output (there may be internal feedback loops) is presented, and properties that are necessary for an optimum (nonlinear) digital system are developed. The model itself consists of a cascade of three mapping operations that successively transform the real-valued input sequence into an M-ary valued digital sequence, thence into anN-ary valued digital sequence, and finally into a real-valued output sequence. The operating routine and optimality criterion function chosen permit us to consider the problems of prediction, interpolation or synchronous operation as well as a wide variety of loss functions. The derived properties are discussed with particular regard to the quadratic loss function and synchronous or interpolatory operation and then applied to the determination of several optimum systems. Optimum nonlinear amplitude quantizers, pulse code and delta modulation systems, and stepped controllers are described. In particular, conditions are given under which delta modulation is superior to pulse code modulation and some remarks are made concerning suboptimal delta modulation systems and their relation to previous work.