Київський національний університет імені Тараса Шевченка

Жигайло Ольга Олександрівна

УДК 519.21

Оптимальне оцінювання для марковських систем

в умовах неповної статистичної інформації

01.05.01 – теоретичні основи інформатики

та кібернетики

Автореферат

дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Київ – 2002

Дисертацією є рукопис

Робота виконана на кафедрі прикладної статистики

Київського національного університету імені Тараса Шевченка

Науковий керівник:

доктор фізико-математичних наук, професор кафедри

прикладної статистики факультету кібернетики

Київського національного університету

імені Тараса Шевченка

Война Олександр Андрійович

Офіційні опоненти:

доктор фізико-математичних наук,

академік НАН України, професор

Королюк Володимир Семенович

Інститут математики НАН України,

радник при дирекції

кандидат фізико-математичних наук, доцент

Заславський Володимир Анатолійович

Київський національний університет імені Тараса

Шевченка, факультет кібернетики,

доцент кафедри системного аналізу та

теорії прийняття рішень

Провідна установа:

Інститут кібернетики імені В.М.Глушкова

НАН України, відділ математичних методів

теорії надійності складних систем

Захист відбудеться 25.04.20022002 року о 15 на засіданні спеціалізованої

вченої ради Д 26.001.09 Київського національного університету

імені Тараса Шевченка, Київ, пр. Глушкова, 2,

корп. 6, ф-т. кібернетики, ауд. 40, тел. 252-58-83,

факс 252-59-77,

З дисертацією можна ознайомитись у Науковій бібліотеці

Київського національного університету імені Тараса Шевченка

Київ, вул. Володимирська, 58.

Автореферат розісланий 23 березня 2002 р.

Вчений секретар

спеціалізованої вченої ради Шевченко В.П.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ.

Актуальність теми. При вивченні багатьох систем природи та суспільства широко використовуються стохастичні моделі. Аналіз і оптимізація цих моделей вимагає наявності розвинених методів оптимального оцінювання для різноманітних класів статистичних задач. Процедури оцінювання значно ускладнюються в ситуації, коли інформація про функціонування досліджуваної системи є неповною, тобто у випадках відсутності "прямих" спостережень за характеристикою системи, для якої потрібно проводити оцінювання. Застосування обчислювальної техніки для розв'язання цих задач поставило також проблему побудови таких алгоритмів оптимального оцінювання, які можна було б ефективно використовувати на практиці.

Математичне обгрунтування та побудова алгоритмів параметричного та непараметричного оцінювання для стохастичних систем за неповними спостереженнями є основним напрямком досліджень в теорії прихованих марковських моделей. Ці моделі мають важливе значення для розв'язання проблем, пов'язаних із статистичним аналізом сигналів, зокрема, в теорії автоматичного розпізнавання мови, при вивченні ринку цінних паперів, надійності систем, в астрономії, в метеорології і в багатьох інших галузях. Серед робіт, присвячених питанню відновлення станів неспостережуваного процесу в теорії прихованих марковських моделей, потрібно відмітити статті Л. Рабинера, Б. Янга, Дж. Д. Форни-мл. Аналогічні задачі в більш загальному контексті вивчались в роботах Р. Ліпцера, А. Ширяєва та інших. Однак, поки що не до кінця досліджені питання побудови конструктивних методів оцінювання функціоналів прихованого потоку. Розв'язанню цієї проблеми сприяли результати, отримані в роботах О. Войни. Ітераційний метод оцінювання параметрів марковських моделей в умовах відсутності повної статистичної інформації було запропоновано у дослідженнях Л. Баума, Т. Петри та інших. На необхідність вивчення подібних задач у теорії масового обслуговування було вказано Д. Кендалом. Умови, за якими характеристики системи можуть бути відновлені за вихідним потоком, розглядались у роботах академіка І. М. Коваленко та інших. На жаль, пряме застосування існуючих методів оцінювання характеристик стохастичних моделей за неповними спостереженнями в багатьох практично важливих випадках себе не виправдовує через неможливість їх ефективної машинної реалізації. Все це викликає необхідність у розвиненні існуючих, створенні та математичному обгрунтуванні нових конструктивних методів статистичного аналізу частково спостережуваних марковських систем, що і обумовлює актуальність даної дисертаційної роботи.

Зв'язок роботи з науковими програмами, планами, темами. Робота виконана у відповідності з планом наукових досліджень кафедри прикладної статистики факультету кібернетики Київського національного університету імені Тараса Шевченка: б/т № 97064, б/т № 97549.

