*IMPORTANT* Homework Submission Instructions

1.  All homeworks must be submitted in one PDF file to Gradescope.

2.  Please make sure to select the corresponding HW pages on Gradescope for each question

3.  For all coding components, complete the solutions with a Jupyter notebook/Google Colab, and export the notebook (including both code and outputs) into a PDF file.  Concatenate the theory solutions PDF file with the coding solutions PDF file into one PDF file which you will submit.

4. You must show work or give an explanation for every question.   “Yes”  and  “No” are not sufficient answers.  Always show the steps of your calculations.  Only partial credit can be given if you do not explain your answer.

5.  Failure to adhere to the above submission format may result in penalties.

All homework assignments must be your independent work product, no collaboration is al- lowed.  You may check your assignment with others or the internet after you have done it, but you must actually do it by yourself.  Please copy the following statement at the top of your assignment file:

Agreement:  This assignment represents my own work.  I did not work on this assignment with others. All coding was done by myself.

1    Constructing Kernels (Theory) 5 pts (Ishaan)

In class, we saw that by choosing a kernel

K(xi ,xk ) =< Φ(x), Φ(x) >Hk ,

we can implicitly map data to a high dimensional space, and have the SVM algorithm work in that space. One way to generate kernels is to explicitly define the mapping Φ to a higher dimensional space, and then work out the corresponding K. However in this question we are interested in direct construction of kernels. Let K be a kernel over Rn  × Rn , let a ∈ R.   < c,d > denotes the dot product, cTd.  Φ(x) represents a mapping function that transforms the original data point x into a higher-dimensional space, and Hk  refers to a Hilbert Space associated with the kernel k (the space where the kernel function operates).

For each of the function K below, state whether it is necessarily a kernel. If you think it is, prove it; Other- wise, please specify a counterexample.

(a) K1 (x,z) = aK(x,z) for a > 0

(b) K2 (x,z) = aK(x,z) for a < 0

