{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Sequence Models\n",
"\n",
"Imagine that you're watching movies on Netflix. As a good Netflix user you decide to rate each of the movies religiously. After all, a good movie is a good movie, and you want to watch more of them, right? As it turns out, things are not quite so simple. People's opinions on movies can change quite significantly over time. In fact, psychologists even have names for some of the effects:\n",
"\n",
"* There's [anchoring](https://en.wikipedia.org/wiki/Anchoring), based on someone else's opinion. For instance after the Oscar awards, ratings for the corresponding movie go up, even though it's still the same movie. This effect persists for a few months until the award is forgotten. [Wu et al., 2017](https://dl.acm.org/citation.cfm?id=3018689) showed that the effect lifts rating by over half a point. \n",
"* There's the [Hedonic adaptation](https://en.wikipedia.org/wiki/Hedonic_treadmill), where humans quickly adapt to accept an improved (or a bad) situation as the new normal. For instance, after watching many good movies, the expectations that the next movie be equally good or better are high, and even an average movie might be considered a bad movie after many great ones.\n",
"* There's seasonality. Very few viewers like to watch a Santa Claus movie in August. \n",
"* In some cases movies become unpopular due to the misbehaviors of directors or actors in the production. \n",
"* Some movies become cult movies, because they were almost comically bad. *Plan 9 from Outer Space* and *Troll 2* achieved a high degree of notoriety for this reason. \n",
"\n",
"In short, ratings are anything but stationary. Using temporal dynamics helped [Yehuda Koren, 2009](https://dl.acm.org/citation.cfm?id=1557072) to recommend movies more accurately. But it isn't just about movies. \n",
"\n",
"* Many users have highly particular behavior when it comes to the time when they open apps. For instance, social media apps are much more popular after school with students. Stock market trading apps are more commonly used when the markets are open.\n",
"* It is much harder to predict tomorrow's stock prices than to fill in the blanks for a stock price we missed yesterday, even though both are just a matter of estimating one number. After all, hindsight is so much easier than foresight. In statistics the former is called *prediction* whereas the latter is called *filtering*. \n",
"* Music, speech, text, movies, steps, etc. are all sequential in nature. If we were to permute them they would make little sense. The headline *dog bites man* is much less surprising than *man bites dog*, even though the words are identical. \n",
"* Earthquakes are strongly correlated, i.e. after a massive earthquake there are very likely several smaller aftershocks, much more so than without the strong quake. In fact, earthquakes are spatiotemporally correlated, i.e. the aftershocks typically occur within a short time span and in close proximity. \n",
"* Humans interact with each other in a sequential nature, as can be seen in Twitter fights, dance patterns and debates. \n",
"\n",
"## Statistical Tools\n",
"\n",
"In short, we need statistical tools and new deep networks architectures to deal with sequence data. To keep things simple, we use the stock price as an example. \n",
"\n",
"![FTSE 100 index over 30 years](../img/ftse100.png)\n",
"\n",
"Let's denote the prices by $x_t \\geq 0$, i.e. at time $t \\in \\mathbb{N}$ we observe some price $x_t$. For a trader to do well in the stock market on day $t$ he should want to predict $x_t$ via \n",
"\n",
"$$x_t \\sim p(x_t|x_{t-1}, \\ldots x_1).$$\n",
"\n",
"### Autoregressive Models\n",
"\n",
"In order to achieve this, our trader could use a regressor such as the one we trained in the [section on regression](../chapter_deep-learning-basics/linear-regression-gluon.md). There's just a major problem - the number of inputs, $x_{t-1}, \\ldots x_1$ varies, depending on $t$. That is, the number increases with the amount of data that we encounter, and we will need an approximation to make this computationally tractable. Much of what follows in this chapter will revolve around how to estimate $p(x_t|x_{t-1}, \\ldots x_1)$ efficiently. In a nutshell it boils down to two strategies:\n",
"\n",
"1. Assume that the potentially rather long sequence $x_{t-1}, \\ldots x_1$ isn't really necessary. In this case we might content ourselves with some timespan $\\tau$ and only use $x_{t-1}, \\ldots x_{t-\\tau}$ observations. The immediate benefit is that now the number of arguments is always the same, at least for $t > \\tau$. This allows us to train a deep network as indicated above. Such models will be called *autoregressive* models, as they quite literally perform regression on themselves.\n",
"1. Another strategy is to try and keep some summary $h_t$ of the past observations around and update that in addition to the actual prediction. This leads to models that estimate $x_t|x_{t-1}, h_{t-1}$ and moreover updates of the form $h_t = g(h_t, x_t)$. Since $h_t$ is never observed, these models are also called *latent autoregressive models*. LSTMs and GRUs are examples of this.\n",
"\n",
"Both cases raise the obvious question how to generate training data. One typically uses historical observations to predict the next observation given the ones up to right now. Obviously we do not expect time to stand still. However, a common assumption is that while the specific values of $x_t$ might change, at least the dynamics of the time series itself won't. This is reasonable, since novel dynamics are just that, novel and thus not predictable using data we have so far. Statisticians call dynamics that don't change *stationary*. Regardless of what we do, we will thus get an estimate of the entire time series via\n",
"\n",
"$$p(x_1, \\ldots x_T) = \\prod_{t=1}^T p(x_t|x_{t-1}, \\ldots x_1).$$\n",
"\n",
"Note that the above considerations still hold if we deal with discrete objects, such as words, rather than numbers. The only difference is that in such a situation we need to use a classifier rather than a regressor to estimate $p(x_t| x_{t-1}, \\ldots x_1)$. \n",
"\n",
"### Markov Model\n",
"\n",
"Recall the approximation that in an autoregressive model we use only $(x_{t-1}, \\ldots x_{t-\\tau})$ instead of $(x_{t-1}, \\ldots x_1)$ to estimate $x_t$. Whenever this approximation is accurate we say that the sequence satisfies a Markov condition. In particular, if $\\tau = 1$, we have a *first order* Markov model and $p(x)$ is given by \n",
"\n",
"$$p(x_1, \\ldots x_T) = \\prod_{t=1}^T p(x_t|x_{t-1}).$$\n",
"\n",
"Such models are particularly nice whenever $x_t$ assumes only discrete values, since in this case dynamic programming can be used to compute values along the chain exactly. For instance, we can compute $x_{t+1}|x_{t-1}$ efficiently using the fact that we only need to take into account a very short history of past observations. \n",
"\n",
"$$p(x_{t+1}|x_{t-1}) = \\sum_{x_t} p(x_{t+1}|x_t) p(x_t|x_{t-1})$$\n",
"\n",
"Going into details of dynamic programming is beyond the scope of this section. Control and reinforcement learning algorithms use such tools extensively. \n",
"\n",
"### Causality\n",
"\n",
"In principle, there's nothing wrong with unfolding $p(x_1, \\ldots x_T)$ in reverse order. After all, by conditioning we can always write it via \n",
"\n",
"$$p(x_1, \\ldots x_T) = \\prod_{t=T}^1 p(x_t|x_{t+1}, \\ldots x_T).$$\n",
"\n",
"In fact, if we have a Markov model we can obtain a reverse conditional probability distribution, too. \n",
"In many cases, however, there exists a natural direction for the data, namely going forward in time. It is clear that future events cannot influence the past. Hence, if we change $x_t$, we may be able to influence what happens for $x_{t+1}$ going forward but not the converse. That is, if we change $x_t$, the distribution over past events will not change. Consequently, it ought to be easier to explain $x_{t+1}|x_t$ rather than $x_t|x_{t+1}$. For instance, [Hoyer et al., 2008](https://papers.nips.cc/paper/3548-nonlinear-causal-discovery-with-additive-noise-models) show that in some cases we can find $x_{t+1} = f(x_t) + \\epsilon$ for some additive noise, whereas the converse is not true. This is great news, since it is typically the forward direction that we're interested in estimating. For more on this topic see e.g. the book by [Peters, Janzing and Schölkopf, 2015](https://mitpress.mit.edu/books/elements-causal-inference). We are barely scratching the surface of it. \n",
"\n",
"## Toy Example\n",
"\n",
"After so much theory, let's try this out in practice. Since much of the modeling is identical to when we built regression estimators in Gluon, we will not delve into much detail regarding the choice of architecture besides the fact that we will use several layers of a fully connected network. Let's begin by generating some data. To keep things simple we generate our 'time series' by using a sine function with some additive noise."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"