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

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

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

${\displaystyle (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)]|,}$

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

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

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

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

${\displaystyle 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)]|}$.

Эта результирующая связь

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

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

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

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

${\displaystyle {\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)\|}{\|xy\|}}\right)\leq 1,\;\langle f(x),n(x)\rangle =0\;\forall x\in \partial {\mathcal {X}}\right\}}$

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

В одномерном случае классическое расхождение Штейна может быть вычислено точно путем решения квадратично-ограниченной квадратичной программы . ^[1]${\displaystyle d=1}$

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

${\displaystyle {\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 на самом деле является решением конечномерной линейной программы с размером всего лишь линейным в , что означает, что GSD может быть эффективно вычислено. ^[1]${\displaystyle E}$${\displaystyle n}$

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

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

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

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

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

${\displaystyle 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})}}.}$

Построенное таким образом расхождение Штейна называется ядерным расхождением Штейна ^{[5] [6] [7] [8]} , и его построение тесно связано с теорией вложения ядер распределений вероятностей .

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

${\displaystyle {\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\},}$

связанный с матрично-значным воспроизводящим ядром , дает ядро ​​Стейна с расхождением ^[5]${\displaystyle K(x,x')=k(x,x')I_{d\times d}}$

${\displaystyle {\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')}$

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

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

${\displaystyle (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 }}}}$.

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

Дополнительные расхождения Штейна были разработаны для ограниченных областей, ^[10] неевклидовых областей ^{[11] [12] [10]} , дискретных областей, ^{[13] [14]} улучшенной масштабируемости., ^{[15] [16]} и безградиентных расхождений Штейна, где обойдены производные плотности . ^[17] Более того, этот подход расширен до безградиентного ядра условного расхождения Штейна, которое нацелено на условные распределения. ^[18]${\displaystyle p}$

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

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

${\displaystyle 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)}$

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

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

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

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

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

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

Точки Штейна ^[20] являются результатом выполнения оптимального квантования посредством минимизации расхождения Штейна:

${\displaystyle (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)}$

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

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

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

${\displaystyle 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),}$

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

${\displaystyle 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)}$

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

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

^{Было показано [26],} что неблизорукие и мини-пакетные обобщения жадного алгоритма обеспечивают дальнейшее улучшение качества аппроксимации относительно вычислительных затрат.

Расхождение Штейна использовалось как вариационная цель в вариационных байесовских методах . ^{[27] [28]} Имея набор вероятностных распределений на , параметризованных с помощью , можно найти распределение в этом наборе, которое наилучшим образом приближает интересующее распределение:${\displaystyle \{Q_{\theta }\}_{\theta \in \Theta }}$${\displaystyle {\mathcal {X}}}$${\displaystyle \theta \in \Theta }$${\displaystyle P}$

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

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

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

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

Подход тесно связан с фреймворком оценки минимального расстояния , где роль «расстояния» играет расхождение Стейна. В качестве альтернативы можно рассмотреть обобщенный байесовский подход к оценке параметра ^[4], где, учитывая априорное распределение вероятностей с функцией плотности , , (относительно соответствующей референтной меры на ), строится обобщенное апостериорное распределение с функцией плотности вероятности${\displaystyle \theta }$${\displaystyle \pi (\theta )}$${\displaystyle \theta \in \Theta }$${\displaystyle \Theta }$

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

для некоторых из них необходимо указать или определить.${\displaystyle \gamma >0}$

Расхождение Стейна также использовалось в качестве тестовой статистики для выполнения проверки согласия ^{[6] [7]} и сравнения моделей скрытых переменных. ^[30] Поскольку вышеупомянутые тесты имеют вычислительную стоимость, квадратичную по размеру выборки, были разработаны альтернативы с (почти)линейным временем выполнения. ^{[31] [15]}

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