d(c) K(K)4(3)x(x),, z(z)  x(x),, z(z) 2(3) (ex(<)∥x(>)p(−∥z∥2 )

2    VC Dimension, Pattern Counting, and Kernels (Theory) 15 pts (Harry)

VC dimension is an important tool in theoretically guaranteeing the efficacy of various ML models.   In this problem,  we  examine  the VC  dimension of the  hypothesis  space of linear models.   We  then  show a generalization that allows us to calculate how well a linear model can perform even past the point of shattering.

n(a)armo(Fin)d(d)e(t)ls(h)ewit(V)h(C)ou(di)t(m)a(e)co(nsi)n(o)st(n)a(o)n(f)ttt(h)e(e)rm(hy)pP(o)ro(th)ve(esi)syo(s)u(p)r(a)ca(e)nsw(Fd) {f : Rd  → {−1, 1}, f(x) = sgn(wTx), w ∈ Rd } of

Hints:  To  show that the VC dimension is k, you must show that there exists a set of k points that can be shattered, and you must also show that there exists no set of k + 1 points that can be shattered; Use the fact that any set of k + 1 vectors in a k-dimensional vector space must be linearly dependent.

(b)   We wish to show that, under some simple assumptions, a linear model in Fd  can classify n points in

exactly 2 Σk(d)0(1)（n 1）different ways no matter how the points are arranged. We will do this by showing that

this problem can be reduced to two other problems, one of which is much easier to solve.  We start with some definitions. Suppose that we have some d-dimensional vector space V.

. We define a hyperplane to be a (d − 1)-dimensional subspace in V.  For example, the set of hyperplanes

.  Given a set of n linear functions fj  : V → R, suppose that each fj  is not always zero.  Then, it can be shown that the set of solutions to fj (x) = 0 forms a hyperplane Sj  of V. We then say that the cells  of the arrangement of hyperplanes {S1 ,..., Sn } are the regions of V divided by the hyperplanes.  More

C(ri)g{(o)x(u)s,Va: fj(m)pj(se)t}⊂whe(V)r(i)e(s) s(a)gn(ce)d(ll)en(if)ot(a)e(n)s(d) the(onl)si(y)g(if)ntfu(he)n(r)ctio(e ex)n(is)ts some p ∈ {−1, 1}n  such that

.  The orthants of Rd  are a generalization of the concept of quadrants in R2  and octants in R3 .  For each p e {-1, 1}d , we define the orthant corresponding top as the set of vectors {x e Rd :  sgn(xj ) = pj  Aj}. Note that there are 2d  orthants in Rd.

.  Given a collection of n vectors  (xi  collection if and only if there exists a linear function f : V 一 R such that sgn(f(xi )) = pi  for each i.

. We say that a set of n vectors in V is in general position  if,  for all 0 三 k  三 d, any subset of k of the vectors is linearly independent.   Note that this is not the same as all  n vectors being linearly independent.   For  example,  {(1, 0), (0, 1), (1, 1)}  军  R2   is  in  general  position  but  it  is  not  linearly independent.

We now present the three problems we will be working with.  Suppose that n and d are fixed and n ≥ d ≥ 1.

.  The cell counting problem supposes that we have a collection of n hyperplanes in a d-dimensional real vector space V  (and corresponding linear functions  fj   :  V  一 R).   Then, the problem asks for the number of cells in the resulting arrangement. It can be proven using recursion that there at most

C(n,d) = 2

cells, but you may use this result directly.

.  The orthant intersection problem supposes that we have a d-dimensional subspace S in Rn.  Then, the problem asks for the number of orthants of Rn  that S intersects.

.  The pattern counting problem supposes that we have n vectors in Rd  in general position, and the problem asks for the number of distinct patterns of the set of vectors.

We now show that we can reduce the pattern counting problem to the orthant intersection problem, and that we can reduce the orthant intersection problem to the cell counting problem.  Note that when you reduce problem A to problem B, you must show a correspondence between the answer to A and the answer to B , and you must show that the assumptions and conditions of B are satisfied.  This way, you can cite the answer to B to solve A.

1.  Given that S intersects at least one orthant, prove that the answer to the orthant intersection problem is at most C(n,d) by reducing it to the cell counting problem.

Hints:   Let  V  =  S,  and  consider  the  linear  mappings  fj    :  S  一  R  where  fj (x)  =  ej(T)x  for  each

j = 1,..., n; Make sure to show that each fj  is not always zero.

2.  Prove that the answer to the pattern counting problem is at most C(n,d) by reducing it into the orthant intersection problem.  Make sure to show that the subspace you construct has dimension d and that it intersects at least one orthant.

Hints:  Since the patterns  correspond to the outputs of the dot product of each point with a given weight vector, try consolidating the dot products into one matrix multiplication; Recall the relation- ship between the column space of a matrix and its rank.

3.  (Optional, no points) Let C(n,d) be the least upper bound to the solution of the cell counting problem over all choices of n hyperplanes in d dimensions.  Prove that the formula C(n,d) = 2 Σk(d)0(1)（n 1）is indeed correct by showing that the recurrence

C(n,d) = C(n - 1, d) + C(n - 1,d - 1)

holds when n,d ≥ 2 with base cases C(1, d) = C(n,1) = 2.  Note that while we stated earlier that n ≥ d, the formula holds when n < d also.  This problem is not for points  (bonus or otherwise) and will not be graded, it is just for fun.

If we are more careful with our math, then we can actually show that the answer to the pattern counting problem is  exactly  C(n,d)  (try  to prove this!).   Furthermore,  if we relax the assumption of the pattern counting problem so that the vectors need not be in general position, then the number of patterns is still bounded above by C(n,d). We can now analyze some consequences of this result.

4.  Use the fact above to give a short alternative proof for the VC dimension of Fd.

Hints:  Use the fact thatΣk(m)) = 2m ; Recall that a set of m points is shattered if the number of

patterns of the set of points is 2m .

5.  Suppose that d is held constant.  What is the Big-O growth rate of C(n,d) with respect to n when n ≥ d? What does this say about the efficacy of linear models on (possibly very unrealistic) datasets with a large number of points?

h(c)t w(S)e(u)have(ppose)som(tha)e(t) n(w)o(e)nli(h)ne(av)a(e)ra ke(d)r(a)n(t)e(a)l(s)ek(t) it(x) rres(}ni=)ponding(1 where) R(xi)HS(R)dk(y)i  h(1)a()l(d)et(n) ℓ>: 2a R(su)b(p)e(p)a(os)n(e)

arbitary loss function, and let Ω : R → R be nondecreasing.  By the Representer Theorem, we know that minimizing the empirical cost Σ ℓ(f(xi ), yi ) + Ω(||f||) over Hk  is equivalent to minimizing the empirical cost over the set of linear functions Sk  = {f ∈ Hk : f = Σ αik(xi , · ),αi  ∈ R}.  For a given x ∈ Rd , what is the dimension of the vector (k(x1 , x), k(x2 , x),..., k(xn , x))?  Referencing (b), why does this suggest that the dataset is more likely to be separable using the kernel trick with an SVM as opposed to simply using an SVM directly?

3    Logistic Regression, Kernels, and Optimization (Theory) 10 pts (Allan)

reg(Let)utic(b)re(e)gr(a)e(s)s(e)si(t)ramet(wher)e(e)rxθ(i) ,wher(∈ Rd)e w(fo)e(r) wa(all)n(i) to(an)fi(d)nd(yi) an(∈) f({)θ−a(1)t} minimize(. Consid)s(e)t(r)h(t)e(h)l(e)os(l)s(2)

