Skupinové testování - Group testing

Ilustrace problému žárovky, kde se hledá zlomená žárovka mezi šesti žárovkami. Zde jsou první tři připojeny k napájecímu zdroji a rozsvítí se (A). To znamená, že rozbitá žárovka musí být jednou z posledních tří (B). Pokud se místo toho žárovky nerozsvítily, dalo by se být jisté, že rozbitá žárovka byla mezi prvními třemi. Pokračováním v tomto postupu můžete rozbité žárovky lokalizovat maximálně ve třech testech, ve srovnání s maximálně šesti testy, pokud jsou žárovky kontrolovány jednotlivě.

v statistika a kombinatorická matematika, skupinové testování je jakýkoli postup, který rozdělí úkol identifikovat určité objekty do testů na skupinách položek, spíše než na jednotlivých. Nejprve studoval Robert Dorfman v roce 1943 je skupinové testování relativně novým oborem aplikované matematiky, který lze aplikovat na širokou škálu praktických aplikací a je dnes aktivní oblastí výzkumu.

Známý příklad skupinového testování zahrnuje řetězec žárovek zapojených do série, kde je známo, že právě jedna z žárovek je rozbitá. Cílem je najít rozbitou žárovku pomocí nejmenšího počtu testů (přičemž zkouškou je test, kdy jsou některé z těchto žárovek připojeny k napájecímu zdroji). Jednoduchým přístupem je otestovat každou žárovku zvlášť. Pokud však existuje velké množství žárovek, bylo by mnohem efektivnější sloučit žárovky do skupin. Například připojením první poloviny žárovek najednou lze určit, ve které polovině je poškozená žárovka, což vylučuje polovinu žárovek pouze v jednom testu.

Schémata pro provádění skupinového testování mohou být jednoduchá nebo složitá a testy v každé fázi se mohou lišit. Schémata, ve kterých testy pro další fázi závisí na výsledcích předchozích fází, se nazývají adaptivní postupy, zatímco jsou volána schémata navržená tak, aby byly předem známy všechny testy neadaptivní postupy. Struktura schématu testů zapojených do neadaptivního postupu je známá jako a sdružování design.

Skupinové testování má mnoho aplikací, včetně statistik, biologie, počítačové vědy, medicíny, strojírenství a kybernetické bezpečnosti. Moderní zájem o tyto testovací schémata znovu vzbudil Projekt lidského genomu.^[1]

Základní popis a pojmy

Na rozdíl od mnoha oblastí matematiky lze počátky skupinového testování vysledovat až k jediné zprávě^[2] napsal jedna osoba: Robert Dorfman.^[3] Motivace vznikla během druhé světové války, kdy Služba veřejného zdraví USA a Selektivní služba pustil se do velkého projektu, aby všechny vyřadil syfilitický muži vyvolali indukci. Testování jedince na syfilis zahrnuje odebrání vzorku krve z nich a následnou analýzu vzorku, aby se určila přítomnost nebo nepřítomnost syfilisu. V té době bylo provedení tohoto testu nákladné a testování každého vojáka jednotlivě by bylo velmi nákladné a neefektivní.^[3]

Předpokládejme, že existují ${ displaystyle n}$ vojáků, tato metoda testování vede k ${ displaystyle n}$ samostatné testy. Pokud je infikována velká část lidí, byla by tato metoda rozumná. V mnohem pravděpodobnějším případě, že je infikována jen velmi malá část mužů, lze dosáhnout mnohem efektivnějšího schématu testování. Realizace efektivnějšího testovacího schématu závisí na následující vlastnosti: vojáci mohou být sdruženi do skupin a v každé skupině mohou být vzorky krve kombinovány dohromady. Kombinovaný vzorek lze poté otestovat a zkontrolovat, zda alespoň jeden voják ve skupině má syfilis. Toto je ústřední myšlenka skupinového testování. Pokud má jeden nebo více vojáků v této skupině syfilis, je test zbytečný (je třeba provést více testů, aby se zjistilo, o jaké vojáky se jednalo). Na druhou stranu, pokud nikdo v bazénu nemá syfilis, uloží se mnoho testů, protože každý voják v této skupině může být vyloučen pouze jedním testem.^[3]

Položky, které způsobí, že skupina bude mít pozitivní test, se obecně nazývají vadné položky (to jsou rozbité žárovky, syfilitičtí muži atd.). Celkový počet položek je často označen jako ${ displaystyle n}$ a ${ displaystyle d}$ představuje počet defektů, pokud se předpokládá, že jsou známy.^[3]

Klasifikace problémů skupinového testování

Existují dvě nezávislé klasifikace problémů se skupinovým testováním; každý problém se skupinovým testováním je buď adaptivní nebo neadaptivní a je pravděpodobnostní nebo kombinatorický.^[3]

V pravděpodobnostních modelech se předpokládá, že vadné položky některé následují rozdělení pravděpodobnosti a cílem je minimalizovat očekávaný počet testů potřebných k identifikaci vadnosti každé položky. Na druhou stranu je u kombinatorického skupinového testování cílem minimalizovat počet testů potřebných v „nejhorším scénáři“ - tj. Vytvořit algoritmus minmax - a nepředpokládá se žádná znalost rozdělení závad.^[3]

Druhá klasifikace, adaptivita, se týká toho, jaké informace lze použít při výběru položek, které se mají seskupit do testu. Obecně platí, že výběr položek, které se mají testovat, může záviset na výsledcích předchozích testů, jako ve výše uvedeném problému žárovky. An algoritmus který pokračuje provedením testu a poté pomocí výsledku (a všech minulých výsledků) k rozhodnutí, který další test provést, se nazývá adaptivní. Naopak v neadaptivních algoritmech jsou všechny testy rozhodnuty předem. Tuto myšlenku lze zobecnit na vícestupňové algoritmy, kde jsou testy rozděleny do fází a o každém testu v další fázi je třeba rozhodnout předem, pouze s vědomím výsledků testů v předchozích fázích. Ačkoli adaptivní algoritmy nabízejí mnohem větší svobodu v Je známo, že algoritmy adaptivního testování skupin se oproti neadaptivním nezlepšují o více než konstantní faktor v počtu testů potřebných k identifikaci sady vadných položek.^[4][3] Kromě toho jsou v praxi často neadaptivní metody užitečné, protože je možné pokračovat v následných testech, aniž by byly nejprve analyzovány výsledky všech předchozích testů, což umožňuje efektivní distribuci testovacího procesu.

