Abstract

최근의 mobile 기기는 learning model에 적합한 많은 데이터에 접근할 수 있다. 하지만, 이러한 data는 종종 privacy에 민감하고 양이 너무 방대하여 기존의 방식과 같이 data center에 접근하여 학습하는 것은 어려울 수 있다.

따라서, 본 논문에서는 각 mobile device에 있는 training data를 이용, local에서 계산된 update를 취합해 공유 모델을 학습하는 decentralized approach인 Federated Learning 을 제안한다.

논문은 실험을 통해 이러한 접근이 unbalanced, non-IID data 분포에 대해 robust함을 보였다. 또한, 주된 cost로 뽑히는 communication costs에 대해, 기존의 동기화된 stochastic gradient descent(SGD) 방식보다 논문의 방식이 10배에서 100배 정도 communication round를 덜 거친다는 것을 보였다.

Introduction

점점 더 많은 사람들에게 핸드폰과 태블릿은 주요한 계산 장치이고, 그러한 장치 안에 있는 여러 센서들(카메라, GPS 등)은 비공개로 제공되는 많은 data에 접근할 수 있다. 해당 data를 기반으로 학습한 모델은 보다 지능적인 application을 작동시켜 사용성을 크게 향상시킬 수 있다는 가능성을 가지고 있지만, 중앙 location에 이를 저장하는 것에는 risk가 존재한다.

우리는 풍부한 data를 중앙에 저장하지 않고도, 공유된 모델을 학습시킬 수 있는 기술인 Federated Learning 기법을 소개한다. 이러한 이름이 붙은 이유는 중앙 server 에 의해 조절되는 여러대의 device(여기서는 client 라고도 한다)의 loose한 federation으로 학습 task가 진행되기 때문이다.

각 client는 절대 server로 upload 되지 않는 local training dataset을 가진다. 대신 각 client는 update 값을 계산하여 오직 그 값만, server에 의해 유지되는 global model에 전달한다. (direct application of the principle of focused collection) Update 값은 model을 개선시키는 것에 특화되어 있기 때문에 한번 적용되면 이를 저장할 이유가 없다.

논문에서 제시하는 main contribution은 다음과 같다.

1. Mobile 장치로부터 받아오는 decentralized data를 사용하는 training의 문제점 확인
2. 위와 같은 setting에 적용할 수 있는 straightforward, practical 알고리즘의 선택
3. 제안된 방식에 대한 경험적인 평가

더 자세히 말하자면 논문에서는 model averaging을 수행하는 server와 local SGD를 수행하는 각 client를 결합한 FederateAveraging 알고리즘을 소개한다. 또한 실험을 통해 해당 알고리즘이 unbalanced, non-IID data 분포에 대해 강인하고, 학습에 필요한 communication round를 줄일 수 있다는 것을 보였다.

Federated Learning

Federated learning의 ideal problems는 다음의 속성들을 가지고 있다.

1. 일반적으로 data center에서 이용 가능한 proxy data에서의 학습보다 mobile devices으로부터 받은 real-world data 기반 학습이 훨씬 명확한 장점을 가지고 있다.
2. Data가 privacy에 민감하고, model의 size보다 크기 때문에 이를 model training의 목적으로 data center에 기록하는 것은 좋지 않다.
3. Supervised task들에 대해 data의 label은 사용자 간 interaction에서 추정할 수 있다.

위의 조건을 만족하는 예로 논문에서는 2가지 예를 들었다; Image classification, Language models (근거는 논문에 자세히 명시되어 있음)

Privacy

Federated learning에서는 특정 model을 개선시키기 위한 minimal update(필수 정보)만이 전송된다. 이때, 업데이트가 단시간에 이루어진다는 점(그래야 하기도 하다)과 raw data에 비해 많은 정보를 가지고 있지 않다는 것이 특징이다.

Federated Optimization

논문에서는 Federated learning에서의 optimization problem을 federated optimization이라고 부르고, distributed optimization과의 연결(및 대조)를 유도한다. Federated optimization은 기존의 distributed optimization problem과 비교하여 다음의 특징들을 가진다.

• Non-IID
  Client의 training data는 각 user의 mobile device 사용을 기반으로 하기 때문에, 어떠한 user의 local dataset도 모집단을 대표할 수 없다.

