Skip to content
بازگشت به نتایج جست‌وجو

انتشار برچسب (Label Propagation)

معرفی‌شده توسط
Zhu, X. & Ghahramani, Z.
سال
2002
نوع
Graph-based semi-supervised classification

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

انتشار برچسب یک الگوریتم یادگیری نیمه‌نظارتی مبتنی بر گراف است که توسط ژو و قهرامانی در سال ۲۰۰۲ معرفی شد. این الگوریتم برچسب‌های کلاس را از مجموعه‌ای کوچک از گره‌های برچسب‌دار به مجموعه‌ای بزرگ از گره‌های بدون برچسب، با انتشار مکرر اطلاعات برچسب در امتداد یال‌های یک گراف شباهت و با بهره‌گیری از ساختار منیفلد داده‌ها، گسترش می‌دهد.

شهود پشت روش

یک شبکه اجتماعی را تصور کنید که در آن به تعداد کمی از افراد از قبل یک دسته اختصاص داده شده است. شایعه به طور طبیعی پخش می‌شود: هر فرد تمایل دارد برچسبی را بپذیرد که در میان همسایگان نزدیکش رایج‌تر است. انتشار برچسب این شهود را رسمی می‌کند — یک گراف وزن‌دار می‌سازد که در آن نقاط داده مشابه توسط یال‌های قوی به هم متصل می‌شوند، سپس اجازه می‌دهد برچسب‌های شناخته شده گام به گام به بیرون جریان یابند تا زمانی که هر نقطه بدون برچسب سیگنال کافی را برای طبقه‌بندی جذب کند. از آنجا که انتشار از هندسه داده‌ها پیروی می‌کند و نه از مرزهای تصمیم‌گیری دلخواه، می‌تواند پیش‌بینی‌های بسیار دقیقی را حتی زمانی که نمونه‌های برچسب‌دار کمیاب هستند، تولید کند.

تاریخ

شیائوجین (جری) ژو و زوبین قهرامانی انتشار برچسب را در یک گزارش فنی دانشگاه کارنگی ملون (CMU-CALD-02-107) در سال ۲۰۰۲ معرفی کردند. سال بعد، ژو، قهرامانی و جان لافرتی چارچوب میدان‌های گوسی و توابع هارمونیک مرتبط را در ICML 2003 منتشر کردند که تفسیری احتمالی از طریق گام‌های تصادفی و میدان‌های تصادفی مارکوف گوسی ارائه می‌داد. این آثار موجی از روش‌های نیمه‌نظارتی مبتنی بر گراف را در اواسط دهه ۲۰۰۰ کاتالیز کردند. دنگیونگ ژو و همکارانش در سال ۲۰۰۴ انتشار برچسب (Label Spreading) را پیشنهاد کردند — یک نوع منظم‌شده که به اطلاعات برچسب اجازه می‌دهد تا حدی بر برچسب‌های ثابت‌شده غلبه کند و مقاومت در برابر حاشیه‌نویسی‌های نویزدار را ارائه می‌دهد. هر دو روش اکنون به عنوان خطوط مبنای استاندارد در معیارهای یادگیری نیمه‌نظارتی هستند و در کتابخانه‌های یادگیری ماشین پرکاربرد گنجانده شده‌اند. با ظهور شبکه‌های عصبی گراف در دهه ۲۰۱۰، انتشار برچسب به یک پیش‌ساز مفهومی و یک خط مبنای رقابتی تبدیل شد که هنوز به دلیل سادگی و تضمین‌های فرم بسته آن مورد استناد قرار می‌گیرد.

چه زمانی استفاده شود

انتشار برچسب زمانی مناسب است که نمونه‌های برچسب‌دار نسبت به اندازه کل مجموعه داده کمیاب باشند، داده‌ها دارای ساختار خوشه‌ای یا منیفلد زیربنایی باشند که یک گراف شباهت بتواند آن را ثبت کند، و دلیلی برای باور به فرض همواری وجود داشته باشد — اینکه نقاط نزدیک (در فضای ویژگی) تمایل به اشتراک‌گذاری یک برچسب دارند. سناریوهای معمول شامل دسته‌بندی متن با تعداد کمی سند حاشیه‌نویسی شده، طبقه‌بندی تصویر با برچسب‌های انسانی پراکنده، و طبقه‌بندی گره‌های شبکه است. این روش نیازمند آن است که گراف متصل باشد (یا حداقل هر گره بدون برچسب از یک گره برچسب‌دار قابل دسترسی باشد). زمانی که فضای ویژگی بازتاب‌دهنده شباهت معنایی نباشد، زمانی که مرز تصمیم‌گیری از مناطق متراکم عبور کند، یا زمانی که تمام داده‌ها از قبل برچسب‌دار شده‌اند، مناسب نیست.

