ملخص تقني: LAPLEX – تحويل فوريه السريع (FFT) لنواة لابلاتس القابلة للتعلم

1. بيان المشكلة

تعمل أنظمة تعلم الآلة الحديثة بشكل متزايد في أطر تصل فيها الأبعاد المحيطة إلى ملايين أو مليارات. في هذه الإعدادات عالية الأبعاد، غالبًا ما تكون العقبة هي تكلفة وقت التنفيذ (wall-clock cost) وبصمة الذاكرة للعمليات الخطية، مثل تطبيق المصفوفات الكثيفة، وحساب مؤثرات جرام (Gram operators)، وخلط الميزات.

تضحي النهج الحالية لتوسيع الجبر الخطي بإحدى الخصائص الثلاث المرغوبة: الدقة (exactness)، أو القابلية للتعلم (learnability)، أو التوسع شبه الخطي (near-linear scaling).

• طرق الرتبة المنخفضة (Low-rank methods) (مثل LoRA) تحتفظ بتفاعلات كثيفة تعتمد على الأساس، لكنها تعاني من بصمة ذاكرة قدرها $O(nk)$ لأنها يجب أن تخزن معاملات لأساس المدخلات، حتى لو كانت رتبة المخرجات مضغوطة.
• النماذج العشوائية (Randomized sketches and random features) (مثل CountSketch وRandom Fourier Features) توفر القابلية للتوسع ولكنها تعمل على فهرسة ثابتة أو تقرب النواة، مضحيةً بالدقة مقابل الكفاءة. وهي لا تستطيع تكييف كيفية مطابقة الإحداثيات.
• الطرق المتفرقة (Sparse methods) يمكن أن تكسر الانتظام العتادي (hardware regularity) ويصعب تدريبها من البداية إلى النهاية (end-to-end).
• التحويلات السريعة الكلاسيكية (Classical fast transforms) (مثل FFT) هي دقيقة ورخيصة ($O(n \log n)$) ولكنها ثابتة على هندسة شبكة محددة ولا يمكنها تعلم نظام الإحداثيات.

تتمثل المشكلة الجوهرية المحددة في الاعتماد على الأساس (basis-dependence): تقوم المؤثرات القياسية بتمثيل قيم المصفوفة مباشرة، مما يتطلب تخزينًا يتناسب مع أبعاد المدخلات. تجادل الورقة بضرورة التحول إلى مؤثرات على مستوى الفهرس (index-level operators) يمكنها تعلم هندسة المدخلات نفسها دون تخزين مصفوفة كثيفة.

2. المنهجية: LAPLEX

يقدم المؤلفون LAPLEX، وهو فئة من المؤثرات الدقيقة والقابلة للتدريب القائمة على نواة لابلاتس (Laplace kernel). يتم تعريف طبقة LAPLEX ضمنيًا بواسطة مراسي إحداثيات (coordinate anchors) قابلة للتعلم بدلاً من أوزان المصفوفة الصريحة.

2.1 المؤثر

اللبنة الأساسية هي مصفوفة نواة لابلاتس المعرفة بمجموعتين من المراسي القابلة للتعلم، $a \in \mathbb{R}^n$ و $b \in \mathbb{R}^k$:
$$\text{LAPLEX}(a, b)_{ij} = \exp(-|a_i - b_j|)$$
في نظام حدّي طبيعي (درجة الحرارة $t \to 0$)، يقوم هذا المؤثر بترميز جميع تبديلات مجموعة الإحداثيات. بإضافة معاملات الطور $\phi, \psi$، يمكن توسيع المؤثر ليصبح:
$$\text{LAPLEX}(a, \phi; b, \psi)_{jk} = \exp(-|a_j - b_k|) \cdot \cos(\phi_j - \psi_k)$$
يسمح هذا للمؤثر بالعمل كمصفوفة كثيفة وقابلة للتدريب مع استخدام $O(n)$ فقط من المعاملات (المراسي).

2.2 جبر المسح الدقيق (Exact Scan Algebra)

المساهمة الخوارزمية الرئيسية هي خوارزمية دقيقة ومتوازية بالكامل بقدر $O(n \log n)$ لضرب المصفوفة في المتجه وحساب ضربات جرام، والتي لا تقوم أبدًا بتجسيد المصفوفة الكثيفة.

