論文の概要: Concomitant Group Testing

• arxiv url: http://arxiv.org/abs/2309.04221v1
• Date: Fri, 8 Sep 2023 09:11:12 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-11 13:53:39.034647
• Title: Concomitant Group Testing
• Title（参考訳）: 共同グループテスト
• Authors: Thach V. Bui, Jonathan Scarlett
• Abstract要約: 肯定的なテストが複数種類の項目の組み合わせを必要とするという考え方を捉えたグループテストの問題のバリエーションを紹介した。 目標は、可能な限り少数のテストを使用して、半欠陥セットをすべて確実に識別することである。 我々のアルゴリズムは、(i)決定性(ゼロエラー)かランダム化(小エラー)か、(ii)非適応性(非適応性)、完全適応性(完全適応性)、あるいは限定適応性(限定適応性)かによって区別される。
• 参考スコア（独自算出の注目度）: 49.50984893039441
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we introduce a variation of the group testing problem capturing the idea that a positive test requires a combination of multiple ``types'' of item. Specifically, we assume that there are multiple disjoint \emph{semi-defective sets}, and a test is positive if and only if it contains at least one item from each of these sets. The goal is to reliably identify all of the semi-defective sets using as few tests as possible, and we refer to this problem as \textit{Concomitant Group Testing} (ConcGT). We derive a variety of algorithms for this task, focusing primarily on the case that there are two semi-defective sets. Our algorithms are distinguished by (i) whether they are deterministic (zero-error) or randomized (small-error), and (ii) whether they are non-adaptive, fully adaptive, or have limited adaptivity (e.g., 2 or 3 stages). Both our deterministic adaptive algorithm and our randomized algorithms (non-adaptive or limited adaptivity) are order-optimal in broad scaling regimes of interest, and improve significantly over baseline results that are based on solving a more general problem as an intermediate step (e.g., hypergraph learning).
• Abstract（参考訳）: 本稿では,ポジティブテストには項目の複数の ``types'' の組み合わせが必要であるという概念を捉えた,グループテスト問題のバリエーションを紹介する。 具体的には、複数のdisjoint \emph{semi-defective sets} が存在し、テストが正であることと、それがこれらの集合から少なくとも1つのアイテムを含むことであると仮定する。 目標は、できるだけ少数のテストを使って、すべての半欠陥集合を確実に識別することであり、この問題を \textit{Concomitant Group Testing} (ConcGT) と呼ぶ。 このタスクの様々なアルゴリズムを導出し、主に2つの半完備集合が存在する場合に焦点を当てる。 我々のアルゴリズムは区別される 一 決定的(ゼロエラー)であるか、ランダム化(小エラー)であるか、及び (二)非適応的、完全適応的、又は限定適応性(二・三段階など)があるか。 我々の決定論的適応アルゴリズムとランダム化アルゴリズム(非適応的あるいは限定的適応性)は、幅広いスケールの関心事において順序最適であり、中間ステップ(ハイパーグラフ学習など)としてより一般的な問題の解法に基づくベースライン結果よりも大幅に改善される。

関連論文リスト

• CMSA algorithm for solving the prioritized pairwise test data generation problem in software product lines [1.1970409518725493]
  ソフトウェア製品ライン(SPL)では、多数の有効な機能の組み合わせが存在するため、家族のすべての製品をテストするのは難しい、あるいは不可能かもしれない。 本研究では,Construct, Merge, Solve & Adapt というハイブリッド・メピエリスト的アプローチに基づく新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2024-02-07T05:43:57Z)
• A Sequential Deep Learning Algorithm for Sampled Mixed-integer Optimisation Problems [0.3867363075280544]
  混合整数最適化問題に対する2つの効率的なアルゴリズムを導入,解析する。 両アルゴリズムが最適解に対して有限時間収束を示すことを示す。 3つの数値実験により,これらのアルゴリズムの有効性を定量的に確立する。
  論文  参考訳（メタデータ） (2023-01-25T17:10:52Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Group Testing with Non-identical Infection Probabilities [59.96266198512243]
  そこで我々は,集合形成法を用いた適応型グループテストアルゴリズムを開発した。 提案アルゴリズムは, エントロピー下界に近い性能を示す。
  論文  参考訳（メタデータ） (2021-08-27T17:53:25Z)
• Determinantal Beam Search [75.84501052642361]
  ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。 複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。 ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
  論文  参考訳（メタデータ） (2021-06-14T13:01:46Z)
• Genetic Algorithms for Redundancy in Interaction Testing [0.6396288020763143]
  インタラクションテストには一連のテストの設計が含まれており、少数のコンポーネントが連携して動作する場合、障害を検出することが保証される。 これらのテストスイートを構築するための既存のアルゴリズムは通常、ほとんどのテストを生成する1つの"高速"アルゴリズムと、テストスイートを"完全"する別の"より遅い"アルゴリズムを含んでいる。 我々は、これらのアプローチを一般化する遺伝的アルゴリズムを用いて、選択したアルゴリズムの数を増やして冗長性も含み、それを「ステージ」と呼ぶ。
  論文  参考訳（メタデータ） (2020-02-13T10:16:46Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

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

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