Selezione dell'algoritmo - Algorithm selection

La selezione dell'algoritmo (a volte chiamata anche selezione dell'algoritmo per istanza o selezione dell'algoritmo offline ) è una tecnica meta- algoritmica per scegliere un algoritmo da un portafoglio su base istanza per istanza. È motivato dall'osservazione che su molti problemi pratici, algoritmi diversi hanno caratteristiche di prestazione diverse. Cioè, mentre un algoritmo funziona bene in alcuni scenari, funziona male in altri e viceversa per un altro algoritmo. Se siamo in grado di identificare quando utilizzare quale algoritmo, possiamo ottimizzare per ogni scenario e migliorare le prestazioni complessive. Questo è ciò che la selezione dell'algoritmo mira a fare. L'unico prerequisito per l'applicazione delle tecniche di selezione degli algoritmi è che esista (o che possa essere costruito) un insieme di algoritmi complementari.

Definizione

Dato un portafoglio di algoritmi , un insieme di istanze e una metrica di costo , il problema di selezione dell'algoritmo consiste nel trovare una mappatura dalle istanze agli algoritmi in modo tale che il costo di tutte le istanze sia ottimizzato. ${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {A}}\in {\mathcal {P}}}$${\displaystyle i\in {\mathcal {I}}}$${\displaystyle m:{\mathcal {P}}\times {\mathcal {I}}\to \mathbb {R}}$${\displaystyle s:{\mathcal {I}}\to {\mathcal {P}}}$${\displaystyle {\mathcal {I}}}$${\displaystyle {\mathcal {P}}}$${\displaystyle \sum _{i\in {\mathcal {I}}}m(s(i),i)}$

Esempi

Problema di soddisfacibilità booleana (e altri problemi combinatori difficili)

Un'applicazione ben nota della selezione di algoritmi è il problema di soddisfacibilità booleana . Qui, il portafoglio di algoritmi è un insieme di risolutori SAT (complementari) , le istanze sono formule booleane, la metrica del costo è ad esempio il tempo di esecuzione medio o il numero di istanze non risolte. Quindi, l'obiettivo è selezionare un risolutore SAT ben funzionante per ogni singola istanza. Allo stesso modo, la selezione dell'algoritmo può essere applicata a molti altri problemi difficili (come la programmazione di interi misti , CSP , pianificazione AI , TSP , MAXSAT , QBF e programmazione di insiemi di risposte ). I sistemi vincitori della competizione in SAT sono SATzilla, 3S e CSHC ${\displaystyle {\mathcal {NP}}}$

Apprendimento automatico

Nell'apprendimento automatico , la selezione dell'algoritmo è meglio conosciuta come meta-apprendimento . Il portafoglio di algoritmi è costituito da algoritmi di apprendimento automatico (ad es. Random Forest, SVM, DNN), le istanze sono insiemi di dati e la metrica di costo è ad esempio il tasso di errore. Quindi, l'obiettivo è prevedere quale algoritmo di apprendimento automatico avrà un piccolo errore su ciascun set di dati.

Funzionalità dell'istanza

Il problema della selezione degli algoritmi viene risolto principalmente con tecniche di machine learning. Rappresentando le istanze del problema per caratteristiche numeriche , la selezione dell'algoritmo può essere vista come un problema di classificazione multiclasse imparando una mappatura per una data istanza . ${\displaystyle f}$${\displaystyle f_{i}\mapsto {\mathcal {A}}}$${\displaystyle i}$

Le feature di istanza sono rappresentazioni numeriche di istanze. Ad esempio, possiamo contare il numero di variabili, clausole, lunghezza media delle clausole per le formule booleane o il numero di campioni, caratteristiche, equilibrio di classe per i set di dati ML per avere un'idea delle loro caratteristiche.

Funzionalità statiche e di tastatura

Distinguiamo due tipi di caratteristiche:

1. Le caratteristiche statiche sono nella maggior parte dei casi alcuni conteggi e statistiche (ad esempio, rapporto tra clausole e variabili in SAT). Queste caratteristiche vanno da caratteristiche molto economiche (es. numero di variabili) a caratteristiche molto complesse (es. statistiche sui grafici a clausola variabile).
2. Le funzionalità di sondaggio (a volte chiamate anche funzionalità di landmarking) vengono calcolate eseguendo un'analisi del comportamento dell'algoritmo su un'istanza (ad esempio, l'accuratezza di un algoritmo di albero decisionale economico su un set di dati ML o eseguendo per un breve periodo un solutore di ricerca locale stocastico su un formula booleana). Queste funzionalità spesso costano più delle semplici funzionalità statiche.

Costi delle funzionalità

A seconda della metrica delle prestazioni utilizzata , il calcolo delle caratteristiche può essere associato ai costi. Ad esempio, se utilizziamo il tempo di esecuzione come metrica delle prestazioni, includiamo il tempo per calcolare le nostre funzionalità di istanza nelle prestazioni di un sistema di selezione dell'algoritmo. La soluzione SAT è un esempio concreto, in cui tali costi di funzionalità non possono essere trascurati, poiché le funzionalità di istanza per le formule CNF possono essere molto economiche (ad esempio, per ottenere il numero di variabili si può fare in tempo costante per le CNF nel formato DIMAC) o molto costoso (ad es. caratteristiche del grafico che possono costare decine o centinaia di secondi). ${\displaystyle m}$

È importante tenere conto del sovraccarico del calcolo delle caratteristiche nella pratica in tali scenari; altrimenti si crea un'impressione fuorviante delle prestazioni dell'approccio di selezione dell'algoritmo. Ad esempio, se la decisione sull'algoritmo da scegliere può essere presa con perfetta precisione, ma le caratteristiche sono il tempo di esecuzione degli algoritmi di portafoglio, non vi è alcun vantaggio per l'approccio di portafoglio. Questo non sarebbe ovvio se i costi delle funzionalità venissero omessi.

