[ICML 2019] Agnostic FL - (2)

논문 제목: Agnostic Federated Learning

출처: https://arxiv.org/abs/1902.00146

 

 지난 포스트에서 Agnostic FL의 기본적인 아이디어를 확인해보았습니다. (이전 글 보기) 이번 포스트에서는 Agnostic FL이 fairness에 어떻게 기여하는지 살펴볼 계획입니다. 그리고 이후의 내용을 전개하기 위한 몇 가지 정의도 함께 다루도록 하겠습니다.

 

3. Good-intent Fairness

 

 지금부터 하는 이야기는, Agnostic FL의 방법론을 FL이 아닌 다른 분야(domain adaptation, crowdsourcing 등)에서도 적용하기 위하여 일반화하는 과정에 관한 것입니다. 따라서, 지금까지 client라고 불렀던 것들을 해당 파트에서는 class라고 부르도록 하겠습니다. 즉, $p$개의 class $c_1, c_2, \cdots, c_p$로 이루어진 dataset을 사용하여 model을 학습하는 상황을 가정하겠습니다. 그리고 이 중 한 가지는 protected feature class $c$가 될 것입니다.

 

 앞서 언급하였듯이, Fairness 분야에서는 model이 biased되는 것을 최대한 방지하는 것이 주 관심사입니다. 이때, model에 bias를 주는 이유로는 크게 두 가지를 고려해볼 수 있습니다.

 

$(\text{i})$ model 학습에 사용되는 dataset이 biased된 경우

 예를 들어, gender를 protected class로 지정한 상황에서, 특정 성별 모두의 data가 저소득층에서 sampling되었다면, model은 "해당 성별은 소득이 낮은 경향을 보인다"고 학습할 것입니다.

 

$(\text{ii})$ model의 학습 과정이 biased된 경우

 예를 들어, ethnicity를 protected class로 지정한 상황에서, 특정 인종에 대한 data가 전체 dataset에서 대부분을 차지한다면, model은 해당 인종에 대하여 overfitting될 것입니다.

 

 아쉽게도, Agnostic FL이 첫 번째 경우를 해결해주지는 못 합니다. (이는 잘 생각해보면 당연하기도 한데, data 자체에 어떠한 bias가 존재하는지는 dataset을 구성할 때에 확인해야 하는 사안이지, modeling을 통해서 해결할 수 있는 문제가 아닙니다.) Agnostic FL이 해결하고자 하는 것은 두 번째 경우인데, 이는 "특정 유형의 client가 학습에 참여하지 못하였고, 다른 특정 유형의 client가 학습에 크게 관여하였다면, mixture weight $\lambda$를 조절하여 distribution을 estimate해야겠다"는 Agnostic FL의 철학과 일치하는 부분임을 알 수 있습니다.

 

  우선, underlying distribution $\mathcal{D}$에 대하여, $\mathcal{D}_k$를 다음과 같이 conditional distribution으로 정의합니다.

$$\mathcal{D}_k (x, y) := \mathcal{D} (x, y \mid c(x, y) = c_k)$$

다음으로, mixture weight $\lambda$들을 모아놓은 set $\Lambda$를 $\Lambda := \{ \delta_k \mid k \in [p] \} = \{ \delta_1, \cdots, \delta_p \}$로 정의합니다. 이러한 setting 하에서 앞서 언급한 Agnostic FL과 동일하게 학습을 수행하면, 각 $\delta_k$가 mixture weight로 사용될 때, 그 특정 class $c_k$에 가중치가 전부 몰려 있는 상황이 될 것이고, 그렇게 해서 나온 $p$개의 loss 중 가장 큰 값을 $\mathcal{L}_{\mathcal{D}_{\Lambda}}$로 택하게 될 것입니다. 그리고 이 $\mathcal{L}_{\mathcal{D}_{\Lambda}}$를 minimizing하는 task를 계속해서 수행하게 되는 것이죠. 결국은 client라는 개념이 class라는 개념으로 바뀐 것이 전부인 셈입니다.

 

4. Learning Bounds 증명을 위한 몇 가지 definition

 

 지금부터는 Agnostic FL이 정상적으로 학습된다는 것을 증명하고자 하는데, 다루는 내용이 상당히 복잡하고 어려우므로 주의를 요합니다. 우선, weighted Rademacher complexity를 정의해야 하는데, 이는 mixture weight $\lambda \in \Lambda$를 사용하는 우리의 상황에 맞게 Rademacher complexity를 확장한 것입니다. 먼저, $\mathcal{G}$를 모든 $h \in \mathcal{H}$에 대한 loss를 모아 놓은 family로 정의합시다. 즉, $\mathcal{G} := \{ (x, y) \mapsto \ell (h (x), y) \; | \; h \in \mathcal{H} \}$입니다. 그리고 $\textbf{m}$은 $p$개의 client마다 가지고 있는 data의 개수를 모은 vector로 정의합니다. 즉, $\textbf{m} := [m_1, m_2, \cdots, m_p]$이며, $\sum_{k=1}^{p} m_k = m$입니다. 그리고, $\overline{\textbf{m}} := \frac {\textbf{m}} {m} = \left[ \frac {m_1} {m}, \frac {m_2} {m}, \cdots, \frac {m_p} {m} \right]$로 정의합니다. 이때, 주어진 mixture weight $\lambda$에 대하여, weighted Rademacher complexity는 다음과 같이 정의됩니다.

