## Characterizations of Learnability for Classes of [0,...,n]-valued FunctionsComputer Research Laboratory, University of California, Santa Cruz, 1993 - Computational learning theory - 21 pages |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Common terms and phrases

0-1 loss functions Applications to learning apply Assume for contradiction binary encoding binary functions characterization of learnability characterize learnability Choose a class chosen arbitrarily class of multi-valued classes of binary completes the proof Corollary 14 definition of learnability definition of shattering denoted distinct elements equivalent extending the VC-dimension family of mappings flog2(n Follows immediately given class Graph dimension immediately from Lemma integer-valued function learnability for classes learnable w.r.t. learning problems learning sample complexity learning strategy least significant bit Lemma 15 Lemma 23 longest sequence main result multi-valued functions n}-valued functions Natarajan dimension necessary and sufficient notions of dimension p-dimension PAC learning sample positive integer probability distribution probability measure problem of learning Proof of Theorem properties prove robust learnability Santa Cruz scheme for extending sufficient for learning target function Theorem 16 trivially uniform convergence uniform dimension uniformly p-shattered V-dim(S Valiant's PAC model valued functions VC-shattered zj+1