Federated Learning with Fair Averaging

1. Fairness in FL

 

공정성은 연방 학습(FL)에서 중요한 문제로 떠오릅니다.

 

FL은 다양한 불공정성에 직면하게 되는데 그 중 가장 큰 문제는 규모에 큰 차이가 있는 Conflict gradient입니다.

 

이 문제를 해결하기 위해 저자들은 그라디언트를 평균하기 전에 클라이언트 간의 잠재적인 Conflict를 완화하기 위해 federated fair averaging (FedFV) 알고리즘을 제안합니다.

 

저자들은 먼저 코사인 유사성을 사용하여 그라디언트 conflicts를 찾고 그라디언트의 방향과 크기를 수정해 이와 같은 충돌을 반복적으로 제거하는 프로세스를 보여줍니다.

 

2. Introduction

 

FL은 client 데이터를 통해 개인정보의 유출 없이 global model을 훈련하는것을 목표로 한다고 이전 포스트에서 이야기 했습니다. [McMahan et al., 2017]

하지만 global model은 일반적으로 훈련에 사용되는 데이터의 전체 모수가 local 보다 더 많기 때문에 일반화 성능이 높을것이라 생각되지만 그 과정에서 결코 각 client는 공정한 update에 직면하지 않습니다. 

 

FL의 공정성 문제를 해결하기 위한 다양한 방법이 있었지만 가장 근본적인 원인은 non-IID Setting에서의 Data difference 입니다. 

이는 필연적으로 Gradient의 magnitude의 차이를 불러옵니다. 다시 말해 서로 다른 magnitude의 client's gradient는 충돌을 불러 오고 FL에서 불공정 문제를 가져올 수 있다는 것입니다. 

이와 같은 gradient는 client에서 local로 계산되기 때문에 일부 client의 업데이트 방향은 다른 client의 훈련 성능을 방해 할 수 있습니다. 그래디언트 충돌은 단순한 그래디언트 평균이 글로벌 목적 함수를 최적화하는 데 유효하다는 것을 보여주었기 때문에 그 자체로는 해롭지 않습니다. 이와 같은 가정을 고수 할때 충돌하는 gradient 차이는 일부 client에 대한 model 정확도에 부정적인 영향을 미칩니다. 

 

그림은 기울기의 차이에 따른 모델의 편향을 나타냅니다. 각 기울기가 차원공간에서 가리키는 방향으로 model이 업데이트 한다면 그 기울기의 합이 가리키는 방향으로 global model은 움직입니다. 다시 말해 특정 client의 global update 크기 즉 gradient가 크다면 그리고 그 합(average)가 편향된다면 global model 자체 또한 한편으로 편향될 수 있습니다. 

 

이는 global iteration이 반복됨에 따라 점진적으로 심화됩니다.

 

3. FL 공정성 보장을 위한 특징 3가지

위와 같은 이유로 인해 FL에서의 fairness는 중요한 문제 입니다. 공정성 보장을 위해 고려해야 하는 사항 중 가장 큰 3가지는 다음과 같습니다.

Heterogeneous and imbalanced data.

서로 다른 클라이언트는 각자의 local 데이터 특성을 가지므로 잠재적으로 서로 다른 데이터 분포가 있습니다. 다시말해 데이터가 non-IID 분포일 때 서로 다른 클라이언트의 기울기 차이는 더욱 커집니다. 이들은 FL에서 충돌하는 기울기에 큰 영향을 미칩니다. 또 클라이언트마다 로컬 데이터의 크기가 다를 수 있습니다. 클라이언트 전체에서 동일한 로컬 배치 크기가 사용되는 경우 더 많은 데이터가 있는 클라이언트는 로컬 모델을 교육하는 데 더 많은 step을 거쳐야 하므로 기울기 크기의 차이가 심화됩니다. 결과적으로 통신 라운드에서 선택된 사용자는 이와 같은 이질성으로인해 서로 충돌할 수 있으며 (gradient summation section) 일부에 대한 불공평한 업데이트가 발생할 수 있습니다. 이러한 충돌을 internal conflict 라고 합니다.

 

 