• Unbalanced
  몇몇 user는 다른 이들보다 service나 app을 훨씬 많이 사용할 것이기 때문에 local training data의 양이 달라질 수 있다.

• Massively distributed
  Client 당 평균 example의 수 보다 optimization에 참여하는 client의 수가 더 많을 것을 기대한다.

• Limited communication
  Mobile device들은 보통 offline 상태이며 느리고 비싼 connection을 가진다.

논문에서 강조하는 optimization property는 Non-IID 와 Unbalanced 이다. (이는 communication constraints와도 부합)

물론, 배포된 federated optimization system은 수많은 현실적 문제를 해결해야 하지만 이는 논문의 범위에서 벗어난 issue이므로, 실험에 적절한 통제된 환경을 사용한다 하자. (하지만 client availability와 unbalanced & non-IID data issue를 해결)

여기서 동기화된 update scheme은 communication round에 진행된다고 가정한다.

보다 자세히 설명하면, 고정된 local dataset을 가진 $k$ 명의 고정된 clients set이 존재한다. 각 round의 시작에서 random한 비율 $C$ 만큼의 clients가 선택되고, server는 현재의 global algorithm state(예를 들어, model parameters)를 각 client에게 전송한다. 전체 clients 중 일부만 선택하는 이유는 효율성 때문인데, 논문의 실험에서 특정 값 이상의 clients를 추가하면 오히려 return을 줄인다는 사실이 드러났기 때문이다. 선택된 각 client들은 local dataset을 기반으로 global state에 대한 local computation을 수행하여, update 값을 server에 전송한다. 이후 server는 그러한 update들을 global state에 적용하는 식으로 process가 반복된다.

비록 우리는 non-convex neural network objectives에 집중하고 있지만, 우리가 생각하고 있는 알고리즘은 다음의 어떠한 finite-sum objective form에도 적용할 수 있다.

Machine learning problem에 대해 보통 $f_i(w)=l(x_i, y_i;w)$라고 잡는다. 이때, $l(x_i, y_i;w)$는 model parameter $w$로 만들어진 example $(x_i,y_i)$에 대한 prediction loss를 의미한다.

우리는 data가 $K$명의 client들에게 분산되어 있음을 가정하고, $\mathcal{P}_k$ 는 client $k$의 data point index 집합이며 $n_k = |\mathcal{P}_k|$ 이다. 이때 우리는 위의 식을 아래와 같이 표현할 수 있다.

만약 partition $P_k$가 training example들을 clients에 대해 uniformly random하게 분배하는 식으로 구성되었다고 하면 $\mathbb{E}_{\mathcal{P}_k} [F_k(w)] = f(w)$ 이고, 이는 fixed client $k$ 에 할당된 example set에 대한 기대값이다. 이러한 IID 가정은 보통 distributed optimization 알고리즘에 사용되는데 우리는 이와 달리 non-IID setting을 가정한다.

Data center optimization과 달리 federated optimization에서는 communication costs가 지배적이다. 따라서 upload bandwidth는 $1 \textrm{MB/sec}$ 이하로 제한한다. 또한 clients는 충전되고 있거나 unmetered wi-fi connection 등의 상태에서만 optimization에 참여할 것이다. (장치를 안쓸때 학습한다는 의미인듯) 이에 더해, 각 client가 하루 당 적은 수의 update rounds에만 참여한다고 기대한다.

상대적으로 single device의 dataset은 작고, 요즘 핸드폰에는 상대적으로 빠른 processor들이 탑재되어 있기 때문에 우리는 추가적인 computation을 사용하여 model을 학습하는데 필요한 communication round의 총 횟수를 줄이는 것을 목적으로 둔다.

Computation을 추가하는 방법에는 크게 다음의 두 가지가 있는데 하나는 increased parallelism, 다른 하나는 increased computation on each client 이다. 첫 번째 방식은 각 communication round 사이에 독립적으로 작동하는 clients를 더 사용하는 것이고, 두 번째는 각 client가 gradient calculation보다 더 복잡한 연산을 진행하는 것이다. 이러한 두 가지 접근법을 조사했지만, 논문에서 얻은 speed up은 각 client에게 더 많은 연산을 추가하여 얻은 것이다.

Related Work

해당 파트는 논문을 직접 참고하도록 하자.

Reference

McMahan, Brendan, et al. "Communication-efficient learning of deep networks from decentralized data." Artificial intelligence and statistics. PMLR, 2017.