전역 민감도·입력 제한·Laplace 잡음

잡음보다 먼저 보호할 변화를 정한다

차등 프라이버시는 두 인접 데이터의 출력 분포를 비교합니다. 따라서 잡음을 얼마나 넣을지 선택하기 전에 인접성을 정해야 합니다. 이 단원은 인원 n이 공개된 고정값이며 각 값을 공개된 고정 구간 [0,B]로 먼저 제한한다고 가정합니다. 한 사람의 값을 이 구간 안의 다른 값으로 교체하는 것이 인접 변화입니다. 이 모형 자체가 인원이나 명단을 숨기는 것은 아닙니다.

행 추가·삭제와 행 교체는 다른 인접성입니다. 히스토그램에서는 한 사람의 값 교체가 두 구간의 개수를 동시에 바꿀 수 있습니다. 분모까지 변하는 평균은 고정 n의 평균과도 다릅니다. ‘평균’이라는 이름만 보고 민감도 공식을 가져오면 안 됩니다.

B는 비공개 자료와 독립적으로 정한 공개 경계입니다. 관측한 최댓값을 그대로 경계로 사용하면 그 값 자체가 비공개 통계일 수 있고, 다른 가능한 입력의 변화량을 제한하지도 못합니다.

전역 민감도는 조회한 차이 하나가 아니다

실수 질의 f의 전역 민감도는

$$\Delta f=\sup_{D\sim D'}|f(D)-f(D')|$$

입니다. 정의한 전체 입력 공간의 모든 인접 쌍에 대해 가장 큰 변화량을 구합니다. 한 쌍의 차이가 작다고 전역 상계가 작아지는 것은 아닙니다. 국소 민감도는 한 데이터 D를 고정한 뒤 그 이웃들 중에서 최대를 취하는 별도의 개념입니다. 조회한 차이 하나는 자동으로 국소 민감도도 아닙니다.

실습의 조회 이웃은 모든 값이 0인 데이터에서 한 값을 요청한 교체값으로 바꾼 것입니다. 요청값은 B로 제한합니다. 반면 밀도 그림은 전역 민감도를 달성하는 최악 이웃의 출력입니다. 조회용 한 쌍과 전체 보장용 극단 쌍의 역할을 나누어 읽으세요.

네 질의의 민감도를 증명한다

합에서는 바뀌지 않은 모든 항이 상쇄됩니다. 남는 두 값의 차이는 B 이하이며 0을 B로 교체하면 정확히 B가 됩니다. 따라서 합의 전역 민감도는 B입니다.

고정 크기 평균에서는

$$\left|\frac1n\sum_i x_i-\frac1n\sum_i x'_i\right| =\frac{|x_j-x'_j|}{n}\le\frac Bn$$

입니다. 같은 끝점 교체가 B/n을 달성합니다. 고정 조건 x>B/2를 만족하는 사람 수는 지시변수 하나만 변하므로 민감도가 1입니다. B>0에서 0을 B로 바꾸면 실제로 1이 달성됩니다. 상수 질의 f(D)=7은 입력과 무관하여 민감도가 0입니다.

각 증명은 모든 실수 입력에 대한 상계와 그 상계를 달성하는 이웃을 함께 제공합니다. 작은 격자의 전수 검사만으로 연속 입력 공간 전체의 상계가 증명되는 것은 아닙니다. 유한한 공개 경계가 없다면 합과 고정 크기 평균의 교체 민감도는 제한 없이 커질 수 있습니다.

출력 단위에 맞는 Laplace 잡음을 더한다

출력을 M(D)=f(D)+Z로 두고 Z의 밀도를

$$p_Z(z)=\frac1{2b}e^{-|z|/b},\qquad b>0$$

로 정합니다. b는 출력과 같은 단위의 scale입니다. 민감도도 같은 단위이므로 Δ/b와 ε는 무차원입니다. Laplace의 표준편차는 √2b이고 분산은 2b²입니다. b를 표준편차라고 부르면 보정 계수가 달라집니다.