Variace a rozšíření

Existuje mnoho způsobů, jak rozšířit problém skupinového testování. Jeden z nejdůležitějších se nazývá hlučný skupinové testování a zabývá se velkým předpokladem původního problému: že testování je bezchybné. Problém se skupinovým testováním se nazývá hlučný, když existuje nějaká šance, že výsledek skupinového testu je chybný (např. Vyjde pozitivní, když test neobsahuje žádné vady). The Bernoulliho šumový model předpokládá, že tato pravděpodobnost je nějaká konstanta, ${ displaystyle q}$, ale obecně to může záviset na skutečném počtu defektů v testu a počtu testovaných položek.^[5] Například účinek ředění lze modelovat tak, že pozitivní výsledek je pravděpodobnější, když je v testu více defektů (nebo více defektů jako zlomek testovaného počtu).^[6] Hlučný algoritmus bude mít vždy nenulovou pravděpodobnost chyby (tj. Nesprávného označení položky).

Skupinové testování lze rozšířit zvážením scénářů, ve kterých existují více než dva možné výsledky testu. Výsledky může mít například test ${ displaystyle 0,1}$ a ${ displaystyle 2 ^ {+}}$, což odpovídá neexistenci vad, jedné vadě nebo neznámému počtu vad větší než jedna. Obecněji je možné považovat soubor výsledků testu za ${ displaystyle {0,1, ldots, k ^ {+}}}$ pro některé ${ displaystyle k in mathbb {N}}$.^[3]

Dalším rozšířením je uvažovat o geometrických omezeních, na kterých lze sady testovat. Výše uvedený problém s žárovkou je příkladem tohoto druhu omezení: lze testovat pouze žárovky, které se objevují postupně. Podobně mohou být položky uspořádány do kruhu nebo obecně do sítě, kde jsou testy k dispozici cesty v grafu. Dalším druhem geometrického omezení by byl maximální počet položek, které lze testovat ve skupině,^[A] nebo velikosti skupin možná budou muset být sudé atd. Podobným způsobem může být užitečné vzít v úvahu omezení, že se daná položka může objevit pouze v určitém počtu testů.^[3]

Existuje nekonečné množství způsobů, jak pokračovat v remixování základního vzorce skupinového testování. Následující zpracování poskytne představu o některých exotičtějších variantách. V modelu „dobrý – průměrný – špatný“ je každá položka jednou z hodnot „dobrá“, „průměrná“ nebo „špatná“ a výsledkem testu je typ „nejhorší“ položky ve skupině. Při testování prahové skupiny je výsledek testu pozitivní, pokud je počet vadných položek ve skupině větší než nějaká prahová hodnota nebo poměr.^[7] Skupinové testování s inhibitory je variantou s aplikacemi v molekulární biologii. Zde existuje třetí třída položek zvaná inhibitory a výsledek testu je pozitivní, pokud obsahuje alespoň jeden vadný a žádné inhibitory.^[8]

Historie a vývoj

Vynález a počáteční pokrok

Koncept skupinového testování poprvé představil Robert Dorfman v roce 1943 v krátké zprávě^[2] publikováno v sekci Poznámky v Annals of Mathematical Statistics.^[3][b] Zpráva Dorfmana - stejně jako u všech raných prací na skupinovém testování - se zaměřila na pravděpodobnostní problém a zaměřila se na využití nové myšlenky skupinového testování ke snížení očekávaného počtu testů potřebných k vyřazení všech syfilitických mužů v dané skupině vojáků. Metoda byla jednoduchá: rozdělte vojáky do skupin dané velikosti a pomocí individuálního testování (testování položek ve skupinách velikosti jedna) u pozitivních skupin vyhledejte infikované. Dorfman shrnul optimální velikosti skupin pro tuto strategii proti míře prevalence defektů v populaci.^[2]

Po roce 1943 zůstalo skupinové testování po řadu let do značné míry nedotčeno. V roce 1957 pak Sterrett vylepšil Dorfmanův postup.^[10] Tento novější proces začíná opětovným provedením individuálního testování na pozitivních skupinách, ale zastaví se, jakmile je zjištěn defekt. Poté jsou zbývající položky ve skupině testovány společně, protože je velmi pravděpodobné, že žádný z nich není vadný.

První důkladné zpracování skupinových testů poskytli Sobel a Groll ve své formativní práci na toto téma z roku 1959.^[11] Popsali pět nových postupů - kromě zobecnění pro případ, kdy je míra prevalence neznámá - a pro nejoptimálnější poskytli explicitní vzorec pro očekávaný počet testů, které bude používat. Příspěvek také vytvořil spojení mezi skupinovým testováním a teorie informace poprvé, stejně jako diskuse o několika zevšeobecněních problému skupinového testování a poskytnutí některých nových aplikací teorie.

Kombinatorické skupinové testování

Skupinové testování bylo poprvé studováno v kombinatorickém kontextu Li v roce 1962,^[12] se zavedením Li ${ displaystyle s}$- fázový algoritmus.^[3] Li navrhl rozšíření Dorfmanova „dvoustupňového algoritmu“ na libovolný počet stupňů, které nevyžadovaly více než ${ displaystyle t = { frac {e} { log _ {2} (e)}} d log _ {2} (n)}$ je třeba zaručeně najít testy ${ displaystyle d}$ nebo méně vad mezi ${ displaystyle n}$ Myšlenkou bylo odstranit všechny položky v negativních testech a rozdělit zbývající položky do skupin, jak tomu bylo u počátečního fondu. To se mělo udělat ${ displaystyle s-1}$ před provedením individuálního testování.

