Pruebas grupales

Existen dos clasificaciones independientes para los problemas de pruebas grupales; cada problema de prueba grupal es adaptativo o no adaptativo, y probabilístico o combinatorio. ^{[ 3 ]}

En los modelos probabilísticos, se supone que los artículos defectuosos siguen una distribución de probabilidad determinada y el objetivo es minimizar el número esperado de pruebas necesarias para identificar la defectuosidad de cada artículo. Por otro lado, con las pruebas de grupo combinatorias, el objetivo es minimizar el número de pruebas necesarias en el "peor escenario posible" —es decir, crear un algoritmo minmax— y no se presupone ningún conocimiento de la distribución de los artículos defectuosos. ^{[ 3 ]}

La otra clasificación, la adaptabilidad, se refiere a la información que se puede utilizar al elegir qué elementos agrupar en una prueba. En general, la elección de los elementos a probar puede depender de los resultados de pruebas anteriores, como en el problema de la bombilla mencionado anteriormente. Un algoritmo que procede realizando una prueba y luego utilizando el resultado (y todos los resultados anteriores) para decidir qué prueba realizar a continuación se denomina adaptativo. Por el contrario, en los algoritmos no adaptativos, todas las pruebas se deciden de antemano. Esta idea se puede generalizar a algoritmos multietapa, donde las pruebas se dividen en etapas y cada prueba en la siguiente etapa debe decidirse de antemano, conociendo únicamente los resultados de las pruebas en etapas anteriores. Si bien los algoritmos adaptativos ofrecen mucha más libertad en el diseño, se sabe que los algoritmos adaptativos de pruebas grupales no mejoran a los no adaptativos más que un factor constante en el número de pruebas necesarias para identificar el conjunto de elementos defectuosos. ^{[ 4 ] [ 3 ]} Además, los métodos no adaptativos suelen ser útiles en la práctica porque se pueden realizar pruebas sucesivas sin analizar primero los resultados de todas las pruebas anteriores, lo que permite una distribución eficaz del proceso de prueba. ^{[ 5 ]}

Hay muchas maneras de extender el problema de las pruebas grupales. Una de las más importantes se llama prueba grupal ruidosa y aborda una suposición importante del problema original: que la prueba está libre de errores. Un problema de prueba grupal se llama ruidoso cuando hay alguna posibilidad de que el resultado de una prueba grupal sea erróneo (por ejemplo, que dé positivo cuando la prueba no contenía defectuosos). El modelo de ruido de Bernoulli supone que esta probabilidad es una constante.${\displaystyle q}$, pero en general puede depender del número real de defectuosos en la prueba y del número de elementos probados. ^{[ 6 ]} Por ejemplo, el efecto de dilución puede modelarse diciendo que un resultado positivo es más probable cuando hay más defectuosos (o más defectuosos como fracción del número probado) presentes en la prueba. ^{[ 7 ]} Un algoritmo ruidoso siempre tendrá una probabilidad no nula de cometer un error (es decir, etiquetar incorrectamente un elemento). ^{[ 6 ]}

Las pruebas grupales pueden ampliarse considerando escenarios en los que haya más de dos resultados posibles de una prueba. Por ejemplo, una prueba puede tener los siguientes resultados:${\displaystyle 0,1}$y${\displaystyle 2^{+}}$, lo que corresponde a que no haya defectuosos, un solo defectuoso o un número desconocido de defectuosos mayor que uno. De manera más general, es posible considerar que el conjunto de resultados de una prueba es${\displaystyle {0,1,\ldots ,k^{+}}}$para algunos${\displaystyle k\in \mathbb {N} }$. ^{[ 8 ]}

Otra extensión consiste en considerar restricciones geométricas sobre qué conjuntos pueden ser probados. El problema de la bombilla mencionado anteriormente es un ejemplo de este tipo de restricción: solo se pueden probar las bombillas que aparecen consecutivamente. De manera similar, los elementos pueden estar dispuestos en un círculo o, en general, en una red, donde las pruebas son caminos disponibles en el grafo. Otro tipo de restricción geométrica sería sobre el número máximo de elementos que pueden ser probados en un grupo, ^{[ a ]} o los tamaños de los grupos podrían tener que ser pares, etc. De manera similar, puede ser útil considerar la restricción de que cualquier elemento dado solo puede aparecer en un cierto número de pruebas. ^{[ 8 ]}

Existen innumerables maneras de seguir modificando la fórmula básica de las pruebas grupales. Las siguientes explicaciones ilustran algunas de las variantes más singulares. En el modelo «bueno-mediocre-malo», cada elemento es «bueno», «mediocre» o «malo», y el resultado de la prueba es el tipo del elemento «peor» del grupo. En las pruebas grupales con umbral, el resultado es positivo si el número de elementos defectuosos en el grupo supera un valor o proporción umbral. ^{[ 9 ]} Las pruebas grupales con inhibidores son una variante con aplicaciones en biología molecular. En este caso, existe una tercera clase de elementos denominados inhibidores, y el resultado es positivo si contiene al menos un elemento defectuoso y ningún inhibidor. ^{[ 10 ]}

