Estimating decision tree learnability with polylogarithmic sample complexity.
Guy BlancNeha GuptaJane LangeLi-Yang TanPublished in: NeurIPS (2020)
Keyphrases
- sample complexity
- pac learnability
- decision trees
- pac learning
- decision lists
- vc dimension
- learning algorithm
- uniform convergence
- concept class
- theoretical analysis
- learning problems
- upper bound
- generalization error
- active learning
- special case
- machine learning algorithms
- lower bound
- concept classes
- vapnik chervonenkis dimension
- supervised learning
- pac model
- real valued functions
- computational learning theory
- machine learning
- training examples
- training data
- sample size
- uniform distribution
- target concept
- agnostic learning
- training set
- support vector
- dnf formulas
- inductive logic programming
- data mining
- learning experience
- text classification