Выявление зависимостей большой глубины на основе марковских моделей

Построены два статистических теста для выявления зависимости в случайной последовательности и обнаружения отклонений вероятностного распределения элементов последовательности от равно- мерного. Первый тест основан на частотных статистиках цепи Маркова s-го порядка с r частичными связями, второй –...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2008
Автори: Харин, Ю.С., Петлицкий, А.И., Мальцев, М.В.
Формат: Стаття
Мова:Російська
Опубліковано: Інститут проблем штучного інтелекту МОН України та НАН України 2008
Теми:
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/6885
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Выявление зависимостей большой глубины на основе марковских моделей / Ю.С. Харин, А.И. Петлицкий, М.В. Мальцев // Штучний інтелект. — 2008. — № 3. — С. 121-127. — Бібліогр.: 12 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1859721631737315328
author Харин, Ю.С.
Петлицкий, А.И.
Мальцев, М.В.
author_facet Харин, Ю.С.
Петлицкий, А.И.
Мальцев, М.В.
citation_txt Выявление зависимостей большой глубины на основе марковских моделей / Ю.С. Харин, А.И. Петлицкий, М.В. Мальцев // Штучний інтелект. — 2008. — № 3. — С. 121-127. — Бібліогр.: 12 назв. — рос.
collection DSpace DC
description Построены два статистических теста для выявления зависимости в случайной последовательности и обнаружения отклонений вероятностного распределения элементов последовательности от равно- мерного. Первый тест основан на частотных статистиках цепи Маркова s-го порядка с r частичными связями, второй – на частотных статистиках цепи Маркова переменной длины. Представлены результаты компьютерных экспериментов. Побудовані два статичні тести у випадковій послідовності і знайдення відмінностей імовірного розподілу елементів послідовності від рівномірного. Перший тест заснований на частотних ста- тистиках мережі Маркова s-го порядку з r частковими зв’язками, другий – на частотних статистиках мережі Маркова змінної длини. Наявні результати комп’ютерних експериментів. Statistical decision rules for detection of high-order dependencies and for testing of s dimensional uniformity of discrete time series are constructed. The first test is based on frequency statistics of Markov chain with partial connections. The second test is based on frequency statistics of variable length Markov chain. Asymptotic properties of proposed tests are found. Numerical results are given.
first_indexed 2025-12-01T09:51:34Z
format Article
fulltext «Штучний інтелект» 3’2008 121 �� �O�� �M�>�D�������������� �X���K�����O�Z�j�b�g�����:���B�����I�_�l�e�b�p�d�b�c�����F���<�����F�Z�e�v�p�_�\�� НИИ прикладных проблем математики и информатики БГУ, г. Минск, Беларусь kharin@bsu.by, piatlitski@bsu.by, maltsew@mail.ru Выявление зависимостей большой глубины на основе марковских моделей Построены два статистических теста для выявления зависимости в случайной последовательности и обнаружения отклонений вероятностного распределения элементов последовательности от равно- мерного. Первый тест основан на частотных статистиках цепи Маркова �V-го порядка с �U частичными связями, второй – на частотных статистиках цепи Маркова переменной длины. Представлены результаты компьютерных экспериментов. Введение Выявление зависимости в случайной последовательности и обнаружение отклоне- ний вероятностного распределения элементов последовательности от равномерного являются важнейшими проблемами в защите информации [1-3], генетике [4] и других приложениях. Обзор существующих методов решения этих задач представлен в [2]. Актуальность проблемы построения новых статистических тестов [5] связана с тем, что: 1) многие известные тесты проверяют лишь одно из вероятностных свойств, характе- ризующих случайную последовательность; 2) большинство тестов построено «эвристи- чески» и не фиксирует семейство альтернатив; 3) многие из существующих тестов не имеют теоретических оценок мощности. В данной статье разработаны два новых теста для статистической проверки гипотезы � 0�+ {наблюдаемая последовательность есть равномерно распределенная случайная последовательность (РРСП)} против альтернативы 01 �+�+ � ; РРСП – это случайная последовательность, элементы которой независимы в совокупности и имеют равномерное распределение вероятностей [2]. Первый тест �7�P�F���V,�U�� основан на частотных статистиках новой марковской модели – цепи Маркова �V-го порядка с �U частичными связями ЦМ(�V,�U) [6], а второй тест �7�P�F�I�> – на частотных статистиках цепи Маркова переменной длины [7]. Для тестов �7�P�F���V,�U�� и �7�P�F�I�> исследована мощность для семейства контигуальных альтернатив, а также проведено сравнение с тестом �7�P�F на основе частот цепи Маркова �V-го порядка [8]. �� Тест, основанный на частотных статистиках цепи Маркова с частичными связями Обозначим: �^ �`1,...,1,0 ��� �1�$ – множество состояний мощности �f���d�12 ; �� �� 1 1 ,...,, ���� �� �•� �L�N �N�L�L �N �L �$�M�M�M�- – мультииндекс ( 1 )�N �L�� �� -го порядка, �L�N�t ; }{ �$�[�W�• – однородная стационарная цепь Маркова �V-го порядка с вероятностями одношаговых переходов �^ �`111,,..., ,...,| 11 �M�[�M�[�M�[�S �W�V�V�W�V�V�W�M�M�M �V�V � � � �5� ���������� , 11 1 ���� �• �V�V �$�- , 1�t�W ; �O�Z�j�b�g���X���K�������I�_�l�e�b�p�d�b�c���:���B�������F�Z�e�v�p�_�\���F���<������ «Искусственный интеллект» 3’2008 122 �� �O�� �^ �`�V�U ,...,2,1�• – параметр, называемый числом связей; �� ��00 2 0 1 0 ,...,, �U�U �P�P�P�0 � – целочис- ленный �U-вектор с упорядоченными компонентами �V�P�P�P �U �d������� 00 2 0 11 �! , называемый шаблоном связей; 1 1 11 1 �U�- �U �U�- �$ �4 �T �� �� ���• �§ �·� �¨ �¸ �© �¹ – некоторая (�U+1)-мерная стохасти- ческая матрица. Цепь Маркова {�[�W} называется цепью Маркова �V-го порядка с �U частичными связями и обозначается ЦМ(�V,�U) [6], если ее вероятности одношаговых переходов имеют вид: ���� 100 1 11 ,,,,,, ���� � �V �U�P�P�V�V �M�M�M�M�M�M �T�S �!�! , 11 1 ���� �• �V�V �$�- .�� (1)�� Соотношение (1) означает, что вероятность перехода процесса �[�W в состояние �M�V+1 зависит не от всех �V предыдущих состояний процесса �V�M�M,...,1 , а лишь от �U избранных состояний 00 1 ,..., �U�P�P �M�M . Если �V�U� , то получаем цепь Маркова �V-го порядка [9]. Примем еще несколько обозначений: �� ���Q �Q �[�[�[�; ,,, 211 �!� – наблюдаемая реализация длительности �Q; �N�L,�G – символ Кронекера; �� �� �� �¦ �– �� � � �� �������� �¸�¸ �¹ �· �¨�¨ �© �§ � �V�Q �W �M�[ �U �L �M�[�U �U �U�V�P�F �U�V�W�L�L�P�W �0�- 1 , 1 , 1 1),( 11 ; �G�G�Q , 11 1 ���� �• �U�U �$�- ,�� (2)�� – частотные статистики цепи Маркова ЦМ(�V,�U); �� �� �^ �`1111 01 1),( ,,...,; 00 1 ������������ �� � � � �5� �U�V�W�U�P�W�P�W�U �U �U�V�P�F �M�[�M�[�M�[�0�- �U �P , 11 1 ���� �• �U�U �$�- ,���� – распределение вероятностей )1( ���U -грамм цепи Маркова с частичными связями; �� �� �� �� )/(;;€ 01 1),( 01 1),( �V�Q�0�-�0�- �U �U �U�V�P�F�U �U �U�V�P�F ��� ���� �Q�P – несмещенная и состоятельная частот- ная оценка вероятности �� ��01 1),( ; �U �U �U�V�P�F �0�- ���P , 11 1 ���� �• �U�U �$�- . Построим тест проверки гипотез �+0: }{ �W�[ – РРСП, то есть r+1 1 -1 J q =N , 11 1 ���� �• �U�U �$�- ; �+1,�P�F(�V,�U): }{ �W�[ – цепь Маркова ЦМ(�V���U), для которой матрица �4 имеет вид: �� �� �� 0/11)( 1 1 1 1 1 1 �!����� � ������ �V�Q�E �1 �Q�T�T �U�U�U �-�-�- ,�� 11 1 ���� �• �U�U �$�- ,�� (3)�� где 0 1 1 1 � �¦ �•�� ���$�M �-�U �U�E , 0||11 1 1 1 �z�¦ ���� ���• �U�U �U�$�- �- �E . Соотношение (3) определяет контигуальное семейство альтернатив [10] и означает, что при увеличении длительности �Q наблю- даемой последовательности, гипотеза �+1 сближается с �+0 со скоростью �� ��2/1���Q�2 . Обозначим �� �� �� ���� ��)1(01 1),( 11 1),( ;€)( ���������� ����� �U �U �U �U�V�P�F �U�U �U�V�P�F �1�0�-�1�V�Q�- �P�[ , 11 1 ���� �• �U�U �$�- , (4) �� �� �� ���¦ �¦�¦ �• �• �� �• �� �¸ �¸ �¹ �· �¨ �¨ �© �§ �¸ �¸ �¹ �· �¨ �¨ �© �§ ��� ���� �U�U �U�U�$�- �$�M �U �U�V�P�F �$�M �U �U�V�P�F�U�V�P�F �- �1 �- 1 11 2 1 1),( 1 1 2 ),(),( 1 �[�[�U . (5) �L�_�h�j�_�f�Z������ При �f�o�Q случайная величина ),( �U�V�P�F�U в случае справедливости гипотезы H0 имеет 2�F -распределение с �� ��1��� �1�1�8 �U степенями свободы. �<�u�y�\�e�_�g�b�_���a�Z�\�b�k�b�f�h�k�l�_�c���[�h�e�v�r�h�c���]�e�m�[�b�g�u���g�Z���h�k�g�h�\�_���f�Z�j�d�h�\�k�d�b�o���f�h�^�_�e�_�c�� «Штучний інтелект» 3’2008 123 �� �O�� При помощи теоремы 1 строится тест �7�P�F���V,�U�� [11] для проверки гипотез �+0 и �+1,�P�F(�V,�U), основанный на частотных статистиках цепи Маркова с �U частичными связями: 1)��по наблюдаемой последовательности �Q�; 1 длительности �Q строятся частот- ные статистики �� ���^ �`11 1 1 1),( :; ������ �• �U�U �U �U �U�V�P�F �$�-�0�-�Q согласно (2); 2)��согласно (4), (5) вычисляются статистики �� ���^ �`11 1 1 1),( : ������ �• �U�U�U �U�V�P�F �$�-�-�[ и ),( �U�V�P�F�U ; 3)��вычисляется Р-значение: �� ��),(1 �U�V�P�F�8�*�3 �U��� , где �� ���˜�8�* – функция 2�F -распре- деления с �8 степенями свободы; 4)��решение выносится с помощью решающего правила: принимается {�+0, если �H�!�3 ; �+1,�P�F(�V,�U), если �H�d�3 }, где �� ��1,0�•�H – заданный уровень значимости теста. �L�_�h�j�_�f�Z��������При �f�o�Q случайная величина ),( �U�V�P�F�U в случае справедливости ги- потезы H1,ЦМ(s,r) имеет нецентральное 2�F -распределение с �8 степенями свободы и параметром нецентральности �� �¦ ���� �� �• �� � 11 1 1 1 2 1),( 1 �U�U �U �$�- �-�U�U�V�P�F �E �1 �D .�� (6)�� �K�e�_�^�k�l�\�b�_�� ������Мощность теста TЦМ(s,r) при �f�o�Q удовлетворяет асимптоти- ческому соотношению: �� ���� ���H�����o �� 11 1 , ),( �8�D�8 �*�*�Z �U�V�P�F ,�� где �� ���˜ ),(, �U�V�P�F�D�8�* – функция нецентрального 2�F -распределения с U степенями свобо- ды и параметром нецентральности ),( �U�V�P�F�D , определяемым (6). �K�e�_�^�k�l�\�b�_�� ������ Тест TЦМ(s,r) имеет большую мощность по сравнению с тестом TЦМ. Тест, основанный на частотных статистиках цепи Маркова переменной длины Цепь Маркова {�[�W} называется цепью Маркова переменной длины порядка �V [7], если ее вероятности одношаговых переходов имеют вид: �� 1111 ,,,,,, �������� � �V�V�O�V�V�V �M�M�M�M�M�M �T�S �!�! ,���� �� ���V�-�O�O 1� ,���� 11 1 ���� �• �V�V �$�- .�� (7)�� Соотношение (7) означает, что вероятность перехода в состояние �M�V+1 зависит не от всех �V предыдущих состояний, а лишь от �� ���V�-�O�O 1� предыдущих состояний. Если �� ��1 �V�O �- �V� , то получаем цепь Маркова �V-го порядка [9]. Функция )(�˜�O определяется с помощью контекстной функции �� �� �V �O�V �V �-�-�F 11 ����� , �� �� �� ���V�V �-�F�-�O 11 � , �V�V �$�- �•1 . Контекстную функцию удобно представлять в виде корневого дерева �W, которое называется контекстным деревом. У каждой вершины в таком дереве может быть не более �1 потомков, поскольку каждому узлу (кроме корня) соответствует элемент из множества состояний �$. Каждому значению контекстной функции соответствует ветвь данного дерева. Примем обозначения: �� �� �� �¦ �– �� � �� � �� �¸�¸ �¹ �· �¨�¨ �© �§ � ���� �O�Q �W �O �L �M�[ �O �P�F�I�> �L�L�W �- 1 1 1 , 1 1 1 �G�Q ,�� �W�•�O�-1 ,�� �$�M�O �•��1 ,�� (8) �O�Z�j�b�g���X���K�������I�_�l�e�b�p�d�b�c���:���B�������F�Z�e�v�p�_�\���F���<������ «Искусственный интеллект» 3’2008 124 �� �O�� – частотные статистики цепи Маркова переменной длины; �� �� �^ �`111 1 1 ,,..., �������� �� � � � �5� �O�O�W�O�O�W�W �O �P�F�I�> �M�[�M�[�M�[�-�P ,�� �W�•�O�-1 , �$�M�O �•��1 ,���� – распределение вероятностей )1( ���O -грамм цепи Маркова переменной длины; �� �� �� �� )/(€ 1 1 1 1 �O�Q�-�- �O �P�F�I�> �O �P�F�I�> ��� ���� �Q�P – несмещенная и состоятельная частотная оценка вероятности �� ��1 1 ���O �P�F�I�> �-�P , �W�•�O�-1 , �$�M�O �•��1 . Построим тест проверки гипотез �+0: }{ �W�[ – РРСП, то есть l+1 1 -1 J q =N , �W�•�O�-1 , �$�M�O �•��1 ; �+1,�P�F�I�>: }{ �W�[ – цепь Маркова ЦМ(�V,�U), для которой матрица �4 имеет вид аналогичный (3): �� �� �� 0/11)( 1 1 1 1 1 1 �!����� � ������ �V�Q�E �1 �Q�T�T �O�O�O �-�-�- , �W�•�O�-1 ,�� �$�M�O �•��1 ,�� (9)�� где 0 1 1 1 � �¦ �•�� ���$�M �-�O �O�E , 0|| 11 1 1, �z�¦ �•�• �� ���$�M�- �-�O �O �O�E �W . Соотношение (9) определяет контигуальное семейство альтернатив [10]. Определим случайные величины: �� �� �� �� ���� ��)1(1 1 11 1 €)( ���������� ����� �O�O �P�F�I�> �O�O �P�F�I�> �1�-�1�V�Q�- �P�[ ,�� �W�•�O�-1 ���� �$�M�O �•��1 ,�� (10)�� �� �� �� �� ���¦ �¦�¦ �• �• �� �• �� �¸ �¸ �¹ �· �¨ �¨ �© �§ �¸ �¸ �¹ �· �¨ �¨ �© �§ ��� �����W �[�[�U �O �O�O�- �$�M �O �P�F�I�> �$�M �O �P�F�I�>�P�F�I�> �- �1 �- 1 11 2 1 1 1 1 2 1 �� (11)�� �L�_�h�j�_�f�Z�� ������При �f�o�Q случайная величина �P�F�I�>�U в случае справедливости гипотезы H0 имеет 2�F -распределение с �� ��| | 1�8 �1�W� ���� степенями свободы. При помощи теоремы 3 строится тест �7�P�F�I�> для проверки гипотез �+0 и �+1,�P�F�I�>, основанный на частотных статистиках цепи Маркова с �U частичными связями: 1)��по наблюдаемой последовательности �Q�; 1 длительности �Q строятся частотные статистики �� ���^ �`�$�M�-�- �O �O�O �P�F�I�> �•�• �� �� 11 1 1 ,: �W�Q согласно (8); 2)��согласно (10), (11) вычисляются статистики �� ���^ �`�$�M�-�- �O �O�O �P�F�I�> �•�• �� �� 11 1 1 ,: �W�[ и �P�F�I�>�U ; 3)��вычисляется Р-значение: �� ���P�F�I�>�8�*�3 �U��� 1 , где �� ���˜�8�* – функция 2�F - распределения с �8 степенями свободы; 4)��решение выносится с помощью решающего правила: принимается {�+0, если �H�!�3 ; �+1,�P�F�I�>, если �H�d�3 }, где �� ��1,0�•�H – заданный уровень значимости теста. �L�_�h�j�_�f�Z�� ������При �f�o�Q случайная величина �P�F�I�>�U в случае справедливости гипотезы H1,ЦМПД имеет нецентральное 2�F -распределение с �8 степенями свободы и параметром нецентральности���� �� �¦ �� �� �• � �$�M�- �-�P�F�I�> �O �O �O�E �1 �D 11 1 1 , 2 || 1 �W�W ���� (12) �� �K�e�_�^�k�l�\�b�_�� ������Мощность теста TЦМПД при �f�o�Q удовлетворяет асимпто- тическому соотношению: �� ���� ���H�����o �� 11 1 , �8�D�8 �*�*�Z �P�F�I�> ,�� где �� ���˜ �P�F�I�>�D�8�* , – функция нецентрального, 2�F -распределения с U степенями свободы и параметром нецентральности �P�F�I�>�D определяемым (12). �K�e�_�^�k�l�\�b�_��������Тест TЦМПД имеет большую мощность по сравнению с тестом TЦМ. �<�u�y�\�e�_�g�b�_���a�Z�\�b�k�b�f�h�k�l�_�c���[�h�e�v�r�h�c���]�e�m�[�b�g�u���g�Z���h�k�g�h�\�_���f�Z�j�d�h�\�k�d�b�o���f�h�^�_�e�_�c�� «Штучний інтелект» 3’2008 125 �� �O�� Численные результаты Проведены численные эксперименты на модельных и реальных данных. �I�j�b�f�_�j���������f�h�^�_�e�v�g�u�_���^�Z�g�g�u�_���� На рис. 1 представлена зависимость мощности тестов �7�P�F���V,�U��, �7�P�F для альтернативы �+1,�P�F(�V,�U) от �Q при 0,05�H� , �1��= 4, �V��= 6, �U��= 4, �� ��1,4,5,60 � �U�0 и матрице �4, для которой: 1) 0,1 �U�- �E ,…, 2,1 ���1�- �U�E генерировались с помощью стандартного генератора равномерно распределенных на [-13,13] псевдослучайных чисел, а )...( 2,0,1, 111 ���� ������� �1�-�-�1�- �U�U�U �E�E�E ; 2) функция нецентрального 2�F -распределения имеет 768� �8 степеней свободы и параметр нецентральности ( , ) 138,5�P�F �V �U�D � . На этом рисунке квадратиками и кружками указаны значения оценки мощности �Z€ для �7�P�F���V,�U�� и �7�P�F соответственно, полученные с помощью метода Монте-Карло при числе прогонов, равном 1000; пунктирные линии – верхняя и нижняя 99 % доверительные границы для мощности; сплошная линия – теоре- тическое значение �Z, найденное в следствии 1. Из рис. 1 видно, что для указанных значений параметров мощность теста �7�P�F���V,�U�� приблизительно в 4 раза превосходит мощность теста �7�P�F, что согласуется со следствием 2. Отметим, что при �f�o�Q �� мощность тестов не стремится к 1, так как при увеличении �Q гипотеза �+1 сближается с �+0 (контигуальная постановка задачи). Рисунок 1 – Зависимость мощности от �Q�� �I�j�b�f�_�j�� ���� ���f�h�^�_�e�v�g�u�_�� �^�Z�g�g�u�_���� Исследовалась зависимость мощности тестов �7�P�F�I�>, �7�P�F для альтернативы �+1,�P�F�I�> от �Q при 0,05�H� , �1��= 2, �V��= 8 и контекстном дереве �W, представленном на рис. 2. Эта зависимость проиллюстрирована на рис. 3 (квадратики и кружки – значения оценки мощности �Z€ для �7�P�F�I�> и �7�P�F соответ- ственно; пунктирные линии – верхняя и нижняя 99 % доверительные границы для мощности; сплошная линия – теоретическое значение �Z, определяемое следствием 3). Из рис. 3 видно, что для этих значений параметров мощность теста �7�P�F�I�> прибли- зительно в 3 раза превосходит мощность теста �7�P�F, что согласуется со следствием 4. �O�Z�j�b�g���X���K�������I�_�l�e�b�p�d�b�c���:���B�������F�Z�e�v�p�_�\���F���<������ «Искусственный интеллект» 3’2008 126 �� �O�� Рисунок 2 – Контекстное дерево �W Рисунок 3 – Зависимость мощности от �Q �I�j�b�f�_�j�� ���� ���j�_�Z�e�v�g�u�_�� �^�Z�g�g�u�_���� Исследовался генератор псевдослучайных после- довательностей А5/1 [12], состоящий из трех коротких линейных регистров сдвига с обратной связью. Алгоритм А5/1 используется в сети GSM для обеспечения защиты информации на уровне базовая-мобильная станция. При тестировании генератора А5/1 с помощью теста �7�P�F(�V,�U) его выходная после- довательность разбивалась на 12-битовые фрагменты, и каждый такой фрагмент рассматривался как буква алфавита �^ �`12,...,1,0 12 ��� �$ , мощности 122� �1 . На вход теста �7�P�F(�V,�U) поступали 250 реализаций выходной последовательности длительности �Q бит каждая, сгенерированных этим криптоалгоритмом; параметры теста: 2� �V , 1� �U , )1(0 � �U�0 , 0,05�H� . Результаты исследований приведены в табл. 1. Для РРСП при уровне значимости 0,05�H� среднее число отклоненных из 250 реализаций равнялось бы 12,5. Таким образом, представленные в табл. 1 результаты свидетельствуют о сильной неслучайности выходной последовательности алгоритма А5/1. Таблица 1 – Результаты тестирования генератора А5/1 Длина последовательности �Q, бит 2124 �˜ 2125 �˜ 2126 �˜ 2127 �˜ 2128 �˜ Количество (частота) отклоненных тестом �7�P�F(�V,�U) реализаций 37 (0,148) 59 (0,236) 72 (0,288) 91 (0,364) 105 (0,420) �<�u�y�\�e�_�g�b�_���a�Z�\�b�k�b�f�h�k�l�_�c���[�h�e�v�r�h�c���]�e�m�[�b�g�u���g�Z���h�k�g�h�\�_���f�Z�j�d�h�\�k�d�b�o���f�h�^�_�e�_�c�� «Штучний інтелект» 3’2008 127 �� �O�� Заключение Построены статистические тесты на основе марковских частотных статистик, которые позволяют выявлять зависимости высокого порядка и специфической структуры. Проведенные компьютерные эксперименты на модельных и реальных данных иллюстрируют работоспособность построенных тестов. Литература 1.�� Кнут Д. Искусство программирования: В 3 т. – М.: Мир, 1992. 2.�� Харин Ю.С. и др. Математические и компьютерные основы криптологии. – Мн.: Новое знание, 2003. 3.�� Иванов М.А., Чигунков И.В. Теория, применение и оценка качества генераторов псевдослучайных последовательностей. – М.: КУДИЦ-ОБРАЗ, 2003. 4.�� Уотермен М.С. Математические методы анализа последовательностей ДНК. – М.: Мир, 1999. 5.�� Харин Ю.С., Ярмола А.Н., Петлицкий А.И. Методы и алгоритмы статистического тестирования генераторов случайных и псевдослучайных последовательностей в системах информационной безопасности // Искусственный интеллект. – 2006. – № 3. – С. 793-803. 6.�� Харин Ю.С. Цепи Маркова с �U-частичными связями и их статистическое оценивание // Доклады НАН Беларуси. – 2004. – Т. 48, № 1. – С. 40-44. 7.�� Buhlmann P., Wyner A. Variable length Markov chains // The Annals of Statistics. – 1999. – Vol. 27, № 2. – P. 480-513. 8.�� Тихомирова М.И., Чистяков В.П. О двух статистиках типа хи-квадрат, построенных по частотам цепочек состояний сложной цепи Маркова // Дискретная математика. – 2003. – Т. 15, № 2. – С. 149-159. 9.�� Дуб Дж. Вероятностные процессы. – М.: ИЛ, 1956. 10.��Руссас Дж. Контигуальность вероятностных мер. – М.: Мир, 1975. 11.��Петлицкий А.И., Харин Ю.С. Проверка гипотез о независимости и равномерном вероятностном распределении элементов случайной последовательности // Вестник БГУ. – Сер. 1, 2007. – № 3. – C. 74-80. 12.��Асосков А.В. и др. Поточные шифры. – М.: КУДИЦ-ОБРАЗ, 2003. �X���K�����O�Z�j�•�g�����:���1�����I�_�l�e�b�p�v�d�b�c�����F���<�����F�Z�e�v�p�_�\�� �<�b�y�\�e�_�g�g�y���a�Z�e�_�`�g�h�k�l�_�c���[�•�e�v�r�h�€���]�e�b�[�b�g�b���g�Z���h�k�g�h�\�•���f�Z�j�d�h�\�k�v�d�b�o���f�h�^�_�e�_�c�� Побудовані два статичні тести у випадковій послідовності і знайдення відмінностей імовірного розподілу елементів послідовності від рівномірного. Перший тест заснований на частотних ста- тистиках мережі Маркова s-го порядку з r частковими зв’язками, другий – на частотних статистиках мережі Маркова змінної длини. Наявні результати комп’ютерних експериментів. �<�X���6�����.�K�D�U�L�Q�����$���,�����3�L�D�W�O�L�W�V�N�L�����0���9�����0�D�O�W�V�H�Z�� �'�H�W�H�F�W�L�R�Q���R�I���+�L�J�K���2�U�G�H�U���'�H�S�H�Q�G�H�Q�F�H�V���%�D�V�H�G���R�Q���0�D�U�N�R�Y�L�D�Q���0�R�G�H�O�V�� Statistical decision rules for detection of high-order dependencies and for testing of �V��dimensional uniformity of discrete time series are constructed. The first test is based on frequency statistics of Markov chain with partial connections. The second test is based on frequency statistics of variable length Markov chain. Asymptotic properties of proposed tests are found. Numerical results are given. �� �K�l�Z�l�v�y���i�h�k�l�m�i�b�e�Z���\���j�_�^�Z�d�p�b�x��������������������������
id nasplib_isofts_kiev_ua-123456789-6885
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn 1561-5359
language Russian
last_indexed 2025-12-01T09:51:34Z
publishDate 2008
publisher Інститут проблем штучного інтелекту МОН України та НАН України
record_format dspace
spelling Харин, Ю.С.
Петлицкий, А.И.
Мальцев, М.В.
2010-03-19T10:26:42Z
2010-03-19T10:26:42Z
2008
Выявление зависимостей большой глубины на основе марковских моделей / Ю.С. Харин, А.И. Петлицкий, М.В. Мальцев // Штучний інтелект. — 2008. — № 3. — С. 121-127. — Бібліогр.: 12 назв. — рос.
1561-5359
https://nasplib.isofts.kiev.ua/handle/123456789/6885
519.2
Построены два статистических теста для выявления зависимости в случайной последовательности и обнаружения отклонений вероятностного распределения элементов последовательности от равно- мерного. Первый тест основан на частотных статистиках цепи Маркова s-го порядка с r частичными связями, второй – на частотных статистиках цепи Маркова переменной длины. Представлены результаты компьютерных экспериментов.
Побудовані два статичні тести у випадковій послідовності і знайдення відмінностей імовірного розподілу елементів послідовності від рівномірного. Перший тест заснований на частотних ста- тистиках мережі Маркова s-го порядку з r частковими зв’язками, другий – на частотних статистиках мережі Маркова змінної длини. Наявні результати комп’ютерних експериментів.
Statistical decision rules for detection of high-order dependencies and for testing of s dimensional uniformity of discrete time series are constructed. The first test is based on frequency statistics of Markov chain with partial connections. The second test is based on frequency statistics of variable length Markov chain. Asymptotic properties of proposed tests are found. Numerical results are given.
ru
Інститут проблем штучного інтелекту МОН України та НАН України
Прикладные интеллектуальные системы
Выявление зависимостей большой глубины на основе марковских моделей
Виявлення залежностей більшої глибини на основі марковських моделей
Detection of High-Order Dependences Based on Markovian Models
Article
published earlier
spellingShingle Выявление зависимостей большой глубины на основе марковских моделей
Харин, Ю.С.
Петлицкий, А.И.
Мальцев, М.В.
Прикладные интеллектуальные системы
title Выявление зависимостей большой глубины на основе марковских моделей
title_alt Виявлення залежностей більшої глибини на основі марковських моделей
Detection of High-Order Dependences Based on Markovian Models
title_full Выявление зависимостей большой глубины на основе марковских моделей
title_fullStr Выявление зависимостей большой глубины на основе марковских моделей
title_full_unstemmed Выявление зависимостей большой глубины на основе марковских моделей
title_short Выявление зависимостей большой глубины на основе марковских моделей
title_sort выявление зависимостей большой глубины на основе марковских моделей
topic Прикладные интеллектуальные системы
topic_facet Прикладные интеллектуальные системы
url https://nasplib.isofts.kiev.ua/handle/123456789/6885
work_keys_str_mv AT harinûs vyâvleniezavisimosteibolʹšoiglubinynaosnovemarkovskihmodelei
AT petlickiiai vyâvleniezavisimosteibolʹšoiglubinynaosnovemarkovskihmodelei
AT malʹcevmv vyâvleniezavisimosteibolʹšoiglubinynaosnovemarkovskihmodelei
AT harinûs viâvlennâzaležnosteibílʹšoíglibininaosnovímarkovsʹkihmodelei
AT petlickiiai viâvlennâzaležnosteibílʹšoíglibininaosnovímarkovsʹkihmodelei
AT malʹcevmv viâvlennâzaležnosteibílʹšoíglibininaosnovímarkovsʹkihmodelei
AT harinûs detectionofhighorderdependencesbasedonmarkovianmodels
AT petlickiiai detectionofhighorderdependencesbasedonmarkovianmodels
AT malʹcevmv detectionofhighorderdependencesbasedonmarkovianmodels