Differential Privacy Mechanisms

সেনসিটিভিটি জানলেই কি হলো?

আগের অধ্যায়ে আমরা একটা প্রশ্নের উত্তর দিয়েছিলাম: একটা কোয়েরিতে একজন মানুষের ডেটা সর্বোচ্চ কতটুকু প্রভাব ফেলতে পারে? এই সংখ্যাটাই সেনসিটিভিটি।

কিন্তু এটা জানলেই কাজ হয় না। জানতে হবে — ঠিক কী ধরনের নয়েজ যোগ করলে সেই পরিবর্তনটা লুকানো যাবে, এবং কতটুকু যোগ করতে হবে।

এই অধ্যায়ে সেটাই শেখা হবে। চারটা মূল মেকানিজম — Laplace, Gaussian, Exponential, আর Randomized Response — প্রতিটা আলাদা পরিস্থিতির জন্য এই প্রশ্নের উত্তর দেয়। শুধু সূত্র মুখস্থ করা না, বরং কেন প্রতিটা কাজ করে, কখন কোনটা বেছে নেব, সেটা বোঝাটাই মূল লক্ষ্য।

Laplace মেকানিজম

মূল ধারণা

Laplace মেকানিজম হলো সংখ্যাত্মক কোয়েরিকে প্রাইভেট করার সবচেয়ে স্বাভাবিক উপায়। ধারণাটা আসলে সহজ: কোয়েরির আউটপুটে Laplace বিতরণ থেকে নেওয়া নয়েজ যোগ করো। নয়েজের পরিমাণ ঠিক হয় কোয়েরির L1 সেনসিটিভিটি আর প্রাইভেসি বাজেট $\varepsilon$ দিয়ে।

Laplace বিতরণ কী?

মেকানিজমের আগে বিতরণটা চেনা দরকার। শূন্যে কেন্দ্রিত, স্কেল $b$-এর Laplace বিতরণের probability density হলো:

$$\text{Lap}(x \mid b) = \frac{1}{2b} \exp\!\left(-\frac{|x|}{b}\right)$$

এটা প্রতিসম — শূন্যের কাছে সবচেয়ে বেশি probability, দুদিকে exponentially কমে। Gaussian-এর তুলনায় লেজ একটু ভারী — মানে বড় মানের সম্ভাবনা একটু বেশি। variance হলো $2b^2$।

মেকানিজম

$f: \mathcal{D} \to \mathbb{R}^k$ ফাংশনের L1 সেনসিটিভিটি $\Delta_1 f$ হলে, Laplace মেকানিজম আউটপুট দেয়:

$$\mathcal{M}(D) = f(D) + (Z_1, \ldots, Z_k), \quad Z_i \overset{\text{i.i.d.}}{\sim} \text{Lap}\!\left(\frac{\Delta_1 f}{\varepsilon}\right)$$

প্রতিটা আউটপুট কোঅর্ডিনেটে আলাদাভাবে Laplace নয়েজ যোগ হয়, স্কেল $\Delta_1 f / \varepsilon$।

কেন কাজ করে? DP গ্যারান্টি দিতে হলে যেকোনো neighboring database $D, D'$-এর জন্য আউটপুটের probability ratio $e^\varepsilon$-এর মধ্যে থাকতে হবে। Laplace density-র exponential decay ঠিক $\Delta_1 f$ পরিমাণ shift-কে শুষে নেয় — worst case-এ ratio হয় ঠিক $e^\varepsilon$। এটাই pure $\varepsilon$-DP।

একটা বাস্তব উদাহরণ

ধরো একটা হাসপাতালে রোগীদের গড় বয়স প্রকাশ করতে চাও। বয়স $[0, 100]$-এ ক্লিপ করা, $n = 1000$ রোগী, $\varepsilon = 1$।

