Here, \(\mathrm {Ndim}(\mathcal {H})\)  is the Natarajan dimension of \(\mathcal {H}\)  (see definition:natarajan dimension and rem:vc). At first sight this result may not seem surprising. However, its proof is different from the standard multiclass PAC learning (for constant \(k\) ), which goes through uniform convergence and ERM. In fact, such tools provably fail [1]}. For a sketch, see below theorem:partial-pac-learning-sc.
We complement the above structural result with some additional insight which sheds light towards the, perhaps unanticipated, complexity of partial concept classes.
To this end, we discuss the question of disambiguation [2]}, [1]}: Can a partial Natarajan class (i.e., with finite \(\mathrm {Ndim}\) ) be represented by total Natarajan classes? To address this task, the notion of disambiguation is required: roughly, a total class \(\overline{\mathcal {H}}\)  disambiguates the partial class \(\mathcal {H}\)  if every partial concept \(h \in \mathcal {H}\)  can be extended to some total concept \(\overline{h} \in \overline{\mathcal {H}}\) , i.e., \(\overline{h}\)  agrees with \(h\)  in the support of \(h\)  and assigns to the undefined points some labels. For a formal definition of disambiguation, see definition:disambiguation. For the case \(k=1\) , [1]} provided an easy-to-learn partial class that cannot be represented by any total class of bounded VC dimension using, surprisingly, some recent results from communication complexity and graph theory (see e.g., [5]}). We extend this result to the multiclass setting using Sauer's lemma, which provides a bound on the growth function [6]}, and tools from the binary impossibility result.
