ML-As-1

Vector Calculus Review (15 pts)

$a.Show\frac{\partial }{\partial x}(x^{T}c)=c^T$

$\frac{\partial {\mathrm{\Sigma }}_{i=1}^{i=n}{x}^T{c}_i}{\partial x}=[\frac{\partial {\mathrm{\Sigma }}_{i=1}^{i=n}{x}^T{c}_1}{\partial x_1},\frac{\partial {\mathrm{\Sigma }}_{i=1}^{i=n}{x}^T{c}_2}{\partial x_2},\dots ,\frac{\partial {\mathrm{\Sigma }}_{i=1}^{i=n}{x}^T{c}_n}{\partial x_n}]=[c_1,c_2,\dots ,c_n]=c^T$

$b.Show\frac{\partial }{\partial x}||x|{|}_2^2=2x^T$

$\frac{\partial {\mathrm{\Sigma }}_{i=1}^{i=n}{x}_i^2}{\partial x}=[\frac{\partial {\mathrm{\Sigma }}_{i=1}^{i=n}{x}_i^2}{\partial x_1},\frac{\partial {\mathrm{\Sigma }}_{i=1}^{i=n}{x}_i^2}{\partial x_2},\dots ,\frac{\partial {\mathrm{\Sigma }}_{i=1}^{i=n}{x}_i^2}{\partial x_n}]=[2x_1,2x_2,\dots ,2x_n]=2x^T$

$c.Show\frac{\partial }{\partial x}(Ax)=A$

