Machine Learning Homework

HW 2

2.1

$L(x)=\|Ax\|_2^2-\lambda (\|x\|_2^2-1),\; A\in \R^{n\times n},\, x\in \R^n$ 求 $\frac{\partial L}{\partial x}$

$$\begin{aligned} \frac{\partial L}{\partial x} &= \frac{\partial [(Ax)^TAx-\lambda x^Tx]}{\partial x}\\ &=2AA^Tx-2\lambda x \end{aligned}$$

2.2

$L(x)=\|V-WH\|_F^2,\,V\in \R^{m\times n},\,W\in \R^{m\times k},\,H\in \R^{k\times n},\,$ 求 $\frac{\partial L}{\partial W},\,\frac{\partial L}{\partial V}$

$$\begin{aligned} \frac{\partial L}{\partial W} &=\frac{\partial \mathrm{tr}((V-WH)^T(V-WH))}{\partial W}\\ &=-2VH^T+2WHH^T \end{aligned}$$

$$\frac{\partial L}{\partial V} = -2V-2WH$$

2.3

let $f=X^TAX$

$$\begin{aligned} df &= d (X^TAX)\\ &=d \mathrm{tr}(X^TAX)\\ &=\mathrm{tr}(X^TA^TdX + X^T A dX) &=\mathrm{tr}(X^T(A+A^T)dX) \end{aligned}$$

$$\frac{\partial}{\partial X}\mathrm{tr}(X^TAX)=X^T(A+A^T)$$

HW 3

3.1 Logits on Multi-Classification

paramater space: $\theta = \{w_i,b_i\}\; i=1,\ldots,n$ , samples: $X=\{x_1,\ldots,x_n\}$ , labels: $Y=\{y_1,\ldots,y_n\}$, $y_i\in y = \{1,\ldots,K\},\;K$ number of classes.

$$\ell(\theta) = \sum_{i=1}^n \log p(y_i|x_i;\theta)\\ p(y_i|x_i;\theta) = \prod_{j=1}^K p(y_i=j)^{\mathbb I(y_i=j)}\\ p(y=j|x) = \frac{\exp(w_j^Tx+b)}{1+\sum_{k=1}^K\exp(w_k^Tx+b)}\qquad j=1,\ldots,K-1\\ p(y=K|x) = \frac{1}{1+\sum_{k=1}^{K-1}\exp(w_k^Tx+b)}$$

plug them in:

$$\begin{aligned} \ell(\theta) &= \sum_{i=1}^n\sum_{j=1}^K\mathbb I(y_i=j) \log p(y_i = j|x_i;\theta)\\ &= \sum_{i=1}^n\left(\sum_{j=1}^{K-1}\mathbb I(y_i=j) \log \frac{\exp(w_j^Tx_i+b)}{1+\sum_{k=1}^{K-1}\exp(w_k^Tx_i+b)}+\mathbb I(y_i=K) \log \frac{1}{1+\sum_{k=1}^{K-1}\exp(w_k^Tx_i+b)}\right) \end{aligned}$$

Using the softmax function:

$$p(y=j|x)=\sigma_j (z) = \frac{\exp{(z_j)}}{\sum_{k=1}^{K}\exp{(z_k)}}$$

$$\begin{aligned} \ell(\theta) &= \sum_{i=1}^n\sum_{j=1}^K\mathbb I(y_i=j) \log \frac{\exp{(z_j^{(i)})}}{\sum_{k=1}^{K}\exp{(z_k^{(i)})}}\\ &= \sum_{i=1}^n\sum_{j=1}^K\mathbb I(y_i=j) \log \frac{\exp{(w_j^Tx_i+b)}}{\sum_{k=1}^{K}\exp{(w_k^Tx_i+b)}} \end{aligned}$$

Derivatives: note $p_i = p(y_i=j|x_i; \theta)=\sigma_j (z^{(i)})$

$$\begin{aligned}\frac{\partial p_i}{\partial z_j} &=\begin{cases} p_i(1-p_j) & i=j\\ -p_ip_j &i\neq j\end{cases} \\ &=p_i(\mathbb I(i=j)-p_j)\end{aligned}$$

$$\frac{\partial z_k}{\partial w_k} = x \qquad \frac{\partial z_k}{\partial b} = 1$$

$$\begin{aligned}\frac{\partial \ell}{\partial z_k} &=\sum_{i=1}^n\sum_{j=1}^K\mathbb I(y_i=j) \frac{1}{p_i}p_i(\mathbb I(i=k)-p_k)\\ &=\sum_{i=1}^n\sum_{j=1}^K\mathbb I(y_i=j) (\mathbb I(i=k)-p_k)\\ &=\sum_{j=1}^K\left(\mathbb I(y_k=j)(1-p_k)-\sum_{i\neq k}\mathbb I(y_i=j)p_k\right)\\ &= \sum_{j=1}^K \left(\mathbb I(y_k=j)-\sum_{i=1}^K\mathbb I(y_i=j)p_k\right)\\ &=\sum_{j=1}^K(\mathbb I(y_k=j)-p_k)\\ &= -Kp_k +1 \end{aligned}$$

