An Introduction to Machine Unlearning 논문 리뷰 (1)

Introduction

널리 사용되는 기계학습 알고리즘 → 배치 혹은 online learning 방법을 사용하여 새로운 데이로부터 학습은 가능, 그러나 데이터 제거에는 효율적으로 adapt안됨.

데이터 제거의 응용

• 개인 정보 보호 관련 문제
  • ex) EU’s GDPR(General Data Protection Regularization) - “잊혀질 권리”(개인에게 조직의 기록에서 데이터를 제거할 것을 요청할 수 있는 권리)제공
• 공정성 및 데이터 품질 관련 문제
• 데이터 수정
• 편향 감소
• 모델 설명 가능성
• 모델 불확실성 정량화

데이터 제거

retraining

• 지정된 데이터를 제거한 다음 나머지 데이터에서 모델을 처음부터 다시 학습
• 효과적인 방법
• 비효율적 - 큰 계산 비용

unlearning

• 훈련된 모델에서 하위 데이터의 정보를 재학습보다 더 효율적으로 제거하는 것을 보장
• 최초 unlearning 알고리즘 논문 - Towards making systems forget with machine unlearning(2015)
• Exact Unlearning Algorithm: 효율적인 재학습을 위해 초기 학습을 구조화하여 재학습의 계산 비용을 줄임. 그 후에 재학습에서 생성되었을 동일한 모델을 복제.
• Approximate Unlearning Algorithm: 출력 모델과 재학습 모델 사이의 어느 정도의 근사치를 허용

evaluation

• 종종 unlearning 응용 프로그램과 범주에 따라 다름. → 논문들의 평가 프레임워크와 측정값이 일관성 없음.
• 특히, 삭제된 데이터의 정보를 제거한 언러닝 알고리즘이 얼마나 잘 만들어졌는지에 측정하는데에 합의가 거의 없음.
• 이러한 불일치는 심지어 언러닝 알고리즘이 무엇인지 정의할지를 포함하여 현장에 사용되는? 핵심 정의로까지 확장됨.
• prior work (이전 review 논문)
  • Mahadecan and Mathioudakis (2021)
    • 다양한 머신 언러닝들을 비교하여 벤치마크하는 중요한 review paper.
    • 그러나 경사하강법으로 학습된 선형 분류에만 초점을 맞춘 세개의 근사 방법만 고려하였음.
    • 그리고 실제로 언러닝 기술을 적용하는 것에대한 디스커션이 부족한 논문.

contribution

• section 2 → 언러닝 개념의 표준화된 정의
• section 3 → 언러닝 방법을 평가하기 위한 방법 및 각각의 적용 가능성과 한계
• section 4, 5 → 7개의 SOTA 언러닝 방법들 리뷰
  • exact, approximate 접근법으로 분류
  • 각 분류의 범위, 이점 및 한계점에 대해 설명
• section 6 → 결과를 종합하여 다양한 언러닝 기술들을 비교

알고리즘 선별 기준

• 7개의 언러닝 알고리즘 → exact와 approximate 언러닝을 포함하여 광범위한 적용가능성을 커버할 수 있도록 선별
• 경사하강법 기반 모델, 의사결정 트리 기반 모델, convex 손실함수와 non-convex 손실함수를 사용한 알고리즘을 적어도 하나씩 포함하게끔 선별
• 적용가능성, 언러닝 유형과 알고리즘 방법들이 같거나 매우 유사한 알고리즘을 포함하는 것을 최대한 피하여 선별하였음.

Terminology

$\mathcal{X}$: feature space

$\mathcal{Y}$: output space

$\mathcal{Z=X\times Y}$: data point

$\mathcal{Z^*}$: space of datasets

$D \in \mathcal{Z^*}$ : multiset of data points, 중복 entries 허용

objective: D로부터 hypothesis 함수 h:X→Y를 학습.

• $y=h(x) \in \mathcal{Y}$, $x \in \mathcal{X}$가 주어진 경우

Update Mechanism (Definition 1)

$\mathcal{U: H\times Z^*\times Z → H}$

모델 h를 input으로 받고, 모델 h에서 $D_{u}$에 대한 특정 정보를 제거하여 업데이트한 새로운 모델 $\mathcal{U}(h,D,D_{u})$ output으로 준다. 업데이트 메커니즘으로는 removal 메커니즘을 사용한다.

위 update mechanism 식은 update mechanism을 정의하기 위해 필요한 최소한의 input에 대한 식이고, 실제로는 추가적인 input이 요구되는데 이는 뒤 섹션에 설명되어있다.

