Skip to content
Kembali ke hasil pencarian

Propagasi Label

Diperkenalkan oleh
Zhu, X. & Ghahramani, Z.
Tahun
2002
Jenis
Graph-based semi-supervised classification

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Propagasi Label adalah algoritma pembelajaran semi-terawasi berbasis graf yang diperkenalkan oleh Zhu dan Ghahramani pada tahun 2002 yang menyebarkan label kelas dari sejumlah kecil node berlabel ke sejumlah besar node tidak berlabel dengan secara iteratif mendifusikan informasi label di sepanjang tepi graf kesamaan, mengeksploitasi struktur manifold data.

Intuisi di balik metode

Bayangkan sebuah jejaring sosial di mana beberapa orang telah ditugaskan sebuah kategori. Rumor menyebar secara alami: setiap orang cenderung mengadopsi label yang paling umum di antara tetangga dekat mereka. Propagasi Label memformalkan intuisi ini — ia membangun graf berbobot di mana titik data yang serupa terhubung oleh tepi yang kuat, kemudian membiarkan label yang diketahui mengalir keluar langkah demi langkah sampai setiap titik tidak berlabel telah menyerap sinyal yang cukup untuk diklasifikasikan. Karena difusi mengikuti geometri data daripada batas keputusan arbitrer, ia dapat menghasilkan prediksi yang sangat akurat bahkan ketika contoh berlabel langka.

Sejarah

Xiaojin (Jerry) Zhu dan Zoubin Ghahramani memperkenalkan Propagasi Label dalam laporan teknis Carnegie Mellon University tahun 2002 (CMU-CALD-02-107). Tahun berikutnya, Zhu, Ghahramani, dan John Lafferty menerbitkan kerangka kerja medan Gaussian dan fungsi harmonik yang terkait erat di ICML 2003, memberikan interpretasi probabilistik melalui jalan acak dan medan acak Markov Gaussian. Karya-karya ini mengkatalisasi gelombang metode semi-terawasi berbasis graf sepanjang pertengahan 2000-an. Dengyong Zhou dan rekan-rekannya mengusulkan Penyebaran Label pada tahun 2004 — varian yang diregularisasi yang memungkinkan informasi label untuk sebagian mengesampingkan label yang dijepit, menawarkan ketahanan terhadap anotasi yang berisik. Kedua metode sekarang menjadi baseline standar dalam tolok ukur pembelajaran semi-terawasi dan disertakan dalam pustaka pembelajaran mesin yang banyak digunakan. Dengan munculnya jaringan saraf graf pada tahun 2010-an, Propagasi Label menjadi pendahulu konseptual dan baseline yang kompetitif, masih dikutip karena kesederhanaan dan jaminan bentuk tertutupnya.

Kapan digunakan

Propagasi Label sesuai ketika contoh berlabel langka dibandingkan dengan ukuran dataset total, data memiliki struktur cluster atau manifold yang mendasarinya yang dapat ditangkap oleh graf kesamaan, dan ada alasan untuk percaya bahwa asumsi kelancaran berlaku — bahwa titik-titik terdekat (dalam ruang fitur) cenderung berbagi label yang sama. Skenario tipikal termasuk kategorisasi teks dengan sedikit dokumen yang dianotasi, klasifikasi gambar dengan label manusia yang jarang, dan klasifikasi node jaringan. Metode ini mensyaratkan bahwa graf terhubung (atau setidaknya setiap node tidak berlabel dapat dijangkau dari node berlabel). Metode ini tidak cocok ketika ruang fitur tidak mencerminkan kesamaan semantik, ketika batas keputusan memotong wilayah padat, atau ketika semua data sudah berlabel.

Batasan dan pertimbangan

  • Skalabilitas: menyimpan dan mengoperasikan matriks bobot n x n tidak memungkinkan untuk dataset besar tanpa aproksimasi jarang.
  • Konstruksi graf sensitif terhadap pilihan lebar pita kernel sigma dan ukuran lingkungan k; pilihan yang buruk secara substansial menurunkan akurasi.
  • Mengasumsikan asumsi kelancaran (cluster): melanggarnya — ketika batas keputusan melewati wilayah padat — menyebabkan kesalahan klasifikasi sistematis.
  • Transduktif secara default: prediksi untuk titik uji baru yang belum terlihat memerlukan pengulangan algoritma atau ekstensi induktif.
  • Kebisingan label pada beberapa node berlabel menyebar dan dapat merusak sebagian besar graf.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Mengeksploitasi data tidak berlabel secara efektif, menghasilkan akurasi yang kuat dengan sangat sedikit contoh berlabel.
  • Jaminan konvergensi bentuk tertutup: pembaruan iteratif selalu mencapai titik tetap yang unik.
  • Secara alami menangani masalah multi-kelas tanpa modifikasi.
  • Interpretasi geometris intuitif yang didasarkan pada difusi graf dan analisis harmonik.
  • Tidak ada parameter model yang perlu dioptimalkan di luar pilihan konstruksi graf (lebar pita kernel, ukuran lingkungan).

Penerapan

  • Klasifikasi teks dan dokumen ketika hanya sebagian kecil dokumen yang membawa label yang ditetapkan manusia.
  • Anotasi gambar atau video di mana pelabelan manual mahal dan gambar tidak berlabel berlimpah.
  • Klasifikasi node jejaring sosial dan graf kutipan (misalnya, menyimpulkan minat pengguna atau topik makalah).
  • Bioinformatika: memprediksi fungsi gen atau peran interaksi protein dari jaringan biologis yang diberi anotasi sebagian.
  • Deteksi anomali semi-terawasi dengan menyebarkan label normal/anomali yang diketahui melalui graf kesamaan.

