Measurability Aspects of the Compactness Theorem for Sample Compression Schemes

Description
Title: Measurability Aspects of the Compactness Theorem for Sample Compression Schemes
Authors: Kalajdzievski, Damjan
Date: 2012
Abstract: 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.
URL: http://hdl.handle.net/10393/23133
http://dx.doi.org/10.20381/ruor-5915
CollectionThèses, 2011 - // Theses, 2011 -
Files