Estimating decision tree learnability with polylogarithmic sample complexity.
Guy BlancNeha GuptaJane LangeLi-Yang TanPublished in: CoRR (2020)
Keyphrases
- sample complexity
- pac learnability
- decision trees
- pac learning
- decision lists
- learning algorithm
- uniform convergence
- vc dimension
- theoretical analysis
- learning problems
- concept class
- upper bound
- generalization error
- lower bound
- machine learning algorithms
- special case
- supervised learning
- active learning
- sample size
- pac model
- machine learning
- real valued functions
- training set
- vapnik chervonenkis dimension
- concept classes
- training examples
- computational learning theory
- uniform distribution
- agnostic learning
- membership queries
- optimal solution
- semi supervised learning
- learning process