The RNN abstraction

• On a high level, the RNN is a function that

  • Takes as input an arbitrary length ordered sequence of n$n$ din$d_{\text{in}}$-dimensional vectors x1:n=x1,…,xn$x_{1:n}=x_1,\dots ,x_n$, and
  • Returns as output a single dout$d_{\text{out}}$ dimensional vector yn$y_n$
  • The output vector yn$y_n$ is then used for further prediction yn=RNN(x1:n)xi∈Rdin,yn∈Rdout$$\begin{array}{cc}& y_n=\text{RNN}\left(x_{1:n}\right)\\ & x_i\in R^{d_{\text{in}}},y_n\in R^{d_{\text{out}}}\end{array}$$

• This implicitly defines an output vector yi$y_i$ for each prefix x1:i$x_{1:i}$. We denote by RNN∗${}^{\ast }$ the function returning this sequence y1:n=RNN∗(x1:n)yi=RNN(x1:i)xi∈Rdin,yi∈Rdout$$\begin{array}{cc}& y_{1:n}={\text{RNN}}^{\ast }\left(x_{1:n}\right)\\ & y_i=\text{RNN}\left(x_{1:i}\right)\\ & x_i\in R^{d_{\text{in}}},y_i\in R^{d_{\text{out}}}\end{array}$$

• The RNN function provides a framework for conditioning on the entire history x1,…,xi$x_1,\dots ,x_i$ without the Markov assumption

The R function and the O function

• The RNN is defined recursively, by means of a function R$R$ taking as the state vector si−1$s_{i-1}$ and an input vector xi$x_i$ and returning a new state vector si$s_i$

• The state vector si$s_i$ is then mapped to an output vector yi$y_i$ using a simple deterministic function O$O$ si=R(si−1,xi)yi=O(si)$$\begin{array}{cc}{s}_i& =R(s_{i-1},x_i)\\ y_i& =O\left(s_i\right)\end{array}$$

• The functions R$R$ and O$O$ are the same across the sequence positions, but the RNN keeps track of the states of computation through the state vector si$s_i$ that is kept and being passed across invocations of R$R$

An illustration of the RNN

• We include here the parameters θ$\theta$ in order to highlight the fact that the same parameters are shared across all time steps

An illustration of the RNN (unrolled)

Common RNN usage patterns: acceptor

• Acceptor: based on the supervision signal only at the final output vector yn$y_n$

  • Typically, the RNN’s output vector yn$y_n$ is fed into a fully connected layer or an MLP, which produce a prediction

Common RNN usage patterns: encoder

• Encoder: also only uses the final output vector yn$y_n$. Here yn$y_n$ is treated as an encoding of the information in the sequence, and is used as additional information together with other signals

Common RNN usage patterns: transducer

• Transducer: The loss of unrolled sequence will be used

• A natural use case of the transduction is for language modeling, where the sequence of words x1:i$x_{1:i}$ is used to predict a distribution over the (i+1)$(i+1)$th word

• RNN based lanuage models are shown to provide vastly better perplxities than traditional language models

• Using RNNs as transducers allows us to relax the Markov assumption and condition on the entire prediction history

An illustration of transducer

Bidirectional RNNs (biRNN)

• A useful elaboration of an RNN is a biRNN

• Consider an input sequence x1:n$x_{1:n}$. The biRNN works by maintaining two separate states, sfi$s_i^f$ and sbi$s_i^b$ for each input position i$i$

  • The forward state sfi$s_i^f$ is based on x1,x2,…,xi$x_1,x_2,\dots ,x_i$
  • The backward state sbi$s_i^b$ is based on xn,xn−1,…,xi$x_n,x_{n-1},\dots ,x_i$

• The output at position i$i$ is based on the concatenation of the two output vectors yi=[yfi;ybi]=[Of(sfi);Ob(sbi)]$$y_i=[y_i^f;y_i^b]=\left[O^f\right(s_i^f);O^b(s_i^b\left)\right]$$

