ملخص تقني: قياس عدم الإنصاف في قواعد البيانات عبر تكميم التبعية تحت الخصوصية التفاضلية

بيان المشكلة

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

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

المنهجية

يقترح المؤلفون إطار عمل رسمي لقياس عدم الإنصاف بناءً على ثلاث ركائز أساسية مستمدة من مقاييس عدم الاتساق ومتطلبات الخصوصية التفاضلية:

1. الإيجابية (Positivity): يجب أن يكون المقياس غير سالب ويساوي صفرًا إذا وفقط إذا استوفت قاعدة البيانات جميع معايير العدالة.
2. الرتابة (Monotonicity): توسيع مجموعة معايير العدالة لا يمكن أن يؤدي إلى تقليل عدم الإنصاف المقاس.
3. القابلية للحساب تحت الخصوصية التفاضلية (DP Computability): يجب أن يكون المقياس قابلًا للحساب بكفاءة ودقة تحت الخصوصية التفاضلية، مع الحفاظ على قابليته للتفسير رغم الضجيج المضاف.

ولتحقيق هذه المعايير، يقدم البحث ثلاثة مقاييس متكاملة قائمة على التبعية الاحتمالية، وإصلاح البيانات، ومساهمة الصفوف (Tuples).

1. المقياس القائم على المعلومات المتبادلة ($U^{TVD}_{MI}$)

تعد المعلومات المتبادلة (Mutual Information - MI) المعيارية مقياسًا شائعًا للتبعية، لكنها غير مناسبة للخصوصية التفاضلية بسبب الحساسية العالية ($O(\log n / n)$) ونطاقها غير المحدود، مما يجعل تفسيرها صعبًا وعرضة للتشوه الشديد بفعل ضجيج "لابلاس" عندما تكون القيم قريبة من الصفر.

• المنهج: يقترح المؤلفون وسيطًا يعتمد على مسافة التباين الكلي (Total Variation Distance - TVD). حيث يعرّفون $U^{TVD}_{MI}$ كضعف مربع مسافة التباين الكلي ($2 \cdot \text{TVD}^2$) بين التوزيع المشترك لسمات الحماية ($P$) والنتائج ($O$) (بشرط السمات المقبولة $A$) وحاصل ضرب هوامش توزيعها.
• الخصائص: هذا الوسيط محدود النطاق ($[0, 2]$)، وحساسيته منخفضة ($16|F|/n$)، ويقترب بشدة من المعلومات المتبادلة من الناحيتين النظرية والعملية، مما يحقق معايير الإيجابية والرتابة.

2. المقياس القائم على إصلاح البيانات ($U^{SAT}_{R}$)

مستوحى من أدبيات إصلاح البيانات، يقيس هذا المقياس الحد الأدنى من تعديلات الصفوف (الإضافة/الحذف) المطلوبة لجعل مجموعة البيانات عادلة.

• المنهج: إيجاد الإصلاح الأمثل عملية صعبة حاسوبيًا (NP-hard). قام المؤلفون بتكييف اختزال من عمل سابق [80] يحول مشكلة الإصلاح إلى مشكلة الاشباع المنطقي الأقصى الموزون (Weighted MaxSAT). يعرّفون $U^{SAT}_{R}$ كتكلفة الإصلاح الأمثل الذي تجده أداة حل (SAT solver).
• الخصائص: يحقق المقياس معايير الإيجابية والرتابة. حساسيته محدودة بـ $2|F|$. ورغم أنه مكلف حاسوبيًا بسبب أداة حل SAT، إلا أنه يلتقط مفهومًا دقيقًا لعدم الإنصاف بناءً على عدم الاتساق الهيكلي في البيانات.

3. مقياس مساهمة أفضل $k$ من الصفوف ($UTC$)

يعمل هذا المقياس على عزل السجلات الأكثر تأثيرًا والتي تساهم في انتهاكات العدالة.

• المنهج: لكل صف، يحسب المؤلفون الفرق الهامشي (Marginal Difference - MD)، والذي يمثل الانحراف عن حالة الاستقلال. يقيس $UTC$ مجموع قيم MD لأفضل $k$ من الصفوف ذات المساهمات الأكبر.
• الخصائص: يوفر هذا المقياس رؤية على مستوى الصفوف. تعتمد حساسيته على $k$ وحجم مجموعة البيانات ($O(k/n)$). كما يوفر قابلية أكبر للتفسير من خلال تحديد السجلات المحددة التي تدفع بالانحياز.

خوارزميات الحفاظ على الخصوصية

لكل مقياس، صمم المؤلفون خوارزميات تحسب المقياس على البيانات الخام ثم تطبق آلية لابلاس (Laplace Mechanism) لضمان تحقيق الخصوصية التفاضلية بمستوى $\epsilon$.

