Long short-term memory

Machine learning and data mining
Problems Classification Clustering Regression Anomaly detection AutoML Association rules Reinforcement learning Structured prediction Feature engineering Feature learning Online learning Semi-supervised learning Unsupervised learning Learning to rank Grammar induction
Supervised learning (classification • regression) Decision trees Ensembles Bagging Boosting Random forest k-NN Linear regression Naive Bayes Artificial neural networks Logistic regression Perceptron Relevance vector machine (RVM) Support vector machine (SVM)
Clustering BIRCH CURE Hierarchical k-means Expectation–maximization (EM) DBSCAN OPTICS Mean-shift
Dimensionality reduction Factor analysis CCA ICA LDA NMF PCA t-SNE
Structured prediction Graphical models Bayes net Conditional random field Hidden Markov
Anomaly detection k-NN Local outlier factor
Artificial neural networks Autoencoder Deep learning DeepDream Multilayer perceptron RNN LSTM GRU) Restricted Boltzmann machine SOM Convolutional neural network U-Net
Reinforcement learning Q-learning SARSA Temporal difference (TD)
Theory Bias-variance dilemma Computational learning theory Empirical risk minimization Occam learning PAC learning Statistical learning VC theory
Machine-learning venues NIPS ICML ML JMLR ArXiv:cs.LG
Glossary of artificial intelligence Glossary of artificial intelligence
Related articles List of datasets for machine-learning research Outline of machine learning
Machine learning portal

The Long Short-Term Memory (LSTM) cell can process data sequentially and keep its hidden state through time.

Long short-term memory (LSTM) units are units of a recurrent neural network (RNN). An RNN composed of LSTM units is often called an LSTM network (or just LSTM). A common LSTM unit is composed of a cell, an input gate, an output gate and a forget gate. The cell remembers values over arbitrary time intervals and the three gates regulate the flow of information into and out of the cell.

LSTM networks are well-suited to classifying, processing and making predictions based on time series data, since there can be lags of unknown duration between important events in a time series. LSTMs were developed to deal with the exploding and vanishing gradient problems that can be encountered when training traditional RNNs. Relative insensitivity to gap length is an advantage of LSTM over RNNs, hidden Markov models and other sequence learning methods in numerous applications.

History

LSTM was proposed in 1997 by Sepp Hochreiter and Jürgen Schmidhuber. By introducing Constant Error Carousel (CEC) units, LSTM deals with the exploding and vanishing gradient problems.The initial version of LSTM block included cells, input and output gates.

In 1999, Felix Gers introduced the forget gate (also called “keep gate”) into LSTM architecture, enabling the LSTM to reset its own state.

In 2000, Felix Gers & Jürgen Schmidhuber added peephole connections (connections from the cell to the gates) into the architecture. Additionally, the output activation function was omitted.

In 2014, Kyunghyun Cho et al. put forward a simplified variant called Gated recurrent unit (GRU).

Among other successes, LSTM achieved record results in natural language text compression, unsegmented connected handwriting recognition and won the ICDAR handwriting competition (2009). LSTM networks were a major component of a network that achieved a record 17.7% phoneme error rate on the classic TIMIT natural speech dataset (2013).

As of 2016, major technology companies including Google, Apple, and Microsoft were using LSTM as fundamental components in new products. For example, Google used LSTM for speech recognition on the smartphone, for the smart assistant Allo and for Google Translate. Apple uses LSTM for the "Quicktype" function on the iPhone and for Siri. Amazon uses LSTM for Amazon Alexa.

In 2017 researchers from Michigan State University, IBM Research, and Cornell University published a study in the Knowledge Discovery and Data Mining (KDD) conference. Their study describes a novel neural network that performs better than the widely used long short-term memory neural network.

Further in 2017 Microsoft reported reaching 95.1% recognition accuracy on the Switchboard corpus, incorporating a vocabulary of 165,000 words. The approach used "dialog session-based long-short-term memory".

Idea

In theory, classic (or "vanilla") RNNs can keep track of arbitrary long-term dependencies in the input sequences. The problem of vanilla RNNs is computational (or practical) in nature: when training a vanilla RNN using back-propagation, the gradients which are back-propagated can "vanish" (that is, they can tend to zero) or "explode" (that is, they can tend to infinity), because of the computations involved in the process, which use finite-precision numbers. RNNs using LSTM units partially solve the vanishing gradient problem, because LSTM units allow gradients to also flow unchanged. However, LSTM networks can still suffer from the exploding gradient problem.

Architecture

