Predictive PAC Learning and Process Decompositions.

Area of Science:

• Machine Learning
• Statistical Learning Theory
• Probability Theory

Background:

• Stochastic processes are learnable if their generalization error approaches zero for finite VC-dimension concept classes.
• Mixtures of learnable processes may not be learnable themselves, and their generalization error rates can differ.
• Traditional PAC learning conditions on past observations, posing challenges for dependent data.

Purpose of the Study:

• To propose a novel definition of learnability in predictive PAC that conditions on mixture components.
• To develop a PAC generalization bound for mixtures of learnable processes.
• To characterize mixtures of absolutely regular (β-mixing) processes.

Main Methods:

• Introduced a predictive PAC framework conditioning on mixture components rather than past observations.
• Derived a novel PAC generalization bound for mixtures of learnable processes.
• Provided a characterization of mixtures of absolutely regular (β-mixing) processes.

Main Results:

• The proposed conditioning on mixture components addresses limitations of traditional PAC learning with dependent data.
• A new PAC generalization bound guarantees that the mixture's error is no worse than its components.
• Characterized mixtures of β-mixing processes, contributing to probability theory.

Conclusions:

• Conditioning on mixture components offers a more realistic and tractable approach for learning from dependent data.
• The derived generalization bound provides theoretical guarantees for learning from mixtures of learnable processes.
• The characterization of β-mixing process mixtures advances understanding in probability theory and statistical learning.