A New Approach to Characterising Optimisation Problems Using Programmatic Representation and Complexity Measures
Questo articolo propone un approccio innovativo per caratterizzare i problemi di ottimizzazione calcolando il volume di Halstead e l'entropia delle loro implementazioni programmatiche, dimostrando che queste misure di complessità basate sul codice fungono da efficaci meta-caratteristiche predittive privi di campionamento per la selezione degli algoritmi.
Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo
Immagina di cercare di insegnare a un robot come risolvere un labirinto. A volte il labirinto è un semplice corridoio dritto; altre volte, è un labirinto tortuoso e pieno di svolte, con vicoli ciechi e trappole. Nel mondo dell'informatica, questo si chiama ottimizzazione: trovare la migliore soluzione possibile a un problema. Ma ecco la parte complicata: non tutti i labirinti sono creati uguali. Alcuni sono facili da risolvere per un robot, mentre altri fanno perdere la bussola anche agli algoritmi più intelligenti.
Per aiutare i robot a scegliere la strategia giusta, gli scienziati cercano di "caratterizzare" o descrivere questi labirinti prima ancora che il robot inizi a muoversi. Cercano indizi, come quanto sia sconnesso il terreno o quanti vicoli ciechi esistano. Di solito, per trovare questi indizi, il robot deve compiere alcuni passi, guardarsi intorno e misurare il terreno. È come inviare una ricognizione al buio per mappare una grotta. Ma cosa succederebbe se il robot potesse semplicemente guardare la progettazione del labirinto e indovinare quanto sarebbe difficile da risolvere, senza mai mettervi piede dentro? Questa è la grande domanda che questo articolo pone. Suggerisce che il modo in cui un problema è scritto in codice informatico potrebbe custodire il segreto di quanto sia difficile da risolvere, proprio come la complessità di una ricetta può suggerire quanto sarà difficile cucinare.
Il Codice come Palla di Cristallo
In questo articolo, Marcus Gallagher e Katherine Malan propongono un modo nuovo, leggermente magico, di guardare a questi problemi difficili. Invece di inviare una ricognizione per misurare il paesaggio, suggeriscono di leggere semplicemente la "ricetta" che il computer usa per creare il problema.
Pensa a un problema di ottimizzazione come a un livello di un videogioco. Per costruire il livello, un programmatore scrive del codice. Alcuni livelli sono semplici: "Vai avanti, salta sopra un fosso, raccogli la moneta". Il codice per questo è breve e usa comandi base. Altri livelli sono caotici: "Se il cielo è blu, moltiplica la tua velocità per il numero di stelle, poi sottrai la radice quadrata della tua salute, ma solo se indossi un cappello". Il codice per questo è lungo, disordinato e usa una vastissima varietà di comandi.
L'idea dei due autori è questa: Più disordinato e complesso è il codice, più difficile è il problema da risolvere per un algoritmo.
Essi prendono in prestito due strumenti dal mondo dell'ingegneria del software per misurare questa "disordine".
- Volume di Halstead: Immagina di contare ogni singola parola e simbolo in un paragrafo. Se hai un breve racconto con parole semplici, il conteggio è basso. Se hai un romanzo con un vocabolario complesso e frasi lunghe, il conteggio è alto. Questa misura conta gli "operatori" (come i simboli matematici) e gli "operand" (come numeri e variabili) nel codice.
- Entropia di Shannon: Questo è un po' come misurare il fattore sorpresa. Se un paragrafo usa sempre le stesse cinque parole, è prevedibile (entropia bassa). Se usa una vastissima varietà di parole uniche in un ordine casuale, è imprevedibile (entropia alta).
L'Esperimento: Dai Cerchi Semplici alle Vette Caotiche
Per testare la loro teoria, gli autori hanno preso un famoso insieme di 24 problemi di test usati da scienziati in tutto il mondo (noto come suite BBOB). Questi vanno dalla funzione "Sphere" (una collina perfettamente liscia e rotonda, facile da rotolare giù) alla funzione "Lunacek bi-Rastrigin" (un paesaggio irregolare e roccioso con migliaia di minuscole vette e valli).
Hanno trascritto il codice informatico per ciascuno di questi 24 problemi ed hanno eseguito i loro calcolatori di "disordine" su di essi. I risultati sono stati esattamente quelli che speravano:
- La funzione Sphere, semplice e liscia, aveva i punteggi di complessità più bassi.
- La funzione Lunacek, irregolare e difficile, aveva i punteggi di complessità più alti.
- Infatti, la funzione Lunacek era circa 9,3 volte più complessa nella sua struttura di codice rispetto alla funzione Sphere.
Hanno testato questo anche su un altro tipo di problema: l'addestramento di una rete neurale (un tipo di cervello IA). Hanno scoperto che il codice per una rete che utilizza una funzione di attivazione "Tanh" era leggermente più complesso di uno che utilizza "ReLU", e questo corrispondeva all'idea che la versione Tanh sia un puzzle leggermente più difficile da risolvere.
La Connessione Magica: La Complessità del Codice Predice le Prestazioni
La vera magia avviene quando confrontano questi punteggi del codice con le prestazioni effettive degli algoritmi. Hanno osservato i dati di cinque diversi algoritmi "robot" che cercavano di risolvere questi 24 problemi.
Hanno trovato un modello chiaro: Più complesso è il codice, peggiori sono le prestazioni dei robot.
È una relazione negativa. Quando il codice era semplice (volume di Halstead basso), i robot risolvevano il problema velocemente e facilmente. Quando il codice era complesso (volume di Halstead alto), i robot facevano fatica, impiegavano più tempo o rimanevano bloccati. Ad esempio, nei problemi a 5 dimensioni, la connessione tra la complessità del codice e le scarse prestazioni era piuttosto forte.
Tuttavia, gli autori avvertono con cautela che questo non è un cristallo perfetto. C'erano alcuni problemi "outlier" dove il codice era molto complesso, ma i robot non si comportavano così male come il codice suggeriva. Ciò suggerisce che, sebbene la complessità del codice sia un ottimo indizio, non è l'unica cosa che conta.
Perché Questo è Importante
La bellezza di questo approccio è che è incredibilmente veloce e non richiede alcun lavoro extra. I metodi tradizionali per comprendere un problema spesso comportano l'esecuzione dell'algoritmo migliaia di volte solo per vedere come appare il paesaggio. Questo è come inviare una ricognizione a camminare per tutto il labirinto solo per disegnare una mappa.
Al contrario, il metodo degli autori è come guardare la progettazione del labirinto. È possibile calcolare la complessità del codice in una frazione di secondo, senza eseguire il problema una sola volta. Non gli importa della dimensione del problema o di quante dimensioni abbia; guarda solo alla struttura delle istruzioni.
Gli autori suggeriscono che questa nuova misura di "complessità del codice" potrebbe essere un utile complemento alla cassetta degli attrezzi degli scienziati che progettano algoritmi. Non sostituisce i vecchi modi di analizzare i problemi, ma aggiunge un nuovo modo super veloce per indovinare quanto sarà difficile un problema prima ancora di iniziare a risolverlo. È un passo promettente verso l'aiutare i computer a scegliere lo strumento giusto per il compito, semplicemente leggendo le istruzioni.
Sommerso dagli articoli nel tuo campo?
Ricevi digest giornalieri degli articoli più recenti corrispondenti alle tue parole chiave di ricerca — con riassunti tecnici, nella tua lingua.