Appunti di Multiagent Systems

Formattazione del testo

N N N Nt→∞ i=1 i=1 i=1 k∈K iN N N1 1 1 1X X X Xlim (t) = (0) = = =q q q ψ y qi i i k kN N N Nt→∞ i=1 i=1 i=1 k∈K iDi conseguenza: −11 1 1 −1 −1 −1· ·lim (t) = lim Ω (t) (t) = Ω = Ω = Ωw q q N q qi i i ZZN N Nt→∞ t→∞ ZZN.B: il fattore si annulla, pertanto non è necessario conoscere il numero1Ntotale di agenti .NC.V.D.Analogamente, possiamo risolvere problemi di regressione lineare con regolarizzazionedi Tikhonov in modo distribuito.A tale scopo, consideriamo un problema di regressione lineare con loss quadratica eregolarizzazione di Tikhonov, espresso come:K 2T 2X −= +J(w) y ψ w ρkwkk kk=1La soluzione di questo problema può essere calcolata in forma chiusa.Teorema. Il vettore dei parametri ottimo che minimizza il vettore dei◦wcosti relativo ad un problema di regressione lineare con loss quadraticaJ(w)e regolarizzazione di Tikhonov può esserecalcolato come: −1K K! !T◦ −1X X= + = (Ω +w ψ ψ ρI ψ y ρI) qk k kkk=1 k=1dove rappresenta la matrice identica di dimensione opportuna ed è unaΩImatrice invertibile. Dim:⚠️ Consideriamo la funzione di costo relativa ad un problema di regressione CAPITOLO 6. OTTIMIZZAZIONE E ADDESTRAMENTO MULTI-AGENTE 151 lineare con loss quadratica e regolarizzazione di Tikhonov: K 2T 2X −= +J(w) y ψ w ρkwkk kk=1 Calcoliamo il gradiente della funzione di costo rispetto al vettore deiJ(w)parametri w: K !∂J(w) ∂ 2T 2X −= +y ψ w ρkwkk k∂w ∂w k=1 K ∂ 2T 2X −= +y ψ w ρkwkk k∂wk=1 K T X −= 2ψ + 2ρwψ w yk kkk=1 K K !TX X−=2 +ψ ψ w ψ y ρwk k kkk=1 k=1 K K !T X X−=2 +ψ ψ ρI w ψ yk k kkk=1 k=1 −= 2 ((Ω + ρI)w q) Per trovare il valore minimo consideriamo la condizione di ottimalità di pri-mo ordine: ∂J(w) =0∂w Pertanto,Assumendo che esista l'inversa della matrice possiamo calcolare Ω, il valore minimo come: ^Ω_-2 ((Ω + = 0ρI)w q)^-1 = (Ω +w ρI) q In particolare, possiamo dimostrare che è un valore di minimo valutando il segno della matrice Hessiana (ovvero della derivata seconda): K ∑ ∂J(w) T X = 2(Ω + = 2 + 0ρI) ψ ψ ρI >k k2∂w k=1 Infatti, poiché e poiché la matrice rappresenta una somma di quadrati, allora la matrice Hessiana è sempre positiva. C.V.D. Per risolvere questo problema di regressione lineare con loss quadratica e regolarizzazione di Tikhonov in modo distribuito, possiamo utilizzare il precedente algoritmo CAPITOLO 6. OTTIMIZZAZIONE E ADDESTRAMENTO MULTI-AGENTE 152 distribuito dei minimi quadrati, modificando il passo 7 nel seguente modo: ρ(t) = Ω(t) + (t)w I q i i i N Questo garantisce di raggiungere il consenso alla soluzione ottima ◦ -1= (Ω +w ρI) q. Infatti,dall'algoritmo distribuito dei minimi quadrati abbiamo visto che: ^lim Ω (t) = Ω_i Nt→∞ ^lim (t) =q qi Nt→∞ Di conseguenza: −11 1 1ρ −1 −1· ·^lim (t) = ^lim (Ω (t) + (t) = Ω+ = (Ω +w ρI) q I q N ρI) qi i i ZZN N N Nt→∞ t→∞ ZZN. B: lo svantaggio di questa modifica è che dobbiamo conoscere il numero totale di N agenti, che rappresenta un'informazione globale. 6.2 Consenso per l'ottimizzazione e l'apprendimento distribuito Consideriamo un generico problema di ottimizzazione: K !◦ X L= arg min = arg min (y +w J(w) , ψ(x , w)) ρR(w)k kw w k=1 Come abbiamo osservato, questo problema di ottimizzazione fornisce una soluzione informa chiusa solo in alcuni casi speciali (ad esempio, nel caso di un problema di regressione lineare con loss quadratica). In generale, deve essere ricavato mediante una ◦w tecnica di ottimizzazione iterativa (come la discesa del gradiente),che ha a disposizione.

