A rank-based approach to active diagnosis

Gowtham Bellala, Jason Stanley, Suresh Bhavnani, Clayton Scott

Research output: Contribution to journalArticle

9 Citations (Scopus)

Abstract

The problem of active diagnosis arises in several applications such as disease diagnosis and fault diagnosis in computer networks, where the goal is to rapidly identify the binary states of a set of objects (e.g., faulty or working) by sequentially selecting, and observing, potentially noisy responses to binary valued queries. Previous work in this area chooses queries sequentially based on Information gain, and the object states are inferred by maximum a posteriori (MAP) estimation. In this work, rather than MAP estimation, we aim to rank objects according to their posterior fault probability. We propose a greedy algorithm to choose queries sequentially by maximizing the area under the ROC curve associated with the ranked list. The proposed algorithm overcomes limitations of existing work. When multiple faults may be present, the proposed algorithm does not rely on belief propagation, making it feasible for large scale networks with little loss in performance. When a single fault is present, the proposed algorithm can be implemented without knowledge of the underlying query noise distribution, making it robust to any misspecification of these noise parameters. We demonstrate the performance of the proposed algorithm through experiments on computer networks, a toxic chemical database, and synthetic datasets.

Original languageEnglish (US)
Article number6420840
Pages (from-to)2078-2090
Number of pages13
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Volume35
Issue number9
DOIs
StatePublished - 2013

Fingerprint

Query
Maximum a Posteriori Estimation
Fault
Computer Networks
Computer networks
Choose
Noise
Binary
Information Gain
Belief Propagation
Chemical Databases
Misspecification
Receiver Operating Characteristic Curve
Greedy Algorithm
Fault Diagnosis
Poisons
ROC Curve
Area Under Curve
Failure analysis
Demonstrate

Keywords

  • Active diagnosis
  • active learning
  • area under the ROC curve
  • Bayesian network
  • persistent noise

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Vision and Pattern Recognition
  • Software
  • Computational Theory and Mathematics
  • Applied Mathematics
  • Medicine(all)

Cite this

A rank-based approach to active diagnosis. / Bellala, Gowtham; Stanley, Jason; Bhavnani, Suresh; Scott, Clayton.

In: IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 35, No. 9, 6420840, 2013, p. 2078-2090.

Research output: Contribution to journalArticle

Bellala, Gowtham ; Stanley, Jason ; Bhavnani, Suresh ; Scott, Clayton. / A rank-based approach to active diagnosis. In: IEEE Transactions on Pattern Analysis and Machine Intelligence. 2013 ; Vol. 35, No. 9. pp. 2078-2090.
@article{ced2b5c1414040e8afdea7b5b5216db9,
title = "A rank-based approach to active diagnosis",
abstract = "The problem of active diagnosis arises in several applications such as disease diagnosis and fault diagnosis in computer networks, where the goal is to rapidly identify the binary states of a set of objects (e.g., faulty or working) by sequentially selecting, and observing, potentially noisy responses to binary valued queries. Previous work in this area chooses queries sequentially based on Information gain, and the object states are inferred by maximum a posteriori (MAP) estimation. In this work, rather than MAP estimation, we aim to rank objects according to their posterior fault probability. We propose a greedy algorithm to choose queries sequentially by maximizing the area under the ROC curve associated with the ranked list. The proposed algorithm overcomes limitations of existing work. When multiple faults may be present, the proposed algorithm does not rely on belief propagation, making it feasible for large scale networks with little loss in performance. When a single fault is present, the proposed algorithm can be implemented without knowledge of the underlying query noise distribution, making it robust to any misspecification of these noise parameters. We demonstrate the performance of the proposed algorithm through experiments on computer networks, a toxic chemical database, and synthetic datasets.",
keywords = "Active diagnosis, active learning, area under the ROC curve, Bayesian network, persistent noise",
author = "Gowtham Bellala and Jason Stanley and Suresh Bhavnani and Clayton Scott",
year = "2013",
doi = "10.1109/TPAMI.2013.30",
language = "English (US)",
volume = "35",
pages = "2078--2090",
journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",
issn = "0162-8828",
publisher = "IEEE Computer Society",
number = "9",

}

TY - JOUR

T1 - A rank-based approach to active diagnosis

AU - Bellala, Gowtham

AU - Stanley, Jason

AU - Bhavnani, Suresh

AU - Scott, Clayton

PY - 2013

Y1 - 2013

N2 - The problem of active diagnosis arises in several applications such as disease diagnosis and fault diagnosis in computer networks, where the goal is to rapidly identify the binary states of a set of objects (e.g., faulty or working) by sequentially selecting, and observing, potentially noisy responses to binary valued queries. Previous work in this area chooses queries sequentially based on Information gain, and the object states are inferred by maximum a posteriori (MAP) estimation. In this work, rather than MAP estimation, we aim to rank objects according to their posterior fault probability. We propose a greedy algorithm to choose queries sequentially by maximizing the area under the ROC curve associated with the ranked list. The proposed algorithm overcomes limitations of existing work. When multiple faults may be present, the proposed algorithm does not rely on belief propagation, making it feasible for large scale networks with little loss in performance. When a single fault is present, the proposed algorithm can be implemented without knowledge of the underlying query noise distribution, making it robust to any misspecification of these noise parameters. We demonstrate the performance of the proposed algorithm through experiments on computer networks, a toxic chemical database, and synthetic datasets.

AB - The problem of active diagnosis arises in several applications such as disease diagnosis and fault diagnosis in computer networks, where the goal is to rapidly identify the binary states of a set of objects (e.g., faulty or working) by sequentially selecting, and observing, potentially noisy responses to binary valued queries. Previous work in this area chooses queries sequentially based on Information gain, and the object states are inferred by maximum a posteriori (MAP) estimation. In this work, rather than MAP estimation, we aim to rank objects according to their posterior fault probability. We propose a greedy algorithm to choose queries sequentially by maximizing the area under the ROC curve associated with the ranked list. The proposed algorithm overcomes limitations of existing work. When multiple faults may be present, the proposed algorithm does not rely on belief propagation, making it feasible for large scale networks with little loss in performance. When a single fault is present, the proposed algorithm can be implemented without knowledge of the underlying query noise distribution, making it robust to any misspecification of these noise parameters. We demonstrate the performance of the proposed algorithm through experiments on computer networks, a toxic chemical database, and synthetic datasets.

KW - Active diagnosis

KW - active learning

KW - area under the ROC curve

KW - Bayesian network

KW - persistent noise

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

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

U2 - 10.1109/TPAMI.2013.30

DO - 10.1109/TPAMI.2013.30

M3 - Article

VL - 35

SP - 2078

EP - 2090

JO - IEEE Transactions on Pattern Analysis and Machine Intelligence

JF - IEEE Transactions on Pattern Analysis and Machine Intelligence

SN - 0162-8828

IS - 9

M1 - 6420840

ER -