Групповое тестирование

Иллюстрация проблемы с лампочкой, где среди шести лампочек ищут сломанную. Здесь первые три подключаются к источнику питания и загораются (А). Это указывает на то, что разбитая лампочка должна быть одной из трех последних (B). Если бы вместо этого лампочки не загорелись, можно было бы быть уверенным, что разбитая лампочка была среди первых трех. Продолжение этой процедуры позволит обнаружить сломанную лампочку не более чем за три проверки по сравнению с максимальным числом шести проверок, если лампы проверяются по отдельности.

В статистике и комбинаторной математике групповое тестирование — это любая процедура, которая разбивает задачу идентификации определенных объектов на тесты по группам элементов, а не по отдельным. Групповое тестирование, впервые изученное Робертом Дорфманом в 1943 году, представляет собой относительно новую область прикладной математики, которая может применяться к широкому спектру практических приложений и сегодня является активной областью исследований.

Знакомый пример группового тестирования включает в себя цепочку последовательно соединенных лампочек, при этом известно, что ровно одна из лампочек перегорела. Цель состоит в том, чтобы найти перегоревшую лампочку, используя наименьшее количество тестов (где тест заключается в том, что некоторые лампочки подключены к источнику питания). Простой подход — проверить каждую лампочку по отдельности. Однако если луковиц много, гораздо эффективнее объединить их в группы. Например, подключив сразу первую половину лампочек, можно определить, в какой половине находится разбитая лампочка, исключив половину лампочек всего за один тест.

Схемы проведения группового тестирования могут быть простыми или сложными, а тесты, используемые на каждом этапе, могут быть разными. Схемы, в которых тесты следующего этапа зависят от результатов предыдущих этапов, называются адаптивными процедурами , а схемы, построенные так, что все тесты известны заранее, — неадаптивными процедурами . Структура схемы тестов, включенных в неадаптивную процедуру, известна как пул-проект .

Групповое тестирование имеет множество применений, включая статистику, биологию, информатику, медицину, инженерию и кибербезопасность. Современный интерес к этим схемам тестирования возродился благодаря проекту «Геном человека» .

Основное описание и условия

В отличие от многих областей математики, истоки группового тестирования можно проследить до одного отчета. написано одним человеком: Робертом Дорфманом . Мотивация возникла во время Второй мировой войны, когда Служба общественного здравоохранения США и Отборочная служба приступили к крупномасштабному проекту по отсеиванию всех мужчин с сифилитом, призванных на вводный курс. Тестирование человека на сифилис включает в себя взятие у него образца крови и последующий анализ этого образца, чтобы определить наличие или отсутствие сифилиса. В то время проведение этого теста было дорогостоящим, а тестирование каждого солдата индивидуально было бы очень дорого и неэффективно.

Предположим, есть $n$ солдат, этот метод тестирования приводит к $n$ отдельные тесты. Если большая часть людей инфицирована, этот метод будет разумным. Однако в более вероятном случае, когда инфицирована лишь очень небольшая часть мужчин, можно реализовать гораздо более эффективную схему тестирования. Возможность более эффективной схемы тестирования зависит от следующего свойства: солдат можно объединить в группы, и в каждой группе можно объединить образцы крови. Затем объединенную пробу можно протестировать, чтобы проверить, болен ли хотя бы один солдат в группе сифилисом. Это основная идея группового тестирования. Если у одного или нескольких солдат в этой группе есть сифилис, то тест бесполезен (необходимо провести больше тестов, чтобы определить, какой солдат(ы) это был). С другой стороны, если ни у кого в группе нет сифилиса, то многие тесты сохраняются, поскольку каждого солдата в этой группе можно исключить с помощью всего лишь одного теста.

Предметы, из-за которых группа получает положительный результат теста, обычно называются дефектными предметами (это разбитые лампочки, сифилитические мужчины и т. д.). Часто общее количество предметов обозначается как $n$ и $d$ представляет количество дефектов, если предполагается, что оно известно.

Классификация задач группового тестирования

Существует две независимые классификации задач группового тестирования; Каждая задача группового тестирования является либо адаптивной, либо неадаптивной, либо вероятностной, либо комбинаторной.

В вероятностных моделях предполагается, что дефектные изделия подчиняются некоторому распределению вероятностей , и цель состоит в том, чтобы минимизировать ожидаемое количество тестов, необходимых для выявления дефектности каждого изделия. С другой стороны, при комбинаторном групповом тестировании цель состоит в том, чтобы минимизировать количество тестов, необходимых в «наихудшем сценарии» (то есть создать алгоритм minmax ), и не предполагается знание распределения дефектов.

Другая классификация, адаптивность, касается того, какую информацию можно использовать при выборе элементов для группировки в тест. В общем, выбор элементов для проверки может зависеть от результатов предыдущих тестов, как в приведенной выше задаче с лампочкой. Алгоритм , который выполняет тест, а затем использует результат (и все прошлые результаты) для принятия решения о том, какой следующий тест выполнить, называется адаптивным. И наоборот, в неадаптивных алгоритмах все тесты решаются заранее. Эту идею можно обобщить на многоэтапные алгоритмы, где тесты разделены на этапы, и каждый тест на следующем этапе должен быть решен заранее, зная только результаты тестов на предыдущих этапах.Хотя адаптивные алгоритмы предлагают гораздо больше свободы в разработке, известно, что адаптивные алгоритмы группового тестирования не улучшают неадаптивные алгоритмы не более чем на постоянный коэффициент количества тестов, необходимых для выявления набора дефектных элементов. В дополнение к этому, неадаптивные методы часто полезны на практике, поскольку можно приступать к последовательным тестам без предварительного анализа результатов всех предыдущих тестов, что позволяет эффективно распределить процесс тестирования.

Вариации и расширения