disponibili per esso. In altre parole: ρX L R(w)(w) = (y +J , ψ(x , w))i k k Nk∈K iDi conseguenza, ogni agente è in grado di calcolare il proprio gradiente parziale .∂J (w)ii ∂wN.B: ricordiamo che, in presenza del termine di regolarizzazione (cioè, quando R(w) ≠ 0),il calcolo del gradiente parziale richiede la conoscenza del numero totale di agenti∂J (w)i∂w, che costituisce un’informazione globale.NPer risolvere un problema di ottimizzazione distribuita, assegniamo un vettore di pa-rametri a ciascun agente Di conseguenza, riformuliamo il problema originale diw i.iottimizzazione non vincolata, che consiste nel minimizzare la funzione di costo comples-siva (la quale può essere scritta come la somma delle funzioni di costo parziali).J(w)Ovvero: NXmin = min (w)J(w) Jiw w i=1Pertanto, tale problema può essere riformulato in modo distribuito, minimizzando ri-spetto agli vettori dei parametri associati a ciascun agente, con

Il vincolo che taliNvettori debbano convergere per ogni coppia di agenti connessi. Ovvero:i, jNXmin (w )Ji iw ,...,w1 N i=1 per ogni ∈ N=w w i, ji jL'idea per risolvere il problema di ottimizzazione in maniera distribuita è che ciascunagente minimizzi il proprio costo parziale applicando l'algoritmo di consenso(w ),i Ji iin modo tale da garantire la condizione di sincronizzazione sul vettore dei parametri ,w icioè per ogni coppia di agenti e connessi.=w w i ji jN.B: se il grafo è connesso, allora i vincoli implicano sincronizzazione, cioè per=w wiogni agente In questo contesto, la soluzione del problema distribuito è uguale a quellai.del problema originale.A tale scopo, consideriamo il potenziale artificiale che misura il disaccordo totale dellarete, definito come: 1DIS 2X kw − k(w ) =J , ..., w α wN i j1 2 {i,j}∈ERicordiamo che, quando il grafo è connesso, l'applicazione della condizione di

La sincronizzazione per ogni coppia di agenti connessa, equivale alla minimizzazione del disaccordo totale della rete DIS(w). Di conseguenza, l'idea è quella di introdurre il termine di disaccordo totale della rete nella funzione di costo, in modo tale da far rispettare la condizione di sincronizzazione. Ovvero: N DIS(w) = Σ Σ (w_i - w_j)^2 i=1 j=1 {i,j}∈E Pertanto, l'obiettivo diventa quello di minimizzare la funzione di costo J(w): Jmin(w) = Σ Σ (w_i - w_j)^2 i=1 j=1 w,...,w1 N.B: rilassando i vincoli come descritto, trasformiamo il problema con vincoli hard in un problema non vincolato. N.B: il valore di α dovrebbe essere sufficientemente grande, in modo tale da garantire α(w_i - w_j)^2 per ogni coppia di agenti e connessi. Infatti, al crescere di α, il vincolo soft si avvicina al vincolo hard.ovvero tutti i vettori dei parametri convergono ad un valore di consenso per ogni agente. Di conseguenza, la soluzione si avvicina a quella centralizzata, che può essere ottenuta in presenza di sincronizzazione. Ogni agente può calcolare il gradiente parziale utilizzando soltanto le informazioni locali. Ovvero: i   N(w ) 1∂J , ..., w ∂   N1 2X X kw − k= (w ) +J α wk k k `2∂w ∂wi i   {k,`}∈Ek=1(w )∂J i i X −= + (w )α wi j∂w i j∈Ni Applicando un algoritmo standard di discesa del gradiente per minimizzare J (w ), ..., w N1, otteniamo il seguente algoritmo di ottimizzazione distribuita denominato Consensus-Based Distributed Gradient Descent: Algorithm 8 Consensus-Based Distributed Gradient Descent. for do each agent 1: = 1,i ..., N for do each time 2: = 0, 1,t ... Update local parameter vector as: 3: (t)w i(w (t),

(t))∂J ..., w N1−(t + 1) = (t)w w εi i ∂w i (w (t))∂J i i