Machine Learning - NN

1. Step Function as Features

A linear classifier in 2D-space separates a group of training data with features $x^{(i)}=[x_1^{(i)},x_2^{(i)}{]}^T$$x^{(i)}=[x^{(i)}_1, x^{(i)}_2]^T$ and labels $y^{(i)}\in \{0,1\}$$y^{(i)} \in \{0, 1\}$ into to two. If we plot the separated training data into 3D-space, what we would get is a step function in 3D-space

Step function could be used as features, its difference from the previous case is that this time the feature itself also has parameters, consider the two step functions below

${\varphi }_i(x)$$\phi_i(x)$ is evaluated as $1$$1$ if what inside the curly braces is true

where

• ${\varphi }_i(x)$$\phi_i(x)$ is a step function of $x=[x_1,x_2{]}^T\in {\mathbb{R}}^2$$x =[x_1, x_2]^T \in \mathbb{R}^2$

• $y=w_i^{T}x+w_{0,i}$$y=w_i^Tx+w_{0,i}$ is the hyperplane of a linear classifier

Construct a feature vector of data point out of the above two step functions

Then we implement linear classification in 3D-space with this feature vector

We could assign a set of weight values and visualize this this classification hypothesis

If we add a third feature like this

We could see that there is some overlaps in the visualization of this hypothesis, but since we have determined the threshold value is 0, overlaps would not affect the classification results

While theoretically we could be more "confident" to classify training data lying in those regions

[TIP] To better understand the meaning of this process, think about it in some context:

We want to know which planet is suitable for human immigration, and the most descisive elements are

• $x_1:$$x_1:$ precipitation

• $x_2:$$x_2:$ temperature

Then we can interpret the three features given

• ${\varphi }_1(x):$$\phi_1(x):$ we don't want to immigrate if there's too much rain

• ${\varphi }_2(x):$$\phi_2(x):$ we don't want to immigrate if it's too hot

• ${\varphi }_3(x):$$\phi_3(x):$ we don't want to immigrate if it's too cold

So finally, in the top view graph on the right hand side, only planets lie in the green zone is inhabitable

 

 

 

2. Hypothesis

The process in 1. describes a Neural Network, that has the following two layers

1. Construct the Features

2. Assign the Labels

Superscript on a letter (in the form $L^{(i)}$$L^{(i)}$) would be used to represent indices of layer

$i=1$$i=1$ means we are at layer 1

• $1^{st}$$1^{st}$ Layer, Construct the Features

  • Input

    One Single Data Point of Features

    where $m^{(1)}$$m^{(1)}$ is the number of Features of a data point

    in our case, $m^{(1)}=2$$m^{(1)}=2$

    $$\begin{array}{c}x=\left[\begin{array}{c}{x}_1\\ ⋮\\ x_{m^{(1)}}\end{array}\right]\in {\mathbb{R}}^{m^{(1)}}\end{array}$$

    

  • Output

    Vector of (Step Function) Features

    where $n^{(1)}$$n^{(1)}$ is the number of (Step Function) Features

    in our case, $n^{(1)}=3$$n^{(1)}=3$

    $$\begin{array}{c}{A}^{(1)}=\left[\begin{array}{c}{A}_1^{(1)}\\ ⋮\\ A_{n^{(1)}}^{(1)}\end{array}\right]\in {\mathbb{R}}^{n^{(1)}}\end{array}$$

    

  • Computation

    • The $i^{th}$$i^{th}$ feature

      $$A_i^{(1)}=f^{(1)}(w_i^{(1)T}x+w_{0,i}^{(1)})$$

      where the dimension of $w_i^{(1)}$$w_{i}^{(1)}$ should be the same as that of $x$$x$

      $$\begin{array}{cc}{w}_i^{(1)}=\left[\begin{array}{c}{w}_{i[1]}^{(1)}\\ ⋮\\ w_{i[m^{(1)}]}^{(1)}\end{array}\right]\in {\mathbb{R}}^{m^{(1)}}& w_{0,i}^{(1)}\in \mathbb{R}\end{array}$$

    • All features at once

      $$A^{(1)}=f^{(1)}(W^{(1)T}x+W_0^{(1)})$$

      where $w_i^{(1)}$$w_{i}^{(1)}$ are horizontally stacked and $w_{0,i}^{(1)}$$w_{0,i}^{(1)}$ are vertically stacked

      $$\begin{array}{cc}{W}^{(1)}=\left[\begin{array}{ccc}{w}_1^{(1)}& \cdots & w_{n^{(1)}}^{(1)}\end{array}\right]\in {\mathbb{R}}^{m^{(1)}\times n^{(1)}}& W_0^{(1)}=\left[\begin{array}{c}{w}_1^{(1)}\\ ⋮\\ w_{n^{(1)}}^{(1)}\end{array}\right]\in {\mathbb{R}}^{n^{(1)}}\end{array}$$