Есть много способов расширить проблему группового тестирования. Один из наиболее важных из них называется шумным групповым тестированием и основан на большом допущении исходной проблемы: тестирование безошибочно. Задача группового тестирования называется шумной, если существует некоторая вероятность того, что результат группового теста окажется ошибочным (например, окажется положительным, если тест не содержит дефектов). Модель шума Бернулли предполагает, что эта вероятность является некоторой константой: $q$, но в целом это может зависеть от истинного количества бракованных изделий в тесте и количества тестируемых изделий. Например, эффект разбавления можно смоделировать, сказав, что положительный результат более вероятен, когда в тесте присутствует больше дефектов (или больше дефектов в процентах от числа протестированных). Зашумленный алгоритм всегда будет иметь ненулевую вероятность допустить ошибку (то есть неправильно маркировать элемент).

Групповое тестирование можно расширить, рассмотрев сценарии, в которых существует более двух возможных результатов теста. Например, тест может иметь результаты $0,1$ и $2^{+}$, что соответствует отсутствию дефектов, одному дефекту или неизвестному количеству дефектов, превышающему один. В более общем смысле можно рассматривать набор результатов теста как ${0,1,\ldots ,k^{+}}$ для некоторых $k\in \mathbb {N}$.

Еще одним расширением является рассмотрение геометрических ограничений на то, какие множества можно тестировать. Приведенная выше задача с лампочками является примером такого рода ограничений: можно проверять только лампочки, которые появляются последовательно. Аналогичным образом элементы могут быть расположены по кругу или вообще по сети, где тесты представляют собой доступные пути на графе. Другой вид геометрического ограничения касается максимального количества элементов, которые можно протестировать в группе. или размеры групп могут быть четными и так далее. Подобным образом может быть полезно рассмотреть ограничение, согласно которому любой заданный элемент может появляться только в определенном количестве тестов.

Существует бесконечное множество способов продолжать изменять базовую формулу группового тестирования. Следующие разработки дадут представление о некоторых наиболее экзотических вариантах. В модели «хорошо-посредственно-плохо» каждый элемент относится к «хорошему», «посредственному» или «плохому», а результатом теста является тип «худшего» элемента в группе. При тестировании пороговой группы результат теста является положительным, если количество дефектных изделий в группе превышает некоторое пороговое значение или долю. Групповое тестирование с ингибиторами - вариант применения в молекулярной биологии. Здесь существует третий класс предметов, называемый ингибиторами, и результат теста считается положительным, если он содержит хотя бы один дефектный элемент и не содержит ингибиторов.

История и развитие

Изобретение и первоначальный прогресс

Концепция группового тестирования была впервые представлена ​​Робертом Дорфманом в 1943 году в коротком отчете. опубликовано в разделе «Примечания» журнала «Анналы математической статистики» . Отчет Дорфмана – как и все ранние работы по групповому тестированию – сосредоточился на вероятностной проблеме и был направлен на использование новой идеи группового тестирования для уменьшения ожидаемого количества тестов, необходимых для отсеивания всех мужчин, больных сифилисом, в данном пуле солдат. Метод был прост: разбить солдат на группы заданного размера и использовать индивидуальное тестирование (тестирование предметов в группах одного размера) на положительных группах, чтобы определить, какие из них были инфицированы. Дорфман составил таблицу оптимальных размеров групп для этой стратегии с учетом уровня распространенности дефективности среди населения. Стивен Сэмюэлс нашли решение в закрытой форме для определения оптимального размера группы в зависимости от уровня распространенности.

После 1943 года групповые испытания в течение ряда лет оставались практически нетронутыми. Затем, в 1957 году, Стерретт усовершенствовал процедуру Дорфмана. Этот новый процесс начинается с повторного индивидуального тестирования положительных групп, но останавливается, как только обнаруживается дефект. Затем остальные элементы группы проверяются вместе, поскольку весьма вероятно, что ни один из них не окажется дефектным.

Первое подробное рассмотрение группового тестирования было дано Собелом и Гроллом в их основополагающей статье по этому вопросу в 1959 году. Они описали пять новых процедур – в дополнение к обобщениям для случаев, когда уровень распространенности неизвестен – и для оптимальной они предоставили явную формулу для ожидаемого количества тестов, которые она будет использовать. установлена ​​связь между групповым тестированием и теорией информации В статье также впервые , а также обсуждаются некоторые обобщения проблемы группового тестирования и предлагаются некоторые новые применения теории.

Фундаментальный результат Питера Унгара, полученный в 1960 году, показывает, что если уровень распространенности $p>p_{u}=(3-{\sqrt {5}})/2\approx 0.38$, то индивидуальное тестирование является оптимальной процедурой группового тестирования относительно ожидаемого числа тестов, и если $p<p_{u}$, то это не оптимально. Однако важно отметить, что, несмотря на 80-летние исследования, оптимальная процедура пока неизвестна. $p<p_{u}$ и общая численность населения $n>2$.

Комбинаторное групповое тестирование

Групповое тестирование было впервые изучено в комбинаторном контексте Ли в 1962 году. с введением Ли $s$-стадийный алгоритм . Ли предложил продлить«Двухэтапный алгоритм» Дорфмана к произвольному числу этапов, не требующий болеечем $t={\frac {e}{\log _{2}(e)}}d\log _{2}(n)$ тесты, которые гарантированно найдут $d$ или меньше дефектных среди $n$ предметы.Идея заключалась в том, чтобы удалить все элементы в отрицательных тестах, а оставшиеся элементы разделить на группы, как это было сделано с исходным пулом. Это должно было быть сделано $s-1$ раз перед выполнением индивидуального тестирования.

Комбинаторное групповое тестирование в целом позже было более полно изучено Катоной в 1973 году. Катона ввел матричное представление неадаптивного группового тестирования и разработал процедуру поиска дефектного в неадаптивном 1-дефектном случае не более чем за $t=\lceil \log _{2}(n)\rceil$испытаний, которые он также оказался оптимальными.

