We study the problem of nonparametric classification with repeated observations. Let${\mathbf {X}}$be the$d$dimensional feature vector and let$Y$denote the label taking values in$\lbrace 1,\ldots, M\rbrace$. In contrast to usual setup with large sample size$n$and relatively low dimension$d$, this letter deals with the situation, when instead of observing a single feature vector${\mathbf {X}}$we are given$t$repeated feature vectors${\mathbf {V}}_{1},\ldots, {\mathbf {V}}_{t}$. Some simple classification rules are presented such that the conditional error probabilities have exponential rate of convergence as$t\to \infty$.

We study the problem of estimating the density$f({\mathbf {x}})$of a random vector${ {\mathbf {X}}}$in${\mathbb R}^{d}$. For a spanning tree$T$defined on the vertex set$\{1, {\dots },d\}$, the tree density$f_{T}$is a product of bivariate conditional densities. An optimal spanning tree minimizes the Kullback-Leibler divergence between$f$and$f_{T}$. From i.i.d. data we identify an optimal tree$T^{*}$and efficiently construct a tree density estimate$f_{n}$such that, without any regularity conditions on the density$f$, one has$\lim _{n\to \infty } \int | f_{n}({\mathbf {x}})-f_{T^{*}}({\mathbf {x}})|d {\mathbf {x}}=0$a.s. For Lipschitz$f$with bounded support,${\mathbb E}\left \{{ \int | f_{n}({\mathbf {x}})-f_{T^{*}}({\mathbf {x}})|d {\mathbf {x}}}\right \}=O\big (n^{-1/4}\big)$, a dimension-free rate.

We revisit the problem of the estimation of the differential entropy$H(f)$of a random vector$X$in$R^{d}$with density$f$, assuming that$H(f)$exists and is finite. In this note, we study the consistency of the popular nearest neighbor estimate$H_{n}$of Kozachenko and Leonenko. Without any smoothness condition we show that the estimate is consistent ($E\{|H_{n} - H(f)|\} \to 0$as$n \to \infty $) if and only if${\mathbb E}\{ \log (\| X \| + 1)\} < \infty $. Furthermore, if$X$has compact support, then$H_{n} \to H(f)$almost surely.

We study universal consistency and convergence rates of simple nearest-neighbor prototype rules for the problem of multiclass classification in metric spaces. We first show that a novel data-dependent partitioning rule, named Proto-NN, is universally consistent in any metric space that admits a universally consistent rule. Proto-NN is a significant simplification of OptiNet, a recently proposed compression-based algorithm that, to date, was the only algorithm known to be universally consistent in such a general setting. Practically, Proto-NN is simpler to implement and enjoys reduced computational complexity. We then proceed to study convergence rates of the excess error probability. We first obtain rates for the standard $k$-NN rule under a margin condition and a new generalized-Lipschitz condition. The latter is an extension of a recently proposed modified-Lipschitz condition from $\mathbb R^d$ to metric spaces. Similarly to the modified-Lipschitz condition, the new condition avoids any boundness assumptions on the data distribution. While obtaining rates for Proto-NN is left open, we show that a second prototype rule that hybridizes between $k$-NN and Proto-NN achieves the same rates as $k$-NN while enjoying similar computational advantages as Proto-NN. However, as $k$-NN, this hybrid rule is not consistent in general.

A composite hypothesis testing procedure, originally introduced in [5], is examined for robustness in the binary case. A density-free uniform exponential bound for the error probability is derived which tightens the bound of [5], it is shown that this procedure is equivalent to a hard-limited likelihood-ratio test, and asymptotic and nonasymptotic robustness is discussed.

Discrete time growth optimal investment in stock markets with proportional transactions costs is considered. The market process is modeled by a first-order Markov process. Not assuming that the distribution of the market process is known, we show empirical investment strategies such that, in the long run, the growth rate on trajectories achieves the maximum with probability 1.

The authors discuss quantization or clustering of nonparametric regression estimates. The main tools developed are oracle inequalities for the rate of convergence of constrained least squares estimates. These inequalities yield fast rates for both nonparametric (unconstrained) least squares regression and clustering of partition regression estimates and plug-in empirical quantizers. The bounds on the rate of convergence generalize known results for bounded errors to subGaussian, too.

A simple on-line procedure is considered for the prediction of a binary-valued sequence in the setup introduced and studied by Weissman and Merhav [2001], [2004], where only side information is available for the algorithm. The (non-randomized) algorithm is based on a convex combination of several simple predictors. If the side information is also binary-valued (i.e. original sequence is corrupted by a binary sequence) and both processes are realizations of stationary and ergodic random processes then the average of the loss converges, almost surely, to that of the optimum, given by the Bayes predictor. An analog result is offered for the classification of binary processes.

Estimation of conditional distributions is considered. It is assumed that the conditional distribution is either discrete or that it has a density with respect to the Lebesgue measure. Partitioning estimates of the conditional distribution are constructed and results concerning consistency and rate of convergence of the integrated total variation error of the estimates are presented.

