Марковские цепи на разбиениях и бесконечномерные диффузионные процессы тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Петров, Леонид Александрович

• Петров, Леонид Александрович
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Петров, Леонид Александрович

Введение

Глава 1. Диффузии и распределения Пуассона-Дирихле.

1.1. Распределения Пуассона-Дирихле и модель Морана.

1.2. Марковские цепи на разбиениях и симметрические функции

1.3. Построение и свойства предельного процесса.

Глава 2. Марковские цепи на строгих разбиениях.

2.1. Строгие разбиения и перемежающиеся координаты.

2.2. Вычисление в алгебре дважды симметрических функций

2.3. Сходимость марковских цепей на строгих разбиениях.

Введение диссертации (часть автореферата) на тему «Марковские цепи на разбиениях и бесконечномерные диффузионные процессы»

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

Теория машинного обучения изучает методы построения и анализа алгоритмов, способных обучаться в процессе своей работы. К области машинного обучения без учителя относятся алгоритмы, в ходе выполнения которых система спонтанно обучается выполнять поставленную задачу без вмешательства со стороны экспериментатора. Общие сведения о задачах машинного обучения см. в книгах [1], [9], [57]. В последние несколько лет в области машинного обучения без учителя активно развиваются методы анализа и классификации по темам большого корпуса текстов на естественном языке, основанные на непараметрических байесовских моделях (см., например, работы [32], [61], [89], [66], [29], а также обширную библиографию в последней работе). Многие вероятностные модели, рассматриваемые в связи с этими задачами, основаны на распределениях Пуассона-Дирихле.

