Extensions of Generalized Binary Search to Group Identification and Exponential Costs
Generalized Binary Search (GBS) is a well known greedy algorithm for identifying an unknown object while minimizing the number of yes" or "no" questions posed about that object, and arises in problems such as active learning and active diagnosis. Here, we provide a coding-theoretic interpretation for GBS and show that GBS can be viewed as a top-down algorithm that greedily minimizes the expected number of queries required to identify an object. This interpretation is then used to extend GBS in two ways. First, we consider the case where the objects are partitioned into groups, and the objective is to identify only the group to which the object belongs. Then, we consider the case where the cost of identifying an object grows exponentially in the number of queries. In each case, we present an exact formula for the objective function involving Shannon or Renyi entropy, and develop a greedy algorithm for minimizing it."
Code (0)
등록된 구현이 없습니다.
Tasks
Active LearningObjectSimilar Papers 제목 키워드 기반
Hadamard Extensions and the Identification of Mixtures of Product Distributions
The Hadamard Extension of a matrix is the matrix consisting of all Hadamard products of subsets of its rows. This construction arises in the context of identifying a mixture of product distributions on binary random vari…
Subgroup detection in linear growth curve models with generalized linear mixed model (GLMM) trees
Growth curve models are popular tools for studying the development of a response variable within subjects over time. Heterogeneity between subjects is common in such models, and researchers are typically interested in ex…
Time SeriesGaussian Variational Inference with Non-Gaussian Factors for State Estimation: A UWB Localization Case Study
This letter extends the exactly sparse Gaussian variational inference (ESGVI) algorithm for state estimation in two complementary directions. First, ESGVI is generalized to operate on matrix Lie groups, enabling the esti…
Probability Link Models with Symmetric Information Divergence
This paper introduces link functions for transforming one probability distribution to another such that the Kullback-Leibler and R\'enyi divergences between the two distributions are symmetric. Two general classes of lin…
Survival AnalysisOn extensions of partial priorities in school choice
We consider a school choice matching model where the priorities for schools are represented by binary relations that may not be weak order. We focus on the (total order) extensions of the binary relations. We introduce a…