автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:О минимаксной и обобщенной байесовской задачах скорейшего обнаружения разладки для пуассоновского процесса

На правах рукописи

003452812

БУРНАЕВ ЕВГЕНИЙ ВЛАДИМИРОВИЧ

г

О МИНИМАКСНОЙ И ОБОБЩЕННОЙ БАЙЕСОВСКОЙ ЗАДАЧАХ СКОРЕЙШЕГО ОБНАРУЖЕНИЯ РАЗЛАДКИ ДЛЯ ПУАССОНОВСКОГО ПРОЦЕССА

Специальность: 05.13.17 - теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА 2008

003452812

Работа выполнена в Московском физико-техническом институте (государственном университете)

Научный руководитель:

доктор физико-математических наук, профессор А.Н. Ширяев Официальные оппоненты:

доктор физико-математических наук, профессор В.В. Мазалов доктор физико-математических наук, ст. науч. сотр. B.C. Дарховский Ведущая организация:

Центральный экономико-математический институт Российской академии наук

Защита состоится 11_" _ 2008 г. в 11 часов на

заседании диссертационного совета Д.002.077.01 в Институте проблем передачи информации им. A.A. Харкевича РАН по адресу: 101447, Москва, ГСП-4, Б. Каретный пер., 19, стр. 1.

С диссертацией можно ознакомиться в библиотеке Института проблем передачи информации им. A.A. Харкевича РАН.

Автореферат разослан " 31 " октября 2008 г.

Ученый секретарь диссертационного совета,

Общая характеристика работы

Актуальность проблемы. За последние двадцать лет существенно возросла потребность в решении ряда практических задач1, таких как автоматическое обнаружение неисправностей (разладок, сбоев, и т.п.), обслуживание оборудования на основе автоматического контроля его состояния, обеспечение безопасности сложных технических и информационных систем (самолетов, судов, ракет, ядерных электростанций, различных интернет-сервисов, и т.д.), автоматический контроль качества выпускаемой продукции, предсказание естественных катастрофических явлений (землятресения, цунами, и т.д.), мониторинг в биомедицине и финансовой сфере.

Эти задачи возникают по причине2: возрастания влияния антропогенного воздействия из-за высокоразвитой промышленной индустрии; роста масштабов и сложности эргатиче-ских3 систем; стремления человека эффективно использовать ограниченные природные ресурсы, энергию, сырье и производственное оборудование при минимальных затратах социального времени; необходимости раннего предсказания естественных катастрофических явлений.

Основная черта вышеперечисленных задач состоит в том, что по сути все они сводятся к выявлению момента резкого изменения {разладки) некоторых характеристик рассматриваемого объекта на основе статистических данных о других характеристиках этого объекта.

С развитием информатики появилась возможность построения автоматизированных информационных систем для ста-

JF Gustafison. Adaptive filtering and change detection. - New York: Wiley, 2000.

2Г.А. Сырецкий. Информатика. Фундаментальный курс. Том I. Основы информационной и вычислительной техники. - СПб.: БХВ-Петербург, 2005.

3Система, в которой во взаимосвязи находятся '^трирода+техника-(-человек".

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

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

Теоретические методы обнаружения разладки для диффузионных процессов были получены Ширяевым А.Н., Moustaki-des G.V., Pollak М., Siegmund D., Новиковым A.A., Файнбер-гом Е.А. и др. Позже эти методы были применены Тартаков-ским А.Г., Розовским Б.Л. и др. для построения систем обеспечения безопасности сетей; Basseville М., Benveniste А., Никифоров И.В. и др. использовали их для разработки эффективных алгоритмов обнаружения неисправностей в сложных технических устройствах и т.п.

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

описывается с помощью пуассоновской модели. Именно поэтому для практических приложений актуальна задача о разладке для пуассоновского процесса.

До сих пор были разработаны методы скорейшего обнаружения момента изменения интенсивности пуассоновского потока событий, являющиеся оптимальными только в "среднем", поскольку при построении этих методов было сделано предположение, что момент разладки является случайной величиной с заранее заданным распределением4,5 (байесовская постановка задачи о разладке). В то же время в приложениях зачастую требуется использовать метод обнаружения разладки, являющийся оптимальным для случая, когда момент разладки представляет собой детерминированный неизвестный параметр, однако теоретические методы построения эффективных процедур обнаружения разладки в этом важном для практики случае отсутствовали.

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

В соответствии с поставленной целью были определены следующие задачи исследования:

1. Свести задачу скорейшего обнаружения момента изменения интенсивности потока событий в пуассоновской мо-

4Peskir G., Shiryaev A.N. Solving the Poissoa disorder problem // Advances in Finance and Stochastics. Essays in Honour of Dieter Sondermann / Ed. by Sandmann К., Schonbucher P - Berlin: Springer, 2002. - P. 295-312.

5Dayanik S , Sezer S.O. Compound Poisson disorder problem // Mathematics of Operations Research. - 2005. - V. 31, N. 4. - P. 649-672.

дели потока к математической задаче оптимальной остановки некоторого модельного процесса.

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

3. Вычислить среднее время запаздывания в обнаружении разладки при использовании полученных методов.

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

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

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

• могут применяться при построении компонент автоматизированных информационных систем, используемых для выявления разладок;

• приближенно описывают, какие "эффекты" следует ожидать на практике при применении полученных методов скорейшего обнаружения момента смены интенсивности пуассоновского потока событий;

• позволяют отработать подходы к решению задачи скорейшего обнаружения для более общих, по сравнению с изменением интенсивности пуассоновского потока событий, моделей разладки (в которых под разладкой понимается, например, одновременное изменение нескольких характеристик наблюдаемого процесса).

Научные результаты, выносимые на защиту:

1. Метод сведения задачи скорейшего обнаружения момента изменения интенсивности потока событий в пуассонов-ской модели потока к математической задаче оптимальной остановки модельного процесса специального вида (т.н. кусочно-детерминистический процесс Ширяева, являющийся достаточной статистикой).

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

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

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

5. Асимптотики среднего времени запаздывания в обнаружении разладки.

Апробация работы. Результаты работы докладывались и обсуждались на следующих российских и международных конференциях:

1. Научная конференция "Информационные технологии и системы" (ИТиС-2008), 29 сентября - 3 октября 2008 г., Геленджик, Россия.

2. Advanced Research Workshop on Financial Mathematics: Methods and Applications, 16-20 September 2008, University of Gdansk, Poland.

3. Russian-Japan Workshop "Complex Stochastic Models: Asymptotics and Applications", 4-5 June 2007, St.eklov Mathematical Institute, Moscow, Russia.

4. 15th European Young Statisticians Meeting, 10-14 September 2007, Castro Urdiales, Spain.

5. II всероссийская научная конференция с молодежной научной школой "Математическое моделирование развивающейся экономики" (ЭКОМОД-2007), 9-15 июля 2007 г., ВятГУ, Киров, Россия.

6. 50-я научная конференция Московского физико-технического института, 23-27 ноября 2007 г., Долгопрудный, Россия.

Основные результаты диссертации обсуждались на научном семинаре "Случайные процессы и стохастический анализ" кафедры теории вероятностей механико-математического факультета МГУ под руководством А.Н. Ширяева (2006-2008 гг.), научном семинаре Добрушинской лаборатории ИППИ РАН (2008 г.), научном семинаре кафедры высшей математики МФТИ (2008 г.), научном семинаре лаборатории теории передачи информации и управления ИППИ РАН (2008 г.), научном семинаре ВЦ РАН по руководством И.С. Меньшикова (2008 г.).

Полученные результаты использовались в работах, проводимых в рамках программы "Развитие научного потенциала высшей школы" (код проекта РНП.2.2.1.1.2467, тема 717).

Публикации. По теме диссертации опубликовано 6 печатных работ, из них 2 работы - статьи в ведущих рецензируемых научных журналах, 4 работы в трудах ведущих российских и международных конференций. Все работы написаны без соавторов. Наиболее важные результаты опубликованы в работах [1], [2] и [3].

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы, включающего 137 наименований. Работа изложена на 127 страницах и содержит 3 рисунка.

Содержание работы

Во введении обоснована актуальность задачи скорейшего обнаружения, проведен обзор известных результатов, связанных с темой диссертации, сформулирована цель и определены задачи исследования, а также приведено краткое содержание диссертации. Теоретические задачи, которые необходимо решить для достижения поставленной цели, были сформулиро-

