Optimal attribute-efficient learning of disjunction, parity, and threshold functions
説明
Decision trees are a very general computation model. Here the problem is to identify a Boolean function f out of a given set of Boolean functions F by asking for the value of f at adaptively chosen inputs. For classes F consisting of functions which may be obtained from one function g on n inputs by replacing arbitrary n−k inputs by given constants this problem is known as attribute-efficient learning with k essential attributes. Results on general classes of functions are known. More precise and often optimal results are presented for the cases where g is one of the functions disjunction, parity or threshold.
