Ошибка первого рода ложная тревога

Материал из MachineLearning.

Перейти к: навигация, поиск

Статистическая гипотеза (statistical hypothesys) — это определённое предположение о распределении вероятностей, лежащем в основе наблюдаемой выборки данных.

Проверка статистической гипотезы (testing statistical hypotheses) — это процесс принятия решения о том, противоречит ли рассматриваемая статистическая гипотеза наблюдаемой выборке данных.

Статистический тест или статистический критерий — строгое математическое правило, по которому принимается или отвергается статистическая гипотеза.

Методика проверки статистических гипотез

Пусть задана случайная выборка — последовательность объектов из множества .
Предполагается, что на множестве существует некоторая неизвестная вероятностная мера .

Методика состоит в следующем.

1. Формулируется нулевая гипотеза  о распределении вероятностей на множестве . Гипотеза формулируется исходя из требований прикладной задачи. Чаще всего рассматриваются две гипотезы — основная или нулевая и альтернативная . Иногда альтернатива не формулируется в явном виде; тогда предполагается, что  означает «не ». Иногда рассматривается сразу несколько альтернатив. В математической статистике хорошо изучено несколько десятков «наиболее часто встречающихся» типов гипотез, и известны ещё сотни специальных вариантов и разновидностей. Примеры приводятся ниже.
2. Задаётся некоторая статистика (функция выборки) , для которой в условиях справедливости гипотезы выводится функция распределения и/или плотность распределения . Вопрос о том, какую статистику надо взять для проверки той или иной гипотезы, часто не имеет однозначного ответа. Есть целый ряд требований, которым должна удовлетворять «хорошая» статистика . Вывод функции распределения при заданных  и  является строгой математической задачей, которая решается методами теории вероятностей; в справочниках приводятся готовые формулы для ; в статистических пакетах имеются готовые вычислительные процедуры.
3. Фиксируется уровень значимости — допустимая для данной задачи вероятность ошибки первого рода, то есть того, что гипотеза на самом деле верна, но будет отвергнута процедурой проверки. Это должно быть достаточно малое число . На практике часто полагают .
4. На множестве допустимых значений статистики  выделяется критическое множество  наименее вероятных значений статистики , такое, что . Вычисление границ критического множества как функции от уровня значимости является строгой математической задачей, которая в большинстве практических случаев имеет готовое простое решение.
5. Собственно статистический тест (статистический критерий) заключается в проверке условия:

Итак, статистический критерий определяется статистикой 
и критическим множеством , которое зависит от уровня значимости .

Замечание.
Если данные не противоречат нулевой гипотезе, это ещё не значит, что гипотеза верна.
Тому есть две причины.

Альтернативная методика на основе достигаемого уровня значимости

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

Достигаемый уровень значимости (пи-величина, англ. p-value) — это наименьшая величина уровня значимости,
при которой нулевая гипотеза отвергается для данного значения статистики критерия 

где
— критическая область критерия.

Другая интерпретация:
достигаемый уровень значимости — это вероятность при справедливости нулевой гипотезы получить значение статистики, такое же или ещё более экстремальное, чем 

Если достигаемый уровень значимости достаточно мал (близок к нулю), то нулевая гипотеза отвергается.
В частности, его можно сравнивать с фиксированным уровнем значимости;
тогда альтернативная методика будет эквивалентна классической.

Типы критической области

Обозначим через значение, которое находится из уравнения , где  — функция распределения статистики .
Если функция распределения непрерывная строго монотонная,
то есть обратная к ней функция:

.

Значение называется также —квантилем распределения .

На практике, как правило, используются статистики  с унимодальной (имеющей форму пика) плотностью распределения.
Критические области (наименее вероятные значения статистики) соответствуют «хвостам» этого распределения.
Поэтому чаще всего возникают критические области одного из трёх типов:

• Левосторонняя критическая область:

определяется интервалом .

пи-величина:

• Правосторонняя критическая область:

определяется интервалом .

пи-величина:

• Двусторонняя критическая область:

определяется двумя интервалами

пи-величина:

Ошибки первого и второго рода

• Ошибка первого рода или «ложная тревога» (англ. type I error,  error, false positive) — когда нулевая гипотеза отвергается, хотя на самом деле она верна. Вероятность ошибки первого рода:

• Ошибка второго рода или «пропуск цели» (англ. type II error,  error, false negative) — когда нулевая гипотеза принимается, хотя на самом деле она не верна. Вероятность ошибки второго рода:

	Верная гипотеза
Результат  применения  критерия		верно принята	неверно принята  (Ошибка второго рода)
	неверно отвергнута  (Ошибка первого рода)	верно отвергнута

Свойства статистических критериев

Мощность критерия:
— вероятность отклонить гипотезу , если на самом деле верна альтернативная гипотеза .
Мощность критерия является числовой функцией от альтернативной гипотезы .

Несмещённый критерий:

для всех альтернатив 
или, что то же самое,

для всех альтернатив .

Состоятельный критерий:
при для всех альтернатив .

Равномерно более мощный критерий.
Говорят, что критерий с мощностью является равномерно более мощным, чем критерий с мощностью , если выполняются два условия:

1. ;
2. для всех рассматриваемых альтернатив , причём хотя бы для одной альтернативы неравенство строгое.

Типы статистических гипотез

• Простая гипотеза однозначно определяет функцию распределения на множестве . Простые гипотезы имеют узкую область применения, ограниченную критериями согласия (см. ниже). Для простых гипотез известен общий вид равномерно более мощного критерия (Теорема Неймана-Пирсона).

• Сложная гипотеза утверждает принадлежность распределения к некоторому множеству распределений на . Для сложных гипотез вывести равномерно более мощный критерий удаётся лишь в некоторых специальных случаях.

Типы статистических критериев

В зависимости от проверяемой нулевой гипотезы статистические критерии делятся на группы, перечисленные ниже по разделам.

Наряду с нулевой гипотезой, которая принимается или отвергается по результату анализа выборки, статистические критерии могут опираться на дополнительные предположения, которые априори предпологаются выполненными.

• Параметрические критерии предполагают, что выборка порождена распределением из заданного параметрического семейства. В частности, существует много критериев, предназначенных для анализа выборок из нормального распределения. Преимущество этих критериев в том, что они более мощные. Если выборка действительно удовлетворяет дополнительным предположениям, то параметрические критерии дают более точные результаты. Однако если выборка им не удовлетворяет, то вероятность ошибок (как I, так и II рода) может резко возрасти. Прежде чем применять такие критерии, необходимо убедиться, что выборка удовлетворяет дополнительным предположениям. Гипотезы о виде распределения проверяются с помощью критериев согласия.

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

Критерии согласия

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

• Критерий Колмогорова-Смирнова
• Критерий хи-квадрат (Пирсона)
• Критерий омега-квадрат (фон Мизеса)

Критерии сдвига

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

• Критерий Стьюдента
• Критерий Уилкоксона-Манна-Уитни

Критерии нормальности

Критерии нормальности — это выделенный частный случай критериев согласия.
Нормально распределённые величины часто встречаются в прикладных задачах, что обусловлено действием закона больших чисел.
Если про выборки заранее известно, что они подчиняются нормальному распределению, то к ним становится возможно применять более мощные параметрические критерии.
Проверка нормальность часто выполняется на первом шаге анализа выборки, чтобы решить, использовать далее параметрические методы или непараметрические.
В справочнике А. И. Кобзаря приведена сравнительная таблица мощности для 21 критерия нормальности.

• Критерий Шапиро-Уилка
• Критерий асимметрии и эксцесса

Критерии однородности

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

Критерии симметричности

Критерии симметричности позволяют проверить симметричность распределения.

• Одновыборочный критерий Уилкоксона и его модификации: критерий Антилла-Кёрстинга-Цуккини, критерий Бхаттачария-Гаствирса-Райта
• Критерий знаков
• Коэффициент асимметрии

Критерии тренда, стационарности и случайности

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

Критерии выбросов

Критерии дисперсионного анализа

Критерии корреляционного анализа

Критерии регрессионного анализа

Литература

1. Вероятность и математическая статистика: Энциклопедия / Под ред. Ю.В.Прохорова. — М.: Большая российская энциклопедия, 2003. — 912 с.
2. Кобзарь А. И. Прикладная математическая статистика. Справочник для инженеров и научных работников. — М.: Физматлит, 2006. — 816 с.

Ссылки

• Statistical hypothesis testing — статья в англоязычной Википедии.

Ошибки первого рода (англ. type I errors, α errors, false positives) и ошибки второго рода (англ. type II errors, β errors, false negatives) в математической статистике — это ключевые понятия задач проверки статистических гипотез. Тем не менее, данные понятия часто используются и в других областях, когда речь идёт о принятии «бинарного» решения (да/нет) на основе некоего критерия (теста, проверки, измерения), который с некоторой вероятностью может давать ложный результат.

Определения

Пусть дана выборка из неизвестного совместного распределения , и поставлена бинарная задача проверки статистических гипотез:

где  — нулевая гипотеза, а  — альтернативная гипотеза. Предположим, что задан статистический критерий

,

сопоставляющий каждой реализации выборки одну из имеющихся гипотез. Тогда возможны следующие четыре ситуации:

1. Распределение выборки соответствует гипотезе , и она точно определена статистическим критерием, то есть .
2. Распределение выборки соответствует гипотезе , но она неверно отвергнута статистическим критерием, то есть .
3. Распределение выборки соответствует гипотезе , и она точно определена статистическим критерием, то есть .
4. Распределение выборки соответствует гипотезе , но она неверно отвергнута статистическим критерием, то есть .

Во втором и четвертом случае говорят, что произошла статистическая ошибка, и её называют ошибкой первого и второго рода соответственно. ^[1][2]

	Верная гипотеза
Результат  применения  критерия		верно принята	неверно принята  (Ошибка второго рода)
	неверно отвергнута  (Ошибка первого рода)	верно отвергнута

О смысле ошибок первого и второго рода

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

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

Термин широко используется в медицине. Например, тесты, предназначенные для диагностики заболеваний, иногда дают положительный результат (т.е. показывают наличие заболевания у пациента), когда на самом деле пациент этим заболеванием не страдает. Такой результат называется ложноположительным.

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

