Skip to content

fabolas.md

Latest commit

 

History

History
246 lines (158 loc) · 10.9 KB

fabolas.md

File metadata and controls

246 lines (158 loc) · 10.9 KB

Fast Bayesian Optimization of Machine Learning Hyperparameters on large datasets (FABOLAS)

Introduzione

Mentre gli algoritmi di ottimizzazione Bayesiani classici modellano la loss come una funzione black box da essere minimizzata, FABOLAS tiene conto di come varia la loss (e il costo computazionale) al variare della dimensione del dataset (ad esempio usare porzioni piu' piccole nei primi passaggi).
In questo modo si aggiunge un grado di liberta' in piu', sfruttando anche la dimensione del dataset come variabile per ottimizzare piu' rapidamente.
Dunque ci deve essere un nuovo input alla funzione black box f, cioe' la dimensione del sottoinsieme considerato (rappresentata in forma relativa cioe' s = N_sub / N). Se s e' 1 allora si considera tutto il dataset per intero. L'obiettivo e' minimizzare la loss f (x , s=1).

Valutare f per s piu' piccoli ovviamente risulta meno costoso, ma la struttura di correlazione rispetto a valori sempre piu' grandi e' inizialmente sconosciuta, anche se sappiamo che esiste. La sfida e' trovare una strategia che bilanci il costo delle valutazioni con il vantaggio informativo, e quindi quali configurazioni saranno le migliori su tutto il dataset.

Verso l'algoritmo

Trattiamo s ∈ [0,1] come una variabile ambientale che puo' essere cambiata liberamente durante l'ottimizzazione, ma e' settata = 1 durante il periodo di evaluation. In FABOLAS esiste una regola ben fondata (principled rule) per selezionare automaticamente la prossima coppia (x, s) da valutare (x configurazione di iperparametri).
In poche parole, mentre l’ottimizzazione bayesiana classica valuterebbe sempre le configurazioni sul dataset completo, FABOLAS fa qualcosa di più furbo: usa un criterio chiamato ES (Expected Information Gain per Second) per stimare quanto possiamo imparare sul comportamento del modello sull’intero dataset anche valutandolo solo su una porzione più piccola (cioè a un certo s<1).

Una dimostrazione del funzionamento su questo approccio e' riportato nel paper nei confronti di MNIST. Hanno valutato 400 configurazioni di una SVM (Support Vector Machine) su sottoinsiemi del dataset MNIST (N = 50000). Sono state usate diverse dimensioni relative dei sottoinsiemi, cioe' s ∈ { 1/512 , 1/256 , 1/128 , ... , 1}. Viene mostrato che gia' usando 1 / 128 di dimensione relativa, si riesce gia a trovare qualche configurazione ragionevole, senza cadere in eventuali trappole di 'falsi' minimi locali

Per trasformare le intuizioni ottenute dall’esempio illustrativo (quello sull’SVM e MNIST) in un modello formale che descriva sia la loss che il costo al variare della dimensione del sottoinsieme di dati, gli autori estendono il modello GP (Gaussian Process) aggiungendo una nuova dimensione di input, cioè il parametro s∈[0,1], che rappresenta la dimensione relativa del dataset usato.

Grazie a questa estensione: il modello surrogato (GP) è in grado di fare previsioni su s=1 (cioè sull’intero dataset) senza dover realmente eseguire valutazioni costose su tutto il dataset. Per modellare questa dipendenza, viene usato un kernel fattorizzato, ovvero una funzione di covarianza composta da due parti:

  • Un kernel stazionario classico per gli iperparametri x (es. RBF o Matérn kernel), che cattura la similarità tra diverse configurazioni.
  • Una funzione di covarianza di rango finito (o "degenere") su s, progettata appositamente per catturare il comportamento della loss e del costo in base alla dimensione del dataset.

Kernel Fattorizzato in FABOLAS

La funzione di kernel usata in FABOLAS è definita come:

$$ k\big((x, s), (x_0, s_0)\big) = k_{5/2}(x, x_0) \cdot \phi^T(s) \cdot \Sigma_\phi \cdot \phi(s_0) $$

1. Significato della formula

