論文の概要: 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の適用性を保ちながら、これらのパフォーマンス改善を実現していることだ。
関連論文リスト
- 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) - METGEN: A Module-Based Entailment Tree Generation Framework for Answer
Explanation [59.33241627273023]
複数のモジュールと推論コントローラを備えたモジュールベースのEntailment Tree GENフレームワークMETGENを提案する。
質問に対して、METGENは、別々のモジュールで単一ステップのエンタテインメントを実行し、コントローラで推論フローを選択することで、エンタテインメントツリーを反復的に生成することができる。
実験の結果,METGENは従来の最先端モデルよりも9%のパラメータで優れていた。
論文 参考訳(メタデータ) (2022-05-05T12:06:02Z) - Hierarchical Shrinkage: improving the accuracy and interpretability of
tree-based methods [10.289846887751079]
木構造を改変しないポストホックアルゴリズムである階層収縮(Hierarchical Shrinkage, HS)を導入する。
HSは、他の正規化技術と併用しても、決定木の予測性能を大幅に向上させる。
すべてのコードとモデルはGithubにある本格的なパッケージでリリースされている。
論文 参考訳(メタデータ) (2022-02-02T02:43:23Z) - Frequent Itemset-driven Search for Finding Minimum Node Separators in
Complex Networks [61.2383572324176]
本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。
頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。
特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
論文 参考訳(メタデータ) (2022-01-18T11:16:40Z) - 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) - AdaS: Adaptive Scheduling of Stochastic Gradients [50.80697760166045]
我々は、textit "knowledge gain" と textit "mapping condition" の概念を導入し、Adaptive Scheduling (AdaS) と呼ばれる新しいアルゴリズムを提案する。
実験によると、AdaSは派生した指標を用いて、既存の適応学習手法よりも高速な収束と優れた一般化、そして(b)いつトレーニングを中止するかを決定するための検証セットへの依存の欠如を示す。
論文 参考訳(メタデータ) (2020-06-11T16:36:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。