понедельник, сентября 08, 2008

Закон больших чисел

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

На большой выборке даже маловероятные события становятся наблюдаемыми.

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

Ещё одно проявление Закона больших чисел в том, что невозможно построить информационную систему гарантированно не содержащую ошибок в данных. Простой пример: Оператор вводит данные вручную. Оператор не идеален, поэтому он делает одну ошибку на 100 записей. Это означает, что на 1 000 000 введенных записей будет порядка 10 000 ошибок. Поскольку такое количество ошибок нас не устраивает, мы садим поверх оператора контроллера, который будет проверять правильность ввода. Пусть контроллер более внимателен и продуктивен, однако и он не идеален, поэтому допускает одну ошибку на 1000 записей. Тогда вероятность ошибки снижается до 10-5 на запись. Однако, на миллионе записей это даст примерно 10 ошибок. Если количество данных неограниченно растет, а так бывает почти всегда, никаким контролем не добиться гарантированного отсутствия ошибок. Даже оценить вероятность ошибки и то не всегда возможно. Люди не механические приборы, к ним паспортов точности не полагается.

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

  • Признают, что качество данных не имеет значения для бизнеса;
  • Контролируют качество собственными силами;
  • Выбирают один из наборов данных и признают его эталонным.

Это всего лишь частные эффекты. На практике достаточно хорошо осознавать, что чем больше данных, тем сильнее проявляется Закон больших чисел, влияние которого нужно учитывать при проектировании, в разработке и в тестировании.

2 комментария:

Анонимный комментирует...

Макс, ну зачем такие грязно-бытовушные трактовки ЗБЧ. Смысл ЗБЧ в точности обратный - при стремлении числа членов выборки к бесконечности выборочное среднее сходится по вероятности к матожиднию. То есть вероятность того, что выборочное среднее сколь угодно мало отличается от матожидания - стремится к нулю. Если у вас миллиард пользователей то их средние запросы точно соответствуют виндоус ХП и шестому эксплореру.
При проектировании больших и сложных систем источники ошибок учитывают, оценивают, контролируют и так далее. Получающие гигабайты данных в секунду компы с детектора ATLAS на LHC - это большая и сложная система, система приема платежей на мобильники из 100 автоматов - это мелкая бытовуха.
Даже приличные представители social science(мне тут кстати прояснили разницу между social science и humanities) публикуют данные с эррорбарами и оценками ошибок, корреляций и прочего.

Miroff комментирует...

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

Вот я о чем. Понятно что у scientist'ов культура оценки ошибок есть, а для физиков так вообще хлеб. Вопрос в том, как обстоит дело с ошибками у системы, которая начисляет тебе зарплату в институте, у системы учета багажа в аэропорту, у полицейской базы с отпечатками пальцев и т.п. Или это тоже "мелкая бытовуха"?