Quando gli statistici aiutano i progettisti di algoritmi

Confrontare algoritmi complessi è un compito molto impegnativo. Tuttavia, si tratta di un processo necessario, poiché gli algoritmi devono svolgere i loro compiti in modo rapido e con un impiego minimo di risorse, e devono gestire insiemi di dati e problemi di dimensioni importanti senza un calo significativo delle prestazioni. Nel recente articolo "Optimal design of the Barker proposal and other locally balanced Metropolis-Hastings algorithms", Giacomo Zanella del Dipartimento di Scienze delle Decisioni della Bocconi, Jure Vogrinc della Warwick University e Samuel Livingstone dello University College di Londra sviluppano un metodo per prevedere le prestazioni di diversi algoritmi di una stessa classe.

Progettare un algoritmo significa ideare un metodo o un processo matematico per risolvere i problemi. Esistono poi metodi matematici che prevedono in quali condizioni un algoritmo funziona bene, ovvero è in grado di produrre il suo risultato in un arco di tempo ragionevolmente breve. Questo è l'approccio utilizzato quando si tratta di algoritmi stocastici, che comportano un elemento di casualità, che porta a diversi risultati possibili anche con input identici. Tali algoritmi funzionano bene non solo su due dimensioni, come il piano cartesiano, ma su un numero molto ampio (e teoricamente illimitato) di dimensioni. Non si tratta di astratta teoria: gli algoritmi utilizzati nell'apprendimento automatico e in altre applicazioni statistiche avanzate lavorano abitualmente con diverse migliaia di dimensioni.

"Si può dire che questo è un caso in cui la matematica aiuta la progettazione algoritmica," afferma Giacomo Zanella. L'articolo si propone di studiare una classe specifica di algoritmi (tecnicamente noti come algoritmi di Metropolis-Hastings del primo ordine localmente bilanciati) per determinarne l'efficienza, cioè in che misura ciascuno di essi risponde a quella che gli addetti ai lavori chiamano la "maledizione della dimensionalità". Con questo termine si intende il fatto che, nel peggiore dei casi, la quantità di dati necessaria per mantenere la stessa affidabilità cresce esponenzialmente all'aumentare del numero di dimensioni. Pertanto, gli algoritmi sono destinati a diventare meno efficienti con l'aumentare delle dimensioni ed è importante sapere quali sono i meno vulnerabili in determinate condizioni. È a questo che si riferisce il "design ottimale" del titolo dell'articolo. Il risultato è quello che gli autori definiscono "un'espressione esplicita per l'efficienza asintotica di un algoritmo arbitrario all'interno della classe".

"È comune che i progettisti dedichino molti sforzi a fare scelte attente nel disegno degli algoritmi e a regolare i parametri di messa a punto degli algoritmi per garantire che le prestazioni siano adeguate a un determinato problema. Un'omissione in questo senso può essere catastrofica. Gli esempi in cui un algoritmo ben progettato funziona adeguatamente, ma un'alternativa scelta con meno attenzione invece no, sono numerosi," spiega Zanella.

Jure Vogrinc, Samuel Livingstone, Giacomo Zanella, "Optimal design of the Barker proposal and other locally balanced Metropolis–Hastings algorithms", Biometrika, Volume 110, numero 3, settembre 2023, DOI https://doi.org/10.1093/biomet/asac056