• الحالة المتماثلة ($a=b$): بعد فرز المراسي، تتحلل مصفوفة النواة إلى أجزاء مثلثية سفلية وعلوية. يمكن حساب كل جزء عبر مسح مسبق (prefix-scan) ومسح لاحق (suffix-scan). على سبيل المثال، الضرب المثلثي السفلي $y_i = \sum_{j \le i} \exp(a_j - a_i)x_j$ يحقق علاقة تكرارية $y_{i+1} = x_{i+1} + \exp(a_i - a_{i+1})y_i$، والتي يتم تقييمها في $O(n)$ من العمل و $O(\log n)$ من العمق المتوازي.
• الحالة العامة ($a \neq b$): تقوم الخوارزمية بتجميع مساهمات مراسي $b$ في فترات محددة بواسطة مراسي $a$ المرتبة. يتم تلخيص المساهمات المحلية في متجهات $u$ و $v$، والتي يتم نشرها عالميًا باستخدام أداة المسح المتماثل.
• مؤثرات جرام (Gram Operators): يتيح هيكل الترتيب نفسه حساب مصفوفات جرام الموزونة $M = A \text{diag}(D) A^\top$ بدقة في زمن $O(n^2 + k \log n)$، مما يتجنب التكلفة البدائية $O(n^2 k)$. هذا أمر بالغ الأهمية للتحسين من الدرجة الثانية وطرق النواة.

2.3 القدرة التعبيرية والحدود

تثبت الورقة أن LAPLEX هو عائلة مستمرة تتداخل بين فئات المؤثرات المختلفة:

• حد درجة الحرارة الصفرية: عندما تقترب معلمة درجة الحرارة من الصفر، تتقارب النواعة الناعمة إلى مصفوفة توجيه متساوية (equality-routing matrix)، مما يستعيد CountSketch والتبديلات التعسفية.
• الشمولية (Universality): مع القياسات القطرية والتكرار المتفرق، تكون العائلة شاملة لأي مصفوفات كثيفة مستطيلة.
• العلاقة بـ FFT: إذا تم تجميد المراسي على شبكة موحدة، يصبح LAPLEX مصفوفة توبليتز (Toeplitz)، وتتحول الخوارزمية إلى Toeplitz-FFT. إذا تم استبدال النواة بتوسع طيفي محدود، يصبح Random Fourier Features (RFF). يحتفظ LAPLEX بالدقة والقابلية للاشتقاق بالنسبة للمراسي، على عكس RFF التي تعاني من تباين غير محدود في التدرج بسبب كثافة كوشي الطيفية الثقيلة لنواة لابلاتس.

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

1. تحديد الاعتماد على الأساس: توضح الورقة أهمية المؤثرات المدركة للتبديل وعلى مستوى الفهرس كبديل مبدئي لطرق الرتبة المنخفضة، التي لا تستطيع الهروب من بصمة ذاكرة $O(nk)$ لأنها لا تضغط أساس المدخلات.
2. الهندسة القابلة للتعلم: توضح أن مصفوفة نواة لابلاتس تشفر جميع تبديلات الإحداثيات في نظام حدي طبيعي باستخدام $O(n)$ فقط من المعاملات.
3. خوارزميات دقيقة وقابلة للتوسع: يقدم المؤلفون خوارزمية دقيقة ومتوازية بالكامل بقدر $O(n \log n)$ لضرب المصفوفة في المتجه وضربات جرام باستخدام $O(n)$ من الذاكرة. هذا يسمح بأبعاد تصل إلى $10^9$ على وحدات معالجة الرسومات الحديثة دون تجسيد المصفوفة.
4. التحقق التجريبي: تظهر الورقة أن LAPLEX يطابق مقياس فئة FFT بينما يعمل بكفاءة كمكون مهيكل جاهز للاستخدام. إنه يتفوق على النماذج الكثيفة في الذاكرة والسرعة، ويتفوق على نماذج الرتبة المنخفضة والميزات العشوائية في الدقة واستقرار التدرج.

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

4.1 التوسع والأداء

• توسع GPU: على NVIDIA H100 وRTX 2080، يتوسع LAPLEX بسلاسة حتى $n = 2^{20}$ (حوالي مليون عنصر)، بينما تنفد ذاكرة النماذج الكثيفة (OOM) عند $n = 2^{14}$.
• السرعة: عند أكبر حجم يمكن لكلتا الطريقتين تشغيله ($n = 2^{14}$)، يكون LAPLEX أسرع بـ $\sim 65\times$ في التمرير الأمامي وحوالي $\sim 430\times$ أسرع في التمرير الأمامي + الخلفي مقارنة بضرب المصفوفات الكثيف (dense matmul).
• الذاكرة: يستخدم LAPLEX ذاكرة ذروة أقل بنحو $\sim 100\times$ من النموذج الكثيف المرجعي.
• الدقة العددية: رغم العمل بدقة float32، يظهر LAPLEX خطأ نسبيًا أقل ضد مرجع float64 مقارنة بكل من dense float32 matmul وToeplitz-FFT. ويعزى ذلك إلى قدرة خوارزمية المسح على إبقاء عوامل القياس الأسية منفصلة عن المانتيسا (mantissas)، مما يتجنب تراكم الخطأ $O(n \epsilon)$ الموجود في الجمع الكثيف.

