İçeriğe atla
Arama sonuçlarına dön

Beklenti-Maksimizasyon (EM) Algoritması

Ortaya koyan
Dempster, Laird & Rubin
Yıl
1977
Tür
Iterative optimization algorithm
Aile
Estimation

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Beklenti-Maksimizasyon (EM) algoritması, gizli değişkenler veya eksik veriler içeren istatistiksel modellerde parametrelerin maksimum olabilirlik veya maksimum a posteriori tahminlerini bulmak için kullanılan iteratif bir optimizasyon prosedürüdür.

Dempster, Laird ve Rubin tarafından 1977 tarihli önemli makalelerinde tanıtılan EM, tamamlanmış veri log-olabilirlik beklentisini hesaplama (E-adımı) ve bunu parametrelere göre maksimize etme (M-adımı) arasında gidip gelerek her iterasyonda monoton artan bir olabilirlik sağlar.

Yöntemin mantığı

Kartlarını göremediğiniz oyuncuları izleyerek bir oyunun kurallarını öğrenmeye çalıştığınızı hayal edin. Her turda, gözlemlediklerinize dayanarak muhtemelen hangi kartlara sahip olduklarını tahmin edersiniz, ardından bu tahminlerin doğru olduğunu varsayarak kurallar hakkındaki modelinizi güncellersiniz. EM tam olarak bunu yapar: E-adımı, mevcut parametre tahminlerini kullanarak eksik bilgiyi olasılıksal olarak doldurur ve M-adımı, doldurulmuş değerlerin gerçek gözlemler olduğunu varsayarak modeli yeniden ayarlar.

Tarih

Algoritma, Arthur Dempster, Nan Laird ve Donald Rubin tarafından 1977 tarihli JRSS-B makalelerinde resmen birleştirilmiş ve adlandırılmıştır; bu makale şimdiye kadar en çok atıfta bulunulan istatistik makalelerinden biri olmaya devam etmektedir. Makale, belirli eksik veri sorunları için bağımsız olarak geliştirilen önceki özel durum prosedürlerini genelleştirmiştir. Sonraki on yıllarda ECM, ECME, AECM ve SEM algoritmaları dahil olmak üzere çok sayıda uzantı üretilmiş, uygulanabilirliği genişletmiş ve birçok pratik durumda yakınsamayı hızlandırmıştır.

Ne zaman kullanılır?

Veriler eksik değerler, gizli durumlar veya gizli değişkenler içerdiğinde ve maksimum olabilirlik tahminlerine ihtiyaç duyduğunuzda EM algoritmasını kullanın. Gauss karışım modelleri, gizli Markov modelleri, faktör analizi ve eksik veri ataması için uygundur. Temel varsayımlar, eksik verilerin rastgele eksik (MAR) olduğu ve tamamlanmış veri modelinin çözülebilir olduğudur. Sınırlamalar, başlatmaya duyarlılığı, yerel maksimumlara olası yakınsamayı ve eyer noktalarına yakın yavaş yakınsamayı içerir. Alternatifler arasında sayısal entegrasyonlu gradyan tabanlı optimizasyon, varyasyonel çıkarım veya MCMC yöntemleri bulunur.

Sınırlar ve dikkat edilmesi gerekenler

  • Olabilirlik yüzeyi çok modlu olduğunda küresel maksimum yerine yerel maksimuma yakınsama
  • Eksik bilgi oranı büyük olduğunda çok yavaş (doğrusal) yakınsama sergileyebilir
  • Analistin tamamlanmış veri modelini ve gizli değişkenlerin dağılımını belirtmesini gerektirir
  • Standart EM, tahminlerin gözlemlenen veri kovaryans matrisini doğrudan sağlamaz; standart hatalar için ek bir adım (örneğin, Louis yöntemi veya SEM algoritması) gereklidir

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Her iterasyonda gözlemlenen veri olabilirliklerinde garantili monoton artış, kararlı yakınsamayı sağlar
  • Zor bir eksik veri problemini çözülebilir tamamlanmış veri optimizasyon dizisine dönüştürür
  • Üstel aile modelleri, karışım modelleri ve gizli değişken çerçeveleri boyunca geniş çapta uygulanabilir
  • Birçok standart model için kapalı form M-adımı güncellemeleri mevcuttur, bu da uygulamayı verimli hale getirir

Uygulama alanları

  • Kümeleme ve yoğunluk tahmini için Gauss karışım modellerini uyarlama
  • Konuşma tanıma ve biyolojik dizi analizi için gizli Markov modellerini eğitme
  • Klinik ve sosyal bilim araştırmalarında çoklu atama ve eksik veri analizi
  • Faktör analizi ve gizli sınıf analizinde parametre tahmini
  • Tıbbi görüntülemede görüntü segmentasyonu ve yeniden yapılandırma

Nasıl çalışır?

Nasıl çalışır?

1