$$\mathfrak{R}_\textbf{m} (\mathcal{G}, \lambda) := \mathbb{E}_{S_k \sim \mathcal{D}_k^{m_k} \\ \quad \boldsymbol{\sigma}} \left[ \sup_{h \in \mathcal{H}} \sum_{k=1}^p \frac {\lambda_k} {m_k} \sum_{i=1}^{m_k} \sigma_{k, i} \ell (h (x_{k, i}, y_{k, i})) \right]$$

여기에서, $\boldsymbol{\sigma} = \left( \sigma_{k, i} \right)_{k \in [p], \; i \in [m_k]}$는 Rademacher variable을 모아놓은 것입니다. 다시 말해, 각 $\sigma_{k, i}$는 $\frac {1} {2}$의 확률로 $-1$의 값을, $\frac {1} {2}$의 확률로 $1$의 값을 갖는 variable입니다. 더 나아가서,  weighted Rademacher complexity를 $\Lambda$마다 정의할 수도 있는데, 이때 $\mathfrak{R}_\textbf{m} (\mathcal{G}, \Lambda) := \max_{\lambda \in \Lambda} \mathfrak{R}_\textbf{m} (\mathcal{G}, \lambda)$입니다.

 

 다음으로, $\overline{\textbf{m}}$에 대한 $\Lambda$의 skewness를 아래와 같이 정의합니다.

$$\mathfrak{s} (\Lambda \parallel \overline{\textbf{m}}) = \max_{\lambda \in \Lambda} \chi^2 (\lambda \parallel \overline{\textbf{m}}) + 1$$

여기에서 $\chi^2(\cdot \parallel \cdot)$은 chi-squared divergence로, $\chi^2 (\lambda \parallel \overline{\textbf{m}}) = \sum_{k=1}^p \overline{\textbf{m}}_k \left( \frac {\lambda_k} {\overline{\textbf{m}}_k} - 1 \right)^2 = \sum_{k=1}^p \frac {\left( \lambda_k - \overline{\textbf{m}}_k \right)^2} {\overline{\textbf{m}}_k}$입니다.

 

 마지막으로, $\Lambda_{\epsilon}$을 정의해야 하는데, 정의가 직관적으로 잘 와닿지 않습니다. 우선, $C(\Lambda, \epsilon)$을 다음과 같이 정의합니다.

$$C(\Lambda, \epsilon) := \left\{ \Lambda' := \{ \lambda_k' \mid k \in [p] \} \;\middle|\; \forall \; \lambda \in \Lambda, \exists \; \Lambda' \text{ such that } \sum_{k=1}^p |\lambda_k - \lambda_k'| \leq \epsilon \right\}$$

즉, $C(\Lambda, \epsilon)$는 $\ell_1$ distance 기준으로 $\Lambda$의 $\epsilon$-neighborhood 안에 있는 $\Lambda'$들로 이루어진 set입니다. (그러므로 당연히 $\Lambda \in C(\Lambda, \epsilon)$입니다.) 그리고 이때, $\ell_1$ distance에서의 $\Lambda$의 minimum $\epsilon$-cover $\Lambda_{\epsilon}$를 다음과 같이 정의합니다.

$$\Lambda_{\epsilon} : = \text{argmin}_{\Lambda' \in C(\Lambda, \epsilon)} \;  |\Lambda|$$

다시 말해, $\Lambda_{\epsilon}$는 $C(\Lambda, \epsilon)$ 안의 모든 $\Lambda'$를 covering할 수 있는 선에서 자기 자신의 크기를 최소화한 mixture weight를 의미합니다. (우연히 $\Lambda = \Lambda_{\epsilon}$일 수도 있겠으나, equality는 보장되지 않습니다.)

 

다음 포스트에서는 지금까지 정의한 $\mathfrak{R}_\textbf{m} (\mathcal{G}, \lambda)$, $\mathfrak{s} (\Lambda \parallel \overline{\textbf{m}})$, 그리고 $\Lambda_{\epsilon}$에 기반하여 learning guarantee를 보일 것입니다.