4.2 نمذجة الكثافة عالية الأبعاد

قام المؤلفون بتدريب نموذج كثافة غاوسية على صور DIV2K مسطحة (بُعد $3 \cdot 10^6$) باستخدام مؤثر جرام دقيق.

• الإعداد: قارن عامل LAPLEX (رتبة 1000، $\sim 14$ مليون معامل) مقابل نموذج كثيف منخفض الرتبة (رتبة 4، $\sim 15$ مليون معامل).
• النتيجة: انهار النموذج الكثيف إلى ضوضاء موحدة بسبب عدم كفاية الرتبة. تعلم نموذج LAPLEX هياكل لونية مكانية متماسكة (مناطق متصلة، ظلال) رغم العمل على متجهات مسطحة بدون انحياز تلافيفي (convolutional bias). كان لوغاريتم الاحتمالية للاختبار أعلى بـ $4.5\times$ من النموذج الكثيف.

4.3 الإسقاطات المهيكلة والتصنيف

• إسقاطات ImageNet10: في إعداد إسقاط مجمد (صور مسطحة بأبعاد $150,528$إلى$m \in {25, \dots, 1000}$)، كان LAPLEX أكثر استقرارًا من CountSketch والإسقاطات العشوائية، وأصبح الأفضل أداءً عند قيم $m$ الكبيرة.
• الرؤوس القابلة للتدريب: عند استخدامه كرأس تصنيف لـ Swin-T وMaxViT-T، طابق LAPLEX أو تجاوز دقة الإسقاطات الكثيفة غير المقيدة عند نفس بُعد المخرجات، باستخدام $\Theta(m+d)$ من المعاملات بدلاً من $\Theta(md)$. عند الرتب المنخفضة، تفوق LAPLEX بشكل كبير على التفكيك منخفض الرتبة (أسلوب LoRA).

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

تدعي الورقة أن LAPLEX يفصل بين القدرة التعبيرية وتكلفة التخزين. فهو يعمل مثل مصفوفة كثيفة قابلة للتدريب ولكن يتم تمثيلها وتطبيقها من خلال مجموعة صغيرة مهيكلة من المعاملات (المراسي).

• الفصل بين القدرة التعبيرية والتخزين: يمكن تعلم الهندسة الكثيفة دون الحاجة لتخزين مصفوفة كثيفة. هذا يتيح تفاعلات عالمية متكيفة مع البيانات في الأطر التي تكون فيها الطبقات الكثيفة العادية غير ممكنة.
• الدقة مقابل التقريب: على عكس ميزات فورييه العشوائية (RFF) أو طرق Nyström، يوفر LAPLEX تطبيق نواة وحساب جرام دقيقًا. وهو يتجنب مقايضات القيمة/التدرج في الميزات العشوائية، وخاصًة التباين غير المحدود في تدرجات المراسي الناتج عن كثافة كوشي الطيفية.
• التحويلات السريعة القابلة للتعلم: تثبت هذه العمل أن التحويلات السريعة لا يجب أن تعيش في أنظمة إحداثيات ثابتة. من خلال تمثيل مؤثر كثيف عبر مراسي لابلاتس قابلة للتعلم، تصبح الهندسة نفسها معلمة قابلة للاشتقاق.

6. القيود

يقر المؤلفون بالقيود التالية:

• الأبعاد: يستخدم البناء الحالي مراسي لابلاتس أحادية البعد وخوارزميات تعتمد على الفرز. إن توسيع هذه الدقة إلى هندسات مراسي متعددة الأبعاد ونوى أغنى هو اتجاه رياضي مفتوح.
• نضج الأنظمة: يوضح التنفيذ الإطار الخوارزمي، ولكن كتل الانتباه (attention blocks) واسعة النطاق، والمحسنات، والنماذج التوليدية ستتطلب نوى متخصصة وتصميم معماري دقيق.
• النطاق: تقتصر الطريقة حاليًا على نواة لابلاتس وتفكيكها المحدد القائم على المسح (scan-based decomposition).

باختصار، يقدم LAPLEX بديلًا مبدئيًا لطرق الرتبة المنخفضة والطرق العشوائية، مما يتيح جبرًا خطيًا دقيقًا، وقابلاً للتعلم، وقابلاً للتوسع في الأطر عالية الأبعاد عبر الانتقال من تمثيل المصفوفات إلى تمثيل تفاعلات الفهرس.