When One Point Is Not Enough: Addressing Ambiguous Instances in Dimensionality Reduction by Splitting

ملخص تقني: معالجة الحالات الغامضة في تقليل الأبعاد عن طريق التقسيم

تعريف المشكلة
يُعد تقليل الأبعاد (Dimensionality Reduction - DR) أداة أساسية لتصور البيانات عالية الأبعاد، ومع ذلك، فهو عملية تتضمن فقدانًا للمعلومات بطبيعتها. وبينما صنفت الأدبيات الحالية تشوهات متنوعة، مثل تمزق المتشعبات (manifold tearing)، تحدد هذه الورقة مصدرًا لم يسبق ملاحظته للآثار البصرية: الحالات الغامضة (ambiguous instances). وهذه الحالات هي نقاط بيانات تتشابه بشدة مع جيران متعددين متباعدين في الفضاء عالي الأبعاد.

تقوم طرق تقليل الأبعاد القياسية برسم كل حالة بيانات كنقطة واحدة في الفضاء المرئي. وبناءً على ذلك، لا يمكن للحالة الغامضة أن تمثل بصدق عضويتها في عدة جيران متميزين في آن واحد؛ حيث تُجبر على اتخاذ موقع واحد، مما يؤدي إلى تضمين الجوار الجزئي (partial neighborhood embedding). في هذه الحالة، تظهر الحالة وكأنها تنتمي إلى جار واحد فقط (أو لا تنتمي لأحد)، مما يحجب علاقتها الحقيقية بالمجموعات المتميزة الأخرى. ويعد هذا الأثر مشكلة خاصة في التحليلات على مستوى الحالة، مثل الذكاء الاصطناعي القابل للتفسير (XAI) أو علم الأحياء الخلوي، حيث يكون فهم بنية الجوار الدقيقة أمرًا بالغ الأهمية. وتفشل المقاييس الحالية مثل الموثوقية (trustworthiness) والاستمرارية (continuity) في تمييز تضمين الجوار الجزئي عن التشوهات الأخرى لأنها تعمل على التضمين النهائي دون الوصول إلى غموض البيانات الأساسي.

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

1. بناء الرسم البياني وتخفيف الكثافة (Graph Construction and Sparsification):

   • يتم نمذجة العلاقات عالية الأبعاد كرسم بياني غير موجه وموزون $G$.
   • للكشف عن بنى الجوار ذات المعنى وإزالة الحواف الزائدة الناتجة عن التقارب العرضي، يطبق المؤلفون التخفيف الطيفي (spectral sparsification) باستخدام خوارزمية شبيلمان-سبريلمان. ينتج عن ذلك رسم بياني مخفف $\bar{G}$ يحافظ على الخصائص الهيكلية والجبرية للأصل مع إزالة الاتصالات الضعيفة.

2. تحديد الحالات الغامضة:

   • يتم تعريف الغموض طوبولوجيًا. يكيّف المؤلفون مفهوم نقاط التمفصل المحلية (Local Articulation Points - LAPs). تُعتبر الرأس (vertex) نقطة تمفصل محلية إذا أدى حذفها إلى زيادة عدد المكونات المتصلة داخل جوار محلي مستحث بمسافة $r$ خطوة.
   • تُعتبر الحالة غامضة إذا كانت نقطة تمفصل محلية في الرسم البياني المخفف $\bar{G}$. يشير هذا إلى أن الحالة تربط بين جيران منفصلين كان من المفترض أن يكونا متباعدين.
   • تُستخدم اللمة (Lemma) 3.1 لتحسين الحوسبة: إذا لم تكن الرأس نقطة تمفصل محلية عند نصف قطر معين $r$، فلا يمكن أن تكون نقطة تمفصل محلية عند أي نصف قطر أكبر $r' > r$.

3. تقسيم الرؤوس وقواعد القرار:

   • بمجرد تحديد رأس غامض $v_i$، يتم تقسيمه إلى $K$ من النسخ، حيث يتوافق $K$ مع عدد المكونات المتصلة المتبقية بعد حذف $v_i$ من جواره المحلي.
   • قواعد القرار: لا يتم تنفيذ جميع عمليات التقسيم المحتملة. يقوم النهج بتصفية ما يلي:
     • اتصالات (LAP-LAP): إذا كان هناك حافة تربط بين جارين وكان كلا الطرفين عبارة عن نقاط تمفصل محلية، يتم قمع التقسيم لتجنب خلق عزلة اصطناعية.
     • الاتصالات الضعيفة: يقوم عتبة يحددها المستخدم $\tau_w$ (نسبة قوة الاتصال إلى أقوى مكون) بتصفية التقسيمات التي يكون فيها الاتصال بالجوار ضعيفًا جدًا ليكون ذا معنى. هذا يمنع إنشاء نقاط معزولة بصريًا بسبب عدم كفاية قوى الجذب.

4. الخرائط والتصور (Mapping and Visualization):

   • يتم إسقاط الرسم البياني المعدل، الذي يحتوي على الرؤوس المقسمة، في الفضاء المرئي باستخدام تقنيات تقليل الأبعاد المحلية القياسية (مثل UMAP أو ForceAtlas2).
   • الترميز البصري: يتم عرض الحالات المقسمة كعلامات متميزة (مثل علامات X) متصلة بخطوط متقطعة بموقعها الأصلي أو ببعضها البعض، مما يسمح للمحللين بتتبع عضويات الجوار المتعددة لنقطة بيانات واحدة.

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

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

النتائج

• الرؤى النوعية: في مجموعة بيانات SVBTN، أظهر الرقم '1' الذي تم تصنيفه خطأً (على أنه '7') في UMAP القياسي أنه ينتمي حصريًا إلى جوار الـ '7'. أظهر النهج المقترح تقسيم هذه الحالة، مما كشف عن تشابهها المتزامن مع جوار الـ '1'، وبالتالي شرح غموض خطأ المصنف. وبالمثل، في بيانات النصوص، أظهرت ورقة بحثية حول "النماذج المدعومة بالبرمجة الخطية الصحيحة (ILP) لعلم السموم" أنها تنتمي إلى كل من مجموعات ILP والبرمجة القائمة على الحالة (CBR)، وهو ازدواجية حجبتها الإسقاطات القياسية.
• التحليل الكمي:
  • تأثير التخفيف (Sparsification Impact): أظهرت التجارب التي تقيس أقرب الجيران $k$ (kNN) المحفوظة أن التخفيف الطيفي يحتفظ ببنى الجوار المحلية بشكل مشابه للرسم البياني الأصلي (نسب قريبة من 1 لمعظم مجموعات البيانات)، رغم ملاحظة بعض التباين في بيانات الخلية الواحدة ذات الأبعاد الجوهرية العالية.
  • محدودية المقاييس: وُجد أن المقاييس القياسية (الموثوقية والاستمرارية) غير فعالة في تحديد الحالات الغامضة، حيث تتوزع هذه النقاط بشكل مشابه للنقاط غير الغامضة عبر توزيعات المقاييس.
  • حساسية المعلمات: أدى زيادة عدد الجيران في الرسم البياني الأولي عمومًا إلى تقليل عدد عمليات التقسيم المكتشفة، حيث أن زيادة الاتصال تجسر الجيران الذين قد يظهرون كمنفصلين لولا ذلك.

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