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

Etiket Yayılımı

Ortaya koyan
Zhu, X. & Ghahramani, Z.
Yıl
2002
Tür
Graph-based semi-supervised classification

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

Yazı boyutu

Ne işe yarar?

Etiket Yayılımı, 2002'de Zhu ve Ghahramani tarafından tanıtılan, etiketli bir düğüm kümesinden etiketlenmemiş geniş bir düğüm kümesine sınıf etiketlerini yayan, benzerlik grafiğinin kenarları boyunca etiket bilgisini yinelemeli olarak yayan, verinin manifold yapısından yararlanan bir grafik tabanlı yarı denetimli öğrenme algoritmasıdır.

Yöntemin mantığı

Birkaç kişinin zaten bir kategoriye atanmış olduğu bir sosyal ağ hayal edin. Söylenti doğal olarak yayılır: her kişi yakın komşuları arasında en yaygın olan etiketi benimseme eğilimindedir. Etiket Yayılımı bu sezgiyi biçimlendirir — benzer veri noktalarının güçlü kenarlarla bağlandığı ağırlıklı bir graf oluşturur, ardından bilinen etiketlerin adım adım dışarı akmasına izin verir, böylece etiketlenmemiş her nokta sınıflandırılacak kadar sinyal emmiş olur. Yayılım, keyfi karar sınırları yerine verinin geometrisini izlediği için, etiketlenmiş örnekler az olsa bile oldukça doğru tahminler üretebilir.

Tarih

Xiaojin (Jerry) Zhu ve Zoubin Ghahramani, Etiket Yayılımı'nı 2002'de Carnegie Mellon Üniversitesi teknik raporunda (CMU-CALD-02-107) tanıttı. Ertesi yıl Zhu, Ghahramani ve John Lafferty, ICML 2003'te yakından ilişkili Gauss alanları ve harmonik fonksiyonlar çerçevesini yayınladı, rastgele yürüyüşler ve Gauss Markov rastgele alanları aracılığıyla olasılıksal bir yorum sağladı. Bu çalışmalar, 2000'lerin ortalarında grafik tabanlı yarı denetimli yöntemlerden oluşan bir dalgayı tetikledi. Dengyong Zhou ve meslektaşları 2004'te Etiket Yayılımı'nı önerdi — her düğümün başlangıç etiketini ne kadar koruduğunu komşularının etiketlerini ne kadar benimsediğini kontrol eden bir düzenlileştirme parametresi alfa'ya izin veren bir düzenlileştirilmiş varyant. Klasik Etiket Yayılımı'nda etiketlenmiş düğümler katı bir şekilde sabitlenir, onları tamamen emici hale getirir. Etiket Yayılımı, etiket gürültüsüne karşı daha sağlam olmasını sağlayan, ancak bir ek hiperparametre maliyetiyle, etiketlenmiş düğümlerin kısmen geçersiz kılınmasına izin verir. Bu yöntemler artık yarı denetimli öğrenme karşılaştırmalarında standart temel çizgilerdir ve yaygın olarak kullanılan makine öğrenimi kütüphanelerine dahil edilmiştir. 2010'larda grafik sinir ağlarının yükselişiyle birlikte, Etiket Yayılımı kavramsal bir öncü ve rekabetçi bir temel çizgi haline geldi, hala basitliği ve kapalı form garantileri için alıntılanmaktadır.

Ne zaman kullanılır?

Etiket Yayılımı, etiketlenmiş örneklerin toplam veri kümesi boyutuna göre az olduğu, verinin benzerlik grafiğinin yakalayabileceği bir küme veya manifold yapısına sahip olduğu ve düzgünlük varsayımının geçerli olduğuna inanmak için bir neden olduğu durumlarda uygundur — yani, yakın noktaların (özellik uzayında) aynı etiketi paylaşma eğiliminde olduğu durumlarda. Tipik senaryolar arasında az sayıda etiketlenmiş belge ile metin sınıflandırması, seyrek insan etiketleri ile görüntü sınıflandırması ve ağ düğümü sınıflandırması yer alır. Yöntem, grafiğin bağlı olmasını (veya en azından her etiketlenmemiş düğümün etiketlenmiş bir düğümden ulaşılabilir olmasını) gerektirir. Özellik uzayının anlamsal benzerliği yansıtmadığı, karar sınırının yoğun bölgelerden geçtiği veya tüm verilerin zaten etiketlenmiş olduğu durumlarda uygun değildir.

