Федеративное обучение и честные модели

В федеративном обучении строки остаются у клиентов, а сервер объединяет обновления модели. Это уменьшает передачу сырых данных, но не создаёт приватность автоматически. Неодинаковые клиенты превращают простое среднее в содержательный выбор цели: «средняя строка» и «средний человек» — разные задачи, и побеждают в них разные модели.

Клавиатура учится на телефонах

Модель следующего слова должна учитывать реальные пользовательские тексты, которые нельзя собирать в одну центральную таблицу без серьёзного риска. Федеративная схема отправляет текущие веса на выбранные устройства, каждое делает несколько локальных шагов, сервер агрегирует изменения. Сырые сообщения остаются на телефоне; наружу выходит только «поправка к модели».

У клиента $k$ есть данные $D_k$ объёмом $n_k$ строк и локальная функция

$$F_k(w)=\frac1{n_k}\sum_{i\in D_k}\ell_i(w).$$

Классическая цель, взвешенная по числу примеров:

$$F(w)=\sum_{k=1}^K\frac{n_k}{\sum_j n_j}\,F_k(w).$$

Она в точности равна среднему loss по всем строкам, как если бы данные были объединены в одну таблицу. Но «средний пользователь» и «средняя строка» — разные цели: активный человек с миллионом сообщений получает в первой формуле огромный вес, а редкий клиент почти не слышен.

Фраза Винера здесь буквальна: обновление модели — не сырьё и не энергия, но и не пустота. Оно несёт информацию о данных, и весь дальнейший урок — о том, сколько именно и как этим управлять.

Опыт, на котором всё видно

Чтобы не рассуждать в воздухе, возьмём тот же корпус, что и в уроке о наивном Байесе: SMS Spam Collection — $5574$ реальных сообщения, из них $747$ спама, то есть $13{,}4\,\%$. Отложим $1115$ сообщений на общий тест, оставшиеся $4459$ раздадим двадцати «телефонам».

Модель — логистическая регрессия на мешке слов, свёрнутом хеш-приёмом в $256$ координат:

$$\Pr(\text{спам}\mid x)=\sigma\!\left(w^\top\phi(x)\right), \qquad \sigma(z)=\frac1{1+e^{-z}},$$

а качество мы меряем по редкому классу — гармоническим средним точности и полноты,

$$F_1=\frac{2\,\mathrm{TP}}{2\,\mathrm{TP}+\mathrm{FP}+\mathrm{FN}},$$

потому что при доле спама $13{,}4\,\%$ голая доля верных ответов слишком снисходительна (см. урок 31).

Централизованно обученная, эта модель даёт на тесте точность $97{,}0\,\%$ и $F_1=0{,}88$ по классу «спам». Это наш потолок: столько можно выжать, если собрать все письма в одном месте. Дальше мы будем пытаться дойти до него, не собирая их.

Раздать данные можно двумя способами. Первый — перемешать и нарезать поровну: клиенты получаются статистически одинаковыми (IID). Второй — раздать так, как бывает в жизни: разного объёма и разного состава. Мы использовали для этого распределение Дирихле по каждому классу, и получилось похоже на правду: от $40$ до $1002$ строк на клиента (разброс в $25$ раз), доля спама от $0$ до $100\,\%$, причём у двух клиентов спама нет вообще ни одного.

FedAvg: раунд как единица времени

В одном раунде клиент получает общий вектор $w_t$ и выполняет $E$ локальных эпох SGD (см. урок 24):

$$w_{t,k}^{(e+1)}=w_{t,k}^{(e)}-\eta\,\nabla F_{k,B_e}\!\left(w_{t,k}^{(e)}\right), \qquad w_{t,k}^{(0)}=w_t .$$

Сервер усредняет присланные веса (эквивалентно — присланные поправки $\Delta_k=w_{t,k}-w_t$):

$$w_{t+1}=\sum_{k\in S_t}\frac{n_k}{\sum_{j\in S_t}n_j}\,w_{t,k} =w_t+\sum_{k\in S_t}\frac{n_k}{\sum_{j\in S_t}n_j}\,\Delta_k .$$

Веса внутри раунда нормируются на присутствующих, а не на всю популяцию:

$$\sum_{k\in S_t}\frac{n_k}{\sum_{j\in S_t}n_j}=1, \qquad \mathbb{E}\left[\sum_{k\in S_t}\frac{n_k}{\sum_{j\in S_t}n_j}\Delta_k\right] \ne\sum_{k=1}^{K}\frac{n_k}{\sum_j n_j}\Delta_k$$

