Koşullu rastgele alan - Conditional random field

Koşullu rastgele alanlar (CRF'ler) bir sınıftır istatistiksel modelleme yöntemi sıklıkla uygulandı desen tanıma ve makine öğrenme ve için kullanıldı yapılandırılmış tahmin. Oysa bir sınıflandırıcı "komşu" örnekleri dikkate almadan tek bir numune için bir etiket tahmin ettiğinde, bir CRF bağlamı hesaba katabilir. Bunu yapmak için tahmin, bir grafik model, tahminler arasında bağımlılıkları uygulayan. Ne tür bir grafiğin kullanıldığı uygulamaya bağlıdır. Örneğin, doğal dil işleme, doğrusal zincir CRF'leri, tahminlerde sıralı bağımlılıkları uygulayan popülerdir. Görüntü işlemede grafik tipik olarak konumları yakındaki ve / veya benzer konumlara bağlayarak benzer tahminler almalarını sağlar.

CRF'lerin kullanıldığı diğer örnekler şunlardır: etiketleme veya ayrıştırma sıralı veri doğal dil işleme veya biyolojik diziler,[1] POS etiketleme, sığ ayrıştırma,[2] adlandırılmış varlık tanıma,[3] gen bulma peptid kritik fonksiyonel bölge bulgusu,[4] ve nesne tanıma[5] ve Resim parçalama içinde Bilgisayar görüşü.[6]

Açıklama

CRF'ler bir tür ayırt edici yönsüz olasılığa dayalı grafik model.

Lafferty, McCallum ve Pereira[1] gözlemlerle ilgili bir CRF tanımlayın ve rastgele değişkenler aşağıdaki gibi:

İzin Vermek öyle bir grafik ol

, Böylece köşelerine göre dizine alınır . Sonra rastgele değişkenler olduğunda koşullu rastgele bir alandır koşullu itaat et Markov özelliği grafiğe bağlı olarak: , nerede anlamına gelir ve vardır komşular içinde .

Bunun anlamı, CRF'nin bir yönsüz grafik model düğümleri tam olarak iki ayrık kümeye bölünebilen ve sırasıyla gözlemlenen ve çıktı değişkenleri; koşullu dağılım daha sonra modellenmiştir.

Çıkarım

Genel grafikler için, CRF'lerde kesin çıkarım sorunu çözülemez. Bir CRF için çıkarım problemi temelde bir MRF ve aynı argümanlar geçerlidir.[7]Bununla birlikte, kesin çıkarımın mümkün olduğu özel durumlar vardır:

  • Grafik bir zincir veya ağaç ise, mesaj iletme algoritmaları kesin çözümler üretir. Bu durumlarda kullanılan algoritmalar, ileri geri ve Viterbi algoritması HMM'ler için.
  • CRF yalnızca ikili potansiyeller içeriyorsa ve enerji alt modüler kombinatoryal minimum kesme / maksimum akış algoritmaları kesin çözümler sağlar.

Kesin çıkarım imkansızsa, yaklaşık çözümler elde etmek için birkaç algoritma kullanılabilir. Bunlar şunları içerir:

Parametre Öğrenimi

Parametreleri öğrenmek genellikle tarafından yapılır maksimum olasılık için öğrenmek . Tüm düğümlerin üstel aile dağılımları varsa ve tüm düğümler eğitim sırasında gözlemlenirse, bu optimizasyon dışbükeydir.[7] Örneğin kullanılarak çözülebilir dereceli alçalma algoritmalar veya Quasi-Newton yöntemleri benzeri L-BFGS algoritması. Öte yandan, bazı değişkenler gözlenmiyorsa, bu değişkenler için çıkarım probleminin çözülmesi gerekir. Genel grafiklerde kesin sonuç çıkarılamaz, bu nedenle tahminler kullanılmalıdır.

Örnekler

Sıralı modellemede, ilgilenilen grafik genellikle bir zincir grafiğidir. Gözlemlenen değişkenlerin giriş dizisi bir dizi gözlemi temsil eder ve gözlemler verildiğinde çıkarılması gereken gizli (veya bilinmeyen) bir durum değişkenini temsil eder. her biri arasında bir kenar ile bir zincir oluşturacak şekilde yapılandırılmıştır. ve . Basit bir yorumunun yanı sıra Giriş sırasındaki her öğe için "etiketler" olarak, bu düzen aşağıdakiler için verimli algoritmalara izin verir:

  • model Eğitim, arasındaki koşullu dağılımları öğrenmek ve bazı eğitim verilerinden işlevler içerir.
  • kod çözme, belirli bir etiket dizisinin olasılığını belirleme verilen .
  • çıkarım, belirlemek büyük ihtimalle etiket dizisi verilen .

Her birinin koşullu bağımlılığı açık sabit bir dizi aracılığıyla tanımlanır özellik fonksiyonları şeklinde giriş sırasındaki ölçümler olarak düşünülebilir, olasılık olası her değerin . Model, her bir özelliğe sayısal bir ağırlık atar ve bunları, belirli bir değerin olasılığını belirlemek için birleştirir. .

Doğrusal zincirli CRF'ler, kavramsal olarak daha basit gizli Markov modelleri (HMM'ler) ile aynı uygulamaların çoğuna sahiptir, ancak giriş ve çıkış dizisi dağılımları hakkındaki belirli varsayımları gevşetir. Bir HMM, genel olarak durum geçişlerini ve emisyonları modellemek için sabit olasılıkları kullanan çok spesifik özellik işlevlerine sahip bir CRF olarak anlaşılabilir. Tersine, bir CRF, giriş sırasına bağlı olarak, sabit geçiş olasılıklarını gizli durumlar dizisindeki konumlar arasında değişen keyfi işlevlere dönüştüren bir HMM'nin genelleştirmesi olarak gevşek bir şekilde anlaşılabilir.