Sınırlar ve dikkat edilmesi gerekenler

  • Ölçeklenebilirlik: n x n ağırlık matrisini depolamak ve üzerinde işlem yapmak, seyrek yaklaşımlar olmadan büyük veri kümeleri için imkansızdır.
  • Grafik oluşturma, çekirdek bant genişliği sigma ve komşuluk boyutu k'nin seçimine duyarlıdır; kötü seçimler doğruluğu önemli ölçüde düşürür.
  • Düzgünlük (küme) varsayımını varsayar: bunu ihlal etmek — karar sınırları yoğun bölgelerden geçtiğinde — sistematik yanlış sınıflandırmaya yol açar.
  • Varsayılan olarak transdüktif: yeni, görülmemiş test noktaları için tahminler, algoritmayı yeniden çalıştırmayı veya endüktif bir uzantıyı gerektirir.
  • Etiketlenmiş az sayıdaki düğümdeki etiket gürültüsü yayılır ve grafiğin büyük bir kısmını bozabilir.

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

Güçlü yönleri

  • Etiketlenmemiş verilerden etkili bir şekilde yararlanır, çok az etiketlenmiş örnekle güçlü doğruluk sağlar.
  • Kapalı form yakınsama garantisi: yinelemeli güncelleme her zaman benzersiz bir sabit noktaya ulaşır.
  • Çok sınıflı problemleri modifikasyon olmaksızın doğal olarak ele alır.
  • Grafik yayılımı ve harmonik analize dayanan sezgisel geometrik yorum.
  • Grafik oluşturma seçimlerinin (çekirdek bant genişliği, komşuluk boyutu) ötesinde optimize edilecek model parametresi yoktur.

Uygulama alanları

  • Yalnızca belgelerin küçük bir kısmının insan tarafından atanmış etiketler taşıdığı metin ve belge sınıflandırması.
  • Manuel etiketlemenin pahalı olduğu ve etiketlenmemiş görüntülerin bol olduğu görüntü veya video etiketleme.
  • Sosyal ağ ve atıf grafiği düğüm sınıflandırması (örneğin, kullanıcı ilgi alanlarını veya makale konularını çıkarma).
  • Biyoenformatik: kısmen etiketlenmiş biyolojik ağlardan gen fonksiyonunu veya protein etkileşim rollerini tahmin etme.
  • Yarı denetimli anomali tespiti, bilinen normal/anormal etiketleri bir benzerlik grafiği aracılığıyla yayarak.

Nasıl çalışır?

Nasıl çalışır?

1

Hem etiketlenmiş hem de etiketlenmemiş tüm n veri noktası üzerinde ağırlıklı bir benzerlik grafiği oluşturulur. Yaygın bir seçim Gauss (RBF) çekirdeğidir: kenar ağırlığı W_ij, bant genişliği parametresi sigma tarafından kontrol edilen i ve j noktaları arasındaki karesel Öklid mesafesinin azalan bir fonksiyonudur. Grafik seyrek kalacak şekilde yalnızca k-en yakın komşular veya epsilon-yarıçaplı komşular tutulur.

Formül
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

Ağırlık matrisi W, satır-stokastik bir geçiş matrisi T üretmek üzere sütun normalleştirilir, burada her giriş T_ij, etiket bilgisinin j düğümünden i düğümüne akma olasılığını temsil eder. Bu, her düğümün aldığı toplam etkinin bire kadar toplandığını garanti eder.

Formül
T_{ij} = \frac{W_{ij}}{\sum_k W_{kj}}
3

Başlangıç etiket matrisi F (sınıf başına bir sütun) ile algoritma yinelenir: F'yi T ile çarpın, ardından etiketlenmiş düğümlere karşılık gelen satırları gerçek tek-sıcak etiketlerine Y_L geri sabitleyin. Bu sabitleme, bilinen etiketlerin kaymasını önler ve emici sınır koşulu görevi görür. Yineleme, F'nin etiketlenmemiş girişleri yakınsayana kadar tekrarlanır.

Formül
F^{(t+1)} = T F^{(t)}, \quad F_L = Y_L \text{ (clamp labeled rows after each step)}
4