Мета і задачі дослідження. Метою даного дослідження є розробка конструктивних методів непараметричного та параметричного оцінювання для прихованих марковських моделей, зокрема, побудова процедур оптимального оцінювання для однорідних процесів Маркова з неперервним часом та теоретичне обгрунтування і побудова алгоритмів оптимального оцінювання характеристик СМО типу M|M|n|m в умовах відсутності повної статистичної інформації.

Наукова новизна одержаних результатів. У роботі отримано нові формули для знаходження оптимальних оцінок моментів попадання марковської системи у фіксований стан та оцінок кількості таких попадань за час спостережень. Зміни, внесені авторкою до методу “максимальної правдоподібності”, дозволяють побудувати ітераційну процедуру оцінювання інтенсивності надходження й інтенсивності обробки вимог у СМО при відсутності повної статистичної інформації та дають можливість розв'язати задачі параметричного оцінювання для однорідного регулярного неперервного справа процесу Маркова у випадку, коли величини, що визначають поведінку процесу, є лінійними функціями від невідомих параметрів. У роботі сформульовано нову постановку статистичної задачі для випадку, коли спостереження над марковською системою є неповними і, крім того, деформуються певним чином, і запропоновано оригінальні методи її вирішення. Знайдено умови існування й властивості оцінок параметрів деформації, отриманих за допомогою цих методів.

Практичне значення одержаних результатів. Розроблені методи можна безпосередньо використовувати при статистичному аналізі СМО в умовах неповних статистичних спостережень. На основі теоретичних результатів, отриманих у дисертаційній роботі, було розроблено та програмно реалізовано алгоритми оптимального оцінювання для частково спостережуваних марковських систем. Ефективність роботи методів ілюструється даними статистичних експериментів, наведеними в додатку.

Особистий внесок здобувача. Всі результати роботи отримані авторкою самостійно. Науковому керівнику належить постановка задач, ідеї та пропозиції що до методів їх розв'язання.

Апробація результатів дисертації. Результати дисертаційної роботи доповідались на III Швецько-Українській конференції з математичної статистики (Київ 1999 р.); на міжнародній конференції ”Прогнозування та прийняття рішень в умовах невизначеності” (Київ 2001 р.). Робота доповідалась на наукових семінарах Київського національного університету імені Тараса Шевченка та Інституту Кібернетики імені В.М.Глушкова НАН України.

Публікації. Автором по темі дисертації було опубліковано 6 наукових робіт, із них 4 у виданнях, затверджених ВАК України.

Структура та обсяг роботи. Дисертація складається зі вступу, трьох розділів, висновків, додатку та списку використаних джерел, що налічує 51 найменування. Загальний обсяг дисертації становить 138 сторінок, основний текст роботи викладено на 111 сторінках.

ЗМІСТ РОБОТИ.

У першому розділі дисертації дається огляд літератури по темі дисертації, обгрунтування актуальності роботи та визначається вигляд досліджуваної стохастичної моделі: нехай х(t), t , 1, …– однорідний ланцюг Маркова зі зліченною множиною станів E { , 1, … }; z(t)(l), lОE, t , 1, …– сімейство незалежних від процесу x(t), t , 1, … випадкових величин, незалежних при різних t, розподіл яких не залежить від t. Послідовністю умовно незалежних випадкових величин, визначених на ланцюгу Маркова x(t), t , 1, …, називається випадковий процес t(t)(t)(х(t)), t , 1, …

У цій роботі пропонується до розгляду наступна схема статистичного експерименту: спостерігається лише процес t(t)(t)(х(t)), t , 1, …, інформація про траєкторію ланцюга Маркова х(t), t , 1, … за час спостережень повністю відсутня. За цими спостереженнями потрібно оцінити характеристики процесу h(t) { x(t), t(t) }, t , 1, …

Стохастичні моделі, які можуть бути описані за допомогою цієї схеми, отримали назву прихованих марковських моделей.

Розглянемо систему масового обслуговування (СМО) типу М|М|n|m. Ця система згідно загальноприйнятої класифікації складається з n однакових обслуговуючих приладів, має m місць в черзі. Потік вимог, що надходять у систему, є пуассонівським процесом із параметром l. Час обслуговування вимоги – випадкова величина, що має показниковий розподіл із параметром m. Нехай ti, i , , …(t0 ) – впорядкована по зростанню послідовність моментів, коли в системі змінювалась кількість вимог або вимога надійшла в систему і була втрачена.