В общем, найти оптимальные алгоритмы для адаптивного комбинаторного группового тестирования сложно, и хотя вычислительная сложность группового тестирования не определена, предполагается, что оно будет трудным . в каком-то классе сложности Однако важный прорыв произошел в 1972 году с введением обобщенного алгоритма двоичного разделения . Обобщенный алгоритм двоичного разделения работает, выполняя двоичный поиск в группах с положительным результатом теста, и представляет собой простой алгоритм, который находит один дефектный алгоритм не более чем за ограниченное нижней границей информации количество тестов, .

В сценариях, где имеется два или более дефектов, обобщенный алгоритм двоичного разделения по-прежнему дает почти оптимальные результаты, требующие не более $d-1$ тесты выше нижней границы информации, где $d$ это количество бракованных. В 2013 году компания Allemann внесла значительные улучшения в этот процесс, в результате чего необходимое количество тестов сократилось до менее чем $0.187d+0.5\log _{2}(d)+5.5$ выше нижней границы информации, когда $n/d\geq 38$ и $d\geq 10$. Это было достигнуто за счет замены двоичного поиска в алгоритме двоичного разделения на сложный набор подалгоритмов с перекрывающимися тестовыми группами. Таким образом, проблема адаптивного комбинаторного группового тестирования – с известным числом или верхней границей числа дефектных – по существу решена, и возможностей для дальнейшего совершенствования практически нет.

остается открытым Вопрос о том, когда индивидуальное тестирование является минимальным, . Ху, Хван и Ван показали в 1981 году, что индивидуальное тестирование является минимальным, когда $n\leq \lfloor (5d+1)/2\rfloor$, и что это не минмакс, когда $n>3d$. В настоящее время предполагается, что эта граница является точной: то есть индивидуальное тестирование является минимаксным тогда и только тогда, когда $n\leq 3d$. Некоторый прогресс был достигнут в 2000 году Риччио и Колборном, которые показали, что для больших $n$, индивидуальное тестирование является минмаксом, когда $d\geq n/\log _{3/2}(3)\approx 0.369n$.

Неадаптивное и вероятностное тестирование

Один из ключевых выводов о неадаптивном групповом тестировании заключается в том, что значительных успехов можно добиться, устранив требование, чтобы процедура группового тестирования была уверена в успехе («комбинаторная» проблема), а, скорее, разрешив ей иметь некоторые низкие, но неудовлетворительные результаты. -нулевая вероятность неправильной маркировки каждого элемента («вероятностная» проблема). Известно, что по мере того, как число дефектных изделий приближается к общему числу изделий, точные комбинаторные решения требуют значительно большего количества тестов, чем вероятностные решения — даже вероятностные решения, допускающие лишь асимптотически малую вероятность ошибки.

В этом духе Чан и др. (2011) представили COMP — вероятностный алгоритм, требующий не более $t=ed(1+\delta )\ln(n)$ тесты, чтобы найти до $d$ дефекты в $n$ элементы с вероятностью ошибки не более $n^{-\delta }$. Это находится в пределах постоянного коэффициента $t=O(d\log _{2}n)$ нижняя граница.

Чан и др. (2011) также обобщили COMP на простую модель с шумом и аналогичным образом установили явную границу производительности, которая снова была лишь константой (зависящей от вероятности неудачного теста) выше соответствующей нижней границы. В общем, количество тестов, необходимых в случае шума Бернулли, является постоянным фактором, большим, чем в случае без шума.

Олдридж, Бальдассини и Джонсон (2014) разработали расширение алгоритма COMP, в которое добавлены дополнительные этапы постобработки. Они показали, что производительность этого нового алгоритма, названного DD , строго превосходит производительность COMP, и что DD «по существу оптимален» в сценариях, где $d^{2}\geq n$, сравнивая его с гипотетическим алгоритмом, определяющим разумный оптимум. Производительность этого гипотетического алгоритма предполагает, что есть возможности для улучшения, когда $d^{2}<n$, а также предположить, насколько это может быть лучше.

Формализация комбинаторного группового тестирования

В этом разделе формально определены понятия и термины, относящиеся к групповому тестированию.

• вектор Входной , $\mathbf {x} =(x_{1},x_{2},\dots ,x_{n})$, определяется как двоичный вектор длины $n$ (то есть, $\mathbf {x} \in \{0,1\}^{n}$), причем j -й элемент называется бракованным тогда и только тогда, когда $x_{j}=1$. Кроме того, любой исправный товар называется «хорошим».

$\mathbf {x}$ предназначен для описания (неизвестного) набора дефектных изделий. Ключевое свойство $\mathbf {x}$ заключается в том, что это неявный ввод . То есть, нет прямого знания о том, какие записи $\mathbf {x}$ являются иными, чем те, которые можно вывести с помощью серии «тестов». Это приводит к следующему определению.

• Позволять $\mathbf {x}$ быть входным вектором. Набор, $S\subseteq \{1,2,\dots ,n\}$ называется тестом . Если тестирование бесшумное , результат теста положительный , если существует $j\in S$ такой, что $x_{j}=1$, а в противном случае результат отрицательный .

Поэтому цель группового тестирования — найти метод выбора «короткой» серии тестов, позволяющей $\mathbf {x}$ определить точно или с высокой степенью достоверности.

• Говорят, что алгоритм группового тестирования допускает ошибку , если он неправильно маркирует элемент (то есть помечает любой дефектный элемент как исправный или наоборот). Это не то же самое, что результат группового теста неверен. Алгоритм называется нулевым, если вероятность того, что он допустит ошибку, равна нулю.
• $t(d,n)$ обозначает минимальное количество тестов, необходимое для того, чтобы всегда найти $d$ дефекты среди $n$ элементы с нулевой вероятностью ошибки по любому алгоритму группового тестирования. Для той же величины, но с ограничением неадаптивности алгоритма, используются обозначения ${\bar {t}}(d,n)$ используется.

Общие границы

Поскольку всегда можно прибегнуть к индивидуальному тестированию, установив $S_{j}=\{j\}$ для каждого $1\leq j\leq n$, должно быть, это то ${\bar {t}}(d,n)\leq n$. Кроме того, поскольку любую процедуру неадаптивного тестирования можно записать как адаптивный алгоритм, просто выполняя все тесты без учета их результатов, $t(d,n)\leq {\bar {t}}(d,n)$. Наконец, когда $0\neq d\neq n$, существует хотя бы одно изделие, дефектность которого необходимо определить (хотя бы одним испытанием), и поэтому $1\leq t(d,n)$.