El concepto de pruebas grupales fue introducido por primera vez por Robert Dorfman en 1943 en un breve informe ^{[ 2 ]} publicado en la sección de Notas de Annals of Mathematical Statistics . ^{[ 8 ] [ b ]} El informe de Dorfman, al igual que todos los primeros trabajos sobre pruebas grupales, se centró en el problema probabilístico y tuvo como objetivo utilizar la novedosa idea de las pruebas grupales para reducir el número esperado de pruebas necesarias para descartar a todos los hombres sifilíticos en un grupo determinado de soldados. El método era simple: colocar a los soldados en grupos de un tamaño determinado y utilizar pruebas individuales (pruebas de elementos en grupos de tamaño uno) en los grupos positivos para encontrar cuáles estaban infectados. Dorfman tabuló los tamaños de grupo óptimos para esta estrategia en función de la tasa de prevalencia de la deficiencia en la población. ^{[ 2 ]} Stephen Samuels encontró una solución de forma cerrada para el tamaño de grupo óptimo en función de la tasa de prevalencia. ^{[ 12 ]}

Después de 1943, las pruebas grupales permanecieron prácticamente sin cambios durante varios años. Luego, en 1957, Sterrett introdujo una mejora al procedimiento de Dorfman. Este nuevo proceso comienza realizando nuevamente pruebas individuales en los grupos positivos, pero deteniéndose tan pronto como se identifica un elemento defectuoso. Luego, los elementos restantes del grupo se prueban juntos, ya que es muy probable que ninguno de ellos sea defectuoso. ^{[ 13 ]}

El primer análisis exhaustivo de las pruebas grupales fue realizado por Sobel y Groll en su artículo fundamental de 1959 sobre el tema. Describieron cinco nuevos procedimientos —además de generalizaciones para casos donde se desconoce la tasa de prevalencia— y, para el óptimo, proporcionaron una fórmula explícita para el número esperado de pruebas que requeriría. El artículo también estableció por primera vez la conexión entre las pruebas grupales y la teoría de la información , además de analizar varias generalizaciones del problema de las pruebas grupales y ofrecer algunas aplicaciones nuevas de la teoría. ^{[ 14 ]}

El resultado fundamental de Peter Ungar en 1960 muestra que si la tasa de prevalencia${\displaystyle p>p_{u}}$, dónde${\displaystyle p_{u}=(3-{\sqrt {5}})/2\approx 0.38}$, entonces la prueba individual es el procedimiento óptimo de prueba grupal con respecto al número esperado de pruebas, y si${\displaystyle p<p_{u}}$, entonces no es óptimo. Sin embargo, es importante señalar que a pesar de 80 años de esfuerzo de investigación, el procedimiento óptimo aún se desconoce para${\displaystyle p<p_{u}}$y un tamaño de población general${\displaystyle n>2}$. ^{[ 15 ]}

Las pruebas de grupo fueron estudiadas por primera vez en el contexto combinatorio por Li en 1962, ^{[ 16 ]} con la introducción de la de Li.${\displaystyle s}$algoritmo de -etapa . ^{[ 8 ]} Li propuso una extensión del 'algoritmo de 2 etapas' de Dorfman a un número arbitrario de etapas que no requería más de${\textstyle t={\frac {e}{\log _{2}(e)}}d\log _{2}(n)}$pruebas que se garantizan para encontrar${\displaystyle d}$o menos defectuosos entre${\displaystyle n}$elementos. La idea era eliminar todos los elementos con resultados negativos en las pruebas y dividir los elementos restantes en grupos, como se hizo con el conjunto inicial. Esto se iba a hacer${\displaystyle s-1}$veces antes de realizar pruebas individuales. ^{[ 16 ]}

Las pruebas de grupo combinatorias en general fueron estudiadas más a fondo por Katona en 1973. Katona introdujo la representación matricial de las pruebas de grupo no adaptativas y desarrolló un procedimiento para encontrar el defectuoso en el caso no adaptativo de 1-defectuoso en no más de${\displaystyle t=\lceil \log _{2}(n)\rceil }$pruebas, que también demostró que eran óptimas. ^{[ 17 ]}

En general, encontrar algoritmos óptimos para pruebas grupales combinatorias adaptativas es difícil, y aunque no se ha determinado la complejidad computacional de las pruebas grupales, se sospecha que es difícil en alguna clase de complejidad . ^{[ 8 ]} Sin embargo, en 1972 se produjo un avance importante con la introducción del algoritmo generalizado de división binaria . Este algoritmo funciona realizando una búsqueda binaria en grupos que dan positivo en las pruebas, y es un algoritmo simple que encuentra un único defectuoso en no más del número de pruebas que el límite inferior de información . ^{[ 18 ]}

En escenarios donde hay dos o más defectuosos, el algoritmo generalizado de división binaria aún produce resultados casi óptimos, requiriendo como máximo${\displaystyle d-1}$pruebas por encima del límite inferior de información donde${\displaystyle d}$es el número de defectuosos. ^{[ 18 ]} Allemann realizó mejoras considerables en esto en 2013, logrando que el número requerido de pruebas fuera menor que${\displaystyle 0.187d+0.5\log _{2}(d)+5.5}$por encima del límite inferior de información cuando${\displaystyle n/d\geq 38}$y${\displaystyle d\geq 10}$Esto se logró cambiando la búsqueda binaria en el algoritmo de división binaria a un conjunto complejo de subalgoritmos con grupos de prueba superpuestos. De esta manera, el problema de las pruebas de grupo combinatorias adaptativas —con un número conocido o un límite superior en el número de defectuosos— se ha resuelto esencialmente, con poco margen para futuras mejoras. ^{[ 19 ]}

