Unprovability and Other Impossibility Results in Machine Learning
summary
Shows that expectation-maximization learning of set families hinges on set-theory: existence of a finite compression scheme for finite-subset classes is equivalent to domain cardinality < aleph_k, so learnability of finite subsets of R becomes independent from ZFC (uses forcing and model constructions). Proves no first-order combinatorial dimension can characterize EMX learnability, and that requiring learners to be computable removes the independence. Tools: sample-compression games, cardinal arithmetic, and forcing arguments.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:46A fundamental statistical learning problem
- 4:04Two important types of problem restriction
- 5:59Talk outline
- 7:03A general learning approach -- Uniform Estimation of Random Variables
- 8:21A milder learning Problem -- Expectation Maximization (EMX)
- 9:35Examples of EMX problems
- 16:42The case of Subset Probability Maximization
- 17:19Non-equivalence for EMX
- 21:08Specific sample compression schemes
- 22:17Monotone compression for subset probability maximization Consider the collection of all finite subsets of a
- 24:18Examples of such compression
- 30:37The connection to learnability
- 32:24A Quantitative version
- 34:05A model theoretic observation
- 39:09Impossibility for Learnability of distributions
related talks
01h 12mLearning probability distributions; what can, what can't be done
30mComputational Barriers For Learning Some Generalized Linear Models
23mComparative Learning: A Sample Complexity Theory for Two Hypothesis Classes
40mExtending Generalization Theory Towards Addressing Modern Challenges in Machine Learning
48mFrom Predictions to Decisions: Limitations and Possibilities of Optimization from Samples
15mFundamental Limits Of Learning In Data-Driven Problems
55mThree Problems in Computable Probability Theory
29mA Pre-Expectation Calculus for Probabilistic Sensitivity