Повышение эффективности метода Монте-Карло в задачах разладки тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

не 0й

-1 п ^лд ез

5 ис!АНКТ-ПЕТЕРВУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

АЛСАВВЛГХ Мохамад Захир Тауфик

ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ МЕТОДА. МОНТЕ-КАРЛО В ЗАДАЧАХ РАЗЛАДКИ

Специальность: 01.01.09 - математическая кибернетика 05.13.16 - применение вычислительной техники, математического моделирования и мате- ?- веских методов в научных исследог .

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

САНКТ-ПЕТЕРБУРГ 1993 г.

Работа выполнена на кафедре статистического моделирования математико-механического факультета Санкт-Петербургского государственного университета.

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

Официальные оппоненты: доктор технических наук, профессор A.B. Красковский, кандидат физико-математических наук, доцент М.К. Чирков

Ведущая органиэация-Саикт-Петербургская академия гражданской авиации

па заседании специализированного совета К 063.57.49 по присуждению ученой степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, г.Санкт-Петербург, Старый Петергоф, Библиотечная площадь, дом 2, математико-механический факультет.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского государственного университета по адресу: 199034, г.Санкт-Петербург, Университетская набережная, дом 7/9.

1993 г.

Ученый секретарь специализировавногб Совета К 063.57.49, кандидат физико-математических наук, доцепт А.И.ШЕПЕЛЯВЫЙ

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

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

Важные результаты в этой области получены такими учеными как С.М. Ермаков, Г.Д. Михайлов, A.A. Жиглявский, А.Е. Крас-ковский, Д.Сигмунд.

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

3

ное исследование разработанных алгоритмов.

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

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

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

Алпробация работы. Результаты работы докладывались и обсуждались на семинарах кафедры статистического моделирования и лаборатории моделирования систем и статистических методов СПбГУ, представлены к опубликованию в работе [1].

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и двух приложений. Основной текст диссертации занимает 85 страниц машинописного текста. Библиография содержит 36 наименований. Приложения содержат 72 страницы.

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

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

4

В главе 1 рассматривается повышение эффективности метола Монте-Карло для расчета вероятностей ошибок теста отношения правдоподобия.

В пункте 1.1 главы 1 рассматривается общая постановка задачи. Предположим, что на интервале времени (О, .¡У) наблюдаются значения случайного процесса