Existe una cuestión abierta sobre cuándo las pruebas individuales son minmax . Hu, Hwang y Wang demostraron en 1981 que las pruebas individuales son minmax cuando${\displaystyle n\leq \lfloor (5d+1)/2\rfloor }$y que no es minmax cuando${\displaystyle n>3d}$. ^{[ 20 ]} Actualmente se conjetura que este límite es preciso: es decir, la prueba individual es minmax si y solo si${\displaystyle n\leq 3d}$. ^{[ 21 ] [ c ]} En 2000, Riccio y Colbourn lograron algunos avances al demostrar que para grandes${\displaystyle n}$, la prueba individual es minmax cuando${\displaystyle d\geq n/\log _{3/2}(3)\approx 0.369n}$. ^{[ 22 ]}

Una de las ideas clave en las pruebas grupales no adaptativas es que se pueden lograr avances significativos eliminando el requisito de que el procedimiento de prueba grupal tenga éxito garantizado (el problema "combinatorio"), y en cambio permitiéndole tener una probabilidad baja pero no nula de etiquetar erróneamente cada elemento (el problema "probabilístico"). Se sabe que a medida que el número de elementos defectuosos se acerca al número total de elementos, las soluciones combinatorias exactas requieren significativamente más pruebas que las soluciones probabilísticas, incluso cuando estas últimas permiten solo una probabilidad de error asintóticamente pequeña. ^{[ 4 ] [ d ]}

En este sentido, Chan et al. (2011) introdujeron COMP , un algoritmo probabilístico que no requiere más que${\displaystyle t=ed(1+\delta )\ln(n)}$pruebas para encontrar hasta${\displaystyle d}$defectuosos en${\displaystyle n}$elementos con una probabilidad de error no mayor que${\displaystyle n^{-\delta }}$. ^{[ 6 ]} Esto está dentro de un factor constante de la${\displaystyle t=O(d\log _{2}n)}$límite inferior. ^{[ 4 ]}

Chan et al. (2011) también proporcionaron una generalización de COMP a un modelo ruidoso simple y, de manera similar, produjeron un límite de rendimiento explícito, que nuevamente era solo una constante (dependiente de la probabilidad de una prueba fallida) por encima del límite inferior correspondiente. ^{[ 4 ] [ 6 ]} En general, el número de pruebas requeridas en el caso de ruido de Bernoulli es un factor constante mayor que en el caso sin ruido. ^{[ 6 ]}

Aldridge, Baldassini y Johnson (2014) produjeron una extensión del algoritmo COMP que agregó pasos de posprocesamiento adicionales. ^{[ 23 ]} Demostraron que el rendimiento de este nuevo algoritmo, llamado DD , supera estrictamente el de COMP, y que DD es "esencialmente óptimo" en escenarios donde${\displaystyle d^{2}\geq n}$, comparándolo con un algoritmo hipotético que define un óptimo razonable. El rendimiento de este algoritmo hipotético sugiere que hay margen de mejora cuando${\displaystyle d^{2}<n}$, además de sugerir cuánto podría mejorar esto. ^{[ 23 ]}

Dado que siempre es posible recurrir a pruebas individuales mediante la configuración${\displaystyle S_{j}=\{j\}}$para cada${\displaystyle 1\leq j\leq n}$, debe ser que eso${\displaystyle {\bar {t}}(d,n)\leq n}$Además, dado que cualquier procedimiento de prueba no adaptativo puede escribirse como un algoritmo adaptativo simplemente realizando todas las pruebas sin tener en cuenta su resultado,${\displaystyle t(d,n)\leq {\bar {t}}(d,n)}$. Finalmente, cuando${\displaystyle 0\neq d\neq n}$, hay al menos un artículo cuya defectuosidad debe determinarse (mediante al menos una prueba), y por lo tanto${\displaystyle 1\leq t(d,n)}$.

En resumen (al asumir${\displaystyle 0\neq d\neq n}$),${\displaystyle 1\leq t(d,n)\leq {\bar {t}}(d,n)\leq n}$. ^{[ f ]}

Los algoritmos para pruebas grupales no adaptativas constan de dos fases distintas. Primero, se decide cuántas pruebas realizar y qué elementos incluir en cada una. En la segunda fase, a menudo denominada etapa de decodificación, se analizan los resultados de cada prueba grupal para determinar qué elementos tienen más probabilidades de ser defectuosos. La primera fase se suele codificar en una matriz como se muestra a continuación. ^{[ 6 ]}

• Supongamos un procedimiento de prueba de grupo no adaptativo para${\displaystyle n}$Los elementos consisten en las pruebas${\displaystyle S_{1},S_{2},\dots ,S_{t}}$para algunos${\displaystyle t\in \mathbb {N} _{\geq 0}}$. La matriz de pruebas para este esquema es la${\displaystyle t\times n}$matriz binaria,${\displaystyle M}$, dónde${\displaystyle (M)_{ij}=1}$si y solo si${\displaystyle j\in S_{i}}$(y es cero en caso contrario).

