Inference for Clustering: Conformal Sets for Cluster Labels

إليك ملخص تقني مفصل للورقة البحثية بعنوان "الاستدلال للتجميع: المجموعات المطابقة لملصقات العناقيد" (Inference for Clustering: Conformal Sets for Cluster Labels) من تأليف أنيربان ناث، ويونهاينغ هور، وجينيفيرا ألين.

1. صياغة المشكلة

يُعد التجميع (Clustering) مهمة أساسية في التعلم غير الخاضع للإشراف، ومع ذلك، فإنه يفتقر إلى طرق دقيقة لقياس عدم اليقين في تعيينات العناقيد. وبينما تتناول الأدبيات الحالية عدم اليقين في وجود العناقيد (مثل SigClust) أو مواقع المراكز (Centroids)، لا يوجد إطار عمل واسع النطاق لـ عدم اليقين في ملصقات العناقيد نفسها.

التحدي الجوههري هو أن ملصقات العناقيد هي:

• غير ملاحظة: يتم تقديرها من البيانات بدلاً من كونها معطاة.
• منفصلة ومتماثلة التبديل (Permutation-Invariant): لا يمكن معاملتها ككائنات بارامترية سلسة.
• غير قابلة للتبادل (Non-Exchangeable): يعتمد الاستدلال المطابق (Conformal Inference) القياسي على تبادلية نقاط البيانات. ومع ذلك، عندما يتم تقدير الملصقات من نفس البيانات المستخدمة للمعايرة، يتم انتهاك فرضية التبادلية، مما يؤدي إلى تغطية ناقصة شديدة (حيث يقع الملصق الحقيقي خارج مجموعة الثقة بمعدل أكبر من المعدل الاسمي).

الهدف: بناء مجموعة ثقة $\hat{C}(x) \subseteq \{1, \dots, K\}$ لأي نقطة استعلام $x$ بحيث تحتوي، باحتمال لا يقل عن $1-\alpha$، على ملصق العنقود الحقيقي (والمجهول) $Y^*_{n+1}$، حتى عند تقدير الملصقات بواسطة خوارزمية تجميع عشوائية.

2. المنهجية

يقترح المؤلفون إطار عمل جديد يسمى التجميع المطابق المنقسم مع الملصقات العشوائية (Split Conformal Clustering with Stochastic Labels).

2.1 فشل النهج الساذجة

تحلل الورقة أولاً نهجين ساذجين يفشلان في تقديم ضمانات صالحة:

1. القطع للتجميع الناعم القابل للتعميم (Cutoff for Generalizable Soft Clustering): استخدام الملصقات الناعمة (الاحتمالات اللاحقة) مباشرة واختيار الملصقات حتى يتجاوز الاحتمال التراكمي $1-\alpha$. يفشل هذا لأن الملصقات الناعمة غالباً ما تكون ضعيفة المعايرة، مما يؤدي إما إلى تغطية ناقصة (في العينات الصغيرة) أو تغطية مفرطة غير مفيدة (في المجموعات الكبيرة).
2. التجميع المطابق المنقسم (الحتمي) (Split Conformal Clustering - Deterministic): تقسيم البيانات إلى مجموعة تدريب ومجموعة معايرة، وتجميع كل منهما باستخدام خوارزمية حتمية (مثل K-means)، والتعامل مع الملصقات الصلبة الناتجة كحقائق مطلقة. يفشل هذا لأن الملصقات الحتمية لا تلتقط عدم اليقين المتأصل في عملية التجميع، مما ينتهك شرط التبادلية المطلوب للاستدلال المطابق.

2.2 الخوارزمية المقترحة: التجميع المطابق المنقسم مع الملصقات العشوائية

يقدم النهج المقترح (الخوارزمية 1) العشوائية في عملية التسمية لاستعادة التبادلية والتقاط عدم اليقين.

1. تقسيم البيانات: تقسيم البيانات غير المصنفة $X_1, \dots, X_n$ عشوائياً إلى مجموعة تدريب ($I_{tr}$) ومجموعة معايرة ($I_{ca}$).
2. التسمية العشوائية (التدريب): تطبيق خوارزمية تجميع عشوائية $\gamma$ على بيانات التدريب. بدلاً من تعيين ملصق صلب واحد، تقوم الخوارزمية بأخذ عينات من الملصقات $Y_i$ من توزيع احتمالي (على سبيل المثال، أخذ عينات من التوزيع اللاحق لنموذج الخليط الغاوسي أو طريقة C-means الضبابية).
3. تدريب المصنف الناعم: تدريب مصنف ناعم $\hat{\pi}$ (مثل الغابة العشوائية، أو SVM مع مخرجات احتمالية) على بيانات التدريب $(X_i, Y_i)$ للتنبؤ بمتجهات الاحتمالات لأي مدخل.
4. التسمية العشوائية (المعايرة): تطبيق نفس خوارزمية التجميع العشوائية على بيانات المعايرة للحصول على ملصقات مأخوذة بالعينات $Y_i$ لـ $i \in I_{ca}$.
5. محاذاة الملصقات: بما أن التجميع يتميز بتبادلية الترتيب (Permutation-Invariant)، فقد تختلف الملصقات في مجموعة المعايرة عن مخرجات المصنف بسبب التبديل. يتم إيجاد التبديل الأمثل $\hat{\sigma}$ الذي يقلل من عدم الاتفاق بين تنبؤات المصنف وملصقات المعايرة المأخوذة بالعينات.
6. حساب درجات المطابقة: حساب درجات المطابقة لمجموعة المعايرة باستخدام الملصقات المحاذية والمصنف الناعم.
7. بناء مجموعة الثقة: لأي نقطة جديدة $x$، يتم إنشاء مجموعة الثقة $\hat{C}(x)$ التي تحتوي على جميع الملصقات التي تقع درجات مطابقتها تحت المئين التجريبي لدرجات المعايرة.

