On the minimal teaching sets of two-dimensional threshold functions
This work addresses a theoretical problem in computational learning theory, providing incremental results on teaching set sizes for threshold functions.
The paper tackles the problem of determining minimal teaching sets for two-dimensional threshold functions, deriving exact formulae for functions with sets of size 3 or 4 and proving that the average set size asymptotically approaches 7/2.
It is known that a minimal teaching set of any threshold function on the twodimensional rectangular grid consists of 3 or 4 points. We derive exact formulae for the numbers of functions corresponding to these values and further refine them in the case of a minimal teaching set of size 3. We also prove that the average cardinality of the minimal teaching sets of threshold functions is asymptotically 7/2. We further present corollaries of these results concerning some special arrangements of lines in the plane.