Асимптотические свойства процедур статистического оценивания на многообразиях Янович Юрий Александрович

Содержание к диссертации

Введение

1 Локальное поведение случайных выборок на многообразии 11

1.1 Описание задачи 11

1.2 Модель данных 14

1.3 Основные результаты главы 18

1.4 Некоторые определения и леммы

1.4.1 Локальная линеаризация 20

1.4.2 Леммы Муавра-Лапласа для медленно убывающей вероятности 22

1.4.3 Вероятность больших уклонений для ограниченных случайных величин 23

1.4.4 Замена области интегрирования 24

1.4.5 Конечные сети 25

1.5 Доказательство основных теорем для попадания в окрестность 25

2 Непараметрическое оценивание на многообразии 31

2.1 Рассматриваемые статистики 31

2.2 Основные результаты главы 34

2.3 Доказательство основных теорем главы 36

3 Выборочное оценивание непрерывных интегральных операторов 46

3.1 Постановка задачи 46

3.2 Иллюстративный пример 47

3.3 Рассматриваемые статистики и основные результаты главы 49

3.4 Доказательство основных теорем главы 52

4 Свойства процедур моделирования многообразий 52

4.1 Оценивание многообразий как задача вложения многообразий 53

4.2 Типичная схема алгоритмов вложения многообразий

4.2.1 Шаг первый: построение окрестности 54

4.2.2 Шаг второй: описание окрестностей 54

4.2.3 Шаг третий: глобальное описание

4.2.4 Шаг четвертый: расширение задачи для точек вне выборки 55

4.3 Основной результат главы 55

Заключение 58

Список литературы

• Основные результаты главы
• Основные результаты главы
• Рассматриваемые статистики и основные результаты главы
• Типичная схема алгоритмов вложения многообразий

Введение к работе

Актуальность темы

Развитие вычислительной техники и информационных технологий привело к возможности хранить, передавать по каналам связи и быстро обрабатывать большие массивы данных, осуществлять быстрый удаленный доступ к ним. Появление в результате таких возможностей “шквала данных”, называемого обычно парадигмой больших данных (Big Data), и новые возможности для работы с ними, позволили ставить и эффективно решать новые научные и прикладные задачи в области промышленности и сельского хозяйства, биологии и медицины, обработки сигналов, речи, текстов и изображений, и др. Для решения таких задач были развиты методы работы с большими данными, научную основу которым составляет новая мультидисциплинарная область знаний, выделившаяся в XXI веке в отдельную академическую и университетскую дисциплину наука о данных (Data Science), в которой сконцентрированы методы математики и статистики, распознавания образов, визуализации и машинного обучения, информационных технологий и интеллектуального анализа данных.

Понятие большие данные включает в себя не только большой объем данных, но и их высокую размерность, так как реальные данные обычно имеют очень высокую размерность (например, размерность цифровой черно-белой фотографии равна числу ее пикселей и может достигать сотен тысяч; изображения головного мозга, получаемые ежесекундно с помощью функциональной магнито-резонансной томографии, имеют размерность порядка полутора миллионов). Однако многие традиционные методы и алгоритмы становятся неэффективными или просто неработоспособными для данных высокой размерности (не только в вычислительном, но и в статистическом смысле), и этот феномен назван проклятием размерно-сти¹. Известный статистик Д. Донохо сказал в 2000 году на конференции, посвященной математическим вызовам 21-го века: “мы можем с полной уверенностью сказать, что в наступающем веке анализ многомерных данных станет очень важным занятием, и совершенно новые методы многомерного анализа данных будут разработаны, просто мы еще не знаем, каковы они будут”.

Однако совокупность конкретных “реальных” данных, полученных из реальных источников, в силу наличия различных зависимостей между компонентами данных и ограничений на их возможные значения, занимает, как правило, малую часть высокоразмерного пространства наблюдений,

¹Richard E. Bellman. Dynamic programming. Princeton University Press, 1957.

²David L. Donoho. High-dimensional data analysis: The curses and blessings of dimensionality. AMS conference on math challenges of 21st century, 2000.

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

Традиционные методы математической статистики в задаче снижения размерности рассматривают, в основном, лишь случай, когда высокоразмерные данные сосредоточены вблизи неизвестного низкоразмерного аффинного подпространства, которое можно оценить, например, с помощью метода главных компонент К. Пирсона. Однако многие реальные данные имеют нелинейную, “искривленную” структуру, для нахождения которой в прошлом веке были предложены различные эвристические методы нелинейного снижения размерности (например, репликативные нейронные се-ти³ или нелинейные методы многомерного шкалирования), свойства которых невозможно было исследовать строгими методами в силу отсутствия математической модели для обрабатываемых данных. Имелись лишь отдельные работы (например, работы В.М. Бухштабера^,) в которых строгие дифференциально-геометрические и статистические методы использовались при решении нелинейных статистических задач.

