Less Noise, Same Certificate: Retain Sensitivity for Unlearning

이 논문은 머신 언러닝에서 보존 데이터의 프라이버시를 보호할 필요가 없다는 점을 활용하여 '보존 민감도'를 정의함으로써 기존 차등 프라이버시 기반의 과도한 노이즈를 줄이면서도 동일한 인증을 달성할 수 있음을 이론적·실증적으로 증명합니다.

핵심

이 논문은 **"기억 지우기 (Machine Unlearning)"**라는 주제를 다루고 있습니다. 쉽게 말해, AI 가 특정 사람의 데이터를 잊어버리게 하되, 그 사람의 데이터가 없었을 때 처음부터 다시 학습한 결과와 통계적으로 구별할 수 없을 정도로 똑같아지도록 만드는 기술에 관한 연구입니다.

이 논문이 제안한 핵심 아이디어는 **"덜 많은 소음으로, 같은 인증을 받자 (Less Noise, Same Certificate)"**는 것입니다.

이 복잡한 개념을 일상적인 비유로 쉽게 설명해 드릴게요.

---

1. 배경: 왜 '기억 지우기'가 필요할까요?

상상해 보세요. 어떤 AI 비서가 당신과 친구들의 대화 기록을 모두 학습해서 똑똑해졌습니다. 그런데 갑자기 친구 A 가 "내 대화 기록을 지워달라"고 요청했습니다 (GDPR 같은 개인정보 보호법 때문이죠).

• 기존 방식 (전체 재학습): 친구 A 의 기록을 지우려면, AI 는 친구 A 의 기록을 빼고 친구 B, C, D... 모두의 기록을 다시 처음부터 학습해야 합니다. 이는 마치 학교를 다시 입학해서 1 학년부터 다시 공부하는 것과 같아 매우 비싸고 느립니다.
• 새로운 방식 (인증된 지우기): AI 가 "내가 A 를 잊어버렸어"라고 증명하면서, A 가 없었을 때의 상태와 똑같은 모델을 빠르게 만들어내는 기술입니다.

2. 기존 문제점: "너무 무서워서 소음을 너무 많이 뿌린다"

기존 기술들은 **차별화된 프라이버시 (Differential Privacy)**라는 개념을 차용했습니다. 이 개념은 "어떤 데이터가 들어오든, AI 의 결과가 크게 달라지지 않게 하라"는 원칙입니다.

이를 위해 AI 는 **소음 (Noise)**을 섞어서 결과를 흐리게 만듭니다. 마치 안개 낀 날에 사진을 찍는 것처럼요.

• 기존 방식의 문제: "만약 세상에 존재하는 가장 최악의 데이터가 들어와도 결과가 안 변해야 해!"라고 가정합니다. 그래서 **최악의 경우 (Global Sensitivity)**를 기준으로 소음을 엄청나게 많이 뿌립니다.
• 비유: 비가 올지 말지 모르는 날, "혹시 폭우가 쏟아질지도 모르니" 방수 우비 100 장을 껴입고 나가는 것과 같습니다. 비가 오지 않는 날 (대부분의 경우) 에는 너무 덥고 불편합니다.

3. 이 논문의 혁신: "우리가 가진 데이터만 보면 되는데, 왜 최악을 걱정해?"

이 논문의 저자들은 중요한 사실을 발견했습니다.

"기억 지우기"를 할 때는, 지울 데이터 (A) 만 숨기면 됩니다. 나머지 친구들 (B, C, D...) 의 데이터는 이미 알고 있고, 그 데이터는 변하지 않습니다.

기존 방식은 "어떤 데이터가 들어오든"을 가정하지만, 기억 지우기는 "남아있는 데이터 (R)"가 고정되어 있을 때만 고려하면 됩니다.

• 새로운 개념 (Retain Sensitivity): "남아있는 친구들 (R) 을 기준으로 했을 때, 한 명 (A) 이 사라졌을 때 AI 가 얼마나 흔들리는가?"를 계산합니다.
• 비유:
  • 기존 (Global Sensitivity): "우리가 100 명일 때, 1 명이 사라져도 우리가 흔들리지 않게 하려면 100 명 모두를 단단하게 묶어야 해!" (너무 많은 소음)
  • 이 논문 (Retain Sensitivity): "우리는 이미 99 명으로 단단하게 묶여 있어. 1 명이 사라져도 우리가 흔들리지 않을 거야. 그러니까 약간의 소음만 섞으면 돼." (적은 소음)

4. 구체적인 예시: 어떻게 소음을 줄일 수 있을까요?

이 논문은 여러 상황에서 이 '적은 소음'이 얼마나 큰 차이를 만드는지 증명했습니다.