কোয়েরি $f(D) = \frac{1}{n}\sum x_i$। $n$ ফিক্সড থাকলে L1 সেনসিটিভিটি $= 100/1000 = 0.1$। নয়েজ স্কেল $= 0.1/1 = 0.1$। এই নয়েজের standard deviation মাত্র $\sqrt{2} \cdot 0.1 \approx 0.14$ বছর — বাস্তবে প্রায় অদৃশ্য।

python

Copy

নয়েজ স্কেল ঠিক করতে শুধু দুটো সংখ্যা লাগে — সেনসিটিভিটি আর epsilon। কোনো অনুমান নেই, কোনো tuning নেই।

বৈশিষ্ট্যসমূহ

Gaussian মেকানিজম

অন্য মেকানিজম কেন দরকার?

Laplace মেকানিজম সর্বোত্তম — কিন্তু শুধু pure DP-তে। বাস্তবে অনেক গুরুত্বপূর্ণ সিস্টেম — যেমন নিউরাল নেটওয়ার্কের জন্য DP-SGD — অনেক উচ্চমাত্রার আউটপুট নিয়ে কাজ করে। সেখানে Laplace মেকানিজম অনেক বেশি নয়েজ যোগ করে।

কল্পনা করো একজন শিক্ষার্থীর কাছে দশ লাখ প্যারামিটারের একটা গ্রেডিয়েন্ট ভেক্টর আছে। Laplace নয়েজ প্রতিটা মাত্রায় আলাদাভাবে নয়েজ যোগ করে — মোট নয়েজ বিশাল হয়ে যায়। Gaussian মেকানিজম এই সমস্যা সমাধান করে: pure DP-র কঠোরতা একটু কমিয়ে $(\varepsilon, \delta)$-DP দেয়, কিন্তু উচ্চমাত্রায় অনেক কম নয়েজ লাগে।

মেকানিজম

$f: \mathcal{D} \to \mathbb{R}^k$ ফাংশনের L2 সেনসিটিভিটি $\Delta_2 f$ হলে, Gaussian মেকানিজম আউটপুট দেয়:

$$\mathcal{M}(D) = f(D) + \mathcal{N}(0, \sigma^2 I_k)$$

যেখানে $(\varepsilon, \delta)$-DP নিশ্চিত করতে ($\varepsilon \leq 1$-এর জন্য):

$$\sigma \geq \frac{\Delta_2 f \cdot \sqrt{2 \ln(1.25/\delta)}}{\varepsilon}$$

$\delta$ মানে কী সহজভাবে? $(\varepsilon, \delta)$-DP বলে: $1 - \delta$ probability-তে প্রাইভেসি গ্যারান্টি pure $\varepsilon$-DP-র মতোই শক্ত থাকে। বাকি $\delta$ probability-তে মেকানিজম সম্পূর্ণভাবে ব্যর্থ হতে পারে। $\delta$ হলো সেই ক্ষুদ্র সম্ভাবনা যে নয়েজ যথেষ্ট না হয়ে যায়। $n$ রেকর্ডের ডেটাসেটে $\delta$ অবশ্যই $1/n$-এর চেয়ে অনেক ছোট হতে হবে।

কেন Laplace না? $k$-মাত্রার আউটপুটে মোট নয়েজ বাড়ে — Gaussian হলে $\sigma\sqrt{k}$, Laplace হলে $k \cdot \sigma'$। ১০ লাখ প্যারামিটারে Laplace-এর মোট নয়েজ Gaussian-এর চেয়ে $\sqrt{k} \approx 1000$ গুণ বেশি হতে পারে।

python

Copy

L2 বনাম L1 সেনসিটিভিটি

Gaussian মেকানিজম L1 না, L2 সেনসিটিভিটি ব্যবহার করে। আগে দেখেছিলাম $\Delta_2 f \leq \Delta_1 f$ সবসময়। $k$-মাত্রার আউটপুটে ব্যবধান $\sqrt{k}$ পর্যন্ত হতে পারে। ১০ লাখ প্যারামিটারের গ্রেডিয়েন্টে এই সুবিধাই Gaussian মেকানিজমকে DP-SGD-এর ডিফল্ট পছন্দ বানায়।