• $2^{nd}$$2^{nd}$ Layer, Assign the Labels

  • Input

    Vector of (Step Function) Features, the output of the $1^{st}$$1^{st}$ layer,

    where $m^{(2)}=n^{(1)}$$m^{(2)}=n^{(1)}$ is the number of (Step Function) Features

    in our case, $m^{(2)}=n^{(1)}=3$$m^{(2)}=n^{(1)}=3$

    $$\begin{array}{c}{A}^{(1)}=\left[\begin{array}{c}{A}_1^{(1)}\\ ⋮\\ A_{n^{(1)}}^{(1)}\end{array}\right]\in {\mathbb{R}}^{m^{(2)}}={\mathbb{R}}^{n^{(1)}}\end{array}$$

    

  • Output

    Vector of Labels

    where $n^{(2)}$$n^{(2)}$ is the number of labels

    in our case, $n^{(2)}=1$$n^{(2)}=1$ as we are just trying to decide "yes" or "no"

    $$\begin{array}{c}{A}^{(2)}=\left[\begin{array}{c}{A}_1^{(2)}\\ ⋮\\ A_{n^{(2)}}^{(2)}\end{array}\right]\in {\mathbb{R}}^{n^{(2)}}\end{array}$$

    

    And yeah, all this process forms a Neural Net as noted in the graph above

  • Computation

    • The $i^{th}$$i^{th}$ label

      $$A_i^{(2)}=f^{(2)}(w_i^{(2)T}{A}^{(1)}+w_{0,i}^{(2)})$$

      where

      $$\begin{array}{cc}{w}_i^{(2)}=\left[\begin{array}{c}{w}_{i[1]}^{(2)}\\ ⋮\\ w_{i[m^{(2)}]}^{(2)}\end{array}\right]\in {\mathbb{R}}^{m^{(2)}}={\mathbb{R}}^{n^{(1)}}& w_{0,i}^{(2)}\in \mathbb{R}\end{array}$$

    • All labels at once

      $$A^{(2)}=f^{(2)}(W^{(2)T}{A}^{(1)}+W_0^{(2)})$$

      where $w_i^{(2)}$$w_{i}^{(2)}$ are horizontally stacked and $w_{0,i}^{(2)}$$w_{0,i}^{(2)}$ are vertically stacked

      $$\begin{array}{cc}{W}^{(2)}=\left[\begin{array}{ccc}{w}_1^{(2)}& \cdots & w_{n^{(2)}}^{(2)}\end{array}\right]\in {\mathbb{R}}^{m^{(2)}\times n^{(2)}}={\mathbb{R}}^{n^{(1)}\times n^{(2)}}& W_0^{(2)}=\left[\begin{array}{c}{w}_1^{(2)}\\ ⋮\\ w_{n^{(2)}}^{(2)}\end{array}\right]\in {\mathbb{R}}^{n^{(2)}}\end{array}$$

• Summary

  • The $1^{st}$$1^{st}$ layer

    $A^{(1)}=f^{(1)}(W^{(1)T}x+W_0^{(1)})$$A^{(1)}=f^{(1)}(W^{(1)T}x+W^{(1)}_0)$

  • The $2^{nd}$$2^{nd}$ layer

    $A^{(2)}=f^{(2)}(W^{(2)T}{A}^{(1)}+W_0^{(2)})$$A^{(2)}=f^{(2)}(W^{(2)T}A^{(1)}+W^{(2)}_0)$

  • The Whole Process

    $A^{(2)}=NN(x;W,W_0)$$A^{(2)}=NN(x; W, W_0)$

 

 

 

3. Function Graph

The following is a function graph created based on the hypothesis we developed (see 2.)

We have only one label to predict, so the output is just $A_1^{(2)}$$A^{(2)}_1$

Explanation

• This is a Fully Connected, Feed-Forward neural network

  • Fully Connected:

    A fully connected layer means that all inputs to every neuron of the layer is the same

    A fully connected network is composed of fully connected layers

  • Feed-Forward:

    Well, literally, all arrows are pointing forward

    (There are some NNs with arrows not pointing forward, like RNN)

• Circles in the graph means function evaluation. The summation signs $\sum$$\sum$ and $Z_i^{(n)}$$Z^{(n)}_i$ inside refers to

  • $1^{st}$$1^{st}$ layer:

    $$Z_i^{(1)}=w_i^{(1)T}x+w_{0,i}^{(1)}$$

  • $2^{nd}$$2^{nd}$ layer:

    $$Z_i^{(2)}=w_i^{(2)T}{A}^{(1)}+w_{0,i}^{(2)}$$

  Important Notation:

  $Z^{(l)}⟶$$Z^{(l)} \longrightarrow$ "Linear Part of $l^{th}$$l^{th}$ layer", if using the notations in 2., then $Z^{(l)}\in {\mathbb{R}}^{n^{(l)}}$$Z^{(l)} \in \mathbb{R}^{n^{(l)}}$

 

 

3.1 "Neuron"

Neurons/Units/Nodes are basic elements of a Neural Network

