Forward propagation

• Components of a neural network
  • Neurons = computational units
  • Dendrites = input features $(x_0,...,x_n)$
    • Bias unit: $x_0=1$
  • Axons = output; the result of our hypothesis function

• Visual diagram

  $$\left[\begin{array}{c}{x}_0\\ x_1\\ x_2\\ x_3\end{array}\right]\to \left[\begin{array}{c}{a}_1^{(2)}\\ a_2^{(2)}\\ a_3^{(2)}\end{array}\right]\to h_{\theta }(x)$$
  • Layer 1 (aka input layer) = input nodes
  • Layer 2 (aka hidden layer)
    • Let a sigmoid function g be the activation function
    • Node $a_i^{(j)}$ = activation unit i in layer j
    • Matrix ${\mathrm{\Theta }}^{(j)}$ = weights for the mapping from layer j to j+1
  • Layer 3 (aka output layer) = hypothesis function

• Hidden layers enable non-linear hypotheses

  $$\begin{array}{rl}{a}_1^{(2)}& =g({\mathrm{\Theta }}_{10}^{(1)}{x}_0+{\mathrm{\Theta }}_{11}^{(1)}{x}_1+{\mathrm{\Theta }}_{12}^{(1)}{x}_2+{\mathrm{\Theta }}_{13}^{(1)}{x}_3)\\ a_2^{(2)}& =g({\mathrm{\Theta }}_{20}^{(1)}{x}_0+{\mathrm{\Theta }}_{21}^{(1)}{x}_1+{\mathrm{\Theta }}_{22}^{(1)}{x}_2+{\mathrm{\Theta }}_{23}^{(1)}{x}_3)\\ a_3^{(2)}& =g({\mathrm{\Theta }}_{30}^{(1)}{x}_0+{\mathrm{\Theta }}_{31}^{(1)}{x}_1+{\mathrm{\Theta }}_{32}^{(1)}{x}_2+{\mathrm{\Theta }}_{33}^{(1)}{x}_3)\\ h_{\mathrm{\Theta }}(x)=a_1^{(3)}& =g({\mathrm{\Theta }}_{10}^{(2)}{a}_0^{(2)}+{\mathrm{\Theta }}_{11}^{(2)}{a}_1^{(2)}+{\mathrm{\Theta }}_{12}^{(2)}{a}_2^{(2)}+{\mathrm{\Theta }}_{13}^{(2)}{a}_3^{(2)})\end{array}$$
  • Each layer gets its own matrix of weights, ${\mathrm{\Theta }}^{(j)}$
  • If the NN has $s_j$ units in layer j and has $s_{j+1}$ units in layer j+1, then the dimension of ${\mathrm{\Theta }}^{(j)}\to (s_{j+1},s_j+1)$
    • The +1 comes from accounting for the bias node, $x_0$
    • Input nodes include the bias node vs. Output nodes do not

Vectorized implementation

• Let $z_k^{(j)}$ represent node k in layer j

$$z_k^{(j)}={\mathrm{\Theta }}_{k0}^{(j-1)}{x}_0+{\mathrm{\Theta }}_{k1}^{(j-1)}{x}_1+{\mathrm{\Theta }}_{kn}^{(j-1)}{x}_n$$ $$\downarrow \text{vectorize nodes into a column}$$ $$\begin{array}{rl}{z}^{(j)}& ={\mathrm{\Theta }}^{(j-1)}{a}^{(j-1)}\end{array}$$

         where $a^{(1)}=x=\left[\begin{array}{c}{x}_0\\ x_1\\ ...\\ x_n\end{array}\right]$, and $a_0^{(j)}=1$ is added in as the bias unit

• Then, the next layer’s activation nodes are computed
  • Include bias node for hidden layers
  • Do not include bias node for output layer

$$\begin{array}{rl}{a}^{(j)}& =g\left(z^{(j)}\right)\end{array}$$

• So the idea is to repeat $z^{(j)}\to a^{(j)}\to z^{(j+1)}\to a^{(j+1)}$ until we reach $a^{(\text{final\_layer})}=h_{\mathrm{\Theta }}(x)$

  $$\begin{array}{rl}{a}^{(1)}& =x\\ z^{(2)}& ={\mathrm{\Theta }}^{(1)}{a}^{(1)}\\ a^{(2)}& =g(z^{(2)})\text{ (add }{a}_0^{(2)}\text{)}\\ z^{(3)}& ={\mathrm{\Theta }}^{(2)}{a}^{(2)}\\ a^{(3)}& =g(z^{(3)})\text{ (add }{a}_0^{(3)}\text{)}\\ z^{(4)}& ={\mathrm{\Theta }}^{(3)}{a}^{(3)}\\ a^{(4)}& =h_{\mathrm{\Theta }}(x)=g(z^{(4)})\end{array}$$

