Расхождение Штейна

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

Определение

Позволять ${\mathcal {X}}$ быть измеримым пространством и пусть ${\mathcal {M}}$ — набор измеримых функций вида $m:{\mathcal {X}}\rightarrow \mathbb {R}$. Естественное понятие расстояния между двумя распределениями вероятностей. $P$, $Q$, определенный на ${\mathcal {X}}$, обеспечивается интегральной вероятностной метрикой

$(1.1)\quad d_{\mathcal {M}}(P,Q):=\sup _{m\in {\mathcal {M}}}|\mathbb {E} _{X\sim P}[m(X)]-\mathbb {E} _{Y\sim Q}[m(Y)]|,$

где для целей изложения мы предполагаем, что ожидания существуют и что набор ${\mathcal {M}}$ достаточно богата, чтобы (1.1) действительно была метрикой множества вероятностных распределений на ${\mathcal {X}}$, то есть $d_{\mathcal {M}}(P,Q)=0$ тогда и только тогда, когда $P=Q$. Выбор набора ${\mathcal {M}}$ определяет топологические свойства (1.1). Однако для практических целей оценка (1.1) требует доступа как к $P$ и $Q$, что часто делает прямое вычисление (1.1) непрактичным.

Метод Штейна — это теоретический инструмент, который можно использовать для оценки (1.1). В частности, мы предполагаем, что можем идентифицировать оператор ${\mathcal {A}}_{P}$ и набор ${\mathcal {F}}_{P}$ вещественных функций в области ${\mathcal {A}}_{P}$, и то и другое может быть $P$-зависимая, такая, что для каждого $m\in {\mathcal {M}}$ существует решение $f_{m}\in {\mathcal {F}}_{P}$ к уравнению Штейна

$(1.2)\quad m(x)-\mathbb {E} _{X\sim P}[m(X)]={\mathcal {A}}_{P}f_{m}(x).$

Оператор ${\mathcal {A}}_{P}$ называется оператором Штейна , а множество ${\mathcal {F}}_{P}$ называется множеством Штейна . Подставляя (1.2) в (1.1), получаем верхнюю оценку

$d_{\mathcal {M}}(P,Q)=\sup _{m\in {\mathcal {M}}}|\mathbb {E} _{Y\sim Q}[m(Y)-\mathbb {E} _{X\sim P}[m(X)]]|=\sup _{m\in {\mathcal {M}}}|\mathbb {E} _{Y\sim Q}[{\mathcal {A}}_{P}f_{m}(Y)]|\leq \sup _{f\in {\mathcal {F}}_{P}}|\mathbb {E} _{Y\sim Q}[{\mathcal {A}}_{P}f(Y)]|$ .

Эта результирующая граница

$D_{P}(Q):=\sup _{f\in {\mathcal {F}}_{P}}|\mathbb {E} _{Y\sim Q}[{\mathcal {A}}_{P}f(Y)]|$

называется невязкой Штейна . В отличие от исходной интегральной вероятностной метрики $d_{\mathcal {M}}(P,Q)$, возможно, можно будет проанализировать или вычислить $D_{P}(Q)$ используя ожидания только в отношении распределения $Q$.

Примеры

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

Классическое несоответствие Штейна

Для распределения вероятностей $P$ с положительной и дифференцируемой функцией плотности $p$ на выпуклом множестве ${\mathcal {X}}\subseteq \mathbb {R} ^{d}$, границу которого обозначим $\partial {\mathcal {X}}$, комбинация оператора Ланжевена–Штейна ${\mathcal {A}}_{P}f=\nabla \cdot f+f\cdot \nabla \log p$ и классическое множество Штейна

${\mathcal {F}}_{P}=\left\{f:{\mathcal {X}}\rightarrow \mathbb {R} ^{d}\,{\Biggl \vert }\,\sup _{x\neq y}\max \left(\|f(x)\|,\|\nabla f(x)\|,{\frac {\|\nabla f(x)-\nabla f(y)\|}{\|x-y\|}}\right)\leq 1,\;\langle f(x),n(x)\rangle =0\;\forall x\in \partial {\mathcal {X}}\right\}$