İterasyon başlamadan önce analist, bilinmeyen parametreler için başlangıç değerleri seçer, bunlar $\theta_0$ ile gösterilir. Bunlar rastgele, basitleştirilmiş bir uydurmadan veya alan bilgisinden seçilebilir. Başlatmanın kalitesi, algoritmanın hangi yerel maksimuma yakınsayacağını etkileyebilir, bu da birden fazla rastgele yeniden başlatmayı yaygın bir uygulama haline getirir.

Formül
\text{Choose initial parameter estimates } \theta^{(0)}
2

Mevcut parametre tahmini $\theta_t$ verildiğinde, E-adımı, gözlemlenen verilere X koşullu olarak, gözlemlenmeyen gizli değişkenler Z'nin dağılımı üzerinden tamamlanmış veri log-olabilirlik beklentisi olan Q'yu hesaplar. Bu beklenti, tek bir atanan değerle sınırlı kalmadan bilinmeyen nicelikleri olasılıksal tahminleriyle etkili bir şekilde değiştirir.

Formül
Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)]
3

M-adımı, E-adımından gelen Q fonksiyonunu $\theta$'ya göre maksimize ederek güncellenmiş bir $\theta_{t+1}$ tahmini üretir. Tamamlanmış veri log-olabilirliği, marjinal gözlemlenen veri olabilirliğinden maksimize etmek için genellikle daha basit olduğundan, bu adım doğrudan maksimum olabilirlik mümkün olmasa bile sıklıkla çözülebilir.

Formül
\theta^{(t+1)} = \arg\max_{\theta} \, Q(\theta \mid \theta^{(t)})
4

E- ve M-adımları dönüşümlü olarak tekrarlanır. Her tam döngüden sonra, gözlemlenen veri log-olabilirliği değerlendirilir. İterasyon, log-olabilirlik (veya parametre vektöründeki) değişiklik kullanıcı tanımlı bir tolerans epsilon'un altına düştüğünde durur. Dempster ve arkadaşları, her döngünün gözlemlenen veri olabilirlikini azaltamayacağını kanıtlayarak kararlı yakınsamayı sağlamıştır.

Formül
\text{Repeat E- and M-steps until } |\ell(\theta^{(t+1)}) - \ell(\theta^{(t)})| < \epsilon

Sık yapılan hatalar

  • Tek bir rastgele başlatma kullanmak, kötü bir yerel maksimumda sonlanma riskini taşır; her zaman birden fazla yeniden başlatma çalıştırın ve en yüksek nihai log-olabilirliğe sahip çözümü saklayın
  • Yalnızca parametre değişimini izleyerek çok erken yakınsama beyan etmek yerine gözlemlenen veri log-olabilirliğini izlemek, yanlış tahminlere yol açabilir
  • Veriler Rastgele Eksik Olmadığında (MNAR) model ayarlaması olmadan EM uygulamak, tahminlerde sistematik yanlılığa neden olabilir
  • Karışım modellerinde etiket değiştirme problemini göz ardı etmek, doğru yakınsamadan sonra bile yorumlanamayan bileşen atamalarına yol açar

Sık sorulan sorular

EM algoritması her zaman küresel maksimuma yakınsar mı?

Hayır. EM, yalnızca gözlemlenen veri olabilirliklerinin yerel bir maksimumuna (veya eyer noktasına) yakınsayacağı garanti edilir. Olabilirlik yüzeyinin birden fazla modu olduğunda, nihai çözüm başlatmaya bağlıdır. Algoritmayı birkaç farklı başlangıç noktasından çalıştırmak ve en yüksek log-olabilirliğe sahip çözümü saklamak standart pratik çözümdür.

EM, doğrudan maksimum olabilirlik optimizasyonundan nasıl farklıdır?

Doğrudan MLE, gizli değişkenler üzerinden çözülemeyen integralleri içerebilen gözlemlenen veri log-olabilirliğini maksimize eder. EM, genellikle analitik olarak çözülebilen tamamlanmış veri log-olabilirlik beklentisini iteratif olarak maksimize ederek bunu atlar. Karşılığında EM yavaş yakınsayabilirken, gradyan tabanlı yöntemler marjinal olabilirlik gradyanları mevcut olduğunda daha hızlı olabilir.

MICE atamasını EM algoritmasına ne zaman tercih etmeliyim?

MICE (Zincir Denklemlerle Çoklu Atama), verilerde karışık türde değişkenler, doğrusal olmayan ilişkiler veya tek bir parametrik tamamlanmış veri modelinde kodlanması zor karmaşık etkileşim yapıları bulunduğunda tercih edilir. EM, tüm değişkenler için iyi tanımlanmış bir ortak modelin bulunduğu ve çıkarımın model parametrelerini hedeflediği, atanan veri kümelerini değil, durumlarda daha doğaldır.

İlgili yöntemler

Kaynaklar

  1. Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B, 39(1), 1–38.

    DOI kaynağını aç
    Kopyalandı.