تحليل دقيق لتقريبات مصفوفة النواة ذات الرتبة المنخفضة

نconsider المشاكل التعليمية الخاضعة للإشراف ضمن إطار النواة الموجبة المحددة، مثل انهيار النواة والانحدار اللوجستي للنواة أو آلة دعم المتجهات. مع النوى التي تؤدي إلى فضاءات ميزات غير محدودة الأبعاد، تكون الصعوبة العملية الشائعة هي ضرورة حساب مصفوفة النواة، مما يؤدي في كثير من الأحيان إلى خوارزميات تستغرق وقتًا على الأقل تربيعي في عدد الملاحظات n، أي O(n²). وغالبًا ما تعتبر التقريبات ذات الرتبة المنخفضة لمصفوفة النواة كوسيلة لتقليل تعقيدات وقت التشغيل إلى O(p² n)، حيث p هو رتبة التقريب. تعتمد عملية مثل هذه الأساليب بالتالي على الرتبة المطلوبة p. في هذه الورقة، نظهر أنه في سياق انهيار النواة، بالنسبة للتقريبات القائمة على مجموعة عشوائية من أعمدة مصفوفة النواة الأصلية، يمكن اختيار الرتبة p لتكون خطية في درجات الحرية المرتبطة بالمشكلة، وهي كمية تُستخدم تقليديًا في التحليل الإحصائي مثل هذه الأساليب، وغالبًا ما يُنظر إليها كعدد ضمني من المعلمات للمقدرات غير المعلمية. تمكّن هذه النتيجة الخوارزميات البسيطة التي تتمتع بتعقيد وقت تشغيل أقل من التربيع، لكن تُظهر بنفس القدر أداءً تنبؤيًا مشابهًا للخوارزميات الحالية، لأي مثيل مشكلة محدد، وليس فقط للمواقف الأسوأ.