Así, cada columna de${\displaystyle M}$representa un elemento y cada fila representa una prueba, con un${\displaystyle 1}$en el${\displaystyle (i,j){\textrm {-th}}}$entrada que indica que el${\displaystyle i{\textrm {-th}}}$La prueba incluyó la${\displaystyle j{\textrm {-th}}}$artículo y un${\displaystyle 0}$indicando lo contrario.

Además del vector${\displaystyle \mathbf {x} }$(de longitud${\displaystyle n}$) que describe el conjunto defectuoso desconocido, es común introducir el vector de resultados, que describe los resultados de cada prueba.

• Dejar${\displaystyle t}$sea ​​el número de pruebas realizadas por un algoritmo no adaptativo. El vector de resultados ,${\displaystyle \mathbf {y} =(y_{1},y_{2},\dots ,y_{t})}$, es un vector binario de longitud${\displaystyle t}$(eso es,${\displaystyle \mathbf {y} \in \{0,1\}^{t}}$) tal que${\displaystyle y_{i}=1}$si y solo si el resultado de la${\displaystyle i{\textrm {-th}}}$La prueba fue positiva (es decir, contenía al menos un defectuoso). ^{[ g ]}

Con estas definiciones, el problema no adaptativo puede reformularse de la siguiente manera: primero se elige una matriz de prueba,${\displaystyle M}$, después de lo cual el vector${\displaystyle \mathbf {y} }$se devuelve. Entonces el problema es analizar${\displaystyle \mathbf {y} }$para encontrar alguna estimación de${\displaystyle \mathbf {x} }$.

