Blog.

Federated Averaging Optimizer | Federated Learning


Autore
Andrea Provino
Data
Tempo di lettura
4 minuti
Categoria
machine-learning, Privacy Preserving

federated-averaging-optimizer-federated-learning-privacy-preserving-deep-learning-machine-learning-data-science-machine-learning

Il Federated Averaging è il più popolare federated optimizer per risolvere problemi di federated learning.

Evidentemente è tutto chiaro e la definizione non necessita di ulteriori spiegazioni.

Direi quindi che possiamo concludere qui il post.

Ci sei ancora?

Benissimo!

Ora che abbiamo allontanato le persone pigre, ecco che siamo rimasti solo io e te: preparati per questa avventura alla scoperta del federated averaging!

A cosa serve il federated averaging ?

Per capire questa domanda, e dunque intuitivamente il ruolo giocato dall’algoritmo, ripassiamo sinteticamente alcuni concetti chiave.

Sappiamo che il federated learning consente l’allenamento di un modello su un dataset distribuito, eliminando i problemi legati alla presenza di dati sensibili in un unico centro.

In questo modo entriamo nell’affascinante mondo del privacy preserving machine learning (PPML), tutelando la privacy dei dati degli utenti coinvolti e garantendo al contempo il conseguimento dell’obiettivo: la creazione di un modello.

Devi sapere però una cosa fondamentale.

Questo nuovo approccio, che elimina il single point of failure rappresentato dall’esistenza di un centralized dataset (suscettibile ad attacchi mirati e pericolosi), presenta diverse difficoltà.

Una di queste è rappresentata dall’algoritmo di ottimizzazione scelto.

In un tipico sistema di machine learning, un algoritmo di ottimizzazione, quale può essere lo Stochastic Gradient Descent (SGD), sovente usato nelle sue varianti, opera su un grande dataset partizionato omogeneamente.

Questo algoritmo, come altri della sua categoria, è altamente iterativo e richiede bassa latenza nonché elevate larghezze di banda.

Non proprio le condizioni presenti in un sistema di federated learning, che al contrario si appoggia a una moltitudine di device (e.g. smartphone) dalle prestazioni ridotte e con limitazioni di connessione (i.e. larghezza di banda, costo, intermittenza del collegamento).

Le limitazioni di latenza e larghezza di banda hanno portato Google a sviluppare nel 2017 un nuovo approccio chiamato Federated Averaging e presentato in questo articolo accademico.

Come funziona l’algoritmo

Molto semplicemente, il federated averaging (FedAvg) combina il calcolo locale dello stochastic gradient descent (SGD), affidato dunque ai singoli client, con la determinazione del loro valore medio, gestito invece dal server centrale (performs model averaging).

Questo sistema si dimostra robusto persino alle distribuzioni sbilanciate (unbalanced distribution) e non-IDD (che vederemo prossimamente), riducendo il numero di comunicazioni necessarie al training di una rete neurale su dataset decentralizzati di diversi ordini di magnitudine.

Seguimi in questi ultimi passaggi.

Esaminiamo più tecnicamente il funzionamento del federated averaging algorithm.

Definiamo un server di coordinamento (coordinating server) per l’orchestrazione dei federated averaging rounds (cicli di media federati) tra i fornitori di dati partecipanti (data furnischers, e più in generale participating data controllers).

Gli step dell’algoritmo sono dunqe i seguenti:

  1. Il server di coordinamento, che definiamo coordinator, inizializza un modello.
  2. Il coordinator seleziona casualmente un sottoinsieme dei data-holders che definiamo runners, per iniziare un ciclo di allenamento.
  3. Il coordinator invia dunque il modello globale ai runners selezionati
  4. I runners ricevono il modello globale, e procedono a ottimizzarne i parametri localmente prima d’inviarlo nuovamente al coordinatore.
  5. Il coordinator esegue ora la media dei parametri di ogni modello ricevuto dai runners nel singolo ciclo di allenamento.
  6. Gli step da 2 a 5 sono ripetuti sino al conseguimento di un requisito (e.g. numero massimo di rounds raggiunto, convergenza del modello, early stopping etc.)

FedSGD vs FedAvg

Ti faccio inoltre notare che il metodo di cui sopra costituisce di fatto una generalizzazione di un approccio simile noto come Federated Stochastic Gradient Descent (FedSGD), delineato in questo articolo accademico.

