Автор рассматривает проблему гипотезы "независимости" при анализе данных, особенно в задачах с размерностью 16 и выше, когда эта гипотеза становится ненадежной, и для ее обхода предлагается использовать энтропийно-корреляционный метод. Он позволяет вычислять энтропию по Шеннону для длинных чисел с зависимыми разрядами, обеспечивая более точные результаты.
Одной из неприятностей для всех тех, кто использует реальные данные, является гипотеза "независимости". Мы вынуждены применять эту гипотезу на малых выборках или вообще при отсутствии данных. Классика начинает "хромать" на задачах размерности 16 и более. Если осознаешь свою "хромоту", то нужно искать какой-то костыль. Пускай он будет не очень ортопедичным, главное, чтобы он помогал идти к поставленной цели. В этой статье рассматривается вариант энтропийно-корреляционного костыля, который помогает обойти "тупик" гипотезы "независимости" при вычислении энтропии по Шеннону для длинных чисел с зависимыми разрядами.
Каждая система имеет собственную размерность, которая может быть заранее оценена.
Наиболее глубоко этот вопрос проработан в криптографии. В ее приложениях длина бинарного ключа симметричного алгоритма криптографических приложений является размерностью задачи. Криптографические приложения специально построены так, чтобы уничтожить существующие корреляционные связи естественного языка между битами в шифротекстах. Если применен алгоритм шифрования с ключом длиной 256 бит, то попытки оценить корреляции между разрядами шифротекста должны приводить к малым значениям коэффициентов парной корреляции между разрядами.
Формально этот эффект может быть оценен построением корреляционной матрицы размерности [256*256]. При формировании такой корреляционной матрицы, например, может быть использовано скользящее по шифротексту окно шириной 256 бит. Фрагмент шифротекста, на котором строится корреляционная матрица, должен быть примерно в 3-:-4 раза длиннее ширины скользящего окна. То есть в нашем случае достаточно фрагмента шифротекста длиной 999 бит. Сами коэффициенты парной корреляции оцениваются по классической формуле:
где Е(.) – оператор вычисления математического ожидания; σ(.) – оператор вычисления стандартного отклонения; кавычками "." помечены дискретные переменные (так обычно выделяют текстовые переменные при программировании).
Внутри скользящего окна процедуры вычисления коэффициентов корреляции между разрядами описываются полносвязным графом, структура которого приведена на рис. 1.
На рисунке вершинами графа являются 256 состояний разрядов бинарного кода в скользящем окне по шифротексту. Матрица условных вероятностей и матрица коэффициентов парной корреляции существенно зависят от того, насколько анализируемые данные близки к идеальному белому шуму. Так, для идеального белого шума все диагональные коэффициенты корреляции должны быть единичными, а находящиеся вне диагонали коэффициенты корреляции должны быть малы:
Более того, любая корреляционная матрица симметрична, а матрица для действительно белого шума размерностью [256*256] дополнительно обязана иметь нормальное распределение коэффициентов корреляции, размещенных вне диагонали с нулевым математическим ожиданием E(r) = 0,00 и стандартным отклонением σ(r) ≈ 0,061.
Таким образом, даже идеальный белый шум (полный хаос) не может иметь идеальную единичную корреляционную матрицу (правая часть формулы (2). Любая корреляционная матрица размерности [256*256] вне диагонали имеет малые, случайные значения коэффициентов корреляции. Ситуация, когда все коэффициенты корреляции вне диагонали являются нулевыми, маловероятна.
Таким образом, распространенной гипотезой "полностью" независимых данных могут пользоваться только криптографы, убедившись в том, что при шифровании использованы криптографические механизмы, реализованные без ошибок.
Распределение откликов нейросети при воздействии на нее белого шума отображена в центре рис. 2. При отходе от хаоса в сторону роста порядка входных биометрических данных корреляционная метрика положительна и становится дельта-функцией при совпадении кодов "свой" и "чужой". В случае, когда порядок увеличивается в сторону инверсии кода "свой", корреляция становится отрицательной и растет ее модуль.
В центре рис. 2 всегда располагается нормальное распределение коэффициентов корреляции откликов нейросети. Противоположная ситуация распределения откликов нейросети на примеры образа "свой" (почти полный порядок) отображена дельта-функцией в правой части рисунка. Выходные коды примеров образа "свой" практически полностью детерминированы (шумов почти нет, коды-отклики с вероятностью 0,95 повторяются во всех разрядах).
Убедиться в достоверности данных рис. 2 можно, воспользовавшись средой моделирования "БиоНейроАвтограф" [2]. Структура преобразования данных этой среды приведена на рис. 3.
В левой часть рисунка дан один пример рукописного пароля "Пенза", воспроизведенного на графическом планшете. Для обучения нейросети необходимо от 8 до 16 примеров рукописной парольной фразы. При обработке данных с планшета снимаются две функции времени x(t) и y(t), возникающие при воспроизведении рукописного пароля. Далее эти данные преобразуются в 416 коэффициентов двухмерного преобразования Фурье [3]. Нейросеть состоит из 256 нейронов, каждый нейрон имеет по 24 входа. Каждый вход нейрона случайно подключен к вектору 416 входных биометрических параметров. Каждый нейрон отвечает за один бит криптографического ключа, после его автоматического обучения.
Обучение нейросети выполняется автоматически алгоритмом ГОСТ Р 52633.5–2011 [4]. После обучения нейросеть воспроизводит с доверительной вероятностью 0,95 верный код ключа криптографической аутентификации. С вероятностью 0,05 возникает от 1 до 5 ошибочных бит, если нейросети предъявлять примеры образа "свой", которые не участвовали в обучении.
В случае, когда на вход обученной распознаванию пароля "Пенза" нейросети подаются случайно выбранные рукописные образы – "Сура", "крест", …, "дом", число ошибочных бит на выходах нейросети возрастает до интервала от 50 до 200. Примеры откликов нейросети на тестовые образы "чужой" приведены на рис. 4.
Практика тестирования показывает, что бинарные коды примеров одного и того же образа похожи и имеют существенную коррелированность. Примеры разных образов "чужой" не похожи и, соответственно, имеют слабую по модулю коррелированность. На рис. 4 представлено 32 примера образов "чужие". Опираясь на них, можно вычислить (322/2-32) = 480 коэффициентов корреляции для всех неповторяющихся сочетаний 32 разных примера образов "чужой". Этого достаточно для оценки стандартного отклонения коэффициентов корреляции – σ (r). При использовании столь большой тестовой выборки нет смысла вычислять математическое ожидание коэффициентов корреляции. Достаточно оценивать только их стандартное отклонение.
В силу того, что при вычислении коэффициентов корреляции по формуле (1) используется 256-кратное суммирование, их распределение описывается нормальным законом. При тестировании стойкости нейросетевой защиты к атакам подбора появляется возможность пользоваться гипотезой нормальности. При этом вероятность ошибок второго рода (ложное принятие образа "чужой" за образ "свой") можно оценивать, прогнозируя число опытов, попадающих в правый хвост нормального распределения со значением коэффициентов корреляции более 0,992 (рис. 2). В этом случае 256-мерная энтропия Шеннона приближенно оценивается следующим образом:
Для биометрических данных рукописного пароля "Пенза" {E(r) = 0,00; σ(r) ≈ 0,27} как результат прогнозируемая вероятность ошибок составляет Р2 ≈ 0,00021. Пересчет этой вероятности в энтропию дает значение в 12 бит. Как показали исследования, энтропия Шеннона связана с корреляционной энтропией линейно.
Из-за того, что классическая энтропия Шеннона [5, 6] и корреляционная энтропия вычисляются разными алгоритмами, каждая из оценок имеет свою собственную шкалу. Соотношение этих двух шкал энтропии отображены на рис. 5.
Из рис. 5 следует, что модуль-корреляционная метрика энтропии, вычисленная в рамках гипотезы нормального распределения данных, всегда дает заниженные оценки. Наблюдаем методическую ошибку занижения оценок энтропии, возникающую из-за вычислений в пространстве коэффициентов корреляции. Важным фактом является то, что и шкала энтропии Шеннона, и шкала энтропии Хэмминга [6, 7], и шкала корреляционной энтропии [8] линейны. В этом контексте шкала корреляционной энтропии легко приводится к классической шкале энтропии Шеннона:
Устранение методической ошибки (4) увеличивает прогнозируемая стойкость защиты рукописного пароля "Пенза" с 12 до 17 бит. Из рис. 5 видно, что оценка корреляционной энтропии всегда меньше классической энтропии Шеннона, однако вычислить энтропию по формуле Шеннона на обычном компьютере технически невозможно.
Принципиально важным является то, что вычислительная сложность оценок корреляции по формуле (1) является квадратичной. То есть вместо вычисления энтропии Шеннона с экспоненциальной вычислительной сложностью [5, 6] появляется возможность обойти проблему через вычисления с полиномиальной вычислительной сложностью, используя последовательность преобразований (1), (3), (4). Корреляционная энтропия [8] может быть применена к задачам высокой размерности.
Видимо, самой сложной в вычислительном отношении является классическая энтропия Шеннона, которой трудно воспользоваться для сложных объектов. Параллельно с классической энтропией Шеннона должно существовать множество упрощенных алгоритмов ее оценки со своими собственными шкалами:
Приведенный выше список возможных шкал энтропии, дополняющих классическую шкалу энтропии Шеннона, открытый. Для первых двух позиций списка (энтропия Хэмминга и корреляционная энтропия) связь частных шкал со шкалой энтропии Шеннона построена. Для пункта 3 и пунктов ниже известны только упрощенные процедуры оценок соответствующих статистик. Однако как связаны упрощенные статистики с порождаемыми ими шкалами энтропии и шкалой энтропии Шеннона, неизвестно.
Так, вполне возможна оценка минимального числа элементов ε-сетей, предложенная А.Н.
Колмогоровым в 1954 г. [10]. Соответственно, для оценок Колмогорова может быть построена шкала энтропии. На данный момент работ, связывающих шкалу ε-энтропии Колмогорова со шкалой энтропии Шеннона, нет. Это обстоятельство отображено отсутствием соответствующих ссылок в списке литературы – [10, ?].
Приведенный выше список открытый (нет его завершения), нумерация в нем может быть существенно увеличена. Так, нумерация вырастет с 6 до 22, если его расширить 16 тестами NISN [11], предназначенными для упрощенной оценки близости криптографических ключей к белому шуму. Каждому тесту NISN должна соответствовать своя шкала связи с энтропией Шеннона. Упрощенных процедур оценки энтропии множество, каждую их них можно рассматривать как некоторую оценку расстояния от анализируемых данных до идеального белого шума или энтропии Шеннона.
В прошлом веке статистика не имела инструмента для учета реальных корреляционных связей между параметрами. Именно по этой причине исследователи и инженеры часто применяли гипотезу независимости данных. Ее популярность обусловлена простотой вычисления вероятности появления того или иного вектора случайных независимых событий:
В более компактной форме соотношение (5) удобно записывать, опираясь на среднее геометрическое частных вероятностей:
Формально преобразования (5) и (5а) эквивалентны, однако разница между ними все-таки есть. Вторая форма записи позволяет легко перейти к учету влияния корреляционных связей:
где корреляционный параметр – rN является параметром симметризованной корреляционной матрицы, находящийся вне ее диагонали.
Как правило, корреляционная матрица реальных данных симметрична относительно своей диагонали, но модули ее элементов, расположенных вне диагонали, не совпадают. У полностью симметризованной корреляционной матрицы вне диагонали должны располагаться одинаковые положительные коэффициенты корреляции – rN:
Процедура полной симметризации корреляционных связей (7) существенно упрощает программирование многомерных численных экспериментов [12, 13], сохраняя тождество многомерных вероятностей реальных данных и их моделей. Переход к параметрам полностью симметризованной корреляционной матрицы выполняется усреднением модулей коэффициентов корреляции исходной матрицы [14]:
Следует отметить, что при симметризации корреляционных матриц желательно опираться на реальные данные, однако это требование не всегда выполнимо. Если реальные данные полностью отсутствуют, они могут быть заменены экспертными оценками.
На рис. 6 отображены кости кисти руки человека, сочлененные 22 суставами. Каждый сустав – это как минимум одна степень свободы кисти руки. То есть наличие 22 суставов с 22 приводами порождает 22-мерную задачу численного моделирования управления мышцами руки.
Нумерация суставов кисти руки начинается с вершины указательного пальца. Сам палец содержит четыре сустава, пятый сустав находится в запястье. Реальных данных о корреляционных связях работы мышц указательного пальца у меня нет, в связи с этим корреляционная матрица построена на экспертных оценках:
Усреднение коэффициентов корреляции, находящихся вне диагонали, дает симметричную матрицу в правой части (2). Пользуясь значением одинаковых коэффициентов корреляции r5= 0,35, мы можем вычислить ожидаемое число степеней свободы задачи управления одним пальцем руки:
Предполагая, что число степеней свободы задачи управления для всех пальцев одинаково, получаем число степеней свободы для кисти руки, равное 11,25. Это соответствует снижению числа степеней свободы задачи управления кистью руки примерно на 96%.
Хаос один и находится в центре возможных состояний любой системы, а порядок может быть как отрицательным, так и положительным (рис. 2). Описанный в статье переход к корреляционным оценкам энтропии учитывает только переход к положительному порядку, что делать с отрицательным порядком, пока неизвестно.
Этот вопрос пока повис и нуждается в дополнительных исследованиях. Тем не менее хорошо просматриваются перспективы развития этого направления работ. Каждому упрощенному тесту NISTдля проверки качества криптографических ключей может быть построен свой упрощенный оценщик энтропии Шеннона. Объединение достаточно большого числа упрощенных оценок энтропии, видимо, позволит оценивать энтропию Шеннона достаточно точно.
Одним из важных приложений корреляционных процедур оценки энтропии является то, что через полную симметризацию корреляционных матриц удается оценивать реальную размерность той или иной практической задачи.
Список литературы
Иллюстрации предоставлены автором.
Иллюстрация к статье сгенерирована нейросетью Kandinsky