Dipartimento di Fisica

È stato pubblicato dalla prestigiosa rivista Physical Review X un lavoro a firma di due ricercatori del Dipartimento di Fisica della Sapienza (Maria Chiara Angelini e Federico Ricci-Tersenghi) che compie un importante passo avanti nella comprensione degli algoritmi di inferenza basati sui metodi di tipo Monte Carlo, come ad esempio il famoso algoritmo del Simulated Annealing. Quest'ultimo è probabilmente l’algoritmo più usato al mondo per ottimizzare (minimizzare) una funzione complessa e trova applicazioni nelle discipline più varie.

I ricercatori della Sapienza hanno proposto una teoria, e delle congetture associate ad essa, grazie alle quali è possibile determinare in quali condizioni un algoritmo di tipo Simulated Anneling sia in grado di risolvere una certa classe di problemi di inferenza, noti con il nome di planted models.

Nei problemi di inferenza l’obiettivo è quello di estrarre un segnale da un insieme di dati incompleti e/o rumorosi. Nei modelli di tipo planted il segnale viene “piantato” a mano in un punto noto e poi “nascosto” aggiungendo rumore e incertezze nel modello. Ovviamente il luogo dove il segnale è piantato non è noto all’algoritmo che lo deve trovare.

Angelini e Ricci-Tersenghi sono riusciti a capire che in tali modelli planted si viene ad instaurare una competizione tra lo stato planted (dove risiede il segnale da recuperare) e gli stati vetrosi (descritti molto bene dalla teoria della complessità per la quale Giorgio Parisi ha vinto il Nobel per la Fisica nel 2021). Gli stati vetrosi si generano grazie al rumore e all’incertezza nei dati e rivestono un ruolo fondamentale al momento di capire il comportamento degli algoritmi di ricerca del segnale. Come illustrato in modo schematico nella figura di destra, se gli stati vetrosi sono molto attrattivi e l’algoritmo di ricerca vi finisce dentro è impossibile che poi ne esca e l’inferenza del segnale fallisce. Il destino dell’algoritmo è quindi determinato da quale stato (tra il planted e il vetroso) viene incontrato prima scendendo verso le basse energie. La risposta a questa domanda si può evincere dai diagrammi di fase (come quello nella figura di sinistra) che i ricercatori sono stati in grado di derivare con le tecniche della meccanica statistica dei sistemi disordinati.

Link alla pubblicazione:
https://journals.aps.org/prx/abstract/10.1103/PhysRevX.13.021011

Contatti degli autori:
Maria Chiara Angelini, mariachiara.angelini@uniroma1.it
Federico Ricci-Tersenghi, federico.ricci@uniroma1.it