14885154
On-line learning of functions of bounded variation under various sampling schemes
We consider the problem of learning of an arbitrary function selected from the non-smooth class of functions that are of bounded variation. Bounds on the prediction errors resulting from sequential type algorithms are achieved for various scenarios. It is shown that for any algorithm there exists a sequence of samples and a function that results in a unit error at each step. If the samples are i.i.d. uniform then there exists an algorithm such that for any function of bounded variation the expected error is less than O(log n/n). Furthermore, for any algorithm there exists a function such that the expected error is greater than 0(1/n). We then introduce a mixed sampling setting in which an adversary can choose points but the actual samples are drawn uniformly from a 6 neighborhood of his selection. We show that there exists an algorithm such that for any function of bounded variation and for any sequence of adversarychosen points the expected cumulative error is less than 0(+ log n). Finally, results are derived for the uniform sampling case with noisy observations. We show that the order of growth of the expected error with noise sequences in Z1 remains unaltered. However, for i.i.d. zero mean and finite variance noise there exists an algorithm with expected error less than 0(1/n*), and for i.i.d. Gaussian noise any algorithm has expected error of at least o(l/@). Permission to copy without fee all or part of this material is granted provided that the copies ars not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying IS by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. ACM COLT ’93 171931CA, USA @ 1993 Acfvf 0.89791-61 ~-5/93 /o(307/0439... $1 .50
1752947
Learning decision rules for pattern classification under a family of probability measures
In this paper, uniformly consistent estimation (learnability) of decision rules for pattern classification under a family of probability measures is investigated. In particular, it is shown that uniform boundedness of the metric entropy of the class of decision rules is both necessary and sufficient for learnability under each of two conditions: (i) the family of probability measures is totally bounded, with respect to the total variation metric, and (ii) the family of probability measures contains an interior point, when equipped with the same metric. In particular, this shows that insofar as uniform consistency is concerned, when the family of distributions contains a total variation neighborhood, nothing is gained by this knowledge about the distribution. Then two sufficient conditions for learnability are presented. Specifically, it is shown that learnability with respect to each of a finite collection of families of probability measures implies learnability with respect to their union; also, learnability with respect to each of a finite number of measures implies learnability with respect to the convex hull of the corresponding families of uniformly absolutely continuous probability measures.
7846439
Universal lossless source coding with the Burrows Wheeler Transform
The Burrows Wheeler transform (1994) is a reversible sequence transformation used in a variety of practical lossless source-coding algorithms. In each, the BWT is followed by a lossless source code that attempts to exploit the natural ordering of the BWT coefficients. BWT-based compression schemes are widely touted as low-complexity algorithms giving lossless coding rates better than those of the Ziv-Lempel codes (commonly known as LZ'77 and LZ'78) and almost as good as those achieved by prediction by partial matching (PPM) algorithms. To date, the coding performance claims have been made primarily on the basis of experimental results. This work gives a theoretical evaluation of BWT-based coding. The main results of this theoretical evaluation include: (1) statistical characterizations of the BWT output on both finite strings and sequences of length n /spl rarr/ /spl infin/, (2) a variety of very simple new techniques for BWT-based lossless source coding, and (3) proofs of the universality and bounds on the rates of convergence of both new and existing BWT-based codes for finite-memory and stationary ergodic sources. The end result is a theoretical justification and validation of the experimentally derived conclusions: BWT-based lossless source codes achieve universal lossless coding performance that converges to the optimal coding performance more quickly than the rate of convergence observed in Ziv-Lempel style codes and, for some BWT-based codes, within a constant factor of the optimal rate of convergence for finite-memory sources.
9782780
A paradigm for class identification problems
The following problem arises in many applications involving classification, identification, and inference. There is a set of objects X, and a particular x /spl isin/ X is chosen (unknown to us). Based on information obtained about x in a sequential manner, one wishes to decide whether x belongs to one class of objects A/sub 0/ or a different class of objects A/sub 1/. The authors study a general paradigm applicable to a broad range of problems of this type, which they refer to as problems of class identification or discernibility. They consider various types of information sequences, and various success criteria including discernibility in the limit, discernibility with a stopping criterion, uniform discernibility, and discernibility in the Cesaro sense. They consider decision rules both with and without memory. Necessary and sufficient conditions for discernibility are provided for each case in terms of separability conditions on the sets A/sub 0/ and A/sub 1/. They then show that for any sets A/sub 0/ and A/sub 1/, various types of separability can be achieved by allowing failure on appropriate sets of small measure. Applications to problems in language identification, system identification, and discrete geometry are discussed. >
6063474
PAC learning with generalized samples and an application to stochastic geometry
In this paper, we introduce an extension of the standard PAC learning model which allows the use of generalized samples. We view a generalized sample as a pair consisting of a functional on the concept class together with the value obtained by the functional operating on the unknown concept. It appears that this model can be applied to a number of problems in signal processing and geometric reconstruction to provide sample size bounds under a PAC criterion. We consider a specific application of the model to a problem of curve reconstruction, and discuss some connections with a result from stochastic geometry.
7606261
Rates of convergence of nearest neighbor estimation under arbitrary sampling
Rates of convergence for nearest neighbor estimation are established in a general framework in terms of metric covering numbers of the underlying space. The first result is to find explicit finite sample upper bounds for the classical independent and identically distributed (i.i.d.) random sampling problem in a separable metric space setting. The convergence rate is a function of the covering numbers of the support of the distribution. For example, for bounded subsets of R/sup r/, the convergence rate is O(1/n/sup 2/r/). The main result is to extend the problem to allow samples drawn from a completely arbitrary random process in a separable metric space and to examine the performance in terms of the individual sample sequences. The authors show that for every sequence of samples the asymptotic time-average of nearest neighbor risks equals twice the time-average of the conditional Bayes risks of the sequence. Finite sample upper bounds under arbitrary sampling are again obtained in terms of the covering numbers of the underlying space. In particular, for bounded subsets of R/sup r/ the convergence rate of the time-averaged risk is O(1/n/sup 2/r/). The authors then establish a consistency result for k/sub n/-nearest neighbor estimation under arbitrary sampling and prove a convergence rate matching established rates for i.i.d. sampling. Finally, they show how their arbitrary sampling results lead to some classical i.i.d. sampling results and in fact extend them to stationary sampling. The framework and results are quite general while the proof techniques are surprisingly elementary. >
12287966
Complexity issues in automated synthesis of failsafe fault-tolerance
We focus on the problem of synthesizing failsafe fault-tolerance where fault-tolerance is added to an existing (fault-intolerant) program. A failsafe fault-tolerant program satisfies its specification (including safety and liveness) in the absence of faults. However, in the presence of faults, it satisfies its safety specification. We present a somewhat unexpected result that, in general, the problem of synthesizing failsafe fault-tolerant distributed programs from their fault-intolerant version is NP-complete in the state space of the program. We also identify a class of specifications, monotonic specifications, and a class of programs, monotonic programs, for which the synthesis of failsafe fault-tolerance can be done in polynomial time (in program state space). As an illustration, we show that the monotonicity restrictions are met for commonly encountered problems, such as Byzantine agreement, distributed consensus, and atomic commitment. Furthermore, we evaluate the role of these restrictions in the complexity of synthesizing failsafe fault-tolerance. Specifically, we prove that if only one of these conditions is satisfied, the synthesis of failsafe fault-tolerance is still NP-complete. Finally, we demonstrate the application of monotonicity property in enhancing the fault-tolerance of (distributed) nonmasking fault-tolerant programs to masking.
8320156
Resettable vector clocks
Vector clocks (VC) are an inherent component of a rich class of distributed applications. In this paper, we consider the problem of realistic —more specifically, bounded-space and fault-tolerant— implementation of these client applications. To this end, we generalize the notion of VC to resettable vector clocks (RVC), and provide a realistic implementation of RVC. Further, we identify an interface contract under which our RVC implementation can be substituted for VC in client applications, without affecting the client's correctness. Based on such substitution, we show how to transform the client so that it is itself realistically implemented; we demonstrate our method in the context of Ricart-Agrawala's mutual exclusion program.
5887329
Graybox stabilization
Research in system stabilization has traditionally relied on the availability of a complete system implementation. As such, it would appear that the scalability and reusability of stabilization is limited in practice. Towards redressing this perception, the authors show for the first time that system stabilization may be designed knowing only the system specification but not the system implementation. We refer to stabilization designed thus as being "graybox" and identify "local everywhere-eventually specifications" as being amenable to design of graybox stabilization. We illustrate the design of graybox stabilization using timestamp-based distributed mutual exclusion as our example.
1711572
Designing masking fault-tolerance via nonmasking fault-tolerance
Masking fault-tolerance guarantees that programs continually satisfy their specification in the presence of faults. By way of contrast, nonmasking fault-tolerance does not guarantee as much: it merely guarantees that when faults stop occurring, program executions converge to states from where programs continually (re)satisfy their specification. In this paper, we show that a practical method to design masking fault-tolerance is to first design nonmasking fault-tolerance and to then transform the nonmasking fault-tolerant program minimally so as to achieve masking fault-tolerance. We demonstrate this method by designing novel fully distributed programs for termination detection, mutual exclusion, and leader election, that are masking tolerant of any finite number of process fail-stops and/or repairs.
52887342
Low-cost fault-tolerance in barrier synchronizations
We show how fault-tolerance can be effectively added to several types of faults in program computations that use barrier synchronization. We divide the faults that occur in practice into two classes, detectable and undetectable, and design a fully distributed program that tolerates the faults in both classes. Our program guarantees that every barrier is executed correctly even if detectable faults occur, and that eventually every barrier is executed correctly even if undetectable faults occur. Via analytical as well as simulation results we show that the cost of adding fault-tolerance is low, in part by comparing the times required by our program with that required by the corresponding fault-intolerant counterpart.