Подводя итог (при условии, что $0\neq d\neq n$), $1\leq t(d,n)\leq {\bar {t}}(d,n)\leq n$.

Нижняя граница информации

Нижнюю границу количества необходимых тестов можно описать с помощью понятия выборочного пространства , обозначаемого ${\mathcal {S}}$, который представляет собой просто набор возможных мест размещения дефектов. Для любой проблемы группового тестирования с выборочным пространством ${\mathcal {S}}$ и любого алгоритма группового тестирования, можно показать, что $t\geq \lceil \log _{2}{|{\mathcal {S}}|}\rceil$, где $t$ — минимальное количество испытаний, необходимое для выявления всех дефектов с нулевой вероятностью ошибки. Это называется нижней границей информации . Эта граница получена из того факта, что после каждого теста ${\mathcal {S}}$ делится на два непересекающихся подмножества, каждое из которых соответствует одному из двух возможных результатов теста.

Однако сама нижняя граница информации обычно недостижима даже для небольших задач. Это связано с тем, что расщепление ${\mathcal {S}}$ не является произвольным, поскольку оно должно быть реализуемо с помощью некоторого теста.

Фактически, нижнюю границу информации можно обобщить на случай, когда существует ненулевая вероятность того, что алгоритм допустит ошибку. В этой форме теорема дает нам верхнюю границу вероятности успеха, основанную на количестве тестов. Для любого алгоритма группового тестирования, который выполняет $t$ испытания, вероятность успеха, $\mathbb {P} ({\textrm {success}})$, удовлетворяет $\mathbb {P} ({\textrm {success}})\leq t/\log _{2}{n \choose d}$. Это можно усилить, чтобы: $\mathbb {P} ({\textrm {success}})\leq {\frac {2^{t}}{n \choose d}}$.

Представление неадаптивных алгоритмов

Типичная установка группового тестирования. Неадаптивный алгоритм сначала выбирает матрицу $M$, а затем дается вектор y . Тогда проблема состоит в том, чтобы найти оценку x .

Алгоритмы неадаптивного группового тестирования состоят из двух отдельных этапов. Сначала решается, сколько тестов выполнить и какие элементы включить в каждый тест. На втором этапе, часто называемом этапом декодирования, результаты каждого группового теста анализируются, чтобы определить, какие элементы могут быть дефектными. Первая фаза обычно кодируется в матрице следующим образом.

• Предположим, что используется неадаптивная процедура группового тестирования для $n$ предметы состоят из тестов $S_{1},S_{2},\dots ,S_{t}$ для некоторых $t\in \mathbb {N} _{\geq 0}$. Матрица тестирования для этой схемы представляет собой $t\times n$ двоичная матрица, $M$, где $(M)_{ij}=1$ тогда и только тогда, когда $j\in S_{i}$ (и равен нулю в противном случае).

Таким образом, каждый столбец $M$ представляет элемент, а каждая строка представляет собой тест с $1$ в $(i,j){\textrm {-th}}$ запись, указывающая на то, что $i{\textrm {-th}}$ тест включал в себя $j{\textrm {-th}}$ предмет и $0$ указывая на иное.

Как и вектор $\mathbf {x}$ (длины $n$), описывающий неизвестное дефектное множество, обычно вводят вектор результатов, который описывает результаты каждого теста.

• Позволять $t$ — количество тестов, выполненных неадаптивным алгоритмом. Вектор результата , $\mathbf {y} =(y_{1},y_{2},\dots ,y_{t})$, представляет собой двоичный вектор длины $t$ (то есть, $\mathbf {y} \in \{0,1\}^{t}$) такой, что $y_{i}=1$ тогда и только тогда, когда результат $i{\textrm {-th}}$ тест был положительным (т.е. содержал хотя бы один дефектный).

С помощью этих определений неадаптивная проблема может быть переформулирована следующим образом: сначала выбирается проверочная матрица, $M$, после чего вектор $\mathbf {y}$ возвращается. Тогда проблема в том, чтобы проанализировать $\mathbf {y}$ найти некоторую оценку для $\mathbf {x}$.

В простейшем зашумленном случае, когда существует постоянная вероятность, $q$, что групповой тест даст ошибочный результат, рассматривается случайный двоичный вектор, $\mathbf {v}$, где каждая запись имеет вероятность $q$ бытия $1$, и есть $0$ в противном случае. Тогда возвращаемый вектор ${\hat {\mathbf {y} }}=\mathbf {y} +\mathbf {v}$, с обычным дополнением $(\mathbb {Z} /2\mathbb {Z} )^{n}$ (эквивалентно это поэлементная операция XOR ). Шумный алгоритм должен оценивать $\mathbf {x}$ с использованием ${\hat {\mathbf {y} }}$ (то есть без непосредственного знания $\mathbf {y}$).

Границы для неадаптивных алгоритмов

Матричное представление позволяет доказать некоторые ограничения на неадаптивное групповое тестирование. Этот подход отражает подход многих детерминистских проектов, где $d$-разделимые матрицы рассматриваются, как определено ниже.

• Бинарная матрица, $M$, называется $d$-сепарабельны , если каждая булева сумма (логическое ИЛИ) любого $d$ его столбцов различен. Кроме того, обозначения ${\bar {d}}$-separable указывает, что каждая сумма любого из до $d$ из $M$столбцы различны. (Это не то же самое, что $M$ существование $k$-разборный для каждого $k\leq d$.)

Когда $M$ это матрица тестирования, свойство быть $d$-разборный ( ${\bar {d}}$-separable) эквивалентно способности различать (до) $d$ дефектные. Однако это не гарантирует, что это будет просто. Более сильное свойство, называемое дизъюнктностью, имеет такое значение.