ваны в виде задачи скорейшего обнаружения (в обобщенной байесовской и минимаксной постановках) момента изменения интенсивности пуассоновского потока событий.

Первая глава посвящена изложению постановок задачи скорейшего обнаружения и получению представления для модельного процесса специального вида (т.н. кусочно-детерминистический процесс Ширяева (^()4>о> являющийся достаточной статистикой), к оптимальной остановке которого сводится задача скорейшего обнаружения момента изменения интенсивности пуассоновского потока событий.

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

Предполагается, что в рассматриваемой модели разладки наблюдаемый стохастический процесс X = (^)(>о имеет вид

Г I < в,

' I ^ +

сХ0 = 0, где в 6 [0, оо] - неизвестный момент разладки, = «°)(>0 и NXl = - независимые пуассоновские про-

цессы с интенсивнос.тями Ао и А1 соответственно, определенные на фильтрованном вероятностном пространстве (П, Т, {Тг\>0, Р), при этом параметры Ао > 0 и А1 > 0 (Ао ф Ах) считаются известными.

Значения реализации процесса (Хг)4>0 поступают последовательно, текущим образом и задача заключается в том, чтобы на основании поступающих данных построить такой конечный момент остановки т = г (ш) (выбором т определяется правило подачи сигнала тревоги) относительно фильтрации = (•7г*)г>о, порожденной процессом (Х()1>0 (то есть Т* —

a {Xs, 0 < s < £}), который в определенном смысле "наиболее близок" к моменту разладки в.

Пусть Ps = Law(X|s) обозначает распределение процесса (Хг)(>0 при условии, что разладка происходит в детерминированный момент времени в = s > 0. В частности, через Роо обозначим распределение (Xt)t>0 при условии, что разладка никогда не произойдет, то есть Р«, = Law(iVtA°,i > 0). Обозначим также через Es математическое ожидание по мере Ра.

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

Вариант (Л). Допустим, что в - случайная величина (в = в(и>)), независящая от процесса (Xt)t>a и имеющая экспоненциальное распределение с атомом в нуле, то есть

Р((9 = 0) = тг и Р (0 > t\9 > 0) = e-Ai,

где 7Г 6 [0,1) и А > 0 - известные константы.

Обозначим через

Ща) = {г < со : Р (г < в) < а}

при фиксированном значении а 6 (0,1) множество конечных моментов остановки, для которых вероятность ложной тревоги Р (г < в) не превосходит а.

Вариант (Л) задачи скорейшего обнаружения состоит в том, чтобы найти для заданного а € (0,1) такой оптимальный момент остановки Т(*а) £ 9Я(а)> если он существует, что

inf Е (г - в\т > в) = Е (r(*Q) - 0jr(*a) > в) .

Вариант (В). В данном случае 9 G [0, оо] - детерминированный неизвестный параметр.

Для каждого Т > 0 обозначим через

ЗЛг = {т : Егот = Т}

множество моментов остановки, среднее время до ложной тревоги Еост которых равно фиксированному значению Т.

Вариант (В) задачи о разладке состоит в том, чтобы для заданного Т > 0 найти такой оптимальный момент остановки Ту, если он существует, что

1 рсо \ Г°°

inf-/ Ee(T-6)+d9 = - Ee(r±-9)+d9. rmT 1 Jo 1 Jo

Такая постановка задачи называется обобщенной байесовской, поскольку параметр в можно интерпретировать как обобщенную случайную величину с "равномерным" распределением на [О, оо).

Естественно также рассматривать более широкий класс моментов остановки

т>т = {т:Т< ЕооТ < оо} э ЭЛГ

и найти такой момент остановки г>г 6 9Л>т, если он существует, что

1 Г°° 1 Г30

inf-/ Ее(т-в)+с1в=- Е e(rZT-e)+d9.

теэл >т 1 Jo 1 Jo

Вариант (С). В данном случае в € [0, оо] - детерминированный неизвестный параметр.

Вариант (С) задачи о разладке состоит в том, чтобы для заданного Т > 0 найти такой момент остановки 6 971т, если он существует, что

inf supE0 (т - в\т >в)= supEe - в\а*т > в).

геОТт0> о б>о

Естественно также найти такой момент остановки а*>г 6 ЗЛ>г, если он существует, что

inf supEfl (г - в\т > 0) = supE# (а*>т - в\а*>т > в) те<т>те> о в>о

Рассмотрим вариант (А) задачи скорейшего обнаружения. Пусть

Щ = Р {в < t\F?) , t > О

обозначает апостериорную вероятность того, что разладка появляется до момента времени £. В частности, щ = ж. Известно6, что момент остановки

Т(*а) = inf {i > 0 : 7г4 > 1 — а}

является оптимальным решением в классе ЯЛ(а) варианта (Л) задачи скорейшего обнаружения для пуассоновского процесса.

Во втором разделе показано, как получить уравнение для процесса апостериорной вероятности (?г«)*>о из уравнения для процесса отношения правдоподобия {y>t)t>o с

ЧН = т^-, t > 0. 1 -щ

Далее, специальным предельным переходом из процесса (vt)i>0 получен кусочно-детерминистический процесс Ширяева (^¡)«>о удовлетворяющий уравнению

drl>t = dt+(^-ljd{Xt-Xot),rpo = 0 (1)

и имеющий представление

V>t = / у-du, J о

6Shiryaev A N., Peshkir G. Optimal stopping and free-boundary problems. -Birkhauser, 2006

где отношение правдоподобия

(ь* -*>)«)

Доказывается, что процесс (ч/^х) является марковским.

Вторая глава посвящена решению варианта (В) задачи скорейшего обнаружения для пуассоновского процесса.

В первом разделе доказывается, что вариант (В) задачи скорейшего обнаружения может быть сведен к условно-экстремальной задаче оптимальной остановки кусочно-детерминистического процесса

Теорема 1. Значение

функции риска обобщенной байесовской задачи о разладке равно значению функции цены условно-экстремальной задачи оптимальной остановки процесса {"фг)г>0.'

Таким образом, процесс (фг)^ играет роль своего рода достаточной статистики в варианте (В) задачи о разладке.

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

В третьем разделе решается задача вычисления среднего значения некоторых интегральных функционалов от кусочно-детерминистического процесса {фг)(>о, то есть функций вида

(2)

(3)

где E^i' - математическое ожидание по мере Р^', относительно которой процесс (i/>t)i>0 удовлетворяет уравнению (1) с начальным условием тра = х, у > 0 - произвольная фиксированная величина, F(x) - положительная, непрерывно дифференцируемая, ограниченная на [0, у] функция, а ту = inf {i > 0 : V't > у}, и разрабатывается метод для подсчета асимптотик этих функционалов.

В четвертом, разделе разрабатывается метод для вычисления математического ожидания Е^ тд момента выхода на заданную границу у = А > 0 кусочно-детерминистического процесса (^()«>о-

В пятом разделе решается задача подбора такого значения границы у = А, среднее значение момента выхода тд = inf {i > 0 : ^ > Л} на которую кусочно-детерминистического процесса {ipt)t>о равняется заданной величине Т. Доказана

Теорема 2. При Ai < А0 и любых Т > 0 для А = А(Т) = Т момент остановки G Wlj-, При Aj > Ао и любых Т > О найдется решение А = А(Т) уравнения ЕооТл = Т, удовлетворяющее неравенствам j>-T < А(Т) < Т, для которого та G тТ.

В шестом разделе решается условно-экстремальная задача оптимальной остановки кусочно-детерминистического процесса (A)t>o

inf Ето I ipedd теотг J о

и доказывается, что момент первого выхода этого процесса на специальным образом подобранную границу является оптимальным решением варианта (В) задачи скорейшего обнаружения, то есть верна

Теорема 4. При любых Ai > 0, Ад > 0 и Т > 0 момент остановки

где процесс {ipt)t>о удовлетворяет уравнению (1), а А = А(Т) является решением уравнения E^та = Т, будет оптимальным решением варианта (В) задачи скорейшего обнаружения для пуассоновского процесса в классах моментов остановок Tlx и ЯЯ>х-

В седьмом разделе подсчитываются среднее время запаздывания В(Т) при обнаружении разладки в варианте (В) задачи скорейшего обнаружения и асимптотики этого среднего времени. Доказаны следующие теоремы.

Теорема 5. Пусть Ai —> оо и Ао —> оо так, что выполняется соотношение Ai = Ао + \Ао ■ Л с произвольным фиксированным значением Л € К. Тогда для функции риска В(Т) имеет место следующее разложение по степеням малого парамет-

Гт = тА(Т) = {t > 0 : Фг > А(Т)},

В(Т) = Во(Т) + еВ1(Т) + ...,

где

В0(Т)

Ulog(pT)-(C + l)+o(^)] при Т ► ос i[f+ 0((РГ)2)] при Т —> О,

-5v/|k(pT)-(C + l) v

оо,

+ <>№*)] приТ^Ъ

в случае Ai < Ао и

LBl{T) < Bi(T) < RBl(T),

LBl{T) =

-iyf[21og(pT)-(2C-|)

)

+o( Цр

при T —+ oo,

-^{рТ + ОЦрТ)2)], ' при Т —► О, iy|[41og(pT)-(4C+f)

прчТ^оо,

[рТ + 0((рТ)>)},

в случае Ai > Aq.

RbAT) =

при T —> О

Теорема 6. Для произвольных Ао > 0, Aj > 0 и

1

С{ Ао.АО =

A1log|j-(A1-Ao)

при Т —» оо

В(Г) = С (Ао, Ai) В (Т) 4- С> (1),

1,

ВД = уЕ00 (Vr^log^J,

процесс {^t)t> о удовлетворяет уравнению (1), ТА(Т) = {i > 0: > у1(Т)}, а А = Л(Г) - решение уравнения ЕдаТд = Т. При этом В(Т) = log Т в случае < Xq и В{Т) 6 logТ, % log Т] в случае Ах > А0.

Третья глава посвящена получению асимптотически оптимального решения варианта (С) задачи скорейшего обнаружения для пуассоновского процесса.

В первом разделе определяются оценки сверху и снизу среднего времени запаздывания при обнаружении разладки в варианте (С) задачи скорейшего обнаружения, а именно, доказывается, что для минимаксных рисков

С(Т)= тГ 8ирЕв(т-0|т>0) (4)

т€ОТГ0>о

и

С>(Т)= т£ зирЕй (т — в\т > 9). (5)

тешг>Т е>о

выполняется следующая

Теорема 7. Для произвольного Т > О и момента остановки Ту = М {£ > 0 : фь > А(Т)}, где процесс (^«)(>0 удовлетворяет уравнению (1), а А = А(Т) является решением уравнения ЕооТа = Т, выполнено, что

В(Т) < С>(Т) < С(Т) < С*{Т), (6)

где С*(Т) = Кот}, а В(Т) определено в (2), (3) (см. также теоремы 5 и 6).

Во втором разделе решается задача вычисления функции У/(х\ А) = Ец^тд, где Ец1' - математическое ожидание по мере Рр1', относительно которой процесс (Ф^г>0 удовлетворяет уравнению (1) с начальным условием фо = х, А > 0 - произвольная фиксированная величина, и разрабатывается метод для подсчета асимптотик этой функции.

В третьем разделе подсчитываются асимптотики оценки сверху С* (Г) = ЕоТу среднего времени запаздывания и доказывается, что момент первого выхода кусочно-детерминисти-

ческого процесса (т/><)(>0 на специальным образом подобранную границу является асимптотически оптимальным решением варианта (С) задачи скорейшего обнаружения. Доказана

Теорема 8. Для оценки сверху С*(Т) минимаксных рисков (4) и (5) при А1 —» оо и Ао —+ оо, удовлетворяющих соотношению Ах = Ао + \/Ао • Л с произвольным фиксированным значением Л € К, имеет место следующее разложение по степеням малого параметра е = -4=- | О

С*{Т) = Сд(Т) + еС1(Т) + .

• >

где

(рТ)-С + 0{^)\ при Т —> оо, + 0({рТ)2)} при Т —+ О,

з

^[^(^-(С + З)

сцт) =

+0 при Т ^ оо,

1

з

^/|[2(рГ)2 + 0((рГ)4)] приТ-> О

в случае Ах < Ао и

Ьс-(Т) < СЦТ) < Пс;(Т)

[рТ + 0((рТ)2)], т —*о,

гг-

оо; О

Лс-(Г) = +0 (ь^Г)

е случае Л1 > Ао.

Из теорем 5, 8 и формулы (6) получаем

Следствие. Пусть А1 —» оо и Ао —<> оо так, что выполняется соотношению А1 = Ао + \/Ао - Л с произвольным фиксированным значением Л 6 К, тогда момент остановки

Ту = > 0 : > Л(Т)},

где процесс (^)г>0 удовлетворяет уравнению (1), а порог А = Л (Г) является решением уравнения Ж^та = Г, будет асимптотически при Т оо оптимальным решением варианта (С) задачи скорейшего обнаружения для пуассоновского процесса в классах моментов остановок Шт и 9Я>т-

В заключении сформулированы основные результаты диссертационной работы:

1. Метод сведения задачи скорейшего обнаружения момента изменения интенсивности потока событий в пуассонов-ской модели потока к математической задаче оптимальной остановки модельного процесса специального вида (т.н. кусочно-детерминистический процесс Ширяева, являющийся достаточной статистикой).

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

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

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

5. Асимптотики среднего времени запаздывания в обнаружении разладки.

Публикации автора по теме диссертации

1. Бурнаев Е.В. О задаче обнаружения разладки для пуассо-новского процесса в обобщенной байесовской постановке // Теория вероятностей и ее применения. - 2008. - Т. 53, вып. 3. - С. 534-556.

2. Бурнаев Е.В. Задача о разладке для пуассоновского процесса в обобщенной байесовской постановке // Успехи математических наук. - 2007. - Т. 62, вып. 4. - С. 151-152.

3. Бурнаев Е.В. О минимаксной асимптотической оптимальности первого порядка в задаче наискорейшего обнаружения изменения интенсивности пуассоновского процесса // Информационные технологии и системы (ИТиС'08): сборник трудов конференции. - М.: ИППИ РАН, 2008. - С. 403-405.

4. Бурнаев Е.В. Об обобщенной байесовской постановке задачи о разладке для пуассоновского процесса // Сборник научных трудов II всероссийской научной конференции "Математическое моделирование развивающейся экономики" (ЭКОМОД-2007). - Киров: ВятГУ, 2007. - С. 6469.

5. Burnaev E.V. Quickest detection of intensity change for Poisson process in generalized Bayesian setting // Proceedings of the 15th European Young Statisticians Meeting (EYSM-2007). - 2007. - P. 1-5.

6. Бурнаев Е.В. О задаче обнаружения разладки для пуассоновского процесса в обобщенной байесовской постановке // Труды 50-й научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук". -Москва-Долгопрудный: ФУПМ, 2007. - С. 11-14.

Сдано в печать 31 октября 2008года Объем печати 1,375п.л. Эаказ№4237/8. Тираж 100 экз. Отпечатано в типографии ООО НВП «ИНЭК» г.Москва, Ленинградское шоссе, д.18

Введение

1. Постановка задачи

1.1. Формализация задачи скорейшего обнаружения разладки.

1.1.1. Вариант (Л).

1.1.2. Вариант (В).

1.1.3. Вариант (С).

1.2. Достаточные статистики в задаче скорейшего обнаружения разладки.

1.2.1. Вариант (А).

1.2.2. Вариант (В).

1.2.3. Вариант (С).

2. Задача скорейшего обнаружения разладки для пуассоновского процесса в обобщенной байесовской постановке (вариант (В))

2.1. Сведение варианта (В) задачи скорейшего обнаружения разладки к условно-экстремальной задаче оптимальной остановки модельного процесса (4>t)t>o

2.2. Поведение выборочных траекторий модельного процесса (ф/)г>о.

2.3. О решении дифференциально-разностного уравнения для вычисления функции G{x]y)=^^F(^a-)ds.

2.3.1. Случай Ai < Л0.

2.3.2. Случай Лх > Л0.

2.3.3. Асимптотики функции G(x; у).

2.4. Вычисление Ж^т^

2.4.1. Случай Ai < Л0.

2.4.2. Случай Ai > Л0.

2.5. Нахождение порогового значения А = А(Т)

2.6. Задача условной оптимизации

2.6.1. Постановка задачи со свободными концами

2.6.2. Решение задачи со свободными концами

2.6.3. Некоторые особенности решения задачи со свободными концами.

2.6.4. Решение задачи условной оптимизации

2.7. Асимптотики обобщенной байесовской функции риска В(Т).

2.7.1. Асимптотики функции U{x\ А).

2.7.2. Случай Ai < А0.

2.7.3. Случай Ах > А0.

2.7.4. Основной результат.

3. Задача скорейшего обнаружения разладки для пуассоновского процесса в минимаксной постановке (вариант (С))

3.1. Оценка минимаксного риска

3.2. Вычисление оценки сверху С*(Т).

3.2.1. О решении дифференциально-разностного уравнения для вычисления функции

W(x-, А) = Ео^тд.

3.2.2. Асимптотики функции W{x\ А).

3.3. Асимптотики оценки сверху С*(Т).

3.3.1. Асимптотики функции W{х\ А).

3.3.2. Случай Ai < Л0.

3.3.3. Случай Ах > Л0.

3.3.4. Основной результат.

За последние двадцать лет существенно возросла потребность в решении ряда практических задач:

• Статистический контроль качества

Первые схемы статистического контроля за ходом производственного процесса были предложены В.А. Шьюар-том в 1920-30 гг. (W.A. Shewart) [122, 123] и получили название "контрольных карт". Цель статистического контроля состоит в том, чтобы в режиме реального времени выявлять изменения параметров моделей, используемых для описания сложного технологического процесса [49,76,136]. При обнаружении изменений подается сигнал тревоги, после которого может быть осуществлена остановка технологического процесса, его настройка и перезапуск.

Работы В.А. Шьюарта послужили толчком к систематическому изучению и построению новых (в том числе оптимальных) методов статистического контроля в режиме реального времени [3,13,14,18,19,24,25,38-43,74,102, 108,109,115,116,121,127].

• Обнаружение сигналов в информационных системах

Классической задачей теории информационных систем (сюда относятся системы связи, управления, массового обслуживания, локационные системы и т.п.) является задача обнаружения сигнала (или последовательности случайных сигналов) с неизвестным временем прихода на фоне случайных помех [17,36,37]. Ситуации, когда время прихода сигнала априори неизвестно, часто возникают в системах связи (прием стартстопных комбинаций, появляющихся в произвольные моменты времени), в радиолокации (обнаружение импульсов, отраженных от объекта с неизвестным местонахождением), в системах телесигнализации и телеуправления (спорадическая передача управляющих сигналов в виде одиночных импульсов или кодовых групп) и т.п. Использование оптимальных (или близких к ним) методов приема сигналов является эффективным средством (в ряде случаев единственным) повышения достоверности, необходимой предпосылкой для применения помехоустойчивого кодирования [17, 32,36,37], а также позволяет существенно увеличить пропускную способность информационных систем, что является важным аспектом для эффективного использования вычислительных средств в современных информационных комплексах [32,33].

• Обнаружение неисправностей в сложных технических устройствах

В [1,26,49,74,137] были построены эффективные алгоритмы обнаружения неисправностей в сложных технических устройствах [1,26,49,74,137].

В [49,105] и [99] описаны соответственно методы определения в режиме реального времени дефектных сенсоров в навигационной системе и в системе, контролирующей транспортное средство.

В [134] описан метод определения момента разладки системы слежения за движущимися объектами (также этот метод был применен для сегментации видеоряда).

В [23] предложен подход для диагностики биения валков стана холодной прокатки, которая необходима для поддержания показателей качества листового проката на заданном уровне.

Обработка геологичесих и сейсмологических данных

Методы, разработанные в [1,23,26,49,74], позволяют: решать задачу оценивания момента вступления сейсмических волн; проводить автоматическое расчленение геологического разреза по данным сейсморазведки, необходимое для построения геологической модели, которая облегчает обнаружение формаций, характерных для скоплений нефти и газа.

Обработка эконометрических данных

В [4,46,60,74,85,86,89,124] предложены различные методы, позволяющие выявлять тренды в финансовых временных рядах и строить на их основе эффективные торговые стратегии, определять максимумы и минимумы в циклических макроэкономических временных рядах и т.п.

Обеспечение безопасности систем и сетей

В [84,90,131,133,135] разработаны подходы, позволяющие в режиме реального времени выявлять различные типы компьютерных интервенций [66], например, ха-керские атаки распределенных компьютерных систем, направленные на нарушение нормального обслуживания пользователей (так называемые DDoS-атаки).

• Раннее обнаружение случаев биотерроризма и эпидемий

В [106] предложен метод, позволяющий выявлять распространение химического загрязнения окружающей среды.

В [69,93] описываются системы для обнаружения случаев биотерроризма.

В [71,78,91,103,104,107,120,128] рассматриваются методы, с помощью которых на основе данных о коэффициенте заболеваемости можно определить начало эпидемии на ранней стадии.

• Анализ биомедицинских данных

В [1,23,47,49,55-57,74,80,120] предложены методы анализа биомедицинских сигналов, таких, как электроэнцефалограмма, электрокардиограмма, стабилограмма, ДНК последовательность и др. Эти методы позволяют классифицировать сердечные ритмы и обнаруживать аритмии, исследовать процесс длительного поддержания позы человека, сегментировать речевой сигнал человека для последующего распознавания и т.п.

В [96-98] предложены способы автоматического выявления заболевших животных (на сельскохозяйственном предприятии) на основе данных о суточном потреблении воды.

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

В [70, 77] предложен метод для выявления момента времени, когда происходит значимое увеличение числа случаев возникновения побочных эффектов от использования нового лекарства после того, как это лекарство прошло основные проверки и поступило в свободную продажу.

Эти задачи возникают по причине [31]: возрастания влияния антропогенного воздействия из-за высокоразвитой промышленной индустрии; роста масштабов и сложности эргати-ческих1 систем; стремления человека эффективно использовать ограниченные природные ресурсы, энергию, сырье и производственное оборудование при минимальных затратах социального времени; необходимости раннего предсказания естественных катастрофических явлений.

Основная черта вышеперечисленные задач состоит в том, что по сути все они сводятся к выявлению момента резкого изменения (разладки) некоторых характеристик рассматриваемого объекта на основе статистических данных о других характеристиках этого объекта.

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

Для создания таких систем с привлечением программных средств требуется разработка соответствующих фундаментальных математических методов обработки поступающей и поступившей информации исходя из естественных критериев оптимальности. В свою очередь, при построении оптимальных методов обнаружения разладки (методов скорейшего обнару-(НС&Л/ИЛ разладки) необходимо прежде всего формализовать

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

Имеется два "статистически разных" случайных процесса X1 = (X/)f>0 и X2 = (X£2)t>0, определенных на фильтрованном вероятностном пространстве (П, J-, Р). Эти процессы "формируют" наблюдаемый процесс X = (Xt)t>0 в том смысле, что

Xt ~ 1 х*в, при t > е, (1) где в £ [0, оо] - момент разладки (0 = оо означает, что разладка не происходит), представляющий собой либо случайную величину с заданным распределением (байесовский подход), либо неизвестный детерминированный параметр. (Везде в дальнейшем обозначение "Р-п.н." использоваться не будет, то есть предполагается, что соотношения С, = или <, = между измеримыми множествами или случайными величинами, соответственно, выполняются с вероятностью единица.) Типичным примером наблюдаемого процесса, у которого происходит разладка, может служить процесс х = / Yu при t < г + Yu при t > в, где (Yt)f>0 - некоторый стационарный процесс, а г Е 1 - известная или неизвестная константа, характеризующая величину изменения среднего значения.

Предполагается, что значения реализации процесса (Xt)t>0 поступают последовательно, текущим образом и задача заключается в том, чтобы на основании поступающих данных построить такой конечный момент остановки г = г (и>) (выбором г определяется правило подачи сигнала тревоги) относительно фильтрации = порожденной процессом (Xt)t>Q (то есть Т* = a {Xs, 0 < s < £}), который в определенном смысле "наиболее близок" к моменту разладки в (в момент времени 9 "исправный" процесс {X})t>0 меняется на "дефектный" процесс (X^)t>Q). Таким образом, величина г может интерпретироваться как решение о том, что разладка наступила в момент времени т = т(и>).

Пусть Ps = Law(X|5) обозначает распределение процесса (.Xt)t>0 при условии, что разладка происходит в детерминированный момент времени в = s. В частности, через Роо обозначим распределение (Xt)t>Q при условии, что разладка никогда не произойдет, то есть Р^ = Law'{X},t > 0), а через Ро -распределение процесса (X^jt>Q.

Момент остановки г, с помощью которого оценивается момент разладки в, должен обладать следующими показателями качества, впервые введенными А.Н. Ширяевым [38-42] и в дальнейшем повсеместно используемыми (см., например, статьи [10,27,28,35,44,51,68,82,88,94,95,100,111,111-114,116,124, 125,127,129]):

1. Малое число ложных тревог. Действительно, в большинстве практических ситуаций крайне нежелательно иметь значительное число ложных тревог (сигналов тревог при отсутствии разладки), поэтому "хороший" момент остановки должен быть нечувствителен к шуму. Появление ложных тревог при контроле системы с помощью момента остановки г можно характеризовать, например, вероятностью ложной тревоги а0 = Ро (т < 9) , 9 € [0, сю), или сродним временем до ложной тревоги

Т = ЕооТ, или их комбинацией, где обозначает математическое ожидание по мере Р<7, в € [0, оо]. Таким образом, при использовании момента остановки г необходимо, чтобы либо среднее время до ложной тревоги было большим, либо вероятность ложной тревоги была малой. Легко показать [40], что если момент разладки т является случайной величиной, имеющей экспоненциальное распределение, то условие ЕооТ > Т эквивалентно ограничению вероятности ложной тревоги ад < а (или уровня значимости в статистическом смысле).

2. Малое запаздывание в обнаружении разладки. В любой практической ситуации в высшей степени желательно, чтобы сигнал тревоги т возникал без задержки хотя бы для того, чтобы "потерять" как можно меньше наблюдений для оценивания характеристик процесса (Xf)t>Q после разладки. Поэтому важным вероятностным показателем является среднее время запаздывания в обнаружении разладки. При этом необходимо разрешить противоречие между требованием, например, большого среднего времени до ложной тревоги и малого среднего времени запаздывания в обнаружении разладки, поскольку способность быстро обнаруживать изменения повышает вероятность ложных тревог. На практике путь решения, очевидно, зависит от конкретной задачи. Обычно используется следующий подход: ищется момент остановки т|., удовлетворяющий условию ЕооТ* = Т (или ЕооТу. > Т) при фиксированном значении Т > 0, для которого среднее время запаздывания принимает минимальное значение. Такой момент будем называть оптимальным.

Зачастую среднее время запаздывания в обнаружении разладки характеризуется с помощью так называемых байесовской., обобщенной байесовской и минимаксной функций риска, а соответствующие задачи скорейшего обнаружения разладки называются задачами о разладке в байесовской (вариант (А)), обобщенной байесовской (вариант (В)) и минимаксной (вариант (С)) постановках.

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

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

В [38-40,42,43,127] был рассмотрен вариант (А) задачи о разладке в дискретном и непрерывном времени (для броуновского движения), причем момент разладки в моделировался случайной величиной с геометрическим (в случае дискретного времени) или экспоненциальным (в случае непрерывного времени) распределением. Оказалось, что оптимальная процедура скорейшего обнаружения разладки состоит в объявлении тревоги в момент, когда апостериорная вероятность того, что разладка произошла, впервые превосходит некоторый порог, зависящий от параметров задачи.

В [38-40,42,43] для случая непрерывного времени специальным предельным переходом было получено решение варианта (В) задачи о разладке для броуновского движения, к которому сводится решение задачи о скорейшем обнаруженный нарушения стационарного реэюима (см. [40], [126, п.4.2], [124, §3.9]). Отметим, что прямое решение варианта (В) задачи о разладке без предельного перехода было приведено в работе [68]. Оптимальный метод в указанных работах строится на основе так называемого процесса Ширяева (в случае дискретного времени аналогом процесса Ширяева является так называемая процедура Ширяева-Робертса [116]).

Минимаксная постановка задачи о разладке с существенным супремумом в дискретном времени была впервые рассмотрена в [94]. Было показано, что метод "кумулятивных сумм" (CUSUM - Cumulative Sums) является асимптотически оптимальным первого порядка. Позже в [100] было доказано, что в случае дискретного времени специальная модификация процедуры CUSUM является оптимальным решением задачи скорейшего обнаружения разладки в минимаксной постановке с существенным супремумом. Аналогичные результаты были получены в [44,101,124] для случая непрерывного времени.

В [112,113] для случая дискретного времени была предложена процедура на основе рандомизированного процесса Ширяева, которая оказалась асимптотически оптимальным (при больших значениях среднего времени до ложной тревоги) решением варианта (С) задачи скорейшего обнаружения разладки. В [68] в непрерывном времени были получены асимптотики первого порядка при больших значениях среднего времени до ложной тревоги для минимаксной функции риска, причем асимптотически оптимальный момент остановки строился на основе процесса Ширяева. Затем в [10] результаты статьи [68] были улучшены, а именно, за счет рандомизации процесса Ширяева удалось получить асимптотически оптимальный момент остановки второго порядка.

В [111] для случая непрерывного времени было проведено сравнение процедуры CUSUM и процедуры на основе процесса Ширяева, которое показало, что средние запаздывания в обнаружении разладки у этих процедур сравнимы.

Поведение процедуры "экспоненциально взвешенных скользящих средних" (EWMA - Exponentially Weighted Moving Average) было изучено в [27,28,35,95,129]. Оказалось, что метод EWMA существенно проигрывает по сравнению с процедурой CUSUM и процедурой на основе процесса Ширяева.

Наконец, в [88] для случая дискретного времени была исследована процедура скорейшего обнаружения разладки на основе скользящего среднего и было показано, как выбирать параметры процедуры, чтобы она стала асиптотичсски оптимальной первого порядка в минимаксном смысле.

Отметим, что наиболее часто используются байесовская, обобщенная байесовская или минимаксная функции риска. Однако, существуют и другие функции риска, см. например [40, 51,82,114,124]. В то же время, как показано в [125], некоторые из этих функций риска могут быть сведены к байесовской.

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

До сих пор были разработаны методы скорейшего обнаружения момента изменения интенсивности пуассоновского потока событий, являющиеся оптимальными только в "среднем", поскольку при построении этих методов было сделано предположение, что момент разладки представляет собой случайную величину с заранее заданным распределением [11,52-54,62,72, 110,127] (байесовская постановка задачи о разладке). В то же время в приложениях зачастую требуется использовать метод обнаружения разладки, который будет оптимальным в случае, когда момент разладки представляет собой детерминированный неизвестный параметр, однако теоретические методы построения эффективных процедур обнаружения разладки в этом важном для практики случае отсутствовали.

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

В соответствии с поставленной целью были определены следующие задачи исследования:

1. Свести задачу скорейшего обнаружения момента изменения интенсивности потока событий в пуассоновской модели потока к математической задаче оптимальной остановки некоторого модельного процесса.

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

3. Вычислить среднее время запаздывания в обнаружении разладки при использовании полученных методов.

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

Опишем структуру диссертационной работы.

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

Первая глава посвящена изложению постановок задачи скорейшего обнаружения разладки и получению представления для модельного процесса специального вида (т.н. кусочно-детерминистический процесс Ширяева (iftt)t>oi являющийся достаточной статистикой), к оптимальной остановке которого сводится задача скорейшего обнаружения момента изменения интенсивности пуассоновского потока событий.

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

Во втором, разделе показано, как получить уравнение для процесса апостериорной вероятности (7г^(>0 из уравнения для процесса отношения правдоподобия (<ft)t>o ■ Далее, специальным предельным переходом из процесса ((pt)l>0 получен кусочно-детерминистический процесс Ширяева (ifit)t>о> являющийся достаточной статистикой для варианта (В) задачи скорейшего обнаружения разладки. Доказывается, что процесс (^)t>0 марковский.

Вторая глава посвящена решению варианта (В) задачи скорейшего обнаружения разладки для пуассоновского процесса.

В первом разделе доказывается, что вариант (В) задачи скорейшего обнаружения разладки может быть сведен к условно-экстремальной задаче оптимальной остановки кусочно-детерминистического процесса (-0t)j>o, то есть процесс (ipt)t>Q играет роль своего рода достаточной статистики в варианте {В) задачи о разладке.

Во втором разделе исследуется поведение выборочных траекторий кусочно-детерминистического процесса (ipt)t>0 и доказывается, что этот процесс с вероятностью единица за конечное время выходит на любой заданный уровень.

В третьем разделе решается задача вычисления среднего значения некоторых интегральных функционалов от кусочно-детерминистического процесса (ijh)t>о

В четвертом разделе разрабатывается метод для вычисления математического ожидания момента выхода на заданную границу кусочно-детерминистического процесса {'фь)^

В пятом разделе решается задача подбора такого значения границы, среднее значение момента выхода на которую кусочно-детерминистического процесса (ipt)t>о равняется заданной величине.

В шестом разделе решается условно-экстремальная задача оптимальной остановки кусочно-детерминистического процесса (^)t>0 и доказывается, что момент первого выхода этого процесса на специальным образом подобранную границу является оптимальным решением варианта (5) задачи скорейшего обнаружения разладки.

В седьмом разделе подсчитываются среднее время запаздывания при обнаружении разладки в варианте (5) задачи скорейшего обнаружения разладки и асимптотики этого среднего времени.

Третья глава посвящена получению асимптотически оптимального решения варианта (С) задачи скорейшего обнаружения разладки для пуассоновского процесса.

В первом разделе определяются оценки сверху и снизу среднего времени запаздывания при обнаружении разладки в варианте (С) задачи скорейшего обнаружения разладки.

Во втором разделе решается задача вычисления оценки сверху среднего времени запаздывания при обнаружении разладки в варианте (С) задачи скорейшего обнаружения разладки, которая сводится к решению дифференциально-разностного уравнения.

В третьем разделе подсчитываются асимптотики оценки сверху среднего времени запаздывания и доказывается, что момент первого выхода кусочно-детерминистического процесса (i)t)t>o на специальным образом подобранную границу является асимптотически оптимальным решением варианта (С) задачи скорейшего обнаружения разладки.

В заключении сформулированы основные результаты диссертационной работы.

Результаты, приведенные в диссертации, были опубликованы автором в статьях [5-9,58] и использовались в работах, проводимых в рамках программы "Развитие научного потенциала высшей школы" (код проекта РНП.2.2.1.1.2467, тема 717).

Заключение

В диссертационной работе впервые были получены следующие научные результаты:

1. Разработан метод сведения задачи скорейшего обнаружения момента изменения интенсивности потока событий в пуассоновской модели потока к математической задаче оптимальной остановки модельного процесса специального вида (т.н. кусочно-детерминистический процесс Ширяева, являющийся достаточной статистикой).

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

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

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

5. Найдены асимптотики среднего времени запаздывания в обнаружении разладки.

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

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

• могут применяться при построении компонент автоматизированных информационных систем, используемых для выявления разладок;

• приближенно описывают, какие "эффекты" следует ожидать на практике при применении полученных методов скорейшего обнаружения момента смены интенсивности пуассоновского потока событий;

• позволяют отработать подходы к решению задачи скорейшего обнаружения разладки для более общих, по сравнению с изменением интенсивности пуассоновского потока событий, моделей разладки (в которых под разладкой понимается, например, одновременное изменение нескольких характеристик наблюдаемого процесса).

1. Бассевиль М., Банвенист А. Обнаружение изменения свойств сигналов и динамических систем. - М.: Наука, 1989.

2. Беллман Р., Кук K.JI. Дифференциально-разностные уравнения. М.: Мир, 1967.

3. Бородкин Л.И., Моттль В.В. Алгоритм обнаружения моментов изменения параметров уравнения случайного процесса // Автоматика и телемеханика. 1976. - N. 6. - С. 23-32.

4. Буркатовская Ю.Б., Воробейников С.Э. Гарантированное обнаружение момента разладки GARCH-процесса // Автоматика и телемеханика. 2006. - N. 12. - С. 56-70.

5. Бурнаев Е.В. Задача о разладке для пуассоновского процесса в обобщенной байесовской постановке // Успехи математических наук. 2007. - Т. 62, вып. 4. - С. 151-152.

6. Бурнаев Е.В. О задаче обнаружения разладки для пуассо-новекого процесса в обобщенной байесовской постановке // Труды 50-й научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук". -Москва-Долгопрудный: ФУПМ, 2007. С. 11-14.

7. Бурнаев Е.В. О задаче обнаружения разладки для пуассо-новского процесса в обобщенной байесовской постановке // Теория вероятностей и ее применения. 2008. - Т. 53, вып. 3. - С. 534-556.

8. Гальчук Л.И., Розовский Б.Л. Задача о "разладке" для пуассоновского процесса // Теория вероятностей и ее применения. 1971. - Т. 16, вып. 4. - С. 729-734.

9. Градштейн И.С., Рыжик И.М. Таблицы интегралов, сумм, рядов и произведений. М.: Физматгиз, 1963, 4-е издание.

10. Дарховский Б.С. Непараметрический метод для апосте-v риорного обнаружения момента "разладки" последовательности независимых случайных величин // Теория вероятностей и ее применения. 1976 - Т. XXI, вып. 1. - С. 180-184.

11. Дарховский Б.С., Бродский Б.Е. Апостериорное обнаружение момента "разладки" случайной последовательности // Теория вероятностей и ее применения. 1980. - Т. XXV, вып. 3. - С. 476-489.

12. Дынкин Е.Б. Марковские процессы. М.: Физматгиз, 1963.

13. Жакод Ж., Ширяев А.Н. Предельные теоремы для случайных процессов. Т.1. М.: Физматлит, 1994.

14. Жиглявский А.А., Красковский А.Е. Обнаружение разладки случайных процессов в задачах радиотехники. -JL: Издательство Ленинградского университета, 1988.

15. Клигене Н., Телькснис JI. Методы обнаружения моментов изменения свойств случайных процессов // Автоматика и телемеханика. 1983. - N. 10. - С. 5-56.

16. Колмогоров А.Н., Прохоров Ю.В., Ширяев А.Н. Вероятностно-статистические методы обнаружения спонтанно возникающих эффектов // Тр. МИАН. 1988. - Т. 182. - С. 4-23.

17. Лебедев Н.Н. Специальные функции и их применения. -М.: Физматгиз, 1968.

18. Липцер Р.Ш., Ширяев А.Н. Статистика случайных процессов. М.: Наука, 1974.

19. Липцер Р.Ш., Ширяев А.Н. Теория мартингалов. М.: Наука, 1986.

20. Моттль В.В., Мучник И.Б. Скрытые марковские модели в структурном анализе сигналов. М.: Физматлит, 1999.

21. Никифоров И.В. Применение кумулятивных сумм для обнаружения изменения характеристик случайного процесса // Автоматика и телемеханика. 1979. - N. 2. - С. 48-58.

22. Никифиров И.В. Модификация и исследование процедуры кумулятивных сумм // Автоматика и телемеханика. 1980. - N. 9. - С. 74-80.

23. Никифоров И.В. Последовательное обнаружение изменения свойств временных рядов. М.: Наука, 1983.

24. Новиков А.А., Эргашев Б. Аналитический подход к расчету алгоритма экспоненциального сглаживания для обнаружения разладки // Статистические проблемы управления. Вильнюс: Ин-т математ. и кибернет. АН Лит. ССР, 1988. - Вып. 83. - С. 110-114.

25. Новиков А. А. О моменте первого выхода процесса авторегрессии за уровень и одно применение в задаче "разладки" // Теория вероятностей и ее примененияю 1990. - Т. 35, вып. 2. - С.282-292.

26. Прудников А.П., Брычков Ю.А., Маричев О.И. Интегралы и ряды. Специальные функции. М.: Наука, 1983.

27. Сивухин Д.В. Общий курс физики. Т. 5. Атомная и ядерная физика. Физматлит, 2006.

28. Сырецкий Г.А. Информатика. Фундаментальный курс. Том I. Основы информационной и вычислительной техники. СПб.: БХВ-Петербург, 2005.

29. Тартаковский А.Г. Последовательные методы в теории информационных систем. М.: Радио и связь, 1991.

30. Тартаковский Г.П. Теория информационных систем. М.: Физматкнига, 2005.

31. Тер-Крикоров A.M., Шабунин М.И. Курс математического анализа. М.: МФТИ, 1997.

32. Фишман М.М. Оптимизация алгоритма обнаружения разладки, основанного на статистике экспоненциального сглаживания // Статистические проблемы управления. -Вильнюс: Ин-т математ. и кибернет. АН Лит. ССР, 1988. Вып. 83. - С. 146-151.

33. Шахтарин Б.И. Случайные процессы в радиотехнике. Т.

34. Линейные преобразования. М.: Гелиос АРВ, 2006.

35. Шахтарин Б.И. Случайные процессы в радиотехнике. Т.

36. Нелинейные преобразования. М.: Гелиос АРВ, 2006.

37. Ширяев А.Н. Обнаружение спонтанно возникающих эффектов // Докл. АН СССР. 1961. - Т. 138, вып. 4. - С. 799-801.

38. Ширяев А.Н. Задача скорейшего обнаружения нарушения стационарного режима // Докл. АН СССР. 1961. -Т. 138, вып. 5. - С. 1039-1042.

39. Ширяев А.Н. Об оптимальных методах в задачах скорейшего обнаружения // Теория вероятностей и ее применения. 1963. - Т. VIII, вып. 1. - С. 26-51.

40. Ширяев А.Н. К обнаружению разладок производственного процесса. I, II // Теория вероятностей и ее применения.- 1963. Т. VIII, вып. 3. - С. 264-281; - Т. VIII, вып. 4. -с. 431-445.

41. Ширяев А.Н. Некоторые точные формулы в задаче о "разладке" // Теория вероятностей и ее применения. 1965.- Т. 10, вып. 2. С. 380-385.

42. Ширяев А.Н. Статистический последовательный анализ. Оптимальные правила остановки. М.: Наука, 1969.

43. Ширяев А.Н. "Минимаксная оптимальность метода кумулятивных сумм (CUSUM) в случае непрерывного времени" // Успехи математических наук. 1996. - Т. 51, вып. 4. - С. 173-174.

44. Ширяев А.Н. Основы стохастической финансовой математики. Том 1. Факты. Модели. М.: Фазис, 1998.

45. Andersson Е. Monitoring cyclical processes: a non-paramctric approach // Journal of Applied Statistics. 2002.- V. 29. P. 973-990.

46. Barlow J.S., Creutzfeldt O.D.,Michael D., Houchin J., Epelbaum H. Automatic adaptive segmentation of clinical EEGs // Electroencephalography and Clinical Neurophysiology. 1981. - V. 51, N. 5. - P.512-525.

47. Basscvillc M. Detecting changes in signals and systems. A survey // Automatica. 1989. - V. 24. - P. 309-326.

48. Basseville M., Nikiforov I. Detection of aprupt changes: theory and applications. Prentice Hall, 1993.

49. Basu A.P., Rigdon S.E. Statistical methods for the reliability of repairable systems. New York: John Wiley and Sons, 2000.t

50. Bayraktar E., Dayanik S., Karatzas I. Standard poisson disorder problem revisited // Stochastic Processes and Their Applications. 2005. - V. 115, N. 9. - P. 1437-1450.

51. Bayraktar E., Dayanik S., Karatzas I. Adaptive poisson disorder problem // Annals of Applied Probability. 2006. - V. 16, N. 3. - P. 1190-1261.

52. Bayraktar E., Dayanik S. Poisson disorder problem with exponential penalty for delay // Mathematics of Operations Research. 2006. - V. 31, N. 2. - P. 217-233.

53. Bayraktar E., Poor H.V. Quickest detection of a minimum of two poisson disorder times // SIAM Journal on Control and Optimization. 2007. - V. 46, N. 1. - P. 308-331.

54. Braun J.V., Braun R.K., Miiller H.G. Multiple changepoint fitting via quasilikelihood, with application to DNA sequence segmentation // Biometrika. 2000. - V. 87, N. 2. - P.301-314.

55. Brodsky B.E., Darkhovsky B.S. Non-parametric statistical diagnosis. Kluwer, The Netherlands, 2000.

56. Bodenstein G., Praetorius H.M. Feature extraction from the electroencephalogram by adaptive segmentation // Proceedings of the IEEE. 1977. - V. 65, N. 5. - P.642-652.

57. Burnaev E.V. Quickest detection of intensity change for Poisson process in generalized Bayesian setting / / Proceedings of the 15th European4 Young Statisticians Meeting (EYSM-2007). 2007. - P. 1-5.

58. Change-point problems / Ed. by Carlstein E., Muller H.-G., Siegmund D. Papers presented at the AMS-IMS-SIAM

59. Summer Research Conference on Change-Point Problems. -Mt. Holyoke College, 1992.

60. Chen J., Gupta A.K. Testing and locating variance changepoints with application to stock prices // Journal of the American Statistical Association. 1997. - V. 92, N. 438.- P. 739-747.

61. Dacorogna M.M., Gen3ay R., Mtiller U.A., Olsen R.B., Pictet O.V. An introduction to high-frequency finance. Academic Press, 2001.

62. Dayanik S., Sezer S.O. Compound Poisson disorder problem // Mathematics of Operations Research. 2005. - V. 31, N. 4. - P. 649-672.

63. Davis M.H.A. A note on poisson disorder problem // Banach Center Publ. 1976. - V. 1. - P. 65-72.

64. Davis M.H.A. Piecewise-deterministic Markov processes: a general class of nondiffusion stochastic models // J. Roy. Statist. Soc. Ser. B. 1984. - V. 46, N. 3. - P. 353-388.

65. Davis M.H.A. Markov models and optimization. Monographs on statistics and applied probability, vol. 49. London: Chapman&Hall, 1993.

66. Delpar H., Dacier M., Wespi A. Towards a taxonomy of intrusion-detection systems // Computer Networks. 1999.- V. 31, N. 8. P. 805-822.

67. Dvoretzky A., Kiefer J., Wolfowitz J. Sequential decision problems for processes with continuous time parameter. Testing hypotheses // Ann. Math. Statist. 1953. - V. 24.- P. 254-264.

68. Feinbcrg E.A., Shiryaev A.N. Quickest detection of drift change for brownian motion in generalized bayesian and minimax settings // Statistics and Decisions. 2006. - V. 24. - P. 445-470.

69. Fitch J., Raber E., Imbro D. Technology challenges in respoding to biological or chemical attacks in the civilian sector // Science. 2003. - V. 32. - P. 1350-1354.

70. Frisen M. Evaluations of methods for statistical surveillance // Statistics in Medicine. 1992. - V. 11. - P. 1489-1502.

71. Frisen M., Andersson E. Semiparametric surveillance of outbreaks // Statistical Research Unit, Department of Economics, School of Business, Economics and Law, Goteborg University, series Research Reports No. 2007:11. 2008.

72. Gapeev P.V. The disorder problem for compound Poisson processes with exponential jumps // Ann. Appl. Probab. -2005. V. 15, N. 1. - P. 487-499.

73. Grandell J. Doubly stochastic poisson processes. Berlin-Heidelberg-New York: Springer, 1976.

74. Gustaffson F. Adaptive filtering and change detection. New York: Wiley, 2000.

75. Gross D., Harris C.M. Fundamentals of queueing theory. Wiley Series in Probability and Statistics. Wiley-Interscience, 1998.

76. Hawking D.M., Olwell D.H. Cumulative sum charts and charting for quality improvement. New York: Springer-Verlag, 1998.

77. Hillson E.M., Reeves J.H., McMillan C.A. A statistical signalling model for use in surveillance of adverse drug reaction data // Journal of Applied Statistics. 1998. - V. 25. - P. 23-40.

78. Hohle M., Paul M., Held L. Statistical approaches to the surveillance of infectious diseases for veterinary public health // Technical Report. University of Munich: Department of Statistics, 2007. - N. 014.

79. Jon M. P., Sutivong A. Admission Control Algorithms For Cellular Systems // ACM Wireless Networks. 2001. - V. 7, N. 2. - P. 117-125.

80. Karagiannis Т., Molle M., Faloutsos M., Broido A. A nonstationary poisson view of internet traffic // Proc. IEEE INFOCOM 2004, Hong Kong. 2004. - V. 3. - P. 1558-1569.

81. Karatzas I. A note on Bayesian detection of change-points with an expected miss criterion // Statistics and Decisions.- 2002. V. 21. - P. 3-14.

82. Kim S., Peker S. et al. Report on detecting hackers (analyzing network traffic) by poisson model measure // Eighth PIMS-MITACS Industrial Problem Solving Workshop, PIMS-UBC.- Canada, Vancouver, ВС, 2004.

83. Kim H., Rozovskii B.L., Tartakovsky A.G. A nonparametric multichart CUSUM test for rapid detection of DOS attacksin computer networks // International Journal of Computing and Information Sciences. 2004. - V. 2, N. 3.

84. Kohler 0, Lerche H R. An empirical study concerning the detection of trend changes in some financial time series // FDM Preprint. 1997. - N. 36.

85. Koop G.M., Potter S.M. Forecasting and estimating multiple change-point models with unknown number of chane points // Technical report. Federal Reserve Bank of New York, 2004.

86. Kyprianou A.E. Introductory lectures on fluctuations of Levy processes with applications. Springer, 2006.

87. Lai T.L. Sequential changepoint detection in quality control and dynamical systems // J.R. Statist. Soc. B. 1995. - V. 52, N. 4. - P. 613-658.

88. Lam K., Yam H.C. CUSUM Techniques for technical trading in financial markets // Financial engineering and the japanese markets. 1997. - V. 4. - P. 257-274.

89. Lam Ho-Yu, Li Chi-Pan, Chanson S.T., Yeung Dit-Yan. A coordinated detection and response scheme for distributed denial-of-service attacks // Proceedings of the IEEE International Conference on Communications (ICC), Istanbul, Turkey. 2006.

90. Levin В., Kline J. The CUSUM test of homogeneity with an application in spontaneous abortion epidemiology // Statistics in Medicine. 1985. - V. 4. - P. 469-488.

91. Lindskog F., McNeil A. Common Poisson shock models: applications to insurance and credit risk modelling // ASTIN Bulletin. 2000. - V. 33, N. 2. - P. 209-238.

92. Lorden G. Procedures for reacting to a change in distribution // Ann. Math. Statist. 1971. - V. 42. - P. 1897-1908.

93. Lukacs J.M., Saccucci M.S. Exponentially weighted moving average control schemes: properties and enhancements (with discussion) // Technometrics. 1990. - V. 32, N. 1. - P. 1-29.

94. Madsen T.N. Tools for monotoring growing pigs // PhD thesis. Department of Animal Science and Animal Health, Royal Veterinary and Agricultural University. Dina Research Report N. 91, 103 pp. 2001.

95. Madsen T.N., Kristcnsen A.R. A model for monitoring the condition of young pigs by their drinking behavior // Computers and Electronics in Agriculture. 2005. - V. 48.- P. 138-154.

96. Madsen T.N., Andersen S., Kristensen A.R. Modelling the drinking pattern of young pigs using a state space model // Computers and Electronics in Agriculture. 2005. - V. 48.- P. 39-62.

97. Malladi D. P., Speyer J. L. A generalized shiryaev sequential probability ratio test for change detection and isolation //

98. EE Trans. Automatic Control. 1999. - V. AC-44, N. 8. -P. 1522- 1534.

99. Moustakides G.V. Optimal stopping times for detecting changes in distributions // Ann. Statist. 1986. - V. 14, N. 4. - P. 1379-1387.

100. Moustakides G. Optimality of the CUSUM procedure in continuous time // Ann. Statist. 2004. - V. 32, N. 1. -P. 302-315.

101. Moustakides G.V. Sequential change detection revisited // The Annals of Statistics. 2008. - V. 36, N. 2. - P. 787-807.

102. Naus J., Wallenstein S. Temporal surveillance using scan statistics // Statistics in Medicine. 2005. - Vol. 25, N. 2. -P. 311-324.

103. Neill D.B., Moore A.W., Cooper G.F. A Bayesian Spatial Scan Statistic // Advances in Neural Information Processing Systems. 2006. - V. 18. - P. 1003-1010.

104. Nikiforov I.V. Statistical method for detecting the time at which the sensor proeprties change // Preprint of IMEKO Symposium on Application of Statistical Methods in Measurement. Leningrad, 1978. - P. 1-7.

105. Ortner M., Nehorai A. A sequential detector for biochemical release in realistic environments // IEEE Transactions on Signal Processing. 2007. - V. 55, N. 8. - P. 4173-4182.

106. Osanaiye P.A., Talabi C.O. On some non-manufacturing applications of countcd data cumulative sum (CUSUM) control chart schemes // The Statisticians. 1989. - V. 38. - P. 251-257.

107. Page E.S. Continuous inspection schemes // Biometrika. -1954. V. 41. - P. 100-114.

108. Page E.S. Control charts with warning lines // Biometrika. 1955. - V. 42. - P. 243-257.

109. Peskir G., Shiryaev A.N. Solving the Poisson disorder problem // Advances in Finance and Stochastics. Essays in Honour of Dieter Sondermann / Ed. by Sandmann K., Schonbucher P. Berlin: Springer, 2002. - P. 295-312.

110. Pollak M., Siegmund D. A diffusion process and its applications to detecting change in the drift of Brownian motion // Biometrika. 1985. - Vol. 72. - P. 267-280.

111. Pollak M. Optimal detection of a change in distribuion // Ann. Statist. 1986. - V. 13. - P. 206-227.

112. Pollak M. Average run lengths of an optimal methods of detecting a change in distribution // Ann. Statist. 1987. -V. 15. - P. 749-779.

113. Poor V.H. Quickest detection with exponential penalty for delay // Annals of Statistics. 1998. - V. 26. - P. 2179-2205.

114. Roberts S.W. Control charts based on geometric moving average // Technometrics. 1959. - V. 1. - P. 239-250.

115. Roberts S.W. A comparison of some control chart procedures // Technometrics. 1966. - V. 8. - P. 411-430.

116. Scalas E., Gorenflo R., Luckock H., Mainardi F., Mantelli M., Raberto M. Anomalous waiting times in high-frequency financial data // Quant. Finance. 2004. -V. 4. - P. 695-702.

117. Scargle J. Studies in astronomical time series analysis. V. Bayesian blocks, a new method to analyze structure in photon counting data // Astrophysical Journal. 1998. -V. 504. - P. 405-418.

118. Scott S. L., Smyth P. The Markov modulated poisson process and Markov poisson cascade with applications to web traffic data // Bayesian Statistics. V. 7. - P. 671-680. / Ed. by Bayarri M. J. et al. - UK, Oxford: Oxford University Press, 2003.

119. Sego L.H. Applications of Control Charts in Medicine and Epidemiology // Dissertation, faculty of the Virginia Polytechnic Institute and State University, Blacksburg, Virginia. 2006.

120. Sequential analysis. Design methods and applications. Celebrating eighty years of control charts. Walter A. Shewhart's Legacy // Taylor and Francis. 2007. - V. 26, N. 2, 3.

121. Shewhart W.A. The application of statistics as an aid in maintaining quality of manufactures product // J. Amer. Statist. Assoc. 1925. - V. 138. - P. 546-548.

122. Shewhart W.A. Economic control of manufactured product. New York: Van Nostrand Rainhold, 1931. (Republished in 1981 by the American Society for Quality Control, Milwaukee.)

123. Shiryaev A.N. Quickest detetion problems in the "Technical Analysis" of the financial data // Mathematical Finance -Bachelier Congress (Paris, 2000). Berlin: Springer, 2002. -P. 487-521.125

124. Shiryaev A.N. A remark on the quickest detection problems // Statistics and Decision. 2004. - V. 22. - P. 79-82.

125. Shiryaev A.N. From "Disorder" to Nonlinear Filtering and Martingale Theory // Mathematical Events of the Twentieth Century / Ed. by Bolibruch A.A., Osipov Yu.S., Sinai Ya. G.- Springer and Phasis, 2006.

126. Shiryaev A.N., Peshkir G. Optimal stopping and free-boundary problems (Lectures in Mathematics. ETH Zurich).- Birkhauser, 2006.

127. Siegmund D. The Wald memorial lectures. Boundary crossing probablities and statistical applications // Annals of Statistics. 1996. - V. 14. - P. 261-404.

128. Srivastava M.S., Wu Y. Comparison of EWMA, CUSUM and Shiryaev-Roberts procedures for detecting a shift in the mean // Annals of Statistics. 1993. - V. 21. - P. 645-670.

129. Steiner S.H., Cook R.J., Farewell V.T. Monitoring paired binary surgical outcomes using cumulative sum charts // Statistics in Medicine. 1999. - V. 18, N. 1. - P. 69-86.

130. Tartakovsky A.G., Veeravalli V. Change-point detection in multichannel and distributed systems with applications // Applications of Sequential Methodologies / Ed. by Mukhopadhyay M., Datta S., Chattopadnaya S. New York: Dekker, 2002. - P. 339-370.

131. Tartakovsky A.G., Veeravalli V.V. General asymptotic Bayesian theory of quickest change detection // Theory of probability and its applications. 2005. - V. 49. - P. 458497.

132. Tartakovsky A.G., Rozovskii B.L., Blazek R.B., Kim H. Detection of intrusions in information systems by sequential change-point methods // Statistical Methodology. 2006. -V. 3. - P. 252-293.

133. Vasilios A.S., Papagalou F. Application of anomaly detection algorithms for detecting SYN flooding attacks // Computer Communications. 2006. - V. 29, N. 9. - P. 1433-1442.

134. Wetherill G.B. Sampling inspections and quality control. -London/New York: Chapman&Hall/Halsted Press, 1977.

135. Willsky A.S. A survey of design methods for failure detection in dynamic systems // Automatica. 1976. - V. 12. - P. 601611.