Dimension of hypothesis class of multiclass classifiers which characterizes Uniform learnability

To prove that Natarajan dimension of One-vs-all based classes for k classes is less than kd, where d is the VC-dimension of the individual one-vs-all classes. Consider a set of kd, which is shattered, under the multi-class definition of shattering. Take the two functions f0 and f1 in that definition. One of the classes has a preimage under f0 which has size at least d. f1 labels these points differently. Using definition of multiclass shattering this implies that the corresponding one-vs-all labeller for that class shatters this set of size at least d*. Therefore NdimOvA>=kd => VCdim>=d or VCdim <d => NdimOvA < kd

• This doesn't work for the case where we construct the multiclass classifier from inconsistent one-vs-all binary classifiers. The number of OvA for class k for the multiclass classifiers may be greater than the original component OvA. I guess in that case we need to use the other bound in UML maybe?

UML 29.1 Consider the class of binary classifies that shatter a set X, but outside the set are uniformly 1. The corresponding OvA multilabel class has Ndim d also, irrespective of k

See here for some discussion/results on extensions of VC dimension to multiclass classifiers (and even real-valued functions)