Affiliation: | a Faculty of Natural Sciences, Komazawa University, Komazawa 1-23-1, Setagaya-ku, Tokyo 154-8525, Japan b Faculty of Engineering, Toyo University, Kujirai, Kawagoe-shi, Saitama 350, Japan c FB Informatik, LS II, University Dortmund, 44221 Dortmund, Germany |
Abstract: | Let F be a class of functions obtained by replacing some inputs of a Boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient learning, is to identify “efficiently” a Boolean function g out of F by asking for the value of g at chosen inputs, where “efficiency” is measured in terms of the number of essential variables. We study the query complexity of attribute-efficient learning for three function classes that are, respectively, obtained from disjunction, parity, and threshold functions. In many cases, we obtain almost optimal upper and lower bound on the number of queries. |