Linear-cost Polyharmonic Spline Interpolation of Arbitrary Degree

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

لحل هذه المشكلة، يستخدم العلماء غالباً أداة تسمى "الشرائح متعددة التوافقيات" (polyharmonic spline). فكر في هذا كأنه ورقة مطاطية سحرية ومرنة تقوم بتثبيتها عند نقاط البيانات المعروفة لديك. تستقر الورقة بشكل طبيعي لتأخذ شكلاً يربط بين جميع النقاط بسلاسة. المشكلة تكمن في أن حساب كيفية انحناء هذه الورقة المطاطية بدقة يتطلب حل شبكة ضخمة ومتشابكة من المعادلات. عادةً ما يتطلب هذا قوة حوسبة كبيرة لدرجة أنها تشبه محاولة عد كل حبة رمل على الشاطئ يدوياً. ومع ذلك، هناك خدعتان ذكيتان في صندوق أدوات العلماء لتسريع ذلك. الأولى هي "طريقة المجموعات المتعددة السريعة" (Fast Multipole Method - FMM)، وهي طريقة فعالة للغاية لتجميع الأصدقاء البعيدين معاً حتى لا تضطر للتحدث إلى كل شخص على حدب وصوب لإرسال رسالة. الثانية هي "تقريب فيكيا" (Vecchia approximation)، وهي طريقة لتخمين الإجابة من خلال النظر فقط إلى جيرانك الأقرب، بافتراض أن الأشخاص البعيدين لا يؤثرون عليك كثيراً.

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

سحر الورقة المطاطية الممتدة

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

المشكلة هي أن جدول البيانات هذا "كثيف"، مما يعني أن كل خلية تحتوي على رقم. إذا كان لديك 1,000 نقطة، فلديك مليون خلية لحسابها. إذا كان لديك مليون نقطة، فلديك تريليون تريليون خلية. الحواسيب التقليدية ستحتاج إلى عمل مكعب ($O(n^3)$) لحل هذه المشكلة، وهذا هو السبب في أنها عادة ما تكون مستحيلة لمجموعات البيانات الضخمة.

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

طريقة المجموعات المتعددة السريعة: تجميع الحشود

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

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

الممهد: تسخين المحرك

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

يقترح المؤلفون ممهداً جديداً وسريعاً للغاية يعتمد على "تقريب فيكيا". تفترض هذه الطريقة أن النقطة تتأثر بشكل أساسي بجيرانها الأقرب، وليس بالنقاط الموجودة في الجانب الآخر من العالم. باستخدام نموذج إحصائي يسمى "تباين ماتيرن" (Matérn covariance) (الذي يصف كيف تتلاشى الأشياء بمرور المسافة)، يمكنهم بناء مصفوفة متفرقة (sparse matrix)—وهي جدول بيانات معظم خلاياه أصفار. هذه المصفوفة المتفرقة سهلة الحساب وتعمل كمرحلة إحماء مثالية للمحلل.

وجد المؤلفون أن هذا المزيج المحدد يعمل بشكل رائع. في اختباراتهم، استقر برنامج الحل (وهو طريقة تسمى "Conjugate Gradient الممهد") في أقل من 15 تكراراً، حتى مع مجموعات البيانات التي تزيد عن مليون نقطة. هذا يعني أن السيارة لم تكتفِ بتسلق التلة فحسب، بل طارت فوقها.

النتائج: السرعة تلتقي بالدقة

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

كما اختبروا الدقة. في إحدى التجارب، حاولوا التنبؤ بدالة معقدة تحتوي على موجات ناعمة ونتوء حاد ومسنن. أنتجت الطريقة الجديدة أخطاءً مطابقة تقريباً للطريقة "المثالية" (البطيئة)، مما يثبت أن الاختصارات لم تضحِّ بالجودة.

ولعل العرض الأكثر إثارة للإعجاب كان اختباراً واقعياً باستخدام بيانات درجة حرارة سطح البحر في المحيط الهادئ. كان لديهم حوالي 58,000 قياس مع وجود بعض الفجوات بسبب "الغطاء السحابي" (المحاكي للفجوات). باستخدام طريقتهم، ملأوا البيانات المفقودة في 5 ثوانٍ فقط مع معدل خطأ منخفض جداً. في المق المقابل، استغرقت طريقة تقليدية تستخدم نفس النموذج الإحصائي أكثر من 400 ثانية وكان أداؤها أسوأ في الواقع. وهذا يسلط الضوء على ميزة رئيسية لنهجهم: نظرًا لأن "الشرائح متعددة التوافقيات" مستقلة عن المقياس (scale-invariant)، فهي لا تحتاج إلى ضبط أو تعديل لأحجام مختلفة من البيانات، مما يجعلها حلاً جاهزاً للاستخدام مباشرة.

لماذا هذا مهم؟

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

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