I will explain what a neural network is and how it is possible to
learn with neural networks. I will focus on neural networks with a
binary output space and will give a corresponding definition of a
learning algorithm (agnostic PAC learning).
In this context the VC-Dimension is an important quantity. It is
often difficult to calculate the VC-dimension exactly. Therefore
I want to explain how one can derive upper and lower bounds on the
VC-dimension. For the upper bound we use techniques that count
the number of connected components in the partition of parameter
space defined by the input points.