QBUS1040 Assignment 5 Semester 1, 2022

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

QBUS1040 Assignment 5

Semester 1, 2022

1.  (10 points)  Algorithm 12.1 in the textbook uses the QR factorization to compute the least squares approx- imate solution  = A† b, where the m × n matrix A has linearly independent columns. It has a complexity of 2mn2  flops. In this exercise we consider an alternative method: First, form the Gram matrix G = AT A and the vector h = AT b, then compute  = G −1h (using algorithm 11.2 in the textbook).  What is the complexity of this method? Compare it to algorithm 12.1.

2. In this question, we examine computing k-fold cross-validation on a least squares problem ∥Ax−b∥2 , where A is a N ×p matrix and b is a N-vector. The least squares problem can arise, for example from a data-fitting model with N data points and p basis functions, and we wish to use k-fold cross validation to assess our choice of basis functions.

We assume for convenience that  N  can be split into  k  even-sized folds of size  N/k  (so  k  divides N). Let A1 , . . . ,Ak  denote the (N/k) × p blocks of data corresponding to each fold, and b1 , . . . ,bp  denote the corresponding right hand sides for each fold.  We also assume N is much larger than p, i.e., N ≫ p, and that columns of A remain linearly independent even when we remove one block Ai .

(a)  (5 points)  Analyse the complexity of the following na¨ıve method of performing k-fold cross-validation:

for each fold i = 1, . . . ,k

• Construct i  to be the matrix A but with rows corresponding to Ai  removed.  (Note that i  has size ((k − 1)N/k) × p.)

• Construct i to be the right-hand side vector b but with entries corresponding to bi removed. (Note that i  is a ((k − 1)N/k)-vector.)

• Compute θi  = i(†)i .

(b)  (5 points)  Argue that for any fold i = 1, . . . ,k ,

i(T)i  = AT A − Ai(T)Ai

i(T)i  = AT b − Ai(T)bi .

It may help to write A and b in block form:

 A1                        b1

A =  ...Ak    ,    b =   b...k   .

Then think about what the difference is between i , i  and A,b.

(c)  (5 points)  Based on the observation in part (b), we consider an alternative method to perform k-fold cross validation:

• Compute G = AT A, h = AT b.

• For each fold i = 1, . . . ,k, compute

θi  = (i(T)i ) −1i(T)i  = (G − Ai(T)Ai ) −1(h − Ai(T)bi ).

Analyse the complexity of this method and compare it to the na¨ıve method of part (a). When is this method better than the na¨ıve one?

3.  Suppose you have a dataset {(x(1) ,y (1) ), . . . , (x(N),y (N))} on which you wish to fit a linear regression model y ≈ xT β + v . Naturally, you try a least squares data fitting approach: define

 1    (x(1) )T                        y (1) 

A =   ...1    (x(...N) )T    ,    b =  y (...N)

and solve

β(m)  A   β(v)  − b  2 .

Unfortunately, you find that the model does not fit well, so you explore approaches to improve it.  One approach is to define an extra feature z as a linear combination of current features x, so z = xT γ for some fixed vector γ . Let (i)  = (x(i),z (i)) where z (i)  = (x(i))T γ for all i = 1, . . . ,N, and define

 =   1..    (( 1..) )T

 1    ((N))T    .

You then compare the previous model with the one obtained by solving

β˜(m)    β˜(v) − b  2 .

(a)  (5 points)  Do you expect the new model to perform better than the old one? Why or why not? Here,

“perform better” means that the sum of squared errors is lower.

(b)  (5 points) What computational issues do you expect to arise when you solve the new model?

4.  Estimating the  elasticity matrix.  In this problem you create a standard model of how demand varies with the prices of a set of products, based on some observed data. There are n different products, with (positive) prices given by the n-vector p.  The prices are held constant over some period, say, a day.  The (positive) demand for the products over the day is given by the n-vector d. The demand in any particular day varies, but it is thought to be (approximately) a function of the prices. The units of the prices and demands don’t really matter in this problem. Demand could be measured in 10,000 units, and prices in $100.

The nominal prices are given by the n-vector pnom .  You can think of these as the prices that have been charged in the past for the products. The nominal demand is the n-vector dnom . This is the average value of the demand, when the prices are set to pnom .   (The actual daily demand fluctuates around the value dnom .) You know both pnom  and dnom . We will describe the prices by their (fractional) variations from the nominal values, and the same for demands.  We define δp  and δ d  as the (vectors of) relative price change

and demand change:

δi(p)  =  ,    δi(d)  =  ,    i = 1, . . . ,n.

So δ3(p)  = +0.05 means that the price for product 3 has been increased by 5% over its nominal value, and δ5(d)  = −0.04 means that the demand for product 5 in some day is 4% below its nominal value. Your task is to build a model of the demand as a function of the price, of the form

δ d  ≈ Eδp ,

where E is the n × n elasticity matrix.

You don’t know E, but you do have the results of some experiments in which the prices were changed a bit from their nominal values for one day, and the day’s demands were recorded. This data has the form

(p1 ,d1 ), . . . , (pN ,dN ),

where pi  is the price for day i, and di  is the observed demand.

(a)  (10 points)  Explain how you would estimate E, given this price-demand data. Be sure to explain how

you will test for, and (if needed) avoid over-fit.

Hint.  You might find it easier to separately fit the models δi(d)  ≈ i(T)δp , where i  is the ith row of E . (We use the tilde above ei  to avoid conflict with the notation for unit vectors.)

(b)  (10 points)  Please refer to the Jupyter Notebook file for this problem.

5.  (20 points)  Please refer to the Jupyter Notebook file for this problem.

6.  Handwritten digit classification.

(a)  (5 points)  Please refer to the Jupyter Notebook file for this problem.

(b)  (5 points)  Please refer to the Jupyter Notebook file for this problem.

(c)  (5 points)  Please refer to the Jupyter Notebook file for this problem.

(d)  (5 points)  Note that your dataset is slightly different from the one we used in the lecture example, although both come from the same source.  In particular, you haven’t done any preprocessing to the images. Hence your confusion matrices will look slightly differently. Comment on what else causes the differences between your results and the results presented in the lecture (there is more to this story than preprocessing).





















2022-05-26