No free lunch

Nel contesto della complessità computazionale e dell'ottimizzazione, il teorema "no free lunch" (NFL) è un risultato che afferma che per certi tipi di problemi matematici, il costo computazionale per il ritrovamento di una soluzione, mediato su tutti i problemi della classe, è lo stesso per qualsiasi metodo di soluzione. Il nome allude al detto " no such thing as a free lunch ", ovvero nessun metodo offre una "scorciatoia". Ciò si basa sull'assunzione che lo spazio di ricerca sia una funzione di densità di probabilità ma non si applica al caso in cui lo spazio di ricerca abbia una struttura sottesa (ad esempio, sia una funzione differenziabile) che può essere sfruttata in modo più efficiente (ad esempio, come nel metodo di Newton nell'ottimizzazione) rispetto alla ricerca casuale o addirittura abbia soluzioni in forma chiusa (ad esempio, gli estremi di un polinomio quadratico) che possono essere determinate senza alcuna ricerca. Fatte tali assunzioni probabilistiche, gli output di tutte le procedure che risolvono un particolare tipo di problema sono statisticamente identici. Un modo colorito per descrivere tale circostanza, introdotto da David Wolpert e William G. Macready in relazione ai problemi di ricerca e ottimizzazione, è dire che non esiste un pranzo gratis. Wolpert aveva precedentemente derivato teoremi NFL per l'apprendimento automatico (inferenza statistica). Prima che l'articolo di Wolpert fosse pubblicato, Cullen Schaffer aveva dimostrato in modo indipendente una versione ristretta di uno dei teoremi di Wolpert e lo utilizzò per criticare lo stato della ricerca sull'apprendimento automatico riguardo al problema dell'induzione.

Nella metafora del "nessun pasto gratis", ogni "ristorante" (procedura di problem-solving) ha un "menù" che associa a ogni "piatto" (problema) un "prezzo" (l'efficacia della procedura nella risoluzione del problema). I menù dei ristoranti sono identici, tranne che per un aspetto: i prezzi cambiano da un ristorante all'altro. Per un onnivoro che abbia la stessa probabilità di ordinare ogni piatto come qualsiasi altro, il costo medio del pasto non dipende dalla scelta del ristorante. Ma un vegano che mangia regolarmente con un carnivoro che cerca di risparmiare potrebbe pagare molto, mediamente, per un pasto. Per ridurre in modo sistematico il costo medio, è necessario sapere in anticipo a) cosa si ordinerà e b) quanto costerà l'ordine nei vari ristoranti. In altre parole, il miglioramento delle prestazioni nella risoluzione dei problemi dipende dall'utilizzo di informazioni pregresse per adattare le procedure ai problemi.

In termini formali, non c'è niente di gratuito quando la distribuzione di probabilità sulle istanze del problema è tale che tutti i risolutori di problemi ottengono risultati distribuiti in modo identico. Nel caso della ricerca, un'istanza del problema in tale contesto è una particolare funzione obiettivo e un risultato è una sequenza di valori ottenuti nella valutazione delle soluzioni candidate nel dominio della funzione. Per le interpretazioni tipiche dei risultati, la ricerca è un processo di ottimizzazione. Non ci sono pasti gratis nella ricerca se e solo se la distribuzione sulle funzioni obiettivo è invariante rispetto alla permutazione dello spazio delle soluzioni candidate. Questa condizione non è verificata esattamente nella pratica, ma un teorema "(quasi) niente pasti gratis" suggerisce che sia verificata in modo approssimato.

Panoramica

Alcuni problemi computazionali vengono risolti cercando buone soluzioni in uno spazio di soluzioni candidate. Un algoritmo di ricerca costituisce una descrizione di come selezionare ripetutamente soluzioni candidate per la valutazione. Dato un particolare problema, diversi algoritmi di ricerca possono trovare risultati diversi, ma nel complesso dei diversi problemi essi sono indistinguibili. Ne consegue che se un algoritmo ottiene risultati superiori su alcuni problemi, deve pagare con l'inferiorità su altri problemi. In questo senso, la ricerca non è un pasto gratis. In alternativa, seguendo Schaffer, esiste una legge di conservazione delle le prestazioni nella ricerca. Essendo di solito la ricerca finalizzata all'ottimizzazione, ne consegue l'osservazione che non ci siano pasti gratis nell'ottimizzazione.