в общем случае — уже сама выборка устройств вносит смещение. Здесь $S_t$ — множество доступных в этом раунде устройств. Ключевое наблюдение: при $E=1$ и полном батче

$$\Delta_k=-\eta\nabla F_k(w_t) \quad\Longrightarrow\quad w_{t+1}=w_t-\eta\sum_k\frac{n_k}{\sum_j n_j}\nabla F_k(w_t)=w_t-\eta\nabla F(w_t).$$

То есть один локальный шаг у всех — это ровно один обычный градиентный шаг по глобальной цели. Всё, что федеративного в FedAvg, начинается со второго локального шага: он экономит связь, но уводит клиентов в стороны их собственных данных.

Одни письма, разное расселение

Запустим FedAvg на нашем корпусе: $20$ клиентов, в каждом раунде участвует половина, $100$ раундов. Сравним IID-раздачу и перекошенную.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Три вывода читаются прямо с картинки. Первый: федеративное среднее вообще работает — на ста раундах перекошенная раздача доходит до $F_1=0{,}88$, то есть до централизованного потолка. Второй: неоднородность стоит не столько качества, сколько раундов, а раунды — это батарея, трафик и время. Третий: локальные эпохи — рычаг с двух сторон. При IID переход от $E=1$ к $E=5$ сокращает путь с шести раундов до двух; при перекошенных данных дальнейшее увеличение до $E=20$ уже вредит — двенадцать раундов вместо восьми.

Client drift: почему среднее не равно шагу

Разберём механизм на чистом модельном примере — двух квадратичных потерях с разными минимумами (числа ниже посчитаны точно, это не иллюстрация «на глаз»):

$$F_1(w)=\|w-m_1\|^2,\qquad F_2(w)=2\|w-m_2\|^2,\qquad F=\tfrac12\left(F_1+F_2\right).$$

Из общей точки каждый клиент делает $E$ шагов с $\eta=0{,}1$, сервер усредняет. Сравним результат с $E$ последовательными шагами по $F$.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Причина алгебраическая. Первый шаг линеен по градиенту, а среднее линейных функций — линейная функция среднего. Второй шаг берёт градиент уже в разных точках:

$$\nabla F_k\!\left(w_t-\eta\nabla F_k(w_t)\right) =\nabla F_k(w_t)-\eta\nabla^2F_k(w_t)\,\nabla F_k(w_t)+O(\eta^2),$$

и в поправке стоит собственный градиент клиента, а не общий $\nabla F$. Отсюда после двух шагов

$$w_{t,k}^{(2)}=w_t-2\eta\nabla F_k(w_t) +\eta^2\nabla^2F_k(w_t)\,\nabla F_k(w_t)+O(\eta^3),$$

и при усреднении по $k$ квадратичный член содержит $\overline{\nabla^2F_k\nabla F_k}$, тогда как центральный шаг дал бы $\overline{\nabla^2F_k}\cdot\overline{\nabla F_k}$ — среднее произведения против произведения средних. В среднем появляется член, зависящий от того, насколько $\nabla F_k$ отличается от $\nabla F$. Обычная мера этой разницы — дисперсия локальных градиентов:

$$\zeta^2=\frac1K\sum_{k=1}^K\left\|\nabla F_k(w)-\nabla F(w)\right\|^2 .$$

При $\zeta=0$ (одинаковые клиенты) локальные шаги бесплатны; при большом $\zeta$ каждый лишний локальный шаг покупает скорость ценой смещения.

На реальных данных разброс обновлений ведёт себя так же, как в модельном примере. При одной локальной эпохе перекошенная раздача даёт разброс $0{,}65$ против $0{,}33$ у одинаковых клиентов — в $1{,}97$ раза больше при том же алгоритме и том же корпусе. Разница целиком создана расселением данных.

Глушков и сеть, где данные остаются на месте

Мысль «считать там, где рождаются данные, а вверх передавать только сводки» старше машинного обучения. В 1962–1964 годах Виктор Михайлович Глушков, директор Института кибернетики в Киеве, разрабатывал проект ОГАС — общегосударственной автоматизированной системы, ядром которой должна была стать Единая государственная сеть вычислительных центров. Устройство сети было принципиально не «одна большая ЭВМ»: первичные данные обрабатывались на предприятиях, в районные и республиканские центры уходили агрегаты, и только они сводились дальше. Глушков прямо формулировал причину — «информационный барьер»: объём первичных сведений растёт быстрее, чем способность любого единого центра их переработать.