Из-за возможности ложных срабатываний не удаётся полностью автоматизировать борьбу со многими видами угроз. Как правило, вероятность ложного срабатывания коррелирует с вероятностью пропуска события (ошибки второго рода). То есть: чем более чувствительна система, тем больше опасных событий она детектирует и, следовательно, предотвращает. Но при повышении чувствительности неизбежно вырастает и вероятность ложных срабатываний. Поэтому чересчур чувствительно (параноидально) настроенная система защиты может выродиться в свою противоположность и привести к тому, что побочный вред от неё будет превышать пользу.

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

Слово «отрицательный» в данном случае не имеет отношения к желательности или нежелательности самого события.

Термин широко используется в медицине. Например, тесты, предназначенные для диагностики заболеваний, иногда дают отрицательный результат (т.е. показывают отсутствие заболевания у пациента), когда на самом деле пациент страдает этим заболеванием. Такой результат называется ложноотрицательным.

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

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

Вероятности ошибок (уровень значимости и мощность)

Вероятность ошибки первого рода при проверке статистических гипотез называют уровнем значимости и обычно обозначают греческой буквой (отсюда название -errors).

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

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

В статистических тестах обычно приходится идти на компромисс между приемлемым уровнем ошибок первого и второго рода. Зачастую для принятия решения используется пороговое значение, которое может варьироваться с целью сделать тест более строгим или, наоборот, более мягким. Этим пороговым значением является уровень значимости, которым задаются при проверке статистических гипотез. Например, в случае металлодетектора повышение чувствительности прибора приведёт к увеличению риска ошибки первого рода (ложная тревога), а понижение чувствительности — к увеличению риска ошибки второго рода (пропуск запрещённого предмета).

Примеры использования

Радиолокация

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

Компьютеры

Понятия ошибок первого и второго рода широко используются в области компьютеров и программного обеспечения.

Компьютерная безопасность

Наличие уязвимостей в вычислительных системах приводит к тому, что приходится, с одной стороны, решать задачу сохранения целостности компьютерных данных, а с другой стороны — обеспечивать нормальный доступ легальных пользователей к этим данным (см. компьютерная безопасность). Moulton (1983, с.125) отмечает, что в данном контексте возможны следующие нежелательные ситуации:

• когда нарушители классифицируются как авторизованные пользователи (ошибки первого рода)
• когда авторизованные пользователи классифицируются как нарушители (ошибки второго рода)

Фильтрация спама

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

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

Пока не удалось создать антиспамовую систему без корреляции между вероятностью ошибок первого и второго рода. Вероятность пропустить спам у современных систем колеблется в пределах от 1% до 30%. Вероятность ошибочно отвергнуть валидное сообщение — от 0,001 % до 3 %. Выбор системы и её настроек зависит от условий конкретного получателя: для одних получателей риск потерять 1% хорошей почты оценивается как незначительный, для других же потеря даже 0,1% является недопустимой.

Вредоносное программное обеспечение

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

Поиск в компьютерных базах данных

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

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

Оптическое распознавание текстов (OCR)

Разнообразные детектирующие алгоритмы нередко выдают ошибки первого рода. Программное обеспечение оптического распознавания текстов может распознать букву «a» в ситуации, когда на самом деле изображены несколько точек, которые используемый алгоритм расценил как «a».

Досмотр пассажиров и багажа

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

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

Биометрия

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

Массовая медицинская диагностика (скрининг)

В медицинской практике есть существенное различие между скринингом и тестированием:

• Скрининг включает в себя относительно дешёвые тесты, которые проводятся для большой группы людей при отсутствии каких-либо клинических признаков болезни (например, мазок Папаниколау).
• Тестирование подразумевает гораздо более дорогие, зачастую инвазивные, процедуры, которые проводятся только для тех, у кого проявляются клинические признаки заболевания, и которые, в основном, применяются для подтверждения предполагаемого диагноза.

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

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

Возможно, наиболее широкие дискуссии вызывают ошибки первого рода в процедурах скрининга на рак груди (маммография). В США уровень ошибок первого рода в маммограммах достигает 15%, это самый высокий показатель в мире.^[5] Самый низкий уровень наблюдается в Нидерландах, 1%.^[6]

Медицинское тестирование

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

Ошибки второго рода вызывают серьёзные и трудные для понимания проблемы, особенно когда искомое условие является широкораспространённым. Если тест с 10%-ным уровнем ошибок второго рода используется для обследования группы, где вероятность «истинно-положительных» случаев составляет 70%, то многие отрицательные результаты теста окажутся ложными. (См. Теорему Байеса).

Ошибки первого рода также могут вызывать серьёзные и трудные для понимания проблемы. Это происходит, когда искомое условие является редким. Если уровень ошибок первого рода у теста составляет один случай на десять тысяч, но в тестируемой группе образцов (или людей) вероятность «истинно-положительных» случаев составляет в среднем один случай на миллион, то большинство положительных результатов этого теста будут ложными.^[7]

Исследования сверхъестественных явлений

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

См. также

• Статистическая значимость
• Ложноположительный
• Атака второго рода
• Случаи ложного срабатывания систем предупреждения о ракетном нападении
• Receiver_operating_characteristic

Примечания

1. Ошибки первого и второго рода при проверке гипотез.

шибки первого рода (англ. type
I
errors,
α
errors,
false
positives)
и ошибки
второго рода (англ. type
II
errors,
β
errors,
false
negatives)
в математической
статистике —
это ключевые понятия задач проверки
статистических гипотез. Тем не менее,
данные понятия часто используются и в
других областях, когда речь идёт о
принятии «бинарного» решения (да/нет)
на основе некоего критерия (теста,
проверки, измерения), который с некоторой
вероятностью может давать ложный
результат.

[Править]Определения

Пусть дана выборка 
 из
неизвестного совместного распределения 
,
и поставлена бинарная задача проверки
статистических гипотез:

где 
 — нулевая
гипотеза,
а 
 — альтернативная
гипотеза.
Предположим, что задан статистический
критерий

,

сопоставляющий каждой
реализации выборки 
 одну
из имеющихся гипотез. Тогда возможны
следующие четыре ситуации:

1. Распределение 
    выборки 
    соответствует
   гипотезе 
   ,
   и она точно определена статистическим
   критерием, то есть 
   .

2. Распределение 
    выборки 
    соответствует
   гипотезе 
   ,
   но она неверно отвергнута статистическим
   критерием, то есть 
   .

3. Распределение 
    выборки 
    соответствует
   гипотезе 
   ,
   и она точно определена статистическим
   критерием, то есть 
   .

4. Распределение 
    выборки 
    соответствует
   гипотезе 
   ,
   но она неверно отвергнута статистическим
   критерием, то есть 
   .

Во втором и четвертом случае
говорят, что произошла статистическая
ошибка, и её называют ошибкой
первого и второго рода соответственно. ^[1][2]

[Править]о смысле ошибок первого и второго рода

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

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

Термин широко используется в медицине.
Например, тесты, предназначенные для
диагностики заболеваний, иногда дают
положительный результат (т. е. показывают
наличие заболевания у пациента), когда,
на самом деле пациент этим заболеванием
не страдает. Такой результат называется
ложноположительным.

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

Из-за возможности ложных срабатываний
не удаётся полностью автоматизировать
борьбу со многими видами угроз. Как
правило, вероятность ложного срабатывания
коррелирует с вероятностью пропуска
события (ошибки второго рода). То есть,
чем более чувствительна система, тем
больше опасных событий она детектирует
и, следовательно, предотвращает. Но при
повышении чувствительности неизбежно
вырастает и вероятность ложных
срабатываний. Поэтому чересчур
чувствительно (параноидально) настроенная
система защиты может выродиться в свою
противоположность и привести к тому,
что побочный вред от неё будет превышать
пользу.

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

Слово «отрицательный» в данном случае
не имеет отношения к желательности или
нежелательности самого события.

Термин широко используется в медицине.
Например, тесты, предназначенные для
диагностики заболеваний иногда дают
отрицательный результат (т. е. показывают
отсутствие заболевания у пациента),
когда, на самом деле пациент страдает
этим заболеванием. Такой результат
называется ложноотрицательным.

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

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

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

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

Мы воспринимаем ошибки как нечто чуждое, но что если вокруг них и строится наша жизнь?

Как доказать доказательство

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

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

Долгое время никто не мог доказать доказательство компьютера — был проведен слишком большой объем вычислений, для того чтобы можно было их все проверить. С точки зрения «чистой» математики принять такое решение проблемы было сложно — оно противоречило эталону доказательства теорем, использовавшемуся со времен Евклида. Кроме того, математики предположили, что в программе могли быть ошибки. И ошибки в коде действительно были.

В 2004 году Джордж Гонтье из исследовательской лаборатории Microsoft перепроверил доказательство с помощью программы Coq v7.3.1, использующей собственный язык функционального программирования Gallina. Математики задали следующий вопрос: есть ли доказательство того, что программа-проверщик не содержит ошибок? Полной уверенности в этом нет, однако программа была многократно протестирована при выполнении многих других задач. В результате специализированный софт, помогающий математикам, содержит десятки тысяч формальных доказательств.

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

Случайные числа и криптография

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

Проблема поиска случайных чисел интересно затронута в книге Беллоса «Алекс в стране чисел. Необычайное путешествие в волшебный мир математики». Число π долгое время считалось хорошим примером случайности. Конечно, какие-то последовательности в бесконечном числе есть. Так на 17 387 594 880-м месте после запятой можно найти подряд цифры 0123456789. Однако эта последовательность лишь случайность — как показывает эксперимент с подбрасыванием монеты, противоречащие интуиции длинные последовательности являются скорее нормой.

Цифры Пи могут вести себя, как будто они случайны, но на самом деле они предопределены. Например, если бы цифры в числе π были случайны, то шанс, что первая цифра после десятичной запятой будет равна 1, был бы равен всего 10%. Однако же мы с абсолютной определенностью знаем, что там стоит 1; π проявляет случайность не случайно.

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

