Learnability can be undecidable.
Shai Ben-DavidPavel HrubesShay MoranAmir ShpilkaAmir YehudayoffPublished in: Nat. Mach. Intell. (2019)
Keyphrases
- sufficient conditions
- uniform convergence
- finite automata
- np complete
- learning algorithm
- uniform distribution
- pattern languages
- boolean functions
- pac learnability
- inductive inference
- datalog programs
- pac learning
- dnf formulas
- concept class
- decision lists
- agnostic learning
- vapnik chervonenkis dimension
- membership queries
- inductive logic programming
- expressive power
- optimal solution