On specifying Boolean functions by labelled examples

DOI10.1016/0166-218X(94)00007-ZzbMath0826.06008MaRDI QIDQ1897365

John Shawe-Taylor, Martin Anthony, Graham R. Brightwell

Publication date: 28 November 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

hyperplanelinearly separable Boolean functionsspecification numbertesting dimension

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Boolean functions (06E30) Other classical set theory (including functions, relations, and set algebra) (03E20)

Related Items

On data classification by iterative linear partitioning, A characterization of 2-threshold functions via pairs of prime segments, Witness sets for families of binary vectors, On teaching sets of \(k\)-threshold functions, On the number of irreducible points in polyhedra, Improved approximation of linear threshold functions, Measuring teachability using variants of the teaching dimension, Massive online teaching to bounded learners, Learning mixtures of spherical gaussians, Low-weight halfspaces for sparse boolean vectors, Learnability of DNF with representation-specific queries, Can theories be tested?, Making evolution rigorous, On the convergence of the Hegselmann-Krause system, Is privacy compatible with truthfulness?, Differentially private data analysis of social networks via restricted sensitivity, Characterizing the sample complexity of private learners, Barriers in cryptography with weak, correlated and leaky sources, On the possibilities and limitations of pseudodeterministic algorithms, Evasiveness through a circuit lens, The garden-hose model, Space-bounded communication complexity, Towards an optimal query efficient PCP?, A characterization of approximation resistance for even k-partite CSPs, On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction, On the power of many one-bit provers, Approaching utopia, Learning and incentives in user-generated content, Welfare maximization and the supermodular degree, Reachability in graph timelines, Runtime guarantees for regression problems, An energy complexity model for algorithms, Streaming computations with a loquacious prover, Adversary lower bound for the k-sum problem, Stronger methods of making quantum interactive proofs perfectly complete, Active self-assembly of algorithmic shapes and patterns in polylogarithmic time, An equational approach to secure multi-party computation, Publicly verifiable proofs of sequential work, On the power of nonuniformity in proofs of security, Fast reductions from RAMs to delegatable succinct constraint satisfaction problems, Resource-based corruptions and the combinatorics of hidden diversity, Time hierarchies for sampling distributions, Properties and applications of boolean function composition, Pseudo-partitions, transversality and locality, Competing provers protocols for circuit evaluation, Catch them if you can, Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints, Robust optimization in the presence of uncertainty, Sorting noisy data with partial information, New affine-invariant codes from lifting, H-wise independence, Sparse extractor families for all the entropy, On the power of conditional samples in distribution testing, Teaching randomized learners with feedback, Monotone term decision lists, Decision lists and related Boolean functions, Recent Developments in Algorithmic Teaching, Linear read-once and related Boolean functions, DNF are teachable in the average case, The Vapnik-Chervonenkis dimension of a random graph, On Boolean threshold functions with minimum specification number, On the limits of efficient teachability, On teaching sets for 2-threshold functions of two variables

Cites Work

• Teachability in computational learning
• Linear function neurons: Structure and training
• Approximation algorithms for combinatorial problems
• Testing geometric objects
• On the complexity of teaching
• Queries and concept learning
• Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions
• Learnability and the Vapnik-Chervonenkis dimension
• Using the Perceptron Algorithm to Find Consistent Hypotheses
• Enumeration of Seven-Argument Threshold Functions
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item