We consider the rate of convergence of the expected distortion redundancy of empirically optimal vector quantizers. Earlier results show that the mean-squared distortion of an empirically optimal quantizer designed from n independent and identically distributed (i.i.d.) source samples converges uniformly to the optimum at a rate of O(1//spl radic/n), and that this rate is sharp in the minimax sense. We prove that for any fixed distribution supported on a given finite set the convergence rate is O(1/n) (faster than the minimax lower bound), where the corresponding constant depends on the source distribution. For more general source distributions we provide conditions implying a little bit worse O(logn/n) rate of convergence. Although these conditions, in general, are hard to verify, we show that sources with continuous densities satisfying certain regularity properties (similar to the ones of Pollard that were used to prove a central limit theorem for the code points of the empirically optimal quantizers) are included in the scope of this result. In particular, scalar distributions with strictly log-concave densities with bounded support (such as the truncated Gaussian distribution) satisfy these conditions.

We present two simple and explicit procedures for testing homogeneity of two independent multivariate samples of size n. The nonparametric tests are based on the statistic T/sub n/, which is the L/sub 1/ distance between the two empirical distributions restricted to a finite partition. Both tests reject the null hypothesis of homogeneity if T/sub n/ becomes large, i.e., if T/sub n/ exceeds a threshold. We first discuss Chernoff-type large deviation properties of T/sub n/. This results in a distribution-free strong consistent test of homogeneity. Then the asymptotic null distribution of the test statistic is obtained, leading to an asymptotically /spl alpha/-level test procedure.

We consider the rate of convergence of the expected distortion redundancy of empirically optimal vector quantizers. Earlier results show that the mean-squared distortion of an empirically optimal quantizer designed from n independent and identically distributed source samples converges uniformly to the optimum at a rate O(1/radicn), and that this rate is sharp in the minimax sense. We prove that for any fixed source distribution supported on a given finite set, the convergence rate is O(1/n) (faster than the minimax lower bound), where the corresponding constant depends on the distribution. For more general source distributions, we provide conditions implying a little bit worse O(log n/n) rate of convergence. In particular, scalar distributions having strictly log-concave densities with bounded support (such as the truncated Gaussian distribution) satisfy these conditions

We deal with the coding problem of the multiple-access adder channel, considering both the identification of the active users and decoding of their messages. We examine the bounds on the minimal length of codes solving these tasks. We examine codes solving both tasks simultaneously, and we give asymptotic upper and lower bounds on the length of the shortest possible code. Our new bounds are quite similar to the bounds known for the identification task only. The difference between the upper and lower bounds is a factor of two.

We introduce a simple new hypothesis testing procedure, which, based on an independent sample drawn from a certain density, detects which of k nominal densities is the true density closest to, under the total variation (L/sub 1/) distance. We obtain a density-free uniform exponential bound for the probability of false detection.

This paper presents relative stability properties of various nonparametric density estimators (histogram, kernel estimates) and of regression estimators (partitioning, kernel, and nearest neighbor estimates). In density estimation, let En denote the L/sub 1/ error of an estimate calculated from n data, whereas in regression estimation, the L/sub 2/ error of the estimate is used. Sufficient conditions for E/sub n//E{E/sub n/}/spl rarr/1 in probability are provided. If this limit holds, the asymptotic behavior of the random error E/sub n/ can be characterized by its expectation E{E/sub n/},, and one may apply, for example, the established rate-of-convergence results for E{En}.

This paper discusses some metrics of TCP based on real measurements over the Internet. We present algorithms to measure the congestion window related metrics and use these metrics to study the stationary behavior of TCP. Our statistical analysis shows that the distribution of the congestion window process in a stable period has a bell-like shape and can be approximated by a normal distribution.

We give a short proof of the following result. Let (X,Y) be any distribution on N/spl times/{0,1}, and let (X/sub 1/,Y/sub 1/),...,(X/sub n/,Y/sub n/) be an i.i.d. sample drawn from this distribution. In discrimination, the Bayes error L*=inf/sub g/P{g(X)/spl ne/Y} is of crucial importance. Here we show that without further conditions on the distribution of (X,Y), no rate-of-convergence results can be obtained. Let /spl phi//sub n/(X/sub 1/,Y/sub 1/,...,X/sub n/,Y/sub n/) be an estimate of the Bayes error, and let {/spl phi//sub n/(.)} be a sequence of such estimates. For any sequence {a/sub n/} of positive numbers converging to zero, a distribution of (X,Y) may be found such that E{|L*-/spl phi//sub n/(X/sub 1/,Y/sub 1/,...,X/sub n/,Y/sub n/)|}/spl ges/a/sub n/ often converges infinitely.

We present a simple randomized procedure for the prediction of a binary sequence. The algorithm uses ideas from previous developments of the theory of the prediction of individual sequences. We show that if the sequence is a realization of a stationary and ergodic random process then the average number of mistakes converges, almost surely, to that of the optimum, given by the Bayes predictor. The desirable finite-sample properties of the predictor are illustrated by its performance for Markov processes. In such cases the predictor exhibits near-optimal behavior even without knowing the order of the Markov process. Prediction with side information is also considered.

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.

Shows that a discrete infinite distribution with finite entropy cannot be estimated consistently in information divergence. As a corollary the authors show that there is no universal source code for an infinite source alphabet over the class of all discrete memoryless sources with finite entropy.>

Constructions of protocol sequences for multiple-access collision channel without feedback are given. These constructions are the extensions of those described by A, Gyorfi, and Massey (see ibid., vol.38, p. 940, May 1992). If the basic code in their constructions, a Reed-Solomon code, is replaced by a BCH code then the resulting protocol sequences have the feature that, for a given sum rate, the ratio of the total user population to the block length becomes much larger.>

A general theorem is proved showing how to obtain a constant-weight binary cyclic code from a p-ary linear cyclic code, where p is a prime, by using a representation of GF(p) as cyclic shifts of a binary p-tuple. Based on this theorem, constructions are given for four classes of binary constant-weight codes. The first two classes are shown to achieve the Johnson upper bound on minimum distance asymptotically for long block lengths. The other two classes are shown similarly to meet asymptotically the low-rate Plotkin upper bound on minimum distance. A simple method is given for selecting virtually the maximum number of cyclically distinct codewords with full cyclic order from Reed-Solomon codes and from Berlekamp-Justesen maximum-distance-separable codes. Two correspondingly optimum classes of constant-weight cyclically permutable codes are constructed. It is shown that cyclically permutable codes provide a natural solution to the problem of constructing protocol-sequence sets for the M-active-out-of-T-users collision channel without feedback.>

The problem of the nonparametric estimation of a probability distribution is considered from three viewpoints: the consistency in total variation, the consistency in information divergence, and consistency in reversed-order information divergence. These types of consistencies are relatively strong criteria of convergence, and a probability distribution cannot be consistently estimated in either type of convergence without any restrictions on the class of probability distributions allowed. Histogram-based estimators of distribution are presented which, under certain conditions, converge in total variation, in information divergence, and in reversed-order information divergence to the unknown probability distribution. Some a priori information about the true probability distribution is assumed in each case. As the concept of consistency in information divergence is stronger than that of convergence in total variation, additional assumptions are imposed in the cases of informational divergences.>

The L/sub 1/ and L/sub 2/ strong consistency of recursive kernel density estimators is established for mixing and ergodic stationary processes. Sharp rates of almost sure convergence are obtained in the L/sub 2/ case for mixing processes. In addition, the concept and properties of Hilbert space-valued mixingales are developed, and strong laws of large numbers are given.>

The authors introduce the concept of superimposed codes in Euclidean n-space R/sup n/. An asymptotic existence bound is derived for such codes; the proof uses the idea of random coding. In particular, the asymptotic properties of long codes are studied. It is shown that the derived existence bound differs only by a factor of four from a nonexistence bound obtained by a simple sphere-packing argument.>

Under mild conditions on the observation processes the almost sure convergence properties of linear stochastic approximation are summarized for least squares and for some of its applications: adaptive filtering, echo cancellation, detection of binary data in Gaussian noise, identification, and linear classification.

The performance of a simple memory-repeat-request (MRQ) algorithm for simple ALOHA channels is investigated. The unique feature of the algorithm is that the receiver constructs a correct packet by using the stored undamaged parts of the packets received. Analytical and computer simulation results are presented.

The rate of Convergence ofk_{n}-NN regression estimates and the corresponding multiple classification error are calculated without assuming the existence of the density of the observations.

A Mock code for the noiseless multiple access OR channel is introduced. An exponential error bound is proven if the sum of the equal code rates of the asynchronousTusers is less than\ln 2.

An erroneous method for maximizing the projected divergence between two Gaussian multivariate hypotheses appeared in a recent paper. The correct solution is given.

IfR_{k}, denotes the asymptotic error probability of thek- nearest neighbor rule forMclasses andR\astdenotes the Bayes probability of error, then conditions are given that yieldR_{k} - R\ast \leq \sqrt{MR{1}/k}.

Analogously to the rate distortion function, the error distortion function is defined for a multiple-hypothesis decision problem. The error distortion functione(d)is defined as the supremum of the Bayes' error probability for transformed observations for which the average distortion is less thand (d \geq O)The main result is that the functione(d)is continuous at O.

In many actual learning problems, a sequence of decision functions is generated, and one has to estimate the limit of the error probabilities associated with these decision functions. This correspondence proposes a simple algorithm for the finite hypothesis testing problem. The procedure works in parallel with the iterative estimation of the decision function and utilizes in this way the same labeled samples for training and testing. A mild condition on the behavior of the probability of error of the sequence of decision rules is shown to imply strong convergence of a sequence of estimates of the probability of error.