Věta Hammersley – Clifford - Hammersley–Clifford theorem

The Věta Hammersley – Clifford je výsledkem v teorie pravděpodobnosti, matematická statistika a statistická mechanika což dává nezbytné a dostatečné podmínky, za kterých je přísně pozitivní rozdělení pravděpodobnosti (událostí v a pravděpodobnostní prostor )^{[je zapotřebí objasnění ]} mohou být reprezentovány jako události generované a Markovova síť (také známý jako Markovovo náhodné pole ). To je základní věta náhodných polí.^[1] Uvádí, že rozdělení pravděpodobnosti má přísně pozitivní Hmotnost nebo hustota vyhovuje jednomu z Markov vlastnosti s ohledem na neorientovaný graf G právě když je to Gibbsovo náhodné pole, to znamená, že jeho hustotu lze faktorizovat přes kliky (nebo kompletní podgrafy ) grafu.

Vztah mezi náhodnými poli Markov a Gibbs byl zahájen Roland Dobrushin^[2] a Frank Spitzer^[3] v kontextu statistická mechanika. Věta je pojmenována po John Hammersley a Peter Clifford, který prokázal rovnocennost v nepublikovaném článku v roce 1971.^[4]^[5] Jednodušší důkazy pomocí zásada začlenění - vyloučení byly dány nezávisle uživatelem Geoffrey Grimmett,^[6] Prestone^[7] a Sherman^[8] v roce 1973, s dalším důkazem Julian Besag v roce 1974.^[9]

Důkazní obrys

Jednoduchá Markovova síť pro demonstraci, že jakékoli Gibbsovo náhodné pole splňuje každou Markovovu vlastnost.

Je triviální záležitostí ukázat, že Gibbsovo náhodné pole uspokojí každého Majetek Markov. Jako příklad této skutečnosti viz následující:

Na obrázku vpravo má formulář Gibbsovo náhodné pole nad poskytnutým grafem ${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)}$ . Pokud proměnné ${displaystyle C}$ a ${displaystyle D}$ jsou opraveny, pak globální vlastnost Markov vyžaduje, aby: ${displaystyle A, Bperp E, F | C, D}$ (vidět podmíněná nezávislost ), od té doby ${displaystyle C, D}$ tvoří bariéru mezi ${displaystyle A, B}$ a ${displaystyle E, F}$ .

S ${displaystyle C}$ a ${displaystyle D}$ konstantní, ${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)}$ kde ${displaystyle g_ {1} (A, B) = f_ {1} (A, B, d) f_ {2} (A, c, d)}$ a ${displaystyle g_ {2} (E, F) = f_ {3} (c, d, F) f_ {4} (c, E, F)}$ . To z toho vyplývá ${displaystyle A, Bperp E, F | C, D}$ .

Abychom zjistili, že každé kladné rozdělení pravděpodobnosti, které splňuje místní Markovovu vlastnost, je také Gibbsovým náhodným polem, je třeba prokázat následující lemma, které poskytuje prostředky pro kombinování různých faktorizací:

Lemma 1 poskytuje prostředky pro kombinování faktorizací, jak je znázorněno v tomto diagramu. Všimněte si, že na tomto obrázku je překrývání mezi sadami ignorováno.

Lemma 1

Nechat ${displaystyle U}$ označit množinu všech uvažovaných náhodných proměnných a nechat ${displaystyle Theta, Phi _ {1}, Phi _ {2}, tečky, Phi _ {n} subseteq U}$ a ${displaystyle Psi _ {1}, Psi _ {2}, tečky, Psi _ {m} subseteq U}$ označit libovolné sady proměnných. (Zde, vzhledem k libovolné sadě proměnných ${displaystyle X}$ , ${displaystyle X}$ bude také označovat libovolné přiřazení proměnných z ${displaystyle X}$ .)

Li

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

pro funkce ${displaystyle f, g_ {1}, g_ {2}, tečky g_ {n}}$ a ${displaystyle h_ {1}, h_ {2}, tečky, h_ {m}}$ , pak existují funkce ${displaystyle h '_ {1}, h' _ {2}, tečky, h '_ {m}}$ a ${displaystyle g '_ {1}, g' _ {2}, tečky, g '_ {n}}$ takhle

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

Jinými slovy, ${displaystyle prod _ {j = 1} ^ {m} h_ {j} (Psi _ {j})}$ poskytuje šablonu pro další faktorizaci ${displaystyle f (Theta)}$ .

Důkaz lemma 1

