How does LSTM prevent the vanishing gradient problem? LSTM was invented specifically to avoid the vanishing gradient problem. It is supposed to do that with the Constant Error Carousel (CEC), which on the diagram below (from Greff et al.) correspond to the loop around cell.

(source: deeplearning4j.org)
And I understand that that part can be seen as a sort of identity function, so the derivative is one and the gradient stays constant.
What I don't understand is how it does not vanish due to the other activation functions ? The input, output and forget gates use a sigmoid, which derivative is at most 0.25, and g and h were traditionally tanh. How does backpropagating through those not make the gradient vanish ?
 A: The vanishing gradient is best explained in the one-dimensional case. The multi-dimensional is more complicated but essentially analogous. You can review it in this excellent paper [1].
Assume we have a hidden state $h_t$ at time step $t$. If we make things simple and remove biases and inputs, we have
$$h_t = \sigma(w h_{t-1}).$$
Then you can show that 
\begin{align}
\frac{\partial h_{t'}}{\partial h_t} 
&= \prod_{k=1}^{t' - t} w \sigma'(w h_{t'-k})\\
&= \underbrace{w^{t' - t}}_{!!!}\prod_{k=1}^{t' - t} \sigma'(w h_{t'-k})
\end{align}
The factored marked with !!! is the crucial one. If the weight is not equal to 1, it will either decay to zero exponentially fast in $t'-t$, or grow exponentially fast.
In LSTMs, you have the cell state $s_t$. The derivative there is of the form
$$\frac{\partial s_{t'}}{\partial s_t} = \prod_{k=1}^{t' - t} \sigma(v_{t+k}).$$
Here $v_t$ is the input to the forget gate. As you can see, there is no exponentially fast decaying factor involved. Consequently, there is at least one path where the gradient does not vanish. For the complete derivation, see [2].
[1] Pascanu, Razvan, Tomas Mikolov, and Yoshua Bengio. "On the difficulty of training recurrent neural networks." ICML (3) 28 (2013): 1310-1318.
[2] Bayer, Justin Simon. Learning Sequence Representations. Diss. München, Technische Universität München, Diss., 2015, 2015.
A: http://www.felixgers.de/papers/phd.pdf    Please refer to section 2.2 and 3.2.2 where the truncated error part is explained. They don't propagate the error if it leaks out of the cell memory (i.e. if there is a closed/activated input gate), but they update the weights of the gate based on the error only for that time instant. Later it is made zero during further back propagation. This is kind of hack but the reason to do is that the error flow along the gates anyway decay over time.
A: The picture of LSTM block from Greff et al. (2015) describes a variant that the authors call vanilla LSTM. It's a bit different from the original definition from Hochreiter & Schmidhuber (1997). The original definition did not include the forget gate and the peephole connections.
The term Constant Error Carousel was used in the original paper to denote the recurrent connection of the cell state. Consider the original definition where the cell state is changed only by addition, when the input gate opens. The gradient of the cell state with regard to the cell state at an earlier time step is zero.
Error may still enter the CEC through the output gate and the activation function. The activation function reduces the magnitude of the error a little bit before it is added to the CEC. CEC is the only place where the error can flow unchanged. Again, when the input gate opens, the error exits through the input gate, activation function, and affine transformation, reducing the magnitude of the error.
Thus the error is reduced when it is backpropagated through an LSTM layer, but only when it enters and exits the CEC. The important thing is that it does not change in the CEC no matter how long distance it travels. This solves the problem in the basic RNN that every time step applies an affine transformation and nonlinearity, meaning that the longer the time distance between the input and output, the smaller the error gets.
A: I'd like to add some detail to the accepted answer, because I think it's a bit more nuanced and the nuance may not be obvious to someone first learning about RNNs.
For the vanilla RNN, $$\frac{\partial h_{t'}}{\partial h_{t}} = \prod _{k=1} ^{t'-t} w 
 \sigma'(w h_{t'-k})$$.
For the LSTM, $$\frac{\partial s_{t'}}{\partial s_{t}} = \prod _{k=1} ^{t'-t} 
 \sigma(v_{t+k})$$


*

*a natural question to ask is, don't both the product-sums have a sigmoid term that when multiplied together $t'-t$ times can vanish?

*the answer is yes, which is why LSTM will suffer from vanishing gradients as well, but not nearly as much as the vanilla RNN


The difference is for the vanilla RNN, the gradient decays with $w \sigma'(\cdot)$ while for the LSTM the gradient decays with $\sigma (\cdot)$.
For the LSTM, there's is a set of weights which can be learned such that $$\sigma (\cdot) \approx 1$$ Suppose $v_{t+k} = wx$ for some weight $w$ and input $x$. Then the neural network can learn a large $w$ to prevent gradients from vanishing.
e.g. In the 1D case if $x=1$, $w=10$ $v_{t+k}=10$ then the decay factor $\sigma (\cdot) = 0.99995$, or the gradient dies as: $$(0.99995)^{t'-t}$$
For the vanilla RNN, there is no set of weights which can be learned such that $$w \sigma'(w h_{t'-k}) \approx 1 $$
e.g. In the 1D case, suppose $h_{t'-k}=1$. The function $w \sigma'(w*1)$ achieves a maximum of $0.224$ at $w=1.5434$. This means the gradient will decay as, $$(0.224)^{t'-t}$$
