🤖 machine learning

Efficient Banzhaf-Based Data Valuation for $k$ -Nearest Neighbors Classification

تتناول هذه الورقة عدم القابلية للحساب لتقييم البيانات القائم على "بانزهاف" (Banzhaf) لمصنفات الجيران الأقرب $k$ من خلال إثبات أن المشكلة هي مسألة معقدة من فئة \#P-hard، ومن ثم تطوير خوارزميات دقيقة فعالة ذات تعقيدات زمنية شبه متعددة الحدود وخطية، إلى جانب طرق تقدير "مونت كارلو"، لتمكين التقييم العملي والعادل لمساهمة البيانات.

المؤلفون الأصليون: Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis

نُشر 2026-05-21

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis

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

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

في عالم تعلم الآلة، يسمى هذا تقييم البيانات (Data Valuation). الورقة البحثية التي قدمتها تتناول نسخة محددة ومعقدة من هذه المشكلة: وهي معرفة قيمة المكونات عند استخدام طريقة طبخ معينة تسمى k-الجار الأقرب (k-Nearest Neighbors - kNN).

إليك تفصيل عملهم بكلمات بسيطة:

1. المشكلة: العدّ أمر مستحيل

لمعرفة مدى مساهمة كل مكون (نقطة بيانات) بدقة، فإن الطريقة "العادلة" هي تخيل كل التوليفات الممكنة من المكونات التي يمكنك وضعها في القدر، ورؤية كيف سيكون طعم الحساء مع هذا المكون، ثم رؤية كيف سيكون طعمه بدونه.

التشبيه: تخيل أن لديك 1,000 مكون. لكي تكون عادلًا تمامًا، سيتعين عليك تذوق الحساء مع كل مزيج ممكن من تلك المكونات (مع ومع بدون المكون المستهدف).
الواقع: هناك عدد من التوليفات للمكونات أكثر من عدد الذرات في الكون. القيام بهذا الحساب صعب للغاية لدرجة أن علماء الكمبيوتر يسمونه #P-hard. إنه يشبه محاولة عد كل حبة رمل على الشاطئ عن طريق التقاطها واحدة تلو الأخرى. سيستغرق الأمر وقتًا أطول من عمر الكون.

2. الحل: اختصار ذكي

أدرك المؤلفون أن k-الجار الأقرب (kNN) هو نوع خاص من "الحساء". في kNN، يعتمد طعم الحساء فقط على المكونات الأقرب القليلة (الجيران الأقرب)، وليس على القدر بأكمله.

الاستعارة: إذا كنت تقرر ماذا ترتدي بناءً على الطقس، فأنت تهتم فقط بدرجة الحرارة والرياح الآن. لست بحاجة لمعرفة حالة الطقس قبل ثلاثة أيام أو على بعد ثلاثة أميال. "المكونات البعيدة" لا تهم.
الاختراق: نظرًا لأن kNN يهتم فقط بالجيران "الأقرب"، فقد بنى المؤلفون خوارزمية البرمجة الديناميكية (Dynamic Programming). فكر في هذا كآلة حاسبة ذكية لا تتذوق كل توليفات الحساء، بل تبني "خريطة وصفة" تسمح لها بحساب قيمة كل مكون فورًا من خلال النظر في كيفية تغير "الجيران الأقرب".

لقد ابتكروا ثلاث نسخ من هذه الآلة الحاسبة الذكية:

لـ kNN الموزون (Weighted kNN): طريقة سريعة تتعامل مع المكونات ذات "القوى" المختلفة (الأوزان).
لـ kNN غير الموزون (Unweighted kNN): طريقة أسرع حتى، حيث تعامل جميع المكونات كمتساوية. هذه الطريقة فعالة للغاية لدرجة أنها تتوسع بشكل خطي تقريبًا، مما يعني أنها تستطيع التعامل مع مجموعات بيانات ضخمة (الملايين من المكونات) التي قد تؤدي إلى تعطل الطرق الأخرى.
تقدير مونت كارلو (Monte Carlo Estimation): إذا كانت مجموعة البيانات ضخمة جدًا حتى بالنسبة لآلتهم الحاسبة الذكية، فإنهم يقدمون طريقة "أخذ عينات". بدلًا من تذوق كل كمية الحساء، تتذوق بضع دفعات عشوائية وتخمن المتوسط. إنها ليست مثالية، لكنها سريعة جدًا.