Multiclass classification

• To classify data into multiple classes, we want our hypothesis function to return a vector of values
  • Ex: We want to classify an image into one of four categories: pedestrian, car, motorcycle, or truck
  • Each vector represents a class:
  $$y^{(i)}\in \{\left[\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 1\\ 0\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right]\}$$
  • The process:
  $$\begin{array}{r}\left[\begin{array}{c}{x}_0\\ x_1\\ x_2\\ ...\\ x_n\end{array}\right]\to \left[\begin{array}{c}{a}_0^{(2)}\\ a_1^{(2)}\\ a_2^{(2)}\\ ...\end{array}\right]\to \left[\begin{array}{c}{a}_0^{(3)}\\ a_1^{(3)}\\ a_2^{(3)}\\ ...\end{array}\right]\to ...\to \left[\begin{array}{c}{h}_{\mathrm{\Theta }}(x{)}_1\\ h_{\mathrm{\Theta }}(x{)}_2\\ h_{\mathrm{\Theta }}(x{)}_3\\ h_{\mathrm{\Theta }}(x{)}_4\end{array}\right]\end{array}$$

---

Cost function

• Defining variables:
  • $L$ = # of layers
  • $s_l$ = # of units in layer $l$, excluding the bias unit
  • $K$ = # of output units (i.e. # of classes)
  • $h_{\mathrm{\Theta }}(x{)}_k$ = the hypothesis that results in the $k^{th}$ output

• Recall the cost function for logistic regression:

  $$\begin{array}{r}J(\theta )=-\frac{1}{m}\sum _{i=1}^m[y^{(i)}\log (h_{\theta }(x^{(i)}))+(1-y^{(i)})\log (1-h_{\theta }(x^{(i)}))]+\frac{\lambda }{2m}\sum _{j=1}^n{\theta }_j^2\end{array}$$

• The cost function for NN:

  $$\boxed{{\displaystyle J(\theta )=-\frac{1}{m}\sum _{i=1}^m\sum _{k=1}^K[y_k^{(i)}\log ((h_{\mathrm{\Theta }}(x^{(i)}){)}_k)+(1-y_k^{(i)})\log (1-(h_{\mathrm{\Theta }}(x^{(i)}){)}_k)]+\frac{\lambda }{2m}\sum _{l=1}^{L-1}\sum _{i=1}^{s_l}\sum _{j=1}^{s_{l+1}}({\mathrm{\Theta }}_{j,i}^{(l)}{)}^2}}$$
  • Remember: $y$ here is a vector of 1s and 0s, denoting class
  • First term: take each output node $\to$ calculate the cost for that node, summed up over all examples $\to$ sum up cost for all nodes
  • Second term: square each weight, and add them all up

---

Backpropagation

• Def: NN terminology for minimizing the cost function
  • Goal is to find the optimal set of weights $\to$ need to compute their partials:

$$\begin{array}{r}\frac{\partial }{\partial {\mathrm{\Theta }}_{i,j}^{(l)}}J(\mathrm{\Theta })\end{array}$$

