L’algoritmo che non rallenta
Quando i dati aumentano, quasi tutto rallenta. Più informazioni si inseriscono in un modello, più il numero di parametri cresce, più i calcoli diventano pesanti. E in alcuni casi il tempo necessario per ottenere risultati affidabili può diventare lunghissimo. È uno dei grandi problemi dell’era dei big data: come costruire modelli sofisticati senza che il costo computazionale diventi ingestibile?
Un nuovo studio (“Scalability of Metropolis-within-Gibbs schemes for high-dimensional Bayesian models”) pubblicato sul Journal of the Royal Statistical Society: Series B affronta esattamente questa sfida. Gli autori, Giacomo Zanella (Dipartimento di Scienze delle Decisioni e BIDSA, Bocconi), Filippo Ascolani (Duke University) e Gareth O. Roberts (University of Warwick), dimostrano che, in molti casi rilevanti, esiste un modo per far crescere la complessità del modello senza pagare un prezzo crescente in termini di tempo di calcolo. Oggetto della ricerca è un algoritmo chiamato Metropolis-within-Gibbs, uno strumento molto usato nell’inferenza bayesiana.
Il problema dei modelli gerarchici
In economia, sanità, marketing e scienze sociali si utilizzano spesso modelli gerarchici. Sono modelli che organizzano i dati in gruppi: per esempio pazienti distribuiti tra diversi ospedali, studenti in scuole diverse, clienti in mercati differenti. Ogni gruppo ha caratteristiche proprie, ma condivide anche parametri comuni con gli altri. Quando il numero dei gruppi aumenta, aumenta automaticamente anche il numero dei parametri da stimare. In teoria, questo dovrebbe rendere i calcoli sempre più lenti.
E infatti molti algoritmi soffrono proprio di questo: funzionano bene su problemi piccoli, ma rallentano drasticamente quando la dimensione cresce. Negli anni, però, gli statistici hanno osservato qualcosa di interessante: in molti modelli gerarchici, il Metropolis-within-Gibbs sembrava reggere l’urto della crescita dimensionale molto meglio del previsto. Il problema era che mancava una spiegazione teorica solida.
La velocità può restare stabile
Lo studio di Zanella, Ascolani e Roberts fornisce finalmente quella spiegazione. Gli autori dimostrano che, sotto condizioni realistiche e tipiche delle applicazioni pratiche, il numero di iterazioni necessarie per ottenere risultati affidabili non aumenta quando cresce il numero di gruppi nel modello.
In altre parole, anche se il modello diventa molto più grande, l’algoritmo non diventa più lento nel “mescolare” le informazioni e produrre stime corrette. Dal punto di vista pratico questo significa una cosa molto concreta: il tempo necessario per ottenere un campione accurato cresce in modo proporzionale alla dimensione del problema, non più che proporzionale. Non c’è quindi un “effetto valanga”.
Questo è un risultato importante, perché molti algoritmi alternativi, tra i quali alcuni molto usati nel machine learning, tendono invece a rallentare in modo più marcato quando la dimensionalità aumenta.
Perché funziona
L’intuizione centrale è che l’algoritmo aggiorna i parametri un gruppo alla volta. Se ogni aggiornamento locale è sufficientemente efficace, la qualità complessiva del procedimento resta sotto controllo anche quando i gruppi diventano numerosi. Il punto chiave è che la “perdita di efficienza” rispetto a una versione ideale dell’algoritmo non cresce automaticamente con il numero totale di parametri. Finché gli aggiornamenti locali sono ben progettati, il sistema nel suo complesso rimane stabile. Ciò va contro l’idea intuitiva secondo cui più complessità significa inevitabilmente più lentezza.
Quali sono le implicazioni
In termini computazionali, questo significa che il costo per ottenere stime affidabili aumenta in modo lineare con il numero di gruppi. È una crescita gestibile, prevedibile e compatibile con applicazioni su larga scala. In un mondo in cui aziende, istituzioni e centri di ricerca lavorano con basi dati sempre più estese, sapere che esistono algoritmi realmente scalabili non è un dettaglio tecnico: è una condizione necessaria per poter applicare modelli avanzati in contesti reali.
La complessità dei dati non deve necessariamente tradursi in complessità ingestibile dei calcoli. Con la giusta struttura matematica, la scalabilità è possibile.