Переводя вопросы математики в плоскость физики можно достигнуть удивительных результатов. В 1969 году математик Эдвард Торп выяснил (на самом деле этим вопросом он занимался более 10 лет), что стремление казино снизить систематическое отклонение от идеальной случайной статистически приводит к тому, что предсказать движения шарика оказывается проще. Дело в том, что при настройке ось колеса иногда наклоняют — наклона в 0,2 градуса достаточно для того, чтобы на воронкообразной поверхности появился достаточно большой участок, с которого шарик никогда не соскакивает на колесо. Используя эти сведения, можно довести матожидание выигрыша до 0,44 от ставки.

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

На основе чистой математики можно сделать генератор PRNG с очень высокой стойкостью. Например, алгоритм Блюма-Блюма-Шуба (авторы алгоритма чета Блюмов и Майкл Шуб) имеет высокую криптостойкость, основанную на предполагаемой сложности факторизации целых чисел. Алгоритм математически красив:

где M = pq является произведением двух больших простых чисел p и q. На каждом шаге алгоритма выходные данные получаются из X_n путем взятия либо контрольного бита чётности, либо одного или больше наименее значимых бит X_n.

Некоторые математики считают алгоритм ББШ и им подобные потенциально опасными, поскольку задача факторизации целых чисел может оказаться не такой трудной, как предполагается, и на выходе алгоритма будут числа, которые могут быть выявлены при достаточном объеме вычислений. При использовании быстрого квантового алгоритма для факторизации будет достигнуто огромное пространство возможностей поиска уязвимостей криптостойкого шифрования. За примерами далеко ходить не надо. Когда-то сильный алгоритм DES теперь считается недостаточным для многих приложений. Некоторые старые алгоритмы, которые, как все думали, требуют миллиарда лет вычислительного времени, теперь могут быть взломаны через несколько часов (MD4, MD5, SHA1, DES и другие алгоритмы).

В семействе криптостойких генераторов Fortuna (используется в FreeBSD, OpenBSD, Mac OS X и др.) генератор получает псевдослучайные данные через шифрование последовательных натуральных чисел. Исходным ключом становится начальное число, а после каждого запроса происходит обновление ключа: алгоритм генерирует 256 бит псевдослучайных данных с помощью старого ключа и использует полученное значение в качестве нового ключа. Кроме того, блочный шифр в режиме счетчика производит неповторяющиеся 16-байтовые блоки с периодом 2¹²⁸ в то время, как в истинных случайных данных при таких длинах последовательности с большой вероятностью должны встречаться одинаковые значения блоков — как мы видели выше на примере числа Пи. Поэтому для улучшения статистических свойств максимальный размер данных, которые могут быть выданы в ответ на один запрос, ограничивается 2²⁰ байт (при такой длине последовательности вероятность найти одинаковые блоки в истинно случайном потоке составляет порядка 2⁻⁹⁷). Ко всему прочему подмешиваются истинно (возможно) случайные данные — перемещения мыши, время нажатия на клавиши, отклики жестких дисков, шумы звуковой карты и так далее.

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

Возникновение ошибок

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

if ((err = SSLHashSHA1.update(...)) != 0)
goto fail;
goto fail; /* BUG */
if ((err = SSLHashSHA1.final(...)) != 0)
goto fail;
err  =  sslRawVerif(...);
…
fail:
…
return err;

Классическая ошибка SSL/TLS из 2014 года. Дополнительный оператор goto приводит к тому, что устройства iOS и Mac принимают недействительные сертификаты, что делает их восприимчивыми к MITM-атакам. Разработчик случайно добавил одну избыточную инструкцию goto, возможно, через ctrl+c/ctrl+v, дав возможность обходить все проверки сертификатов для соединений SSL/TLS. Эта ошибка существовала более года, в течение которой миллионы устройств были подвержены MITM-атакам. По иронии судьбы, в том же году более серьезная ошибка «goto» была обнаружена в коде проверки сертификата GnuTLS. Причем ошибка существовала более десяти лет.

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

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

Формула модели оценки опционов впервые была выведена Фишером Блэком и Майроном Шоулзом в 1973 году. Опцион — это договор, по которому покупатель товара или ценной бумаги (так называемый базовый актив) получает право (но не обязательство), совершить покупку или продажу данного актива по заранее оговоренной цене в определенный договором момент.

Модель, определяющая теоретическую цену на европейские опционы, подразумевала, что если базовый актив торгуется на рынке, то цена опциона на него неявным образом уже устанавливается самим рынком. Согласно модели Блэка-Шоулза, ключевым элементом определения стоимости опциона является ожидаемая волатильность (изменчивость цены) базового актива. В зависимости от колебания актива, цена на него возрастает или понижается, что прямо пропорционально влияет на стоимость опциона. Таким образом, если известна стоимость опциона, то можно определить уровень волатильности, ожидаемой рынком.

Уравнение выглядит так:

C(S,t) — текущая стоимость опциона в момент t до истечения срока опциона;
S — текущая цена базисной акции;
N(x) — вероятность того, что отклонение будет меньше в условиях стандартного нормального распределения (таким образом и ограничивают область значений для функции стандартного нормального распределения);
K — цена исполнения опциона;
r — безрисковая процентная ставка;
T-t — время до истечения срока опциона (период опциона);
σ — волатильность (квадратный корень из дисперсии) базисной акции.

Уравнение связывает рекомендуемую цену с четырьмя другими величинами. Три могут быть измерены напрямую: время, цена актива, по которому обеспечен опцион, и безрисковая процентная ставка. Четвертая величина — волатильность актива. Это показатель того, насколько изменчива его рыночная стоимость. Уравнение предполагает, что волатильность актива остается неизменной для срока действия опциона, однако это предположение оказывается ошибочным. Волатильность может быть оценена статистическим анализом движения цен, но она не может быть измерена точным, надежным способом, и оценки могут не соответствовать действительности.

Эта модель восходит к 1900 году, когда в докторской диссертации французский математик Луи Башелье предположил, что колебания фондового рынка могут быть моделированы случайным процессом, известным как броуновское движение. В каждый момент времени цена акции увеличивается или уменьшается, и модель предполагает фиксированные вероятности для этих событий. Они могут быть одинаково вероятными или быть более вероятными, чем другие. Их положение соответствует цене акции, двигаясь вверх или вниз наугад. Важнейшими статистическими особенностями броуновского движения являются его среднее и стандартное отклонение. Среднее значение — это краткосрочная средняя цена, которая обычно дрейфует в определенном направлении вверх или вниз. Стандартное отклонение можно рассматривать как среднюю величину, по которой цена отличается от средней, рассчитанной с использованием стандартной статистической формулы. Для цен на акции это называется волатильностью, и она измеряет, насколько неустойчива цена.

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

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

Уравнение Блэка-Шоулза имеет свои корни в математической физике, где величины бесконечно делимы, время течет непрерывно, а переменные плавно меняются. Такие модели могут быть несовместимы с реальной жизнью.

Первородные проблемы вычислений

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

Где проходит разница между двумя событиями с невероятным расчетом полета астероида, показывают ошибки первого рода (false positives) и ошибки второго рода (false negatives) — ключевые понятия задач проверки статистических гипотез.

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

Величину ошибок первого рода можно рассчитать по формуле:

где
F(x) — функция распределения значений измеряемой величины;
a, d — границы интервала, в котором существует вероятность наступления ошибок первого рода;
F(Δ) — функция распределения действительных значений погрешности средств измерений;
-∞, p — границы интервала, в котором погрешность средств измерений не препятствует наступлению ошибки первого рода.

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

Величина ошибки второго рода рассчитывается по формуле:

где
с, a — границы интервала, в котором существует вероятность наступления ошибок второго рода;
p, +∞ — границы интервала, в котором погрешность средств измерений не препятствует наступлению ошибки второго рода.

В математике понятия формируются следующим образом:

• ошибки, где теорема все еще верна, но доказательство было неверным, относятся к первому роду;
• ошибки, когда теорема была ложной, и доказательство также было неверным, относятся ко второму роду.

Иногда возникновение ошибки связано с изменением стандартов доказывания. Например, когда Давидом Гильбертом были обнаружены ошибки в доказательствах Евклида, которые никто раньше не замечал, теоремы евклидовой геометрии все еще оставались правильными, а ошибки возникли из-за того, что Гильберт был современным математиком, думающим в терминах формальных систем (о чем Евклид и не мыслил). В свою очередь сам Гильберт допустил несколько других досадных ошибок: его знаменитый список из 23 кардинальных проблем математики содержит 2, которые не являются корректными математическими проблемами (одна сформулирована слишком расплывчато, чтобы понять, решена она или нет, другая, далекая от решения, — физическая, а не математическая).

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

Маловероятно, что в 21 веке начали рождаться люди, которые кардинально не похожи на своих предков и все поголовно гении. Однако нам кажется, что именно мы — самые умные и то, что придумано нами и есть подлинная картина мира. Но Евклид, например, на основе логики создал научную структуру, в которой его современники не могли найти недостатка. Точно так же мы можем не видеть недостатков в наших математических инструментах.

Неопровержимые данные свидетельствуют о том, что треть всех статей, опубликованных в математических журналах, содержат ошибки — не только незначительные ошибки, но и неправильные теоремы и доказательства. А вслед за математикой следует признать наличие проблем и в программировании. Есть такая шутка (с долей правды), что при переходе от 4000 строк кода Microsoft DOS к десяткам миллионам строк в последующих версиях Windows, количество активных ошибок выросло пропорционально.

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

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

Математики постоянно ошибаются — это нормально

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

Числа Мерсенна, названные в честь математика Марена Мерсенна, исследовавшего их свойства в 17 веке, имеют вид M_n = 2ⁿ -1, где n — натуральное число. Числа такого вида интересны тем, что некоторые из них являются простыми числами. Мерсенн предполагал, что числа 2ⁿ-1 являются простыми для n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 и составными для всех остальных положительных числе n < 257. Позже выяснилось, что Мерсенн допустил пять ошибок: n = 67 и 257 дают составные числа, а n = 61, 89, 107 — простые.

Между теорией Мерсенна и опровержением прошло почти 200 лет.
То, что число 2⁶⁷-1 является произведением двух чисел 193 707 721 и 761 838 257 287 доказал в 1903 году профессор Коул. На вопрос, сколько он потратил времени, чтобы разложить число на множители, Коул ответил: «Все воскресенья в течение трех лет».

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

Проблема Цербера

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