Для нас важна не историческая деталь, а структура аргумента, которая повторяется в федеративном обучении дословно. Централизация упирается сразу в три стены: пропускную способность каналов, скорость обработки в центре и уязвимость единого хранилища. Децентрализация снимает первые две и меняет природу третьей — вместо одного архива появляется поток агрегатов, у которого своя, куда более тонкая, теория утечек. Глушков решал первую пару задач и проектировал макроконвейерные ЭВМ для второй; вопрос приватности агрегата в полный рост встал позже, и ему посвящена вторая половина этого урока.

Лаборатория федеративного усреднения

Начните с нулевой неоднородности: все клиенты имеют почти общий минимум, локальные траектории лежат друг на друге, и число локальных эпох ни на что не влияет — это режим $\zeta\approx0$. Теперь двигайте неоднородность вверх и следите за тонкими золотыми линиями: они разлетаются, а зелёная траектория глобальной модели начинает вилять. Увеличьте $E$ до пятнадцати — локальные концы уезжают почти в свои звёзды, и среднее промахивается мимо обеих мишеней.

Дальше — самое важное. Переключите веса агрегации. Синяя мишень (оптимум «средней строки») и красная (оптимум «среднего клиента») стоят в разных местах, и алгоритм честно сходится к той, которую вы выбрали. Поднимите неравенство размеров — мишени разъедутся сильнее. Наконец, добавьте шум приватности: точка перестаёт застывать и начинает дрожать вокруг цели, а полоски справа показывают, кому от этого хуже всего.

Две законные цели: строка или клиент

Формально мы выбираем между

$$F_{\text{rec}}(w)=\sum_k\frac{n_k}{\sum_j n_j}F_k(w) \qquad\text{и}\qquad F_{\text{user}}(w)=\frac1K\sum_{k=1}^KF_k(w).$$

Обе — частные случаи одного семейства с распределением $\alpha$ на клиентах:

$$F_\alpha(w)=\sum_k\alpha_kF_k(w),\qquad \alpha_k\ge0,\ \sum_k\alpha_k=1,$$

а третьей, некооперативной, границей семейства служит худший случай

$$F_{\max}(w)=\max_{1\le k\le K}F_k(w)=\max_{\alpha}\;F_\alpha(w).$$

Первая оптимизирует случайно взятую строку, вторая — случайно взятого клиента. Разница видна на арифметике. Пусть у клиента A тысяча записей и локальный минимум $w_A=0$, у клиента B десять записей и минимум $w_B=10$ (обе потери квадратичные). Тогда

$$w_{\text{rec}}=\frac{1000\cdot0+10\cdot10}{1010}=\frac{100}{1010}\approx0{,}099, \qquad w_{\text{user}}=\frac{0+10}{2}=5.$$

Ни один ответ не ошибочен арифметически. Первый оптимизирует среднюю запись и почти игнорирует маленького клиента; второй оптимизирует среднего клиента и заметно ухудшает большинство строк A. Выбор между $0{,}099$ и $5$ — это не вопрос оптимизации, а вопрос о том, кого мы обещали обслуживать.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Обратите внимание на аккуратность формулировки. Наш эксперимент не доказывает, что равный вес клиентов всегда лучше; он показывает, что разница между целями на реальных данных может оказаться небольшой — и что узнать это можно только измерением. В модельном примере с A и B разрыв колоссален ($0{,}099$ против $5$), потому что размеры отличались в сто раз, а минимумы стояли далеко. У нас размеры отличались в двадцать пять раз, но локальные задачи были родственны: спам остаётся спамом на любом телефоне.

Персонализация и её цена

Одна глобальная модель может быть компромиссом, неудобным для всех сразу. Естественная идея: после федеративного обучения дать устройству дообучить последний слой на своей истории. Разумный компромисс между общим и личным записывается смесью

$$v_k=\beta_k\,w^{\text{glob}}+(1-\beta_k)\,w_k^{\text{loc}}, \qquad \beta_k=\frac{\lambda}{\lambda+n_k},$$

где вес личной модели растёт вместе с объёмом локальных данных. Формально мы решаем

$$\min_{v_k}\;F_k(v_k)+\frac{\lambda}{2}\|v_k-w^{\text{glob}}\|^2,$$

где штраф удерживает личную модель рядом с общей — тот же приём стягивания, что и в регуляризации.

