A Generalization of Sampling Without Replacement from a Finite Universe

By D. Horvitz, D. Thompson. 1952

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistics and Probability

Citations in the corpus

Residual Energy-Based Models for Text Generation (2020, background): “Lastly, this formulation enables efﬁcient evaluation and generation via importance sampling (Horvitz & Thompson, 1952; Grover et al., 2019).”
Balanced Policy Evaluation and Learning (2017, background): “Noting that [17, 18] SAPE(⇡) = E[ 1 n Pn i=1 Yi ⇥ ⇡Ti(Xi)/'Ti(Xi) | X1:n], one first fits a probabilistic classification model '̂ to {(Xi, Ti) : i 2 [n]} and then estimates SAPE in an alternate but also plug-in fashion: ⌧̂ IPW(⇡) = ⌧̂W IPW(⇡), W IPW i (⇡) = ⇡Ti(Xi)/'̂Ti(Xi) For a deterministic polic”
Doubly Robust Policy Evaluation and Optimization (2014, background): “Key words and phrases: Contextual bandits, doubly robust estimators, causal inference.”
Doubly Robust Policy Evaluation and Learning (2011, background): “The second kind, called inverse propensity score (IPS) (Horvitz & Thompson, 1952), uses importance weighting to correct for the incorrect proportions of actions in the historic data.”
Learning from Logged Implicit Exploration Data (2010, background): “Given this estimated probability, results can be importance-weighted to estimate average survey outcomes on the entire population [2].”
Offline A/B Testing for Recommender Systems (2018, background): “…is called counterfactual reasoning or off-policy evaluation (OPE) (see [2] for a comprehensive study). such as Basic Importance Sampling (BIS, [8, 11]), Capped Importance Sampling (CIS, [2]), Normalised Importance Sampling (NIS, [21]) and Doubly Robust (DR, [6]) have been introduced to compute…”
Optimal and Adaptive Off-policy Evaluation in Contextual Bandits (2016, methodology): “Lemma 1 (IPS estimator [Horvitz and Thompson, 1952]) .”
Off-policy evaluation for slate recommendation (2016, background): “General approaches, namely inverse propensity scores (IPS) [13, 18], require unrealistically large amounts of logged data to evaluate whole-page metrics that depend on multiple recommended items, which happens when showing ranked lists.”
Comment: Demystifying Double Robustness: A Comparison of Alternative Strategies for Estimating a Population Mean from Incomplete Data. (2008, methodology): “In the original method of Horvitz and Thompson (1952), the πi’s were determined by a known survey design.”
Runaway Feedback Loops in Predictive Policing (2017, methodology): “1) is precisely the weighting scheme of the Thompson-Horvitz estimator, used in survey designs with unequal probability distributions [2].”
Reinforcement and Imitation Learning via Interactive No-Regret Learning (2014, methodology): “Alternate approaches include importance weighting techniques to transform the problem into a standard cost-sensitive classiﬁcation problem [14, 11] and other online learning approaches meant to handle “bandit” feedback.”
Policy Evaluation and Optimization with Continuous Treatments (2018, background): “IPW-based estimation normalizes the observed outcomes by the inverse of the propensity weights of the logging policy [8].”
Off-Policy Evaluation via Off-Policy Classification (2019, background): “Prior works [7, 10, 13, 21, 28, 34] do so with importance sampling (IS) [11], MDP modeling, or both.”
Horizon: Facebook's Open Source Applied Reinforcement Learning Platform (2018, methodology): “The step-wise importance sampling (IS) estimator [22] uses action propensities of logged and evaluated policies to scale logged rewards in order to correct for different action distributions between the two policies.”
Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning (2019, background): “IPS has a rich history in statistics [44, 20, 24], with successful crossover to RL [45].”
Bias Correction of Learned Generative Models using Likelihood-Free Importance Weighting (2019, methodology): “A classical recipe for correcting the bias in expectations, when samples from a different distribution than the ground truth are available, is to importance weight the samples according to the likelihood ratio [6].”
Residual Unfairness in Fair Machine Learning from Prejudiced Data (2018, methodology): “The classic Horvitz-Thompson estimator uses the inverse probability of sampling probability weights and is unbiased for population level estimates (Horvitz & Thompson, 1952).”
Population-based study of human papillomavirus infection and cervical neoplasia in rural Costa Rica. (2000, methodology): “Because HPV testing results were available from all subjects with abnormal diagnoses but were available from only a fraction of those with normal results, bias was prevented by weighting with a Horvitz‐ Thompson-type estimating function ( 19 ).”