Теорема Хаммерсли – Клиффорда

Теорема Хаммерсли-Клиффорда — результат теории вероятностей , математической статистики и статистической механики, дающий необходимые и достаточные условия, при которых строго положительное распределение вероятностей (событий в вероятностном пространстве ) могут быть представлены как события, генерируемые марковской сетью (также известной как марковское случайное поле ). Это фундаментальная теорема о случайных полях . Он утверждает, что распределение вероятностей, имеющее строго положительную массу или плотность, удовлетворяет одному из марковских свойств по отношению к неориентированному графу G тогда и только тогда, когда оно является случайным полем Гиббса , то есть его плотность может быть факторизована по кликам ( или полные подграфы ) графа.

Связь между случайными полями Маркова и Гиббса была инициирована Роландом Добрушиным. и Фрэнк Спитцер в контексте статистической механики . Теорема названа в честь Джона Хаммерсли и Питера Клиффорда , которые доказали эквивалентность в неопубликованной статье 1971 года. Более простые доказательства с использованием принципа включения-исключения были независимо даны Джеффри Гримметом . Престон и Шерман в 1973 году, с дальнейшим доказательством Джулиана Бесага в 1974 году.

Схема доказательства

Простая марковская сеть для демонстрации того, что любое случайное поле Гиббса удовлетворяет всем марковским свойствам.

Нетрудно доказать, что случайное поле Гиббса удовлетворяет всем марковским свойствам . В качестве примера этого факта см. следующее:

На изображении справа случайное поле Гиббса на предоставленном графе имеет форму $\Pr(A,B,C,D,E,F)\propto f_{1}(A,B,D)f_{2}(A,C,D)f_{3}(C,D,F)f_{4}(C,E,F)$. Если переменные $C$ и $D$ фиксированы, то глобальное марковское свойство требует, чтобы: $A,B\perp E,F|C,D$ (см. условную независимость ), поскольку $C,D$ образует барьер между $A,B$ и $E,F$.

С $C$ и $D$ постоянный, $\Pr(A,B,E,F|C=c,D=d)\propto [f_{1}(A,B,d)f_{2}(A,c,d)]\cdot [f_{3}(c,d,F)f_{4}(c,E,F)]=g_{1}(A,B)g_{2}(E,F)$ где $g_{1}(A,B)=f_{1}(A,B,d)f_{2}(A,c,d)$ и $g_{2}(E,F)=f_{3}(c,d,F)f_{4}(c,E,F)$. Это означает, что $A,B\perp E,F|C,D$.

Чтобы установить, что каждое положительное распределение вероятностей, удовлетворяющее локальному свойству Маркова, также является случайным полем Гиббса, необходимо доказать следующую лемму, которая обеспечивает средства для объединения различных факторизаций:

Лемма 1 предоставляет средства для объединения факторизаций, как показано на этой диаграмме. Обратите внимание, что на этом изображении перекрытие между наборами игнорируется.

Лемма 1

Позволять $U$ обозначим множество всех рассматриваемых случайных величин и пусть $\Theta ,\Phi _{1},\Phi _{2},\dots ,\Phi _{n}\subseteq U$ и $\Psi _{1},\Psi _{2},\dots ,\Psi _{m}\subseteq U$ обозначают произвольные наборы переменных. (Здесь для произвольного набора переменных $X$, $X$ также будет обозначать произвольное присвоение переменным из $X$.)

Если

$\Pr(U)=f(\Theta )\prod _{i=1}^{n}g_{i}(\Phi _{i})=\prod _{j=1}^{m}h_{j}(\Psi _{j})$

для функций $f,g_{1},g_{2},\dots g_{n}$ и $h_{1},h_{2},\dots ,h_{m}$, то существуют функции $h'_{1},h'_{2},\dots ,h'_{m}$ и $g'_{1},g'_{2},\dots ,g'_{n}$ такой, что

$\Pr(U)={\bigg (}\prod _{j=1}^{m}h'_{j}(\Theta \cap \Psi _{j}){\bigg )}{\bigg (}\prod _{i=1}^{n}g'_{i}(\Phi _{i}){\bigg )}$

Другими словами, $\prod _{j=1}^{m}h_{j}(\Psi _{j})$ предоставляет шаблон для дальнейшей факторизации $f(\Theta )$.

показывать Доказательство леммы 1.