3. الضمانات النظرية

تضع الورقة ضمانات للتغطية في العينات المحدودة وفي الحالة التقاربية.

3.1 الحد الأدنى للعينات المحدودة

توفر النظرية 1 حداً أدنى لاحتمال التغطية الهامشية:
$$P(\hat{\sigma}^*_o(Y^*_{n+1}) \in \hat{C}(X_{n+1})) \ge 1 - \alpha - \frac{n}{n+2}E_{n/2}(\gamma) - \frac{n}{2(n+2)}S_{n/2}(\gamma)$$
حيث أن:

• الاتساق (Consistency - $E_n$): يقيس خطأ التقدير بين الملصقات الناعمة التي تنتجها الخوارزمية وتوزيع الملصقات الشرطي الحقيقي.
• استقرار الاستبدال الواحد (Replace-One Stability - $S_n$): يقيس مدى تغير توزيع الملصقات المشترك عند استبدال نقطة بيانات واحدة.

يكشف الحد أن التغطية الناقصة يتم التحكم فيها من خلال الاتساق والاستقرار لخوارزمية التجميع الأساسية. إذا كانت هذه القيم صغيرة، فإن الطريقة تحقق التغطية المستهدفة $1-\alpha$.

3.2 التغطية التقاربية

تظهر النظريتان 2 و3 أنه بالنسبة لـ نماذج الخليط البارامترية (مثل نماذج الخليط الغاوسي GMM) حيث يتم تقدير المعلمات باتساق (على سبيل المثال عبر MLE/EM)، فإن شروط الاتساق والاستقرار تتحقق تقاربياً. وبالتالي، تقترب التغطية من $1-\alpha$ مع زيادة $n \to \infty$.

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

4.1 المحاكاة

اختبر المؤلفون الطريقة على نماذج الخليط الغاوسي (GMM) ونماذج الخليط الغاما (GaMM) في أبعاد منخفضة وعالية.

• التغطية: حققت الطريقة المقترحة (Split CC Stochastic) باستمرار التغطية المستهدفة بنسبة 90% عبر مستويات تباين وأحجام عينات مختلفة.
• المقارنة:
  • التجميع المطابق المنقسم الساذج (الملصقات الصلبة): عانى من تغطية ناقصة شديدة (غالباً أقل من 70%) لأن الملصقات الصلبة تفتقر إلى الاستقرار.
  • طريقة القطع (Cutoff Method): كانت متحفظة للغاية، حيث أنتجت مجموعات ثقة غير مفيدة (مجموعات كبيرة) لفرض التغطية.
• حجم المجموعة: أنتجت الطريقة المقترحة مجموعات ثقة معلوماتية. في المناطق جيدة الفصل، كانت المجموعات مكونة من عنصر واحد فقط؛ وفي مناطق الحدود، احتوت المجموعات على ملصقات متعددة محتملة، مما يعكس عدم اليقين بدقة.

4.2 التطبيق الواقعي: تسلسل الحمض النووي الريبي أحادي الخلية (Single-Cell RNA-seq)

تم تطبيق الطريقة على مجموعة بيانات PBMC-3K لقياس عدم اليقين في تحديد نوع الخلية.

• النتائج:
  • اليقين العالي: شكلت خلايا B وخلايا NK عناقيد ضيقة ومنفصلة جيداً، مما أدى إلى مجموعات ثقة مكونة من عنصر واحد (يقين عالٍ).
  • عدم اليقين العالي: أظهرت الخلايا التائية (CD4/CD8) والخلايا الوحيدة/الخلايا الشجيرية مجموعات ثقة أكبر (الحجم $\ge 2$)، مما يعكس بدقة غموضها البيولوجي وحالاتها النسخية المتداخلة.
• التصور: نجحت الطريقة في تصور مناطق عدم اليقين في فضاء PCA، مما سلط الضوء على الحدود حيث يكون تعيين نوع الخلية غامضاً.

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

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

6. الأهمية

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