Differential Privacy for Markov Chain State Trajectories

तकनीकी सारांश: मार्कोव चेन अवस्था प्रक्षेपवक्रों (State Trajectories) के लिए विभेदक गोपनीयता (Differential Privacy)

समस्या विवरण
डेटा-संचालित प्रणालियाँ अक्सर मार्कोव चेन द्वारा उत्पन्न अवस्था प्रक्षेपवक्रों (state trajectories) पर निर्भर करती हैं, जो क्रेडिट जोखिम प्रवासन (credit risk migration), शहर के यातायात पैटर्न और इंटरनेट ब्राउज़िंग जैसे व्यवहारों को मॉडल करती हैं। हालांकि ये प्रक्षेपवक्र उपयोगी हैं, लेकिन इन्हें साझा करना महत्वपूर्ण गोपनीयता जोखिम पैदा करता है, क्योंकि लघु अनुक्रमों का उपयोग अक्सर उपयोगकर्ता की पहचान को पुनर्गठित करने के लिए किया जा सकता है। मार्कोव चेन प्रक्षेपवक्रों को निजी बनाने वाली मौजूदा विधियाँ अक्सर मार्कोव चेन को एक गैर-नियतात्मक परिमित-अवस्था ऑटोमेटन (non-deterministic finite-state automaton) के रूप में मानती हैं, जो संक्रमण संभावनाओं (transition probabilities) की अनदेखी करते हुए समान वितरण वाले यादृच्छिक वॉक (uniform random walks) के माध्यम से निजी अवस्थाओं का चयन करती हैं। यह दृष्टिकोण अक्सर ऐसे "असामान्य" प्रक्षेपवक्र उत्पन्न करता है जो मूल मार्कोव चेन के संरचनात्मक गुणों की कमी रखते हैं, जिससे डाउनस्ट्रीम विश्लेषण के लिए निजीकृत डेटा की उपयोगिता कम हो जाती है। इसके अलावा, पूर्व कार्य अक्सर प्रक्षेपवक्रों को ऑफलाइन रूप से निजी बनाते हैं या संरचनात्मक समानता बनाए रखने के लिए विशिष्ट संक्रमण गतिकी (transition dynamics) का लाभ उठाने में विफल रहते हैं।

कार्यप्रणाली (Methodology)
लेखक $\epsilon$-विभेदक रूप से निजी अवस्था प्रक्षेपवक्रों को ऑनलाइन उत्पन्न करने के लिए एक नया ढांचा प्रस्तावित करते हैं, जिसका अर्थ है कि निजी प्रक्षेपवक्र संवेदनशील प्रक्षेपव melalui के साथ ही उत्पन्न होता है। इस कार्यप्रणाली के मूल में मार्कोव चेन को एक भारित निर्देशित ग्राफ (weighted directed graph) के रूप में मानना शामिल है जहाँ किनारा भार (edge weights) संक्रमण संभावनाओं के ऋणात्मक लघुगणक हैं ($W_{ij} = -\log(P_{ij})$)।

