10.20381/ruor-5915
Kalajdzievski, Damjan
Measurability Aspects of the Compactness Theorem for Sample Compression Schemes
Université d'Ottawa / University of Ottawa
2012
Statistical Learning
VC-dimension
PAC learnability
Sample Compression Schemes
Measurability of Sample Compression Schemes
Université d'Ottawa / University of Ottawa
Université d'Ottawa / University of Ottawa
2012-07-31
2012-07-31
2012
2012
en
Thesis
http://hdl.handle.net/10393/23133
In 1998, it was proved by Ben-David and Litman that a concept space has a sample compression scheme of size $d$ if and only if every finite subspace has a sample compression scheme of size $d$. In the compactness theorem, measurability of the hypotheses of the created sample compression scheme is not guaranteed; at the same time measurability of the hypotheses is a necessary condition for learnability. In this thesis we discuss when a sample compression scheme, created from compression schemes on finite subspaces via the compactness theorem, have measurable hypotheses. We show that if $X$ is a standard Borel space with a $d$-maximum and universally separable concept class $\m{C}$, then $(X,\CC)$ has a sample compression scheme of size $d$ with universally Borel measurable hypotheses. Additionally we introduce a new variant of compression scheme called a copy sample compression scheme.