Лишь в 2000 году появилась первая математическая модель многомерных нелинейных данных, названная моделью многообразия (Manifold model), в соответствии с которой, высокоразмерные данные расположены на (или вблизи) неизвестного низкоразмерного нелинейного многообразия (многообразия данных), вложенного в высокоразмерное пространство наблюдений, а наблюдаемая выборка случайно извлекается из многообразия данных в соответствии с неизвестным вероятностным распределением на нем. Размерность многообразия данных также может быть неизвестной и оцениваться по выборке.

Область анализа данных, в которой статистические задачи рассматриваются в рамках этой модели, получила название моделирование многообразий (Manifold Learning) и в настоящее время является бурно раз-³G.E. Hinton, R.R. Salakhutdinov. Reducing the dimensionality of data with neural networks. Science, 2000.

⁴T.F. Cox, M.A.A. Cox. Multidimensional Scaling. Chapman and Hall/CRC, London, 2001.

⁵В. М. Бухштабер, В. К. Маслов. Факторный анализ и экстремальные задачи на многообразиях Грассмана. Математические методы решения экономических задач, № 7. Наука, 1977.

⁶V. M. Buchstaber. Time series analysis and Grassmannians. Applied problems of Radon transform, Amer. Math. Soc. Transl. Ser. 2, 162, Amer. Math. Soc., Providence, RI, 1994.

⁷H.S. Seung, D.D. Lee. The Manifold Ways of Perception. Science, 2000.

⁸Y. Ma, Y. Fu (eds.). Manifold Learning Theory and Applications. CRC Press, London, 2011.

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

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

Большинство работ по моделированию многообразий содержит описание различных процедур, свойства которых исследуются с помощью вычислительных экспериментов. Лишь в небольшом числе работ^, математически строго исследовались статистические свойства конкретных функций от данных (статистик). При этом известные фундаментальные методы анализа асимптотического поведения статистик, развитые во второй половине прошлого века, значительный вклад в которые внесли, в том числе, такие видные советские и российские исследователи как Л.Н. Большев, И.А. Ибрагимов, Р.З. Хасьминский, А.А. Боровков, Д.М. Чибисов и др., разработаны для данных на линейных подпространствах и непосредственно неприменимы для данных лежащих на нелинейных многообразиях.

В процедурах моделирования многообразий используются, как правило, три типа статистик:

1. локальные статистики, построенные по подвыборке, состоящей из точек попавших в малую окрестность выбранной точки, и оценивающие локальные и дифференциально-геометрические характеристики мно-⁹X. Huo and A.K. Smith. A Survey of Manifold-Based Learning Methods. Journal of Machine Learning Research, 2008.

¹⁰A. Kuleshov and A. Bernstein. Nolinear Multi-Output Regression on Unknown Input Manifold. Annals of Mathematics and Artifcial Intelligence, 2017.

¹¹G. Henry, A. Muсoz, D. Rodrнguez. Locally adaptive density estimation on Riemannian manifolds. Statistics and Operations Research Transactions, 2013.

¹²A. Smith, H. Zha, X. Wu. Convergence and Rate of Convergence of a Manifold-Based Dimension Reduction Algorithm. Advances in Neural Information Processing Systems, 2009.

¹³L. Rosasco, M. Belkin, E. De Vito. On learning with integral operators. The Journal of Machine Learning Research, 2010.

гообразия (касательное пространство¹⁴, Риманов метрический тен-зор, и др.) в выбранной точке; распределение таких статистик зависит, в том числе, от локальных и дифференциально-геометрических свойств многообразия в рассматриваемой точке;

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

2. статистики, являющиеся результатом оптимизации глобальных статистик по этим параметрам.

Оптимизация выборочных интегральных статистики во многих случаях сводится к оптимизации выборочных квадратичных форм от этих параметров (алгоритмы IsoMap, Locally-linear Embedding, Local Tangent Space Alignment, Laplacian Eigenmaps, Hessian Eigenmaps, Grassmann&Stiefel Eigenmaps, и др.), решение которых основаны на спектральных методах (обобщенные задачи на собственные векторы). Решение таких выборочных задач часто сводится к решению спектральных непрерывных задач на многообразии. Например, оптимизируемая выборочная квадратичная форма в алгоритме Laplacian Eigenmaps^14,19 является выборочным аналогом оператора Лапласа-Бельтрами на определенном классе функций, заданных на многообразии данных, а наилучшие низкоразмерные представления сходятся к конкретным собственным функциям этого оператора¹³.

