Adaptive Threshold Sampling
Sampling is a fundamental problem in computer science and statistics. However, for a given task and stream, it is often not possible to choose good sampling probabilities in advance. We derive a general framework for adaptively changing the sampling probabilities via a collection of thresholds.In general, adaptive sampling procedures introduce dependence amongst the sampled points, making it difficult to compute expectations and ensure estimators are unbiased or consistent. Our framework address this issue and further shows when adaptive thresholds can be treated as if they were fixed thresholds which samples items independently. This makes our adaptive sampling schemes simple to apply as there is no need to create custom estimators for the sampling method. Using our framework, we derive new samplers that can address a broad range of new and existing problems including sampling with memory rather than sample size budgets, stratified samples, multiple objectives, distinct counting, and sliding windows. In particular, we design a sampling procedure for the top-K problem where, unlike in the heavy-hitter problem, the sketch size and sampling probabilities are adaptively chosen.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Efficient Spatial Estimation of Perceptual Thresholds for Retinal Implants via Gaussian Process Regression
Retinal prostheses restore vision by electrically stimulating surviving neurons, but calibrating perceptual thresholds (i.e., the minimum stimulus intensity required for perception) remains a time-intensive challenge, es…
GPRComparison of Uniform and Random Sampling for Speech and Music Signals
In this paper, we will provide a comparison between uniform and random sampling for speech and music signals. There are various sampling and recovery methods for audio signals. Here, we only investigate uniform and rando…
REAL Sampling: Boosting Factuality and Diversity of Open-Ended Generation via Asymptotic Entropy
Decoding methods for large language models (LLMs) usually struggle with the tradeoff between ensuring factuality and maintaining diversity. For example, a higher p threshold in the nucleus (top-p) sampling increases the …
DiversityHallucinationAbsolute convergence and error thresholds in non-active adaptive sampling
Non-active adaptive sampling is a way of building machine learning models from a training data base which are supposed to dynamically and automatically derive guaranteed sample size. In this context and regardless of the…
Decision MakingModel SelectionSchedulingMaxGap Bandit: Adaptive Algorithms for Approximate Ranking
This paper studies the problem of adaptively sampling from K distributions (arms) in order to identify the largest gap between any two adjacent means. We call this the MaxGap-bandit problem. This problem arises naturally…
Outlier Detection