Aby bylo možné použít ${displaystyle prod _ {j = 1} ^ {m} h_ {j} (Psi _ {j})}$ jako šablona pro další faktorizaci ${displaystyle f (Theta)}$ , všechny proměnné mimo ${displaystyle Theta}$ je třeba opravit. Za tímto účelem, pojďme ${displaystyle {ar {heta}}}$ být libovolné pevné přiřazení proměnným z ${displaystyle Usetminus Theta}$ (proměnné nejsou v ${displaystyle Theta}$ ). Pro libovolnou sadu proměnných ${displaystyle X}$ , nechť ${displaystyle {ar {heta}} [X]}$ označit úkol ${displaystyle {ar {heta}}}$ omezeno na proměnné z ${displaystyle Xsetminus Theta}$ (proměnné z ${displaystyle X}$ , vyjma proměnných z ${displaystyle Theta}$ ).

Navíc pouze faktorizovat ${displaystyle f (Theta)}$ , další faktory ${displaystyle g_ {1} (Phi _ {1}), g_ {2} (Phi _ {2}), ..., g_ {n} (Phi _ {n})}$ je třeba vykreslit diskutabilní pro proměnné z ${displaystyle Theta}$ . K tomu faktorizace

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

bude znovu vyjádřeno jako

${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} čepice Theta , {ar {heta}} [Phi _ {i}])}} {igg)}}$

Pro každého ${displaystyle i = 1,2, ..., n}$ : ${displaystyle g_ {i} (Phi _ {i} čepice Theta, {ar {heta}} [Phi _ {i}])}$ je ${displaystyle g_ {i} (Phi _ {i})}$ kde všechny proměnné mimo ${displaystyle Theta}$ byly stanoveny na hodnoty předepsané ${displaystyle {ar {heta}}}$ .

Nechat ${displaystyle f '(Theta) = f (Theta) prod _ {i = 1} ^ {n} g_ {i} (Phi _ {i} čepice Theta, {ar {heta}} [Phi _ {i}]) }$ a ${displaystyle g '_ {i} (Phi _ {i}) = {frac {g_ {i} (Phi _ {i})} {g_ {i} (Phi _ {i} čepice Theta, {ar {heta} } [Phi _ {i}])}}}$ pro každého ${displaystyle i = 1,2, tečky, n}$ tak

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

Nejdůležitější je to ${displaystyle g '_ {i} (Phi _ {i}) = {frac {g_ {i} (Phi _ {i})} {g_ {i} (Phi _ {i} čepice Theta, {ar {heta} } [Phi _ {i}])}} = 1}$ když jsou hodnoty přiřazeny ${displaystyle Phi _ {i}}$ nejsou v rozporu s hodnotami předepsanými ${displaystyle {ar {heta}}}$ , tvorba ${displaystyle g '_ {i} (Phi _ {i})}$ "zmizí", když všechny proměnné nejsou v ${displaystyle Theta}$ jsou fixovány na hodnoty z ${displaystyle {ar {heta}}}$ .

Oprava všech proměnných, které nejsou v ${displaystyle Theta}$ na hodnoty z ${displaystyle {ar {heta}}}$ dává

${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} čepice Theta, {ar {heta}} [Psi _ {j}])}}$

