As we mentioned earlier, traditional PAC learning cannot capture data-dependent assumptions. Inspired by [1]}, we slightly modify the basic multiclass learning problem in a quite simple manner: instead of dealing with concept classes \(\mathcal {H}\subseteq \lbrace 0,1,...,k\rbrace ^\mathcal {X}\)  where each concept \(h \in \mathcal {H}\)  is a total function \(h : \mathcal {X}\rightarrow \lbrace 0,1,...,k\rbrace \) , we study partial concept classes \(\mathcal {H}\subseteq \lbrace 0,1,...,k,\star \rbrace ^\mathcal {X}\) , where each concept \(h\)  is now a partial function and \(h(x) = \star \)  means that the function \(h\)  is undefined at \(x\) . We define the support of \(h\)  as the set \(\mathrm {supp}(h) = \lbrace  x \in \mathcal {X}: h(x) \ne \star \rbrace .\)