• 중간값 (Median) 구하기:

  • 데이터가 1 부터 100 까지 고르게 분포되어 있다면, 한 숫자를 빼도 중간값은 거의 변하지 않습니다.
  • 하지만 기존 방식은 "만약 1 과 100 이 모두 사라질 수도 있다"고 가정해 큰 소음을 뿌립니다.
  • 이 논리는 "지금 남아있는 숫자들이 50, 51, 52 로 모여있으니, 한 개를 빼도 50.5 에서 크게 벗어나지 않아"라고 계산해 소음을 대폭 줄입니다.

• 최단 경로 (MST) 찾기:

  • 도로망에서 한 도로가 끊겨도 전체 경로가 크게 바뀌지 않는 경우가 많습니다.
  • 남아있는 도로망이 튼튼하면 (데이터가 잘 정리되어 있으면), 한 도로를 지워도 전체 경로에 미치는 영향은 미미합니다. 이 논리는 그 '튼튼함'을 계산에 넣어 소음을 줄입니다.

• 학습 모델 (SVM, ERM) 업데이트:

  • AI 가 학습할 때, 데이터가 잘 정리되어 있으면 (곡률이 좋으면) 한 데이터를 지워도 모델이 크게 흔들리지 않습니다.
  • 이 논리는 "지금 남아있는 데이터가 얼마나 튼튼한지"를 계산해서, 불필요한 소음을 뿌리지 않고 정확한 지우기를 수행합니다.

5. 결론: 더 적은 소음, 더 좋은 성능

이 논문의 핵심 메시지는 다음과 같습니다.

1. 기존 방식: "모든 가능성을 대비해서" 소음을 너무 많이 뿌려서, AI 의 성능 (정확도) 이 떨어졌습니다.
2. 이 논문의 방식: "남아있는 데이터가 이미 안정적이라면" 그 안정성을 이용해 소음을 최소화했습니다.
3. 결과: 같은 수준의 '기억 지우기 인증'을 받으면서도, AI 는 더 정확해지고, 소음은 훨씬 적게 뿌리게 되었습니다.

한 줄 요약:

"기억 지우기를 할 때, '세상에서 가장 나쁜 경우'를 걱정하며 과하게 소음을 뿌리지 말고, '지금 남아있는 좋은 데이터'가 얼마나 튼튼한지 보고 필요한 만큼만 소음을 뿌려라. 그럼 AI 는 더 똑똑해지고, 우리는 더 적은 비용으로 개인정보를 지울 수 있다."

이 기술은 앞으로 AI 가 개인정보를 더 빠르고 정확하게 삭제하면서도, 여전히 똑똑한 서비스를 제공할 수 있는 길을 열어줄 것입니다.

기술 요약

1. 문제 제기 (Problem)

• 배경: GDPR 등 데이터 삭제 권리 (Right to be Forgotten) 와 중독된 데이터 (poisoned data) 또는 저작권 침해 데이터의 제거 필요성으로 인해, 학습된 모델에서 특정 데이터셋 $U$의 영향을 제거하는 '기계 삭제 (Machine Unlearning)'가 중요해졌습니다.
• 기존 접근법의 한계:
  • 기존 인증된 삭제 방법들은 대부분 차등 프라이버시 (Differential Privacy, DP) 기법을 차용합니다.
  • DP 는 모든 인접 데이터셋 (neighboring datasets) 에서의 출력 변화를 보호하기 위해 **전역 민감도 (Global Sensitivity, GS)**에 기반하여 노이즈를 주입합니다. 전역 민감도는 최악의 경우 (worst-case) 데이터셋 변화에 대한 민감도를 의미합니다.
  • 문제점: 삭제된 데이터 $U$의 영향을 숨기는 것만으로는 충분하지만, DP 방식은 유지된 데이터 $R$의 특성까지도 보호해야 한다는 전제 하에 과도하게 보수적인 (conservative) 노이즈를 추가합니다. 이로 인해 모델의 유용성 (Utility) 이 크게 저하됩니다.

2. 방법론: 유지 민감도 (Retain Sensitivity, RS)

저자들은 삭제된 데이터 $U$의 영향만 숨기고, 유지된 데이터 $R$은 고정된 상태로 간주할 수 있다는 핵심 통찰에서 출발하여 새로운 민감도 개념인 **유지 민감도 (Retain Sensitivity, RS)**를 정의했습니다.

• 정의: 특정 유지 데이터셋 $R$이 고정되어 있을 때, 삭제 집합 $Z$ (단일 점) 가 $R$에 추가되거나 제거됨에 따라 알고리즘의 출력이 변할 수 있는 최악의 변화량을 의미합니다.
  • 수식: $RS_f(R) = \max_{Z: |Z|=1} \|f(R \cup Z) - f(R)\|$
• 전역 민감도 (GS) 와의 차이:
  • GS: 모든 가능한 데이터셋 조합에 대한 최악의 변화 ($\max_{S, S'} \|f(S) - f(S')\|$).
  • RS: 고정된 $R$을 기준으로 한 변화. 따라서 $RS_f(R) \leq GS_f$이며, 실제 데이터 $R$의 안정성 (stability) 에 따라 GS 보다 훨씬 작을 수 있습니다.
