A Map of Update Constraints in Inductive Inference
This work provides foundational insights into inductive inference theory, mapping constraints for delayable learning restrictions, which is incremental to existing research in computational learning theory.
The paper investigates how various learning restrictions affect learning power and their interrelations, providing a complete map for nine restrictions in both complete information and set-driven learning scenarios, and offers characterizations of conservative learning in terms of cautious learning variants.
We investigate how different learning restrictions reduce learning power and how the different restrictions relate to one another. We give a complete map for nine different restrictions both for the cases of complete information learning and set-driven learning. This completes the picture for these well-studied \emph{delayable} learning restrictions. A further insight is gained by different characterizations of \emph{conservative} learning in terms of variants of \emph{cautious} learning. Our analyses greatly benefit from general theorems we give, for example showing that learners with exclusively delayable restrictions can always be assumed total.