czxttkl

Background

This post reviews how we update weights using the back propagation approach in a neural network. The goal of the review is to illustrate a notorious phenomenon in training MLNN, called “gradient vanish”.

Start

Let’s suppose that we have a very simple NN structure, with only one unit in each hidden layer, input layer and output layer. Each unit has sigmoid function as its activation function:

Also suppose we have training data: $latex (x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n)$. Therefore, we have $latex h_1 = \frac{1}{1+e^{-w_0x_i}}$, $latex h_2 = \frac{1}{1+e^{-w_1h_1}}$, $latex h_3 = \frac{1}{1+e^{-w_2h_2}} $, $latex o = \frac{1}{1+e^{-w_3h_3}}$

Our cost function, which we want to minimize, is as follows:

$latex C=\sum\limits_{i=1}^n \left\Vert y_i – o_i\right\Vert^2$ 

If we are going to update $latex w_0$ after a round of inputting all the training data, we use the following rule (with $latex \epsilon$ as the learning rate):

$latex w_0 – \epsilon\nabla_{w_0}C$. 

Due to the chain rule of derivatives, we can have equivalently:

$latex \nabla_{w_0}C = \sum\limits_{i=1}^n\frac{\partial C_x}{\partial o} \cdot \frac{\partial o}{\partial h_3} \cdot \frac{\partial h_3}{\partial h_2} \cdot \frac{\partial h_2}{\partial h_1} \cdot \frac{\partial h_1}{\partial w_0}&s=3$

$latex =\sum\limits_{i=1}^n2(y_i – o_i) \cdot \delta'(w_3h_3) \cdot (-w_3) \delta'(w_2h_2) \cdot(-w_2) \cdot \delta'(w_1h_1) \cdot (-w_1) \cdot \delta'(w_0x_i) \cdot (-x_i)$

$latex =\sum\limits_{i=1}^n2(y_i – o_i)\cdot (-w_3) \cdot (-w_2) \cdot (-w_1) \cdot (-w_0) \cdot (-x_i) \cdot \delta'(w_3h_3) \cdot\delta'(w_2h_2) \cdot\delta'(w_1h_1)\cdot \delta'(w_0x_i)$

,where $latex \delta'(t) = (\frac{1}{1+e^{-t}})’$ is the derivative of sigmoid function.

We should be very familiar with the shape of sigmoid function as well as its derivative.

From the two plots above, we know that the largest derivative of sigmoid function is 0.25 and it takes place at x=0. Let’s go back to $latex \nabla_{w_0}C$ of the multiple-layer neural network,  which is the gradient descent of the weight associated with the layer farthest away from the output unit. It has four sigmoid derivatives, namely $latex \delta'(w_3h_3) \cdot\delta'(w_2h_2) \cdot\delta'(w_1h_1)\cdot \delta'(w_0x_i)$, each of which cannot overseed 0.25. As a result, $latex \nabla_{w_0}C$ would become very tiny.

That’s how gradient vanishing happens! It’s the phenomenon that certain weights in a multi-layer neural network cannot get updated effectively. 

Reference

http://neuralnetworksanddeeplearning.com/chap5.html

http://www-labs.iro.umontreal.ca/~bengioy/dlbook/mlp.html

Maybe it sounds simple to computer scientists, I just want to backup some logical deduction of myself in NP-completeness proofs in case I will deal with such proofs in the future.

In NP-completeness proof, we always want to find a polynomial-time reduction (transformation) from problem A to problem B, denoted as:

We say that there is an algorithm which for each instance $latex I$ of Problem A constructs Problem B in time which is polynomial with respect to the input size.

If $latex B \in P$, then $latex A \in P$. Think about it in contradiction: if $latex A$ is a NP-complete problem, a problem as hard as the “hardest problems” in the world, and suddenly we have a polynomial-time to transform it to problem B which is in P, then why not applying such transformation then solving B, both in polynomial time, every time we are given to solve $latex A$? 

However, it is easy (and wrong) to think that if $latex B \in \text{NP-complete}$ then $latex A \in \text{NP-complete}$. It is wrong because I can even transform $\latex A$, a problem in P,  by my will to any problem as tricky as NP-complete problems. So having $latex B \in \text{NP-complete}$ and a polynomial time transformation from $latex A$ to $latex B$ can’t guarantee $latex A$ to be anything.

If $latex A \in \text{NP-complete}$, then $latex B \in \text{NP-complete}$. Initially I think this is counter-intuitive. After all, by definition of polynomial time reduction, every instance of $latex A$ is mapped to $latex B$, but not every instance of $latex B$ can be assured to be mapped. Thinking in the following way makes me more sense: at least some instances of $latex B$ are mapped from every instance of $latex A$. So the mapped instances of $latex B$ are as hard as NP-complete problems. If the other instances of $latex B$ can be solved in P, problem $latex B$ itself still falls in the $latex NP-complete$ category.

All in all, I think all my logical deduction holds if the following diagram is true:

Otherwise, all the NP-complete proofs in this world will need to take with a grain of salt. 

Intuitively, Breadth-First Search (BFS) can find shortest distances from a source $latex s&s=4$ to any other reachable vertex. However, proving this intuition needs a bit hard work. After some searches, I found that there are two ideas to prove it. The two ideas both use induction to prove it. Both ideas require a bit long proof.

1. The first idea is based on CLRS Page 597-600. The second reference below is talking about the same idea.
2. The second idea is from a pdf file from NYU.  (the third reference)

References:

• CLRS Page 597 – 600
• http://www.cs.toronto.edu/~krueger/cscB63h/lectures/BFS.pdf
• http://www.cs.nyu.edu/courses/fall03/G22.1170-001/bfs.pdf

Here I am showing my proof, a small variant of CLRS:

Continue reading “Proof that BFS finds shortest distance”