Coupled Optimal Transport with Landmark Constraints

ملخص تقني: النقل الأمثل المقترن بقيود المعالم (Landmark Constraints)

بيان المشكلة
تسعى نماذج النقل الأمثل (Optimal Transport - OT) الحالية بشكل أساسي إلى إيجاد خريطة نقل أو خطة نقل تقلل من تكلفة النقل أو التشويه المحدد بين توزيعين احتماليين. وبين أن هذه النماذج فعالة في مطابقة التوزيعات، إلا أن تقليل التكلفة وحدها غالبًا ما يفشل في تحديد التحويلات ذات المعنى الهندسي. على سبيل المثال، في تسجيل الصور أو الأشكال، قد تقوم الخريطة المدفوعة بالتكلفة بنقل الكتلة عبر مسارات قصيرة هندسيًا ولكنها غير صحيحة دلاليًا (مثل مطابقة أجزاء تشريحية مختلفة). ومن ناحية أخرى، فإن الطرق التي تعتمد فقط على معالم (landmarks) موسومة شحيحة تفشل غالبًا في التقاط الانتقال التوزيعي العالمي أو حقل التشوه الذي يحكم التغيير. تعالج هذه الورقة تحدي استعادة حقل تشوه متماسك يلبي كلاً من المحاذاة التوزيعية العالمية والقيود الهندسية المحلية المقدمة من معالم شحيحة.

المنهجية
يقترح المؤلفون إطار عمل جديد لـ النقل الأمثل المقترن (Coupled Optimal Transport - COT) يوحد بين تحسين خطة النقل وتقدير حقل التشوه.

• صياغة النموذج: يقدم إطار العمل رؤية قائمة على التشوه للنقل. لتكن $u: \Omega \to \mathbb{R}^p$ حقل تشوه و $T_u = \text{Id} + u$ خريطة النقل المرتبطة به. بمعلومية مجموعة من أزواج المعالم الموسومة $S = \{(x_i, y_i)\}_{i=1}^m$، يقلل النموذج الدالي $F(\pi, u)$ عبر مجموعة الاقترانات $\Pi(\mu, \nu)$ وفضاء سوبوليف (Sobolev space) لحقول التشوه $U$:
  $$\inf_{\pi \in \Pi(\mu, \nu), u \in U} F(\pi, u)$$
  يتكون الدالي من ثلاثة مكونات رئيسية:

1. تكلفة النقل المقترنة: مزيج مرجح من تكلفة النقل الكلاسيكية $c(x, y)$ وعقوبة اتساق التشوه $h(T_u(x) - y)$. يضمن هذا المصطلح أن خطة النقل $\pi$ متسقة مع حقل التشوه $u$.
2. الإشراف بالمعالم: حد $\sum w_i \rho(A_i^r(u) - \Delta_i^{lm})$ يعاقب التباين بين إزاحات المعالم المرصودة والمتوسط المحلي لحقل التشوه (عبر مؤثر ملاحظة $A_i^r$).
3. التنظيم (Regularization): حد طاقة مرنة $E_{el}(u)$ (طاقة مرنة خطية) لتعزيز التماسك المكاني ونعومة حقل التشوه، مما يسهل انتشار معلومات المعالم الشحيحة عبر النطاق.

• الخصائص النظرية:

  • جودة الصياغة (Well-posedness): يثبت المؤلفون وجود مُقلل $(\pi^\star, u^\star)$ تحت شروط ملائمة (مثل الاستمرارية المطلقة لـ $\mu$، وتماسك الطاقة المرنة).
  • السلوك الحدّي: يتم تحليل النموذج عندما $\alpha \to 1$ (هيمنة التشوه) وعندما $\alpha \to 0$ (هيمنة التكلفة). عندما $\alpha \to 0$، يستعيد النموذج مشكلة منفصلة حيث تقلل خطة النقل التكلفة، ويقلل التشوه فقدان المعالم بشكل مستقل، مع عمل حد الاقتران كمعيار اختيار بين المُقللات المنفصلة.
  • الفرضية 2.1: تحت تكلفة إقليدية مربعة، يُظهر أن المشكلة المقترنة مكافئة لتقليل دالي يتضمن مسافة واسرستاين (Wasserstein distance) بين المقياس المستهدف وصورة المقياس المصدر عبر خريطة تشوه مخففة، بالإضافة إلى حدود التنظيم.