Kombinatorické skupinové testování bylo později podrobněji studováno Katonou v roce 1973.^[13] Katona představila maticová reprezentace neadaptivního skupinového testování a vytvořil postup pro zjištění defektu u neadaptivního 1-defektního případu ne více než ${ displaystyle t = lceil log _ {2} (n) rceil}$testy, které se také ukázaly jako optimální.

Obecně je nalezení optimálních algoritmů pro adaptivní kombinatorické skupinové testování obtížné a přestože výpočetní složitost skupinového testování nebylo stanoveno, předpokládá se, že je tvrdý v nějaké třídě složitosti.^[3] K důležitému průlomu však došlo v roce 1972, kdy byl zaveden zobecněný algoritmus binárního dělení.^[14] Zobecněný algoritmus binárního dělení funguje provedením a binární vyhledávání na skupinách, které testují pozitivně, a je to jednoduchý algoritmus, který shledá jednu vadnou za ne více než informace-dolní hranice počet testů.

Ve scénářích, kde existují dva nebo více defektů, generalizovaný algoritmus binárního dělení stále produkuje téměř optimální výsledky, které vyžadují maximálně ${ displaystyle d-1}$ testy nad dolní mezí informací kde ${ displaystyle d}$ je počet vad.^[14] V roce 2013 provedl Allemann značná vylepšení, čímž se požadovaný počet testů snížil na méně než ${ displaystyle 0,187 d + 0,5 log _ {2} (d) +5,5}$ nad dolní mezí informací, když ${ displaystyle n / d geq 38}$ a ${ displaystyle d geq 10}$.^[15] Toho bylo dosaženo změnou binárního vyhledávání v algoritmu binárního dělení na komplexní sadu subalgoritmů s překrývajícími se testovacími skupinami. Jako takový byl problém adaptivního kombinatorického skupinového testování - se známým počtem nebo horní mezí počtu defektů - v podstatě vyřešen, s malým prostorem pro další zlepšení.

Existuje otevřená otázka, kdy je individuální testování minmax. Hu, Hwang a Wang v roce 1981 ukázali, že individuální testování je minmax, když ${ Displaystyle n leq lfloor (5d + 1) / 2 rfloor}$, a že to není minmax, když ${ displaystyle n> 3d}$.^[16] V současné době se předpokládá, že tato hranice je ostrá: to znamená, že individuální testování je minmax právě tehdy ${ displaystyle n leq 3d}$.^[17][C] Určitého pokroku dosáhli v roce 2000 Ricccio a Colbourn, kteří to ukázali ve velkém ${ displaystyle n}$, individuální testování je minmax, když ${ displaystyle d geq n / log _ {3/2} (3) přibližně 0,369}}$.^[18]

Neadaptivní a pravděpodobnostní testování

Jedním z klíčových poznatků v neadaptivním skupinovém testování je, že významného zisku lze dosáhnout odstraněním požadavku, aby byl postup skupinového testování jistý, že uspěje („kombinatorický“ problém), ale spíše mu dovoluje mít určité nízké, ale ne - nulová pravděpodobnost nesprávného označení každé položky („pravděpodobnostní“ problém). Je známo, že jak se počet vadných položek blíží celkovému počtu položek, vyžadují přesná kombinatorická řešení podstatně více testů než pravděpodobnostní řešení - dokonce i pravděpodobnostní řešení umožňující pouze asymptoticky malá pravděpodobnost chyby.^[4][d]

V tomto duchu, Chan et al. (2011) COMP, pravděpodobnostní algoritmus, který nevyžaduje více než ${ displaystyle t = ed (1+ delta) ln (n)}$ testy najít ${ displaystyle d}$ vady v ${ displaystyle n}$ položky s pravděpodobností chyby nejvýše ${ displaystyle n ^ {- delta}}$.^[5] To je v rámci konstantního faktoru ${ displaystyle t = O (d log _ {2} n)}$ dolní mez.^[4]

Chan et al. (2011) také poskytli zobecnění COMP na jednoduchý hlučný model a podobně vytvořili explicitní vázaný výkon, který byl opět pouze konstantou (v závislosti na pravděpodobnosti neúspěšného testu) nad odpovídající dolní mezí.^[4][5] Obecně je počet zkoušek požadovaných v případě Bernoulliho šumu o konstantní faktor větší než v případě bezhlučného případu.^[5]