Однако до сих пор отсутствуют результаты об асимптотическом поведении статистик на многообразиях для достаточно общих классов, включающих в себя как ранее неисследованные статистики из различных алгоритмов, так и новые статистики для создаваемых алгоритмов с желаемы-¹⁴A. Singer, H.-T Wu. Vector difusion maps and the connection Laplacian. Communications on Pure and Applied Mathematics, 2012.

¹⁵D. Perrault-Joncas and M. Meila. Non-linear Dimensionality Reduction: Riemannian Metric Estimation and the Problem of Geometric Recovery. In: arXiv:1305.7255v1, 2013.

¹⁶J. B. Tenenbaum, V. de Silva, J. C. Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science, 2000.

¹⁷S. Roweis and L. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 2000.

¹⁸Z. Zhang and H. Zha. Principal Manifolds and Nonlinear Dimension Reduction via Local Tangent Space Alignment. SIAM Journal on Scientifc Computing, 2004.

¹⁹M. Belkin, P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 2003.

²⁰D. Donoho and C. Grimes. Hessian eigenmaps: locally linear embedding techniques for high-dimensional data. Proc. Natl. Acad. Sci. USA, 2003.

²¹A.V. Bernstein, A.P. Kuleshov. Manifold Learning: generalizing ability and tangent proximity. International Journal of Software and Informatics, 2013.

²²L. K. Saul, K. Q. Weinberger, J. H. Ham, F. Sha, and D. D. Lee. Spectral methods for dimensionality reduction. Semisupervised Learning, MIT Press, 2006.

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

Основные задачи исследования

Для достижения сформулированной цели были поставлены и решены следующие взаимосвязанные асимптотические статистические задачи:

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

2. исследование асимптотического поведения выбранного класса локальных статистик в окрестности рассматриваемой точки, зависящего, в том числе, от дифференциально-геометрических свойств многообразия в этой точке;

3. исследование асимптотического поведения глобальных (интегральных) статистик получаемых путем усреднения локальных статистик по точкам выборки;

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

Основные выносимые на защиту результаты и их новизна

Все приведенные ниже результаты диссертации являются новыми и получены лично соискателем:

5. найдены асимптотическое распределение числа точек в медленно убывающей окрестности выбранной точки многообразия и условное распределение этих точек. Получена равномерная по многообразию верхняя оценка для вероятности больших уклонений числа точек в окрестности от своего среднего значения;

6. найдено асимптотическое распределение локальных статистик рассматриваемого класса, ранее известное лишь для конкретных статистик (оценки элементов локальной выборочной ковариационной мат-рицы¹⁴ и оценки оператора Лапласа-Бельтрами специального вида).

²³E. Gine and V. Koltchinskii. Empirical graph Laplacian approximation of Laplace-Beltrami operators: large sample results.High Dimension Probability, 51:238-259, 2006.

Получена равномерная по многообразию верхняя оценка на вероятности больших уклонений локальных статистик от их средних значений;

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

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

Основные методы исследования

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

Теоретическая ценность и практическая значимость

Работа носит теоретический характер. Её результаты могут быть использованы для изучения свойств и совершенствования существующих алгоритмов анализа лежащих на многообразии данных, а также, для создания новых алгоритмов с желаемыми свойствами. В частности, результаты диссертации были использованы в работах по развитию новых алгоритмов моделирования многообразий и их использованию в прикладных задачах анализа данных [4-11], написанных в соавторстве с соискателем. В этих работах лично соискателю принадлежат результаты и выводы, основанные на полученных в диссертации результатах применительно к конкретным рассматриваемым в этих работах статистикам.

Результаты апробации

Результаты диссертации были доложены на следующих мероприятиях:

1. семинар отдела теории вероятностей и математической статистики МИАН (2017, Москва, Россия);

2. семинар “Теория риска и смежные вопросы” кафедры математической статистики ВМК МГУ (2016, Москва, Россия);

3. математические и статистические семинары ИППИ РАН (Москва, Россия): Добрушинской математической лаборатории (2016), “Статистический кластерный анализ” (2016), сектора интеллектуального анализа данных (2014);

4. междисциплинарные школы-конференции “Информационные технологии и системы”: 40-я (2016, Санкт-Петербург, Россия), 39-я (2015, Сочи, Россия), 37-я (2013, Калининград, Россия);

5. International Conference on Algebra, Analysis and Geometry (2016, Kazan, Russia);

6. The 8th International Conference on Machine Vision, ICMV (2015, Barcelona, Spain);

7. The 14th International Conference on Machine Learning and Applications (2015, Miami, USA; ICMLA);

8. The third international symposium on statistical learning and data sciences, SLDS (2015, Royal Holloway, University of London, United Kingdom);