• Thus, we define biRNN as biRNN(x1:n,i)=yi=[RNNf(x1:i),RNNb(xn:i)]$$\text{biRNN}(x_{1:n},i)=y_i=\left[{\text{RNN}}^f\right(x_{1:i}),{\text{RNN}}^b(x_{n:i}\left)\right]$$

An illustration of biRNN

Deep (multi-layer stacked) RNNs

• The input for the first RNN are x1:n$x_{1:n}$, while the input of the j$j$th RNN (j≥2$j\ge 2$) are the outputs of the RNN below it, yj−11:n$y_{1:n}^{j-1}$

• While it is not theoretically clear what is the additional power gained by the deeper architecture, it was observed empirically that deep RNNs work better than shallower ones on some tasks

• The author’s experience: using two or more layers indeed often improves over using a single one

A note on reading the literature

• Unfortunately, it is often the case that inferring the exact model form from reading its description in a research paper can be quite challenging

• For example,
  • The inputs to the RNN can be either one-hot vectors or embedded representations
  • The input sequence can be padded with start-of-sequence and/or end-of-sequence symbols, or not

An illustration of deep RNN

Simple RNN (SRNN)

• The nonlinear function g$g$ is usually tanh or ReLU

• The output function O(⋅)$O(\cdot )$ is the identify function si=RSRNN(xi,si−1)=g(si−1Ws+xiWx+b)yi=OSRNN(si)=si$$\begin{array}{cc}{s}_i& =R_{\text{SRNN}}(x_i,s_{i-1})=g(s_{i-1}{W}^s+x_i{W}^x+b)\\ y_i& =O_{\text{SRNN}}\left(s_i\right)=s_i\end{array}$$ si,yi∈Rds,xi∈Rdx,Wx∈Rdx×ds,Ws∈Rds×ds,b∈Rds$$s_i,y_i\in R^{d_s},x_i\in R^{d_x},W^x\in R^{d_x\times d_s},W^s\in R^{d_s\times d_s},b\in R^{d_s}$$

• SRNN is hard to train effectively because of the vanishing gradients problem

Gated architectures

• An apparent problem with SRNN is that the memory access is not controlled. At each step of the computation, the entire memory state is read, and the entire memory state is written

• We denote the hadamard-product operation (element-wise product) as ⊙$\odot$

• To control memory access, consider a binary vector g∈{0,1}n$g\in \{0,1{\}}^n$

• For a memory s∈Rd$s\in R^d$ and an input x∈Rd$x\in R^d$, the computation

s′⟵g⊙x+(1−g)⊙s$$s^{\prime }⟵g\odot x+(1-g)\odot s$$ “reads” the entries in x$x$ that correspond to the 1 values in g$g$, and writes them to the new memory s′$s^{\prime }$. Locations that weren’t read to are copied from the memory s$s$ to the new memory s′$s^{\prime }$ through the use of the gate (1−g)$(1-g)$

An illustration of binary gate

Differentiable gates

• The gates should not be static, but be controlled by the current memory state and the input, and their behavior should be learned

• Obstacle: learning in our framework entails being differentiable (because of the backpropagation algorithm), but the binary 0-1 values used in th e gates are not differentiable

• Solution: approximate the hard gating mechanism with a soft, but diffrentiable, gating mechanism

• To achieve these differentiable gates, we replace the requirement that g∈{0,1}n$g\in \{0,1{\}}^n$, and allow arbitrary real numbers g′∈Rn$g^{\prime }\in R^n$. These are then passed through a sigmoid function σ(g′)$\sigma \left(g^{\prime }\right)$, which take values in the range (0,1)$(0,1)$

LSTM

• Long Short-Term Memory (LSTM): explicitly splits the state vector si$s_i$ into two halves, where one half is treated as “memory cells” cj$c_j$, and the hidden state component hj$h_j$

sj=RLSTM(sj−1,xj)=[cj;hj]$$s_j={\text{R}}_{\text{LSTM}}(s_{j-1},x_j)=[c_j;h_j]$$