где C(i) - гауссопский шум с нулевым средним (E((i) = о) и ковариационной функцией R(t,a) = EC(t)i(s), S(t) =Ец(г) - среднее значение процесса y(t). Причем функция û(t) такова :

.„, /о 1Т (о, t£{r,T + T\

«W-i^W • гда = t € [г, г + Tj

Если û(t) = 0, значит сигнал отсутствует в задшшом интервале, в другом случае наблюдаем сигнал прямоугольной формы с амплитудой А, длительностью Т и моментом появления т. (Другими словами, наблюдаем разладку случайного процесса в смысле изменения его свойств, происходящего в момент времени г).

Формально, задача обнаружения сигнала является задачей проверки гипотезы :

Яо : 0(f) = O, t€[0,JÏ]

Пх : Щ = %,,+л(<). «€ [О, Щ-

Из классических результатов теории проверки гипотез при фиксированном г наиболее применим критерий для проверки гипотезы Во против альтернативы Я1} основанный на статистике логарифма отношения правдоподобия

где yf = {yi,...,ïw}, и irCvfl-ffi) - функции правдоподобия

соответственно при гипотезе Я0 и альтернативе Ui в предположении, что моментом прихода сигнала является т.

s

Если т неизвестно, то критерий отношения правдоподобия имеет вид

Hi

тахЬЛ^ J ha, Л

где Ло - некоторый порог.

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

А ТА1

tSIT+l

И соответственно критерий отношения правдоподобия (при фиксированном т) может быть представлеп так :

К * hoc1 ТА

2J к 5 = —+ т-

i—А+1 Я, л i

Обозначим через i отношение сигнал / шум : 7 = А\/Т/а.

Перейдем к непрерывному аналогу §т(Ъ) - гауссовскому процессу S(t), i € [о, А/], характеристики которого по виду совпадают с характеристиками процесса ST(k) :

ЕS(t) = О, ЕS{t)S(t + u) = max{0,1 - |и|}.

Непрерывный аналог решающего правила имеет вид :

5т(0 % h-Q,(t),

ä,

где Л = J + Ь., Qr(i) = 7max{0,1 - |i - т|}.

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

а = Р{ sup 5(t) > h], 'ФМ]

а второго рода (пропуска сигнала) -

р = Р{5(0 <к- длл всех г <= [О, Щ \ Я1}.

При фиксированном Ц вероятность 0Ш1бки первого рода а зависит только от нормированного порога Л (т.е. « = с<(Л)), а второго рода - также от пеизвестпого момента появления сигнала г (т.е. /? = /?(Л,т)).

В пункте 1.2 главы 1 рассматривается применение существенной выборки в методе Мопте-Карло для для оценивания вероятности ошибки первого рода теста отношения правдоподобия. Прямой подход в методе Мопте-Карло - оценивать вероятности относительными частотами : оценивать а = Р(Л), вероятность события А, которое согласно Р имеет распределение Р{1Л = 1} = а — 1 - Р{1л = 0}. Эта оценка несмещенная и имеет дисперсию

Уагр (/„) = «(!-«).

Если а мало, то пужпо сделать очень много реализаций, чтобы обеспечить точную оценку.

Применяя существенную выборку, получаем

Р (^4) = У

А

где I - отношение вероятности Р относительно ( £ = если Р и <3 имеют соответственно плотности р и ?). Тогда можно оценить а средним числом п независимых реализаций 1Л1, произведенных распределением, вызванным С}. Эта оценка также несмещенная и имеет дисперсию

Уах¿1*1) = I Ыд-с?,

л

которая может быть меньше, чем в прямом методе Мопте-Карло. Основным результатом пункта 1.2 является представление

ог = Р«.{34: &2;Л}= J ¿Р}. =

7

= I ехр{((Г - в")§к - Г(Ф(5') - ЩО'))} ¿Р?,1 (1.2.1)

Применяя к оценке последнего интеграла метод Монте-Карло имеем оценку, полученную с помощью метода существенной выборки (Аее», Еа = а)

& = £ ¿«р{(«' " - ТОО ~ *(*"))}•

Дисперсия оценки (1.2.1) имеет вид :

Уы& = J ехр[2(0' - в")5ь - 2Г(«(9') - Ф(й"))] ¿Р* ~ <*'] <

< - |ехрГ(20' - в")к - Т(2Ф(0') - «(«"))] - а2|

Результаты моделирования и сравнения приведены в приложении 1.

При типичных значениях порога и параметров и,Т,Ы дисперсия оценки существенной выборхи меньше дисперсии прямой оценки метода Монте-Карло до 10е раз.

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

В пункте 1.4 главы 1 приведены асимптотические формулы пересчета оценок вероятностей ошибок.

В пункте 1.5 главы 1 описаны случайное блуждание и интегральные уравнения, а также метод существенной выборки.

В главе 2 рассматривается обнаружение разладки гауссов-ского случайного процесса.

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

8

чин. Плотность распределения выражается формулой:

1= 1,2, где параметр 0,- = (м.,"?); (/' - математическое ожидание, о? - дисперсия) может для всей выборки иметь одно зпачепие , а может п неизвестный момент г скачкообразно изменить значения на в2. Во втором случае имеет место разладка. Формально эта альтернатива описывается двумя возможными гипотезами:

До : ~ р(х. Ох) —нет разладки

Яд: {^ОГГ/ ~ р(г1 —разладка в момент г.

Задача состоит в том, чтобы выбрать одну из гипотез Я0 и 77,, а также определить неизвестный момент разладки г в случае Я!.

В пункте 2.2 представлен расчет вероятностей ошибок первого и второго рода теста отношения правдоподобия для двух-параметрической разладки гауссонского процесса. Наблюдается случайный процесс, измерения {¡г,}^ - независимые случайные величины, имеющие гауссовское распределение. Рассматриваются следующие гипотезы :

Я0 : Ыг)

отсутствие разладки.

разладка в неизвестный момент г

{««к« ~

{г.Ки-ЛфЬ.^) где Ф Л3,а1 фа% - известные параметры.

Логарифм отношения правдоподобия для этих гипотез будет ? П£,/(** I Щи)) _

° ПйлЛчИД.) -

+ (2.2.1) к=» 1 *

Критерием принятия решения является сравнение максимума статистик Д, с порогом Л. Введем обозначения

-1 £14.1

, , d , "I , (Л-Л.)3 1

3 <rt + 2a>(Ai-Aiy> с\ 2+ 1а\ а\

- 1 4. ^ + ff?

Решающим правилом у пас является

й

вир St Z h W и.

За оценку момента разладки принимается f «= arg max Si

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

« = P(3i,05t<W; г,>Я|50 = О)|и,

Применив формулу для наклонного барьера из [5], получаем приближенное выражение для вероятности ложной тревоги, зависящее от порога

где а, А описаны выше.

Вероятность пропуска сигнала выписывается несколы«о сложнее:

ю

гЛ + а_Т_а0у_ц).._j__

y/2irßu\ V 2ди/ H ^ /-i

где Ф - функлкя пормальлого распределения, a,k,X,ß - ковффигщ-епты, определяемые выше по исходпым параметрам. Последшзя вероятность зависит от момента разладки и. Если для критерия качества взять паихудпшй по этому параметру вариант, а за сам функционал качества взять критерий идеального наблюдателя, то формула для выбора оптимального порога будет

а(Л) + sup ß{h, и) Д min

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

Имеются наблюдения ¡д, t = 1,2,..., которые при отсутствии разладки удовлетворяют уравнению линейной регрессии

к = «о + Д>«» + i?

Альтернативная гипотеза состоит в изменении параметров регрессии в неизвестный момент г.

( ao+ßo*i + 8, » < г Vi = {

( Cty+faXi + Q, i>r

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

11

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

Заключение.

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

1. Разработан метод существенной выборки для оценивания вероятности ошибки / рода теста отношения правдоподобия для обнаружения ограниченной во времени разладки случайного процесса. Проведено численное исследование метода существенной выборки по методу Монте-Карло.

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

3. Получены приближенные формулы для расчета вероятностей ошибок I и II родов для двухпараметрической разладки гауссов-ского случайного процесса.

4. Проведено статистическое моделирование для численного сравнения двух методов обнаружения разладки в параметрах линейной регрессии.

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