論文の概要: A Probably Approximately Correct Analysis of Group Testing Algorithms
- arxiv url: http://arxiv.org/abs/2412.00466v1
- Date: Sat, 30 Nov 2024 13:01:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-04 15:42:59.693519
- Title: A Probably Approximately Correct Analysis of Group Testing Algorithms
- Title（参考訳）: 群検定アルゴリズムのほぼ正しい分析法
- Authors: Sameera Bharadwaja H., Chandra R. Murthy,
- Abstract要約: 我々は,非適応型グループテストフレームワークを用いて,多数の項目から欠陥を識別する問題を考察する。
ほぼすべての欠陥項目と非欠陥項目を高い信頼性で識別するために必要なテスト数を分析する。
- 参考スコア（独自算出の注目度）: 9.476463361600826
- License:
- Abstract: We consider the problem of identifying the defectives from a population of items via a non-adaptive group testing framework with a random pooling-matrix design. We analyze the sufficient number of tests needed for approximate set identification, i.e., for identifying almost all the defective and non-defective items with high confidence. To this end, we view the group testing problem as a function learning problem and develop our analysis using the probably approximately correct (PAC) framework. Using this formulation, we derive sufficiency bounds on the number of tests for three popular binary group testing algorithms: column matching, combinatorial basis pursuit, and definite defectives. We compare the derived bounds with the existing ones in the literature for exact recovery theoretically and using simulations. Finally, we contrast the three group testing algorithms under consideration in terms of the sufficient testing rate surface and the sufficient number of tests contours across the range of the approximation and confidence levels.
- Abstract（参考訳）: ランダムなプール・行列設計による非適応型グループテストフレームワークを用いて,多数の項目から欠陥を識別する問題を考察する。
本研究では, ほぼすべての欠陥項目と非欠陥項目を高い信頼性で識別するために, 近似集合同定に必要なテスト数を分析する。
そこで本研究では,グループテスト問題を関数学習問題とみなし,ほぼ正しいPACフレームワークを用いて分析を行う。
この定式化を用いて、カラムマッチング、組合せ基底探索、定値欠陥探索という3つの一般的なバイナリグループテストアルゴリズムの試験数に基づく十分性境界を導出する。
得られた境界を文献中の既存の境界値と比較し,理論的およびシミュレーションを用いて再現する。
最後に,評価値と信頼度の範囲で十分なテスト率表面と十分な数の輪郭を考慮に入れた3つのグループテストアルゴリズムを比較した。
関連論文リスト
- Precise Error Rates for Computationally Efficient Testing [75.63895690909241]
本稿では,計算複雑性に着目した単純な対数-単純仮説テストの問題を再考する。
線形スペクトル統計に基づく既存の試験は、I型とII型の誤差率の間の最良のトレードオフ曲線を達成する。
論文 参考訳（メタデータ） (2023-11-01T04:41:16Z) - Concomitant Group Testing [49.50984893039441]
肯定的なテストが複数種類の項目の組み合わせを必要とするという考え方を捉えたグループテストの問題のバリエーションを紹介した。
目標は、可能な限り少数のテストを使用して、半欠陥セットをすべて確実に識別することである。
我々のアルゴリズムは、(i)決定性(ゼロエラー)かランダム化(小エラー)か、(ii)非適応性(非適応性)、完全適応性(完全適応性)、あるいは限定適応性(限定適応性)かによって区別される。
論文 参考訳（メタデータ） (2023-09-08T09:11:12Z) - Statistical and Computational Phase Transitions in Group Testing [73.55361918807883]
本研究の目的は、希少な疾患を患っているk人の集団を同定することである。
個々人のテストを割り当てるための2つの異なる単純なランダムな手順を考える。
論文 参考訳（メタデータ） (2022-06-15T16:38:50Z) - Group Testing with Non-identical Infection Probabilities [59.96266198512243]
そこで我々は,集合形成法を用いた適応型グループテストアルゴリズムを開発した。
提案アルゴリズムは, エントロピー下界に近い性能を示す。
論文 参考訳（メタデータ） (2021-08-27T17:53:25Z) - Efficient Detection Of Infected Individuals using Two Stage Testing [0.0]
集団検査は、集団を検査して感染した個体を検出する効果的な方法である。
複数の段階群試験アルゴリズムの効率を特徴付ける。
最適設定では、テストスキームは入力パラメータのエラーに対して堅牢である。
論文 参考訳（メタデータ） (2020-08-24T23:05:10Z) - Cross-validation Confidence Intervals for Test Error [83.67415139421448]
この研究は、クロスバリデーションのための中心極限定理と、学習アルゴリズムの弱い安定性条件下での分散の一貫した推定器を開発する。
結果は、一般的な1対1のクロスバリデーションの選択にとって、初めてのものだ。
論文 参考訳（メタデータ） (2020-07-24T17:40:06Z) - Noisy Adaptive Group Testing using Bayesian Sequential Experimental
Design [63.48989885374238]
病気の感染頻度が低い場合、Dorfman氏は80年前に、人のテストグループは個人でテストするよりも効率が良いことを示した。
本研究の目的は,ノイズの多い環境で動作可能な新しいグループテストアルゴリズムを提案することである。
論文 参考訳（メタデータ） (2020-04-26T23:41:33Z) - Genetic Algorithms for Redundancy in Interaction Testing [0.6396288020763143]
インタラクションテストには一連のテストの設計が含まれており、少数のコンポーネントが連携して動作する場合、障害を検出することが保証される。
これらのテストスイートを構築するための既存のアルゴリズムは通常、ほとんどのテストを生成する1つの"高速"アルゴリズムと、テストスイートを"完全"する別の"より遅い"アルゴリズムを含んでいる。
我々は、これらのアプローチを一般化する遺伝的アルゴリズムを用いて、選択したアルゴリズムの数を増やして冗長性も含み、それを「ステージ」と呼ぶ。
論文 参考訳（メタデータ） (2020-02-13T10:16:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。