Теорема Хаммерсли – Клиффорда - Hammersley–Clifford theorem

В Теорема Хаммерсли – Клиффорда это результат теория вероятности, математическая статистика и статистическая механика что дает необходимые и достаточные условия, при которых строго положительный распределение вероятностей (событий в вероятностное пространство )^{[требуется разъяснение ]} могут быть представлены как события, генерируемые Сеть Маркова (также известный как Марковское случайное поле ). Это основная теорема случайных полей.^[1] Он утверждает, что распределение вероятностей, которое имеет строго положительный масса или же плотность удовлетворяет один из Марковские свойства относительно неориентированного графа грамм если и только если это Случайное поле Гиббса, то есть его плотность может быть факторизована по кликам (или полные подграфы ) графа.

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

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

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

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

На изображении справа случайное поле Гиббса над предоставленным графом имеет вид ${displaystyle 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)}$ . Если переменные ${displaystyle C}$ и ${displaystyle D}$ фиксированы, то глобальное марковское свойство требует, чтобы: ${displaystyle A, Bperp E, F | C, D}$ (видеть условная независимость ), поскольку ${displaystyle C, D}$ образует барьер между ${displaystyle A, B}$ и ${displaystyle E, F}$ .

С ${displaystyle C}$ и ${displaystyle D}$ постоянный, ${displaystyle 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)}$ куда ${displaystyle g_ {1} (A, B) = f_ {1} (A, B, d) f_ {2} (A, c, d)}$ и ${displaystyle g_ {2} (E, F) = f_ {3} (c, d, F) f_ {4} (c, E, F)}$ . Отсюда следует, что ${displaystyle A, Bperp E, F | C, D}$ .

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

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

Лемма 1

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

Если

${displaystyle Pr (U) = f (Theta) prod _ {i = 1} ^ {n} g_ {i} (Phi _ {i}) = prod _ {j = 1} ^ {m} h_ {j} ( Пси _ {j})}$

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

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

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

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

Чтобы использовать ${displaystyle prod _ {j = 1} ^ {m} h_ {j} (Psi _ {j})}$ в качестве шаблона для дальнейшей факторизации ${displaystyle f (Theta)}$ , все переменные вне ${displaystyle Theta}$ нужно исправить. С этой целью пусть ${displaystyle {ar {heta}}}$ - произвольное фиксированное присвоение переменных из ${displaystyle Usetminus Theta}$ (переменные не в ${displaystyle Theta}$ ). Для произвольного набора переменных ${displaystyle X}$ , позволять ${displaystyle {ar {heta}} [X]}$ обозначить присвоение ${displaystyle {ar {heta}}}$ ограничено переменными из ${displaystyle Xsetminus Theta}$ (переменные из ${displaystyle X}$ , исключая переменные из ${displaystyle Theta}$ ).

Более того, разложить на множители только ${displaystyle f (Theta)}$ , другие факторы ${displaystyle g_ {1} (Phi _ {1}), g_ {2} (Phi _ {2}), ..., g_ {n} (Phi _ {n})}$ необходимо сделать спорным для переменных из ${displaystyle Theta}$ . Для этого факторизация

${displaystyle Pr (U) = f (Theta) prod _ {i = 1} ^ {n} g_ {i} (Phi _ {i})}$

будет повторно выражен как

${displaystyle Pr (U) = {igg (} f (Theta) prod _ {i = 1} ^ {n} g_ {i} (Phi _ {i} cap Theta, {ar {heta}}) [Phi _ {i }]) {igg)} {igg (} prod _ {i = 1} ^ {n} {frac {g_ {i} (Phi _ {i})} {g_ {i} (Phi _ {i} cap Theta , {ar {heta}} [Phi _ {i}])}} {igg)}}$

Для каждого ${displaystyle i = 1,2, ..., n}$ : ${displaystyle g_ {i} (Phi _ {i} cap Theta, {ar {heta}} [Phi _ {i}])}$ является ${displaystyle g_ {i} (Phi _ {i})}$ где все переменные вне ${displaystyle Theta}$ были установлены на значения, предписанные ${displaystyle {ar {heta}}}$ .