• Бинарная матрица, $M$ называется $d$-дизъюнкт , если булева сумма любого $d$ Столбцы не содержат других столбцов. (В этом контексте говорят, что столбец A содержит столбец B, если для каждого индекса, где B имеет 1, A также имеет 1.)

Полезное свойство $d$-дизъюнктные матрицы тестирования заключаются в том, что с точностью до $d$ дефектные, то каждый исправный товар будет обнаружен по крайней мере в одном тесте, результат которого будет отрицательным. Это означает, что существует простая процедура поиска дефектов: просто удалите каждый элемент, который окажется в отрицательном тесте.

Используя свойства $d$-разборные и $d$-дизъюнктных матриц для задачи идентификации $d$ дефекты среди $n$ общее количество предметов.

1. Количество тестов, необходимых для асимптотически малой средней вероятности ошибки, масштабируется как $O(d\log _{2}n)$.
2. Количество тестов, необходимых для асимптотически малой максимальной вероятности ошибки, масштабируется как $O(d^{2}\log _{2}n)$.
3. Количество тестов, необходимых для нулевой вероятности ошибки, масштабируется как $O\left({\frac {d^{2}\log _{2}n}{\log _{2}d}}\right)$.

Обобщенный алгоритм двоичного разделения

Иллюстрация обобщенного алгоритма двоичного разделения, в котором имеется 8 дефектных и всего 135 элементов. Здесь, $2^{\alpha _{1}}=16$, и первый тест дает отрицательный результат, поэтому каждый товар объявляется исправным. Следовательно, осталось 119 элементов, поэтому $2^{\alpha _{2}}=8$. Эта вторая группа дает положительный результат, поэтому для поиска бракованного используется бинарный поиск. Как только это будет сделано, весь процесс повторяется, вычисляя новую $\alpha$ использование только тех изделий, дефектность которых не установлена.

Обобщенный алгоритм двоичного разделения — это по существу оптимальный адаптивный алгоритм группового тестирования, который находит $d$ или меньше дефектных среди $n$ предметы следующим образом:

1. Если $n\leq 2d-2$, протестируйте $n$ предметы индивидуально. В противном случае установите $l=n-d+1$ и $\alpha =\lfloor \log _{2}{l/d}\rfloor$.
2. Тестирование группы по размеру $2^{\alpha }$. При отрицательном результате каждая деталь группы признается исправной; набор $n:=n-2^{\alpha }$ и перейдите к шагу 1. В противном случае используйте двоичный поиск для выявления одного дефектного и неопределенного номера, называемого $x$, исправных изделий; набор $n:=n-1-x$ и $d:=d-1$. Перейдите к шагу 1.

Обобщенный алгоритм двоичного разделения требует не более $T$ тесты, где $T={\begin{cases}n&n\leq 2d-2\\(\alpha +2)d+p-1&n\geq 2d-1\end{cases}}$.

Для $n/d$ большой, можно показать, что $T\rightarrow d\log _{2}(n/d)$, что выгодно отличается от $t={\frac {e}{\log _{2}e}}d\log _{2}\left({\frac {n}{d}}\right)$ необходимые тесты для Ли $s$-этапный алгоритм. Фактически обобщенный алгоритм двоичного разбиения близок к оптимальному в следующем смысле. Когда $d\geq 2$ можно показать, что $T-B_{I}(d,n)\leq (d-1)$, где $B_{I}(d,n)=\left\lceil \log _{2}\sum _{i=0}^{d}{n \choose i}\right\rceil$ – нижняя граница информации.

Неадаптивные алгоритмы

Неадаптивные алгоритмы группового тестирования склонны предполагать, что известно количество дефектов или, по крайней мере, их хорошая верхняя граница. Эту величину обозначают $d$ в этом разделе. Если границы не известны, существуют неадаптивные алгоритмы с низкой сложностью запроса, которые могут помочь оценить $d$.

Комбинаторное ортогональное сопоставление (COMP)

Иллюстрация алгоритма COMP. COMP идентифицирует деталь a как дефектную, а деталь b как исправную. Однако он ошибочно помечает c как дефектный, поскольку он «скрыт» дефектными заданиями в каждом тесте, в котором он появляется.

Комбинаторное ортогональное сопоставление (COMP) — это простой неадаптивный алгоритм группового тестирования, который формирует основу для более сложных алгоритмов, описанных в этом разделе.

Во-первых, каждая запись матрицы тестирования выбирается iid как $1$ с вероятностью $1/d$ и $0$ в противном случае.

Этап декодирования выполняется по столбцам (т.е. по элементам). Если каждое испытание, в котором обнаруживается изделие, оказывается положительным, то изделие объявляется дефектным; в противном случае товар считается исправным. Или, что то же самое, если в ходе какого-либо испытания обнаруживается изделие с отрицательным результатом, изделие объявляется исправным; в противном случае товар считается дефектным. Важным свойством этого алгоритма является то, что он никогда не создает ложноотрицательных результатов , хотя ложноположительный результат возникает, когда все местоположения с единицами находятся в j -м столбце $M$ (соответствующие исправному изделию j ) «скрыты» столбцами других столбцов, соответствующих дефектным изделиям.

Алгоритм COMP требует не более $ed(1+\delta )\ln(n)$ тесты, которые имеют вероятность ошибки меньше или равную $n^{-\delta }$. Это находится в пределах постоянного коэффициента нижней границы средней вероятности ошибки, указанной выше.

В случае с шумом можно ослабить требование исходного алгоритма COMP о том, что набор расположений единиц в любом столбце $M$ соответствующий положительному элементу, полностью содержаться в наборе расположений единиц в векторе результата. Вместо этого допускается определенное количество «несовпадений» — это количество несовпадений зависит как от количества единиц в каждом столбце, так и от параметра шума, $q$. Этот шумный алгоритм COMP требует не более $4.36({\sqrt {\delta }}+{\sqrt {1+\delta }})^{2}(1-2q)^{-2}d\log _{2}{n}$ тесты для достижения максимальной вероятности ошибки $n^{-\delta }$.