En el caso ruidoso más simple, donde hay una probabilidad constante,${\displaystyle q}$, que una prueba grupal tendrá un resultado erróneo, se considera un vector binario aleatorio,${\displaystyle \mathbf {v} }$donde cada entrada tiene una probabilidad${\displaystyle q}$de ser${\displaystyle 1}$y es${\displaystyle 0}$de lo contrario. El vector que se devuelve es entonces${\displaystyle {\hat {\mathbf {y} }}=\mathbf {y} +\mathbf {v} }$, con la adición habitual en${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$(equivalentemente, esta es la operación XOR elemento a elemento ). Un algoritmo ruidoso debe estimar${\displaystyle \mathbf {x} }$usando${\displaystyle {\hat {\mathbf {y} }}}$(es decir, sin conocimiento directo de${\displaystyle \mathbf {y} }$). ^{[ 6 ]}

La representación matricial permite demostrar algunos límites en las pruebas grupales no adaptativas. El enfoque refleja el de muchos diseños deterministas, donde${\displaystyle d}$Se consideran matrices separables, tal como se define a continuación. ^{[ 8 ]}

• Una matriz binaria,${\displaystyle M}$, se llama${\displaystyle d}$-separable si cada suma booleana (OR lógico) de cualquier${\displaystyle d}$de sus columnas es distinto. Además, la notación${\displaystyle {\bar {d}}}$-separable indica que cada suma de cualquiera de hasta${\displaystyle d}$de${\displaystyle M}$Las columnas de 's son distintas. (Esto no es lo mismo que${\displaystyle M}$ser${\displaystyle k}$-separable para cada${\displaystyle k\leq d}$.)

Cuando${\displaystyle M}$es una matriz de prueba, la propiedad de ser${\displaystyle d}$-separable (${\displaystyle {\bar {d}}}$-separable) es equivalente a poder distinguir entre (hasta)${\displaystyle d}$defectuosos. Sin embargo, esto no garantiza que sea sencillo. Una propiedad más fuerte, llamada disyunción, sí lo garantiza.

• Una matriz binaria,${\displaystyle M}$se llama${\displaystyle d}$-disyunto si la suma booleana de cualquier${\displaystyle d}$Una columna no contiene ninguna otra columna. (En este contexto, se dice que una columna A contiene una columna B si para cada índice donde B tiene un 1, A también tiene un 1).

Una propiedad útil de${\displaystyle d}$-las matrices de prueba disjuntas son que, con hasta${\displaystyle d}$En el caso de los artículos defectuosos, cada artículo no defectuoso aparecerá en al menos una prueba cuyo resultado sea negativo. Esto significa que existe un procedimiento sencillo para encontrar los defectuosos: basta con retirar todos los artículos que den negativo en una prueba.

Utilizando las propiedades de${\displaystyle d}$-separable y${\displaystyle d}$-matrices disjuntas lo siguiente se puede demostrar para el problema de identificación${\displaystyle d}$defectuosos entre${\displaystyle n}$Artículos totales. ^{[ 4 ]}

1. El número de pruebas necesarias para una probabilidad de error promedio asintóticamente pequeña aumenta como${\displaystyle O(d\log _{2}n)}$.
2. El número de pruebas necesarias para una probabilidad máxima de error asintóticamente pequeña se escala como${\displaystyle O(d^{2}\log _{2}n)}$.
3. El número de pruebas necesarias para una probabilidad de error cero se escala como${\displaystyle O\left({\frac {d^{2}\log _{2}n}{\log _{2}d}}\right)}$.

El algoritmo Combinatorial Orthogonal Matching Pursuit , o COMP, es un algoritmo sencillo de prueba de grupos no adaptativo que constituye la base de los algoritmos más complejos que se describen a continuación en esta sección.

Primero, cada entrada de la matriz de prueba se elige iid para ser${\displaystyle 1}$con probabilidad${\displaystyle 1/d}$y${\displaystyle 0}$de lo contrario.

El paso de decodificación procede columna por columna (es decir, por elemento). Si cada prueba en la que aparece un elemento es positiva, entonces el elemento se declara defectuoso; de lo contrario, se asume que el elemento no es defectuoso. O equivalentemente, si un elemento aparece en alguna prueba cuyo resultado es negativo, el elemento se declara no defectuoso; de lo contrario, se asume que el elemento es defectuoso. Una propiedad importante de este algoritmo es que nunca crea falsos negativos , aunque se produce un falso positivo cuando todas las ubicaciones con unos en la j -ésima columna de${\displaystyle M}$(que corresponden a un artículo no defectuoso j ) están "ocultos" por los de otras columnas que corresponden a artículos defectuosos.

El algoritmo COMP no requiere más que${\displaystyle ed(1+\delta )\ln(n)}$pruebas para tener una probabilidad de error menor o igual a${\displaystyle n^{-\delta }}$. ^{[ 6 ]} Esto está dentro de un factor constante del límite inferior para la probabilidad promedio de error anterior.

En el caso ruidoso, se relaja el requisito en el algoritmo COMP original de que el conjunto de ubicaciones de unos en cualquier columna de${\displaystyle M}$correspondiente a un elemento positivo estar completamente contenido en el conjunto de ubicaciones de unos en el vector de resultados. En cambio, se permite un cierto número de “desajustes”: este número de desajustes depende tanto del número de unos en cada columna como del parámetro de ruido.${\displaystyle q}$Este algoritmo COMP ruidoso no requiere más que${\displaystyle 4.36({\sqrt {\delta }}+{\sqrt {1+\delta }})^{2}(1-2q)^{-2}d\log _{2}{n}}$pruebas para lograr una probabilidad de error como máximo${\displaystyle n^{-\delta }}$. ^{[ 6 ]}

El método de defectuosos definidos (DD) es una extensión del algoritmo COMP que intenta eliminar cualquier falso positivo. Se ha demostrado que las garantías de rendimiento de DD superan con creces las de COMP. ^{[ 23 ]}

El paso de decodificación utiliza una propiedad útil del algoritmo COMP: que cada elemento que COMP declara como no defectuoso ciertamente no lo es (es decir, no hay falsos negativos). Procede de la siguiente manera.

1. Primero se ejecuta el algoritmo COMP y se eliminan los artículos que no presentan defectos. Todos los artículos restantes se consideran "posiblemente defectuosos".
2. A continuación, el algoritmo analiza todas las pruebas positivas. Si un elemento aparece como el único "posible defectuoso" en una prueba, entonces debe ser defectuoso, por lo que el algoritmo lo declara defectuoso.
3. Se supone que todos los demás artículos no presentan defectos. La justificación de este último paso radica en la suposición de que el número de artículos defectuosos es mucho menor que el número total de artículos.

Cabe destacar que los pasos 1 y 2 nunca cometen errores, por lo que el algoritmo solo puede equivocarse si declara que un artículo defectuoso no lo es. Por lo tanto, el algoritmo DD solo puede generar falsos negativos.

SCOMP (Sequential COMP) es un algoritmo que utiliza el hecho de que DD no comete errores hasta el último paso, donde se supone que los elementos restantes no son defectuosos. Sea el conjunto de elementos declarados defectuosos.${\displaystyle K}$Una prueba positiva se llama explicada por${\displaystyle K}$si contiene al menos un elemento en${\displaystyle K}$La observación clave con SCOMP es que el conjunto de defectos encontrados por DD puede no explicar todas las pruebas positivas, y que cada prueba inexplicable debe contener un defecto oculto.

El algoritmo procede de la siguiente manera.

1. Realice los pasos 1 y 2 del algoritmo DD para obtener${\displaystyle K}$, una estimación inicial para el conjunto de defectuosos.
2. Si${\displaystyle K}$Explica cada prueba positiva, finaliza el algoritmo:${\displaystyle K}$es la estimación final para el conjunto de defectuosos.
3. Si hay alguna prueba inexplicada, encuentre el "posible defectuoso" que aparece en la mayor cantidad de pruebas inexplicadas y declárelo como defectuoso (es decir, agréguelo al conjunto).${\displaystyle K}$). Vaya al paso 2.

En simulaciones, se ha demostrado que SCOMP tiene un rendimiento casi óptimo. ^{[ 23 ]}

Polynomial Pools (PP) es un algoritmo determinista que garantiza identificar con exactitud hasta${\displaystyle d}$positivos. ^{[ 26 ]} El algoritmo es para la construcción de la matriz de agrupación${\displaystyle M}$, que se puede utilizar directamente para decodificar las observaciones en${\displaystyle y}$. De forma similar a COMP, una muestra se decodifica según la relación: ${\displaystyle x_{i}=1~~{\text{ if }}~~M(:,i)~.*~y=M(:,i)}$, dónde${\displaystyle .*}$representa la multiplicación elemento a elemento y${\displaystyle M(:,i)}$es el${\displaystyle i}$columna de${\displaystyle M}$. Dado que el paso de decodificación no es difícil, PP está especializado en generar${\displaystyle M}$.

