Description
1
• Linear Regression Error
Consider a noisy target y = w∗T x + , where x ∈ R
d
(with the added coordinate
x0 = 1), y ∈ R, w∗
is an unknown vector, and is a noise term with zero mean and
σ
2 variance. Assume is independent of x and of all other ’s. If linear regression
is carried out using a training data set D = {(x1, y1), . . . ,(xN , yN )}, and outputs the
parameter vector wlin, it can be shown that the expected in-sample error Ein with
respect to D is given by:
ED[Ein(wlin)] = σ
2
1 −
d + 1
N
1. For σ = 0.1 and d = 8, which among the following choices is the smallest
number of examples N that will result in an expected Ein greater than 0.008?
[a] 10
[b] 25
[c] 100
[d] 500
[e] 1000
• Nonlinear Transforms
In linear classification, consider the feature transform Φ : R
2 → R
2
(plus the added
zeroth coordinate) given by:
Φ(1, x1, x2) = (1, x2
1
, x2
2
)
2. Which of the following sets of constraints on the weights in the Z space could
correspond to the hyperbolic decision boundary in X depicted in the figure?
x
x
2
1
−1 −1 +1
You may assume that ˜w0 can be selected to achieve the desired boundary.
2
[a] w˜1 = 0,w˜2 > 0
[b] w˜1 > 0,w˜2 = 0
[c] w˜1 > 0,w˜2 > 0
[d] w˜1 < 0,w˜2 > 0
[e] w˜1 > 0,w˜2 < 0
Now, consider the 4th order polynomial transform from the input space R
2
:
Φ4 : x → (1, x1, x2, x2
1
, x1x2, x2
2
, x3
1
, x2
1×2, x1x
2
2
, x3
2
, x4
1
, x3
1×2, x2
1x
2
2
, x1x
3
2
, x4
2
)
3. What is the smallest value among the following choices that is not smaller than
the VC dimension of a linear model in this transformed space?
[a] 3
[b] 5
[c] 15
[d] 20
[e] 21
• Gradient Descent
Consider the nonlinear error surface E(u, v) = (uev − 2ve−u
)
2
. We start at the point
(u, v) = (1, 1) and minimize this error using gradient descent in the uv space. Use
η = 0.1 (learning rate, not step size).
4. What is the partial derivative of E(u, v) with respect to u, i.e., ∂E
∂u ?
[a] (uev − 2ve−u
)
2
[b] 2(uev − 2ve−u
)
[c] 2(e
v + 2ve−u
)
[d] 2(e
v − 2ve−u
)(uev − 2ve−u
)
[e] 2(e
v + 2ve−u
)(uev − 2ve−u
)
5. How many iterations (among the given choices) does it take for the error E(u, v)
to fall below 10−14 for the first time? In your programs, make sure to use double
precision to get the needed accuracy.
[a] 1
3
[b] 3
[c] 5
[d] 10
[e] 17
6. After running enough iterations such that the error has just dropped below
10−14, what are the closest values (in Euclidean distance) among the following
choices to the final (u, v) you got in Problem 5?
[a] (1.000, 1.000)
[b] (0.713, 0.045)
[c] (0.016, 0.112)
[d] (−0.083, 0.029)
[e] (0.045, 0.024)
7. Now, we will compare the performance of “coordinate descent.” In each iteration, we have two steps along the 2 coordinates. Step 1 is to move only along
the u coordinate to reduce the error (assume first-order approximation holds
like in gradient descent), and step 2 is to reevaluate and move only along the v
coordinate to reduce the error (again, assume first-order approximation holds).
Use the same learning rate of η = 0.1 as we did in gradient descent. What will
the error E(u, v) be closest to after 15 full iterations (30 steps)?
[a] 10−1
[b] 10−7
[c] 10−14
[d] 10−17
[e] 10−20
• Logistic Regression
In this problem you will create your own target function f (probability in this case)
and data set D to see how Logistic Regression works. For simplicity, we will take f
to be a 0/1 probability so y is a deterministic function of x.
Take d = 2 so you can visualize the problem, and let X = [−1, 1]×[−1, 1] with uniform
probability of picking each x ∈ X . Choose a line in the plane as the boundary between
f(x) = 1 (where y has to be +1) and f(x) = 0 (where y has to be −1) by taking two
random, uniformly distributed points from X and taking the line passing through
4
them as the boundary between y = ±1. Pick N = 100 training points at random
from X , and evaluate the outputs yn for each of these points xn.
Run Logistic Regression with Stochastic Gradient Descent to find g, and estimate Eout
(the cross entropy error) by generating a sufficiently large, separate set of points to
evaluate the error. Repeat the experiment for 100 runs with different targets and take
the average. Initialize the weight vector of Logistic Regression to all zeros in each
run. Stop the algorithm when kw(t−1) − w(t)k < 0.01, where w(t) denotes the weight
vector at the end of epoch t. An epoch is a full pass through the N data points (use a
random permutation of 1, 2, · · · , N to present the data points to the algorithm within
each epoch, and use different permutations for different epochs). Use a learning rate
of 0.01.
8. Which of the following is closest to Eout for N = 100?
[a] 0.025
[b] 0.050
[c] 0.075
[d] 0.100
[e] 0.125
9. How many epochs does it take on average for Logistic Regression to converge for
N = 100 using the above initialization and termination rules and the specified
learning rate? Pick the value that is closest to your results.
[a] 350
[b] 550
[c] 750
[d] 950
[e] 1750
• PLA as SGD
10. The Perceptron Learning Algorithm can be implemented as SGD using which
of the following error functions en(w)? Ignore the points w at which en(w) is
not twice differentiable.
[a] en(w) = e
−ynw|xn
[b] en(w) = −ynw|xn
[c] en(w) = (yn − w|xn)
2
[d] en(w) = ln(1 + e
−ynw|xn )
[e] en(w) = − min(0, ynw|xn)
5
