Вероятностно-статистические методы в теории принятия решений

А. Н. Ширяев

Вероятностностатистические методы 
в теории принятия 
решений

Об авторе

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

ЛЕКЦИИ ШКОЛЫ
АНАЛИЗА ДАННЫХ ЯНДЕКСА

ИЗДАНИЕ ОСУЩЕСТВЛЯЕТСЯ
ПРИ ПОДДЕРЖКЕ КОМПАНИИ «ЯНДЕКС»

ISBN 978-5-4439-0247-0

9 785443 902470 >

Вероятностно-статистические методы
А. Н. Ширяев

ЛШЯА. Н. Ширяев

Вероятностно-статистические методы
в теории принятия решений

Издание второе, новое

Москва
МЦНМО


УДК .(.)
ББК .
Ш

Ширяев А. Н.

Ш
Вероятностно-статистические методы в теории принятия
решений. — -е изд., новое. — М.: МЦНМО, . —  с.

ISBN ----

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

ББК .

Альберт Николаевич Ширяев

-Подписано в печать ... Формат 60×90 /. Бумага офсетная № .
Печать офсетная. Печ. л. . Тираж  экз. Заказ №
.

Издательство Московского центра
непрерывного математического образования.
, Москва, Большой Власьевский пер., д.. Тел. () --.

Отпечатано в ППП «Типография „Наука“».
, Москва, Шубинский пер., .

Книги издательства МЦНМО можно приобрести в магазине «Математическая книга»,
Москва, Большой Власьевский пер., д.. Тел. () --. E-mail: biblio@mccme.ru

----

© Ширяев А. Н., .
© OOO «Яндекс», .
© МЦНМО, .

Оглавление

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Вступление
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Глава 
Ключевые статистики и тесты в теории принятия решений в задачах различения двух гипотез по фиксированному числу наблюдений. Дискретное время . . . . . . . . . . . . . . . . . . . . . .


Глава 
Ключевые статистики и последовательные тесты в задачах различения двух гипотез. Дискретное время . . . . . . . . . . . . . .


Глава 
Некоторые широко используемые статистики в задаче скорейшего обнаружения момента появления разладки . . . . . . . . .


Глава 
О различении двух гипотез для броуновского движения. Сравнение методов Неймана—Пирсона и Вальда . . . . . . . . . . . . . .


Глава 
Об основных постановках задач скорейшего обнаружения изменения сноса у броуновского движения . . . . . . . . . . . . . . . .


Глава 
Система наблюдения, основанная на процедуре Вальда, в предположении появления разладки на фоне установившегося режима наблюдения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Глава 
Система наблюдения, основанная на процедуре Неймана—Пирсона, в предположении появления разладки на фоне установившегося режима наблюдения . . . . . . . . . . . . . . . . . . . . . . .


Оглавление

Глава 
Постановка задачи о разладке в байесовском варианте и ее редукция к задаче об оптимальной остановке для марковского процесса. I. Случай дискретного времени . . . . . . . . . . . . . . . . .


Глава 
Постановка задачи о разладке в байесовском варианте и ее редукция к задаче об оптимальной остановке для марковского процесса. II. Случай непрерывного времени . . . . . . . . . . . . . . .


Глава 
Решение задачи об оптимальной остановке для марковского
процесса в байесовской и условно-вариационной постановках
задач о разладке для броуновского движения . . . . . . . . . . . .


Приложение A
Важные теоремы из стохастического анализа
. . . . . . . . . . . 
A.. Некоторые общие принципы стохастического анализа . 
A.. Теорема об остановке
. . . . . . . . . . . . . . . . . . . . . . 
A.. Принцип отражения для броуновского движения . . . .

A.. Теорема Гирсанова для броуновского движения . . . . .

A.. Теорема Леви (о совместном распределении B и sup B)
и ее обобщение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A.. Прямые и обратные уравнения Колмогорова . . . . . . .

A.. Процессы Ито и формула Ито
. . . . . . . . . . . . . . . . .