The following graph is a neuron taken from the $1^{st}$$1^{st}$ layer

represents the $i^{th}$$i^{th}$ feature with the equation

 

 

3.2 "Layer"

Multiple Neurons compose a layer

• Annotations

  

• Simplified Version

  with 3 features ${\varphi }_1(x)$$\phi_1(x)$, ${\varphi }_2(x)$$\phi_2(x)$, ${\varphi }_3(x)$$\phi_3(x)$, each is dependent on 2 parameter $x_1$$x_1$, $x_2$$x_2$

  

• Multiple (Hidden) Layers

  for example, you have $L$$L$ layers in a Neural Network

  

  Then each layer could be represented with

  $$\begin{array}{rl}{A}^{(l)}& =f^{(l)}(Z^{(l)})\\ & =f^{(l)}(W^{(l)T}{A}^{(l-1)}+W_0^{(l)})\end{array}$$

  where $l\in \{1,...,L\}$$l\in\{1,..., L\}$

 

 

 

4. Activation Function

4.1 Example

• Identity Function

  "Do Nothing"

• Sigmoid Function

  For classification to range $[0,1]$$[0, 1]$

  $$f(z)=\sigma (z)=\frac{1}{1+e^{-z}}$$

• Hyperbolic Tangent

  For classification to range $[-1,1]$$[-1, 1]$

  $$f(z)=\tanh \left(z\right)=\frac{e^z-e^{-z}}{e^z+e^{-z}}$$