Özellikle, HMM'lerin aksine, CRF'ler herhangi bir sayıda özellik işlevi içerebilir, özellik işlevleri tüm giriş sırasını inceleyebilir çıkarım sırasında herhangi bir noktada ve özellik işlevlerinin aralığının olasılıklı bir yorumuna sahip olması gerekmez.

Varyantlar

Yüksek dereceli CRF'ler ve yarı Markov CRF'ler

CRF'ler, her biri yapılarak daha yüksek seviyeli modellere genişletilebilir. sabit bir sayıya bağlı önceki değişkenlerin . Yüksek dereceden CRF'lerin geleneksel formülasyonlarında, eğitim ve çıkarım, yalnızca küçük değerler için pratiktir. (gibi k ≤ 5),[8] hesaplama maliyetleri katlanarak arttığı için .

Bununla birlikte, yakın zamandaki bir başka gelişme, Bayesci nonparametrikler alanındaki kavram ve araçları kullanarak bu sorunları iyileştirmeyi başardı. Özellikle, CRF-sonsuzluk yaklaşımı[9] ölçeklenebilir bir şekilde sonsuz uzunlukta zamansal dinamikleri öğrenebilen CRF tipi bir model oluşturur. Bu, sıralı gözlemlerde sonsuz uzunlukta dinamikleri öğrenmek için parametrik olmayan Bayesci bir model olan Sıralı Hatırlatıcıya (SM) dayanan yeni bir potansiyel fonksiyonun CRF'ler için tanıtılmasıyla gerçekleştirilir.[10] Böyle bir modeli sayısal olarak izlenebilir hale getirmek için CRF-infinity, bir ortalama alan yaklaşımı[11] varsayılan yeni potansiyel fonksiyonların (bir SM tarafından yönlendirilen). Bu, modelin keyfi uzunluktaki zamansal bağımlılıkları yakalama ve modelleme yeteneğini zayıflatmadan, model için verimli yaklaşık eğitim ve çıkarım algoritmaları tasarlamaya izin verir.