function:

 ln(1 + exp( −yi (fθ (xi ))) + λ∥fθ ∥H(2)

where fθ (x) is of the form θTx, and ∥fθ ∥H(2) = θT θ .

1.  Let H be the reproducing kernel Hilbert space that corresponds to the above l2  regularized logistic regression. Using the representer theorem, what is the form of the optimal predictive function?

2.  closely(Define) r(t)elated t(he funct)o(io)th(n)e(g) fol(as)lo(g)p(l)o(e)pti(xp)z(ζ)on proble(It turns)m:(ou)t that l2  regularized logistic regression is

ω(m)ζ(n)  ∥ω∥2 + C g(ζi )

subject to:

yi (ωT xi ) ≥ ζi , ∀i

where C > 0 is a constant.

Derive the dual formulation of this problem (you are not required to solve the problem, just state it). You should simplify the dual formulation so that it only depends on α, the yi ’s and xi ’s and C.

4    Attention and Convolution (Coding) 10 pts (Jon)

In this question, we will use the PyTorch framework to explore some properties of self-attention and some connections between self-attention and convolution1 .  First, we define the notion of a  “similarity metric”, which can be thought of as the opposite of a distance metric.  Formally, we call a function s : Rd ×d  → R a similarity metric if, for any x, y, z ∈ Rd :

1.  s is bounded above by some value b:  s(x, y) ≤ b.

2.  The similarity between an object and itself is the maximum similarity possible:  s(x, x) = b

3.  The similarity between two distinct objects is not the maximum similarity: x  y  =⇒ s(x, y) < b

4.  Similarity is symmetric: s(x, y) = s(y, x)

(a)   When learning about convolution, you may have learned that it is similar to template matching, where we find the similarity between a template and an image at each location.  In the first part of this problem, we will use the PyTorch package to visually explore whether convolution is computing a similarity function. First, recall the definition of convolution.  For an input matrix Z ∈ Rdin ×hin ×win    and a learned tensor of dout  convolutional filters K ∈ Rdout ×din ×hkernel ×wkernel , the output of a simple 2 dimensional convolution at position h,w for filter j is:

din   hkernel wkernel

(Z ∗ K)j,h,w  =         kj,a,b,cza,h+b−⌊hkernel/2⌋,w+c−⌊hkernel/2⌋ ,                            (1)

where the ∗ operator denotes convolving the first tensor with the second. For simplicity, in this problem we will consider convolution with hkernel  = wkernel  = 1, simplifying Equation 1 to

din

(Z ∗ K)j,h,w  =  kj,a,1 , 1 za,h,w                                                                                      (2)

We will also consider din   =  3  to  be the  RGB representation of a pixel at each location,  allowing easy visualization. The starting notebook available at this link provides an input tensor and a kernel tensor.  Use this starting notebook to:

1. Visualize the provided input tensor using Matplotlib’s imshow function.  Additionally, visualize each filter in the given “kernels” tensor as a separate subplot in one figure. Note that PyTorch and Matplotlib follow different conventions around the semantics of each axis in a tensor.  In PyTorch, an image is represented with the channel dimension (e.g., RGB) first, followed by height and width. In Matplotlib, the convention is height and width followed by channel.  To display torch tensors using matplotlib, you will need to reorder the axes using torch.permute such that the channel dimension comes last rather than first. Note that the color of each filter appears in the input tensor.

2.  Use the  PyTorch  function torch.nn.functional.conv2d to  convolve the given  input tensor with the given kernels. This should produce an output tensor in Rdout ×hin ×win . Display the activation map for each kernel as a subplot of one plot, i.e., produce dout  subplots of shape hin  × win. Based on these visualizations, you should notice that the entries in these matrices are not produced by a similarity

function. State which of the rules for similarity functions is violated and how you know.

3.  Let’s take a moment to consider something that is  a similarity function.  For two vectors x, y  ∈ Rd , the cosine similarity between x and y is defined to be:

CosSim(x, y) := cos(θ(x, y)),                                                     (3)

where θ : Rd ×d  → [0, 2π) is a function that gets the angle between two vectors.  Prove that CosSim is a similarity metric. Hint: θ is a distance metric.

4. Implement CosSim using a processing step on Z and K and torch.nn.functional.conv2d; that is, perform

a transformation T on Z and K such that (Z(¯) ∗ K(¯))j,h,w  computes a cosine similarity, where Z(¯) = T(Z)

andK(¯) = T(K). Display the activation map for each kernel.  Do the activation maps reflect a similarity

function? What is the difference between what you just implemented and a normal convolution?  Hint: Recall that xTy = ∥x∥2 ∥y∥2 cos(θ(x, y)).

(b)   We now attend to attention.  Recall the definition of dot product attention as computed in “Attention is All You Need”. For matrices Q, K, V ∈ Rwin ×din , we have

Attention(Q, K, V) := softmax V.                                                (4)

In the simplest form of self-attention, an input matrix Z ∈ Rwin ×din   is passed as all three arguments, i.e.

SimpleSelfAttention(Z) := Attention(Z, Z, Z) = softmax  Z.

1.  Note that you were given an input image in Rdin ×hin ×win , which does not quite line up with the dimensions expected for attention.   Flatten  the given input into a matrix of shape  (din ,  hin win ), transpose the resulting matrix to shape  (hin win ,  din ),  and  use it to compute  ZZT . Visualize the resulting matrix with imshow.  Based on this visualization, could the entries in the resulting matrix be produced by a similarity function?  State whether one of the rules for similarity functions is violated and how you know.

2.  Compute softmax  , and visualize the resulting matrix.  Based on this visualization, could the entries in this matrix be produced by a similarity function?  State whether a rule for similarity metrics is violated and how you know.

l1/∥0(z:) , 1 ∥2      1/∥z:(0) 2 ∥2      ...(...)                 0(0)           」                                                   T

[      0(.)                0          ...    1/∥z:in  ∥2l

ize the resulting matrix.  Based on this visualization, could the entries in this matrix be produced by a similarity function?  State whether one of the rules for similarity functions is violated and how you know.

4.  Based on the prior questions, you can see a connection between attention and convolution.  Implement the function f(Z) :=  using a convolution; reshape the output to a matrix of the appropriate size, and visualize the result. Hint: Recall that  ∈ Rwin hin ×win hin    and (Z ∗ K) ∈ Rdout ×hin ×win . How many convolutional kernels will you need to make these dimensions match?

5    K-Means and GMM (Coding) 15 pts (Yiyang)

In this problem,  we will explore the  Gaussian Mixture Model  and K-Means clustering  algorithm using the mall customers dataset.  This dataset consists of 200 samples with two features:  annual  income and

spending  score.  Note: Before doing clustering for the dataset, please use the MinMaxScalar to normalize the entire dataset.  Since there is no train and test split in this problem, there is no need to worry about data leakage. Please set up the random seed as 42 to keep the reproducibility of your result.

For the GMM model, suppose we assume that the dataset follows a Gaussian Mixture Model density in two-dimensional feature space, which we wrote as

g(x) = ωkgk (x)

where gk  is the normal distribution distribution with mean µk  and 2 × 2 covariate matrix Σk  for each class k = 1, 2, ··· K , K is total number of classes, and ωk   ≥ 0 is the weight of each class whereΣ ωk  = 1. Here {µk ,ωk Σk } are unknown parameters, and we would like to fit this mixture model.

As we have learned in class, the log-likelihood of the data is

l(µk ,ωk ,σ 2 ) = log 

For the Expectation step, it computes the responsibility of xi  for class k for the tth  step as:

r =       ωk,tgk,t (xi )       

where gm,t  = N(µm , Σm ), m = 1, ··· K

For the maximization step, it computes the weighted means and covariances as:

µk,t  =  , Σk,t  = Σ rk)(xi − µk,t )T

and the updated weights for gk,t (x) as

ωk,t  =

Hint:  When updating the covariate matrix, remember to add a regularizer to avoid making it a singular matrix. For example, you can add a matrix 10 −6 · I2×2  each time when updating Σk,t.

(a)[Gaussian Mixture Model]    Based on the formulas for the EM algorithm above, please implement this GMM algorithm in Python from scratch, The arguments of your function are the number of clusters K, the maximum number of iterations max iter, the tolerance of log-likelihood differences between two iterations tol. You are allowed to use any functions in numpy and scipy packages to implement the GMM Algorithm (you might need scipy.stats.multivariate normal.pdf() to help you generate the Probability density function of gk,t (xi )). You are allowed to use pandas to load the dataset and sklearn package for min-max scaling the dataset.  Set the initial weight of each class ωk,0  =  sampled point in the dataset, and the initial covariates matrix as 0 .01I2×2  to ensure reproducibility, where I2×2  is an identity matrix.   Set the default maximum iteration number as  100, and tol as  10−4 .   After implementing the GMM Algorithm, please answer the following questions:

1.  Set up K = 1 to 10, and plot the relationship between K and the negative log-likelihood of the dataset. Based on the plotted graph, Can you select a proper K for this dataset?

2.  Using the proper K you selected, train your GMM model based on the selected K, and plot the scatter plot of the dataset as well as the density estimation for this Gaussian mixture model.  You can find more information on how to draw the density estimation for a Gaussian Mixture in the scikit-learn document.   The  score samples  function  in Gaussian Mixture computes the log-likelihood of each sample. Hint: when you update the covariate matrix, make sure you add a small regularization matrix