Certifying the Right to Be Forgotten: Primal-Dual Optimization for Sample and Label Unlearning in Vertical Federated Learning

이 논문은 수직 연합 학습 (VFL) 환경에서 프라이버시 보호를 위해 특정 데이터나 라벨의 영향을 효과적으로 제거하면서도 재학습과 유사한 성능을 유지하는 'FedORA'라는 원시 - 이중 최적화 기반의 새로운 언러닝 알고리즘을 제안하고 그 이론적 보장과 실험적 유효성을 입증합니다.

핵심

잊혀질 권리를 위한 '기억 지우기' 기술: FedORA 설명

이 논문은 **수직 연방 학습 (Vertical Federated Learning, VFL)**이라는 복잡한 환경에서, AI 가 특정 사람의 데이터를 '완전히 잊어버리게' 만드는 새로운 방법인 FedORA를 소개합니다.

이 기술이 왜 필요한지, 어떻게 작동하는지 일상적인 비유를 통해 쉽게 설명해 드리겠습니다.

---

1. 배경: 왜 '잊혀질 권리'가 필요한가요?

비유: 공동으로 만든 거대한 레시피 책
여러 식당 (데이터를 가진 회사들) 이 각자 다른 재료를 가지고 있어, 함께 모여 '최고의 스테이크 레시피' (AI 모델) 를 만들었다고 상상해 보세요.

• A 식당: 고기 품질 정보
• B 식당: 소스 레시피 정보
• C 식당: 요리법 정보

이들은 각자의 비밀 레시피를 남기지 않고, 오직 '조리된 결과물'만 공유하며 함께 레시피를 완성합니다. 이것이 수직 연방 학습입니다.

하지만 문제는, 만약 A 식당의 한 손님이 "내 고기 정보는 이 레시피에서 지워주세요 (잊혀질 권리)"라고 요청하면 어떻게 될까요?
기존 방식은 **전체 레시피 책을 다 버리고, 남은 재료들만 가지고 처음부터 다시 레시피를 만드는 것 (Retrain)**입니다. 이는 시간이 너무 오래 걸리고 비용이 많이 듭니다.

2. 문제점: 기존 방법들은 왜 실패할까요?

기존의 '기억 지우기' 방법들은 주로 **역방향 학습 (Gradient Ascent)**을 사용했습니다.
비유: "이 요리는 못 먹게 해!"라고 소리 지르기
기존 방법은 "이 특정 손님이 쓴 고기 정보를 모델이 완전히 틀리게 인식하게 만들어라"라고 강요했습니다.

• 문제점: 모델이 너무 당황해서, 그 손님의 정보뿐만 아니라 다른 손님들의 정보까지 엉망으로 기억하게 되는 (과도한 망각) 경우가 많았습니다. 마치 "이 고기는 못 먹어!"라고 너무 크게 소리 치다가, "아, 그럼 소금도 못 쓰나?"라고 착각하는 꼴입니다.

3. 해결책: FedORA (기억을 '혼란스럽게' 만드는 기술)

저자들은 FedORA 라는 새로운 방법을 제안합니다. 핵심은 **"틀리게 만드는 게 아니라, '모르겠다'고 만드는 것"**입니다.

① 원리: "정답을 알려주지 말고, '모르겠다'고 하라"

기존 방법은 정답을 강제로 틀리게 만들려 했지만, FedORA 는 **"이 데이터에 대해 100% 확신하지 말고, 모든 답을 동등하게 고르라 (무작위성)"**라고 가르칩니다.

• 비유: 시험 문제에서 "이 답은 A 가 아니야!"라고 외우는 대신, "A, B, C, D 중 어느 게 정답인지 모르겠어"라고 답하게 만드는 것입니다. 이렇게 하면 모델은 그 데이터의 특징을 더 이상 기억하지 못하게 됩니다.

② 기술: '원 - 쌍대 (Primal-Dual)' 최적화

이것은 **저울 (균형)**을 잡는 기술입니다.

• 한쪽 (원 - Primal): 남은 손님들의 레시피는 여전히 맛있게 유지해야 합니다.
• 다른 쪽 (쌍대 - Dual): 잊혀야 할 손님의 정보는 완전히 지워져야 합니다.
  FedORA 는 이 두 가지 목표를 동시에 달성하기 위해 자동으로 저울을 조절합니다. 잊혀야 할 정보가 너무 많이 남으면 자동으로 더 강하게 지우고, 남은 정보가 흔들리면 더 부드럽게 보호합니다.

③ 효율성: "나머지는 조금만, 지울 건 다 지우자"

기존 방식은 지울 데이터뿐만 아니라, 남은 모든 데이터를 다시 한 번 확인하며 학습했습니다.
FedORA 는 비대칭 배치 (Asymmetric Batch) 방식을 사용합니다.

• 비유: 지울 데이터 (불량 고기) 는 전체를 다 꺼내서 확인하고 버립니다. 하지만, 좋은 재료 (남은 데이터) 는 **일부만抽样 (샘플링)**해서 맛을 보며 레시피를 수정합니다.
• 효과: 전체를 다 다시 계산할 필요가 없으므로, 시간과 비용이 획기적으로 줄어듭니다.