$$\nabla_{w_k}\ell = \frac{\partial \ell}{\partial z_k}\frac{\partial z_k}{\partial w_k} = (-Kp_k +1)x\\ \nabla_{b}\ell = \frac{\partial \ell}{\partial z_k}\frac{\partial z_k}{\partial w_k} = -Kp_k +1$$

def loss_function:
    Cross Entropy Loss

def compute_grad:
    return grad_W, grad_b
def gradient_descent:
    while stop == False
        W ,b = compute_grad
        do descent
        if |newpoint - oldpoint| < eps:
            stop = True
    return result

def predict:
    return index of softmax(gradient_descent).max

3.2 Multi-Class LDA

Suppose dataset $\{(\bold x_i,y_i)\}\quad y_i\in y=\{1,\ldots,K\}$ . Class $k$ have $N_k$ samples $X_k$ .
Step 1: Pre-Computing
Mean Vectors:

$$\mu_k = \frac{1}{N_k}\sum_{i=1}^{N_k}x_i$$

$N_k$ is number of samples in class $k$

$$\mu = \frac{1}{N}\sum_{i=1}^{N}x_i$$

$N$ is the total number of samples.

Within-Class Scatter Matrix:

$$S_k = \sum_{x\in X_k}(x-\mu_k)(x-\mu_k)^T$$

$$S_W=\sum_{k=1}^K S_k$$

Between-Class Scatter Matrix

$$S_B = \sum_{k=1}^{K}N_k(\mu_k-\mu)(\mu_k-\mu)^T$$

Step 2: Solve Generalized Eigenvalue Problem

$$S_W^{-1}S_B \bold w=\lambda \bold w$$

Use Numerical Methods.

Step 3
Select $d'\leq N-1$ Top Eigenvectors to form transformation matrix $W$ , projecting data to lower-dimensional space.

$$Z=W^TX$$

Step 4
Apply any classification method that suits lower dimensions.

3.3 In Multi-Class LDA, proof: $\mathrm{rank}(S_W^{-1}S_B)\leq K-1$

$$\mathrm{rank}(S_W^{-1}S_B) \leq \min \{\mathrm{rank}(S_W^{-1}),\mathrm{rank}(S_B)\}$$

for the Between-Class Scatter Matrix $S_B$ :

$$\begin{aligned} \mathrm{rank}(S_B) &= \mathrm{rank}\left(\sum_{k=1}^{K}N_k(\mu_k-\mu)(\mu_k-\mu)^T\right)\\ &\leq \sum_{k=1}^{K}\mathrm{rank}\left((\mu_k-\mu)(\mu_k-\mu)^T\right) \end{aligned}$$

notice that:

$$\mathrm{rank}\left((\mu_k-\mu)(\mu_k-\mu)^T\right) \leq 1$$

$$\mu = \frac{1}{N}\sum_{k=1}^K\mu_k N_k$$

$$\sum_{k=1}^KN_k(\mu-\mu_k)=0$$

Thus vectors $\{\mu-\mu_k\}$ are linear correlated. There is atmost $K-1$ vectors that are linear independent. There must be at least one matrix $(\mu_j-\mu)(\mu_j-\mu)^T$ that has $\mathrm{rank}=0$. Therefore:

$$\mathrm{rank}(S_W^{-1}S_B)\leq \mathrm{rank}(S_B) \leq K-1$$

3.4 Convexity of functions

Definition: for all $x_1, x_2\in D,\; \lambda \in (0,1)$ , there is:

$$f(\lambda x_1+(1-\lambda x_2))\leq \lambda f(x_1)+(1-\lambda) f(x_2)$$

$$y=\frac{1}{1+\exp(w^Tx+b)}$$

$$\nabla_w y = \frac{-x e^{-w^Tx+b}}{(1+e^{-w^Tx+b})^2}$$

$e= e^{-w^Tx+b}$

$$\begin{aligned}\nabla_w^2 y &= \frac{(1+e)^2 xx^Te -xe 2(1+e)e x^T}{(1+e)^4}\\ &=\frac{(-e^3+e)xx^T}{(1+e)^4} \end{aligned}$$

The Hessian could be negative defintie, therefore Convexity is not generalized.

$$\ell(\beta) = \sum_{i=1}^m \left( -y_i\beta^T\hat x _i + \ln (1+e^ {\beta^T\hat x_i})\right)$$

$$\nabla_\beta \ell = \sum_{i=1}^m -y_i\hat x_i +\frac{e}{1+e}$$

$e=e^ {\beta^T\hat x_i}$

$$\begin{aligned}\nabla_\beta^2 \ell &= \sum_{i=1}^m \frac{\hat x_i\hat x_i^Te(1+e)-e^2 \hat x_i\hat x_i^T}{(1+e)^2}\\ &=\sum_{i=1}^m \frac{\hat x_i\hat x_i^T}{(1+e)^2} \end{aligned}$$

This Hessian is semi-positive definite, Convexity proven.

HW 4

4.1