CRF'lerin başka bir genellemesi vardır, yarı Markov koşullu rasgele alan (yarı-CRF), değişken uzunluklu segmentasyonlar etiket dizisinin .[12] Bu, yüksek dereceli CRF'lerin gücünün çoğunu, uzun menzilli bağımlılıklarını modellemek için sağlar. , makul bir hesaplama maliyetiyle.

Son olarak, büyük marjlı modeller yapılandırılmış tahmin, benzeri yapılandırılmış Destek Vektör Makinesi CRF'lere alternatif bir eğitim prosedürü olarak görülebilir.

Gizli dinamik koşullu rastgele alan

Gizli dinamik koşullu rastgele alanlar (LDCRF) veya ayırt edici olasılıklı gizli değişken modeller (DPLVM), sıra etiketleme görevleri için bir CRF türüdür. Onlar gizli değişken modeller ayrımcı bir şekilde eğitilmiş.

Bir dizi gözlem verildiğinde, herhangi bir sıralı etiketleme görevinde olduğu gibi bir LDCRF'de x = modelin çözmesi gereken temel sorun, bir dizi etiketin nasıl atanacağıdır. y = sonlu bir etiket kümesinden Y. Doğrudan modelleme yerine P(y|x) sıradan bir doğrusal zincirli CRF'nin yapacağı gibi, bir dizi gizli değişken h arasına "eklendi" x ve y kullanmak zincir olasılık kuralı:[13]

Bu, gözlemler ve etiketler arasındaki gizli yapının yakalanmasına izin verir.[14] LDCRF'ler yarı-Newton yöntemleri kullanılarak eğitilebilirken, Algılayıcı algoritma denilen gizli değişken algılayıcı Collins'e göre onlar için de geliştirilmiştir. yapılandırılmış algılayıcı algoritması.[13] Bu modeller uygulamaları şurada bulur: Bilgisayar görüşü özellikle mimik tanıma video akışlarından[14] ve sığ ayrıştırma.[13]

Yazılım

Bu, genel CRF araçlarını uygulayan yazılımların kısmi bir listesidir.

Bu, CRF ile ilgili araçları uygulayan yazılımların kısmi bir listesidir.

Ayrıca bakınız

