Homework # 1

15-486/782: Artificial Neural Networks Dave Touretzky, Fall 2006

• Due September 6, 2006.

• Read HK&P sections 5.1 through 5.4 first.

• Software you need is in /afs/cs/academic/class/15782-f06/matlab/perceptron

• Answers must be typed. Handwritten answers will not be accepted.

Problems

1. Suppose you want to train a two-input perceptron on the following classification problem:

P atterns = [ \begin{matrix}2 & 1 & 3 \\ 6 & 3 & 9 \end{matrix} ] Desired = [ 0 1 1 ]

Prove that the perceptron cannot learn this task, using inequalities expressed in terms of the weights w_{0}, w_{1}, and w_{2}.

2. The proof of the perceptron convergence theorem states that if ŵ is a weight vector that correctly classifies all patterns, and \overline{w}^{(τ)} is the weight vector at step τ of the algorithm, then ŵ · \overline{w}^{(τ)} increases at each step. Modify the perceptron program to demonstrate this by displaying the value of this dot product at each step. Turn in your source code and a sample run.

Note: in order to do this you will need to know the correct weight vector at the start of the run. You can calculate this vector directly from the slope and y-intercept in the perceptron demo.

3. Run the bowl demo with learning rates of 0.1, 0.142, and 0.15. Hand in a printout of each run. What can you say about the model’s behavior at each learning rate?

4. Consider the function f(x, y) = exp (−(0.6y − 0.7)^{2} − (x − 0.4)^{2}). The following code will graph f for you:

    [x,y] = meshgrid(0 :  0.1 :  1);
    z = exp(-(0.6*y-0.7).^2-(x-0.4).^2);
    surf(x,y,z)
    box on, rotate3d on

Problem: (a) Train an LMS network to approximate f(x, y) over the unit square (0 ≤ x ≤ 1, 0 ≤ y ≤ 1). You may use the code in lms3d.m to get started, if you wish. (b) What is the shape of your approximation function? (c) By looking at the weights of your trained network, you can see the first degree polynomial that the neural network has devised to approximate f. Write down this polynomial, and hand it in along with the code you wrote to solve this problem.

5. How much information does it take to describe a two-input perceptron? The classical description uses a vector of three real-valued parameters: w⃗ = ⟨w_{0}, w_{1}, w_{2}⟩. But the perceptron’s decision boundary is a line, which can be uniquely specified with just two parameters, e.g., slope and intercept.

Jack says: “I claim a perceptron can be described with less information than three real numbers. Here’s how I would do it with just two real values: set s_{0} = w_{0}/w_{2}, and s_{1} = w_{1}/w_{2}. From the description ⟨s_{0}, s_{1}⟩, I can construct a weight vector ⟨s_{0}, s_{1}, 1⟩ that describes a line with the same slope and intercept as the one described by w⃗. So it should behave exactly the same as w⃗ for all inputs.”

Jill replies: “I claim a perceptron requires more than just two real numbers to describe. A line is not an inequality. Consider the case where w_{2} is negative. How will that effect the results of your transformation?”

(a) Whose claim is correct, and why?

(b) How much information does it really take to correctly describe a two-input perceptron? (Don’t worry about the case where w_{2} = 0.)