Dwork·Roth 교재 3.3절은 민감도로 보정한 Laplace 메커니즘을 설명합니다. 여기서는 교체 인접성의 스칼라 경우를 직접 유도합니다. 두 이웃의 질의 중심을 u,v라고 하면

$$\frac{p_u(y)}{p_v(y)} =\exp\left(\frac{|y-v|-|y-u|}{b}\right) \le\exp\left(\frac{|u-v|}{b}\right) \le e^{\Delta/b}.$$

첫 부등식은 삼각부등식입니다. 이 밀도 부등식을 임의의 출력 사건에 적분하면 모든 사건의 순수 DP 부등식을 얻습니다. 따라서 ε>0에서 b≥Δ/ε이면 충분합니다. 양의 Δ를 달성하는 이웃의 꼬리에서는 비율이 실제로 e^(Δ/b)가 되어 이 스칼라 메커니즘의 최소 순수 ε도 Δ/b입니다.

ε가 작을 때 최악 사건을 찾는다

이웃 중심을 0과 d>0으로 평행 이동합시다. 로그 밀도비는 y≤0에서 d/b, 0<y<d에서 (d−2y)/b, y≥d에서 −d/b입니다. ε≥d/b이면 모든 출력의 차이가 양수가 아니므로 필요한 δ는 0입니다. 그렇지 않으면 양의 밀도 차이는 정확히 다음 반직선에서 생깁니다.

$$S=(-\infty,t),\qquad t=\frac{d-b\epsilon}{2}.$$

어떤 사건에서도 음의 차이를 더하면 전체 차이가 줄어듭니다. 그러므로 양의 차이가 있는 반직선 전체를 적분하면 모든 사건 중 최대가 됩니다. 몇 가지 공격을 골라 실험하는 방법과 다른, 전체 사건에 대한 증명입니다. 좌우를 반사하면 반대 방향도 같은 결과입니다.

Laplace 누적 분포를 대입하면

$$\delta_d(\epsilon)= \begin{cases} 0,&\epsilon\ge d/b,\\ 1-\exp((\epsilon-d/b)/2),&0\le\epsilon<d/b. \end{cases}$$

를 얻습니다. 고정한 ε,b에서 d가 커질수록 필요 δ가 커집니다. 따라서 d=Δ를 달성하는 이웃이 있는 이 질의에서는 Δ를 대입한 값이 정확한 전역 프로필입니다. d=0이면 두 분포가 같으므로 δ=0을 따로 처리합니다.

안내 예제를 손으로 계산한다

첫 예제는 n=4,B=2인 합입니다. Δ=2와 b=2로 최소 순수 ε=1이며 ε=1에서 필요한 δ는 0입니다. 잡음 MSE는 2b²=8입니다.

둘째 예제는 같은 입력의 평균입니다. Δ=2/4=0.5이고 b=0.5이면 다시 최소 ε=1입니다. MSE는 평균 단위로 0.5입니다. 평균 출력을 4배 하여 합 단위로 바꾸면 분산은 16배인 8이 됩니다. 같은 무차원 보장 아래 숫자만 작다고 더 좋은 정확도라고 결론 내리지 마세요.

셋째 예제는 합에서 b를 1로 줄이고 ε=1을 주장합니다. 전역 Δ=2이므로 필요 δ는 1−exp(−1/2)≈0.393469입니다. 그러나 조회 교체값은 1이고 조회 차이는 1이므로 이 한 쌍만 보면 δ=0으로 통과합니다. 그 한 쌍이 통과해도 다른 끝점 이웃을 포함한 전체 주장은 실패합니다. 조회값을 2로 바꾸어 최악 쌍을 직접 확인하세요.

추정 오차와 프라이버시는 다른 계산이다

잡음의 평균은 0이므로 공개값은 입력을 제한한 질의의 불편 추정값입니다. 잡음 자체에 대해서는

$$\mathbb E[Z^2]=2b^2,\qquad \mathbb E|Z|=b,\qquad \Pr(|Z|>r)=e^{-r/b}\quad(r\ge0)$$

