[ICML 2019] Agnostic FL - (1)

논문 제목: Agnostic Federated Learning

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

 

 이번 포스트부터는 fairness에 관한 내용을 살펴볼 예정입니다. FL의 특성 상 불특정 다수의 client가 학습에 관여하게 되는데, 이때 학습에 기여하는 정도는 각 client 별로 다를 것입니다. 예를 들어, straggler와 같이 환경적인 요인으로 인해 학습에 참여하지 못한 client가 생길 수도 있고, 혹시라도 개인정보가 유출될까봐 걱정되어 데이터 사용에 동의하지 않는 application 사용자도 있을 것입니다. 반대로, random하게 sampling을 진행하지만 우연히도 매 round마다 학습에 참여하게 된 client가 있을 수도 있고, 또 그중에는 학습을 의도적으로 방해하는 Byzantine client가 존재할 수도 있습니다. 이처럼 각 client는 저마다 서로 다른 학습 기여도를 가지고 있는데, 이에 관하여 다음과 같이 두 가지 의문이 존재합니다. (그리고 이는 FL 분야 뿐만 아니라, Crowdsourcing과 같이 다수의 client가 참여하는 방법론이라면 모두 한 번쯤 생각해볼 만한 부분이기도 합니다.)

 

$(\text{i})$ 모든 client에게 동일한 결과를 제공하는 것이 바람직할까? 일을 안 해도 보상이 주어진다면, 아무도 학습에 참여하지 않으려고 하지 않을까? 적게 기여한 사람에게는 그만큼 penalty를 주고, 많이 기여한 사람에게는 그만큼 reward를 주어 학습에 참여하도록 유도하고, 동기부여하는 방향으로 system을 구축해야겠다.

 

$(\text{ii})$ 학습에 많이 관여한 특정 client 집단에 biased된 model이 만들어졌을텐데, 소수의 client에 대해서도 과연 올바르게 inference할 수 있을까? global model에서 gender, ethinicity, nationality 등 특정 집단에 관한 factor들의 영향을 최대한 제거할 수는 없을까? generalized된 global model을 만들어서, 정보가 다소 부족한 유형의 client가 우리의 program을 사용하였을 때에도 올바른 결과를 받아갈 수 있도록 해야겠다.

 

 여기에서 전자의 경우 Contribution Evaluation 분야에서 다루고 있으며, 후자의 경우가 Fairness 분야의 주된 관심사입니다. 그리고 Agnostic FL은 (원래의 논문 집필 의도가 이것인지는 잘 모르겠으나) FL 분야로 fairness를 끌고 온 첫 번째 paper입니다.

 

1. 연구 배경

 

 기존의 aggregation method들을 보면, global model의 distribution을 다음과 같이 정의하였습니다.

$$\bar{\mathcal{U}} := \sum_{k=1}^p \frac {m_k} {m} \mathcal{D}_k, \text{ where } \sum_{k=1}^p m_k = m$$

 그리고  $\bar{\mathcal{U}}$를 추정하기 위한 $\widehat{\mathcal{U}}$은 다음과 같이 정의됩니다.

$$\widehat{\mathcal{U}} := \sum_{k=1}^p \frac {m_k} {m} \widehat{\mathcal{D}}_k, \text{ where } \sum_{k=1}^p m_k = m$$

 즉, 이는 해당 round의 학습에 관여한 $p$개의 client로부터 받아 온 학습 결과를 단순히 uniform하게 더한 것인데, 저자들은 이러한 분포가 과연 global model을 올바르게 estimate할 수 있는 것인지에 대한 의문을 제기합니다. 왜냐하면, sampling된 client들이 전체를 대표하지 못하기 때문입니다. 학습에 참여한 client들과 유사한 특징을 지닌 client가 해당 model을 사용할 경우 비교적 좋은 결과을 얻을 수 있겠지만, 다소 상이한 성격의 client의 경우 올바르지 못한 결과를 받을 수도 있다는 이야기입니다. 이에, 저자들은 이러한 mismatch를 최소화하기 위한 방법을 고안하기 시작합니다.

 

2. Agnostic Federated Learning

 

 Agnostic FL은 uniform distibution을 가정하는 것이 문제라고 이야기 하고 있습니다. 즉, 저자들은 $\sum_{k=1}^p \frac {m_k} {m}$ term이 마음에 들지 않는 것이죠. 따라서 이 term을 mixture weight 라고 부르는 $\lambda := [\lambda_1, \cdots, \lambda_p]$로 대체하였고, 이 $\lambda$에 의하여 정의된 새로운 global model을 (기존의 $\bar{\mathcal{U}}$와 구분하기 위하여) $\mathcal{D}_\lambda$로 denote합니다. 즉, $\mathcal{D}_\lambda$는 다음과 같이 정의됩니다. (여기에서, $\Lambda$는 가능한 모든 $\lambda$의 집합을 의미합니다.)