Первая версия протокола была создана в 1983 году в Массачусетском технологическом институте (MIT) в рамках проекта «Афина», основной целью которого была разработка плана по внедрению компьютеров в учебный процесс MIT. Проект был образовательным, но в конечном итоге дал миру несколько программных продуктов, которые используются и сегодня (например, X Window System).

В 1989 году появилась 4-я версия протокола, которая стала общедоступной. Другие крупные проекты по распределенным системам (например, AFS) использовали идеи Kerberos 4 для своих систем аутентификации. Генератор случайных чисел Kerberos в течение нескольких лет широко использовался в различных системах шифрования. И в течение десяти лет никто не обращал внимания на гигантскую дыру, позволявшую попасть в любую систему, использовавшую модуль Kerberos.

Предполагалось, что программа должна выбирать ключ случайным образом из огромного массива чисел, но оказалось, генератор случайных чисел выбирал из небольшого набора. 10 лет исследователи не знали, что в Kerberos 4 рандомные числа вовсе не рандомные, а секретные ключи можно получить в течение нескольких секунд.

Kerberos 4 использовал функцию UNIX для создания случайных 56-разрядных DES-ключей. Неверная реализация алгоритма, используемого для генерации псевдослучайных чисел, привела к тому, что любая последовательность чисел ключа имела энтропию всего 32 бита, из которых первые 12 бит редко менялись и были предсказуемы. В результате у Kerberos 4 было только около 220 (или примерно один миллион) возможных ключей.

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

Ошибка, которая ничего не значит

Иногда ошибка вовсе не означает, что от уравнения или доказательства нужно отказаться.

Принцип Дирихле — знаменитое утверждение, сформулированное немецким математиком Дирихле в 1834 году, устанавливающее связь между объектами («голубями») и контейнерами («клетками») при выполнении определенных условий, звучит примерно так:

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

Переведем на язык математики:

Пусть в n клетках сидит не менее kn + 1 голубей, тогда в какой-то из клеток сидит, по крайней мере, k + 1 голубь.

Звучит интересно, но самое интересное происходит в другой области. В математической физике принцип Дирихле относится к теории потенциала и формулируется следующим образом: если функция u(x) есть решение уравнения Пуассона

Δ u+f=0

в области Ω⊂Rⁿ с граничным условием: u = g на границе Ω, то u может быть найдена как решение вариационной задачи: найти минимум

среди всех дважды дифференцируемых функций v таких, что v=g на границе Ω.

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

Так как сам принцип оказался неверным, но красивым и нужным, математикам пришлось придумывать различные ограничения на кривые и граничные условия, устраняя возражение Вейерштрасса.

Та самая точка/запятая

О проблеме с плавающей точкой известно много и, на данный момент, это не такая уж проблема. Но коротко напомним: бинарная математика с трудом точно отражает определенные числа. Например, бесконечные числа невозможно точно выразить в двоичном формате. При делении 2/3 на компьютере вы получите ряд цифр: 0,6666666666666667.

Обратите внимание на последнюю цифру 7. Во время войны в Персидском заливе компьютер противоракетной системы Patriot из-за схожей арифметики пропустил удар, в результате которого погибли 28 человек и были ранены еще 100. Причиной сбоя было неточное вычисление времени. Системное время компьютера хранилось в 24-битном регистре с фиксированной точкой с точностью до одной десятой секунды. Таким образом, значение 1/10, которое имеет не заканчивающееся двоичное разложение, было прервано на 24 бите после точки счисления.

Система Patriot проработала около 100 часов. За это время ошибка составила примерно 0,34 секунды. Двоичное представление 1/10 = 0,0001100110011001100110011001100… В 24 битном регистре это выглядело как 0,00011001100110011001100, внося ошибку, равную 0,0000000000000000000000011001100… в двоичном исчислении или примерно 0,000000095 в десятичном. За сто часов работы получилось 0,000000095 × 100 × 60 × 60 × 10 = 0,34 секунды.

Ракета летела со скоростью 1676 метров в секунду, и прошла за 0,34 секунды больше полукилометра, опередив радиус поражения противоракетного комплекса.

Число с плавающей точкой математически записывается так:

(-1)^s × M × B^E, где s — знак, B — основание, E — порядок, а M — мантисса.

Бесконечность при делении разработчики определили исходя из существования пределов, когда делимое и делитель стремится к какому-то числу: c/0 = ±∞ (3/0 = +∞, а -3/0 = -∞, к тому же 1/∞ = 0), так как если делимое стремится к константе, а делитель к нулю, предел равен бесконечности. При 0/0 предел не существует, поэтому результатом будет неопределенность NaN.

Расчеты с плавающей точкой могут отражаться по-разному в зависимости от того, где они хранятся. Внутренние регистры FPU некоторых процессоров имеют другую длину, чем оперативная память, что может привести к разным результатам одной и той же арифметической операции на GPU и CPU.

Выработаны методы, позволяющие устранять эти известные неточности, однако то, что работает на домашнем компьютере, не обязательно будет эффективно использоваться на суперкомпьютере. Решения проблемы с плавающей точкой для высоконагруженных систем также известны. Исследователи Sun предлагают интервальную арифметику, которая ловит математически неправильное число между двумя другими правильными числами. В 1990 году появился метод пары Wilf-Zeilberger, позволяющий выдавать точные результаты без ошибок округления, даже оперируя десятками тысяч знаков после запятой.

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

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

DO 17 I = 1, 10

было интерпретировано как

DO17I = 1.10

то есть как присвоение переменной DO17I — так как пробельные символы не учитываются языком.

Идеальный код

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

В подходе «давайте сделаем программу по тем же принципам, на которых математики создают уравнение» нет ничего нового. Еще в 1973 году нидерландский ученый Эдсгер Дейкстра предложил идею безошибочного кода, оформленную в виде книги 1976 года «Дисциплина программирования». Идея Дейкстры проста: программа имеет дело с математическими объектами с рядом заданных характеристик. Фактически код описывает математическую модель, оперирующую параметрами в заданных диапазонах. Выход за пределы параметра означает отмену операции. Программа также должна обладать всей полнотой данных.

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

Дейкстра много раз говорил о доказуемости компьютерных программ как абстрактных сущностей. В качестве следствия он отмечал, что обычного тестирования для программ недостаточно. Например, он указывал на невозможность проверить функцию умножения f (x, y) = x * y для любых больших значений x и y во всех диапазонах x и y. Правда, это утверждение относилось к 70-м годам прошлого века, но в одном с ученым можно согласиться и сейчас: программы содержат неустранимые ошибки.

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

Проблема не только для спутников, но и для наземной электроники (с учетом уменьшения размеров транзисторов). В 1990-х годах IBM исследовала воздействие космических лучей на электронику. Оказалось, что из-за излучения компьютеры получают около одной ошибки на 256 мегабайт оперативной памяти в месяц. Это означает, что есть вероятность 3,7 × 10^-9 байт в месяц или 1,4 × 10^-15 за байт в секунду. Если ваша программа работает в течение 1 минуты и занимает 20 МБ ОЗУ, то вероятность сбоя будет:

1 – (1 – 1,4,e-15)60 × 20 × 1024² = 1,8e-6

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

Точность вычислений

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

(Замечание. Есть маргинальное мнение, поддерживаемое рядом ученых, что вся теория струн — это одна большая ошибка, на которой непонятно зачем строится современная теоретическая физика. Это мнение активно продвигает физик Ли Смолин, занимающий 21-е место в списке 100 самых выдающихся мыслителей мира по версии журнала Foreign Policy. Смолин сам известен пионерскими работами по теории струн, однако позже кардинально изменил свое мнение и сейчас является сторонником «альтернативы» — теории петлевой квантовой гравитации. Кроме того, ученый указывает на несправедливый перевес интереса академической науки в сторону струнного подхода в ущерб всем конкурентам, среди которых техниколор, преонные модели, суперсимметрия, теория твисторов, причинные ряды, супергравитация, динамические триангуляции и другие).

Откуда берутся ошибки? Они возникают всюду и по любому поводу.

Упрощение, округление и сокращение — злейшие враги. Во всех учебниках по математике и физике вы найдете задачу, начинающуюся со следующих слов: частица, падающая под действием силы тяжести, подвержена постоянному ускорению 9,8 м/с²…

С точки зрения ученого здесь написана полная чушь. Даже не будем касаться того факта, что ускорение свободного падения на поверхности Земли варьируется от 9,780 м/с² до 9,832 м/с², а стандартное значение, принятое при построении систем единиц, 9,80665 м/с². Посмотрим на саму цифру 9,8. Означает ли она, что ускорение ближе к 9,8, чем к 9,9 или 9,7? Означает ли это, что ускорение ближе к 9,80000, чем к 9,80001 или 9,79999?

Точность цифр, зависящая он контекста, может влиять не только на задачи в учебнике, но и на человеческую жизнь.

В 2008 году бортовой компьютер самолета А-330 авиакомпании Qantas через 3 часа после взлета неожиданно дал сбой, в результате чего самолет свалился в пике. Многих пассажиров швырнуло в потолок, но пилот смог взять управление на себя и благополучно посадить борт.

Что произошло? На самолете А-330, как и на многих других, установлено три компьютера (FCPC), которые получают данные от трех инерциально-навигационных систем (ADIRU). В ADIRU произошел аппаратный сбой в процессоре Intel, в результате которого вместо одних параметров полета стали выдаваться совершенно другие. Однако компьютер сходу ничего не заметил. (Кстати, есть мнение, что сбой в процессоре вызвали уже упоминавшиеся космические лучи. Круговорот ошибок).

Для вычисления угла атаки использовалось среднее значение с двух сенсоров: если значение сильно отличалось от среднего, алгоритм использовал крайнее допустимое значение на протяжении 1,2 секунды. Если на протяжении 1 секунды ситуация не менялась — этот вход отключался и больше не использовался. Через секунду после скачка значение было правильным, но через 1,2 секунды опять произошел скачок и это значение пометилось как допустимое. В результате ошибка образовалась из-за разницы всего в 0,2 секунды.

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

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

Есть ли вообще с точки зрения математики ограничения на количество необходимой выборки для устранения ошибок? Есть — это здравый смысл.

Предотвращение последствий

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

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

