Preserving Target Distributions With Differentially Private Count Mechanisms

إليك ملخص تقني مفصل لورقة البحث بعنوان "الحفاظ على توزيعات الأهداف باستخدام آليات العد ذات الخصوصية التفاضلية" (Preserving Target Distributions With Differently Private Count Mechanisms) للباحثين نيتين كوهلي وبول لاسكوسكي.

1. بيان المشكلة

غالباً ما يحتاج حاملو البيانات (مثل مكاتب التعداد أو دوائر الصحة العامة) إلى نشر جداول من الأعداد (مثل عدد الحالات لكل ولاية) مع الحفاظ على خصوصية الأفراد عبر الخصوصية التفاضلية (Differential Privacy - DP). تضيف آليات الخصوصية التفاضلية القياسية (مثل آلية Laplace أو Geometric) ضجيجاً مستقلاً لكل عدد لحماية المدخلات الفردية.

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

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

2. المنهجية: إطار عمل ثنائي المراحل

يقترح المؤلفون إطار عمل مكون من مرحلتين، حيث يتم تقسيم إجمالي ميزانية الخصوصية $\epsilon_t$ إلى $\epsilon_1$ (للتوزيع) و $\epsilon_2$ (للأعداد).

المرحلة الأولى: تخصية التوزيع (Distribution Privatization)

يقوم حامل البيانات أولاً بحساب التوزيع الحقيقي للأعداد $\zeta$ (نسبة الفئات التي تمتلك العدد $i$). ثم يقوم بتخصية هذا التوزيع لإنشاء توزيع مستهدف $z$.

• آلية مبتكرة: يقدم المؤلفون آلية Laplace الدورية (Cyclic Laplace Mechanism).
  • بخلاف ضجيج Laplace الذي يُضاف بشكل مستقل إلى الفئات، تضيف هذه الآلية ضجيجاً مترابطاً: $V_i = \zeta_i + L_i - L_{i+1}$، حيث $L_i$ هي متغيرات Laplace مستقلة و $L_n = L_0$.
  • الفائدة: هذا الهيكل "الدوري" يضمن بقاء المجموع التراكمي للتوزيع مستقراً، مما يقلل بشكل كبير من تباين الأخطاء التراكمية مقارنة بآليات Laplace القياسية. وقد ثبت أنها تحقق $\epsilon$-DP.

المرحلة الثانية: خوارزمية البناء (Constructor Algorithm)

الهدف هو بناء مصفوفة انتقال $T$ (مصفوفة $n \times n$ حيث $T_{i,j}$ هو احتمال إخراج $j$ بمعلومية $i$) بحيث:

1. تحقق المصفوفة $T$ شرط $\epsilon_2$-DP.
2. تمتلك المصفوفة $T$ نقطة ثابتة عند $z$ (أي $zT = z$). وهذا يضمن أنه إذا كانت البيانات المدخلة تتبع التوزيع $z$، فإن البيانات المخرجة ستتبع أيضاً $z$ في التوقع.

لحل هذه المشكلة، طور المؤلفون نظرية رياضية قائمة على مقاييس $\epsilon$ ($\epsilon$-scales):

• مقاييس $\epsilon$: هي متجهات احتمالية حيث يتقيد قيد الخصوصية التفاضلية لكل زوج من المدخلات المتجاورة (إما $s_i = e^\epsilon s_{i+1}$ أو $s_i = e^{-\epsilon} s_{i+1}$).
• تمثيل متعدد الوجوه (Polytope Representation): تشكل مجموعة آليات النقطة الثابتة الصالحة "متعدد وجوه محدب" $F$. يثبت المؤلفون أن أي آلية في $F$ يمكن تمثيلها كمزيج مخروطي من مقاييس $\epsilon$.
• متعدد وجوه التمثيل ($R_F$): يقومون برسم خرائط لفضاء عالي الأبعاد لمصفوفات الانتقال إلى فضاء تمثيل منخفض الأبعاد باستخدام مصفوفة مقياس $\Psi$. وهذا يسمح بتوصيف النقاط القصوى للمجموعة المتاحة.
• الخوارزميات:
  • البناء الأمثل (للقيم الصغيرة لـ $n$): يستخدم البرمجة الخطية القياسية (Simplex/Interior Point) لتقليل خطأ العدد (مثل متوسط مربع الخطأ MSE) ضمن متعدد وجوه النقطة الثابتة $F$.
  • البناء الاستدلالي (للقيم الكبيرة لـ $n$): خوارزمية جشعة (Algorithm 1) تعمل بزمن $O(n^2)$ تقوم ببناء مصفوفة الانتقال عبر إضافة "مقاييس $\epsilon$ أحادية الذروة" بشكل تكراري. وهي تختار الأعمدة لتعبئتها بناءً على دالة اختيار $\kappa$ (مثل "Sandwich" أو "Max Probability") لضمان تلبية قيد النقطة الثابتة بكفاءة.

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

