A Hierarchical Sampling Framework for bounding the Generalization Error of Federated Learning

이 글은 간단한 언어와 창의적인 비유를 사용하여 해당 논문을 설명합니다.

큰 그림: 비밀을 공유하지 않고 팀을 훈련시키기

로봇이 고양이를 인식하는 법을 가르치려 한다고 상상해 보세요. 일반적인 교실에서는 인터넷에서 수천 장의 고양이 사진을 모아 로봇에게 한 번에 보여주고 학습시킵니다. 이것이 중앙집중식 학습입니다.

하지만 그 사진들이 공유하기를 원하지 않는 다른 사람들에게 속해 있다면 어떨까요? 아마도 사생활 보호 문제일 수도 있고, 모든 사진을 한 곳으로 보내기에 인터넷 연결이 너무 느릴 수도 있습니다. 이것이 **연방 학습 (Federated Learning, FL)**입니다. 사진을 보내는 대신, 로봇은 자신의 '뇌'(모델) 를 각 사람의 컴퓨터로 보냅니다. 컴퓨터는 자신의 사진으로 학습한 후 사진 자체가 아닌 뇌에 적용된 변화만 다시 보냅니다.

이 논문은 이를 **계층적 연방 학습 (Hierarchical Federated Learning, HFL)**이라고 부르는 구체적이고 복잡한 버전의 문제를 다룹니다. 사람들이 단순한 개인이 아니라 가족 나무처럼 조직되어 있다고 상상해 보세요.

• 1 단계: 전 세계 (글로벌).
• 2 단계: 국가.
• 3 단계: 도시.
• 4 단계: 동네.
• 5 단계: 개별 주택 (실제 데이터).

한 동네의 데이터는 그 동네의 다른 주택들과 유사하지만, 다른 도시의 주택과는 다릅니다. 이는 의존성의 '나무' 구조를 만듭니다. 저자들은 다음과 같은 간단한 질문에 답하고자 했습니다: 이 로봇이 실제로 이 복잡하고 나무 같은 구조에서 얼마나 잘 학습할 수 있을까?

문제: '일반화' 능력 측정하기

기계 학습에서 '일반화'란 이전에 본 적 없는 새로운 데이터에서도 잘 수행하는 능력을 의미합니다.

• 위험: 로봇이 훈련 사진에 있는 특정 고양이들을 암기한다면, 새로운 고양이를 보았을 때 실패할 수 있습니다.
• 목표: 우리는 "로봇의 새로운 데이터에 대한 성능은 훈련 데이터에 대한 성능보다 크게 나빠지지 않을 것"이라고 말하는 수학적 보장 (상한선) 을 원합니다.

이전 방법들은 간단한 수학을 사용하여 이를 측정하려 했지만, 종종 데이터의 '나무' 구조를 무시했습니다. 그들은 데이터를 무작위로 쌓인 모래 더미로 간주하여 같은 도시의 데이터가 서로 관련되어 있다는 사실을 놓쳤습니다. 이 논문은 "나무의 모양에 실제로 맞는 자를 만들어 보자"고 말합니다.

해결책: '유령' 나무와 새로운 자

저자들은 이 오차를 측정하기 위해 두 가지 주요 도구를 소개합니다.

1. '유령' 나무 (초표본 구성)

학생의 지식을 테스트한다고 상상해 보세요. 단순히 한 번의 시험을 주는 대신, 실제 시험과 거의 동일하지만 아주 작은 차이 (예: 한 문제 교체) 가 있는 '유령 시험'을 주는 것입니다.

