Answers.Body: <p>Language models explicitly assume that word sequences are <strong>not</strong> independent and identically distributed (iid). A word-based model that assumed iid within each sequence could only predict probabilities of words according to some other context than surrounding words, which would not be very useful for a language model.</p>
  <p>The training processes for statistical models often require iid input/output pairs when sampling e.g. minibatches. Neural networks definitely train better when datasets are shuffled to remove any chance of correlation between examples as they are used to update parameters.</p>
  <p>How to resolve these two different needs? When training a sequence-based model on many sequences, it is the distribution of <em>sequences</em> that needs to be iid and representative of the overall population. The distribution of items within the sequence is what is being learned, so should not be obscured or removed.</p>
  <p>As an analogy, you do not usually want to shuffle the rows of pixels in an image when training image classifiers. The spatial pattern in the image needs to be preserved in the same way that the sequential pattern in a sentence needs to be preserved, because the pattern is part of the data being modelled. With image data, you accept non-iid relationships between the pixels that are next to each other within a single image, then apply shuffling and stratifying algorithms at the level of individual images.</p>
  <blockquote>
  <p>If so, are there any papers that try and deal with this?</p>
  </blockquote>
  <p>There may be some original papers from 50 years ago which compare iid with non-iid data when training sequences fed into RNNs, but it has been a standard part of engineering practice for decades now to shuffle datasets, and the separate sequences used to train RNNs are no different.</p>
  <p>From your comments:</p>
  <blockquote>
  <p>However the sequences that are sampled for training are not iid if they are multiple sequences generated sequentially from the same document, which from what I understand happens often?</p>
  </blockquote>
  <p>You are correct, the raw set of sequences is not iid if they are collected in that fashion. However, the dataset is always shuffled or resampled for training purposes, it is not fed into training routines in that raw state. The shuffling (of selected sequences which are kept intact internally) happens in-between the raw data collection and the training.</p>
  <hr />
  <p>There are some simple statistical models that do not require iid data to train on. This occurs for example in tabular reinforcement learning, which can learn online from a single continuous sequence of states, actions and rewards. An equivalent language model would be word- or letter-based ngrams.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-11T20:08:40.737Z
Answers.Text: I agree that LMs for a single sequence assume non-iid. However the sequences that are sampled for training are *not* iid if they are multiple sequences generated sequentially from the same document, which from what I understand happens often?
Answers.UserDisplayName: Opt
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-11T21:49:21.310Z
Answers.Text: @Opt: You keep the sequences intact internally, but shuffle the collection of sequences as you would any other dataset that you need to be iid. This is separate to how the data might be *collected*. It is fine to collect them in order from source documents, the shuffling comes later, i.e. in between collecting the data and training with it
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-12T02:34:25.333Z
Answers.Text: Shuffling necessarily doesn't give iid - see https://math.stackexchange.com/questions/2965518/does-the-shuffling-of-a-sequence-of-measurements-produce-an-i-i-d-sequence
Answers.UserDisplayName: Opt
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-12T02:42:42.550Z
Answers.Text: *doesn't necessarily
Answers.UserDisplayName: Opt
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-12T07:21:10.423Z
Answers.Text: @Opt: The results in that question are edge cases that are not going to be relevant in most machine learning (including statistical language models), even if they are interesting mathematically.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-13T17:42:54.190Z
Answers.Text: That's not true -- suppose you split dataset into train/validation and use validation set for early stopping etc. Suppose this is the sentiment analysis task. Then if it's not iid, training data having proportionally more positive sentiment than the overall data will mean validation has proportionally less which lead to suboptimal stopping time, etc.
Answers.UserDisplayName: Opt
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-11T20:01:51.520Z
Answers.LastActivityDate: 2021-03-11T22:05:50.657Z
Answers.LastEditDate: 2021-03-11T22:05:50.657Z
Answers.UserDisplayName: Neil Slater
Body: <p>If I understand correctly, when training language models, we take a document and then chunk the document into a sequences of k tokens. So if the document is of length 30 and k=10, then we'll have 20 chunks of 10 tokens each (token 1-11, 2-12, and so on).</p>
  <p>However these training sequences are not iid, right? If so, are there any papers that try and deal with this?</p>
  
