ДОПОЛНЕНИЕ 1

Б.Е.Бродский, Б.С.Дарховский
МЕТОДЫ ОБНАРУЖЕНИЯ "РАЗЛАДКИ" СЛУЧАЙНЫХ ПРОЦЕССОВ
И ИХ ПРИМЕНЕНИЕ ДЛЯ АНАЛИЗА ИСТОРИЧЕСКИХ ТЕКСТОВ

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

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

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

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

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

Первое. Пусть предъявлена выборка (реализация) случайного процесса (поля). Всякая статистическая обработка этой выборки с целью построения модели, оценки параметров и т.п. основана на предположении (оно лежит в основе математической статистики), что оцениваемый феномен в процессе сбора данных не изменялся. Поэтому предварительным этапом любой статистической обработки должен быть этап проверки подобной однородности. Таким образом, вопрос здесь ставится так; является ли предъявленная выборка статистически однородной в смысле неизменности своих вероятностных характеристик? Если ответ на этот вопрос положителен, то далее следует заниматься обычной статистической обработкой в зависимости от тех целей, которые ставит исследователь. Если же ответ отрицателен, то возникает задача обнаружения моментов изменения вероятностных характеристик и разбиения исходной выборки на несколько статистически однородных кусков.

Описанный класс задач получил название ретроспективных (апостериорных) задач о "разладке" ("разладка" - краткий термин для любого изменения вероятностных характеристик).

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

Первые работы в указанной области были опубликованы еще в 30-х годах (см.ссылку в [539] на работу Шьюхарта, посвященную задаче скорейшего обнаружения). Однако, строгой теории тогда построено не было. В 50-х годах появились работы Пейджа [540], [541], где был предложен метод обнаружения "разладки" как в ретроспективном, так и в скорейшем варианте. Этот метод, получивший впоследствии название метода кумулятивных сумм, и основанный на последовательном вычислении функции правдоподобия, оказался удобным с точки зрения организации расчетов и практически эффективным. Примерно в это же время А.Н.Колмогоров дал строгую постановку задачи о скорейшем обнаружении момента "разладки" для винеровского процесса, сформулировав ее как некоторую вероятностную экстремальную проблему. Эта проблема была решена А.Н.Ширяевым, который нашел в указанной ситуации оптимальный метод обнаружения. Итог исследованиям А.Н.Ширяева в этой области подведен в книге [542].

Интерес к проблематике задач о "разладке" стал возрастать с середины 60-х годов, что вызывалось потребностями приложений. При этом основные усилия исследователей направлялись на то, чтобы разработать методы, использующие как можно меньше априорной информации. Дело в том, что оптимальные и близкие к ним методы основаны на точном знании функций распределения до и после момента "разладки" и функции распределения момента "разладки" (если он случаен). Такую информацию трудно получить во многих интересных практических приложениях. В связи с этим обстоятельством стали развиваться минимаксные методы (позволяющие избавиться от информации о функции распределения момента "разладки") и непараметрические методы, позволяющие отказаться от информации о рапсределениях случайной последовательности. Большие обзоры работ по этой проблематике за последние 15-20 лет содержатся в работах [543]-[545].

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

Итог нашим исследованиям в рассматриваемой области математической статистики подведен в книге [546]. Здесь мы изложим основные идеи нашего подхода применительно к ретроспективным методам обнаружения "разладки", т.к. именно эти методы использовались для анализа исторических текстов.

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

X = {x_t}^N_t=1,

"склеенная" из двух строго стационарных случайных последовательностей

X₁ = {x_t}^n*_t=1, X = {x_t}^N_t=n*+1,

где n* = [θN], 0 < θ < 1, и требуется оценить точку склейки n.

Пусть известно, что X₁ и X₂ отличаются между собой одной из двумерных функций распределения, а именно, предположим, что функция P{x_t ≤ u₀, x_t+2 ≤ u₁} = F(u₀,u₁) до момента t^*₁ = n* - 2 равна F₁(·), а при t ≥ t^*₂ равна n*+1–F(·), причем ||F₁(·)–F₂(·)|| ≥ ε > 0, где || · || -обычная sup-норма. Хорошо известно, что функция распределения конечномерного случайного вектора может быть приближена равномерно с любой точностью функцией распределения случайного вектора с конечным числом значений. Отсюда следует, что при разбиении плоскости R на достаточно большое число непересекающихся областей A_j, j=1,...,r, вектор (x_t,x_t+2) можно аппроксимировать по распределению вектором с конечным числом значений. Поэтому, если ввести новые случайные последовательности

V_t^ij = I(x _Î A_i, x_t+2 Î A_j), 1 ≤ i ≤ r, 1 ≤ j ≤ r,

(I(A) - индикатор множества А), то хотя бы в одной из этих последовательностей происходит изменение математического ожидания. Следовательно, если существует алгоритм, обнаруживающий изменение математического ожидания, то этот же алгоритм обнаружит и изменение функции распределения. Аналогично можно обнаружить и изменение произвольной вероятностной характеристики. Например, если в последовательности меняется корреляционная функция, то рассматривая новые последовательности V_t(t ) = x_tx_t+t , t =0,1,2,..., мы сведем задачу к обнаружению изменения математического ожидания в одной из последовательностей V_t(t ).

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

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

(1) - ,

где 0 ≤ d ≤ 1, 1 ≤ n ≤ N-1, X={x_k}^N_k=1 - исследуемая реализация, и некоторых производных от этих статистик.

Семейство (1) представляет собой обобщенный вариант статистики Колмогорова-Смирнова, которая используется для проверки совпадения или различия функций распределения у двух выборок (при фиксированном n). Можно показать, что статистики вида (1) асимптотически (при N ® ¥ и сохранении соотношения между объемами "склеенных" реализаций) минимаксны (т.е. минимизируют максимально возможную вероятность ошибки оценивания момента "разладки") по порядку.

Указанные идеи (подробнее см.[546]) воплощены в комплексе прикладных программ VERDIA для персональной ЭВМ типа IBM PC. Этот комплекс позволяет в диалоговом режиме обнаруживать "разладки" произвольной случайной последовательности. При помощи комплекса VERDIA нами был проведен анализ ряда конкретных исторических текстов. Результаты этого анализа изложены в Дополнении 2 к настоящей книге.

_