DynamicHS: Streamlining Reiter's Hitting-Set Tree for Sequential Diagnosis

• URL: http://arxiv.org/abs/2012.11078v1
• Date: Mon, 21 Dec 2020 01:59:19 GMT
• Title: DynamicHS: Streamlining Reiter's Hitting-Set Tree for Sequential Diagnosis
• Authors: Patrick Rodler
• Abstract summary: We propose DynamicHS, a variant of HS-Tree that maintains state throughout the diagnostic session. We prove the reasonability of DynamicHS and testify its clear superiority to HS-Tree wrt. computation time.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a system that does not work as expected, Sequential Diagnosis (SD) aims at suggesting a series of system measurements to isolate the true explanation for the system's misbehavior from a potentially exponential set of possible explanations. To reason about the best next measurement, SD methods usually require a sample of possible fault explanations at each step of the iterative diagnostic process. The computation of this sample can be accomplished by various diagnostic search algorithms. Among those, Reiter's HS-Tree is one of the most popular due its desirable properties and general applicability. Usually, HS-Tree is used in a stateless fashion throughout the SD process to (re)compute a sample of possible fault explanations in each iteration, each time given the latest (updated) system knowledge including all so-far collected measurements. At this, the built search tree is discarded between two iterations, although often large parts of the tree have to be rebuilt in the next iteration, involving redundant operations and calls to costly reasoning services. As a remedy to this, we propose DynamicHS, a variant of HS-Tree that maintains state throughout the diagnostic session and additionally embraces special strategies to minimize the number of expensive reasoner invocations. In this vein, DynamicHS provides an answer to a longstanding question posed by Raymond Reiter in his seminal paper from 1987. Extensive evaluations on real-world diagnosis problems prove the reasonability of the DynamicHS and testify its clear superiority to HS-Tree wrt. computation time. More specifically, DynamicHS outperformed HS-Tree in 96% of the executed sequential diagnosis sessions and, per run, the latter required up to 800% the time of the former. Remarkably, DynamicHS achieves these performance improvements while preserving all desirable properties as well as the general applicability of HS-Tree.

Related papers

• CodeTree: Agent-guided Tree Search for Code Generation with Large Language Models [91.15135237584771]
  Large language models (LLMs) can act as agents with capabilities to self-refine and improve generated code autonomously. We propose CodeTree, a framework for LLM agents to efficiently explore the search space in different stages of the code generation process. Specifically, we adopted a unified tree structure to explicitly explore different coding strategies, generate corresponding coding solutions, and subsequently refine the solutions.
  arXiv  Detail & Related papers  (2024-11-07T00:09:54Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• Dynamic Data Pruning for Automatic Speech Recognition [58.95758272440217]
  We introduce Dynamic Data Pruning for ASR (DDP-ASR), which offers fine-grained pruning granularities specifically tailored for speech-related datasets. Our experiments show that DDP-ASR can save up to 1.6x training time with negligible performance loss.
  arXiv  Detail & Related papers  (2024-06-26T14:17:36Z)
• Tree-based Learning for High-Fidelity Prediction of Chaos [0.2999888908665658]
  TreeDOX is a tree-based approach to model-free forecasting of chaotic systems. It uses time delay overembedding as explicit short-term memory and Extra-Trees Regressors to perform feature reduction and forecasting. We demonstrate the state-of-the-art performance of TreeDOX using the Henon map, Lorenz and Kuramoto-Sivashinsky systems, and the real-world Southern Oscillation Index.
  arXiv  Detail & Related papers  (2024-03-12T01:16:29Z)
• FastDiagP: An Algorithm for Parallelized Direct Diagnosis [64.65251961564606]
  FastDiag is a typical direct diagnosis algorithm that supports diagnosis calculation without predetermining conflicts. We propose a novel algorithm, so-called FastDiagP, which is based on the idea of speculative programming. This mechanism helps to provide consistency checks with fast answers and boosts the algorithm's runtime performance.
  arXiv  Detail & Related papers  (2023-05-11T16:26:23Z)
• Entailment Tree Explanations via Iterative Retrieval-Generation Reasoner [56.08919422452905]
  We propose an architecture called Iterative Retrieval-Generation Reasoner (IRGR) Our model is able to explain a given hypothesis by systematically generating a step-by-step explanation from textual premises. We outperform existing benchmarks on premise retrieval and entailment tree generation, with around 300% gain in overall correctness.
  arXiv  Detail & Related papers  (2022-05-18T21:52:11Z)
• Hierarchical Shrinkage: improving the accuracy and interpretability of tree-based methods [10.289846887751079]
  We introduce Hierarchical Shrinkage (HS), a post-hoc algorithm that does not modify the tree structure. HS substantially increases the predictive performance of decision trees, even when used in conjunction with other regularization techniques. All code and models are released in a full-fledged package available on Github.
  arXiv  Detail & Related papers  (2022-02-02T02:43:23Z)
• Evaluating Tree Explanation Methods for Anomaly Reasoning: A Case Study of SHAP TreeExplainer and TreeInterpreter [6.718611456024702]
  We investigate the performance of two methods for explaining tree-based models- Tree Interpreter (TI) and SHapley Additive exPlanations TreeExplainer (SHAP-TE) We find that, although the SHAP-TE offers consistency guarantees over TI, at the cost of increased computation, consistency does not necessarily improve the explanation performance in our case study.
  arXiv  Detail & Related papers  (2020-10-13T23:18:26Z)
• RBF-HS: Recursive Best-First Hitting Set Search [0.0]
  We propose two novel diagnostic search algorithms. RBF-HS (Recursive Best-First Hitting Set Search) and HBF-HS (Hybrid Best-First Hitting Set Search) For the computation of minimum-cardinality fault explanations, we find that RBF-HS reduces memory requirements substantially.
  arXiv  Detail & Related papers  (2020-10-08T22:09:39Z)
• Sound, Complete, Linear-Space, Best-First Diagnosis Search [0.0]
  We propose RBF-HS, a diagnostic search method based on Korf's well-known RBFS algorithm. RBF-HS can enumerate an arbitrary fixed number of fault explanations in best-first order within linear space bounds.
  arXiv  Detail & Related papers  (2020-09-25T12:49:49Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  We present a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
  arXiv  Detail & Related papers  (2020-07-24T17:06:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.