453 lines
24 KiB
Plaintext
453 lines
24 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "3727da18",
|
|
"metadata": {
|
|
"origin_pos": 0
|
|
},
|
|
"source": [
|
|
"# Backpropagation Through Time\n",
|
|
":label:`sec_bptt`\n",
|
|
"\n",
|
|
"If you completed the exercises in :numref:`sec_rnn-scratch`,\n",
|
|
"you would have seen that gradient clipping is vital \n",
|
|
"for preventing the occasional massive gradients\n",
|
|
"from destabilizing training.\n",
|
|
"We hinted that the exploding gradients\n",
|
|
"stem from backpropagating across long sequences.\n",
|
|
"Before introducing a slew of modern RNN architectures,\n",
|
|
"let's take a closer look at how *backpropagation*\n",
|
|
"works in sequence models in mathematical detail.\n",
|
|
"Hopefully, this discussion will bring some precision \n",
|
|
"to the notion of *vanishing* and *exploding* gradients.\n",
|
|
"If you recall our discussion of forward and backward \n",
|
|
"propagation through computational graphs\n",
|
|
"when we introduced MLPs in :numref:`sec_backprop`,\n",
|
|
"then forward propagation in RNNs\n",
|
|
"should be relatively straightforward.\n",
|
|
"Applying backpropagation in RNNs \n",
|
|
"is called *backpropagation through time* :cite:`Werbos.1990`.\n",
|
|
"This procedure requires us to expand (or unroll) \n",
|
|
"the computational graph of an RNN\n",
|
|
"one time step at a time.\n",
|
|
"The unrolled RNN is essentially \n",
|
|
"a feedforward neural network \n",
|
|
"with the special property \n",
|
|
"that the same parameters \n",
|
|
"are repeated throughout the unrolled network,\n",
|
|
"appearing at each time step.\n",
|
|
"Then, just as in any feedforward neural network,\n",
|
|
"we can apply the chain rule, \n",
|
|
"backpropagating gradients through the unrolled net.\n",
|
|
"The gradient with respect to each parameter\n",
|
|
"must be summed across all places \n",
|
|
"that the parameter occurs in the unrolled net.\n",
|
|
"Handling such weight tying should be familiar \n",
|
|
"from our chapters on convolutional neural networks.\n",
|
|
"\n",
|
|
"\n",
|
|
"Complications arise because sequences\n",
|
|
"can be rather long.\n",
|
|
"It is not unusual to work with text sequences\n",
|
|
"consisting of over a thousand tokens. \n",
|
|
"Note that this poses problems both from \n",
|
|
"a computational (too much memory)\n",
|
|
"and optimization (numerical instability)\n",
|
|
"standpoint. \n",
|
|
"Input from the first step passes through\n",
|
|
"over 1000 matrix products before arriving at the output, \n",
|
|
"and another 1000 matrix products \n",
|
|
"are required to compute the gradient. \n",
|
|
"We now analyze what can go wrong and \n",
|
|
"how to address it in practice.\n",
|
|
"\n",
|
|
"\n",
|
|
"## Analysis of Gradients in RNNs\n",
|
|
":label:`subsec_bptt_analysis`\n",
|
|
"\n",
|
|
"We start with a simplified model of how an RNN works.\n",
|
|
"This model ignores details about the specifics \n",
|
|
"of the hidden state and how it is updated.\n",
|
|
"The mathematical notation here\n",
|
|
"does not explicitly distinguish\n",
|
|
"scalars, vectors, and matrices.\n",
|
|
"We are just trying to develop some intuition.\n",
|
|
"In this simplified model,\n",
|
|
"we denote $h_t$ as the hidden state,\n",
|
|
"$x_t$ as input, and $o_t$ as output\n",
|
|
"at time step $t$.\n",
|
|
"Recall our discussions in\n",
|
|
":numref:`subsec_rnn_w_hidden_states`\n",
|
|
"that the input and the hidden state\n",
|
|
"can be concatenated before being multiplied \n",
|
|
"by one weight variable in the hidden layer.\n",
|
|
"Thus, we use $w_\\textrm{h}$ and $w_\\textrm{o}$ to indicate the weights \n",
|
|
"of the hidden layer and the output layer, respectively.\n",
|
|
"As a result, the hidden states and outputs \n",
|
|
"at each time step are\n",
|
|
"\n",
|
|
"$$\\begin{aligned}h_t &= f(x_t, h_{t-1}, w_\\textrm{h}),\\\\o_t &= g(h_t, w_\\textrm{o}),\\end{aligned}$$\n",
|
|
":eqlabel:`eq_bptt_ht_ot`\n",
|
|
"\n",
|
|
"where $f$ and $g$ are transformations\n",
|
|
"of the hidden layer and the output layer, respectively.\n",
|
|
"Hence, we have a chain of values \n",
|
|
"$\\{\\ldots, (x_{t-1}, h_{t-1}, o_{t-1}), (x_{t}, h_{t}, o_t), \\ldots\\}$ \n",
|
|
"that depend on each other via recurrent computation.\n",
|
|
"The forward propagation is fairly straightforward.\n",
|
|
"All we need is to loop through the $(x_t, h_t, o_t)$ triples one time step at a time.\n",
|
|
"The discrepancy between output $o_t$ and the desired target $y_t$ \n",
|
|
"is then evaluated by an objective function \n",
|
|
"across all the $T$ time steps as\n",
|
|
"\n",
|
|
"$$L(x_1, \\ldots, x_T, y_1, \\ldots, y_T, w_\\textrm{h}, w_\\textrm{o}) = \\frac{1}{T}\\sum_{t=1}^T l(y_t, o_t).$$\n",
|
|
"\n",
|
|
"\n",
|
|
"\n",
|
|
"For backpropagation, matters are a bit trickier, \n",
|
|
"especially when we compute the gradients \n",
|
|
"with regard to the parameters $w_\\textrm{h}$ of the objective function $L$. \n",
|
|
"To be specific, by the chain rule,\n",
|
|
"\n",
|
|
"$$\\begin{aligned}\\frac{\\partial L}{\\partial w_\\textrm{h}} & = \\frac{1}{T}\\sum_{t=1}^T \\frac{\\partial l(y_t, o_t)}{\\partial w_\\textrm{h}} \\\\& = \\frac{1}{T}\\sum_{t=1}^T \\frac{\\partial l(y_t, o_t)}{\\partial o_t} \\frac{\\partial g(h_t, w_\\textrm{o})}{\\partial h_t} \\frac{\\partial h_t}{\\partial w_\\textrm{h}}.\\end{aligned}$$\n",
|
|
":eqlabel:`eq_bptt_partial_L_wh`\n",
|
|
"\n",
|
|
"The first and the second factors of the\n",
|
|
"product in :eqref:`eq_bptt_partial_L_wh`\n",
|
|
"are easy to compute.\n",
|
|
"The third factor $\\partial h_t/\\partial w_\\textrm{h}$ is where things get tricky, \n",
|
|
"since we need to recurrently compute the effect of the parameter $w_\\textrm{h}$ on $h_t$.\n",
|
|
"According to the recurrent computation\n",
|
|
"in :eqref:`eq_bptt_ht_ot`,\n",
|
|
"$h_t$ depends on both $h_{t-1}$ and $w_\\textrm{h}$,\n",
|
|
"where computation of $h_{t-1}$\n",
|
|
"also depends on $w_\\textrm{h}$.\n",
|
|
"Thus, evaluating the total derivate of $h_t$ \n",
|
|
"with respect to $w_\\textrm{h}$ using the chain rule yields\n",
|
|
"\n",
|
|
"$$\\frac{\\partial h_t}{\\partial w_\\textrm{h}}= \\frac{\\partial f(x_{t},h_{t-1},w_\\textrm{h})}{\\partial w_\\textrm{h}} +\\frac{\\partial f(x_{t},h_{t-1},w_\\textrm{h})}{\\partial h_{t-1}} \\frac{\\partial h_{t-1}}{\\partial w_\\textrm{h}}.$$\n",
|
|
":eqlabel:`eq_bptt_partial_ht_wh_recur`\n",
|
|
"\n",
|
|
"\n",
|
|
"To derive the above gradient, assume that we have \n",
|
|
"three sequences $\\{a_{t}\\},\\{b_{t}\\},\\{c_{t}\\}$ \n",
|
|
"satisfying $a_{0}=0$ and $a_{t}=b_{t}+c_{t}a_{t-1}$ for $t=1, 2,\\ldots$.\n",
|
|
"Then for $t\\geq 1$, it is easy to show\n",
|
|
"\n",
|
|
"$$a_{t}=b_{t}+\\sum_{i=1}^{t-1}\\left(\\prod_{j=i+1}^{t}c_{j}\\right)b_{i}.$$\n",
|
|
":eqlabel:`eq_bptt_at`\n",
|
|
"\n",
|
|
"By substituting $a_t$, $b_t$, and $c_t$ according to\n",
|
|
"\n",
|
|
"$$\\begin{aligned}a_t &= \\frac{\\partial h_t}{\\partial w_\\textrm{h}},\\\\\n",
|
|
"b_t &= \\frac{\\partial f(x_{t},h_{t-1},w_\\textrm{h})}{\\partial w_\\textrm{h}}, \\\\\n",
|
|
"c_t &= \\frac{\\partial f(x_{t},h_{t-1},w_\\textrm{h})}{\\partial h_{t-1}},\\end{aligned}$$\n",
|
|
"\n",
|
|
"the gradient computation in :eqref:`eq_bptt_partial_ht_wh_recur` satisfies\n",
|
|
"$a_{t}=b_{t}+c_{t}a_{t-1}$.\n",
|
|
"Thus, per :eqref:`eq_bptt_at`, \n",
|
|
"we can remove the recurrent computation \n",
|
|
"in :eqref:`eq_bptt_partial_ht_wh_recur` with\n",
|
|
"\n",
|
|
"$$\\frac{\\partial h_t}{\\partial w_\\textrm{h}}=\\frac{\\partial f(x_{t},h_{t-1},w_\\textrm{h})}{\\partial w_\\textrm{h}}+\\sum_{i=1}^{t-1}\\left(\\prod_{j=i+1}^{t} \\frac{\\partial f(x_{j},h_{j-1},w_\\textrm{h})}{\\partial h_{j-1}} \\right) \\frac{\\partial f(x_{i},h_{i-1},w_\\textrm{h})}{\\partial w_\\textrm{h}}.$$\n",
|
|
":eqlabel:`eq_bptt_partial_ht_wh_gen`\n",
|
|
"\n",
|
|
"While we can use the chain rule to compute $\\partial h_t/\\partial w_\\textrm{h}$ recursively, \n",
|
|
"this chain can get very long whenever $t$ is large.\n",
|
|
"Let's discuss a number of strategies for dealing with this problem.\n",
|
|
"\n",
|
|
"### Full Computation ### \n",
|
|
"\n",
|
|
"One idea might be to compute the full sum in :eqref:`eq_bptt_partial_ht_wh_gen`.\n",
|
|
"However, this is very slow and gradients can blow up,\n",
|
|
"since subtle changes in the initial conditions\n",
|
|
"can potentially affect the outcome a lot.\n",
|
|
"That is, we could see things similar to the butterfly effect,\n",
|
|
"where minimal changes in the initial conditions \n",
|
|
"lead to disproportionate changes in the outcome.\n",
|
|
"This is generally undesirable.\n",
|
|
"After all, we are looking for robust estimators that generalize well. \n",
|
|
"Hence this strategy is almost never used in practice.\n",
|
|
"\n",
|
|
"### Truncating Time Steps###\n",
|
|
"\n",
|
|
"Alternatively,\n",
|
|
"we can truncate the sum in\n",
|
|
":eqref:`eq_bptt_partial_ht_wh_gen`\n",
|
|
"after $\\tau$ steps. \n",
|
|
"This is what we have been discussing so far. \n",
|
|
"This leads to an *approximation* of the true gradient,\n",
|
|
"simply by terminating the sum at $\\partial h_{t-\\tau}/\\partial w_\\textrm{h}$. \n",
|
|
"In practice this works quite well. \n",
|
|
"It is what is commonly referred to as truncated \n",
|
|
"backpropgation through time :cite:`Jaeger.2002`.\n",
|
|
"One of the consequences of this is that the model \n",
|
|
"focuses primarily on short-term influence \n",
|
|
"rather than long-term consequences. \n",
|
|
"This is actually *desirable*, since it biases the estimate \n",
|
|
"towards simpler and more stable models.\n",
|
|
"\n",
|
|
"\n",
|
|
"### Randomized Truncation ### \n",
|
|
"\n",
|
|
"Last, we can replace $\\partial h_t/\\partial w_\\textrm{h}$\n",
|
|
"by a random variable which is correct in expectation \n",
|
|
"but truncates the sequence.\n",
|
|
"This is achieved by using a sequence of $\\xi_t$\n",
|
|
"with predefined $0 \\leq \\pi_t \\leq 1$,\n",
|
|
"where $P(\\xi_t = 0) = 1-\\pi_t$ and \n",
|
|
"$P(\\xi_t = \\pi_t^{-1}) = \\pi_t$, thus $E[\\xi_t] = 1$.\n",
|
|
"We use this to replace the gradient\n",
|
|
"$\\partial h_t/\\partial w_\\textrm{h}$\n",
|
|
"in :eqref:`eq_bptt_partial_ht_wh_recur`\n",
|
|
"with\n",
|
|
"\n",
|
|
"$$z_t= \\frac{\\partial f(x_{t},h_{t-1},w_\\textrm{h})}{\\partial w_\\textrm{h}} +\\xi_t \\frac{\\partial f(x_{t},h_{t-1},w_\\textrm{h})}{\\partial h_{t-1}} \\frac{\\partial h_{t-1}}{\\partial w_\\textrm{h}}.$$\n",
|
|
"\n",
|
|
"\n",
|
|
"It follows from the definition of $\\xi_t$ \n",
|
|
"that $E[z_t] = \\partial h_t/\\partial w_\\textrm{h}$.\n",
|
|
"Whenever $\\xi_t = 0$ the recurrent computation\n",
|
|
"terminates at that time step $t$.\n",
|
|
"This leads to a weighted sum of sequences of varying lengths,\n",
|
|
"where long sequences are rare but appropriately overweighted. \n",
|
|
"This idea was proposed by \n",
|
|
":citet:`Tallec.Ollivier.2017`.\n",
|
|
"\n",
|
|
"### Comparing Strategies\n",
|
|
"\n",
|
|
"\n",
|
|
":label:`fig_truncated_bptt`\n",
|
|
"\n",
|
|
"\n",
|
|
":numref:`fig_truncated_bptt` illustrates the three strategies \n",
|
|
"when analyzing the first few characters of *The Time Machine* \n",
|
|
"using backpropagation through time for RNNs:\n",
|
|
"\n",
|
|
"* The first row is the randomized truncation that partitions the text into segments of varying lengths.\n",
|
|
"* The second row is the regular truncation that breaks the text into subsequences of the same length. This is what we have been doing in RNN experiments.\n",
|
|
"* The third row is the full backpropagation through time that leads to a computationally infeasible expression.\n",
|
|
"\n",
|
|
"\n",
|
|
"Unfortunately, while appealing in theory, \n",
|
|
"randomized truncation does not work \n",
|
|
"much better than regular truncation, \n",
|
|
"most likely due to a number of factors.\n",
|
|
"First, the effect of an observation\n",
|
|
"after a number of backpropagation steps \n",
|
|
"into the past is quite sufficient \n",
|
|
"to capture dependencies in practice. \n",
|
|
"Second, the increased variance counteracts the fact \n",
|
|
"that the gradient is more accurate with more steps. \n",
|
|
"Third, we actually *want* models that have only \n",
|
|
"a short range of interactions. \n",
|
|
"Hence, regularly truncated backpropagation through time \n",
|
|
"has a slight regularizing effect that can be desirable.\n",
|
|
"\n",
|
|
"## Backpropagation Through Time in Detail\n",
|
|
"\n",
|
|
"After discussing the general principle,\n",
|
|
"let's discuss backpropagation through time in detail.\n",
|
|
"In contrast to the analysis in :numref:`subsec_bptt_analysis`,\n",
|
|
"in the following we will show how to compute\n",
|
|
"the gradients of the objective function\n",
|
|
"with respect to all the decomposed model parameters.\n",
|
|
"To keep things simple, we consider \n",
|
|
"an RNN without bias parameters,\n",
|
|
"whose activation function in the hidden layer\n",
|
|
"uses the identity mapping ($\\phi(x)=x$).\n",
|
|
"For time step $t$, let the single example input \n",
|
|
"and the target be $\\mathbf{x}_t \\in \\mathbb{R}^d$ and $y_t$, respectively. \n",
|
|
"The hidden state $\\mathbf{h}_t \\in \\mathbb{R}^h$ \n",
|
|
"and the output $\\mathbf{o}_t \\in \\mathbb{R}^q$\n",
|
|
"are computed as\n",
|
|
"\n",
|
|
"$$\\begin{aligned}\\mathbf{h}_t &= \\mathbf{W}_\\textrm{hx} \\mathbf{x}_t + \\mathbf{W}_\\textrm{hh} \\mathbf{h}_{t-1},\\\\\n",
|
|
"\\mathbf{o}_t &= \\mathbf{W}_\\textrm{qh} \\mathbf{h}_{t},\\end{aligned}$$\n",
|
|
"\n",
|
|
"where $\\mathbf{W}_\\textrm{hx} \\in \\mathbb{R}^{h \\times d}$, $\\mathbf{W}_\\textrm{hh} \\in \\mathbb{R}^{h \\times h}$, and\n",
|
|
"$\\mathbf{W}_\\textrm{qh} \\in \\mathbb{R}^{q \\times h}$\n",
|
|
"are the weight parameters.\n",
|
|
"Denote by $l(\\mathbf{o}_t, y_t)$\n",
|
|
"the loss at time step $t$. \n",
|
|
"Our objective function,\n",
|
|
"the loss over $T$ time steps\n",
|
|
"from the beginning of the sequence is thus\n",
|
|
"\n",
|
|
"$$L = \\frac{1}{T} \\sum_{t=1}^T l(\\mathbf{o}_t, y_t).$$\n",
|
|
"\n",
|
|
"\n",
|
|
"In order to visualize the dependencies among\n",
|
|
"model variables and parameters during computation\n",
|
|
"of the RNN,\n",
|
|
"we can draw a computational graph for the model,\n",
|
|
"as shown in :numref:`fig_rnn_bptt`.\n",
|
|
"For example, the computation of the hidden states of time step 3,\n",
|
|
"$\\mathbf{h}_3$, depends on the model parameters\n",
|
|
"$\\mathbf{W}_\\textrm{hx}$ and $\\mathbf{W}_\\textrm{hh}$,\n",
|
|
"the hidden state of the previous time step $\\mathbf{h}_2$,\n",
|
|
"and the input of the current time step $\\mathbf{x}_3$.\n",
|
|
"\n",
|
|
"\n",
|
|
":label:`fig_rnn_bptt`\n",
|
|
"\n",
|
|
"As just mentioned, the model parameters in :numref:`fig_rnn_bptt` \n",
|
|
"are $\\mathbf{W}_\\textrm{hx}$, $\\mathbf{W}_\\textrm{hh}$, and $\\mathbf{W}_\\textrm{qh}$. \n",
|
|
"Generally, training this model requires \n",
|
|
"gradient computation with respect to these parameters\n",
|
|
"$\\partial L/\\partial \\mathbf{W}_\\textrm{hx}$, $\\partial L/\\partial \\mathbf{W}_\\textrm{hh}$, and $\\partial L/\\partial \\mathbf{W}_\\textrm{qh}$.\n",
|
|
"According to the dependencies in :numref:`fig_rnn_bptt`,\n",
|
|
"we can traverse in the opposite direction of the arrows\n",
|
|
"to calculate and store the gradients in turn.\n",
|
|
"To flexibly express the multiplication of \n",
|
|
"matrices, vectors, and scalars of different shapes\n",
|
|
"in the chain rule,\n",
|
|
"we continue to use the $\\textrm{prod}$ operator \n",
|
|
"as described in :numref:`sec_backprop`.\n",
|
|
"\n",
|
|
"\n",
|
|
"First of all, differentiating the objective function\n",
|
|
"with respect to the model output at any time step $t$\n",
|
|
"is fairly straightforward:\n",
|
|
"\n",
|
|
"$$\\frac{\\partial L}{\\partial \\mathbf{o}_t} = \\frac{\\partial l (\\mathbf{o}_t, y_t)}{T \\cdot \\partial \\mathbf{o}_t} \\in \\mathbb{R}^q.$$\n",
|
|
":eqlabel:`eq_bptt_partial_L_ot`\n",
|
|
"\n",
|
|
"Now we can calculate the gradient of the objective \n",
|
|
"with respect to the parameter $\\mathbf{W}_\\textrm{qh}$\n",
|
|
"in the output layer:\n",
|
|
"$\\partial L/\\partial \\mathbf{W}_\\textrm{qh} \\in \\mathbb{R}^{q \\times h}$. \n",
|
|
"Based on :numref:`fig_rnn_bptt`, \n",
|
|
"the objective $L$ depends on $\\mathbf{W}_\\textrm{qh}$ \n",
|
|
"via $\\mathbf{o}_1, \\ldots, \\mathbf{o}_T$. \n",
|
|
"Using the chain rule yields\n",
|
|
"\n",
|
|
"$$\n",
|
|
"\\frac{\\partial L}{\\partial \\mathbf{W}_\\textrm{qh}}\n",
|
|
"= \\sum_{t=1}^T \\textrm{prod}\\left(\\frac{\\partial L}{\\partial \\mathbf{o}_t}, \\frac{\\partial \\mathbf{o}_t}{\\partial \\mathbf{W}_\\textrm{qh}}\\right)\n",
|
|
"= \\sum_{t=1}^T \\frac{\\partial L}{\\partial \\mathbf{o}_t} \\mathbf{h}_t^\\top,\n",
|
|
"$$\n",
|
|
"\n",
|
|
"where $\\partial L/\\partial \\mathbf{o}_t$\n",
|
|
"is given by :eqref:`eq_bptt_partial_L_ot`.\n",
|
|
"\n",
|
|
"Next, as shown in :numref:`fig_rnn_bptt`,\n",
|
|
"at the final time step $T$,\n",
|
|
"the objective function\n",
|
|
"$L$ depends on the hidden state $\\mathbf{h}_T$ \n",
|
|
"only via $\\mathbf{o}_T$.\n",
|
|
"Therefore, we can easily find the gradient \n",
|
|
"$\\partial L/\\partial \\mathbf{h}_T \\in \\mathbb{R}^h$\n",
|
|
"using the chain rule:\n",
|
|
"\n",
|
|
"$$\\frac{\\partial L}{\\partial \\mathbf{h}_T} = \\textrm{prod}\\left(\\frac{\\partial L}{\\partial \\mathbf{o}_T}, \\frac{\\partial \\mathbf{o}_T}{\\partial \\mathbf{h}_T} \\right) = \\mathbf{W}_\\textrm{qh}^\\top \\frac{\\partial L}{\\partial \\mathbf{o}_T}.$$\n",
|
|
":eqlabel:`eq_bptt_partial_L_hT_final_step`\n",
|
|
"\n",
|
|
"It gets trickier for any time step $t < T$,\n",
|
|
"where the objective function $L$ depends on \n",
|
|
"$\\mathbf{h}_t$ via $\\mathbf{h}_{t+1}$ and $\\mathbf{o}_t$.\n",
|
|
"According to the chain rule,\n",
|
|
"the gradient of the hidden state\n",
|
|
"$\\partial L/\\partial \\mathbf{h}_t \\in \\mathbb{R}^h$\n",
|
|
"at any time step $t < T$ can be recurrently computed as:\n",
|
|
"\n",
|
|
"\n",
|
|
"$$\\frac{\\partial L}{\\partial \\mathbf{h}_t} = \\textrm{prod}\\left(\\frac{\\partial L}{\\partial \\mathbf{h}_{t+1}}, \\frac{\\partial \\mathbf{h}_{t+1}}{\\partial \\mathbf{h}_t} \\right) + \\textrm{prod}\\left(\\frac{\\partial L}{\\partial \\mathbf{o}_t}, \\frac{\\partial \\mathbf{o}_t}{\\partial \\mathbf{h}_t} \\right) = \\mathbf{W}_\\textrm{hh}^\\top \\frac{\\partial L}{\\partial \\mathbf{h}_{t+1}} + \\mathbf{W}_\\textrm{qh}^\\top \\frac{\\partial L}{\\partial \\mathbf{o}_t}.$$\n",
|
|
":eqlabel:`eq_bptt_partial_L_ht_recur`\n",
|
|
"\n",
|
|
"For analysis, expanding the recurrent computation\n",
|
|
"for any time step $1 \\leq t \\leq T$ gives\n",
|
|
"\n",
|
|
"$$\\frac{\\partial L}{\\partial \\mathbf{h}_t}= \\sum_{i=t}^T {\\left(\\mathbf{W}_\\textrm{hh}^\\top\\right)}^{T-i} \\mathbf{W}_\\textrm{qh}^\\top \\frac{\\partial L}{\\partial \\mathbf{o}_{T+t-i}}.$$\n",
|
|
":eqlabel:`eq_bptt_partial_L_ht`\n",
|
|
"\n",
|
|
"We can see from :eqref:`eq_bptt_partial_L_ht` \n",
|
|
"that this simple linear example already\n",
|
|
"exhibits some key problems of long sequence models:\n",
|
|
"it involves potentially very large powers of $\\mathbf{W}_\\textrm{hh}^\\top$.\n",
|
|
"In it, eigenvalues smaller than 1 vanish\n",
|
|
"and eigenvalues larger than 1 diverge.\n",
|
|
"This is numerically unstable,\n",
|
|
"which manifests itself in the form of vanishing \n",
|
|
"and exploding gradients.\n",
|
|
"One way to address this is to truncate the time steps\n",
|
|
"at a computationally convenient size \n",
|
|
"as discussed in :numref:`subsec_bptt_analysis`. \n",
|
|
"In practice, this truncation can also be effected \n",
|
|
"by detaching the gradient after a given number of time steps.\n",
|
|
"Later on, we will see how more sophisticated sequence models \n",
|
|
"such as long short-term memory can alleviate this further. \n",
|
|
"\n",
|
|
"Finally, :numref:`fig_rnn_bptt` shows \n",
|
|
"that the objective function $L$ \n",
|
|
"depends on model parameters $\\mathbf{W}_\\textrm{hx}$ and $\\mathbf{W}_\\textrm{hh}$\n",
|
|
"in the hidden layer via hidden states\n",
|
|
"$\\mathbf{h}_1, \\ldots, \\mathbf{h}_T$.\n",
|
|
"To compute gradients with respect to such parameters\n",
|
|
"$\\partial L / \\partial \\mathbf{W}_\\textrm{hx} \\in \\mathbb{R}^{h \\times d}$ and $\\partial L / \\partial \\mathbf{W}_\\textrm{hh} \\in \\mathbb{R}^{h \\times h}$,\n",
|
|
"we apply the chain rule giving\n",
|
|
"\n",
|
|
"$$\n",
|
|
"\\begin{aligned}\n",
|
|
"\\frac{\\partial L}{\\partial \\mathbf{W}_\\textrm{hx}}\n",
|
|
"&= \\sum_{t=1}^T \\textrm{prod}\\left(\\frac{\\partial L}{\\partial \\mathbf{h}_t}, \\frac{\\partial \\mathbf{h}_t}{\\partial \\mathbf{W}_\\textrm{hx}}\\right)\n",
|
|
"= \\sum_{t=1}^T \\frac{\\partial L}{\\partial \\mathbf{h}_t} \\mathbf{x}_t^\\top,\\\\\n",
|
|
"\\frac{\\partial L}{\\partial \\mathbf{W}_\\textrm{hh}}\n",
|
|
"&= \\sum_{t=1}^T \\textrm{prod}\\left(\\frac{\\partial L}{\\partial \\mathbf{h}_t}, \\frac{\\partial \\mathbf{h}_t}{\\partial \\mathbf{W}_\\textrm{hh}}\\right)\n",
|
|
"= \\sum_{t=1}^T \\frac{\\partial L}{\\partial \\mathbf{h}_t} \\mathbf{h}_{t-1}^\\top,\n",
|
|
"\\end{aligned}\n",
|
|
"$$\n",
|
|
"\n",
|
|
"where $\\partial L/\\partial \\mathbf{h}_t$\n",
|
|
"which is recurrently computed by\n",
|
|
":eqref:`eq_bptt_partial_L_hT_final_step`\n",
|
|
"and :eqref:`eq_bptt_partial_L_ht_recur`\n",
|
|
"is the key quantity that affects the numerical stability.\n",
|
|
"\n",
|
|
"\n",
|
|
"\n",
|
|
"Since backpropagation through time is the application of backpropagation in RNNs,\n",
|
|
"as we have explained in :numref:`sec_backprop`,\n",
|
|
"training RNNs alternates forward propagation with\n",
|
|
"backpropagation through time.\n",
|
|
"Moreover, backpropagation through time\n",
|
|
"computes and stores the above gradients in turn.\n",
|
|
"Specifically, stored intermediate values\n",
|
|
"are reused to avoid duplicate calculations,\n",
|
|
"such as storing $\\partial L/\\partial \\mathbf{h}_t$\n",
|
|
"to be used in computation of both $\\partial L / \\partial \\mathbf{W}_\\textrm{hx}$ \n",
|
|
"and $\\partial L / \\partial \\mathbf{W}_\\textrm{hh}$.\n",
|
|
"\n",
|
|
"\n",
|
|
"## Summary\n",
|
|
"\n",
|
|
"Backpropagation through time is merely an application of backpropagation to sequence models with a hidden state.\n",
|
|
"Truncation, such as regular or randomized, is needed for computational convenience and numerical stability.\n",
|
|
"High powers of matrices can lead to divergent or vanishing eigenvalues. This manifests itself in the form of exploding or vanishing gradients.\n",
|
|
"For efficient computation, intermediate values are cached during backpropagation through time.\n",
|
|
"\n",
|
|
"\n",
|
|
"\n",
|
|
"## Exercises\n",
|
|
"\n",
|
|
"1. Assume that we have a symmetric matrix $\\mathbf{M} \\in \\mathbb{R}^{n \\times n}$ with eigenvalues $\\lambda_i$ whose corresponding eigenvectors are $\\mathbf{v}_i$ ($i = 1, \\ldots, n$). Without loss of generality, assume that they are ordered in the order $|\\lambda_i| \\geq |\\lambda_{i+1}|$. \n",
|
|
" 1. Show that $\\mathbf{M}^k$ has eigenvalues $\\lambda_i^k$.\n",
|
|
" 1. Prove that for a random vector $\\mathbf{x} \\in \\mathbb{R}^n$, with high probability $\\mathbf{M}^k \\mathbf{x}$ will be very much aligned with the eigenvector $\\mathbf{v}_1$ \n",
|
|
"of $\\mathbf{M}$. Formalize this statement.\n",
|
|
" 1. What does the above result mean for gradients in RNNs?\n",
|
|
"1. Besides gradient clipping, can you think of any other methods to cope with gradient explosion in recurrent neural networks?\n",
|
|
"\n",
|
|
"[Discussions](https://discuss.d2l.ai/t/334)\n"
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"language_info": {
|
|
"name": "python"
|
|
},
|
|
"required_libs": []
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
} |