9. International IEEE Conference on Data Science and Advanced Analytics, DSAA (2015, Paris, France);

10. Yandex School of Data Analysis Conference “Machine Learning: Prospects and Applications” (2015, Berlin, Germany);

11. Premolab-WIAS Workshop “Advances in predictive modeling and optimization” (2014, WIAS, Berlin, Germany);

12. International Workshop on Statistical Learning (2013, Moscow, Russia);

13. The 29th European Meeting of Statisticians, EMS (2013, Budapest, Hungary);

14. Neural Information Processing Systems Conference (NIPS 2013, Lake Tahoe, USA).

Публикации

Список работ автора по теме диссертации приведен в конце диссертации. Основные результаты диссертации содержатся в работах автора [1-3]. Работы [1-7] опубликованы в изданиях, индексируемых в системах Scopus или Web of Science.

Структура и объем работы

Основные результаты главы

Окрестность каждой точки X Є М близка к g-мерному линейному касательному пространству Тх(М) в точке X. Дифференцирование на многообразии немного отличается от дифференцирования в Евклидовых координатах в Жк. Отличия носят преимущественно технический характер, и основной особенностью является то, что производные определены лишь в направлениях из касательного пространства Тх(М) (см. приложение A.3).

В достаточно малой окрестности X Є М существует взаимнооднозначное соответствие соответствие между точками многообразия М и элементами касательного пространства Тх(М). В такой окрестности векторы V Є Тх(М) задают координаты. Будем записать V в полярных координатах: V = t0, t Є (0, оо) и в Є Sq-i = Sp-i ПТх(М), где Sq-i — единичная сфера в g-мерном пространстве. Такие координаты называются Римановыми (см. Приложение A.3).

Элемент объема многообразия и g-мерный объем в касательном пространстве связаны следующей леммой: Лемма 1. (см. [42J)- Риманова мера в полярных координатах в окрестности точки X Є М имеет вид dV(expx(t6)) = J(t,0)dtdO, где для некоторых t Є [0,t], X Є {expxt6} и в Є ТХ(М): J(t, в) = tq + tq+ Ricx(0, 0) + 0(tq+ ), J(t,Q) = tq + tq+ Ricx(Q,Q), где Ricx{0,0) — кривизна Риччи (66) в точке X в направлении 9, X = expx(t6), t Є [0,]; в Є ТХ(М). Расстояние между близкими точками многообразия в р-мерном пространстве и расстояние между ними в g-мерных Римановых координатах [14] связано Леммой: Лемма 2. (см. [43J). Для X, X Є М; таких, что X = expx(t6), для малых t (и малых h = \\Х — Х\\): 1 о ,, t = а -\—\\ilx{v}0)\\ а + и(п ); 24 t = h -\—\\Нх(в, в)\\ h , где X Є {ехрхЩЇ Є [0,]}, в Є ТХ(Ш), IIx{V,V) — вторая фундаментальная форма многообразия (61). Значения правых частей Леммы 1 и 2 могут быть ограничены в Предположениях M1-M8: Лемма 3. Для X є М и в є Тх(М) П Sp-\: Си \\IIxw, 0)\\ Сц = — q, Cj где Си — максимальный элемент Гессиана отображения f (9), cj — минимальное собственное значение метрического тензора М (7). Лемма 4. Для X Є М и в Є Тх(М) П S,p_1(l): \\Ricx{0,0)\\ Стс = 2q h +g IOGTT h 46я /cj} Cj Cj где Сн — максимальный элемент Гессиана отображения f (9), cj и Cj — минимальное и максимальное собственные значения метрического тензора М (7) и (8), Ст — максимальная норма третьей производной (10). Доказательства Лемм 3 и 4 приведены в Приложении A.3. В работе используются локальные и интегральные леммы Маувра-Лапласа для медленно стремящейся к нулю вероятности успеха в схеме серий. В классической формулировке, вероятность предполагается фиксированной. Однако, доказательство почти не изменится, если предположить, что параметр р убывает с увеличением размера выборки N, но р N — оо при N — оо. Единственное отличие состоит в разложении функций по малому параметру 1