محدودیت‌ها و ملاحظات

  • مقیاس‌پذیری: ذخیره و عملیات بر روی یک ماتریس وزن n x n برای مجموعه‌های داده بزرگ بدون تقریب‌های تنک، بسیار پرهزینه است.
  • ساخت گراف به انتخاب پهنای باند هسته سیگما و اندازه همسایگی k حساس است؛ انتخاب‌های نامناسب به طور قابل توجهی دقت را کاهش می‌دهند.
  • فرض همواری (خوشه) را در نظر می‌گیرد: نقض آن — زمانی که مرزهای تصمیم‌گیری از مناطق متراکم عبور می‌کنند — منجر به طبقه‌بندی اشتباه سیستماتیک می‌شود.
  • به طور پیش‌فرض استنتاجی (transductive) است: پیش‌بینی برای نقاط آزمایشی جدید و دیده نشده نیازمند اجرای مجدد الگوریتم یا یک بسط استقرایی است.
  • نویز برچسب در گره‌های برچسب‌دار کم، منتشر می‌شود و می‌تواند بخش بزرگی از گراف را آلوده کند.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • داده‌های بدون برچسب را به طور مؤثر بهره‌برداری می‌کند و با تعداد بسیار کمی از نمونه‌های برچسب‌دار، دقت بالایی را به دست می‌دهد.
  • تضمین همگرایی به شکل بسته: به‌روزرسانی تکراری همیشه به یک نقطه ثابت منحصر به فرد می‌رسد.
  • مسائل چندکلاسه را به طور طبیعی و بدون تغییر مدیریت می‌کند.
  • تفسیر هندسی شهودی مبتنی بر انتشار گراف و تحلیل هارمونیک.
  • هیچ پارامتر مدلی برای بهینه‌سازی فراتر از انتخاب‌های ساخت گراف (پهنای باند هسته، اندازه همسایگی) وجود ندارد.

کاربردها

  • طبقه‌بندی متن و سند زمانی که تنها بخش کوچکی از اسناد دارای برچسب‌های انسانی هستند.
  • حاشیه‌نویسی تصویر یا ویدئو که برچسب‌گذاری دستی پرهزینه است و تصاویر بدون برچسب فراوان هستند.
  • طبقه‌بندی گره‌های شبکه اجتماعی و گراف استنادی (به عنوان مثال، استنتاج علایق کاربر یا موضوعات مقاله).
  • بیوانفورماتیک: پیش‌بینی عملکرد ژن یا نقش‌های تعامل پروتئین از شبکه‌های بیولوژیکی تا حدی حاشیه‌نویسی شده.
  • تشخیص ناهنجاری نیمه‌نظارتی با انتشار برچسب‌های عادی/ناهنجار شناخته شده از طریق یک گراف شباهت.

چگونه کار می‌کند

چگونه کار می‌کند

1

یک گراف شباهت وزن‌دار بر روی تمام n نقطه داده — هم برچسب‌دار و هم بدون برچسب — ساخته می‌شود. یک انتخاب رایج، هسته گوسی (RBF) است: وزن یال W_ij تابعی کاهشی از فاصله اقلیدسی مجذور بین نقاط i و j است که توسط پارامتر پهنای باند سیگما کنترل می‌شود. تنها k نزدیک‌ترین همسایه یا همسایگان در شعاع اپسیلون حفظ می‌شوند تا گراف تنک باقی بماند.

فرمول
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

ماتریس وزن W به صورت ستونی نرمال‌سازی می‌شود تا یک ماتریس انتقال ردیف-تصادفی T تولید شود، که در آن هر درایه T_ij نشان‌دهنده احتمال جریان اطلاعات برچسب از گره j به گره i است. این امر تضمین می‌کند که مجموع تأثیر دریافتی توسط هر گره برابر با یک است.

فرمول
T_{ij} = \frac{W_{ij}}{\sum_k W_{kj}}
3

با شروع از یک ماتریس برچسب اولیه F (یک ستون برای هر کلاس)، الگوریتم تکرار می‌شود: F را در T ضرب کنید، سپس ردیف‌های مربوط به گره‌های برچسب‌دار را به برچسب‌های یک-داغ (one-hot) واقعی خود Y_L برگردانید. این تثبیت (clamping) از انحراف برچسب‌های شناخته شده جلوگیری می‌کند و به عنوان یک شرط مرزی جذب‌کننده عمل می‌کند. تکرار تا زمانی که ورودی‌های بدون برچسب F همگرا شوند، ادامه می‌یابد.

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

راه حل نقطه ثابت برای بلوک بدون برچسب F_U* به صورت بسته به شکل (I - T_UU)^{-1} T_UL Y_L ارائه می‌شود، که در آن T_UU زیرماتریس انتقال بین گره‌های بدون برچسب و T_UL انتقال از گره‌های برچسب‌دار به گره‌های بدون برچسب را نشان می‌دهد. در عمل، نسخه تکراری برای گراف‌های بزرگ ترجیح داده می‌شود زیرا از وارونگی ماتریس جلوگیری می‌کند؛ هر دو مسیر به یک راه‌حل منحصر به فرد منجر می‌شوند.

