論文の概要: DynamicHS: Streamlining Reiter's Hitting-Set Tree for Sequential
Diagnosis
- arxiv url: http://arxiv.org/abs/2012.11078v1
- Date: Mon, 21 Dec 2020 01:59:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-29 11:25:03.143268
- Title: DynamicHS: Streamlining Reiter's Hitting-Set Tree for Sequential
Diagnosis
- Title(参考訳): DynamicHS:シークエンシャル診断のためのライターのハッティングセットツリーのストリーム化
- Authors: Patrick Rodler
- Abstract要約: 診断セッションを通じて状態を維持するHS-Treeの変種であるDynamicHSを提案する。
DynamicHSの理由を証明し、HS-Treeのwrtに明確な優越性を証明します。
計算時間。
- 参考スコア(独自算出の注目度): 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.
- Abstract(参考訳): 期待通りに機能しないシステムを考えると、シーケンシャル診断 (sd) は、システムの誤動作の真の説明を潜在的に指数関数的な説明の集合から分離する一連のシステム計測を提案することを目的としている。
SD法は、最もよい次の測定を推察するために、通常反復診断プロセスの各ステップで可能な故障説明のサンプルを必要とする。
このサンプルの計算は様々な診断探索アルゴリズムによって達成される。
その中でも、ReiterのHS-Treeはその望ましい特性と一般的な適用性から最も人気がある。
通常、HS-TreeはSDプロセス全体を通してステートレスな方法で使われ、各イテレーションで可能な障害説明のサンプルを(再)計算する。
この時点では、構築されたサーチツリーは2つのイテレーションの間に破棄されるが、多くの場合、ツリーの大きな部分は次のイテレーションで再構築され、冗長な操作と費用のかかる推論サービスへの呼び出しが必要となる。
これに対する対策として,診断セッション全体を通して状態を保ち,さらに高価な推論回数を最小限に抑えるための特別な戦略を取り入れたHS-Treeの変種であるDynamicHSを提案する。
この例では、DynamicHSは1987年の論文の中でレイモンド・ライター(Raymond Reiter)の長年の疑問に対する答えを提供している。
実世界の診断問題に対する広範囲な評価は、DynamicHSの推論可能性を示し、HS-Tree wrtに対する明確な優位性を証明している。
計算時間。
より具体的には、DynamicHSは実行されたシーケンシャル診断セッションの96%でHS-Treeを上回り、実行毎に後者は前者の800%の時間を必要とした。
注目すべきは、DynamicHSは、すべての望ましい特性とHS-Treeの適用性を保ちながら、これらのパフォーマンス改善を実現していることだ。
関連論文リスト
- CodeTree: Agent-guided Tree Search for Code Generation with Large Language Models [106.11371409170818]
大規模言語モデル(LLM)は、生成されたコードを自己定義し、自律的に改善する機能を持つエージェントとして機能する。
コード生成プロセスの異なる段階における探索空間を効率的に探索するLLMエージェントのためのフレームワークであるCodeTreeを提案する。
具体的には、異なるコーディング戦略を明示的に探求し、対応するコーディングソリューションを生成し、その後、ソリューションを洗練するために統合されたツリー構造を採用しました。
論文 参考訳(メタデータ) (2024-11-07T00:09:54Z) - LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。
GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
論文 参考訳(メタデータ) (2024-06-29T05:14:04Z) - Dynamic Data Pruning for Automatic Speech Recognition [58.95758272440217]
ASR(DDP-ASR)のダイナミック・データ・プルーニング(Dynamic Data Pruning for ASR)を導入し,音声関連データセットに特化して微細なプルーニングの粒度を提供する。
実験の結果,DDP-ASRは最大1.6倍のトレーニング時間を節約できることがわかった。
論文 参考訳(メタデータ) (2024-06-26T14:17:36Z) - Tree-based Learning for High-Fidelity Prediction of Chaos [0.2999888908665658]
TreeDOXは、カオスシステムのモデルフリー予測に対するツリーベースのアプローチである。
時間遅延オーバー埋め込みを明示的な短期記憶として使用し、Extra-Trees Regressorsを使用して機能の削減と予測を行う。
我々はHenon map, Lorenz and Kuramoto-Sivashinsky system, and the real-world Southern Oscillation Indexを用いてTreeDOXの最先端性能を示す。
論文 参考訳(メタデータ) (2024-03-12T01:16:29Z) - FastDiagP: An Algorithm for Parallelized Direct Diagnosis [64.65251961564606]
FastDiagは、競合を事前に決定せずに診断計算をサポートする典型的な直接診断アルゴリズムである。
本稿では,投機的プログラミングのアイデアに基づく新しいアルゴリズムであるFastDiagPを提案する。
このメカニズムは、高速な回答で一貫性チェックを提供し、アルゴリズムのランタイムパフォーマンスを高めるのに役立つ。
論文 参考訳(メタデータ) (2023-05-11T16:26:23Z) - Entailment Tree Explanations via Iterative Retrieval-Generation Reasoner [56.08919422452905]
我々はIRGR(Iterative Retrieval-Generation Reasoner)と呼ばれるアーキテクチャを提案する。
本モデルでは,テキストの前提からステップバイステップの説明を体系的に生成することにより,与えられた仮説を説明することができる。
前提条件の検索と細分化木の生成に関する既存のベンチマークを上回り、全体の正しさはおよそ300%向上した。
論文 参考訳(メタデータ) (2022-05-18T21:52:11Z) - Hierarchical Shrinkage: improving the accuracy and interpretability of
tree-based methods [10.289846887751079]
木構造を改変しないポストホックアルゴリズムである階層収縮(Hierarchical Shrinkage, HS)を導入する。
HSは、他の正規化技術と併用しても、決定木の予測性能を大幅に向上させる。
すべてのコードとモデルはGithubにある本格的なパッケージでリリースされている。
論文 参考訳(メタデータ) (2022-02-02T02:43:23Z) - Evaluating Tree Explanation Methods for Anomaly Reasoning: A Case Study
of SHAP TreeExplainer and TreeInterpreter [6.718611456024702]
木に基づくモデルを記述するための2つの手法-木インタープリタ(TI)とシャプレー付加例木説明器(SHAP-TE)-の性能について検討する。
SHAP-TEはTI上での整合性を保証するが,計算量の増加を犠牲にすることで,このケーススタディでは必ずしも整合性は向上しないことがわかった。
論文 参考訳(メタデータ) (2020-10-13T23:18:26Z) - RBF-HS: Recursive Best-First Hitting Set Search [0.0]
本稿では,2つの新しい診断アルゴリズムを提案する。
RBF-HS (Recursive Best-First Hitting Set Search)とHBF-HS (Hybrid Best-First Hitting Set Search)
最小限の心不全説明の計算では,RBF-HSがメモリ要求を大幅に削減することがわかった。
論文 参考訳(メタデータ) (2020-10-08T22:09:39Z) - Sound, Complete, Linear-Space, Best-First Diagnosis Search [0.0]
我々はKorfのよく知られたRBFSアルゴリズムに基づく診断探索法RBF-HSを提案する。
RBF-HSは、線形空間境界の中で最優先の順序で任意の数の断層説明を列挙することができる。
論文 参考訳(メタデータ) (2020-09-25T12:49:49Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳(メタデータ) (2020-07-24T17:06:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。