Formación de grupos

Un grupo/piscina${\displaystyle \ell }$Se genera utilizando una relación polinómica que especifica los índices de las muestras contenidas en cada grupo. Un conjunto de parámetros de entrada determina el algoritmo. Para un número primo${\displaystyle p>1}$y un número entero${\displaystyle n\geq 1}$cualquier potencia prima se define por${\displaystyle q=p^{n}}$. Para un parámetro de dimensión${\displaystyle c\geq 2}$El número total de muestras es${\displaystyle n=q^{c}}$y el número de muestras por grupo es${\displaystyle q^{c-1}}$. Además, el campo finito de orden${\displaystyle q}$se denota por${\displaystyle \mathbb {F} _{q}}$ (es decir, los números enteros)${\displaystyle \{0,1,2,\ldots ,q-1\}}$definido por operaciones aritméticas especiales que aseguran que la suma y la multiplicación en${\displaystyle \mathbb {F} _{q}}$permanece en${\displaystyle \mathbb {F} _{q}}$). El método dispone cada muestra en una cuadrícula y la representa mediante coordenadas${\displaystyle x=(u,v)}$Las coordenadas se calculan según una relación polinómica utilizando los números enteros. ${\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}.}$

La combinación de recorrer el bucle${\displaystyle u_{i_{l}}}$los valores están representados por un conjunto con${\displaystyle q^{c-1}}$elementos de una secuencia de${\displaystyle d-1}$números enteros, es decir, ${\displaystyle u_{i_{1}}\times \cdots \times u_{i_{c-1}}=\{(i_{1},\ldots ,i_{c-1})\}}$, dónde ${\displaystyle 0\leq i_{l}\leq q-1}$. Sin pérdida de generalidad , la combinación es tal que ${\displaystyle i_{d-1}}$ciclos cada${\displaystyle q}$veces,${\displaystyle i_{d-2}}$ciclos cada${\displaystyle q^{2}}$tiempos hasta ${\displaystyle i_{1}}$ciclos solo una vez. Fórmulas que calculan los índices de muestra y, por lo tanto, los grupos correspondientes, para valores fijos${\displaystyle a}$y${\displaystyle b}$, son dados por

${\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}}}$

Los cálculos en${\displaystyle \mathbb {F} _{q}}$se puede implementar con bibliotecas de software disponibles públicamente para campos finitos, cuando${\displaystyle q}$es un poder primordial. Cuando${\displaystyle q}$es un número primo entonces los cálculos en${\displaystyle \mathbb {F} _{q}}$simplificar a aritmética modular, es decir,${\displaystyle v_{u_{i}}=(\sum _{l=1}^{c-1}a^{l}i_{l}+b)~{\text{mod}}~q}$Un ejemplo de cómo generar un pool${\displaystyle \ell }$cuando ${\displaystyle a=1,b=0,c=2}$En la tabla siguiente se muestra la información, mientras que la selección de muestras correspondiente se muestra en la figura superior.

Este método utiliza${\displaystyle q(c-1)(d+1)}$pruebas para identificar con exactitud hasta${\displaystyle d}$aspectos positivos entre${\displaystyle n=q^{c}}$muestras. Debido a esto, PP es particularmente eficaz para tamaños de muestra grandes, ya que el número de pruebas crece solo linealmente con respecto a${\displaystyle c}$mientras que las muestras crecen exponencialmente con este parámetro. Sin embargo, PP también puede ser eficaz para tamaños de muestra pequeños. ^{[ 26 ]}

Un canal de acceso múltiple es un canal de comunicación que conecta a muchos usuarios simultáneamente. Cada usuario puede escuchar y transmitir en el canal, pero si más de un usuario transmite al mismo tiempo, las señales colisionan y se reducen a ruido ininteligible. Los canales de acceso múltiple son importantes para diversas aplicaciones del mundo real, especialmente para redes informáticas inalámbricas y redes telefónicas. ^{[ 32 ]}

Un problema importante con los canales de acceso múltiple es cómo asignar tiempos de transmisión a los usuarios para que sus mensajes no colisionen. Un método simple es dar a cada usuario su propio intervalo de tiempo para transmitir, lo que requiere${\displaystyle n}$ranuras. (Esto se denomina multiplexación por división de tiempo o TDM). Sin embargo, esto es muy ineficiente, ya que asignará ranuras de transmisión a usuarios que quizás no tengan un mensaje, y generalmente se asume que solo unos pocos usuarios querrán transmitir en un momento dado; de lo contrario, un canal de acceso múltiple no sería práctico en primer lugar.