Лемма 5. (Локальная Муавра-Лапласа для медленно убывающей вероятности успеха). Пусть вероятность успеха в схеме Бернулли рм 0 зависит от размера выборки N и q = 1 — pjy. Также пусть р N — оо при N — оо. Тогда при N — оо для числа успехов к, такого что (L р

Лемма 6. (интегральная Myавра-Лапласа для убывающей вероятности успеха). Пусть вероятность успеха в схему Бернулли р 0 зависит от числа испытаний N, и q = 1 — рм- При этом р N — оо при N — оо. Обозначим Рм(к) = CNpNqN , PN(a, b] = J2a z b PN(NPN + Zy/NpNqN). Тогда Л/27Г sup —oo a 6 oo PN{a, b] = ЄХ13(—Z і A jCLZ 27Г a — 0, n — oo. Леммы 5 и 6 доказаны в Приложении B.1. 1.4.3 Вероятность больших уклонений для ограниченных случайных величин Для оценивания вероятности больших уклонений будем использовать следующую лемму доказанную в Приложении B.2: Лемма 7. Пусть \\ XN независимые одинаково распределенные случайные величины, E%i оо; \х\ — E%i С оо и константы mi,... ,шлг такие, что maxk=i,...,N \тк Xk\ т- Обозначим у = -л? У\ і У/г — mi- и а2 = Е(УІ — ЕУІ)2. Тогда для Н 2С при 0 ж т?: /V _/V fc=l А.л л VA.J- A.J- Ц Р(х х а + т) ехр(—х а N/A), Р(х —х о- — т) ехр(—х а N/A) и при х т?: J-[ Р(х х а + т) ехр(—ха N/AH), Р(х —х а — т) ехр(—ха N /АН). 1.4.4 Замена области интегрирования Обозначим ВЄ(Х) — пересечение евклидовой є-окрестности точки X Є М как точки р-мерного пространства с многообразием М: ВЄ(Х) = {Х\Х Є М П \Х — Х\ є}. (18) Обозначим ВЄ(Х) — є окрестность в локально-римановых координатах с центром в X Є М: ВЄ(Х) = {X\3V Є Тх(М): X = expx(V) П \V\ є}. (19) Обозначим Мє — множество внутренних точек, отстоящих от границы не менее чем на є: Мє = {X є MW Є Tx(M) П \V\ є: expx(V) Є М} (20) Лемма 8. Для произвольной ограниченной функции д(Х,Х) = g(X,t,0), є Cint и X Є МЄ,Х є М, в є Тх(М) П Sp-i выполнено giX XjdviX) — 9\Х, X )dV (X ) ВЄ(Х) ВЄ(Х) 8 Vq sup \g(X, X) eq+ , x,x где c(M) — число обусловленности (M7), Vq — объем q-мерного шара (17), Сц и Ста — константы из Лемм 3 и 4, ограничивающие вторую квадратичную форму и кривизну Риччи, /24 (\/2 у тах{1, . 1 24-(v 2 — 1) 1 Cint = niin —, ——z, —= (21) с(М) тах{1,6// 2\/Сш Лемма доказана в разделе B.3. 1.4.5 Конечные сети Для доказательства равномерности оценок будем использовать дополнительное построение. 6-сеть метрического пространства Z есть множество 1inet(d) С Z такое, что для любой точки Z Є Z найдётся точка Znet Є ЪпеЬ{Ь\ удалённая от Z не более чем д. Так как множество Мє (19) точек, удаленных от границы не менее чем на є, является подмножеством М и многообразием для которого также выполнены M2 и M4, то применяя к нему лемму 11, получаем Следствие 2. (Следствие леммы 11). Для каждого 5 0 и є 0 найдется с ТЙ лт Ґ- ( 2а,/» \ V конечная о-сеть JML, содержащая не долее= элементов, где а 0 — ребро описанного вокруг М р-мерного гиперкуба.

Основные результаты главы

Пусть F = {ф} — гильбертово (под)пространство функций определенных на многообразии M со скалярным произведением (фі, фо) = M фл (X) ф2(Х)іі(сІХ), /І — вероятностная мера на M, удовлетворяющие сформулированным в диссертации условиям регулярности. Пусть L — действующий на F линейный самосопряженный оператор Гильберт-Шмидта с неположительными собственными значениями.

Рассмотрим задачу максимизации функционала / ф(Х) Ьф(Х)с1ц(Х), (49) по нормированным функциям ф Є F ((/ 2, = M\ф(Х)\2(1и,(Х) = 1) ор-тогональным собственному подпространству Fo оператора L, например ядру Ker(L) = {ф Є F : Ьф = 0} оператора L. Очевидно, что решение этой задачи даётся собственной функцией ф (Х) оператора L с наибольшим ненулевым собственным значением А .

Такие задачи естественным образом возникают в моделировании многообразий. Например, задача минимизации функционала LM \\7ф(Х)\2(Ііі(Х) по нормированным функциям 0, естественным образом возникающая при построении низкоразмерной параметризации многообразия данных (снижении размерности)19 21, сводится к решению рассматриваемой оптимизационной задачи с оператором Лапласа-Бельтрами L = ALB (у усеченным спектром), являющимся обобщением стандартного оператора Лапласа на случай многообразия.

В статистической постановке, многообразие M и мера /І неизвестны, и исследуется задача оценивания ф по конечной выборке Хдг, состоящей из точек многообразия M случайно и независимо друг от друга выбранных в M в соответствии с вероятностной мерой /І.

Оптимизируемый функционал (49) квадратичен по 0, поэтому его выборочный аналог естественно также строить в виде квадратичной формы от вектора ф N = (Ф( і) Ф( м))1, состоящего из неизвестных значений функции ф в точках выборки Хдг: интеграл (49) заменяется квадратичной оценкой ф(Х) ьф{Х)ац{Х) — у ф\Хп) ьф{Хп) ф N WN ф N, M N t \ в последнем члене вектор, состоящий из величин {(Ьф)(Хп),п = 1,2,..., iV} заменен оценкой вида WN- ф лг, в котором WN — некоторая явно построенная по оператору L матрица размера N х N. В диссертации рассматривается конкретный способ13 19 построения такой матрицы, обеспечивающий состоятельность этой оценки.

Рассмотрим задачу максимизации квадратичной формы Ф N WN Ф N (50) по вектору ф при условиях нормировки \фк\2 = 1 и ортогональности ядру матрицы Кег(\]у) = {фм : WN ф N = Одг}, где ON — вектор из N нулей. Решение этой задачи даётся собственным вектором ф м = (фм(Хі), фу{Х2), фу{Х ))т матрицы WN с наибольшим ненулевым собственным значением vN. По построенным оценкам (фм(Хі), фм(Х2), ф (Х ) значений неизвестной функции ф (Х) в точках выборки, с использованием стандартных методов ядерного непараметрического оценивания29, можно построить оценку ф х(Х), функции ф (Х) в произвольной точке X. В диссертации рассматривается конкретная оценка фм(Х) = — п= —S , (51) в которой ядро КЄ(Х,Х ) описано в Главе 2. 3.2 Иллюстративный пример Пусть многообразие М = [—7г,7г] С М1. На нем существует естественная параметризация М = {ХХ Є [—7г,7г]}, Однако, любая строго монотонная функция д: [—7г,7г] — К. также задает параметризацию на М: М = {Х ЇХ Є д 1([—7Г, 7г])}. Следовательно, параметризаций бесконечно много. Поэтому, что бы задача нахождения параметризации имела единственное решение, можно сформулировать оптимизационную задачу. Например, / {){) — max, (52) при условиях нормировки LM()2 = 1, где F — пространство бесконечно дифференцируемых функций на М, = А = Л — оператор Лапласа. В про-странстве F оператор А имеет базис (ненормированных) собственных функций: 1, , sin , cos ,..., sin , cos ,... соответствующих собственным числам 0,0,-1,-1,...,-2,-2,... , где Є N. Если дополнительно потребовать, чтобы была ортогональна константной функции L () l = О, то реше-ние (52) будет задаваться единственной допустимой собственной функцией, отвечающей минимальному собственному числу 0, то есть () = -п-, которая задает выделенную параметризацию на М (обладающую минимальным квадратом первой производной из теоремы Стокса).

Пусть теперь многообразие М не известно (но по-прежнему является отрезком [—,] прямой), а задана лишь конечная выборка Хдг = {і,... ,дг} на нём (например, i.i.d. из равномерного распределения). При этом по ней требуется оценить параметризацию (). Оценивание можно разбить на два этапа: оценивание () для Є Хдг и оценивание () для Є М по оценкам { (і),..., (дг)} с предыдущего шага оценивания. Второй шаг может быть реализован, например, непараметрическим оцениванием (51) і ELiE(,n) N(n) EZ=iE(,n) результаты о качестве которого получены во второй Главе. А для оценивания { (і),..., ( )} на первом шаге возможно сформулировать выборочную оптимизационную задачу. Оптимизируемый функционал (52) квадратичен по , поэтому его выборочный аналог естественно также строить в виде квадратичной формы от вектора N = ((\),..., ( )) 1, состоящего из неизвестных значений функции в точках выборки Хдг: интеграл (52) заменяется квадра

Рассматриваемые статистики и основные результаты главы

Дифференцирование многообразий понимается стандартно. Напомним, что это означает. В р-мерном действительном пространстве Rр для любой точки Z Є Rр и любого направления 7eRp\ {0} легко определить производную функции по заданному направлению в заданной точке. Однако, для X Є X малое смещение не во все направления оставляет результат переноса на многообразии. Точнее, для многообразия X, покрытого картой (B,/) с полноранговой матрицей Якоби Jj{f l{X)), то в точке XQ = /(&о) локально многообразие ведет себя почти как g-мерное линейное пространство — касательное пространство Тх(X), которое можно определить как линейное пространство, натянутое на р-мерные вектор-столбцы матрицы где верхний индекс обозначает компоненту вектора. То есть, дифференцировать можно только по направлениям V{XQ) Є Тх0(X).

Как видно из записи, касательное пространство Тх0(X) зависит от точки многообразия Хо, в которой оно строится. Поэтому, в общем случае, на многообразии нельзя определить производную скалярной функции (р(Х) как предел отношений изменения функции ср при переходе от точки Хо к точке Xo+tV(Xo) к длине tV(Xo), так как Xo + tV(Xo) X и значения функции є в этой точке не определена в общем случае. Поэтому, вместо Хо + tV(Xo) рассматривают кривую 7(), t Є (—є, є) на многообразии такую, что 7(0) = XQ и ДТ(О) = V(Xn). Производная скалярной функции определяется как (p{ {t)) — (/9(7(0)) cpijit)) — ср(Хо) VwxoM o) = Inn = lim . Замечание 7. В случае евклидового пространства Жт существует его тождественное накрытие: В = Жт и f(b) = Ъ, то есть X = Ъ. Поэтому в качестве кривой j(t) можно выбрать j(t) = XQ + tV(Xo) и ковариантная производная функции ср совпадает с обычной производной по направлению.

Рассмотрим ограничение векторного поля V(X) Є Тх(Х), X Є X на кривую j(t): V{t) = V{l{t))i t (—eie)- Производная V(t) может быть определена как обычно: dV V (t + К) — V (t) (t) = lim , at h o t где t Є (—є, є). Однако, производная - -(t) может не лежать в Т с+ч(Х). Поэтому определяют ковариантную производную Щ-(Н) как проекцию rr(t) на TLmfX). Далее, рассмотрим уравнение —jr{t) = О , (60) // I (J ) = \/\/ где VK Є Т7(о)(Х). Решение VK() уравнения (60) существует и называется параллельным переносом вектора W{ {{))) вдоль кривой j{t) и обозначается Теперь, чтобы определить производную векторного ПОЛЯ W(X), X Є X, вдоль кривой 7(0? t Є (—є?є) будем параллельно переносить VK(7( )) в точку Хо = 7(0)- Результат параллельного переноса P7(o),7(t)VK(7()) 7(0)( ) поэтому в Т7(о)(Х) определена разность P7(o);7(i)VK(7()) — W{ {{))) и определена ковариантная производная векторного поля W(X) на X: V\/(xn)M/r( o) = Hm , t-ю t где 7: (—є,є) чХи 7(0) = о X, 7 (0) = (- о) Є х0(Х).

Замечание 8. В случае евклидового пространства Ш171 решением уравнения (60) является Р7(О)Л(І)И/Г(7( )) = W(y(t)) = W(XQ + tV(Xo)) и ковариантная производная векторного совпадает с обычной производной по направлению: т-, Т17/,, W(Xo+ tV(Xo))— W(Xo) \/y(xn)vV{Xo) = lim . t-ю t Будем обозначать ковариантную производную в направлении V Є Тх(Х)\ {0} в точке X как Vy. Ковариантная производная обладает привычными свойствами производной по направлению, например линейностью Vi,V2 Є Тх(Х) \ {0}, «і, «2 Є Ж. \ 0 при a\V\ + (У.2У2 ф 0: Vaiy1+a2y2 = aiVvi + a2Vy2. A.2 Квадратичные формы многообразия и кривизна Риччи

В работе предполагается, что метрический тензор многообразия X порожден его вложением в многомерное пространство W. Это означает, что скалярное произведение для векторов V, W Є Тх(Х) является ограничением скалярного произведения Шр на Тх(Х), то есть в ортонормированном базисе выражается билинейной формой IxiV-jW) = VTW.

Первая квадратичная форма многообразия — это форма длины векторов касательного пространства (и позволяет вычислять длины кривых): ІхІУі V) = V У Запишем координаты вектора V в базисе, заданном параметризацией (В, /): Ъ = f (X); V = Jf(b)av, OLV Є Ж9, civ = (Jf(b) Jf(b) ) J fib) У] Ix(av) = av (Jfib) Jf(b)) OLV. Вторая билинейная форма многообразия показывает ортогональную касательному пространству составляющую изменения векторов касательного про странства вдоль разных направлений касательного пространства V, W Є Тх(Х). Запишем выражение второй билинейной формы IIx{V,W) в базисе, заданном параметризацией (В,/), в точке X = fib):

