Lecture 5: Optimization (Oxford machine learning)

background

Partial derivatives and gradient

$$f(\theta)=f(\theta_1,\theta_2)=\theta_1^2+\theta_2^2$$ $$\frac{\partial}{\partial\theta_1}f(\theta_1,\theta_2)=\lim_{\Delta\theta_1\rightarrow0}\frac{f(\theta_1+\Delta\theta_1,\theta_2)-f(\theta_1,\theta_2)}{\Delta\theta_1}$$ $$\frac{\partial f(\theta)}{\partial\theta_1}=2\theta_1 \\ \frac{\partial f(\theta)}{\partial\theta_2}=2\theta_2$$ $$\nabla J(\theta)=\begin{bmatrix}2\theta_1 \\ 2\theta_2\end{bmatrix}$$

Hessian

Suppose $f$ : $\mathbb{R}^n\rightarrow\mathbb{R}$ is a function taking as input a vector $x \in \mathbb{R}^n$ and outputting a scalar $f(x) \in \mathbb{R}$; if all second partial derivatives of $f$ exist and are continuous over the domain of the function, then the Hessian matrix $H$ of $f$ is a square $n\times n$ matrix, usually defined and arranged as follows:

$$H=\begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2 } & \cdots & \frac{\partial^2 f}{\partial x_n \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2 } & \cdots & \frac{\partial^2 f}{\partial x_n^2} \end{bmatrix}$$

use single equation: $H_{i,j}=\frac{\partial^2 f}{\partial x_i \partial x_j}$ In case above: $\frac{\partial}{\partial\theta_1}\left(\frac{\partial f(\theta)}{\partial \theta_1}\right)=\frac{\partial^2f(\theta)}{\partial\theta_1^2}=2 \\ \frac{\partial^2f(\theta)}{\partial\theta_2^2}=2 \\ \frac{\partial^2f(\theta)}{\partial\theta_1 \partial\theta_2}=\frac{\partial^2f(\theta)}{\partial\theta_2 \partial\theta_1}=0$ so, $H=\begin{bmatrix}2 & 0 \\ 0 & 2\end{bmatrix}$

Chain rule

$$Z=f(x(u,a),y(u,a))$$ $$\frac{\partial Z}{\partial u}=\frac{\partial Z}{\partial x}\frac{\partial x}{\partial u}+\frac{\partial Z}{\partial y}\frac{\partial y}{\partial u}$$

Linear regression

$$y_i=\theta_0+\theta_1x_i$$ $$J(\theta)=\sum_{i=1}^{n}(y_i-\theta_0-\theta_1x_i)^2+\delta^2\theta_1^2$$ $$\nabla J=\begin{bmatrix}\sum_{i=1}^{n}2(y_i-\theta_0-\theta_1x_i)(-1) \\ \sum_{i=1}^{n}2(y_i-\theta_0-\theta_1x_i)(-x_i)+2\delta^2\theta_1 \end{bmatrix}$$

Gradient vector

Let $\theta$ be an d-dimensional vector and $f(\theta)$ a scalar-valued function. the gradient vector of $f$ with respect to $\theta$ is:

$$\nabla_\theta f(\theta)= \begin{bmatrix} \frac{\partial f(\theta)}{\partial \theta_1} \\ \frac{\partial f(\theta)}{\partial \theta_2} \\ \vdots \\ \frac{\partial f(\theta)}{\partial \theta_n} \end{bmatrix}$$

Hessian matrix

Also Hessian matrix defined as

$$\nabla_\theta^2 f(\theta)$$

In offline learning, we have a batch of data $x_{1:n} = \{x_1,x_2,…,x_n\}$. We typically optimize cost function of the form

$$f(\theta)= f(\theta,x_{1:n})=\frac{1}{n}\sum_{i=1}^{n}f(\theta,x_i)$$

The corresponding gradient is

$$g(\theta)=\nabla_\theta f(\theta)=\frac{1}{n}\sum_{i=1}^{n}\nabla_\theta f(\theta,x_i)$$

we have the quadratic cost

$$f(\theta)=f(\theta,X,y)=(y-X\theta)^T(y-X\theta)=\sum_{i=1}^{n}(y_i-x_i\theta)^2$$ $$\nabla f(\theta)=-2X^Ty+2X^TX\theta$$ $$\nabla^2f(\theta)=2X^TX$$

Steepset gradient descent algorithm

One of the simplest optimization algorithms is called gradient descent or steepest descent. This can be written as follows: $\theta_{k+1}=\theta_k-\eta_kg_k=\theta_k-\eta_k\nabla f(\theta_k)$ where $k$ indexes steps of the algorithm, $g_k=g(\theta_k)$ is gradient at step $k$, and $\eta_k > 0$ is called the learning rate or step size.

For least squares

$$f(\theta)=f(\theta,X,y)=(y-X\theta)^T(y-X\theta)=\sum_{i=1}^{n}(y_i-x_i\theta)^2$$ $$\nabla f(\theta)=-2X^Ty+2X^TX\theta$$ $$\theta_{k+1}=\theta_k - \eta\left[-2X^Ty+2X^TX\theta_k\right] \\ \theta_{k+1}=\theta_k - \eta\left[-2\sum_{i=1}^{n}x_i^T(y_i-x_i\theta_k)\right]$$

Newton’s algorithm

The most basic second-order optimization algorithm. $\theta_{k+1}=\theta_k-H_K^{-1}g_k$ make a second-order Taylor series approximation of $f(\theta)$ around $\theta_k$:

$$f_{quad}(\theta)=f(\theta_k)+g_k^T(\theta-\theta_k)+\frac{1}{2}(\theta-\theta_k)^TH_k(\theta-\theta_k)$$ $$\nabla f_{quad}(\theta)=0+g_k+H_k(\theta-\theta_k)=0$$ $$\theta=\theta_k-H_k^{-1}g_k$$

For linear regression

$$f(\theta)=f(\theta,X,y)=(y-X\theta)^T(y-X\theta)=\sum_{i=1}^{n}(y_i-x_i\theta)^2$$ $$\nabla f(\theta)=-2X^Ty+2X^TX\theta$$ $$\nabla^2 f(\theta)=2X^TX$$ $$\begin{aligned} \theta&=\theta_k-H_k^{-1}g_k \\ & =\theta_k - (2X^TX)^{-1} [-2X^Ty+2X^TX\theta_k]\\ & =(X^TX)^{-1}X^Ty \end{aligned}$$

Newton CG algorithm

We can solve the linear system of equations $H_kd_k = -g_k$ for $d_k$ rather than computing $d_k=-H_k^{-1}g_k$ .

$$\begin{align} &\text{Newton CG Algorithm} \\\hline & 1 \ : \ \text{Initialize} \ \theta_0 \\ & 2 \ : \ for\ k =1,2,\dots \text{untill} \ \text{covergence} \ do\\ &3 \ : \ \qquad \text{Evaluate} \ g_k=\nabla f(\theta_k) \\ &4 \ : \ \qquad \text{Evaluate} \ H_k=\nabla^2 f(\theta_k) \\ &5 \ : \ \qquad \text{Solve} H_k d_k=-g_k\ \text{for} \ d_k \\ &6 \ : \ \qquad \text{Use line serch to find stepsize}\ \eta_k \ \text{along} \ d_k \\ &7 \ : \ \qquad \theta_{k+1}=\theta_k+\eta_k d_k \\\hline \end{align}$$

SGD(Stochastic gradient descent)

$$\nabla_\theta f(\theta)=\int\nabla_\theta f(X,\theta)P(x)dx \overset{\underset{\mathrm{want}}{}}{=} 0$$ $$\eta \times \mathbb{E}[\nabla f(x,\theta)]= 0 \times \eta = 0$$ $$\begin{align} \theta_{k+1}&=\theta_k - \eta\mathbb{E}[\nabla f(x,\theta)]+\eta\left[\mathbb{E}[\nabla f(x,\theta)-\nabla f(x^{(k)},\theta_k)\right] \\ &\approx \theta_k - \eta \frac{1}{n}\sum_{i=1}^{n}\nabla f(x^{(i)},\theta_k)\\ &\approx \theta_k - \eta \nabla f(x^{(k)},\theta_k) \end{align}$$ $$\theta_{k+1}=\theta_k-\eta\mathbb{E}[\nabla f]+\eta[\mathbb{E}[\nabla f]-\nabla f(x_k,\theta_k)]$$

위 수식에서 $\eta\mathbb{E}[\nabla f]$는 러닝을 위한 term이고 그 뒤의 $\eta[\mathbb{E}[\nabla f]-\nabla f(x_k,\theta_k)]$는 noise term이다.

Online learning with mini-batches

Batch

$$\theta_{k+1}=\theta_k + \eta\sum_{i=1}^{n}x_i^T(y_i-x_i\theta_k)$$

Online

$$\theta_{k+1}=\theta_k + \eta x_k^T(y_k-x_k\theta_k)$$

mini-batch

$$\theta_{k+1}=\theta_k + \eta\sum_{i=1}^{20}x_i^T(y_i-x_i\theta_k)$$

이 과정에서 train과 test의 error function을 계속해서 관찰해야 한다.

만약 train의 error는 줄어드는데 test의 error는 증가할 경우 오버피팅이 발생한 경우이므로 Early stopping을 해주면 된다.

Downpour

Google paper

수 많은 파라미터들이 서버에 있다고 하자. 우리는 모델의 레플리카를 제작할 것이다. 가장 먼저 레플리카가 로컬 데이터에 접근을 하게 된다. 로컬에는 부분 데이터가 저장되어 있다. 각각의 레플리카 모델은 batch 러닝을 진행한다. 그리고 다시 서버에 파라미터에 올린다. 그것을 서버가 받으면 서버는 정보를 토대로 자신을 업데이트 한다.

step1: Replica access local data. too much data to load .

step2: compute mini batch.

step3: update gradient to server.

추가적으로 큰 뉴럴 네트워크의 경우 각각을 쪼개서 로컬 업데이트 하도록 만들 수 있다.각각이 커뮤니케이션을 가지도록 한다면 충분히 가능하다.

Polyak averaging

$$\begin{align} W^{(t+1)}&=W^{(t)}-\gamma^{(t)}\nabla L(W^{(t)},v^{(t)})\\ \overline{W}^{(t+1)}&=\overline{W}^{(t)}-\frac{1}{t}\nabla L(\overline{W}^{(t)},v^{(t)}) \end{align}$$

Pick average when decent next step.

It will helpful when the $\eta$ is big so that the location of $\theta$ is vibrating.

Momentum

For three-dimensional planes shaped like valleys, running takes a long time.

$$\theta_{t+1}-\theta_t = \alpha(\theta_t -\theta_{t-1})+(1-\alpha)\left[-\eta \nabla J(\epsilon)\right]$$

This will not decent constant speed.

Adagrad

$$w_i^{(t+1)} \leftarrow w_i^{(t)}-\frac{\eta}{\sqrt{\sum_{\tau=1}^{t}g_{\tau,i}^2}}$$

Looking at the history of how much samples change the loss.

Rare features are able to get a larger update for the parameters.

This technique is used like in text data.