3. لماذا بانزهاف؟ (تشبيه "قوة التصويت")

تركز الورقة على صيغة رياضية تسمى قيمة بانزهاف (Banzhaf value).

التشبيه: تخيل لجنة تصوت على قرار ما. قيمة شابلي (Shapley value) (وهي طريقة شائعة أخرى) تشبه عدّ عدد المرات التي يكون فيها الشخص هو "صوت الترجيح" في كل تشكيلة ممكنة من اللجنة، مما يعطي وزنًا إضافيًا للمجموعات الصغيرة والضخمة على حد سواء.
الفرق في بانزهاف: طريقة بانزهاف أبسط. فهي تسأل فقط: "في كم سيناريو يغير صوت هذا الشخص النتيجة فعليًا؟"
لماذا يهم هذا: وجد المؤلفون أن بانزهاف غالبًا ما تكون أكثر تشتتًا (sparser) وأكثر قوة (robust).
- التشتت (Sparsity): تعطي قيمة صفرًا للمكونات التي لا تهم حقًا، مما يجعل من السهل تحديد "نجوم" العرض.
- القوة (Robustness): إذا تسلل شخص ما بوضع الكثير من المكونات السيئة والعشوائية (الضوضاء)، فإن طريقة بانزهاف تتجاهلها تمامًا. أما طريقة شابلي فقد ترتبك وتعطي تلك المكونات السيئة قدرًا ضئيلاً من الائتمان، مما يفسد الحساب بأكمله.

4. ما الذي اختبروه (إثبات من الواقع)

لم يكتفِ المؤلفون بالقيام بالرياضيات على الورق؛ بل اختبروا "آلاتهم الحاسبة الذكية" على بيانات حقيقية (مثل التعرف على الأرقام المكتوبة بخط اليد أو اكتشاف الاحتيال في بطاقات الائتمان).

السرعة: كانت خوارزمياتهم الجديدة أسرع بآلاف المرات من طرق "القوة الغاشمة" (brute force) القديمة. تمكنوا من التعامل مع مجموعات بيانات تحتوي على مئات الآلاف من النقاط في ساعات، بينما قد تستغرق الطرق الأخرى أيامًا أو تفشل تمامًا.
تنظيف البيانات: أظهروا أن طريقتهم ممتازة في العثور على "التفاح الفاسد". إذا قمت بإزالة نقاط البيانات التي تقول طريقتهم إنها "الأقل قيمة"، فإن أداء النموذج ينخفض بشكل حاد. وهذا يثبت أنهم حددوا البيانات المهمة بشكل صحيح.
إيجاد الأخطاء: اختبروا ما إذا كانت الطريقة قادرة على إيجاد البيانات ذات التصنيفات الخاطئة (على سبيل المثال، صورة قطة مصنفة ككلب).
- الناعم مقابل الصلب (Soft vs. Hard): وجدوا أن الطرق "الناعمة" (التي تنظر إلى الاحتمالات) أفضل في العث find الأخطاء العشوائية. ومع ذلك، فإن طريقة بانزهاف "الصلبة" الخاصة بهم أفضل في العثور على الأخطاء الحرجة — تلك الأخطاء المحددة في البيانات التي تسحب أداء النموذج للأسفل أكثر من غيرها.

الملخص

تحل هذه الورقة مشكلة سرعة هائلة. لقد حولت مهمة مستحيلة رياضيًا (تقييم كل نقطة بيانات في نموذج kNN بشكل عادل) إلى أداة عملية وسريعة.