Явные дефекты (DD)

Метод определенных дефектов (DD) является расширением алгоритма COMP, который пытается удалить любые ложные срабатывания. Было показано, что гарантии производительности для DD строго превышают гарантии COMP.

На этапе декодирования используется полезное свойство алгоритма COMP: каждый элемент, который COMP объявляет исправным, безусловно, является дефектным (то есть нет ложноотрицательных результатов). Это происходит следующим образом.

1. Сначала запускается алгоритм COMP, и все обнаруженные им исправные дефекты удаляются. Все оставшиеся предметы теперь «возможно, бракованные».
2. Далее алгоритм просматривает все положительные тесты. Если элемент оказывается единственным «возможным дефектом» в тесте, то он должен быть дефектным, поэтому алгоритм объявляет его дефектным.
3. Все остальные изделия считаются исправными. Оправдание этого последнего шага исходит из предположения, что количество дефектных изделий намного меньше общего количества изделий.

Обратите внимание, что шаги 1 и 2 никогда не допускают ошибок, поэтому алгоритм может допустить ошибку только в том случае, если он объявит дефектный элемент исправным. Таким образом, алгоритм DD может создавать только ложноотрицательные результаты.

Последовательный КОМП (SCOMP)

SCOMP (Sequential COMP) — это алгоритм, использующий тот факт, что DD не допускает ошибок до последнего шага, где предполагается, что остальные элементы исправны. Пусть множество заявленных дефектов будет $K$. тест называется объясненным Положительный $K$ если он содержит хотя бы один элемент в $K$. Ключевое наблюдение SCOMP заключается в том, что набор дефектов, обнаруженных DD, не может объяснить каждый положительный тест, и что каждый необъяснимый тест должен содержать скрытый дефект.

Алгоритм следующий.

1. Выполните шаги 1 и 2 алгоритма DD, чтобы получить $K$, начальная оценка набора дефектов.
2. Если $K$ объясняет каждый положительный тест, завершите алгоритм: $K$ — окончательная оценка набора дефектов.
3. При наличии необъяснимых тестов найти «возможный дефект», который появляется среди наибольшего числа необъяснимых тестов, и объявить его дефектным (то есть добавить его в множество $K$). Перейдите к шагу 2.

В ходе моделирования было показано, что SCOMP работает близко к оптимальному.

Полиномиальные пулы (PP)

Детерминированный алгоритм, который гарантированно точноидентифицировать до $d$ позитивы — это полиномиальные пулы (PP).. Алгоритм предназначен для построения матрицы пула. $M$, который можно напрямую использоватьрасшифровать наблюдения в $y$. Похоже на:COMP, выборка декодируется по соотношению: $x_{i}=1~~{\text{ if }}~~M(:,i)~.*~y=M(:,i)$, где $.*$ представляет собой поэлементное умножение и $M(:,i)$ это $i$й столбец $M$. Поскольку этап декодирования не сложен, PP специализируется на генерации $M$.

Формирование групп

Оформление группы с $q^{c-1}=9$ образцы (синие) из набора $n=q^{c}=27$ общее количество выборок с использованием алгоритма полиномиальных пулов

Группа/бассейн $\ell$ являетсягенерируется с использованием полиномиального отношения, которое определяет индексы выборок, содержащихся в каждом пуле. Набор входных параметров определяет алгоритм. Для простого числа $p>1$ и целое число $n\geq 1$ любая простая степень определяется формулой $q=p^{n}$. Для параметра размера $c\geq 2$ общее количество образцов $n=q^{c}$ а количество образцов на пул равно $q^{c-1}$.Кроме того, Конечное порядка поле $q$ обозначается $\mathbb {F} _{q}$ (т.е. целые числа $\{0,1,2,\ldots ,q-1\}$ определяются специальными арифметическими операциями, которые гарантируют, что сложение и умножение в $\mathbb {F} _{q}$ остается в $\mathbb {F} _{q}$).Метод располагает каждый образец в сетке и представляет его по координатам. $x=(u,v)$. Координаты вычисляются в соответствии с полиномиальным соотношением с использованием целых чисел $1\leq l\leq c-1$, $0\leq u_{i_{l}}\leq q-1$

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

Комбинация циклического прохождения $u_{i_{l}}$ значения представлены набором с $q^{c-1}$ элементы последовательности $d-1$ целые числа, т.е. $u_{i_{1}}\times \cdots \times u_{i_{c-1}}=\{(i_{1},\ldots ,i_{c-1})\}$, где $0\leq i_{l}\leq q-1$. Без ограничения общности комбинация такова, что $i_{d-1}$ циклы каждые $q$ раз, $i_{d-2}$ циклы каждые $q^{2}$ раз, пока $i_{1}$ цикл только один раз.Формулы, вычисляющие индексы выборки и, следовательно, соответствующие пулы для фиксированных $a$ и $b$, даны

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

Вычисления в $\mathbb {F} _{q}$ может быть реализовано с помощью общедоступных программных библиотек для конечных полей, когда $q$ это высшая сила. Когда $q$ является простым числом, то вычисления в $\mathbb {F} _{q}$ упростить до модульной арифметики, т.е. $v_{u_{i}}=(\sum _{l=1}^{c-1}a^{l}i_{l}+b)~{\text{mod}}~q$. Пример того, как сгенерировать один пул $\ell$ когда $a=1,b=0,c=2$ отображается в таблице ниже, а соответствующая выборка образцов показана на рисунке выше.

Вычисление одного пула $\ell$ используя ПП с $c=3$, $q=3$, $a=1$, $b=0$