• 저자들은 실제 데이터 나무 alongside 로 유령 나무를 구축합니다.
• '실제' 노드와 '유령' 노드 쌍을 만듭니다.
• 나무의 각 가지마다 동전을 던져 알고리즘이 실제 데이터로 학습할지 유령 데이터로 학습할지 결정합니다.
• 실제 노드를 유령 노드로 교체할 때 로봇의 뇌가 얼마나 변하는지 비교함으로써, 로봇이 특정 데이터 포인트에 얼마나 민감한지 측정할 수 있습니다. 로봇이 아주 작은 교체에도 극적으로 마음을 바꾸면 과적합 (암기) 중인 것입니다. 반면 차분하게 유지한다면 잘 학습하고 있는 것입니다.

2. '와서슈타인 거리' (탄성 자)

로봇의 '실제 뇌'와 '유령 뇌' 사이의 차이를 측정하기 위해 저자들은 **와서슈타인 거리 (Wasserstein Distance)**라는 지표를 사용합니다.

• 비유: 흙더미 (실제 뇌) 를 가지고 다른 모양의 흙더미 (유령 뇌) 와 일치하도록 옮기고 싶다고 상상해 보세요.
• 옛날 자들 (상호 정보): 이는 서로 다른 흙 알갱이의 개수를 세는 것과 같았습니다. 좋지만, 너무 엄격하거나 너무 느슨할 수 있습니다.
• 와서슈타인 자: 이는 흙을 옮기는 데 필요한 노력을 측정합니다. 데이터의 형태와 기하학적 구조를 고려합니다. "이 특정 흙 알갱이를 더미가 일치하도록 밀어내려면 얼마나 멀리 밀어야 할까?"라고 묻습니다.
• 이 자는 데이터 분포의 '형태'를 이해하므로, 특히 데이터가 제한되어 있을 때 (실수의 크기에 한계가 있을 때) 오차에 대해 더 엄격하고 정확한 추정을 제공합니다.

그들이 발견한 것

1. 더 나은 공식: 그들은 전체 나무 구조에 적용 가능한, 최대 가능 오차를 계산하는 새로운 수학적 공식을 유도했습니다. 이는 평평한 데이터뿐만 아니라 나무 구조 전체에 작동합니다.
2. 더 엄격함: 그들은 새로운 '탄성 자'( Wasserstein) 가 오차에 대해 기존 '알갱이 계수기'(조건부 상호 정보) 방법보다 더 엄격하고 정확한 한계를 제공함을 증명했습니다. 특히 실수의 크기가 제한되어 있을 때 그렇습니다.
3. 개인정보 보호의 작동: 그들은 데이터를 보호하기 위해 '노이즈'를 추가하는 경우 (차등 개인정보 보호), 그들의 공식이 여전히 작동하며 그 개인정보 보호 노이즈가 학습 정확도에 얼마나 영향을 미칠지 예측할 수 있음을 보였습니다.
4. 테스트 사례 (가우스 위치 모델): 그들은 정확한 답을 알고 있는 특정 단순 시나리오 (가우스 위치 모델) 에서 그들의 수학을 테스트했습니다.
   • 결과: 그들의 공식은 실제 답과 매우 가까웠습니다. 나무에 더 많은 층을 추가할 때 오차가 어떻게 증가하는지 올바르게 예측했지만, 나무의 깊이와 관련된 오차는 약간 과대평가했습니다.

결론

이 논문은 복잡하고 다단계인 도시를 위한 더 나은 지도를 만드는 것과 같습니다. 이전 지도들은 도시를 평평한 격자로 취급하여 길을 잃게 만들었습니다. 저자들은 고층 빌딩과 지하 터널 (계층 구조) 을 존중하는 지도를 만들었습니다.

'유령 나무'를 사용하여 민감도를 테스트하고 '와서슈타인 자'를 사용하여 거리를 측정함으로써, 그들은 연방 학습 시스템이 얼마나 잘 수행될지 예측하는 더 신뢰할 수 있는 방법을 만들었습니다. 이는 개인 데이터를 볼 필요 없이 복잡한 계층적 네트워크의 장치들 간에 훈련된 모델에 대해 엔지니어들이 얼마나 신뢰할 수 있는지 정확히 알 수 있게 도와줍니다.