Пропонується така схема спостережень: спостерігається лише послідовність  {0, t1, … }, при цьому інформація про те, які зміни відбувалися в системі в моменти tk, k , 1, …, повністю відсутня. Задача полягає в знаходженні оцінок характеристик системи за спостереженнями .

Позначимо через x(t) – кількість вимог у системі в момент часу tі0, враховуючи як ті вимоги, що обслуговуються, так і ті, що чекають на обслуговування в черзі. ?(t), t?0 – однорідний марковський процес з неперервним часом і скінченною множиною станів E { , 1, …, N }, де N n + m. Враховуючи конструктивну побудову процесу ?(t), t?0, можна стверджувати, що задачі статистичного оцінювання за спостереженнями для СМО типу М|М|n|m зводяться до відповідних задач теорії прихованих марковських моделей.

Другий розділ складається з двох підрозділів, в яких розглядається задача непараметричного оцінювання для марковських процесів в умовах неповної статистичної інформації.

У підрозділі 2.1 пропонується підхід до оптимального оцінювання функціоналів типу моментів попадання у фіксовану множину станів частково спостережуваних марковських систем. У пункті 2.1.1 ( теорема .1 ) виводяться формули для підрахунку умовних ймовірностей для схеми умовно незалежних випадкових величин, визначених на однорідному ланцюгу Маркова зі зліченною множиною станів.

У пункті 2.1.2 знайдено оптимальні оцінки моменту k-го попадання в 0-ий стан ланцюга Маркова x(n), n , 1, … з множиною станів Е { , 1, …, N }, в умовах, коли наявні спостереження лише над послідовністю умовно незалежних випадкових величин ?(n), n , 1, …, визначених на процесі x(n).

Нехай F(?) { Fn, n , 1,… } – потік s-алгебр Fn ={),…,?(n) }, a М[F(?)] – клас марковських моментів відносно потоку F(? );

F(x) {Fn(x), n , 1,…} – потік s-алгебр Fn(x){ x(0),…,x(n)}, а М[F(x)] – клас марковських моментів відносно потоку F(x).

Марковський момент ?*ОМ[F(?)] назвемо оптимальною оцінкою моменту tОМ[F(x)], якщо

M| t – ?* |  M| t – ? |

У теоремі 2.2 доводиться, що якщо ланцюг Маркова х(n), n 0, 1,… не звідний, то оптимальною оцінкою моменту k-го попадання процесу х(n) в 0-й стан є випадкова величина

c(k)*{ n, nі0: Ј 0.5 },

де (i, j){ x(n) i, x*(n) j/ Fn}, iОE, jО{0, 1, …}, а x*(n), n , 1, … – випадковий процес, що вказує на кількість попадань процесу x(n) в 0-й стан на проміжку часу від 0 до n. Значення (i, j) підраховуються за рекурентними формулами, які будуються на основі тверджень теореми 2.1. Оптимальність оцінки c(k)* доводиться з використанням результатів теорії оптимальних правил зупинки марковських послідовностей.

Як наслідок теореми 2.2 ( теорема 2.4 ) у пункті 2.1.3 отримано формули для знаходження оптимальних оцінок моменту k-го попадання в 0-ий стан однорідного регулярного неперервного справа процесу Маркова ?(t), tі0 зі скінченною множиною станів в умовах, коли спостерігаються тільки моменти стрибків процесу.

У пункті 2.1.4 ( теорема 2.5 ) розв'язано задачу оптимального оцінювання моменту k-ої втрати вимоги в СМО типу М|М|n|m за спостереженнями  { t0, t1, … }. Зауважимо, що для моментів, коли система була спустошена або навпаки заповнена повністю, формули для підрахунку оцінок можна отримати як безпосередній наслідок тверджень теореми 2.2.

У першому пункті підрозділу 2.2 знайдено оцінки – кількості попадань ланцюга Маркова x(n), n = , , … в 0-й стан на проміжку часу від 0 до r за спостереженнями ={?0, …, ?r} над процесом ?(n), (?tt), t , , …, r).

Нехай mr = j(?0, ?1, …, ?r) – деяка дискретна випадкова величина, що приймає значення із множини X= {0, 1, …, r}. mr* назвемо оптимальною оцінкою , якщо

M|– mr* |  M| – mr |

Теорема 2.6. Оптимальною оцінкою є випадкова величина

mr* max{k: c(k)*Јr },