$i_{1}$	$i_{2}$	$u_{i}$	$v_{u_{i}}$	$qu_{i}+v_{u_{i}}$	$\ell$
$0$	$0$	$0$	$0$	$0$	$x_{0}$
$0$	$1$	$1$	$1$	$4$	$x_{4}$
$0$	$2$	$2$	$2$	$8$	$x_{8}$
$1$	$0$	$3$	$1$	$10$	$x_{10}$
$1$	$1$	$4$	$2$	$14$	$x_{14}$
$1$	$2$	$5$	$0$	$15$	$x_{15}$
$2$	$0$	$6$	$2$	$20$	$x_{20}$
$2$	$1$	$7$	$0$	$21$	$x_{21}$
$2$	$2$	$8$	$1$	$25$	$x_{25}$

Этот метод использует $q(c-1)(d+1)$ тесты для точной идентификации до $d$ позитивные моменты среди $n=q^{c}$ образцы.По этой причине ПП особенно эффективен для больших объемов выборок, поскольку количество тестов растет только линейно по отношению к $c$ в то время как образцы растут экспоненциально с этим параметром. Однако ПП также может быть эффективным для выборок небольшого размера.

Примеры приложений

Общность теории группового тестирования позволяет использовать ее во многих разнообразных приложениях, включая скрининг клонов, обнаружение коротких замыканий; высокоскоростные компьютерные сети; медицинское обследование, поиск количества, статистика; машинное обучение, секвенирование ДНК; криптография; и судебная экспертиза данных. В этом разделе представлен краткий обзор небольшой выборки этих приложений.

Каналы мультидоступа

Иллюстрация канала множественного доступа, показывающая успешное сообщение и конфликт сообщений.

Канал множественного доступа — это канал связи, который соединяет одновременно множество пользователей. Каждый пользователь может слушать и передавать по каналу, но если несколько пользователей передают одновременно, сигналы сталкиваются и превращаются в неразборчивый шум. Каналы множественного доступа важны для различных реальных приложений, особенно для беспроводных компьютерных сетей и телефонных сетей.

Заметная проблема с каналами множественного доступа заключается в том, как назначить время передачи пользователям, чтобы их сообщения не конфликтовали. Простой метод — предоставить каждому пользователю собственный временной интервал для передачи, требующий $n$ слоты. (Это называется мультиплексированием с временным разделением , или TDM.) Однако это очень неэффективно, поскольку при этом интервалы передачи будут назначаться пользователям, у которых может не быть сообщения, и обычно предполагается, что только несколько пользователей захотят передавать в любой момент времени. заданное время – в противном случае канал множественного доступа вообще непрактичен.

В контексте группового тестирования эта проблема обычно решается путем разделения времени на «эпохи» следующим образом. Пользователь называется «активным», если у него есть сообщение в начале эпохи. (Если сообщение генерируется в течение определенной эпохи, пользователь становится активным только в начале следующей.) Эпоха заканчивается, когда каждый активный пользователь успешно передал свое сообщение. Проблема заключается в том, чтобы найти всех активных пользователей в данную эпоху и запланировать время для их передачи (если они еще не сделали этого успешно). Здесь тест на наборе пользователей соответствует тем пользователям, которые пытаются осуществить передачу. Результатом теста является количество пользователей, пытавшихся осуществить передачу, $0,1,$ и $2^{+}$, что соответствует соответственно отсутствию активных пользователей, ровно одному активному пользователю (успешная передача сообщения) или более чем одному активному пользователю (конфликт сообщений). Поэтому использование алгоритма адаптивного группового тестирования с результатами $\{0,1,2^{+}\}$, можно определить, какие пользователи хотят передавать в эпоху. Затем любому пользователю, который еще не совершил успешную передачу, теперь можно назначить слот для передачи, без расточительного назначения времени неактивным пользователям.

Машинное обучение и сжатое зондирование

Машинное обучение — это область информатики, в которой имеется множество программных приложений, таких как классификация ДНК, обнаружение мошенничества и таргетированная реклама. Одной из основных областей машинного обучения является проблема «обучения на примерах», где задача состоит в том, чтобы аппроксимировать некоторую неизвестную функцию, если ей задано ее значение в ряде конкретных точек. Как указано в этом разделе, эту проблему обучения функции можно решить с помощью подхода группового тестирования.

В простом варианте задачи есть какая-то неизвестная функция, $f:\{0,1\}^{N}\to \{0,1\}$ где $f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}$, и ${\textbf {a}}\in \{0,1\}^{N}$ (с использованием логической арифметики: сложение — логическое ИЛИ, а умножение — логическое И). Здесь ${\textbf {a}}$ является ' $d$ разреженный', что означает, что самое большее $d\ll N$ из его записей $1$. Цель состоит в том, чтобы построить приближение к $f$ с использованием $t$ балльные оценки, где $t$ как можно меньше. (Именно выздоравливает $f$ соответствует алгоритмам с нулевой ошибкой, тогда как $f$ аппроксимируется алгоритмами, имеющими ненулевую вероятность ошибки.)

В этой задаче восстановление $f$ эквивалентно нахождению ${\textbf {a}}$. Более того, $f({\textbf {p}})=1$ тогда и только тогда, когда существует некоторый индекс, $n$, где ${\textbf {a}}_{n}={\textbf {p}}_{n}=1$. Таким образом, эта проблема аналогична задаче группового тестирования с $d$ дефектные и $n$ общее количество предметов. Записи ${\textbf {a}}$ являются изделиями, которые являются дефектными, если они $1$, ${\textbf {p}}$ определяет тест, и тест положителен тогда и только тогда, когда $f({\textbf {p}})=1$.

В действительности часто интересуют более сложные функции, такие как $f:\mathbb {C} ^{N}\to \mathbb {C}$, опять же где $f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}$. Для решения этой проблемы можно использовать сжатое зондирование , тесно связанное с групповым тестированием.

Целью сжатого зондирования является восстановление сигнала, ${\textbf {v}}\in \mathbb {C} ^{N}$, проведя ряд измерений. Эти измерения моделируются как произведение скалярное ${\textbf {v}}$ с выбранным вектором. Цель состоит в том, чтобы использовать небольшое количество измерений, хотя обычно это невозможно, если не делать каких-либо предположений о сигнале. Одно из таких предположений (которое часто встречается ) заключается в том, что лишь небольшое количество записей ${\textbf {v}}$ значимы , то есть имеют большую величину. Поскольку измерения представляют собой скалярное произведение ${\textbf {v}}$, уравнение $M{\textbf {v}}={\textbf {q}}$ держится, где $M$ это $t\times N$ матрица, которая описывает набор измерений, которые были выбраны и $\mathbf {q}$ – набор результатов измерений. Эта конструкция показывает, что сжатое зондирование представляет собой своего рода «непрерывное» групповое тестирование.