approcci

Approccio di regressione

Uno dei primi approcci di selezione dell'algoritmo di successo prevedeva le prestazioni di ciascun algoritmo e selezionava l'algoritmo con le migliori prestazioni previste per un'istanza . ${\displaystyle {\hat {m}}_{\mathcal {A}}:{\mathcal {I}}\to \mathbb {R}}$${\displaystyle arg\min _{{\mathcal {A}}\in {\mathcal {P}}}{\hat {m}}_{\mathcal {A}}(i)}$${\displaystyle i}$

Approccio di clustering

Un presupposto comune è che il dato insieme di istanze possa essere raggruppato in sottoinsiemi omogenei e per ciascuno di questi sottoinsiemi, esiste un algoritmo ben funzionante per tutte le istanze. Quindi, l'addestramento consiste nell'identificare i cluster omogenei tramite un approccio di clustering non supervisionato e nell'associare un algoritmo a ciascun cluster. Una nuova istanza viene assegnata a un cluster e l'algoritmo associato selezionato. ${\displaystyle {\mathcal {I}}}$

Un approccio più moderno è il clustering gerarchico sensibile ai costi che utilizza l'apprendimento supervisionato per identificare i sottoinsiemi di istanze omogenei.

Approccio di classificazione a coppie sensibile ai costi

Un approccio comune per la classificazione multiclasse consiste nell'imparare modelli a coppie tra ogni coppia di classi (qui algoritmi) e scegliere la classe che è stata prevista più spesso dai modelli a coppie. Possiamo pesare le istanze del problema di previsione a coppie in base alla differenza di prestazioni tra i due algoritmi. Ciò è motivato dal fatto che ci preoccupiamo maggiormente di ottenere previsioni con grandi differenze corrette, ma la penalità per una previsione errata è piccola se non c'è quasi nessuna differenza di prestazioni. Pertanto, ogni istanza per l'addestramento di un modello di classificazione vs è associata a un costo . ${\displaystyle i}$${\displaystyle {\mathcal {A}}_{1}}$${\displaystyle {\mathcal {A}}_{2}}$${\displaystyle |m({\mathcal {A}}_{1},i)-m({\mathcal {A}}_{2},i)|}$

Requisiti

Clustering di risolutori SAT dallo scenario SAT12-INDU ASlib secondo il coefficiente di correlazione di spearman.

Valori di Shapley per l'analisi complementare sullo scenario ASlib SAT12-INDU

Il problema di selezione dell'algoritmo può essere efficacemente applicato sotto le seguenti ipotesi:

• Il portafoglio di algoritmi è complementare rispetto all'insieme di istanze , ovvero non esiste un singolo algoritmo che domini le prestazioni di tutti gli altri algoritmi (vedi figure a destra per esempi sull'analisi complementare).${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {I}}}$${\displaystyle {\mathcal {A}}\in {\mathcal {P}}}$${\displaystyle {\mathcal {I}}}$
• In alcune applicazioni, il calcolo delle caratteristiche dell'istanza è associato a un costo. Ad esempio, se la metrica del costo è il tempo di esecuzione, dobbiamo considerare anche il tempo per calcolare le caratteristiche dell'istanza. In tali casi, il costo per calcolare le caratteristiche non dovrebbe essere maggiore del guadagno in termini di prestazioni attraverso la selezione dell'algoritmo.

Domini dell'applicazione

La selezione dell'algoritmo non è limitata ai singoli domini ma può essere applicata a qualsiasi tipo di algoritmo se i requisiti di cui sopra sono soddisfatti. I domini dell'applicazione includono:

• problemi combinatori difficili: SAT , Programmazione di numeri interi misti , CSP , AI Planning , TSP , MAXSAT , QBF e Programmazione di insiemi di risposte
• aste combinatorie
• nell'apprendimento automatico, il problema è noto come meta-apprendimento
• progettazione del software
• ottimizzazione della scatola nera
• sistemi multi-agente
• ottimizzazione numerica
• algebra lineare, equazioni differenziali
• algoritmi evolutivi
• problema di percorso del veicolo
• sistemi di alimentazione

Per un ampio elenco di letteratura sulla selezione degli algoritmi, si fa riferimento a una panoramica della letteratura.

Varianti di selezione dell'algoritmo

Selezione online

La selezione dell'algoritmo online si riferisce al passaggio tra diversi algoritmi durante il processo di risoluzione. Questo è utile come iper-euristica . Al contrario, la selezione dell'algoritmo offline seleziona un algoritmo per una determinata istanza solo una volta e prima del processo di risoluzione.

Calcolo degli orari

Un'estensione della selezione dell'algoritmo è il problema di scheduling dell'algoritmo per istanza, in cui non selezioniamo un solo risolutore, ma selezioniamo un budget temporale per ogni algoritmo su una base per istanza. Questo approccio migliora le prestazioni dei sistemi di selezione in particolare se le caratteristiche dell'istanza non sono molto informative ed è probabile una selezione errata di un singolo risolutore.

Selezione di portafogli paralleli

Data la crescente importanza del calcolo parallelo, un'estensione della selezione dell'algoritmo per il calcolo parallelo è la selezione del portafoglio parallelo, in cui selezioniamo un sottoinsieme degli algoritmi da eseguire contemporaneamente in un portafoglio parallelo.

link esterno

• Libreria di selezione degli algoritmi (ASlib)
• Letteratura sulla selezione degli algoritmi

Riferimenti