$$\mathcal{D}_\lambda := \sum_{k=1}^p \lambda_k \mathcal{D}_k \text{ for some } \lambda \in \Lambda$$

 물론, 이 경우에는 $\lambda$를 직접 지정해주어야 한다는 문제가 존재합니다. 따라서 최적의 $\lambda$를 찾는 것이 우리가 해야 할 일이며, 이를 판단하기 위한 metric인 agnostic loss (혹은 agnostic risk) $\mathcal{L}_{\mathcal{D}_\Lambda}$를 다음과 같이 정의하겠습니다. (여기에서, $h$는 우리가 확인하고자 하는 hypothesis 내지는 predictor를 의미하며, $\mathcal{H}$는 가능한 모든 $h$의 집합을 의미합니다. $\ell$은 loss function인데, 별도의 언급이 없는 한 cross-entropy loss를 사용하도록 하겠습니다. 즉, $\ell (h(x), y) = - \log (\mathbb{P}_{y' \sim h(x)} [y' = y])$입니다.)

$$\mathcal{L}_{\mathcal{D}_\Lambda} (h) := \max_{\lambda \in \Lambda} \mathcal{L}_{\mathcal{D}_\lambda} (h) = \max_{\lambda \in \Lambda} \mathbb{E}_{(x, y) \sim \mathcal{D}_\lambda} [\ell (h(x), y)]$$

그리고 이때의 minimizing hypothesis $h$를 $h_{\mathcal{D}_\Lambda} := \text{argmin}_{h \in \mathcal{H}} \mathcal{L}_{\mathcal{D}_\Lambda} (h)$로 정의합니다.

 

 직관적으로 보았을때, Agnostic FL은 가장 큰 loss를 보이는 $\lambda_k \; (k = 1, 2, \cdots, p)$의 조합을 택한 후, 이때의 loss를 최소화하는 방식으로 global model을 구성하고자 한다는 것을 알 수 있습니다. 다시 말해, 최악의 상황에서의 성능을 높이는 것이 해당 방법론의 목적이며, 이는 곧 더 좋은 성능을 낼 수 있는 상황임에도 의도적으로 학습을 덜 시키고 있는 상황임을 의미하기도 합니다. 이는 generalization을 위한 일종의 trade-off 정도로 생각할 수 있고, 이후의 paper들을 보면 실제로 이 trade-off가 크다는 점을 지적하는 모습을 확인할 수 있습니다.

 

 다만, 현실에서는 우리가 직접 각 device의 dataset에 직접적으로 접근할 수 있는 권한이 없으므로, $\mathcal{D}_k$가 아닌 $\widehat{\mathcal{D}}_k$에 기반한 정의가 필요합니다. 따라서 $\bar{\mathcal{D}}_\lambda := \sum_{k=1}^p \lambda_k \widehat{\mathcal{D}}_k$에 대해서 agnostic empirical loss $\mathcal{L}_{\bar{\mathcal{D}}_\Lambda} := \text{argmin}_{h \in \mathcal{H}} \mathcal{L}_{\bar{\mathcal{D}}_\Lambda} (h)$를 정의하도록 하겠습니다. ($\hat{\mathcal{D}}_\lambda$이 아니라 $\bar{\mathcal{D}}_\lambda$임에 유의하시기 바랍니다. $\hat{\mathcal{D}}_\lambda$는 직접적으로 $\mathcal{D}_\lambda$를 estimate하는 것이고, $\bar{\mathcal{D}}_\lambda$는 $\mathcal{D}_k$들에 기반하여 estimate하는 것입니다.) 그리고 이러한 정의에 맞추어서 $h_{\bar{\mathcal{D}}_\Lambda} := \text{argmin}_{h \in \mathcal{H}} \mathcal{L}_{\bar{\mathcal{D}}_\Lambda} (h)$도 함께 정의할 수 있습니다.

 

 이때, 다음 $\text{Proposition}$은 저자들이 제안하는 Agnostic FL이 기존의 aggregation method보다 상수 term 만큼 더 작은 loss를 가진다는 것을 보장해줍니다.

 

$\text{Proposition 1}$

 

 $\ell$이 cross-entropy loss라고 할 때, 다음 부등식을 만족하는 $\Lambda, h \in \mathcal{H}, \mathcal{D}_{k \in [p]}$가 존재한다:

$$\mathcal{L}_{\mathcal{D}_\Lambda} (h_{\bar{\mathcal{U}}}) \geq \mathcal{L}_{\mathcal{D}_\Lambda} (h_{\mathcal{D}_\Lambda}) + \log \frac {2} {\sqrt{3}}$$

 

$\text{Proof}$

 일반성을 잃지 않고, 다음과 같은 상황으로 문제를 축소하고자 한다.

---

 data $x \in \mathcal{X}$를 $\mathcal{Y} = \{ 0, 1 \}$로 mapping하는 Binary Classification을 진행하고자 한다. 이때, 두 client $k = 1, 2$의 distribution $\mathcal{D}_1$, $\mathcal{D}_2$는 다음과 같이 정의되어 있다.

$$\mathcal{D}_1 (x, 0) = 0, \; \mathcal{D}_1 (x, 1) = 1, \; \mathcal{D}_2 (x, 0) = \frac {1} {2} , \; \mathcal{D}_2 (x, 1) = \frac {1} {2}$$

