Malfermi la ĉefan menuon

Teoremo de Hammersley–Clifford

La Teoremo de Hammersley–Clifford temas pri probabloteorio, statistiko kaj statistika mekaniko. Ĝi difinas la necesan kaj sufiĉan kondiĉojn tial, kial probabla distribuo povas reprezentiĝi kiel Markova reto. Ĝi estas la fundamenta teoremo pri hazarda kampo.[1] La teoremo asertas, ke probablo distribuo, kiu havas strikte pozitivan masondenson, estas Markova al sendirekta grafeo G, se kaj nur se  ĝi estas Gibsa. Tio estas, ĝia denso eblas faktoriĝi laŭ la klikoj de la grafeo.

La rilaton inter Markova kaj Gibsa reto unue studis Roland Dobrushin[2] kaj Frank Spitzer[3] sub kunteksto de statistika mekaniko. La teoremo nomiĝas memore al John Hammersley kaj Peter Clifford, kiuj pruvis la ekvivalenton en nepublikigita raporto en  1971.[4][5] Pli simpla pruvo per inkluziveco-ekskluda principo donis sendepende Geoffrey Grimmett,[6] Preston[7] kaj Sherman[8] en 1973, kun posta pruvo fare de Julian Besag en 1974.[9]

Ideo pri pruvoRedakti

Estas triviala pruvi ke Gibsa reto havas ĉiujn Markovecojn. Ekzemple jen:

Dekstre montras Gibsan reton sur la grafeo kun formo  . Se variablo   kaj   estas konstanta, do la malloka Markoveco bezonas ke   (vidu kondiĉan sendependecon), ĉar   iĝas muro inter   kaj  .

Kun   kaj   konstantaj,   kie   kaj  . Tio implicas, ke  .

Por verigi ke ĉiu pozitiva probablodistribuo kun loka Markoveco estas Gibsa, oni unue pruvas jenan lemon, kiu ebligas kunigi malsamajn faktorigon:

Lemo 1

  signu la aro de hazardaj variabloj koncernaj kaj   kaj   signu iujn arojn da variabloj (Ĉikuntekste, por aro da variablo  ,   ankaŭ signu iun valorigon al la variabloj en  .)

Se

 

por funkcioj   kaj  , do estas funkcioj   kaj  tiaj, ke

 

Alivorte,  fariĝas plano por plu faktorigi  .

Lemo 1 ebligas kunigi du malsamajn faktorigojn de  . La loka Markoveco implicas ke por ĉiu hazarda variablo  , estas faktoroj   kaj   tiaj, ke

 

kie   estas la najbaroj de  . Apliki lemon 1 refoje fine faktorigos   en produto de kliko-potencialoj (vidu la dekstran bildon).

Vidu ankaŭRedakti

NotojRedakti

  1. Lafferty, John . “Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data”.  
  2. Dobrushin, P. L. (1967). “The Description of a Random Field by Means of Conditional Probabilities and Conditions of Its Regularity”. doi:10.1137/1113026. 
  3. Spitzer, Frank (1971). “Markov Random Fields and Gibbs Ensembles”, The American Mathematical Monthly 78 (2), p. 142–154. doi:10.2307/2317621. 
  4. Hammersley, J. M.; Clifford, P. (1971), Markov fields on finite graphs and lattices
  5. CLIFFORD, Peter. (1990) Disorder in Physical Systems. ISBN 0-19-853215-6.
  6. Grimmett, G. R. (1973), "A theorem about random fields", Bulletin of the London Mathematical Society 5 (1): 81–84, doi:10.1112/blms/5.1.81 
  7. Preston, C. J. (1973), "Generalized Gibbs states and Markov random fields", Advances in Applied Probability 5 (2): 242–261, doi:10.2307/1426035 
  8. Sherman, S. (1973), "Markov random fields and Gibbs random fields", Israel Journal of Mathematics 14 (1): 92–103, doi:10.1007/BF02761538 
  9. Besag, J. (1974), "Spatial interaction and the statistical analysis of lattice systems", Journal of the Royal Statistical Society, Series B 36 (2): 192–236 

Plia legadoRedakti