Cara kerjanya

Cara kerjanya

1

Sebuah graf kesamaan berbobot dibangun di atas semua n titik data — baik yang berlabel maupun yang tidak berlabel. Pilihan umum adalah kernel Gaussian (RBF): bobot tepi W_ij adalah fungsi yang menurun dari jarak Euclidean kuadrat antara titik i dan j, dikendalikan oleh parameter lebar pita sigma. Hanya k-tetangga terdekat atau tetangga radius epsilon yang dipertahankan sehingga graf tetap jarang.

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

Matriks bobot W dinormalisasi kolom untuk menghasilkan matriks transisi T yang stokastik baris, di mana setiap entri T_ij mewakili probabilitas bahwa informasi label mengalir dari node j ke node i. Ini memastikan bahwa total pengaruh yang diterima oleh setiap node berjumlah satu.

Rumus
T_{ij} = \frac{W_{ij}}{\sum_k W_{kj}}
3

Dimulai dari matriks label awal F (satu kolom per kelas), algoritma berulang: kalikan F dengan T, lalu jepit baris yang sesuai dengan node berlabel kembali ke label one-hot asli mereka Y_L. Penjepitan ini mencegah label yang diketahui bergeser dan bertindak sebagai kondisi batas yang menyerap. Iterasi diulang sampai entri tidak berlabel dari F konvergen.

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

Solusi titik tetap untuk blok tidak berlabel F_U* diberikan dalam bentuk tertutup sebagai (I - T_UU)^{-1} T_UL Y_L, di mana T_UU adalah submatriks transisi di antara node tidak berlabel dan T_UL menangkap transisi dari node berlabel ke node tidak berlabel. Dalam praktiknya, versi iteratif lebih disukai untuk graf besar karena menghindari inversi matriks; kedua rute menghasilkan solusi unik yang sama.

Rumus
F_U^* = (I - T_{UU})^{-1} T_{UL} Y_L

Kesalahan umum

  • Menggunakan graf yang terhubung penuh tanpa sparsifikasi, yang mengaburkan struktur lokal dan secara komputasi tidak dapat diatasi dalam skala besar.
  • Memilih sigma secara default tanpa validasi silang pada set berlabel, yang mengarah pada distribusi label yang terlalu halus atau kurang halus.
  • Mengabaikan ketidakseimbangan kelas: jika satu kelas mendominasi set berlabel, labelnya membanjiri graf; penimbangan ulang atau pengambilan sampel diperlukan.
  • Memperlakukan prediksi transduktif sebagai model yang terlatih dan menerapkannya pada titik-titik baru tanpa pembungkus induktif.
  • Gagal memeriksa konektivitas graf: node tidak berlabel dalam komponen terisolasi tidak menerima sinyal dan default ke probabilitas kelas seragam.

Pertanyaan yang sering diajukan

Apa perbedaan antara Propagasi Label dan Penyebaran Label?

Penyebaran Label, yang diusulkan oleh Zhou et al. (2004), memperkenalkan parameter regularisasi alpha yang mengontrol seberapa banyak setiap node mempertahankan label awalnya versus mengadopsi label tetangganya. Dalam Propagasi Label klasik, node berlabel dijepit dengan kaku, menjadikannya sepenuhnya menyerap. Penyebaran Label memungkinkan node berlabel untuk sebagian dikesampingkan, yang membuatnya lebih tahan terhadap kebisingan label dengan biaya satu hiperparameter tambahan.

Apakah Propagasi Label dapat diskalakan ke dataset besar?

Solusi bentuk tertutup naif memerlukan pembalikan matriks (n_U x n_U), yang tidak layak untuk n besar. Dalam praktiknya, graf k-tetangga terdekat atau radius epsilon yang jarang mengurangi memori menjadi O(nk), dan pembaruan iteratif kemudian diskalakan secara kasar secara linear dalam jumlah tepi per iterasi. Untuk graf yang sangat besar, metode tetangga terdekat perkiraan dan varian mini-batch digunakan.

Berapa banyak contoh berlabel yang dibutuhkan?

Propagasi Label dirancang khusus untuk rezim label ekstrem rendah. Bahkan satu node berlabel per kelas dapat menghasilkan prediksi yang bermakna jika struktur graf selaras dengan batas kelas, meskipun memiliki setidaknya beberapa contoh berlabel per kelas sangat direkomendasikan untuk keandalan. Kinerja menurun seiring meningkatnya kebisingan label atau ketika graf menjadi kurang informatif tentang keanggotaan kelas.

Bisakah Propagasi Label memprediksi data baru yang belum terlihat?

Dalam bentuk transduktif standarnya, tidak — algoritma beroperasi pada graf tetap dan tidak memiliki mekanisme untuk memprediksi di luar graf tersebut. Untuk penggunaan induktif, pendekatan umum adalah menghubungkan titik-titik baru ke k-tetangga terdekat mereka dalam graf yang ada dan menjalankan langkah propagasi parsial, atau menggunakan matriks label yang konvergen untuk melatih pengklasifikasi terawasi standar sebagai tahap kedua.

Metode terkait

Sumber

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

    Buka referensi publikasi
    Disalin.
  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.

    Buka referensi publikasi
    Disalin.
  3. Chapelle, O., Scholkopf, B., & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    ISBN: 978-0-262-03358-9
    Disalin.