Используются языки, библиотеки или фреймворки, которые упрощают обработку чисел без неожиданных последствий. В тех языках, где возможно допустить ошибку в обработке уравнений, используются библиотеки безопасности (такие как SafeInt (C ++) или IntegerLib (C или C ++)), помогающие предотвращать переполнение емкости целочисленных переменных и исключить другие ошибки, возникающие в ходе выполнения математических операций.
Есть ли у нас основания предполагать, что математика внутри себя содержит более впечатляющие проблемы? Да, более того, математика содержит внутри не что-то «потенциально опасное», а настоящие бомбы замедленного действия, о некоторых из которых мы еще не знаем.

Прямо сейчас можно сказать, что математический фундамент цивилизации содержит несколько потенциальных ошибок, которые могут ощутимо сказаться на IT области. Если такие широко распространенные гипотезы, как P ≠ NP или гипотеза Римана, окажутся ложными, то, поскольку они находятся в основе многих современных правдоподобных предположений и доказательств, может произойти математический Холокост. Если P не равно NP, значит, все в порядке. Если P = NP, появятся способы относительно быстро решать NP-полные проблемы: криптография, основанная на RSA или DES/AES, окажется бесполезной.

Чистую математику можно сравнить с обычным программированием. Программист напишет короткую программу — 100 строк кода — за небольшой промежуток времени без особых проблем. Отладка займет больше времени, чем непосредственно создание кода, но она не повлечет за собой суицидальные мысли. Однако если неопытный программист обязуется написать немного более длинную программу, скажем, 1000 строк, последуют неутешительные результаты. Процесс отладки становится эмоциональным кошмаром, и можно засомневаться в собственном здравомыслии.

Крайне небольшой процент математиков подвергают доказательства любых своих теорем столь пристальному вниманию. И хотя можно быть уверенным абсолютно, что доказательства верны (по крайней мере, значимые), вера нуждается в обосновании. Сравните это с процессом отладки. В конце отладки мы довольны нашей программой из-за согласованности результатов, которую она дает, а не потому, что мы считаем, что мы доказали ее правильность — ведь мы делали это по крайней мере двадцать раз при отладке, и каждый раз мы ошибались. Почему не двадцать первый? На самом деле мы остро осознаем, что наша бедная программа была протестирована только с ограниченным набором ресурсов. Если программа достаточно важна, она будет отлаживаться до тех пор, пока не будет полностью защищенной.

Результат уравнения

Ошибки никуда не денутся, но никакой роли в получении верного результата они играть не будут.

Скорее всего.

Математика (и таящиеся в ней ошибки) и алгоритмы достигли такого уровня, что если человек понимает стоящую перед ним математическую задачу, то ее можно считать тривиальной. Очень долгое время казалось, что математическое доказательство — это всего лишь инструмент, используемый одним человеком для того, чтобы убедить другого человека в истинности математического утверждения (Steven G. Krantz, «The Proof is in the Pudding»), сейчас же мы вступаем в фазу, когда одна программа будет доказывать свою правоту другим программам.

Статья основана на следующих материалах:

How Did Software Get So Reliable Without Proof?
An Empirical Study on the Correctness of Formally Verified Distributed Systems
The misfortunes of a trio of mathematicians using Computer Algebra Systems. Can we trust in them?
The mathematical equation that caused the banks to crash
CWE-682: Incorrect Calculation
Experimental Errors and Error Analysis
Misplaced Trust: Kerberos 4 Session Keys
The Patriot Missile Failure
Чарльз Сейфе. «Ноль: биография опасной идеи»
Алекс Беллос. «Красота в квадрате»
Type I and Type II Errors and Their Application
Cryptographic Right Answers
Mathematical Modelling In Software Reliability

Оши́бка пе́рвого ро́да (α-ошибка, ложноположительное заключение) — ситуация, когда отвергнута верная нулевая гипотеза (об отсутствии связи между явлениями или искомого эффекта).

Оши́бка второ́го ро́да (β-ошибка, ложноотрицательное заключение) — ситуация, когда принята неверная нулевая гипотеза.

This article is about erroneous outcomes of statistical tests. For closely related concepts in binary classification and testing generally, see false positives and false negatives.

In statistical hypothesis testing, a type I error is the mistaken rejection of an actually true null hypothesis (also known as a «false positive» finding or conclusion; example: «an innocent person is convicted»), while a type II error is the failure to reject a null hypothesis that is actually false (also known as a «false negative» finding or conclusion; example: «a guilty person is not convicted»).^[1] Much of statistical theory revolves around the minimization of one or both of these errors, though the complete elimination of either is a statistical impossibility if the outcome is not determined by a known, observable causal process.
By selecting a low threshold (cut-off) value and modifying the alpha (α) level, the quality of the hypothesis test can be increased.^[2] The knowledge of type I errors and type II errors is widely used in medical science, biometrics and computer science.^{[clarification needed]}

Intuitively, type I errors can be thought of as errors of commission, i.e. the researcher unluckily concludes that something is the fact. For instance, consider a study where researchers compare a drug with a placebo. If the patients who are given the drug get better than the patients given the placebo by chance, it may appear that the drug is effective, but in fact the conclusion is incorrect.
In reverse, type II errors are errors of omission. In the example above, if the patients who got the drug did not get better at a higher rate than the ones who got the placebo, but this was a random fluke, that would be a type II error. The consequence of a type II error depends on the size and direction of the missed determination and the circumstances. An expensive cure for one in a million patients may be inconsequential even if it truly is a cure.

Definition[edit]

Statistical background[edit]

In statistical test theory, the notion of a statistical error is an integral part of hypothesis testing. The test goes about choosing about two competing propositions called null hypothesis, denoted by H₀ and alternative hypothesis, denoted by H₁. This is conceptually similar to the judgement in a court trial. The null hypothesis corresponds to the position of the defendant: just as he is presumed to be innocent until proven guilty, so is the null hypothesis presumed to be true until the data provide convincing evidence against it. The alternative hypothesis corresponds to the position against the defendant. Specifically, the null hypothesis also involves the absence of a difference or the absence of an association. Thus, the null hypothesis can never be that there is a difference or an association.

If the result of the test corresponds with reality, then a correct decision has been made. However, if the result of the test does not correspond with reality, then an error has occurred. There are two situations in which the decision is wrong. The null hypothesis may be true, whereas we reject H₀. On the other hand, the alternative hypothesis H₁ may be true, whereas we do not reject H₀. Two types of error are distinguished: type I error and type II error.^[3]

Type I error[edit]

The first kind of error is the mistaken rejection of a null hypothesis as the result of a test procedure. This kind of error is called a type I error (false positive) and is sometimes called an error of the first kind. In terms of the courtroom example, a type I error corresponds to convicting an innocent defendant.

Type II error[edit]

The second kind of error is the mistaken failure to reject the null hypothesis as the result of a test procedure. This sort of error is called a type II error (false negative) and is also referred to as an error of the second kind. In terms of the courtroom example, a type II error corresponds to acquitting a criminal.^[4]

Crossover error rate[edit]

The crossover error rate (CER) is the point at which type I errors and type II errors are equal. A system with a lower CER value provides more accuracy than a system with a higher CER value.

False positive and false negative[edit]

In terms of false positives and false negatives, a positive result corresponds to rejecting the null hypothesis, while a negative result corresponds to failing to reject the null hypothesis; «false» means the conclusion drawn is incorrect. Thus, a type I error is equivalent to a false positive, and a type II error is equivalent to a false negative.

Table of error types[edit]

Tabularised relations between truth/falseness of the null hypothesis and outcomes of the test:^[5]

Error rate[edit]

A perfect test would have zero false positives and zero false negatives. However, statistical methods are probabilistic, and it cannot be known for certain whether statistical conclusions are correct. Whenever there is uncertainty, there is the possibility of making an error. Considering this nature of statistics science, all statistical hypothesis tests have a probability of making type I and type II errors.^[6]

• The type I error rate is the probability of rejecting the null hypothesis given that it is true. The test is designed to keep the type I error rate below a prespecified bound called the significance level, usually denoted by the Greek letter α (alpha) and is also called the alpha level. Usually, the significance level is set to 0.05 (5%), implying that it is acceptable to have a 5% probability of incorrectly rejecting the true null hypothesis.^[7]
• The rate of the type II error is denoted by the Greek letter β (beta) and related to the power of a test, which equals 1−β.^[8]

These two types of error rates are traded off against each other: for any given sample set, the effort to reduce one type of error generally results in increasing the other type of error.^[9]

The quality of hypothesis test[edit]

The same idea can be expressed in terms of the rate of correct results and therefore used to minimize error rates and improve the quality of hypothesis test. To reduce the probability of committing a type I error, making the alpha value more stringent is quite simple and efficient. To decrease the probability of committing a type II error, which is closely associated with analyses’ power, either increasing the test’s sample size or relaxing the alpha level could increase the analyses’ power.^[10] A test statistic is robust if the type I error rate is controlled.

Varying different threshold (cut-off) value could also be used to make the test either more specific or more sensitive, which in turn elevates the test quality. For example, imagine a medical test, in which an experimenter might measure the concentration of a certain protein in the blood sample. The experimenter could adjust the threshold (black vertical line in the figure) and people would be diagnosed as having diseases if any number is detected above this certain threshold. According to the image, changing the threshold would result in changes in false positives and false negatives, corresponding to movement on the curve.^[11]

Example[edit]

Since in a real experiment it is impossible to avoid all type I and type II errors, it is important to consider the amount of risk one is willing to take to falsely reject H₀ or accept H₀. The solution to this question would be to report the p-value or significance level α of the statistic. For example, if the p-value of a test statistic result is estimated at 0.0596, then there is a probability of 5.96% that we falsely reject H₀. Or, if we say, the statistic is performed at level α, like 0.05, then we allow to falsely reject H₀ at 5%. A significance level α of 0.05 is relatively common, but there is no general rule that fits all scenarios.

Vehicle speed measuring[edit]

The speed limit of a freeway in the United States is 120 kilometers per hour. A device is set to measure the speed of passing vehicles. Suppose that the device will conduct three measurements of the speed of a passing vehicle, recording as a random sample X₁, X₂, X₃. The traffic police will or will not fine the drivers depending on the average speed . That is to say, the test statistic

