論文の概要: How Low Can We Go? Minimizing Interaction Samples for Configurable Systems
- arxiv url: http://arxiv.org/abs/2501.06788v1
- Date: Sun, 12 Jan 2025 12:02:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-14 14:26:21.115493
- Title: How Low Can We Go? Minimizing Interaction Samples for Configurable Systems
- Title（参考訳）: どれくらいの時間で行けるか? 構成可能なシステムのためのインタラクションサンプルの最小化
- Authors: Dominik Krupke, Ahmad Moradi, Michael Perk, Phillip Keldenich, Gabriel Gehrke, Sebastian Krieter, Thomas Thüm, Sándor P. Fekete,
- Abstract要約: 提案手法は, 必要サンプルサイズに対して, ほぼ最適解と証明可能な下限を結合する枠組みである。
我々のアルゴリズムであるSampLNSは,85%のケースにおいて,従来手法よりも小型のサンプルを確実に見つけることができる。
これにより、研究者や実践者によるサンプルの最小化という面倒な作業を避けることができる。
- 参考スコア（独自算出の注目度）: 2.569213261297365
- License:
- Abstract: Modern software systems are typically configurable, a fundamental prerequisite for wide applicability and reusability. This flexibility poses an extraordinary challenge for quality assurance, as the enormous number of possible configurations makes it impractical to test each of them separately. This is where t-wise interaction sampling can be used to systematically cover the configuration space and detect unknown feature interactions. Over the last two decades, numerous algorithms for computing small interaction samples have been studied, providing improvements for a range of heuristic results; nevertheless, it has remained unclear how much these results can still be improved. We present a significant breakthrough: a fundamental framework, based on the mathematical principle of duality, for combining near-optimal solutions with provable lower bounds on the required sample size. This implies that we no longer need to work on heuristics with marginal or no improvement, but can certify the solution quality by establishing a limit on the remaining gap; in many cases, we can even prove optimality of achieved solutions. This theoretical contribution also provides extensive practical improvements: Our algorithm SampLNS was tested on 47 small and medium-sized configurable systems from the existing literature. SampLNS can reliably find samples of smaller size than previous methods in 85% of the cases; moreover, we can achieve and prove optimality of solutions for 63% of all instances. This makes it possible to avoid cumbersome efforts of minimizing samples by researchers as well as practitioners, and substantially save testing resources for most configurable systems.
- Abstract（参考訳）: 現代のソフトウェアシステムは一般に構成可能であり、広い適用性と再利用性の基礎的な前提条件である。
この柔軟性は品質保証に驚くべき課題をもたらします。
ここでは、t-wiseの相互作用サンプリングを使用して、構成空間を体系的にカバーし、未知の機能相互作用を検出する。
過去20年間で、小さな相互作用のサンプルを計算するための多くのアルゴリズムが研究され、様々なヒューリスティックな結果が得られた。
必要標本サイズに対する証明可能な下界の近似解と近似最適解を組み合わせるための、双対性の数学的原理に基づく基本的な枠組みを提示する。
これは、もはや限界あるいは改善のないヒューリスティックスに取り組む必要はなく、残りのギャップに制限を課すことで、ソリューションの品質を証明できることを意味している。
我々のアルゴリズムSampLNSは、既存の文献から47個の小型・中型構成可能なシステムでテストされた。
SampLNSは85%のケースで従来の方法よりも小さなサンプルを確実に見つけることができ、さらに全インスタンスの63%で解の最適性を達成および証明することができる。
これにより、研究者や実践者によるサンプルの最小化や、ほとんどの構成可能なシステムのテストリソースの大幅な削減といった、面倒な作業を回避することができる。
関連論文リスト
- Neural Solver Selection for Combinatorial Optimization [23.449310200885893]
本稿では,特徴抽出,選択モデル,選択戦略を含むニューラルソルバのコーディネートを行うための,最初の汎用フレームワークを提案する。
提案するフレームワークは,インスタンスを効果的に分散し,結果として得られる複合解法により性能が大幅に向上することを示す。
論文 参考訳（メタデータ） (2024-10-13T02:05:41Z) - Faster Stochastic Variance Reduction Methods for Compositional MiniMax
Optimization [50.10952609321302]
合成ミニマックス最適化は、さまざまな機械学習領域において重要な課題である。
構成最小最適化の現在の方法は、最適以下の複雑さや、大きなバッチサイズに大きく依存することによって悩まされている。
本稿では,Nested STOchastic Recursive Momentum (NSTORM)と呼ばれる新しい手法を提案する。
論文 参考訳（メタデータ） (2023-08-18T14:57:21Z) - Maximize to Explore: One Objective Function Fusing Estimation, Planning,
and Exploration [87.53543137162488]
我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。
textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。
様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
論文 参考訳（メタデータ） (2023-05-29T17:25:26Z) - Best-Effort Adaptation [62.00856290846247]
本稿では, 試料再重み付け法に関する新しい理論的解析を行い, 試料再重み付け法を一様に保持する境界について述べる。
これらの境界が、我々が詳細に議論する学習アルゴリズムの設計を導く方法を示す。
本稿では,本アルゴリズムの有効性を実証する一連の実験結果について報告する。
論文 参考訳（メタデータ） (2023-05-10T00:09:07Z) - Single-Trajectory Distributionally Robust Reinforcement Learning [21.955807398493334]
本研究では,分散ロバストRL (DRRL) を提案する。
既存のDRRLアルゴリズムはモデルベースか、1つのサンプル軌道から学習できないかのいずれかである。
単一軌道を用いた分散ロバストQ-ラーニング(DRQ)と呼ばれる,完全モデルフリーなDRRLアルゴリズムを設計する。
論文 参考訳（メタデータ） (2023-01-27T14:08:09Z) - Learning Sampling Distributions for Model Predictive Control [36.82905770866734]
モデル予測制御(MPC)に対するサンプリングに基づくアプローチは、MPCに対する現代のアプローチの基盤となっている。
我々は、学習された分布を最大限に活用できるように、潜在空間における全ての操作を実行することを提案する。
具体的には、学習問題を双方向の最適化として捉え、バックプロパゲーションスルータイムでコントローラをトレーニングする方法を示す。
論文 参考訳（メタデータ） (2022-12-05T20:35:36Z) - Offline Model-Based Optimization via Normalized Maximum Likelihood
Estimation [101.22379613810881]
データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。
この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。
我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
論文 参考訳（メタデータ） (2021-02-16T06:04:27Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Bloom Origami Assays: Practical Group Testing [90.2899558237778]
グループテストは、いくつかの魅力的なソリューションでよく研究されている問題である。
近年の生物学的研究は、従来の方法と相容れない新型コロナウイルスの実践的な制約を課している。
我々は,Bloomフィルタと信条伝搬を組み合わせた新しい手法を開発し,n(100以上)の大きい値に拡張し,良好な経験的結果を得る。
論文 参考訳（メタデータ） (2020-07-21T19:31:41Z) - Fast and stable MAP-Elites in noisy domains using deep grids [1.827510863075184]
Deep-Grid MAP-ElitesはMAP-Elitesアルゴリズムの変種である。
この単純なアプローチは、適合性最適化の観点から競争性能を達成しつつ、動作記述子のノイズに対する耐性が著しく高いことを示す。
論文 参考訳（メタデータ） (2020-06-25T08:47:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。