Trial and error: A new approach to space-bounded learning (Q1901711)

A pac-learning algorithm is \(d\)-space bounded, if it stores at most \(d\) examples from the sample at any time. We characterize the \(d\)-space learnable concept classes. For this purpose we introduce the compression parameter of a concept class \(\mathcal C\) and design our Trial and Error Learning Algorithm. We show: \({\mathcal C}\) is \(d\)-space learnable if and only if the compression parameter of \(\mathcal C\) is at most \(d\). This learning algorithm does not produce a hypothesis consistent with the whole sample as previous approaches e.g. by \textit{Floyd}, who presents consistent space bounded learning algorithms, but has to restrict herself to very special concept classes. On the other hand our algorithm needs large samples; the compression parameter appears as exponent in the sample size. We present several examples of polynomial time space bounded learnable concept classes: \(\bullet\) all intersection closed concept classes with finite VC-dimension, \(\bullet\) convex \(n\)-gons in \(\mathbb{R}^2\), \(\bullet\) halfspaces in \(\mathbb{R}^n\), \(\bullet\) unions of triangles in \(\mathbb{R}^2\). We further relate the compression parameter to the VC-dimension, and discuss variants of this parameter.