Proves de grup

Ilustració del problema de la pera: es busca una pera trencada entre sis peres. En este cas, les tres primeres estan conectades a una font d'alimentació i s'encenen (A). Açò indica que la pera trencada deu ser una de les tres últimes (B). Si, pel contrari, les peres no s'encengueren, es podria estar segur de que la pera trencada estava entre les tres primeres. Continuant en este procediment, es pot localisar la pera trencada en un màxim de tres proves, en comparació a un màxim de sis si es revisen les peres individualment.

En estadística i matemàtiques combinatòries, les proves de grup són procediments que dividixen la tasca d'identificar determinats objectes en proves sobre grups d'elements, en lloc de sobre elements individuals. Estudiada per primera volta per Robert Dorfman en 1943, la comprovació de grups és un camp relativament nou de la matemàtica aplicada que pot aplicar-se a un ampli palmito d'aplicacions pràctiques i és un àrea activa d'investigació en l'actualitat.

Un eixemple conegut de prova de grups és el d'una série de peres conectades en série de les que se sap que una està trencada. L'objectiu és trobar la pera estropejada en el menor número possible de proves (a on una prova és quan alguna de les peres està conectada a una font d'alimentació). Un método senzill consistix en provar cada pera per separat. No obstant, quan hi ha un gran número de peres, seria molt més eficaç agrupar-les. Per eixemple, conectant la primera mitat de les peres al mateix temps, es pot determinar en quina mitat està la pera estropejada, descartant la mitat de les peres en una sola prova.

Els esquemes per a portar a terme les proves en grup poden ser simples o complexos i les proves implicades en cada etapa poden ser diferents. Els esquemes en els que les proves de l'etapa següent depenen dels resultats de les etapes anteriors es denominen procediments adaptatius, mentres que els esquemes dissenyats per a que totes les proves es coneguen de bestreta es denominen procediments no adaptatius. L'estructura de l'esquema de les proves implicades en un procediment no adaptatiu es coneix com a disseny d'agrupació.

Les proves de grup tenen moltes aplicacions, com l'estadística, la biologia, l'informàtica, la medicina, l'ingenieria i la ciberseguridad. El Proyecte Genoma Humà ha revivat l'interés modern per estos esquemes de proves.

Descripció bàsica i térmens

A diferència de moltes àrees de les matemàtiques, els orígens de les proves de grup es remonten a un únic informe escrit per una sola persona: Robert Dorfman. La motivació va sorgir durant la Segona Guerra Mundial, quan el Servici de Salut Pública d'Estats Units i el Servici Selectiu es varen embarcar en un proyecte a gran escala per a eliminar a tots els hòmens sifilíticos cridats a files. La prova de la sífilis consistix en extraure una mostra de sanc i analisar-la per a determinar la presència o absència de sífilis. En aquella época, la realisació d'esta prova era cara, i analisar a cada soldat individualment hauria segut molt costós i ineficaç.

Suponent que hi haja 𝑛 soldats, este método d'anàlisis conduïx a 𝑛 proves separades. Si una gran proporció de persones estan infectades, este método seria raonable. No obstant, en el cas més provable de que només una proporció molt chicoteta dels hòmens estiguen infectats, es pot conseguir un esquema de proves molt més eficaç. La viabilitat d'un pla de proves més eficaç depén de la següent propietat: els soldats poden agrupar-se i en cada grup es poden combinar les mostres de sanc. La mostra combinada pot analisar-se per a comprovar si a lo manco un soldat del grup té sífilis. Esta és l'idea central de les proves en grup. Si un o més dels soldats d'este grup té sífilis, es desperdicia una prova (cal realisar més proves per a averiguar de quin soldat o soldats es tracta). Per un atre costat, si ningú del grup té sífilis, llavors s'aforren moltes proves, ya que tots els soldats d'eixe grup poden ser eliminats en una sola prova.

Els elements que fan que un grup done positiu es denominen generalment elements defectuosos (són les peres trencades, els hòmens sifilíticos, etc.). A sovint, el número total d'elements es denota com 𝑛 i 𝑑 representa el número de defectuosos si se supon que és conegut.

Classificació dels problemes de proves en grup

Existixen dos classificacions independents per als problemes de proves en grup; cada problema de proves en grup és adaptatiu o no adaptatiu, i provabilístic o combinatori.

En els models provabilístics, se supon que els elements defectuosos seguixen alguna distribució de provabilitat i l'objectiu és minimisar el número esperat de proves necessàries per a identificar la defectuosidad de cada element. En canvi, en les proves combinatòries de grup, l'objectiu és minimisar el número de proves necessàries en el pijor dels casos, és dir, crear un algoritme de minimisació, i no se supon que es conega la distribució dels elements defectuosos.

L'atra classificació, l'adaptabilitat, es referix a l'informació que pot utilisar-se per a elegir els elements que s'agrupen en una prova. En general, l'elecció de quins elements provar pot dependre dels resultats de proves anteriors, com en el problema de la pera anterior. Un algoritme que realisa una prova i després utilisa el resultat (i tots els resultats anteriors) per a decidir qué prova realisar a continuació es denomina adaptatiu. Pel contrari, en els algoritmes no adaptatius, totes les proves es decidixen de bestreta. Esta idea pot generalisar-se als algoritmes multietapa, en els que les proves es dividixen en etapes, i cada prova de l'etapa següent deu decidir-se de bestreta, en només el coneiximent dels resultats de les proves de les etapes anteriors. Encara que els algoritmes adaptatius oferixen molta més llibertat en el disseny, se sap que els algoritmes adaptatius de proves en grup no milloren als no adaptatius en més d'un factor constant en el número de proves necessàries per a identificar el conjunt d'elements defectuosos. Ademés d'açò, els métodos no adaptatius solen ser útils en la pràctica perque es pot procedir en proves successives sense analisar primer els resultats de totes les proves anteriors, lo que permet distribuir eficaçment el procés de proves.

Variacions i ampliacions

Hi ha moltes formes d'ampliar el problema de les proves de grup. Una de les més importants es denomina proves en grup sorolloses, i aborda un gran supost del problema original: que les proves no contenen errors. Un problema de proves en grup es denomina sorollós quan existix alguna possibilitat de que el resultat d'una prova en grup siga erròneu (per eixemple, que ixca positiu quan la prova no contenia cap defecte). El model de soroll Bernoulli assumix que esta provabilitat és una constant, 𝑞, pero en general pot dependre de l'número real de defectuosos en la prova i del número d'elements provats. Per eixemple, l'efecte de la dilució pot modelar-se dient que un resultat positiu és més provable quan hi ha més defectuosos (o més defectuosos com a fracció del número provat), presents en la prova. Un algoritme sorollós sempre tindrà una provabilitat distinta de zero de cometre un error (és dir, etiquetar mal un element).

Les proves de grup poden ampliar-se considerant escenaris en els que hi ha més de dos resultats possibles d'una prova. Per eixemple, una prova pot tindre els resultats $0,1$ i $2^{+}$, corresponents a que no hi haja cap defectuós, un únic defectuós o un número desconegut de defectuosos major que un. En térmens més generals, és possible considerar que el conjunt de resultats d'una prova és $0,1,\dots ,k^{+}$per a algun $k\in \mathbb{N}$

Una atra extensió consistix en considerar restriccions geomètriques sobre els conjunts que poden sometre's a prova. El problema de la pera és un eixemple d'este tipo de restricció: només es poden provar les peres que apareixen consecutivament. De la mateixa manera, els elements poden dispondre's en un círcul o, en general, en una ret, a on les proves són camins disponibles en el grafo. Un atre tipo de restricció geomètrica seria el número màxim d'elements que poden provar-se en un grup,[a] o que el tamany dels grups siga parell, etcétera. De forma similar, pot ser útil considerar la restricció de que un element determinat només puga aparéixer en un número determinat de proves.

Hi ha infinites formes de seguir remezclando la fòrmula bàsica de les proves de grup. Les següents elaboració donaran una idea d'algunes de les variants més exòtiques. En el model "bo-mediocre-mal", cada element és "bo", "mediocre" o “mal”, i el resultat d'una prova és el tipo de el "pijor" element del grup. En les proves de grup en llindar, el resultat d'una prova és positiu si el número d'elements defectuosos del grup és superior a algun valor llindar o proporció. Les proves de grup en inhibidors són una variant en aplicacions en biologia molecular. En este cas, existix una tercera classe d'elements denominats inhibidors, i el resultat d'una prova és positiu si conté a lo manco un element defectuós i cap inhibidor.

Història i desenrolle

Invenció i primers alvanços

Robert Dorfman va introduir per primera volta el concepte de les proves de grup en 1943 en un breu informe publicat en la secció de notes de Annals of Mathematical Statistics[b]. L'informe de Dorfman, de la mateixa manera que tots els primers treballs sobre proves de grup, se centrava en el problema provabilístic i pretenia utilisar la nova idea de les proves de grup per a reduir el número previst de proves necessàries per a eliminar a tots els sifilíticos d'un grup determinat de soldats. El método era senzill: dividir als soldats en grups d'un tamany determinat i realisar proves individuals (proves en grups d'un tamany) en els grups positius per a averiguar quins estaven infectats. Dorfman tabuló els tamanys de grup òptims per a esta estratègia en funció de la taxa de prevalença de la defectuosidad en la població. Stephen Samuels va trobar una solució de forma tancada per al tamany de grup òptim en funció de la taxa de prevalença.

