論文の概要: Deep Dive into Probabilistic Delta Debugging: Insights and Simplifications

• arxiv url: http://arxiv.org/abs/2408.04735v1
• Date: Thu, 8 Aug 2024 19:30:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-12 17:18:49.489942
• Title: Deep Dive into Probabilistic Delta Debugging: Insights and Simplifications
• Title（参考訳）: 確率的デルタデバッグを深く掘り下げる - 洞察と単純化
• Authors: Mengxiao Zhang, Zhenyang Xu, Yongqiang Tian, Xinru Cheng, Chengnian Sun,
• Abstract要約: アドバンストなddminであるProbDDが提案され、最先端のパフォーマンスを実現している。 ProbDDの詳細な理論的解析を行い、確率とサブセットサイズの変化の傾向を明らかにする。 本稿では,ProbDDの簡易版であるCDDを提案する。
• 参考スコア（独自算出の注目度）: 6.393194328016689
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a list L of elements and a property that L exhibits, ddmin is a well-known test input minimization algorithm designed to automatically eliminate irrelevant elements from L. This algorithm is extensively adopted in test input minimization and software debloating. Recently, ProbDD, an advanced variant of ddmin, has been proposed and achieved state-of-the-art performance. Employing Bayesian optimization, ProbDD predicts the likelihood of each element in L being essential, and statistically decides which elements and how many should be removed each time. Despite its impressive results, the theoretical probabilistic model of ProbDD is complex, and the specific factors driving its superior performance have not been investigated. In this paper, we conduct the first in-depth theoretical analysis of ProbDD, clarifying trends in probability and subset size changes while simplifying the probability model. Complementing this analysis, we perform empirical experiments, including success rate analysis, ablation studies, and analysis on trade-offs and limitations, to better understand and demystify this state-of-the-art algorithm. Our success rate analysis shows how ProbDD addresses bottlenecks of ddmin by skipping inefficient queries that attempt to delete complements of subsets and previously tried subsets. The ablation study reveals that randomness in ProbDD has no significant impact on efficiency. Based on these findings, we propose CDD, a simplified version of ProbDD, reducing complexity in both theory and implementation. Besides, the performance of CDD validates our key findings. Comprehensive evaluations across 76 benchmarks in test input minimization and software debloating show that CDD can achieve the same performance as ProbDD despite its simplification. These insights provide valuable guidance for future research and applications of test input minimization algorithms.
• Abstract（参考訳）: L の要素リスト L と L のプロパティが与えられたとき、ddmin は L から無関係な要素を自動的に除去するように設計されたよく知られたテスト入力最小化アルゴリズムである。 近年、アドバンストなddminであるProbDDが提案され、最先端のパフォーマンスを実現している。 ベイズ最適化を用いて、ProbDD は L の各元が必須である可能性を予測し、どの元と何回削除されるべきなのかを統計的に決定する。 その結果, ProbDDの理論的確率モデルは複雑であり, 優れた性能を示す要因は明らかにされていない。 本稿では,確率モデルの簡易化とともに,確率およびサブセットサイズの変化の傾向を明らかにするため,ProbDDの詳細な理論解析を行う。 この分析を補完し、我々は、成功率分析、アブレーション研究、トレードオフと制限の分析を含む経験的な実験を行い、この最先端のアルゴリズムをよりよく理解し、デミスティフィケートする。 私たちの成功率分析は、サブセットや以前に試されたサブセットの補完を削除しようとする非効率なクエリをスキップすることで、ddminのボトルネックにProbDDがどのように対処しているかを示しています。 アブレーション研究では、ProbDDのランダム性は効率に有意な影響を与えないことが示されている。 これらの結果に基づき,ProbDDの簡易版であるCDDを提案し,理論と実装の複雑さを低減した。 また,CDDの性能評価も重要な結果である。 テスト入力の最小化とソフトウェアデブロ化における76ベンチマークの総合的な評価は、CDDがProbDDと同じ性能を達成できることを示している。 これらの知見は、将来のテスト入力最小化アルゴリズムの研究および応用のための貴重なガイダンスを提供する。

関連論文リスト

