Learning decision trees from random examples needed for learning

摘要: Abstract We define the rank of a decision tree and show that for any fixed r , class all trees at most on n Boolean variables is learnable from random examples in time polynomial linear 1/ɛ log(1/δ), where ɛ accuracy parameter δ confidence parameter. Using suitable encoding variables, Rivest's learnability result lists can be interpreted as special case this 1. As another corollary, we size are O (log ) 1/ɛ, log(1/δ). third functions have DNF expressions both their positive negative instances ((log 2