فرمول
F_U^* = (I - T_{UU})^{-1} T_{UL} Y_L

دام‌های رایج

  • استفاده از یک گراف کاملاً متصل بدون تنک‌سازی، که ساختار محلی را مبهم می‌کند و از نظر محاسباتی در مقیاس بزرگ غیرقابل انجام است.
  • انتخاب پیش‌فرض سیگما بدون اعتبارسنجی متقابل بر روی مجموعه برچسب‌دار، که منجر به توزیع‌های برچسب بیش از حد هموار یا کمتر از حد هموار می‌شود.
  • نادیده گرفتن عدم تعادل کلاس: اگر یک کلاس در مجموعه برچسب‌دار غالب باشد، برچسب آن گراف را پر می‌کند؛ نیاز به وزن‌دهی مجدد یا نمونه‌برداری است.
  • در نظر گرفتن پیش‌بینی‌های استنتاجی به عنوان یک مدل آموزش‌دیده و اعمال آن‌ها بر روی نقاط جدید بدون یک پوشش استقرایی.
  • عدم بررسی اتصال گراف: گره‌های بدون برچسب در مؤلفه‌های ایزوله هیچ سیگنالی دریافت نمی‌کنند و به احتمالات کلاس یکنواخت پیش‌فرض می‌روند.

پرسش‌های متداول

تفاوت بین انتشار برچسب (Label Propagation) و گسترش برچسب (Label Spreading) چیست؟

گسترش برچسب (Label Spreading)، که توسط ژو و همکاران (۲۰۰۴) پیشنهاد شد، یک پارامتر منظم‌سازی آلفا را معرفی می‌کند که میزان حفظ برچسب اولیه هر گره در مقابل پذیرش برچسب‌های همسایگانش را کنترل می‌کند. در انتشار برچسب کلاسیک، گره‌های برچسب‌دار به طور سختگیرانه ثابت می‌شوند و آن‌ها را کاملاً جذب‌کننده می‌سازد. گسترش برچسب به گره‌های برچسب‌دار اجازه می‌دهد تا حدی نادیده گرفته شوند، که آن را در برابر نویز برچسب مقاوم‌تر می‌کند، اما به قیمت یک فراپارامتر اضافی.

آیا انتشار برچسب (Label Propagation) برای مجموعه‌های داده بزرگ مقیاس‌پذیر است؟

راه‌حل ساده فرم بسته نیازمند وارونگی یک ماتریس (n_U x n_U) است که برای n بزرگ غیرممکن است. در عمل، یک گراف k-نزدیک‌ترین همسایه یا شعاع اپسیلون تنک، حافظه را به O(nk) کاهش می‌دهد، و به‌روزرسانی تکراری سپس تقریباً خطی با تعداد یال‌ها در هر تکرار مقیاس‌پذیر است. برای گراف‌های بسیار بزرگ، از روش‌های تقریبی نزدیک‌ترین همسایه و انواع مینی-بچ استفاده می‌شود.

چند نمونه برچسب‌دار لازم است؟

انتشار برچسب به طور خاص برای رژیم برچسب کم طراحی شده است. حتی یک گره برچسب‌دار در هر کلاس می‌تواند پیش‌بینی‌های معنی‌داری تولید کند اگر ساختار گراف با مرزهای کلاس همسو باشد، اگرچه داشتن حداقل چند نمونه برچسب‌دار در هر کلاس برای قابلیت اطمینان به شدت توصیه می‌شود. عملکرد با افزایش نویز برچسب یا زمانی که گراف اطلاعات کمتری در مورد عضویت کلاس ارائه می‌دهد، کاهش می‌یابد.

آیا انتشار برچسب (Label Propagation) می‌تواند بر روی نقاط داده جدید و دیده نشده پیش‌بینی کند؟

در شکل استاندارد استنتاجی خود، خیر — الگوریتم بر روی یک گراف ثابت عمل می‌کند و مکانیزمی برای پیش‌بینی خارج از آن گراف ندارد. برای استفاده استقرایی، یک رویکرد رایج این است که نقاط جدید را به k-نزدیک‌ترین همسایگان خود در گراف موجود متصل کرده و یک مرحله انتشار جزئی را اجرا کنید، یا از ماتریس برچسب همگرا شده برای آموزش یک طبقه‌بندی‌کننده نظارتی استاندارد به عنوان مرحله دوم استفاده کنید.

روش‌های مرتبط

منابع

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

    باز کردن مرجع انتشار
    کپی شد.
  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.

    باز کردن مرجع انتشار
    کپی شد.
  3. Chapelle, O., Scholkopf, B., & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    شابک: 978-0-262-03358-9
    کپی شد.