論文の概要: RBF-HS: Recursive Best-First Hitting Set Search

• arxiv url: http://arxiv.org/abs/2010.04282v2
• Date: Mon, 21 Feb 2022 14:29:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-09 12:26:57.531021
• Title: RBF-HS: Recursive Best-First Hitting Set Search
• Title（参考訳）: RBF-HS:再帰的なベストセッティングセット検索
• Authors: Patrick Rodler
• Abstract要約: 本稿では,2つの新しい診断アルゴリズムを提案する。 RBF-HS (Recursive Best-First Hitting Set Search)とHBF-HS (Hybrid Best-First Hitting Set Search) 最小限の心不全説明の計算では,RBF-HSがメモリ要求を大幅に削減することがわかった。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Various model-based diagnosis scenarios require the computation of most preferred fault explanations. Existing algorithms that are sound (i.e., output only actual fault explanations) and complete (i.e., can return all explanations), however, require exponential space to achieve this task. As a remedy, we propose two novel diagnostic search algorithms, called RBF-HS (Recursive Best-First Hitting Set Search) and HBF-HS (Hybrid Best-First Hitting Set Search), which build upon tried and tested techniques from the heuristic search domain. RBF-HS can enumerate an arbitrary predefined finite number of fault explanations in best-first order within linear space bounds, without sacrificing the desirable soundness or completeness properties. The idea of HBF-HS is to find a trade-off between runtime optimization and a restricted space consumption that does not exceed the available memory. In extensive experiments on real-world diagnosis cases we compared our approaches to Reiter's HS-Tree, a state-of-the-art method that gives the same theoretical guarantees and is as general(ly applicable) as the suggested algorithms. For the computation of minimum-cardinality fault explanations, we find that (1) RBF-HS reduces memory requirements substantially in most cases by up to several orders of magnitude, (2) in more than a third of the cases, both memory savings and runtime savings are achieved, and (3) given the runtime overhead is significant, using HBF-HS instead of RBF-HS reduces the runtime to values comparable with HS-Tree while keeping the used memory reasonably bounded. When computing most probable fault explanations, we observe that RBF-HS tends to trade memory savings more or less one-to-one for runtime overheads. Again, HBF-HS proves to be a reasonable remedy to cut down the runtime while complying with practicable memory bounds.
• Abstract（参考訳）: 様々なモデルに基づく診断シナリオは、最も好ましい故障説明の計算を必要とする。 既存のアルゴリズム(すなわち、実際の故障説明のみを出力する)と完全(すなわち全ての説明を返す)は、このタスクを達成するために指数空間を必要とする。 本稿では,RBF-HS (Recursive Best-First Hitting Set Search) とHBF-HS (Hybrid Best-First Hitting Set Search) という2つの新しい診断アルゴリズムを提案する。 RBF-HSは、望ましい音性や完全性を犠牲にすることなく、線形空間境界の中で最優先の順序で任意の定義された有限個の故障説明を列挙することができる。 HBF-HSの考え方は、実行時最適化と利用可能なメモリを超えない制限された空間消費との間のトレードオフを見つけることである。 実世界の診断事例に関する広範な実験では,提案手法と同じ理論的な保証を与え,一般に適用可能な(適用可能な)手法であるreiterのhs-treeと比較した。 その結果,(1)rbf-hsはメモリ要求を最大で数桁削減し,(2)3分の1以上のケースではメモリ節約とランタイムの節約を実現し,(3)ランタイムのオーバーヘッドを考慮すれば,rbf-hsの代わりにhbf-hsを使用することで,使用メモリを合理的に境界化しながらhs-treeに匹敵する値にランタイムを還元できることがわかった。 最も予測可能なフォールト説明を計算する場合、RBF-HSは実行時のオーバーヘッドに対してメモリ節約を多かれ少なかれ1対1で処理する傾向にある。 繰り返しになるが、HBF-HSは、実践可能なメモリバウンダリに準拠しながらランタイムを削減できる適切な対策であることを証明している。

関連論文リスト

• IDentity with Locality: An ideal hash for gene sequence search [34.574424989422674]
  大部分の遺伝子検索システムは、ブルームフィルタ(BF)のようなハッシュベースのデータ構造を使っている。 本稿では,IDL(Identity with Locality)ハッシュファミリーと呼ばれる新しいハッシュ関数を提案する。
  論文  参考訳（メタデータ） (2024-06-21T06:47:39Z)
• Learning to Hash Robustly, with Guarantees [79.68057056103014]
  本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。 理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。 我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
  論文  参考訳（メタデータ） (2021-08-11T20:21:30Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• DynamicHS: Streamlining Reiter's Hitting-Set Tree for Sequential Diagnosis [0.0]
  診断セッションを通じて状態を維持するHS-Treeの変種であるDynamicHSを提案する。 DynamicHSの理由を証明し、HS-Treeのwrtに明確な優越性を証明します。 計算時間。
  論文  参考訳（メタデータ） (2020-12-21T01:59:19Z)
• ROME: Robustifying Memory-Efficient NAS via Topology Disentanglement and Gradient Accumulation [106.04777600352743]
  微分可能なアーキテクチャサーチ(DARTS)は、スーパーネット全体がメモリに格納されているため、メモリコストが大幅に低下する。 シングルパスのDARTSが登場し、各ステップでシングルパスのサブモデルのみを選択する。 メモリフレンドリーだが、計算コストも低い。 RObustifying Memory-Efficient NAS (ROME) と呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-23T06:34:07Z)
• Sound, Complete, Linear-Space, Best-First Diagnosis Search [0.0]
  我々はKorfのよく知られたRBFSアルゴリズムに基づく診断探索法RBF-HSを提案する。 RBF-HSは、線形空間境界の中で最優先の順序で任意の数の断層説明を列挙することができる。
  論文  参考訳（メタデータ） (2020-09-25T12:49:49Z)
• A Genetic Algorithm for Obtaining Memory Constrained Near-Perfect Hashing [0.0]
  本稿では,検索時の比較回数の最小化と,総コレクションサイズを最小化することに焦点を当てたハッシュテーブルに基づくアプローチを提案する。 論文は、ほぼ完全なハッシュはバイナリ検索よりも高速であるが、完全なハッシュよりも少ないメモリを使用することを示した。
  論文  参考訳（メタデータ） (2020-07-16T12:57:15Z)
• Best-First Beam Search [78.71330480725668]
  本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。 ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
  論文  参考訳（メタデータ） (2020-07-08T05:56:01Z)
• Progressively Pretrained Dense Corpus Index for Open-Domain Question Answering [87.32442219333046]
  本稿では,段落エンコーダを事前学習するための簡易かつ資源効率の高い手法を提案する。 本手法は,事前学習に7倍の計算資源を使用する既存の高密度検索法より優れている。
  論文  参考訳（メタデータ） (2020-04-30T18:09:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。