Обозначим R = (Rij)1j=i — матрица порядка q. Для в Є Тх(Х): сіє = (jf(b)T //(&)) Jf(b)T6. Кривизна Риччи в направлении в в точке X: Ricx(0,9) = (1Q R ад. (66) Кривизна Риччи характеризует отличие Евклидового элемента объема от элемента объема многообразия.

Для малой окрестности точки XQ Є X отображение X ь- V Є Тх(Х): = /(7(1)), где 7: 7 0 = Хп и дт 0 = I/, определяет взаимнооднозначное соответствие между окрестностью точки Хо и окрестностью точки 0 в Тх0(Х). Обратное отображение называют экспоненциальным и обозначают X = expY (V)- (67) В данной окрестности векторы V Є Тх0(Х) задают координаты. Эти координаты называются локально римановыми координатами. Замечание 9. В случае евклидового пространства М = Ш.т, касательное пространство TV(X) = Шт и expу (V) = Xo + V для любого V Є TV(X) (то есть, результат справедлив для произвольной окрестности Хо).

Свяжем теперь расстояние между близкими точками многообразия в р-мерном пространстве и расстояние в между их q мерными римановыми координатами связаны Леммами 1 и 2. При этом Леммы 3 и 4 (грубо) оценивают сверху вторую фундаментальную форму и кривизну Риччи через достаточно гладкую параметризацию многообразия. Докажем их:

Доказательство леммы 3. Для произвольной точки Ъ Є В обозначим V\,..., Vq — ортонормированный базис собственных векторов матрицы Jj(b)TJj(b). Обозначим Ai,..., \ соответствующие Vi,... , Vq собственные значения.

Типичная схема алгоритмов вложения многообразий

Свяжем теперь расстояние между близкими точками многообразия в р-мерном пространстве и расстояние в между их q мерными римановыми координатами связаны Леммами 1 и 2. При этом Леммы 3 и 4 (грубо) оценивают сверху вторую фундаментальную форму и кривизну Риччи через достаточно гладкую параметризацию многообразия. Докажем их:

Доказательство леммы 3. Для произвольной точки Ъ Є В обозначим V\,..., Vq — ортонормированный базис собственных векторов матрицы Jj(b)TJj(b). Обозначим Ai,..., \ соответствующие Vi,... , Vq собственные значения.

Запишем координаты в Є Тд5)(Х): Щ = 1 в базисе Vi,...,Vq: в = Хл=і РІУІ, где Хл=і Pi = 1. Учитывая (7), преобразуем

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

