A new constructive approach for creating all linearly separable functions is introduced. Balanced and unate functions on N+1 variables are created and then projected to N variables permitting to create straightforward all the linearly separable functions without needing to check for linearly separability. The method is supported by the demonstration of a theorem and numerical simulation results for small number of variables. If the results extrapolates the method may permit to test the linear separability of any function on N variables by checking monotonicity and unaleness in N+1 dimension. Furthermore, the generalization complexity of the linear threshold functions is analyzed.

In this paper, we analyze Boolean functions using a recently proposed measure of their complexity. This complexity measure, motivated by the aim of relating the complexity of the functions with the generalization ability that can be obtained when the functions are implemented in feed-forward neural networks, is the sum of a number of components. We concentrate on the case in which we use the first two of these components. The first is related to the "average sensitivity" of the function and the second is, in a sense, a measure of the "randomness" or lack of structure of the function. In this paper, we investigate the importance of using the second term in the complexity measure, and we consider to what extent these two terms suffice as an indicator of how difficult it is to learn a Boolean function. We also explore the existence of very complex Boolean functions, considering, in particular, the symmetric Boolean functions.

This paper concerns the generalization accuracy when training a classifier that is a fixed Boolean function of the outputs of a number of perceptrons. The analysis involves the 'margins' achieved by the constituent perceptrons on the training data. A special case is that in which the fixed Boolean function is the majority function (where we have a 'committee of perceptrons'). Recent work of Auer et al. studied the computational properties of such networks (where they were called 'parallel perceptrons'), proposed an incremental learning algorithm for them. The results given here provide further motivation for the use of this learning rule.

We analyze Boolean functions using a recently proposed measure of their complexity. This complexity measure, motivated by the aim of relating the complexity of the functions with the generalization ability that can be obtained when the functions are implemented in feed-forward neural networks, is the sum of two components. The first of these is related to the 'average sensitivity' of the function and the second is, in a sense, a measure of the 'randomness' or lack of structure of the function. In this paper, we investigate the importance of using the second term in the complexity measure. We also explore the existence of very complex Boolean functions, considering, in particular, the symmetric Boolean functions.

Article Cross-validation for binary classification by real-valued functions: theoretical analysis Share on Authors: Martin Anthony Department of Mathematics, London School of Economics, Houghton Street, London WC2A 2AE, U.K. Department of Mathematics, London School of Economics, Houghton Street, London WC2A 2AE, U.K.View Profile , Sean B. Holden Department of Computer Science, University College London, Gower Street, London WC1E 6BT, U.K. Department of Computer Science, University College London, Gower Street, London WC1E 6BT, U.K.View Profile Authors Info & Claims COLT' 98: Proceedings of the eleventh annual conference on Computational learning theoryJuly 1998 Pages 218–229https://doi.org/10.1145/279943.279987Online:24 July 1998Publication History 10citation449DownloadsMetricsTotal Citations10Total Downloads449Last 12 Months29Last 6 weeks5 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 SiteGet Access

The paper introduces some generalizations of Vapnik's (1982) method of structural risk minimization (SRM). As well as making explicit some of the details on SRM, it provides a result that allows one to trade off errors on the training sample against improved generalization performance. It then considers the more general case when the hierarchy of classes is chosen in response to the data. A result is presented on the generalization performance of classifiers with a "large margin". This theoretically explains the impressive generalization performance of the maximal margin hyperplane algorithm of Vapnik and co-workers (which is the basis for their support vector machines). The paper concludes with a more general result in terms of "luckiness" functions, which provides a quite general way for exploiting serendipitous simplicity in observed data to obtain better prediction accuracy from small training sets. Four examples are given of such functions, including the Vapnik-Chervonenkis (1971) dimension measured on the sample.

The paper introduces a framework for studying structural risk minimisation. The model views structural risk minimisation in a PAC context. It then considers the more general case when the hierarchy of classes is chosen in response to the data. This theoretically explains the impressive performance of the maximal margin hyperplane algorithm of Vapnik. It may also provide a general technique for exploitingserendipitous simplicity in observed data to obtain better prediction accuracy from small training sets. 1 Introduction The standard PAC model of learning considers a fixed hypothesis class H together with a required accuracy ffl and confidence 1 \\Gamma ffi . The theory characterises when a target function from H can be learned from examples in terms of the Vapnik-Chervonenkis dimension, a measure of the flexibility of the class H and specifies sample sizes required to deliver the required accuracy with the allowed confidence. In many cases of practical interest the precise class conta...

In this paper we examine the representational and expressive power of two types of linearly weighted neural network:the polynomial discriminators (PDFs) and the radial basis function networks (RBFNs)..

Some recent work [7, 14, 15] in computational learning theory has discussed learning in situations where the teacher is helpful, and can choose to present carefully chosen sequences of labelled examples to the learner. We say a function t in a set H of functions (a hypothesis space) defined on a set X is specified by S***X if the only function in H which agrees with t on S is t itself. The specification number σ(t) of t is the least cardinality of such an S. For a general hypothesis space, we show that the specification number of any hypotheis is at least equal to a parameter from [14] known as the testing dimension of H. We investigate in some detail the specification numbers of hypotheses in the set Hn of linearly separable boolean functions: We present general methods for finding upper bounds on σ(t) and we characterise those t which have largest σ(t). We obtain a general lower bound on the number of examples required and we show that for all nested hypotheses, this lower bound is attained. We prove that for any t ε Hn, there is exactly one set of examples of minimal cardinality (i.e., of cardinality σ(t)) which specifies t. We then discuss those t ε Hn which have limited dependence, in the sense that some of the variables are redundant (i.e., there are irrelevant attributes), giving tight upper and lower bounds on σ(t) for such hypotheses. In the final section of the paper, we address the complexity of computing specification numbers and related parameters.