Active diagnosis via AUC maximization

An efficient approach for multiple fault identification in large scale, noisy networks

Gowtham Bellala, Jason Stanley, Clayton Scott, Suresh Bhavnani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 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 ob-serving, (noisy) responses to binary valued queries. Current algorithms in this area rely on loopy belief propagation for active query selection. These algorithms have an exponential time complexity, making them slow and even intractable in large networks. We propose a rank-based greedy algorithm that se-quentially chooses queries such that the area under the ROC curve of the rank-based output is maximized. The AUC criterion allows us to make a simplifying assumption that significantly reduces the complexity of active query selection (from exponential to near quadratic), with little or no compromise on the performance quality.

Original languageEnglish (US)
Title of host publicationProceedings of the 27th Conference on Uncertainty in Artificial Intelligence, UAI 2011
Pages35-42
Number of pages8
StatePublished - 2011
Event27th Conference on Uncertainty in Artificial Intelligence, UAI 2011 - Barcelona, Spain
Duration: Jul 14 2011Jul 17 2011

Other

Other27th Conference on Uncertainty in Artificial Intelligence, UAI 2011
CountrySpain
CityBarcelona
Period7/14/117/17/11

Fingerprint

Fault Identification
Query
Binary
Computer networks
Failure analysis
Belief Propagation
Receiver Operating Characteristic Curve
Exponential time
Computer Networks
Greedy Algorithm
Fault Diagnosis
Time Complexity
Choose
Output

ASJC Scopus subject areas

  • Artificial Intelligence
  • Applied Mathematics

Cite this

Bellala, G., Stanley, J., Scott, C., & Bhavnani, S. (2011). Active diagnosis via AUC maximization: An efficient approach for multiple fault identification in large scale, noisy networks. In Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, UAI 2011 (pp. 35-42)

Active diagnosis via AUC maximization : An efficient approach for multiple fault identification in large scale, noisy networks. / Bellala, Gowtham; Stanley, Jason; Scott, Clayton; Bhavnani, Suresh.

Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, UAI 2011. 2011. p. 35-42.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Bellala, G, Stanley, J, Scott, C & Bhavnani, S 2011, Active diagnosis via AUC maximization: An efficient approach for multiple fault identification in large scale, noisy networks. in Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, UAI 2011. pp. 35-42, 27th Conference on Uncertainty in Artificial Intelligence, UAI 2011, Barcelona, Spain, 7/14/11.
Bellala G, Stanley J, Scott C, Bhavnani S. Active diagnosis via AUC maximization: An efficient approach for multiple fault identification in large scale, noisy networks. In Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, UAI 2011. 2011. p. 35-42
Bellala, Gowtham ; Stanley, Jason ; Scott, Clayton ; Bhavnani, Suresh. / Active diagnosis via AUC maximization : An efficient approach for multiple fault identification in large scale, noisy networks. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, UAI 2011. 2011. pp. 35-42
@inproceedings{ba965af2e1cd4d55a4309fe519420f2d,
title = "Active diagnosis via AUC maximization: An efficient approach for multiple fault identification in large scale, noisy networks",
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 ob-serving, (noisy) responses to binary valued queries. Current algorithms in this area rely on loopy belief propagation for active query selection. These algorithms have an exponential time complexity, making them slow and even intractable in large networks. We propose a rank-based greedy algorithm that se-quentially chooses queries such that the area under the ROC curve of the rank-based output is maximized. The AUC criterion allows us to make a simplifying assumption that significantly reduces the complexity of active query selection (from exponential to near quadratic), with little or no compromise on the performance quality.",
author = "Gowtham Bellala and Jason Stanley and Clayton Scott and Suresh Bhavnani",
year = "2011",
language = "English (US)",
pages = "35--42",
booktitle = "Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, UAI 2011",

}

TY - GEN

T1 - Active diagnosis via AUC maximization

T2 - An efficient approach for multiple fault identification in large scale, noisy networks

AU - Bellala, Gowtham

AU - Stanley, Jason

AU - Scott, Clayton

AU - Bhavnani, Suresh

PY - 2011

Y1 - 2011

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 ob-serving, (noisy) responses to binary valued queries. Current algorithms in this area rely on loopy belief propagation for active query selection. These algorithms have an exponential time complexity, making them slow and even intractable in large networks. We propose a rank-based greedy algorithm that se-quentially chooses queries such that the area under the ROC curve of the rank-based output is maximized. The AUC criterion allows us to make a simplifying assumption that significantly reduces the complexity of active query selection (from exponential to near quadratic), with little or no compromise on the performance quality.

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 ob-serving, (noisy) responses to binary valued queries. Current algorithms in this area rely on loopy belief propagation for active query selection. These algorithms have an exponential time complexity, making them slow and even intractable in large networks. We propose a rank-based greedy algorithm that se-quentially chooses queries such that the area under the ROC curve of the rank-based output is maximized. The AUC criterion allows us to make a simplifying assumption that significantly reduces the complexity of active query selection (from exponential to near quadratic), with little or no compromise on the performance quality.

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

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

M3 - Conference contribution

SP - 35

EP - 42

BT - Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, UAI 2011

ER -