Bounding the Fat Shattering Dimension of a Composition Function Class Built Using a Continuous Logic Connective

Details Bounding the Fat Shattering Dimension of a Composition Function Class Built Using a Continuous Logic Connective Bounding the Fat Shattering Dimension of a Composition Function Class Built Using a Continuous Logic Connective

2011-05-23

arxiv.org/abs/1105.4618v1

Computer Science

Learning

Winter 2011 Honours research project done under the supervision of Dr. Vladimir Pestov at the University of Ottawa; 35 pages

Scientific paper

We begin this report by describing the Probably Approximately Correct (PAC) model for learning a concept class, consisting of subsets of a domain, and a function class, consisting of functions from the domain to the unit interval. Two combinatorial parameters, the Vapnik-Chervonenkis (VC) dimension and its generalization, the Fat Shattering dimension of scale e, are explained and a few examples of their calculations are given with proofs. We then explain Sauer's Lemma, which involves the VC dimension and is used to prove the equivalence of a concept class being distribution-free PAC learnable and it having finite VC dimension. As the main new result of our research, we explore the construction of a new function class, obtained by forming compositions with a continuous logic connective, a uniformly continuous function from the unit hypercube to the unit interval, from a collection of function classes. Vidyasagar had proved that such a composition function class has finite Fat Shattering dimension of all scales if the classes in the original collection do; however, no estimates of the dimension were known. Using results by Mendelson-Vershynin and Talagrand, we bound the Fat Shattering dimension of scale e of this new function class in terms of the Fat Shattering dimensions of the collection's classes. We conclude this report by providing a few open questions and future research topics involving the PAC learning model.

Affiliated with

Also associated with

No associations

Rating

Bounding the Fat Shattering Dimension of a Composition Function Class Built Using a Continuous Logic Connective does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounding the Fat Shattering Dimension of a Composition Function Class Built Using a Continuous Logic Connective, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounding the Fat Shattering Dimension of a Composition Function Class Built Using a Continuous Logic Connective will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-514397