A rank-based approach to active diagnosis.

Area of Science:

• Computer Science
• Machine Learning
• Network Engineering

Background:

• Active diagnosis aims to identify binary object states (e.g., faulty/working) through sequential, noisy queries.
• Existing methods use Information Gain for query selection and Maximum A Posteriori (MAP) estimation for state inference.

Purpose of the Study:

• To develop a novel active diagnosis algorithm that ranks objects by posterior fault probability.
• To overcome limitations of existing methods, particularly in large-scale networks and with unknown noise distributions.

Main Methods:

• A greedy algorithm is proposed to sequentially select queries that maximize the area under the Receiver Operating Characteristic (ROC) curve.
• The algorithm ranks objects based on their posterior fault probability, moving beyond MAP estimation.

Main Results:

• The algorithm performs effectively in large-scale networks without relying on belief propagation.
• It demonstrates robustness to noise parameter misspecification when only a single fault is present.
• Experimental validation was conducted on computer networks, a toxic chemical database, and synthetic datasets.

Conclusions:

• The proposed greedy algorithm offers a more feasible and robust approach to active diagnosis compared to existing techniques.
• It provides improved performance for both single and multiple fault scenarios in diverse applications.