Laplace vs Gaussian Mechanism — Noise Shape and Use CasesIllustration coming soon

বৈশিষ্ট্যসমূহ

Exponential মেকানিজম

যখন আউটপুট কোনো সংখ্যা না

Laplace আর Gaussian নয়েজ সংখ্যায় যোগ হয়। কিন্তু আউটপুট যদি সংখ্যা না হয়? যদি তুমি একটা সীমিত set থেকে সবচেয়ে ভালো উত্তরটা বেছে নিতে চাও — সবচেয়ে জনপ্রিয় মুভি সুপারিশ, সেরা চিকিৎসা পদ্ধতি, সর্বোত্তম hyperparameter?

মুভির নামে Laplace নয়েজ যোগ করা যায় না। এটাই Exponential মেকানিজম সমাধান করে।

মেকানিজম

Exponential মেকানিজম একটা scoring function $u(D, r)$ ব্যবহার করে যা প্রতিটা সম্ভাব্য আউটপুট $r \in \mathcal{R}$-কে একটা মান দেয়। তারপর সেই মানের অনুপাতে randomly একটা আউটপুট বেছে নেয়।

দেওয়া আছে:

• ডেটাসেট $D$
• সীমিত আউটপুট space $\mathcal{R}$
• Scoring function $u: \mathcal{D} \times \mathcal{R} \to \mathbb{R}$, সেনসিটিভিটি $\Delta u = \max_{r, D \sim D'} |u(D, r) - u(D', r)|$

Exponential মেকানিজম আউটপুট $r$ বেছে নেয় এই probability-তে:

$$\Pr[\mathcal{M}(D) = r] \propto \exp\!\left(\frac{\varepsilon \cdot u(D, r)}{2 \Delta u}\right)$$

এটা $\varepsilon$-DP (pure differential privacy) নিশ্চিত করে।

মূল কথাটা। বেশি স্কোরের আউটপুট exponentially বেশি probability পায়। $2\Delta u / \varepsilon$ পরিমাণ স্কোর এগিয়ে থাকলে $e$ গুণ বেশি probability পায়। স্কোরের নিরপেক্ষ মান যাই হোক না কেন, শুধু আপেক্ষিক পরিবর্তন গণনা করে — এটাই DP গ্যারান্টি ধরে রাখে।

Scoring function-এর সেনসিটিভিটি

সংখ্যাত্মক কোয়েরির মতোই এখানেও বাউন্ড করতে হবে — একজন মানুষ কোনো candidate-এর স্কোর সর্বোচ্চ কতটুকু বদলাতে পারে:

$$\Delta u = \max_{r \in \mathcal{R}} \max_{D \sim D'} |u(D, r) - u(D', r)|$$

স্কোর যদি কতজন $r$ পছন্দ করে তার কাউন্ট হয়, তাহলে একজন যোগ বা বাদ গেলে স্কোর সর্বোচ্চ ১ বদলায় — $\Delta u = 1$।

বাস্তব উদাহরণ

ধরো বিশ্ববিদ্যালয়ের ক্যান্টিন ভোট। তিনটা অপশন: সায়েন্স বিল্ডিং, ইঞ্জিনিয়ারিং ক্যান্টিন, সেন্ট্রাল ক্যাফেটেরিয়া।

$\varepsilon = 1$, $\Delta u = 1$ হলে সায়েন্স বিল্ডিং প্রায় নিশ্চিত বিজয়ী। কিন্তু ভোটে কাছাকাছি থাকলে uncertainty থাকে — এটাই প্রাইভেসি।

python

Copy

বৈশিষ্ট্যসমূহ

Randomized Response

প্রাইভেসি শুরু হয় ডেটার উৎস থেকেই