여기에서, 두 client는 동일한 갯수의 data를 가지고 있다고 가정하자. 즉, $h_{\bar{\mathcal{U}}} = \frac {1} {2} (\mathcal{D}_1 + \mathcal{D}_2)$이다. 그리고 $\Lambda = \{ \delta_1, \delta_2 \}$로 정의하자. (단, $\delta_k (k = 1, 2)$는 Dirac mearsure이다.) 

---

 이 상황에서, $p_0$를 $h$가 $x$를 $0$으로 분류할 확률, $p_1$를 $h$가 $x$를 $1$으로 분류할 확률이라고 할 때, 다음 식이 성립함을 알 수 있다. (여기에서, $p_0 + p_1 = 1$임은 자명하다.)

\begin{align*} \mathcal{L}_{\bar{\mathcal{U}}} (h) =  \mathbb{E}_{(x, y) \sim \bar{\mathcal{U}}} \left[ - \log p_y \right] &= \underbrace{\frac {1} {2} \log \frac {1} {p_1}}_{\mathcal{D}_1} + \underbrace{\frac {1} {4} \log \frac {1} {p_0} + \frac {1} {4} \log \frac {1} {p_1}}_{\mathcal{D}_2} \\&= \frac {1} {4} \log \frac {1} {p_0} + \frac {3} {4} \log \frac {1} {p_1} \\&= D_{\text{KL}} \left( \left( \frac {1} {4}, \frac {3} {4}  \right) \parallel (p_0, p_1) \right) + \frac {1} {4} \log \frac {4} {1} + \frac {3} {4} \log \frac {4} {3} \\&\geq \frac {1} {4} \log \frac {4} {1} + \frac {3} {4} \log \frac {4} {3} \; (\because \text{nonnegativity}) \end{align*}

그리고 여기에서 등호는 $0 = D_{\text{KL}} \left( \left( \frac {1} {4}, \frac {3} {4}  \right) \parallel (p_0, p_1) \right) = \frac {1} {4} \log \frac {1} {4 p_0} + \frac {3} {4} \log \frac {3} {4 p_0}$일 때 성립하는데, $p_0 + p_1 = 1$과 함께 해당 식을  정리하면 $p_0 = \frac {1} {4}, p_1 = \frac {3} {4}$임을 알 수 있다. 그리고 이것이 곧 $h_{\bar{\mathcal{U}}}$가 된다. 이때, 비교 대상인 $\mathcal{L}_{\mathcal{D}_\Lambda} (h_{\bar{\mathcal{U}}})$는 다음과 같다.

\begin{align*} \mathcal{L}_{\mathcal{D}_\Lambda} (h_{\bar{\mathcal{U}}}) &= \max \left\{ \mathcal{L}_{\delta_1} (\bar{\mathcal{U}}), \mathcal{L}_{\delta_2} (\bar{\mathcal{U}}) \right\} \\&= \max \left\{ 1 \cdot \log \frac {4} {3}, \frac {1} {2} \log \frac {4} {1} + \frac {1} {2} \log \frac {4} {3} \right\} \\&= \max \left\{ \log \frac {4} {3}, \log \frac {4} {\sqrt{3}} \right\} \\&= \log \frac {4} {\sqrt{3}}  \end{align*}

 다음으로, 우리가 사용하고자 하는 $h_{\mathcal{D}_{\Lambda}}$의 loss를 구하면 다음과 같다.

\begin{align*} \min_{h \in \mathcal{H}} \mathcal{L}_{\mathcal{D}_{\Lambda}} (h) &= \min_{h \in \mathcal{H}} \max_{k \in [p]} \mathcal{L}_{\mathcal{D}_k} \\&= \min_{h \in \mathcal{H}} \max \left\{ \mathcal{L}_{\mathcal{D}_1} (h),  \mathcal{L}_{\mathcal{D}_2} (h) \right\} \\&= \min_{\;\, p_0 + p_1 = 1 \\ 0 < p_0, \; p_1 < 1} \max \left\{ \log \frac {1} {p_1},  \frac {1} {2} \log \frac {1} {p_0} + \frac {1} {2} \log \frac {1} {p_1} \right\} \\&= \min_{0 < p_1 < 1} \max \left\{ \log \frac {1} {p_1}, \log \frac {1} {\sqrt{1 - p_1}} + \log \frac {1} {\sqrt{p_1}} \right\} \; (\because p_0 + p_1 = 1) \\&= \min_{0 < p_1 < 1} \max \left\{ \log \frac {1} {p_1}, \log \frac {1} {\sqrt{p_1 (1 - p_1)}} \right\} \; (\because 0 < p_1 < 1) \\&= \log 2 \end{align*}

따라서, $\log \frac {2} {\sqrt{3}}$ 이상의 loss 차가 보장된다. $\square$

 

 해당 증명이 일반화 가능한 것인지 다소 의문이 들긴 하지만, $\text{Proposition 1}$에 의하면 저자들의 주장이 충분히 그럴듯하다는 것을 확인할 수 있습니다. 다음 포스트에서는 해당 방법론이 어떻게 fairness를 보장하는지에 관하여 알아보도록 하겠습니다.