Aldridge, Baldassini a Johnson (2014) vytvořili rozšíření algoritmu COMP, které přidalo další kroky po zpracování.^[19] Ukázali, že výkon tohoto nového algoritmu, tzv DD, striktně překračuje to COMP a toto DD je „v zásadě optimální“ ve scénářích, kde ${ displaystyle d ^ {2} geq n}$porovnáním s hypotetickým algoritmem, který definuje přiměřené optimum. Výkon tohoto hypotetického algoritmu naznačuje, že existuje prostor pro zlepšení, když ${ displaystyle d ^ {2}$, a také navrhnout, jak velké zlepšení by to mohlo být.^[19]

Formalizace testování kombinatorické skupiny

Tato část formálně definuje pojmy a pojmy týkající se skupinového testování.

• The vstupní vektor, ${ displaystyle mathbf {x} = (x_ {1}, x_ {2}, tečky, x_ {n})}$, je definován jako binární vektor délky ${ displaystyle n}$ (to znamená, ${ displaystyle mathbf {x} v {0,1 } ^ {n}}$), s j-tá položka, která se volá vadný kdyby a jen kdyby ${ displaystyle x_ {j} = 1}$. Jakákoli nezávadná položka se dále nazývá „dobrá“ položka.

${ displaystyle mathbf {x}}$ je určen k popisu (neznámé) sady vadných položek. Klíčová vlastnost ${ displaystyle mathbf {x}}$ je to, že je implicitní vstup. To znamená, že neexistuje žádná přímá znalost toho, o co jde ${ displaystyle mathbf {x}}$ jsou jiné než ty, které lze odvodit pomocí několika sérií „testů“. To vede k další definici.

• Nechat ${ displaystyle mathbf {x}}$ být vstupním vektorem. Sada, ${ displaystyle S subseteq {1,2, tečky, n }}$ se nazývá a test. Když je testování tichý, výsledek testu je pozitivní když existuje ${ displaystyle j v S}$ takhle ${ displaystyle x_ {j} = 1}$a výsledek je negativní v opačném případě.

Cílem skupinového testování je proto přijít s metodou výběru „krátké“ série testů, které to umožní ${ displaystyle mathbf {x}}$ bude stanoveno, buď přesně, nebo s vysokou mírou jistoty.

• Algoritmus skupinového testování prý dělá chyba pokud položku nesprávně označí (tj. označí jakoukoli vadnou položku jako nezávadnou nebo naopak). Tohle je ne totéž jako výsledek nesprávného skupinového testu. Algoritmus se nazývá nulová chyba pokud je pravděpodobnost, že udělá chybu, nulová.^[E]
• ${ displaystyle t (d, n)}$ označuje minimální počet testů potřebných k nalezení vždy ${ displaystyle d}$ defekty mezi ${ displaystyle n}$ položky s nulovou pravděpodobností chyby jakýmkoli algoritmem skupinového testování. Pro stejnou veličinu, ale s omezením, že algoritmus je neadaptivní, notace ${ displaystyle { bar {t}} (d, n)}$ se používá.

Obecné hranice

Protože je vždy možné uchýlit se k individuálnímu testování nastavením ${ displaystyle S_ {j} = {j }}$ pro každého ${ Displaystyle 1 leq j leq n}$, musí to tak být ${ displaystyle { bar {t}} (d, n) leq n}$. Jelikož jakýkoli neadaptivní testovací postup lze zapsat jako adaptivní algoritmus pouhým provedením všech testů bez ohledu na jejich výsledek, ${ displaystyle t (d, n) leq { bar {t}} (d, n)}$. Konečně, když ${ displaystyle 0 neq d neq n}$, existuje alespoň jedna položka, jejíž vadnost musí být stanovena (alespoň jednou zkouškou) atd ${ Displaystyle 1 leq t (d, n)}$.

Souhrnně (při předpokladu ${ displaystyle 0 neq d neq n}$), ${ Displaystyle 1 leq t (d, n) leq { bar {t}} (d, n) leq n}$.^[F]

Informace dolní mez

Dolní hranici počtu potřebných testů lze popsat pomocí pojmu ukázkový prostor, označeno ${ displaystyle { mathcal {S}}}$, což je jednoduše soubor možných umístění vad. Pro jakýkoli problém s testováním skupiny s ukázkovým prostorem ${ displaystyle { mathcal {S}}}$ a jakýkoli algoritmus pro testování skupin, lze to ukázat ${ displaystyle t geq lceil log _ {2} {| { mathcal {S}} |} rceil}$, kde ${ displaystyle t}$ je minimální počet zkoušek požadovaných k identifikaci všech vad s nulovou pravděpodobností chyby. Tomu se říká informace dolní mez.^[3] Tato vazba je odvozena ze skutečnosti, že po každém testu ${ displaystyle { mathcal {S}}}$ je rozdělena do dvou nesouvislých podmnožin, z nichž každá odpovídá jednomu ze dvou možných výsledků testu.

Samotná dolní mez informací je však obvykle nedosažitelná, a to i pro malé problémy.^[3] Je to proto, že rozdělení ${ displaystyle { mathcal {S}}}$ není libovolný, protože musí být proveditelný nějakým testem.

Ve skutečnosti lze dolní mez informací zobecnit na případ, kdy existuje nenulová pravděpodobnost, že algoritmus udělá chybu. V této formě nám věta dává horní hranici pravděpodobnosti úspěchu na základě počtu testů. Pro jakýkoli algoritmus skupinového testování, který funguje ${ displaystyle t}$ testy, pravděpodobnost úspěchu, ${ displaystyle mathbb {P} ({ textrm {success}})}$, splňuje ${ displaystyle mathbb {P} ({ textrm {success}}) leq t / log _ {2} {n zvolit d}}$. To lze posílit na: ${ displaystyle mathbb {P} ({ textrm {success}}) leq { frac {2 ^ {t}} {n zvolit d}}}$.^[5][20]

Reprezentace neadaptivních algoritmů

Typické nastavení testování skupiny. Neadaptivní algoritmus nejprve vybere matici ${ displaystyle M}$, a poté dostane vektor y. Problém je pak najít odhad pro X.

Algoritmy pro neadaptivní skupinové testování se skládají ze dvou odlišných fází. Nejprve se rozhodne, kolik testů provést a které položky zahrnout do každého testu. Ve druhé fázi, často nazývané krok dekódování, se analyzují výsledky každého skupinového testu, aby se určilo, které položky budou pravděpodobně vadné. První fáze je obvykle kódována v matici následujícím způsobem.^[5]

• Předpokládejme neadaptivní postup testování skupiny pro ${ displaystyle n}$ položky se skládá z testů ${ displaystyle S_ {1}, S_ {2}, tečky, S_ {t}}$ pro některé ${ displaystyle t in mathbb {N} _ { geq 0}}$. The testovací matice pro toto schéma je ${ displaystyle t krát n}$ binární matice, ${ displaystyle M}$, kde ${ displaystyle (M) _ {ij} = 1}$ kdyby a jen kdyby ${ displaystyle j v S_ {i}}$ (a jinak je nula).

Každý sloupec tedy ${ displaystyle M}$ představuje položku a každý řádek představuje test s a ${ displaystyle 1}$ v ${ displaystyle (i, j) { textrm {-th}}}$ položka označující, že ${ displaystyle i { textrm {-th}}}$ test zahrnoval ${ displaystyle j { textrm {-th}}}$ položka a ${ displaystyle 0}$ označující opak.

Stejně jako vektor ${ displaystyle mathbf {x}}$ (délky ${ displaystyle n}$), který popisuje neznámou vadnou množinu, je běžné zavést vektor výsledků, který popisuje výsledky každého testu.

• Nechat ${ displaystyle t}$ je počet testů provedených neadaptivním algoritmem. The vektor výsledků, ${ displaystyle mathbf {y} = (y_ {1}, y_ {2}, tečky, y_ {t})}$, je binární vektor délky ${ displaystyle t}$ (to znamená, ${ displaystyle mathbf {y} v {0,1 } ^ {t}}$) takové, že ${ displaystyle y_ {i} = 1}$ právě tehdy, pokud je výsledkem ${ displaystyle i { textrm {-th}}}$ test byl pozitivní (tj. obsahoval alespoň jeden vadný).^[G]

S těmito definicemi lze neadaptivní problém přejmenovat následujícím způsobem: nejprve je vybrána testovací matice, ${ displaystyle M}$, po kterém vektor ${ displaystyle mathbf {y}}$ je vrácen. Pak je problém analyzovat ${ displaystyle mathbf {y}}$ najít nějaký odhad pro ${ displaystyle mathbf {x}}$.

V nejjednodušším hlučném případě, kde je stálá pravděpodobnost, ${ displaystyle q}$, že skupinový test bude mít chybný výsledek, vezme se v úvahu náhodný binární vektor, ${ displaystyle mathbf {v}}$, kde každý záznam má pravděpodobnost ${ displaystyle q}$ bytí ${ displaystyle 1}$, a je ${ displaystyle 0}$ v opačném případě. Vrácený vektor je pak ${ displaystyle { hat { mathbf {y}}} = mathbf {y} + mathbf {v}}$, s obvyklým doplňkem na ${ displaystyle ( mathbb {Z} / 2 mathbb {Z}) ^ {n}}$ (ekvivalentně je to elementární XOR úkon). Hlučný algoritmus musí odhadnout ${ displaystyle mathbf {x}}$ použitím ${ displaystyle { hat { mathbf {y}}}}$ (tj. bez přímé znalosti ${ displaystyle mathbf {y}}$).^[5]

Meze pro neadaptivní algoritmy

Maticová reprezentace umožňuje dokázat určité hranice při neadaptivním skupinovém testování. Tento přístup odráží to, co existuje u mnoha deterministických návrhů ${ displaystyle d}$- jsou uvažovány oddělitelné matice, jak je definováno níže.^[3]

• Binární matice, ${ displaystyle M}$, je nazýván ${ displaystyle d}$-oddělitelný pokud každý booleovský součet (logický OR) libovolného ${ displaystyle d}$ jeho sloupců je odlišný. Navíc notace ${ displaystyle { bar {d}}}$-oddělitelný označuje, že každý součet některého z až do ${ displaystyle d}$ z ${ displaystyle M}$sloupce jsou odlišné. (To není totéž jako ${ displaystyle M}$ bytost ${ displaystyle k}$-oddělitelné pro každého ${ displaystyle k leq d}$.)

Když ${ displaystyle M}$ je testovací matice, vlastnost bytí ${ displaystyle d}$-oddělitelné (${ displaystyle { bar {d}}}$-separable) je ekvivalentní schopnosti rozlišovat mezi (až) ${ displaystyle d}$ vady. Nezaručuje však, že to bude jednoduché. Silnější vlastnost, tzv ${ displaystyle d}$-disjunctness dělá.

• Binární matice, ${ displaystyle M}$ je nazýván ${ displaystyle d}$-disjunct pokud booleovský součet nějakého ${ displaystyle d}$ sloupce neobsahuje žádný další sloupec. (V této souvislosti se říká, že sloupec A obsahuje sloupec B, pokud pro každý index, kde B má 1, má A také 1.)

Užitečná vlastnost ${ displaystyle d}$-disjunct testování matic je to, že až ${ displaystyle d}$ defektů, každá nezávadná položka se objeví alespoň v jednom testu, jehož výsledek je negativní. To znamená, že pro nalezení defektů existuje jednoduchý postup: stačí odstranit všechny položky, které se objeví v negativním testu.

Používání vlastností ${ displaystyle d}$-oddělitelné a ${ displaystyle d}$-disjunct matice následující mohou být ukázány pro problém identifikace ${ displaystyle d}$ defekty mezi ${ displaystyle n}$ celkem položek.^[4]

1. Počet testů potřebných pro asymptoticky malý průměrný pravděpodobnost chybových stupnic jako ${ displaystyle O (d log _ {2} n)}$.
2. Počet testů potřebných pro asymptoticky malý maximum pravděpodobnost chybových stupnic jako ${ displaystyle O (d ^ {2} log _ {2} n)}$.
3. Počet testů potřebných pro a nula pravděpodobnost chybových stupnic jako ${ displaystyle O left ({ frac {d ^ {2} log _ {2} n} { log _ {2} d}} right)}$.

Zobecněný algoritmus binárního dělení

Ilustrace zobecněného algoritmu binárního rozdělení, kde je 8 defektů a celkem 135 položek. Tady, ${ displaystyle 2 ^ { alpha _ {1}} = 16}$a první test dává negativní výsledek, takže každá položka je prohlášena za vadnou. Proto zbývá 119 položek, takže ${ displaystyle 2 ^ { alpha _ {2}} = 8}$. Tato druhá skupina dává pozitivní výsledek, takže k nalezení vadného se používá binární vyhledávání. Jakmile je to hotové, celý proces se opakuje a vypočítává se nový ${ displaystyle alpha}$ používat pouze ty položky, jejichž vadnost nebyla stanovena.

Zobecněný algoritmus binárního dělení je v zásadě optimální algoritmus adaptivního testování skupin, který najde ${ displaystyle d}$ nebo méně vad mezi ${ displaystyle n}$ položky takto:^[3][14]

1. Li ${ displaystyle n leq 2d-2}$, vyzkoušejte ${ displaystyle n}$ položky jednotlivě. Jinak nastavte ${ displaystyle l = n-d + 1}$ a ${ displaystyle alpha = lfloor log _ {2} {l / d} rfloor}$.
2. Vyzkoušejte skupinu velikosti ${ displaystyle 2 ^ { alpha}}$. Pokud je výsledek negativní, je každá položka ve skupině prohlášena za nezávadnou; soubor ${ displaystyle n: = n-2 ^ { alpha}}$ a přejděte ke kroku 1. Jinak použijte a binární vyhledávání identifikovat jedno vadné a nespecifikované číslo, volané ${ displaystyle x}$nezávadných položek; soubor ${ displaystyle n: = n-1-x}$ a ${ displaystyle d: = d-1}$. Přejděte na krok 1.

Zobecněný algoritmus binárního rozdělení nevyžaduje více než ${ displaystyle T}$ testy kde${ displaystyle T = { begin {cases} n & n leq 2d-2 ( alpha +2) d + p-1 & n geq 2d-1 end {cases}}}$.^[3]

Pro ${ displaystyle n / d}$ velké, lze to ukázat ${ displaystyle T rightarrow d log _ {2} (n / d)}$,^[3] který se příznivě srovnává s ${ displaystyle t = { frac {e} { log _ {2} e}} d log _ {2} left ({ frac {n} {d}} right)}$ testy požadované pro Li ${ displaystyle s}$- fázový algoritmus. Ve skutečnosti je zobecněný algoritmus binárního dělení blízký optimálnímu v následujícím smyslu. Když ${ displaystyle d geq 2}$ lze to ukázat ${ displaystyle T-B_ {I} (d, n) leq (d-1)}$, kde ${ displaystyle B_ {I} (d, n) = levý lceil log _ {2} součet _ {i = 0} ^ {d} {n zvolit i} pravý rceil}$ je informace dolní mez.^[3][14]

Neadaptivní algoritmy

Neadaptivní algoritmy pro testování skupin mají tendenci předpokládat, že je znám počet defektů nebo alespoň jejich dobrá horní hranice.^[5] Toto množství je označeno ${ displaystyle d}$ v této části. Pokud nejsou známy žádné hranice, existují neadaptivní algoritmy s nízkou složitostí dotazů, které mohou pomoci odhadnout ${ displaystyle d}$.^[21]

Pronásledování kombinatorickým ortogonálním párováním (COMP)

Ilustrace algoritmu COMP. COMP identifikuje položku A jako vadný a předmět b jako nezávadné. Nesprávně však označuje C jako vadný, protože je „skrytý“ vadnými položkami v každém testu, ve kterém se objeví.

Combinatorial Orthogonal Matching Pursuit neboli COMP je jednoduchý neadaptivní algoritmus pro testování skupin, který tvoří základ složitějších algoritmů, které následují v této části.

Nejprve je vybrána každá položka testovací matice i.i.d. být ${ displaystyle 1}$ s pravděpodobností ${ displaystyle 1 / d}$ a ${ displaystyle 0}$ v opačném případě.

Krok dekódování pokračuje po sloupcích (tj. Po položkách). Pokud je každý test, ve kterém se položka objeví, pozitivní, pak je položka prohlášena za vadnou; jinak se předpokládá, že položka není vadná. Nebo ekvivalentně, pokud se položka objeví v testu, jehož výsledek je negativní, je položka prohlášena za nezávadnou; jinak se předpokládá, že je vadný. Důležitou vlastností tohoto algoritmu je, že nikdy nevytváří falešné negativy, ačkoli falešně pozitivní nastane, když všechna místa s těmi v j-tý sloupec ${ displaystyle M}$ (odpovídá nezávadnému zboží j) jsou „skryty“ ostatními sloupci odpovídajícími vadným položkám.

Algoritmus COMP nevyžaduje více než ${ displaystyle ed (1+ delta) ln (n)}$ testy, jejichž pravděpodobnost chyby je menší nebo rovna ${ displaystyle n ^ {- delta}}$.^[5] To je v rámci konstantního faktoru dolní meze pro průměrnou pravděpodobnost chyby výše.

V hlučném případě uvolní požadavek v původním algoritmu COMP, aby množina pozic těch v libovolném sloupci ${ displaystyle M}$ odpovídající kladné položce budou zcela obsaženy v sadě umístění jedniček ve vektoru výsledků. Místo toho jeden umožňuje určitý počet „neshod“ - tento počet nesouladů závisí jak na počtu jednotek v každém sloupci, tak také na parametru šumu, ${ displaystyle q}$. Tento hlučný algoritmus COMP nevyžaduje více než ${ displaystyle 4.36 ({ sqrt { delta}} + { sqrt {1+ delta}}) ^ {2} (1-2q) ^ {- 2} d log _ {2} {n}}$ testy k dosažení maximální pravděpodobnosti chyby ${ displaystyle n ^ {- delta}}$.^[5]

Určité vady (DD)

Metoda definitivních defektů (DD) je rozšířením algoritmu COMP, který se pokouší odstranit jakékoli falešné poplachy. Ukázalo se, že výkonnostní záruky pro DD přísně překračují záruky COMP.^[19]

Krok dekódování využívá užitečnou vlastnost algoritmu COMP: že každá položka, kterou COMP deklaruje jako nezávadnou, je určitě nezávadná (to znamená, že neexistují žádné falešné negativy). Postupuje následovně.

1. Nejprve je spuštěn algoritmus COMP a odstraněny všechny závady, které detekuje. Všechny zbývající položky jsou nyní „pravděpodobně vadné“.
2. Algoritmus dále zkoumá všechny pozitivní testy. Pokud se položka v testu objeví jako jediná „možná vadná“, pak musí být vadná, takže algoritmus ji prohlásí za vadnou.
3. Předpokládá se, že všechny ostatní položky nejsou vadné. Odůvodnění tohoto posledního kroku vychází z předpokladu, že počet defektů je mnohem menší než celkový počet položek.

Všimněte si, že kroky 1 a 2 nikdy neudělají chybu, takže algoritmus může udělat chybu, pouze pokud deklaruje vadnou položku za nezávadnou. Algoritmus DD tedy může vytvářet pouze falešné negativy.

Sekvenční COMP (SCOMP)

SCOMP (Sequential COMP) je algoritmus, který využívá skutečnosti, že DD nedělá chyby až do posledního kroku, kdy se předpokládá, že zbývající položky nejsou vadné. Nechť je soubor deklarovaných vad ${ displaystyle K}$. Pozitivní test se nazývá vysvětleno podle ${ displaystyle K}$ pokud obsahuje alespoň jednu položku v systému Windows ${ displaystyle K}$. Klíčovým poznatkem u SCOMP je, že sada defektů nalezená DD nemusí vysvětlovat každý pozitivní test a že každý nevysvětlený test musí obsahovat skrytý defekt.

Algoritmus probíhá následovně.

1. Proveďte kroky 1 a 2 algoritmu DD, které chcete získat ${ displaystyle K}$, počáteční odhad pro soubor defektů.
2. Li ${ displaystyle K}$ vysvětluje každý pozitivní test, ukončete algoritmus: ${ displaystyle K}$ je konečný odhad pro soubor defektů.
3. Pokud existují nějaké nevysvětlené testy, najděte „možný defekt“, který se objeví v největším počtu nevysvětlených testů, a prohlédněte jej jako defektní (tj. Přidejte jej do sady ${ displaystyle K}$). Přejděte na krok 2.

V simulacích se ukázalo, že SCOMP funguje téměř optimálně.^[19]

Ukázkové aplikace

Obecnost teorie skupinového testování ji propůjčuje mnoha různým aplikacím, včetně screeningu klonů, lokalizace elektrických zkratů;^[3] vysokorychlostní počítačové sítě;^[22] lékařské vyšetření, vyhledávání množství, statistiky;^[16] strojové učení, sekvenování DNA;^[23] kryptografie;^[24][25] a datová forenzní.^[26] Tato část poskytuje stručný přehled malého výběru těchto aplikací.

Kanály pro více přístupů

Ilustrace kanálu s více přístupy zobrazující úspěšnou zprávu a kolizi zprávy.

A kanál více přístupů je komunikační kanál, který spojuje mnoho uživatelů najednou. Každý uživatel může poslouchat a vysílat na kanálu, ale pokud vysílá více než jeden uživatel současně, signály se srazí a sníží se na nesrozumitelný šum. Kanály pro více procesů jsou důležité pro různé aplikace v reálném světě, zejména bezdrátové počítačové sítě a telefonní sítě.^[27]

Prominentním problémem u kanálů s více přístupy je, jak přiřadit přenosové časy uživatelům, aby se jejich zprávy nekolidovaly. Jednoduchou metodou je poskytnout každému uživateli svůj vlastní časový úsek, ve kterém má vysílat, což vyžaduje ${ displaystyle n}$ sloty. (Tomu se říká multiplexování s časovým dělením, nebo TDM.) To je však velmi neefektivní, protože přiřadí přenosové sloty uživatelům, kteří nemusí mít zprávu, a obvykle se předpokládá, že v daném okamžiku bude chtít vysílat pouze několik uživatelů - jinak multiaccess kanál není praktické na prvním místě.

V kontextu skupinového testování je tento problém obvykle řešen rozdělením času na „epochy“ následujícím způsobem.^[3] Uživateli se říká „aktivní“, pokud má na začátku epochy zprávu. (If a message is generated during an epoch, the user only becomes active at the start of the next one.) An epoch ends when every active user has successfully transmitted their message. The problem is then to find all the active users in a given epoch, and schedule a time for them to transmit (if they have not already done so successfully). Here, a test on a set of users corresponds to those users attempting a transmission. The results of the test are the number of users that attempted to transmit, ${displaystyle 0,1,}$ a ${displaystyle 2^{+}}$, corresponding respectively to no active users, exactly one active user (message successful) or more than one active user (message collision). Therefore, using an adaptive group testing algorithm with outcomes ${displaystyle {0,1,2^{+}}}$, it can be determined which users wish to transmit in the epoch. Then, any user that has not yet made a successful transmission can now be assigned a slot to transmit, without wastefully assigning times to inactive users.

Machine learning and compressed sensing

Strojové učení is a field of computer science that has many software applications such as DNA classification, fraud detection and targeted advertising. One of the main subfields of machine learning is the 'learning by examples' problem, where the task is to approximate some unknown function when given its value at a number of specific points.^[3] As outlined in this section, this function learning problem can be tackled with a group-testing approach.

In a simple version of the problem, there is some unknown function, ${displaystyle f:{0,1}^{N} o {0,1}}$ kde ${displaystyle f({ extbf {x}})={ extbf {a}}cdot { extbf {x}}}$, a ${displaystyle { extbf {a}}in {0,1}^{N}}$ (using logical arithmetic: addition is logical OR and multiplication is logical AND). Tady ${displaystyle { extbf {a}}}$ je '${ displaystyle d}$ sparse', which means that at most ${displaystyle dll N}$ of its entries are ${ displaystyle 1}$. The aim is to construct an approximation to ${ displaystyle f}$ použitím ${ displaystyle t}$ point evaluations, where ${ displaystyle t}$ je co nejmenší.^[4] (Exactly recovering ${ displaystyle f}$ corresponds to zero-error algorithms, whereas ${ displaystyle f}$ is approximated by algorithms that have a non-zero probability of error.)

In this problem, recovering ${ displaystyle f}$ is equivalent to finding ${displaystyle { extbf {a}}}$. Navíc, ${displaystyle f({ extbf {p}})=1}$ if and only if there is some index, ${ displaystyle n}$, kde ${displaystyle { extbf {a}}_{n}={ extbf {p}}_{n}=1}$. Thus this problem is analogous to a group-testing problem with ${ displaystyle d}$ defectives and ${ displaystyle n}$ total items. The entries of ${displaystyle { extbf {a}}}$ are the items, which are defective if they are ${ displaystyle 1}$, ${ displaystyle { textbf {p}}}$ specifies a test, and a test is positive if and only if ${displaystyle f({ extbf {p}})=1}$.^[4]

In reality, one will often be interested in functions that are more complicated, such as ${displaystyle f:mathbb {C} ^{N} o mathbb {C} }$, again where ${displaystyle f({ extbf {x}})={ extbf {a}}cdot { extbf {x}}}$. Komprimované snímání, which is closely related to group testing, can be used to solve this problem.^[4]

In compressed sensing, the goal is to reconstruct a signal, ${displaystyle { extbf {v}}in mathbb {C} ^{N}}$, by taking a number of measurements. These measurements are modelled as taking the dot product of ${ displaystyle { textbf {v}}}$ with a chosen vector.^[h] The aim is to use a small number of measurements, though this is typically not possible unless something is assumed about the signal. One such assumption (which is common^[30][31]) is that only a small number of entries of ${ displaystyle { textbf {v}}}$ jsou významný, meaning that they have a large magnitude. Since the measurements are dot products of ${ displaystyle { textbf {v}}}$, rovnice ${displaystyle M{ extbf {v}}={ extbf {q}}}$ holds, where ${ displaystyle M}$ je ${displaystyle t imes N}$ matrix that describes the set of measurements that have been chosen and ${ displaystyle mathbf {q}}$ is the set of measurement results. This construction shows that compressed sensing is a kind of 'continuous' group testing.

The primary difficulty in compressed sensing is identifying which entries are significant.^[30] Once that is done, there are a variety of methods to estimate the actual values of the entries.^[32] This task of identification can be approached with a simple application of group testing. Here a group test produces a complex number: the sum of the entries that are tested. The outcome of a test is called positive if it produces a complex number with a large magnitude, which, given the assumption that the significant entries are sparse, indicates that at least one significant entry is contained in the test.

There are explicit deterministic constructions for this type of combinatorial search algorithm, requiring ${displaystyle d2^{(log _{2}log _{2}N)^{O(1)}}}$ Měření.^[33] However, as with group-testing, these are sub-optimal, and random constructions (such as COMP) can often recover ${ displaystyle f}$ sub-linearly in ${ displaystyle N}$.^[32]

Multiplex assay design for COVID19 testing

During a pandemic such as the COVID-19 outbreak in 2020, virus detection assays are sometimes run using nonadaptive group testing designs.^[34][35] One example was provided by the Origami Assays project which released open source group testing designs to run on a laboratory standard 96 well plate.^[36]

Origami Assay paper template for group testing design

In a laboratory setting, one challenge of group testing is the construction of the mixtures can be time-consuming and difficult to do accurately by hand. Origami assays provided a workaround for this construction problem by providing paper templates to guide the technician on how to allocate patient samples across the test wells.^[37]

Using the largest group testing designs (XL3) it was possible to test 1120 patient samples in 94 assay wells. If the true positive rate was low enough, then no additional testing was required.

Viz také: Seznam zemí implementujících strategii testování fondů proti COVID-19.

Data forensics

Data forensics is a field dedicated to finding methods for compiling digital evidence of a crime. Such crimes typically involve an adversary modifying the data, documents or databases of a victim, with examples including the altering of tax records, a virus hiding its presence, or an identity thief modifying personal data.^[26]

A common tool in data forensics is the one-way cryptographic hash. This is a function that takes the data, and through a difficult-to-reverse procedure, produces a unique number called a hash.^[i] Hashes, which are often much shorter than the data, allow us to check if the data has been changed without having to wastefully store complete copies of the information: the hash for the current data can be compared with a past hash to determine if any changes have occurred. An unfortunate property of this method is that, although it is easy to tell if the data has been modified, there is no way of determining how: that is, it is impossible to recover which part of the data has changed.^[26]

One way to get around this limitation is to store more hashes – now of subsets of the data structure – to narrow down where the attack has occurred. However, to find the exact location of the attack with a naive approach, a hash would need to be stored for every datum in the structure, which would defeat the point of the hashes in the first place. (One may as well store a regular copy of the data.) Group testing can be used to dramatically reduce the number of hashes that need to be stored. A test becomes a comparison between the stored and current hashes, which is positive when there is a mismatch. This indicates that at least one edited datum (which is taken as defectiveness in this model) is contained in the group that generated the current hash.^[26]

In fact, the amount of hashes needed is so low that they, along with the testing matrix they refer to, can even be stored within the organisational structure of the data itself. This means that as far as memory is concerned the test can be performed 'for free'. (This is true with the exception of a master-key/password that is used to secretly determine the hashing function.)^[26]

Poznámky

Reference

Citace

Obecné odkazy

• Ding-Zhu, Du; Hwang, Frank K. (1993). Combinatorial group testing and its applications. Singapur: World Scientific. ISBN  978-9810212933.
• Atri Rudra's course on Error Correcting Codes: Combinatorics, Algorithms, and Applications (Spring 2007), Lectures 7.
• Atri Rudra's course on Error Correcting Codes: Combinatorics, Algorithms, and Applications (Spring 2010), Lectures 10, 11, 28, 29
• Du, D., & Hwang, F. (2006). Pooling Designs and Nonadaptive Group Testing. Boston: Twayne Publishers.
• Aldridge, M., Johnson, O. and Scarlett, J. (2019), Group Testing: An Information Theory Perspective, Foundations and Trends® in Communications and Information Theory: Vol. 15: No. 3-4, pp 196-392. doi:10.1561/0100000099
• Ely Porat, Amir Rothschild: Explicit Non-adaptive Combinatorial Group Testing Schemes. ICALP (1) 2008: 748–759
• Kagan, Eugene; Ben-gal, Irad (2014), "A group testing algorithm with online informational learning", Transakce IIE, 46 (2): 164–184, doi:10.1080/0740817X.2013.803639, ISSN  0740-817X

Viz také

• Balance puzzle