الطريقة القديمة: حاول عد كل حبة رمل (بطيئة جدًا، ومستحيلة).
الطريقة الجديدة: استخدم خريطة لعد الحبات التي تلمس المسار فقط (سريعة، ودقيقة).

لق لقد أثبتوا أنه بالنسبة لنماذج kNN، لست بحاجة لتذوق كل تركيبات الحساء في الكون لتعرف أي مكون هو الأكثر أهمية. أنت فقط بحاجة للنظر في الجيران.

ملخص تقني: تقييم البيانات بكفاءة بناءً على قيمة بانزهاف لتصنيف أقرب $k$ جار ( $k$ -Nearest Neighbors)

بيان المشكلة

يعد تقييم البيانات، وهو مهمة تحديد مساهمة النقاط الفردية في أداء النموذج، تحديًا جوهريًا في تعلم الآلة. وبينما توفر النهج القائمة على نظرية الألعاب مثل "قيمة بانزهاف" (Banzhaf value) أطرًا مبدئية للتقييم العادل، إلا أنها تعاني من تعقيد حسابي أسي. وتحديدًا، يتطلب حساب قيم بانزهاف الدقيقة تقييم دالة القيمة عبر جميع المجموعات الفرعية الممكنة لمجموعة البيانات، وهي مهمة ثبت أنها تنتمي لتعقيد #P-hard بشكل عام. هذا العبء الحسابي يجعل الحساب الدقيق غير ممكن لمجموعات البيانات الواقعية التي تحتوي على آلاف أو ملايين العينات، مما يجبر معظم الأعمال الحالية على الاعتماد على طرق تقريبية تضحي بالدقة مقابل الكفاءة.

تتناول هذه الورقة التحدي المحدد المتمثل في حساب قيم بانزهاف الدقيقة لمصنفات أقرب $k$ جار ( $k$ NN). يهدف المؤلفون إلى سد الفجوة بين الأسس النظرية لنظرية الألعاب التعاونية والمتطلبات العملية لتعلم الآلة في العالم الحقيقي من خلال تطوير خوارزميات تستغل خصائص المحلية الفريدة لـ $k$ NN لتحقيق تحسينات حسابية كبيرة دون اللجو-ء إلى التقريب.

المنهجية

تقترح الورقة مجموعة من خوارزميات البرمجة الديناميكية (DP) المصممة خصيصًا لإطار تصنيف $k$ NN، جنبًا إلى جنب مع طرق تقدير مونت كارلو الفعالة.

1. الصعوبة النظرية

يحدد المؤلفون أولاً الصعوبة النظرية للمشكلة. فقد أثبتوا أن حساب قيم بانزهاف لنموذج تصنيف $k$ NN هو مسألة #P-hard. وقد تم إثبات ذلك عبر اختزال من مشكلة "لعبة الأغلبية الموزونة" (Weighted-Majority-Game - WMG)، وهي مشكلة كلاسيكية من نوع #P-hard في نظرية الألعاب التعاونية. تعني هذه النتيجة أنه، في ظل الافتراضات القياسية للتعقيد، لا توجد خوارزمية ذات تعقيد زمني حدودي قوي للحالة العامة.

2. أطر البرمجة الديناميكية

رغم نتيجة الصعوبة، يستفيد المؤلفون من خاصية المحلية لـ $k$ NN (حيث تؤثر أقرب $k$ جيران فقط على التنبؤ) لتطوير خوارزميات دقيقة ذات تعقيدات زمنية محسنة.

