Optimal attribute-efficient learning of disjunction, parity, and threshold functions
Ryuhei UeharaKensei TsuchidaIngo WegenerPublished in: Electron. Colloquium Comput. Complex. (1996)
Keyphrases
- decision lists
- attribute efficient learning
- threshold functions
- decision trees
- concept classes
- pac learning
- sample complexity
- rule sets
- agnostic learning
- optimal solution
- low degree
- noise tolerant
- uniform distribution
- machine learning
- classification models
- learning theory
- theoretical analysis
- worst case
- training data
- learning algorithm