Хитрое тестирование

Немного тервера. Предположим, Вам надо протестировать воду нескольких водоёмов на чистоту, точнее, отсутствие в ней определённого редкого химиката (вероятность  p того, что он «загрязнит» водоём мала). У Вас есть супер-тест, который по пробе воды определяет в ней наличие химиката (со 100%-й точностью). Вы взяли пробы воды из N водоёмов и должны точно указать, в каких водоёмах он есть.

pic

Первый способ решения (примитивный). Последовательно протестировать N проб (из всех водоёмов). Так Вы гарантированно найдёте все загрязнённые.

Второй способ — попытаться сократить число тестов. Если вероятность загрязнения p очень мала, то есть шанс, что все водоёмы чистые. Давайте сделаем одну общую пробу воды (сольём по чуть-чуть из каждой пробы) и протестируем её. С вероятностью

formula4

мы ничего не обнаружим, иначе придётся всё-таки последовательно тестировать все пробы (или сделать умнее, см. дальше).

Итак, ожидаемое число тестов во втором способе

formula3Попробуем оценить, когда выгоден второй способ (это число меньше N).

Интуитивно ясно, что если химикат очень-очень редкий (вероятность p совсем маленькая), то второй способ явно лучше, т.к. он сводится просто к тому, чтобы убедиться, что все водоёмы чистые. Поэтому должна получиться какая-то оценка на p.

formula1

Единица на N в степени единица на N это страшно, поэтому, чтобы избежать громоздких выражений часто приближённо оценивают так

formula2

С такой оценкой, конечно, проще работать, но всё-таки надо понимать, к чему приводят такие оценки — см. рис.

graphik
Функции разных оценок.

Даже когда число водоёмов переваливает за сотню, оценки могут различаться на порядок! Так что, осторожнее с приближениями… А вот если Вы вторую оценку замените на 1/N, то разницы от изменения Вы не почувствуете (скажем, 0.01 или 0.0099).

Что делать, когда химикат не очень редкий? Тогда высока вероятность, что первый тест будет положительным, а следовательно, лишним. Всё равно можно попытаться сократить число тестов, разбив водоёмы на группы и сделав общие пробы всех групп. Если группа «чистая», то не надо отдельно тестировать её представителей. Кстати, этот метод был реально предложен Р.Дорфманом при тестировании на сифилис военнослужащих США и позволил сократить число тестов в пять раз! Можете это доказать, заодно определить оптимальный размер групп (такая задача есть во многих учебниках по ТВ).

В книге М.Б. Лагутина говорится про выигрыш в 5 раз (это доказывается прямым подсчётом), в двухтомнике В. Феллера (с. 254) говорится про экономию на 80% (возможно, Р.Дорфман выбрал неоптимальные размеры групп). В различных научных статьях методика была улучшена (введением большего числа этапов — разбиений на группы).

В анализе данных я столкнулся с тестированием, которое можно изложить в такой интерпретации (без вероятностей). Пусть у нас вода в водоёмах или абсолютно грязная или абсолютно чистая. Когда мы организуем объединённую пробу из нескольких водоёмов, то из каждого мы можем брать воду в одном объёме, скажем 1л, а тест говорит нам сколько литров грязной воды в пробе. Например, тестируем воду семи водоёмов, тест показал «2 литра», значит 2 из 7 грязные (какие именно — пока неизвестно). Вопрос: как организовать тестирование, чтобы делать поменьше тестов?

Интересно, что в худшем случае надо всё-таки сделать N тестов для N водоёмов, но вдруг повезёт… скажем, если для группы из 4х водоёмов тест показал 4л., то они все грязные, 0л. — они все чистые. Если 1л. или 3л. — то ровно один чистый/грязный и за логарифм от N тестов (ещё 2 теста) он находится. Хуже всего, когда 2л. — есть шанс сделать 4 теста для этих 4х водоёмов.

Самое забавное, что на практике число тестов в несколько раз меньше N (при ~ 300), а сами тесты можно делать чуть ли не по случайным подгруппам водоёмов (главное — правильно обрабатывать результаты, см. рис). Если кто-то знает здесь оптимальную стратегию — пишите.

test

Реклама

2 thoughts on “Хитрое тестирование

  1. Интересная постановка задачи. Оказывается, в зарубежной литературе она известна как Quantitative Group Testing и изучалась еще Эрдёшом. В книге Combinatorial Group Testing and Its Applications, которую довольно легко найти, об этом рассказывается в главе Additive Model and Others. Кроме того, на эту тему можно почитать также статью http://www.sciencedirect.com/science/article/pii/0012365X9400106S

    • Огромное спасибо! Я понимал, что задача должна быть известной, но не знал нужных терминов для гугления. Название «Quantitative Group Testing», действительно, позволяет найти много интересного!

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s