Мы проверили это на наших клиентах: взяли глобальную модель и дали каждому одну локальную эпоху с маленьким шагом. Результат отрезвляющий. Средняя точность по клиентам сдвинулась с $0{,}970$ до $0{,}967$, худший клиент — с $0{,}921$ до $0{,}917$, а лучше или так же стало ровно у половины клиентов. Персонализация не бесплатна: у клиента мало строк, и одна эпоха способна увести модель в шум локальной выборки быстрее, чем принести пользу.

Коммуникация как ограничение

Посчитаем масштаб. Модель с $10$ млн параметров во float32 — это

$$10^7\cdot4\ \text{байт}=40\ \text{МБ}$$

на одно обновление. В общем виде объём раунда

$$B=m\cdot P\cdot b/8,$$

где $m$ — число участников, $P$ — число параметров, $b$ — бит на координату. Если в раунде участвуют $500$ устройств, вверх уходит

$$500\cdot40\ \text{МБ}=20\ \text{ГБ за раунд},$$

и это только клиент→сервер. При сотнях раундов счёт идёт на терабайты — и, что важнее, на батарею и мобильный трафик пользователей. Отсюда весь арсенал: выбор части клиентов, несколько локальных шагов, квантование, разреживание, отправка только крупных координат и error feedback, накапливающий отброшенный остаток

$$e_{t+1}=\left(\Delta_t+e_t\right)-\mathcal{Q}\!\left(\Delta_t+e_t\right),$$

чтобы невысказанная часть попала в следующий раунд, а не потерялась навсегда.

Сколько качества стоит один килобайт

Общие слова про сжатие легко проверить. Мы прогнали тот же FedAvg на реальном корпусе, применяя к каждому обновлению одно из преобразований, и измерили $F_1$ после сорока раундов.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Вывод для практики: точность отдельного числа почти не нужна — восьмикратное огрубление шкалы прошло незамеченным. А вот структура важна: у логистической регрессии на словах сигнал размазан по многим координатам, и выбрасывание мелких обнуляет как раз редкие слова, которых у отдельного клиента и так мало. Именно здесь error feedback и оправдывает себя.

Secure aggregation: сервер видит только сумму

Даже без сырых текстов отдельное обновление $\Delta_k$ — это функция личных данных. Secure aggregation позволяет серверу узнать сумму, не увидев слагаемых. Идея проста: клиенты попарно договариваются о случайных масках $s_{kj}$ так, что

$$\widetilde\Delta_k=\Delta_k+\sum_{j\ne k}\pm s_{kj}, \qquad \sum_k\widetilde\Delta_k=\sum_k\Delta_k,$$

потому что каждая маска входит в сумму дважды с противоположными знаками. Сервер видит набор равномерно случайных на вид векторов, а их сумма — ровно то, что нужно для агрегации.

Протокол должен переживать отключения: если клиент пропал после раздачи масок, его маска не погасится, и сумма испортится. Практические схемы поэтому раздают доли секретов соседям, чтобы уцелевшие могли восстановить маску выбывшего.

И, главное, secure aggregation защищает от любопытного сервера, глядящего на отдельное обновление, но не от информации в самой сумме. Если в раунде участвует один клиент, сумма равна его обновлению. Отсюда обязательное требование минимального размера группы и анализа угроз.

Differential privacy: обрезка и шум

Формальная гарантия формулируется не как «данные не передаются», а как требование к распределению результата. Механизм $\mathcal{M}$ удовлетворяет $(\varepsilon,\delta)$-дифференциальной приватности, если для любых соседних наборов $D$ и $D'$, отличающихся участием одного клиента, и любого множества исходов $A$

