Содержание к диссертации
Введение
Глава 1. Диффузии и распределения Пуассона-Дирихле 16
1.1. Распределения Пуассона-Дирихле и модель Морана 16
1.2. Марковские цепи на разбиениях и симметрические функции 26
1.3. Построение и свойства предельного процесса 34
Глава 2. Марковские цепи на строгих разбиениях 50
2.1. Строгие разбиения и перемежающиеся координаты 50
2.2. Вычисление в алгебре дважды симметрических функций . 59
2.3. Сходимость марковских цепей на строгих разбиениях 84
Заключение 93
Литература 95
- Марковские цепи на разбиениях и симметрические функции
- Построение и свойства предельного процесса
- Вычисление в алгебре дважды симметрических функций
- Сходимость марковских цепей на строгих разбиениях
Введение к работе
Актуальность темы. Теория машинного обучения изучает методы построения и анализа алгоритмов, способных обучаться в процессе своей работы. К области машинного обучения без учителя относятся алгоритмы, в ходе выполнения которых система спонтанно обучается выполнять поставленную задачу без вмешательства со стороны экспериментатора. Общие сведения о задачах машинного обучения см. в '.
В последние несколько лет в области машинного обучения без учителя активно развиваются методы анализа и классификации по темам большого корпуса текстов на естественном языке, основанные на непараметрических байесовских моделях (см., например, работы2'3'4, а также обширную библиографию в последней работе). Многие вероятностные модели, рассматриваемые в связи с этими задачами, основаны на распределениях Пуассона-Дирихле. Вероятностные распределения Пуассона-Дирихле зависят от двух параметров 0 ^ а < 1 и в > -а и описывают закон распределения последовательности невозраста-ющих неотрицательных случайных величин с суммой единица. В исследование распределений Пуассона-Дирихле внесли вклад Бертуан, Биллингсли, Бли-новский, Вершик, Гончаров, Гримметт, Гриффите, Дикман, Доннелли, Игнатов, Пор, Карлтон, Керов, Куртц, Кингман, Ллойд, Ольшанский, Питман, Уоттерсон, Цилевич, Шепп, Шмидт, Этье, Ювенс, и другие. Более подробно о распределениях Пуассона-Дирихле см. недавнюю монографию5. Однопараметрическое семейство распределений Пуассона-Дирихле (соответствующее случаю а = 0) было введено Кингманом (1975) в связи с задачами, возникающими в попу-ляционной генетике. Двухпараметрическое обобщение принадлежит Питману (1992). Вероятностные модели машинного обучения, основанные на распределениях Пуассона-Дирихле, существенно используют специфику второго пара-
1 Прикладная статистика: классификация и снижение размерности / С. Айвазян, В. Бухштабер, И. Енюков, Л. Мешалкин. — М.: Финансы и статистика, 1989. — 608 С.
Johnson, М., Griffiths, Т., Goldwater, S. Adaptor grammars: A framework for specifying compositional nonparametric bayesian models II Advances in neural information processing systems. — 2007.-V. 19.-P. 641-649.
Teh, . A hierarchical Bayesian language model based on Pitman-Yor processes II Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics. — 2006. — P. 985-992.
4Blei, D., Griffiths, Т., Jordan, M. The nested Chinese restaurant process and bayesian nonparametric inference of topic hierarchies II J ACM. - 2010. - V. 57, № 2. - P. 1-30.
5Feng, S. The Poisson-Dirichlet Distribution and Related Topics. — Springer, 2010. — 216 P.
метра а. Это связано с тем, что случайные величины в последовательности, имеющей распределение Пуассона-Дирихле, при а = 0 с вероятностью единица убывают показательным образом, а при а + 0 — степенным образом; как известно, для естественных языков характерно степенное убывание частот (см., например, работу6).
В теории машинного обучения начинают исследоваться и динамические модели, см., например, статью7. Они связаны с распределениями Дирихле, которые являются конечномерными аналогами распределений Пуассона-Дирихле. Использование распределений Дирихле приводит к ограничениям на число возможных тем в задаче классификации. Поэтому возникает потребность в динамических моделях (связанных с двухпараметрическими распределениями Пуассона-Дирихле), которые могли бы снять это ограничение.
Динамические модели, связанные с однопараметрическим семейством распределений Пуассона-Дирихле, широко изучались в контексте популяционной генетики. Изучение динамических моделей в популяционной генетике началось с дискретных моделей Райта-Фишера (рассматривалась, начиная с 1920-30-х гг.) и Морана (была введена в 1950-е гг.). Эти модели можно трактовать как последовательности марковских цепей на разбиениях (пространство состояний п-й цепи есть множество всех разбиений числа п).
Разбиения — фундаментальный математический объект. Основные сведения о них можно найти в книге Стенли8. Разбиения широко применяются в теоретической информатике, например, в различных методах сортировки (в частности, при сортировке слияниями), которым посвящена фундаментальная монография Кнута9.
Предельное поведение некоторых классов моделей Райта-Фишера и Морана исследовано в работе Этье и Куртца10, в которой построено семейство бесконечномерных диффузионных процессов, сохраняющих однопараметриче-
6Шрейдер, Ю. О возможности теоретического вывода статистических закономерностей текста (к обоснованию закона Ципфа) // Проблемы передачи информации. — 1967. — Т. 3, № 1. — С. 57-63.
7 Wang, С, Blei, D., Heckerman, D. Continuous time dynamic topic models II Uncertainty in Artificial Intelligence [UAI].-2008.
Стенли, P. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции. — М.: Мир, 2005. — 767 С.
9Кнут, Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск.— СПб.: Вильяме, 2000. - 824 С.
Ethier, S. К, Kurtz, Т. G. The Infinitely-Many-Neutral-Alleles Diffusion Model II Advances in Applied Probability. - 1981.- V. 13, № 3. - P. 429-452.
ские распределения Пуассона-Дирихле. Построенные процессы исследовались и обобщались в работах, принадлежащих Вио, Доннелли, Гриффите, Куртц, Таваре, Уоттерсон, Флеминг, Шмуланд, Этье, и др.
Для построения бесконечномерных диффузионных процессов Этье и Куртц использовали их аппроксимацию конечномерными диффузиями на симплексах растущей размерности. Данный метод неприменим в случае двухпарамет-рических распределений Пуассона-Дирихле. Поэтому для построения бесконечномерных диффузий, обобщающих процессы Этье-Куртца10 на двухпараметрический случай, требуется применение других методов. В диссертации найдена алгебро-комбинаторная интерпретация модели Морана на разбиениях, которая позволяет обобщить эту модель на двухпараметрический случай, а также построить диффузии, сохраняющие двухпараметрические распределения Пуассона-Дирихле.
Алгебро-комбинаторная интерпретация модели Морана включает её (и её двухпараметрическое обобщение) в широкий класс марковских цепей на разбиениях, рассматриваемый Фульманом, Бородиным и Ольшанским (см., например, работу11). Возникает вопрос об анализе асимптотического поведения других марковских цепей на разбиениях, входящих в этот класс. В диссертации проводится исследование одного семейства марковских цепей из этого класса на строгих разбиениях (то есть, разбиениях, все части которых различны). О некоторых приложениях строгих разбиений в теоретической информатике (в задачах сортировки) см., например, монографию Кнута9. Соответствие Робинсона-Шенстеда-Кнута для обычных разбиений9 обобщается и на случай строгих разбиений12. Это комбинаторное соответствие делает возможным применение различных ансамблей случайных разбиений в задачах, связанных со случайными матрицами, а также в теории массового обслуживания (см., например, работу13). Модель марковских цепей на строгих разбиениях возникает в связи с ансамблем случайных строгих разбиений, введенном Бородиным14. Этот ансамбль связан с теорией проективных представлений симметрических
11 Borodin, A., Olshanski, G. Infinite-dimensional diffusions as limits of random walks on partitions II Prob. Theor. Rel. Fields. - 2009. - V. 144, № 1. - P. 281-318.
Sagan, B. Shifted tableaux, Schur Q-functions, and a conjecture of Stanley II J. Comb. Theo. A. — 1987.-V. 45.-P. 62-103.
13Baryshnikov, . GUEs and queues II Probability Theory and Related Fields. — 2001. — V. 119, № 2. — P. 256-274.
Бородин, А. Мультипликативные центральные меры на графе Шура // Зап. научи, сем. ПОМИ. — 1997. - Т. 240. - С. 44-52.
групп (эта теория развивалась в работах Иванова, Назарова, Сергеева, Стембри-джа, Шура, и др.). Стоит отметить, что этот ансамбль приводит к новым моделям точечных процессов, которые отличаются от традиционно рассматриваемых в статистической физике. Изучение предельного поведения указанных марковских цепей на строгих разбиениях позволяет построить новые примеры бесконечномерных диффузионных процессов.
Цель работы. Цель настоящей диссертации состоит в построении (путем предельного перехода от конечных марковских цепей на разбиениях) и исследовании новых примеров бесконечномерных диффузионных процессов, которые могут быть использованы в динамических задачах классификации в теории машинного обучения.
Научная новизна. В диссертации построены новые примеры бесконечномерных диффузионных процессов, среди которых — семейство процессов, сохраняющих двухпараметрические распределения Пуассона-Дирихле. Данные процессы могут использоваться в динамических задачах классификации в тех моделях машинного обучения, где ранее использовались распределения Дирихле. Кроме того, введены и исследованы новые примеры марковских цепей на разбиениях, в пределе приводящие к указанным бесконечномерным диффузионным процессам.
Методы исследования. При исследовании конечных марковских цепей на разбиениях в диссертации широко применяются методы алгебраической комбинаторики, теории симметрических и дважды симметрических функций. При исследовании асимптотического поведения конечных марковских цепей используются разработанные Троттером, Этье и Куртцом методы аппроксимации непрерывных полугрупп в банаховых пространствах дискретными полугруппами. При построении бесконечномерных диффузионных процессов используется также общая теория полугрупп в банаховых пространствах.
Теоретическая и прикладная ценность. Диссертация носит теоретический характер. Полученные результаты могут найти применение в теоретической информатике, теории машинного обучения (в динамических задачах классификации), непараметрической байесовской статистике, популяционной генетике, комбинаторике и теории случайных процессов. Некоторые из полученных в диссертации результатов имеют продолжение в недавних работах Фенга и Са-
на 15 и Руггиеро и Уолкера 16.
Апробация работы. Результаты диссертации неоднократно докладывались автором на семинаре «Комбинаторные и вероятностные аспекты теории представлений» (Независимый Московский Университет, руководитель — д.ф.-м.н., т.н. с. Г.И. Ольшанский), на семинаре Добрушинской математической лаборатории (ИППИ РАН, 2010 г., руководитель — профессор РА. Минлос), на семинаре «Теория вероятностей и эргодическая теория» (МГУ, 2007 и 2010 гг., руководители — профессор Б.М. Гуревич, профессор В.И. Оселедец, доцент С.А. Пирогов), на семинаре «Математические модели в биологии» (МГУ, 2007 г., руководитель — профессор В.А. Малышев), на петербургском семинаре по теории представлений и динамическим системам (ПОМП РАН, 2008 г., руководитель — профессор A.M. Вершик), на семинаре «Асимптотический анализ случайных процессов и полей» (МГУ, 2008 г., руководители — профессор А.В. Булинский и доцент А.П. Шашкин), на международной школе «Large N Limits» (Биш, Франция, 2008 г.), на международной школе Тихоокеанского Института Математических Наук и Университета Британской Колумбии (Ванкувер, Канада, 2009 г.).
Публикации. Основные результаты диссертации опубликованы в 3 статьях автора в научных журналах, входящих в перечень ВАК. Список работ приведен в конце автореферата.
Структура диссертации. Диссертация состоит из введения, двух глав, заключения и списка литературы, насчитывающего 93 наименования. В текст включены 5 рисунков. Общий объем работы составляет 103 страницы.
Feng, S., Sun, W. Some diffusion processes associated with two parameter Poisson-Dirichlet distribution and Dirichlet process II Probability Theory and Related Fields. — 2009.
l6Ruggiero, M., Walker, S. Countable representation for infinite dimensional diffusions derived from the two-parameter Poisson-Dirichlet process II Electronic Communications in Probability. — 2009. — V. 14. — P. 501-517.
Марковские цепи на разбиениях и симметрические функции
В этом параграфе приводится определение алгебры симметрических функций, и вычисляется действие переходных операторов Тп марковских цепей вверх/вниз, построенных по структуре разбиений Ювенса-Питмана {Мп в} на симметрические функции от компонент разбиений.
Определение 1.2.1. Пусть т/i э 2/2»- - — формальные переменные. Алгебра симметрических функций Л состоит из всех формальных степенных рядов с действительными коэффициентами от переменных уі,у2,..., которые симметричны по /1, т/2,... и имеют ограниченную степень (то есть, степени всех мономов в формальном степенном ряде равномерно ограничены). Другими словами, каждая симметрическая функция / є Л представляет собой последовательность многочленов (fk)kn таких, что Многочлен fk зависит от переменных yi,..., yj и является симметрическим. Степени многочленов равномерно ограничены: supfc deg Д со. Число supj. deg fk называется степенью симметрической функции. Выполнено свойство стабильности: Алгебра Л свободно порождена (как коммутативная алгебра с единицей) суммами Ньютона pk := г і у\, к є N. Мономиальные функции определяются как где р = (pi,... -, pi) e IK и сумма ведется по всем наборам попарно различных индексов гі,..., ie 1. Факториальные аналоги функций тр (обозначаемые т ) получаются из обычных функций заменой каждой степени у\ на фак-ториальную степень у\к = УІ(УІ-1) (уі-к + l). Каждая из систем функций {пір} и {т } (где р пробегает все разбиения) является линейным базисом алгебры Л. Алгебру всех действительнозначных функций на множестве X с поточечными операциями будем обозначать через Fun(X). Рассмотрим вложение (абстрактной) алгебры симметрических функций Л в алгебру функций Fun(K) на множестве всех разбиений. Это вложение определено на суммах Ньютона (которые порождают алгебру Л) следующим образом: Будем отождествлять алгебру Л с ее образом в Fun(K) при этом вложении. Алгебра симметрических функций на множестве
К разделяет точки. Пусть / є Л. Через /„ обозначим ограничение функции / на подмножество Кп с К. Так как Кп конечно, то конечномерное пространство Fun(Kn) исчерпывается функциями вида fn, где / е Л. С использованием только что введенных обозначений можно удобно сформулировать одно важное свойство факториальных функций т , которое связывает их с графом Кингмана, определенным в первом параграфе. Напомним, что там же были определены числа путей g(cr, р), а, р є К. Ясно, что они удовлетворяют следующим рекуррентным соотношениям для всех j, р IK. Как объясняется в первом параграфе, сумма по т здесь фактически конечна и ведется только по тем гп, для которых определено разбиение р т\ С помощью рекуррентных соотношений (1.2.1) нетрудно получить по индукции следующую формулу для g(cr, р), выражающую это число путей через факториальную функцию т : Здесь предполагается, что г р, так как иначе g(cr,p) = 0. При доказательстве (1.2.4) используется определение факториальных функций т , а также следующие простые свойства факториальных степеней Если b = 0, то полагаем а -1) := 0.
Положим m := m /(n&Li [с:&]!) и ma := mff/(nj=i [c:f!) для всех сг є К. Ясно, что каждая из систем функций {гпа} и {тп } (где а пробегает все разбиения) является линейным базисом алгебры симметрических функций Л. Отметим, что (1.2.2) переписывается в более удобном виде следующим образом: Комбинаторные свойства (1.2.1), (1.2.3) и (1.2.4) используются ниже при вычислении действия переходного оператора Тп марковской цепи вверх/внр построенной по структуре разбиений Ювенса-Питмана, на симметрические функции от компонент разбиений. Как указано выше, симметрические функции на Кг, на самом деле исчерпывают все пространство функций Fim(Kn). Действие переходного оператора Тп на пространстве Fim(Kn) однозначно определяется тем, как он действует на симметрические функции (m )n є Fim(K„). Действие Т„ на (тп )п дается следующей теоремой. Оставшаяся часть данного параграфа посвящена доказательству теоремы 1.2.2. Сперва представим оператор Тп в виде композиции операторов «вниз» Dn+1)n:Fun(IKn) - Fun(Kn+1) и «вверх» С/П)П+і:Гші(Кп+і) - Fun(Kn), действующих на функции. Оператор Dn+i n строится по переходным вероятностям вниз и не зависит от параметров а и 9, в то время как оператор С/П)П+і строится по переходным вероятностям вверх и от параметров зависит: Эти операторы являются сопряженными к соответствующим операторам, действующим на меры. Последние операторы действуют в соответствии со своими названиями, например, D l+ln:M(Kn+i) - М(Кп), где М(Х) — пространство мер на множестве X.
Построение и свойства предельного процесса
В этом параграфе построено двухпараметрическое семейство процессов Xafl(t) на симплексе Е (0.1), зависящих от параметров 0 а 1 и в -а. Данные процессы строятся как пределы марковских цепей Тп на разбиениях, соответствующих структурам разбиений Ювенса-Питма-на {Мп } Последовательность рассуждений в данном параграфе следующая. Сначала устанавливается сходимость генераторов марковских цепей вверх/вниз к некоторому оператору А в пространстве непрерывных функций С(Е). Факт этой сходимости является чисто алгебраическим. Оператор А может быть записан в нескольких разных формах. Утверждения о сходимости генераторов и формулах для оператора А сведены в теорему 1.3.4. После того, как сходимость генераторов марковских цепей установлена, можно применить разработанные Троттером [90], Этье и Куртцом [47] методы аппроксимации непрерывных полугрупп в банаховых пространствах дискретными полугруппами. Данные методы позволяют доказать сходимость дискретных полугрупп марковских цепей вверх/вниз к некторой непрерывной полугруппе в С(Е) (теорема 1.3.9 (1)). Эта полугруппа и есть полугруппа нашего процесса Xa$(t) (см. теорему 1.3.9 (2)). Из построения следует, что процесс Xaje{t) сохраняет меру Пуассона-Дирихле PD(a,#) на Е (теорема 1.3.9 (3)).
После того, как семейство процессов Xa (t) построено, мы исследуем его свойства, такие, как непрерывность траекторий, единственность инвариантной меры, структура спектра, и другие (см. теорему 1.3.9 (4)-(6)). Введем некоторые обозначения, которые будут использоваться в формулировке и доказательстве теоремы 1.3.4 ниже. Каждой точке х є Е соответствует вероятностная мера на отрезке [0,1], где 5S означает меру Дирака в точке s и j(x) := 1 - ?і хг-. Через q/c(x) обозначим к-к момент меры i/x: Это непрерывные функции на Е, поскольку для каждого г = 1,2,... выполнено Xj г 1. Стоит отметить, что функция 7(х) не является непрерывной на Е. Также q/v(x), к Z 1, разделяют точки симплекса Е (поскольку мера на [0,1] однозначно определяется своими моментами), и являются алгебраически независимыми. По аналогии с работой [33] qi(x),q2(x),... назовем моментными координатами точки х е Е. Пусть JF = R [q1; q2,... ] — коммутативная алгебра с единицей, порожденная моментными координатами. По теореме Стоуна-Вейерштрасса, Т является плотной подалгеброй в С(Е) . Пусть / := (pi - 1)Л есть главный идеал в Л (алгебре симметрических функций, определенной во втором параграфе данной главы), порожденный элементом pi - 1 є Л. Положим Л := А/1. Каждому элементу / є Л со ответствует образ в Л, обозначим его через f. В частности, р\ = 1 и Л является коммутативной алгеброй с единицей, свободно порожденной эле ментами рк, к = 2,3, Кроме того, значит, Л = Ш[р2,рз,] Легко проверить, что базис последней алгебры над К — это {т/э}РбК1 [ .i]=o (здесь тр — мономиальные функции, см. второй параграф). Поэтому Е-базисом в Л является система {т}рк, і]=о Соответствие р?2 - яі(х),Рз " ЧгМ,... устанавливает изоморфизм алгебры Л на алгебру Т. Таким образом, каждому элементу / є Л соответствует непрерывная функция на Е, которую обозначим через /(х). В частности, рк(х) = г xf, к = 2,3,..., и рЦх) = 1. Замечание 1.3.1 (теорема Кингмана). В терминах алгебры Л = Т с С(Е) можно удобно описать, как именно вероятностная мера Р на Е определяет структуру разбиений {Мп} на К в теореме Кингмана (теорема 1.1.4): Здесь m — образ в J7 с С(Е) симметрической функции тр є Л, a g(p) — число путей от 0 до р в графе Кингмана, определенное в первом параграфе. Замечание 1.3.2 (формула Керова для т(х)). Пусть х є Е. Если х є Е, то єсть, Ег і Xj = 1, то значение функции f є Л (где / є Л) может быть вычислено путем простой подстановки координат (хі,Х2,...) точки х вместо формальных переменных уі,у2,... в алгебре симметрических, функций Л. Отметим, что так как х є Е, то факторизация / - / происходит автоматически. Если же х є Е \ Е, то значение /(х) (где / еЛ) уже не вычисляется таким образом. Керовым [11], [67] найден способ вычислять т(х), где р К, для всех х є Е. Пусть /(xi,X2,...) для / є Л означает формальную подстановку координат точки х є Е в функцию /. Пусть р є К, [р: 1] =: г 0. Тогда Здесь m(x) — значение функции m в точке х, полученное путем факторизации алгебры Л и р - пк — разбиение, полученное из р выкидыванием к единичных частей. Отметим, что если х є Е либо [р: 1] = 0, то значение т(х) совпадает с формальной подстановкой mp(xi,x2)...). Нам также понадобится следующее определение. Определение 1.3.3.
Пусть дана коммутативная алгебра. Будем говорить, что каждый оператор умножения на элемент этой алгебры имеет нулевой порядок. Будем говорить, что оператор Q имеет порядок п 1, если коммутатор Q с любым оператором умножения на элемент алгебры имеет порядок п- 1. Напомним, что через С(Е) обозначается банахова алгебра всех неп рерывных функций на Е с поточечными операциями и супремум-нормой . Каждый оператор Тп действует в конечномерном пространстве функ ций Pun(Kn), п = 1,2, Эти пространства можно считать банаховыми с супремум-нормой, которую также будем обозначать через . В первом параграфе данной главы были введены вложения гп:Кп Е. Отметим, что образы гп(Кп) аппроксимируют пространство Е в том смысле, что каждое открытое множество в Е имеет непустое пересечение с гп(Кп) для всех достаточно больших п. Пусть 7гп — соответствующие вложениям гп проекции пространств функций: Теперь, пользуясь обозначениями и фактами выше, мы можем сформулировать теорему о сходимости генераторов марковских цепей вверх/вниз. Теорема 1.3.4. Существует оператор А .Т - Т, такой, что при п - со операторы п2{Тп - 1) сходятся к А в алгебре Т. Более формально, Оператор А может быть записан как формальный дифференциальный оператор в коммутативной алгебре полиномов от qi, q2,...:
Вычисление в алгебре дважды симметрических функций
Теория машинного обучения изучает методы построения и анализа алгоритмов, способных обучаться в процессе своей работы. К области машинного обучения без учителя относятся алгоритмы, в ходе выполнения которых система спонтанно обучается выполнять поставленную задачу без вмешательства со стороны экспериментатора. Общие сведения о задачах машинного обучения см. в книгах [1], [9], [57]. В последние несколько лет в области машинного обучения без учителя активно развиваются методы анализа и классификации по темам большого корпуса текстов на естественном языке, основанные на непараметрических байесовских моделях (см., например, работы [32], [61], [89], [66], [29], а также обширную библиографию в последней работе). Многие вероятностные модели, рассматриваемые в связи с этими задачами, основаны на распределениях Пуассона-Дирихле.
Вероятностные распределения Пуассона-Дирихле PD(a,#) зависят от двух параметров 0 ( а 1 и б -а и описывают закон распределения последовательности невозрастающих неотрицательных случайных величин (Xi,X2,.-.), таких, что Х\ Хч ... 0 и Y i i = 1- В исследование распределений Пуассона-Дирихле внесли вклад Бертуан, Биллингсли, Бли-новский, Вершик, Гончаров, Гримметт, Гриффите, Дикман, Доннелли, Игнатов, Йор, Карлтон, Керов, Куртц, Кингман, Ллойд, Ольшанский, Питман, Уоттерсон, Цилевич, Шепп, Шмидт, Этье, Ювенс, и другие. Однопарамет-рическое семейство распределений Пуассона-Дирихле PD(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:6), при а = 0 с вероятностью единица убывают показательным образом, а при а Ф 0 — степенным образом; как известно, для естественных языков характерно степенное убывание частот (см., например, работу Шрейдера [21]). Опишем одну из общих постановок задач классификации в теории машинного обучения. Пусть задано конечное множество слов, называемое словарем. Вероятностное распределение на этом множестве слов называется темой (англ. topic). Текст — это некоторая последовательность слов, а набор текстов принято называть корпусом. На вход алгоритма классификации подается некоторый (обычно весьма большой) корпус текстов. В качестве корпуса текстов, подаваемого на вход, может, например, выступать набор аннотаций к статьям в некотором научном журнале, или подшивка новостных газетных материалов за определенный период времени. Различают статическую и динамическую постановку задачи классификации. В статистической задаче классификации все тексты входного корпуса рассматриваются как равноправные, и задача алгоритма классификации состоит в выборе тем и расположении текстов по темам так, чтобы это наилучшим образом соответствовало входным данным. В динамической задачи классификации постановке каждому тексту корпуса приписывается определенная временная отметка (время выхода журнала или газетного материала в примерах, приведенных выше). Помимо распределенрія текстов по темам, в задачу алгоритма классификации при динамической постановке входит отслеживание зависимости распределения тем от времени. Статические задачи классификации исследовались в уже упомянутых работах [32], [61], [89], [66], [29]. Исследованию некоторых динамических задач классификации посвящены работы [30], [31], [91]. В теории машинного обучения в статических и динамических задачах классификации в основном используется непараметрический байесовский подход, который состоит в следующем. Сначала строится априорная модель, которая порождает случайный корпус текстов с заданными свойствами. Затем по входному корпусу текстов вычисляется (а чаще моделируется, так как явно вычислить не удается) апостериорное распределение при заданных входных данных, по которому уже строится искомый набор тем и распределение текстов по темам, другими словами, производится статистический вывод. Априорная модель здесь зависит от некоторых параметров, которые обычно принадлежат бесконечномерному пространству (например, в качестве параметров модели могут выступать вероятностные распределения на прямой или на множестве натуральных чисел). Применение методов параметрической байесовской статистики в данной ситуации невозможно, поэтому используются другие подходы, называемые непараметрическими. О непараметрической байесовской статистике см., напрршер, книги [38], [60]. Изучение (и в-некоторых случаях явное вычисление) апостериорных распределений, связанных с распределениями Пуассона-Дирихле PD(a, в), проводилось в работах Фергюсона [54], Антоняка [23], Блэкуэлла и Мак-Куина [28], Питмана [77]. Первые три работы рассматривают однопара-метрический случай, а четвертая работа посвящена двухпараметрическим распределенріям Пуассона-Дирихле. Важные задачи статистического оце- нивания и проверки гипотез, связанные с двухпараметрическими распределениями Пуассона-Дирихле, исследовались в диссертации Карлтона [34]. Близкие проблемы исследовались также в работах [64], [65].
Сходимость марковских цепей на строгих разбиениях
Использование распределений Дирихле приводит к ограничениям на число возможных тем в задаче классификации. Поэтому возникает потребность в динамических моделях, связанных с двухпарамет-рическими распределениями Пуассона-Дирихле, которые могли бы снять это ограничение.
Динамические модели, связанные с однопараметрическим семейством распределений Пуассона-Дирихле PD(0,9), широко изучались в контексте популяционной генетики. Изучение динамических моделей в популяцион-ной генетике началось с дискретных моделей Райта-Фишера (рассматривалась, начиная с 1920-30-х гг.) и Морана (была введена в 1950-е гг.). О различных дискретных моделях популяционной генетики см. работы [71], [50], [92], 3 работы [46], главу 10 книги [47], а также книгу [52]. Дискретные модели Райта-Фишера и Морана можно трактовать как последовательности марковских цепей на разбиениях (пространство состояний n-й цепи есть множество всех разбиений числа п).
Разбиения — фундаментальный математический объект. Основные сведения о них можно найти, например, в книгах Стенли [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(a,6).
В первом параграфе приводятся необходимые сведения о разбиениях и распределениях Пуассона-Дирихле. Приводится определение модели Морана на разбиениях и дается ее алгебро-комбинаторная интерпретация, а также вводится двухпараметрический аналог модели Морана. Обозначим через Тп (п б N) переходный оператор марковской цепи на множестве разбиений числа 72, которая является двухпараметрическим обобщением модели Морана. Оператор Тп зависит от параметров 0 а 1и# -а.
Во втором параграфе вычисляется действие переходного оператора Тп на симметрические функции от компонент разбиений. В этом вычислении заключается основная техническая работа по построению двухпара-метрического семейства диффузионных процессов.