Приложение B
Вероятностные свойства момента τa =inf{t ⩾0: Bt ⩾ a} . . . . . 

Приложение C
Вероятностные свойства момента σa =inf{t ⩾0: |Bt|⩾ a} . . . . 

Приложение D
Критерий согласия Колмогорова и Смирнова . . . . . . . . . . . .


Приложение E
Свойства момента τab =inf{t ⩾0: Bt − bt ⩾ a}, a >0 . . . . . . . . 

Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

Предисловие

Перед вами курс лекций Альберта Николаевича Ширяева, излагающий одну из самых замечательных теорий анализа данных —
теорию, объясняющую, как по наблюдениям за реализацией случайного процесса обнаруживать «спонтанно возникающие эффекты», когда свойства процесса изменяются скачком. Большая часть
проблем анализа данных связана с исследованием стохастических
динамических систем, и, конечно, обнаружение в них существенных, но редких событий часто имеет решающее значение. Это верно
и для анализа финансовых потоков, и для анализа данных с датчиков сейсмических станций предварительного оповещения о возможных землетрясениях, и для мониторинга динамических факторов, характеризующих изменения качества поисковой Интернетсистемы, и для слежения за сигналами жизнедеятельности больного
в палате интенсивной терапии, и для многих других приложений,
где редкие скрытые события могут принципиально изменить законы поведения рассматриваемой сложной системы. Оказывается,
можно обнаруживать и даже предугадывать такие редкие события,
и курс А. Н. Ширяева является базовым для того, кто хочет научиться это делать.
Два слова из истории. А. Н. Ширяев излагает только одну из
известных теорий анализа стохастических динамических данных.
Другие теории, как, например, теория скрытых марковских моделей
или теория обучающихся марковских сетей, также широко применяются для обнаружения редких событий. Однако среди всех этих
теорий излагаемая в настоящем курсе является наиболее теоретически обоснованной, наиболее конструктивной и наиболее востребованной на практике. Ее называли раньше теорией обнаружения
разладок в сложных системах. В настоящее время ее включают
в теорию оптимальных правил остановки, дающую возможность
строить процедуры обнаружения моментов изменения свойств про

Предисловие

цесса с минимальной задержкой и минимальным средним числом
ложных тревог.
Эта теория во многом создана автором курса, А. Н. Ширяевым,
так что читатель получает здесь ее изложение из первых рук. Отмечу сразу, что теория эта сложна даже для студентов вероятностных
специализаций. На протяжении трех лет ее преподавания в Школе
анализа данных Альберт Николаевич несколько раз менял изложение курса, стараясь сделать его максимально доступным для студентов инженерных специальностей. Настоящая книга — результат
этих поисков. И вместе с тем не следует думать, что эту книгу будет
легко изучать инженеру. Для тех, кто действительно захочет это
сделать, можно дать несколько советов:

) необходимо изучать параллельно с освоением материала этой
книги учебники А. Н. Ширяева «Вероятность-» и «Вероятность-»,
) следует иметь в виду, что книга написана очень плотно и поэтому разбирать ее надо медленно, но систематически,
) необычную роль в книге играет раздел приложений — в него
надо систематически заглядывать,
) не нужно жалеть времени на первые  страниц, где дается
«вспомогательный» материал, классические теории Неймана—Пирсона и Вальда,
) не пропускайте лекции и семинары на курсах Яндекса и активно работайте на них, а главное — если вы понимаете, что эта теория
вам нужна, будьте уверены в том, что вы ее освоите, хотя поначалу
может казаться, что это не так.

Следует отметить исключительную продуманность и ясность изложения материала. А. Н. Ширяев уделил в книге много места случаю дискретного времени. Уверен, что для инженера это наиболее
удобно и понятно, несмотря на то, что иногда вычисления, связанные с дискретностью, оказываются довольно сложными.
Еще одно замечание. Параллельно с освоением теории и методов обнаружения редких событий, читатель-инженер узнает из этой
небольшой книжки о двух фундаментальных моделях случайных
процессов — о броуновском движении и марковских процессах. Тот,
кто освоит их, получит твердую базу для своих собственных исследований в самых различных приложениях.

