Бинарный тест что это

Статистические тесты в R. Часть 1: Бинарная классификация

Доброго времени суток. Хочу поделиться своими знаниями о работе со статистикой в R.
Многим из нас приходится сталкиваться с различными данными на работе и в повседневной жизни. Качественно и правильно их обработать и проанализировать не так сложно. В этой серии статей я покажу применения некоторых статистических тестов.

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

Бинарная классификация, качественные данные

Первая статья посвящена такому интересному тесту, как бинарная классификация. Это тестирование, которое состоит в проверке объектов на наличие какого-то качества. Например, диагностические тесты (манту все, наверное, делали) или обнаружение сигналов в радиолокации.

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

Сохраняем сразу ее в csv, чтобы не напрягаться с чтением xls (это возможно в R, но не из коробки).

Теперь немного теории. По результатам теста составляется следующая таблица.

Важные параметры

Априорная вероятность:
Чувствительность (Sensitivity). P(T+|H+). Вероятность, что человек будет обнаружен.
Se = 14/16
Специфичность (Specificity), в других тестах часто называется мощностью (Power). P(T-|H-). Вероятность того, что при отсутствии человека, результат тест отрицательный.
Sp = 10/14

Отношение правдоподобия (Likelihood quotient). Важная характеристика для оценки теста. Состоит из 2-х значений.

В литературе тест считается хорошим, если LR+ и LR- больше 3 (относится к медицинским тестам).

Апостериорная вероятность: положительное и отрицательное предсказательное значение (positive and negative predictive value). Вероятность, что результат теста (положительный или отрицательный) верен.
PV+ = 14/18
PV- = 10/12

Также существуют такие понятия, как ошибка первого рода (1 — Se) и ошибка второго рода (1 — Sp). По сути эквивалентны sensitivity и specificity.

Теперь в R

Для начала загрузка данных.

В двух последних строчках мы присвоили вместо 0 и 1 ярлыки. Необходимо это сделать, т.к. иначе R будет работать с нашими даннами как с числами.

Таблицу можно вывести следующим образом:

Данная таблица неплохая, но существует пакет prettyR, который сделает практически все за нас. Для того, чтобы установить пакет, в дефолтном R gui нужно в packages нажать install packages и набрать имя пакета.

Используем библиотеку. Для разнообразия мы выведем результат в html, т.к. у меня в RStudio таблицы отображаются немного некорректно (если знаете как пофиксить — пишите).

Разберем, что там написано.

Таким образом, мы получаем количественные характеристики работы нашего алгоритма. Заметим, что LR+, который на таблице обозначен как odds ratio больше 3-х. Также обратим внимание на параметры описанные выше. Как правило, основной интерес должен представлять PV+ и Se, т.к. ложная тревога это дополнительные затраты, а необнаружение может привести к фатальным последствиям.

Бинарная классификация, количественные данные

А что если наши данные являются количественными? Это может быть, например, параметр, по которому предыдущий алгоритм выносит решение (скажем, количество пикселей цвета кожи). Ради интереса, давайте рассмотрим работу алгоритма, который блокирует спамеров.

Вы создатель новой социальной сети, и пытаетесь бороться со спамерами. Спамеры посылают большое количество писем, поэтому самое простое — блокировать их после превышения некоторого порога сообщений. Только как его выбрать? Берем выборку из опять 30 пользователей. Узнаем, являются ли они роботами, считываем количество сообщений и получаем:

Совсем чуть-чуть теории. После выбора порога, мы делим выборку на 2 части и получаем таблицу из 1-го примера. Естественно, наша задача выбрать лучший порог. Однозначного алгоритма нет, т.к. в каждом реальном примере sensitivity и specificity играют разную роль. Однако, есть метод, который помогают принять решение, а также оценивают тест в целом. Этот метод называется ROC-curve, кривая “рабочей характерики приемника”, используемый изначально в радиолокации. Построим ее в R.

Для начала установим пакет ROCR (с ним установятся пакеты gtools, gplots и gdata, если у вас их нет).

Опять загрузка данных.

Теперь строим кривую.

