Markov rastgele alanı - Markov random field

Markov rastgele alan örneği.
Markov rastgele alan örneği. Her kenar bağımlılığı temsil eder. Bu örnekte: A, B ve D'ye bağlıdır. B, A ve D'ye bağlıdır. D, A, B ve E'ye bağlıdır. E, D ve C'ye bağlıdır. C, E'ye bağlıdır.

Bir etki alanında fizik ve olasılık , bir Markov rastgele alan ( MRF ), Markov ağ veya yönsüz grafik modeli bir dizi rastgele değişken bir olan Markov özelliği , bir tarafından tarif yönsüz grafik . Diğer bir deyişle, bir rastgele alan bir olduğu söylenir Markov bunu karşılamaktadır Markov özellikleri ise rasgele bir alan.

Bir Markov ağı veya MRF, bağımlılıkları temsil etmesi bakımından bir Bayes ağına benzer ; farklar, Bayes ağlarının yönlendirilmiş ve döngüsel olmamasıdır , oysa Markov ağları yönsüzdür ve döngüsel olabilir. Bu nedenle, bir Markov ağı, bir Bayes ağının yapamayacağı belirli bağımlılıkları temsil edebilir (döngüsel bağımlılıklar gibi); Öte yandan, bir Bayes ağının yapabileceği belirli bağımlılıkları (indüklenmiş bağımlılıklar gibi) temsil edemez. Markov rasgele alanının temel grafiği sonlu veya sonsuz olabilir.

Zaman Birleşik olasılık yoğunluk rastgele değişkenlerin kesin pozitiftir, aynı zamanda olarak da adlandırılır Gibbs rasgele alanı göre, çünkü Hammersley-Clifford teoremi , bu durumda bir ile temsil edilebilir Gibbs ölçü (yerine göre) bir uygun için enerji fonksiyonu. Prototipik Markov rastgele alanı, Ising modelidir ; gerçekten, Markov rastgele alanı, Ising modeli için genel ayar olarak tanıtıldı. Alanında ise yapay zeka , bir Markov rasgele alan orta düzey görevlere çeşitli düşük modellemek için kullanılan görüntü işleme ve bilgisayar görüşü .

Tanım

Yönlendirilmemiş bir grafik verildiğinde   , yerel Markov özelliklerini karşılayıp karşılamadıklarına   göre bir Markov rasgele alanı oluşturarak indekslenen bir rasgele değişkenler kümesi :

Pairwise Markov özelliği: Bitişik olmayan herhangi iki değişken, diğer tüm değişkenler göz önüne alındığında koşullu olarak bağımsızdır :
Yerel Markov özelliği: Bir değişken, komşuları verilen diğer tüm değişkenlerden koşullu olarak bağımsızdır:
nerede ait komşularının kümesidir ve bir kapalı semt arasında .
Global Markov özelliği: Herhangi iki değişken alt kümesi, bir ayırma alt kümesi verildiğinde koşullu olarak bağımsızdır:
burada bir düğümden her yol bir düğüme geçirmelerle .

Global Markov özelliği, sırasıyla Pairwise olandan daha güçlü olan Yerel Markov özelliğinden daha güçlüdür. Bununla birlikte, yukarıdaki üç Markov özelliği, pozitif dağılımlar için eşdeğerdir (ilişkili değişkenlere yalnızca sıfırdan farklı olasılıklar atayanlar).

klik çarpanlarına ayırma

Rastgele bir olasılık dağılımının Markov özelliğinin oluşturulması zor olabileceğinden, yaygın olarak kullanılan bir Markov rastgele alan sınıfı , grafiğin kliklerine göre çarpanlara ayrılabilenlerdir .

Rasgele değişkenler kümesi Verilen , let olmak olasılık belirli bir alan konfigürasyonun içinde  . Yani, rastgele değişkenlerin belirli bir değeri aldığını bulma olasılığıdır . Çünkü bir dizi, olasılığı anlaşılmalıdır bir göre alınacak ortak dağıtım arasında .