$$\Pr[\mathcal{M}(D)\in A]\le e^{\varepsilon}\Pr[\mathcal{M}(D')\in A]+\delta .$$

Чтобы такое обещание выполнить, нужно ограничить влияние одного клиента. Сначала обрезка нормы обновления,

$$\widetilde\Delta_k=\Delta_k\cdot\min\!\left(1,\frac{C}{\|\Delta_k\|}\right),$$

затем шум, пропорциональный этой чувствительности:

$$\bar\Delta=\frac1{m}\left(\sum_{k}\widetilde\Delta_k+\mathcal{N}\!\left(0,\sigma^2C^2I\right)\right).$$

Обрезка создаёт смещение, шум — дисперсию. Гарантия расходуется с каждым раундом: наивная композиция $T$ механизмов даёт

$$\varepsilon_{\text{total}}=T\varepsilon,$$

а более тонкий продвинутый анализ — примерно

$$\varepsilon_{\text{total}}\approx\sqrt{2T\ln(1/\delta')}\,\varepsilon+T\varepsilon(e^{\varepsilon}-1),$$

то есть бюджет растёт как $\sqrt{T}$, а не как $T$. Отсюда практический вывод: число раундов — не только вопрос трафика, но и статья расхода приватности.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Заметьте, кого обрезка задевает сильнее: клиентов с большой нормой обновления, то есть тех, чьи данные сильнее отличаются от текущей модели. Это как раз редкие сценарии и малые группы. Приватность, добытая обрезкой и шумом, слегка сглаживает именно хвост — тот самый, ради которого мы в предыдущем разделе беспокоились о худшем клиенте.

Утечки из обновлений и отравление агрегата

Градиент — не шифр. По обновлению можно узнать, встречалось ли у клиента редкое слово (для многих архитектур это видно по единственной ненулевой координате эмбеддинга), а при небольших батчах — приблизительно восстановить сам обучающий пример. Злонамеренный сервер способен пойти дальше: разослать разным клиентам разные модели и сравнить ответы, фактически проведя эксперимент над людьми.

Симметричная угроза идёт снизу. Клиенты могут отравлять агрегат: подмешивать обновление, встраивающее backdoor — «при виде такого триггера отвечай так». Робастная агрегация (медиана по координатам, усечённое среднее, отбраковка по норме) помогает, но плохо совмещается с secure aggregation: сервер, который не видит отдельных векторов, не может и отбраковать подозрительный.

Честная оценка федеративной системы

Федеративный benchmark должен сохранять естественное разбиение по клиентам и неодинаковые объёмы. Случайное перемешивание всех строк уничтожает главную трудность: получится обычное распределённое обучение, и все выводы окажутся неприменимы. Именно поэтому наборы вроде LEAF строят из данных, у которых клиент — реальная единица (автор, устройство, учреждение).

Отчёт по такой системе состоит минимум из шести чисел:

$$\underbrace{\bar q}_{\text{среднее}},\quad \underbrace{q_{0{,}1}}_{\text{нижний дециль}},\quad \underbrace{\min_k q_k}_{\text{худший клиент}},\quad \underbrace{B}_{\text{байты}},\quad \underbrace{T}_{\text{раунды}},\quad \underbrace{(\varepsilon,\delta)}_{\text{бюджет}} .$$

Сравнивать методы из уроков 61 и 62 следует при равном бюджете раундов и локальных вычислений — иначе выигрывает тот, кому дали больше связи. Разделение train/test делают по времени внутри клиента и, отдельно, по новым клиентам: это два разных сценария — продолжение личной истории и cold start.

Что решает архитектор до первой строки кода

Прежде чем запускать раунды, проект обязан назвать:

1. клиента и единицу приватности (человек, устройство, учреждение);
2. глобальную цель и веса — «по строкам» или «по клиентам»;
3. механизм выборки доступных устройств и его смещение;
4. локальный оптимизатор, число шагов $E$ и шаг $\eta$;
5. протокол агрегации и модель угроз;
6. бюджет $(\varepsilon,\delta)$, байты, раунды и качество групп;
7. сценарий нового клиента и мониторинг деградации.

Пункт третий обычно недооценивают. Устройства выходят на связь, когда заряжены и в Wi-Fi, то есть ночью и в богатых сетях: выборка клиентов систематически смещена, и это ровно та проблема отбора, о которой шла речь в уроке 57. Заявленная цель «средний клиент» превращается в «средний клиент, который часто бывает онлайн» — и никакая формула агрегации этого не исправит.

Что уезжает с телефона

Федеративное обучение полезно там, где централизация данных неприемлема, а распределённое вычисление реально доступно. Оно начинается с невинной формулы среднего, но каждое слово в ней оказывается решением: чьи данные, с каким весом, за сколько раундов, под какой маской и с каким шумом. Наш маленький опыт на пяти с половиной тысячах реальных сообщений показал всё сразу: федеративное среднее догоняет централизованный потолок $F_1=0{,}88$; перекос данных стоит втрое больше раундов; локальные эпохи разгоняют разброс обновлений в $3{,}4$ раза; квантование до четырёх бит бесплатно, а разреживание до одного процента разрушительно; шум приватности $\sigma=1$ роняет $F_1$ с $0{,}85$ до $0{,}53$ — на треть с лишним.

Ни одно из этих чисел не следует из лозунга «сырые данные не покидают устройство». Они следуют из измерений — и именно поэтому в честном проекте рядом с обещанием приватности всегда стоит таблица её цены.

Задачи