🤖 machine learning

Efficient Coreset Selection via K-Nearest Neighbor Graphs

تقدم هذه الورقة KNNG-CS، وهي طريقة خفيفة الوزن لاختيار النواة المركزية (coreset) تستفيد من رسوم الجوار لأقرب جار (K-nearest neighbor graphs) لتحديد مجموعات فرعية تمثيلية للبيانات بكفاءة مع تقليل تكاليف الوقت والذاكرة بشكل كبير، مع الحفاظ على دقة تضاهي أساليب تقريب التدرج الحالية.

المؤلفون الأصليون: Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui

نُشر 2026-08-18

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

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

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

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

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

ملخص تقني: اختيار النواة المركزية (Coreset) بكفاءة عبر رسوم الجيران الأقرب K (KNNG)

بيان المشكلة

يهدف اختيار النواة المركزية (Coreset selection) إلى تقليل التكاليف الحسابية وتكاليف الذاكرة لتدريب نماذج تعلم الآلة من خلال استبدال مجموعة تدريب كبيرة بمجموعة فرعية صغيرة وممثلة. يركز البحث على اختيار النواة المركزية القائم على تقريب التدرج (GA). في هذا الإطار، الهدف هو اختيار مجموعة فرعية $C$ بحجم $M$ من مجموعة تدريب $T$ بحيث يتم تقريب تدرجات المجموعة الكاملة بشكل جيد بواسطة المجموعة الفرعية. تُختزل هذه المشكلة رياضياً في تقليل خطأ التمثيل في فضاء الميزات (المعادلة 1)، حيث يتم تمثيل كل نقطة بيانات بواسطة أقرب جار لها في النواة المركزية المختارة.

تعتمد الطرق الحالية القائمة على تقريب التدرج (GA)، مثل CRAIG و FastCore، على استراتيجيات اختيار جشعة (greedy). ومع ذلك، فإنها تواجه مشكلات كبيرة في القابلية للتوسع:

CRAIG: يقوم بحساب مسبق لمصفوفة مسافات ثنائية كثيفة، مما يتطلب مساحة $O(n^2)$ ووقت $O(n^2d)$ ، وهو أمر يصبح تعجيزياً في مجموعات البيانات الكبيرة.
FastCore: يستبدل المسافات بين العناصر والمسافات بين العناصر والمجموعات (clusters) بحدود عليا لتوفير المساحة، لكنه غالباً ما يتطلب عدداً هائلاً من المجموعات (مئات إلى عشرات الآلاف) للحفاظ على الدقة، مما يؤدي إلى عبء حسابي وتخزيني كبير لمصفوفات الحدود الضخمة.

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

المنهجية: KNNG-CS

يقترح البحث KNNG-CS، وهو طريقة خفيفة الوزن لاختيار النواة المركزية تعتمد على رسم بياني للجيران الأقرب K (KNNG). تعمل الطريقة عبر ثلاث مراحل رئيسية:

1. بناء تقريبي لـ KNNG

بدلاً من حساب جميع المسافات الثنائية، تبني الطريقة رسم بياني تقريبي للـ KNNG $G=(V, E)$ فوق متجهات الميزات. يتصل كل عقدة $x_i$ بجيرانه الـ $K$ الأقرب.

الكفاءة: باستخدام طرق تقريبية حديثة (مثل KGraph)، تبلغ وقت البناء $O(n^{1.14}d)، وتكون التعقيد في المساحة خطياً$ O(nK) $، حيث$ K$ ثابت صغير (تم ضبطه على 10 في التجارب). وهذا يتجنب متطلبات المساحة التربيعية للمصفوفات الكثيفة.

2. تسجيل العقد المدرك للمسافة

الابتكار الأساسي هو دالة تسجيل (scoring function) تُقدر أهمية كل عقدة (عنصر بيانات) بناءً على هيكل جوارها المحلي داخل الـ KNNG.

الدرجة الداخلة (In-Degree): العقدة ذات الدرجة الداخلة العالية (العديد من العقد تشير إليها كجار قريب) هي مرشح قوي للتمثيل.
إدراك المسافة: الدرجة الداخلة وحدها غير كافية. تدمج الطريقة مسافات الحواف عن طريق تحويلها إلى احتمالات باستخدام دالة softmax (المعادلة 2).
صيغة التسجيل: درجة الأهمية $P_i$ للعقدة $v_i$ هي مجموع احتمالات الـ softmax لجميع الحواف الداخلة (المعادلة 3):
$P_i = \sum_{v_j \in N_{in}^G(v_i)} p_{ji}$
حيث تمثل $p_{ji}$ وزن القرب المعياري من الجار $v_j$ إلى $v_i$ . وهذا يسمح للطريقة بالتمييز بين العقد ذات الدرجات الداخلة المتساوية ولكن بمسافات متفاوتة من جيرانها.

3. الاختيار الجشع مع إزالة التكرار

