CS 391L Machine Learning
Homework 3: Computational Learning Theory


Due: October 25, 2007


Present solutions to the following PAC learning-theory problems. Show each significant step in deriving the solution, presenting a clear and complete explanation of how each equation is derived. Presenting a solution without a clear step by step derivation and/or explanation is inadequate. When finding upper bounds, always try to find the tightest bound that you can. Final solutions should be in closed form (no iterative sums (sigma's) or products (pi's)). Handwritten solutions are fine as long as they are clearly written and presented. Remember the log's in the Blumer bound are base two.
  1. Consider the class of concepts, C, consisting of axis-parallel hyper-rectangles in n-dimensional space. That is, assume instances are described by n real-valued features and that an instance is classified as positive iff the value for each feature, xi, falls in the range (li <= xi <= ui) where li and ui are separate lower and upper bounds specified for each feature.

    (a) First consider a discretized concept space where all bounds li and ui must be integers in the interval (0, m), inclusive. Note that zero-width hyper-rectangles along one or more dimensions are allowed since it is possible that li = ui for any feature. Using the size of this finite hypothesis space, give an upper bound on the number of randomly drawn training instances sufficient to assure that for any concept in C, any consistent learner using H=C, will, with probability at least 1-, output a hypothesis with error at most . Calculate a specific number of sufficient examples when n=3 (axis-parallel boxes in 3-D), m=10, and = = 0.01.

    (b) Now suppose the hyper-rectangle boundaries, li and ui, can take on real values. Update your answers to part (a).

  2. Consider the class of concepts described by single M-of-N rules on n binary features. An M-of-N rule contains N literals and is true if any subset of M of them are true. For example:

    3-of-{red, not(small), soft, not(box)}

    is true if any 3 of the 4 given literals are true for an example. Note: M and N are not parameters defining the space, the hypothesis space includes all possible rules with all possible meaningful values of M and N over the set of n features.

    (a) Determine an upper-bound on the PAC sample complexity of any consistent learning algorithm using this hypothesis space.

    (b) Using this upper-bound, calculate a sufficient number of examples when = =0.01, n = 50.

  3. Assuming instances are described by a single real-valued feature, x, consider the class of concepts, C, consisting of disjunctions of two intervals, (a <= x <= b) or (c <= x <= d) where a, b, c and d are all real values.

    (a) Give an upper bound on the number of randomly drawn training instances sufficient to assure that for any concept in C, any consistent learner using H=C, will, with probability at least 1-, output a hypothesis with error at most .

    (b) Calculate a specific number of sufficient examples when = = 0.01.

    (c) Generalize your result to disjunctions of k real-valued intervals on a single real-valued feature.