الانتقال إلى المحتوى
العودة إلى نتائج البحث

انتشار التسمية

قدّمه
Zhu, X. & Ghahramani, Z.
السنة
2002
النوع
Graph-based semi-supervised classification

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

انتشار التسمية هو خوارزمية تعلم شبه موجهة قائمة على الرسوم البيانية قدمها تشو وغراماني في عام 2002، والتي تنشر تسميات الفئات من مجموعة صغيرة من العقد المسماة إلى مجموعة كبيرة من العقد غير المسماة عن طريق الانتشار التكراري لمعلومات التسمية على طول حواف رسم بياني للتشابه، مستغلة بنية المشعب للبيانات.

الفكرة الحدسية وراء الطريقة

تخيل شبكة اجتماعية حيث تم بالفعل تعيين فئة لبعض الأشخاص. تنتشر الشائعات بشكل طبيعي: يميل كل شخص إلى تبني التسمية الأكثر شيوعًا بين جيرانه المقربين. يقوم انتشار التسمية بتشكيل هذه الحدسية رسميًا - فهو يبني رسمًا بيانيًا مرجحًا حيث يتم توصيل نقاط البيانات المتشابهة بحواف قوية، ثم يسمح للتسميات المعروفة بالتدفق للخارج خطوة بخطوة حتى يمتص كل نقطة غير مسماة إشارة كافية لتصنيفها. نظرًا لأن الانتشار يتبع هندسة البيانات بدلاً من حدود القرار التعسفية، يمكنه إنتاج تنبؤات دقيقة للغاية حتى عندما تكون الأمثلة المسماة نادرة.

التاريخ

قدم شياو جين (جيري) تشو وزوبين غراماني انتشار التسمية في تقرير فني لجامعة كارنيجي ميلون عام 2002 (CMU-CALD-02-107). في العام التالي، نشر تشو وغراماني وجون لافيرتي إطار عمل حقول غاوسية ووظائف توافقية وثيق الصلة في ICML 2003، مما يوفر تفسيرًا احتماليًا عبر المشي العشوائي وحقول ماركوف الغاوسية العشوائية. حفزت هذه الأعمال موجة من الأساليب شبه الموجهة القائمة على الرسوم البيانية طوال منتصف العقد الأول من القرن الحادي والعشرين. اقترح دينغ يونغ تشو وزملاؤه انتشار التسمية في عام 2004 - وهو شكل منظم يسمح لمعلومات التسمية بتجاوز التسميات المثبتة جزئيًا، مما يوفر المتانة للتعليقات التوضيحية الصاخبة. كلا الطريقتين هما الآن خطوط أساس قياسية في معايير التعلم شبه الموجه ويتم تضمينهما في مكتبات التعلم الآلي شائعة الاستخدام. مع ظهور شبكات الرسوم البيانية العصبية في العقد الأول من القرن الحادي والعشرين، أصبح انتشار التسمية مقدمة مفاهيمية وخط أساس تنافسيًا، ولا يزال يُستشهد به لبساطته وضماناته في شكل مغلق.

متى تُستخدم

انتشار التسمية مناسب عندما تكون الأمثلة المسماة نادرة بالنسبة لحجم مجموعة البيانات الإجمالي، وللبيانات بنية عنقودية أو مشعب أساسية يمكن لرسم بياني للتشابه التقاطها، وهناك سبب للاعتقاد بأن افتراض السلاسة صحيح - أن النقاط القريبة (في مساحة الميزات) تميل إلى مشاركة نفس التسمية. تشمل السيناريوهات النموذجية تصنيف النصوص مع عدد قليل من المستندات المشروحة، وتصنيف الصور مع تسميات بشرية متفرقة، وتصنيف عقد الشبكة. تتطلب الطريقة أن يكون الرسم البياني متصلاً (أو على الأقل أن تكون كل عقدة غير مسماة قابلة للوصول من عقدة مسماة). إنها غير مناسبة عندما لا تعكس مساحة الميزات التشابه الدلالي، أو عندما يقطع حد القرار مناطق كثيفة، أو عندما تكون جميع البيانات مسماة بالفعل.

الحدود والاعتبارات

  • قابلية التوسع: تخزين وتشغيل مصفوفة وزن n x n أمر مستحيل لمجموعات البيانات الكبيرة بدون تقريبات متفرقة.
  • بناء الرسم البياني حساس لاختيار عرض نطاق النواة سيجما وحجم الجوار k؛ الخيارات السيئة تقلل الدقة بشكل كبير.
  • يفترض افتراض السلاسة (العنقودية): انتهاكه - عندما تمر حدود القرار عبر مناطق كثيفة - يؤدي إلى تصنيف خاطئ منهجي.
  • نقلية افتراضيًا: تتطلب التنبؤات لنقاط الاختبار الجديدة غير المرئية إعادة تشغيل الخوارزمية أو امتدادًا استقرائيًا.
  • تنتشر ضوضاء التسمية على العقد المسماة القليلة ويمكن أن تفسد جزءًا كبيرًا من الرسم البياني.

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

  • يستغل البيانات غير المسماة بفعالية، مما يؤدي إلى دقة قوية مع عدد قليل جدًا من الأمثلة المسماة.
  • ضمان التقارب في شكل مغلق: التحديث التكراري يصل دائمًا إلى نقطة ثابتة فريدة.
  • يتعامل بشكل طبيعي مع مشاكل الفئات المتعددة دون تعديل.
  • تفسير هندسي بديهي متجذر في انتشار الرسوم البيانية والتحليل التوافقي.
  • لا توجد معلمات نموذج لتحسينها بخلاف خيارات بناء الرسم البياني (عرض نطاق النواة، حجم الجوار).