Questa espressione definisce il kernel (funzione di covarianza) tra due input estesi:

  • una configurazione di iperparametri ( x ) e dimensione relativa ( s ),
  • un'altra configurazione ($ x_0 $) e dimensione relativa ( $s_0$).

La formula è composta da due parti principali:

2. ($ k_{5/2}(x, x_0$) ) — Kernel Matérn

  • È un kernel Matérn 5/2, una funzione standard stazionaria usata nei Gaussian Processes.
  • Misura quanto sono simili le due configurazioni di iperparametri ($ x $) e ( $x_0 $).
  • È particolarmente utile per modellare funzioni relativamente lisce, ma non troppo.

3. ( $\phi^T(s) \cdot \Sigma_\phi \cdot \phi(s_0)$ ) — Covarianza sulla dimensione del dataset

Questa parte modella la dipendenza dalla dimensione relativa del dataset ( s ).

  • ( $\phi(s)$ ): vettore di basi (feature map), ad esempio ( $[1, s, s^2, \log s]$ ), che rappresenta ( s ) in uno spazio finito.
  • ( $\Sigma_\phi$ ): matrice di covarianza tra le basi, appresa durante il training.
  • ( $\phi^T(s)$ ): trasposta del vettore ( $\phi(s)$ ), usata per ottenere un prodotto scalare.

Permette di modellare quanto sono correlati i valori della funzione tra diverse porzioni del dataset.

4. Riassunto Intuitivo

Il kernel è fattorizzato in due componenti:

  • Una parte che misura la similarità tra configurazioni ( x ).
  • Una parte che misura la similarità tra dimensioni relative ( s ).

Questo consente al modello GP di generalizzare su entrambe le dimensioni, e fare previsioni anche per dimensioni del dataset mai valutate direttamente.

Esempio di ( $\phi(s)$ )

Una possibile scelta per il vettore ( $\phi(s)$ ):

$$ \phi(s) = \begin{bmatrix} 1 \\ s \\ s^2 \\ \log s \end{bmatrix} $$

Questa base consente al modello di catturare sia comportamenti lineari che non lineari in ( s ).

Modellazione della Loss e del Costo in FABOLAS

1. Scelta delle funzioni base $\phi$ e positività del kernel

Ogni scelta della funzione base $\phi(s)$ genera una funzione di covarianza positiva semidefinita.
Questo garantisce flessibilità: possiamo scegliere $\phi$ per modellare conoscenza a priori su come si comportano loss e costo rispetto alla dimensione relativa del dataset $s$.

2. Due kernel distinti per loss e costo

FABOLAS usa lo stesso schema di kernel, ma con funzioni base $\phi$ diverse, per:

  • La loss $f(x, s)$
  • Il costo computazionale $c(x, s)$

Per la loss $f$

  • Funzione base:

    $$ \phi_f(s) = \begin{bmatrix} 1 \ (1 - s)^2 \end{bmatrix} $$

  • Motivazione: La loss tende a diminuire all’aumentare dei dati. Questa scelta impone al modello una predizione monotona, con un minimo in $s = 1$.

  • Interpretazione: Questo equivale a una regressione lineare bayesiana con funzioni base $\phi_f$ e prior gaussiani sui pesi.

Per il costo $c$

  • Modellano il logaritmo del costo, per:

    • Ottenere solo valori positivi
    • Modellare complessità del tipo $\mathcal{O}(s^\alpha)$ per qualunque $\alpha$

  • Funzione base:

    $$ \phi_c(s) = \begin{bmatrix} 1 \ s \end{bmatrix} $$

  • Anche questa è una regressione lineare bayesiana, ma applicata a $\log c$.

3. Validazione empirica

  • Negli allegati (supplementary material, Sezione B), mostrano che i kernel scelti si adattano bene ai dati reali di loss e costo sull’esempio con SVM.
  • Considerano anche la possibilità di modellare il rumore eteroschedastico (varianza che cambia con $s$) introdotto dal sottocampionamento, discusso nella Sezione C.

Riassunto