Позволять ${displaystyle f '(Theta) = f (Theta) prod _ {i = 1} ^ {n} g_ {i} (Phi _ {i} cap Theta, {ar {heta}} [Phi _ {i}]) }$ и ${displaystyle g '_ {i} (Phi _ {i}) = {frac {g_ {i} (Phi _ {i})} {g_ {i} (Phi _ {i} cap Theta, {ar {heta}) } [Phi _ {i}])}}}$ для каждого ${displaystyle i = 1,2, dots, n}$ так

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

Самое главное, что ${displaystyle g '_ {i} (Phi _ {i}) = {frac {g_ {i} (Phi _ {i})} {g_ {i} (Phi _ {i} cap Theta, {ar {heta}) } [Phi _ {i}])}} = 1}$ когда значения, присвоенные ${displaystyle Phi _ {i}}$ не противоречат ценностям, предписанным ${displaystyle {ar {heta}}}$ , изготовление ${displaystyle g '_ {i} (Phi _ {i})}$ "исчезнуть", когда все переменные не в ${displaystyle Theta}$ фиксируются на значениях из ${displaystyle {ar {heta}}}$ .

Исправление всех переменных не в ${displaystyle Theta}$ к значениям из ${displaystyle {ar {heta}}}$ дает

${displaystyle Pr (Theta, {ar {heta}}) = f '(Theta) prod _ {i = 1} ^ {n} g' _ {i} (Phi _ {i} cap Theta, {ar {heta}) } [Phi _ {i}]) = prod _ {j = 1} ^ {m} h_ {j} (Psi _ {j} cap Theta, {ar {heta}} [Psi _ {j}])}$