البرمجة الديناميكية القياسية لـ $k$ NN الموزون:
يقدم المؤلفون في البداية خوارزمية برمجة ديناميكية بتعقيد زمني قدره $O(W n^4)$ ، حيث $n$ هو عدد نقاط البيانات و $W$ هو الحد الأقص️ لمجموع أعلى $k$ أوزان. يحدد هذا النهج دالة حالة $f_i(w, s, m)$ تمثل عدد المجموعات الفرعية ذات الحجم $s$ مع مجموع وزن $w$ ونقطة محددة هي رقم $m$ في الترتيب من حيث القرب.
البرمجة الديناميكية المحسنة لـ $k$ NN الموزون:
لتقليل التعقيد، قدم المؤلفون تقنيات مبتكرة:
- الحساب المسبق للجمع الجزئي: في حالة كان حجم المجموعة الفرعية $s \le k$ ، يقومون بحساب المجاميع الجزئية مسبقًا لتسريع علاقة التكرار، مما يقلل من المساهمة التعقيدية لهذا الحد.
- تكرار المعامل الثنائي: في حالة $s > k$ ، يستغلون علاقات التكرار للمعاملات الثنائية لحساب مجموع الحالات بكفاءة.
- النتيجة: تحقق هذه التحسينات خوارزمية بتعقيد زمني قدره $O(W k n^2)$ .
البرمجة الديناميكية المتخصصة لـ $k$ NN غير الموزون:
بالنسبة للحالة غير الموزونة (حيث تكون جميع الأوزان 1)، يقترح المؤلفون خوارزمية متخصصة تحقق تعقيدًا قدره $O(n k^2)$ .
- إعادة تصميم فضاء الحالة: يقللون من فضاء الحالة عبر إلغاء الحاجة لتتبع الهوية المحددة للنقطة رقم $m$ في الترتيب.
- التجميع الأمامي والخلفي: يستخدمون دوال أمامية ( $f_i$ ) وخلفية ( $b_i$ )، بالإضافة إلى دوال خلفية بإشارة ( $b^+_i, b^-_i$ ) للتعامل مع إشارات العلامات (labels).
- النتيجة: بما أن $k$ عادة ما يكون ثابتًا صغيرًا، فإن هذه الخوارزمية تعمل في وقت قريب من الخطي بالنسبة لعدد نقاط البيانات.

3. تقدير مونت كارلو

إدراكًا منهم أن التعقيد التربيعي قد يكون عائقًا أمام مجموعات البيانات الضخمة، تقدم الورقة طريقتين فعالتين تعتمدان على أخذ العينات:

أخذ العينات القائم على التحالف (Coalition-based Sampling): يتم تحسينه عبر الاحتفاظ فقط بأعلى $k+1$ لاعب في قائمة مرتبة، مما يقلل التعقيد إلى $O(m n \log k)$ لـ $m$ من العينات.
أخذ العينات القائم على التبديل (Permutation-based Sampling): يكيف صياغة التبديل لقيم بانزهاف عبر مخطط إعادة وزن، محققًا أيضًا تعقيد $O(m n \log k)$ .

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

إثبات الصعوبة: تثبت الورقة أن حساب قيم بانزهاف لمصنفات $k$ NN هو مسألة #P-hard.
أول برمجة ديناميكية دقيقة لـ $k$ NN الموزون: تقدم أول خوارزمية برمجة ديناميكية لحساب قيم بانزهاف الدقيقة في مصنفات $k$ NN الموزونة بتعقيد زمني شبه حدودي.
خوارزمية موزونة محسنة: تحسن التعقيد الزمني للخوارزمية الموزونة بشكل كبير إلى $O(W k n^2)$ من خلال تقنيات خوارزمية مبتكرة تتضمن المجاميع الجزئية وتكرارات المعاملات الثنائية.
خوارزمية غير موزونة ذات وقت قريب من الخطي: تقدم خوارزمية متخصصة لـ $k$ NN غير الموزون بتعقيد $O(n k^2)$ ، وهي أول خوارزمية ذات وقت قريب من الخطي لحساب القيم القائمة على نظرية الألعاب لـ $k$ NN ذي العلامات الصلبة (hard-label).
تقدير مونت كارلو الفعال: توفر طرق مونت كارلو المحسنة القائمة على التحالف والتبديل التي تستغل محلية $k$ NN للتقدير التقريبي السريع.

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