Вероятностные распределения Пуассона-Дирихле PD(a,0) зависят от двух параметров 0 ( а < 1 и 0 > -а и описывают закон распределения последовательности невозрастающих неотрицательных случайных величин (Xl, Х2,. ■ ■ ), таких, что Х\ ^ Хч ^ . ^ 0 и = 1. В исследование распределений Пуассона-Дирихле внесли вклад Бертуан, Биллингсли, Бли-новский, Вершик, Гончаров, Гримметт, Гриффите, Дикман, Доннелли, Игнатов, Йор, Карлтон, Керов, Куртц, Кингман, Ллойд, Ольшанский, Питман, Уоттерсон, Цилевич, Шепп, Шмидт, Этье, Ювенс, и другие. Однопарамет-рическое семейство распределений Пуассона-Дирихле PD(0,0) (соответствующее случаю а = 0) было введено Кингманом [69] в связи с задачами, возникающими в популяционной генетике. Двухпараметрическое обобщение принадлежит Питману [76]. О мотивации введения второго параметра в распределения Пуассона-Дирихле, а также о свойствах двухпараметри-ческих распределений PD(a,#) см. работу Питмана и Йора [79]. Семейство распределений Пуассона-Дирихле является одним из фундаментальных законов в теории вероятностей и теории случайных процессов. Более подробно об этих распределениях см. книгу Питмана [78] и недавнюю монографию Фенга [52], в которой описаны некоторые популяционно-гене-тические модели, приводящие к мерам Пуассона-Дирихле. О различных популяционно-генетических моделях см. также [49], [70], [51], [46] й главу 10 книги [47]. Стоит отметить, что распределения Пуассона-Дирихле также используются в комбинаторике [78], теории чисел [39], [8], [27], [7], [40], математической физике [36], [37], Существуют экономико-математические модели, приводящие к распределениям Пуассона-Дирихле [24].

Модели машинного обучения, основанные на распределениях Пуассона-Дирихле, существенно используют специфику второго параметра а. Это связано с тем, что случайные величины в последовательности, имеющей распределение Пуассона-Дирихле PD(a;,#), ПРИ cl = 0 с вероятностью единица убывают показательным образом, а при а Ф 0 — степенным образом; как известно, для естественных языков' характерно степенное убывание частот (см., например, работу Шрейдера [21]). Опишем одну из общих постановок задач классификации в теории машинного обучения. Пусть задано конечное множество слов, называемое словарем. Вероятностное распределение на этом множестве слов называется темой (англ. topic). Текст — это некоторая последовательность слов, а набор текстов принято называть корпусом. На вход алгоритма классификации подается некоторый (обычно весьма большой) корпус текстов. В качестве корпуса текстов, подаваемого на вход, может, например, выступать набор аннотаций к статьям в некотором научном журнале, или подшивка новостных газетных материалов за определенный период времени. Различают статическую и динамическую постановку задачи классификации. В статистической задаче классификации все тексты входного корпуса рассматриваются как равноправные, и задача алгоритма классификации состоит в выборе тем и расположении текстов по темам так, чтобы это наилучшим образом соответствовало входным данным. В динамической задачи классификации постановке каждому тексту корпуса приписывается определенная временная отметка (время выхода журнала или газетного материала в примерах, приведенных выше). Помимо распределения текстов по темам, в задачу алгоритма классификации при динамической постановке входит отслеживание зависимости распределения тем от времени. Статические задачи классификации исследовались в уже упомянутых работах [32], [61], [89], [66], [29]. Исследованию некоторых динамических задач классификации посвящены работы [30], [31], [91].

В теории машинного обучения в статических и динамических задачах классификации в основном используется непараметрический байесовский подход, который состоит в следующем. Сначала строится априорная модель, которая порождает случайный корпус текстов с заданными свойствами. Затем по входному корпусу текстов вычисляется (а чаще моделируется, так как явно вычислить не удается) апостериорное распределение при заданных входных данных, по которому уже строится искомый набор тем и распределение текстов по темам, другими словами, производится статистический вывод. Априорная модель здесь зависит от некоторых параметров, которые обычно принадлежат бесконечномерному пространству (например, в качестве параметров модели могут выступать вероятностные распределения на прямой или на множестве натуральных чисел). Применение методов параметрической байесовской статистики в данной ситуации невозможно, поэтому используются другие подходы, называемые непараметрическими. О непараметрической байесовской статистике см., например, книги [38], [60]. Изучение (и в-некоторых случаях явное вычисление) апостериорных распределений, связанных с распределениями Пуассона-Дирихле PD(a, в), проводилось в работах Фергюсона [54], Антоняка [23], Блэкуэлла и Мак-Куина [28], Питмана [77]. Первые три работы рассматривают однопара-метрический случай, а четвертая работа посвящена двухпараметрическим распределениям Пуассона-Дирихле. Важные задачи статистического оценивания и проверки гипотез, связанные с двухпараметрическими распределениями Пуассона-Дирихле, исследовались в диссертации Карлтона [34]. Близкие проблемы исследовались также в работах [64], [65].

Опишем простейшую процедуру построения одного случайного текста на основе распределения Пуассона-Дирихле PD(o:, в). Данный пример представляет собой упрощенный частный случай иерархической модели классификации из работы [29]. Для анализа реальных данных требуются гораздо более сложные априорные модели, также основанные на распределениях Пуассона-Дирихле (см., например, библиографию в работе [29]). Зададим длину текста N € N := {1,2,.} (впоследствии N можно также рандомизировать, например, с помощью распределения Пуассона). Выберем последовательность величин (Х\,Х2,. ■.), где Х± ^ Хч ^ . ^ 0 и Y^i Xi = 1, из распределения PD(a, 9). Набор (Xi, Х2,.) можно рассматривать как вероятностное распределение на натуральных числах N, которое приписывает вероятность Х^ числу к. Предположим, что для каждого натурального к задан закон распределения темы (обозначим его через Topic(fc)) на множестве всех допустимых тем. Теперь для кажого г = 1,.N выберем случайно число кг из распределения (Xi,Xo, ■ ■ ■) на множестве N. Затем выберем тему из распределения Topic(ki). Наконец, по теме Topic(ki) случайно выберем слово из нашего словаря. Это и будет слово номер г в нашем построенном случайном тексте. Таким образом будет построен весь случайный текст длины N. Статистический вывод в этой ситуации (то есть, результат, работы алгоритма классификации) представляет собой некоторый набор тем, которым лучше всего отвечает поданный на вход текст. Видно, что использование распределения Пуассона-Дирихле позволяет не ограничивать заранее число возможных тем в тексте. Также отметим, что текст строится последовательно, что позволяет добавлять новые данные после статистической обработки уже имеющихся.

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

Динамические модели, связанные с однопараметрическим семейством распределений Пуассона-Дирихле PD(0, в), широко изучались в контексте популяционной генетики. Изучение динамических моделей в популяцион-ной генетике началось с дискретных моделей Райта-Фишера (рассматривалась, начиная с 1920-30-х гг.) и Морана (была введена в 1950-е гг.). О различных дискретных моделях популяционной генетики см. работы [71], [50], [92], §3 работы [46], главу 10 книги [47], а также книгу [52]. Дискретные модели Райта-Фишера и Морана можно трактовать как последовательности марковских цепей на разбиениях (пространство состояний п-й цепи есть множество всех разбиений числа п).

Разбиения — фундаментальный математический объект. Основные сведения о них можно найти, например, в книгах Стенли [19] и Фултона [20]. Разбиения широко применяются в теоретической информатике, например, в различных методах сортировки (в частности, при сортировке слияниями), которым посвящена фундаментальная монография Кнута [13]. В контексте алгебраической комбинаторики разбиения изучаются в книге Макдональда [14].

Предельное поведение некоторых классов моделей Райта-Фишера и Морана исследовано в работе Этье и Куртца [46], в которой построено семейство бесконечномерных диффузионных процессов, сохраняющих од-нопараметрические распределения Пуассона-Дирихле PD(0,в). Под бесконечномерным диффузионным процессом понимается строго марковский процесс с непрерывными траекториями на бесконечномерном компактном или локально компактном пространстве состояний. Построенные в [46] процессы исследовались и обобщались в работах, принадлежащих Вио, Доннелли, Гриффитсу, Куртцу, Таваре, Уоттерсону, Флемингу, Шмуланду,

Этье, и другим. Более подробно об этих процессах и их различных обобщениях см. главу 10 книги [47], а также работы [55], [41], [43], [83], [44], [45] [48].

Этье и Куртц строили бесконечномерные диффузионные процессы, сохраняющие распределения PD(O,0), с помощью их аппроксимации конечномерными диффузиями на симплексах растущей размерности. Данный метод неприменим в случае двухпараметрических распределений Пуассона-Дирихле PD(a. (9). Поэтому для построения бесконечномерных диффузий, обобщающих процессы Этье-Куртца [46] на двухпараметрический случай, требуется применение других методов.

В диссертации найдена алгебро-комбинаторная интерпретация модели Морана на разбиениях, которая позволяет обобщить эту модель на двухпараметрический случай, а также построить диффузии, сохраняющие двухпа-раметрические распределения Пуассона-Дирихле. Данная интерпретация включает модель Морана (и её двухпараметрическое обобщение) в широкий класс марковских цепей на разбиениях, рассматриваемый Фульманом, Бородиным и Ольшанским [58], [59], [33], [75]. Возникает вопрос об анализе асимптотического поведения других марковских цепей на разбиениях, входящих в этот класс. Проводится исследование одного семейства марковских цепей из этого класса на строгих разбиениях (то есть, разбиениях, все части которых различны).

О некоторых приложениях строгих разбиений в теоретической информатике (в задачах сортировки) см., например, монографию Кнута [13]. Соответствие Робинсона-Шенстеда-Кнута для обычных разбиений (описанное, например, в книгах [20], [13]) обобщается и на случай строгих разбиений [93], [82]. Это комбинаторное соответствие делает возможным применение различных ансамблей случайных разбиений в задачах, связанных со случайными матрицами, а также в теории массового обслуживания (см., например, работы [25], [42]). Комбинаторные свойства строгих разбиений изучались также в [80]. Важные асимптотические задачи, связанные со случайными строгими и обычными разбиениями (в частности, нахождение предельных форм случайных диаграмм), исследовались в работах [63], [2], [22], [35], [3], [4].

Модель марковских цепей на строгих разбиениях возникает в связи с ансамблем случайных строгих разбиений, введенном Бородиным [5]. Этот ансамбль связан с теорией проективных представлений симметрических групп, начало которой положила работа Шура [84]. Теория проективных представлений симметрических групп (включая асимптотические вопросы) развивалась в работах Иванова [10], Назарова [15], [73], [74], Сергеева [85], Стембриджа [87], и других . См. также книгу [62].

Стоит отметить, что ансамбль случайных строгих разбиений [5] приводит к новым моделям точечных процессов, которые отличаются от традиционно рассматриваемых в статистической физике (об этих моделях см., например, книгу Форрестера [56]). Изучение предельного поведения ^указанных марковских цепей на строгих разбиениях позволяет построить новые примеры бесконечномерных диффузионных процессов.

Первая глава диссертации посвящена построению и исследованию семейства бесконечномерных диффузионных процессов, сохраняющих двух-параметрические распределения Пуассона-Дирихле PD(cn,0).

В первом параграфе приводятся необходимые сведения о разбиениях и распределениях Пуассона-Дирихле. Приводится определение модели Морана на разбиениях и дается ее алгебро-комбинаторная интерпретация, а также вводится двухпараметрический аналог модели Морана. Обозначим через Тп (п е N) переходный оператор марковской цепи на множестве разбиений числа 72, которая является двухпараметрическим обобщением модели Морана. Оператор Тп зависит от параметров 0^а<1и#> -а.

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

В третьем параграфе строится и исследуется двухпараметрическое семейство бесконечномерных марковских процессов с непрерывным временем Xa$(t), которые являются пределами марковских цепей Тп при п -> оо (точный смысл сходимости пояснен ниже в теореме 1.3.9). Опишем пространство состояний процессов X^it). Распределения Пуассона-Дирихле PD(a, 0) описывают закон распределения последовательности невоз-растающих неотрицательных случайных величин (Xi,X2,. ■), таких, что Xi ^ Х2 > . . Z 0 и Y.'jti Х{ = 1. Другими словами, распределения PD(a, в) можно рассматривать как вероятностные меры на множестве Е := {(xi,x2,. ):xi ^ х2 > . ^ 0, Е^х* = l}.

Рассматриваемое как подмножество куба [0,1]°° с топологией покоординатной сходимости, пространство Е не является замкнутым. Удобно рассматривать замыкание пространства Е в этой топологии, а именно, пространство := {(хьх2,. ):х! ^ Х2 ^ . > 0, < l}. (0.1)

Таким образом, подмножество Е с Е плотно в Е. В топологии покоординатной сходимости, наследуемой из [0,1]°°, множество Е с [0,1]00 является компактным, метризуемым и сепарабельным топологическим пространством. Мы будем называть пространство Е (бесконечномерным) симплексом. Этот симплекс и выступает в качестве пространства состояний процессов Xafi{t).

Чтобы описать основные свойства процессов Xa>g(t), требуется дать некоторые определения. Через С(Е) обозначим банахову алгебру всех непрерывных функций на Е с поточечными операциями и супремум-нормой. Рассмотрим плотную подалгебру Т с С(Е), порожденную (как коммутативная алгебра с единицей) алгебраически независимыми функциями q&(x) := Е^хИ, к б N, х € Е. Отметим, что функция Y,T=i хг не является непрерывной на Е. Рассмотрим оператор А.Т -> Т, зависящий от параметров а и 9, который может быть записан как формальный дифференциальный оператор второго порядка в коммутативной алгебре полиномов от qi, q2,.: оо Q2 i,j=1 iu4j оо Q £ [-(« + 1)(г + в)Цг + (г + 1)(г - a)qi-i] тт", q0 == 1, г=1 ОС\г а также как дифференциальный оператор в естественных координатах:

ОО Q2 оО Q2 оо Q

А = - Е -+ о-- (0.2) г=1 аХг ij=l ОХгОХ0 -=1 СХг

Оператор Л, записанный в естественных координатах, может применяться только к функциям д € Т'. Чтобы применить его к такой функции, следует сначала вычислить Ад(х) для х е Е (такие х составляют плотное подмножество в Е) путем применения правой части формулы (0.2) к функции д(х) напрямую, а затем продолжить полученную функцию на весь симплекс Е по непрерывности.

Основные свойства процессов Xa>g(t), которые устанавливаются в третьем параграфе, состоят в следующем:

• Для каждой пары параметров 0 ^ а < 1 и в > -а оператор А\Т Т замыкаем в С(Е) и порождает бесконечномерный диффузионный процесс Xate{t) на Е. Оператор А-Т Т называется предгенератором процесса Xa>g(t).

• Процесс Xaj)(t) сохраняет меру Пуассона-Дирихле PD(cv, 0), обратим и эргодичен относительно нее.

• Траектории процесса Xa>g(t) непрерывны с вероятностью единица.

• Конечные марковские цепи Тп на разбиениях (двухпараметрическое обобщение модели Морана) при п оо сходятся к процессу Xate(t). Точная формулировка этой сходимости приведена в теореме 1.3.9 ниже.

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

В первом параграфе приводится определение и основные свойства ансамбля случайных строгих разбиений (зависящего от параметра а > 0), введенного в работе [5]. Определяются марковские цепи на строгих разбиениях, связанные с указанным ансамблем. Используемая при определении этих марковских цепей алгебро-комбинаторная конструкция аналогична той, что была использована при исследовании модели Морана и ее двух-параметрического обобщения. Кроме того, в первом параграфе вводятся новые координаты для строгих разбиений, называемые перемежающимися координатами Керова, и исследуются их комбинаторные свойства. Эти координаты позволяют значительно уменьшить технические трудности, возникающие при исследовании построенных марковских цепей на строгих разбиениях.

Во втором параграфе вычисляется действие переходных операторов построенных марковских цепей на дважды симметрические функции от компонент разбиений. Функция /(Ai, А2,.) называется дважды симметрической, если она симметрична по Ai, А2,., и кроме того, для всех 1 ^ г < j функция 7(АЬ ., г,., -z,.) (z стоит на г-м месте, a (-z) — на j-м) не зависит от z. Здесь Ai > А2 > • • • > 0 — компоненты строгого разбиения. При вычислении действия переходный операторов используются полученные в первом параграфе комбинаторные свойства координат Керова строгих разбиений.

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

Пространство состояний марковских процессов Xa(t) — бесконечномерный симплекс Е. Как pi в первой главе, бесконечномерный диффузионный процесс Xa(t) на Е удобно описывать в терминах его предгенератора. Пусть алгебра Q с С(Е) порождена функциями qA.(x) с четными номерами. Это также плотная подалгебра в С(Е). Рассмотрим оператор в алгебре полиномов от Ц2, q4, • • •, зависящий от параметра а > 0: оо Q2

В= Y, (2i + 1)(23 + 1) - q2iq2j) д—д—+ ij=1 oq2iOq2j

00 д °° ( а\ с)

2 £ (2г + 2j + 3) q2iq2,----£(2г + 1) 2г + - Чи—. ij=0 Cq2«+2i+2 г=1 \ 2/ Cq2i

Основные свойства процессов Xa(t), которые устанавливаются в третьем параграфе, состоят в следующем:

• Для каждого а > 0 оператор B:Q -> Q замыкаем в С(Е) и порождает бесконечномерный диффузионный процесс Xa(t) на Е.

• У процесса Xa(t) существует единственная инвариантная вероятностная мера Р(а) на Е. Процесс обратим и эргодичен относительно нее.

• Траектории процесса Xa(t) непрерывны с вероятностью единица.

• Конечные марковские цепи на строгих разбиениях, построенные в первом параграфе второй главы, сходятся к процессу Xa(t). Точная формулировка этой сходимости приведена в теореме 2.3.5 ниже.

Основные результаты диссертации

1. Дана алгебро-комбинаторная интерпретация однопараметрической классической модели Морана и построено ее обобщение на двухпарамет-рический случай.

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

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

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

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

Некоторые из полученных в диссертации результатов имеют продолжение в недавних работах Фенга и Сана [53] и Руггиеро и Уолкера [81].

Основные результаты диссертации опубликованы в 3 статьях автора [16], [17], [18] в научных журналах, входящих в Перечень ВАК. Они неоднократно докладывались автором на семинаре «Комбинаторные и вероятностные аспекты теории представлений» (Независимый Московский Университет, руководитель — д.ф.-м.н., г.н.с. Г.И. Ольшанский), на семинаре Добрушинской математической лаборатории (ИППИ РАН, 2010 г., руководитель — профессор Р.А. Минлос), на семинаре «Теория вероятностей и эргодическая теория» (МГУ, 2007 и 2010 гг., руководители — профессор Б.М. Гуревич, профессор В.И. Оселедец, доцент С.А. Пирогов), на семинаре «Математические модели в биологии» (МГУ, 2007 г., руководитель — профессор В.А. Малышев), на петербургском семинаре по теории представлений и динамическим системам (ПОМИ РАН, 2008 г., руководитель — профессор A.M. Вершик), на семинаре «Асимптотический анализ случайных процессов и полей» (МГУ, 2008 г., руководители — профессор А.В. Булинский и доцент А.П. Шашкин), на международной школе «Large N Limits» (Биш, Франция, 2008 г.), на международной школе Тихоокеанского Института Математических Наук и Университета Британской Колумбии (Ванкувер, Канада, 2009 г.).

Научная новизна

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

Заключение диссертации по теме «Теоретические основы информатики», Петров, Леонид Александрович

Основные результаты диссертации состоят в следующем:

1. Дана алгебро-комбинаторная интерпретация однопараметрической классической модели Морана и построено ее обобщение на двухпараметрический случай.

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

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

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

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

Полученные в диссертации результаты могут найти применение в теоретической информатике, теории машинного обучения (в динамических задачах классификации), непараметрической байесовской статистике, попу-ляционной генетике, комбинаторике и теории случайных процессов. Некоторые из полученных в диссертации результатов уже имеют продолжение в работах Фенга и Сана [53] и Руггиеро и Уолкера [81].

Заключение

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Петров, Леонид Александрович, 2010 год

1. Прикладная статистика: классификация и снижение размерности / Айвазян С., Бухштабер В., Енюков И., Мешалкин Л.— М.: Финансы и статистика, 1989.— 608 С.

2. Блиновский В. Принцип больших уклонений для границы случайной диаграммы юнга // Пробл. передачи информ,— 1999.— Т. 35, № 1,— С. 61-74.

3. Блиновский В. Принцип больших уклонений для пуассоновских случайных величин и диаграммы Юнга // Проблемы передачи информации. — 2001,-Т. 37, № 1.-С. 72-77.

4. Блиновский В. Случайная диаграмма Юнга, вариационный метод и смежные проблемы // Проблемы передачи информации. — 2002. — Т. 38, №2.-С. 33-43.

5. Бородин А. Мультипликативные центральные меры на графе Шура // Зап. научн. сем. ПОМИ.- 1997.- Т. 240.- С. 44-52.

6. Вентцель А. Курс теории случайных процессов. — М.: Наука. Физмат-лит, 1996.-400 С.

7. Вершик А. Асимптотическое распределение разложений натуральных чисел на простые делители II ДАН СССР.- 1986.- Т. 289, № 2.-С. 269-272.

8. Гончаров В. Из области комбинаторики // Известия Российской академии наук. Серия математическая. — 1944.— Т. 8, № 1.— С. 3-48.

9. Загоруйко Н. Прикладные методы анализа данных и знаний. — Изд-во Ин-та математики, Новосибирск, 1999.— 264 С.

10. Иванов В. Размерность косых сдвинутых диаграмм Юнга и проективные характеры бесконечной симметрической группы // Записки научных семинаров ПОМИ. 1997. - Т. 240. — С. 115-135.

11. Керов С. Комбинаторные примеры в теории AF-алгебр // Зап. науч. семып. ЛОМИ. 1989. - Т. 172. - С. 55-67.

12. Керов С. Анизотропные диаграммы Юнга и симметрические функции Джека // Функц. анализ и его прил. — 2000. — Т. 34, № 1. — С. 51-64.

13. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. СПб.: Вильяме, 2000.- 824 С.

14. Макдоиалъд И. Симметрические функции и многочлены Холла.— Москва, Мир, 1984.-221 С.

15. Назаров М. Ортогональный базис в неприводимых проективных представлениях симметрической группы // Функциональный анализ и его приложения. — 1988. Т. 22, № 1. - С. 77-78.

16. Петров Л. Двухпараметрическое семейство бесконечномерных диффузий на симплексе Кингмана // Функциональный анализ и его приложения. 2009. - Т. 43, № 4. - С. 45-66.

17. Петров Л. Предельное поведение некоторых случайных блужданий на строгих разбиениях // Успехи математических наук. — 2009.— Т. 64, №6.-С. 177-178.

18. Петров Л. Случайные блуждания на строгих разбиениях // Записки научных семинаров ПОМИ. 2009. - Т. 373. - С. 226-272.

19. Стенли Р. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции. — М.: Мир, 2005. — 767 С.

20. Фултон У. Таблицы Юнга и их приложения к теории представлений и геометрии. М.: МЦНМО, 2006.- 328 С.

21. Шрейдер Ю. О возможности теоретического вывода статистических закономерностей текста (к обоснованию закона Ципфа) // Проблемы передачи информации. — 1967. — Т. 3, № 1.— С. 57-63.

22. Якубович Ю. Центральная предельная теорема для нормированных диаграмм юнга разбиений на различные слагаемые // Зап. научн. сем. ПОМИ.- 1999.-Т. 256.-С. 212-223.

23. Antoniak, С. Mixtures of Dirichlet Processes with Applications to Bayesian Nonparametric Problems // Ann. Statist.— 1974.— V. 2, № 6.— P. 1152-1174.

24. Aoki, M. Thermodynamic limits of macroeconomic or financial models: One-and two-parameter Poisson-Dirichlet models // Journal of Economic Dynamics and Control. 2008. - V. 32, № 1. - P. 66-84.

25. Baiyshnikov, Y. GUEs and queues // Probability Theory and Related Fields. 2001. - V. 119, № 2. - P. 256-274.

26. Berele, A., Tenner, B. Doubly symmetric functions. — 2009. — arXiv:0903.5306vl math.CO.

27. Billingsley, P. On the distribution of large prime divisors // Periodica Mathematica Hungarica.- 1972.- V. 2, № 1. — P. 283-289.

28. Blackwell, D., MacQueen, J. Ferguson distributions via Polya urn schemes I I The annals of statistics. — 1973.- V. 1, № 2,- P. 353-355.

29. Blei, D., Griffiths, Т., Jordan, M. The nested Chinese restaurant process and bayesian nonparametric inference of topic hierarchies // J. ACM. — 2010.— V. 57, № 2.- P. 1-30.

30. Blei, D.,-Lafferty, J. Dynamic topic models // Proceedings of the 23rd international conference on Machine learning / ACM. — 2006.

31. Blei, D., Lafferty, J. A correlated topic model of Science // Annals of Applied Statistics. 2007. - V. 1, № 1. - P. 17-35.

32. Blei, D., Ng, A., Jordan, M. Latent Dirichlet allocation // The Journal of Machine Learning Research. — 2003. — V. 3. — P. 993-1022.

33. Borodin, A., Olshanski, G. Infinite-dimensional diffusions as limits of random walks on partitions 11 Prob. Theor. Rel. Fields. — 2009.— V. 144, № 1.- P. 281-318.

34. Carlton, M. Applications of the two-parameter Poisson-Dirichlet distribution: Ph.D. thesis / University of California Los Angeles. — 1999.

35. Dembo, A., Vershik, A., Zeitouni, O. Large deviations for integer partitions // Markov Process. Relat. Fields. 2000. - V. 6, № 2. - P. 147-179.

36. Derrida, B. Random-energy model: An exactly solvable model of disordered systems // Physical Review B. 1981. - V. 24, № 5. - P. 2613-2626.

37. Derrida, B. From random walks to spin glasses // Physica D: Nonlinear-Phenomena.- 1997. — V. 107, № 2-4. — P. 186-198.

38. Dey, D., Mueller, P., Sinha, D. Practical nonparametric and semiparametric Bayesian statistics. — New York: Springer, 1998. — 392 P.

39. Dickman, K. On the frequency of numbers containing prime factors of a certain relative magnitude II Ark. Mat. Astr. Fys. — 1930. — V. 22. — P. 1-14.

40. Donnelly, P., Grimmett, G. On the asymptotic distribution of large prime factors // J. London Math. Soc. 1993. - V. 47, № 2. - P. 395-404.

41. Donnelly, P., Tavare, S. The population genealogy of the infinitely-many neutral alleles model I I Journal of mathematical biology.— 1987.— V. 25, № 4.- P. 381-391.

42. Draief M., Mairesse, J., O'Connell, N. Queues, stores, and tableaux // Journal of Applied Probability. 2005. - V. 42, № 4. - P. 1145-1167.

43. Ethier, S. The infinitely-many-neutral-alleles diffusion model with ages // Advances in Applied Probability. — 1990. V. 22, № 1. - P. 1-24.

44. Ethier, S. Eigenstructure of the infinitely-many-neutral-alleles diffusion model // Journal of Applied Probability.— 1992.— V. 29, № 3,— P. 487-498.

45. Ethier, S., Griffiths, R. The transition function of a Fleming-Viot process // The Annals of Probability. 1993. - V. 21, № 3. p. 1571-1590.

46. Ethier, S. N., Kurtz, T. G. The Infinitely-Many-Neutral-Alleles Diffusion Model // Advances in Applied Probability.— 1981.— V. 13, № 3.— P. 429-452.

47. Ethier, S. N. Kurtz, T. G. Markov processes: Characterization and convergence. — New York: Wiley-Interscience, 1986. — 552 P.

48. Ethier, S. N., Kurtz, T. G. Fleming-Viot Processes in Population Genetics // SI AM J. Control and Optimization. — 1993. V. 31, № 2. - P. 345-386.

49. Ewens, W. The sampling theory of selectively neutral alleles // Theoretical Population Biology. 1972. - V. 3. - P. 87-112.

50. Ewens, W., Kirby, K. The eigenvalues of the neutral alleles process // Theoret. Popn Biol 1975. - V. 7. - P. 212-220.

51. Ewens, W. J. Mathematical Population Genetics. — Berlin: Springer-Verlag, 1979.- 325 P.

52. Feng, S. The Poisson-Dirichlet Distribution and Related Topics. — Springer, 2010,-216 P.

53. Feng, S., Sun, W. Some diffusion processes associated with two parameter Poisson-Dirichlet distribution and Dirichlet process // Probability Theory and Related Fields. — 2009.

54. Ferguson, T. A bayesian analysis of some nonparametric problems // The Annals of Statistics. 1973,- V. 1, № 2,- P. 209-230.

55. Fleming, W. H., Viot, M. Some measure-valued Markov processes in population genetics theory // Indiana Univ. Math. J.— 1979.— V. 28.— P. 817-843.

56. Forrester, P. Log-gases and random matrices. — URL: http://www.ms.unimelb.edu.au/~matpjf/matpjf.html.

57. Friedman, J., Hastie, Т., Tibshirani, R. The elements of statistical learning. — Springer Series in Statistics, 2001. — 746 P.

58. Fulman, J. Stein's method and Plancherel measure of the symmetric group // Trans. Amer. Math. Soc. 2005. - V. 357. - P. 555-570.

59. Fulman, J. Commutation relations and Markov chains // Probability Theory and Related Fields. 2009. - V. 144, № 1. - P. 99-136.

60. Ghosh, J., Ramamoorthi, R. Bayesian Nonparametrics. — New York: Springer-Verlag, 2003. 305 P.

61. Goldwater, S., Griffiths, Т., Johnson, M. Interpolating between types and tokens by estimating power-law generators // Advances in Neural Information Processing Systems. — 2006. — V. 18.

62. Hoffman, P. N., Humphreys, J. F. Projective representations of the symmetric groups. — Oxford Univ. Press, 1992. — 320 P.

63. Ivanov, V. Plancherel measure on shifted Young diagrams // Representation theory, dynamical systems, and asymptotic combinatorics.— Amer. Math. Soc. Transl. Ser. 2, 2006. V. 217. - P. 73-86.

64. James, L. F. Bayesian calculus for gamma processes with applications to semiparametric intensity models // Sankhya: The Indian Journal of Statistics.- 2003.- V. 65, № 1,- P. 179-206.

65. James, L. F. Bayesian Poisson process partition calculus with an application to Bayesian Levy moving averages // Ann. Statist. — 2005. — V. 33, № 4. — P. 1771-1799.

66. Johnson, М., Griffiths, Т., Goldwater, S. Adaptor grammars: A framework for specifying compositional nonparametric bayesian models 11 Advances in neural information processing systems. — 2007. — V. 19. — P. 641-649.

67. Kerov, S. Asymptotic representation theory of the symmetric group and its applications in analysis. — Amer. Math. Soc., 2003.— 201 P.

68. Kerov, S., Okounkov, A., Olshanski, G. The boundary of Young graph with Jack edge multiplicities // Intern. Math. Research Notices. — 1998. — V. 4. — P. 173-199.

69. Kingman, J. F. C. Random discrete distributions // J. Roy. Statist. Soc. B. — 1975.-V. 37.-P. 1-22.

70. Kingman, J. F. C. Random partitions in population genetics // Proc. R. Soc. London, A.- 1978.-V. 361.-P. 1-20.

71. M. Kimura, J. C. The number of alleles that can be maintained in a finite population // Genetics. 1964.- V. 49.- P. 725-738.

72. Macdonald, I. G. Symmetric functions and Hall polynomials.— 2nd edition. — Oxford University Press, 1995. — 488 P.

73. Nazarov, M. Projective representations of the infinite symmetric group // Representation theory and dynamical systems / Ed. by A. Vershik. — Amer. Math. Soc., 1992.-V. 9.-P. 115-130.

74. Nazarov, M. Young's Symmetrizers for Projective Representations of the Symmetric Group // Advances in Mathematics.— 1997.— V. 127, № 2.— P. 190-257.

75. Olshanski, G. Anisotropic Young diagrams and infinite-dimensional diffusion processes with the Jack parameter // International Mathematics Research Notices. 2010. - V. 2010. - P. 1102-1166.

76. Pitman, J. The two-parameter generalization of Ewens' random partition structure: Technical report 345 / J. Pitman: Dept. Statistics, U. C. Berkeley, 1992.

77. Pitman, J. Some developments of the Blackwell-MacQueen urn scheme / J. Pitman // Lecture Notes-Monograph Series.— 1996.— V. 30.— P. 245-267.

78. Pitman, J. Combinatorial Stochastic Processes. — Springer-Verlag, 2006. — 256 P.

79. Pitman, J., Yor, M. Two-parameter Poisson-Dirichlet distribution derived from a stable subordinator // The Annals of Probability.— 1997.— V. 25, №2.-P. 855-900.

80. Pragacz, P. Algebro-geometric applications of Schur S- and Q-polynomials // Lecture Notes in Mathematics.— 1478.— V. 1991.— P. 130-191.

81. Ruggiero, M., Walker, S. Countable representation for infinite dimensional diffusions derived from the two-parameter Poisson-Dirichlet process // Electronic Communications in Probability. — 2009. — V. 14. — P. 501-517.

82. Sagan, B. Shifted tableaux, Schur Q-functions, and a conjecture of Stanley // J. Comb. Theo. A. 1987.- V. 45.- P. 62-103.

83. Schmuland, B. A result on the infinitely many neutral alleles diffusion model // Journal of Applied Probability.— 1991.— V. 28, № 2.— P. 253-267.

84. Schur, I. Uber die Darstellung der symmetrischen und der alternierenden Gruppe durch gebrocheme lineare Substitionen // J. Reine Angew. Math. — 1911.-V. 139,- P. 155-250.

85. Sergeev, A. The Howe duality and the projective representations of symmetric groups // Represent. Theory. — 1999. — V. 3. — P. 416-434.

86. Stembridge, J. A characterization of supersymmetric polynomials // J. Algebra. 1985. - V. 95. - P. 439-444.

87. Stembridge, J. Shifted tableaux and the projective representations of symmetric groups // Advances in Mathematics.— 1989.— V. 74, № 1.— P. 87-134.

88. Stembridge, J. On schur's q-functions and the primitive idempotents of a commutative hecke algebra // J. Algebraic Combin.— 1992.— V. 1,—

89. Trotter, H. F. Approximation of Semigroups of Operators // Pacific J. Math. 1958.-V. 8.-P. 887-919.

90. Wang, C., Blei, D., Heckerman, D. Continuous time dynamic topic models // Uncertainty in Artificial Intelligence UAI. — 2008.

91. Watterson, G. Reversibility and the age of an allele. I. Moran's infinitely many neutral alleles model // Theoret. Popn Biol.— 1976.— V. 10.— P. 239-253.

92. Worley, D. A theory of shifted Young tableaux: Ph.D. thesis / MIT, Dept. of Mathematics. — 1984.1. P. 71-95.