Od té doby ${displaystyle g '_ {i} (Phi _ {i} čepice Theta, {ar {heta}} [Phi _ {i}]) = 1}$ ,

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

Pronájem ${displaystyle h '_ {j} (Theta cap Psi _ {j}) = h_ {j} (Psi _ {j} cap Theta, {ar {heta}} [Psi _ {j}])}}$ dává:

${displaystyle f '(Theta) = prod _ {j = 1} ^ {m} h' _ {j} (Theta cap Psi _ {j})}$ který nakonec dává:

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

Klika tvořená vrcholy

{displaystyle x_ {1}}

,

{displaystyle x_ {2}}

, a

{displaystyle x_ {3}}

, je křižovatkou

{displaystyle {x_ {1}} šálek částečný x_ {1}}

,

{displaystyle {x_ {2}} šálek částečný x_ {2}}

, a

{displaystyle {x_ {3}} pohár částečný x_ {3}}

.

Lemma 1 poskytuje způsob kombinování dvou různých faktorizací ${displaystyle Pr (U)}$ . Místní vlastnost Markov to znamená pro libovolnou náhodnou proměnnou ${displaystyle xin U}$ , že existují faktory ${displaystyle f_ {x}}$ a ${displaystyle f _ {- x}}$ takové, že:

${displaystyle Pr (U) = f_ {x} (x, částečné x) f _ {- x} (Usetminus {x})}$

kde ${displaystyle částečné x}$ jsou sousedé uzlu ${displaystyle x}$ . Opakovaná aplikace Lemma 1 nakonec ovlivní ${displaystyle Pr (U)}$ do produktu klikových potenciálů (viz obrázek vpravo).

Konec důkazu

Viz také

Poznámky

^ Lafferty, John D .; Mccallum, Andrew (2001). „Podmíněná náhodná pole: Pravděpodobnostní modely pro segmentaci a označování sekvenčních dat“. ICML. Citováno 14. prosince 2014. základní teorémou náhodných polí (Hammersley & Clifford, 1971)
^ Dobrushin, P. L. (1968), „Popis náhodného pole pomocí podmíněných pravděpodobností a podmínek jeho pravidelnosti“, Teorie pravděpodobnosti a její aplikace, 13 (2): 197–224, doi:10.1137/1113026
^ Spitzer, Frank (1971), „Markov Random Fields and Gibbs Ensembles“, Americký matematický měsíčník, 78 (2): 142–154, doi:10.2307/2317621, JSTOR 2317621
^ Hammersley, J. M .; Clifford, P. (1971), Markovova pole na konečných grafech a mřížkách (PDF)
^ Clifford, P. (1990), "Markovova náhodná pole ve statistikách", Grimmett, G. R .; Welsh, D. J. A. (eds.), Porucha ve fyzických systémech: Svazek na počest Johna M. Hammersleye, Oxford University Press, s. 19–32, ISBN 978-0-19-853215-6, PAN 1064553, vyvoláno 2009-05-04
^ Grimmett, G. R. (1973), „Věta o náhodných polích“, Bulletin of London Mathematical Society, 5 (1): 81–84, CiteSeerX 10.1.1.318.3375, doi:10,1112 / blms / 5.1.81, PAN 0329039
^ Preston, C. J. (1973), „Generalized Gibbs States and Markov random fields“, Pokroky v aplikované pravděpodobnosti, 5 (2): 242–261, doi:10.2307/1426035, JSTOR 1426035, PAN 0405645
^ Sherman, S. (1973), „Markovova náhodná pole a Gibbsova náhodná pole“, Israel Journal of Mathematics, 14 (1): 92–103, doi:10.1007 / BF02761538, PAN 0321185
^ Besag, J. (1974), "Prostorová interakce a statistická analýza příhradových systémů", Journal of the Royal Statistical Society, Series B, 36 (2): 192–236, JSTOR 2984812, PAN 0373208

Další čtení

Bilmes, Jeff (jaro 2006), Leták 2: Hammersley – Clifford (PDF), poznámky z kurzu od University of Washington chod.
Grimmett, Geoffrey, Pravděpodobnost v grafech, kapitola 7
Langseth, Helge, Věta Hammersley – Clifford a její dopad na moderní statistiku (PDF)

[1] Lafferty, John D .; Mccallum, Andrew (2001). „Podmíněná náhodná pole: Pravděpodobnostní modely pro segmentaci a označování sekvenčních dat“. ICML. Citováno 14. prosince 2014. základní teorémou náhodných polí (Hammersley & Clifford, 1971)

[2] Dobrushin, P. L. (1968), „Popis náhodného pole pomocí podmíněných pravděpodobností a podmínek jeho pravidelnosti“, Teorie pravděpodobnosti a její aplikace, 13 (2): 197–224, doi:10.1137/1113026

[3] Spitzer, Frank (1971), „Markov Random Fields and Gibbs Ensembles“, Americký matematický měsíčník, 78 (2): 142–154, doi:10.2307/2317621, JSTOR 2317621

[4] Hammersley, J. M .; Clifford, P. (1971), Markovova pole na konečných grafech a mřížkách (PDF)

[clifford-5] Clifford, P. (1990), "Markovova náhodná pole ve statistikách", Grimmett, G. R .; Welsh, D. J. A. (eds.), Porucha ve fyzických systémech: Svazek na počest Johna M. Hammersleye, Oxford University Press, s. 19–32, ISBN 978-0-19-853215-6, PAN 1064553, vyvoláno 2009-05-04

[6] Grimmett, G. R. (1973), „Věta o náhodných polích“, Bulletin of London Mathematical Society, 5 (1): 81–84, CiteSeerX 10.1.1.318.3375, doi:10,1112 / blms / 5.1.81, PAN 0329039

[7] Preston, C. J. (1973), „Generalized Gibbs States and Markov random fields“, Pokroky v aplikované pravděpodobnosti, 5 (2): 242–261, doi:10.2307/1426035, JSTOR 1426035, PAN 0405645

[8] Sherman, S. (1973), „Markovova náhodná pole a Gibbsova náhodná pole“, Israel Journal of Mathematics, 14 (1): 92–103, doi:10.1007 / BF02761538, PAN 0321185

[9] Besag, J. (1974), "Prostorová interakce a statistická analýza příhradových systémů", Journal of the Royal Statistical Society, Series B, 36 (2): 192–236, JSTOR 2984812, PAN 0373208

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]