Referanslar

  1. ^ a b Lafferty, J., McCallum, A., Pereira, F. (2001). "Koşullu rastgele alanlar: Sıra verilerini bölümlere ayırmak ve etiketlemek için olasılık modelleri". Proc. 18. Uluslararası Konf. Makine Öğreniminde. Morgan Kaufmann. s. 282–289.CS1 Maint: yazar parametresini kullanır (bağlantı)
  2. ^ Sha, F .; Pereira, F. (2003). koşullu rastgele alanlarla sığ ayrıştırma.
  3. ^ Yerleşir, B. (2004). "Koşullu rastgele alanlar ve zengin özellik kümeleri kullanarak biyomedikal adlı varlık tanıma" (PDF). Biyotıpta Doğal Dil İşleme ve Uygulamaları Üzerine Uluslararası Ortak Çalıştayın Bildirileri. sayfa 104–107.
  4. ^ Chang KY; Lin T-p; Shih L-Y; Wang C-K (2015). Koşullu Rastgele Alanlara Dayalı Antimikrobiyal Peptitlerin Kritik Bölgelerinin Analizi ve Tahmini. PLoS ONE. doi:10.1371 / journal.pone.0119490. PMC  4372350.
  5. ^ a b J.R. Ruiz-Sarmiento; C. Galindo; J. Gonzalez-Jimenez (2015). "UPGMpp: Bağlamsal Nesne Tanıma için Yazılım Kitaplığı.". 3 üncü. Sahne Anlama için Tanıma ve Eylem Çalıştayı (REACTS).
  6. ^ O, X.; Zemel, R.S .; Carreira-Perpinñán, MA (2004). "Görüntü etiketleme için çok ölçekli koşullu rastgele alanlar". IEEE Bilgisayar Topluluğu. CiteSeerX  10.1.1.3.7826.
  7. ^ a b Sutton, Charles; McCallum Andrew (2010). "Koşullu Rastgele Alanlara Giriş". arXiv:1011.4088v1 [stat.ML ].
  8. ^ Lavergne, Thomas; Yvon, François (7 Eylül 2017). "Değişken Sıralı CRF'lerin Yapısını Öğrenmek: Sonlu Durum Perspektifi". Doğal Dil İşlemede Ampirik Yöntemler 2017 Konferansı Bildirileri. Kopenhag, Danimarka: Hesaplamalı Dilbilim Derneği. s. 433.
  9. ^ Chatzis, Sotirios; Demiris, Yiannis (2013). "Sıralı Veri Modellemesi için Sonsuz Sıralı Koşullu Rastgele Alan Modeli". Örüntü Analizi ve Makine Zekası Üzerine IEEE İşlemleri. 35 (6): 1523–1534. doi:10.1109 / tpami.2012.208. hdl:10044/1/12614. PMID  23599063.
  10. ^ Gasthaus, Ocak; Teh, Yee Whye (2010). "Sekans Hafızasına İlişkin İyileştirmeler" (PDF). Proc. NIPS.
  11. ^ Celeux, G .; Forbes, F .; Peyrard, N. (2003). "Markov Modeline Dayalı Görüntü Segmentasyonu için Ortalama Alan Benzeri Yaklaşımları Kullanan EM Prosedürleri". Desen tanıma. 36 (1): 131–144. CiteSeerX  10.1.1.6.9064. doi:10.1016 / s0031-3203 (02) 00027-4.
  12. ^ Sarawagi, Sunita; Cohen, William W. (2005). "Bilgi çıkarma için yarı-Markov koşullu rasgele alanlar" (PDF). Lawrence K. Saul'da; Yair Weiss; Léon Bottou (editörler). Sinirsel Bilgi İşleme Sistemlerindeki Gelişmeler 17. Cambridge, MA: MIT Press. sayfa 1185–1192.
  13. ^ a b c Xu Sun; Takuya Matsuzaki; Daisuke Okanohara; Jun'ichi Tsujii (2009). Yapılandırılmış Sınıflandırma için Gizli Değişken Algılayıcı Algoritması. IJCAI. sayfa 1236–1242.
  14. ^ a b Morency, L. P .; Quattoni, A .; Darrell, T. (2007). "Sürekli Hareket Tanıma için Gizli Dinamik Ayrımcı Modeller" (PDF). 2007 IEEE Bilgisayarlı Görü ve Örüntü Tanıma Konferansı. s. 1. CiteSeerX  10.1.1.420.6836. doi:10.1109 / CVPR.2007.383299. ISBN  978-1-4244-1179-5.
  15. ^ T. Lavergne, O. Cappé ve F. Yvon (2010). Pratik çok büyük ölçekli CRF'ler Arşivlendi 2013-07-18 de Wayback Makinesi. Proc. 48. Yıllık Toplantısı EKL, s. 504-513.

daha fazla okuma

  • McCallum, A .: Koşullu rastgele alanların özelliklerini verimli bir şekilde indükleme. İçinde: Proc. Yapay Zekada Belirsizlik Konferansı 19. Konferansı. (2003)
  • Wallach, H.M .: Koşullu rastgele alanlar: Giriş. Teknik rapor MS-CIS-04-21, Pennsylvania Üniversitesi (2004)
  • Sutton, C., McCallum, A .: İlişkisel Öğrenme için Koşullu Rastgele Alanlara Giriş. "İstatistiksel İlişkisel Öğrenmeye Giriş" bölümünde. Tarafından düzenlendi Lise Getoor ve Ben Taskar. MIT Basın. (2006) Çevrimiçi PDF
  • Klinger, R., Tomanek, K .: Klasik Olasılık Modelleri ve Koşullu Rastgele Alanlar. Algoritma Mühendisliği Raporu TR07-2-013, Bilgisayar Bilimleri Bölümü, Dortmund Teknoloji Üniversitesi, Aralık 2007. ISSN 1864-4503. Çevrimiçi PDF