April 5
Michał Tomasz Godziszewski,
University of Warsaw
Set-Theoretic Independence and Machine Learning
In a recent exciting paper Learnability can be undecidable by S. Ben-David et. al. published in Nature Machine Intelligence the authors argue that certain abstract learnability questions are undecidable by ZFC axioms. The general learning problem considered there is to find a way of choosing a finite set that maximizes a particular expected value (within a certain range of error) with an obstacle that the probability distribution is unknown, or more formally:
given a family of functions $\mathcal{F}$ from some fixed domain $X$ to the real numbers and an unknown probability distribution $\mu$ over $X$, find, based on a finite sample generated by $\mu$, a function in $\mathcal{F}$ whose expectation with respect to $\mu$ is (close to) maximal.
The authors then provide a translation from this statistical framework to infinite comibnatorics: namely, they prove that existence of certain learning functions corresponding to the problem above (the so-called estimating the maximum learners, or EMX-learners) translates into the existence of the so-called monotone compression schemes, which in turn is equivalent to a statement in cardinal arithmetic that is indeed independent of ZFC. Specifically, let $X$ be an infinite set, $Fin(X)$ be the family of its finite subsets, and let $m > k$ be natural nubers. A monotone compressions scheme for $(X, m, k)$ is a function $f: [X]^k \rightarrow Fin(X)$ such that $$\forall A \in [X]^m \exists B \in [X]^k \: (B \subseteq A \subseteq f(B)).$$
The main result of the paper then is that there exists a monotone compressions scheme for $([0,1], m+1, m)$ for some $m$ if and only if $2^{\aleph_0} < \aleph_\omega$.
K.P. Hart immediately observed that the main combinatorial content of the results in the paper is related to Kuratowski's theorem on decompositions of finite powers of sets and that the monotone compression functions on the unit interval cannot, in a certain sense, be constructive or descriptively nice - namely, they cannot be Borel measurable. During the talk I will introduce the subject of the paper in question, and present the set-theoretic aspects of the main results.