Основная трудность при сжатом измерении заключается в определении того, какие записи являются значимыми. Как только это будет сделано, существует множество методов для оценки фактических значений записей. К этой задаче идентификации можно подойти с помощью простого применения группового тестирования. Здесь групповой тест выдает комплексное число: сумму проверяемых записей. Результат теста называется положительным, если он дает комплексное число большой величины, что, учитывая предположение о том, что значимые записи немногочисленны, указывает на то, что в тесте содержится по крайней мере одна значимая запись.

Для этого типа алгоритма комбинаторного поиска существуют явные детерминированные конструкции, требующие $d2^{(\log _{2}\log _{2}N)^{O(1)}}$ измерения. Однако, как и в случае с групповым тестированием, они неоптимальны, и случайные конструкции (такие как COMP) часто могут помочь. $f$ сублинейно в $N$.

Дизайн мультиплексного анализа для тестирования на COVID19

Во время пандемии, такой как вспышка COVID-19 в 2020 году, анализы на выявление вируса иногда проводятся с использованием неадаптивных групповых схем тестирования. Один из примеров был предоставлен проектом Origami Assays, который выпустил проекты группового тестирования с открытым исходным кодом для проведения на лабораторном стандартном 96-луночном планшете.

Бумажный шаблон оригами для дизайна группового тестирования

В лабораторных условиях одной из проблем группового тестирования является то, что приготовление смесей может занять много времени и его сложно сделать точно вручную. Анализы «Оригами» позволили обойти эту проблему, предоставив бумажные шаблоны, которые помогали технику распределять образцы пациентов по испытательным лункам.

Используя самые большие схемы группового тестирования (XL3), удалось протестировать 1120 образцов пациентов в 94 аналитических лунках. Если уровень истинного положительного результата был достаточно низким, то дополнительное тестирование не требовалось.

См. Также: Список стран, реализующих стратегию пулового тестирования на COVID-19.

Криминалистика данных

Криминалистика данных — это область, посвященная поиску методов сбора цифровых доказательств преступлений. Такие преступления обычно включают в себя изменение злоумышленником данных, документов или баз данных жертвы, примеры включают изменение налоговых отчетов, вирус, скрывающий свое присутствие, или похититель личных данных, изменяющий личные данные.

Распространенным инструментом в криминалистике данных является односторонний криптографический хэш . Это функция, которая принимает данные и с помощью сложнообратимой процедуры создает уникальное число, называемое хешем. Хэши, которые часто намного короче данных, позволяют нам проверить, были ли изменены данные, без необходимости расточительного хранения полных копий информации: хеш текущих данных можно сравнить с прошлым хэшем, чтобы определить, есть ли какие-либо изменения. произошли. Неприятным свойством этого метода является то, что, хотя легко определить, были ли изменены данные, невозможно определить, каким образом: то есть невозможно восстановить, какая часть данных была изменена.

Один из способов обойти это ограничение — хранить больше хэшей (теперь подмножеств структуры данных), чтобы сузить область, где произошла атака. Однако, чтобы определить точное место атаки с помощью наивного подхода, необходимо сохранить хэш для каждого элемента данных в структуре, что в первую очередь приведет к исчезновению точки хэшей. (Можно также хранить обычную копию данных.) Групповое тестирование можно использовать для значительного сокращения количества хэшей, которые необходимо хранить. Тест представляет собой сравнение сохраненных и текущих хэшей, которое является положительным в случае несоответствия. Это указывает на то, что по крайней мере один отредактированный элемент данных (который в этой модели принимается за дефектность) содержится в группе, сгенерировавшей текущий хэш.

Фактически, количество необходимых хэшей настолько мало, что они вместе с матрицей тестирования, к которой они относятся, могут даже храниться в организационной структуре самих данных. Это означает, что что касается памяти, тест можно провести «бесплатно». (Это верно, за исключением главного ключа/пароля, который используется для тайного определения функции хеширования.)

Ссылки

Общие ссылки

• Дин-Чжу, Ду; Хван, Фрэнк К. (1993). Комбинаторное групповое тестирование и его приложения . Сингапур: World Scientific. ISBN  978-9810212933 .
• Курс Атри Рудры «Коды, исправляющие ошибки: комбинаторика, алгоритмы и приложения» (весна 2007 г.), Лекции 7 .
• Курс Атри Рудры «Коды, исправляющие ошибки: комбинаторика, алгоритмы и приложения» (весна 2010 г.), лекции 10 , 11 , 28 , 29
• Ду, Д.; Хван, Ф. (2006). Объединение проектов и неадаптивное групповое тестирование . Всемирная научная. ISBN  9789814477864 .
• Олдридж, М.; Джонсон, О.; Скарлетт, Дж. (2019). «Групповое тестирование: взгляд на теорию информации» (PDF) . Основы и тенденции в теории связи и информации . 15 (3–4): 196–392. дои : 10.1561/0100000099 . S2CID   62841593 .
• Порат, Э.; Ротшильд, А. (2011). «Явные неадаптивные схемы комбинаторного группового тестирования». Транзакции IEEE по теории информации . 57 (12): 7982–89. arXiv : 0712.3876 . дои : 10.1109/TIT.2011.2163296 . S2CID   8815474 .
• Каган, Юджин; Бен-гал, Ирад (2014), «Алгоритм группового тестирования с информационным онлайн-обучением», IIE Transactions , 46 (2): 164–184, doi : 10.1080/0740817X.2013.803639 , ISSN   0740-817X , S2CID   18588494

См. также

• Балансовая головоломка