এখন পর্যন্ত সব মেকানিজম কাজ করেছে বিশ্লেষকের পক্ষ থেকে: একজন বিশ্বস্ত aggregator আসল ডেটা দেখে, কোয়েরি চালায়, তারপর নয়েজ যোগ করে। কিন্তু বিশ্বস্ত aggregator যদি না থাকে? ব্যবহারকারীরা যদি ডেটা শেয়ার করার আগেই প্রাইভেসি চায়?

Randomized Response এই সমস্যা সমাধান করে। সমাজবিজ্ঞানী Stanley Warner ১৯৬৫ সালে এটা আবিষ্কার করেছিলেন সংবেদনশীল জরিপ (মাদক ব্যবহার, বেআইনি আচরণ) পরিচালনার জন্য। এটা প্রাইভেসি গ্যারান্টি দেয় ডেটা সংগ্রহের স্তরে — কোনো aggregate হিসাব হওয়ার আগেই।

মেকানিজম

ক্লাসিক ফর্ম: ব্যবহারকারীর binary sensitive attribute $x \in \{0, 1\}$ (যেমন, "তোমার কি এই রোগটা আছে?") আছে। সে $p$ probability-তে সত্য বলে, $1-p$ probability-তে উল্টোটা বলে।

$$\Pr[\text{report} = 1 \mid x = 1] = p, \quad \Pr[\text{report} = 1 \mid x = 0] = 1 - p$$

এই মেকানিজম local differential privacy নিশ্চিত করে:

$$\varepsilon = \ln\!\left(\frac{p}{1-p}\right)$$

সাধারণ পছন্দ $p = 3/4$, যা দেয় $\varepsilon = \ln 3 \approx 1.1$।

কেন প্রাইভেট? একজন শত্রু "১" রিপোর্ট দেখে। সে জানে আসল উত্তর $p$ probability-তে ১ আর $1-p$ probability-তে ০। $p < 1$ থাকলে সে নিশ্চিত হতে পারে না। $e^\varepsilon = p/(1-p)$ হলো odds ratio — $\varepsilon$ যত ছোট, $p$ তত $1/2$-এর কাছে, রিপোর্ট তত বেশি random এবং প্রাইভেট।

সত্যিকারের অনুপাত কীভাবে বের করবে? প্রতিটা রিপোর্ট noisy, কিন্তু অনেক ব্যবহারকারীর aggregate de-bias করা যায়। observed proportion $\hat{q}$ হলে আসল proportion-এর অনুমান:

$$\hat{\pi} = \frac{\hat{q} - (1-p)}{2p - 1}$$

python

Copy

De-biased অনুমান $n$ বাড়লে আসল মানে কাছে আসে — কোনো একজনের আসল উত্তর সরাসরি না দেখেও।

Local DP বনাম Central DP

Randomized Response হলো Local Differential Privacy (LDP)-এর সবচেয়ে পরিচিত উদাহরণ:

বৈশিষ্ট্যসমূহ

নয়েজ ক্যালিব্রেশন

মূল ডিজাইন প্রশ্ন

প্রতিটা মেকানিজমে একটা নয়েজ parameter আছে — Laplace-এ scale $b$, Gaussian-এ standard deviation $\sigma$, Randomized Response-এ flip probability $p$। এই parameter বেছে নেওয়াকে বলা হয় নয়েজ ক্যালিব্রেশন। এটা শুধু একটা formula দেখার কাজ না — এটা একটা design সমস্যা।

প্রাইভেসি বনাম Utility

মূল টানটান: বেশি নয়েজ = বেশি প্রাইভেসি = কম কার্যকর আউটপুট। মেকানিজমগুলো তোমাকে কোণঠাসা করে ধরে; তুমি ঠিক করো কোথায় থামবে।

কম্পোজিশন আর বাজেট বিভাজন