де c(k)* – оптимальна оцінка моменту k-го попадання процесу Маркова x(n), n , 1, … в 0-й стан. Якщо c(1)*>r, то mr* .

У теоремі 2.7 пункту 2.2.2 знайдено аналогічні оцінки кількості втрачених вимог у СМО типу M|M|n|m на проміжку часу [0, tr+1], за спостереженнями  {t0, t1, …, tr+1}.

У пункті 2.2.3 отримано оцінки випадкової величини ( теорема 2.8 ) і кількості втрачених вимог у СМО за час спостережень ( теорема 2.9 ) за наступним критерієм оптимальності: нехай n, hr – дискретні випадкові величини, що приймають значення із множини X { , , …, r } і hr = j(t0, …,r)ОX, де t0, t1, … – деяка послідовність випадкових величин. Назвемо h0 оптимальною оцінкою n, якщо P{0 № } P{r № }.

Третій розділ дисертації присвячено задачам параметричного оцінювання для марковських систем в умовах неповної статистичної інформації, тобто закон розподілу процесу h(t) { x(t), t(t) }, t , 1, …, що відповідає прихованій марковській моделі, залежить від невідомих параметрів, значення яких потрібно оцінити лише за спостереженнями над процесом t(t).

У підрозділі 3.1 пропонується ітераційна процедура знаходження оцінок невідомих параметрів, яка виникає при спробі застосування методу максимальної правдоподібності до статистичних задач такого типу: вектор початкового розподілу q { qi, i?E }= { qi(q), i?E }, Ppij||pij(q)||, i, j?E – ?матриця перехідних ймовірностей за один крок?ланцюга Маркова x(k), k , 1, … та функції fi(x) fi(x,iОE – щільності розподілу випадкових величин z(t)(i), iОE, (t)(t)(х(t)), t , 1, … ) залежать від невідомого параметра qОQНRr, де Q – множина можливих значень параметра q.

За спостереженнями ={?0, …, ?n} над процесом ?(t) потрібно знайти таку оцінку невідомого параметра qОQ, яка б максимізувала функцію правдоподібності .

У пункті 3.1.1 на прикладі побудови алгоритму переоцінки елементів інфінітезимальної матриці однорідного регулярного неперервного справа процесу Маркова x(t), tі0  з множиною станів E { , 1, …, N } в умовах, коли спостерігаються тільки моменти стрибків процесу, демонструється загальний принцип розв'язання подібних задач, який базується на використанні допоміжної функції Баума.

У пункті 3.1.2 ( теорема 3.2 ) обгрунтовується ітераційна процедура пошуку оцінок інтенсивності вхідного потоку ?????і інтенсивності обслуговування ??для СМО типу M|M|n|m за спостереженнями  { t0, t1, …, tT+1 }, таких, що максимізують функцію правдоподібності L? (), де q {m }– сукупність невідомих параметрів.

У пункті 3.1.3 ( теорема 3.3 ) проводиться узагальнення методу розв'язання задачі пункту 3.1.2 на випадок, коли елементи інфінітезимальної матриці A=||aij||, i, jОE марковського процесу x(t), tі0 є лінійними функціями від невідомих параметрів q { ui, i }, uk>0, k=:

де – відомі константи, такі, що mi>0.

На основі перетворень = G(??), отриманих у пунктах 3.1.1, 3.1.2 і 3.1.3, побудовані ітераційні процедури для переоцінки невідомих параметрів, які мають наступні властивості:

1. Для довільного початкового значення параметра q процедура переоцінки буде збігатися до деякої критичної точки функції правдоподібності Lq() по змінній q.

2. На кожному кроці алгоритму гарантується збільшення значення функції правдоподібності Lq(), поки не буде виконуватись = G().

У підрозділі 3.2 пропонується задача параметричного оцінювання для марковських систем за неповними деформованими спостереженнями. Яким саме буде спотворення інформації, залежить від стану, в якому перебуває система в момент спостережень. При цьому спостереження над станами системи, які визначають вигляд функцій деформації, не проводяться.

У пункті 3.2.1 пропонується метод “моментів” для такої статистичної задачі: нехай x(t), t?0 – однорідний регулярний неперервний справа процес Маркова з множиною станів E{ ,…, N } та матрицею інтенсивностей Aaij||, i, j? E; tk+1 min{ t: t>tk,t)tk) }, t0 ; tk tk+1 –k, k , 1, …; ?(t) max{ k: tk? t }; x(k)tk), k , 1, …; { di(t), i?E },?0 – сукупність деяких вимірних функцій.

