Mas 557 기계학습 이론 및 응용

Homework #6

due date: 5/17/05

1. Consider the learning of a two-input perceptron for binary classification.

(a) Give an upper bound on the number of training examples sufficient to assure with the minimum probability of 95% that the learned perceptron will have the true error of at most 0.05.

(b) Give a lower bound on the number of training examples necessary to assure with the maximum probability of 95 % that the learned perceptron will have the true error of at most 0.05.

2. In (1), we have 1000 samples.  What is the maximum difference between the true and empirical risks in  with the confidence of 0.95?

3. The estimation function  for the target function  is considered for the function approximation problem.  Here, we assume that the loss function is bounded, i.e.,

.

In this case, the following probability bound

is satisfied for the finite VCD of loss function .

Determine the generalization bound of regression models using the suggested

probability bound.

4. For the case of ANNs including sigmiodal, radial basis functions, and sigma-pi networks, describe the upper bounds of confidence intervals in big-O notation in the cases of 1) the bounded loss functions, and 2) the non-negative loss functions.

5. Consider a structure for which the VCD of the hypothesis  and the approximation

error is given by .  Show that the optimal  is proportional to

such that the following asymptotic rate of convergence reaches its maximum:

where  is a constant.