A Boolean function is called read-once over a basis B if it can be expressed by a formula over B where no variable appears more than once. A checking test for a read-once function f over B depending on all its variables is a set of input vectors distinguishing f from all other read-once functions of the same variables. We show that every read-once function f over B has a checking test containing O(n^l) vectors, where n is the number of relevant variables of f and l is the largest arity of functions in B. For some functions, this bound cannot be improved by more than a constant factor. The employed technique involves reconstructing f from its l-variable projections and provides a stronger form of Kuznetsov's classic theorem on read-once representations.
Closely related to the notion of checking test complexity is the definition of teaching dimension introduced by Goldman and Kearns @cite_3 . A teaching sequence for a Boolean concept (a Boolean function @math ) in a known class @math is a sequence of labeled instances (pairs of the form @math ) consistent with only one function @math from @math . The teaching dimension of a class is the smallest number @math such that all concepts in the class have teaching sequences of length at most @math .
@cite_3
2020764470
While most theoretical work in machine learning has focused on the complexity of learning, recently there has been increasing interest in formally studying the complexity of teaching. In this paper we study the complexity of teaching by considering a variant of the on-line learning model in which a helpful teacher selects the instances. We measure the complexity of teaching a concept from a given concept class by a combinatorial measure we call the teaching dimension, Informally, the teaching dimension of a concept class is the minimum number of instances a teacher must reveal to uniquely identify any target concept chosen from the class.