На этом графике по оси y находится sensitivity, а по x (1 — specificity). Очевидно, что для хорошего теста нужно максимизировать и sensitivity и specificity. Неизвестно лишь в какой пропорции. Если оба параметра равнозначны, то можно искать точку, наиболее удаленную от бисектрисы. Кстати, в R есть возможность сделать этот график более наглядным, добавив точки среза.

Вот так гораздо лучше. Мы видим, что наиболее удаленные от биссектрисы точки, это 40 и 60. Кстати, о биссектрисе и площади под кривой, которую мы подсчитали. Биссектриса — тест дурака, т.е. 50 на 50. Хороший тест должен иметь площадь под кривой, превышающую площадь 0.5, т.е. площадь под биссектрисой. Желательно сильно превышать, но никак уж не быть меньше, т.к. в этом случае лучше тыкать наугад, чем пользоваться нашим методом.

Итоги

В данной статье, я описал как работать с бинарной классификацией в R. Как видите, ситуации, где их применить, можно встретить в обычной жизни. Основные характеристики таких тестов: sensivity, specificity, likelihood rate и predictive value. Они связаны между собой и показывают эффективность теста с разных сторон. В случае количественных данных их можно регулировать с помощью выбора точки среза. Для этого можно использовать ROC-curve. Выбор осуществляется отдельно в каждом случае с учетом требований к тесту, но как правило sensitivity важнее.

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

Спасибо за внимание. Надеюсь, вам понравилось!

Источник

III. Бинарные тесты

1. Крупная феодальная собственность формировалась за счёт бенефиций и аллода. а) да, б) нет.

2. Прекарий – это наследственное владение замлёй. а) да, б) нет.

3. Внеэкономическое принуждение осуществлялось с помощью личной зависимости. а) да, б) нет.

4. Иммунитетные права феодалов фактически закрепляли внеэкономическое прину-ждение крестьян. а) да, б) нет.

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

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

7. На заре феодализма 1 км 2 самой благоприятной зоны лесостепи мог прокормить 20 членов родовой общины. а) да, б) нет.

Зубарева Т.С. «История экономики» ч. 2.

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

9. Человек, проживший 1 год и 1 день в городе, считался свободным. а) да, б) нет.

10. Во Франции принимали указы об ограничении щегольства состоятельных граж-дан. а) да, б) нет.

11. Цеховая система, в основном, функционировала в текстильной производстве. а) да, б) нет.

12. Производить продукцию дешевле и снижать цены – это принципы цеховой систе-мы. а) да, б) нет.

13. В Италии внецеховое ремесло преследовалось. а) да, б) нет.

14. «Замыкание цехов». являлось положительным результатом цеховой системы а) да, б) нет.

15. «Свободное ремесло» функционировало в городах Южной Франции. а) да, б) нет.

16. Бюргером считали того, кто был лично свободным. а) да, б) нет.

17. «Золотой кладовой» Европы считали Италию. а) да, б) нет.

18. Первая морская карта появилась в Венеции. а) да, б) нет.

19. Фаянс изобрели в Германии. а) да, б) нет.

20. Вывоз зерна был запрещён Ватиканом. а) да, б) нет.

21. Перец выполнял роль международного эквивалента. а) да, б) нет.

22. Ярмарки в Шампани и Бри XII-XIII не имели конкурентов. а) да, б) нет.

23. «Великим средством безналичности» называли чек. а) да, б) нет.

24. Первые банки появились в Генуе. а) да, б) нет.

25. Наибольшее распространение наёмный труд получил в XIII в.. а) да, б) нет.

26. По численности правящий класс при феодализме составлял менее 5 %. а) да, б) нет.

27. Институт крепостного права в Западной Европе стал исчезать с XII в. а) да, б) нет.

28. Серваж практиковали в Испании. а) да, б) нет.

29. Вилланы во Франции могли обращаться в королевский суд. а) да, б) нет.

30. В гильдии предусматривалось наказание для тех, кто продавал товар дешевле. а) да, б) нет.

31. Социальное различие между ремесленниками в гильдии в Англии в первой поло-вине XIV в были значительны. а) да, б) нет.

Зубарева Т.С. «История экономики» ч. 2.

32. «Величайшим изобретением». на суше стали семейные компании а) да, б) нет.