Предисловие
7

В заключение хочу обратиться к тем, кто смотрит на теорию
анализа данных как на теорию, доставляющую средства, которые
помогают в деле разработки новых Интернет-технологий. В настоящее время практически все наши исследования базируются на статическом статистическом анализе. Очень трудно, если вообще возможно, найти исследование процессов в Интернете, которое базировалось бы на стохастическом аппарате теории случайных процессов. Между тем, именно динамика случайности в наших системах
представляет наибольший интерес. Можно надеяться, что будущие
разработчики Яндекса, изучившие курс А. Н. Ширяева, найдут адекватные методы исследования поиска и других процессов, которые
мы разрабатываем.

И. Б. Мучник

Вступление

. Если говорить о сфере действия больших информационных
систем, к которым относится и Яндекс, то видно, что они достигли такого высокого уровня, который требует применения точных
методов мышления и, прежде всего, общематематических методов,
в частности, вероятностно-статистических.
Мы хорошо знаем, что зарождение собственно теории вероятностей было связано с желанием получить ответ на разного рода
вопросы, естественно возникающие в связи с интересом к азартным
играм. (Например, известна задача Галилея: бросаются три шестигранные кости с нанесенными на них цифрами 1, 2, …, 6; спрашивается, какова вероятность того, что сумма выпавших очков будет равна . Другими известными задачами являются задачи, возникшие
в ходе переписки Паскаля и Ферма.) Мы также знаем, что зарождение статистического мышления и статистических методов было
связано с необходимостью разрешения вопросов геодезии и астрономии. (Так, согласно первоначальному определению меры длины,
принятому во Франции, метр — это есть одна десятимиллионная
часть (1 · 10−7) четверти длины парижского географического меридиана. Тем самым, по многочисленным измерениям надо было
как можно точнее определить арифметическую величину этой четверти меридиана.) Именно в связи с этими геодезическими, а также астрономическими запросами (определение параметров орбит
планет и комет) возник метод наименьших квадратов (Лежандр,
Лаплас), начала строиться количественная технология обработки
эмпирических данных, стали вырабатываться логика и методология
измерений в условиях неопределенности, создаваться «исчисление
наблюдаемых данных». (В связи со сказанным, было бы хорошо
иметь в рамках Школы по анализу данных специальный курс относительно таких базисных идей математической статистики, как метод наименьших квадратов, метод максимального правдоподобия,
байесовский метод, непараметрическая статистика, … Для наилуч

Вступление
9

шего понимания всего этого полезно было бы вести изложение этого предмета в его историческом развитии.)
. Настоящий курс посвящен изложению некоторых современных методов теории принятия решений в условиях неопределенности, нацеленных на решение конкретных задач общего интереса,
возникающих при динамическом анализе (в режиме реального времени) статистических данных, получаемых, например, в финансовой инженерии, в теории обнаружения сигналов на фоне помех, …
Для большинства информационных систем весьма актуальна разработка методов успешного обнаружения нежелательных внедрений
в информационные системы («network intrusions») и методов создания систем защиты от кибер-атак («cyber-terrorism»).
. В литературе описаны разнообразные методы обнаружения
нежелательных «внедрений», основанные на технике «искусственного интеллекта», включая экспертные системы, нейронные сети,
«pattern matching», и др. []. Существующие системы обнаружения
«внедрений» (IDS — Intrusion Detection Systems) обычно классифицируются или как Signature Detection Systems, или как Anomaly
Detection Systems [], [].
Signature Detection Systems обнаруживают атаки путем сравнения наблюдаемых шаблонов (pattern) сетевого трафика с известными образцами (signature) атак, хранящимися в базе данных [].
Мы уделяем значительное время изложению второго метода
обнаружения, основанного на Anomaly Detection Systems. Обычно,
внедрение в сети (например, Denial-of-Service [DOS] attacks, Address
Resolution Protocol Men-in-the-Middle [ARP MiM] attacks, …) происходит в неизвестный заранее момент времени θ и сопровождается изменением вероятностно-статистических свойств некоторых
характеристик наблюдаемого процесса (например, количества отправленных и принятых сервером пакетов). Поэтому естественно возникает идея математически сформулировать задачу обнаружения атаки как задачу («θ-задачу») скорейшего обнаружения
момента (θ) появления разладки в ходе наблюдаемого процесса.
Наша цель будет состоять в том, чтобы, начиная с простых моделей

 Есть несколько, уже давно изданных, классических книг, посвященных теории
