Введение 3
1. Тепловые ядра и ядра Матерна на конечных группах и однород¬ных пространствах 3
1.1. Напоминания из теории групп 3
1.2. Тепловые ядра и ядра Матерна на графах 6
1.3. Тепловые ядра и ядра Матерна на конечных группах 7
1.4. Тепловые ядра и ядра Матерна на однородных простран¬ствах конечных групп 8
1.5. Пары Гельфанда и зональные сферические функции 9
2. Приложение к филогенетическим деревьям 15
2.1. Пара Гельфанда (S2n, S21 Sn) 16
2.2. Напоминания из теории представлений симметрических групп 19
2.3. Граф Кэли группы S2n 23
2.4. Зональные сферические функции 24
3. Вычисление ядер 26
3.1. Наивный метод 26
3.2. Метод на основе зональных полиномов 28
3.3. Монте-Карло аппроксимация 32
3.4. Сравнение и эксперименты 34
Заключение 35
Благодарности 35
Список литературы 36
A. Доказательства 38
Гауссовские случайные поля (гауссовские процессы) представляют большой интерес как с точки зрения чистой математики [6, 7, 9], так и с точки зрения различных приложений [13, 18]. Напомним, что гауссовским полем на множестве T называется набор случайных величин {Xt}t€-т, каждый конечный набор которых имеет совместное гауссовское распределение. При этом, все конечномерные распределения гауссовского процесса однозначным образом определяются функцией среднего и ковариационной функцией (ядром):
m(t) = E [Xt] k(s, t) = E [(Xs — m(s))(Xt — m(t)].
Для евклидовых пространств, то есть T с Rd, наиболее популярными являются семейства тепловых ядер и ядер Матерна. Обобщение данных семейств на случаи неевклидовых пространств, а также нахождение методов, позволяющих их эффективно вычислять, является интересным направлением для исследований. Например, в статье [3] рассматривается случай, когда множество T является графом, а в статье [1] — случай, когда множество T это (компактная) группа Ли или её однородное пространство.
Вдохновляясь возможными приложениями в филогенетике и пользуясь аппаратом теории представлений, пар Гельфанда и симметрических функций, в рамках данной работы мы введём тепловые ядра и ядра Матерна на некоторых пространствах филогенетических деревьев, после чего рассмотрим несколько методов вычисления полученных ядер, а также проведём их теоретическое и эмпирическое сравнение .
В рамках данной работы мы построили тепловые ядра и ядра Матерна на
некоторых пространствах филогенетических деревьев. Далее, мы рассмотрели вопрос эффективного вычисления полученных ядер, который, по существу,
свёлся к вопросу эффективного вычисления зональных сферических функций пары Гельфанда (S2n, S2 ≀Sn). Нами был предложен метод их вычисления,
основанный на использовании зональных полиномов. Наконец, было проведено сравнение, в частности включающее в себя численные эксперименты,
различных подходов к вычислению ядер. По результатам сравнения оказалось, что предложенный метод на основе зональных полиномов имеет как
теоретическое, так и эмпирическое преимущество перед наивным методом.
В частности, он позволил вычислять значения ядер для филогенетических
деревьев на 15 и более листьях за адекватное время, в то время как наивный
алгоритм был ограничен случаем филогенетических деревьев на 5–6 листьях.