Despuix de 1943, les proves de grup varen permanéixer pràcticament intactes durant varis anys. En 1957, Sterrett va introduir una millora en el procediment de Dorfman. Este nou procés comença realisant de nou proves individuals en els grups positius, pero es deté en quant s'identifica un defecte. A continuació, els demés elements del grup es proven junts, ya que és molt provable que cap d'ells siga defectuós.

El primer tractament exhaustiu de les proves de grup ho varen realisar Sobel i Groll en el seu artícul de 1959 sobre el tema, en el que descrivien cinc nous procediments -ademés de generalisacions per a quan es desconeix la taxa de prevalença- i, per a l'òptim, proporcionaven una fòrmula explícita del número previst de proves que utilisaria. En l'artícul també s'establix per primera volta la conexió entre les proves de grup i la teoria de l'informació, ademés d'analisar vàries generalisacions del problema de les proves de grup i proporcionar algunes aplicacions noves de la teoria.

El resultat fonamental de Peter Ungar en 1960 mostra que si la taxa de prevalença $p>p_u=(3-\sqrt{5})/2\approx 0.38$, llavors la prova individual és el procediment de prova de grup òptim sobre el número esperat de proves, i si p$p<p_u$, llavors no és òptim. No obstant, és important senyalar que, a pesar de 80 anys d'esforços d'investigació, el procediment òptim encara es desconeix per a p$p<p_u$ i un tamany de població general n $n>2$