• الخوارزمية العددية:

  • التقطيع (Discretization): يستخدم المؤلفون طريقة العناصر المحدودة (FEM) لحقل التشوه باستخدام عناصر $Q_1$ ذات التنسور المستمر. يتم تقطيع المقاييس كمقاييس ذرية موزونة.
  • التكرار المتناوب: يتم حساب الحل عبر مخطط متناوب:
    1. تحديث النقل: بتثبيت $u$، يتم تحديث خطة النقل باستخدام تكرار شبيه بـ Sinkhorn مع تنظيم من نوع إنتروبي أو بريغمان (KL-divergence) للتعامل مع قيود الهوامش.
    2. تحديث التشوه: بتثبيت $\pi$، يتم تحديث معاملات التشوه عن طريق حل نظام خطي مشتق من شروط الأمثلية من الدرجة الأولى (نظرًا للاختيارات التربيعية لـ $h$ و $\rho$).
  • التقارب: يثبت التحليل النظري أن تسلسل التكرارات محدود، وأن قيمة الهدف تتناقص رتيبًا، وأن الفروق بين التكرارات المتتالية تتلاشى. بالنسبة للنسخة المنظمة بالإنتروبي، يُظهر التسلسل تقاربًا نحو نقطة حرجة مقيدة.

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

1. إطار عمل مبتكر: اقتراح نموذج نقل أمثل مقترن موحد يدمج تحسين خطة النقل وتقدير حقل التشوه، مما يجسّر الفجوة بين التسجيل القائم على المعالم ومطابقة التوزيع القائم على النقل.
2. الأساس النظري: إرساء صلاحية النموذج في سياق متغير عام وتوصيف علاقته بالنقل الكلاسيكي من خلال التحليل الحدّي.
3. التطوير الخوارزمي: تطوير خوارزمية عددية قائمة على العناصر المحدودة مع تحليل تقارب منهجي، بما في ذلك متغيرات KL-proximal والنسخ المنظمة بالإنتروبي.
4. الإشراف الشحيح: إثبات القدرة على استعادة حقول تشوه كثيفة وذات معنى هندسي من إشراف معالم شحيحة مدمج مع مطابقة التوزيع العالمي.

النتائج التجريبية
تم التحقق من فعالية الطريقة المقترحة من خلال نوعين من التجارب:

1. التجارب الاصطناعية: باستخدام توزيعات على شكل سمكة مع حقول تشوه معروفة (Ground-truth).
   • المقاييس: خطأ التشوه ($L_2$)، خطأ المعالم المحجوزة، وخطأ الكثافة ($L_1$).
   • النتائج: تفوقت طريقة COT (سواء نسخة KL-proximal أو النسخة الإنتروبية) باستمرار على "OT (barycentric)" (التي تفتقر إلى قيود المعالم) و "Landmark-only" (التي تفتقر إلى قيود التوزيع العالمي)، لا سيما في نظام المعالم الشحيحة. نجحت الطريقة في استعادة التشوه الحقيقي بخطأ أقل مع زيادة عدد المعالم. كما لوحظ تقارب دالة الهدف والتكرارات، بما يتماشى مع التوقعات النظرية.
2. مطابقة الأشكال الحقيقية: طُبقت على صور الأرقام المكتوبة بخط اليد (MNIST) مع معالم محددة يدويًا.
   • النتائج: مقارنة بالنماذج المرجعية، أنتجت COT حقول تشوه متماسكة مكانيًا ومتسقة مع مراسلات المعالم المحددة. بينما التقطت "OT (barycentric)" التوزيع العالمي ولكنها أنتجت حقولًا غير منتظمة، وأنتجت "Landmark-only" حقولًا ناعمة فقط بالقرب من المعالم، نجحت COT في نشر كل من المعلومات التوزيعية والمعلومات الخاصة بالمعالم عبر كامل دعم المصدر.

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

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