Tags: <natural-language-processing><language-model><iid>
Title: Are training sequences for LMs sampled in an IID fashion?
UserDisplayName: Opt
ThreadText: # Are training sequences for LMs sampled in an IID fashion?
  
  (Asked by: username_0 on 2021-03-11)
  
  If I understand correctly, when training language models, we take a document and then chunk the document into a sequences of k tokens. So if the document is of length 30 and k=10, then we'll have 20 chunks of 10 tokens each (token 1-11, 2-12, and so on).
  
  However these training sequences are not iid, right? If so, are there any papers that try and deal with this?
  
  **Tags:** natural-language-processing, language-model, iid
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-03-11. Score: 1
  
  Language models explicitly assume that word sequences are **not** independent and identically distributed (iid). A word-based model that assumed iid within each sequence could only predict probabilities of words according to some other context than surrounding words, which would not be very useful for a language model.
  
  The training processes for statistical models often require iid input/output pairs when sampling e.g. minibatches. Neural networks definitely train better when datasets are shuffled to remove any chance of correlation between examples as they are used to update parameters.
  
  How to resolve these two different needs? When training a sequence-based model on many sequences, it is the distribution of *sequences* that needs to be iid and representative of the overall population. The distribution of items within the sequence is what is being learned, so should not be obscured or removed.
  
  As an analogy, you do not usually want to shuffle the rows of pixels in an image when training image classifiers. The spatial pattern in the image needs to be preserved in the same way that the sequential pattern in a sentence needs to be preserved, because the pattern is part of the data being modelled. With image data, you accept non-iid relationships between the pixels that are next to each other within a single image, then apply shuffling and stratifying algorithms at the level of individual images.
  
  > If so, are there any papers that try and deal with this?
  
  There may be some original papers from 50 years ago which compare iid with non-iid data when training sequences fed into RNNs, but it has been a standard part of engineering practice for decades now to shuffle datasets, and the separate sequences used to train RNNs are no different.
  
  From your comments:
  
  > However the sequences that are sampled for training are not iid if they are multiple sequences generated sequentially from the same document, which from what I understand happens often?
  
  You are correct, the raw set of sequences is not iid if they are collected in that fashion. However, the dataset is always shuffled or resampled for training purposes, it is not fed into training routines in that raw state. The shuffling (of selected sequences which are kept intact internally) happens in-between the raw data collection and the training.
  
  ---
  
  There are some simple statistical models that do not require iid data to train on. This occurs for example in tabular reinforcement learning, which can learn online from a single continuous sequence of states, actions and rewards. An equivalent language model would be word- or letter-based ngrams.
  
  > **Comments:**
  > **username_0**: I agree that LMs for a single sequence assume non-iid. However the sequences that are sampled for training are *not* iid if they are multiple sequences generated sequentially from the same document, which from what I understand happens often?  
  > **username_1**: @Opt: You keep the sequences intact internally, but shuffle the collection of sequences as you would any other dataset that you need to be iid. This is separate to how the data might be *collected*. It is fine to collect them in order from source documents, the shuffling comes later, i.e. in between collecting the data and training with it  
  > **username_0**: Shuffling necessarily doesn't give iid - see https://math.stackexchange.com/questions/2965518/does-the-shuffling-of-a-sequence-of-measurements-produce-an-i-i-d-sequence  
  > **username_0**: *doesn't necessarily  
  > **username_1**: @Opt: The results in that question are edge cases that are not going to be relevant in most machine learning (including statistical language models), even if they are interesting mathematically.  
  > **username_0**: That's not true -- suppose you split dataset into train/validation and use validation set for early stopping etc. Suppose this is the sentiment analysis task. Then if it's not iid, training data having proportionally more positive sentiment than the overall data will mean validation has proportionally less which lead to suboptimal stopping time, etc.  
  
  ---
  
  