En el contexto de las pruebas grupales, este problema generalmente se aborda dividiendo el tiempo en "épocas" de la siguiente manera. ^{[ 8 ]} Un usuario se considera "activo" si tiene un mensaje al comienzo de una época. (Si se genera un mensaje durante una época, el usuario solo se vuelve activo al comienzo de la siguiente). Una época termina cuando todos los usuarios activos han transmitido con éxito su mensaje. El problema consiste entonces en encontrar a todos los usuarios activos en una época determinada y programar un tiempo para que transmitan (si aún no lo han hecho con éxito). Aquí, una prueba en un conjunto de usuarios corresponde a aquellos usuarios que intentan una transmisión. Los resultados de la prueba son el número de usuarios que intentaron transmitir,${\displaystyle 0,1,}$y${\displaystyle 2^{+}}$, que corresponden respectivamente a ningún usuario activo, exactamente un usuario activo (mensaje exitoso) o más de un usuario activo (colisión de mensajes). Por lo tanto, utilizando un algoritmo de prueba de grupo adaptativo con resultados${\displaystyle \{0,1,2^{+}\}}$Se puede determinar qué usuarios desean transmitir en ese momento. Luego, a cualquier usuario que aún no haya realizado una transmisión exitosa se le puede asignar un espacio para transmitir, evitando así asignar innecesariamente tiempos a usuarios inactivos.

El aprendizaje automático es un campo de la informática con numerosas aplicaciones de software, como la clasificación de ADN, la detección de fraudes y la publicidad dirigida . Uno de los principales subcampos del aprendizaje automático es el problema del "aprendizaje mediante ejemplos", donde la tarea consiste en aproximar una función desconocida a partir de su valor en varios puntos específicos. ^{[ 8 ]} Como se describe en esta sección, este problema de aprendizaje de funciones puede abordarse mediante un enfoque de pruebas grupales.

En una versión simple del problema, hay alguna función desconocida,${\displaystyle f:\{0,1\}^{N}\to \{0,1\}}$dónde${\displaystyle f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}}$, y${\displaystyle {\textbf {a}}\in \{0,1\}^{N}}$(utilizando aritmética lógica: la suma es la operación lógica OR y la multiplicación es la operación lógica AND). Aquí${\displaystyle {\textbf {a}}}$es '${\displaystyle d}$escaso', lo que significa que como máximo${\displaystyle d\ll N}$de sus entradas son${\displaystyle 1}$. El objetivo es construir una aproximación a${\displaystyle f}$usando${\displaystyle t}$evaluaciones de puntos, donde${\displaystyle t}$es lo más pequeño posible. ^{[ 4 ]} (Recuperación exacta${\displaystyle f}$corresponde a algoritmos de error cero, mientras que${\displaystyle f}$(Se aproxima mediante algoritmos que tienen una probabilidad de error distinta de cero).

En este problema, recuperar${\displaystyle f}$es equivalente a encontrar${\displaystyle {\textbf {a}}}$. Además,${\displaystyle f({\textbf {p}})=1}$si y solo si existe algún índice,${\displaystyle n}$, dónde${\displaystyle {\textbf {a}}_{n}={\textbf {p}}_{n}=1}$. Por lo tanto, este problema es análogo a un problema de prueba grupal con${\displaystyle d}$defectuosos y${\displaystyle n}$artículos totales. Las entradas de${\displaystyle {\textbf {a}}}$son los artículos, que son defectuosos si están${\displaystyle 1}$,${\displaystyle {\textbf {p}}}$especifica una prueba, y una prueba es positiva si y solo si${\displaystyle f({\textbf {p}})=1}$. ^{[ 4 ]}

En realidad, a menudo uno estará interesado en funciones más complicadas, como por ejemplo:${\displaystyle f:\mathbb {C} ^{N}\to \mathbb {C} }$, de nuevo donde${\displaystyle f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}}$. La detección comprimida , que está estrechamente relacionada con las pruebas grupales, puede utilizarse para resolver este problema. ^{[ 4 ]}

En la detección comprimida, el objetivo es reconstruir una señal,${\displaystyle {\textbf {v}}\in \mathbb {C} ^{N}}$, tomando una serie de mediciones. Estas mediciones se modelan como el producto escalar de${\displaystyle {\textbf {v}}}$con un vector elegido. ^{[ h ]} El objetivo es utilizar un número pequeño de mediciones, aunque esto normalmente no es posible a menos que se asuma algo sobre la señal. Una de esas suposiciones (que es común ^{[ 35 ] [ 36 ]} ) es que solo un pequeño número de entradas de${\displaystyle {\textbf {v}}}$son significativas , lo que significa que tienen una gran magnitud. Dado que las mediciones son productos escalares de${\displaystyle {\textbf {v}}}$, la ecuación${\displaystyle M{\textbf {v}}={\textbf {q}}}$sostiene, donde${\displaystyle M}$es un${\displaystyle t\times N}$matriz que describe el conjunto de mediciones que se han elegido y${\displaystyle \mathbf {q} }$es el conjunto de resultados de medición. Esta construcción muestra que la detección comprimida es una especie de prueba grupal "continua".

La principal dificultad en la detección comprimida radica en identificar qué entradas son significativas. ^{[ 35 ]} Una vez hecho esto, existen diversos métodos para estimar los valores reales de las entradas. ^{[ 37 ]} Esta tarea de identificación puede abordarse mediante una sencilla aplicación de pruebas de grupo. En este caso, una prueba de grupo produce un número complejo : la suma de las entradas analizadas. El resultado de una prueba se considera positivo si produce un número complejo de gran magnitud, lo que, bajo el supuesto de que las entradas significativas son escasas, indica que al menos una entrada significativa está presente en la prueba.

