Properly learning decision trees with queries is NP-hard.
Caleb KochCarmen StrassleLi-Yang TanPublished in: FOCS (2023)
Keyphrases
- decision trees
- np hard
- learning process
- learning algorithm
- learning systems
- response time
- objective function
- supervised learning
- active learning
- special case
- query processing
- prior knowledge
- information retrieval
- data sources
- semi supervised
- relational databases
- reinforcement learning
- online learning
- training data
- learning tasks