• The algorithm:
  1. Initialize all weights to zero. Also set ${\mathrm{\Delta }}_{ij}^{(l)}=0$ for all $l,i,j$.
  2. Let $m$ denote the number of samples. For $t=1:m$
     • Set $a^{(1)}:=x^{(t)}$
     • Perform forward propagation to compute $a^{(l)}$ for $l=2,3,...,L$
  3. Compute the error in each layer.
     • Last layer: ${\delta }^{(L)}=a^{(L)}-y^{(t)}$
     • Previous layers: ${\delta }^{(L-1)},{\delta }^{(L-2)},...,{\delta }^{(2)}$
     • For $\mathrm{\Theta }$, be sure to exclude the first column (the bias column) since bias units do not hold any error (they hold no connection to the input layer.)
     $$\begin{array}{rl}{\delta }^{(l)}& =[({\mathrm{\Theta }}^{(l)}{)}^T{\delta }^{(l+1)}]\cdot g^{\prime }(z^{(l)})\\ & =[({\mathrm{\Theta }}^{(l)}{)}^T{\delta }^{(l+1)}]\cdot a^{(l)}\cdot (1-a^{(l)})\end{array}$$

  4. Update capital deltas, the accumulators for adding up partials.

     $${\mathrm{\Delta }}_{ij}^{(l)}:={\mathrm{\Delta }}_{ij}^{(l)}+a_j^{(l)}{\delta }_i^{(l+1)}$$ $$\downarrow \text{vectorized}$$ $$\begin{array}{r}{\mathrm{\Delta }}^{(l)}:={\mathrm{\Delta }}^{(l)}+{\delta }^{(l+1)}(a^{(l)}{)}^T\end{array}$$
  5. Outside the for loop, use capital deltas to calculate partial derivatives.
     • Notice: we do not regularize the bias unit.
     $$\begin{array}{r}\frac{\partial }{\partial {\mathrm{\Theta }}_{i,j}^{(l)}}J(\mathrm{\Theta }):=\{\begin{array}{l}\frac{1}{m}({\mathrm{\Delta }}_{i,j}^{(l)}+\lambda {\mathrm{\Theta }}_{i,j}^{(l)})\text{ if }j\ne 0\\ \frac{1}{m}{\mathrm{\Delta }}_{i,j}^{(l)}\text{ if }j=0\end{array}\end{array}$$

Intuition

• Calculating $z_k^j$ in FP Andrew Ng | Coursera
• ${\delta }_j^{(l)}=\frac{\partial }{\partial z_j^{(l)}}cost(t)⟷$ error for $a_j^{(l)}$ (unit j, layer $l$)
  • i.e.) How much we would like to change NN weights in order to affect intermediate values of computation (z) so as to affect the final output $h(x)$ and therefore affect the overall cost
  • i.e.) How much that node was “responsible” for any errors in output
    • Steeper the slope $\to$ the more incorrect we are
• Calculating ${\delta }_j^{(l)}$
  • Multiply the deltas that feed into that node from the right with their respective weights, and add. Andrew Ng | Coursera
• BP vs. gradient descent
  • BP computes the direction to go downhill, towards the minimum.
  • Gradient descent takes those small steps towards the minimum.

Random initialization

• Problem of symmetric ways: Initializing all theta weights to zero (or any same number) causes all nodes to update to the same value
  • e.g.) ${\mathrm{\Theta }}_{ij}^{(l)}=0\mathrm{\forall }i,j,l\to a_1^{(2)}=a_2^{(2)}\to {\delta }_1^{(2)}={\text{delat}}_2^{(2)}\to \frac{\partial }{\partial {\mathrm{\Theta }}_{01}^{(1)}}J(\mathrm{\Theta })=\frac{\partial }{\partial {\mathrm{\Theta }}_{02}^{(1)}}J(\mathrm{\Theta })\to a_1^{(2)}=a_2^{(2)}$ even after gradient descent and BP! That’s like saying we have only 1 feature in the NN
• To break this symmetry, do random initialization
  • Initialize each ${\mathrm{\Theta }}_{ij}^{(l)}$ to a random value in $[-ϵ,ϵ]$
    • The epsilon here is unrelated to epsilon in gradient checking
  • Choose $ϵ$ based on the # of units in the NN $\begin{array}{r}ϵ=\frac{\sqrt{(}6)}{\sqrt{(}{s}_l+s_{l+1})}\end{array}$

Training a NN

• Pick a neural architecture. Choose how many hidden layers, how many units in each layer, etc. Andrew Ng | Coursera

  • of input units = dimension of features

  • of output units = number of classes

  • of hidden layers = reasonable default is 1

  • of hidden units = more the better (but computationally expensive)

    • Usually more than the number of features (up to 3-4 times the number of input units)
    • If you choose >1 hidden layer, have the same # of hidden units in each layer

1. Randomly initialize weights ($\mathrm{\Theta }$ close to zero)
2. Implement FP to get $h(x^{(i)})$ for any $(x^{(i)}$
3. Implement code to compute cost function $J(\mathrm{\Theta })$
4. Implement BP to compute partial derivatives of $J(\mathrm{\Theta })$
5. Use gradient descent or advanced optimization method with BP to minimize $J(\mathrm{\Theta })$
6. Note: $J(\mathrm{\Theta })$ is non-convex. So in theory, gradient descent / advanced methods can get stuck finding local minima instead of the global minimum. But this is usually not a problem, even with local minima.