Skip to main content
Our aim is to predict the next character given a set of previous characters from our data string. For our RNN implementation, we would take a sequence of length 25 characters as inputs to predict the next character. The notation used here was introduced first here. This minimal character-level Vanilla RNN model was first written by Andrej Karpathy (@karpathy) and was decorated with the forward and backprop equations by students of the CS-GY-6613 course as part of an asignment.
Inputs to RNN
  • x1x_1 to x25x_{25} is the input sequence of 25 characters, one character given as input to RNN at each time step
Hidden state of RNN
  • The state consists of a single ‘hidden’ vector h
  • At every time step, a recurrence function fWf_W with parameters WxhW_{xh}, WhhW_{hh} and bhb_h is applied to the input xtx_t and the output from the previous hidden state ht−1h_{t-1}, to generate hth_t
ht=fW(ht−1,xt) \qquad \qquad \qquad \qquad h_t = f_W (h_{t-1},x_t)         =tanh⁡(Whhht−1+Wxhxt+bh) \qquad \qquad \qquad \qquad \; \; \; \; = \tanh (W_{hh}h_{t-1} + W_{xh}x_t + b_h) Outputs of the RNN
  • y^T\hat y_T is the character that our network would predict after T=25T=25 time steps
  • At each time step, a oto_t is calculated as
ot=Whyht+by \qquad \qquad \qquad \qquad o_t = W_{hy}h_t + b_y
  • The softmax of oto_t is the set of probabilities of occurance of each unique character in the input data
y^t=softmax(ot) \qquad \qquad \qquad \qquad \hat y_t = \mathtt{softmax}(o_t)
  • At each time step, from t=1t=1 to 2525, loss is calculated from the set of predicted probabilities.
Lt=CE(y^t,yt) \qquad \qquad \qquad \qquad L_t = \mathtt{CE}(\hat y_t, y_t) \qquad where the yty_t is the next character to the input sequence in the data string
  • The total loss is the sum of all the losses from the previously unrolled steps
L=∑t=024Lt \qquad \qquad \qquad \qquad L = ∑_{t=0}^{24}L_t All the weights WxhW_{xh}, WhhW_{hh}, bhb_h, WhyW_{hy} and byb_y are reused at each time step. Hyperparameters
  • the size of hidden state of neurons
  • the sequence length or the time steps to unroll, which is 25 in our case
  • optimizer we use here is Adagrad
  • the learning rate for Adagrad optimizer
Dimensions of tensors Input:
  • Each character from the data string is pre-processed before being fed then into the RNN
  • From each sequence of 25 characters (for 25 time-steps) from the data string, we create an ‘inputs’ list of tokenized integer values
  • Each character is converted to an integer token index using ‘char_to_ix’ function, which maps each character to a number between 0 and 42 (as there are 43 unique characters in our data)
  • The integer tokens from the ‘inputs’ list are then one-hot encoded in 1-of-k representations, ie, into vectors of size 43 (k=43 unique characters in our data), which are fed as inputs to the RNN
\qquad => dimension of input xt=x_t = (43,1) Targets (yty_t):
  • For each input in the ‘inputs’ list, we create a ‘target’ list consisting of the subsequent character’s integer token
  • Our targets list, which is used during the cross-entropy loss calculation, is of length 25
Predicted output:
  • The predicted outputs are the probabilities of the next characters
  • Since k=43 unique characters, the unnormalized logits for next chars is
\qquad => dimension of output ot=o_t = (43,1)
  • The softmax(ot)softmax(o_t) gives the class probabilities for next characters
  • The probabilities are then converted into one-hot encoded vectors using arg⁡max⁡\arg \max
  • The one-hot encoded vectors are converted into integer tokens and then to a single character using ‘ix_to_char’ function
Hidden layers:
  • Since we have chosen 100 neurons in the hidden layer,
\qquad => dimension of hidden state ht=h_t = (100,1) Model parameters:
  • Given the hidden_size=100, input x dimension=(43,1) and output y dimension=(43,1):
\qquad => dimension of Wxh=W_{xh} = (100,43), \qquad => dimension of Whh=W_{hh} = (100,100), \qquad => dimension of bh=b_{h} = (100,1), \qquad => dimension of Why=W_{hy} = (43,100), \qquad => dimension of by=b_{y} = (43,1)
Forward Pass
  • Forward through entire sequence x1x_1 to x25x_{25} to compute loss
  • Calculate hidden states at each time step
ht=tanh(Whhht−1+Wxhxt+bh) \qquad \qquad \qquad \qquad h_t = tanh (W_{hh}h_{t-1} + W_{xh}x_t + b_h)
  • Calculate output yty_t
ot=Whyht+by \qquad \qquad \qquad \qquad o_t = W_{hy}h_t + b_y
  • The softmax of oto_t is the set of probabilities of occurance of each unique character in the input data
y^t=softmax(ot) \qquad \qquad \qquad \qquad \hat y_t = softmax(o_t)
  • Calculate loss at each time step
Lt=Cross  Entropy(y^t,yt) \qquad \qquad \qquad \qquad L_t = Cross\;Entropy(\hat y_t, y_t)
  • Calculate the total loss, which is the negative log likelihood of our model
