Побудова оцінок моментів зміни

Размещено на http://www.allbest.ru/

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

УДК 519.22

Автореферат

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

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

Побудова оцінок моментів зміни

01.01.05 -- теорія ймовірностей та математична статистика

Шуренков Григорій Валентинович

Київ -- 2008

Дисертацією є рукопис алгоритм математичний економічний

Роботу виконано на кафедрі теорії ймовірностей і математичної статистики Київського національного університету імені Тараса Шевченка.

Науковий керівник: доктор фізико-математичних наук, професор, Майборода Ростислав Євгенович, Київський національний університет імені Тараса Шевченка, професор кафедри теорії ймовірностей і математичної статистики механікоматематичного факультетую

Офіційні опоненти: доктор фізико-математичних наук, професор, Булдигін Валерій Володимирович, Національний технічний університет України „КРІ”, Завідувач кафедри математичного аналізу та теорії ймовірностей;

Кандидат фізико-математичних наук Розора Ірина Василівна, Київський національний університет Імені Тараса Шевченка, Асистент кафедри прикладної статистики факультету кібернетики

Захист відбудеться ``21'' квітня 2009 р. о 14:00 годині на засіданні спеціалізованої вченої ради Д 26.001.37 в Київському національному університеті імені Тараса Шевченка (03022, м. Киів-22, пр-т Глушкова, 6, механіко-математичний факультет).

З дисертацією можна ознайомитись в бібліотеці Київського національного університету імені Тараса Шевченка за адресою: м. Київ, вул. Володимирська, 58.

Автореферат розіслано ``18'' березня 2009 р.

Вчений секретар Моклячук М.П. спеціалізованої вченої ради

Загальна характеристика роботи

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

Перші еврістичні процедури пошуку моментів зміни з'явилися в кінці 20-тих років XX століття, теоретичне ж дослідження почалось в 50-тих роках з робіт І. Пейджа та А. Н. Ширяєва В останні роки розвивається теорія непараметричного оцінювання моментів зміни, яка має зв'язки з теорією розпізнавання образів. Непараметричні оцінки розглядалися Б. Є. Бродським та Б. С. Дарховським. Для непараметричних оцінок одним з важливих параметрів є швидкість, тобто кількість операцій, які потрібно виконати при обчислені оцінки в залежності від обсягу вибірки. Більшість непараметричних оцінок потребують багато операцій для їх обчислення. В. В. Моттль та І. Б. Мучнік запропонували застосовувати для деяких класів непараметричних оцінок динамічне програмування, що дозволяє швидко отримати результат. Оцінки, отримані таким чином -- так звані ДП-оцінки, розглядалися в роботах Р. Є. Майбороди та О. В. Сугакової

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

Зв'язок роботи з науковими програмами, планами, темами.

Дисертаційна робота виконана в рамках держбюджетної дослідницької теми № 06БФ038-03 "Аналітичні та стохастичні методи дослідження динамічних систем", що виконується на кафедрі теорії ймовірностей та математичної статистики механіко-математичного факультету Київського Національного університету імені Тараса Шевченка і входить до програми "Побудова та застосування математичних методів дослідження детермінованих та стохастичних еволюційних систем" (номер державної реєстрації 0101U002472).

Мета та задачі дослідження.

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

* отримання оцінок для математичного сподівання довжину інтервалу невизначеності;

* дослідження умов консистентності оцінок багатьох моментів зміни;

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

* дослідження властивостей квантильних оцінок моментів зміни;

* побудова асимптотично оптимальні оцінки багатьох моментів зміни.

Методика дослідження.

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

Наукова новизна одержаних результатів.

У дисертації досліджено адаптивні ДП-оцінки багатьох моментів зміни та вказані умови асимптотичної оптимальності. Основні результати, отримані в дисертації такі:

* отримані оцінки для математичного сподівання розподілу довжини інтервалу невизначеності;

* знайдені умови консистентності оцінок багатьох моментів зміни;

* побудовані адаптивні ДП-оцінки для багатьох моментів зміни, досліджені їх асимптотичні властивості;

* доведена консистеність квантильних оцінок, в тому числі для випадку невідомих розподілів;

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

* знайдено умови, при яких адаптивні ДП-оцінки є асимптотично оптимальними.

Практичне значення одержаних результатів.

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

Особистий внесок здобувача.

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

Апробація результатів.

Результати дисертації доповідались та обговорювались на конференціях і наукових семінарах:

* науковому семінарі кафедри теорії ймовірностей і математичної статистики механіко-математичного факультету Київського національного університету імені Тараса Шевченка;