Infatti, nel caso del FedSGD i gradienti del modello sono mediati a ogni singolo ciclo, aumentando la frequenza di comunicazione tra coordinators e runners richiesta per il conseguimento della convergenza.

Al contrario il FedAvg richiede un numero minimo di epoche prima del calcolo della media, con notevoli risparmi in termini computazionali.

In base al principio “small communication, large computation possiamo dire che il FedAvg è particolarmente CPU-bound (i.e. le prestazioni aumentano proporzionalmente alla velocità di calcolo), contrariamente al FedSGD di tipo IO-bound (con rendimento maggiore in presenza di connessione migliore per trasferimento dati).

In uno schema cross-device, l’idea è quindi sfruttare i relativamente potenti processori degli smartphone per calcolare updates di alta qualità, anziché limitarsi ai singoli step del gradiente,

La fase di training richiede dunque meno comunicazione, poiché sono necessarie iterazioni minori, grazie ad aggiornamenti di più alta qualità.

Questi guadagni, uniti ad algoritmi di compressione degli updates, per limitare il flusso di upload, consentono lo sviluppo di modelli di buona qualità.

non-IIDness

Un’ultima cosa prima di salutarti.

Prima abbiamo accennato al fatto che il FedAvg sia CPU-bound.

Questo vantaggio agevola lo scaling dell’algoritmo su dataset di grandi volumi, ma ha un difetto.

Il modello locale può potenzialmente divergere tra diversi rounds, finendo per andare in over-fitting sul dataset locale.

Si delinea quindi un compromesso tra il numero di training epochs locali e i federated averaging training rounds.

La chiave di volta è rappresentata dal Non-independently and identically distributed data, abbreviato in Non-IIDness.

Copriremo questo concetto nel prossimo post.

Federated Averaging con Tensorflow

Utilizzando il core layer Federated Core (FC) di Tensorflow abbiamo la possibilità di andare a realizzare sistemi di federated learning.

Possiamo inoltre sfruttare il FC Layer per implementare algoritmi federati custom, come il Fedearated Averaging.

Studieremo le applicazioni pratiche, a livello di codice, di questi concetti prossimamente.

Per il momento è tutto!

Un caldo abbraccio, Andrea.

Taggeddifferential privacyprivacy preserving machine learningteoria


Ultimi post

Patricia Merkle Trie

Il Practical Algorithm To Retrieve Information Coded In Alphanumeric Merkle Trie, o Patricia Merkle Trie è una struttura dati chiave-valore usatada Ethereum e particolarmente efficiente per il salvataggio e la verifica dell’integrità dell’informazione. In questo post ne studieremo le caratteristiche. Prima di procedere, ci conviene ripassare l’introduzione al Merkle Tree nella quale abbiamo chiarito il […]

Andrea Provino
ethereum-patricia-merkle-tree
Tree Data Structure: cos’è un Merkle Tree

Un Merkle Tree è una struttura dati efficiente per verificare che un dato appartenga a un insieme esteso di elementi. È comunemente impiegato nelle Peer to Peer network in cui la generazione efficiente di prove (proof) contribuisce alla scalabilità della rete. Capire i vantaggi di questa struttura ci tornerà utile nel nostro percorso di esplorazione […]

Andrea Provino
merkle-tree-cover
UTXO: come funziona il modello Unspent Transaction Outputs

Per tenere traccia dei bilanci utente, la blockchain di Bitcoin sfrutta un modello di contabilità definito UTXO o Unspent Transaction Outputs. In questo articolo ne esaminiamo le caratteristiche. Ogni blockchain è dotata di un sistema di contabilità, un meccanismo attraverso cui tenere traccia dei bilanci di ciascun utente. I due grandi modelli di riferimento nel […]

Andrea Provino
bitcoin-utxo
Cos’è Ethereum

Possiamo definire Ethereum come una macchina a stati distribuita che traccia le transizioni di un archivio dati general-purpose (i.e. una memoria in grado di registrare qualsiasi dato esprimibile come coppia di chiave e valore o key-value) all’interno della Ethereum Blockchain. È arrivato il momento di esplorare uno dei progetti tecnologici più innovativi e interessanti degli […]

Andrea Provino
ethereum