we described a kernel K(u, v) = ((u), (v)) as a function that allows us to compute inner prod- ucts in high dimensions efficiently. However, some functions K: Rd x Rd R are not valid kernels for any mapping Rd Re. While we can sometimes easily find the specific that proves K is a valid kernel, it is often easier to prove that K is a valid kernel without explicitly finding . To determine if there exists some mapping for which K is a valid kernel, we define the Gram matrix G for a kernel function K and a dataset u, ..., un Rd to be: [K(u, u) K(u2, u) K(u1, u2) K(u2, u2) ... K(u, un) ... K(u2, un) G== K(un, u1) K(un, u2) K(un, un)] K is a valid kernel if and only if G is symmetric and positive semidefinite for all possible datasets. Recall that a matrix M is positive semidefinite matrix if and only if a Ga > 0 for all a = Rn. (You may use this fact in your proofs, but it's not required). In this problem, you will prove that the polynomial kernel K(u,v) = (b(u, v) + c)d is a valid kernel function when b> 0, c> 0, and d Z+. a. Prove that the linear kernel K(u, v) = (u, v) is a valid kernel. b. Prove that if K is a valid kernel and b > 0, then K(u,v) = bK(u, v) is a valid kernel by showing that the Gram matrix of K is positive semidefinite. c. Prove that if K is a valid kernel and c 0, then K(u,v) = K(u, v) + c is a valid kernel. Hint: Let (u) be the mapping for K. How could you use (u) to construct another mapping, (u), for which K is a valid kernel? Ac d. It is also true that if K and K2 are valid kernels, then the product K(u,v) = K(u, v) K(u, v) is a valid kernel (you don't need to prove this). Use this fact and parts (a)-(c) to prove that the polynomialo kernel K(u, v) (b(u, v) + c)d is a valid kernel. =