* науковому семінарі кафедри математичного аналізу та теорії ймовірностей Національного технічного університету України ``КПІ'';

* науковому семінарі відділу математичних методів дослідження операцій Інституту кібернетики НАН України;

* десятій Міжнародній науковій конференції імені академіка М.Кравчука (м. Київ, 2004р.);

* на міжнародній конференції "Сучасні проблеми та нові напрямки в теорії ймовірностей" (19-26 червня 2005 р., м. Чернівці);

* міжнародній конференції "Сучасна стохастика: теорія і застосування" (19-23 червня 2006 р., м. Київ).

Публікації.

За результатами дисертаційної роботи опубліковано п'ять статей [1]-[5] у фахових виданнях, що входять до переліку, затвердженого ВАК України, та три тези доповідей на конференціях [6]-[8].

Структура та обсяг роботи.

Дисертація складається зі вступу, семи розділів, розбитих на підрозділи, висновків та списку використаних джерел. Основний текст складає 131 сторінку, список використаних джерел займає 8 сторінок і включає в себе 75 найменувань.

Основний зміст

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

У першому розділі вміщений огляд літератури теорії оцінювання моментів зміни, наведено допоміжні факти, які використовуються в дисертації.

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

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

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

Послідовності номерів розподілів будемо називати траєкторіями, істиною траєкторією послідовності. Номери розподілів будемо називати станами.

Нехай задано набір функцій



Введемо функціонал . Функціонал задається формулою

де -- невипадкова величина. Як оцінку для розглянемо

Оцінки для моментів зміни будуються за траєкторією . Кількість знайдених точок зміни позначимо . Оцінками моментів зміни будуть . Послідовність оцінок моментів зміни позначимо .

В дисертації знайдені умови консистетності та асимптотичної оптимальності оцінок, що будуються таким способом, у випадку, коли функції залежать від спостережень. В розділі 2 в основному розглядаються властивості оцінок, що побудовані за функціями ? незалежними від спостережень.

Траєкторію можна шукати послідовно методом динамічного програмування. Позначимо - траєкторія, що складається з j елементів, останній її елемент дорівнює , на якій досягається максимум функціонала серед усіх таких траєкторій. повинна співпадати з однією з траєкторій . Назовемо оптимальною траєкторією. Нехай у нашому розпорядженні є лише перші j спостережень. Чи можна по цих спостереженнях визначити деяку частину оптимальної траєкторії, побудованої по всіх даних? Якщо траєкторії мають спільний початок, то це означає, що оптимальна траєкторія теж має такий самий початок, отже є відомою до якогось моменту. У випадку, коли аналіз даних проводиться одночасно з надходженням нових спостережень, і оптимальна траєкторія шукається лише по наявним даним, виникає питання про довжину інтервалу невизначеності, тобто кількості спостережень, для яких не можна визначити оптимальну траєкторію. Ця задача розглянута в параграфах 2.3-2.7.

Позначимо - останній момент, для якого в момент відома оптимальна траєкторія.

Означення 2.3.1 Iнтервалом невизначеності в момент називається інтервал натурального ряду . Довжиною інтервалу невизначеності називається величина . Розглядається величина - перший момент, в який траєкторія до моменту вже відома. Далі ми будемо оцінювати величину .

Для випадку двох розподілів (K = 2) зручно розглядати послідовність величин - перший момент після , в який траєкторії будуть співпадати для (не враховуючи стан траєкторій в момент ).

У параграфі 2.5 розглядається випадок двох розподілів.

Теорема 2.5.1. Нехай K = 2, виконуються умови (A),(B) та (E) тоді

У параграфі 2.6 отримані оцінки для довільного K.

Теорема 2.6.1. Якщо виконуються умови (A), (D) та (E)

У параграфі 2.7 отримані оцінки для випадку, коли математичне сподівання може дорівнювати нескінченності.

Теорема 2.7.1. Нехай виконуються умови (E)-(H) тоді існують такі , що починаючи з деякого

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

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

Означення 2.8.4. Нехай послідовність, така що прямує до 0. Оцінка називається строго консистентною зі швидкістю збіжності , якщо починаючи з деякого випадкового виконується подія

Теорема 2.8.1. Нехай виконуються умови (E)-(H) і виконуються співвідношення (3.6) тоді оцінка є консистентною.

Теорема 2.8.2. Нехай виконуються умови (E)-(H) і

1. виконуються співвідношення (3.6)

2. центровані функції є субгаусовими випадковими величинами.