Proves combinatòries de grup

Les proves de grup varen ser estudiades per primera volta en el context combinatori per Li en 1962, en l'introducció de l'algoritme d'Li 𝑠-stage. Li va propondre una extensió de el "algoritme de 2 etapes" de Dorfman a un número arbitrari d'etapes que requerien no més de $t=\frac{e}{{\log }_2(e)}d{\log }_2(n)$ proves per a garantisar trobar 𝑑 o menys defectuosos entre 𝑛 elements. L'idea era eliminar tots els ítems en proves negatives, i dividir els ítems restants en grups com es va fer en el pool inicial. Açò devia fer-se 𝑠-1 voltes abans de realisar les proves individuals.

Les proves combinatòries de grup en general varen ser estudiades més a fondo per Katona en 1973. Katona va introduir la representació matricial de les proves de grup no adaptatives i va elaborar un procediment per a trobar els defectuosos en el cas 1-defectuós no adaptatiu en no més de $t=\lceil {\log }_2(n)\rceil$proves, que també va demostrar ser òptim.

En general, és difícil trobar algoritmes òptims per a la prova combinatòria adaptativa de grups i, encara que no s'ha determinat la complexitat computacional de la prova de grups, se sospita que és difícil en alguna classe de complexitat. No obstant, en 1972 es va produir un alvanç important, en l'introducció de l'algoritme de divisió binaria generalisada. L'algoritme de divisió binaria generalisada funciona realisant una busca binaria en els grups que donen positiu i és un algoritme senzill que troba un únic defectuós en un número de proves no superior al llímit inferior d'informació.