• $O(d/T)$ Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions [6.76974373198208]
  我々は、最小限の仮定の下で、人気のあるSDEベースのサンプルラーに対して高速収束理論を確立する。 解析の結果, スコア関数の$ell_2$-accurate推定値が与えられた場合, 対象分布と生成分布の総変動距離は$O(d/T)$で上限値となることがわかった。 これは、逆プロセスの各ステップでエラーがどのように伝播するかの詳細な特徴を提供する、新しい分析ツールセットによって達成される。
  論文  参考訳（メタデータ） (2024-09-27T17:59:10Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  細長い分布は、少数の少数派が限られた数のサンプルを含む実世界のデータにしばしば現れる。 近年の研究では、教師付きコントラスト学習がデータ不均衡を緩和する有望な可能性を示していることが明らかになっている。 本稿では,特徴空間の各クラスからのサンプルデータ分布を推定する確率論的コントラスト学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-11T13:44:49Z)
• Querying Easily Flip-flopped Samples for Deep Active Learning [63.62397322172216]
  アクティブラーニング(英: Active Learning)は、ラベルのないデータを戦略的に選択してクエリすることで、モデルの性能を向上させることを目的とした機械学習パラダイムである。 効果的な選択戦略の1つはモデルの予測の不確実性に基づくもので、サンプルがどの程度情報的であるかの尺度として解釈できる。 本稿では,予測されたラベルの不一致の最小確率として,最小不一致距離(LDM)を提案する。
  論文  参考訳（メタデータ） (2024-01-18T08:12:23Z)
• Optimal Decision Tree and Adaptive Submodular Ranking with Noisy Outcomes [9.321976218862542]
  プールベースのアクティブラーニングでは、学習者にラベルのないデータセットが与えられ、データポイントのラベルをクエリすることで未知の仮説を効率的に学習することを目的としている。 これは古典的最適決定木(ODT)問題として定式化できる: テストのセット、仮説のセット、各テストと仮説に対する結果が与えられた場合、我々の目標は、真の仮説を識別する低コストなテスト手順(すなわち決定木)を見つけることである。 本研究では,ODT問題の基本的変種について検討し,実験結果がうるさい場合,さらに一般的な場合であっても検討する。
  論文  参考訳（メタデータ） (2023-12-23T21:47:50Z)
• Local Discovery by Partitioning: Polynomial-Time Causal Discovery Around Exposure-Outcome Pairs [18.31538168213386]
  本稿では,因果推論タスクの分割(LDP)による局所的な発見を提案する。 LDPは制約ベースのプロシージャで、潜伏したコンバウンディングの下で露光出力ペアのVASを返す。 LDPの調整セットは、ベースライン発見アルゴリズムよりもバイアスが少なく、より正確な平均処理効果の推定値が得られる。
  論文  参考訳（メタデータ） (2023-10-25T14:53:10Z)
• High-dimensional Contextual Bandit Problem without Sparsity [8.782204980889077]
  本稿では,この問題に対処し,その性能を検証するための探索列コミット(EtC)アルゴリズムを提案する。 我々は、ETCアルゴリズムの最適レートを$T$で導出し、探索とエクスプロイトのバランスをとることで、このレートを実現できることを示す。 本稿では,最適バランスを適応的に求める適応探索定理 (AEtC) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-19T15:29:32Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。 本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
  論文  参考訳（メタデータ） (2023-06-13T01:18:16Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Minimax rate of consistency for linear models with missing values [0.0]
  多くの実世界のデータセットでは、複数のソースが集約され、本質的に欠落した情報(センサーの故障、調査における未回答の疑問...)が欠落する。 本稿では,広範に研究された線形モデルに焦点をあてるが,不足する値が存在する場合には,非常に難しい課題であることが判明した。 最終的には、多くの学習タスクを解決し、入力機能の数を指数関数的にすることで、現在の現実世界のデータセットでは予測が不可能になる。
  論文  参考訳（メタデータ） (2022-02-03T08:45:34Z)
• LSDAT: Low-Rank and Sparse Decomposition for Decision-based Adversarial Attack [74.5144793386864]
  LSDATは、入力サンプルのスパース成分と対向サンプルのスパース成分によって形成される低次元部分空間における摂動を加工する。 LSDは画像ピクセル領域で直接動作し、スパース性などの非$ell$制約が満たされることを保証します。
  論文  参考訳（メタデータ） (2021-03-19T13:10:47Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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