chapter_recurrent-neural-networks/language-models-and-dataset.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 0
   },
   "source": [
    "# Language Models and the Dataset\n",
    ":label:`sec_language_model`\n",
    "\n",
    "\n",
    "In :numref:`sec_text_preprocessing`, we see how to map text data into tokens, where these tokens can be viewed as a sequence of discrete observations, such as words or characters.\n",
    "Assume that the tokens in a text sequence of length $T$ are in turn $x_1, x_2, \\ldots, x_T$. \n",
    "Then, in the text sequence,\n",
    "$x_t$($1 \\leq t \\leq T$) can be considered as the observation or label at time step $t$. Given such a text sequence,\n",
    "the goal of a *language model* is to estimate the joint probability of the sequence\n",
    "\n",
    "$$P(x_1, x_2, \\ldots, x_T).$$\n",
    "\n",
    "Language models are incredibly useful. For instance, an ideal language model would be able to generate natural text just on its own, simply by drawing one token at a time $x_t \\sim P(x_t \\mid x_{t-1}, \\ldots, x_1)$.\n",
    "Quite unlike the monkey using a typewriter, all text emerging from such a model would pass as natural language, e.g., English text. Furthermore, it would be sufficient for generating a meaningful dialog, simply by conditioning the text on previous dialog fragments.\n",
    "Clearly we are still very far from designing such a system, since it would need to *understand* the text rather than just generate grammatically sensible content.\n",
    "\n",
    "Nonetheless, language models are of great service even in their limited form.\n",
    "For instance, the phrases \"to recognize speech\" and \"to wreck a nice beach\" sound very similar.\n",
    "This can cause ambiguity in speech recognition,\n",
    "which is easily resolved through a language model that rejects the second translation as outlandish.\n",
    "Likewise, in a document summarization algorithm\n",
    "it is worthwhile knowing that \"dog bites man\" is much more frequent than \"man bites dog\", or that \"I want to eat grandma\" is a rather disturbing statement, whereas \"I want to eat, grandma\" is much more benign.\n",
    "\n",
    "\n",
    "## Learning a Language Model\n",
    "\n",
    "The obvious question is how we should model a document, or even a sequence of tokens. \n",
    "Suppose that we tokenize text data at the word level.\n",
    "We can take recourse to the analysis we applied to sequence models in :numref:`sec_sequence`.\n",
    "Let us start by applying basic probability rules:\n",
    "\n",
    "$$P(x_1, x_2, \\ldots, x_T) = \\prod_{t=1}^T P(x_t  \\mid  x_1, \\ldots, x_{t-1}).$$\n",
    "\n",
    "For example, \n",
    "the probability of a text sequence containing four words would be given as:\n",
    "\n",
    "$$P(\\text{deep}, \\text{learning}, \\text{is}, \\text{fun}) =  P(\\text{deep}) P(\\text{learning}  \\mid  \\text{deep}) P(\\text{is}  \\mid  \\text{deep}, \\text{learning}) P(\\text{fun}  \\mid  \\text{deep}, \\text{learning}, \\text{is}).$$\n",
    "\n",
    "In order to compute the language model, we need to calculate the\n",
    "probability of words and the conditional probability of a word given\n",
    "the previous few words.\n",
    "Such probabilities are essentially\n",
    "language model parameters.\n",
    "\n",
    "Here, we\n",
    "assume that the training dataset is a large text corpus, such as all\n",
    "Wikipedia entries, [Project Gutenberg](https://en.wikipedia.org/wiki/Project_Gutenberg),\n",
    "and all text posted on the\n",
    "Web.\n",
    "The probability of words can be calculated from the relative word\n",
    "frequency of a given word in the training dataset.\n",
    "For example, the estimate $\\hat{P}(\\text{deep})$ can be calculated as the\n",
    "probability of any sentence starting with the word \"deep\". A\n",
    "slightly less accurate approach would be to count all occurrences of\n",
    "the word \"deep\" and divide it by the total number of words in\n",
    "the corpus.\n",
    "This works fairly well, particularly for frequent\n",
    "words. Moving on, we could attempt to estimate\n",
    "\n",
    "$$\\hat{P}(\\text{learning} \\mid \\text{deep}) = \\frac{n(\\text{deep, learning})}{n(\\text{deep})},$$\n",
    "\n",
    "where $n(x)$ and $n(x, x')$ are the number of occurrences of singletons\n",
    "and consecutive word pairs, respectively.\n",
    "Unfortunately, estimating the\n",
    "probability of a word pair is somewhat more difficult, since the\n",
    "occurrences of \"deep learning\" are a lot less frequent. In\n",
    "particular, for some unusual word combinations it may be tricky to\n",
    "find enough occurrences to get accurate estimates.\n",
    "Things take a turn for the worse for three-word combinations and beyond.\n",
    "There will be many plausible three-word combinations that we likely will not see in our dataset.\n",
    "Unless we provide some solution to assign such word combinations nonzero count, we will not be able to use them in a language model. If the dataset is small or if the words are very rare, we might not find even a single one of them.\n",
    "\n",
    "A common strategy is to perform some form of *Laplace smoothing*.\n",
    "The solution is to\n",
    "add a small constant to all counts. \n",
    "Denote by $n$ the total number of words in\n",
    "the training set\n",
    "and $m$ the number of unique words.\n",
    "This solution helps with singletons, e.g., via\n",
    "\n",
    "$$\\begin{aligned}\n",
    "\t\\hat{P}(x) & = \\frac{n(x) + \\epsilon_1/m}{n + \\epsilon_1}, \\\\\n",
    "\t\\hat{P}(x' \\mid x) & = \\frac{n(x, x') + \\epsilon_2 \\hat{P}(x')}{n(x) + \\epsilon_2}, \\\\\n",
    "\t\\hat{P}(x'' \\mid x,x') & = \\frac{n(x, x',x'') + \\epsilon_3 \\hat{P}(x'')}{n(x, x') + \\epsilon_3}.\n",
    "\\end{aligned}$$\n",
    "\n",
    "Here $\\epsilon_1,\\epsilon_2$, and $\\epsilon_3$ are hyperparameters.\n",
    "Take $\\epsilon_1$ as an example:\n",
    "when $\\epsilon_1 = 0$, no smoothing is applied;\n",
    "when $\\epsilon_1$ approaches positive infinity,\n",
    "$\\hat{P}(x)$ approaches the uniform probability $1/m$. \n",
    "The above is a rather primitive variant of what\n",
    "other techniques can accomplish :cite:`Wood.Gasthaus.Archambeau.ea.2011`.\n",
    "\n",
    "\n",
    "Unfortunately, models like this get unwieldy rather quickly\n",
    "for the following reasons. First, we need to store all counts.\n",
    "Second, this entirely ignores the meaning of the words. For\n",
    "instance, \"cat\" and \"feline\" should occur in related contexts.\n",
    "It is quite difficult to adjust such models to additional contexts,\n",
    "whereas, deep learning based language models are well suited to\n",
    "take this into account.\n",
    "Last, long word\n",
    "sequences are almost certain to be novel, hence a model that simply\n",
    "counts the frequency of previously seen word sequences is bound to perform poorly there.\n",
    "\n",
    "## Markov Models and $n$-grams\n",
    "\n",
    "Before we discuss solutions involving deep learning, we need some more terminology and concepts. Recall our discussion of Markov Models in :numref:`sec_sequence`.\n",
    "Let us apply this to language modeling. A distribution over sequences satisfies the Markov property of first order if $P(x_{t+1} \\mid x_t, \\ldots, x_1) = P(x_{t+1} \\mid x_t)$. Higher orders correspond to longer dependencies. This leads to a number of approximations that we could apply to model a sequence:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "P(x_1, x_2, x_3, x_4) &=  P(x_1) P(x_2) P(x_3) P(x_4),\\\\\n",
    "P(x_1, x_2, x_3, x_4) &=  P(x_1) P(x_2  \\mid  x_1) P(x_3  \\mid  x_2) P(x_4  \\mid  x_3),\\\\\n",
    "P(x_1, x_2, x_3, x_4) &=  P(x_1) P(x_2  \\mid  x_1) P(x_3  \\mid  x_1, x_2) P(x_4  \\mid  x_2, x_3).\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "The probability formulae that involve one, two, and three variables are typically referred to as *unigram*, *bigram*, and *trigram* models, respectively. In the following, we will learn how to design better models.\n",
    "\n",
    "## Natural Language Statistics\n",
    "\n",
    "Let us see how this works on real data.\n",
    "We construct a vocabulary based on the time machine dataset as introduced in :numref:`sec_text_preprocessing` \n",
    "and print the top 10 most frequent words.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load ../utils/djl-imports\n",
    "%load ../utils/plot-utils\n",
    "%load ../utils/PlotUtils.java\n",
    "\n",
    "%load ../utils/Accumulator.java\n",
    "%load ../utils/Animator.java\n",
    "%load ../utils/Functions.java\n",
    "%load ../utils/StopWatch.java\n",
    "%load ../utils/Training.java\n",
    "%load ../utils/timemachine/Vocab.java\n",
    "%load ../utils/timemachine/RNNModelScratch.java\n",
    "%load ../utils/timemachine/TimeMachine.java"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "NDManager manager = NDManager.newBaseManager();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "String[][] tokens = TimeMachine.tokenize(TimeMachine.readTimeMachine(), \"word\");\n",
    "// Since each text line is not necessarily a sentence or a paragraph, we\n",
    "// concatenate all text lines\n",
    "List<String> corpus = new ArrayList<>();\n",
    "for (int i = 0; i < tokens.length; i++) {\n",
    "    for (int j = 0; j < tokens[i].length; j++) {\n",
    "        if (tokens[i][j] != \"\") {\n",
    "            corpus.add(tokens[i][j]);\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "Vocab vocab = new Vocab(new String[][] {corpus.toArray(new String[0])}, -1, new String[0]);\n",
    "for (int i = 0; i < 10; i++) {\n",
    "    Map.Entry<String, Integer> token = vocab.tokenFreqs.get(i);\n",
    "    System.out.println(token.getKey() + \": \" + token.getValue());   \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 5
   },
   "source": [
    "As we can see, the most popular words are actually quite boring to look at.\n",
    "They are often referred to as *stop words* and thus filtered out.\n",
    "Nonetheless, they still carry meaning and we will still use them.\n",
    "Besides, it is quite clear that the word frequency decays rather rapidly. The $10^{\\mathrm{th}}$ most frequent word is less than $1/5$ as common as the most popular one. To get a better idea, we plot the figure of the word frequency.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "int n = vocab.tokenFreqs.size();\n",
    "double[] freqs = new double[n];\n",
    "double[] x = new double[n];\n",
    "for (int i = 0; i < n; i++) {\n",
    "    freqs[i] = (double) vocab.tokenFreqs.get(i).getValue();\n",
    "    x[i] = (double) i;\n",
    "}\n",
    "\n",
    "PlotUtils.plotLogScale(new double[][] {x}, new double[][] {freqs}, new String[] {\"\"},\n",
    "                       \"token: x\", \"frequency: n(x)\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 7
   },
   "source": [
    "We are on to something quite fundamental here: the word frequency decays rapidly in a well-defined way.\n",
    "After dealing with the first few words as exceptions, all the remaining words roughly follow a straight line on a log-log plot. This means that words satisfy *Zipf's law*,\n",
    "which states that the frequency $n_i$ of the $i^\\mathrm{th}$ most frequent word\n",
    "is:\n",
    "\n",
    "$$n_i \\propto \\frac{1}{i^\\alpha},$$\n",
    ":eqlabel:`eq_zipf_law`\n",
    "\n",
    "which is equivalent to\n",
    "\n",
    "$$\\log n_i = -\\alpha \\log i + c,$$\n",
    "\n",
    "where $\\alpha$ is the exponent that characterizes the distribution and $c$ is a constant.\n",
    "This should already give us pause if we want to model words by count statistics and smoothing.\n",
    "After all, we will significantly overestimate the frequency of the tail, also known as the infrequent words. But what about the other word combinations, such as bigrams, trigrams, and beyond?\n",
    "Let us see whether the bigram frequency behaves in the same manner as the unigram frequency.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "String[] bigramTokens = new String[corpus.size()-1];\n",
    "for (int i = 0; i < bigramTokens.length; i++) {\n",
    "    bigramTokens[i] = corpus.get(i) + \" \" + corpus.get(i+1);\n",
    "}\n",
    "Vocab bigramVocab = new Vocab(new String[][] {bigramTokens}, -1, new String[0]);\n",
    "for (int i = 0; i < 10; i++) {\n",
    "    Map.Entry<String, Integer> token = bigramVocab.tokenFreqs.get(i);\n",
    "    System.out.println(token.getKey() + \": \" + token.getValue()); \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 9
   },
   "source": [
    "One thing is notable here. Out of the ten most frequent word pairs, nine are composed of both stop words and only one is relevant to the actual book---\"the time\". Furthermore, let us see whether the trigram frequency behaves in the same manner.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "String[] trigramTokens = new String[corpus.size()-2];\n",
    "for (int i = 0; i < trigramTokens.length; i++) {\n",
    "    trigramTokens[i] = corpus.get(i) + \" \" + corpus.get(i+1) + \" \" + corpus.get(i+2);\n",
    "}\n",
    "Vocab trigramVocab = new Vocab(new String[][] {trigramTokens}, -1, new String[0]);\n",
    "for (int i = 0; i < 10; i++) {\n",
    "    Map.Entry<String, Integer> token = trigramVocab.tokenFreqs.get(i);\n",
    "    System.out.println(token.getKey() + \": \" + token.getValue()); \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 11
   },
   "source": [
    "Last, let us visualize the token frequency among these three models: unigrams, bigrams, and trigrams.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = bigramVocab.tokenFreqs.size();\n",
    "double[] bigramFreqs = new double[n];\n",
    "double[] bigramX = new double[n];\n",
    "for (int i = 0; i < n; i++) {\n",
    "    bigramFreqs[i] = (double) bigramVocab.tokenFreqs.get(i).getValue();\n",
    "    bigramX[i] = (double) i;\n",
    "}\n",
    "\n",
    "n = trigramVocab.tokenFreqs.size();\n",
    "double[] trigramFreqs = new double[n];\n",
    "double[] trigramX = new double[n];\n",
    "for (int i = 0; i < n; i++) {\n",
    "    trigramFreqs[i] = (double) trigramVocab.tokenFreqs.get(i).getValue();\n",
    "    trigramX[i] = (double) i;\n",
    "}\n",
    "\n",
    "PlotUtils.plotLogScale(new double[][] {x, bigramX, trigramX}, new double[][] {freqs, bigramFreqs, trigramFreqs}, \n",
    "                       new String[] {\"unigram\", \"bigram\", \"trigram\"}, \"token: x\", \"frequency: n(x)\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 13
   },
   "source": [
    "This figure is quite exciting for a number of reasons. First, beyond unigram words, sequences of words also appear to be following Zipf's law, albeit with a smaller exponent $\\alpha$ in :eqref:`eq_zipf_law`, depending on the sequence length.\n",
    "Second, the number of distinct $n$-grams is not that large. This gives us hope that there is quite a lot of structure in language.\n",
    "Third, many $n$-grams occur very rarely, which makes Laplace smoothing rather unsuitable for language modeling. Instead, we will use deep learning based models.\n",
    "\n",
    "\n",
    "## Reading Long Sequence Data\n",
    "\n",
    "Since sequence data are by their very nature sequential, we need to address\n",
    "the issue of processing it.\n",
    "We did so in a rather ad-hoc manner in :numref:`sec_sequence`.\n",
    "When sequences get too long to be processed by models\n",
    "all at once,\n",
    "we may wish to split such sequences for reading.\n",
    "Now let us describe general strategies.\n",
    "Before introducing the model,\n",
    "let us assume that we will use a neural network to train a language model,\n",
    "where the network processes a minibatch of sequences with predefined length, say $n$ time steps, at a time.\n",
    "Now the question is how to read minibatches of features and labels at random.\n",
    "\n",
    "To begin with,\n",
    "since a text sequence can be arbitrarily long,\n",
    "such as the entire *The Time Machine* book,\n",
    "we can partition such a long sequence into subsequences\n",
    "with the same number of time steps.\n",
    "When training our neural network,\n",
    "a minibatch of such subsequences\n",
    "will be fed into the model.\n",
    "Suppose that the network processes a subsequence\n",
    "of $n$ time steps\n",
    "at a time.\n",
    ":numref:`fig_timemachine_5gram`\n",
    "shows all the different ways to obtain subsequences\n",
    "from an original text sequence, where $n=5$ and a token at each time step corresponds to a character.\n",
    "Note that we have quite some freedom since we could pick an arbitrary offset that indicates the initial position.\n",
    "\n",
    "![Different offsets lead to different subsequences when splitting up text.](https://raw.githubusercontent.com/d2l-ai/d2l-en/master/img/timemachine-5gram.svg)\n",
    ":label:`fig_timemachine_5gram`\n",
    "\n",
    "Hence, which one should we pick from :numref:`fig_timemachine_5gram`?\n",
    "In fact, all of them are equally good.\n",
    "However, if we pick just one offset,\n",
    "there is limited coverage of all the possible subsequences\n",
    "for training our network.\n",
    "Therefore,\n",
    "we can start with a random offset to partition a sequence\n",
    "to get both *coverage* and *randomness*.\n",
    "In the following,\n",
    "we describe how to accomplish this for both\n",
    "*random sampling* and *sequential partitioning* strategies.\n",
    "\n",
    "\n",
    "### Random Sampling\n",
    "\n",
    "In random sampling, each example is a subsequence arbitrarily captured on the original long sequence.\n",
    "The subsequences from two adjacent random minibatches\n",
    "during iteration\n",
    "are not necessarily adjacent on the original sequence.\n",
    "For language modeling,\n",
    "the target is to predict the next token based on what tokens we have seen so far, hence the labels are the original sequence, shifted by one token.\n",
    "\n",
    "The following code randomly generates a minibatch from the data each time.\n",
    "Here, the argument `batchSize` specifies the number of subsequence examples in each minibatch\n",
    "and `numSteps` is the predefined number of time steps\n",
    "in each subsequence.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Generate a minibatch of subsequences using random sampling.\n",
    " */\n",
    "public ArrayList<NDList>\n",
    "        seqDataIterRandom(List<Integer> corpus, int batchSize, int numSteps, NDManager manager) {\n",
    "    // Start with a random offset (inclusive of `numSteps - 1`) to partition a\n",
    "    // sequence\n",
    "    corpus = corpus.subList(new Random().nextInt(numSteps - 1), corpus.size());\n",
    "    // Subtract 1 since we need to account for labels\n",
    "    int numSubseqs = (corpus.size() - 1) / numSteps;\n",
    "    // The starting indices for subsequences of length `numSteps`\n",
    "    List<Integer> initialIndices = new ArrayList<>();\n",
    "    for (int i = 0; i < numSubseqs * numSteps; i += numSteps) {\n",
    "        initialIndices.add(i);\n",
    "    }\n",
    "    // In random sampling, the subsequences from two adjacent random\n",
    "    // minibatches during iteration are not necessarily adjacent on the\n",
    "    // original sequence\n",
    "    Collections.shuffle(initialIndices);\n",
    "\n",
    "    int numBatches = numSubseqs / batchSize; \n",
    "        \n",
    "    ArrayList<NDList> pairs = new ArrayList<NDList>();\n",
    "    for (int i = 0; i < batchSize * numBatches; i += batchSize) {\n",
    "        // Here, `initialIndices` contains randomized starting indices for\n",
    "        // subsequences\n",
    "        List<Integer> initialIndicesPerBatch = initialIndices.subList(i, i + batchSize);\n",
    "\n",
    "        NDArray xNDArray = manager.create(new Shape(initialIndices.size(), numSteps), DataType.INT32);\n",
    "        NDArray yNDArray = manager.create(new Shape(initialIndices.size(), numSteps), DataType.INT32);\n",
    "        for (int j = 0; j < initialIndices.size(); j++) {\n",
    "            ArrayList<Integer> X = data(initialIndices.get(j), corpus, numSteps);\n",
    "            xNDArray.set(new NDIndex(j), manager.create(X.stream().mapToInt(Integer::intValue).toArray()));\n",
    "            ArrayList<Integer> Y = data(initialIndices.get(j)+1, corpus, numSteps);\n",
    "            yNDArray.set(new NDIndex(j), manager.create(Y.stream().mapToInt(Integer::intValue).toArray()));\n",
    "        }\n",
    "        NDList pair = new NDList();\n",
    "        pair.add(xNDArray);\n",
    "        pair.add(yNDArray);\n",
    "        pairs.add(pair);\n",
    "    }\n",
    "    return pairs;\n",
    "}\n",
    "\n",
    "ArrayList<Integer> data(int pos, List<Integer> corpus, int numSteps) {\n",
    "    // Return a sequence of length `numSteps` starting from `pos`\n",
    "    return new ArrayList<Integer>(corpus.subList(pos, pos + numSteps));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 15
   },
   "source": [
    "Let us manually generate a sequence from 0 to 34.\n",
    "We assume that\n",
    "the batch size and numbers of time steps are 2 and 5,\n",
    "respectively.\n",
    "This means that we can generate $\\lfloor (35 - 1) / 5 \\rfloor= 6$ feature-label subsequence pairs. With a minibatch size of 2, we only get 3 minibatches.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "List<Integer> mySeq = new ArrayList<>();\n",
    "for (int i = 0; i < 35; i++) {\n",
    "    mySeq.add(i);\n",
    "}\n",
    "\n",
    "for (NDList pair : seqDataIterRandom(mySeq, 2, 5, manager)) {\n",
    "    System.out.println(\"X:\\n\" + pair.get(0).toDebugString(50, 50, 50, 50, true));\n",
    "    System.out.println(\"Y:\\n\" + pair.get(1).toDebugString(50, 50, 50, 50, true));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 17
   },
   "source": [
    "### Sequential Partitioning\n",
    "\n",
    "In addition to random sampling of the original sequence, we can also ensure that \n",
    "the subsequences from two adjacent minibatches\n",
    "during iteration\n",
    "are adjacent on the original sequence.\n",
    "This strategy preserves the order of split subsequences when iterating over minibatches, hence is called sequential partitioning.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Generate a minibatch of subsequences using sequential partitioning.\n",
    " */\n",
    "public ArrayList<NDList> seqDataIterSequential(List<Integer> corpus, int batchSize, int numSteps, \n",
    "                                               NDManager manager) {\n",
    "    // Start with a random offset to partition a sequence\n",
    "    int offset = new Random().nextInt(numSteps);\n",
    "    int numTokens = ((corpus.size() - offset - 1) / batchSize) * batchSize;\n",
    "    \n",
    "    NDArray Xs = manager.create(\n",
    "        corpus.subList(offset, offset + numTokens).stream().mapToInt(Integer::intValue).toArray());\n",
    "    NDArray Ys = manager.create(\n",
    "        corpus.subList(offset + 1, offset + 1 + numTokens).stream().mapToInt(Integer::intValue).toArray());\n",
    "    Xs = Xs.reshape(new Shape(batchSize, -1));\n",
    "    Ys = Ys.reshape(new Shape(batchSize, -1));\n",
    "    int numBatches = (int) Xs.getShape().get(1) / numSteps;\n",
    "    \n",
    "    \n",
    "    ArrayList<NDList> pairs = new ArrayList<NDList>();\n",
    "    for (int i = 0; i < numSteps * numBatches; i += numSteps) {\n",
    "        NDArray X = Xs.get(new NDIndex(\":, {}:{}\", i, i + numSteps));\n",
    "        NDArray Y = Ys.get(new NDIndex(\":, {}:{}\", i, i + numSteps));\n",
    "        NDList pair = new NDList();\n",
    "        pair.add(X);\n",
    "        pair.add(Y);\n",
    "        pairs.add(pair);\n",
    "    }\n",
    "    return pairs;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 20
   },
   "source": [
    "Using the same settings,\n",
    "let us print features `X` and labels `Y` for each minibatch of subsequences read by sequential partitioning.\n",
    "Note that\n",
    "the subsequences from two adjacent minibatches\n",
    "during iteration\n",
    "are indeed adjacent on the original sequence.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for (NDList pair : seqDataIterSequential(mySeq, 2, 5, manager)) {\n",
    "    System.out.println(\"X:\\n\" + pair.get(0).toDebugString(10, 10, 10, 10, true));\n",
    "    System.out.println(\"Y:\\n\" + pair.get(1).toDebugString(10, 10, 10, 10, true));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 22
   },
   "source": [
    "Now we wrap the above two sampling functions to a class so that we can use it as a data iterator later.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "public class SeqDataLoader implements Iterable<NDList> {\n",
    "    public ArrayList<NDList> dataIter;\n",
    "    public List<Integer> corpus;\n",
    "    public Vocab vocab;\n",
    "    public int batchSize;\n",
    "    public int numSteps;\n",
    "    \n",
    "    /** \n",
    "     * An iterator to load sequence data.\n",
    "     */\n",
    "    @SuppressWarnings(\"unchecked\")\n",
    "    public SeqDataLoader(int batchSize, int numSteps, boolean useRandomIter, int maxTokens) throws IOException, Exception {\n",
    "        Pair<List<Integer>, Vocab> corpusVocabPair = TimeMachine.loadCorpusTimeMachine(maxTokens);\n",
    "        this.corpus = corpusVocabPair.getKey();\n",
    "        this.vocab = corpusVocabPair.getValue();\n",
    "        \n",
    "        this.batchSize = batchSize;\n",
    "        this.numSteps = numSteps;\n",
    "        if (useRandomIter) {\n",
    "            dataIter = seqDataIterRandom(corpus, batchSize, numSteps, manager);\n",
    "        }else {\n",
    "            dataIter = seqDataIterSequential(corpus, batchSize, numSteps, manager);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    @Override\n",
    "    public Iterator<NDList> iterator() {\n",
    "        return dataIter.iterator();\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 24
   },
   "source": [
    "Last, we define a function `loadDataTimeMachine` that returns both the data iterator and the vocabulary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Return the iterator and the vocabulary of the time machine dataset.\n",
    " */\n",
    "public Pair<ArrayList<NDList>, Vocab> loadDataTimeMachine(int batchSize, int numSteps, boolean useRandomIter, int maxTokens) throws IOException, Exception {\n",
    "    SeqDataLoader seqData = new SeqDataLoader(batchSize, numSteps, useRandomIter, maxTokens);\n",
    "    return new Pair(seqData.dataIter, seqData.vocab); // ArrayList<NDList>, Vocab\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 26
   },
   "source": [
    "## Summary\n",
    "\n",
    "* Language models are key to natural language processing.\n",
    "* $n$-grams provide a convenient model for dealing with long sequences by truncating the dependence.\n",
    "* Long sequences suffer from the problem that they occur very rarely or never.\n",
    "* Zipf's law governs the word distribution for not only unigrams but also the other $n$-grams.\n",
    "* There is a lot of structure but not enough frequency to deal with infrequent word combinations efficiently via Laplace smoothing.\n",
    "* The main choices for reading long sequences are random sampling and sequential partitioning. The latter can ensure that the subsequences from two adjacent minibatches during iteration are adjacent on the original sequence.\n",
    "\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Suppose there are $100,000$ words in the training dataset. How much word frequency and multi-word adjacent frequency does a four-gram need to store?\n",
    "1. How would you model a dialogue?\n",
    "1. Estimate the exponent of Zipf's law for unigrams, bigrams, and trigrams.\n",
    "1. What other methods can you think of for reading long sequence data?\n",
    "1. Consider the random offset that we use for reading long sequences.\n",
    "    1. Why is it a good idea to have a random offset?\n",
    "    1. Does it really lead to a perfectly uniform distribution over the sequences on the document?\n",
    "    1. What would you have to do to make things even more uniform?\n",
    "1. If we want a sequence example to be a complete sentence, what kind of problem does this introduce in minibatch sampling? How can we fix the problem?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "14.0.2+12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}