• الخوارزمية 1 ($U^{TVD}_{MI}$): تحسب الاحتمالات التجريبية والتباين الكلي، ثم تضيف ضجيجًا يتناسب مع الحساسية $16|F|/n$. التعقيد: $O(|F|n)$.
• الخوارزمية 2 ($U^{SAT}_{R}$): تنشئ صيغة CNF من الربط الذاتي لقاعدة البيانات، وتحل مشكلة Weighted MaxSAT، ثم تضيف ضجيجًا يتناسب مع الحساسية $2|F|$. التعقيد: $O(|F|(n^4 + SAT))$.
• الخوارزمية 3 ($UTC$): تحسب MD لجميع الصفوف، وترتبها، وتجمع أفضل $k$ منها، ثم تضيف ضجيجًا يتناسب مع الحساسية $7k|F|/n$ (شرطي) أو $3k|F|/n$ (غير شرطي). التعقيد: $O(|F|n \log n)$.

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

1. إطار عمل رسمي: أول عمل يقدم إطار عمل عملي لتكميم عدم الإنصاف في البيانات الخاصة مباشرة على مستوى البيانات، مع تحديد معايير محددة (الإيجابية، الرتابة، القابلية للحساب تحت الخصوصية التفاضلية) لهذه المقاييس.
2. ثلاثة مقاييس مبتكرة:
   • $U^{TVD}_{MI}$: وسيط مناسب للخصوصية التفاضلية للمعلومات المتبادلة باستخدام مسافة التباين الكلي.
   • $U^{SAT}_{R}$: مقياس مستوحى من إصلاح البيانات يتم تقريبه عبر الاختزال إلى Weighted MaxSAT.
   • $UTC$: مقياس مساهمة أفضل $k$ من الصفوف الذي يحدد السجلات الأكثر تأثيرًا في انتهاكات العدالة.
3. الضمانات النظرية: إثباتات رسمية بأن جميع المقاييس تحقق المعايير المقترحة، وتظهر حساسية منخفضة بالنسبة لنطاقها، ويمكن حسابها بخطأ محدود تحت الخصوصية التفاضلية.
4. التحقق التجريبي: تجارب واسعة على خمس مجموعات بيانات من العالم الحقيقي (Adult, IPUMS-CPS, Stackoverflow, Compas, Healthcare) تظهر أن المقاييس تقترب بدقة من نظائرها غير الخاصة، وتحدد الانحياز بفعالية، وتتوسع مع مجموعات البيانات الكبيرة.

النتائج

• الدقة (Faithfulness): تتبع المقاييس المقترحة توجهات نظائرها غير الخاصة ومقاييس عدالة تعلم الآلة القياسية (مثل فجوات التكافؤ الديموغرافي). وتحديدًا، يتبع $U^{TVD}_{MI}$ المعلومات المتبادلة القياسية عن كثب، ويزداد $UTC$ بشكل رتيب مع فجوة التكافؤ الديموغرافي.
• الحساسية تجاه عدم الإنصاف: تكتشف المقاييس مستويات متفاوتة من عدم الإنصاف بشكل صحيح. يظهر $U^{SAT}_{R}$ نموًا قريبًا من الخط المستقيم مع زيادة عدم الإنصاف، بينما يظهر $U^{TVD}_{MI}$ و $UTC$ نموًا لوغاريتميًا.
• القابلية للتوسع (Scalability): الخوارزمية 3 ($UTC$) هي الأسرع عمومًا، تليها الخوارزمية 1 ($U^{TVD}_{MI}$). أما الخوارزمية 2 ($U^{SAT}_{R}$) فهي أبطأ بكثير ($10^2$–$10^3$ مرة) بسبب حلّال MaxSAT، لكنها تظل قيمة لمنظورها الدقيق.
• المقايضة بين الخصوصية والدقة: مع زيادة ميزانية الخصوصية ($\epsilon$)، ينخفض الخطأ النسبي لجميع الخوارزميات. وتعد الخوارزمية 2 الأكثر دقة نظرًا لضخامة قيمها مقارنة بالضجيج المضاف، بينما تعد الخوارما 3 الأقل دقة للمجموعات الصغيرة بسبب الحساسية العالية.
• حالات الاستخدام: تعمل المقاييس كمؤشرات ثقة فعالة قبل الاستعلام، مما يساعد في تفسير نتائج الاستعلام الضوضائية وتحديد مجموعات البيانات التي من المرجح أن يؤثر فيها الانحياز على القرارات اللاحقة.

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

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

يضع المؤلفون عملهم كخطوة تأسيسية نحو التقييم المنهجي للعدالة في البيانات المحمية بالخصوصية. وهم يقرون بالقيود، بما في ذلك الاعتماد على منهجية استدلالية لحل MaxSAT في $U^{SAT}_{R}$ (والتي تحسن القابلية للتوسع ولكن قد تضعف الدقة)، والحاجة إلى اختيار مبدئي للمعامل $k$ في $UTC$، وحقيقة أن المقاييس تعمل على المستوى الترابطي دون مراعاة الهياكل السببية أو انحيازات جمع البيانات.

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