Bounding the Fat Shattering Dimension of a Composition Function Class
  Built Using a Continuous Logic Connective
  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.