33. Цензиву практиковали во Франции. а) да, б) нет.

34. Переходы из одного сословия в другое были чрезвычайно затруднены. а) да, б) нет.

35. Рентный фонд предполагал, что феодал за службу получал не земельные участки, а ренту с них.. а) да, б) нет.

36. Гайды существовали в Англии. а) да, б) нет.

37. Боклэнд представлял собой королевскую землю, право сбора с которой предостав-лялось определённому феодалу.. а) да, б) нет.

38. Наследники копигольдеров могли использовать их землю только выплате файна. а) да, б) нет.

39. В «держателей по обычаю» малых земель превращались сервы. а) да, б) нет.

40. Арендаторов маноров называли фермерами. а) да, б) нет.

41. Для Англии было характерно расширение домениального хозяйства в середине XIV в. а) да, б) нет.

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

Источник

Статистические тесты в R. Часть 2: Тесты качественных данных

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

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

Перед тем как начать, сделаю важное замечание. Самое сложное, выбрать, как анализировать данные. R — это инструмент, он сделает все, что вы ему скажете. Но если вы примените не тот метод, ваши результаты не будут иметь смысла.

Немного теории

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

В статистике оперируют так называемыми гитпотезами. Их всего две. Основная, H0, что отличия нет:

Альтернативная, H1, отличие величин:

Гипотеза может быть и вида x1

Источник

Статистическая проверка случайности двоичных последовательностей методами NIST

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

Случайные двоичные последовательности

Во­-первых, под генерацией случайных чисел подразумевается получение последовательности из двоичных знаков 0 и 1, а не байтами, как бы ни хотелось программистам. Идеальным подобным генератором является подбрасывание «идеальной» монеты (ровная монета, у которой вероятности выпадения каждой из сторон одинаковы), которую бы подбрасывали столько раз, сколько нужно, но проблема в том, ничего идеального не сущ ествует, а производительность такого генератора оставляла бы желать лучшего (один подрос монеты = одному биту). Тем не менее, все тесты, описываемые ниже, оценивают, насколько исследуемый генератор случайных чисел «похож» или «не похож» на воображаемую идеальную монету (не по скорости получения «случайных» знаков, а их «качества»).

Во­-вторых, все генераторы случайных чисел делятся на 2 типа —истинно случайные — физические генераторы/датчики случайных чисел (ДСЧ/ФДСЧ) и псевдо­случайные – программные датчики/генераторы случайных чисел (ПДСЧ). Первые принимают на вход некий случайный бесконечный процесс, а на выходе дают бесконечную (зависит от времени наблюдения) последовательность 0 и 1. Вторые представляют собой заданную разработчиком детерминированную функцию, которая инициализируется т. н. зерном, после чего также на выходе выдает последовательность 0 и 1. Зная это зерно, можно предсказать всю последовательность. Хороший ПДСЧ — этот тот, для которого невозможно предсказать последующие значения, имея всю историю предыдущих значений, не имея зерна. Это свойство называется прямой непредсказуемостью. Есть еще обратная непредсказуемость — невозможность вычислить зерно, зная любое количество генерируемых значений.

Казалось бы, проще всего взять истинно случайные/физические ДСЧ и не думать ни о какой предсказуемости. Однако тут есть проблемы:

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

Нулевая и альтернативная гипотезы

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

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

Вероятность ошибки первого рода называют уровнем статистической значимости и обозначают как α. Т.е. α — это вероятность отбраковать «хорошую» случайную последовательность. Это значение определяется областью применения. В криптографии принято α брать от 0.001 до 0.01.

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

Частотный блочный тест

Этот тест делается на основе предыдущего, только теперь значения пропорции «1»/«0» для каждого блока анализируются методом Хи-квадрат. Ясно, что это соотношение должно быть приблизительно равным 1.

Например, пусть дана последовательность 0110011010. Разобъем ее на блоки по 3 бита («бесхозный» 0 на конце отброшен):
011 001 101

Посчитаем пропорции π_i для каждого блока: π₁ = 2/3, π₂ = 1/3, π₃ = 1/3. Далее вычисляем статистику по методу Хи-квадрат c N степенями свободы (здесь N — количество блоков):

