Selecting the most likely faulty component from numerous candidate diagnoses has always been a focal point in model diagnostics. Existing methods require determining all candidate diagnoses first and then calculating the posterior fault probability for each component, which is challenging to yield effective results within a finite timeframe. To solve the problems, a research team led by Jihong Ouyang published their new research on 15 May 2025 in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.

In this research, they propose an efficient algorithm for solving the posterior failure probabilities of components, which can approximate a ranking of failure probabilities for all components (the PIHS is an approximate algorithm, while all the comparison algorithms are complete algorithms). When solving large-scale circuits, the time required to solve MHSs significantly affects the overall efficiency of the algorithm, making it difficult for many algorithms to return the posterior failure probabilities of components. Initially, they utilize the BAMHS algorithm combined with an incremental strategy to propose a solving framework. Subsequently, they present two important propositions for the elimination of redundant hitting sets. Finally, they provide specific expressions for the minimization parameters. In terms of the number of instances solved, they can provide the posterior failure probabilities for all components in the ISCAS-85 conflict dataset, whereas nearly half of the circuits that the ten comparatively efficient algorithms can solve account for less than 10% of instances. In terms of accuracy, they select components that rank in the top 1% to 10% of posterior failure probabilities and achieve an average accuracy of over 85%. Their algorithm shows an order of magnitude improvement in runtime compared to several current advanced hitting set algorithms.

DOI: 10.1007/s11704-024-40393-y