тоді є строго консистентною.

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

В розділі 3 розглядаються адаптивні оцінки моментів зміни. В параграфі 3.4 доведена загальна теорема про консистентність адаптивних оцінок. Як приклад адаптивних оцінок, розглянуто оцінки, які будуються за вибірковими квантилями. Такі оцінки доцільно використовувати тоді, коли про розподіли відомо дуже мало або взагалі невідомо нічого. В параграфі 3.5 доведено загальну теорему про консистентність ДП-оцінок. В параграфі 3.6 розглянута задача швидкого пошуку моментів зміни при невідомих розподілів. В параграфі 3.7 досліджується асимптотична поведінка медіанної оцінки моментів зміни.

Розглянемо випадок, коли функції ? є випадковими і залежними від спостережень. Позначимо такі функції ?€. Позначимо відповідну оцінку моментів зміни через

Теорема 3.4.1. Нехай -- послідовність класів функцій для яких виконуються умови 1-4

Тоді

1. якщо, коли то є консистентною,

2. якщо починаючи з деякого N, то є строго консистентною.

В параграфі 3.5 загальна теорема про консистентність адаптивних оцінок застосовується для того щоб довести теорему про консистентність квантильних оцінок.

Теорема 3.5.1. Нехай -- замкнені множини, , в околі є неперервною й виконуються такі нерівності

Для послідовності виконуються співвідношення (3.6). Тоді оцінка , побудована за функціями є строго консистентною.

Наведемо деякі наслідки з цієї теореми.

Наслідок 1. Нехай K=2. Медіани розподілів спостережень не співпадають. Позначимо через розподіл з більшою медіаною. є неперервними на проміжку між медіанами. Нехай виконується (3.6). Тоді оцінка , побудована за функціями

є консистентною.

Наслідок 2. Нехай K=2. Квантилі рівня розподілів та не співпадають. Нехай . та неперервні на проміжку . Нехай виконується (3.6). Тоді оцінка , побудована за функціями є консистентною.

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

Теорема 3.6.1. Нехай K=2 і виконується (3.6), неперервні, тоді існує таке , що оцінка побудована за функціями є строго консистентною.

В параграфі 3.7 розглядається важливий частинний випадок квантильної оцінки - медіанна оцінка. Знаходиться асимптотичний розподіл відхилення медіанної оцінки моментів зміни від справжнього значення.

Спочатку задача розглядається для випадку одного моменту зміни.

Теорема 3.7.1. Нехай розподіли та неперервні на проміжку . Тоді для , визначеного (3.9),

де , . Точка є медіаною розподілу .

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

Теорема 3.7.2. Нехай та неперервні на проміжку

тоді

В розділі 4 розглядається побудова асимптотично оптимальних адаптивних оцінок. Використовується таке означення асимптотичної оптимальності.

Означення 4.1.3. Оцінка є асимптотично оптимальною за вірогідністю, якщо для будь-якої іншої оцінки

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

У пункті 4.3 показано, що асимптотичні розподіли оцінок (4.1) та (4.2) співпадають за деяких умов.

Спочатку задача розглядається за умови, що момент зміни лише один. Отже, в послідовності присутні лише два розподіли.

Теорема 4.3.1. Нехай виконуються умови 1-4, тоді розподіли оцінок (4.1) та (4.2) співпадають.

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

Теорема 4.4.1. Нехай виконані умови 1-4, тоді є консистентною за ймовірністю оцінкою .

Теорема 4.4.2. Нехай виконуються умови 1-4, тоді розподіли оцінок (4.1) та (4.2) співпадають.

Загальні висновки

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

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

Список літератури

1. Шуренков Г. В. Асимптотика медіанних оцінок для багатьох моментів зміни / Г. В. Шуренков // Теорія ймовірностей і математична статистика. --- 2004. --- . 70. --- . 96--104.

2. Шуренков Г. В. Асимптотично оптимальні оцінки моментів зміни / Г. В. Шуренков // Укр. мат. журн. --- 2006. --- . 58. --- . 406--416.

3. Шуренков Г. В. Довжина інтервалу невизначеності при використанні алгоритму динамічного програмування для оцінки моментів зміни / Г. В. Шуренков // Вісник Київського Університету, серія: математика, механіка. --- 2007. --- . 4. --- . 65--68.

4. Shurenkov G. V. The length of the interval of indeterminacy for the estimate of multiple change-points / G. V. Shurenkov // Theory of Stochastic Processes. --- 2007. --- Vol. 29. --- P. 251--266.