입니다. b=2이면 MSE=8, 평균 절대 오차=2이고 95% 절대 오차 반경은 2ln20≈5.9915입니다. 이는 제한한 질의 주변의 잡음 오차입니다. 원래 과학적 목표가 제한하기 전의 평균이라면 입력 제한에 따른 편향이 추가될 수 있습니다.

실습은 잡음 출력을 원래 범위로 자르지 않습니다. 출력 clipping은 후처리이므로 유효한 DP 상계는 유지하지만 편향·위험·정확한 프로필을 바꿀 수 있습니다. 입력 제한은 민감도를 정의하고, 출력 제한은 이미 잡음을 더한 답을 바꿉니다.

유한한 그림 창이 꼬리를 없애지는 않는다

첫 그림의 가로축은 f(D₀)를 뺀 출력이고 세로축은 확률이 아닌 밀도입니다. 밀도 높이는 1보다 클 수도 있으며 면적을 적분해야 확률입니다. 그림은 두 중심 바깥으로 여섯 scale까지 표시하지만 실제 출력은 실수 전체에 걸칩니다.

음영은 최대 반직선 사건 중 보이는 부분입니다. 전체 사건 보장은 창 밖의 꼬리까지 적분한 분석식에 근거합니다. ε 프로필의 선분은 0.1 간격의 분석식 값을 잇는 안내선이며 무한 출력에 대한 증명을 대신하지 않습니다.

Laplace의 순수 경계는 정수 입력의 교차곱으로 판단하여 부동소수점 나눗셈의 작은 오차를 피합니다. 양의 δ는 분석식을 부동소수점으로 평가한 근삿값으로 표시합니다. 표시에서 반올림된 숫자로 원래 계산을 덮어쓰지 않습니다.

상수 질의와 ε=0의 경계

상수 질의는 입력에 관한 정보를 드러내지 않으므로 잡음 없이도 정확히 공개할 수 있습니다. 실습은 같은 밀도 모형을 유지하려고 선택한 양의 b를 그대로 둡니다. 이 추가 오차는 보호에 필요한 비용이 아닙니다.

양의 민감도와 유한한 b를 갖는 비상수 질의는 ε=0에서 양의 δ가 필요합니다. b를 무한대로 보내는 극한을 유한한 유용한 순수 메커니즘으로 해석하면 안 됩니다. 보정식 Δ/ε에 ε=0을 대입하여 나누지도 않습니다.

연습 문제와 해설

1. n=8,B=4인 합과 평균의 민감도는 각각 얼마인가요? 4와 0.5이며 끝점 교체가 달성합니다.
2. 평균의 Δ=0.5, 순수 ε=0.25이면 최소 b와 MSE는? b=2이고 평균 단위 MSE는 8입니다.
3. Δ=2,b=1,ε=1에서 실패를 증명하는 사건은? 중심을 0,2로 옮겼을 때 y<0.5인 반직선입니다. 사건 차이는 1−exp(−0.5)입니다.
4. 조회값을 0으로 두면 전역 민감도도 없어지나요? 아닙니다. 그 조회 쌍만 같아지며 다른 끝점 쌍의 변화량은 유지됩니다.
5. 관측 표준편차를 민감도 대신 쓰면 왜 안 되나요? 가능한 모든 교체를 제한하지 않으며 그 통계 자체가 비공개 정보일 수도 있습니다.
6. 상수 질의에서 b=1의 MSE=2가 필수인가요? 아닙니다. 상수는 잡음 없이 공개해도 됩니다.

구성과 AI 학습에 연결한다

앞 단원의 구성 정리는 먼저 유효한 한 단계 보장이 있어야 적용할 수 있습니다. 입력 경계·공개 좌표·중간 통계가 바뀌면 한 단계 메커니즘도 바뀝니다. 벡터에 독립 Laplace 잡음을 더할 때는 전체 벡터의 L1 민감도를 사용합니다. 스칼라 평균 공식으로 임의의 gradient 공개를 인증할 수는 없습니다.

짝 단원에서는 Gaussian 잡음의 전체 사건 프로필을 유도합니다. Gaussian 표준편차와 Laplace scale은 다르며 순수 프라이버시의 경계도 다릅니다.