С ${displaystyle g '_ {i} (Phi _ {i} cap Theta, {ar {heta}} [Phi _ {i}]) = 1}$ ,

${displaystyle f '(Theta) = prod _ {j = 1} ^ {m} h_ {j} (Psi _ {j} cap Theta, {ar {heta}} [Psi _ {j}])}$

Сдача ${displaystyle h '_ {j} (Theta cap Psi _ {j}) = h_ {j} (Psi _ {j} cap Theta, {ar {heta}} [Psi _ {j}])}$ дает:

${displaystyle f '(Theta) = prod _ {j = 1} ^ {m} h' _ {j} (Theta cap Psi _ {j})}$ что наконец дает:

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

Клика, образованная вершинами

{displaystyle x_ {1}}

,

{displaystyle x_ {2}}

, и

{displaystyle x_ {3}}

, является пересечением

{displaystyle {x_ {1}} чашка частичная x_ {1}}

,

{displaystyle {x_ {2}} чашка частичная x_ {2}}

, и

{displaystyle {x_ {3}} чашка частичная x_ {3}}

.

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

${displaystyle Pr (U) = f_ {x} (x, частичное x) f _ {- x} (Usetminus {x})}$

куда ${displaystyle partial x}$ являются соседями узла ${displaystyle x}$ . Многократно применяя лемму 1, в конечном итоге разложим ${displaystyle Pr (U)}$ в произведение потенциалов клики (см. изображение справа).

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

Смотрите также

Примечания

^ Лафферти, Джон Д .; Маккаллум, Эндрю (2001). «Условные случайные поля: вероятностные модели для сегментации и маркировки данных последовательности». ICML. Получено 14 декабря 2014. по основной теореме о случайных полях (Hammersley & Clifford, 1971)
^ Добрушин, П.Л. (1968), «Описание случайного поля с помощью условных вероятностей и условий его регулярности», Теория вероятностей и ее приложения, 13 (2): 197–224, Дои:10.1137/1113026
^ Спитцер, Фрэнк (1971), "Марковские случайные поля и ансамбли Гиббса", Американский математический ежемесячник, 78 (2): 142–154, Дои:10.2307/2317621, JSTOR 2317621
^ Hammersley, J.M .; Клиффорд, П. (1971), Марковские поля на конечных графах и решетках (PDF)
^ Клиффорд, П. (1990), «Марковские случайные поля в статистике», в Grimmett, G.R .; Уэлш, Д. Дж. А. (ред.), Беспорядок в физических системах: Книга в честь Джона М. Хаммерсли, Oxford University Press, стр. 19–32, ISBN 978-0-19-853215-6, МИСТЕР 1064553, получено 2009-05-04
^ Гримметт, Г. (1973), «Теорема о случайных полях», Бюллетень Лондонского математического общества, 5 (1): 81–84, CiteSeerX 10.1.1.318.3375, Дои:10.1112 / blms / 5.1.81, МИСТЕР 0329039
^ Престон, К. Дж. (1973), "Обобщенные состояния Гиббса и марковские случайные поля", Достижения в прикладной теории вероятностей, 5 (2): 242–261, Дои:10.2307/1426035, JSTOR 1426035, МИСТЕР 0405645
^ Шерман, С. (1973), "Марковские случайные поля и случайные поля Гиббса", Израильский математический журнал, 14 (1): 92–103, Дои:10.1007 / BF02761538, МИСТЕР 0321185
^ Бесаг, Дж. (1974), "Пространственное взаимодействие и статистический анализ решетчатых систем", Журнал Королевского статистического общества, серия B, 36 (2): 192–236, JSTOR 2984812, МИСТЕР 0373208

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

Билмес, Джефф (весна 2006 г.), Раздаточный материал 2: Хаммерсли – Клиффорд (PDF), заметки из курса Вашингтонский университет курс.
Гриммет, Джеффри, Вероятность на графах, Глава 7
Лангсет, Хельге, Теорема Хаммерсли – Клиффорда и ее влияние на современную статистику (PDF)

[1] Лафферти, Джон Д .; Маккаллум, Эндрю (2001). «Условные случайные поля: вероятностные модели для сегментации и маркировки данных последовательности». ICML. Получено 14 декабря 2014. по основной теореме о случайных полях (Hammersley & Clifford, 1971)

[2] Добрушин, П.Л. (1968), «Описание случайного поля с помощью условных вероятностей и условий его регулярности», Теория вероятностей и ее приложения, 13 (2): 197–224, Дои:10.1137/1113026

[3] Спитцер, Фрэнк (1971), "Марковские случайные поля и ансамбли Гиббса", Американский математический ежемесячник, 78 (2): 142–154, Дои:10.2307/2317621, JSTOR 2317621

[4] Hammersley, J.M .; Клиффорд, П. (1971), Марковские поля на конечных графах и решетках (PDF)

[clifford-5] Клиффорд, П. (1990), «Марковские случайные поля в статистике», в Grimmett, G.R .; Уэлш, Д. Дж. А. (ред.), Беспорядок в физических системах: Книга в честь Джона М. Хаммерсли, Oxford University Press, стр. 19–32, ISBN 978-0-19-853215-6, МИСТЕР 1064553, получено 2009-05-04

[6] Гримметт, Г. (1973), «Теорема о случайных полях», Бюллетень Лондонского математического общества, 5 (1): 81–84, CiteSeerX 10.1.1.318.3375, Дои:10.1112 / blms / 5.1.81, МИСТЕР 0329039

[7] Престон, К. Дж. (1973), "Обобщенные состояния Гиббса и марковские случайные поля", Достижения в прикладной теории вероятностей, 5 (2): 242–261, Дои:10.2307/1426035, JSTOR 1426035, МИСТЕР 0405645

[8] Шерман, С. (1973), "Марковские случайные поля и случайные поля Гиббса", Израильский математический журнал, 14 (1): 92–103, Дои:10.1007 / BF02761538, МИСТЕР 0321185

[9] Бесаг, Дж. (1974), "Пространственное взаимодействие и статистический анализ решетчатых систем", Журнал Королевского статистического общества, серия B, 36 (2): 192–236, JSTOR 2984812, МИСТЕР 0373208

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]