There are several architectures of LSTM units. A common architecture is composed of a cell (the memory part of the LSTM unit) and three "regulators", usually called gates, of the flow of information inside the LSTM unit: an input gate, an output gate and a forget gate. Some variations of the LSTM unit do not have one or more of these gates or maybe have other gates. For example, gated recurrent units (GRUs) do not have an output gate.

Intuitively, the cell is responsible for keeping track of the dependencies between the elements in the input sequence. The input gate controls the extent to which a new value flows into the cell, the forget gate controls the extent to which a value remains in the cell and the output gate controls the extent to which the value in the cell is used to compute the output activation of the LSTM unit. The activation function of the LSTM gates is often the logistic function.

There are connections into and out of the LSTM gates, a few of which are recurrent. The weights of these connections, which need to be learned during training, determine how the gates operate.

Variants

In the equations below, the lowercase variables represent vectors. Matrices $W_{q}$ and $U_{q}$ contain, respectively, the weights of the input and recurrent connections, where the subscript $_{q}$ can either be the input gate $i$, output gate $o$, the forget gate $f$ or the memory cell $c$, depending on the activation being calculated. In this section, we are thus using a "vector notation". So, for example, $c_{t}\in \mathbb {R} ^{h}$ is not just one cell of one LSTM unit, but contains $h$ LSTM unit's cells.

LSTM with a forget gate

The compact forms of the equations for the forward pass of an LSTM unit with a forget gate are:

${\begin{aligned}f_{t}&=\sigma _{g}(W_{f}x_{t}+U_{f}h_{t-1}+b_{f})\\i_{t}&=\sigma _{g}(W_{i}x_{t}+U_{i}h_{t-1}+b_{i})\\o_{t}&=\sigma _{g}(W_{o}x_{t}+U_{o}h_{t-1}+b_{o})\\c_{t}&=f_{t}\circ c_{t-1}+i_{t}\circ \sigma _{c}(W_{c}x_{t}+U_{c}h_{t-1}+b_{c})\\h_{t}&=o_{t}\circ \sigma _{h}(c_{t})\end{aligned}}$

where the initial values are $c_{0}=0$ and $h_{0}=0$ and the operator $\circ$ denotes the Hadamard product (element-wise product). The subscript $t$ indexes the time step.

Variables

• $x_{t}\in \mathbb {R} ^{d}$: input vector to the LSTM unit
• $f_{t}\in \mathbb {R} ^{h}$: forget gate's activation vector
• $i_{t}\in \mathbb {R} ^{h}$: input gate's activation vector
• $o_{t}\in \mathbb {R} ^{h}$: output gate's activation vector
• $h_{t}\in \mathbb {R} ^{h}$: hidden state vector also known as output vector of the LSTM unit
• $c_{t}\in \mathbb {R} ^{h}$: cell state vector
• $W\in \mathbb {R} ^{h\times d}$, $U\in \mathbb {R} ^{h\times h}$ and $b\in \mathbb {R} ^{h}$: weight matrices and bias vector parameters which need to be learned during training

where the superscripts $d$ and $h$ refer to the number of input features and number of hidden units, respectively.

Activation functions

• $\sigma _{g}$: sigmoid function.
• $\sigma _{c}$: hyperbolic tangent function.
• $\sigma _{h}$: hyperbolic tangent function or, as the peephole LSTM paper suggests, $\sigma _{h}(x)=x$.

Peephole LSTM

A peephole LSTM unit with input (i.e. $i$), output (i.e. $o$), and forget (i.e. $f$) gates. Each of these gates can be thought as a "standard" neuron in a feed-forward (or multi-layer) neural network: that is, they compute an activation (using an activation function) of a weighted sum. $i_{t},o_{t}$ and $f_{t}$ represent the activations of respectively the input, output and forget gates, at time step $t$. The 3 exit arrows from the memory cell $c$ to the 3 gates $i,o$ and $f$ represent the peephole connections. These peephole connections actually denote the contributions of the activation of the memory cell $c$ at time step $t-1$, i.e. the contribution of $c_{t-1}$ (and not $c_{t}$, as the picture may suggest). In other words, the gates $i,o$ and $f$ calculate their activations at time step $t$ (i.e., respectively, $i_{t},o_{t}$ and $f_{t}$) also considering the activation of the memory cell $c$ at time step $t-1$, i.e. $c_{t-1}$. The single left-to-right arrow exiting the memory cell is not a peephole connection and denotes $c_{t}$. The little circles containing a $\times$ symbol represent an element-wise multiplication between its inputs. The big circles containing an S-like curve represent the application of a differentiable function (like the sigmoid function) to a weighted sum. There are many other kinds of LSTMs as well.