Etiketlenmemiş blok F_U* için sabit nokta çözümü, T_UU etiketlenmemiş düğümler arasındaki geçiş alt matrisi ve T_UL etiketlenmişten etiketlenmemişe geçişleri yakalayan (I - T_UU)^{-1} T_UL Y_L olarak kapalı formda verilir. Pratikte, matris tersini önlediği için büyük grafikler için yinelemeli sürüm tercih edilir; her iki yol da aynı benzersiz çözümü verir.

Formül
F_U^* = (I - T_{UU})^{-1} T_{UL} Y_L

Sık yapılan hatalar

  • Seyreltme olmaksızın tam bağlı bir grafik kullanmak, yerel yapıyı gizler ve ölçekte hesaplama açısından çözülemez.
  • Etiketlenmiş küme üzerinde çapraz doğrulama yapmadan varsayılan olarak sigma seçmek, aşırı veya eksik düzgünleştirilmiş etiket dağılımlarına yol açar.
  • Sınıf dengesizliğini göz ardı etmek: bir sınıf etiketlenmiş kümede baskınsa, etiketi grafiği doldurur; yeniden ağırlıklandırma veya örnekleme gereklidir.
  • Transdüktif tahminleri eğitilmiş bir model olarak ele almak ve bunları endüktif bir sarmalayıcı olmadan yeni noktalara uygulamak.
  • Grafik bağlantısını kontrol etmemek: izole bileşenlerdeki etiketlenmemiş düğümler sinyal almaz ve tekdüze sınıf olasılıklarına varsayılan olarak ayarlanır.

Sık sorulan sorular

Etiket Yayılımı ile Etiket Yayılımı arasındaki fark nedir?

Zhou ve ark. (2004) tarafından önerilen Etiket Yayılımı, her düğümün başlangıç etiketini ne kadar koruduğunu komşularının etiketlerini ne kadar benimsediğini kontrol eden bir düzenlileştirme parametresi alfa'yı tanıtır. Klasik Etiket Yayılımı'nda etiketlenmiş düğümler katı bir şekilde sabitlenir, onları tamamen emici hale getirir. Etiket Yayılımı, etiket gürültüsüne karşı daha sağlam olmasını sağlayan, ancak bir ek hiperparametre maliyetiyle, etiketlenmiş düğümlerin kısmen geçersiz kılınmasına izin verir.

Etiket Yayılımı büyük veri kümelerine ölçeklenir mi?

Naif kapalı form çözümü, bir (n_U x n_U) matrisini tersine çevirmeyi gerektirir, bu da büyük n için imkansızdır. Pratikte, seyrek bir k-en yakın komşu veya epsilon-yarıçaplı grafik belleği O(nk)'ye düşürür ve ardından yinelemeli güncelleme, yineleme başına kenar sayısı ile kabaca doğrusal olarak ölçeklenir. Çok büyük grafikler için yaklaşık en yakın komşu yöntemleri ve mini-yığın varyantları kullanılır.

Kaç etiketlenmiş örneğe ihtiyaç vardır?

Etiket Yayılımı özellikle aşırı düşük etiketli rejim için tasarlanmıştır. Grafik yapısı sınıf sınırlarıyla uyumluysa, sınıflar başına tek bir etiketlenmiş düğüm bile anlamlı tahminler üretebilir, ancak güvenilirlik için sınıflar başına en az birkaç etiketlenmiş örneğe sahip olmak şiddetle tavsiye edilir. Performans, etiket gürültüsü arttıkça veya grafik sınıf üyeliği hakkında daha az bilgilendirici hale geldikçe düşer.

Etiket Yayılımı yeni, görülmemiş veri noktalarında tahmin yapabilir mi?

Standart transdüktif biçiminde, hayır — algoritma sabit bir grafik üzerinde çalışır ve bu grafiğin dışında tahmin yapmak için bir mekanizması yoktur. Endüktif kullanım için yaygın bir yaklaşım, yeni noktaları mevcut grafikteki k-en yakın komşularına bağlamak ve kısmi bir yayılım adımı çalıştırmak veya ikinci bir aşama olarak standart bir denetimli sınıflandırıcıyı eğitmek için yakınsamış etiket matrisini kullanmaktır.

İlgili yöntemler

Kaynaklar

  1. Zhu, X., & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.

    Yayın kaynağını aç
    Kopyalandı.
  2. Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the 20th International Conference on Machine Learning (ICML-2003), pp. 912–919.

    Yayın kaynağını aç
    Kopyalandı.
  3. Chapelle, O., Scholkopf, B., & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    ISBN: 978-0-262-03358-9
    Kopyalandı.