Докажем локальную и интегральные леммы Муавра-Лапласа для параметра успеха, медленно стремящегося к нулю. Доказательство леммы 5. Доказательство во многом повторяет доказательство локальной предельной теоремы из [57] и существенно использует формулу Стирлинга N\ = V2TTN е N (1 + R(N)), где R(N) = 1 1ш + ооо1дг2 — м1ІІп + OdrTj), и 177Х7 R(N) 1T1f, N 1 может быть выражена через числа Бернулли. Для удобства будем опускать индекс N у PN И qjy.

Доказательство. Так как собственные числа матрицы Якоби параметризации (В,/) ограничены по предположению M4 и множество В СІ5 ограничено по предположению M2, то множество МсМр ограничено. Так как Мс1р ограничено, оно может быть помещено в гиперкуб Са с ребром а 0. Пусть 6 0 — некоторое число. Рассмотрим равномерную сетку G(5) для куба с расстояниями между точками вдоль каждого ребра не превосходящим -т=. Число точек ребрами не превосходящими —у. Поэтому для каждой точки Z из куба Са расстояние между Z и G(5) не превосходит длины диагонали малого, которому она принадлежит: где для точки Z Є Шр и множества А С Мр, d(Z,A) = miz eA\\Z — Z \\ — расстояние от точки до множества. Поэтому во множестве G(6) для каждой точки X Є X содержится точка, удаленная от нее не более чем на д. Но G(6) (/і X.

Обозначим Bs(X) шар с центром X и радиусом д. Определим G(6): Для каждой точки X Є G(6/2), если В/2(Х) = В(Х) П М = 0, то выберем точку X из В и поместим ее в G(). Множество G() является (5-сетью для X и оно состоит не более чем из (у точек. U Докажем лемму о выполнении системы событий Лемма 12. Пусть каждое из событий Аі,...,Ам наступает с вероятностью не меньше, чем р. Тогда все они наступают одновременно с вероятностью не меньше Р(Г\ =іАт) 1 — М (1 — р).

Доказательство. Обозначим А — дополнение борелевского множества А до множества элементарных исходов. Преобразуем Лемма 13 (четность главного члена F(X,X )). При d\2 функция (р(Х,в,0) — четная по в и функция (р1(Х,в,0) — нечетная по в. При d /2 функция (р(Х,в,0) — нечетная по в и функция (р1(Х,в,0) — четная по в.