The Lempel Ziv complexity of a string has recently been used in pattern recognition and classification as part of a string distance function. Its main advantage is that it can measure dissimilarity between a pair of strings of different lengths. This is very useful for machine learning on unstructured data since such data is not restricted to a fixed input dimensionality. The standard computation of LZ-complexity is inherently serial and is not suitable for processing large unstructured data. Hence, we propose a parallel algorithm that computes the LZ-complexity of strings whose length is limited only by the amount of memory, typically in the tens of gigabytes. The algorithm is implemented in CUDA on a GPU. Its speed-up factor is approximately n2/3for strings of length n, for at least up to n = 2Mb. For instance, on 2Mb strings, the speed-up is 150. We compare the execution times of kernel variants with shared and global memory. The more efficient variant obtains approximately 90% GPU utilization.

Given a finite random sample from a Markov chain environment, we select a predictor that minimizes a criterion function and refer to it as being calibrated to its environment. If its prediction error is not bounded by its criterion value, we say that the criterion fails. We define the predictor’s complexity to be the amount of uncertainty in detecting that the criterion fails given that it fails. We define a predictor’s stability to be the discrepancy between the average number of prediction errors that it makes on two random samples. We show that complexity is inversely proportional to the level of adaptivity of the calibrated predictor to its random environment. The calibrated predictor becomes less stable as its complexity increases or as its level of adaptivity decreases.

Let {Xt: t ∈ ℤ} be a sequence of binary random variables generated by a stationary Markov source of order k*. Let β be the probability of the event “Xt= 1”. Consider a learner based on a Markov model of order k, where k may be different from k*, who trains on a sample sequence X(m)which is randomly drawn by the source. Test the learner's performance by asking it to predict the bits of a test sequence X(n)(generated by the source). An error occurs at time t if the prediction Ytdiffers from the true bit value Xt, 1 ≤ t ≤ n. Denote by Ξ(n)the sequence of errors where the error bit Ξtat time t equals 1 or 0 according to whether an error occurred or not, respectively. Consider the subsequence Ξ(ν)of Ξ(n)which corresponds to the errors made when predicting a 0, that is, Ξ(ν)consists of those bits Ξtat times t where Yt= 0: In this paper we compute an upper bound on the absolute deviation between the frequency of 1 in Ξ(ν)and β. The bound has an explicit dependence on k, k*, m, ν, n. It shows that the larger k, or the larger the difference k - k*, the less random that Ξ(ν)can become.

We call a learning environment partially blind when there is an admixture of supervised and unsupervised (or blind) learning. Such situations typically arise in practice when supervised training data labelled by a teacher are scarce or expensive and are supplemented by inexpensive unlabelled (or blind) data available in relative profusion. Vapnik-Cervonenkis theory can be deployed in such settings to quantify the relative worth of supervision (and the lack thereof) in learning. We illustrate the nature of the trade-offs possible in a simple setting of hyperplane decision functions and make explicit the role of dimensionality and side-information in these trade-offs in the context of d-variate Gaussian mixtures.

The classical theory of pattern recognition assumes labeled examples appear according to unknown underlying class conditional probability distributions where the pattern classes are picked randomly in a passive manner according to their a priori probabilities. This paper presents experimental results for an incremental nearest-neighbor learning algorithm which actively selects samples from different pattern classes according to a querying rule as opposed to the a priori probabilities. The amount of improvement of this query-based approach over the passive batch approach depends on the complexity of the Bayes rule.

this paper we extend on previous work [17] and introduce a novel model selection criterion, based on combining two recent chains of thought. In particular we make use of the powerful framework of uniform convergence of empirical processes pioneered by Vapnik and Chernovenkins [23], combined with recent results concerning the approximation ability of non-linear manifolds of functions, focusing in particular on feedforward neural networks. The main contributions of this work are twofold: (i) Conceptual - elucidating a coherent and robust framework for model selection, (ii) Technical - the main contribution here is a lower bound on the approximation error (Theorem 10), which holds in a well specified sense for most functions of interest. As far as we are aware, this result is new in the field of function approximation. The remainder of the paper is organized as follows. In

Article Free Access Share on Learning from a mixture of labeled and unlabeled examples with parametric side information Authors: Joel Ratsaby Department of Electrical Engineering, Technion, Israel and Department of Electrical Engineering, University of Pennsylvania, Philadelphia, PA Department of Electrical Engineering, Technion, Israel and Department of Electrical Engineering, University of Pennsylvania, Philadelphia, PAView Profile , Santosh S. Venkatesh Department of Electrical Engineering, University of Pennsylvania, Philadelphia, PA Department of Electrical Engineering, University of Pennsylvania, Philadelphia, PAView Profile Authors Info & Claims COLT '95: Proceedings of the eighth annual conference on Computational learning theoryJuly 1995 Pages 412–417https://doi.org/10.1145/225298.225348Online:05 July 1995Publication History 41citation532DownloadsMetricsTotal Citations41Total Downloads532Last 12 Months29Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF