グループテスト

統計学と組合せ数学において、グループ テストとは、特定のオブジェクトを識別するタスクを、個々の項目ではなく項目のグループに対するテストに分割する手順です。1943年にロバート ドルフマンによって初めて研究されたグループ テストは、幅広い実用的用途に適用できる比較的新しい応用数学の分野であり、現在も活発に研究されています。

グループ テストのよくある例としては、直列に接続された電球の列があり、そのうちの 1 つが壊れていることが分かっている場合が挙げられます。目的は、最小のテスト回数で壊れた電球を見つけることです (テストとは、電球の一部を電源に接続した状態です)。簡単な方法は、各電球を個別にテストすることです。ただし、電球の数が多い場合は、電球をグループにまとめる方がはるかに効率的です。たとえば、最初の半分の電球を一度に接続すると、壊れた電球がどの半分にあるかがわかり、1 回のテストで電球の半分を除外できます。

グループ テストを実行するためのスキームは、単純な場合も複雑な場合もあり、各段階で行われるテストも異なる場合があります。次の段階のテストが前の段階の結果に依存するスキームは適応型手順と呼ばれ、すべてのテストが事前にわかっているように設計されたスキームは非適応型手順と呼ばれます。非適応型手順に含まれるテストのスキームの構造は、プーリング デザインとして知られています。

グループテストは、統計学、生物学、コンピュータサイエンス、医学、工学、サイバーセキュリティなど、多くの分野で応用されています。これらのテストスキームに対する現代の関心は、ヒトゲノムプロジェクトによって再燃しました。^[1]

数学の多くの分野とは異なり、集団検査の起源は、ロバート・ドーフマンという一人の人物によって書かれた一つの報告書^[2]にまで遡ることができます。^[3]その動機は、第二次世界大戦中に、米国公衆衛生局と徴兵局が徴兵対象となった梅毒の男性全員を排除する大規模なプロジェクトに着手したときに生まれました。個人の梅毒検査では、その人から血液サンプルを採取し、そのサンプルを分析して梅毒の有無を判定します。当時、この検査は費用がかかり、兵士全員を個別に検査するのは非常に費用がかかり非効率的でした。^[3]

兵士がいると仮定すると、この検査方法は個別の検査につながります。大多数の人々が感染している場合は、この方法が合理的です。しかし、より可能性の高い、感染している男性がごく少数の場合、はるかに効率的な検査計画を実現できます。より効果的な検査計画の実現可能性は、次の特性にかかっています。兵士をグループにまとめ、各グループで血液サンプルを組み合わせることができます。その後、組み合わせたサンプルを検査して、グループ内の少なくとも 1 人の兵士が梅毒にかかっているかどうかを確認できます。これがグループ検査の中心的な考え方です。このグループ内の 1 人以上の兵士が梅毒にかかっている場合、検査は無駄になります (どの兵士が梅毒にかかっているかを見つけるために、より多くの検査を行う必要があります)。一方、プール内の誰も梅毒にかかっていない場合は、1 回の検査でそのグループのすべての兵士を排除できるため、多くの検査が節約されます。^[3]${\displaystyle n}$${\displaystyle n}$

グループが陽性反応を示す原因となったアイテムは、一般的に不良品と呼ばれます（壊れた電球、梅毒患者など）。多くの場合、アイテムの総数は と表され、不良品の数が既知であると仮定した場合は不良品の数を表します。^[3]${\displaystyle n}$${\displaystyle d}$

グループテスト問題には2つの独立した分類があります。すべてのグループテスト問題は適応型か非適応型か、確率型か組み合わせ型かのいずれかです。^[3]

確率モデルでは、不良品は何らかの確率分布に従うと想定され、各品目の不良品を特定するために必要なテストの予想回数を最小限に抑えることが目的です。一方、組み合わせグループテストでは、「最悪のシナリオ」で必要なテスト回数を最小限に抑えることが目的です。つまり、最小最大アルゴリズムを作成し、不良品の分布に関する知識は想定されていません。^[3]

もう 1 つの分類である適応性は、どの項目をテストにグループ化するかを選択する際にどのような情報を使用できるかに関するものです。一般に、テストする項目の選択は、上記の電球問題のように、以前のテストの結果に依存することがあります。テストを実行し、その結果 (および過去のすべての結果) を使用して次に実行するテストを決定するアルゴリズムは、適応型と呼ばれます。逆に、非適応型アルゴリズムでは、すべてのテストが事前に決定されます。この考え方は、テストが段階に分割され、前の段階のテストの結果のみを知って、次の段階のすべてのテストを事前に決定する必要がある多段階アルゴリズムに一般化できます。適応型アルゴリズムでは設計の自由度が大幅に高まりますが、適応型グループ テスト アルゴリズムは、不良品セットを識別するために必要なテストの数に関して、非適応型アルゴリズムよりも一定倍以上改善されないことが知られています。^{[4] [3]}これに加えて、非適応型の方法は、最初にすべての以前のテストの結果を分析することなく連続したテストを進めることができるため、テストプロセスを効果的に分散できるため、実際には役立つことがよくあります。

グループテストの問題を拡張する方法は数多くあります。最も重要なものの 1 つは、ノイズのあるグループテストと呼ばれ、元の問題に対する大きな前提、つまりテストにエラーがないという前提を扱っています。グループテストの問題は、グループテストの結果が誤っている可能性がある場合 (たとえば、テストに不良品が含まれていないのに陽性と出る場合)、ノイズがあると呼ばれます。ベルヌーイノイズモデルでは、この確率が定数 であると想定していますが、一般には、テストの実際の不良品数とテストされたアイテムの数によって異なります。^[5]たとえば、希釈の効果は、テストに存在する不良品の数が多いほど (またはテストされた数に対する不良品の割合が多いほど)、陽性の結果が出る可能性が高くなるとモデル化できます。^[6]ノイズのあるアルゴリズムでは、エラー (つまり、アイテムのラベル付けミス) が発生する確率が常にゼロではありません。 ${\displaystyle q}$

グループテストは、テストの結果が2つ以上あり得るシナリオを考慮することによって拡張できます。たとえば、テストの結果は、不良品がまったくない、不良品が1つある、または不良品の数が1より大きい未知の場合に対応して、 および になる可能性があります。より一般的には、何らかの に対してテストの結果セットを と見なすことができます。^[3]${\displaystyle 0,1}$${\displaystyle 2^{+}}$${\displaystyle {0,1,\ldots ,k^{+}}}$${\displaystyle k\in \mathbb {N} }$

もう 1 つの拡張は、どのセットをテストできるかという幾何学的制約を考慮することです。上記の電球問題は、この種の制約の例です。連続して出現する電球のみをテストできます。同様に、アイテムは円状、または一般にはネット状に配置でき、テストはグラフ上の利用可能なパスです。別の種類の幾何学的制約は、グループでテストできるアイテムの最大数に関するものです。 ^[a]または、グループ サイズが偶数でなければならないなどです。同様に、特定のアイテムが特定の数のテストにしか出現できないという制約を考慮すると便利です。^[3]

グループテストの基本式をリミックスする方法は無限にあります。以下の説明は、より珍しいバリエーションのいくつかについてのアイデアを提供します。「良い-平凡-悪い」モデルでは、各アイテムは「良い」、「平凡」、「悪い」のいずれかであり、テストの結果はグループ内の「最悪の」アイテムの種類です。しきい値グループテストでは、グループ内の不良アイテムの数があるしきい値または割合よりも大きい場合、テストの結果は陽性になります。^[7]阻害剤を使用したグループテストは、分子生物学に応用されているバリエーションです。ここでは、阻害剤と呼ばれる3番目のクラスのアイテムがあり、少なくとも1つの不良アイテムが含まれ、阻害剤が含まれない場合、テストの結果は陽性になります。^[8]

グループ検査の概念は、1943年にロバート・ドーフマンがAnnals of Mathematical Statisticsの Notes セクションに掲載した短いレポート^[2]で初めて導入されました。^{[3] [b]}ドーフマンのレポートは、グループ検査に関する初期のすべての研究と同様に、確率の問題に焦点を当てており、グループ検査という新しいアイデアを使用して、特定の兵士のプールから梅毒患者をすべて除去するために必要な検査の予想数を減らすことを目指していました。方法は単純でした。兵士を所定サイズのグループに分け、陽性グループに対して個別検査（サイズ 1 のグループで項目を検査）を使用して、どのグループが感染しているかを調べます。ドーフマンは、この戦略に最適なグループ サイズを、人口における欠陥の発生率に対して表にまとめました。^[2] スティーブン・サミュエルズ ^[10]は 、発生率の関数として最適なグループ サイズの閉形式の解を見つけました。

1943 年以降、グループ テストは数年間ほとんど変更されませんでした。その後、1957 年に Sterrett が Dorfman の手順を改良しました。^[11]この新しいプロセスは、再び陽性グループに対して個別のテストを実行することから始まりますが、不良品が特定されるとすぐに停止します。次に、グループ内の残りのアイテムは、どれも不良品ではない可能性が高いため、まとめてテストされます。

グループテストを初めて徹底的に扱ったのは、ソベルとグロールによる1959年の論文でした。^[12]彼らは、有病率が不明な場合の一般化に加えて、5つの新しい手順を説明し、最適な手順については、使用されるテストの予想数の明示的な式を提供しました。この論文では、グループテストと情報理論の関係も初めて示し、グループテストの問題のいくつかの一般化について議論し、理論の新しい応用をいくつか提供しました。

1960年にピーター・ウンガーが出した基本的な結果によると、有病率が の場合、期待される検査数に関して個別検査が最適なグループ検査手順となり、 の場合は最適ではないことが示されています。しかし、80年にも及ぶ研究努力にもかかわらず、一般人口サイズが の場合の最適な手順はまだわかっていないことに注意することが重要です。^[13]${\displaystyle p>p_{u}=(3-{\sqrt {5}})/2\approx 0.38}$${\displaystyle p<p_{u}}$${\displaystyle p<p_{u}}$${\displaystyle n>2}$

グループテストは、1962年にLiによって初めて組み合わせの文脈で研究され、^[14] Liの段階アルゴリズム${\displaystyle s}$^[3]が導入されました。Liは、Dorfmanの「2段階アルゴリズム」を任意の段階数に拡張し、項目間で不良品が確実に見つかるテストを 個以下で済むようにすることを提案しました。そのアイデアは、陰性テストのすべての項目を取り除き、残りの項目を最初のプールで行ったようにグループに分けるというものでした。これは、個別のテストを実行する前に 回行う必要がありました。 ${\displaystyle t={\frac {e}{\log _{2}(e)}}d\log _{2}(n)}$${\displaystyle d}$${\displaystyle n}$${\displaystyle s-1}$

組み合わせグループテスト全般については、1973年にカトナによってさらに詳しく研究されました。^[15]カトナは、非適応型グループテストの行列表現を導入し、非適応型の1欠陥ケースで不良品をテスト回数以下で見つける手順を作成し、それが最適であることも証明しました。 ${\displaystyle t=\lceil \log _{2}(n)\rceil }$

一般的に、適応型組み合わせグループテストの最適なアルゴリズムを見つけることは難しく、グループテストの計算複雑性は決定されていないものの、ある複雑性クラスでは難しいと疑われています。 ^[3]しかし、1972年に一般化バイナリ分割アルゴリズムが導入され、重要なブレークスルーが起こりました。^{[16]一般化バイナリ分割アルゴリズムは、陽性のテスト結果を示すグループに対して}バイナリ検索を実行することで機能し、情報下限回数以下のテストで単一の不良品を見つける単純なアルゴリズムです。

不良品が2個以上あるシナリオでも、一般化バイナリ分割アルゴリズムは、最大で情報下限を超えるテスト数（ は不良品の数）で、ほぼ最適な結果を生成します。^[16] 2013年にAllemannによってこれに大幅な改良が加えられ、および のときに、必要なテスト数が情報下限を超える数未満になりました。^[17]これは、バイナリ分割アルゴリズムのバイナリ検索を、重複するテストグループを持つ複雑なサブアルゴリズムセットに変更することで達成されました。このようにして、不良品の数または上限がわかっている適応型組み合わせグループテストの問題は基本的に解決されており、それ以上の改善の余地はほとんどありません。 ${\displaystyle d-1}$${\displaystyle d}$${\displaystyle 0.187d+0.5\log _{2}(d)+5.5}$${\displaystyle n/d\geq 38}$${\displaystyle d\geq 10}$

個別検定がいつminmaxになるかは未解決の問題です。Hu、Hwang、Wang は のとき個別検定が minmax になり、 のときは minmax にならないことを 1981 年に示しました。^[18]現在では、この境界は明確である、つまり、 のときのみ個別検定が minmax になると推測されています。^{[19] [c]} 2000 年には Riccio と Colbourn によっていくらか進展があり、 が大きいとき個別検定が minmax になることを示しました。^[20]${\displaystyle n\leq \lfloor (5d+1)/2\rfloor }$${\displaystyle n>3d}$${\displaystyle n\leq 3d}$${\displaystyle n}$${\displaystyle d\geq n/\log _{3/2}(3)\approx 0.369n}$

非適応型グループテストにおける重要な洞察の 1 つは、グループテスト手順が確実に成功するという要件 (「組み合わせ」問題) を排除し、各アイテムに誤ったラベルを付ける可能性が低いがゼロではないことを許容することで (「確率」問題)、大きな利益が得られるという点です。不良品の数がアイテムの総数に近づくにつれて、正確な組み合わせソリューションは確率ソリューションよりも大幅に多くのテストを必要とすることが知られています。確率ソリューションは、漸近的に小さなエラー確率しか許容しません。^{[4] [d]}

このような観点から、Chanら(2011)は、最大で 回のテストで最大 個の不良品を 個以下のエラー確率で検出できる確率的アルゴリズムCOMPを発表しました。^[5]これは下限値の定数倍以内です。^[4]${\displaystyle t=ed(1+\delta )\ln(n)}$${\displaystyle d}$${\displaystyle n}$${\displaystyle n^{-\delta }}$${\displaystyle t=O(d\log _{2}n)}$

Chan et al. (2011) もCOMPを単純なノイズモデルに一般化し、同様に明示的なパフォーマンス境界を生成しましたが、これもまた対応する下限値より一定値（テスト失敗の可能性に依存）だけ上回りました。^{[4] [5]}一般に、ベルヌーイノイズの場合に必要なテストの数は、ノイズがない場合よりも定数倍大きくなります。^[5]

アルドリッジ、バルダッシーニ、ジョンソン（2014）は、COMPアルゴリズムの拡張版を作成し、追加の後処理ステップを追加しました。^[21]彼らは、DDと呼ばれるこの新しいアルゴリズムのパフォーマンスがCOMPのパフォーマンスを大幅に上回り、DDが のシナリオで「本質的に最適」であることを、合理的な最適値を定義する仮想アルゴリズムと比較することで示しました。この仮想アルゴリズムのパフォーマンスは、 のときに改善の余地があることを示唆しており、改善の程度も示唆しています。^[21]${\displaystyle d^{2}\geq n}$${\displaystyle d^{2}<n}$

このセクションでは、グループ テストに関連する概念と用語を正式に定義します。

• 入力ベクトル は、長さ のバイナリ ベクトル(つまり)として定義され、の場合にのみ、j番目のアイテムは不良品と呼ばれます。さらに、不良品でないアイテムはすべて「良品」と呼ばれます。${\displaystyle \mathbf {x} =(x_{1},x_{2},\dots ,x_{n})}$${\displaystyle n}$${\displaystyle \mathbf {x} \in \{0,1\}^{n}}$${\displaystyle x_{j}=1}$

${\displaystyle \mathbf {x} }$は、（未知の）不良品集合を記述することを目的としています。 の重要な特性は、それが暗黙の入力であることです。つまり、一連の「テスト」を通じて推測できるもの以外に、 のエントリが何であるかについての直接的な知識はありません。これが次の定義につながります。 ${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {x} }$

• を入力ベクトルとします。集合 はテストと呼ばれます。テストにノイズがない場合、が存在するときにテストの結果は正となり、それ以外の場合は負となります。${\displaystyle \mathbf {x} }$${\displaystyle S\subseteq \{1,2,\dots ,n\}}$${\displaystyle j\in S}$${\displaystyle x_{j}=1}$

したがって、グループ テストの目標は、正確に、または高い確実性で決定できる 「短い」一連のテストを選択する方法を見つけることです。${\displaystyle \mathbf {x} }$

• グループテストアルゴリズムは、アイテムに誤ったラベルを付ける（つまり、欠陥のあるアイテムを欠陥のないアイテムとしてラベル付けする、またはその逆）とエラーを起こすと言われます。これは、グループテストの結果が間違っていることとは異なります。アルゴリズムがエラーを起こす確率がゼロの場合、そのアルゴリズムはゼロエラーと呼ばれます。 ^[e]
• ${\displaystyle t(d,n)}$任意のグループテストアルゴリズムによってエラーの確率がゼロの状態で常にアイテムの中から不良品を見つけるために必要なテストの最小数を示します。同じ数量ですが、アルゴリズムが非適応型であるという制限がある場合は、表記法が使用されます。${\displaystyle d}$${\displaystyle n}$${\displaystyle {\bar {t}}(d,n)}$