The figure on the right is a graphical representation of an LSTM unit with peephole connections (i.e. a peephole LSTM). Peephole connections allow the gates to access the constant error carousel (CEC), whose activation is the cell state. $h_{t-1}$ is not used, $c_{t-1}$ is used instead in most places.

${\begin{aligned}f_{t}&=\sigma _{g}(W_{f}x_{t}+U_{f}c_{t-1}+b_{f})\\i_{t}&=\sigma _{g}(W_{i}x_{t}+U_{i}c_{t-1}+b_{i})\\o_{t}&=\sigma _{g}(W_{o}x_{t}+U_{o}c_{t-1}+b_{o})\\c_{t}&=f_{t}\circ c_{t-1}+i_{t}\circ \sigma _{c}(W_{c}x_{t}+U_{c}c_{t-1}+b_{c})\\h_{t}&=o_{t}\circ \sigma _{h}(c_{t})\end{aligned}}$

Peephole convolutional LSTM

Peephole convolutional LSTM. The $*$ denotes the convolution operator.

${\begin{aligned}f_{t}&=\sigma _{g}(W_{f}*x_{t}+U_{f}*h_{t-1}+V_{f}\circ c_{t-1}+b_{f})\\i_{t}&=\sigma _{g}(W_{i}*x_{t}+U_{i}*h_{t-1}+V_{i}\circ c_{t-1}+b_{i})\\o_{t}&=\sigma _{g}(W_{o}*x_{t}+U_{o}*h_{t-1}+V_{o}\circ c_{t-1}+b_{o})\\c_{t}&=f_{t}\circ c_{t-1}+i_{t}\circ \sigma _{c}(W_{c}*x_{t}+U_{c}*h_{t-1}+b_{c})\\h_{t}&=o_{t}\circ \sigma _{h}(c_{t})\end{aligned}}$

Training

To minimize LSTM's total error on a set of training sequences, an optimization algorithm, like gradient descent, combined with backpropagation through time to compute the gradients needed during the optimization process, is often employed, so as to change each weight of the LSTM network in proportion to the derivative of the error (at the output layer of the LSTM network) with respect to corresponding weight.

A problem with using gradient descent for standard RNNs is that error gradients vanish exponentially quickly with the size of the time lag between important events. This is due to $\lim _{n\to \infty }W^{n}=0$ if the spectral radius of $W$ is smaller than 1.

However, with LSTM units, when error values are back-propagated from the output layer, the error remains in the LSTM unit's cell. This "error carousel" continuously feeds error back to each of the LSTM unit's gates, until they learn to cut off the value.

CTC score function

Many applications use stacks of LSTM RNNs and train them by connectionist temporal classification (CTC) to find an RNN weight matrix that maximizes the probability of the label sequences in a training set, given the corresponding input sequences. CTC achieves both alignment and recognition.

Applications

Applications of LSTM include:

• Robot control
• Time series prediction
• Speech recognition
• Rhythm learning
• Music composition
• Grammar learning
• Handwriting recognition
• Human action recognition
• Sign Language Translation
• Protein Homology Detection
• Predicting subcellular localization of proteins
• Time series anomaly detection
• Several prediction tasks in the area of business process management
• Prediction in medical care pathways
• Semantic parsing
• Object Co-segmentation

See also

• Recurrent neural network
• Gated recurrent unit
• Differentiable neural computer
• Long-term potentiation
• Prefrontal cortex basal ganglia working memory
• Time series

External links

• Recurrent Neural Networks with over 30 LSTM papers by Jürgen Schmidhuber's group at IDSIA
• Gers, Felix (2001). "Long Short-Term Memory in Recurrent Neural Networks" (PDF). PhD thesis.
• Gers, Felix A.; Schraudolph, Nicol N.; Schmidhuber, Jürgen (Aug 2002). "Learning precise timing with LSTM recurrent networks" (PDF). Journal of Machine Learning Research. 3: 115–143.
• Abidogun, Olusola Adeniyi (2005). "Data Mining, Fraud Detection and Mobile Telecommunications: Call Pattern Analysis with Unsupervised Neural Networks". Master's Thesis. hdl:11394/249. Archived (PDF) from the original on May 22, 2012.
  • original with two chapters devoted to explaining recurrent neural networks, especially LSTM.
• Monner, Derek D.; Reggia, James A. (2010). "A generalized LSTM-like training algorithm for second-order recurrent neural networks" (PDF). High-performing extension of LSTM that has been simplified to a single node type and can train arbitrary architectures
• Herta, Christian. "How to implement LSTM in Python with Theano". Tutorial.
• Chevalier, Guillaume. Tutorial: How to use LSTMs with TensorFlow in Python on cellphone sensor data on GitHub