Existen construcciones deterministas explícitas para este tipo de algoritmo de búsqueda combinatoria , que requieren${\displaystyle d2^{(\log _{2}\log _{2}N)^{O(1)}}}$mediciones. ^{[ 38 ]} Sin embargo, al igual que con las pruebas grupales, estas son subóptimas y las construcciones aleatorias (como COMP) a menudo pueden recuperar${\displaystyle f}$sublinealmente en${\displaystyle N}$. ^{[ 37 ]}

Durante una pandemia como el brote de COVID-19 en 2020, los ensayos de detección de virus a veces se realizan utilizando diseños de pruebas grupales no adaptativos. ^{[ 39 ] [ 40 ] [ 41 ]} Un ejemplo fue proporcionado por el proyecto Origami Assays, que publicó diseños de pruebas grupales de código abierto para ejecutarse en una placa de laboratorio estándar de 96 pocillos. ^{[ 42 ]}

En un entorno de laboratorio, uno de los desafíos de las pruebas grupales es que la preparación de las mezclas puede ser laboriosa y difícil de realizar con precisión a mano. Los ensayos de origami proporcionaron una solución a este problema de preparación al ofrecer plantillas de papel que guían al técnico sobre cómo distribuir las muestras de los pacientes en los pocillos de prueba. ^{[ 43 ]}

Utilizando el diseño de prueba para grupos grandes (XL3), fue posible analizar 1120 muestras de pacientes en 94 pocillos de ensayo. Si la tasa de verdaderos positivos era suficientemente baja, no se requerían pruebas adicionales.

La informática forense es un campo dedicado a encontrar métodos para recopilar evidencia digital de un delito. Estos delitos suelen implicar que un adversario modifique los datos, documentos o bases de datos de una víctima, como por ejemplo la alteración de registros fiscales, un virus que oculta su presencia o un ladrón de identidad que modifica datos personales. ^{[ 31 ]}

Una herramienta común en el análisis forense de datos es la función hash criptográfica unidireccional . Esta función toma los datos y, mediante un procedimiento difícil de revertir, produce un número único llamado hash. ^{[ i ]} Los hashes, que suelen ser mucho más cortos que los datos, permiten comprobar si estos han sido modificados sin tener que almacenar innecesariamente copias completas de la información: el hash de los datos actuales se puede comparar con un hash anterior para determinar si se han producido cambios. Una desventaja de este método es que, si bien es fácil saber si los datos han sido modificados, no hay forma de determinar cómo: es decir, es imposible recuperar qué parte de los datos ha cambiado. ^{[ 31 ]}

Una forma de sortear esta limitación es almacenar más hashes —ahora de subconjuntos de la estructura de datos— para acotar la ubicación del ataque. Sin embargo, para encontrar la ubicación exacta del ataque con un enfoque ingenuo, sería necesario almacenar un hash para cada dato de la estructura, lo que anularía el propósito de los hashes. (Sería mejor almacenar una copia normal de los datos). Las pruebas de grupo pueden utilizarse para reducir drásticamente el número de hashes que deben almacenarse. Una prueba consiste en una comparación entre los hashes almacenados y los actuales, que es positiva cuando hay una discrepancia. Esto indica que al menos un dato editado (que se considera defectuoso en este modelo) está contenido en el grupo que generó el hash actual. ^{[ 31 ]}

De hecho, la cantidad de hashes necesarios es tan baja que, junto con la matriz de prueba a la que hacen referencia, pueden incluso almacenarse dentro de la estructura organizativa de los propios datos. Esto significa que, en lo que respecta a la memoria, la prueba puede realizarse "gratis". (Esto es cierto con la excepción de una clave maestra/contraseña que se utiliza para determinar secretamente la función hash). ^{[ 31 ]}

• Ding-Zhu, Du; Hwang, Frank K. (2000). Pruebas de grupos combinatorios y sus aplicaciones (2.ª  ed.). Singapur: World Scientific. ISBN 978-9810241070.
• Curso de Atri Rudra sobre Códigos Correctores de Errores: Combinatoria, Algoritmos y Aplicaciones (Primavera de 2007), Lección 7 .
• Curso de Atri Rudra sobre Códigos Correctores de Errores: Combinatoria, Algoritmos y Aplicaciones (Primavera de 2010), Lecciones 10 , 11 , 28 , 29
• Du, D.; Hwang, F. (2006). Diseños de agrupamiento y pruebas grupales no adaptativas . World Scientific. ISBN 9789814477864.
• Aldridge, M.; Johnson, O.; Scarlett, J. (2019). "Pruebas grupales: una perspectiva de la teoría de la información" (PDF) . Fundamentos y tendencias en la teoría de la comunicación y la información . 15 ( 3–4 ): 196–392 . arXiv : 1902.06002 . doi : 10.1561/0100000099 . S2CID 62841593 . 
• Porat, E.; Rothschild, A. (2011). "Esquemas explícitos de prueba de grupos combinatorios no adaptativos". IEEE Transactions on Information Theory . 57 (12): 7982– 89. arXiv : 0712.3876 . Bibcode : 2011ITIT...57.7982P . doi : 10.1109/TIT.2011.2163296 . S2CID 8815474 . 
• Kagan, Eugene; Ben-gal, Irad (2014), "Un algoritmo de pruebas grupales con aprendizaje informacional en línea", IIE Transactions , 46 (2): 164–184 , doi : 10.1080/0740817X.2013.803639 , ISSN 0740-817X , S2CID 18588494