In addition, we suppose that the measurements X₁, X₂, X₃ are modeled as normal distribution N(μ,4). Then, T should follow N(μ,4/3) and the parameter μ represents the true speed of passing vehicle. In this experiment, the null hypothesis H₀ and the alternative hypothesis H₁ should be

H₀: μ=120     against      H₁: μ₁>120.

If we perform the statistic level at α=0.05, then a critical value c should be calculated to solve

According to change-of-units rule for the normal distribution. Referring to Z-table, we can get

Here, the critical region. That is to say, if the recorded speed of a vehicle is greater than critical value 121.9, the driver will be fined. However, there are still 5% of the drivers are falsely fined since the recorded average speed is greater than 121.9 but the true speed does not pass 120, which we say, a type I error.

The type II error corresponds to the case that the true speed of a vehicle is over 120 kilometers per hour but the driver is not fined. For example, if the true speed of a vehicle μ=125, the probability that the driver is not fined can be calculated as

which means, if the true speed of a vehicle is 125, the driver has the probability of 0.36% to avoid the fine when the statistic is performed at level 125 since the recorded average speed is lower than 121.9. If the true speed is closer to 121.9 than 125, then the probability of avoiding the fine will also be higher.

The tradeoffs between type I error and type II error should also be considered. That is, in this case, if the traffic police do not want to falsely fine innocent drivers, the level α can be set to a smaller value, like 0.01. However, if that is the case, more drivers whose true speed is over 120 kilometers per hour, like 125, would be more likely to avoid the fine.

Etymology[edit]

In 1928, Jerzy Neyman (1894–1981) and Egon Pearson (1895–1980), both eminent statisticians, discussed the problems associated with «deciding whether or not a particular sample may be judged as likely to have been randomly drawn from a certain population»:^[12] and, as Florence Nightingale David remarked, «it is necessary to remember the adjective ‘random’ [in the term ‘random sample’] should apply to the method of drawing the sample and not to the sample itself».^[13]

They identified «two sources of error», namely:

(a) the error of rejecting a hypothesis that should have not been rejected, and

(b) the error of failing to reject a hypothesis that should have been rejected.

In 1930, they elaborated on these two sources of error, remarking that:

…in testing hypotheses two considerations must be kept in view, we must be able to reduce the chance of rejecting a true hypothesis to as low a value as desired; the test must be so devised that it will reject the hypothesis tested when it is likely to be false.

In 1933, they observed that these «problems are rarely presented in such a form that we can discriminate with certainty between the true and false hypothesis» . They also noted that, in deciding whether to fail to reject, or reject a particular hypothesis amongst a «set of alternative hypotheses», H₁, H₂…, it was easy to make an error:

…[and] these errors will be of two kinds:

(I) we reject H₀ [i.e., the hypothesis to be tested] when it is true,^[14]

(II) we fail to reject H₀ when some alternative hypothesis H_A or H₁ is true. (There are various notations for the alternative).

In all of the papers co-written by Neyman and Pearson the expression H₀ always signifies «the hypothesis to be tested».

In the same paper they call these two sources of error, errors of type I and errors of type II respectively.^[15]

[edit]

Null hypothesis[edit]

It is standard practice for statisticians to conduct tests in order to determine whether or not a «speculative hypothesis» concerning the observed phenomena of the world (or its inhabitants) can be supported. The results of such testing determine whether a particular set of results agrees reasonably (or does not agree) with the speculated hypothesis.

On the basis that it is always assumed, by statistical convention, that the speculated hypothesis is wrong, and the so-called «null hypothesis» that the observed phenomena simply occur by chance (and that, as a consequence, the speculated agent has no effect) – the test will determine whether this hypothesis is right or wrong. This is why the hypothesis under test is often called the null hypothesis (most likely, coined by Fisher (1935, p. 19)), because it is this hypothesis that is to be either nullified or not nullified by the test. When the null hypothesis is nullified, it is possible to conclude that data support the «alternative hypothesis» (which is the original speculated one).

The consistent application by statisticians of Neyman and Pearson’s convention of representing «the hypothesis to be tested» (or «the hypothesis to be nullified») with the expression H₀ has led to circumstances where many understand the term «the null hypothesis» as meaning «the nil hypothesis» – a statement that the results in question have arisen through chance. This is not necessarily the case – the key restriction, as per Fisher (1966), is that «the null hypothesis must be exact, that is free from vagueness and ambiguity, because it must supply the basis of the ‘problem of distribution,’ of which the test of significance is the solution.»^[16] As a consequence of this, in experimental science the null hypothesis is generally a statement that a particular treatment has no effect; in observational science, it is that there is no difference between the value of a particular measured variable, and that of an experimental prediction.^{[citation needed]}

Statistical significance[edit]

If the probability of obtaining a result as extreme as the one obtained, supposing that the null hypothesis were true, is lower than a pre-specified cut-off probability (for example, 5%), then the result is said to be statistically significant and the null hypothesis is rejected.

British statistician Sir Ronald Aylmer Fisher (1890–1962) stressed that the «null hypothesis»:

… is never proved or established, but is possibly disproved, in the course of experimentation. Every experiment may be said to exist only in order to give the facts a chance of disproving the null hypothesis.

— Fisher, 1935, p.19

Application domains[edit]

Medicine[edit]

In the practice of medicine, the differences between the applications of screening and testing are considerable.

Medical screening[edit]

Screening involves relatively cheap tests that are given to large populations, none of whom manifest any clinical indication of disease (e.g., Pap smears).

Testing involves far more expensive, often invasive, procedures that are given only to those who manifest some clinical indication of disease, and are most often applied to confirm a suspected diagnosis.

For example, most states in the USA require newborns to be screened for phenylketonuria and hypothyroidism, among other congenital disorders.

Hypothesis: «The newborns have phenylketonuria and hypothyroidism»

Null Hypothesis (H₀): «The newborns do not have phenylketonuria and hypothyroidism»,

Type I error (false positive): The true fact is that the newborns do not have phenylketonuria and hypothyroidism but we consider they have the disorders according to the data.

Type II error (false negative): The true fact is that the newborns have phenylketonuria and hypothyroidism but we consider they do not have the disorders according to the data.

Although they display a high rate of false positives, the screening tests are considered valuable because they greatly increase the likelihood of detecting these disorders at a far earlier stage.

The simple blood tests used to screen possible blood donors for HIV and hepatitis have a significant rate of false positives; however, physicians use much more expensive and far more precise tests to determine whether a person is actually infected with either of these viruses.

Perhaps the most widely discussed false positives in medical screening come from the breast cancer screening procedure mammography. The US rate of false positive mammograms is up to 15%, the highest in world. One consequence of the high false positive rate in the US is that, in any 10-year period, half of the American women screened receive a false positive mammogram. False positive mammograms are costly, with over $100 million spent annually in the U.S. on follow-up testing and treatment. They also cause women unneeded anxiety. As a result of the high false positive rate in the US, as many as 90–95% of women who get a positive mammogram do not have the condition. The lowest rate in the world is in the Netherlands, 1%. The lowest rates are generally in Northern Europe where mammography films are read twice and a high threshold for additional testing is set (the high threshold decreases the power of the test).

The ideal population screening test would be cheap, easy to administer, and produce zero false-negatives, if possible. Such tests usually produce more false-positives, which can subsequently be sorted out by more sophisticated (and expensive) testing.

Medical testing[edit]

False negatives and false positives are significant issues in medical testing.

Hypothesis: «The patients have the specific disease».

Null hypothesis (H₀): «The patients do not have the specific disease».

Type I error (false positive): «The true fact is that the patients do not have a specific disease but the physicians judges the patients was ill according to the test reports».

False positives can also produce serious and counter-intuitive problems when the condition being searched for is rare, as in screening. If a test has a false positive rate of one in ten thousand, but only one in a million samples (or people) is a true positive, most of the positives detected by that test will be false. The probability that an observed positive result is a false positive may be calculated using Bayes’ theorem.

Type II error (false negative): «The true fact is that the disease is actually present but the test reports provide a falsely reassuring message to patients and physicians that the disease is absent».

False negatives produce serious and counter-intuitive problems, especially when the condition being searched for is common. If a test with a false negative rate of only 10% is used to test a population with a true occurrence rate of 70%, many of the negatives detected by the test will be false.

This sometimes leads to inappropriate or inadequate treatment of both the patient and their disease. A common example is relying on cardiac stress tests to detect coronary atherosclerosis, even though cardiac stress tests are known to only detect limitations of coronary artery blood flow due to advanced stenosis.

Biometrics[edit]

Biometric matching, such as for fingerprint recognition, facial recognition or iris recognition, is susceptible to type I and type II errors.

Hypothesis: «The input does not identify someone in the searched list of people»

Null hypothesis: «The input does identify someone in the searched list of people»

Type I error (false reject rate): «The true fact is that the person is someone in the searched list but the system concludes that the person is not according to the data».

Type II error (false match rate): «The true fact is that the person is not someone in the searched list but the system concludes that the person is someone whom we are looking for according to the data».

The probability of type I errors is called the «false reject rate» (FRR) or false non-match rate (FNMR), while the probability of type II errors is called the «false accept rate» (FAR) or false match rate (FMR).

If the system is designed to rarely match suspects then the probability of type II errors can be called the «false alarm rate». On the other hand, if the system is used for validation (and acceptance is the norm) then the FAR is a measure of system security, while the FRR measures user inconvenience level.

Security screening[edit]

False positives are routinely found every day in airport security screening, which are ultimately visual inspection systems. The installed security alarms are intended to prevent weapons being brought onto aircraft; yet they are often set to such high sensitivity that they alarm many times a day for minor items, such as keys, belt buckles, loose change, mobile phones, and tacks in shoes.

Here, the null hypothesis is that the item is not a weapon, while the alternative hypothesis is that the item is a weapon.

A type I error (false positive): «The true fact is that the item is not a weapon but the system still alarms».

Type II error (false negative) «The true fact is that the item is a weapon but the system keeps silent at this time».

The ratio of false positives (identifying an innocent traveler as a terrorist) to true positives (detecting a would-be terrorist) is, therefore, very high; and because almost every alarm is a false positive, the positive predictive value of these screening tests is very low.