Вектор  { ?1, …, ??(T), ?(T) }, де ?k dx(k  – 1)(?k – 1), k , …,T), ?(T) dx(?(T))(T –?(T)), будемо називати частково спостережуваною траєкторією процесу ?(t), яка була деформована функцією D(t) { di(t), i?E }, t?0. 

Нехай D(t) D(t, { di(t, i?E }, t?0, тобто функція деформації D(t) залежить від невідомого параметра ? {1, …,r }?QН Rr, істинне значення якого ?0 {10, …, ?r0 } є внутрішньою точкою Q. Тоді

?k dx(k – 1)(?k – 1, ?0), k , …, n(T), ?(T) = dx(?(T)) (T – t?(T), ?0).

Задача полягає в знаходженні оцінок невідомого параметра ? за – частково спостережуваною траєкторією процесу ?(t), яка була деформована функцією D(t,.

У методі “моментів” для розв'язання цієї задачі використовуються статистики

Нехай m(s)(j,, j?E, s= , ???Q??а aj – ajj, j?E.

Теорема 3.4. Нехай виконуються такі умови.

1. Вкладений ланцюг Маркова x(t), t 0, 1, 2, … для процесу x(t), t?0 незвідний і неперіодичний, а { rj, j ? E} – його стаціонарний розподіл.

2. Для l  функції

скінченні і неперервні в деякому околі ??0 точки ?0 {10, …, ?r0 }.

3. В околі ??0 існують та неперервні похідні m(l)(?1, …, ?r),  j, l , і при цьому Якобіан

відмінний від нуля в точці ?0 .

4. Існує окіл U() точки  { m(1)(?0), …, m(r)(?0) } такий, що для будь-якого ы { u1, …, ur }? U() система рівнянь

m(l) (?1, …, ?r)l, l 

має єдиний розв'язок ? {1, …, ?r } в області Q.

Тоді з ймовірністю, що прямує до 1 при n????система рівнянь

m(l) (?1, …, ?r) , l 

має єдиний розв'язок  { , …,  }, що є спроможною оцінкою параметра ?0.

У теоремі 3.5 сформульовано умови, за якими розподіл випадкового вектора

?  { ( – m(1)(?0)), …, ( – m(r)(?0)) }

збігається слабо при n??? до багатовимірного нормального розподілу, визначається вигляд вектора середніх та коваріаційної матриці цього розподілу. Як наслідок теореми 3.5 доводиться асимптотична нормальність випадкового вектора

? = { ( – ?10), …, ( – ?r0) }.

У підпункті 3.2.1.3 за допомогою методу "моментів" отримано формули для знаходження оцінок невідомих параметрів у випадку, коли функції деформації мають вигляд di( x, q )x, iE, q?QНR. Спроможна та асимптотично нормальна оцінка q буде мати вигляд .

У підпункті 3.2.1.4 доведено, що у випадку, коли q {1, q2 }, q?QНR2, і di( x, q )j(i) x, i?E, j(i)?{1, 2}, I(l) { i?E: j(i) l }, l , 2, якщо відомо, що справжнє значення параметра деформації q0?QНQ1={ {q1,2}: q1<q2} або q0?QНQ2 = { {q1,2}: q1>q2 }, то з ймовірністю, що прямує до 1 при n®Ґ, значення D > 0 і ={q1(n),2(n)}, що задається формулами:

у випадку q0ОQНQ1: b–1,

у випадку q0ОQНQ2: b–1,

де D b2(db2 +ga2) – b2 gd, edb2+ga2)–1,

є спроможною й асимптотично нормальною оцінкою параметра деформації q0.

У підпункті 3.2.1.5 отримано аналогічні результати для функцій деформації вигляду di( x,j(i) +, i?E, j(i)?{1, …, r}, q {q1, …,r}?QНRr, де r 1 або r 2.

У пункті 3.2.2 пропонується підхід до задачі оцінювання параметрів деформації спостережень над процесом гибелі та народження c(t), tі0 із множиною станів E { , 1, …, N }, який вводиться таким чином: нехай tk, k , 1, …( t0 ) – моменти переходів процесу c(t) із стану в стан; час перебування процесу c(t), tі0 в стані j?E має показниковий розподіл з параметром lj >0; n(t) max{ k: tk Ј t }; x(k)tk), k = , 1, … – однорідний ланцюг Маркова з матрицею перехідних ймовірностей Ppij||, i, j?E, де

Функція деформації D(t, { di(t,i?E }, tі0, q?QНRN+1 залежить від невідомого параметра q { q0, …, qN }, справжнє значення якого q0 є внутрішньою точкою множини Q. Спостерігається випадковий вектор  { x0, …, xn(T)–1, x(T) }, де xk dx(k)(tk, q0), k , 1, …,T) – 1; x(T) dx(n(T))(T – У роботі для пошуку оцінок параметрів деформації за вектором спостережень застосовується метод “кореляційної залежності”, в якому використовуються статистики

Нехай , i?E. Особливості процесу c(t), tі0 дозволяють знаходити оцінки , i?E із наступної системи рівнянь:

де  { ri, i?E } – стаціонарний розподіл ланцюга Маркова x(n), Ps =||, i,jОE– матриця перехідних ймовірностей процесу x(n) за s кроків.

У теоремі 3.6 доведено, що якщо всі власні числа матриці P різні і <Ґ, i?E, то з ймовірністю, що прямує до 1 при n®Ґ, ця система рівнянь має дійсні розв'язки, один з яких є спроможною оцінкою F0. Якщо при цьому , i?E де , то розподіл випадкового вектора

при n®Ґ прямує слабо до багатовимірного нормального розподілу.

У наслідку теореми 3.6 сформульовані умови існування спроможної та асимптотично нормальної оцінки параметра q0, яка знаходиться із системи рівнянь:

Fi(q) i(n), i?E.

У підпункті 3.2.2.3 сформульовано алгоритм знаходження оцінки F0. У підпункті 3.2.2.4 доводиться, що у випадку, коли N , всі умови, які накладаються на процес c(t), tі0 в теоремі 3.6, виконані. Наведено приклади функцій деформації D(t,для яких виконуються умови теореми 3.6 і для яких оцінку невідомого параметра q0 можна записати в явній формі, використовуючи оцінку F0.

У пункті 3.2.3 розглянуто задачу параметричного оцінювання для СМО типу M|M|n|m за спостереженнями  { x0, …, xn(T)–1, x(T) }, де

xk dx(k)(tk, q0), k , 1, …,T) –1; x(T) dx(n(T))(T –n(T), q0),

а tk tk+1 – tk, k , 1, … – проміжки часу між черговими змінами стану системи, di(t, q), i?E, tі0, q?QНRr – функції деформації, що залежать від невідомого параметра q {1, …, qr}, справжнє значення якого q0 є внутрішньою точкою множини Q. У підпункті 3.2.3.1 (теорема 3.7) сформульовано метод “моментів” для розв'язання цієї задачі та отримано спроможні та асимптотично нормальні оцінки параметрів деформації, аналогічні до оцінок пункту 3.2.1.

У підпункті 3.2.3.2 пропонується розглянути випадок, коли q?QНRr, r Ј N + і функції деформації мають вигляд

di(x,, i?E, j(i)?{ , …, r }.

Задача полягає у знаходженні оцінок параметрів деформації q?QНRr таких, що максимізують функцію правдоподібності за спостереженнями . Знайдено вигляд перетворення переоцінки невідомих параметрів у випадку неповних деформованих спостережень для схеми умовно незалежних випадкових величин, визначених на ланцюгу Маркова. Як наслідок представлені оцінки параметрів деформації спостережень, які проводяться над СМО. Розроблена ітераційна процедура знаходження оцінок параметрів деформації збігається до деякої критичної точки функції правдоподібності, яка є фіксованою точкою перетворення переоцінки, при цьому на кожному кроці значення функції правдоподібності збільшується.

У підрозділі 3.3 описується інтерфейс користувача програми, в якій реалізуються розроблені в дисертації алгоритми статистичного оцінювання характеристик марковських систем за неповними спостереженнями. Програма включає в себе наступні функціональні можливості:

Моделювання траєкторії для заданих марковських процесів із неперервним часом, зокрема, для СМО типу M|M|n|m.

Знаходження непараметричних оцінок:

оцінок моментів попадання та кількості попадань марковської системи в заданий стан за час спостережень;

оцінок моменту k-ої втрати вимоги та кількості втрачених вимог за час спостережень у СМО типу M|M|n|m.

Знаходження параметричних оцінок ітераційним методом “максимальної правдоподібності”:

оцінок елементів інфінітезимальної матриці та вектору початкового розподілу марковського процесу;

оцінок інтенсивності обробки та інтенсивності надходження вимог у СМО типу M|M|n|m.

Знаходження оцінок параметрів деформації спостережень над марковськими системами:

методом “моментів” для випадку, коли розмірність вектора невідомих параметрів дорівнює 1 або 2;

методом “максимальної правдоподібності” у випадку, коли розмірність вектора невідомих параметрів дорівнює 1 або 2, або співпадає з розмірністю множини станів досліджуваної марковської системи.

Дано аналіз чисельних результатів роботи алгоритмів, які ілюструються даними, наведеними в додатку.

ВИСНОВКИ

В даній роботі розглянуто клас задач, які виникають при спробі вирішення проблем параметричного та непараметричного оцінювання для СМО в умовах неповної статистичної інформації. Розв'язано задачі параметричного та непараметричного оцінювання, які виникають в рамках теорії прихованих марковських моделей, зокрема, при статистичному аналізі частково спостережуваних однорідних марковських процесів з неперервним часом.

Основними результатами даної дисертаційної роботи є:

Отримано формули для оптимального оцінювання моментів попадання у фіксований стан марковських систем в умовах неповних статистичних спостережень. Зокрема, отримано оптимальні оцінки моментів k-ої втрати вимоги в СМО типу M|M|n|m.

Знайдено оптимальні оцінки кількості попадань процесу Маркова в певний стан за час спостережень та кількості втрачених вимог на фіксованому проміжку часу в СМО типу M|M|n|m.

Побудовано ітераційний метод типу методу “максимальної правдоподібності” для оцінювання параметрів СМО типу M|M|n|m при неповних спостереженнях. Цей метод узагальнюється для випадку, коли елементи інфінітезимальної матриці марковського процесу є лінійними функціями від невідомих параметрів.

Розглянуто нову постановку задачі статистичного оцінювання для марковських систем за неповними деформованими спостереженнями. Для оцінювання параметрів деформації побудовано метод ”моментів” та метод “кореляційної залежності”. Доведено спроможність та асимптотичну нормальність отриманих оцінок.

Отримано оцінки параметрів деформації у випадку неповних деформованих спостережень для СМО типу M|M|n|m.

На основі розроблених конструктивних методів створено та програмно реалізовано алгоритми оптимального оцінювання для частково спостережуваних марковських систем.

СПИСОК ПУБЛІКАЦІЙ ЗА ТЕМОЮ ДИСЕРТАЦІЇ.

Война А.А., Жигайло О.А. Оптимальное оценивание некоторых функционалов марковских систем в условиях неполных наблюдений // Кибернетика и системный анализ. - 1998. - №6. - C.88-95.

Война О. А., Жигайло О.О. Статистичне оцінювання для процесів гибелі та народження у випадку неповної статистичної інформації // Вісник Київського Університету. Серія: фізико-математичні науки. - 2000. - Вип. №3. - С.212-219.

Война О. А., Жигайло О.О. Про параметричне оцінювання для марковських систем за частковими деформованими спостереженнями // Доповіді НАН України. Серія: Кібернетика та обчислювальна техніка. - 2001. - №2. - C.70-74.

Жигайло О.О. Про оцінки максимальної правдоподібності параметрів частково спостережуваних марковських систем // Доповіді НАН України. Серія: Кібернетика та обчислювальна техніка. - 2001. - №6 - С. 76-80.

Война О. А., Жигайло О.О. Оцінювання деяких функціоналів частково спостережуваних марковських процесів // Теорія ймовірності та математична статистика. - 1998. - №59. - С. 34-39.

A.Voina, O.Zhigailo. Properties of estimations of parameters of death and birth processes under incomplete observations // The Third Ukrainian-Scandinavian Conference in Probability Theory and Mathematical Statistics. Abstracts. - Kyiv ( Ukraine ). - 1999. - P.159.

У роботах, написаних у співавторстві, науковому керівнику належить постановка та вибір методів розв'язання задач.

Жигайло О.О. Оптимальне оцінювання для марковських систем в умовах неповної статистичної інформації. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 – теоретичні основи інформатики та кібернетики. Київський національний університет імені Тараса Шевченка, Київ, 2002.

Робота присвячена розробці методів статистичного аналізу для задач теорії прихованих марковських моделей. Розв'язано задачі параметричного та непараметричного оцінювання для характеристик частково спостережуваних марковських систем. Розроблено рекурентні алгоритми оптимального оцінювання для моментів попадання марковського процесу у фіксований стан та кількості таких попадань за час спостережень. Для випадку, коли закон розподілу процесу залежить від невідомих параметрів, побудовано ітераційну процедуру знаходження оцінок типу максимальної правдоподібності. Запропоновано нову постановку статистичної задачі оцінювання та різні підходи до її вирішення у випадку, коли спостереження є неповними та деформуються функціями, залежними від невідомих параметрів. Досліджено умови існування та властивості отриманих оцінок. Практичне значення одержаних результатів демонструється на прикладі статистичного аналізу систем масового обслуговування типу M|M|n|m в умовах неповних спостережень.

Ключові слова: марковські процеси, приховані марковські моделі, системи масового обслуговування, параметричне та непараметричне оцінювання.

Zhigailo O.A. Optimal estimation of the Markov systems under incomplete observations. – Manuscript.

Thesis for a candidate's degree of physics and mathematics by speciality 01.05.01–Theoretical Bases of Computer Science and Cybernetics. Kyiv Taras Shevchenko national university, Kyiv, 2002.

The dissertation is devoted to the development of a statistical analysis of hidden Markov models. The tasks of parametric and nonparametric estimation for the characteristics of partially observed Markov systems are solved. The recurrent algorithms of optimal estimation for the moments of hits of a Markov process and a number of such hits during the observations are constructed. The iterative procedure for finding maximum likelihood estimations in the case when the process distribution depends on unknown parameters is obtained. The new task and methods of its solution in case when observations are incomplete and deformed with functions which depend on unknown parameters are proposed. The properties and conditions of existence of the estimation are investigated. The obtained results are applied to the statistical analysis of the queuing systems under incomplete observations.

Key words: Markov processes, hidden Markov models, queuing systems, parametric and nonparametric estimation.

Жигайло О.А. Оптимальное оценивание для марковских систем в условиях неполной статистической информации. – Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 – теоретические основы информатики и кибернетики. Киевский национальный университет им. Тараса Шевченко, Киев, 2002.

Работа посвящена статистическому анализу стохастических систем, которые получили название скрытых марковских моделей. Их функционирование может быть описано двухкомпонентным случайным процессом с дискретным временем. Первая компонента – это однородная цепь Маркова с дискретным множеством состояний, распределение второй компоненты в некоторый момент времени зависит от состояния, в котором в этот момент находится первая. Условия статистического эксперимента таковы, что возможны наблюдения только над второй компонентой процесса. Подобные модели получили широкое распространение при анализе сигналов, автоматическом распознавании речи, в экологии и других прикладных отраслях. При описанной схеме наблюдений остро возникает необходимость в разработке конструктивных методов параметрического и непараметрического оценивания для марковских систем, которые можно эффективно использовать на практике. Аналогичные задачи возникают также при попытке анализа систем массового обслуживания, когда полностью отсутствуют информация о количестве требований в системе. Известны только моменты, когда система меняла свое состояние, то есть моменты, когда требование пришло в систему, или покинуло ее, или было потеряно. К какому именно типу относятся наблюдаемые моменты, неизвестно.

В этой работе предлагается подход к оптимальному оцениванию функционалов типа попадания частично наблюдаемой марковской системы в некоторое множество состояний, который иллюстрируется на примере построения оптимальной оценки момента k-го попадания марковского процесса в заданное состояние. Найдены оценки количества таких попаданий за время наблюдений. Также рассматриваются аналогичные оценки для систем массового обслуживания типа M|M|n|m в условиях, когда наблюдаются только моменты, когда система меняла свое состояние. Получены оценки моментов k-ой потери требования в системе и количества потерь требований в системе массового обслуживания типа M|M|n|m за время наблюдений. Для построения оценок используются уравнения оптимальной нелинейной фильтрации для частично наблюдаемых многомерных марковских процессов. Оптимальность этих оценок доказывается на основе результатов теории правил оптимальной остановки для марковских последовательностей.

Для решения задач оценивания параметров марковской системы в условиях неполной статистической информации предлагается итерационная процедура, которая является аналогом метода максимального правдоподобия. Построен алгоритм поиска оценок интенсивности прихода и интенсивности обработки требований в системе M|M|n|m по неполным наблюдением. Найдены процедуры переоценки для марковских процессов в случае, когда элементы матрицы интенсивностей процесса являются линейными функциями от неизвестных параметров. Разработанные процедуры сходятся к некоторой критической точке функции правдоподобия и гарантируют увеличение ее значений на каждом шаге алгоритма.

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

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

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