4. 실험 결과: 정말 잘 작동할까요?

논문에서는 다양한 데이터 (소득 정보, 의료 이미지, 사진 등) 로 실험했습니다.

• 성능: 처음부터 다시 레시피를 만든 경우 (Retrain) 와 거의 똑같은 맛 (정확도) 을 유지했습니다.
• 기억 지우기: 잊으려던 데이터에 대해서는 모델이 "모르겠다"고 답하는 비율이 매우 높았습니다.
• 보안: 해커가 "이 데이터는 학습에 사용되었어요?"라고 추측하는 공격 (멤버십 추론) 이나, 특정 신호에 반응하는 백도어 공격에도 효과적으로 방어했습니다.

5. 결론

FedORA는 AI 가 사용자의 "잊혀질 권리"를 존중하면서도, AI 의 성능을 떨어뜨리지 않고 빠르게 실행할 수 있는 현실적인 해결책입니다.

• 기존 방식: "다 버리고 처음부터 다시 만들어라" (비효율적)
• 기존 지우기: "틀리게 만들어라" (과도한 망각 발생)
• FedORA: "모르겠다고 하라" (정확도 유지 + 완벽한 지우기 + 빠른 속도)

이 기술은 개인정보 보호가 중요한 시대에, AI 와 사용자 간의 신뢰를 회복하는 데 큰 역할을 할 것으로 기대됩니다.

기술 요약

1. 연구 배경 및 문제 정의 (Problem)

• 배경: 연방 학습 (Federated Learning, FL) 은 데이터 공유 없이 협업 학습을 가능하게 하지만, AI 모델이 학습 과정에서 민감한 데이터를 기억할 수 있어 '잊힐 권리 (Right to be Forgotten, GDPR 등)'와 관련된 프라이버시 우려가 존재합니다.
• 핵심 문제: 기존 연방 학습에서의 '기억 삭제 (Unlearning)' 연구는 주로 수평적 연방 학습 (HFL) 에 집중되어 있었습니다. 그러나 수직적 연방 학습 (VFL, Vertical Federated Learning) 환경에서는 다음과 같은 고유한 어려움이 존재합니다.
  • 분산된 특징 (Distributed Features): 동일한 샘플의 특징이 여러 당사자 (Party) 에게 분산되어 있어, 특정 데이터의 영향을 제거하려면 당사자 간의 긴밀한 조정이 필요합니다.
  • 계산 및 통신 오버헤드: 모든 특징을 가진 데이터의 상호의존성으로 인해 특정 데이터의 영향을 격리하고 제거하는 과정이 복잡하며, 기존 방법들은 재학습 (Retrain) 에 비해 효율성이 낮거나 모델 성능이 급격히 저하되는 문제가 있었습니다.
  • 기존 방법의 한계: 그라디언트 상승 (Gradient Ascent) 기반의 기존 VFL 기법들은 불안정성이 크며, 목표 데이터를 과도하게 잊어버려 (Catastrophic forgetting) 모델의 유틸리티 (성능) 를 해치거나, 반대로 잊지 못하는 경우가 발생했습니다.

2. 제안 방법론: FedORA (Methodology)

저자들은 FedORA (Federated Optimization for data Removal via primal-dual Algorithm) 라는 새로운 프레임워크를 제안합니다. 이는 VFL 환경에서의 샘플 (Sample) 및 레이블 (Label) 삭제 문제를 제약 최적화 (Constrained Optimization) 문제로 형식화하고, Primal-Dual (원 - 쌍대) 알고리즘을 통해 해결합니다.

주요 기술적 구성 요소:

1. Primal-Dual 최적화 프레임워크:

   • 목적: 남은 데이터 (Remaining Data) 에 대한 손실 최소화 (모델 성능 유지) 와 삭제 대상 데이터 (Unlearning Data) 에 대한 손실 최대화 (기억 삭제) 사이의 균형을 찾습니다.
   • 구현: 라그랑주 승수법을 사용하여 제약 조건을 목적 함수에 통합합니다.
     • Primal 변수 (모델 파라미터): 남은 데이터의 성능을 유지하면서 삭제 데이터의 영향을 줄입니다.
     • Dual 변수 (이중 변수): 삭제 요구사항이 충족되었는지 모니터링하며, 삭제 효과가 부족할 때 삭제 압력을 가하는 '인증자 (Certificate)' 역할을 합니다.

2. 새로운 삭제 손실 함수 (Uncertainty-based Loss):

   • 기존 그라디언트 상승법이 삭제 데이터를 '오분류'시키려 하여 불안정성을 유발하는 것과 달리, FedORA 는 삭제 대상 데이터에 대해 분류 불확실성 (Classification Uncertainty) 을 극대화하도록 설계되었습니다.
   • 손실 함수: 엔트로피 (Entropy) 를 최대화하고 균일 분포 (Uniform Distribution) 와의 KL 발산 (KL Divergence) 을 최소화하는 형태를 취합니다. 이는 모델이 특정 클래스를 예측하지 못하고 모든 클래스에 대해 동일한 확률을 갖도록 하여, 데이터의 영향을 완전히 제거하면서도 모델 구조를 붕괴시키지 않습니다.