In order to use $\prod _{j=1}^{m}h_{j}(\Psi _{j})$ as a template to further factorize $f(\Theta )$, all variables outside of $\Theta$ need to be fixed. To this end, let ${\bar {\theta }}$ be an arbitrary fixed assignment to the variables from $U\setminus \Theta$ (the variables not in $\Theta$). For an arbitrary set of variables $X$, let ${\bar {\theta }}[X]$ denote the assignment ${\bar {\theta }}$ restricted to the variables from $X\setminus \Theta$ (the variables from $X$, excluding the variables from $\Theta$). Moreover, to factorize only $f(\Theta )$, the other factors $g_{1}(\Phi _{1}),g_{2}(\Phi _{2}),...,g_{n}(\Phi _{n})$ need to be rendered moot for the variables from $\Theta$. To do this, the factorization $\Pr(U)=f(\Theta )\prod _{i=1}^{n}g_{i}(\Phi _{i})$ will be re-expressed as $\Pr(U)={\bigg (}f(\Theta )\prod _{i=1}^{n}g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}]){\bigg )}{\bigg (}\prod _{i=1}^{n}{\frac {g_{i}(\Phi _{i})}{g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])}}{\bigg )}$ For each $i=1,2,...,n$: $g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])$ is $g_{i}(\Phi _{i})$ where all variables outside of $\Theta$ have been fixed to the values prescribed by ${\bar {\theta }}$. Let $f'(\Theta )=f(\Theta )\prod _{i=1}^{n}g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])$and $g'_{i}(\Phi _{i})={\frac {g_{i}(\Phi _{i})}{g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])}}$for each $i=1,2,\dots ,n$ so $\Pr(U)=f'(\Theta )\prod _{i=1}^{n}g'_{i}(\Phi _{i})=\prod _{j=1}^{m}h_{j}(\Psi _{j})$ What is most important is that $g'_{i}(\Phi _{i})={\frac {g_{i}(\Phi _{i})}{g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])}}=1$ when the values assigned to $\Phi _{i}$ do not conflict with the values prescribed by ${\bar {\theta }}$, making $g'_{i}(\Phi _{i})$ "disappear" when all variables not in $\Theta$ are fixed to the values from ${\bar {\theta }}$. Fixing all variables not in $\Theta$ to the values from ${\bar {\theta }}$ gives $\Pr(\Theta ,{\bar {\theta }})=f'(\Theta )\prod _{i=1}^{n}g'_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])=\prod _{j=1}^{m}h_{j}(\Psi _{j}\cap \Theta ,{\bar {\theta }}[\Psi _{j}])$ Since $g'_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])=1$, $f'(\Theta )=\prod _{j=1}^{m}h_{j}(\Psi _{j}\cap \Theta ,{\bar {\theta }}[\Psi _{j}])$ Letting $h'_{j}(\Theta \cap \Psi _{j})=h_{j}(\Psi _{j}\cap \Theta ,{\bar {\theta }}[\Psi _{j}])$gives: $f'(\Theta )=\prod _{j=1}^{m}h'_{j}(\Theta \cap \Psi _{j})$which finally gives: $\Pr(U)={\bigg (}\prod _{j=1}^{m}h'_{j}(\Theta \cap \Psi _{j}){\bigg )}{\bigg (}\prod _{i=1}^{n}g'_{i}(\Phi _{i}){\bigg )}$

Клика, образованная вершинами $x_{1}$, $x_{2}$, и $x_{3}$, является пересечением $\{x_{1}\}\cup \partial x_{1}$, $\{x_{2}\}\cup \partial x_{2}$, и $\{x_{3}\}\cup \partial x_{3}$.

Лемма 1 предоставляет средства объединения двух различных факторизаций $\Pr(U)$. Локальное марковское свойство означает, что для любой случайной величины $x\in U$, что существуют факторы $f_{x}$ и $f_{-x}$ такой, что:

$\Pr(U)=f_{x}(x,\partial x)f_{-x}(U\setminus \{x\})$

где $\partial x$ являются соседями узла $x$. Повторное применение леммы 1 в конечном итоге приводит к факторам $\Pr(U)$ в произведение кликовых потенциалов (см. изображение справа).

Конец доказательства

См. также

• Марковское случайное поле
• Условное случайное поле

Дальнейшее чтение

• Гриммет, Джеффри (2018), «7», Вероятность на графиках (2-е изд.), Cambridge University Press, ISBN  9781108438179
• Лангсет, Хельге, Теорема Хаммерсли-Клиффорда и ее влияние на современную статистику (PDF) , Департамент математических наук, Норвежский университет науки и технологий