Аппроксимации гауссовского процесса

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

Основные идеи

При статистическом моделировании часто удобно предполагать, что $y\in {\mathcal {Y}}$, исследуемое явление представляет собой гауссовский процесс , индексируемый $X\in {\mathcal {X}}={\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\dots {\mathcal {X}}_{d}$ который имеет среднюю функцию $\mu :{\mathcal {X}}\rightarrow {\mathcal {Y}}$ и ковариационная функция $K:{\mathcal {X}}\times {\mathcal {X}}\rightarrow \mathbb {R}$. Можно также предположить, что данные $\mathbf {y} =(y_{1},\dots ,y_{n})$ – значения конкретной реализации этого процесса для показателей $\mathbf {X} =X_{1},\dots ,X_{n}$.

Следовательно, совместное распределение данных можно выразить как

$\mathbf {y} \sim {\mathcal {N}}(\mathbf {\mu } ,\mathbf {\Sigma } )$,

где $\mathbf {\Sigma } =\left[K(X_{i},X_{j})\right]_{i,j=1}^{n}$ и $\mathbf {\mu } =\left(\mu (X_{1}),\mu (X_{2}),\dots ,\mu (X_{d})\right)^{\top }$, т.е. соответственно матрица со значениями ковариационной функции и вектор со средними значениями функции по соответствующим (парам) индексам.Тогда отрицательное логарифмическое правдоподобие данных принимает форму

$-\log \ell (\mathbf {y} )={\frac {d}{2\pi }}+{\frac {1}{2}}\log \det(\mathbf {\Sigma } )+\left(\mathbf {y} -\mathbf {\mu } \right)^{\top }\mathbf {\Sigma } ^{-1}\left(\mathbf {y} -\mathbf {\mu } \right)$

Аналогично, лучший предсказатель $\mathbf {y} ^{*}$, значения $y$ для индексов $\mathbf {X} ^{*}=\left(X_{1}^{*},X_{2}^{*},\dots ,X_{d}^{*}\right)$, данные данные $\mathbf {y}$ имеет форму

$\mathbf {\mu } _{\mathbf {y} }^{*}=\mathbb {E} \left[\mathbf {y} ^{*}|\mathbf {y} \right]=\mathbf {\mu } ^{*}-\mathbf {\Sigma } _{\mathbf {y} ^{*}\mathbf {y} }\mathbf {\Sigma } ^{-1}\left(\mathbf {y} -\mathbf {\mu } \right)$

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

Самый затратный в вычислительном отношении компонент формулы лучшего предиктора — это инвертирование ковариационной матрицы. $\mathbf {\Sigma }$, который имеет кубическую сложность ${\mathcal {O}}(n^{3})$. Аналогичным образом, оценка вероятности включает в себя как расчет $\mathbf {\Sigma } ^{-1}$ и определитель $\det(\mathbf {\Sigma } )$ который имеет ту же кубическую сложность.

Аппроксимации гауссовского процесса часто можно выразить в терминах предположений о $y$ согласно которому $\log \ell (\mathbf {y} )$ и $\mathbf {\mu } _{\mathbf {y} }^{*}$ можно вычислить с гораздо меньшей сложностью. Поскольку обычно считается, что эти предположения не отражают реальность, вероятность и лучший предиктор, полученные таким образом, не являются точными, но они должны быть близки к своим исходным значениям.

Методы на основе моделей

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

Методы разреженной ковариации

Эти методы аппроксимируют истинную модель за счет разреженности ковариационной матрицы. Обычно каждый метод предлагает свой собственный алгоритм, который в полной мере использует преимущества шаблона разреженности в ковариационной матрице. Двумя выдающимися представителями этого класса подходов являются сужение ковариации и разделение доменов. Первый метод обычно требует метрики $d$ над ${\mathcal {X}}$ и предполагает, что для $X,{\tilde {X}}\in {\mathcal {X}}$ у нас есть $Cov(y(X),y({\tilde {X}}))\neq 0$ только если $d(X,{\tilde {X}})<r$ для некоторого радиуса $r$. Второй метод предполагает, что существуют ${\mathcal {X}}^{(1)},\dots ,{\mathcal {X}}^{(K)}$ такой, что $\bigcup _{k=1}^{K}{\mathcal {X}}^{(k)}$. Тогда при соответствующем распределении индексов по элементам разбиения и упорядочивании элементов $X$ ковариационная матрица является блочно-диагональной.

Методы разреженной точности

Это семейство методов предполагает, что матрица точности $\mathbf {\Lambda } =\mathbf {\Sigma } ^{-1}$ является разреженным и обычно определяет, какие из его элементов не равны нулю. Это приводит к быстрой инверсии, поскольку необходимо вычислять только эти элементы. Некоторые из известных приближений в этой категории включают подход, основанный на эквивалентности между гауссовыми процессами с ковариационной функцией Матерна и стохастическими уравнениями в уравнениях, периодического вложения и гауссовых процессов с ближайшим соседом. Первый метод применяется в случае $d=2$ и когда ${\mathcal {X}}$ имеет определенную метрику и использует тот факт, что сохраняется марковское свойство, что делает $\mathbf {\Lambda }$ очень редко. Второй расширяет область и использует дискретное преобразование Фурье для декорреляции данных, что приводит к получению матрицы диагональной точности. Третий требует метрики по ${\mathcal {X}}$ и использует так называемый эффект экранирования, предполагая, что $\mathbf {\Lambda } _{i,j}\neq 0$ только если $d(x_{i},x_{j})<r$, для некоторых $r>0$.

Методы разреженного фактора Холецкого

Во многих практических приложениях вычисление $\mathbf {\Lambda }$ сначала заменяется вычислениями $\mathbf {L}$, фактор Холецкого $\mathbf {\Sigma }$, и второй его обратный $\mathbf {L} ^{-1}$. Известно, что это более стабильно, чем простая инверсия. По этой причине некоторые авторы сосредотачиваются на построении разреженной аппроксимации фактора Холецкого прецизионных или ковариационных матриц. Одним из наиболее устоявшихся методов этого класса является приближение Веккья и его обобщение. Эти подходы определяют оптимальное упорядочение индексов и, следовательно, элементов $\mathbf {x}$ а затем предположим структуру зависимостей, которая сводит к минимуму заполнение коэффициента Холецкого. В этой структуре можно выразить несколько других методов: аппроксимацию с несколькими разрешениями (MRA), гауссовский процесс ближайшего соседа, модифицированный процесс прогнозирования и полномасштабную аппроксимацию.

Методы низкого ранга

Хотя этот подход включает в себя множество методов, общим допущением, лежащим в их основе, является предположение о том, что $y$, представляющий интерес Гауссов процесс, фактически является низкоранговым. Точнее, предполагается, что существует набор индексов ${\bar {X}}=\{{\bar {x}}_{1},\dots ,{\bar {x}}_{p}\}$ такой, что любой второй набор индексов $X=\{x_{1},\dots ,x_{n}\}$

$y(X)\sim {\mathcal {N}}\left(\mathbf {A} _{X}{\bar {\mathbf {\mu } }},\mathbf {A} _{X}^{\top }{\bar {\mathbf {\Sigma } }}\mathbf {A} _{X}+\mathbf {D} \right)$

где $\mathbf {A} _{X}$ это $p\times k$ матрица, ${\bar {\mathbf {\mu } }}=\mu \left(y\left({\bar {X}}\right)\right)$ и ${\bar {\mathbf {\Sigma } }}=K\left({\bar {X}},{\bar {X}}\right)$ и $\mathbf {D}$ является диагональной матрицей. В зависимости от метода и применения различные способы выбора ${\bar {X}}$ были предложены. Обычно $p$ выбирается значительно меньшим, чем $n$ что означает, что вычислительные затраты на инвертирование ${\bar {\mathbf {\Sigma } }}$ это управляемо( ${\mathcal {O}}(p^{3})$ вместо ${\mathcal {O}}(n^{3})$).

В более общем плане, помимо выбора ${\bar {X}}$, можно также найти $n\times p$ матрица $\mathbf {A}$ и предположим, что $X=\mathbf {A} \mathbf {\eta }$, где $\mathbf {\eta }$ являются $p$ значения гауссовского процесса, возможно, не зависящие от $x$. Многие методы машинного обучения попадают в эту категорию, такие как подмножество регрессоров (SoR), векторная машина релевантности , гауссов процесс с разреженным спектром и другие, и они обычно различаются по способу получения $\mathbf {A}$ и $\mathbf {\eta }$.

Иерархические методы

Общий принцип иерархических аппроксимаций состоит в многократном применении какого-либо другого метода, причем каждое последующее применение улучшает качество аппроксимации. Несмотря на то, что их можно выразить как набор статистических предположений, их часто описывают в терминах иерархической матричной аппроксимации (HODLR) или расширения базисной функции (LatticeKrig, MRA, вейвлеты). Иерархический матричный подход часто можно представить как повторное применение аппроксимации низкого ранга к последовательно меньшим подмножествам набора индексов. $X$. Расширение базовых функций основано на использовании функций с компактной поддержкой. Эти особенности затем могут быть использованы алгоритмом, который последовательно проходит через последовательные уровни аппроксимации. В наиболее благоприятных условиях некоторые из этих методов могут достичь квазилинейной ( ${\mathcal {O}}(n\log n)$) сложность.

Единая структура

Вероятностные графические модели обеспечивают удобную основу для сравнения аппроксимаций на основе моделей. В этом контексте значение процесса по индексу $x_{k}\in X$ тогда может быть представлена ​​вершиной в ориентированном графе, а ребра соответствуют членам факторизации совместной плотности $y(X)$. В общем, когда не предполагается никаких независимых отношений, совместное распределение вероятностей может быть представлено произвольным направленным ациклическим графом. Использование определенного приближения может быть выражено как определенный способ упорядочивания вершин и добавления или удаления определенных ребер.

Методы без статистической модели

Этот класс методов не определяет статистическую модель и не налагает допущений на существующую. Тремя основными членами этой группы являются алгоритм мета-кригинга, алгоритм заполнения пробелов и подход локального аппроксимированного гауссовского процесса. Первый разбивает набор индексов на $K$ компоненты ${\mathcal {X}}^{(1)},\dots ,{\mathcal {X}}^{(k)}$, вычисляет условное распределение для каждого из этих компонентов отдельно, а затем использует геометрическую медиану условных PDF-файлов для их объединения. Второй основан на квантильной регрессии с использованием значений процесса, близких к значению, которое пытается предсказать, где расстояние измеряется с точки зрения метрики набора индексов. Локальный приближенный гауссов процесс использует аналогичную логику, но строит действительный стохастический процесс на основе этих соседних значений.

Ссылки

• Лю, Хайтао; Онг, Ю-Сун; Шен, Сяобо; Цай, Цзяньфэй (2020). «Когда гауссов процесс встречается с большими данными: обзор масштабируемой GPS». Транзакции IEEE в нейронных сетях и системах обучения . ПП : 1–19. arXiv : 1807.01065 . дои : 10.1109/TNNLS.2019.2957109 . ПМИД   31944966 .
• Хитон, Мэтью Дж.; Датта, Абхируп; Финли, Эндрю О.; Фуррер, Рейнхард; Гиннесс, Джозеф; Гуханиеги, Раджарши; Гербер, Флориан; Грэмси, Роберт Б.; Хаммерлинг, Дорит; Кацфусс, Матиас; Линдгрен, Финн; Нычка, Дуглас В.; Сунь, Фуронг; Заммит-Мангион, Эндрю (2018). «Конкурс тематических исследований среди методов анализа больших пространственных данных» . Журнал сельскохозяйственной, биологической и экологической статистики . 24 (3): 398–425. дои : 10.1007/s13253-018-00348-w . ISSN   1085-7117 . ПМК   6709111 .
• Банерджи, Судипто (2017). «Многомерная байесовская геостатистика» . Байесовский анализ . 12 (2): 583–614. дои : 10.1214/17-BA1056R . ПМК   5790125 . ПМИД   29391920 .