أجرى المؤلفون تجارب واسعة النطاق على 12 مجموعة بيانات واقعية (تتراوح من 5,404 إلى 1,000,000 نقطة بيانات) وبيانات اصطناعية.

الكفاءة الحسابية:
- فشلت الخوارزمية القائمة على البحث الشامل (brute-force) في الاكتمال خلال 10 ساعات لمجموعات بيانات صغيرة تصل إلى 30 نقطة.
- أظهرت خوارزمية البرمجة الديناميكية غير الموزونة (bv-uw) توسعًا خطيًا تقريبًا، حيث تعاملت مع مجموعات بيانات تصل إلى $10^6$ نقطة ضمن الميزانية الزمنية.
- توسعت الخوارزمية الموزونة المحسنة (bv-fast) حتى $10^4$ نقطة، متفوقة على خطوط الأساس لـ Shapley ذات العلامات الصلبة (sv, sv-uw) التي لم تستطع إكمال عمليات التشغيل لـ $n \ge 10^4$ .
- وفرت طرق مونت كارلو تسريعًا يصل إلى 25 ضعفًا مقارنة بالبرمجة الدينامية الموزونة عند قبول انحراف قدره 0.02 تقريبًا.
التطبيقات العملية:
- إزالة النقاط: أدت إزالة نقاط البيانات ذات قيم بانزهاف الأعلى إلى انخفاض أكثر حدة في دقة النموذج مقارنة بالطرق الأخرى (مثل LOO أو دوال التأثير/Influence Functions)، مما يشير إلى أن هذه النقاط كانت حاسمة للأداء.
- اختيار البيانات: أدى اختيار النقاط ذات القيم الأعلى تدريجيًا إلى تحسين دقة النموذج بشكل أسرع من الاختيار العشوائي أو غيره من الخطوط المرجعية.
- كشف سوء التصنيف: سلطت الدراسة الضوء على المقايضة بين أنواع التقييم. كانت قيم Shapley ذات العلامات الناعمة (soft-label) أفضل في اكتشاف العلامات المقلوبة عشوائيًا (درجة $F_1$ عالية). ومع ذلك، كانت قيم بانزهاف ذات العلامات الصلبة (hard-label) متفوقة في تحديد النقاط منخفضة الجودة الحاسمة التي يؤدي تصحيحها إلى تحسين أداء النموذج بشكل كبير. كانت قيم العلامات الصلبة أكثر قوة تجاه الضوضاء وأفضل ملاءمة لتنظيف البيانات حيث يكون الهدف هو إصلاح النقاط التي تغير التنبؤات فعليًا.

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

تدعي الورقة أنها توفر أسرع الخوارخزميات لتقييم بانزهاف للعلامات الصلبة في $k$ NN، متجاوزة حتى كفاءة نظيراتها من قيم Shapley ذات العلامات الصلبة. تكمن الأهمية في جعل التقييم الدقيق للبيانات القائم على نظرية الألعاب أمرًا ممكنًا حسابيًا لمجموعات البيانات واسعة النطاق، وهي مهمة كانت تقتصر سابقًا على التقريب.

يؤكد المؤلفون أنه بينما لا تحقق قيمة بانزهاف بديهية الكفاءة (أي أن مجموع القيم يساوي القيمة الإجمالية) دون تطبيع (normalization)، إلا أنها تقدم مزايا عملية متميزة:

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

تخلص الورقة إلى أنه بينما لا يمتد الإطار مباشرة إلى انحدار $k$ NN (regression) بسبب مصطلحات التطبيع غير القابلة للتفكيك، فإنه ينجح في سد الفجوة بين نظرية الألعاب التعاونية وتطبيقات تعلم الآلة العملية لمهام التصنيف.