Group-based active query selection for rapid diagnosis in time-critical situations

Gowtham Bellala, Suresh Bhavnani, Clayton Scott

Research output: Contribution to journalArticle

25 Citations (Scopus)

Abstract

In applications such as active learning and disease/fault diagnosis, one often encounters the problem of identifying an unknown object through a minimal number of queries. This problem has been referred to as query learning or object/entity identification. We consider three extensions of this fundamental problem that are motivated by practical considerations in real-world,time- critical identification tasks such as emergency response. First, we consider the problem where the objects are partitioned into groups, and the goal is to identify only the group to which the object belongs. Second, we address the situation where the queries are partitioned into groups, and an algorithm may suggest a group of queries to a human user, who then selects the actual query. Third, we consider the problem of object identification in the presence of persistent query noise, and relate it to group identification. To address these problems we show that a standard algorithm for object identification, known as generalized binary search, may be viewed as a generalization of Shannon-Fano coding. We then extend this result to the group-based settings, leading to new algorithms, whose performance is demonstrated through a logarithmic approximation bound, and through experiments on simulated data and a database used for toxic chemical identification.

Original languageEnglish (US)
Article number6121981
Pages (from-to)459-478
Number of pages20
JournalIEEE Transactions on Information Theory
Volume58
Issue number1
DOIs
StatePublished - Jan 2012

Fingerprint

Group
Failure analysis
learning
time
coding
Experiments
Disease
experiment
performance
Problem-Based Learning

Keywords

  • Active learning
  • decision trees
  • generalized binary search
  • persistent noise
  • Shannon-Fano coding
  • submodularity

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Cite this

Group-based active query selection for rapid diagnosis in time-critical situations. / Bellala, Gowtham; Bhavnani, Suresh; Scott, Clayton.

In: IEEE Transactions on Information Theory, Vol. 58, No. 1, 6121981, 01.2012, p. 459-478.

Research output: Contribution to journalArticle

@article{0c6b39d29d624780acae8379902275c7,
title = "Group-based active query selection for rapid diagnosis in time-critical situations",
abstract = "In applications such as active learning and disease/fault diagnosis, one often encounters the problem of identifying an unknown object through a minimal number of queries. This problem has been referred to as query learning or object/entity identification. We consider three extensions of this fundamental problem that are motivated by practical considerations in real-world,time- critical identification tasks such as emergency response. First, we consider the problem where the objects are partitioned into groups, and the goal is to identify only the group to which the object belongs. Second, we address the situation where the queries are partitioned into groups, and an algorithm may suggest a group of queries to a human user, who then selects the actual query. Third, we consider the problem of object identification in the presence of persistent query noise, and relate it to group identification. To address these problems we show that a standard algorithm for object identification, known as generalized binary search, may be viewed as a generalization of Shannon-Fano coding. We then extend this result to the group-based settings, leading to new algorithms, whose performance is demonstrated through a logarithmic approximation bound, and through experiments on simulated data and a database used for toxic chemical identification.",
keywords = "Active learning, decision trees, generalized binary search, persistent noise, Shannon-Fano coding, submodularity",
author = "Gowtham Bellala and Suresh Bhavnani and Clayton Scott",
year = "2012",
month = "1",
doi = "10.1109/TIT.2011.2169296",
language = "English (US)",
volume = "58",
pages = "459--478",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "1",

}

TY - JOUR

T1 - Group-based active query selection for rapid diagnosis in time-critical situations

AU - Bellala, Gowtham

AU - Bhavnani, Suresh

AU - Scott, Clayton

PY - 2012/1

Y1 - 2012/1

N2 - In applications such as active learning and disease/fault diagnosis, one often encounters the problem of identifying an unknown object through a minimal number of queries. This problem has been referred to as query learning or object/entity identification. We consider three extensions of this fundamental problem that are motivated by practical considerations in real-world,time- critical identification tasks such as emergency response. First, we consider the problem where the objects are partitioned into groups, and the goal is to identify only the group to which the object belongs. Second, we address the situation where the queries are partitioned into groups, and an algorithm may suggest a group of queries to a human user, who then selects the actual query. Third, we consider the problem of object identification in the presence of persistent query noise, and relate it to group identification. To address these problems we show that a standard algorithm for object identification, known as generalized binary search, may be viewed as a generalization of Shannon-Fano coding. We then extend this result to the group-based settings, leading to new algorithms, whose performance is demonstrated through a logarithmic approximation bound, and through experiments on simulated data and a database used for toxic chemical identification.

AB - In applications such as active learning and disease/fault diagnosis, one often encounters the problem of identifying an unknown object through a minimal number of queries. This problem has been referred to as query learning or object/entity identification. We consider three extensions of this fundamental problem that are motivated by practical considerations in real-world,time- critical identification tasks such as emergency response. First, we consider the problem where the objects are partitioned into groups, and the goal is to identify only the group to which the object belongs. Second, we address the situation where the queries are partitioned into groups, and an algorithm may suggest a group of queries to a human user, who then selects the actual query. Third, we consider the problem of object identification in the presence of persistent query noise, and relate it to group identification. To address these problems we show that a standard algorithm for object identification, known as generalized binary search, may be viewed as a generalization of Shannon-Fano coding. We then extend this result to the group-based settings, leading to new algorithms, whose performance is demonstrated through a logarithmic approximation bound, and through experiments on simulated data and a database used for toxic chemical identification.

KW - Active learning

KW - decision trees

KW - generalized binary search

KW - persistent noise

KW - Shannon-Fano coding

KW - submodularity

UR - http://www.scopus.com/inward/record.url?scp=84855672674&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84855672674&partnerID=8YFLogxK

U2 - 10.1109/TIT.2011.2169296

DO - 10.1109/TIT.2011.2169296

M3 - Article

VL - 58

SP - 459

EP - 478

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 1

M1 - 6121981

ER -