Differential Privacy for Markov Chain State Trajectories
تقدم هذه الورقة إطار عمل للخصوصية التفاضلية عبر الإنترنت لمسارات حالات سلاسل ماركوف، والذي يستفيد من الرسوم البيانية الموجهة والموزونة ومسافات المسار الأقصر لتوليد مسارات خاصة تحافظ على فائدة عالية من خلال محاكاة البيانات الحساسة عن كثب مع ضمان الاتساق الإحصائي مع سلسلة ماركوف الأساسية.
المؤلفون الأصليون:Alexander Benvenuti, Matthew Hale
تخيل أنك تحاول الاحتفاظ بمذكرات سرية لمغامراتك اليومية، لكنك بحاجة إلى مشاركة القصة مع صديق آلي مفيد يرغب في التعلم من عاداتك. المشكلة هي أنه إذا أخبرت الروبوت بالضبط أين ذهبت، أو ماذا اشتريت، أو مع من تحدثت، فقد يكتشف أعمق أسرارك. هذا هو جوهر مجال يسمى الخصوصية التفاضلية (Differential Privacy). فكر في الأمر كأنه "آلة ضوضاء" سحرية تضيف قدرًا كافيًا من التشويش إلى الإشارة بحيث يتم طمس قصة شخص معين، بينما تظل النمط العام للحشد واضحًا. الأمر يشبه قولك لصديق: "ذهبت إلى المنتزه"، بدلًا من قول "ذهبت إلى المنتزه في الساعة الثالثة مساءً وجلست على المقعد الأزرق"، ليعرف صديقك أنك تحب المنتزهات دون أن يعرف مكانك بالضبط.
ولجعل هذا الأمر يعمل مع الأشياء التي تتغير بمرور الوقت، غالبًا ما يستخدم العلماء سلاسل ماركوف (Markov chains). تخيل لعبة لوحية حيث تعتمد خطوتك التالية فقط على مكان وجودك الآن، وليس على كيفية وصولك إلى هناك. إذا كنت في "المنزل"، فقد ترمي نردًا لتقرر ما إذا كنت ستذهب إلى "المدرسة"، أو "العمل"، أو "النادي الرياضي". هذه السلاسل رائعة لنمذجة كل شيء، من الازدحام المروري إلى كيفية تغير درجات الائتمان. ولكن هنا تكمن العقبة: إذا شاركت مسارك الكامل عبر هذه اللعبة اللوحية، فقد يتمكن شخص ما من إعادة بناء حياتك بالكامل بمجرد النظر إلى تسلسل المربعات التي هبطت عليها. لذا، فإن السؤال الكبير الذي يواجه العلماء هو: كيف نشارك هذه المسارات بحيث تظل البيانات مفيدة، ولكن يظل مسارك المحدد لغزًا؟
تقدم هذه الورقة البحثية طريقة جديدة وذكية للعب هذه اللعبة. يقترح المؤلفان، ألكسندر بنفينوتو وماثيو هيل، نظامًا ينشئ نسخة "مزيفة" ولكن واقعية لمسارك في الوقت الفعلي، تمامًا أثناء حركتك. وبدلاً من مجرد إضافة ضوضاء عشوائية أو اتخاذ مسار عشوائي تمامًا (مما يؤدي غالبًا إلى مسارات سخيفة أو مستحيلة)، تستخدم طريقتهم قواعد اللعبة نفسها لتوجيه المسار المزيف. إنهم يعاملون اللعبة اللوحية كخريطة حيث لا تُقاس "المسافة" بين المربعات بالخطوات، بل بمدى احتمالية قفزك بينها. فإذا كان الانتقال من "المنزل" إلى "المدرسة" أمرًا شائعًا جدًا، فإن المسافة تكون قصيرة؛ وإذا كان الانتقال من "المنزل" إلى "القمر" مستحيلاً، فإن المسافة تكون لانهائية.
عندما يحتاج النظام إلى اختيار الخطوة المزيفة التالية، فإنه ينظر إلى الخطوة الحقيقية التالية التي اتخذتها ويحاول اختيار خطوة مزيفة تكون "قريبة" في هذه المسافة الخاصة. إنه يستخدم خدعة ذكية تشبه رمي العملة المعدنية (بناءً على طريقة تسمى "التبديل والقلب" - permute-and-flip) لتقرير الخطوة المزيفة التي سيتخذها. والنتيجة هي مسار خاص يبدو ويشعر تمامًا مثل المسار الحقيقي الذي تولده اللعبة، رغم أنه ليس المسار الدقيق الذي اتخذته. لقد أثبت المؤلفان رياضيًا أن هذا المسار المزيف يظل قريبًا من المسار الحقيقي معظم الوقت ولا يتوه إلى مناطق مستحيلة. وفي اختباراتهم، التي تضمنت محاكاة تغيرات درجات الائتمان، وحركة المرور في المدن، وتصفح الإنترنت، كانت طريقتهم الجديدة أفضل بكثير من أفضل الأساليب الحالية. فقد أنتجت مسارات مزيفة كانت أقل فوضوية بنسبة تصل إلى 80% (مقاسة بالاعتلاج أو الإنتروبي) مقارنة بالمحاولات السابقة، مما يعني أن القصص المزيفة كانت أكثر إقناعًا بكثير. كما وجدوا أن احتمال ارتكاب خطأ فادح وواضح كان أقل بما يصل إلى 10,000 مرة (انخفاض بمقدار 4 مراتب عشرية) مما كان عليه من قبل. وهذا يعني أنه يمكننا مشاركة آثارنا الرقمية للمساعدة في بناء أنظمة أفضل دون ترك مساراتنا الفعلية مكشوفة.
ملخص تقني: الخصوصية التفاضلية لمسارات حالات سلاسل ماركوف
بيان المشكلة تعتمد الأنظمة القائمة على البيانات بشكل متكرر على مسارات الحالات الناتجة عن سلاسل ماركوف لنمذجة السلوكيات مثل هجرة مخاطر الائتمان، وأنماط حركة المرور في المدن، وتصفح الإنترنت. وبينما تعد هذه المسارات مفيدة، فإن مشاركتها تنطوي على مخاطر خصوصية كبيرة، حيث يمكن استخدام التسلسلات القصيرة غالباً لإعادة بناء هويات المستخدمين. وتتعامل الطرق الحالية لخصخصة مسارات سلاسل ماركوف مع السلسلة كآلة ذات حالات منتهية غير حتمية، حيث تختار حالات خاصة عبر مسارات عشوائية منتظمة تتجاهل احتمالات الانتقال. هذا النهج غالباً ما يولد مسارات "غير نمطية" تفتقر إلى الخصائص الهيكلية لسلسلة ماركوف الأساسية، مما يؤدي إلى تدهور فائدة البيانات المخصخصة للتحليلات اللاحقة. علاوة على ذلك، غالباً ما تعمل الأبحاث السابقة على خصخصة المسارات بشكل غير متصل (offline)، أو تفشل في الاستفلاً من ديناميكيات الانتقال المحددة للحفاظ على التشابه الهيكلي.
المنهجية يقترح المؤلفون إطار عمل جديد لتوليد مسارات حالات لـ ϵ-خصوصية تفاضلية بشكل متصل (online)، مما يعني أن المسار الخاص يتم توليده بالتزامن مع المسار الحساس. ويتضمن جوهر المنهجية التعامل مع سلسلة ماركوف كرسم بياني موجه وموزون حيث تكون أوزان الحواف هي اللوغاريتمات السالبة لاحتمالات الانتقال (Wij=−log(Pij)).
الاستقراء الرسومي والمسافة: يحدد المؤلفون مسافة أقصر مسار G(i,j) على هذا الرسم البياني. يثبت الاقتراح 1 أن أقصر مسار في هذا الرسم البياني يتوافق مع المسار الأكثر احتمالاً بين حالتين في سلسلة ماركوف.
تعريف التجاور: تم تقديم مفهوم جديد لتجاور المسارات (التعريف 4). تُعتبر المسارات متجاورة إذا كان مجموع مسافات أقصر مسار المتماثلة بين حالاتها المقابلة محدوداً بمعلمة ρ. يختلف هذا عن العمل السابق الذي يعتمد على مسافة هامينج (عد العناصر المختلفة)، مما يسمح بتعريف أكثر دقة للتشابه بناءً على احتمالية الانتقالات.
تصميم الآلية (الآلية 1): تولد الآلية المقترحة الحالات الخاصة بشكل متصل باستخدام استراتيجية مستوحاة من آلية "التبديل والقلب" (permute-and-flip). في كل خطوة زمنية t، وبالنظر إلى الحالة السابقة الخاصة st−1′ والحالة الحساسة الحالية st، تختار الآلية الحالة الخاصة التالية st′ من الجوار الممكن N(st−1′). يتم تحيز احتمال الاختيار بواسطة دالة المنفعة u(w,w′)=−∑G(st′,st)، والتي تعاقب الحالات البعيدة عن الحالة الحقيقية من حيث مسافة الرسم البياني.
تحليل الانجراف: ينمذج المؤلفون العملية المشتركة للحالات الحساسة والخاصة كنموذج ماركوف خفي. ويستخدمون تحليل انجراف فوستر-ليابونوف (Foster-Lyapunov drift analysis) لإثبات أن المسار الخاص يظهر "انجرافاً سالباً"، مما يعني أنه من المرجح إحصائياً أن يعود إلى جوار المسار الحساس إذا انحرف عنه.
المساهمات الرئيسية يقدم البحث أربع مساهمات رئيسية:
تعريف وآلية خصوصية جديدة: يقدم المؤلفون تعريفاً جديداً للتجاور لمسارات حالات سلاسل ماركوف بناءً على أقصر مسار، ويطورون الآلية 1، وهي آلية ϵ-خصوصية تفاضلية متصلة مصممة خصيصاً لهذا التعريف.
حدود الخطأ: يقدمون حداً للتركيز (النظرية 2) على احتمال انحراف المسار الخاص بشكل كبير عن المسار الحساس، مما يظهر أن الأخطاء الكبيرة تحدث باحتمالية تتناقص أسياً.
النمطية وحدود الإنتروبيا: يضع المؤلفون حداً للإنتروبيا التجريبية المتوقعة للمسارات الخاصة (النظرية 3) ويوفرون حداً للتركيز (النظرية 4) يظهر أن المسارات الخاصة تقع ضمن المجموعة النمطية η لعملية ماركوف الأساسية باحتمالية عالية. وهذا يضمن أن البيانات المخصخصة تحتفظ بالخصائص الإحصائية للعملية الأصلية.
التحقق التجريبي: تم اختبار الآلية على ثلاث مجموعات بيانات من العالم الحقيقي: هجرة الائتمان، وحركة المرور في المدينة (Gainesville, FL)، وحركة مرور الإنترنت (Wikispeedia).
النتائج تظهر المحاكاة العددية أن الآلية 1 تتفوق بشكل كبير على آلية الحالة الراهنة (Chen et al., 2023b) من حيث المنفعة مع الحفاظ على نفس مستوى الخصوصية:
تقليل الإنتروبيا: في ظل خصوصية تفاضلية بمقدار 3، تظهر الآلية 1 انخفاضاً يصل إلى 80% في الإنتروبيا مقارنة بالآلية السابقة الأفضل، مما يشير إلى أن المسارات الخاصة المولدة أقرب بك كثيراً إلى التوزيع الإحصائي الحقيقي لسلسلة ماركوف.
احتمالية الخطأ: تقلل الآلية من احتمال حدوث أخطاء كبيرة (الانحرافات في مسافة أقصر مسار) بما يصل إلى 4 مراتب عشرية مقارنة بالطرق الموجودة. على سبيل المثال، في مثال هجرة الائتمان، انخفض احتمال الخطأ الكبير (v=15) من 0.003 إلى 2×10−7.
التشابه الهيكلي: على عكس الطرق السابقة التي غالباً ما تتحول إلى مسارات عشوائية (مما يزيد الإنتروبيا مع طول المسار)، تحافظ الآلية 1 على مستوى إنتروبيا ثابت بعد طول معين للمسار، مما يحافظ على السلامة الهيكلية للبيانات.
الأهمية يزعم البحث أن إطاره يعالج المقايضة الحرجة بين الخصوصية والمنفعة في بيانات سلاسل ماركوف. ومن خلال الاستفادة من احتمالات الانتقال لتعريف المسافة والتجاور، تضمن الآلية بقاء المسارات المخصخصة "نمطية" ومتشابهة هيكلياً مع البيانات الحساسة. وهذا يسمح للأنظمة اللاحقة باستخدام البيانات المخصخصة بفعالية دون المساس بخصوصية المستخدم. ويؤكد المؤلفون أن نهجهم لا يتطلب شبكات عصبية أو دالات مسافة خاصة بالسياق، مما يجعله قابلاً للتطبيق مباشرة على أي إعداد لسلاسل ماركوف حيث تكون احتمالات الانتقال معروفة. يثبت هذا العمل أنه من الممكن توليد مسارات خاصة متصلة تحترم الديناميكيات الأساسية للنظام، وهو تحسن كبير عن الطرق التي تعامل فضاءات الحالات كمجموعات غير منظمة.