언러닝에서 $\mathcal{U}$는 처음에는 전체 데이터셋 D로 학습한 모델이 되지만$(h=\mathcal{A}(D)), \mathcal{U}$은 이후에 A이 필수적으로 적용되어야 하는 것은 아니고, 다만 U 그 자체의 몇몇 절차가 적용될 것이다. 이 논문에서의 모든 경우를 고려하면, 메커니즘 $\mathcal{U}$는 무작위 학습 알고리즘으로 동일한 방법으로 랜덤화된다.

학습된 모델에서 $D_u$가 제거되었음을 보장하는 방법은 제거 메커니즘이 데이터셋 $D$ 중에서 $D_u$가 제거되어 학습 알고리즘 A이 적용된 것과 동일하도록 규정되는 것이다.

Exact Removal Mechanism (Exactness), (Definition 2)

무작위 학습 알고리즘 A에 대한 업데이트 메커니즘 U는 scratch로부터 재학습하여 동일한 모델을 얻은 경우에만 exact removal mechanism이라고 한다.

→ 랜덤변수 $U(A(D),D,D_u)$와 $A(D \setminus D_u)$가 동일한 분포를 가지는 U를 찾는다.

Naive Removal Mechanism (Definition 3)

A: randomised training algorithm

U*: naive removal mechanism

다음으로 정의되는 update mechanism이다.

$(\mathcal{A}(D),D,D_u) \mapsto \mathcal{A}(D \setminus D_u)$

이 방법은 매우 많은 계산을 요하기 때문에 Ginart et al. (2019)는 대안적인 방법으로 approximate removal mechanism을 제안했다. 이러한 메커니즘의 확률 분포는 더이상 naive removal의 확률분포와 일치하지 않으므로 모델 h로부터 D_u에 대한 정보가 제거되었음을 보장하는 대체 수단에 의존해야하며, 이를 update mechanism의 certifiability(검증가능성)이라고 한다.

예를 들어 Guo et al.(2020)은 업데이트 메커니즘과 naive 언러닝 간의 통계적 구별 불가능성을 다음과 같이 증명함으로써 이를 보장한다.

$\epsilon$-certifiability (Definition 4)

• $\mathcal{U}$: update mechanism, 모든 데이터셋 D를 사용하여 랜덤의 학습 절차 $A$에 대해 $\epsilon$-certiified 제거 mechanism
• $ D_u \subseteq D $: removal subsets
• $x \in \mathcal{X}$ : inputs
• $T \subseteq \mathcal{Y}$ : output subsets
• $$ e^{-\epsilon}\leq \frac{P[\mathcal{U(A}(D), D, D_u)(x)\in \mathcal{T}]}{P[\mathcal{A}(D\backslash D_u)(x)\in\mathcal{T}]} \leq e^{\epsilon} $$

직관적으로, $\epsilon$-certified removal은 naive 제거를 통한 모델과 업데이트된 모델을 구분할 수 있는 확률이 $e^\epsilon$의 bound에 있도록 해준다.

$(\epsilon,\delta)$-certifiability (Definition 5)

엡실론값과 0보다큰 델타값이 주어졌을 때

$$ P[\mathcal{U(A}(D), D, D_u)(x)\in \mathcal{T}] \leq \ e^\epsilon P[\mathcal{A}(D\backslash D_u)(x)\in\mathcal{T}]+\delta, \\P[\mathcal{A}(D\backslash D_u)(x)\in\mathcal{T}] \leq e^\epsilon\ P[\mathcal{U(A}(D), D, D_u)(x)\in \mathcal{T}]+\delta $$

이는 두 component를 구성하는 언러닝의 정의, 즉 이 메커니즘의 certifiability(검증가능성)를 보장하는 업데이트 메커니즘을 동기화한다. 그러나 여러 논문에서 검증가능성을 보여주는 다양한 방법은 표준 정의로 notion하기 어렵게 만든다. 이것은 아마도 언러닝 방법이 실제로 적용되는 규제의 명확성이 부족해서 특정 검증가능성을 다른 언러닝 방법에 적용하기 어렵기 때문일 것으로 보인다. 이를 회피하기 위해 업데이터 매커니즘은 $\mathcal{A}(D)$에서 $D_u$에 대한 정보를 제거하는 메커니즘의 능력에 관한 검증가능한 일련의 이론적 보장과 경험적 결과를 수반해야 한다고 규정한다. 요구되는 특성과 인정 가능성의 정도는 이론가, 실무자 및 감사인의 외부 판단에 맡겨진다.

Certificate of Unlearning 정의 (Definition 6)

다음 두가지가 정해지면