Aspetto Loss $f$ Costo $c$
Funzione base $\phi$ $[1,\ (1-s)^2]$ $[1,\ s]$
Obiettivo Comportamento decrescente Crescita polinomiale
Modellazione Regressione lineare bayesiana Regressione bayesiana su $\log c$
Proprietà chiave Minimo in $s = 1$ Predizioni sempre positive

Funzione di acquisizione in FABOLAS

FABOLAS seleziona ogni nuova coppia $(x, s)$ valutando la seguente funzione di acquisizione:

$$ \alpha_F(x, s) = \frac{1}{c(x, s) + c_{\text{overhead}}} \int \mathbb{E}_{p(y \mid x, s, D)} \left[ \frac{p_{s=1}^{\text{min}}(x \mid D \cup {(x, s, y)})}{p_{s=1}^{\text{min}}(x \mid D)} \log \left( \frac{p_{s=1}^{\text{min}}(x \mid D \cup {(x, s, y)})}{p_{s=1}^{\text{min}}(x \mid D)} \right) \right] , dy $$

Dove:

  • $p_{s=1}^{\text{min}}(x \mid D)$ è la probabilità che $x$ sia ottimale su tutto il dataset ($s=1$), dato il dataset corrente $D$.
  • $c(x, s)$ è il costo atteso per valutare $f(x, s)$.
  • $c_{\text{overhead}}$ è un costo fisso di sistema.
  • L’integrale calcola il guadagno informativo atteso su $p_{s=1}^{\text{min}}$ a seguito della valutazione di $f(x, s)$.

L'obiettivo è massimizzare il guadagno informativo sulla configurazione ottimale per il dataset completo, per unità di costo.

Algoritmo

  1. Inizializza i dati $D_0$ con un design iniziale (che vedremo meglio dopo)

  2. Per ogni iterazione $t = 1, 2, \dots$:

    1. Fitta i modelli Gaussian Process (GP) su $D_{t-1}$:

      • Uno per la funzione obiettivo $f(x, s)$
      • Uno per il costo computazionale $c(x, s)$

    2. Scegli la nuova coppia $(x_t, s_t)$ massimizzando la funzione di acquisizione (Equation 7).

    3. Valuta:

      • $y_t \sim f(x_t, s_t) + \mathcal{N}(0, \sigma^2)$ (loss osservata)
      • $z_t \sim c(x_t, s_t) + \mathcal{N}(0, \sigma_c^2)$ (costo osservato)
      • Aggiorna il dataset:
        $D_t = D_{t-1} \cup {(x_t, s_t, y_t, z_t)}$

    4. Seleziona il candidato ottimale (incumbent) $\hat{x}_t$ tra tutti gli $x_1, \dots, x_t$
      in base alla predizione della loss su tutto il dataset ($s = 1$).

  3. Ripeti.

Design iniziale

Nell'ottimizzazione bayesiana, è comune iniziare con un initial design:

  • Una serie di punti selezionati casualmente o tramite Latin Hypercube Sampling,
  • Serve a fornire una buona base per il modello GP.

Strategia usata in FABOLAS

FABOLAS modifica l'approccio classico per sfruttare valutazioni più rapide:

  • Si selezionano $k = 10$ punti casuali $x_1, \dots, x_k \in \mathcal{X}$.
  • Ciascuno viene valutato su diversi sottoinsiemi del dataset, con $s \in \left{ \frac{1}{64}, \frac{1}{32}, \frac{1}{16}, \frac{1}{8} \right}$.
  • Questo aiuta a:
    • Catturare la dipendenza della loss da $s$,
    • Ridurre il costo computazionale iniziale.

Considerazioni di costo

Se il costo $c(s)$ cresce linearmente o peggio con $s$, allora:

  • Il costo totale di $k$ punti valutati su 4 subset piccoli è molto inferiore a quello di $k \cdot 8$ valutazioni a $s = 1$.

$$ \text{Costo}(k \text{ punti su } s \in \left{ \tfrac{1}{64}, \tfrac{1}{32}, \tfrac{1}{16}, \tfrac{1}{8} \right}) \ll \text{Costo}(k \cdot 8 \text{ punti su } s = 1) $$

Questo è rilevante perché il tempo iniziale speso per l'initial design viene incluso nel tempo totale per valutare FABOLAS.