Taking the Human Out of the Loop: A Review of Bayesian Optimization

The paper introduces the reader to Bayesian optimization, highlighting its methodical aspects and showcasing its applications.

By Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando de Freitas

 

ABSTRACT | Big Data applications are typically associated with
systems involving large numbers of users, massive complex
software systems, and large-scale heterogeneous computing
and storage architectures. The construction of such systems
involves many distributed design choices. The end products
(e.g., recommendation systems, medical analysis tools, realtime
game engines, speech recognizers) thus involve many
tunable configuration parameters. These parameters are
often specified and hard-coded into the software by various
developers or teams. If optimized jointly, these parameters
can result in significant improvements. Bayesian optimization
is a powerful tool for the joint optimization of design choices
that is gaining great popularity in recent years. It promises
greater automation so as to increase both product quality and
human productivity. This review paper introduces Bayesian
optimization, highlights some of its methodological aspects,
and showcases a wide range of applications.

KEYWORDS | Decision making; design of experiments; optimization;
response surface methodology; statistical learning

 

Proceedings of the IEEE | Vol. 104, No. 1, January 2016

Ottimizzazione

I problemi di ottimizzazione richiedono necessariamente la creazione di algoritmi efficienti in quanto, generalmente, un problema di ottimizzazione possiede uno spazio delle possibili soluzioni di cardinalità esponenziale, quindi anche possedendo il più potente dei computer non potremmo permetterci di enumerare tutte le possibili soluzioni e scegliere la migliore. A titolo di esempio supponiamo di avere n variabili x(i), i=1,…,n; che possono assumere d(i) valori diversi 0,1,2,…,d(i)-1; in questo caso avremo che il numero di soluzioni ammissibili per il problema sarebbe dato da: ns=d(1)*d(2)*…*d(n). Considerando n=20 e d(i)=4 per ogni i, si otterrebbe ns=4^20, cioè circa 10^12! (il simbolo ^ sta per elevamento a potenza; 10^12=1,000,000,000,000, cioè un milione di milioni). Di conseguenza un algoritmo enumerativo richiederebbe un tempo di esecuzione proporzionale a 10^12 con soli 20 elementi.

L’ottimizzazione può essere suddivisa in due grandi categorie: dinamica e statica. Nell’ottimizzazione dinamica i vincoli e le variabili che esprimono il modello del problema possono variare nel tempo. Nella ottimizzazione statica vincoli e variabili sono costanti. A sua volta l’ottimizzazione statica si divide in continua e discreta in funzione del fatto che le variabili possano assumere valori contini o discreti. Nell’ambito della programmazione continua distinguiamo tra programmazione lineare, se funzione obiettivo e vincoli sono lineari, e programmazione non lineare altrimenti.

Un lettore non addetto potrebbe domandarsi come sia possibile trovare la soluzione ottima senza verificare una per una tutte le soluzioni disponibili. Questo può avvenire grazie a meccanismi di classificazione; il dominio delle soluzioni viene organizzato secondo una struttura che le ordina in funzione di determinate caratteristiche, quindi è possibile scartare a priori alcuni sottoinsiemi del dominio delle soluzioni senza esaminarle essendo sicuri del fatto che queste non potranno fornire soluzioni migliori di un determinato obiettivo. È un po’ come entrare in una biblioteca e cercare un libro; il libri sono organizzati per argomento e per titolo alfabeticamente, quindi non sarà necessario esplorare tutti i libri della biblioteca per trovare quello che cerchiamo ma solo un sottoinsieme. Questo è il meccanismo di funzionamento degli algoritmi e delle metodologie di risoluzione dei problemi di ottimizzazione tra cui ricordiamo il metodo del simplesso e la tecnica del branch and bound.