En situacions en les que hi ha dos o més defectuosos, l'algoritme de divisió binaria generalisada seguix produint resultats casi òptims, requerint com a màxim 𝑑-1 proves per damunt del llímit inferior d'informació, a on 𝑑 és el número de defectuosos. Allemann va realisar millores considerables en 2013, conseguint que el número de proves necessàries fora inferior a $0.187d+0.5{\log }_2(d)+5.5$ per damunt del llímit inferior d'informació quan n$n/d\ge 38$i $d\ge 10$. Açò es va conseguir canviant la busca binaria en l'algoritme de divisió binaria per un conjunt complex de subalgoritmos en grups de proves superposts. D'esta manera, el problema de la prova combinatòria adaptativa de grups -en un número conegut o un llímit superior en el número de defectuosos- ha quedat essencialment resolt, en poc marge per a noves millores.

Queda oberta la qüestió de quàn les proves individuals són mínimes. Hu, Hwang i Wang varen demostrar en 1981 que la prova individual és minima quan $0.187d+0.5{\log }_2(d)+5.5$, i que no és minima quan $n/d\ge 38$. Actualment es conjectura que este llímit és agut: és dir, la prova individual és minmax si i només si $n\le \lfloor (5d+1)/2\rfloor$.[c] En 2000 Riccio i Colbourn varen fer alguns progressos, demostrant que para grans 𝑛, la prova individual és minmax quan d$d\ge n/{\log }_{3/2}(3)\approx 0.369n$.

Proves no adaptatives i provabilístiques

Una de les idees clau de les proves de grup no adaptatives és que es poden obtindre beneficis significatius eliminant el requisit de que el procediment de prova de grup tinga un èxit segur (el problema "combinatori"), sino permetent que tinga una provabilitat baixa pero no nula d'etiquetar mal cada element (el problema "provabilístic"). Se sap que, a mida que el número d'elements defectuosos s'aproxima al número total d'elements, les solucions combinatòries exactes requerixen moltes més proves que les solucions provabilístiques, i inclús les solucions provabilístiques solament permeten una provabilitat d'error asintóticamente menuda.

En esta llínea, Chan et al. (2011) varen introduir COMP, un algoritme provabilístic que no requerix més de $t=ed(1+\delta )\ln (n)$ proves per a trobar fins a $d$ defectuosos en $n$ elements en una provabilitat d'error no superior a n$n^{-\delta }$. Açò està dins d'un factor constant del llímit inferior de $t=O(d{\log }_{2}n)$.

Chan et al. (2011) també varen proporcionar una generalisació de COMP a un model sorollós simple, i de manera similar varen produir un llímit de rendiment explícit, que era de nou només una constant (depenent de la provabilitat d'una prova fallanca) per damunt del llímit inferior corresponent. En general, el número de proves necessàries en el cas de soroll Bernoulli és un factor constant major que en el cas sense soroll.

Aldridge, Baldassini i Johnson (2014) varen produir una extensió de l'algoritme COMP que afegia passos adicionals de posprocesamiento. Varen demostrar que el rendiment d'este nou algoritme, denominat DD, supera estrictament a el de COMP, i que DD és "essencialment òptim" en escenaris en els que $d^2\ge n$, comparant-ho en un algoritme hipotètic que definix un òptim raonable. El rendiment d'este algoritme hipotètic sugerix que hi ha marge de millora quan $d^2<n$, ademés de sugerir quànt podria millorar.

Vore també

• Problema de les dotze monedes

Bibliografia

• Ding-Zhu, Du; Hwang, Frank K. (1993). Combinatorial group testing and its applications. Singapore: 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. World Scientific. ISBN 9789814477864.
• Aldridge, M.; Johnson, O.; Scarlett, J. (2019). "Group Testing: An Information Theory Perspective" (PDF). Foundations and Trends in Communications and Information Theory. 15 (3–4): 196–392. doi:10.1561/0100000099. S2CID 62841593.
• Porat, E.; Rothschild, A. (2011). "Explicit nonadaptive combinatorial group testing schemes". IEEE Transactions on Information Theory. 57 (12): 7982–89. arXiv:0712.3876. doi:10.1109/TIT.2011.2163296. S2CID 8815474.

• Kagan, Eugene; Ben-gal, Irad (2014), "A group testing algorithm with online informational learning", IIE Transactions, 46 (2): 164–184, doi:10.1080/0740817X.2013.803639, ISSN 0740-817X, S2CID 18588494