3. 적응형 스텝 사이즈 (Adaptive Step Size):

   • Primal 및 Dual 변수 업데이트의 안정성을 보장하기 위해, 연속된 반복 간의 파라미터 변화량을 모니터링하여 스텝 사이즈를 동적으로 조정하는 메커니즘을 도입했습니다.

4. 비대칭 배치 설계 (Asymmetric Batch Design):

   • 삭제 데이터: 완전한 삭제를 위해 전체 배치 (Full Batch) 로 처리합니다.
   • 남은 데이터: 이미 학습에 영향을 미쳤으므로 전체를 다시 학습할 필요는 없습니다. 따라서 남은 데이터의 일부만 샘플링하여 처리함으로써 계산 및 통신 오버헤드를 크게 줄입니다.

3. 주요 기여 (Key Contributions)

1. 최초의 VFL Primal-Dual 삭제 방법: VFL 환경에서 샘플 및 레이블 삭제를 위한 Primal-Dual 최적화 프레임워크를 적용한 최초의 방법 (FedORA) 을 제안했습니다.
2. 불확실성 기반 손실 함수: 오분류가 아닌 '불확실성'을 유도하는 새로운 손실 함수를 설계하여, 과도한 망각을 방지하고 모델 안정성을 확보했습니다.
3. 효율성 최적화: 적응형 스텝 사이즈와 비대칭 배치 처리를 통해 계산 비용과 통신 비용을 획기적으로 줄였습니다.
4. 이론적 증명: FedORA 로 얻은 모델과 처음부터 다시 학습한 (Train-from-scratch) 모델 간의 차이가 상한 (Upper Bound) 으로 제한됨을 수학적으로 증명하여, 삭제 효과에 대한 이론적 보장을 제공했습니다.

4. 실험 결과 (Results)

다양한 표 (Tabular, Income) 및 이미지 (MedMNIST, CIFAR-10/100, Tiny-ImageNet) 데이터셋을 통해 평가되었습니다.

• 성능 유지 (Utility Preservation):
  • FedORA 는 완전 재학습 (Retrain) 과 거의 유사한 테스트 정확도를 유지했습니다.
  • 특히 복잡한 이미지 데이터셋 (CIFAR-100, Tiny-ImageNet) 에서 기존 방법들 (Gradient Ascent, ICO, CVFU) 보다 성능 저하가 훨씬 적었습니다.
• 삭제 효과 (Unlearning Effectiveness):
  • 삭제된 데이터에 대한 예측 정확도 (Unlearning Accuracy) 가 매우 낮았으며, 이는 모델이 해당 데이터를 성공적으로 잊었음을 의미합니다.
  • 멤버십 추론 공격 (MIA): MIA 성공률이 50% (무작위 추측 수준) 에 근접하여, 공격자가 해당 데이터가 학습에 사용되었는지 구분하지 못하게 되었습니다.
  • 백도어 공격 (Backdoor Attack): 백도어 트리거에 대한 반응이 거의 사라져 (BD-ASR < 10%), 악성 패턴이 효과적으로 제거되었음을 확인했습니다.
• 효율성:
  • 계산/통신 비용: 완전 재학습 (Retrain) 에 비해 계산 복잡도와 통신 오버헤드가 현저히 낮았습니다.
  • 실행 시간: Gradient Ascent (GA) 다음으로 빠른 실행 시간을 보였으며, 재학습보다 훨씬 효율적이었습니다.
• 강건성:
  • 비 IID (Non-IID) 데이터 분포 및 차등 프라이버시 (DP) 노이즈가 추가된 환경에서도 안정적인 성능을 유지했습니다.

5. 의의 및 결론 (Significance)

이 논문은 수직적 연방 학습 (VFL) 환경에서의 '잊힐 권리' 실현을 위한 실질적이고 이론적으로 검증된 솔루션을 제시했습니다.

• 프라이버시 보호 강화: 규제 준수 (GDPR 등) 를 위한 데이터 삭제를 효율적으로 수행할 수 있게 하여, 분산 환경에서의 프라이버시 보장을 강화합니다.
• 모델 안정성: 기존 방법들의 불안정성과 과도한 망각 문제를 해결하여, 삭제 후에도 모델의 전반적인 성능을 유지할 수 있음을 입증했습니다.
• 실용성: 계산 및 통신 자원을 효율적으로 사용하여 대규모 VFL 시스템에서도 실제 적용 가능한 수준의 성능을 제공합니다.

결론적으로, FedORA 는 VFL 환경에서 데이터 주권과 모델 유틸리티 사이의 균형을 잡는 최적의 접근법으로 평가받으며, 향후 대규모 모델 및 다양한 프라이버시 위협에 대한 연구의 기초를 마련했습니다.