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

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2008
Hauptverfasser:	Харин, Ю.С., Петлицкий, А.И., Мальцев, М.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2008
Schlagworte:	Прикладные интеллектуальные системы
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/6885
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Выявление зависимостей большой глубины на основе марковских моделей / Ю.С. Харин, А.И. Петлицкий, М.В. Мальцев // Штучний інтелект. — 2008. — № 3. — С. 121-127. — Бібліогр.: 12 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-6885
record_format	dspace
spelling	irk-123456789-68852010-03-22T12:02:53Z Выявление зависимостей большой глубины на основе марковских моделей Харин, Ю.С. Петлицкий, А.И. Мальцев, М.В. Прикладные интеллектуальные системы Построены два статистических теста для выявления зависимости в случайной последовательности и обнаружения отклонений вероятностного распределения элементов последовательности от равно- мерного. Первый тест основан на частотных статистиках цепи Маркова 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. 2008 Article Выявление зависимостей большой глубины на основе марковских моделей / Ю.С. Харин, А.И. Петлицкий, М.В. Мальцев // Штучний інтелект. — 2008. — № 3. — С. 121-127. — Бібліогр.: 12 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/6885 519.2 ru Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Прикладные интеллектуальные системы Прикладные интеллектуальные системы
spellingShingle	Прикладные интеллектуальные системы Прикладные интеллектуальные системы Харин, Ю.С. Петлицкий, А.И. Мальцев, М.В. Выявление зависимостей большой глубины на основе марковских моделей
description	Построены два статистических теста для выявления зависимости в случайной последовательности и обнаружения отклонений вероятностного распределения элементов последовательности от равно- мерного. Первый тест основан на частотных статистиках цепи Маркова s-го порядка с r частичными связями, второй – на частотных статистиках цепи Маркова переменной длины. Представлены результаты компьютерных экспериментов.
format	Article
author	Харин, Ю.С. Петлицкий, А.И. Мальцев, М.В.
author_facet	Харин, Ю.С. Петлицкий, А.И. Мальцев, М.В.
author_sort	Харин, Ю.С.
title	Выявление зависимостей большой глубины на основе марковских моделей
title_short	Выявление зависимостей большой глубины на основе марковских моделей
title_full	Выявление зависимостей большой глубины на основе марковских моделей
title_fullStr	Выявление зависимостей большой глубины на основе марковских моделей
title_full_unstemmed	Выявление зависимостей большой глубины на основе марковских моделей
title_sort	выявление зависимостей большой глубины на основе марковских моделей
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2008
topic_facet	Прикладные интеллектуальные системы
url	http://dspace.nbuv.gov.ua/handle/123456789/6885
citation_txt	Выявление зависимостей большой глубины на основе марковских моделей / Ю.С. Харин, А.И. Петлицкий, М.В. Мальцев // Штучний інтелект. — 2008. — № 3. — С. 121-127. — Бібліогр.: 12 назв. — рос.
work_keys_str_mv	AT harinûs vyâvleniezavisimostejbolʹšojglubinynaosnovemarkovskihmodelej AT petlickijai vyâvleniezavisimostejbolʹšojglubinynaosnovemarkovskihmodelej AT malʹcevmv vyâvleniezavisimostejbolʹšojglubinynaosnovemarkovskihmodelej
first_indexed	2025-07-02T09:44:09Z
last_indexed	2025-07-02T09:44:09Z
_version_	1836527857919066112
fulltext	«Штучний інтелект» 3’2008 121 2Х УДК 519.2 Ю.С. Харин, А.И. Петлицкий, М.В. Мальцев НИИ прикладных проблем математики и информатики БГУ, г. Минск, Беларусь kharin@bsu.by, piatlitski@bsu.by, maltsew@mail.ru Выявление зависимостей большой глубины на основе марковских моделей Построены два статистических теста для выявления зависимости в случайной последовательности и обнаружения отклонений вероятностного распределения элементов последовательности от равно- мерного. Первый тест основан на частотных статистиках цепи Маркова s-го порядка с r частичными связями, второй – на частотных статистиках цепи Маркова переменной длины. Представлены результаты компьютерных экспериментов. Введение Выявление зависимости в случайной последовательности и обнаружение отклоне- ний вероятностного распределения элементов последовательности от равномерного являются важнейшими проблемами в защите информации [1-3], генетике [4] и других приложениях. Обзор существующих методов решения этих задач представлен в [2]. Актуальность проблемы построения новых статистических тестов [5] связана с тем, что: 1) многие известные тесты проверяют лишь одно из вероятностных свойств, характе- ризующих случайную последовательность; 2) большинство тестов построено «эвристи- чески» и не фиксирует семейство альтернатив; 3) многие из существующих тестов не имеют теоретических оценок мощности. В данной статье разработаны два новых теста для статистической проверки гипотезы 0H {наблюдаемая последовательность есть равномерно распределенная случайная последовательность (РРСП)} против альтернативы 01 HH  ; РРСП – это случайная последовательность, элементы которой независимы в совокупности и имеют равномерное распределение вероятностей [2]. Первый тест TЦМ(s,r) основан на частотных статистиках новой марковской модели – цепи Маркова s-го порядка с r частичными связями ЦМ(s,r) [6], а второй тест TЦМПД – на частотных статистиках цепи Маркова переменной длины [7]. Для тестов TЦМ(s,r) и TЦМПД исследована мощность для семейства контигуальных альтернатив, а также проведено сравнение с тестом TЦМ на основе частот цепи Маркова s-го порядка [8]. Тест, основанный на частотных статистиках цепи Маркова с частичными связями Обозначим:  1,...,1,0  NA – множество состояний мощности  N2 ;   1 1 ,...,,    ik kii k i AjjjJ – мультииндекс ( 1 )k i  -го порядка, ik  ; }{ Axt  – однородная стационарная цепь Маркова s-го порядка с вероятностями одношаговых переходов  111,,..., ,...,\| 11 jxjxjxp tsstsstjjj ss   , 11 1   ss AJ , 1t ; Харин Ю.С., Петлицкий А.И., Мальцев М.В. «Искусственный интеллект» 3’2008 122 2Х  sr ,...,2,1 – параметр, называемый числом связей;  00 2 0 1 0 ,...,, rr mmmM  – целочис- ленный r-вектор с упорядоченными компонентами smmm r  00 2 0 11  , называемый шаблоном связей; 1 1 11 1 rJ r rJ A Q q          – некоторая (r+1)-мерная стохасти- ческая матрица. Цепь Маркова {xt} называется цепью Маркова s-го порядка с r частичными связями и обозначается ЦМ(s,r) [6], если ее вероятности одношаговых переходов имеют вид: 100 1 11 ,,,,,,   s rmmss jjjjjj qp  , 11 1   ss AJ . (1) Соотношение (1) означает, что вероятность перехода процесса xt в состояние js+1 зависит не от всех s предыдущих состояний процесса sjj ,...,1 , а лишь от r избранных состояний 00 1 ,..., rmm jj . Если sr  , то получаем цепь Маркова s-го порядка [9]. Примем еще несколько обозначений:  n n xxxX ,,, 211  – наблюдаемая реализация длительности n; ki, – символ Кронекера;                 sn t jx r i jxr r rsЦМ rstiimt MJ 1 , 1 , 1 1),( 11 ;  , 11 1   rr AJ , (2) – частотные статистики цепи Маркова ЦМ(s,r);    1111 01 1),( ,,...,; 00 1    rstrmtmtr r rsЦМ jxjxjxMJ r  , 11 1   rr AJ , – распределение вероятностей )1( r -грамм цепи Маркова с частичными связями;     )/(;;€ 01 1),( 01 1),( snMJMJ r r rsЦМr r rsЦМ    – несмещенная и состоятельная частот- ная оценка вероятности  01 1),( ; r r rsЦМ MJ  , 11 1   rr AJ . Построим тест проверки гипотез H0: }{ tx – РРСП, то есть r+1 1 -1 J q =N , 11 1   rr AJ ; H1,ЦМ(s,r): }{ tx – цепь Маркова ЦМ(s,r), для которой матрица Q имеет вид:   0/11)( 1 1 1 1 1 1   snb N nqq rrr JJJ , 11 1   rr AJ , (3) где 0 1 1 1   Aj Jr rb , 0\|\|11 1 1 1    rr rAJ J b . Соотношение (3) определяет контигуальное семейство альтернатив [10] и означает, что при увеличении длительности n наблю- даемой последовательности, гипотеза H1 сближается с H0 со скоростью  2/1nO . Обозначим     )1(01 1),( 11 1),( ;€)(   r r r rsЦМ rr rsЦМ NMJNsnJ  , 11 1   rr AJ , (4)                           rr rrAJ Aj r rsЦМ Aj r rsЦМrsЦМ J N J 1 11 2 1 1),( 1 1 2 ),(),( 1  . (5) Теорема 1. При n случайная величина ),( rsЦМ в случае справедливости гипотезы H0 имеет 2 -распределение с  1 NNU r степенями свободы. Выявление зависимостей большой глубины на основе марковских моделей «Штучний інтелект» 3’2008 123 2Х При помощи теоремы 1 строится тест TЦМ(s,r) [11] для проверки гипотез H0 и H1,ЦМ(s,r), основанный на частотных статистиках цепи Маркова с r частичными связями: 1) по наблюдаемой последовательности nX 1 длительности n строятся частот- ные статистики   11 1 1 1),( :;   rr r r rsЦМ AJMJ согласно (2); 2) согласно (4), (5) вычисляются статистики   11 1 1 1),( :   rrr rsЦМ AJJ и ),( rsЦМ ; 3) вычисляется Р-значение:  ),(1 rsЦМUGP  , где  UG – функция 2 -распре- деления с U степенями свободы; 4) решение выносится с помощью решающего правила: принимается {H0, если P ; H1,ЦМ(s,r), если P }, где  1,0 – заданный уровень значимости теста. Теорема 2. При n случайная величина ),( rsЦМ в случае справедливости ги- потезы H1,ЦМ(s,r) имеет нецентральное 2 -распределение с U степенями свободы и параметром нецентральности       11 1 1 1 2 1),( 1 rr r AJ JrrsЦМ b N a . (6) Следствие 1. Мощность теста TЦМ(s,r) при n удовлетворяет асимптоти- ческому соотношению:     11 1 , ),( UaU GGw rsЦМ , где   ),(, rsЦМaUG – функция нецентрального 2 -распределения с U степенями свобо- ды и параметром нецентральности ),( rsЦМa , определяемым (6). Следствие 2. Тест TЦМ(s,r) имеет большую мощность по сравнению с тестом TЦМ. Тест, основанный на частотных статистиках цепи Маркова переменной длины Цепь Маркова {xt} называется цепью Маркова переменной длины порядка s [7], если ее вероятности одношаговых переходов имеют вид: 1111 ,,,,,,   sslsss jjjjjj qp  ,  sJll 1 , 11 1   ss AJ . (7) Соотношение (7) означает, что вероятность перехода в состояние js+1 зависит не от всех s предыдущих состояний, а лишь от  sJll 1 предыдущих состояний. Если  1 sl J s= , то получаем цепь Маркова s-го порядка [9]. Функция )(l определяется с помощью контекстной функции   s ls s JJc 11  ,    ss JcJl 11  , ss AJ 1 . Контекстную функцию удобно представлять в виде корневого дерева  , которое называется контекстным деревом. У каждой вершины в таком дереве может быть не более N потомков, поскольку каждому узлу (кроме корня) соответствует элемент из множества состояний A . Каждому значению контекстной функции соответствует ветвь данного дерева. Примем обозначения:                  ln t l i jx l ЦМПД iit J 1 1 1 , 1 1 1  , lJ1 , Ajl 1 , (8) Харин Ю.С., Петлицкий А.И., Мальцев М.В. «Искусственный интеллект» 3’2008 124 2Х – частотные статистики цепи Маркова переменной длины;    111 1 1 ,,...,    lltlltt l ЦМПД jxjxjxJ , lJ1 , Ajl 1 , – распределение вероятностей )1( l -грамм цепи Маркова переменной длины;     )/(€ 1 1 1 1 lnJJ l ЦМПД l ЦМПД    – несмещенная и состоятельная частотная оценка вероятности  1 1 l ЦМПД J , lJ1 , Ajl 1 . Построим тест проверки гипотез H0: }{ tx – РРСП, то есть l+1 1 -1 J q =N , lJ1 , Ajl 1 ; H1,ЦМПД: }{ tx – цепь Маркова ЦМ(s,r), для которой матрица Q имеет вид аналогичный (3):   0/11)( 1 1 1 1 1 1   snb N nqq lll JJJ , lJ1 , Ajl 1 , (9) где 0 1 1 1   Aj Jl lb , 0\|\| 11 1 1,    AjJ Jl l lb  . Соотношение (9) определяет контигуальное семейство альтернатив [10]. Определим случайные величины:     )1(1 1 11 1 €)(   ll ЦМПД ll ЦМПД NJNsnJ  , lJ1 , Ajl 1 , (10)                            l llJ Aj l ЦМПД Aj l ЦМПДЦМПД J N J 1 11 2 1 1 1 1 2 1 (11) Теорема 3. При n случайная величина ЦМПД в случае справедливости гипотезы H0 имеет 2 -распределение с  \| \| 1U N  степенями свободы. При помощи теоремы 3 строится тест TЦМПД для проверки гипотез H0 и H1,ЦМПД, основанный на частотных статистиках цепи Маркова с r частичными связями: 1) по наблюдаемой последовательности nX 1 длительности n строятся частотные статистики   AjJJ l ll ЦМПД    11 1 1 ,:  согласно (8); 2) согласно (10), (11) вычисляются статистики   AjJJ l ll ЦМПД    11 1 1 ,:  и ЦМПД ; 3) вычисляется Р-значение:  ЦМПДUGP  1 , где  UG – функция 2 - распределения с U степенями свободы; 4) решение выносится с помощью решающего правила: принимается {H0, если P ; H1,ЦМПД, если P }, где  1,0 – заданный уровень значимости теста. Теорема 4. При n случайная величина ЦМПД в случае справедливости гипотезы H1,ЦМПД имеет нецентральное 2 -распределение с U степенями свободы и параметром нецентральности      AjJ JЦМПД l l lb N a 11 1 1 , 2 \|\| 1  . (12) Следствие 3. Мощность теста TЦМПД при n удовлетворяет асимпто- тическому соотношению:     11 1 , UaU GGw ЦМПД , где   ЦМПДaUG , – функция нецентрального, 2 -распределения с U степенями свободы и параметром нецентральности ЦМПДa определяемым (12). Следствие 4. Тест TЦМПД имеет большую мощность по сравнению с тестом TЦМ. Выявление зависимостей большой глубины на основе марковских моделей «Штучний інтелект» 3’2008 125 2Х Численные результаты Проведены численные эксперименты на модельных и реальных данных. Пример 1 (модельные данные). На рис. 1 представлена зависимость мощности тестов TЦМ(s,r), TЦМ для альтернативы H1,ЦМ(s,r) от n при 0,05  , N = 4, s = 6, r = 4,  1,4,5,60 rM и матрице Q, для которой: 1) 0,1 rJ b ,…, 2,1 NJ rb генерировались с помощью стандартного генератора равномерно распределенных на [-13,13] псевдослучайных чисел, а )...( 2,0,1, 111   NJJNJ rrr bbb ; 2) функция нецентрального 2 -распределения имеет 768U степеней свободы и параметр нецентральности ( , ) 138,5ЦМ s ra  . На этом рисунке квадратиками и кружками указаны значения оценки мощности w€ для TЦМ(s,r) и TЦМ соответственно, полученные с помощью метода Монте-Карло при числе прогонов, равном 1000; пунктирные линии – верхняя и нижняя 99 % доверительные границы для мощности; сплошная линия – теоре- тическое значение w, найденное в следствии 1. Из рис. 1 видно, что для указанных значений параметров мощность теста TЦМ(s,r) приблизительно в 4 раза превосходит мощность теста TЦМ, что согласуется со следствием 2. Отметим, что при n мощность тестов не стремится к 1, так как при увеличении n гипотеза H1 сближается с H0 (контигуальная постановка задачи). Рисунок 1 – Зависимость мощности от n Пример 2 (модельные данные). Исследовалась зависимость мощности тестов TЦМПД, TЦМ для альтернативы H1,ЦМПД от n при 0,05  , N = 2, s = 8 и контекстном дереве  , представленном на рис. 2. Эта зависимость проиллюстрирована на рис. 3 (квадратики и кружки – значения оценки мощности w€ для TЦМПД и TЦМ соответ- ственно; пунктирные линии – верхняя и нижняя 99 % доверительные границы для мощности; сплошная линия – теоретическое значение w, определяемое следствием 3). Из рис. 3 видно, что для этих значений параметров мощность теста TЦМПД прибли- зительно в 3 раза превосходит мощность теста TЦМ, что согласуется со следствием 4. Харин Ю.С., Петлицкий А.И., Мальцев М.В. «Искусственный интеллект» 3’2008 126 2Х Рисунок 2 – Контекстное дерево  Рисунок 3 – Зависимость мощности от n Пример 3 (реальные данные). Исследовался генератор псевдослучайных после- довательностей А5/1 [12], состоящий из трех коротких линейных регистров сдвига с обратной связью. Алгоритм А5/1 используется в сети GSM для обеспечения защиты информации на уровне базовая-мобильная станция. При тестировании генератора А5/1 с помощью теста TЦМ(s,r) его выходная после- довательность разбивалась на 12-битовые фрагменты, и каждый такой фрагмент рассматривался как буква алфавита  12,...,1,0 12 A , мощности 122N . На вход теста TЦМ(s,r) поступали 250 реализаций выходной последовательности длительности n бит каждая, сгенерированных этим криптоалгоритмом; параметры теста: 2s , 1r , )1(0 rM , 0,05  . Результаты исследований приведены в табл. 1. Для РРСП при уровне значимости 0,05  среднее число отклоненных из 250 реализаций равнялось бы 12,5. Таким образом, представленные в табл. 1 результаты свидетельствуют о сильной неслучайности выходной последовательности алгоритма А5/1. Таблица 1 – Результаты тестирования генератора А5/1 Длина последовательности n, бит 2124  2125  2126  2127  2128  Количество (частота) отклоненных тестом TЦМ(s,r) реализаций 37 (0,148) 59 (0,236) 72 (0,288) 91 (0,364) 105 (0,420) Выявление зависимостей большой глубины на основе марковских моделей «Штучний інтелект» 3’2008 127 2Х Заключение Построены статистические тесты на основе марковских частотных статистик, которые позволяют выявлять зависимости высокого порядка и специфической структуры. Проведенные компьютерные эксперименты на модельных и реальных данных иллюстрируют работоспособность построенных тестов. Литература 1. Кнут Д. Искусство программирования: В 3 т. – М.: Мир, 1992. 2. Харин Ю.С. и др. Математические и компьютерные основы криптологии. – Мн.: Новое знание, 2003. 3. Иванов М.А., Чигунков И.В. Теория, применение и оценка качества генераторов псевдослучайных последовательностей. – М.: КУДИЦ-ОБРАЗ, 2003. 4. Уотермен М.С. Математические методы анализа последовательностей ДНК. – М.: Мир, 1999. 5. Харин Ю.С., Ярмола А.Н., Петлицкий А.И. Методы и алгоритмы статистического тестирования генераторов случайных и псевдослучайных последовательностей в системах информационной безопасности // Искусственный интеллект. – 2006. – № 3. – С. 793-803. 6. Харин Ю.С. Цепи Маркова с r-частичными связями и их статистическое оценивание // Доклады НАН Беларуси. – 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. Ю.С. Харін, А.І. Петлицький, М.В. Мальцев Виявлення залежностей більшої глибини на основі марковських моделей Побудовані два статичні тести у випадковій послідовності і знайдення відмінностей імовірного розподілу елементів послідовності від рівномірного. Перший тест заснований на частотних ста- тистиках мережі Маркова s-го порядку з r частковими зв’язками, другий – на частотних статистиках мережі Маркова змінної длини. Наявні результати комп’ютерних експериментів. Yu.S. Kharin, A.I. Piatlitski, M.V. Maltsew Detection of High-Order Dependences Based on Markovian Models 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. Статья поступила в редакцию 02.07.2008.

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

Institution

Ähnliche Einträge