Описанный класс задач получил название ретроспективных (апостериорных) задач о «разладке». Поясним, что «разладка» — это краткий термин для любого изменения вероятностных характеристик.
ВТОРОЙ класс проблем описывается следующим образом. Пусть информация о случайном процессе (его измерение) поступает последовательно во времени. Допустим, что в некоторый, заранее неизвестный, момент происходит изменение какой-либо вероятностной характеристики процесса (в общем случае, какой-либо функции распределения). Спрашивается, как обнаружить произошедшее изменение скорейшим образом после того, как оно возникло (ясно, что сделать это заранее — «предсказать будущее» — в принципе нельзя), но так, чтобы при этом ложные сигналы тревоги не были слишком частыми. Частота таких сигналов может быть ограничена заданной величиной. Эта задача получила название задачи о скорейшем обнаружении «разладки».
Первые работы в указанной области были опубликованы еще в 30-х годах. См. описание в [1111] работы Шьюхарта, посвященной задаче скорейшего обнаружения. Однако, строгой теории тогда построено не было. В 50-х годах появились работы Пейджа [1325], [1326], где предложен метод обнаружения «разладки» как в ретроспективном, так и в скорейшем варианте. Этот метод, получивший впоследствии название метода кумулятивных сумм, и основанный на последовательном вычислении функции правдоподобия, оказался удобным с точки зрения организации расчетов и практически эффективным. Примерно в это же время А.Н. Колмогоров дал строгую постановку задачи о скорейшем обнаружении момента «разлуки» для винеровского процесса, сформулировав ее как некоторую вероятностную экстремальную проблему. Эта проблема решена А.Н. Ширяевым, который нашел в указанной ситуации оптимальный метод обнаружения. Итог исследованиям А.Н. Ширяева в этой области подведен в книге [976].
Интерес к проблематике задач о «разладке» стал возрастать с середины 60-х годов, что вызывалось потребностями приложений. При этом основные усилия исследователей направлялись на то, чтобы разработать методы, использующие как можно меньше априорной информации. Дело в том, что оптимальные и близкие к ним методы основаны на точном знании функций распределения до и после момента «разладки» и функции распределения момента «разладки» (если он случаен). Такую информацию трудно получить во многих интересных практических приложениях. В связи с этим обстоятельством стали развиваться минимаксные методы (позволяющие избавиться от информации о функции распределения момента «разладки») и непараметрические методы, позволяющие отказаться от информации о распределениях случайной последовательности. Большие обзоры работ по этой проблематике за последние 15–20 лет содержатся в работах [392], [1406], [1230].
Работы авторов настоящей работы были в числе первых исследований в области непараметрических методов решения задач о «разладке». С самого начала мы стремились синтезировать такие методы, которые можно достаточно легко применять для решения практических задач. В этом отношении именно непараметрические методы, не использующие априорную информацию о распределениях, представляются наиболее подходящими.
Итог нашим исследованиям в рассматриваемой области математической статистики подведен в книге [1051]. Здесь мы изложим основные идеи нашего подхода применительно к ретроспективным методам обнаружения «разладки», так как именно эти методы использовались для анализа исторических текстов.
Наша методология основана на двух основных идеях. Первая состоит в том, что обнаружение изменения любой функции распределения или какой-либо иной вероятностной характеристики может быть (с любой степенью точности) сведено к обнаружению изменения математического ожидания в некоторой новой случайной последовательности, сформированной из исходной. Поясним это положение на следующем примере. Пусть анализируется случайная последовательность
«склеенная» из двух строго стационарных случайных последовательностей
n* = [θN], 0<θ<1, и требуется оценить точку склейки n*.
Пусть известно, что Х1 и Х2 отличаются между собой одной из двумерных функций распределения, а именно, предположим, что функция Р{ хt ≤ u0, хt+2 ≤ u1} = F(u0, u1) до момента = t1*-2 равна F1(), а при t ≤ t2* = n*+1-F2(), причем ||F1()-F2()||≥ε>0, где |||| — обычная sup-норма. Хорошо известно, что функция распределения конечномерного случайного вектора может быть приближена равномерно с любой точностью функцией распределения случайного вектора с конечным числом значений. Отсюда следует, что при разбиении плоскости R на достаточно большое число непересекающихся областей Aj, j = 1…., r, вектор (хt, хt+2) можно аппроксимировать по распределению вектором с конечным числом значений. Поэтому, если ввести новые случайные последовательности Vyt = I(xt ε A, xt+2 ε Aj), 1 ≤ i ≤ r, 1 ≤ j ≤ r (I(А) — индикатор множества А, то хотя бы в одной из этих последовательностей происходит изменение математического ожидания. Следовательно, если существует алгоритм, обнаруживающий изменение математического ожидания, то этот же алгоритм обнаружит и изменение функции распределения. Аналогично можно обнаружить и изменение произвольной вероятностной характеристики. Например, если в последовательности меняется корреляционная функция, то рассматривая новые последовательности Vt(τ) = ХtХt+τ, τ = 0, 1, 2…, мы сведем задачу к обнаружению изменения математического ожидания в одной из последовательностей Vt(τ).
Указанное обстоятельство позволяет ограничиться разработкой только одного, базового, алгоритма, который может обнаруживать изменение математического ожидания, а не создавать (вообще говоря, бесконечное) семейство алгоритмов для обнаружения изменений тех или иных вероятностных характеристик.
Вторая идея нашего подхода заключается в использовании для обнаружения моментов «разладок» семейства статистик вида
где 0 ≤ δ ≤ 1, 1 ≤ n ≤ N—1, Х = {хк}Nk=1 — исследуемая реализация, и некоторых производных от этих статистик.
Семейство (1) представляет собой обобщенный вариант статистики Колмогорова-Смирнова, которая используется для проверки совпадения или различия функций распределения у двух выборок (при фиксированном n). Можно показать, что статистики вида (1) асимптотически (при N → и сохранении соотношения между объемами «склеенных» реализаций) минимаксны (т. е. минимизируют максимально возможную вероятность ошибки оценивания момента «разладки») по порядку.
Указанные идеи — подробнее см. [1051] — воплощены в комплексе прикладных программ VERDIA для персональной ЭВМ типа IBM-PC. Этот комплекс позволяет в диалоговом режиме обнаруживать «разладки» произвольной случайной последовательности. При помощи комплекса VERDIA нами был проведен анализ ряда конкретных исторических текстов. Результаты этого анализа изложены в следующем Дополнении 2 к настоящей книге.
Дополнение 2Выявление однородных и неоднородных фрагментов внутри русских летописей, римских и греческих хроник, в Библии
В данном разделе цитируются фрагменты работы Б.Е. Бродского, Б.С. Дарховского, Г.В. Носовского, А.Т. Фоменко.
1. Введение
В современной математической статистике большое применение нашел важный метод разладки, созданный А.Н. Ширяевым. В настоящей работе кратко описываются результаты интересного численного эксперимента, идея которого впервые предложена А.Н. Ширяевым и А.Т. Фоменко. Эта идея и эксперимент обсуждались на научно-исследовательском семинаре «Геометрия и статистика», несколько лет работавшем под руководством А.Т. Фоменко и А.Н. Ширяева в математическом ин-те им. В.А. Стеклова АН СССР. Цель эксперимента — применить метод разладки к важной задаче выявления, распознавания «однородных кусков» внутри достаточно больших исторических текстов. К таким текстам относятся, в частности, исторические хроники, летописи и т. п. Теоретические основы метода разладки см. в статье Б.Е. Бродского и B.C. Дарховского, помещенного в настоящей книге как Дополнение 1.
Выявление информативных количественных характеристик текстов и предварительная обработка исторических текстов, в частности, русских летописей и исторических книг Библии, были выполнены Г.В. Носовским и А.Т. Фоменко. Статистический анализ и компьютерный эксперимент затем проведены Б.С. Дарховским и Б.Е. Бродским. Большую помощь при этом нам оказали Т. Толозова, А. Громова и Л. Мищенко.
Напомним постановку задачи. Многие исторические источники составлены из фрагментов разной природы. Эти отдельные куски могли быть написаны в разное время разными авторами и вообще в разных странах. Затем отдельные фрагменты были объединены каким-то более поздним летописцем в одну книгу. Они начинали существовать, «спаянные» в единое целое внутри какой-то одной поздней летописи. При многократной ее переписке, при редакторских изменениях, внешние различия, существовавшие первоначально между старыми фрагментами, составляющими «новый большой текст», постепенно стирались. Сегодня такие составные тексты часто воспринимаются как единое целое, поскольку предыстория их возникновения давно забыта.