Выявление зависимостей большой глубины на основе марковских моделей
Построены два статистических теста для выявления зависимости в случайной последовательности и обнаружения отклонений вероятностного распределения элементов последовательности от равно- мерного. Первый тест основан на частотных статистиках цепи Маркова 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 |