Definable families of finite Vapnik Chervonenkis dimension

Simple item page
dc.contributor.advisorLaskowski, Michael Cen_US
dc.contributor.authorJohnson, Hunter Ren_US
dc.contributor.departmentMathematicsen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2008-06-20T05:37:12Z
dc.date.available2008-06-20T05:37:12Z
dc.date.issued2008-04-25en_US
dc.description.abstractVapnik Chervonenkis dimension is a basic combinatorial notion with applications in machine learning, stability theory, and statistics. We explore what effect model theoretic structure has on the VC dimension of formulas, considered as parameterized families of sets, with respect to long disjunctions and conjunctions. If the growth in VC dimension is linear in the number of disjunctions, then the theory under consideration has a certain kind of good structure. We have found a general class of theories in which this structure obtains, as well as situations where it fails. We relate ``compression schemes'' of computational learning theory to model theoretic type definitions, and explore the model theoretic implications. All stable definable families are shown to have finite compression schemes, with specific bounds in the case of NFCP theories. Notions of maximality in VC classes are discussed, and classified according to their first order properties. While maximum classes can be characterized in first-order logic, maximal classes can noten_US
dc.format.extent520453 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/8174
dc.language.isoen_US
dc.subject.pqcontrolledMathematicsen_US
dc.subject.pqcontrolledComputer Scienceen_US
dc.subject.pquncontrolledVC dimensionen_US
dc.subject.pquncontrolledVCen_US
dc.subject.pquncontrolledlogicen_US
dc.subject.pquncontrolledmodel theory;Vapnik Chervonenkis dimensionen_US
dc.subject.pquncontrolledIndependence dimensionen_US
dc.titleDefinable families of finite Vapnik Chervonenkis dimensionen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
umi-umd-5355.pdf
Size:
508.25 KB
Format:
Adobe Portable Document Format
Download

Collections

UMD Theses and Dissertations
Mathematics Theses and Dissertations