• randomised training algorithm A
• update mechanism $\mathcal{U}$

certificate unlearning $C_\mathcal{U}$ → certifiability가 외부적으로 다시 계산되고 분석될 수 있는 검증가능한 claim들의 집합이 된다. claim은 임의의 데이터셋 D 및 부분집합 $D_u \subseteq D$에 대해 모델 $\mathcal{U}(\mathcal{A}(D),D,D_u)$에 대한 충분히 작은 양의 정보를 포함한다는 것을 보여주어야 한다. “충분히 작은”의 정확한 의미는 예를 들어, exactness(definition 2)와 $\epsilon$-certifiability (Definition 6)을 만족하는, 특정한 증명가능성 claim에 의존한다.

Machine Unlearning Algorithm (Definition 7)

무작위의 학습 알고리즘 $\mathcal{A}$가 주어졌을 때, 머신 언러닝은 업데이트 메커니즘 $\mathcal{U}$와 언러닝 certificate $C_\mathcal{U}$로 구성되는 쌍 $(\mathcal{U},C_\mathcal{U})$가 된다.

뒤에 보게 되겠지만, 언러닝 알고리즘 중 일부는 언러닝 certificate에 대한 경험적 결과만을 제공한다. 경험적 결과와 측정은 언러닝 certificate에 도움이 되는 추가 사항이지만, 언러닝의 많은 응용 프로그램의 프라이버시에 민감한 특성을 고려할 때, 그것들만으로는 충분하지 않다. 언러닝 certificate에 경험적 결과를 추가하는 것은 제거할 데이터가 오직 approximate degree에만 보장되는 경우의 approximate removal에 가장 유용하다.

Naive Unlearning (Definition 8)

naive 언러닝 알고리즘: $(\mathcal{U}^, C_{\mathcal{U}})$

• $\mathcal{U^*}$: naive unlearning mechanism
• $C_{\mathcal{U}}$: U가 exact한 trivial한 사실을 포함한 경우의 언러닝 certificate

Exact and Approximate Unlearning Algorithms (Definition 9)

$\mathcal{U}$가 exact한 언러닝 메커니즘일때 exact 언러닝 알고리즘은 $(\mathcal{U},C_\mathcal{U})$쌍이 된다, 이 경우 $C_\mathcal{U}$는 $\mathcal{U}$가 exact removal 메커니즘이라는 증명을 포함한다. approximate 언러닝 알고리즘은 exact하지는 않은 언러닝 알고리즘이다.

일회성 batch 제거를 위해 위의 머신 언러닝 프로세스를 공식화했지만, 실제로는 사용자가 데이터 삭제를 요청하는 경우와 같이 제거 sequence에 걸쳐 언러닝이 발생해야 할수 있다. 결과적으로 임의의 제거 sequence에 대한 언러닝 알고리즘 분석이 도움된다. Neel et al. (2020)에 의해 고려된 single removal의 sequence의 가장 간단한 경우는 5.4 섹션의 뒷부분에서 자세히 설명한다. $\left\{z_i | 0 ≤ i ≤ m\right\} \subseteq D$를 학습하지 말아야할 데이터 포인트의 seqeunce라고 한다.

$$ D_0=D,\ D_i=D_{i-1}\backslash \left\{z_{i=1}\right\},\ h_0=\mathcal{A}(D_0), \ h_i=\mathcal{U}(h_{i-1}, D_{i-1}, z_{i-1} ,\ 1\leq i\leq m $$

그리고 위가 각각 언러닝 과정동안의 데이터셋과 언러닝된 모델의 sequence가 된다. (\alpha, \beta)-정확도는 sequence의 길이를 넘어서 언러닝 알고리즘의 얻어진 파라미터의 이론적 보장을 제공한다. 반면에 strong vs weak은 그들의 sequence의 길이에대한 언러닝 속도에 기초하여 알고리즘을 특성화한다.

($\alpha, \beta$)-accuracy, Neel et al(2020) (Definition 10)

$h_i*=A(D_{i-1} \setminus \left\{ z_{i-1} \right\})$를 i=1,…,m에 대한 h_{i-1}에서의 naive 제거의 결과라고 하자. Given \alpha>0, 0<\beta<1

이때 우리는 모든 0≤i≤m에 대하여 (U,C_U)가 (\alpha,\beta)-정확하다고 하면 다음을 만족한다.

$Pr[L(h_i, D_i)-L(h^*_i,D_i)>\alpha]<\beta$

즉, 언러닝 loss와 naive 재학습 loss가 $\alpha$보다 크게 차이가 날 확률은 최대 $\beta$라는 것이다.