"Il teorema del 'pasto gratis' di Wolpert e Macready", come affermato in parole semplici dagli stessi autori, sostiene che "due algoritmi qualsiasi sono equivalenti quando le loro prestazioni vengono mediate su tutti i possibili problemi". I risultati NFL indicano che con l'abbinamento fra algoritmi e problemi si ottengano prestazioni medie più elevate rispetto all'applicazione di un algoritmo fisso. Igel e Toussaint e English hanno stabilito una condizione generale in base alla quale non esista un pasto gratis. Sebbene sia fisicamente possibile, essa non è precisamente valida. Droste, Jansen e Wegener hanno dimostrato un teorema che interpretano come indice del fatto che non esista "(quasi) nessun pranzo gratis" nella pratica.

Per rendere le cose più concrete, si consideri un tecnico dell'ottimizzazione alle prese con un problema. Avendo una certa conoscenza su come si sia verificato il problema, il tecnico potrebbe essere in grado di sfruttarla per selezionare un algoritmo che nella sua risoluzione fornirà buone prestazioni. Se il tecnico non comprende come sfruttare tale conoscenza o se, semplicemente, non ne ha alcuna, allora si trova ad affrontare la questione di stabilire se un dato algoritmo, in generale, sia superiore ad altri su problemi reali. Gli autori del teorema "(quasi) nessun pasto gratis" affermano che la risposta è essenzialmente negativa, ma ammettono di avere delle riserve sul fatto che il teorema sia applicabile nella pratica.

Teoremi

Sul piano formale un "problema" è una funzione obiettivo che associa soluzioni candidate a valori di qualità. Un algoritmo di ricerca accetta una funzione obiettivo come input e valuta le soluzioni candidate una alla volta. L'output dell'algoritmo è la sequenza dei valori di qualità osservati.

Wolpert e Macready sostengono che un algoritmo non rivaluta mai una soluzione candidata e che le prestazioni dell'algoritmo vengono misurate in base agli output. Per semplicità, non si considereranno algoritmi che sfruttino la casualità. In tali condizioni, quando un algoritmo di ricerca viene eseguito su ogni possibile input, genera ogni possibile output esattamente una volta. Poiché le prestazioni vengono misurate in base agli output, gli algoritmi sono indistinguibili in base alla frequenza con cui raggiungono particolari livelli di prestazioni.

Alcune misure delle prestazioni degli algoritmi di ricerca indicano quanto bene essi si comportano nell'ottimizzazione della funzione obiettivo. In effetti, non sembra esserci alcuna applicazione interessante degli algoritmi di ricerca nella classe in esame se non ai problemi di ottimizzazione. Una misura comune è l'indice minimo del valore minimo nella sequenza di output. Questo rappresenta il numero di valutazioni necessarie per minimizzare la funzione obiettivo. Per alcuni algoritmi, il tempo necessario per trovare il minimo è proporzionale al numero di valutazioni.

I teoremi originali NFL presuppongono che tutte le funzioni obiettivo abbiano la stessa probabilità di essere date in input ad algoritmi di ricerca. È stato quindi stabilito che non ci sono pasti gratis se e solo se, in parole povere, "rimescolare" le funzioni obiettivo non ha alcun impatto sulle loro probabilità. Sebbene questa condizione sia fisicamente possibile, è stato osservato che certamente essa non sia valida in modo preciso.

Apparentemente l'interpretazione immediata di "non NFL" è quella di "pasto gratis", tuttavia ciò è fuorviante. NFL è un fatto graduale non una proprietà che valga "del tutto o per niente". Se la condizione per il NFL è pressoché soddisfatta, allora tutti gli algoritmi producono approssimativamente gli stessi risultati mediando su tutte le funzioni obiettivo. "Non NFL" implica solo che gli algoritmi siano nel complesso non equivalenti per una certa misura delle prestazioni. Per una data misura di interesse, gli algoritmi potrebbero restare equivalenti, o quasi.

Sinossi formale