একই ডেটাসেটে একাধিক কোয়েরি চালালে প্রাইভেসি বাজেট জমে। Basic composition theorem বলে: $k$টা কোয়েরি $\varepsilon_i$ বাজেটে চালালে মোট খরচ $\sum_i \varepsilon_i$ পর্যন্ত।

বাস্তব মানে: মোট বাজেট $\varepsilon_{\text{total}}$ আর $k$টা কোয়েরি হলে, প্রতিটা পায় $\varepsilon_{\text{total}} / k$। $k$ বাড়লে প্রতিটা কোয়েরি বেশি noisy হয়। তাই কোয়েরির সংখ্যাটা বাজেটের মতোই গুরুত্বপূর্ণ।

বাস্তবে ক্যালিব্রেশন: DP-SGD উদাহরণ

প্রতিটা training step-এ DP-SGD করে:

১. Per-sample gradient হিসাব করো mini-batch-এর প্রতিটা উদাহরণের জন্য।
২. প্রতিটা gradient L2 norm $C$-তে ক্লিপ করো — এটাই L2 sensitivity = $C$ নিশ্চিত করে।
৩. Clipped gradient যোগ করো আর Gaussian নয়েজ যোগ করো $\sigma = C \cdot \sigma_{\text{mult}}$।
৪. Privacy cost track করো moments accountant দিয়ে।

python

Copy

কখন কোন মেকানিজম ব্যবহার করতে হবে

এটাই practical সারসংক্ষেপ। সঠিক মেকানিজম নির্ভর করে চারটা জিনিসে: আউটপুট ধরন, সেনসিটিভিটি ধরন, বিশ্বাসের মডেল, আর প্রাইভেসির সংজ্ঞা।

DP Mechanism Selection Decision TreeIllustration coming soon

বিশ্বাসের সীমাটাই নির্ধারক

বিশ্বস্ত aggregator থাকলে: Central DP মেকানিজম (Laplace, Gaussian, Exponential) একই $\varepsilon$-তে অনেক বেশি accuracy দেয়।

বিশ্বস্ত aggregator না থাকলে: Local DP (Randomized Response আর এর বিভিন্ন রূপ) ছাড়া উপায় নেই। Accuracy-র মূল্য দিতে হয়, কিন্তু প্রাইভেসি গ্যারান্টি অনেক শক্ত — system operator-এর কাছ থেকেও প্রাইভেট।

δ একটা ডিজাইন সিদ্ধান্ত, default না

Laplace (pure $\varepsilon$-DP) বনাম Gaussian ($(\varepsilon, \delta)$-DP) বেছে নেওয়ার সময়:

• Threat model যদি প্রাইভেসি ব্যর্থতার বিন্দুমাত্র সম্ভাবনা সহ্য করতে না পারে — Laplace ব্যবহার করো।
• $\delta$ যদি $10^{-8}$ বা ছোট করা যায় আর আউটপুট উচ্চমাত্রার — Gaussian প্রায় সবসময়ই utility-তে এগিয়ে।
• বেশিরভাগ practical ML সিস্টেমে Gaussian + advanced composition (RDP) স্ট্যান্ডার্ড পছন্দ।

সাধারণ ভুলগুলো

ইন্টারভিউ কর্নার

মূল শিক্ষা

পরবর্তী যাত্রা

চারটা মূল মেকানিজম শেখা হয়েছে — এখন তোমার কাছে individual DP component তৈরির পুরো toolkit আছে। স্বাভাবিক পরের প্রশ্ন হলো এগুলো কীভাবে একসাথে ব্যবহার করবে: বাজেট শেষ না করে একাধিক কোয়েরিতে মেকানিজমগুলো কীভাবে compose করবে? Advanced composition theorem, Rényi DP, আর privacy amplification by subsampling এই প্রশ্নের উত্তর — এগুলোই DP-SGD-কে বাস্তবে হাজার হাজার gradient step জুড়ে কার্যকর করে।