Ricerca quasi casuale

Questa unità si concentra sulla ricerca quasi-casuale.

Perché utilizzare una ricerca quasi-casuale?

La ricerca quasi-casuale (basata su sequenze a bassa discrepanza) è la nostra preferenza rispetto agli strumenti di ottimizzazione più originali quando vengono utilizzati come parte di un processo di ottimizzazione iterativo finalizzato a massimizzare gli insight sul problema di ottimizzazione (quella che definiamo "fase di esplorazione"). L'ottimizzazione bayesiana e strumenti simili sono più appropriati per la fase di sfruttamento. Una ricerca quasi casuale basata su sequenze a bassa discrepanza in modo casuale può essere considerata come una "ricerca a griglia distorta e distorta", poiché esplora in modo uniforme, ma casuale, un determinato spazio di ricerca e distribuisce i punti di ricerca più della ricerca casuale.

I vantaggi della ricerca quasi casuale rispetto agli strumenti di ottimizzazione più sofisticati delle blackbox (ad es. ottimizzazione bayesiana, algoritmi evolutivi) includono:

• Il campionamento dello spazio di ricerca in modo non adattivo consente di modificare l'obiettivo di ottimizzazione nell'analisi post hoc senza dover eseguire di nuovo gli esperimenti. Ad esempio, di solito vogliamo trovare la prova migliore in termini di errore di convalida raggiunto in qualsiasi momento dell'addestramento. Tuttavia, la natura non adattiva della ricerca quasi casuale consente di trovare la prova migliore in base all'errore di convalida finale, all'errore di addestramento o a qualche metrica di valutazione alternativa, senza dover eseguire nuovamente gli esperimenti.
• La ricerca quasi casuale si comporta in modo coerente e statisticamente riproducibile. Dovrebbe essere possibile riprodurre uno studio di sei mesi fa anche se l'implementazione dell'algoritmo di ricerca cambia, a condizione che mantenga le stesse proprietà di uniformità. Se utilizzi un sofisticato software di ottimizzazione bayesiano, l'implementazione potrebbe cambiare in modo importante tra le versioni, rendendo molto più difficile la riproduzione di una ricerca precedente. Non è sempre possibile eseguire il rollback a un'implementazione precedente (ad esempio se lo strumento di ottimizzazione è eseguito come servizio).
• La sua esplorazione uniforme dello spazio di ricerca consente di ragionare più facilmente sui risultati e su ciò che potrebbero suggerire. Ad esempio, se il punto migliore nell'attraversamento della ricerca quasi-casuale si trova al confine dello spazio di ricerca, è un segnale valido (ma non infallibile) che indica che i limiti dello spazio di ricerca devono essere modificati. Tuttavia, un algoritmo di ottimizzazione adattivo della blackbox potrebbe aver trascurato il centro dello spazio di ricerca a causa di alcune prove iniziali sfortunate anche se contiene punti altrettanto validi, poiché è proprio questo tipo di non uniformità che un buon algoritmo di ottimizzazione deve utilizzare per velocizzare la ricerca.
• L'esecuzione di numeri diversi di prove in parallelo e in sequenza non produce risultati statisticamente diversi quando si utilizza una ricerca quasi casuale (o altri algoritmi di ricerca non adattivi), a differenza degli algoritmi adattivi.
• Gli algoritmi di ricerca più sofisticati potrebbero non gestire correttamente i punti impossibili, soprattutto se non sono progettati pensando all'ottimizzazione degli iperparametri di rete neurale.
• La ricerca quasi casuale è semplice e funziona soprattutto quando molte prove di ottimizzazione vengono eseguite in parallelo. Aneddoticamente¹, è molto difficile per un algoritmo adattivo battere una ricerca quasi casuale che ha il doppio del budget, soprattutto quando molte prove devono essere eseguite in parallelo (quindi ci sono pochissime possibilità di utilizzare i risultati delle prove precedenti al momento del lancio di nuove prove). Senza l'esperienza dell'ottimizzazione bayesiana e di altri metodi avanzati per l'ottimizzazione delle blackbox, potresti non ottenere i vantaggi che sono in linea di principio in grado di fornire. È difficile confrontare algoritmi di ottimizzazione avanzati di blackbox in condizioni di ottimizzazione realistiche del deep learning. Sono un'area molto attiva di ricerca attuale e gli algoritmi più sofisticati presentano le proprie insidie per gli utenti inesperti. Gli esperti di questi metodi riescono a ottenere buoni risultati, ma in condizioni di elevata parallelismo lo spazio di ricerca e il budget tendono a essere più importante.

Detto questo, se le risorse di calcolo consentono l'esecuzione in parallelo solo di un numero limitato di prove in parallelo e puoi permetterti di eseguire molte prove in sequenza, l'ottimizzazione bayesiana diventa molto più allettante nonostante renda più difficili da interpretare i risultati dell'ottimizzazione.

Dove posso trovare un'implementazione della ricerca quasi-casuale?

Vizier open source ha un'implementazione della ricerca quasi-casuale. Imposta algorithm="QUASI_RANDOM_SEARCH" in questo esempio di utilizzo di Vizier. Esiste un'implementazione alternativa in questo esempio di scansione di iperparametri. Entrambe queste implementazioni generano una sequenza di Halton per un determinato spazio di ricerca (che si intende implementare una sequenza di Halton spostata e criptata, come consigliato in Iper-parametri critici: No Random, No Cry).

Se non è disponibile un algoritmo di ricerca basato su una sequenza quasi a bassa discrepanza, è possibile sostituire una ricerca uniforme pseudo casuale, anche se probabilmente questa sarà leggermente meno efficiente. Anche la ricerca con griglia è accettabile, ma non con dimensioni superiori, anche se con una o due dimensioni. (vedi Bergstra e Bengio, 2012).

Quante prove sono necessarie per ottenere buoni risultati con una ricerca quasi casuale?

Non c'è modo di determinare quante prove sono necessarie per ottenere risultati con la ricerca quasi-casuale in generale, ma puoi guardare esempi specifici. Come mostra la Figura 3, il numero di prove in uno studio può avere un impatto sostanziale sui risultati:

Figura 3: ResNet-50 ottimizzato su ImageNet con 100 prove. Utilizzando il bootstrap, sono stati simulati diversi budget di ottimizzazione. Vengono tracciati i box plot delle migliori prestazioni per ogni budget di prova.

 

Osserva quanto segue in merito alla Figura 3:

• Gli intervalli interquartili durante il campionamento di 6 prove sono molto più grandi rispetto a quando sono stati campionati 20 prove.
• Anche con 20 prove, la differenza tra studi particolarmente fortunati e sfortunati è probabilmente maggiore della variazione tipica tra riaddestramenti di questo modello su diversi semi casuali, con iperparametri fissi, che per questo carico di lavoro potrebbero essere circa +/- 0,1% con un tasso di errore di convalida di circa il 23%.

---

1. Ben Recht e Kevin Jamieson hanno sottolineato l'efficacia della ricerca casuale con un budget raddoppiato come base (il documento sull'hyperband presenta argomenti simili), ma è sicuramente possibile trovare spazi di ricerca e problemi in cui le tecnologie di ottimizzazione bayesiane all'avanguardia frantumano la ricerca casuale che ha il doppio del budget. Tuttavia, secondo la nostra esperienza, superare il doppio del budget la ricerca casuale diventa molto più difficile nel regime ad alto parallelismo poiché l'ottimizzazione bayesiana non ha l'opportunità di osservare i risultati delle prove precedenti.↩