Extensions of Generalized Binary Search to Group Identification and Exponential Costs

Details

• Personal Author:
  Bellala G ; Bhavnani SK ; Scott C
• Description:
  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. [Description provided by NIOSH]
• Subjects:
  Decision Making Nervous System Occupational Health Safety
• Keywords:
  Algorithms Cognitive Function Decision Making Simulation Methods
• Publisher:
  Neural Information Processing Systems
• Document Type:
  Text
• Funding:
  Grant
• Genre:
  Proceedings
• Place as Subject:
  Michigan ; OSHA Region 5 ; OSHA Region 6 ; Texas
• CIO:
  National Institute for Occupational Safety and Health (NIOSH)
• Topic:
  Workplace Safety & Health
• Location:
  North America
• Pages in Document:
  1-9
• NIOSHTIC Number:
  nn:20055937
• Citation:
  Proceedings of NeurIPS 2010: 24th Conference on Neural Information Processing Systems, December 6-11, 2010, Vancouver. San Diego, CA: Neural Information Processing Systems, 2010 Dec; :1-9
• Federal Fiscal Year:
  2011
• Performing Organization:
  University of Texas Medical Branch, Galveston
• Peer Reviewed:
  False
• Start Date:
  20100901
• Source Full Name:
  Proceedings of NeurIPS 2010: 24th Conference on Neural Information Processing Systems, December 6-11, 2010, Vancouver
• End Date:
  20130131
• Collection(s):
  National Institute for Occupational Safety and Health
• Main Document Checksum:
  urn:sha-512:c2677581b4af0dd2f0c8df36abb0f56788aeece4f638d278eeee10235ddf6aa6ef287956670ce2f124cd3ec252a8d785b78a28d66eb145bbb94b8bbb12ca51cb
• Download URL:
  https://stacks.cdc.gov/view/cdc/213685/cdc_213685_DS1.pdf
• File Type:
  [PDF - 232.60 KB ]