Meta FAIR تطلق e-means: بديل أسرع من التجميع العنقودي k-means

أطلق باحثو Meta FAIR أداة e-means، وهي بديل مباشر لخوارزمية k-means من Lloyd. تحقق خوارزمية التجميع العنقودي الجديدة الخسارة التي تصل إليها خوارزمية Lloyd في 25 دورة خلال 1.4 إلى 2.6 دورة فقط. وهي متضمنة في FAISS 1.16.0 تحت faiss.contrib.e_means. بالنسبة للمطورين العاملين على فهارس المتجهات أو أدوات التكميم أو خطوط معالجة تنسيق البيانات، غالباً ما يمثل التجميع العنقودي أبطأ خطوة غير متصلة بالإنترنت، وهو ما تهدف e-means إلى تحسينه.

باختصار

• الحجم: خوارزمية اختُبرت من 100 ألف إلى 10 مليارات نقطة، وتدعم ما يصل إلى 16.7 مليون عنقود.
• بيئة التشغيل: CPU أو GPU، ومتوافقة مع PyTorch tensors أو NumPy. تستخدم تجارب GPU في الورقة البحثية وحدات H100.
• الأداء: خسارة أقل من k-means من Lloyd في نحو عُشر عدد الدورات عبر 24 إعداداً لمجموعات البيانات (بحسب الإبلاغ الذاتي).
• الأفضل: تسريع على GPU يتراوح بين 10 و45 ضعفاً مقارنة بـ Flash-KMeans عند خسارة متساوية.
• الأسوأ: تتطلب عمليات التشغيل بـ 16 مليون مركز 64 GiB من مراكمات float32، ما يستلزم توزيع المراكز (centroid sharding) عبر وحدات GPU.

ما هي e-means؟

e-means خوارزمية mini-batch k-means طورتها Meta FAIR وتحدّث المراكز باستخدام المتوسطات المتحركة الأسية (exponential moving averages).

كيف تعمل e-means؟

تحتفظ كل نسخة من k-means بمجموع S وعدد N لكل عنقود، ويُحسب المركز بقسمة S على N. وتختلف الطرق في كيفية تحديث S وN.

• Lloyd: يعيد حساب S وN من مجموعة البيانات كاملة في كل تكرار.
• MacQueen (1967): يضيف إحصاءات الدفعة باستمرار، ما يؤدي إلى بقاء التعيينات القديمة.
• e-means: يقلل الإحصاءات القديمة بمعدل α: S ← (1−α)S + αs، مع نهج مماثل لـ N.

يتيح هذا التلاشي للتعيينات الأقدم أن تخفت، ما يمكّن المراكز من عكس البيانات الحديثة بشكل أفضل. ويشير الفريق البحثي إلى أن طريقة Lloyd حالة خاصة تعمل بدفعة كاملة وα = 1، ما ينتج خسارة أعلى بنسبة 1.8% من أفضل خسارة.

اختبر الفريق أيضاً الانحدار التدرجي العادي كبديل، فجاء أداؤه أسوأ من e-means بنسبة 1.6% (DEEP) و0.4% (SIFT) عند أفضل إعداداته. ويرجح المؤلفون أن تكون e-means في وضع أفضل لأن المراكز تبقى باستمرار داخل الهيكل المحدب للنقاط المعينة لها.

ما الذي يحل محل ضبط المعاملات الفائقة؟

تحدد قانونان تناسبيان مُلائمان حجم الدفعة B والخطوة الأولية α0 بناءً على حجم مجموعة البيانات n وعدد العناقيد k والدورات T. وعلى مجموعات بيانات محجوزة، بلغ متوسط الندم (median regret) 0.07% لقانون الخطوة، الذي يتبع بعد ذلك جدولاً جيبياً من α0 إلى 0.1α0.

ما الذي تغير أيضاً؟

• إحياء العناقيد الميتة: تُحيا العناقيد التي تقل عن حد معين من الحجم عبر تقسيم عنقود أكبر.
• الإنهاء: ينتهي التدريب بمتوسط الدورة الأخيرة الدقيق لكل عنقود.
• نوى GPU المدمجة: يُدمج تعيين أقرب مركز، ما يقلل أزمنة الدورات.

ما مدى سرعة e-means في الاختبارات المعيارية؟

جميع مقاييس الأداء أدناه بحسب الإبلاغ الذاتي للمؤلفين.

• الدورات: تحقق e-means خسارة Lloyd عند 25 دورة في 1.4 إلى 2.6 دورة.
• GPU: تسريع في الزمن الفعلي يتراوح بين 10 و45 ضعفاً مقارنة بـ Flash-KMeans.
• CPU: تسريع يتراوح بين 8 و15 ضعفاً مقارنة بـ Faiss k-means.
• اختبار VIBE المعياري: تطلبت جميع مجموعات بيانات التضمين الـ 11 من 1.6 إلى 2.4 دورة.
• مقياس المليارات: قُسمت DINO10B، التي تضم 10 مليارات تضمين بأبعاد 1,024، إلى 16.7 مليون عنقود في 2.5 دورة.

يشير منشور الإصدار إلى أن عرضاً تجريبياً بخيط CPU واحد أظهر أن Lloyd استغرق 4.39 ثانية لـ 25 دورة، بينما أكملت e-means 2.2 دورة في 0.43 ثانية فقط. عالجت خطوة واحدة من Lloyd 100,000 نقطة في 0.176 ثانية، بينما عالجت e-means 512 نقطة في 0.001 ثانية.

تساعد ضوضاء الدفعة الصغيرة أيضاً في تجنب القيم الدنيا المحلية السيئة. في مثال لعبة من 5 كتل، علق Lloyd في 46% من 200 محاولة، بينما لم تشهد e-means أي ركود.

الإحياء مهم عند قيم k الأكبر. في مجموعة بيانات DEEP مع 16,384 عنقوداً، أسفر التقسيم النسبي عن 47 عنقوداً ميتاً (0.3%). ودون الإحياء، أصبحت 4,313 عنقوداً (26.3%) غير نشطة.

كيف تقارن e-means بخيارات k-means الأخرى؟

النقاط الرئيسية

• تستبدل e-means تحديث Lloyd بالدفعة الكاملة بدفعات صغيرة EMA.
• تضاهي أداء 25 دورة من Lloyd في 1.4 إلى 2.6 دورة فقط.
• توفر تحسينات سرعة تتراوح بين 10 و45 ضعفاً على GPU و8 و15 ضعفاً على CPU (بحسب الإبلاغ الذاتي).
• لا تتطلب ضبطاً، إذ تحدد قوانين التناسب أحجام الدفعات والخطوات.
• e-means متاحة الآن في FAISS 1.16.0.

رابط ذو صلة: e-means.github.io

 

المصدر: MarkTechPost