各 に対して を設定することにより、常に個別のテストに頼ることができるため、 でなければなりません。また、非適応型テスト手順は、結果に関係なくすべてのテストを実行するだけで適応型アルゴリズムとして記述できるため、 です。最後に、 のとき、欠陥があるかどうかを（少なくとも 1 つのテストによって）判定する必要があるアイテムが少なくとも 1 つあるため、 となります。 ${\displaystyle S_{j}=\{j\}}$${\displaystyle 1\leq j\leq n}$${\displaystyle {\bar {t}}(d,n)\leq n}$${\displaystyle t(d,n)\leq {\bar {t}}(d,n)}$${\displaystyle 0\neq d\neq n}$${\displaystyle 1\leq t(d,n)}$

まとめると（ と仮定した場合）、. [ ^f]${\displaystyle 0\neq d\neq n}$${\displaystyle 1\leq t(d,n)\leq {\bar {t}}(d,n)\leq n}$

必要なテスト数の下限は、 と表記されるサンプル空間の概念を使用して記述できます。これは、不良品を配置できる可能性のある集合です。サンプル空間とグループテストアルゴリズムを使用する任意のグループテスト問題では、 であることが示されます。ここで、 は、エラーの確率がゼロですべての不良品を識別するために必要なテストの最小数です。これは情報下限と呼ばれます。^[3]この境界は、各テストの後、が2つの互いに素なサブセットに分割され、各サブセットがテストの2つの可能な結果のいずれかに対応するという 事実から導き出されます。${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle t\geq \lceil \log _{2}{|{\mathcal {S}}|}\rceil }$${\displaystyle t}$${\displaystyle {\mathcal {S}}}$

しかし、情報の下限値自体は、小さな問題であっても通常は達成できません。^[3]これは、の分割が恣意的ではなく、何らかのテストによって実現可能でなければならないためです。 ${\displaystyle {\mathcal {S}}}$

実際、情報下限は、アルゴリズムがエラーを起こす確率がゼロではない場合に一般化できます。この形式では、定理はテストの数に基づいて成功確率の上限を与えます。テストを実行する任意のグループテストアルゴリズムについて、成功確率は を満たします。これは次のように強化できます。^{[5] [22]}${\displaystyle t}$${\displaystyle \mathbb {P} ({\textrm {success}})}$${\displaystyle \mathbb {P} ({\textrm {success}})\leq t/\log _{2}{n \choose d}}$${\displaystyle \mathbb {P} ({\textrm {success}})\leq {\frac {2^{t}}{n \choose d}}}$

非適応型グループテストのアルゴリズムは、2つの異なるフェーズで構成されています。まず、実行するテストの数と、各テストに含める項目を決定します。2番目のフェーズは、デコードステップと呼ばれることが多く、各グループテストの結果を分析して、どの項目が不良品である可能性が高いかを判断します。最初のフェーズは通常、次のようにマトリックスにエンコードされます。^[5]

• 項目の非適応型グループ検定手順が、いくつかの の検定で構成されているとします。この方式の検定行列はバイナリ行列です。ここで、 は の場合に限ります(それ以外の場合は 0 です)。${\displaystyle n}$${\displaystyle S_{1},S_{2},\dots ,S_{t}}$${\displaystyle t\in \mathbb {N} _{\geq 0}}$${\displaystyle t\times n}$${\displaystyle M}$${\displaystyle (M)_{ij}=1}$${\displaystyle j\in S_{i}}$

したがって、 の各列は項目を表し、各行はテストを表します。エントリ内のはテストに項目が含まれていることを示し、 はそうでないことを示します。 ${\displaystyle M}$${\displaystyle 1}$${\displaystyle (i,j){\textrm {-th}}}$${\displaystyle i{\textrm {-th}}}$${\displaystyle j{\textrm {-th}}}$${\displaystyle 0}$

未知の不良セットを記述するベクトル(長さ) と同様に、各テストの結果を記述する結果ベクトルを導入するのが一般的です。 ${\displaystyle \mathbf {x} }$${\displaystyle n}$

• を非適応型アルゴリズムによって実行されるテストの数とします。結果ベクトル は長さ のバイナリベクトル(つまり)であり、テストの結果が陽性 (つまり、少なくとも 1 つの不良品が含まれていた) の場合に限り となります。^[g]${\displaystyle t}$${\displaystyle \mathbf {y} =(y_{1},y_{2},\dots ,y_{t})}$${\displaystyle t}$${\displaystyle \mathbf {y} \in \{0,1\}^{t}}$${\displaystyle y_{i}=1}$${\displaystyle i{\textrm {-th}}}$

これらの定義により、非適応型問題は次のように再構成できます。まず、テスト行列 が選択され、その後ベクトルが返されます。次に、 を分析して の推定値を見つけることが問題となります。 ${\displaystyle M}$${\displaystyle \mathbf {y} }$${\displaystyle \mathbf {y} }$${\displaystyle \mathbf {x} }$

最も単純なノイズのあるケースでは、グループテストが誤った結果をもたらす一定の確率 があり、ランダムなバイナリベクトル を考えます。ここで、各エントリはである確率があり、そうでない場合は です。返されるベクトルは で、通常の への加算が行われます(これは要素ごとのXOR演算と同等です)。ノイズのあるアルゴリズムはを使って推定する必要があります(つまり、 を直接知る必要はありません)。^[5]${\displaystyle q}$${\displaystyle \mathbf {v} }$${\displaystyle q}$${\displaystyle 1}$${\displaystyle 0}$${\displaystyle {\hat {\mathbf {y} }}=\mathbf {y} +\mathbf {v} }$${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$${\displaystyle \mathbf {x} }$${\displaystyle {\hat {\mathbf {y} }}}$${\displaystyle \mathbf {y} }$

行列表現により、非適応型グループ検定におけるいくつかの境界を証明することが可能になる。このアプローチは、以下に定義されるような分離可能な行列が考慮される多くの決定論的設計のアプローチを反映している。^[3]${\displaystyle d}$

• バイナリ行列 は、その列のブール和 (論理和) がすべて異なる場合、- 分離可能と呼ばれます。さらに、 - 分離可能という表記は、 の列の最大 までのすべての和がすべて異なることを示します。(これは、すべての に対して - 分離可能であることとは異なります。)${\displaystyle M}$${\displaystyle d}$${\displaystyle d}$${\displaystyle {\bar {d}}}$ ${\displaystyle d}$${\displaystyle M}$${\displaystyle M}$${\displaystyle k}$${\displaystyle k\leq d}$

がテスト行列である場合、 - 分離可能 ( - 分離可能) という特性は、(最大で) 不良品を区別できることと同等です。ただし、これが簡単になることを保証するものではありません。分離性と呼ばれるより強力な特性がこれを保証します。 ${\displaystyle M}$${\displaystyle d}$${\displaystyle {\bar {d}}}$${\displaystyle d}$

• バイナリ マトリックスでは、任意の列のブール値の合計に他の列が含まれていない場合、そのマトリックスは- 分離と呼ばれます。(このコンテキストでは、B が 1 であるすべてのインデックスに対して、A も 1 である場合、列 A には列 B が含まれていると言われます。)${\displaystyle M}$${\displaystyle d}$${\displaystyle d}$

-分離テスト マトリックスの便利な特性は、不良品が最大 個ある場合、不良品でないすべてのアイテムが、結果が否定的なテストに少なくとも 1 回は出現するという点です。つまり、不良品を見つけるには、否定的なテストに出現するすべてのアイテムを削除するだけでよいという簡単な手順があります。 ${\displaystyle d}$${\displaystyle d}$

-分離行列と-分離行列の性質を利用すると、全アイテムの中から不良品を特定する問題に対して次のことが示せます。^[4]${\displaystyle d}$${\displaystyle d}$${\displaystyle d}$${\displaystyle n}$

1. 漸近的に小さい平均エラー確率に必要なテストの数は、に比例します。${\displaystyle O(d\log _{2}n)}$
2. 漸近的に小さい最大エラー確率に必要なテストの数は、に比例します。${\displaystyle O(d^{2}\log _{2}n)}$
3. エラーの確率をゼロにするために必要なテストの数はに比例します。${\displaystyle O\left({\frac {d^{2}\log _{2}n}{\log _{2}d}}\right)}$

一般化バイナリ分割アルゴリズムは、次のようにアイテム間で不良品を100個以下見つける本質的に最適な適応型グループテストアルゴリズムです。 ^{[3] [16]}${\displaystyle d}$${\displaystyle n}$

1. の場合、項目を個別にテストします。それ以外の場合は、およびを設定します。${\displaystyle n\leq 2d-2}$${\displaystyle n}$${\displaystyle l=n-d+1}$${\displaystyle \alpha =\lfloor \log _{2}{l/d}\rfloor }$
2. サイズ のグループをテストします。結果が負の場合、グループ内のすべてのアイテムが不良品ではないと宣言され、 を設定して手順 1 に進みます。それ以外の場合は、バイナリ検索を使用して、不良品 1 個と、と呼ばれる不特定の数の不良品ではないアイテムを特定し、と を設定します。手順 1 に進みます。${\displaystyle 2^{\alpha }}$${\displaystyle n:=n-2^{\alpha }}$${\displaystyle x}$${\displaystyle n:=n-1-x}$${\displaystyle d:=d-1}$

一般化されたバイナリ分割アルゴリズムでは、のテスト のみが必要です。^[3]${\displaystyle T}$${\displaystyle T={\begin{cases}n&n\leq 2d-2\\(\alpha +2)d+p-1&n\geq 2d-1\end{cases}}}$

大きい場合、 であることが示され、^[3]これは、 Liのステージアルゴリズムに必要なテストに匹敵します。実際、一般化されたバイナリ分割アルゴリズムは、次の意味で最適に近いです。 であることが示される場合、 は情報下限です。^{[3] [16]}${\displaystyle n/d}$${\displaystyle T\rightarrow d\log _{2}(n/d)}$${\displaystyle t={\frac {e}{\log _{2}e}}d\log _{2}\left({\frac {n}{d}}\right)}$${\displaystyle s}$${\displaystyle d\geq 2}$${\displaystyle T-B_{I}(d,n)\leq (d-1)}$${\displaystyle B_{I}(d,n)=\left\lceil \log _{2}\sum _{i=0}^{d}{n \choose i}\right\rceil }$

非適応型グループテストアルゴリズムは、不良品の数、または少なくともその上限がわかっていると仮定する傾向があります。^[5]この量はこのセクションで示されています。上限がわからない場合は、クエリの複雑さが低い非適応型アルゴリズムを使用してを推定することができます。^[23]${\displaystyle d}$${\displaystyle d}$

組み合わせ直交マッチング追跡 (COMP) は、このセクションで説明するより複雑なアルゴリズムの基礎となる、単純な非適応型グループ テスト アルゴリズムです。

まず、テスト マトリックスの各エントリは、確率が の場合にiidが選択され、そうでない場合は が選択されます。 ${\displaystyle 1}$${\displaystyle 1/d}$${\displaystyle 0}$

デコード手順は列方向 (つまりアイテムごと) に進みます。アイテムが出現するすべてのテストで陽性と判定された場合、そのアイテムは不良品と宣言されます。それ以外の場合は、そのアイテムは不良品ではないとみなされます。または、同様に、結果が陰性となるテストにアイテムが出現した場合、そのアイテムは不良品ではないと宣言されます。それ以外の場合は、そのアイテムは不良品であるとみなされます。このアルゴリズムの重要な特性は、偽陰性が決して生成されないことです。ただし、(不良品でないアイテムjに対応する)のj列目に 1 が含まれるすべての場所が、不良品に対応する他の列の 1 によって「隠される」場合は、偽陽性が発生します。 ${\displaystyle M}$

COMPアルゴリズムでは、エラー確率が以下になるテストが個以上必要ありません。^[5]これは、上記の平均エラー確率の下限値の定数倍以内です。 ${\displaystyle ed(1+\delta )\ln(n)}$${\displaystyle n^{-\delta }}$

ノイズの多いケースでは、元のCOMPアルゴリズムの要件である、正の項目に対応する の任意の列の1の位置の集合が、結果ベクトルの1の位置の集合に完全に含まれているという要件を緩和します。代わりに、一定数の「不一致」を許容します。この不一致の数は、各列の1の数とノイズパラメータ の両方に依存します。このノイズの多いCOMPアルゴリズムでは、最大 のエラー確率を達成するために、 テスト数だけが必要です。^[5]${\displaystyle M}$${\displaystyle q}$${\displaystyle 4.36({\sqrt {\delta }}+{\sqrt {1+\delta }})^{2}(1-2q)^{-2}d\log _{2}{n}}$${\displaystyle n^{-\delta }}$

明確な欠陥検出法（DD）はCOMPアルゴリズムの拡張版であり、誤検出を排除しようとするものである。DDの性能保証はCOMPの性能保証を大幅に上回ることが実証されている。^[21]

デコード手順では、COMP アルゴリズムの便利な特性、つまり、COMP が不良品ではないと宣言したすべてのアイテムは確かに不良品ではない (つまり、偽陰性がない) という特性を利用します。これは次のように進行します。

1. まず、COMP アルゴリズムが実行され、検出された不良品以外の品目が削除されます。残りの品目はすべて「不良品の可能性がある」品目になります。
2. 次に、アルゴリズムはすべての陽性テストを調べます。テストでアイテムが唯一の「不良品の可能性がある」と表示された場合は、そのアイテムは不良品であるはずなので、アルゴリズムはそれを不良品であると宣言します。
3. その他のすべてのアイテムは不良品ではないと想定されます。この最後のステップの正当性は、不良品の数がアイテムの総数よりもはるかに少ないという想定に基づいています。

ステップ 1 と 2 で間違いが起こることは決してないので、アルゴリズムが間違いを犯す可能性があるのは、欠陥のあるアイテムを欠陥がないと宣言した場合のみであることに注意してください。したがって、DD アルゴリズムは偽陰性しか作成できません。

SCOMP (Sequential COMP) は、DD が最後のステップまでミスをしないという事実を利用したアルゴリズムで、最後のステップでは残りのアイテムは不良品ではないと想定されます。宣言された不良品のセットを とします。陽性テストは、のアイテムが少なくとも 1 つ含まれている場合、によって説明されると呼ばれます。SCOMP に関する重要な観察は、DD によって検出された不良品のセットがすべての陽性テストを説明できるとは限らず、説明できないすべてのテストには隠れた不良品が含まれている必要があるということです。 ${\displaystyle K}$${\displaystyle K}$${\displaystyle K}$

アルゴリズムは次のように進行します。

1. DD アルゴリズムのステップ 1 と 2 を実行して、不良品セットの初期推定値を取得します。${\displaystyle K}$
2. がすべての陽性テストを説明する場合、アルゴリズムを終了します。は不良品セットの最終推定値です。${\displaystyle K}$${\displaystyle K}$
3. 説明されていないテストがある場合は、説明されていないテストの最大数に現れる「不良の可能性がある」ものを探し、それを不良であると宣言します（つまり、セットに追加します）。手順 2 に進みます。${\displaystyle K}$

シミュレーションでは、SCOMPは最適に近いパフォーマンスを発揮することが示されています。^[21]

正の数まで正確に識別することが保証されている決定論的アルゴリズムは、多項式プール（PP）です。^[24]このアルゴリズムは、プーリング行列 を構築するためのもので、 の観測値をデコードするために直接使用できます。COMPと同様に、サンプルは という関係に従ってデコードされます。 ここで、 は要素ごとの乗算を表し、は の 番目の列です。デコード手順は難しくないため、PPは の生成に特化しています。 ${\displaystyle d}$${\displaystyle M}$${\displaystyle y}$${\displaystyle x_{i}=1~~{\text{ if }}~~M(:,i)~.*~y=M(:,i)}$${\displaystyle .*}$${\displaystyle M(:,i)}$${\displaystyle i}$${\displaystyle M}$${\displaystyle M}$

グループ/プールは、各プールに含まれるサンプルのインデックスを指定する多項式関係を使用して生成されます。一連の入力パラメータによってアルゴリズムが決まります。素数と整数の場合、任意の素数累乗は で定義されます。次元パラメータの場合、サンプルの総数は で、プールあたりのサンプル数は です。さらに、 有限順序体はで表されます (つまり、での加算と乗算がに留まるようにする特別な算術演算によって定義された整数)。この方法では、各サンプルをグリッドに配置し、座標 で表します。座標は、整数 を使用した多項式関係に従って計算されます 。${\displaystyle \ell }$${\displaystyle p>1}$${\displaystyle n\geq 1}$${\displaystyle q=p^{n}}$${\displaystyle c\geq 2}$${\displaystyle n=q^{c}}$${\displaystyle q^{c-1}}$ ${\displaystyle q}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle \{0,1,2,\ldots ,q-1\}}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle x=(u,v)}$${\displaystyle 1\leq l\leq c-1}$${\displaystyle 0\leq u_{i_{l}}\leq q-1}$

${\displaystyle v~=~a^{c-1}~u_{i_{c-1}}+\cdots +a~u_{i_{1}}+b,\quad a,b,u_{i_{l}}\in \mathbb {F} _{q}.}$

値をループする組み合わせは、整数 のシーケンスの要素を持つセット、つまり で表されます。ここで です 。一般性を失うことなく、この組み合わせは、 が ごとに を循環し、 がごとに を循環し、 が 1 回だけ循環するまで続きます 。サンプルインデックス、つまり対応するプールを計算する式は、固定のおよびに対して次のように与えられます。 ${\displaystyle u_{i_{l}}}$${\displaystyle q^{c-1}}$${\displaystyle d-1}$${\displaystyle u_{i_{1}}\times \cdots \times u_{i_{c-1}}=\{(i_{1},\ldots ,i_{c-1})\}}$${\displaystyle 0\leq i_{l}\leq q-1}$${\displaystyle i_{d-1}}$${\displaystyle q}$${\displaystyle i_{d-2}}$${\displaystyle q^{2}}$${\displaystyle i_{1}}$${\displaystyle a}$${\displaystyle b}$

${\displaystyle {\begin{aligned}u_{i}&=\sum _{l=1}^{c-1}~q^{d-1-l}~i_{l}\\v_{u_{i}}&=\sum _{l=1}^{c-1}~a^{l}~i_{l}+b\quad ({\text{computed in }}\mathbb {F} _{q})\\x_{qu_{i}+v_{u_{i}}}&=(u_{i},v_{u_{i}})\end{aligned}}}$

が素数べき乗である場合、 の計算は、有限体用の公開ソフトウェア ライブラリを使用して実装できます。が素数である場合、 の計算はモジュラス演算に簡略化されます。つまり、 です。 の場合に 1 つのプールを生成する方法の例を以下の表に示します。対応するサンプルの選択を上の図に示します。 ${\displaystyle \mathbb {F} _{q}}$${\displaystyle q}$${\displaystyle q}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle v_{u_{i}}=(\sum _{l=1}^{c-1}a^{l}i_{l}+b)~{\text{mod}}~q}$${\displaystyle \ell }$${\displaystyle a=1,b=0,c=2}$

この方法では、サンプル間で陽性を正確に識別するためにテストを使用します。このため、PPはサンプル数が大きい場合に特に効果的です。これは、サンプル数がこのパラメータに対して指数関数的に増加するのに対し、テスト数は線形にしか増加しないためです。ただし、PPはサンプル数が小さい場合にも効果的です。^[24]${\displaystyle q(c-1)(d+1)}$${\displaystyle d}$${\displaystyle n=q^{c}}$${\displaystyle c}$

グループテスト理論の一般性は、クローンのスクリーニング、電気的なショートの位置の特定、^[3]高速コンピュータネットワーク、^[25]医療検査、数量検索、統計、^[18]機械学習、DNA配列決定、^[26]暗号化、^{[27] [28]}データフォレンジック^[29]など、さまざまなアプリケーションに応用できます。このセクションでは、これらのアプリケーションのいくつかを簡単に紹介します。

マルチアクセスチャネルは、一度に多くのユーザーを接続する通信チャネルです。すべてのユーザーはチャネルで受信および送信できますが、複数のユーザーが同時に送信した場合、信号が衝突し、理解できないノイズになります。マルチアクセスチャネルは、ワイヤレスコンピュータネットワークや電話ネットワークなど、さまざまな実際のアプリケーションで重要です。^[30]

マルチアクセス チャネルの大きな問題は、メッセージが衝突しないように、ユーザーに送信時間を割り当てる方法です。簡単な方法は、各ユーザーに独自の送信用タイム スロットを与えることです。これにはスロットが必要です。(これは、時分割多重化(TDM)と呼ばれます)。ただし、これは非常に非効率的です。メッセージを持っていない可能性のあるユーザーに送信スロットが割り当てられ、通常、特定の時点で送信したいユーザーは少数であると想定されるためです。そうでなければ、マルチアクセス チャネルはそもそも実用的ではありません。 ${\displaystyle n}$

グループテストの文脈では、この問題は通常、次のように時間を「エポック」に分割することによって対処されます。^[3]エポックの開始時にメッセージを持っている場合、そのユーザーは「アクティブ」と呼ばれます。(エポック中にメッセージが生成された場合、ユーザーは次のエポックの開始時にのみアクティブになります。) エポックは、すべてのアクティブユーザーがメッセージを正常に送信したときに終了します。問題は、特定のエポック内のすべてのアクティブユーザーを見つけて、それらのユーザーが送信する時間をスケジュールすることです(まだ成功していない場合)。ここで、一連のユーザーに対するテストは、送信を試行しているユーザーに対応します。テストの結果は、送信を試みたユーザーの数、およびであり、それぞれ、アクティブユーザーがいない、アクティブユーザーが1人だけ(メッセージ成功)、または複数のアクティブユーザー(メッセージ衝突)に対応します。したがって、結果 を持つ適応型グループテストアルゴリズムを使用すると、どのユーザーがエポックで送信を希望しているかを判断できます。すると、非アクティブなユーザーに時間を無駄に割り当てることなく、まだ送信に成功していないユーザーに送信スロットを割り当てることができるようになります。 ${\displaystyle 0,1,}$${\displaystyle 2^{+}}$${\displaystyle \{0,1,2^{+}\}}$

機械学習は、DNA分類、詐欺検出、ターゲット広告など、多くのソフトウェアアプリケーションを持つコンピュータサイエンスの分野です。機械学習の主なサブフィールドの1つは、「例による学習」問題であり、特定のポイントの数で値が与えられた場合に、未知の関数を近似するタスクです。^[3]このセクションで概説されているように、この機能学習問題は、グループテストアプローチで取り組むことができます。

問題の簡単なバージョンでは、未知の関数があり、ここでであり（論理演算を使用：加算は論理OR、乗算は論理AND）。ここで は「スパース」であり、つまりその要素のほとんどは です。目的は、点評価を使用しての近似値を構築することです。ここで は可能な限り小さくなります。^[4]（正確に回復することはゼロエラーアルゴリズムに対応しますが、 はエラーの確率がゼロではないアルゴリズムによって近似されます。） ${\displaystyle f:\{0,1\}^{N}\to \{0,1\}}$${\displaystyle f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}}$${\displaystyle {\textbf {a}}\in \{0,1\}^{N}}$${\displaystyle {\textbf {a}}}$${\displaystyle d}$${\displaystyle d\ll N}$${\displaystyle 1}$${\displaystyle f}$${\displaystyle t}$${\displaystyle t}$${\displaystyle f}$${\displaystyle f}$

この問題では、回復はを見つけることと同等です。さらに、は、というインデックス が存在する場合に限ります。したがって、この問題は不良品と合計アイテムを含むグループテスト問題に類似しています。 のエントリはアイテムであり、 の場合に不良品であり、はテストを指定し、 の場合にのみテストが陽性となります。^[4]${\displaystyle f}$${\displaystyle {\textbf {a}}}$${\displaystyle f({\textbf {p}})=1}$${\displaystyle n}$${\displaystyle {\textbf {a}}_{n}={\textbf {p}}_{n}=1}$${\displaystyle d}$${\displaystyle n}$${\displaystyle {\textbf {a}}}$${\displaystyle 1}$${\displaystyle {\textbf {p}}}$${\displaystyle f({\textbf {p}})=1}$

現実には、 （ここでも ）のようなより複雑な関数に関心が寄せられることが多い。グループテストと密接に関連する圧縮センシングは、この問題を解決するために使用できる。^[4]${\displaystyle f:\mathbb {C} ^{N}\to \mathbb {C} }$${\displaystyle f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}}$

圧縮センシングでは、いくつかの測定値を取得して信号 を再構築することが目標です。これらの測定値は、選択されたベクトルとのドット積を取得するものとしてモデル化されます。 ^[h]目的は少数の測定値を使用することですが、これは通常、信号について何かを仮定しない限り不可能です。そのような仮定の 1 つ (一般的な仮定^{[33] [34]} ) は、 のエントリのうち少数のみが有意である、つまりそれらの値が大きいというものです。測定値はのドット積であるため、次の式が成り立ちます。ここで、 は選択された測定値のセットを表す行列であり、は測定結果のセットです。この構成は、圧縮センシングが一種の「連続的な」グループ テストであることを示しています。 ${\displaystyle {\textbf {v}}\in \mathbb {C} ^{N}}$${\displaystyle {\textbf {v}}}$${\displaystyle {\textbf {v}}}$${\displaystyle {\textbf {v}}}$${\displaystyle M{\textbf {v}}={\textbf {q}}}$${\displaystyle M}$${\displaystyle t\times N}$${\displaystyle \mathbf {q} }$

圧縮センシングの主な難しさは、どのエントリが重要であるかを識別することです。^[33]それが完了すると、エントリの実際の値を推定するさまざまな方法があります。^[35]この識別タスクには、グループテストを簡単に適用することで対応できます。ここで、グループテストは複素数、つまりテストされたエントリの合計を生成します。テストの結果が陽性と呼ばれるのは、大きな値を持つ複素数を生成する場合です。これは、重要なエントリがまばらであるという仮定のもとで、テストに少なくとも 1 つの重要なエントリが含まれていることを示します。

このタイプの組み合わせ探索アルゴリズムには、測定を必要とする明示的な決定論的構成があります。^[36]しかし、グループテストと同様に、これらは最適ではなく、ランダム構成（COMPなど）はしばしば線形以下で回復することがあります。^[35]${\displaystyle d2^{(\log _{2}\log _{2}N)^{O(1)}}}$${\displaystyle f}$${\displaystyle N}$

2020年のCOVID-19の流行のようなパンデミックの際には、非適応型グループテスト設計を使用してウイルス検出アッセイが実行されることがあります。^{[37] [38] [39]} 一例として、Origami Assaysプロジェクトが、実験室標準の96ウェルプレートで実行するためのオープンソースのグループテスト設計をリリースしました。^[40]

実験室環境でのグループテストの課題の1つは、混合物の構築に時間がかかり、手作業で正確に行うことが難しいことです。折り紙アッセイは、技術者がテストウェル全体に患者のサンプルをどのように割り当てるかをガイドする紙のテンプレートを提供することで、この構築の問題を回避しました。^[41]

最大規模のグループテスト設計 (XL3) を使用すると、94 個のアッセイ ウェルで 1120 個の患者サンプルをテストすることが可能です。真陽性率が十分に低ければ、追加のテストは必要ありませんでした。

データフォレンジックは、犯罪のデジタル証拠を収集する方法を見つけることに特化した分野です。このような犯罪では通常、敵対者が被害者のデータ、文書、データベースを改ざんします。例としては、納税記録の改ざん、ウイルスの存在の隠蔽、個人情報窃盗犯による個人データの改ざんなどが挙げられます。^[29]

データフォレンジックでよく使われるツールは、一方向暗号ハッシュです。これは、データを受け取り、逆引きが困難な手順を経て、ハッシュと呼ばれる一意の番号を生成する関数です。^[i]ハッシュはデータよりもはるかに短いことが多いため、情報の完全なコピーを無駄に保存することなく、データが変更されたかどうかを確認できます。現在のデータのハッシュを過去のハッシュと比較することで、変更があったかどうかを判断できます。この方法の残念な点は、データが変更されたかどうかは簡単にわかりますが、どのように変更されたかを判断する方法がないことです。つまり、データのどの部分が変更されたかを復元することは不可能です。^[29]

この制限を回避する 1 つの方法は、より多くのハッシュ (データ構造のサブセット) を保存して、攻撃が発生した場所を絞り込むことです。ただし、単純なアプローチで攻撃の正確な場所を見つけるには、構造内のすべてのデータに対してハッシュを保存する必要があり、ハッシュの目的がそもそも失われます (データの通常のコピーを保存することもできます)。グループ テストを使用すると、保存する必要があるハッシュの数を大幅に削減できます。テストは、保存されたハッシュと現在のハッシュの比較になり、不一致がある場合は肯定的になります。これは、現在のハッシュを生成したグループに少なくとも 1 つの編集されたデータ (このモデルでは欠陥と見なされます) が含まれていることを示します。^[29]

実際、必要なハッシュの数は非常に少ないため、ハッシュとそれが参照するテストマトリックスは、データ自体の組織構造内に保存することもできます。これは、メモリに関する限り、テストを「無料で」実行できることを意味します。（これは、ハッシュ関数を秘密裏に決定するために使用されるマスターキー/パスワードを除いて当てはまります。）^[29]