A Maximum Entropy Implementation of Differential Privacy Under Linear Invariants

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

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

---

لغز الضجيج المتوازن تماماً

تخيل أنك طاهٍ يحاول خبز كعكة لقاضٍ صعب الإرضاء للغاية. لدى القاضي قاعدتان:

1. قاعدة المذاق: يجب أن يكون لكل قضمة من الكعكة مذاق يشبه نكهة محددة (مثل الفانيليا مثلاً) لضمان اتباع الوصفة.
2. قاعدة الوزن: يجب أن يكون الوزن الإجمالي للكعكة 1,000 جرام بالضبط، لا أكثر ولا أقل.

الآن، تخيل أنك تضيف "مكونات سرية" (ضجيج) إلى الخليط لحماية أصل الوصفة. إذا قمت فقط برش حفنة من حبوب الفانيليا في كل وعاء بشكل عشوائي، فإن الوزن الإجمالي للكعكة سيكون خاطئاً على الأرجح. قد ينتهي بك الأمر بـ 1,005 جرام أو 990 جراماً. وإذا حاولت إصلاح الوزن عن طريق طرح الجرامات الزائدة من الطبقة العليا فقط، فستفسد "قاعدة المذاق" لأن الطبقة العليا ستصبح ذات مذاق مختلف عن بقية الأجزاء.

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

الطريقة القديمة مقابل الطريقة الجديدة

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

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

حل "الإنتروبيا القصوى"

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

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

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

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

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

ما وجدوه وأثبتوه

لم يكتفِ المؤلفان بالتخمين بأن هذا سينجح، بل أثبتا ذلك.

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

لماذا يهم هذا الأمر؟

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

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

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