حول النواة المثلى الصحيحة للمهمات وتطبيقاتها في تصنيف الرسوم البيانية

نجاح طرق النواة (kernel methods) قد أدى إلى تصميم دوال جديدة موجبة نصف محددة، وبشكل خاص للبيانات المهيكلة. أحد أهم نماذج التصميم لهذه الأغراض هو نواة التجعيد (convolution kernel)، والتي تقوم بتفكيك الأشياء المهيكلة إلى أجزائها وجمعها على جميع أزواج الأجزاء. ومع ذلك، فإن نوى التعيين (assignment kernels) تُحصل من تعيين أمثل بين الأجزاء، مما يمكن أن يوفر تعريفًا أكثر صحة للتشابه. ومع ذلك، في العادة، يؤدي التعيين الأمثل إلى دوال غير محددة (indefinite functions)، مما يعقد استخدامها في طرق النواة. نحن نحدد فئة من الدوال الأساسية المستخدمة لمقارنة الأجزاء التي تضمن وجود دوال تعيين أمثل موجبة نصف محددة. هذه الدوال الأساسية تولد هرميات يتم حساب نوى التعيين الأمثل منها بوقت خطي عبر تقاطع التوزيعات التكرارية (histogram intersection). نطبق هذه النتائج بتطوير نواة Weisfeiler-Lehman للتعيين الأمثل للرسوم البيانية (graphs). إنها توفر دقة تصنيف عالية على مجموعة بيانات مقاييسية مستخدمة بشكل واسع، مما يحسن من النواة الأصلية Weisfeiler-Lehman.