принятия решений. Отметим в первую очередь монографии [], [].

Вступление

и затем переходя к более сложным, изложить те методы скорейшего обнаружения, которым уделялось и поныне уделяется большое
внимание.
Наряду с моментом θ появления разладки важной характеристикой рассматриваемых систем будет момент подачи тревоги, который мы обозначаем через τ. Этот момент должен строиться по прошлым данным, т. е. быть моментом «без упреждения». Такие моменты называются моментами остановки или марковскими моментами
(точное определение будет приведено ниже). Стремиться мы будем
к тому, чтобы минимизировать (в некотором усредненном смысле)
время запаздывания τ − θ в обнаружении момента θ (когда τ ⩾ θ)
при соблюдении условия, что ложное обнаружение (когда τ < θ)
имеет малую вероятность.
Основным аппаратом решения таких задач является «последовательный анализ принятия решений». Такие задачи, как мы увидим, удобно формулировать как задачи об оптимальной остановке.
Первые задачи такого типа были рассмотрены еще в сороковых годах А. Вальдом в рамках теории последовательного различения двух
(а также многих) статистических гипотез. К настоящему времени
теория оптимальных правил остановки получила значительное развитие. Основной литературой для нас будут книги [], [].
. Мы рекомендуем читателям хотя бы бегло ознакомиться с книгами [], [], являвшимися, в сущности, первыми переводами на
русский язык книг по вопросам принятия решений, применениям
к теории игр, экономике, исследованию операций. Математические методы во многом были основаны на новых тогда методах
линейного программирования. Возникшие затем методы динамического программирования (Р. Беллман), истоками которого были работы по последовательному анализу А. Вальда, Д. Блекуэлла,
М. А. Гиршика и др., дали возможность исследовать динамические
постановки задач типа задач оптимального управления.
Рассматриваемые нами методы решения задач скорейшего обнаружения в значительной мере опираются на современный аппарат теории случайных процессов, стохастического исчисления, теории мартингалов, нелинейной фильтрации и т. д. Хотелось бы подчеркнуть, что многие эти теоретические методы были выработаны
именно на пути решения задач скорейшего обнаружения. Это слу

Вступление
11

жит хорошей иллюстрацией того, как происходит развитие теории,
когда она нацелена на решение конкретных задач, имеющих практический интерес.
В небольшой статье [] Клод Шеннон, говоря о теории информации, подчеркивает, что хотя она и «является сильнейшим средством
решения проблем теории связи (и в этом отношении ее значение
будет возрастать), нельзя забывать, что она не является панацеей
для инженера-связиста и тем более для представителей всех других специальностей. Очень редко удается открыть одновременно
несколько тайн природы одним и тем же ключом».
Мы приводим эти слова с тем, чтобы подчеркнуть, что излагаемые нами постановки задач и известные методы их решения должны побуждать читателей на формулирование новых задач, в том
числе непосредственно интересных для Яндекса, для решения которых будут найдены новые подходы, стимулирующие развитие и собственно теоретических исследований.
Автор приносит свою благодарность руководству Яндекса и профессору И. Б. Мучнику за приглашение прочитать курс лекций, многочисленные советы и поддержку. Большая помощь при подготовке
рукописи к печати была оказана автору Е. В. Бурнаевым.