Teorema No Free Lunch

Les teoremes No Free Lunch (NFL)  publicats en 1997 per David Wolpert i William MacReady, són un conjunt de teoremes matemàtics que tenen implicacions per al camp de l'optimisació i l'aprenentage supervisat. Estes teoremes establixen que, per a qualsevol algoritme d'optimisació, qualsevol millora en l'eixercite sobre una classe de problemes es compensa en un eixercite inferior en una atra classe, és dir, no existix un algoritme òptim universal per a tots els problemes d'optimisació.

L'idea bàsica darrere de les teoremes NFL és que, per a qualsevol algoritme d'optimisació, qualsevol millora en el rendiment sobre una classe de problemes es compensa en el rendiment sobre una atra classe. En atres paraules, no existix un algoritme d'optimisació que s'adapte a tots els problemes per igual. Est és un resultat contraintuitivo, ya que implica que hi ha llímits fonamentals en el poder dels algoritmes d'optimisació.

Implicacions

Supongam que tenim dos algoritmes d'optimisació, A i B, i dos classes de problemes, P i Q. Assumim ademés que l'algoritme A té un millor rendiment que l'algoritme B en els problemes de la classe P, mentres que l'algoritme B té un millor rendiment que l'algoritme A en els problemes de la classe Q. Llavors, segons la teorema NFL, deu existir alguna distribució de problemes sobre P i Q tal que l'algoritme A i l'algoritme B tinguen un rendiment igual en promig.

En atres paraules, qualsevol millora en el rendiment de l'algoritme A sobre l'algoritme B en els problemes de classe P es compensa exactament en una disminució en el rendiment en els problemes de classe Q, i viceversa.

Podem expressar esta idea utilisant el concepte de valor esperat. Siga f una funció d'optimisació que assigna un espai d'entrada X a un conjunt de possibles valors d'eixida I. Siga F el conjunt de totes les possibles funciones f, i siga D una distribució de provabilitat sobre l'espai d'entrada X. Llavors, el valor esperat d'una funció f sobre la distribució D es definix com:

$E[f]=\underset{x}{\int }f(x)D(x)dx$

a on l'integral es pren sobretot l'espai d'entrada X. En atres paraules, el valor esperat d'una funció f és el valor promig que f pren sobre totes les possibles entrades, ponderat per la seua provabilitat d'ocurrència.

Les implicacions de la teorema NFL són significatives. Sugerixen que l'eixercite dels algoritmes d'optimisació està llimitat inherentemente per l'estructura dels problemes que es resolen. Açò significa que, en la pràctica, diferents algoritmes d'optimisació poden ser més adequats per a diferents tipos de problemes. També significa que la busca d'un algoritme òptim universal és inútil.

Expressió matemàtica

Les teoremes NFL es poden expressar matemàticament. Sean A i B dos algoritmes d'optimisació, i siguen P i Q dos classes de problemes. Siga $f_A(P)$ la millor solució trobada per l'algoritme A en els problemes de la classe P, i $f_B(Q)$ la millor solució trobada per l'algoritme B en els problemes de la classe Q. Llavors, les teoremes NFL establixen que:

$E[f_A(P)]=E[f_B(Q)]$

a on $E[f_A(P)]$ és el valor esperat de la millor solució trobada per l'algoritme A sobre els problemes de la classe P, i $E[f_B(Q)]$ és el valor esperat de la millor solució trobada per l'algoritme B sobre els problemes de la classe Q.

Açò significa que, independentment de lo ben que s'eixercite un algoritme A en els problemes de la classe P, sempre existix alguna distribució de problemes sobre P i Q tal que l'algoritme B tinga un eixercite igualment bo en promig.