$$\frac{\partial }{\partial x}(Ax)=[\frac{\partial Ax}{\partial x_1},\frac{\partial Ax}{\partial x_2},\dots ,\frac{\partial Ax}{\partial x_n}]$$$$=\left[\begin{array}{cccc}\frac{\partial (A_{11}{x}_1+A_{12}{x}_2+\cdots +A_{1n}{x}_n)}{\partial x_1}& \frac{\partial (A_{11}{x}_1+A_{12}{x}_2+\cdots +A_{1n}{x}_n)}{\partial x_2}& \dots & \frac{\partial (A_{11}{x}_1+A_{12}{x}_2+\cdots +A_{1n}{x}_n)}{\partial x_n}\\ \frac{\partial (A_{21}{x}_1+A_{22}{x}_2+\cdots +A_{2n}{x}_n)}{\partial x_1}& \frac{\partial (A_{21}{x}_1+A_{22}{x}_2+\cdots +A_{2n}{x}_n)}{\partial x_2}& \dots & \frac{\partial (A_{21}{x}_1+A_{22}{x}_2+\cdots +A_{2n}{x}_n)}{\partial x_n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{\partial (A_{n1}{x}_1+A_{n2}{x}_2+\cdots +A_{nn}{x}_n)}{\partial x_1}& \frac{\partial (A_{n1}{x}_1+A_{n2}{x}_2+\cdots +A_{nn}{x}_n)}{\partial x_2}& \dots & \frac{\partial (A_{n1}{x}_1+A_{n2}{x}_2+\cdots +A_{nn}{x}_n)}{\partial x_n}\end{array}\right]$$$$=\left[\begin{array}{cccc}{A}_{11}& A_{12}& \dots & A_{1n}\\ A_{21}& A_{22}& \dots & A_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ A_{n1}& A_{n2}& \dots & A_{nn}\end{array}\right]=A$$

$d.Show\frac{\partial }{\partial x}(x^{T}Ax)=x^T(A+A^T)$

$$\frac{\partial }{\partial x}(Ax)=[\frac{\partial x^{T}Ax}{\partial x_1},\frac{\partial x^{T}Ax}{\partial x_2},\dots ,\frac{\partial x^{T}Ax}{\partial x_n}]$$$$={\left[\begin{array}{c}\frac{\partial }{\partial x_1}(x_1(A_{11}{x}_1+A_{12}{x}_2+\cdots +A_{1n}{x}_n)+x_2(A_{21}{x}_1+A_{22}{x}_2+\cdots +A_{2n}{x}_n)+\cdots +x_n(A_{n1}{x}_1+A_{n2}{x}_2+\cdots +A_{nn}{x}_n))\\ \\ \frac{\partial }{\partial x_2}(x_1(A_{11}{x}_1+A_{12}{x}_2+\cdots +A_{1n}{x}_n)+x_2(A_{21}{x}_1+A_{22}{x}_2+\cdots +A_{2n}{x}_n)+\cdots +x_n(A_{n1}{x}_1+A_{n2}{x}_2+\cdots +A_{nn}{x}_n))\\ \\ ⋮\\ \\ \frac{\partial }{\partial x_n}(x_1(A_{11}{x}_1+A_{12}{x}_2+\cdots +A_{1n}{x}_n)+x_2(A_{21}{x}_1+A_{22}{x}_2+\cdots +A_{2n}{x}_n)+\cdots +x_n(A_{n1}{x}_1+A_{n2}{x}_2+\cdots +A_{nn}{x}_n))\end{array}\right]}^T$$$$={\left[\begin{array}{c}2A_{11}{x}_1+(A_{12}+A_{21})x_2+\cdots +(A_{1n}+A_{n1})x_n\\ (A_{12}+A_{21})x_1+2A_{22}{x}_2+\cdots +(A_{2n}+A_{n2})x_n\\ ⋮\\ (A_{1n}+A_{n1})x_1+(A_{2n}+A_{n2})x_2+\cdots +2A_{nn}{x}_n\end{array}\right]}^T$$$$=\left[\begin{array}{c}{A}_{11}{x}_1+A_{12}{x}_2+\cdots +A_{1n}{x}_n\\ A_{21}{x}_1+A_{22}{x}_2+\cdots +A_{2n}{x}_n\\ ⋮\\ A_{n1}{x}_1+A_{n2}{x}_2+\cdots +A_{nn}{x}_n\end{array}\right]+\left[\begin{array}{c}{A}_{11}{x}_1+A_{21}{x}_2+\cdots +A_{n1}{x}_n\\ A_{12}{x}_1+A_{22}{x}_2+\cdots +A_{n2}{x}_n\\ ⋮\\ A_{1n}{x}_1+A_{2n}{x}_2+\cdots +A_{nn}{x}_n\end{array}\right]$$$$=x^T(A+A^T)$$

$e.Underwhatconditionisthepreviousderivativeequalto2x^{T}A?$

When $A=A^T$, $A$ is a symmetric matrix.

Bayes’ Rule (10 pts)

Assume the probability of a certain disease is $0.01$. The probability of test positive given that a person is infected with the disease is $0.95$ and the probability of test positive given the person is not infected with the disease is $0.05$.

(a) Calculate the probability of test positive.

• $P(D)=0.01$: The probability that a person has the disease.
• $P(T^{+}|D)=0.95$: The probability of testing positive given that the person has the disease.
• $P(T^{+}|\mathrm{\neg }D)=0.05$: The probability of testing positive given that the person does not have the disease.
• $P(\mathrm{\neg }D)=1-P(D)=0.99$: The probability that a person does not have the disease.

$$P(T^{+})=P(T^{+}|D)P(D)+P(T^{+}|\mathrm{\neg }D)P(\mathrm{\neg }D)$$$$P(T^{+})=(0.95)(0.01)+(0.05)(0.99)=0.059$$

(b) Use Bayes’ Rule to calculate the probability of being infected with the disease given that the test is positive.

$$P(D|T^{+})=\frac{P(T^{+}|D)P(D)}{P(T^{+})}=\frac{(0.95)(0.01)}{0.059}=0.161$$

Gradient Descent Mechanics (20 pts)

Gradient descent is the primary algorithm to search optimal parameters for our models. Typically, we want to solve optimization problems stated as

$$\underset{\theta \in \mathrm{\Theta }}{min}\mathcal{L}(f_{\theta },\mathcal{D})$$

where $\mathcal{L}$ are differentiable functions. In this example, we look at a simple supervised learning problem where given a dataset $\mathcal{D}=\{(x_i,y_i){\}}_{i=1}^n$, we want to find the optimal parameters $\theta$ that minimizes some loss. We consider different models for learning the mapping from input to output, and examine the behavior of gradient descent for each model.

a

The simplest parametric model entails learning a single-parameter constant function, = 𝜃. where we set ${\hat{y}}_i=\theta$. We wish to find

$${\hat{\theta }}_{const}=mi{n}_{\theta \in \mathbb{R}}\mathcal{L}(f_{\theta },\mathcal{D})=mi{n}_{\theta \in \mathbb{R}}\frac{1}{N}{\mathrm{\Sigma }}_{i=1}^N(y_i-\theta {)}^2$$

i. What is the gradient of $\mathbb{L}$ with respect to $\theta$?

$$\mathcal{L}(\theta )=\frac{1}{N}\sum _{i=1}^N(y_i-\theta {)}^2$$$$\frac{\partial }{\partial \theta }\mathcal{L}(\theta )=\frac{1}{N}\sum _{i=1}^{N}2(y_i-\theta )(-1)$$$$\frac{\partial }{\partial \theta }\mathcal{L}(\theta )=-\frac{2}{N}\sum _{i=1}^N(y_i-\theta )$$

ii. What is the optimal value of $\theta$?

when

$$-\frac{2}{N}\sum _{i=1}^N(y_i-\theta )=0$$$$\sum _{i=1}^N(y_i-\theta )=0$$$$\sum _{i=1}^N{y}_i=N\theta$$$$\theta =\frac{1}{N}\sum _{i=1}^N{y}_i$$

iii. Write the gradient descent update.

$${\theta }^{(t+1)}={\theta }^{(t)}-\eta {\mathrm{\nabla }}_{\theta }\mathcal{L}({\theta }^{(t)})$$$${\theta }^{(t+1)}={\theta }^{(t)}+\eta \frac{2}{N}\sum _{i=1}^N(y_i-{\theta }^{(t)})$$

Where $\eta$ is the learning rate.

iv. Stochastic Gradient Descent (SGD) is an alternative optimization algorithm, where instead of using all N samples, we use single sample per optimization step to update the model. What is the contribution of each data-point to the full gradient update?

$${\mathrm{\nabla }}_{\theta }{\mathcal{L}}_i(\theta )=-2(y_i-\theta )$$

Thus, the gradient descent update for a single data point is:

$${\theta }^{(t+1)}={\theta }^{(t)}+\eta 2(y_i-{\theta }^{(t)})$$

In SGD, this single sample gradient update is used to update \theta after each data point.

b

Instead of constant functions, we now consider a single-parameter linear model $\widehat{y_i}(x_i)=\theta (x_i)$ where we search for $\theta$ such that

$$\hat{\theta }=mi{n}_{\theta \in \mathbb{R}}\frac{1}{N}{\mathrm{\Sigma }}_{i=1}^N(y_i-\theta x_i{)}^2$$

i. What is the gradient of $\mathbb{L}$ with respect to $\theta$?

$$\mathcal{L}(\theta )=\frac{1}{N}\sum _{i=1}^N(y_i-\theta x_i{)}^2$$$$\frac{\partial }{\partial \theta }\mathcal{L}(\theta )=-\frac{1}{N}\sum _{i=1}^{N}2(\theta x_i^2-y_i{x}_i)$$$$\frac{\partial }{\partial \theta }\mathcal{L}(\theta )=-\frac{2}{N}\sum _{i=1}^N{x}_i(y_i-\theta x_i)$$

ii. What is the optimal value of $\theta$?

when

$$-\frac{2}{N}\sum _{i=1}^N(\theta x_i^2-y_i{x}_i)=0$$$$\sum _{i=1}^N(\theta x_i^2)=\sum _{i=1}^N{y}_i{x}_i$$$$\theta =\frac{\sum _{i=1}^N{y}_i{x}_i}{\sum _{i=1}^N{x}_i^2}$$

iii. Write the gradient descent update.

$${\theta }^{(t+1)}={\theta }^{(t)}-\eta {\mathrm{\nabla }}_{\theta }\mathcal{L}({\theta }^{(t)})$$$${\theta }^{(t+1)}={\theta }^{(t)}+\eta \frac{2}{N}\sum _{i=1}^N(y_i{x}_i-{\theta }^{(t)}{x}_i^2)$$

Where $\eta$ is the learning rate.

iv. Do all points get the same vote in the update? Why or why not?

No, not all points get the same vote in the gradient update.

$${\mathrm{\nabla }}_{\theta }\mathcal{L}(\theta )=-\frac{2}{N}\sum _{i=1}^N{x}_i(y_i-\theta x_i)$$

Each data point is weighted by $x_i$ . If $x_i$ is large, that data point will have a larger influence on the gradient (and thus on the update), Whereas if $x_i$ is small, the influence will be smaller.

MAP Interpretation of Ridge Regression (20 pts)

Consider the Ridge Regression estimator

$$arg{min}_w||Xw-y|{|}^2+\lambda ||w|{|}^2$$

We know this is solved by

$$\hat{w}=(X^T+\lambda I{)}^{-1}{X}^{T}y$$

One interpretation of Ridge Regression is to find the Maximum A Posteriori (MAP) estimate on $w$, the parameters, assuming that the prior of $w$ is $N(0,I)$ and that the random $Y$ is generated using

$$Y=Xw+\lambda N$$

Note that each entry of vector $N$ is zero-mean, unit-variance normal. Show that $\hat{w}=(X^T+\lambda I{)}^{-1}{X}^{T}y$ is indeed the MAP estimate for $w$ given an observation on $Y=y$ .

---

The MAP estimate maximizes the posterior distribution:

$$w^{MAP}=\arg \underset{w}{max}\log P(w|Y)$$

From Bayes' rule:

$$P(w|Y)=\frac{P(Y|w)}{P(Y)}P(w)\propto P(Y|w)P(w)$$$$w^{MAP}=\arg \underset{w}{max}\log P(w|Y)=\arg \underset{w}{max}(\log P(Y|w)+\log P(w))$$$$f(x|\mu ,{\sigma }^2)=\frac{1}{\sqrt{2\pi {\sigma }^2}}\exp (-\frac{(x-\mu {)}^2}{2{\sigma }^2})$$

Substituting the likelihood and prior:

$$w^{MAP}=-\frac{1}{2{\sigma }^2}\parallel Xw-Y{\parallel }^2-\frac{1}{2{\nu }^2}\parallel w{\parallel }^2\lambda =\frac{{\sigma }^2}{{\nu }^2}$$$$\because \sigma =1\therefore w^{MAP}=-\frac{1}{2{\sigma }^2}\parallel Xw-Y{\parallel }^2-\frac{\lambda }{2}|w{|}^2$$

Maximizing this expression with respect to $w$ is equivalent to minimizing the following expression:

$$\arg \underset{w}{min}\parallel Xw-Y{\parallel }^2+\lambda \parallel w{\parallel }^2$$$$\therefore \hat{w}=(X^T+\lambda I{)}^{-1}{X}^{T}y$$

Programming (35 pts)

Task 1

# You should return your result. 

import numpy as np 

def insertSecond(a, b):
    return np.insert(a, 1, b)

assert np.array_equal(insertSecond(np.array([-5,-10,-12,-6]),5), np.array([-5, 5, -10, -12, -6]))
assert np.array_equal(insertSecond(np.array([1,2,3]),7), np.array([1, 7, 2, 3]))
assert np.array_equal(insertSecond(np.array([-5,-10,-12,-6]),8), np.array([ -5, 8, -10,-12, -6]))
assert np.array_equal(insertSecond(np.array([1,2,3]),12), np.array([1, 12, 2, 3]))

Task 2

import numpy as np 

def mergeArrays(a,b):
    return np.sort(np.unique(np.concatenate((a,b))))

# Test cases 
assert np.array_equal(mergeArrays(np.array([1,1,4,8,1]), np.array([2, 3])), np.array([1, 2, 3, 4, 8])) 
assert np.array_equal(mergeArrays(np.array([-5,-10,-10,-6]), np.array([-5, 8, -10, -12,-6])),np.array([-12, -10, -6, -5, 8]) )
assert np.array_equal(mergeArrays(np.array([1,1,6,8,1]), np.array([2, 3])), np.array([1, 2, 3, 6, 8]))

Task 3

import numpy as np
import matplotlib.pyplot as plt

# data to plot
n_groups = 5
men_means = (22, 30, 33, 30, 26)
women_means = (25, 32, 30, 35, 29)
alpha = 0.5

fig, ax = plt.subplots()
index = np.arange(n_groups)
bar_width = 0.4
opacity = 0.8

rects1 = plt.bar(index, men_means, bar_width,
alpha=0.5,
color='g',
label='Men')

rects2 = plt.bar(index + bar_width, women_means, bar_width,
alpha=0.5,
color='r',
label='Women')

plt.xlabel('Person')
plt.ylabel('Scores')
plt.title('Scores by person')
plt.xticks(index + bar_width / 2, ('G1', 'G2', 'G3', 'G4', 'G5'))
plt.legend()

plt.tight_layout()
plt.show()

Task 4

import pandas as pd


def setDataFrameZeros(df):
    rows = df.isin([0]).any(axis=1)
    cols = df.isin([0]).any(axis=0)
    df.loc[rows, :] = 0
    df.loc[:, cols] = 0
    return df

df1 = pd.DataFrame({'c1': [1, 4, 7], 'c2': [2, 0, 8], 'c3': [3, 6, 9]})
df2 = pd.DataFrame({'c1': [1, 0, 7], 'c2': [0, 0, 0], 'c3': [3, 0, 9]})
(df2.equals(setDataFrameZeros(df1)))

df1 = pd.DataFrame({'c1': [0, 3, 1], 'c2': [1, 4, 3], 'c3': [2, 5, 1], 'c4': [0, 2, 5]})
df2 = pd.DataFrame({'c1': [0, 0, 0], 'c2': [0, 4, 3], 'c3': [0, 5, 1], 'c4': [0, 0, 0]})
assert (df2.equals(setDataFrameZeros(df1)))

df1 = pd.DataFrame({'c1': [1, 4, 7], 'c2': [2, 0, 8], 'c3': [3, 6, 9]})
df2 = pd.DataFrame({'c1': [1, 0, 7], 'c2': [0, 0, 0], 'c3': [3, 0, 9]})
assert (df2.equals(setDataFrameZeros(df1)))

df1 = pd.DataFrame({'c1': [0, 3, 1], 'c2': [1, 4, 3], 'c3': [2, 5, 1], 'c4': [0, 2, 5]})
df2 = pd.DataFrame({
    'c1': [0, 0, 0],
    'c2': [0, 4, 3],
    'c3': [0, 5, 1],
    'c4': [0, 0, 0]
})
assert (df2.equals(setDataFrameZeros(df1)))