• There are three gates, i$i$nput, f$f$orget, and o$o$utput cj=f⊙cj−1+i⊙zz=tanh(xjWxz+hj−1Whz)hj=o⊙tanh(cj)yj=OLSTM(sj)=hj$$\begin{array}{cc}{c}_j& =f\odot c_{j-1}+i\odot z\\ z& =\text{tanh}(x_j{W}^{xz}+h_{j-1}{W}^{hz})\\ h_j& =o\odot \text{tanh}\left(c_j\right)\\ y_j& =O_{\text{LSTM}}\left(s_j\right)=h_j\end{array}$$

LSTM gates

• The gates are based on xj,hj−1$x_j,h_{j-1}$ and are passed through a sigmoid activation function i=σ(xjWxi+hj−1Whi)f=σ(xjWxf+hj−1Whf)o=σ(xjWxo+hj−1Who)$$\begin{array}{cc}i& =\sigma (x_j{W}^{xi}+h_{j-1}{W}^{hi})\\ f& =\sigma (x_j{W}^{xf}+h_{j-1}{W}^{hf})\\ o& =\sigma (x_j{W}^{xo}+h_{j-1}{W}^{ho})\end{array}$$

• When training LSTM networks, it is strongly recommended to always initialize the bias term of the forget gate to be close to one

GRU

• Gated Recurrent Unit (GRU) is shown to perform comparably to the LSTM on several datasets

• GRU has substantially fewer gates that LSTM and doesn’t have a separate memory component sj=RGRU(sj−1,xj)=(1−z)⊙sj−1+z⊙˜sj˜sj=tanh(xjWxs+(r⊙sj−1)Wsg)yj=OGRU(sj)=sj

• Gate r controls access to the previous state sj−1 in ˜sj

• Gate z controls the proportions of the interpolation between sj−1 and ˜sj when in the updated state sj z=σ(xjWxz+sj−1Wsz)r=σ(xjWxr+sj−1Wsr)

Acceptors

• The simplest use of RNN: read in an input sequence, and produce a binary of multi-class answer at the end

• The power of RNN is often not needed for many natural language classification tasks, because the word-order and sentence structure turn out to not be very important in many cases, and bag-of-words or bag-of-ngrams classifier often works just as well or even better than RNN acceptors

Sentiment classification: sentence level

• The sentence level sentiment classification is straightforward to model using an RNN acceptor:

  • Tokenization
  • RNN reads in the words of the sentence one at a time
  • The final RNN state is then fed into a MLP followed by a softmax-layer with two outputs
  • The network is trained with cross-entropy loss based on the gold sentiment labels p(label=k∣w1:n)=ˆy[k]ˆy=softmax{MLP[RNN(x1:n)]}x1:n=E[w1],…,E[wn]

• biRNN: it is often helpful to extend the RNN model into the biRNN ˆy=softmax{MLP[RNNf(x1:n);RNNb(xn:1)]}

Hierarchical biRNN

• For longer sentences, it can be useful to use a hierarchical architecture, in which the sentence is split into smaller spans based on punctuation

• Suppose a sentence w1:n is split into m spans w11:ℓ1,…,wm1:ℓm, then the architecture is p(label=k∣w1:n)=ˆy[k]ˆy=softmax{MLP[RNN(z1:m)]}zi=[RNNf(xi1:ℓi),RNNb(xiℓi:1)]xi1:ℓi=E[wi1],…,E[wiℓi]

• Each of the m different spans may convey a different sentiment

• The higher-level acceptor reads the summary z1:m produced by the lower level encoder, and decides on the overall sentiment

Document level sentiment classification

• Document level sentiment classification and harder than sentence level classification

• A hierarchical architecture is useful:

  • Each sentence si is encoded using a gated RNN, producing a vector zi
  • The vectors z1:n are then fed into a second gated RNN, producing a vector h=RNN(z1:n)
  • h is then used fro prediction ˆy=softmax(MLP(h))

• Keeping all intermediate vectors of the document-level RNN produces slightly higher results in some cases h1:n=RNN∗(z1:n)ˆy=softmax(MLP(1nn∑i=1hi))

References

• Goldberg, Yoav. (2017). Neural Network Methods for Natural Language Processing, Morgan & Claypool