дает классическое несоответствие Штейна . Здесь $\|\cdot \|$ обозначает евклидову норму и $\langle \cdot ,\cdot \rangle$ евклидов внутренний продукт. Здесь $\|M\|=\textstyle \sup _{v\in \mathbb {R} ^{d},\|v\|=1}\|Mv\|$ – ассоциированная операторная норма для матриц $M\in \mathbb {R} ^{d\times d}$, и $n(x)$ обозначает внешнюю единицу, нормальную к $\partial {\mathcal {X}}$ на месте $x\in \partial {\mathcal {X}}$. Если ${\mathcal {X}}=\mathbb {R} ^{d}$ тогда мы интерпретируем $\partial {\mathcal {X}}=\emptyset$.

В одномерном случае $d=1$Классическое несоответствие Штейна можно точно вычислить путем решения квадратичной программы с квадратичными ограничениями .

Расхождение графика Стейна

Первыми известными вычислимыми неточностями Стейна были графовые неточности Стейна (GSD). Учитывая дискретное распределение $Q=\textstyle \sum _{i=1}^{n}w_{i}\delta (x_{i})$, можно определить график $G$ с набором вершин $V=\{x_{1},\dots ,x_{n}\}$ и набор кромок $E\subseteq V\times V$. Из этого графа можно определить граф, множество Штейна, как

${\begin{aligned}{\mathcal {F}}_{P}={\Big \{}f:{\mathcal {X}}\rightarrow \mathbb {R} ^{d}&\,{\Bigl \vert }\,\max \left(\|f(v)\|_{\infty },\|\nabla f(v)\|_{\infty },{\textstyle {\frac {\|f(x)-f(y)\|_{\infty }}{\|x-y\|_{1}}}},{\textstyle {\frac {\|\nabla f(x)-\nabla f(y)\|_{\infty }}{\|x-y\|_{1}}}}\right)\leq 1,\\[8pt]&{\textstyle {\frac {\|f(x)-f(y)-{\nabla (x)}{(x-y)}\|_{\infty }}{{\frac {1}{2}}\|x-y\|_{1}^{2}}}\leq 1},{\textstyle {\frac {\|f(x)-f(y)-{\nabla f(y)}{(x-y)}\|_{\infty }}{{\frac {1}{2}}\|x-y\|_{1}^{2}}}\leq 1},\;\forall v\in \operatorname {supp} (Q_{n}),(x,y)\in E{\Big \}}.\end{aligned}}$

Комбинация оператора Ланжевена – Штейна и множества графа Штейна называется невязкой графа Штейна (GSD). GSD на самом деле является решением конечномерной линейной программы размером $E$ настолько низко, насколько линейно в $n$, что означает, что GSD может быть эффективно вычислен.

Несоответствие ядра Штейна

Супремум, возникающий при определении невязки Штейна, можно оценить в замкнутой форме, используя тот или иной выбор множества Штейна. Действительно, пусть ${\mathcal {F}}_{P}=\{f\in H(K):\|f\|_{H(K)}\leq 1\}$ быть единичным шаром в (возможно, векторном) воспроизводящем ядерном гильбертовом пространстве. $H(K)$ с воспроизводящим ядром $K$, элементы которого находятся в области определения оператора Штейна ${\mathcal {A}}_{P}$. Предположим, что