L=∑t=024Lt \qquad \qquad \qquad \qquad L = ∑_{t=0}^{24}L_t         =−∑tlog  pmodel(yt∣x1,...,xt) \qquad \qquad \qquad \qquad \; \; \; \; = - ∑_t log \; p_{model} (y_t | x_1,...,x_t) Backpropogation Through Time
  • Backward through entire sequence to compute gradient
  • The nodes include parameters WxhW_{xh}, WhhW_{hh}, bhb_h, WhyW_{hy} and byb_y
  • The inputs and outputs of nodes are xtx_t, hth_t, yty_t, ptp_t and LtL_t at time-step tt
  • We’ll use the suffix (i)(i) to indicate the ithi^{th} sample
Gradients on the internal nodes:
  • We’ll be computing the gradients recursively starting with the nodes immediately preceding the final loss
∂L∂Lt=1\qquad \qquad \qquad \qquad \frac{\partial L}{\partial L_t} = 1
  • The gradient with respect to the softmax layer would be:
∂L∂y(i)t=p(i)t−1\qquad \qquad \qquad \qquad \frac{\partial L}{\partial y_{(i)t}} = p_{(i)t} -1
  • At t=25, the gradient with respect to the hidden layer would be:
∂L∂ht=25=WhyT∂L∂yt=25\qquad \qquad \qquad \qquad \frac{\partial L}{\partial h_{t=25}} = {W_{hy}}^T \frac{\partial L}{\partial y_{t=25}}
  • We can now iterate backwards from t=24 down to t=1:
∂L∂ht=(∂ht+1∂ht)T∂L∂ht+1+(∂yt∂ht)T∂L∂yt\qquad \qquad \qquad \qquad \frac{\partial L}{\partial h_{t}} = \bigg(\frac{\partial h_{t+1}}{\partial h_{t}}\bigg)^T \frac{\partial L}{\partial h_{t+1}} + \bigg(\frac{\partial y_{t}}{\partial h_{t}}\bigg)^T \frac{\partial L}{\partial y_{t}} =(Whh)T  diag(1−(ht+1)2)∂L∂ht+1+(Why)T∂L∂yt\qquad \qquad \qquad \qquad \qquad = (W_{hh})^T \; diag\bigg(1-(h_{t+1})^2\bigg) \frac{\partial L}{\partial h_{t+1}} + (W_{hy})^T \frac{\partial L}{\partial y_{t}} \qquad \qquad where diag(1−(ht+1)2)diag\bigg(1-(h_{t+1})^2\bigg) indicates the diagonal matrix containing the elements 1−(h(i)t+1)21-(h_{(i)t+1})^2 Gradients on the parameter nodes:
  • Gradients with respect to WhyW_{hy}:
∂L∂Why=∑t∑i∂L∂y(i)t∂y(i)t∂Why\qquad \qquad \qquad \qquad \frac{\partial L}{\partial W_{hy}} = \sum_t \sum_i \frac{\partial L}{\partial y_{(i)t}} \frac{\partial y_{(i)t}}{\partial W_{hy}} =∑t∂L∂yt(ht)T \qquad \qquad \qquad \qquad \qquad = \sum_t \frac{\partial L}{\partial y_t} (h_t)^T
  • Gradients with respect to byb_y:
∂L∂by=∑t(∂yt∂by)T∂L∂yt\qquad \qquad \qquad \qquad \frac{\partial L}{\partial b_{y}} = \sum_t \bigg(\frac{\partial y_t}{\partial b_{y}}\bigg)^T \frac{\partial L}{\partial y_{t}} =∑t∂L∂yt\qquad \qquad \qquad \qquad \qquad = \sum_t \frac{\partial L}{\partial y_{t}}
  • Gradients with respect to WhhW_{hh}:
∂L∂Whh=∑t∑i∂L∂h(i)t∂h(i)t∂Whh\qquad \qquad \qquad \qquad \frac{\partial L}{\partial W_{hh}} = \sum_t \sum_i \frac{\partial L}{\partial h_{(i)t}} \frac{\partial h_{(i)t}}{\partial W_{hh}} =∑tdiag(1−(ht)2)∂L∂ht(ht−1)T \qquad \qquad \qquad \qquad \qquad = \sum_t diag\bigg(1-(h_{t})^2\bigg) \frac{\partial L}{\partial h_t} (h_{t-1})^T
  • Gradients with respect to bhb_h:
∂L∂bh=∑t(∂ht∂bh)T∂L∂ht\qquad \qquad \qquad \qquad \frac{\partial L}{\partial b_{h}} = \sum_t \bigg(\frac{\partial h_t}{\partial b_{h}}\bigg)^T \frac{\partial L}{\partial h_{t}} =∑tdiag(1−(ht)2)∂L∂ht\qquad \qquad \qquad \qquad \qquad = \sum_t diag\bigg(1-(h_{t})^2\bigg) \frac{\partial L}{\partial h_{t}}
  • Gradients with respect to WxhW_{xh}:
∂L∂Wxh=∑t∑i∂L∂h(i)t∂h(i)t∂Wxh\qquad \qquad \qquad \qquad \frac{\partial L}{\partial W_{xh}} = \sum_t \sum_i \frac{\partial L}{\partial h_{(i)t}} \frac{\partial h_{(i)t}}{\partial W_{xh}} =∑tdiag(1−(ht)2)∂L∂ht(xt)T \qquad \qquad \qquad \qquad \qquad = \sum_t diag\bigg(1-(h_{t})^2\bigg) \frac{\partial L}{\partial h_t} (x_t)^T

​
PyTorch reference

Edit this page on GitHub or file an issue.