${\displaystyle Y^{X}}$ è l'insieme di tutte le funzioni obiettivo ${\displaystyle f:X\to Y}$, dove ${\displaystyle X}$ è uno spazio delle soluzioni finito e ${\displaystyle Y}$ è un insieme parzialmente ordinato finito. L'insieme di tutte le permutazioni di ${\displaystyle X}$ è ${\displaystyle J}$. Una variabile casuale ${\displaystyle F}$ sia distribuita su ${\displaystyle Y^{X}}$. Per ciascun ${\displaystyle j}$ in ${\displaystyle J}$, sia ${\displaystyle F\circ j}$ una variabile casuale distribuita su ${\displaystyle Y^{X}}$, con ${\displaystyle P(F\circ j=f)=P(F=f\circ j^{-1})}$ per ogni f in ${\displaystyle Y^{X}}$.

Sia ${\displaystyle a(f)}$ l'output dell'algoritmo di ricerca ${\displaystyle a}$ sull'input ${\displaystyle f}$ . Se ${\displaystyle a(F)}$ e ${\displaystyle a'(F)}$ sono identicamente distribuite per tutti gli algoritmi ${\displaystyle a}$ e ${\displaystyle a'}$, allora ${\displaystyle F}$ ha una distribuzione NFL. Questa condizione è valida se e solo se ${\displaystyle F}$ e ${\displaystyle F\circ j}$ sono identicamente distribuite per tutti i ${\displaystyle j}$ in ${\displaystyle J}$. In altre parole, non c'è pasto gratis per gli algoritmi di ricerca se e solo se la distribuzione delle funzioni obiettivo è invariante rispetto alla permutazione dello spazio delle soluzioni. I teoremi NFL insiemistici sono stati recentemente generalizzati a casi di ${\displaystyle X}$ e ${\displaystyle Y}$ di cardinalità arbitraria.

Origini

Wolpert e Macready forniscono due principali teoremi NFL, il primo riguarda le funzioni obiettivo non cambiano nel corso della ricerca mentre il secondo riguarda le funzioni obiettivo possono cambiare.

Teorema 1 : Per ogni coppia di algoritmi a ₁ e a ₂

${\displaystyle \sum _{f}P(d_{m}^{y}|f,m,a_{1})=\sum _{f}P(d_{m}^{y}|f,m,a_{2}),}$ Dove ${\displaystyle d_{m}^{y}}$ denota l'insieme ordinato di dimensione ${\displaystyle m}$ dei valori di costo ${\displaystyle y\in Y}$ associati ai valori di input ${\displaystyle x\in X}$, ${\displaystyle f:X\rightarrow Y}$ è la funzione che viene ottimizzata e ${\displaystyle P(d_{m}^{y}|f,m,a)}$ è la probabilità condizionata di ottenere una data sequenza di valori di costo dall'algoritmo ${\displaystyle a}$ eseguito ${\displaystyle m}$ volte sulla funzione ${\displaystyle f}$.

In sostanza ciò significa che quando tutte le funzioni f sono equiprobabili, la probabilità di osservare una sequenza arbitraria di ${\displaystyle m}$ valori nel corso della ricerca non dipende dall'algoritmo di ricerca.

Il secondo teorema stabilisce un risultato NFL "più sottile" per funzioni obiettivo che variano nel tempo.

Interpretazioni dei risultati

Un'interpretazione convenzionale, ma non del tutto accurata, dei teoremi NFL è che "una strategia di ottimizzazione universale di uso generale è teoricamente impossibile e l'unico modo in cui una strategia può superare un'altra è specializzarsi sullo specifico problema in esame". È il caso di fare diverse osservazioni:

• In teoria, esiste un ottimizzatore quasi universale di uso generale. Ogni algoritmo di ricerca funziona bene su quasi tutte le funzioni obiettivo. Quindi, se non ci si preoccupa delle differenze "relativamente piccole" tra gli algoritmi di ricerca, ad esempio perché il tempo di elaborazione è economico, non ci si dovrebbe preoccupare di non avere pasti gratis.
• Un algoritmo può superare un altro in un problema quando nessuno dei due è specializzato per quel problema. Anzi, può darsi che entrambi gli algoritmi siano tra i peggiori per quel problema. Più in generale, Wolpert e Macready hanno sviluppato una misura del grado di "allineamento" tra un algoritmo e una distribuzione sui problemi (in senso stretto, un prodotto interno). Affermare che un algoritmo si adatta meglio a una distribuzione rispetto a un altro non significa che uno dei due sia stato consapevolmente specializzato per quella distribuzione; un algoritmo può avere un buon allineamento semplicemente per fortuna.
• In pratica, alcuni algoritmi rivalutano le soluzioni candidate. Il motivo per cui si considerano le prestazioni solo su candidati mai valutati prima è per assicurarsi che, nel confrontare algoritmi, si stiano confrontando soluzioni identiche. Inoltre, qualsiasi superiorità di un algoritmo che non rivaluta mai i candidati rispetto a un altro algoritmo che lo fa su un particolare problema potrebbe non avere nulla a che fare con la specializzazione del problema.
• Per quasi tutte le funzioni obiettivo, la specializzazione è essenzialmente accidentale. Le funzioni obiettivo incomprimibili, o casuali di Kolmogorov, non hanno alcuna regolarità che un algoritmo possa sfruttare, per quanto riguarda la lavorazione di Turing universale utilizzata per definire la casualità di Kolmogorov. Quindi si supponga che esista una scelta chiaramente superiore di macchina di Turing universale. Quindi, data una funzione obiettivo incomprimibile per quella macchina di Turing, non c'è alcuna base per scegliere tra due algoritmi se entrambi sono comprimibili, come misurato utilizzando quella macchina di Turing. Se un algoritmo scelto funziona meglio della maggior parte, il risultato è casuale. Una funzione casuale di Kolmogorov non ha una rappresentazione più piccola di una tabella di ricerca che contiene un valore (casuale) corrispondente a ciascun punto nello spazio di ricerca; qualsiasi funzione che può essere espressa in modo più compatto è, per definizione, non casuale di Kolmogorov.

In pratica, solo le funzioni obiettivo altamente comprimibili (lontane dall'essere casuali) possono trovare posto nella memoria dei computer, e non è detto che ogni algoritmo funzioni bene su quasi tutte le funzioni comprimibili. In genere, l'integrazione nell'algoritmo di conoscenza pregressa sul problema comporta un vantaggio in termini di prestazioni. Sebbene i risultati NFL costituiscano, in senso stretto, teoremi di piena occupazione per gli esperti di ottimizzazione, è importante tenere presente un contesto più ampio. Da un lato, gli esseri umani spesso dispongono di scarse conoscenze pregresse con cui lavorare. Dall'altro, l'integrazione della conoscenza pregressa non garantisce un gran miglioramento delle prestazioni su certi problemi. Infine, il costo del tempo è molto maggiore per gli umani rispetto alle macchine. In molti i casi un'azienda preferisce ottimizzare una funzione in modo lento con un programma senza modifiche piuttosto che rapidamente usando un programma modificato dall'uomo.

I teoremi NFL non indicano che sia vano tentare di risolvere problemi con algoritmi non specializzati. Nessuno è stato in grado di determinare la proporzione di problemi pratici per i quali un algoritmo produce rapidamente buoni risultati. E c'è un vantaggio pratico, per nulla in conflitto con la teoria. Eseguire l'implementazione di un algoritmo su un computer costa pochissimo rispetto al costo del tempo per un esperto e al beneficio di una buona soluzione. Se un algoritmo riesce a trovare una soluzione soddisfacente in un tempo accettabile, un piccolo investimento ha prodotto un grande guadagno. Se l'algoritmo fallisce, allora la perditaè contenuta.

Recentemente alcuni filosofi della scienza hanno sostenuto che esistono modi per aggirare i teoremi NFL, utilizzando la cosiddetta "meta-induzione". Wolpert affronta tali argomentazioni in.

Coevoluzione

Wolpert e Macready hanno dimostrato che nell'ottimizzazione coevolutiva ci sono pasti gratis. La loro analisi "copre i problemi di 'auto-gioco' (self-play). In tali problemi, l'insieme dei giocatori lavora insieme per produrre un campione, che poi affronta uno o più antagonisti in una successiva partita multigiocatore". Cioè, l'obiettivo è ottenere un buon giocatore, ma senza una funzione obiettivo. La bontà di ciascun giocatore (soluzione candidata) viene valutata osservando la qualita del suo gioco contro gli altri. Un algoritmo tenta di utilizzare giocatori e loro qualità di gioco per ottenere giocatori migliori. Il giocatore ritenuto il migliore di tutti dall'algoritmo è il campione. Wolpert e Macready hanno dimostrato che alcuni algoritmi coevolutivi sono generalmente superiori ad altri algoritmi per qualità dei campioni ottenuti. La generazione di un campione attraverso self-play è di interesse nel calcolo evolutivo e nella teoria dei giochi. I risultati non sono applicabili alla coevoluzione delle specie biologiche, che non produce campioni.

Note

Voci correlate

• Bias induttivo
• Rasoio di Occam
• Semplicità
• Teorema del brutto anatroccolo

Altri progetti

• Wikimedia Commons contiene immagini o altri file su No free lunch

Collegamenti esterni

• http://www.no-free-lunch.org
• Radcliffe e Surry, 1995, "Fundamental Limitations on Search Algorithms: Evolutionary Computing in Perspective" (uno dei primi articoli pubblicati su NFL, apparso subito dopo l'articolo ICML di Schaffer, a sua volta basato sul pre-print di Wolpert; disponibile in vari formati)
• Pubblicazioni NFL di Thomas English, su boundedtheoretics.com.
• Pubblicazioni NFL di Christian Igel e Marc Toussaint, su neuroinformatik.ruhr-uni-bochum.de.
• Pubblicazioni NFL e "pasti gratis" di Darrell Whitley, su cs.colostate.edu.
• Vecchio elenco di pubblicazioni di David Wolpert, William Macready e Mario Koeppen su ottimizzazione e ricerca, su ti.arc.nasa.gov.

V · D · M Apprendimento automatico
Problemi	Teoria dell'apprendimento statistico · Classificazione · Regressione · Classificazione a singola classe · Ranking · Regole di associazione · Apprendimento non supervisionato · Apprendimento semi-supervisionato · Apprendimento supervisionato · Apprendimento debolmente supervisionato · Apprendimento auto-supervisionato · Apprendimento da pochi esempi · Apprendimento gerarchico · Apprendimento per rinforzo · Apprendimento profondo · Apprendimento online · Apprendimento incrementale · Apprendimento trasduttivo · Apprendimento di rappresentazioni · Apprendimento per similarità · Apprendimento per contrasto · Concept drift · Meta-apprendimento · Dati mancanti
Apprendimento non supervisionato	Clustering · Clustering gerarchico · K-means · Algoritmo EM · Clustering spettrale · DBSCAN · Mean shift · Rete generativa avversaria (cGAN · VAE-GAN · cycleGAN)
Apprendimento supervisionato	Albero di decisione · Foresta casuale · Conditional random field CRF · Modello di Markov nascosto · Algoritmo k-nearest neighbors (k-NN) · Ragionamento basato su casi (CBR) · Classificatore bayesiano · Rete neurale artificiale · Regressione lineare · Regressione logistica · Modello grafico · Rete bayesiana · Macchine a vettori di supporto (SVM) · Processo gaussiano · Modello ensemble · Boosting · Bagging · Classifier chain · Cascading · Classificatore ECOC · Stacking · Voting
Apprendimento per rinforzo	Q-learning · SARSA · TD
Riduzione della dimensionalità	Analisi fattoriale · Analisi della correlazione canonica (CCA) · Analisi delle componenti indipendenti (ICA) · Analisi discriminante lineare (LDA) · Analisi delle componenti principali (PCA) · Apprendimento di varietà (manifold learning) · Estrazione di caratteristiche · Immersione localmente lineare (LLE) · Isomap · Scaling multidimensionale (MDS) · Selezione delle caratteristiche · t-distributed stochastic neighbor embedding (t-SNE)
Reti neurali artificiali	Percettrone · Percettrone basato su kernel · Rete neurale a funzioni base radiali (RBF net) · Rete neurale feed-forward · Rete di Hopfield · Percettrone multistrato · Rete neurale ricorrente (LSTM) · Macchina di Boltzmann ristretta · Mappa auto-organizzata · Rete neurale convoluzionale · Rete neurale a ritardo · Rete neurale spiking · Rete neurale grafica · Trasformatore
Software	Keras · Microsoft Cognitive Toolkit · Scikit-learn · TensorFlow · Theano · PyTorch · Weka
Altro	Algoritmo genetico · Particle Swarm Optimization · Caratteristica · Compromesso bias-varianza · Minimizzazione del rischio empirico

Portale Informatica

Portale Matematica