Computability-theoretic learning complexity

Area of Science:

• Computability-theoretic learning theory
• Theoretical computer science
• Algorithmic learning theory

Background:

• Explores Alan Turing's ideas on mind and mechanism.
• Focuses on algorithmic, trial-and-error program inference from data points.
• Critiques the use of intrinsic complexity in analyzing function learnability within Gold-style learning settings.

Purpose of the Study:

• Introduce epitomizing sets as an alternative to intrinsic complexity for analyzing learning complexity.
• Develop new reducibility notions based on robust learning to capture the concept of epitomizing sets.
• Characterize degrees of epitomizing sets and provide methods for their identification and generation.

Main Methods:

• Introduced new reducibility notions based on robust learning.
• Characterized various degrees of epitomizing sets using these new notions.
• Employed these characterizations to prove sets as epitomizers and developed a scheme for generating strong epitomizers (self-learning sets).

Main Results:

• Identified weaknesses in the notion of intrinsic complexity.
• Defined epitomizing sets as learnable under a criterion but not under weaker ones.
• Characterized epitomizing sets as complete with respect to new reducibility notions.
• Provided a scheme for generating strong epitomizers, specifically self-learning sets.

Conclusions:

• Epitomizing sets offer a robust alternative for analyzing learning complexity.
• New reducibility notions provide effective tools for characterizing and identifying epitomizing sets.
• The developed scheme facilitates the generation of strong epitomizers, demonstrating strict separations in learning power between criteria.