State-Space ModelsModelli a spazio di stato

A linear system \(x'(t) = A\,x(t) + B\,u(t)\), \(y(t) = C\,x(t)\), sampled with step \(\Delta\) while the input is held constant between samples, becomes the recurrence \(x_k = \bar A\,x_{k-1} + \bar B\,u_k\), and the recurrence, unrolled, is the convolution of the input with the kernel \(\bar K = (C\bar B, C\bar A\bar B, C\bar A^2\bar B, \dots)\); S4 and its successors train such a layer as a convolution, which is parallel over the sequence, and run it as a recurrence, which costs one step per token. The first part computes the same model in both ways, the second shows the matrix \(A\) of HiPPO, whose state is a compressed memory of the whole past input, and the third lets \(\Delta\), \(B\) and \(C\) depend on the token, as in Mamba, which allows the model to decide what to write and what to forget (a choice that a convolution with a fixed kernel cannot make).

Un sistema lineare \(x'(t) = A\,x(t) + B\,u(t)\), \(y(t) = C\,x(t)\), campionato con passo \(\Delta\) tenendo l'ingresso costante fra un campione e l'altro, diventa la ricorrenza \(x_k = \bar A\,x_{k-1} + \bar B\,u_k\), e la ricorrenza, srotolata, è la convoluzione dell'ingresso con il nucleo \(\bar K = (C\bar B, C\bar A\bar B, C\bar A^2\bar B, \dots)\); S4 e i suoi successori addestrano uno strato di questo tipo come una convoluzione, che è parallela lungo la sequenza, e lo eseguono come una ricorrenza, che costa un passo per token. La prima parte calcola lo stesso modello nei due modi, la seconda mostra la matrice \(A\) di HiPPO, il cui stato è una memoria compressa di tutto l'ingresso passato, e la terza fa dipendere \(\Delta\), \(B\) e \(C\) dal token, come in Mamba, il che permette al modello di decidere che cosa scrivere e che cosa dimenticare (una scelta che una convoluzione con un nucleo fisso non può fare).

1. Recurrence and convolution1. Ricorrenza e convoluzione

The matrix \(A\) is diagonal, as in S4D, with complex poles \(\lambda_n\) in conjugate pairs and \(B = C = 1\), and therefore every pair adds to the output a damped oscillation; the zero-order hold gives \(\bar A = e^{\Delta\lambda}\) and \(\bar B = (e^{\Delta\lambda} - 1)/\lambda\), which maps the left half-plane into the unit disc. Drag a pole in either plane, or move \(\Delta\): a small step leaves the poles near 1 and the kernel long and slow, a large one shrinks them toward 0 and folds the oscillations beyond \(\pi/\Delta\) back onto slower ones.

La matrice \(A\) è diagonale, come in S4D, con poli complessi \(\lambda_n\) in coppie coniugate e \(B = C = 1\), e quindi ogni coppia aggiunge all'uscita un'oscillazione smorzata; il mantenimento di ordine zero dà \(\bar A = e^{\Delta\lambda}\) e \(\bar B = (e^{\Delta\lambda} - 1)/\lambda\), che manda il semipiano sinistro nel disco unitario. Trascina un polo in uno dei due piani, o muovi \(\Delta\): un passo piccolo lascia i poli vicino a 1 e il nucleo lungo e lento, uno grande li stringe verso 0 e ripiega le oscillazioni oltre \(\pi/\Delta\) su altre più lente.

The poles \(\lambda_n\) of the continuous system (left, the dashed line is \(|\mathrm{Im}\,\lambda| = \pi/\Delta\)) and their images \(\bar A_n = e^{\Delta\lambda_n}\) in the unit disc (right); the conjugates, fainter, follow.I poli \(\lambda_n\) del sistema continuo (a sinistra, la linea tratteggiata è \(|\mathrm{Im}\,\lambda| = \pi/\Delta\)) e le loro immagini \(\bar A_n = e^{\Delta\lambda_n}\) nel disco unitario (a destra); i coniugati, più tenui, seguono.
The kernel \(\bar K_j = \sum_n 2\,\mathrm{Re}\,(\bar A_n^{\,j}\bar B_n)\), which is also the output of the model to an impulse; in gold the contribution of each pair.Il nucleo \(\bar K_j = \sum_n 2\,\mathrm{Re}\,(\bar A_n^{\,j}\bar B_n)\), che è anche l'uscita del modello a un impulso; in oro il contributo di ciascuna coppia.

\(x_k = \bar A\,x_{k-1} + \bar B\,u_k,\quad y_k = C\,x_k\)\(y_k = \sum_{j \le k} \bar K_{k-j}\,u_j\)

The recurrent scan: the input, the state of every pair as a point of the complex plane (each step turns it by \(\arg \bar A_n\), shrinks it by \(|\bar A_n|\) and adds \(\bar B_n u_k\)) and the output, built one step at a time.La scansione ricorrente: l'ingresso, lo stato di ogni coppia come punto del piano complesso (ogni passo lo ruota di \(\arg \bar A_n\), lo riduce di \(|\bar A_n|\) e aggiunge \(\bar B_n u_k\)) e l'uscita, costruita un passo alla volta.
The convolution: the kernel, reversed, slides under the input so that \(\bar K_{k-j}\) sits under \(u_j\); the products, summed, give \(y_k\) without any state.La convoluzione: il nucleo, rovesciato, scorre sotto l'ingresso così che \(\bar K_{k-j}\) stia sotto \(u_j\); i prodotti, sommati, danno \(y_k\) senza alcuno stato.

2. HiPPO: the state as a memory2. HiPPO: lo stato come memoria

With the HiPPO-LegS matrix, \(A_{nk} = \sqrt{2n+1}\sqrt{2k+1}\) below the diagonal, \(A_{nn} = n+1\) and \(B_n = \sqrt{2n+1}\), the system \(x'(t) = -\tfrac1t A\,x(t) + \tfrac1t B\,u(t)\) keeps in its \(N\) numbers the coefficients of the best approximation of the whole input seen so far by polynomials of degree below \(N\); hence, the past is read back as \(u(s) \approx \sum_n x_n(t)\sqrt{2n+1}\,P_n(2s/t - 1)\) for \(0 \le s \le t\). You can draw the input with the mouse; as \(t\) grows the same \(N\) numbers cover a longer past, and the detail of the remote input is lost first. S4 starts from this \(A\) with a fixed step in place of \(1/t\), and therefore its memory of the remote input fades over a time scale set by the step.

Con la matrice HiPPO-LegS, \(A_{nk} = \sqrt{2n+1}\sqrt{2k+1}\) sotto la diagonale, \(A_{nn} = n+1\) e \(B_n = \sqrt{2n+1}\), il sistema \(x'(t) = -\tfrac1t A\,x(t) + \tfrac1t B\,u(t)\) tiene nei suoi \(N\) numeri i coefficienti della migliore approssimazione di tutto l'ingresso visto finora con polinomi di grado minore di \(N\); il passato si rilegge quindi come \(u(s) \approx \sum_n x_n(t)\sqrt{2n+1}\,P_n(2s/t - 1)\) per \(0 \le s \le t\). Puoi disegnare l'ingresso con il mouse; al crescere di \(t\) gli stessi \(N\) numeri coprono un passato più lungo, e il dettaglio dell'ingresso lontano si perde per primo. S4 parte da questa \(A\) con un passo fisso al posto di \(1/t\), e quindi la sua memoria dell'ingresso lontano svanisce su una scala di tempo fissata dal passo.

The input \(u\) over \([0, 1]\) (fainter after \(t\), not yet read), and in violet the past read back from the \(N\) numbers of the state at time \(t\); the error of the reconstruction is given below.L'ingresso \(u\) su \([0, 1]\) (più tenue dopo \(t\), non ancora letto), e in viola il passato riletto dagli \(N\) numeri dello stato al tempo \(t\); l'errore della ricostruzione è dato sotto.

The state \(x(t)\), one bar per Legendre coefficient.Lo stato \(x(t)\), una barra per coefficiente di Legendre.
The first basis functions \(\sqrt{2n+1}\,P_n(2s/t-1)\) on \([0, t]\): they stretch with \(t\), and therefore the state keeps the whole past, with less and less detail on its oldest part.Le prime funzioni di base \(\sqrt{2n+1}\,P_n(2s/t-1)\) su \([0, t]\): si allungano con \(t\), e quindi lo stato tiene tutto il passato, con sempre meno dettaglio sulla sua parte più vecchia.

3. Selectivity3. Selettività

The task: a random sequence of the colors A, B, C, D holds one marker \(\star\), and at the end the model must name the color that came right after the marker. Two one-layer models with \(D\) channels of \(N\) real diagonal states each are trained side by side with Adam on the same minibatches; both read \(x_k\), a mix of the token and of the one before it, and in the selective one \(\Delta_k = \mathrm{softplus}(W_\Delta x_k + b_\Delta)\), \(B_k = W_B x_k + b_B\) and \(C_k = W_C x_k + b_C\) depend on it, while in the time-invariant one only the biases are there. The selective model learns a large \(\Delta\) after the marker, which sets \(\bar A = e^{\Delta A}\) near 0 and \(\bar B\) large (the state is reset and the token written), and a small one elsewhere, which sets \(\bar A\) near 1 and \(\bar B\) near 0 (the state is kept and the token ignored); the time-invariant model is a fixed convolution followed by a linear readout, and therefore its answer is a sum of terms each of which depends on a single position; at most, it can learn that the answer is often the color seen most often (about 40% of the sequences at \(L = 16\), against the 25% of chance).

Il compito: una sequenza casuale dei colori A, B, C, D contiene un marcatore \(\star\), e alla fine il modello deve dire il colore venuto subito dopo il marcatore. Due modelli di uno strato, con \(D\) canali di \(N\) stati reali diagonali ciascuno, sono addestrati fianco a fianco con Adam sugli stessi minibatch; entrambi leggono \(x_k\), una combinazione del token e di quello precedente, e in quello selettivo \(\Delta_k = \mathrm{softplus}(W_\Delta x_k + b_\Delta)\), \(B_k = W_B x_k + b_B\) e \(C_k = W_C x_k + b_C\) ne dipendono, mentre in quello tempo-invariante ci sono solo i bias. Il modello selettivo impara un \(\Delta\) grande dopo il marcatore, che porta \(\bar A = e^{\Delta A}\) vicino a 0 e \(\bar B\) grande (lo stato si azzera e il token si scrive), e uno piccolo altrove, che porta \(\bar A\) vicino a 1 e \(\bar B\) vicino a 0 (lo stato si conserva e il token si ignora); il modello tempo-invariante è una convoluzione fissa seguita da una lettura lineare, e quindi la sua risposta è una somma di termini ciascuno dei quali dipende da una sola posizione; al più, può imparare che la risposta è spesso il colore visto più spesso (circa il 40% delle sequenze con \(L = 16\), contro il 25% del caso).

A test sequence and, under each token, the step \(\Delta_k\) of the two models (one bar per channel, log scale; violet the selective model, gold the time-invariant one) and how much of what the token wrote is still in the state at the end, \(\bar B_k \prod_{j>k} \bar A_j\), relative to the largest; then the probabilities of the four answers. Click the sequence for another one.Una sequenza di test e, sotto ogni token, il passo \(\Delta_k\) dei due modelli (una barra per canale, scala logaritmica; in viola il modello selettivo, in oro quello tempo-invariante) e quanto di ciò che il token ha scritto è ancora nello stato alla fine, \(\bar B_k \prod_{j>k} \bar A_j\), relativo al massimo; poi le probabilità delle quattro risposte. Clicca la sequenza per vederne un'altra.
The accuracy of the two models on 256 test sequences; the dashed line is chance, 25%.L'accuratezza dei due modelli su 256 sequenze di test; la linea tratteggiata è il caso, 25%.
Their loss (cross-entropy on the same sequences); the dashed line is \(\ln 4\), the loss of the uniform guess.La loro loss (entropia incrociata sulle stesse sequenze); la linea tratteggiata è \(\ln 4\), la loss della risposta uniforme.