Bu eklem yoğunluğu aşağıdaki klikler üzerinden çarpanlara ayrılabilirse :

sonra göre bir Markov rasgele alanı oluşturur . Burada, klikler kümesidir . Tanım, yalnızca maksimum klikler kullanılıyorsa eşdeğerdir. Fonksiyonlar bazen faktör potansiyelleri veya klik potansiyelleri olarak adlandırılır . Bununla birlikte, çelişkili terminolojinin kullanımda olduğuna dikkat edin: potansiyel kelimesi genellikle logaritması için kullanılır . Bunun nedeni, istatistiksel mekanikte , bir konfigürasyonun potansiyel enerjisi olarak doğrudan bir yoruma sahip olmasıdır .  

Bazı MRF'ler çarpanlara ayırmaz: basit bir örnek, bazı sonsuz enerjilere sahip 4 düğümden oluşan bir döngü üzerine inşa edilebilir, yani sıfır olasılıklı konfigürasyonlar, daha uygun bir şekilde, sonsuz enerjilerin tam grafik üzerinde hareket etmesine izin verse bile .

Aşağıdaki koşullardan en az biri yerine getirildiğinde MRF'ler faktörleşir:

Böyle bir çarpanlara ayırma mevcut olduğunda , ağ için bir faktör grafiği oluşturmak mümkündür .

üstel aile

Herhangi bir pozitif Markov rasgele alanı , tam eklemli dağılımın şu şekilde yazılabileceği şekilde , özellik fonksiyonları ile kanonik biçimde üstel aile olarak yazılabilir.

notasyon nerede

alan konfigürasyonları üzerinde sadece bir nokta çarpımıdır ve Z , bölüm işlevidir :

Burada, ağın tüm rasgele değişkenlerine olası tüm değer atamaları kümesini belirtir. Genellikle özellik işlevleri oldukları olacak biçimde tanımlanır göstergeler klik yapılandırmasının, yani eğer karşılık gelir i arasında ıncı olası konfigürasyonu k -inci klik ve 0 aksi. Bu model, yukarıda verilen klik çarpanlara modeline eşdeğerdir klik kardinalitesi ve bir özellik ağırlığıdır gelen klik faktörü logaritması için karşılık gelir , yani , bir i muhtemel konfigürasyonunu inci k - inci klik, yani i clique etki inci değer .

P olasılığına genellikle Gibbs ölçüsü denir. Tüm klik faktörleri, sıfır olmayan ise bir lojistik model olarak Markov alanının bu ifade mümkündür , yani eğer elemanlarının yok Bu matris cebir teknikleri uygulanabilir sağlar 0 bir olasılık, atanır örneğin bu iz Bir matrisin değeri, determinantın günlüğüdür ve grafiğin geliş matrisinden kaynaklanan bir grafiğin matris temsili .

Z bölme fonksiyonunun önemi, entropi gibi istatistiksel mekanikten birçok kavramın doğrudan Markov ağları durumuna genellenmesi ve böylece sezgisel bir anlayış kazanılabilmesidir. Ek olarak, bölme işlevi , problemin çözümüne değişken yöntemlerin uygulanmasına izin verir : bir veya daha fazla rastgele değişkene bir itici güç eklenebilir ve bu bozulmaya yanıt olarak ağın tepkisi araştırılabilir . Bu nedenle, örneğin, grafiğin her köşesi v için, aşağıdakileri elde etmek için bölme işlevine bir J v sürücü terimi eklenebilir :

Resmi olarak göre farklılaşan J v verir beklenti değeri rasgele değişken bölgesinin X v tepe ilişkili v :

Korelasyon fonksiyonları da aynı şekilde hesaplanır; iki noktalı korelasyon:

Ne yazık ki, bir lojistik Markov ağının olasılığı dışbükey olsa da, bir modelin olasılığının olasılığını veya gradyanını değerlendirmek, modelde genellikle hesaplama açısından mümkün olmayan çıkarsama gerektirir (aşağıdaki 'Çıkarım'a bakın).

Örnekler

Gauss

Bir çok değişkenli normal dağılım bir grafik ile ilgili olarak bir Markov rasgele bir alan oluşturur eksik kenarları sıfırların uygun ise hassas bir matris (ters kovaryans matrisi ):

öyle ki

çıkarım

Bir Bayes ağında olduğu gibi , Markov rasgele alanındaki tüm olası atamaları toplayarak, değerler verilen bir dizi düğümün koşullu dağılımını hesaplayabilir ; buna kesin çıkarım denir . Bununla birlikte, kesin çıkarım bir #P-tam sorundur ve bu nedenle genel durumda hesaplama açısından zorludur. Markov zinciri Monte Carlo ve döngüsel inanç yayılımı gibi yaklaşım teknikleri pratikte genellikle daha uygundur. Ağaçlar (bkz. Chow-Liu ağacı ) gibi MRF'lerin bazı özel alt sınıfları, polinom zamanlı çıkarım algoritmalarına sahiptir; bu tür alt sınıfları keşfetmek aktif bir araştırma konusudur. Etkili izin MRF alt sınıfları vardır MAP , veya muhtemelen atama çıkarım; bunlara örnek olarak ilişkisel ağlar dahildir. Bir başka ilginç alt sınıf, ayrıştırılabilir modellerden biridir (grafik kordal olduğunda ): MLE için kapalı bir forma sahip olarak , yüzlerce değişken için tutarlı bir yapı keşfetmek mümkündür.

Koşullu rastgele alanlar

Markov rasgele alanının dikkate değer bir varyantı, her rasgele değişkenin aynı zamanda bir dizi global gözleme göre koşullandırılabileceği koşullu rasgele alandır . Bu modelde, her fonksiyon hem k grubuna yapılan tüm atamalardan hem de negatif olmayan gerçek sayılara yapılan gözlemlerden bir eşlemedir. Markov ağının bu formu , dağılımı gözlemler üzerinden modellemeyen ayırt edici sınıflandırıcılar üretmek için daha uygun olabilir . CRF'ler 2001 yılında John D. Lafferty , Andrew McCallum ve Fernando CN Pereira tarafından önerildi .

Çeşitli uygulamalar

Markov rastgele alanları, bilgisayar grafiklerinden bilgisayarla görme, makine öğrenimi veya hesaplamalı biyolojiye kadar çeşitli alanlarda uygulama bulur . MRF'ler, esnek ve stokastik görüntü modelleri oluşturmak için kullanılabildikleri için dokular oluşturmak için görüntü işlemede kullanılır. Görüntü modellemede görev, uygunluğun görevin türüne bağlı olduğu ve MRF'lerin görüntü ve doku sentezi, görüntü sıkıştırma ve restorasyon, görüntü bölütleme , 3D görüntü için kullanılabilecek kadar esnek olduğu belirli bir görüntünün uygun yoğunluk dağılımını bulmaktır. 2D görüntülerden çıkarım, görüntü kaydı , doku sentezi , süper çözünürlük , stereo eşleştirme ve bilgi alma . Bölge kategorisini tahmin etmek için bir Markov rasgele alan çerçevesi içinde bir dizi ayırt edici özellik kullanılarak farklı bölgelerin ayırt edilmesi gereken enerji minimizasyon problemleri veya problemler olarak ortaya konabilen çeşitli bilgisayarla görme problemlerini çözmek için kullanılabilirler. Markov rasgele alanları, Ising modeli üzerinde bir genellemeydi ve o zamandan beri, kombinatoryal optimizasyonlarda ve ağlarda yaygın olarak kullanılmaktadır.

Ayrıca bakınız

Referanslar