التطبيقات

  • تصنيف النصوص والمستندات عندما تحمل نسبة صغيرة فقط من المستندات تسميات معينة يدويًا.
  • تسمية الصور أو الفيديو حيث يكون وضع العلامات اليدوية مكلفًا والصور غير المسماة وفيرة.
  • تصنيف عقد الشبكات الاجتماعية ورسوم بيانية الاقتباس (على سبيل المثال، استنتاج اهتمامات المستخدم أو مواضيع الورق).
  • المعلوماتية الحيوية: التنبؤ بوظيفة الجينات أو أدوار تفاعل البروتين من الشبكات البيولوجية المشروحة جزئيًا.
  • الكشف عن الشذوذ شبه الموجه عن طريق نشر تسميات طبيعية/شاذة معروفة عبر رسم بياني للتشابه.

كيف يعمل

كيف يعمل

1

يتم بناء رسم بياني مرجح للتشابه على جميع نقاط البيانات n - المسماة وغير المسماة. الخيار الشائع هو نواة غاوسية (RBF): وزن الحافة W_ij هو دالة متناقصة للمسافة الإقليدية المربعة بين النقاط i و j، يتم التحكم فيها بواسطة معلمة عرض النطاق الترددي سيجما. يتم الاحتفاظ فقط بجيران k الأقرب أو جيران نصف قطر epsilon بحيث يظل الرسم البياني متفرقًا.

الصيغة
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، ثم قم بتثبيت الصفوف المقابلة للعقد المسماة مرة أخرى إلى تسمياتها الحقيقية أحادية التشفير Y_L. يمنع هذا التثبيت التسميات المعروفة من الانجراف ويعمل كشرط حدودي ماص. يتم تكرار التكرار حتى تتقارب الإدخالات غير المسماة لـ 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

الأخطاء الشائعة

  • استخدام رسم بياني متصل بالكامل بدون تفرقة، مما يحجب البنية المحلية وغير قابل للحساب على نطاق واسع.
  • اختيار سيجما افتراضيًا بدون التحقق المتقاطع على المجموعة المسماة، مما يؤدي إلى توزيعات تسميات مفرطة أو ناقصة السلاسة.
  • تجاهل عدم توازن الفئات: إذا هيمنت فئة واحدة على المجموعة المسماة، فإن تسميتها تغمر الرسم البياني؛ يلزم إعادة الترجيح أو أخذ العينات.
  • معاملة التنبؤات النقلية كنموذج مدرب وتطبيقها على نقاط جديدة بدون غلاف استقرائي.
  • الفشل في التحقق من اتصال الرسم البياني: العقد غير المسماة في المكونات المعزولة لا تتلقى أي إشارة وتعود إلى احتمالات فئة موحدة.

الأسئلة الشائعة

ما هو الفرق بين انتشار التسمية وانتشار التسمية؟

يقدم انتشار التسمية، الذي اقترحه تشو وزملاؤه (2004)، معلمة تنظيم ألفا تتحكم في مقدار ما تحتفظ به كل عقدة بتسميتها الأولية مقابل تبني تسميات جيرانها. في انتشار التسمية الكلاسيكي، يتم تثبيت العقد المسماة بإحكام، مما يجعلها ماصة بالكامل. يسمح انتشار التسمية بتجاوز العقد المسماة جزئيًا، مما يجعلها أكثر متانة لضوضاء التسمية بتكلفة معلمة فائقة إضافية.

هل ينتشر انتشار التسمية إلى مجموعات البيانات الكبيرة؟

يتطلب الحل البسيط في شكل مغلق عكس مصفوفة (n_U x n_U)، وهو أمر غير ممكن لمجموعات n الكبيرة. في الممارسة العملية، يقلل رسم بياني متفرق لجيران k الأقرب أو نصف قطر epsilon الذاكرة إلى O(nk)، ثم يتوسع التحديث التكراري تقريبًا خطيًا في عدد الحواف لكل تكرار. بالنسبة للرسوم البيانية الكبيرة جدًا، يتم استخدام طرق الجار الأقرب التقريبية ومتغيرات الدُفعات الصغيرة.

كم عدد الأمثلة المسماة المطلوبة؟

تم تصميم انتشار التسمية خصيصًا لنظام التسمية المنخفض للغاية. حتى عقدة مسماة واحدة لكل فئة يمكن أن تنتج تنبؤات ذات مغزى إذا كان هيكل الرسم البياني يتوافق مع حدود الفئة، على الرغم من أن وجود عدد قليل على الأقل من الأمثلة المسماة لكل فئة موصى به بشدة للموثوقية. تتدهور الأداء مع زيادة ضوضاء التسمية أو عندما يصبح الرسم البياني أقل إفادة حول عضوية الفئة.

هل يمكن لانتشار التسمية التنبؤ ببيانات جديدة غير مرئية؟

في شكله النقلي القياسي، لا - تعمل الخوارزمية على رسم بياني ثابت وليس لديها آلية للتنبؤ خارج هذا الرسم البياني. للاستخدام الاستقرائي، يتمثل أحد الأساليب الشائعة في ربط النقاط الجديدة بجيرانها الأقرب 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
    تم النسخ.