Вычислим P-значение через специальную функцию Q:

Q — это т.н. неполная верхняя гамма-функция, определяемая как:

При этом функция Г — стандартная гамма-функция:

Последовательность считается случайной, если P-значение > 0.01. Рекомендуется анализировать последовательности длиной не менее 100 бит, а также должны выполняться соотношения M >= 20, M > 0.01n и N 0.1, а значит идем дальше.

Вычисляем суммарное число знакоперемен V:

где если , или в противном случае.

Вычисляем P-значение через функцию ошибок:

Если результат >= 0.01 (как в нашем примере), то последовательность признается случайной.

Тест на самую длинную последовательность из единиц в блоке

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

Какую взять длину блока? NIST рекомендует несколько опорных значений, как разбивать на блоки:

Пусть дана последовательность:
11001100 00010101 01101100 01001100 11100000 00000010
01001101 01010001 00010011 11010110 10000000 11010111
11001100 11100110 11011000 10110010

Разобьем ее на блоки по 8 бит (M=8), после чего посчитаем максимальную последовательность из единиц для каждого блока:

Далее считаем статистику по разным длинам на основе следующей таблицы:

Как пользоваться этой таблицей: у нас M = 8, поэтому смотрим только один соответствующий столбец. Считаем v_i:
v₀ = <кол-во блоков с макс. длиной ≤ 1 > = 4
v₁ = <кол-во блоков с макс. длиной = 2 > = 9
v₂ = <кол-во блоков с макс. длиной = 3 > = 3
v₃ = <кол-во блоков с макс. длиной ≥ 4 > = 0

Вычисляем Хи-квадрат:

Где значения K и R берутся исходя из такой таблицы:

Теоретические вероятности π_i задаются константами. Например, для K=3 и M=8 рекомендуется взять π₀ = 0.2148, π₁ = 0.3672, π₂ = 0.2305, π₃ = 0.1875. (Значения для других K и M приведены в [2]).

Далее вычисляем P-значение:

Если оно > 0.01, как в нашем примере, то последовательность считается достаточно случайной.

Тест рангов бинарных матриц

Тест анализирует матрицы, которые составлены из исходной последовательности, а именно — рассчитывает ранги непересекающихся подматриц, построенных из исходной двоичной последовательности. В основе тест лежат исследования Коваленко [6], где ученый исследовал случайные матрицы, состоящие из 0 и 1. Он показал, что можно спрогнозировать вероятности того, что матрица M x Q будем иметь ранг R, где R = 0,1,2. min(M,Q). Эти вероятности равны:

NIST рекомендует брать M = Q = 32, а также, чтобы длина последовательности n = M^2 * N. Но мы для примера возьмем M = Q = 3. Далее нужны вероятности P_M, P_M-1 и P_M-2. С небольшой долей погрешности формулу можно упростить, и тогда эти вероятности равны:

Итак, пусть дана последовательность 01011001001010101101. «Раскладываем» ее по матрицам — хватило на 2 матрицы:

Вычисляем P-значение:

Если результат > 0.01, то последовательность признается случайной. NIST рекомендует, чтобы общая длина последовательности была >= 38MQ.

Спектральный тест

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

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

Вы спросите, а где же здесь периодичности? Ответ — экспоненту можно выразить через тригонометрические функции:

Для нашего теста интересны не фазы, а абсолютные значения амплитуд. И если мы вычислим эти абсолютные значения, то окажется, что они симметричны (это общеизвестный факт при переходе от комплексных значений к вещественным), поэтому для дальнейшего рассмотрения мы возьмём только половину этих значений (от 0 до n/2) — остальные не несут дополнительной информации.

Вот как разложение Фурье можно сделать, например, в программе GNU Octave:
Видим, что наблюдается симметрия. Поэтому нам хватит и пять значений: 0, 2, 4.4721, 2, 4.4721.

Далее вычисляем граничное значение по формуле

Оно означает, что если последовательность истинно случайная, то 95% пиков не должны превышать эту границу.

Вычислим предельное число пиков, которых должно быть меньше, чем T:

Далее смотрим на результат разложения и видим, что все наши 4 пика меньше граничного значения. Далее оцениваем эту разницу:

Вычисляем P-значение:

Оно получилось >0.01, поэтому гипотеза о случайности принимается. И да, для теста рекомендуется брать не менее 1000 бит.

Тест на встречающиеся непересекающиеся шаблоны

Подопытная последовательность разбивается на блоки одинаковой длины. Например:
1010010010 1110010110

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

Итак, для наших блоков W₁ = 2 и W₂ = 1:
101 001 001 0
111 001 0110

Вычислим математические ожидание и дисперсию, как если бы наша последовательность была подлинно случайна. Ниже приведены формулы. Здесь N = 2 (кол-во блоков), M = 10 (длина блока), m = 3 (длина образца).

Вычислим итоговое P-значение через неполную гамма-функцию:

Видим, что P-значение > 0.1, а значит, последовательность достаточно случайна.

Мы оценили только один шаблон. На самом деле нужно проверить все комбинации шаблонов, да и ещё к тому же для разной длины этих шаблонов. Сколько того и другого нужно, определяется исходя из конкретных требований, но обычно m берут 9 или 10. Чтобы получить осмысленные результаты, следует брать N 0.01 * n.

Тест на встречающиеся пересекающиеся шаблоны

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

Универсальный тест Мауэра

Тест оценивает, насколько «далеко» друг от друга отстоят шаблоны внутри последовательности. Смысл теста в том, чтобы понять, насколько последовательность сжимаема (конечно, имеется в виду сжатие без потерь). Чем более сжимаема последовательность, тем она менее случайна. Алгоритм этого теста весьма громоздкий для Хабра-формата, поэтому опустим его.

Тест на линейную сложность

В основе теста лежит предположение, что подопытная последовательность была получена через регистр сдвига с линейной обратной связью (или LFSR, Linear feedback shift register). Это общеизвестный метод получения бесконечной последовательности: тут каждый следующий бит получается как некая функция бит, «сидящих» в регистре. Минус LFSR в том, что он всегда имеет конечный период, т.е. последовательность обязательно будет рано или поздно повторяться. Чем больше длина LFSR, тем лучше случайная последовательность.

Исходная последовательность разбивается на равные блоки длиной M. Далее для каждого блока с помощью алгоритма Берлекэмпа — Мэсси [10] находится его линейная сложность (L_i), т.е. длина LFSR. Затем для всех найденных L_i оценивается распределение Хи-квадрат со 6 степенями свободы. Покажем на примере.

Пусть дан блок 1101011110001 (M=13), для которого алгоритм Берлекэмпа — Мэсси выдал L = 4. Убедимся, что это так. Действительно, нетрудно догадаться, что для этого блока каждый следующий бит получается как сумма (по модулю 2) 1-го и 2-го бита (нумерация с 1):
x₅ = x₁ + x₂ = 1 + 1 = 0
x₆ = x₂ + x₃ = 1 + 0 = 1
x₇ = x₃ + x₄ = 1 + 0 = 1
и.т.д.

Вычисляем математическое ожидание по формуле

Для каждого блока вычисляем значение T_i:

Имеем 7 возможных исходов, а значит вычисляем Хи-квадрат с числом степеней свободы 7 — 1 = 6:

Вероятности π_i в тесте жестко заданы и равны соответственно: 0.010417, 0.03125, 0.125, 0.5, 0.25, 0.0625, 0.020833. (π_i для большего числа степеней свободы можно вычислить по формулам, данным в [2]).

Вычислить P-значение:

Если результат получился > 0.01, то последовательность признается случайной. Для реальных тестов рекомендуется брать n >= 10^6 и М в пределах от 500 до 5000.

Тест на подпоследовательности

В основе теста лежат работы [8] и [11]. Там описываются 2 показателя (∇ψ 2 _m и ∇ 2 ψ 2 _m), которые характеризуют, насколько частоты появления образцов соответствуют этим же частотам для истинно случайной последовательности. Покажем алгоритм на примере.

Пусть дана последовательность 0011011101 длиной n = 10, а также m = 3.

Подставляем:

Итоговые значения:

Итак, оба P-значения > 0.01, а значит последовательность признается случайной.