• 이론적 근거:
  • DP 는 인접 데이터셋 간의 구별 불가능성을 보장해야 하므로 데이터 의존적 민감도 (Local Sensitivity) 를 직접 사용할 수 없습니다 (노이즈 스케일이 입력에 의존하면 프라이버시가 깨짐).
  • 하지만 인증된 삭제는 $R$이 고정된 상태에서 $R \cup U$ (원래 모델) 와 $R$ (재학습 모델) 의 분포가 구별 불가능해야 합니다. 이 경우 $R$에 기반한 노이즈 스케일링이 가능하므로, RS 를 기반으로 노이즈를 조정해도 인증 (Certificate) 을 유지할 수 있습니다.

3. 주요 기여 (Key Contributions)

1. 유지 민감도 (RS) 의 공식적 정의 및 증명:
   • 수동 (Passive) 및 능동 (Active) 삭제 알고리즘 모두에서 RS 가 노이즈 보정을 위한 충분조건 (필요조건인 경우도 있음) 임을 수학적으로 증명했습니다.
   • RS 기반 노이즈 주입이 $(\epsilon, \delta)$-삭제 보장을 만족함을 보였습니다.
2. 다양한 문제에 대한 RS 상한선 유도 및 분석:
   • 최소 신장 트리 (MST) 가중치: 유지된 그래프의 절단 (cut) 구조에 따라 RS 가 결정되며, 전역 민감도보다 훨씬 작음을 보였습니다.
   • 주성분 분석 (PCA): 고유값 간격 (eigengap) 이 클 때 RS 가 급격히 감소함을 보였습니다.
   • SVM (하드 마진): 마진 (margin) 이 클수록 RS 가 감소합니다.
   • 경험적 위험 최소화 (ERM): 데이터 의존적인 강한 볼록성 (data-dependent strong convexity, $\lambda_R$) 을 이용하여 전역적인 $\lambda$ 대신 더 큰 $\lambda_R$을 사용할 수 있음을 보였습니다.
3. 기존 알고리즘의 개선:
   • Descent-to-Delete (D2D): 유지 집합 $R$의 조건수 (condition number) 를 활용하여 필요한 반복 횟수를 크게 줄였습니다.
   • Newton Update: Hessian 의 역행렬 bound 를 데이터 의존적으로 조정하여 노이즈 스케일을 $O((\lambda/\lambda_R)^3)$만큼 줄였습니다.

4. 실험 결과 (Results)

• 수동 삭제 (Passive Unlearning):
  • 여러 데이터셋 (MNIST, ACSIncome, MST 네트워크 등) 에서 RS 기반 노이즈가 GS 기반 노이즈보다 수십 배에서 수백 배 (orders of magnitude) 적게 필요함을 확인했습니다.
  • 특히 정규화 파라미터 $\lambda$가 작을 때 (즉, 모델이 데이터에 민감할 때) 개선 효과가 극대화되었습니다.
• 능동 삭제 (Active Unlearning):
  • Descent-to-Delete: GS 기반 분석 대비 최대 $10^5$배 적은 반복 횟수로 동일한 삭제 보장을 달성했습니다.
  • Newton Update: RS 기반 노이즈를 적용했을 때, 재학습 (Retraining) 과 거의 동일한 정확도를 유지하면서도 노이즈는 현저히 줄어듦을 확인했습니다.
• 시각화: 그림 1 과 2 에서 유지 데이터가 잘 조건화 (well-conditioned) 되어 있을 때 (예: 큰 마진, 큰 고유값 간격) RS/GS 비율이 1 에 가까워지거나 0 에 수렴하는 것을 보여주었습니다.

5. 의의 및 결론 (Significance)

• 개념적 전환: 기계 삭제는 DP 와 달리 유지 데이터의 프라이버시를 보호할 필요가 없으므로, **데이터 의존적 민감도 (Data-dependent Sensitivity)**를 사용할 수 있음을 처음으로 체계적으로 증명했습니다.
• 실용적 가치: 기존 DP 기반 삭제 방법들이 겪던 '과도한 노이즈로 인한 성능 저하' 문제를 해결하여, 실제 환경에서 더 정확하고 효율적인 삭제 알고리즘을 가능하게 합니다.
• 미래 과제: 유지 민감도를 계산하기 위한 효율적인 추정 방법 개발과 대규모 모델 (Deep Learning) 에의 적용이 향후 연구 과제로 제시되었습니다.

요약하자면, 이 논문은 "삭제된 데이터의 영향만 숨기면 되므로, 유지된 데이터의 특성을 이용해 더 적은 노이즈로 동일한 보안 수준을 달성할 수 있다"는 통찰을 바탕으로, 기계 삭제의 효율성을 획기적으로 높이는 이론적 틀과 알고리즘 개선을 제시했습니다.