1. آلية Laplace الدورية: تخصية توزيع جديدة مصممة خصيصاً لتوزيعات الأعداد تتفوق على آليات الهيستوغرام العامة (مثل الطرق الهرمية أو الموجية) في الحفاظ على دقة التوزيع.
2. النظرية الرياضية لآليات النقطة الثابتة:
   • تعريف مفهوم مقاييس $\epsilon$ ككتل أساسية لآليات عد الخصوصية التفاضلية.
   • توصيف النقاط القصوى لمتعدد وجوه النقطة الثابتة $F$ باستخدام متعدد وجوه التمثيل $R_F$.
   • إثبات أن النقاط القصوى لـ $F$ يمكن تمثيلها بعدد صغير نسبياً من مقاييس $\epsilon$، مما يتيح بناء خوارزميات فعالة.
3. خوارزميات بناء فعالة:
   • تطوير بناء استدلالي (Algorithm 1) يعمل بزمن $O(n^2)$، مما يجعله عملياً للقيم الكبيرة لـ $n$ حيث تفشل البرمجة الخطية القياسية.
   • تطوير بناء "الأمثل غير المثبت" ثنائي المرحلة (Algorithm 2) للمقارنة المرجعية، والذي يجد الآلية المثلى دون قيد النقطة الثابتة.
4. التحقق التجريبي: تجارب شاملة توضح المقايضات بين معايير الأداء الثلاثة.

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

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

• دقة التوزيع:
  • تفوقت طرق النقطة الثابتة بشكل كبير على جميع النماذج المرجعية غير المثبتة.
  • مثال: في مجموعة بيانات Binomial مع $\epsilon_t = 0.48$، أدى الانتقال من أفضل نموذج مرجعي غير مثبت إلى طريقة النقطة الثابتة إلى تقليل مسافة Wasserstein بنسبة 94% (من 0.64 إلى 0.04).
• دقة الأعداد:
  • فرض قيد النقطة الثابتة يؤدي إلى تدهور طفيف في دقة الأعداد مقارنة بالنماذج المرجعية غير المثبتة (التي تمتلك فضاءً متاحاً أكبر).
  • ومع ذلك، فإن هذا التدهور متوسط (غالباً بضع نقاط مئوية). على سبيل المثال، في بيانات الجريمة، زاد خطأ العدد بنسبة 5.7% فقط بينما انخفض خطأ التوزيع بنسبة 74%.
• وقت التشغيل:
  • تصبح حلول البرمجة الخطية القياسية (Simplex/Interior Point) غير عملية للقيم الكبيرة لـ $n$.
  • حقق البناء الاستدلالي المقترح أوقات تشغيل مقاربة لأسرع النماذج المرجعية غير المثبتة (مثل Truncated Geometric)، حيث عالج $n=2000$ في أقل من 10 ثوانٍ.
• تخصيص الميزانية:
  • يقدم المؤلفون "قاعدة عامة" لتقسيم ميزانية الخصوصية ($f = \epsilon_1 / \epsilon_t$) بناءً على الميزانية الإجمالية، حيث يظهر أنه كلما انخفضت $\epsilon_t$، يجب تخصيص جزء أكبر لتخصية التوزيع.

5. الأهمية

تعالج هذه الورقة فجوة حرجة في الخصوصية التفاضلية: الحفاظ على الخصائص الإحصائية العالمية (التوزيعات) جنباً إلى جنب مع الخصائص المحلية (الأعداد الفردية).

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