{
  "id": "2002.09067",
  "version": "v1",
  "published": "2020-02-21T00:12:01.000Z",
  "updated": "2020-02-21T00:12:01.000Z",
  "title": "Incremental Sampling Without Replacement for Sequence Models",
  "authors": [
    "Kensen Shi",
    "David Bieber",
    "Charles Sutton"
  ],
  "categories": [
    "cs.LG",
    "cs.DS",
    "stat.ML"
  ],
  "abstract": "Sampling is a fundamental technique, and sampling without replacement is often desirable when duplicate samples are not beneficial. Within machine learning, sampling is useful for generating diverse outputs from a trained model. We present an elegant procedure for sampling without replacement from a broad class of randomized programs, including generative neural models that construct outputs sequentially. Our procedure is efficient even for exponentially-large output spaces. Unlike prior work, our approach is incremental, i.e., samples can be drawn one at a time, allowing for increased flexibility. We also present a new estimator for computing expectations from samples drawn without replacement. We show that incremental sampling without replacement is applicable to many domains, e.g., program synthesis and combinatorial optimization.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-02-21T00:12:01.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "replacement",
      "sequence models",
      "incremental sampling",
      "exponentially-large output spaces",
      "duplicate samples"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}