Party selection.

각 통신 라운드에서 서버는 클라이언트의 하위 집합을 임의로 선택하여 로컬 데이터 세트로 글로벌 모델을 훈련합니다. 각 라운드의 데이터 분포가 실제 모집단 분포를 대표한다는 보장은 없습니다. 데이터 분포는 서버가 특정 클라이언트를 반복적으로 선택할 때 매우 불균형할 수 있습니다. 예를 들어 컴퓨팅 성능, 대기 시간, 배터리 등에 기반한 샘플링 전략으로 인해 그래디언트의 평균이 반복적으로 선택된 클라이언트에 의해 global model은 편향될 수 있습니다. 이를 external conflict라고 합니다. 

 

Client dropping out

external conflict의 또 다른 원인은 네트워크 연결해제 입니다. 네트워크 중단(또는 기타 하드웨어 문제)으로 인해 클라이언트가 중단되면 그 규모는 0으로 간주됩니다. 이는 global update에서 모수를 줄이므로 특정 client 에 대한 편향을 심화 합니다.

 

 

4. FedFV(Federated Fair aVeraging)

3 과같은 공정성의 문제를 해결하기 위해 저자들은 FedFV알고리즘을 제안하여 전송된 gradient를 averaging하기 전에 클라이언트간 충돌을 완화합니다. 

 

먼저 코사인 유사도를 통해 gradient conflict를 감지한 다음 gradient의 방향과 크기를 수정하는 과정의 반복을 통해 충돌의 영향을 완화 합니다. 

FedFV는 가중 집계 이전에 클라이언트간 충돌을 완화하는 것을 목표로 합니다. FedFV의 t 번째 global iteration을 가정할때 임의의 참여 client의 가중치와 그 loss를 수신합니다. 그리고 각 client의 손실을 오름차순으로 정렬해서 해당 client의 PO_T를 얻습니다. 그리고 반복적으로 conflict를 제거 합니다. 

 

위에서 언급한 바와 같이 internal conflict는 client간의 fairness를 저해 합니다. 예를들어 이진분류기 문제에서 하나의 class가 다수번 입력되는 경우에 서로 다른 class 간에 일어나는 internal conflict는 global model의 선호를 특정 class로 bias 합니다. 

 

 

Internal Conflict

이 경우 다른 class에 대한 정확도의 희생이 공평성을 등한시한 결과로 이어지게 됩니다. 또한 두 클래스의 client 비율이 균형이 있음에도 불구하고 각 client의 데이터 크기가 상이 하기 때문에 여전히 internal conflict가 발생할 수 있습니다. 

내부 충돌을 해결하기 위해 FedFV는 충돌하는 기울기가 있는 다른 클라이언트의 법선 평면에 클라이언트의 기울기를 반복적으로 투영합니다. 임의의 순서로 투영하는 대신 Theorem 1을 기반으로 다른 그래디언트의 투영 대상이 되는 그래디언트를 결정하기 위해 손실 기반 순서를 설계합니다. 후에 클라이언트의 그래디언트가 투영 대상으로 사용되면 FedFV에서 계산한 최종 평균 기울기와의 충돌이 줄어듭니다. 

External Conflict

 

FL에서 각 통신 라운드 동안 샘플링과정에서의 편향이 있을 수 있습니다.

 

t번째 라운드에서 선택되지 않은 클라이언트는 업데이트 gt가 임의의 기울기 gt2와 충돌할 때마다 모델에서 배제될 위험이 있습니다.

이는 또다른 형태의 공정성 문제를 야기 합니다. 

저자들은 이러한 클라이언트가 각 라운드에서 가중치가 0인 것으로 간주할 수 있습니다. (배제 되었으므로) 그러나 실제 훈련된 기울기에 액세스할 수 없기 때문에 이러한 클라이언트에 대한 conflict를 찾는것은 어려운 문제 입니다. 이 문제를 해결하기 위해 최근 기울기에 따라 실제 기울기를 추정합니다. 이를 External Conflict라고 합니다. 

 

5. Experiment Result