The relative cost of false results determines the likelihood that test creators allow these events to occur. As the cost of a false negative in this scenario is extremely high (not detecting a bomb being brought onto a plane could result in hundreds of deaths) whilst the cost of a false positive is relatively low (a reasonably simple further inspection) the most appropriate test is one with a low statistical specificity but high statistical sensitivity (one that allows a high rate of false positives in return for minimal false negatives).

Computers[edit]

The notions of false positives and false negatives have a wide currency in the realm of computers and computer applications, including computer security, spam filtering, Malware, Optical character recognition and many others.

For example, in the case of spam filtering the hypothesis here is that the message is a spam.

Thus, null hypothesis: «The message is not a spam».

Type I error (false positive): «Spam filtering or spam blocking techniques wrongly classify a legitimate email message as spam and, as a result, interferes with its delivery».

While most anti-spam tactics can block or filter a high percentage of unwanted emails, doing so without creating significant false-positive results is a much more demanding task.

Type II error (false negative): «Spam email is not detected as spam, but is classified as non-spam». A low number of false negatives is an indicator of the efficiency of spam filtering.

See also[edit]

References[edit]

Bibliography[edit]

External links[edit]

• Bias and Confounding – presentation by Nigel Paneth, Graduate School of Public Health, University of Pittsburgh

This article is about erroneous outcomes of statistical tests. For closely related concepts in binary classification and testing generally, see false positives and false negatives.

In statistical hypothesis testing, a type I error is the mistaken rejection of an actually true null hypothesis (also known as a «false positive» finding or conclusion; example: «an innocent person is convicted»), while a type II error is the failure to reject a null hypothesis that is actually false (also known as a «false negative» finding or conclusion; example: «a guilty person is not convicted»).^[1] Much of statistical theory revolves around the minimization of one or both of these errors, though the complete elimination of either is a statistical impossibility if the outcome is not determined by a known, observable causal process.
By selecting a low threshold (cut-off) value and modifying the alpha (α) level, the quality of the hypothesis test can be increased.^[2] The knowledge of type I errors and type II errors is widely used in medical science, biometrics and computer science.^{[clarification needed]}

Intuitively, type I errors can be thought of as errors of commission, i.e. the researcher unluckily concludes that something is the fact. For instance, consider a study where researchers compare a drug with a placebo. If the patients who are given the drug get better than the patients given the placebo by chance, it may appear that the drug is effective, but in fact the conclusion is incorrect.
In reverse, type II errors are errors of omission. In the example above, if the patients who got the drug did not get better at a higher rate than the ones who got the placebo, but this was a random fluke, that would be a type II error. The consequence of a type II error depends on the size and direction of the missed determination and the circumstances. An expensive cure for one in a million patients may be inconsequential even if it truly is a cure.

Definition[edit]

Statistical background[edit]

In statistical test theory, the notion of a statistical error is an integral part of hypothesis testing. The test goes about choosing about two competing propositions called null hypothesis, denoted by H₀ and alternative hypothesis, denoted by H₁. This is conceptually similar to the judgement in a court trial. The null hypothesis corresponds to the position of the defendant: just as he is presumed to be innocent until proven guilty, so is the null hypothesis presumed to be true until the data provide convincing evidence against it. The alternative hypothesis corresponds to the position against the defendant. Specifically, the null hypothesis also involves the absence of a difference or the absence of an association. Thus, the null hypothesis can never be that there is a difference or an association.

If the result of the test corresponds with reality, then a correct decision has been made. However, if the result of the test does not correspond with reality, then an error has occurred. There are two situations in which the decision is wrong. The null hypothesis may be true, whereas we reject H₀. On the other hand, the alternative hypothesis H₁ may be true, whereas we do not reject H₀. Two types of error are distinguished: type I error and type II error.^[3]

Type I error[edit]

The first kind of error is the mistaken rejection of a null hypothesis as the result of a test procedure. This kind of error is called a type I error (false positive) and is sometimes called an error of the first kind. In terms of the courtroom example, a type I error corresponds to convicting an innocent defendant.

Type II error[edit]

The second kind of error is the mistaken failure to reject the null hypothesis as the result of a test procedure. This sort of error is called a type II error (false negative) and is also referred to as an error of the second kind. In terms of the courtroom example, a type II error corresponds to acquitting a criminal.^[4]

Crossover error rate[edit]

The crossover error rate (CER) is the point at which type I errors and type II errors are equal. A system with a lower CER value provides more accuracy than a system with a higher CER value.

False positive and false negative[edit]

In terms of false positives and false negatives, a positive result corresponds to rejecting the null hypothesis, while a negative result corresponds to failing to reject the null hypothesis; «false» means the conclusion drawn is incorrect. Thus, a type I error is equivalent to a false positive, and a type II error is equivalent to a false negative.

Table of error types[edit]

Tabularised relations between truth/falseness of the null hypothesis and outcomes of the test:^[5]

Error rate[edit]

A perfect test would have zero false positives and zero false negatives. However, statistical methods are probabilistic, and it cannot be known for certain whether statistical conclusions are correct. Whenever there is uncertainty, there is the possibility of making an error. Considering this nature of statistics science, all statistical hypothesis tests have a probability of making type I and type II errors.^[6]

• The type I error rate is the probability of rejecting the null hypothesis given that it is true. The test is designed to keep the type I error rate below a prespecified bound called the significance level, usually denoted by the Greek letter α (alpha) and is also called the alpha level. Usually, the significance level is set to 0.05 (5%), implying that it is acceptable to have a 5% probability of incorrectly rejecting the true null hypothesis.^[7]
• The rate of the type II error is denoted by the Greek letter β (beta) and related to the power of a test, which equals 1−β.^[8]

These two types of error rates are traded off against each other: for any given sample set, the effort to reduce one type of error generally results in increasing the other type of error.^[9]

The quality of hypothesis test[edit]

The same idea can be expressed in terms of the rate of correct results and therefore used to minimize error rates and improve the quality of hypothesis test. To reduce the probability of committing a type I error, making the alpha value more stringent is quite simple and efficient. To decrease the probability of committing a type II error, which is closely associated with analyses’ power, either increasing the test’s sample size or relaxing the alpha level could increase the analyses’ power.^[10] A test statistic is robust if the type I error rate is controlled.

Varying different threshold (cut-off) value could also be used to make the test either more specific or more sensitive, which in turn elevates the test quality. For example, imagine a medical test, in which an experimenter might measure the concentration of a certain protein in the blood sample. The experimenter could adjust the threshold (black vertical line in the figure) and people would be diagnosed as having diseases if any number is detected above this certain threshold. According to the image, changing the threshold would result in changes in false positives and false negatives, corresponding to movement on the curve.^[11]

Example[edit]

Since in a real experiment it is impossible to avoid all type I and type II errors, it is important to consider the amount of risk one is willing to take to falsely reject H₀ or accept H₀. The solution to this question would be to report the p-value or significance level α of the statistic. For example, if the p-value of a test statistic result is estimated at 0.0596, then there is a probability of 5.96% that we falsely reject H₀. Or, if we say, the statistic is performed at level α, like 0.05, then we allow to falsely reject H₀ at 5%. A significance level α of 0.05 is relatively common, but there is no general rule that fits all scenarios.

Vehicle speed measuring[edit]

The speed limit of a freeway in the United States is 120 kilometers per hour. A device is set to measure the speed of passing vehicles. Suppose that the device will conduct three measurements of the speed of a passing vehicle, recording as a random sample X₁, X₂, X₃. The traffic police will or will not fine the drivers depending on the average speed . That is to say, the test statistic

In addition, we suppose that the measurements X₁, X₂, X₃ are modeled as normal distribution N(μ,4). Then, T should follow N(μ,4/3) and the parameter μ represents the true speed of passing vehicle. In this experiment, the null hypothesis H₀ and the alternative hypothesis H₁ should be

H₀: μ=120     against      H₁: μ₁>120.

If we perform the statistic level at α=0.05, then a critical value c should be calculated to solve

According to change-of-units rule for the normal distribution. Referring to Z-table, we can get

Here, the critical region. That is to say, if the recorded speed of a vehicle is greater than critical value 121.9, the driver will be fined. However, there are still 5% of the drivers are falsely fined since the recorded average speed is greater than 121.9 but the true speed does not pass 120, which we say, a type I error.

The type II error corresponds to the case that the true speed of a vehicle is over 120 kilometers per hour but the driver is not fined. For example, if the true speed of a vehicle μ=125, the probability that the driver is not fined can be calculated as

which means, if the true speed of a vehicle is 125, the driver has the probability of 0.36% to avoid the fine when the statistic is performed at level 125 since the recorded average speed is lower than 121.9. If the true speed is closer to 121.9 than 125, then the probability of avoiding the fine will also be higher.

The tradeoffs between type I error and type II error should also be considered. That is, in this case, if the traffic police do not want to falsely fine innocent drivers, the level α can be set to a smaller value, like 0.01. However, if that is the case, more drivers whose true speed is over 120 kilometers per hour, like 125, would be more likely to avoid the fine.

Etymology[edit]

In 1928, Jerzy Neyman (1894–1981) and Egon Pearson (1895–1980), both eminent statisticians, discussed the problems associated with «deciding whether or not a particular sample may be judged as likely to have been randomly drawn from a certain population»:^[12] and, as Florence Nightingale David remarked, «it is necessary to remember the adjective ‘random’ [in the term ‘random sample’] should apply to the method of drawing the sample and not to the sample itself».^[13]

They identified «two sources of error», namely:

(a) the error of rejecting a hypothesis that should have not been rejected, and

(b) the error of failing to reject a hypothesis that should have been rejected.

In 1930, they elaborated on these two sources of error, remarking that:

…in testing hypotheses two considerations must be kept in view, we must be able to reduce the chance of rejecting a true hypothesis to as low a value as desired; the test must be so devised that it will reject the hypothesis tested when it is likely to be false.

In 1933, they observed that these «problems are rarely presented in such a form that we can discriminate with certainty between the true and false hypothesis» . They also noted that, in deciding whether to fail to reject, or reject a particular hypothesis amongst a «set of alternative hypotheses», H₁, H₂…, it was easy to make an error:

…[and] these errors will be of two kinds:

(I) we reject H₀ [i.e., the hypothesis to be tested] when it is true,^[14]

(II) we fail to reject H₀ when some alternative hypothesis H_A or H₁ is true. (There are various notations for the alternative).

In all of the papers co-written by Neyman and Pearson the expression H₀ always signifies «the hypothesis to be tested».

In the same paper they call these two sources of error, errors of type I and errors of type II respectively.^[15]

[edit]

Null hypothesis[edit]

It is standard practice for statisticians to conduct tests in order to determine whether or not a «speculative hypothesis» concerning the observed phenomena of the world (or its inhabitants) can be supported. The results of such testing determine whether a particular set of results agrees reasonably (or does not agree) with the speculated hypothesis.

On the basis that it is always assumed, by statistical convention, that the speculated hypothesis is wrong, and the so-called «null hypothesis» that the observed phenomena simply occur by chance (and that, as a consequence, the speculated agent has no effect) – the test will determine whether this hypothesis is right or wrong. This is why the hypothesis under test is often called the null hypothesis (most likely, coined by Fisher (1935, p. 19)), because it is this hypothesis that is to be either nullified or not nullified by the test. When the null hypothesis is nullified, it is possible to conclude that data support the «alternative hypothesis» (which is the original speculated one).

The consistent application by statisticians of Neyman and Pearson’s convention of representing «the hypothesis to be tested» (or «the hypothesis to be nullified») with the expression H₀ has led to circumstances where many understand the term «the null hypothesis» as meaning «the nil hypothesis» – a statement that the results in question have arisen through chance. This is not necessarily the case – the key restriction, as per Fisher (1966), is that «the null hypothesis must be exact, that is free from vagueness and ambiguity, because it must supply the basis of the ‘problem of distribution,’ of which the test of significance is the solution.»^[16] As a consequence of this, in experimental science the null hypothesis is generally a statement that a particular treatment has no effect; in observational science, it is that there is no difference between the value of a particular measured variable, and that of an experimental prediction.^{[citation needed]}

Statistical significance[edit]

If the probability of obtaining a result as extreme as the one obtained, supposing that the null hypothesis were true, is lower than a pre-specified cut-off probability (for example, 5%), then the result is said to be statistically significant and the null hypothesis is rejected.

British statistician Sir Ronald Aylmer Fisher (1890–1962) stressed that the «null hypothesis»:

… is never proved or established, but is possibly disproved, in the course of experimentation. Every experiment may be said to exist only in order to give the facts a chance of disproving the null hypothesis.

— Fisher, 1935, p.19

Application domains[edit]

Medicine[edit]

In the practice of medicine, the differences between the applications of screening and testing are considerable.

Medical screening[edit]

Screening involves relatively cheap tests that are given to large populations, none of whom manifest any clinical indication of disease (e.g., Pap smears).

Testing involves far more expensive, often invasive, procedures that are given only to those who manifest some clinical indication of disease, and are most often applied to confirm a suspected diagnosis.

For example, most states in the USA require newborns to be screened for phenylketonuria and hypothyroidism, among other congenital disorders.

Hypothesis: «The newborns have phenylketonuria and hypothyroidism»

Null Hypothesis (H₀): «The newborns do not have phenylketonuria and hypothyroidism»,

Type I error (false positive): The true fact is that the newborns do not have phenylketonuria and hypothyroidism but we consider they have the disorders according to the data.

Type II error (false negative): The true fact is that the newborns have phenylketonuria and hypothyroidism but we consider they do not have the disorders according to the data.

Although they display a high rate of false positives, the screening tests are considered valuable because they greatly increase the likelihood of detecting these disorders at a far earlier stage.

The simple blood tests used to screen possible blood donors for HIV and hepatitis have a significant rate of false positives; however, physicians use much more expensive and far more precise tests to determine whether a person is actually infected with either of these viruses.

Perhaps the most widely discussed false positives in medical screening come from the breast cancer screening procedure mammography. The US rate of false positive mammograms is up to 15%, the highest in world. One consequence of the high false positive rate in the US is that, in any 10-year period, half of the American women screened receive a false positive mammogram. False positive mammograms are costly, with over $100 million spent annually in the U.S. on follow-up testing and treatment. They also cause women unneeded anxiety. As a result of the high false positive rate in the US, as many as 90–95% of women who get a positive mammogram do not have the condition. The lowest rate in the world is in the Netherlands, 1%. The lowest rates are generally in Northern Europe where mammography films are read twice and a high threshold for additional testing is set (the high threshold decreases the power of the test).

The ideal population screening test would be cheap, easy to administer, and produce zero false-negatives, if possible. Such tests usually produce more false-positives, which can subsequently be sorted out by more sophisticated (and expensive) testing.

Medical testing[edit]

False negatives and false positives are significant issues in medical testing.

Hypothesis: «The patients have the specific disease».

Null hypothesis (H₀): «The patients do not have the specific disease».

Type I error (false positive): «The true fact is that the patients do not have a specific disease but the physicians judges the patients was ill according to the test reports».

False positives can also produce serious and counter-intuitive problems when the condition being searched for is rare, as in screening. If a test has a false positive rate of one in ten thousand, but only one in a million samples (or people) is a true positive, most of the positives detected by that test will be false. The probability that an observed positive result is a false positive may be calculated using Bayes’ theorem.

Type II error (false negative): «The true fact is that the disease is actually present but the test reports provide a falsely reassuring message to patients and physicians that the disease is absent».

False negatives produce serious and counter-intuitive problems, especially when the condition being searched for is common. If a test with a false negative rate of only 10% is used to test a population with a true occurrence rate of 70%, many of the negatives detected by the test will be false.

This sometimes leads to inappropriate or inadequate treatment of both the patient and their disease. A common example is relying on cardiac stress tests to detect coronary atherosclerosis, even though cardiac stress tests are known to only detect limitations of coronary artery blood flow due to advanced stenosis.

Biometrics[edit]

Biometric matching, such as for fingerprint recognition, facial recognition or iris recognition, is susceptible to type I and type II errors.

Hypothesis: «The input does not identify someone in the searched list of people»

Null hypothesis: «The input does identify someone in the searched list of people»

Type I error (false reject rate): «The true fact is that the person is someone in the searched list but the system concludes that the person is not according to the data».

Type II error (false match rate): «The true fact is that the person is not someone in the searched list but the system concludes that the person is someone whom we are looking for according to the data».

The probability of type I errors is called the «false reject rate» (FRR) or false non-match rate (FNMR), while the probability of type II errors is called the «false accept rate» (FAR) or false match rate (FMR).

If the system is designed to rarely match suspects then the probability of type II errors can be called the «false alarm rate». On the other hand, if the system is used for validation (and acceptance is the norm) then the FAR is a measure of system security, while the FRR measures user inconvenience level.

Security screening[edit]

False positives are routinely found every day in airport security screening, which are ultimately visual inspection systems. The installed security alarms are intended to prevent weapons being brought onto aircraft; yet they are often set to such high sensitivity that they alarm many times a day for minor items, such as keys, belt buckles, loose change, mobile phones, and tacks in shoes.

Here, the null hypothesis is that the item is not a weapon, while the alternative hypothesis is that the item is a weapon.

A type I error (false positive): «The true fact is that the item is not a weapon but the system still alarms».

Type II error (false negative) «The true fact is that the item is a weapon but the system keeps silent at this time».

The ratio of false positives (identifying an innocent traveler as a terrorist) to true positives (detecting a would-be terrorist) is, therefore, very high; and because almost every alarm is a false positive, the positive predictive value of these screening tests is very low.

The relative cost of false results determines the likelihood that test creators allow these events to occur. As the cost of a false negative in this scenario is extremely high (not detecting a bomb being brought onto a plane could result in hundreds of deaths) whilst the cost of a false positive is relatively low (a reasonably simple further inspection) the most appropriate test is one with a low statistical specificity but high statistical sensitivity (one that allows a high rate of false positives in return for minimal false negatives).

Computers[edit]

The notions of false positives and false negatives have a wide currency in the realm of computers and computer applications, including computer security, spam filtering, Malware, Optical character recognition and many others.

For example, in the case of spam filtering the hypothesis here is that the message is a spam.

Thus, null hypothesis: «The message is not a spam».

Type I error (false positive): «Spam filtering or spam blocking techniques wrongly classify a legitimate email message as spam and, as a result, interferes with its delivery».

While most anti-spam tactics can block or filter a high percentage of unwanted emails, doing so without creating significant false-positive results is a much more demanding task.

Type II error (false negative): «Spam email is not detected as spam, but is classified as non-spam». A low number of false negatives is an indicator of the efficiency of spam filtering.

See also[edit]

References[edit]

Bibliography[edit]

External links[edit]

• Bias and Confounding – presentation by Nigel Paneth, Graduate School of Public Health, University of Pittsburgh

Ошибки первого и второго рода

Ошибки первого рода (false positives) и ошибки второго рода (false negatives) — ключевые понятия задач проверки статистических гипотез. Они используются также и в других областях, когда речь идёт о принятии «бинарного» решения (да/нет).

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

Из-за возможности ложных срабатываний не удаётся полностью автоматизировать борьбу со многими видами угроз. Как правило, вероятность ложного срабатывания коррелирует с вероятностью пропуска события (ошибки второго рода). То есть: чем более чувствительна система, тем больше опасных событий она детектирует и, следовательно, предотвращает. Но при повышении чувствительности неизбежно вырастает и вероятность ложных срабатываний. Поэтому чересчур чувствительно (параноидально) настроенная система защиты может выродиться в свою противоположность и привести к тому, что побочный вред от неё будет превышать пользу.

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

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

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

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

когда авторизованные пользователи классифицируются как нарушители (ошибки первого рода)
когда нарушители классифицируются как авторизованные пользователи (ошибки второго рода)

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

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

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

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

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

Ошибки второго рода вызывают серьёзные и трудные для понимания проблемы, особенно когда искомое условие является широкораспространённым. Если тест с 10%-ным уровнем ошибок второго рода используется для обследования группы, где вероятность «истинно-положительных» случаев составляет 70%, то многие отрицательные результаты теста окажутся ложными. (См. Теорему Байеса).

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

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

Источник: https://ru.wikipedia.org/wiki/Ошибки_первого_и_второго_рода