• Rectified Linear Unit

  Similar to Identity Function, but zero-out all values less than 0

  There's one single point that is non-differentiable, but we won't go to that point most of the time

  $$\begin{array}{c}f(z)=\text{ReLU}(z)=\{\begin{array}{ll}0& \text{for }z<0\\ z& \text{otherwise}\end{array}\end{array}$$

 

• [Special] Softmax Function

  A popular choice for multi-class classification, see Special Topics - 1. for more information

 

 

4.2 Function Selection

Technically, we cannot use Step Function as Activation Function due to the following concerns

• Derivatives are either 0 or undefined

  Cannot apply (Stochastic) Gradient Descent

• Cannot take a range of values

  Cannot apply Regressions

• Value is completely binary with no values in between

  Cannot apply NLL Loss

The Hypothesis of Neural Network of our example is (see 2.)

You can choose different Activation Function based on what you want to do

• Regression

  If $f^{(1)}$$f^{(1)}$ could take in a range of values, then you can just use Identity Function as $f^{(2)}$$f^{(2)}$

  $$f^{(2)}(z)=z$$

• NLL Loss

  Sigmoid Function does return values $\in [0,1]$$\in [0,1]$, so...

  $$f^{(2)}(z)=\sigma (z)$$

• (Stochastic) Gradient Descent

  Both the above functions for $f^{(2)}$$f^{(2)}$ have non-zero derivatives

  $$\begin{array}{rl}& f_1^{(2)}(z)=z\\ & f_2^{(2)}(z)=\sigma (z)\end{array}$$

  We also need to make sure $f^{(1)}$$f^{(1)}$ is also differentiable, like...

  $$\begin{array}{rl}& f_2^{(1)}(z)=\sigma (z)\\ & f_2^{(1)}(z)=\tanh \left(z\right)\\ & f_2^{(1)}(z)=\text{ReLU}(z)\end{array}$$

[DEMO] Choosing different activation functions could generate different hyperplanes, for example

• $f^{(1)}(z)=\sigma (z)$$f^{(1)}(z)=\sigma(z)$

  

• $f^{(2)}(z)=z$$f^{(2)}(z)=z$ or $f^{(2)}(z)=\sigma (z)$$f^{(2)}(z)=\sigma(z)$

  

 

 

 

5. How to Train

A general form of Learning (or Optimization) Objective is

[Theorem] if optimization objective is nice and convex, then (Stochastic) Gradient Descent perform well

BUT! Unfortunately, the objective of Neural Network is SUPER NON-CONVEX function of parameters !!!

Except for 1-layer NN...

 

 

5.1 Back-Propagation

For Supervised Learning, what we want to do is

Since (Stochastic) Gradient Descent is usually preferred, what we need is

And, yeah, Back-Propagation is a very elegant way to find Gradients!

 

5.1.1 Some Remainders

• Chain Rule

  Back-Prop is based on Chain Rule

  $$\frac{da}{dc}=\frac{da}{db}\cdot \frac{db}{dc}$$

• Weight Hiding

  Bias Parameter $W_0$$W_0$ could be casted into $W$$W$ to form a general weight, and we can add a "$1$$1$" in the end of the original $A^{(l)}$$A^{(l)}$

  In this way the formula of linear part of the $l^{th}$$l^{th}$ layer could be simplified to

  $$Z^{(l)}=W^{(l)T}{A}^{(l)}$$

  This is the notation we are using in this section

  (See Machine Learning - Basics 1.6.5)

• Gradient with respect to What???

  Always find the Gradient of Loss function with respect to the Weights of the $l^{th}$$l^{th}$ layer $W^{(l)}$$W^{(l)}$

  That tells us how much we want to change the weights, in order to reduce the loss

 

5.1.2 Computation Analysis

Assume the Neural Network has $L$$L$ layers

• [How Training Loss depends on Weights of the Last Layer]

  Loss Function with the part of the $L^{th}$$L^{th}$ Layer

  $$\begin{array}{rl}Loss& =L(A^{(L)},y^{(i)})\\ A^{(L)}& =f^{(L)}(Z^{(L)})\\ Z^{(L)}& =W^{(L)T}{A}^{(L-1)}\end{array}$$

  Gradient Computation with respect to $L^{th}$$L^{th}$ Layer

  $$\frac{\partial Loss}{\partial W^{(L)}}=\underset{n^{(L)}\times 1}{\underbrace{\frac{\partial Loss}{\partial A^{(L)}}}}\cdot \underset{n^{(L)}\times n^{(L)}}{\underbrace{\frac{\partial A^{(L)}}{\partial Z^{(L)}}}}\cdot \underset{m^{(L)}\times 1}{\underbrace{\frac{\partial Z^{(L)}}{\partial W^{(L)}}}}$$

  Analysis

  • First Term $\frac{\partial Loss}{\partial A^{(L)}}$$\frac{\partial{Loss}}{\partial{A^{(L)}}}$

    According to 2., $A^{(L)}\in {\mathbb{R}}^{n^{(L)}}$$A^{(L)} \in\mathbb{R}^{n^{(L)}}$

    It's just the derivative $Los{s}^{\prime }$$Loss'$, depending on choice of Loss Function

  • Second Term $\frac{\partial A^{(L)}}{\partial Z^{(L)}}$$\frac{\partial{A^{(L)}}}{\partial{Z^{(L)}}}$

    According to 3., $Z^{(L)}\in {\mathbb{R}}^{n^{(L)}}$$Z^{(L)} \in\mathbb{R}^{n^{(L)}}$

    We know each $A_i^{(L)}$$A^{(L)}_i$ only depends on each $Z_i^{(L)}$$Z^{(L)}_i$, so this partial derivative is a diagonal matrix of size $n^{(L)}\times n^{(L)}$$n^{(L)}\times n^{(L)}$

    $$\begin{array}{c}\frac{\partial A^{(L)}}{\partial Z^{(L)}}=\left[\begin{array}{cccc}\frac{\partial A_1^{(L)}}{\partial Z_1^{(L)}}& 0& \cdots & 0\\ 0& \frac{\partial A_2^{(L)}}{\partial Z_2^{(L)}}& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & \frac{\partial A_{n^{(L)}}^{(L)}}{\partial Z_{n^{(L)}}^{(L)}}\end{array}\right]\end{array}$$

  • Third Term $\frac{\partial Z^{(L)}}{\partial W^{(L)}}$$\frac{\partial{Z^{(L)}}}{\partial{W^{(L)}}}$

    According to 2., $A^{(L-1)}\in {\mathbb{R}}^{m^{(L)}}$$A^{(L-1)} \in \mathbb{R}^{m^{(L)}}$

    If you just look at the equation of $Z^{(L)}$$Z^{(L)}$, you could find that this value is just

    $$\frac{\partial Z^{(L)}}{\partial W^{(L)}}=A^{(L-1)}$$

  • Proper Computation Sequence

    Obviously the dimensions of the terms of the above equation do not match

    The actual computation sequence is the below arrangement

    $$\underset{m^{(L)}\times n^{(L)}}{\underbrace{\frac{\partial Loss}{\partial W^{(L)}}}}=\underset{m^{(L)}\times 1}{\underbrace{\frac{\partial Z^{(L)}}{\partial W^{(L)}}}}\cdot \underset{1\times n^{(L)}}{\underbrace{(\underset{n^{(L)}\times n^{(L)}}{\underbrace{\frac{\partial A^{(L)}}{\partial Z^{(L)}}}}\cdot \underset{n^{(L)}\times 1}{\underbrace{\frac{\partial Loss}{\partial A^{(L)}}}}{)}^T}}$$

    Then we could find this nice and neat general notation

    $$\underset{m^{(L)}\times n^{(L)}}{\underbrace{\frac{\partial Loss}{\partial W^{(L)}}}}=\underset{m^{(L)}\times 1}{\underbrace{A^{(L-1)}}}\cdot \underset{1\times n^{(L)}}{\underbrace{(\frac{\partial Loss}{\partial Z^{(L)}}{)}^T}}$$

    By the above equation, we could see that

    since we have already found "$A^{(l-1)}$$A^{(l-1)}$" in the Forward Pass, we just need to find $\frac{\partial Loss}{\partial Z^{(l)}}$$\frac{\partial{Loss}}{\partial{Z^{(l)}}}$ to compute the gradient!!!

    Yeah!

• [How Training Loss depends on Weights of the First Layer]

  Too stupid if we still stick to the partial derivative train above...

  We can focus on finding $\frac{\partial Loss}{\partial Z^{(1)}}$$\frac{\partial{Loss}}{\partial{Z^{(1)}}}$, with the following equation in the third line

  $$\begin{array}{rl}\frac{\partial Loss}{\partial W^{(1)}}& =\frac{\partial Loss}{\partial A^{(L)}}\cdot \frac{\partial A^{(L)}}{\partial Z^{(L)}}\cdot \frac{\partial Z^{(L)}}{\partial A^{(L-1)}}\cdot \frac{\partial A^{(L-1)}}{\partial Z^{(L-1)}}\cdots \frac{\partial A^{(2)}}{\partial Z^{(2)}}\cdot \frac{\partial Z^{(2)}}{\partial A^{(1)}}\cdot \frac{\partial A^{(1)}}{\partial Z^{(1)}}\cdot \frac{\partial Z^{(1)}}{\partial W^{(1)}}\\ \\ & =(\frac{\partial Loss}{\partial A^{(L)}}\cdot \frac{\partial A^{(L)}}{\partial Z^{(L)}}\cdot W^{(L)}\cdot \frac{\partial A^{(L-1)}}{\partial Z^{(L-1)}}\cdots \frac{\partial A^{(2)}}{\partial Z^{(2)}}\cdot W^{(2)}\cdot \frac{\partial A^{(1)}}{\partial Z^{(1)}})\cdot x\\ \\ & =\frac{\partial Loss}{\partial Z^{(1)}}\cdot x\end{array}$$

  where $x$$x$ is the initial data point, equivalent notation is kind of "$A^{(0)}$$A^{(0)}$" (see 2.)

 

5.1.3 General Equation

• [Back-Propagation to $l^{th}$$l^{th}$ Layer]

  Dimensions of terms match properly in this version

  $$\begin{array}{rl}\frac{\partial Loss}{\partial Z^{(l)}}& =\frac{\partial A^{(l)}}{\partial Z^{(l)}}\cdot W^{(l+1)}\cdot \frac{\partial A^{(l+1)}}{\partial Z^{(l+1)}}\cdots W^{(L-1)}\cdot \frac{\partial A^{(L-1)}}{\partial Z^{(L-1)}}\cdot W^{(L)}\cdot \frac{\partial A^{(L)}}{\partial Z^{(L)}}\cdot \frac{\partial Loss}{\partial A^{(L)}}\\ \\ \frac{\partial Loss}{\partial W^{(l)}}& =A^{(l-1)}\cdot (\frac{\partial Loss}{\partial Z^{(l)}}{)}^T\end{array}$$

• [Summary]

  • Forward Pass

    For layer $l=0⟶L$$l = 0 \longrightarrow L$

    Compute all $A^{(l)}$$A^{(l)}$, $Z^{(l)}$$Z^{(l)}$, and $Loss$$Loss$

  • Back-Propagation

    For layer $l=L⟶0$$l = L \longrightarrow 0$

    Compute all gradients $\frac{\partial Loss}{\partial W^{(l)}}$$\frac{\partial{Loss}}{\partial{W^{(l)}}}$ and updata the weights

  

 

 

5.2 Stochastic GD

Here is the pseudo-code implementation of a Neural Network using Stochastic Gradient Descent

 

5.2.1 Weight Initialization

• Random

  Different layers of the Neural Network address different things, so do not start everything at the same weights!

  Or this will lead you to some Local Optimums rather than the Global Optimum!

• Not too Extreme

  1. Consider a Sigmoid as activation function, if the weight is too big, the input to Sigmoid will also be very big, which means the gradient will be almost 0!

  2. Consider a ReLU as activation function, if the weight is too small, the output of ReLU will lie on the left hand plane, where the gradient is 0!

  3. Worst Case:

     Extremely Big $⟶$$\longrightarrow$ Gradient Explodes

     Extremely Near 0 $⟶$$\longrightarrow$ Gradient Vanishes

     (see 5. for more information)

• Generally, keep the initial weights to be random small values to ensure Gradients to be non-zero

 

5.2.2 $Loss$$Loss$ and $f^{(L)}$$f^{(L)}$

Some common combinations of Loss Function with their respective Last Layer Activation Function

• Squared Loss $⟶$$\longrightarrow$ Identity

  (need real numbers)

• NLL Loss $⟶$$\longrightarrow$ Sigmoid

  (need two-class probability)

• NLLM Loss $⟶$$\longrightarrow$ Softmax

  (need multi-class probability)

 

 

5.3 Mini-Batch GD

"Average" the benefits of Batch GD and Stochastic GD

by selecting $k$$k$ data points at random from dataset to compute gradients

"Mini-Batch" = "Epoch"

but people use the term "Epoch" differently in other cases, so ...

Comparisons on Weight Update Equations with the following conditions

• By 5.1.1, weight hiding $\hat{W}=W,W_0$$\hat{W} = W, W_0$

• Assume dataset of size $n$$n$

• Assume mini-batch of size $k$$k$

[ Note ]

"Randomly select $k$$k$ data points" is hard, while "Randomly shuffle dataset & iterate" is easy

 

 

5.4 Regularization

When you train something and do not stop, the training loss would always going down, but the validation loss would go up at some point due to overfitting, and this is what Regularization deals with

 

5.4.1 Weight Decay

Add a (Ridge Regression) Regularizer / Penalty $R(W)=\lambda {\Vert W\Vert }^2$$R(W)=\lambda\norm{W}^{2}$ with $\lambda \ge 0$$\lambda \geq 0$ after the Objective Function

(Examples / Theories in Machine Learning - Basics 3.2.4 / 3.3.4)

Then the general Objective Function becomes

Assume using SGD ($n=1$$n = 1$), then the gradient of Objective Function is

Therefore the weight update equation becomes

Recall that the weight update equation without regularizer is

You can see that the difference is that $W_{t-1}$$W_{t-1}$ now has a Decay Coefficient $(1-2\eta \lambda )$$(1 - 2\eta\lambda)$ to make sure the weight is not too big

Here we assume Small Weight is more preferable with better performance to generalize the model

 

5.4.2 Batch Normalization

This deals with Covariate Shift, which assumes that

• Distribution of Input $P(x)$$P(x)$ is changed, or "shifted"

  Ex. For a Cat Classifier

  • Input Dataset 1 = cats at days

  • Input Dataset 2 = cats at nights

• Labeling Function $F(x,y)$$F(x,y)$ Stays the same

  The cats in the above 2 datasets are from the same group

  Hence the classification results should correspond

What you need to do is just to normalize the input data $X^{(i)}$$X^{(i)}$ for the $j^{th}$$j^{th}$ Mini-Batch at the $i^{th}$$i^{th}$ layer of Neural Network

5.4.3 Other Practices

• Dropout

  On each forward pass, each node has a probability $p$$p$ to be dropped out (by setting corresponding weight $W=0$$W=0$)

  The purpose is to make each node replaceable

  Nodes are just like members of a team with different capacities, you need to make sure that they can partially cover each other's specializations, so that one day when someone was absent due to sickness, the rest of the team could still make some progress.

  

• Perturbing Data

  Messing with Training Data a bit, with Normal Distribution or other stuff...

  $${\hat{x}}^{(i)}=x^{(i)}+N\text{where }N\sim Gaussian(\mu =0,{\sigma }^2\to \text{small})$$

  Sort of a form of Data Augmentation

 

 

 

 

 

Special Topics

1. Softmax Regression

Softmax Regression is a special activation function for Multi-Class Classification, the layer where this function is implemented is called "Softmax Layer" whose output is like the following.

Assume at $l^{th}$$l^{th}$ layer

• $C=4⟶$$C = 4 \longrightarrow$ 4 classes available to be classified

• $p(\text{Class n}{|}_{A^{(l-1)}})$$p(\text{Class n}|_{A^{(l-1)}})$ $⟶$$\longrightarrow$ Probability of being classified to Class $n$$n$ given $A^{(l-1)}$$A^{(l-1)}$

Output of the above Softmax layer $A^{(l)}$$A^{(l)}$ is a $4\times 1$$4\times 1$ matrix of whose elements are probabilities with a sum of $1$$1$

The name "Softmax" is relative to "Hardmax"

"Hardmax" also outputs a $4\times 1$$4\times 1$ matrix in the example above, but only assigns "$1$$1$" to the predicted class and "$0$$0$"s for the rest

$$\begin{array}{c}\text{Hardmax}(Z^{(l)})=\left[\begin{array}{c}0\\ 1\\ 0\\ 0\end{array}\right]\end{array}$$

"Just like One-Hot encoding"

 

 

1.1 Softmax Function

Assume number of classes to be classified is $C$$C$

• Linear Part of Softmax Layer (input to Softmax function)

  $$Z^{(l)}=W^{(l)T}{A}^{(l-1)}+W_0^{(l)}$$

• Softmax Activation Function

  It's kind of doing normalization, mapping input elements to probabilities

  $$A^{(l)}=\text{Softmax}(Z^{(l)})=\frac{e^{Z^{(l)}}}{\sum _{i=1}^C{e}^{Z_i^{(l)}}}$$

  The probability of the $i^{th}$$i^{th}$ Class is

  $$A_i^{(l)}=\frac{e^{Z_i^{(l)}}}{\sum _{i=1}^C{e}^{Z_i^{(l)}}}\in \mathbb{R}$$

  Dimensions:

  • $A^{(l)},e^{Z^{(l)}}\in {\mathbb{R}}^C$$A^{(l)}, e^{Z^{(l)}} \in\mathbb{R}^C$

  • $A_i^{(l)},e^{Z_i^{(l)}}\in \mathbb{R}$$A^{(l)}_i, e^{Z^{(l)}_i} \in\mathbb{R}$

[Example]

Given

• number of classes to be classified $C=4$$C = 4$

• linear part of Softmax Layer $Z^{(l)}=[5,2,-1,3{]}^T$$Z^{(l)}= [5, 2, -1, 3]^T$

Then calculate some essential data

Now we can find the output with the above

 

 

1.2 How to Train

• Loss Function for the $i^{th}$$i^{th}$ Data Point

  Assume having $4$$4$ classes to be classified, with the following example data point

  $$\begin{array}{rl}\text{Label: }& y^{(i)}=\left[\begin{array}{c}0\\ 1\\ 0\\ 0\end{array}\right]\\ \text{Result: }& {\hat{y}}^{(i)}=A^{(l)(i)}=\left[\begin{array}{c}0.3\\ 0.2\\ 0.1\\ 0.4\end{array}\right]\end{array}$$

  The Loss Function is defined by

  $$L(y^{(i)},\widehat{y^{(i)}})=-\sum _{j=1}^4[y_j^{(i)}\log \left({\hat{y}}_j^{(i)}\right)]$$

  This function seems to have terms of all four classes, but if you look at the label matrix $y^{(i)}$$y^{(i)}$, you'll notice that only one class is assigned with $1$$1$, and rest assigned with "$0$$0$"s, which means only the term related to predicted class will be left

  Based on the above example, we will have

  $$\begin{array}{rl}-\sum _{j=1}^4[y_j^{(i)}\log \left({\hat{y}}_j^{(i)}\right)]& =-y_2^{(i)}\log \left({\hat{y}}_2^{(i)}\right)\\ & =-1\cdot \log \left({\hat{y}}_2^{(i)}\right)\\ & =-\log \left({\hat{y}}_2^{(i)}\right)\end{array}$$

  Therefore, you want to make ${\hat{y}}^{(2)}$$\hat{y}^{(2)}$ as big as possible to minimize this loss function

  a.k.a. Make a correct prediction!

• Objective Function for the Training Set

  Assume the Training Set has $m$$m$ data points

  $$J(W^{(l)},W_0^{(l)})=\frac{1}{m}\sum _{i=1}^{m}L(y^{(i)},\widehat{y^{(i)}})$$

  Then you can just use gradient descent or other methods to learn the parameter...

 

 

 

2. Multi-Class NLL Loss

2.1 Two-Class Version

This is the Loss Function for Logistic Regression (see Machine Learning - Basics 3.2.3), hence it is actually a 2-Class NLL Loss

Assume $y^{(i)}$$y^{(i)}$ is the labeled value for the $i^{th}$$i^{th}$ data point, $g^{(i)}$$g^{(i)}$ is the guessed value for the $i^{th}$$i^{th}$ data point.

If $y^{(i)}\in \{0,1\}$$y^{(i)} \in \{0, 1\}$, then the NLL Loss function could be defined as

 

 

2.2 Multi-Class Version

The definition in 2.1 could be extended to multi-class classification directly

Assume the number of classes to be classified is $C$$C$, using Softmax as output layer activation function, then

• $y^{(i)}⟶$$y^{(i)} \longrightarrow$ one-hot encoded matrix with "$1$$1$" representing the labeled class

• $g^{(i)}⟶$$g^{(i)} \longrightarrow$ output of Softmax Layer representing the probability distribution over $C$$C$ classes

The probability that the Neural Network makes proper prediction is

Definition of Multi-Class Negative-Log-Likelihood Loss Function is

 

 

 

3. Adaptive Step-Size

Step size $\eta$$\eta$ should be independent for each weight, based on the local view of gradient update

For example

• $\eta$$\eta$ should be small when gradient change is small

• $\eta$$\eta$ should be large when gradient change is large

or you might miss something important...like the red-little optimum...

 

 

3.1 Moving Average

This is the theoretical basis for further discussion of step-size

Define a sequence of $T$$T$ data points $a_t=a_1,a_2,...,a_T$$a_t = a_1, a_2,...,a_T$

Define a weight average of first $t$$t$ data points $A_t=A_0,A_1,A_2,...,A_T$$A_t = A_0,A_1,A_2,...,A_T$ with the following formulations

where ${\gamma }_t\in (0,1)$$\gamma_t \in (0,1)$ is the weight, assume constant ${\gamma }_t=\gamma$$\gamma_t = \gamma$

Then the weighted average of all $T$$T$ data points is

Data input closer to the end $T$$T$ have more impact on weighted average $A_T$$A_T$

Noted that $\gamma \in (0,1)$$\gamma \in (0,1)$, therefore

• ${\gamma }^a\to 0$$\gamma^a \rightarrow 0$ as $a\to \mathrm{\infty }$$a\rightarrow \infin$

• ${\gamma }^a\to 1$$\gamma^a \rightarrow 1$ as $a\to 0$$a\rightarrow 0$

[ Note ]

Setting ${\gamma }_t=\frac{t-1}{t}$$\gamma_t = \frac{t-1}{t}$, then the equation gives the actual average

 

 

3.2 Momentum

SGD and MBGD randomly select one or more data points to compute gradient, hence the direction of next step is also random

"Momentum" allows more effective weight update by taking past gradients into account

Momentum = Weighted Average of Current & Past Gradients

To be more specific, in the graph below

• Red Arrows are the final choice of update of each step

• Blue Dots are the computed "current gradients" Mini-Batch at each step

Definition of Weight Update with Momentum

To arrange the above equations into standard form of Moving Average, define $\eta ={\eta }^{\prime }(1-\gamma )$$\eta = \eta'(1-\gamma)$

• Momentum Update

  $$\begin{array}{rl}{V}_t& =\gamma V_{t-1}+\eta {\mathbf{\nabla }}_{W}J(W_{t-1})\\ V_t& =\gamma V_{t-1}+{\eta }^{\prime }(1-\gamma ){\mathbf{\nabla }}_{W}J(W_{t-1})\\ \frac{V_t}{{\eta }^{\prime }}& =\gamma \frac{V_{t-1}}{{\eta }^{\prime }}+(1-\gamma ){\mathbf{\nabla }}_{W}J(W_{t-1})\end{array}$$

  Define that $M_t=V_t/{\eta }^{\prime }$$M_t = V_t / \eta'$, then

  $$M_t=\gamma M_{t-1}+(1-\gamma ){\mathbf{\nabla }}_{W}J(W_{t-1})$$

• Initial Momentum

  $$M_0=\frac{V_0}{{\eta }^{\prime }}=\frac{0}{{\eta }^{\prime }}=0$$

• Weight Update

  $$W_t=W_{t-1}-{\eta }^{\prime }\cdot \frac{V_t}{{\eta }^{\prime }}=W_{t-1}-{\eta }^{\prime }{M}_t$$

• Summary

  Now this looks exactly like update weights with step-size of ${\eta }^{\prime }$$\eta'$ on a weighted moving average of gradients

  $$\begin{array}{rl}{M}_0& =0\\ M_t& =\gamma M_{t-1}+(1-\gamma ){\mathbf{\nabla }}_{W}J(W_{t-1})\\ W_t& =W_{t-1}-{\eta }^{\prime }{M}_t\end{array}$$

 

 

3.3 AdaDelta / AdaGrad

Here is an intuitive way to understand this:

"Big Steps when Flat, Small Steps when Steep"

Just like the example provided in the beginning of this section!

Definition of Weight Update with AdaDelta

where

• $g_{t,j}⟶$$g_{t,j}\longrightarrow$ Gradient of the $j^{th}$$j^{th}$ Weight, or the $j^{th}$$j^{th}$ Component of the Gradient

• $G_{t,j}⟶$$G_{t,j}\longrightarrow$ Weighted Moving Average of the Squared Gradient of the $j^{th}$$j^{th}$ Weight

  This is the measure of Curvature (Flat / Steep)

  • $g_{t,j}\uparrow \Rightarrow G_{t,j}\uparrow$$g_{t,j} \uparrow \;\Rightarrow G_{t,j}\uparrow$, curvature is high, scale-down step-size in weight update

  • $g_{t,j}\downarrow \Rightarrow G_{t,j}\downarrow$$g_{t,j} \downarrow \;\Rightarrow G_{t,j}\downarrow$, curvature is low, scale-up step-size in weight update

• $ϵ⟶$$\epsilon\longrightarrow$ a very small "Safeguard" in case the step-size goes crazy when $G_{t,j}=0$$G_{t,j} = 0$

 

 

3.4 Adam

Combines the idea of Momentum and AdaDelta, by computing the Moving Averages of both Gradient and Squared Gradient

but it may actually violate the convergence conditions of SGD

Definition of Weight Update with Adam

where

• $g_{t,j}⟶$$g_{t,j}\longrightarrow$ Gradient of the $j^{th}$$j^{th}$ Weight, or the $j^{th}$$j^{th}$ Component of the Gradient

• $m_{t,j}⟶$$m_{t,j}\longrightarrow$ Weighted Moving Average of the Gradient of the $j^{th}$$j^{th}$ Weight

  the "Nominal" Mean

• $v_{t,j}⟶$$v_{t,j}\longrightarrow$ Weighted Moving Average of the Squared Gradient of the $j^{th}$$j^{th}$ Weight

  the "Nominal" Variance

• ${\hat{m}}_{t,j},{\hat{v}}_{t,j}⟶$$\hat{m}_{t,j}, \hat{v}_{t,j} \longrightarrow$ Corrected "Mean" & "Variance"

  if "Nominal" Mean & Variance use zero initialization ($m_0=0,v_0=0$$m_0=0, v_0=0$) without being corrected

  then their values would always be too small!

 

 

 

4. CNN

Concolution Neural Network (CNN) is a classic architecture for Image Processing

see this cheatsheet