Приблизительная энтропия

Метод приблизительной энтропии (Approximate Entropy) изначально проявил себя в медицине, особенно в кардиологии. Вообще, согласно классическому определению, энтропия является мерой хаоса: чем она выше, тем более непредсказуемые явления. Хорошо это или плохо, зависит от контекста. Для случайных последовательностей, используемых в криптографии, важно иметь высокую энтропию — это значит, что будет сложно предсказать последующие случайные биты на основе того, что уже имеем. А вот, например, если за случайную величину взять сердечный ритм, измеряемый с заданным периодом, то ситуация иная: есть множество исследований (например, [12]), доказывающих, что чем ниже вариабельность сердечных ритмов, тем реже вероятность инфарктов и прочих неприятных явлений. Очевидно, что сердце человека не может биться с постоянной частотой. Однако одни умирают от инфарктов, а другие нет. Поэтому метод приблизительной энтропии позволяет оценить, насколько с виду случайные явления действительно случайны.

Конкретно, тест вычисляет частоты появления всевозможных образцов заданной длины (m), а затем аналогичные частоты, но уже для образцов длиной m+1. Затем распределение частот сравнивается с эталонным распределением Хи-квадрат. Как и в предыдущем тесте, образцы могут перекрываться.

Покажем на примере. Пусть дана последовательность 0100110101 (длина n = 10), и возьмём m = 3.

Для начала дополним последовательность первыми m-1 битами. Получится 0100110101 01.

Посчитаем встречаемость каждого из 8 всевозможных блоков. Получится:
k₀₀₀ = 0, k₀₀₁ = 1, k₀₁₀ = 3, k₀₁₁ = 1, k₁₀₀ = 1, k₁₀₁ = 3, k₁₁₀ = 1, k₁₁₁ = 0.

Посчитаем соответствующие частоты по формуле C_i m = k_i / n:
C₀₀₀ 3 = 0, C₀₀₁ 3 = 0.1, C₀₁₀ 3 = 0.3, C₀₁₁ 3 = 0.1, C₁₀₀ 3 = 0.1, C₁₀₁ 3 = 0.3, C₁₁₀ 3 = 0.1, C₁₁₁ 3 = 0.

Аналогичным образом считаем частоты появления подблоков длиной m+1=4. Их уже 2 4 =16:
С₀₀₁₁ 4 = С₀₁₀₀ 4 = С₀₁₁₀ 4 = С₁₀₀₁ 4 = С₁₁₀₁ 4 = 0.1, С₀₁₀₁ 4 = 0.2, С₁₀₁₀ 4 = 0.3. Остальные частоты = 0.

Вычисляем φ 3 и φ 4 (заметьте, что здесь натуральный логарифм):

Вычисляем Хи-квадрат:

P-значение:

Получившееся значение > 0.01, а значит последовательность признается случайной.

Тест кумулятивных сумм

Далее находится число z = максимум среди этих сумм.

Наконец, считается P-значение по следующей формуле (её вывод см. в [9]):

Где:

Здесь Φ — функция распределения стандартной нормальной случайной величины. Напоминаем, что стандартное нормальное распределение — это всем известное гауссово распределение (в форме колокола), у которого математическое ожидание 0 и дисперсия 1. Выглядит так:

Если получившееся P-значение > 0.01, то последовательность признается случайной.

Кстати, у этого теста есть 2 режима: первый мы только что рассмотрели, а во втором суммы считаются начиная с последнего элемента.

Тест на произвольные отклонения

Где v_k(x) — значения в таблице для данного состояния, J — количество циклов (у нас 3), π_k(x) — вероятности того, что состояние «x» возникнет k раз в подлинно случайном распределении (они известны).

Например, для x=1 получается:

Значения π для остальных x смотрите в [2].

Вычисляем P-значение:

Если оно > 0.01, то делается вывод о случайности. В итоге необходимо вычислить 8 P-значений. Какие-то могут оказаться больше 0.01, какие-то — меньше. В таком случае финальное решение о последовательности делается на основе других тестов.

Разновидность теста на произвольные отклонения

Ниже привожу список источников, которые можно посмотреть, если хочется углубиться в тему:

Источник