عملية الاختيار هي خوارزمية جشعة تمر بمرة واحدة (one-pass):

حساب درجة الأهمية $P_i$ لجميع العقد.
اختيار العقدة ذات أعلى درجة وإضافتها إلى النواة المركزية $C$ .
إزالة التكرار: إزالة العقدة المختارة وجميع جيرانها الداخلين (in-neighbors) من الرسم البياني فوراً. المنطق هو أنه إذا تم اختيار عقدة، فإن جيرانها الداخلين (الذين يعتبرونها جاراً قريباً) سيتم تمثيلهم بواسطتها ولا يحتاجون لاختيارهم بأنفسهم.
تكرار العملية حتى يتم اختيار $M$ من العناصر.

يتجنب هذا النهج إعادة حساب الفائدة بشكل متكرر، وهو ما يعد عائقاً رئيسياً في الطرق الجشعة التقليدية.

المساهمات الرئيسية

خوارزمية KNNG-CS: طريقة لاختيار النواة المركزية قائمة على تقريب التدرج (GA) وقابلة للتوسع، تستخدم رسماً بيانياً متفرقاً للجيران الأقرب K لتجنب هياكل المسافات الكثيفة المكلفة.
آلية تسجيل مبتكرة: دالة تسجيل للجيران الداخلين مدركة للمسافة تُقدر التمثيل المحلي مباشرة من الـ KNNG دون الحاجة لتخزين مسافات ثنائية كثيفة.
مكاسب الكفاءة: التحقق التجريبي الذي يظهر أن الطريقة تقلل وقت الاختيار واستخدام الذاكرة بشكل كبير مع الحفاظ على جودة النواة المركزية مقارنة بالطرق الرائدة.

النتائج التجريبية

قيم المؤلفون KNNG-CS على أربع مجموعات بيانات من العالم الحقيقي: CovType، IMDB، Brazil، و Card. وقارنوا طريقتهم بكل من العينات العشوائية (Random sampling)، و CRAIG، و FastCore.

الفعالية (الدقة): حققت KNNG-CS دقة اختبار قابلة للمقارنة مع CRAIG و FastCore، وأفضل بكثير من العينات العشوائية. وبينما أظهر CRAIG دقة أعلى قليلاً في بعض المجموعات (IMDB, Card, Brazil) بسبب استخدامه للمسافات الدقيقة، حافظت KNNG-CS على أداء تنافسي.
الكفاءة (الوقت): أظهرت KNNG-CS تسريعاً كبيراً:
- أسرع بـ 2.3 إلى 41.2 ضعفاً من CRAIG.
- أسرع بـ 2.3 إلى 4.9 ضعفاً من FastCore.
  ويُعزى هذا التسريع إلى بناء الـ KNNG الفعال واستراتيجية الاختيار الجشعة ذات المرة الواحدة التي تتجنب حسابات المصفوفات.
استخدام الذاكرة: قللت KNNG-CS استهلاك ذروة الذاكرة بشكل جذري:
- تطلبت فقط 0.3% إلى 3.4% من ذروة الذاكرة التي استخدمها CRAIG.
- تطلبت فقط 4.1% إلى 7.5% من ذروة الذاكرة التي استخدمها FastCore.
  ويرجع ذلك إلى أن KNNG-CS تخزن فقط $O(nK)$ من الحواف، بينما تخزن المنافسة مصفوفات مسافات $O(n^2)$ أو مصفوفات حدود العناصر والمجموعات الضخمة.
التقارب: كان التدريب على النواة المركزية المختارة يتقارب بشكل أسرع (من حيث عدد التكرارات) من التدريب على مجموعة البيانات الكاملة، حيث وفر حجم النواة $M=0.01n$ توازناً جيداً بين الكفاءة والفعالية.

الأهمية والادعاءات

يزعم البحث أن KNNG-CS تقدم حلاً عملياً لاختيار النواة المركزية واسع النطاق من خلال الانتقال من هياكل المسافات العالمية الكثيفة إلى هياكل الجوار المحلية المتفرقة. ومن خلال الاستفادة من الموضع المحلي المتأصل في فضاءات الميزات، تحقق الطريقة:

تعقيد تخزين خطي ( $O(nK)$ ) مقارنة بالتعقيد التربيعي ( $O(n^2)$ ) للطرق السابقة الرائدة.
تخفيضات كبيرة في كل من تكاليف الوقت والذاكرة دون التضحية بجودة المجموعة الفرعية المختارة.
عملية اختيار خفيفة الوزن تتطلب تمريرة واحدة فقط من الاختيار الجشع بعد بناء الرسم البياني، مما يلغي الحاجة إلى حسابات المسافة المتكررة.

خلص المؤلفون إلى أن هذا النهج يتيح اختيار نواة مركزية فعال لمجموعات البيانات الكبيرة حيث تكون طرق تقريب التدرج التقليدية مكلفة حسابياً أو من حيث الذاكرة.