• За каждое фиксированное $x\in {\mathcal {X}}$, карта $f\mapsto {\mathcal {A}}_{P}[f](x)$ является непрерывным линейным функционалом на ${\mathcal {F}}_{P}$.
• $\mathbb {E} _{X\sim Q}[{\mathcal {A}}_{P}{\mathcal {A}}_{P}'K(X,X)]<\infty$.

где оператор Штейна ${\mathcal {A}}_{P}$ действует на первый аргумент $K(\cdot ,\cdot )$ и ${\mathcal {A}}_{P}'$ действует на второй аргумент. Тогда это можно будет показать что

$D_{P}(Q)={\sqrt {\mathbb {E} _{X,X'\sim Q}[{\mathcal {A}}_{P}{\mathcal {A}}_{P}'K(X,X')]}}$,

где случайные величины $X$ и $X'$ в ожидании независимы. В частности, если ${\textstyle Q=\sum _{i=1}^{n}w_{i}\delta (x_{i})}$ представляет собой дискретное распределение на ${\mathcal {X}}$, то невязка Штейна принимает замкнутый вид

$D_{P}(Q)={\sqrt {\sum _{i=1}^{n}\sum _{j=1}^{n}w_{i}w_{j}{\mathcal {A}}_{P}{\mathcal {A}}_{P}'K(x_{i},x_{j})}}.$

Невязка Штейна, построенная таким образом, называется ядерной невязкой Штейна. и конструкция тесно связана с теорией вложения в ядро ​​вероятностных распределений .

Позволять $k:{\mathcal {X}}\times {\mathcal {X}}\rightarrow \mathbb {R}$ быть воспроизводящим ядром. Для распределения вероятностей $P$ с положительной и дифференцируемой функцией плотности $p$ на ${\mathcal {X}}=\mathbb {R} ^{d}$, комбинация оператора Ланжевена--Стейна ${\mathcal {A}}_{P}f=\nabla \cdot f+f\cdot \nabla \log p$ и набор Штейна

${\mathcal {F}}_{P}=\left\{f\in H(k)\times \dots \times H(k):\sum _{i=1}^{d}\|f_{i}\|_{H(k)}^{2}\leq 1\right\},$

связанный с матричным воспроизводящим ядром $K(x,x')=k(x,x')I_{d\times d}$, дает несоответствие ядра Стейна с

${\mathcal {A}}_{P}{\mathcal {A}}_{P}'K(x,x')=\nabla _{x}\cdot \nabla _{x'}k(x,x')+\nabla _{x}k(x,x')\cdot \nabla _{x'}\log p(x')+\nabla _{x'}k(x,x')\cdot \nabla _{x}\log p(x)+k(x,x')\nabla _{x}\log p(x)\cdot \nabla _{x'}\log p(x')$

где $\nabla _{x}$ (соответственно $\nabla _{x'}$) указал градиент по отношению к аргументу, индексированному $x$ (соответственно $x'$).

Конкретно, если взять обратное многоквадричное ядро $k(x,x')=(1+(x-x')^{\top }\Sigma ^{-1}(x-x'))^{-\beta }$ с параметрами $\beta >0$ и $\Sigma \in \mathbb {R} ^{d\times d}$ симметричная положительно определенная матрица, и если обозначить $u(x)=\nabla \log p(x)$, тогда мы имеем

$(2.1)\quad {\mathcal {A}}_{P}{\mathcal {A}}_{P}'K(x,x')=-{\frac {4\beta (\beta +1)(x-x')^{\top }\Sigma ^{-2}(x-x')}{\left(1+(x-x')^{\top }\Sigma ^{-1}(x-x')\right)^{\beta +2}}}+2\beta \left[{\frac {{\text{tr}}(\Sigma ^{-1})+[u(x)-u(x')]^{\top }\Sigma ^{-1}(x-x')}{\left(1+(x-x')^{\top }\Sigma ^{-1}(x-x')\right)^{1+\beta }}}\right]+{\frac {u(x)^{\top }u(x')}{\left(1+(x-x')^{\top }\Sigma ^{-1}(x-x')\right)^{\beta }}}$.

Диффузионное расхождение Штейна

Диффузионные расхождения Штейна обобщить оператор Ланжевена Штейна ${\mathcal {A}}_{P}f=\nabla \cdot f+f\cdot \nabla \log p=\textstyle {\frac {1}{p}}\nabla \cdot (fp)$ к классу диффузионных операторов Штейна ${\mathcal {A}}_{P}f=\textstyle {\frac {1}{p}}\nabla \cdot (mfp)$, каждый из которых представляет диффузию Ито , которая имеет $P$ как его стационарное распределение. Здесь, $m$ – матрица-функция, определяемая бесконечно малым генератором диффузии.

Другие расхождения Штейна

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

Характеристики

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

Вычислимо без константы нормализации

Расхождение Штейна иногда можно вычислить в сложных условиях, когда распределение вероятностей $P$ допускает функцию плотности вероятности $p$ (в отношении соответствующей эталонной меры по ${\mathcal {X}}$) вида $p(x)=\textstyle {\frac {1}{Z}}{\tilde {p}}(x)$, где ${\tilde {p}}(x)$ и ее производная может быть оценена численно, но константа нормализации которой $Z$ нелегко вычислить или аппроксимировать. Учитывая (2.1), заметим, что зависимость ${\mathcal {A}}_{P}{\mathcal {A}}_{P}K(x,x')$ на $P$ происходит только через срок

$u(x)=\nabla \log p(x)=\nabla \log \left({\frac {{\tilde {p}}(x)}{Z}}\right)=\nabla \log {\tilde {p}}(x)-\nabla \log Z=\nabla \log {\tilde {p}}(x)$

которая не зависит от константы нормировки $Z$.

Расхождение Штейна как статистическое расхождение

Основное требование к расхождению Штейна состоит в том, что оно является статистическим расхождением, а это означает, что $D_{P}(Q)\geq 0$ и $D_{P}(Q)=0$ тогда и только тогда, когда $Q=P$. Можно показать, что это свойство справедливо для классической невязки Штейна. и несоответствие ядра Штейна a при условии выполнения соответствующих условий регулярности.

Контроль сходимости

Более сильным свойством, по сравнению со статистическим расхождением, является контроль сходимости , что означает, что $D_{P}(Q_{n})\rightarrow 0$ подразумевает $Q_{n}$ сходится к $P$ в смысле, который следует уточнить. Например, при соответствующих условиях регулярности как классическое несоответствие Стейна, так и графическое несоответствие Стейна подчиняются контролю сходимости Вассерштейна , что означает, что $D_{P}(Q_{n})\rightarrow 0$ подразумевает, что метрика Вассерштейна между $Q_{n}$ и $P$ сходится к нулю. Для ядра невязки Штейна слабый контроль сходимости . установлен при условиях регулярности распределения $P$ и воспроизводящее ядро $K$, которые применимы, в частности, к (2.1). Другие известные варианты $K$, например, основанные на ядре Гаусса, очевидно, не имеют слабого контроля сходимости.

Обнаружение сходимости

Обратным свойством к управлению сходимостью является обнаружение сходимости , что означает, что $D_{P}(Q_{n})\rightarrow 0$ в любое время $Q_{n}$ сходится к $P$ в смысле, который следует уточнить. Например, при соответствующих условиях регулярности классическое несоответствие Стейна имеет особую форму обнаружения среднеквадратичной сходимости. , это означает, что $D_{P}(Q_{n})\rightarrow 0$ в любое время $X_{n}\sim Q_{n}$ сходится в среднем квадратическом к $X\sim P$ и $\nabla \log p(X_{m})$ сходится в среднем квадратическом к $\nabla \log p(X)$. Для несоответствия ядра Штейна обнаружение сходимости Васерштейна : было установлено при соответствующих условиях регулярности распределения $P$ и воспроизводящее ядро $K$.

Применение невязки Штейна

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

Оптимальное квантование

Duration: 40 seconds.0:40

Оптимальное квантование с использованием невязки Штейна. Контуры в этом видео представляют собой наборы уровней непрерывного распределения вероятностей. $P$и рассмотрим задачу суммирования этого распределения с дискретным набором состояний $x_{1},\dots ,x_{m}$ выбран из своего домена ${\mathcal {X}}$. В частности, мы предполагаем, что функция плотности $p(x)$ известна только с точностью до пропорциональности, когда широко используются методы Монте-Карло с цепью Маркова (MCMC). В первой половине этого видео цепь Маркова производит выборки, которые приблизительно распределены по $P$, путь к образцу показан черным цветом. Во второй половине видео используется алгоритм, называемый прореживанием Штейна . применяется для выбора подмножества состояний из выборочного пути, при этом выбранные состояния отображаются красным цветом. Эти состояния выбираются на основе жадной минимизации невязки Штейна между дискретным распределением и $P$. В совокупности выбранные состояния дают приблизительное представление о $P$ в данном случае это более точно, чем исходный вывод MCMC.

Учитывая распределение вероятностей $P$ определенный на измеримом пространстве ${\mathcal {X}}$, задача квантования состоит в выборе небольшого количества состояний $x_{1},\dots ,x_{n}\in {\mathcal {X}}$ такое, что соответствующее дискретное распределение ${\textstyle Q^{n}={\frac {1}{n}}\sum _{i=1}^{n}\delta (x_{i})}$ является точным приближением $P$ в смысле, который следует уточнить.

Очки Штейна являются результатом выполнения оптимального квантования посредством минимизации неточности Штейна:

$(3.1)\quad {\underset {x_{1},\dots ,x_{n}\in {\mathcal {X}}}{\operatorname {arg\,min} }}\;D_{P}\left({\frac {1}{n}}\sum _{i=1}^{n}\delta (x_{i})\right)$

При соответствующих условиях регулярности можно показать что $D_{P}(Q^{n})\rightarrow 0$ как $n\rightarrow \infty$. Таким образом, если невязка Штейна контролируется сходимостью, отсюда следует, что $Q^{n}$ сходится к $P$. Также были получены расширения этого результата, позволяющие обеспечить несовершенную численную оптимизацию.

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

Оптимальное взвешенное приближение

Если разрешить рассматривать взвешенные комбинации точечных масс, то возможна более точная аппроксимация по сравнению с (3.1). Для простоты изложения предположим, что нам дан набор состояний $\{x_{i}\}_{i=1}^{n}\subset {\mathcal {X}}$. Тогда оптимальная взвешенная комбинация точечных масс $\delta (x_{i})$, то есть

$Q_{n}:=\sum _{i=1}^{n}w_{i}^{*}\delta (x_{i}),\qquad w^{*}\in {\underset {w_{1}+\cdots +w_{n}=1}{\operatorname {arg\,min} }}\;D_{P}\left(\sum _{i=1}^{n}w_{i}\delta (x_{i})\right),$

которые минимизируют невязку Стейна, можно получить в закрытой форме, если использовать ядро ​​невязки Стейна. Некоторые авторы рассмотрите возможность наложения, кроме того, ограничения на неотрицательность весов, т.е. $w_{i}\geq 0$. Однако в обоих случаях вычисления, необходимые для вычисления оптимальных весов, $w^{*}$ может включать решение линейных систем уравнений, которые плохо обусловлены численно. Интересно, что было показано это жадное приближение $Q_{n}$ используя невзвешенную комбинацию $m\ll n$ государства могут уменьшить эту вычислительную потребность. В частности, жадный прореживания Штейна алгоритм

$Q_{n,m}:={\frac {1}{m}}\sum _{i=1}^{m}\delta (x_{\pi (i)}),\qquad \pi (m)\in {\underset {j=1,\dots ,n}{\operatorname {arg\,min} }}\;D_{P}\left({\frac {1}{m}}\sum _{i=1}^{m-1}\delta (x_{\pi (i)})+{\frac {1}{m}}\delta (x_{j})\right)$

было показано, что удовлетворяет границе ошибки

$D_{P}(Q_{n,m})=D_{P}(Q_{n})+O\left({\sqrt {\frac {\log m}{m}}}\right).$

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

Вариационный вывод

Невязка Штейна использовалась как вариационная цель в вариационных байесовских методах . Учитывая коллекцию $\{Q_{\theta }\}_{\theta \in \Theta }$ вероятностных распределений на ${\mathcal {X}}$, параметризованный $\theta \in \Theta$, в этой коллекции можно найти распределение, которое лучше всего аппроксимирует распределение $P$ интерес:

${\underset {\theta \in \Theta }{\operatorname {arg\,min} }}\;D_{P}(Q_{\theta })$

Возможное преимущество несоответствия Штейна в этом контексте: по сравнению с традиционной вариационной целью Кульбака – Лейблера , заключается в том, что $Q_{\theta }$ не обязательно быть абсолютно непрерывным по отношению к $P$ для того, чтобы $D_{P}(Q_{\theta })$ быть четко определенным. Это свойство можно использовать, например, чтобы обойти использование генеративных моделей на основе потоков , которые накладывают ограничения диффеоморфизма, чтобы обеспечить абсолютную непрерывность $Q_{\theta }$ и $P$.

Статистическая оценка

Невязка Стейна была предложена как инструмент для подгонки параметрических статистических моделей к данным. Учитывая набор данных $\{x_{i}\}_{i=1}^{n}\subset {\mathcal {X}}$, рассмотрим соответствующее дискретное распределение $Q^{n}=\textstyle {\frac {1}{n}}\sum _{i=1}^{n}\delta (x_{i})$. Для данного параметрического набора $\{P_{\theta }\}_{\theta \in \Theta }$ вероятностных распределений на ${\mathcal {X}}$, можно оценить значение параметра $\theta$ который совместим с набором данных с использованием минимальной оценки несоответствия Штейна

${\underset {\theta \in \Theta }{\operatorname {arg\,min} }}\;D_{P_{\theta }}(Q^{n}).$

Этот подход тесно связан со структурой оценки минимального расстояния , где роль «расстояния» играет невязка Штейна. Альтернативно, обобщенный байесовский подход к оценке параметра $\theta$ можно считать где, учитывая априорное распределение вероятностей с функцией плотности $\pi (\theta )$, $\theta \in \Theta$, (относительно соответствующей эталонной меры по $\Theta$), строится обобщенный апостериор с функцией плотности вероятности

$\pi ^{n}(\theta )\propto \pi (\theta )\exp \left(-\gamma D_{P_{\theta }}(Q^{n})^{2}\right),$

для некоторых $\gamma >0$ быть уточнены или определены.

Проверка гипотез

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

См. также

• метод Штейна
• Дивергенция (статистика)