1. ग्राफ प्रेरण और दूरी (Graph Induction and Distance): लेखक इस ग्राफ पर एक लघुतम पथ दूरी (shortest-path distance) $G(i, j)$ को परिभाषित करते हैं। प्रस्ताव 1 स्थापित करता है कि इस ग्राफ में लघुतम पथ मार्कोव चेन में दो अवस्थाओं के बीच सबसे संभावित पथ के अनुरूप होता है।
2. समीपता परिभाषा (Adjacency Definition): एक नया प्रक्षेपवक्र समीपता (trajectory adjacency) का विचार पेश किया गया है (परिभाषा 4)। दो प्रक्षेपवक्रों को तब समीप माना जाता है यदि उनके संगत अवस्थाओं के बीच सममित लघुतम-पथ दूरियों का योग एक पैरामीटर $\rho$ द्वारा सीमित हो। यह हैमिंग दूरी (Hamming distance - भिन्न प्रविष्टियों की गणना करना) पर आधारित पूर्व कार्य से भिन्न है, जो संक्रमण की संभावना के आधार पर समानता की अधिक सूक्ष्म परिभाषा की अनुमति देता है।
3. तंत्र डिजाइन (Mechanism Design - Mechanism 1): प्रस्तावित तंत्र 'परम्यूट-एंड-फ्लिप' (permute-and-flip) तंत्र से प्रेरित रणनीति का उपयोग करके ऑनलाइन निजी अवस्थाओं को उत्पन्न करता है। प्रत्येक समय चरण $t$ पर, पिछले निजी राज्य $s'_{t-1}$ और वर्तमान संवेदनशील राज्य $s_t$ को देखते हुए, तंत्र अगले निजी राज्य $s'_t$ को उसके व्यवहार्य पड़ोस $N(s'_{t-1})$ से चुनता है। चयन की संभावना उपयोगिता फलन $u(w, w') = -\sum G(s'_t, s_t)$ द्वारा पक्षपाती होती है, जो उन अवस्थाओं को दंडित करती है जो ग्राफ दूरी के संदर्भ में वास्तविक अवस्था से दूर हैं।
4. ड्रिफ्ट विश्लेषण (Drift Analysis): लेखक संवेदनशील और निजी अवस्थाओं की संयुक्त प्रक्रिया को एक हिडन मार्कोव मॉडल (hidden Markov model) के रूप में मॉडल करते हैं। वे यह सिद्ध करने के लिए फोस्टर-लयापुनोव ड्रिफ्ट विश्लेषण (Foster-Lyapunov drift analysis) का उपयोग करते है कि निजी प्रक्षेपवक्र में "ऋणात्मक ड्रिफ्ट" (negative drift) प्रदर्शित होता है, जिसका अर्थ है कि यदि वह संवेदनशील प्रक्षेपवक्र से विचलित होता है, तो सांख्यिकीय रूप से उसके संवेदनशील प्रक्षेपवक्र के पड़ोस में वापस आने की संभावना होती है।

प्रमुख योगदान
यह शोध पत्र चार प्राथमिक योगदान देता है:

• नई गोपनीयता परिभाषा और तंत्र: लेखक लघुतम-पथ दूरियों पर आधारित मार्कोव चेन अवस्था प्रक्षेपवक्रों के लिए समीपता की एक नई परिभाषा पेश करते हैं और 'मैकेनिज्म 1' विकसित करते हैं, जो इस परिभाषा के लिए अनुकूलित एक ऑनलाइन $\epsilon$-विभेदक रूप से निजी तंत्र है।
• त्रुटि सीमाएं (Error Bounds): वे निजी प्रक्षेपवक्र के संवेदनशील प्रक्षेपवक्रम से महत्वपूर्ण रूप से विचलित होने की संभावना पर एक एकाग्रता सीमा (concentration bound - Theorem 2) प्रदान करते हैं, जो यह दर्शाता है कि बड़ी त्रुटियां तेजी से घटती प्रायिकता के साथ होती हैं।
• सामान्यता और एंट्रॉपी सीमाएं (Typicality and Entropy Bounds): लेखक निजी प्रक्षेपवक्रों की अपेक्षित अनुभवजन्य एंट्रॉपी (expected empirical entropy) को सीमित करते हैं (Theorem 3) और एक एकाग्रता सीमा (Theorem 4) प्रदान करते हैं जो यह दर्शाती है कि निजी प्रक्षेपवक्य उच्च संभावना के साथ मूल मार्कोव चेन के $\eta$-टिपिकल सेट (typical set) के भीतर रहते हैं। यह सुनिश्चित करता है कि निजीकृत डेटा मूल प्रक्रिया के सांख्यिकीय गुणों को बनाए रखता है।
• अनुभवजन्य सत्यापन (Empirical Validation): तंत्र का परीक्षण तीन वास्तविक दुनिया के डेटासेट पर किया गया है: क्रेडिट माइग्रेशन, सिटी ट्रैफिक (गेंसविले, FL), और इंटरनेट ट्रैफिक (विकिस्पीडिया)।

परिणाम
संख्यात्मक सिमुलेशन प्रदर्शित करते हैं कि मैकेनिज्म 1 समान गोपनीयता स्तर बनाए रखते हुए उपयोगिता के मामले में अत्याधुनिक तंत्र (चेन एट अल., 2023b) की तुलना में काफी बेहतर प्रदर्शन करता है:

• एंट्रॉपी में कमी: 3-विभेदक गोपनीयता के तहत, मैकेनिज्म 1 पूर्व अत्याधुनिक तंत्र की तुलना में 80% तक कम एंट्रॉपी प्रदर्शित करता है। यह इंगित करता है कि उत्पन्न निजी प्रक्षेपवक्र मार्कोव चेन के वास्तविक सांख्यिकीय वितरण के बहुत करीब हैं।
• त्रुटि प्रायिकता: तंत्र मौजूदा विधियों की तुलना में बड़ी त्रुटियों (लघुतम-पथ दूरी में विचलन) की संभावना को 4 क्रमों (orders of magnitude) तक कम कर देता है। उदाहरण के लिए, क्रेडिट माइग्रेशन उदाहरण में, एक बड़ी त्रुटि ($v=15$) की प्रायिकता 0.003 से गिरकर $2 \times 10^{-7}$ हो गई।
• संरचनात्मक समानता: पूर्व विधियों के विपरीत जो अक्सर यादृच्छिक वॉक में बदल जाती हैं (प्रक्षेपवक्र की लंबाई बढ़ने के साथ एंट्रॉपी बढ़ाती हैं), मैकेनिज्म 1 एक निश्चित प्रक्षेपवक्र लंबाई के बाद स्थिर एंट्रॉपी स्तर बनाए रखता है, जिससे डेटा की संरचनात्मक अखंडता सुरक्षित रहती है।

महत्व
यह शोध पत्र दावा करता है कि इसका ढांचा मार्कोव चेन डेटा के लिए गोपनीयता और उपयोगिता के बीच के महत्वपूर्ण संतुलन को संबोधित करता है। संक्रमण संभावनाओं का उपयोग करके दूरी और समीपता को परिभाषित करके, तंत्र यह सुनिश्चित करता है कि निजीकृत प्रक्षेपवक्र "टिपिकल" बने रहें और संवेदनशील डेटा के साथ संरचनात्मक रूप से समान रहें। यह डाउनलोड सिस्टम को उपयोगकर्ता की गोपनीयता से समझौता किए बिना निजीकृत डेटा का प्रभावी ढंग से उपयोग करने की अनुमति देता है। लेखक इस बात पर जोर देते हैं कि उनके दृष्टिकोण के लिए न्यूरल नेटवर्क या संदर्भ-विशिष्ट दूरी कार्यों की आवश्यकता नहीं है, जिससे यह किसी भी मार्कोव चेन सेटिंग के लिए सीधे लागू करने योग्य बन जाता है जहाँ संक्रमण संभावनाएँ ज्ञात होती हैं। यह कार्य यह स्थापित करता है कि ऐसे ऑनलाइन निजी प्रक्षेपवक्र उत्पन्न करना संभव है जो प्रणाली की अंतर्निहित गतिशीलता का सम्मान करते हैं, जो उन विधियों की तुलना में एक महत्वपूर्ण सुधार है जो अवस्था स्थानों (state spaces) को असंरचित सेटों के रूप में मानती हैं।