5. Шуренков Г. В. Оцінки багатьох моментів зміни при невідомих розподілах / Г. В. Шуренков // Прикл. статист. Актуарна та фін. Математика. --- 2007. --- . 1. --- . 125--132.

6. Шуренков Г. В. Асимптотично оптимальні оцінки багатьох моментів зміни / Г. В. Шуренков // X Міжнародна Наукова Конференція імені академіка М. Кравчука. Матеріали конференції "--- Київ, 2004. "--- . 647.

7. Shurenkov G. V. Asymptotically optimal estimators for moments of change / S. V. Posashkov // International conference ``Modern problems and New Trends in Probability Theory''. Abstracts II. "--- Chernivtsi, Ukraine: Інститут математики НАН України, 2006. "--- P. 133--134.

8. Shurenkov G. V. Length of interval of indeterminacy in change-points problem / G. V. Shurenkov // International conference ``Modern Stochastics: Theory and Applications''. Conference materials. "--- Kyiv, Ukraine: ВПЦ ``Київський університет'', 2006. "--- P. 239.

Анотація

Шуренков Г.В. Побудова оцінок моментів зміни -- Рукопис. Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.01.05 - теорія ймовірностей і математична статистика. Київський національний університет імені Тараса Шевченка, Київ, 2008.

Дисертаційна робота присвячена побудові алгоритмів швидкого пошуку багатьох моментів зміни та дослідженню їх асимптотичної оптимальності. В дисертації розглядаються непараметричні апостеріорні оцінки багатьох моментів зміни. Основну увагу приділено адаптивному випадку, коли оцінки будуються на основі результатів попереднього оцінювання. Оцінки, що розглядаються, називаються ДП-оцінками, оскільки їх можна обчислити за допомогою динамічного програмування. Отримані оцінки для математичного сподівання розподілу довжини інтервалу невизначеності. Знайдені умови консистентності оцінок багатьох моментів зміни. Побудовані адаптивні ДП-оцінки для багатьох моментів зміни. Доведена консистеність квантильних оцінок, в тому числі для випадку невідомих розподілів. Знайдено явний вигляд асимптотичного розподілу медіанної оцінки моментів зміни. Знайдено умови, при яких адаптивні ДП-оцінки є асимптотично оптимальними.

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

Аннотация

Шуренков Г.В. Построение оценок моментов разладки. -- Рукопись. Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.01.05 - теория вероятностей и математическая статистика. Киевский национальный университет имени Тараса Шевченко, Киев, 2008.

Диссертационная работа посвящена построению алгоритмов быстрого поиска многих моментов разладки и исследованию их асимптотических свойств. В диссертации рассматриваются непараметрические оценки многих моментов разладки. Основное внимание уделено адаптивному случаю, когда оценки строятся на основании результатов предварительного оценивания. Для непараметрических оценок одним з важных параметров является скорость, то есть количество операций, необходимых для вычисления оценки в зависимости от объема выборки. В диссертации изучаются ДП-оценки -- оценки, которые можно вычислить с помощью динамического программирования. Для таких оценок количество операций линейно зависит от объема выборки.

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

Найдены условия состоятельности оценок многих моментов разладки. Построены адаптивные ДП-оценки для многих моментов разладки, исследованы их асимптотические свойства. Доказана состоятельность квантильных оценок, в том числе для случая неизвестных распределений. Найдено явный вид асимптотического распределения медианной оценки моментов разладки. Найдены условия, при которых адаптивные ДП-оценки являются асимптотически оптимальными.

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

Annotation

Shurenkov G.V. The construction of estimators of change-points. -- Manuscript. The thesis is for obtaining the Candidate of Physical and Mathematical Sciences degree on the specialty 01.01.05 - Probability Theory and Mathematical Statistics. Kyiv National Taras Shevchenko University, 2008.

The thesis is devoted to the construction of algorithms of fast search for several change-points and the study of their asymptotic properties. Nonparametric estimators of several change-points are considered in the thesis. The main attention is given to an adaptive case when estimators are constructed from the results of previous estimations. Considered estimators are called DP-estimators as they can be computed by means of dynamic programming. Estimations for mathematical expectation of the length of interval inconsistency are found. Adaptive DP-estimators for several change-points are constructed and their asymptotic properties are studied. Consistency of quantile estimators is proven, also in the case of unknown distributions. Explicit form of the distribution of median estimator of change-points is determined. The conditions under which adaptive DP-estimators are asymptotically optimal are found.

Key words: change-points, adaptive estimation, asymptotic optimality, dynamic programming

Размещено на Allbest.ru

...